Problems Index              Sun May 07 04:46:55 AM EDT 2006


These are some of the more `educational' problems from
the various BOSPRE contests, and from a few Eastern New
England predecessors of BOSPRE.  You can do these pro-
blems to learn new algorithms, or just for fun.

Text
----

    problems/passwords
	What is a good way to generate memorable
	passwords?
	Boston Preliminary 2004.
	Author: Bob Walton

    problems/stringhash
	Computing a random hash value from a string.
	Boston Preliminary 2005.
	Author: Bob Walton

    problems/huffman
	Huffman coding trees.
	Boston Preliminary 2001.
	Author: Bob Walton

    problems/rle
	Run length encoding.
	Northeastern Preliminary at Harvard 1997.
	Author: Dan Ellard


Simulation
----------

    problems/fibonacci
	Tail recursion.
	Northeastern Preliminary at Harvard 1997.
	Author: Bob Walton

    problems/convoy
	Why traffic patterns are what they are.
	Boston Preliminary 2003.
	Author: Bob Walton

    problems/motion
	Simulate a bounding ball.
	Northeastern Preliminary at Harvard 1997.
	Author: Bob Walton

    problems/soldiers
	DFA simulation: soldiers in a row.
	Northeastern Preliminary at Harvard 1996.
	Author: Bob Walton

    problems/virus
	Simulate an AID's like virus's ecology.
	Northeastern Preliminary at Harvard 1996.
	Author: Bob Walton

    problems/gcomputer
	Simulate a graph computer that can search.
	Northeastern Preliminary at Harvard 1996.
	Author: Bob Walton

    problems/hypercube
	Simulate a hypercube queued message network.
	Northeastern Preliminary at Harvard 1996.
	Author: Bob Walton


Trees and Graphs
----- --- ------

    problems/tsearch
	Binary trees and their rotations.
	Northeastern Preliminary at Harvard 1997.
	Author: Bob Walton

    problems/treap
	Treaps.
	Northeastern Preliminary at Harvard 1997.
	Author: Bob Walton

    problems/unify
	Unifying a labeled graph.
	Northeastern Preliminary at Harvard 1997.
	Author: Bob Walton


Search
------

    problems/isa
	Searching a graph.
	Boston Preliminary 2005.
	Author: Bob Walton

    problems/gsat
	A greedy local search to satisfy large proposi-
	tional formulae.
	Boston Preliminary 2002.
	Author: Bob Walton

    problems/tng
	Game search in for a game with very simple
	state.
	Boston Preliminary 2001.
	Author: Bob Walton

    problems/palin
	Exhaustive search with tree pruning.
	Boston Preliminary 2000.
	Author: Tomas Rokicki


Calculation
-----------

    problems/binary
	Simulate binary addition.
	Northeastern Preliminary at Harvard 1997.
	Author: Bob Walton

    problems/monotonic
	Solving monotonic functions.
	Boston Preliminary 2003.
	Author: Bob Walton

    problems/chromatic
	Calculating chromatic polynomials.
	Boston Preliminary 2005.
	Author: Bob Walton


Probability
-----------

    problems/pseudopi
	Throwing chalk at a circle on a blackboard
	in order to compute PI.
	Boston Preliminary 2005.
	Author: Bob Walton

    problems/drunkard
	What do random walks look like?
	Boston Preliminary 2004.
	Author: Bob Walton

    problems/puredie
	How to you get a biased die to behave like an
	unbiased die?
	Boston Preliminary 2003.
	Author: Bob Walton

    problems/transducer
	Computing probabilistic non-deterministic
	finite transducers.
	Boston Preliminary 2004.
	Author: Bob Walton

    problems/betterbias
	Getting dice to act like biased dice.
	Boston Preliminary 2002.
	Author: Bob Walton


Geometry
--------

See the 2D_geometry help file.

    problems/changeview
	Often computer geometry problems are basically
	a matter of changing the coordinate system.
	Boston Preliminary 2003.
	Author: Bob Walton

    problems/beebumblia
	How close is a point to a line segment?
	Boston Preliminary 2001.
	Author: Bob Walton


Dynamic Programming
------- -----------

See the dynamic_programming help file.

    problems/opnum
	A simple dynamic programming problem.
	Boston Preliminary 2000.
	Author: Tomas Rokicki

    problems/tour
	Using dynamic programming to solve small
	traveling salesman problems.
	Boston Preliminary 2001.
	Author: Bob Walton


Greedy Algorithms
------ ----------

    problems/coloring
	Coloring graphs with a greedy algorithm.
	Boston Preliminary 2003.
	Author: Bob Walton

    problems/warriors
	The optimal matching algorithm.  Read the
	optimal_matchings help file to see how to solve
	this very hard problem.
	Boston Preliminary 2001.
	Author: Bob Walton


Logic and Language
----- --- --------

    problems/prooflabel
	The Curry-Howard Isomorphism.
	Boston Preliminary 2005.
	Author: Bob Walton

    problems/features
	Feature structures.
	Boston Preliminary 2003.
	Author: Bob Walton