3. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time. 4. Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue jugs. Also, for every red jug, there is a blue jug that holds the same amount of water, and vice versa. You are to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or if they are of the same volume. Assume this comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs. (a) Describe a deterministic algorithm that uses pairs. (n²) comparisons to group the jugs into (b) Give a randomized algorithm whose expected number of comparisons is O(nlogn), and show that this bound is correct. What is the worst-case number of comparisons for your algorithm? 5. (a) Show the contents of the hash table after inserting the keys E, L, E, C, T, I, O, N (in that order) into a hash table of length m = 13 for hashing with chaining. Let the hash function be h(k) (position of k in the alphabet) mod m. For example, the letter A = has position 1, B has position 2, and R has position 18. (b) Show the contents of the hash table after inserting the keys E, L, E, C, T, I, O, N (in that order) into a hash table of length m = 13 using open addressing with linear probing. (h' (k) + i) mod m, where the (position of k in the alphabet) mod m. For example, Let the hash function for linear probing be h(k, i) auxiliary hash function h'(k) = = the numerical value of the key A is 1, key B is 2, and key S is 19. (c) Show the result of inserting the keys E, L, E, C, T, I, O, N (in that order) into a hash table of length m = 13 using open addressing with double hashing. Let h₁(k) = k mod m and h₂(k) = 1+ (k mod m') where m = 11. Again assume the numerical value of an alphabetical key k is its position in the alphabet. 1+(k_mod m'

3. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time. 4. Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue jugs. Also, for every red jug, there is a blue jug that holds the same amount of water, and vice versa. You are to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or if they are of the same volume. Assume this comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs. (a) Describe a deterministic algorithm that uses pairs. (n²) comparisons to group the jugs into (b) Give a randomized algorithm whose expected number of comparisons is O(nlogn), and show that this bound is correct. What is the worst-case number of comparisons for your algorithm? 5. (a) Show the contents of the hash table after inserting the keys E, L, E, C, T, I, O, N (in that order) into a hash table of length m = 13 for hashing with chaining. Let the hash function be h(k) (position of k in the alphabet) mod m. For example, the letter A = has position 1, B has position 2, and R has position 18. (b) Show the contents of the hash table after inserting the keys E, L, E, C, T, I, O, N (in that order) into a hash table of length m = 13 using open addressing with linear probing. (h' (k) + i) mod m, where the (position of k in the alphabet) mod m. For example, Let the hash function for linear probing be h(k, i) auxiliary hash function h'(k) = = the numerical value of the key A is 1, key B is 2, and key S is 19. (c) Show the result of inserting the keys E, L, E, C, T, I, O, N (in that order) into a hash table of length m = 13 using open addressing with double hashing. Let h₁(k) = k mod m and h₂(k) = 1+ (k mod m') where m = 11. Again assume the numerical value of an alphabetical key k is its position in the alphabet. 1+(k_mod m'