CSE 373 Winter 2017: Homework 6 - Sorting

Overview

Overview:

Your task is to use comparison sorting to unscramble pieces of images that your program will download from a remote server. You will compare the performance of two sorting algorithms, SelectionSort and MergeSort. In order to accomplish this, you will first implement the sorting algorithms for Integers. This is the required starting point, because it will be much easier for you to debug and test your code on Integers. Once your sorts are working with integers, you will implement both sorts for the Packet class that we provide.

Once you have completed your implementation you will be able to use the code we provide along with your sorting algorithm to unscramble the pieces of image that you receive.

You have been given skeleton code to assist you in the sorting. We have provided implementations of InsertionSort for Packets and Integers as an example. In addition, all of the code necessary to download the pieces of the images is also provided for you.

Suggested Steps:

1. Download the skeleton code.
2. Write sorting for integers:
   1. Navigate to the IntegerComparator.java class and make sure you understand how comparators are used in sorting.
   2. Implement the method stubs for mergeSort and selectionSort in IntegerSorter.java
   3. Verify that the test files TestIntegerSelectionSort and TestIntegerMergeSort pass.
3. Write sorting for packets:
   1. Implement the compare method stub inside the PacketComparator.java class.
   2. Verify that the tests in TestPacketComparator pass.
   3. Implement the method stubs for mergeSort and selectionSort in PacketSorter.java. (You can copy your work from integers).
   4. Verify that the test files TestPacketSelectionSort and TestPacketMergeSort pass.
4. Render an image:
   1. Set MY_STUDENT_NUMBER equal to your student number in PacketReceiver.java.
   2. Implement the main method stub inside ImageDownloader.java, which will download and unscramble the image for display. Refresh your Eclipse project (File -> Refresh) to load the image that was produced. NOTE: You must have access to Internet to complete this step.
   3. Run the main method inside ImageDownloader.java, sorting using your selectionSort, and verify that it produces the correct image. You should look for it inside the root directory.
   4. Run the main method inside ImageDownloader.java but this time use your mergeSort.
5. Complete the rest of the writeup

Background Knowledge: Comparators

Many sorting algorithms make use of Comparators, and so you will be making use of these objects in the sorting algorithms you implement. Comparators are objects that are used to compare two objects. They have a single method, compare, which takes two parameters: the two objects to compare. The purpose of this method is to decide which one of the parameters is considered "larger" The specification of the compare method requires simply that it returns an integer greater than 0 if the first parameter is larger; return 0 if the two parameters are considered equal; return an integer less than 0 if the first parameter is considered smaller.

Your sorting algorithms will take as a parameter a Comparator, and it will use this Comparator's compare method to execute all comparisons. Comparators are useful because they abstract away the comparison itself. It is completely up to the comparator to decide what it means to be "larger". This adds flexibility because you can use the same sorting algorithm to provide a different sorted order based on the comparator that is passed as a parameter. For instance, you can sort Integers in reverse order by passing in a Comparator whose compare method reverses our perception of numerical comparison. Comparator objects implement the Comparator interface. As an example, in this assignment you will use IntegerComparator, which implements Comparator.

Background Knowledge: Calling Static Methods

You have called static methods in Java without realizing it, but it is something that you should be aware of for this assignment. A great example is something like Math.min(). The Math class contains a static method min(). To call a class's static method, you specify the class name, a dot, and then the static method name. So, for the case of the min() method of the Math class, you would write Math.min(4, 92). More examples can be seen with the SortingUtility.java from the JUnit and Testing lecture.

You will have to call several static methods in the ImageDownloader.java class. The sorting methods that you implement are static, so to call them, you will have to use this syntax. Additionally, the provided methods inside PacketRender and PacketReceiver are also static.

Background Knowledge: Data Transfer

The second portion of this assignment deals with programmatically connecting to a server to download pieces of images. This may sound overwhelming, but do not worry because we have provided all of the necessary functionality. Your job is to make the calls to the correct methods.

Correctly implementing this portion of the assignment does not require an understanding of networking and how data is sent between machines, but it may be helpful for you if you know what is happening behind the scenes. When you download something from the Internet, your computer sets up a transport connection with the machine that holds the file you are downloading. In this homework assignment, we will refer to this machine as the "server". Every file is made up of bytes. When the server sends the file to your machine, it sends it in a series of chunks, called packets. Each packet contains a small portion of the data.

Each packet is sent by the server independently. Interestingly enough, each packet may take a different route through the Internet to arrive to your machine, and each may be further fragmented into smaller chunks along the way. This introduces two levels of complexity. Because packets may take different routes, packets can arrive out of order. Since they can arrive out of order, the server sends the packets with a an index that specifies the packet's position in correct order. We refer to this index as the major index. Additionally, because each of the original packets might be fragmented by the Internet during its transport, we need to introduce one more index to distinguish between fragments that were originally part of the same packet. Other implementations may use a different means for distinguishing between fragments of the original packet, but for simplicity, we will introduce an additional index in this assignment. This will be called the minor index.

An example will make this more clear:

Let's say that you are downloading an image called puppy.jpg from the server. First, the server will split this up into some number of packets. For this example, we will say that the image is split up into 3 packets. Maybe the first packet has the top 1/3rd of the image, so it is given major index 0. The second packet has second 1/3rd of the image, and it is given major index 1, etc. Now, the server sends these 3 packets out to the Internet. Along the way, the Internet discovers that each of these 3 packets is too large! What does it do? It splits them into smaller packets. Now, the first packet (the one that had major index 0) is split into some number of fragments. Let's say that each is split into 2 fragments. This is means that the packet with major index 0 is now 2 packets, each of them with major index 0, with minor indexes 0 through 1. The first packet is also fragmented into some number of new packets, maybe 3 packets. Each of these will have major index 1 and minor indexes 0 through 2.

These packets may arrive out of order. Normally, your computer takes care of this problem for you. Your computer assembles and sorts the packets that you receive before presenting the data to you, so you have never had to think about this before.

In this assignment, you will interact with a server to receive unsorted packets. Specifically, you will be requesting an image file, and you will be implementing the protocol to sort the jumbled packets. We have provided code that you will use reassemble and render the packets once they have been sorted by you. The final result will be an image.

Provided Files

Provided Files:

You can download all the files in cse373_17wi_hw6_supplied.zip. Only this zip has the provided JUnit test suite; for more information on JUnit testing, see testing section below. See the expectedImage.jpg here.

1. IntegerComparator.java.

   This class is fully implemented. The IntegerComparator we provide for you is simple, and it compares integers using our classic intuition of what it means for one number to be larger than another. The sorting algorithms you write will take a comparator as a parameter, and you must use this comparator to execute each comparison..

2. IntegerSorter.java.

   This class contains two methods that you will implement, selectionSort and mergeSort. These methods will take as parameters an array of Integers and a Comparator. The selectionSort method will sort the integers using the selection sort algorithm, whereas the mergeSort method will use the merge sort algorithm. See lecture slides and the text book for details on this. We have provided an implementation of insertionSort for your reference.

3. Packet.java.

   This java object is a representation of the network Packet described in the Background Knowledge: Data Transfer section of this specification. Each packet has a major and minor index, as described above. In addition, each packet as an array of bytes. However, for the purposes of this assignment, you will only be dealing with the major and minor indexes. You will not need to use the byte[] array for anything, as this code is implemented for you.

4. PacketComparator.java.

   This class has the compare method that will be used to compare Packet objects. You will implement this method.

5. PacketSorter.java.

   This class is very similar to IntegerSorter but it is for sorting packets. It contains two methods that you will implement, selectionSort and mergeSort. These methods will take as parameters an array of Packets and a Comparator. The selectionSort method will sort the Packets using the selection sort algorithm, whereas the mergeSort method will use the merge sort algorithm. You will pass these methods an instance of your PacketComparator.

6. PacketReceiver.java.

   This class is what you will use to download the packets from the server. There are two static methods, receivePackets() and receivePackets(int seed). The first will request that the server sends the packets in any order. This is the method that you should be calling in your final implementation. However, to make debugging easier for students, there is an additional static method that takes a seed as a parameter. A seed is used to eliminate randomness. Using this method will ensure that the server is consistent in how it randomizes the packets. You may choose any seed for debugging.

   For an example of how seeds work, consider this program:

   int mySeed = 502;
Random r = new Random(mySeed);
System.out.println(r.nextInt(100));
System.out.println(r.nextInt(42));
System.out.println(r.nextInt(934));

   This chunk of code will always print out 43, 12, 811, no matter how many times it is run. Without the seed, it would produce a different sequence each time

7. PacketRenderer.java.

   This class is what you will use to render the final image using the packets you have sorted. You will use the method renderPackets(Packet[] packets, String filename), which will render the packets as an image and save the final jpg to the specified file location.

8. ImageDownloader.java.

   This class has the main method stub that you will fill in. This method will make the call to receive the packets, sort them using a call to one of your sorting methods, and then display the packets using a call to renderPackets. Inside main(), you will see a String variable imageOutputFilename with the value finalImage.jpg. You should use this as the output location that you specify to PacketRenderer. Note that with Eclipse, you will find the resulting image at the top level directory (outside of src, but at the same level as src.)

In your eclipse workspace, to obtain the required files:
      file >> import >> general >> Existing Projects into Workspace >> Select archive file >> cse373_17wi_hw6_supplied.zip

Functionality

Required Public Functionality

PacketComparator class

IntegerSorter class

PacketSorter class

A note about ascending order:
When the method is finished, it should be true that: comparator.compare(array[i - 1], array[i]) <= 0 for all i from 1 through array.length.

ImageDownloader class

Implementation Hints

Implementation Hints

We strongly advise that you get your IntegerSorter methods working before you start implementing the PacketSorter methods. We even suggest that you copy your methods from IntegerSorter over to PacketSorter. If this makes you cringe, see the Extra Credit section!

Don't get overwhelmed by the number of files and the size of the specification. The complexities are handled by the provided code.

To help you understand how all the pieces interact, refer to this diagram:

As you can see, ImageDownloader will receive the packets from PacketReceiver. The ImageDownloader will ask PacketSorter to sort the packets, and then finally it will ask PacketRenderer to output the image as finalImage.jpg.

Style: For this assignment we will be grading similarly, but make sure that you are implementing the correct sorting algorithms!. The tests will pass as long as your sort works, but they will not check, for example, that you implemented mergesort instead of quicksort, so make sure that your implementations are the correct sorts. Make sure you are commenting your code, looking for structural mistakes, correctly formatting of your code, and taking note of the efficiency of your algorithms. We have provided the comments on all public functionality, but please comment any complex lines of code you write.

Reporting Outages

Reporting Outages

Since you are interacting with a remote server, and because there are 200 of you, it is possible that the server will crash from over-use. If you are getting exceptions from the server when you run your ImageDownloader, please post in the message board in the Assignment 6 thread, specifying the exception and any other relevant details.

Testing

Testing

We have provided a test suite. The tests are not meant to be exhaustive, and you are encouraged to add more of your own tests to the appropriate files. These tests are only included in the provided zip for the provided files.

The test files we have provided use a Java testing environment, called JUnit. The most recent versions of the Eclipse IDE come with JUnit configured. If you have an older version of Eclipse, you may need to add JUnit as an external jar. To do this, navigate to JUnit. Download junit.jar and hamcrest-core.jar. Now, to use JUnit, you must add these jar files to your build path. To do this, go to your Eclipse window and navigate to Project » Properties » Java Build Path » Libraries » Add External JARs and then telling Eclipse where your copies of junit.jar and hamcrest-core.jar are located.

For help on installing JUnit with JGrasp, see this old handout from CSE 143.

Running Tests

1. Right click on the package named test within the src/ folder of your Assignment6 project in Eclipse.

   

2. Click on the Run As option, and select JUnit Test.
3. You should see all the test results pop-up in a JUnit pane. Sometimes this causes your console pane to disappear. If you need to see the console again, select the Window -> Show View -> Console.
4. You can also run individual tests by right clicking them and selecting Run.

Test Suite Structure, Debugging Tests, and Adding New Tests

If you are failing tests and you want the tests to provide more information, you can add some System.out.println()'s inside the method that is failing. You'll need to see the console to view the output, so see the instructions above about viewing the console if it disappears.

It might be helpful for you to understand the test structure when you are debugging. The tests for the Integer[] sorting algorithms are in TestIntegerSortBase. All of the integer sorts extend this abstract class and override method, specificSort that makes a call to the sorting algorithm that should be tested. So, there is one base class for mergeSort, one for insertionSort, and one for selectionSort. All of the tests are contained in the base class, and this base class calls specificSort. In this way, there is one file that contains all the tests and each subclass just specifies which alogirthm is tested. This is a way of reducing the redundancy between test suites. There is a similar structure for the Packet tests. The tests are in TestPacketSortBase, and there is a subclass for each of the sorting algorithms. You can add tests to any of these files, or you can create new files! If you would like to add a test for just one of the sorting algorithms, add it to the specific class's test file. So, you could add a test to TestIntegerSelectionSort, and just selectionSort would get tested with your new test. Otherwise, you can add a test to the base class and this will mean that all three subclasses inherit your test.

To create a new test method, you must use the @Test decorator above your test method. This is what signals to JUnit that the method should be run as a test. You should not place @Test above any helper methods, or JUnit will attempt to run the helper method as a test. As a tip, after you have created a test and it passes, add a bug somewhere in your code and make sure that the test fails! If it doesn't fail, it is likely that 1) You forgot @Test or 2) the test method didn't have any assert statements.

If you want to create a new test class, follow these steps:

1. Right click again on the package named test, and this time go to New -> JUnit Test Case.
2. This will auto-generate a test stub for you.
3. Make sure that any tests you write have @Test above the method header. Otherwise, they will not be run as tests!
4. Use any number of the JUnit assert methods, including assertTrue(), assertFalse(), and assertEquals().
5. You can take a look at our tests inside TestPacketSortBase and TestIntegerSortBase for examples on how to design tests and use the asserts.

Extra Credit

Extra Credit

You may have noticed the redundancy between your PacketSorter and your IntegerSorter classes. Fortunately, it is possible to avoid such redundancy by creating generic methods. Research Java Generics and implement a new class, called GenericSorter.java with mergeSort and selectionSort that take E[] array and Comparator as parameters.

To help you research Generics in Java and to help you figure out how to write this GenericSorter.java implementation, here are some slides from CSE 331 on Generics.

Write-Up

Write-Up Questions

1. Using Quick Sort, with the median pivot rule (pick the median of: data[lo], data[hi - 1], and data[(hi + lo) / 2]), sort the following list of numbers. Show your work by drawing the tree of partitions and pivots (as seen in the lecture slides) with the partition rules discussed in lecture (swapping the pivot to index lo and doing swaps to complete the partitions). Apply a cutoff of 3 elements and sort with any sorting method.
   data= [5, 7, 9, 1, 3, 4, 6, 8, 2]
2. Using Radix Sort with a radix of 6 (letters: a, b, c, d, e, f) to alphabetically sort the following strings, draw contents of each bucket at the end of each radix 'digit' iteration pass.
   Strings = (abc, da, ffff, defcd, abebd, ca, b, fef, dfe)
3. If you did any above and beyond for extra credit, describe what you did.

Turn-In

What to turn in:

Due: Friday, March 10th, 11pm

You should submit a zip file to the Canvas dropbox with the name cse373_17wi_hw6.zip. This zip should include the following files. Files:

1. ImageDownloader.java -- with the main method stub implemented by you.
2. IntegerSorter.java -- with the selectionSort and mergeSort methods implemented by you.
3. PacketComparator.java -- with the compare method implemented by you.
4. PacketSorter.java -- with the selectionSort and mergeSort methods implemented by you.
5. GenericSorter.java (Optional) -- entire file written by you
6. Electronic version of your project report in pdf, MS word, or text format (please check with us first if you need to submit in another format).

You don't need to include the files for IntegerComparator.java, Packet.java, PacketRenderer.java or PacketReceiver since you don't have to modify those files, but you can include them if you want to.