Algoritmer og Datastrukturer 1 (Forår 2012, Q3)
Meddelelser
- 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.
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 2011. 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. |