Antal poäng: 4. Betygskala: TH. Valfri för: D4, E4, F4. Kursansvarig: Universitetslektor Rolf Karlsson, Rolf.Karlsson@cs.lth.se, Inst f datavetenskap. Förkunskapskrav: EDA025/EDA026/EDA027 Algoritmer och datastrukturer eller EDA020 Programmering 2. Prestationsbedömning: Slutbetyget baseras på dels en skriftlig tentamen dels fem inlämningsuppgifter. Hemsida: http://www.cs.lth.se. Övrigt: Kursen ges i samarbete med Datavetenskap, nat. fak.

Mål
Att ge en djupare insikt i konstruktion och analys av algoritmer samt ge träning i algoritmisk problemlösning.

Innehåll

• Lösning av rekursionsekvationer.

• Randomiserade algoritmer.

• Amorterad analys.

• Ordningsstatistik.

• Rödsvarta träd.

• Dynamisk programmering.

• Geometriska algoritmer.

• Kortaste vägar.

• Nätverksflöde.

• Mönstersökning i strängar.

Litteratur
Cormen T, Leiserson C, Rivest R, Stein C: Introduction to Algorithms, Second Ed. McGraw-Hill & MIT Press, 2001.