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

## 14

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

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 1 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 Bertha Amy Clare Xavier Yancey Zeus Amy Bertha 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 Bertha Amy Clare Xavier Yancey Zeus Amy Bertha 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 71 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 1 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 Proposeand rej 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 Vi c ror A e c o A X V B C n n An instance where nnl 1 proposals required WgtUn nwgt0 ITI ITI ITI ITI in g lt N lt x g lt N 8272008 Z V ltgtlt lt NltX 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 Proof of Correctness Perfection 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 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 zyrfilfro fpgizggriiccfasiquot9 gt AZ is stable 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 2 Amy an 8m Inverse 4 rh 5 rh 6 rh 3quotd 15 r Amy prefers man 3 To 6 for i 1 to n since inverse 3 lt inverse6 2 7 anerse pref L 1 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 Measuring Running Time 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

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

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