Pre-requisite: CA 763, CA 761, CA 769
Outline:
Arrays, stacks, queues, linked lists, trees- their applications. Fundamental Strategies in algorithm design - recursion, divide and conquer, greedy and dynamic programming methods.
Problems and instances- Efficiency of algorithms- asymptotic notations- solving recurrence relations, complexity of Sorting algorithms- Exchange sort, selection sort, Insertion Sort, Heap Sort, Quick Sort, Radix Sort. Medians and order statistic. Complexity of searching- Binary search- hash tables, binary search trees, insertion and deletion.
Graph algorithms- breadth and depth first searches, MST using disjoint set union algorithm, single source and all pairs shortest path, flow networks, maximum bipartite matching – complexity analysis.
Polynomials - FFT, multiplication of large integers, Algorithms for random number generation. probabilistic algorithms- selection, sorting, searching and Monte Carlo methods.
Definition of non-deterministic polynomial algorithms. Basic concepts of NP-Hard and NP-complete problems- Cook's theorem, Reduction of Clique, Node cover, Chromatic Number as NPC. Scheduling problem - NP hard.
Books:
1. Horowitz, Sahni and Rajasekaran -" Fundamentals of Computer Algorithms", 1st Edition, 1999, Galgotia.
2. Cormen, Leiserson, Rivest and Stein - "Introduction to Algorithms", 2nd Edition, MIT Press
