3.9)

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. Trace the partition method showing how list is partitioned into listL and listR.

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, leftIndex = -1, rightIndex = 9

While loop pass 1:

leftIndex ends up at 0, rightIndex ends up at 9

leftIndex

While loop pass 2:

...

While loop pass 3:

...

While loop terminates because leftIndex = ??? >= rightIndex = ???

partition() returns ??? so listL = { ??? }, listR = { ??? },

4.1

(Include your modified DList.java source code file in your homework solution zip archive) Using whatever Java IDE you prefer, create a project and add DList.java and DListTest.java to it (these files are provided in the Week 6 Source zip archive). Modify DList to implement a method that removes all occurrences of a specific integer from the list. Here is the pseudocode:

Method removeAll(In: Integer pData) Returns Nothing Define index variable i and initialize i to 0 While i Dlist Do

If get(i) equals pData Then remove(i)

Else Increment i

End If

End While

End Method removeAll

Next, modify DListTest() to add test case 21 which tests that removeAll() works correctly.

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 simpler and more readable (my new and improved remove() method is half-a-dozen lines of code). Be sure to run the test cases in DListTest to ensure that your new remove() method still works correctly. Also, make sure remove() throws an IndexOutOfBoundsException if pIndex is less than 0 or greater than or equal to getSize().

5.1

5.3 (Include your modified BinaryTree.java source code file in your homework solution zip archive) Add a method int getSize() to BinaryTree 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 Week 3 : Objects and Classes II : Section 2) in getSize() named Counter which implements the BinaryTree VisitorE> interface:

The Counter constructor initializes mCount to 0. visit() simply increments mCount when it is called. 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 performe 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 ??? Counter counter = new Counter(); traverse(LEVEL_ORDER, counter); return counter.getCount();

}

5.6

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?

The height is 4.

5.8 (1 bonus pt) Continuing, assume the keys of Exercise 5.6 are integers which are appened to a linked list of integers, i.e., 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.

What is the average number of comparisons?

Now for element 1, Comparison= 1*5=5

for element 2, Comparison= 1*4=4

for element 3, Comparison= 1*3=3

for element 4, Comparison= 1*2=2

for element 5, Comparison= 1*1=1

for element 6, Comparison= 1*4=4

for element 7, Comparison= 1*3=3

for element 8, Comparison= 1*2=2

for element 9, Comparison= 1*3=3

So total comparison=27, Total nodes in BST=9

Average Comparison= 27/9=3

PLEASE ANSWER 5.9 and 5.4

5.9 (1 bonus pt) How much faster, expressed as a percentage, are searches in this particular BST than searches in this particular linked list?

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?

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.orderedAdd(3); 

list.orderedAdd(1); 

list.orderedAdd(7); 

list.orderedAdd(9); 

list.orderedAdd(-5); 

// list = { 5 } // list = { 3 5 } // list = { 1 3 5} // list = { 1 3 5 7} // list = { 1 3 5 79 } // list = { -5 1 3 5 7 9 }

5 Binary Trees and BSTs 5.1 Consider this binary tree. (a) List the descendants of node 8. (b) List the ancestors of 1. 7 X (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. 8 8 6 4 9 5 Binary Trees and BSTs 5.1 Consider this binary tree. (a) List the descendants of node 8. (b) List the ancestors of 1. 7 X (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. 8 8 6 4 9