Proposed MSc projects for Russell Martin
Coupling from the Past: Implementation and Animation
Coupling from the past is an algorithmic method for generating random combinatorial structures, such as domino tilings or 3-colorings of rectangular regions, or lattice paths joining (0,0) to (n,n) in the square lattice.
This project will entail implementing one or more coupling from the past algorithms and providing a method for animating the procedure (displaying intermediate steps and the final resulting combinatorial structure). One of the aims is to find establish empirical bounds on the time needed to generate these random structures, and in some case compare those empirical bounds with theoretically established bounds.
Combinatorial Properties of the Stable Marriage Problem
The Stable Marriage Problem is a classical combinatorial and algorithmic
problem. The problem was first formally stated in 1962 by David Gale and
Lloyd Shapley, although hospitals had been using similar procedures to
determine intern assignments before this time.
Simply stated, consider a set of n women and n men. Each
woman has her own strict preference rating for the men, and similarly each
man has one for the women.
A marriage is a pairing of the men and women into n pairs
(where each man and women are used once, of course in the pairings).
The marriage is called "stable" if there does not exist a woman W
and a man M such that W prefers M over her
current partner and M prefers W over his current partner (else W
and M would drop their partners and pair up themselves).
It is well-known that every set of preference lists admits at least one
stable marriage, and there are efficient algorithms to find one. There
are many variants of this problem such as to the case of roommates, where
the pairs need not be male/female pairings.
The focus of this project is to first implement some related algorithms for these
matching/marriage/roommate problems (or other variants), and
use them to explore the combinatorial properties
of the problem instances and related structures that arise from them, or other
interesting questions. One could, for example, generate random instances of
the stable roommate problem, and determine what fraction of the instances admit a
stable matching.
Further description of the "Combinatorial Properties
of the Stable Marriage Problem" project.
River Crossing is a puzzle marketed by ThinkFun. The idea of the puzzle is that a hiker wants to cross a river that is filled with crocodiles, fleash-eating fish, and/or other unpleasantries. There are tree stumps that stick out above the surface of the river, and a few planks of wood of various lengths are available. By rearranging the planks to fit between the tree stumps (i.e. picking up and putting them in other places, in some sequential order), the hiker wishes to make it across the river safely.
This project consists of developing and programming a method to solve these types of puzzles (or demonstrating that no solution exists). Given time, a graphical interface can also be developed to allow users to input puzzles and to demonstrate (animate) the solution (should one exists).
Other Projects
Ideas for other projects will be considered. The ones that will be of most
personal interest will either involve a "randomized" component, some
combinatorial mathematics, and/or some aspect of game theory.
Back to Russ's home page