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 :: Char -> a -> b -> a
bar :: Char
Mark True for each of the following statements if it is correct, and False if not.
True | False | ||
foo is ad hoc polymorphic | |||
The type of foo could be written as Char -> (a -> (b -> a)) | |||
foo 't' 'k' 'g' can be given a type | |||
foo '1' [1,2,3] True [1] can be given a type | |||
The type of [bar] is String |
Question 2
[10 Marks]
Multiple choice questions
For each of the following questions, mark the correct answer.
2 i)
[2 Marks]
Functions in Haskell
Which of the following definitions is not a correct implementation of absolute value on integers?myAbs :: Int -> Int
myAbs x | |
myAbs x = case x>=0 of | |
myAbs x = case x<0 of | |
myAbs x = sqrt (x*x) | |
myAbs x = max x (-x) | |
2 ii)
[2 Marks]
Testing
If you conduct white box testing, you ...
Use your specification to design your tests | |
Use your code to design your tests | |
Must write your tests in a separate file | |
Test the speed of the code, not the correctness | |
Test the whole program, not individual parts | |
2 iii)
[2 Marks]
Type Classes
Which statement about Haskell is false?
Any type that is an instance of Ord is also an instance of Eq | |
Bool is an instance of Ord | |
['a'..'e'] evaluates to "abcde" because Char is an instance of Enum | |
Type classes allow function names to have different definitions when applied to different types | |
In Haskell, overloading is resolved when the function is run | |
2 iv)
[2 Marks]
Trees
Which statement is false given the following code?data BinaryTree a = Null | Node (BinaryTree a ) a (BinaryTree a)
tr :: BinaryTree Int
tr = Node (Node Null 5 Null) 7 (Node (Node Null 8 Null) 10 (Node (Node Null 11 Null) 20 (Node Null 21 Null)))
The root of tr has value 7 | |
tr has 4 leaves | |
tr is a binary search tree | |
The height (largest number of edges between the root and a leaf) of tr is 4 | |
tr has 7 nodes and 6 edges | |
2 v)
[2 Marks]
Games
Which of the following statements is false?
Given enough time, Minimax always returns the same solution as alpha-beta pruning | |
Decisions made using a heuristic might not be optimal | |
In Alpha-beta pruning, alpha is the lower bound of possible values | |
A branch that is pruned is guaranteed not to be played by any player | |
Minimax should only be used for zero-sum games | |
Question 3
[10 Marks]
Numbers (Numbers.hs)
Using the incomplete template Numbers.hs
in your final exam IntelliJ project, complete the two undefined functions returnBigger
and returnMedian
. The specification of the functions are 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 Numbers.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
[15 Marks]
AU (AU.hs)
Using the incomplete template AU.hs
in your final exam IntelliJ project, complete the three undefined functions show
, bigCities
and cityInState
.
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous questions.
Question 5
[10 Marks]
Coffee (Coffee.hs)
Using the incomplete template Coffee.hs
in your final exam IntelliJ project, complete the two undefined functions toPay
and orderSummary
.
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous question.
Question 6
[20 Marks]
List Functions (ListFunctions.hs)
Using the incomplete template ListFunctions.hs
in your final exam IntelliJ project, complete the four undefined functions removeElem
, countOccur
, isMatrix
and separateList
.
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous questions.
Question 7
[15 Marks]
Trees (Trees.hs)
Using the incomplete template Trees.hs
in your final exam IntelliJ project, complete the three undefined functions isTernary
, numLeaves
and isSorted
.
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous questions.
Question 8
[10 Marks]
Complexity
Open the file Complexity.hs
in your final exam IntelliJ project. Two functions are defined: findMax
and insert
. Answer the following questions about these functions' time complexity.
8 i)
[2 Marks]
What is the best case time complexity of findMax
?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
8 ii)
[2 Marks]
What is the worst case time complexity of findMax
?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
8 iii)
[2 Marks]
A tree is balanced if the depth of every leaf differs by at most one.
Assuming that the input tree is balanced, what is the best case time complexity of insert
?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
8 iv)
[2 Marks]
Assuming that the input tree is balanced, what is the average case time complexity of insert
?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
8 v)
[2 Marks]
If we do not assume that the input tree is balanced, what is the worst case time complexity of insert
?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |