Algorithm Analysis and Design: Problem Solutions - C11.37

This assignment presents solutions to two problems related to algorithm analysis and design. The first problem focuses on modifying a search-tree structure to efficiently determine the number of keys within a specified range, achieving O(h) worst-case time complexity. The second problem addresses an election scenario, requiring the development of an O(n log k)-time algorithm to identify the winner given a set of votes. The solution for the first problem is not fully provided, but the second problem includes a detailed explanation and code for finding the kth smallest element in two sorted arrays. The provided code uses a recursive approach with a time complexity of O(log n), effectively trimming the search space by comparing elements and recursively calling the function with adjusted parameters until the kth smallest element is found. The assignment emphasizes the importance of algorithm efficiency and the application of data structures in solving computational problems.

Problem 2
C-11.37 Suppose we wish to support a new method countRange(k1, k2) that
determines
how many keys of a sorted map fall in the specified range. We could clearly
implement this in O(s + h) time by adapting our approach to subMap. Describe
how to modify the search-tree structure to support O(h) worst-case time
for countRange.
Problem 3
Suppose we are given an n-element sequence S such that each element in S
represents a different vote in an election, where each vote is given as an integer
representing the ID of the chosen candidate. Suppose the number of candidates running
is 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 two
array with same size but after we trim the array the array size will be different. So we have to
make sure the smaller one always on top. This Algorithm trim the array by compare the value at
S[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 swap
If (SizeS > SizeT)
then return FindKthSmallest(k, ArrayT , ArrayS , SizeT, SizeS)
//Case when no element in a array
If(SizeS == 0 && SizeT > 0)
Then return T[k - 1]
//base case
If(k==1)

Then return min(S[0] , T[0])
// no larger than size
i  min(SizeS,k/2)
j  min(SizeT,k/2)
if(S[i-1] > b[j - 1])
then return FindKthSmallest (k - j, ArrayS , ArrayT + j , SizeS, SizeT -j )
else
return FindKthSmallest (k - i, ArrayS + i , ArrayT , SizeS – i , SizeT )
End