COMP1100/COMP1130 The Australian National University Semester 1, 2016
INTRODUCTION TO PROGRAMMING AND ALGORITHMS Final Examination (COMP1100/COMP1130)
Writing period: Study period: Permitted materials:
Total COMP1100 questions: Total COMP1100 marks:
Total COMP1130 questions: Total COMP1130 marks:
3 hours
15 minutes None
6 100
6 100
COMP1100 students must answer questions 1–6 COMP1130 students must answer questions 3–8 Questions are not of equal value.
All questions must be completed on this exam paper.
Please write your student ID number at the top of every page. This examination paper must not be removed from the exam room.
Student ID:
Course Code:
For use by examiners only:
COMP1100:
COMP1130
Question
Points
Score
1
15
2
15
3
10
4
20
5
20
6
20
Total:
100
Question
Points
Score
3
10
4
20
5
20
6
20
7
10
8
20
Total:
100
COMP1100/COMP1130
Final Examination 2016
Page 1 of 17
Student Number:
COMP1100: Question1 ………………………………………………………….[15marks] (a) (5 marks) Consider the following function:
mystery :: (Eq a) => a -> a -> a -> Bool mystery x y z = not ((x==y) && (y==z))
Explain the behaviour of this mystery function. When does it return True and when False?
(b) (5 marks) Define a function threeDifferent that takes three values as arguments and re- turns True only if they are all different. Be sure that you write a corresponding function sig- nature.
(c) (5marks) NowdefineafunctionfourEqualthatreturnsTrueonlyifallfourofitsarguments are equal. You may freely reuse either of the above functions mystery or threeDifferent.
COMP1100/COMP1130 Final Examination 2016 Page 2 of 17
Student Number:
COMP1100: Question2 ………………………………………………………….[15marks]
(a) For each of the following expressions check off the description that applies and fill in the blanks:
i. (2 marks) 9 + “hello” ⃝ ill-typed
⃝ well-typed with type ii. (2marks) (9 + 5) * 43
⃝ ill-typed
⃝ well-typed with type
iii. (2 marks) (\ x -> (x :: Int) ‘div‘ 0)
⃝ ill-typed
⃝ well-typed with type
iv. (2 marks) (\ x -> head [500, x::Int])
⃝ ill-typed
⃝ well-typed with type
v. (2 marks) (\ x -> 9::Int)(1 / 0)
⃝ ill-typed
⃝ well-typed with type
(b) (5 marks) Various streaming video services (YouTube, Netflix, Hulu) let you watch video in your Web browser. As you watch the video, your browser sends requests to a server, which returns responses. Suppose that, for each request, the server can return one of the following responses:
• When the video is over, the response is a link (URL) to watch it again.
• A video is divided up into frames (individual pictures, which are played consecutively to
make the video). When the video is playing, the response is a collection of video frames.
• The video services share content, so if you make a request on one service, it may forward that request to another service, and return their response. However, this forwarded re- sponse needs to be accompanied by the service to which the request was forwarded (e.g., so their ads can be displayed). For example, if you request a video from Netflix, it might
return a respose that says “I checked with Hulu, and here is their response.”
Let the type Link represent Web addresses (URLs). Let the type Frame represent a video frame. Let the type Service represent a video service (YouTube, Netflix, Hulu, etc.). You can assume these types without defining them.
Define a data type Response representing the above responses:
data Response = …
COMP1100/COMP1130 Final Examination 2016 Page 3 of 17
Student Number:
COMP1100/COMP1130: Question 3 ……………………………………………….[10 marks]
Consider the following definition of a binary tree that stores values only in leaf nodes: data Tree a = Empty | Leaf a | Node (Tree a) (Tree a)
Often, one uses trees to model sequences, representing a sequence by the leaves of the tree, from left to right. However, one disadvantage of this representation of sequences is that there is no unique representation of the empty sequence. For example,
Empty
Node Empty Empty
Node (Node Empty Empty) Empty
are all different representations of the empty sequence. We can solve this problem by restricting attention to normal trees.
A normal tree is either: • Empty, or
• a non-empty tree
and that’s it! A non-empty tree is either:
• Leaf x,or
• Node l r where l and r are non-empty trees
and that’s it!
Thereisonlyonenormalemptytree;treeslikeNode Empty Emptyarenotnormal. Define a function that normalises a tree:
norm :: Tree a -> Tree a
COMP1100/COMP1130 Final Examination 2016 Page 4 of 17
Student Number:
COMP1100/COMP1130: Question 4 ……………………………………………….[20 marks] In graphics, people make three-dimensional models of scenes they plan to turn into pictures or movies. One technique used is called constructive solid geometry, or CSG. A complicated three- dimensional object (say, Buzz Lightyear or Hello Kitty) is defined in terms of some basic shapes: spheres, rectangles, etc.
This question is inspired by the idea of CSG but is highly simplified: we are only working in two dimensions, and the only thing your constructions will be able to do is report “black” or “white” for a particular two-dimensional coordinate point.
A point is represented in Cartesian coordinates, as a pair (x,y) of Real numbers. A construction is represented by a function that returns True on all points that should be colored black. Thus:
type Point = (Float, Float) type Constr = Point -> Bool
where
for any construction c,
c p True
if and only if p should be colored black, and, c p False
if and only if p should be colored white.
In this problem, you will define some basic shapes, and some ways of composing them to make constructions. For instance, the construction in Figure 1 is the union of:
• the intersection of – a disk, and
– the inverse of ∗ a rectangle
• a rectangle
• another rectangle
COMP1100/COMP1130
Final Examination 2016
Page 5 of 17
Figure 1: A simple construction
Student Number:
Define the following constructions as Haskell functions:
(a) (5 marks) Given two points min and max, the construction rect min max represents a black rectangle where min is the lower-left corner, and max is the upper-right corner.
rect :: Point -> Point -> Constr
(b) (5 marks) Given two constructions c1 and c2, the construction intersection c1 c2 has, as black points, exactly those points that are colored black by both c1 and c2.
intersection :: Constr -> Constr -> Constr
(c) (5 marks) Given two constructions c1 and c2, the construction union c1 c2 has, as black points, exactly those points that are colored black by either c1 or c2 (or both).
union :: Constr -> Constr -> Constr
(d) (5 marks) Given a construction c, the construction inverse c has, as black points, exactly those points that are colored white by c.
inverse :: Constr -> Constr
COMP1100/COMP1130 Final Examination 2016 Page 6 of 17
Student Number:
COMP1100/COMP1130: Question 5 ……………………………………………….[20 marks]
(a) (2marks) Recallthatabinarytreeasformulatedinlecturesandthetextbookstoresvaluesonly in its interior nodes, while the leaves have no associated value. Give the data type definition of a binary tree of this form.
(b) (8 marks) Write the definition of a function elemT that decides whether a value is an element of a Tree, and having the signature:
elemT :: (Eq a) => Tree a -> a -> Bool
Recall that the type class Eq allows testing for equality on values of its instances. For example,
the following expression evaluates to True:
elemT (Node 2 (Node 3 NilT NilT) NilT) 3
(c) (10 marks) A binary search tree can be modelled by the same type Tree a except that the tree isconstrainedtobeordered.AtreeNode a t1 t2isorderedif:
• all values in t1 are smaller than a,
• all values in t2 are larger than a,
• and the trees t1 and t2 are themselves ordered.
Reimplement elemT to take advantage of this ordering, and having the signature: elemT :: (Ord a) => Tree a -> a -> Bool
COMP1100/COMP1130 Final Examination 2016 Page 7 of 17
Student Number:
COMP1100/COMP1130: Question 6 ……………………………………………….[20 marks] Recall the Abstract Data Type Store defined to model the way values are stored in variables within a computer memory, which has the following signature:
initial :: Store
value :: Store -> Var -> Integer
update :: Store -> Var -> Integer -> Store
The corresponding Haskell module header for this ADT is:
module Store ( Store,
initial,
value,
update
) where
— Store
— Store -> Var -> Integer
— Store -> Var -> Integer -> Store
We wish to change the specification of Store to return a Maybe value instead of 0 when using value to look up a variable that does not yet have a value in the given store. Recall that Maybe is defined as:
data Maybe a = Nothing | Just a
(a) (5 marks) Write the new signature for this revised Store ADT.
COMP1100/COMP1130 Final Examination 2016 Page 8 of 17
Student Number:
(b) (5 marks) The following implementation models the Store ADT as a list of pairs associating values with variables:
data Store = Store [(Integer,Var)] initial :: Store
initial = Store []
value :: Store -> Var -> Integer value (Store []) v = 0
value (Store ((n,w):sto)) v
| v==w = n
| otherwise = value (Store sto) v
update :: Store -> Var -> Integer -> Store update (Store sto) v n = Store ((n,v):sto)
Rewrite this list of pairs implementation of Store to match the new Store specification using Maybe.
COMP1100/COMP1130 Final Examination 2016 Page 9 of 17
Student Number:
(c) (10 marks) The following implementation models the Store ADT as a function:
newtype Store = Store (Var -> Integer) initial :: Store
initial = Store (\v -> 0)
value :: Store -> Var -> Integer value (Store sto) v = sto v
update :: Store -> Var -> Integer -> Store update (Store sto) v n
= Store (\w -> if v == w then n else sto w)
Rewrite this function implementation of Store to match the new Store specification using
Maybe.
COMP1100/COMP1130 Final Examination 2016 Page 10 of 17
Student Number:
COMP1130: Question7 ………………………………………………………….[10marks]
Recall the definition of insertion sort for lists:
iSort :: [Integer] -> [Integer] iSort [] = []
iSort (x:xs) = ins x (iSort xs)
ins :: Integer -> [Integer] -> [Integer] ins x [] = [x]
ins x (y:ys)
| x <= y = x:(y:ys)
| otherwise = y : ins x ys
A definition of a function minList for finding the minimum element of a list by first applying iSort and then taking the head element of the list can be defined as follows:
minList :: [Integer] -> Int minList = head . iSort
(a) (6 marks) Trace evaluation of the minList function on the list [8,6,1,7,5].
(b) (4 marks) How does laziness make this approach realistically feasible as compared to a lan- guage with eager evaluation?
COMP1100/COMP1130 Final Examination 2016 Page 11 of 17
Student Number:
COMP1130: Question8 ………………………………………………………….[20marks] Consider the following two functions that reverse a list:
rev1 [] = []
rev1 (x:xs) = rev1 xs ++ [x]
rev2 = shunt []
shunt xs [] = xs
shunt xs (y:ys) = shunt (y:xs) ys
(a) (5 marks) Estimate the time complexity of rev1. Explain your answer!
(b) (5 marks) Estimate the time complexity of rev2. Explain your answer!
COMP1100/COMP1130 Final Examination 2016 Page 12 of 17
Student Number:
(c) (10 marks) Prove for all finite lists xs and ys that rev2 (xs ++ ys) = rev2 ys ++ rev2 xs You may rely on the following lemmas in your proof:
[] ++ zs = zs
(w:ws) ++ zs = w:(ws++zs)
xs ++ [] = xs
xs ++ (ys ++ zs) = (xs ++ ys) ++ zs
(++.1)
(++.2)
(++.3)
(++.4)
COMP1100/COMP1130 Final Examination 2016
Page 13 of 17
Student Number:
This page intentionally blank for scratch paper.
COMP1100/COMP1130 Final Examination 2016 Page 14 of 17
Student Number:
This page intentionally blank for scratch paper.
COMP1100/COMP1130 Final Examination 2016 Page 15 of 17
Student Number:
This page intentionally blank for scratch paper.
COMP1100/COMP1130 Final Examination 2016 Page 16 of 17
Student Number:
This page intentionally blank for scratch paper.
COMP1100/COMP1130 Final Examination 2016 Page 17 of 17