Algoritmer og Datastrukturer 1 (Q3, 2014)

Meddelelser

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:

DatLab

Der afholdes DatLab i Algoritmer og Datastrukturer 1 om fredagen 13-15 i Ada-020/026 med følgende bemanding: Mathias 31/1, Barbora 7/2, Bryan 14/2, Sarfraz 21/2, Antigoni 28/2, Andreas 7/3.

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 27. januar 2014.

Bemærk at der holdes øvelser for hold DA1 mandag d. 27 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.

Gerth, 17. marts 13.00, Lille Aud (Incuba)
Hold 1 (Sarfraz), 17. marts 12.00, Nygaard 298
Hold 2 (Jade), 18. marts 11.00, Building 1110, room 214
DA2 (Jakob), 18. marts 10.00, Ada 020
DA4 (Casper), 18. marts 12.00, Ada 020
DA5 (Mathias), 17. marts 10.00, Ada 026
DA7 (Andreas), 17. marts 11.00, Ada 020
DA1 (Bryan), DA6 (Barbora), IT1+IT2 (Antigoni): Da instruktorerne er forhindret i at afholde spørgetime, kan disse hold blot deltage i en af de ovenstående spørgetimer

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 under dokumenter efter forelæsningen. Opgaverne A1-A6 er de obligatoriske afleveringsopgaver. De obligatoriske afleveringsopgave skal regnes og afleveres i grupper af 1-3 personer. Afleveringstidspunktet er efter aftale med den enkelte instruktor.

Uge Dag Forelæsning Litteratur Slides Opgaver
5     (introduktionsopgaver)   Opgaver 1-7
27/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.pptx
puzzle.pdf
[Brodal] opgaver 1-3
[Bentley] 8.7.6, 8.7.11, 8.7.12
A1: Opgave 8
30/1 Analyseværktøjer [CLRS] Kap. 1-3.1 rammodel.pptx
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 3/2 Flettesortering, Heapsort, Prioritetskøer [CLRS] Kap. 2.3, 6 heaps.pptx
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
6/2 QuickSort, Median, Selektion

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

ThinkFun's webside om RushHour (Youtube)
[CLRS] Kap. 12.1-12.3, 13 searchtrees.pptx
searchtrees.pdf
rushhour.pptx
rushhour.pdf
[CLRS] Excercises 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
20/2 Hashing [CLRS] Kap. 11.1-11.3 hashing.pptx
hashing.pdf
[CLRS] Excercises 11.2-2, 11.2-5
9 24/2 Transitionssystemer
Forelæsning ved Erik Meineche Schmidt
[HS] Kap. 1 HS1.pdf Opgave 5, Opgave 8, Opgave 9, Opgave 10
27/2 Transitionssystemer
Forelæsning ved Erik Meineche Schmidt
[HS] Kap. 2 HS.pdf Opgave 13, Opgave 15
A6: Opgave 12
10 3/3 Transitionssystemer
Forelæsning ved Erik Meineche Schmidt
[HS] Kap. 3 HS.pdf  
6/3 Hashing (continued)
Union-find datastrukturer
[CLRS] Kap. 13.4
[CLRS] Kap. 21.1-21.3
greylisting.ppt
greylisting.pdf
unionfind.pptx
unionfind.pdf
[CLRS] Excercises 11.4-1, 21.3-3, 21.3-5
11 10/3 Amortiseret analyse
Udvidede datastrukturer: Dynamisk rang, Interval træer
[CLRS] Kap. 17
[CLRS] Kap. 14
amortized.pptx
amortized.pdf
augmented.pptx
augmented.pdf
[CLRS] Excercises 17.2-3, 17.3-3, 17.3-7, 14.1-5, 14.1-7, 14.3-4, 14.3-6, Problems 14-1
13/3 Eksempel: Prioritetskøer med afskæring (ikke pensum)
Repetition og diskussion af eksamen
(gennemgår eksamensopgaverne marts 2012)
[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 2014. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (Foråret 2014, 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, Februar 2014 (2014 udgaven af noten er identisk med 2004 udgaven, bort set fra følgende errata er levet rettet).
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.

Eksamen

2 timers skriftlig eksamen, 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 2013 var:

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 2004 (errata):
Kapitel 1, 2.

Eksamensopgaver

Eksamen består af en kombination af små skriftlige opgaver og multiple-choice-opgaver.