Kursusbeskrivelse
for
Datastrukturer og algoritmer
ved
Keld Helsgaun
1. Formål
Studiet af datastrukturer og algoritmer er en central del af datalogien. Ved udvikling af et program er det vigtigt, at udvikleren har et solidt kendskab til egnede datastrukturer og algoritmer og kan foretage et kvalificeret valg imellem disse.
Kursets formål er
2. Mål
Målet er, at den studerende efter gennemførelse af kurset
3. Indhold
Kursets indhold kan overordnet beskrives ved følgende punkter:
Hovedvægten lægges på de tre første punkter.
4. Form
Undervisningen foregår ved forelæsninger og øvelser.
5. Lærebog
Som lærebog anvendes
Mark Allen Weiss,
Data Structures & Problem Solving Using Java,
Addison Wesley, 1998.
6. Forelæsninger
Til stofgennemgang er afsat 10 forelæsningsgange. En foreløbig plan er vist nedenfor. Ret til ændringer forbeholdes.
(11/9) Algoritmeanalyse (Kapitel 5: s. 107 - 141) O-notation. Binær søgning. |
||||||||
(18/9) Datastrukturer I (Kapitel 6: s. 143 - 172) Dataabstraktion. Elementære datastrukturer. |
||||||||
(25/9) Rekursion (Kapitel 7: s. 173 - 219) Algoritmedesign. |
||||||||
(2/10) Sortering (Kapitel 8 og 9: s. 223 - 279) Simple metoder. ShellSort, MergeSort og Quicksort. Randomisering. |
||||||||
(9/10) Anvendelser I (Kapitel 10 og 11: s. 283 - 330) Rekursion og stakke: spiltræer, aritmetiske udtryk. |
||||||||
(16/10) Anvendelser II (Kapitel 12 og 13: s. 331 - 365) Prioritetskøer: filkomprimering, simulering. |
||||||||
(23/10) Anvendelser III (Kapitel 14 : s. 367-410) Grafer. |
||||||||
(30/10) Datastrukturer II (Kapitel 15, 16 og 17: s. 411 - 487) Implementering af stakke, køer, hægtede lister og træer. |
||||||||
(6/11) Datastrukturer III (Kapitel 18: s.489 - 552) Søgetræer. |
||||||||
(13/11) Datastrukturer IV (Kapitel 19 og 20: s. 553 - 613) Hashing. Prioritetskøer. (20/11) Kursusvaluering |
7. Anbefalede forudsætninger
De anbefalede forudsætninger er som beskrevet i studieordningens §5, stk. 2. Det er en fordel at have et basalt kendskab til objektorienteret programmering i Java. For deltagere uden et sådant kendskab etableres i kursets start et kort undervisningsforløb baseret på lærebogens kapitel 2-4.
8. Arbejdsbelastning
Den forventede arbejdsbelastning er cirka 12 timer per uge i kursusperioden.
Der afholdes en skriftlig prøve med ekstern censur. Prøven varer 2 timer og foregår ved brug af alle sædvanlige hjælpemidler.