### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithm Design and Analysis CSE 565

Penn State

GPA 3.53

### View Full Document

## 22

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 0 page Class Notes was uploaded by Libby Kuhlman on Sunday November 1, 2015. The Class Notes belongs to CSE 565 at Pennsylvania State University taught by Staff in Fall. Since its upload, it has received 22 views. For similar materials see /class/233118/cse-565-pennsylvania-state-university in Computer Science and Engineering at Pennsylvania State University.

## Popular in Computer Science and Engineering

## Reviews for Algorithm Design and Analysis

### 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: 11/01/15

Algorithm Design and Analysis LECTURE 10 Divide and Conquer 0 Merge Sort 0 Counting Inversions Binary Search Exponentiation Solving Recurrences Recursion Tree Method Sofya Raskhodnikova S Raskhodnikova based on slides by E Demaine C leiserson A Smith K Wayne 9192007 Divide and Conquer Break up problem into several parts Solve each part recursively Combine solutions to sub problems into overall solution 39MOSt COHIIIIOII usage Break up problem of size 11 into two equal parts of size n2 Solve two parts recursively Combine two solutions into overall solution in linear time 0Consequence 2 Divide et impera Brute force n Veni vidi vici Divide and conquer 9 n log n 39 M39us 6 63 9192007 S Raskhodnikova based on slides by E Demaine C Leiserson A Smith K Wayne Sorting Given n elements rearrange in ascending order Applications sort a St 0f names obvious applications Display Google PageRank results Find the median problems become easy once Flnd the closest pa1r items are in sorted order Binary search in a database Find duplicates in a mailing list Data compression Computer graphics Computational biology nonobvious applications Load balancing on a parallel computer 9192007 S Raskhodnikova based on slides by E Demaine C leiserson A Smith K Wayne Divide array into two halves Recursively sort each half Merge two halves to make sorted whole Jon von Neumann 1945 A L G o R I l T H M s divide 01 A G 1 L 39o R H I M s T sort 2Tn2 A 1 G H I L M o R s T merge On 9192007 S Raskhodnikova based on slides by E Demaine C Leiserson A Smith K Wayne 0Combine two presorted lists into a sorted whole How to merge efficiently E Linear number of comparisons Use temporary array R 5433 s T A at H I I Challenge for the bored in place merge Kronrud 1969 using only a constant amount of extra storage 9192007 S Raskhodnikova based on slides by E Demaine C leiserson A Smith K Wayne Recurrence for Mergesort 1 if n 1 2Tn2 n if n gt 1 Tn 2 worst case r ning time of Mergesort on an input of size 11 Should be T rt21 TLn21 but it turns out not to matter asymptotically Tn Usually omit the base case because our algorithms always run in time 1 when n is a small constant 0 Several methods to find an upper bound on T n 9192007 S Raskhodnikova based on slides by E Demaine C Leiserson A Smith K Wayne Recursion Tree Method Technique for guessing solutions to recurrences 7 Write out tree of recursive calls 7 Each node gets assigned the Work done during that call to the procedure dividing and combining 7 Total Work is sum of Work at all nodes After guessing the answer can prove by induction that it works WWW I Recursion Tree for Mergesort Solve Tn 2Tn2 cn Where c gt O is constant m Tn2 Tn2 h1gn Tn4 Tn4 Tn4 Tn4 T6 Myriam I Recursion Tree for Mergesort Solve Tn 2Tn2 cn Where c gt 0 is constant T01 Tn2 Tn2 h 1g quot Tn4 Tn4 Tn4 Tn4 Tlt1gt mm w m Recursion Tree for Mergesort Solve Tn 2Tn2 cn Where c gt O is constant on 012 012 391 1g quot Tn4 Tn4 Tn4 Tn4 T6 mm m Recursion Tree for Mergesort Solve Tn 2Tn2 cn Where c gt O is constant on cnZ CW2 h 15 quot Uri4 Uri4 014 014 T m WWW Recurs10n Tree for Mergesort Solve Tn 2Tn2 cn Where c gt O is constant Cquot quot on CW2 cnZ En h 2 lg n 14 14 14 14 m a ltngt Total 90 lg n mm m Counting Inversmns Music Site tries to match your song preferences with others 7 You rankn songs 7 Mus1o s1te consults database to ndpeuple With similamstes Similarity metric number of inversions between two rankings 32 7 Songs 1 and inverted m lt1 but a gt a 5W 3 4 5 Inversmns 4 2 5 37242 IT Brute force check all nz pairs i andj mm W Counting Inversions Algorithm Divideandconquer 7 Divide separate list into two pieces 1 5 4 B 10 2 a 9 1211 3 7 DWBGUL E I Hi mm m Counting Inversion Algorithm Divideandconquer mm Counting Inversion Algorithm Divideandconquer 7 Divide separate list into two pieces 7 Conquer recursively count inversions in each half 1 5 4 B 10 2 6 9 1211 3 7 wagon Conquer 2m 2 551mm mversmns a gmwgmn mmquot 574 572472 872 112 3973977127312771271111731177 mm M Counting Inversions Algorithm Divideandconquer 7 Divide separate list into two pieces 7 Conquer recursively count inversions in each half new 11 and a1 are in J39 L and retum sum ofthree quantities 1 5 4 a 10 2 6 9 1211 3 7 wdem Conquer 2Tn2 5 mm m mversmns a gammaquot mmquot 9 bluergmen mmquot 573473B7 873B771n761n791n731n77 Tntal5 E1922 5mm m mm m Counting Inversions Combine Combine count blue green inversions E 7 Assume each halfis sorted 7 Countinversions where a1 and a1 are in different halves u 3 L i hl an 13 blue7green mversmns o v 3 v 2 v 2 o o o 0 Count om 2 3 7 1a 11 14 1 6 17 18 1 9 23 25 Merge om m 2Tn2 o n salmon m o n log n mm 1 wquot m m Implementation Precondition MergeandCount A and B are sorted Postcondition SortandCount Lis sorted Sortrandrcom tlm Jf 115 L has one element mth o and cm Jlst L Dlvld the list Jnco m halvas A and a m m 4 Sortrandrcom ti try El 4 Sortrandrcom tim tr m Merg randrbomtm 9 return I rA e I r and cm 5 01th List L gt WWW i w m Binary search Find an element in a sorted array 1 Divide Check middle element 2 Conquer Recursiver search 1 subarray 3 Combine Trivial Example Find 9 3 5 7 8 9 12 15 WWW i wquot g Binary search Find an element in a sorted array 1 Divide Check middle element 2 Conquer Recursiver search 1 subarray 3 Combine Trivial Example Find 9 3 5 7 9 12 15 WWW i w Binary search Find an element in a sorted array 1 Divide Check middle element 2 Conquer Recursiver search 1 subarray 3 Combine Trivial Example Find 9 3 5 7 8 9 12 15 WWW i w Binary search Find an element in a sorted array 1 Divide Check middle element 2 Conquer Recursiver search 1 subarray 3 Combine Trivial Example Find 9 3578915 WWW i w Binary search Find an element in a sorted array 1 Divide Check middle element 2 Conquer Recursiver search 1 subarray 3 Combine Trivial Example Find 9 3 5 7 8 9 12 15 WWW i w m m Binary search Find an element in a sorted array 1 Divide Check middle element 2 Conquer Recursively search 1 subarray 3 Combine Trivial Example Find 9 3 5 7 8 0 12 15 WWW m g Binary Search BmARYSEARcHb A1 71 gt nd bin sorted array A 1 If n0 then retum not foundquot 2 IfAUnZl b then retuminZl 3 IfAUnZl lt1 then 4 retum BINARYSEARCHA1 rt2U 5 Else 6 retum rt2 BWARYSEARCHAUnZll 71 yum W Recurrence for binary search M if 4 work dividing and combining subproblems subproblem size WWW W Recurrence for binary search Tltngt if 0 subproblems subproblem size work dividing and combining 3 Tn Tn2 C Tn4 25 cilog nl lg n mm A wquot W I Exponentiation Problem Compute a where b E Nis n bits long Question How many multiplications Naive algorithm b 92 exponential in the input length Divideandconquer algorithm am x a if b is even a WHY2 x WHY2 x a if b is odd Tb Tb2 91 2 Tb log b n WWW i w S f 2 0 ar recurrences Mergesort Counting Inversions Tn 2 Tn2 n n log n Binary Search Exponentiation Tn 1 Tn2 91 log n Master Theorem method for solving recurrences yum Algerithm Design and Analysis LECTURE 10 51 I fiffih Implement1ng MST Algorithms Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9152008 Minimum spanning tree MST Input A connected undirected graph G V E with weight function w E a R For now assume all edge weights are distinct Output A spanning tree T a tree that connects all vertices of minimum weight wT 2wuv WET 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Greedy Algorithms for MST Kruskal39s Start with T 4 Consider edges in ascending order of weights Insert edge e in T unless doing so would create a cycle ReverseDelete Start with T E Consider edges in descending order of weights Delete edge e from T unless doing so would disconnect T Prim39s Start with some root node s Grow a tree T from s outward At each step add to T the cheapest edge e with exactly one endpoint in T 9152008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne

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

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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