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.
References:
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 @ library.nu, 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:
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