PROGRAMMING AS PROBLEM SOLVING COMP1100
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.
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.
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 (3 True) can be given a type Clear
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
Clear
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
Clear
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
Clear
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
Clear
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
Clear
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.
The type of bar could also be written Int -> (Bool -> (Int,Bool))
Clear bar 3 can be given a type Clear foo . bar can be given a type Clear Clear
If bar 3 True does not terminate, foo (bar 3 True) will certainly also not terminate Question 2 [10 Marks] Multiple choice questions
Each correct answer gains you 2 marks, each incorrect answer loses you 1 mark, while a question left unanswered neither loses nor gains marks.
Drag and drop GreatMinusLess.hs below
!
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.
!
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.
Drag and drop MobileOS.hs below
Question 5 [10 Marks] Approximating e (ApproximatingE.hs)
Using the incomplete template ApproximatingE.hs in your final exam IntelliJ project, complete the two undefined
Drag and drop ApproximatingE.hs below
!
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.
!
functions stutter , take , elemIndices , and ascendingPrefix .
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as
Drag and drop Movies.hs below
Question 7 [20 Marks] List Functions (ListFunctions.hs)
Using the incomplete template ListFunctions.hs in your final exam IntelliJ project, complete the four undefined
for the previous questions.
!
isBinary , roseToBinary , and isPath .
The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as
Drag and drop ListFunctions.hs below
Question 8 [15 Marks] Trees (Trees.hs)
Using the incomplete template Trees.hs in your final exam IntelliJ project, complete the three undefined functions
for the previous questions.
!
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)
Clear
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)
Clear
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)
Drag and drop Trees.hs below
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)
Clear
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)
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.
Clear