Algoritmer og Datastrukturer 1

dADS1

DAIMI / Kurser / dADS1

Meddelelser

12/8: Eksamensopgaverne og vejledende besvarelse august 2006.
11/7: Ifølge den foreløbige eksamensplan er dADS 1 re-eksamen den 11. august 2006.
11/7: Tilmelding til dADS 1 re-eksamen i august 2006 skal ske på universitetets selvbetjening i perioden den 1.-15. juli 2006.
23/3: Eksamensopgaverne og vejledende besvarelse marts 2006.
16/3: Ifølge den endelige eksamensplan er eksamen den 23/3 2006.
16/3: Pensum til eksamen.
8/3: Ugesedlen for uge 11.
ældre meddelelser

Ugesedler

Uge 5 | 6 | 7 | 8 | 9 | 10 | 11
Alle 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 Auditorium E (1-533-103).

Første forelæsning er mandag den 30. januar 2006.

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
5	30/1	Introduktion til Algoritmer og Datastrukturer	[Brodal], [Bentley] Kap. 8
5	3/2	Analyseværktøjer	[CLRS] Kap. 1-3.1
6	6/2	Flettesortering, Heapsort, Prioritetskøer	[CLRS] Kap. 2.3, 6
6	10/2	QuickSort, Median, Selektion	[CLRS] Kap. 7.1-7.4.1, 9.1-9.2
7	13/2	Nedre grænse for sammenligningsbaseret sortering CountSort, RadixSort, BucketSort	[CLRS] Kap. 8
7	17/2	Stakke, Køer, Søgetræer	[CLRS] Kap. 10, 12
8	20/2	Rød-sorte søgetræer	[CLRS] Kap. 13
8	24/2	Hashing	[CLRS] Kap. 11
9	27/2	Transitionssystemer (forelæsning ved Erik Meineche Schmidt)	[HS] Kap. 1
9	3/3	Transitionssystemer (forelæsning ved Erik Meineche Schmidt)	[HS] Kap. 2
10	6/3	Transitionssystemer	[HS] Kap. 2
10	10/3	Union-find datastrukturer	[CLRS] Kap. 21
11	13/3	Udvidede datastrukturer: Dynamisk rang, Interval træer	[CLRS] Kap. 14
11	17/3	Amortiseret analyse Diskusion af 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 2006. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (4. kvarter, foråret 2006).

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 i Uge 5. 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.

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.

Nedenstående note udleveres til forelæsningen i Uge 5.

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

Webboard

Til diskussioner om opgaver og lignende har kurset et webboard.