Algoritmer og Datastrukturer 1 (2008)

dADS1
DAIMI / Kurser / dADS1

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:
  • 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.

Ugesedler

Forelæser

Gerth Stølting Brodal <gerth@cs.au.dk>

Forelæsninger

Mandag 14.15-16.00 og fredag 12.15-14.00 i Store Auditorium (IT Huset).

Første forelæsning er mandag den 28. januar 2008.

Kursusplan

Uge Dag Forelæsning Litteratur Slides
5 28/1 Introduktion til Algoritmer og Datastrukturer [Brodal], [Bentley] Kap. 8 puzzle.ppt
puzzle.pdf
1/2 Analyseværktøjer [CLRS] Kap. 1-3.1 rammodel.ppt
rammodel.pdf
6 4/2 Flettesortering, Heapsort, Prioritetskøer [CLRS] Kap. 2.3, 6 heaps.ppt
heaps.pdf
8/2 QuickSort, Median, Selektion [CLRS] Kap. 7, 9.1-9.2 quicksort.ppt
quicksort.pdf
7 11/2 Nedre grænse for sammenligningsbaseret sortering
CountSort, RadixSort, BucketSort
[CLRS] Kap. 8 sorting.ppt
sorting.pdf
15/2 Stakke, Køer, Træer [CLRS] Kap. 10 stacks.ppt
stacks.pdf
rushhour.ppt
rushhour.pdf
8 18/2 Søgetræer, Rød-sorte søgetræer [CLRS] Kap. 12.1-12.3, 13 searchtrees.ppt
searchtrees.pdf
22/2 Hashing [CLRS] Kap. 11.1-11.4 hashing.ppt
hashing.pdf
greylisting.ppt
greylisting.pdf
9 25/2 Transitionssystemer [HS] Kap. 1 HSkap1
29/2 Transitionssystemer [HS] Kap. 2 HSkap2-3
10 3/3 Transitionssystemer [HS] Kap. 2 HSkap2-3
7/3 Union-find datastrukturer
Amortiseret analyse
[CLRS] Kap. 21.1-21.3
[CLRS] Kap. 17
unionfind.ppt
unionfind.pdf
amortized.ppt
amortized.pdf
11 10/3 Udvidede datastrukturer: Dynamisk rang, Interval træer
Diskussion af eksamen
[CLRS] Kap. 14 augmented.ppt
augmented.pdf
14/3 Ingen forelæsning    

Materiale

Kernen af kursusmaterialet udgøres af følgende bog, som kan købes i Gad Stakbogladen Naturfag fra ultimo januar 2008. Bogen vil også blive brugt i Algoritmer og Datastrukturer 2 (4. kvarter, foråret 2008).

Introduction to Algorithms (Second Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. MIT Press and McGraw-Hill, 2001.

Kapitel 8 af følgende bog vil blive udleveret til forelæsningen mandag den 28. januar 2008. De øvrige kapitler i bogen vil ikke blive gennemgået i kurset.

Jon Bentley: Programming Pearls, Second Edition. Addison-Wesley, Inc., 2000. ISBN 0-201-65788-0.

Nedenstående note udleveres til forelæsningen mandag den 28. januar 2008.

Gerth Stølting Brodal: Puslespil ved Ombytninger, januar 2006, 4 sider.

Forelæsningerne i uge 9-10 vil dække dele af følgende note, der vil kunnne købes i Gad Stakbogladen Naturfag i slutningen af uge 8 for ca. 20 kroner.

Mikkel Nygaard Hansen og Erik Meineche Schmidt: Transition Systems, DAIMI-FN-64, February 2004.


Denne side vedligholdes af Gerth Stølting Brodal