HW1: Upper and lower bounds on the running time of the 3SUM problem will be due on WED 25 JAN 2012.

3SUM Problem

INPUT: a positive integer n. Three arrays A,B,C, each containing n positive integers. A = [a1,…,an], and similarly for B and C. Integers in an array not necessarily sorted.

OUTPUT: any triple * such that a_i + b_j = c_k if such a triple exists; “NONE SUCH” otherwise. Note that if there is more than one triple, only one has to be output.*

*
*As mentioned in class, you are to make your bounds as tight as you can make them but no tighter. Remember to say where your ideas came from, including (if itâ€™s the case) from your own head. You will NEVER lose points for good scholarship.

See Lecture 1 for problem description.

### Like this:

Like Loading...

*Related*