## CS1800 Discrete Structures: Spring 2012 Schedule

### Instructor Harriet Fell

Week Class Date Topics Reading Due
1 1 Jan 10
Overview and Course Organization
Get online homework account
2 Jan 12
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
3 Jan 13
Representing Negative Numbers
Two's Complement
1.3 Octal Representation
1.5 Representing Negative Numbers: Two's Complement

2 4 Jan 17
Wrap up of Binary Arithmetic Operations
Basic Logic and Logic Gates
Chs. 2, 3 Introductions
2.1 Transistors and Switches
2.2 Basic Logic Gates: AND, OR, NOT
Jan 18
OLHW1: Binary, Octal, Hex
5 Jan 19
Logic Gates and Logic, contd.
2.3 More Logic Gates: NAND, NOR, XOR, XNOR
3.1 Truth Values
3.2 Truth Tables
6 Jan 20
Logic and Logical Equivalence
Basic circuits
3.3 Logical Equivalence
2.4 Binary Arithmetic: Ripple Carry Adders

3 7 Jan 24
Gem 1: Design of a CPU
OLHW2: Logic, Logic Gates
8 Jan 26
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 27
Modular Arithmetic
Division Algorithm
Powers Modulo n
4.5 Modular Arithmetic
4.6 Powers mod n
5.1 Divides
5.3 Division
WHW1: Binary Arithmetic and Logic

4 10 Jan 31
Collisions in ciphers and hash functions
Prime Numbers
Prime Number Decomposition
5.2 Primes
OLHW3: Modular Arithmetic, Linear Encryption
11 Feb 02
GCD, LCM
Euclid's Algorithm
5.5 Euclid's Algorithm
5.4 Greatest Common Divisor and Least Common Multiple
12 Feb 03
Extended Euclid's Algorithm
Secret-sharing and public key cryptosystems
5.6 Extended Euclid's Algorithm

5 13 Feb 07
Gem 2: RSA
OLHW4: Prime Decomposition, GCD, LCM
14 Feb 09
Module 3: Counting
Ch. 6 Introduction
6.1 Set Basics
15 Feb 10
Set Builder Notation
Set Operations
Computer Representation of Sets
6.2 Set-Builder Notation
6.3 Venn Diagrams
6.4.1-6.4.4 Set Operations
6.5 Computer Representation of Sets

6 16 Feb 14
Power Set
Cartesian Product
6.4.5 Power Set
6.4.6 Cartesian Product
WHW2: Modular Arithmetic, Cryptography
17 Feb 16
Review
Chapters 1 through 5, and handouts
18 Feb 17
Midterm Exam 1

7 19 Feb 21
Simple Counting
Product and Sum Rules
Ch. 7 Introduction
7.1 Basic Rules
OLHW5: Sets, Set Operations, Power Set, Cartesian Product
20 Feb 23
Inclusion-Exclusion Principle
7.2 Inclusion-Exclusion Principle
21 Feb 24
Pigeonhole Principle
7.3 Pigeonhole Principle

8 22 Feb 28
Permutations
Combinations
7.4 Permutations
7.5 Combinations
23 Mar 01
Pascal's Triangle
Binomial Theorem
7.6 Binomial Theorem
OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle
24 Mar 02
Gem 3: Polymerase Chain Reaction
(maybe)

Mar 06
Spring Break – NO CLASS
Mar 08
Spring Break – NO CLASS
Mar 09
Spring Break – NO CLASS

9 25 Mar 13
Probability Basics
Expectation and independence
Ch. 8 Introduction
8.1 Definitions and Basic Properties
8.2 (Probability) Examples
26 Mar 15
More Probability Examples
Conditional Probability
Chapter 8
OLHW7: Permutations and Combinations
27 Mar 16
More Conditional Probability
Bayes Law

10 28 Mar 20
Markov Chains
Matrices
Introduction to Graphs
Ch. 13 Introduction
13.1 Simple Graphs
OLHW8: Probability
29 Mar 22
Gem 4: Web as graph and Google's PageRank
30 Mar 23
Review for Midterm Exam 2
Chapters 6 through 8
WHW3: Counting and Probability

11 31 Mar 27
Midterm Exam 2
32 Mar 29
Module 4: Algorithms
Sorting and Searching
9.1 Algorithms for Search
9.2 Analysis of Algorithms
9.3 Algorithms for Sorting
33 Mar 30
Sequences and Sums
Proof by Induction
10.1 Sequences
10.2 Series and Partial Sums
OLHW9: Conditional Probability and Markov Chains

12 34 Apr 03
More Proofs by Induction
Simple Recurrences
11.1 Specifying Recurrences
11.2 Solving Recurrences
35 Apr 05
Growth of Functions
Ch. 12 Growth of Functions
OLHW10: Sorting and Searching
36 Apr 06
Gem 5: The Stable Matching problem

13 37 Apr 10
Module 5: Networks
Graph Data Structures
13.3 Graph Data Structures
13.4 Graph Problems
38 Apr 12
More Graphs
13.4 Graph Problems
13.5 Graph Theory
39 Apr 13
Graph traversals
Handout
WHW4: Graphs and Algorithms

14 40 Apr 17
Wrapup and review
OLHW11: Graphs
OLHW12: Review (optional)

TBA
FINAL EXAM