Homework

[Thomas L. Bevan]

=2D----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Thanks,

Let's hope you don't ruin my weekend.

Tom


On Fri, 22 Aug 2003 04:25 pm, Andrew J Bromage wrote:
> G'day all.
>
> On Fri, Aug 22, 2003 at 03:41:14PM +1000, thomas_bevan@aardvark.net.au=20
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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
=2D----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)

iD8DBQE/Rm7SYha8TWXIQwoRAvCrAJ4hN2Fh2auX8Sw9yv9jyuvGKYgPyQCcCtj0
2pHxw0tuysC1t54haq0dIOo=3D
=3DfurR
=2D----END PGP SIGNATURE-----