# 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` log_{2} `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) = { |
1 | if n ≤ 1 |

2 T(n/2) + n | if 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

of numbers, we want to find the largest sum
of any subsegment `a`

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.`a`[`i`:`j`]

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.)