Department of Computer Science & Engineering

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