Assn 2: Proofs & design

Due: 5pm, Wednesday, September 17. Value: 4% of final grade.

Choose any two of the following three problems to answer. Please note that each problem requires a carefully written mathematical argument; the quality of reasoning and writing shown in this argument will be the primary criterion by which your solutions will be graded.

You should submit your solution on paper, either handwritten or typed. E-mailed solutions will not be accepted. Feel free to submit your solution by sliding the paper under my office door.

Problem 1

Using induction, and without appealing to the Master Theorem, prove that T(n) = n log2 n + n is a correct closed-form solution to the below recurrence, assuming that n is a power of 2. (Please note that you are proving an exact bound, not a big-O bound.)

T(n) = { 1if n ≤ 1
T(n/2) + nif n > 1

Problem 2

Suppose we have two arrays of n numbers, both known to be in increasing order. We want to find the median of the numbers in both arrays. For instance, if the arrays are <1, 2, 4> and <3, 5, 6>, the median is 3.5: If you merge the arrays together, the middle two numbers are 3 and 4, which average to 3.5.

Describe an algorithm for this problem that takes O(log n) time. Argue that your algorithm is correct and that it takes the required amount of time.

Problem 3

Given an array a of numbers, we want to find the largest sum of any subsegment a[i:j] of the array. For example, given the array <−1, 4, −2, 3, −5>, the largest sum is 5, achieved in this case by summing the middle three numbers.

Design a divide-and-conquer algorithm for this problem, and argue that it works correctly and that it takes O(n log n) time. (There is an O(n) algorithm for this problem based on dynamic programming. However, your solution here should explicitly use the divide-and-conquer technique.)