CPE 102

Winter 2008

Extra Credit Programming Assignment - No collaboration allowed!

Due Date

You must turn in a functionally correct program to receive any credit.  There will be only one submission due date - you must hand in your functionally correct program on or before this date.  Programs will be graded after the due date and the results will be emailed to you within a few days of that date.

100% (minus any deductions) by 9:00pm Friday, 3/14/08

No late submissions accepted!

Errata:

None

Objectives

• To implement a recursive linked-list data structure.
• To gain experience with recursion.
• To practice developing your own unit tests for code you develop.

Resources

1. Java Standard API
2. RecursiveList.java
3. JUnit API
4. AllTests.java
5. ECTestDriver.java (to be published on Monday, 3/10/08)
   

Problem Description

1. You will be implementing a recursive linked-list very similar, but not identical, to the one specified in our text in Exersize 20.10. Be sure to read the actual exercise in the text as it provides useful diagrams, discussion, and some actual code samples that you may find helpful. The differences from exercise 20.10 are:
   
   
   1. You will not implement the add(E element) method (only add(int index, E element).
   2. The return type of the set(int index, E element) has been change to E (from void in exercise 20.10).
   3. The names of the instance variables of the NonEmptyList have been changed from head and tail in exersize 20.10 to element and list, respectively, in the provided source.
   
   
2. To help you get started in the right direction - you have been provided a partial implementation of the solution. Your task is to complete it as specified. You will find additional instructions in the provided source file, RecursiveList.java.
   
   
3. You will not be provided with a test driver for this assignment. Instead, you will have to adequately test your own implementation to ensure its correctness. Submissions will be tested each night (Monday through Thursday) and, if your solution fails you will be notified by email. You will be given a general indication of what failed but it will not be sufficient for you to identify the exact fault in your code – you will need to develop tests to discover the failure and then fix your solution.
   
4. You will be provided only the AllTests.java file.  You will need to create the test file RecursiveListTest to test the functionality of your program.  Be sure to test each method in the RecursiveList class.
   
   Furthermore, the full list of asserts can be found in the JUnit API under the Assert class.

Suggestions

1. Examine RecursiveList.java (provided) closely. Read all comments and instructions paying special attention to the fact that you are only to modify the private inner-classes EmptyList and NonEmptyList.

2. Implement a stubbed version of all the required methods in private inner-classes EmptyList and NonEmptyList and make sure it compiles.

3. Now imagine an empty RecursiveList and implement the EmptyList methods so that the behave as expected (these do not require any recursion so they should be relatively easy). If you have stubbed all of the other methods you should actually be able to develop unit tests for each of the methods for an empty list and see if they work correctly.

4. Don’t forget that drawing pictures can help you visualize what should be happening in your code – draw the state of the list before and after an operation – then implement the method.

5. Next you should work on the add, get, and size methods of the NonEmptyList class and test these thoroughly before implementing the other methods of this class.
   
6. Follow the test-driven development style by first writing the test for how the method should work, see that it fails (since you have not written the code yet), then write the code to pass the test.
   
   
7. Keep track of your hours worked as you go, so you don’t have to guess when you hand in your assignment (see handin section below for information on time.txt).

Specification

1. Modify only the private inner-classes EmptyList and NonEmptyList (details to be found in the provided source file).

2. Your implementation of all methods in NonEmptyList must be recursive except for isEmpty()! Note that none of the methods in EmptyList are recursive
   

Testing With the Provided Tests

1. Your code must be 100% correct to recieve credit.  Correctness will be determined by running the acceptance test ECTestDriver.java.  
2. In addition to the acceptance test, sections 7 and 9 will be graded on the quality of JUnit tests they create for this program, section 3 will not.
3. Use the JUnit tests while developing in a test-driven approach to ensure your code's correctness before the acceptance test is released.  Run them by opening the AllTests.java file and executing it.
4. Ask your instructor for assistance if you are not able to run these tests on your own.

Handing in Your Source Electronically…

1. Create a plain text file called time.txt to log the amount of time spent on the assignment. The file will contain only three lines with the following information on each line: name, project number, hours spent.
                Example time.txt file:
            Sally Student
            Extra Credit Program
            7.5 hours
   
2. Move the necessary file(s) to your vogon account using your favorite FTP client program.
   
   
3. Log on to vogon using your favorite Shell client program.
   
   
4. Change directory (cd-command) to the directory containing the file(s) to hand in.  Be sure you code compiles and runs correctly on hornet before turning it in!
   
   
5. Use the following handin command:

12:01pm vogon ~$ handin graderkm ExtraCreditProgram RecursiveList.java RecursiveListTest.java time.txt