DM507/DS814/T510040101 Algoritmer og datastrukturer

Forår 2021
Rolf Fagerberg


Generel information

Kurset starter mandag den 1. februar og slutter mandag den 25. maj.

Timer

Uge Type Dato Tid Lokale Indhold
5 F Tirsdag 2/2 08-10 Zoom mødelink Introduktion til kurset (slides, kapitel 1 i lærebogen).

Eksempel på algoritmeanalyse: Ombytningspuslespil (slides, noter). Et ombytningspuslespil fra nettet.

Optagelse af forelæsning. Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 1.1, 1.4 og 1.8.

5 F Torsdag 4/2 10-12 Zoom mødelink Start på sorteringsalgoritmer: Insertionsort, Selectionsort, Mergesort (side 147-150 i lærebogen, afsnit 2.1-3 i lærebogen, side 1-9 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.

Optagelse af forelæsning. Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 1.5-7.

5 E     Zoom mødelink Opgaver
6 F Tirsdag 9/2 08-10 Zoom mødelink Afslutning af Mergesort (side 147-150 i lærebogen, afsnit 2.1-3 i lærebogen, side 10-12 i slides).

Asymptotisk analyse (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.

Optagelse af forelæsning. Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 2.1-4 (evt. også 2.5 for ekstra eksempler).

6 E     Zoom mødelink Opgaver
7 F Tirsdag 16/2 08-10 Zoom mødelink Repetition af asymptotisk analyse (afsnit 3.1 i lærebogen, slides).

Et eksempel på at forskellige algoritmer for samme beregningsproblem kan have meget forskellige køretider: the maximum sub-array problem (wikipedia, MaxSum1.java, MaxSum2.java, MaxSum3.java).

Divide-and-conquer/rekursive algoritmer (side 30 i lærebogen, slides).

Optagelse af forelæsning.

7 F Torsdag 18/2 10-12 Zoom mødelink Flere sorteringsalgoritmer: Quicksort (afsnit 7.1-3 i lærebogen, næste dele af slides).

Optagelse af forelæsning. Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 5.1-4.

7 E     Zoom mødelink Opgaver
8 F Tirsdag 23/2 08-10 Zoom mødelink Flere sorteringsalgoritmer: Heapsort (afsnit 6.1-4 i lærebogen, B.5.3 i lærebogen, sidste del af slides).

Optagelse af forelæsning. Forslag til yderligere videomateriale (ikke pensum): Mifta Sintaha.

8 E     Zoom mødelink Opgaver
9 F Tirsdag 2/3 08-10 Zoom mødelink Prioritetskøer (afsnit  6.5 i lærebogen, slides). Forslag til yderligere videomateriale (ikke pensum): 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 projektet, del I (kun for DM507 og DS814). Java version: projektbeskrivelse, del I, PQ.java, Element.java, PQSort.java, Testfiler.zip. Python version: projektbeskrivelse, del I, PQSort.py, Testfiler.zip.

Optagelse af forelæsning.

9 F Torsdag 4/3 10-12 Zoom mødelink 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 yderligere videomateriale (ikke pensum): 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.

Optagelse af forelæsning.

9 E     Zoom mødelink Opgaver
10 F Tirsdag 9/3 08-10 Zoom mødelink 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). Optagelse af forelæsning. Forslag til yderligere videomateriale (ikke pensum): 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, screencast). Sletninger gennemgås næste gang. Forslag til yderligere videomateriale (ikke pensum): 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 E     Zoom mødelink Opgaver
11 F Tirsdag 16/3 08-10 Zoom mødelink Sletning i rød-sorte træer (afsnit 13.4 i lærebogen, side 14-15 og 27-31 i slides)).

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 yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 14.1-3 og 15.1.

Optagelse af forelæsning.

11 F Torsdag 18/3 10-12 Zoom mødelink Dekoration af binære søgetræer (afsnit 14.1-2 i lærebogen, slides). Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 13.3 fra 22:00.

Optagelse af forelæsning.

11 E     Zoom mødelink Opgaver
12 F Tirsdag 23/3 08-10 Zoom mødelink 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 og via Master Theorem (screencast, afsnit 4.0, 4.4 og 4.5 i lærebogen, slides side 1-20). Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 4.1, 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].

Optagelse af forelæsning.

Udlevering af projektet, del II (kun for DM507 og DS814). Java version: projektbeskrivelse, del II, Dict.java, optagelse af gennemgang af projektbeskrivelse. Python version: projektbeskrivelse, del II, optagelse af gennemgang af projektbeskrivelse.

12 E     Zoom mødelink Opgaver
14 F Tirsdag 6/4 08-10 Zoom mødelink Mere om rekursionstræsmetoden og Master Theorem (afsnit 4.0, 4.4 og 4.5 i lærebogen, slides side 21-30).

En berømt Divide and Conquer algoritme: Strassens algoritme for matrix-multiplikation (afsnit 4.2 i lærebogen, slides). Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 3.3.

Optagelse af forelæsning.

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

14 F Torsdag 8/4 10-12 Zoom mødelink Midtvejsevaluering af kurset.

Dynamisk programmering (afsnit 15.1-2 i lærebogen, slides, slide med tegninger fra forelæsning). Optagelse af forelæsning.

Forslag til yderligere videomateriale (ikke pensum): Dan Suthers, University of Hawaii.

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

14 E     Zoom mødelink Opgaver
15 F Tirsdag 13/4 08-10 Zoom mødelink Mere om dynamisk programmering (afsnit 15.4 i lærebogen, slides, slide med tegninger fra forelæsning). Optagelse af forelæsning.

Forslag til yderligere videomateriale (ikke pensum): Dan Suthers, University of Hawaii, Dan Suthers, University of Hawaii.

15 E     Zoom mødelink Opgaver

Tilhørende filer (Java): to biblioteksfunktioner BitInputStream.java, BitOutputStream.java, samt et eksempel på brug af dem Test.java (læs kommentarer i programmet).

Tilhørende filer (Python): biblioteket bitIO.py, samt et eksempel på brug af det test.py (læs kommentarer i programmet).

16 F Tirsdag 20/4 08-10 Zoom mødelink Grådige algoritmer (afsnit 16.1-3 i lærebogen, slides, slide med tegninger fra forelæsning). Optagelse af forelæsning. 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 af Projekt, del III (kun for DM507 og DS814).

Java version: projektbeskrivelse. tegneserieudgave af 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). En samling testfiler samt liste med angivelse af korrekt størrelse efter komprimering.

Python version: projektbeskrivelse. tegneserieudgave af del III. Tilhørende filer: bibliotek bitIO.py samt et eksempel på brug af det test.py (læs kommentarer i programmet), klassen Element.py samt et eksempel på brug af det PQSortElements.py (læs kommentarer i programmet). En samling testfiler samt liste med angivelse af korrekt størrelse efter komprimering.

16 F Torsdag 22/4 10-12 Zoom mødelink Bevis for korrekthed af Huffmans algoritme (afsnit 16.3 i lærebogen, sidste del af slides, slide med tegninger fra forelæsning).

Datastrukturer for disjoint sets (afsnit 21.1-3 i lærebogen, slides, slide med tegninger fra forelæsning).

Gennemgang af projektet, del III (tegneserieudgave af del III).

Optagelse af forelæsning.

16 E     Zoom mødelink Opgaver
17 F Tirsdag 27/4 08-10 Zoom mødelink 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.

Optagelse af forelæsning.

Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 9.2 og 10.1-2.

17 E     Zoom mødelink Opgaver
18 F Tirsdag 4/5 08-10 Zoom mødelink Bevis for BFS egenskaber, DFS grafgennemløb (afsnit 22.2-3 i lærebogen, slides).

Optagelse af forelæsning.

Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 10.3 og 10.5.

18 F Tirsdag 6/5 10-12 Zoom mødelink DAGs, topologisk sorting (afsnit 22.4 i lærebogen, slides). Sammenhængskomponenter i uorienterede grafer og stærke sammenhængskomponenter i orienterede grafer (side 1170-71 og 615-17 i lærebogen, slides, slide med tegninger fra forelæsning). Beviset for korrekthed af SCC algoritmen er ikke pensum.

Start på Minimum udspændende træer (kapitel 23 i lærebogen, slides).

Optagelse af forelæsning. Video med bevis for korrekthed af SCC algoritmen (ikke pensum).

Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 10.6, 10.4 og 10.7.

18 E     Zoom mødelink Opgaver
19 F Tirsdag 11/5 08-10 Zoom mødelink

Mere om Minimum udspændende træer, Prim-Jarniks algoritme, Kruskals algoritme (kapitel 23 i lærebogen, slides).

Optagelse af forelæsning, video-forelæsning om Kruskals algoritme.

19 E     Zoom mødelink Opgaver
20 F Tirsdag 18/5 08-10 Zoom mødelink

Korteste veje, single source: Bellman-Fords algoritme, Dijkstras algoritme, shortest paths på DAGs (afsnit 24.0 til 24.3 i lærebogen, første del af slides). Korteste veje, all-pairs: Floyd-Warshalls algoritme, Johnsons algoritme (afsnit 25.0 og 25.2-3 i lærebogen, sidste del af slides.

Optagelse af forelæsning.

Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 11.1-4.

20 E     Zoom mødelink Opgaver


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