Algorithms are required to be “correct” and “fast”. In a wide variety of applications, these twin objectives are in conflict with each other. Fortunately,neither of these ideals are sacrosanct. Therefore we can often try to optimize one of these goals by incurring a small penalty on the other. This takes us to the field of Randomized Algorithms. Often, the randomized variants, in addition to being faster than their deterministic counterpart, are simpler to understand and implement. In this course, we will study this tradeoff between correctness and speed. We will be learning a number of methods to design and analyze randomized algorithms.
INTENDED AUDIENCE: Senior UG students, PG students and Ph.D candidates interested in computer science, combinatorics, etc.
CORE/ELECTIVE: Elective
UG/PG: UG/PG
PREREQUISITES: Basic Understanding of Algorithms and Probabilityl
INDUSTRY SUPPORT: Google, Microsoft
2123 students have enrolled already!!
ABOUT THE INSTRUCTOR:
Dr Benny George K is an Assistant Professor in the Department of Computer Science and Engineering at IIT Guwahati. He is interested in theoretical aspects of computer science.
COURSE LAYOUT:
Week 1 : Introduction to Randomized Algorithms Week 2 : Probability Review Week 3 : Moments and Deviation Week 4 : The Probabilistic Method Week 5 : Markov Chains - I Week 6 : Markov Chain - II Week 7 : Number Theoretic Algorithms Week 8 : Graph Algorithms Week 9 : Approximate Counting Week 10 : Data Structures Week 11 : Computational Complexity Week 12 : Review of the course
SUGGESTED READING MATERIALS:
Rajeev Motwani and Prabhakar Raghavan,Randomized Algorithms
Michael Mitzenmacher and Eli Upfal Probability and Computing.
CERTIFICATION EXAM :
The exam is optional for a fee.
Date and Time of Exams: April 27 2019(Saturday). Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
Registration url: Announcements will be made when the registration form is open for registrations.
The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published.
CERTIFICATION:
Final score will be calculated as : 25% assignment score + 75% final exam score
25% assignment score is calculated as 25% of average of Best 8 out of 12 assignments
E-Certificate will be given to those who register and write the exam and score greater than or equal to 40% final score. Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IIT Guwahati.It will be e-verifiable at nptel.ac.in/noc.
