DM507 Algoritmer og datastrukturer
Forår 2018
Rolf Fagerberg
Kurset starter tirsdag den 6. februar og slutter fredag den
25. maj.
Den skriftlige eksamen finder sted fredag den 22. juni.
Datoen for reeksamen er mandag den 27. august, 2018. Reeksamen er
mundtlig. Listen af emner man kan trække samt andre oplysninger kan
findes her.
Timer
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 6 |
I |
Tirsdag 6/2 |
14-16 |
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 |
Fredag 9/2 |
08-10 |
U1 |
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 |
Tirsdag 13/2 |
14-16 |
U140 |
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). Rekursive algoritmer (side 30 i lærebogen,
slides).
Disse timer forelæses af Lene
Monrad Favrholdt.
|
| 7 |
TE |
|
|
|
Opgaver
|
| 8 |
I |
Mandag 19/2 |
08-10 |
U1 |
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.
|
| 8 |
I |
Fredag 23/2 |
08-10 |
U45 |
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.
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 af Projekt, del I. Tilhørende
Java.filer: PQ.java, Element.java,
Heapsort.java,
Testfiler.zip.
|
| 8 |
TE |
|
|
|
Opgaver
|
| 9 |
I |
Tirsdag 27/2 |
14-16 |
U1 |
Diskussion af Projekt, del I.
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.
|
| 9 |
TE |
|
|
|
Opgaver
|
| 10 |
I |
Tirsdag 6/3 |
14-16 |
U140 |
Multiple-choice test i klassen (kan findes i Blackboard under E-test som
MC test 1). 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.
|
| 10 |
I |
Fredag 9/3 |
08-10 |
U45 |
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 |
TE |
|
|
|
Opgaver
|
| 11 |
I |
Tirsdag 13/3 |
14-16 |
U1
|
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. 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.
|
| 11 |
TE |
|
|
|
Opgaver |
| 12 |
I |
Tirsdag 20/3 |
14-16 |
U1 |
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 (afsnit 4.0 og
4.4 i lærebogen, slides). Forslag til
videomateriale:
Tim
Roughgarden, Stanford, afsnit 4.1.
|
| 12 |
I |
Fredag 23/3 |
08-10 |
U45 |
Feedback på projekt, del I
(slides). 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+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 13 pga. påske.
|
| 14 |
I |
Tirsdag 3/4 |
14-16 |
U140 |
Eksempler på analyse af Divide and Conquer algoritmer via
rekursionstræer, når Master Theorem ikke kan bruges. Midtvejsevaluering.
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. For the historical development of
the running time of the asymptotically best matrix multiplication
algorithm, see this
wiki
page.
|
| 14 |
TE |
|
|
|
Opgaver |
| 15 |
I |
Mandag 9/4 |
12-14 |
U140 |
Dynamisk programmering (afsnit 15.1-2 i lærebogen,
slides, afsnit 15.4 i lærebogen,
første del af slides).
Forslag til videomateriale:
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of
Hawaii. Bellmans
forklaring om historien bag navnet Dynamisk
Programmering.
|
| 15 |
I |
Tirsdag 10/4 |
14-16 |
U140 |
Mere om dynamisk programmering (afsnit 15.4 i lærebogen, anden del af
slides). Grådige algoritmer
(afsnit 16.1-2 i lærebogen, første del af
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.
|
| 15 |
TE |
|
|
|
Opgaver |
| 16 |
I |
Tirsdag 17/4 |
10-12 |
U140 |
Mere om grådige algoritmer: Huffmans algoritme (afsnit 16.1-3 i
lærebogen, sidste del af slides). Udlevering og
diskussion af Projekt, del III. Multiple-choice test i klassen (kan
findes i Blackboard under E-test som MC test 2). 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).
|
| 16 |
TE |
|
|
|
Opgaver |
| 17 |
I |
Mandag 23/4 |
12-14 |
U55 |
Lidt mere om projektet, del III. 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).
|
| 17 |
I |
Onsdag 25/4 |
16-18 |
U55 |
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 |
Fredag 4/5 |
08-10 |
U45 |
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 |
Tirsdag 8/5 |
14-16 |
U1 |
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).
Disse timer forelæses af Lene
Monrad Favrholdt.
|
| 19 |
TE |
|
|
|
Opgaver |
| 20 |
I |
Mandag 14/5 |
10-12 |
U140 |
Mere om minimum udspændende træer (kapitel 23 i lærebogen, resten af
slides).
|
| 20 |
I |
Torsdag 17/5 |
08-10 |
U110 |
Korteste veje, single source, all-pairs. (afsnit 24.0-1 og 24.3 i lærebogen,
slides. Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 20 |
TE |
|
|
|
Opgaver |
| 20 |
I |
Torsdag 24/5 |
08-10 |
U110 |
Afslutning af korteste veje, single source. Korteste veje, all-pairs.
(afsnit 24.2-3 i lærebogen, afsnit 25.2-3 i lærebogen,
slides. Forslag til videomateriale:
Tim
Roughgarden, Stanford, afsnit 11.1-4.
|
| 21 |
TE |
|
|
|
Opgaver |
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|