HW1: Upper and lower bounds on the running time of the 3SUM problem will be due on WED 25 JAN 2012.
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.