Algoritmer och datastrukturer I

5 hp

Kursplan, Grundnivå, 1DL210

Det finns en senare version av kursplanen.

Kod: 1DL210
Utbildningsnivå: Grundnivå
Huvudområde(n) med fördjupning: Datavetenskap G1F, Teknik G1F
Betygsskala: Med beröm godkänd (5), Icke utan beröm godkänd (4), Godkänd (3), Underkänd (U)
Fastställd av: Teknisk-naturvetenskapliga fakultetsnämnden, 2 maj 2017
Ansvarig institution: Institutionen för informationsteknologi

Behörighetskrav

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

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.

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.

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

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

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

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