Syllabus Algorithms - [CS3401] UNIT I INTRODUCTION Algorithm 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. (Chapter - 1) 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 - Shortest path : Bellman - Ford algorithm - Dijkstra’s algorithm - Floyd-Warshall algorithm Network flow : Flow networks - Ford-Fulkerson method - Matching : Maximum bipartite matching. (Chapter - 2) 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. (Chapters - 3, 4, 5) 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. (Chapter - 6) UNIT V NP-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. (Chapter - 7)
