Skip to main content

IE2xx : Data Structures and Algorithms

Prerequisites: None

Contents:

1. Object oriented programming: Concepts and use in data structures.  

2. Complexity analysis: Computational complexity, asymptotic complexity, Big-O Notation, Omega and Theta Notations, Amortized complexity, Theory of P and NP complexity classes

3. Algorithm paradigms: greedy, divide-and-conquer, dynamic programming

3. Linked list, stacks, queues, priority queues, dequeues. 

4. Recursion and Backtracking. Binary trees: creation, insertion, deletion, search, traversal. Balancing trees, self-adjusting trees. Heaps: Creation, insertion, deletion, search, traversal.

5. K-d trees, Multi-way trees: B-tree, Tries.

6. Sorting algorithms

7. Hashing algorithms. Dictionaries, skip lists.

8. Graphs: Graph representation, traversal, cycle detection, spanning trees, topological sort, Shortest path: Dijkstra's algorithm, 

9. Networks: Matching, Maximum flow algorithm, Minimum cost algorithm.  

References:

  • G. L. Heileman (2002) Data Structures Algorithms and Object Oriented Programming, Tata Mcgraw Hill.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2003) Introduction to Algorithms and Java, 2nd edition, McGraw-Hill.
  • Dasgupta, Papadimitriou and Vazirani, (2006) Algorithms, McGraw Hill
  • Ellis Horowitz and Sartaj Sahni, Foundations of Computer Algorithms.
  • Alfred V. Aho, John E. Hopcroft and Jeffrey Ullman (1983) Data Structures and Algorithms, Pearson Education India.