Objectives
Outcomes
Unit – I
Mathematical preliminaries, time complexity and space complexity, worst-case and average-case analyses, use of order notations and related results, divide and conquer recurrences, recurrence relations: substitution method, recurrence trees, Master’s theorem and its applications.
Unit – II
QuickSort and its analyses, MergeSort recurrence, Strassen’s matrix multiplication, fast multiplication of large integers, binary search trees, priority queues, Heaps and HeapSort
Unit – III
Data structures for disjoint sets, Path compression, union by rank, Prim’s and Kruskal’s algorithms, Huffman coding, LZW coding, shortest paths, greedy activity selection, set cover and greedy heuristics.
Unit – IV
Dynamic Programming basics, matrix chain multiplication, DP solution for traveling salesman and 0/1 Knapsack problems, least common subsequences, independent sets and backtracking algorithm, Breadth/depth-first algorithms.
Unit – V
Topological sort, recursive graph algorithms, string matching: KMP algorithm, Rabin-Karp algorithm, number theory algorithms: basics, GCD and extended Eucledean algorithm, primality testing.