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

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)$

COMP1100 Haskell FINAL EXAM 2020

加微信 powcoder

代做各类CS相关课程和程序语言

Programming Help Add Wechat powcoder

Email: powcoder@163.com

成功案例

java代写 c/c++代写 python代写 drracket代写 MIPS汇编代写 matlab代写 R语言代写 javascript代写

prolog代写 haskell代写 processing代写 ruby代写 scheme代写 ocaml代写 lisp代写

• 数据结构算法 data structure algorithm 代写
• 计算机网络 套接字编程 computer network socket programming 代写
• 数据库 DB Database SQL 代写
• 机器学习 machine learning 代写
• 编译器原理 Compiler 代写
• 操作系统OS(Operating System) 代写
• 计算机图形学 Computer Graphics opengl webgl 代写
• 人工智能 AI Artificial Intelligence 代写
• 大数据 Hadoop Map Reduce Spark HBase 代写
• 系统编程 System programming 代写
• 网页应用 Web Application 代写
• 自然语言处理 NLP natural language processing 代写
• 计算机体系结构 Computer Architecture 代写
• 计算机安全密码学computer security cryptography 代写
• 计算机理论 Computation Theory 代写
• 计算机视觉(Compute Vision) 代写