Design and Analysis of Algorithms
Design and Analysis of Algorithms COT 5405
University of Central Florida
Popular in Course
Popular in Engineering and Tech
This 6 page Class Notes was uploaded by Lamont Block on Thursday October 22, 2015. The Class Notes belongs to COT 5405 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 27 views. For similar materials see /class/227693/cot-5405-university-of-central-florida in Engineering and Tech at University of Central Florida.
Reviews for Design and Analysis of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
Design and Analysis of Algorithms COT 5405 CLASS NOTES 14th October 2003 Overview 0 Divide and Conquer 0 Master theorem 0 Master theorem based analysis for gt Binary Search gt Merge Sort gt Quick Sort Divide and Conguer Basic Idea Ni Decompose problems into sub instances Solve sub instances successively and independently Combine the sub solutions to obtain the solution to the original problem E In order to look into the ef ciency of the Divide and Conquer lets look into the Multiplication of two n digit Numbers Traditional Multiplication Say we are multiplying 382 with 695n3 382 695 Essentially we are multiplying 1 digit with n other digits and then adding the n numbers which can give us a solution of at most 2n digits There are n additions each of On time at most which gives us the running time of the algorithm as Onz l l Using Divide and Cong uer to multiply n dig t numbers We will write the two ndigit numbers as follows 10 2X Y 10 2WZ 10 XW xz YW 1o 2 YZ 1 That is we are converting the multiplication of two ndigit numbers into multiplication of four n 2 digit numbers plus some extra work involved in additions We are recursively calling multiplication and performing some additions in every recursion Let T n be the running time of multiplying two ndigit numbers Then in our case T n 4T n2 0 n 0 Four multiplications of n 2 digit numbers 0 Addition is going to be between numbers that have atmost 2n digits Thus addition can be 0 n Recursively substituting the value of T n T n 4 4T n4 0 n2 0 n 16 T n4 40 N2 0 n CT1 Master s Theorem Let Tn be the running time of an algorithm with an input size of n Suppose we can run the algorithm in such a way that we make a recursive calls every time with an input size of nb and do some extra work in every recursion additions and subtractions Such that T n can be represented as T n a T mb 0 nk Then If log bagtk T n 0 n10g ba recursive calls dominates If log bak T n 0 nklog n almost equal work in rec calls and in extra work If log baltk T n 0 nk Extra work dominates In our multiplication problem T n 4T n2 0 n A4 b2 Logz42 kl Since algorithm is dominated by recursive calls and the running time is 0 n2 But this is as good as our traditional multiplication algorithm Since we now know that multiplications dominate the running time if we can reduce the number of multiplications to three which can bring down our Tn by 25 To calculate l we just need the following 3 multiplications separately 1 XYWZ 2 additions and one multiplication 2XW 3YZ Then we can calculate XZYWXYWZXWYZ Thus we use three multiplications at the expense of some extra additions and subtractions which run in constant time each of On time Thus Tn3Tr 2 On Applying Master s theorem A3b2k1 Thus TnOnl gz3 Since log 23 N15 We have reduced the total number of recursive calls in our program For very large n it will work well but in actual implementation we hardly code to gain advantage out if this feature Binary Search Goal Searching for nth value in a sorted list of length n Divide the list into two and recursively search in the individual lists half the size Again Let Tn be the running time of the algorithm Then TnTn2 Ol In Ol time we divide the list into two halvesn2 that run in Tn2 time Using Master s theorem A lb2 Lo g2 10 K0 So TnOlo g n Merge Sort Goal Splitting the element list into 2 lists sort them and merge them Tn2Tn2 On Here the hidden constant is greater than the hiddent constant in the merge sort because while dividing the lists into two different arrays and then sorting them we are allocating extra space and subsequently copying into the original array Using Master s theorem A2b2kl Log22l So TnOn log n uicksort Goal Pick one element as the partition element Put all the elements smaller than it to the left of it and all elements greater than it to the right of it On the lists left and right of the partition element recursively call Qsort Say the list is 83692475 Partition element5 83 6 92 4 7 5 T front Last 8 in the womg place 7 fine 8 3 6 9 2 4 7 5 T T front Last 43692875 T T front last 4 3amp9 6lt7 5 front last 43 2 9 687 5 last front Now swap front with 5 and we have 5 in place 43256879 Thus the only extra space utilized here is the temporary variable used for swapping In te worst case we might end up choosing a partition element which is the rst element in our list In that case TnOnz To make sure this rarely happens 1 Pick a random partition element 2 Probablity of picking a good partition element is as low as the probability of picking a bad one So they will even out There are n possible partition elements Element 1 Now T n ln TO Tnl 001 ln Tl Tn2 0n ln T2 Tn3 0n IIII H ln T nl T 0 0 71 n Tn 2 k02 391Tk 00 i4 Substitute n n1 n1 Tn1 2 k02 391Tk 0n12 e3 SubtractA from B n Tn nlTnl 2 Tn 1 0m n Tn n1 Tnl 0n Tn n1n Tn1 01 Divide by n1 Tnn1 Tn1n 01n 9 C Let Sn Tnn1 9 D Sn Sn1 01n This can be written as a sum Sn2 01n1 01n Sn3 01n2 01n1 01n Sn 00 Equot Jk 0Hn Sn Tnn1 0 In 71 E Substitute D in C Tn Sn n1 use E Tn O In 71 n1 Tn0nlgn Notes compiled by Shankar Vaithianthan and Harjinder Mandarh