CS201

DATA STRUCTURES AND ALGORITHMS

Objectives      

  • 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

 

Outcomes

  • 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.

 

TEXT BOOKS:

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