Chapter

Date 


Chapter 1 
Tuesday 1/17 
Course
introduction Counting, sets, sum & product principles slides  4up 
Be sure to do all the "Check
yourself" exercises as part of the reading. Reading: 1.11.5 Exercises: Section 1.2 
Thursday 1/19 
Counting
and proofs Counting subsets; the pigeonhole principle; introduction to mathematical proofs 
Exercises 1.7: 1, 2, 3, 11, 12, 16, 17,
19, 20, 21 Problem set 1  due Thursday 1/26 Quiz 0 (practice  does not count for grade) 

Chapter 2 
Tuesday 1/24 
Sets Notation, basic definitions, proofs about sets slides  4up 
Reading: 2.1 & 2.2 Exercises 2.4: 1, 3, 5, 7, 8 Exercises 2.9: 1, 4, 6, 8, 14 Quiz 1 (available now  8am 1/26/17) 
Thursday 1/26 
Logic Notation, basic definitions, logical connectives, quantifiers, types of proofs 
Reading: 2.3 & 2.5 Exercises 2.4: 2, 4, 6, 9 Exercises 2.9: 5, 17, 19, 20, 23 Problem set 2  due Thursday 2/2 Quiz 2 (available 2:30pm 1/26/17  8am 1/31/17) 

Chapter 2 
Tuesday 1/31 
Graphs
and Functions Functions: onetoone, onto, bijections, domain, codomain Graphs: vertices, edges, paths, cycles, handshaking lemma slides  4up 
Reading:
3.1, 3.2, 3.4, 3.5 Excercises: 3.3.1(all), 3.3.2(all) Quiz 3 (available 2:30pm 1/31/17  8am 2/2/17) 
Thursday 2/2 
Graph and Functions (continued) Special graphs, subgraphs, complements, bipartite graphs, graph isomorphism See also  graph isomorphism in the news 
Reading: 3.6,
3.7 Exercises 3.8 Exercises 3.13: 1, 3, 5, 6, 8, 10, 13, 14, 20, 24 See also  graph isomorphism resource 

Chapter 4 
Tuesday 2/7 
Exam 1 (chapters 1,
2, 3) 

Thursday 2/9 
University closed  class is canceled  see note on Piazza 
Reading:
4.1, 4.2 Quiz 4a (available until 12pm 2/14/17) 

Chapter 4 
Tuesday 2/14 
Induction Proof techniques, summation formulas, mathematical induction slides  4up mathematical induction proof template 
Reading:
4.4, 4.5 Exercises 4.3: 1, 2, 5 Quiz 4b (available until 12pm 2/16/17) 
Thursday 2/16 
(induction continued) 
Exercises 4.6: 1, 2, 3 Exercises 4.11: 2, 3, 4, 5, 8, 12 Problem set 3 due Thursday 2/23 

Chapter 5 
Tuesday 2/21 
Modular arithmetic and equivalence relations modular arithmetic, congruences, equivalence relations, equivalence classes, partitions. slides  4up 
Reading: 5.3 (5.1, 5.2 review algorithms) Exercises 5.5: 1, 2 Quiz 5a (available until 12pm 2/23/17) 
Thursday 2/23 
Applications of modular arithmetic to cryptography shift ciphers, onetime pads, public key cryptography, RSA algorithm, digital signatures See Piazza for additional links and resources, including spreadsheets and code to experiment with modular arithmetic. 
Reading: 5.4 (focus on shift ciphers and supplement with material from slides) Exercises 5.9: 2, 4, 9, 18, 23 Problem set 4 due Thursday 3/2/17 

Chapter 6 
Tuesday 2/28 
Binomial coefficients
and Pascal's triangle Combinations, permutations, Pascal's triangle, combinatorial proofs, binomial theorem slides  4up 
Reading: 6.16.7 Exercises 6.3: 14 Exercises 6.6: 1, 2 Quiz 6a (available until 12pm 3/2/17) 
Thursday 3/2 
(continued  focus on binomial theorem & combinatorial proofs) 
Reading: 6.8 Exercises 6.3: 5, 6 Exercises 6.6: 36 Exercises 6.9: all Exercises 6.13: 10, 15, 16, 21 

Spring Break 

Chapter 7 
Tuesday 3/14 
University closed  class is canceled  Exam postponed until Thursday 3/16  see note on Piazza 

Thursday 3/16 
Exam 2 (chapters 4, 5, 6) Similar in structure to Exam 1. Although this exam will focus on material from chapters 46, it may use concepts from earlier chapters and will include a repeat question from Exam 1. 

Chapter 7 
Tuesday 3/ 21 
Combinatorics I Counting  review, principle of inclusionexclusion slides  4up 
Reading: 7.1, 7.2, 7.5 Quiz 7a (available until 12pm 3/23/17) 
Thursday 3/23 
Combinatorics II Counting  permutations and combinations with repetition; stars and bars argument slides  4up 
Reading:
7.4, 7.6 Exercises 7.6: 1, 2, 3, 5, 6, 7, 8 Exercises 7.9: 1, 2, 3, 5, 6, 7, 9, 11, 13, 14, 16, 17, 22 (also good problems for review: *7.4 check yourself) Problem set 5 due Tuesday 3/28/17 Quiz 7b(available until 12pm 3/28/17) 

Chapter 8 
Tuesday 3/28 
Recurrences Arithmetic and geometric sequences, techniques for finding closed forms of recurrence relations slides  4up 
Reading:
8.1, 8.2, 8.3, 8.5, 8.6 Quiz 8a(available until 12pm 3/30/17) 
Thursday 3/30 
Recurrences continued slides  4up 
Reading:
8.8 (But this week you only need to do the check yourself exercises listed below) Check yourself exercises: Exercises 8.2: 1, 2 Exercises 8.3: 1, 2, 4 Exercises 8.5: 1, 2, 3 (find formula, proof is optional) Exercises 8.6: (none, just skim the section) Exercises 8.8: 1, 2, 4 Exercises 8.9: 1, 7 Exercises 8.12: 1, 3, 7, 8, 9, 14, 17, 18, 19, 25 Problem set 6 due Thursday 4/6/17 Quiz 8b (available until 12pm 4/4/17) 

Chapter 10 
Tuesday 4/4 
Graph theory  Trees definitions, examples, spanning trees, minimum weight spanning trees, Prim's and Kruskal's algorithms slides  4up 
Reading: 10.110.4 graph activity  London Tube Quiz 10A (available until 12pm 4/6/17) 
Thursday 4/6 
Graph theory
 Trees binary search trees, matchings, backtracking 
Reading: 10.5  10.8 Check yourself exercises: Exercises 10.2: all Exercises 10.3: 1, 2, 7 Exercises 10.4: all Exercises 10.5: all Exercises 10.6: 3, 4, 6, 7 Exercises 10.7: 1, 2 Exercises 10.8: 1, 2 Exercises 10.11: 1, 2, 4, 7, 8, 17, 19 

Chapter 10 
Tuesday 4/11 
Exam 3 (chapters 7, 8, 10) Similar in structure to Exams 1 and 2. Although this exam will focus on material from chapters 7, 8 &10, it may use concepts from earlier chapters (almost surely chapters 3, 4 & 6). 

Thursday 4/13 
Easter
Recess 

Chapter 11, 12 
Tuesday 4/18 
Graph planarity Planar graphs and faces of the plane, Euler's formula, special nonplanar graphs Planarity game slides  4up 
Reading:
11.411.6 Exercises 11.11: 3, 4, 5, 6, 7, 13 Quiz 11 (available until 12pm 4/20/17) 
Thursday 4/20 
Graph traversals Euler circuits/paths; Hamilton circuits/paths slides  4up 
Reading:
12.112.4 Exercises 12.10: 1, 4, 5, 7, 15, (24) Quiz 12 (available until 12pm 4/25/17) Problem set 7 due Tuesday 4/25/17 

Chapter 13 
Tuesday 4/25 
Graph coloring Vertex coloring; coloring planar graphs; the four color map theorem; applications slides  4up 
Reading:
13.113.5 Exercises 13.8: 3, 8, 9, 14, 15, 16, 19, 22, 23 Quiz 13A (available until 12pm 4/27/17) 
Thursday 4/27 
Graph coloring Edge coloring; vertex coloring algorithms revisited slides  4up 
Quiz 13B (available until 12pm 5/4/17) 

* 
Tuesday 5/2 
No class  (Friday
schedule) 

Thursday 5/4 
Review 

Final Exam  Saturday, May 6, 4:156:45pm Room TBA 