Algoritmer og Datastrukturer 1 (Forår 2012, Q3)
Meddelelser
- 13/8: Karaktererne for reeksamen sendt til studiekontoret
- 10/8: Eksamensopgaverne august 2012 og vejledende besvarelse
- 4/8: Spørgetime (reeksamen) onsdag den 8. august 14.00 i Ada-018
- 13/4: dADS1 karaktererne sendt til studiekontoret
- 21/3: Eksamensopgaverne marts 2012 og vejledende besvarelse
- 27/2: Tid og sted for eksamen
- 24/1: Der afholdes DatLab i Ada0 hver fredag 27. januar-2. marts
- 18/1 2012: Holdlisterne er nu tilgængelige science.au.dk. Bemærk at hold DA7 skal have øvelser allerede mandag den 23. januar, før første forelæsning
- 6/12 2011: 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 4 | 5 | 6 | 7 | 8 | 9 | 10
Forelæser
Forelæsninger
Mandag 14.15 - 16.00 og Torsdag 12.15 - 14.00 i Peter Bøgh Andersen Auditoriet (Nygaard bygningen, Finlandsgade 21).
Første forelæsning og øvelser er mandag den 23. januar 2012.
Spørgetime før eksamen
De enkelte hold aftaler selv med instruktoren hvornår der skal holdes spørgetime før eksamen.
15. marts 10.00, Ada 018, Torben (Hold 1)
14. marts 12.00, Ada 018, Magnus (IT1)
16. marts 13.00, Nygaard 184, Mathies (IT2)
19. marts 11.00, Ada 020, Mathias (DA1)
14. marts 10.00, Ada 018, Casper (DA2)
19. marts 10.00, Ada 026, Jesper (DA3)
16. marts 11.00, Ada 018, Jana (DA4)
16. marts 12.00, Turing 014, Andreas (DA5)
19. marts 11.00, Nygaard 297, Barbora (DA6)
16. marts 14.00, 5520.112, Lukas (DA7)
Kursusplan
Bemærk: Slides med clicker spørgsmål findes under dokumenter efter forelæsningen.
| Uge | Dag | Forelæsning | Litteratur | Slides |
|---|---|---|---|---|
| 4 | 23/1 |
Introduktion til Algoritmer og Datastrukturer
Puslespils applet; kode til maxsum problemet 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 |
| 26/1 | Analyseværktøjer | [CLRS] Kap. 1-3.1 | rammodel.ppt rammodel.pdf |
|
| 5 | 30/1 | Flettesortering, Heapsort, Prioritetskøer | [CLRS] Kap. 2.3, 6 | heaps.ppt heaps.pdf |
| 2/2 | QuickSort, Median, Selektion Eksperimentel sammenligning af sorterings algoritmer |
[CLRS] Kap. 7.1-7.4.1, 9.1-9.2 | quicksort.ppt quicksort.pdf |
|
| 6 | 6/2 | Nedre grænse for sammenligningsbaseret sortering CountSort, RadixSort, BucketSort |
[CLRS] Kap. 8 | sorting.ppt sorting.pdf |
| 9/2 | Stakke, Køer, Træer | [CLRS] Kap. 10 | stacks.ppt stacks.pdf |
|
| 7 | 13/2 | Søgetræer, Rød-sorte søgetræer ThinkFun's webside om RushHour (Youtube) |
[CLRS] Kap. 12.1-12.3, 13 | searchtrees.ppt searchtrees.pdf rushhour.ppt rushhour.pdf |
| 16/2 | Hashing | [CLRS] Kap. 11.1-11.4 | hashing.ppt hashing.pdf greylisting.ppt greylisting.pdf |
|
| 8 | 20/2 | Union-find datastrukturer Amortiseret analyse |
[CLRS] Kap. 21.1-21.3 [CLRS] Kap. 17 |
unionfind.ppt unionfind.pdf amortized.ppt amortized.pdf |
| 23/2 | Udvidede datastrukturer: Dynamisk rang, Interval træer | [CLRS] Kap. 14 | augmented.ppt augmented.pdf |
|
| 9 | 27/2 | Transitionssystemer | [HS] Kap. 1 | HSkap1.pdf |
| 1/3 | Transitionssystemer | [HS] Kap. 2 | HSkap2-3.pdf | |
| 10 | 5/3 | Transitionssystemer | [HS] Kap. 3 | HSkap2-3.pdf |
| 8/3 |
Eksempel: Prioritetskøer med afskæring (ikke pensum)
Repetition og diskussion af eksamen |
[S89] Kap. 1-3 | attritions.pptx attritions.pdf |
Materiale
|
Introduction to Algorithms (Third Edition), Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein.
MIT Press, 2009.
Kernen af kursusmaterialet udgøres af denne bog, som kan købes i Stakbogladen på Matematisk Institut under Auditorium E, fra ultimo januar 2012. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (Foråret 2012, Q4). Videoer af forelæsninger på MIT over bogens emner med Charles E. Leiserson (en af bogens forfattere) og Erik D. Demaine findes som MIT OpenCourseWare |
|
Programming
Pearls, Second Edition,
Jon Bentley.
Addison-Wesley, Inc., 2000.
ISBN 0-201-65788-0.
Kapitel 8 findes under dokumenter. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset. |
|
Puslespil ved Ombytninger,
Gerth Stølting Brodal. Januar 2006, 4 sider.
Noten findes også under dokumenter. |
|
Transition Systems,
Mikkel Nygaard Hansen og Erik Meineche Schmidt.
DAIMI-FN-64, February 2004 (errata).
Noten anvendes til forelæsningerne i uge 9-10 Noten findes også online under dokumenter og kan også købes trykt from i Stakbogladen fra uge 8. Pris ca. 20 kr. |
|
Worst-case data structures for the priority queue with attrition, Rajamani Sundar.
Information Processing Letters,
31(2), 69-75, 1989.
Artiklen findes under dokumenter. Artiklens kapitel 1-3 vil blive gennemgået til den sidste forelæsning som eksempel på amortiseret analyse, invarianter, og transitioner. Artiklen er ikke pensum. |