Algoritmer og datastrukturer 2

• Beskrive en algoritme præcist, kortfattet og entydigt.
• Anvende datastrukturer og algoritmer fra kurset.
• Analysere algoritmer og datastrukturer, herunder være i stand til at bestemme værste-tilfælde, forventet og amortiseret køretid og pladsforbrug i asymptotisk notation.
• Argumentere for korrekthed af algoritmer.
• Identificere og formulere det underliggende algoritmiske problem i en given problemstilling.
• Analysere, vurdere og sammenligne algoritmer/​datastrukturer og på baggrund af dette vælge en passende algoritme/datastruktur til løsning af et givet problem.
• Anvende strømningsgrafer til at modellere en given problemstilling.
• Tilpasse algoritmer og datastrukturer til at løse et givet problem.
• Sammenligne forskellige algoritmiske paradigmer (f.eks. del-og-hersk, dynamisk programmering, randomiserede algoritmer og strømningsalgoritmer) og vælge et passende til løsning af et givet problem.
• Genkende et NP-komplet problem og bevise at det er NP-komplet.
• Implementere og afprøve datastrukturer og algoritmer, samt lave passende test og empiriske analyser af dem.
• Argumentere for valg foretaget i forbindelse med løsning af et problem.

Strømingsalgoritmer. Datatrukturer til indeksering og partiel sum (f.eks. hashtabeller, Fenwick trees). Algoritmer til streng matching. Teknikker til design og analyse af algoritmer (dynamisk programmering, del-og-hersk, randomiserede algoritmer og datastrukturer, forventet og amortiseret køretidsanalyse). NP.

02105/02326, Kurset bygger på 02105 Algoritmer og Datastrukturer I. Det forventes at den studerende kan pensum fra 02105, som inkluderer

Basal algoritmisk analyse, asymptotisk notation.
Datastrukturer: stakke, køer, hægtede lister, træer, hobe, prioritetskøer, union-find, balancerede binære søgetræer.
Søgning og sortering: binær søgning, hobsortering, indsættelsessortering, flettesortering.
Grafalgoritmer: korteste veje (Dijkstra og korteste veje i DAGs), mindste udspændende træer, topologisk sortering, breddeførst søgning, dybdeførst søgning, repræsentation af grafer.

Forelæsninger og grupperegninger.