In the next two problems and throughout the course, you will be asked to design efficient algorithms. The word "efficient" here usually means that the worst-case complexity of your algorithms is O(n") for some constant k, where n denotes the size of the input. Naturally, you should prefer to construct algorithms so that k is as small as possible, thus the score you achieve for each problem will reflect how small your running time is. As a general rule, algorithms that are of the brute-force variety, or have running times that are equivalent to a brute-force algorithm, may not receive many/any points, and ought to be reexamined. You should write your algorithms using pseudocode in a "C-like" style. Good inden- tation and thoughtful comments will assist the (tired, overworked) TA when they read your algorithm. Use the unit-cost model to analyze your algorithm. Express the running time of your algorithm as a function of n, the size of the input. Exact answers are not required. Instead, find an upper bound and express the complexity of the running time using Big-O (or Big-e) notation. 4. [20 marks] Unbounded Secret Number Suppose that you and I play a guessing game. First, I will pick an integer N that will remain fixed throughout the game. Next, you will ask a sequence of yeso questions, each of which I must answer truthfully. Your goal is to determine my number using the fewest questions possible. Devise a sequence of questions that will always determine N. Then analyze the total number of questions as a function of N. Like in Lecture 1, the questions will be of one of two types. (a) [10 marks] Single number guesses. E.g., "Is it 1?" (b) (10 marks) A combo of single number guesses and greater than questions. E.g., "Is N > 50?" 5. (30 marks] Partial Sums Suppose you were given an array of integers A[N], and you were tasked with computing all the partial sums of the array. A partial sum adds a contiguous range of elements, i.e., A[i] + A[i+1] + ... + AG) for indices i, j where 0