Problem Set 4

due by 11:59 p.m. on Sunday, March 3, 2019

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email course instuctor.

Make sure to submit your work using gsubmit, following the instructions found at the end of the assignment.

Part I

40 points total

Problem 1: A method that makes multiple recursive calls

10 points; individual-only

We cover a similar problem in Lab 5 on 2/21 and 2/22.

Put all of your work for this problem in a plain-text file named ps4pr1.txt.

A number of the algorithms that we consider in CS 112 involve recursive methods in which a given invocation of the method may make two or more recursive calls. To understand how this type of algorithm works, it helps to draw a call tree for a given set of initial parameters.

In this problem, you will draw such a call tree to illustrate the execution of a simple recursive method that operates on integers. You may find it helpful to review our solutions to the similar problem in Lab 5 problem before continuing.

Here is the method you will trace:

public static int foo(int x, int y) {
    if (y == 0) {
        return x;
    } else if (x <= y) {
        return y;
    } else {
        int result1 = foo(x - 1, y - 1);
        int result2 = foo(x - 1, y + 1);
        return result1 + result2;
    }
}

Assume that we begin with the following initial call to this method:

foo(5, 3)

1. Construct a call tree that shows each invocation of the method, and that uses lines to connect a given invocation to the recursive calls that it makes (if any). Follow the same format that we use in our solutions for Lab 4, Task 1.

   In particular, you should:

   • Begin by copying the following initial diagram into your ps4pr1.txt file:

                                      1:foo(5,3)
                                     /          \
                                    /            \
                                   /              \
     

   • Add each subsequent call with its parameters to the call tree in the appropriate place.

   • If a given call is a base case, simply put its return value under the call, as we do in our Lab 4, Task 1 solution for calls to fib(1) and fib(0).

   • If a given call is not a base case, use lines composed of / or \ characters to connect the call to the recursive call(s) that it makes.

   • Precede each call with a number that indicates the overall order in which the calls were made.

2. Underneath your call tree, list the order in which the calls return, as well as their return values. When you refer to a given call in this part of the problem, use its number from the call tree.

   For example, the initial call always returns last, so the last line in this part of the problem should look like this:

   call 1 (foo(5,3)) returns ...
   

   where you replace the ... with its return value.

   See our solution for Lab 4, Task 1 for another example of what this part of your solution should look like.

Problem 2: Sum generator

16 points total; 4 points each part; individual-only

We will begin our coverage of algorithms on Tuesday’s lecture.

Let’s say that you want to implement a method generateSums(n) that takes an integer n and generates and prints the results of the following series of sums:

1
1 + 2
1 + 2 + 3
...
1 + 2 + ... + n

For example, generateSums(4) should print the following:

1
3
6
10

and generateSums(6) should print the following:

1
3
6
10
15
21

One possible implementation of this method is the following:

public static void generateSums(int n) {
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= i; j++) {
            sum = sum + j; // how many times is this executed?
        }
        System.out.println(sum);
    }
}

1. Derive an exact formula for the number of times that the line that increases the sum is executed, as a function of the parameter n.

2. What is the time efficiency of the method shown above as a function of the parameter n? Use big-O notation as we did in lecture, and explain your answer briefly.

3. Create an alternative implementation of this method that also uses iteration (i.e., you should not use recursion) but that has a better time efficiency.

4. What is the time efficiency of your alternative implementation as a function of the parameter n? Use big-O notation as we did in lecture, and explain your answer briefly.

Problem 3: Sorting practice

14 points; 2 points for each part; individual-only

We will cover all of the sorting algorithms mentioned in this problem by Thursday February 28.

Important: When answering these questions, make sure to apply the versions of these algorithms that were discussed in lecture. The Java code for each algorithm can be found in our Sort class.

Given the following array:

{14, 7, 27, 13, 24, 20, 10, 33}

1. If the array were sorted using selection sort, what would the array look like after the third pass of the algorithm (i.e., after the third time that the algorithm performs a pass or partial pass through the elements of the array)?

2. If the array were sorted using insertion sort, what would the array look like after the third iteration of the outer loop of the algorithm?

3. If the array were sorted using insertion sort, what would the array look like after the fifth iteration of the outer loop of the algorithm?

4. If the array were sorted using bubble sort, what would the array look like after the second pass of the algorithm?

Part II

60 points total

Problem 4: Set Class: Creating another Custom Data Type

40 points total; individual-only

Overview

In mathematics and computer science, a set is a collection in which order does not matter and there are no duplicates.

In this problem, we are going to to define a class which wil allow us to create an object to represent a set of integers. You will write a program Set.java to define the class Set. Each instance of the class Set will be an object representing a set of integers.

The only method of the class which will be static is the main method, which contains the testing code. All other methods written will be instance methods of the class.

The Set class will represent our sets using integer arrays of arbitrary size (but starting with size 10). The class will also maintain an index (i.e. pointer) next indicating the next available slot in the array:

private int SIZE = 20;        // initial length of the array, may be resized
private int[] set;            // 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 Methods of the Set Class

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 or 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 i
   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.)

Completing your Solution

Begin by downloading the template: Set.java. As with BigInt, this template will also compile because of the dummy return statements just for that purpose; again you will need to change these when you add your code to implement the methods as specified above. You can also download the file DriverForSet.java which contains a main program that you can use as a guide to incrementally test the methods of your set class.

Problem 5: Finding pairs that sum to k

20 points total; individual-only

Suppose you are given an array of n integers, and you need to find all pairs of values in the array (if any) that sum to a given integer k. In a class named PairFinder, write code that performs this task for you and outputs all of the pairs that it finds. For example, if k is 12 and the array is {10, 4, 7, 7, 8, 5, 15}, your code should output something like the following:

4 + 8 = 12
7 + 5 = 12
7 + 5 = 12

Note that we get two 7 + 5 sums because 7 appears twice in the array. However, while the methods that you write may print a given pair of values more than once in such cases, it is not necessary to do so. In addition, the order in which the sums (and the terms within each sum) are printed does not matter. If no pairs are found, the methods do not need to print anything.

1. Implement a static method named findPairSums() that requires O(n²) steps to solve this problem. The method should have the following header:

   public static void findPairSums(int k, int[] arr)
   

   In addition, you should add test code for it to a main method. You may find it helpful to call the randomArray() method from our SortCount class to generate test arrays, although it also makes sense to use literal arrays that you define.

2. Implement a static method named findPairSumsFaster() that takes the same parameters as findPairSums, but that requires only O(nlogn) steps in the average case to solve this problem. (Hint: you should begin by sorting the array using one of the methods from our Sort class. Once you have done so, only O(n) additional steps are needed to find the pairs.) Here again, you should add test code to the main method.

• You have read the Java Style Guide (linked on Course page)and followed all guidelines regarding format, layout, spaces, blank lines, and comments;
• ensured that the signature of the methods specified in the assignment have not been changed.
• You have verified that your programs satisfy all the performance tests in the templates;

Follow the instructions and submit the following files:

• your ps4pr1.txt file containing your solutions for Problem 1
• your ps4pr2.txt file containing your solutions for Problem 2
• your ps4pr3.txt file containing your solutions for Problem 3
• your Set.java file containing your solutions for Problem 4
• your PairFinder.java file containing your solutions for Problem 5