[Solved] METCS526 Module4

Problem 1 . Consider the following heap, which shows integer keys in the nodes:

Show the resulting tree if you add an entry with key = 27 to the above tree? You need to describe, step by step, how the resulting tree is generated.

Problem 2 . Consider the following heap, which shows integer keys in the nodes:

Suppose that you execute the removeMin( ) operation on the above tree. Show the resulting tree. You need to describe, step by step, how the resulting tree is generated.

Problem 3 This problem is about the chaining method we discussed in the class. Consider a hash table of size N = 11. Suppose that you insert the following sequence of keys to an initially empty hash table. Show, step by step, the content of the hash table.

Sequence of keys to be inserted: <5, 8, 44, 23, 30, 34, 52, 32, 15, 16>

Problem 4. This problem is about linear probing method we discussed in the class. Consider a hash table of size N = 11. Suppose that you insert the following sequence of keys to an initially empty hash table. Show, step by step, the content of the hash table.

Sequence of keys to be inserted: <5, 8, 44, 23, 30, 34, 52, 32, 15, 16>

Problem 5 Suppose that your hash function resolves collisions using open addressing with double hashing, which we discussed in the class. The double hashing method uses two hash functions h and h.

Assume that the table size N = 13, h(k) = k mod 13, h(k) = 1 + (k mod 11), and the current content of the hash table is:

0 1 2 3 4 5 6 7 8 9 10 11 12

28

98

59

22

43

51

If you insert k = 15 to this hash table, where will it be placed in the hash table? You must describe, step by step, how the location of the key is determined.

Problem 6). The goal of this problem is to give students an opportunity to observe differences among three data structures in Java Javas HashMap, ArrayList, LinkedList in terms of insertion time and search time.

Students are required to write a program that implements the following pseudocode:

create a HashMap instance myMap create an ArrayList instance myArrayList create a LinkedList instance myLinkedList

Repeat the following 10 times and calculate average total insertion time and average total search time for each data structure

generate 100,000 random integers in the range [1, 1,000,000] and store them in the array of integers insertKeys[ ]

// begin with empty myHap, myArrayList, and myLinkedList each time

// Insert keys one at a time but measure only the total time (not individual insert // time)

// Use put method for HashMap

// Use add method for ArrayList and LinkedList

insert all keys in insertKeys [ ] into myMap and measure the total insert time insert all keys in insertKeys [ ] into myArrayList and measure the total insert time insert all keys in insertKeys [ ] into myLinkedList and measure the total insert time

generate 100,000 random integers in the range [1, 2,000,000] and store them in the array searchKeys[ ].

// Search keys one at a time but measure only total time (not individual search // time)

// Use containsKey method for HashMap

// Use contains method for ArrayList and Linked List

search myMap for all keys in searchKeys[ ] and measure the total search time search myArrayList for all keys in searchKeys[ ] and measure the total search time search myLinkedList for all keys in searchKeys[ ] and measure the total search time

Print your output on the screen using the following format:

Number of keys = 100000

HashMap average total insert time = xxxxx

ArrayList average total insert time = xxxxx

LinkedList average total insert time = xxxxx

HashMap average total search time = xxxxx

ArrayList average total search time = xxxxx

LinkedList average total search time = xxxxx

You can generate n random integers between 1 and N in the following way:

Random r = new Random(System.currentTimeMillis() );

for i = 0 to n 1

a[i] = r.nextInt(N) + 1

When you generate random numbers, it is a good practice to reset the seed. When you first create an instance of the Random class, you can pass a seed as an argument, as shown below:

Random r = new Random(System.currentTimeMillis());

You can pass any long integer as an argument. The above example uses the current time as a seed.

Later, when you want to generate another sequence of random numbers using the same Random instance, you can reset the seed as follows:

r.setSeed(System.currentTimeMillis());

You can also use the Math.random( ) method. Refer to a Java tutorial or reference manual on how to use this method.

We cannot accurately measure the execution time of a code segment. However, we can estimate it by measuring an elapsed time, as shown below:

long startTime, endTime, elapsedTime; startTime = System.currentTimeMillis();

// code segment

endTime = System.currentTimeMillis(); elapsedTime = endTime startTime;

We can use the elapsedTime as an estimate of the execution time of the code segment.

Name the program Hw4_P6.java.

Deliverable

You need to submit the following files:

• P1_P5pdf: This file must include:
• Answers to problems 1 through 5.
• Discussion/observation of Problem 6: This part must include what you observed and learned from this experiment and it must be substantive.
• java
• Other files, if any.

Combine all files into a single archive file and name it LastName_FirstName_hw4.EXT, where EXT is an appropriate archive file extension, such as zip or rar.

Grading