## CSU200 Discrete Structures Schedule Fall 2006

### Professors Aslam and Fell

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

12,13-Sep   Review and Practice:
Binary, Octal, Hex

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

15-Sep       OLHW1: binary, octal, hex

3 6 18-Sep More Logic Gates   Other Logic Gates: NAND, NOR, XOR, XNOR
19,20-Sep   Review and Practice:
Binary Arithmetic
Logic and Logic Gates

7 20-Sep Ripple Carry Adder   2.4 Binary Arithmetic: Ripple Carry Adders WHW1: patterns and binary arithmetic
8 21-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

22-Sep       OLHW2: logic and logic gates

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

26,27-Sep   Exam Review
10 27-Sep Prime Numbers
Prime Number Decomposition
5.1 Divides
5.2 Primes
5.3 Division

11 28-Sep EXAM 1
29-Sep

5 12 2-Oct GCD, LCM
Euclidean Algorithm
5.4 Greatest Common Divisor and Least Common Multiple
5.5 Euclidean Algorithm
OLHW3: modular arithemetic
linear encryption
3,4-Oct   Review and Practice:
modular arithmetic
GCD, LCM

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

6-Oct       OLHW4: prime decomposition, gcd, lcm

6   6-Oct Columbus Day - NO CLASS
10,11-Oct   Review and Practice:
open problem session

15 11-Oct
Set Operations
Computer Representation of Sets
6.3 Venn Diagrams
6.4.1-6.4.2 Set Operations
6.5 Computer Representation of Sets

16 12-Oct Power Set
Cartesian Product
6.4.5 Power Set
6.4.6 Cartesian Product
WHW2: - modular arithmetic and cryptography
13-Oct       OLHW5: Sets, Set Operations, Power Set, Cartesian Product

7 17 16-Oct Simple Counting
Product and Sum Rules
7.1 Basic Rules
17,18-Oct   Review and Practice:
counting & Exam

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

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

8 20 23-Oct EXAM 2
24,25-Oct   Review and Practice:
combinations
permutations

21 25-Oct Combinations   7.5 Combinations
22 26-Oct More Counting
27-Oct

9 23 30-Oct Binomial Theorem
Pascal's Triangle
Sierpinski's Triangle
7.6 Binomial Theorem OLHW7: permutations and combinations
31-Oct
1-Nov
Review and Practice:
more counting

24 1-Nov Probability Basics   CH. 8 Introduction
8.1 Definitions and Basic Properties

25 2-Nov More Probability   8.2 (Probability) Examples
3-Nov

10 27 6-Nov Module 4: Algorithms
Sorting and Searching
9.1 Algorithms for Search OLHW8: probability
7,8-Nov   Review and Practice:
algebra and special functions

28 8-Nov Analysis of Sorting and Searching   9.2 Analysis of Algorithms
29 9-Nov Sequences   10.1 Sequences WHW3: - counting
10-Nov

11 30 13-Nov Sums
Proof by Induction
10.2 Series and Partial Sums OLHW9: sorting and searching
14,15-Nov   Exam Review
31 15-Nov Recurrences
Proof by Induction
Ch. 11 Recurrences
32 16-Nov EXAM 3
17-Nov

12 33 20-Nov Growth of Functions   Ch. 12 Growth of Functions
21,22-Nov   No Review Sessions
21-Nov Thanksgiving Break - NO CLASS
22-Nov
23-Nov

13 34 27-Nov Module 5: Networks
Graphs
Ch. 13 Introduction
13.1 Simple Graphs
13.3 Graph Data Structures
OLHW10: sequences and sums
28,29-Nov   Review and Practice:
graphs

35 29-Nov More Graphs   13.4 Graph Problems
13.5 Graph Theory

36 30-Nov Relations   Ch. 14 Introduction
14.1 Examples (of Relations)

36 1-Dec

14 37 4-Dec More Relations   14.2 Properties of Relations
14.3 Equivalence Relations
WHW4: Analysis of Algorithms, Sums, Graphs
OLHW11: graphs
5,6-Dec   Final Review
38 6-Dec Final Review

15   13-Dec FINAL EXAM
10:30 AM
Prof. Aslam Section - TBA
Prof. Fell Section - TBA