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 Puzzle

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