| |
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
| 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 |
| 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 |
| 2.0 |
Union and set membership algorithms |
| 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
close this window
|
 |
