Pre-requisites : CS201
Syllabus : Algorithms: Models of Computation, Space & Time Complexity, Upper and lower bounds. Paradigms: Divide-and-conquer, branch & bound, backtracking, dynamic programming, greedy methods, local search algorithms. Sorting algorithms and their analysis: Insertion sort, Quicksort, Heapsort, Mergesort etc. Graph Algorithms: Connectivity, Shortest path, Spanning trees, Topological sorting etc. Efficient algorithms for disjoint set union and the UNION--FIND problems. Introduction to NP-completeness, Geometric algorithms, Approximation algorithms, Parallel and Randomized algorithms.
1. Manber, Udi, Introduction to Algorithms. 2/e. Addison-Wesley, 1994.
2. Cormen, Leiserson and Rivest. Introduction to Algorithms. MIT Press, 1990.
1. Aho, Hopcroft and Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley. 1974.
2. G Brassard and P Bratley. Fundamentals of Algorithms. Prentice Hall. 1995.