Menu:
Drop In Hours: M 2:20-3:20, W 11:20-12:20, F 12:20-1:20 in
Olin 202
Diestel's book on Graph Theory
Ullman Book on Big Data
Homework and in-class activities may be found in the Shared Drive.
Recommended Exercises:
Chapter 1: 1-6, 9-10, 12-13, 15-17, 21-23, 26
Chapter 2: 1, 2, 5-9, 12-18, 22-25, 31-32
Chapter 3: 1-3, 6-8, 11-12, 16-18, 22-24
Chapter 4: 1-6, 9-10, 17-18, 21-25
Chapter 5: 2-9, 11-13, 16-18, 21-26
Chapter 6: 1-10, 13-16, 18
Chapter 7: 1-3, 5-8, 10-11, 15, 17, 20, 22-24, 26-27
Final Project Ideas:
Fingerprinting, number theory, pattern matching in strings mimicking Section 1.3
Survey streaming algorithms that work via sampling, mimicking Section 3.4
Survey oblivious algorithms, as in Sections 4.4-4.5
More kinds of Hashing, e.g. Cuckoo Hashing - v1, v2, v3, v4, v5
Streaming Hashing (count min sketch) - solves Distinct Elements problem in Streaming, v1 (watch till 41:00, skipping the integration in the middle)
Big Data - summarize the main algorithms
Primality Testing (requires some number theory)
Lower bounds on streaming algorithms: video
Ramsey theory for hypergraphs
Ramsey theory for general monochromatic subgraphs H (not just complete Kn graphs)
Further applications of the probabilistic method, e.g. sorting networks, Dr. Ludwig's knot mosaics
Chapter 9 - information theory
Chapter 10 - Markov Chain Monte Carlo
Chapter 12 - Martingales
Chapter 13 - Universal Hash Families and Perfect Hash Functions (requires basic number theory)
Game Theory - randomized algorithm for game tree evaluation, beats all known deterministic
Google Page Rank and more advanced versions - see Chapter 5 of Ullman
Computing Frequent Lists of Items, Market Basket model - see Chapter 6 of Ullman
Clustering - see Chapter 7 of Ullman
Web Advertising - see Chapter 8 of Ullman
Recommender Systems (the Netflix algorithm) - chapter 9 of Ullman
Quantum Computing
Social Network Graph Modeling and the Small World Phenomenon
Extremal Graph Theory
Spectral Graph Theory (requires linear algebra)
Expander Graphs
Diestel's book on Graph Theory
Ullman Book on Big Data
Homework and in-class activities may be found in the Shared Drive.
| Day | Date | Topic |
Reading Due |
Work Due | |
| F | Sep 2 | PolyEquality & Testing AB=C |
|||
| 1 | M | Sep 5 | Probability, Bayes Theorem |
Syllabus 1.1-1.3 |
|
| W | Sep 7 | Random Var, Expected Value |
2.1, video1 video2 |
||
| F | Sep 9 | Binomial RV |
2.2, video1 v2, v3 |
If necessary - videos on Big O, Big Theta: v1, v2, v3 |
|
| 2 | M | Sep 12 | Geometric RV, conditional |
2.3, 2.4 v1,v2, v3,v4 |
|
| W | Sep 14 | Variance, Markov |
3.1, 3.2 v1, v2, v3 |
||
| F | Sep 16 | QuickSort QuickSelect |
2.5, v1, v2, v3, v4, v5 |
HW 1 |
|
| 3 | M | Sep 19 | Chebyshev, Coupon Collector |
3.3, v1, v2, v3, v4 |
|
| W | Sep 21 | Moment Generating Functions |
4.1,4.2.1,v1 |
Examples 2 & 3 on Activity 11, v2 (12-35 theory, 35-45 example) |
|
| F | Sep 23 | Streaming Algs, Median |
3.4 |
HW 2 Activity 12a |
|
| 4 | M | Sep 26 | Chernoff bounds |
4.2, 4.3 v1, v2 |
|
| W | Sep 28 | Graph Theory |
Diestel 1.1-1.3 MU 4.4,v1,v2 |
Quiz 1 - Pr and E[X] Reading Notes |
|
| F | Sep 30 | Hypercube Routing, viz |
4.5, v1 Reading Notes |
HW 3 Quiz 2 - Rand Algs |
|
| 5 | M | Oct 3 | Graph Connectivity |
Diestel 1.4-1.7, 1.10 |
HW 4: one problem due Tuesday |
| W | Oct 5 | Min Cut |
MU 1.4 |
Quiz 3 - Tail bounds | |
| F | Oct 7 | Birthday Prob Balls into Bins Bucket Sort |
5.1, 5.2 Birthday WC MD5, v1, v2 |
HW 4 Quiz 4 - graphs |
|
| 6 | M | Oct 10 | Review Day Exam (night) |
5.3, video, video2 |
|
| W | Oct 12 | Poisson |
5.4, video |
HW 5: one problem due Thursday |
|
| F | Oct 14 | Go over exam Hashing Bloom Filters |
5.5, v1, v2 |
Optional: v3 Bloom tutorial |
|
| 7 | M | Oct 17 | Random Graphs Hamiltonians |
5.6, 5.8, v1, v2, v3 |
HW 5 Applet |
| W | Oct 19 | Graph Coloring, BloomVideo |
Diestel 5.1-5.3, 10.1, v1 |
Optional: D 10.2-10.3 LoadBal (2-13:00) HashProbe(38-48) |
|
| F | Oct 21 | Fall break |
Optional: Bollobas I.3 |
||
| 8 | M | Oct 24 | Streaming: Approximate Counting |
Ullman4.1-4.3, notes,MU8.2, vid (till 45:00) | HW 6: one problem due Tuesday. Quiz 5 |
| W | Oct 26 |
Coloring, Random Graphs Friend/stranger |
Bollobas V.1 & V.2 & VII.1, v1, v2, v3, v4 | ||
| F | Oct 28 | Ramsey Theory Quiz6: MU ch5 |
Bollobas VI.1, v1, v2, v3, v4, v5, v6 |
Optional: Diestel 9.1, Bollobas VI.2-VI.4 | |
| 9 | M | Oct 31 | Streaming: Distinct Elts |
notes, notes, Ullman 4.4-4.6 v1 (till 41:00) |
HW 6: due Tuesday Optional: Ullman 10.1 |
| W | Nov 2 | Cuckoo Hash, Count Min Sketch |
Handout, v1 (38:30-58:00), notes |
HW 7: one problem due Thursday Optional: Ullman 7.6 |
|
| F | Nov 4 | Probabilistic Method, max cut | Diestel 11.1 MU 6.1, 6.2 v1, v2. |
Quiz 7: graphs, streams Optional: Graph th'y vid (21:00-36:00) |
|
| 10 | M | Nov 7 | Derandomizat- ion, max sat | 6.3, SATvid, derand cut |
HW 7: due Tuesday |
| W | Nov 9 | Sample & Modify graph threshold |
6.4-6.5 v1 (10-52:00) |
HW 8: one problem due Thursday | |
| F | Nov 11 | Second moment method, almost all graphs |
Diestel 11.2-11.4, v1 |
Quiz 8 & 9: Hashing Optional: Bollobas VII.2-VII.5 |
|
| 11 | M | Nov 14 | Lovasz Local Lemma, edge disjoint paths |
6.6, 6.7 vid (0-13:00, 43:00-54:00) |
HW 8: due Tuesday Quiz 10: MU 6.1-6.3 |
| W | Nov 16 | Review Day Primality Test |
6.8, handout vid (till 8:00) |
vidLLL, vidLLLGeneral (till 15:00) |
|
| F | Nov 18 | RSA, AKS, Miller-Rabin, Riemann Hyp | 6.9, v1, v2: Miller-Rabin |
Final Project Proposal Quiz 11: MU ch6 Optional vid |
|
| 12 | M | Nov 21 | Thanksgiving break |
||
| W | Nov 23 | Thanksgiving break |
|||
| F | Nov 25 | Thanksgiving break |
|||
| 13 | M | Nov 28 | Markov Chains, SAT |
7.1, 3SATvid, RWvid | Optional: exampleVid |
| W | Nov 30 | Recurrent vs. Transient, Gambler's Ruin |
7.2, 3SAT, DefnVid, Defn2 |
Exam 2 on Thursday night (December 1) |
|
| F | Dec 2 | Random Walks on Graphs, Polya's Theorem | 7.4, vid till 13, Ullman 5.1,5.3 |
HW 9: one problem due Sunday Optional: Bol IX.1-IX.3 |
|
| 14 | M | Dec 5 | Parrondo's Paradox |
7.5, vid (esp. 23:00-38:00) |
|
| W | Dec 7 | Stationary Distributions |
7.3,vid,vid2, | HW 9: due Thursday | |
| F | Dec 9 |
Game Theory, minimax |
Handout | Quiz 12: MU ch7 HW 10: one problem due Sunday |
|
| 15 | M | Dec 12 | Final project presentations |
Eigenvectors | Optional: Ullman8.1-8.3 HW 10: due Tuesday |
| W | Dec 14 | Final project presentations |
SVD Example | ||
| F | Dec 16 | Streaming SVD, PCA, Dimension Reduction, Randomized Data Structures | Handout, Ullman 9.4, 11.1-11.3, skipList, treap |
Final Paper due Wednesday, Dec 21 Optional: Ullman 11.4 |
Chapter 1: 1-6, 9-10, 12-13, 15-17, 21-23, 26
Chapter 2: 1, 2, 5-9, 12-18, 22-25, 31-32
Chapter 3: 1-3, 6-8, 11-12, 16-18, 22-24
Chapter 4: 1-6, 9-10, 17-18, 21-25
Chapter 5: 2-9, 11-13, 16-18, 21-26
Chapter 6: 1-10, 13-16, 18
Chapter 7: 1-3, 5-8, 10-11, 15, 17, 20, 22-24, 26-27
Final Project Ideas:
Fingerprinting, number theory, pattern matching in strings mimicking Section 1.3
Survey streaming algorithms that work via sampling, mimicking Section 3.4
Survey oblivious algorithms, as in Sections 4.4-4.5
More kinds of Hashing, e.g. Cuckoo Hashing - v1, v2, v3, v4, v5
Streaming Hashing (count min sketch) - solves Distinct Elements problem in Streaming, v1 (watch till 41:00, skipping the integration in the middle)
Big Data - summarize the main algorithms
Primality Testing (requires some number theory)
Lower bounds on streaming algorithms: video
Ramsey theory for hypergraphs
Ramsey theory for general monochromatic subgraphs H (not just complete Kn graphs)
Further applications of the probabilistic method, e.g. sorting networks, Dr. Ludwig's knot mosaics
Chapter 9 - information theory
Chapter 10 - Markov Chain Monte Carlo
Chapter 12 - Martingales
Chapter 13 - Universal Hash Families and Perfect Hash Functions (requires basic number theory)
Game Theory - randomized algorithm for game tree evaluation, beats all known deterministic
Google Page Rank and more advanced versions - see Chapter 5 of Ullman
Computing Frequent Lists of Items, Market Basket model - see Chapter 6 of Ullman
Clustering - see Chapter 7 of Ullman
Web Advertising - see Chapter 8 of Ullman
Recommender Systems (the Netflix algorithm) - chapter 9 of Ullman
Quantum Computing
Social Network Graph Modeling and the Small World Phenomenon
Extremal Graph Theory
Spectral Graph Theory (requires linear algebra)
Expander Graphs