Algoritmer och datastrukturer II

5 hp

Kursplan, Grundnivå, 1DL230

Kursen är avvecklad.

Det finns en senare version av kursplanen.

Kod: 1DL230
Utbildningsnivå: Grundnivå
Huvudområde(n) med fördjupning: Datavetenskap G1F
Betygsskala: Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
Fastställd av: Teknisk-naturvetenskapliga fakultetsnämnden, 12 mars 2009
Ansvarig institution: Institutionen för informationsteknologi

Behörighetskrav

Matematik15 hp och datavetenskap 30 hp inklusive Algoritmer och datastrukturer I.

För godkänt betyg ska studenten kunna

använda notationen för asymptotisk tillväxt av funktioner för att beskriva komplexitet av beräkningsproblem.
härleda ekvationer för en algoritms komplexitet och lösa dessa.
använda vanliga algoritmiska tekniker som dynamisk programmering, greedy algorithms, etc.
lösa enkla problem inom grafalgoritmer, sträng matchning och geometriska algoritmer.

Funktioners tillväxt, komplexitet av rekursiva algoritmer, dynamisk programmering inkl. Strassen's algoritm för matrismultiplikation,

"greedy algorithms", grafalgoritmer, Tillämpningar, t.ex. strängmatchning, geometriska algoritmer, och datakomprimering.

Föreläsningar, lektioner och övningar.

Skriftligt prov (3 hp) samt inlämningsuppgifter (2 hp).