CS210A - Data Structure And Algorithms
Prerequisites:
3-0-3-12
Course Contents
- 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.
- 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.
- 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, distributed algorithms.
Topics
Current Course Information
Instructor(s):
Number of sections:
Tutors for each section:
Schedule for Lectures:
Schedule for Tutorial:
Schedule for Labs: