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

Total marks: 100
Reading period: 15 Minutes duration (no use of keyboard or selection of answers).
Writing period: 180 Minutes duration.
Permitted materials: One A4 page with notes on both sides, Unannotated paper-based dictionary.
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

  [30 Marks]

  Multiple choice questions

For each of the following questions, mark the single correct answer.

Each correct answer gains you 2 marks. Each incorrect answer or question left unanswered neither loses nor gains marks.

1 i)

  [2 Marks]

  Haskell Interpreter

Which of the following statements about Haskell's interpreter is true?

The interpreter transforms a whole program
The interpreter executes code line-by-line
The interpreter turns machine-level programs into high-level programs
The interpreter translates between imperative and declarative programming

1 ii)

  [2 Marks]

  Built-in functions

Consider the function

 between1And10 :: Int -> Bool
 between1And10 n
   | n < 1 = False
   | n > 10 = False
   | otherwise = True

Which of the following definitions of between1And10 is functionally the same as the one above? (Two functions are functionally the same if they return the same output whenever they are given the same input.)

between1And10 n = not ((n < 1) && (n <= 10))
between1And10 n = not (10 < n) || (n < 1)
between1And10 n = not (10 < n) && not (n < 1)
between1And10 n = (1 <= n <= 10)

1 iii)

  [2 Marks]

  Types and Data

Which of the following is not a valid definition in Haskell?

type IntTimesBool = (Int, Bool)
data IntTimesBool = Combine (Int, Bool)
type IntTimesBool = Combine Int Bool
data IntTimesBool = Combine Int Bool

1 iv)

  [2 Marks]

  Associativity of ->

Which of the following options is the same as a -> (a -> b) -> a?

(a -> (a -> b)) -> a
(a -> a -> b) -> a
a -> ((a -> b) -> a)
a -> (a -> (b -> a))

1 v)

  [2 Marks]

  Testing

Which of the following statements about testing is true?

If testing of your code does not give any errors, then you know that the code has no bugs.
In black box tests, special cases should be tested individually.
White box tests are written without looking at the code, while black box tests are motivated by the code.
You need to write new black box tests every time the code changes.

1 vi)

  [2 Marks]

  Anonymous functions

Consider the function

myFunction :: Int -> Int -> Int
myFunction x y = x + 2 * y

Which of the following anonymous functions is functionally the same? (Recall that two functions are functionally the same if they return the same output whenever they are given the same input.)

\y -> \x -> y + x + x
\x y -> (2 + x) * y
\x -> x + \y -> 2 * y
\x -> \y -> y + x + x
\y -> \x -> x + 2 * y

1 vii)

  [2 Marks]

  Errors

Consider the following Haskell code:

 3   minusTwo :: Int -> Int
 4   minusTwo n = minusOne (n-1)
 5       where minusOne m = m-1
 6
 7   minusThree :: Int -> Int
 8   minusThree n = minusTwo (minusOne n)
 9

When compiling this we get the following error:

 error: Variable not in scope: minusOne :: Int -> Int
   |
 8 | minusThree n = minusTwo (minusOne n)
   |                          ^^^^^^^^

How can we make the file compile without errors?

Remove the indentation on line 5 before the where clause
Copy the where clause from line 5 to line 9
Change every occurrence of n on line 8 to m
Swap the order of minusTwo and minusOne on line 8

1 viii)

  [2 Marks]

  Folds

When we write foldr f then each time the function f is called, its inputs will be

First the base case, then a list
First the head of a list, then the result of the recursive call on the tail of that list
First the head of a list, then the value accumulated from the initial part of the original list
First a list, then the base case
First the result of the recursive call on the tail of a list, then the head of that list
First the value accumulated from the initial part of the original list, then the head of a list

1 ix)

  [2 Marks]

  Game Trees

Assume that it is our move next in a two player game. In this game moves alternate strictly between the players. We are trying to maximise a heuristic, while our opponent is trying to minimise that number. Given the game tree below, what value will the minimax algorithm return for the root?

Tree

0
1
3
8
9

1 x)

  [2 Marks]

  Ad Hoc Polymorphism

What is the most general correct type declaration for the following function definition?

 foo x y = show (x == y)

foo :: Eq a => a -> a -> String
foo :: (Eq a, Eq b) => a -> b -> String
foo :: (Eq a, Show a) => a -> a -> String
foo :: (Eq a, Show a, Eq b, Show b) => a -> b -> String
foo :: Show a => a -> a -> String
foo :: (Show a, Show b) -> a -> b -> String

1 xi)

  [2 Marks]

  Evaluation Order

Recall that id is the polymorphic identity function, and that negate is the function in Num with default behaviour

 negate x = 0 - x

Thinking about the evaluation order of Haskell, how will the following program evaluate?

 id (negate (id 5))

⟹ id (negate 5) ⟹ id (0 - 5) ⟹ 0 - 5 ⟹ -5
⟹ id (negate 5) ⟹ id (0 - 5) ⟹ id (-5) ⟹ -5
⟹ id (negate 5) ⟹ negate 5 ⟹ 0 - 5 ⟹ -5
⟹ negate (id 5) ⟹ 0 - id 5 ⟹ 0 - 5 ⟹ -5
⟹ negate (id 5) ⟹ negate 5 ⟹ 0 - 5 ⟹ -5

1 xii)

  [2 Marks]

  Complexity

Consider the function

 eraseOne :: Eq a => a -> [a] -> [a]
 eraseOne x list = case list of
   [] -> []
   y:ys
     | x == y    -> ys
     | otherwise -> y : eraseOne x ys

How could you describe the best case, with respect to 'Big O' time complexity, of eraseOne x list?

list has exactly one element, which is equal to x
list is empty
the head of list is equal to x
the last element of list is equal to x
x is not in list

1 xiii)

  [2 Marks]

  Complexity

What is the worst case time complexity of eraseOne?

O(1)
O(n)
O(n2)
O(n3)
O(n4)
O(2n)

1 xiv)

  [2 Marks]

  Complexity

Consider the function

 largest :: Ord a => [a] -> a
 largest list = case list of
   []   -> error "empty list"
   x:xs -> foldr max x xs

What is the worst case time complexity of largest?

O(1)
O(n)
O(n2)
O(n3)
O(n4)
O(2n)

1 xv)

  [2 Marks]

  Complexity

Consider the function

 largeSort :: Ord a => [a] -> [a]
 largeSort list = case list of
   [] -> []
   _  -> largeSort (eraseOne large list) ++ [large]
   where
     large = largest list

What is the worst case time complexity of largeSort?

O(1)
O(n)
O(n2)
O(n3)
O(n4)
O(2n)

Question 2

  [10 Marks]

  Numbers.hs

The following instructions apply to all programming questions below and should be read carefully.

There are seven Haskell files to complete. Files contain various numbers of functions to complete. Each function is worth 5 marks. Completion of the later functions in files do not require you to complete the earlier functions, except where noted otherwise in the file's text. You will find the template Haskell files in a folder on your desktop, and in VSCodium.

You may define helper functions if you wish. You may use any Haskell function available in the Prelude or basic libraries. The doctests in the file are intended to help you, but are not intended to be exhaustive, and do not replace your need to test your own code. Your code will be marked both for correctness and for other aspects of quality, such as style.

Please submit by dragging and dropping each Haskell file into the white box below each question. Do not rename the files before submission. You should be able to see the text of the file you have submitted in the box. No further testing feedback will be supplied to you. You may submit to the same question multiple times; if you do so, your previous submission will be overwritten. Your work will only be visible to markers if you submit it correctly. Therefore it is essential that you upload your code into this exam by dragging your file into the appropriate box.

Complete the program Numbers.hs in your final exam VSCodium project.

Question 3

  [10 Marks]

  Stomachs.hs

Complete the program Stomachs.hs in your final exam VSCodium project.

Question 4

  [5 Marks]

  Fliponacci.hs

Complete the program Fliponacci.hs in your final exam VSCodium project.

Question 5

  [10 Marks]

  ListInsertions.hs

Complete the program ListInsertions.hs in your final exam VSCodium project.

Question 6

  [10 Marks]

  FunctionLists.hs

Complete the program FunctionLists.hs in your final exam VSCodium project.

Question 7

  [15 Marks]

  Trees.hs

Complete the program Trees.hs in your final exam VSCodium project.

Question 8

  [10 Marks]

  UnitLists.hs

Complete the program UnitLists.hs in your final exam VSCodium project.