CST 370 – Design & Analysis of Algorithms
Course Overview
CST 370 covers fundamental algorithm design techniques and the data structures that support them. The course builds intuition for measuring and comparing algorithm efficiency, then applies that framework across a range of problem-solving strategies used throughout computer science.
Topics included asymptotic analysis (Big-O, Ω, Θ), hash tables, heaps, trees, graphs, sorting and searching, brute force, divide-and-conquer, decrease-and-conquer, transform-and-conquer, space-time tradeoffs, dynamic programming, and greedy algorithms.
Course Outcomes
- Measure algorithm efficiency and represent it using asymptotic notation.
- Apply design techniques including brute force, divide-and-conquer, decrease-and-conquer, transform-and-conquer, greedy, and dynamic programming.
- Explain sorting algorithms including heapsort, merge sort, and quicksort.
- Implement and analyze tree and graph algorithms: DFS, BFS, minimum spanning trees, and shortest path.
Sudoku Validator — Hash-Based Solution in C++
A group extra credit project implementing a 9×9 Sudoku board validator
in C++. The program reads a completed board from a file and determines whether it is
valid — no repeated values in any row, column, or 3×3 subgrid — outputting either
Valid!
or
Invalid!.
The algorithm uses C++'s unordered_set
for hash-based duplicate detection — inserting each cell value and treating a failed
insertion as a duplicate. This gives O(1) average-case insert and lookup,
avoiding the need for nested comparison loops.
My contribution: designed and implemented the full suite of input/output test cases,
covering valid boards, row duplicates, column duplicates, and subgrid violations
across 5 test files verified against expected output with diff.