CSC 225 Fall 2017: Assignment #2 Part A
Due at 11:55pm on Thursday Oct. 12

Instructions

1. This assignment should be submitted electronically on connex. Do not forget to use the SUBMIT button every time you make a submission. Upload only one copy of each file.
2. All programs must be written in Java. All code must be nicely indented and thoroughly documented. You are not permitted to use any libraries besides those provided with the assignment to implement the data structures (they must be programmed from scratch). You will lose marks for not following the specifications precisely. It is important in an industrial setting to stick rigorously to specifications given to you. Also, the tasks are defined as they are to meet educational objectives.
3. Please put your name inside each class (at the top, in a comment).

Learning objectives:

The aim of this assignment is to provide further practice in programming with linked lists and for designing recursive algorithms.

It is a good idea to save a copy of your assignment #1 solution in a different directory from where you plan to start work on assignment #2. You can reuse code you wrote for assignment #1 for assignment #2. To start this exercise, first copy these files (you can right click on the hyperlink and use the "Save as" option to save them as/is):

1. ListNode.java
2. LinkedList.java
3. BigIntegerNode.java This class gives you the definition of a list node for a linked list of big integers.
4. BigIntegerList.java This class has methods for working with linked lists of big integers.
5. Test.java
6. in.txt

The goal of this assignment is to write a quickSort method for sorting a linked list of bigInteger values.

1. [20 marks] Fill in the code for readBigInteger and reverse from assignment #1. Your lists representing big integers should be as specified for Assignment #1 (least significant digit first). The new LinkedList.java has a new method printBigInteger(int nDigit) that formats bigIntegers with less than nDigit digits by printing nDigit - n blanks in front of the value. that will make nicer output for debugging than the method from assignment #1.
2. [20 marks] Write a compare method in the class linkedList for comparing bigInteger values. Big integers can have leading zeroes. If they do, please do not remove them (it is more interesting when we are analyzing time complexities to be forced to deal with them). If you call it like this: x.compare(y) then it should return -1 if x < y, 0 if x=y, and +1 if x > y. For full marks, your routine should take O(n) time to execute in the worst case where n is the maximum of x.n and y.n. Be careful when programming this to ensure that it still works correctly if a bigInteger is compared to itself.
3. [10 marks] Write the code for
   public static BigIntegerList readBigIntegerList(Scanner in)
   in the class BigIntegerList. Your method should read in an integer n followed by n big integers. If the program has no more input when it tries to read in n, return null. Otherwise, return a big integer list that contains the big integers in the same order as they appear in the input stream. For full marks, your code should run in O(n) time assuming that the big integers each have at most some constant number of digits (in contrast to the lab 1 readRear code which runs in O(n²) time).
4. [10 marks] Write the code for
   public void printBigIntegerList()
   in the class BigIntegerList. This method prints a big integer list. To print a big integer x, use x.printBigInteger(8) (code I gave you in LinkedList.java) so that the output is lined up nicely and easier to read for your quickSort routine. Print the output so that only 10 values appear on each line except possibly the last line (which may have less than 10 values). Ensure subsequent output starts on a new line.
5. [40 marks] Write the code for
   public void quickSort(int level)
   in the class BigIntegerList. The variable level is a debugging variable representing the level of recursion. This routine sorts a list of big integers by rearranging the pointers.
   The pseudo code you should implement for this program is:
   A list of size 0 or 1 is sorted so return if n is at most 1.
   Set the pivot value to be the big integer value that appears first on the linked list.
   Create 3 new lists, List1, List2 and List3.
   Traverse the list removing each cell and placing it at the end of the appropriate list:
   List1: for values less than the pivot.
   List2: for values equal to the pivot.
   List3: for values greater than the pivot.
   Sort List1 and List3 recursively.
   The final answer is List1 followed by List2 followed by List3.

You can test your programs like this:
java Test < in.txt > out.txt
Feel free to do additional testing to ensure correctness.

Electronic Submissions with connex:

1. LinkedList.java
2. BigIntegerList.java

Your routines will be unit tested. If for example, your readBigInteger does not match the specifications for assignment #1 and you hack the compare method so that they work properly together, you will not get credit for either routine since they will not meet the specifications. Do not make changes to the other .java files or your program will not run properly in our testing environment.