Design an Algorithm for Ternary Search
Added on 2019-09-30
11 Pages2061 Words1060 Views
|
|
|
AssignmentOnDesign and Analysis of AlgorithmsSubject:Design and Analysis of AlgorithmsTopics:HW2
Q1.Find the recurrence relation on given equation:T (n) = 7T(n/5) +10n for n>1T(1)= 1, Find T(625)Solution: Here this recurrence relation is evaluate for n=5^s where s>0, since we have been given T (1),Using the given formula,T (n) = 7T(n/5) + 10n T(625) = 7*T(125) + 10*625==7*[ 7*T(25) + 10*125 ] + 10*625 = 7*[ 7*{ 7*T(5) + 10*25 } + 10*125 ] +10*625 = 7*[ 7*{ 7*( 7*T(1) + 10*5 ) + 10*25 } + 10*125 ] +10*625..................................................................................................................................................Now here T(1)=1Now, we can open the bracket to evaluate this expression, T(625) = (7^4) + (7^3)*10*5 + (7^2)*10*25 + (7^1)*10*125 + 10*625We can also write as:T(625) = (7^4) + (7^3)*10*(5^1) + (7^2)*10*(5^2) + (7^1)*10*(5^3) + (7^0)*10*(5^4)So, In general to evaluate the relation for n=5^s , so we can express in relation.T(5^s) = 7^s + Σ{7^(s-k-1)*10*5^(k+1)} where k can varies from 0 to (s-1), which is givens>0.When we will calculate this equation then we will found: T(625) will come out: 46801
Q2. Write a non-recursive algorithm for merge sort.Solution: As per the question, we have to explain the non-recursive algorithms for Merge Sort.Suppose we know the number of inversions in the left half and right half of the array (let beinv1 and inv2), what kinds of inversions are not accounted for in Inv1 + Inv2? The answer is– the inversions we have to count during the merge step. Therefore, to get number ofinversions, we need to add number of inversions in left subarray, right subarray and merge().How to get number of inversions in merge()?In merge process, let i is used for indexing left sub-array and j for right sub-array. At any stepin merge(), if a[i] is greater than a[j], then there are (mid – i) inversions. Because left andright subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] ...a[mid]) will be greater than a[j].
Merge-and-CountMergeAndCount(SortedList A, SortedList B):a = b = CrossInvCount = 0OutList = empty listWhile a < |A| and b < |B|: // not at end of a listnext = min(A[a], B[b]) OutList.append(next)If B[b] == next:b = b + 1CrossInvCount += |A| - a //inc by # left in AElsea = a + 1EndWhileAppend the non-empty list to OutListReturn CrossInvCount and OutListNote that MergeAndCount will produce a sorted list as well as the number of cross inversions.
End of preview
Want to access all the pages? Upload your documents or become a member.