CS4301 – ALGORITHMS

                                                   UNIT – I: INTRODUCTION
Al gorithm analysis: Time and space complexity – Asymptotic Notations and its

    properties Best case, Worst case and average case analysis – Recurrence relation:
substitution method – Lower bounds – searching: linear search, binary search and
Interpolation Search, Pattern search: The naïve string-matching algorithm – Rabin-Karp
algorithm – Knuth-Morris-Pratt algorithm. Sorting: Insertion sort – heap sort

                                         UNIT – II: GRAPH ALGORITHMS
Graph algorithms: Representations of graphs – Graph traversal: DFS – BFS –
applications – Connectivity, strong connectivity, bi-connectivity – Minimum spanning
tree: Kruskal’s and Prim’s algorithm – Shortestpath: Bellman-Ford algorithm –
Dijkstra’s algorithm – Floyd-Warshall algorithm Network flow: Flownetworks –
Ford-Fulkerson method – Matching: Maximum bipartite matchin.

                                  UNIT – III: ALGORITHM DESIGN TECHNIQUES
Divide and Conquer methodology: Finding maximum and minimum – Merge
sort – Quick sort Dynamic programming: Elements of dynamic programming –
Matrix-chain multiplication – Multi stage graph – Optimal Binary Search Trees. Greedy
Technique: Elements of the greedy strategy – Activity-selection problem – Optimal
Merge pattern – Huffman Trees.

                               UNIT – IV: STATE SPACE SEARCH ALGORITHMS
Backtracking: n-Queens problem – Hamiltonian Circuit Problem – Subset Sum
Problem – Graph colouring problem Branch and Bound: Solving 15-Puzzle problem
– Assignment problem – Knapsack Problem – Travelling Salesman Problem

                          UNIT – V: NIP-COMPLETE AND APPROXIMATION ALGORITHM
Tractable and intractable problems: Polynomial time algorithms – Venn diagram
representation – NP algorithms – NP-hardness and NP-completeness – Bin Packing
problem – Problem reduction: TSP – 3-CNF problem. Approximation Algorithms:
TSP – Randomized Algorithms: concept and application – primality testing –
randomized quick sort – Finding kth smallest number