The members return a pointer to an element or the nullptr if there is none. Implement itera- tors for List, Slist, and Vector as classes derived from Itor. Compare this design to the abstract Container design in X.32[7]. [9] ( 1) Make a version of X.32[7] where the element type is a template argument. [10] ( 2.5) Given an Itor class like the one in X.32[8], consider how to provide iterators for for- wards iteration, backwards iteration, iteration over a container that might change during an iteration, and iteration over an immutable container. Organize this set of iterators so that a user can interchangeably use iterators that provide sufficient functionality for an algorithm. Minimize replication of effort in the implementation of the containers. What other kinds of iterators might a user need? List the strengths and weaknesses of your approach. [11] ( 1) Make a version of X.32[8] where the element type is a template argument. [12] ( 3) Design a ''truly object-oriented'' container holding Objects as elements A Container (along the lines of X.32[7]) is itself derived (directly or indirectly) from Object. Implement a List, Slist, and Vector as outlined in X.32[7] and test them as in X.32[7]. [13] ( 2.5) Generate 10,000 uniformly distributed random numbers in the range 0 to 1,023 and store them in Describe how the Lempel Ziv text compression algorithm works, illustrating your answer by deriving the sequence of numbers and corresponding bit patterns it would generate when applied to a string starting with the following 24 characters: ABCDABCDABCDABCDABCDABCD ... You may assume that the initial table is of size 256 (containing bytes 0 to 255) and that the codes for "A", "B", "C" and "D" are 65, 66, 67 and 68, respectively. [12 marks] (b) Estimate how many bits the algorithm would use to encode a string consisting of 1000 repetitions of the character "A". [8 marks] (a) Discuss to what extent a programmer can expect a program that conforms to a standard to generate identical results when run under dierent conforming compilers on dierent machines. [6 marks] (b) ALGOL 60 provided call by value and call by name, Pascal provided call by value and call by reference, and ALGOL-W provided a variety of calling methods including call by result and call by value-result. Briey describe the calling mechanisms just mentioned and discuss why most modern programming languages provide only call by value. [8 marks] (c) Discuss the reasons why languages such as Fortran, Algol and PL/I designed in 1950s and 1960s are less widely used than languages designed in the last 20 years. [6 marks] (a) What problem do real-time scheduling algorithms try to solve? [2 marks] (b) Describe one static priority and one dynamic priority real-time scheduling algorithm. You should discuss the issue of admission control, and comment on the data structures that an implementation would need to maintain and on how these would be used to make scheduling decisions. [8 marks] (c) A designer of a real-time system wishes to have concurrently executing tasks share a data structure protected by a mutual exclusion lock. (i) What scheduling problem could arise here? [2 marks] (ii) How could this problem be overcome? [2 marks] (d) The designer also wishes the real-time system to use demand paged virtual memory for eciency. What problems could arise here, and how could they be overcome? [6 marks] (a) For Single Precision in the IEEE binary oating-point standard (IEEE 754) the precision is dened as 24, and the exponent requires 8 bits of storage. With reference to IEEE Single Precision, explain the terms exponent, signicand, precision, sign bit, normalised number, denormal number. [6 marks] (b) Explain the term hidden bit. What are the values of the hidden bit for normalised and denormal numbers? How is the exponent stored and why? How are the exponent, signicand and sign bit arranged in memory? [4 marks] (c) Let x denote the oating-point representation of a number x. Dene the terms absolute error (x) and relative error (x) in representing x. How are x and x related? Dene machine epsilon (m). [3 marks] (d) Assume x = y = z = m. Using worst-case analysis, estimate xy, xy. Find an expression for w where w = zxy. [4 marks] (e) Working to 4 signicant decimal digits only, compute w when x = 2.018, y = 2.008,z = 4.058. Given m ' 0.5103, how many signicant decimal digits of w can be relied on? [3 marks] (a) What is Turing's Thesis? [2 marks] (b) Explain the action of a Turing machine that is specied by a quintuplet description. [4 marks] (c) Dene the conguration of a Turing machine at step t, and establish equations that specify the conguration of a k-symbol Turing machine at step (t +1) in terms of the conguration at the previous step t. [6 marks] (d) Explain how you would use your equations to simulate a specic Turing machine by a register machine whose program encodes the quintuplet description. To what extent does this support Turing's Thesis? [Explicit program for a register machine is not required.] [8 marks] Describe an algorithm for performing scan conversion of a set of 3D polygons, including details of clipping, projection, and the underlying 2D polygon scan conversion algorithm. You may assume that you are given the colour of each polygon and that no lighting calculations are required. Please state any additional assumptions that you need to make. Ray tracing is not an acceptable answer to this question. [20 marks] (a) Explain briey mechanisms that software on a desktop computer can use to securely generate secret keys for use in cryptographic protocols. [5 marks] (b) Give two dierent ways of implementing residual information protection in an operating system and explain the threat addressed by each. [5 marks] (c) Consider the standard POSIX le-system access control mechanism: (i) Under which conditions can les and subdirectories be removed from a parent directory? [2 marks] (ii) Many Unix variants implement an extension known as the "sticky bit". What is its function? [2 marks] (iii) On a POSIX system that lacks support for the "sticky bit", how could you achieve an equivalent eect? [2 marks] (d) VerySafe Ltd oer two vaults with electronic locks. They open only after the correct decimal code has been entered. The VS100 - a low-cost civilian model - expects a 6-digit code. After all six digits have been entered, it will either open or will signal that the code was wrong and ask for another try. The VS110 - a far more expensive government version - expects a 40-digit code. Users of a beta-test version of the VS110 complained about the diculty of entering such a long code correctly. The manufacturer therefore made a last-minute modication. After every ve digits, the VS110 now either conrms that the code has been entered correctly so far, or it asks for the previous ve digits again. Compare the security of the VS100 and VS110. [4 marks]

There is deliberate over-provision of fans so that there is adequate cooling as long as at least one fan in each group is working. The local maintenance policy is to do nothing until all three fans in one or other of the groups have failed. When that happens, all six fans in the room are replaced including those that have not failed. (a) When replacement occurs, what is the minimum number of working fans that could be replaced and what is the maximum number that could be replaced? Justify your answers. [2 marks] (b) Let X be a random variable whose value r is the number of failed fans when replacement occurs. Clearly 0 6 r 6 6 and, for some values of r, the probability P(X = r) = 0. By constructing an event tree or otherwise, tabulate P(X = r) for r = 0,1,2...6. All non-zero probabilities should be expressed as fractions. [12 marks] (c) Determine the expectation and variance E(X) and V(X). [6 marks] (a) an standard library vector, (b) a Vector from X.32[7], (c) a Vector from X.32[8]. (d) a Vector from X.32[12]. In each case, calculate the arithmetic mean of the elements of the vector (as if you didn't know it already). Time the resulting loops. Estimate, measure, and compare the memory consumption for the three styles of vectors S