CS 6363.004: Algorithms
Spring 2019
Assignment 1
Wed, Jan 30, 2019

You can write or type your answers.  Submit on elearning.

If you submit photos of your written assignment, make sure that they are readable
and all pages are included.  Use lower resolution so that each page is less
than 256 KB.  Submit a single pdf, docx or txt file with all the pages.

If you solve optional problems, you can score additional points,
but the net contribution from homework assignments to the weighted total
used in grade calculations is capped at 20/100.

Due: 11:59 PM, Sun, Feb 10 (on elearning).

1. Prove that log(n!) = Theta(n log n) using any method from class.

2. Solve the following recurrences using the given method.  Assume T(1)=1.
	a. Iteration method:   T(n) <= 2T(n/2) + 1, for n > 1.
	b. Substitution method:   T(n) = T(n-1) + n^2, for n > 1.
	c. Master method (special case): Problem 4-1, parts a,c,e (p. 107).

3. Rewrite recursive binary search to solve the following problem:
   Given a sorted array A, and a value x, find the index i of A such that
   A[i] <= x < A[i+1].  Assume that A[0] = -infinity and A[n-1] = +infinity,
   where n = A.length.  In other words, the function should return the index of
   the rightmost occurrence of x if x is in A, and the index of floor(x) if
   x is not in A.  Prove that your algorithm is correct and analyze its running time.

   // Assume A has sentinels, A[0] = -infinity and A[n-1] = +infinity.
   int binarySearch(int[] A, int x):
	return binarySearch(A, 0, A.length-1, x)

   int binarySearch(int[] A, int p, int r, int x):  // To do


Optional problems (extra credit):

4. Prove that the following algorithm is incorrect for problem 3:

   binarySearch(A, p, r, x):
     n <-- r-p+1
     if n <=  2 then
        return p
     else
        q <-- (p+r)/2
        if x < A [q] then
           return binarySearch(A, p, q-1, x)
        else if x = A [q] then
           return q
        else /* x > A[q] */
           return binarySearch(A, q+1, r, x)

5. Write a proof of correctness of the recurrence for E(j) that was
   written in class for the maximum subarray problem.  Show that it
   runs in O(n) time.

6. Show how to implement the divide and conquer algorithm for the
   maximum subarray problem discussed in class (see Sec 4.1 in book)
   to run in O(n) time.  Do not modify the main structure of the
   algorithm: divide into 2 halves, recurse and conquer.