1. 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.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.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.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.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.

import java.util.*; import java.io.*; public class LinkedList { int n; ListNode start; ListNode rear; // You can set debug=true when you are debugging and want // to print out what your program is doing. // Please leave your debugging messages in your code when // you submit it. Change debug back to false before // submitting your code. static final boolean debug= false; public LinkedList() { n= 0; start= null; rear= null; } public LinkedList(int size, ListNode first, ListNode last) { n= size; start= first; rear= last; } public static LinkedList readBigInteger(Scanner in) { LinkedList x; x= new LinkedList(); // Insert your code from assignment #1 here // for credit on question 1 of assignment #2. return(x); } public void reverse(int level) { // Insert your code from assignment #1 here // for credit on question 1 of assignment #2. } /* This method returns: -1 if the bigInteger associated with the method is less than y 0 if the bigInteger associated with the method is equal to y +1 if the bigInteger associated with the method is greater than y */ public int compare(LinkedList y) { // Insert your code for question 2 here. return(0); // Delete this when you write your code. } // Tries to read in a non-negative integer from the input stream. // If it succeeds, the integer read in is returned. // Otherwise the method returns -1. public static int readInteger(Scanner in) { int n; try{ n= in.nextInt(); if (n >=0) return(n); else return(-1); } catch(Exception e) { // We are assuming legal integer input values are >= zero. return(-1); } } // You can use this in order to get nicer output // (lined up in columns). public void printBigInteger(int nDigit) { boolean leadingZero; ListNode current; int i; int n_extra; reverse(0); leadingZero= true; if (n < nDigit) { for (i=n; i < nDigit; i++) System.out.print(" "); } n_extra= n- nDigit; current= start; while (current != null) { if (leadingZero) { if (current.data != 0) leadingZero= false; } if (leadingZero) { if (current.next == null) // value is 0. System.out.print(current.data); else if (n_extra <= 0) System.out.print(" "); } else { System.out.print(current.data); } n_extra--; current= current.next; } reverse(0); } } 

import java.util.*; import java.io.*; /* This class is for creating a singly linked class of big integer nodes. */ /* Hand this in together with your LinkedList.java. */ class BigIntegerList { int n; // Number of items in the list. BigIntegerNode start; BigIntegerNode rear; // You can set debug=true when you are debugging and want // to print out what your program is doing. // Please leave your debugging messages in your code when // you submit it. Change debug back to false before // submitting your code. static final boolean debug= false; public BigIntegerList() { n=0; start= null; rear= null; } public static BigIntegerList readBigIntegerList(Scanner in) { BigIntegerList problem; // Insert your code for Question 2 here. return(null); } public void printBigIntegerList() { // Insert your code for Question 3 here. } public void quickSort(int level) { // Insert your code for Question 4 here. } } 

/* This class defines a list node for a singly linked list of integers. Do not insert any code into this class. The automated testing of your program will include this code as it is given here. */ class ListNode{ public int data; public ListNode next; public ListNode(int x, ListNode ptr) { data= x; next= ptr; } } 

 /* This class defines a list node for a singly linked list of big integers. Do not insert any code into this class. The automated testing of your program will include this code as it is given here. */ class BigIntegerNode{ public LinkedList x; public BigIntegerNode next; public BigIntegerNode(LinkedList y, BigIntegerNode ptr) { x= y; next= ptr; } }