Algorithms study problems

Problem 1

Consider the following procedure Gnarly, which returns true or false. Notice the indenting on lines 04-05: they execute only when the test on line 03 succeeds. You can assume that \(n \ge 1\) and that extracting a subarray (e.g. in the recursive calls in line 06) requires only constant time. 

01 Gnarly (a[1],..., a[n]:  array of integers) 
02     if (n = 1) return true
03     else if (n = 2)
04         if (a[1] = a[2]) return true
05         else return false 
06     else if (Gnarly(a[1],...,a[n-1]) and Gnarly(a[2],...,a[n])) return true 
07     else return false
  1. If Gnarly returns true, what must be true of the values in the input array? Briefly justify your answer.
  2. Give a recursive definition for T(n), the running time of Gnarly on an input of length n. Be sure to include a base case.
  3. Give a big-theta bound on the running time of Gnarly. For full credit, you must show work or briefly explain your answer.

solution

Problem 2

Here is pseudocode for functions find_closest and find_closest_sorted. Each function takes as input an array of n numbers and a target number and outputs the closest value in the input that is at least as large as the target (or NULL if no such number exists). The function find_closest_sorted assumes that the input array is sorted in ascending order. 

01 function find_closest(input_array, target)}
02   sorted_array = cocktailsort(input_array)   
03   return find_closest_sorted(sorted_array, target)


04 function find_closest_sorted(sorted_array, target)
05    length = get_length(sorted_array)    // takes constant time
06    if length = 0 
07        return NULL
08    else if length = 1 
09        if sorted_array[0] >= target 
10               return sorted_array[0]
11        else return NULL
12    else
13        mid = floor(length/2)
14        if (sorted_array[mid-1] < target)
15           half_array = sorted_array(mid,...,length-1)     // array containing second half of elements 
16        else 
17           half_array = sorted_array(0, ...,mid-1)         // array containing first half of elements 
18         return find_closest_sorted(half_array, target)

Answer the questions below using worst-case analysis (e.g., the target value is equal to the largest number in the input array). Assume that the input length n is a power of 2 and that cocktailsort takes \(\Theta(n^2)\) time.

  1. Suppose R(n) is the running time of find_closest_sorted. Give a recursive definition of R(n). Assume that it takes constant time to extract the first or second half of the array in lines 15 and 17.
  2. What is the height of the recursion tree for R(n)?
  3. How many leaves are in the recursion tree for R(n)?
  4. What is the big-Theta (aka tight big-O) running time of find_closest_sorted? Make your answer as simple as posible.
  5. What is the big-Theta running time of find_closest. Make your answer as simple as possible.

solution