RGPV COMPUTER SCIENCE RANDOMIZED ALGORITHMS (CS-7202)

TAGS:- RGPV COMPUTER SCIENCE 7TH SEM SYLLABUS I DOWNLOAD RGPV COMPUTER SCIENCE 7TH SEM ELECTIVE SUBJECT SYLLABUS I RGPV COMPUTER SCIENCE 7TH SEM SYLLABUS I DOWNLOAD RGPV COMPUTER SCIENCE 7TH SEM SYLLABUS IDOWNLOAD RGPV COMPUTER SCIENCE COMPLETE SYLLABUS

Rajiv Gandhi Technological University, Bhopal (MP)
B.E. (CS) COMPUTER SCIENCE ENGINEERING 

RGPV COMPUTER SCIENCE RANDOMIZED ALGORITHMS (CS-7202)

Unit -I

Introduction, A min-cut algorithm, Las Vegas and Monte Carlo, Binary planar partition, A probalistic recurrence, Computational models and time complexity.

Unit -II

Markov Chains and Random Walks: A 2-sat example, Markov chains, Random Walks on graphs, Cover times, Graph connectivity.
Unit -III

Random Data Structure : The fundamental data structure problem, Treaps, skip lists, Hash tables, Hashing with O(1) time.

Unit -IV

Geometric algorithms and linear programming: Randomized incremental construction, Convex Hulls in the plane,Duality,Half space Intersection,Delanuay triangulation,Trapeziodal decomposition, Binary Spacepartition, The diamenter of point set, Random sampling, Linear programming. Graph algorithms: All pairs shortest paths, The min cut problem, Minimum Spanning tree,

Unit -V

Parallel and Distributed Computing: The PRAM Model, Sorting on a PRAM,Maximal independent sets,Perfect Matching, The choice coordinate problem, Byzantine Agreement.

References Books:-

1. Randomized Algorithms by R. Motwani and Raghavan, Cambridge press.

7201                7202                 7203