380: Introduction to Discrete Mathematics
The final is on Monday, March 12, 8:30-10:20am. Here is some
info and review problems to help you start preparing.
The week of March 5-9, I'll have my office hours on Monday, 2-3pm (in PDL C-416), on Tuesday, 5-6:30pm (in PDL C-401), and on Friday, 1:30-3:30pm (in PDL C-416). Please come and bring questions!
Course information
Textbook
Combinatorics Through Guided Discovery (November 6, 2004 edition) by Kenneth Bogart
Office hours/Problem Solving Sessions/Homework Assistance
- Monday 2-3 in PDL C-416
- Tuesday 4:30-6:00 in PDL C-401
Exams
- Midterm (Friday, February 9)
- Final (Monday, March 12, 8:30am-10:20am)
Schedule/Assignments (all problems are from this set)
- 1/3/18:
- Topic: Introduction to counting
- Practice Problems (for today): #1, 3, 5
- Practice Problems (for next class): #7, 8, 13, 10a
- Homework Problems (due Wednesday, January 10): #2, 4, 6
- Book reading: read 1.1, start reading 1.2
- 1/5/18:
- Topic: Sums, products and functions
- Practice Problems (for today): #7, 8
- Practice Problems (for next class): #13, 10a, 16
- Homework Problems (due Wednesday, January 10): #9, 11, 12
- Book reading: 1.1 and 1.2.1
- 1/8/18:
- Topic: General Product Principle and its applications
- Practice Problems (for today): #13, 10a, 16
- Practice Problems (for next class): #18, 20; 21, 22, 25, 26
- Homework Problems (due Wednesday, January 17): #14, 15, 17
- Extra-credit HW Problem: 10b
- Book reading: 1.1 and 1.2.1
- 1/10/18:
- Topic: Applications of General Product Principle; Functions and Digraphs
- Practice Problems (for today): #18, 20; 21, 22, 25
- Practice Problems (for next class): #26; 28, 31, 32
- Homework Problems (due Wednesday, January 17): #19, 23, 24
- Book reading: 1.2.2 and 1.2.3; start reading 1.2.4 and 1.2.5
- 1/12/18:
- Topic: Bijection Principle; Binomial coefficients
- Practice Problems (for today): #26, 28a
- Practice Problems (for next class): #28bcd, 31, 32
- Homework Problems (due Wednesday, January 17): #27
- Book reading: 1.2.4 and 1.2.5
- 1/17/18:
- Topic: Bijection Principle; Binomial coefficients
- Practice Problems (for today): #28bcd, 31, 32
- Practice Problems (for next class): #37, 39, 36+38
- Homework Problems (due Wednesday, January 24): #29, 33, 34, 35ab
- Extra-credit HW Problem: 35c
- Book reading: 1.2.4 and 1.2.5; start reading 1.2.6
- 1/19/18:
- Topic: Binomial coefficients; Quotient Principle
- Practice Problems (for today): #37, 39, 36+38
- Practice Problems (for next class): #41, 43, 50
- Homework Problems (due Wednesday, January 24): #40, 42
- Book reading: 1.2.6
- 1/22/18:
- Topic: Applications of binomial coefficients
- Practice Problems (for today): #41, 43a
- Practice Problems (for next class): #43b, 50, 51, 54b
- Book reading 1.3.1; start reading 1.3.2
- 1/24/18:
- Topic: Binomial Theorem
- Practice Problems (for today): #43b; 50, 51
- Practice Problems (for next class): #54b; 56, 59
- Homework Problems (due Wednesday, January 31): #44; 52, 53
- Book reading: 1.3.2; start reading 1.3.3
- 1/26/18:
- Topic: Binomial Theorem and its applications; Pigeonhole Principle
- Practice Problems (for today): #54b; 56; B and C from this handout; 59
- Homework Problems (due Wednesday, January 31): #55; A from this handout; #58abc, and 57 (use the pigeonhole principle to solve it)
- Extra-credit HW Problem: #54a
- Book reading: 1.3.2, 1.3.3
- Practice Problems (for next class): #D, 61
- 1/29/18:
- Topic: Pigeonhole Principle
- Practice Problems: #D, 61
- Homework Problems (due Wednesday, February 7): #E, 61, 62
- Extra-credit HW Problem: Use the Pigeonhole Principle to solve #60
- Book reading: 1.3.3; start reading 2.1
- 1/31/18:
- Topic: Applications of Induction to Combinatorics
- Practice Problems (for today): #65, 67 (70, 63)
- Practice Problems (for next class): #70, 63; 71, 72
- Homework Problems (due Wdenesday, February 7): #66, 68, 69
- Book reading: 2.1.1, 2.1.2, 2.1.3
- 2/2/18:
- Topic: Applications of Induction to Combinatorics; Recurrence relations
- Practice Problems (for today): #70, 63 (71, 72)
- Practice Problems (for next class): #71, 72, 75
- Homework Problems (Wdenesday, February 7): #64
- Book reading: 2.1.1, 2.1.2, 2.1.3, 2.2
- 2/5/18:
- Topic: Recurrence relations
- Practice Problems (for today): #71,72,75
- Homework Problems (due Wednesday, February 21): #73, 74
- Extra-credit HW Problem: #76 (due Feb 14)
- Book reading: 2.1.3, 2.2
- 2/12/18:
- Topic: Graphs
- Practice Problems (for today): #80, 81ab, and I.3 from this handout
- Practice Problems (for next class): #I.3, II.1
- Homework Problems (due Wednesday, February 21): #82, 83, and I.1, I.2 from this handout
- Book reading: 2.3.1, 2.3.2; also please review strong induction (p.35 in the book)
- 2/14/18:
- Topic: Graphs and strong induction
- Practice Problems (for today): #I.3, II.1 from this handout
- Practice Problems (for next class): #I.4, 84, 85
- Homework Problems (due Wednesday, February 21): #II.2 from this handout
- Book reading: 2.3.1, 2.3.2, and p.35
- 2/16/18:
- Topic: Trees
- Practice Problems (for today): I.4 from this handout, #84; start thinking about #85
- Homework Problems (due Wednesday, February 21): #I.5 (feel free to use the conclusion of #84), 86, 91a
- Extra-credit HW Problem: #I.6 (due Feb 28)
- Book reading: 2.3.4
- 2/21/18:
- Topic: A bit more on trees; Distribution problems
- Practice Problems (for today): #85; 93, 95
- Practice Problems (for next class): 98, 99, 101, 104
- Homework Problems (due Wednesday, February 28): #94, 96
- Book reading: 3.1.1-3.1.3
- 2/23/18:
- Topic: Distribution problems
- Practice Problems (for today): #98, 99, 101; #2 and 4 from this handout
- Practice Problems (for next class): #4 from this handout; 105, 106, 109
- Homework Problems (due Wednesday, February 28): #100, 103; #1 and 3 from this handout
- Book reading: 3.1.3-3.1.4
- 2/26/18:
- Topic: Distribution problems
- Practice Problems (for today): #4 from this handout; 105, 106abc
- Practice Problems (for next class): 106def, 109, 112, 114
- Homework Problems (due Wednesday, March 7): #107, 108, 116
- Book reading: 3.2.1
- 2/28/18:
- Topic: Distribution problems
- Practice Problems (for today): #106def, 109, 112, 114
- Practice Problems (for next class): #114; 175, 177, 178, 179
- Homework Problems (due Wednesday, March 7): #115
- Extra-credit HW Problem: 111ab
- Book reading: 3.2.2
- 3/2/18:
- Topic: Stirling numbers; Inclusion-Exclusion
- Practice Problems (for today): #114; 175, 177, 178
- Practice Problems (for next class): #179 and #11-13 from Review handout
- Homework Problems (due Wednesday, March 7): #174, 176
- Book reading: 5.1
- 3/5/18:
- Topic: Inclusion-Exclusion
- Practice Problems (for today): #11-13 from Review handout
- Next time: finish discussing #13 from Review handout and #179; start reviewing
- 3/7/18:
- Topic: Inclusion-Exclusion; Review
- Practice Problems (for today): #13 from Review handout
- Extra-credit HW Problem: #179 (due Friday, March 9)
- Bring questions for Friday's lecture!