T-79.5201 Discrete Structures (4 cr) P VAutumn 2006The course T-79.5201 replaces the course T-79.149 Discrete Structures . This autumn's instalment 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 2004.
[Current]
[General]
[Lectures]
[Tutorials]
[Assignments]
[Exams]
[Course material]
[Literature]
Previous years (as T-79.149): [Autumn 2004] [Autumn 2003] [Autumn 2001] [Spring 2001] Current
General
Tutorial problemsProblem sets will be available here as the course progresses. Most of the problems are likely to be the same as in Autumn 2004.
Home assignmentsThere will be three home assignments of four problems each. All the problems must be personally solved and handed in to the lecturer or left in the lab's assignments mailbox (next to the TCS lab office TB336) 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 20 Dec 4 p.m. (Two days before the exam.)
ExamsThe 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.
Problem sets from previous instalments of the course: Course materialTypeset lecture notes in Finnish from Autumn 2001 (updated in Autumn 2004) are available here in both one page per sheet and two pages per sheet format. The lecture notes are mainly based on the following texts:
General literature
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.
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.
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links] Latest update: 23 January 2008. Pekka Orponen |