Homework 4: My Linked List

Due October 21 @ 8:00pm on Autolab

1. Introduction

In this assignment, you’ll be adding more methods to the MyLinkedList class we developed in class. When you’re done, you’ll have a pretty good start on a fully-fledged generic linked list class!

Download the pre-prepared Eclipse Project hw4.zip and import it into Eclipse using these instructions. You will make all of your changes inside of the Java files in this project.

2. The New Methods

The new methods you need to write are as follows:

3. Note on Efficiency

Three of the methods listed above have efficiency requirements. The Autograder will test the efficiency of those methods in order to ensure your implementation is \(O(N)\).

To test your complexity, we time how long the method takes to run on a list with 200,000 elements. Next, we time and run it again with a list twice that size. We then divide the two times to get your speed ratio. If your method is \(O(N)\) then your speed ratio should be \(\approx 2\). (Because if we double the input, the time to run should double as well.) If your speed ratio is 3 or less, the Autograder will accept your efficiency.

This method of determining your speed ratio is not an exact science, and your speed ratio will vary a little bit between two runs, even if your code hasn’t changed. If you fail the testcase with a speed ratio close to 3 (such as 3.1), consider resubmitting so that Autolab will try again. It might be below 3 the next time. (If your ratio is much higher than 3, or the testcase times out, then you’ll need to rework your implementation.) You have a few extra submissions to account for this.

If you code is much slower than \(O(N)\), such as \(O(N^2)\), then the time to complete an operation on a 200,000 item list will be very high. As such, the testcase will simply timeout after 10 seconds and you’ll see a message indicating that a timeout occurred. This means your solution is not efficient enough.

4. Bonus Method

This assignment includes one bonus method worth up-to three points. It will be manually graded.

void reverseInPlace()
This recursive method modifies the contents of the original list. It does not add new values to the list, but it does change their position. The first value should become the last one; the second value becomes the next to the last one, etc. until the last value in the original list becomes the first one in the modified list. It does nothing if the list is empty. You cannot create any new nodes when writing this method, nor modify any data fields of existing nodes (but you can declare as many local variables as you want that store references to nodes); you can only manipulate references to nodes.

This will be manually graded, meaning Autolab will not provide you feedback about this method. In addition, we did not include a placeholder for it in the skeleton code. You need to properly place it, name it, etc. In order to receive the bonus points:

  1. Your solution must be substantially recursive.
  2. You must include a testcase for it.

5. Grading and Submission

There are multiple parts of the grading of this assignment:

  1. For the first 90 points, your submission will be auto-graded on Autolab.
  2. For the next 5 points, your submission will be manually graded to check for good implementation methodologies. (Did you use a good approach to solving the problems?)
  3. For the next 5 points, your submission will be manually graded to check for good testcases that you include in the main method. (Do you have 2-3 basic testcases for each method, and do they all execute automatically?)
  4. Your code will also be checked for style. The parts of style that can be checked automatically (things like spacing, indentation, the use of CamelCase, etc.) are automatically checked by the autograder. Other parts of style, such as choosing good variable names, will be checked manually. Autograded style guide violations can result in, at most, -10 points. Manually checked style guide violations can result in, at most, -5 points.

You will submit your program to Autolab. Login to the system and you will see the homework.

For this homework you’ll need to submit a zip file containing your code. Lucky for you, however, Eclipse can create this zip file for you. Check out these instructions. On Autolab, you’ll submit that exported zip file. On the page that follows your submission you will see your live score (out of 90). It may take up to a few minutes for your score to appear, during that time just hit refresh in your browser. If you receive a lower score than you expect, you can click on the score to see the feedback from the autograder.

For this assignment you have 20 submissions. Please note that you will likely need to use some of these in order to properly determine the exact exceptions that you will need to raise in error situations. You may also need some if your efficiency is border-line and you need to submit a few times. Make sure to save submissions for this purpose.

5.1. Testcases

In this homework we are not providing any testcases for the new methods. We do, however, provide some basic testcases for the methods already provided.

You need to write at least two testcases for each of the new methods listed above. (This is a total of 16 test cases you write.) One of those testcases should test basic functionality, and the other should test an error condition of some sort. All of your testcases should be in the MyLinkedListTester class included with the skeleton code. You must follow the model of our testcases (meaning you print when you start, print when you finish, etc.) Additionally, you must comment each testcase with a note describing what it tests.

6. Restrictions

You may only use the following Java libraries in this assignment:

java.util.ArrayList

7. Important Notes