AARHUS UNIVERSITET DATALOGISK INSTITUT Algoritmer og Datastrukturer (dADS)

Uge 21

Forelæsninger

Mandag den 19/5-2003, kl 12-14

• Feedback på obligatorisk opgave
• Drøftelse af eksamen

Torsdag den 22/5-2003, kl. 14-16

• Ingen forelæsning

Øvelser

S97.3 [ps, pdf], S97.4 [ps, pdf], S98.3 [ps, pdf], S99.2 [ps, pdf], S01.3 [ps, pdf]

Disse fem eksamensopgaver er ganske repræsentative for den emnemæssige spredning, der kan forventes i det kommende eksamenssæt.

Uge 20

Forelæsninger

Mandag den 12/5-2003, kl 12-14

• Repetition (gamle eksamensopgaver)

  Søgetræer: A01.4 [ps, pdf], S02.3 [ps, pdf], A99.2 [ps, pdf]

  Dynamisk programmering: A02.4 [ps, pdf], S00.3 [ps, pdf]

Torsdag den 15/5-2003, kl. 14-16

• Repetition (gamle eksamensopgaver)

  Graf algoritmer: S93.5 [ps, pdf]

Øvelser

[GT] R-9.12, C-9.3, C-9.9

S01.1 [ps, pdf], A94.4 [ps, pdf], S92.6 [ps, pdf]

Uge 19

Forelæsninger

Mandag den 5/5-2003, kl 12-14

• Streng algoritmer, [GT] Kap. 9.2-9.3

Torsdag den 8/5-2003, kl. 14-16

• Amortiseret analyse, [GT] Kap. 1.5

Øvelser

Opgave 21 [ps,pdf], Opgave 27 [ps,pdf],

[GT] C-7.2, C-7.6, C-7.7

S00.1 [ps, pdf], S92.3 [ps, pdf]

Afleveringsopgave

Obligatorisk opgave O3

Uge 18

Forelæsninger

Mandag den 28/4-2003, kl 12-14

• Graf algoritmer, [GT] Kap. 7.2.1, 7.3

Torsdag den 1/5-2003, kl. 14-16

• Streng algoritmer, [GT] Kap. 9.1

Øvelser

S98.2 [ps, pdf], S01.2 [ps, pdf], A02.1 [ps, pdf], Opgave 42 [ps,pdf] (trykfejl: erstat "kapitel 7" med "kapitel 3"), Opgave 34 [ps,pdf],

Opgave

Udvid algortimen LLMS(A) så den udover længden af den længste monotone delfølge også finder (en) følge(n) af denne længde.

Afleveringsopgave

Obligatorisk opgave O2

Uge 16-17

Forelæsninger

Mandag den 14/4-2003, kl 12-14

• [HS] Transitionssystemer 3.5-6 (forelæser Erik Meineche Schmidt)

Torsdag den 24/4-2003, kl. 14-16

• Graf algoritmer, [GT] Kap. 7.1

Øvelser

Opgave 22 [ps,pdf]

R-6.6, R-6.11

C-6.2, C-6.4, C-6.9, C-6.12, C-6.18, C-6.19

Afleveringsopgave

Obligatorisk opgave O1

Uge 15

Forelæsninger

Mandag den 7/4-2003, kl 12-14

• Graf algoritmer, [GT] Kap. 6.1, 6.2, 6.3.1, 6.3.3

Torsdag den 10/4-2003, kl. 14-16

• Graf algoritmer, [GT] Kap. 6.4

Øvelser

Opgave 3 [ps,pdf], Opgave 37 [ps,pdf], A00.4 [ps, pdf],

Afleveringsopgave

Opgave 39 [ps,pdf]

Rettelse til opgaven: Erstat "Udvidet Euklid fra afsnit 6.4.1" med "ExtendedEuklid fra afsnit 2.4.1". Variablerne p,q,s,t skal rettes til hhv m,n,p,q (dvs p->m, q->n, s->p, t->q). I invarianten i 39b skal m og n rettes til m0 og n0. Inputbetingelsen i 39b skal vaere: m,n>=1.

(korrigeret udgave af Opgave 39 [ps,pdf])

Uge 14

Forelæsninger

Mandag den 31/3-2003, kl 12-14

• [HS] Transitionssystemer 2.3.2, 2.5-6, gennemgang af opgave 36 (forelæser Erik Meineche Schmidt; slides [HS, Kap. 2-3])

Torsdag den 3/4-2003, kl. 14-16 (forelæsningen er flyttet til Auditorium F og starter kl. 15.00 (præcist!)).

• [HS] Transitionssystemer 3.1-3 (forelæser Erik Meineche Schmidt; slides [HS, Kap. 2-3])

Øvelser

[GT] C-5.9, C-5.13

S98.5 [ps, pdf], S00.2 [ps, pdf], A00.3 [ps, pdf], S93.3 [ps, pdf]

Afleveringsopgave

[GT] C-5.10

Uge 13

Forelæsninger

Mandag den 24/3-2003, kl 12-14

• [HS] Transitionssystemer 1.4.1-2, 1.5.2-3, 1.5.5, 1.5.6 (forelæser Erik Meineche Schmidt; slides [HS, Kap. 1])

Torsdag den 27/3-2003, kl. 14-16 (forelæsningen er flyttet til Auditorium F)

• [HS] Transitionssystemer 2.1-2, 2.3.1, 2.4.1 (forelæser Erik Meineche Schmidt; slides [HS, Kap. 2-3])

Øvelser

Opgave 28 [ps,pdf], Opgave 17 [ps,pdf], Opgave 18 [ps,pdf], Opgave 35 [ps,pdf]

V93.6 (Eksamensopgave 6 fra Vinteren 1993) [ps, pdf]

Afleveringsopgave

A96.3 [ps, pdf]

Bemærknimg

De fleste eksamensopgaver bruger notation fra programmeringssproget TRINE, som blev anvendt på det tidspunkt, hvor opgaven blev stillet. Forskellene fra JAVA-notation er som hovedregel selvforklarende og vil ellers blive kommenteret i forbindelse med de enkelte opgaver.

Til brug for eksamensopgave V93.6 er det nyttigt at vide, at A.(i) er TRINE-notation for array-referencer, dvs. er ækvivalent med A[i].

Uge 12

Forelæsninger

Mandag den 17/3-2003, kl 12-14

• [HS] Transitionssystemer 1.1-3, 1.4.0, 1.5.1 (forelæser Erik Meineche Schmidt; slides [HS, Kap. 1])

Torsdag den 20/3-2003, kl. 14-16

• Dynamisk programmering [GT] Kap. 5.3, 9.4

Øvelser

[GT] R-4.4, R-4.9, C-4.9, C-4.19, C-4.21, C-4.22, C-4.25

Opgave 29 [ps,pdf]

Afleveringsopgave

Opgave 33 [ps,pdf]

Uge 11

Forelæsninger

Mandag den 10/3-2003, kl 12-14

• Bucketsort, radixsort [GT] Kap. 4.5-4.6
• Multiplikation af lange heltal og matricer [GT] Kap. 5.2.2-5.2.3

Torsdag den 13/3-2003, kl. 14-16

• Del-og-kombiner [GT] Kap. 5.1-5.2

Øvelser

[GT] R-3.10, R-3.12, R-3.14, C-3.14

Opgave 4 [ps,pdf], Opgave 7 [ps,pdf], Opgave 15 [ps,pdf], Opgave 16 [ps,pdf]

Afleveringsopgave

Opgave 13 [ps,pdf]

Uge 10

Forelæsninger

Mandag den 3/3-2003, kl 12-14

• Merge-sort, union-find [GT] Kap. 4.1-4.2 (ikke side 232-234)

Torsdag den 6/3-2003, kl. 14-16

• Quick-sort, selektion, nedre grænse for sortering [GT] Kap. 4.3-4.4, 4.7-4.8

Øvelser

[GT] C-2.31, C-2.32, C-2.33, C-2.34, C-3.1, C-3.3

Opgave 12 [ps,pdf],

Afleveringsopgave

Opgave 11 [ps,pdf] (trykfejl: erstat "afsnit 6.3" med "afsnit 2.4.3")

Uge 9

Forelæsninger

Mandag den 24/2-2003, kl 12-14

• Søgetræer, AVL-træer [GT] Kap. 3.1-3.2

Torsdag den 27/2-2003, kl. 14-16

• (2,4)-træer, rød-sorte træer [GT] Kap. 3.3

Øvelser

[GT] R-2.3 R-2.5, R-2.14, R-2.15, C-2.11, C-2.12, C-2.20

Opgave 6 [ps,pdf], Opgave 9 [ps,pdf]

Afleveringsopgave

Opgave 10 [ps,pdf]

Uge 8

Forelæsninger

Mandag den 17/2-2003, kl 12-14

• Prioritetskøer, heaps [GT] Kap. 2.4

Torsdag den 20/2-2003, kl. 14-16

• Hashtabeller [GT] Kap. 2.5.1-2.5.5

Øvelser

[GT] R-1.10-14, C-1.4, C-1.6 (trykfejl: første tilfælde skal være "n=0") , C-1.17, C-1.18, C-2.5, C-2.7

Afleveringsopgave

Opgave 5 [ps,pdf] (trykfejl: "side 79" skal være "side 61")

Uge 7

Forelæsninger

Mandag den 10/2-2003, kl 12-14

• Stakke, køer [GT] Kap. 2.1-2.2

Torsdag den 13/2-2003, kl. 14-16

• Træer [GT] Kap. 2.3

Øvelser

[Bentley] 6.6.1, 6.6.2, 7.7.5, 7.7.9

[GT] R-1.2, R-1.3, R-1.6, R-1.15, R-1.18, C-1.7, C-1.8, C-1.9

Afleveringsopgave

Opgave 2 [ps,pdf]

Uge 6

Forelæsninger

Mandag den 3/2-2003, kl 12-14

• Introduktion til dADS
• Introduktion til algoritmer, [Bentley] Kap. 5.1,6.1-2,7.1-7.2

Torsdag den 6/2-2003, kl. 14-16

• Introduktion til algoritmer, [Bentley] Kap. 7.3-7.5
• Analyseværktøjer, [GT] Kap. 1.1-1.2

Øvelser

Opgaver til uge 6

Afleveringsopgave

Opgave 1 [ps,pdf]

Forklaring

Ugesedlen er ordnet efter faldende ugenummer, så den mest interessante information står øverst. Ugesedlen anfører til hver uge, hvilke forelæsninger der har været holdt, og hvilke forelæsninger der planlægges holdt i nærmeste fremtid. De anførte øvelsesopgaver bliver gennemgået til TØ i den pågælden de uge. De vil typisk behandle stof fra den foregående uge. Afleveringsopgaven skal regnes og afleveres i udgangen af den pågældende uge, typisk i week-enden, efter aftale med holdets instruktor.

For prins Knud: 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.