DM507 Algoritmer og datastrukturer

Forår 2017
Rolf Fagerberg


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

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 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, 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]. Flere sorteringsalgoritmer: sortering af heltal med Countingsort og Radixsort (afsnit 8.2-3 i lærebogen, anden del af slides).


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