CSC 316 Data Structures and Algorithms

3 Credit Hours

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 asymptotics
• Array and linked-memory implementations of lists, stacks, and queues
• Searching 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 operations
• Graphs 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)
• Hash tables and hashing techniques