Antal högskolepoäng: 7,5. Betygsskala: TH. Nivå: A (Avancerad nivå). Huvudområde: Teknik. Undervisningsspråk: Kursen ges på engelska. Överlappar följande kurs/kurser: EDA110. Valfri för: D4, D4pv, E4, E4pv, F4, F4bs, F4pv, Pi4, Pi4pv. Kursansvarig: Univ.lektor Rolf Karlsson, Rolf.Karlsson@cs.lth.se, Inst f datavetenskap. Förkunskapskrav: EDAA01 Programmeringsteknik-fördjupningskurs eller EDA027 Algoritmer och datastrukturer. Dessutom FMA420, Linjär algebra. Förutsatta förkunskaper: FMA410 Matematik, endimensionell analys. Prestationsbedömning: Tentamen är skriftlig. Slutbetyg i kursen grundar sig i huvudsak på tentamen men kan påverkas positivt av resultatet på inlämningsuppgifter. För godkänt betyg krävs också slutfört obligatoriskt projekt. Poängsatta delmoment: 2. Hemsida: http://cs.lth.se/edan05.

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. Fibonacci-heapar. Amorterad analys. van Emde Boas-träd. Dynamisk programmering. Geometriska algoritmer. Sorterande nätverk. Mönstersökning i strängar. Ett obligatoriskt projekt.

Litteratur
Cormen T, Leiserson C, Rivest R & Stein C: Introduction to Algorithms, Third Ed.. MIT Press 2009. ISBN: 978-0-262-53305-8

Kod: 0109. Benämning: Algoritmteori.
Antal Högskolepoäng: 6. Betygsskala: TH. Prestationsbedömning: Skriftlig tentamen. Slutbetyg på kursen grundar sig i huvudsak på denna tentamen, men kan påverkas positivt av resultaten på inlämningsuppgifter.

Kod: 0209. Benämning: Projekt.
Antal Högskolepoäng: 1,5. Betygsskala: UG. Prestationsbedömning: För godkänt betyg på kursen måste projektet vara godkänt.