Antal poäng: 4. Betygskala: TH. Valfri för: D4, E4, F4. Kursansvarig: Universitetslektor Rolf Karlsson, Rolf.Karlsson@cs.lth.se. 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. Webbsida: http://www.cs.lth.se. Övrigt: Kursen ges i samarbete med Datavetenskap, mat. 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. & C. Stein: Introduction to Algorithms, Second Ed. McGraw-Hill & MIT Press, 2001.