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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s