-
Background: Review of Algorithm Complexity and Order
Notations, sorting Methods Heap Sort, Radix Sort, Bucket Sort and Counting
Sorts.
-
Divide and Conquer Methods: Binary Search, merge sort, Quick
sort and Strasen’s matrix multiplication.
-
Greedy Method: Knapsack Problem, Job sequencing, optima
merge Patterns and minimal spanning trees.
-
Dynamic Programming: Matrix chin Multiplication Longes
Common Subsequence and 0/1 Knapsack problem.
-
Branch and bound: Travelling Salesman Problem and Lower
Bound theory.
-
Pattern Matching Algorithms: KMP Matcher and Boyer Moors
Algorithms.
-
Problem Classes NP, NP-Hard and Np-complete: Definitions of
P.NP, NP-Hard and NP-complete problems, Decision, Problems, Cooks Theorem,
Proving NP-complete problems satisfiability problem and Vertex cover
problem. Approximation Algorithms for Vertex Cover and Set Cover Problem.
-
Introduction to Assignement problems: Formulation of assignment Problem, Quadratic
Assignement and Biquadratic Assignment Problems, Branch and bound Methods
for Solving Assignment Problems (Not of Quardratic or Biquaratic
Assignment Problem).
Recommended Books:
1
Aho A. V., J.E. Hopcroft, J.D. Ullman: Design and Analysis of
Algorithms, Pearson Education.
2
Rivest and Cormen, Introduction to Algorithms, Prentice Hall of
India.
3
Baase.- Computer Algorithms Pearson Education.
4
Brassard- Algorithms Prentice Hall.
5
Bazaraa,- Linear Programme & Network Flows, John Wiley &
Sons. |