0/24 Questions Answered
Final Exam
STUDENT NAME
Search students by name or email… ” Q1 Instructions
0 Points
You must acknowledge the following integrity pledge before proceeding. Please read carefully and check all the boxes.
I am committed to being a person of integrity.
I pledge, as a member of the Australian National University community, to abide by and uphold the standards of academic integrity outlined in the ANU statement on honesty and plagiarism, and I am aware of the relevant legislation, and understand the consequences of me breaching those rules.
I will not actively communicate in any way with anyone else during this exam. This includes asking questions in any online forum.
Read and check off the following instructions:
1. You will need to be able to upload code files to this browser from your Haskell workspace. You must also make sure all code you upload compiles without errors.
Make sure this browser window is open on the machine where you plan to work.
If you are working on the ANU Linux VDI this browser window should be open in Linux, not on your personal machine.
If this browser window is not open where you plan to work close this window now and log back into the exam in a browser on your work machine.
2. This examination is timed.
Note the remaining time at the top right of this screen. Set an alarm for yourself if you need one.
3. Permitted materials. This is an open book exam. You might in particular find the course website, the Prelude documentation, and the Data.List documentation useful.
You may use any documentation you wish but all work must be your own.
Save Answer
Q2 Polymorphic type signatures 5 Points
For each of the following select True if the function signature is polymorphic and False otherwise.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. snd ::(a,b)->b True
False
2. tail :: [a] -> [a] True
False
3. takeWhile :: (a -> Bool) -> [a] -> [a] True
False
4. zipWith ::(a->b->c)->[a]->[b]->[c] True
False
5. id :: Bool -> Bool True
False
Save Answer
Q3 Polymorphic types 5 Points
For each of the following select True if the expression is a valid Haskell expression and False otherwise.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. length [(/), (*), (-), (+)] True
False
2. length [1.0, 2.0, 3.0, 4] True
False
3. length [cos, sin, (-), (+)] True
False
4. length [cos, sin, tan, (*2)] True
False
5. length [1/2, 1/3, 1/4, (\x -> 1/5) 1] True
False
Save Answer
Q4 Types 5 Points
For each of the following Haskell expressions select True if it is mathematically correct and results in a comparison of rational numbers, otherwise choose False.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. 1/10 * 10^56 == 10^55 True
False
2. 1/10 * 10^560 == 10^559 True
False
3. 1/10 * 10^560 – 10^559 < 0.0001 True
False
4. 1/10 * 10^56 == 10^55 True
False
5. 1/10 * toRational(10)^56 == toRational(10)^55 True
False
Save Answer
Q5 Algebraic Data Type 4 Points
Consider the following algebraic data type:
data Color = Black | White
data Pixel = Pixel Color Color Color
How many shades of grey are encoded by this data type if a Pixel 's intensity is encoded by the number of occurrences of White in the data constructor.
# 16 #8 #6 #4 #3
Save Answer
Q6 Typeclasses 4 Points
Consider the following algebraic data type:
data Temperature = Low | Normal | High
What is the minimum set of type classes this type should derive from to have comparison operators defined, including equality, and allow for printing its values to the GHCi prompt.
# (Eq, Ord, Show, Read) # (Ord, Show, Read)
# (Eq, Show, Read)
# (Ord, Eq, Show)
# (Eq, Show) Save Answer
Q7 Types 4 Points
For each of the following type declarations consider whether it is suitable to define a point on a Cartesian x-y coordinate plane such that:
memory overhead should be minimised, values of the type should not be compatible to
(Double,Double) , and
it should be possible to check if two points are equal.
Select True if it is suitable and False otherwise.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
newtype Point = Point (Double, Double) deriving Eq True
False
data Point = Point (Double, Double) deriving Eq True
False
type Point = (Double, Double) True
False
type Point = (Double, Double) deriving Eq True
False
Save Answer
Q8 Functions 5 Points
Consider the following type signature for a function that finds the length of a given list:
myLength :: [Int] -> Int
For each of the following definitions answer True if it a correct
implementation of that function and False otherwise.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. myLengthxs=sum[x`mod`2+(x+1) `mod`2|x<-xs] True
False
2. myLength list
|[] ==list=0
| otherwise = 1 + (myLength $ tail list) True
False
3. myLength = fst . last . zip [1..] True
False
4. myLength list = sum(map (1+) (map (0*) list)) True
False
5. myLength=foldl(\x_->x+1)0 True
False
Save Answer
Q9 Recursion and Lazy evaluation 4 Points
For each of the following statements, select whether it is True or False for Haskell.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point.
It is possible to write a recursive function that outputs ¡°abcdefg¡±
Recursive functions need at least one base case Recursion reduces the given problem to solve it
Recursive functions are always more efficient than non- recursive functions
Save Answer
Q10 Haskell 4 Points
For each of the following statements, select whether it is True or False for Haskell.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. The length of [[¡°abc¡±]] is 3 . True
False
2. String is an instance of class Eq . True
False
3. The built-in function zip can pair up elements of different types from two lists.
True False
4. Function application has higher priority than all other operators. True
False
Save Answer
Q11 Function signatures 9 Points
Consider the following Haskell function:
isIntersect [] _ = False
| otherwise = isIntersect xs (y:ys) || isIntersect (x:xs) ys
Q11.1 Polymorphism 5 Points
For each of the following type signatures select True if it is a valid signature for the function isIntersect or False otherwise.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1.
2.
3.
4.
isIntersect _ [] = False
isIntersect (x:xs) (y:ys)
|x==y =True
[Int] -> [Int] -> Bool True
False
a->a->Bool True
False
a->b->Bool True
False
[a] -> [a] -> Bool True
False
Eqa=>[a]->[a]->Bool True
False
Save Answer
Q11.2 Complexity 4 Points
How many comparisons x==y between elements occur when evaluating isIntersect [1,2,3] [4,5] ?
#6 #7 #8 #9 # 10
Save Answer
Q12 Complexity 5 Points
For each of the following statements, select whether it is True or False for Haskell.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. The worst case time complexity of Quick sort is worse than the average case time complexity of Merge sort.
True False
2. Bubble sort is on average slower than Insertion sort. True
False
3. Bubble and Insertion sort are in the same complexity class. True
False
4. The best case time complexities of Selection sort and Insertion sort are in different complexity classes.
True False
5. Binary search is on average n times faster than Merge sort. True
False
Save Answer
Q13 Complexity 4 Points
Given the following function:
positions :: Eq a => a -> [a] -> [Int]
positions x xs = [i | (x’, i) <- zip xs [0..], x == x']
What is its average case time complexity # O(1)
# O(n)
# O(log n)
# O(n log n) # O(n^2)
Save Answer
Q14 Higher order functions 5 Points
For each of the following statements, select whether it is True or False for Haskell.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. foldl and foldr are equivalent and interchangeable True
False
2. The following two definitions are equivalent
map f xs = [f x | x <- xs] and
map _ [] = []
map f (x:xs) = f x : map f xs
True False
zipWith (,) is equivalent to zip True
False
The following two definitions are equivalent:
count x xs = length [x' | x' <- xs, x == x'] and
count x xs = sum (map (\x' -> if x == x’ then 0 else 1) XS) True
False
The composition operator . and application operator $ are interchangeable.
True False
Save Answer
Q15 Trees 3 Points
For each of the following statements, select whether it is True or False for Haskell.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. The following data type represents a multiway (Rose) tree:
data Tree a = Leaf a | Node a (Tree a) (Tree a) (Tree a) True
False
2. Given a data type
data Tree a = Leaf a | Node a (Tree a) (Tree a) then the following value stores a binary search tree:
Node (Node (Leaf 11) 13 (Leaf 14)) 16 (Node (Leaf 12) 17 (Leaf True
False
3. Given a data type
data Tree a = Node a [Tree a] deriving Show
then the following function implements Depth First Search:
1.
2.
3.
4.
5.
3.
4.
5.
flatten :: Tree a -> [a]
True False
Save Answer
Q16 Testing 4 Points
++ (flatten $ last children)
flatten (Node g []) = [g]
flatten (Node g children) = [g] ++ (flatten $ head children)
For each of the following statements, select whether it is True or False for Haskell.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. To test a certain function property, Quickcheck generates random inputs and verifies if the property holds.
True False
2. Most commonly in practice assert is true unless there is a bug. True
False
3. If white box testing is conducted, no code of the tested functions is used in designing the tests.
True False
4. The Haskell toolchain does not provide any functionality for testing code performance.
True False
Save Answer
Q17 Lazy evaluation 4 Points
For each of the following statements, select whether it is True or False for Haskell.
Each correct answer gains you 1 point while each incorrect answer loses you 0.5 point. An unanswered question neither gains nor loses you points.
1. Given
inf :: Int
inf = 1 + inf
The following expression called by value will never terminate:
snd (inf, 0) True
False
2. The following expression is a non-terminating sequence:
fib = 0:1:[a + b | (a, b) <- zip fib (tail fib)] True
False
3. Lazy evaluation can require a lot more space than non-lazy evaluation.
True False
4. The following expression contains two reducible expressions:
snd (4*2, 4+3) True
False
Save Answer
Q18 Haskell Programming 100 Points
The following programming questions use template files which you can access by clicking on the links in the questions below.
You must submit your answer using the link provided in each question to upload the file. You will not be able to push your solution to gitlab.
As an alternative to clicking on the links, you can clone the files from the gitlab repository at https://gitlab.cecs.anu.edu.au/comp1100/comp1100-2020s2-final using the command:
git clone https://gitlab.cecs.anu.edu.au/comp1100/comp1100-2020s2
Q18.1 Functions 14 Points
Click on the link Triathlon.hs to download a Haskell script containing templates (instructions included) for the functions
calories and totalCalories .
If your browser downloads the file as Triathlon.hs.txt with the extension .txt make sure to rename the file to
Triathlon.hs .
You must complete both the functions calories and
totalCalories .
Make sure to edit and test using ghci before uploading using the
following link:
$ Please select file(s) Select file(s)
Save Answer
Q18.2 Data Types 14 Points
Click on the link Persons.hs to download a Haskell script containing templates (instructions included) for the functions show , isMale and over20 .
If your browser downloads the file as Persons.hs.txt with the extension .txt make sure to rename the file to Persons.hs .
You must complete both the functions show , isMale and over20 .
Make sure to edit and test using ghci before uploading using the following link:
$ Please select file(s) Select file(s) Save Answer
Q18.3 Recursive Data Types 18 Points
Click on the link DNA.hs to download a Haskell script containing templates (instructions included) for the functions lenSeq ,
numEqLetters and numSubSeqs .
If your browser downloads the file as DNA.hs.txt with the
extension .txt make sure to rename the file to DNA.hs .
You must complete both the functions lenSeq , numEqLetters
and numSubSeqs .
Make sure to edit and test using ghci before uploading using the
following link:
$ Please select file(s) Select file(s)
Save Answer
Q18.4 Functions 16 Points
Click on the link Election.hs to download a Haskell script containing templates (instructions included) for the functions countBallot ,
rankBallots and winnerBallot .
If your browser downloads the file as Election.hs.txt with the
extension .txt make sure to rename the file to Election.hs . You must complete both the functions countBallot ,
rankBallots and winnerBallot .
Make sure to edit and test using ghci before uploading using the
following link:
$ Please select file(s) Select file(s)
Save Answer
Q18.5 Trees 14 Points
Click on the link Expressions.hs to download a Haskell script containing templates (instructions included) for the functions show and eval .
If your browser downloads the file as Expressions.hs.txt with the extension .txt make sure to rename the file to
Expressionshs .
You must complete both the functions show and eval .
Make sure to edit and test using ghci before uploading using the following link:
$ Please select file(s) Select file(s) Save Answer
Q18.6 Trees 24 Points
Click on the link Heap.hs to download a Haskell script containing templates (instructions included) for the functions isBalanced and
isHeap .
If your browser downloads the file as Heap.hs.txt with the
extension .txt make sure to rename the file to Heap.hs .
You must complete both the functions isBalanced and isHeap .
Make sure to edit and test using ghci before uploading using the following link:
$ Please select file(s) Select file(s) Save Answer
Save All Answers
Submit & View Submission !
19
-fi