Describe the relation = of beta-conversion between terms of the polymorphic lambda calculus (PLC). How can one

No answer yet for this question. Ask a Tutor

Question:

Describe the relation =β of beta-conversion between terms of the polymorphic
lambda calculus (PLC). How can one decide whether two typeable PLC terms
are in this relation? Why does the decision procedure fail for untypeable
terms? [8 marks]
(b) Let ω be the polymorphic type ∀α1((∀α2(α2 → α1)) → α1). Show that there
is a closed PLC term I with the following two properties.
(i) I has type ∀α(α → ω).
(ii) If M1 and M2 are any closed PLC terms of the same type, τ say, and if
(I τ M1) =β (I τ M2), then M1 =β M2.
[Hint: for property (ii), consider the beta-normal forms of I τ M1 α x and
I τ M2 α x, where α is a type variable and x is a variable.]
11 Numerical Analysis II
(a) Explain the term positive semi-definite matrix. [1 mark]
(b) Let A and B be n × n matrices and let x be a vector of n elements. State
Schwarz's inequality for each of the products AB and Ax. What are the
singular values of A, and how are they related to the `2 norm of A?
[4 marks]
(c) Describe briefly the singular value decomposition A = UWVT
, and how it
may be used to solve the linear equations Ax = b. [4 marks]
(d) Let xˆ be an approximate solution of Ax = b and write r = b−Axˆ, e = x−xˆ.
Find an expression for an upper bound on the relative error kek / kxk in terms
of computable quantities. Show how this formula may be computed using the
singular values of A. [8 marks]
(e) Suppose A is a 5 × 5 matrix and its singular values are 103
, 1, 10−14
,
10−18, 10−30. If machine epsilon ' 10−15 then choose a suitable rank for
an approximate solution and form the generalised inverse W+.

(a) Describe the OSI (Open Systems Interconnections) reference model and
discuss examples of the networking functions normally associated with each
component. [14 marks]
(b) What do we mean by layer violation? Discuss some of the reasons that
might lead a pragmatic protocol implementer to engage in layer violation and
illustrate with an example. [6 marks]
4 Distributed Systems
(a) You have been asked to design an event composition and aggregation service
to operate above publish/subscribe middleware to be deployed in various
environmental monitoring scenarios. Your service is to advertise and publish
high-level events of interest to applications. It may subscribe to any published
events in the domain of deployment. Your service may itself be distributed.
Identify a list of technical design issues you would raise with your client prior
to specifying the service in detail. [12 marks]
(b) By means of a diagram illustrate the use of vector clocks to implement the
delivery in causal order of multicast messages among members of a closed,
unstructured process group. Include an explanation of the message delivery
algorithm.

Annotate the circuit to indicate the widths of the transistors required to
give rise and fall times equal to a minimal, balanced inverter. Assume that
p-channel transistors have γ times the resistance of n-channel transistors when
conducting. [4 marks]
(c) Calculate the logical effort and parasitic delay for the circuit. [4 marks]
(d) Sketch a stick diagram for the circuit, arranged for reasonably compact layout.
Assume two layers of metal with power and ground routed in parallel tracks on
the second layer, and arrange for inputs and the output to be available outside
the power rails. [4 marks]
(e) Estimate the size of your layout, assuming a separation of 8λ between the
centre-lines of parallel metal tracks.