1. Introduction to Computer Architecture concepts; The MIPS R2000 architecture allows for up to four external coprocessors. Our local systems arIPS external coprocessors are used by describing, in architectural terms, what happens when the instructions below are executed. Details specific to floating point are not required. lwc1 $f4, fdata # $f4 is a floating point register # fdata labels a data area mtc1 $f6, $16 # $16 is a general purpose register? mul.s $f4, $f4, $f2 mfc1 $f4, $17 add.s $f4, $f4, $f6 swc1 $f4, fdata+4 [12 marks] Give an example of an exception which is detected by the R2000 but concerns the R2010. [2 marks] Give an example of an exception which is detected by the R2010. [2 marks] What provision has been made for these exceptions to be signalled between the main processor and coprocessor? [4 marks] 1 [TURN OVER CST.94.6.2 2 Computer Structures Write short notes explaining the following: (a) hard-wired control of a CPU [6 marks] (b) asynchronous operation of a bus [7 marks] (c) delayed branching in a pipelined RISC processor [7 marks] 3 Digital Communication I Define the term flow control. [5 marks] How does it differ from congestion control? [3 marks] What is meant by the terms entry level, hop by hop and end to end flow control? When is each appropriate? [8 marks] Sketch the design of a simple flow control protocol. [4 marks] 4 Graphics Discuss transformations applied to 3D wireframe objects. [12 marks] Discuss the use of homogeneous coordinate representations (a) for presenting concepts [4 marks] (b) within programs [4 marks] 2 CST.94.6.3 SECTION B 5 Programming in C Write a program in C which can solve cryptarithmetic puzzles in the format of the sum of two words. For example, given the input SEND +MORE MONEY? the program would output 9567 +1085 10652 N.B. Each letter represents a different digit. [20 marks] 6 Programming Language Compilation Discuss two possible strategies that you might use to translate the abstract syntax tree corresponding to an integer expression composed of simple variables, integer constants and the usual integer operators +, , and / into reasonable quality code for a machine with eight general-purpose registers. You should pay particular attention to how you would control the allocation of registers and anonymous store locations, and you should outline what optimisations are convenient to perform. [20 marks] 3 [TURN OVER CST.94.6.4 7 Concurrent Systems A transaction processing system for a banking application is to be implemented using object semantics. Bank account objects include the following among their operations: credit (account id, amount) debit (account id, amount) add interest (account id) By defining "transactions" based on this example, show what is meant by (a) a non-serialisable execution schedule [3 marks] (b) a non-strict execution schedule leading to a cascading abort [3 marks] Explain the ACID properties of transactions, drawing on the above application for examples. Indicate which properties are concerned with failure resilience and which with concurrency control. [8 marks] Again using the above application for examples, explain concurrency control based on (a) two-phase locking [3 marks] (b) time-stamp ordering [3 marks] 4? CST.94.6.5 8 Databases Describe how a data model is represented in a relational database, and explain how one might specify a relational database schema. [5 marks] What is meant by a referential integrity constraint in a relational database? [3 marks] Each year the number of tourists coming to Cambridge increases by 10%. Most of the pressure falls on a limited number of identified sites in the city centre. The Tourist Board has restricted the size of any group visiting such a site to 20, and requires a group of ten people or more to get a permit in advance. Most bookings are made either by tour operators or directly by independent guides: the Tourist Board will arrange guides for groups if asked to do so. A database is being installed to coordinate bookings and to provide information about the opening times of sites. Each site has separate opening times for summer and winter (owing to college autonomy, changes of season differ from site to site). Permits are issued to start on the hour or on the half-hour: they are valid either for 1 hour or for 2 hours, the duration being fixed for each site. The final permits of each day are timed to expire at the site's closing time. Each site has a fixed capacity, and no booking can be accepted that would cause it to be exceeded. The charge for a permit depends only on the site and the season. (Occasionally sites are closed for several hours during the normal opening period, for example when recording is taking place in King's College Chapel. The protocol is to inform the Tourist Board at least 6 months in advance.) The Tourist Board issues permits to visit an identified site at a given time on a given day, specifying the booking agent and the number in the group. Bookings can be made up to 6 months beforehand. Permits are issued to registered tour operators and guides on account, but in all other cases payment must be made in advance. The data held for registered guides includes not only account details but also their working hours and charges. Design a schema for the relational database that is to record this information for the Tourist Board. You may find it helpful to use domain types DATE, TIME and MONEY in addition to standard programming language datatypes. You do not need to specify the transactions that maintain the database, but you should state clearly any assumptions that influence the schema design. [12 marks] 5 [TURN OVER CST.94.6.6 SECTION C 9 Foundations of Logic Programming Describe in detail an algorithm for finding the most general unifier of two terms. Illustrate your answer by unifying the following pairs of terms: f(x, a, x) with f(a, y, b) f(x, y, z) with f(g(y), z, a) f(g(y), y, z) with f(x, z, x) The variables above are x, y and z. [8 marks] "The resolution method relies on most general unifiers because they are unique." Discuss. [3 marks] The resolution method can be applied directly to any first-order formula, regardless of its structure. Discuss and evaluate the following proposals for dealing with special cases: (a) If the formula has the form A, then apply the resolution method to A. Failure to prove A establishes that A is a theorem. (b) If the formula has the form of a disjunction A B, then apply the resolution method separately to A and to B. If either proof succeeds then A B is a theorem. (c) If the formula has the form of a conjunction A B, then apply the resolution method separately to A and to B. If both proofs succeed then A B is a theorem. (d) If the formula has the form A B, convert A to clauses. Then apply the resolution method to B, allowing A's clauses to take part in applications of the resolution rule. If this proof succeeds then A B is a theorem. [9 marks] 6 CST.94.6.7 10 Foundations of Functional Programming Describe the operation of a graph reducer and its treatment of the combinators K, S, Y, if (for conditional expressions) and mult (integer multiplication). [6 marks] Describe the operation of the SECD machine, including its treatment of recursive functions. [5 marks] Exhibit an infinite family n of distinct fixed-point combinators. Justify your answer by showing that n F(n F) for all non-negative integers n and -terms F. You must also show that m 6= n for m 6= n, quoting standard results about the -calculus if necessary. [9 marks] 11 Computation Theory Explain Turing's Thesis. [5 marks] (a) What is meant by saying that a Turing machine has searching states? Show that any Turing machine computation can be effected by a machine with searching states, equivalent in the sense that the head movements are identical and the same symbols are written to the tape. [5 marks] (b) Show that, subject to suitable encoding, any computation can be carried out by a Turing machine having only two states. [10 marks] 12 Software Engineering Compare and contrast the relative merits of Z and VDM as tools for specifying and developing large software systems.

1 Foundations of Programming (a) Briefly describe ASCII and Unicode and draw attention to any relationship between them. [3 marks] (b) Briefly explain what a Reader is in the context of reading characters from data. [3 marks] A novice programmer has written the following copying program which is intended simply to read characters from data one at a time and to write them out. public class Copying { public static void main(String[] args) { int ch; while ((ch = System.in.read()) != -1) { System .out print("%c", (char) ch); } } } (c) Unfortunately this program causes a compile-time error. Explain what the problem is and modify the code so that the program compiles. [3 marks] (d) The amended program correctly copies data in simple cases but is found to fail when exotic characters are encountered. Why is this? [3 marks] (e) By exploiting a Reader, rewrite the program so that exotic characters no longer cause any problems. [8 marks] 2 CST.2008.10.3 2 Foundations of Programming (a) Outline the use of enum in Java programs and explain any similarities to and any differences from a Java class. [6 marks] The following fragment of code shows an early attempt to write and test a Java program to simulate the paper-scissors-stone game. In the method main() each of the identifiers a and b is assigned one of the items, paper, scissors or stone and the printf() method then says whether the first beats, draws with or loses against the second. [The rule is that paper beats stone, scissors beat paper and stone beats scissors.] public class Game { public static void main(String[] args) { Item a = allocateItem(); Item b = allocateItem(); int res = a.versus(b); System.out.printf("%s %s %s%n", a, res>0 ? "beats" : res==0 ? "draws with" : "loses against", b); } private static Item allocateItem() { ... } } enum Item { PAPER... The three possibilities PAPER, SCISSORS and STONE are declared in enum Item along with a constructor, the method versus() and any necessary additional data fields. (b) Using the method Math.random() or otherwise, provide a body for the method allocateItem() such that the method returns an Item PAPER, SCISSORS or STONE equiprobably. [6 marks] (c) Complete the enum Item so that the statements in the method main() operate as intended. [8 marks] 3 (TURN OVER) CST.2008.10.4 3 Floating-Point Computation (a) Write a function in a programming language of your choice that takes a (32-bit IEEE format) float and returns a float with the property that: given zero, infinity or a positive normalised floating-point number then its result is the smallest normalised floating-point number (or infinity if this is not possible) greater than its argument. You may assume functions f2irep and irep2f which map between a float and the same bit pattern held in a 32-bit integer. [6 marks] (b) Briefly explain how this routine can be extended also to deal with negative floating-point values, remembering that the result should always be greater than the argument. [2 marks] (c) Define the notions of rounding error and truncation error of a floating-point computation involving a parameter h that mathematically should tend to zero. [2 marks] (d) Given a function f implementing a differentiable function that takes a floatingpoint argument and gives a floating-point result, a programmer implements a function f 0 (x) f(x + h) f(x h) 2h to compute its derivative. Using a Taylor expansion or otherwise, estimate how rounding and truncation errors depend on h. You may assume that all mathematical derivatives of f are within an order of magnitude of 1.0. [8 marks] (e) Suggest a good value for h given a double-precision floating-point format that represents approximately 15 significant decimal figures. [2 marks] 4 CST.2008.10.5 4 Programming in C and C++ A hardware engineer stores a FIFO queue of bits in an int on a platform with 32-bit ints and 8-bit chars using the following C++ class: class BitQueue { int valid_bits; //the number of valid bits held in queue int queue; //least significant bit is most recent bit added public: BitQueue(): valid_bits(0),queue(0) {} void push(int val, int bsize); int pop(int bsize); int size(); }; (a) Write an implementation of Bit Queue::size, which should return the number of bits currently held in queue. [1 mark] (b) Write an implementation of BitQueue::push, which places the bsize least significant bits from val onto queue and updates valid bits. An exception should be thrown in cases where data would otherwise be lost. [5 marks] (c) Write an implementation of BitQueue::pop, which takes bsize bits from queue, provides them as the bsize least significant bits in the return value, and updates valid bits. An exception should be thrown when any requested data is unavailable. [4 marks] (d) The hardware engineer has built a communication device together with a C++ library function send to transmit data with the following declaration: void send(char); Use the BitQueue class to write a C++ definition for: void sendmsg(const char* msg); Each of the characters in msg should be encoded, in index order, using the following binary codes: 'a'=0, 'b'=10, 'c'=1100, and 'd'=1101. All other characters should be ignored. Successive binary codes should be bit-packed together and the code 111 should be used to denote the end of the message. Chunks of 8-bits should be sent using the send function and any remaining bits at the end of a message should be padded with zeros. For example, executing sendmsg("abcd") should call the send function twice, with the binary values 01011001 followed by 10111100. [10 marks] 5 (TURN OVER) CST.2008.10.6 5 Computer programming (b) Some liquid crystal displays divide a pixel into four sub-pixels coloured red, green, blue, and white. Explain why this might be useful, what advantages it has, and what limitations it has. [6 marks] (c) Compare and contrast half-toning and error diffusion. Include in your answer an explanation of the situations in which each is superior to the other. [6 marks] (d) One method of anti-aliasing is to sample at high resolution, n n higher than the final image, and then to average each block of n n pixels to give a single pixel value. Discuss the advantages and disadvantages of using (i) Gaussian blurring, and (ii) median filtering in place of simple averaging. [4 marks] 6 CST.2008.10.7 6 Introduction to Functional Programming (a) Write an SML function propercuts: ( list) ( list * list) list that given a list ` outputs the list of all pairs of non-empty lists (`1, `2) such that `1@`2 = `. [5 marks] (b) Consider the following datatypes datatype tree = leaf of | node of tree * tree ; datatype symbol = Lbracket | Rbracket | token of ; and the SML function rep: tree ( symbol) list that represents a binary tree as a list of symbols, according to the following definition: fun rep ( leaf x ) = [ token x ] | rep ( node(l,r) ) = [ Lbracket ] @ (rep l) @ (rep r) @ [ Rbracket ] ; Write an SML function istree: ( symbol) list bool that given a list of symbols ` outputs true if there exists a (necessarily unique) tree t such that rep(t) = `, and outputs false otherwise. [10 marks] (c) Define the SML functions infix @ ; @: list * list list ; map: ( ) list list ; and rigorously argue for the correctness of the following identity: map f (`1 @ `2) = (map f `1) @ (map f `2) : list for all f : and `1, `2 : list. [5 marks] 7 (TURN OVER) CST.2008.10.8 7 Artificial Intelligence I (a) Give a general description of the operation of the Recursive Best-First Search (RBFS) algorithm. [6 marks] (b) Consider the following search tree. The numbers by the nodes denote the sum of some path cost and heuristic. The boxed nodes are goals. Describe in detail the way in which the RBFS algorithm searches this tree. Your answer should indicate the order in which nodes are expanded, the reason that this order is used, and should state which of the three goals is found and why. Note that smaller numbers represent more desirable nodes. [12 marks] (c) What shortcoming of the A? algorithm does the RBFS algorithm address, and how does it achieve this? [2 marks] 8 CST.2008.10.9 8 Introduction to Security (a) A source of secure, unpredictable random numbers is needed to choose cryptographic keys and nonces. (i) Name six sources of entropy that can be found in typical desktopcomputer hardware to seed secure random-number generators. [4 marks] (ii) What sources of entropy can a smartcard chip, like the one in your University Card, access for this purpose? [4 marks] (b) As Her Majesty's prime hacker "001", on a mission deep inside an enemy installation, you have gained brief temporary access to a secret chip, which contains a hardware implementation of the DES encryption algorithm, along with a single secret key. You connect the chip to your bullet-proof laptop and quickly manage to encrypt a few thousand 64-bit plaintext blocks of your choice, and record the resulting 64-bit ciphertext blocks. You are unable to directly read out the DES key K used in the chip to perform these encryptions and you will not be able to leave the site without knowing K. But you know that all S-boxes in the last DES round are supplied in this chip via a separate power-supply pin. When you create a short-circuit on that pin, the encryption progresses as normal, except that the output of all S-boxes in the last round changes to zero. (i) Explain briefly the role of an S-box and the structure of a single round in DES. [4 marks] (ii) How can you find K, considering that your available time and computing power will not permit you to search through more than 109 possible keys? [8 marks] 9 (TURN OVER) CST.2008.10.10 9 Data Structures and Algorithms (a) Take an initially empty hash table with five slots, with hash function h(x) = x mod 5, and with collisions resolved by chaining. Draw a sketch of what happens when inserting the following sequence of keys into it: 35, 2, 18, 6, 3, 10, 8, 5. [You are not requested to draw the intermediate stages as separate figures, nor to show all the fields of each entry in detail.] [3 marks] (b) Repeat part (a) but with the following three changes: the hash table now has ten slots, the hash function is h(x) = x mod 10, and collisions are resolved by linear probing. [3 marks] (c) Imagine a hash table implementation where collisions are resolved by chaining but all the data stays within the slots of the original table. All entries not containing key-value pairs are marked with a Boolean flag and linked together into a free list. (i) Give clear explanations on how to implement the set(key, value) method in expected constant time, highlighting notable points and using high-level pseudocode where appropriate. Make use of doubly-linked lists if necessary. [8 marks] (ii) Assume the hash table has 5 slots, is initially empty and uses the hash function h(x) = x mod 5. Draw five diagrams of the hash table representing the initially empty state and then the table after the insertion of each of the following key-value pairs: (2, A), (2, C), (12, T), (5, Z). In the final diagram, draw all the fields and pointers of all the entries. [6 marks] 10 CST.2008.10.11 10 Operating System Foundations (a) Assume a 32-bit architecture with hardware support for paging, in the form of a translation lookaside buffer (TLB), but no hardware support for segmentation. Assume that the TLB is shared rather than flushed on process switching and that the operating system designers are supporting "soft" segments. (i) In addition to page number and page base, what fields would you expect to find in each TLB register? How would each of these be used? [4 marks] (ii) What fields would you expect to find in a process page table? How would each of these fields be used? [6 marks] (b) (i) Outline the function of a timing device. [2 marks] (ii) Why are timers essential in multiprogramming operating systems? [2 marks] (iii) Explain the operation of a multi-level feedback queue in process scheduling.

1 Introduction to Computer Architecture The MIPS R2000 architecture allows for up to four external coprocessors. Our local systems are configured with one: the R2010 Floating Point Accelerator (FPA). Explain how the MIPS external coprocessors are used by describing, in architectural terms, what happens when the instructions below are executed. Details specific to floating point are not required. lwc1 $f4, fdata # $f4 is a floating point register # fdata labels a data area mtc1 $f6, $16 # $16 is a general purpose register mul.s $f4, $f4, $f2 mfc1 $f4, $17 add.s $f4, $f4, $f6 swc1 $f4, fdata+4 [12 marks] Give an example of an exception which is detected by the R2000 but concerns the R2010. [2 marks] Give an example of an exception which is detected by the R2010. [2 marks] What provision has been made for these exceptions to be signalled between the main processor and coprocessor? [4 marks] 1 [TURN OVER CST.94.6.2 2 Computer Structures Write short notes explaining the following: (a) hard-wired control of a CPU [6 marks] (b) asynchronous operation of a bus [7 marks] (c) delayed branching in a pipelined RISC processor [7 marks] 3 Digital Communication I Define the term flow control. [5 marks] How does it differ from congestion control? [3 marks] What is meant by the terms entry level, hop by hop and end to end flow control? When is each appropriate? [8 marks] Sketch the design of a simple flow control protocol. [4 marks] 4 Graphics Discuss transformations applied to 3D wireframe objects. [12 marks] Discuss the use of homogeneous coordinate representations (a) for presenting concepts [4 marks] (b) within programs [4 marks] 2 CST.94.6.3 SECTION B 5 Programming in C Write a program in C which can solve cryptarithmetic puzzles in the format of the sum of two words. For example, given the input SEND +MORE MONEY the program would output 9567 +1085 10652 N.B. Each letter represents a different digit. [20 marks] 6 Programming Language Compilation Discuss two possible strategies that you might use to translate the abstract syntax tree corresponding to an integer expression composed of simple variables, integer constants and the usual integer operators +, , and / into reasonable quality code for a machine with eight general-purpose registers. You should pay particular attention to how you would control the allocation of registers and anonymous store locations, and you should outline what optimisations are convenient to perform. [20 marks] 3 [TURN OVER CST.94.6.4 7 Concurrent Systems A transaction processing system for a banking application is to be implemented using object semantics. Bank account objects include the following among their operations: credit (account id, amount) debit (account id, amount) add interest (account id) By defining "transactions" based on this example, show what is meant by (a) a non-serialisable execution schedule [3 marks] (b) a non-strict execution schedule leading to a cascading abort [3 marks] Explain the ACID properties of transactions, drawing on the above application for examples. Indicate which properties are concerned with failure resilience and which with concurrency control. [8 marks] Again using the above application for examples, explain concurrency control based on (a) two-phase locking [3 marks] (b) time-stamp ordering [3 marks] 4 CST.94.6.5 8 Databases Describe how a data model is represented in a relational database, and explain how one might specify a relational database schema. [5 marks] What is meant by a referential integrity constraint in a relational database? [3 marks] Each year the number of tourists coming to Cambridge increases by 10%. Most of the pressure falls on a limited number of identified sites in the city centre. The Tourist Board has restricted the size of any group visiting such a site to 20, and requires a group of ten people or more to get a permit in advance. Most bookings are made either by tour operators or directly by independent guides: the Tourist Board will arrange guides for groups if asked to do so. A database is being installed to coordinate bookings and to provide information about the opening times of sites. Each site has separate opening times for summer and winter (owing to college autonomy, changes of season differ from site to site). Permits are issued to start on the hour or on the half-hour: they are valid either for 1 hour or for 2 hours, the duration being fixed for each site. The final permits of each day are timed to expire at the site's closing time. Each site has a fixed capacity, and no booking can be accepted that would cause it to be exceeded. The charge for a permit depends only on the site and the season. (Occasionally sites are closed for several hours during the normal opening period, for example when recording is taking place in King's College Chapel. The protocol is to inform the Tourist Board at least 6 months in advance.) The Tourist Board issues permits to visit an identified site at a given time on a given day, specifying the booking agent and the number in the group. Bookings can be made up to 6 months beforehand. Permits are issued to registered tour operators and guides on account, but in all other cases payment must be made in advance. The data held for registered guides includes not only account details but also their working hours and charges. Design a schema for the relational database that is to record this information for the Tourist Board. You may find it helpful to use domain types DATE, TIME and MONEY in addition to standard programming language datatypes. You do not need to specify the transactions that maintain the database, but you should state clearly any assumptions that influence the schema design. [12 marks] 5 [TURN OVER CST.94.6.6 SECTION C 9 Foundations of Logic Programming Describe in detail an algorithm for finding the most general unifier of two terms. Illustrate your answer by unifying the following pairs of terms: f(x, a, x) with f(a, y, b) f(x, y, z) with f(g(y), z, a) f(g(y), y, z) with f(x, z, x) The variables above are x, y and z. [8 marks] "The resolution method relies on most general unifiers because they are unique." Discuss. [3 marks] The resolution method can be applied directly to any first-order formula, regardless of its structure. Discuss and evaluate the following proposals for dealing with special cases: (a) If the formula has the form A, then apply the resolution method to A. Failure to prove A establishes that A is a theorem. (b) If the formula has the form of a disjunction A B, then apply the resolution method separately to A and to B. If either proof succeeds then A B is a theorem. (c) If the formula has the form of a conjunction A B, then apply the resolution method separately to A and to B. If both proofs succeed then A B is a theorem. (d) If the formula has the form A B, convert A to clauses. Then apply the resolution method to B, allowing A's clauses to take part in applications of the resolution rule. If this proof succeeds then A B is a theorem. [9 marks] 6 CST.94.6.7 10 Foundations of Functional Programming Describe the operation of a graph reducer and its treatment of the combinators K, S, Y, if (for conditional expressions) and mult (integer multiplication). [6 marks] Describe the operation of the SECD machine, including its treatment of recursive functions. [5 marks] Exhibit an infinite family n of distinct fixed-point combinators. Justify your answer by showing that n F(n F) for all non-negative integers n and -terms F. You must also show that m 6= n for m 6= n, quoting standard results about the -calculus if necessary. [9 marks] 11 Computation Theory Explain Turing's Thesis. [5 marks] (a) What is meant by saying that a Turing machine has searching states? Show that any Turing machine computation can be effected by a machine with searching states, equivalent in the sense that the head movements are identical and the same symbols are written to the tape. [5 marks] (b) Show that, subject to suitable encoding, any computation can be carried out by a Turing machine having only two states. [10 marks] 12 Software Engineering Compare and contrast the relative merits of Z and VDM as tools for specifying and