Algoritmer og Datastrukturer 1 (Q3, 2014)

Meddelelser

10/8: Eksamensopgaverne august 2014 og vejledende besvarelse.
23/4: Karakterne sendt til studiekontoret.
19/3: Eksamensopgaverne marts 2014 og vejledende besvarelse.
6/3: Eksamensplan.
22/1 2014: 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.

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	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
7	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
8	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
9	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
10	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
11	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.