Behörighetskrav

10 hp programmering (Programkonstruktion, Programmeringsteknik II eller motsvarande) och 10 hp matematik, inklusive grundläggande algebra.

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,
• välja lämpliga algoritmer och datastrukturer för lagring av data, sökning och sortering, samt implementera dessa.
• använda och implementera grundläggande grafalgoritmer.

Innehåll

Matematiska grunder: asymptotisk notation, summationer, rekursionsformler.

Datastrukturer: träd, köer, stackar, prioritetsköer, "heaps".

Sökmetoder: binära sökträd, balanserade sökträd, hashtabeller.

Sorteringsmetoder: instickssortering, merge sort, quick sort, heap sort.

Enkla grafalgoritmer: djupet-först och bredden-först sökning, topologisk sortering, komponenter.

Metoder: söndra och härska.

Implementering av algoritmer och datastrukturer.

Undervisning

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

Examination

Skriftligt prov (4 hp) samt inlämningsuppgifter (1 hp).

Övriga föreskrifter

Kursen kan inte räknas in i examen med Programkonstruktion II (1IT022) eller

Datastrukturer (1DL009, 1TD191, 1MB026).