| 1 |
1/3
|
1/4
Introduction:
Basic counting rules
Sum Rule, Inclusion/Exclusion, Product rule, Power rule, Permutations (Rosen 8.5, 6.1, 6.3)
|
1/5
|
1/6
Counting continued:
Combinations
Symmetries
Binomial Coefficients (Rosen 6.3, 6.4)
|
1/7
(HW0 due)
|
1/8 |
1/9
|
| 2 |
1/10
|
1/11
Probability
Distributions and conditional probability
|
1/12
|
1/13
Probability
Random Variables and expected value
|
1/14
HW1 due
(counting)
|
1/15
|
1/16
|
| 3 |
1/17
Martin Luther King Jr. Holiday
|
1/18
Algorithms:
sorting and searching
|
1/19
test 1 (counting)
|
1/20
Algorithms:
Order notation/Time analysis
|
1/21
HW2 due
(probability)
|
1/22
|
1/23 |
| 4 |
1/24
|
1/25
Algorithms:
Loop invariants
|
1/26
|
1/27
Algorithms:
Recursive algorithms
|
1/28
HW3 due (sorting and order notation)
|
1/29
|
1/30
|
| 5 |
1/31
|
2/1
Algorithm:
Divide and conquer/Master theorem
|
2/2
|
2/3
Recursive Counting
|
2/4
HW4 due
(algorithm analysis)
|
2/5 |
2/6 |
| 6 |
2/7
|
2/8
Recursive counting
|
2/9
|
2/10
Midterm
(counting and probability and order notation)
|
2/11
(no homework)
|
2/12 |
2/13 |
| 7 |
2/14
|
2/15
Graph:
Graphs and graphsearch (Rosen 10.1, 10.2)
Modeling problems as graphs (Rosen 10.3, 10.4
|
2/16
|
2/17
Graph:
Eulerian and Hamiltonian paths (Rosen 10.5)
|
2/18
HW 5 recursive counting
|
2/19 |
2/20 |
| 8 |
2/21
Presidents' Day Holiday
|
2/22
Special graphs:
Trees and DAGs (Rosen 10.5 )
|
2/23
|
2/24
Intro Encoding
Fixed-length
Variable length: Huffman (Rosen 11.2)
|
2/25
HW6
graphs
|
2/26 |
2/27 |
| 9 |
2/28
|
3/1
Coding continued:
Ranking and Unranking (Rosen 11.2)
|
3/2
(probability test)
|
3/3
Randomized Algorithms (finding duplicates through hashing)
|
3/4
HW7 encoding
|
3/5 |
3/6 |
| 10 |
3/7
|
3/8
Variance/Concentration and application.
Monte Carlo methods
|
3/9
|
3/10
Review
|
3/11
|
3/12 |
3/13 |
| Finals |
3/14
|
3/15
Final Exam:
11:30am-2:29pm
|
3/16
|
3/17
|
3/18 |
3/19 |
3/20 |