This page shows a rough outline of what will be/was covered in each lecture/discussion section, and dates of tests. Schedule for future lecture topics is tentative, and may change. Roughly the course will cover Logic and Proofs (Chapters 1 and 3), basic mathematics (Chapter 4), Induction (Chapter 5), Arithmetic (Chapter 9), more Induction and Recursion (Chapters 6 and 7), Graphs and Orders (Chapters 10 and 12), and Counting (Chapters 14 and 15), in that order; here chapter references point to the relevant chapters in the textbook. We may also cover Chapters 8, 16, 17, and 18.
Video recording of the lectures will be available through Engineering's Echo360 service. To login, you will need to enter their University of Illinois email address. You will then be prompted to authenticate using their Active Directory (AD) password. Once you’re authenticated, you should see a dashboard page displaying content for which you are enrolled as a student. If need further documentation on how to use this platform, please consult this page.
Video recording of the lectures is also available through Class Transcribe. Class Transcribe automatically close captions the videos, and the resulting videos are also searchable.
In the table below, "MCS" refers to the class textbook, Mathematics for Computer Science. Topics covered in the lecture can often also be found in the alternate textbook for the course Building Blocks for Theoretical Computer Science, which is referred to below as "BBTCS".
Week | Date | Lecture/Test Topic | Reference Material |
---|---|---|---|
|
Aug 26 | Administrivia, and Introduction to Proofs [slides, worksheet, scribbled notes] |
meetings and materials assigned work MCS: Section 1.1 |
Aug 28 | Propositional Logic [worksheet, scribbled notes] |
MCS: Sections 3.1 to 3.3; BBTCS: 2.1 to 2.9 | |
Aug29/30 | Discussion: Propositional Logic | MCS: 3.1 to 3.3 | |
Aug 30 | Propositional Logic (contd), Satisfiability, Validity [worksheet, scribbled notes] |
MCS: Sections 3.4, 3.5; BBTCS: 2.1 to 2.9 CBTF, CBTF video and reservation, CBTF Documentation |
|
|
Sep 02 | No class. Labor Day | |
Sep 04 | Quantifiers and Proofs [worksheet, scribbled notes] |
MCS: Sections 1.1 to 1.5 and 3.6; BBTCS: 3.1 to 3.9 | |
Sep 05/06 | Discussion: Quantifiers and Proofs | MCS: 3.6 and 1.1 to 1.5 | |
Sep 06 | Proofs: Contrapositives and IFF [worksheet, scribbled notes] |
MCS: Sections 1.5 and 1.6; BBTCS: 3.12 and 3.13 | |
|
Sep 08-10 | CBTF Test 1 on Logic | Skill set |
Sep 09 | Proofs: By Cases, Contradiction, and Existentials [worksheet, scribbled notes] |
MCS: Sections 1.7 and 1.8; BBTCS: 3.10, 3.11, and 17 | |
Sep 11 | Sets [worksheet, scribbled notes] |
MCS: Section 4.1; BBTCS: 5 Instructions for taking long tests. |
|
Sep 12/13 | Discussion: More Proofs | MCS: 1.5 to 1.9 | |
Sep 13 | Functions, Binary Relations [worksheet, scribbled notes] |
MCS: Sections 4.2 to 4.4; BBTCS: 6,7,8 | |
|
Sep 16/17 | Long Test 1 on Proofs | Skill set |
Sep 16 | No class. Evening test | ||
Sep 18 | Finite Cardinality and Induction [worksheet, scribbled notes] |
MCS: Sections 4.5, Chapter 5; BBTCS: Chapter 11 | |
Sep 19/20 | Discussion: Sets and Functions | MCS: Chapter 4 | |
Sep 20 | Induction [worksheet, scribbled notes] |
MCS: Chapter 5; BBTCS: Chapter 11 | |
|
Sep 22-24 | CBTF Test 2 on Predicate Logic, Sets, Functions, and Relations | Skill set |
Sep 23 | Divisibility [worksheet, scribbled notes] |
MCS: Sections 9.1, 9.2, and 9.6; BBTCS: Chapter 4 | |
Sep 25 | Proving Algorithms: Inductive Invariants [worksheet, scribbled notes] |
MCS: Chapter 6, Section 9.2; BBTCS: -- | |
Sep 26/27 | Discussion: Induction Proofs | MCS: Chapters 5 and 6 | |
Sep 27 | Modular Arithmetic, and Equivalence relations [worksheet, scribbled notes] |
MCS: Chapter 9, Section 10.10; BBTCS: Chapter 4 and 6 | |
|
Sep 30/Oct 01 | Long Test 2 on Sets, Functions, Relations, and Induction | Skill set |
Sep 30 | No class. Evening test | ||
Oct 02 | Cryptography [worksheet, scribbled notes] |
MCS: Chapter 9; BBTCS: -- | |
Oct 03/04 | Discussion: Invariant Principle and Number Theory | MCS: Chapter 9, and Section 10.10 | |
Oct 04 | Recursive Structures and Structural Induction [worksheet, scribbled notes] |
MCS: Sections 7.1 to 7.5; BBTCS: Chapter 12 (?) | |
|
Oct 06-08 | CBTF Test 3 on Number Theory and the Invariant Principle | Skill set |
Oct 07 | Directed Graphs [worksheet, scribbled notes] |
MCS: Sections 10.1 to 10.4; BBTCS: Chapter 10 (?) | |
Oct 09 | DAGs and Partial Orders [worksheet, scribbled notes] |
MCS: Sections 10.5 to 10.10; BBTCS: Chapter 6 (?) | |
Oct 10/11 | Discussion: Structural Induction and Directed Graphs | MCS: Sections 7.1 to 7.5 and 10.1 to 10.4 | |
Oct 11 | (Undirected) Graphs [worksheet, scribbled notes] |
MCS: Sections 12.1 to 12.4; BBTCS: 9.1 to 9.4 | |
|
Oct 14/15 | Long Test 3 on Number Theory, the Invariant Principle, and Structural Induction. | Skill set |
Oct 14 | No class. Evening test | ||
Oct 16 | Sub Graphs and Connectivity [worksheet, scribbled notes] |
MCS: Sections 12.7 to 12.9; BBTCS: 9.6 to 9.8, and 9.10 | |
Oct 17/18 | Discussion: Partial Orders and Graphs | Sections from Chapters 10 and 12 | |
Oct 18 | Graph Coloring and Bipartiteness [worksheet, scribbled notes] |
MCS: Section 12.5 and 12.6; BBTCS: 9.11, 10.3 | |
|
Oct 20-22 | CBTF Test 4 on Directed Graphs, DAGs and Partial Orders | Skill set |
Oct 21 | Trees [worksheet, scribbled notes] |
MCS: Section 7.6 and 12.11; BBTCS: 13.1-3, 13.8 | |
Oct 23 | Analysis of Algorithms [worksheet, scribbled notes] |
MCS: Section 14.7; BBTCS: Chapter 14 | |
Oct 24/25 | Discussion: Graphs and Trees | Sections from Chapter 12 | |
Oct 25 | Big Oh [worksheet, scribbled notes] |
MCS: Section 14.7; BBTCS: Chapter 14 | |
|
Oct 28/29 | Long Test 4 on Directed and Undirected Graphs, and Partial Orders | Skill set |
Oct 28 | No class. Evening test | ||
Oct 30 | Summing Series [worksheet, scribbled notes] |
MCS: Section 14.1; BBTCS: Chapter 1(?) | |
Oct 31/Nov 01 | Discussion: Trees and Asymptotic Analysis | Chapter 12, Section 14.7 | |
Nov 01 | Solving recurrences [worksheet, scribbled notes] |
MCS: Sections 22.1 to 22.3; BBTCS: Chapter 12(?) | |
|
Nov 03-05 | CBTF Test 5 on Undirected Graphs, Trees, and Big Oh | Skill set |
Nov 04 | Analyzing Algorithms: Recursion tree Method [worksheet, scribbled notes] |
Section 1.7 of Jeff's notes; BBTCS: Chapter 15 | |
Nov 06 | Counting: Sums, Products, and Bijection [worksheet, scribbled notes] |
MCS: Sections 15.1 to 15.3; BBTCS: 5.7 to 5.9 | |
Nov 07/08 | Discussion: Summing series and Recurrences | Sections 14.1, 22.1 to 22.3, and Jeff's notes | |
Nov 08 | Counting: Permutations and Combinations [worksheet, scribbled notes] |
MCS: Section 15.4 to 15.5; BBTCS: 8.4, 8.5 | |
|
Nov 11/12 | Long Test 5 on Trees, Big O, and Recurrences | Skill set |
Nov 11 | No class. Evening test | ||
Nov 13 | Binomial and Multinomial Theorems [worksheet, scribbled notes] |
MCS: Section 15.6 and 15.7; BBTCS: 18.4 to 18.8 | |
Nov 14/15 | Discussion: Counting | Sections 15.1 to 15.7 | |
Nov 15 | Pigeon Hole Principle [worksheet, scribbled notes] |
MCS: Section 15.8; BBTCS: 8.3 | |
|
Nov 17-19 | CBTF Test 6 on Recursion Tree method and Counting | Skill set |
Nov 18 | Principle of Inclusion-Exclusion and Combinatorial Proofs [worksheet, scribbled notes] |
MCS: Sections 15.9 and 15.10; BBTCS: Section 5.7 | |
Nov 20 | Probability [worksheet, scribbled notes] |
MCS: Chapter 17 | |
Nov 21/22 | Discussion: Counting II | Sections 15.6 to 15.10 | |
Nov 22 | Conditional Probability [worksheet, scribbled notes] |
MCS: Chapter 18 | |
|
Nov 23 to Dec 01 | Thanksgiving Break | |
|
Dec 02 | Probability Theory: Pitfalls and Paradoxes [worksheet, scribbled notes] |
MCS: Chapters 17 and 18 |
Dec 04 | Infinite Sets [worksheet, scribbled notes] |
MCS: Section 8.1; BBTCS: Chapter 20 | |
Dec 05/06 | Discussion:Probability and ICES forms | ||
Dec 06 | Computability and ICES forms [worksheet, scribbled notes] |
MCS: Section 8.2; BBTCS: Chapter 20 | |
|
Dec 09/10 | Long Test 6 on Recursion Tree Method, Counting, and Probability | Skill set |
Dec 09 | No class. Evening test | ||
Dec 11 | Course Review |