# 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](https://cs.anu.edu.au/courses/comp1100/news/2020/06/15/final-exam-instructions/) 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](https://www.google.com).
– Permitted materials: This is an open book exam, and you may use any resources you wish.
You might in particular find the [course website](https://cs.anu.edu.au/courses/comp1100/), the [Prelude documentation](https://hackage.haskell.org/package/base-4.14.0.0/docs/Prelude.html), and the [Data.List documentation](https://hackage.haskell.org/package/base-4.14.0.0/docs/Data-List.html) 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.
“`haskell
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:
“`haskell
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
“`haskell
baz :: [Int]
baz = 0 : 1 : map (+1) baz
“`
What infinite sequence does `baz` construct?
– $`0, 1, 0, 1, 0, 1, 0, 1, 0, 1, …`$
– $`0, 1, 1, 1, 1, 1, 1, 1, 1, 1, …`$
– $`0, 1, 1, 1, 2, 2, 2, 3, 3, 3, …`$
– $`0, 1, 1, 2, 2, 3, 3, 4, 4, 5, …`$
– $`0, 1, 2, 3, 4, 5, 6, 7, 8, 9, …`$
**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`?
– $`O(1)`$
– $`O(log\,n)`$
– $`O(n)`$
– $`O(n^2)`$
– $`O(2^n)`$
**9 ii)** What is the **worst case** time complexity of `isSorted`?
– $`O(1)`$
– $`O(log\,n)`$
– $`O(n)`$
– $`O(n^2)`$
– $`O(2^n)`$
**9 iii)** What is the **best case** time complexity of `sortedTail`?
– $`O(1)`$
– $`O(log\,n)`$
– $`O(n)`$
– $`O(n^2)`$
– $`O(2^n)`$
**9 iv)** What is the **worst case** time complexity of `sortedTail`?
– $`O(1)`$
– $`O(log\,n)`$
– $`O(n)`$
– $`O(n^2)`$
– $`O(2^n)`$