St. Lawrence University
Mathematics, Computer Science and Statistics Department

Travis Atkinson Approximate Confidence Interval Estimation for Biometric Identification Devices ABSTRACT: In this talk we consider methods for making a confidence interval for error rates of a biometric identification device. These devices, such as fingerprint scanners or iris scanners, are becoming increasingly prevalent. We present and evaluate four new approaches to confidence interval estimation of the matching error rates of biometric identification devices. These matching errors often follow a Beta-binomial distribution. Therefore, we propose extensions to the methodology of Agresti and Coull for the Beta-binomial distribution. We compare these methods using a Monte Carlo simulation and make recommendations for future work.

Scott P Cipriano 3D Queens Problem ABSTRACT: The well known 8-Queens Problem derives its popularity back to the famous mathematician Carl Friedrich Gauss. Gauss incorrectly claimed that he had found all the possible ways of putting 8 queens on an 8 by 8 chess board such that no queen attacks another. This problem has been extended and generalized by considering queen placements on an n by n chessboard, or the N-Queens Problem. The N-Queens problem similarly has become popular among mathematicians and computer scientists alike. The purpose of this study is to expand the N-Queens Problem a second time, into three dimensions, and answer the question: How many queens can be placed on a three dimensional chessboard?

Amy Earl  A Software Engineering Project: Using the UML and State Machines ABSTRACT: We describe a semester long software development project, as part of a software engineering course, where five students worked as a team using the UML (Universal Modeling Language) to architect and develop a concurrent, distributed, internet based version of the popular board game Clue. The UML is an industry standard graphical object-oriented software modeling language used to specify the architecture of software systems. The UML consists of several kinds of diagrams. Some of these diagrams are purely visual in nature used only to convey an intuitive feel for the structure of a software system. Other diagrams are precisely defined and grounded in theoretical computer science and mathematics. These diagrams are used to specify, unambigously, the behavior of the software system. For example, StateChart diagrams, used to specify the dynamic behavior of objects, have a mathematical definition grounded in automata theory. StateCharts also have a visual representation similar to finite state machines.

Justin C. Keller Quantum Formalisms for Static Games of Perfect Information ABSTRACT: We give a brief explanation of the implications of quantum information carriers for static games of perfect information, as well as outlining the application of two equivalent quantum formalisms. We use the Stag and Hare game as an example to show how new unique Nash Equilibria can be achieved that do not exist classically.

Katie Livingstone Modeling Disease: Mathematics in Epidemiology and Applications to the SARS Virus ABSTRACT: Epidemiological models are based on differential equations and can tell us much about how a population will react to a disease. This talk will look at how such models can help predict whether an epidemic will occur, how many people will be infected, and which intervention methods will be most effective in controlling the disease. Using the basics of epidemiology, we will examine how researchers have modeled SARS, one of the most recent global disease outbreaks.

Abhishek Parajuli Using C++ Boost Graph Library to Locate Rogues ABSTRACT: My presentation is on my honors project “Using C++ Boost Graph Library to Locate Rogues” that I am doing with Dr. Knickerbocker at St. Lawrence University. Dr. C.J. Knickerbocker, Dr. Patti Lock, and Dr. Mike Sheard have done research involving graphs that are uniquely Hamiltonian-Connected. A graph that has a unique Hamiltonian path from every vertex to every other vertex is uniquely Hamiltonian-Connected. There are certain structures that can be added onto uniquely Hamiltonian-Connected graphs to produce larger uniquely Hamiltonian-Connected graphs. These are called “rogues.” There are certain uniquely Hamiltonian-Connected graphs of the same number of nodes that cannot be constructed in this fashion, which are called “constructibles.” Dr. Knickerbocker maintains a database of uniquely Hamiltonian-Connected graphs that contain both the rogues and the constructibles without any means to distinguish them from one another. My project includes writing program(s) to separate rogues and constructibles from the database. For this purpose, I intend to use “The Boost Graph Library.” There are advanced data structures built into C++ Boost Graph Library that attempt to model graph like structures. C++ Boost Graph Library is a collection of C++ template classes that deals with graphs and the graph algorithms. In short, the honors project “Using C++ Boost Graph Library to Locate Rogues” includes implementing C++ Boost Graph Library features to write a program that identifies rogues from a collection of rogues and contructibles.

Omar F. Zaidan Heuristic Graph Coloring Algorithms ABSTRACT: This is one colorful presentation you don`t want to miss! A valid coloring of a graph is an assignment of colors to its vertices, exactly one color per vertex, such that no two adjacent vertices are colored using the same color. The Graph Coloring Problem asks us, "What is the least number of colors needed to color a given graph?" This problem is NP-complete (i.e. it is really hard), and there exist approximation algorithms (heuristics) for finding a coloring for a graph that may or may not be optimum. This project studied seven different heuristics and compared their efficiency and quality. Which heuristics are `suitable` for which types of graphs? How and why does each heuristic work? And, most importantly, which heuristic performed best, and which performed worst?

Created 4/20, 2004
Peg Barkley
Math, CS &
Stats.  Department