Total marks: 100
Writing period: 180 Minutes duration.
Study period: 15 Minutes duration (no use of keyboard or selection of answers).
Permitted materials: None, aside from the software environment provided.
Note that links to the specification of the Prelude and Data.List libraries are provided.
Questions are not of equal value.
All questions must be completed on this web form.
Your work is automatically saved and recorded as you type.
This is a closed examination. You may not copy this exam.
Question 1
[10 Marks]
Multiple choice questions
For each of the following questions, mark the correct answer.
1 i)
[2 Marks]
Functions, lists, and types
Consider the following type signature
baz :: Double -> Double -> [Char]
What is the type of [baz]
?
[Double -> Double -> Char] | |
[Double -> Double -> String] | |
[Double] -> [Double] -> [Char] | |
[Double] -> [Double] -> [String] | |
[baz] cannot be given a type | |
1 ii)
[2 Marks]
Testing
When you conduct white box testing, you...
Test that large numbers of random inputs obey some property | |
Test the code to measure speed and memory usage | |
Test the whole program, and not individual parts | |
Use the form of the actual code to guide your choice of tests | |
Use the specification to guide your choice of tests | |
1 iii)
[2 Marks]
Folds
foldr (:)
is mathematically equivalent to
\x y -> (reverse x) ++ y | |
\x y -> x : y | |
\x y -> x ++ y | |
\x y -> y : x | |
\x y -> y ++ x | |
1 iv)
[2 Marks]
Games
Which of the following statements about alpha-beta pruning is true?
It is risky, because there is a small chance that the best move might get pruned away | |
It is slower than minimax but returns better answers | |
It requires that your heuristic has some type in the type class Bounded | |
It requires the use of rose trees | |
It will return the same answer as minimax if you have enough time to explore the whole game tree | |
1 v)
[2 Marks]
Ad hoc polymorphism
Which of the following is the most general type signature, i.e. can be instantiated in the largest number of ways?
Eq a => a -> a -> a | |
(Eq a, Eq b) => a -> b -> a | |
(Eq a, Ord a) => a -> a -> a | |
Ord a => a -> a -> a | |
(Ord a, Ord b) => a -> b -> a | |
Question 2
[10 Marks]
Approximating e (ApproximatingE.hs)
Using the incomplete template ApproximatingE.hs
in your final exam IntelliJ project, complete the two undefined functions fact
and eApprox
. The specification of these functions is provided in the comments immediately above them. You will need to adhere to these specifications. You may use the doctests provided to help test your solutions. These doctests may not be exhaustive, and so passing all the available doctests may not guarantee full marks. We may also deduct marks for poor style.
You can upload your implementation of ApproximatingE.hs by dragging your file into the box below. You will receive automatic feedback on whether your code compiles, but no feedback on the correctness of your code. If you drag your file into the box again, it will overwrite your previous upload. Your markers will only see your code if it is uploaded into your exam. Therefore it is essential that you upload your code into this exam, in the browser.
Question 3
[10 Marks]
Movies (Movies.hs)
Using the incomplete template Movies.hs
in your final exam IntelliJ project, complete the two undefined functions show
and unrestrictedTitles
.
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous question.
Question 4
[20 Marks]
List Functions (ListFunctions.hs)
Using the incomplete template ListFunctions.hs
in your final exam IntelliJ project, complete the four undefined functions stutter
, take
, elemIndices
, and ascendingPrefix
.
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous questions.
Question 5
[15 Marks]
Trees (Trees.hs)
Using the incomplete template Trees.hs
in your final exam IntelliJ project, complete the three undefined functions isBinary
, roseToBinary
, and isPath
.
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous questions.
Question 6
[10 Marks]
Complexity
Open the file Complexity.hs
in your final exam IntelliJ project. Three functions are defined: rightOfList
, rightOfBTree
, and rightOfRose
. Answer the following questions about these functions' time complexity.
6 i)
[2 Marks]
What is the best case time complexity of rightOfList
?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
6 ii)
[2 Marks]
What is the average case time complexity of rightOfList
?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
6 iii)
[2 Marks]
A BinaryTree
is balanced if for any two leaves the difference between their depth is at most 1. What is the worst case time complexity of rightOfBTree
on balanced input?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
6 iv)
[2 Marks]
What is the best case time complexity of rightOfRose
? Make no assumption that the tree is balanced.
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
6 v)
[2 Marks]
What is the worst case time complexity of rightOfRose
? Make no assumption that the tree is balanced.
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
Question 7
[12 Marks]
Lambda Calculus
In your answers below, you may write \
for λ
. Write ->
to indicate that an expression beta-reduces to another, and <-
if you wish to indicate that an expression reduces from another, e.g.
(\x.x) y
-> y
<- (\x.y) z
7 i)
[2.5 Marks]
Present every step of the lazy evaluation of the following term in the text box below:
(λx.(λy.x y) y)((λz.z) y)
7 ii)
[2.5 Marks]
Present every step of the eager evaluation of the same term:
(λx.(λy.x y) y)((λz.z) y)
7 iii)
[3 Marks]
The combinator Y
is defined as:
λf.(λx.f (x x))(λx.f (x x))
Show that Y F
is beta-equal to F(Y F)
for any term F
.
7 iv)
[4 Marks]
Define a lambda calculus term that acts as 'less than or equal to' on natural numbers: when applied to two natural numbers, it should return True
if the first input is less than or equal to the second, and False
if it is larger.
You do not have to write the lambda term out in full, but rather may assume you have access to the following encodings discussed in lectures: Y
, true
, false
, if... then... else
, all natural numbers, succ
, pred
, iszero
, and plus
.
Question 8
[13 Marks]
Program Proof
Consider the following Haskell functions:
length :: [a] -> Int
length [] = 0 -- L1
length (x:xs) = 1 + length xs -- L2
mirror :: [a] -> [a]
mirror = helper [] -- M1
helper :: [a] -> [a] -> [a]
helper xs [] = xs -- H1
helper xs (y:ys) = helper (y:(xs ++ [y])) ys -- H2
Your task is to prove that the following property holds for all lists xs
:
length (mirror xs) = 2 * length xs
You may at any time use the following lemma, without proof, for any list xs
and element x
:
length (xs ++ [x]) = length xs + 1 -- Lemma1
8 i)
[1 Marks]
You will need to use induction to prove a lemma about the function helper
. We will call this lemma Lemma2
. State this lemma in the text box below.
Hint: if you are not sure, attempt question (vi) and see where you get stuck.
8 ii)
[1 Marks]
State the base case for Lemma2
.
8 iii)
[2 Marks]
Prove the base case of Lemma2
using equational reasoning. Make sure that you write every line of your argument, and give a reason for each step beside that line. For example, if an equation follows from the first line of the definition of length
, write (L1)
beside it. If an equation follows by standard laws of mathematics, write (maths)
beside it.
8 iv)
[1 Marks]
State the induction hypothesis for Lemma2
.
8 v)
[6 Marks]
Prove the induction case for Lemma2
using equational reasoning. Make sure that you write every line of your argument, and give a reason for each step beside that line.
8 vi)
[2 Marks]
Prove the theorem
length (mirror xs) = 2 * length xs
using equational reasoning. Make sure that you write every line of your argument, and give a reason for each step beside that line.