CS173 Lecture Schedule (Under Development)
Fall 2018   Tandy Warnow


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
Two-person 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 1-10 (propositional logic), pages 25-31 (propositional equivalence and satisfiability), and pages 86-87 (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 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
Recursive definitions
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)
(PDF) RQ 2, due Tuesday September 11 (covers Weeks 1-3)

HW 2, due Wednesday September 12 (covers Week 1-2, and latex)
9/13   Functions
Strong induction
(PDF)
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
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 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
10/2 Deadline to report a conflict with Midterm 1: October 2
See course webpage for instructions
Dynamic Programming
Floyd-Warshall
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 Big-O (PDF)
Rosen, pages 204-214
(PDF)
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
HW7 solutions
(PDF)
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
11/6 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: (PDF)
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