answer the question clearly

(a) What is the von Neumann bottleneck and why can it limit performance on today's RISC machines? [4 marks] (b) What computer architecture techniques are used to mitigate the effects of the von Neumann bottleneck on RISC machines as compared to early computers like EDSAC? [4 marks] (c) How do RISC machines enforce memory protection for applications with disjoint data sets? [4 marks] (d) What is segmented addressing (e.g. as used on x86 machines)? [4 marks] (e) If non-volatile random access memory had similar performance and cost to DRAM, how would this change the memory hierarchy?

(a) Explain the terms amortized analysis and aggregate analysis, highlighting the difference between them. [3 marks] (b) Assume that the following two classes, which implement the standard stack (last-in first-out) and queue (first-in first-out) data structures, are available. class Stack class Queue void push(Item x) void enqueue(Item x) Item pop() Item dequeue() Boolean isEmpty() Boolean isEmpty() (i) A Multistack class is derived from Stack with the addition of two methods: a void multipush(Itemlist l) that takes a list l of items and pushes each of the items onto the stack (each action of extracting an item from the list and pushing it onto the stack has constant cost), and a void multipop(int m) that takes an integer m and pops that many items off the stack (raising an exception if there were fewer, but don't worry about that). Is it true or false that, given an arbitrary sequence of n Multistack operations starting from an empty Multistack, each operation in the sequence has amortized constant cost? Justify your answer in detail. [5 marks] (ii) Provide an implementation of class Queue using no other data structures than Item, Boolean, int and Stack. The amortized running time of each Queue method must be constant. (Note that you may only use the Stack as a black box: you are not allowed to access its internal implementation.) [7 marks] (iii) Using the potential method, prove that the amortized running time of all your Queue methods from part (b)(ii) is indeed constant. [5 marks]

Consider the following claim: "The cross-product trick can be used as a plug-in substitution for the comparison operation between two arguments that gives a three-way result (namely <, > or =). Therefore, given an arbitrary set of 2D vectors all starting from the origin, I can sort them in order of increasing polar angle, from 0 to 2, without computing any angles, merely by applying a standard sort algorithm with the comparison operation replaced by the crossproduct trick". (i) Explain the "cross-product trick". [3 marks] (ii) Prove the correctness of the above claim or refute it with a clearly explained graphical or numerical counterexample. [7 marks] (c) Traditionally, Jarvis's march handles the left side and the right side of the hull separately. Clearly explain why a single pass would not work as desired and then describe a variant implementation to handle the problem in one pass, highlighting its advantages and disadvantages. [Hint: see part (b)(ii).]Describe and compare the call-by-value, call-by-name, and call-by-need evaluation strategies for functional programming languages. The ML function butlast removes the last element from a non-empty list: exception Butlast; fun butlast [] = raise Butlast | butlast [ ] = [] | butlast (x::xs) = x::(butlast xs); Show how the evaluation of butlast [[1,2],[],[3],[4,5]] proceeds in ML. Write an iterative version of butlast (i.e. one in which the recursive function calls are tail recursive). You may assume the existence of the append (@) function. State with justification the time complexity of your function. An ML data type of lazy lists can be defined by: datatype 'a lazy list = Nil | Cons of unit -> 'a * 'a lazy list; An 'infinite' list of increasing integers can be generated by the function infinite below: fun infinite n = Cons (fn () => (n, infinite(n+1))); Write a version of butlast for lazy lists which terminates when applied to an infinite lazy list such as infinite(0). Can an iterative version of this function be written that still terminates on infinite lazy lists? Explain your reasoning. [20 marks] ) What does the ML function map do? Give an example, first coded without map and then with it, to illustrate how it can lead to more compact or comprehensible code. [3 marks] (b) Functions foldl and foldr might be defined as fun foldl f (e, []) = e | foldl f (e, x::xs) = foldl f (f(e,x), xs); fun foldr f ([], e) = e | foldr f (x::xs , e) = f(x, foldr f (xs,e)); Explain what these two functions do and why they may be useful. [4 marks] (c) Here is a typical use of map: fun mangle n = (n-2)*(n+7); fun manglelist x = map mangle x; Show how to express manglelist using one of the "fold" functions rather than map.(a) Write brief notes on top-down merge sort, contrasting it with insertion sort. State its worst-case and average-case complexity, with brief justification. (There is no need to present ML code.) [5 marks] (b) Write brief notes on preorder, inorder and postorder tree traversal. Present efficient code for one of them and state, with justification, its worst-case complexity. [5 marks] (c) The binary search tree t1 is superseded by t2 provided every (key, value) entry in t1 is also present in t2. Code an ML function to determine whether one binary search tree is superseded by another. Express its cost in terms of n1 and n2, the numbers of entries in t1 and t2, respectively. For full credit, the worst-case cost should be no worse than O(n1 + n2). [10 marks] All code must be explained clearly. You may assume that any necessary ML data structures or functions are available.The ML data type BOOL, defined below, is to be used to represent boolean expressions. datatype BOOL = VAR of string | NOT of BOOL | AND of BOOL*BOOL | OR of BOOL*BOOL; The constructor VAR is used to represent named boolean variables, and NOT, AND and OR are used to represent the corresponding boolean operators. Define a function that will return a list of the distinct names used in a given boolean expression. [4 marks] A context is represented by a list of strings corresponding to the boolean variables that are set to true. All other variables are deemed to be set to false. Define a function that will evaluate a given boolean expression in a given context. [3 marks] Incorporate your two functions into a program that will determine whether a given boolean expression is true for all possible settings of its variableA puzzle, or one-person game, can be represented in ML by two functions: a next-state function, which maps a state to a list of possible next states, and a wins function, which returns true if the given state counts as a win. A simple example is a puzzle that has states consisting of positive integers, a nextstate function that maps n to [n+ 2, n+ 5], and a "wins" function that returns true if n = 10. We can win if we start from n = 2 but not from n = 7. (a) Code a polymorphic datatype 'a puzzle, to represent a puzzle by the pair of a next-state function and a wins function. [2 marks] (b) Briefly contrast depth-first search, breadth-first search and iterative deepening as techniques for solving such puzzles. [6 marks] (c) Write a function depth that accepts a puzzle, a state and a depth limit. It should use depth-first search to determine whether the puzzle can be solved from the given state within the given depth limit. [6 marks] (d) Write a function breadth that accepts a puzzle and a state. It should use breadth-first search to determine whether the puzzle can be solved from the given state. [6 marks] All code must be explained clearly. You may assume that any necessary ML data structuresHere horizontal and vertical bars indicate walls. One can step from a position to an adjacent position if there is no wall obstructing the move. For example, one can move in one step from position (1,1) to position (2,1), but not to (1,0). Diagonal steps are not allowed. (a) Carefully explain a convenient way of representing such labyrinths in ML. Then define a function, call it next, which takes two arguments, a position (x,y) and a labyrinth, and returns a list of all positions that can be reached in one step from position (x,y). [Hint: Consider representing labyrinths as functions with a type of the form int * int -> something.] [8 marks] (b) Use next to code, in ML, a space-efficient function that checks whether it is possible to move from a position (x1,y1) to another position (x2,y2) in a given labyrinth. For full marks, make sure your function always terminates. [6 marks] (c) Explain, not necessarily using ML code, how one can code a function that returns the shortest path between two given positions. Here path means a list of all the positions one would visit en route to the destination. The solution must be space efficient and practical even for large labyrinths. Briefly explain why your solution is space efficientFoundations of Computer Science (a) This question concerns the data structure of queues. (i) Describe the primitive queue operations. [3 marks] (ii) Describe an efficient implementation of queues, presenting code fragments as appropriate (a complete program listing is not required). [3 marks] (iii) Carefully discuss the efficiency of your implementation, using the concept of amortised time. [4 marks] (b) Write an ML function to compute all permutations of its argument, a list. (You may assume that the elements of this list are distinct.) For example, given the argument [1, 2, 3], the result should be a list consisting of the elements [1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2] and [3, 2, 1] in any order. For full credit, your code must be well structured and clearly You are a computer architect working on the design of your company's new instruction set architecture for the 21st Century. Analysis of the latest implementation of the current architecture indicates that removal of logic to perform 8- and 16-bit loads and stores could result in a 20% reduction in processor cycle time. You have been assigned to assess the overall performance implications of removing sub-word memory accesses from the current architecture in order to determine whether they will be omitted from the new architecture. First, you need to consider what sequence of instructions will be required to emulate sub-word loads and stores in software using standard instructions. Show the instruction sequences that will be required to load and store a signed byte value given an arbitrary byte address stored in a register. Be sure to state any assumptions you make. [10 marks] Here is a summary of some dynamic instruction mix data that have been collected from the company's current processor executing an important integer benchmark: Instruction Percentage Instruction Percentage load 20% add 18% branch 16% compare 13% store 9% or 8% shift 7% other 9% Of the loads and stores, 94% are 32-bit, 0% are 16-bit, and 6% are 8-bit. Assuming that your instruction sequences are used to replace all the 8-bit memory accesses, estimate the overall performance of the new implementation relative to the one with hardware support for such accesses. [4 marks] In practice, shorter instruction sequences can be used to replace most sub-word accesses on processors without such hardware support. What extra instruction set features or compiler optimisations might be used to reduce the overhead of sub-word memory accesses?(a) Give one difference and one similarity between the programming languages: (i) Algol and SIMULA [2 marks] (ii) LISP and Smalltalk [2 marks] (b) What is the type of the expression fn f => fn x => f(f(x)) inferred by the SML interpreter? Explain your answer. [6 marks] (c) Give an example in the SML Modules language of two distinct signatures, say IN and OUT, and of a functor that takes structures matching IN to produce structures matching OUT. [6 marks] (d) Comment on the mechanism for parameter-passing in the programming language Scala. [4 marks] You may wish to consider the following two code samples. def whileLoop( cond: => Boolean )( comm: => Unit ) { if( cond ) comm; whileLoop( cond )( comm ) } def qsort[T]( xs: Array[T] )( implicit o: Ord[T] ): Array[T] = if( xs.length <= 1 ) xs else { val pivot = xs( xs.length/2 ) Array.concat ( qsort( xs filter (x => x.lt(x,pivot)) ) , xs filter (x => x == pivot ) , qsort( xs filter (x => x.lt(pivot,x)) ) ) }