## CSU200 Discrete Structures Schedule Fall 2005

### Professors Aslam and Fell

Week Class Date CS200 Topics Review Sessions Due
1 1 7-Sep Overview and Course Organization   get on-line homework account
2 8-Sep Module 1: Search Searches:
demo Linear, Binary, and Chunk searches

2 3 12-Sep specification, pseudocode: assignment, if/then/else, while, for, arrays
13-Sep   algebra review - linear functions, exponentials, logs
4 14-Sep analysis of an algorithm, counting compares - analyze the search algorithms
5 15-Sep growth of functions - linear, square root, log2
16-Sep     OLHW1: pseudocode , search algorithms, algebra review: variable and expressions, exponents, logarithms

3 6 19-Sep Module 2: Sort
demo Insertion and Merge sorts

20-Sep   algebra review - special functions
7 21-Sep specification - start analysis   WHW1: compare functions, What n makes one search better than another?
8 22-Sep speed analysis: looping, summation notation
23-Sep     OLHW2: search algorithm analysis, algebra review: special functions ... , the sorts (insertion, selection, merge)

4 9 26-Sep speed analysis: recurrences, proof by induction
27-Sep   exam review
10 28-Sep EXAM 1
11 29-Sep correctness: loop invariants, induction
30-Sep     OLHW3: sort analysis, recurrences

5 12 3-Oct more induction proofs: evaluating sums
4-Oct   induction review
13 5-Oct Module 3: Encryption
Caesar shift, single substitution cipher

14 6-Oct modular arithmetic, finite fields (Zp) - linear encryption
OLHW4: modular arithemetic, linear encryption

6 Columbus Day - NO CLASS
11-Oct   division algorithm review
15 12-Oct prime numbers, prime decomposition   WHW2: - some induction, recurrences
16 13-Oct gcd, lcm, Euclidean Algorithm
14-Oct     OLHW5: prime decomposition, gcd, lcm

7 17 17-Oct Extended Euclidean Algorithm, finding inverses for linear encryption   OLHW6: Extended Euclidean Algorithm
18-Oct   exam review
18 19-Oct EXAM 2
19 20-Oct Module 4: Codes
binary, octal, hex representation of integers
NO ONLINE HW this Friday

8 20 24-Oct converting binary to decimal
converting decimal to binary

25-Oct   number representation review
21 26-Oct more binary, hex, octal, ASCII
22 27-Oct error detecting codes
ISBN numbers
hiding messages in pictures (Steganography)

28-Oct     OLHW7: binary, octal, hex, ISBN numbers

9 23 31-Oct Module 5: Counting

1-Nov   review of set notation
24 2-Nov sets: intersection, union
25 3-Nov sets: Cartesian product, power set   WHW3: - twos complement, ...
4-Nov     OLHW8: sets: intersection, union, Cartesian product, power set

10 27 7-Nov simple counting
9-Nov   review of factorials and simple counting
28 9-Nov permutations
29 10-Nov combinations
11-Nov     OLHW9: counting 1 - permutations

11 30 14-Nov more counting
15-Nov   exam review
31 16-Nov combinations and permutations
32 17-Nov Binomial theorem and Pascal's triangle
18-Nov

12 33 21-Nov simple probability   OLHW10: counting 2 - combinations
22-Nov   open review session
23-Nov     NO CLASS, ONLINE HW due on Monday

13 34 28-Nov more probability   OLHW11: probability
29-Nov   exam review
35 30-Nov EXAM 3
36 1-Dec Module 6: Networks
Graphs: definitions and properties

36 2-Dec     NO ONLINE HOMEWORK

14 37 5-Dec Trees: definitions and Properties
6-Dec   final review
38 7-Dec final review   WHW4: graphs and trees

15   13-Dec FINAL EXAM
3:30 PM
Prof. Aslam Section - 224 HT
Prof. Fell Section - 103 CH