Introduction to Algorithm
AnalysisTime and Space
Complexity- Elementary operations and Computation of Time Complexity- Best,
worst and Average Case Complexities- Complexity Calculation of simple
Recurrence Equations:Solution of Recurrence Equations – Iteration Method
and Recursion Tree Methods
Master’s Theorem(Proof not required) – examples, Asymptotic Notations
and their properties- Application of Asymptotic Notations in Algorithm
Analysis- Common Complexity Functions.
AVL Trees – rotations, Red-Black Trees insertion and deletion
(Techniques only; algorithms not expected). B-Trees – insertion and deletion
operations. Sets- Union and find operations on disjoint sets.
Graphs – DFS and BFS traversals, complexity, Spanning trees –
Minimum Cost Spanning Trees, single source shortest path algorithms,
Topological sorting, strongly connected components.
Divide and Conquer:The Control Abstraction, 2 way Merge sort, Strassen’s
Matrix Multiplication, Analysis.
Dynamic Programming : The control Abstraction- The Optimality Principle-
Optimal matrix multiplication, Bellman-Ford Algorithm
Analysis, Comparison of Divide
and Conquer and Dynamic Programming strategies
Greedy Strategy: - The Control Abstraction- the Fractional Knapsack
Problem, Minimal Cost Spanning Tree Computation- Prim’s Algorithm – Kruskal’s
Back Tracking: -The Control Abstraction – The N Queen’s Problem, 0/1
Branch and Bound: Travelling Salesman Problem.
Complexity Theory :-Tractable and
Intractable Problems- The P and NP Classes- Polynomial Time Reductions - The
NP- Hard and NP-Complete Classes