-----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, [EMAIL PROTECTED] 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 > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell-cafe -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.2 (GNU/Linux) iD8DBQE/Rm7SYha8TWXIQwoRAvCrAJ4hN2Fh2auX8Sw9yv9jyuvGKYgPyQCcCtj0 2pHxw0tuysC1t54haq0dIOo= =furR -----END PGP SIGNATURE----- _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
