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.4 Reading: 6.56.8 
Thursday 3/2 
(continued) 

Spring Break 

Chapter 7 
Tuesday 3/14 
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. 

Thursday 3/16 
Combinatorics I Counting  review, principle of inclusionexclusion slides  4up 
Reading:
7.1, 7.2 

Chapter 7 
Tuesday 3/ 21 
Combinatorics II Counting  permutations and combinations with repetition; stars and bars argument slides  4up 
Reading: 7.5 
Thursday 3/23 
(continued) 
Reading:
7.4, 7.6 

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 
Thursday 3/30 
* Work on Recurrences worksheet and exercises from 8.9 

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 
Thursday 4/6 
Graph theory
 Trees binary search trees, matchings, backtracking 

Chapter 10 
Tuesday 4/11 
Exam 3 (chapters 7, 8, 10) 

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 
Thursday 4/20 
Graph traversals Euler circuits/paths; Hamilton circuits/paths slides  4up 
Reading:
12.112.4 

Chapter 13 
Tuesday 4/25 
Graph coloring Vertex coloring; coloring planar graphs; the four color map theorem; applications slides  4up 
Reading:
13.113.3 
Thursday 4/27 
Graph coloring (continued) 

* 
Tuesday 5/2 
No class  (Friday
schedule) 

Thursday 5/4 
Review 

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