### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 217 Note 13 for CSE 565 at PSU

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 23 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 17 views.

## Similar to Course at Penn State

## Reviews for 217 Note 13 for CSE 565 at PSU

### 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: 02/06/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 7 nlog 8 n3 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne f0rx 1 for x lt 1 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 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 Pair39 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 o f 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 with 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 Pair39 of PoinTs Def LeT si be The poinT in The Z sTr39ip wiTh The i rh smallesT ycoor dinaTe C Claim If Ii jl 2 12 Then The disTcmce beTween J 5i and SJ is aT leasT 6 a Proof No Two poinTs lie in same 6by6 box I Two poinTs aT leasT 2 rows apar39T 2 rows Q have disTcmce 2 2G6 l a I 56 FacT STiII True if we replace 12 wiTh 7 e C O O 6 6 nahI NII l 00 00 nahl 00 Closes r Pair Algori rhm Closest Pairp1 m pn Compute separation line L such that half the points oo ogn are on one side and half on the other side 61 Closest Pairleft half 2T012 62 Closest Pairright half 5 min 51 52 Delete all points further than 5 from separation line L 000 Sort remaining points by y coordinate O ogn 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 n return 6 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 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Standard algorithm forielton d0 forjelton d0 01190 forkelton d0 cl6 0 alk39bkj 1 Running time n3 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne IDEA ngtltn matrix 2 gtlt2 matrix of 112 gtlt n2 submatrices 23 31 39 22 C A 39 B 7 06 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 k 2 v Analysis of DampC algorithm To in submatrices work adding submatrices submatrlx szze 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 P3cd e tP3P4 P4Zd g 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 P3ltcdgte 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

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

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

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