Solution to Homework 3, CSE444, Fall 2003

1.

a.     Heap

 Block 0 Block 1 Block 2 Block 3 2 NULL NULL 2 1 0 NULL NULL 40 10 30 Free 35 20 39 Free 25 28 Free Free

b.     Clustered table

 Block 0 Block 1 Block 2 Block 3 2 NULL NULL 3 3 0 1 2 40 10 30 28 Free 20 35 Free Free 25 39 Free

2.     Both “best fit” and “first fit” need a new block only when all blocks are full.  So none saves disk space over the other. Deletions and Insertions are equally efficient in both policies since they require access to 1 block in both policies to remove a record or insert a new one.

Updates of variable-length fields are more efficient with “best fit”. This policy ensures each allocated block contains the maximum possible free space on average, thus allowing the records grow and shrink flexibly. As a counterpart, “first-fit” fills up the blocks as fast as possible making changes to the record length much more difficult. Details depend on the specific implementation, but it would inevitably involve much more allocations due insufficient space in a block to handle update and as a consequence more swapping records between blocks.

3.

a.     No Tombstones

·          2 insertions/ 1 deletion per day

(2*(100+2) - (100+2)) bytes/days = 102 bytes/days

·          4096 bytes / 102 bytes/days = ~40 days

b.     With Tombstones

·          2 insertions/ 1 deletion per day

(2*(100+2) - (100)) bytes/days = 104 bytes/days

·          4096 bytes / 104 bytes/days = ~39 days

4.

a.     b.

5.

a.     Histogram of bucket sizes using Mr. Frumble’s hash function

b.     Expected running time is 1’000’000 = 100*100^2.

Running time using Mr. Frumble’s hash function is 4,816,030 = 02 + … + 02 + 12 + 42 + 102 + … + 6602 + 6702 + 6602 + … + 102 + 42 + 12 + 02 + …

It is 4.81603 times slower than expected.

c.

i.      New hash function

unsigned int NewHash(const char *s, unsigned int n)

{

unsigned int res = 0;

s++;

int x = atoi(s);

res = x % n;

return res;

}

ii.      New running time is 1’000’000 = 1002+1002+…+1002

iii.      Histogram of bucket sizes using new hash function