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 
and 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
Get Free Quote! 408 Experts Online | ||
