do the following,.....

Write program that reads a person's first and last names, separated by a space. Then the program outputs last name, comma, first name. Create program that takes in user input and stores the input into an array. Also within the program show how you can: show the elements in the array, remove an element from the array, add an element to the array. Write program that reads a list of integers ending with a negative, and that then outputs that list in reverse. After the negative that ends the list, a character indicates what character should separate the output integers

(a) A (phrase-structured) grammar is often defined to be a 4-tuple (N, T, R, S) where R is a set of production rules. Explain what the other components of the 4-tuple are. Explain also the (most general form of) production rules, how these are conventionally restricted and why one might wish to restrict them. [6 marks] (b) Give a grammar which is ambiguous. [2 marks] (c) Give a grammar which is not a regular grammar but which generates a regular language containing an infinite number of strings. [2 marks] (d) Is it possible to wr ite a grammar which generates the strings {aa, aaa, aaaaa, . . . , ap , . . .} where p is prime? (A general argument for or against suffices.) [2 marks] (e) It is desired to construct a simple "pocket-calculator" program using yacc and lex (or other similar automated tools of your choice) which can parse strings such as "1+(10-5-3)*5+2=" and print the result, 13 in this case. Outline the overall structure of your program components. Give full details of the input to yacc and lex (or equivalent). (Precise syntactic details are not important, but your answer should show an understanding of the principles involved.)

(a) Calculate the maximum resolution needed by a movie projector in a movie theatre. Clearly state any assumptions that you make. [6 marks] (b) Describe, in detail, an error diffusion algorithm for converting greyscale images to bi-level black and white images at the same resolution. [8 marks] (c) Explain how this could be extended to provide an algorithm to print full colour RGB images on a CMYK laser printer, assuming that one pixel in the image maps to one pixel on the printer. [6 marks] 11 Introduction to Security (a) A and B play a simple game. A chooses a number RA Z3 and B chooses a number RB Z3. Then A and B communicate their respective choice to each other simultaneously, meaning that the players cannot change their choice after having seen that of the opponent. These rules decide who wins the game: RA RB + 1 (mod 3) A wins RB RA + 1 (mod 3) B wins In any other case, the result of the game is a draw. (i) What complication arises when this game is played at a distance, for example via e-mail? [2 marks] (ii) Suggest a cryptographic protocol that prevents cheating when this game is played via e-mail. Your solution should not rely on a trusted third party. [6 marks] (iii) What assumptions do you make about the cryptographic functions used in your solution of part (ii)? [3 marks] (iv) What assumptions do you make about the amount of computing power available to the opponent in your solution of part (ii)? [3 marks] (b) Outline briefly the purpose of an organisation's security policy and what steps should be considered in its development.

(a) Explain informally, i.e. without reference to any particular model of computation, why the Halting Problem is undecidable. [6 marks] (b) Briefly describe two mathematical problems, other than the Halting Problem, that are algorithmically undecidable. [4 marks] (c) What does it mean for a partial function to be register machine computable? Show how the informal argument in part (a) can be turned into a rigorous proof that there is no register machine deciding the Halting Problem for register machine computable functions.

(a) A device driver process carries out character I/O via a Universal Asynchronous Receiver/Transmitter (UART). (i) Why is hardware-software synchronisation needed? [1 mark] (ii) Describe polled operation. [2 marks] (iii) Describe interrupt-driven operation. [2 marks] (iv) Draw a state transition diagram for the device-driver process. Indicate the events that cause each transition and in each case explain the effect on the device driver's process descriptor and the operating system's scheduling queues. Assume interrupt-driven software. [7 marks] (b) The device driver process fills/empties a buffer of fixed size in an I/O buffer area. A process carrying out application requests reads and writes data in variable-sized amounts from the buffer. (i) Why must mutually exclusive access to the buffer be enforced? [2 marks] (ii) Why is condition synchronisation needed? [2 marks] (iii) What is wrong with the following pseudocode fragment from the devicedriver's specification, where: buffer-lock is a semaphore initialised to 1, space is a semaphore initialised to the buffer size in bytes, data is a semaphore initialised to 0? on input: on output: WAIT(buffer-lock); WAIT(buffer-lock); if buffer is full then WAIT(space); if buffer is empty then WAIT(data); wr ite a character into the buffer; read a character from the buffer; SIGNAL(buffer-lock); SIGNAL(buffer-lock);

Imagine that you are the user interface designer responsible for a system that manages the shutdown of a nuclear power station. (a) Comment on hazards, risks and reliability. (b) What special procedures should be followed during design? (c) There is some debate among the team about whether the operator should be in the control loop. What options are there? (d) In order to assess alternative options like those in part (c): (i) How could you estimate the speed of operator action based on a draft interface layout?

qplus an initialisation method. Calling send would append the argument to a (fixed-length) FIFO queue of data which would be collected by the thread calling receive. The thread would block if receive were called when the queue was empty or if send were called when the buffer was full. W rite an interface, Message, defining a suitable opaque object type with init and send methods, and writ e a further interface MessageInternal revealing the receive method. [8 marks] W rite an implementation exporting to both of these interfaces supplying the concrete revelations of the types and providing appropriate default methods. [12 marks] 3 [TURN OVER CST.97.3.4 4 Compiler Construction Consider the following grammar for expressions () and commands (). ::= i | n | - | ** | ( ) ::= i := | if then | if then else | repeatwhile | ; | { } Show that there are syntactic ambiguities between (a) the minus (-) and exponentiation (**) operators, (b) the if-command and the if-then-elsecommand, and (c) the if-then-else-command and the repeatwhile-command. [4 marks] Define, in a programming language notation of your choice, a recursive descent parser that will construct the abstract syntax tree for an input stream conforming to the above syntax for commands. You may assume the existence of a function lex() that will yield an integer representing the next lexical token from the input stream, and the functions mk2(op,x), mk3(op,x,y) and mk4(op,x,y,z) that will ssume that exponentiation is right associative and more binding than subtraction which is left associative. The command following then should be the longest possible and the command before repeatwhile should be the shortest possible. [12 marks] Briefly outline how you would modify your parser if the command to the left of repeatwhile was changed to be the longest (rather than the shortest). [4 marks] 5 Data Structures and Algorithms You are given two sets of numbers Xi and Yj , where i and j run from 1 to N. Devise an algorithm to find the M largest values of Xi Yj . This algorithm should not be quadratic in N, though it is permitted to be quadratic in M. You should regard N as being of the order of 20,000 and M as being of the order of 1,000. [20 marks] 4 CST.97.3.5 6 Data Structures and Algorithms Describe and justify Kruskal's algorithm for finding the minimum spanning tree of an undirected graph. [6 marks] Suppose that all edges longer than some given L were omitted from the graph, for example as a result of not calculating them at all. Would the algorithm still give the correct result? Would you be able to tell if it had not? If it yielded a tree would it be guaranteed to be the best one? Justify your answers and consider the problem of finding a minimum spanning tree for 1,000,000 points in a plane rectangle where there is an edge between every pair of points and the cost of the edge is the Euclidean distance between the two points. [14 marks] 7 Structured Hardware Design A smart card is the size and shape of a credit card, but contains a microprocessor, a RAM, a ROM and some amount of non-volatile storage. The only connections to the card are five gold-plated contacts for power, ground, clock, data and reset. Wri te a few sentences about each of the following: (a) Design partition: i.e. how should the circuitry of the card be structured? [5 marks] (b) Testing: i.e. how will the component(s) of the card and the completed card be tested before shipping? [5 marks] (c) Product customisation: i.e. how will the card be different in different application markets (banking, authentication, casino, cellular phone etc.)? [5 marks] (d) Uniqueness: i.e. how would the card be customised or differentiated on a percard basis for individual users?

Explain briefly how the OCaml compiler can statically check if you have handled all the input possibilities for the input parameters to describe and identify. [4 marks] (c) Define a type stree that only distinguishes between three species oak, birch or maple and no others. Implement functions for the following signatures with similar functionality to the earlier identify function: val identify exn : string -> stree val identify opt : string -> stree option Briefly discuss the tradeoffs between your two approaches. [5 marks] (d) You now need to implement a simple simulator before starting real surveys. Trees will occur in the following fixed infinite sequence: oak, birch, oak, maple, maple, and then repeat from the beginning. (i) Define a function val spotter : unit -> stree that will return the sequence of trees when called multiple times. [5 marks] (ii) Define a purely functional alternative spotter that calculates the next stree in sequence, using only the input arguments to the function to calculate the return value. Write down an example application of this function with the input arguments and the expected output result.(Hint: you may need to pass in the complete sequence as one of the arguments.) [5 marks] 2 CST0.2020.1.3 2 Foundations of Computer Science In this exercise, we will develop a game engine to play a simplified version of the game of Mastermind. In simplified Mastermind, player A selects a list of n colours among 3 possible colours: Red, Green and Blue (e.g., [Red; Red; Green; Blue] if n = 4). Player B has to guess player A's list of colours by proposing lists of colours in sequence until she finds the list proposed by player A. Every time player B proposes a list of colours, she gets feedback in the form of a number x. (x is the number of colours that are in the correct position). For example, if player A's list is [Red; Red; Green; Blue] and player B guessed [Red; Green; Green; Red], then x = 2 (the first Red and second Green are at the right positions). Note that x n. (a) Define a type colour to represent a colour. [2 marks] (b) Given two colour lists, wr ite a function feedback that returns x. The first argument a is the list of player A, and the second argument b is a list of player B. Raise a SizeMismatch exception if the lengths of both lists do not match. You may need to introduce a helper function. [4 marks] (c) Using currying, define a test function that takes a list proposed by player B and returns x. This function should assume that player A's list is [Blue; Green; Red]. [2 marks] (d) What is the type of test in Part (c)? [2 marks] (e) W rite a function generate lists that generates all possible colour lists of a given length n. The function takes a single argument n. You may use the concatenation operation @ and List.map function. Tip: generate 2 should output 32 = 9 lists. [6 marks] (f ) Given a colour list of player B and a feedback x, wri te a function valid lists that takes two arguments b and x and returns all possible lists that player A could have chosen (such that they match the feedback given to player B). You may use generate lists, feedback, List.length and/or List.filter. [4 marks] 3 (TURN OVER) CST0.2020.1.4 SECTION B 3 Object-Oriented Programming You have been asked to implement a user-interface component ButtonCanvas which is both a button that can be clicked by the user and a canvas which the user can draw on. Your existing code contains a Button class and a Canvas class. Both of these extend GuiComponent. (a) ButtonCanvas could be built using multiple inheritance. What does this mean in this context? [2 marks] (b) Give two reasons why this might be desirable. [2 marks] (c) Give two complexities that arise in this case. [2 marks] (d) Java interfaces originally contained only abstract methods and static final fields. How did this restriction avoid the complexities of extending multiple classes? [3 marks] (e) Draw a UML diagram for building ButtonCanvas using abstract interfaces rather than multiple inheritance. Explain how your design attempts to preserve the desirable properties arising from multiple inheritance. You do not need to recall the exact UML specification, instead you may provide a key explaining your notation. [9 marks] (f ) Recent versions of Java added default methods to interfaces. What is the impact of this with respect to multiple inheritance? [2 marks] 4 CST0.2020.1.5 4 Object-Oriented Programming (a) Describe the differences between primitive types and objects in Java. Consider: (i) the values they contain [1 mark] (ii) where they are stored in memory [1 mark] (iii) how they interact with Java references [1 mark] (b) What are auto-boxing and auto-unboxing? Give an example of how they might cause an exception to be thrown. [4 marks] (c) Consider the following code in which any arbitrary Java type (primitive or object) could be substituted for T. void f(T t) { /* ... */ } T t1 = /* ... */ f(t1); For which substitutions of T can we guarantee that the value in t1 is unchanged after the invocation of f(t1)? Justify your answer. [3 marks] (d) Explain how Java's implementation of generics precludes substituting T with a primitive type. [2 marks] (e) You are asked to redesign the standard library to incorporate an immutable list. Explain the relative merits of: (i) MutableList being a subtype of ImmutableList [2 marks] (ii) ImmutableList being a subtype of MutableList [2 marks] (iii) ImmutableList and MutableList having no common supertype [2 marks] (iv) ImmutableList and MutableList both subtyping CommonList [2 marks] 5 (TURN OVER) CST0.2020.1.6 SECTION C 5 Introduction to Probability (a) You are looking forward to the European Cup 2020. The tournament is going to last for 30 days. Each day during the tournament, you want to invite all of your 100 classmates to your house. But people might be busy on any given day, so you expect each classmate to come with probability 0.03 on each day, and they show up independently of one another. Let X denote the number of classmates that show up on any given day. Note: In parts (ii), (iii) and (iv) you do not have to compute explicit numerical values. (i) Give the exact and approximate distributions of X along with parameters. Explain why the approximation is valid. [3 marks] (ii) What is the approximate probability that between 2 and 4 classmates, inclusive, show up on any given day? [3 marks] (iii) What is the exact probability that at least 2 classmates show up on any given day? [3 marks] (iv) What is the probability that there will be more than 27 days where at least 2 classmates show up? [3 marks] (b) Suppose that each classmate is asked to arrive at 8pm, but the actual arrival time differs in minutes by a continuous uniform distribution [, +], where is an unknown parameter. Your data set Y1, Y2, . . . , Yk is a realisation of independent random samples from that distribution, for some integer k 1. (i) Show that T = 3 k (Y 2 1 + Y 2 2 + + Y 2 k ) is an unbiased estimator for 2 . [3 marks] (ii) Is T also an unbiased estimator for ? [1 mark] (iii) Justify your answer in (b)(ii). [4 marks] 6 CST0.2020.1.7 6 Introduction to Probability (a) Give the probability mass function of each of the three distributions: (i) Poisson distribution, [2 marks] (ii) Bernoulli distribution, [2 marks] (iii) Binomial distribution. [2 marks] (b) The football association has asked you to analyse the England team football matches from previous big tournaments. For each of the three situations below, choose a suitable distribution and compute its expectation and variance. Note: In Part (b)(ii) you do not have to compute explicit numerical values. (i) You analyse 2000 penalty kicks from the last 10 years of big tournaments. It turns out that 1200 of those 2000 penalty kicks were goals. A penalty kick is chosen at random. Let X be a success if a goal is scored. [2 marks] (ii) Consider again the setting from (b)(i). If you pick 50 penalty kicks without replacement, let Y be the number of missed goals out of that sample. [2 marks] (iii) Taking into account all games from the last 10 years of big tournaments, the England football team scored an average of 1 goal every 30 minutes. Let Z be the number of scored goals during a match of 90 minutes

a deductive system for predicate calculus, covering at least the following topics: (a) terms, formulae and sequents [5 marks] (b) introduction versus elimination rules [5 marks] (c) side conditions and variable capture [5 marks] Illustrate your explanations with examples. 12 Computational Number Theory Describe how the set of composite numbers can be recognised in Random Polynomial time. [12 marks] Describe how the set of prime numbers can be recognised in Non-deterministic Polynomial time. [8 marks] 6 CST.94.7.7 13 Semantics of Programming Languages Dijkstra proposed the language of guarded commands with the following syntax. Commands take the form c ::= skip | abort | X := e | c; c | if gc fi | do gc od where e is an arithmetic expression and gc stands for a guarded command of the form b1 c1 [] b2 c2 for boolean expressions b1 and b2, called guards, and commands c1 and c2. Execution of the command skip does not result in a change of state. Following Dijkstra's intentions, if no guard evaluates to true at a state, then the guarded command is said to fail, in which case, the guarded command does not yield a final state. Otherwise, the guarded command executes as one of the commands ci whose associated guard bi evaluates to true. The execution of the command abort does not yield a final state from any initial state. The command if gc fi executes as the guarded command gc, if gc does not fail, otherwise, it acts like abort. The command do gc od executes repeatedly as the guarded command gc, while gc continues not to fail, and terminates when gc fails. (a) Assume that boolean and arithmetic expressions have no side effects and always terminate, and that the rules for their evaluation are given. Write down a collection of rules for an inductively defined evaluation relation of the form c, S S 0 whose sense is "starting from the initial state S, the evaluation of the command c terminates at the final state S 0 ." [10 marks] (b) Give the commands in Dijkstra's guarded language which simulate the standard imperative programming commands if b then c1 else c2 and while b do c respectively. You may assume that if b is a boolean expression, then so is b, the negation of b. [2 marks] (c) Give an appropriate definition of semantic equivalence of commands with respect to the evaluation relation defined in (a). Prove that for any boolean expression b and any command c, the command do b c [] b c od is semantically equivalent to the command if b (c; do b c [] b c od) [] b skip fi [8 marks] 7 [TURN OVER CST.94.7.8 14 Concurrency Define what is meant by observational equivalence of CCS agents. [5 marks] A transmitter T, transmission medium M, and receiver R are modelled by CCS agents with the following definitions: T def = in.i.T0 T 0 def = r.i.T0 + a.T M def = i.M0 M0 def = o.M + .r.M R def = o.out.a.R M is an unreliable medium: having received an input message from T (action i) it either outputs the message to R (action o), or loses it (represented by the action) and then sends a request for retransmission (action r). If R does receive the message, after broadcasting it (action out) it sends an acknowledgement directly to T (action a). Calculate the transition graph of (T|M|R) \ {i, o, r, a} and hence show that this agent is observationally equivalent to a simple buffer B with definition B def = in.out.B [10 marks] Are (T|M|R) \ {i, o, r, a} and B observationally congruent? [3 marks] Do the two agents have the same behaviour with respect to divergence, that is, the ability to perform a series of actions ending in an infinite sequence of -actions?