PROGRAMMING AS PROBLEM SOLVING COMP1100
checksum: AAAAA bytes: 72
Important notice: Code templates for answers to coding questions in this exam can be found in the accompanying IntelliJ project. You can place this Web page for the exam in a window side-by-side with 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 can load your solution codes into GHCi and test them out. You can also make use of QuickCheck and doctest in testing.
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.
Question 1 [12 Marks]
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.
Recall the following functions from the Data.Char library:
toUpper :: Char -> Char
isUpper :: Char -> Bool
toUpper converts letters to their corresponding upper-case letters, and leaves other characters unchanged. isUpper returns True for upper-case letters, and False otherwise.
There are corresponding functions toLower and isLower for lower-case letters.
For each of the following, mark either True or False. If uncertain, use the ‘clear’ button to clear your answer.
Each correct answer gains you 2 marks, each incorrect answer loses you 1 mark, while a question left unanswered neither loses nor gains marks.
True False
Clear
Clear Clear
The type of expression (map toUpper) is [Char] -> [Char]
The type of expression (filter isUpper) is [Char] -> Bool
The type of expression (toUpper ‘a’) is [Char] The following expression is evaluated to True
map toUpper [‘c’,’A’,’m’,’E’,’l’] == [‘C’,’A’,’M’,’E’,’L’]
The following expression is evaluated to True filter isUpper [‘c’,’A’,’m’,’E’,’l’] == [False]
Functions (toLower . toUpper) and toUpper always produce the same outputs on the same inputs Question 2 [14 Marks] Syntax
Clear Clear Clear
Assume a function plus :: Int -> Int -> Int has already been defined.
Some of the following expressions might be accepted by a Haskell compiler or interpreter such as ghci. Others might be accepted with warnings, or rejected. Select whether each of the expressions below are accepted or rejected by a Haskell compiler, along with the correct description accompanying the item.
Each correct answer gains you 2 marks, each incorrect answer loses you 1 mark,while a question left unanswered neither loses nor gains marks.
2 i) [2 Marks] plus plus 1 2 3
Accepted because there are implicit parentheses and the compiler will be able to infer them Accepted because Haskell does not need to infer the type signature of plus, since it is defined
(plus :: Int -> Int -> Int)
Rejected because the expression is ill-typed
Rejected because a binary function like plus must only be written in infix notation, e.g. 1 plus 2
Rejected because a binary function like plus must only be written in infix notation with parentheses, e.g. 1 (plus) 2
Clear
2 ii) [2 Marks] plus == plus
Accepted because (==) is comparing the same functions
Rejected because plus returns an Int, but (==) returns a Bool
Rejected because Int is not a member of the Eq class
Rejected because Int -> Int -> Int is not a member of the Eq class Rejected because Int -> Int -> Int is not a member of the Show class
Clear
2 iii) [2 Marks] c = [] ++ [plus]
Accepted and the type of c is [Int -> Int -> Int]
Accepted and the type of c is [[Int -> Int -> Int]]
Accepted and the type of c is [Int] -> [Int] -> [Int]
Rejected because (++) takes two lists, whereas plus takes two Ints
Rejected because the type of [] is [a], which is more general than the type of [plus]
Clear
2 iv) [2 Marks]
z = True : False : []
Accepted and the type of z is Bool
Accepted and the type of z is [Bool]
Accepted with a warning because the empty list is unnecessary
Rejected because the compiler is unable to infer the type since the parentheses are missing Rejected because expression (True : False) is ill-typed
Clear
2 v) [2 Marks]
allTrue l = case l of
[] -> True
x:xs -> x && allTrue x
Accepted with a warning because there is no [x] case, so the pattern matches are non-exhaustive Accepted with a warning because the variable x is named but not used
Rejected because the output is an expression of type Bool
Rejected because allTrue is applied to the argument of the wrong type in the recursive call Rejected because the function could be written in one line using foldr
Clear
2 vi) [2 Marks]
f :: (Eq a) => a -> a -> a fab
|a==b =b | otherwise = a
Accepted and expression (f 3 4) is evaluated to 3
Accepted and expression (f 3 4) is evaluated to 4
Accepted but expression (f 3 3) would produce an error
Rejected because we could define it more concisely as (\x y -> x) Rejected because there is a built-in Prelude function const and it is better
Clear
2 vii) [2 Marks]
e = foldl (++) [] [[True],[False,True]]
Accepted and the type of e is Bool
Accepted and the type of e is [Bool]
Accepted and the type of e is [[Bool]]
Rejected because (++) is an operation on lists and its arguments are of type Bool here Rejected because expression (foldl (++) []) must take an argument of type [Bool], but [[True],[False,True]] is of type [[Bool]].
Clear
Question 3 [12 Marks] Boolean Expressions
Using the incomplete template for BoolExpressions.hs in your exam IntelliJ project, complete the unimplemented functions (allEqual, allDifferent, exactlyTwoEqual). Use the doctests provided to test your solutions, and then upload your implementation of BoolExpressions.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 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.
Drag and drop BoolExpressions.hs below
!
Question 4 [5 Marks] Abstraction, Algebraic Datatypes, Arithmetics
Using the incomplete template for Shapes.hs in your exam IntelliJ project, complete the unimplemented function (perimeter). Use the doctests provided to test your solution, and then upload your implementation of Shapes.hs, by dragging your file into the box below.
The specification of the perimeter 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 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.
Drag and drop Shapes.hs below
!
Question 5 [7 Marks] Enumeration Datatypes, Tuples, HOF
Using the incomplete template for Animals.hs in your exam IntelliJ project, complete the unimplemented function (animalsInContinent). Use the doctests provided to test your solutions, and then upload your implementation of Animals.hs, by dragging your file into the box below.
The specifications the animalsInContinent 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 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.
Drag and drop Animals.hs below
!
Question 6 [10 Marks] Rose Trees
Using the incomplete template for Trees.hs in your exam IntelliJ project, complete the unimplemented functions (isRootElement, size, addRootValue and leaves). 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 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.
Drag and drop Trees.hs below
!
Question 7 [10 Marks] Abstraction, Lists, Function composition, Recursion
Using the incomplete template for IncreasingDifferences.hs in your exam IntelliJ project, complete the unimplemented function (increasingDifferences). Use the doctests provided to test your solutions, and then upload your implementation of IncreasingDifferences.hs, by dragging your file into the box below.
The specifications the increasingDifferences 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 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.
Drag and drop IncreasingDifferences.hs below
!
Question 8 [10 Marks] Abstraction, Lists, HOF
Using the incomplete template for Primes.hs in your exam IntelliJ project, complete the unimplemented functions (isPrime, isEmirp, and emirps). Use the doctests provided to test your solutions, and then upload your implementation of Primes.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 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.
Drag and drop Primes.hs below
!
Question 9 [10 Marks] Abstraction, Lists, HOF
Using the incomplete template for RLE.hs in your exam IntelliJ project, complete the unimplemented functions (encode and decode). Use the doctests provided to test your solutions, and then upload your implementation of RLE.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 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.
Drag and drop RLE.hs below
!
Question 10 [10 Marks] Complexity
Open the file Complexity.hs in your exam IntelliJ project. Three functions are defined: remove, smallest, and selSort. 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.
10 i) [2 Marks]
What is the best case time complexity of remove?
O(1)
O(log n)
O(n)
O(n log n) O(n2)
Clear
10 ii) [2 Marks]
What is the average case time complexity of remove?
O(1)
O(log n)
O(n)
O(n log n) O(n2)
Clear
10 iii) [2 Marks]
What is the worst case time complexity of remove?
O(1)
O(log n)
O(n)
O(n log n) O(n2)
Clear
10 iv) [2 Marks]
What is the worst case time complexity of smallest?
O(log n) O(n)
O(n log n) O(n2)
O(n3) Clear
10 v) [2 Marks]
What is the worst case time complexity of selSort?
O(log n) O(n)
O(n log n) O(n2)
O(n3) Clear