DM507 Algoritmer og datastrukturer
Forår 2015
Rolf Fagerberg
Kurset starter tirsdag den 3. februar og slutter tirsdag den
26. maj.
Spørgetime torsdag 4. juni, 10:15 i
U140. Vi vil
bla. gennemgå eksamenssættet for F14.
Skriftlige eksamen mandag den 8. juni kl. 16.00-20.00.
Eksamensættet endte således, med følgende
vejledende løsninger.
Eksamenskaraktererne fordelte sig på følgende
måde.
Datoen for reeksamen er fredag den 21. august, 2015. Reeksamen er
mundtlig. Eksamensspørgsmålene og andre oplysninger kan findes
her.
Timer
| Uge |
Type |
Dato |
Tid |
Lokale |
Indhold |
| 6 |
I |
Tirsdag 3/2 |
10-12 |
U140 |
Introduktion til kurset (slides, kapitel 1 i
lærebogen). Eksempel på algoritmeanalyse: Jul i Valhalla (Gerth Brodal:
slides, noter). |
| 6 |
I |
Torsdag 5/2 |
10-12 |
U140 |
Asymptotisk notation
(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.2 hvis der i kurset bruges
matematiske formler, definitioner og metoder, man har glemt.
|
| 6 |
TE |
|
|
|
Opgaver (Problem
1.1 fra lærebogen) |
| 7 |
I |
Tirsdag 10/2 |
10-12 |
U140 |
Sorteringsalgoritmer:
Insertionsort, Mergesort (side 147-150, afsnit 2.1-2,
afsnit 2.3, starten af 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.
|
| 7 |
TE |
|
|
|
Opgaver |
| 8 |
I |
Tirsdag 17/2 |
10-12 |
U140 |
Flere sorteringsalgoritmer: Quicksort (afsnit 7.1-3,
næste dele af slides).
|
| 8 |
I |
Torsdag 19/2 |
10-12 |
U140 |
Rekursive algoritmer. Flere sorteringsalgoritmer:
Heapsort. (afsnit 6.1-4, B.5.3,
slides,
slides).
|
| 8 |
TE |
|
|
|
Opgaver |
| 9 |
I+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 9 (ugen er
friholdt til reeksamen for nogle af studieretningerne).
|
| 10 |
I |
Tirsdag 3/3 |
10-12 |
U140 |
Heapsort færdig (afsnit 6.1-4, B.5.3, resten af
slides).
Nedre grænser for
sammenligningsbaseret sortering (afsnit 8.1, start af
slides).
Prioritetskøer (afsnit 6.5,
slides). Udlevering og diskussion af
Projekt, del I (tilhørende Java.filer:
PQ.java,
Element.java,
Dict.java). Eksempel på brug af Scanner i Java:
ScannerExample.java (læs kommentarer i
programmet). Testprogram som bruger PQHeap.java og DictBinTree.java:
TestProjectPartI.java (læs kommentarer i
programmet).
|
| 10 |
I |
Torsdag 5/3 |
10-12 |
U20 |
Mere gennemgang af projektet. Flere sorteringsalgoritmer: sortering af
heltal med Countingsort og Radixsort (afsnit 8.2-3,
resten af slides).
|
| 10 |
TE |
|
|
|
Opgaver |
| 11 |
I |
|
|
|
Bemærk: der er ingen I-timer (forelæsninger) i uge 11, da underviseren
er i udlandet. Brug tiden på at starte arbejdet med projektet.
|
| 11 |
TE |
|
|
|
Opgaver |
| 12 |
I |
Tirsdag 17/3 |
10-12 |
U140 |
Dictionaries og deres implementation via binære søgetræer (side 229-230,
afsnit 10.4, afsnit 12.1-3, afsnit 13.1-3, første del
af 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
(mere om invarianter til næste 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 bogen.
|
| 12 |
TE |
|
|
|
Opgaver |
| 13 |
I |
Tirsdag 24/3 |
10-12 |
U140 |
Sletning i rød-sorte træer (afsnit 13.4, midten af
slides). Dekoration af binære søgetræer
(afsnit 14.1-2, slides). Implementation
af dictionaries via hashing (afsnit 11.1-4 [dog ikke siderne 265-268 og
274-276], slutningen af slides).
|
| 13 |
I |
Torsdag 26/3 |
10-12 |
U140 |
Invarianter (side 18-20, 32-33, 157, 171-173, 318-322,
slides). Divide and Conquer algoritmer,
rekursionsligninger, og analyse heraf via rekursionstræer og Master
Theorem (afsnit 4.0, 4.4, 4.5,
slides). Læs også kommentaren om
forholdet mellem de to analysemetoder (rekursionstræsmetoden og Master
Theorem) på sedlen med opgaver til Uge 15.
|
| 13 |
TE |
|
|
|
Opgaver |
| 14 |
I+TE |
|
|
|
Bemærk: der er ingen timer (hverken I eller TE) i uge 14 pga. påske.
|
| 15 |
I |
Tirsdag 7/4 |
10-12 |
U140 |
Analyse af Divide and Conquer algoritmer via rekursionstræer og Master
Theorem (afsnit 4.0, 4.4, 4.5,
slides).
|
| 15 |
TE |
|
|
|
Opgaver |
| 16 |
I |
Tirsdag 14/4 |
10-12 |
U140 |
Eksempel på en Divide and Conquer algoritme: Strassen algoritme for
matrix-multiplikation (afsnit 4.2).
|
| 16 |
I |
Torsdag 16/4 |
10-12 |
U140 |
Dynamisk programmering (afsnit 15.1-2,
slides,
afsnit 15.4,
første del af slides).
|
| 16 |
TE |
|
|
|
Opgaver |
| 17 |
I |
Tirsdag 21/4 |
10-12 |
U140 |
Endnu et eksempel på dynamisk programmering (afsnit 15.3, anden del af
slides) 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. Udlevering og diskussion af Projekt,
del II. Tilhørende filer er to biblioteksfunktioner
BitInputStream.java,
BitOutputStream.java, set et eksempel på
brug af dem Test.java (læs kommentarer i programmet).
|
| 17 |
TE |
|
|
|
Opgaver |
| 18 |
I |
Tirsdag 28/4 |
10-12 |
U140 |
Feedback på projekt, del I
(slides). Resumé af
midtvejsevaluringe (slides).
Gennemgang af projektet, del II.
|
| 18 |
I |
Torsdag 30/4 |
10-12 |
U140 |
Bevis for optimalitet af Huffmankodning (afsnit 16.3, sidste del af
slides). Datastrukturer for disjoint sets
(afsnit 21.1-3, slides). Start på
grafalgoritmer: repræsentation af grafer (afsnit 22.1,
slides). Derudover er de første tre
sider af appendiks B.4 (side 1168-70) om basal terminologi for grafer
overladt til selvstændig læsning.
|
| 18 |
TE |
|
|
|
Opgaver |
| 19 |
I |
Tirsdag 5/5 |
10-12 |
U140 |
BFS grafgennemløn, DFS grafgennemløb, DAGs og topologisk sorting
(afsnit 22.2-4, slides).
|
| 19 |
TE |
|
|
|
Opgaver |
| 20 |
I |
Tirsdag 12/5 |
10-12 |
U140 |
Mere om DFS grafgennemløb, DAGs og topologisk sortering (afsnit 22.3-4,
slides). Sammenhængskomponenter (i
uorienterede grafer) og stærke sammenhængskomponenter (i orienterede
grafer) (slides). Start på
minimum udspændende træer (kapitel 23, slides).
|
| 20 |
I |
Fredag 15/5 |
10-12 |
U140 |
Mere om minimum udspændende træer (kapitel 23,
slides). Korteste veje, single source (afsnit 24.0,
start af slides).
|
| 20 |
TE |
|
|
|
Opgaver |
| 21 |
I |
Mandag 18/5 |
14-16 |
U110 |
GENTAGELSE af forelæsningen fra fredag 15/5.
Mere om minimum udspændende træer (kapitel 23,
slides). Korteste veje, single source
(afsnit 24.0, start af
slides).
|
| 21 |
I |
Tirsdag 19/5 |
10-12 |
U140 |
Mere om korteste veje, single source
(afsnit 24.1-3,
slides).
Korteste veje, all pairs (afsnit 25.2-3,
slides)
|
| 21 |
TE |
|
|
|
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)
|
|