Give the typing rules for Peano natural numbers and their eliminator.(ii) Using the rules given above, define the addition function.] (iii) Let a binary tree be either a leaf Leaf or a node Node(l,x,r) where l and r are subtrees, and x is a natural number. Give typing rules for trees corresponding to this prose description, including an eliminator.(iv) Using the rules given above, define a function size which takes a binary tree and returns the total number of nodes in the tree

 

answer all questions

HearMe Ltd. has put a new wearable for the ear (earable) on the market that, in
addition to other sensors, has an accelerometer. The company is hoping to use the
accelerometer to analyze human activity recognition (HAR) of the users.
(a) What are the challenges the company will face in collecting the accelerometer
data for human activity recognition (on their servers)?
(b) What are the steps of the HAR pipeline (you should also discuss person
dependent/independent aspects)? Please use examples only related to
accelerometer sensing.

(c) What are the limitations of applying Deep Learning to HAR data for analysis
and how can they be obviated?

(d) The company would like to be able to perform HAR on-device on the earable.
However, the current model running on the servers does not fit in its processor.
What techniques can be applied to the model to make it run on the device
efficiently and indicate in which way each helps?

 


(a) Describe inference-based program analysis on expressions e. Explain how it can
be used to judge effect systems. [3 marks]
(b) Give inference rules and a set of effects for an effect system for the following
language:
e ::= x | λx.e | e1e2 | if e1 then e2 else e3 | O(ξ).e | W(ξe1).e2 | C(ξ).e
where O(ξ).e opens file ξ and results in the value of e, W(ξe1).e2 evaluates e1
and writes its (integer) value to file ξ before resulting in the value of e2, and
C(ξ).e closes file ξ before resulting in the value of e. The language types are
integers and functions. [4 marks]
(c) Give and explain the safety condition for this system. [3 marks]
(d) Show how the rules from Part (b) assign a type and effect(s) to the following
expression.
O(ξ).if x then λx.W(ξx).C(ξ).x else λx.C(ξ).x
[5 marks]
(e) Justify that the effect system will allow us to identify all expressions with
incorrect use of files or, using an example, describe why it won't and show
how to alter the effect system so that it will allow us to. [5 marks]
13 Principles of Communications
(a) Briefly describe link-state routing, outlining the link-state advertisement and
the shortest path computation that each node carries out. [5 marks]
(b) Fibbing is a technique for injecting link-state advertisements to the routing
system that provides a way to add alternate paths into the results of the route
computation. Describe what this is for, how this operates and what security
implications it has.
[15 marks]
11 (TURN OVER)
CST2.2020.8.12
14 Quantum Computing
(a) In the superdense coding protocol, Alice and Bob each have one qubit from the
entangled pair √
1
2
(|00i + |11i), which enables Alice to send two bits of classical
information to Bob, using a single qubit. Explain the superdense coding protocol
in detail, and show that it does indeed enable the transmission of two bits using
a single qubit. [10 marks]
(b) This question concerns entangled states.
(i) Suppose Alice transmits the two-bit string '00' using the superdense coding
protocol and an evesdropper, Eve, intercepts the qubit transmitted by Alice,
measures it in the computational basis and then re-transmits to Bob. Find
the probability that Bob correctly receives '00'.

 

 

 

We are given a directed graph g = (V, E). A vertex v ∈ V is said to be an origin if
for any other vertex w ∈ V there is a directed path from v to w.
(a) Consider the dfs recurse(g,s) algorithm as described in lecture notes. Show
carefully that, once it terminates, if it has visited a vertex v then it has also
visited all vertices reachable from v. [4 marks]
(b) Suppose g has an origin. Give an algorithm that returns an origin, and which has
O(V + E) running time. [Hint: Consider dfs recurse all(g). What happens
after it visits an origin?] [5 marks]
(c) Suppose g has an origin. Prove that the vertex returned by your algorithm in
part (b) is indeed an origin. [6 marks]
(d) Give an algorithm that returns all origins, and which has O(V + E) running
time. If the graph has no origins, your algorithm should return an empty set.
Explain briefly why your algorithm is correct. [5 marks]
10
CST0.2020.1.11
10 Algorithms
This question concerns unbalanced binary search trees. In some scenarios, most
searches are for a small interval in the key space. For example, if we are searching a
social media feed for posts keyed by timestamp, perhaps 90% of searches might be
for the newest 5% of posts.
(a) Explain why, in a balanced binary search tree with N items, the worst-case cost
of searching for an item is Θ(log N). [1 mark]
(b) Define amortized cost. [2 marks]
(c) Consider an unbalanced binary search tree with N items, where the root holds
a dummy key, the left subtree holds (1 −α)N items, the right subtree holds αN
items, and where each subtree is balanced. Call this an α-BALANCED tree.
Suppose there are m searches, (1 − β)m for items on the left and βm for items
on the right. Find the amortized worst-case cost of a search. For α = 5% and
β = 90%, would you prefer α-BALANCED or a fully balanced tree? [5 marks]
(d) Describe the weighted union heuristic and the path compression heuristic, for
the Disjoint Set data structure. Explain what is meant by a rotation of a binary
search tree. [6 marks]
(e) We speculate that for real-world search frequencies it might be useful to have
an binary search tree that is unbalanced not just at the root but also at other
levels. We would also like the data structure to adjust its shape automatically,
as searches occur.
By adapting the two heuristics above, suggest a suitable data structure. [Note:
You do not need to give detailed pseudocode, but you should explain how you
are adapting the heuristics.]

 

(a) For the bubblesort algorithm, state its best-case Θ complexity and describe, for
any given input of arbitrary size n, one permutation that would trigger this
best-case behaviour. Then give the corresponding permutation of [0, 1, 2,
3, 4, 5, 6, 7, 7, 7]. Then repeat the above for the worst case: state the
Θ complexity, saying when it is achieved, and exhibit as a concrete example a
permutation of the 10 numbers given. [4 marks]
(b) Repeat Part (a) for the heapsort algorithm. [4 marks]
(c) Repeat Part (a) for the basic quicksort algorithm, where the pivot is simply
chosen as the last element in the range. [4 marks]
(d) Write clear and efficient pseudocode to eliminate all duplicates from a linked
list of n elements, without changing the order of the remaining elements. Then
derive and justify its Θ complexity. [4 marks]
(e) [Hint: The Ω notation, like the Θ notation, is typically used to describe the
asymptotic behaviour of a worst-case cost function f(n). When we say, by
extension, that a certain task has a complexity bound of Ω(g(n)), we mean that
this bound applies to the worst-case cost function of every possible algorithm
that could solve that task.]
Give a formula for f(n) ∈ Ω(g(n)), in a format similar to that of the Reminder
above, and briefly explain it. Then derive, with a clear justification, a tight Ω
complexity bound for the task of eliminating all duplicates from a linked list of
n elements.

 

In simplified Mastermind, player A selects a list of n colours among 3 possible colours:
Red, Green and Blue (e.g., [Red; Red; Green; Blue] if n = 4). Player B has to guess
player A's list of colours by proposing lists of colours in sequence until she finds the
list proposed by player A. Every time player B proposes a list of colours, she gets
feedback in the form of a number x. (x is the number of colours that are in the
correct position). For example, if player A's list is [Red; Red; Green; Blue] and player
B guessed [Red; Green; Green; Red], then x = 2 (the first Red and second Green are
at the right positions). Note that x ≤ n.
(a) Define a type colour to represent a colour. [2 marks]
(b) Given two colour lists, write a function feedback that returns x. The first
argument a is the list of player A, and the second argument b is a list of player
B. Raise a SizeMismatch exception if the lengths of both lists do not match.
You may need to introduce a helper function. [4 marks]
(c) Using currying, define a test function that takes a list proposed by player B
and returns x. This function should assume that player A's list is [Blue; Green;
Red]. [2 marks]
(d) What is the type of test in Part (c)? [2 marks]
(e) Write a function generate lists that generates all possible colour lists of a
given length n. The function takes a single argument n. You may use the
concatenation operation @ and List.map function. Tip: generate 2 should
output 32 = 9 lists. [6 marks]
(f ) Given a colour list of player B and a feedback x, write a function valid lists
that takes two arguments b and x and returns all possible lists that player A
could have chosen (such that they match the feedback given to player B). You
may use generate lists, feedback, List.length and/or List.filter.
[4 marks]
3 (TURN OVER)
CST0.2020.1.4
SECTION B
3 Object-Oriented Programming
You have been asked to implement a user-interface component ButtonCanvas which
is both a button that can be clicked by the user and a canvas which the user can
draw on.
Your existing code contains a Button class and a Canvas class. Both of these extend
GuiComponent.
(a) ButtonCanvas could be built using multiple inheritance. What does this mean
in this context? [2 marks]
(b) Give two reasons why this might be desirable. [2 marks]
(c) Give two complexities that arise in this case. [2 marks]
(d) Java interfaces originally contained only abstract methods and static final fields.
How did this restriction avoid the complexities of extending multiple classes?
[3 marks]
(e) Draw a UML diagram for building ButtonCanvas using abstract interfaces rather
than multiple inheritance. Explain how your design attempts to preserve the
desirable properties arising from multiple inheritance.
You do not need to recall the exact UML specification, instead you may provide
a key explaining your notation. [9 marks]
(f ) Recent versions of Java added default methods to interfaces. What is the impact
of this with respect to multiple inheritance?

 

 

Consider expressions represented using the following ML datatype:
datatype exp = Var of string | Neg of exp | Divide of exp * exp
(a) Using at least one union, define a type or types in the C language for
conveniently storing such expressions. [5 marks]
(b) Give efficient C code that checks whether two structures represent identical
expressions. (Do not consider whether they might evaluate to the same result.)
Explain how much of the input expressions is explored when they differ.
[4 marks]
(c) Given that a lot of expressions are to be rapidly generated and discarded, what
considerations apply to storage management? Define and discuss at least 3
different approaches to storage management. [5 marks]
(d) The substitution operation for an expression replaces all occurrences of one
variable with another variable. Given that sub-expression trees are commonly
shared over numerous expressions, explain a problem that could arise in the
substitution operation. Explain the details of a solution to the problem by
giving code or otherwise. [6 marks]
2
CST1.2020.4.3
2 Programming in C and C++
(a) Arrays in C are accessed using square bracket notation.
(i) What are the advantages and disadvantages of array bounds checking?
(ii) Define with examples an array access and a pointer de-reference in the C
language explaining the underlying equivalents.
(iii) State all similarities between array access and pointer dereference and
comment on interactions with possible bounds checks.
[5 marks]
(b) What advantage is gained from allowing a given C program to vary in execution
behaviour from one computer architecture to another? Give three common
example variations. What is the disadvantage of variation? [5 marks]
(c) Give two ways in which C++ templates differ from Java Generics, other than
mere syntactic differences. [4 marks]
(d) Giving a suitable example, explain the effect in C++ of qualifying a member
function (method) with virtual. [3 marks]
(e) Recode the following Java code in C++. Minor syntactic errors will not be
penalised.
class Foo
{ final int[] v; final int s;
public Foo(int n) { s = n; v = new int[n]; }
// In Java garbage collection de-allocates arrays
// appearing in no-longer-used instances of Foo.
// In C++ an alternative solution is required.
}
 

 


Consider commands C composed from assignments X := E (where X is a program
variable, and E is an arithmetic expression), heap allocation X := alloc(E1, ..., En),
heap assignment [E1] := E2, heap dereference X := [E], disposal of heap locations
dispose(E), the no-op skip, sequencing C1; C2, conditionals if B then C1 else C2
(where B is a boolean expression), and loops while B do C. null is 0.
Recall the separation logic partial list representation predicates:
plist(t, [], u) = (t = u) ∧ emp
plist(t, h :: α, u) = ∃y.((t 7→ h) ∗ ((t + 1) 7→ y) ∗ plist(y, α, u))
Circular lists can be represented by clist(t, α) = plist(t, α, t) ∧ (α = [] ⇒ t = null).
(a) Assuming ` {P1} C1 {Q1} and ` {P2} C2 {Q2}:
(i) explain precisely why ` {P1 ∗ P2} C1; C2 {Q1 ∗ Q2} [2 marks]
(ii) give a counterexample to ` {P1 ∧ P2} C1; C2 {Q1 ∧ Q2}. [1 mark]
(b) Give a proof outline for the following circular list 'next' triple:
{clist(X, t :: α)} X := [X + 1] {clist(X, α ++ [t])} [3 marks]
(c) Give a loop invariant (no need for a proof outline) for the following circular list
'length' triple:]
{clist(X, α)}
if X = null then Y := 0
else (Z := [X + 1]; Y := 1; while Z 6= X do (Z := [Z + 1]; Y := Y + 1))
{clist(X, α) ∗ Y = length(α)}
[3 marks]
(d) Give a loop invariant (no need for a proof outline) for the following triple for a
'previous' operation on non-empty circular lists:
{clist(X, α ++ [t])}
Z := X; Y := [X + 1]; (while Y 6= X do (Z := Y ; Y := [Y + 1])); X := Z
{clist(X, t :: α)}
[4 marks]
(e) Give a loop invariant (no need for a proof outline) for the following triple for a
'dial to minimum' operation on non-empty circular lists:
{clist(X, α1 ++ [t] ++ α2) ∧ sorted(t :: merge(sort(α1), sort(α2)))}
Z := X; M := [X]; Y := [X + 1];
(while Y 6= Z do
(N := [Y ]; (if N < M then X := Y else skip); Y := [Y + 1]));
{clist(X, [t] ++ α2 ++ reverse(α1))}
[5 marks]
(f ) Describe precisely all pairs of a stack and a heap that satisfy
∃y, z.((X 7→ y ∗ y 7→ z ∗ z 7→ X) ∧ Y = 0)
[2 marks]
7 (TURN OVER)
CST2.2020.8.8
9 Information Theory
(a) A binary symmetric channel receives as input a bit whose values {0, 1} have
probabilities {p, 1 − p}, but in either case, a transmission error can occur with
probability which flips the bit. The surface plot below describes the mutual
information of this channel as a function M(, p) of these probabilities:
1.
M(ε,p)
A
B
C
(i) At the point marked A, the error probability is = 0. Why then is the
channel mutual information minimal in this case: M(, p) = 0? [2 marks]
(ii) At the point marked B, an error always occurs ( = 1). Why then is the
channel mutual information maximal in this case: M(, p) = 1? [2 marks]
(iii) At the point marked C, the input bit values are equiprobable (p = 0.5), so
the symbol source has maximal entropy. Why then is the channel mutual
information in this case M(, p) = 0? [2 marks]
(iv) Define mathematically the function M(, p) in terms of and p. [4 marks]
(b) An important operation in pattern recognition is convolution. If f and g are two
functions R → C then their convolution is (f ∗ g)(x) = Z ∞
−∞
f(x − y)g(y)dy.
If their respective Fourier transforms are F[f](ω) and F[g](ω), prove that the
convolution (f ∗g)(x) has a Fourier transform F[f∗g](ω) that is the simple product
F[f∗g](ω) = 2πF[f](ω) · F[g](ω).
[6 marks]
(c) Show how a generating (or "mother") wavelet Ψ(x) can spawn a self-similar
family of "daughter" wavelets Ψjk(x) by simple scaling and shifting operations.
Explain the advantages of analysing data in terms of such a self-similar family
of dilates and translates of a mother wavelet. [4 marks]
8
CST2.2020.8.9
10 Machine Learning and Bayesian Inference
(a) Give a detailed description of the general Bayes decision rule for classification.
Include in your answer definitions of the loss, conditional risk, decision rule and
risk. [7 marks]
(b) For a problem with C classes, we suffer a loss of 1 for an incorrect classification
and 0 for a correct one. Show that the Bayes decision rule for inputs x is
h(x) = argmaxc Pr(c|x).


Many languages (like C and Java) support coercions, in which values of one datatype
(e.g., machine integers) can be used where values of another datatype (e.g., floating
point numbers) are expected, by having the compiler silently insert code to convert
from one type to another. Suppose we have a language with the following grammar
of types:

 


(a) Describe the differences between primitive types and objects in Java. Consider:
(i) the values they contain [1 mark]
(ii) where they are stored in memory [1 mark]
(iii) how they interact with Java references [1 mark]
(b) What are auto-boxing and auto-unboxing? Give an example of how they might
cause an exception to be thrown. [4 marks]
(c) Consider the following code in which any arbitrary Java type (primitive or
object) could be substituted for T.
void f(T t) { /* ... */ }
T t1 = /* ... */
f(t1);
For which substitutions of T can we guarantee that the value in t1 is unchanged
after the invocation of f(t1)? Justify your answer. [3 marks]
(d) Explain how Java's implementation of generics precludes substituting T with a
primitive type. [2 marks]
(e) You are asked to redesign the standard library to incorporate an immutable list.
Explain the relative merits of:
(i) MutableList being a subtype of ImmutableList [2 marks]
(ii) ImmutableList being a subtype of MutableList [2 marks]
(iii) ImmutableList and MutableList having no common supertype
[2 marks]
(iv) ImmutableList and MutableList both subtyping CommonList

 

Write  program to Print first 5 even numbers using for loop
e a program to input and print the greater of three numbers.
 


(a) You are looking forward to the European Cup 2020. The tournament is going to
last for 30 days. Each day during the tournament, you want to invite all of your
100 classmates to your house. But people might be busy on any given day, so
you expect each classmate to come with probability 0.03 on each day, and they
show up independently of one another. Let X denote the number of classmates
that show up on any given day.
Note: In parts (ii), (iii) and (iv) you do not have to compute explicit numerical
values.
(i) Give the exact and approximate distributions of X along with parameters.
Explain why the approximation is valid. [3 marks]
(ii) What is the approximate probability that between 2 and 4 classmates,
inclusive, show up on any given day? [3 marks]
(iii) What is the exact probability that at least 2 classmates show up on any
given day? [3 marks]
(iv) What is the probability that there will be more than 27 days where at least
2 classmates show up? [3 marks]
(b) Suppose that each classmate is asked to arrive at 8pm, but the actual arrival time
differs in minutes by a continuous uniform distribution [−θ, +θ], where θ is an
unknown parameter. Your data set Y1, Y2, . . . , Yk is a realisation of independent
random samples from that distribution, for some integer k ≥ 1.
 


(a) Give the probability mass function of each of the three distributions:
(i) Poisson distribution, [2 marks]
(ii) Bernoulli distribution, [2 marks]
(iii) Binomial distribution. [2 marks]
(b) The football association has asked you to analyse the England team football
matches from previous big tournaments. For each of the three situations below,
choose a suitable distribution and compute its expectation and variance.
Note: In Part (b)(ii) you do not have to compute explicit numerical values.
(i) You analyse 2000 penalty kicks from the last 10 years of big tournaments.
It turns out that 1200 of those 2000 penalty kicks were goals. A penalty
kick is chosen at random. Let X be a success if a goal is scored. [2 marks]
(ii) Consider again the setting from (b)(i). If you pick 50 penalty kicks without
replacement, let Y be the number of missed goals out of that sample.
[2 marks]
(iii) Taking into account all games from the last 10 years of big tournaments,
the England football team scored an average of 1 goal every 30 minutes.
Let Z be the number of scored goals during a match of 90 minutes.