Franz Lemmermeyer

# Discrete Mathematics

### Schedule

```  Tu  8:40 - 10:30, G236
Th 10:40 - 12:30, G236```
This is a 3-hour course; in the fourth hour, Selman Erol (a 4th year math student) will take over and present examples, discuss the homework, and answer questions.

### Homework

Homework is always due one week after hand-out except when stated otherwise.
You can download the scanned book (I'm assuming you bought it) here as a djvu file. You can find a reader for djvu files here. I also found a few other books on discrete math as pdf files; they're here, here, and here.

### Suggested Exercises for midterm 1

• 1.2. Ex. 3, 8, 9, 11, 13, 16, 20, 21, 22, 26, 27, 35
• 1.3. Ex. 2, 8, 11, 12, 13, 15, 21, 23, 25
• 1.4. Ex. 1, 2, 3, 4, 5, 7, 12, 14, 18
• 4.1. Ex. 1, 2, 3, 4, 12, 13, 14, 15, 18, 24, 26
• 4.2. Ex. 11, 12, 13, 14, 15
• 4.3. Ex. 2, 4, 9, 10, 11, 12, 13, 14, 15, 16, 16, 19,
• 4.4. Ex. 1, 3, 6, 7, 10, 13
• 4.5. Ex. 1, 13, 14, 25, 27
• 14.3. Ex. 1, 2, 32

### Suggested Exercises for midterm 2

As far as I can see, the problems mentioned below are the same for the 3rd and the 5th edition. Also make sure you understand all the homework problems.
• 5.2. Ex. 1, 2, 3, 4, 8, 15, 16, 18
• 5.5. Ex. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
• 5.6. Ex. 3, 10, 17, 21
• 7.1. Ex. 1, 5
• 7.3. Ex. 17, 19
• 7.4. Ex. 1, 6, 7, 8
• 8.1. Ex. 1, 2, 3, 4, 5, 12, 13
• 9.1. Ex. 1, 4, 5
• 9.2. Ex. 1, 2, 3, 4, 5, 6, 7, 8, 9, 17, 18
• 10.2. Ex. 1
• 10.3. Ex. 1, 2, 5, 6, 7
• 10.4. Ex. 1

### Suggested Exercises Chapter 11

• 11.1 Ex. 2, 3, 5, 12
• 11.2 Ex. 9
• 11.3 Ex. 1, 2, 3, 4, 5, 18, 19
• 11.4 Ex. 2, 3, 4, 5, 7, 10, 14
Here are a few practice exams.

### What I did in class

• Tu 30.01. Basic Counting principles; binomial theorem
• Th 01.02. More counting
• Tu 06.02. More examples. Induction
• Th 08.02. Induction; Fibonacci numbers; unique factorization
• Tu 13.02. Euclidean algorithm; examples
• Th 15.02. Tutorial (this somehow went wrong)
• Tu 20.02. Congruences (14.3), ISBN, RSA
• Th 22.02. Relations (5.1, 5.2)
• Tu 27.02. injective and surjective functions; pigeonhole principle (5.5)
• Th 01.03. composition of functions; inverse functions; complexity. See also Knuth's article on the complexity of songs.
• Tu 06.03. Review. Here are some problems from last year's exams.
• Th 08.03. 11:40 tutorial (review)
• Su 11.03. 10:00 - 12:00 BZ08: Midterm 1, covering everything up to ISBNs. Average 73; here are the solutions.
• Tu 13.03. discussion of midterm 1; equivalence relations
• Th 15.03. equivalence relations
• Tu 20.03. posets; digraphs; adjacency matrices; generating functions I
• Th 22.03. 11:40 tutorial
• Tu 27.03. generating functions II; partitions
• Th 29.03 10:40 - 12:30 exponential generating functions; homework.
• Tu 03.04. generating functions; recurring sequences
• Th 05.04. 11:40 tutorial
• Tu 17.04. nonhomogeneous recurring sequences
• Th 10.04. 10:40 class; 11:40 tutorial
• Tu 17.04. nonhomogeneous recurring sequences
• Th 19.04. Graphs (Ch. 11)
• Tu 24.04. homework; review
• Th 26.04. review; tutorial. Here are more problems from last year's exams.
• Su 29.04. 10:00 - 12:00 BZ08 Midterm 2; average: 60. Here are solutions.
• Tu 01.05. Planar graphs
• Th 03.05. 11:40 tutorial (no class from 10:40-11:30)
• Tu 08.05. Platonic solids
• Th 10.05. Section 10.2
• Fr 25.05. Final 12:15 BZ08