DM507 Algoritmer og datastrukturer
Forår 2017
Rolf Fagerberg
Kurset starter onsdag den 8. februar og slutter fredag den
26. maj.
Den skriftlige eksamen finder sted tirsdag den 6. juni.
Datoen for reeksamen er onsdag den 23. august, 2017. Reeksamen er
mundtlig. Eksamensspørgsmålene og andre oplysninger kan findes
her.
Timer
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 6 |
I |
Onsdag 8/2 |
10-12 |
U140 |
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 |
I |
Torsdag 9/2 |
08-10 |
U140 |
Sorteringsalgoritmer: Insertionsort, Mergesort (side 147-150 i
lærebogen, afsnit 2.1-3 i lærebogen, side 1-12 i
slides). Jeg vil vende 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.
|
| 6 |
TE |
|
|
|
Opgaver
|
| 7 |
I |
Onsdag 15/2 |
10-12 |
U140 |
Rekursive algoritmer (side 30 i lærebogen,
slides). 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. 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).
|
| 7 |
TE |
|
|
|
Opgaver
|
| 8 |
I |
Onsdag 22/2 |
10-12 |
U140 |
Flere sorteringsalgoritmer: Heapsort. (afsnit 6.1-4 i lærebogen, B.5.3 i
lærebogen, sidste del af slides). Forslag til
videomateriale: Mifta
Sintaha, fra start til slut (14:42).
|
| 8 |
I |
Torsdag 23/2 |
08-10 |
U140 |
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 diskussion af Projekt,
del I. Tilhørende Java.filer: PQ.java,
Element.java, Heapsort.java,
Testfiler.zip.
|
| 8 |
TE |
|
|
|
Opgaver
|
| 9 |
I |
Onsdag 1/3 |
10-12 |
U140 |
Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1 i
lærebogen, start 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. 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-2 i
lærebogen, første del af slides. Forslag
til videomateriale:
Tim
Roughgarden, Stanford, afsnit 13.1-2 samt 13.3 indtil 14:15.
|
| 9 |
TE |
|
|
|
Opgaver
|
| 10 |
I |
Onsdag 8/3 |
10-12 |
U140 |
Indsættelser og sletninger i binære søgetræer (afsnit 12.3 i lærebogen,
de næste par sider af slides. Forslag til
videomateriale:
Tim
Roughgarden, Stanford, afsnit 13.3 fra 14:15 indtil 22:00. Start på rød-sorte
træer (kapitel 13 i lærebogen, midten af
slides). 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 |
I |
Torsdag 9/3 |
08-10 |
U140 |
Afslutning af rød-sorte træer (kapitel 13 i lærebogen, midten af
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 13.4-6. 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 videomateriale:
Tim
Roughgarden, Stanford, afsnit 14.1-3 og 15.1.
|
| 10 |
TE |
|
|
|
Opgaver
|
| 11 |
I |
Onsdag 15/3 |
10-12 |
U140 |
Dekoration af binære søgetræer (afsnit 14.1-2 i lærebogen,
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 13.3 fra 22:00. Udlevering og diskussion
af Projekt, del II. Tilhørende Java.filer:
Dict.java,
TestProjectPartII.java. Invarianter
(siderne 18-20, 32-33, 157, 171-173 og 318-322 i lærebogen,
slides).
|
| 11 |
TE |
|
|
|
Opgaver |
| 12 |
I |
Onsdag 22/3 |
10-12 |
U140 |
Divide and Conquer algoritmer, rekursionsligninger, og analyse heraf via
rekursionstræer (afsnit 4.0 og 4.4 i lærebogen,
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 4.1.
|
| 12 |
I |
Torsdag 23/3 |
12-14 |
U140 |
Flere eksempler på analyse af Divide and Conquer algoritmer via
rekursionstræer, samt via Master Theorem (afsnit 4.4 og 4.5 i lærebogen,
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 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 |
TE |
|
|
|
Opgaver |
| 13 |
I |
Onsdag 29/3 |
10-12 |
U140 |
Eksempler på analyse af Divide and Conquer algoritmer via
rekursionstræer, når Master Theorem ikke kan bruges. Eksempel på en
Divide and Conquer algoritme: Strassens algoritme for
matrix-multiplikation (afsnit 4.2 i lærebogen,
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 3.3. Feedback på projekt, del I
(slides).
|
| 13 |
TE |
|
|
|
Opgaver |
| 14 |
I |
Onsdag 5/4 |
10-12 |
U140 |
Midtvejsevaluering.
Dynamisk programmering (afsnit 15.1-2 i lærebogen,
slides, afsnit 15.4 i lærebogen,
slides).
Forslag til videomateriale:
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii.
|
| 14 |
I |
Torsdag 6/4 |
12-14 |
U140 |
Grådige algoritmer (afsnit 16.1-3 i lærebogen,
slides - bevis for korrekthed af Huffmans
algoritme dog først næste gang). 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 diskussion
af Projekt, 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).
|
| 14 |
TE |
|
|
|
Opgaver |
| 15 |
I+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 15 pga. påske.
|
| 16 |
I |
Onsdag 19/4 |
10-12 |
U140 |
Lidt mere diskussion af projektet, del III. Bevis for optimalitet af
Huffmankodning (afsnit 16.3 i lærebogen, sidste del af
slides).
|
| 16 |
TE |
|
|
|
Opgaver |
| 17 |
I |
Onsdag 26/4 |
10-12 |
U140 |
Feedback på midtvejsevaluering
(slides). Datastrukturer for
disjoint sets (afsnit 21.1-3 i lærebogen,
slides).
|
| 17 |
I |
Torsdag 27/4 |
08-10 |
U140 |
Feedback på projekt del II
(slides). 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
videomateriale:
Tim
Roughgarden, Stanford, afsnit 9.2 og 10.1-3.
|
| 17 |
TE |
|
|
|
Opgaver |
| 18 |
I |
Onsdag 3/5 |
10-12 |
U140 |
DFS grafgennemløb, DAGs og topologisk sorting (afsnit 22.3-4 i
lærebogen, anden halvdel af slides).
Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 10.4-6.
|
| 18 |
TE |
|
|
|
Opgaver |
| 19 |
I |
Onsdag 10/5 |
10-12 |
U140 |
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).
|
| 19 |
I |
Torsdag 11/5 |
12-14 |
U140 |
Minimum udspændende træer (kapitel 23 i lærebogen,
slides).
|
| 19 |
TE |
|
|
|
Opgaver |
| 20 |
I |
Onsdag 17/5 |
10-12 |
U140 |
Korteste veje, single source, all-pairs. (afsnit 24.0-4 i lærebogen,
afsnit 25.2 i lærebogen,
slides. Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 20 |
TE |
|
|
|
Opgaver |
| 21 |
I |
|
|
|
De skemalagte forelæsninger i uge 21 afholdes ikke, da vi er blevet
færdig med pensum.
|
| 21 |
TE |
|
|
|
Opgaver |
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|