Algoritmer og Datastrukturer 2 (2007)
dADS2
DAIMI / Kurser / dADS 2

Meddelelser

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 Store Auditorium (IT Huset).

Forelæsningen mandag den 7. maj er dog i Auditorium F i Ny Munkegade (bygning 1534).

Første forelæsning er mandag den 2. april 2007.

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-15 2/4 Del-og-kombiner [CLRS] Kap. 2.3.1-2.3.2, 4.1-4.3, 28.2, Problem 30.1.c
5-9/4 Påskeferie
13/4 Del-og-kombiner: Fast Fourier Transform (FFT) [CLRS] Kap. 30.1-30.2
16 16/4 Dynamisk programmering [CLRS] Kap. 15
20/4 Dynamisk programmering [CLRS] Kap. 15
17 23/4 Grådige algoritmer [CLRS] Kap. 16.1-16.3
27/4 Graf algoritmer: Repræsentation, BFS, DFS [CLRS] Kap. 22.1-22.3
18 30/4 Graf algoritmer: Topologisk sortering, stærke sammenhængskomponenter [CLRS] Kap. 22.4-22.5
4/5 Store Bededag - ingen forelæsning
(Hold 1 aftaler med instruktoren tidspunkt for øvelser)
19 7/5 Graf algoritmer: Korteste veje (SSSP)
Forelæsning ved Peter Bro Miltersen
Forelæsningen er flyttet til Auditorium F i Ny Munkegade 		[CLRS] Kap. 24.1-24.3, 24.5
11/5 Graf algoritmer: Korteste veje (APSP)
Forelæsning ved Peter Bro Miltersen		 [CLRS] Kap. 25.1-25.2
20 14/5 Graf algoritmer: Minimum udspændende træer [CLRS] Kap. 23
17/5 Kr. Himmelfartsdag
(Hold DA3 og DA4 aftaler med instruktoren tidspunkt for øvelser)
18/5 Streng algoritmer: Mønstergenkendelse [CLRS] Kap. 32.1-32.2, 32.4
21 21/5 Streng algoritmer: Suffix træer og suffix arrays [Smyth] 5.3.2, [GT] 9.2
25/5 Repetition
Diskusion af eksamen		  

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.

Denne side vedligholdes af Gerth Stølting Brodal <gerth@cs.au.dk>