A discrete sequence {xn} can be converted into a continuous representation x(t) = ts X n= (t n ts) xn, where ts is the sampling period. (a) State two characteristic properties of Dirac's function. [2 marks] (b) Describe briefly how this representation helps to explain aliasing. [4 marks] (c) Define three functions h(t), such that convolving x(t) with h(t) results in (i) the output of an idealized analog-to-digital converter that holds the output voltage of each sample xn for the time interval from t = n ts until the next sample xn+1 arrives at time t = (n + 1) ts ; [4 marks] (ii) linear interpolation of {xn}; [4 marks] (iii) reconstruction of a signal x(t) that was sampled as xn = x(n ts), assuming that the Fourier transform of x(t) is zero at any frequency f with |f|

Suppose we have a relational database with five tables. table key attributes S(sid, A) sid T(tid, B) tid U(uid, C) uid R(sid, tid, D) sid, tid Q(tid, uid, E) tid, uid Here R implements a many-to-many relationship between the entities implemented with tables S and T, and Q implements a many-to-many relationship between the entities implemented with tables T and U. (a) Write an SQL query that returns all records of the form sid, uid where sid is the key of an S-record and uid is the key of a U-record and these two records are related through the relations R and Q. Use SELECT and not SELECT DISTINCT in your query. [3 marks] (b) Write an SQL query that returns records of the form A, C where the A-value is from an S-record and the C-value is from a U-record and these two records are related through the relations R and Q. Use SELECT and not SELECT DISTINCT in your query. [3 marks] (c) Could one of your queries from parts (a) and (b) return more records than the other? If so, which one? Justify your answer. [3 marks] (d) Suppose you replaced SELECT with SELECT DISTINCT in your queries from parts (a) and (b). Could one of these modified queries return more records than the other? If so, which one? Justify your answer. [3 marks] (e) Consider again your query from part (a). If pair sid, uid is returned by this query then there must exist at least one "path" that goes from from table S to table T (via relation R) and then from table T to table U (via relation Q). Note that there can be many such paths for a given pair sid, uid. Write an SQL query that returns records of the form tid, total where tid is a key of a record from table T and total indicates the total number of such paths that "go through" that record. [8 marks]

) What is a page fault? [2 marks] (b) How is a page fault handled if it is triggered by a process issuing a write for which it has permission on a machine with ample free memory at the point the page fault occurs? [6 marks] (c) If the machine does not have sufficient free memory at the point that the page fault occurs, a victim page must be selected for replacement. Describe the ideal algorithm for handling this case, and explain why it cannot be implemented. [2 marks] (d) Now describe a practical algorithm for selecting a victim page for replacement. In your answer you should discuss its performance, storage and time overheads, indicating any assumptions you make. [6 marks] (e) What is Belady's Anomaly? Can the algorithm described in Part (d) suffer from it? Justify your answer. (

untrusted code: int table[800]; int insert_in_table(int val, int pos) { if (pos > sizeof(table) / sizeof(int)) return -1; table[pos] = val; return 0; } Identify potential vulnerabilities and provide a fixed version. [4 marks] (b) When you log into a system that uses Kerberos authentication by providing a password (e.g., using the Unix/Linux/macOS command kinit): (i) What data does your computer send to and receive from the keydistribution centre (KDC) and which parts of that data are encrypted with whose key or password? [9 marks] (ii) What is the purpose of a ticket-granting ticket? [2 marks] (iii) Where are Kerberos tickets stored? [2 marks] (c) Suggest and briefly explain three countermeasures used by a typical Linux distribution to mitigate the risk of stack-overflow vulnerabilities in included software. [3 marks]

(a) Why is I/O buffering used by operating systems? [2 marks] (b) Explain why both mutual exclusion and condition synchronisation are needed for controlling access by concurrent processes to a shared buffer. [3 marks] (c) Why is forbidding interrupts not a general solution to implementing concurrency control? [1 mark] (d) Explain how a "read and clear" instruction can be used as a basis for building concurrency control. [2 marks] (e) Define semaphores, including how they differ from a simple free/busy flag. [2 marks] (f ) The following pseudocode fragments represent access by a single producer and a single consumer to a shared, N-slot, cyclic buffer. items is a semaphore initialised to 0 spaces is a semaphore initialised to the buffer size, N producer repeats: consumer repeats: produce data WAIT (items) WAIT (spaces) remove data from buffer insert data in buffer SIGNAL (spaces) SIGNAL (items) consume data (i) Explain in detail how the semaphores are being used to enforce concurrency control. [6 marks] (ii) Extend the code fragments for multiple producers and multiple consumers, explaining how your solution implements concurrency control. [4 marks

Consider the following learning problem in which we wish to classify inputs, each consisting of a single real number, into one of two possible classes C1 and C2. There are three potential hypotheses where Pr(h1) =are the following functions hi(x) = x i 1 5 and the likelihood for any hypothesis hi is Pr(x C1|hi , x) = (hi(x)) where (y) = 1/(1 + exp(y)). You have seen three examples: (0.9, C1), (0.95, C2) and (1.3, C2), and you now wish to classify the new point x = 1.1. (a) Explain how in general the maximum a posteriori (MAP) classifier works. [3 marks] (b) Compute the class that the MAP classifier would predict in this case. [10 marks] (c) The preferred alternative to the MAP classifier is the Bayesian classifier, computing Pr(x C1|x, s). where s is the vector of examples. Show that Pr(x C1|x, s) = X hi Pr(x C1|hi , x) Pr(hi |s) What are you assuming about independence in deriving this result? [3 marks] (d) Compute the class that the Bayesian classifier would predict in this case. [4 marks

Write class called Course _xxx that represents a course taken at a school. Represent each student using the Student class from the Chapter 7 source files, Student.java. Use an ArraylList in the Course to store the students taking that course. The constructor of the Course class should accept only the name of the course. Provide a method called addStudent that accepts one Student parameter. Provide a method called roll that prints all students in the course. Create a driver class School xxx with a main method that creates a course, adds several students, and prints a rol. Submit School_xxxjava and Course ooxjava where xxox are your initials. Student.java public class Student private String firstName, lastName; private Address homeAddress. schoolAddress:

Explain the following Java words. For each write sentence giving an overview of what the word is about, then either write second sentence that shows how it fits in with related concepts or write a small code-fragment to illustrate its purpose: (a) abstract; (b) assert; (c) boolean; (d) break; (e) byte; (f ) case; (g) catch; (h) extends; (i) new; (j) null. [2 marks each] Please keep your explanations of each word brief so that your whole answer to this question remains a reasonable size: you are not expected to produce a detailed explanation or comprehensive illustration.

Consider the design of a Java application for the automated marking of exam questions on Java. The answer to each question consists of Java source code. Your application should read the text of each answer from a file, and check that actual lines of code expected by the examiner are included at any point in the answer. The examiners will want to calculate the average mark (out of 20) for each question, and also the total mark (out of 100) achieved by each candidate in a paper consisting of 5 questions. Model answers should take the form of an executable Java class, for example a class called question1model might contain the following method: protected void defineAnswer() { expectedLines.add("import java.io.*;"); expectedLines.add("public class helloWorld"); expectedLines.add("system.out.println(\"hello world\");"); } Provide a UML diagram showing the classes in the application, and write the basic code for each class, in order to achieve the above fied to Java fields and methods. Why are they useful? [4 marks] (b) When you extend a class, the constructor for your new class will reference the constructor of the parent class, and this latter constructor may have any of the four possible access regimes. Comment on the consequences of each of the four possibilities. [4 marks] (c) If the only constructor for a class is marked as private, is it ever possible to have an instance of that class or any subclass of it? Explain why or why not. [2 marks]

T). At each time step all cells transform simultaneously. If a cell is dead, it becomes alive if it had (just before this time step) exactly three live neighbours. If it is alive, it becomes dead unless it has two or three live neighbours. In this question, locations beyond a 1000 1000 board are to be treated as permanently dead. (a) Show how to set up a simple Java 2-dimensional array of boolean values to represent a Life Board, with all cells initially "dead". [2 marks] (b) For a location (i, j) on the board, give code that will decide whether the next state of that cell should be alive or dead. Make it clear how your code copes if the cell is at the boundary of the board. [4 marks] (c) Referring to part (b), write code that takes one board representing the current state of the game and fills in a second board-array with the state arrived at after one time step. What would happen if instead of using two arrays you wrote the new cell state directly back, using just a single copy of the board? [3 marks] (d) Re-work your solution to part (c) so that you can perform a time step using just one board. You may need to use a 1000-element vector to store information in a way that makes the update safe. [7 marks] (e) All the code you have written so far uses an array of boolean values. Some programmers would instead use an array of int values and treat each of the 32 bits in each int as giving the status of a cell. Suppose you have a 2-dimensional array of integers of size 1024 by 32 (that size is chosen so the array of integers may be viewed as a 1024 by 1024 array of bits): give code to retrieve a bit from a given position (i, j). [4 marks]

A company has fired one of its senior staff after an incident that they claimed was an accident, but where the directors suspected malice. The company's auditors have suggested a review of the company's systems to mitigate 'the insider threat', and your advice has been sought. The directors want to be able to assure the shareholders that they are taking all reasonable steps to limit the damage that staff could do to affect the company's share price, whether accidentally or otherwise. (a) Describe a multilevel security policy briefly, explaining what sort of harms it seeks to prevent, and how. [5 marks] (b) Describe a separation-of-duty security policy briefly, explaining what sort of harms it seeks to prevent, and how. [5 marks] (c) Describe one approach to minimising the risk of user error that is based primarily on psychology. [5 marks] (d) Introducing architectural changes to the company's information systems will take time, while changes to user interfaces and workflows are often simple to implement. Which psychological approaches might be adopted more quickly, and what might you expect to go wrong? [5 marks]

Consider the following grammar: ce, cats} V {saw, grinned} (a) The grammar can be used to generate the following sentences: (i) Alice saw cats (ii) Cats Alice saw grinned Draw derivation trees for both of these sentences. [2 marks] (b) What is the longest sentence that can be generated by the grammar? Describe this sentence. [2 marks] (c) Is the language generated by the grammar a regular language? Provide a proof for your answer. [8 marks] (d) A psycho-linguistic experiment shows that, by the 2nd word in the sentence, Part (a)(ii) is harder to process than the sentence Part (a)(i). Yngve hypothesised that a speaker's short-term memory functions as a stack. Explain how this hypothesis might account for the experimental results by drawing the stack arising from a top-down parse of the two sentences. [4 marks] (e) How might the sentence in Part (a)(ii) be altered so that it has the same meaning but is easier to process? Explain your reasoning.

A Boolean satisfiability problem has four variab The aim is to find assignments to the variables such that f is true under the usual rules for Boolean operations. This question addresses the use of more general constraint satisfaction to solve this problem. (a) Give a general description of a constraint satisfaction problem (CSP). [3 marks] (b) Explain how a Boolean satisfiability problem in CNF form and with n variables can be converted to a CSP, also having n variables and having a suitable constraint for each clause. Illustrate your answer using the 4-variable formula f in (1). [3 marks] (c) Explain, again using a constraint corresponding to a clause from (1), how general constraints can be converted to binary constraints. Provide a graph illustrating the problem from (1) after it has been converted to a CSP with only binary constraints. [4 marks] (d) Explain, how forward checking works in the context of a general CSP. How does this benefit a CSP solver? [3 marks] (e) Using the CSP equivalent you developed for (1), with only binary constraints, demonstrate how forward checking works using the sequence of assignments x1 = F, x2 = F, x4 = T. [5 marks] (f ) How would you expect the solution obtained when applying forward checking to be affected if constraints were allowed to propagate more widely? [2 marks]

A program is required to draw an arc from (0, 1) to (1, 0) of the circle centred t the origin with unit radius. (a) One approach would be to draw a segment of the cubic Overhauser curve defined by i) Explain how a segment of an Overhauser curve in general can be represented as an Hermite cubic and so as a Bezier cubic. [4 marks] (ii) Derive the formula for the resulting Bezier curve, P(t). [3 marks] (iii) Calculate the coordinates of P( 1 2 ). How large is the error? [Hint: 2 1.414.] [3 marks] (b) Calculate revised control points for the Bezier curve so that it models the circular arc more accurately. [4 marks] (c) Describe in outline an alternative way of efficiently drawing the arc by calculating the pixels that lie on it directly.

(a) State what is meant by a directed graph and a strongly connected component.

Illustrate your description by giving an example of such a graph with 8 vertices

and 12 edges that has three strongly connected components. [5 marks]

(b) Describe, in detail, an algorithm to perform a depth-fifirst search over such a

graph. Your algorithm should attach the discovery and fifinishing times to each

vertex and leave a representation of the depth-fifirst spanning tree embedded

within the graph. [5 marks]

(c) Describe an O(n) algorithm to discover all the strongly connected components

of a given directed graph and explain why it is correct. You may fifind it useful

to use the concept of the forefather (v) of a vertex v which is the vertex, u,

with highest fifinishing time for which there exists a (possibly zero length) path

from v to u. [10 marks]

2 Computer Design

master station for the floor manager. Output from the system will be video and this will feed monitor displays in the studio and be included in the broadcast programme. (a) Sketch a block diagram of the overall system, showing clearly the various units and the signals which make up the cables which run between them. [5 marks] (b) Specify the controls and indicators on the front panel of the two types of station. Give a pair of state diagrams of the system, one as seen by the audience and the other as seen by the floor manager. [5 marks] (c) Given that a profitable return on the sale of three complete systems is required, describe the components and technology that should be used in the units. [okay (d) Discuss the advantages and disadvantages of including a PC inside the floor manager's station, in terms of cost, ease of use and whether a custom or standard operating system should be used.

SECTION A 1 Twenty-part question (One mark per part) (a) Consider the ML lists (fn x => [x,x])(ref 0) and map ref [0,0]. What do they have in common, and how do they differ? (b) What does it mean for a function to be tail-recursive? (c) How can an ML program form a cyclic list? (Your answer need not present any code.) (d) Find an integer solution x, y to 284x + 220y = 4. (e) Draw a Venn diagram for three sets, A, B and C, showing the symmetric difference A B C. (f ) Define a partial order on set A.and two of the most important methods that might be defined in an applet which just by being defined can alter its behaviour or appearance. (h) In Java if a is a variable of type int what values of a will result in (a & (a-1)) == 0 being true? (i) What is the range of real numbers which can be represented by a floating point format with 1 sign bit, 8 bias-127 exponent bits, and 23 normalised mantissa bits? You may round the mantissa value to the nearest integer. 1 (j) Unix operating systems give each process its own virtual address space, initially containing three segments. What is contained in each of these segments? (k) What is this? X p-channel p-channel Z n-channel Y n-channel (l) Give a sum of products form for the exclusive or of two variables a and b. (m) Give at least one good reason why professionals carry a greater ethical burden in the activities of their profession than ordinary members of the public. (n) Write down a short expression or command which is a syntactically correct piece of program, but which would normally be faulted by a type-checker. Justify your answer in a few words. (o) Given events A and B, demonstrate that P(AB) = P(A)+P(B)P(AB). (p) Given the axioms of Probability, prove the Empty Set Theorem: P() = 0. (q) An inertial navigation set has a mean time to failure of 1000 hours. If an aircraft is fitted with two of them to increase reliability, is the mean time to failure of both systems which is experienced in practice likely to be several thousand hours or about a million hours? Give a brief justification for your answer. (r ) Outline the key principles of loop design, considering the simple case of a while loop. (s) What are the differences, if any, between the languages determined by the three regular expressions , ( ) and ( ) ? (t) For the main memory of a computer, why is volatile technology more often used than non-volatile technology? 2 CST.99.2.3 SECTION B 2 Digital Electronics An arbiter is a functional unit that allows requesters to lock resources while they are in use. (a) Describe the inputs and outputs of an arbiter for a single resource which has two requesters. [5 marks] (b) Describe two policies that the arbiter might implement when both requesters request the resource simultaneously. One of these should require some internal state. [5 marks] (c) Give a state diagram for a policy which requires internal state assuming synchronous operation. [5 marks] (d) Choose one of the policies in (b) and derive equations for outputs and next state control using any type of storage element you choose. [5 marks] 3 [TURN OVER CST.99.2.4 3 Digital Electronics In an edge triggered flip flop, explain what is meant by (a) hold time (b) setup time (c) delay from clock edge to output [3 marks] What relation should hold between two of these quantities to provide sensible behaviour and why? [5 marks] Comment on the possibility and desirability of negative hold times. [2 marks] Each of the following boolean functions is a function of the four variables w, x, y, z. The functions are not totally specified and may take on any value for certain inputs. fn indicates where the function must be true, while gn is true where the value of the function is not constrained. Draw maps and provide a minimum sum of products form for each of the functions. (a) f1 = wxyz + wxyz + wxyz + wxyz + wxyz + wxyz g1 = wxy z + wxyz (b) f2 = wxyz + wxyz + wxyz + wxyz + wxyz + wxyz + wxyz + wxyz + wxyz g2 = wxy z + wxyz [5 marks] Let f(x0, x1, . . . , xn1) be equal to 1 if and only if exactly k of the variables have the value 1. How many prime implicants does this function have? [5 marks] 4 CST.99.2.5 SECTION C 4 Probability A B Each of the five switches in the above circuit is closed with probability p, independently of all the other switches. What is the probability of there being a connection from A to B? Express the answer as a polynomial in p. [7 marks] The circuit is then modified to the version shown below, the five switches still being independent. What is the probability of there being a connection from A to B now? Again express the answer as a polynomial in p. [13 marks] A B 5 Probability A solitaire game is played with two coins. One coin is fair, so that P(heads) = 1 2 , and the other is biased so that P(heads) = p. At the first turn the player tosses the fair coin. At all subsequent turns the biased coin is used if the toss at the previous turn resulted in heads and the fair coin is used if the toss at the previous turn resulted in tails. Suppose un is the probability of obtaining heads at turn n. Show that, for n > 1: 2un + (1 2p)un1 = 1 [4 marks] Demonstrate that this difference equation also holds for the case n = 1 provided u0 is suitably defined. [2 marks] Solve the difference equation, expressing un in terms of n and p. [14 marks] 5 [TURN OVER CST.99.2.6 SECTION D 6 Professional Practice and Ethics What is the nature of privacy and how do EU guidelines and/or British legislation serve to protect privacy? [20 marks] 7 Regular Languages and Finite Automata Suppose that L is a language over the alphabet {0, 1}. Let L 0 consist of all strings u 0 over {0, 1} with the property that there is some string u L with the same length as u 0 and differing from u 0 in at most one position in the string. Show that if L is regular, then so is L 0 . [Hint: if Q is the set of states of some finite automaton accepting L, construct a non-deterministic automaton accepting L 0 with states Q {0, 1}, where the second component counts how many differences have been seen so far.

This assignment gives you an opportunity to learn about files, arrays, and pointers. A cost involves a Description, and an amount and An Item Number.

Write a program that opens a file, reads records into a container of data structures, and prints out the sum in order. You can use Vectors to contain the data structures.

1. Create a data structure to represent the record ==> struct Cost in cost.h 2. Write a function called ==> parse_account, that parses one (string) record from a file, and populates a data structure with that data. 3. Write a function called sum_accounts, that when passed a container of structures, returns a double representing the sum of the amounts in those structures. 4. Create a main program a) Create an appropriate container of data structures b) Open the accounts file (costfile.txt) c) While you can read a line from the file without error Call parse_account, which returns a data structure. Add the returned data structure to the container (using, pushToV) d) Call sum_accounts to determine the amount of money represented e) Print a message and the result.

Try this with some sample data, such as the following lines in costfile.dat You may add or create your own data file to test the program with: You can start with the data in a text file and then write the data in a binary file, this way you practice with both file types.

Description Amount Item number Pass_Go 200.00 135 Reading_RR 50.00 136 Connecticut 120.00 137 Chance 25.00 138

I have the code that goes with this question just need a flowchart diagram?

(b) What sort of guarantee does circuit switching provide? [5 marks]

(c) What advantages does packet switching provide over circuit switching?

[5 marks]

(d) Which of frequency division multiplexing, time division multiplexing and code

division multiplexing lend themselves to circuit switching? Which to packet

switching? Explain why or why not in each case. [5 marks]

4 Computer Graphics and Image Processing

(a) Describe the z-buffffer polygon scan conversion algorithm. [10 marks]

(b) In ray tracing, once we have determined where a ray strikes an object, the

illumination at the intersection point can be calculated using the formula:

Explain what real effffect each of the three terms is trying to model and explain

what each of the following symbols means, within the context of this formula:

I, Ia, i, Ii , ka, kd, ks,Li, N, Ri, V, n

[10 marks]

3

[TURN OVERCST.2001.6.4

SECTION B

5 Comparative Programming Languages

(a) Brieflfly explain the concept of coroutines as used in BCPL and outline

the effffect of the library functions createco(f, size), deleteco(ctpr),

callco(cptr, val) and cowait(val). [10 marks]

(b) Outline how you would design a coroutine to merge, in increasing order, two

infifinite streams of increasing integers supplied by two other coroutines.

[5 marks]

(c) Brieflfly outline how you would implement an analogous merging mechanism in

an object-oriented language, such as Java, that does not provide a coroutine

mechanism. [5 marks]

6 Compiler Construction

(a) Describe one possible structure (e.g. ELF) of an object fifile. Illustrate your

answer by considering the form of object fifile which might result from the

following C program.

int a = 1, b = -1;

extern int g(int);

extern int c;

int f() { return g(a-b) + c; }

It is not necessary to consider the exact instruction sequence, just issues

concerning its interaction with the object fifile format. [10 marks]

(b) Describe how a linker takes a sequence of such programs and produces an

executable fifile. [4 marks]

(c) Compare and contrast static and dynamic linking in a system using your object

fifile format. [6 marks]

4CST.2001.6.5

7 Prolog for Artifificial Intelligence

A weighted binary tree can be defifined using compound terms in the following way.

A node of the tree is represented by the term n(V, L, R), where V stands for the

value of the node, and L and R stand for the left and right branches, respectively.

A terminal node has the R and L components instantiated to the null list.

Given an input tree T, write a Prolog program that constructs a tree of the same

shape as T, but in which the value of each node has been set to the value of the

maximum value node in T.

[Note: Maximum marks are available only for programs that perform this task in

one recursive descent of the input tree, and which use no more than four clauses.]

[20 marks]

5

[TURN OVERCST.2001.6.6

8 Databases

The environmental agency is setting up an SQL database to monitor long-term

trends in the climate. Data are collected from observatories of a number of difffferent

kinds.

Flood risk is of particular concern. Each water authority measures river levels and

rates of flflow hourly at major points, and records reservoir levels daily.

In addition, the agency maintains weather stations both inland and at sea. These

record precipitation (rainfall etc.), temperature, sunshine, air pressure and wind.

Values of new precipitation, temperature, pressure, and wind speed and direction

are taken hourly; gusts of over 60 m.p.h. are noted whenever they occur.

Maximum and minimum temperature and pressure, the total number of hours of

sunshine and the total precipitation are recorded daily. Inland stations can be

grouped by water authority.

By default these primary data will be relegated to archive after 2 years. Selected

information is retained permanently in a data warehouse. This serves two purposes.

First, it holds monthly summary data consisting of the maximum (and minimum

as appropriate) day value for each statistic, together with the monthly totals of

sunshine and precipitation. The warehouse also keeps detailed information relating

to periods of extreme weather from the relevant observatories, with one or more

keywords describing the nature of the incident (flflood, blizzard, hurricane etc.) and

an optional comment.

Write notes to assist in the design of the schema for the relational data warehouse,

including any diagrams that you fifind helpful. Explain how your design will enable

meteorologists to fifind relevant past records, noting any assumptions that you make

about the nature of the data.

[You should not go into unnecessary detail about the structure of the primary

database. You may assume that expert meteorologists will select the data for the

warehouse.]

[20 marks]

6CST.2001.6.7

SECTION C

9 Semantics of Programming Languages

Write short notes on four of the following fifive topics.

(a) The relationship between three forms of operational semantics of the Language

of Commands (LC) given by

an evaluation relation h P, si hV, s0 i

a transition relation h P, si hP0 , s0 i

a transition relation between the confifigurations

h c, r, si of the

SMC-machine

(b) The notion of semantic equivalence of LC phrases and its congruence property.

(c) Call-by-name and call-by-value rules for 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]

kindly answer all the questions