Suppose you have a list of integers Zo, ,..., n. You would like to produce a...

Transcribed Image Text:

Suppose you have a list of integers Zo, ₁,..., n. You would like to produce a duplicate-free list, although you're not picky about changing the order of items, so for example if the input is [1,3,5, 3, 2] then a perfectly acceptable output is [5, 2, 3, 1]. (a) [10 points] Explain how to do so in O(n log n) time in the worst case. (b) [10 points] Explain how to do so in O(n) time "on average" (or "with high probability", or however else you like to say). Problem 3. Merging Binary Heaps [20 points] Suppose you have two binary heaps h₁ and h₂, and you wish to produce a new heap h that combines both of them. That is, h contains all of the items (& their priorities) from both hi and h₂. Suppose that h₁ and h₂ have m and n elements, respectively. (a) [5 points] Explain how to do so in O(n +m) time. Justify your claim. (b) [10 points] Suppose n < m. Explain how to do so in O(n log m) time. Justify. (c) [5 points] Develop a combined merging strategy that will run in O(min{n+m, n log m,m log n}) time. You can assume the existence of the strategies in (a) and (b), even if you haven't figured them out yourself. Suppose you have a list of integers Zo, ₁,..., n. You would like to produce a duplicate-free list, although you're not picky about changing the order of items, so for example if the input is [1,3,5, 3, 2] then a perfectly acceptable output is [5, 2, 3, 1]. (a) [10 points] Explain how to do so in O(n log n) time in the worst case. (b) [10 points] Explain how to do so in O(n) time "on average" (or "with high probability", or however else you like to say). Problem 3. Merging Binary Heaps [20 points] Suppose you have two binary heaps h₁ and h₂, and you wish to produce a new heap h that combines both of them. That is, h contains all of the items (& their priorities) from both hi and h₂. Suppose that h₁ and h₂ have m and n elements, respectively. (a) [5 points] Explain how to do so in O(n +m) time. Justify your claim. (b) [10 points] Suppose n < m. Explain how to do so in O(n log m) time. Justify. (c) [5 points] Develop a combined merging strategy that will run in O(min{n+m, n log m,m log n}) time. You can assume the existence of the strategies in (a) and (b), even if you haven't figured them out yourself.

Answer rating: 100% (QA)

Answer Sure here are the solutions to the problems Problem 2 Duplicate Removal a On log n time solution There are several ways to remove duplicates from a list in On log n time in the worst case One c... View the full answer