I'm going to pose some problems
and programming exercises (as you suggested earlier). I'm not requiring
solutions for all of them, though it would be nice.
Cite sources as appropriate!
* Maximum Segment Sum:
you've seen this - given a list of integers (works on R, I suppose),
find the largest of the sums of continuous (possibly empty) subsequences
of that list.
- provide a correct algorithm, a proof, and
its worst-case complexity
- prove a lower bound on the complexity of any solution
- Find as (asymptotically) efficient an algorithm as you can.
* Goodstein's sequence:
See here:
http://astronomy.swin.edu.au/~pbourke/fun/goodstein/
Write code implements goodstein's sequence from an
arbitrary starting point. Explicitly manipulating expressions
would be a nice reality check that you know how to handle
data in Haskell. Otherwise, show your code is correctly
following the theorem.
For bonus points, prove goodstein's sequence terminates at
0 starting from any natural number.
As a mathematician, if you haven't run across this result before you
might be interested in the Kirby-Paris theorem, which states that this
termination of Goodstein's sequence is independent of Peano Arithmetic.
* Haskell coding:
Write a monad providing continuations, reference cells (ala STRef)
whose state is captured by continuations, and reference cells which
do not revert when a continuation is invoked. (providing reference
cells at any desired type is a bit tricky - I think there's probably
a solution that doesn't require exploiting loopholes in the type
system).
Make an interpreter for a language with at least these features,
lambdas, conditionals, arithmetic, and output.
* Maximum Length Acceptable Segment Sum
Similar to maximum segment sum, except you have a threshold "k", and you
want to find the length of the longest contiguous subsequence whose sum
is at least k.
Again, provide some correct algorithm, and try to find as efficient
an algorithm as possible.
(Took me a few days to work out, knowing a few approaches to optimal
solution for the other problem)
* Pirates
A band of pirates has a pot of gold coins.
In some pre-determined order, each pirate proposes an allocation
of the gold, and all living pirates vote. If the proposal is rejected
or tied, the pirates kill the proposer, and the next steps up.
Each pirate votes to maximize their income, and to maximize the number
of rivals killed, subject to maximizing their income.
What happens for 100 gold pieces and n pirates?
What happens for k gold pieces and n pirates?
Plenty of interesting generalization to consider, if you like:
What if the gold is continuously divisible?
What if each dying pirate gets two pieces of gold, to pay Charon's fare?
What if a pirate can propose a random choice between distributions?
What if the next pirate is randomly selected, rather than selected
according to some fixed order?
less practical variations:
What if you have an infinite pot and n pirates?
What about an infinite pot and infinitely many pirates?
(who's afraid of a little transfinite induction?)
Well, that seems to plenty of little puzzles - I've got no excuse to be
bored for a while.