ECS 304: Data Structures and Algorithms (4)
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.
- Random-access-machine model , concept of problem size, and asymptotic behavior 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.
- 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.
- Definition 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: 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.Selected Readings
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms , 3rd Ed., MIT Press, 2009.
- J. Kleinberg, E. Tardos, Algorithm Design, 1st 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|