CMSC 27100-1
Discrete Mathematics - Autumn 2005

Instructor: Caroline J. Klivans
office: Eckhart 308A
e-mail: cjk (at) math.uchicago.edu
office hours: Monday 3:00-4:00 and by appointment

TAs: Sourav Chakraborty
office: Ryerson 162A
office hours: Tuesday 4-5 & Friday 4:30-5:30 in Ryerson 255

Duru Turkoglu
office: Ryerson 257
office hours: Tuesday 3-4 & Thursday 3-4 in Ryerson 255

Lecture: MWF 1:30-2:20 Ryerson 251

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

Required texts: (Available at the Seminary Co-op)
Discrete Mathematics with Combinatorics, by James A. Anderson, published by Pearson Prentice Hall, 2nd edition, ISBN# 0130457914

Homework There will be weekly homework assignments due every 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.

Final exam: Wednesday December 7th 1:30-3:30 Ryerson 251

Practice problems for the final exam.

Some lecture notes on generating functions and recurrences

Homework 1, due Wednesday October 5th From the handout: Problems 1.2.8, 1.2.9, 4.1.6, 4.1.22, 4.1.25, 4.1.29, 4.1.32, 4.1.41, 4.1.46, 4.2.8. Optional (challenging): 4.2.9

Homework 2, due Wednesday October 12th From the handout: Problems 4.1.8, 4.1.49, 5.1.14, 5.1.24, 5.1.39. Prove the following relation: for p,q prime, phi(p)phi(q) = phi(pq), where phi is Euler's phi function.

Homework 3, due Wednesday October 19th From the handout: Problems 4.1.39, 5.1.18, 5.1.28, 5.1.35, 5.2.6, 5.2.7 (Find the ordinary generating functions for problem 5.2.7) Additional problem

Homework 4, due Wednesday October 26th From the handout: Problems 7.1.5, 7.1.24, 7.1.32, 7.2.16, 7.2.27, 7.4.8

Homework 5, due Wednesday November 2ndHomework 5

Midterm Wednesday November 2nd

Homework 6, due Wednesday November 16th From the handout: Problems 2.3.6, 6.1.10, 6.1.26, 6.1.27, 6.1.45, 7.2.21 (A random graph is defined on page 74 of the handout - just before exercise 7.2.20)

Homework 7, due Wednesday November 23rd From the handout: Problems 6.1.65, 6.1.78, 6.1.79, 6.1.80, 6.1.81,6.2.32

Homework 8, due Wednesday November 30th Homework 8

Lecture notes on Markov chains

Challenge Problems :
From week 1: Lecture notes 4.2.9 Hint 1 Hint 2
From week 2: (a) Suppose you have a 2n x 2n grid of squares with two opposite corners removed. Can you exactly cover the board with dominoes (1 x 2 or 2 x 1 blocks)? Hint
(b) Suppose you have an n x n grid of squares. Each square is colored either black or white. The color of the squares may change by the following rules: If a square is black it must stay black. If a square is white and has at least two black neighbors it becomes black. Continue to recolor squares until the configuration is stable. Question: What is the minimum number of initial black squares needed so that the board will become completely black?