Algoritmer og Datastrukturer 1 (Forår 2011, Q3)
Meddelelser
- 12/8: Karaktererne for eksamen den 11/8 sendt til studiekontoret
- 12/8: Eksamensopgaverne august 2011 og vejledende besvarelse
- 28/7: Endelige dato for reeksamen: 11. august
- 5/7: Tid og sted for reeksamen i august
- 19/4: dADS1 karakterne sendt til studiekontoret
- 30/3: Eksamensopgaverne marts 2011 og vejledende besvarelse
- 15/3: E-mail fra Jesper (instruktor på DA5) omkring programmeringskonkurrence (mere info om algoritmik relaterede programmeringskonkurrencer findes på Mark Greve's hjemmeside)
- 10/3: Tid og sted for eksamen
- 3/3: Mht DatLab, så afholdes der også DatLab den 11/3 (den sidste fredag i kvarteret)
- 1/3: Opgaver til øvelserne i uge 10
- 23/2: Opgaver til øvelserne i uge 9
- 17/2: Opgaver til øvelserne i uge 8
- 9/2: Opgaver til øvelserne i uge 7
- 2/2: Opgaver til øvelserne i uge 6
- 28/1: Information om DatLab. Første gang fredag den 4. februar
- 24/1: Slides fra dagens forelæsning med clicker spørgsmål findes under dokumenter
- 24/1: Opgaver til øvelserne i uge 5
- 17/1: Opgaver til øvelserne i uge 4
- 17/1 2011: Holdlister for øvelsesholdene er nu tilgængelige i læseplanen
- 22/11: Eksamensdato, 30. marts 2011
- 11/10 2010: 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. Auditorium E (1533-103).
Første forelæsning og øvelser er mandag den 24. januar 2011.
Bemærk at der holdes øvelser for hold DA4 og DA5 før første forelæsning.
Kursusplan
Bemærk: Slides med clicker spørgsmål findes under dokumenter efter forelæsningen.
| Uge | Dag | Forelæsning | Litteratur | Slides |
|---|---|---|---|---|
| 4 | 24/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. Forelæsning ved Gudmund Skovbjerg Frandsen |
[Brodal], [Bentley] Kap. 8 | puzzle.ppt puzzle.pdf applet maxsum kode |
| 27/1 | Analyseværktøjer | [CLRS] Kap. 1-3.1 | rammodel.ppt rammodel.pdf |
|
| 5 | 31/1 | Flettesortering, Heapsort, Prioritetskøer | [CLRS] Kap. 2.3, 6 | heaps.ppt heaps.pdf |
| 3/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 | 7/2 | Nedre grænse for sammenligningsbaseret sortering CountSort, RadixSort, BucketSort |
[CLRS] Kap. 8 | sorting.ppt sorting.pdf |
| 10/2 | Stakke, Køer, Træer | [CLRS] Kap. 10 | stacks.ppt stacks.pdf |
|
| 7 | 14/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 |
| 17/2 | Hashing | [CLRS] Kap. 11.1-11.4 | hashing.ppt hashing.pdf greylisting.ppt greylisting.pdf |
|
| 8 | 21/2 | Union-find datastrukturer Amortiseret analyse |
[CLRS] Kap. 21.1-21.3 [CLRS] Kap. 17 |
unionfind.ppt unionfind.pdf amortized.ppt amortized.pdf |
| 24/2 | Udvidede datastrukturer: Dynamisk rang, Interval træer | [CLRS] Kap. 14 | augmented.ppt augmented.pdf |
|
| 9 | 28/2 | Transitionssystemer | [HS] Kap. 1 | HSkap1.pdf |
| 3/3 | Transitionssystemer | [HS] Kap. 2 | HSkap2-3.pdf | |
| 10 | 7/3 | Transitionssystemer | [HS] Kap. 3 | HSkap2-3.pdf |
| 10/3 |
Eksempel: Prioritetskøer med afskæring (ikke pensum)
Repetition og diskussion af eksamen |
[S89] Kap. 1-3 | attritions.pptx attritions.pdf |
Materiale
 stort billede |
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 fra ultimo januar 2011. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (Foråret 2011, 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 |
 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 24. januar 2011 (findes også under dokumenter). 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 24. januar 2011. |
 stort billede |
Transition Systems,
Mikkel Nygaard Hansen og Erik Meineche Schmidt.
DAIMI-FN-64, February 2004 (errata).
Noten anvendes til forelæsningerne i uge 9-10 og kan købes i Stakbogladen fra uge 8. Pris 20 kr. |
 stort billede |
Worst-case data structures for the priority queue with attrition, Rajamani Sundar.
Information Processing Letters,
31(2), 69-75, 1989.
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. |