Week 41

Lecture Wednesday (9.10.2012)

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


space and time consumption, correctness proofs


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.


correctness proofs, relevant exam topics


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

Design by 1234.info | Modified by Peter Schneider-Kamp | CSS 2.0