[10 marks for sensible discussion of correctness/termination along these lines, including clear correlation with the code; partial credit for partial discussions.]
int first, second, k;
if (n < 2)
error ("n too small"); /* bonus! */
if (A[1] >= A[2])
first = 1, second = 2;
else
first = 2, second = 1; /* P2 established */
for (k = 3; k <= n; k++) /* P(k-1) established */
if (A[k] > A[second])
if (A[k] > A[first])
second = first, first = k;
else
second = k; /* Pk established */
return second; /* Pn established */
[10 marks for clear and correct algorithm; 6 for implementation, with trivial `typos' ignored and 2 marks deducted for each other error.]The loop is entered n-2 times, doing one comparison each time and a second comparison whenever second is updated; there is one comparison outside the loop, so the number of comparisons is (a) in the best case, n-1, for example when the objects are initially sorted largest-first, and (b) in the worst case, 2n-3, for example when the objects are initially sorted smallest-first.
[2 marks for each. Total mark: 30]Comments: Unseen example, of similar difficulty to other coding exercises discussed during the module. Students' preferred language may [well] be more like QBasic than C! Note: it is certainly possible to find second largest in n-2 + ceiling(lg n) comparisons -- run a Wimbledon-style KO tourney, then run a small KO tournament among those who lost to the winner.
[Bookwork; 10 marks]Quicksort: The objects are `partitioned' [for example, using the DNF algorithm] into those less than, equal to, or greater than some `pivot' element; each partition is then sorted using quicksort recursively. Best case: the partitions are of equal size every time, so that the maximum partition `depth' is O(log n), each object is compared with the pivot once at each depth, and so the work done is O(n log n). Worst case: one partition is empty each time, so only the pivot is removed from the set of objects [it turned out to be the largest or smallest object], and the total work done is clearly O(n2). Average case: each partition is a `reasonable' fraction of the whole, so the maximum partition `depth' is again O(log n) [though with a larger constant than in the best case], and the total work O(n log n).
[All bookwork; 2 marks for description and each case, total 8]Insertion sort: Assume, for a loop invariant, that the first k objects have been sorted, where initially k = 0. To sort the first k+1, find by the `binary chop' algorithm where in the first k the (k+1)th should go, and create space for it by moving up a place all the objects [perhaps none] between that position and the (k+1)st. Best case: no moves are needed, when the objects are already in the right order, so only the binary chops are needed, total work O(log 1 + log 2 + ... + log n), or O(n log n). Worst case: the next object always sorts to the front, when the objects are initially anti-sorted, and the work needed is dominated by having to move every already-sorted object at every stage, total work O(1 + 2 + ... + n), or O(n2). Average case: the next abject sorts to the middle, so on average half the objects move at each stage, and the total work done is half that for the worst case, so still O(n2).
[All bookwork; 2 marks for description and each case, total 8]To mitigate the worst-case behaviour of `quicksort', we need to take more care over choice of pivot -- a typical technique would be to choose the median of three pseudo-randomly chosen objects. Also, the recursion and other book-keeping of `quicksort' become inefficient when there are few objects, so another idea is to stop `quicksorting' when the partitions become small and instead to do a `clean-up' pass over the objects with a different sorting technique designed to be efficient with a nearly-sorted array, such as insertion sort.
[Bookwork; 4 marks. Total of 30 marks available for the question.]
[Total mark 30. Unseen problem of a familiar type -- slightly easier than those done for coursework and slightly harder than those tackled in problem classes.]
| ... | b | b | 1 | 0 | 1 | b | 1 | 0 | 0 | 0 | 1 | 0 | 0 | ... | 1 | b | ... |
So we get the following FSM [blanks `can't happen']:
| next state | write symbol | direction | |||||||
|---|---|---|---|---|---|---|---|---|---|
| current state \ read symbol | b | 0 | 1 | b | 0 | 1 | b | 0 | 1 |
| 0 [start] | 2 | 0 | 1 | b | 0 | 1 | L | R | R |
| 1 | 3 | 1 | 1 | b | 0 | 1 | L | R | R |
| 2 | 8 | 2 | b | b | L | L | |||
| 3 | 5 | 3 | 4 | b | 0 | 0 | L | L | L |
| 4 | 6 | 4 | 3 | b | 0 | 1 | L | L | L |
| 5 | 7 | 5 | 5 | 0 | 0 | 1 | R | L | L |
| 6 | 7 | 6 | 6 | 1 | 0 | 1 | R | L | L |
| 7 | 0 | 7 | 7 | b | 0 | 1 | R | R | R |
| 8 [halt] | |||||||||
[Marks: 10 for general design and structure, pro rata for faulty attempts, trivia ignored in this section; 3 for description and 2 for sensible design of tape layout; 10 for detailed description of TM, either as matrix or as state transition diagram, 2 marks deducted for each missing or seriously incorrect state, but trivia ignored; 5 for accuracy, 1 deducted for each error; total 30. Unseen, but TMs of similar difficulty seen during module.]
[Each of these is a minor twist on an example discussed in lectures. Total available marks: 30]