The course will cover the following topics: Abstract data types; abstract and implementation-level views of data types. Linear and branching data structures, including stacks, queues, trees, heaps, hash tables, graphs, and others at discretion of instructor. Best, worst, and average case asymptotic time and space complexity as a means of formal analysis of iterative and recursive algorithms. The course will cover a wide range of data structures and associated algorithms, including:Properties of programs, running time, and asymptoticsArray and linked-memory implementations of lists, stacks, and queuesSearching using lists, unbalanced tree structures (binary search trees, splay trees) and balanced trees (AVL trees, 2-4 trees, red-black trees)Up-trees as sets with union-find operationsGraphs and graph algorithms (traversals, shortest paths, minimum spanning trees)Sorting (including heap sort, merge sort, insertion sort, selection sort, quick sort, counting sort, radix sort)
- Instructor: Staff, __