Let B be a subset of Nm, m > 1. We say that B is r.e. if B = {(x1 , ... , xm) E Nm I g(xto ... , xm)H for some partially computable function g(x1 , ??? , xm). Let Show that B' is r.e. if and only if B is r.e. 2. Let K0 = {(x, y) I x E Wj}. Show that K0 is r.e. 3. Let f be an n-ary partial function. The graph of f, denoted gr(f), is the set {[x1 , ??? , xn ,f(x1 , ??? , xn)] I f(x 1 , ??? , xn)J, }. (a) Let W be a PRC class. Prove that if f belongs to W then gr(f) belongs to W. (b) Prove that if gr (f) is recursive then f is partially computable. (c) Prove that the recursiveness of gr(f) does not necessarily imply that f is computable. 4. Let B = {f(n) In EN}, where f is a strictly increasing computable function [i.e., f(n + 1) > f(n) for all n]. Prove that B is recursive. 5. Show that every infinite r.e. set has an infinite recursive subset. : 6. Prove that an infinite set A is r.e. if and only if A = {f(n) In EN} for some one-one computable function f(x).

Let CNF-SAT denote the problem of determining, given a formula in CNF, whether it has a satisfying assignment. Let k-SAT denote the problem of determining, given a formula in k-CNF, whether it has a satisfying assignment. Let k-NAE denote the problem of determining, given a formula in k-CNF, whether it has a not-all-equals assignment. (a) Explain why CNF-SAT is NP-complete. Your explanation should include a full definition of NP-completeness and a brief sketch of the proof of the Cook-Levin theorem. [5 marks] (b) Show that 3-SAT is NP-complete by means of a suitable reduction. [3 marks] (c) Give a polynomial-time reduction from 3-SAT to 4-NAE. What can you conclude about the complexity of the latter problem? (Hint: consider introducing one new variable and adding it to every clause.) [8 marks] (d) Show that the problem 3-NAE is NP-complete. (Hint: consider a reduction from 4-NAE)

What is the maximum number of terms there can be in a minimal sum of products form of a function of n boolean variables? [2 marks] Consider a two-bit multiplier with inputs x1, x0, y1, y0 and outputs z3, z2, z1, z0 such that Z = Y X where Z, Y, X are the positive integers represented by z3z2z1z0, y1y0 and x1x0 using the obvious representation. Find a minimal sum of products expression for each of z3, z2, z1 and z0. [10 marks] Comment on the complexity of building an eight-bit multiplier using a minimal sum of products form. [3 marks] Describe another way of building an eight-bit multiplier.

Describe the characteristic features of a VLIW (Very Long Instruction Word) processor architecture. [3 marks] VLIW processors aim to achieve high execution throughput using a different strategy from that of out-of-order dynamic execution RISC implementations. Compare and contrast these different approaches, pointing out the advantages and disadvantages of each strategy in achieving this goal. You may wish to consider the following issues: ? instruction issue logic ? cache sizes ? compiler code generation ? execution unit utilisation [9 marks] Why have VLIW architectures traditionally been used only for special-purpose applications such as Digital Signal Processors? What techniques have been developed to make VLIW-like architectures more suitable for general-purpose use? [5 marks] 3 [TURN OVER

Transcribed Image Text:

1. Give appropriate descriptions in terms of each of 'O' (big-Oh) and (big-Omega) of the function f(n) = 5 n2 - n2 log(n3) You should justify your answers, but do not need to give proofs. 2. Consider a binary tree satisfying the heap properties and containing n nodes. Give the big-Oh and big- Omega of the height of the tree, and give a brief justification of your answers. 3. a) Give, and also briefly explain, the definitions of big-Oh, big-Omega, and little-oh by completing each of the following: i) 'big-Oh': f(n) is O(g(n))..... ii) 'big-Omega': f(n) is g(n)).... iii) 'little-oh': f(n) is o( g(n)).... (b) From the definitions prove or disprove that f(n) = 2 n2-nis i)0 (12) (big-Oh) ii) 2 (n2) (big-Omega) (c) Given the function f(n) = n when n is even = 2 n2-n when n is odd From the definitions prove or disprove that f(n) is (n2) (big-Omega) (d) Suppose you are given a function f(n) and all you know about it is that f(n) is O( g(n)) ("big-Oh of g") From the definition of little-oh prove that f(n) is o( n g(n)) ("little-oh of n times g(n)") (e) Briefly explain the idea and usage of amortised complexity when considering a sequence of operations on a data structure. In particular, explain the difference from the average case complexity. 1. Give appropriate descriptions in terms of each of 'O' (big-Oh) and (big-Omega) of the function f(n) = 5 n2 - n2 log(n3) You should justify your answers, but do not need to give proofs. 2. Consider a binary tree satisfying the heap properties and containing n nodes. Give the big-Oh and big- Omega of the height of the tree, and give a brief justification of your answers. 3. a) Give, and also briefly explain, the definitions of big-Oh, big-Omega, and little-oh by completing each of the following: i) 'big-Oh': f(n) is O(g(n))..... ii) 'big-Omega': f(n) is g(n)).... iii) 'little-oh': f(n) is o( g(n)).... (b) From the definitions prove or disprove that f(n) = 2 n2-nis i)0 (12) (big-Oh) ii) 2 (n2) (big-Omega) (c) Given the function f(n) = n when n is even = 2 n2-n when n is odd From the definitions prove or disprove that f(n) is (n2) (big-Omega) (d) Suppose you are given a function f(n) and all you know about it is that f(n) is O( g(n)) ("big-Oh of g") From the definition of little-oh prove that f(n) is o( n g(n)) ("little-oh of n times g(n)") (e) Briefly explain the idea and usage of amortised complexity when considering a sequence of operations on a data structure. In particular, explain the difference from the average case complexity.