Ask a question to Desklib · AI bot

Ask NowBETA

Problem 2. C-11.37 Suppose we wish to support a new met

2 Pages483 Words264 Views
   

Added on  2019-09-16

BookmarkShareRelated Documents
Problem 2C-11.37 Suppose we wish to support a new method countRange(k1, k2) that determineshow many keys of a sorted map fall in the specified range. We could clearlyimplement this in O(s + h) time by adapting our approach to subMap. Describehow to modify the search-tree structure to support O(h) worst-case timefor countRange.Problem 3Suppose we are given an n-element sequence S such that each element in Srepresents a different vote in an election, where each vote is given as an integerrepresenting the ID of the chosen candidate. Suppose the number of candidates runningis k < n. Describe an O(n log k)-time algorithm for determining who wins the election.Below is the sample of solution。Problem 1:Explanation: This algorithm will find the kth smallest element in these array, we start with twoarray with same size but after we trim the array the array size will be different. So we have tomake sure the smaller one always on top. This Algorithm trim the array by compare the value atS[K/2 - 1] and T[K/2 -1] ,if S[i] > T[j], trim the arrays to left side of S[i], and right side of T[j], k= k-j.if S[i]<T[j], the other way around,k = k-i. We can find the Kth smallest until k = 1.Complexity: O(log(M+N)) -> O(logn) Algorithm FindKthSmallest (k, ArrayS , ArrayT , SizeS, SizeT ) // O(logn)//Pre-Cond: ArrayS,ArrayT two sorted Array//Post-Cond: output Kth smallest element in ArrayS U ArrayT// If Size T smaller than SizeS make a swapIf (SizeS > SizeT) then return FindKthSmallest(k, ArrayT , ArrayS , SizeT, SizeS)//Case when no element in a arrayIf(SizeS == 0 && SizeT > 0) Then return T[k - 1]//base caseIf(k==1)
Problem 2. C-11.37 Suppose we wish to support a new met_1

Found this document preview useful?

Related Documents
Advanced Algorithm Analysis: Recurrence Trees, Divide-and-Conquer Technique, and Universal Sink
|9
|2086
|492

Advanced Algorithm Analysis - Desklib
|8
|1712
|254

Advanced Algorithm Analysis: Techniques, Complexity, Recurrence, and Universal Sink
|9
|1953
|138

Advance Algorithm: Divide and Conquer, Recurrence, Universal Sink
|8
|1956
|422

Advanced Algorithm Analysis - Desklib
|9
|2127
|207

Algorithms: Internal Node Children, Kth Smallest Key, Sorting, Recurrence, Adjacency Matrix
|8
|2224
|310