Java Program for missing arrays
CIS 390/550 Homework MISS: The Case of the Missing Int(s)1 Due Saturday, September 11 at 11:59 PM 1 Introduction In a distant land lies a curious town filled with strange inhabitants. They speak only in complementary language: everyone says everything except what they mean. When it comes to specifying numbers, like the number of dollars in their bank account, they don’t say the number, but instead list every possible number (say, those between 1 and 1000000) except the actual value. For instance: tell(1); (“It’s not 1”) “Ok” tell(2); (“It’s not 2”) “Ok” tell(4); (“It’s not 4”) “Ok” tell(5); (“It’s not 5”) “Ok” . . . tell(999999); (“It’s not 999999”) “Ok” tell(1000000); (“It’s not 1000000”) “Ok” missing_one(x); (“What number was missing?”) x = 3; (“3 was missing”) In this homework, you’ll implement an “oracle” that can be told a sequence of numbers containing every number from 1 to 1000000, except for one or two, and returns the missing number(s).2 If this seems impossible, just consider the following facts: Theorem 1.1. Let x1, x2, . . . , xn−1, y be a permutation of the numbers from 1 to n. Then y = n(n+1) 2 −∑n−1 i=1 xi. Theorem 1.2. Let x1, x2, . . . , xn−2, y1, y2 be a permutation of the numbers from 1 to n. Let s = y1+y2 and t = y21+y 2 2. Then s = n(n+1)/2− ∑n−2 i=1 xi and t = n(n+1)(2n+1) 6 − ∑n−2 i=1 x 2 i . Moreover, 2y21−2sy1+s2−t = 0. Theorem 1.3 (Quadratic formula). Let a, b, c, x ∈ R with ax2 + bx+ c = 0. Then x = −b± √ b2−4ac 2a . 1This homework is inspired by Bill Gasarch’s “Find the Missing Number or Numbers: An Exposition”. 2In the example above, the oracle is the one responding “Ok” at each step, and “3 was missing” at the end. 1 http://www.cs.umd.edu/~gasarch/BLOGPAPERS/streaming.pdf 2 Instructions The following files have been given to you: 1. A class file (Oracle.java) declaring the Oracle class. 2. A test file (MainTest.java) containing a main function with tests. Implement the class (functions) declared in Oracle.java so that Oracle.java and the provided files compile into a program that runs with no failed tests. Submit only source file Oracle.java. 3 Submission and Grading Submit the aforementioned source file(s) via Blackboard as attached file(s). In the case of multiple submis- sions, the last submission before the deadline is graded. For grading, each submission is compiled with the provided files and run. Submissions that contain failed tests receive deductions. Submissions that do not run to completion (i.e. fail to print “Assignment complete.”) receive no credit. Submissions that take an unreasonable amount of time (e.g. more than a minute or so) to run and do not meet the asymptotic efficiency requirements receive no credit. All other submissions receive full credit. See the course late work policy for information about receiving partial credit for late submissions. 4 Tips Here are some helpful tips for this assignment: • Use long everywhere to avoid overflow and remember that a constant like 1000000 is an int. • Use the theorems in the assignment pdf. No mathematics is needed beyond these three theorems. • Don’t overthink the assignment: this assignment is more about algebra than algorithms. 2 Introduction Instructions Submission and Grading Tips package MissingNumber; import java.lang.Math; public class Oracle { long[] data; // Creates a new oracle, ready to be told all numbers // (in any order) from 1 to 1000000, except for one or two. // // Must run in O(1) time. Oracle() { } // Tells the oracle a number between 1 and 1000000 not yet told. // // Must run in O(1) time. void tell(int i) { } // If every number between 1 and 1000000 except one have // been told, and no number has been told more than once, // sets MissInt[0] equal to the one number not yet told. // // Otherwise has undefined behavior. // // Must run in O(1) time. void missing_one(int[] MissInt) { } // If every number between 1 and 1000000 except two have // been told, and no number has been told more than once, // sets MissInt[0] and MissInt[1] equal to the two numbers // not yet told (where MissInt[0] < missint[1]).="" otherwise="" has="" undefined="" behavior.="" must="" run="" in="" o(1)="" time.="" void="" missing_two(int[]="" missint)="" {="" }="" }="" package="" missingnumber;="" import="" java.util.*;="" import="" missingnumber.oracle;="" public="" class="" maintest="" {="" public="" static="" void="" main(string[]="" args)="" {="" setup="" int[]="" missint;="" missint="new" int[2];="" for="" missing="" numbers.="">
V= new ArrayList(); // Test missing_one() Oracle o1 = new Oracle(); for (int i = 1; i <= 999999;="" ++i)="" o1.tell(i);="" missint[0]="0;" o1.missing_one(missint);="" test(missint[0]="=" 1000000);="" oracle="" o2="new" oracle();="" for="" (int="" i="2;" i=""><= 1000000;="" ++i)="" o2.tell(i);="" missint[0]="0;" o2.missing_one(missint);="" test(missint[0]="=" 1);="" oracle="" o3="new" oracle();="" o3.tell(1);="" for="" (int="" i="3;" i=""><= 1000000;="" ++i)="" o3.tell(i);="" missint[0]="0;" o3.missing_one(missint);="" test(missint[0]="=" 2);="" oracle="" o4="new" oracle();="" v.clear();="" for="" (int="" i="1;" i=""><= 1000000;="" ++i)="" v.add(i);="" collections.shuffle(v);="" for="" (int="" i="0;" i="">< 999999;="" ++i)="" o4.tell(v.get(i));="" o4.missing_one(missint);="" test(missint[0]="=" v.get(999999));="" oracle="" o5="new" oracle();="" v.clear();="" for="" (int="" i="1;" i=""><= 1000000;="" ++i)="" v.add(i);="" collections.shuffle(v);="" for="" (int="" i="0;" i="">< 999999;="" ++i)="" o5.tell(v.get(i));="" o5.missing_one(missint);="" test(missint[0]="=" v.get(999999));="" oracle="" o6="new" oracle();="" v.clear();="" for="" (int="" i="1;" i=""><= 1000000;="" ++i)="" v.add(i);="" collections.shuffle(v);="" for="" (int="" i="0;" i="">< 999999;="" ++i)="" o6.tell(v.get(i));="" o6.missing_one(missint);="" test(missint[0]="=" v.get(999999));="" oracle="" o7="new" oracle();="" v.clear();="" for="" (int="" i="1;" i=""><= 1000000;="" ++i)="" v.add(i);="" collections.shuffle(v);="" for="" (int="" i="0;" i="">< 999999;="" ++i)="" o7.tell(v.get(i));="" o7.missing_one(missint);="" test(missint[0]="=" v.get(999999));="" oracle="" o8="new" oracle();="" v.clear();="" for="" (int="" i="1;" i=""><= 1000000;="" ++i)="" v.add(i);="" collections.shuffle(v);="" for="" (int="" i="0;" i="">< 999999;="" ++i)="" o8.tell(v.get(i));="" o8.missing_one(missint);="" test(missint[0]="=" v.get(999999));="" retest="" old="" oracles="" to="" prevent="" global="" variables="" missint[0]="0;" o1.missing_one(missint);="" test(missint[0]="=" 1000000);="" missint[0]="0;" o3.missing_one(missint);="" test(missint[0]="=" 2);="" missint[0]="0;" o8.missing_one(missint);="" test(missint[0]="=" v.get(999999));="" test="" missing_two="" oracle="" o9="new" oracle();="" for="" (int="" i="1;" i=""><= 999998;="" ++i)="" o9.tell(i);="" missint[0]="MissInt[1]" =="" 0;="" o9.missing_two(missint);="" test(missint[0]="=" 999999);="" test(missint[1]="=" 1000000);="" oracle="" o10="new" oracle();="" for="" (int="" i="3;" i=""><= 1000000;="" ++i)="" o10.tell(i);="" missint[0]="MissInt[1]" =="" 0;="" o10.missing_two(missint);="" test(missint[0]="=" 1);="" test(missint[1]="=" 2);="" oracle="" o11="new" oracle();="" o11.tell(1);="" o11.tell(3);="" for="" (int="" i="5;" i=""><= 1000000;="" ++i)="" o11.tell(i);="" missint[0]="MissInt[1]" =="" 0;="" o11.missing_two(missint);="" test(missint[0]="=" 2);="" test(missint[1]="=" 4);="" oracle="" o12="new" oracle();="" for="" (int="" i="2;" i=""><= 999999;="" ++i)="" o12.tell(i);="" missint[0]="MissInt[1]" =="" 0;="" o12.missing_two(missint);="" test(missint[0]="=" 1);="" test(missint[1]="=" 1000000);="" oracle="" o13="new" oracle();="" v.clear();="" for="" (int="" i="1;" i=""><= 1000000;="" ++i)="" v.add(i);="" collections.shuffle(v);="" if="" (v.get(999998)=""> V.get(999999)) Collections.swap(V, 999998, 999999); for (int i = 0; i < 999998;="" ++i)="" o13.tell(v.get(i));="" missint[0]="MissInt[1]" =="" 0;="" o13.missing_two(missint);="" system.out.println(missint[0]+","+missint[1]);="" test(missint[0]="=" v.get(999998));="" test(missint[1]="=" v.get(999999));="" oracle="" o14="new" oracle();="" v.clear();="" for="" (int="" i="1;" i=""><= 1000000;="" ++i)="" v.add(i);="" collections.shuffle(v);="" if="" (v.get(999998)=""> V.get(999999)) Collections.swap(V, 999998, 999999); for (int i = 0; i < 999998;="" ++i)="" o14.tell(v.get(i));="" missint[0]="MissInt[1]" =="" 0;="" o14.missing_two(missint);="" test(missint[0]="=" v.get(999998));="" test(missint[1]="=" v.get(999999));="" oracle="" o15="new" oracle();="" v.clear();="" for="" (int="" i="1;" i=""><= 1000000;="" ++i)="" v.add(i);="" collections.shuffle(v);="" if="" (v.get(999998)=""> V.get(999999)) Collections.swap(V,999998,999999); for (int i = 0; i < 999998;="" ++i)="" o15.tell(v.get(i));="" missint[0]="MissInt[1]" =="" 0;="" o15.missing_two(missint);="" test(missint[0]="=" v.get(999998));="" test(missint[1]="=" v.get(999999));="" oracle="" o16="new" oracle();="" v.clear();="" for="" (int="" i="1;" i=""><= 1000000;="" ++i)="" v.add(i);="" collections.shuffle(v);="" if="" (v.get(999998)=""> V.get(999999)) Collections.swap(V, 999998, 999999); for (int i = 0; i < 999998; ++i) o16.tell(v.get(i)); missint[0] = missint[1] = 0; o16.missing_two(missint); test(missint[0] == v.get(999998)); test(missint[1] == v.get(999999)); system.out.println("assignment complete."); } public static void test(boolean a) { if (a) system.out.println("found!!!"); else { system.out.println("fail!"); } return; } } 999998;="" ++i)="" o16.tell(v.get(i));="" missint[0]="MissInt[1]" =="" 0;="" o16.missing_two(missint);="" test(missint[0]="=" v.get(999998));="" test(missint[1]="=" v.get(999999));="" system.out.println("assignment="" complete.");="" }="" public="" static="" void="" test(boolean="" a)="" {="" if="" (a)="" system.out.println("found!!!");="" else="" {="" system.out.println("fail!");="" }="" return;="" }="">