## CSU200 Discrete Structures Spring 2007

### Instructor: Ana-Maria Visan

Week Class Date CSU200 Topics Reading Due

1 1 8-Jan Overview and Course Organization   get on-line homework account
2 10-Jan 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   15-Jan Martin Luther King Day
4 17-Jan Representing Negative Numbers
Two's Complement
Arithmetic Operations in Binary
1.5 Representing Negative Numbers:
Two’s Complement

5 18-Jan 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
OLHW1: binary, octal, hex

3 6 22-Jan More Logic Gates Other Logic Gates: NAND, NOR, XOR, XNOR
7 24-Jan Ripple Carry Adder 2.4 Binary Arithmetic: Ripple Carry Adders WHW1: patterns and binary arithmetic
8 25-Jan 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
OLHW2: logic and logic gates

4 9 29-Jan Modular Arithmetic
Division Algorithm
Powers Modulo n
4.5 Modular Arithmetic
4.6 Powers mod n

10 31-Jan Prime Numbers
Prime Number Decomposition
5.1 Divides
5.2 Primes
5.3 Division

11 1-Feb EXAM 1

5 12 5-Feb GCD, LCM
Euclidean Algorithm
5.4 Greatest Common Divisor and Least Common Multiple
5.5 Euclidean Algorithm
OLHW3: modular arithemetic
linear encryption
13 7-Feb Introduction to RSA handout
14 8-Feb Module 3: Counting
Set Builder Notation
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation
OLHW4: prime decomposition, gcd, lcm

6 15 12-Feb 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 14-Feb Power Set
Cartesian Product
6.4.5 Power Set
6.4.6 Cartesian Product
WHW2: - modular arithmetic and cryptography
17 15-Feb Simple Counting
Product and Sum Rules
7.1 Basic Rules OLHW5: Sets, Set Operations, Power Set, Cartesian Product

7   19-Feb Presidents' Day
18 21-Feb Inclusion-Exclusion Principle
Pigeonhole Principle
7.2 Inclusion-Exclusion Principle
7.3 Pigeonhole Principle

19 22-Feb Permutations 7.4 Permutations OLHW6: simple counting
inclusion-exclusion
pigeonhole principle

8 20 26-Feb EXAM 2
21 28-Feb Combinations 7.5 Combinations
22 1-Mar More Counting

5-Mar
7-Mar
8-Mar
Spring Break Week

9 23 12-Mar Binomial Theorem
Pascal's Triangle
Sierpinski's Triangle
7.6 Binomial Theorem OLHW7: permutations and combinations
24 14-Mar Probability Basics CH. 8 Introduction
8.1 Definitions and Basic Properties

25 15-Mar More Probability 8.2 (Probability) Examples

10 26 19-Mar Module 4: Algorithms
Sorting and Searching
9.1 Algorithms for Search OLHW8: probability
27 21-Mar Analysis of Sorting and Searching 9.2 Analysis of Algorithms
9.3 Algorithms for Sorting

28 22-Mar Sequences 10.1 Sequences WHW3: - counting

11 29 26-Mar Sums
Proof by Induction
10.2 Series and Partial Sums OLHW9: sorting and searching
30 28-Mar Recurrences
Proof by Induction
Ch. 11 Recurrences
31 29-Mar EXAM 3

12 32 2-Apr Growth of Functions Ch. 12 Growth of Functions OLHW10: sequences and sums
33 4-Apr Module 5: Networks
Graphs
Ch. 13 Introduction
13.1 Simple Graphs
13.3 Graph Data Structures

34 5-Apr Graph Problems 13.4 Graph Problems

13 35 9-Apr Graph Theory 13.5 Graph Theory OLHW11: graphs
36 11-Apr Relations Ch. 14 Introduction
14.1 Examples (of Relations)

37 12-Apr More Relations 14.2 Properties of Relations
14.3 Equivalence Relations
WHW4: Analysis of Algorithms, Sums, Graphs

14   16-Apr Patriots' Day
38 18-Apr Final Review