• Kursusforside
• Fakultetets kursusbeskrivelse
• Eksamen
• dADS2 kursusside
• dADS1 - forår 2007

Meddelelser

• 12/8: Eksamensopgaverne august 2008 og vejledende besvarelse.
• 30/7: Endelig eksamensdato for august 2008 eksamen: 7. august 2008
• 25/7: Forløbig eksamensdato for august 2008 eksamen: 7. august 2008
• 7/5: Karaktererne for eksamenen den 8. april er afleveret til Studiekontoret.
• 8/4: Eksamensopgaverne april 2008 og vejledende besvarelse.
• 10/3: Eksamenspensum.
• 10/3: Endelig eksamensdato 8. april 2008
• ældre meddelelser

Formål

Deltagerne vil efter kurset have indsigt i algoritmer som model for sekventielle beregningsprocesser og som basis for formelle korrekthedsbeviser og analyse af ressourceforbrug ved beregningerne, samt detaljeret kendskab til adskillige konkrete implementationer af fundamentale datastrukturer.

Indhold

Datastrukturer Lister, træer, hashtabeller Dataabstraktioner Stakke, køer, prioritetskøer, ordbøger, mængder Algoritmer Søgning, sortering, selektion, fletning Analyse og syntese Worst-case, amortiseret og forventet udførelsestid, udsagn, invarianter, gyldighed, terminering og korrekthed.

Læringsmål

• formulere og udføre algoritmer og datastrukturer i pseudo code.
• analysere og sammenligne tid og pladsforbruget af algoritmer.
• identificere gyldige invarianter for en algoritme.
• bevise korrektheden af simple programmer og transitionssystemer.

Ugesedler

• Uge 5 | 6 | 7 | 8 | 9 | 10 | 11
• Alle ugesedler

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 28. januar 2008.

Kursusplan

Uge	Dag	Forelæsning	Litteratur	Slides
5	28/1	Introduktion til Algoritmer og Datastrukturer	[Brodal], [Bentley] Kap. 8	puzzle.ppt puzzle.pdf
	1/2	Analyseværktøjer	[CLRS] Kap. 1-3.1	rammodel.ppt rammodel.pdf
6	4/2	Flettesortering, Heapsort, Prioritetskøer	[CLRS] Kap. 2.3, 6	heaps.ppt heaps.pdf
	8/2	QuickSort, Median, Selektion	[CLRS] Kap. 7, 9.1-9.2	quicksort.ppt quicksort.pdf
7	11/2	Nedre grænse for sammenligningsbaseret sortering CountSort, RadixSort, BucketSort	[CLRS] Kap. 8	sorting.ppt sorting.pdf
	15/2	Stakke, Køer, Træer	[CLRS] Kap. 10	stacks.ppt stacks.pdf rushhour.ppt rushhour.pdf
8	18/2	Søgetræer, Rød-sorte søgetræer	[CLRS] Kap. 12.1-12.3, 13	searchtrees.ppt searchtrees.pdf
	22/2	Hashing	[CLRS] Kap. 11.1-11.4	hashing.ppt hashing.pdf greylisting.ppt greylisting.pdf
9	25/2	Transitionssystemer	[HS] Kap. 1	HSkap1
	29/2	Transitionssystemer	[HS] Kap. 2	HSkap2-3
10	3/3	Transitionssystemer	[HS] Kap. 2	HSkap2-3
	7/3	Union-find datastrukturer Amortiseret analyse	[CLRS] Kap. 21.1-21.3 [CLRS] Kap. 17	unionfind.ppt unionfind.pdf amortized.ppt amortized.pdf
11	10/3	Udvidede datastrukturer: Dynamisk rang, Interval træer Diskussion af eksamen	[CLRS] Kap. 14	augmented.ppt augmented.pdf
	14/3	Ingen forelæsning

Materiale

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

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 28. januar 2008. 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 28. januar 2008.

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.