6 CS 3-DESIGN & ANALYSIS OF ALGORITHMS |
Units: I |
BACKGROUND: Review of Algorithm Complexity and Order Notations and Sorting Methods. DIVIDE AND CONQUER
METHOD: Binary Search, Merge Sort, Quick sort and strassen's matrix multiplication algorithms. GREEDY METHOD:
Knapsack Problem, Job Sequencing, Optimal Merge Patterns and Minimal Spanning Trees.
|
Units: II |
DYNAMIC PROGRAMMING: Matrix Chain Multiplication. Longest Common Subsequence and 0/1 Knapsack Problem.
BRANCH AND BOUND: Traveling Salesman Problem and Lower Bound Theory. Backtracking Algorithms and queens
problem. |
Units: III |
PATTERN MATCHING ALGORITHMS: Naïve and Rabin Karp string matching algorithms, KMP Matcher and
Boyer Moore Algorithms. ASSIGNMENT PROBLEMS: Formulation of Assignment and Quadratic Assignment Problem.
|
Units: IV |
RANDOMIZED ALGORITHMS. Las Vegas algorithms, Monte Carlo algorithms, randomized algorithm for Min-Cut,
randomized algorithm for 2-SAT. Problem definition of Multicommodity flow, Flow shop scheduling and Network capacity
assignment problems.
|
Units: V |
PROBLEM CLASSES NP, NP-HARD AND NP-COMPLETE: Definitions of P, NP-Hard and NP-Complete
Problems. Decision Problems. Cook's Theorem. Proving NP-Complete Problems - Satisfiability problem and Vertex Cover
Problem. Approximation Algorithms for Vertex Cover and Set Cover Problem.
|