Last Modified
| Week | Class | Date | Topics | Reading | Due |
|---|---|---|---|---|---|
| 1 | 1 | Sep 09 |
Overview and Course Organization
|
Get online homework account
|
|
| 2 | Sep 10 |
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 14 |
Hexadecimal and Octal Representation
|
1.2 Hexadecimal Representation
1.3 Octal Representation
|
|
| 4 | Sep 16 |
Representing Negative Numbers
Two's Complement
Arithmetic Operations in Binary
|
1.5 Representing Negative Numbers: Two's Complement
|
||
| 5 | Sep 17 |
Basic Logic and Logic Gates
|
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
|
||
| Sep 18 |
OLHW1: Binary, Octal, Hex
|
||||
| 3 | 6 | Sep 21 |
Logic and Logical Equivalence
|
3.1 Truth Values
3.2 Truth Tables
3.3 Logical Equivalence
|
|
| 7 | Sep 23 |
Application: CPU Architecture
|
2.4 Binary Arithmetic: Ripple Carry Adders
|
||
| 8 | Sep 24 |
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 25 |
OLHW2: Logic, Logic Gates
|
||||
| 4 | 9 | Sep 28 |
Modular Arithmetic
Division Algorithm
Powers Modulo n
|
4.5 Modular Arithmetic
4.6 Powers mod n
5.1 Divides
5.3 Division
|
|
| 10 | Sep 30 |
Prime Numbers
Prime Number Decomposition
|
5.2 Primes
|
WHW1: Patterns, Binary Arithmetic
|
|
| 11 | Oct 01 |
GCD, LCM
Euclidean Algorithm
|
5.4 Greatest Common Divisor and Least Common Multiple
5.5 Euclidean Algorithm
|
||
| Oct 02 |
OLHW3: Modular Arithemetic, Linear Encryption
|
||||
| 5 | 12 | Oct 05 |
Application: RSA
|
||
| 13 | Oct 07 |
Module 3: Counting
Password Spaces, Sets
Set Builder Notation
|
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation
6.3 Venn Diagrams
|
||
| Oct 07 |
Exam 1
6-7pm, 201 Mugar
|
Chapters 1 through 4 | |||
| 14 | Oct 08 |
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
|
||
| Oct 09 |
OLHW4: Prime Decomposition, GCD, LCM
|
||||
| 6 |
Oct 12
|
Columbus Day – NO CLASS | |||
| 15 | Oct 14 |
Simple Counting
Product and Sum Rules
|
Ch. 7 Introduction
7.1 Basic Rules
|
||
| 16 | Oct 15 |
Inclusion-Exclusion Principle
Pigeonhole Principle
|
7.2 Inclusion-Exclusion Principle
7.3 Pigeonhole Principle
|
||
| Oct 16 |
OLHW5: Sets, Set Operations, Power Set, Cartesian Product
|
||||
| 7 | 17 | Oct 19 |
Permutations
|
7.4 Permutations
|
|
| 18 | Oct 21 |
Combinations
|
7.5 Combinations
7.7 Balls in Bins
|
||
| 19 | Oct 22 |
Counting: Problem Solving Examples
|
Ch. 6, 7
|
WHW2: Modular Arithmetic, Cryptography
|
|
| Oct 23 |
OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle
|
||||
| 8 | 20 | Oct 26 |
Binomial Theorem
Pascal's Triangle
Sierpinski's Triangle
|
7.6 Binomial Theorem
|
|
| 21 | Oct 28 |
Probability Basics
|
Ch. 8 Introduction
8.1 Definitions and Basic Properties
8.2 (Probability) Examples
|
||
| 22 | Oct 29 |
Probability
|
8.2 (Probability) Examples
|
||
| Oct 30 |
OLHW7: Permutations and Combinations
|
||||
| 9 | 23 | Nov 02 |
Venn Diagrams
Conditional Probability
Bayes Law
|
||
| 24 | Nov 04 |
Markov Chains
|
Handout
|
||
| 25 | Nov 05 |
Application: PageRank
|
Handout
|
||
| Nov 06 |
OLHW8: Probability
|
||||
| 10 | 26 | Nov 09 |
Module 4: Algorithms
Sorting and Searching
|
9.1 Algorithms for Search
|
WHW3: Counting |
|
Nov 11
|
Veterans' Day – NO CLASS | ||||
| 27 | Nov 12 |
Analysis of Sorting and Searching
|
9.2 Analysis of Algorithms
9.3 Algorithms for Sorting
|
||
| Nov 13 | |||||
| 11 | 28 | Nov 16 |
Sequences
|
10.1 Sequences
|
|
| 29 | Nov 18 |
Sums
Proof by Induction
|
10.2 Series and Partial Sums
|
||
| Nov 18 |
Exam 2
6-7pm, 201 Mugar
|
Chapters 5 through 8 | |||
| 30 | Nov 19 |
Recurrences
|
11.1 Specifying Recurrences
|
||
| 12 | 31 | Nov 23 |
More Recurrences
Proof by Induction
|
11.2 Solving Recurrences
|
OLHW9: Conditional Probability, Markov Chains
|
|
Nov 25
|
Thanksgiving Break – NO CLASS | ||||
|
Nov 26
|
Thanksgiving Break – NO CLASS | ||||
| 13 | 32 | Nov 30 |
Growth of Functions
|
Ch. 12 Growth of Functions
|
OLHW10: Searching, Sorting
|
| 33 | Dec 02 |
Module 5: Networks
Graphs
|
Ch. 13 Introduction
13.1 Simple Graphs
13.3 Graph Data Structures
|
||
| 34 | Dec 03 |
More Graphs
|
13.4 Graph Problems
13.5 Graph Theory
|
||
| 14 | 35 | Dec 07 |
Relations
|
Ch. 14 Introduction
14.1 Examples
14.2 Properties of Relations
14.3 Equivalence Relations
|
OLHW11: Summations, Recurrences, Graphs
|
| 36 | Dec 09 |
Application: Modeling with Graphs
|
Handout
|
WHW4: Analysis of Algorithms OLHW12: Review (optional)
|
|