CSC 316 - Data Structures and Algorithms
Catalog Description: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.
Contact Hours:
- Lecture: 3 hours
Co-requisites: None
Restrictions:
Coordinator: Dr. Jason King
Textbook: Data Structures and Algorithms in Java
Course Outcomes:
Upon successful completion of this course, a student will be able to
- A. Data Structures
- A1. explain how abstract data types (e.g., lists, stacks, queues, maps, trees, priority queues, sets, and graphs) can be represented as different data structures;
- A2. construct and use linear data structures, including array-based lists, linked lists, list-based stacks, and array-based queues;
- A3. construct and use tree data structures, including general trees, binary trees, binary search trees, and balanced search trees
- A4. construct and use hash tables that use complex hash functions and collision resolution strategies, including chaining and open addressing;
- A5. construct and use priority queue data structures, including heaps;
- A6. construct and use union-find data structures, including up-trees;
- A7. construct and use graph data structures, including adjacency lists and adjacency matrices;
- A8. employ phases of software development to design, implement, and test a software solution that uses efficient data structures and algorithms to solve a given problem;
- B. Algorithms
- B1. characterize the worst-case running time and space usage of iterative algorithms as a function of input size;
- B2. characterize the worst-case running time and space usage of recursive algorithms as a function of input size;
- B3. design and implement complex iterative algorithms
- B4. design and implement complex recursive algorithms
- B5. describe and implement sorting algorithms, including bubblesort, insertion sort, selection sort, mergesort, quicksort, heapsort, counting sort, and radix sort;
- B6. describe and implement tree algorithms, including tree traversals;
- B7. describe and implement graph algorithms, including breadth-first and depth-first search, constructing minimum spanning trees, and finding shortest paths;
- B8. describe algorithmic design paradigms, including divide-and-conquer, brute-force search, dynamic programming, and greedy algorithms;
Topics:
- Problems, Algorithms, & Programs
- Justification Techniques & Growth Rates
- Algorithm Analysis & Iterative Sorting Algorithms
- List & Positional List Abstract Data Types
- Stack & Queue Abstract Data Types
- Recursive Algorithm Analysis
- Mergesort & Quicksort
- Map Abstract Data Type & List-based Map Data Structures
- Tree & Binary Tree Abstract Data Types
- Binary Search Trees
- AVL Trees
- Splay Trees
- (2,4) Trees
- Red-Black Trees
- Hash Functions
- Collision Resolution Strategies for Hash-based Maps
- Priority Queue & Adaptable Priority Queue Abstract Data Types
- Set & Disjoint Set Abstract Data Types
- Graph Abstract Data Type
- Graph Traversals
- Transitive Closure & All-Pairs Shortest Paths
- Single-Source Shortest Paths & Minimum Spanning Trees
- Graph Applications: Biconnectivity & PageRank
- Introduction to P v NP
- Data Structures in the Java Libraries
See Course Listings