TCS /
Studies /
T-79.149 /
Autumn 2001
T-79.149 Discrete Structures
Autumn 2001 (2 cr)
This year's instantiation of
the course covers some of the fundamental techniques of enumerative
combinatorics, with applications to the analysis of algorithms.
The emphasis will be on the methodology of generating functions,
especially their formal construction, and the exact and asymptotic
analysis of coefficient sequences using e.g. tools from
complex function theory.
- Course exam Wed 12 Dec, 16-19, T1. The exam will
be "open book", i.e. reference use of all written &
printed material will be permitted. However programmable
calculators may not be used.
- Lectures:
Pekka Orponen,
19 Sep - 5 Dec, Wed 12-14, room TB353
- Tutorials:
Wed 14-15, room TB353
- Grading:
Home assignments, exam.
- Registration by
TOPI
or by attending the first two lectures
- Wed 12 Dec 2001, 16-19, T1.
(Problems in ps,
pdf)
- Wed 9 Jan 2002, 9-12, T2. Cancelled!
- Sat 16 Feb 2002, 10-12, D
(Problems in ps,
pdf)
- Problem Set 1:
Finnish
(ps,
pdf),
English
(ps,
pdf)
- Problem Set 2:
Finnish
(ps,
pdf),
English
(ps,
pdf)
- Problem Set 3:
Finnish
(ps,
pdf),
English
(ps,
pdf)
- Problem Set 4:
Finnish
(ps,
pdf),
English
(ps,
pdf)
- Problem Set 5:
Finnish
(ps,
pdf),
English
(ps,
pdf)
- Problem Set 6:
Finnish
(ps,
pdf),
English
(ps,
pdf)
- Problem Set 7:
Finnish
(ps,
pdf),
English
(ps,
pdf)
- No problem set for Wed 14 Nov.
- Problem Set 8:
Finnish
(ps,
pdf),
English
(ps,
pdf)
- Problem Set 9:
Finnish
(ps,
pdf),
English
(ps,
pdf)
- No problem set for Wed 5 Dec.
- There will be three compulsory assignments of four problems each.
These will not be graded, but all the problems must be personally
solved and handed in to the lecturer in order to be eligible to take
the exam on Wed 12 Dec.
Assignments 1 and 2 are due at the beginning
of the weekly lecture on Weeks 5 and 9 (resp.) of the course,
and the due date for assignment 3 is Mon 10 Dec 4 p.m. (Two
days before the exam.)
- Assignment 1
(ps,
pdf),
due Wed 17 Oct 12:15 p.m.
- Assignment 2
(ps,
pdf),
due Wed 14 Nov 12:15 p.m.
- Assignment 3
(ps,
pdf),
due Mon 10 Dec 4 p.m.
- P. Flajolet, "Mathematical methods in the analysis of
algorithms and data structures,"
pp. 225-304 in E. Börger (Ed.), Trends in Theoretical
Computer Science. Computer Science Press 1988.
- D. H. Greene, D. E. Knuth, Mathematics for the Analysis
of Algorithms, 3rd Ed. Birkhäuser 1990.
Copies of the lecture notes, solutions to the tutorial problems,
and the Flajolet paper are available for inspection in
the theory lab office (TB336).
- Handbooks
R. Graham et al. (Eds.), Handbook of Combinatorics, 2 Vols.
Elsevier/North-Holland 1995.
K. Rosen et al. (Eds.), Handbook of Discrete and Combinatorial
Mathematics. CRC Press 1999.
N. J. A. Sloane, S. Plouffe, The Encyclopedia of Integer Sequences.
Academic Press 1995.
- Textbooks
P. Flajolet, R. Sedgewick,
Analytic Combinatorics. Manuscript, 2001.
I. P. Goulden, D. M. Jackson, Combinatorial Enumeration.
Wiley 1983.
R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics: A
Foundation for Computer Science, 2nd Ed. Addison-Wesley 1994.
M. Hofri, Analysis of Algorithms: Computational Methods and Mathematical
Tools. Oxford University Press 1995.
R. P. Stanley, Enumerative Combinatorics, 2 Vols.
Cambridge University Press 1996/1999.
H. S. Wilf,
Generatingfunctionology, 2nd Ed. Academic Press 1994.
- Links
Latest update: Sep 19, 2004
by orponen@tcs.hut.fi