The Student Honors Papers collection represents exemplary work in computer science at Illinois Wesleyan University. The Ames Library is proud to archive these and other honors projects in Digital Commons @ IWU, the University's online archive of student, faculty and staff scholarship and creative activity.
Constraint satisfaction problems (CSPs) involve finding assignments to a set of variables that satisfy some mathematical constraints. Unsatisfiable constraint problems are CSPs with no solution. However, useful characteristic subsets of these problems may be extracted with algorithms such as the MARCO algorithm, which outperforms the best known algorithms in the literature. A heuristic choice in the algorithm affects how it traverses the search space to output these subsets. This work analyzes the effect of this choice and introduces three improvements to the algorithm. The first of these improvements sacrifices completeness in terms of one type of subset in order to improve the output rate of another; the second and third are variations of a local search in between iterations of the algorithm which result in improved guidance in the search space. The performance of these improvements is analyzed both individually and in combinations across a variety of benchmarks and they are shown to improve the output rate of MARCO.
Native Cardinality Constraints: More Expressive, More Efficient Constraints
by Jordyn C. Maglalang
Boolean cardinality constraints are commonly translated (encoded) into Boolean CNF, a standard form for Boolean satisﬁability problems, which can be solved using a standard SAT solving program. However, cardinality constraints are a simple generalization of clauses, and the complexity entailed by encoding them into CNF can be avoided by reasoning about cardinality constraints natively within a SAT solver. In this work, we compare the performance of two forms of native cardinality constraints against some of the best performing encodings from the literature. We designed a number of experiments, modeling the general use of cardinality constraints including crafted, random and application problems, to be run in parallel on a cluster of computers. Results show that native implementations substantially outperform CNF encodings on instances composed entirely of cardinality constraints, and instances that are mostly clauses with few cardinality constraints exhibit mixed results warranting further study.
QuickAdvise - The Search for a More Efficient Method of Advising
by Gregory G. Pengiel '94
In order to choose courses both efficiently and properly, a student and
advisor must look at which courses have been taken, and also which ones are
necessary. They must then determine whether or not the student is qualified
to take the necessary courses. Unfortunately, there is no easy way to record
and maintain this work so that it may be used throughout the college career.
Hence, even though the student and advisor recently determined which
classes were headed, they must once again look up all relevant information
and determine which courses are best. This is exactly the type of problem
that a computer can solve. However, in order to properly design a software
application, various aspects of the situation must be extensively researched.
First, the solution presents a quandary in terms of the system design. The
language that is best suited to this type of application must be determined.
Secondly, in order to be useful, the user interface must be well constructed.
People do not like software that is not user friendly, so to make this a
worthwhile software application, the interface must be both intuitive and
accommodating. Finally, different development platforms must be considered
in order to properly solve the problem. If the previously mentioned items are properly devised and documented, the actual construction of the software
should not be difficult. Other points to consider are testing documentation,
unit and system testing, code reviews, scheduling, and graphic user interface
The use of a genetic algorithm to evolve networks for a natural language processing task
by Alexander E. Dimov '02
In this project a novel approach was taken for performing a natural language task. The task requires a neural network to predict the grammatical category of the next word in a stream of sentences. There are two main reasons why this task is interesting. In natural language processing, it is sometimes very difficult to determine the grammatical category of a word in a sentence when that word could belong to different grammatical categories depending on the context. For example, the word "run" can either be a noun or a verb in a certain sentence. The ability to correctly determine the category of the word can help a computer process natural language. In addition, the approach taken here to solve this task can lead to insights about the way the human brain learns and/or understands language. A Genetic Algorithm, which is conceptually based on simple principles known from Genetics, was developed and utilized to evolve neural networks that were used to perform the task. Genetic Algorithms have been used with remarkable success to solve complex problems in a number of fields but not for this type of problem. In addition, networks were trained via a classic learning algorithm, called back-propagation, to perform the same task. Since a Genetic Algorithm has not been used for this type of task, an implicit goal of this project was to show that it can be used. One of the other main questions addressed is whether learning (as in the case of training a neural network via back-propagation) and a search for an optimal solution (as in the case of the use of a Genetic Algorithm to evolve neural networks) differ and if so, how. Also, the underlying properties of the two different types of networks (depending on the approach taken to obtain them) were compared. Finally, issues about the computational complexity of the Genetic Algorithm were studied and discussed. These issues included the relationship between the input size (for ex. 10000 sentences) and the perfonnance of the network developed via the Genetic Algorithm approach, as well as the way the network must change as the input changes in size and the task changes in complexity (i.e. as the grammar and lexicon change) while the optimal parameters (of the Genetic Algorithm) are used.
Course Scheduling Software: Reference Manual
by Saa Gobir '91
Welcome to version 1.0 of the Course Scheduling software. Course Scheduling is designed to meet needs of anyone who is tying to create a course schedule.
This software is a product that compiles, links, and runs in C++; although it has C extension. It has been specifically designed to work In C++ exclusively. I had mixed a little of C++ functions with C structure programming to complete this package and make it more efficient. It is versatile, quick, and efficient.
This instruction manual is brief, due to fact that the software is well documented. It only covers the basic functions and features; creating data, editing data, sorting and searching data.
To get started, you need to be a little familiar with DOS. If you are not familiar with DOS, please turn to page 1.
Financial Aid Budget Projection Methodology
by Amy N. Baird '94
The nature of this research project is to make a very strong contribution toward the final goal of completely automating the Financial Aid Office at Illinois Wesleyan University over the next five years.
Improved Data Migration and Processing for Projecting the Financial Aid Budget
by Jeffery L. Olson '96
Last fall, I again resumed work on the budget projection model that encompassed five spreadsheets. Four of these sheets generated a set of statistical averages for each class. Each one consisted of 101 columns containing data for the four-to five-hundred students(rows) in each class. In addition, a fifth sheet used these averages to generate a highly accurate prediction for expenditures in the upcoming year. However, there were two main areas of improvement that became readily apparent: importing data and the sheets themselves.
PowerFAIDS: Building a Road to Financial Aid Efficiency
by Lauri Nichols '96
To most students, the Financial Aid office is a small room in the basement of Holmes Hall where they are occasionally sent to sign over a paper or two. It has something to do with money, and every so often, these students get something in the mail that tells them just how much it's going to cost them to continue their education here at Illinois Wesleyan. They know that papers are filled out, usually by their parents, and then in a couple of months, a figure jumps out of nowhere and becomes "Your Financial Aid Package."
Mapping Robotic Movement to a Three-Dimensional Coordinate System
by Craig A. Materick '97
The Illinois Wesleyan Intelligence Network on Knowledge (I.W.I.N.K.) is a project to design and implement an artificial"person'" named Shelley. Robotics, networking, and artificial intelligence will be the main topics ofthe preliminary work. For my research honors project I designed the three-dimensional coordinate system in which the robotic arms move and interact with objects. The anns we have constructed are based on an arrangement of six servos, each of which rotate approximately 185 degrees. The program takes in data about the location of an object in three-dimensional coordinates and moves each of the six motors in the ann to arrive at that point.Included in this work is a look at robotic arm developments through history, from Leonardo da Vinci through the Industrial Revolution, and beyond. Also discussed are the various joint and arm designs developed during these years of research and some robotics projects which employ these different designs. Next, we will investigate the various methods of control developed by other robotic arm research projects and apply one particular method to control Shelley, as briefly outlined above. Finally, we will highlight problems we faced during the implementation of this program, the solutions to these problems, and various ideas about future research possibilities.
Designing an Integrated Environment for Artificial Intelligence
by Andrew B. Ritger '99
The SHELLEY RESEARCH GROUP (part of the Illinois Wesleyan Intelligence Network on Knowledge -IWINK) has been in existence for several years, and has benefited immensely from various student contributors who have added such components as robotic arm control, cross platform networking, an artificially intelligent tic-tac-toe player, and an interactive teaching tool demonstrating the functionality of artificial neural networks. What is lacking, however, amidst these undergraduate contributions to the SHELLEY Project, is an effective means of integrating existing components into a single cohesive functional unit, let alone any easy means of making further contributions within a simple unified context. The focus of this research has been to design an all-encompassing structure for incorporating the different components of SHELLEY (both existing and future). Because we must operate under the assumption that we cannot predict what future contributions will be made to SHELLEY, nor how these components will be used, this integrated environment must be both flexible and expandable in such a way as to not confine future projects. The approach to artificial intelligence that the SHELLEY RESEARCH GROUP has taken relies heavily upon interaction with the surrounding environment. For this reason, many of the existing components are devices for receiving input from SHELLEY'S surroundings (such as vision cameras) or acting upon the surroundings (such as robotic arms). Thus, we can assume that future contributions will fall under two primary categories: additional devices (either cognitive, modules, such as neural networks, or interactive devices, such as cameras or arms), or intelligent agents (such as tic-tac-toe players, or navigation systems) that will use these devices. The environment must then be flexible in two manners -allowing for the addition of further devices, and providing a task management mechanism for accessing these devices. The solution is to use a modern operating system model where the devices that SHELLEY uses to interact with her environment correspond to computer hardware devices and their drivers, the intelligent agents are analogous to processes that run on the system and use the devices, and the administrator, which coordinates these agents and their usage of devices, can be compared to the kernel of the modern operating system.