Schedule (Under Development)
This outline shows (tentatively) what was/will be covered in each lecture,
links to reading assignments,
exam dates, homework due dates,
and reading quiz due dates.
However, you will need to look at Moodle to see and
submit homeworks and reading quizzes.
Some of the material presented in class may not be in the textbook, and so attendance in class is required. If you don't attend class, please at least make sure to read the PDF or PPTX for the class lecture. Any material covered in class or in assigned reading may appear in a homework, midterm exam, or final exam.
Weekly homework and reading quizzes will be provided in Moodle. The reading quizzes are typically due on Tuesdays and cover all assigned reading through the end of that week, and the homeworks are typically due on Wednesdays and cover the material through the previous week.
The class textbook is Discrete Mathematics and its Applications (7th edition) by Kenneth Rosen, which is available in Grainger Library, and available for purchase at the Bookstore.
You should read the assigned reading and lecture material before attending class!
Date  Comments  Lecture Topic  Readings  Lecture PDF/PPTX  HW and RQs  

8/28  Policies document in Moodle must be completed by September 7  Syllabus Campus emergency information Twoperson games Algorithmic computational biology Moodle password 
Campus academic integrity policy
assigned work policies excuses policy exam instructions Campus Emergency Information 
(PPTX) (PDF) 
Quiz for policies and instructions (mandatory)  
8/30  Proofs by contradiction Logic Set notation 
PDF for lecture notes
Rosen, pages 110 (propositional logic), pages 2531 (propositional equivalence and satisfiability), and pages 8687 (proofs by contradiction) 
(PDF)  
9/4  The LaTeX document is provided here to help you
learn how to write LaTeX:
Latex for lecture notes.
PDF for lecture notes.
See also these practice problems for proofs by contradiction, created by TA Meghan Shanks for her discussion section, and which could be helpful in preparing for exams. 
Logic Satisfiability 2SAT 
Rosen, List of symbols inside front cover, pages 3649 (predicates and quantifiers), and pages 115120 (sets and Venn Diagrams).  See PDF from previous class 
RQ 1, due Tuesday September 4 (covers Weeks 1 and 2) HW 1, due Wednesday September 5 (covers Week 1) 

9/6  Introduction to proofs by induction Recursive definitions 
Rosen, pages 311320 (induction) and pages 344346, 349 (recursive definitions)  (PDF) 

9/11  173alatexhw.tex  the latex file for homework and its PDF file  Why induction works 
Rosen, pages 333338 (Strong Induction) notes from lecture (PDF) 
(PDF) 
RQ 2, due Tuesday September 11 (covers Weeks 13) HW 2, due Wednesday September 12 (covers Week 12, and latex) 

9/13  Functions Strong induction 
(PDF)  
9/18  More strong induction 
Rosen, pages 127134 (sets) and pages 138151 (functions) Why Johnny Can't Induct (by Dan Gusfield of UC Davis) and Chandra Chekuri's notes on induction. notes from today's lecture (PDF) 
(PDF)  RQ 3, due Tuesday September 18  
9/20  Complicated induction proofs (and possibly relations)  Relations: Rosen, pages 573578 and my notes on relations at (PDF)  (PDF)  HW 3, due Wednesday September 19  
9/25  Introduction to
dynamic programming and
recursions for running time analysis

Rosen,
Examples 5, 10, and 13 in Chapter 5.3.
Optional readings: Rosen, pages 507510 (material on Algorithms and Recurrence Relations) 
Fibonacci numbers and running time (PDF)
Coin Changing Problem (PDF) 
RQ 4, due Wednesday September 25  
9/27  Dynamic Programming  Longest Increasing Subsequence  Part I (PDF)  HW 4, due Wednesday September 26  
10/2 
Deadline to report a conflict with Midterm 1: October 2
See course webpage for instructions 
Dynamic Programming FloydWarshall 
Wikipedia 
More Dynamic Programming (PDF)  RQ 5, due Tuesday October 2  
10/4  Proofs by Contradiction (taught by Prof. Varodayan)  HW 5, due Wednesday October 3  
10/9  Review of Material (to date)  Midterm 1 Prep (PDF) 
Review of material (PDF)  
10/11  First Midterm this evening  No class  No homework  
10/16  Deadline to drop class on Friday October 19  BigO 
(PDF)
Rosen, pages 204214 
(PDF)  
10/18  PDF covers two days  Graphs  part 1  Rosen, pages 641644, 651657, and 735737 (Key terms)  (PDF)  HW 6, due Wednesday October 17 RQ 6, due Thursday October 18 

10/23  Graphspart 2  Rosen, pages 668671 (representations of graphs)  (PDF) Also, finishing PDF from 10/18 
RQ 7, due October 23  
10/25  Combinatorial Counting  Rosen, pages 385395.  (PDF) (PPTX)  HW 7, due October 24  
10/30  Introduction to computational complexity Karp reductions, NPhardness, NPcompleteness P vs. NP. 
Rosen, pages 219227
HW7 solutions 
(PDF)  
11/1  Graph algorithms; decision, optimization, and construction problems  Rosen, pages 645649 (representing real world problems as graph problems)  (PDF)  HW 8, due October 31  
11/6 
Deadline to report a conflict with Midterm 2: November 6
See course webpage for instructions 
TBD  Rosen, pages 745747  TBD  
11/8  Review for Midterm 2  HW 9, due November 7  
11/13  Second Midterm this evening! (No class today conflict exam during the class period in ECEB Auditorium)  No class  
11/15  Review of Second Midterm  No homework this week  
11/27  More dynamic programming  (PDF)  
11/29  Cardinality, countability, and uncountability  IMPORTANT Final Exam Info  (PDF)  Homework 10, due November 28, Reading quiz 10, due November 30  
12/4 
Jeff Erickson's text on MST:
(PDF) Princeton's slides on MST: Version 1 Version 2  Fun stuff, not on the final exam: Minimum Spanning Trees (MST) and a 2approximation for TriangleTSP  A short proof that Kruskal's algorithm is correct from Cornell.  (PDF)  
12/6  Fun stuff, not on the final exam: Proof that Kruskal's algorithm is correct, and (time permitting) more Approximation Algorithms  (PDF)  Homework 11, due December 3  
12/11  (Final Exam Prep)  Review for final exam 