Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CIT 5940 - Module 2 Programming Assignment
Assignment Overview
In this module, you will implement methods that perform functions on a linked list and adapt those methods to a linked list class implementation similar to the one seen in this module’s videos.
Learning Objectives
• Become familiar with the implementation and behaviour of linked lists using static methods
• Become familiar with the implementation of and object-oriented linked list class
• Apply what you have learned about how linked lists store data
• Develop algorithms for modifying linked lists content
Advice
We highly encourage you to utilize the course discussion forum to discuss the project with classmates and TAs. Before asking the question, please search in the forum to see if there are any similar questions asked before. Please check all suggestions listed there.
For this and all other assignments in this course, we recommend that you work on your local computer using an integrated development environment (IDE) such as Eclipse, IntelliJ, Visual Studio Code, or whatever IDE you used for any prior Java courses that you are familiar with. Although you will need to upload your solution to Gradescope for grading (see the Submission Section below) and could develop your solution on that platform, we recommend using industry standard tools such as Eclipse or IntelliJ so that you become more used to them and can take advantage of their features.
If you have trouble setting up your IDE or cannot get the starter code to compile, please post a note in the discussion forum and a member of the instruction staff will try to help you get started.
We expect that you will create your own JUnit tests to validate your solution before submission.
1 Setup
- Begin by downloading the CIT594-linkedlists.zip archive from Canvas, then extract the contents. The main files you will work with are MyRawLinkedList.java and MyLinkedList.java. These contain the unimplemented methods for the code that you will write in this assignment.
- Compile this code before making any changes. This will ensure your local environment is configured correctly.
- Review the current implementation. You’ll want to understand the various parts of the code and how they work together before making changes!
2 Requirements
2.1 Structure and Compiling
- You MUST use a Java Development Kit (JDK) version of 17 or higher.
- You MAY use a JDK version higher than 17, but you MUST set the Java language level to 17 for compatibility with Gradescope.
- You MUST NOT change any of method signatures for any of the provided methods. This includes the parameter lists, names, and return value types, etc.
- You MUST leave the MyLinkedList and MyRawLinkedList classes in the default pack age.
- You MUST NOT create additional .java files for your solution.
- You SHOULD create JUnit tests to help validate your code. These tests SHOULD NOT be a part of your solution. We do expect you to test your code thoroughly with JUnit tests before submission.
- You MUST follow our directives in the starter code comments. This means if we ask you to not change a variable’s value, you MUST NOT change that variable’s value.
- You MAY create additional helper functions, as long as they meet the other requirements of the assignment (e.g. doesn’t crash with invalid inputs, etc.).
- You MUST fill out the required Academic Integrity signature in the comment block at the top of your submission file.
2.2 Functionality Specifications
2.2.1 General Requirements
- Your method MUST NOT crash if a user enters an invalid input. Remember you do not have control over what a user inputs as arguments. For example, all methods should handle null inputs gracefully or as specified.
- You MUST NOT overload any of the provided methods.
- You MUST NOT use arrays anywhere in your solution.
- You MUST NOT have any import statements in your solution. This implies that you MUST NOT use any other classes or utility functions to manipulate lists.
- You MAY use methods of the elements, for example equals or compareTo from java.lang.String.
- You MUST NOT throw any exceptions, either deliberately or by failing to handle them, unless otherwise specified in these instructions
- You MAY create your own helper methods.
2.2.2 Raw Linked List with Static Methods
This first part is designed to help you learn the core behaviour of singly linked lists. It is NOT written in an object-oriented style. So you won’t be able to instantiate a new linked list like this:
/// not valid when using static methods!
MyRawLinkedList myRawList = new MyRawLinkedList();
Instead, you will create individual Nodes as follows:
Node list0 = null; // the empty list, list0 = [ ]
Node list1 = new Node("b", list0); // list1 = [ "b" ]
Node list2 = new Node("a", list1); // list2 = [ "a", "b" ]
Note specifically that list2 "contains" list1, which in turn "contains" list0.
Be careful to not mix up a null list (representing an empty list) with a linked list containing a single element with value null. The following example is valid and MUST be handled appropriately:
// this is valid!
Node list3 = new Node(null, list2); // list3 = [ null, "a", "b" ]
Additionally, you must follow these requirements for all methods in this section:
1. You MUST NOT reference this anywhere in your code. This is because all the methods are static.
2. Each method MUST take at least a Node as an argument. This represents the head of some linked list.
3. You MUST consider a null Node argument as a linked list containing no Nodes (that is, the empty list).
4. The end of any linked list MUST have a final Node where Node.next = null. This signifies the end of the linked list. The empty list is the ONLY exception.
5. You MUST handle both of the following scenarios for each method:
(a) The Node is the empty list (i.e. null)(b) The Node is a non-empty list
6. You MUST NOT create new instances of Nodes. That is, you should not have new Node(...) in your solution
7. You MAY create temporary pointers to Nodes within the list
8. You MUST implement the following methods according to their specific specifications
2.2.2.1 reverse(Node)
You MUST implement the reverse(Node) method as follows:
1. it MUST take the following parameters:
(a) Node head: the head of a linked list
2. it MUST reverse the order of the original list
3. it MUST return the Node representing the head of the reversed list
4. it MUST NOT modify the value field. That is, you MUST NOT simply reverse the values of each Node
5. As an example, assume the list with head Node contains the following:
DOG → BANANA → CAT → BEAR
Calling reverse(head) should return this reversed list:
BEAR → CAT → BANANA → DOG
2.2.2.2 removeMaximumValues(Node, int)
You MUST implement the removeMaximumValues(Node, int) method as follows:
1. it MUST take the following parameters:
(a) Node head: the head of a linked list
(b) int N: the number largest values to remove
2. it MUST use the compareTo method to determine which value is the largest.
3. it MUST remove ALL nodes containing each of the N largest values. If the largest value appears more than once in the list, this method MUST remove all such Nodes.
4. it MUST return the Node representing the head of the linked list with the required elements removed
5. if N is either zero or negative, then this method MUST return the original list unmodified
6. it MUST NOT change the order of the unremoved Nodes
7. it MUST return the empty list from the empty list, for any value of N
8. it MUST gracefully handle scenarios where the original head Node was removed. That is, it must handle these scenarios without crashing or throwing unspecified exceptions.
9. it MUST gracefully handle scenarios where all Nodes were removed
10. it MUST gracefully handle scenarios where you try to remove more Nodes than the listcontains
11. For this method ONLY, we will not pass a list to your method that contains any nodes with null Strings. However, it is good practice to expect and handle this case.
12. As an extended example, assume the list with head Node called head contains the following:
DOG → GORILLA → BANANA → CAT → GORILLA → BEAR
Calling removeMaximumValues(head, 1) would remove all instances of the largest value, which is GORILLA, and the returned linked list would be:
DOG → BANANA → CAT → BEAR
However, given that same original linked list, removeMaximumValues(head, 2) would remove the two largest values, which are GORILLA and DOG, so the linked list would be:
BANANA → CAT → BEAR
Finally, consider this second list:
KANGAROO → PLATYPUS → AARDVARK → KANGAROO → DONKEY → COYOTE
Calling removeMaximumValues(head, 2), would remove all instances of the largest value PLATYPUS) and all instances of the second-largest value KANGAROO. The returned list in this scenario would be:
AARDVARK → DONKEY → COYOTE
2.2.2.3 containsSubsequence(Node, Node)
You MUST implement the containsSubsequence(Node, Node) method as follows:
1. it MUST take the following parameters:
(a) Node head: the head of a linked list
(b) Node other: the head of another linked list
2. it MUST return true if head contains a subsequence of values that matches the list in other. A valid subsequence is defined as follows:
(a) the subsequence can be derived by removing zero or more elements from the original sequence
(b) the relative order of elements remains unchanged
3. it MUST return false otherwise
4. it MUST compare ONLY the values in the lists. You MUST NOT check if the Node itself matches
5. it MUST consider the empty sequence as a valid subsequence for all possible sequences
6. it MUST handle scenarios in which either or both lists contain Nodes that contain null values.
7. As an example, consider the original sequence
[A, B, C, D]
A few (but not all) of the valid subsequences are [ ]; [A]; [A, B]; [B, D]; [A, B, D]
[B, A] is invalid because the order changed
[A, B, C, D, E] is invalid because E does not appear in the original
2.2.3 Object-Oriented LinkedList
This second part is designed to help you understand the implementation of a linked list as an object-oriented data structure. Now, each MyLinkedList contains three fields to keep track of the state of the linked list, rather than taking a Node as an argument.
// this is valid for object oriented classes
MyLinkedList myList = new MyLinkedList();
You can add or remove elements using this classes methods:
Node node1 = new Node("b");
Node node2 = new Node("a");
myList.add(0, "b"); // myList : [ "b" ]
myList.add(0, "a"); // myList : [ "a", "b" ]
Note specifically that myList hides the underlying implementation from the user. Be careful to not mix up a null list (representing a MyLinkedLIst that has not been initialised) with a linked list containing a zero element with the head field set to null. This is different from how the MyRawLinkedList works. The following examples are valid:
MyLinkedList first = null // a uninitialised list
MyLinkedList second = new MyLinkedList(); // an empty list
MyLinkedLIst third = new MyLinkedList(null); // another empty list.
Additionally, you must follow these requirements for all methods in this section:
1. Changes to the linked list MUST modify the linked list object rather than a returned list.
Therefore, you MUST work with the object’s linked list, using the head field as the start of the list.
2. You MUST maintain the state of the head, tail, AND size fields.
3. You MAY copy your implementations from MyRawLinkedList, but you MUST adjust them to meet the specifications in this part
4. You MAY use the element’s methods (e.g. equals and compareTo
5. Your methods MUST NOT take a Node as an argument
6. You MUST handle null MyLinkedList objects and MyLinkedLists with a null ele ment as described above.
2.2.3.1 reverse
The primary functionality is the same as the Raw Linked List reverse method above, EXCEPT for these specific changes:
1. It MUST make the updates to the MyLinkedList instance in-place (that is, using the this keyword).
2. It MUST NOT return the reverse list.
2.2.3.2 removeMaximumValues(int)
The primary functionality is the same as the Raw Linked List removeMaximumValues method above, EXCEPT for these specific changes:
1. It MUST make the updates to the MyLinkedList instance in-place (that is, using the this keyword).
2.2.3.3 containsSubsequence(MyLinkedList)
The primary functionality is the same as the Raw Linked List containsSubsequence method above, EXCEPT for these specific changes:
1. It MUST make the updates to the MyLinkedList instance in-place (that is, using the this keyword).
2. It MUST take another MyLinkedList as the other list, instead of a Node
3. It MUST return the type Boolean object, instead of the primitive boolean. This has several implications:
(a) When the other list is non-null, the behaviour MUST be exactly the same as before(b) When the other list is non-instantiated (that is, NULL) it MUST return null
4. It MUST NOT throw a NullPointerException
2.3 Writing Test Cases
Upon completion of each functional requirement, always conduct thorough testing of the corre sponding functions. Consult the guidelines on composing JUnit tests and creating test cases in Module 1. You MUST develop JUnit tests to cover all corner cases you can think of for each of your implemented function in order to get full credit. This testing component carries a weight of approximately 5% towards the total assignment score.
3 Submission
3.1 Pre-submission Check
Before you submit, please double check that you followed all the instructions, especially the items in the Structure and Compiling section above.
3.2 Gradescope Submission
1. When you are ready to submit the assignment, go to the Module 2 Programming Assignment Submission item and click the button to go to the Gradescope platform.
2. Once you are logged into Gradescope, locate the assignment name you would like to submit. This should be the first thing that appears in the Dashboard.
3. Upload your solution and any JUnit test files via file upload or a private GitHub repo. Please pay attention to preserve the file structure as presented in the starter code given.
4. When you are sure you are ready to submit, confirm at the prompt.
5. You will see quite a bit of output after a while (which can be at most a few minutes), even if all the tests pass. At the bottom of the output, starting at "Autograder Results" you will see the number ofsuccessful and failed test cases.
6. If you want to update your code and resubmit, for example if you did not pass all of the tests, simply edit your code and submit.
4 Grading
4.1 Grading Overview
1. There is a peer review for this assignment. Other students will be reviewing your code and providing feedback. While their review will not directly impact your grade, we still expect you to use best practices (comments, indentation, etc). There is a separate assignment in Canvas for you to submit your code for peer review and review the submissions of your classmates.
2. There may be hidden tests. You will be able to see the name of each test, if it passed or failed, and the associated point value.
3. Failed tests will have brief feedback about the specifics of the failure.
4. We will not provide the exact test cases.
5. You have unlimited submissions, until the due date of the assignment as noted in the Syllabus (or your approved extension).
6. The score at the due date is final. Scores will sync to Canvas relatively immediately.
4.2 Rubric Items
This assignment will be marked on 6 rubric items.
• Raw Linked List - reverse : 11 points
• Raw Linked List - removeMaximumValues : 27 points
• Raw Linked List - containsSubsequence : 24 points
• Linked List - reverse : 15 points
• Linked List - removeMaximumValues : 27 points
• Linked List - containsSubsequence : 25 points
Total : 129 points(+ 6 points for JUnit test cases); 62 from MyRawLinkedList, 67 from
MyLinkedList.
Good Luck!