## CSU200 Discrete Structures Schedule Spring 2009

### Instructor Eric Miles

Week Class Date Topics Reading Due
1 1 Jan 5
Overview and Course Organization
Get online homework account
2 Jan 7
Module 1: Computers and Computing
Binary Representation of Numbers
Converting Between Binary and Decimal
1.1 Binary Representation
1.5 Converting Between Decimal and Binary
3 Jan 8
1.4 Octal Representation

2 4 Jan 12
Representing Negative Numbers
Two's Complement
Arithmetic Operations in Binary
1.6 Representing Negative Numbers: Two's Complement
5 Jan 14
Basic Logic and Logic Gates
2.1 Transistors and Switches
2.2 Basic Logic Gates: AND, OR, NOT
3.1 Truth Values
6 Jan 15
More Logic Gates
2.3 Other Logic Gates: NAND, NOR, XOR, XNOR
Jan 16
OLHW1: Binary, Octal, Hex

3
Jan 19
Martin Luther King Jr.'s Birthday – NO CLASS
Jan 21
Happy Wednesday! – CLASS CANCELED
7 Jan 22
Logic: Truth Values and Tables
Logical Equivalence
2.4 Binary Arithmetic: Ripple Carry Adders
3.1, 3.2 Truth Values and Tables
3.3 Logical Equivalence
Jan 23
OLHW2: Logic, Logic Gates

4 8 Jan 26
Module 2: Encryption
Caesar Shift
Simple Substitution Cipher
4.1 Simple Shift Ciphers
4.2 Encoding
4.3 The mod Function
4.4 Simple Substitution Ciphers
WHW1: Patterns, Binary Arithmetic
9 Jan 28
Modular Arithmetic
Powers Modulo n
4.5 Modular Arithmetic
4.6 Powers mod n
10 Jan 29
Prime Numbers
Prime Number Decomposition
Division Algorithm
5.1 Divides
5.2 Primes
5.3 Division
Jan 30
OLHW3: Modular Arithemetic, Linear Encryption

5 11 Feb 2
GCD, LCM
Euclidean Algorithm
5.4 Greatest Common Divisor and Least Common Multiple
5.5 Euclidean Algorithm
12 Feb 4
Extended Euclidean Algorithm
Introduction to RSA
5.6 Extended Euclidean Algorithm
13 Feb 5
EXAM 1

6 14 Feb 9
Module 3: Counting
Set Builder Notation
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation
15 Feb 11
Set Operations
Power Set
Cartesian Product
6.3 Venn Diagrams
6.4.1-6.4.5 Set Operations
6.4.6 Power Set
6.4.7 Cartesian Product
16 Feb 12
Simple Counting
Product and Sum Rules
Inclusion-Exclusion Principle
Ch. 7 Introduction
7.1 Basic Rules
7.2 Inclusion-Exclusion Principle
Feb 13
OLHW4: Prime Decomposition, gcd, lcm

7
Feb 16
President's Day – NO CLASS
17 Feb 18
Pigeonhole Principle
Permutations
Combinations
7.3 Pigeonhole Principle
7.4 Permutations
7.5 Combinations
18 Feb 19
Binomial Theorem
Pascal's Triangle
7.6 Binomial Theorem
WHW2: Modular Arithmetic, Cryptography
Feb 20
OLHW5: Sets, Set Operations, Power Set, Cartesian Product

8 19 Feb 23
Balls in Bins
7.7 Balls in Bins
20 Feb 25
Probability Basics
8.1 Definitions and Basic Properties
Feb 26
Hiring Talk: David Molnar, 10:45am in 366WVH – CLASS CANCELED
Feb 27
OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle

Mar 2
Mar 4
Mar 5
Spring Break – NO CLASS

9 21 Mar 9
More Probability
8.2 (Probability) Examples
22 Mar 11
Even More Probability
Proof Concepts & Techniques
23 Mar 12
Proofs (continued)
WHW3: Counting
Mar 13
OLHW7: Permutations and Combinations

10 24 Mar 16
EXAM 2
25 Mar 18
Module 4: Algorithms
Sorting and Searching
9.1 Algorithms for Searching
9.3 Algorithms for Sorting
26 Mar 19
Discussion of Exam 2

11 27 Mar 23
Analysis of Sorting and Searching
9.2 Analysis of Algorithms
OLHW8: Probability
28 Mar 25
Sequences
Sums
10.1 Sequences
10.2 Series and Partial Sums
29 Mar 26
Recurrences
Ch. 11 Recurrences

12 30 Mar 30
Recurrences (continued)
Growth of Functions
Ch. 11 Recurrences
Ch. 12 Growth of Functions
OLHW9: Searching
31 Apr 1
Module 5: Networks
Graphs
13.1 Simple Graphs
13.2 Weighted Graphs
13.3 Graph Data Structures
32 Apr 2
More Graphs
13.4 Graph Problems
13.5 Graph Theory
13.6 Directed Graphs

13 33 Apr 6
Relations
Ch. 14 Introduction
14.1 Examples
14.2 Properties of Relations
OLHW10: Sorting, Sequences, Sums
34 Apr 8
Equivalence Relations
Partitions
14.3 Equivalence Relations
35 Apr 9
Review
WHW4: Analysis of Algorithms, Sums, Graphs

Apr 13
Extended Office Hours: 10am - 2pm – CLASS CANCELED
OLHW11: Graphs
Apr 15