CS-7202 Randomized Algorithms Syllabus 7th semester
RGTU/RGPV Syllabus Randomized Algorithms Syllabus
Randomized Algorithms Course Content:
Unit -1 Introduction, A min-cut algorithm, Las Vegas and Monte Carlo, Binary planar partition, A probalistic recurrence, Computational models and time complexity.
Unit -2 Markov Chains and Random Walks: A 2-sat example, Markov chains, Random Walks on graphs, Cover times, Graph connectivity.
Unit -3 Random Data Structure : The fundamental data structure problem, Treaps, skip lists, Hash tables, Hashing with O(1) time.
Unit -4 Geometric algorithms and linear programming: Randomized incremental construction, Convex Hulls in the plane, Duality, Half space Intersection, Delanuay triangulation, Trapeziodal decomposition, Binary Space partition, The diamenter of point set, Random sampling, Linear programming. Graph algorithms: All pairs shortest paths, The min cut problem, Minimum Spanning tree,
Unit -5 Parallel and Distributed Computing: The PRAM Model, Sorting on a PRAM, Maximal independent sets, Perfect Matching, The choice coordinate problem, Byzantine Agreement.
References / Suggested Reading / Books for CS-7202 Randomized Algorithms :
1. Randomized Algorithms by R. Motwani and Raghavan, Cambridge press.
ConversionConversion EmoticonEmoticon