Problem Set 3

You may work alone or with a partner on this assignment. However, in order to make sure you learn the material and are well-prepared for the exams, you should work through non-coding problems on your own before discussing them with your partner, should you choose to work with someone. Also, be sure every programming task is a team effort. In particular, the "you do these and I'll do these" approach is sure to leave you unprepared for the exams.

All GitHub repositories must be created with all group members having write access and all group member names specified in the README.md file by 4:00 PM, Wednesday, October 10, 2018. This applies to those who choose to work alone as well!

There is a significant amount of work to be done here, and you are sure to have questions. It will be difficult if not impossible to complete the assignment if you wait until the last minute. A slow and steady approach will be much more effective.

You will receive an email with the link to follow to set up your GitHub repository for this problem set (ps3-yourgitname). One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub.

You may answer the questions later in this assignment either by handing in a hard copy by the deadline, including a scan or picture of a handwritten responses in your repository, or by including responses in the README.md file in your repository. If you choose the latter, please use Markdown to format neatly. Extensive formatting is not necessary.

Question 1: Suppose you find that a method performs n/2 + 1 addition operations when its input is of size n. Give the "Big O" complexity of this method. (3 points)

Question 2: Suppose you find that a method performs n² + 20000n array assignment operations when its input is of size n. Give the "Big O" complexity of this method. (4 points)

In this section, we revisit the DoubleArrayList class from a recent lab. Start by copying your final version of that class from the lab into your repository for this problem set. The coding tasks here will be graded as a programming assignment, so style, documentation, and formatting will be considered in addition to correctness.

Suppose we wish to implement a destructive method of this class to reverse the order of the values in the data structure. We will consider two ways to implement this. In one, a new internal array will be created, the values copied to it in reverse order, and the new array will be come the DoubleArrayList's internal array. In the other, values we be rearranged "in place", with no array space allocated, even temporarily.

Programming Assignment: Write the methods reverseWithCopy, which uses a new internal array, and reverseInPlace, which rearranges values in place, and a thorough set of tests in a main method, all in your DoubleArrayList class. (see grading breakdown for points)

For simplicity when answering the questions below, assume that the size and capacity of the DoubleArrayList are both n, that is, there are no unoccupied slots in the internal array.

Question 3: How many array accesses are needed for each of these reverse methods when called on a DoubleArrayList with size n? Also give the "Big O" complexity of each in terms of n. (6 points)

Question 4: How much extra storage (number of double values) are needed for each of these reverse methods when called on a DoubleArrayList with size n? Also give the "Big O" complexity of each in terms of n. (6 points)

Now, we turn our attention to recursion. The programming for this section will be graded as practice programs.

We will consider the function Choose(n,k), which is the number of different ways you can choose k items from among n items. For example, if you have three items {a,b,c}, there are 3 ways to choose 2 of them: {a,b}, {b,c}, and {a,c}. So Choose(3,2) = 3.

This is a case where recursive thinking leads to an elegant solution. We can define Choose(n,k) recursively as follows: Choose(n,0) is 1 for all n >= 0, and Choose(0,k) is 0 for all k >= 1. For all n > 0 and k > 0, Choose(n,k) is equal to the number of ways you can choose k-1 items from among n-1 items added to the number of ways you can choose k items from among n-1 items.

Question 5: Compute, by hand, the values of Choose(n,k) for each of the following: n=4 and k=0, n=4 and k=1, n=5 and k=1, n=4 and k=2, n=4 and k=3. (4 points)

First, write a main method in the Choose class that prompts for and reads in two positive integers that will be used as n and k. You need not worry about error checking the input for this assignment. (2 points)

Next, write a recursive method recNChooseK that uses that formulation to compute the value of Choose(n,k). Update your main method to call the recNChooseK method on the numbers entered by the user, and print out the value returned. (9 points)

Question 7: Draw a recursive call diagram for recChoose(4,3). Note that this will be more complicated than the diagrams you have made so far, since method calls other than those that match a base case will result in two recursive calls. (10 points)

> Feature	Value	Score
Question 1	3
Question 2	4
`DoubleArrayList` `reverseWithCopy` method	10
`DoubleArrayList` `reverseInPlace` method	10
`DoubleArrayList` reverse tests	5
`DoubleArrayList` comments (include Javadoc)	4
`DoubleArrayList` naming conventions	2
`DoubleArrayList` formatting	1
Question 3	6
Question 4	6
Question 5	4
Question 6	6
`Choose` basic `main` method	2
`Choose` `recNChooseK` method	9
Question 7	10
Git commit frequency and message quality	3
Total	85