Randomized Algorithms CS-7202 SYLLABUS RGTU/RGPV Syllabus

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.

Add to Mixx! Mixx it!
| More

0 comments:

Post a Comment

 

RGTU Syllabus , RGPV Syllabus © Template Design by Herro | Publisher : Templatemu Copy Protected by RgtuSyllabus.blogspot.com in association with | RollingRoxy.Blogspot.Com | ResultsZone.Blogspot.Com | MBANetBook.Blogspot