School of Computer Science题量大约四五道，与Mock Examination难度相当
欢迎随时预定学霸大神
Answer ALL questions. The paper will be marked out of 60, which will be rescaled to a mark out of 100.
Question 2 : Context-free Languages
Question 3 : Models of Computation
Question 4 : Decidability and Complexity
(a) Following a spate of malware problems, several companies are reviewing their security
procedures.
(i) The manager of Very Careful Ltd. instructs their IT team to write a program
that can determine whether an app is able to corrupt data. Can this instruction
be carried out? Explain your answer.
(ii) The manager of Somewhat Careful Inc. instructs their IT team to write a
program that can determine whether an app’s code contains the signature (the
essential part of the code) of a known virus. Can this instruction be carried
out? Explain your answer.
(b) The following program takes as input a nonempty array p of a’s and b’s of length
n > 0.
elapse 2 seconds;
for (int i=0; i<n-1; i++){
elapse 1 second;
if (p[i]==’b’ && p[i+1]==’a’) {
p[i+1] = ‘b’;
elapse 1 second;
}
}
For example, if the input is abab, then the output is abbb. All the running time is
given by the elapse instructions.
Give the best case, worst case, and average case running time for length n = 3. For
the average case, assume that each entry is independent, with a and b equally likely.
Show that the worse case running time is O(n).
[9 marks]
