Algoritmer og Datastrukturer 1 (Q3, 2013)

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:

Øvelser og obligatoriske opgaver

Uge 5 | 6 | 7 | 8 | 9 | 10 | 11

DatLab

Der afholdes DatLab i Algoritmer og Datastrukturer 1 om fredagen 13-15 i Babbage-0 med følgende bemanding: 1/2 Jesper, 8/2 Barbora, 15/2 Tore, 22/2 Nils, 1/3 Lauge, 8/3 Andreas.

Forelæser

Gerth Stølting Brodal

Forelæsninger

Mandag 14.15 - 16.00 og Torsdag 12.15 - 14.00 i Auditorium E.

Første forelæsning og øvelser er mandag den 28. januar 2013.

Spørgetime før eksamen

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

18. marts 14.00, Ada 020, Nils (DA4)
19. marts 8.00, Ada 026, Bryan (DA7)
19. marts 10.00, Ada 018, Barbora (IT1 + IT2)
19. marts 11.00, Ada 020, Thorbjørn (DA1)
19. marts 11.00, Ada 026, Andreas (DA6)
19. marts 12.00, Turing 014, Lauge (DA5)
20. marts 9.15, Ada 026, Jesper (Hold 1)
20. marts 12.00, Ada 020, Jacob (DA3)
20. marts 15.15, Ada 020, Tore (DA2)

Kursusplan

Bemærk: Slides med clicker spørgsmål findes under dokumenter efter forelæsningen.

Uge Dag Forelæsning Litteratur Slides
5 28/1 Introduktion til Algoritmer og Datastrukturer
(Algoritmer og Datastrukturer vs. Java og C++)

Puslespils applet; 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
31/1 Analyseværktøjer [CLRS] Kap. 1-3.1 rammodel.pptx
rammodel.pdf
6 4/2 Flettesortering, Heapsort, Prioritetskøer [CLRS] Kap. 2.3, 6 heaps.pptx
heaps.pdf
7/2 QuickSort, Median, Selektion

Eksperimentel sammenligning af sorterings algoritmer		 [CLRS] Kap. 7.1-7.4.1, 9.1-9.2 quicksort.pptx
quicksort.pdf
7 11/2 Nedre grænse for sammenligningsbaseret sortering
CountSort, RadixSort, BucketSort
Forelæsning aflyst pga sygdom 		[CLRS] Kap. 8 sorting.pptx
sorting.pdf
14/2 Stakke, Køer, Træer [CLRS] Kap. 10 stacks.pptx
stacks.pdf
8 18/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
21/2 Hashing [CLRS] Kap. 11.1-11.4 hashing.pptx
hashing.pdf
greylisting.ppt
greylisting.pdf
9 25/2 Union-find datastrukturer
Amortiseret analyse		 [CLRS] Kap. 21.1-21.3
[CLRS] Kap. 17		 unionfind.pptx
unionfind.pdf
amortized.pptx
amortized.pdf
28/2 Udvidede datastrukturer: Dynamisk rang, Interval træer [CLRS] Kap. 14 augmented.pptx
augmented.pdf
10 4/3 Transitionssystemer [HS] Kap. 1 HS.pdf
7/3 Transitionssystemer [HS] Kap. 2 HS.pdf
11 11/3 Transitionssystemer [HS] Kap. 3 HS.pdf
14/3 Eksempel: Prioritetskøer med afskæring (ikke pensum)

Repetition og diskussion af eksamen		 [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 2013. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (Foråret 2013, 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 2004 (errata).

Noten anvendes til forelæsningerne i uge 9-10. Noten findes også online under dokumenter og kan også købes trykt from i Stakbogladen fra uge 9. Pris ca. 20 kr.
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 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 (Second Edition), MIT Press and McGraw-Hill, 2001:
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.