DM507/DS814 Algoritmer og datastrukturer
Forår 2020
Rolf Fagerberg
Generel information
Kurset starter mandag den 3. februar og slutter mandag den
25. maj.
Den skriftlige multiple-choice eksamen finder sted online torsdag den
11. juni kl. 09:30 til 12:30.
Der er en spørgetime med underviseren onsdag 10. juni kl. 11:00
på dette Zoom
mødelink (optagelse af spørgetimen).
Datoen for reeksamen er onsdag-fredag 6.-7. august, 2020. Reeksamen er
mundtlig og foregår på Zoom. Listen af emner man kan trække samt andre
oplysninger kan findes
her. Rækkefølgen og tider til eksamen
kan ses på et opslag på kursets Blackboard side. Der afholdes en
spørgetime før reeksamen tirsdag den 4. august kl. 15:00 på
Zoom linket for
reeksamen.
Der er separat reeksamen i projektdelen. Du skal aflevere en løsning
af samme projekt (men ikke eventuelle dele I-III, som allerede er
blevet godkendt i forår 2020) på Blackboard under SDU Assignment
senest torsdag den 13. august kl. 12:00.
Timer
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 6 |
F |
Mandag 3/2 |
15-17 |
U55 |
Introduktion til kurset (slides, kapitel 1 i
lærebogen).
Eksempel på algoritmeanalyse: Ombytningspuslespil
(slides, noter). Et
ombytningspuslespil
fra nettet. Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 1.1, 1.4 og 1.8.
|
| 6 |
F |
Fredag 7/2 |
12-14 |
U55 |
Start på sorteringsalgoritmer: Insertionsort, Selectionsort, Mergesort (side 147-150 i lærebogen, afsnit 2.1-3 i lærebogen, side 1-11 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. Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 1.5-7.
Asymptotisk notation (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. Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 2.1-4 (evt. også 2.5 for ekstra
eksempler).
|
| 6 |
E |
|
|
|
Opgaver
|
| 7 |
F |
Torsdag 13/2 |
12-14 |
U55 |
Mere om asymptotisk notation (afsnit 3.1 i lærebogen,
slides).
Rekursive algoritmer (side 30 i lærebogen,
slides).
|
| 7 |
E |
|
|
|
Opgaver
|
| 8 |
F |
Mandag 17/2 |
15-17 |
U55 |
Testspørgsmål i asymptotisk analyse.
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). |
| 8 |
F |
Torsdag 20/2 |
12-14 |
U55 |
Flere sorteringsalgoritmer:
Quicksort (afsnit 7.1-3 i lærebogen, næste
dele af slides). Forslag til
videomateriale:
Tim
Roughgarden, Stanford, afsnit 5.1-4.
Start på Heapsort (afsnit 6.1-4 i lærebogen, B.5.3 i lærebogen, sidste
del af slides). Forslag til videomateriale:
Mifta Sintaha.
|
| 8 |
E |
|
|
|
Opgaver
|
| 9 |
F |
Tirsdag 25/2 |
16-18 |
U45 |
Slut på Heapsort (afsnit 6.1-4 i lærebogen, B.5.3 i lærebogen, sidste
del af slides). Forslag til videomateriale:
Mifta Sintaha.
Prioritetskøer (afsnit 6.5 i lærebogen,
slides). Forslag til videomateriale:
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 diskusson af projektet, del I. [Java version:
projektbeskrivelse, del I,
PQ.java, Element.java,
PQSort.java, Testfiler.zip.]
[Python version: projektbeskrivelse,
del I, PQSort.py,
Testfiler.zip.]
|
| 9 |
E |
|
|
|
Opgaver
|
| 10 |
F |
Tirsdag 3/3 |
16-18 |
U55 |
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 videomateriale:
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.
|
| 10 |
F |
Fredag 6/3 |
08-10 |
U55 |
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. Forslag
til videomateriale:
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 (sletninger gennemgås dog først
næste gang)). Forslag til videomateriale:
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 |
|
|
|
Opgaver
|
| 11 |
F |
Torsdag 12/3 |
|
|
Multiple-choice test (25 minutter). Kan findes i Blackboard
under E-test som MC test 1.
Sletning i rød-sorte træer (screencast [især
de sidste dele], afsnit 13.4 i lærebogen, side 26-30 i
slides)).
Implementation af dictionaries via hashing
(screencast, afsnit 11.1-4 i lærebogen [dog ikke
siderne 265-268 og 274-276], slutningen af
slides). Forslag til yderligere videomateriale:
Tim
Roughgarden, Stanford, afsnit 14.1-3 og 15.1.
|
| 11 |
E |
|
|
|
Opgaver. Instruktorernes
løsninger til del II,
CountingSort.java,
counting_sort.py.
|
| 12 |
F |
Tirsdag 17/3 |
|
|
Udlevering og diskussion af Projekt, del II
(screencast) [Java version:
projektbeskrivelse,
Dict.java.] [Python version:
projektbeskrivelse.]
Dekoration af binære søgetræer (screencast,
afsnit 14.1-2 i lærebogen, slides).
Forslag til yderligere videomateriale:
Tim
Roughgarden, Stanford, afsnit 13.3 fra 22:00.
Invarianter (screencast, siderne 18-20, 32-33,
157, 171-173 og 318-322 i lærebogen,
slides).
|
| 12 |
F |
Torsdag 19/3 |
|
|
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:
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. Instruktorernes
løsninger.
|
| 13 |
F |
Torsdag 26/3 |
|
|
Mere om rekursionstræsmetoden og Master Theorem
(screencast, 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 (screencast, afsnit 4.2 i
lærebogen, slides). Forslag til yderligere
videomateriale:
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.
Instruktorernes løsninger.
|
| 14 |
F |
Tirsdag 31/3 |
08-10 |
Zoom mødelink
|
Dynamisk programmering (optagelse af videoundervisning, afsnit 15.1-2 i lærebogen,
slides.
Forslag til yderligere videomateriale:
Dan
Suthers, University of Hawaii,
Bellmans
forklaring om historien bag navnet Dynamisk Programmering (ikke
pensum).
|
| 14 |
E |
|
|
|
Opgaver.
Instruktorernes løsninger,
optagelse
af spørgetime.
|
| 14 |
F |
Torsdag 2/4 |
12-14 |
Zoom mødelink |
Mere om dynamisk programmering
(screencast,
optagelse af videoundervisning,
afsnit 15.4 i lærebogen,
slides). Forslag til yderligere
videomateriale:
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii.
Midtvejsevaluering af kurset.
|
| 16 |
F |
Torsdag 16/4 |
12-14 |
Zoom mødelink |
Multiple-choice test (45 minutter). Kan findes i Blackboard under
E-test som MC test 2.
Grådige algoritmer (optagelse af
videoundervisning, afsnit 16.1-3 i lærebogen,
slides). 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 og indledende diskussion af Projekt, del III.
[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
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
angivelse af korrekt størrelse efter komprimering.]
|
| 16 |
E |
Spørgetime I: mandag 20/4 14:15-15:00
Spørgetime II: onsdag 22/4 14:15-15:00
|
|
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).
Instruktorernes løsninger,
optagelse
af spørgetime I,
optagelse af
spørgetime II.
|
| 17 |
F |
Tirsdag 21/4 |
10-12 |
Zoom mødelink |
Mere gennemgang af projektet, del III
(optagelse af
videoundervisning, tegneserieudgave af
del III).
Bevis for korrekthed af Huffmans algoritme
(optagelse af
videoundervisning, afsnit 16.3 i lærebogen, sidste del af
slides).
Datastrukturer for disjoint sets
(optagelse af
videoundervisning, afsnit 21.1-3 i lærebogen,
slides).
Multiple-choice test i opgaveteksten til projekt del III (15
minutter). Kan findes i Blackboard under E-test som MC test Projekt
Del III.
|
| 17 |
F |
Torsdag 23/4 |
12-14 |
Zoom mødelink |
Afslutning af datastrukturer for disjoint sets
(optagelse af
videoundervisning, afsnit 21.1-3 i lærebogen,
slides).
Start på grafalgoritmer: repræsentation af grafer
(optagelse af
videoundervisning, afsnit 22.1 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:
Tim
Roughgarden, Stanford, afsnit 9.2 og 10.1-3.
|
| 17 |
E |
Spørgetime: mandag 27/4 14:15-15:00
|
|
Zoom mødelink
|
Opgaver.
Instruktorernes løsninger,
optagelse
af spørgetime.
|
| 18 |
F |
Torsdag 30/4 |
12-14 |
Zoom mødelink |
BFS gennemløb og DFS grafgennemløb
(optagelse af videoundervisning,
afsnit 22.2-3 i lærebogen, slides).
Forslag til yderligere videomateriale:
Tim
Roughgarden, Stanford, afsnit 10.4-6.
|
| 18 |
E |
Spørgetime I: mandag 4/5 14:15-15:00
Spørgetime II: onsdag 6/5 14:15-15:00
|
|
Zoom mødelink
|
Opgaver.
Instruktorernes løsninger,
optagelse af
spørgetime I,
optagelse
af spørgetime II.
|
| 19 |
F |
Mandag 4/5 |
12-14 |
Zoom mødelink |
Afslutning på DFS, DAGs, topologisk sorting
(optagelse af videoundervisning,
afsnit 22.3-4 i lærebogen, slides).
Sammenhængskomponenter i uorienterede grafer og stærke
sammenhængskomponenter i orienterede grafer
(optagelse af videoundervisning, side
1170-71 og 615-17 i lærebogen,
slides).
|
| 19 |
F |
Torsdag 7/5 |
12-14 |
Zoom mødelink |
Minimum udspændende træer (optagelse af
videoundervisning, kapitel 23 i lærebogen,
slides).
|
| 19 |
E |
Spørgetime: mandag 11/5 14:15-16:00 |
|
Zoom mødelink |
Opgaver
Instruktorernes løsninger,
optagelse af
spørgetime del 1,
optagelse af
spørgetime del 2.
|
| 20 |
F |
Tirsdag 12/5 |
10-12 |
Zoom mødelink |
Korteste veje, single source, Bellman-Fords algoritme
(optagelse af videoundervisning,
afsnit 24.0 og 24.1 i lærebogen,
slides side 1-11) . Forslag til
yderligere videomateriale:
Tim Roughgarden, Stanford, afsnit 11.1-4.
|
| 20 |
E |
Spørgetime I: mandag 18/5 14:15-16:00
Spørgetime II: onsdag 20/5 14:15-16:00
|
|
Zoom mødelink
|
Opgaver. Instruktorernes
løsninger,
optagelse
af spørgetime I,
optagelse
af spørgetime II.
|
| 21 |
F |
Tirsdag 19/5 |
10-12 |
Zoom mødelink |
Afslutning af korteste veje, single source: Dijkstras algoritme,
shortest paths på DAGs. Korteste veje, all-pairs.
(Optagelse af videoundervisning,
afsnit 24.2-3 i lærebogen, afsnit 25.0 og 25.2-3 i lærebogen,
slides. Forslag til yderligere
videomateriale:
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 21 |
E |
Spørgetime: mandag 25/5 14:15-16:00
|
|
|
Opgaver. Instruktorernes
løsninger,
optagelse
af spørgetime.
|
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|