CompSci 201, Spring 2020, Exam 1 Solutions

Problem 1

Part A:

blue  blue  dukeblue  4
red  blue  blueblue  8
bat  bird  fish  5
5 9 4 3

Problem 1

Part B: 
1.
Cannot be determined.
s.equals(t) is true if the two strings have the same value. However, two
strings with different values could have the same hashcode, and then
s.equals(t) will be false.
 
2.
Cannot be determined. Strings that do not have the same values could have
the same hashcodes or not. 

3.
Cannot be determined.

s == t  could be true if they are the same memory location but
would be false if they are different memory locations.

4.
true. Strings with the same value must have the same hashcode, as a key
must be unique. 

Problem 2

Part A.
double

Part B.
Yes,  myXpos is for the current object which can also be referred to as
this, so myXpos can be refered to as  this.myXPos.

Part C.  No. Since b is an object and this is an object, this.b doesn't
make sense. That is because this "dot" should be followed by a method of
the CelestialBody class and b is not a method of that class.

Part D.
Yes. getX() returns myXPos so it can be used in place of myXPos.


Problem 3.
Part A.
a) O(n)

The for loop executes exactly n times. Inside the loop there are two
adds which both take constant O(1) time, or just 1 time each. The body
executed one time takes time 2. Thus the total time is 2+2+2+...+2, (add 2
n times) which
is 2*n, which is O(n). 

b) O(n^2)

The for loop executes exactly n times.
The first sum is the sum 0 + 1 + 2 + 3 + ... + n-1 which is (n-1)(n)/2
The second sum is n added n times, which is n*n.
The total value is the sum of the two = (n-1)(n)/2 + n*n = O(n^2).

Part B
a) O(log n)^2

The first for loop is executed in log n times, since k doubles each time.
The second for loop also executes in log n times, since j doubles each
time.
The sum takes 1 step.
Since the second loop is nested, the total time is O((log n)^2). 

b) O(log n)^2

The value of sum is one for each time the second for loop is executed,
which means its value is the same as the run time, which is O((log n)^2)

Part C
a) O(n^2)

1) The first for loop is executed n times.
2) The second for loop is executed 1 time, then 2 times, then 3 times, up to
n-1 times.
The total time the second for loop is executed is the sum of 1+2+...+n-1,
which is (n-1)*n/2.
2) The sum operation is constant, 1 step.
3) Thus the total time for all the sum operations of the first two for loops
is the total time of the second for loop which is (n-1)*n/2.
4) The third for loop is executed 2*n times. The sum in it take constant
time. The total time for all of these sum operations is 2*n.
5) The total time of the two sums operations are (n-1)*n/2 + (2*n).
The n^2 term will dominate, so this is O(n^2)

b) O(n^3)

1) The value of sum for the sum in the first two for loops is n * the total
time, which is (n-1)*n/2 given above, which equals n*(n-1)*n/2.

2) The value of sum for the sum in the third for loop is n * the total time
for that loop, which is n*2*n, which equals 2n^2.

3) The total value of sum is then n*(n-1)*n/2 + 2n^2.
The large term dominates, this is O(n^3).


Problem 4

Part A

    public Storage(int capacity, String [] items) {
        myCapacity = capacity;
        mySize = items.length;
        if (mySize > capacity) {
            myCapacity = mySize;
        }
        myItems = new String[myCapacity];
        for (int k=0; k<mySize; k += 1) {
            myItems[k] = new String(items[k]);
        }
        myUniqueItems = new HashSet<String>();
        for (int k=0; k<mySize; k += 1) {
            myUniqueItems.add(myItems[k]);
        }
    }


NOTE: You cannot throw the array myItems into the set or you will add null to
the set.

Part B
    public int getMyCapacity() {
        return myCapacity;
    }


Part C
    public int getMySize() {
        return mySize;
    }



Part D
    @Override
    public String toString() {
        ArrayList<String> all = new ArrayList<String>(myUniqueItems);
        Collections.sort(all);
        String allstr = String.join( " ", all);
        return String.format("(size: %d, unique: %d, capacity: %d, items: %s)",
             mySize, myUniqueItems.size(), myCapacity, allstr);
    }



Part E
    public void add(String item) {
        if (mySize >= myCapacity) {
            throw new IndexOutOfBoundsException("bad index in add "+mySize);
        }
        myItems[mySize] = item;
        mySize += 1;
        myUniqueItems.add(item);
    }



Part F
    public boolean updateCapacity(int newCapacity) {
        if (newCapacity <= myCapacity ) {
            return false;
        }
        String [] newCap = new String[newCapacity];
        for (int k=0; k<mySize; k++) {
            newCap[k] = myItems[k];
        }
        myItems = newCap;
        myCapacity = newCapacity;
        return true;
    }


Part G

    public int howMany(String word) {
        return Collections.frequency(Arrays.asList(myItems), word);
    }

Alternate Soln:

    public int howMany(String word) {
        int sum = 0;
	for (k=0; k<mySize, k +=1) {
            if myItems[k].equals(word) {
	       sum += 1;
	    }
        }
	return sum;
    }

Part H

    @Override
    public boolean equals(Object o) {

        Storage other = (Storage) o;
        if (other.mySize != mySize || other.myCapacity != myCapacity) {
            return false;
        }
        if (myUniqueItems.equals(other.myUniqueItems)) {
            return true;
        }
        return false;
    }

Part I

Currently the .hashcode return value is based on toString which uses the
state of the class in that string, especially the new toString implemented
on the exam, which will help spread the values out so they are more likely
spread over the hash table. Then the .hashcode operation is O(1).
If you return 10, then every object will collide in the hash table since
they all go to the same location 10 in the hashtable, making performance
slower, O(n) to look through the n items that collided.