Antal poäng: 4. Betygskala: TH. Valfri för: D4, E4, F4, L4XGM, L3XTG, Pi3. Kursansvarig: Univ.lektor Rolf Karlsson, Rolf.Karlsson@cs.lth.se, Inst f datavetenskap. Förkunskapskrav: EDA027 Algoritmer och datastrukturer, FMA410 Matematik, endimensionell analys och FMA420/FMA425 Linjär algebra. Prestationsbedömning: Slutbetyget baseras på dels en skriftlig tentamen dels fem inlämningsuppgifter. Övrigt: Kursen ges i samarbete med Datavetenskap, Nat. fak. Kursen ges på engelska. Hemsida: http://www.cs.lth.se/EDA110.

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.

• Ordningsstatistik.

• Rödsvarta träd.

• Dynamisk programmering.

• Giriga algoritmer.

• Geometriska algoritmer.

• Kortaste vägar.

• Nätverksflöde.

• Sorterade nätverk.

• 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. ISBN: 0-262-53196-8