Behörighetskrav

Matematik 20 p/30 hp och datavetenskap 15 p/22,5 hp, däribland Programmeringsteknik MN2 eller motsvarande.

Mål

För godkänt betyg ska studenten kunna

• analysera körtiden för en (enkel) algoritm/program i relation till indatats storlek, i bästa, sämsta, och genomsnittliga fall,
• besvara frågor för att utvärdera algoritm/program: vad händer med körtiden om indata blir dubbelt så stor? Vilka algoritmer/program ska man välja bland olika alternativ för samma specifikation? Med vilka datastrukturer ska man implementera en algoritm, med tanke på operationerna (lägga till, ändra, ta bort, söka, sortera) på datat. Spelar det någon roll (för stora indata) att byta ut en del av algoritmen/programmet mot ett annat?
• i detalj ange antaganden som ligger till grund för denna analys.
• analysera körtiden för operationerna (lägga till, ändra, ta bort, söka, sortera) för vanliga datastrukturer (listor, arrayer, köer, prioritetsköer, stackar, träd, och heaps).
• förklara fördelar och nackdelar med "giriga algoritmer" (som gör lokalt optimala val utan att ångra sig) för optimeringsproblem som generellt kräver för lång körtid för vanliga indata.

Innehåll

Matematiska grunder: asymptotisk notation,

summationer, rekursionsformler.

Datastrukturer: stackar, köer, träd, prioritetsköer, "heaps". Sökmetoder: binära sökträd, balanserade sökträd, hashtabeller.

Sorteringsmetoder. Enkla grafalgoritmer och "giriga algoritmer". Implementering i ett imperativt (evt. objektorienterat) språk.

Undervisning

Föreläsningar, lektioner och obligatoriska inlämningsuppgifter.

Examination

Skriftligt prov (4,5 hp) samt inlämningsuppgifter (3 hp).

Övriga föreskrifter

Kursen kan ej räknas in i examen tillsammans med Algoritmer och datastrukturer I

(1TD442, 1DL210) eller Programkonstruktion II (1IT022).