Uge 11

Forelæsninger

Mandag den 12/3-2007, kl 14-16

• Udvidede datastrukturer: Dynamisk rang, Interval træe [CLRS] Kap. 14

Fredag den 16/3-2007, kl. 12-14

• Amortiseret analyse [CLRS] Kap. 17
  Diskusion af eksamen

Øvelser

[CLRS] Exercises 11.2-2, 11.2-5, 11.4-1, 21.3-3, 21.3-4
Opgave 12, Opgave 13, Opgave 15

Uge 10

Forelæsninger

Mandag den 5/3-2007, kl 14-16

• Transitionssystemer [HS] Kap. 2: eksempler på korrekthedsbeviser.

Fredag den 9/3-2007, kl. 12-14

• Union-Find [CLRS] Kap. 21.1-21.3

Øvelser

[CLRS] Exercises 13.1-5, 13.1-6, 13.2-2, 13.3-2 Problems 13-2
Opgave 5, Opgave 8, Opgave 9, Opgave 10,

Obligatorisk afleveringsopgave

[CLRS] Exercises 13.2-4

Uge 9

Forelæsninger

Mandag den 26/2-2007, kl 14-16

• Transitionssystemer [HS] Kap. 1

Fredag den 2/3-2007, kl. 12-14

• Transitionssystemer [HS] Kap. 2

Øvelser

[CLRS] Exercises 10.1-2, 10.1-5, 10.1-6, 10.2-2, 10.2-3, 10.2-7, 10.2,8, 12.1-5, 12.2-4 Problems 10.1, 12.2

Obligatorisk afleveringsopgave

[CLRS] Exercise 10.4-6

Uge 8

Forelæsninger

Mandag den 19/2-2007, kl 14-16

• Rød-sorte søgetræer [CLRS] Kap. 13 (Slides)

Fredag den 23/2-2007, kl. 12-14

• Hashing [CLRS] Kap. 11.1-11.4

Øvelser

[CLRS] Exercises 7.2-4, 7.3-2, 8.2-4, 8.3-2, 8.3-4, 9.1-1, Problems 7.1, 7.3, 9.1

Obligatorisk afleveringsopgave

[CLRS] Problem 6-3

Uge 7

Forelæsninger

Mandag den 12/2-2007, kl 14-16

• Nedre grænse for sammenligningsbaseret sortering CountSort, RadixSort, BucketSort [CLRS] Kap. 8 (Slides)

Fredag den 16/2-2007, kl. 12-14

• Stakke, Køer, Søgetræer [CLRS] Kap. 10, 12.1-12.3 (Slides)

Øvelser

[CLRS] Exercises 2.3-5, 6.1-4, 6.1-5, 6.1-6, 6.3-2, 7.1-2, 7.2-3, Problems 2-1, 2-4

Obligatorisk afleveringsopgave

[CLRS] Problem 6-2

Uge 6

Forelæsninger

Mandag den 5/2-2007, kl 14-16

• Flettesortering, Heapsort, Prioritetskøer [CLRS] Kap. 2.3, 6 (Slides)

Fredag den 9/2-2007, kl. 12-14

• QuickSort, Median, Selektion [CLRS] Kap. 7, 9.1-9.2 (Slides)
  (Sammenligning af sorterings algoritmer.)

Øvelser

[Bentley] 8.7.6, 8.7.12

[CLRS] Exercises 1.2-2, 1.2-3, 3.1-1, 3.1-4, Problems 1.1, 3.3 (undlad funktioner med "lg*")

Obligatorisk afleveringsopgave

[Bentley] 8.7.11

Uge 5

Forelæsninger

Mandag den 29/1-2007, kl 14-16

• Introduktion til algoritmer, [Brodal], [Bentley] Kap. 8 (Slides)
  (Yderligere information om tilfældige permutationer kan i findes David J.C. MacKay, Information Theory, Inference, and Learning Algorithms, tillæg om "Random Permutations". Dette er ikke pensum.)

Fredag den 2/2-2007, kl. 12-14

• Analyseværktøjer, [CLRS] Kap. 1-3.1 (Slides)

Øvelser

Opgaver til uge 5 + [Brodal] opgaver 1-3

Obligatorisk afleveringsopgave

Opgave 1

Forklaring

Ugesedlen anfører til hver uge hvilke forelæsninger der planlægges holdt i nærmeste fremtid. De anførte øvelsesopgaver bliver gennemgået til TØ i den pågældende uge. De vil typisk behandle stof fra den foregående uge. Den obligatoriske afleveringsopgave skal regnes og afleveres i udgangen af den pågældende uge, typisk i weekenden, efter aftale med holdets instruktor.

Afleveringsopgaven på ugesedlen til uge x afleveres mellem øvelserne i uge x og x+1. Så har man nemlig gavn af gennemgangen af relateret stof til TØ i uge x til at regne afleveringsopgaven. Instruktoren vil gennemgå opgaven til TØ i uge x+1 og tilbagelevere den rettede aflevering.

---