T-79.5201 Discrete Structures (4 cr) P VAutumn 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
General
LecturesScanned copied of lecture notes available for download, courtesy of Kim Blomqvist.
Tutorial problemsProblem sets will be available here as the course progresses.
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 19 Dec 4 p.m. (Two days before the exam.)
ExamsThe 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 materialThe course will follow, at a general level, the monograph:
General literature
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.
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.
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.
[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links] Latest update: 09 March 2008. Pekka Orponen |