EECS 281 - Data Structures and Algorithms
This class covered a range of introductory computer science topics, from fundamental data structures to efficient algorithm design.
Fundamental Data Structures
In this class, we learned to use fundamental data structures like stacks, queues, deques, hash tables, binary trees, search trees, priority queues, and more. We additionally implemented each of the preceding data structures, some in a variety of ways - for a priority queue, for example, we implemented through everything from a binary tree to a pairing heap.
We also learned basic approaches to algorithm design. Topics which we engaged with included searching and sorting algorithms, recursive and dynamic programming, greedy algorithms and divide-and-conquer strategies, and more.
Using the aforementioned data structures and techniques, we created a number of algorithms to solve complex problems. The first project involved finding a solution to a 3 dimensional maze of arbitrary size, which I solved using a deque that stored reachable locations and an array which allowed for backtracing to the start. The next project was implementing a simple stock exchange, which I accomplished through a priority queue that would match the highest purchase requests with the lowest sale requests. Following that, we implemented a database query language, which used hash tables and search trees to speed up computation. Finally, we implemented a drone navigation problem, which required efficiently generating MSTs and reaching solutions or close approximations for the Travelling Salesman Problem, depending on the input size.
For each of these problems, we were graded not only on correctness, but on runtime and memory usage. This helped me learn efficiency in algorithm design, and I'm proud to have met all efficiency requirements for the class in addition to implementing solutions which arrived at the right answers.
Runtime Analysis and O-Notation
Beyond working with algorithm optimization in a concrete way as we attempted to make our programs run under the required threshold, we additionally worked on the mathematical side of things. By evaluating the big O notation of the various algorithms covered academically in lecture, we learned to think critically about algorithm design so that we could in turn create efficient and effective solutions to the problems we engaged with. This big O notation also formed an important part of our specifications when implementing data structures - we were required to implement solutions on the same order as the standard library for each of the data structures we created.