## CS 112 Summer 2, 2017-- Homework Three

### Introduction

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):

• All programs should be literate, i.e., easily understandable by a human (say, your grader) and follow the Java Style Guidelines for CS112 posted on the class web site;
• All files for this homework should be submitted using WebSubmit, following the instructions on the class web site;
• You may not use data structure libraries such as ArrayList, since we are learning to write Java from the ground up and you must learn how these libraries are built; however, you are free to use (unless specifically directed otherwise) the basic libraries String, Character, Scanner, and Math; You may use the toString(...) method from the Arrays library if you wish (following from Lab 03), EXCEPT when specifically forbidden to do so.
• You may freely use code from the class web site, the textbook, or lecture (unless specifically directed otherwise) as long as you cite the source in your comments; but you may NEVER use code from the web or other students' programs---this will be considered plagiarism and penalized accordingly.

## Part A: Analytical Problems (12 pts)

1. For each function f from the following list of functions, determine which g makes the equality f(n) = O(g(n)) true. The point of representing a function in this form is to create the simplest possible function g(n), e.g., do not include a coefficient in g(n), since it does not matter. Represent your answer as an equality (e.g., p(n) = O(n2)). To be clear, the correct answer to the first function is shown.

Write your solutions in a text file hw03.txt.

a(n) = 8n + 3 = O(n)
b(n) = 12n + n2 + 64
c(n) = 2log(n) + n
d(n) = log(n) + 2
e(n) = sqrt(2n)

2. Using O(....) notation, determine the number of times the `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.

3. Using O(....) notation, determine the number of times the `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.

4. Perform this code for insertion sort on the following input array, showing the array after every swap.

``````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:

5. ``````+-------------------+
| 3 | 5 | 8 | 2 | 1 |
+-------------------+
``````
6. Perform selection sort on the following input array, showing the array after each swap.

``````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 |
+-------------------+
```
```
7. Now perform merge sort on the following input array, showing each subarray after it is merged with another subarray (you will sort all sublists of size 1, then of size 2, and finally of size 4).

```+-------------------------------+
| 9 | 5 | 3 | 2 | 1 | 8 | 7 | 4 |
+-------------------------------+

```

## Part B: Programming Problems (88 points)

### Problem B.1: Lab Problem (8 points)

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.

### Problem B.2: Big Int Library: Creating your own static library class (40 points)

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.

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:

• You should examine the method stubs and fill them in with appropriate code to implement the functionality described above.
• Use my descriptions above (edited or expanded as you wish) as comments before each of the methods; any lines the seem to require more explanation (e.g., to yourself trying to understand what you were thinking, 2 years from now at 4am).
• You may add tests to the main method as you develop your code, but remove them before submission.
• Remove any debugging code before submission.

### Problem B.3: Set Data Type: Creating a dynamic Abstract Data Type (40 points)

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.

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:

• You should examine the method stubs and fill them in with appropriate code to implement the functionality described above.
• Use my descriptions above (edited to remove my comments on how to implement!) as comments before each of the methods; any lines the seem to require more explanation (e.g., to yourself trying to understand what you were thinking, 2 years from now at 4am).
• You may add tests to the main method as you develop your code, but remove them before submission.
• Remove any debugging code before submission.

### Submission Checklist

Submit the following files.

1. `hw03.txt`
2. `FindMaximum.java`
3. `BigInt.java`
4. `Set.java`

Be sure to do the following:

• You have read the Java Style Guide for CS112 (linked on the class web page), and followed all guidelines regarding format, layout, spaces, blank lines, and comments;
• You have removed or changed all comments inherited from my templates which do not relate to your solution;
• You have verified that your program for B.2 and B.3 satisfy all the performance tests in the templates;
• You have kept your debugging code in PalindromeRedux.java but removed them from all other submissions.