G12FCO -- Formal Computation

Mock Exam

Introductory Notes:

This set of practice questions has been devised completely independently of the actual exam, and you should have no expectation that topics selected here are thereby made either more or less likely to appear on that exam. This set conforms to the general structure that there are two questions on each of the major strands of the module, that half of them are `problems' and the other half `bookwork', of which one is of an `essay' nature. These questions have not been moderated in any way, so it is more likely than for the actual exam that it contains misfeatures.

DEPARTMENT OF MATHEMATICS
Module G12FCO -- Formal Computation
Time allowed: TWO hours
Marks will be awarded for the best FOUR answers
Silent, programmable and single-line calculators are permitted
but will be of less use than a teddy-bear in this exam

Given an odd positive integer r, consider the following fragment of code:
```
		p = 1, q = 1, n = r
		while n /= 0 do
		   if n > 0
		     then n = n - p, p = p + 2
		     else n = n + q, q = q + 2
		   endif
		endwhile
	
```
Show that this code must terminate, and that when it does so the values (p-q)/2 and (p+q-2)/2 are factors of r. What happens if r is (a) negative; (b) even?
[Hint: You may find it helpful to follow through the cases r = 7, 9 and 15 in detail, and to consider the sums 1+3+5+... of the values taken on by p and q.]
Describe the Dutch National Flag problem, and an algorithm for solving it. Explain how this algorithm can be used to implement the Quicksort sorting procedure. Comment on the efficiency of this procedure, and what steps can be taken to improve it.
Write an essay on Feasibility.
Possible topics include [but are not confined to]: polynomial vs. exponential operation counts, the class P of decision problems, the class NP and completeness, Cook's theorem, the hierarchy of complexity classes. Literary merit will be taken into account, and an essay which covers a few topics well will be preferred to one which consists of disconnected jottings about many.
You are given a network of roads and villages and an integer k. The Bounded Degree Spanning Tree decision problem is to determine whether or not there is a subset of the roads which connects all the villages, but such that no more than k roads leave any village. Show that Bounded Degree Spanning Tree is NP-complete. [Hint: Consider the case k=2.]
Design a Turing machine to the following specification: its tape contains a [non-zero] number of consecutive X's and is otherwise blank; the read head is initially over the rightmost-X; and the machine is to place on the tape the binary representation of the number of X's. [Your solution need not preserve the X's.]
What is meant by a Universal Turing machine [UTM]? Sketch one method by which a UTM can be constructed. [You need not describe the resulting machine in great detail, but you should indicate the general nature of its operating cycle.]
Show that it is possible to construct a [single tape, single head] UTM which never changes a non-blank symbol on its tape. [You may quote general results about minimal computers, as long as they are clearly stated in your exposition.]

top of page

G12FCO home page. border=0

Solutions.