COMP1100 (PROGRAMMING AS PROBLEM SOLVING)
FINAL EXAM, SEMESTER 1, 2020
DO NOT EDIT THIS FILE Important Notes
If you are a COMP1130 student, this is not the correct exam paper. Consult the exam instructions on our website to see how to access the correct repository.
Total marks: 100
Writing period: 210 Minutes duration. This includes time spent accessing and submitting your exam via Gitlab. We will use the same clock that you can see if you search for Canberra time with Google.
Permitted materials: This is an open book exam, and you may use any resources you wish. You might in particular find the course website, the Prelude documentation, and the Data.List documentation useful.
Important note: You may not actively communicate with anyone else during this exam. This includes asking questions in any online forum.
Questions are not of equal value.
True/False and Multiple choice questions must be completed in the given file, Answer.md Programming questions must be completed in the Haskell files given in the folder, ProgrammingQuestions
Instructions for Access and Submission
Fork this project to your own namespace. Do not change the name of this repository. Once you have forked the exam, you can Clone with HTTPS to your local machine (clone with SSH will not work).
Commit and push your work to GitLab frequently. We recommend that you do this at least after you complete each question.
Check Gitlab in your browser to confirm that your pushes into your forked version of the exam were successful.
When the exam is over at 6:00pm Canberra time, students will be automatically blocked from this repository unless they have particular arrangements for a longer exam time. Gitlab pushes can take time, so do not leave your final push until 5:59pm.
Question 1 [10 Marks] True/False questions Consider the following type signatures.
foo :: Eq a => (Char -> a) -> Int
bar :: Eq a => Char -> a
Use the file Answer.md to mark True for each of the following statements if it is correct, and False if not, by placing an x in the square brackets. This means that [ ] should become [x] , while the options you do not wish to select should remain blank.
Each correct answer gains you 2 marks, and 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.
1 i) foo is a higher order function
1 ii) The type of foo could equivalently be written as Eq a => Char -> a -> Int
1 iii) foo (bar ‘a’) has type Int
1 iv) The type of bar can be instantiated as Char -> Bool
1 v) The type variable a in the type of bar can be instantiated as any type in Ord
Question 2 [12 Marks] Multiple choice questions
Use the file Answer.md to mark the correct answer for each of the following questions, by placing an x in the square brackets.
Each correct answer gains you 2 marks, and 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) Programming languages
Which of the following statements is not a good reason to use a high-level programming
language, instead of a machine-level language.
High-level programming languages are closer to how humans think about problems High-level programming languages offer superior control over every action that the computer takes
High-level programs are easier to read
High-level programs are usually more portable to multiple different hardware setups There is a wider choice of high-level languages than machine-level languages
2 ii) Types
Which statement is False about Haskell types?
Every Haskell function has a type
The Int type can have arithmetic overflow The Bool type has only two possible values Types are checked while the program runs
We can give existing types new names with the type keyword 2 iii) Lists and Recursion
Which statement is False in Haskell?
[1,4..15] will output [1,4,7,10,13]
[1,2,3] is exactly the same as 1:2:3:[]
It is possible to construct a list of functions
The definition of lists is recursive
We can construct a list that contains more than one type
2 iv) Style
Which of the following is not useful for documenting a Haskell program?
Comments that explain how a function works Comments that explain what a function is for Descriptive names for functions and variables Type declarations
Unit tests, such as doctests
2 v) Binary Trees
Recall the usual definition of binary trees:
data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a) Which of the following is a binary search tree?
Node (Node (Node Null 4 Null) 2 (Node Null 5 Null)) 1 (Node Null 3 Null)
Node (Node (Node Null 4 Null) 3 (Node Null 5 Null)) 2 (Node Null 1 Null)
Node (Node (Node Null 1 Null) 2 (Node Null 4 Null)) 3 (Node Null 5 Null)
Node (Node (Node Null 1 Null) 2 (Node Null 3 Null)) 4 (Node Null 5 Null)
Node (Node (Node Null 1 Null) 3 (Node Null 2 Null)) 5 (Node Null 4 Null)
2 vi) Streams Consider the program
What infinite sequence does baz construct?
baz :: [Int]
baz = 0 : 1 : map (+1) baz
Question 3 [5 Marks] AddBiggest (AddBiggest.hs)
Code templates for all programming questions in this exam can be found in the ProgrammingQuestions folder. We recommend that you use VSCodium for your programming, and that you open the Terminal tool in VSCodium in order to test your code.
Using the incomplete template AddBiggest.hs in the folder, complete the undefined function addBiggest . The specification of the 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.
Question 4 [10 Marks] Tickets (Tickets.hs)
Using the incomplete template Tickets.hs in the folder, complete the two undefined functions validTicket and issueTicket . The specifications of these functions are provided in the
comments immediately above the functions. Instructions for submission are the same as for the previous question.
Question 5 [10 Marks] Numbers (Numbers.hs)
Using the incomplete template Numbers.hs in the folder, complete two undefined functions sumOfPowers and mercator . The specifications of these functions are provided in the
comments immediately above the functions. Instructions for submission are the same as for the previous questions.
Question 6 [20 Marks] ListFunctions (ListFunctions.hs)
Using the incomplete template ListFunctions.hs in the folder, complete four undefined functions answerToMark , allBetween , stretch and longestStreak . The specifications of these functions are provided in the comments immediately above the functions. Instructions for submission are the same as for the previous questions.
Question 7 [10 Marks] CustomLists (CustomLists.hs)
Using the incomplete template CustomLists.hs in the folder, complete two undefined functions second and show . The specifications of these functions are provided in the comments
immediately above the functions. Instructions for submission are the same as for the previous questions.
Question 8 [15 Marks] Trees (Trees.hs)
Using the incomplete template Trees.hs in the folder, complete three undefined functions leafProduct , roseResults and treeWidth . The specifications of these functions are provided
in the comments immediately above the functions. Instructions for submission are the same as for the previous questions.
Question 9 [8 Marks] Complexity
Open the file Complexity.hs . Two functions are defined: isSorted and sortedTail . Answer the following questions about these functions’ time complexity. Use the file Answer.md to mark the correct answer for each of the following questions, by placing an x in the square brackets.
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.
9 i) What is the best case time complexity of isSorted ?
9 ii) What is the worst case time complexity of isSorted ?
9 iii) What is the best case time complexity of sortedTail ?
9 iv) What is the worst case time complexity of sortedTail ?