DM507/DM578/DS814/SE4-DMAD Algoritmer og datastrukturer

Forår 2026
Rolf Fagerberg

Generel information

Kurset starter mandag den 2. februar og slutter fredag den 29. maj.

• Lærebog
• Tidligere eksamensopgaver
• Skema for DM507, DM578, DS814 og SE4-DMAD. Samlet skema for alle fire.
• Officiel kursusbeskrivelse for DM507, DM578, DS814 og SE4-DMAD
• Instruktorer
• Formelsamling
• Visualiseringer

Timer

Hvis tid eller sted er angivet med rødt, er det for at henlede opmærksomheden på, at placeringen afviger fra det normale.

Uge	Type	Dato	Tid	Lokale	Indhold
6	F	Mandag 2/2	16-18	U55	Introduktion til kurset (slides med overlays/uden overlays, kapitel 1 i lærebogen [3. udgave: kapitel 1]). Om algoritmeanalyse (dele af afsnit 2.2 i lærebogen [3. udgave: dele af afsnit 2.2], slides med overlays/uden overlays). Eksempel på en (meget detaljeret) algoritmeanalyse: Ombytningspuslespil (slides med overlays/uden overlays, noter). Et ombytningspuslespil fra nettet.
7	F	Tirsdag 10/2	08-10	U1	Lidt mere om algoritmeanalyse (dele af afsnit 2.2 i lærebogen [3. udgave: dele af afsnit 2.2], slides med overlays/uden overlays), især om RAM-modellen (side 5 i slides). Start på sorteringsalgoritmer: Insertionsort (side 157-160 i lærebogen [3. udgave: side 147-150], afsnit 2.1-2.2 i lærebogen [3. udgave: afsnit 2.1-2.2], side 1-6 i slides med overlays/uden overlays). Vi vender tilbage til begrebet "Invariant" lidt senere i kurset - de dele af teksten i lærebogen, som snakker om dette, kan indtil videre læses let.
7	F	Torsdag 12/2	10-12	U55	Mere om sorteringsalgoritmer: Selectionsort, Mergesort (afsnit 2.3 i lærebogen [3. udgave: afsnit 2.3], side 7-13 i slides med overlays/uden overlays). Vi vender tilbage til begrebet "Divide and Conquer" lidt senere i kurset - de dele af teksten i lærebogen, som snakker om dette, kan indtil videre læses let. Noter om logaritmefunktionen. [Yderligere kommentarer (ikke pensum): Noterne om logaritmefunktionen antager, at man kender begrebet omvendt funktion. Man kan få genopfrisket dette i afsnit 7.1 og 7.3 af Benjamin Teglbjærgs noter til Matematik B på HHX. ] Asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1], side 1-3 og 9-23 i slides med overlays/uden overlays, Det kan være en fordel at orientere sig i afsnit 3.3 i lærebogen [3. udgave: afsnit 3.2], hvis der i kurset bruges matematiske formler, definitioner og metoder, man har glemt.
7	E				Opgaver.
8	F	Torsdag 19/2	10-12	U1	Afslutning af asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1], resten af siderne i slides med overlays/uden overlays). Java-programmerne fra slides: Linear.java, Quadratic.java, Cubic.java. Et eksempel på at forskellige algoritmer for samme beregningsproblem kan have meget forskellige køretider: the maximum sum sub-array problem. (slides med overlays/uden overlays, wikipedia).
8	E				Opgaver.
9	F	Tirsdag 24/2	08-10	U1	Divide-and-conquer/rekursive algoritmer (side 34 i lærebogen [3. udgave: side 30], slides med overlays/uden overlays, eksempel i Python som illustrerer flow-of-control). Mergesort formuleret rekursivt (afsnit 2.3 i lærebogen [3. udgave: afsnit 2.3], side 14-15 i slides med overlays/uden overlays). Flere sorteringsalgoritmer: Quicksort (afsnit 7.1-3 i lærebogen [3. udgave: afsnit 7.1-3], side 16-22 i slides med overlays/uden overlays).
9	F	Torsdag 26/2	10-12	U1	Flere sorteringsalgoritmer: Heapsort (afsnit 6.1-4 i lærebogen [3. udgave: afsnit 6.1-4], afsnit B.5.3 i lærebogen [3. udgave: afsnit B.5.3], sidste del af slides med overlays/uden overlays).
9	E				Opgaver.
10	F	Torsdag 5/3	10-12	U1	Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1 i lærebogen [3. udgave: afsnit 8.1], første del af slides med overlays/uden overlays, eksempler på decisiontrees for insertionsort (n=1,2,3,4,5,6,7), mergesort (n=1,2,3,4,5,6,7)) og heapsort (n=1,2,3,4,5,6,7), eksempel i Python på at annotere en sammenligningsbaseret sorteringsalgoritme med elementernes startindekser). Flere sorteringsalgoritmer: sortering af heltal med Countingsort og Radixsort (afsnit 8.2-3 i lærebogen [3. udgave: afsnit 8.2-3], anden del af slides med overlays/uden overlays). For at forstå sidste side af slides om Radixsort, skal man kende det binære talsystem. Gør man ikke det, så check side 5-7 i disse slides med overlays/uden overlays. Prioritetskøer (afsnit  6.5 i lærebogen [3. udgave: afsnit  6.5], slides med overlays/uden overlays).
10	E				Opgaver.