PROGRAMMING AS PROBLEM SOLVING (ADVANCED)
COMP1130
checksum:
AAAAA
bytes:
50
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]

  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.

1 i)

  [2 Marks]

  Functions, lists, and types

Consider the following type signature

baz :: Double -> Double -> [Char]

What is the type of [baz]?

[Double -> Double -> Char]
[Double -> Double -> String]
[Double] -> [Double] -> [Char]
[Double] -> [Double] -> [String]
[baz] cannot be given a type

1 ii)

  [2 Marks]

  Testing

When you conduct white box testing, you...

Test that large numbers of random inputs obey some property
Test the code to measure speed and memory usage
Test the whole program, and not individual parts
Use the form of the actual code to guide your choice of tests
Use the specification to guide your choice of tests

1 iii)

  [2 Marks]

  Folds

foldr (:) is mathematically equivalent to

\x y -> (reverse x) ++ y
\x y -> x : y
\x y -> x ++ y
\x y -> y : x
\x y -> y ++ x

1 iv)

  [2 Marks]

  Games

Which of the following statements about alpha-beta pruning is true?

It is risky, because there is a small chance that the best move might get pruned away
It is slower than minimax but returns better answers
It requires that your heuristic has some type in the type class Bounded
It requires the use of rose trees
It will return the same answer as minimax if you have enough time to explore the whole game tree

1 v)

  [2 Marks]

  Ad hoc polymorphism

Which of the following is the most general type signature, i.e. can be instantiated in the largest number of ways?

Eq a => a -> a -> a
(Eq a, Eq b) => a -> b -> a
(Eq a, Ord a) => a -> a -> a
Ord a => a -> a -> a
(Ord a, Ord b) => a -> b -> a

Question 2

  [10 Marks]

  Approximating e (ApproximatingE.hs)

Using the incomplete template ApproximatingE.hs in your final exam IntelliJ project, complete the two undefined functions fact and eApprox. The specification of these functions is provided in the comments immediately above them. You will need to adhere to these specifications. 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 ApproximatingE.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 3

  [10 Marks]

  Movies (Movies.hs)

Using the incomplete template Movies.hs in your final exam IntelliJ project, complete the two undefined functions show and unrestrictedTitles.

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

Question 4

  [20 Marks]

  List Functions (ListFunctions.hs)

Using the incomplete template ListFunctions.hs in your final exam IntelliJ project, complete the four undefined functions stutter, take, elemIndices, and ascendingPrefix.

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

Question 5

  [15 Marks]

  Trees (Trees.hs)

Using the incomplete template Trees.hs in your final exam IntelliJ project, complete the three undefined functions isBinary, roseToBinary, and isPath.

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

Question 6

  [10 Marks]

  Complexity

Open the file Complexity.hs in your final exam IntelliJ project. Three functions are defined: rightOfList, rightOfBTree, and rightOfRose. 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.

6 i)

  [2 Marks]

What is the best case time complexity of rightOfList?

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

6 ii)

  [2 Marks]

What is the average case time complexity of rightOfList?

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

6 iii)

  [2 Marks]

A BinaryTree is balanced if for any two leaves the difference between their depth is at most 1. What is the worst case time complexity of rightOfBTree on balanced input?

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

6 iv)

  [2 Marks]

What is the best case time complexity of rightOfRose? Make no assumption that the tree is balanced.

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

6 v)

  [2 Marks]

What is the worst case time complexity of rightOfRose? Make no assumption that the tree is balanced.

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

Question 7

  [12 Marks]

  Lambda Calculus

In your answers below, you may write \ for λ. Write -> to indicate that an expression beta-reduces to another, and <- if you wish to indicate that an expression reduces from another, e.g.

(\x.x) y
-> y
<- (\x.y) z

7 i)

  [2.5 Marks]

Present every step of the lazy evaluation of the following term in the text box below:

(λx.(λy.x y) y)((λz.z) y)

7 ii)

  [2.5 Marks]

Present every step of the eager evaluation of the same term:

(λx.(λy.x y) y)((λz.z) y)

7 iii)

  [3 Marks]

The combinator Y is defined as:

λf.(λx.f (x x))(λx.f (x x))

Show that Y F is beta-equal to F(Y F) for any term F.

7 iv)

  [4 Marks]

Define a lambda calculus term that acts as 'less than or equal to' on natural numbers: when applied to two natural numbers, it should return True if the first input is less than or equal to the second, and False if it is larger.

You do not have to write the lambda term out in full, but rather may assume you have access to the following encodings discussed in lectures: Y, true, false, if... then... else, all natural numbers, succ, pred, iszero, and plus.

Question 8

  [13 Marks]

  Program Proof

Consider the following Haskell functions:

length :: [a] -> Int
length []     = 0             -- L1
length (x:xs) = 1 + length xs -- L2

mirror :: [a] -> [a]
mirror = helper [] -- M1

helper :: [a] -> [a] -> [a]
helper xs []     = xs                        -- H1
helper xs (y:ys) = helper (y:(xs ++ [y])) ys -- H2

Your task is to prove that the following property holds for all lists xs:

length (mirror xs) = 2 * length xs

You may at any time use the following lemma, without proof, for any list xs and element x:

length (xs ++ [x]) = length xs + 1 -- Lemma1

8 i)

  [1 Marks]

You will need to use induction to prove a lemma about the function helper. We will call this lemma Lemma2. State this lemma in the text box below.

Hint: if you are not sure, attempt question (vi) and see where you get stuck.

8 ii)

  [1 Marks]

State the base case for Lemma2.

8 iii)

  [2 Marks]

Prove the base case of Lemma2 using equational reasoning. Make sure that you write every line of your argument, and give a reason for each step beside that line. For example, if an equation follows from the first line of the definition of length, write (L1) beside it. If an equation follows by standard laws of mathematics, write (maths) beside it.

8 iv)

  [1 Marks]

State the induction hypothesis for Lemma2.

8 v)

  [6 Marks]

Prove the induction case for Lemma2 using equational reasoning. Make sure that you write every line of your argument, and give a reason for each step beside that line.

8 vi)

  [2 Marks]

Prove the theorem

length (mirror xs) = 2 * length xs

using equational reasoning. Make sure that you write every line of your argument, and give a reason for each step beside that line.