PROGRAMMING AS PROBLEM SOLVING COMP1100
checksum: AAAAA bytes: 60
Important notice: Code templates for programming questions in this exam can be found in the accompanying IntelliJ project. You can place this Web page for the exam next to the IntelliJ project window, so that you can conveniently switch between them while working on your answers. You will also want to open the Terminal tool in IntelliJ, in which you test your solution code with ghci. You can also make use of doctest for testing.
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.
Each correct answer gains you 2 marks, each incorrect answer loses you 1 mark, while a question left unanswered neither loses nor gains marks. The minimum total mark for this question is 0.
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.
Clear Clear Clear Clear Clear
Each correct answer gains you 2 marks, each incorrect answer loses you 1 mark, while a question left unanswered neither loses nor gains marks. The minimum total mark for this question is 0.
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
|x>=0 =x | otherwise = -x
myAbs x = case x>=0 of
True -> x
False -> -x
myAbs x = case x<0 of
True -> -x
_ ->x
myAbs x = sqrt (x*x)
myAbs x = max x (-x)
Clear
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
Clear
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
Clear
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
Clear
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
Clear
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.
Drag and drop Numbers.hs below
!
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.
Drag and drop AU.hs below
!
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.
Drag and drop Coffee.hs below
!
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.
Drag and drop ListFunctions.hs below
!
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.
Drag and drop Trees.hs below
!
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.
Each correct answer gains you 2 marks, each incorrect answer loses you 1 mark, while a question left unanswered neither loses nor gains marks.
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)
Clear
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)
Clear
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)
Clear
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)
Clear
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)
Clear