ESO 207: Data Structures and Algorithms

Units: 3-0-3-12

Pre-requisites: ESC101

Course Contents:

1. Random-access-machine model, concept of problem size, and asymptotic behaviour of time/space complexity.
2. Estimation of time/space complexity by smooth functions and order notations.
3. A simple example of worst-case time/space complexity analysis.
4. Elementary data-structures: arrays, lists, queues, stacks and their applications.
5. Binary search algorithm, binary trees, binary-search-tree data-structure.
6. Balanced binary-search-tree: Red-Black trees.
7. Hashing for insert, search, delete.
8. Heap data structure.
9. Efficient data structures, apart from those in items 6,7, and 8, for sets with the following group of operations:

1. insert, delete, membership,
2. insert, delete, minimum,
3. union, intersection, dierence,
4. disjoint-set union, nd.

10. Sorting algorithms, including the average case analysis of quick-sort.
11. Greedy paradigm with examples.
12. Divide and conquer paradigm with examples.
13. Dynamic-programming paradigm with examples.
14. Denition of graphs, paths, trees, cycles. Data structures for graphs: adjacency lists, adjacency matrix.
15. Graph algorithms: Depth First Search, Breadth First Search, Minimum Spanning Tree.

Additional topics based on time and interest may be selected from the following list: 16. Single-source shortest path computation, topological sorting of a partially ordered set, convex- hull computation, string matching algorithms, median computation, distributed algorithms.

Books and References:

1. AV Aho, J Hopcroft, JD Ullman, Data Structures and Algorithms, Addison- Wesley, 1983.
2. TH Cormen, CF Leiserson, RL Rivest, C Stein, Introduction to Algorithms, 3rd Ed., MIT Press, 2009.
3. AV Aho, J Hopcroft, JD Ullman, The Design and Analysis of Algorithms, Addison-Wesley, 1974.
4. MT Goodrich, R Tamassia, DM Mount, Data Structures and Algorithms in Java, 5th Ed., Wiley, 2010. (Equivalent book in C also exists.)