# Honors Thesis

The computer science major requires each student to complete a research project. Most satisfy this requirement by completing CSCI 373, but some choose to pursue an extended independent research project guided in one-on-one interaction with a faculty member. This could be a more involved paper than in CSCI 373, or it could involve completing a novel project (such as a program demonstrating the viability of a concept). The student writes a paper and gives a short presentation. In addition to the experience of working on the project, the independent project counts toward a college honors or departmental distinction designation on their degree. The experience is especially valuable for students interested in graduate study.

Though it is called an "honors thesis," students need not be part of the colleges' Honors Program to participate. Participating students are responsible for finding a thesis advisor and arranging the project. This typically occurs in the spring of the junior year, and the work continues throughout the senior year. The Web page for the CSB/SJU Honors Thesis Program contains detailed information about procedures.

Below are the descriptions of some of the past senior theses.

## 2007-2008

**Vanja Paunic**, *Creating a computer model of a lake.* Developing a model that tracks the flow of chemicals in and out of a lake which will be able to predict the concentration of the chemicals in the lake. Advisor: Michael Heroux

## 2005-2006

**Sarah Knepper**, "*Casting complex systems into equivalent real formulations (ERFs)"* Many computational science and engineering problems result in complex-valued systems of linear equations. At the same time, a large portion of equation solver software is written to solve only real-valued systems. Casting complex systems into equivalent real formulations (ERFs) enables the use of real solvers and preconditioners. Each ERF has unique properties that make it desirable in certain instances. We created a mathematical framework that permits easy conversions between different ERFs. This will allow, for instance, one ERF to be used as a preconditioner and another ERF to be used to iteratively solve the linear system by simply switching back and forth between the forms through scaling and permuting. Such transformations between ERF forms are attractive for simultaneously exploiting spectral and symmetry properties in different phases of a solver. My thesis describes the specific diagonal and permutation matrices needed as well as how to transform from one ERF to another. Advisor: Michael Heroux

**John Wilder**, "*A Machine Model for Color Constancy*" Color constancy refers to the phenomenon that our perception of a color stays constant even if the illuminating light changes composition. The current study is an attempt to make a machine vision model that correctly identifies the color of a section of a Mondrian display (a poster made of many colored sheets of paper named after the painter Piet Mondrian) regardless of the spectral composition of the illumination. We start with a discussion of previous color constancy research, with a large focus on the studies by E.H. Land (1977 & 1986). Then we discuss how well our program functions at identifying the color of a portion of the Mondrian display in photographs taken under various lighting conditions. Advisor: Lynn Ziegler

**Stephanie Mansano**, "*Abstraction and its Effects on Runtime Performance: An analysis of the Thyra package*"

Abstract interfaces support the separation of functionality from implementation, providing the ability to adapt concrete capabilities to fit the userâ€s view. This generic type of programming is the purpose of the Thyra package, which contains a number of interfaces for accessing numerical algorithms. Yet by using interfaces, we are forced to accept a certain amount of overhead added to a programâ€s run time. To help understand more about how interfaces affect performance, access to Epetra classes via the Thyra interfaces were tested against direct access to these classes. Times were collected for running a number of numerical algorithms, and the amount of overhead for specific problem sizes and algorithms were generated. Interfaces can be very useful to a programmer; however, when to use interfaces depends on how much overhead someone is willing to accept. Advisor: Michael Heroux

## 2004-2005

**Jason Cross**, "*An Evaluation of Java as a High Performance Computing Language through Jpetra: A Java Library for Distributed Memory Parallel Linear Algebra Computations*" The Java programming language and Sun Microsystems' Java Virtual Machine (JVM) provide a cross platform runtime environment that simplifies application development and deployment when compared to traditional natively compiled languages such as C++. Jpetra is a pure Java library for distributed memory parallel linear algebra computations that can be used to test the usefulness of Java as a high performance computing (HPC) language. Through my test results I will show that although Java does provide a promising platform for HPC computing, the way that Sun Microsystems' JVM is implemented makes optimizing Jpetra in a parallel environment challenging due to memory management issues. I will then provide recommendations for how I believe Jpetra should be modified to help alleviate the problems that hurt the performance of Jpetra caused by Sun Microsystemsâ€ JVMâ€s memory management. Advisor: Michael Heroux

**Joe Federer**, "*Exploring Distributed Peer-to-Peer Co-evolutionary Genetic Programming of Finite State Automata*" Genetic Programming is a branch of Artificial Intelligence which uses evolutionary theory to automatically write programs. As of 2003, only 8 people have managed to produce human-level quality programs through Genetic Programming, none of which has produced a program which competes directly and favorably with human-made programs in a head-to-head contest. My Genetic Programming project has evolved a simulated ant brain (a finite state automata machine) which competes, and wins, against other ants in the international programming contest called Ant Wars. In this contest artificial ants battle for food and survival in virtual worlds. This paper will center around the main ideas of Genetic Programming and how I was able to harness the power of evolution in order to automatically give rise to complex programs and sophisticated Ant Wars strategies. Advisor: Chris Lusena

## 2003-2004

**Ellen Alberes**. *Kruskal's Minimum Spanning Tree Algorithm: Does Partial Sorting of the List of Edges Improve Performance?* An experimental comparison of alternative implementations of Kruskal's all-pairs shortest-path algorithm.

Computer program implementations of Kruskal's MST algorithm frequently create a list of the weighted graph edges and sort the list in ascending order. My project implements Kruskal's using three sorting techniques: 1) Standard QuickSort sorts the entire list of edges. 2) Modified QuickSort adds edges to the MST as the partition process isolates subgroups of about ten of the lowest weighted edges, stopping when the MST is complete. 3) Heap Kruskal removes edges from a minimizing heap until the MST is complete.

When run on randomly generated graphs, both partial sorting techniques can have shorter run times. Modified QuickSort is faster when less than about 90% of the graph edges must be sorted. Heap Kruskal is faster when the graphs have two edge weights and less than 60% of the edges must be sorted; with 100,000 edge weights this percentage drops to 15%. Modified QuickSort yields significantly better performance than the other two techniques. Lynn Ziegler, advisor.

**Joe Athman**. *Using Distributed Computing to Improve the Efficiency of a Genetic Algorithm*. An investigation ofthe effects of distributing the processing for a genetic-algorithm solver across several computers.

This project will show that the traveling salesperson problem (TSP) will become a much more manageable problem when these two techniques are used: 1) A genetic algorithm (GA) is used to greatly speed up finding usable solutions and 2) The algorithm will be distributed to several computers to further improve the efficiency of the algorithm. Although GA's have been shown numerous times to be an extremely effective manner in finding possible solutions to NP-complete problems, there are some limitations. The major drawback to GA is the inability to guarantee that the optimal solution will be found. GA's employ a great deal of randomness which makes it impossible to say exactly how quickly the best solution will be found or even if it will be found. It is inaccurate to say that a GA solves because finding the best solution is never guaranteed. A solution in a GA is simply one possible way of solving the problem, not the best solution. Keeping in mind the limitations of GA's, the interesting part of this project is to show how distributing the algorithm can really speed up the process. J Andrew Holey, advisor.

**Tim Durnan**. *Learning-Based Artificial Intelligence Applied to a Strategic Bidding Card Game*. An implementation of a program for playing a bidding game, which can learn how to beat any opponent strategy. Carl Burch, advisor.

**Adrian Harper-Vassell**. *The Virtual Clasroom: A Fusion of Education and Computer Technology*. A software program for teaching a class via video sent over the Internet. Lynn Ziegler, advisor.

**Paul Sexton**. *Towards Optimal Usage of C++ Templates and Generic Programming Techniques*. An examination of the run-time efficiency of templates, using an adaptation of an industrial-strength matrix solver for the testbed. Mike Heroux, advisor.

**Kevin Trettel**. *Bounce Mapping: The Effects of the Range Coordinates Sharing a Greatest Common Divisor on Path Behavior in an Integer Lattice*. Mike Heroux, advisor.

## 2002-2003

**Michael Boldt**. *Improved Partitioning of Convection-Diffusion Problems*. An experimental analysis of how different ways of partitioning a space can help in solving differential equations in multiprocessor systems. Mike Heroux, advisor.

**Jennifer Dommer**. *Bioinformatics: The Effects of Sequence Length and Percent Identity on Alignments Done with CLUSTALW*. Experiments with the effectiveness of the genetic-code similarity algorithm implemented in a popular bioinformatics software package. J. Andrew Holey, advisor.

**Radhika Lal**. *The Market for Operating Systems: Is it a Penguin's Paradise?*. An analysis of how economic theories apply to the operating systems market. Jim Schnepf, advisor.

**Christopher Marsh**. *Machine Learning: Applying Reinforcement Learning to Continuous Environments*. A comparison of different methods for learning in large state spaces, using the example domain of a variant of Capture the Flag. Carl Burch, advisor.

**Jared Pangier**. *The Tension between Online Security and Efficiency in Relation to Online Business*. Noreen Herzfeld, advisor.

## 2001-2002

**Ben Franek**. *Computer Vision: Image Analysis and Recognition*. A system designed to find a hand in a picture of a person and count the numbers of fingers being held up. Carl Burch, advisor.

**Kara Hansen**. *JPetraVis: A Graphical User Interface for Matrices and Vectors*. An API for visualizing large vectors and matrices. Mike Heroux, advisor.

**Abnita Munankarmy**. *A Comparison of Two Equivalent Real Formulations for Complex-Valued Linear Systems*. An experimental analysis of differing techniques for solving systems of linear equations over complex numbers using programs designed for linear systems over real numbers. Mike Heroux, advisor.

**Rebecca Schafer**. *Protecting Brand Image: A Web Based Trademark Surveillance Application*. An investigation of using a specialized Web spider to locate trademark violations. Carl Burch, advisor.

## 2000-2001

**Nicholas Charboneau**. *Voice Interactive Events Calendar at the College of Saint Benedict/Saint John's University: A Feasibility Study Using VXML*. A comparison of the effectivity of voice information retrieval (with a telephone interface) relative to visual information retrieval (with Web pages). Carl Burch, advisor.

**Kris Kampshoff**. *Parallel Sparse Matrix Computations on Beowulf Clusters*. An investigation of scientific computation on parallel computers with a mix of processor speeds. Mike Heroux, advisor.

## 1999-2000

**Kristopher Glesener**. *Applying Machine Learning Algorithms to Othello*. J. Andrew Holey, advisor.

**Courtney Remes**. *Rethinking Consciousness, Objectivity, and the Potential for Artificial Intelligence*. Noreen Herzfeld, advisor.

**Cody Zilverberg**. *Design and Creation of a Dynamic Homework System*. Jim Schnepf, advisor.

## 1998-1999

**Karen Jakubowsky**. *Metaphor and Understanding: The Work of Lakoff and Johnson and Natural Language Processing*. Noreen Herzfeld, advisor.

## 1997-1998

**Peter Lindquist**, *Data Mining in Electronic Media Usage Statistics: A Case Study of Knowledge Discovery in Databases*. Jim Schnepf, advisor.

**Hans Mersinger**. *Heraldry and Programming Languages: the Complexity of Natural Languages Examined through the Parsing of the Heraldic Blazon*. John Miller, advisor.

**Nathaniel Schutta**. *The Impact of Technology on Special Education Students*. Jim Schnepf, advisor.

## 1996-1997

**James Beach**. *The Effects of Network Latency on Multimedia Applications* Jim Schnepf, advisor.

**Joshua Flynn**. *The Use of Prime Numbers as an Effective Method of Cryptology* Jennifer Galovich, advisor.

**Brooke Frost**. *Object-Oriented Development in Creating Software Systems* J. Andrew Holey, advisor.

**Paul W. Jones**. *Genetic Algorithms: A Visual Search* Michael Gass, advisor.

**Julie Klinefelter**. *How Secure Transactions are Achieved on the Internet using SSL: An Honors Presentation of Internet Security Practices and Protocols* Jim Schnepf, advisor.

**Ben Knuth**. *Semantic Analysis of the Postscript Page Description Language* J. Andrew Holey, advisor.

**Aaron Ziegler**. *Simulation of Living Processes Utilizing Concurrency and Object-Oriented Programming* J. Andrew Holey, advisor.

## 1995-1996

**Michael Criswell**. *Using Genetic Algorithms to Solve the Geometric Traveling Salesperson Problem*. Michael Gass, advisor.

**Mitch L. Hamelau**. *An Examination of Virtual Reality Modeling Language and its Implications for the Future of the World Wide Web*. J. Andrew Holey, advisor.

**David Weinandt**. *Researching the Growing Technology of Virtual Reality*. John Miller, advisor.

## 1994-1995

**Mara Zell**. *A Knowledge-Based Approach to Class Scheduling*. Daniel Challou, advisor.

## 1992-1993

**Eric Gronholz**. *Monitoring Shared Memory: A Toolset Prototype for the INFORMIX OnLine Administrator*. Lynn Ziegler, advisor.