DM507 Algoritmer og datastrukturer

Forår 2019
Rolf Fagerberg

Generel information

Kurset starter mandag den 4. februar og slutter fredag den 24. maj.

Den skriftlige eksamen finder sted fredag den 21. juni. Tider og lokaler kan findes på kursets Blackboard-side.

Der vil være en spørgetime onsdag 19. juni kl. 15:15 i U82. Medbring spørgsmål til pensum og til løsning af konkrete opgaver (f.eks. gamle eksamensopgaver).

Datoen for reeksamen er torsdag den 29. august, 2019. Reeksamen er mundtlig. Listen af emner man kan trække samt andre oplysninger kan findes her. Der afholdes en spørgetime før reeksamen tirsdag den 27. august kl. 15:15 til 16:00 i U176.

Projektet

Timer

Uge Type Dato Tid Lokale Indhold
6 I Mandag 4/2 16-18 U55 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 Fredag 8/2 10-12 U55 Start på sorteringsalgoritmer: Insertionsort, Mergesort (side 147-150 i lærebogen, afsnit 2.1-3 i lærebogen, side 1-12 i slides). Vi vender 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.

Disse timer forelæses af Kim Skak Larsen.

6 TE       Opgaver
7 I Onsdag 13/2 08-10 U1 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).

Rekursive algoritmer (side 30 i lærebogen, slides).

Disse timer forelæses af Kim Skak Larsen.

7 TE       Opgaver
8 I Onsdag 20/2 08-10 U1 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.
8 I Fredag 22/2 10-12 U55 Heapsort (afsnit 6.1-4 i lærebogen, B.5.3 i lærebogen, sidste del af slides). Forslag til videomateriale: Mifta Sintaha.
8 TE       Opgaver
9 I Onsdag 27/2 08-10 U1 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 diskusson af Projekt, del I. Tilhørende Java.filer: PQ.java, Element.java, Heapsort.java, Testfiler.zip.

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.

9 TE       Opgaver
10 I Onsdag 6/3 08-10 U1 Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1 i lærebogen, første del 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.
10 I Fredag 8/3 10-12 U55 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-3 i lærebogen, første del af slides. Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 13.1-2 samt 13.3 indtil 22:00.

Rød-sorte træer (kapitel 13 i lærebogen, midten af slides (sletninger gennemgås dog først næste gang)). 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 TE       Opgaver
11 I Onsdag 13/3 08-10 U1 Multiple-choice test (25 minutter) i klassen (kan findes i Blackboard under E-test som MC test 1).

Sletning i rød-sorte træer (afsnit 13.4 i lærebogen).

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.

11 TE       Opgaver
12 I Onsdag 20/3 08-10 U1 Udlevering og diskussion af Projekt, del II. Tilhørende Java.filer: Dict.java, TestProjectPartII.java.

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.

Invarianter (siderne 18-20, 32-33, 157, 171-173 og 318-322 i lærebogen, slides).

12 TE       Opgaver
12 I Fredag 22/3 10-12 U55 Divide and Conquer algoritmer, rekursionsligninger, og analyse heraf via rekursionstræer (afsnit 4.0 og 4.4 lærebogen, slides). Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 4.1 [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].
13 I Onsdag 27/3 08-10 U1 Tilbagelevering og feedback på projekt, del I.

Analyse af Divide and Conquer algoritmer 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].

En berømt 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.

For en historisk gennemgang af udviklingen i køretid for algoritmer for matrix-multiplikation, se denne wikipedia side (ikke pensum).

13 TE       Opgaver
14 I Onsdag 3/4 08-10 U1 Dynamisk programmering (afsnit 15.1-2 i lærebogen, slides. Forslag til videomateriale: Dan Suthers, University of Hawaii, Dan Suthers, University of Hawaii, Dan Suthers, University of Hawaii.

Bellmans forklaring om historien bag navnet Dynamisk Programmering (ikke pensum).

14 I Fredag 5/4 14-16 U55 Midtvejsevaluering af kurset.

Mere om dynamisk programmering (afsnit 15.4 i lærebogen, slides).

14 TE       Opgaver
15 I Onsdag 10/4 08-10 U1 Grådige algoritmer (afsnit 16.1-3 i lærebogen, 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 III. Tilhørende filer: to biblioteksfunktioner BitInputStream.java, BitOutputStream.java, samt et eksempel på brug af dem Test.java (læs kommentarer i programmet).

15 TE       Opgaver. Tilhørende filer: to biblioteksfunktioner BitInputStream.java, BitOutputStream.java, samt et eksempel på brug af dem 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 24/4 08-10 U1 Multiple-choice test i klassen i opgaveteksten til projekt del III (15 minutter). Kan findes i Blackboard under E-test som MC test Projekt Del III.

Bevis for korrekthed af Huffmans algoritme (afsnit 16.3 i lærebogen, sidste del af slides).

Datastrukturer for disjoint sets (afsnit 21.1-3 i lærebogen, slides).

17 TE       Opgaver
17 I Fredag 26/4 10-12 U110 Multiple-choice test i klassen.

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.

18 I Onsdag 1/5 08-10 U1

Bevis for korrekthed af BFS gennemløb (afsnit 22.2 i lærebogen, første halvdel af slides)

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 8/5 08-10 U1 Tilbagelevering og feedback på projekt, del II.

Sammenhængskomponenter (i uorienterede grafer) og stærke sammenhængskomponenter (i orienterede grafer) (side 1170-71 og 615-17 i lærebogen, slides).

19 I Fredag 10/5 10-12 U55 Minimum udspændende træer (kapitel 23 i lærebogen, slides).
19 TE       Opgaver
20 I Onsdag 15/5 08-10 U1 Korteste veje, single source, all-pairs. (afsnit 24.0 til 24.3 i lærebogen, det meste af slides. Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 11.1-4.
20 TE       Opgaver
21 I Onsdag 22/5 08-10 U1 Afslutning af korteste veje, single source. Korteste veje, all-pairs. (afsnit 24.2-3 i lærebogen, afsnit 25.2-3 i lærebogen, slides. Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 11.1-4.
21 TE       Opgaver

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