DM507/DS814/SE4-DMAD Algoritmer og datastrukturer
Forår 2022
Rolf Fagerberg
Generel information
Kurset starter tirsdag den 1. februar og slutter fredag den
20. maj.
Timer
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 5 |
F |
Tirsdag 1/2 |
10-12 |
U45 |
Introduktion til kurset (slides, kapitel 1 i
lærebogen).
Eksempel på en (meget detaljeret) algoritmeanalyse: Ombytningspuslespil
(slides, noter). Et
ombytningspuslespil
fra nettet.
Optagelse af online forelæsning 2021.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 1.1, 1.4 og 1.8.
|
| 5 |
F |
Torsdag 3/2 |
14-16 |
U55 |
Start på sorteringsalgoritmer: Insertionsort, Selectionsort, Mergesort
(side 147-150 i lærebogen, afsnit 2.1-3 i lærebogen, side 1-9 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.
|
| 5 |
E |
|
|
|
Opgaver.
|
| 6 |
F |
Tirsdag 8/2 |
10-12 |
U45 |
Afslutning af Mergesort (side 147-150 i lærebogen, afsnit 2.1-3 i
lærebogen, side 10-12 i slides).
Asymptotisk analyse (afsnit 3.1 i lærebogen,
slides, Java-programmerne fra
slides: Linear.java,
Quadratic.java, Cubic.java).
Det kan være en fordel at orientere sig i afsnit 3.2 i lærebogen 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).
|
| 6 |
E |
|
|
|
Opgaver for DM507/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 7 |
F |
Tirsdag 15/2 |
10-12 |
U45 |
Repetition af asymptotisk analyse (afsnit 3.1 i lærebogen,
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.
|
| 7 |
F |
Torsdag 17/2 |
14-16 |
U55 |
Divide-and-conquer/rekursive algoritmer (side 30 i lærebogen,
slides).
Flere sorteringsalgoritmer: Quicksort (afsnit 7.1-3 i lærebogen, 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.
|
| 7 |
E |
|
|
|
Opgaver.
|
| 8 |
F |
Tirsdag 22/2 |
10-12 |
U45 |
Flere sorteringsalgoritmer: Heapsort (afsnit 6.1-4 i lærebogen, B.5.3
i lærebogen, sidste del af slides).
Prioritetskøer (afsnit 6.5 i lærebogen, 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].
|
| 8 |
E |
|
|
|
Opgaver for DM507/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 9 |
F |
Tirsdag 1/3 |
10-12 |
U45 |
Denne forelæsning varetages af Lene Monrad Favrholdt.
Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1 i
lærebogen, 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, 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 1-5 i disse
slides.
Annoterede slides fra Lenes forelæsning.
Optagelse af online
forelæsning 2021.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 8.6.
|
| 9 |
F |
Torsdag 3/3 |
14-16 |
U55 |
Denne forelæsning varetages af Lene Monrad Favrholdt.
Dictionaries og deres implementation via binære søgetræer
(side 229-230 i lærebogen, afsnit 10.4 i lærebogen, afsnit 12.1-3 i
lærebogen, første del af slides).
Start på rød-sorte træer (afsnit 13.1-2 i lærebogen, starten af midten af
slides).
Annoterede slides fra Lenes
forelæsning. Optagelse af online forelæsning 2021
(binære søgetræer). Optagelse af
online forelæsning 2021 (start af rød-sorte træer).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 13.1-2 samt 13.3 indtil 22:00.
|
| 9 |
E |
|
|
|
Opgaver.
|
| 10 |
F |
Tirsdag 8/3 |
10-12 |
U45 |
Mere om rød-sorte træer, indsættelse i rød-sorte træer (afsnit 13.3-4
i lærebogen, 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.
Udlevering og diskussion af projektet, del I (kun for DM507 og DS814).
Java version:
projektbeskrivelse, del I,
PQ.java, Element.java,
PQSort.java, Testfiler.zip.
Python version: projektbeskrivelse,
del I, PQSort.py,
Testfiler.zip.
Optagelse af online forelæsning 2021
(mere om rød-sorte træer, indsættelse i rød-sorte træer).
Optagelse af online forelæsning
2021 (projekt del
I). Optagelse
af online forelæsning 2021 (mere projekt del I).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 13.4-6.
|
| 10 |
E |
|
|
|
Opgaver for DM507/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 11 |
F |
Tirsdag 15/3 |
10-12 |
U45 |
Sletning i rød-sorte træer (afsnit 13.4 i lærebogen, side 14-15 og
27-31 i slides)).
Implementation af dictionaries via hashing (afsnit 11.1-4 i lærebogen
[dog ikke siderne 265-268 og 274-276], slutningen af
slides).
Optagelse af online forelæsning 2021
(sletning i rød-sorte træer, hashing).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 14.1-3 og 15.1.
|
| 11 |
F |
Torsdag 17/3 |
14-16 |
U55 |
Repetition af hashing. Dekoration af binære søgetræer (afsnit 14.1-2 i
lærebogen, slides).
Optagelse af online
forelæsning 2021 (repetition af hashing).
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.
|
| 11 |
E |
|
|
|
Opgaver.
|
| 12 |
F |
Tirsdag 22/3 |
10-12 |
U45 |
Invarianter (siderne 18-20, 32-33, 157, 171-173 og 318-322 i
lærebogen, 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, slides side 1-22).
Optagelse af online
forelæsning 2021.
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 en smule mindre generel end
lærebogens, og at rækkefølgen af cases er forskellig].
|
| 12 |
E |
|
|
|
Opgaver for DM507/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 13 |
F |
Tirsdag 29/3 |
10-12 |
U45 |
Mere om rekursionstræsmetoden og Master Theorem (afsnit 4.0, 4.4 og
4.5 i lærebogen, slides side
20-30).
En berømt Divide and Conquer algoritme: Strassens algoritme for
matrix-multiplikation (afsnit 4.2 i lærebogen,
slides).
Optagelse af online forelæsning
2021.
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 |
F |
Torsdag 31/3 |
14-16 |
U55 |
Dynamisk programmering (afsnit 15.1-2 i lærebogen,
slides).
Bellmans
forklaring om historien bag navnet Dynamisk Programmering (ikke
pensum).
Udlevering af projektet, del II (kun for DM507 og DS814). Java
version: projektbeskrivelse, del II,
Dict.java. Python version:
projektbeskrivelse, del II,
Optagelse af online forelæsning 2021.
Optagelse af online
gennemgang af projektbeskrivelse 2021, Java version.
Optagelse af online gennemgang af
projektbeskrivelse 2021, Python version.
Forslag til yderligere videomateriale (ikke pensum):
Dan
Suthers, University of Hawaii.
|
| 13 |
E |
|
|
|
Opgaver.
|
| 14 |
F |
Tirsdag 5/4 |
10-12 |
U45 |
Mere om dynamisk programmering (afsnit 15.4 i lærebogen,
slides).
Optagelse af online forelæsning 2021,
mere optagelse af online
forelæsning 2021.
Forslag til yderligere videomateriale (ikke pensum):
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii.
|
| 14 |
E |
|
|
|
Opgaver for DM507/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 16 |
F |
Tirsdag 19/4 |
10-12 |
U45 |
Grådige algoritmer (afsnit 16.1-3 i lærebogen,
slides).
Optagelse af online forelæsning 2021.
NB: både
afsnit 16.1 og første del af 16.2 er ret langstrakt, og refererer
nogle gange til dynamisk programmering (kapitel 15) - læs disse afsnit
let, og fokuser på slides.
Midtvejsevaluering af kurset.
|
| 16 |
F |
Torsdag 21/4 |
14-16 |
U55 |
Bevis for korrekthed af Huffmans algoritme (afsnit 16.3 i lærebogen,
sidste del af slides).
Datastrukturer for disjoint sets (afsnit 21.1-3 i lærebogen,
slides).
Udlevering af Projekt, del III (kun for DM507 og DS814).
Java version: projektbeskrivelse.
tegneserieudgave af del III.
Tilhørende filer: to biblioteksfunktioner
BitInputStream.java,
BitOutputStream.java, samt et eksempel på
brug af dem Test.java (læs kommentarer i
programmet). En samling
testfiler samt liste
med angivelse af korrekt størrelse efter komprimering.
Python version: projektbeskrivelse.
tegneserieudgave af del III.
Tilhørende filer: bibliotek bitIO.py samt et eksempel
på brug af det test.py (læs kommentarer i programmet),
klassen Element.py samt et eksempel på brug af det
PQSortElements.py (læs kommentarer i
programmet). En samling
testfiler samt liste med
angivelse af korrekt størrelse efter komprimering.
|
| 16 |
E |
|
|
|
Opgaver.
|
| 17 |
F |
Tirsdag 26/4 |
10-12 |
U45 |
Start på grafalgoritmer: repræsentation af grafer, BFS grafgennemløb
(afsnit 22.1-2 i lærebogen, første halvdel af
slides). Derudover er de første tre
sider af appendiks B.4 i lærebogen (side 1168-70) om basal terminologi
for grafer overladt til selvstændig læsning.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 9.2 og 10.1-2.
|
| 17 |
E |
|
|
|
Opgaver for DM507/DS814,
opgaver for SE4-DMAD (samme opgaver i en
lidt anden gruppering pga. skemaet).
|
| 18 |
F |
Tirsdag 3/5 |
10-12 |
U45 |
Bevis for BFS egenskaber, DFS grafgennemløb (afsnit 22.2-3 i
lærebogen, slides).
DAGs, topologisk sorting (afsnit 22.4 i lærebogen,
slides).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.3 og 10.5.
|
| 18 |
F |
Torsdag 5/5 |
14-16 |
U55 |
Sammenhængskomponenter i uorienterede grafer og stærke
sammenhængskomponenter i orienterede grafer (side 1170-71 og 615-17 i
lærebogen, slides).
Start på Minimum udspændende træer (kapitel 23 i lærebogen,
slides).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.6, 10.4 og 10.7.
|
| 18 |
E |
|
|
|
Opgaver.
|
| 19 |
F |
Tirsdag 10/5 |
10-12 |
U45 |
Bevis for korrekthed af algoritmen for strongly connected components
(side 617-20 i lærebogen,
slides).
Mere om Minimum udspændende træer, Prim-Jarniks algoritme, Kruskals
algoritme (kapitel 23 i lærebogen, slides).
|
| 19 |
E |
|
|
|
Opgaver.
|
| 20 |
F |
Tirsdag 17/5 |
10-12 |
U45 |
Korteste veje, single source: Bellman-Fords algoritme, Dijkstras
algoritme, shortest paths på DAGs (afsnit 24.0 til 24.3 i lærebogen,
første del af slides). [Flg. er på slides, men er ikke pensum i år: Korteste veje,
all-pairs: Floyd-Warshalls algoritme, Johnsons algoritme (afsnit 25.0
og 25.2-3 i lærebogen, sidste del af
slides.]
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 20 |
E |
|
|
|
Opgaver.
|
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|