CS 499 Milestone Three
Enhancement Two: Algorithms and Data Structures
The artifact I selected for this enhancement is my ABCU Advising Assistance Program, originally created in CS 300: Data Structures and Algorithms in 2025 C-6 (Oct - Dec). The application allows users to load course information from a CSV file, display the courses in alphanumeric order, and search for individual courses and their prerequisites. The original project demonstrated the use of a binary search tree (BST) to organize and retrieve course data efficiently.
I selected this artifact because it represents one of the strongest examples of my understanding of algorithms and data structures throughout the Computer Science program. While the original project successfully met the course requirements, I recognized an opportunity to improve its efficiency and demonstrate a deeper understanding of balanced tree algorithms. For this enhancement, I replaced the original binary search tree with a self-balancing AVL tree while preserving the program's existing functionality. I also modernized the implementation by replacing manual node ownership with std::unique_ptr, improving memory safety and making the code easier to maintain. In addition, I created automated tests to verify AVL rotations and tree invariants, along with an empirical benchmark comparing the enhanced AVL implementation against a traditional binary search tree using both sorted and randomized insertion orders.
This enhancement primarily demonstrates my ability to design and evaluate computing solutions using appropriate algorithmic principles, directly supporting Computer Science Program Outcome Three. Converting the application to an AVL tree required understanding not only binary search tree operations, but also balance factors, tree height maintenance, and the four rotation cases required to preserve logarithmic performance. The benchmarking portion further reinforced the importance of evaluating design decisions with measurable data instead of relying solely on theoretical complexity. The enhancement also contributes to Outcome Four by demonstrating the use of modern C++ features, modular design, testing, and professional software engineering practices. Although security was not the primary focus of this artifact, using smart pointers instead of manual memory management also reduces opportunities for memory-related programming errors and supports a more robust implementation.
The completed enhancement aligns well with the goals I established during Module One. My original plan was to replace the binary search tree with an AVL tree, introduce smart-pointer ownership, compare balanced and unbalanced implementations through benchmarking, and document the tradeoffs involved in those design decisions. The completed artifact accomplishes those objectives while preserving the original behavior of the advising application. During testing, the benchmark clearly demonstrated the advantage of AVL trees under worst-case insertion order while also showing that the additional balancing work introduces some overhead compared to an ordinary binary search tree when the data is already reasonably balanced. Seeing both the theoretical and measured results reinforced that algorithm selection is often a tradeoff rather than a universally better solution. I do not have any updates to my outcome-coverage plan because the completed enhancement supports the outcomes I identified in Module One as intended.
Working through this enhancement strengthened my understanding of self-balancing trees beyond what I learned in the original CS 300 course. Implementing AVL rotations correctly while maintaining ownership through smart pointers required careful attention to both algorithm correctness and modern C++ resource management. I also gained valuable experience designing repeatable benchmarks and automated tests to validate both correctness and performance. One of the more challenging aspects of the enhancement was ensuring that balancing logic did not change the outward behavior of the advising application. The finished project demonstrates not only a stronger implementation of the underlying data structure, but also a more thoughtful approach to testing, documentation, and evaluating algorithmic tradeoffs. Overall, I believe this enhancement better represents my current abilities and is a much stronger artifact for inclusion in my professional ePortfolio.
Benchmark Evidence
The benchmark inserted the same records into both trees and ran the same queries against each. Values are medians in microseconds from a Release build at 10,000 records.
Sorted insertion, n = 10,000
BST height 10000 AVL height 14
BST build 371762.3 AVL build 4542.2
BST searches 306753.1 AVL searches 1929.4
Randomized insertion, n = 10,000
BST height 29 AVL height 16
BST build 3307.2 AVL build 5143.5
BST searches 2480.7 AVL searches 1947.2Sorted insertion is the case that matters most. The ordinary tree degenerated to a height equal to the record count while the AVL tree stayed at 14. The randomized case shows the cost: the ordinary tree built faster because the AVL tree pays for height bookkeeping and rotations.