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.

Current

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.

General

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

Exams

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)

Tutorial problems

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.

Compulsory assignments

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.

Course material

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).