Ugeplan og generel info

Indhold

Introduktion til algoritmer og datastrukturer.

Officielle beskrivelser: 02105 Algoritmer og datastrukturer 1, 02326 Algoritmer og datastrukturer

Undervisere

Philip Bille, phbi@dtu.dk, kontortid mandag + torsdag 12.30-13.00.

Hvor og hvornår

Grupperegning, torsdag 8.00 – 10.00.

  • Hold 1, 116/025, Thomas Gøttrup Nielsen
  • Hold 2, 116/025, Simon Graverholt Søkilde
  • Hold 3, 116/018, Anders Palmelund
  • Hold 4, 116/013, Mathias Kaas-Olsen
  • Hold 5, 210/042, Martin Kasban Tange
  • Hold 6, 210/048, Søren Paabøl Jacobsen
  • Hold 7, 210/142, Anders Roy Christiansen
  • Hold 8, 210/148, Emil Klarskov Kristensen

Hold 1, 2 og 3 er regnehold forbeholdt diplomstuderende. Hold 4, 5, 6 og 7 er regnehold forbeholdt civilstuderende. Hold 8 er gennemgangshold for både civil- og diplomstuderende.

Torsdag d. 17 april og 1 maj er der ikke undervisning pga. ferie. Tilgengæld er der undervisning tirsdag d. 13 maj.

Forelæsning, torsdag 10.20-12.00, Bygn. 116, Aud. 81.

Litteratur

“Introduction to Algorithms” af Cormen, Leierson, Rivest og Stein. 3rd edition

Ugeplan

Ugeplanen er tentativ. Den vil blive opdateret i løbet af semestret. Der arbejdes med opgaver fra uge x i uge x+1.

Uge 0: Opvarming: Forberedelse, programmeringsforståelse.

Uge 1: Basale begreber I: Introduktion, algoritmer, datastrukturer, toppunkter.

Uge 2: Basale begreber II: Søgning, sortering. 

Uge 3: Basale begreber III: Kompleksitetsanalyse, O-notation, empirisk analyse.

Uge 4: Datastrukturer I: Stakke, køer, hægtede lister, træer.

Uge  5: Datastrukturer II: Hobe, prioritetskøer, hobsortering.

Uge  6: Grafalgoritmer I: Uorienterede grafer, repræsentation, søgning, modellering.

  • CLRS introduktion til del VI + kap. 22.1-22.4 + appendix B.4-B.5.
  • Slides
  • Ugeseddel

Uge  7: Grafalgoritmer II:  Orienterede grafer, topologisk sortering, implicitte grafer.

Uge  8: Datastrukturer III: Foren og find, dynamiske sammenhængskomponenter.

Uge  9: Grafalgoritmer III: Mindste udspændende træ, Prims algoritme, Kruskals algoritme.

Uge  10: Grafalgoritmer IV: Dijkstras algoritme, korteste veje i vægtede grafer, korteste veje i DAGs.

Uge  11: Datastrukturer IV: Ordbøger, hashing.

Uge  12: Datastrukturer V: Algoritmer på træer, predecessor datastrukturer, binære søgetræer.

Uge  13: Opsamling: Spørgetime, gennemregning af gammelt eksamenssæt, videregående kurser i algoritmik.

Gamle eksamenssæt

FAQ