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

## 16

## 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 16 views. For similar materials see /class/233118/cse-565-pennsylvania-state-university in Computer Science and Engineering at Pennsylvania State University.

## Similar to CSE 565 at Penn State

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

Algerithm Design and Analysis LECTURE 13 Divide and Conquer Closest Pair of Points Convex Hull Strassen Matrix Mult Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9242008 Midterm Exam 1 Willard Building Room 76 Tuesday night 815pm You may bring one 1 doublesided handwritten 85 X 11 sheet of notes on colored paper Hint use its preparation as a study aid 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Review questions Find the solution to the recurrence using MT Tn8Tn2cn Answer logba3gtl solution is n3 0 Draw the recursion tree for this recurrence a What is its height Answer hlog n b What is the number of leaves in the tree Answer 8h 810g nlog 8 n3 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne l x 1xx2xn f0rx 1 1 1xx2 f0rxlt1 l x Return to last slide Viewed 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne ClosesT Pair of PoinTs ClosesT pair Given n poinTs in The plane find a pair wiTh smallesT Euclidean disTance beTween Them FundamenTal geomeTric primiTive Graphics compuTer vision geographic informaTion sysTems molecular modeling air Traffic conTrol Special case of nearesT neighbor Euclidean MST Voronoi fasT closesT pair inspired fasT algoriThms for These problems BruTe force Check all pairs of poinTs p and q wiTh nz comparisons 1D version poinTs on a line On log n easy via sorTing AssumpTion No Two poinTs have same x coordinaTe i To make presenTaTion cleaner Closes r Pair of Poin rs Firs r A r remp r Divide Subdivide region info 4 quadran rs Closes r Pair of Poin rs Firs r A r remp r Divide Subdivide region info 4 quadran rs Obsfacle Impossible To ensure n4 points in each piece L o o 0 o o o o o no Closes r Pair of Poin rs Algori rhm Divide dr39aw vertical line L so That roughly n points on each side o L o o o o o o o o o 0 o o o o 39 39 o Closes r Pair of Poin rs Algori rhm Divide draw vertical line L so That roughly n points on each side Conquer find closesT pair in each side recursively O L O O 21 60 O O Closes r Pair of Poin rs Algori rhm Divide draw vertical line L so That roughly n points on each side Conquer find closesT pair in each side recursively Combine find closesT pair wi rh one point in each side seems like nz Refurn besT of 3 solu rions o L o o o o o o o 8i 21 o 39 o 0 160 o o o 0 0 Closes r Pair of Poin rs Find closesT pair39 wi rh one point in each side assuming Tha r disfcmce lt 6 o L o o o o o o o 0 21 o 39 o 6 mm16 21 16 o o o o o 0 0 Closes r Pair39 of Poin rs Find closest pair39 with one point in each side assuming Tha r disTance lt 6 Observa rion only need To consider points within 6 of line L Closes r Pair39 of Poin rs Find closest pair39 with one point in each side assuming Tha r disTance lt 6 Observa rion only need To consider points within 6 of line L Sor39T points in 26sTr39ip by Their y coordinate Closes r Pair39 of Poin rs Find closest pair39 wi rh one point in each side assuming Tha r disTance lt 6 Obser39vcrrion only need To consider poin rs wi rhin 6 of line L Sor39T points in Zosfr39ip by Their39 y coordinate Theorem Only need To check disTances of Those within 11 posiTions in sor39Ted lisT ClosesT Pair of PoinTs Def LeT si be The poinT in The Z sTr39ip wiTh The i rh smallesT ycoor dinaTe Claim If Ii jl 2 12 Then The disTcmce beTween si and SJ is aT leasT 6 Proof No Two poinTs lie in same 6by6 box I Two poinTs aT leasT 2 rows apar39T 2 39quotOWS have disTcmce 2 2G6 FacT STiII True if we replace 12 wiTh 7 0 J 6 a Q a e e 0 6 6 nahI NII l 00 00 nahl 00 Closes r Pair Algori rhm Closest Pairp1 pn Compute separation line L such that half the points are on one side and half on the other side 61 Closest Pairleft half 62 Closest Pairright half 5 min51 52 Delete all points further than 5 from separation line L Sort remaining points by y coordinate Scan points in y order and compare distance between each point and next 11 neighbors If any of these distances is less than 5 update 5 return 6 On log n 2Tn 2 On On log n On ClosesT Pair of PoinTs Analysis Running Time Tn s 2Tn2 0nlogn gt Tn 0nlog2n Q Can we achieve On log n A Yes Don39T sorT poinTs in sTrip from scraTch each Time SorT enTire poinT seT by xcoordinaTe only once Each recursive call Takes as inpuT a seT of poinTs sorTed by x coordinaTes and reTurns The same poinTs sorTed by y coordinaTe TogeTher wiTh The closesT pair CreaTe new ysorTed lisT by merging Two oquuT from recursive calls T0taltimen 0n10gn Tn Tn s 2Tn2 0n gt Tn 0n10gn AaU1 BbU 2 2CcAB la 192 1 1 011 612 Cln all 12 1n bu b12 bln C21 C22 CZn 021 022 a2n 521 b22 b2n Cnl Cn2 cnn anl an2 ann bnl bn2 bnn 11 Q Eaik 39bkj k1 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Standard algorithm forielton d0 forjelton d0 cijeO forkelton d0 cijecijJraik39bkj Running time n3 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne IDEA ngtltn matrix 2 X2 matrix of 712 gtlt 712 submatrices 23 31 39 22 C A 39 B r 616 78 recursive S 61f M 8Imults of 712 gtltn2 submatrices teedh u 2 Cf dg 4 adds of 712 gtltn2 submatrlces 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Analysis of DampC algorithm To an O submatrices work adding submatrices submatrix Size nlogbquot nlogzg n3 2 CASE 1 2 T n n3 No better than the ordinary algorithm 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Strassen s idea 0 Multiply 2 X2 matrices with only 7 recursive mults P1a f h VZP5P4 P2P6 P2ab h sP1P2 P3cd39e tP3P4 P4Zd39g e uzPsP1 P3 P7 P5 2 a d 6 h 7 mults 18 addssubs P 6 2 b d g h Note No reliance on P 7 Z a 6 6 f commutativity of multiplication A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9242008 Strassen s idea 0 Multiply 2 X2 matrices with only 7 recursive mults P1a f h VZP5P4 P2P6 P2ltabgth ltadgtltehgt P3ltcdgt39e dltg egt ltabgth P4dltg e ltb dgtltgh P5adeh aeahdedh P6b d gh dg de ah bh P7a c ef bgbh dg dh aebg 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

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

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