Lab Exercises Week 11

Complexity

For this week's lab exercises, create a file Lab11.hs. In this file enter the function definitions appearing in the exercises below. Then, following the function definitions, in a multi-line comment, enter the derivation for the timing function and the proof that the function is in a certain O-class. So, overall, the structure should be as follows:

foo :: <some type signature>
foo ...<definition of the function>

{- ------------

DERIVATION OF T_...

PROOF:


-}

Ex 1:

Given the following function definition:

foo:: [Int] -> Int
foo []     = []
foo (x:xs) = (bar xs) + (foo xs)
	      

1. Derive the timing function for foo under the assumetion that T_bar(n) = 2 (n is the length of the input list). Does foo have constant, linear or quadratic work complexity? Justify your answer (which O-class? Provide witnesses c and n₀ to the proof)

2. Derive the timing function for foo under the assumetion that T_bar(n) = 3 * n + 1 (n is the length of the input list). Does foo have constant, linear or quadratic work complexity? Justify your answer (which O-class? Provide witnesses c and n₀ to the proof or use the observations discussed in the lecture)

Ex 2:

Ord a => [a] -> [a]
bubbleSort:: Ord a => [a] -> [a]
bubbleSort xs
  | xs == xs' = xs
  | otherwise = bubbleSort xs'     
  where
     xs' = bubble xs
     bubble (x:y: xs)
       | x < y     = x : (bubble (y:xs))
       | otherwise = y : (bubble (x:xs))
     bubble xs = xs
	      

1. Assume comparing two lists (==) has constant work complexity (i.e, n:length of first list, m: length of second list, T₌₌(n,m) = 1) . What is the asymptotic work complexity of bubbleSort in the worst case and the best case?

When you have completed the above exercise show it to your tutor for this week's advanced mark.

Additional Exercise