PROGRAMMING AS PROBLEM SOLVING
COMP1100
checksum:
AAAAA
bytes:
78
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.


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.

Question 1

  [12 Marks]

Consider the following functions, which are defined in the file TripleInc.hs in your IntelliJ project:

triple :: Integer -> Integer
triple = (* 3)

inc :: Integer -> Integer
inc = (+ 1)

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. The final mark for this question is calculated between 0 and 12. For example, if you answered all questions correctly you would gain 12 marks for this question. If you answer 5 correctly and 4 incorrectly you would receive 6 marks for this question.

TrueFalse
(inc . triple) 5 == 16
(triple . inc) 10 == 18
map inc ["1"] == ["2"]
map triple [2,5,6] == [6,15,18]
(inc . inc) and (+ 2) are equivalent functions
(triple . triple) and (* 6) are equivalent functions
(triple . inc) and (inc . triple) are equivalent functions
The type of (triple . inc) is Integer
The type of (map triple) is [Integer] -> [Integer]

Question 2

  [12 Marks]

  Data types and functions

Using the incomplete template for Cities.hs in your exam IntelliJ project, complete the unimplemented function (neighbouringCities). Use the doctests provided to test your solution, and then upload your implementation of Cities.hs, by dragging your file into the box below.

The specification of the neighbouringCities 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 slightly 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.

Question 3

  [12 Marks]

  Functions and numeric computation

Using the incomplete template for Shapes.hs in your exam IntelliJ project, complete the unimplemented functions (area, rectangles, totalArea, areaOfRectangles, sortShapes). Use the doctests provided to test your solutions, and then upload your implementation of Shapes.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 slightly 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.

Question 4

  [40 Marks]

  Binary trees and binary search trees

Using the incomplete template for Trees.hs in your exam IntelliJ project, complete the unimplemented functions. 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 slightly 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.

Question 5

  [14 Marks]

  Syntax, types, well-formed expressions

Some of the following expressions are not syntactically correct, while others are syntactically correct but do not have sensible types. Some are well-formed (syntactically correct and having a sensible type). Which of the following expressions is syntactically correct, and which is well-formed? In the case of a well-formed expression, identify a suitable type. Assume double :: Int -> Int. If you use the computer to check your answers be prepared for some strange error messages, and choose your corresponding answer carefully.

Each correct answer gains you 2 marks, each incorrect answer loses you 1 mark, while a question left unanswered neither loses nor gains marks.

5 i)

  [2 Marks]

double -3

not syntactically correct
syntactically correct, not sensibly typed
well-formed, Int
well-formed, Integer
well-formed, Num a => a

5 ii)

  [2 Marks]

double double 0

not syntactically correct
syntactically correct, not sensibly typed
well-formed, Int
well-formed, Integer
well-formed, Num a => a

5 iii)

  [2 Marks]

"++" == "+" ++ "+"

not syntactically correct
syntactically correct, not sensibly typed
well-formed, [Char]
well-formed, String
well-formed, Bool

5 iv)

  [2 Marks]

[(+),(-)]

not syntactically correct
syntactically correct, not sensibly typed
well-formed, [a]
well-formed, [(a),(b)]
well-formed, Num a => [a -> a -> a]

5 v)

  [2 Marks]

[[],[[]],[[[]]]]

not syntactically correct
syntactically correct, not sensibly typed
well-formed, [t]
well-formed, [[t]]
well-formed, [[[t]]]
well-formed, [[[[t]]]]

5 vi)

  [2 Marks]

concat ["tea","for",'2']

not syntactically correct
syntactically correct, not sensibly typed
well-formed, Char
well-formed, [Char]
well-formed, [String]

5 vii)

  [2 Marks]

concat ["tea","for","2"]

not syntactically correct
syntactically correct, not sensibly typed
well-formed, Char
well-formed, [Char]
well-formed, [String]

Question 6

  [10 Marks]

  Complexity

Consider the following two Haskell functions that both reverse a given list:

rev1 [] = []
rev1 (x:xs) = rev1 xs ++ [x]

rev2 = shunt []
  where
    shunt xs [] = xs
    shunt xs (y:ys) = shunt (y:xs) ys

6 i)

  [2 Marks]

What is the execution time complexity of rev1 (where n is the length of the given list)?

O(1)
O(log n)
O(n)
O(n2)
O(n3)
O(nn)

6 ii)

  [3 Marks]

Justify your answer to the previous question.

The list cons (:) operation is O(1): constant time and there are n recursive calls
Binary search is O(log n): logarithmic time
All list operations are O(n): linear time
The append operation (++) is O(n): linear time and there are n recursive calls
The append operation (++) is O(n2): quadratic time and there are n recursive calls
The append operation (++) is O(nn): exponential time which dominates the n recursive calls

6 iii)

  [2 Marks]

What is the execution time complexity of rev2 (where n is the length of the given list)?

O(1)
O(log n)
O(n)
O(n2)
O(n3)
O(nn)

6 iv)

  [3 Marks]

Justify your answer to the previous question.

The list cons (:) operation is O(1): constant time and there are n recursive calls
Binary search is O(log n): logarithmic time
All list operations are O(n): linear time
The append operation (++) is O(n): linear time and there are n recursive calls
The append operation (++) is O(n2): quadratic time and there are n recursive calls
The append operation (++) is O(nn): exponential time which dominates the n recursive calls