DM507/DM578/DS814/SE4-DMAD Algoritmer og datastrukturer
Forår 2024
Rolf Fagerberg
Generel information
Kurset starter torsdag den 1. februar og slutter fredag den
24. 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 |
| 5 |
F |
Torsdag 1/2 |
08-10 |
U1 |
Introduktion til kurset (slides, 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,
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.
|
| 6 |
F |
Tirsdag 6/2 |
10-12 |
U55 |
Om algoritmeanalyse (dele af afsnit 2.2 i lærebogen [3. udgave: dele af afsnit 2.2],
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). Vi vender tilbage til
begrebet "Invariant" lidt senere i kurset - de dele af teksten, 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.
|
| 6 |
F |
Torsdag 8/2 |
08-10 |
U1 |
Mere om sorteringsalgoritmer: Selectionsort, Mergesort (afsnit 2.3 i
lærebogen [3. udgave: afsnit 2.3], side
7-13 i slides). Vi vender tilbage til
begrebet "Divide and Conquer" lidt senere i kurset - de dele af
teksten, som snakker om dette, kan indtil videre læses let.
Asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1],
slides, 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 (selectionsort, merge).
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).
|
| 6 |
E |
|
|
|
Opgaver.
|
| 7 |
F |
Tirsdag 13/2 |
10-12 |
U55 |
Afslutning af asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1],
slides,
tidsTabelBeregninger.py).
Optagelse af online
forelæsning 2021 (samme som i torsdags).
|
| 7 |
E |
|
|
|
Opgaver.
|
| 8 |
F |
Tirsdag 20/2 |
10-12 |
U1 |
Et eksempel på at forskellige algoritmer for samme beregningsproblem
kan have meget forskellige køretider: the maximum sub-array problem
(slides,
wikipedia,
MaxSum1.py, MaxSum1.java,
MaxSum2.py, MaxSum2.java,
MaxSum3.py, MaxSum3.java).
Optagelse af
online forelæsning 2021 (maximum sum subarray).
Divide-and-conquer/rekursive algoritmer (side 34 i lærebogen [3. udgave: side 30],
slides).
Optagelse af
online forelæsning 2021 (recursive algorithms).
Mergesort formuleret rekursivt (afsnit 2.3 i lærebogen [3. udgave: afsnit 2.3], side 14-15 i
slides).
|
| 8 |
F |
Torsdag 22/2 |
08-10 |
U1 |
Flere sorteringsalgoritmer: Quicksort (afsnit 7.1-3 i lærebogen [3. udgave: afsnit 7.1-3], næste dele af
slides).
Optagelse af online forelæsning 2021
(quicksort).
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).
Optagelse af
online forelæsning 2021 (heapsort).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 5.1-4.
|
| 8 |
E |
|
|
|
Opgaver.
|
| 9 |
F |
Tirsdag 27/2 |
10-12 |
U55 |
Afslutning af Heapsort.
Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1 i
lærebogen [3. udgave: afsnit 8.1], første
del af slides, 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)).
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). 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-6 i disse
slides.
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.
Start på prioritetskøer (side 175-176 i lærebogen [3. udgave: side 164],
slides side 8-9).
|
| 9 |
E |
|
|
|
Opgaver.
|
| 10 |
F |
Tirsdag 5/3 |
10-12 |
U55 |
Afslutning af prioritetskøer (afsnit 6.5 i lærebogen [3. udgave: afsnit 6.5],
slides).
[NB: 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].]
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].
Start på 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 i lærebogen [3. udgave:
afsnit 12.1], første del af
slides).
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.
Udlevering af projektet, del I (kun for
DM507 og DS814).
|
| 10 |
F |
Torsdag 7/3 |
08-10 |
U1 |
Mere om projekt I: Gennemgang af krav til afleveringen. 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).
Mere om binære søgetræer (afsnit 12.2-3 i lærebogen [3. udgave: afsnit 12.2-3], næste del af
slides).
Optagelse af online forelæsning
2021 (binære søgetræer).
|
| 10 |
E |
|
|
|
Opgaver.
|
| 10 |
F |
Tirsdag 12/3 |
10-12 |
U55 |
Rød-sorte træer (afsnit 13.1-4 i lærebogen [3. udgave: afsnit 13.1-4], næste del af
slides).
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 og siderne 297 (midt) til 300 [3. udgave: afsnit 11.1-4, dog ikke: siderne 258-260,
266-268 og 274-276], slutningen af
slides).
Optagelse af online forelæsning 2021
(rød-sorte træer). Optagelse af online
forelæsning 2021 (sletning i rød-sorte træer, hashing).
Optagelse af online
forelæsning 2021 (repetition af hashing).
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.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit
13.4-6. Tim
Roughgarden, Stanford, afsnit 14.1-3 og 15.1.
|
| 11 |
E |
|
|
|
Opgaver.
|
| 12 |
F |
Tirsdag 19/3 |
10-12 |
U55 |
Afslutning af hashing (læsning: som sidst).
Dekoration af binære søgetræer (afsnit 17.1-2 i lærebogen [3. udgave: afsnit 14.1-2],
slides).
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.
|
| 12 |
F |
Torsdag 21/3 |
08-10 |
U1 |
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).
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)],
slides side 1-20).
Optagelse af
online forelæsning 2021 (invarianter).
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].
|
| 12 |
E |
|
|
|
Opgaver.
|
| 14 |
F |
Tirsdag 2/4 |
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)],
slides side 21-34)
En berømt Divide and Conquer algoritme: Strassens algoritme for
matrix-multiplikation (afsnit 4.2 i lærebogen
[3. udgave: afsnit 4.2],
slides).
Udlevering af projektet, del II (kun for DM507 og
DS814).
Optagelse af online
forelæsning 2021 (mere om rekursionsligninger, Strassens algoritme).
Optagelse af online forelæsning 2021
(gennemgang af projekt del II). Bemærk at implementationen af
træer via klasser nu er den beskrevne metode i projektteksten (fremfor
en mulighed nævnt i en fodnote i 2021). Metoden fra 2021 med
implementation via lister må sådan set gerne bruges, men efter mine
informationer har alle nu lært om klasser i deres Python
programmeringskursus.
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).
|
| 14 |
E |
|
|
|
Opgaver.
|
| 15 |
F |
Tirsdag 9/4 |
10-12 |
U55 |
Dynamisk programmering (afsnit 14.1 i lærebogen [3. udgave: afsnit 15.1],
slides).
Bellmans
forklaring om historien bag navnet Dynamisk Programmering (ikke
pensum).
Optagelse af online forelæsning
2021 (dynamisk programmering).
Forslag til yderligere videomateriale (ikke pensum):
Dan
Suthers, University of Hawaii.
|
| 15 |
F |
Torsdag 11/4 |
08-10 |
U1 |
Mere om dynamisk programmering (afsnit 14.4 og 14.2 i lærebogen [3. udgave: afsnit 15.4 og 15.2],
slides).
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.
|
| 15 |
E |
|
|
|
Opgaver.
|
| 16 |
F |
Tirsdag 16/4 |
10-12 |
U55 |
Grådige algoritmer (afsnit 15.1-3 i lærebogen [3. udgave: afsnit 16.1-3],
slides).
NB: afsnit 15.1 og første del af 15.2
[3. udgave: afsnit 16.1 og første del af 16.2] er 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).
|
| 16 |
E |
|
|
|
Opgaver.
|
| 17 |
F |
Tirsdag 23/4 |
10-12 |
U55 |
Multiple-choice test (25 minutter) i klassen (kan findes i ITS under
Ressourcer som MC test 1).
Bevis for korrekthed af Huffmans algoritme (afsnit 15.3 i lærebogen,
[3. udgave: afsnit 16.3], slutningen af
slides)
Datastrukturer for disjoint sets (afsnit 19.1-3 i lærebogen [3. udgave: afsnit 21.1-3],
slides).
Optagelse af online
forelæsning 2021 (disjoint sets),
|
| 17 |
F |
Torsdag 25/4 |
08-10 |
U1 |
Afslutningen af datastrukturer for disjoint sets (afsnit 19.1-3 i
lærebogen [3. udgave: afsnit 21.1-3],
slides).
Start på grafalgoritmer: repræsentation af grafer (afsnit 20.1 i
lærebogen [3. udgave: afsnit 22.1], side
1-6 i slides). 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 (mere om disjoint sets).
Optagelse af
online forelæsning 2021 (start på grafalgoritmer).
Udlevering af projektet, del III (kun for DM507
og DS814).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 9.2 og 10.1-2.
|
| 17 |
E |
|
|
|
Opgaver.
|
| 18 |
F |
Tirsdag 30/4 |
10-12 |
U55 |
Grafgennemløb: BFS, DFS (afsnit 20.2-3 i lærebogen [3. udgave: afsnit 22.2-3], side 7-27 i
slides).
Mere om projektet, del III (kun for DM507
og DS814).
Optagelse af
online forelæsning 2021 (grafgennemløb, BSF).
Optagelse af
online forelæsning 2021 (DFS).
Optagelse af online
forelæsning 2021 (gennemgang af projekt del III).
Optagelse af online
forelæsning 2021 (mere gennemgang af projekt del III).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.3 og 10.5.
|
| 18 |
E |
|
|
|
Opgaver.
|
| 19 |
F |
Tirsdag 7/5 |
10-12 |
U55 |
Multiple-choice test (30 minutter) i klassen (kan findes i ITS under
Ressourcer som MC test 2).
DAGs, topologisk sorting (afsnit 20.4 i lærebogen [3. udgave: afsnit 22.4], resten af
slides)
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).
Optagelse af
online forelæsning 2021 (DAGs, CC og
SCC). Optagelse af online forelæsning 2021
(bevis for SCC algoritmen).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.6, 10.4 og 10.7.
|
| 19 |
F |
Onsdag 8/5 |
16-18 |
U55 |
Minimum Udspændende Træer, Prim-Jarniks algoritme.
(kapitel 21 i lærebogen [3. udgave:
kapitel 23], slides).
Optagelse af online
forelæsning 2021 (Prim).
|
| 19 |
E |
|
|
|
Opgaver.
|
| 20 |
F |
Tirsdag 14/5 |
10-12 |
U55 |
Afslutning af Minimum Udspændende Træer: Kruskals
algoritme. (kapitel 21 i lærebogen [3. udgave:
kapitel 23], slides).
Optagelse af online forelæsning 2021
(Kruskal).
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). Shortest paths på 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).
Optagelse af online forelæsning 2021
(korteste veje).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 20 |
E |
|
|
|
Opgaver.
|
| 21 |
F |
Tirsdag 21/5 |
10-12 |
U55 |
Afslutning af korteste veje, single source: beviser for korrekthed af
algoritmerne fra sidst: Dijkstras, DAGs, Bellman-Ford (afsnit 22.0,
22.3, 22.5, 22.2 og 22.1 i lærebogen [3. udgave:
afsnit 24.0, 24.3, 24.5, 24.2 og 24.1], første og midterste del
af slides).
Relation 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 relation til Dijkstra nævnes her.
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). Johnsons algoritme er ikke
pensum.
Optagelse af online forelæsning 2021
(korteste veje).
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.
|
| 21 |
E |
|
|
|
Opgaver.
|
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|