• To introduce first level topics covering basics in Algorithms and Data Structures
  • To provide examples for various design paradigms
  • To identify the basic properties of graphs and trees and model simple applications



  • Ability to comprehend the basics in algorithms and data structures
  • Ability to solve problems that involve these concepts/similar problems
  • Ability to provide algorithmic solutions/approaches to new problems


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.



  • T.Cormen, C.Lieserson, R.Rivest, and C.Stein, “Introductions to Algorithms”, Prentice-Hall/India, 3rd edition, 2009