All your answers will be auto-graded, so for coding problems you will be marked according to how many of our tests you pass (including example tests provided to you in the comments). Incorrect answers that pass tests will be penalised accordingly. The auto-grader will only mark code that you upload to the exam.
Writing period: 180 Minutes duration.
Study period: 15 Minutes duration (no use of keyboard).
Permitted materials: None, aside from the software environment provided.
You must attempt to answer all questions.
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
[16 Marks]
Higher Order Functions
Consider the following functions, which are defined in the file Mystery.hs in your IntelliJ project:
mystery_0 :: (a -> a) -> a -> a
mystery_0 f x = f (f x)
mystery_1 :: (a -> a) -> a -> a
mystery_1 f g = f g
mystery_2 :: (a -> a) -> (a -> a) -> a -> a
mystery_2 f g h = (f . g) h
For each of the following, mark either True or False. If uncertain, use the 'clear' button to clear your answer.
True | False | ||
mystery_0 and mystery_1 are equivalent functions | |||
mystery_0 (\b -> b) and mystery_1 (\b -> b) are equivalent functions | |||
mystery_2 (\b -> b + 1) (\b -> b + 2) and mystery_1 (\b -> b + 3) are equivalent functions | |||
mystery_2 (\b -> b - 1) (\b -> b * 2) and mystery_1 (\b -> (b - 1) * 2) are equivalent functions | |||
mystery_0 (\b -> b * b) and mystery_2 (\b -> b * b) (\b -> b * b) are equivalent functions | |||
mystery_0 (\b -> b - 2) and mystery_2 (\b -> b - 1) (\b -> b - 1) are equivalent functions | |||
mystery_2 (map (+2)) (map (3*)) and mystery_1 (map (\b -> (b * 3) + 2)) are equivalent functions | |||
mystery_2 (\b -> b) and mystery_1 are equivalent functions |
Question 2
[12 Marks]
Data types and functions
Using the incomplete template for Cities.hs
in your exam IntelliJ project, complete the unimplemented function (neighbouringCities
). Use the doctests provided to test your solution, and then upload your implementation of Cities.hs, by dragging your file into the box below.
The specification of the neighbouringCities
function is provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ slightly from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 3
[12 Marks]
Functions and numeric computation
Using the incomplete template for Shapes.hs
in your exam IntelliJ project, complete the unimplemented functions (area
, rectangles
, totalArea
, areaOfRectangles
, sortShapes
). Use the doctests provided to test your solutions, and then upload your implementation of Shapes.hs, by dragging your file into the box below.
The specifications of each function are provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ slightly from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 4
[40 Marks]
Binary trees and binary search trees
Using the incomplete template for Trees.hs
in your exam IntelliJ project, complete the unimplemented functions. Use the doctests provided to test your solutions, and then upload your implementation of Trees.hs, by dragging your file into the box below.
The specifications of each function are provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ slightly from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 5
[10 Marks]
Syntax, types, well-formed expressions
Some of the following expressions are not syntactically correct, while others are syntactically correct but do not have sensible types. Some are well-formed (syntactically correct and having a sensible type). Which of the following expressions is syntactically correct, and which is well-formed? In the case of a well-formed expression, identify a suitable type. Assume double :: Int -> Int
. If you use the computer to check your answers be prepared for some strange error messages, and choose your corresponding answer carefully.
5 i)
[1 Marks]
double double 0
not syntactically correct | |
syntactically correct, not sensibly typed | |
well-formed, Int | |
well-formed, Integer | |
well-formed, Num a => a | |
5 ii)
[1 Marks]
"++" == "+" ++ "+"
not syntactically correct | |
syntactically correct, not sensibly typed | |
well-formed, [Char] | |
well-formed, String | |
well-formed, Bool | |
5 iii)
[2 Marks]
[(+),(-)]
not syntactically correct | |
syntactically correct, not sensibly typed | |
well-formed, [a] | |
well-formed, [(a),(b)] | |
well-formed, Num a => [a -> a -> a] | |
5 iv)
[2 Marks]
[[],[[]],[[[]]]]
not syntactically correct | |
syntactically correct, not sensibly typed | |
well-formed, [t] | |
well-formed, [[t]] | |
well-formed, [[[t]]] | |
well-formed, [[[[t]]]] | |
5 v)
[2 Marks]
concat ["tea","for",'2']
not syntactically correct | |
syntactically correct, not sensibly typed | |
well-formed, Char | |
well-formed, [Char] | |
well-formed, [String] | |
5 vi)
[2 Marks]
concat ["tea","for","2"]
not syntactically correct | |
syntactically correct, not sensibly typed | |
well-formed, Char | |
well-formed, [Char] | |
well-formed, [String] | |
Question 6
[10 Marks]
Complexity
Consider the following two Haskell functions that both reverse a given list:
rev1 [] = []
rev1 (x:xs) = rev1 xs ++ [x]
rev2 = shunt []
where
shunt xs [] = xs
shunt xs (y:ys) = shunt (y:xs) ys
6 i)
[2 Marks]
What is the execution time complexity of rev1
(where n is the length of the given list)?
O(1) | |
O(log n) | |
O(n) | |
O(n2) | |
O(n3) | |
O(nn) | |
6 ii)
[3 Marks]
Justify your answer to the previous question.
The list cons (:) operation is O(1): constant time and there are n recursive calls | |
Binary search is O(log n): logarithmic time | |
All list operations are O(n): linear time | |
The append operation (++) is O(n): linear time and there are n recursive calls | |
The append operation (++) is O(n2): quadratic time and there are n recursive calls | |
The append operation (++) is O(nn): exponential time which dominates the n recursive calls | |
6 iii)
[2 Marks]
What is the execution time complexity of rev2
(where n is the length of the given list)?
O(1) | |
O(log n) | |
O(n) | |
O(n2) | |
O(n3) | |
O(nn) | |
6 iv)
[3 Marks]
Justify your answer to the previous question.
The list cons (:) operation is O(1): constant time and there are n recursive calls | |
Binary search is O(log n): logarithmic time | |
All list operations are O(n): linear time | |
The append operation (++) is O(n): linear time and there are n recursive calls | |
The append operation (++) is O(n2): quadratic time and there are n recursive calls | |
The append operation (++) is O(nn): exponential time which dominates the n recursive calls | |
Question 7
[20 Marks]
Structural Induction
Consider the following two Haskell functions, which are defined in the file Mystery.hs in your IntelliJ project:
s :: Num a => [a] -> a
s [] = 0 -- S1
s (x:xs) = x + s xs -- S2
m :: (a->a) -> [a] -> [a]
m _ [] = [] -- M1
m f (x:xs) = (f x) : (m f xs) -- M2
Your task is to prove by structural induction that the following property holds:
(s . m (*a)) = ((*a) . s)
7 i)
[1 Marks]
State the base case of the inductive proof. Enter your answer into the text box below.
7 ii)
[5 Marks]
Prove the base case of the induction using equational reasoning. Enter your answer into the text box below. Make sure to state all lemmas or definitions on which you rely for your proof. For example, you may use the definition of function composition:
(f . g) x
= f (g x) -- by definition of (.)
7 iii)
[2 Marks]
State the inductive hypothesis of the inductive proof. Enter your answer into the text box below.
7 iv)
[2 Marks]
State the inductive case of the inductive proof. Enter your answer into the text box below.
7 v)
[10 Marks]
Prove the inductive case of the induction using equational reasoning. Enter your answer into the text box below. Make sure to state all lemmas or definitions on which you rely for your proof. For example, you may use the arithmetic distributivity law:
x * (y + z)
= x * y + x * z -- by distribution of (*) over (+)