Algoritmer og Datastrukturer 2

dADS2

DAIMI / Kurser / dADS 2

Meddelelser

14/8: Eksamensopgaverne august 2006.
11/7: Ifølge den foreløbige eksamensplan er dADS 2 re-eksamen den 14. august 2006.
11/7: Tilmelding til dADS 2 re-eksamen i august 2006 skal ske på universitetets selvbetjening i perioden den 1.-15. juli 2006.
11/7: Vejledende besvarelse til dADS 2 eksamen juni 2006.
23/6: Eksamensopgaverne juni 2006.
ældre meddelelser

Ugesedler

Uge 14 | 15-16 | 17 | 18 | 19 | 20 | 21
Alle ugesedler

Målbeskrivelse

Målet med kurset er at introducere den studerende til generelle designteknikker til konstruktion af effektive algoritmiske løsninger til kombinatoriske problemstillinger, samt at gøre den studerende bekendt med effektive løsninger til vigtige graf- og strengproblemer.

Forelæser

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

Forelæsninger

Mandag 14.15-16.00 og fredag 12.15-14.00 i Auditorium E (1-533-103).

Kursusplan

Nedenstående er kursusplanen som den var ved kursets start. Hvad der faktisk blev gennemgået fremgår af ugesedlerne.

Uge	Dag	Forelæsning	Litteratur
14	3/4	Del-og-kombiner	[CLRS] Kap. 2.3.1-2.3.2, 4.1-4.3, 28.2, Problem 30.1
14	7/4	Dynamisk programmering	[CLRS] Kap. 15
15-16	10/4	Dynamisk programmering	[CLRS] Kap. 15
	13-17/4	Påskeferie
	21/4	Grådige algoritmer	[CLRS] Kap. 16
17	24/4	Graf algoritmer: Repræsentation, BFS, DFS	[CLRS] Kap. 22.1-22.3
17	28/4	Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter	[CLRS] Kap. 22.4-22.5
18	1/5	Graf algoritmer: Minimum udspændende træer	[CLRS] Kap. 23
18	5/5	Graf algoritmer: Korteste veje (SSSP)	[CLRS] Kap. 24
19	8/5	Graf algoritmer: Korteste veje (APSP)	[CLRS] Kap. 25.1-25.2
19	12/5	Store Bededag
20	15/5	Streng algoritmer: Mønstergenkendelse	[CLRS] Kap. 32.1-32.2, 32.4
20	19/5	Streng algoritmer: Suffix træer og suffix arrays	[Smyth] 5.3.2, [GT] 9.2
21	22/5	Repetition Diskusion af eksamen
21	26/5	Ingen forelæsning

Materiale

Kernen af kursusmaterialet udgøres af følgende bog.

Introduction to Algorithms (Second Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. MIT Press and McGraw-Hill, 2001.

Til forelæsningerne om suffix træer udleveres der Kapitel 9.2 fra nedenstående bog. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.

Michael T. Goodrich and Roberto Tamassia: Algorithm design - Foundations, Analysis and Internet Examples. John Wiley & Sons, Inc. ISBN: 0-471-38365-1.

Til forelæsningerne om suffix arrays udleveres Kapitel 5.3.2 fra nedenstående bog. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.

William Smyth: Computing Patterns in Strings. Pearson Education, 2003. ISBN: 0-20139-839-7 (errata).

Webboard

Til diskussioner om opgaver og lignende har kurset et webboard.