6 IT 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.
|