wed6am

The “Order” of Performance: (Big) O

• Basic idea:

1. Ignore constant factor: computer and language implementation details affect that: go for fundamental rate of increase with problem size.

2. Consider fastest growing term: Eventually, for large problems, it will dominate.

• Value: Compares fundamental performance difference of algorithms

• Caveat: For smaller problems, big-O worse performer may actually do better

T(n) = O(f(n))

• T(n) = time for algorithm on input size n

• f(n) = a simpler function that grows at about the same rate

• Example: T(n) = 3n2+5n-17 = O(n2)

• f(n) has faster growing term

• no extra leading constant in f(n)

T(n) = O(f(n)) Defined

1. $n0 and

2. $c such that

If n > n0 then c·f(n) ≥ T(n)

Example: T(n) = 3n2+5n-17

Pick c = 4, say; need 4n02 > 3n02+5n0-17

n02 > 5n0-17, for which n0 = 5 will do.

Efficiency of Algorithms

Efficiency of Algorithms

Efficiency Example 1

int find (int x[], int val) {

for (int i = 0; i < X_LENGTH; i++) {

if (x[i] == val)

return i;

}

return -1; // not found

}

Letting n be x.length:

Average iterations if found = (1+…+n)/n = (n+1)/2 = O(n)

Iterations if not found = n = O(n)

Hence this is called linear search.

Efficiency Example 2

bool all_different (

int x[], int y[]) {

for (int i = 0; i < X_LENGTH; i++) {

if (find(y, x[i]) != -1)

return false;

}

return true; // no x element found in y

}

Letting m be X_LENGTH and n be Y_LENGTH m:

Time if all different = O(m·n) = m · cost of search(n)

Efficiency Example 3

bool unique (int x[]) {

for (int i = 0; i < X_LENGTH; i++) {

for (int j = 0; j < X_LENGTH; j++ {

if (i != j && x[i] == x[j])

return false;

}

}

return true; // no duplicates in x

}

Letting n be X_LENGTH:

Time if unique = n2 iterations = O(n2)

Efficiency Example 4

bool unique (int x[]) {

for (int i = 0; i < X_LENGTH; i++) {

for (int j = i+1; j < X_LENGTH; j++ {

if (i != j && x[i] == x[j])

return false;

}

}

return true; // no duplicates in x

}

Letting n be X_LENGTH:

Time if unique = (n-1)+(n-2)+…+2+1 iterations =

n(n-1)/2 iterations = O(n2) still … only factor of 2 better

Efficiency Example 5

for (int i = 1; i < n; i *= 2) {

do something with x[i]

}

Sequence is 1, 2, 4, 8, …, @n.

Number of iterations = log2n = log n.

Computer scientists generally use base 2 for log, since that matches with number of bits, etc.

Also O(logbn) = O(log2n) since chane of base just multiples by a constant: log2n = logbn/logb2

(20 pts)

Determine the time complexity for the following method.

1 void doubleIt( int []a, int n )

2 {

3 int i = 0;

4 while ( i < n )

5 {

6 a[i] = 2 * a[i];

7 i++;

8 }

9 }

Answers:

(40 pts)

A is an ArrayList of size N. The elements of A are integers, they are in sorted order increasing from the low end of the array, and no two integers are the same. Variable x is an integer. Which of the following operations takes time that is less than O(N). That is, the operation is guaranteed to be completed in time that is O(1), O(log N), or big-oh of some function that grows more slowly than N.

1. Add an integer that is one greater than the largest element of A.

2. Find the second largest element of A.

3. Determine whether the integers in A are 1, 2,…,N exactly.

4. Determine whether the integer x is in A. Use binary search.

5. Determine whether the integer x is in A.

6. Determine whether there are any negative integers in A.

7. Insert into A the integer that is 1 less than the current smallest element.

8. Delete the integer 10x from A.

9. Insert the integer 2x into A.

10.Check whether two consecutive integers appear in A.

11.Find the sum of the elements of A.

12.Delete the middle element of A (assume N is odd).

13.Insert the integer x into A.

14.Delete the integer x from A.

15.Delete the smallest element of A.

16.Insert the integer 100 into A. Delete the smallest element of A.

ANSWER:

(20 pts)

Determine the time complexity for the following method.

Determine the time complexity for the following method.

1 boolean find2D( int [][]a, int n, int target ) {

2 int i = 0;

3 while ( i < n )

4 {

5 int j = 0;

6 while ( j < n )

7 {

8 if ( a[i][j] == target )

9 return true;

10 j++;

11 }

12 i++;

13 }

14 return false;

15 }

ANSWER:

(20 pts)

Express the following using Big-Oh notation

(a) 3n +n²+ 200

(b) 10log2n + 2n

(c) 21n + 14n + n³

Answers:

DEFINITION OF A HASH TABLE

The basis of a hash table is a hash function. A hash function is a function that takes an element of whatever data type youare storing (integer, string, etc) and outputs an integer in a certain range. This integer isused to determine the location in the table for that element. The hash table itself consists of an array whose indices are the range of the hash function.

For example, a hash table for a car database might make use of the registration plate as a key. Let’s assume the table has a size of 20. A possible hash function would be Value Mod 20,for example

(sum of numeric values of the characters) % 20

where % is the modulus operator, giving the remainder after dividing.

This would give translations like this:

SD52DFG 28+13+5+2+13+15+16 = 92: Hashcode = 12

FG02GTH 15+16+0+2+16+29+17 = 95: Hashcode = 15

DR52GHY 13+27+5+2+16+17+34 = 114: Hashcode = 14

FT52RET 15+29+5+2+27+14+29 = 121: Hashcode = 1

NN52FRT 23+23+5+2+15+27+29 = 124: Hashcode = 4

A hash table with size 20 which has had records with these keys added could look like this:

A good hash function is one that gets a fairly even distribution of the numbers in the output range, even if the input values are very poorly distributed (for example, English words are poorly distributed since they only use 26 different letters and some letters and some combinations of letter occur far more frequently than others.

Collisions

With hash tables, there always exists the possibility that two data elements will hash to the same integer value. When this happens, a collision results (two data members try to occupy the same place in the hash table array). For example:

SD52QWS 28+13+5+2+26+32+28 = 134: Hashcode = 14

The element cannot be stored as location 14 is already occupied. Methods have been devised to deal with such situations.

The loading factor in a hash table is defined as the proportion of locations which are occupied. When the loading factor is high, a hash table becomes rather inefficient.

Closed hashing

Linear probing

Linear probing is one method for dealing with collisions. If a data element hashes to a location in the table that is already occupied, the table is searched consecutively from that location until an open location is found. The new key would then be stored in location 16, as location 15 is also already occupied.

Rehashing

In rehashing, a second function is used to generate an alternative address. The function should hash to a location far from the original one.

Open hashing

In open hashing further additions which have hashed to an occupied location are stored out the main table. These locations may be stored as part of an overflow table orthey may be allocated dynamically:

Searching a hash table

Searching a hash table is easy and extremely fast: just find the hash value for the item you’re looking for, then go to that index and start searching the array until you find what you’re looking for or you hit an empty location.

Note that these examples are based on the use of linear probing to handle collisions.

Example:search for car with registration NN52FRT (table uses linear probing)

Calculate hashcode: 23+23+5+2+15+27+29 = 124: Hashcode = 4

Go to location 4.

Compare key in location 4 with target

Target was found, index = 4

Example:search for car with registration SD52QWS

Calculate hashcode: 28+13+5+2+26+32+28 = 134: Hashcode = 14

Go to location 14

Compare key in location 14 with target

Key not equal to target, go to next location

Compare key in location 15 with target

Key not equal to target, go to next location

Compare key in location 16 with target

Target was found, index = 16

Example:search for car with registration FD52HBC

Calculate hashcode: 15+13+5+2+17+11+12 = 75: Hashcode = 15

Go to location 15

Compare key in location 15 with target

Key not equal to target, go to next location

Compare key in location 16 with target

Key not equal to target, go to next location

Compare key in location 17 with target

Location 17 is empty – this is where the key would have been if it was in the table

Target not in table

Deleting from a hash table

Deleting an element from a hash table involves searching for the key, then deleting the element when it is found. The location must be marked as deleted, rather than empty, as searching will not work correctly otherwise. Locations marked deletedcan be reused.

The following segment of the table shows the result of adding SD52QWS using linear probing – the hash function of this key is 14, but the element is stored in the next empty location, 16.

If we now delete the element in location 15, we get:

We now search for key SD52QWS. If location 15 was empty, the search algorithm would stop and report that the key is not in the table.

Applications of a Hash Table

Hash tables are good in situations where you have enormous amounts of data from which you would like to quickly search and retrieve information. A few typical hash table implementations would be in the following situations:

For driver’s license record’s. With a hash table, you could quickly get information about the driver (ie. name, address, age) given the license number.

For compiler symbol tables. The compiler uses a symbol table to keep track of the user-defined symbols in a C++ program. This allows the compiler to quickly look up attributes associated with symbols (for example, variable names)

For internet search engines. For more information, click here

For telephone book databases. You could make use of a hash table implementatation to quickly look up John Smith’s telephone number.

For electronic library catalogs. Hash Table implementations allow for a fast find among the millions of materials stored in the library.

For implementing passwords for systems with multiple users. Hash Tables allow for a fast retrieval of the password which corresponds to a given username.
(30 pts) Paper and Pencil

a. For the car registration table described in the notes, with size 20, describe the sequenceof actions used to add the following elements & show the contents of the hash table:

You can find a table of the numeric values of characters below

(Numeric values of characters, returned by the Character.getNumericValue(char)method in Java):

b. Describe the sequenceof actions used to delete the following key:

TU02XYZ

Answer:

c.Describe the sequenceof actions now used to search for the following key:

YU51TRH

YU52TRH

Answer:

2. (70 pts) NetBeans 6.9.1 Java

Hash Maps

A map data structure stores (key, value)pairs. Values are retrieved by searching for the appropriate key. Maps are also sometimes called dictionariesor associative arrays.

Maps can be implemented in a number of ways. One of the most common ways is to store the (key, value) pairs in a hash table. This is called a hash map. The following code shows a simple Java implementation of a HashMapclass (parts of the code is missing, you are to complete it).

This class uses linear probing to handle collisions and includes methods to store and retrieve entries. Any kind of object can be used as a key, and any kind of object can be stored as a value.

We can’t use exactly the same hash function as we used in the examples above since we want to be able to use any kind of key, not just strings representing car registration numbers. The function used now makes use of the fact that every Java object inherits a method hashCodefrom Object.

/**

* class HashMap

*

*/

public class HashMap

{

public int CAPACITY = 20;

public Object[] keys = new Object[CAPACITY];

public Object[] values = new Object[CAPACITY];

public String[] status = new String[CAPACITY];

/**

* Initialize this HashMap object to be empty.

*/

public HashMap()

{

for (int i=0;i<CAPACITY;i++)

{

status[i] = “empty”;

keys[i] = “empty”;

values[i] = null;

}

}

/**

* Determines if this object contains no elements

*

* @return true – if this object contains no elements

*/

public boolean isEmpty()

{

int count = 0;

for (int i=0;i<CAPACITY;i++)

{

if (status[i] == “occup”)

count++;

}

if (count==0) return true;

else return false;

}

/**

* Determines the number of elements

*

* @return the number of elements */

public int size()

{

int count = 0;

for (int i=0;i<CAPACITY;i++)

{

if (status[i] == “occup”)

count++;

}

return count;

}

/**

* Puts a new key/value pair in this HashMap

* Calculates array position from hashcode, and rehashes

* if that position is occupied

*

* @param key – the key to be stored

* @param value – the value to be stored

*/

public void put(Object key, Object value)

{

int hashcode = Math.abs(key.hashCode());

*******************

System.out.println(“Hashcode calculated:” + hashcode);

if (status[hashcode]==”occup”)

{

*******************

System.out.println(“Hashcode recalculated:” +

hashcode);

}

keys[hashcode] = key;

values[hashcode] = value;

status[hashcode] = “occup”;

}

/**

* Checks whether the specifed key is present

*

* @param key – the key to be checked

* @return true – if the key is present

*/

public boolean containsKey(Object key)

{

boolean found = false;

*******************

*******************

return found;

}

/**

* Returns the value for a specified key

* Uses hashcode to select starting point for search,

* and uses linear probing to search from there

*

* @param key – the key to be found

* @return the value associated with key

*/

public Object get(Object key)

{

int hashcode = Math.abs(key.hashCode());

*******************

System.out.println(hashcode);

int attempts = 0;

if (keys[hashcode].equals(key))

return values[hashcode];

else

{

while (!keys[hashcode].equals(key) &&

status[hashcode] != “empty” && hashcode <=

CAPACITY && attempts < 10)

{

hashcode++;

if (status[hashcode] == “occup”)

{

if(keys[hashcode].equals(key))

return values[hashcode];

}

else

attempts++;

}

return null;

}

}

/** * Recursively recalculates array position to find * unoccupied position, based on linear probing method

* Checks whether allowed number of attempts has been

* exceeded.

*

* @param hashcode – the hashcode of an object

* @param attempts – the number of attempts allowed

* @return the new array position

*/

private int rehash(int hashcode, int attempts)

{

if (hashcode < CAPACITY && attempts < CAPACITY)

{

hashcode++;

if (hashcode==CAPACITY)

hashcode = 0;

System.out.println(“rehashing:” + hashcode);

if (status[hashcode] == “occup”)

{

hashcode = rehash(hashcode,attempts+1);

}

return hashcode;

}

else

return -1;

}

}

Looking at a HashMap

Create a new NetBeans project called Homework8, and add a new class HashMapusing the above completed code. Add new classes Carand CarInventoryusing the following uncompleted code:

/**

* class Car

*

*/

public class Car

{

private String registration;

private String make;

/**

* Constructor for objects of class Car

*/

public Car(String registration, String make)

{

this.registration = registration;

*******************

this.model = model;

}

}

/**

* classCarInventory

*

*/

public classCarInventory

{

public HashMap map;

/**

* Constructor for objects of classCarInventory

*/

publicCarInventory(HashMap map)

{

this.map = map;

}

/**

* Constructs a Car object and stores in the map

* using the registration number as the key

*

* @param reg the registration number

* @param make the make

* @param model the model

*/

public void storeCar(String reg, String make)

{

Car car = new Car(reg, make);

*******************

}

/**

* Retrieves a Car object from the map

* using the registration number as the key

*

* @param reg the registration number

* @return the Car object found

*/

public Car findCar(String reg)

{

Car car = (Car) map.get(reg);

return car;

}

}

Create a driver main class that creates a new instance of HashMapcalled hashmap1. Create a new instance of CarInventorycalled carInventory1and supply hashMap1 as the parameter for the constructor. You cannow use carInventory1 to store and find Carobjects in hashMap1, and also inspect the mapdirectly.

a.(20 pts)Draw the UML “compilable” Classes Diagram for theHomework8Project.

ANSWER:

b.(50 pts)Adding DataIn driver main class add the following elements then display the contents of the hash table:

Registration Make

“DF52TYU”, “Audi”

“RT02GHT”, “Volvo”

“FD52HBC”, “Saab”

“DR02TRG”, “Mini”

“TU02XYZ”, “Renault”

“YU51TRH”, “Hyundai”

Answer:

c. Finding DataIn driver main class search for the following key:

YU51TRH

Answer:

d. Updating DataAdd a method set (key, value) to your HashMap class to update the value object for a specified key. Modify your CarInventory class so that you can test this method, call it modifyCar (key, value). In driver main class call the modifyCar method of carInventory1with “YU51TRH” and “Hyundai” and “Mercedes” as parameters.

Answer:

(20 points)Paper and Pencil Merge Sort

We can describe the Merge Sort Algorithm on an array of n elements, where n is a power of 2 (i.e., 2, 4, 8, 16, 32, etc.), informally as follows:

If n = 2, return a list of the two elements sorted, lowest first.

If n > 2, recursively Merge-Sort the left (low-index) half of the array, to produce a sorted list L1, and recursively sort the right (high-index) half of the array to produce a sorted list L2.

Merge L1 and L2 to produce a single sorted list.

WRITE THE ALGORITHMforMerge Sortandshow/trace the progress of each pass of the algorithm for the following array of length 16, whose elements have values:

12, 4, 10, 1, 14, 6, 3, 11, 7, 13, 2, 15, 8, 5, 16, 9

in order, from the left.

Simulate/Show/Trace Merge Sort ALGORITHM above on this array. Which of the following lists will be L1 (not L2) in some call to Merge Sort?

Answer:

(20 points)Paper and Pencil

What does the following method do for the callprintArray (a, a.length)

for the arraya = { 54, 23 36 }?

What is wrong with this method? Fix the problem, if you can.

void printArray ( int[] values, int n )

{

if ( n< 0 )

return;

n–;

printArray ( values, n );

System.out.print (values[n] );

}

What is the fix?

Answer:

(20 points)Paper and Pencil

Lori first coded recursivebinarySearch()as follows. Where did she go wrong?

public static int binarySearch( int[] coll, int target)

{

int first = 0,

last = target.length,

mid = (first + last ) / 2;

if ( first > last ) return -1; //failure — base case

if (coll [ mid ] == target ) //success — base case

return mid;

if (coll [ mid ] < target ) { //recursive cases

last = mid – 1;

return binarySearch( coll, target );

}

else {

first = mid + 1;

return binarySearch( coll, target );

}

}

Answer:

.

(40 points)Paper and Penciland Netbeans 6.9.1or Visual Studio

IT MUST USE RECURSION!!!!!

You cannot use any other library functions thanmod% and powerpow!

Answer:

HINT:

int 11 % 10 is1 —> last bit value

Thus, you have obtained the last bit value to which you will applypow(2, weight) and subtotal it to the decimal value

int11 / 10 is 1 —> next binary number that you pass to the recursive call

(10 points)Paper and Pencil Selection Sort

WRITE THE ALGORITHMforSelection Sortandshow/trace the progress of each pass of the algorithm for the following array:

{17, 8, 11, 9, 21, 32, 5, 2}

Show/Trace the first 3 passes of the Selection Sort Algorithm above.

How many comparisons are performed?

How many exchanges?

Answer:

(10 points)Paper and PencilInsertion Sort

WRITE THE ALGORITHMforInsertion Sortandshow/trace the progress of each pass of the algorithm for the following array:

{17, 8, 11, 9, 21, 32, 5, 2}

Show/Trace the first 3 passes of the Insertion Sort Algorithm above.

How many comparisons are performed?

How many exchanges?

Answer:

(40 points)Paper and Penciland Netbeansor Visual Studio

Modify the Selection Sort Algorithm (GIVEN in 1.) so it sorts integer array

{17, 8, 11, 9, 21, 32, 5, 2} in descending order.

IF YOU WILL IMPLEMENT IT, then the PROJECT SCREENSHOT SHOWING the CODE in the SOURCE WINDOW, the OUTPUT WINDOW and PROJECT FILES can be turned in as a HARDCOPY instead of by hand rewriting it.

Answer:

(10 points) Paper and Pencil

(a) Use the sequential search to find a target value in an array of 10000 items.

(i)What is the fewest number of comparisons the search will require?

(ii)What is the maximum number of comparisons the search will require?

(iii)What is the expected number of comparisons for the search?

(b) Use the binary search to find a target value in an array of 10000 items.

(i)What is the fewest number of comparisons the search will take?

(ii)What is the maximum number of comparisons for the search?

Answer:

(20 points)Paper and PencilQuick Sort

WRITE THE ALGORITHMforQuick Sort (pivot is the middle element)andshow/tracethe progress of each pass of the algorithm for the following array:

{17, 8, 11, 9, 21, 32, 5, 2}

Show/Trace the Quick Sort Algorithm above.

Answer:

Binary Search

The binary search is the standard method for searching through a sorted array. It is much more efficient than a linear search, where we pass through the array elements in turn until the target is found. It does require that the elements be in order.

The binary search repeatedly divides the array in two, each time restricting the search to the half that should contain the target element.

In this example, we search for the integer 5in the 10-element array below:

Loop 1 – Look at whole array

Low index = 0, high index = 9

Choose element with index (0+9)/2 = 4

Compare value (10) to target

10 is greater than 5, so the target must be in the lower half of the array

Set high index = (4-1) = 3

Loop 2

Low index = 0, high index = 3

Choose element with index (0+3)/2 = 1

Compare value (5) to target

5 is equal to target

Target was found, index = 1

Efficiency

The maximum number of comparisons required to find a target in an array of n elements is (the number of times that ncan be divided in two) + 1.

This means that to search an array of 1024 elements would take at most 10comparisons using a binary search, but could take up to 1024comparisons using alinear search.

Binary Data Structures

A linked list structure is not efficient when searching for a specific item as the node can only be accessed sequentially.

The binary search algorithmsuggests a data structure which can be implemented using dynamic storage and allows searching to be done efficiently. Consider the order in which the elements of the following array would be accessed in a binary search:

The first step would be to divide the array in two and compare the target with element 6

(Jim). Depending on the result of the comparison, the next element to be checked would be either 2 (Dot) or 10 (Ron). If it is Dot, then we would next check either 0 (Amy) or 4

(Guy), and so on.

We can describe the possible sequence of comparisons in a diagram:

For example, to search for the target Jonin the array, we would have to compare the target with the elements Jim, Ron, Kayand Jon(try it for yourself to check this).

This diagram looks a little bit like a family tree, and suggests that a treeis a suitable data structure. Tree structures are commonly used in computer science. The characteristic features of a tree are that each element may have several successors (or “children”), and every element except the topmost one has a unique predecessor (or “parent”). Tree structures are hierarchicalrather than linear, (whereas a List is a linear structure).

Examples of tree structures include computer file systems and the inheritance structure for Java & C++ classes.

Binary Trees and Binary Search Trees

Our diagram is a special kind of tree, called a binary search tree, which is ideal for storing data for efficient searching. The binary search tree is a hierarchical structure in which data access is similar to a binary search algorithm.

A binary search tree is itself a special kind of binary tree. A binary tree is a tree which is either empty or consists of a node called the root, together with two children called the left subtreeand the right subtreeof the root. Each of these children is itself a binary tree.

A binary search tree satisfies the following additional conditions:

•Each element has a key value which is used to order the elements

•The keys of all the elements (if there are any) in the left subtree of the root precede the key in the root

•The key in the root precedes all keys (if any) in the right subtree

•The left and right subtrees of the root are again search trees.

Look at the diagram above and check that the element Jimis a binary search tree.

Operations

The main primitive operations of a binary search tree are:

Addadds a new node

Getretrieves a specified node

Removeremoves a node

Traversalmoves through the structure

Additional primitives can be defined:

IsEmptyreports whether the tree empty

IsFullreports whether the tree is full

Initializecreates/initializes the tree

Destroydeletes the contents of the tree (may be implemented by re-initializing the tree)

Storing a binary search tree in a dynamic data structure

Each node contains data AND references to the left and right subtrees. An empty subtree is represented by a NULL reference. Each subtree is itself a binary search tree.

For some purposes it is useful to include a reference to the parent tree, but for simplicity

we will not do this here.

Traversal methods

Traversal is the facility to move through a structure visiting each of the nodes once. With a binary tree, there are three actions associated with a traversal:

V:visit the node (for example, to output the data stored in that node)

L:traverse the left subtree

R:traverse the right subtree

There are three commonly used ways of organizing the traversal

VLRPreOrder (i.e. visit the node then traverse the subtrees)

LVRInOrder (traverse the left subtree, visit the node then traverse the right subtree)

LRVPostOrder (traverse the subtrees then visit the node)

Example: PreOrder

Step 1. Root = Jim

Display Jimthen traverse its left subtree (root = Dot) and then its right subtree (root =

Ron)

Display:Jim

Step 2. Root = Dot (Jim.LeftSubTree)

Display Dotthen traverse its left subtree (root = Amy) and then its right subtree (root =

Guy)

Display:Jim Dot

Step 3. Root = Amy (Dot.LeftSubTree)

Display Amythen traverse its left subtree (root = NULL) and then its right subtree (root =

Ann)

Display:Jim Dot Amy

Since the left subtree of Amy is empty we then move onto the right subtree.

Step 4. Root = Ann (Amy.RightSubTree)

Display Annthen traverse its left subtree (root = NULL) and then its right subtree (root =

NULL)

Display:Jim Dot Amy Ann

Since both of Ann’s subtrees are empty we have finished traversing the tree with Root =

Ann.

This completes the traversal of the right subtree of Amyand thus completes Amy,

The tree with root Amy is the left subtree of Dot, so we now continue with the right

subtree of Dot(Root = Guy).

Step 5. Root = Guy (Dot.RightSubTree)

Display Guythen traverse its left subtree (root = Eva) and then its right subtree (root =

Jan)

Display:Jim Dot Amy Ann Guy

Remaining steps

We display Eva and Jan and this completes the right subtree of Dot, and thus the left

subtree of Jim.

Display:Jim Dot Amy Ann Guy Eva Jan

We now traverse the right subtree of Jim in a similar way, giving a final output of

Display:Jim Dot Amy Ann Guy Eva Jan Ron Kay Jon Kim Tim Roy Tom

(20 pts) Tree Paper and Pencil

a. Write down the output for InOrdertraversal of the example tree.

What do you notice about the final output?

Answer:

b. Write down the output for PostOrdertraversal of the example tree.

What do you notice about the final output?

Answer:

(30 pts) Paper and Pencil

Recursion and the binary search tree algorithms

The algorithms used to implement a binary tree can make use of recursion. A recursive operation can call itself. This can result in a lot of work being done by very little code.

For example, the PreOrder traversal above uses the following algorithm:

PreOrder(Root)

If Root is not NULL

Display Root.DataItem

Call PreOrder(Root.LeftSubTree)

Call PreOrder(Root.RightSubTree)

End If

Other operations can also make use of recursion:

Get

Searches for a specified target. The target is a key value, and the operation will return the data item with that key.

e.g.Get(Root, Guy)

Algorithm:

Get(Root, Target)

If Root is not NULL

If Target = Root.DataItem.Key

Return Root.DataItem

Else If Target < Root.DataItem.Key

Return Get(Root.LeftSubTree)

Else

Return Get(Root.RightSubTree)

EndIf

Else

Return NULL

End If

Example: Target = Guy

The operation must start at the root Jim and then go through the following stages:

Guy < Jimgo to left subtree of Jim (root is Dot)

Guy > Dotgo to right subtree of Dot (root is Guy)

Guy = roottarget found, return data item of node Guy

The target data item is passed by return statements back to the original operation call, as shown in the diagram below:

Add

Adds a new node to the tree.

e.g.Add(Root, Meg)

The Add operation is similar to the Get operation in that you have to recursively descend the tree until you find the appropriate place to add the new node. For example, if you want to add a new node with key Meg, the operation must start at the root Jim and then go through the following stages:

Meg> Jimgo to right subtree of Jim

Meg <Rongo to left subtree of Ron

Meg>Kaygo to right subtree of Kay

Meg>Kimgo to right subtree of Kimwhich is NULL, therefore add Meg

as a right child of Kim

Remove

Removes a node from the tree

e.g.Remove(Root, Guy)

The remove operation can be rather involved, as it may be necessary to rearrange nodes so that the remaining structure is still a valid binary search tree. For example, if

Guyis removed, a possible new structure would be:

Note that:

•Evais now the right subtree of Dot, rather than Guy

•Janis now the right subtree of Eva,rather than Guy

Removing a node with empty subtrees, known as a leaf node(e.g. Meg) is straightforward as no rearrangement is required.

Algorithms to remove a node and change the attachments of other nodes as required are quite complex, and it can be useful to have a parentreference in each node.

a. Describe the steps required to search for (use the original tree!)

(1) Roy (2) Ian

Answer:

b. Describe the steps required to add (use the original tree!)

(1) Abi (2) Ken (3) Rik

Answer:

c. Draw a diagram of a possible tree structure after removing: (use the original tree!)

(1) Ann (2) Ron

Answer:

(40 pts) NetBeans 6.9.1 Java

Binary TreeImplementation

a.(10 pts)Draw the UML “compilable” ClassesDiagram for theHomework11 Project.

ANSWER:

b.(30 pts)

Create a new project called Homework11.

The following code shows a simple Java implementation of a Node class Node.javaand the BinaryTreeclass BinaryTree.java (parts of the code is missing, you are to complete it). ===========.

For simplicity, this version stores Strings rather than Objects.

Node.java

public class Node {

protected String DataItem;

protected Node LeftSubTree;

protected Node RightSubTree;

public Node ( ){

this.DataItem = “”;

this.LeftSubTree = null;

this.RightSubTree = null;

}

public Node ( String data){

this.DataItem = data;

this.LeftSubTree = null;

this.RightSubTree = null;

}

}

BinaryTree.java

public class BinaryTree {

private Node Root;

/**

* Constructor for objects of class BinaryTree

*/

public BinaryTree() {

Root = null;

}

public BinaryTree(String rootData) {

Root = new Node (rootData);

}

/**

* sets all Root entry to null

*

**/

public void destroy() {

Root = null;

}

/**

* checks whether BinaryTree is empty

*/

public boolean isEmpty() {

return (Root == null);

}

/**

* get an item of the BinaryTree

*/

public String Get(String o) {

String str = get (Root, o);

return (str);

}

public String get(Node Root, String o) {

if (!(Root == null))

{

if (o.equals(Root.DataItem)) {

return (Root.DataItem);

} else if (o.compareTo(Root.DataItem) < 0) {

return (get(Root.LeftSubTree, o));

} else {

return (get(Root.RightSubTree, o));

}

} else {

return null;

}

}

/**

* add an item to the BinaryTree

*/

public void Add(String o) {

Node parentNode;

Node newNode = new Node (o);

if (Root == null){

Root = newNode;

}

else{

parentNode = Root;

add(parentNode, newNode, o);

}

}

/**

* add an item to the BinaryTree

*/

public void add(Node LocalRoot, Node newNode, String o)

{

=======

……

=======

}

/**

* PreOrder Traversal of the BinaryTree

*/

public void PreOrder() {

preorder (Root);

}

public void preorder(Node Root) {

if (!(Root == null))

{

System.out.println(“Visited” + Root.DataItem);

preorder(Root.LeftSubTree);

preorder(Root.RightSubTree);

}

else

System.out.println(“Visited none: Tree is EMPTY”);

}

}

Using a BinaryTree

Data structure classes are intended to be used in programs as utility classes which contain the data the program needs to work with. To use the BinaryTreeclass, you need to know how to write code to call the BianryTreeoperations, for example to add data to the BinaryTree.

Controller Class:The following classTreeTester.java shows how to use a BinaryTreeto hold stringobjects. Calls to BinaryTreeoperations are shown in bold.

TreeTester.java.

public class TreeTester {

private BinaryTree tree;

private Node root;

public TreeTester(BinaryTree tree) {

this.tree = tree;

}

/**

* check to see if tree is empty

*/

public void isEmptyTree() {

if (tree.isEmpty())

System.out.println(“Tree is EMPTY?”);

else

System.out.println(“Tree is NOT EMPTY?”);

}

/**

* add item to tree

*/

public void populateTree(String str) {

System.out.println(“Control class: Populate the Binary Tree”);

tree.Add(str);

System.out.println(“Added new string: ” + str);

}

/**

* Preorder traversal of the tree

*/

public void traverseTreeInPreOrder() {

System.out.println(“Control class: PreOrder traversal of the Binary Tree”);

System.out.println(“The PreOrder Travelsal is:”);

tree.PreOrder();

}

/**

* search item in the tree

*/

public void searchInBinaryTree(String str) {

System.out.println(“Control class: Searching the Binary Tree”);

System.out.println(“Found string ” + tree.Get(str));

}

}

Create aDriver.java class (it contains main).

1. Create an instance of BinaryTree called bt.
2. Create a new instance of Controller Class called TreeTester called treetest with the BinaryTree bt created above.
3. Call the isEmptyTree method of your TreeTester. What was the result?
4. Call the populateTree method of your TreeTester with:

Jim, Dot, Amy, Ann, Guy, Eva, Jan, Ron, Kay, Jon, Kim, Tim, Roy, Tom

1. Call the traverseTreeInPreOrder method of your TreeTester to get the preorder traversal of your tree.

1. Call the searchInBinaryTree method of your TreeTester to find “Kim”. Trace the code and observe the nodes traversed to get to “Kim”.

ANSWER:

(10 pts) Paper and Pencil

For each tree, indicate whether it is a heap (maximum or minimum).

answer

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.