logo

Assignment On Design and Analysis of Algorithms

   

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.

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

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

CS 4120/5120 Spring 2017.
|6
|491
|172

Advanced Algorithm Analysis - Desklib
|8
|1712
|254

Algorithm Analysis and Examples
|15
|1404
|218

Data Structure and Algorithms - Desklib Online Library
|16
|1240
|91