Courses with significant overlap with this course:

Semester of last offering:

Date of approval: dd-mmm-yyyy

Prerequisites:  

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. Efficient data structures, apart from those in items 6, 7, and 8, for sets with the foHowing group of operations: (i) insert, delete, membership, (ii) insert, delete, minimum, (iii) union, intersection, deference, (iv) 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. Definition 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.

Topics