Assignment LinkedList Version XXXXXXXXXX Instructions 1. Read this prompt thoroughly. a. You can use the document outline to more quickly move between parts of the exam. i. Make sure it is available....

NEed help with the attached assignment.


Assignment LinkedList Version 20.11.21-24 Instructions 1. Read this prompt thoroughly. a. You can use the document outline to more quickly move between parts of the exam. i. Make sure it is available. To check, in the menu go to “View->Show document outline”. Then you can click on the icon to the left near the top to open the outline. 2. Download the starter code from Mimir a. Do not change the file names. Otherwise, it will not be graded. b. File names i. LinkedList.h ii. LinkedList.cpp iii. Tests.cpp 3. Get started a. Think before you code b. Draw pictures to help you think 4. Compile early and often. 5. Test early and often. 6. Submit to Mimir early and often. 7. Ask for clarification on Piazza (private posts only) a. Refresh and read the FAQ first 8. And Just Have Fun! Allowed Includes Use of an “illegal” header file will result in a zero (0) on the assignment. · This is shown as a visible test cast on Mimir. · Failing the “Approved Includes” test case will result in a zero (0) on the exam. · List of allowed Includes · · · · · · · · “LinkedList.h” · “test_helpers.h” · If there is a library not on this list that you think you need, ask us on Piazza and we’ll consider it. Only the following topics can be used for the assignment: 0. Classes 0. With or without dynamic memory 0. Encapsulation 1. Private/Public members (data and methods) 1. Constructor overload 1. Operator overload 1. Rule of Three 3. Copy constructor - Deep/shallow copy 3. Destructor - Memory leaks 3. Copy assignment - Memory leaks & Deep/shallow copy 1. Linked Lists 4. Create (construct) 4. Read (access, copy) 4. Update (insert, remove) 4. Destroy (destruct) How to Compile Failure to submit compilable code will result in a zero (0) on the exam. · This is shown as a visible test case on Mimir. · Failing the “Compiles without errors” test case will result in a zero (0) on the exam. · Recall that warnings do not prevent code from compiling. g++ -std=c++17 -Wall -Wextra -pedantic-errors -g LinkedList.cpp Tests.cpp How to Use Tools for Checking for Memory Errors Sanitizers g++ -std=c++17 -Wall -Wextra -pedantic-errors -g -fsanitize=address,undefined LinkedList.cpp Tests.cpp ./a.out Valgrind g++ -std=c++17 -Wall -Wextra -pedantic-errors -g LinkedList.cpp Tests.cpp valgrind --leak-check=full ./a.out Example Test Cases Every problem on the exam has some provided example use case code, which is replicated as 0-point test cases on Mimir. There is no automatic determination for “passing” these tests. · You will get a “50%” if your code compiles and runs. · Click on the test case to see the details. · The tests output the contents of the list at certain points and you must decide whether the output is correct. · That is, the other 50% of the test case is in your mind. · These are visible test cases on Mimir. · If you get 50% · You know that your code compiled and ran with the example test cases. · You DO NOT KNOW if your results are correct. Grading Overview Item Points Code Coverage 10 Problem 0: Basic Linked List Infrastructure 20 Problem 1: Remove all Duplicates from a Linked List 40 Problem 2: Length of Maximum Subsequence of Decreasing Values 20 Problem 3: Rule of Three 20 Total: 110 out of 110 Problem Theme: Linked List You must implement a Linked List that supports the following: 1. basic linked list infrastructure 2. remove duplicate values from the list 3. find the length of the maximum subsequence of decreasing values 4. rule of three What is Provided Must Also Be Submitted · LinkedList.h · struct Node defines the Node object type. The provided types, names, and access modifiers must not be changed. · int data · stores the data value. · Node* next · stores the address of the next node in the list. · You may add to Node, but it is not required. The provided Node is sufficient. · class LinkedList defines the LinkedList object type. · The type to use for sizes and indices is size_t. · You must implement the rest of LinkedList. · LinkedList.cpp · Nothing · You must implement the rest of LinkedList. · Tests.cpp · An empty main function stub. · You must write your tests in this file and use them in main. · Your tests will be executed and must run without error. · You should NOT comment out your tests, since your tests will be scored for code coverage. · A main() function with testing code is required to be submitted. · You are expected to test your own code.  You must submit the test cases you used to test your code.  This file will be one of the required files along with the other files provided in started code. Code Coverage Overview The code coverage assessment measures how much of your code your test cases exercise by being called from the main function in Tests.cpp. · It does not care that you get correct results, it only counts how many times each executable line gets executed and reports the percentage of lines executed. · You must have at least 80% coverage to pass the code coverage test. In practice, 100% coverage is often effectively unattainable, so developers aim for “enough” coverage. · This testcase is visible in Mimir. Points · 10 points · You need at least 80% coverage. · This is shown as a visible test case on Mimir. Problem 0: Basic Linked List Infrastructure Overview You must design and implement any and all Linked List infrastructure that is necessary for the remaining problems, see the specification of Required Functions below. Points · 20 points · Partial credit is available Example LinkedList list; // list := list.push_back(8); list.push_back(6); list.push_back(7); list.push_back(5); list.push_back(3); list.push_back(0); list.push_back(9); // list := 8, 6, 7, 5, 3, 0, 9 Required Functions You are required to provide these public functions.You may add additional public and private helper functions that support the required functions. LinkedList::LinkedList() The LinkedList default constructor makes an empty list (zero size, null head). Parameters None. Return Value None. Exceptions None. size_t LinkedList::size() const Return the number of elements in the list. Parameters None. Return Value The number of elements in the list. Exceptions None. const Node* LinkedList::head() const Return the pointer to the head of the list. · Note: This is for testing purposes only! You would normally not make a public head function since the public interface should protect the inner workings of your class. Parameters None. Return Value Pointer to the head of the list, or nullptr if the list is empty. Exceptions None. void LinkedList::push_back(int value) Append the given value to the end of the list. Parameters value - the value to append. Return Value None. Exceptions None. Problem 1: Remove all Duplicates from a Linked List Overview You must implement a function that removes duplicate values from the list. You must design and implement any and all Linked List infrastructure that is necessary for this operation, see the specification of Required Functions below. Removing duplicates from a list means transforming the list such that each value in the list appears exactly once. Points · 40 points · Partial credit is available Examples LinkedList list; // list := list.push_back(1); list.push_back(7); list.push_back(2); list.push_back(7); list.push_back(7); list.push_back(3); list.push_back(7); list.push_back(7); list.push_back(4); list.push_back(7); list.push_back(5); // list := 1, 7, 2, 7, 7, 3, 7, 7, 4, 7, 5 list.remove_duplicates(); // // the following and all permutations thereof are correct: // list := 1, 2, 3, 4, 5, 7 The following example is not a visible test on Mimir. LinkedList list; // list := list.push_back(1); list.push_back(2); list.push_back(3); list.push_back(4); list.push_back(3); list.push_back(2); list.push_back(1); // list := 1, 2, 3, 4, 3, 2, 1 list.remove_duplicates(); // the following and all permutations thereof are correct: // list := 1, 2, 3, 4 Required Functions You are required to provide these public functions. You may add additional public and private helper functions that support the required functions. void LinkedList::remove_duplicates() Remove all duplicate values from the list, keeping only a single element of each distinct value in the list. The order of the list after removing all duplicates is unspecified (i.e. order is not necessarily preserved). Parameters None. Return Value None. Exceptions None. Functions If you are unsure of how to solve this problem, you may refer to Appendix: Partial Credit Methods which lists some methods which you can implement for partial credit in lieu of a correct and complete implementation of remove_duplicates. Problem 2: Length of Maximum Subsequence of Decreasing Values Overview You must implement a function that returns the length of the maximum subsequence of strictly decreasing values. See the specification of Required Functions below. Points · 20 points · Partial credit is available Example LinkedList list; // list := list.push_back(11); list.push_back(9); list.push_back(3); list.push_back(8); list.push_back(7); list.push_back(5); list.push_back(2); list.push_back(1); list.push_back(4); list.push_back(3); list.push_back(9); list.push_back(8); // list := 11, 9, 3, 8, 7, 5, 2, 1, 4, 3, 9, 8 size_t max_length = list.length_max_decreasing(); // max_length will be 5 The following examples are not visible tests on Mimir. LinkedList list2; // list := list2.push_back(11); // list := 11 size_t max_length2 = list2.length_max_decreasing(); // max_length will be 1 LinkedList list3; // list := list3.push_back(11); list3.push_back(4); // list := 11, 4 size_t max_length3 = list3.length_max_decreasing(); // max_length will be 2 LinkedList list4; // list := list4.push_back(11); list4.push_back(11); // list := 11, 11 size_t max_length4 = list4.length_max_decreasing(); // max_length will be 1 Required Functions You are required to provide these public functions. You may add additional public and private helper functions that support the required functions. size_t LinkedList::length_max_decreasing() const Determine the length of the maximum subsequence of decreasing values. Parameters None. Return Value The number of elements in the longest contiguous subsequence of strictly decreasing values in the list, or 0 if the list is empty. Exceptions None. Problem 3: Rule of Three Overview Implement the rule of three for the Linked List class. See the specification of Required Functions below. Points · 20 points · Partial credit is available Example LinkedList list_A; // list_A := for (int n = 1; n <=>