Algoritmer og Datastrukturer 2

dADS2

DAIMI / Kurser / dADS 2

Meddelelser

12/8: Eksamensopgaverne august 2008.
30/7: Endelig eksamensdato for august 2008 eksamen: 11. august 2008
25/7: Forløbig eksamensdato for august 2008 eksamen: 11. august 2008
23/6 Eksamensopgaverne juni 2008 og vejledende besvarelse.
3/6: Vdr. resultatdato for eksamen: Datoen 21. juli er bebræftiget af studiekontoret. Hvis man skulle dumpe dADS2 eksamen i juni, kan man eftermelde sig til august eksamen efter den 21. juli.
30/5: Eksamenspensum
30/5: Kopier af [GT, kapitel 9.2] og [Smyth, kapitel 5.3.2] er lagt i dADS kursushylden i Shannon bygningen.
21/5: Ugeseddel 7
14/5: Ugeseddel 6
5/5: Slides om ACM/ICPC programmeringskonkurrencer
21/4: Endelig eksamensdato, 23/6-2008.
ældre meddelelser

Formål

Deltagerne vil efter kurset have indsigt i konstruktionen af graf- og streng-algoritmer til løsning af konkrete algoritmiske problemer, og detaljeret kendskab til anvendelsen af fundamentale algoritmiske paradigmer til design af algoritmer.

Indhold

Algoritmeparadigmer: Del-og-kombiner, dynamisk programmering, grådighed. Grafalgoritmer: Grafgennemløb, sammenhængsegenskaber, topologisk sortering, udspændende træer, korteste veje, transitiv lukning. Tekstprocessering: Mønstergenkendelse, trier, tekstkomprimering, tekstsimilaritet.

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

konstruere og analysere algoritmer ved hjælp af standard algoritmeparadigmer.
identificere og formulere algoritmiske problemer som graf- og streng-problemer.
identificere og sammenligne graf- og streng-algoritmer til løsning af algoritmiske problemer.
konstruere algoritmer for simple graf- og streng-problemer.

Ugesedler

Ugeseddel 1 (10/4-16/4)
Ugeseddel 2 (17/4-23/4)
Ugeseddel 3 (24/4-30/4)
Ugeseddel 4 (5/5-8/5)
Ugeseddel 5 (14/5-19/5)
Ugeseddel 6 (21/5-26/5)
Ugeseddel 7 (28/5-2/6)
Alle ugesedler

Bemærk: Hvad der gennemgås til de enkelte forelæsninger fremgår af nedenstående kursusplan, ligesom slides til forelæsningerne forefindes i kursusplanen.

Forelæser

Gerth Stølting Brodal <gerth@cs.au.dk>

Forelæsninger

Mandag 14.15-16.00 og fredag 12.15-14.00 i Store Auditorium (IT Huset).

Første forelæsning er fredag den 11. april 2008.

Kursusplan

Nedenstående er kursusplanen for dADS2.

Uge	Dag	Forelæsning	Litteratur	Slides
15	10/4	Start 4. kvarter DA2 og DA3 første øvelsesgang
15	11/4	Del-og-kombiner (under forelæsningen bevises en simplere udgave af Master Theorem'et)	[CLRS] Kap. 2.3.1-2.3.2, 4.1-4.3, 28.2, Problem 30.1.c	divide.ppt divide.pdf
16	14/4	Dynamisk programmering	[CLRS] Kap. 15.1-15.4	dynamicprogramming.ppt dynamicprogramming.pdf
16	18/4	Store Bededag: Ingen forelæsning
17	21/4	Dynamisk programmering	[CLRS] Kap. 15.5	dynamicprogramming.ppt dynamicprogramming.pdf
17	25/4	Grådige algoritmer	[CLRS] Kap. 16.1-16.3	greedy.ppt greedy.pdf
18	28/4	Graf algoritmer: Repræsentation, BFS, DFS	[CLRS] Kap. 22.1-22.3	graphs.ppt graphs.pdf
	1/5	Kr. Himmelfartsdag: DA2 og DA3 ingen øvelser
	2/5	Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter	[CLRS] Kap. 22.4-22.5	topologicalsort.ppt topologicalsort.pdf
19	5/5	Graf algoritmer: Korteste veje (SSSP)	[CLRS] Kap. 24.1-24.3, 24.5	shortestpaths.ppt shortestpaths.pdf
19	9/5	Graf algoritmer: Korteste veje (APSP)	[CLRS] Kap. 25.1-25.2	shortestpaths.ppt shortestpaths.pdf
20	12/5	2. Pinsedag: Ingen forelæsning og DA4 ingen øvelser
20	16/5	Graf algoritmer: Minimum udspændende træer	[CLRS] Kap. 23	mst.ppt mst.pdf
21	19/5	Graf algoritmer: Maksimale strømninger	[CLRS] Kap. 26.1-26.2	flow.ppt flow.pdf
21	23/5	Graf algoritmer: Maximale todelte parringer	[CLRS] Kap. 26.3	flow.ppt flow.pdf
22	26/5	Streng algoritmer: Mønstergenkendelse	[CLRS] Kap. 32.1-32.2, 32.4	patternmatching.ppt patternmatching.pdf
22	30/5	Streng algoritmer: Suffix træer og suffix arrays	[Smyth] 5.3.2, [GT] 9.2	tries.ppt tries.pdf
23	2/6	Repetition Diskusion af eksamen Slut 4. kvarter