CS173 Lecture Schedule
Fall 2015   Tandy Warnow


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.

Before each lecture, you are required to do the posted reading assignments. Most of these are from the online textbook written by Margaret Fleck, but some are about class or university policies. (Please note that the textbook has an errata file; report new errors and typos to the author at mfleck@illinois.edu).

I plan to provide a PDF for each class meeting of the material I will present in class. You should look at each PDF presentation in advance of the class meeting. Note that some of the material presented in class may not be in the assigned reading, nor in the online textbook. Therefore, attendance in class is required. Any material covered in class may appear in a homework, examlet, midterm exam, or final exam. Looking at the PDFs of the class presentation is helpful, but not as useful as actually attending class!

Weekly homework and reading quizzes are provided in Moodle. The homeworks are due on Mondays at 10 PM, and the reading quizzes (covering all reading assignments up to and including the following day, anything covered in class, and anything done in the homework) are due on Wednesdays at 10 PM.

An additional source for reading is the excellent text on discrete mathematics by Kenneth Rosen, which is available in Grainger Library. Please see a list of suggested reading from Rosen's textbook.

Date         Examlet Lecture Topic Readings Presentation         Comments
8/25   Syllabus
Campus emergency information
Two-person games
Algorithmic computational biology
Moodle password
Campus emergency information
Campus academic integrity policy
(PPTX)
(PDF)
Reading quiz #1 due 8/26 at 10 PM
8/27   Proofs by contradiction
Logic
Chapter 17
assigned work policies
excuses policy
exam instructions
(PPTX)
(PDF)
9/1   Logic
Satisfiability
2SAT
1.1-1.4, 1.7;  
Chapter 2 (but not 2.14)
Chapter 3
Lecture notes
Latex for lectures notes
(PDF-1)
(PPT-2)
Homework #1 due 8/31 at 10 PM
Reading quiz #2 due 9/2 at 10 PM
9/3   Introduction to proofs by induction
Recursive definitions
11.1-11.4
Lecture notes
Latex for lecture notes
(PDF)
(latex)
First ``examlet" next Thursday
9/8   Sets Chapter 5
Lecture notes
(PDF) Homework #2 due 9/7 at 10 PM
Reading quiz #3 due 9/9 at 10 PM
9/10 1: Proofs (direct, by contradiction, and by induction) and logic Sets 10.5 (PDF)
9/15   Proofs by induction - why they work
A bit more about sets
11.5-11.9
12.1, 12.2, 12.5
18.1, 18.2
Why Johnny Can't Induct
(PDF) Homework #3 due 9/14 at 10 PM
Reading quiz #4 due 9/16 at 10PM
9/17 2: Sets Functions 7.1-7.12;
8.1, 8.2, 8.6, 8.7
Solutions to examlet 1
(PDF)
9/22 Relations 6.1-6.7
Solutions to examlet 2
(PDF)
Homework #4 due 9/22 at 10PM
Reading quiz #5 due 9/23 at 10 PM
9/24 3: Relations and Functions Relations and Functions Solutions to examlet 3 (PDF)
9/29   Induction proofs 14.7 (PDF) Homework #5 due 9/28 at 10 PM
No reading quiz this week
Honors homework due 9/30
10/1 4: Induction proofs Review for Examlet (PDF) (PDF) Homework #6 due 9/30 at 10 PM
10/6   Midterm     No homework or reading quiz this week
10/8 Running times and big-oh 14.1-14.6, 14.8
(PDF)
10/13   Dynamic programming (PDF) (PDF) Homework #7 due 10/12 at 10 PM
Honors add-on homework due 10/14
Reading Quiz #6 due 10/14 at 10 PM
10/15   Combinatorial counting 8.4, 8.5,
18.1-18.9
(PPTX)
(PDF)
Fri is Drop Date
10/20 5: Running times, big-oh,
counting and DP algorithms
Review for Examlet #5 9.1-9.9 (PDF) Homework #8 due 10/19 at 10 PM
Reading quiz #7 due 10/21 at 10 PM
10/22   P vs. NP Chapter 16 (PDF)  
10/27   Graphs 9.10-9.11, 10.3  (PDF) Homework #9 due October 26, 10 PM
Reading Quiz #8 due Oct 28, 10 PM
10/29 6: Graphs and NP-hardness Review for examlet (PDF)  
11/3   Floyd-Warshall Algorithm
Reductions between problems
Wikipedia
MIT presentation
(PDF) Take-home examlet #7 distributed in class
Homework #10 due 11/2, 10 PM
Reading Quiz #9 due 11/4, 10 PM
Office hours Tuesday 1-3 and Thursday 1-2 PM
11/5 Approximation algorithms and heuristics 2-approximation for Minimum Vertex Cover (PDF)
11/10 7: Graph algorithms
Solving graph problems using other algorithms
Take-home examlet due in class by 11:05 AM
Solutions to Examlet 7 Eulerian Graphs
de Bruijn Graphs (PPT)
Genome Assembly
  Homework #11 due 11/8, 10 PM
Reading Quiz #10 due 11/11, 10 PM
No office hours this week
11/12   Eulerian Graphs and Genome Assembly   (PPT)
(PDF)
Note change to grade policy
11/17 Trees and Minimum spanning trees youtube (PDF) Homework #12 due 11/16, 10 PM
Reading Quiz #11 due 11/18, 10 PM
11/18   Cardinality, Countability, and Uncountability 20.1-20.6
IMPORTANT Final Exam Info
(PDF)
11/24   Thanksgiving Holiday      
11/26   Thanksgiving Holiday      
12/1 Review of last two weeks Math 347
(Review questions for final)
(PDF) Homework #13 due 11/30, 10 PM
Reading Quiz #12 due 12/2, 10 PM
12/3 8: Trees, algorithms, cardinality, countability, and uncountability Review for examlet (PDF)
Solutions to examlet 8
12/8   Review for Final
ICES forms
  (PDF) Homework #14, due 12/7, 10 PM
Last class
12/11   Final Exam   Friday, 8-11 AM