CS173: Discrete Structures
Fall 2014   Madhusudan Parthasarathy
Lecture Schedule

This outline shows what was/will be covered in each lecture, as well as exam dates and similar information. It is still tentative and based on what happened last term.

Before each lecture, you are expected to do the reading assignment from the textbook. Please check the errata file for typos; report any new ones to Margaret (mfleck@illinois.edu). The corresponding Moodle quiz is due at 1am during the night before the lecture. You may also wish to read the corresponding sections in the optional Rosen textbook.

Date	Topic	Pre-lecture readings	Notes from lecture	Reading Resources
8/26	Introduction		Lecture 1 slides
8/29	Logic: Propositional logic	--	Lecture 2 slides	Chapter 1 and 2 (2.1-2.10) of textbook
9/2	More Logic: Predicate logic, quantifiers, etc.		Lecture 3 slides	Chapter 2 (2.10-2.17) and Chapter 3 (3.1, 3.2, 3.3)
9/4	Proofs	--	Lecture 4 slides
9/9 and 11/9	Number theory		Lecture 5+mini slides	Chapter 4
9/16	Number theory: congruences, rationals, reals		Lecture 6 slides	Chapter 4
9/18	Sets		Lecture 7 slides	Chapter 5
9/23	Relations		Lecture 8 slides (annotations lost due to sys crashes)	Chapter 6
9/25	Function Intro (mini lec by Ivory)		Lecture 9 slides	Chapter 7
9/30	Functions: Types of functions		Lecture 10 slides	Chapter 7,8
10/2	Induction		Lecture 11 slides annotations lost due to sys crashes	Chapter 11. Also read new Induction Notes
10/7	Induction-part 2; pigeonhole principle		Lecture 12 slides	Chapter 11. Also read new Induction Notes
10/10; 10/14	Induction; Recursive Definitions		Lecture 13 slides	Chapter 11, 12. Also read new Induction Notes
10/16	Graphs; Subgraphs; Isomorphisms		Lecture 14 slides (annotations lost due to crash)	Chapter 9
10/21	Trees		Lecture 16 slides (some annotations lost due to crash)	See Section 5.7 in Math for CS book for free trees See Chapter 13 in textbook for rooted trees (Section 13.5 is not covered in this course)
10/23	Two-way bounding		Lecture 17 slides by Adam Vollrath Projector Notes	Chapter 10
10/28	Permutations		Mini-lecture by Lingyu Xu	Sections 8,4, 8.5 of textbook
10/30	More Trees		Lecture 19 slides	See Section 5.7 in Math for CS book for free trees See Chapter 13 in textbook for rooted trees (Section 13.5 is not covered in this course)
11/4	Proof by contradiction		Lecture 20 slides	Chapter 17 in textbook
11/6	Big-O and Algorithms-I		Lecture 21 slides	Chapter 14 in textbook
11/11	Big-O and Algorithms-II		Lecture 22 slides	Chapter 15 in textbook
11/13	Collections of Sets		Lecture 23 slides	Chapter 18 in textbook
11/18	Examlet
TENTATIVE SCHEDULE	----------------	----------------	----------------	----------------
11/20	Combinations; State Diagrams		Lecture 24 slides	Chapter 19 in textbook
12/2	Mini Lecture-uncountability		Included in next lecture slides	Chapter 19 in textbook
12/4	Countability; uncomputability		Lecture 25 slides	Chapter 20 in textbook
12/9	Wrap up; look ahead; review