Computation Theory ExplainShow that the function giving the next state of a register machine in terms of the current state is primitive recursive. (You may assume the existence of primitive recursive functions for coding any n-element list of numbers (x1, . . . , xn) as a number [x1, . . . , xn] (for each n), and for extracting the head x1 and the (coded) tail [x2, . . . , xn] from such a coded list.) [8 marks] Deduce that every register machine computable partial function is partial recursive.

What is a pipeline bubble and why might a branch instruction introduce one or more bubbles? [4 marks] (b) Explain, with the aid of an example, how conditional instructions may be used to reduce the number of bubbles in a pipeline. [4 marks] (c) What is the difference between branches, interrupts, software interrupts (initiated by a SWI instruction on the ARM) and exceptions? [8 marks] (d) What is an imprecise exception and why might a processor designer prefer it to a precise exception mechanism? [4 marks] 2 CST.2001.12.3 3 Digital Communication I Information is to be conveyed from A to B using automatic repeat request (ARQ), forward error correction (FEC), and lossless compression. (a) Explain the terms ARQ, FEC and lossless compression. [5 marks] (b) If we consider each of these functions to be operating at different protocol layers, what would be the most sensible ordering of the layers, and why? [5 marks] (c) Suppose: The underlying bit channel has a capacity of B, a delay and error rate 0. The compression ratio is C < 1. The FEC has rate R < 1 and given an error rate 0 provides an error rate 1 (which is detected). The ARQ protocol has a window size of W. At what rate can the information be conveyed? [Hint: Consider when retransmissions are made.] State any assumptions you make about the operation of the ARQ protocol. (a) Describe the limitations of human vision in terms of: (i) spatial resolution (ii) luminance (iii) colour and explain the implications that each of these limitations has on the design of display devices. [10 marks] (b) In image compression we utilise three different mechanisms to compress pixel data: (i) mapping the pixel values to some other set of values (ii) quantising those values (iii) symbol encoding the resulting values Explain each mechanism, describe the way in which it helps us to compress the image, and describe in what way it affects the visual quality of the resulting (decompressed) image when compared with the original. [10 marks] 5 Business Studies You are inspired to make your fortune by starting a distance learning enterprise to teach the world Computer Science, using multimedia lessons distributed over the Web. Write notes for a business plan for the potential investors, under the following headings: (a) The market. [5 marks] (b) The team required. [5 marks] (c) Outline overall project plan. [5 marks] (d) Business model, with a rough estimation of capital expenditure and profitability. (a) Outline the main innovations that are in Simula 67 but were not in Algol 60, paying particular attention to Simula Classes. [6 marks] (b) Illustrate how Simula can be used to simulate a small restaurant with six tables, two waiters and small groups of customers arriving at random intervals. You need specify only the classes you would define. Most of the algorithmic details may be omitted. [6 marks] (c) Discuss to what extent Simula has been made redundant by the development of modern object-oriented languages such as Java. [8 marks] 7 Compiler Construction Consider a language J which has Java-like syntax nested definitions of procedures within other procedures local variables (with static binding) raising and handling of named, parameterless exceptions Explain a possible run-time data structure which a compiler for J might use. [10 marks] A nave user of such a language suggests that the resultant compiled code will spend a significant fraction of execution time searchingboth finding the store location corresponding to the use of a variable name and finding the exception handler corresponding to the raising of a given exception name. Determine with justification whether this is so for your run-time data-structure proposed above. [4 marks] Now instead suppose a simple interpreter for J is written, so that searches for variable (or exception) names search the appropriate environment for the variable value or exception handler code. To what extent are these searches bounded by (a) the number of variables or exceptions in the program or (b) the dynamic or static nesting of procedures?

HERE IS THE CODE FOR THE BOARD CLASS:

import java.util.Random; public class Board { private int rows; private int columns; private int num_rows; // Number of rows private int num_columns; // Number of columns private int num_Boats; // Number of boats private Battleboat[] boats; // Array of the Battleboats private Cell[][] board; // Board made up of Cells (2-D) private boolean debugMode; // Boolean representing debug mode being on/off

// TODO Board constructor initializes everything public Board(int size, boolean debugMode){ // Set basic attributes this.rows = 0; this.columns = 0; this.debugMode = debugMode; }

// TODO Returns: // 0 if out of bounds // 1 if missed // 2 if hit // 3 if island // -1 for anything else public int guess(int r, int c){ // Out of bounds if(true){ return 0; }

// Miss else if(true){ return 1; }

// Hit else if(true){ return 2; }

// Island else if(true){ return 3; }

// Penalty return -1; }

//TODO: Updates the boat cell since it is independent of the cells in the board public void updateBoatCell(int r, int c){

}

//TODO: write a function that calculates the number of unsunk boats public int unsunkBoats(){ return 0; }

// Prints out the board // Will only print debug mode if debug mode is toggled public void display(){ if(this.debugMode) { for (Cell[] row : this.board) { for (Cell col : row) { System.out.print(" " + col.get_status() + " "); } System.out.println(); } } else{ for(Cell[] row : this.board){ for(Cell col : row){ if(col.get_status() == 'H' || col.get_status() == 'M' || col.get_status() == 'I'){ System.out.print(" " + col.get_status() + " "); } else{ System.out.print(" - "); } } System.out.println(); } } }

// Toggles the debug printing mode public void toggleDebugMode(){ if(!this.debugMode){ this.debugMode = true; } else{ this.debugMode = false; } } } HERE IS THE CODE FOR THE CELL.JAVA CLASS FOR ADDITIONAL UNDERSTANDING:

public class Cell { public int row; // Integer representing the row where the cell resides public int col; // Integer representing the column where the cell resides private char status; // Status of the cell

// Cell constructor initializes cell variables public Cell(int row, int col, char status){ }

// Returns the status of the cell public char get_status(){ return '0'; }

// Sets the status of the cell public void set_status(char c){ if(c != 'B' && c != 'H' && c != 'M') { c = ' '; set_status(status); } this.status = c; }

// Returns the row in which the cell resides public int getRow(){ this.row = row; return 0; }

// Returns the column in which the cell resides public int getCol(){ this.col = col; return 0; } } HERE IS THE CODE FOR THE BATTLEBOAT.JAVA CLASS FOR ADDITIONAL UNDERSTANDING:

import java.util.Random; public class Battleboat {

private int size; // Size of the boat private boolean orientation; // Orientation of the boat (true for vertical, false for horizontal) private Cell[] spaces; // Cell array representing the boat spaces

// TODO Battleboat constructor initializes everything public Battleboat(){ orientation = Math.floor(Math.random()*2) == 1; size = 3; spaces = new Cell[size]; }

// TODO Returns the orientation of the boat public boolean get_orientation() { return orientation; }

// TODO Returns the size of the boat public int get_size(){ return size; }

// TODO Returns the cells of the boat public Cell[] get_spaces() { return spaces; }

// TODO Need to set Cells public void setCells(Cell[] cells){ } } HERE IS THE CODE FOR THE GAME.JAVA CLASS FOR ADDITIONAL UNDERSTANDING:

import java.util.Scanner;

public class Game {

public static void main(String[] args) { int score = 0; boolean debugMode = true;

Scanner sc = new Scanner(System.in); System.out.println("Enter board size dimension (between 3 and 7 inclusive): "); int size, r, c; while(true){ size = sc.nextInt(); if(size < 3 || size > 7){ System.out.println("Invalid board dimensions"); System.out.println("Enter board size dimension (between 3 and 7 inclusive): "); } else{ break; } }

Board board = new Board(size, debugMode); int unsunkBoats = board.unsunkBoats();

System.out.println("Boats placed on board: " + unsunkBoats + " ");

System.out.println("Would you like debug mode to be enabled ? Please enter 'd' if so, otherwise enter anything else : "); String debug = sc.next(); if (debug.equals("d")){ board.toggleDebugMode(); }

while(unsunkBoats > 0){ board.display(); System.out.println(); System.out.println(); System.out.println("Enter guess for row: "); r = sc.nextInt(); System.out.println("Enter guess for column: "); c = sc.nextInt();

int result = board.guess(r, c); score = updateScore(score, result);

unsunkBoats = board.unsunkBoats();

System.out.println("Unsunk boats left: " + unsunkBoats + ", score: " + score); System.out.println(); }

System.out.println("Final score: " + score); }

public static int updateScore(int score, int result) { if (result == 0) { System.out.println("Penalty: Out of Bounds"); return score + 2; } else if (result == 1) { System.out.println("Miss"); return score + 1; } else if (result == 2) { System.out.println("Hit"); return score + 1; } else if (result == 3) { System.out.println("Penalty: Attacking an Island"); return score + 2; } else { System.out.println("Penalty: Redundant Guess"); return score + 2; } } }

Describe the facilities provided in Modula-3 for abstraction through object inheritance and partial revelations of opaque types. [8 marks] Illustrate your answer by reference to the Trestle toolkit, mentioning the relationship between VBT.T, VBT.Leaf, VBT.Split, Filter.T and their sub-types. [4 marks] Explain how overriding methods such as mouse, position and keyboard in a sub-type of VBT.T can be used to define a new class of window. [4 marks] How is initialisation of super-types handled? [4 marks] 3 Software Engineering Describe the particular difficulties involved in constructing very large software systems, as observed by Curtis et al. List some of the root causes of these difficulties. [7 marks] Write an essay on the role of testing in a software project. The essay should describe testing's purpose and limitations, and touch upon black-box, white-box and acceptance testing, ultra-high reliability and beta-testing. (A mere list of definitions will receive little credit.) [13 marks] 2 CST.95.11.3 4 Compiler Construction Outline how minimum cost code can be compiled from a parse tree using rules that consist of tree template replacements, costs and corresponding code. Illustrate your answer by considering the translation of the expression Add(Add(K1, K2), Add(K3, K4)) using the following rules: #1 Ri <- Add(Ri, Rj) cost: 2 code: ADDR Ri,Rj #2 Ri <- Add(Ri, Kc) cost: 3 code: ADDI Ri,c #3 Ri <- Kc cost: 2 code: LOADI Ri,c #4 Ri <- Add(Ri, Add(Rj, Kc)) cost: 4 code: ADDRI Ri,Rj,c In your answer you should derive the finite state machine needed for the efficient matching of these four rules, and you should also give the cost and resulting translation of the given example expression. [15 marks] Briefly discuss in what ways this algorithm may fail to generate optimum code when used in a compiler. [5 marks] 3 [TURN OVER CST.95.11.4 5 Data Structures and Algorithms What is a priority queue? Explain the data structure known as a heap and document how a heap is stored in a simple linear block of memory. [4 marks] If a heap stores N items, describe how it can be viewed as an almost-balanced binary tree. What difference can there be between the greatest and least lengths of paths from the root of the tree to a leaf? What operations must be performed to move from one node in the tree to (a) its parent and (b) its offspring? [5 marks] Describe, and estimate the costs of, procedures to (a) insert a new item into an existing heap; (b) delete the topmost item from a non-empty heap; (c) starting from an array holding N items in arbitrary order, rearrange those items so that they form a heap, taking time less than that which would be needed if the items were just inserted into the heap one after the other. [6 marks] A stable sorting method is one where items whose keys compare as equal will appear in the output in the same order that they appeared in the input list. Would a heap sort based on the algorithms you have documented be stable? Justify your answer. [5 marks] 6 Topics in Artificial Intelligence Give some reasons why some tasks are suited to being solved by using constraints. Illustrate your answer with examples of such tasks and the methods by which constraints are used to solve them. [20 marks] 7 Operating System Foundations Consider the operation of a scheduler in a system where there are system level and user level processes. User processes may be IO bound or CPU bound and may have user controlled (negative) priority. Describe the data structures that the scheduler might use, including parts of process descriptors that the scheduler would operate on. [10 marks] Describe in detail the circumstances under which the scheduler would be entered and for each different circumstance outline a scheduling algorithm that might be used.