## Description

1. Suppose A[1..n] is an array of n distinct integers. Each integer A[i] could be positive, negative, or zero. Find

a contiguous subarray which has the largest sum. For example, if the A = [−2, 1,−3, 4,−1, 2, 1,−5, 4], then

the contiguous subarray with the largest sum is 4,−1, 2, 1, with sum 6. Design a recursive and an iterative

algorithm runs in O(n) time. (Hint: use induction)

2. Given n numbers, find the maximum and the second maximum in about n + log n steps. (Fact: if the range

of the numbers is unbounded, the only thing you can do is using comparison. Therefore, you can’t use radix

sort here)

3. The Element Uniqueness problem is to determine whether all elements in an array are distinct. If you are

only allowed to use comparison, the problem will need at least O(n log n) time. Based on this fact, prove that

there is no algorithm for closest pair problem less than O(n log n) time if the points are not from a bounded

domain (see comment in problem 2), because then you’ll be able to answer the Element Uniqueness problem

in less than O(n log n) time, also called o(n log n)- little O of n log n, i.e. function whose asymptotic grows

slower than a rate of a constant from n log n, e.g., n

p

log n.

4. Design a convex hull algorithm in O(n log n) time using divide and conquer.

Æ Homework assignments are STRICTLY due on the exact time indicated. Please submit a hard copy of your

homework solution with your Name, Bruin ID, Discussion Number, clearly indicated on the first page.

If your homework consists of multiple pages, please staple them together. Email attachments or other

electronic delivery methods are not acceptable.

Æ We recommend to use LATEX, LYX or other word processing software for submitting the homework. This is

not a requirement but it helps us to grade the homework and give feedback. For grading, we will take into

account both the correctness and the clarity. Your answer are supposed to be in a simple and understandable

manner. Sloppy answers are expected to receiver fewer points.

Æ Unless specified, you should justify your algorithm with proof of correctness and time complexity.

1