| Unit I |
Mathematical foundations & Asymptotic notations |
8 |
|
Algorithm, Mathematical Notations, Algorithm specification, Analysis of Algorithm- Introduction, Analyzing control structures, Asymptotic notations, space complexity, time complexity, Performance measurement, analyzing control structures, best case, worst case and average case analysis, Iterative Algorithm analysis |
|
| Unit II |
Divide and Conquer |
8 |
|
Recurrence relations, solutions of recurrence relations by Master Methods. Divide and conquer basic strategy, binary search, quick sort, merge sort, maximum and minimum finding |
|
| Unit III |
Greedy Method |
8 |
|
Greedy method – basic strategy, application to job sequencing with deadlines problem, minimum cost spanning trees, single source shortest path etc. |
|
| Unit IV |
Dynamic Programming |
6 |
|
Dynamic Programming basic strategy, multistage graphs, all pairs shortest path, single source shortest paths, optimal binary search trees, traveling salesman problems |
|
| Unit V |
Traversal And Search Techniques |
6 |
|
Basic Traversal and Search Techniques, breadth first search and depth first search, Backtracking basic strategy, 8--Queen’s problem, graph colouring, Hamiltonian cycles. NP, P Problems, Optimization Algorithms |
|