Projects

Collegiate

Fall Semester 2009

While maintaining the stamina to make it through the first semester of my Junior year at Cedarville University, I completed the following projects.

Algorithms

Roads Scholar

A map is read in from the data file accompanying the source files. Predecessor and adjacency matrices are then created and filled using the Floyd-Warshall algorithm for single-source shortest path of the built map. Signs are also placed along a particular direction on roads between intersections, and cities are placed at given intersections. Distances to cities are added to the signs from the filled in adjacency matrix if the sign is along a road in a direction that is the shortest path to a given city on the map.
Download Source

Rush Hour

One of the best puzzle games of all time (in my opinion) is the Rush Hour board game. This Java program will solve any game board given in the minimum number of moves using properties of the Greedy algorithm. It's abstracted enough that I went ahead and built a playable interface for it in Java as well. Yup, play it on any operating system (with the stand-alone version) or in your browser (with the applet version). Standard levels are included, and you can even make your own levels! (It’s worth noting that clicking the Solve button may take a ridiculous amount of time if the applet version is run.
Play Rush Hour 0.2 in Your Brower (Requires Java 1.5 or Higher)
Download Rush Hour 0.2 (Requires Java 1.5 or Higher)
Download Version 0.2 (Playable Interface) Source
Download Version 0.1 (Console Interface) Source

Making Change

The classic, dynamic programming problem for making coins for a given value out of a particular set of denominations. The greedy algorithm is really only efficient for U.S. coin denominations, so for this project we implemented it using an algorithm that would always guarantee we found the optimal (least amount of coins used) solution. Three separate algorithms were implemented to better show the value of dynamic programming: bottom-up iterative, recursive with memoization, recursive without memoization. I don't recommend running anything higher than twenty-five on the recursive without memoization since it'll take ... Forever. A brief summary of our findings can be found here. We originally implemented this project in Java, but for fun, curiosity, and speed comparisons, I went back and implemented it in Python and C++ as well. All language implementations are contained within the zip file.
Download Source

Sort Comparisons

A benchmark framework developed using Java to compare the sort times of QuickSort and InsertionSort. A complete report of our findings can be found here.
Download Source

Simulated First-Come-First-Serve Scheduler

Using the SimPy library, a first-come-first-serve scheduler was written using the Python program language. Python 2.6 with SimPy is required to compile the source.
Download Version 0.1 in Python 2.6

The Internet Home of Alex Laird

Ask Me Why