Algoritmer og Datastrukturer 1 (Q3, 2017)

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.

Forelæser

Gerth Stølting Brodal

Forelæsninger

Mandag 14.15 - 16.00 og Torsdag 12.15 - 14.00 i Auditorium E (1533-103). Første forelæsning er mandag den 23. januar 2017.

Spørgetime før eksamen

De enkelte hold aftaler selv med instruktoren hvornår der skal holdes spørgetime før eksamen.

Gerth, fredag 24. marts, 13.00-16.00, Peter Bøgh Auditoriet (Nygaard)
Kostas, mandag 27. marts, 9.00-, Nygaard 184 (5335-184)
Casper, mandag 27. marts, 12.00-, Nygaard 192 (5335-192)
Alexander, mandag 27. marts, 12.00-14.00, Nygaard (5335-295)
Sabine, mandag 27. marts, 14.00-, Nygaard 184 (5335-184)
Andreas, tirsdag 28. marts, 10.00-, Nygaard 184 (5335-184)
Ingo, tirsdag 28. marts, 14-17, Nygaard 184 (5335-184)

Studiecafé

Der afholdes dagligt studiecafé i Ada 0 for alle kurser på 1. studieår, hvor der også vil være en instruktor til stede for Algoritmer og Datastruktuer 1.

Mandag 12-14, Tirsdag 14-16, Onsdag 12-14, Torsdag 14-16, Fredag 13-15.

Bemanding: mandag, Sabine; tirsdag, Kostas; onsdag, Casper; torsdag, Ingo; og fredag, Edvin.

En generel side om studiecaféen findes på studieportalen.

Kursusbelastning

Forelæsning 7 uger á 2 x 2 timer : 28 timer
Teoretiske øvelser 7 uger á 3 timer : 21 timer
StudieCafé 7 uger á 2 time : 14 timer
Udarbejdelse af 6 afleveringsopgaver á 2 timer : 12 timer
Forberedelse til forelæsning 1 time per 2 timers forelæsning : 14 timer
Forberedelse til teoretiske øvelser 7 uger á 2 timer : 14 timer
Foreberedelse til eksamen 5 dage á 8 timer : 40 timer
Eksamen : 2 timer
I alt: 145 timer

Kursusplan

Nedenstående er kursusplanen for kurset. For hver foreæsning er angivet opgaverne relateret til forelæsningen, som regnes til de efterfølgende øvelser. Slides med clicker spørgsmål findes efter forelæsningen under Dokumenter i menuen. Opgaverne A1-A6 er de obligatoriske afleveringsopgaver. De obligatoriske afleveringsopgaver skal regnes og afleveres i grupper af 1-3 personer. Afleveringstidspunktet er efter aftale med den enkelte instruktor. Afleveringstidspunkterne fremgår og fremgår i menuen til venstre.

UgeDagForelæsningLitteraturSlidesOpgaver
4 (introduktionsopgaver) Opgaver 1-7
23/1 Introduktion til Algoritmer og Datastrukturer
(Algoritmer og Datastrukturer vs. Java og C++)

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.pdf [Brodal] opgaver 1-3
[Bentley] 8.7.6, 8.7.11, 8.7.12
A1: Opgave 8
26/1 Analyseværktøjer

Algorithmic Challenge ved Thomas Dueholm Hansen		 [CLRS] Kap. 1-3.1 rammodel.pdf [CLRS] Exercises 1.2-2, 1.2-3, 3.1-1, 3.1-4, Problems 1-1, 3-3 (undlad funktioner med "lg*")
A2: [CLRS] Problem 3-4 (delspørgsmål a.-e.)
Quizz: Asymptotisk notation: Funktioner og Summer
5 30/1 Flettesortering, Heapsort, Prioritetskøer [CLRS] Kap. 2.3, 6 heaps.pdf [CLRS] Exercises 2.3-5, 6.1-4, 6.1-5, 6.1-6, 6.3-2, Problems 2-1, 2-4
A3: [CLRS] Problem 6-2
A4: [CLRS] Problem 6-3
Quizz: Heaps
2/2 QuickSort, Median, Selektion

Eksperimentel sammenligning af sorterings algoritmer		 [CLRS] Kap. 7.1-7.4.1, 9.1-9.2 quicksort.pdf [CLRS] Exercises 7.1-2, 7.2-3, 7.3-2, Problems 9.1
Quizz: Mergesort og Quicksort
6 6/2 Nedre grænse for sammenligningsbaseret sortering
CountSort, RadixSort, BucketSort		 [CLRS] Kap. 8 sorting.pdf [CLRS] Exercises 8.1-1, 8.1-3, 8.2-4, 8.3-4
9/2 Stakke, Køer, Træer [CLRS] Kap. 10 stacks.pdf [CLRS] 10.1-2, 10.1-5, 10.2-7, 10.2-8, Problems 10.1
7 13/2 Søgetræer, Rød-sorte søgetræer

ThinkFun's webside om RushHour (Youtube, Michael Fogleman's website on Rush Hour)		 [CLRS] Kap. 12.1-12.3, 13 searchtrees.pdf
rushhour.pdf		 [CLRS] Exercises 12.1-5, 12.2-4, 13.1-5, 13.1-6, 13.2-2, 13.3-2, Problems 12.2,13-2
A5: [CLRS] Exercises 13.2-4
Quizz: Rød-sorte søgetræer
16/2 Transitionssystemer [HS] Kap. 1 HS.pdf Opgave 5, Opgave 8, Opgave 9, Opgave 10
Quizz: Transitionssystemer
8 20/2 Transitionssystemer [HS] Kap. 2 HS.pdf Opgave 13, Opgave 15
A6: Opgave 12
Quizz: Algoritmer
23/2 Transitionssystemer
 [HS] Kap. 3 HS.pdf
9 27/2 Union-find datastrukturer [CLRS] Kap. 21.1-21.3 unionfind.pdf [CLRS] Exercises 21.3-3, 21.3-5
2/3 Amortiseret analyse
Udvidede datastrukturer: Dynamisk rang, Interval træer 		[CLRS] Kap. 17
[CLRS] Kap. 14		 amortized.pdf
augmented.pdf		 [CLRS] Exercises 17.2-3, 17.3-3, 17.3-7, 14.1-5, 14.1-7, 14.3-4, 14.3-6, Problems 14-1
Quizz: Amortiseret analyse
10 6/3 Hashing [CLRS] Kap. 11.1-11.4 hashing.pdf
 greylisting.pdf		 [CLRS] Exercises 11.2-2, 11.2-5, 11.4-1
9/3 Eksempel: Prioritetskøer med afskæring (ikke pensum)
Repetition og diskussion af eksamen
(gennemgår eksamensopgaverne marts 2012)		 [S89] Kap. 1-3 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 2017. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (Foråret 2017, 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 i menuen. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.
Puslespil ved Ombytninger, Gerth Stølting Brodal. Januar 2006, 4 sider.
Transition Systems, Mikkel Nygaard Hansen og Erik Meineche Schmidt. DAIMI-FN-64, Februar 2014.

Eksamen

2 timers multiple-choice, intern censur, 7-skala bedømmelse.

Hjælpemidler: Alle sædvanlige hjælpemidler (lærebøger, notater, lommeregner). Computer må ikke medbringes.

For at kunne indstilles til eksamen skal man have godkendt besvarelserne af 6 obligatoriske ugeopgaver.

Pensum

Pensum til dADS 1 eksamen i foråret 2017 er:

Jon Bentley. Programming Pearls, Second Edition, Addison-Wesley, Inc., 2000:
Kapitel 8.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. Introduction to Algorithms (Third Edition), MIT Press and McGraw-Hill, 2009:
Kapitel 1, 2, 3.1, 6, 7.1-7.4.1, 8, 9.1-9.2, 10, 11.1-11.4, 12.1-12.3, 13, 14, 17, 21.1-21.3.

Mikkel Nygaard Hansen og Erik Meineche Schmidt. Transition Systems, DAIMI FN-64, februar 2014:
Kapitel 1, 2.

Eksamenshistorik

Karakterfordeling 2010-2016.

Eksamensopgaver

Eksamen er multiple-choice (indtil 2014 bestod eksamen af en kombination af små skriftlige opgaver og multiple-choice-opgaver).