### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Design and Analysis of Algorithms COT 5405

University of Central Florida

GPA 3.74

### View Full Document

## 27

## 0

## 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.

## Similar to COT 5405 at University of Central Florida

## Popular in Engineering and Tech

## Reviews for Design and Analysis of Algorithms

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.