Randomized Algorithms
Offered By: Indian Institute of Technology Guwahati via Swayam
Course Description
Overview
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.PRE-REQUISITES : Basic Understanding of Algorithms and ProbabilitylINDUSTRY SUPPORT : Google, Microsoft
INTENDED AUDIENCE : Senior UG students, PG students and Ph.D candidates interested in computer science, combinatorics, etc.PRE-REQUISITES : Basic Understanding of Algorithms and ProbabilitylINDUSTRY SUPPORT : Google, Microsoft
Syllabus
COURSE LAYOUT
Week 1 : Introduction to Randomized AlgorithmsWeek 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
Taught by
Prof. Benny George K
Tags
Related Courses
Automata TheoryStanford University via edX Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX 算法设计与分析 Design and Analysis of Algorithms
Peking University via Coursera How to Win Coding Competitions: Secrets of Champions
ITMO University via edX Introdução à Ciência da Computação com Python Parte 2
Universidade de São Paulo via Coursera