Probability for Computing

[Probability and Algorithms] [Mathematics for CS]

[Prob. Models and Algorithms for Internet applications]


This is the second big course (or a collection of smaller ones) that I have been building, getting stuck with for a long time (the other is on areas of Security and Applied Cryptography). I hope I will be proud of this effort.


In an ideal world, I would name it “Probability for Computing” [a bit too ambitious, I have created/collected material enough for 90 hour-length but still omitted several important areas]. In the real world there is no such class. Instead, I cover the main core and then select advanced material with proper customization for 3 different classes: Mathematics for CS (Toan Chuyen de), Probability and Algorithms, and Probabilistic Models and Algorithms for the Internet. The main core is to cover basic probability topics with application in basic CS areas (such as analyzing the random behavior of the Quick Sort algorithm, understanding Birthday paradox and its importance in implementing Digital signatures). There are many different approaches to go from here. The suggested best reference (Probability and Computing) chooses to go cover more classical areas in Computing that use probabilistic models.


Typical advanced topics that I choose to cover in the class “Probabilistic Models and Algorithms for the Internet”:

-        Probabilistic Data Structure (Bloom Filter) and methods to detect and mitigate DDoS attack

-        Markov Models, Random walk and Google’s PageRank

-        Distributed Hash Tables and structured peer-to-peer networks for content sharing

-        Random network,  models of real-world large-scale networks (such as social networks), and routing algorithms


I believe that the material covered in this (set of) course and the accessibility that I try to make happen will be a valuable platform for students seeking postgraduate program abroad, especially ones who want to become a good researcher.



o   Probability and Computing – Randomized Algorithms and Probabilistic Analysis (Mitzenmacher and Upfal)

o   Chapter 5, Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein), 2nd

o   A first course in probability (Sheldon Ross), 5ed [if you need to quickly review basic probability knowledge that has been taught to you in the first year course “Probability and Statistics”]


[In the past E-books versions of these could be found @, now they might be floating around at various download sites]


Lecture 1: Introduction, quick review of basic probability, examples

Lecture 2: Sample space and events, probabilistic analysis 

Lecture 3: Axioms, conditional probability, random variables, distributions

Lecture 4: Conditional probability, applications, geometric distribution

Lecture 5: More applications with probabilistic analysis, balls and bins

Lecture 6: Balls and bins, Bloom filters and applications for discovering TCP SYN FLOOD attack

Lecture 7: Continous distributions, poison process and applications

Lecture 8: Central limit theorems

Lecture 9 – Borrowed material:        

a) Markov Model and application: Page rank and its use in Google SE

                        b) Random walk and application

Lecture 10:     Borrowed material:

a)     Unstructured P2P networks

b)     Distributed Hash Tables (DHT) and Structured P2P networks

Lecture 11:     Random graphs, Random network models and application in various areas: modeling real-world large-scale networks, network designs [For future, 2014 possibly]

Lecture 12:    Collaborative Filter and Recommender Systems [2015 possibly]

Lecture 13:    Hiden Markov Chains and application in Software Model Checking [2016 possibly]


Past Material: Further reading on applications (collected from the Internet and other sources) – collected by 2010

An application with Coupon Collector Problem:  Practical Network Support for IP Traceback (a student presentation, not the original paper)

An application with Bloom filters: DdoS attack with TCP SYN flooding (another student review work)

An application with randomized algorithms: Zero Knowledge Proofs (examples: identification protocol without revealing any information to the verifier)

An application with distributed hashing: Distributed Hash Tables (for and Peer-to-Peer strutural architectures)

An application with hash collisions: MicroMint (A electronic micro-payment systems: how to pay small amount such as a cent or even milicents)

An application with randomized algorithm (in a kind of random graph): Small-World Phenomenal: An Algorithmic Perspective