Computer Science 210

Data Structures

Fall 2018, Siena College

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.

Getting Set Up

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.

Complexity and Big O

`ArrayList`s and Complexity

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.

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.

*n* Choose *k*

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.

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)

Grading

This assignment is worth 85 points, which are distributed as follows:

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