### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 669 Class Note for CSE 565 at PSU

### View Full Document

## 28

## 0

## Popular in Course

## Popular in Department

This 3 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 28 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 669 Class Note 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

Algorithm Design and Analysis LECTURE 3 An Example Problem Stable matching problem Asymptotic Notation 0 2 9 o conotation Sofya Raskhodnikova s mmmkm taxmmzwby K mm 5 04th c unemmA 5mm m m Review Question Brute force algorithm an algorithm that checks every possible solution In terms of n whatis the running time for the brute force algorithm for Stable Matching Problem Assume your algorithm goes over all possible perfect matchings Answer Sn s magmam baredovirlider am mm 5 04th c ZAMKDYAA 5mm w ProposeandReject 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 up s mmmkm taxmmzwby K mm 5 04th c mama 5mm Proof of Correctness Perfection Claim All men and women get matched Proof by contradiction 7Suppose for sake of contradiction some guy say Zeus is not matched upon termination of algorithm 7Then some woman say Amy is not matched upon termination 7By Observation 2 Amy was never proposed to 7But Zeus proposes to everyone since he ends up unmatched quotmmquot s magmam baredovirlider am mm 5 04th c ZAMKDYAA 5mm m M Proof of Correctness Stability Claim No unstable pairs Proof by contradiction 7 Suppose AZ is an unstable pair they prefer wch other to their partners in GaleShapley matching S 7 Case I Z never proposed to A WWW WWW 2 Z prefers his GS partner to A quotquot 39 Pquotquotquotquot 2 AZ is stable 7 Case 2 Z proposed to A 2 A rejected Z right away or later 2 A prefers her GS partner to Z 7 worm mm up 2 AZ is stable quotmm s mumbnkom baredovirluiaby K mm 5 Demamt c 1mm 5mm g Efficient Implementation We describe 0n1 time implementation Assume men have IDs n and so do women Engagements data structures 7 a list of free men eg a queue 7 two arrays wife In and husband w set entry to D unmatched lfm matchedtu w men w re m 7w and husband w 7m Men proposing data structures 7 an array men7pref m1 rhwomen on m3911 list 7 an array count In how many proposals m made quotmmquot s magmam baredovirlider we mm 5 04th c ZAMKDYAA 5mm m Efficient Implementation Women rejectingaccepting data structures 7 Does woman w prefer man in to man 139 7 7 For each Woman create inverse of preference list of men 7 Constant time queries afmr 0n preprocessing per Woman Amyprefersman 3 a a for 1 1 to n Since mama mm inversemref jl J 2 7 quotmmquot s maaammaa baredonrldaiby K Wayna E panama c uuerramA mat g Asymptotic Order of Growth Upper bound T n is 0fn if there exist constants c gt O and n0 2 0 such that for all n 2 no OSTM Sc fn Lower bound T n is Sfn if there exist constants c gt O and n0 2 0 such that for all n 2 no Tn Z c fn Tight bound Tn is fn if Tn is both Ofn and 9600 Example Tn 32n2 17n 32 7 Tn is 0n2 0n3 9n2 9n and n2 r Tn is not 0n 9n3 n or n3 quotmm s maaammaua baredonrluiaby K Wayna E panama c uuerramA 5mm W Summary Stable matching problem Given n men and 11 women and their preferences find a stable matching if one exists GaleShapley algorithm Guarantees to find a stable matching for every problem instance Time and space complexity 0n2 linear in the input size s maaaaaua baredonrlid am Wayna E panama c mama 5mm W Notation Onesided equality Tn Ofn 7 Not transitive fn 5n3 gn 3n2 39 fn 0013 gm but fn gn iAlternative notation Tn e Ofn Meaningless Any compaiisonbased sorting algorithm requires at least On log n comparisons iUse S for lower bounds s maaaaaua baredonrlid am Wayna E panama c Laaaama 5mm m g Properties Transitivity 71f r 0g and g 0h then f 0h 71f r 9g and g 5201 then r not 71f f g and g h then f h Additivity 71f r 0h and g 0h then r g 0h 71f r not and g nh then r g not fit f h and g 0h then f g h s maaammaua baredonrldaby K wma E panama c uuerramA 5mm m Common Functions Asymptotic Bounds Polynomials a0 an adnd is nd if ad gt O Polynomial time Running time is 0nd for some constant d independent of the input size n Loga thms loga n T logb n for all constants a b gt O m 7 WW h 5 tag was saw than my panama For every x gt 0 log n 0nquot my Wm was a no my Mama Exponentials For all r gt1 and all d gt 0 n6 0r Factorial By Sterling s formula n 260mg quotmmquot s maaaaaua baredonrlid we wma E panama c Laaaama 5mm m OverVIew Nutmun means Thmkm Eg L1m ngn n0n 3 cgt0 n0gt0Vn gt MO Upper 101ij1 In exxsts u 0 S n lt cgn bound OM 15 lt 00 n 2gn 3 cgt0 nagt0 v n gt MO Lower W m exxsts u 0 g cm lt n bound mg 15 gt 0 n gn bath ome above Txght bound 10gn1 mt exxsts u KMg andf 0g em lugn 15 gt 0 Andlt 00 nugn v cgt0 nugt0VyL gt nu Smct upper n1 o0quot ernrt exxsts 0 S n lt cgn bound 0 nugn v cgt0 nugt0 v n gt nu Smct lower n1 Lxrmt exxsts 0 g cgn n bound w ugn oo 5 Rummkom boredonrzwby 1c mm 539 04th c uueVXDmA 5mm quot1000000 2 beats nk for any fixed k 39n s mmmbm bluedonxltd am mm 539 04th c uueKDYAA 5mm

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

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

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