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)