This is my Computer Science Capstone Project for the Spring 2013 Semester.
For my first capstone, I wanted to attempt a project that was both feasible in scope and educationally interesting. After a fall semester of higher level computer science classes, I had become increasingly intrigued in algorithms, data structures, and software optimization.
The challenge of this project is three-fold:
-
Learning a new programming language, Google's “Go.” Go is a very new language, created in 2007 and announced in 2009. It is a compiled and garbage-collected language, and allows for an object-oriented style of programming. The main reason Go is of interest to my project is its concurrency, or the ability to easily parallelize operations.
-
Continued studying of the implementation of both graph data structures and search algorithms. The algorithm in particular that will be implemented is the Edmonds-Karp, an algorithm used to find the maximum flow in a flow network.
-
Parallelization of the algorithm. Once the algorithm has been implemented, further study will be necessary in order to cut it up into separate “jobs” or “threads” that will be set up to run concurrently. Above all, this will be the most complicated step because it will require a fundamental understanding both of how the algorithm is executed and how Go handles its coroutines.
Concurrent algorithm implementation complete; still needs a little clean-up here and there, but overall the project is finished.