Use the following hash table and hashing function f(key) = key%15 to hash the keys. Calculate average displacement and average number of comparisons to locate every key.

computer science

Description

1. Assuming a dataset of size N, complete the following table:

 

 

Algorithm

Lower bound

Ω ( ? )

Upper bound

O ( ? )

Search

 

Sequential search

 

 

 

Binary search

 

 

 

Hashed search

 

 

 

Binary Search Tree

 

 

 

B-Tree

 

 

Sort

 

Insertion Sort

 

 

 

Quick Sort

 

 

 

Merge Sort

 

 

 


2.  Given the following keys:

 

{ 27, 35, 30, 48, 57, 7, 49, 59, 22, 81, 73, 95, 18, 86, 43}

 

Use the following hash table and hashing function f(key) = key%15 to hash the keys.

Calculate average displacement and average number of comparisons to locate every key.

 

 

Address

 

Key

 

Displacement

 

# Comparisons

0

 

 

 

1

 

 

 

2

 

 

 

3

 

 

 

4

 

 

 

5

 

 

 

6

 

 

 

7

 

 

 

8

 

 

 

9

 

 

 

10

 

 

 

11

 

 

 

12

 

 

 

13

 

 

 

14

 

 

 

 

 

Average

Displacement:

 

Average # Comparisons:

 

 

 

 

 


3.  Given the following dataset, a hashed table divided into buckets of size 3, map the keys to buckets and calculate the average displacement and average number of comparisons:

 

    {27, 35, 30, 48, 57, 7, 49, 59, 22, 81, 73, 95, 18, 86, 43}

 

Use the following hash table and hashing function f(key) = key%5 to hash the keys.

Calculate average displacement and average number of comparisons to locate every key.

 

 

Address

 

Key

 

Displacement

 

# Comparisons

 

0

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

 

 

4

 

 

 

 

 

 

 

 

 

 

 

Average

Displacement:

 

Average # Comparisons:

 

 

 

 

 

 

 


4. Complete the following “paint” method to draw the following shapes on the screen, leave 20 pixels between the borders of the shape Text Box: Title bar (40 pixelsand the visible section of the frame:

 


public void paint(Graphics g)

{

Graphics2D g2 = (Graphics2D) g;

            int ww = (int)this.getWidth();

            int wh = (int)this.getHeight() -40;

 

 

 

 

 

 

}

 


5. Given the following transformation matrix for translation, rotation and scaling, construct matrices to: translate, rotate and scale a shape given following parameters.

Scaling(Sx,Sy)


Related Questions in computer science category

Get Higher Grades Now
Tutors Online