Homework

[Andrew J Bromage]

G'day all.

On Fri, Aug 22, 2003 at 03:41:14PM +1000, thomas_bevan@aardvark.net.au wrote:

> Seeing as its thst time of year again and everyone is posting their
> homework, has anyone got any good puzzles to do?
> I wouldn't mind having a go at something a bit tricky.

OK, here's a tricky problem.

Take a list S.  Delete some elements from the list.  What you have
left is a subsequence of S. For example, [1,3,2] is a subsequence of
[2,1,2,1,3,2,1,3].

Consider the following list:

	[1,2,3,1,2,3,1]

This list contains all permutations of the list [1,2,3] as
subsequences.  It is also minimal, in the sense that there is no shorter
subsequence which will do (though there are potentially many minimal
subsequences).  We will call such a list a shortest supersequence
over the alphabet [1..3].

The challenge is multi-part.  You may answer as many or as few questions
as you want.

   1. Write a function sss :: Int -> [Int] where sss n is a shortest
      supersequence over the alphabet [1..n].  Make this as efficient
      as possible.  Prove an upper-bound complexity on your function.

   2. Write a function sss_length :: Int -> Int where sss_length n is
      the length of a shortest supersequence over the alphabet [1..n].
      Make this as efficient as possible.  Prove an upper-bound
      complexity on your function.

      If you can't solve this problem efficiently, write a function
      sss_length_bounds :: Int -> (Int,Int) which returns the best
      upper and lower bounds that you can.

      (Hint: n is a trivial lower bound, n^2 is a trivial upper
      bound.  A tighter upper bound is n^2-n+1.  Prove this as an
      exercise.)

   3. Write a function sss_count :: Int -> Int where sss_count n is
      the number of shortest supersequences over the alphabet [1..n].
      Make this as efficient as possible.  Prove an upper-bound
      complexity on your function.

      (Hint: sss_count n must be a multiple of n factorial.  Why?)

      If you can't solve this problem efficiently, write a function
      sss_count_bounds :: Int -> (Int,Int) which returns the best
      upper and lower bounds that you can.

Incidentally, I don't have sub-exponential answers to any of these
questions.  You did ask for something "a bit tricky".

Cheers,
Andrew Bromage