DM507/DM578/DS814/SE4-DMAD Algoritmer og datastrukturer
Forår 2023
Rolf Fagerberg
Generel information
Kurset starter tirsdag den 7. februar og slutter fredag den
26. maj.
Timer
Når 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 7/2 |
10-12 |
U55 |
Introduktion til kurset (slides, kapitel 1 i
lærebogen [3. udgave: kapitel 1]).
Eksempel på en (meget detaljeret) algoritmeanalyse: Ombytningspuslespil
(slides, noter). Et
ombytningspuslespil
fra nettet.
Optagelse af online forelæsning 2021 (NB: detaljerne om kursets struktur er en smule ændret, se slides ovenfor i stedet).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 1.1, 1.4 og 1.8.
|
| 6 |
F |
Torsdag 9/2 |
08-10 |
U55 |
Start på sorteringsalgoritmer: Insertionsort, Selectionsort, Mergesort
(side 157-160 i lærebogen [3. udgave: side
147-150], kapitel 2 i lærebogen [3. udgave: kapitel 2], side 1-12 i
slides). Vi vender tilbage til begreberne
"Invarianter" og "Divide and Conquer" lidt senere i kurset - de dele
af teksten, som beskriver disse begreber, kan indtil videre læses let.
Optagelse af online forelæsning 2021.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 1.5-7.
|
| 6 |
E |
|
|
|
Opgaver.
|
| 7 |
F |
Tirsdag 14/2 |
10-12 |
U55 |
Afslutning af Mergesort (side 13 i slides).
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.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 2.1-4 (evt. også 2.5 for ekstra
eksempler).
|
| 7 |
E |
|
|
|
Opgaver for DM507/DM578/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 8 |
F |
Tirsdag 21/2 |
10-12 |
U45 |
Repetition af asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1],
slides).
Et eksempel på at forskellige algoritmer for samme beregningsproblem
kan have meget forskellige køretider: the maximum sub-array problem
(wikipedia,
MaxSum1.java, MaxSum2.java,
MaxSum3.java).
Optagelse af online forelæsning 2021.
|
| 8 |
F |
Torsdag 23/2 |
08-10 |
U55 |
Divide-and-conquer/rekursive algoritmer (side 34 i lærebogen [3. udgave: side 30],
slides).
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 (rekursive algoritmer). Optagelse af online forelæsning 2021 (quicksort).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 5.1-4.
|
| 8 |
E |
|
|
|
Opgaver.
|
| 9 |
F |
Tirsdag 28/2 |
10-12 |
U55 |
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).
Prioritetskøer (afsnit 6.5 i lærebogen [3. udgave: afsnit 6.5],
slides).
Optagelse af online forelæsning
2021 (heapsort). 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].
|
| 9 |
E |
|
|
|
Opgaver for DM507/DM578/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 10 |
F |
Tirsdag 7/3 |
10-12 |
U55 |
Udlevering af projektet, del I (kun for
DM507 og DS814).
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 (udlevering af projekt del I).
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 |
F |
Torsdag 9/3 |
14-16 |
U55 |
Lidt mere om projekt I: redirection af standard input og output
(relevant viden for alle).
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).
[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 (redirection).
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.
|
| 10 |
E |
|
|
|
Opgaver.
|
| 11 |
F |
Tirsdag 14/3 |
10-12 |
U55 |
Rød-sorte træer (afsnit 13.1-4 i lærebogen [3. udgave: afsnit 13.1-4], midten af
slides).
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.
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).
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 for DM507/DM578/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 12 |
F |
Tirsdag 21/3 |
10-12 |
U55 |
Dekoration af binære søgetræer (afsnit 17.1-2 i lærebogen [3. udgave: afsnit 14.1-2],
slides).
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).
Optagelse af online
forelæsning 2021 (dekoration af binære søgetræer).
Optagelse af
online forelæsning 2021 (invarianter).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 13.3 fra 22:00.
|
| 12 |
F |
Torsdag 23/3 |
14-16 |
U1 |
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-23).
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.
|
| 13 |
F |
Tirsdag 28/3 |
10-12 |
U55 |
Udlevering af projektet, del II (kun for DM507 og
DS814).
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 24-33)
En berømt Divide and Conquer algoritme: Strassens algoritme for
matrix-multiplikation (afsnit 4.2 i lærebogen
[3. udgave: afsnit 4.2],
slides).
Optagelse af online gennemgang af
projektbeskrivelse 2021.
Optagelse af online
forelæsning 2021 (mere om rekursionsligninger, 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).
|
| 13 |
E |
|
|
|
Opgaver for DM507/DM578/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 15 |
F |
Tirsdag 11/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 13/4 |
08-10 |
U55 |
Mere om dynamisk programmering (afsnit 14.4 og 14.2 i lærebogen [3. udgave: afsnit 15.4 og 15.2],
slides).
Start på grådige algoritmer (afsnit 15.1 i lærebogen [3. udgave: afsnit 16.1],
slides side 1-7).
NB: afsnit 15.1 [3. udgave: afsnit 16.1]
er ret langstrakt, og refererer nogle gange til dynamisk programmering
(kapitlet før) - læs dette afsnit let, og fokuser på slides.
Optagelse af online forelæsning 2021 (mere
om dynamisk programmering),
optagelse af
online forelæsning 2021 (endnu mere om dynamisk programmering).
optagelse af online
forelæsning 2021 (start på grådige algoritmer).
Forslag til yderligere videomateriale (ikke pensum):
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii.
|
| 15 |
E |
|
|
|
Opgaver.
|
| 16 |
F |
Tirsdag 18/4 |
10-12 |
U55 |
Mere om grådige algoritmer (afsnit 15.2-3 i lærebogen [3. udgave: afsnit 16.2-3], resten af
slides).
NB: starten af afsnit 15.2 [3. udgave:
afsnit 16.2] er ret langstrakt, og refererer nogle gange til
dynamisk programmering (kapitlet før) - læs dette afsnit let, og
fokuser på slides.
Optagelse af online
forelæsning 2021 (start på grådige algoritmer).
Midtvejsevaluering af kurset.
|
| 16 |
E |
|
|
|
Opgaver for DM507/DM578/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 17 |
F |
Tirsdag 25/4 |
10-12 |
U55 |
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),
optagelse af online
forelæsning 2021 (endnu mere om disjoint sets).
Udlevering af projektet, del III (kun for DM507
og DS814).
|
| 17 |
F |
Torsdag 27/4 |
08-10 |
U55 |
Start på grafalgoritmer: repræsentation af grafer, grafgennemløb
(afsnit 20.1 i lærebogen [3. udgave:
afsnit 22.1], side 1-11 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 (start på grafalgoritmer).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 9.2 og 10.1-2.
|
| 17 |
E |
|
|
|
Opgaver.
|
| 18 |
F |
Tirsdag 2/5 |
10-12 |
U55 |
Denne forelæsning varetages af Lene Monrad Favrholdt.
Mere om grafgennemløb: BFS, DFS (afsnit 20.2-3 i lærebogen [3. udgave: afsnit 22.2-3], side 12-29 i
slides).
Annoterede slides
fra Lenes forelæsning.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.3 og 10.5.
|
| 18 |
E |
|
|
|
Opgaver, opgaver
for SE4-DMAD (samme opgaver (minus nogle projektrelaterede opgaver)
i en lidt anden gruppering pga. skemaet).
|
| 19 |
F |
Tirsdag 9/5 |
10-12 |
U55 |
DAGs, topologisk sorting (afsnit 20.4 i lærebogen [3. udgave: afsnit 22.4], resten af
slides)
Sammenhængskomponenter i uorienterede grafer og stærke
sammenhængskomponenter i orienterede grafer (side 1166 (øverste
halvdel) og side 576-580 i lærebogen [3. udgave:
side 1170-71 og 615-20],
slides).
Start på Minimum Udspændende Træer (kapitel 21 i lærebogen [3. udgave: kapitel 23],
slides).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.6, 10.4 og 10.7.
|
| 19 |
F |
Torsdag 11/5 |
08-10 |
U55 |
Mere om Minimum udspændende træer, Prim-Jarniks algoritme, Kruskals
algoritme (kapitel 23 i lærebogen, slides).
|
| 19 |
E |
|
|
|
Opgaver.
|
| 20 |
F |
Tirsdag 16/5 |
10-12 |
U55 |
Korteste veje, single source: Dijkstras algoritme, relation mellem
Dijkstra og A*-algoritmen (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). 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.
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.
|
| 20 |
E |
|
|
|
Opgaver, opgaver
for SE4-DMAD (samme opgaver i en lidt anden gruppering pga. skemaet).
|
| 21 |
F |
Tirsdag 23/5 |
10-12 |
U55 |
Denne forelæsning varetages af Lene Monrad Favrholdt.
Mere om korteste veje, single source: 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).
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
Annoterede slides
fra Lenes forelæsning.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 21 |
E |
|
|
|
Opgaver.
|
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|