Algoritmer og Datastrukturer 2 (2006)

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 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
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
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
5/5 Graf algoritmer: Korteste veje (SSSP) [CLRS] Kap. 24
19 8/5 Graf algoritmer: Korteste veje (APSP) [CLRS] Kap. 25.1-25.2
12/5 Store Bededag
20 15/5 Streng algoritmer: Mønstergenkendelse [CLRS] Kap. 32.1-32.2, 32.4
19/5 Streng algoritmer: Suffix træer og suffix arrays [Smyth] 5.3.2, [GT] 9.2
21 22/5 Repetition
Diskusion af eksamen
 
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.


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