Antal högskolepoäng: 6. Betygskala: TH. Nivå: A (Avancerad nivå). Undervisningsspråk: Kursen ges på engelska. Valfri för: D4, D4ps, E4, E4ps, F4, F4tvb, L4, Pi3, Pi3sbs. 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: Tentamen är skriftlig. Slutbetyg i kursen grundar sig i huvudsak på tentamen men kan påverkas positivt av resultatet på inlämningsuppgifter. Övrigt: Kursen ges i samarbete med Datavetenskap, Nat. fak. Hemsida: http://www.cs.lth.se/EDA110.

Syfte
Att ge fördjupade kunskaper i konstruktion och analys av effektiva algoritmer och ge träning i algoritmisk problemlösning

Mål

Kunskap och förståelse
För godkänd kurs skall studenten

• ha ingående kunskap om egenskaper och användbarhet hos presenterade datastrukturer och problemlösningstekniker

• förstå vad som är en praktiskt effektiv algoritm för stora problem

Färdighet och förmåga
För godkänd kurs skall studenten

• kunna analysera algoritmer med avseende på tids- och utrymmeskomplexitet

• kunna formulera och lösa rekursionsekvationer

• kunna tillämpa de givna teknikerna vid problemlösning

• ha ökad förmåga att utveckla effektiva algoritmer för praktiskt relevanta problem

Innehåll
Lösningsmetoder för rekursionsekvationer. Ordningsstatistik. Rödsvarta träd. Utökade datastrukturer. Dynamisk programmering. Giriga algoritmer. Kortaste vägar. Geometriska algoritmer. Maxflöde. Sorterande 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