CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)

CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)1 Submission InstructionsCreate a document using your favorite word processor and type your exercise solutions. At the top of the document besure to include your name and the homework assignment number, e.g. HW4. Convert this document into Adobe PDFformat and name the PDF file <asuriteid>.pdf where <asuriteid> is your ASURITE user id (for example, my ASURITEuser id is kburger2 so my file would be named kburger2.pdf). To convert your document into PDF format, Microsoft Officeversions 2008 and newer will export the document into PDF format by selecting the proper menu item from the Filemenu. The same is true of Open Office and Libre Office. Otherwise, you may use a freeware PDF converter program, e.g.,CutePDF is one such program.Next, create a folder named <asuriteid> and copy <asuriteid>.pdf to that folder. Copy any requested Java source codefiles to this folder (note: Java source code files are the files with a .java file name extension; do not copy the .class files aswe do not need those).Next, compress the <asuriteid> folder creating a zip archive file named <asuriteid>.zip. Upload <asuriteid>.zip to theHomework Assignment 4 dropbox by the assignment deadline. The deadline is 11:59pm Wed 30 Apr. Consult the onlinesyllabus for the late and academic integrity policies.Note: not all of these exercises will be graded, i.e., random ones will be selected for grading.Exercises 4.7–4.9, 5.4, and 5.8–5.9 are optional and are worth bonus credit. Any points earned on these exercises will beadded to your homework assignment point total before computing your homework assignment percentage. Your homeworkassignment percentage is limited to a maximum of 100%, e.g., if you ended up earning 95 homework points yourhomework percentage would be calculated as min(95 / 87.5, 1.0).2 Learning Objectives1. 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 compexity of BST operations.3 Sorting3.1 In the video lecture for Sorting Algorithms : Section 7 : Merge Sort Example we traced how merge sort wouldrecursively sort list = { 4, 2, 7, 3, 5, 13, 11, 8, 6, 2 }. For this exercise, I would like you to draw a similar diagramshowing how merge sort would sort list = { 5, 3, 1, 6, 2, 4 }. Scan this diagram and insert it into your final PDF.The objective of this exercise is to essentially see if you understand how the merge sort procedure works.3.2 In Sorting Algorithms : Section 9 : Merge Sort Pseudocode we discussed the high-level pseudocode for the mergesort algorithm. I wrote three methods: recursiveMergeSort(), merge(), and copyRest(). Continuing the previousexercise, how many times will recursiveMergeSort() be called when sorting the list of Exercise 3.1. Include theoriginal nonrecursive call to recursiveMergeSort() and all of the recursive calls in the sum.3.3 Continuing, how many times will merge() be called?3.4 Continuing, during the final call to merge()—when we are merging listL and listR to form the final sorted list—copyRest() will be called. (a) When copyRest() executes, which list will be srcList (listL or listR)? (b) What will bethe value of srcIndex? (c) Which list will be dstList? (d) What will be the value of dstIndex?3.5 Consider list = { 5, 4, 2, 9, 1, 7, 3, 8, 6 } and the quick sort algorithm. Assume we always choose the first list itemin the list being partitioned as the pivot. Trace the partition method showing how list is partitioned into listL andlistR. To get you started, here is the format of what I am looking for in your solution (next page):Arizona State University Page 1CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)list = { 5, 4, 2, 9, 1, 7, 3, 8, 6 }, pivot = 5, leftIndex = -1, rightIndex = 9While loop pass 1:leftIndex ends up at 0, rightIndex ends up at 6leftIndex < rightIndex so swap list[0] and list[6]: list = { 3, 4, 2, 9, 1, 7, 5, 8, 6 }While loop pass 2:...While loop pass 3:...While loop terminates because leftIndex = ??? >= rightIndex = ???partition() returns ??? so listL = { ??? }, listR = { ??? },3.6 Choosing the first list element as the pivot does not always lead to a good partitioning (ideally, the sizes of listL andlistR will be approximately equal). Suppose list = { 1, 2, 3, 4, 5, 6, 7, 8 } and we again select the first element as thepivot. What would listL and listR be? For this exercise, you do not have to write a detailed trace of the partitionmethod as you did for the previous exercise; simply list what index would be returned by partition() and thecontents of listL, and listR.3.7 Starting with listR from the previous exercise, repeat Exercise 3.6 on listR. Explain what pattern is going to hold ifwe continue to partition each successive listR.4 Linked Lists4.1 (Include your modified DList.java source code file in your homework solution zip archive) Usingwhatever Java IDE you prefer, create a project and add DList.java and DListTest.java to it (these files are providedin the Week 6 Source zip archive). Modify DList to implement a method that removes all occurrences of a specificinteger from the list. Here is the pseudocode:Method removeAll(In: Integer pData) Returns NothingDefine index variable i and initialize i to 0While i < the size of this Dlist DoIf get(i) equals pData Thenremove(i)ElseIncrement iEnd IfEnd WhileEnd Method removeAllNext, modify DListTest() to add test case 21 which tests that removeAll() works correctly.4.2 Let n be the size of a DList, i.e., the number of elements. The remove(index) method is O(n). The get(i) method isO(n) because in the worst case, we have to traverse almost the entire list to locate the element at index i. Why?get(i) calls getNodeAt(i) to obtain a reference to the node at index i so the time complexity of get(i) is proportionalto the time complexity of getNodeAt(i).Now what is the time complexity of getNodeAt(i)? The key operations in getNodeAt() are the assignments ofgetHead().getNext() before the loop starts and the assignment of node.getNext() to node during each iteration of thefor loop. For getNodeAt(0) and getNodeAt(n - 1) the key operations will never be performed so the best case timecomplexity of getNodeAt() is O(1). In the worst case, i would be n - 2 and the key operations would be performed 1+ n - 2 = n - 1 times so the worst case time complexity is O(n).The key operations of removeAll() are the key operations of getNodeAt(). For this exercise, define a function f(n)which specifies the maximum number of times the key operations will occur as a function of the list size n. Thenspecify what the worst case time complexity of removeAll() is in big O notation (you don't have to provide a formalproof; just do a little hand waving).Arizona State University Page 2CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)4.3 (Include DList.java in your solution zip archive) Here is the Java implementation of three useful methods(which are not currently in Dlist)./*** Removes the head node from this DList. It would be inadvisable to call this method on an* empty list because we do not check for that condition. Returns the data stored in the head* node.*/protected Integer removeHead() {Integer data = getHead().getData();if (getSize() == 1) {setHead(null);setTail(null);} else {getHead().getNext().setPrev(null);setHead(getHead().getNext());}setSize(getSize() - 1);return data;}/*** Removes an interior node pNode from this DList. It would be inadvisable to call this method* when pNode is null because we do not check for that condition. Returns the data stored in* pNode.*/protected Integer removeInterior(Node pNode) {Integer data = pNode.getData();pNode.getPrev().setNext(pNode.getNext());pNode.getNext().setPrev(pNode.getPrev());setSize(getSize() - 1);return data;}/*** Removes the tail node from this DList. It would be inadvisable to call this method on an* empty list because we do not check for that condition. Returns the data stored in the tail* node.*/protected Integer removeTail() {Integer data = getTail().getData();if (getSize() == 1) {setHead(null);setTail(null);} else {getTail().getPrev().setNext(null);setTail(getTail().getPrev());}setSize(getSize() - 1);return data;}Using these three methods, rewrite the provided remove(index) method to make the code in that method simplerand more readable (my new and improved remove() method is half-a-dozen lines of code). Be sure to run the testcases in DListTest to ensure that your new remove() method still works correctly. Also, make sure remove() throwsan IndexOutOfBoundsException if pIndex is less than 0 or greater than or equal to getSize().Arizona State University Page 3CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)4.4 (Include DList.java in your solution zip archive) Here is the Java implementation of three useful methods(which are not currently in Dlist)./*** Adds a new node storing pData to be the new head of this DList.*/protected void addHead(Integer pData) {Node newNode = new Node(pData, null, getHead());if (getHead() == null) {setTail(newNode);} else {getHead().setPrev(newNode);}setHead(newNode);setSize(getSize() + 1);}/*** Adds a new node storing pData to be the predecessor to pNode pNode (pNode may be head or tail).*/protected void addInterior(Integer pData, Node pNode) {if (pNode == getHead()) {addHead(pData);} else {Node newNode = new Node(pData, pNode.getPrev(), pNode);pNode.getPrev().setNext(newNode);pNode.setPrev(newNode);setSize(getSize() + 1);}}/*** Adds a new node storing pData to be the new tail of this DList.*/protected void addTail(Integer pData) {Node newNode = new Node(pData, getTail(), null);if (getTail() == null) {setHead(newNode);} else {getTail().setNext(newNode);}setTail(newNode);setSize(getSize() + 1);}Using these three methods, rewrite add(index, data) to make the code in that method simpler and more readable(my new and improved add() method is half-a-dozen lines of code). Be sure to run the test cases in DListTest toensure that your new remove() method still works correctly. Also, make sure add() still throws an IndexOutOfBoundsException if pIndex is less than 0 or greater than getSize().4.5 (Include DList.java in your solution zip archive) If you determined the correct answer to Exercise 4.2, youmay wonder if the pseudocode of Exercise 4.1 is really the best way to remove all nodes containing a specific valuefrom the list. For this exercise, comment out the statements in removeAll() that that you implemented in Exercise4.1, and provide a more efficient implementation of this method. Reuse your same test case from Exercise 4.1 toverify that your new implementation works correctly.Arizona State University Page 4CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)Rather than giving you pseudocode, I will give you a hint by describing the general procedure. Create a Node objectnamed node which initially refers to the head of the list. Compare the data in the head node to pData. If theymatch, call removeHead() to remove the head node (note that the next node you will visit will be the new headnode). If they do not match, make node refer to the node succeeeding head. Compare the data in the element in thenode to pData. if they match, and if this is not the tail node, call removeInterior() to remove the node. Continuemoving node to each successive node, checking for a match and removing when necessary. Like the head node,removing the tail node has to be handled specially by calling removeTail(). Do not even think about callinggetNodeAt(index) or remove(index); the only methods my solution uses are getHead(), removeHead(), removeInterior(), removeTail(), and getNext() on the node when we need to move to the next node.4.6 Give an informal proof of the worst case time complexity of your new removeAll() method of Exercise 4.5. Basically,what I am looking for is an identification of the key operation, a function f(n) which counts the maximum number oftimes the key operation is performed as a function of the list size n, and then state that f(n) is O(g(n)) for someg(n).4.7 (1 bonus pt for each) (Include DList.java in your solution zip archive) Using the new add methods,rewrite append(data) and prepend(data).4.8 (4 bonus pts) (Include DList.java in your solution zip archive) Write a method void orderedAdd(Integer pData) that will insert Integers into a DList such that ascending sort order is maintained. For example,DList list = new DList(); // list = { }list.orderedAdd(5); // list = { 5 }list.orderedAdd(3); // list = { 3 5 }list.orderedAdd(1); // list = { 1 3 5 }list.orderedAdd(7); // list = { 1 3 5 7 }list.orderedAdd(9); // list = { 1 3 5 7 9 }list.orderedAdd(-5); // list = { -5 1 3 5 7 9 }4.9 (4 bonus pts) Write a method void split(int pIndex, DList pLeft, DList pRight) that will "split" thisDList (the one on which the method is invoked) into a left sublist pLeft and a right sublist pRight. The elements ofpLeft will consist of list elements at indices 0, 1, 2, ..., pIndex - 1. The elements of pRight will consist of list elementsat indices pIndex, pIndex + 1, ..., getSize() - 1. Note that pLeft and pRight must be created (and are assumed to beempty) before calling split(). For example:DList list = new DList(); // list = { }list.append(3); list.append(5); list.append(7); list.append(11);list.append(13); list.append(17); list.append(19); list.append(29);// list = { 3, 5, 7, 11, 13, 17, 19, 29 }DList left = new DList, right = new DList();list.split(5, left, right);// left = { 3, 5, 7, 11, 13 }, right = { 17, 19, 29 }5 Binary Trees and BSTs5.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 at6? (h) Is this a full binary tree? Explain. (i) Explain how we could transform this tree tobe a complete binary tree, i.e., state which nodes we would move and where we wouldmove them to.Arizona State University Page 5CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)5.2 (a) List the nodes in the order they would be visited during a level order traversal. (b) List the nodes in the orderthey would be visited during an inorder traversal. (c) List the nodes in the order they would be visited during apreorder traversal. (d) List the nodes in the order they would be visited during a postorder traversal.5.3 (Include your modified BinaryTree.java source code file in your homework solution zip archive) Adda method int getSize() to BinaryTree that returns the size of the binary tree where the size of the tree is definedto be the number of nodes. Here is how I want you to implement this method. Write a local class (see Week 3 :Objects and Classes II : Section 2) in getSize() named Counter which implements the BinaryTree Visitor<E>interface:The Counter constructor initializes mCount to 0. visit() simply increments mCount when it is called. Once the localclass is completed, we can count the nodes in the tree by performing a traversal (it does not matter which type oftraversal we performe because each node will be visited during the traversal; the order in which we visit them doesnot matter for this application). To perform the traversal write:public int getSize() {// Implement local class named Counter here???Counter counter = new Counter();traverse(LEVEL_ORDER, counter);return counter.getCount();}5.4 (1 bonus pt) If n is the size of the tree, what is the worst case time complexity of getSize() in big O notation?5.5 (Include BinaryTree.java in your solution zip archive) The BinaryTree.Iterator<E> class uses a stack (themStack instance variable) to store references to parent nodes as the iterator moves left and right downward in thetree. The stack of parent nodes is necessary because the moveUp() method needs to change the iterator's currentnode reference to be the parent node of the current node when moveUp() is called.However, storing the parent nodes on a stack is not the only way to implement moveUp(). Furthermore, in certaintree 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 BinaryTree, BinaryTree.Node, and BinaryTree.Iterator classes so each node willstore a reference to its parent (for the root node, the parent reference will be null).First, modify the BinaryTree.Node<E> class to add a new instance variable Node<E> mParent which will alwayscontain a reference to the parent node of a node (for the root node, mParent will be null). Add accessor and mutatormethods for mParent to the Node class. Modify the Node constructors thusly:public Node() {this(null, null);}public Node(E pData, Node<E> pParent) {this(pData, null, null, pParent);}Arizona State University Page 6CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)public Node(E pData, Node<E> pLeft, Node<E> pRight, Node<E> pParent) {setData(pData);setLeft(pLeft);setRight(pRight);setParent(pParent);}Second, modify the BinaryTree.Iterator class to eliminate the mStack instance variable and the getStack() andsetStack() accessor and mutator methods. Modify these Iterator methods:public Iterator(BinaryTree<E> pTree) {setTree(pTree);setCurrent(getTree().getRoot());setStack(new Stack<Node<E>>());}public void addLeft(E pData) throws EmptyTreeException {if (getTree().isEmpty()) throw new EmptyTreeException();pruneLeft();getCurrent().setLeft(new Node<E>(pData, getCurrent()));}public void addRight(E pData) throws EmptyTreeException {if (getTree().isEmpty()) throw new EmptyTreeException();pruneRight();getCurrent().setRight(new Node<E>(pData, getCurrent()));}public void moveLeft() {if (getCurrent().hasLeft()) {getStack().push(getCurrent());setCurrent(getCurrent().getLeft());}}public void moveRight() {if (getCurrent().hasRight()) {getStack().push(getCurrent());setCurrent(getCurrent().getRight());}}public void moveToRoot() {getStack().clear();setCurrent(getTree().getRoot());}public void moveUp() {setCurrent(getStack().pop());if (getCurrent().getParent() != null) {setCurrent(getCurrent().getParent());}}Arizona State University Page 7CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)Finally, modify this BinaryTree constructor:public BinaryTree(E pData, BinaryTree<E> pLeft, BinaryTree<E> pRight) {Node<E> leftChild = pLeft == null ? null : pLeft.getRoot();Node<E> rightChild = pRight == null ? null : pRight.getRoot();setRoot(new Node<E>(pData, leftChild, rightChild, null));if (leftChild != null) leftChild.setParent(getRoot());if (rightChild != null) rightChild.setParent(getRoot());}This driver routine will test things out (put this in Main.java):BinaryTree<Integer> treeLeft = new BinaryTree(3); // 3BinaryTree.Iterator<Integer> itLeft = treeLeft.iterator(); // / \itLeft.addLeft(10); itLeft.addRight(20); // 10 20BinaryTree<Integer> treeRight = new BinaryTree(5); // 5BinaryTree.Iterator<Integer> itRight = treeRight.iterator(); // / \itRight.addLeft(100); itRight.addRight(200); itRight.moveLeft(); // 100 200BinaryTree<Integer> treeTest = new BinaryTree(9, treeLeft, treeRight); // 9// Prints: 9 3 5 10 20 100 200 // / \treeTest.traverse(BinaryTree.LEVEL_ORDER, this); // 3 5System.out.println(); // / \ / \BinaryTree.Iterator<Integer> itTest = treeTest.iterator(); // 10 20 100 200itTest.moveLeft(); itTest.moveLeft();System.out.println(itTest.get()); // Prints: 10itTest.moveUp();System.out.println(itTest.get()); // Prints: 3itTest.moveUp();System.out.println(itTest.get()); // Prints: 9itTest.moveUp();System.out.println(itTest.get()); // Prints: 95.6 A BST is created (it is initially empty) where the key associated with the data in each node is an integer. Elementsare 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 isthe 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 ofthe keys in the tree.Key Number of Key Comparisons toLocate Node Containing Key123456789What is the average number of comparisons?Arizona State University Page 8CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts)5.8 (1 bonus pt) Continuing, assume the keys of Exercise 5.6 are integers which are appened to a linked list ofintegers, i.e., the elements of the list will be 5, 4, 8, ..., 2, 1. Assume we always start from the head node whensearching for an element. Complete this table which lists the number of comparisons that are made to locate eachelement in the list.Element Number of Comparisons toLocate the Element123456789What is the average number of comparisons?5.9 (1 bonus pt) How much faster, expressed as a percentage, are searches in this particular BST than searches in thisparticular linked list?Arizona State University Page 9