CSC 225 Fall 2017: Assignment #1 Part A: Programming Exercises
Due by 11:55pm on Saturday Sept. 23.

Submission Instructions

Put your name in a comment at the top of LinkedList.java.
Upload LinkedList.java to connex (in the same place as the assignment is posted). You can change the file that you upload as many times as you want up until the submission deadline. Do not zip, tar, or otherwise compress your file before uploading it.
Your program 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.
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.

Learning objectives:

Linked lists are an important data structure that you should have studied in CSC 115 or its equivalent. The goal of this assignment is to ensure students are able to write programs for manipulating linked lists and also to gain competence in programming recursive algorithms. Later when we gain skills for algorithm analysis, the algorithms you program will be analyzed with respect to its time and space complexities and compared with other approaches to the problem.

Problem Motivation

In my research, I often run into situations where I am counting combinatorial objects and the number of items counted is larger than can be stored in one integer. I have 64 processors for running long computations, and to get the final results, it is necessary to takes sums of the answers that each machine has computed.

Your Task

The goal of this assignment is to create routines for computing with big integers (potentially too large to represent with 32 bits). The integers represented are assumed to be greater than or equal to zero and may have an arbitrary number of digits. Each digit is stored in a cell of a linked list and has a value between 0 and 9. To facilitate adding two big integers together, the big integers are stored in a linked list which has the least significant digit at the front of the list. For example, the integer 2385 is stored in a linked list like this:

You should start with the following java classes (to save these, right click on the link and use the "save as" option):

ListNode.java : This class defines a list node.
LinkedList.java : Your new routines will be placed into this class. The method headers for your new methods are already in this class.
Test.java : You can use this as a starting point for testing your final program. Additional testing is recommended to ensure correctness. This class has a checkList routine- fill in code here to check the integrity of your lists (n, start and rear) to aid in debugging.
itest.txt : This is one file of inputs you can use to test your final submission:
java Test < itest.txt > otest.txt

Add code to define these methods in the file LinkedList.java (do not change the method headers):

public static LinkedList readBigInteger(Scanner in) [15 marks]
This routine reads in one big integer and returns its linked list representation. The readBigInteger method should return null if there is no further input remaining. The way that a big integer is given for input is that first, an integer n_digit representing the number of digits is specified followed by n_digit digits which should be in the range 0 to 9. For example, the integer 2385 is input as
4 2 3 8 5
Do not make any assumptions about the number of spaces between the integers or about how the input is arranged on lines. You can use readInteger in LinkedList.java.
public void printBigInteger( ) [15 marks]
The printBigInteger method should reverse the list using the reverse method, then traverse the list to print the big integer without leading zeroes and without spaces between the digits, and then should restore the original list by calling reverse again.
public void reverse(int level) [30 marks]
The reverse must operate recursively. First the list should be split into two lists, one with the first floor of n/2 entries and the other with the rest. You can use two new LinkedList objects each time you split the list in half but do not make any new ListNode objects. Then each of these lists should be reversed recursively. Then concatenate together the answers appropriately to get the final answer. The variable level is for debugging and represents the level of the recursive call. The initial call should be at level 0. If reverse is called from level k then the resulting invocation is at level k+1.
public void plus_plus( ) [15 marks]
This method operates in-place and has the effect of adding one to the current integer value. You should not create any new list nodes except in the case that one more list node is required to represent the answer. For example, if 99 is incremented, the original list has two cells, each with a digit value of 9. After the increment, the data values are changed to 0 in the first two cells and a new cell with data value 1 is added to the end of the list.
public LinkedList plus(LinkedList y) [25 marks]
If x, y, and z are LinkedList objects representing big integers, then calling this routine like this:
z = x.plus(y)
sets z to be big integer which is the sum of the big integers stored in x and y.

For full marks, the values for n, start and rear for linked lists that arise during processing should have correct values for their lists.

Sample Output

When I run
java Test < in.txt
with this in the file in.txt:
3 8 5 9 3 7 2 3
Then the output is:
Test the increment method:
Value should be 1 is 1
Value should be 11 is 11
Value should be 111 is 111
Value should be 1111 is 1111
Value should be 11111 is 11111
Problem 1:
859 + 723 = 1582

Do not print extraneous new lines when printing your big integers (your output should look like mine does).

IMPORTANT NOTE: When we test your code, it will be unit tested. It is important to make sure that each routine follows the specifications precisely. If for example, your readBigInteger is not correct because the resulting list has the values in the list in reverse order from the specifications but your printList is hacked to print the bigInteger correctly, it may appear that your program is working but you will lose marks for both routines since neither one meets the specifications.

If you view the file itest.txt in an old version of notepad, then the new lines might not be displayed properly. Try downloading this file instead: itest2.txt instead. Your java program can read in either file correctly as intended. The file itest.txt should look like this: