Indicate whether the following statements are true or false. Provide an argument for each answer. You may
Question:
Indicate whether the following statements are true or false. Provide an argument for each answer. You may use standard results provided that you state them clearly. (a) For all PCF-types ? and closed PCF-terms M1 and M2 of type ? , if [[M1]] = [[M2]] in [[? ]] then M1 ?=ctx M2 : ? [6 marks] (b) For all PCF-types ? and closed PCF-terms M1 and M2 of type ? , if M1 ?=ctx M2 : ? then [[M1]] = [[M2]] in [[? ]] [7 marks] (c) For all closed PCF-terms M1 and M2 of type nat ? nat, if M1 ?=ctx M2 : nat ? nat then [[M1]] = [[M2]] in (N? ? N?) [7 marks] 6 Digital Communication II (a) A network consists of a central hub router, with links (spokes) to a set of routers at outlying sites. A network designer is trying to choose which routing protocol to deploy. (i) Illustrate the operation of Link State and Distance Vector routing algorithms over this simple topology. [6 marks] (ii) What are the overall packet counts for each protocol in the whole network from turning the system on until all routers know where all destinations are? [2 marks] (b) Another network consists of a set of sites with routers, connected in a long line. (i) Illustrate the operation of Distance Vector routing when one link at one end fails. [6 marks] (ii) What are two common techniques to improve the performance of the protocol in these scenarios? [4 marks] (c) Why do path vector protocols not have this problem?
Foundations of Functional Programming
The following are some concepts that have flflourished in the context of functional
programming but which have (so far) been less heavily used in main-stream
languages even when they have been available:
(a) polymorphic types
(b) type reconstruction
(c) higher-order functions
(d) lazy evaluation
(e) continuations
For each case give a brief explanation of the facility referred to, suggest a
circumstance in which it might be useful and comment on how immediately relevant
to non-functional languages it seems.
[4 marks per part]
8CST.2001.6.9
11 Logic and Proof
(a) In the context of clause-based proof methods, defifine the notion of pure literal
and describe what should be done if the set of clauses contains pure literals.
[3 marks]
(b) Use the Davis-Putnam method to discover whether the following set of clauses
is satisfifiable. If they are satisfifiable, show a satisfying interpretation.
{P, R} {P, R} {P, Q} {Q, R} {P, Q, R}
[6 marks]
(c) The three-fifingered inhabitants of the planet Triterra build base-3 computers.
A Triterran named Randal Tryant has found a way of verifying base-3
combinational logic. His Ordered Ternary Decision Diagrams (OTDDs) are
the same as a technology used on planet Earth except that all variables and
expressions range over the values 0, 1 and 2 instead of just 0 and 1.
(i) Describe how a full ternary decision tree can be reduced to an OTDD
without regard for effiffifficiency. [2 marks]
(ii) Sketch an effiffifficient algorithm to convert a ternary expression directly to an
OTDD without constructing the full decision tree. For a typical ternary
connective use modulo-3 multiplication, written as ?. [6 marks]
(iii) Demonstrate your algorithm by applying it to the ternary expression
((i ? i) ? j) ? 2. [3 marks]
9
[TURN OVERCST.2001.6.10
12 Complexity Theory
(a) Show that any language that can be accepted by a nondeterministic machine
in time f(n) can also be decided by a deterministic machine in space O(f(n)).
[4 marks]
(b) Show that any language that can be accepted by a nondeterministic machine
in space f(n) can also be decided by a deterministic machine in time
O(c(f(n)+log n) ), for some constant c. [6 marks]
(c) Explain what the above results tell us about the inclusion relationships among
the complexity classes:
NL, co-NL, P, NP, PSPACE and NPSPACE
[4 marks]
(d) It has been proved that the graph reachability problem is in co-NL. What
further inclusions can you derive among the above complexity classes using
this fact? Explain your answer. [6 marks]
Describe an O(n log(n)) algorithm based on a variation of merge sort to fifind the
closest pair of a given set of points lying in a plane. You may assume that the set
of points is given as a linked list of (x, y) coordinates. [8 marks]
Carefully prove that your algorithm can never take longer than O(n log(n)).
[6 marks]
Modify, with explanation, your algorithm to fifind the pair of points with minimum
Manhattan distance. The Manhattan distance between points (x1, y1) and (x2, y2)
is |x1 ? x2| + |y1 ? y2|. [6 marks]
1
[TURN OVERCST.2000.6.2
2 Computer Design
Why are the following statements fallacies?
(a) MIPS is an accurate measure for comparing performance among computers.
[5 marks]
(b) A benchmark is a typical program which accurately predicts the performance
of all other applications. [5 marks]
(c) Complex instruction set computers minimise the semantic gap between
machine code and high-level languages, thereby making applications run more
quickly. [5 marks]
(d) Data caches always improve processor throughput. [5 marks]
3 Digital Communication I
Compare circuit switching and packet switching, paying attention to channel
characteristics and resource effiffifficiency. [7 marks]
What is wave division multiplexing (WDM)? Is it more like circuit switching or
packet switching and why? [7 marks]
Wave length conversion is the process, either optical or optical-electronic-optical,
of receiving a signal on one wavelength and transmitting on another.
How does wave length conversion ease the problem of routing optical carriers in a
network? [3 marks]
"The huge capacity of WDM systems will mean that IP becomes redundant."
Expert Answer:
Introduction to Governmental and Not for Profit Accounting
ISBN: 978-0132776011
7th edition
Authors: Martin Ives, Terry K. Patton, Suesan R. Patton
