Draw the closed hash table

Assignment Help Data Structure & Algorithms
Reference no: EM131860367

Homework

1. A closed hash table with length 13 is used to store positive integers, using linear probing to resolve collisions. The hash function value for an integer N is simply the remainder N % 13. Suppose that the following numbers are inserted into the table in the order shown, starting with an empty table:

131 32 818 295 88 204 55 321 419 492

a) Draw the closed hash table, showing the contents of the hash table after this sequence of insertions.

b) Now, explain carefully how to search the table to check if the number 321 is present. (What steps are followed, and why?) Do the same for the number 16.

2. Now, suppose that an open hash table is used instead. The size of the table is still 13, and the same hash function is used. Lists are implemented as simple linked lists, using the following class to represent the list nodes:

class ListNode {

int item;

ListNode next;

}

a) Draw the open hash table after the same sequence of insertions as in the previous problem.

b) The hash table is declared in Java as ListNode[] table = new ListNode[13], and of course initially all the values in the array are null. Write a Java method that prints out all of the integers in the open hash table, using System.out.println.

c) Write a Java method for deleting a number N from the open hash table, if it is present.

If N is not in the table, nothing should be done. (Use the hash function to find out where N should be!)

3. Next, we turn to heaps. For this problem, we consider a heap to be a full binary tree, and we ignore the possibility of storing it in an array. Suppose we start with the following heap of integers:

379_figure.png

a) Redraw the heap to show its state after inserting 50.

b) Now, redraw it again to show its state after inserting 18 (after the previous insertion).

c) Now, redraw it again to show its state after inserting 35 (after the previous insertions).

d) Now, redraw it again to show its state after inserting 87 (after the previous insertions).

e) Finally, redraw the resulting heap to show the effect of deleting the maximum element, and explain the process that was used to delete that element. (What steps are followed, and why?)

4. We have seen how dynamic arrays enable arrays to grow while still achieving constant time amortized performance. This problem concerns extending dynamic arrays to let them both grow and shrink as items are added and removed over time.

a) Consider an "underflow" strategy that cuts the array size in half whenever the number of items falls below half of the length of the array. Give an example sequence of insertions and deletions where this strategy gives a bad amortized cost.

b) Then give a better underflow strategy than the one suggested in part a). Your strategy should be one that achieves constant amortized cost per deletion.

Reference no: EM131860367

Questions Cloud

Probability that none of them were committed with a weapon : If three murders are selected at random, find the probability that none of them were committed with a weapon.
What sample size should be used : A statistics practitioner would like to estimate a population mean to within 40 units with 99% confidence given that the population standard deviation is 160.
Describe a specific example from the story : Describe a specific example from the story to illustrate your argument. Discuss how this perspective affects your reading and interpretation of the story.
Defective rate on the assembly line : Suppose that in the random sample the defective rate is 5%. What does that suggest about the defective rate on the assembly line?
Draw the closed hash table : CPSC 327 Homework. Draw the closed hash table, showing the contents of the hash table after this sequence of insertions
Determining the warranty of refrigerators : The expected life of refrigerators produced by the Keep It Cool Company are normally distributed with a mean of 240 months
Suspicious of steroid use among olympic athletes : In 2008, the Gallup poll asked people whether they were suspicious of steroid use among Olympic athletes. Thirty-five percent of respondents
Find one violation with code section : Assume you complete the tax return. Find one violation with Code Section 6694 or the related Treasury regulations - Find one thing wrong about this
Calculate a z statistic for a sample of 30 people : The population mean is 160, and the standard deviation is 100. Show your work for each question.

Reviews

len1860367

2/12/2018 1:57:56 AM

This written homework assignment is due next Wednesday, February 14. Remember that you can discuss the homework with other people, but you should write up your own solutions. Consider an “underflow” strategy that cuts the array size in half whenever the number of items falls below half of the length of the array. Give an example sequence of insertions and deletions where this strategy gives a bad amortized cost.

Write a Review

Data Structure & Algorithms Questions & Answers

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  Write the selection sort algorithm

Write the selection sort algorithm

  Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

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