PROGRAMMING AS PROBLEM SOLVING
COMP1100
checksum:
AAAAA
bytes:
60
Important notice: Code templates for programming questions in this exam can be found in the accompanying IntelliJ project. You can place this Web page for the exam next to 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 test your solution code with ghci. You can also make use of doctest for testing.

Total marks: 100
Writing period: 180 Minutes duration.
Study period: 15 Minutes duration (no use of keyboard or selection of answers).
Permitted materials: None, aside from the software environment provided.
Note that links to the specification of the Prelude and Data.List libraries are provided.

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

  [10 Marks]

  True/False questions

Consider the following type signatures.

foo :: Char -> a -> b -> a
bar :: Char

Mark True for each of the following statements if it is correct, and False if not.

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.

TrueFalse
foo is ad hoc polymorphic
The type of foo could be written as Char -> (a -> (b -> a))
foo 't' 'k' 'g' can be given a type
foo '1' [1,2,3] True [1] can be given a type
The type of [bar] is String

Question 2

  [10 Marks]

  Multiple choice questions

For each of the following questions, mark the correct 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 minimum total mark for this question is 0.

2 i)

  [2 Marks]

  Functions in Haskell

Which of the following definitions is not a correct implementation of absolute value on integers?

myAbs :: Int -> Int

myAbs x
   | x >= 0    = x
   | otherwise = -x

myAbs x = case x>=0 of
   True  -> x
   False -> -x

myAbs x = case x<0 of
   True -> -x
    _   -> x


myAbs x = sqrt (x*x)

myAbs x = max x (-x)

2 ii)

  [2 Marks]

  Testing

If you conduct white box testing, you ...

Use your specification to design your tests
Use your code to design your tests
Must write your tests in a separate file
Test the speed of the code, not the correctness
Test the whole program, not individual parts

2 iii)

  [2 Marks]

  Type Classes

Which statement about Haskell is false?

Any type that is an instance of Ord is also an instance of Eq
Bool is an instance of Ord
['a'..'e'] evaluates to "abcde" because Char is an instance of Enum
Type classes allow function names to have different definitions when applied to different types
In Haskell, overloading is resolved when the function is run

2 iv)

  [2 Marks]

  Trees

Which statement is false given the following code?

data BinaryTree a = Null | Node (BinaryTree a ) a (BinaryTree a)

tr :: BinaryTree Int
tr = Node (Node Null 5 Null) 7 (Node (Node Null 8 Null) 10 (Node (Node Null 11 Null) 20 (Node Null 21 Null)))

The root of tr has value 7
tr has 4 leaves
tr is a binary search tree
The height (largest number of edges between the root and a leaf) of tr is 4
tr has 7 nodes and 6 edges

2 v)

  [2 Marks]

  Games

Which of the following statements is false?

Given enough time, Minimax always returns the same solution as alpha-beta pruning
Decisions made using a heuristic might not be optimal
In Alpha-beta pruning, alpha is the lower bound of possible values
A branch that is pruned is guaranteed not to be played by any player
Minimax should only be used for zero-sum games

Question 3

  [10 Marks]

  Numbers (Numbers.hs)

Using the incomplete template Numbers.hs in your final exam IntelliJ project, complete the two undefined functions returnBigger and returnMedian. The specification of the functions are 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.

You can upload your implementation of Numbers.hs by dragging your file into the box below. You will receive automatic feedback on whether your code compiles, but no feedback on the correctness of your code. If you drag your file into the box again, it will overwrite your previous upload. Your markers will only see your code if it is uploaded into your exam. Therefore it is essential that you upload your code into this exam, in the browser.

Question 4

  [15 Marks]

  AU (AU.hs)

Using the incomplete template AU.hs in your final exam IntelliJ project, complete the three undefined functions show, bigCities and cityInState.

The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous questions.

Question 5

  [10 Marks]

  Coffee (Coffee.hs)

Using the incomplete template Coffee.hs in your final exam IntelliJ project, complete the two undefined functions toPay and orderSummary.

The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous question.

Question 6

  [20 Marks]

  List Functions (ListFunctions.hs)

Using the incomplete template ListFunctions.hs in your final exam IntelliJ project, complete the four undefined functions removeElem, countOccur, isMatrix and separateList.

The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous questions.

Question 7

  [15 Marks]

  Trees (Trees.hs)

Using the incomplete template Trees.hs in your final exam IntelliJ project, complete the three undefined functions isTernary, numLeaves and isSorted.

The specifications of the functions are provided in the comments immediately above them. Instructions for submission are as for the previous questions.

Question 8

  [10 Marks]

  Complexity

Open the file Complexity.hs in your final exam IntelliJ project. Two functions are defined: findMax and insert. Answer the following questions about these functions' time complexity.

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

8 i)

  [2 Marks]

What is the best case time complexity of findMax?

O(1)
O(log n)
O(n)
O(n log n)
O(n2)

8 ii)

  [2 Marks]

What is the worst case time complexity of findMax?

O(1)
O(log n)
O(n)
O(n log n)
O(n2)

8 iii)

  [2 Marks]

A tree is balanced if the depth of every leaf differs by at most one.

Assuming that the input tree is balanced, what is the best case time complexity of insert?

O(1)
O(log n)
O(n)
O(n log n)
O(n2)

8 iv)

  [2 Marks]

Assuming that the input tree is balanced, what is the average case time complexity of insert?

O(1)
O(log n)
O(n)
O(n log n)
O(n2)

8 v)

  [2 Marks]

If we do not assume that the input tree is balanced, what is the worst case time complexity of insert?

O(1)
O(log n)
O(n)
O(n log n)
O(n2)