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


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'sParrondo'sEnvelope 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
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