|
|
| Binary integer programming is a class of algorithms that are used to solve problems where we have several yes/no decisions, along with some constraints on which decisions we can make and a value associated with each decision. A classic example is the knapsack problem, where we have to choose what to carry in the knapsack. For each possible item, we can carry it or not. We are also limited by space and weight, and some objects will have a higher value than others. This paper examines binary integer programming and a simple computer implementation of a technique for solving such problems, called the Multiphase Dual Algorithm, which was developed by Dr. Fred Glover in 1965. We also test the execution time of this program compared to an implementation of a branch-and-cut algorithm developed by COIN-OR. Results show that this Multiphase Dual program executes in about the same time as the branch-and-cut algorithm on small problems, but starts to become slower on large programs. This indicates that although the Multiphase Dual algorithm may not be the fastest possible algorithm, it can solve binary integer programming problems in a reasonable time. We conclude by discussing other parts of the algorithm whose implementation would increase its efficiency. |
|
|
| This thesis has three parts: an analysis of mountain lion data provided by Montana Department of Fish, Wildlife and Parks, a study of the strength of correlations with small data sets, and preparation of a beginner’s user manual for the statistical package R. The analysis of the mountain lion data showed correlations in which the coefficient of determination was around 0.60 with a data set of size five. A simulation was written in R to determine the likelihood of seeing this strength of correlation, and it was found that a coefficient of at least 0.60 occurs in only 13% of cases. The open source statistical package, R, was used for all analysis. In the course of learning R, a manual was prepared to assist future students in learning this valuable software package. |
|
|
| This thesis has three parts: an analysis of mountain lion data provided by Montana Department of Fish, Wildlife and Parks, a study of the strength of correlations with small data sets, and preparation of a beginner’s user manual for the statistical package R. The analysis of the mountain lion data showed correlations in which the coefficient of determination was around 0.60 with a data set of size five. A simulation was written in R to determine the likelihood of seeing this strength of correlation, and it was found that a coefficient of at least 0.60 occurs in only 13% of cases. The open source statistical package, R, was used for all analysis. In the course of learning R, a manual was prepared to assist future students in learning this valuable software package. |
|
|
| As a rubber tire rolls down its path it is subjected to many different forces. To limit the deformation of the tire as it is subjected to these forces, cords of a more rigid material are aligned in the rubber to provide a stiffening effect. This stiffening of the composite material depends on the angle at which the cords are aligned in the rubber material. This research focuses on the specific case of in-plane bending of a tire ply through the application of a bending moment to the ply. The cord forces and the resultant stresses of the rubber membrane are studied as a function of the cord angle. |
|
|
| The classical laws of motion and Newtonian thought met considerable
opposition in the late 1800s and early 1900s as a result of several observations
that were inexplicable by then current means. Several breakthroughs were
made by notable historic figures such as Louis de Broglie, Werner Heisenberg,
Max Planck, Albert Einstein, and of particular interest, Erwin Schrödinger.
The new ideas and innovations of these and other individuals helped forge
the beginnings of Quantum Mechanics and paved the way for significant understanding. Erwin Schrödinger confronted the problem of electrostatic attraction between the nucleus and electrons within atoms. His approach greatly utilized the developing theory of wave-particle duality, introduced by Planck and Einstein, and the quantization of energy. The result of Schrödinger’s work was a wave model that fundamentally stated that all possible locations for a particle can be represented by a wave. The Schrödinger Equation establishes a mathematical relation between a particle’s energy and its wavefunction, and is considerably generalized, making it adaptable to various applications. This investigation aims to understand the observations and discoveries leading up to and resulting from the Schrödinger equation, as well as look into some simple solutions of the equation in one dimension. Specifically, five well-known instances of classical mechanical failures are presented followed by a basic approach to solving the single particle systems of a particle in a box and a simple harmonic oscillator. Numerical methods are utilized to solve the Schrödinger equation and discover allowed particle states within various potentials. |
|
|
| Real-life decisions often need to take into account uncertainties about many future events. There are various models for processes that evolve over time in a probabilistic manner. Such processes are called stochastic processes. In this paper, we use both discrete and continuous time Markov chains to model an aircraft maintenance facility and explore the relationships of these models with standard queuing theory approaches. Our first step applies discrete time Markov chains based on Binomial and Poisson distributions to our model. Next, we extend the models to continuous time Markov chains associated with exponential distributions, and also relate the new model to queuing theory. Finally, we compare our discrete models to the continuous ones and generalize cases for which a discrete Markov chain can be effectively implemented into the standard queuing approach to help analyze the transient probability states. In the end, we analyze strengths and weaknesses of our methods as well as propose future work that could be accomplished. Several ideas are explored using Mathematica. |
|
|
| Buoyant flux tubes of magnetic energy in the sun rise through powerful and turbulent convection to penetrate the sun's photosphere and produce sunspots. The question studied in this research paper is: How do magnetic flux tubes rise through this violent convection to the solar surface without being destroyed? We analyze data in 128*128*300 arrays generated from supercomputer simulations of three-dimensional magnetized gas to investigate the sensitivity of flux tube survival time to different parameters: the magnetic field strength of the tubes, the viscosity of the solar fluid, and the magnetic diffusivity. We also calculate the standard deviation of magnetic energy density within the arrays to set a scale that quantitatively describes flux tube coherence. Both quantitative and qualitative measures indicate that increased magnetic field strength and increased viscosity greatly expand the time of the flux tube's survival, whereas increased magnetic diffusivity minutely inhibits flux tube survival time. |
|
|
| The Riemann Hypothesis is probably the most famous unresolved problem in all of mathematics. While some unsolved problems in math can be stated and understood in a handful of lines, the Riemann Hypothesis requires a significant background before the problem can be grasped. This paper provides the background necessary to understand the Prime Number Theorem, and the zeta function on which the Riemann Hypothesis is based. This paper also examines the tie between the zeta function and the distribution of prime numbers. Operations of complex numbers are discussed at length, as well as functional convergence with complex arguments. The difficulty of graphing functions with complex arguments is addressed and primitive graphs of the zeta function are explained. Lastly, this thesis discusses why this problem has become so important and the current state of the search for its proof. |
|
|
| This thesis explores topics in game theory within the framework of the popular game Mancala. Game theory is a branch of mathematical analysis developed to study decision making in conflict situations such as games. Mancala is believed to be one of the oldest games in the world, and makes a great study because of its many levels of complexity. I explore several variations of the game and demonstrate the increasing level of difficulty in developing optimal playing strategies. |
|
|
| Permutations and substitutions have been used in cryptography for the past two thousand years, dating back to Julius Caesar and the Egyptians. The algorithms themselves are very simple, yet when multiple permutations and substitutions are combined, some of the most sophisticated and complex coding methods of our time are produced. In this paper we first review the basic permutation and substitution ciphers. We then see how these ciphers are used in two very modern and complex applications. The first application discussed is the Enigma machine, used by the Germans in World War II. We explain how this "unbreakable" coding method was finally broken. The second application of permutation and substitution ciphers that we look at is the Data Encryption Standard (DES). We briefly state the controversy surrounding the use of DES and mention a few of its successors designed to overcome these perceived problems. A number of these cryptographic ideas are illustrated with code in C++ and Mathematica. |
|
|
| This research involved the study of seismic behavior of older reinforced concrete bridge columns. This column reinforcement was modeled on columns used in the state of Washington prior to the mid 1970's. These columns were characterized by small quantities of hoop steel, poor confinement, and non-ductile behavior. The goal of the research was to determine the effect of cyclic load history on the resistance of such columns to lateral loading. Four specimens have been tested in a previous phase of the work, but the displacement histories used did not differ enough to determine the relative importance of two possible characterizing parameters: maximum displacement and cumulative plastic displacement. This current phase of the work involved the construction and testing of two additional columns, subjected to very different load histories, to clarify the role of each parameter. Upon completion of the tests, further analysis will be needed to determine the influence of each parameter on the column resistance. |
|
|
| The need for information sharing is growing daily, along with the costs
related to software licensing, training, and system maintenance. A niche has developed in
which organizations on tight budgets - such as colleges - require low or no cost alternatives
to pricey name brand interfaces. Open-source, freeware languages have resulted. They provide
users with the means for implementing and maintaining highly functional data systems from the
ground up and are quickly establishing an edge in the world of data communications for both
amateur and professional system designers.
This Honor's project focuses on the melding of three relatively dissimilar topics contained within the field of computer science: web design using hyper-text markup language (HTML); database structures created in the language MySQL; and object-oriented programming via hyper-text preprocessor (PHP). Together, these three components form a powerful tool with literally boundless applications in the area of data management, involving few to numerous participating users. A system utilizing HTML, MySQL, and PHP has been designed from the ground up with the intent of demonstrating practical, as well as numerous powerful uses for this specific programming combination, including web-driven database searches, variable passing, and data modification, to name a few. The primary goals of this project are as follows: explain and breakdown the three components previously mentioned in terms of their history and technical specifications; present the system and accompanying interface based on these programming structures and concepts; and to discuss any findings, including strengths, weaknesses, difficulties, and all other pertinent information related to this project. |
|
|
| Due to fierce winter conditions, Montana streets can
become overridden with snow and ice. It is up to the snowplow operators
to ensure the safety of travelers across the state by plowing and sanding
roads before traffic becomes prevalent and accidents occur. Through algorithms
and graph theory a plan can be made to optimally plow the streets so that
snow and ice do not interfere with the daily commute.
Through the use of two algorithms, this thesis addresses the task of optimal plowing. The first is a greedy algorithm, the other a Look Ahead Algorithm. The greedy algorithm assesses the priorities of every street connected to the current intersection and chooses to plow the highest priority street. The Look Ahead Algorithm allows the user to input how many streets beyond local streets are to be considered. For example, the program could look many streets into the future to seek out a street that may not have been plowed yet but is surrounded by other streets that are. Algorithms can be used in any user-defined sequence. Users are also able to create, edit, and save their own maps through a graphical user interface. The editing program allows users to create and delete both streets and intersections as well as edit properties such as position and name on existing intersections and streets. This interface allows the user to enter more complex maps, such as the sectors of Helena for more realistic optimization. |
|
|
| Fractal Geometry provides a way, using mathematics, to reproduce the repetitive characteristics of objects found in nature. This thesis provides a background in Fractal concepts such as Chaotic Systems, Iterative Function Systems, the Mandelbrot Set and Brownian motion, and creates computer implementations for several of these fractals. Using computers, we can execute the step-by-step instructions to create Fractal images and give us a greater understanding of the depth and beauty of Fractal geometry. The computer implementations in this thesis provide the basis for coding natural landscapes in simulations, art, videogames and many other applications. |
|
|
| In today's world of information technology there is a heavy
emphasis upon the efficiency and speed of computers. With this new age,
an abundant amount of new methods have emerged attempting to save time and
computer space by compressing both 2-dimensional pictures and continuous
feed multi-media, such as movies and music. Recently, wavelet analysis has
emerged as the best tool to perform these tasks. In the world of mathematics,
wavelet theory has also become a hotbed for both cutting edge research and
applications to real-world situations.
My paper begins by exploring the mathematics behind wavelet analysis and the connections wavelets have with vector spaces. An exploration of applications of wavelets to different forms of real-world phenomena follows. I first utilize a program written in Maple to show how wavelets can be applied to the fields of sound filtering and signal compression. Mathematica is then used to illustrate wavelet applications to the compression of 2-dimensional images. An analysis of different compression ratios further demonstrates the effectiveness of the wavelet compression. Finally, a variation of the Mathematica computer program is utilized to perform compression of a continuous feed movie. An analysis to determine the optimal length of segments extracted from a continuous feed signal to send through the wavelet algorithm is then explored. |
|
|
| A technical study of wireless local area networks (LANs) with an emphasis on the associated security features and problems. An in-depth look at the IEEE specifications for wireless LANs, the security options in the specifications, an analysis of the shortcomings of these security options, and possible countermeasures for these lapses in security. |
|
|
| This paper studies the current state of mathematics on the Internet, while also analyzing various options in order to implement mathematical expressions online. Many educators wish to make classroom labs and exercises available online, without hindering students with more code than necessary. After analyzing a variety of available options, the decision was made to use Wolfram's WebMathematica to convert a typical classroom lab into an interactive online experience. Once the web page is online and accessible, it is critiqued for efficiency and functionality. This thesis will explore the installation of the WebMathematica software on a Linux-based web server, the creation of the web page, and the problems faced during the conversion process. |
|
|
| Math and music share one very common property; they are both universal languages of the world. Their scientific relationship represents another powerful tie. The harmonious, unique, and enjoyable tunes we hear are surrounded by scientific and mathematical concepts that make music possible. Exploring this natural connection between math and music allows for a more comlete understanding of both these subjects. By analyzing the formulas used to create musical notes, examining how to apply matrices to music, and implementing an inter-disciplinary unit of math and music into the classroom, the reader of this thesis will discover the multitude of similarities that math and music share. |
|
|
| Logic is a fundamental part of mathematics and computer science since it is the basis of mathematical proof and computer programming. In order to help students gain a better understanding of logic, I have implemented a computer version of Logic Puzzle which was created by Non Ishida in 1988. My thesis explores the rules of Logic Puzzle, some of the mathematics involved, and the computer code I have written. |
|
|
| Finding an efficient algorithm for solving NP-Complete problems has long been a goal of computer scientists and mathematicians. The purpose of this paper is to examine existing heuristics (approximate algorithms) and to construct original heuristics for solving the Traveling Salesperson Problem, a famous NP-Complete problem. Each heuristic is implemented on a personal computer in C++. The results of the heuristics are then compared against the best known solutions for specific well-studied instances of the problem. |
|
|
| In 1987 Whitfield Diffie at Stanford University and Martin
Hellman at the University of California proposed a revolutionary encryption
scheme that came to be known as public key cryptography. In 1977 Ron Rivest,
Adi Shamir, and Leonard Adleman implemented a version of this process in
a way that has become known as the RSA system. The strength of the system
resides in the fact that as of now, if we know a number is the product of
two large but unknown primes, say 150 or 200 digits each, there is no fast
or easy way of finding these unknown primes. Thus the security of this widely
used system depends upon the difficulty of factoring a large composite integer.
This paper begins by defining and illustrating what led up to public key cryptography and its implementation in the RSA system. We then investigate some of the known methods for trying to factor large (150-200 digits) integers. We start with elementary methods and algorithms and proceed to more difficult and complex ones, illustrating most of these using Mathematica. Doing so will require some results from the theory of numbers, and these too are discussed and illustrated. These topics include unique factorization and the Euclidean Algorithm, Fermat's and Euler's Theorems, pseudoprimes, the Chinese Remainder Theorem, Euler's f function, early factorization techniques, and quadratic reciprocity. The last section will summarize the state of the problem. |
|
|
| Each semester, Carroll College department heads spend hours developing course schedules by hand. Once registration begins,
class conflicts arise, and a significant amount of fime is spent attempting to alter the schedules by hand to resolve the conflicts.
In order to reduce the workload of designing course schedules, I developed an integer programming model for the scheduling of the classes in the Math Department. I researched historic schedules and interviewed professors for class and time preferences. Using this information, I formulated constraints and parameters for my scheduling model, with the objective of maximizing the happiness of the teachers. My model results in 1728 equations and 757 variables, which can be solved in a matter of seconds with computer software. I coded the model using the General Algebraic Modeling System (GAMS) and used the software's included CPLEX solver. The model produces a viable schedule for the courses in the department. My thesis discusses my model design and its application within the Math Department. I also analyze the flexibility of the model and the possibilities for its use in other departments and as a school-wide prototype. |
|
|
| This thesis focuses on why smallpox is considered a possible biological weapon and why the world needs to be concerned about its existence in laboratories. I based my model on how smallpox affected the Native American populations of both North America and South America and on the findings of other experts, especially the World Health Organization. With the information gathered, I made a model in order to help predict how the population would be affected if a community were to be attacked with smallpox. The model considers the manner in which the infection is spread before it is diagnosed as the smallpox virus. I used different scenarios to emphasize my point and gave suggestions on how or if the attack might be contained. |