COMP1011 Exercises for Week 11
Computing 1A 05s2 Last updated Tue 19 Jul 2005 14:37
Mail cs1011@cse.unsw.edu.au

# 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 Tbar(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 n0 to the proof)

2. Derive the timing function for foo under the assumetion that Tbar(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 n0 to the proof or use the observations discussed in the lecture)
When you have completed the above exercise show it to your tutor for this week's core mark.

### Ex 2:

The following program is yet another definition of a function that sorts the elements of a list.
```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?
Hint: To understand bubbleSort, use stepwise evaluation to evaluate bubbleSort [2,1,4,3] and bubble [4,3,2,1]. How does bubble alter the order of elements in a list? Under which condition is bubble xs == xs?

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