CS1800 Discrete Structures: Fall 2011 Schedule

Instructors Rajmohan Rajaraman and Ravi Sundaram

Week Class Date Topics Reading Due
1 1 Sep 07
Overview and Course Organization
Get online homework account
2 Sep 08
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

2 3 Sep 12
Representing Negative Numbers
Two's Complement
1.3 Octal Representation
1.5 Representing Negative Numbers: Two's Complement
4 Sep 14
Review of Two's Complement
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
5 Sep 15
Logic Gates and Logic, contd.
2.3 More Logic Gates: NAND, NOR, XOR, XNOR
3.1 Truth Values
3.2 Truth Tables
Sep 16
OLHW1: Binary, Octal, Hex

3 6 Sep 19
Logic and Logical Equivalence
Basic circuits
3.3 Logical Equivalence
2.4 Binary Arithmetic: Ripple Carry Adders
7 Sep 21
Gem 1: Design of a CPU
8 Sep 22
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
Sep 23
OLHW2: Logic, Logic Gates

4 9 Sep 26
Modular Arithmetic
Division Algorithm
Powers Modulo n
4.5 Modular Arithmetic
4.6 Powers mod n
5.1 Divides
5.3 Division
10 Sep 28
Collisions in ciphers and hash functions
Prime Numbers
Prime Number Decomposition
5.2 Primes
WHW1: Binary Arithmetic and Logic
11 Sep 29
GCD, LCM
Euclid's Algorithm
5.5 Euclid's Algorithm
5.4 Greatest Common Divisor and Least Common Multiple
Sep 30
OLHW3: Modular Arithmetic, Linear Encryption

5 12 Oct 03
Extended Euclid's Algorithm
Secret-sharing and public key cryptosystems
5.6 Extended Euclid's Algorithm
13 Oct 05
Gem 2: RSA
14 Oct 06
Module 3: Counting
Set Builder Notation
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation
6.3 Venn Diagrams
Oct 07
OLHW4: Prime Decomposition, GCD, LCM

6
Oct 10
Columbus Day – NO CLASS
15 Oct 12
Set Operations
Computer Representation of Sets
6.4.1-6.4.4 Set Operations
6.4.5 Power Set
6.4.6 Cartesian Product
6.5 Computer Representation of Sets
WHW2: Modular Arithmetic, Cryptography
16 Oct 13
Simple Counting
Product and Sum Rules
Inclusion-Exclusion Principle
Pigeonhole Principle
Ch. 7 Introduction
7.1 Basic Rules
7.2 Inclusion-Exclusion Principle
7.3 Pigeonhole Principle
Oct 13
Midterm Exam 1: 6:00-7:00 PM in 200 Richards
Chapters 1 through 5, and handouts

7 17 Oct 17
Permutations and combinations
Combinations
7.4 Permutations
7.5 Combinations
Oct 18
OLHW5: Sets, Set Operations, Power Set, Cartesian Product
18 Oct 19
More permutations and combinations
Pascal's Triangle
19 Oct 20
Binomial Theorem
7.6 Binomial Theorem
Oct 21
OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle

8 20 Oct 24
Balls in Bins
7.7 Balls in Bins
21 Oct 26
Counting: Problem Solving Examples
Ch. 6, 7
22 Oct 27
Gem 3: Polymerase Chain Reaction
Oct 28
OLHW7: Permutations and Combinations

9 23 Oct 31
Probability Basics
Expectation and independence
Ch. 8 Introduction
8.1 Definitions and Basic Properties
8.2 (Probability) Examples
24 Nov 02
More Probability Examples
Conditional Probability
Chapter 8
25 Nov 03
More Conditional Probability
Bayes Law
Nov 04
OLHW8: Probability

10 26 Nov 07
Markov Chains
Matrices
Introduction to Graphs
Ch. 13 Introduction
13.1 Simple Graphs
27 Nov 09
Gem 4: Web as graph and Google's PageRank
28 Nov 10
Review for Midterm Exam 2
Chapters 6 through 8
Nov 10
Midterm Exam 2: 6:00-7:30 PM in 200 Richards

11 29 Nov 14
Module 4: Algorithms
Sorting and Searching
9.1 Algorithms for Search
9.2 Analysis of Algorithms
9.3 Algorithms for Sorting
30 Nov 16
Sequences and Sums
Proof by Induction
10.1 Sequences
10.2 Series and Partial Sums
OLHW9: Conditional Probability and Markov Chains
31 Nov 17
More Proofs by Induction
Simple Recurrences
11.1 Specifying Recurrences
11.2 Solving Recurrences

12 32 Nov 21
Growth of Functions
Ch. 12 Growth of Functions
Nov 22
OLHW10: Sorting and Searching
Nov 23
Thanksgiving Break – NO CLASS
Nov 24
Thanksgiving Break – NO CLASS

13 33 Nov 28
Gem 5: The Stable Matching problem
34 Nov 30
Module 5: Networks
Graph Data Structures
13.3 Graph Data Structures
13.4 Graph Problems
35 Dec 01
More Graphs
13.4 Graph Problems
13.5 Graph Theory
Dec 02

14 36 Dec 05
Graph traversals
Handout
WHW4: Graphs and Algorithms
37 Dec 07
Wrapup and review
OLHW11: Graphs
OLHW12: Review (optional)