### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 152 Note 2 for CSE 565 at PSU

### View Full Document

## 27

## 0

## Popular in Course

## Popular in Department

This 15 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 27 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 152 Note 2 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 2 Analysis of Stable Matching Asymptotic Notation Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 8272008 Stable Matching Problem Goal Given n men and n women nd a quotsuitablequot matching Participants rate members of opposite sex Each man lists women in order of preference from best to worst Each woman lists men in order of preference from best to worst favorite least favorite favorite least favorite l l l 1 Xavier Amy Bertha Clare Amy Yancey Xavier Zeus Yancey Bertha Amy Clare Bertha Xavier Yancey Zeus Zeus Amy Bertha Clare Clare Xavier Yancey Zeus Men s Preference Profie Women39s Preference Profie 8272008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Stable Matching Problem Unstable pair man m and woman w are unstable if m prefers w to his assigned match and w prefers m to her assigned match Stable assignment no unstable pairs favorite least favorite favorite least favorite l l l 1 Xavier Amy Bertha Clare Amy Yancey Xavier Zeus Yancey Bertha Amy Clare Bertha Xavier Yancey Zeus Zeus Amy Bertha Clare Clare Xavier Yancey Zeus Men s Preference Profie Women39s Preference Profie 8272008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Review Questions 0 In terms of n What is the length of the input to the Stable Matching problem ie the number of entries in the tables Answer 2112 list entries or 2n210g 72 bits 8272008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Review Question Brute force algorithm an algorithm that checks every possible solution 0 In terms of n what is the running time for the brute force algorithm for Stable Matching Problem Assume your algorithm goes over all possible perfect matchings Answer 7 1 X time to check if a matching is stable n n2 8272008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne ProposeandRej ect Algorithm Proposeandrej ect algorithm GaleShapley 1962 Initialize each person to be free while some man is free and hasn39t proposed to every woman Choose such a man m w 1 woman on m39s list to whom m has not yet proposed if w is free assign m and w to be engaged else if w prefers m to her fianc m39 assign m and w to be engaged and m39 to be free else w rejects m 8272008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Proof of Correctness Termination 0 Claim Algorithm terminates after at most n2 iterations of while loop 0 Pf Each time through the loop a man proposes to a new woman There are only n2 possible proposals B C D V Z V Victor A Wyatt Xavier 3030 NltX ITIITIITIITI B C C D Yancey D A A B Zeus An instance where nn1 1 proposals required 8272008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne ProposeandRej ect Algorithm Observation 1 Men propose to women in decreasing order of preference Observation 2 Once a woman is matched she never becomes unmatched she only quottrades H up 8272008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne 0 Claim All men and women get matched 0 Proof by contradiction Suppose for sake of contradiction some guy say Zeus is not matched upon termination of algorithm Then some woman say Amy is not matched upon termination By Observation 2 Amy was never proposed to But Zeus proposes to everyone since he ends up unmatched 8272008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne a Proof of Correctness Stability Claim No unstable pairs Proof by contradiction Suppose AZ is an unstable pair they prefer each other to their partners in GaleShapley matching 8 Case 1 Z never proposed to A gt Z prefers his GS partner to A men l 39quot Se i damaging gt AZ is Stable order of preference Case 2 Z proposed to A gt A rejected Z right away or later gt A prefers her GS partner to Z women my mde up gt AZ is stable In either case AZ is stable a contradiction 8272008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Efficient Implementation We describe 0012 time implementation Assume men have IDs 1 n and so do women 0 Engagements data structures a list of free men eg a queue two arrays wife In and husband w set entry to 0 if unmatched ifm matched to w then wife m w and husband w m 0 Men proposing data structures an array men pref m i ith women on mth list an array count m how many proposals m made 8272008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Efficient Implementation Women rejecting accepting data structures Does woman w prefer man In to man In 39 For each woman create inverse of preference list of men Constant time queries after 0n preprocessing per woman Awnmmmmmnm 7 1 4 5 was AW 8m Inverse 4m Amy prefers man 3 To 6 since inverse 3 lt inverse6 2 7 for i 1 to n inverseprefi i 8272008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Summary Stable matching problem Given n men and n women and their preferences nd a stable matching if one exists GaleShapley algorithm Guarantees to nd a stable matching for every problem instance Also proves that stable matching always exists 0 Time and space complexity 0n2 linear in the input size 8272008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Brief Syllabus Reminders Worstcase analysis Asymptotic notation Basic Data Structures 0 Design Paradigms Greedy algorithms Divide and conquer Dynamic programming Network ow and linear programming 0 Analyzing algorithms in other models Parallel algorithms Memory hierarchies C 0 P NP and NPcompleteness 8272008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Focus on scalability parameterize the running time by some measure of size eg n number of men and women 0 Kinds of analysis Worstcase Averagecase requires knowing the distribution Bestcase how meaningful Exact times depend on computer instead measure asymptotic growth 8272008 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

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

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I 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."

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