"Fortran, Algol and Lisp invented most programming language concepts 50 years ago; adding the concept of object-orientation suffices to explain all programming languages to date". To what extent is this statement true or false? Provide evidence for both, keeping in mind developments in hardware, large-scale system design, type systems and the like. [5 marks] (b) "JavaScript is just Java with dynamic typing". Discuss. [3 marks] (c) In Java and the JVM every value is either a primitive type or a heap-allocated object. However, Java 8 added ML-style functions-as-values. How is this achieved both at the value level and the type level, and does this addition increase the expressiveness of Java or merely provide more compact syntax? [4 marks] (d) What is the difference between internal and external iteration? Explain the key differences between the Collection and Stream interfaces in Java 8, commenting on any association with internal and external iteration. [4 marks] (e) The Stream interface to Java provides the parallel() method to cause the elements of a Stream to be processed in parallel. Comment, fixing any problems you find, on the following program fragment (forming part of a top-level class) which has recently been adjusted by a new employee "to work faster" by the insertion of the call to parallel(). int nin, nout; Stream shortstrings(Stream s) { return s.parallel().filter(w -> { nin++; if (w.length() < return true;} return false; });

Describe briefly the facilities provided in Java for synchronising concurrent threads. [6 marks] An alternative scheme would be to model the system used in some shops where a machine issues numbered tickets to customers, and customers are served in numeric order. A ticket machine holds an integer,s the integer count queue(value) suspends the calling thread until the count is at least as large as the value given as an argument Given a ticket machine, m, and a scheduler, s, a critical region could then be coded as follows: number = m.turn(); s.queue(number); . . protected code . s.next(); Write Java classes TicketMachine, with a turn method, and Scheduler, with next and queue methods. [8 marks] Show how a synchronised buffer holding a single value could be implemented using this new scheme. [6 marks]

The following attempt at Java code might have been written by a beginner. Identify (but do not correct) as many of the mistakes as you can. Explain how each oddity you identify is either something that would prevent the program from compiling, something that would cause it to stop abruptly reporting failure at runtime, a reason why the program might not do anything sensible or just a stylistic oddity. //* A comment to start with: Exam:2000 */ public Class mycode.java { void static public fun main(String [junk]) begin Leaf tr = null; for (i=1; i>10; ++i) tr = new Node(i, tr) tr.print(); end; } class Leaf { integer value; Leaf(int value) { this = value; } public void print() { System.out.println(value); } } class Node extends Leaf { Leaf left, right; Node(leaf l, Leaf r) { left = l, right = r; } void print() { left.print(); System.out.println("val=" @ value); right.print(); } }

(a) Give recursive definition of an ML datatype 'a tree of binary trees consisting of nodes where data items are stored. Each such node is either a leaf or a branch node with left and right trees as branches. [3 marks] (b) Write recursive function size of type 'a tree -> int that returns the number of nodes of a given tree. [4 marks] (c) Write iterative function isize of type int * 'a tree -> int which satisfies the following identity for all integers n and all trees t isize(n, t) = size(t) + n (1) [6 marks] (d) Prove, by structural induction, that the identity (1) holds for the two functions you defined. [7 marks]

(a) Define a polymorphic datatype 'a tree to represent binary trees. [1 mark] (b) A breadth-first traversal of a tree walks over all the nodes at each level before proceeding to the next level. For example the breadth-first traversal of the tree: 1 2 3 4 5 6 7 visits the nodes in the order 1, 2, 3, 4, 5, 6, 7. Define a function breadth: 'a tree -> 'a list such that breadth(t) returns the nodes of tree t in breadth-first order. [10 marks] (c) Define a polymorphic datatype 'a seq to represent lazy lists. [1 mark] (d) Define a polymorphic datatype 'a ltree to represent lazy binary trees. [3 marks] (e) Define a function inorder of type 'a ltree -> 'a seq that traverses a lazy tree in-order, returning the nodes in a lazy list. (You should define any auxiliary functions you may use.) [5 marks]

(a) Give a definition of an ML datatype bool exp to describe Boolean expressions built up from named variables using Boolean operations of conjunction, disjunction and negation: For example, the Boolean expression ((A B) C) D would be given by Conj(Conj(Disj(Var "A",Var "B"),Neg (Var "C")),Var "D") [4 marks] (b) Write ML function variables which takes an argument e of type bool exp and returns a value of type string list which lists all variables occurring in e. [8 marks] (c) Write ML function eval which takes two argumentse of type bool exp and a of type (string * bool) list giving a value for each va

(a) Brieflfly explain the difffferences between combinational and sequential logic.

[2 marks]

(b) With the aid of appropriate diagrams, brieflfly explain the operation of Moore

and Mealy fifinite state machines and highlight their difffferences. [6 marks]

(c) The state sequence for a binary counter is as follows:

The counter is to be implemented using four synchronously clocked D-type

flflip-flflops.

(i) Draw a state table for the counter, showing the required D inputs.

[4 marks]

(ii) Find expressions for the D inputs, making use of unused states if

appropriate. [6 marks]

(iii) What problem could occur when the counter circuit is powered-up? Give

two possible general methods for overcoming the problem. [2 marks]

(a) With the aid of relevant diagrams, show the effffect on the output of a

combinational logic circuit of a:

(i) static hazard;

(ii) dynamic hazard. [3 marks]

(b) Simplify the following expressions using Boolean algebra:

(i) X = (A + B + A . B).(A + B). A . B

(ii) Y = (A + B + A . B). C

[4 marks]

(c) Given:

F = A . B . C . D + A . C + B . C . D + B . C + A . C . D + A . B . C . D

(i) Show using a Karnaugh map that F can be simplifified to

F1 = A . B + A . B + A . C + B . C . D

[2 marks]

(ii) Show that there are a total of four possible expressions for F. [3 marks]

(iii) Show how F1 can be implemented using NAND gates and draw the circuit

diagram. Assume that complemented input variables are available.

[2 marks]

(iv) Show how the static 1 hazard in F1 can be eliminated using a Karnaugh

map-based approach. [2 marks]

(v) Now implement F1 assuming that only 2-input NAND gates are available.

[4 marks]

Let X and Y be sets. You are reminded that a relation from X to Y is a subset of

the product X Y .

(a) Explain what it means for a relation f from X to Y to be a function, an

injection and a surjection from X to Y . [4 marks]

(b) A bijection from X to Y is defifined to be a function from X to Y which is

both an injection and a surjection. Prove that a function f from X to Y is a

bijection iffff it has an inverse function g, i.e. g is a function from Y to X such

that g f = idX and f g = idY .

[Remember to prove both the "if" and "only if" parts of the assertion.]

[12 marks]

(c) Describe, without proof, a bijection from P(X Y ) to (X P(Y )) and its

inverse. [4 marks]

Let I be a non-empty subset of the natural numbers N = {1, 2, 3, }.

The set S is defifined to be least subset of N such that

I S, and

if m, n S and m < n, then (n m) S.

Defifine h to be the least member of S. This question guides you through to a proof

that h coincides with the highest common factor of I, written hcf (I), and defifined

to be the natural number with the properties that

hcf (I) divides n for every element n I, and

if k is a natural number which divides n for every n I, then k

divides hcf (I).

[Throughout this question you may assume elementary facts about division.]

(a) The set S may also be described as the least subset of N closed under certain

rules. Describe the rules. Write down a principle of rule induction appropriate

for the set S. [4 marks]

(b) Show by rule induction that hcf (I) divides n for every n S. [3 marks]

(c) Let n S. Establish that

if p.h < n then (n p.h) S

for all non-negative integers p. [5 marks]

(d) Show that h divides n for every n S. [Hint: suppose otherwise and derive a

contradiction.] [5 marks]

(e) Explain very brieflfly why the results of parts (b) and (d) imply that h = hcf (I).

[3 marks]

(a) Suppose that X is a random variable whose value r is distributed Geometric(p).

Write down the expression for the probability P(X = r). [3 marks]

(b) By using a suitable generating function or otherwise, show that the expectation

E(X) = (1 p)/p. [5 marks]

The University Computing Service defifine a serious power outage as a power cut that

lasts for longer than their Uninterruptable Power Supply equipment can maintain

power. During the course of an academical year the number of serious power outages

is a random variable whose value is distributed Geometric(2/5). Accordingly, the

probability of having no serious power outages during the course of a year is 2/5.

(c) The University is investigating a compensation scheme which would make no

payment over the year if the number of serious power outages were zero or

one but which would pay the Computing Service 1000 for every such outage

(including the fifirst) if the total number of serious power outages in a year were

two or more. Determine the expected annual sum that the Computing Service

would receive. [8 marks]

(d) To what value would the parameter of the Geometric Distribution have to be

changed (from 2/5) for the expected annual sum to be 750? [4 marks]

(a) Give a brief account of the Trinomial Distribution and include in your

explanation an expression that is equivalent to n

!

r!(n

r)! prqnr for the Binomial

Distribution. [5 marks]

(b) An indicator light can be in one of three states: OFF, FLASHING and ON, with

probabilities 1/2, 2/5 and 1/10 respectively. A test panel has fifive such lights

whose states are mutually independent.

(i) What is the probability that all fifive lights are OFF? [3 marks]

(ii) What is the probability that three lights are OFF, one light is FLASHING

and one light is ON? [3 marks]

(iii) What is the probability that three or more lights are OFF and at most one

is ON? [9 marks]

All results must be expressed as fractions.

operate. For example, a vehicle control system should be

aware of the fact that the car has precisely four wheels. This kind of information

must be captured, encoded and tested at each stage of the software design process.

Using the number of wheels in a car as a simple example, describe relevant design

activities and products at each of the following phases of a software project:

(a) inception; [4 marks]

(b) elaboration; [4 marks]

(c) construction; [4 marks]

(d) transition; [4 marks]

(e) system operation. [4 marks]

(a) Explain what is a context-free grammar and the language it generates.

[4 marks]

(b) What does it mean for a context-free grammar to be regular? Given any

deterministic fifinite automaton M, describe a regular context-free grammar

that generates the language of strings accepted by M. [4 marks]

(c) Construct a non-deterministic fifinite automaton with -transitions whose

language of accepted strings is equal to the language over the alphabet {a, b, c}

generated by the context-free grammar with non-terminals q0 and q1, whose

start symbol is q0 and whose productions are q0 abq1, q1 , q1 q0 and

q1 abc. [4 marks]

(d) Is every language generated by a context-free grammar equal to the

set of strings accepted by some non-deterministic fifinite automaton with

-transitions? Justify your answer. (Any standard results about regular

languages you use should be carefully stated, but need not be proved.)

[8 marks]

(a) The British Computer Society Code of Conduct has four sections. What kind

of professional conduct does each section cover, and how does each of these

kinds of conduct benefifit the profession and its members? [8 marks]

(b) True or False questions:

(i) A User can provide occasional use of the University computer system for

a friend who is a temporary visitor.

(ii) Circumstances that mitigate minor infractions of the rules promulgated

by the Information Technology Syndicate include, among other things,

inebriation.

(iii) Appropriate use of the Cambridge University Data Network (CUDN)

means bona fifide academic activity plus a low level for private purposes.

(iv) Small amounts of commercial activity are acceptable as long as the User

is acting in a private capacity.

[4 marks]

(c) The IT industry is increasingly aware of its own environmental impact.

Describe at least one environmental problem to which the industry contributes

and how, as an IT professional, you can help to solve this problem. [4 marks]

(d) "Social engineering is a greater threat to computer security than computer

cracking software." What is social engineering and what measures can be

taken to guard against it? [2 marks]

(e) What is copyleft and how is it used to protect free, open-source, software?

How do software engineering tools change as systems scale? Discuss this question

with reference to

(a) a 2000-line device driver for a safety-critical sensor on board an aircraft;

(b) a 100,000-line engine control unit for a diesel engine that adapts it for use in

trucks, generators or irrigation pumps;

(c) a 1,000,000-line social networking site such as Facebook or MySpace;

(d) a 50,000,000-line operating system.

[20 marks]

(a) The classic MIPS 5-stage pipeline is depicted below.

instruction

decode and

execute

memory

write

fetch

register fetch

access

back

(i) With reference to the 5-stage pipeline, what are data hazards and how

can they be resolved to ensure that the programmer's model of sequential

execution is always preserved whilst minimising performance impact?

[6 marks]

(ii) With reference to the 5-stage pipeline, what are control hazards and how

can they be resolved? [4 marks]

(b) If we wanted the above pipeline to mimic two processors running at half the

speed, then we could have two copies (A and B) of the register state and keep

the existing pipeline. The instruction-fetch stage would alternate between

fetching from threads A and B on alternate clock cycles. As a consequence, if

instruction fetch was from thread B, then an instruction from thread A would

be in decode, B in execute, A in memory access and B in write back.

(i) For this dual-threaded processor, if branches are performed in the decode

stage, does the pipeline exhibit a branch delay slot? [5 marks]

(ii) How can the resolution of data hazards be simplifified for this dual-threaded

processor? [5 marks]

(a) Describe fifive physical properties of a communications channel. [5 marks]

(b) Consider the fifigure below. Entities N and N0 use an ARQ system.

(i) Explain how the latency of channel n 1 can have a direct effffect on the

capacity of channel n. [6 marks]

(ii) Defifine windowing as it relates to an ARQ system and describe how the

capacity of the ARQ system may be improved through its use. [4 marks]

(iii) If an ARQ system is used for an interactive session, the ARQ system

can lead to many small packets, each under-full and perhaps sent with

signifificant overhead. Design and describe an algorithm that overcomes

the limitation of sending many mostly-empty packets for an interactive

session. [5 marks]

(a) A web server is an application that listens for incoming network connections

on TCP port 80. Once a connection is established, the task of processing

client requests and sending replies can be handled by an instance of a

Worker class which you may assume already exists. Worker implements the

java.lang.Runnable interface and has an accessible constructor that takes as

argument a java.net.Socket object representing the network connection to

a client.

Provide the Java code for a webserver which, upon start-up, attempts to listen

on TCP port 80 and starts a new Thread running a new Worker for every

connection. Your program should print helpful error messages indicating the

likely cause of problems when it is unable to proceed as expected. [10 marks]

(b) A busy web server might expect to handle concurrent requests to read and

update some shared data and could use Timestamp Ordering (TSO) to enforce

isolation between concurrent transactions.

(i) Explain how TSO enforces isolation. [5 marks]

(ii) Is TSO appropriate for a web server application? Explain your reasoning.

[5 marks]

(a) Describe in detail an algorithm that returns the minimum distance from a

point to a line segment in two dimensions. Ensure that you include all of your

assumptions and all necessary mathematical calculations. [7 marks]

(b) A quadratic Bezier curve is defifined by three points, P1, P2, P3, and a

parameter, t:

P(t) = (1 t)2P1 + 2t(1 t)P2 + t2P3, 0 t 1

Describe an algorithm that draws the quadratic Bezier curve, using straight

lines only, to within a tolerance . You may use the algorithm from part (a)

and you may assume that you already have an algorithm for drawing a straight

line. [8 marks]

(c) Consider the control of detail in a curve that is represented by a sequence of

many straight line segments. Describe how Douglas and Pucker's algorithm

can be used to remove superflfluous points. You may use the algorithm from

part (a). [5 marks]

Consider the following grammar for expressions (where Id is a terminal symbol

representing an identififier resulting from lexical analysis):

Expr ::= 1 | 2 | Id | Expr + Expr | Expr / Expr |

Expr ^ Expr | (Expr)

(a) Explain in what principal respect this grammar is unsatisfactory. [1 mark]

(b) Assuming further that + is to be left-associative, ^ is to be right-associative and

/ is to be non-associative (i.e. 2/2/2 is forbidden but (2/2)/2 and 2/(2/2)

are allowed), re-write the grammar to reflflect this. [4 marks]

(c) List the terminal symbols and non-terminal symbols, and count the production

rules both in the original grammar and in the grammar in your answer to

part (b). Indicate the start symbol in both grammars. [2 marks]

(d) Defifine a type or types (in C, Java, or ML) suitable for holding an abstract

syntax tree resulting from your answer to part (b). [2 marks]

(e) Give a brief and elementary explanation of the principles of how the grammar

resulting from part (b) might be used to create a syntax analyser taking a

token stream as input (via calls to function lex()) and giving as output an

abstract syntax tree corresponding to part (d). Mention both hand-written

and automatically-generated syntax analysers. [8 marks]

(f ) Summarise any issues related to left- or right-associative operators in the

two techniques (in implementing the parser and in constructing the tool) you

outlined in part (e). [3 marks]

(a) Write procedure and a call to it in block-structured pseudocode such

that the execution of the procedure under pass-by-reference and under

pass-by-value/result yields difffferent outcomes. Justify your answer.

[7 marks]

(b) Explain the meaning of static (i.e. compile-time) and dynamic (i.e. run-time)

type checking.

Compare the advantages and disadvantages of these two approaches to type

checking from the point of view of the language designer, the language

implementer, and the programmer.

[6 marks]

(c) Explain how objects can be simulated in SML, giving an example.

Does it follow that SML, together with its module system, is an object-oriented

programming language? Why?

[7 marks]

(a) What is the difffference between a key and a functional dependency? [3 marks]

(b) The schema R(A, B, C, D, E) has the following functional dependencies.

(i) What are all of the keys of R? [3 marks]

(ii) Which functional dependencies violate Boyce-Codd Normal form

(BCNF)? [3 marks]

(iii) Which functional dependencies violate Third Normal form (3NF)?

[3 marks]

(iv) Find a lossless-join decomposition of R into BCNF relations. [8 marks]

8CST.2008.5.9

(a) Defifine the translation of the call-by-name -calculus into continuation passing

style. [9 marks]

(b) How does the translation diffffer for the call-by-value -calculus? [2 marks]

(c) Now consider extending the call-by-name -calculus with exceptions:

where it reduces in the following way:

try raise catch M M

try x.M1 catch M2 x.M1

raise M

raise

Show how to translate this language into pure -calculus using continuations.

[Hint: Use two continuations: one for the exceptional case, and one for the

normal case.]

[9 marks]

(a) The Halting Problem for register machines is unsolvable. State, without proof,

a precise form of this result. [3 marks]

(b) Let the computation by program c on data d be represented by the natural

number k that codes the pair (c, d). By considering the set H(k) of the

HALTing computations represented by codes k0 < k, show that there is an

increasing total function h(k) which grows too fast to be computable.

[6 marks]

(c) Given h : N N with the above property

let f(k) = h(k) + k

and g(x) = sup{k : f(k) 6 x}.

Then f : N N is strictly increasing, and g : N N satisfifies

g(f(k)) = k, g(x) < k

for all x < f(k).

Show that g grows too slowly to be computable in the following sense:

given G : N N such that

(i)

{G(n) : n N} is unbounded

(ii) G(n) 6 g(n) for all n N

then G(n) is not computable. [11 marks]

Below is a fragment of L1, equipped with a rather strange semantics. Call it L?.

Booleans b B = {truetrue

true,falsefalse

false}

Integers n Z = {. . . , 1, 0, 1, . . .}

Locations ` L = {l 0, l 1, l 2, . . .}

Stores s, fifinite partial functions from L to Z

Operations op ::= + |

Expressions e ::= b | n | !` | ` := e | e1 op e2 | ifif

if e thenthen

then e1 elseelse

else e2

(op +) h n1 + n2, si hn, si

if n = n1 + n2

(op ) h n1 n2, si hb, si

if b = (n1 n2)

(opA)

h e1, si he01, s0 i

h e1 op e2, si he01 op e2, s0 i (opB)

(deref) h !`, si hn, si

if ` dom(s) and s(` ) = n

(assignA) h ` := n, si hn, s + {` 7 n}i

if ` dom(s)

(assignB)

h e, si he0 , s0 i

h ` := e, si h` := e0 , s0 i

(ifA)

h e, s1i h truetrue

true, s2i

h ifif

if e thenthen

then e1 elseelse

else e2, s1i he1, s1i

(ifB)

h e, s1i h falsefalse

false, s2i

h ifif

if e thenthen

then e1 elseelse

else e2, s1i he2, s1i

Here is the reflflexive transitive closure of , defifined by:

(incl)

h e, si he0 , s0 i

h e, si h e0 , s0 i

(tran)

h e, si h e0 , s0 i h e 00 , s 00 i

h e, si h e 00 , s 00 i

(reflfl)

h e, si h e, si

(a) Give a terminating sequence of reduction steps, with full derivations for each,

of the confifiguration

h ifif

if (` 0 := 3) 2 thenthen

then 7 elseelse

else 8, {` 0 7 0}i

[5 marks]

(b) Describe, with examples and alternative reduction rules, how the behaviour

of L? expressions diffffers from that in L1: for (i) binary operations, (ii) store

operations, and (iii) conditionals. Discuss the effffects that these difffferences

could have on programming in the language. [15 marks]

11 (TURN OVER)CST.2008.5.12

12 Complexity Theory

(a) Give a precise defifinition of what it means for one decision problem to be

polynomial-time reducible to another. [3 marks]

(b) Consider the following two decision problems:

HamCycle: Given a graph G = (V, E) does it contain a cycle that visits

every vertex exactly once?

HamPath: Given a graph G = (V, E) and two distinguished vertices

s, t V , is there a simple path in G that starts at s, ends at t and visits

every other vertex exactly once?

Show that HamCycle is polynomial-time reducible to HamPath. [8 marks]

(c) The following decision problem is known to be solvable in polynomial time:

EulerCycle: Given a graph G = (V, E) does it contain a cycle that visits

every edge exactly once?

What can you conclude about the truth of the following statements? Justify

your answers.

(i) EulerCycle is polynomial-time reducible to HamCycle. [3 marks]

(ii) EulerCycle is polynomial-time reducible to HamPath. [3 marks]

(iii) HamPath is polynomial-time reducible to EulerCycle. [3 marks]

kindly answer all the questions