Discrete Structures Schedule
CS 1800 Fall 2013

Last Updated:

Week Class Date Topics Reading Due
1 1 Sep 04
Overview and Course Organization
Get online homework account
2 Sep 05
Module 1: Computers and Computing
Binary Representation of Numbers
Converting Between Binary and Decimal
Ch. 1 Introduction
1.1 Binary Representation
1.2 Bytes
1.5 Converting Between Decimal and Binary

2 3 Sep 09
Representing Negative Numbers
Two's Complement
1.4 Octal Representation
1.6 Representing Negative Numbers: Two's Complement
4 Sep 11
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 12
Logic Gates and Logic, contd.
2.3 More Logic Gates: NAND, NOR, XOR, XNOR
3.1 Truth Values
3.2 Truth Tables
Sep 13
OLHW1: Binary, Octal, Hex

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

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

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

6 15 Oct 07
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 09
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
OLHW5: Sets, Set Operations, Power Set, Cartesian Product
Oct 10
Review for Midterm Exam 1
Chapters 1 through 5, and handouts
Midterm Exam 1: 6:00-7:00 PM in 200 Richards

7
Oct 14
Columbus Day – NO CLASS
17 Oct 16
Permutations and combinations
Combinations
7.4 Permutations
7.5 Combinations
18 Oct 17
More permutations and combinations
Pascal's Triangle
Oct 18
OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle

8 19 Oct 21
Binomial Theorem
7.6 Binomial Theorem
20 Oct 23
Balls in Bins
7.7 Balls in Bins
21 Oct 24
Counting: Problem Solving Examples
Ch. 6, 7
Oct 25
OLHW7: Permutations and Combinations

9 22 Oct 28
Probability Basics
Expectation and independence
Ch. 8 Introduction
8.1 Definitions and Basic Properties
8.2 (Probability) Examples
23 Oct 30
More Probability Examples
24 Oct 31
Conditional Probability
Bayes Law
8.3 Conditional Probability and Bayes Theorem
Nov 01
OLHW8: Probability

10 25 Nov 04
Module 4: Algorithms
Algorithms for Searching
9.1 Algorithms for Search
9.2 Analysis of Algorithms
26 Nov 06
Algorithms for Sorting
9.3 Algorithms for Sorting
27 Nov 07
Review for Midterm Exam 2
Chapters 6 through 8
Midterm Exam 2: 6:00-7:30 PM in 200 Richards

11
Nov 11
Veteran's Day – NO CLASS
28 Nov 13
Sequences
10.1 Sequences
29 Nov 14
Sums
Proof by Induction
10.2 Series and Partial Sums
Nov 15
OLHW9: Conditional Probability and Markov Chains

12 30 Nov 18
More Proofs by Induction
11.1 Specifying Recurrences
31 Nov 20
Simple Recurrences
11.2 Solving Recurrences
WHW3: Probability, Counting, and Algorithms
32 Nov 21
Growth of Functions
Ch. 12 Growth of Functions
Nov 22
OLHW10: Sorting and Searching

13 33 Nov 25
Module 5: Networks
Graph Data Structures
13.3 Graph Data Structures
13.4 Graph Problems
Nov 27
Thanksgiving Break – NO CLASS
Nov 28
Thanksgiving Break – NO CLASS

14 34 Dec 02
More Graphs
Graph traversals
13.4 Graph Problems
13.5 Graph Theory
35 Dec 04
Wrapup and review
WHW4: Graphs and Algorithms
Dec 06
OLHW11: Graphs
OLHW12: Review (optional - no credit)
Final Exam Friday December 13, 10:30am-12:30pm
(West Village F 020 for both Prof. Fell's sections, Shilman 305 for Prof. Vona's section)