DM507/DM578/DS814/SE4-DMAD Algoritmer og datastrukturer
Forår 2025
Rolf Fagerberg
Generel information
Kurset starter tirsdag den 4. februar og slutter fredag den
30. maj.
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 |
Tirsdag 4/2 |
08-10 |
U55 |
Introduktion til kurset (slides med
overlays/uden overlays, kapitel 1
i lærebogen [3. udgave: kapitel 1]).
Optagelse af online forelæsning 2021
(introduktion til kursus) (NB: detaljerne om kursets struktur er en
smule ændret, se slides ovenfor i stedet).
Eksempel på en (meget detaljeret) algoritmeanalyse:
Ombytningspuslespil (slides med
overlays/uden overlays,
noter). Et
ombytningspuslespil
fra nettet.
Optagelse af online forelæsning
2021 (ombytningspuslespil).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 1.1, 1.4 og 1.8.
|
| 7 |
F |
Tirsdag 11/2 |
08-10 |
U55 |
Om algoritmeanalyse (dele af afsnit 2.2 i lærebogen [3. udgave: dele af afsnit 2.2], slides
med
overlays/uden overlays,
tidsTabelBeregninger.py).
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.
Optagelse af online
forelæsning 2021 (insertionsort).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 1.5-7.
|
| 7 |
F |
Torsdag 13/2 |
10-12 |
U1 |
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.
Optagelse af online
forelæsning 2021 (selectionsort, merge).
Asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1], side 1-23 i slides
med
overlays/uden overlays,
Java-programmerne fra slides: Linear.java,
Quadratic.java, Cubic.java).
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.
Optagelse af online
forelæsning 2021 (mergesort, asymptotisk analyse).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 2.1-4 (evt. også 2.5 for ekstra
eksempler).
|
| 7 |
E |
|
|
|
Opgaver.
|
| 8 |
F |
Tirsdag 18/2 |
|
Video |
Afslutning af asymptotisk analyse
(videoforelæsning,
afsnit 3.1-2 i lærebogen [3. udgave:
afsnit 3.1], slides med
overlays/uden overlays).
Optagelse af online
forelæsning 2021 (samme som i torsdags).
Et eksempel på at forskellige algoritmer for samme beregningsproblem
kan have meget forskellige køretider: the maximum sum sub-array
problem (videoforelæsning, slides
med
overlays/uden overlays,
wikipedia).
Implementationer af de tre algoritmer for maximum sum sub-array:
MaxSum1.py, MaxSum1.java,
MaxSum2.py, MaxSum2.java,
MaxSum3.py, MaxSum3.java.
Optagelse af
online forelæsning 2021 (maximum sum subarray).
|
| 8 |
E |
|
|
|
Opgaver.
|
| 9 |
F |
Tirsdag 25/2 |
08-10 |
U55 |
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).
Optagelse
af online forelæsning 2021 (rekursive algoritmer).
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).
Optagelse af online forelæsning 2021
(quicksort).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 5.1-4.
|
| 9 |
F |
Torsdag 27/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).
Optagelse af
online forelæsning 2021 (heapsort).
|
| 9 |
E |
|
|
|
Opgaver.
|
| 10 |
F |
Tirsdag 4/3 |
08-10 |
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.
Optagelse
af online forelæsning 2021 (nedre grænser for sortering, Countingsort
og Radixsort).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 8.6.
|
| 10 |
E |
|
|
|
Opgaver.
|
| 11 |
F |
Tirsdag 11/3 |
08-10 |
U1 |
[Det antages i dette kursus, at man allerede er bekendt med de
simple datastrukturer lænket liste, stak og kø,
f.eks. fra ens programmeringskursus. I modsat fald, læs afsnit 10.1-2
i lærebogen [3. udgave: afsnit 10.1-2].]
Prioritetskøer (afsnit 6.5 i lærebogen [3. udgave: afsnit 6.5], slides
med overlays/uden
overlays).
Optagelse
af online forelæsning 2021 (prioritetskøer).
Forslag til yderligere videomateriale (ikke pensum):
Mifta Sintaha,
Tim
Roughgarden, Stanford, afsnit 12.1-3 [bemærk at de enkelte
heap-operationer ikke nødvendigvis hedder det samme som i bogen].
Dictionaries og deres implementation via binære søgetræer
(side 249-251 i lærebogen [3. udgave:
side 229-231], afsnit 10.3 (mest figur 10.6) i lærebogen [3. udgave: afsnit 10.4 (mest figur 10.9)],
afsnit 12.1-3 i lærebogen [3. udgave:
afsnit 12.1-3], første del af slides
med
overlays/uden overlays).
Optagelse af online forelæsning
2021 (binære søgetræer).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 13.1-2 samt 13.3 indtil 22:00.
|
| 11 |
F |
Torsdag 13/3 |
10-12 |
U1 |
Udlevering og gennemgang af projektet, del I (kun
for DM507 og DS814). Redirection af standard input og output (relevant
viden for alle).
Optagelse af online
forelæsning 2021 (udlevering af projekt del
I). Optagelse
af online forelæsning 2021 (redirection).
Rød-sorte træer (afsnit 13.1-4 i lærebogen [3. udgave: afsnit 13.1-4], næste del af slides
med
overlays/uden overlays).
Optagelse af online forelæsning 2021
(rød-sorte træer).
Optagelse af online
forelæsning 2021 (sletning i rød-sorte træer).
Bemærk at lærebogen er ret tung læsning i kapitel 13. Det skyldes
dels, at dens pseudo-kode er fungerende kode (robust og gennemtænkt,
så den også virker i specialtilfælde, såsom tomme træer, etc.) med
alle detaljer, og dels at den udtrykker og beviser invarianter på
niveau 2 (mere om invarianter til en senere forelæsning), dvs. under
henvisning til denne kode. Det anbefales (for alle emner, men her
endnu mere end normalt) at læse lærerens slides før man nærlæser
lærebogen.
|
| 11 |
E |
|
|
|
Opgaver.
|
| 12 |
F |
Tirsdag 18/3 |
08-10 |
U1 |
Dekoration af binære søgetræer (afsnit 17.1-2 i lærebogen [3. udgave: afsnit 14.1-2], slides
med
overlays/uden overlays).
Optagelse af online
forelæsning 2021 (dekoration af binære søgetræer).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 13.3 fra 22:00.
Implementation af dictionaries via hashing (afsnit 11.1-4 i lærebogen
(dog ikke: siderne 278-281, beviset for corollary 11.3, afsnit
11.3.3-1.3.5, siderne 297 (midten) til 300) [3. udgave: afsnit 11.1-4 (dog ikke: siderne 258-260,
266-268, 274-276)], slutningen af slides
med
overlays/uden overlays).
Optagelse af online
forelæsning 2021
(hashing). Optagelse
af online forelæsning 2021 (mere om hashing).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit
13.4-6. Tim
Roughgarden, Stanford, afsnit 14.1-3 og 15.1.
En god indføring i state-of-the-art hashing metoder, som både er
effektive i praksis og teoretisk gode, kan findes i disse
noter af Mikkel Thorup (ikke
pensum).
|
| 12 |
E |
|
|
|
Opgaver.
|
| 13 |
F |
Tirsdag 25/3 |
08-10 |
U45 |
Invarianter (siderne 20-21, 167-168, 184 og 340-345 i lærebogen [3. udgave: siderne 18-20, 32-33, 157, 171-173 og
318-322], slides med
overlays/uden overlays).
Optagelse af
online forelæsning 2021 (invarianter).
Divide and Conquer algoritmer, rekursionsligninger, og analyse heraf
via rekursionstræer og via Master Theorem (afsnit 4.0, 4.4 og 4.5 i
lærebogen [3. udgave: afsnit 4.0, 4.4 og 4.5
(bemærk at i 3. udgave er case 2 i Master Theorem en smule mindre
generel end i 4. udgave)], side 1-14 i
med
overlays/uden
overlays).
Optagelse af online
forelæsning 2021 (rekursionsligninger). Bemærk at i 4. udgave er
case 2 i Master Theorem en smule mere generel end i 3. udgave, som
denne online forelæsning referer til).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 4.1, 4.2, 4.3 og 4.5 [bemærk at udgaven
af Master Theorem i disse videoer er mindre generel end lærebogens, og
at rækkefølgen af cases er forskellig].
|
| 13 |
F |
Torsdag 27/3 |
10-12 |
U1 |
Mere om rekursionstræsmetoden og Master Theorem (afsnit 4.0, 4.4 og
4.5 i lærebogen [3. udgave: afsnit 4.0, 4.4 og
4.5 (bemærk at i 3. udgave er case 2 i Master Theorem en smule mindre
generel end i 4. udgave)], side 15-26 i slides
med
overlays/uden overlays)
|
| 13 |
E |
|
|
|
Opgaver.
|
| 14 |
F |
Torsdag 3/4 |
10-12 |
U1 |
Afslutning af rekursionstræsmetoden og Master Theorem (afsnit 4.0, 4.4
og 4.5 i lærebogen [3. udgave: afsnit 4.0, 4.4 og
4.5 (bemærk at i 3. udgave er case 2 i Master Theorem en smule mindre
generel end i 4. udgave)], side 27-34 i slides
med
overlays/uden overlays)
Optagelse af
online forelæsning 2021 (mere om rekursionsligninger).
En berømt Divide and Conquer algoritme: Strassens algoritme for
matrix-multiplikation (afsnit 4.2 i lærebogen [3. udgave: afsnit 4.2], slides
med
overlays/uden overlays).
Optagelse af online
forelæsning 2021 (Strassens algoritme).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 3.3.
For en historisk gennemgang af udviklingen i køretid for algoritmer
for matrix-multiplikation, se denne
wikipedia
side (ikke pensum). For en slags forgænger (og mulig inspiration) til
Strassens algoritme, se
Karatsubas
rekursive algoritme (1962) til multiplikation af tal (ikke pensum).
Udlevering af projektet, del II (kun for DM507 og
DS814).
|
| 14 |
E |
|
|
|
Opgaver.
|
| 15 |
F |
Tirsdag 8/4 |
08-10 |
U1 |
Dynamisk programmering (afsnit 14.1 i lærebogen [3. udgave: afsnit 15.1], slides
med
overlays/uden
overlays).
Optagelse af online forelæsning
2021 (dynamisk programmering).
Forslag til yderligere videomateriale (ikke pensum):
Dan
Suthers, University of Hawaii.
Mere om dynamisk programmering (afsnit 14.4 og 14.2 i lærebogen [3. udgave: afsnit 15.4 og 15.2], side 1-6 i
slides med
overlays/uden
overlays).
Optagelse af online forelæsning 2021 (mere
om dynamisk programmering),
optagelse af online
forelæsning 2021 (endnu mere om dynamisk programmering).
Forslag til yderligere videomateriale (ikke pensum):
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii.
Bellmans
forklaring om historien bag navnet Dynamisk Programmering (ikke
pensum).
|
| 15 |
F |
Torsdag 10/4 |
10-12 |
U1 |
Afslutning af dynamisk programmering (afsnit 14.4 og 14.2 i lærebogen
[3. udgave: afsnit 15.4 og 15.2], resten
af slides med
overlays/uden
overlays).
Start på grådige algoritmer (afsnit 15.1-2 i lærebogen [3. udgave: afsnit 16.1-2], side 1-9 i slides
med
overlays/uden overlays).
NB: I lærebogen er afsnit 15.1 og første del af 15.2 [3. udgave: afsnit 16.1 og første del af 16.2]
ret langstrakt, og refererer nogle gange til dynamisk programmering
(kapitlet før) - læs disse sider let, og fokuser på slides.
Optagelse af online forelæsning
2021 (grådige algoritmer).
|
| 15 |
E |
|
|
|
Opgaver.
|
| 17 |
F |
Tirsdag 22/4 |
|
Video |
Afslutning af grådige algoritmer: Huffmans algoritme
(videoforelæsning, afsnit 15.3 i
lærebogen, [3. udgave: afsnit 16.3],
slutningen (side 10-21) af slides med
overlays/uden overlays).
En god
tabel
over den klassiske ASCII
fixed-width encoding (ikke pensum).
|
| 17 |
E |
|
|
|
Opgaver.
|
| 18 |
F |
Tirsdag 29/4 |
08-10 |
U55 |
Datastrukturer for disjoint sets (afsnit 19.1-3 i lærebogen [3. udgave: afsnit 21.1-3], slides
med
overlays/uden overlays).
Optagelse af online
forelæsning 2021 (disjoint sets).
Optagelse af online
forelæsning 2021 (mere om disjoint sets).
Udlevering af projektet, del III (kun for DM507
og DS814).
|
| 18 |
F |
Torsdag 1/5 |
10-12 |
U1 |
Start på grafalgoritmer: repræsentation af grafer (afsnit 20.1 i
lærebogen [3. udgave: afsnit 22.1], side
1-14 i slides med
overlays/uden
overlays). Derudover er de første to sider af appendiks B.4 i
lærebogen om basal terminologi for grafer overladt til selvstændig
læsning.
Optagelse af
online forelæsning 2021 (start på grafalgoritmer).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 9.2 og 10.1-2.
Midtvejsevaluering af kurset.
|
| 18 |
E |
|
|
|
Opgaver.
|
| 19 |
F |
Tirsdag 6/5 |
08-10 |
U55 |
Grafgennemløb: BFS, DFS (afsnit 20.2-3 i lærebogen [3. udgave: afsnit 22.2-3], side 15-25 i
slides med
overlays/uden overlays).
Optagelse af
online forelæsning 2021 (grafgennemløb, BSF).
Optagelse af online forelæsning
2021 (DFS).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.3 og 10.5.
Mere om projektet, del III (kun for DM507
og DS814).
|
| 19 |
E |
|
|
|
Opgaver.
|
| 20 |
F |
Tirsdag 13/5 |
08-10 |
U55 |
Afslutning af DFS. DAGs, topologisk sorting (afsnit 20.4 i lærebogen
[3. udgave: afsnit 22.4], resten af slides
med
overlays/uden overlays)
Sammenhængskomponenter (CC) i uorienterede grafer og stærke
sammenhængskomponenter (SCC) i orienterede grafer (side 1166 (øverste
halvdel) og side 576-580 i lærebogen [3. udgave:
side 1170-71 og 615-20],
slides med
overlays/uden overlays).
Optagelse af
online forelæsning 2021 (DFS afslutning, DAGs, CC og SCC).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.6, 10.4 og 10.7.
|
| 20 |
F |
Torsdag 15/5 |
10-12 |
U1 |
Minimum Udspændende Træer: Prim-Jarniks algoritme, Kruskals algoritme.
(kapitel 21 i lærebogen [3. udgave:
kapitel 23], slides med
overlays/uden overlays).
Optagelse af
online forelæsning 2021 (MST introduction).
Optagelse af online
forelæsning 2021 (Prim). Optagelse af
online forelæsning 2021 (Kruskal).
|
| 20 |
E |
|
|
|
Opgaver.
|
| 21 |
F |
Tirsdag 20/5 |
08-10 |
U55 |
Korteste veje, single source: Dijkstras algoritme (afsnit 22.0, 22.3
og 22.5 i lærebogen [3. udgave: afsnit 24.0, 24.3
og 24.5], første del af slides
med
overlays/uden overlays),
korteste veje i DAGs, Bellman-Fords algoritme (afsnit 22.2 og 22.1 i
lærebogen [3. udgave: afsnit 24.2 og
24.1], midterste del af slides
med
overlays/uden overlays).
Optagelse af online
forelæsning 2021 (single source korteste veje: BF, Dijkstra, DAG).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 21 |
E |
|
|
|
Opgaver.
|
| 22 |
F |
Tirsdag 27/5 |
08-10 |
U55 |
Bevis for Bellman-Fords algoritme (afsnit 22.1 i lærebogen [3. udgave: afsnit 24.1], midterste del af
slides med
overlays/uden overlays).
Korteste veje, all-pairs: Floyd-Warshalls algoritme, Johnsons
algoritme (afsnit 23.0 og 23.2-3 i lærebogen [3. udgave: afsnit 25.0 og 25.2-3], sidste del
af slides med
overlays/uden overlays).
Optagelse af online
forelæsning 2021 (all pairs korteste veje: Floyd-Warshall, Johnson).
Relationen mellem Dijkstra og A*-algoritmen. A*-algoritmen er ikke
pensum (og nævnes ikke i lærebogen), men er kendt af nogle deltagere
fra andre kurser, hvorfor dens forhold til Dijkstra nævnes her.
For oprindelsen/betydningen af navnet "A*", se A* Search: What's in
a Name? af James W. Davis og Jeff Hachtel, Communications of
the ACM, Januar 2020, Vol. 63 No. 1, side 36-37 (ikke pensum).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 22 |
E |
|
|
|
Opgaver.
|
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|