DIKU

Datalogisk Institut
Københavns Universitet

Datalogi 2P : Algoritmik

Siste ændring 23.6.1999 11.00

Jyrki

Afslutningsøl

Instruktorerne giver (2 kasser) øl på caféen den 17/7 1999 fra kl. 12

Kursusbog

T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, The MIT Press, Cambridge (1990)

Spørgsmål til mundlig eksamen F99

  1. Divide and conquer
  2. Prune and search
  3. Greedy strategy
  4. Problem transformation
  5. Dynamic programming
  6. Incremental method
  7. Depth-first search and strongly connected components
  8. Single-source shortest paths
  9. All-pairs shortest paths
  10. Maximum flow: concepts and definitions
  11. Maximum flow: the Ford-Fulkerson method
  12. NP-completeness: concepts and definitions
  13. NP-completeness of the vertex-cover and subset-sum problems
  14. NP-completeness of the hamiltonian-cycle and travelling-salesman problems
  15. Branch and bound
  16. Approximation algorithms

Studerende kan efter eget valg eksamineres på dansk eller engelsk.

Pensum til eksamen

Pensum er angivet i kursusbeskrivelsen 1998-99 Punkt 9.

Hjemmeopgaver

Opgaverne er taget fra Introduction to Algorithms af Cormen, Leiserson og Rivest (bemærk, at opgaveangivelser af typen x-y henviser til opgave y placeret i slutningen af kapitel x, mens x.y-z henviser til opgave z placeret efter afsnit x.y) med mindre andet er angivet. Sidetal er skrevet i parentes.

uge 48 (ansvarlig lærer: Sofus): on-line opgaver som deles ud ved øvelserne

uge 49 (ansvarlig lærer: Jyrki): 1.2-1, 1.4-1, 1-2, 2.1-1, 2.1-4, 2.2-4

uge 50 (ansvarlig lærer: Jarl): 1.3-2, 1.3-5, 4.1-6, 4.4-2, 4-1, 35.4-2

uge 51 (ansvarlig lærer: Signe): 4-4, 8.3-2, 8-4, 10.1-2, 10.2-1, 10.3-1

uge 5 (ansvarlig lærer: Signe): 10-2, 17.1-3, 17.2-1, 17.2-6, 17-1, 24.2-4

uge 6 (ansvarlige lærere: alle): 22.2-3 (446), 22.3-2 (450), 22-3 (460-461), 32.2-2 (790), 32.2-3 (791), 32.2-4 (791)

uge 7 (ansvarlig lærer: Jyrki): 2.2-7 (37), 16.3-2 (319), 16.3-4 (319), 16.3-6 (319-320), 16-3 (325-326), 17.2-2 (336)

uge 8 (ansvarlig lærer: Jyrki): 13-3 (260-262), 14.1-4 (265), 14.2-5 (267), 14-2 (278-279), 35.2-7 (898), 35.3-2 (907)

uge 9 (ansvarlige lærere: Jarl, Jyrki, Signe): 12.3-2 (232), 12.3-5 (232), 18.1-3 (360), 18.2-2 (363), 18.3-2 (366), opgave om dynamisk lager (halvdelen af O1 fra sidste år)

uge 10 (ansvarlig lærer: Jyrki): 2-5 (39-40), 7.4-3 (149), 7.5-4 (151), 7.5-5 (151), 20.2-10 (417), 20-2 (418-419), 23.4-3, 23.4-5, 23.5-4, 23.5-7, 23.3-10

uge 11 : 25.2-5, 25.2-6, 25.3-4, 25-3, 26.1-1, 26.1-4, 26.1-6, 26.1-6, 26.1-8, 26.2-3

uge 12 : O2 fra 1998(bilver udleveret til forelæsning), 27-1,"Offshore Adventures"(bilver udleveret til forelæsning), opsamling af gamle opgaver!

uge 13 :

Beregningsmodeller:

Show that a RAM can simulate a SAM. If the SAM requires T(n) time and S(n) space to solve a problem of size n, how much resources does the corresponding RAM require a) under the unit-cost measure and b) under the log-cost measure.

Show that a SAM can simulate a RAM. If the RAM requires T(n) time and S(n) space to solve a problem of size n, how much resources does the corresponding SAM require when the cost of the RAM is measured by using a) the unit-cost measure and b) the log-cost measure.

uge 14 :Påskeferie

uge 15 :

Beregnelighed:

Show that any proposed algorithm for the halting problem must fail on infinitely many inputs.

Consider the problem of deciding whether the set of possible outputs of an algorithm is finite or infinite. Prove that this problem is not computable.

Samt 36.1-1, 36.1-2, 36.1-4, 36.1-6, 36.1-7, 36.2-1, 36.2-6

uge 16 : 36.2-4, 36.3-1, 36.3-2, 36.3-5, Problem 36-1 a, b

uge 17 : 36.5-2, 36.5-3, 36.5-4, 36.5-5, Problem 36-1 c, d

uge 18 : Kursusbog 6 Del 1 opgave 1, 2, 3, 5, 6, 7(a)

uge 19 : 37.1-1, 37.1-2, 37.1-4, 37.2-1, 37.2-4, Problem 37-1

uge 20 : 37.4-1, 37.4-2, 37.4-3, Problem 37-2

Forelæsninger

Dato Lærer Kapitler Tema
23. nov. Jyrki Chapter 1
Chapter 2		 Introduction to algorithmics
Sorting
Various runtime bounds
Growth of functions
25. nov. Jyrki Chapter 1, Section 1.3
Chapter 4 (not Section 4.4)
Chapter 10, Section 10.1
Chapter 31, Section 31.2
Chapter 35, Section 35.4 		Divide and conquer
Minimum and maximum
Sorting
Closest pair
Matrix multiplication
Recurrences
2. dec. Jyrki Chapter 8
Chapter 10		 Randomized algorithms
Sorting
Selection
Sieving (prune and search)
Prime numbers
Selection
7. dec. Jyrki Chapter 17 (not Sections 17.4-17.5)
Chapter 24		 Greedy strategy
Minimum spanning trees
Activity selection
Minimum-redundancy codes
9. dec. Jyrki
Stephen		 Chapter 22 (not Section 22.4) Disjoint sets
Minimum spanning trees
Connected components
16. dec. Jyrki Chapter 32, Sections 32.1-32.2 Problem transformation
Polynomial multiplication
1. feb. Jyrki Chapter 16 (not Section 16.4) Dynamic programming
Making change
Matrix chain multiplication
Longest common subsequence
3. feb. Jyrki Chapter 13 (not Section 13.4)
Chapter 14		 Ordered dictionary
Binary search trees
Height-balanced search trees
O1 stilles
10. feb. Jyrki Chapter 35, Sections 35.1-35.3 Incremental method
Sorting
Detecting intersection of line segments
Convex hulls
15. feb. Jyrki Chapter 12 (not Section 12.4) Unordered dictionary
Direct-access tables
Hash tables
Universal hashing
17. feb. Jyrki Chapter 18
Chapter 7		 Amortized analysis
Stack operations
Incrementing a binary counter
Dynamic tables
Priority queues
Binary heaps
O1 afleveres
24. feb. Jyrki Chapter 24
Chapter 20
Chapter 21		 Minimum spanning trees
Binomial heaps
Fibonacci heaps
1. mar. Jakob Chapter 23 Depth-first search
Strongly connected components
3. mar. Jakob Chapter 25, Sections 25.1-25.3 Single-source shortest paths
10. mar. Jakob Chapter 26, Sections 26.1-26.2 All-pairs shortest paths
O2 stilles
15. mar. Jakob Chapter 27, Sections 27.1-27.3 Maximum flow: classical algorithms
17. mar. Jakob Chapter 27, Section 27.4 Maximum flow: preflow-push algorithms
24. mar Jyrki Chapter 1, Section 1.2 Models of computation
Cost models
Criticism
O2 afleveres
29. mar. Jyrki [1, Section 3.2], [2, pp. 206-244] Spectrum of computational complexity
Halting problem
Totality problem
Equivalence problem
7. apr. David Chapter 36, Sections 36.1-36.3
 The class NP and NP-completeness
12. apr.
 David
 Chapter 36, Sections 36.4-36.5
 Reduction among NP-complete problems
14. apr. David Chapter 36, Section 36.5 More NP-complete problems
21. apr. David
 Kursusbog 5, Del 1
 The branch-and-bound paradigm
O3 stilles
26. apr.
 David


 Kursusbog 5, Del 1

 Design issues for branch-and-bound algorithms
28. apr. David Chapter 37, Sections 37.1-37.2 Approximation algorithms: the vertex-cover and travelling-salesman problems
5. maj David Chapter 37, Section 37.4
 Approximation algorithms: the subset-sum problem
O3 afleveres
10. maj
 David
 Kursusbog 5, Del 2

 Heuristics
12. maj David Kursusbog 5, Del 2 Well solved special cases
17. maj David & Jakob   Eksamensforberedelser
9. juni David, Jakob & Jyrki   Spørgetime
[1] Les Goldschlager and Andrew Lister, Computer Science: A Modern Introduction, Prentice/Hall International (1982)
[2] Dexter C. Kozen, Automata and Computability, Springer-Verlag (1997)

Kursusbeskrivelse

Dat2P 1998 - 1999

Dat2P 1997 - 1998

Nyhedsgruppe

diku.dat2p-algoritmik

Transparenter

Se Faron Mollers hjemmeside i Uppsala.

Julelæsning

Nogle klassiske artikler er tilgængelige fra kopirum.

O1

This exercise is on multiplication of long integers. You can load the files related to the exercise via this page. Beware of the latest version of each file.

  • O1-1999.ps (latest version: 1.0): the problem formulation in PostScript format.
  • driver.cc (latest version: 1.3): a C++ driver program to carry out an experiment.
  • makefile (latest version 1.0): to make your life easier.
  • integer.cc (latest version 1.5): you should write the missing multiplication routines in this C++ class.
  • word.cc (latest version 1.2): a C++ class for double precision arithmetic.
  • multiplication.gp (latest version 1.0): a gnuplot control file to draw a plot about your results.
  • multiplication.sh (latest version 1.1): a shell script to carry out a series of experiments.

    • O2 rettelse

    Linie 6 fra oven: "x=yi, y=xi, i tilhører F" rettes til "x=xi, i tilhører F og y=yj, j tilhører F"

    Her har jeg brugt ordet "tilhører" istedet for det buede E, som fås med \in i LaTeX

    O3 Opgaveformulering og instanser

    Instanser