DM507/DS814/T510040101 Algoritmer og datastrukturer
Forår 2021
Rolf Fagerberg
Generel information
Kurset starter mandag den 1. februar og slutter mandag den
25. maj.
Timer
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 5 |
F |
Tirsdag 2/2 |
08-10 |
Zoom mødelink
|
Introduktion til kurset (slides, kapitel 1 i
lærebogen).
Eksempel på algoritmeanalyse: Ombytningspuslespil
(slides, noter). Et
ombytningspuslespil
fra nettet.
Optagelse af forelæsning. Forslag til yderligere
videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 1.1, 1.4 og 1.8.
|
| 5 |
F |
Torsdag 4/2 |
10-12 |
Zoom mødelink |
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 forelæsning. Forslag til
yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 1.5-7.
|
| 5 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 6 |
F |
Tirsdag 9/2 |
08-10 |
Zoom mødelink |
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 forelæsning.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 2.1-4 (evt. også 2.5 for ekstra
eksempler).
|
| 6 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 7 |
F |
Tirsdag 16/2 |
08-10 |
Zoom mødelink |
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).
Divide-and-conquer/rekursive algoritmer (side 30 i lærebogen,
slides).
Optagelse af forelæsning.
|
| 7 |
F |
Torsdag 18/2 |
10-12 |
Zoom mødelink |
Flere sorteringsalgoritmer: Quicksort (afsnit 7.1-3 i lærebogen, næste
dele af
slides).
Optagelse af forelæsning. Forslag til
yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 5.1-4.
|
| 7 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 8 |
F |
Tirsdag 23/2 |
08-10 |
Zoom mødelink |
Flere sorteringsalgoritmer: Heapsort (afsnit 6.1-4 i lærebogen, B.5.3
i lærebogen, sidste del af slides).
Optagelse af forelæsning. Forslag til yderligere
videomateriale (ikke pensum):
Mifta Sintaha.
|
| 8 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 9 |
F |
Tirsdag 2/3 |
08-10 |
Zoom mødelink |
Prioritetskøer (afsnit 6.5 i lærebogen,
slides). Forslag til yderligere videomateriale
(ikke pensum):
Tim
Roughgarden, Stanford, afsnit 12.1-3 [bemærk at de enkelte
heap-operationer ikke nødvendigvis hedder det samme som i bogen].
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 forelæsning.
|
| 9 |
F |
Torsdag 4/3 |
10-12 |
Zoom mødelink |
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)).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 8.6.
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 første halvdel af
disse slides.
Optagelse af forelæsning.
|
| 9 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 10 |
F |
Tirsdag 9/3 |
08-10 |
Zoom mødelink |
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).
Optagelse af forelæsning. Forslag til yderligere
videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 13.1-2 samt 13.3 indtil 22:00.
Rød-sorte træer (kapitel 13 i lærebogen, midten af
slides, screencast).
Sletninger gennemgås næste gang. Forslag til yderligere videomateriale
(ikke pensum):
Tim
Roughgarden, Stanford, afsnit 13.4-6.
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.
|
| 10 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 11 |
F |
Tirsdag 16/3 |
08-10 |
Zoom mødelink |
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). Forslag til yderligere
videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 14.1-3 og 15.1.
Optagelse af forelæsning.
|
| 11 |
F |
Torsdag 18/3 |
10-12 |
Zoom mødelink |
Dekoration af binære søgetræer (afsnit 14.1-2 i lærebogen,
slides). Forslag til yderligere
videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 13.3 fra 22:00.
Optagelse af forelæsning.
|
| 11 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 12 |
F |
Tirsdag 23/3 |
08-10 |
Zoom mødelink |
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
(screencast, afsnit 4.0, 4.4 og 4.5 i
lærebogen, slides side
1-20). 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].
Optagelse af forelæsning.
Udlevering af projektet, del II (kun for DM507 og DS814). Java
version: projektbeskrivelse, del II,
Dict.java, optagelse af
gennemgang af projektbeskrivelse. Python version:
projektbeskrivelse, del II,
optagelse af gennemgang af projektbeskrivelse.
|
| 12 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 14 |
F |
Tirsdag 6/4 |
08-10 |
Zoom mødelink |
Mere om rekursionstræsmetoden og Master Theorem (afsnit 4.0, 4.4 og
4.5 i lærebogen, slides side
21-30).
En berømt Divide and Conquer algoritme: Strassens algoritme for
matrix-multiplikation (afsnit 4.2 i lærebogen,
slides). Forslag til yderligere
videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 3.3.
Optagelse af forelæsning.
For en historisk gennemgang af udviklingen i køretid for algoritmer
for matrix-multiplikation, se denne
wikipedia
side (ikke pensum).
|
| 14 |
F |
Torsdag 8/4 |
10-12 |
Zoom mødelink |
Midtvejsevaluering af kurset.
Dynamisk programmering (afsnit 15.1-2 i lærebogen,
slides,
slide med tegninger fra
forelæsning).
Optagelse af forelæsning.
Forslag til yderligere videomateriale (ikke pensum):
Dan
Suthers, University of Hawaii.
Bellmans
forklaring om historien bag navnet Dynamisk Programmering (ikke
pensum).
|
| 14 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 15 |
F |
Tirsdag 13/4 |
08-10 |
Zoom mødelink |
Mere om dynamisk programmering (afsnit 15.4 i lærebogen,
slides,
slide med tegninger fra
forelæsning). Optagelse af forelæsning.
Forslag til yderligere videomateriale (ikke pensum):
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii.
|
| 15 |
E |
|
|
Zoom mødelink |
Opgaver
Tilhørende filer (Java): to biblioteksfunktioner
BitInputStream.java,
BitOutputStream.java, samt et eksempel på
brug af dem Test.java (læs kommentarer i
programmet).
Tilhørende filer (Python): biblioteket bitIO.py, samt
et eksempel på brug af det test.py (læs kommentarer i
programmet).
|
| 16 |
F |
Tirsdag 20/4 |
08-10 |
Zoom mødelink |
Grådige algoritmer (afsnit 16.1-3 i lærebogen,
slides,
slide med tegninger fra
forelæsning). Optagelse af forelæsning. 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.
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 |
F |
Torsdag 22/4 |
10-12 |
Zoom mødelink |
Bevis for korrekthed af Huffmans algoritme (afsnit 16.3 i lærebogen,
sidste del af slides,
slide med tegninger fra
forelæsning).
Datastrukturer for disjoint sets (afsnit 21.1-3 i lærebogen,
slides,
slide med tegninger fra
forelæsning).
Gennemgang af projektet, del III
(tegneserieudgave af del III).
Optagelse af forelæsning.
|
| 16 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 17 |
F |
Tirsdag 27/4 |
08-10 |
Zoom mødelink |
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.
Optagelse af forelæsning.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 9.2 og 10.1-2.
|
| 17 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 18 |
F |
Tirsdag 4/5 |
08-10 |
Zoom mødelink |
Bevis for BFS egenskaber, DFS grafgennemløb (afsnit 22.2-3 i
lærebogen, slides).
Optagelse af forelæsning.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.3 og 10.5.
|
| 18 |
F |
Tirsdag 6/5 |
10-12 |
Zoom mødelink |
DAGs, topologisk sorting (afsnit 22.4 i lærebogen,
slides). Sammenhængskomponenter i
uorienterede grafer og stærke sammenhængskomponenter i orienterede
grafer (side 1170-71 og 615-17 i lærebogen,
slides,
slide med tegninger fra
forelæsning). Beviset for korrekthed af SCC algoritmen er ikke
pensum.
Start på Minimum udspændende træer (kapitel 23 i lærebogen,
slides).
Optagelse af forelæsning.
Video med bevis for korrekthed af SCC algoritmen (ikke
pensum).
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 10.6, 10.4 og 10.7.
|
| 18 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 19 |
F |
Tirsdag 11/5 |
08-10 |
Zoom mødelink |
Mere om Minimum udspændende træer, Prim-Jarniks algoritme, Kruskals
algoritme (kapitel 23 i lærebogen, slides).
Optagelse af forelæsning,
video-forelæsning om Kruskals algoritme.
|
| 19 |
E |
|
|
Zoom mødelink |
Opgaver
|
| 20 |
F |
Tirsdag 18/5 |
08-10 |
Zoom mødelink |
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). Korteste veje,
all-pairs: Floyd-Warshalls algoritme, Johnsons algoritme (afsnit 25.0
og 25.2-3 i lærebogen, sidste del af
slides.
Optagelse af forelæsning.
Forslag til yderligere videomateriale (ikke pensum):
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 20 |
E |
|
|
Zoom mødelink |
Opgaver
|
Som led i studienævnets evalueringsrutine er en kursusevaluering
afholdt efter eksamen. De
sammentalte
svar (uden kommentarer af hensyn til de studerendes anonymitet,
jvf. studienævnets regler) og underviserens
handlingsplan er nu
tilgængelige.
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|