answer all questions as instructed below.

make sure you have attended all questions.Comparative Architectures (a) Describe the organisation of a two-level branch predictor that makes use of a global branch history. [3 marks] (b) What are false (or name) dependencies and what hardware technique is often used to remove them within a processor? [3 marks] (c) You are asked to design a new Instruction Set Architecture (ISA). You are told that this new ISA will be the basis for both simple low-power and high-performance processor implementations. Would you include the features or design choices listed below? In each case, carefully justify your answer. (i) A branch delay slot. (ii) The ability to predicate the execution of most instructions. (iii) A conditional move instruction. (iv) The use of condition codes (or flags) to specify the branch condition. (v) A large number of general-purpose registers. (vi) A TSO memory consistency model. (vii) Support for custom ISA extensions, e.g. to allow the addition of special functional units. [14 marks] 4 CST2.2019.8.5 4 Computer Vision (a) Explain why such a tiny number of 2D Gabor wavelets as shown in this sequence are so efficient at representing faces, and why such wavelet-based encodings deliver good performance in "appearance-based" algorithms for face recognition. What role do such encodings have in representing different facial expressions? What sort of neural evidence is there for such encodings in human vision? Number of Wavelets 16 52 116 216 original [6 marks] (b) Explain the "receptive field" concept as used both in CNNs (convolutional neural networks) and in visual neuroscience, and explain the role of trainable connections. Why is the concept of convolution relevant? Roughly how many layers are in the 'FaceNet' CNN, and how many connection parameters must be trained? By comparison, in the visual cortex of the brain, typically how many synapses are there per neurone, and what is the total length of "wiring" (neurite connections) per cubic-millimeter? Can connection updates be a basis for computer vision? [6 marks] (c) In relation to the image formation diagram shown below, explain: (i) the concept of a reflectance map; (ii) what is a specular surface; (iii) what is a Lambertian surface; and (iv) what is surface albedo. Give the defining relationships for the amount of light from a point source that is scattered in different directions by such illuminated surfaces, and describe the inferences that a vision system must make with them. [8 marks] .->q'l :r )-- ?rxi The definitions of the angles i, , and g 5 (TURN OVER) CST2.2019.8.6 5 Cryptography (a) The Tripos Encryption Standard (TES) is a block cipher optimized for use on UGPs ("undergraduate processors"). It operates on 4-bit blocks, written as hexadecimal digits (e.g., a 9 = 3). For one particular key K, it implements the following permutation: m 0 1 2 3 4 5 6 7 8 9 a b c d e f EK(m) 1 b 5 c 7 e 2 a 4 9 f d 0 3 6 8 Using this key K, decrypt the following three ciphertexts according to the indicated modes of operation. [Note: the XOR table at the bottom of this page may be of use.] (i) ECB: 188b06 [2 marks] (ii) CBC: 301b2 [3 marks] (iii) CFB: 10f6d [3 marks] (b) State four advantages that counter mode has over either CBC or CFB mode. [4 marks] (c) Using the same K as in Part (a): (i) Show that the CBC-MAC tag for message 1234 is d. [3 marks] (ii) Demonstrate that CBC-MAC with a given K is not collision resistant, by showing how to find another message, of the form 1x04, that results in the same CBC-MAC message tag (without iterating over different candidates for 4-bit block x). [5 marks] UGP XOR accelerator: 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 0 1 2 3 4 5 6 7 8 9 a b c d e f 1 1 0 3 2 5 4 7 6 9 8 b a d c f e 2 2 3 0 1 6 7 4 5 a b 8 9 e f c d 3 3 2 1 0 7 6 5 4 b a 9 8 f e d c 4 4 5 6 7 0 1 2 3 c d e f 8 9 a b 5 5 4 7 6 1 0 3 2 d c f e 9 8 b a 6 6 7 4 5 2 3 0 1 e f c d a b 8 9 7 7 6 5 4 3 2 1 0 f e d c b a 9 8 8 8 9 a b c d e f 0 1 2 3 4 5 6 7 9 9 8 b a d c f e 1 0 3 2 5 4 7 6 a a b 8 9 e f c d 2 3 0 1 6 7 4 5 b b a 9 8 f e d c 3 2 1 0 7 6 5 4 c c d e f 8 9 a b 4 5 6 7 0 1 2 3 d d c f e 9 8 b a 5 4 7 6 1 0 3 2 e e f c d a b 8 9 6 7 4 5 2 3 0 1 f f e d c b a 9 8 7 6 5 4 3 2 1 0 6 CST2.2019.8.7 6 E-Commerce (a) Describe five ecommerce business models. [5 marks] (b) Describe five things to consider when internationalising an ecommerce business. [5 marks] (c) Does the nature of the Internet naturally lead to dominant firms in ecommerce markets? [10 marks] 7 (TURN OVER) CST2.2019.8.8 7 Hoare Logic and Model Checking Consider a programming language that consists of commands C composed from assignments X := E (where X is a program variable, and E is an arithmetic expression), heap allocation X := alloc(E1, . . . , En), heap assignment [E1] := E2, heap dereference X := [E], disposal of heap locations dispose(E), the no-op skip, sequencing C1; C2, conditionals if B then C1 else C2 (where B is a boolean expression), and loops while B do C. null is 0 (a) Explain informally what it means for a separation logic partial correctness triple {P} C {Q} to be valid. [3 marks] (b) Explain informally what it means in terms of the executions of C for the separation logic partial correctness triple {>} C {} to be valid. [2 marks] (c) Recall the list representation predicate list: list(t, []) = (t = null) list(t, h :: ) = y.((t 7 h) ((t + 1) 7 y) list(y, )) We write [] for the empty mathematical list; h :: for the mathematical list the head of which is h, and the tail of which is ; ++ for the concatenation of mathematical lists and ; [i] for the i-th element of the list , starting at 0; and [k, . . . , n] for the ascending list of integers from k to n, including k and n. Give a proof outline, including a loop invariant, for the following triple: {N = n N 0} X := null; while N > 0 do (X := alloc(N, X); N := N 1) {list(X, [1, . . . , n])} [4 marks] (d) Also recall the partial list representation predicate plist: plist(t, [], u) = (t = u) plist(t, h :: , u) = y.((t 7 h) ((t + 1) 7 y) plist(y, , u)) Give a loop invariant for the following list sum triple: {list(X, )} Y := X; N := 0; while Y 6= null do (M := [Y ]; N := N + M; Y := [Y + 1]) n list(X, ) N = Plength()1 i=0 [i] o [4 marks] (e) Give a loop invariant for the following list concatenation triple: {list(X, ) list(Y, )} if X = null then Z := Y else Z := X; U := Z; V := [Z + 1]; while V 6= null do (U := V ; V := [V + 1]); [U + 1] := Y {list(Z, ++ )} [5 marks] (f ) Describe precisely a stack and a heap that satisfy list(X, [1, . . . , 3]). [2 marks] 8 CST2.2019.8.9 8 Information Theory (a) Consider the four-state Markov process in the graph below. It emits the eight letters {A, B, C, D, e, f, g, h} with probabilities and changes of state as shown, but note the sequence constraints. (For example, an A can only be followed by a B or an e.) Letter emissions with clockwise state transitions occur with probability , and the others with probability 1 , where 0 < < 1. p = p = p = p = 1 p = p = 1 p = 1 p = 1 "B" "C" "A" "D" "h" "g" "f" "e" (i) First imagine a one-state Markov process that emits any of eight letters with equal probabilities. What is its entropy? [2 marks] (ii) For the four-state Markov process shown with parameter , what is the long-term probability distribution across the eight letters? [4 marks] (iii) In terms of parameter , what is the overall entropy H() of this four-state Markov process? [2 marks] (iv) Sketch a plot of H() as a function of . Compare its maximum value with your earlier answer in Part (a)(i) for a one-state Markov process that also emits eight letters, and explain the difference, if any. [4 marks] (b) Is it possible to construct an instantaneous code (a code possessing the prefix property) for a five-letter symbol set using codewords whose lengths in bits are: 1, 2, 3, 3, and 4 bits? Justify your answer by stating the relevant condition. [4 marks] (c) Provide an operation in linear algebra that involves simply the multiplication of a matrix by a vector, which describes the Discrete Fourier Transform of a discrete sequence of data f[n] = (f[1], ..., f[N]) to obtain Fourier coefficients F[k] = (F[1], ..., F[N]). Define the elements of the (N N) matrix and give the computational cost of the operation in this vector-matrix form. [4 marks]1 Artificial Intelligence Evil Robot has been kidnapped by experimental psychologists, who are forcing him to solve problems involving the stacking of blocks. For example, given the start state on the left, he is asked to re-arrange the blocks into the state shown on the right. = B D D C B A C A You are to help him solve these problems by designing a system using planning graphs. A block can only be moved if it does not have another block on top of it. Only one block can be placed directly on top of another, although stacks of multiple blocks are allowed. (a) Explain how this problem can be represented as a planning problem, such that it can be analyzed using a planning graph. Describe how state should be represented, and how actions should be represented, giving a specific example relevant to the stated problem in each case. [5 marks] (b) Using the start state in the diagram above, draw the initial planning graph for the problem, including the initial state level, the first action level, and the state level resulting from the first action level. Do not add any mutex links at this stage. [4 marks] (c) Define an inconsistent effects mutex and an interfering actions mutex. Add to your diagram for Part (b) a single example of each, or explain why this is not possible. [4 marks] (d) Define a competing for preconditions mutex. By adding a small number of actions to the second action level of your planning graph, give a single example of such a mutex, or explain why this is not possible. [2 marks] (e) How many more action levels would you expect to need before a valid plan could be extracted to solve the problem stated? Explain your answer. [2 marks] (f ) Give two examples of the difficulties that might arise if we also wish to include long blocks as follows: B E B D D A C A = E C In each case explain why it might be difficult to address such an extension using planning graphs. [3 marks] 2 CST1.2019.6.3 2 Artificial Intelligence (a) Describe the state-variable representation for planning by discussing the following, giving specific examples of each concept: (i) Rigid relations and state variables. [2 marks] (ii) Actions. [2 marks] (iii) The representation of state. [2 marks] (iv) Goals and solutions. [2 marks] (b) Your boss has suggested using heuristic search to solve a planning problem expressed in the state-variable representation. Explain how this might be achieved. You do not need to suggest a specific heuristic at this stage. [3 marks] (c) Comment on whether or not heuristic search is a good approach to solving planning problems in the state-variable representation, compared with the alternative of using a constraint satisfaction solver. [5 marks] (d) Suggest an admissible heuristic that could be used when applying A? search to solving a planning problem in the state-variable representation. Show that it is admissible. [4 marks] 3 (TURN OVER) CST1.2019.6.4 3 Complexity Theory A Boolean formula is said to be satisfiable if there is an assignment : V {true, false} of values to the variables of that makes it true. A quantified Boolean formula is an expression that is (i) either a Boolean formula; or (ii) X where is a quantified Boolean formula and X is variable; or (iii) X where is a quantified Boolean formula and X is variable. We say that a quantified Boolean formula is satisfied by an assignment : V {true, false} if either is a Boolean formula that is made true by ; or is X and either [X/true] or [X/false] make true; or is X and both [X/true] and [X/false] make true. Here, [X/v] denotes the assignment that is the same as for all variables apart from X, and it maps X to the truth value v. We write QBF for the decision problem of determining whether a given quantified Boolean formula is satisfiable. In answering the questions below, you may assume the NP-completeness of any standard problem, as long as you state your assumptions clearly. (a) Show that QBF is NP-hard. [4 marks] (b) Show that QBF is co-NP-hard. [6 marks] (c) Show that QBF is in PSpace. [6 marks] (d) Is QBF NP-complete? Why or why not? [4 marks] 4 CST1.2019.6.5 4 Complexity Theory A Boolean formula is in conjunctive normal form (CNF) if it is the conjunction of clauses, each of which is the disjunction of literals. It is said to be in k-CNF (for k N) if each clause has exactly k literals in it. An assignment : V {true, false} of truth values to the variables is a satisfying assignment for a CNF formula if it makes at least one literal in each clause of true. It is said to be a not-all-equals assignment for if it makes at least one literal in each clause of true and at least one literal in each clause of false. Let CNF-SAT denote the problem of determining, given a formula in CNF, whether it has a satisfying assignment. Let k-SAT denote the problem of determining, given a formula in k-CNF, whether it has a satisfying assignment. Let k-NAE denote the problem of determining, given a formula in k-CNF, whether it has a not-all-equals assignment. (a) Explain why CNF-SAT is NP-complete. Your explanation should include a full definition of NP-completeness and a brief sketch of the proof of the Cook-Levin theorem. [5 marks] (b) Show that 3-SAT is NP-complete by means of a suitable reduction. [3 marks] (c) Give a polynomial-time reduction from 3-SAT to 4-NAE. What can you conclude about the complexity of the latter problem? (Hint: consider introducing one new variable and adding it to every clause.) [8 marks] (d) Show that the problem 3-NAE is NP-complete. (Hint: consider a reduction from 4-NAE) [4 marks] 5 (TURN OVER) CST1.2019.6.6 5 Computation Theory For each e N, let e denote the partial function N * N computed by the register machine with index e. (a) What is meant by a universal register machine for computing partial functions N k * N of any number of arguments k. [3 marks] (b) How would you modify the machine from Part (a) to compute the partial function u : N 2 * N satisfying u(e, x) e(x) for all e, x N? [2 marks] (c) Given a register machine computable partial function g : N 2 * N, show that there is a total function g : N N which is register machine computable and which satisfies u(g(x), y) g(x, y) for all x, y N. [7 marks] (d) Suppose h : N N is a total function which is register machine computable. Show that there exists a number n N such that n and h(n) are equal partial functions. [Hint: let g be the computable partial function defined by g(x, y) u(h(u(x, x)), y) and consider g(e) where g is the function obtained from g as in Part (c) and e is the index of some register machine that computes it.] [8 marks] 6 CST1.2019.6.7 6 Computation Theory (a) (i) Give an inductive definition of the relation M = N of -conversion between -terms M and N. [3 marks] (ii) What is meant by a term in -normal form? [1 mark] (iii) If M and N are in -normal form, explain why M = N implies that M and N are -equivalent -terms. [2 marks] (You need not define notons such as -equivalence and capture-avoiding substitution.) (b) Show that there are -terms True, False and If satisfying If True M N = M and If False M N = N for all -terms M and N and with True 6= False. [4 marks] (c) Define Curry's fixed point combinator Y and prove its fixed point property. [3 marks] (d) Consider the following two properties of a -term M: (I) there exist -terms A and B with M A = True and M B = False (II) for all -terms N, either M N = True or M N = False. Prove that M cannot have both properties (I) and (II). [Hint: if M has property (I), consider M (Y (x. If (M x) B A)).] [4 marks] (e) Deduce that there is no -term E such that for all -terms M and N E M N = ( True if M = N False otherwise [3 marks] 7 (TURN OVER) CST1.2019.6.8 7 Foundations of Data Science (a) Let X1, . . . , Xn be independent binary random variables, P(Xi = 1) = , P(Xi = 0) = 1 , for some unknown parameter . Using Uniform[0, 1] as the prior distribution for , find the posterior distribution. [Note: For your answer, and in answer to parts (b) and (d), give either a named distribution with its parameters, or a normalised density function.] [3 marks] I have collected a dataset of images, and employed an Amazon Mechanical Turk worker to label them. The labels are binary, nice or nasty. To assess how accurate the worker is, I first picked 30 validation images at random, found the true label myself, and compared the worker's label. The worker was correct on 25 and incorrect on 5. (b) Let be the probability that the worker labels an image incorrectly. Using Beta(0.1, 0.5) as the prior distribution for , find the posterior. [3 marks] I next ask the worker to label a new test image, and they tell me the image is nice. Let z {nice, nasty} be the true label, and let the prior distribution for z be Pr(nice) = 0.1, Pr(nasty) = 0.9. (c) For both z = nice and z = nasty, find P

worker says nice | z, . Hence find the posterior distribution of (z, ). Your answer may be left as an un-normalised density function. [5 marks] (d) Find the posterior distribution of z. [5 marks] My colleague has more grant money and she can employ 3 workers to rate each image. On a test set of 30 images, she found that they all agreed on 15 images, worker 1 was the odd one out on 8 of the images, worker 2 was the odd one out on 4, and worker 3 was the odd one out on 3. (e) Let i be the probability that worker i labels an image incorrectly. Find the posterior distribution of (1, 2, 3). Your answer may be left as an un-normalised density function. [4 marks] Hint. The Beta(, ) distribution has mean /( + ) and density Pr(x) = + 1 1 x 1 (1 x) 1 , x [0, 1] . Data Science (djw1005) (a) Let xt be the number of new COVID infections on date t. We anticipate approximately exponential growth or decay, xt+1 (1 + )xt , and we would like to estimate from a dataset (x1, . . . , xT ). (i) Find the maximum likelihood estimator for for the model Xt+1 Poisson (1 + )xt [2 marks] (ii) Find the maximum likelihood estimator for for the model Xt+1 Normal (1 + )xt , (xt) 2 [3 marks] (iii) For the latter model, explain how to compute a 95% confidence interval for . Explain the resampling step carefully. [4 marks] (b) We don't actually know the number of new infections xt on date t: we only know the number of new positive test results, yt . We anticipate yt dow(t)xt , where dow(t) gives the day of the week for date t. We would like to estimate not only but also Mon, ..., Sun from the dataset (y1, . . . , yT ). (i) Propose a probability model for Yt+1 in terms of yt . [5 marks] (ii) Explain briefly how to estimate the parameters of your model. In your answer, you should consider whether or not the parameters are identifiable. [6 markAssuming you get a job as a network engineer in a multinational company that has five (5) regional station that must be interconnected with others for smooth operation of the organization. The company is about to network the regional offices together. Each physical link must allow communication in both directions. Use the knowledge acquired in this course to advice the management of the company based on the following: a) Recommend the most suitable Network topology for the organization. b) Give detail explanation of the recommended Topology. c) Illustrate the explanation in (b) with a diagram to show the interconnectivity of the five (5) regional offices. d) Explain four (4) major advantages of the topology named in (a) over other network topology

1. Enumerates five components of a data communications system. 2. Define key element of protocol. 3. Define two types of standards. 4. Describe the role of the following standards creation committee. 46 i. International Organization for Standardization (ISO). ii. International Telecommunication Union iii. American National Standards Institute (ANSI). iv. Institute of Electrical and Electronics Engineers (IEEE). 1) What are the three criteria necessary for an effective and efficient network? 2) Categorize the four basic topologies in terms of line configuration. 3) Name the four basic network topologies, and cite an advantage of each type. 4) For n devices in a network, what is the number of cable links required for a mesh, ring, bus, and star topology? 5) What are some of the factors that determine whether a communication system is a LAN or WAN?

Define data and Data Communication. 2. Compare analog and digital data 3. Why data communication 4. List and explain components of data communication system. 5. Highlights any 5 examples of resources that can be share on data communication and networks 6. Define and gives example of basic components of data communication network. 7. What are the major criteria that data communication network must meet. 23 8. Highlights the factors that affect response time as related to performance of data communication network. 9. List various ways of data representation in computer system. 10. Define Data communication equipment and data terminal equipment. Give at least two examples in each case.

What are the concerns of the physical layer in the Internet model? 2. What are the responsibilities of the data link layer in the Internet model? 3. What are the responsibilities of the network layer in the Internet model? 4. What are the responsibilities of the transport layer in the Internet model? 5. What is the difference between a port address, a logical address, and a physical address? 6. Name some services provided by the application layer in the Internet model. 7. How do the layers of the Internet model correlate to the layers of the OSI model? 8. How are OSI and ISO related to each other? 9. Match the following to one or more layers of the OSI model: a) Route determination b) Flow control c) Interface to transmission media d) Provides access for the end user 9. Match the following to one or more layers of the OSI model: a) Reliable process-to-process message delivery b) Route selection c) Defines frames d) Provides user services such as e-mail and file transfer e) Transmission of bit stream across physical medium 10. Match the following to one or more layers of the OSl model: a) Communicates directly with user's application program 55 b)Error correction and retransmission c) Mechanical, electrical, and functional interface d)Responsibility for carrying frames between adjacent nodes