DM507 Algoritmer og datastrukturer
Forår 2014
Rolf Fagerberg
Kurset starter mandag den 3. februar og slutter fredag den
30. maj.
Der er spørgetime mandag 23. juni, 15:00 i
U20. Vi vil bla. gennemgå
eksamenssættet for F13.
Datoen for den skriftlige eksamen er tirsdag den 24. juni.
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 22. august, 2014. Reeksamen er
mundtlig. Eksamensspørgsmålene og andre oplysninger kan findes
her.
Timer
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 6 |
I |
Mandag 3/2 |
14-16 |
U140 |
Introduktion til kurset (slides, kapitel 1 i
lærebogen). Eksempel på algoritmeanalyse: Jul i Valhalla (Gerth Brodal:
slides, noter). |
| 6 |
I |
Onsdag 5/2 |
14-16 |
U140 |
Asymptotisk notation (afsnit 3.1,
slides, Java-programmerne fra
slides: Linear.java,
Quadratic.java,
Cubic.java). Start på sorteringsalgoritmer:
Insertionsort (afsnit 2.1-2, starten af
slides). Det kan
være en fordel at orientere sig i afsnit 3.2 hvis der i kurset bruges
matematiske formler, definitioner og metoder, man har glemt. Derudover:
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.
|
| 6 |
TE |
|
|
|
Opgaver |
| 7 |
I |
Onsdag 12/2 |
14-16 |
U140 |
Flere sorteringsalgoritmer: Mergesort, Quicksort (side 147-150,
afsnit 2.3, 7.1-3, midten af slides).
|
| 7 |
TE |
|
|
|
Opgaver |
| 8 |
I |
Mandag 17/2 |
14-16 |
U140 |
Flere sorteringsalgoritmer: Heapsort, nedre grænser for
sammenligningsbaseret sortering (afsnit 6.1-4, B.5.3, 8.1),
resten af slides, start af
slides).
|
| 8 |
I |
Onsdag 17/2 |
14-16 |
U140 |
Flere sorteringsalgoritmer: sortering af heltal med Countingsort og
Radixsort, prioritetskøer
(afsnit 8.2-3, 6.5),
resten af slides,
slides). Udlevering og diskussion af
Projekt, del I (tilhørende Java.filer:
PQ.java,
Element.java,
Dict.java). Eksempel på brug af Scanner i Java:
ScannerExample.java (læs kommentarer i
programmet). Testprogram som bruger PQHeap.java og DictBinTree.java:
TestProjectPartI.java (læs kommentarer i
programmet).
|
| 8 |
TE |
|
|
|
Opgaver |
| 9 |
I+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 9 (ugen er
friholdt til reeksamen for nogle af studieretningerne).
|
| 10 |
I |
Mandag 3/3 |
14-16 |
U140 |
Start på dictionaries og deres
implementation via binære søgetræer (side 229-230, afsnit 10.4,
afsnit 12.1-2, start af slides).
|
| 10 |
I |
Onsdag 5/3 |
14-16 |
U140 |
Mere om dictionaries: indsætning og sletning i binære søgetræer (afsnit 12.3,
midten af slides).
Invarianter (side 18-20, 32-33, 157, 171-173,
slides).
Bemærk at bogen er ret tung læsning i kapitel 13. Det skyldes dels, at
bogens 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
(se slides om invarianter), 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 bogen.
|
| 10 |
TE |
|
|
|
Opgaver |
| 11 |
I |
Onsdag 12/3 |
14-16 |
U140 |
Divide and Conquer algoritmer, rekursionsligninger, og analyse heraf via
rekursionstræer og Master Theorem (afsnit 4.0, 4.4, 4.5,
slides, Lenes
forelæsningsnoter). Denne forelæsning varetages af Lene Monrad Favrholdt.
Læs også kommentaren om forholdet mellem de to analysemetoder
(rekursionstræsmetoden og Master Theorem) på
sedlen med opgaver til Uge 13.
|
| 11 |
TE |
|
|
|
Opgaver |
| 12 |
I |
Mandag 17/3 |
14-16 |
U140 |
Endnu et eksempel på en Divide and Conquer algoritme: Strassen algoritme
for matrix-multiplikation (afsnit 4.2). Mere om dictionaries: dekoration
af binære søgetræer (afsnit 14.1-2,
slides).
|
| 12 |
I |
Onsdag 19/3 |
14-16 |
U140 |
Mere om dictionaries: hashing (afsnit 11.1-4 [dog ikke siderne 265-268
og 274-276], slutningen af slides). Start
på dynamisk programmering (afsnit 15.1,
slides).
|
| 12 |
TE |
|
|
|
Opgaver |
| 13 |
I |
Onsdag 26/3 |
14-16 |
U140 |
Flere eksempler på dynamisk programmering (afsnit 15.2-4,
slides).
|
| 13 |
TE |
|
|
|
Opgaver |
| 14 |
I+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 14 (ugen er
friholdt til eksamen for nogle af studieretningerne).
|
| 15 |
I |
Mandag 7/4 |
14-16 |
U140 |
Grådige algoritmer (afsnit 16.1-2, 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 |
I |
Onsdag 9/4 |
14-16 |
U140 |
Flere grådige algoritmer: Huffmankodning (afsnit 16.3,
slides). Udlevering og diskussion af
Projekt, del II. Tilhørende filer:
BitInputStream.java,
BitOutputStream.java,
Test.java (læs kommentarer i programmet).
|
| 16 |
I+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 16 pga. påske.
|
| 17 |
I |
Onsdag 23/4 |
14-16 |
U140 |
Gennemgang af filer hørende til projektet, del II:
BitInputStream.java,
BitOutputStream.java,
Test.java (læs kommentarer i programmet). Bevis for
optimalitet af Huffmankodning (afsnit 16.3,
slides).
|
| 17 |
TE |
|
|
|
Opgaver |
| 18 |
I |
Mandag 28/4 |
14-16 |
U140 |
Tilbagelevering af projekt, del I. Datastrukturer for disjoint sets
(afsnit 21.1-3, slides).
|
| 18 |
I |
Onsdag 30/4 |
14-16 |
U140 |
Start på grafalgoritmer: repræsentation af grafer, BFS grafgennemløb
(afsnit 22.1-2, slides). Derudover er
de første tre sider af appendiks B.4 (side 1168-70) om basal terminologi
for grafer overladt til selvstændig læsning.
|
| 18 |
TE |
|
|
|
Opgaver |
| 19 |
I |
Onsdag 7/5 |
14-16 |
U140 |
DFS grafgennemløb, DAGs og topologisk sorting
(afsnit 22.3-4,
slides). Sammenhængskomponenter
(slides, første halvdel).
|
| 19 |
TE |
|
|
|
Opgaver |
| 20 |
I |
Mandag 12/5 |
14-16 |
U140 |
Stærke sammenhængskomponenter (afsnit 22.5,
slides, anden halvdel).
|
| 20 |
I |
Onsdag 14/5 |
14-16 |
U140 |
Mínimum udspændende træer (kapitel 23,
slides).
|
| 20 |
TE |
|
|
|
Opgaver |
| 21 |
I |
Onsdag 21/5 |
14-16 |
U140 |
Korteste veje, single source (kapitel 24,
slides).
|
| 21 |
TE |
|
|
|
Opgaver |
| 22 |
I |
Onsdag 28/5 |
14-16 |
U140 |
Korteste veje, all pairs (afsnit 25.2-3,
slides).
|
| 22 |
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)
|
|