Introduction: The role of algorithms in computing.
Complexity Analysis: Growth of a function, Asymptotic notation.
Recurrence Relation: Methods to solve recurrences, Substitution method, Recursion tree method, Master method.
Graph related algorithms: Breadth First search, Depth First Search, Topological sort, Strongly connected components, Euler Path, Articulation Point.
Shortest Path: Dijkstra’s shortest path algorithm, The Bellman-Ford algorithm for single source shortest path, The Floyd-Warshall algorithm for all-pair shortest path.
Divide and Conquer: basic idea, properties, Applications of Divide and Conquer: Counting Inversions, Closest pair of points, etc.
Dynamic Programming: Basic idea, Comparison with Divide and Conquer, Memorization. Application of Dynamic programming: Coin related problems, Longest Increasing Sequence (LIS), Longest Common Subsequence (LCS), 0/1 Knapsack problem, Matrix Chain Multiplication, etc.
Greedy method: Elements of greedy method basic control structure, Comparison with dynamic programming and Divide and Conquer. Application of Greedy method: Minimum spanning tree: The algorithms of Prim &Kruskal, Job sequencing with deadline.
Backtracking: Basic idea behind backtracking, control structure. Application of backtracking: Permutation & Combination Generation, Graph coloring problem, n-queens problems, Hamiltonian Cycle etc. Branch and Bound.
String Matching Algorithms: Naive string matching algorithm, String matching with finite automata, The Boyer-More algorithm for string matching, Knuth-Morris-Pratt algorithm.
NP-Completeness: Polynomial time, Polynomial Time verification, NP-completeness and reducibility, NP-Completeness proofs, NP Complete problems.
Approximation Algorithms: Introduction, Approximation Ratio, Approximation algorithms for: Vertex-Cover Problem, TSP Problem