CP7005 RANDOMIZED ALGORITHMS

CP7005    RANDOMIZED ALGORITHMS

UNIT I            INTRODUCTION TO RANDOMIZED ALGORITHMS

Introduction to Randomized Algorithms - Min-cut – Elementary Probability Theory – Models of Randomized Algorithms – Classification of Randomized Algorithms – Paradigms of the Design of Randomized Algorithms - Game Theoretic Techniques – Game Tree Evaluation – Minimax Principle – Randomness and Non Uniformity.   

UNIT II           PROBABILISTIC METHODS

Moments and Deviations – occupancy Problems – Markov and Chebyshev Inequalities – Randomized Selection – Two Point Sampling – The Stable Marriage Problem – The Probabilistic Method – Maximum Satisfiability – Expanding Graphs – Method of Conditional Probabilities – Markov Chains and Random Walks – 2-SAT Example – Random Walks on Graphs – Random Connectivity.  

UNIT III        ALGEBRAIC TECHNIQUES AND APPLICATIONS

Fingerprinting Techniques – Verifying Polynomial Identities – Perfect Matching in Graphs – Pattern Matching – Verification of Matrix Multiplication - Data Structuring Problems – Random Treaps – Skip Lists – Hash Tables.  

UNIT IV       GEOMETRIC AND GRAPH ALGORITHMS

Randomized Incremental Construction – Convex Hulls – Duality – Trapezoidal Decompositions – Linear Programming – Graph Algorithms – Min-cut – Minimum Spanning Trees.  

UNIT V       HASHING AND ONLINE ALGORITHMS

Hashing – Universal Hashing - Online Algorithms – Randomized Online Algorithms - Online Paging – Adversary Models – Relating the Adversaries – The k-server Problem

REFERENCES: 

1. Rajeev Motwani and Prabhakar Raghavan, “Randomized Algorithms”, Cambridge University Press, 1995. 

2. Juraj Hromkovic,”Design and Analysis of Randomized Algorithms”, Springer, 2010. 

3. Michael Mitzenmacher and Eli Upfal, “Probabilty and Computing – Randomized Algorithms and Probabilistic Analysis”, Cambridge University Press, 2005.