resolved first by reducing the raw hash value modulo the size of the array and arranging that each array entry refers to the start of a linked list of (index,value) pairs. Retrieving a value from the table involves accessing the array to obtain the correct list of pairs and then scanning the list to find an index value that is identical (use the library function Text.Equal) with the TEXT index being sought. The corresponding value can then be returned. Storing into the table will involve adding a new (index,value) pair to one of the lists. Design appropriate data structures for such a table, and write procedures to store and retrieve values, using the following signatures: PROCEDURE Put(VAR table: Table; key, value: TEXT) RAISES {DuplicateKey} PROCEDURE Get(READONLY table: Table; key: TEXT): TEXT RAISES {MissingKey} [20 marks] 8 CST.94.1.9 11 In Modula-3 what are object types, and how do they differ from simple record data types? In this context give a brief explanation of method invocation, inheritance and of each of the keywords METHODS, NEW and OVERRIDES. Include short examples where appropriate. [10 marks] Describe briefly the facilities in Modula-3 for defining and using array and reference types. Explain the concept of an open array, showing how access to an array that is received as an argument by a procedure may differ from direct references to the same array. Give an example of a programming task that would be harder in Modula-3 if open arrays were not provided.

 

 Describe an algorithm which clips an arbitrary polygon against an arbitrary convex polygon (in 2D). [8 marks] Will your algorithm correctly clip an arbitrary polygon against an arbitrary non-convex polygon? If so, explain why and demonstrate an example which illustrates that it does work in such cases. If not, explain why not and outline how your algorithm could be extended to perform clipping in such cases. [4 marks] 5 Business Studies Describe five criteria a Venture Capitalist might use for assessing a business. [5 marks] Write, in terms of these criteria, an assessment of the Apple iMac project. [3 marks for each criterion] 6 Comparative Programming Languages Early programming languages had relatively poor facilities for type checking, data abstraction, data hiding and encapsulation. Explain the meaning of these terms and discuss their importance. [6 marks] Outline the key features that a language must have to be called object-oriented and briefly discuss to what extent C++, Java and Smalltalk have them. [7 marks] Briefly discuss some of the reasons why C++ programs typically run faster than equivalent programs written in Java or Smalltalk.

 

 

The new Master of (fictional) Porterhouse would like to modernise the college. They
bring the following proposals to the College Council, of which you are a member.
(a) Proposal 1: Change the way students are admitted to the college for all subjects.
Rather than having humans interview candidates, or at least read their references
and personal statements, an algorithm would make all admission decisions.
(i) Use an ethical perspective to make a persuasive argument for or against
Proposal 1, defining and explaining relevant concepts. [5 marks]
(ii) If Proposal 1 is accepted, what changes would the college need to implement
to comply with GDPR? [5 marks]
(b) Proposal 2: The college is buying apartments in the next phase of the North
West Cambridge development for use by graduate students and students with
dependents. The options are to buy a) a range of apartments, from utilitarian
to luxurious, which would be rented out at different amounts; or b) a block of
apartments all of the same size, which would be rented out at the same price.
(i) Use an economic perspective to make a persuasive argument for option a)
or b), defining and explaining relevant concepts. [5 marks]
(ii) If Proposal 2, option a) is accepted, how might the college decide how much
to charge for each grade of apartment? [5 marks]
3
CST1+CST2.2021.7.4
3 Economics, Law and Ethics
(a) You incorporate existing open source code into a program you are writing. What
intellectual property aspects will you need to consider? [4 marks]
(b) What are the economic arguments for and against making code you write open
source? [6 marks]
(c) You are approached by someone who claims to have identified a vulnerability
in your popular software application. They demand you make them a payment,
otherwise they will release the vulnerability publicly. The vulnerability is fixable
and has not (yet) been exploited, however it would likely generate adverse
publicity. What is the ethical approach to take? [5 marks]
(d) You are approached by someone who claims to have identified a vulnerability
in your corporate servers and breached your customer database. They demand
you make them a payment, otherwise they will release the personal information.
Your logs confirm the database has been breached. What is the lawful approach
to take?

(a) The following is a pattern for some legal strings in a language:
[a ∈ A]{0,1} [b ∈ B]{0,1} [c ∈ C]{1,n} [d ∈ D]{1,1}
where A is a finite set of characters from the alphabet, Σ; similarly for B, C, D.
The sets A, B, C and D are disjoint. {x, y} indicates that the previous bracket
must match at least x times but no more than y times.
(i) Specify a Deterministic Finite Automaton, M1, that can recognise these
strings only. [4 marks]
(ii) Design a Regular Grammar, G1, which generates L(M1). [4 marks]
(iii) Describe a set of strings in a natural language that could be generated by
G1 given an appropriate Σ and its subsets A, B, C and D. [1 mark]
(b) We can hypothesise that matches of the following pattern are always valid
constructions in English:
[The Noun]{n,n} [V erb]{n,n}
where Noun represents the coordinated members of a finite set; similarly for
V erb.
(i) Now consider the following English sentence which matches the pattern
when n = 1:
The vaccine worked
Provide example sentences that extend this sentence for the case when
n = 2 and n = 3. [2 marks]
(ii) Assuming that these constructions are part of the English language, would
this mean that English is a Context-Free Language? Justify your answer.
[3 marks]
(iii) Design a grammar in Chomsky Normal Form, G2, which generates the finite
matches of the pattern. [3 marks]
(iv) Specify a Push Down Automaton, M2, that recognises L(G2).

 

 

7 A small electronic mail system has been installed in your organisation, allowing the
dozen or so workers in your group (all users of a single central server computer)
to send each other messages about their work. There is now talk of extending this
mail system to provide contact with several hundred other sites, each of which has
from a dozen to a few hundred workers. For political reasons it will be necessary
to construct a new mail system for this enlarged group, rather than buy in services
from some commercial organisation that provides existing hardware or software.
Discuss some of the problems that will have to be considered in the design of the
new mail system. Concentrate on ways that electronic mail will interact with the
body of users rather than on any fine technical details of a design. In particular
consider:
(a) Mail redirection when a user moves to a new location; [5 marks]
(b) Circulation lists and multiple copies of mail; [5 marks]
(c) Recovery of the cost of setting up and running the mail service; [5 marks]
(d) The possible alternative of using existing telephone lines and installing a large
number of FAX machines.

8 Suppose that take and drop are ML functions such that take(n, s) returns the first
n elements of the list s, while drop(n, s) returns all but the first n elements of s. Let
length(s) be the function to compute the length of the list s. Consider the following
ML function
fun front s = take(length s div 2, s);
fun back s = drop(length s div 2, s);
fun bsum [ ] = 0.0
| bsum [x] = x
| bsum s = bsum front s + bsum back s;
fun sum [ ] = 0.0
| sum (x::s) = x + sum s;
Give a formal proof that sum(front s) + sum(back s) = sum(s) for all lists s,
explaining what properties of arithmetic you are assuming. [9 marks]
Describe a proof of bsum(s) = sum(s) for all s using the lemma that you have just
established. Do not give a detailed proof but instead outline the main argument.
State any additional lemmas required and indicate how they might be proved.
[6 marks]
Does proving bsum(s) = sum(s) for all s in this way ensure that bsum and sum are
completely interchangable in ML programs? Discuss. [5 marks]
4
CST.94.2.5
9 Recall that a binary search tree is a binary tree whose labels are ordered from
left to right, while a priority queue is a collection whose elements are inserted in
any order but are removed in increasing order. Priority queues can be represented
by binary search trees using the normal insert operation; they require additional
functions least and del least. Given a binary search tree, least returns the node
with the smallest label, while del least returns the binary search tree with that
node removed.
Using a suitable datatype for binary trees, code del least as a recursive (and sideeffect free) ML function. Illustrate its operation using an example. [4 marks]
Consider now the cost of emptying an n-label binary search tree by applying
del least to it n times. The cost will be measured by the number of calls to del least,
including recursive calls.
Which binary search trees constitute the best and worst cases for this operation?
State the cost of each as a function of n. [4 marks]
If the tree is perfectly balanced and of depth d then n = 2d −1. Show that the cost
of emptying the tree in this case is d × 2

A functional program cannot update the binary tree 'in place' but must do some
copying. To what extent does the number of calls to del least reflect the true cost
of emptying the tree? Discuss. [4 marks]
SECTION D
10 "Avoidable monopolies are objectionable because they lead to higher prices and/or
lower supply than would be the case in a free market. Patents confer avoidable
monopolies. Therefore, patents are objectionable." How would you defend the
patent system against this argument? [20 marks]
11 You are in charge of the design of both hardware and software for a new (but fairly
conventional) workstation which will have its peripherals (for example a disc drive
and a printer) directly connected to it. Your workstation will be required to support
an operating system that allows its user(s) to run several independent programs at
once.
Explain and justify the method that you will provide for an application program
to gain access to kernel services and physical input/output devices. [12 marks]
For both a printer and a disc drive, indicate additional functions (beyond those
provided by the physical device itself) that an operating system typically provides
in software.

12 If a program is written cautiously and in a suitable high level language then it can
be "portable", and one set of source files can be used with little or no change on a
wide variety of computers and with many different operating systems. Explain the
steps that are taken to turn the source version of such a program into a runnable
version of the application that it represents. Indicate all the places where programs
or pieces of code not derived from the portable sources are involved. [4 marks]
Identify which parts of the software preparation path (if any) will need to be altered
in each of the following cases, commenting on just where programs and code (not
being directly part of the portable source) can be used unaltered and where different
versions are called for:
(a) The program is to be run on different hardware configurations of the various
models of the same computer; [4 marks]
(b) The program is to be run on computers which share the same hardware
design and have the same processor, but under different operating systems
(for example some PCs will run MSDOS, Unix and several other operating
systems); [4 marks]
(c) The program is to be run on two machines that share a common operating
system (such as Unix) but which have different processor designs. [4 marks]
Suppose the portable programming language involved is implemented using an
interpreter rather than a compiler, and the language is already implemented on
all the computer systems involved. How does this affect the amount of work and
the number of changes needed when building an executable version of a program
for use in many different environments?

 

 

A linguist produces the grammar G = (N , Σ, S,P) where:
N = {S, X, Y, V, C}
Σ = {a, contagious, highly, virus}
S = S
P = {S → a X, X → Y virus | virus, Y → V C | C,
V → highly V | highly, C → contagious C | contagious}
(a) Draw all the trees with 4 leaves that can be derived from this grammar.
[2 marks]
(b) Based on corpus data the linguist assigns probabilities to each rule in his
grammar. Describe how the probability of a string is calculated from the rule
probabilities. [2 marks]
A mathematician prefers to generate the strings of a language inductively. She
defines a homomorphism: {(a, a),(c, contagious),(h, highly),(v, virus)}. She defines
L ⊂ Σ
∗ where Σ = {a, c, h, v} using the following axioms and rules:
(a1)
av
u1v
(r1) where u1 ∈ Σ∗
u1cv
acu1
(r2) where u1 ∈ Σ∗
ahcu1
u1hu2
(r3) where u1, u2 ∈ Σ∗
u1hhu2
(c) Let Li = {u ∈ L | length(u) ≤ i}. Find all members of L4 [3 marks]
(d) Describe L as a regular expression and specify a Deterministic Finite Automaton,
M, such that L(M) = L. [4 marks]
(e) Provide an expression for the conditional entropy of X for L5, where X is a
random variable over Σ. A numerical value is not required. [5 marks]
(f ) Suggest some hypotheses about human language processing that we could test
based on the models mentioned in this question. Provide reasons for your
hypotheses. [4 marks]
6
CST1+CST2.2021.7.7
6 Further Graphics
(a) An implicit function based on a kernel regressor can be defined as
P
f(x) =
i αiki(x), where αi are scalar coefficients, ki(xi) = e
−||x−xi||2/σ2
are kernels,
and xi are sample points.
(i) Can αi > 0 define a valid implicit function, why/why not? [1 mark]
(ii) For a point x on the surface, compute the surface normal, simplify as much
as possible. [2 marks]
(iii) Assume the points xi are sampled from a plane passing through the origin.
Will the regressor based implicit function preserve the plane normal? Show
it mathematically. If not, explain a solution to better approximate the
plane with the kernel regresso
(b) We have two surfaces A and B, both of which are represented continuously. We
would like to compute if they intersect. How would you represent A and B
(parametric and/or implicit) and why?
(c) (i) Prove that a plane has zero mean curvature by utilizing ∇Mp = −2Hn.
[2 marks]
(ii) Given a triangular mesh with equilateral triangles and a vertex with
non-negative discrete minimum and maximum curvatures, what is the
maximum number of neighbours it can have? [3 marks]
(d) Assume we embed a number of bones inside the sphere of radius 1 and with center
at the origin and start trying to deform the sphere by only having rotations at
the bones.
(i) If we use linear blend skinning, show whether the transformed points can
be off the sphere. [1 mark]
(ii) If we use linear quaternion blending with normalization, show whether the
transformed points can be off the sphere. [2 marks]
(iii) If we use linear quaternion blending with normalization, will the sphere
stay intact? Briefly explain. [2 marks]
(iv) If we use linear quaternion blending with normalization, but this time
the sphere we are deforming is centered at [1, 1, 1]T
, show whether the
transformed points can be off the sphere.

 

 

 

Predictive text entry systems are familiar on touch screens and mobile phones. This
question asks you to consider how the same principles might be used in a programming
editor for creating Java code.
(a) Explain using Bayes' Theorem how such an editor might update its expectation
about which identifier will appear next, as the programmer is typing a line of
code. Your answer should include a short extract of Java code preceding this line,
in order to illustrate the context in which the expectation is being calculated.
[5 marks]
(b) Describe how you could obtain an empirical measurement of the actual
improvement in efficiency that results from using this predictive editor in
practice. [5 marks]
(c) Consider the four possible combinations of a) small versus large variance,
and b) small versus large effect size, in repeating this measurement. For
each combination, explain the practical interpretation of that data for future
development of the programming editor. [5 marks]
(d) If programmers have the option of whether or not to turn on this new
function in the editor, describe some of the factors that might influence their
decision-making process, with specific reference to the cognitive processes and
sources of information that they would use. [5 marks]
9
CST1+CST2.2021.7.10
9 Further HCI
(a) Augmented reality displays such as the Microsoft Hololens allow elements of the
display to be registered against objects in the physical world. Briefly explain
how such a display could be used for an Internet of Things application, setting
different temperatures for multiple rooms in a home heating system. [1 mark]
(b) Explain how this compares to the use of visual metaphor on a conventional
display for the same application, taking account of the correspondence between
graphical resources and their representational purpose. [3 marks]
(c) Describe an alternative approach to visual representation that could be more
efficient for setting desired temperature in a large number of rooms, for example
in a multi-storey office building. Your description should mention three different
categories of graphic resource, explaining the design principles for each of them
in relation to this application. [8 marks]
(d) Choose three cognitive dimensions that are especially relevant to this problem,
and explain how these dimensions would be different if the temperature settings
were being adjusted using a speech interface such as Amazon Alexa or Google
Assistant. [6 marks]
(e) How could an ethnographic approach be used to develop an alternative theory
of correspondence relevant to this problem? [2 marks]
10
CST1+CST2.2021.7.11
10 Prolog
A Caesar Cipher (or Shift Cipher) produces ciphertext from plaintext by replacing
each letter with another that is found a fixed number of places down the alphabet.
Users provide a key from 1 to 25 (inclusive) to determine the number of places to
move. Our alphabet contains just the 26 lowercase letters and is circular: moving
past z takes you back round to a again. For example under a key of 5 the letter y
would be replaced by the letter d.
When answering this question ensure that each of your predicates has a comment
giving a declarative reading of its behaviour and avoid unnecessary use of cut. Do
not use any extra-logical predicates (such as assertz) or any library predicates.
(a) One way to represent the ordering of characters is with 26 facts indicating the
next character. For example next(a,b) then next(b,c) through to next(z,a).
Use next to implement a predicate nextn(N,C1,C2) which succeeds if the
character C2 appears N places after the character C1. You may assume that
N is always a ground term. [3 marks]
(b) Another approach would be to use a list of characters to record the order of
letters.
Provide an alternative implementation of nextn which makes use of the list
representation [a,b,c,...]. Explain how you deal with the case of moving
past the end of the alphabet.
You may assume the existence of two predicates: scan(C,R,List) which
succeeds if R is the remainder of List that follows the letter C; and
charAt(N,C1,List) which succeeds if C1 is the character at position N in List.
Position 0 is the first element of the list. N must be a ground term. [6 marks]
(c) Compare the merits of these two representations giving three relative benefits
or drawbacks. [3 marks]
(d) Implement a predicate caesar(K,P,C) which succeeds if C is the ciphertext of
the plaintext P under key K. Both ciphertext and plaintext are represented with
a list of letters. You may assume that P and K are ground terms. [3 marks]
(e) The plaintext for a single ciphertext character has been discovered through a
known-plaintext attack. Extend your caesar predicate to recover the key in
this scenario and give an example invocation.

 

(a) Recall that the (local) rendering equation is given as Lo(x, ~ωo) = Le(x, ~ωo) +
R
H2 fr(x, ~ωi
, ~ωo)Li(x, ~ωi) cos θid~ωi
. Simplify this expression progressively as much
as possible after each of the following assumptions. [5 marks]
(i) There is no light emitted from this surface point x.
(ii) Diffuse reflection.
(iii) Reflection is constant at all surface points.
(iv) The incoming light is the same for all incident angles but there can be
occluders.

 

 

Contrast the use of linear versus non-linear operators in computer vision, giving at least one example of each. What can linear operators accomplish, and what are their fundamental limitations? With non-linear operators, what heavy price must be paid and what are the potential benefits? [8 marks] When shape descriptors such as "codons" or Fourier boundary descriptors are used to encode the closed 2D shape of an object in an image, how can invariances for size, position, and orientation be achieved? Why are these goals important for pattern recognition and classification?