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

• Instructor: Isabella Novik
• Syllabus
• Writing Guidelines handout
• Some materials (for registered students only)

Textbook

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!