Each assignment (including this one) includes a .java file with methods that you can use to check your code. I will run these checks when grading, so be sure that they run before you submit your solutions. I'll also check your code manually to ensure that your solutions are correct.

Here are a few tips for using the checks:

Follow the instructions carefully. The checks call methods that you will write. So, method names and parameter orders must be exactly as specified in the assignment details for checks to work.

Don't put your class code in named package. In other words, leave the package name blank when creating a class.

Import checks one at a time. If you include all checks before you start programming, you will see a lot of syntax errors since the checks call methods that you have not implemented yet. So, include checks one at a time as you work on each problem. The easiest way to do this would probably be to create your own class with a main method for each problem. Then, copy and paste the relevant check method for a problem from the provided .java file into your class that contains your main method.

Write your own checks too. My checks only test that you have completely solved a problem. It is helpful to test bits of code as you write it. So, as you solve each problem, it will be helpful to create your code to test your code. If you pass the checks, you do not need to turn in your test code.

Try lots of examples to test your code. Feel free to modify my checks to thoroughly test your code. Keep in mind that I will run the original checks when grading.

Problems

Here are the problems for Assignment 1. If you have any questions, please let me know or post a question on Discord!

Problem 1

Merging two ordered arrays is a process of combining the two arrays into one array. The new array should contain all elements of the two arrays in order.

For example, assume two sources arrays are:

srcArray1: 12 28 30

srcArray2: 2 4 11 19 25 50 89

Then, the returned destination array should be:

destArray: 2 4 11 12 19 25 28 30 50 89

Create a class called "ArrayMethods" and add a static merge method to the class. Start with the following method definition:

 public int[] merge(int[] srcArray1, int[] srcArray2) { // TODO your code here... }

The method should merge the input the input arrays into a single return array. The method should be called like this:

 int[] = destArray ArrayMethods.merge(srcArray1, srcArray2);

After the method call above, destArray should be a new array that is the merge of srcArray1 and srcArray2.

Merge will come up again in an algorithm called "merge sort". Your algorithm should have a O(srcArray1.length + srcArray2.length) runtime.

Problem 2

UnorderedArray is a partially-filled array. The underlying array that stores values has a fixed size called the "capacity". Currently, the number of elements inserted into the UnorderedArray cannot exceed the capacity. Let's upgrade UnorderedArray so that as elements are inserted, if the number of elements to be inserted is greater than the capacity, the underlying array of values is resized and the capacity is increased.

Suppose we have an array with capacity 5 and elements 3, 1, 4, 1, 5.

Note that the number of elements is 5 and capacity is 5. So, if we try to add another number, we will need to resize the array. Let's consider a couple of different ways of resizing the array.

We could increase the size by 1. So, adding a 9 would give a new resized array 3, 1, 4, 1, 5, 9. The capacity is now 6.

We could double the size of the array. So, adding a 9 would give a new resized array 3, 1, 4, 1, 5, 9, 0, 0, 0, 0. Notice the capacity is now 10.

Which method is better? Method 1 uses less space than Method 2, but generally Method 2 requires less resizes if we insert lots of numbers. To see this, consider inserting 100 more values. To do this, Method 1 would require 100 more resizes, but Method 2 would only require 4 more resizes. (Why only 4?)

In class, we will see how to analyze each method to see that Method 2 is generally much faster than Method 1. Another way to see that Method 2 is faster than Method 1 is to benchmark each method. This is what you will do for this problem.

Add two methods to UnorderedArray that implements each resize method discussed above called "insert1" and "insert2". The method insert1 should implement Method 1, and insert2 should implement Method 2. Here are definitions for these methods.

 public void insert1(long value) // put element into array and increase capacity by 1 if needed public void insert2(long value) // put element into array and double capacity if needed

Once you have implemented and passed the checks for both of these methods, run the method called "compareInsertRuntimes" in Assignment1Checks.java to get a run-time comparison between each insert method. If you have a very fast machine, you may need to tweak the compareInsertRuntimes method to see a difference between insert1 and insert2.

Problem 3

In Module 2 we discuss 3 different simple sorting algorithms. Another simple sort is the odd-even sort. The idea is to repeatedly make two passes through the array. On the first pass you look at all the pairs of items, a[j] and a[j+1], where j is odd (j = 1, 3, 5, ). If their key values are out of order, you swap them. On the second pass you do the same for all the even values (j = 2, 4, 6, ). You do these two passes repeatedly until the array is sorted.

Add a method called oddEvenSort to the SortableArray class that implements the algorithm above. Make sure it works for varying amounts of data. Youll need to figure out how many times to do the two passes. Add a comment above your oddEvenSort method with the worst case run-time for oddEvenSort in big-O notation. Here is a method definition to get you started.

 // Worst case run-time is O( TODO ) public void oddEvenSort() { // TODO }

The odd-even sort is actually useful in a multiprocessing environment, where a separate processor can operate on each odd pair simultaneously and then on each even pair. Because the odd pairs are independent of each other, each pair can be checkedand swapped, if necessaryby a different processor.