Algoritmer og Datastrukturer 1 (Forår 2009, Q3)

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

Deltagerne skal ved afslutningen af kurset kunne:

Øvelser og obligatoriske opgaver

Uge 5 | 6 | 7 | 8 | 9 | 10 | 11

Forelæser

Gerth Stølting Brodal

Forelæsninger

Mandag 14.15 - 16.00 Auditorium I (1514-213) og Torsdag 12.15 - 14.00 Auditorium E (1533-103).

Første forelæsning er mandag den 26. januar 2009.

Kursusplan

Uge Dag Forelæsning Litteratur Slides
5 26/1 Introduktion til Algoritmer og Datastrukturer

Yderligere information om tilfældige permutationer kan findes i David J.C. MacKay, Information Theory, Inference, and Learning Algorithms, tillæg om "Random Permutations". Dette er ikke pensum.
[Brodal], [Bentley] Kap. 8 puzzle.ppt
puzzle.pdf
applet
29/1 Analyseværktøjer [CLRS] Kap. 1-3.1 rammodel.pptx
rammodel.pdf
6 2/2 Flettesortering, Heapsort, Prioritetskøer [CLRS] Kap. 2.3, 6 heaps.ppt
heaps.pdf
5/2 QuickSort, Median, Selektion

Eksperimentel sammenligning af sorterings algoritmer
[CLRS] Kap. 7, 9.1-9.2 quicksort.ppt
quicksort.pdf
7 9/2 Nedre grænse for sammenligningsbaseret sortering
CountSort, RadixSort, BucketSort
[CLRS] Kap. 8 sorting.ppt
sorting.pdf
12/2 Stakke, Køer, Træer [CLRS] Kap. 10 stacks.ppt
stacks.pdf
8 16/2 Søgetræer, Rød-sorte søgetræer

ThinkFun's webside om RushHour
[CLRS] Kap. 12.1-12.3, 13 searchtrees.ppt
searchtrees.pdf
rushhour.ppt
rushhour.pdf
19/2 Hashing [CLRS] Kap. 11.1-11.4 hashing.ppt
hashing.pdf
greylisting.ppt
greylisting.pdf
9 23/2 Transitionssystemer [HS] Kap. 1 HSkap1.pdf
26/2 Transitionssystemer [HS] Kap. 2 HSkap2-3.pdf
10 2/3 Transitionssystemer [HS] Kap. 2 HSkap2-3.pdf
5/3 Union-find datastrukturer
Amortiseret analyse
[CLRS] Kap. 21.1-21.3
[CLRS] Kap. 17
unionfind.ppt
unionfind.pdf
amortized.ppt
amortized.pdf
11 9/3 Udvidede datastrukturer: Dynamisk rang, Interval træer [CLRS] Kap. 14 augmented.ppt
augmented.pdf
12/3 Repetition og diskussion af eksamen    

Materiale



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

Kernen af kursusmaterialet udgøres af denne bog, som kan købes i Gad Stakbogladen Naturfag fra ultimo januar 2009. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (Foråret 2009, Q4).

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

Kapitel 8 vil blive udleveret til forelæsningen mandag den 26. januar 2009. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.

stort billede
Puslespil ved Ombytninger, Gerth Stølting Brodal. Januar 2006, 4 sider.

Noten udleveres til forelæsningen mandag den 26. januar 2009.

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

Noten anvendes til forelæsningerne i uge 9-10 og kan købes i Gad Stakbogladen Naturfag fra uge 8. Pris 20 kr.