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 |