CS1800 Discrete Structures: Spring 2011 Schedule

Instructor Scott Roche

Set Operations
Computer Representation of Sets
Week Class Date Topics Reading Due
1 1 Jan 10
Overview and Course Organization
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
Arithmetic Operations in Binary
1.3 Octal Representation

2
Jan 17
Martin Luther King Day – NO CLASS
4 Jan 19
Representing Negative Numbers
Two's Complement
1.5 Representing Negative Numbers: Two's Complement
5 Jan 20
Logic Gates and Circuits
Chs. 2, 3 Introductions
2.1 Transistors and Switches
2.2 Basic Logic Gates: AND, OR, NOT
2.3 More Logic Gates: NAND, NOR, XOR, XNOR
OLHW1:Integer Representations DUE JAN 21 9 p.m.

3 6 Jan 24
Logic and Logical Equivalence
3.1 Truth Values
3.2 Truth Tables
3.3 Logical Equivalence
7 Jan 26
Disjunctive Normal Form
8 Jan 27
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:Circuits and Logic DUE JAN 28 9 p.m.

4 9 Jan 31
Modular Arithmetic
Division Algorithm
Powers Modulo n
4.5 Modular Arithmetic
4.6 Powers mod n
5.1 Divides
5.3 Division
Practice Session Tuesday 1 Feb, 5:30 p.m. 335 Shillman Hall
10 Feb 2
Prime Numbers
Prime Number Decomposition
5.2 Primes
11 Feb 3
GCD, LCM
Euclidean Algorithm
Application: RSA
5.4 Greatest Common Divisor and Least Common Multiple
5.5 Euclidean Algorithm

5 12 Feb 7
Module 3: Counting
Set Builder Notation
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation
6.3 Venn Diagrams
OLHW 3 DUE 9 p.m. / Exam Review Session 5:30 p.m. 335 Shillman Hall
12 Feb 9
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
13 Feb 10
EXAM 1

6 Feb 14
15 Feb 16
Simple Counting
Product and Sum Rules
Ch. 7 Introduction
7.1 Basic Rules
16 Feb 17
Inclusion-Exclusion Principle
Pigeonhole Principle
7.2 Inclusion-Exclusion Principle
7.3 Pigeonhole Principle

7 17 Feb 21
Balls in Bins
Counting: Problem Solving Examples
7.4 Permutations
7.5 Combinations
7.7 Balls in Bins
OLHW 5 DUE 9 p.m.
18 Feb 23
Counting: Problem Solving Examples
Binomial Theorem
Pascal's Triangle
7.6 Binomial Theorem
Feb 24
Catch-up Day
OLHW 6 DUE 9 P.M. Friday, March 11

Spring Break!!!! WOOOOO!!! – NO CLASS

8 19 Mar 7
Probability Basics
Ch. 8 Introduction
8.1 Definitions and Basic Properties
8.2 (Probability) Examples
20 Mar 9
Probability
21 Mar 10
Venn Diagrams
Conditional Probability
Bayes Law

9 22 Mar 14
Conditional Probability
Bayes Law
23 Mar 16
Markov Chains
24 Mar 17
Markov Chains
Application: PageRank

10 25 Mar 21
Review
OLHW 8 Due Tuesday at 9 p.m.
26 Mar 23
Module 4: Algorithms
Sorting and Searching
9.1 Algorithms for Search
27 Mar 24
Analysis of Sorting and Searching
9.2 Analysis of Algorithms
9.3 Algorithms for Sorting
OLHW 4 Due 9 p.m., OLHW 9 due Friday 9 p.m.

11 28 Mar 28
Exam 2
29 Mar 30
Sequences
10.1 Sequences
30 Mar 31
Sums
Proof by Induction
10.2 Series and Partial Sums

12 31 Apr 4
Recurrences
11.1 Specifying Recurrences
32 Apr 6
More Recurrences
Proof by Induction
11.2 Solving Recurrences
33 Apr 7
Growth of Functions
Ch. 12 Growth of Functions
OLHW 10 Due 9 p.m.

13 34 Apr 11
Module 5: Networks
Graphs
Ch. 13 Introduction
13.1 Simple Graphs
13.3 Graph Data Structures
35 Apr 13
More Graphs
13.4 Graph Problems
13.5 Graph Theory
36 Apr 14
Relations
Ch. 14 Introduction
14.1 Examples
14.2 Properties of Relations
14.3 Equivalence Relations

14
Apr 18
Patriots' Day – NO CLASS
37 Apr 21
(optional) Review