Kursusbeskrivelse

1. Formål

Kursets formål er

at supplere den studerendes kendskab til analyse og design af algoritmer
at udbygge den studerendes evne til at tilegne sig algoritmeorienteret stof og at formidle dette til andre.

2. Indhold

Kurset er et avanceret kursus i algoritmedesign.

Emner:

Algoritmeanalyse
Asymptotisk notation, amortisering, eksperimentel analyse
Algoritmiske designmønstre
Grådige algoritmer, del-og-hersk, dynamisk programmering
Grafalgoritmer
Traversering, topologisk sortering, korteste vej,
mindste udspændende træ, strømning i netværk
Internetalgoritmer
Strengsøgning, tekstkomprimering, kryptografi, netværksalgoritmer
Geometriske algoritmer
Flerdimensionale træer, konvekst hylster

3. Form

Undervisningen foregår ved forelæsninger og øvelser.

4. Deltagerforudsætninger

Kurset forudsætter fortrolighed med datastrukturer og algoritmer svarende til gennemførelse af kurset “Datalogi C” eller CSS.
Desuden forudsættes matematik på B-niveau.

5. Evaluering

Mundtlig eksamen. 30 minutters individuel prøve.
Den studerende fremlægger en artikel, der er udleveret 3 arbejdsdage inden eksamen.
Der gives karakter efter 7-trinsskalaen.

6. Lærebog

Som lærebog anvendes

        Michael T. Goodrich og Roberto Tamassia:
        Algorithm Design: Foundations, Analysis, and Internet Examples,
        John Wiley & Sons, Inc., 2002.

7. Forelæsninger

Til stofgennemgang er afsat 10 forelæsningsgange. En foreløbig plan for forelæsningerne er vist nedenfor. Ret til ændringer forbeholdes.

(4/2) Fundamentale værktøjer I
Algoritmeanalyse. Prioritetskøer. Hashing.

(11/2) Fundamentale værktøjer II
Søgetræer og skiplister. Sortering.

(18/2) Fundamentale værktøjer III
Algoritmiske designmønstre.

(25/2) Grafalgoritmer I
Korteste veje. Mindste udspændende træ.

(3/3) Grafalgoritmer II
Strømning i netværk.

(10/3) Internetalgoritmer I
Strengsøgning. Tekstkomprimering.

(17/3) Internetalgoritmer II
Kryptografi.

(31/3) Internetalgoritmer III
Netværksalgoritmer.

(7/4) Geometriske algoritmer
Flerdimensionale søgetræer. Konvekst hylster.

(14/4) Kursusafrunding

Algoritmedesign

med internetanvendelser