Question 1: Binary search
*************************

Part a) Algorithm:
 
This is the solution for the non-decreasing case. For
the non-increasing case the third comparison changes
from ">" to "<" in both the iterative and recursive
solution.

Iterative Algorithm 

int find (const apvector &list, double target);
// Iterative binary search will return the index of 
// the target element, else list length
{
   bool found = false;
   int mid;
   int first = 0;
   int last = list.length( ) - 1;
   while (first <= last && !found)
   {
      mid = (first + last) / 2;
      if (list[mid] == target)
         found = true;
      else
         if (list[mid] > target)
            last = mid - 1;
         else   
            first = mid + 1;
   }
   if (found)
      return mid;
   return -1;
}

Recursive Algorithm 

int Find (const apvector &list, double target, double
first, double last)
// Recursive binary search will return the index of 
// the target element, else list length
{
   int mid;
   if (first > last)
      return -1;
   mid = (first + last) / 2;
   if (list[mid] == target)
      return mid;
   if (list[mid] > target)
      return find(list, target, first, mid-1);
   return find(list, target, mid+1, last);
}

Part b) Recurrence relation:

T(n) = T(n/2) + c

Part c) Solution of b) using the Master Theorem:

a = 1; b = 2, f(n) = c

Conditions of case 2) are satisfied, hence T(n) is
BigTheta(lg n).

Part d) Lower bound:

For an array of size n, the element that we are
searching for could be at possibly n different places.
The solution to each of these locations is represented
by a leaf in the comparison tree. Thus the comparison
tree must have n leaves. Since for any comparison tree
is must be true that the depth of the tree >= (lg n),
the lower bound on the complexity of this problem is
BigOmega(lg n).

Proposed grading criteria for this problem:
 
a) 3 points: 
   2 points for dividing the search space (not necessarily recursively) 
     and identifying a correct base case
   1 point for clear, correct solution

b) 2 points: no partial points
c) 2 points: no partial points
d) 3 points: 
   1 point for correct BigTheta(lg n)
   2 points for correct reasoning


Question 2: Master Method
**************************** 

There was almost no partial credit given for this problem.

Version 1:


3 pts - 1) T(n) = 5T(n/2) + n^2

a = 5, b = 2, Case 1: T(n) = Theta(n^(log(base2)5))

4 pts - 2) T(n) = 9T(n/3) + n^2

a = 9, b = 3, Case 2: T(n) = Theta(n^2(logn))

3 pts - 3) T(n) = 10T(n/3) + n^2

a = 10, b = 3, Case 1: T(n) = Theta(n^(log(base3)10))


Version 2:

4 pts - 1) T(n) = 16T(n/4) + n^2

a = 16, b = 4, Case 2: T(n) = Theta(n^2(logn))

3 pts - 2) T(n) = 7T(n/3) + n^2

a = 7, b = 3, Case 3: T(n) = Theta(n^2)

3 pts - 3) T(n) = 7T(n/2) + n^2

a = 7, b = 2 Case 1: T(n) = Theta(n^(log(base2)7))


Question 3: Frequent element
****************************

Suggest and linear-time algorithm that finds a frequent element in an
unordered array of elements, if it exists. We define a frequent element as
one that is present more than n/3 times in an array of length n. Assume
linear-time selection, that is the presence of an algorithm which finds the
k-th smallest element in an unordered list in linear time. Your proposed
algorithm for finding the frequent element should be also be linear time.

Solution: As a hint, think of the selection problem as a way of peaking
into the sorted array at a specific array location. We know that if there
is a frequent element in the array then in the sorted array there must be
at least (floor(n/3)+1) of this frequent element next to each other. Thus
we can be sure that in the sorted array either at location [floor(n/3)] or
[2*floor(n/3)] we will find a frequent element. Let us call these elements
found at these locations candidates. Once we find a candidate for a
frequent element all we have to do is to check if it really is one. This
check can be done in linear time with a simple sequential scan. 

(bool, element) FindFreq(array: A)
	c1 <- Select(A, floor(n/3));
	if IsFreq(A, c1) return (TRUE, c1)       
	c2 <- Select(A, 2*floor(n/3));      
	if IsFreq(A, c2) return (TRUE, c2)       
	return (FALSE, 0)

The running time of the algorithm is O(n) as required.

Grading criteria: 10 points

10 points if done correctly 
6 points if done partially right (n/3, 2n/3, overlap)
2 points if had one correct concept in there