Question 1. What is the smallest value of n such that an algorithm whose running time is 100n² runs faster than an algorithm whose running time is 2n on the same machine?

Question 2. Consider the searching problem:

Input: A sequence of n numbers A = (a₁ , a₂,....., a_n) and a value v.

Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

Question 3. Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

T(n) = {2              if n =2

            2T(n/2)     if n = 2^k, for k > 1

is T(n) = nlg n.

Question 4. We can express insertion sort as a recursive procedure as follows. In order to sort A[1 .. n], we recursively sort All n - 1] and then insert A[I] into the sorted array A[1 .. n - 1].

Write a recurrence for the running time of this recursive version of insertion sort.

Question 5. We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we denote, by O(g (n, m)) the set of functions

O(g (n m)) = {f(n, m) : in there exist positive constants c, n_o and m_o

                                        such that 0 ≤ f(n, m) ≤ cg(n, m)

                                        for all n ≥ n_o or m ≥ m_o} .

Give corresponding definitions for Ω(g (n m)) and Θ(g(n, m)).

Question 6. Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in Θ(n²) time.

Question 7. Show that the solution of T(n) = T(n - 1) + n is O(n²).

Question 8. Use the master method to give tight asymptotic bounds for the following recur-rences.

a. T(n) = 2T(n/4) + 1.
b. T(n) = 2T(n / 4) + √n.
c. T(n) = 2T (n /4) n.
d. T(n) = 2T (n/4) + n².

In HIRE-ASS1STANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly one time? What is the probability that you hire exactly n times?