Algoritmer og Datastrukturer 1 (Q3, 2016)

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 25. januar 2016.

Spørgetime før eksamen

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

Kostas (Hold 3), mandag 28. marts, 9.00-12.00, 5342-026 Ada
Kostas (DA6), tirsdag 29. marts, 9.00-12.00, IT-huset, lokale 112 (5520-112, INCUBA)
Edvin (Hold 1), onsdag 30. marts, 10.00-12.00, 5342-020 Ada
Casper (DA3), torsdag 31. marts, 10.00-12.00, 5242-018 Ada
Gerth, fredag 1. april, 10.00-12.00, Store Aud (INCUBA)
Rasmus (Hold 2), søndag 3. april, 10.00-12.00, 5242-020 Ada

Studiecafé

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

Mandag-Tirsdag-Onsdag 12.00-14.00, Torsdag 14.00-16.00, Fredag 13.00-15.00

Bemanding: mandag, Ingo; tirsdag, Edvin; onsdag, Edvin; torsdag, Ingo; og fredag, Rasmus.

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: 144 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
25/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
28/1 Analyseværktøjer [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 1/2 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
4/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 8/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
11/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 15/2 Transitionssystemer
Forelæsning ved Erik Meineche Schmidt		 [HS] Kap. 1 HS.pdf Opgave 5, Opgave 8, Opgave 9, Opgave 10
Quizz: Transitionssystemer
18/2 Transitionssystemer
Forelæsning ved Erik Meineche Schmidt		 [HS] Kap. 2 HS.pdf Opgave 13, Opgave 15
A5: Opgave 12
Quizz: Algoritmer
8 22/2 Transitionssystemer
 [HS] Kap. 3 HS.pdf
25/2 Søgetræer, Rød-sorte søgetræer

ThinkFun's webside om RushHour (Youtube)		 [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
A6: [CLRS] Exercises 13.2-4
Quizz: Rød-sorte søgetræer
9 29/2 Union-find datastrukturer [CLRS] Kap. 21.1-21.3 unionfind.pdf [CLRS] Exercises 21.3-3, 21.3-5
3/3 Amortiseret analyse
Udvidede datastrukturer: Dynamisk rang, Interval træer
Diskussion af eksamen		 [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 7/3 Hashing
Forelæsning ved Erik Meineche Schmidt		 [CLRS] Kap. 11.1-11.4 hashing.pdf
 greylisting.pdf		 [CLRS] Exercises 11.2-2, 11.2-5, 11.4-1
10/3 Ingen forelæsning      

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 2016. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (Foråret 2016, 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 2016 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.

Eksamensopgaver

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