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
