Last Modified
| Date | Topics | Reading | Exercises | ||
|---|---|---|---|---|---|
| Mon Jan 7 |
Overview and Course Organization
|
||||
| Wed Jan 9 |
Module 1: Computers and Computing
Binary Representation of Numbers
Converting Between Binary and Decimal
|
Ch. 1 Introduction
1.1 Binary Representation
1.5 Converting Between Decimal and Binary
|
Book: Chapter 1 Exercises
OLHW1: Binary, Octal, Hex
|
||
| Thu Jan 10 |
Representing Negative Numbers
Two's Complement
|
1.2 Bytes
1.3 Hexadecimal Representation
1.4 Octal Representation
1.6 Representing Negative Numbers: Two's Complement
|
|||
| Mon Jan 14 |
Wrap-up of Number Representations
Logic Gates and Circuits
|
Ch. 2 Introduction
2.2 Basic Logic Gates: AND, OR, NOT
2.3 More Logic Gates: NAND, NOR, XOR, XNOR
|
Book: Chapter 2 Exercises
Book: Chapter 3 Exercises
OLHW2: Logic, Logic Gates
|
||
| Wed Jan 16 |
Logical Completeness
Logic Gates and Circuits, contd.
|
2.4 Binary Arithmetic: Ripple Carry Adders
|
|||
| Thu Jan 17 |
Logic and Logical Equivalence
|
Ch. 3 Introduction
3.1 Truth Values
3.2 Truth Tables
3.3 Logical Equivalence
|
|||
|
Mon Jan 21
|
Martin Luther King Jr.'s Birthday observed, no classes | ||||
| Wed Jan 23 |
Laws of Logical Equivalence
Logic Wrap-up
Module 2: Cryptography
Shift Ciphers
|
Ch. 4 Introduction
4.1 Simple Shift Ciphers
4.2 Encoding
4.3 The mod Function
|
Book: Chapter 4 Exercises
OLHW3: Modular Arithmetic, Linear Encryption
|
||
| Thu Jan 24 |
Simple Substitution Ciphers
Modular Arithmetic
|
4.4 Simple Substitution Ciphers
4.5 Modular Arithmetic
|
|||
| Mon Jan 28 |
Powers Modulo n
Prime Numbers
Prime Number Decomposition
|
4.6 Powers mod n
5.1 Divides
5.2 Primes
5.3 Division
|
Book: Chapter 5 Exercises
OLHW4: Prime Decomposition, GCD, LCM
|
||
| Wed Jan 30 |
GCD, LCM
Euclidean Algorithm
Extended Euclidean Algorithm
|
5.4 Greatest Common Divisor and Least Common Multiple
5.5 Euclidean Algorithm
5.6 Extended Euclidean Algorithm
|
|||
| Thu Jan 31 |
Multiplicative Inverse
Linear Ciphers
Public-Key Cryptography
|
||||
| Mon Feb 4 |
Review for Test 1
|
Chapters 1 to 5
|
|||
| Wed Feb 6 |
Test 1
|
||||
| Thu Feb 7 |
Module 3: Combinatorics
Sets
|
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation
6.3 Venn Diagrams
6.4.1-6.4.5 Set Operations
|
|||
| Mon Feb 11 |
Sets (Continued)
|
6.4.6 Power Set
6.4.7 Cartesian Product
6.5 Computer Representation of Sets
|
Book: Chapter 6 Exercises
OLHW5: Sets, Set Operations, Power Set, Cartesian Product
|
||
| Wed Feb 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
|
|||
| Thu Feb 14 |
Permutations
Combinations
|
7.4 Permutations
7.5 Combinations
|
|||
|
Mon Feb 18
|
Presidents' Day, no classes | ||||
| Wed Feb 20 |
Pascal's Triangle
Binomial Theorem
Balls in Bins
|
7.6 Binomial Theorem
7.7 Balls in Bins
|
Book: Chapter 7 Exercises
OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle
OLHW7: Permutations and Combinations
|
||
| Thu Feb 21 |
Probability Basics
Division of Stakes
|
Ch. 8 Introduction
8.1 Definitions and Basic Properties
8.2 (Probability) Examples
|
|||
| Mon Feb 25 |
More Probability Basics
Conditional Probability
|
8.3 Conditional Probability and Bayes Theorem
|
Book: Chapter 8 Exercises
OLHW8: Probability
OLHW9: Conditional Probability
|
||
| Wed Feb 27 |
Bayes Theorem
Monty Hall Problem
|
||||
| Thu Feb 28 |
Pancakes Problem
Puppies Problem ("Two Boys")
|
||||
|
Mon Mar 4
|
Spring Break – NO CLASS | ||||
|
Wed Mar 6
|
Spring Break – NO CLASS | ||||
|
Thu Mar 7
|
Spring Break – NO CLASS | ||||
| Mon Mar 11 |
Expectation
|
||||
| Wed Mar 13 |
Review for Test 2
|
Chapters 6 to 8
|
|||
| Thu Mar 14 |
Test 2
|
||||
| Mon Mar 18 |
Module 4: Algorithmic Analysis
Searching and Analysis
|
9.1 Algorithms for Search
9.2 Analysis of Algorithms
|
Book: Chapter 9 Exercises
OLHW10: Sorting and Searching
|
||
| Wed Mar 20 |
Sorting
|
9.3 Algorithms for Sorting
|
|||
| Thu Mar 21 |
Sequences
|
10.1 Sequences
|
|||
| Mon Mar 25 |
Sums
|
10.2 Series and Partial Sums
|
Book: Chapter 10 Exercises
Book: Chapter 11 Exercises
OLHW11: Sequences and Summations
|
||
| Wed Mar 27 |
Recurrences
Proof by Induction
|
11.1 Specifying Recurrences
11.2 Solving Recurrences
|
|||
| Thu Mar 28 |
Sorting Analysis
Growth of Functions
|
Ch. 12 Growth of Functions
|
|||
| Mon Apr 1 |
Module 5: Networks
Graphs
|
Ch. 13 Introduction
13.1 Simple Graphs
13.3 Graph Data Structures
|
Book: Chapter 13 Exercises
OLHW12: Graphs
|
||
| Wed Apr 3 |
Graph Problems
|
13.4 Graph Problems
|
|||
| Thu Apr 4 |
More Graphs
|
13.4 Graph Problems
13.5 Graph Theory
|
|||
| Mon Apr 8 |
Module 6: Relations
Relations
|
Ch. 14 Introduction
14.1 Examples
14.2 Properties of Relations
14.3 Equivalence Relations
|
|||
| Wed Apr 10 |
Review for Test 3
|
Chapters 9 to 14
|
|||
| Thu Apr 11 |
Test 3
|
||||
|
Mon Apr 15
|
Patriots' Day, no exams or classes | ||||
| Wed Apr 17 |
Wrap-up and review
|
Chapters 1 to 14
|
OLHW13: Review
|
||
| Tue Apr 23 |
FINAL EXAM
|
||||