Data Structures: COSC 320 (4)
Abstract data types, classes, and design patterns with C++. Sorting algorithms—insertion sort, merge sort, heapsort, quicksort. Linear data structures—stacks, queues, linked lists. Hash tables. Trees—binary search trees, 2-3 trees, B-trees, abstract syntax trees. Disjoint sets. Graphs—search algorithms, spanning trees, Kruskal's and Dijkstra's algorithms.
Prerequisite: COSC 221
| Hours | Topic |
|---|---|
| Introduction (6 hours) | |
| 2..0 | Procedural features of C++ |
| 2.0 | Object-oriented features of C++ |
| 2.0 | Review of asymptotic behavior and recurrences |
| Sorting Algorithms (5 hours) | |
| 1.0 | Insertion sort |
| 1.0 | Merge sort |
| 2.0 | Heapsort, priority queues |
| 1.0 | Quicksort |
| Linear Data Structures (10 hours) | |
| 1.0 | Array implementation of stack and queue ADTs |
| 2.0 | Pointer implementation of linked lists |
| 1.0 | Linked implementation of stack and queue ADTs |
| 2.0 | State design pattern for linked lists |
| 4.0 | Strategy design pattern for stack and queue |
| ADTs Hash Tables (3 hours) | |
| 2.0 | Collision techniques |
| 1.0 | Hashing functions |
| Trees (10 hours) | |
| 0.5 | Mathematical definitions |
| 1.0 | Binary search tree ADTs |
| 3.0 | State design pattern for binary search trees |
| 2.0 | 2-3 trees |
| 1.0 | B-trees |
| 1.0 | Abstract syntax trees |
| 1.5 | Recursive composition design pattern |
| Disjoint Sets (2 hours) | |
| 2.0 | Union and set membership algorithms |
| Graphs (11 hours) | |
| 0.5 | Mathematical definitions |
| 1.5 | Adjacency list and adjacency matrix representations |
| 2.0 | Breadth-first and depth-first searches |
| 1.0 | Minimum spanning trees |
| 2.0 | Kruskal's algorithm |
| 2.0 | The shortest path problem |
| 2.0 | Dijkstra's algorithm |
Total: 47.0 hours, excluding holidays, review sessions, and exams
*Fifty-minute class hours