# Topics

DISCRETE COMPUTATIONAL STRUCTURES
Com S 330

Course Topics

The following is a tentative schedule of the topics we will be covering in class.

Week Date Book Chapters Topics
1 Jan 10 Rosen 1.1 Introduction and Course Policies
Introduction to Logic
Logical Operators, Truth Tables
1 Jan 12 Rosen 1.1 Conditional Satements
Translating English Sentences
1 Jan 14 Rosen 1.2 Logical Equivalences
2 Jan 17 - University Holiday
2 Jan 19 Rosen 1.3 Predicates and Quantifiers
2 Jan 21 Rosen 1.4 Nested Quantifiers
3 Jan 24 Rosen 1.4 Translating between English and
Logical Expressions with Quantifiers
3 Jan 26 Rosen 1.5 Rules of Inference
3 Jan 28 Rosen 1.5 Valid Arguments
4 Jan 31 Rosen 1.6 Direct and Indirect Proofs
4 Feb 2 Rosen 1.7 Proof Methods and Strategy
4 Feb 4 Rosen 2.1 Introduction to Sets
5 Feb 7 Rosen 2.1 Countable and Uncountable Sets
Power Sets, Cartesian Products
5 Feb 9 Rosen 2.2 Set Operations, Set Identities
5 Feb 11 Rosen 2.2 Proofs of Set Properties
6 Feb 14 Rosen 2.2 Generalized Unions and Intersections
Computer Representation of Sets
6 Feb 16 Rosen 2.3 Introduction to Functions
One-to-one and Onto Functions
6 Feb 18 Rosen 2.3 Inverse, Converse and Composition of Functions
7 Feb 21 Rosen 2.3 Proving Properties of Functions
7 Feb 23 Rosen 8.1 Relations
Properties of Relations
7 Feb 25 - Exam I: Sets & Logic
8 Feb 28 Rosen 8.5 Equivalence Relations
Equivalence Classes and Partitions
8 Mar 2 Rosen 8.6 Partial Orders
8 Mar 4 Rosen 2.4 Sequences and Summations
9 Mar 7 Rosen 2.4 Proving Sets Countable by Dovetailing
9 Mar 9 Rosen 2.4 Proving Sets Uncountable by Diagonalization
9 Mar 11 - Some Problems are Unsolvable
- Mar 14 - Spring Break
- Mar 16 - Spring Break
- Mar 18 - Spring Break
10 Mar 21 Rosen 4.1 Mathematical Induction
10 Mar 23 Rosen 4.2 Strong Induction
Strengthening the Inductive Hypothesis
10 Mar 25 Rosen 4.3 Inductive and Recursive Definitions
11 Mar 28 Rosen 4.3 Structural Induction
11 Mar 30 Rosen 5.1 Basic Counting Techniques
11 Apr 1 Rosen 5.2 PigeonHole Principle
12 Apr 4 Rosen 5.3 Permutations
12 Apr 6 Rosen 5.3 Combinations
12 Apr 8 - Exam II: Functions, Relations & Induction
13 Apr 11 Rosen 5.4 Binomial Theorem
13 Apr 13 Rosen 5.5 Generalized Permutations and Combinations
13 Apr 15 Rosen 5.5 Combinations with Repetitions
Permutations with Indistinguishable Objects
14 Apr 18 Rosen 6.1 Introduction to Probability
14 Apr 20 Rosen 6.2 Finite and Infinite Sample Space
Conditional Probability
14 Apr 22 Rosen 6.2, 7.5 Independence in Probability
Inclusion-Exclusion Principle
15 Apr 25 Rosen 9.1, 9.2, 9.4, CLRS B.4 Introduction to Graphs
15 Apr 27 Rosen 10.1, CLRS B.5 Introduction to Trees
15 Apr 29 Rosen 10.1, CLRS B.5 Properties of Trees and Graphs
- May 4 - Exam III: Counting, Probability
& Graph Theory