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
Algorithmic computational biology
Campus academic integrity policy
assigned work policies
Campus Emergency Information
|Quiz for policies and instructions (mandatory)|
|8/30||Proofs by contradiction
PDF for lecture notes
Rosen, pages 1-10 (propositional logic), pages 25-31 (propositional equivalence and satisfiability), and pages 86-87 (proofs by contradiction)
|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.
|Rosen, List of symbols inside front cover, pages 36-49 (predicates and quantifiers), and pages 115-120 (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
|Rosen, pages 311-320 (induction) and pages 344-346, 349 (recursive definitions)||(PDF)
|9/11||173a-latex-hw.tex - the latex file for homework and its PDF file||Why induction works||
Rosen, pages 333-338 (Strong Induction)
notes from lecture (PDF)
RQ 2, due Tuesday September 11 (covers Weeks 1-3)
HW 2, due Wednesday September 12 (covers Week 1-2, and latex)
|9/18||More strong induction||
Rosen, pages 127-134 (sets) and pages 138-151 (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 573-578 and my notes on relations at (PDF)||(PDF)||HW 3, due Wednesday September 19|
dynamic programming and
recursions for running time analysis
Examples 5, 10, and 13 in Chapter 5.3.
Optional readings: Rosen, pages 507-510 (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|
Deadline to report a conflict with Midterm 1: October 2
See course webpage for instructions
||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||Big-O||
Rosen, pages 204-214
|10/18||PDF covers two days||Graphs - part 1||Rosen, pages 641-644, 651-657, and 735-737 (Key terms)||(PDF)||HW 6, due Wednesday October 17
RQ 6, due Thursday October 18
|10/23||Graphs-part 2||Rosen, pages 668-671 (representations of graphs)||(PDF)
Also, finishing PDF from 10/18
|RQ 7, due October 23|
|10/25||Combinatorial Counting||Rosen, pages 385-395.||(PDF) (PPTX)||HW 7, due October 24|
|10/30||Introduction to computational complexity
Karp reductions, NP-hardness, NP-completeness
P vs. NP.
|Rosen, pages 219-227
|11/1||Graph algorithms; decision, optimization, and construction problems||Rosen, pages 645-649 (representing real world problems as graph problems)||(PDF)||HW 8, due October 31|
Deadline to report a conflict with Midterm 2: November 6
See course webpage for instructions
|TBD||Rosen, pages 745-747||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:
Princeton's slides on MST: Version 1 Version 2
|Fun stuff, not on the final exam: Minimum Spanning Trees (MST) and a 2-approximation for Triangle-TSP||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|