PROGRAMMING AS PROBLEM SOLVING (INCLUDING ADVANCED)
COMP1100/COMP1130
checksum:
AAAAA
bytes:
59
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 on your desktop.

Questions are not of equal value.
Note that some questions are only for COMP1100 students, some are only for COMP1130 students, and some are for all students.
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]

  COMP1100 Multiple choice questions

All questions in this section are for ONLY COMP1100 Students. Do NOT attempt if you are a COMP1130 student.

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

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

1 i)

  [3 Marks]

  Prelude functions

Which of the following Prelude functions do not always return a Bool as output?

(Note that we follow usual Haskell notation by writing functions that are usually written infix, inside parentheses.)

(&&)
(/=)
(>)
elem
filter

1 ii)

  [3 Marks]

  Datatypes

Which of the following cannot be understand mathematically as defining Foo to be the product of String and Double?

data Foo = Bar (String, Double)
data Foo = Bar String | Qux Double
data Foo = Bar String Double
type Foo = (String, Double)

1 iii)

  [3 Marks]

  Exceptions

What is an exception?

A runtime error
A type error
An incorrect output diagnosed during testing
The final line of a guarded expression, starting with otherwise
The Nothing element of a Maybe type

1 iv)

  [3 Marks]

  List syntax

Which of the following is not valid Haskell syntax for a three element list containing the characters 'H', 'B', and 'C'?

('H' : 'B') : "C"
"HBC"
'H' : ('B' : "C")
'H' : "BC"
'H' : 'B' : 'C' : ""

Question 2

  [16 Marks]

  COMP1100 and COMP1130 Multiple choice questions

All questions in this section are for BOTH COMP1100 and COMP1130 students.

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.

2 i)

  [2 Marks]

  Types

Consider the following type declarations:
listFunc :: Int -> [a] -> [a]
numFunc :: Bool -> Int -> Int

Which of the following is correct?

The type of numFunc True is Int
It is valid to compose the functions as listFunc . numFunc
It is valid to compose the functions as listFunc . numFunc True
If numFunc is given one input, the result is an Int
The type signature of numFunc is equivalent to (Bool -> Int) -> Int

2 ii)

  [2 Marks]

  Complexity

Which of the following functions has the best (smallest) Big-O complexity?

f(x) = log x + 1500
f(x) = x2 - 40
f(x) = 2x - 500
f(x) = x * log x + 2
f(x) = x + x2 + x3

2 iii)

  [2 Marks]

  Complexity

Consider the following function:
f :: [Int] -> Int -> Int
f list n = (foldr ((+).(*n)) 0 list) + 20000 * 5000


What is the worst case time complexity of f?

O(log n)
O(n)
O(n2)
O(n log n)
O(2n)

2 iv)

  [2 Marks]

  Sorting

Which of the following statements is correct?

The merge function in merge sort turns two unsorted lists into one sorted list.
Insertion sort involves recursively dividing the list into smaller lists.
Merge sort involves finding the minimum element at each iteration.
Insertion sort has O(log n) time complexity in the worst case.
Selection sort has O(n2) time complexity in the worst case.

2 v)

  [2 Marks]

  Stacks and Queues

Which of the following statements is correct?

The push and pop operations on a stack implemented as a list occur on the same side of the list.
The push and pop operations on a stack implemented as a list can sometimes occur on opposite sides of the list.
The enqueue and dequeue operations on a queue implemented as a single list occur on the same side of the list.
The push and pop operations on a stack implemented as a list take O(n) time in the worst case.
The enqueue and dequeue operations on a queue implemented as a single list take O(1) time in the worst case.

2 vi)

  [2 Marks]

  Binary Search Trees

Given the standard definition of Binary Tree:

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

suppose we have the Binary Search Tree of Ints:

Node (Node (Node Null 5 Null) 12 Null) 20 (Node (Node Null 22 Null) 24 Null)

If we search this tree for the number 7, using the usual Binary Search algorithm, which nodes will we visit?

20, 12, 24, 5
20, 12
20, 12, 5
5, 12, 20
All nodes, because in this worst case using a Binary Search Tree does not help.

2 vii)

  [2 Marks]

  Parametric polymorphism

Consider the following type declaration:

calculate :: a -> [b] -> [a] -> b -> [b]

Which of the following statements is correct?

The first and second arguments cannot both be a String.
If calculate was given a Char as its first argument, then the second argument must be a String
If calculate was given an Int as its first argument, then the third argument could be a String
If calculate was given a Char as its first argument, then the third argument must be a String
If calculate was given a list of Int as its second argument, then the fourth argument could be of any type.

2 viii)

  [2 Marks]

  Folds

Which of the following is not valid Haskell syntax?

foldr (+) 0 [1,2]
foldr (&&) False [True,True]
foldr (||) True [True,True]
foldr (++) [] [[1,2],[2,3]]
foldr (+2) 0 [1,2]

Question 3

  [12 Marks]

  ScientificNames.hs

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

There are seven Haskell files provided to you, of which one is for COMP1100 students only, one is for COMP1130 students only, and the other five are for everyone. Files contain various numbers of functions to complete. Each function is worth 6 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 ScientificNames.hs in your final exam VSCodium project.This question is for COMP1100 STUDENTS ONLY. Do NOT attempt if you are a COMP1130 Student.

Question 4

  [12 Marks]

  NumberSequences.hs

Complete the program NumberSequences.hs in your final exam VSCodium project.This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 5

  [18 Marks]

  ListFunc.hs

Complete the program ListFunc.hs in your final exam VSCodium project.This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 6

  [12 Marks]

  Concerts.hs

Complete the program Concerts.hs in your final exam VSCodium project.This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 7

  [6 Marks]

  Authors.hs

Complete the program Authors.hs in your final exam VSCodium project.This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 8

  [12 Marks]

  Movies.hs

Complete the program Movies.hs in your final exam VSCodium project.This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 9

  [6 Marks]

  ChurchNaturals.hs

Complete the program ChurchNaturals.hs in your final exam VSCodium project.This question is for COMP1130 STUDENTS ONLY. Do NOT attempt if you are a COMP1100 Student.

Question 10

  [18 Marks]

  Lambda Calculus

All questions in this section are for COMP1130 STUDENTS ONLY. Do NOT attempt if you are a COMP1100 student.

In your answers below you may write \ for λ, |- for , and alpha,beta,gamma for the Greek letters α,β,γ. Write -> to indicate that an expression beta-reduces to another, and = for alpha-equality.

If asked to present a typing derivation, use a numbered list of typing judgements, with a clear justification beside each line, e.g.

1. x : Bool -> alpha, y : Bool |- x : Bool -> alpha [Variable]
 2. x : Bool -> alpha, y : Bool |- y : Bool [Variable]
 3. x : Bool -> alpha, y : Bool |- x y : alpha [1,2,Application]
 4. x : Bool -> alpha |- \x. x y : Bool -> alpha [3,Lambda]

10 i)

  [4 Marks]

Consider the term

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

If lazy evaluation of this term terminates, present every step of this evaluation. If it does not terminate, present enough steps that the non-termination is clear.

10 ii)

  [4 Marks]

Consider the same term as the previous question

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

If strict evaluation of this term terminates, present every step of this evaluation. If it does not terminate, present enough steps that the non-termination is clear.

10 iii)

  [4 Marks]

Consider the following Haskell program

foo :: Word -> Word
 foo x
   | x == 0    = 1
   | otherwise = foo (x-1) + bar x
   where
    bar y
      | y == 0    = 1
      | otherwise = bar (y-1) + 1

(Note that Word is a Haskell implementation of natural numbers.)

Write foo as a single untyped lambda calculus term. Your implementation should be as close as possible to this term, not merely mathematically equal. You may use the combinators if-then-else, isZero, 0, 1, pred, +, and Y without translating them into lambda calculus syntax.

10 iv)

  [2 Marks]

Give a lambda calculus term that inhabits the type

α → (β → α → γ) → β → γ

for any instantiation of types for the variables α, β, and γ.

10 v)

  [4 Marks]

Recall the definitions of pairs and case in the extension of the simply typed lambda calculus with products and sums:

Typing rules for pairing and case

Present every step of a typing derivation, with justifications for each line, to show that (given an empty basis)

⊢ λw.λx.case w of y.⟨y,x⟩; z.⟨x,z⟩ : (α + α) → α → (α × α)