# Week 51

## Exercise Tuesday (20.12.2011)

1) To represent graphs we can use finite lists of pairs of nodes. Each pair represents an edge between two nodes:

type Graph a = [(a,a)]

Consider the graph `g` over integers above.
A representation of `g` as an object of type `Graph Int` could be:

[(0,1),(1,3),(3,1),(0,2),(1,0),(2,2)]

The following data structure represents trees where every node may have an arbitrary number of children:

data Tree a = Node a [Tree a]

Consider the tree `t` above that is the result of *unfolding* the graph `g` starting from `0`.
A representation of the first four layers of the infinite tree `t` as an object of type
`Tree Int` in Haskell could be:

Node 0 [Node 1 [Node 3 [Node 1 [..., ...]], Node 0 [Node 1 [..., ...], Node 2 [...]], Node 2 [Node 2 [Node 2 [...]]]

Implement the following functions in Haskell:

- The function
`unfold`takes a graph`g`and a node`x`and returns the tree which results from unfolding`g`starting from`x`. Note that for a cyclic graph, the tree can be infinite. - The function
`pruneTree :: Tree a -> Int -> Tree a`takes a tree`t`and an integer`n`and returns the first`n`layers of the tree. This corresponds to the function`take`on lists. For example, the expression`pruneTree (unfold [(0,1),(1,3),(3,1),(0,2),(1,0),(2,2)] 0) 4`should evaluate to the expression`Node 0 [Node 1 [Node 3 [Node 1 []], Node 0 [Node 1 [], Node 2[]]], Node 2 [Node 2 [Node 2 []]]`.

2) The two functions `fibs1` and `fibs2` compute the infinite list of Fibonacci numbers
starting from `0` and `1`, i.e., the list `[0,1,1,2,3,5,8,13,21,34,55,...]`. The
Fibonacci sequence *fib*_{0}, *fib*_{1}, ... is defined by *fib*_{0} = 0,
*fib*_{1} = 1, and *fib*_{n+2} = *fib*_{n+1} + *fib*_{n}.

fibs1 = map fib [0..] where

fib 0 = 0

fib 1 = 1

fib (n+2) = (fib (n+1)) + (fib n)

fibs2 = map fib [0..] where

fib n = fib' n 0 1 where

fib' n a b | n == 0 = a

| True = fib' (n-1) (a+b) a

Analyze the complexity of evaluating the two expressions `take n fibs1`
and `take n fib2` depending on `n`. Give upper bounds using the O-notation that
are as low as possible. Here, you can assume that addition has constant complexity, i.e.,
evaluating `n + m` is in O(1).

Implement a function `fibs3` which computes the same list as `fibs1` and `fibs2`
by using a cyclic data structure. Analyze the complexity of evaluating `take n fibs3` depending
on `n` as before.

To measure the amount of reductions, in hugs you can type `:s +s` to switch on the "profiler".
This might give you an idea of the behaviour for different `n`.

3) Implement a function `sumList :: IO ()` in Haskell. If `sumList` is executed,
the user can type in a list of integers on the keyboard in standard Haskell notation.
Afterwards, the sum of these integers is printed on the screen using the function putStr.
For example, if the user enters the string `[1, -5, 70]`, then the number `66`
is displayed on the screen.

In order to convert a `String` into an `[Int]` you may use the built-in function
`read :: String -> [Int]`. For example, `read "[1, -5, 70]" :: [Int]` will read
in the list of integers `[1, -5, 70]`.

4) Write a program in Haskell which tells the user to think of a secret integer number. Then the program asks the user for a lower and an upper bound of an interval containing the secret number. Afterwards, the computer tries to guess the secret number and asks the user if its guess is the right one or the secret number is smaller or bigger. The program repeats guessing until it finds the secret number. It should try to use as few guesses as possible.

Here is a successful session (where inputs by the user are enclosed in underscores):

Try to think of a number in a certain range!

Please enter the lower bound of your range: _1_

Please enter the upper bound of your range: _100_

Searching from 1 to 100

My guess #1: 50

Am I (r)ight or is your number (s)maller or (b)igger? _s_

Smaller? Let me see ...

My guess #2: 25

Am I (r)ight or is your number (s)maller or (b)igger? _b_

Bigger? Well, I think ...

My guess #3: 37

Am I (r)ight or is your number (s)maller or (b)igger? _s_

Smaller? Let me see ...

My guess #4: 31

Am I (r)ight or is your number (s)maller or (b)igger? _b_

Bigger? Well, I think ...

My guess #5: 34

Am I (r)ight or is your number (s)maller or (b)igger? _r_

Yes! I made it!

Here is another successful session:

Try to think of a number in a certain range!

Please enter the lower bound of your range: _1_

Please enter the upper bound of your range: _100_

Searching from 1 to 100

My guess #1: 50

Am I (r)ight or is your number (s)maller or (b)igger? _b_

Bigger? Well, I think ...

My guess #2: 75

Am I (r)ight or is your number (s)maller or (b)igger? _s_

Smaller? Let me see ...

My guess #3: 62

Am I (r)ight or is your number (s)maller or (b)igger? _b_

Bigger? Well, I think ...

My guess #4: 68

Am I (r)ight or is your number (s)maller or (b)igger? _b_

Bigger? Well, I think ...

My guess #5: 71

Am I (r)ight or is your number (s)maller or (b)igger? _b_

Bigger? Well, I think ...

My guess #6: 73

Am I (r)ight or is your number (s)maller or (b)igger? _b_

Bigger? Well, I think ...

... it is 74!

5) 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.

## Lecture Wednesday (21.12.2011)

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)