I need help with answering all of the following questions pleas let me know if you need more info

the dlist file that was provided

section 4 and on questions

please help and answer each part thank you

Next, create an empty folder named asuriteid-104 and copy asuriteid-104.pdf to that folder. For the linked list exercises 4.1 and 4.3, copy your modified DList.java source code file to the asurite-04 folder. For the binary tree tree exercise 5.3 copy your modified Binary Tree.java source code folder to the asuriteid-h04 folder. (Note: Java source code files are the files with a java file name extension; do not copy the class files or any data files as we do not need those.) Then compress the asuriteid-h04 folder creating a zip archive file named asuriteid-h04.zip. Upload asuriteid-104.zip to Canvas using the submission link on the Module 7: HW4 Due submission page before the assignment deadline. Please see the Course Summary section on the Syllabus page in Canvas for the deadline. The deadline can also be found on the CSE205 course calendar, look for the event named Module 7: HW4 Due. . Consult the Syllabus for the late and academic integrity policies 2 Learning Objectives 1. To use the merge sort and quick sort sorting algorithms to sort a list of elements. 2. To analyze the time complexity of the merge sort and quick sort sorting algorithms. 3. To implement linked list, stack, queue, and tree data structures. 4. To analyze the time complexity of linked list, stack, queue, and tree operations. 5. To implement a binary search tree (BST) data structure 6. To analyze the time complexity of BST operations. 3 Sorting 3.1 Learning Objectives for Exs. 3.1-3.4: To demonstrate that the student understands how the merge sort algorithm sorts a list. In the video lecture Sorting Algorithms: Section ? : Merge Sort Example we traced how merge sort would recursively sort list = { 4. 2. 7, 3, 5, 13, 11, 8, 6,2 }. For this exercise, I would like you to draw a similar diagram showing how merge sort would sort list = { 5.3, 1.6, 2. + }. Scan this diagram and insert it into your final PDF 3.2 In Sorting Algorithms : Section 9 : Merge Sort Pseudocode we discussed the high-level pseudocode for the merge soru algorithm. I wrote three methods: recursive MergeSort(), merge(), and copyRest). Continuing the previous exercise, how many times will recursive.Merge Sort() be called when sorting the list of Exercise 3.1. Include the original non- recursive call to recursive MergeSort() and all of the subsequent recursive calls in the answer. 3.3 Continuing Exs. 3.1-3.2, how many times will merge() be called? 3.4 Continuing Exs. 3.1-3.2, during the final call to merge when we are merging list and lists to form the final sorted list-copyRest() will be called. (a) When copyRest() executes, which list will be srcList (listy or lista)? (b) What will be the value of srcIndex? (c) Which list will be dstList? (d) What will be the value of dstinder? 3.5 Learning Objectives for Exs. 3.5-3.7: To demonstrate that the student understands how the quick sort algorithm sorts a list. Consider list = { 5, 4, 2, 9, 1, 7, 3, 8, 6 } and the quick sort algorithm. Assume we always choose the first list item in the list being partitioned as the pivot, as you did in Project 3. Trace the partition method showing how list is partitioned into list and listy. To get you started, here is the format of what I am looking for in your solution: list - {5, 4, 2, 9, 1, 7, 3, 8, 6}, pivot - 5, left Inder - -1, rightInder - 9 While loop pass 1: left Inder ends up at o, rightInder ends up at 6 left Inder = right Inder - ??? partition() returns ??? so list: - {???}. lists = { ???), first list item in the list being partitioned as the pivot, as you did in Project 3. Trace the partition method showing how list is partitioned into list and liste. To get you started, here is the format of what I am looking for in your solution: list = { 5, 4, 2, 9, 1, 7, 3, 8, 6), pivot - 5, leftInder --1, rightInder = 9 While loop pass 1: leftInder ends up at o, right Index ends up at 6 leftInder = right Index = 777 partition() returns 777 so list: = { ??? }, liste = { ??? }, 3.6 Choosing the first list element as the pivot does not always lead to a good partitioning (ideally, the sizes of list and listy will be approximately equal). Suppose list = {1, 2, 3, 4, 5, 6, 7, 8 } and we again select the first element as the pivot. What would list and liste be? For this exercise, you do not have to write a detailed trace of the partition method as you did for the previous exercise; simply list what index would be returned by partition) and the con- tents of list, and listy 3.7 Starting with lista from the previous exercise, repeat Exercise 3.6 on lista. Explain what pattern is going to hold if we continue to partition each successive listy 4 Linked Lists Important Note: There are two version of Distjava in the Week 6 Source Code and Week 7 Source Code zip archives The two versions are mostly identical with this difference: the DList class in the Week 6 Source Code zip archive is designed to store elements only of the java.lang. Integer data type, eg.. we could not use this class to store Circles or DList.java X 14 150 /** 16 * Implements a doubly linked list of Integers. 17 18 public class DList { == //=== ===== // DList Instance Variables //======== * For a nonempty Dlist, mHead is a reference to the first Node in the DList. For an empty * DList, mHead will be null. private Node mHead; * The number of Nodes containing data in this blist. For an empty Dlist, mize is e. private int mSize; *For a nonempty DList, mail is a reference to the last Node in the DList. For an empty DList, mail will be null. private Node mTail; / DList Instance Methods Creates an empty Duist. For an empty Dist, mHead = null, mail - null, and mSize = 0. DList.java X 44 45e 46 Creates an empty Dlist. For an empty Dlist, mHead = null, mTail = null, and mSize - 0. 47 480 49 50 public DList() { setHead(null); setTail(null); setSize(); 52 53 540 * Creates a new DList with one element containing pData. 56 57e public DList(Integer pData) { 1/ Create a new Node storing pData. The ctor makes the mPrev and mNext references null. Node newNode = new Node (pData); 17 Make the mhead reference refer to the new node. setHead(newNode); 889888898 // Make the mail reference refer to the new node. setTail(newNode); // The size of the list is now 1. setSize(1); 712 * Inserts a new Node containing pData into this list at index pIndex. Shifts the element currently at that index (if it exists) and succeeding elements to the right (i.e., adds one to their indices). Note that if pIndex == getSize() the new element is appended to the list. Throws an IndexOutOfBounds Exception if pIndex size of the Dist. * Inserts a new Node containing pData into this list at index pIndex. Shifts the element currently at that index (if it exists) and succeeding elements to the right (i.e., adds one to their indices). Note that if pIndex = getSize() the new element is appended to the list. * Throws an IndexOutOfBoundsException if pIndex size of the DList. */ 80e public void add(int pIndex, Integer pData) throws IndexOutOfBoundsException { 1/ Check for pIndex out of bounds. if (pIndex getSize() throw new IndexOutOfBoundsException(); 1/ Are we appending? if (pIndex = getSize() { // Create a new Node storing pData. The mNext reference is initialized to null because // the new Node will become the tail Node of the DList and the mNext reference of the // tail Node is always null. The mPrev reference is initialized to mail so it will // refer to the Node preceding the new Node. Node newNode = new Node(pData, getTail(), null); 1/ If this list is empty the new Node becomes the head Node. Otherwise whange mNext of // the tail Node to refer to the new Node. if (isEmpty()) setHead(newNode); else getTail().setNext(newNode); // In any case, we must change mTail to refer to the new Node that is now at the tail. setTail(newlode); 1ee 101 102 2 1! We are not appending. else { 1/ Get a reference to the Node at Node node - getNodeAt(pIndex); a new Node before 'node les DListjava X 99 100 101 !! we are not appending. 102 // We are not appending. else { 1/ Get a reference to the Node at pIndex. We are inserting a new Node before 'node'. Node node - getNodeAt(pIndex); 164 105 L06 e7 // Create a new Node storing pData. Set the mPrev reference of the new Node to refer to // the Node preceding 'node'. Set the mNext reference of the new Node to refer to 11 'node'. Node newNode = new Node (pData, node.getPrev(), node); // If we are not inserting at pIndex = @ then we need to change the mext reference of 11 the Node preceding 'node' to refer to the new Node. if (pIndex != e) node.getPrev().setNext(newNode); Don 1/ Make the mPrev reference of 'node' refer to the new Node. The result of these three 1/ operations is to "link" the the new Node into the DList. node.setPrev(newlode); // Are we inserting at index @? If so, we need to change the head to refer to the new // Node because the new Node is now at head. if (pIndex == 0) setHead(newlode); // We have added a new Node to the Dist. Increment the size of the DList. setSize(getSize() + 1); Appends a new Node storing pData to this Dist. Note that passing an index of getSize() to add (int pIndex, Integer pData) will cause add() to perform an append operation. public void append(Integer pData) { 280 29 Appends a new Node storing pData to this DList. Note that passing an index of getSize() to * add(int pIndex, Integer pData) will cause add() to perform an append operation. 30 32e public void append(Integer pData) { add(getSize(), pData); 34 36e /** * Removes all of the elements from the Dist. After this operation the DList will be empty. 38 39 40 until the list becomes public void clear() { // To clear the list is simple. Simply remove the node at index // empty. while (!isEmpty()) { remove(); } 43 44 45 46 * Returns the element at index pIndex. * Thows IndexOutOfBoundsException if pIndex = mSize. public Integer get(int pIndex) throws IndexOutOfBoundsException { return getNodeAt (pIndex).getData(); 50- -51 52 53 54 55 - Accessor method for the mead field. 56 1572 protected Node getHead() { return mHead; 159 1540 155 156 157e * Accessor method for the mHead field. */ protected Node getHead() { return mHead; /** * Returns a reference to the Node at index pIndex. 165 1660 167 168 * Thows IndexOutOfBoundsException if pIndex = getSize() */ protected Node getNodeAt(int pIndex) throws IndexOutOfBoundsException { 1/ Check for pIndex out of bounds and throw exception is necessary. if (pIndex = getSize() throw new IndexOutOfBoundsException(); 1/ Since accessing the head and tail nodes is a common operation we check for those cases // first. if (pIndex == @) return getHead(); else if (pIndex -- getSize() - 1) return getTail(); BE // Otherwise, start at the node at index 1 and walk forward until the node at index pIndex is reached and then return it. Node node = getHead().getNext(); for (int index = 1; index = getSize(). 216 217 public Integer remove(int pIndex) throws IndexOutOfBounds Exception { 218 Node node - getNodeAt (pIndex); 220 (Are we removing the only element in a list with one element? 229 Uw HLAVULVT VVURULALLPLAVI 13 PIRULA T PAHULA :- -70 public Integer remove(int pIndex) throws IndexOutOfBoundsException { Node node = getNodeAt (pIndex); // Are we removing the only element in a list with one element? if (getSize() == 1) { setHead(null); setTail(null); BE6BSNP vouw // Else are we removing the head node in a list with more than one element (note: we will // not get here if the list has only one element)? else if (pIndex == 0) { 1/ Change the prev reference of the next node to null because the next node will now // be the head node in the list. node.getNext().setPrev(null); // Since we removed the head node, we have to change the head reference to refer to the 1/ next node succeeding the one that was just removed. setHead (node.getNext(); // Else are we removing the tail node in a list with more than one element (note: we will 1/ not get here if the list has only one element)? else if (pIndex == getSize() - 1){ 1/ Change the next reference of the previous node to null because the previous node will // now be the tail node in the list. node.getPrev().setNext(null); // Since we removed the tail node, we have to change the tail reference to refer to the Il previous node preceding the one that was just removed. setTail(node.getPrev(); 46 // We are not removing the head or tail node. mmmmst. 2 Else are we removing the tail node in a list with more than one element (note: we will // not get here if the list has only one element)? else if (pIndex = getSize() - 1) { 77 Change the next reference of the previous node to null because the previous node will // now be the tail node in the list. node.getPrev().setNext(null); // Since we removed the tail node, we have to change the tail reference to refer to the 1/ previous node preceding the one that was just removed. setTail(node.getPrev()); 1/ We are not removing the head or tail node. else { node.getPrev().setNext(node.getNext(); node.getNext().setPrev(node.getPrev(); No // We have removed a Node so decrement the size of the list. setSize(getSize() - 1); // Return the data stored at the removed Node. return node.getData(); 54 Replaces the element at the specified position in this list with the specified element. Returns the element that was previously stored at pIndex. public Integer set(int pIndex, Integer pData) throws IndexOutOfBoundsException { Node node = getNodeAt(pIndex); Integer original = node.getData(); node.setData(pData); return original; 70 74- Mutator method for the mead field. 64 * Replaces the element at the specified position in this list with the specified element. Returns the element that was previously stored at pIndex. * 66 670 public Integer set(int pIndex, Integer pData) throws IndexOutOfBoundsException { Node node = getNodeAt (pIndex); Integer original = node.getData(); node.setData(pData); return original; -71 72 -73 2746 275 /* * Mutator method for the mead field. 276 277e 278 279 280 2819 282 protected void setHead (Node pHead) { mHead = pHead; } /** Mutator method for the mize field. 283 protected void setSize(int pSize) { mSize = pSize; } 2840 285 286 287 288- 289 290 2914 292 293 294 295- 296 297 298 "Mutator method for the mail field. / protected void setTail(Node prail) { mTail = pTail; Returns a string representation of this DList where we define string representation be the string representation of each of the Nodes. 299- @Override @Override public String toString() { String string = ""; for (int i = 0; i and Binary TreeVisitor classes in the Week 7 Source Code zip archive are generic classes which means in English that we can use the Binary Tree class to store elements of any data type (of course, all of the elements still have to be of the same type or in the same inheritance hierarchy). For example, we may wish to create a Binary Tree of Students by writing BinaryTree tree = new BinaryTree(); Learning Objectives for Exs. 5.1-5.5: The student shall be able to write a generic binary tree class and shall be able to explain the characteristics of binary trees. 5.1 Consider this binary tree. (a) List the descendants of node 8. (b) List the ancestors of 1. (C) List the leaf nodes. (d) List the internal nodes. (e) What are the levels of nodes 3. 1. and 9? (f) What is the height of the tree? (g) What is the height of the subtree rooted at 6? (h) Is this a full binary tree? Explain. (i) Explain how we could transform this tree to be a complete binary tree, i.e., state which nodes we would move and where we would move them to 5 5.2 (a) List the nodes in the order they would be visited during a level order traversal. (b) List the nodes in the order they would be visited during an inorder traversal (c) List the nodes in the order they would be visited during a preorder traversal. (d) List the nodes in the order they would be visited during a postorder traversal. 5.3 (Include your modified Binary Tree.java source code file in your homework solution zip archive) Add a method int getSize() to Binary Tree that returns the size of the binary tree, where the size of the tree is defined to be the number of nodes. Here is how I want you to implement this method. Write a local class (see Module 3: Objects and Classes II : Section 2) in method public int getSize() named Counter which implements the Binary Tree Visitor interface: - implements Counter -m Count: int + Counter(): ctor +get Count(); int +visit (pData: E): void interface Binary TreeVisitor visit (pData: E): void The Counter constructor initializes the counter variable mCount to 0, and the Counter.visit() method will be called each a time a node is visited either from Binary Tree. traverse(int, Node, Binary TreeVisitor) or Binary Tree. traverse LevelOrder(Node, Binary TreeVisitor) depending on whether you performed a level order traversal or one of the three other types of traversals as described below. Within Counter.visit(), we simply increment mCount to count the node as visited. Once the local class is completed, we can count the nodes in the tree by performing a traversal (it does not matter which type of traversal we perform because each node will be visited during the traversal; the order in which we visit them does not matter for this application). To perform the traversal write: public int getSize() { // Implement local class named Counter here ??? Once the local class is completed, we can count the nodes in the tree by performing a traversal (it does not matter which type of traversal we perform because each node will be visited during the traversal; the order in which we visit them does not matter for this application). To perform the traversal write: public int getSize() { // Implement local class named Counter here ??? // Create a Counter object to count the nodes Counter counter - new Counter(); 11 I have chosen to perform a level order traversal, but try the other ones to verify they work // the same way as well, e.g, traverse (PRE_ORDER, counter) traverse (LEVEL_ORDER, counter); 17 After we finish the traverse, Counter. mCount is equal to the number of nodes visited, which // 15 the size of the tree. return counter getCount(); 5.4 If n is the size of the tree, what is the worst case time complexity of getSize() in Big O notation? 5.5 The Binary Tree.Iterator class uses a stack (the mStack instance variable to store references to parent nodes as the iterator moves left and right downward in the tree. The stack of parent nodes is necessary because the moveUpo method needs to change the iterator's current node reference to be the parent node of the current node when move Up() is called. However, storing the parent nodes on a stack is not the only way to implement moveUp(). Furthermore, in certain tree methods (that are not currently implemented), it would be very helpful to have a reference to the parent node. traverse(LEVEL_ORDER, counter); 11 After we finish the traverse, Counter.mCount is equal to the number of nodes visited, which // is the size of the tree. return counter.getCount(); 5.4 If n is the size of the tree, what is the worst case time complexity of getSize() in Big O notation? 5.5 The Binary Tree.Iterator class uses a stack (the mStack instance variable) to store references to parent nodes as the iterator moves left and right downward in the tree. The stack of parent nodes is necessary because the moueUpO method needs to change the iterator's current node reference to be the parent node of the current node when move Up() is called However, storing the parent nodes on a stack is not the only way to implement move Up(). Furthermore, in certain tree methods (that are not currently implemented), it would be very helpful to have a reference to the parent node. For this exercise we will modify the Binary Tree, Binary Tree. Node, and Binary Tree.Iterator classes so each node will store a reference to its parent (for the root node, the parent reference will be null). First, modify the Binary Tree.Node class to add a new instance variable Node mParent which will always contain a reference to the parent node of a node (for the root node, mParent will be null). Add accessor and mutator methods for mParent to the Node class. Modify the Node constructors thusly: public Node() { this(null, null); public Node (E pData, Node pParent) { this(pData, null, null, pParent); public Node (E pData, Node PLeft, Node PRight, Node pParent) { setData(pData); setLeft (Left); setRight (pRight); setParent (pParent); Second, modify the Binary Tree. Iterator E class to eliminate the mStack instance variable and the getStack() and setStack() accessor and mutator methods. Then modify these Iterator methods: public Iterator (BinaryTree pTree) { setTree(pTree); setCurrent(getTree().getRoot()); setStack(new Stack>0} // Delete this line public void addLeft(E pData) throws Empty TreeException { if (getTree().isEmpty()) throw new Empty TreeException(); pruneLeft(); getCurrent().setLeft (new Node(pData, getCurrent())); public void addRight (E pData) throws Empty Tree Exception { 1 + 1 ENT public Iterator (BinaryTree PTree) { setTree(pTree); setCurrent (getTree().getRoot()); setStack(new Stack0); // Delete this line public void addLeft (E pData) throws EmptyTreeException { if (getTree().isEmpty()) throw new EmptyTreeException(); pruneLeft(); getCurrent().setLeft(new Node (pData, getCurrent())); public void addRight (E pData) throws EmptyTreeException { if (getTree().isEmpty()) throw new EmptyTreeException(); pruneRight(); getCurrent().setRight(new Node (pData, getCurrent())); public void moveLeft() { if (getCurrent() hasLeft()) { getStacko.push(getCurrent 0) setCurrent (getCurrent().getLeft()); U H U J USJUUw12/Appuata/local/lemp/lempl_cse205-604.zip/cse205-604/doc/cse205 h04.pdf getStack).pushtgetOurrento), setCurrent (getCurrent().getLeft()); public void moveRight() { if (getCurrent() hasRight()) { getStack().push(getCurrent A); setCurrent (getCurrent().getRight()); public void move To Root() { getStack .clear setCurrent (getTree().getRoot()); public void moveUp() { setCurrent [getStack() .pop); if (getCurrent().getParent() ! - null) { setCurrent (getCurrent().getParent(); Finally, modify this Binary Tree constructor public BinaryTree (E pData, BinaryTree pLeft, BinaryTree pRight) { Node E left Child = pLeft == null ? null : pLeft.getRoot(); Node rightChild = pRight == null ? null : pRight.getRoot(); setRoot(new Node treeLeft - new BinaryTree(3); 1/ 3 Binary Tree. Iterator itLeft = treeLeft. iterator(); itLeft.addLeft(10); itLeft addRight (20) // 10 20 BinaryTree treeRight = new Binary Tree (5); // 5 BinaryTree. Iterator itRight = treeRight. iterator(); // itRight addLeft(100); it Right addRight (200); itRight.moveLeft(); // 100 200 BinaryTree Integer> tree Test - new BinaryTree (9 treeLeft, treeRight); // 9 1/ Prints: 9 3 5 10 20 100 200 treeTest traverse (BinaryTree. LEVEL_ORDER, this); 11 3 5 System.out.println(); Binary Tree. Iterator Integer> itTest = treeTest iter ator(); // 10 20 100 200 itTest.moveLeft(); itTest.moveLeft(); System.out.println(itTest.get()); // Prints: 10 itTest.moveUpO; System.out.println(itTest.get(); // Prints: 3 itTest.moveUpO; System.out.println(itTest.get(); 1/ Prints: UP 50 BinaryTree treeTest - new BinaryTree(9, treeLeft, treeRight); // 9 // Prints: 9 3 5 10 20 100 200 treeTest. traverse (Binary Tree. LEVEL_ORDER, this); 113 System.out.println(); // / Binary Tree.Iterator itTest = treeTest. iterator // 10 20 100 200 itTest.moveLeft(); itTest.moveLeft(); System.out.println(it Test.get()); // Prints: 10 itTest.moveUp(); System.out.println(itTest. 1/ Prints: 3 itTest.moveUp(); System.out.println(itTest.get()); 1/ Prints: 9 itTest.moveUp(); System.out.println(itTest.get(); // Prints: 9 Learning Objectives for Exercises 5.6-5.9: The student shall be able to explain what a BST is and to explain the characteristics of BST'S. A BST is created (it is initially empty) where the key associated with the data in each node is an integer. Elements are added to the BST with these keys in this order: 5, 4, 8, 7, 6, 9, 3, 2, 1. (a) Draw the resulting BST. (b) What is the height of the tree? For the tree of Exercise 5.6 complete this table which lists how many key comparisons will be made to locate each of the keys in the tree. 5.6 5.7 Key Number of Key Comparisons to Locate Node Containing Key CON // Prints: 3 1tTest.moveUp(); System.out.println(itTest.get()) itTest.moveUp(); System.out.println(itTest.get()); it Test.moveUp(); System.out.println(itTest.get()); // Prints: 9 // Prints: 9 5.6 Learning Objectives for Exercises 5.6-5.9: The student shall be able to explain what a BST is and to explain the characteristics of BST'S. A BST is created (it is initially empty) where the key associated with the data in each node is an integer. Elements are added to the BST with these keys in this order: 5, 4, 8, 7, 6, 9, 3, 2, 1. (a) Draw the resulting BST. (b) What is the height of the tree? 5.7 For the tree of Exercise 5.6 complete this table which lists how many key comparisons will be made to locate each of the keys in the tree. Key Number of Key Comparisons to Locate Node Containing Key lowlto Nr What is the average number of comparisons? 5.8 Continuing, assume the keys of Exercise 5.6 are integers which are appended to a linked list of integers, ie, the elements of the list will be 5, 4, 8, ---, 2, 1. Assume we always start from the head node when searching for an element. Complete this table which lists the number of comparisons that are made to locate each element in the list. Element Number of Comparisons to Locate the Element What is the average number of comparisons? 5.9 How much faster, expressed as a percentage, are searches in this particular BST than searches in this particular linked list? Next, create an empty folder named asuriteid-104 and copy asuriteid-104.pdf to that folder. For the linked list exercises 4.1 and 4.3, copy your modified DList.java source code file to the asurite-04 folder. For the binary tree tree exercise 5.3 copy your modified Binary Tree.java source code folder to the asuriteid-h04 folder. (Note: Java source code files are the files with a java file name extension; do not copy the class files or any data files as we do not need those.) Then compress the asuriteid-h04 folder creating a zip archive file named asuriteid-h04.zip. Upload asuriteid-104.zip to Canvas using the submission link on the Module 7: HW4 Due submission page before the assignment deadline. Please see the Course Summary section on the Syllabus page in Canvas for the deadline. The deadline can also be found on the CSE205 course calendar, look for the event named Module 7: HW4 Due. . Consult the Syllabus for the late and academic integrity policies 2 Learning Objectives 1. To use the merge sort and quick sort sorting algorithms to sort a list of elements. 2. To analyze the time complexity of the merge sort and quick sort sorting algorithms. 3. To implement linked list, stack, queue, and tree data structures. 4. To analyze the time complexity of linked list, stack, queue, and tree operations. 5. To implement a binary search tree (BST) data structure 6. To analyze the time complexity of BST operations. 3 Sorting 3.1 Learning Objectives for Exs. 3.1-3.4: To demonstrate that the student understands how the merge sort algorithm sorts a list. In the video lecture Sorting Algorithms: Section ? : Merge Sort Example we traced how merge sort would recursively sort list = { 4. 2. 7, 3, 5, 13, 11, 8, 6,2 }. For this exercise, I would like you to draw a similar diagram showing how merge sort would sort list = { 5.3, 1.6, 2. + }. Scan this diagram and insert it into your final PDF 3.2 In Sorting Algorithms : Section 9 : Merge Sort Pseudocode we discussed the high-level pseudocode for the merge soru algorithm. I wrote three methods: recursive MergeSort(), merge(), and copyRest). Continuing the previous exercise, how many times will recursive.Merge Sort() be called when sorting the list of Exercise 3.1. Include the original non- recursive call to recursive MergeSort() and all of the subsequent recursive calls in the answer. 3.3 Continuing Exs. 3.1-3.2, how many times will merge() be called? 3.4 Continuing Exs. 3.1-3.2, during the final call to merge when we are merging list and lists to form the final sorted list-copyRest() will be called. (a) When copyRest() executes, which list will be srcList (listy or lista)? (b) What will be the value of srcIndex? (c) Which list will be dstList? (d) What will be the value of dstinder? 3.5 Learning Objectives for Exs. 3.5-3.7: To demonstrate that the student understands how the quick sort algorithm sorts a list. Consider list = { 5, 4, 2, 9, 1, 7, 3, 8, 6 } and the quick sort algorithm. Assume we always choose the first list item in the list being partitioned as the pivot, as you did in Project 3. Trace the partition method showing how list is partitioned into list and listy. To get you started, here is the format of what I am looking for in your solution: list - {5, 4, 2, 9, 1, 7, 3, 8, 6}, pivot - 5, left Inder - -1, rightInder - 9 While loop pass 1: left Inder ends up at o, rightInder ends up at 6 left Inder = right Inder - ??? partition() returns ??? so list: - {???}. lists = { ???), first list item in the list being partitioned as the pivot, as you did in Project 3. Trace the partition method showing how list is partitioned into list and liste. To get you started, here is the format of what I am looking for in your solution: list = { 5, 4, 2, 9, 1, 7, 3, 8, 6), pivot - 5, leftInder --1, rightInder = 9 While loop pass 1: leftInder ends up at o, right Index ends up at 6 leftInder = right Index = 777 partition() returns 777 so list: = { ??? }, liste = { ??? }, 3.6 Choosing the first list element as the pivot does not always lead to a good partitioning (ideally, the sizes of list and listy will be approximately equal). Suppose list = {1, 2, 3, 4, 5, 6, 7, 8 } and we again select the first element as the pivot. What would list and liste be? For this exercise, you do not have to write a detailed trace of the partition method as you did for the previous exercise; simply list what index would be returned by partition) and the con- tents of list, and listy 3.7 Starting with lista from the previous exercise, repeat Exercise 3.6 on lista. Explain what pattern is going to hold if we continue to partition each successive listy 4 Linked Lists Important Note: There are two version of Distjava in the Week 6 Source Code and Week 7 Source Code zip archives The two versions are mostly identical with this difference: the DList class in the Week 6 Source Code zip archive is designed to store elements only of the java.lang. Integer data type, eg.. we could not use this class to store Circles or DList.java X 14 150 /** 16 * Implements a doubly linked list of Integers. 17 18 public class DList { == //=== ===== // DList Instance Variables //======== * For a nonempty Dlist, mHead is a reference to the first Node in the DList. For an empty * DList, mHead will be null. private Node mHead; * The number of Nodes containing data in this blist. For an empty Dlist, mize is e. private int mSize; *For a nonempty DList, mail is a reference to the last Node in the DList. For an empty DList, mail will be null. private Node mTail; / DList Instance Methods Creates an empty Duist. For an empty Dist, mHead = null, mail - null, and mSize = 0. DList.java X 44 45e 46 Creates an empty Dlist. For an empty Dlist, mHead = null, mTail = null, and mSize - 0. 47 480 49 50 public DList() { setHead(null); setTail(null); setSize(); 52 53 540 * Creates a new DList with one element containing pData. 56 57e public DList(Integer pData) { 1/ Create a new Node storing pData. The ctor makes the mPrev and mNext references null. Node newNode = new Node (pData); 17 Make the mhead reference refer to the new node. setHead(newNode); 889888898 // Make the mail reference refer to the new node. setTail(newNode); // The size of the list is now 1. setSize(1); 712 * Inserts a new Node containing pData into this list at index pIndex. Shifts the element currently at that index (if it exists) and succeeding elements to the right (i.e., adds one to their indices). Note that if pIndex == getSize() the new element is appended to the list. Throws an IndexOutOfBounds Exception if pIndex size of the Dist. * Inserts a new Node containing pData into this list at index pIndex. Shifts the element currently at that index (if it exists) and succeeding elements to the right (i.e., adds one to their indices). Note that if pIndex = getSize() the new element is appended to the list. * Throws an IndexOutOfBoundsException if pIndex size of the DList. */ 80e public void add(int pIndex, Integer pData) throws IndexOutOfBoundsException { 1/ Check for pIndex out of bounds. if (pIndex getSize() throw new IndexOutOfBoundsException(); 1/ Are we appending? if (pIndex = getSize() { // Create a new Node storing pData. The mNext reference is initialized to null because // the new Node will become the tail Node of the DList and the mNext reference of the // tail Node is always null. The mPrev reference is initialized to mail so it will // refer to the Node preceding the new Node. Node newNode = new Node(pData, getTail(), null); 1/ If this list is empty the new Node becomes the head Node. Otherwise whange mNext of // the tail Node to refer to the new Node. if (isEmpty()) setHead(newNode); else getTail().setNext(newNode); // In any case, we must change mTail to refer to the new Node that is now at the tail. setTail(newlode); 1ee 101 102 2 1! We are not appending. else { 1/ Get a reference to the Node at Node node - getNodeAt(pIndex); a new Node before 'node les DListjava X 99 100 101 !! we are not appending. 102 // We are not appending. else { 1/ Get a reference to the Node at pIndex. We are inserting a new Node before 'node'. Node node - getNodeAt(pIndex); 164 105 L06 e7 // Create a new Node storing pData. Set the mPrev reference of the new Node to refer to // the Node preceding 'node'. Set the mNext reference of the new Node to refer to 11 'node'. Node newNode = new Node (pData, node.getPrev(), node); // If we are not inserting at pIndex = @ then we need to change the mext reference of 11 the Node preceding 'node' to refer to the new Node. if (pIndex != e) node.getPrev().setNext(newNode); Don 1/ Make the mPrev reference of 'node' refer to the new Node. The result of these three 1/ operations is to "link" the the new Node into the DList. node.setPrev(newlode); // Are we inserting at index @? If so, we need to change the head to refer to the new // Node because the new Node is now at head. if (pIndex == 0) setHead(newlode); // We have added a new Node to the Dist. Increment the size of the DList. setSize(getSize() + 1); Appends a new Node storing pData to this Dist. Note that passing an index of getSize() to add (int pIndex, Integer pData) will cause add() to perform an append operation. public void append(Integer pData) { 280 29 Appends a new Node storing pData to this DList. Note that passing an index of getSize() to * add(int pIndex, Integer pData) will cause add() to perform an append operation. 30 32e public void append(Integer pData) { add(getSize(), pData); 34 36e /** * Removes all of the elements from the Dist. After this operation the DList will be empty. 38 39 40 until the list becomes public void clear() { // To clear the list is simple. Simply remove the node at index // empty. while (!isEmpty()) { remove(); } 43 44 45 46 * Returns the element at index pIndex. * Thows IndexOutOfBoundsException if pIndex = mSize. public Integer get(int pIndex) throws IndexOutOfBoundsException { return getNodeAt (pIndex).getData(); 50- -51 52 53 54 55 - Accessor method for the mead field. 56 1572 protected Node getHead() { return mHead; 159 1540 155 156 157e * Accessor method for the mHead field. */ protected Node getHead() { return mHead; /** * Returns a reference to the Node at index pIndex. 165 1660 167 168 * Thows IndexOutOfBoundsException if pIndex = getSize() */ protected Node getNodeAt(int pIndex) throws IndexOutOfBoundsException { 1/ Check for pIndex out of bounds and throw exception is necessary. if (pIndex = getSize() throw new IndexOutOfBoundsException(); 1/ Sin