Office of Academic Affairs
Indian Institute of Science Education and Research Bhopal

ECS 304: Data Structures and Algorithms (4)

Learning Objectives:

To get an introduction to some elementary data structures and some standard algorithm design techniques. Also to be able to mathematically analyze an algorithm to estimate its running time in the worst case.

Course Contents:

1. Random-access-machine model , concept of problem size, and asymptotic behavior 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. Sorting algorithms, including the average case analysis of quick-sort.
10. Greedy paradigm with examples.
11. Divide and conquer paradigm with examples.
12. Dynamic-programming paradigm with examples.
13. Definition of graphs, paths, trees, cycles. Data structures for graphs: adjacency lists, adjacency matrix.
14. 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: Single-source shortest path computation , topological sorting of a partially ordered set, convex- hull computation, string matching algorithms, median computation, data structures for disjoint sets.

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms , 3^rd Ed., MIT Press, 2009.
• J. Kleinberg, E. Tardos, Algorithm Design, 1^st Ed., Pearson, 2005 .
• A.V. Aho, J.E. Hopcroft , J.D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983.

Previous

Back to Course List

Next