## CSU200 Discrete Structures Schedule Spring 2008

### Instructor Dan Brown

Week Class Date Topics Reading Due
1 1 Jan 7 Overview and Course Organization Get online homework account
2 Jan 9 Module 1: Computers and Computing
Binary Representation of Numbers
Converting Between Binary and Decimal
Ch. 1 Introduction
1.1 Binary Representation
1.4 Converting Between Decimal and Binary
1.3 Octal Representation

2 Jan 14 Snow Day! – CLASS CANCELLED
4 Jan 16 Representing Negative Numbers
Two's Complement
Arithmetic Operations in Binary
1.5 Representing Negative Numbers: Two's Complement
5 Jan 17 Basic Logic and Logic Gates Chs. 2, 3 Introductions
2.1 Transistors and Switches
2.2 Basic Logic Gates: AND, OR, NOT
3.1 Truth Values
Jan 18 OLHW1: Binary, Octal, Hex

3 Jan 21 Martin Luther King Jr.'s Birthday – NO CLASS
6 Jan 23 More Logic Gates
Other Logic Gates: NAND, NOR, XOR, XNOR
7 Jan 24 Ripple Carry Adder
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
WHW1: Patterns, Binary Arithmetic
Jan 25 OLHW2: Logic, Logic Gates

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

5 11 Feb 4 GCD, LCM
Euclidean Algorithm
5.4 Greatest Common Divisor and Least Common Multiple
5.5 Euclidean Algorithm
12 Feb 6 Introduction to RSA The Mathematical Guts of RSA Encryption
13 Feb 7 EXAM 1
Feb 8 OLHW4: Prime Decomposition, gcd, lcm

6 14 Feb 11 Module 3: Counting
Set Builder Notation
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation
15 Feb 13 Set Operations
Computer Representation of Sets
6.3 Venn Diagrams
6.4.1-6.4.4 Set Operations
6.5 Computer Representation of Sets
WHW2: Modular Arithmetic, Cryptography
16 Feb 14 Power Set
Cartesian Product
6.4.5 Power Set
6.4.6 Cartesian Product

7 Feb 18 President's Day – NO CLASS
17 Feb 20 Simple Counting
Product and Sum Rules
Ch. 7 Introduction
7.1 Basic Rules
18 Feb 21 Inclusion-Exclusion Principle
Pigeonhole Principle
7.2 Inclusion-Exclusion Principle
7.3 Pigeonhole Principle
Feb 22 OLHW5: Sets, Set Operations, Power Set, Cartesian Product

8 19 Feb 25 Permutations
Combinations
7.4 Permutations
7.5 Combinations
20 Feb 27 Binomial Theorem
Pascal's Triangle
Sierpinski's Triangle
7.6 Binomial Theorem
Feb 28 Happy Thursday! – CLASS CANCELLED
Feb 29 OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle

Mar 3
Mar 5
Mar 6
Spring Break – NO CLASS

9 21 Mar 10 Balls in Bins 7.7 Balls in Bins
22 Mar 12 Probability Basics Ch. 8 Introduction
8.1 Definitions and Basic Properties
23 Mar 13 More Probability 8.2 (Probability) Examples
Mar 14 OLHW7: Permutations and Combinations

10 24 Mar 17 Review WHW3: Counting
25 Mar 19 EXAM 2
26 Mar 20 Module 4: Algorithms
Sorting and Searching
9.1 Algorithms for Search
Mar 21 OLHW8: Probability

11 27 Mar 24 Analysis of Sorting and Searching 9.2 Analysis of Algorithms
9.3 Algorithms for Sorting
28 Mar 26 Sequences 10.1 Sequences
29 Mar 27 Sums 10.2 Series and Partial Sums
Mar 28 OLHW9: Searching

12 30 Mar 31 Recurrences Ch. 11 Recurrences
31 Apr 2 Growth of Functions Ch. 12 Growth of Functions
32 Apr 3 Module 5: Networks
Graphs
Ch. 13 Introduction
13.1 Simple Graphs
13.3 Graph Data Structures
Apr 4 OLHW10: Sorting, Sequences, Sums

13 33 Apr 7 More Graphs 13.4 Graph Problems
13.5 Graph Theory
34 Apr 9 Relations Ch. 14 Introduction
14.1 Examples
35 Apr 10 More Relations 14.2 Properties of Relations
14.3 Equivalence Relations
Apr 11 OLHW11: Graphs

14 36 Apr 14 Review WHW4: Analysis of Algorithms, Sums, Graphs
37 Apr 16 Review
Apr 17
Apr 18 FINAL EXAM
5 SL, 1-3pm
OLHW12: Review (optional)