evaluating function applications in the

Language of Functions and Procedures (LFP) and the relationship between the

evaluation relations for LFP based upon each of them.

(d) The notion of bisimilarity of two confifigurations in a labelled transition system.

(e) The rules defifining the possible labelled transitions of parallel composition

(P1|P2) and restriction (? c . P) in the Language of Communicating Processes

(LCP).

[5 marks each]

7

[TURN OVERCST.2001.6.8

10 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.

2. What does this item, "//" do? 3. What does this line do: import java.util.Scanner; 4. What is "Scanner"? What does it do? 5. In this line, public class Template Model, what is Template Model the name of? 6. In Java, what does the operator "="do? 7. In Java, what does the math operator "#" do? 8. In the line, name = inputName.nextLine();, what is "inputName"? 9. Is "nextDouble()" a method of Scanner? Yes or no. www 10. What is the difference between a "float" variable and a "double" variable? 11. What does this operator "+" do? 12. What does this operator "++" do in this example, count++? 13. What does this operator "++" do in this example, ++count? 14. What is the concept of "casting" about. 15. If a variable is declared as an "int", is it an integer? Yes or no. 16. What are the two possible values for a boolean variable? 17. Does the relational operator "=" mean "equal to"? Yes or no. 18. Must the saved file name be the same as the class name of a Java program in textPad, yes or no? 19. Does the relational operator "=" mean "not equal to"? Yes or no. 20. Logical conjunction is expressed by the logical operator "&&"? Yes or no.