Pseudocode Solutions and Hash Function Comments for Data Structures Homework

Data Structures Homework #9 Solution By Carlos

Q1 exercise 18.12 Pseudocode for add, remove and getItem

The pseudocode -- add Add(item:ItemType) : void throw hashtableFullException i = the array index that the address calculator gives you by given item if(table[i] is empty){ put item into table[i] return } else { set originI as i add 1 to i

The pseudocode -- add while(table[i] is occupied and i not equals originI){ if(table[i] is empty){ put item into table[i] return } add 1 to i if(i reaches the size of table) set i as 0 } throw hashtableFullException }

The pseudocode remove(1) remove(searchKey:keyType) : boolean i = the array index that the address calculator gives you for an item whose search key equals searchKey if(table[i].getKey() == searchkey){ remove the item from table[i] return true } else { set originI as i add 1 to i

The pseudocode remove(2) while(table[i] is occupied and i not equals originI){ if(table[i].getKey() == searchkey){ remove the item from table[i] return true } add 1 to i if(i reaches the size of table) set i as 0 } return false }

The pseudocode getItem(1) getItem(searchKey:keyType) : ItemType throw NotFoundException i = the array index that the address calculator gives you for an item whose search key equals searchKey if(table[i].getKey() == searchkey) return table[i] else { set originI as i add 1 to i

The pseudocode getItem(2) while(table[i] is occupied and i not equals originI){ if(table[i].getKey() == searchkey) return table[i] add 1 to i if(i reaches the size of table) set i as 0 } return NotFoundException }

Q2 exercise 18.14 Comments for the hash function

This function is easy to compute but the distribution will not be evenly distribution. The probability of locating around medium is larger to others. If tow keys sums of positions in alphabet of its letters are the same, they will be hashed to the same location. Example : same letters but different order(anagram).

This hash function is easy to compute. However, the distribution will have longer tail of its right side than its left side. There is no way to find a pattern which can be located to the same location by this hash function .

Q3 exercise 19.1 Draw a 2-3 tree

30 10 100 10 10 100 30 80 30 10 50 100 10 80 100

50 80 80 30 50 100 100 30 60 50 80 50 80 30 40 60 70 100 30 60 70 100

50 70 50 70 30 40 60 100 30 40 60 90 100 50 70 30 20 60 90 100 40

50 70 20 40 60 90 100 50 90 20 40 60 100

Q4 exercise 19.3 Range query of 2-3 tree

The pseudocode(1) rangeQuery(23tree:TwoTreeTree, lb:ItemType, ub:ItemType) Let r be the root node of 23 tree if(r equals null) return

The pseudocode(2) if(r has one item){ if(item is between lb and ub) visit item rangeQuery(leftsubtree or r, lb, ub) rangeQuery(rightsubtree or r, lb, ub) if(item is larger than ub) rangeQuery(leftsubtree or r, lb, ub) if(item is smaller than lb) rangeQuery(rightsubtree or r, lb, ub) }

The pseudocode(3) if(r has two items){ if(the left item is between lb and ub and the right on is larger than ub) rangeQuery(leftsubtree or r, lb, ub) visit the left item rangeQuery(middlesubtree or r, lb, ub) if(the left item is smaller than lb and the right on is bwtewwn lb and ub) rangeQuery(middlesubtree or r, lb, ub) visit the right item rangeQuery(rightsubtree or r, lb, ub) }

The pseudocode(4) if(two items are both between the lb and ub) rangeQuery(leftsubtree or r, lb, ub) visit the left item rangeQuery(middlesubtree or r, lb, ub) visit the right item rangeQuery(leftsubtree or r, lb, ub) if(two items are both larger than ub) rangeQuery(leftsubtree or r, lb, ub) if(two items are both smaller than lb) rangeQuery(rightsubtree or r, lb, ub) }

Q5 exercise 19.10 2-3-4 tree represented by red-black tree

37 50 39 30 35 70 85 90 87 89 40 45 32 33 34 60 65 36 80 10 20 38 100

The end~