CS173 Lecture Schedule

Fall 2019 Mahesh Viswanathan

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
1
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
2
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
3
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
4
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
5
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
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 (?)
7
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
8
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
9
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
10
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(?)
11
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
12
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
13
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
14
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
15
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