DM507 Algoritmer og datastrukturer

Forår 2015
Rolf Fagerberg


Kurset starter tirsdag den 3. februar og slutter tirsdag den 26. maj.

Spørgetime torsdag 4. juni, 10:15 i U140. Vi vil bla. gennemgå eksamenssættet for F14.

Skriftlige eksamen mandag den 8. juni kl. 16.00-20.00.

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 21. august, 2015. Reeksamen er mundtlig. Eksamensspørgsmålene og andre oplysninger kan findes her, lokaler og tider her.

Timer

Uge Type Dato Tid Lokale Indhold
6 I Tirsdag 3/2 10-12 U140 Introduktion til kurset (slides, kapitel 1 i lærebogen). Eksempel på algoritmeanalyse: Jul i Valhalla (Gerth Brodal: slides, noter).
6 I Torsdag 5/2 10-12 U140 Asymptotisk notation (afsnit 3.1, slides, Java-programmerne fra slides: Linear.java, Quadratic.java, Cubic.java). 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.
6 TE       Opgaver (Problem 1.1 fra lærebogen)
7 I Tirsdag 10/2 10-12 U140 Sorteringsalgoritmer: Insertionsort, Mergesort (side 147-150, afsnit 2.1-2, afsnit 2.3, starten af 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.
7 TE       Opgaver
8 I Tirsdag 17/2 10-12 U140 Flere sorteringsalgoritmer: Quicksort (afsnit 7.1-3, næste dele af slides).
8 I Torsdag 19/2 10-12 U140 Rekursive algoritmer. Flere sorteringsalgoritmer: Heapsort. (afsnit 6.1-4, B.5.3, slides, slides).
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 Tirsdag 3/3 10-12 U140 Heapsort færdig (afsnit 6.1-4, B.5.3, resten af slides). Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1, start af slides). Prioritetskøer (afsnit  6.5, 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).
10 I Torsdag 5/3 10-12 U20 Mere gennemgang af projektet. Flere sorteringsalgoritmer: sortering af heltal med Countingsort og Radixsort (afsnit 8.2-3, resten af slides).
10 TE       Opgaver
11 I       Bemærk: der er ingen I-timer (forelæsninger) i uge 11, da underviseren er i udlandet. Brug tiden på at starte arbejdet med projektet.
11 TE       Opgaver
12 I Tirsdag 17/3 10-12 U140 Dictionaries og deres implementation via binære søgetræer (side 229-230, afsnit 10.4, afsnit 12.1-3, afsnit 13.1-3, første del af 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 (mere om invarianter til næste 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 bogen.
12 TE       Opgaver
13 I Tirsdag 24/3 10-12 U140 Sletning i rød-sorte træer (afsnit 13.4, midten af slides). Dekoration af binære søgetræer (afsnit 14.1-2, slides). Implementation af dictionaries via hashing (afsnit 11.1-4 [dog ikke siderne 265-268 og 274-276], slutningen af slides).
13 I Torsdag 26/3 10-12 U140 Invarianter (side 18-20, 32-33, 157, 171-173, 318-322, slides). Divide and Conquer algoritmer, rekursionsligninger, og analyse heraf via rekursionstræer og Master Theorem (afsnit 4.0, 4.4, 4.5, slides). Læs også kommentaren om forholdet mellem de to analysemetoder (rekursionstræsmetoden og Master Theorem) på sedlen med opgaver til Uge 15.
13 TE       Opgaver
14 I+TE       Bemærk: der er ingen timer (hverken I eller TE) i uge 14 pga. påske.
15 I Tirsdag 7/4 10-12 U140 Analyse af Divide and Conquer algoritmer via rekursionstræer og Master Theorem (afsnit 4.0, 4.4, 4.5, slides).
15 TE       Opgaver
16 I Tirsdag 14/4 10-12 U140 Eksempel på en Divide and Conquer algoritme: Strassen algoritme for matrix-multiplikation (afsnit 4.2).
16 I Torsdag 16/4 10-12 U140 Dynamisk programmering (afsnit 15.1-2, slides, afsnit 15.4, første del af slides).
16 TE       Opgaver
17 I Tirsdag 21/4 10-12 U140

Endnu et eksempel på dynamisk programmering (afsnit 15.3, anden del af slides) Grådige algoritmer (afsnit 16.1-3, 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. Udlevering og diskussion af Projekt, del II. Tilhørende filer er to biblioteksfunktioner BitInputStream.java, BitOutputStream.java, set et eksempel på brug af dem Test.java (læs kommentarer i programmet).

17 TE       Opgaver
18 I Tirsdag 28/4 10-12 U140 Feedback på projekt, del I (slides). Resumé af midtvejsevaluringe (slides). Gennemgang af projektet, del II.
18 I Torsdag 30/4 10-12 U140 Bevis for optimalitet af Huffmankodning (afsnit 16.3, sidste del af slides). Datastrukturer for disjoint sets (afsnit 21.1-3, slides). Start på grafalgoritmer: repræsentation af grafer (afsnit 22.1, 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 Tirsdag 5/5 10-12 U140 BFS grafgennemløn, DFS grafgennemløb, DAGs og topologisk sorting (afsnit 22.2-4, slides).
19 TE       Opgaver
20 I Tirsdag 12/5 10-12 U140 Mere om DFS grafgennemløb, DAGs og topologisk sortering (afsnit 22.3-4, slides). Sammenhængskomponenter (i uorienterede grafer) og stærke sammenhængskomponenter (i orienterede grafer) (slides). Start på minimum udspændende træer (kapitel 23, slides).
20 I Fredag 15/5 10-12 U140 Mere om minimum udspændende træer (kapitel 23, slides). Korteste veje, single source (afsnit 24.0, start af slides).
20 TE       Opgaver
21 I Mandag 18/5 14-16 U110 GENTAGELSE af forelæsningen fra fredag 15/5. Mere om minimum udspændende træer (kapitel 23, slides). Korteste veje, single source (afsnit 24.0, start af slides).
21 I Tirsdag 19/5 10-12 U140 Mere om korteste veje, single source (afsnit 24.1-3, slides). Korteste veje, all pairs (afsnit 25.2-3, slides)
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)