# Week 41

## Lecture Wednesday (9.10.2012)

The tenth lecture will start with analysis of Haskell programs with respect to space, runtime, and correctness.

##### Topics

space and time consumption, correctness proofs

##### Reading

Lecture Notes in Blackboard (Course Documents), chapter on correctness (Course Documents), chapter on complexity (Course Documents)

## Exercise Tuesday (9.10.2012)

1) Consider the implementation of sets as the data type defined on Page 6 of the notes on complexity available from Blackboard. Discuss how the time complexities given in the table arise.

Discuss what the space complexity for the individual operations is given each of the different data structures.

2) Consider the following Haskell program

data Nats = Zero | Succ Nats

add :: Int -> Int -> Int

add Zero y = y

add (Succ x) y = Succ (add x y)

mul :: Int -> Int -> Int

mul Zero y = Zero

mul (Succ x) y = plus y (mul x y)

Show that `mul x Zero = Zero` for all natural numbers `x`.

Show that `add` is commutative, i.e., that `add x y = add y x` for all
natural numbers `x` and `y`.

## Lecture Wednesday (12.10.2012)

The eleventh and last lecture will present correctness proofs for Haskell programs.

##### Topics

correctness proofs, relevant exam topics

##### Reading

chapter on correctness (Course Documents), chapter on complexity (Course Documents)