DM507 Algoritmer og datastrukturer

Forår 2013
Rolf Fagerberg


Kurset starter tirsdag den 29. januar. Det kører i 3. og 4. kvartal 2013.

Der er spørgetime fredag 21. juni, 12:15-14:00 i U20. Vi vil bla. regne eksamenssættet for F12.

Eksamensdatoen er mandag 24. juni. Her er eksamensættet samt vejledende løsninger.

Eksamenskaraktererne fordelte sig på følgende måde.

Datoen for reeksamen er tirsdag den 20. august, 2013. Reeksamen er mundtlig. Eksamensspørgsmålene og andre oplysninger kan findes her.

Timer

Uge Type Dato Tid Lokale Indhold
5 F Tirsdag 29/1 10-12 U20 Introduktion til kurset (slides). Eksempel på algoritmeanalyse: Jul i Valhalla (Gerth Brodal: slides, noter, applet).
5 F Onsdag 30/1 12-14 U20 Asymptotisk notation (afsnit 3.1, slides, Java-programmerne fra slides: Linear.java, Quadratic.java, Cubic.java). Start på sorteringsalgoritmer: Insertionsort (afsnit 2.1-2, 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.
5 E       Opgaver
6 F Tirsdag 5/2 10-12 U20 Flere sorteringsalgoritmer: Mergesort, Quicksort (afsnit 2.3, 7.1-3, side 147-150, slides).
6 E       Opgaver
7 F Tirsdag 12/2 10-12 U20 Mere om sorteringsalgoritmer: Heapsort, nedre grænser for sortering (afsnit 6.1-4, B.5.3, 8.1, slides, slides).
7 F Onsdag 13/2 12-14 U20 Sortering af heltal: Counting sort, Radixsort (afsnit 8.2-3, slides). Prioritetskøer (afsnit 6.5, slides). Invarianter (side 18-20, 32-33, 157, 171-173), slides).
7 E       Opgaver
8 F Tirsdag 19/2 10-12 U20 Udlevering og diskussion af Projekt, del I (tilhørende Java.filer: PQ.java, Element.java, Dict.java). Bevis for at BuildHeap tager linear tid. Start på dictionaries og deres implementation via binære søgetræer (side 229-230, afsnit 10.4, afsnit 12.1-2, slides).
8 E       Opgaver
9 F Tirsdag 26/2 10-12 U20 Invarianter igen (slides). Mere om dictionaries: indsætning og sletning i binære søgetræer (afsnit 12.3, slides)).
9 F Onsdag 27/2 12-14 U20 Mere om dictionaries: rød-sorte træer (kapitel 13.1-3, 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.
9 E       Opgaver
10 F Tirsdag 5/3 10-12 U20 Mere om dictionaries: Sletning i rød-sorte træer (afsnit 13.4, slides). Dekoration af binære søgetræer (afsnit 14.1-2, slides).
10 E       Opgaver
11 E+F       Der er ingen timer (hverken F eller E) i uge 11 pga. underviseren er i udlandet. Næste kvartal starter i uge 15, hvor DM507 fortsætter.
15 F Tirsdag 9/4 10-12 U20 Hashing (afsnit 11.1-4 [dog ikke siderne 265-268 og 274-276], slides). Start på Divide and Conquer (afsnit 4.0 og 4.4 slides).
15 E       Opgaver
16 F Tirsdag 16/4 10-12 U20 Mere om analyse af Divide and Conquer algoritmer med rekursionstræer og Master Theorem (afsnit 4.4-5). Læs også kommentaren om forholdet mellem de to analysemetoder på sedlen med opgaver til Uge 16.
16 F Onsdag 17/4 12-14 U20 Mere om Master Theorem (afsnit 4.5). Strassens algoritme (afsnit 4.2).
16 E       Opgaver
17 F Tirsdag 23/4 10-12 U20 Feedback på projektet, del I. 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.
17 E       Opgaver
18 F Tirsdag 30/4 10-12 U20 Afslutning på grådige algoritmer (afsnit 16.3, slides). Start på dynamisk programmering (afsnit 15.1, slides).
18 F Onsdag 1/5 12-14 U20 Flere eksempler på dynamisk programmering (afsnit 15.2-4, slides). Udlevering og diskussion af Projekt, del II. Tilhørende filer: BitInputStream.java, BitOutputStream.java, Test.java.
18 E       Opgaver
19 F Tirsdag 7/5 10-12 U20 Grafer og grafgennemløb, DAGs og topologisk sorting (afsnit 22.1-4, slides).
19 E       Opgaver
20 F Tirsdag 14/5 10-12 U20 Minimum udspændende træer (kapitel 23, slides).
20 F Onsdag 15/5 12-14 U20 Datastrukturer for disjoint sets (afsnit 21.1-3, slides).
20 E       Opgaver
21 F Tirsdag 21/5 10-12 U20 Korteste veje (kapitel 24, afsnit 25.2 slides).
21 E       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)