DM507 Algoritmer og datastrukturer
Forår 2016
Rolf Fagerberg
Kurset starter mandag den 1. februar og slutter fredag den
20. maj.
Den skriftlige eksamen finder sted mandag den 6. juni kl. 15.00-19.00.
Spørgetime fredag 3. juni, 12:15-15.00 i
U48A. Vi vil
bla. gennemgå eksamenssættet for F15.
Eksamensættet endte således, med følgende
vejledende løsninger.
Eksamenskaraktererne fordelte sig på følgende
måde.
Datoen for reeksamen er fredag den 19. august, 2016. Reeksamen er
mundtlig. Eksamensspørgsmålene og andre oplysninger kan findes
her.
Timer
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 5 |
I |
Mandag 1/2 |
12-14 |
U140 |
Introduktion til kurset (slides, kapitel 1 i
lærebogen). Eksempel på algoritmeanalyse: Jul i Valhalla (Gerth Brodal:
slides, noter). Forslag til
videomateriale: Tim
Roughgarden, Stanford/Coursera, fra start til 0:04:15, fra 0:25:30 til
0:43:00, samt fra 1:14:00 til slut (1:28:49).
|
| 5 |
I |
Torsdag 4/2 |
08-10 |
U140 |
Sorteringsalgoritmer: Insertionsort, Mergesort (side 147-150 i
lærebogen, afsnit 2.1-3 i lærebogen, side 1-11 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/Coursera, fra 0:43:00 til 1:14:00.
|
| 5 |
TE |
|
|
|
Opgaver |
| 6 |
I |
Mandag 8/2 |
12-14 |
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/Coursera, 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/Coursera, fra start til 33:20 (eller evt. helt til slut
(41:12) for ekstra eksempler).
|
| 6 |
I |
Onsdag 10/2 |
14-16 |
U140 |
Flere sorteringsalgoritmer: Heapsort. (afsnit 6.1-4 i lærebogen, B.5.3 i
lærebogen, slides). Forslag til
videomateriale: Mifta
Sintaha, fra start til slut (14:42).
|
| 6 |
TE |
|
|
|
Opgaver |
| 7 |
I+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 7 da
underviseren er bortrejst.
|
| 8 |
I+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 8, da ugen er
friholdt til reeksamen for nogle af studieretningerne.
|
| 9 |
I |
Mandag 29/2 |
12-14 |
U140 |
Prioritetskøer (afsnit 6.5 i lærebogen,
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford/Coursera, 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. Eksempel på brug af Scanner i Java:
ScannerExample.java (læs kommentarer i
programmet). Testprogram som bruger PQHeap.java:
TestProjectPartI.java (læs kommentarer i
programmet). Flere sorteringsalgoritmer: sortering af heltal med
Countingsort og Radixsort (afsnit 8.2-3 i lærebogen, anden del af
slides).
|
| 9 |
TE |
|
|
|
Opgaver |
| 10 |
I |
Mandag 7/3 |
12-14 |
U140 |
Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1 i
lærebogen, start af slides).
Forslag til videomateriale:
Tim
Roughgarden, Stanford/Coursera, afsnit 8.6. 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, Lenes
noter). Forslag til videomateriale:
Tim
Roughgarden, Stanford/Coursera, afsnit 13.1-2 samt 13.3 indtil 22:00.
Disse timer forelæses af Lene
Monrad Favrholdt.
|
| 10 |
I |
Torsdag 10/3 |
08-10 |
U140 |
Ingen timer, da underviseren er bortrejst.
|
| 10 |
TE |
|
|
|
Opgaver |
| 11 |
I |
Mandag 14/3 |
12-14 |
U140 |
Rød-sorte træer (kapitel 13 i lærebogen, midten af
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford/Coursera, 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.
|
| 11 |
TE |
|
|
|
Opgaver |
| 12 |
I+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 12 pga. påske.
|
| 13 |
I |
Tirsdag 29/3 |
14-16 |
U48A |
Gennemgang af Projekt, del II. Tilhørende
Java.filer: Dict.java,
TestProjectPartII.java. Repetition af
sletning i rød-sorte træer (afsnit 13.4 i lærebogen, midten af
slides). Dekoration af binære søgetræer
(afsnit 14.1-2 i lærebogen,
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford/Coursera, afsnit 13.3 fra 22:00.
|
| 13 |
I |
Torsdag 31/3 |
08-10 |
U140 |
Feedback på projekt, del 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 videomateriale:
Tim
Roughgarden, Stanford/Coursera, afsnit 14.1-3. Invarianter (siderne
18-20, 32-33, 157, 171-173 og 318-322 i lærebogen,
slides).
|
| 13 |
TE |
|
|
|
Arbejde i klassen med Projekt,
del II. Tilhørende Java.filer: Dict.java.
|
| 14 |
I |
Mandag 4/4 |
12-14 |
U140 |
Divide and Conquer algoritmer, rekursionsligninger, og analyse heraf via
rekursionstræer og Master Theorem (afsnit 4.0, 4.4 og 4.5 i lærebogen,
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford/Coursera, 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]. Læs også kommentaren om forholdet mellem de to
analysemetoder (rekursionstræsmetoden og Master Theorem) på
sedlen med opgaver til Uge 15.
|
| 14 |
TE |
|
|
|
Opgaver |
| 15 |
I |
Mandag 11/4 |
12-14 |
U140 |
Feedback på midtvejsevaluering. Flere eksempler på analyse af Divide
and Conquer algoritmer via rekursionstræer og Master Theorem
(afsnit 4.0, 4.4 og 4.5 i lærebogen,
slides).
|
| 15 |
I |
Torsdag 14/4 |
08-10 |
U140 |
Flere eksempler på analyse af Divide and Conquer algoritmer via
rekursionstræer. 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/Coursera, afsnit 3.3.
|
| 15 |
TE |
|
|
|
Opgaver |
| 16 |
I |
Mandag 18/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:
Tim
Roughgarden, Stanford/Coursera, afsnit 9.5,
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii,
Dan
Suthers, University of Hawaii.
|
| 16 |
TE |
|
|
|
Opgaver |
| 17 |
I |
Mandag 25/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. Forslag til videomateriale:
Tim
Roughgarden, Stanford/Coursera, afsnit 2.1 og 8.1-4. Udlevering og
diskussion af Projekt, del III. Tilhørende
filer er to biblioteksfunktioner
BitInputStream.java,
BitOutputStream.java, samt et eksempel på
brug af dem Test.java (læs kommentarer i programmet).
|
| 17 |
I |
Torsdag 28/4 |
08-10 |
U140 |
Feedback på projekt, del II
(slides). Mere diskussion af
projektet, del III. Datastrukturer for disjoint sets (afsnit 21.1-3 i
lærebogen, slides).
|
| 17 |
TE |
|
|
|
Opgaver |
| 18 |
I |
Mandag 2/5 |
12-14 |
U140 |
Bevis for optimalitet af Huffmankodning (afsnit 16.3 i lærebogen, sidste
del af slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford/Coursera, afsnit 8.5-6. 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/Coursera, afsnit 9.2 og 10.1-3.
|
| 18 |
TE |
|
|
|
Opgaver |
| 19 |
I |
Mandag 9/5 |
12-14 |
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/Coursera, afsnit 10.4-6. Sammenhængskomponenter
(i uorienterede grafer) og stærke sammenhængskomponenter (i orienterede
grafer) (side 1170-71 og 615-17 i lærebogen,
slides, dog uden beviset for
korrekthed af algoritmen for stærke sammenhængskomponenter)
|
| 19 |
I |
Tirsdag 10/5 |
14-16 |
U140 |
Minimum udspændende træer (kapitel 23 i lærebogen,
slides). Forslag til videomateriale:
Tim
Roughgarden, Stanford/Coursera, afsnit 4.1-7 og 5.1-5.
|
| 19 |
TE |
|
|
|
Opgaver |
| 20 |
I |
Torsdag 19/5 |
08-10 |
U140 |
Korteste veje, single source, all-pairs. (afsnit 24.0-4 i lærebogen,
afsnit 25.2 i lærebogen, slides
(undtagen den sidste side om Johnsons algoritme)). Forslag til
videomateriale:
Tim
Roughgarden, Stanford/Coursera, afsnit 13.1-7,
Tim
Roughgarden, Stanford/Coursera, afsnit 11.1-3,
Tim
Roughgarden, Stanford/Coursera, afsnit 14.1-3.
|
| 20-21 |
TE |
|
|
|
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)
|
|