Algorithm Theory

Antal poäng: 4.0. Valfri för: D4, E4, F4. Kursansvarig: Rolf Karlsson. Förkunskapskrav: godkänt betyg i EDA 025 Algoritmer och datastrukturer eller EDA 020 Programmering 2. Prestationsbedömning: Slutbetyget baseras på dels en skriftlig tentamen dels på inlämningsuppgifterna. Övrigt: Kursen ges i samarbete med Datalogi och numerisk analys, mat. nat. fak.

Obligatoriska moment: Fem inlämningsuppgifter.

Innehåll

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

Ordningsstatistik. Rödsvarta träd. Dynamisk programmering. Union-Find. Max-flöden. Sorterande nätverk. Parallella algoritmer. Strängmatchning. Datalogisk geometri.

Litteratur

Cormen, T., Leiserson, C. & Rivest, R.: Introduction to Algorithms. McGraw-Hill & MIT Press, 1990.