Problem 1: [35%] [GTG] Exercise C-10.50, page 455 somewhat modified:
Design and analyze an worst-case time algorithm for the following:
Input: two sorted arrays and , each of size , with a total of distinct elements, and a positive integer .
Output: the th smallest element in
Note that the case can be solved symmetrically by thinking
“largest” instead of “smallest”. The reason is that the th smallest element is the th largest element, where If then .
a) What is the output for the below instance with ? What is it for ?
3
5
9
15
27
33
35
41
57
65
2
16
18
42
44
46
48
50
52
54
b) First solve the problem for the special case , i.e., find median of .
Hint: investigate the relationship between , , and
c) Now solve the problem for the general case of as expressed in the problem statements.
1
Problem 2: [35%] [GTG] Exercise C-11.37, page 527:
Suppose we wish to support a new method 𝑐𝑜𝑢𝑛𝑡𝑅𝑎𝑛𝑔𝑒 𝑘1 , 𝑘2 that determines how many keys of a sorted map fall in the specified key range
𝑘1, 𝑘2 = 𝑘 𝑘1 ≤ 𝑘 ≤ 𝑘2 . We could clearly implement this in 𝑂( 𝑠 + ℎ) time by adapting our approach to 𝑠𝑢𝑏𝑀𝑎𝑝. Describe how to modify the search-tree structure (e.g., its node structure) to support 𝑂(ℎ) worst-case time for 𝑐𝑜𝑢𝑛𝑡𝑅𝑎𝑛𝑔𝑒. Design and analyze such an algorithm.
Hint: Augment each node of the search tree by a new field called 𝑠𝑖𝑧𝑒, where 𝑠𝑖𝑧𝑒(𝑣) is the size of the sub-tree rooted at 𝑣, i.e., the number of descendants of 𝑣 (including itself). How will you use this new field to implement 𝑐𝑜𝑢𝑛𝑡𝑅𝑎𝑛𝑔𝑒 in 𝑂(ℎ) time? Also explain how you would
revise the dictionary operations 𝑖𝑛𝑠𝑒𝑟𝑡, and 𝑑𝑒𝑙𝑒𝑡𝑒, to properly maintain this augmented field in a consistent manner without degrading their asymptotic running time.
Problem 3: [30%] [GTG] Exercise C-12.36, page 569:
Consider the voting problem from Exercise C-12.35, but now suppose that we know the number 𝑘 < 𝑛 of candidates running, even though the integer IDs for those candidates can be arbitrarily large. Describe an 𝑂(𝑛 log 𝑘) worstcase time algorithm for determining who wins the election.
