CS6100 - Topics in Design and Analysis of Algorithms

Course Data :

Optimization Problem: Introduction, Scheduling Problem, 4/3-approximation, (2-1/m)- Approximation, LPT Schedule, Knapsack Problem(both versions), Set Cover Problem - log n approximation Weighted VC(vertex cover)-2-approximation Linear Programming: Introductin, Primal Dual, Weak Duality Theorem, Complementary Slackness Theorem, Weighted VC- (LP-version), Dual complementary Slackness Local Search:Introduction, Max-Cut Problem, Neighborhood Function, 2-approximation for Max-Cut, Applications Randomized Algorithm: Introduction, Determistic Algorithm, Las Vegas and Monte Carlo, Chernoff Bounds, Stochastic Bounds, Chernoff-Bounds for Binomial Variale, Fermat Little theorem, Miller Rubin Test Cryptography: Introduction, encryption, decryption, types of encryption, proof of encryption scheme

Pre-Requisites

    None

Parameters

Credits Type Date of Introduction
4 Elective (Core Course)

Previous Instances of the Course


© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits