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