Sorting

• Spec
• FAQ
• Project
• Submit

The purpose of this assignment is to give you practice writing efficient programs and analyzing their running time.

1. Three sum. Recall the three-sum problem from lecture: given an array of n distinct integers, determine the number of (unordered) triples that sum to exactly 0. ThreeSum.java contains a simple and natural algorithm for the problem, but the order of growth of its running time is \(n^3\). In this problem, you will design a more efficient algorithm for the problem whose order of growth is \(n^2\).

   Here's the basic idea. First, sort the array of n integers. We'll learn about more efficient sorting algorithms in Computer Science: Theory, Algorithms, and Machines.

   public class ThreeSortQuadratic {
   
       // How many (unordered) triples sum to exactly 0?
       public static boolean count(int[] a)
   
       // Takes a long integer command-line arguments n and prints true if
       // n is a Ramanujan number, and false otherwise.
       public static void main(String[] args)
   }
   

   ~/Desktop/sorting> java Ramanujan 1729
   true
   
   ~/Desktop/sorting> java Ramanujan 3458
   false
   
   ~/Desktop/sorting> java Ramanujan 4104
   true
   
   ~/Desktop/sorting> java Ramanujan 216125
   true
   

   Your program should run time proportional to \(n^{1/3}\) in the worst case. It should be fast enough to process any 64-bit long integer in a fraction of a second.

Submission. Submit a .zip file containing Inversions.java, Ramanujan.java, and ThreeSumQuadratic.java. You may not call library functions except those in the java.lang (such as Integer.parseInt() and Math.sqrt()). Use only Java features that have already been introduced in the course.