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

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]


Current

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


General

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

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

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

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.
  • Fri 10 Dec 9-12, T1. Problems: Finnish (ps, pdf), English (ps, pdf).
  • Fri 7 Jan 15-18, T1. Problems: Finnish (ps, pdf).

Course material

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.

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