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]).
Eksempel på en (meget detaljeret) algoritmeanalyse:
Ombytningspuslespil (slides med
overlays/uden overlays,
noter). Et
ombytningspuslespil
fra nettet.
|
| 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.
|
| 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.
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.
|
| 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).
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.
|
| 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).
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 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).
|
| 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.
|
| 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).
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).
|
| 11 |
F |
Torsdag 13/3 |
10-12 |
U1 |
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).
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.
Udlevering af projektet, del I (kun for DM507 og
DS814).
|
| 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).
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).
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).
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).
|
| 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)
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).
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).
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).
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.
|
| 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).
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-6 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.
Midtvejsevaluering af kurset.
Mere om projektet, del III (kun for DM507
og DS814).
|
| 18 |
E |
|
|
|
Opgaver.
|
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|