Course page for CS5120 - Probability in Computing
The course will focus on tools from probability and their applications to algorithms.
Topics to be covered:
I: Probability tools,
with algorithmic applications.
II: Data streams
III: Markov chains, random walks, applications to sampling and approximate counting.
1. Probability and Computing by Mitzenmacher and Upfal
2. Randomized Algorithms by Motwani and Raghavan
3. Courses elsewhere with similar or related content:
(i) Randomized Algorithms
by Prof. Surendar Baswana, IIT Kanpur
(ii) Algorithmic Superpower Randomization
by Prof. Bernhard Haeupler
(iii) Algorithms for Big Data
by Chandra Chekuri
(iv) Sublinear and streaming algorithms
by Paul Beame
Division of credit:
Assignments: 10%, Attendance: 10%,
Quizzes: 10%, Exams: 70% (15+15+40)
Minimum is 14 classes and carries 5 marks. Every additional 2 classes carries 1 mark, till a max of 10.