Målet med kurset er at give de studerende erfaring med algoritmer som model for sekventielle beregningsprocesser og som basis for formelle korrekthedsbeviser og analyse af ressourceforbrug ved beregningerne. I forbindelse hermed introduceres de studerende bl.a. til forskellige konkrete implementationer af fundamentale datastrukturer.
· 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
Forelæsninger 4 timer (2+2).
Øvelser 3 timer
Gert Brodal Stølting
2 timers skriftlig eksamen, intern censur, bestået/ikke bestået
3. kvarter
5 ECTS