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 2007 (periods I and II)

The course T-79.5201 replaces the course T-79.149 Discrete Structures .

This autumn's instalment of the course is concerned with probabilistic combinatorics, i.e. the characteristics of random ensembles of combinatorial structures such as graphs, set systems, codes, geometric arrangements etc. Typical issues considered in this field include e.g. the "emergence" of various graph properties (subgraph structures, large components, connectivity) in large random graphs, the existence of good error-correcting codes, and the design of low-discrepancy point sets for geometric approximation. Mathematical ideas and techniques from this area are finding increasing use in the design and analysis of modern, efficient randomised algorithms.


[Current] [General] [Lectures] [Tutorials] [Assignments] [Exams] [Course material] [Literature]

Previous years: [Autumn 2006] [Autumn 2004] [Autumn 2003] [Autumn 2001] [Spring 2001]


Current

  • [18 Dec 2007] 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 21 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 "semi-open book": you may bring copies of your lecture notes (also the photocopies of mine) and solutions to exercises with you. Also a standard non-programmable function calculator is permitted, but no other material or devices.
  • [18 Dec 2007] Please provide feedback on the course via the department's course feedback system. The electronic questionnaires open Mon 10 Dec and close Mon 7 Jan.
  • [11 Dec 2007] Third home assignment has been published. Due date Wed 19 Dec, 4 p.m.
  • [21 Nov 2007] Second home assignment has been published. Due date Wed 5 Dec, 12:15 p.m.
  • [21 Oct 2007] No lecture or tutorial on Wed 24 Oct (lecturer at a meeting) and Wed 31 Oct (exam week).
  • [21 Oct 2007] First home assignment has been published. Due date Wed 7 Nov, 12:15 p.m.
  • [25 Sep 2007] Scanned lecture notes now available for download.
  • [3 Aug 2007] First lecture Wed 19 Sep 12-14, room TB353.
  • [3 Aug 2007] Registration for the course is by TOPI.


General

  • Lectures: Pekka Orponen 19 Sep - 12 Dec, Wed 12-14, room TB353.
  • Tutorials: Wed 14-15, room TB353.
  • Examination: Fri 21 Dec, T1.
  • Registration by TOPI.
  • Prerequisites: First two years' mathematics courses including introductory discrete mathematics (Mat-1.2991/Mat-1.128) and probability theory (e.g. Mat-1.2600/Mat-2.090).
  • 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.

Lectures

Scanned copied of lecture notes available for download, courtesy of Kim Blomqvist.

Tutorial problems

Problem sets will be available here as the course progresses.

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 19 Dec 4 p.m. (Two days before the exam.)

Exams

The exams are "semi-open book": you may bring copies of your lecture notes and solutions to exercises with you to the exam. Printed texts (books) are however not permitted, because not everyone has equal access to them. Also a standard non-programmable function calculator is permitted, but no other material or devices.

Course material

The course will follow, at a general level, the monograph:
  • N. Alon, J. H. Spencer, The Probabilistic Method, 2nd Ed. Wiley Interscience 2000.
However, there is much more material in this book than can be covered on such a course. A shorter exposition of the key topics is:
  • J. H. Spencer, Ten Lectures on the Probabilistic Method, 2nd Ed. Society for Industrial and Applied Mathematics 1994.

General literature

  • Combinatorics: general
    • P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press 1994.
      R. Graham et al. (Eds.), Handbook of Combinatorics, 2 Vols. Elsevier/North-Holland 1995.
      S. Jukna, Extremal Combinatorics: With Applications in Computer Science. Springer-Verlag 2001.
      J. H. van Lint, R. M. Wilson, A Course in Combinatorics, 2nd Ed. Cambridge University Press 2001.

  • Combinatorics: probabilistic
    • B. Bollobás, Random Graphs, 2nd Ed. Cambridge University Press 2001.
      P. Erdös, J. H. Spencer, Probabilistic Methods in Combinatorics. Academic Press 1974.
      S. Janson, T. Luczak, A. Rucinski, Random Graphs. Wiley Interscience 2000.
      V. N. Sachkov, Probabilistic Methods in Combinatorial Analysis. Cambridge University Press 1997.

  • Algorithmic applications
    • B. Bollobás (Ed.), Probabilistic Combinatorics and Its Applications. American Mathematical Society 1991.
      M. Habib et al. (Eds.), Probabilistic Methods for Algorithmic Discrete Mathematics. Springer-Verlag 1998.
      M. Mitzenmacher, E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press 2005.
      R. Motwani, P. Raghavan, Randomized Algorithms. Cambridge University Press 1995.

  • Links


[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 09 March 2008. Pekka Orponen