|
T-79.149 Discrete Structures (2 cr) P V
Autumn 2004
This autumn's instantiation of the course is concerned
with enumerative combinatorics,
i.e. estimating the sizes of families of combinatorial objects,
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. This version of the course was
previously given in Autumn 2001.
[Current]
[General]
[Lectures]
[Tutorials]
[Assignments]
[Exams]
[Course material]
[Literature]
Previous years:
[Autumn 2003]
[Autumn 2001]
[Spring 2001]
- On Wednesday 10 November, there is no tutorial session;
instead the lecture starts already at 12:15.
- By popular request, the ordering of lectures and tutorials
has been changed: tutorials are now Wednesdays 12-13,
and lectures follow them Wednesdays 13-15.
- Registration for the course is still open at
TOPI.
- Lectures:
Pekka Orponen
15 Sep - 1 Dec, Wed 13-15, room TB353.
- Tutorials:
Wed 12-13, room TB353.
- Examination:
Fri 10 Dec 9-12, T1.
- Registration by
TOPI.
- Prerequisites: First two years' mathematics courses including
introductory discrete mathematics (Mat-1.128) and elementary
complex analysis (e.g. Mat-1.413). Familiarity with algorithm
design (e.g. T-106.410) an asset.
- Grading: Exam 30 points, three home assignments 8 points
each, tutorials 6 points, total 60 points.
Minimum passing grade (1) at 30 points, linear scale
up to maximum grade (5) at 54 points.
Problem sets will be available here as the course progresses.
Most of the problems are likely to be the same as in
Autumn 2001.
- 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 10 Nov.
- Problem Set 8: Finnish
(ps,
pdf),
English
(ps,
pdf).
- Problem Set 9: Finnish
(ps,
pdf),
English
(ps,
pdf).
- No problem set for Wed 1 Dec.
- There will be three home assignments of four problems each.
All the problems must be personally solved and handed in to the
lecturer by the given deadlines.
Assignments 1 and 2 are due at the beginning
of the weekly lecture on Weeks 6 and 10 (resp.) of the course,
and the due date for assignment 3 is Wed 8 Dec 4 p.m. (Two
days before the exam.)
- Assignment 1:
Finnish
(ps,
pdf),
English
(ps,
pdf).
Due Wed 20 Oct 12:15 p.m.
- Assignment 2:
Finnish
(ps,
pdf),
English
(ps,
pdf).
Due Wed 17 Nov 12:15 p.m.
- Assignment 3:
Finnish
(ps,
pdf),
English
(ps,
pdf).
Due Wed 8 Dec 4 p.m.
The exams are "open book": you may bring the typeset
lecture notes and solutions to exercises with you to the exam.
Also a standard non-programmable function calculator is permitted,
but no other material or devices.
- Fri 10 Dec 9-12, T1. Problems:
Finnish
(ps,
pdf),
English
(ps,
pdf).
- Fri 7 Jan 15-18, T1. Problems:
Finnish
(ps,
pdf).
Typeset lecture notes in Finnish from Autumn 2001
(updated in Autumn 2004) are available here in both
one page per sheet
(pdf) and
two pages per sheet
(pdf) format.
The lecture notes are mainly based on the following
texts:
- 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.
(
Related tech report.)
- D. H. Greene, D. E. Knuth, Mathematics for the Analysis
of Algorithms, 3rd Ed. Birkhäuser 1990.
- H. S. Wilf,
Generatingfunctionology, 2nd Ed. Academic Press 1994.
- 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, 1994-2004.
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.
D. H. Greene, D. E. Knuth, Mathematics for the Analysis of
Algorithms, 3rd Ed. Birkhäuser 1990.
M. Hofri, Analysis of Algorithms: Computational Methods and Mathematical
Tools. Oxford University Press 1995.
S. K. Lando, Lectures on Generating Functions.
American Mathematical Society 2003.
R. P. Stanley, Enumerative Combinatorics, 2 Vols.
Cambridge University Press 1996/1999.
H. S. Wilf,
Generatingfunctionology, 2nd Ed. Academic Press 1994.
- Links
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 12 September 2006.
Pekka Orponen
|