Description
Problem 1:[GTG] Exercise C-10.50, page 455 somewhat modified: Design and analyze an 𝑂(log 𝑛) worst-case time algorithm for the following: Input: two sorted arrays 𝑆 and 𝑇, each of size 𝑛, with a total of 2𝑛 distinct
elements, and a positive integer 𝑘 ≤ 𝑛. Output: the 𝑘th smallest element in 𝑆 ∪ 𝑇.
Note that the case 𝑛 < 𝑘 ≤ 2𝑛 can be solved symmetrically by thinking “largest” instead of “smallest”. The reason is that the 𝑘th smallest element is the𝑘′th largestelement,where𝑘′ =2𝑛+1−𝑘.If𝑘>𝑛then𝑘′ ≤𝑛.
- a) What is the output for the below instance with 𝑘 = 6? What is it for 𝑘 = 10? 𝑆=𝑇=
- 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.
|
3 |
5 |
9 |
15 |
27 |
33 |
35 |
41 |
57 |
65 |
|
2 |
16 |
18 |
42 |
44 |
46 |
48 |
50 |
52 |
54 |
1
Problem 2: [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 .Wecouldclearlyimplementthisin𝑂(𝑠+h) time by adapting our approach to 𝑠𝑢𝑏𝑀𝑎𝑝. Describe how to modify the search-tree structure (e.g., its node structure) to support 𝑂(h) 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 𝑂(h) 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 𝑘) worst- case time algorithm for determining who wins the election.
2
