DM507/DM578/DS814/SE4-DMAD Algoritmer og datastrukturer

Forår 2024
Rolf Fagerberg


Generel information

Kurset starter torsdag den 1. februar og slutter fredag den 24. maj.

Timer

Hvis tid eller sted er angivet med rødt, er det for at henlede opmærksomheden på, at placeringen afviger fra det normale.

Uge Type Dato Tid Lokale Indhold
5 F Torsdag 1/2 08-10 U1 Introduktion til kurset (slides, kapitel 1 i lærebogen [3. udgave: kapitel 1]).

Optagelse af online forelæsning 2021 (introduktion til kursus) (NB: detaljerne om kursets struktur er en smule ændret, se slides ovenfor i stedet).

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

Optagelse af online forelæsning 2021 (ombytningspuslespil).

Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 1.1, 1.4 og 1.8.

6 F Tirsdag 6/2 10-12 U55 Om algoritmeanalyse (dele af afsnit 2.2 i lærebogen [3. udgave: dele af afsnit 2.2], slides).

Start på sorteringsalgoritmer: Insertionsort (side 157-160 i lærebogen [3. udgave: side 147-150], afsnit 2.1-2.2 i lærebogen [3. udgave: afsnit 2.1-2.2], side 1-6 i slides). Vi vender tilbage til begrebet "Invariant" lidt senere i kurset - de dele af teksten, som snakker om dette, kan indtil videre læses let.

Optagelse af online forelæsning 2021 (insertionsort).

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

6 F Torsdag 8/2 08-10 U1 Mere om sorteringsalgoritmer: Selectionsort, Mergesort (afsnit 2.3 i lærebogen [3. udgave: afsnit 2.3], side 7-13 i slides). Vi vender tilbage til begrebet "Divide and Conquer" lidt senere i kurset - de dele af teksten, som snakker om dette, kan indtil videre læses let.

Asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1], slides, Java-programmerne fra slides: Linear.java, Quadratic.java, Cubic.java). Det kan være en fordel at orientere sig i afsnit 3.3 i lærebogen [3. udgave: afsnit 3.2] hvis der i kurset bruges matematiske formler, definitioner og metoder, man har glemt.

Optagelse af online forelæsning 2021 (selectionsort, merge). Optagelse af online forelæsning 2021 (mergesort, asymptotisk analyse).

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

6 E       Opgaver.
7 F Tirsdag 13/2 10-12 U55 Afslutning af asymptotisk analyse (afsnit 3.1-2 i lærebogen [3. udgave: afsnit 3.1], slides, tidsTabelBeregninger.py).

Optagelse af online forelæsning 2021 (samme som i torsdags).

7 E       Opgaver.
8 F Tirsdag 20/2 10-12 U1 Et eksempel på at forskellige algoritmer for samme beregningsproblem kan have meget forskellige køretider: the maximum sub-array problem (slides, wikipedia, MaxSum1.py, MaxSum1.java, MaxSum2.py, MaxSum2.java, MaxSum3.py, MaxSum3.java). Optagelse af online forelæsning 2021 (maximum sum subarray).

Divide-and-conquer/rekursive algoritmer (side 34 i lærebogen [3. udgave: side 30], slides). Optagelse af online forelæsning 2021 (recursive algorithms).

Mergesort formuleret rekursivt (afsnit 2.3 i lærebogen [3. udgave: afsnit 2.3], side 14-15 i slides).

8 F Torsdag 22/2 08-10 U1

Flere sorteringsalgoritmer: Quicksort (afsnit 7.1-3 i lærebogen [3. udgave: afsnit 7.1-3], næste dele af slides).

Optagelse af online forelæsning 2021 (quicksort).

Flere sorteringsalgoritmer: Heapsort (afsnit 6.1-4 i lærebogen [3. udgave: afsnit 6.1-4], afsnit B.5.3 i lærebogen [3. udgave: afsnit B.5.3], sidste del af slides).

Optagelse af online forelæsning 2021 (heapsort).

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

8 E       Opgaver.
9 F Tirsdag 27/2 10-12 U55 Afslutning af Heapsort.

Nedre grænser for sammenligningsbaseret sortering (afsnit 8.1 i lærebogen [3. udgave: afsnit 8.1], 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)).

Flere sorteringsalgoritmer: sortering af heltal med Countingsort og Radixsort (afsnit 8.2-3 i lærebogen [3. udgave: afsnit 8.2-3], 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 side 5-6 i disse slides.

Optagelse af online forelæsning 2021 (nedre grænser for sortering, Countingsort og Radixsort).

Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 8.6.

Start på prioritetskøer (side 175-176 i lærebogen [3. udgave: side 164], slides side 8-9).

9 E       Opgaver.
10 F Tirsdag 5/3 10-12 U55 Afslutning af prioritetskøer (afsnit  6.5 i lærebogen [3. udgave: afsnit  6.5], slides).

[NB: Det antages i dette kursus, at man allerede er bekendt med de simple datastrukturer lænket liste, stak og , f.eks. fra ens programmeringskursus. I modsat fald, læs afsnit 10.1-2 i lærebogen [3. udgave: afsnit 10.1-2].]

Optagelse af online forelæsning 2021 (prioritetskøer).

Forslag til yderligere videomateriale (ikke pensum): Mifta Sintaha, Tim Roughgarden, Stanford, afsnit 12.1-3 [bemærk at de enkelte heap-operationer ikke nødvendigvis hedder det samme som i bogen].

Start på dictionaries og deres implementation via binære søgetræer (side 249-251 i lærebogen [3. udgave: side 229-231], afsnit 10.3 (mest figur 10.6) i lærebogen [3. udgave: afsnit 10.4 (mest figur 10.9)], afsnit 12.1 i lærebogen [3. udgave: afsnit 12.1], første del af slides).

Optagelse af online forelæsning 2021 (binære søgetræer).

Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 13.1-2 samt 13.3 indtil 22:00.

Udlevering af projektet, del I (kun for DM507 og DS814).

10 F Torsdag 7/3 08-10 U1 Mere om projekt I: Gennemgang af krav til afleveringen. Redirection af standard input og output (relevant viden for alle). Optagelse af online forelæsning 2021 (udlevering af projekt del I). Optagelse af online forelæsning 2021 (redirection).

Mere om binære søgetræer (afsnit 12.2-3 i lærebogen [3. udgave: afsnit 12.2-3], næste del af slides).

Optagelse af online forelæsning 2021 (binære søgetræer).

10 E       Opgaver.
10 F Tirsdag 12/3 10-12 U55 Rød-sorte træer (afsnit 13.1-4 i lærebogen [3. udgave: afsnit 13.1-4], næste del af slides).

Implementation af dictionaries via hashing (afsnit 11.1-4 i lærebogen, dog ikke: siderne 278-281, beviset for corollary 11.3, afsnit 11.3.3-1.3.5 og siderne 297 (midt) til 300 [3. udgave: afsnit 11.1-4, dog ikke: siderne 258-260, 266-268 og 274-276], slutningen af slides).

Optagelse af online forelæsning 2021 (rød-sorte træer). Optagelse af online forelæsning 2021 (sletning i rød-sorte træer, hashing). Optagelse af online forelæsning 2021 (repetition af hashing).

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.

Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 13.4-6. Tim Roughgarden, Stanford, afsnit 14.1-3 og 15.1.

11 E       Opgaver.
12 F Tirsdag 19/3 10-12 U55 Afslutning af hashing (læsning: som sidst).

Dekoration af binære søgetræer (afsnit 17.1-2 i lærebogen [3. udgave: afsnit 14.1-2], slides).

Optagelse af online forelæsning 2021 (dekoration af binære søgetræer).

Forslag til yderligere videomateriale (ikke pensum): Tim Roughgarden, Stanford, afsnit 13.3 fra 22:00.

12 F Torsdag 21/3 08-10 U1 Invarianter (siderne 20-21, 167-168, 184 og 340-345 i lærebogen [3. udgave: siderne 18-20, 32-33, 157, 171-173 og 318-322], slides).

Divide and Conquer algoritmer, rekursionsligninger, og analyse heraf via rekursionstræer og via Master Theorem (afsnit 4.0, 4.4 og 4.5 i lærebogen [3. udgave: afsnit 4.0, 4.4 og 4.5 (bemærk at i 3. udgave er case 2 i Master Theorem en smule mindre generel end i 4. udgave)], slides side 1-20).

Optagelse af online forelæsning 2021 (invarianter). Optagelse af online forelæsning 2021 (rekursionsligninger). Bemærk at i 4. udgave er case 2 i Master Theorem en smule mere generel end i 3. udgave, som denne online forelæsning referer til).

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 mindre generel end lærebogens, og at rækkefølgen af cases er forskellig].

12 E       Opgaver.
14 F Tirsdag 2/4 10-12 U1 Mere om rekursionstræsmetoden og Master Theorem (afsnit 4.0, 4.4 og 4.5 i lærebogen [3. udgave: afsnit 4.0, 4.4 og 4.5 (bemærk at i 3. udgave er case 2 i Master Theorem en smule mindre generel end i 4. udgave)], slides side 21-34)

En berømt Divide and Conquer algoritme: Strassens algoritme for matrix-multiplikation (afsnit 4.2 i lærebogen [3. udgave: afsnit 4.2], slides).

Udlevering af projektet, del II (kun for DM507 og DS814).

Optagelse af online forelæsning 2021 (mere om rekursionsligninger, Strassens algoritme).

Optagelse af online forelæsning 2021 (gennemgang af projekt del II). Bemærk at implementationen af træer via klasser nu er den beskrevne metode i projektteksten (fremfor en mulighed nævnt i en fodnote i 2021). Metoden fra 2021 med implementation via lister må sådan set gerne bruges, men efter mine informationer har alle nu lært om klasser i deres Python programmeringskursus.

Forslag til yderligere videomateriale (ikke pensum): 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).

For en slags forgænger (og mulig inspiration) til Strassens algoritme, se Karatsubas rekursive algoritme (1962) til multiplikation af tal (ikke pensum).

14 E       Opgaver.
15 F Tirsdag 9/4 10-12 U55 Dynamisk programmering (afsnit 14.1 i lærebogen [3. udgave: afsnit 15.1], slides).

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

Optagelse af online forelæsning 2021 (dynamisk programmering).

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

15 F Torsdag 11/4 08-10 U1 Mere om dynamisk programmering (afsnit 14.4 og 14.2 i lærebogen [3. udgave: afsnit 15.4 og 15.2], slides).

Optagelse af online forelæsning 2021 (mere om dynamisk programmering), optagelse af online forelæsning 2021 (endnu mere om dynamisk programmering).

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

15 E       Opgaver.
16 F Tirsdag 16/4 10-12 U55 Grådige algoritmer (afsnit 15.1-3 i lærebogen [3. udgave: afsnit 16.1-3], slides).

NB: afsnit 15.1 og første del af 15.2 [3. udgave: afsnit 16.1 og første del af 16.2] er ret langstrakt, og refererer nogle gange til dynamisk programmering (kapitlet før) - læs disse sider let, og fokuser på slides.

Optagelse af online forelæsning 2021 (grådige algoritmer).

16 E       Opgaver.
17 F Tirsdag 23/4 10-12 U55 Multiple-choice test (25 minutter) i klassen (kan findes i ITS under Ressourcer som MC test 1).

Bevis for korrekthed af Huffmans algoritme (afsnit 15.3 i lærebogen, [3. udgave: afsnit 16.3], slutningen af slides)

Datastrukturer for disjoint sets (afsnit 19.1-3 i lærebogen [3. udgave: afsnit 21.1-3], slides).

Optagelse af online forelæsning 2021 (disjoint sets),

17 F Torsdag 25/4 08-10 U1 Afslutningen af datastrukturer for disjoint sets (afsnit 19.1-3 i lærebogen [3. udgave: afsnit 21.1-3], slides).

Start på grafalgoritmer: repræsentation af grafer (afsnit 20.1 i lærebogen [3. udgave: afsnit 22.1], side 1-6 i slides). Derudover er de første to sider af appendiks B.4 i lærebogen om basal terminologi for grafer overladt til selvstændig læsning.

Optagelse af online forelæsning 2021 (mere om disjoint sets). Optagelse af online forelæsning 2021 (start på grafalgoritmer).

Udlevering af projektet, del III (kun for DM507 og DS814).

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

17 E       Opgaver.
18 F Tirsdag 30/4 10-12 U55 Grafgennemløb: BFS, DFS (afsnit 20.2-3 i lærebogen [3. udgave: afsnit 22.2-3], side 7-27 i slides).

Mere om projektet, del III (kun for DM507 og DS814).

Optagelse af online forelæsning 2021 (grafgennemløb, BSF). Optagelse af online forelæsning 2021 (DFS).

Optagelse af online forelæsning 2021 (gennemgang af projekt del III). Optagelse af online forelæsning 2021 (mere gennemgang af projekt del III).

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

18 E       Opgaver.
19 F Tirsdag 7/5 10-12 U55 Multiple-choice test (30 minutter) i klassen (kan findes i ITS under Ressourcer som MC test 2).

DAGs, topologisk sorting (afsnit 20.4 i lærebogen [3. udgave: afsnit 22.4], resten af slides)

Sammenhængskomponenter (CC) i uorienterede grafer og stærke sammenhængskomponenter (SCC) i orienterede grafer (side 1166 (øverste halvdel) og side 576-580 i lærebogen [3. udgave: side 1170-71 og 615-20], slides).

Optagelse af online forelæsning 2021 (DAGs, CC og SCC). Optagelse af online forelæsning 2021 (bevis for SCC algoritmen).

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

19 F Onsdag 8/5 16-18 U55 Minimum Udspændende Træer, Prim-Jarniks algoritme. (kapitel 21 i lærebogen [3. udgave: kapitel 23], slides).

Optagelse af online forelæsning 2021 (Prim).

19 E       Opgaver.
20 F Tirsdag 14/5 10-12 U55 Afslutning af Minimum Udspændende Træer: Kruskals algoritme. (kapitel 21 i lærebogen [3. udgave: kapitel 23], slides).

Optagelse af online forelæsning 2021 (Kruskal).

Korteste veje, single source: Dijkstras algoritme (afsnit 22.0, 22.3 og 22.5 i lærebogen [3. udgave: afsnit 24.0, 24.3 og 24.5], første del af slides). Shortest paths på DAGs, Bellman-Fords algoritme (afsnit 22.2 og 22.1 i lærebogen [3. udgave: afsnit 24.2 og 24.1], midterste del af slides).

Optagelse af online forelæsning 2021 (korteste veje).

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

20 E       Opgaver.
21 F Tirsdag 21/5 10-12 U55 Afslutning af korteste veje, single source: beviser for korrekthed af algoritmerne fra sidst: Dijkstras, DAGs, Bellman-Ford (afsnit 22.0, 22.3, 22.5, 22.2 og 22.1 i lærebogen [3. udgave: afsnit 24.0, 24.3, 24.5, 24.2 og 24.1], første og midterste del af slides).

Relation mellem Dijkstra og A*-algoritmen. A*-algoritmen er ikke pensum (og nævnes ikke i lærebogen), men er kendt af nogle deltagere fra andre kurser, hvorfor dens relation til Dijkstra nævnes her.

Korteste veje, all-pairs: Floyd-Warshalls algoritme, Johnsons algoritme (afsnit 23.0 og 23.2-3 i lærebogen [3. udgave: afsnit 25.0 og 25.2-3], sidste del af slides). Johnsons algoritme er ikke pensum.

Optagelse af online forelæsning 2021 (korteste veje).

For oprindelsen/betydningen af navnet "A*", se A* Search: What's in a Name? af James W. Davis og Jeff Hachtel, Communications of the ACM, Januar 2020, Vol. 63 No. 1, side 36-37 (ikke pensum).

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

21 E       Opgaver.


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