DM507 Algoritmer og datastrukturer

Forår 2018
Rolf Fagerberg


Kurset starter tirsdag den 6. februar og slutter fredag den 25. maj.

Den skriftlige eksamen finder sted fredag den 22. juni.

Timer

Uge Type Dato Tid Lokale Indhold
6 I Tirsdag 6/2 14-16 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 Fredag 9/2 08-10 U1 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 Tirsdag 13/2 14-16 U140 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 Lene Monrad Favrholdt.
7 TE       Opgaver
8 I Mandag 19/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 23/2 08-10 U45 Start på Heapsort (afsnit 6.1-4 i lærebogen, B.5.3 i lærebogen, sidste del af slides). Forslag til videomateriale: Mifta Sintaha. 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 af Projekt, del I. Tilhørende Java.filer: PQ.java, Element.java, Heapsort.java, Testfiler.zip.
8 TE       Opgaver
9 I Tirsdag 27/2 14-16 U1 Diskussion af Projekt, del I. 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.
9 TE       Opgaver
10 I Tirsdag 6/3 14-16 U140 Multiple-choice test i klassen (kan findes i Blackboard under E-test som MC test 1). 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.
10 I Fredag 9/3 08-10 U45 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 TE       Opgaver
11 I Tirsdag 13/3 14-16 U1

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. 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.

11 TE       Opgaver
12 I Tirsdag 20/3 14-16 U1 Invarianter (siderne 18-20, 32-33, 157, 171-173 og 318-322 i lærebogen, slides). 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 Fredag 23/3 08-10 U45 Feedback på projekt, del I (slides). 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+TE       Bemærk: der er ingen timer (hverken I eller TE) i uge 13 pga. påske.
14 I Tirsdag 3/4 14-16 U140 Eksempler på analyse af Divide and Conquer algoritmer via rekursionstræer, når Master Theorem ikke kan bruges. Midtvejsevaluering. 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. For the historical development of the running time of the asymptotically best matrix multiplication algorithm, see this wiki page.
14 TE       Opgaver
15 I Mandag 9/4 12-14 U140 Dynamisk programmering (afsnit 15.1-2 i lærebogen, slides, afsnit 15.4 i lærebogen, første del af 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.
15 I Tirsdag 10/4 14-16 U140 Mere om dynamisk programmering (afsnit 15.4 i lærebogen, anden del af slides). Grådige algoritmer (afsnit 16.1-2 i lærebogen, første del af 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 TE       Opgaver
16 I Tirsdag 17/4 10-12 U140 Mere om grådige algoritmer: Huffmans algoritme (afsnit 16.1-3 i lærebogen, sidste del af slides). Udlevering og diskussion af Projekt, del III. Multiple-choice test i klassen (kan findes i Blackboard under E-test som MC test 2). 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).
16 TE       Opgaver
17 I Mandag 23/4 12-14 U55 Lidt mere om projektet, 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 I Onsdag 25/4 16-18 U55 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 Fredag 4/5 08-10 U45 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 Tirsdag 8/5 14-16 U1 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). Disse timer forelæses af Lene Monrad Favrholdt.
19 TE       Opgaver
20 I Mandag 14/5 10-12 U140 Mere om minimum udspændende træer (kapitel 23 i lærebogen, resten af slides).
20 I Torsdag 17/5 08-10 U110 Korteste veje, single source, all-pairs. (afsnit 24.0-1 og 24.3 i lærebogen, slides. Forslag til videomateriale: Tim Roughgarden, Stanford, afsnit 11.1-4.
20 TE       Opgaver
20 I Torsdag 24/5 08-10 U110 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)