SNHU CS Data Structures and Algorithms
Files include a runtime analysis for three data structures (i.e., vector, hash table, and binary tree search) and an implementation of a binary search tree algorithm to store, sort, and display a list of courses as well as to search for and display a specific course from that list.
A school named ABC University requested a runtime analysis to determine an algorithm with the best worst-case time complexity to use in an advising tool for students in their computer science department. They provided a list of three data structures (i.e., vector, hash table, and binary tree search) that were to be examined for use with a CSV (comma-separated value) file for loading, sorting, and displaying information about different courses. Error checks were also examined to ensure that each course's prerequisites were present in a list of all available computer science and math courses.
The runtime analysis showed that the data structure with the best worst-case time complexity was a binary search tree, with an overall Big-O notation of O(n), indicating that for all compiled code the worst-case would be searching through each course once. If a binary search tree was formed with code parsed in from a CSV input file that had either ever-increasing or ever-decreasing values, the resulting tree would be a straight line, representing O(n). However, with any randomness to the values added to the binary search tree, the time complexity is reduced (e.g., approaching O(log n)), as the inherent downward branching removes many values to search through.
Through writing the run-time analysis, I have learned more about how time complexities are calculated and algorithms are chosen. By writing the code for a binary search tree, as well as previous algorithms for other assignments, I have learned that implementing certain algorithms require a great deal more time and research than others. A vector is a lot simpler to write but worse to run in worst-case scenarios than a binary search tree. A hash table cannot be sorted easily, so for many applications, including the requested project, it would be even worse to use than a vector.