CSCE 222: Discrete Structures for Computing

Note: Dates and topics are approximate and subject to change.

Date	Topics	Homework/Quiz
Week 1
08/31	Introduction, Course Organization, Syllabus
09/02	Propositional Logic, Applications of Propositional Logic, Propositional Equivalences Rosen 1.1, 1.2, 1.3
09/04	Predicates and Quantifiers, Nested Quantifiers Rosen 1.4, 1.5
Week 2
09/07	Rules of Inference, Introduction to Proofs, Proof Methods and Strategy Rosen 1.6, 1.7, 1.8
09/09	Sets, Set Operations Rosen 2.1, 2.2	HW 1 due
09/11	Functions Rosen 2.3	Quiz 1
Week 3
09/14	Sequences and Summations, Matrices Rosen 2.4, 2.6
09/16	Algorithms Rosen 3.1	HW 2 due
09/18	The Growth of Functions Rosen 3.2	Quiz 2
Week 4
09/21	Complexity of Algorithms Rosen 3.3
09/23	Mathematical Induction Rosen 5.1	HW 3 due
09/25	Strong Induction and Well-Ordering Rosen 5.2	Quiz 3
Week 5
09/28	Recursive Definitions and Structural Induction Rosen 5.3
09/30	Exam 1 in class.	HW 4 due
10/02	Work through solutions to Exam 1.	Quiz 4
Week 6
10/05	Recursive Algorithms Rosen 5.4
10/07	The Basics of Counting, The Pigeonhole Principle Rosen 6.1, 6.2
10/09	Permutations and Combinations, Binomial Coefficients and Identities Rosen 6.3, 6.4
Week 7
10/12	Generalized Permutations and Combinations, Generating Permutation and Combinations Rosen 6.5, 6.6
10/14	Applications of Recurrence Relations, Solving Linear Recurrence Relations Rosen 8.1, 8.2	HW 5 due
10/16	Divide and Conquer Algorithms and Recurrence Relations Rosen 8.3	Quiz 5
Week 8
10/19	Generating Functions, Inclusion-Exclusion, Applications of Inclusion-Exclusion Rosen 8.4, 8.5, 8.6
10/21	Relations and their Properties Rosen 9.1	HW 6 due
10/23	n-ary Relations and their Applications, Representing Relations Rosen 9.2, 9.3	Quiz 6
Week 9
10/26	Equivalence Relations, Partial Orderings Rosen 9.5, 9.6
10/28	Exam 2 in class.
10/30	Work through solutions to Exam 2.	HW 7 due Quiz 7
Week 10
11/02	Review of Induction and Recursion Rosen 5
11/04	Review of Counting Rosen 6, 8
11/06	Review of Relations Rosen 9
Week 11
11/09	Graphs Rosen 10
11/11	Introduction to Trees Rosen 11.1	HW 8 due
11/13	Applications of Trees Rosen 11.2	Quiz 8
Week 12
11/16	Tree Traversal Rosen 11.3
11/18	Finite State Machines Rosen 13.3	HW 9 due
11/20	Finite State Machines Rosen 13.3	Quiz 9
Week 13
11/23	Language Recognition Rosen 13.4
11/25	Thanksgiving Break. No class.
11/27	Thanksgiving Break. No class.
Week 14
11/30	Turing Machines Rosen 13.5
12/02	Exam 3 in class.
12/04	Work through solutions to Exam 3.	HW 10 due Quiz 10
Week 15
12/07	Review for Final Exam.
12/09	Review for Final Exam.
Final Exam
12/16	Final Exam: 10:30am - 12:30pm, ETB 2005