As the XOR operation is not defined on the set {A, . . . , Z}, we replace it here during encryption with modulo-26 addition (e.g., C D = F and Y C = A). (i) Decrypt the following ciphertexts, which were encrypted using (A) Electronic codebook mode: UOMHDJT [2 marks] (B) Cipher feedback mode: RVPHTUH [4 marks] (C) Output feedback mode: LNMSUUY [4 marks] (ii) Determine the CBC-MAC for the message TRIPOS. [4 marks] (b) Consider another small pseudo-random permutation, this time defined over the set of decimal digits {0, 1, 2, . . . , 9}, using modulo-10 addition instead of XOR (e.g., 7 3 = 0). (i) You have intercepted the message 100 with appended CBC-MAC block 4. The message represents an amount of money to be paid to you and can be of variable length. Use this information to generate a message that represents a much larger number, and provide a valid CBC-MAC digit, without knowing the pseudo-random permutation or key that the recipient will use to verify it. [4 marks] (ii) What mistake did the designer of the communication system attacked in part (b)(i) make (leaving aside the tiny block size), and how can this be fix

(a) Describe the intent of the variables buffer, count, front and back. [4 marks] (b) Describe, with justification, three problems with the above implemention which means it does not adhere to the specification of a concurrent queue. [6 marks] (c) Write new implementation of a generic concurrent queue which stores items of type T. The constructor should accept an integer to specify the fixed size of the buffer. [8 marks] (d) Two Java threads form a pipeline where the output of the first thread is used as an input into the second. A concurrent queue is used to allow the output from the first thread to be used as input into the second. Describe, with justification, a situation where increasing the size of the buffer in the concurrent queue would improve overall system throughput.

(a) Define subclasses of Params, Result and Function (called Squared) to compute x 2 where x is of type double. (b) Implement a client which executes Squared. Your solution should accept an argument x from the user, remotely execute the code and print out the result. You may assume a static method byte[] getClassBytes(Class c). [5 marks] (c) An Invoke object can contain incompatible Function and Params references. Provide an example and describe how to refactor your client to include a compile-time compatibility check. Can the server also check? [5 marks] (d) Describe the security challanges i the server implementation. How might these be addressed? [3 marks] (e) Describe how you could improve runtime error handling by the server as well as reporting such errors to the client.

(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 mar

Prelab Exercises Your task is to write Java program that will print out the following message (including the row of equal marks): Computer Science, Yes!! ============== ==== An outline of the program is below. Complete it as follows: a. In the documentation at the top, fill in the name of the file the program would be saved in and a brief description of what the program does. b. Add the code for the main method to do the printing. 1/ *******kk******kk*******k*******k*******k********k*******k** / File Name: Purpose / ************************************************************ public class CSYes I------ --- ---- - -- --- // The following main method prints an exciting message about computer science /--

The variation we will be using is that we want to fill the Knapsack to as close to the total weight limit of the Knapsack as possible. For example, if the Knapsack holds 20 kilograms, we want to add items weighing as close to or equal to 20 kilograms as possible (without going over). The code for Subset-Sum is simple, and very close to the Knapsack code. It is given below. Can you spot the difference between Subset-Sum and Knapsack? Like Knapsack, the time complexity of Subset-Sum is O(nW), where n is the total number of items and W is the total weight capacity of the Knapsack. That (nW) is the size of the matrix that must be filled in. Notice that if W is large (say, 10,000,000) and there are 100 items to consider, we have to fill in a billion-cell matrix. That isn't very practical. There are algorithms that approximate the answer with varying degrees of success. We will look at a greedy algorithm that is guaranteed to fill the knapsack at least half full. In practice, it might even do better than that. Here is the approximation algorithm: GREEDY APPROXIMATION ALGORITHM 1. Sort the weights in descending order (largest weights first). 2. Add the weights in descending order until the next weight will not fit. 3. Return the total weight added. program both algorithms, generate some random data, and compare the results. Specific instructions follow: 1. Our basket will hold a weight of 1000. Using a random number generator, generate 100 possible items for the basket. The items should have random weights between 1 and 600.

2. Use the dynamic programming algorithm to compute the exact optimal solution for the set of 100 items. Note that the solution is a weight, wj, where 0 < wj <= 1000. 3. Use the greedy approximation algorithm to compute an approximate solution using the same set of items. 4. Run this set of steps 10 times, keeping track of the high, low and average values. Also, keep track of the running times for both algorithms. This project requires a report. The report should contain a table with your experimental results. The Approximation Factor is just the greedy result divided by the exact result. The table should look like this, but with your own numbers (my numbers are completely made up and should not be used as a guide): Iteration Dynamic (Exact) Greedy (approx.) Approximation Factor 1 997 927 93% 2 823 754 92% ... 10 742 650 88% Average ??? ??? ??? A report is required for this project. It should include the following: 1. An introduction including your approach to the problem, the theoretical time complexity of each subset-sum-finding method used, programming language used and how this might affect the results, problems encountered, etc. 2. A proof that the greedy algorithm is guaranteed to fill the knapsack at least half full. In your proof you should assume that there are enough items with weights to fill the knapsack at least half full. 3. The table with results, as shown above. 4. A discussion of the results, how close they are to each other, and whether the greedy algorithm always fills the knapsack at least half full. 5. A discussion of the running times. Include a table if it will help. How much faster is the greedy algorithm? 6. The code should be submitted separately (in a zip file) and included as an appendix.

through all triples of vertices, FloydWarshall requires only a single pass, but only because it uses a different nesting order for the three loops! Exercises 1. (a) Describe a modification of LeyzorekAPSP that returns an array of predecessor pointers, in addition to the array of shortest path distances, still in O(V3 log V) time. (b) Describe a modification of FloydWarshall that returns an array of predecessor pointers, in addition to the array of shortest path distances, still in O(V3) time. 2. All of the algorithms discussed in this chapter fail if the graph contains a negative cycle. Johnson's algorithm detects the negative cycle in the initialization phase (via Bellman-Ford) and aborts; the dynamic programming algorithms just return incorrect results. However, all of these algorithms can be modified to return correct shortest-path distances, even in the presence of negative cycles. Specifically, for all vertices u and v: If u cannot reach v, the algorithm should return dist[u, v] = . If u can reach a negative cycle that can reach v, the algorithm should return dist[u, v] = . Otherwise, there is a shortest path from u to v, so the algorithm should return its length. (a) Describe how to modify Johnson's algorithm to return the correct shortest-path distances, even if the graph has negative cycles. (b) Describe how to modify LeyzorekAPSP to return the correct shortestpath distances, even if the graph has negative cycles. (c) Describe how to modify Floyd-Warshall to return the correct shortest-path distances, even if the graph has negative cycles. 3. The algorithms described in this chapter can also be modified to return an explicit description of some negative cycle in the input graph G, if one exists, instead of only reporting whether or not G contains a negative cycle. (a) Describe how to modify Johnson's algorithm to return either the array of all shortest-path distances or a negative cycle. (b) Describe how to modify LeyzorekAPSP to return either the array of all shortest-path distances or a negative cycle. (c) Describe how to modify Floyd-Warshall to return either the array Our fast dynamic programming algorithm is still a factor of O(log V) slower in the worst case than the standard implementation of Johnson's algorithm. A different formulation of shortest paths that removes this logarithmic factor was proposed twice in 1962, first by Robert Floyd and later independently by Peter Ingerman, both slightly generalizing an algorithm of Stephen Warshall published earlier in the same year. In fact, Warshall's algorithm was previously discovered by Bernard Roy in 1959, and the underlying recursion pattern was used by Stephen Kleene8 in 1951. Warshall's (and Roy's and Kleene's) insight was to use a different third parameter in the dynamic programming recurrence. Instead of considering paths with a limited number of edges, they considered paths that can pass through only certain vertices. Here, "pass through" means "both enter and leave"; for example, the path wxyz starts at w, passes through x and y, and ends at z. Number the vertices arbitrarily from 1 to V. For every pair of vertices u and v and every integer r, we define a path (u, v,r) as follows: (u, v,r) is the shortest path (if any) from u to v that passes through only vertices numbered at most r.