DM507 Algoritmer og datastrukturer
Forår 2013
Rolf Fagerberg
Kurset starter tirsdag den 29. januar. Det kører i 3. og 4. kvartal
2013.
Der er spørgetime fredag 21. juni, 12:15-14:00 i
U20. Vi vil bla. regne
eksamenssættet for F12.
Eksamensdatoen er mandag 24. juni. Her er
eksamensættet samt
vejledende løsninger.
Eksamenskaraktererne fordelte sig på følgende
måde.
Datoen for reeksamen er tirsdag den 20. august, 2013. Reeksamen er
mundtlig. Eksamensspørgsmålene og andre oplysninger kan findes
her.
Timer
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 5 |
F |
Tirsdag 29/1 |
10-12 |
U20 |
Introduktion til kurset (slides). Eksempel
på algoritmeanalyse: Jul i Valhalla (Gerth Brodal:
slides, noter, applet). |
| 5 |
F |
Onsdag 30/1 |
12-14 |
U20 |
Asymptotisk notation (afsnit 3.1,
slides, Java-programmerne fra
slides: Linear.java,
Quadratic.java,
Cubic.java). Start på sorteringsalgoritmer:
Insertionsort (afsnit 2.1-2, slides). Det kan
være en fordel at orientere sig i afsnit 3.2 hvis der i kurset bruges
matematiske formler, definitioner og metoder, man har glemt. Derudover:
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. |
| 5 |
E |
|
|
|
Opgaver |
| 6 |
F |
Tirsdag 5/2 |
10-12 |
U20 |
Flere sorteringsalgoritmer: Mergesort, Quicksort (afsnit 2.3, 7.1-3,
side 147-150, slides). |
| 6 |
E |
|
|
|
Opgaver |
| 7 |
F |
Tirsdag 12/2 |
10-12 |
U20 |
Mere om sorteringsalgoritmer: Heapsort, nedre grænser for sortering
(afsnit 6.1-4, B.5.3, 8.1, slides,
slides). |
| 7 |
F |
Onsdag 13/2 |
12-14 |
U20 |
Sortering af heltal: Counting sort, Radixsort (afsnit 8.2-3,
slides). Prioritetskøer
(afsnit 6.5, slides). Invarianter (side 18-20,
32-33, 157, 171-173), slides).
|
| 7 |
E |
|
|
|
Opgaver |
| 8 |
F |
Tirsdag 19/2 |
10-12 |
U20 |
Udlevering og diskussion af Projekt, del
I (tilhørende Java.filer: PQ.java,
Element.java, Dict.java). Bevis
for at BuildHeap tager linear tid. Start på dictionaries og deres
implementation via binære søgetræer (side 229-230, afsnit 10.4,
afsnit 12.1-2, slides). |
| 8 |
E |
|
|
|
Opgaver |
| 9 |
F |
Tirsdag 26/2 |
10-12 |
U20 |
Invarianter igen (slides). Mere om
dictionaries: indsætning og sletning i binære søgetræer (afsnit 12.3,
slides)).
|
| 9 |
F |
Onsdag 27/2 |
12-14 |
U20 | Mere om
dictionaries: rød-sorte træer (kapitel 13.1-3,
slides). Bemærk at bogen er ret tung
læsning i kapitel 13. Det skyldes dels, at bogens 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 (se
slides om invarianter), 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 bogen. |
| 9 |
E |
|
|
|
Opgaver |
| 10 |
F |
Tirsdag 5/3 |
10-12 |
U20 |
Mere om dictionaries: Sletning i rød-sorte træer (afsnit 13.4,
slides). Dekoration af binære søgetræer
(afsnit 14.1-2, slides).
|
| 10 |
E |
|
|
|
Opgaver |
| 11 |
E+F |
|
|
|
Der er ingen timer (hverken F eller E) i uge 11 pga. underviseren er
i udlandet. Næste kvartal starter i uge 15, hvor DM507 fortsætter.
|
| 15 |
F |
Tirsdag 9/4 |
10-12 |
U20 |
Hashing (afsnit 11.1-4 [dog ikke siderne 265-268 og 274-276],
slides). Start på Divide and Conquer
(afsnit 4.0 og 4.4 slides).
|
| 15 |
E |
|
|
|
Opgaver |
| 16 |
F |
Tirsdag 16/4 |
10-12 |
U20 |
Mere om analyse af Divide and Conquer algoritmer med rekursionstræer og
Master Theorem (afsnit 4.4-5). Læs også kommentaren om forholdet mellem
de to analysemetoder på sedlen med opgaver til
Uge 16.
|
| 16 |
F |
Onsdag 17/4 |
12-14 |
U20 |
Mere om Master Theorem (afsnit 4.5). Strassens algoritme (afsnit 4.2).
|
| 16 |
E |
|
|
|
Opgaver |
| 17 |
F |
Tirsdag 23/4 |
10-12 |
U20 |
Feedback på projektet,
del I. Grådige algoritmer (afsnit 16.1-3,
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.
|
| 17 |
E |
|
|
|
Opgaver |
| 18 |
F |
Tirsdag 30/4 |
10-12 |
U20 |
Afslutning på grådige algoritmer (afsnit 16.3,
slides). Start på dynamisk programmering
(afsnit 15.1, slides).
|
| 18 |
F |
Onsdag 1/5 |
12-14 |
U20 |
Flere eksempler på dynamisk programmering (afsnit 15.2-4,
slides). Udlevering og diskussion
af Projekt, del II. Tilhørende filer:
BitInputStream.java,
BitOutputStream.java,
Test.java.
|
| 18 |
E |
|
|
|
Opgaver |
| 19 |
F |
Tirsdag 7/5 |
10-12 |
U20 |
Grafer og grafgennemløb, DAGs og topologisk sorting (afsnit 22.1-4,
slides).
|
| 19 |
E |
|
|
|
Opgaver |
| 20 |
F |
Tirsdag 14/5 |
10-12 |
U20 |
Minimum udspændende træer (kapitel 23, slides).
|
| 20 |
F |
Onsdag 15/5 |
12-14 |
U20 |
Datastrukturer for disjoint sets (afsnit 21.1-3,
slides).
|
| 20 |
E |
|
|
|
Opgaver |
| 21 |
F |
Tirsdag 21/5 |
10-12 |
U20 |
Korteste veje (kapitel 24, afsnit 25.2
slides).
|
| 21 |
E |
|
|
|
Opgaver |
Som led i studienævnets evalueringsrutine er en kursusevaluering afholdt
efter eksamen. De sammentalte svar
(uden kommentarer af hensyn til de studerendes anonymitet,
jvf. studienævnets regler) og underviserens
handlingsplan er nu tilgængelige.
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|