## CSU200 Discrete Structures Schedule Fall 2007

### Professors Aslam and Fell

Week Class Date CS200 Topics Review Sessions Reading Due
1 1 5-Sep Overview and Course Organization     get on-line homework account
2 6-Sep 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

Octal Representation
1.3 Octal Representation

4 12-Sep Representing Negative Numbers
Two's Complement
Arithmetic Operations in Binary
1.5 Representing Negative Numbers: Two’s Complement
5 13-Sep 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

14-Sep       OLHW1: binary, octal, hex

3 6 17-Sep More Logic Gates   Other Logic Gates: NAND, NOR, XOR, XNOR
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 and binary arithmetic
8 20-Sep 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

21-Sep       OLHW2: logic and logic gates

4 9 24-Sep Modular Arithmetic
Division Algorithm
Powers Modulo n
4.5 Modular Arithmetic
4.6 Powers mod n

10 26-Sep Prime Numbers
Prime Number Decomposition
5.1 Divides
5.2 Primes
5.3 Division

11 27-Sep GCD, LCM
Euclidean Algorithm
5.4 Greatest Common Divisor and Least Common Multiple
5.5 Euclidean Algorithm

28-Sep       OLHW3: modular arithemetic
linear encryption

5 12 1-Oct EXAM 1
13 3-Oct Introduction to RSA   handout
14 4-Oct Module 3: Counting
Set Builder Notation
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation

5-Oct       OLHW4: prime decomposition, gcd, lcm

6   8-Oct Columbus Day - NO CLASS
15 10-Oct
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 and cryptography
16 11-Oct Power Set
Cartesian Product
6.4.5 Power Set
6.4.6 Cartesian Product

12-Oct       OLHW5: Sets, Set Operations, Power Set, Cartesian Product

7 17 15-Oct Simple Counting
Product and Sum Rules
Ch. 7 Introduction
7.1 Basic Rules

18 17-Oct Inclusion-Exclusion Principle
Pigeonhole Principle
7.2 Inclusion-Exclusion Principle
7.3 Pigeonhole Principle

19 18-Oct Permutations   7.4 Permutations
19-Oct       OLHW6: simple counting
inclusion-exclusion
pigeonhole principle

8 20 22-Oct Combinations   7.5 Combinations
21 24-Oct Binomial Theorem
Pascal's Triangle
Sierpinski's Triangle
7.6 Binomial Theorem
22 25-Oct Balls in Bins   7.7 Balls in Bins
26-Oct       OLHW7: permutations and combinations

9 23 29-Oct Probability Basics   Ch. 8 Introduction
8.1 Definitions and Basic Properties

24 31-Oct More Probability   8.2 (Probability) Examples WHW3: - counting
25 1-Nov Module 4: Algorithms
Sorting and Searching
9.1 Algorithms for Search
2-Nov       OLHW8: probability

10 26 5-Nov EXAM 2
27 7-Nov Analysis of Sorting and Searching   9.2 Analysis of Algorithms
9.3 Algorithms for Sorting

28 8-Nov Sequences   10.1 Sequences
9-Nov       OLHW9: sorting and searching

11   12-Nov Veteran's Day - NO CLASS
29 14-Nov Sums
Proof by Induction
10.2 Series and Partial Sums
30 15-Nov Recurrences
Proof by Induction
Ch. 11 Recurrences
16-Nov       OLHW10: sequences and sums

12 31 19-Nov Growth of Functions   Ch. 12 Growth of Functions
21-Nov Thanksgiving Break - NO CLASS
22-Nov
23-Nov

13 32 26-Nov Module 5: Networks
Graphs
Ch. 13 Introduction
13.1 Simple Graphs
13.3 Graph Data Structures

33 28-Nov More Graphs   13.4 Graph Problems
13.5 Graph Theory
WHW4: Analysis of Algorithms, Sums, Graphs
34 29-Nov Relations   Ch. 14 Introduction
14.1 Examples (of Relations)

30-Nov       OLHW11: graphs

14 35 3-Dec More Relations   14.2 Properties of Relations
14.3 Equivalence Relations

36 5-Dec Final Review     OLHW12: review (optional)

15   13-Dec FINAL EXAM
3:30 PM
Prof. Aslam Section - TBA
Prof. Fell Section - TBA