DISCRETE COMPUTATIONAL STRUCTURES
Com S 330


Course Topics

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

Date Book Chapters Topics
Mon, Aug 24 Rosen 1.1 Introduction and Course Policies
Introduction to Logic
Logical Operators, Truth Tables
Wed, Aug 26 Rosen 1.1 Conditional Satements
Translating English Sentences
Fri, Aug 28 Rosen 1.2 Logical Equivalences
Mon, Aug 31 Rosen 1.2 Proving New Logical Equivalences
Wed, Sept 2 Rosen 1.3 Predicates and Quantifiers
Fri, Sept 4 Rosen 1.4 Nested Quantifiers
Translating from Nested Quantifiers into English
Mon, Sept 7 - University Holiday
Wed, Sept 9 Rosen 1.4 Translating from English into Nested Quantifiers
Negating Nested Quantifiers
Fri, Sept 11 Rosen 1.5 Rules of Inference
Using Rules of Inference to Build Arguments
Mon, Sept 14 Rosen 1.5 Rules of Inference for Quantified Statements
Wed, Sept 16 Rosen 1.6, 1.7 Direct and Indirect Proofs
Proof Methods and Strategy
Fri, Sept 18 Rosen 2.1 Introduction to Sets
Mon, Sept 21 Rosen 2.1 Countable and Uncountable Sets
Power Sets, Cartesian Products
Wed, Sept 23 Rosen 2.2 Set Operations, Set Identities
Fri, Sept 25 Rosen 2.2 Proofs of Set Properties
Mon, Sept 28 Rosen 2.2, 2.3 Generalized Unions and Intersections
Computer Representation of Sets
Introduction to Functions
Wed, Sept 30 Rosen 2.3 One-to-one and Onto Functions
Inverse Functions; Composition of Functions
Fri, Oct 2 Rosen 2.3 Proving Properties of Functions
Mon, Oct 5 Rosen 8.1 Relations
Properties of Relations
Wed, Oct 7 Rosen 8.5 Equivalence Relations
Fri, Oct 9 - Exam I: Sets & Logic
Mon, Oct 12 Rosen 8.5 Equivalence Classes and Partitions
Wed, Oct 14 Rosen 8.6 Partial Orders
Fri, Oct 16 Rosen 2.4 Sequences and Summations
Mon, Oct 19 Rosen 2.4 Proving Sets Countable and Uncountable
Dovetailing
Wed, Oct 21 Rosen 2.4 Diagonalization
Fri, Oct 23 Rosen 4.1 Mathematical Induction
Mon, Oct 26 Rosen 4.2 Strong Induction
Strengthening the Inductive Hypothesis
Wed, Oct 28 Rosen 4.3 Inductive and Recursive Definitions
Fri, Oct 30 Rosen 4.3 Structural Induction
Mon, Nov 2 Rosen 5.1 Basic Counting Techniques
Wed, Nov 4 Rosen 5.2 PigeonHole Principle
Fri, Nov 6 Rosen 5.3 Permutations
Mon, Nov 9 Rosen 5.3 Combinations
Wed, Nov 11 Rosen 5.4 Binomial Theorem
Fri, Nov 13 - Exam II: Functions, Relations, Induction
& Basics of Counting
Mon, Nov 16 Rosen 5.5 Generalized Permutations and Combinations
Wed, Nov 18 Rosen 5.5 Combinations with Repetitions
Permutations with Indistinguishable Objects
Fri, Nov 20 Rosen 6.1 Introduction to Probability
Mon, Nov 23 - Fall Break
Wed, Nov 25 - Fall Break
Fri, Nov 27 - Fall Break
Mon, Nov 30 Rosen 6.2 Finite and Infinite Sample Space
Conditional Probability
Wed, Dec 2 Rosen 6.2, 7.5 Independence in Probability
Inclusion-Exclusion Principle
Fri, Dec 4 Rosen 9.1, 9.2, 9.4, CLRS B.4 Introduction to Graphs
Mon, Dec 7 Rosen 10.1, CLRS B.5 Introduction to Trees
Wed, Dec 9 Rosen 10.1, CLRS B.5 Properties of Trees and Graphs
Fri, Dec 11 - Review
Mon, Dec 14 - Exam III: Counting, Probability
& Graph Theory

Iowa State University - Computer Science Department - Top of this page