• Kursusforside
• Eksamen
• dADS2 kursusside
• dADS1 - forår 2006

Meddelelser

• 6/8: Eksamensopgaverne og vejledende besvarelse august 2007.
• 26/7: Endelig eksamensdato 6. august 2007 (august eksamen).
• 25/5: Foreløbig eksamensdato 6. august 2007.
• 18/4: Karaktererne afleveret til studiekontoret. Karaktererne vil være tilgængelige fra i morgen.
• 30/3: Eksamensopgaverne marts 2007 og vejledende besvarelse.
• æ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

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