1. Illustrate the operation of Radix_sort on the following list of English words: cow, dog, seq, rug, row, mob, box tab, bar ear, tar, dig, big, tea, now, fox. ANSWER:
It is a sorting algorithm that is used to sort numbers. We sort numbers from least significant digit to most significant digit.
In the following array of words, three is the maximum number of digits a word has, hence the number of passes will be three.
In pass 1, sort the words alphabetically using first letter from the right. For eg, tea has “a” as the last letter, hence it comes first, similarly mob which has “b” as the last letter comes second. In this way the remaining words are sorted.
In pass 2, sort the words alphabetically using second letter from the right. For eg, tab has “a” as its middle letter which comes first, then comes bar and so on.
In pass 3, sort the words alphabetically using third letter from the right. For eg, bar has “b” as its first letter from left and since no word starts with “a”, bar will appear first. Similarly, big, box, cow and so on. UNSORTED ARRAY | PASS 1 | PASS 2 | PASS 3(SORTED ARRAY) | cow | tea | tab | bar | dog | mob | bar | big | seq | tab | ear | box | rug | rug | tar | cow | row | dog | tea | dig | mob | dig | seq | dog | box | big | dig | ear | tab | seq | big | fox | bar | bar | mob | mob | ear | ear | dog | now | tar | tar | cow | row | dig | cow | row | rug | big | row | now | seq | tea | now | box | tab | now | box | fox | tar | fox | fox | rug | tea |

2. Illustrate the insertion of the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash table with collisions resolved by chaining. Let the table has 9 slots, and let the hash function be h(k) = k mod 9.

ANSWER:

The hash function is h(k)=k mod 9 and the hash functions of the keys are: 1. 5 mod 9 = 5 2. 28 mod 9 = 1 3. 19 mod 9 = 1 4. 15 mod 9 = 6 5. 20 mod 9 = 2 6. 33 mod 9 = 6 7. 12 mod 9 = 3 8. 17 mod 9 = 8 9. 10 mod 9 = 1
Based on the hash values obtained from the hash functions we are going to store them in the hash tables in the following way:

/ | / | / | / | / | . | / | / | / |
0 1 2 3 4 5 6 7 8

5 | / |

. | / | / | / | / | . | / | / | / | 0 1 2 3 4 5 6 7 8 28 | / | 5 | / |

. | / | / | / | / | . | / | / | / | 0 1 2 3 4 5 6 7 8 28 | / | 5 | / |

19 | / |

. | / | / | / | / | . | . | / | / | 0 1 2 3 4 5 6 7 8 15 | / | 28 | / | 5 | / |

19 | / |

. | / | . | / | / | . | . | / | / | 0 1 2 3 4 5 6 7 8 15 | / | 20 | / | 28 | / | 5 | / |

19 | / |

. | / | . | / | / | . | . | / | / | 0 1 2 3 4 5 6 7 8 15 | / | 20 | / | 28 | / | 5 | / |

33 | / | 19 | / |

. | / | . | . | / | . | . | / | / | 0 1 2 3 4 5 6 7 8 15 | / | 20 | / | 12 | / | 28 | / | 5 | / |

33 | / | 19 | / |

. | / | . | . | / | . | . | / | . | 0 1 2 3 4 5 6 7 8 15 | / | 20 | / | 12 | / | 17 | / | 28 | / | 5 | / |

33 | / | 19 | / |

. | / | . | . | / | . | . | / | . | 0 1 2 3 4 5 6 7 8 15 | / | 20 | / | 12 | / | 17 | / | 28 | / | 5 | / |

33 | / | 19 | / |

10 | / |

3. You are given an array of n elements, and you notice that some of these elements are duplicates; that is they appear more than one time in the array. Devise an algorithm to remove all duplicates from the array in time O(n log n). ANSWER: Suppose an array is given with n elements where there are some duplicate values present. To remove all the duplicate elements we will use Merge Sort where we will divide the entire array of n elements into two arrays a and b. Each array must be sorted already in non-decreasing order. As a result a new array is returned containing the same elements merged together into a new array in non-decreasing order. We will use two variables to keep track of where we are in arrays a and b: index_a and index_b. * Set index_a to 0. * Set index_b to 0. * Create an empty array c. * While index_a<the length of array a and index_b<the length of array b, do the following : i) If a[index_a]<=b[index_b], then do the following: * Append a[index_a]on to the end of array c * Add 1 to index_a Otherwise, do the following: * Append b[index_b] on to the end of the array c * Add 1 to index_b Once we have finished adding, we have added all of the elements of either array a or array b to array c. * If a[index_a]= b[index_b], then add 1 to index_b which means the element in the array b will be ignored and the checking will be done with the next element in the array b. In this way, duplicate elements can be ignored and all other elements will be copied in other array c. * If index_a<the length of array a, then: Append all remaining elements of the array a to array c. Similarly, If index_b<the length of array b, then: Append all remaining elements of the array b to array c. * Return the array c with all the sorted elements. In order to analyze Merge Sort we have to go into the details of two processes that is core of the implementation. First, the list is splited into halves. We divide a list in half logn times where n is the length of the list. The second process is the merge. Each item in the list will eventually be processed and placed on the sorted list. So the merge operation which results in a list of size n requires n operations. The result of this analysis is that logn splits, each of which costs n for a total of nlogn operations. Hence we can see that a merge sort is an O(nlogn) algorithm. 4. A sequence of n operations is performed on a data structure. The ith operation costs i if i is an exact power of 2, and 1 otherwise. Use aggregate analysis to determine the amortized cost per operation. ANSWER: Let a sequence of n operations on a data structure is performed in which the ith operation costs i if is an exact power of 2, and 1 otherwise. We will use aggregate analysis to determine the amortized cost per function. OPERATIONS | COST | 1 | 1 | 2 | 2 | 3 | 1 | 4 | 4 | 5 | 1 | 6 | 1 | 7 | 1 | 8 | 8 | 9 | 1 | 10 | 1 | n | n or 1 | In a sequence of n operations there are log2n+1 exact powers of 2, namely 1,2,4,8,…,2log2n . The total cost will be therefore, Total Cost =k=0logn2k + k=0n-logn1 = 1-2logn+11-2+ n-logn = 1-2logn .2-1 + n-logn = 2n + n –logn -1 = 3n – logn -1 <=3n

The total cost to compute n operations is therefore O(n). The average cost of each operation calculated in the worst case is then O(n) /n = O(1). Therefore, the amortized cost per function is O(1).

5. A sequence of stack operations is performed on a stack whose size never exceeds k. After every k operations, a copy of the entire stack is made for backup purposes. Show that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized costs to the various stack operations. ANSWER: Amortized cost is assigned to the operations in the following way:

OPERATION | AMORTTIZED COST | PUSH | 3 | POP | 0 | MULTIPOP | 0 | COPY | 0 | Here the PUSH operation is assigned a cost of 3 to pay for the item to be pushed. From 3, $1 is saved in the credit for the future POP and remaining $1 is saved for future copy. POP cannot be performed if the stack is empty. POP does not need to pay for itself since each item on the stack is reserving 1 credit for it. Similarly MULTIPOP also does not need to pay as it is same as the cost of the POPs. The COPY also does not need to pay as the PUSH has saved a credit for this also. Thus we can see that in the worst case, the amortized cost for n operations (n pushes) is O(3n)=O(n).Furthermore, credit will always be greater than 0 because POPs and MULTIPOPs cannot occur if items have not been pushed and COPY does not incur any cost if the stack is empty.

6. Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it 0). Show how to implement a counter as an array of bits so that any sequence of increment or reset operations takes time O(n) on an initially zero counter.

ANSWER: