1 Submission Instructions

Create a document using your favorite word processor and type your exercise solutions. At the top of the document be

sure to include your name and the homework assignment number, e.g. HW4. Convert this document into Adobe PDF

format and name the PDF file <asuriteid>.pdf where <asuriteid> is your ASURITE user id (for example, my ASURITE

user id is kburger2 so my file would be named kburger2.pdf). To convert your document into PDF format, Microsoft Office

versions 2008 and newer will export the document into PDF format by selecting the proper menu item from the File

menu. 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 code

files to this folder (note: Java source code files are the files with a .java file name extension; do not copy the .class files as

we do not need those).

Next, compress the <asuriteid> folder creating a zip archive file named <asuriteid>.zip. Upload <asuriteid>.zip to the

Homework Assignment 4 dropbox by the assignment deadline. The deadline is 11:59pm Wed 30 Apr. Consult the online

syllabus 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 be

added to your homework assignment point total before computing your homework assignment percentage. Your homework

assignment percentage is limited to a maximum of 100%, e.g., if you ended up earning 95 homework points your

homework percentage would be calculated as min(95 / 87.5, 1.0).

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 compexity of BST operations.

3 Sorting

3.1 In the video lecture for Sorting Algorithms : Section 7 : 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, 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 merge

sort algorithm. I wrote three methods: recursiveMergeSort(), merge(), and copyRest(). Continuing the previous

exercise, how many times will recursiveMergeSort() be called when sorting the list of Exercise 3.1. Include the

original 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 be

the 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 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 (next page):

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 6

leftIndex < 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 and

listR 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 listL and listR 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

contents 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 if

we continue to partition each successive listR.

4 Linked Lists

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 < the size of this 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.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 is

O(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 proportional

to the time complexity of getNodeAt(i).

Now what is the time complexity of getNodeAt(i)? The key operations in getNodeAt() are the assignments of

getHead().getNext() before the loop starts and the assignment of node.getNext() to node during each iteration of the

for loop. For getNodeAt(0) and getNodeAt(n – 1) the key operations will never be performed so the best case time

complexity 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. Then

specify what the worst case time complexity of removeAll() is in big O notation (you don’t have to provide a formal

proof; just do a little hand waving).

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().

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 to

ensure that your new remove() method still works correctly. Also, make sure add() still throws an IndexOutOf

BoundsException 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, you

may wonder if the pseudocode of Exercise 4.1 is really the best way to remove all nodes containing a specific value

from the list. For this exercise, comment out the statements in removeAll() that that you implemented in Exercise

4.1, and provide a more efficient implementation of this method. Reuse your same test case from Exercise 4.1 to

verify that your new implementation works correctly.

Rather than giving you pseudocode, I will give you a hint by describing the general procedure. Create a Node object

named node which initially refers to the head of the list. Compare the data in the head node to pData. If they

match, call removeHead() to remove the head node (note that the next node you will visit will be the new head

node). If they do not match, make node refer to the node succeeeding head. Compare the data in the element in the

node to pData. if they match, and if this is not the tail node, call removeInterior() to remove the node. Continue

moving 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 calling

getNodeAt(index) or remove(index); the only methods my solution uses are getHead(), removeHead(), remove

Interior(), 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 of

times the key operation is performed as a function of the list size n, and then state that f(n) is O(g(n)) for some

g(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” this

DList (the one on which the method is invoked) into a left sublist pLeft and a right sublist pRight. The elements of

pLeft will consist of list elements at indices 0, 1, 2, …, pIndex – 1. The elements of pRight will consist of list elements

at indices pIndex, pIndex + 1, …, getSize() – 1. Note that pLeft and pRight must be created (and are assumed to be

empty) 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 BSTs

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.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 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 Visitor<E>

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.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 (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 moveUp() method needs to change the iterator’s current

node 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 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 BinaryTree, BinaryTree.Node, and BinaryTree.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 BinaryTree.Node<E> class to add a new instance variable Node<E> 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<E> pParent) {

this(pData, null, null, pParent);

}

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() and

setStack() 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());

}

}

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); // 3

BinaryTree.Iterator<Integer> itLeft = treeLeft.iterator(); // /

itLeft.addLeft(10); itLeft.addRight(20); // 10 20

BinaryTree<Integer> treeRight = new BinaryTree(5); // 5

BinaryTree.Iterator<Integer> itRight = treeRight.iterator(); // /

itRight.addLeft(100); itRight.addRight(200); itRight.moveLeft(); // 100 200

BinaryTree<Integer> treeTest = new BinaryTree(9, treeLeft, treeRight); // 9

// Prints: 9 3 5 10 20 100 200 // /

treeTest.traverse(BinaryTree.LEVEL_ORDER, this); // 3 5

System.out.println(); // / /

BinaryTree.Iterator<Integer> itTest = treeTest.iterator(); // 10 20 100 200

itTest.moveLeft(); itTest.moveLeft();

System.out.println(itTest.get()); // Prints: 10

itTest.moveUp();

System.out.println(itTest.get()); // Prints: 3

itTest.moveUp();

System.out.println(itTest.get()); // Prints: 9

itTest.moveUp();

System.out.println(itTest.get()); // Prints: 9

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?

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

1

2

3

4

5

6

7

8

9

What is the average number of comparisons?

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.

Element Number of Comparisons to

Locate the Element

1

2

3

4

5

6

7

8

9

What 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 this

particular linked list?