Last updated June 4, 2010, 9pm
To find out what's new, make sure you press your browser's REFRESH button.
Final exam statistics posted (June 4). Click the "Statistics" tab on the banner.
Reminder. The last class of the term is Friday, June 4. Attendance is expected and will count toward the "class participation" portion of your grade (5%).
All-quiz (1-5) statistics posted (May 26). Click the "Statistics" tab on the banner.
All-homework (1-8) statistics posted (May 25).
Full exercise set #8 posted
(a set of DO exercises was added on May 22, 7:30am).
Due Monday, May 24.
Exercise set #9 also
posted (due Wednesday, May 26).
Click the "Exercises, homework" tab on the banner.
First batch of exercise set #8 posted (May 20). Due Monday, May 24. Click the "Exercises, homework" tab on the banner.
Quiz-4 and Quiz-4 statistics posted. Click the "Statistics" tab on the banner. DO: Solve the problems.
Homework 1-7 statistics posted (May 10). Click the "Statistics" tab on the banner.
Exercise set #7 posted. Due Monday, May 10. Click the "Exercises, homework" tab on the banner.
Quiz-3 and combined test statistics posted. Click the "Statistics" tab on the banner.
Test dates posted. Click "Grading, tests" on the banner.
Solutions to exercise set #4 posted. Click "Exercises, homework" on the banner, and then "Solutions #4" on the banner. Study the solutions carefully.
Exercise sets ##5 and 6 posted. Click the "Exercises, homework" tab on the banner. Set #5 is due Friday, April 30. Set #6 is due Monday, May 3. Do not mix the solutions; hand in the solutions on their due dates. Start early on the problems.
Quiz-2 statistics posted. Click the "Statistics" tab on the banner.
Exercise set #4 posted. Due Wednesday, Apr 21. Start early on the problems; it is best if you read and understand them before Monday's class. Click the "Exercises, homework" tab on the banner.
Second quiz posted. Click "Grading, tests" on the banner. Solve by Wednesday.
Exercise set #3 posted. DO exercises due Friday, Apr 16 (before the quiz). Click the "Exercises, homework" tab on the banner.
Quiz statistics posted. Click the "Statistics" tab on the banner.
First quiz posted. Solve all problems, including the bonus problems, by Monday, Apr 12.
Exercise set #2 posted. HW due Monday, Apr 12. Click the "Exercises, homework" tab on the banner.
Course description
Methods of enumeration, construction, and proof of existence of discrete structures are discussed in conjunction with the basic concepts of probability theory over a finite sample space (random variables, independence, expected value, standard deviation, and Chebyshev's and Chernoff's inequalities). Concepts of combinatorial optimization such as duality and good characterization are introduced. Topics include counting, generating functions, Latin squares, finite projective planes, graph theory, matchings, flows in networks, Ramsey theory, coloring graphs and set systems, extremal combinatorics. The highlights include unexpected applications of linear algebra and number theory. Mathematical puzzles will pepper the course. The instructor hopes that the course will be fun in many ways.
Prerequisites: The principal prerequisite for this class is a degree of mathematical maturity. Basic linear algebra will be helpful. It helps if you have taken Discrete Mathematics but it is not required.
Your primary text will be your course notes, so make sure you don't miss classes. If you do, you should copy somebody's class notes and discuss the class with them.
There will also be frequent web postings. Please always check this website.
Online texts: instructor's "Discrete Mathematics" lecture notes in PDF (preliminary, incomplete drafts):
Printed text:
J. H. van Lint, R. M. Wilson: "A Course in Combinatorics," Cambrdge University Press, ISBN# 0 521 00601 5
Recommended supplementary reading:
J. Matoušek, J. Nešetříl: "Invitation to Discrete Mathematics," by Oxford University Press, ISBN# 098502079.
Recommended background text:
Kenneth H. Rosen: Discrete Mathematics and its Applications (n-th edition, n=2,3,4,5,...)
Recommended reference:
The Discrete Mathematics 2009 course (CMSC37110) is a good source of relevant exercises; check out the homeworks and the tests.
Please send email to the instructor with answers to these questions, even if you are only sitting in on the class, did not register, answered the same questionnaire in an earlier class by the instructor, or have an unusual status. Your answers to these questions will help me better to plan the course. Please write "combinatorics data" in the subject.
Class MWF 11:30 - 12:20 Ry 276
Instructor: László Babai Ryerson 164 e-mail: laci(at)cs(dot)uchicago(dot)edu.
Office hours: by appointment (please send e-mail)