Adv anced Algorithms (a) Assume you have a randomised approximation…

Question Answered step-by-step Adv anced Algorithms (a) Assume you have a randomised approximation… Advanced Algorithms (a) Assume you have a randomised approximation algorithm for a maximisation problem, and your algorithm achieves an approximation ratio of 2. What can you deduce for E[C ? /C], where C ? is the cost of the optimal solution, C is the cost of the solution of the approximation algorithm, and E[.] denotes the expectation? [4 marks] (b) Consider the following optimisation problem on graphs: Given an undirected, edge-weighted graph G = (V, E, w) with w : E ? R +, we want to find a subset S ? V such that w(S, V S) = P e?E(S,V S) w(e) (the total sum of weights over all edges between S and V S) is maximised. (i) Design a polynomial-time approximation algorithm for this problem. Also analyse its running time and prove an upper bound on the approximation ratio. [8 marks] (ii) Find a graph which matches your upper bound on the approximation ratio from Part (b)(i) as closely as possible. [4 marks] (iii) Consider now the following generalisation of the problem. Given an integer k ? 2, we want to partition V into disjoint subsets S1, S2, . . . , Sk so that we maximise X k i=1 w(Si , V Si). Describe an extension of your algorithm in Part (b)(i). What approximation ratio can you prove for this algorithm? [4 marks] 2 CST2.2021.9.3 2 Bioinformatics (a) Compute the local alignment between the following sequences: GATTACA, TATACG with the following rules: match score = +5, mismatch = ?3, gap penalty = ?4 and discuss how the alignment depends on the choices of match scores, mismatch and gap penalty. [5 marks] (b) Discuss how a local alignment algorithm allows identification of internal sequence duplications. [3 marks] (c) Define the UPGMA algorithm and state and justify its complexity. What is the output of the algorithm given the distance matrix of the species X1, X2, X3, X4 below? species X1 X2 X3 2 X3 4 4 X4 6 6 6 [4 marks] (d) Discuss a method to perform random access in DNA-based storage memory. [4 marks] (e) Discuss with one example the complexity of the Gillespie algorithm and comment on the main differences with respect to a deterministic approach. [4 marks] 3 CST2.2021.9.4 3 Business Studies You create a startup that helps companies manage office space use to boost employee wellbeing while minimising the potential for workplace virus transmission. After an intense 9 months of building a prototype and trialling it with early customers you demonstrate enough market traction to raise funding and hire a team of 15 people to support your growing customer base. You’ve just completed your first month of work with the new team in your new and larger office space when the government announces a new 2-month lockdown where your staff must work from home. As workers are no longer going to be in offices at the same rate, sales slow down. Confident that this is just temporary you decide to put 5 employees on furlough, with government support, until the lockdown is lifted. (a) Discuss what needs to be done to support your employees as you transition the business to everyone working from home. [8 marks] (b) Unfortunately, at the end of the initial lockdown period the government decides to extend it by another month. Looking at your financial forecasts you do not have enough funds to continue the business in its current form. Discuss what options are available to you. [12 marks] 4 CST2.2021.9.5 4 Comparative Architectures (a) A superscalar processor may speculatively execute loads even when one or more earlier stores have not yet computed their memory addresses. In practice, we would need to restart execution from the speculative load if a memory-carried dependency is subsequently detected. (i) With the help of some additional hardware it is possible to record which loads cause such ordering violations. Briefly outline how this could be done and how such a record could be used to help improve performance. [3 marks] (ii) Describe why such a scheme may unnecessarily delay the issuing of a load even when the mechanism correctly recalls that the load has led to an order violation between a store and load in the past? [4 marks] (b) Why might it also be advantageous for a superscalar processor to predict whether a particular load will hit or miss in the processor’s L1 data cache? [3 marks] (c) You are asked to design hardware to run artificial neural network applications in a high-performance and energy-efficient manner. Such workloads can typically make good use of many multiply-accumulate (MAC) units operating in parallel and narrow datatypes. Your system is required to support a range of different neural networks that vary considerably in the type of computations they perform. You consider three approaches: (1) to use a multicore processor; (2) to design a single domain-specific accelerator; (3) to compose your design from two or more domain-specific accelerators where each is specialised for different types of neural network. (i) What are the advantages and disadvantages of each approach? [6 marks] (ii) Describe one possible way of organising the multicore processor and a possible choice for the architecture(s) of its individual cores. Briefly justify your design decisions. [4 marks] 5 CST2.2021.9.6 5 Computer Vision (a) Inferring a 3D object shape from shading variation across a surface depends on assumptions about how Lambertian or how specular each area is. For a surface reflectance map ?(i, e, g) having a mixed form, ?(i, e, g) = s(n + 1)(2 cos(i) cos(e) ? cos(g))n 2 + (1 ? s) cos(i) give a range of values for s and n that would arise for: (i) a matte surface, and (ii) a glossy surface. What form of reflectance map ?(i, e, g) describes (iii) a mirror, and what form describes (iv) the lunar surface? (v) Why is ?(i, e, g) as specified above sometimes called the “Face Powder Equation”? (vi) How does the lunar form of ?(i, e, g) explain why the full moon looks like a flat 2D penny in the sky, rather than a 3D sphere like a ping-pong ball? [8 marks] (b) A breakthrough in face recognition accuracy arose when machine learning on big datasets minimised a loss function involving terms like k f(x a i ) ? f(x p i ) k 2 and k f(x a i ) ? f(x n i ) k 2 on triples of embeddings for f(x a i ) (anchor faces), f(x p i ) (positive examples: same face), and f(x n i ) (negative examples: different faces). … Batch DEEP ARCHITECTURE L2 Triplet Loss E M B E D D I N G Figure 2. Model structure. Our network consists of a batch input layer and a deep CNN followed by L2 normalization, which results in the face embedding. This is followed by the triplet loss during training. Anchor Positive Negative Anchor Positive Negative LEARNING Figure 3. The Triplet Loss minimizes the distance between an anchor and a positive, both of which have the same identity, and maximizes the distance between the anchor and a negative of a different identity. in the end-to-end learning of the whole system. To this end we employ the triplet loss that directly reflects what we want to achieve in face verification, recognition and clustering. Namely, we strive for an embedding f(x), from an image x into a feature space R d , such that the squared distance between all faces, independent of imaging conditions, of the same identity is small, whereas the squared distance between a pair of face images from different identities is large. Although we did not a do direct comparison to other losses, e.g. the one using pairs of positives and negatives, as used in [14] Eq. (2), we believe that the triplet loss is more suitable for face verification. The motivation is that the loss from [14] encourages all faces of one identity to be projected onto a single point in the embedding space. The triplet loss, however, tries to enforce a margin between each pair of faces from one person to all other faces. This allows the faces for one identity to live on a manifold, while still enforcing the distance and thus discriminability to other identities. The following section describes this triplet loss and how it can be learned efficiently at scale. 3.1. Triplet Loss The embedding is represented by f(x) ? R d . It embeds an image x into a d-dimensional Euclidean space. Additionally, we constrain this embedding to live on the d-dimensional hypersphere, i.e. kf(x)k2 = 1. This loss is motivated in [19] in the context of nearest-neighbor classifiwhere ? is a margin that is enfnegative pairs. T is the set oftraining set and has cardinality The loss that is being minimX N i h kf(x a i ) ? f(x p i )k 2 2 ? kfGenerating all possible triptriplets that are easily satisfiedin Eq. (1)). These triplets woulding and result in slower convebe passed through the networktriplets, that are active and canproving the model. The followdifferent approaches we use for3.2. Triplet Selection In order to ensure fast convetriplets that violate the tripletmeans that, given x a i , we wantitive) such that argmaxx p i kf(xx n i (hard negative) such that argIt is infeasible to computeacross the whole training set.to poor training, as mislabellewould dominate the hard positivtwo obvious choices that avoid• Generate triplets offline evrecent network checkpointand argmax on a subset of• Generate triplets online. Ting the hard positive/negatmini-batch. Here, we focus on the onlinmini-batches in the order of a fonly compute the argmin and aTo have a meaningful reppositive distances, it needs tonumber of exemplars of any onmini-batch. In our experimentssuch that around 40 faces are sebatch. Additionally, randomlyadded to each mini-batch. This approach treats false matches and failures-to-match as equally bad errors. But their costs are vastly different for a 1-to-1 face verification system (that just makes a ‘yes/no’ decision), versus a face identification system that may need to search a database the size of an entire nation, returning an actual identity. Propose a parameterised loss function for an algorithm that can be tuned for the different costs of the two error types, false matches and failures-to-match. Explain how its parameter(s) should reflect the numbers of potential false match collisions that must be avoided in a large-scale search. [6 marks] (c) A surprising aspect of human vision is the prevalence of quite striking illusions, which cannot be defeated even by being aware of them. Are visual illusions “bugs”, or “features” that should be built into computer vision algorithms? Consider in your answer both the tiling illusion (in which all horizontal lines really are parallel), and the hollow mask illusion below (in which the face always appears convex even when the mask is concave in presentation). [6 marks] 6 CST2.2021.9.7 6 Cryptography (a) CrashHash is a cryptographic hash function invented by your colleague this morning. It zero-pads input X, splits it into n 256-bit blocks x1kx2k . . . kxn = Xk0 (?|X|) mod 256 and then appends a length-indicator block xn+1 = h|X|i, as in the Merkle-Damg?ard construction. It then iterates a 512-bit to 256-bit compression function of the form C(K, M) = EK(M), where EK(M) is a blockcipher E applied with 256-bit key K to 256-bit message block M, as z1 = C(h0i, x1) zi = C(zi?1, xi) (1 < i ? n + 1) The value H(X) = zn+1 is the hash value returned. Show that CrashHash is not collision resistant, even if E is replaced with an ideal cipher. [6 marks] (b) (i) How can one modify an implementation of the DES encryption function to obtain the decryption function? [4 marks] (ii) Name two other features of DES that made it well suited for hardware implementation. [2 marks] (c) Your colleague has generated a set of m = 200 000 RSA key pairs that include a modulus ni = piqi where pi and qi are 1536-bit prime numbers (for 1 ? i ? m). The corresponding pi and qi values were discarded immediately after key generation and are no longer available. Due to a bug in your colleague's key-generation software, two types of fault have appeared in a random subset of the issued key pairs: (i) For some key pairs i we have pi = qi . (ii) For some key pairs i there exists another key pair j in that set with pi = pj and i 6= j. Suggest practical tests that can identify all public keys affected by either of these problems and state how often the algorithms involved have to be executed for this task. [4 marks] (d) Calculate 72000 mod 100 by hand. [4 marks] 7 CST2.2021.9.8 7 Denotational Semantics Say whether the following statements are true or false with justification. You may use standard results provided that you state them clearly. (a) For all PCF types ? and terms M ? PCF? , if [[M]] = ?[[?]] then M ?=ctx ?? : ? . [4 marks] (b) For all PCF types ? and terms M ? PCF? , if [[M[] = ?[[?]] then M 6?? . [4 marks] (c) For all PCF types ? and terms M ? PCF? , if M ?=ctx ?? : ? then M 6?? . [4 marks] (d) For all PCF types ? and terms M ? PCF? , if M 6?? then M ?=ctx ?? : ? . [Hint: Recall the extensionality properties of contextual equivalence.] [4 marks] (e) For all PCF types ? and terms M ? PCF? , if M ?=ctx ?? : ? then [[M]] = ?[[?]]. [Hint: Recall the parallel-or test functions.] [4 marks] 8 CST2.2021.9.9 8 Hoare Logic and Model Checking We consider the CTL temporal logic over atomic propositions p ? AP: ? ? StateProp ::= ? | > | ¬? | ?1 ? ?2 | ?1 ? ?2 | ?1 ? ?2 | p | A ? | E ?, ? ? PathProp ::= X ? | F ? | G ? | ?1 U ?2. (a) Alice (a), Bob (b), and Carol (c) are bank tellers. They sit at their till (t), until they need to give money to their customers, which they can do in gold (g) or silver (s) coins, which are stored in two different vaults. Each vault needs two tellers to turn keys simultaneously, but if it determines that there are more than two tellers present, it locks itself and phones the police. Once they have retrieved the coins, they can return with coin (r). This yields atomic propositions AP = Pers × Loc, where Pers ::= a | b | c and Loc ::= t | g | s | r, so that for example a state labelled with {at, bs, cr} is one where Alice is at her desk, Bob is waiting to open the silver vault, and Carol is returning with coin. Give CTL formulas for (i) Alice repeatedly serves clients with coins. [2 marks] (ii) When Bob picks a vault, he stays there until it gets opened. [2 marks] (iii) Carol is always able to serve clients with coins. [2 marks] (iv) The vaults never lock. [2 marks] (b) Explain why Carol’s property cannot be expressed in LTL. [2 marks] (c) A chemist is trying to determine what can be synthesised from the chemicals they have. They know all possible reactions: 2 H2 + O2 ? 2 H2O, C + O2 ? CO2, etc. (i) Describe a model of reactions from given starting quantities. [3 marks] (ii) Keeping track of the exact amount of chemicals is challenging, so the chemist looks only at whether each is present. Describe such an abstract model, and give a simulation relation between the two models. [4 marks] (iii) State, for each of these two properties, which of the models (i) and (ii) is such that if the property holds for it, then it holds for the other: 1/ that dangerous chemicals like CO are never synthesised; 2/ that desirable chemicals like pure gold (Au) can be synthesised. Explain why. [3 marks] 9 CST2.2021.9.10 9 Information Theory (a) A long-term and self-replicating data storage system based on DNA sequences is being developed. Advantages include huge information density (? 1019 bits/cm3 ) and extreme persistence: dinosaur DNA can still be extracted from fossils. The letters A,C,G,T each occur with equal probability, independently, without sequence constraints. Consider sequences consisting of 100 such letters. (i) How many sequences are possible, and with what probabilities? [2 marks] (ii) Random variable X selects such a sequence. Calculate H(X), the entropy of X, starting from Shannon’s definition. [2 marks] (iii) Sequence replication may be corrupted such that the last two letters are reproduced randomly in the post-replication sequences, denoted Y . What is the conditional entropy H(X|Y ), and what is the mutual information I(X; Y ) for this error-prone replication process? [4 marks] (b) Financial markets generate daily asset valuations like the time-series f(t) in the left panel, reflecting the dynamics of greed and fear. But underlying such fluctuating indices there may exist meaningful trends, such as a business cycle (right panel). Write an auto-correlation integral that can extract the coherent quasi-periodic signal on the right from noisy valuations f(t), and explain how computing the Fourier transform F(?) of f(t) makes it efficient. [5 marks] 0 0 Figure a sine wave in noise and b autocorrelation (c) Brain tissue contains about 105 neurones per mm3 , and each neurone has a single output axon whose length r (in dimensionless units) before terminating at synapses to other neurones has probability density distribution p(r) = e ?r . 0 1 2 3 r 0 1 p(r ) = e ?r Note: Z ? 0 e ?r dr = 1 (i) Define differential entropy h for continuous random variables in terms of general probability density distribution p(x), and then calculate the value of h in bits for this axonal length distribution p(r) = e ?r . [5 marks] (ii) If the axon’s branching terminals make altogether about 1,000 synapses (connections) with different neurones within the axonal tree’s 1 mm3 volume, uniformly distributed, roughly how many bits of entropy describe the uncertainty of whether a neurone gets such a connection? [2 marks] 10) Suppose you have a randomised approximation algorithm for a maximisation problem such that, for any > 0 and any problem instance of size n, the algorithm returns a solution with cost C such that Pr[C ? (1 ? 1/) · C ? ] ? 1/n · exp(?1/), where C ? is the cost of the optimal solution. Can you use your algorithm to obtain a PTAS or FTPAS? Justify your answer. [6 marks] (b) We consider the following optimisation problem. Given an undirected graph G = (V, E) with non-negative edge weights w : E ? R +, we are looking for an assignment of vertex weights x : V ? R such that: (i) for every edge {u, v} ? E, x(u) + x(v) ? w({u, v}), (ii) P v?V x(v) is as small as possible. (i) Design a 2-approximation algorithm for this problem. Also analyse the running time and prove the upper bound on the approximation ratio. Note: For full marks, your algorithm should run in at most O(E 2 ) time. Hint: One way to solve this question is to follow the approach used by the greedy approximation algorithm for the VERTEX-COVER problem. [8 marks] (ii) Can this problem be solved exactly in polynomial-time? Either describe the algorithm (including a justification of its correctness and why it is polynomial time) or prove that the problem is hard via a suitable reduction. [6 marks] 2 CST2.2021.8.3 2 Bioinformatics (a) Compute the nearest neighbour phylogeny from the four species (B,M,H,O) distance matrix. B M H O B 0 5 6 4 M 5 0 3 2 H 6 3 0 2 O 4 2 2 0 [6 marks] (b) Can we always build a phylogenetic tree from a distance matrix? [2 marks] (c) Derive the Burrows-Wheeler (BWT) transform of the string ‘TAGTATA’. How can the transform be reversed? Comment on the use of BWT for a genome sequence that has many repeated substrings. [4 marks] (d) Three analysis techinques for gene expression data (microarray) are hierarchical clustering, k-means and Markov clustering. Describe the structure of a set of experimental results that could be analysed by all three techniques and state what each form of analysis might identify and any additional inputs required. [4 marks] (e) Discuss how a Hidden Markov Model can be used to identify different gene parts and how many sequences might be needed to compute reliable transition probabilities. [4 marks] 3 CST2.2021.8.4 3 Comparative Architectures (a) Some VLIW processors exploit fine-grain multithreading and SIMD execution units. (i) What benefits could adding support for fine-grain multithreading to a VLIW processor provide? [4 marks] (ii) Why might a simple round-robin thread schedule be inefficient and how could we improve the schedule? [2 marks] (iii) Assuming the VLIW processor has taken full advantage of fine-grain multithreading with a simple round-robin thread schedule, what changes to the processor might an optimised thread schedule require to ensure programs continue to execute correctly? [4 marks] (iv) Why might it be useful to include SIMD functional units when a VLIW processor can already specify independent operations to be executed in parallel? [4 marks] (b) Some VLIW processors support variable-length bundles of independent instructions. (i) Why is this a useful feature and how could it be supported? [2 marks] (ii) What costs would be incurred and additional logic needed to support this feature? [4 marks] 4 CST2.2021.8.5 4 Computer Vision (a) In the context of automated detection and interpretation of affective expressions using FACS (Facial Action Coding System), define the following concepts: (i) facial muscle action unit (AU) (ii) action descriptor (AD) (iii) valence (iv) arousal (v) “Pan-Am smile” (vi) cross-cultural universal [6 marks] (b) Gabor wavelets offer a unifying framework for many tasks in computer vision, including edge detection, finding facial features, and pattern matching. The complex wavelet components (upper row) are parameterised to approximate the convolution kernels for computing 1st and 2nd derivatives (lower row, given as functions of x but rotatable in images f(x, y) into functions of y as well): Re{e?x 2 e i3x} = e?x 2 cos(3x) 2nd finite difference kernel: ?f ??[xj ] ? ?f[xj?1] + 2f[xj ] ? f[xj+1] Im{e?x 2 e i3x} = e?x 2 sin(3x) 1st finite difference kernel: f ? [xj ] ? ?f[xj ] + f[xj+1] Re{e?x 2 e i3x} = e?x 2 cos(3x) 2nd finite difference kernel: ?f ??[xj ] ? ?f[xj?1] + 2f[xj ] ? f[xj+1] Im{e?x 2 e i3x} = e?x 2 sin(3x) 1st finite difference kernel: f ? [xj ] ? ?f[xj ] + f[xj+1] Explain how Gabor wavelets can estimate the gradient vector field ?~ f(x, y) in edge detection, extracting both edge strength and edge direction. Also describe how they can be used in a demodulation network to localise facial features. Identify one application of Gabor wavelets in pattern matching. [5 marks] (c) What can we learn from the perceptual experiments of the Swedish psychologist Johansson, involving sparse dot patterns such as shown on the right? How might his findings be useful in computer vision for data fusion, integration of motion cues in object recognition, and general aspects of scene understanding? [4 marks] (d) Biological neurones are notoriously noisy, are apparently random in their connections and their firing patterns, and sluggish, with maximum firing rates around 100 Hz. Yet biological vision systems are wonderfully capable. Is there really any need for computer vision systems to use double precision arithmetic and GHz clock speeds? Give three examples of tasks in machine vision whose execution appears to require double precision arithmetic and high FLOPS, and for each example, explain this contrast with biological solutions. [5 marks] 5 CST2.2021.8.6 5 Cryptography (a) Consider the following two alternative definitions of a MAC function, which receives as input an (n · L)-bit long message of the form M = M1kM2k . . . kML with Mi ? {0, 1} n and a private key K ? {0, 1} n picked uniformly at random, returning a tag T ? {0, 1} n . Show how neither definition provides the security property of existential unforgeability. (i) Let F be an n-bit to n-bit pseudo-random function. Return the message tag T = FK(M1) ? FK(M2) ? · · · ? FK(ML). [4 marks] (ii) Let F be a (2n)-bit to n-bit pseudo-random function. Return the message tag T = FK(h1ikM1) ? FK(h2ikM2) ? · · · ? FK(hLikML). [6 marks] [Notation: k = concatenation of bit strings, ? = bit-wise XOR, hii = n-bit binary representation of non-negative integer i.] (b) Your colleague proposes to construct an authenticated encryption scheme that encrypts a plain-text message M by first calculating the message authentication code CMACK(M) = T, and then forms the ciphertext by encrypting MkT using CFB mode with initial vector IV = EK(T), using the same key and blockcipher EK. Does this construction offer CCA security? Why or why not? [5 marks] (c) Given a block cipher EK with n-bit block size, where n ? 64 is a power of two, how can you use EK to construct a strong pseudo-random permutation for n 2 -bit blocks? [5 marks] 6 CST2.2021.8.7 6 Denotational Semantics A right adjoint of a monotone function f : P ? Q between posets is a monotone function g : Q ? P such that idP v g ? f and f ? g v idQ. Let f : P ? Q be a monotone function with a right adjoint g : Q ? P. (a) For p ? P and q ? Q, prove that f(p) vQ q if, and only if, p vP g(q). [4 marks] Let h : P ? P and ` : Q ? Q be monotone functions such that f ?h = `?f : P ? Q. (b) Prove that if h has a least pre-fixed point fix (h) then f(fix (h)) is a least pre-fixed point of `. [8 marks] Further assume that g ? f = idP , in which case f is said to be an embedding and g a projection. (c) Prove that if ` has a least pre-fixed point fix (`) then g(fix (`)) is a least pre-fixed point of h. [8 marks] 7 E-Commerce Over the years you developed a friendship with Alice, the owner-operator of a high quality coffee shop. As a result of recent government regulations in relation to managing the current pandemic, Alice has decided to close the retail aspect of her business and move it online. She turns to you for help as you are the friendly neighbourhood Computer Scientist. (a) Discuss four aspects, from a legal standpoint, of moving her business online that Alice needs to consider that would be different from operating a retail location. [4 marks] (b) Moving online enables Alice to consider alternative business models to the traditional e-commerce merchant model. Discuss two business models that might be relevant to her coffee business highlighting both the business activity and financial model. [6 marks] (c) Choose one of the business models you identified above and discuss what activities Alice might need to use to implement the model, along with the metrics she could use to measure if she is being successful or not. [10 marks] 7 CST2.2021.8.8 8 Hoare Logic and Model Checking Consider commands C composed from assignments X := E (where X is a program variable, and E is an arithmetic expression), heap dereference X := [E], heap assignment [E1] := E2, 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. We write align(t, s) for the smallest multiple of s larger than t. Let block(t, 0) = emp, block(t, n + 1) = (?t 0 . t 7? t 0 ) ? block(t + 1, n). (a) Explain why the following postcondition for an allocator that returns aligned blocks is incorrect, and propose a fix. {block(B, E ? B) ? 1 ? S} if align(B, 2 S ) + 2S < E then (R := align(B, 2 S ); B := B + 2S ) else R := 0 block(B, E ? B) ? (R 6= 0 =? (block(R, 2 S ) ? R = align(R, S))) [3 marks] (b) With this specification, allocations cannot be chained, as in Calloc; Y := X; Calloc. Explain why, and propose a fix. [2 marks] (c) Strengthen the precondition just enough to guarantee the success of allocation (so that R 6= 0 =? is not needed anymore). [2 marks] (d) Consider the following representation predicate for lists of free blocks of size 2S : freelist(t, S) = (t = null ? emp) ? ?t 0 . t = align(t, 2 S ) ? t 7? t 0 ? block(t + 1, 2 S ? 1) ? freelist(t 0 , S) Give a loop invariant, and precisely but informally explain why it is preserved, for this "add the contents of a block into a free list" triple: {B = align(B, 2 S ) ? block(B, E ? B) ? 1 ? S ? L = null} while B + 2S < E do [B] := L; L := B; B := B + 2S {block(B, E ? B) ? freelist(L, S)} [7 marks] (e) Give a loop invariant, and precisely but informally explain why it is preserved, for this "coalesce blocks of a size S free list into a size S + 1 free list" triple: {freelist(L1, S) ? L2 = null ? D = 0} while D = 0 do if L1 = null then D := 1 else X := [L1]; if X = null or X mod 2 S+1 6= 0 then D := 1 else Y := [X]; if X + 2S 6= Y then D := 1 else [X] := L2; L2 := X {freelist(L1, S) ? freelist(L2, S + 1)} [6 marks] Engineering & Technology Computer Science COMPUTING 101 Share QuestionEmailCopy link Comments (0)