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)