Algoritmer: beräkningsgeometri, grafalgoritmer, talteoretiska algoritmer, strängmatchning. Algoritmanalys och algoritmkonstruktion: dynamisk programmering, amorterad analys, rimlighetsbedömningar. Programmeringsfärdigheter, framför allt i C++ och Java.
Kursen fokuserar på problemlösning hela vägen från teori (i form av algoritmdesign) till praktik (i form av ett fungerande program).
Under kursens gång löser studenten ett stort antal hemuppgifter, implementerar ett antal algoritmer för att bygga upp ett mindre algoritmbibliotek, löser problem i små grupper under "problemsessioner", samt presenterar lösningar på hemuppgifter muntligt.
Efter godkänd kurs ska studenten kunna
- använda algoritmkonstruktionsmetoder som giriga algoritmer, dynamisk programmering, dekomposition och kombinatorisk sökning för att konstruera algoritmer i syfte att lösa givna problem
- använda grundläggande algoritmer inom områden som t.ex.grafteori, talteori, och geometri på givna problem samt anpassa dem till problemspecifika omständigheter
- analysera effektiviteten hos olika algoritmer för att avgöra vilka som i ett givet sammanhang är tillräckligt effektiva
- jämföra olika problem med avseende på svårighetsgrad
- implementera algoritmer och datastrukturer givet abstrakta specifikationer
- identifiera buggar i andras lösningsförsök på problem
- kommunicera med andra under problemlösning i grupp
- presentera algoritmer, datastrukturer och problem muntligt på ett koncist och begripligt sätt
i syfte att
- kunna använda programmering som ett verktyg för problemlösning
- kunna tillämpa teoretiska kunskaper från andra datalogikurser på praktisk problemlösning.
