2004 Computer Science Senior Design Projects

Craig W. Brubaker

Advisor: Prof. Hemmendinger, Prof. Hollocher

Earth's Tides Simulation

This project is a simulation of Earth's tides to be used in introductory geology courses. The simulation models the orbits of the moon and the earth, calculates the resultant tidal forces, and graphically displays the tidal bulges that are produced. For user input the simulation accepts current positions in the earth and moon's orbital cycles. Each cycle can be turned on or off and it is reflected in the tidal display by removing that cycle's tidal effect. In addition, current cycle times are used for dynamic output when the simulation advances time in days or hours.

Simplifying the real system, we assume that the earth is uniformly covered by ocean. Thus our simulation does not take into account the effects of the continents. However the display does account for the phenomenon of two bulges on both sides of the Earth for each tidal force. The tidal display itself is a color-coded fixed angle view of the earth showing tidal height. It displays the tidal bulges calculated from the simulation's orbital modeling and the equation for tidal force. Lastly the display for this simulation is able to show the solar and lunar tidal bulges separately and together.

This project has been developed for Prof. Kurt Hollocher (UC Geology Department), and he has served as a technical consultant for it.

Project link    Poster Link

Melissa Chávez

Advisor: Prof. Fernandes

Front-end for a RETAIN Function

IBM is trying to provide their support group with a better user interface in their primary database, RETAIN. This primary tool was created 30 years ago; therefore, it has a command line user interface (with complicated and unintuitive commands), based on technology at the time. When problems reported by customers are caused by an error in IBM's operating system code, an APAR (Authorized Program Analysis Report) is created so the problem can be fixed. My primary goal was the design and implementation of a front-end for a portion of RETAIN, including creating an APAR. A second goal was to implement a spell checker, which is used to identify misspelled acronyms, in a detailed problem description that is written in one of the windows. I implemented the spell checker using the Approximate String Matching Algorithm which compares the misspelled word with the word in the dictionary in a character by character basis; it gives the comparison a weight. Using the lowest weights, it makes the suggestions for the misspelled word.

Project link    Poster Link

Jason Cook

Advisor: Prof. Fernandes

Application of Artificial Intelligence to Chess Playing

Artificial Intelligence is a branch of Computer Science that can be thought of as teaching a computer to act creatively. One interesting application of Artificial Intelligence is programming a computer to play chess. Chess presents challenges that are not present in other games, because of its complexity and the number of possible moves to evaluate. A common strategy for chess programs is to develop a tree data structure with all of the possible moves from a given starting board up to a certain depth, and then traverse the tree and evaluate it to find a good move. The most advanced current programs work around the potentially astronomical size of this tree by eliminating branches with heuristics, and sometimes by using powerful chess-specific hardware.P I have implemented a simple "chess engine", which is the logic behind a full chess computer game. The user interface and other features received limited attention, as the real focus was on strengthening the program's play. The program attempts to balance as much chess playing power as possible with the constraints of running on a desktop computer.

My engine builds a tree of the possible moves from the current board position, extending the tree and looking ahead for as many moves as time allows. The tree is evaluated for the best move after each new level of moves has been added, to ensure that there is always a current "best move" when the time limit for a turn is encountered, without stopping the tree building sooner than necessary (which limits the number of moves ahead the evaluation can see, handicapping it). Running on different hardware allows the program to evaluate more or fewer moves, but it always takes full advantage of the available resources.

The number of moves evaluated is of great importance in determining the strength of a chess engine of this type. For that reason I have implemented the engine in C to minimize the time of execution for the many tree manipulations and bitwise operations involved. The algorithm being used is an anytime implementation of NegaMax search for boards in an iteratively deepened decision tree. Individual boards in the decision tree are evaluated based on material and "emprise". The validation of this project was done by testing the engine against multiple freely available chess engines of varying power. The results of these games were then documented and analyzed.

Project link    Poster Link

Jeff Dalton

Advisor: Prof. David Hannay

Aspect-Oriented Refactoring of the Apache Cocoon Shared-Object Resource Allocation System

Aspect-oriented programming (AOP) enables developers to develop and manage 'cross-cutting concerns' unrelated to the primary function of the system component. Using AOP, these concerns can then be introduced to the base component easily and in a structured manner. Other benefits of using AOP include the creation of software that is easier to understand and modify. Caching, a common and effective technique to improve the performance of applications and middleware, is such a cross-cutting concern. We explore this by refactoring a complex web application, Apache Cocoon, using AOP to introduce a caching mechanism. The goal is to retain the original external behavior, while removing complexity and adding flexibility in the caching system. The development of the AspectJ language and compiler allows the application of this methodology on the existing base of Java-based web applications without requiring new infrastructure. This project takes the next step by using AspectJ to simplify and extend the caching system in a large and complex XML-based website publishing system; it explores the potential difficulties associated with using AspectJ to accomplish this task and considers the effect that the application architecture has on the aspect-oriented refactoring process.

Project link    Poster Link

Claudio Flores

Advisor: Prof. Hemmindinger

Addition to PCSpim

PCSpim is a program which compiles instructions for the MIPS architecture. The program is written in yacc, C, and lex. The first hurdle is to understand the code Mr. Larus wrote. The code is spread out into multiple files with the number of lines of code in the thousands. The second objective is to make additions to the program in order to make it more programming friendly. Currently the program does not accept macros or mathematical operations to variables. With the addition of variables to the PCSpim program we are now able to do away with the so called magic numbers, which will make following programs less difficult to follow. In order to add mathematical operations to the program, the parser has to be changed in order to achieve variable math. Also we are adding the power of macros. The macro will make the program, again easier to follow and more modular than before. Macros are like subroutines in a program, but the advantage is that macros get inserted into the code and the machine does not have to jump to the routine but just execute the code.

Project link    Poster Link

Jonathan Jackson

Advisor: Prof. David Hannay

Cluster Analysis and 3-Dimensional Display

Stimuli from the brain cause our bodies to react to certain things. Neurons communicating with each other through electrical impulses enable people and all other animals to turn thought into movement. Dragonflies, because of their keen sense of sight and remarkable flying skills, draw a lot of attention to their nervous system. Recently, biologists have been able to retrieve information regarding the nervous system of the insects. The retrieval involves inserting electrodes into the neuro-chord of the dragonfly then subjecting the insect to a set of visual stimuli. When the optic nerves stimulate the neuro-chord, the electrical impusles are recorded by the electrode. This data then needs to be sorted to show which nerve cells in the chord go off at which time. Cluster sorting provides a solution to this. Cluster sorting takes data and groups the values into concentrated areas of values that fall within a certain range. Being able to cluster the data allows biologists to map the neuro-chord of the dragonfly and to examine this data in relation to time allows scientists to decode the communication betweens neurons. Successfully decoding the sets of impulses not only gives us insight on the dragonfly, but gives us an algorthm to perform these tests on other insects and possible animals.

Project link    Poster Link

Steve LaPlante, Bryce Levin, Michael Losure

Advisor: Prof. Hannay and Prof. Cura

View Manchu: A Virtual Model of the Qianlong Emperor's Tomb

3d Modeling software allows for the creation of realistic virtual environments without the extremely complex programming involved in real-time 3D graphics, but is not conducive to interactivity. Our project was to realistically recreate a Qing dynasty tomb in an easily distributable form that would allow a user to virtually navigate the model. We settled on a design that mixed the graphical sophistication of pre-rendered graphics and the portability of web applications. To ensure the accuracy of our information, we traveled to China and sketched, measured, and photographed the tomb. Using our data and 3ds Max, a 3D modeling software package, we created the to-scale geometry of the tomb. Since the carved pictures and text on the walls of the tomb are of interest to scholars, we implemented bump-mapping techniques to virtually carve the walls of our model. To achieve interactivity, we designed a virtual camera system and rendered a series of movies depicting movement about the tomb. We compiled these movies into a Flash application and programmed a user interface. The completed walk-through and Flash application is an example of technologies converging to provide a new type of educational tool.

Project link    Poster Link

William MacMillan

Advisor: Prof. Fernandes

GraceNote Fair-Use Jukebox

We have seen online "reserve" systems for professors to allow students to view copyrighted written works, so why not apply this to music? Currently the Union College library allows students to check out CDs or listen to them in a designated lab. This is neither copyright-safe since students have easy access to CD burners, nor is it cost-efficient as CDs are not a durable media and are more vulnerable to data loss than a book. Recent copyright laws like the Digital Millennium Copyright Act have placed heavy restrictions on what is legal and illegal whilst dealing with digital multimedia. What allows professors to share copyrighted works with their class is the doctrine of "Fair-Use". Academia has special exemptions to the restrictive copyright laws that allow students to view copyrighted works for scholarly and critical purposes. Though the exemptions exist, one must be very careful that the copyrighted works stay within the class room environment; this is to ensure that the Fair-Use doctrine applies.

"GraceNote" is a system designed to mimic the online reserve system the library has for copyrighted written works. The system provides a student of a given music course access to streaming audio of copyrighted music. In this way the professor can allow their students to listen but not download, therefore staying within the bounds of Fair-Use. Since the system contains hundreds of copyrighted music files, attention to security and allowing only authorized users access is paramount. Session control prevents unauthenticated users from linking to a web page containing audio streams. The user authentication is handled using the PHP scripting language and a mySQL database. Students are able to log on from within the campus network and listen to audio streams designated for the course in which they are enrolled. The professors are able to add and remove songs from their course page, as well as manage student accounts. The audio streaming technology being used is an open-source solution called Mp3toolbox; it is written in PHP and user agent tag checking has already been included. The security apparatus as well as additional features to provide more information to the students are the main components of this project.

Project link    Poster Link

Ryan A. Menzer

Advisor: Prof. Fernandes

Bioinformatics

In order to help predict the way proteins will act in an organism, biologists cross-examine sequences of amino acids from many proteins. There are a total of 20 amino acids in existence and proteins often consist of 300 or more amino acids. A "multiple alignment" is performed on a collection of sequences to maximize the areas where the amino acids are similar across all sequences. Online websites presently are available to accomplish the task.

Once the multiple alignment is complete, a tedious process begins of searching for contiguous subsequences of the aligned group of protein sequences that may be useful in determining properties about the proteins' functions. Subsequences that are selected for further analysis are called "primers." The primer search process is often done by hand and can take hours for small sequence lengths.

This project entails a Java program that automates the primer search process and a database organizing results obtained after primers are generated. The software allows the user to examine multiple primers at once and to adjust primer lengths. Once the primers are generated, lab tests are performed on the primers and the results are entered into a database. The database can be queried to find results that might be useful to a biologist.

Project link    Poster Link

Mark Schiebel

Advisor: Prof. Hemmendinger

Cellular Tic Tac Au-Toe-Mata

The objective of this project was to create a game based upon a cellular automaton. It also incorporates computer strategy as a 1 player mode was implement. A further goal of the project was to learn a lot about java GUI design.

Project link    Poster Link

Jason Slaunwhite

Advisor: Profs. David Hemmendinger, Gary Reich, John Hiller

Scalable Computational Methods in Quantum Field Theory

Matrix eigenvalue problems arise in several areas of science and engineering. Particle physicists, in particular, are interested in solving eigenvalue problems that describe relativistic subatomic interactions. Quantum field theory provides a formal mathematical approach for specifying the eigenvalue problems, but it also introduces some complications. A particularly problematic complication is accounting for an infinite number of particles. It is not necessary to deal practically with infinities: the system maybe truncated to a discrete number. In the case of strong coupling, however, it is inaccurate to truncate at small particle numbers. Scalable computational methods are vital to the exploration of quantum field theory since they facilitate inclusion of increasing numbers of particles.

I undertook a scalable implementation of an eigenvalue problem from Yukawa theory, a field theory model of the strong force. Effective implementation of the problem required the use of complex mathematical algorithms, optimization of the calculation, and shared-memory parallelization with OpenMP.

The computation of each matrix element and the solution of the eigenvalue problem are complex mathematical operations. Each element calculation involved numerical integration of elaborate kernels. The extraction of eigenvalues from the computed matrix required an iterative solver. Thankfully, there were several useful libraries available, such as the TNT/JAMA libraries from NIST, that facilitated implementation.

Preliminary tests of the code indicated that the computation of matrix elements took two orders of magnitude more time than finding the eigenvalues. Optimization of the code involved identifying redundant calculations in matrix element calculation. All re-used values were stored in a data structure in a canonical time-space tradeoff. The repeatedly used values were retrieved from memory instead of computed, resulting in a significant speedup.

The calculation of the matrix elements was easily parallelized. Each element was independent from all other elements, minimizing barriers and maximizing the effect of increasing the number of processors. The code was run in a shared memory environment using OpenMP on the Minnesota Supercomputer Institute's IBM SP machines. Increasing the number of processors allocated to the matrix element computation resulted in a significant speedup.

Project link    Poster Link