TCS / Studies / T-79.5201 Discrete Structures
Helsinki University of Technology, Laboratory for Theoretical Computer Science

T-79.5201 Discrete Structures (4 cr) P V

Autumn 2006

The 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

  • [13 Dec 2006] The lectures and tutorials for this autumn are over; many thanks for your active participation. The autumn exam for the course is scheduled for Fri 22 Dec 1-3 p.m. in Lecture Hall T1. Please verify the time and place from the DCSE department exam schedule, and remember to register for the exam via TOPI. Note that the exam is "open book": you may bring the typeset lecture notes and solutions to exercises with you. Also a standard non-programmable function calculator is permitted, but no other material or devices.
  • [13 Dec 2006] Please provide feedback on the course via the department's course feedback system. The electronic questionnaires open Wed 13 Dec and close Wed 3 Jan.
  • [3 Dec 2006] Third home assignment has been published. Due date Wed 20 Dec, 4:00 p.m.
  • [3 Dec 2006] No lecture or tutorial on Wed 6 Dec. (Independence day.)
  • [16 Nov 2006] Second home assignment has been published. Due date Wed 29 Nov, 12:15 p.m.
  • [25 Oct 2006] No lecture or tutorial on Wed 1 Nov. (Exam week.)
  • [11 Oct 2006] First home assignment has been published. Due date Wed 25 Oct, 12:15 p.m.
  • [7 Sep 2006] No lecture or tutorial on Wed 20 Sep and Wed 18 Oct. (Lecturer abroad.)
  • [10 Aug 2006] First lecture Wed 13 Sep 12-14, room TB353.
  • [10 Aug 2006] Registration for the course is by TOPI.

General

  • Lectures: Pekka Orponen 13 Sep - 13 Dec, Wed 12-14, room TB353.
  • Tutorials: Wed 14-15, room TB353.
  • Examination: Fri 22 Dec, T1.
  • Registration by TOPI.
  • Prerequisites: First two years' mathematics courses including introductory discrete mathematics (Mat-1.2991/Mat-1.128) and elementary complex analysis (e.g. Mat-1.1131/Mat-1.413). Familiarity with algorithm design (T-106.4100/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.

Tutorial problems

Problem sets will be available here as the course progresses. Most of the problems are likely to be the same as in Autumn 2004.

Home assignments

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

Exams

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.

Problem sets from previous instalments of the course:

Course material

Typeset 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:
  • 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.

General literature

  • 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-2006.
      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: 23 January 2008. Pekka Orponen