DM507 Algoritmer og datastrukturer

Forår 2017
Rolf Fagerberg


Kurset starter onsdag den 8. februar og slutter fredag den 26. maj.

Den skriftlige eksamen finder sted tirsdag den 6. juni.

Timer

Uge Type Dato Tid Lokale Indhold
6 I Onsdag 8/2 10-12 U140 Introduktion til kurset (slides, kapitel 1 i lærebogen). Eksempel på algoritmeanalyse: Ombytningspuslespil (slides, noter). Et ombytningspuslespil fra nettet. Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 1.1, 1.4 og 1.8.
6 I Torsdag 9/2 08-10 U140 Sorteringsalgoritmer: Insertionsort, Mergesort (side 147-150 i lærebogen, afsnit 2.1-3 i lærebogen, side 1-12 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, afsnit 1.5-7.
6 TE       Opgaver
7 I Onsdag 15/2 10-12 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, 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, afsnit 2.1-4 (evt. også 2.5 for ekstra eksempler).
7 TE       Opgaver
8 I Onsdag 22/2 10-12 U140 Flere sorteringsalgoritmer: Heapsort. (afsnit 6.1-4 i lærebogen, B.5.3 i lærebogen, sidste del af slides). Forslag til videomateriale: Mifta Sintaha, fra start til slut (14:42).
8 I Torsdag 23/2 08-10 U140 Prioritetskøer (afsnit  6.5 i lærebogen, slides). Forslag til videomateriale: Tim Roughgarden, Stanford, 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, Heapsort.java, Testfiler.zip.
8 TE       Opgaver
9 I Onsdag 1/3 10-12 U140 Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1 i lærebogen, start af slides, eksempler på decisiontrees for insertionsort (n=1,2,3,4,5,6,7), mergesort (n=1,2,3,4,5,6,7)) og heapsort (n=1,2,3,4,5,6,7)). Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 8.6. Flere sorteringsalgoritmer: sortering af heltal med Countingsort og Radixsort (afsnit 8.2-3 i lærebogen, anden del af slides). For at forstå sidste side af slides om Radixsort, skal man kende det binære talsystem. Gør man ikke det, så check første halvdel af disse slides. 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-2 i lærebogen, første del af slides. Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 13.1-2 samt 13.3 indtil 14:15.
9 TE       Opgaver
10 I Onsdag 8/3 10-12 U140 Indsættelser og sletninger i binære søgetræer (afsnit 12.3 i lærebogen, de næste par sider af slides. Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 13.3 fra 14:15 indtil 22:00. Start på rød-sorte træer (kapitel 13 i lærebogen, midten af slides). Forslag til videomateriale: Tim Roughgarden, Stanford, 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.
10 I Torsdag 9/3 08-10 U140 Afslutning af rød-sorte træer (kapitel 13 i lærebogen, midten af slides). Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 13.4-6. 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, afsnit 14.1-3 og 15.1.
10 TE       Opgaver
11 I Onsdag 15/3 10-12 U140 Dekoration af binære søgetræer (afsnit 14.1-2 i lærebogen, slides). Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 13.3 fra 22:00. Udlevering og diskussion af Projekt, del II. Tilhørende Java.filer: Dict.java, TestProjectPartII.java. Invarianter (siderne 18-20, 32-33, 157, 171-173 og 318-322 i lærebogen, slides).
11 TE       Opgaver
12 I Onsdag 22/3 10-12 U140 Divide and Conquer algoritmer, rekursionsligninger, og analyse heraf via rekursionstræer (afsnit 4.0 og 4.4 i lærebogen, slides). Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 4.1.
12 I Torsdag 23/3 12-14 U140 Flere eksempler på analyse af Divide and Conquer algoritmer via rekursionstræer, samt via Master Theorem (afsnit 4.4 og 4.5 i lærebogen, slides). Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 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, og at rækkefølgen af cases er forskellig].
12 TE       Opgaver
13 I Onsdag 29/3 10-12 U140 Eksempler på analyse af Divide and Conquer algoritmer via rekursionstræer, når Master Theorem ikke kan bruges. 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, afsnit 3.3. Feedback på projekt, del I (slides).
13 TE       Opgaver
14 I Onsdag 5/4 10-12 U140 Midtvejsevaluering. Dynamisk programmering (afsnit 15.1-2 i lærebogen, slides, afsnit 15.4 i lærebogen, slides). Forslag til videomateriale: Dan Suthers, University of Hawaii, Dan Suthers, University of Hawaii, Dan Suthers, University of Hawaii.
14 I Torsdag 6/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. Udlevering og diskussion af Projekt, del III. Tilhørende filer: to biblioteksfunktioner BitInputStream.java, BitOutputStream.java, samt et eksempel på brug af dem Test.java (læs kommentarer i programmet).
14 TE       Opgaver
15 I+TE       Bemærk: der er ingen timer (hverken I eller TE) i uge 15 pga. påske.
16 I Onsdag 19/4 10-12 U140 Lidt mere diskussion af projektet, del III. Bevis for optimalitet af Huffmankodning (afsnit 16.3 i lærebogen, sidste del af slides).
16 TE       Opgaver
17 I Onsdag 26/4 10-12 U140 Feedback på midtvejsevaluering (slides). Datastrukturer for disjoint sets (afsnit 21.1-3 i lærebogen, slides).
17 I Torsdag 27/4 08-10 U140 Feedback på projekt del II (slides). 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, afsnit 9.2 og 10.1-3.
17 TE       Opgaver
18 I Onsdag 3/5 10-12 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, afsnit 10.4-6.
18 TE       Opgaver
19 I Onsdag 10/5 10-12 U140 Sammenhængskomponenter (i uorienterede grafer) og stærke sammenhængskomponenter (i orienterede grafer) (side 1170-71 og 615-17 i lærebogen, slides). Start på minimum udspændende træer (kapitel 23 i lærebogen, slides).
19 I Torsdag 11/5 12-14 U140 Minimum udspændende træer (kapitel 23 i lærebogen, slides).
19 TE       Opgaver
20 I Onsdag 17/5 10-12 U140 Korteste veje, single source, all-pairs. (afsnit 24.0-4 i lærebogen, afsnit 25.2 i lærebogen, slides. Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 11.1-4.
20 TE       Opgaver
21 I       De skemalagte forelæsninger i uge 21 afholdes ikke, da vi er blevet færdig med pensum.
21 TE       Opgaver


Maintained by Rolf Fagerberg (rolf@imada.sdu.dk)