\

(a) (i) Given an array containing n entries sorted in nondecreasing order, and given a value x, describe the binary search method for finding the position of x in the array. (ii) Using an example of a sorted array of eight numbers, explain how the binary search method find the position of number 7 . You should not use an example from the lectures or online sources. (b) Let D1 and D2 denote two decision problems. What does it mean to say that D1 is polynomially transformable to D2 (written D1PD2 )? (c) Explain the steps for proving Hamiltonian Circult Problem (HCP) is polynomially transformable to Travelling Saleman Problem (TSP) using an example of an instance for HCP. You should not use the example from the lectures or online sources. (d) Prove that, if D1PD2 and D2 can be solved by a polynomial time algorithm, then D1 can be solved by a polynomial time algorithm. (e) Give a definition of the set of NP-complete problems. [2]