×

Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

31

0

2

607 Class Note for CSE 565 at PSU

Marketplace > Pennsylvania State University > 607 Class Note for CSE 565 at PSU

No professor available

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
No professor available
TYPE
Class Notes
PAGES
2
WORDS
KARMA
25 ?

Popular in Department

This 2 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 31 views.

×

Reviews for 607 Class Note for CSE 565 at PSU

×

×

What is Karma?

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
Algorithm Design and Analysis LECTURE 2 An Example Problem m Stable matching problem Sofya Raskhodnikova s Rarlhoahibwa baredonrlid hm mm l Stable Matching Problem Goal Given n men and n women find a quotsuitablequot matching 7Participants rate members of opposim sex 7Each man lists Women in order of preference from best to Worst 7Each Woman lists men in order of preference from best to Worst Mm hast mm mm lust mm m My Bertha Vahcey ijw er Zeus em a Amy Ci are j e W Vunczy Zeus Womenr m rmm m M My Bertha Cibi e mgr vmgy Zeus Mm mrmm mm s Rarlhoahibwa baredonrlid hm mm I Review Questions In terms of n whatis the length of the input to the Stable Matching problem ie the number of entries in the tables Answer 2n2 What is a simple lower bound on the running time of any algorithm for Stable Matching Answer 2 n The algorithm needs that much time to print the output quotmm s mmmiaw baredonrlid am mm gl Stable Matching Problem Perfect matching 7 Each man gets exactly one Woman 7 Each Woman gets exactly one man Stability no incentive for some pair of participants to undermine assignment by joint action 7 In matching M an unmatched pair m7w is unstable if man In and woman w prefer each other to their current partners 7 Unstable pair m7w could each improve by eloping Stable matching perfect matching with no unstable pairs Problem Given the preference lists of n men and n women find a stable matching if one exists quotmmquot s mmmiaw baredonrlid am mm I Stable Matching Problem Q Is assignment XC YB ZA stable mm hast mm mm hast mm D n n Vanczy xWr My Ci ir e mm Zeus 32pm Clare cmczy 2m Meni PIKEtn Pm e Women rmm mot quotmm s Rarlhoahibwa baredonrlid we mm gl Stable Matching Problem Q Is assignment XC YB ZA stable A No Bertha and Xavier will hook up Mm hast Mm mm hast mm m Amy Vuncey My cure Bertha Clare M 39 may 2 Womenr m rmm m M Mm mrmm mm quotmmquot s Rarlhoahibwa baredonrlid we mm Stable Matching Problem Q Is assignment XA YB ZC stable mm has mm mm has mm m n Beriha Clare My were Kmy Barma Mm mfgm Pm m mm Women A m rmm I m k quotmmquot s mmmiam baredonrlidaar byK mm Stable Matching Problem Q Is assignment XA YB ZC stable 39 A Yes Xand Y got their first choice Z is the last choise for every woman No man can participate in an unstable pair an has an mm has mm m Vnnczy Zeus mm m Zgus mar Vanczy Womeni m rum m w n Bertha Clare NW cm r e Amy Barma Mm mrmm mm quotmmquot s mmmiam baredonrlidaar byK mm Existence of Stable Matching Q Do stable matchings always exist A Not obvious a priori quotmm s mmmiuw magma am mm g Stable Roommate Problem Stable roommate problem 72n people each person ranks others from 1 to 2n1 iAssign roommate pairs so that no unstable pairs F ea 34 Man 3 5 5 A7354 2 Humming M C A D was DAVEunsmbie M g B D A4187 2 Humane Doofus A B C Observation Stable matchings do not always exist for stable roommate problem quotmmquot s mmmiuw magma am Waw ProposeandReject Algorithm Ltl Proposeand reject algorithm GaleShapley 1962 Inihlallz each person to be free quotmm some man is nae and hasn t proposm to waxy woman i V Choos such a man in w woman on m sdlst to whom n has not yet propaseai 1f 4w 15f frsei asslqn m and w to ba engagea er eAf w prefers m to her ance m39 assigtv m and w to be Angagedquot and w to be me asa w r j c s m quotmm s mmmium magma we mm Proof of Correctness Termination Claim Algorithm terminates after at most n2 iterations of while loop Pf Each time through the loop a man proposes to new woman There are only n2 possible proposals An mm in no1 lprapasuis quotaim quotmmquot s mmmium magma we Waw

×

25 Karma

×

×

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

Steve Martinelli UC Los Angeles

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

Amaris Trozzo George Washington University

"I made \$350 in just two days after posting my first study guide."

Steve Martinelli UC Los Angeles

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

Parker Thompson 500 Startups

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

Become an Elite Notetaker and start selling your notes online!
×

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