EECS 281: Data Structures and Algorithms

Introduction to algorithm analysis and O-notation; Fundamental data structures including lists, stacks, queues, priority queues, hash tables, binary trees, search trees, balanced trees and graphs; searching and sorting algorithms; recursive algorithms; basic graph algorithms; introduction to greedy algorithms and divide and conquer strategy.

Project 1:Letterman Reboot

This program reads in a filename of words and then runs an algorithm that determines if a series of operations can be run on the words such that the first words can, after those alterations, be transformed into the end word (the last word in the file). The operations that can be done on the words are limited to one letter examinations and are determined by what the users enters on the command line. The main goal of this project was to familiarize ourselves with queues and stacks and a basic algorithm. This project challenged me to determine what data structures I wanted to use and how to write my own algorithm to perform the necessary operations.

Project 2:Mine All Mine

This project simulates a take on the game minefield. It reads in a minefield and then it is our responsibility to examine the miner's surrounding blocks and take the path of least work to break our way out of the mine. This project allowed us to practice implementing several kinds of priority queues and an interface that uses inheritance and basic dynamic polymorphism. This project challenged me to determine what data structures I wanted to use and how to write my own algorithm to find the least costing path as well as helping me become more proficient at testing and debugging my code.

Project 3: SillyQL

This project tested our understanding of relational databases. We were given a handful of SQL commands and we needed to implement these various commands using C++. Our program was required to read in a file containing a series of commands and we needed to run those commands and then perform the necessary operations on the tables in our database. Another feature we needed to implement was a BST and Hash option of organization of tables within our database. Our limitation was that only 1 table within the database can be organized into a BST or a Hash Table, but this aspect did force us to re-hash or redo the structure of the BST as we added and removed elements from the specific table. Like the two other projects before this, this project challenged me to determine appropriate data strucutres and making sure that data was stored in the correct method.

Project 4: Poke

This project implemented our knowledge of graphs and various graph algorithms. The scenario for the project is that we are a pokemon trainer with a map of different pokemon locations. Our goal is to visit each pokemon location while minimizing the distance we travel. Our one limitation is that the bottom left quadrant is an ocean and we can only reach ocean pokemon by first visiting a pokemon on the coast (an axis surrounding the bottom left quadrant).There were three different parts to project. Part one required us to implement Prim's algorithm to traverse the map. Part two required us to solve the traveling sales person problem by using arbitrary insertion. Part three required us to optimize the traveling sales person problem by incorporating a branch and bound algorithm.