1.
1 package algorithms.analysis14; 2 3 import algorithms.util.In; 4 import algorithms.util.StdOut; 5 6 /****************************************************************************** 7 * Compilation: javac TwoSum.java 8 * Execution: java TwoSum input.txt 9 * Dependencies: StdOut.java In.java Stopwatch.java 10 * Data files: http://algs4.cs.princeton.edu/14analysis/1Kints.txt 11 * http://algs4.cs.princeton.edu/14analysis/2Kints.txt 12 * http://algs4.cs.princeton.edu/14analysis/4Kints.txt 13 * http://algs4.cs.princeton.edu/14analysis/8Kints.txt 14 * http://algs4.cs.princeton.edu/14analysis/16Kints.txt 15 * http://algs4.cs.princeton.edu/14analysis/32Kints.txt 16 * http://algs4.cs.princeton.edu/14analysis/1Mints.txt 17 * 18 * A program with N^2 running time. Read in N integers 19 * and counts the number of pairs that sum to exactly 0. 20 * 21 * 22 * Limitations 23 * ----------- 24 * - we ignore integer overflow 25 * 26 * 27 * % java TwoSum 2Kints.txt 28 * 2 29 * 30 * % java TwoSum 1Kints.txt 31 * 1 32 * 33 * % java TwoSum 2Kints.txt 34 * 2 35 * 36 * % java TwoSum 4Kints.txt 37 * 3 38 * 39 * % java TwoSum 8Kints.txt 40 * 19 41 * 42 * % java TwoSum 16Kints.txt 43 * 66 44 * 45 * % java TwoSum 32Kints.txt 46 * 273 47 * 48 ******************************************************************************/ 49 50 public class TwoSum { 51 52 // print distinct pairs (i, j) such that a[i] + a[j] = 0 53 public static void printAll(int[] a) { 54 int N = a.length; 55 for (int i = 0; i < N; i++) { 56 for (int j = i+1; j < N; j++) { 57 if (a[i] + a[j] == 0) { 58 StdOut.println(a[i] + " " + a[j]); 59 } 60 } 61 } 62 } 63 64 // return number of distinct triples (i, j) such that a[i] + a[j] = 0 65 public static int count(int[] a) { 66 int N = a.length; 67 int cnt = 0; 68 for (int i = 0; i < N; i++) { 69 for (int j = i+1; j < N; j++) { 70 if (a[i] + a[j] == 0) { 71 cnt++; 72 } 73 } 74 } 75 return cnt; 76 } 77 78 public static void main(String[] args) { 79 In in = new In(args[0]); 80 int[] a = in.readAllInts(); 81 Stopwatch timer = new Stopwatch(); 82 int cnt = count(a); 83 StdOut.println("elapsed time = " + timer.elapsedTime()); 84 StdOut.println(cnt); 85 } 86 }
The answer to this question is that we have discussed and used two classic algorithms,
mergesort and binary search, have introduced the facts that the mergesort is linearith-
mic and binary search is logarithmic.
2.
1 package algorithms.analysis14; 2 3 /****************************************************************************** 4 * Compilation: javac TwoSumFast.java 5 * Execution: java TwoSumFast input.txt 6 * Dependencies: In.java Stopwatch.java 7 * Data files: http://algs4.cs.princeton.edu/14analysis/1Kints.txt 8 * http://algs4.cs.princeton.edu/14analysis/2Kints.txt 9 * http://algs4.cs.princeton.edu/14analysis/4Kints.txt 10 * http://algs4.cs.princeton.edu/14analysis/8Kints.txt 11 * http://algs4.cs.princeton.edu/14analysis/16Kints.txt 12 * http://algs4.cs.princeton.edu/14analysis/32Kints.txt 13 * http://algs4.cs.princeton.edu/14analysis/1Mints.txt 14 * 15 * A program with N log N running time. Read in N integers 16 * and counts the number of pairs that sum to exactly 0. 17 * 18 * Limitations 19 * ----------- 20 * - we ignore integer overflow 21 * 22 * 23 * % java TwoSumFast 2Kints.txt 24 * 2 25 * 26 * % java TwoSumFast 1Kints.txt 27 * 1 28 * 29 * % java TwoSumFast 2Kints.txt 30 * 2 31 * 32 * % java TwoSumFast 4Kints.txt 33 * 3 34 * 35 * % java TwoSumFast 8Kints.txt 36 * 19 37 * 38 * % java TwoSumFast 16Kints.txt 39 * 66 40 * 41 * % java TwoSumFast 32Kints.txt 42 * 273 43 * 44 ******************************************************************************/ 45 46 import java.util.Arrays; 47 48 import algorithms.util.In; 49 import algorithms.util.StdOut; 50 51 public class TwoSumFast { 52 53 // print distinct pairs (i, j) such that a[i] + a[j] = 0 54 public static void printAll(int[] a) { 55 int N = a.length; 56 Arrays.sort(a); 57 for (int i = 0; i < N; i++) { 58 int j = Arrays.binarySearch(a, -a[i]); 59 if (j > i) StdOut.println(a[i] + " " + a[j]); 60 } 61 } 62 63 // return number of distinct pairs (i, j) such that a[i] + a[j] = 0 64 public static int count(int[] a) { 65 int N = a.length; 66 Arrays.sort(a); 67 int cnt = 0; 68 for (int i = 0; i < N; i++) { 69 int j = Arrays.binarySearch(a, -a[i]); 70 if (j > i) cnt++; 71 } 72 return cnt; 73 } 74 75 public static void main(String[] args) { 76 In in = new In(args[0]); 77 int[] a = in.readAllInts(); 78 int cnt = count(a); 79 StdOut.println(cnt); 80 } 81 }
3.
1 package algorithms.analysis14; 2 3 import algorithms.util.In; 4 import algorithms.util.StdOut; 5 6 /****************************************************************************** 7 * Compilation: javac ThreeSum.java 8 * Execution: java ThreeSum input.txt 9 * Dependencies: In.java StdOut.java Stopwatch.java 10 * Data files: http://algs4.cs.princeton.edu/14analysis/1Kints.txt 11 * http://algs4.cs.princeton.edu/14analysis/2Kints.txt 12 * http://algs4.cs.princeton.edu/14analysis/4Kints.txt 13 * http://algs4.cs.princeton.edu/14analysis/8Kints.txt 14 * http://algs4.cs.princeton.edu/14analysis/16Kints.txt 15 * http://algs4.cs.princeton.edu/14analysis/32Kints.txt 16 * http://algs4.cs.princeton.edu/14analysis/1Mints.txt 17 * 18 * A program with cubic running time. Read in N integers 19 * and counts the number of triples that sum to exactly 0 20 * (ignoring integer overflow). 21 * 22 * % java ThreeSum 1Kints.txt 23 * 70 24 * 25 * % java ThreeSum 2Kints.txt 26 * 528 27 * 28 * % java ThreeSum 4Kints.txt 29 * 4039 30 * 31 ******************************************************************************/ 32 33 /** 34 * The <tt>ThreeSum</tt> class provides static methods for counting 35 * and printing the number of triples in an array of integers that sum to 0 36 * (ignoring integer overflow). 37 * <p> 38 * This implementation uses a triply nested loop and takes proportional to N^3, 39 * where N is the number of integers. 40 * <p> 41 * For additional documentation, see <a href="http://algs4.cs.princeton.edu/14analysis">Section 1.4</a> of 42 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 43 * 44 * @author Robert Sedgewick 45 * @author Kevin Wayne 46 */ 47 public class ThreeSum { 48 49 // Do not instantiate. 50 private ThreeSum() { } 51 52 /** 53 * Prints to standard output the (i, j, k) with i < j < k such that a[i] + a[j] + a[k] == 0. 54 * @param a the array of integers 55 */ 56 public static void printAll(int[] a) { 57 int N = a.length; 58 for (int i = 0; i < N; i++) { 59 for (int j = i+1; j < N; j++) { 60 for (int k = j+1; k < N; k++) { 61 if (a[i] + a[j] + a[k] == 0) { 62 StdOut.println(a[i] + " " + a[j] + " " + a[k]); 63 } 64 } 65 } 66 } 67 } 68 69 /** 70 * Returns the number of triples (i, j, k) with i < j < k such that a[i] + a[j] + a[k] == 0. 71 * @param a the array of integers 72 * @return the number of triples (i, j, k) with i < j < k such that a[i] + a[j] + a[k] == 0 73 */ 74 public static int count(int[] a) { 75 int N = a.length; 76 int cnt = 0; 77 for (int i = 0; i < N; i++) { 78 for (int j = i+1; j < N; j++) { 79 for (int k = j+1; k < N; k++) { 80 if (a[i] + a[j] + a[k] == 0) { 81 cnt++; 82 } 83 } 84 } 85 } 86 return cnt; 87 } 88 89 /** 90 * Reads in a sequence of integers from a file, specified as a command-line argument; 91 * counts the number of triples sum to exactly zero; prints out the time to perform 92 * the computation. 93 */ 94 public static void main(String[] args) { 95 In in = new In(args[0]); 96 int[] a = in.readAllInts(); 97 98 Stopwatch timer = new Stopwatch(); 99 int cnt = count(a); 100 StdOut.println("elapsed time = " + timer.elapsedTime()); 101 StdOut.println(cnt); 102 } 103 }
4.
1 package algorithms.analysis14; 2 3 /****************************************************************************** 4 * Compilation: javac ThreeSumFast.java 5 * Execution: java ThreeSumFast input.txt 6 * Dependencies: StdOut.java In.java Stopwatch.java 7 * Data files: http://algs4.cs.princeton.edu/14analysis/1Kints.txt 8 * http://algs4.cs.princeton.edu/14analysis/2Kints.txt 9 * http://algs4.cs.princeton.edu/14analysis/4Kints.txt 10 * http://algs4.cs.princeton.edu/14analysis/8Kints.txt 11 * http://algs4.cs.princeton.edu/14analysis/16Kints.txt 12 * http://algs4.cs.princeton.edu/14analysis/32Kints.txt 13 * http://algs4.cs.princeton.edu/14analysis/1Mints.txt 14 * 15 * A program with N^2 log N running time. Read in N integers 16 * and counts the number of triples that sum to exactly 0. 17 * 18 * Limitations 19 * ----------- 20 * - we ignore integer overflow 21 * - doesn't handle case when input has duplicates 22 * 23 * 24 * % java ThreeSumFast 1Kints.txt 25 * 70 26 * 27 * % java ThreeSumFast 2Kints.txt 28 * 528 29 * 30 * % java ThreeSumFast 4Kints.txt 31 * 4039 32 * 33 * % java ThreeSumFast 8Kints.txt 34 * 32074 35 * 36 * % java ThreeSumFast 16Kints.txt 37 * 255181 38 * 39 * % java ThreeSumFast 32Kints.txt 40 * 2052358 41 * 42 ******************************************************************************/ 43 44 import java.util.Arrays; 45 46 import algorithms.util.In; 47 import algorithms.util.StdOut; 48 49 /** 50 * The <tt>ThreeSumFast</tt> class provides static methods for counting 51 * and printing the number of triples in an array of distinct integers that 52 * sum to 0 (ignoring integer overflow). 53 * <p> 54 * This implementation uses sorting and binary search and takes time 55 * proportional to N^2 log N, where N is the number of integers. 56 * <p> 57 * For additional documentation, see <a href="http://algs4.cs.princeton.edu/14analysis">Section 1.4</a> of 58 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 59 * 60 * @author Robert Sedgewick 61 * @author Kevin Wayne 62 */ 63 public class ThreeSumFast { 64 65 // Do not instantiate. 66 private ThreeSumFast() { } 67 68 // returns true if the sorted array a[] contains any duplicated integers 69 private static boolean containsDuplicates(int[] a) { 70 for (int i = 1; i < a.length; i++) 71 if (a[i] == a[i-1]) return true; 72 return false; 73 } 74 75 /** 76 * Prints to standard output the (i, j, k) with i < j < k such that a[i] + a[j] + a[k] == 0. 77 * @param a the array of integers 78 * @throws IllegalArgumentException if the array contains duplicate integers 79 */ 80 public static void printAll(int[] a) { 81 int N = a.length; 82 Arrays.sort(a); 83 if (containsDuplicates(a)) throw new IllegalArgumentException("array contains duplicate integers"); 84 for (int i = 0; i < N; i++) { 85 for (int j = i+1; j < N; j++) { 86 int k = Arrays.binarySearch(a, -(a[i] + a[j])); 87 if (k > j) StdOut.println(a[i] + " " + a[j] + " " + a[k]); 88 } 89 } 90 } 91 92 /** 93 * Returns the number of triples (i, j, k) with i < j < k such that a[i] + a[j] + a[k] == 0. 94 * @param a the array of integers 95 * @return the number of triples (i, j, k) with i < j < k such that a[i] + a[j] + a[k] == 0 96 */ 97 public static int count(int[] a) { 98 int N = a.length; 99 Arrays.sort(a); 100 if (containsDuplicates(a)) throw new IllegalArgumentException("array contains duplicate integers"); 101 int cnt = 0; 102 for (int i = 0; i < N; i++) { 103 for (int j = i+1; j < N; j++) { 104 int k = Arrays.binarySearch(a, -(a[i] + a[j])); 105 if (k > j) cnt++; 106 } 107 } 108 return cnt; 109 } 110 111 /** 112 * Reads in a sequence of distinct integers from a file, specified as a command-line argument; 113 * counts the number of triples sum to exactly zero; prints out the time to perform 114 * the computation. 115 */ 116 public static void main(String[] args) { 117 In in = new In(args[0]); 118 int[] a = in.readAllInts(); 119 int cnt = count(a); 120 StdOut.println(cnt); 121 } 122 }
