Menu:
Course meets MWF 10:30-11:20 in Olin 217
Drop-In Hours (Olin 202): M 2-3, T 1:30-2:30, W 2:30-3:30, F 1:30-2:30
Probability and Computing book
Diestel's book on Graph Theory
Ullman's Book on Big Data
Homework and in-class activities may be found on Note Bowl.
The videos below are OPTIONAL. Please use as-needed to clarify the reading.
Install Python on your personal computer if you don't have it (select the newest version):
https://www.anaconda.com/download/
Install the editor Atom to write code in Python:
https://atom.io
Recommended Exercises from Probability and Computing:
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
Recommended Exercises from Ullman's book on Big Data:
1.3.2
3.1.3, 3.2.3, 3.3.1, 3.3.3, 3.3.4, 3.3.5, 3.8.1, 3.8.2, 3.8.4
4.3.2, 4.3.3, 4.4.1, 4.5.1, 4.5.2, 4.5.3, 4.5.6, 4.6.1, 4.6.2
8.2.1, 8.3.1, 8.3.3, 8.4.1, 8.4.3
10.1.1, 10.2.1, 10.2.3, 10.3.1, 10.6.1, 10.6.2
7.1.1, 7.1.2, 7.1.3, 11.2.1, 11.2.2
More game theory topics:
Multi-armed bandit
The story of the movie 21
The story of beating the MA state lottery
Non-random lottery numbers
Other topics:
Hypercube Routing, viz
4.5, v1
Matrix multiplication:
Strassen algorithm
Coopersmith-Winograd
Links about streaming computation:
IBM InfoSphere Streams
Kafka Streams
Apache Flume
Apache Spark Streaming
Lambda Architecture for streaming
Kappa Architecture
Streaming Hashing (count min sketch) - solves Distinct Elements problem in Streaming, v1 (watch till 41:00, skipping the integration in the middle)
Streaming SVD, PCA, Dimension Reduction, SVD Example
Final Project Ideas:
Any of the 10 algorithms that dominate our world, e.g. High frequency stock trading
Randomized Data Structures, e.g. skipList, treap
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
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
Mitzenmacher Chapter 9 - information theory
Mitzenmacher Chapter 10 - Markov Chain Monte Carlo
Mitzenmacher Chapter 12 - Martingales
Mitzenmacher Chapter 13 - Universal Hash and Perfect Hash (requires basic number theory)
Game Theory - randomized algorithm for game tree evaluation, beats all known deterministic
Ullman Chapter 5 - Google Page Rank and more advanced versions
Ullman Chapter 6 - Computing Frequent Lists of Items, Market Basket model
Ullman Chapter 7 - Clustering
Ullman Chapter 8 - Web Advertising
Ullman Chapter 9 - Recommender Systems (the Netflix algorithm)
Quantum Computing
Social Network Graph Modeling and the Small World Phenomenon
Extremal Graph Theory
Ullman Chapter 10 - Spectral Graph Theory
Expander Graphs
Nature inspired randomized algorithms:
Ant colony optimization
Evolutionary computing
Simulated Annealing and randomized hill climbers
Drop-In Hours (Olin 202): M 2-3, T 1:30-2:30, W 2:30-3:30, F 1:30-2:30
Probability and Computing book
Diestel's book on Graph Theory
Ullman's Book on Big Data
Homework and in-class activities may be found on Note Bowl.
The videos below are OPTIONAL. Please use as-needed to clarify the reading.
Install Python on your personal computer if you don't have it (select the newest version):
https://www.anaconda.com/download/
Install the editor Atom to write code in Python:
https://atom.io
| Day | Date | Topic |
Reading Due |
Work Due | |
| 1 |
F | Aug 31 |
PolyEquality & Testing AB=C |
If necessary, on Big O, Big Theta: v1, v2, v3 | |
| 2 |
M | Sep 3 |
Probability, Bayes
Theorem, Big O problems |
Syllabus 1.1-1.3 Big O review |
Activities 1 and 2, marked problems |
| 3 |
W | Sep 5 |
Random Var, Expected Value, More Big O |
2.1, video1 video2 |
Activity 3, marked problems |
| 4 |
F | Sep 7 |
Binomial RV |
2.2,v1,v2,v3 Ullman Ch1 |
|
| 5 |
M | Sep 10 | Geometric RV, conditional |
2.3, 2.4 v1,v2, v3,v4 |
|
| 6 |
W | Sep 12 | Variance, Markov |
3.1, 3.2 v1, v2, v3 |
|
| 7 |
F | Sep 14 | Hashing | Ullman 3.1, 3.2, 3.8 | HW 1 (by Saturday at 11:59pm) |
| 8 |
M | Sep 17 | QuickSort QuickSelect |
2.5, v1, v2, v3, v4 |
HW 2 (one prob Tues) |
| 9 |
W | Sep 19 |
Chebyshev, Coupon Collector | MU 3.3, v1, v2, v3, v4 | Quiz 1 - Pr, E[X], big O |
| 10 |
F | Sep 21 | Median |
MU 3.4, v1 |
HW 2 (due Sun night) |
| 11 |
M | Sep 24 | Streaming Sampling Bloom Filters |
Ullman 4.1-4.3 notes, vid MU 8.2 |
Quiz 2 - Rand Algs HW 3 (one prob Tues) |
| 12 |
W | Sep 26 | Birthday Prob Balls into Bins Bucket Sort |
5.1, 5.2 v1, v2 |
For fun: Birthday WC MD5 |
| 13 |
F | Sep 28 |
Moment Generating Functions | MU
4.1, 4.2.1, 4.2.2, v1,
p1, p2 |
HW 3 (due Sun night) |
| 14 |
M | Oct 1 |
Flajolet-Martin Median trick Morris Algorithm |
n1,n2, v1 Ullman 4.4 | Quiz 3 - Var, tail bounds |
| 15 |
W | Oct 3 |
Chernoff bounds | 4.2.3, 4.3, 4.4 v1 |
HW 4 (one prob Thurs) |
| 16 |
F | Oct 5 |
Poisson Hashing |
5.5.1,5.5.2, 5.3,v1,v2,v3 p1, p2 |
|
| 17 |
M | Oct 8 |
CountMinSketch AMS, DGIM, Lp Heavy Hitters |
Ullman 4.5-4.7 n1, MU 10.1 p1,p2,p3, a1 |
|
| M | Oct 8 |
Review Session at night, pizza | Opt: MU 13.4 | Quiz 4 - Chernoff Quiz 5 - Streaming Quiz 6 - Balls & Bins |
|
| T | Oct 9 |
Exam (night) | Bloom tutor | |
|
| 18 |
W | Oct 10 | Bloom Filters Cuckoo Hash Breaking Symm |
5.4-5.5,p1,v1
Handout,
v2
v3,
Opt 13.1 |
|
| 19 |
F | Oct 12 | Go over exam Graph Theory |
Diestel
1.0-1.4 Opt: Bollo I.3 |
HW 4 (at night) |
| 20 |
M | Oct 15 | Graph Connectivity | a1,
Diestel
1.5-1.10, v1 |
HW 5 (one prob Tues) |
| 21 |
W | Oct 17 | Min Cut |
MU 1.4, v1,v2,
v3 |
|
| F | Oct 19 |
Fall break |
|||
| 22 |
M | Oct 22 | Graph recap Graph Coloring |
Diest 5.0-5.3, v0, v1, v2, v3, v4 |
|
| 23 |
W | Oct 24 | Ramsey Theory Friend/stranger slides, aliens |
Bollobas
VI.1 v1, v2, v3, v4, v5, v6 |
HW 5 (at night) |
| 24 |
F | Oct 26 | Probabilistic Method | MU 6.1 | HW 6 (one due Sat) |
| 25 |
M | Oct 29 |
Expectation arg, max cut | MU 6.2 v1, v2, v3 |
|
| 26 |
W | Oct 31 |
Derandomizat- ion, max sat | 6.3, SATvid, derand cut |
HW 6 (at night) |
| 27 |
F | Nov 2 |
Random Graphs Hamiltonians |
Diestel 10.1, 11.1, 11.3 | HW 7 (one due Sat) |
| 28 |
M | Nov 5 |
Hamiltonian cycle alg | MU 5.6, 5.8, v1, v2 | |
| 29 |
W | Nov 7 |
Sample & Modify Simulated Annealing |
MU 6.4, Diestel 11.2 | HW 7 (due at night) |
| 30 |
F | Nov 9 |
Graph thresholds | MU 6.5, 6.6, Diestel 11.4 |
Final Project Proposal |
| 31 |
M | Nov 12 | Lovasz Local Lemma, edge disjoint
paths |
6.7 v1,v2,v3 (6.8, 6.9) |
HW 8 (one due Mon) |
| 32 |
W | Nov 14 | Primality
Test RSA, AKS, Miller-Rabin, Riemann Hyp |
h1, (h2), v0, v1, v2 |
|
| 33 |
F | Nov 16 | No Class |
Optional vid | HW 8 |
| M | Nov 19 |
Thanksgiving break |
|||
| W | Nov 21 | Thanksgiving break |
|||
| F | Nov 23 | Thanksgiving break |
|||
| 34 |
M | Nov 26 | Page Rank |
Ullman 5.1,5.3 | |
| 35 |
W | Nov 28 |
Markov Chains, SAT | 7.1, v1, m1 |
|
| 36 |
F | Nov 30 |
Random Walks on Graphs, Gambler's Ruin | 7.4, v1 |
Final Project Check-in |
| 37 |
M | Dec 3 |
Recurrent vs.
Transient, Stationarity |
7.2, 3SAT, v0, v1 | HW 9: one problem due |
| T |
Dec 4 |
Exam 2 |
|||
| 38 |
W | Dec 5 |
Simpson's, Parrondo's, Envelope Paradoxes |
7.3, v1, v2 7.5, v3 Parrondo |
|
| 39 |
F | Dec 7 |
Game Theory, minimax, St. Petersburg |
Handout MR 2.1-2.2 |
Final Check-in 2 |
| 40 |
M | Dec 10 | Benford's Law, Quantum Comp, Shor's Algorithm |
Handout 1, Handout 2 |
HW 9 (due Sun night) |
| 41 |
W | Dec 12 | Bitcoin Ito Calculus |
vid, handout |
|
| 42 |
F | Dec 14 | Sorting Networks Netflix Algorithm |
Handout 1, Ullman 3.5 & chapter 9 |
Final Paper due Dec 19 |
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
Recommended Exercises from Ullman's book on Big Data:
1.3.2
3.1.3, 3.2.3, 3.3.1, 3.3.3, 3.3.4, 3.3.5, 3.8.1, 3.8.2, 3.8.4
4.3.2, 4.3.3, 4.4.1, 4.5.1, 4.5.2, 4.5.3, 4.5.6, 4.6.1, 4.6.2
8.2.1, 8.3.1, 8.3.3, 8.4.1, 8.4.3
10.1.1, 10.2.1, 10.2.3, 10.3.1, 10.6.1, 10.6.2
7.1.1, 7.1.2, 7.1.3, 11.2.1, 11.2.2
More game theory topics:
Multi-armed bandit
The story of the movie 21
The story of beating the MA state lottery
Non-random lottery numbers
Other topics:
Hypercube Routing, viz
4.5, v1
Matrix multiplication:
Strassen algorithm
Coopersmith-Winograd
Links about streaming computation:
IBM InfoSphere Streams
Kafka Streams
Apache Flume
Apache Spark Streaming
Lambda Architecture for streaming
Kappa Architecture
Streaming Hashing (count min sketch) - solves Distinct Elements problem in Streaming, v1 (watch till 41:00, skipping the integration in the middle)
Streaming SVD, PCA, Dimension Reduction, SVD Example
Final Project Ideas:
Any of the 10 algorithms that dominate our world, e.g. High frequency stock trading
Randomized Data Structures, e.g. skipList, treap
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
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
Mitzenmacher Chapter 9 - information theory
Mitzenmacher Chapter 10 - Markov Chain Monte Carlo
Mitzenmacher Chapter 12 - Martingales
Mitzenmacher Chapter 13 - Universal Hash and Perfect Hash (requires basic number theory)
Game Theory - randomized algorithm for game tree evaluation, beats all known deterministic
Ullman Chapter 5 - Google Page Rank and more advanced versions
Ullman Chapter 6 - Computing Frequent Lists of Items, Market Basket model
Ullman Chapter 7 - Clustering
Ullman Chapter 8 - Web Advertising
Ullman Chapter 9 - Recommender Systems (the Netflix algorithm)
Quantum Computing
Social Network Graph Modeling and the Small World Phenomenon
Extremal Graph Theory
Ullman Chapter 10 - Spectral Graph Theory
Expander Graphs
Nature inspired randomized algorithms:
Ant colony optimization
Evolutionary computing
Simulated Annealing and randomized hill climbers