CS252 Algorithms
Abbreviated lab and project descriptions are listed below. Laboratories are implemented in Java, while projects are implemented in the author's language of choice. Examples are provided at the links.
Labs
Lab 1 - Implemention of Conway's, "The Game of Life". Relevant topics include; review of Java arrays and the AWT and Swing packages.
Lab 2 - Visualization of sorting algorithms and tabulation of a sort work metric. Relevant topics include; GUI design, threading, and implementation of a sort library.
Lab 3 - Visualization of binary search tree operations. Relevant topics include: GUI design, BST ADT design, and recursive tree algorithms.
Lab 4 - Visualization of path generation through a maze. The maze ADT is constructed using equivalence classes and the union-find algorithm. A depth-first search is performed on the maze to generate a path from the start to finish cell. Relevant topics include; Maze ADT design, Graph ADT design, graph traversal algorithms, and advanced algorithmic techniques.
Research Projects
Genetic Algorithms (GA) Survey - A GA Java-based solution for the Traveling Salesman Problem using greedy crossover.
Spatial Partitioning Algorithms - OpenGL implementation of an Octree to perform 3D collision detection.
Approximate This! - A Survey of n-optimal approximation algorithms for NP-Complete problems. A Java-based implementation of the 2-optimal approximation algorithm for the Vertex Cover problem.