CS 112 Summer 2, 2017-- Homework Three

Due Thursday, July 13th at 12 midnight

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

 

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

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.

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:

 

Submission Checklist

Submit the following files.

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

Be sure to do the following: