Task
back to topLarge Integers addition using Linked Lists
The largest value of an integer number in any programming language is limited by the number of bits used to represent the integer. However, you can represent an integer using linked lists, so the value of the integer is limited only by the available memory. Your task is to design and implement an Abstract Data Type (ADT) for storing integer numbers in linked lists. There are two different strategies for storing the integers: by storing one digit in each node or by storing multiple digits in each node. We shall call the first strategy Single-digit Integer Linked List (SILL), and the second strategy Multi-digit Integer Linked List (MILL). In this assignment, you need to implement only Single-digit Integer Linked List (SILL).
Single-digit Integer Linked List (SILL)
In this strategy, each node in the list stores one digit, and the value of the integer is a concatenation of all the nodes in the list. For example, the value 23007999000 is stored in a list that has 11 nodes:
Obviously, SILL is inefficient in memory utilisation, as each node stores only one digit. The simplest way to improve the storage efficiency is to store multiple digits in each node, called MILL.
What to Implement (Tasks):
Task 1 (20 marks):
Read two integers from a file (input.txt) which has two lines. The first line stores the first integer and the second line stores the second integer.
You may assume that
- the integer is entered as Most Significant Bit First
- it could be negative or positive. A number without a ‘-‘ sign is assumed to be a positive number.
If the input file contains invalid values, the program must catch and report the errors. The program must also check if users have passed a command line parameter before attempting to open the file. If it has read the file successfully, then it must inform users. Regardless of the outcome, the program must then display a simple menu as described in Task 4.
Task 2 (15 marks)
Store the two integers using Single-digit Integer Linked List (SILL) and display the integers read. So the following linked list
must be displayed as 23007999000. It must also display the number of nodes in the list (here 11)
Task 3 (35 marks)
Write an addition operation for the SILL. Your program should perform addition operation in the digit level (one digit in the node of a linked list) and store the result in an another SILL. See below an example:
SILL1:
SILL2:
SILL3 = SILL1+SILL2
Task 4 (15 marks)
Write a driver program to test all the functionality that you have implemented. The driver program should have a simple menu to allow users to:
1. Accept the name of an input file. If the file exists, the program should read it. The program must inform users if it has read the file successfully or failed, in which case, it must inform users why it has failed to read the file. (task 1)
2. Display integers stored in SILL (task 2).
3. Display the results of the addition arithmetic operation in SILL (task 3).
4. Exit.
This section concludes the description of the tasks required. Other than functionalities, it is also important the code is designed and written to maximize maintainability. The following section describes aspects that affects code maintainability
Design, Presentation and Conventions
You should NOT use java BigInteger.
You need to think about the design of your program to allow code reuse. The SILL Class should make use of a linked list class to store the digits; you may use Java’s LinkedList class or implement your own. You should also consider the number of lines in each method; as a guideline a method should not exceed 25 lines.
Presentation is mainly formatting for aesthetic, while conventions cover issues like naming of classes, methods and variables as well as coding standards. We will use Google’s Java Style Guide as described inhttps://google.github.io/styleguide/javaguide.html
Rationale
back to topThis assessment task will assess the following learning outcome/s:
- be able to apply a variety of abstract data structures to the solution of welldefined problems.
- be able to implement selected data structures in the Java language.
- be able to design wellstructured solutions to programming problems and implement these solutions in the Java language.
This assignment requires you to use the Java programming language to
- Read input from text files.
- Use linked lists to represent large integers.
- Write an arithmetic operation for large integers (NOT allowed to use Java BigInteger).
- Write a simple text based menu/user interface.
- Comments Java programs using Javadoc style/convention.
Marking criteria and standards
back to topAssignment will be marked out of 100 but will be scaled to assignment weight 15%
Criteria |
HD (85-100%) |
DI (74-85%) |
CR (65-74%) |
PS (50-64%) |
FL(0-49%) |
|---|
Functionality [85 marks] |
Demonstrates highly developed capability to implement program specification by correctly implementing all tasks specified; with a program is robust and correctly handles exceptions and errors.
All arithmetic operations are correct for negative and positive numbers. Error messages are easy to understand.
|
Demonstrates a well-developed capability to implement program specification by implementing all tasks; with a program that correctly handles most exceptions and errors. Error messages are generally easy to understand.
|
Demonstrates moderate ability to implement program specification by implementing more than half of the tasks specified. The program has some exception and error handling. The error messages provided are clear but require further explanation.
|
Demonstrates minimal ability to implement program specification by implementing only task 1 and/or 2.
Very little or no exception and error handling.
|
Demonstrates very little or almost no understanding of implementing the program specification.
No error messages or cryptic error messages.
|
Design [10 marks] |
Shows in-depth understanding of software maintainability by implementing best practices of object-oriented design including information hiding and reusable classes. |
Shows good understanding of software maintainability by implementing most good practices of object-oriented design including information hiding and reusable classes. |
Shows moderate understanding of software maintainability by implementing some good practices of object-oriented design including information hiding and reusable classes. |
Shows minimal understanding of software maintainability.
Some classes and methods are poorly designed. |
Shows little or no understanding of software maintainability. Many classes and methods are poorly designed. |
Presentation and Conventions [5 marks] |
The code is extremely well organized, aesthetically pleasing and easy to follow. Uses JavaDoc style to comment each class and method. Comments each variable and blocks of code, and comments for the code are meaningful (focus on why rather than what). May skip a few variables that are obvious (such as those used in loops).
Names of all the classes, modules and variables are meaningful.
Subscribes to all good coding conventions.
|
The code is fairly easy to read and mostly aesthetically pleasing. One to two names of the classes, modules and variables may be inappropriate. Uses Javadoc style to comment most classes and methods. Comments most variables and blocks of code.
Subscribes to most good coding conventions as described in the style guide above.
|
The code is somewhat readable. Three to four names of the classes, modules and variables maybe inappropriate. Uses Javadoc style to comment many of the classes and methods. Comments many variables and blocks of code
Subscribes to some coding conventions as described in the style guide above.
|
The code is partially organized and somewhat difficult to read. More than four names of the classes, modules and variables maybe appropriate. Uses Javadoc style to comment some of the classes and methods. Comments some variables and blocks of code.
Subscribes to a few coding conventions as described in the style guide above.
|
Code is disorganized (such as poorly indented). Poor choice of names for many of the classes, modules and variables. Little or no internal comments in the source code.
Subscribes to little or no coding conventions as described in the style guide above.
|
Presentation
back to topWhat to submit:
- Java source code (all *.java files only) in the correct directory structure (as dictated by the package structures).
- Documentation (Word file preferable) describing how to compile and run your program and any assumptions you have made (not more than 200 words). This documentation is not graded but it will help the markers in assessing your submission.