Algoritmer og Datastrukturer 1 (Forår 2009, Q3)
Meddelelser
- 7/8: Eksamensopgaverne august 2009 og vejledende besvarelse.
- 23/6: Augusteksamen i dADS1 er den 7. august 2009
- 27/4: Karaktererne afleveret til eksamenskontoret.
- 26/3: Eksamensopgaverne marts 2009 og vejledende besvarelse.
- 26/3: Rettet fejl i vejledende besvarelser for august 2008, opgave 22, 4. delspørgsmål.
- 24/3: Rettet fejl i de vejledende besvarelser for marts 2007, opgave 16, og august 2008, opgave 8.
- 3/3: Foreløbig eksamensdato 26. marts 2009.
- 2/3: Opgaver til øvelserne i uge 11.
- 26/2: Opgaver til øvelserne i uge 10.
- 17/2: Opgaver til øvelserne i uge 9.
- 10/2: Opgaver til øvelserne i uge 8.
- 4/2: Opgaver til øvelserne i uge 7.
- 2/2: Husk at der er eksamenstilmelding den 1.-15. februar via selvbetjeningen.
- 29/1: Opgaver til øvelserne i uge 6.
- 29/1: Overskydende kopier af [Brodal] og [Bentley] er lagt på hylderne i indgangen til Shannon bygningen.
- 23/1: Opgaver til øvelserne i uge 5.
- 23/1: Tilføjet information om eksamen og kursusplan.
- 21/1 2009: Holdlister og bemanding tilføjet. Omlagt websiderne til nyt AU design.
- 19/11 2008: Kursussiden oprettet.
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:
- 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.
Øvelser og obligatoriske opgaver
Uge 5 | 6 | 7 | 8 | 9 | 10 | 11
Forelæser
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. |