Behörighetskrav

10 hp programmering (Programkonstruktion, Programmeringsteknik II eller motsvarande) och 10 hp matematik, inklusive grundläggande algebra. Alternativt 45 hp inom Masterprogram i språkteknologi (HSP2M).

Mål

För godkänt betyg ska studenten kunna:

• analysera körtiden för algoritmer/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.
• använda asymptotisk notation för att resonera kring algoritmer och datastrukturers tids- och minneskomplexitet.
• resonera grundläggande kring algoritmers korrekthet.
• föreslå enkla algoritmer med lämplig komplexitet för nya väldefinierade problem.

Innehåll

Matematiska grunder: asymptotisk notation, summationer, rekursionsformler och induktion.

Datastrukturer: träd, köer, stackar, länkade listor, prioritetsköer, "heaps", binära sökträd och hashtabeller.

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

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

Metoder: söndra och härska.

Implementering av algoritmer och datastrukturer.

Undervisning

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

Examination

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

Om särskilda skäl finns får examinator göra undantag från det angivna examinationssättet och medge att en enskild student examineras på annat sätt. Särskilda skäl kan t.ex. vara besked om särskilt pedagogiskt stöd från universitetets samordnare för studenter med funktionsnedsättning.

Övriga föreskrifter

Kursen kan inte räknas in i examen med Programkonstruktion II (1IT022) eller Datastrukturer (1DL009, 1TD191, 1MB026).