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)