CS 242, Section 002 Sonoma State University Fall, 2021 Discrete Structures for Computer Science Instructor: Henry M. Walker Lecturer, Sonoma State University Professor Emeritus of Computer Science and Mathematics, Grinnell College

# Tentative Class Schedule

Tuesday Thursday
August 17 Preparation
• Last day before classes start
August 19 Unit A: Getting Started
• Introductions
• Quick Course Overview
• Clicker set up
• Status Check—where are we really?

Unit B: Logic and Proof
• 1.1 Propositional Logic
• 1.2 Applications of Propositional Logic
August 24 Unit B: Logic and Proof
• 1.3 Propositional Equivalences
• 1.4 Predicates and Quantifiers

• 1.2.6 Circuits
• 12.2 Representing Boolean Functions
• 12.3 Logic Gates
August 26 Unit B: Logic and Proofs
• 12.4.1-12.4.2 Minimization of Circuits

• 1.5 Nested Quantifiers
• 1.6 Rules of Inference
• 1.7 Introduction to Proofs—Introduction
Due: Assignment 1
August 31 Unit C: Basic Structures
• 1.7 Introduction to Proofs, continued
• 1.8 Proof Methods and Strategy

• Quiz 1
September 2 Unit C: Basic Structures
• 1.8 Proof Methods and Strategy, continued

• 2.1 Sets
• 2.2 Set Operations
• 2.3 Functions
Due: Assignment 2
September 7 Unit C: Basic Structures
• 2.5 Cardinality of Sets
• 3.1 Algorithms
• 2.4 Sequences and Summations

September 9 Unit D: Algorithms
• 3.1 Algorithms, continued
• 2.4 Sequences and Summations, continued

• 9.1 Relations and Their Properties
• 9.2 n-ary Relations and Their Application
Due: Assignment 3
September 14 Unit E: Induction and Recursion
• 5 Induction and Recursion (3 lectures)
• 5.1 Mathematical Induction
• 5.2 Strong Induction

• Quiz 2
September 16 Unit E: Induction and Recursion
• More Induction
• 5.3 Recursive Definitions

• Review of Previous Material
Due: Assignment 4
September 21 Unit E: Induction and Recursion
• 5.4 Recursive Algorithms

• Review of Previous Material
September 23
• 5.4 Recursive Algorithms

• Questions/Test Review
Due: Assignment 5
Due: Optional Quiz 2 Revision
September 28 Test 1 September 30 Unit E: Induction and Recursion
• Relations and their properties
• More Recursion

October 5 Unit F: Graphs
• 10.1 Graphs and Graph Models
• 10.2 Graph Terminology and Special Types of Graphs

• 10.3 Representing Graphs
• 10.2 Hall's Marriage Theorem
• October 7 Unit F: Graphs
• 10.4 Connectivity
• 10.6 Shortest-Path Problem

• 10.3 Graph Isomorphism
Due: Assignment 6
October 12 Unit F: Graphs
• 10.5.2 Euler Paths
• 10.5.3 Hamilton Paths
• 10.7 Planar Graphs

October 14 Unit G: Trees
• 11.1 Introduction to Trees
• 11.3 Tree Traversals and other Recursive Tree Algorithms
Due: Assignment 7
October 19 Unit G: Trees
• More Recursive Tree Algorithms
October 21 Unit G: Trees
• Still More Recursive Tree Algorithms
• 11.2 Applications of Trees

• Questions/Test Review
Due: Assignment 8
October 26 Test 2 October 28 Unit H: Counting
• 6.1 The Basics of Counting
• 6.2 The Pigeonhole Principle
November 2 Unit H: Counting
• 6.3 Permutations and Combinations
• 6.4 Binomial Coefficients and Identities
November 4 Unit H: Counting
• 6.5 Generalized Permutations and Combinations
Due: Assignment 9
November 9 Unit H: Counting
• Tree Applications
• 11.2.3 Decision Trees
• 11.2.4 Prefix Codes (Huffman Codes)
• Quiz 4
November 11 Holiday: Thursday, November 11 (Veterans Day)
November 16 Unit H: Counting
• Review of Tree Algorithms and Counting Techniques
November 18 Unit I: Discrete Probability
• 7.1 An Introduction to Discrete Probability
• 7.2 Probability Theory
Due: Assignment 10
November 23 Unit I: Discrete Probability
• 7.4 Expected Value and Variance

• Quiz 5
November 25 Holiday: Thanksgiving (November 25)
November 30 Unit I: Discrete Probability
• Probability estimation through simulation
• Examples and Exercises
Due: Assignment 11
December 2 Last day of class: Thursday, December 2
• Examples and Exercises
• Semester Wrap-up
December 7 Exam schedule: December 6-10 December 9