CMSC 27100-1
Discrete Mathematics - Autumn 2008

Instructor: Caroline J. Klivans
office: Eckhart 308A
e-mail: cjk (at) math.uchicago.edu
office hours: Mon. 2:30-3:30 E308A and by appointment

TAs: Ankan Saha
office: Ryerson 257
office hours: Tu 5:30-6:30 Ry 257, Th 5:30-6:30 Ry 257

Duru Turkoglu
office: Ryerson 256
office hours: Mon 5-6 Ry 257, Tu 4:30-5:30 Ry 276
Lecture: MWY 11:30-12:20 Ryerson 251 Note room change

Course Description: This course covers a variety of topics from discrete mathematics with an emphasis on mathematical techniques and rigorous proof. Possible topics include counting, number theory, graph theory, probability, Markov models, asymptotics, and linear algebra.

Text: (Available at the Seminary Co-op)
Discrete Mathematics and It's Applications by K. Rosen
Due to the ridiculous price of this textbook, I will put as many copies as possible on reserve in the math library.
A nice reference text:
An Invitation to Discrete Mathematics by Matousek and Nesetril
Exams: There will be two midterms and a final. Midterm 1: Friday Oct. 24th, Midterm 2: Wednesday Nov. 19th Final: Monday, Dec. 8th, 10:30-12:30, Ry 251.
Homework: There will be weekly homework assignments due at the beginning of class each Wednesday. You are encouraged to work together on solving homework problems. All students must turn in their own write-up of the solutions. If you work with other people, you must put their names clearly on the write-up.

Homework 1, due Wednesday Oct. 8th

Homework 2, due Wednesday Oct. 15th

Homework 3, due Wednesday Oct. 22nd

Homework 4, due Wednesday Nov. 5th

Homework 5, due Wednesday Nov. 12th

Homework 6, due Wednesday Nov. 19th

Homework 7, due Wednesday Dec. 3rd

Homework 7, sketch of solutions

A few notes on Markov Chains by Laci Babai. Please note these are preliminary notes and may contain small mistakes, typos, gaps... Your class notes are still your best reference.

Readings: Here I will post the approximate sections in the texts covering the material from class.

Week One: Rosen Chapter 5, sections 5.1-5.4. MN Chapter 2, sections 2.1-2.3. For a refresher of basic manipulations we will be using in class, Rosen Chapter 1 and 2, Chapter 4, section 4.1. MN Chapter 1.
Week Two: Rosen chapter 5, sections 5.2, 5.5, chapter 7, sections 7.5. MN Chapter 2, sections 2.7
Week Three: Rosen chapter 3, section 3.2, 3.3. MN 2.4 - 2.6
Week Four and Five: Rosen chapter 6. MN chapter 9.
Week Six: Rosen Chapters 9 & 10. MN Chapter 3 & 4.