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 :: (Int,Bool) -> Char
bar :: Int -> Bool -> (Int,Bool)

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 (3 True) can be given a type
The type of bar could also be written Int -> (Bool -> (Int,Bool))
bar 3 can be given a type
foo . bar can be given a type
If bar 3 True does not terminate, foo (bar 3 True) will certainly also not terminate

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.

2 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

2 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

2 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

2 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

2 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 3

  [5 Marks]

  Great Minus Less (GreatMinusLess.hs)

Using the incomplete template GreatMinusLess.hs in your final exam IntelliJ project, complete the undefined function greatMinusLess. The specification of the greatMinusLess 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.

You can upload your implementation of GreatMinusLess.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

  [10 Marks]

  Mobile Operating Systems (MobileOS.hs)

Using the incomplete template MobileOS.hs in your final exam IntelliJ project, complete the two undefined functions latestRelease and validRelease.

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

Question 5

  [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 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]

  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 questions.

Question 7

  [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 8

  [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 9

  [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.

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

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

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

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

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