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]
True/False questions
Consider the following type signatures
foo :: (Int,Bool) -> Char
bar :: Int -> Bool -> (Int,Bool)
Mark True for each of the following statements if it is correct, and False if not.
True | False | ||
foo (3 True) can be given a type | |||
The type of bar could also be written Int -> (Bool -> (Int,Bool)) | |||
bar 3 can be given a type | |||
foo . bar can be given a type | |||
If bar 3 True does not terminate, foo (bar 3 True) will certainly also not terminate |
Question 2
[10 Marks]
Multiple choice questions
For each of the following questions, mark the correct answer.
2 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 | |
2 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 | |
2 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 | |
2 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 | |
2 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 3
[5 Marks]
Great Minus Less (GreatMinusLess.hs)
Using the incomplete template GreatMinusLess.hs
in your final exam IntelliJ project, complete the undefined function greatMinusLess
. The specification of the greatMinusLess
function is provided in the comments immediately above the function. You will need to adhere to that specification. 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 GreatMinusLess.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 4
[10 Marks]
Mobile Operating Systems (MobileOS.hs)
Using the incomplete template MobileOS.hs
in your final exam IntelliJ project, complete the two undefined functions latestRelease
and validRelease
.
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous question.
Question 5
[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 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]
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 questions.
Question 7
[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 8
[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 9
[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.
9 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) | |
9 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) | |
9 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) | |
9 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) | |
9 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) | |