Algoritmer og Datastrukturer 1 (Forår 2010, Q3)

Meddelelser

16/8: dADS1 karaktererne sendt til studiekontoret.
13/8: Eksamensopgaverne august 2010 og vejledende besvarelse.
6/8: Reeksamen er fredag den 13. august.
5/5: dADS1 karaktererne sendt til studiekontoret.
9/4: Eksamensopgaverne marts 2010 og vejledende besvarelse.
2/3: Opgaver til øvelserne i uge 10.
2/3: Eksamen, 31. marts, 12.30-14.30.
25/2: Invitation til programmeringskonkurrence for studerende lørdag d. 17. april 10.30-16.00 i Stibitz-123
24/2: Opgaver til øvelserne i uge 9.
18/2: Opgaver til øvelserne i uge 8.
9/2: Opgaver til øvelserne i uge 7.
8/2: Invitation: Studentermøde for datalogistuderende (pdf | ppt)
4/2: Opgaver til øvelserne i uge 6.
29/1: (Valgfri) Information om hvordan man tester en implementation af løsningen til den første obligatoriske opgave (uge 4).
28/1: Opgaver til øvelserne i uge 5.
17/1 2010: Opgaver til øvelserne i uge 4.
18/10 2009: 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.

Øvelser og obligatoriske opgaver

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

Forelæser

Gerth Stølting Brodal

Forelæsninger

Mandag 14.15 - 16.00 og Torsdag 12.15 - 14.00, Auditorium E (1533-103).

Første forelæsning og øvelser er mandag den 25. januar 2010. Bemærk at der holdes øvelser for hold DA1 og DA4 før første forelæsning.

Kursusplan

Uge	Dag	Forelæsning	Litteratur	Slides
4	25/1	Introduktion til Algoritmer og Datastrukturer 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.ppt puzzle.pdf applet maxsum kode
4	28/1	Analyseværktøjer	[CLRS] Kap. 1-3.1	rammodel.ppt rammodel.pdf
5	1/2	Flettesortering, Heapsort, Prioritetskøer	[CLRS] Kap. 2.3, 6	heaps.ppt heaps.pdf
5	4/2	QuickSort, Median, Selektion Eksperimentel sammenligning af sorterings algoritmer	[CLRS] Kap. 7.1-7.4.1, 9.1-9.2	quicksort.ppt quicksort.pdf
6	8/2	Nedre grænse for sammenligningsbaseret sortering CountSort, RadixSort, BucketSort	[CLRS] Kap. 8	sorting.ppt sorting.pdf
6	11/2	Stakke, Køer, Træer	[CLRS] Kap. 10	stacks.ppt stacks.pdf
7	15/2	Søgetræer, Rød-sorte søgetræer ThinkFun's webside om RushHour (Youtube)	[CLRS] Kap. 12.1-12.3, 13	searchtrees.ppt searchtrees.pdf rushhour.ppt rushhour.pdf
7	18/2	Hashing	[CLRS] Kap. 11.1-11.4	hashing.ppt hashing.pdf greylisting.ppt greylisting.pdf
8	22/2	Union-find datastrukturer Amortiseret analyse	[CLRS] Kap. 21.1-21.3 [CLRS] Kap. 17	unionfind.ppt unionfind.pdf amortized.ppt amortized.pdf
8	25/2	Udvidede datastrukturer: Dynamisk rang, Interval træer	[CLRS] Kap. 14	augmented.ppt augmented.pdf
9	1/3	Transitionssystemer (forelæsning ved dekan Erik Meineche Schmidt)	[HS] Kap. 1	HSkap1.pdf
9	4/3	Transitionssystemer (forelæsning ved Gudmund Skovbjerg Frandsen)	[HS] Kap. 2	HSkap2-3.pdf
10	8/3	Transitionssystemer	[HS] Kap. 3	HSkap2-3.pdf
10	11/3	Repetition og diskussion af eksamen

Materiale

stort billede	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 Gad Stakbogladen Naturfag fra ultimo januar 2010. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (Foråret 2010, Q4).
stort billede	Programming Pearls, Second Edition, Jon Bentley, Addison-Wesley, Inc., 2000. ISBN 0-201-65788-0. Kapitel 8 vil blive udleveret til forelæsningen mandag den 25. januar 2010 (linket kræver lovlig login ved Datalogisk Institut). De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.
stort billede	Puslespil ved Ombytninger, Gerth Stølting Brodal. Januar 2006, 4 sider. Noten udleveres til forelæsningen mandag den 25. januar 2010.
stort billede	Mikkel Nygaard Hansen og Erik Meineche Schmidt: Transition Systems, DAIMI-FN-64, February 2004 (errata). Noten anvendes til forelæsningerne i uge 9-10 og kan købes i Gad Stakbogladen Naturfag fra uge 8. Pris 20 kr.

dADS1