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.