Project abstracts from previous quarters
Title: Estimating Phylogenies: A Study of Methods
Authors: Jaime Kurc and Justin Prosser
Abstract: By comparing sequences of DNA it is possible to estimate the historical branching order of the species. But what tree do we consider to be the "best"? Geneticists have pondered this question for years. Different methods for evaluating the accuracy of trees have been used, but since we only have speculative data on what to consider the "best" ordering, it is difficult to determine whether one method is better than another. Instead, we will provide an explanation and comparison of several methods (parsimony, maximum likelihood, distance-matrix, compatibility) that are currently being used and provide a discussion of the genetic significance and assumptions upon which these are based.
Title: Evaluating Shuttle Routing Heuristics with Markov
Chains
Authors: Derek Fallen, Frank Schwieterman, and Brian Vance
Abstract: An airport shuttle service is faced with the problem of when to dispatch vans to cities and airports. To determine the best dispatching scheme, Markov chains were used to determine the probabilities of when passengers would arrive at specific locations. By building complex systems from smaller systems, a process to create Markov chains that appropriately modeled multiple cities, vans, and passengers was developed. This process was implemented in LISP and was demonstrated to accurately model an airport shuttle dispatching problem.
Title: Latent Semantic Analysis as an Application of Singular
Value Decomposition
Authors: C. Lamy Wessling, E. Aurora Graf, Meredith Kim
Abstract: This paper demonstrates a small example of Latent Semantic Analysis (LSA), a semantic model which uses the basic principles of Singular Value Decomposition (SVD). We analyzed movie reviews to determine whether word relationships could be determined significant. We found that movie reviews of each genre differ in the relationship between the words within the review and the relationship between the various reviews. Also included is a brief description of the SVD technique and various applications of LSA.
Title: A Guide to Posting Flyers on the UW Campus
Authors: Theresa Marsh and Ryan Whitney
Abstract: Suppose you wanted to post announcements or flyers in buildings on the University of Washington campus. In which buildings would you post the flyers and in what order would you visit those buildings? Presumably, you would want as many people as possible to read the notices, and you would want to minimize the time it took you to post them. With this mind, the problem arises of finding a route on campus that includes a particular set of high traffic buildings and requires less time to walk than any other such route. To solve this problem, we applied a branch-and-bound technique that has been specialized for the traveling salesman problem. We first utilized the algorithm by hand to find the ideal path for a small set of four buildings, and then programmed the algorithm in C++. We were able to test the program against the solution obtained for the small set of buildings, and then apply the program to a set of ten, acquiring a solution to the larger problem.
Title: SimTraffic, A Study of Traffic at a Crosswalk
Authors: Gloria Chen, Jason Gurule, and Hiroko Takagi
Abstract: Traffic control has always been an important modeling problem. To accomplish such a task, information about each direction's traffic flow is required. Our project models the system of pedestrians and cars at a crosswalk in between the HUB and Lowe Hall on UW campus. It predicts how long a pedestrian or a car has to wait for the other to pass. This was accomplished by using the theory of Markov Chains as well as a Monte Carlo simulation. If needed, this information could then be used in an optimization problem.
Title: Freelance Photography Pricing
Authors: Julie Birum and Jerry Jaquith
Abstract: Our aim is to derive an hourly rate for freelance photographic services that will not only prove competitive and profitable, but will also allow for some personal preferences such as mandating a minimum amount of diversity for the various types of shoots. We model this using a basic economic equation for net profits (revenues) minus expenses, into a linear program. We can also solve another problem simultaneously, finding an optimal combination of jobs each week that will maximize profits, given our personalized constraints. Using the LINDO optimization software, this optimal schedule was found along with its resulting maximized net profit. Computing an hourly rate then became as easy as dividing the expected profit by the average 40 hour work week. The computed rate is now one that we are comfortable quoting all prospective clients regardless of their specific needs or time requirements.
Title: Mathematical Modeling in Phylogenetic Analyses
Authors: Anonymous
Abstract: Phylogeny, the study of the history of evolution, takes much advantage of discrete mathematical modeling. The central part of phylogenetic analysis lies in sequence alignment and the construction of evolutionary trees. We will discuss several different methods that are used in the field: the dot matrix method, the distance method, maximum parsimony, and the maximum likelihood method. We will focus heavily on the two latter methods and take a look at the motivations and principles behind them. Two computer programs are briefly discussed, DNAPARS and DNAML, which employ parsimony and maximum likelihood, respectively.
Title: Simplifying the Search for Food
Authors: Jason E. Eglin, Valentin Swegle
Abstract: Time efficiency in a grocery store can be vastly improved by a layout tailored to the customers. By identifying patterns in grocery store shopping, through calculation of most frequently purchased items, and items most often bought in conjunction, a mathematical model can be generated to approximate a "good" store. Specifically, a network of grocery items is reduced by Primm's algorithm into a maximal spanning tree. Further consideration as to the orientation of the tree within a store is given by the frequency of purchase. Manipulation of the resulting model produces an example of a good grocery store.
Title: Optimal Location Placement For Fast Food Restaurants
Authors: Brandon Bale, Ilia Babinskiy, and Igor Sviridyuk
Abstract: In todays fast-paced lifestyle, the fast food industry is growing rapidly. One can walk down any populated street in the city and find 3 to 15 inviting places to eat. Since fast food restaurants seem to be everywhere, and still more and more are being opened, an interesting question arises when one tries to find the optimal location for the restaurant. Is it more profitable for a franchise to open a restaurant in a less populated area with less competition , or open in a more populated area with more competition? Here we describe two different methods which reveal a solution: (1) Get an upper and lower bound on the expected population the fast food restaurant would serve. We do this by taking into account the customer layout of the system. Using a linear programming model, we can optimize the number of customers served at a particular restaurant. In doing this we obtain maxima and minima values of the people served. (2) Describe the system of restaurants in a particular region as certain states, then use a time evolutionary Markov Chain scheme. From this we find the steady state percentage of the population in that region that go to a particular restaurant. With the knowledge of the fast food eating population in each region, a less populated area and a more heavily populated area, we present a way to mathematically describe which location is better. We shall present a mathematical description and solution to the general case, and also give a solution to a specific problem.
Title: Methods for Generating and Optimized Schedule through
a Selected ACMS pathway
Authors: Eric Hansen, Greg Rothe
Abstract: In this project we examined two methods for generating an optimized schedule through a selected pathway of the ACMS degree program, PERT (Program Evaluation and Review Technique) and topological sort. For our purposes optimized is defined as a schedule the can be completed within two years, schedule classes as even a distribution as possible, and fits within a maximum number of credits per quarter. There are two major difficulties we encountered in the examination of this problem, namely how to make sure all prerequisites would be fulfilled in time to comlete all possible desired courses and how to deal with time conflicts. Our goals were to develop an automated schedule generator using primarily the topological sort technique and to supplement that with a graphical example of the problem using a combination of the PERT and topological sort methods. These objectives have been successfully met. The graphical and the automated scheduling methods can, with most data, construct and optimized, feasible schedule. Full descriptions of our solutions and their output can be found in the Solutions: section of this presentation.
Title: Optimized Layout for a Computer Keyboard
Authors: Daniel Johnson
Abstract: The computer keyboard is a tool used by millions of people daily, and it represents the primary human-to-computer interface. Constructed over one hundred years ago, the keyboard was designed in such a way to prevent the key "hammers" from jamming on early typewriters. This layout did not take into consideration ergonometrics or typing efficiency. Designing an optimized layout could result in less typing related injuries such as carpal tunnel syndrome, and the new design could increase productivity. Criteria used to create the keyboard include: ranking the efficiency of each key by considering which finger is used to type it, where the key is located on the keyboard, considering which keys are most commonly used by generating statistics on a sample and determining the common two letter combinations and positioning them so they are typed with different hands. Determining the optimum layout based on the criteria requires simplifications due to the large number of possible layouts. Restricting the placement of the physical keys to a format similar to the QWERTY layout will substantially shorten the algorithm for calculating the optimum layout. The result of this algorithm produced a layout seemingly more efficient than the QWERTY layout, however, the productivity curve for learning a new keyboard layout could nullify the advantages of the optimized design.
Title: Minimizing Investment Risk with the Capital Asset Pricing
Model
Authors: Stephanie J. McCann and Alexander J. West
Abstract: The Capital Asset Pricing Model can be used to find the set of efficient portfolios for a given group of stocks. A portfolio defines what proportion of money to invest in each of the stocks. An "efficient portfolio" is one with the property that no other portfolio gives the same expected rate of return with less risk. The strength of the model is that it can be applied to any group of stocks. We will simpliify the model by using past data to estimate return and risk for a given stock. We explain this model and the underlying mathematical theory and apply it to a group of 8 stocks, for six different types of investors.
Title: A Mathematical Representation of Telephone Technical
Support
via Queuing Theory
Authors: Theodore Hua and Don Palermo
Abstract: Computing & Communications is a department at the University of Washington offers a variety of services to its users in the computing field. One of these services is that of computer phone support. Due to unusual performance of its phone support department, a study was done to determine how well its service facility worked and what the optimum number of staff servicing clients should be. The mathematical field of queueing theory had been chosen to analyze the system. Due to the traditional format of the system in question, it was possible to analyze C&C's phone support system using a basic mathematical model involving a number of personnel and a constant arrival rate and service rate. This study determined that with a staff of three, an optimum number of clients can be served.