I suggest you read this whole assignment carefully and for Part B, it is definitely worth thinking about your solution for a bit before launching Eclipse and beginning to type. In addition to the requirements for the Java problems, you must observe the following requirements (for all homework submitted in this course):
a(n) = 8n + 3 = O(n)
b(n) = 12n + n^{2} + 64
c(n) = 2log(n) + n
d(n) = log(n) + 2
e(n) = sqrt(2n)
count()
function is called when the following code fragment runs, in terms of
the variable n
.
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < j; k++)
count();
Include a short explanation of your answer by explaining how many times each loop iterates.
count()
function is called when the following code fragment runs, in terms of
the variable n
.
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < n; j++)
for (int k = 0; k < 1000; k++)
count();
Include a short explanation of your answer by explaining how many times each loop iterates.
public static void insertion(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1])
swap(arr, j, j - 1);
// show array here
}
}
}
Execute the algorithm on the following input:
+-------------------+ | 3 | 5 | 8 | 2 | 1 | +-------------------+
public static void selection(int[] arr) {
int k;
for (int i = 0; i < arr.length; i++) {
k = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[k])
k = j;
}
swap(arr, i, k);
// show array here
}
}
Execute the algorithm on the following input:
+-------------------+
| 9 | 6 | 4 | 2 | 3 |
+-------------------+
+-------------------------------+ | 9 | 5 | 3 | 2 | 1 | 8 | 7 | 4 | +-------------------------------+
Hand in your debugged code, with all debugging statements (e.g., db(.....)) in place and debug set to true, as FindMaximum.java
. Upload your file into the hw03 directory, NOT lab02.
In this problem you are going to practice creating a static library (like Math) to solve the problem that in Java the int
type can only represent integers in the range [-2,147,483,648 . . 2,147,483,647]; this is not big enough for storing, for example, the population of Earth (7.125 billion). The Java libraries contain a class BigInteger
to solve this problem, but we are going to write our own library, BigInt
, with only some of the functionality of the Java library. Note that this library, like Math, is a static container for methods; all the members of the class will be static.
Representation of Big Integers by Arrays of Digits
We will represent our big integers by large arrays (we will use arrays of size 20, but they could be larger) of integers representing individual digits:
public static final SIZE = 20; // this gives the length of the arrays, and will occur in BigInt as a constant .... public static int A[] = new int[BigInt.SIZE]; // this is an example of an array -- it will not occur in the class BigInt
An integer such as 57431 is represented by an array A containing integers which are in the range [0 -- 9] (i.e., digits) with as many leading zeros as necessary to fill up the entire array:
00000000000000057431 would be presented as 0 1 2 14 15 16 17 18 19 +----------- ------------------------+ A: | 0 | 0 | 0 ....... | 0 | 5 | 7 | 4 | 3 | 1 | +----------- ------------------------+
The int
s in the array must all be single digits. Note that the BigInt for 0 will have
SIZE-1 leading 0's and the last digit will be a significant digit, not a leading 0. We will not represent negative integers. We will also use a "Error Big Int" called NaBI (Not a Big Int) consisting of a -1 in slot 0, with the remaining values set to 0:
0 1 2 14 15 16 17 18 19 +----------- ------------------------+ NaBI: |-1 | 0 | 0 ....... | 0 | 0 | 0 | 0 | 0 | 0 | +----------- ------------------------+
The Methods of the BigInt Static Library
The library will contain the following methods, which assume that the integer arrays are of length SIZE.
public static int[] intToBigInt(int n) -- Convert the integer n into a big integer; if n < 0, then return NaBI; note that n won't overflow the array, since it's an int. public static int[] stringToBigInt(String s) -- Convert the String s into a big integer; if s does not represent a legal big int (i.e., contains a character other than '0' .. '9' or is longer than SIZE characters) return NaBI. public static String bigIntToString(int[] A) -- Return a String representation of the big integer (with leading zeros suppressed); if any member of A is NOT a digit (e.g., is negative or > 9) return "NaBI". public static int compareTo(int[] A, int[] B) -- Compare the two big integers A and B and return -1, 0, or 1, depending on whether A < B, A == B, or A > B, respectively. public static int[] add(int[] A, int[] B) -- Add two big integers and return a new array representing their sum; if the result overflows, i.e., contains more than SIZE digits, return NaBI.
You must complete the template code BigInt.java to implement your solution.
Algorithms
The algorithms for manipulating these big integers are simply adaptations of the rules for addition and comparison of integers. To compare two big ints, simply go through the two arrays from the left to right, and when you get to two digits which are different, return -1 (if the digit in A is smaller) or 1 (if the digit in A is bigger); if you get to the end of the arrays and all the digits are the same, return 0.
To add two arrays of digits, we must go from right to left through the arrays, adding the digits and keeping track of the carry at each point:
carry: 1 0 1 1 -----------------------+ ... 0 | 5 | 7 | 3 | 3 | 9 | equals 57339 -----------------------+ -----------------------+ ... 0 | 0 | 4 | 5 | 9 | 8 | equals 4598 -----------------------+ -----------------------+ sum: ... 0 | 6 | 1 | 9 | 3 | 7 | equals 61937 -----------------------+
The addition will overflow (create a number larger than 20 digits) if the sum of the left-most two digits is larger than 10, in which case you should return NaBI.
Completing your Solution
You must fill out the "stubs" in the template BigInt.java
. Note that this template will compile, because I have added dummy return statements just for that purpose; obviously you will need to change these when you add your code.
You must follow these requirements for this problem:
In this problem, we are going to to create an Object to represent a set of integers. In mathematics and computer science, a set is a collection in which order does not matter and there are no duplicates. You will write a program Set.java
which implements sets using arrays. Each instance of the Set class will be an object representing a set. The only member of the class which will be static is the main method, which contains the testing code. The template for this class is here: Set.java.
We will represent our sets by arrays of arbitrary size (but starting with size 10) with a pointer next indicating the next available slot in the array after all the elements of the set:
private final int SIZE = 10; // initial length of the array, may be resized private int[] S; // array holding the set private int next; // pointer to next available slot in array
Thus, a set [ 2, 3, 7, -3 ] would be represented as follows:
and the empty set [] would be represented as:
The idea is that you can represent a set of up to SIZE integers, and they are stored, without duplicates, in the indices from 0 to next-1. The values from next to S.length-1 do not matter--they do not need to be 0s. When manipulating the array using a for loop, you should use next as the for loop bound, NOT S.length.
The Methods of the Set Object
You must write the following methods, which are provided as stubs in the template linked above:
public Set() -- Default constructor; constructs this set as an instance of the empty set. public Set(int[] A) -- Construct this set consisting of exactly the elements of A (which, you may assume, does not have duplicates); A can be of arbitrary length (it may not be smaller than SIZE). (Hint: create an empty set and use insert(...) to add the elements, which may trigger a resize of the array.) public Set clone() -- Return an exact copy of this set (hint: use the previous constructor). public String toString() -- Return a string representation of this set, e.g., [2,3,7,-3] or []; you may not use Array.toString(...) to do this; you may create a char array from the array S and use the String constructor (which will accept a char array as initializer), or you may build up the String one character at a time using concatenation. public int size() -- Return the number of elements in this set. public boolean isEmpty() -- Return true if this is the empty set (has no members) and false otherwise. public boolean member(int n) -- Return true if n is in the set and false otherwise. public boolean subset(Set T) -- Returns true if this set is a subset of T, that is, every member of this set is a member of T, and false otherwise. (Hint: use member.) public boolean equal(Set T) -- Returns true if this set and T have exactly the same members. (Hint: use subset.) public void insert(int k) -- If the integer k is a member of the set already, do nothing, otherwise, add to the set; if this would cause an ArrayOutOfBoundsException, call resize() (provided in template code) to increase size of array before doing insertion. public void delete(int k) -- If the integer k is not a member, do nothing; else remove it from the set; you must shift all elements which occur after k in the array to the left by one slot. public Set union(Set T) -- Return a new set consisting of all of the elements of this set and T combined (without duplicates). (Hint: make a clone of this set, and insert all elements of T into the clone.) public Set intersection(Set T) -- Return the intersection of this set and T. (Hint: make a new empty set, and for every element of this set, if it also occurs in T, insert it into the new set.) public Set setdifference(Set T) -- Return the setdifference of this set and T. (Hint: make a new empty set, and for every element of this set, if it does NOT occur in T, insert it into the new set.)
Important Note: The last three methods should make new sets, and NOT modify their input sets in any way! Insert and delete will modify the set. Look for opportunities (suggested in the hints) to reuse your own code by implementing methods by using other, simpler methods. For example, equals can be implemented simply (one line of code) using two calls to subset, and setdifference is VERY similar to intersection!
Note that there is no requirement for error checking in this assignment.
Note that we will be using array resizing to handle the problem of overflow -- I have provided a method resize() in the template and specified when it should be used (in insert); we will discuss this in lecture soon, but you do not need to know the theory to simply use the method.
Completing your Solution
You must fill out the "stubs" in the template Set.java
linked above. Note that this template will compile, because I have added dummy return statements just for that purpose; obviously you will need to change these when you add your code.
You must follow these requirements for this problem:
Submit the following files.
hw03.txt
FindMaximum.java
BigInt.java
Set.java
Be sure to do the following: