CS 210: Data Structures and Algorithms
- Random-access-machine model, concept of problem size, and asymptotic behaviour of time/space complexity.
- Estimation of time/space complexity by smooth functions and order notations.
- A simple example of worst-case time/space complexity analysis.
- Elementary data-structures: arrays, lists, queues, stacks and their applications.
- Binary search algorithm, binary trees, binary-search-tree data-structure.
- Balanced binary-search-tree: Red-Black trees.
- Hashing for insert, search, delete.
- Heap data structure.
- Efficient data structures, apart from those in items 6,7, and 8, for sets with the following group of operations:
- insert, delete, membership,
- insert, delete, minimum,
- union, intersection, dierence,
- disjoint-set union, nd.
- Sorting algorithms, including the average case analysis of quick-sort.
- Greedy paradigm with examples.
- Divide and conquer paradigm with examples.
- Dynamic-programming paradigm with examples.
- Denition of graphs, paths, trees, cycles. Data structures for graphs: adjacency lists, adjacency matrix.
- 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:
- AV Aho, J Hopcroft, JD Ullman, Data Structures and Algorithms, Addison- Wesley, 1983.
- TH Cormen, CF Leiserson, RL Rivest, C Stein, Introduction to Algorithms, 3rd Ed., MIT Press, 2009.
- AV Aho, J Hopcroft, JD Ullman, The Design and Analysis of Algorithms, Addison-Wesley, 1974.
- MT Goodrich, R Tamassia, DM Mount, Data Structures and Algorithms in Java, 5th Ed., Wiley, 2010. (Equivalent book in C also exists.)