Last Modified
| 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 |
Hexadecimal and Octal Representation
Wrap up of Binary Arithmetic Operations
Basic Logic and Logic Gates
|
1.2 Hexadecimal Representation
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
Password Spaces, Sets
|
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
|
||||