What is the load factor of the hash table

Assignment Help Data Structure & Algorithms
Reference no: EM131226701

Question 1:

Consider the sequence of keys 1205, 3248, 1330, 1844, 2042, 2861, 1475, 3582, 2492, 4125 and 2503 are inserted into an empty hash table. The hash function is h(x) = x mod 11. For each of the following four scenarios, per the specified operations:

a) When collisions are handled by separate chaining.

(i) Draw the hash table after all the keys have been inserted.

(ii) Find the average number of key comparisons in a successful search in the hash table. You can assume that a search for each of the nine keys is equally likely.

(iii) Find the largest number of key comparison in a successful search in the hash table.

(iv) What is the load factor of the hash table?

b) When collisions are handled by linear probing.

(i) Draw the hash table after all the keys have been inserted.

(ii) Find the average number of key comparisons in a successful search in the hash table. You can assume that a search for each of the nine keys is equally likely.

(iii) Find the largest number of key comparison in a successful search in the hash table.

(iv) What is the load factor of the hash table?

c) When collisions are handled by quadratic probing using a quadratic probe function f'(x, i) = (h(x) + 1.5i +1.5i2) mod 11, where i = 1, 2, 3, ... and h(x) = x mod 11.

(i) Draw the hash table after all the keys have been inserted.

(ii) Find the aver-age number of key comparisons in a successful search in the hash table. You can assume that a search for each of the nine keys is equally likely.

(iii) Find the largest number of key comparison in a successful search in the hash table.

(iv) What is the load factor of the hash table?

d) When collisions are handled by double hashing using a double hash function h'(x, i) = (h(x) + i x ((2x - 1) mod 7) + 1) mod 11, where i = 0, 1, 2, 3, .... and h(x) = x mod 11.

(i) Draw the hash table after all the keys have been inserted.

(ii) Find the average number of key comparisons in a successful search in the hash table. You can assume that a search for each of the nine keys is equally likely.

(iii) Find the largest number of key comparison in a successful search in the hash table.

(iv) What is the load factor of the hash table?

Question 2

a) The operation convertToMaxHeap(h) converts a minimum heap into a maximum heap. Design an algorithm of convertToMaxHeap that runs in O(n lgn) time. Show that your algorithm runs in o(n lg n).

b) Given the following minimum heap, illustrate the process of converting it into a maximum heap using your algorithm described in (a). You need to show the intermediate processes. Please show every steps you made clearly.

1546_Figure.jpg

Question 3

The INORDER traversal output of a binary tree is U, N, I, V, E, R, 5, I, T, Y and the POSTORDER traversal output of the same tree is I, N, U, E, R, It Y, T, 5, V. Construct the tree and determine the output of the PREORDER traversal output.

Question 4

a) One main difference between a binary search tree (BST) and an AVL (Adelson-Velski and Landis) tree is that an AVL tree has a balance condition, that is, for every node in the AVL tree, the height of the left and right subtrees differ by at most 1. Starting with an empty BST and AVL tree, insert elements into the two trees with the following keys:

0) 7, 11, 12, 18, 21
(ii) 20, 30, 80, 40, 10, 60, 50, 70

b) Comment on the worst-case running time complexity of the two trees structure.

c) A list of student's names is maintained in an AVL tree T. Design an algorithm for performing the operation findAll to return all the names in the AVL tree that match the searched name. Note that there is a posibility that same names exist in the tree. In the case that the same name exists, the name is added to the left subtree.

d) What is asymptotic running time complexity of your algorithm from part c?

Question 5:

a) Starting with an empty 2-4 tree, construct a 2-4 tree with the following keys. Show the major working steps.

5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1

b) What is the running time complexity to process a 2-4 tree with n keys? Show or explain.

Reference no: EM131226701

Questions Cloud

Evaluating critical the originality of your ideas : If you don't identify a problem, you don't have a paper that meets the learning outcome. How you address the problem or challenge's causes, implications and possible solutions, will form the basis of your critical thinking grade. The recommendatio..
Provide information regarding stress management : There are many sites available on the web that provide information regarding stress management. Explore the internet and share with us any sites that offered helpful hints regarding stress management that you were able to find.
Solve the differential equation using euler method : Particle-Laden Flows ME 4863-01 Homework. Create a spreadsheet to solve the differential equation using Euler's method. Assume CD = 24/Rer + 0.44. Use the spreadsheet to examine the particle motion for the following conditions
Promotions and transfers of employees : Fiji Airways has embarked on promotions and transfers of employees within the company to mitigate its potential labour shortage. Discuss the advantages offilling positions with current employees rather than recruiting from externalsources. Illustr..
What is the load factor of the hash table : Find the average number of key comparisons in a successful search in the hash table. You can assume that a search for each of the nine keys is equally likely - What is the load factor of the hash table?
Describe the ethical model being used by the company : Describe the motivational practices used by the organization to promote better strategy execution. Include some illustrative examples in your response.
Improve employees performance : Question: Besides giving employees feedback, what other steps a manager can take to improve employees' performance? Discuss your answer.
Compare cron, anacron, and systemd timer units : An important service provided by any system is the ability to run a process on a predetermined schedule without human intervention. The “automation” of tasks can reduce the workload of the system administrator significantly. Unfortunately Linux curre..
What is the cost of equity capital for vwx : Explain homemade leverage and why it matters. What is the cost of equity capital for VWX? Using the M&M Proposition I with taxes, calculate the value of the firm at each debt level.

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  System analystis you are required to analyse the

you are required to analyse the effectiveness of the qantas online air ticketing system. to do this you are required to

  Normalized relations for a database

Suppose that a information communications network links a computer at corporate headquarters with a computer in each retail outlet. The chain includes fifty stores with an average of 75 workers per store.

  Ambiguity in proposed algorithm-in representation algorithm

Describe distinction between the ambiguity in proposed algorithm and ambiguity in representation of the algorithm.

  Ease of changes in the processing algorithms

Ease of changes in the processing algorithms: For example, line shifting can be performed on each line as it is read from the input device, on all the lines after they have been read, or on demand when the alphabetization requires a new set of shi..

  Encryption algorithm that does not use the alphabet

Research and submit an encryption algorithm that does not use the alphabet or numbers in the encrypted text.  For instance, if you take a sentence like "I love this class"

  Write operations for binary file operations

C++: templates, char arrays and their null terminated representation, sizeof operator, seekp, seekg, read and write operations for binary file operations, eof() function, proper opening and closing of files with different arguments, code to proces..

  Discuss the advantages of declaring and instantiating data

Discuss the advantages of declaring and instantiating data in multidimensional arrays. Show an example that you can use in one of your programs or any program.

  Give the steps for to build priority queue after deque

Give the steps for to build priority queue after deque

  Currency conversion developmentapplication-level

currency conversion developmentapplication-level requirements list1. the program will prompt the user for data input of

  Find the minimum cost path from a designated node

Find the Minimum Cost Path from a designated start node to a designated destination node in a graph.

  Using pseudocode, design an algorithm

BuzzButtons is a novelty item company manufacturing personalized lapel buttons. The owner is promoting his buttons by offering them at 99 cents each. He wants you to design a program asking the user for his or her name for the button, an e-mail addre..

  Give a recursive definition of a singly linked list

Give a C++ code fragment that, given an×n matrix M of type float, replaces M with its transpose. Try to do this without the use of a temporary matrix.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd