Algoritmer og Datastrukturer 1 (Q3, 2015)

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:

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 og øvelser er mandag den 26. januar 2015. Bemærk at der holdes øvelser for hold DA3 og DA7 mandag d. 26 januar før første forelæsning.

Spørgetime før eksamen

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

Ingo (DA2,IT1), torsdag 26. marts, 10.00, Ada 020
Mathias (DA1), torsdag 26. marts, 12.00, Ada-026
Kostas (DA3,DA7), fredag 27. marts, 10.00, 5520-112 (Incuba)
Gerth, fredag 27. marts, 14.00, PBA Auditoriet (Nygaard)
Carsten (Hold 1,IT2), mandag 30. marts, 10.00, Ada-020
Edvin (DA5,DA6), mandag 30. marts, 10.00, Ada 026

Kursusbelastning

Forelæsning 7 uger á 2 x 2 timer : 28 timer
Teoretiske øvelser 7 uger á 3 timer : 21 timer
DatLab 6 uger á 1 time : 6 timer
Udarbejdelse af 6 afleveringsopgaver á 3 timer : 18 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: 142 timer

DatLab

Der afholdes DatLab i Algoritmer og Datastrukturer 1 om fredagen 13-15 i Ada-020/026. Første gang 30. januar 2015. Bemanding: Mathias 30/1, Edvin 6/2, Ingo 13/2, Carsten 20/2, Kostas 27/2, Edvin 6/3. Intro slide.

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.

UgeDagForelæsningLitteraturSlidesOpgaver
5 (introduktionsopgaver) Opgaver 1-7
26/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
29/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.)
6 2/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
5/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
7 9/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
12/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
8 16/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
A5: [CLRS] Exercises 13.2-4
19/2 Transitionssystemer [HS] Kap. 1 HS.pdf Opgave 5, Opgave 8, Opgave 9, Opgave 10
9 23/2 Transitionssystemer [HS] Kap. 2 HS.pdf Opgave 13, Opgave 15
A6: Opgave 12
26/2 Transitionssystemer
 [HS] Kap. 3 HS.pdf
10 2/3 Union-find datastrukturer [CLRS] Kap. 21.1-21.3 unionfind.pdf [CLRS] Exercises 21.3-3, 21.3-5
5/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
11 9/3 Hashing [CLRS] Kap. 11.1-11.4 hashing.pdf
 greylisting.pdf		 [CLRS] Exercises 11.2-2, 11.2-5, 11.4-1
12/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 2015. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (Foråret 2015, 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.

Noten findes også under dokumenter i menuen.
Transition Systems, Mikkel Nygaard Hansen og Erik Meineche Schmidt. DAIMI-FN-64, Februar 2014.
Worst-case data structures for the priority queue with attrition, Rajamani Sundar. Information Processing Letters, 31(2), 69-75, 1989.

Artiklen findes under dokumenter i menuen. 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.

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 2015:

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 af en kombination af små skriftlige opgaver og multiple-choice-opgaver.