Title:
A Teaching Tool for Computer Graphics

Author:
Huiling Yang

Date:
January 1998

Abstract:
The project consists of two teaching tools for polygon clipping and two dimensional transformation. In the polygon clipping teaching tool, the user can observe the (partially) clipped figure and the numerical results after each step. From the two dimensional transformation teaching tool, the user can compare the figures before and after translation, rotation or scaling and view the changes in the composite transformation matrix. Multiple transformation and rotation or scaling about an arbitrary point may be also explored. Both tools have a Help button and a Bckg button for getting the theoretical background information.

e-mail: hxy8630(at sign)cs.rit.edu

Visit project's home page.

Committee:
Prof. Nan C. Schaller, Chairman
Dr. Peter G. Anderson, Reader
3, Observer


Title:
Soccer Tournament Scheduling Using a Genetic Algorithm

Author:
William T. Gustafson

Date:
May 1998

Abstract:
This project involved implementing a genetic algorithm to generate a schedule for a Soccer Tournament. The project serves two purposes: to be a Master's Project involving the study of genetic algorithm; and to be a product, deliverable to the Chili Soccer Association, used to schedule its annual travel soccer tournament.

The scheduling of a tournament is a classic job scheduling application with its own unique problems. The goal in using a genetic algorithm is to produce a schedule in a reasonalbe amount of time that satisfies numerous hard and soft constraints. This goal was successfully accomplished by breaking the problem down into smaller sub-problems and adding scheduling intelligence to the program. This involved a greedy approach to converting individuals in the population space into schedules.

Committee:
Dr. Peter G. Anderson, Chairman
Prof. J. A. Biles, Information Technology Department, Reader
Dr. Walter A. Wolf, Observer

Title:
Optical Character Clustering,

Author:
Jennifer Greenwald

Date:
February 1998

Abstract:
My area of interest is clustering, specifically using GA's and neural networks, as applied to the problem of optical character categorization.

This problem I intend to investigate is this: in the area of optical character recognition (OCR), systems are in place which are capable of doing an adequate job of recognizing text they have been trained for. However, generating training data for these systems (most often based on neural networks) is time consuming and expensive, as it currently requires a human operator to sort through thousands of character samples and tag each one with the character it represents. This project proposes some preliminary proof of concept work for a method which could help drastically reduce the amount of human effort involved in tagging this training data.

The idea is to pre-sort the sample characters to be tagged. Hopefully, once the characters to be tagged are grouped into like sets, the human operator can label them all at once, fixing only a few incorrectly classified samples by hand. In a best case scenario, sets of characters which have been clustered together can be put on the screen for an operator all at once, sorted in order of percentage correlation.

I will investigate using the K-means algorithm, a genetic algorithm and a Kohonen neural network to cluster characters. Each of these methods has shown success in clustering other, simpler data. I will compare the success of each method, and attempt to determine which is the quicker and the more accurate.

Visit the project home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Stanislaw P. Radziszowski, Reader
Dr. Fereydoun Kazemian, Observer


Title:
Hu-Tucker Algorithm for Building Optimal Alphabetic Binary Search trees

Author:
Sashka Davis

Date:
December 1998

Abstract:
The purpose of this project is to design and efficiently implement the Hu-Tucker algorithm for building optimal alphabetic binary search trees. My intentions are to design at least two implementations of the algorithm and compare their break even point as a function of the input size. It will contain three major sections: theoretical, implementation, and experimental.

The Introduction section will present the statement of the alphabetic tree problem, and related definitions. Discussion of the two algorithms for building prefix codes - Huffman, which builds optimal prefix code and Hu-Tucker and Garsia-Wachs algorithms which also build an optimal prefix code but the resulting binary tree is an alphabetic search tree.

The goal of the presentation is to justify the price that is paid in building an optimal alphabetic search tree following the complicated Hu-Tucker algorithm as opposed to the simple optimal binary tree in the case where the compression is applied to very large alphabets.

The Theoretical section will provide an overview of the existing algorithms for construction of optimal alphabetic search trees. They will be compared and evaluated based on their theoretical time and space complexities. This analysis will be used to select the data structures for an efficient implementation of the Hu-Tucker algorithm for building optimal alphabetic search tree.

e-mail: std3246(at sign)cs.rit.edu

Visit project's home page.

Committee:
Dr. Stanislaw P. Radziszowski, Chairman
Dr. Peter G. Anderson, Reader
Dr. Andrew T. Kitchen, Observer

Title:
Sequential segmented video capture for file integration,

Author:
Manisha Mande

Date:
May 1998

Abstract:
Sequential Segmented Video Capture for File Integration or Build Job in short, is a unique Fax feature that allows the user to scan multiple segments of a single job on a multi-function machine, such as the Xerox Document Center, with each segment having unique settings for the following features:

Image Quality (Text, Photo, Auto),

Resolution (Standard, Fine, SuperFine) and Density (Lighter/Darker).

Operability allows for a pause between segments, while the operator loads the next set of originals and optionally changes the mentioned job feature settings.

The result is a fax job with a variety of segments which form a single document output. This feature allows images from the platen to be combined with images from the Document Handler into a single job for faxing. The user must select the Build Job feature prior to scanning each input segment. An input segment is either:

Output of the fax job does not occur until the last input segment of the job has been identified by the user and has been captured. Documents are to be scanned in the order that they are to appear in the output set (1 - N order). For the first segment, the user may set the density (lighter/darker), image quality (photo, text, auto etc) and the resolution (standard, fine, super fine) for the documents to be scanned in. Once the first segment has been scanned in, the user is then allowed to change the scanning source (platen or Document Handler), density, image quality and resolution for each subsequent segment. The user is explicitly provided the ability to indicate the end of Build Job so that he may request faxing or filing to begin.

User Input(s)

User Output(s)

Committee:
Prof. Timothy P. Wells, Information Technology Department, Chairman
Dr. Peter G. Anderson, Reader
Dr. Walter A. Wolf, Observer

Title:
Document Image Orientation

Author:
Herb Chapman

Date:
May 1998

Abstract:

Orienting document images can be a valuable step in a document processing system. This capability eases the document preparation process, and allows other processing steps to expect images in a known orientation. This project addresses document image orientation by concentrating on the text appearing in the document.

This system will capture characters from a scanned document, and attempt to recognize the characters and their orientations. The recognition will be performed by Optical Character Recognition (OCR) Neural Networks (NNs). Several systems will be configured by training a variety of NNs. The relative performance of each configuration will be evaluated.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Roger S. Gaborski, Eastman Kodak, Reader
Mr. John D. Hanson, Eastman Kodak, Observer


Title:
The extended Chinese editor

Author:
Xin Guo

Date:
April, 1998

Abstract:
This project extends Novey Yu-lan Chou's ChineseEditor application in order to make it more efficiently usable. The first major extension introduces a solution to make the phonics character set and the radical character set consistent. This includes discovering the major cause for the inconsistency between the phonics character set and the radical character set, modifying the current ChineseEditor design, and extending the character set searched by phonics and the character set searched by radicals. For ease-of-use and quick editing, the second extension allows a user to create a customized character set for his/her own purpose on the fly. This part involves creating a set of new Java classes in the overall application structure and restructuring the relationship among the classes.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Lawrence A. Coon, Reader
3, Observer


Title:
Factoring Integers

Author:
Jingyan (Cathy) Fu

Date:
May 1998

Abstract:
This two part project contains a web access tool system for the application factorization programs and a research reports of the performance of different software packages using various factorization and primality proving algorithm.

Gather existing software packages related to factorization and prime number study and integrate them into a convenient, user friendly system, create a web site so the others can use them as a tool for a quick factorization of numbers in small to medium range.

Factoring is a very active field of research among mathematicians and computer scientists. It is believed to be a very difficult mathematical problem and a lot of algorithm has been developed to speed up the factorization process. Because of the complexity of the algorithm used in factorization, different method is usually most efficient for a specific kind of factoring process. The second part of my project involves a systematic analysis of the performance and efficiency of different algorithms from the software packages I collected from the first part.

Visit Cathy's home page.

Committee:
Dr. Stanislaw P. Radziszowski, Chairman
Dr. Peter G. Anderson, Reader
3, Observer


Title:
A Multiprecision Integer Package

Author:
Norm Moulton

Date:
August 1998

Abstract:
In some areas of Computer Science, integer math must be performed using very large numbers. For these applications, the standard integer or long integer types available in standard programming languages don't have the required range, and the standard floating point packages don't have the required precision. What is required is a special package that provides operations on very large integers in the range of hundreds or thousands of decimal digits.

Visit project's home page.

e-mail: nwm5049(at sign)rit.edu
Committee:
Dr. Stanislaw P. Radziszowski, Chairman
Dr. Peter G. Anderson, Reader
Prof. Karen A. Atkinson, Observer


Title:
JavaSQL: A homogeneous distributed database management system

Author:
Yu-I Tseng

Date:
January 1998

Abstract:
In the past several years, the growth of multimedia applications has been made possible by increasing the power of desktop workstations capable of displaying multimedia data (e.g., text, images, graphics, audio, video, etc.). Despite the fact of increasing the PC workstation's processing power, some limitations prevent the massive deployment of multimedia applications, namely:


- insufficient storage capacity of a single workstation (audio, video, and graphics require a huge storage space compared to conventional data)
- difficulty in storing and sharing multimedia data in a manner offered by database management systems (security, data integrity, locking, multi-user access, etc.)
- incompatibility between storage systems used on different workstations

These problems become even bigger with the need to develop big multimedia inform information systems for huge companies comprising of multiple physically dislocated subsidiaries. Such companies demand one logical database with data spread across all the locations.

The primary objective of this project is to implement a homogeneous distributed database management system (DDBMS) called JavaSQL. The implementation of JavaSQL is to be solely programmed in JAVA, a high level language developed by Sun Microsystems, Inc. The JavaSQL DDBMS is designed to run on an Intranetworking environment, which allows people to use a mixture of hardware and operating systems. It offers location transparency, partition transparency, distributed data manipulation, distributed query optimization, and portability.

e-mail: yxt0376(at sign)cs.rit.edu

Visit project's home page.

Committee:
Dr. Andrew T. Kitchen, Chairman
Dr. Stanislaw P. Radziszowski, Reader
Dr. Peter G. Anderson, Observer


Title:
Parallel Neural Network Training Based on Gradient Descent Optimization

Author:
Sean Strout

Date:
TBA

Abstract:
Every training algorithm in neurocomputing uses a non-linear optimization to adapt internal weights. This is because the activation function for an artificial neuron is required to be continuously differentiable and asymptotically convergent to horizontal lines[LF94]. Furthermore, this non-linear optimization is performed across every unit (potentially on the order of hundreds of thousands) within the network, so all but the simplest techniques must be precluded.

The standard algorithm in backpropogation networks uses a sigmoid activation function with a gradient descent optimization procedure [RHW86]. This technique is known to present absolute convergence problems when presented with many local extrema. Consider an N dimensional hypersurface, the convergence of the gradient descent algorithm to any one extrema will depend greatly on the local basins of attraction around the starting point [ABE92].

One potential way around this problem, known as simulated annealing, sets the gradient descent step to a high value, and steadily decreases the step as the algorithm progresses through successive iterations of the training data. This method is effective in avoiding the lesser extrema, but does not assure convergence with the optimal basin and absolute minimum extrema for the hypersurface.

For my Masters Project, I propose to work with Dr. Alejandro Engel of the RIT Mathematics Department on his studies of modifications to the gradient optimization procedure and activation function. The purpose of this project is to find variations that minimize the training time while insuring the integrity of the net output. When the network is presented with previously unrealized data sets, the neurocomputer should be able to correctly identify the expected output.

Deliverables:

(1) Development of a software package to simulate neurocomputing. This software must be flexible enough to allow for changes in the following areas using the standard Backpropogation algorithm:

- Optimization Procedure: gradient descent, Powell's Algorithm [MJP64], Conjugate Gradients [FR64], etc.

- Activation Function: binary sigmoid, bipolar sigmoid, hyperbolic tangent , etc. Other areas for potential investigation for training optimization are:

- Weight/Bias Initialization: random, Nguyen-Widrow, etc.

- Training/Weight adjustment method.

- Gradient step procedure: static, simulated annealing, etc. (2) Write up containing discussions on the techniques used and the observed behaviors.

References:

[ABE92] A.B. Engel "Non-Linear Processing in Artificial Synapses" KYBERNETES 21 (1992) 35-45.

[LF94] L. Fausett "Fundamentals of Neural Networks: Architectures, Algorithms and Applications" Prentice-Hall (1994).

[FR64] R. Fletcher and C.M. Reeves "Function Minimization of Conjugate Gradients " Computer Journal 7 (1964) 149-154.

[MJP64] M.J.D. Powell "An Effective Method for Finding Minimum of a Function of Several Variables Without Computing Derivatives" Computer Journal 7 (1964) 152-1 62.

[RHW86] D.E. Rumelhart, G.E. Hinton and R.J. Williams "Learning Internal Representation by Error Propagation" in Rumelhart & McClelland (eds). Parallel distributed Processing, MIT Press (1986).

e-mail: strout(at sign)ppdev.mc.xerox.com
Committee:
Dr. Alejandro B. Engel, Mathematics Department, Chairman
Dr. Peter G. Anderson, Reader
Dr. Stanislaw P. Radziszowski, Observer


Title:
An Automated Content Assembler and Notifier

Author:
Pushpa Gogineni

Date:
January 1998

Abstract:
An Automated Content Assembler and Notifier is a subsystem of DRLINK system. DRLINK is a natural language text Retrieval system that allows searchers to state queries as fully-formed sentences and to specify the requirements for document retrieval and ranking. Through DRLINK web interface, users can save, delete, temporarily deactivate and update their favorite queries. Alert queries are stored and maintained at the server.

The goal of Content Assembler and Notifier subsystem is to notify the user periodically with the updated information on the Alert query.

This subsystem checks periodically, if there is any match for the new content that is being added to the content server against the alert queries. When there is a match, user will be notified via e.mail with the saved query header and related content information. Users can login to drlink through web browser at any time to see the saved Queries and related content information.

Primarily this project is divided into two phases.

First phase is to design the project using Object-Oriented design Patterns. These specific Design Patterns make object-oriented designs more flexible, elegant, and reusable. Second phase is to implement the design specifications using c++.

Benefits of undertaking this Project

To gain more experience in designing and implementing reusable and flexible code. To automate the complete process.

Bibliography:

Design Patterns - Elements of Reusable Object-Oriented Software;
Erich Gamma, RichardHelm, Ralph Johnson, John Vissides Addison Wesley.

e-mail: pushpa(at sign)textwise.copushpa(at sign)textwise.com

Committee:
Mr. Arvind Srinivasan, Chairman
Prof. Timothy P. Wells, Information Technology Department, Reader
Dr. Peter G. Anderson, Observer


Title:
Survey of Two Distributed Middleware Environments: JAVA RMI vs. Distributed COM

Author:
Henry Cho

Date:
January, 1998

Abstract:
The purpose of this project is to design and implement a rudimentary client-server application that takes advantage of two recently developed middleware environments for distributed applications: Java's Remote Method Invocation (RMI) and the Distributed Component Object Model (Distributed COM, or just COM). Development of this application will allow a comparison of the two environments in two areas: performance (how long does it take a call to a service to complete?) and ease of implementation (how long does it take to develop client server software in the two environments?).

The kind of client-server application that will be implemented is arbitrary; it is only meant to compare the two environments in the areas listed above. The application will consist of one client that can request services from two different servers, one implemented as a Java RMI server and the other implemented as a COM server. The interfaces to these two servers will be dictated by the distributed environment that each is developed for. Therefore the client will need to be able to use the appropriate interface for requesting services from each server and make the appropriate calls defined in each environment to gain access to the remote client and its services. Since the actual application implemented is arbitrary and is only meant as a means of comparison, the service(s) provided by the servers need only be the same service(s). The service I propose is simply to return the system time on the computer on which the server is running.

Committee:
Prof. Michael J. Lutz, Chairman
Dr. Paul T. Tyman, Reader
Dr. Peter G. Anderson, Observer

Title:
D2 Network Monitor

Author:
Diane Duda

Date:
April, 1998

Abstract:

This application is a graphical monitor to help monitor a network. It allows the user to input a name and Inet Address of a node on the network and displays a computer icon on the main screen to represent the node. When all nodes have been entered, the monitor "watches" the nodes and reports to the user when one of them goes off-line or crashes (i.e. somehow becomes disconnected from the network where other nodes are not able to recognize it anymore). The following functions have been implemented in the D2 Network Monitor: Exit, Configure, Check Network, Monitor Network, About, and Help.

If I were to continue this project, the next features I think should be implemented are: Select a Node, Edit or Delete a Node, Save a session, and Import a Session. I was thinking about removing the "Convert To" feature all together.

This Master's Project was created to allow me to learn the Java Language and to become more familiar with Networking.

Committee:
Dr. Walter A. Wolf, Chairman
Dr. Peter G. Anderson, Reader
Christopher Daughton, Observer

Title:
Fractal Music and Images

Author:
Michael A. Lepore

Date:
January 1998

Abstract:
The project involves the development of a Java applet that generates music based on fractal formulas. In particular, the Mandelbrot and the Julia sets will be used to determine if music can be generated that is as beautiful as the images these sets create. To attempt to preserve the complex nature of these sets, the real and imaginary parts of the complex numbers will be applied to appropriate music parameters, such as pitch and volume. The user will be presented with an interface to vary several parameters in order to change the music that is produced. These parameters will include the selection of fractal type and application of the fractal to musical parameters such as key, tempo, and scale type. The music will be played on the client machine using MIDI format. The applet will also present a visual representation of the fractal being used, or possibly a gallery of images. The fractal images will be generated by code written in Visual J++ and may also include some three-dimensional images that include shading and ray-tracing. The image part of the project is being done for an advanced computer graphics class.

Visit the project page.

Committee:
Prof. J. A. Biles, Information Technology Department, Chairman
Dr. Peter G. Anderson, Reader
Prof. Michael Eastman, Engineering Technology, Observer

Title:
A File Format Based on Linear Pixel Shuffling

Author:
Jenny K. Pan

Date:
January 1998

Abstract:
There is a saying of "graphics file formats are immortal." Many kinds of graphics file formats have been in the market already, such as TIFF, GIF, JPEG etc., nevertheless, we always need a way to create a better ones and always need a way to read, understand, and display them.

Dr. Anderson has been doing research work on LPS (Linear Pixel Shuffling) theory for many years and he would like to implement his theory to a LPS Image (Graphics) Format, including LPS compression algorithm which is implemented by Elaine Meadows.

In my project, the following specs will be implemented:

(1) An html file invokes a Java applet file that brings out an ImageViewer frame.

(2) From the ImageViewer frame, the user may choose to open a GIF image file as original file or LPS image file with desired percent image shown.

(3) The user may save the image as a regular GIF file or in the LPS file format.

(4) This converter (display) project is implemented in JAVA and HTML and is able to displayed on WWW.

(5) The LPS converter will handle bilevel, monochrome, and color images.

Visit Jenny's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Stanislaw P. Radziszowski, Reader
3, Observer

Title:
System Topologies for Parallizing Genetic Algorithms

Author:
Peter Gousios

Date:
TBA

Abstract:

Genetic algorithms (GA) allow for automatic searching of a solution space without program knowledge of the problem being solved. Genetic algorithms are easy to implement on parallel machines. Many methods of parallel genetic algorithms (PGA) have been experimented with.

Coarse grained parallel genetic algorithms distribute sub-populations among the different computing elements. The sub-populations can be connected in a variety of different topologies. To efficiently solve a problem, knowledge of how the topological arrangement effects a genetic algorithms can be used to optimize the algorithms performance.

This paper analyzes the effects of changing the topology of the computing elements. Analysis of diameter, and connections per node are made. Performance is evaluated independently of the test system. The influence of communications cost and processing cost on selecting a topology is examined. Multiple problems are tested to eliminate single problem bias.

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Stanislaw P. Radziszowski, Reader
Prof. J. A. Biles, Information Technology Department, Observer

Title:
An Illustration of Color Mixing Principles using Java.

Author:
John A. Moore

Date:
April 1998

Abstract:

Java will be used to implement an applet, ColoRama, for demonstrating basic color mixing principles. At a minimum, this applet will allow a user to:

  1. Precisely define three primaries using RGB slider controls.
  2. See the resulting color gamuts for the selected primary set for both additive and subtractive color mixing.
  3. Use the mouse to pick a color from the gamut display and show the corresponding ratios of each primary required to produce the selected color
  4. Define a precise amounts of each primary for mixing and view the resulting color through visual mixing

In addition to gaining experience with JAVA graphics, color and imaging, the AWT (abstract windowing toolkit) will be used to implement a platform independent user interface. The report will include a discussion of the effectiveness of the implementation and performance of the applet on different platforms.

Visit the ColoRama project homepage.

e-mail: jmoore(at sign)mc.xerox.com

Committee:

Prof. Nan C. Schaller, Chairman
Dr. Peter G. Anderson, Observer
Dr. Mark Fairchild, Center for Imaging Science, Reader

Title:
BackPropagation Neural Experimentation Laboratory and Real Time Neural Training Application

Author:
Alex Miller

Date:
April 1998

Abstract:

Developing a training set and optimizing a neural network can be a difficult and time consuming task for anyone. By developing a program that allows for flexible control and ease of use in developing a multilayer feedforward neural network, this task can be, in fact, enjoyable and enlightening. Observing the internals of a neural network during training sessions is surprisingly interesting. By giving the user dynamic control of the various aspects of the network and providing useful visual aids, optimizing a neural network to a set of training data is a simple and quick exercise. Also, a deep understanding of the algorithm can be understood through the use and manipulation of such a tool.

Deliverables:

(1) Development of a software package to implementing, specifically, the feedforward multilayer Backpropogation neural network with visualization facilities. This software will have the following features:

- The ability to create and dynamically change a multilayer feedforward neural network with up to 35 inputs, 35 hidden units and 35 output units.

- The ability to change the number of hidden units "on the fly" during training and execution of the neural net.

- The abitity to change the learning rate and stopping tolerance values "on the fly" during training and execution of the neural net.

- The provision of a graph showing the network weights changing in real time during the training of the neural net.

- The display of training statistics in real time.

- The ability to save the network weight data out to an ascii file for later usage in other applications.

- A Strip Chart showing network input and output values as well as input layer and output layer weight values during training for a visual understanding of the learning process and internal behaviors of the network.

- A visual representation marking discrete moments for individual training pattern cycles as well as entire training file cycles.

- The ability to run pseudo-random input values through a trained/untrained/semi-trained network in order to visualize and understand a networks output behavior under "noisy" conditions.

(2) Development of a graphical application for a vehicle control system that optionally reads and uses networks from the above application or learns in real time via user input. The control system will allow the vehicle to negotiate obstacles in a 2-D environment and display neural actively in graphical form for analysis.

References:

[LF94] L. Fausett "Fundamentals of Neural Networks: Architectures, Algorithms and Applications," Prentice-Hall (1994).

e-mail: Alex_Miller(at sign)wb.xerox.com

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Stanislaw P. Radziszowski, Reader
3, Observer

Title:
3D Object Modeling Using Splines

Author:
Kevyn Ford

Date:
January 1998

Abstract:
Three dimensional object modeling is a crucial step in the design and construction of computer-based objects. These objects can be used to simulate real-world objects found in CAD/CAM systems or can be completely synthetic as those found in a raytraced scene. One technique used in complex object modeling is the use of splines to represent object surfaces. This project investigates the use of splines as a three dimensional modeling tool and presents a spline-based modeler (Smodeler) that generates objects compatible with the freely available POVRAY raytracing system.
e-mail: kevyn_ford(at sign)smb.com

Visit project's home page.

Committee:
Prof. Nan C. Schaller, Chairman
Dr. Andrew T. Kitchen, Reader
Dr. Peter G. Anderson, Observer

Title:
Evaluation of Subdivision Methods used in Octree Ray Tracing Algorithms

Author:
Scott Brown

Date:
February, 1998

Abstract:

The non-uniform spatial subdivision technique refined by Andrew Glassner minimizes facet intersection tests (i) by automatically generating a density dependent spatial hierarchy of facet regions (called an ``octree'') and (ii) by only testing facets in regions along the path of the ray. Past research has addressed optimization of the octree ray tracing process by separately improving both the octree traversal method and facet intersection algorithms. This author attempted to further improve the overall approach by attempting to identify new octree construction methods that would decrease the number of traversals required to render the scene.

This research focused on the subdivision technique used in constructing the octree. The conventional Glassner algorithm utilizes cubic octants that can result in a large population of empty octants when using scenes significantly smaller in one or more dimensions. Sparse octrees (containing significant numbers of empty octants) were believed to hinder performance of the facet traversal algorithm. As an alternative to the conventional cubic algorithm, the performance benefits of non-cubic octants were investigated. Octrees constructed with ``rectangular'' octants which more closely bound the scene were tested as one alternative to the cubic octants method. As a second alternative, this author proposed and implemented an ``ideal-cut'' subdivision algorithm that subdivides the parent octant through the mean location of the facets contained in the octant.

e-mail: sdbpci(at sign)cis.rit.edu

Committee:

Prof. Nan C. Schaller, Chairman
Dr. Peter G. Anderson, Reader
Dr. Stanislaw P. Radziszowski, Observer

Title:
A Simulation Module of UNI Signaling

Author:
Weixiang Chen

Date:
May 1998

Abstract:

Deliverable

Implement a simulation module of UNI Signaling Stack which includes Basic functionalities of point to point and point to multipoint connections. The messages used for setting up or releasing connections and the state machines on both user side and network side are designed based on ATM User-Network Interface Specification, version 3.0/3.1. Call controls are handled with reasonable robustness.

Interfaces

A main driver with an operation menu, which allows you to specify the Test cases, would be given to start the corresponding tests with UNI Signaling Stacks. The test cases briefly include normal connections setup and release. The negative cases are also going to be given to see the robustness and if the stack works correctly. We might observe the print outs showing the setup and release flows of connections. The signaling stack implemented interfaces with the dummy application layer (the layer above) and the dummy data link layer(the layer below); it also interfaces with layer management which provides the functions to control, monitor, initialize or modify layer configurations(figure 1).

There are two types of messages are involved in this project. One is the messages used between user and network. This kind of message includes Setup, Call Proceeding, Connect, Connection Acknowledge, Release and Release Complete. The second type of messages is used for communication between different network layers. This kind of message includes Configuration Request, Bind Request, Connect Request, Connect Status Indication, Connect Confirm, Data Request, Data Indication, Connection Indication, Connect Response, Release Request, Release Indication, Release Response, and Release Confirm. The first type of messages are being sent via various Request and Response messages from upper layer to lower layer, various Indication and Confirm messages from lower layer to upper layer. The Configuration Request and Bind Request are used with other request messages to configure the system and SAPs (Service Access Pointer) at different layers during the startup period. The SAPs are used for signaling stack to communicate with its upper and lower layers. The state machines work very closely with those messages. An incoming message is an event to the state machine. Based on the incoming event, the state machine takes the actions and goes into next state accordingly. Figure 2 is the data flow for successfully establishing point-to-point connections between source and destination. Figure 3 shows point-to-point call release procedures.

e-mail: wchen(at sign)ascend.com
Committee:
Dr. Walter A. Wolf, Chairman
Dr. Peter G. Anderson, Reader
3, Observer

Title:
The extended Chinese editor.

Author:
Xin Guo

Date:
April 1998

Abstract:
This project extends Novey Yu-lan Chou's ChineseEditor application in order to make it more efficiently usable. The first major extension introduces a solution to make the phonics character set and the radical character set consistent. This includes discovering the major cause for the inconsistency between the phonics character set and the radical character set, modifying the current ChineseEditor design, and extending the character set searched by phonics and the character set searched by radicals. For ease-of-use and quick editing, the second extension allows a user to create a customized character set for his/her own purpose on the fly. This part involves creating a set of new Java classes in the overall application structure and restructuring the relationship among the classes.

e-mail: xxg4593(at sign)cs.rti.edu
Committee:
Dr. Peter G. Anderson, Chairman
2, Reader
3, Observer

Title:
Image Manipulation System

Author:
Mary Abraham

Date:
April 1998

Abstract:

The explosion of digital technology has given rise to the need to store and manipulate digital color images. Companies involved in such activities as: visual effects, multi-media, printing and publishing, and medicine rely on software to manipulate digital images.

Today's students need to understand how color images are represented and manipulated to obtain the desired effect. Therefore, I have created an educational image viewer geared toward students beginning to learn about digital color representation and image processing. This project provides a supplement to the current methods for learning.

e-mail: who(at sign)who.who

Visit project's home page.

Committee:
Prof. Nan C. Schaller, Chairman
Dr. Peter G. Anderson, Reader
3, Observer

Title:
Parallel Genetic Algorithms Three Implementations and Their Analysis

Author:
Daniel Pedersen (Department of Computer Engineering)

Date:
May 1998

Abstract:

Although solutions to many problems can be found using direct analytical methods such as those calculus provides, many problems simply are too large or too difficult to solve using traditional techniques. Genetic algorithms provide an indirect approach to solving those problems. A genetic algorithm applies biological genetic procedures and principles to a randomly generated collection of potential solutions. The result is the evolution of new and better solutions. Coarse-Grained Parallel Genetic Algorithms extend the basic genetic algorithm by introducing genetic isolation and distribution of the problem domain.

This thesis makes a comparison of solution strategies using a serial genetic algorithm and three coarse-grained parallel genetic algorithms (a standard parallel algorithm, a non-uniform parallel algorithm and an adaptive parallel algorithm). The evaluation is done using the well-known Traveling Salesman problem ATT48 from TSPLIB95. It is shown that while the standard course-grained parallel algorithm provides more consistent and better results than the serial genetic algorithm, the adaptive algorithm out-performs them both. To facilitate this analysis, an extensible object-oriented library for genetic algorithms encompassing both serial and coarse-grained parallel genetic algorithms was developed. The Java programming language was used throughout.

e-mail: DPeder01(at sign)harris.com

Visit project's home page.

Committee:
Dr. Muhammad Shaaban, Computer Engineering Dept., Chairman
Dr. Peter G. Anderson, Reader
Dr. Roy S. Czernikowski, Computer Engineering Dept., Observer

Title:
Internet Search Engine

Author:
Aleksey Afanasyev

Date:
May 1998

Abstract:
When the size of the Web increased beyond a few sites and a small number of documents, it became clear that manual browsing through a significant portion of the hypertext structure is no longer possible. It led to the invention of an effective method for resource discovery: a search engine. A search engine is a program that accepts queries through a user interface, consults the index, and returns a list of relevant results to the user. The purpose of my MS project will be to design and implement a Internet search engine.

The search engine will consist of four major elements: spider, index, retrieval program, and interface. The spider visits a web page, reads it, and then follows links to other pages within the site. Everything the spider finds will go into the second part of a search engine, the index, a giant book containing a copy of every web page that the spider finds. The retrieval program sifts through the pages recorded in the index to find matches to a search and rank them in order of what it believes is most relevant. The interface defines how the search engine appears in front of users. The robot will support the standard for Robot Exclusion and it will be applied mostly to the local sites. The implementation language for the project is Perl.

e-mail: ava2675(at sign)cs.rit.edu

Visit project's home page.

Committee:
Dr. Andrew T. Kitchen, Chairman
Dr. Peter G. Anderson, Reader
3, Observer

Title:
Intranet application for shelf life

Author:
Glen DeFranco

Date:
Month? 1998

Abstract:

There is a complex relationship between produce shelf-life, storage temperature and the material composition of the products package. Shelf-life can be extended simply by lowering the storage temperature. However, produce is often packaged in a lamination of breathable plastic films. These materials have different properties that can be used to further enhance the shelf-life of the product. The rate at which Oxygen can pass through these materials also varies according to the temperature, making the interaction of these three variables difficult to determine.

A program that could aid professionals involved in the transportation or storage of produce, or the design and testing of their packages would be quite useful. This program is meant to fill that need. It is not intended to determine the best package design, but rather to evaluate and test existing packages and to give the user the ability to instantly see the effects that changes to one or more of their input will have.

The program developed is an interactive intranet application designed to reside on a company web server, thereby allowing easy access by all employees without the need to install additional software. The central database of materials and products is designed to allow users to share some information while giving them a private workspace where they can add their own materials and products.

The application integrates web pages, forms, Java Applets, client-side JavaScripts, client-side VBScripts, server-side VBScripts and database access and manipulation to seamlessly communicate with the user as if they were running a locally installed executable.

e-mail: gad9679(at sign)cs.rit.edu

Visit project's home page.

Committee:
Prof. John A. Biles, Information Technology Dept., Chairman
Prof. Fritz Yambrach, Packaging Science Dept., Reader
Dr. Fereydoun Kazemian, Observer

Title:
Parse Tree Browser

Author:
Rich Walvoord

Date:
May 1998

Abstract:
Any string belonging to a language described by an unambiguous context-free grammar can be represented by a single parse tree. The parse tree then represents the syntactic structure of the string. Deriving this parse tree from the given string is primarily the task of a language compiler. First, it must be verified that the string is a valid element of the language. Secondly, the syntactic structure dictates the semantic meaning of the string

While the parse tree plays a central role in program compilation, it is largely invisible. In the larger scheme of program development, a program's parse tree is merely an intermediary representation between source and executable, useful only to the translation process. As an aid to close examination and understanding, however, it is very instructive.

It is the purpose of this project to develop a tool to construct the parse tree for a given program and grammar, and allow the user to examine that tree interactively, selecting non-terminals to be expanded for in-depth understanding. A number of small languages will be built-in, drawn primarily from the Tiny Language System collection used in study of programming language theory. In addition, an arbitrary BNF grammar may be entered for examination of non-standard language constructs.

e-mail: rwd8666(at sign)cs.rit.ed

Visit project's home page.

Committee:
Dr. Andrew T. Kitchen, Chairman
Dr. Fereydoun Kazemian, Reader
Dr. Peter G. Anderson, Observer

Title:
On-line Image Processing Tool

Author:
Cheng-Peng Kuo

Date:
May 1998

Abstract:
In this project, I implement some important image processing algorithms using Java language which is available on multiple platforms. The project is a Java applet that allows its use from the world wide web. The algorithms I implement fit into three categories:

1. Color processing: This part provides the ability to adjust tonal and color balances in an image, and to adjust brightness and contrast.

2. Filter processing: An image can be made smoother or sharper by using a convolution kernel. In this part, I implement image blur and image sharpening functions. The user is able to define a convolution kernel using a dialog window to setup different effects.

3. Distortion processing: Image warping, which deals with geometric transformation of digital images, is the third category of this project.

e-mail: cxk0157(at sign)cs.rit.edu

Visit project's home page.

Committee:
Prof. Nan C. Schaller, Chairman
Dr. Peter G. Anderson, Reader
3, Observer

Title:
Intelligent system for monitering UNIX network

Author:
Katerina Stoykova-Klemer

Date:
June 1998

Abstract:

In the field of Network Administration, there are many tasks which must be performed to monitor the status of a local network and each of the machines connected to it. These tasks require knowledge of various parameters of the network configuration which can be difficult to track, particularly when a system becomes large and changes occur frequently. An expert system administrator is generally knowledgeable about how to extract the information he or she needs to evaluate the network status or to diagnose problems. However, even when one knows how to access the appropriate information, doing so can involve repeatedly performing a series of commands that can make even the simplest task time-consuming.

It is therefore highly desirable to have a software tool for managing information about the configuration of a UNIX network, for monitoring the status of the system, and for automating the tasks involved with detecting and resolving problems and maintaining the network.

I am designing an intelligent network monitoring system with the purpose of aiding the system administrator in discovering and correcting network inefficiencies and problems. Specifically the system will operate in 3 modes: initialization (learning), interactive, and daemon (continuous background) modes. The objective of the initialization mode is to learn about the network's configuration. In the interactive mode the system uses information learned during its initialization to provide a series of high level tests to the user. The daemon mode provides continuous monitoring of network status, and makes intelligent decisions to alert of high level tests to the user. The daemon mode provides continuous monitoring of network status, and makes intelligent decisions to alert administrators or attempt automatic repair when problems are detected in the system.

e-mail: kis1380(at sign)cs.rit.edu

Visit project's home page.

Committee:
Prof. Warren R. Carithers, Chairman
Prof. Kenneth A. Reek, Reader
Dr. Peter G. Anderson, Observer

Title:
Search for Mersenne primes,

Author:
Yelena Migdalovich

Date:
July 1998

Abstract:
Two main goals of this project are to use MP package that I have developed as well as the GNU MP library and to apply multiple-precision arithmetic to some number theoretical problems. Multiple-precision arithmetic is of fundamental interest for both theoretical and practical reasons. This work presents a developed a multi-precision library which supports the following primitive operations on big numbers: addition, subtraction, multiplication, modular exponentiotion, division. We have been used simple radix-conversion technique for convertion long numbers from radix b to radix B. The recursive implementation of the Karatsuba multiplication algorithm results in reducing running time complexity from O(n^2) to O(n^{log{3}}) \approx O(n^{1.585}), where n is the number of digits.

Implementation of deterministic Lucas-Lehmer and probabilistic Miller-Rabin primality tests, finding the distribution of primes and twin primes in a specific ranges using developed multiple-precision operations.

Search for Mersenne numbers through participation in the Great Internet Mersenne Prime Search.

Committee:
Dr. Stanislaw P. Radziszowski, Chairman
Dr. Peter G. Anderson, Reader
3, Observer


Title:
The N Queens Problem Solved Using Genetic Algorithms and Heuristics

Author:
Xingping Hu

Date:
August 1998

Abstract:
Genetic algorithms use the idea of Survival of the Fittest to minimize the search space. They can find a solution or an optimal solution by examining only a small portion of a big search space. The efficiency of the GAs depends on how small this portion is; the quality of the solution found by the GAs depends on how good the candidate solutions in this portion are. This project combines order-based genetic algorithms with several optimal strategies to shrink the search space and enhance the quality of the candidate solutions at the same time. These optimal strategies include greedy methods, conflict minimization, shortest subtour, cross-edge removing, and cut-and-insert. They have been adopted into special methods and operators, such as population initialization methods and mutation operators, for the N-Queens problem and the Travelling Salesman problem. With these special methods and operators, this project is capable of finding a solution for the 10,000-Queens problem in about 67 minutes and finding the optimal tours for some best-known Travelling Salesman problems. In addition, this project includes a 4-piece interactive software package written in Java.

Visit project home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Stanislaw P. Radziszowski, Reader
Prof. J. A. Biles, Information Technology Department, Observer

Title:
Channel Routing Problem using a GA

Author:
Robert Bachman

Date:
July 1998

Abstract:
The channel routing problem is used in the layout of electronic circuits and VLSI chips. In the classical problem the channel is modeled on a rectangular grid with terminals on the top and bottom sides. Each terminal is labeled and is associated with one net in a net list or is unconnected. The goal of the problem is to connect together all terminals bearing the same net id and to minimize the distance between the terminals.

For this project, I have modeled a channel using C++ classes. Each class contains functions and variables that aid a GA in its search for the best solution to any given problem instance. I use three methods to represent an individual. Each method uses its own crossover, mutation and random generation methods.

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Tony Chang, Computer Engineering Department, Reader
Dr. Roger S. Gaborski, Observer

Title:
Efficient Reconstruction of Sparse Volumes from Cone Beam X-Ray

Author:
Michael Zucca

Date:
May 1998

Abstract:
Current tested and reliable algorithms used to back project 2D X-ray images into 3D volumes for the purposes of cone beam tomography have proven too slow for medical field use. This project attempts to achieve speedup on a back projection program provided by Strong Memorial Hospital's Experimental Radiology department. Three principle techniques were used to achieve sppedup: improving I/O and cache usage, parallelization, and a new technique known as progressive threshold rejection was created. Progressive threshold rejection works well with sparse volumes, such as subtractive volumes.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Ruola Ning, University of Rochester, Reader
Dr. James R. Vallino, Observer

Title:
CRITTER Course Scheduler GUI (Graphical User Interface)

Author:
David P. Cutter

Date:
July 1998

Abstract:
It is the intent of the CRITTER system to provide RIT CS\&IT faculty and staff with a replacement to the current legacy course scheduling system.

The current process of course schedule creation has many draw backs. For one, the professors cannot easily interact with the current system. The reasons for this are that the processes are paper driven and the current scheduler tool that is being utilized is a non-distributed database management application. Another drawback is that the scheduler is required to manually reconcile a good schedule with no conflicts. This is only required when the legacy application that is being used does not compute a good schedule. All of these problems makes the process very time consuming.

The CRITTER system will help make the schedule creation process more stream lined by attacking the deficiencies described above. First by giving users an intuitive and distributed World Wide Web (WWW) based application. This application collects information electronically and stores it to a centralized database. And second by providing a tool that can be used more effectively by the course scheduler.

The complete CRITTER system is composed of the following pieces: A scheduling Genetic Algorithm (GA) engine, a database management system, and a Graphical User Interface (GUI). This project is concerned with the GUI for the CRITTER Scheduling System.

The scheduling GA and database management portion of the system is separate RIT MSCS project defened by Tom Connors in 1997.

e-mail: dpc(at sign)lakers.grail.com

Visit project's home page.

Committee:
Dr. Walter A. Wolf, Chairman
Dr. Peter G. Anderson, Reader
Dr. Feredoun Kazemian, Observer

Title:
LPS-Based Error Diffuction for Color Images

Author:
Qi Xie

Date:
July 1998

Abstract:
We implement a new method of color image halftoning. This method combines Linear Pixel Shuffling order of visiting pixels in a image with error diffusion. Linear pixels shuffling is a quasi-random ordering of pixels, a technique with benefits of pseudo-random ordering, but described by an extremely simple rule based on an arithmetic progression. Digital halftoning of grayscale images using LPS and error diffusion has been studied and the performance is quite good. In this project, this new method will be applied to color images. The results will be tested and compared to the traditional error diffusion algorithm such as Floyd-Steinberg algorithm.

e-mail: qxie(at sign)entire.com

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Roger S. Gaborski, Reader
Dr. Feredoun Kazemian, Observer

Title:
Java Applets for LPS-Based Image Morphology

Author:
Mark DeRoller

Date:
July 1998

Abstract:
There were two goals for this project. The first goal was to demonstrate morphological image processing using linear pixel shuffling as the pixel ordering technique. The second goal was to gain experience in the Java programming language by implementing the first goal in a Java applet.

e-mail: mderolle(at sign)cldx.com

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Roger S. Gaborski, Reader
Dr. Feredoun Kazemian, Observer

Title:
Shape and Density Analysis of A Dental Experiment on Rabbit Jaw X-rays

Author:
Asli Kabasakal

Date:
July 1998

Abstract:
The purpose of this project is to create an application program that will analyze the results of some dental experiments on rabbits. Xrays of rabbit jaws indicate jaw extensions after dental treatment. In order to analyze the experiment effect, the xrays that are taken before experiment and after experiment are compared. In this analysis, two things are considered: the difference in the shape and the difference in the density. The application program that is developed in this project will help dentists to analyze the shape and density differences of the x-rays that have been obtained after and before treatment.

First, for the shape analysis, in this application program, the segmentation task is applied to define the object (jaw) and then median filtering, image closing and edge tracking algorithms are used to define the boundary of the object. Then, Medial Axis Algorithm is applied to define the skeleton of the object. Because there are some discontinuities in the skeleton, an line linking algorithm is applied to get a better skeleton. In order to show the shape difference of the xrays, these xrays are overlayed via a reference point and a reference angle. In the second part of the application program, the above reference point is used to perform a density analysis by subtracting the segmented part of the two images.

e-mail: axk0088(at sign)cs.rit.edu

Visit project's home page.

Committee:
Dr. Roger S. Gaborski, Chairman
Dr. Peter G. Anderson, Reader
3, Observer

Title:
Combinatorial Computing Approach to Selected Extremal Problems in Pseudoline Arrangements

Author:
Alina Y. Beygelzimer

Date:
June 1998

Abstract:
We present two classical open extremal problems that started out geometrical, and soon required the language and techniques from combinatorics, because they appeared to be intractable by other means. The problems referred to in the title are:

1 The Erdos-Szekeres problem of finding the least number n, such that any configuration of n points in general position contains the vertices of a convex (empty) n-gon.

2 The problem of finding for each integer n, the maximum number of halving lines of a configuration of n points in general position in plane.

We interpret the addressed problems in the language of counterclockwise systems which encode in combinatorial terms the ordering properties of a configuration of points. This suggested new approaches to these problems, as well as led to new attractive theoretical problems which proved to be of independent interest. Different concepts of isomorphism are presented settling the question: what are the configurations that are "essentially the same" and "essentially distinct"? Extension of the Knuth table of enumerations of the number of systems constituting different equivalence classes of pseudoline arrangements is given.

e-mail: ayb4369(at sign)cs.rit.edu
Committee:
Dr. Stanislaw P. Radziszowski, Chairman
Dr. Peter G. Anderson, Reader
Dr. Andrew T. Kitchen, Observer

Title:
JEM: A Java Based UNIX Account Administration Program

Author:
John M. Vogtle

Date:
July 1998

Abstract:
A UNIX Systems Administrator has many tasks to perform, not the least of which is the management of User accounts. This task is even more complex in a large environment where NIS is used to manage the accounts database and NFS is used to distribute home directories to multiple servers. The inter-related steps required to add and maintain accounts demands that a number of files be edited, directories be created, disk quotas defined, etc. Additionally, it is often desirable to track auxiliary information about the users such as phone numbers, identification numbers, and office location.

The purpose of this project is to provide an extensible tool (Jem) that can be used to administer UNIX accounts. The tool will be written in Java and will follow the client/server paradigm with the server side running on a UNIX host and the client portion executing in a Web browser which supports Java applets.

The secondary goal of the project is to provide (at minimum) an API allowing other files to be edited within the Jem framework without having to recompile the tool.

e-mail: who(at sign)who.who

Visit project's home page.

Committee:
Dr. Andrew T. Kitchen, Chairman
Prof. Warren R. Carithers, Reader
Dr. Peter G. Anderson, Observer

Title:
On-line Image Processing Tool

Author:
Ming-Li Peng

Date:
August 1998

Abstract:
It is easy to write programs that take input from a keyboard, use it, and then display the results on a screen. However, this type of program is not user friendly. Moreover, most modern programs do not work this way, nor do Web pages.

Java is a machine-independent programming language that supports the creation of a graphical user interface (GUI) for both input and output through a class library called the Abstract Window Toolkit (AWT). The AWT facilitates the addition of interface elements such as text areas and buttons, but experience has shown that writing such a program is simple, but cumbersome, work.

For this project, I built a Java GUI Wizard that allows the user to add their own interface elements using drag-and-drop from a menu bar to a default frame without having to deal with the AWT layout manager. When the user has completed the layout of the GUI, the Wizard will generate the proper Java interface source code for the user. I chose this topic for my Master's project because of my interest in computer graphics.

I selected Java because of its rich support of color, graphics and animation. Furthermore, Java's "write once, use anywhere" philosophy means that my results can be made available on my web site.

e-mail: mxp9196(at sign)cs.rit.edu

Visit project's home page.

Committee:
Prof. Nan C. Schaller, Chairman
Dr. Peter G. Anderson, Reader
Dr. Stanislaw P. Radziszowski, Observer

Title:
Experimental Study of Graph Optimization Techniques

Author:
Alec Berenbaum

Date:
August 1998

Abstract:
Throughout the study of various theories of algorithms much work has been done in the area of traversal and searching of directed graphs. Some of this work includes studies of finding the Minimal-Cost Spanning Trees(MST) in directed and undirected connected graphs. Several algorithms have been developed for such task. These algorithms tend to differ in performances based on various factors, such as graph densities, sizes of problem spaces, ranges of weighs that can be assigned to the edges of the graphs, edge weight distributions, etc. The data structures used by an algorithm can have a significant impact on algorithms performance, for each of the aforementioned factors. This paper presents the results of the experimental study of the impact the data structures have on performances of Kruskals and Prims algorithms for finding Minimum-Cost Spanning Trees in connected undirected graphs.

The goal of this study is to compare performances of the practical implementations of Kruskals and Prims algorithms to their theoretical counterparts, as well as to measure and compare the differences in performances for various implementations of one algorithm, with respect to different implementation of the essential data structures. Performances of different algorithms are studied with respect to each-other for several variations of the types of data. As a result, a table depicting a schedule for use of the various implementations of either of the algorithms, as related to the type of graph used, is presented.

The algorithms are implemented and executed on a single Sun UltraSparc workstation, in order to eliminate the discrepancies, which may result from the differences in the processor speeds and variable CPU loads on multiple test machines. Following implementations are studied in this experiment:

- Kruskals Algorithm with heapsort, and with Path-Compression algorithms

- Kruskal's Algorithm with counting sort and with Path-Compression algorithms

- Prims Algorithm with brute force implementation of priority queues

- Prims Algorithm with priority queue implemented using a binary heap with bubble-up performed each time a decrease-key operation is performed for a vertex ("proper heap")

- Prims Algorithm with priority queue implemented using a binary heap with bubble-up performed after all decrease-key operations are performed for a vertex ("lazy heap")

- Prims Algorithm with priority queue implemented using a binomial heap

- Prims Algorithm with priority queue implemented using a Fibonacci heap.

e-mail: who(at sign)who.who

Visit project's home page.

Committee:
Dr. Stanislaw P. Radziszowski, Chairman
Dr. Peter G. Anderson, Reader
3, Observer

Title:
Evolving Hardware with Genetic Algorithms

Author:
Kevin E Kerr, (Computer Engineering Department)

Date:
July 1998

Abstract:
Genetic techniques are applied to the problem of electronic circuit design, with an emphasis on VLSI circuits. The goal is to have a tool which has the performance and flexibility to attack a wide range of problems. A genetic algorithm is used to design a circuit specified by the desired input/output characteristics. A software system is implemented to synthesize and optimize circuits using an asynchronous parallel genetic algorithm. The software is designed with object-oriented constructs in order to maintain scalability and provide for future enhancements. The system is executed on a heterogeneous network of workstations ranging from Sun Sparc Ultras to HP multiprocessors. Testing of this software is done with examples of both digital and analog CMOS VLSI circuits. Performance is measured in both the quality of the solutions and in the time it took to evolve them.

e-mail: kek7019(at sign)rit.edu

Visit project's home page.

Committee:
Dr. Muhammad E. Shaaban, Computer Engineering Department, Chairman
Greg P. Semeraro, Adjunct Professor, Computer Engineering Department, Reader
Dr. Peter G. Anderson, Observer

Title:
Generation and Isomorph Rejection of Triangle-Free Edge 3-Colorings

Author:
Xiaofei Zhao

Date:
August 1998

Abstract:
Algorithm design for computer based graph generation and isomorphism checking is very complicated. Almost all the principal computer resources have to be carefully considered during the design of these algorithms, and very often compromises have to be made between CPU usage, I/O, and disk usage. It is very challenging to design such programs that can run effectively on a few ordinary computers, which have central processing units typical of the day, limited disk space, and average I/O capacity.

In this project, algorithms were designed and implemented for both a 3-coloring triangle-free graph generator and an isomorphism checker. The resulting programs were run on a couple SVR4 unix systems with 150MHZ CPUs for several months. These programs successfully reproduced the two 3-coloring, triangle-free, non-isomorphic graphs with 16 vertices constructed by Laywine and Mayberry.

e-mail: zhao(at sign)jade.ssd.hcsc.com
Committee:
Dr. Stanislaw P. Radziszowski, Chairman
Dr. Peter G. Anderson, Reader
Dr. Fereydoun Kazemian, Observer

Title:
A Survey of Gaussean Radial Basis Function Neural Nets

Author:
Amin Remtulla

Date:
July 1998

Abstract:
A lot of research is being and has been done in the field of Gaussian Radial Basis Function Neural Networks (GRBFNN) and as a result there has been evolution of GRBFNN towards the computationally efficient and dynamic architectures.

This project investigates three classes of GRBFNN as part of the evolution. These classes are
1) Fully Supervised GRBFNN,
2) Hybrid GRBFNN and
3) Minimal Resource Allocating Network (MRAN) for function approximation.

The learning scheme for the Fully Supervised GRBFNN is derived and its results are compared with the standard Backpropagation algorithm. Hybrid learning scheme, which is the combination of unsupervised and supervised learning is explained.

Main emphasis is given to the MRAN for function approximation. The performance evaluation of MRAN algorithm is done for the following benchmark problems:
Exponential time function.
Hermite polynomial.

e-mail: who(at sign)who.who

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Roger S. Gaborski, Reader
Dr. Fereydoun Kazamian, Observer

Title:
Linear Pixel Shuffling Compression of Grayscale and Color Images

Author:
Charles J. Mayer

Date:
August 1998

Abstract:
The linear pixel shuffling (LPS) technique is a useful way to visit the pixels of an image in a mixed up order. The algorithm is designed so that when a fraction of the pixels are rendered, sub-rectangles of equal size chosen at any location in the image will contain approximately the same number of visited pixels.

This technique has been applied to black and white images. I have extended this technique to grayscale and color images by applying methods from digital image processing. Results have shown that, for most images, this technique yields higher lossless compression ratios than the GIF compression standard. The LPS technique has the advantage of allowing the user to view an approximation of the image before the decompression is complete. In addition, the compression may be halted at any time; the result is a lossy compression. Such properties are especially useful when transmitting across busy networks.

The construction of the LPS algorithm for grayscale and color images will be discussed, and its advantages and disadvantages explored. The results are compared and contrasted with other image compression techniques, such as LZW and the Discrete Cosine Transform.

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Raghuveer M. Rao, Electrical Engineering Department, Reader
Dr. Roger S. Gaborski, Observer

Title:
Design and Implementation of an Extendable Chinese Character Recognition System

Author:
Xuejun Yang

Date:
September 1998

Abstract:
This project involves of designing and implementing a complete functional Chinese character recognition system, as well as testing this system with plenty of character samples. The system will take 24 by 24 character bitmaps as the input, process it, and output some unique information, such as Unicode and GB code, about the input. The engines used extensively during processing is a feature extracting engine and a feature matching engine. Both of them utilized some new algorithms devised by the author. There are four steps during the recognition process, they are modulated in a way that each of them can be refined or replaced with a better approach without affecting the remaining steps. This system has unlimited learning capability, that is, if it fails to recognition a character, it will try to learn the character, and recognition at the next time is guaranteed if the learning is successful. It simulates the learning process of human in this sense.

e-mail: jyang(at sign)sycon-design.com

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Stanislaw P. Radziszowski, Reader
Dr. Andrew T. Kitchen, Observer

Title:
Image Encoding, Reconstruction, and Multiresolution Representation Based on The Fractal Theory of Iterated Function Systems

Author:
Wutnipong Sompamitr

Date:
September 1998

Abstract:
abstract

e-mail: who(at sign)who.who

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Stanislaw P. Radziszowski, Reader
Dr. Andrew T. Kitchen, Observer

Title:
Two-Phase Commit Protocol

Author:
Mattew DeRoller

Date:
October 1998

Abstract:
The goal of this project is to create a set of JAVA classes that implement the Two-Phase Commmit Protocol. These classes will be general enough to be used by JAVA applications with replicated databases. Concurrency control and database management will be handled by this library of classes. An application that utilizes replicated data will be created so that these classes can be demonstrated.

e-mail: who(at sign)who.who

Visit project's home page.

Committee:
Dr. Andrew T. Kitchen, Chairman
Dr. Peter G. Anderson, Observer
3, Observer

Title:
Web Page Generator.

Author:
Wen Fu

Date:
November 1998

Abstract:
To be supplied.

e-mail: who(at sign)who.who

Visit project's home page.

Committee:
Dr. Peter G. Anderson, Chairman
Dr. Stanislaw P. Radziszowski, Reader
Dr. Hans-Peter Bischof, Observer


e-mail: anderson(at sign)cs.rit.edu