Algoritmer og Datastrukturer 1 (2007)

dADS1
DAIMI / Kurser / dADS1

Meddelelser

Ugesedler

Målbeskrivelse

Målet med kurset er at give de studerende erfaring med algoritmer som model for sekventielle beregningsprocesser og som basis for formelle korrekthedsbeviser og analyse af ressourceforbrug ved beregningerne. I forbindelse hermed introduceres de studerende bl.a. til forskellige konkrete implementationer af fundamentale datastrukturer.

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 mandag den 29. januar 2007.

Kursusplan

Uge Dag Forelæsning Litteratur
5 29/1 Introduktion til Algoritmer og Datastrukturer [Brodal], [Bentley] Kap. 8
2/2 Analyseværktøjer [CLRS] Kap. 1-3
6 5/2 Flettesortering, Heapsort, Prioritetskøer [CLRS] Kap. 2.3, 6
9/2 QuickSort, Median, Selektion [CLRS] Kap. 7, 9.1-9.2
7 12/2 Nedre grænse for sammenligningsbaseret sortering
CountSort, RadixSort, BucketSort
[CLRS] Kap. 8
16/2 Stakke, Køer, Søgetræer [CLRS] Kap. 10, 12.1-12.3
8 19/2 Rød-sorte søgetræer [CLRS] Kap. 13
23/2 Hashing [CLRS] Kap. 11.1-11.4
9 26/2 Transitionssystemer [HS] Kap. 1
2/3 Transitionssystemer [HS] Kap. 2
10 5/3 Transitionssystemer [HS] Kap. 2
9/3 Union-find datastrukturer [CLRS] Kap. 21.1-21.3
11 12/3 Udvidede datastrukturer: Dynamisk rang, Interval træer [CLRS] Kap. 14
16/3 Amortiseret analyse
Eksamen
[CLRS] Kap. 17

Materiale

Kernen af kursusmaterialet udgøres af følgende bog, som kan købes i Gad Stakbogladen Naturfag fra medio januar 2007. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (4. kvarter, foråret 2007).

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

Kapitel 8 af følgende bog vil blive udleveret til forelæsningen mandag den 29. januar 2007. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.

Jon Bentley: Programming Pearls, Second Edition. Addison-Wesley, Inc., 2000. ISBN 0-201-65788-0.

Nedenstående note udleveres til forelæsningen mandag den 29. januar 2007.

Gerth Stølting Brodal: Puslespil ved Ombytninger, januar 2006, 4 sider.

Forelæsningerne i uge 9-10 vil dække dele af følgende note, der vil kunnne købes i Gad Stakbogladen Naturfag i slutningen af uge 8 for ca. 20 kroner.

Mikkel Nygaard Hansen og Erik Meineche Schmidt: Transition Systems, DAIMI-FN-64, February 2004.

Webboard

Til diskussioner om opgaver og lignende har kurset et
webboard.


Denne side vedligholdes af Gerth Stølting Brodal