AARHUS UNIVERSITET
DATALOGISK INSTITUT

Algoritmer og Datastrukturer, Efterår 2002
[for matematik-økonomi studerende]
Tid og Sted · Kursus beskrivelse · Ugesedler · Opgaver · Undervisere · Litteratur · Eksamensform · Sprog · Credits · Semester

Tid og sted

Torsdag 11.15-12.00 (forelæsning, colloquium B4), torsdag 12.15-14.00 (øvelser colloquium B4), og Fredag 10.15-12.00 (forelæsning, colloquium B3).

Kursus beskrivelse

Datastrukturer: lister, træer, hashtabeller, skip-lister.

Dataabstraktioner: stakke, køer, prioritetskøer, ordbøger, mængder.

Algoritmer: søgning, sortering, selektion, fletning, mønstergenkendelse.

Grafalgoritmer: grafgennemløb, sammenhængsegenskaber, topologisk sortering, udspændende træer, korteste veje, transitiv lukning

Paradigmer: del-og-kombiner, dynamisk programmering, grådighed

Analyse og syntese: worstcase, amortiseret og forventet udførelsestid; udsagn, invarianter, gyldighed, terminering og korrekthed.

Ugesedler

UgeDatoIndhold
3712. september[Bentley] Kap. 5-6
Opgaver:
uge 37
13. september[Bentley] Kap. 7
[G&T] Kap. 1.1-1.2
3819. september Opgaver:
[Bentley] 6.6.1, 6.6.2, 7.7.5, 7.7.9
[G&T] R-1.6, R-1.15, R-1.18, C-1.7, C-1.8, C-1.9
20. september [G&T] Kap. 1.3-1.5, 2.1-2.2
3926. september [G&T] Kap. 2.3-2.4.2
Opgaver:
[G&T] R-1.10-14, C-1.4, C-1.17, C-1.18, C-1.32
Afleveringsopgave:
Opgave 2
27. september [G&T] Kap. 2.4.3-2.4.4, 2.5.1-2.5.5
403. oktober [G&T] Kap. 2.5.6, 3.1
Opgaver:
[G&T] R-2.3, R-2.14, C-2.7, C-2.11, C-2.12, C-2.20
Afleveringsopgave:
Opgave 4
4. oktober [G&T] Kap. 3.1
4110. oktoberAflyst
11. oktoberAflyst
42 17. oktober Opgaver:
Opgave 7, 9
[G&T] C-2.21, C-2.22, C-2.30, C-2.31, C-2.32
Afleveringsopgave:
Opgave 11
18. oktober [G&T] Kap 3.3
4324. oktober [G&T] Kap 3.5
Opgaver:
[G&T] R-3.1, R-3.12, R-3.14, C-3.1 C-3.14
Opgave 15
Afleveringsopgave:
Opgave 13
25. oktober[G&T] Kap. 4.1, 4.3-4.6, 4.8
4431. oktober[G&T] Kap 4.2, 4.7
Opgaver:
[G&T] R-4.11, C-4.2, C-4.4, C-4.8, C-4.9
Opgave 16
Afleveringsopgave:
[G&T] Opgave C-4.22
1. november[G&T] Kap. 4.2, 5.1
457. november [G&T] Kap. 5.2
Opgaver:
[G&T] C-4.7, C-4.16, C-4.19, C-4.20, C-4.25
Afleveringsopgave:
Opgave 33
8. november[G&T] Kap. 5.3, 9.4
4614. november [G&T] Kap. 6.1-6.3.1
Opgaver:
[G&T] C-5.13
Opgave 29
Eksamensopgave S00.3
15. novemberAflyst
4721. novemberAflyst
Afleveringsopgave:
[G&T] C-5.10
22. novemberAflyst
4828. november [G&T] Kap. 6.3.3-6.47
Opgaver:
[G&T] C-5.11, C-6.3, C-6.12, C-6.18, C-6.19
Afleveringsopgave:
[G&T] C-6.9
29. november[G&T] Kap. 7.1
495. december [G&T] Kap. 7.2
Opgaver:
Eksamensopgave A00.2, S02.2
[G&T] C-7.2, C-7.6, C-7.7
Afleveringsopgave:
Eksamensopgave S00.1
6. december[G&T] Kap. 7.3
5012. december[G&T] Kap. 7.3
Opgaver:
[G&T] R-7.2
Eksamensopgave S00.2, A02.3, A00.1, S01.1 (+ bevis sætningen sidst i opgaven)
Afleveringsopgave:
Eksamensopgave A01.1
13. december[G&T] Kap. 9.1
5119. decemberAfslutning
20. decemberAflyst

Opgaver

Opgaver 1-42

Postscript: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

PDF: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 (samlet)

Gamle eksamensopgaver (A=august, S=sommer, V=vinter)

Postscript: S91 V92 S92 V93 S93 V94 S94 A94 V95 S95 A95 V96 S96 A96 S97 A97 S98 A98 S99 A99 S00 A00 S01 A01 S02 A02

PDF: S91 V92 S92 V93 S93 V94 S94 A94 V95 S95 A95 V96 S96 A96 S97 A97 S98 A98 S99 A99 S00 A00 S01 A01 S02 A02

Undervisere
Gerth Stølting Brodal og Rolf Fagerberg.
Litteratur
[G&T]
Michael T. Goodrich and Roberto Tamassia: Algorithm design - Foundations, Analysis and Internet Examples. John Wiley & Sons, Inc. ISBN: 0-471-38365-1.
[Bentley]
Kapitel 5, 6 og 7 fra Jon Bentley: Programming Pearls, Addison-Wesley. First edition, 1986.
[H&S]
Mikkel Nygaard Hansen og Erik Meineche Schmidt: Transition Systems, April 2002 [ps | pdf].
Eksamensform
Afløsning
Sprog
Dansk
Credits
10 ECTS
Semester
Efterår 2002
Denne side vedligeholdes af Gerth Stølting Brodal <gerth@cs.au.dk>.