Page 1 1 CSE 421 Algorithms Richard Anderson Lecture 3 Classroom Presenter Project â€¢ Understand how to use Pen Computing to support classroom instruction â€¢ Writing on electronic slides â€¢ Distributed presentation â€¢ Student submissions â€¢ Classroom Presenter 2.0, started January 2002 â€“ www.cs.washington.edu/education/dl/presenter/ â€¢ Classroom Presenter 3.0, started June 2005 Key ideas for Stable Matching â€¢ Formalizing real world problem â€“ Model: graph and preference lists â€“ Mechanism: stability condition â€¢ Specification of algorithm with a natural operation â€“ Proposal â€¢ Establishing termination of process through invariants and progress measure â€¢ Underspecification of algorithm â€¢ Establishing uniqueness of solution Question â€¢ Goodness of a stable matching: â€“ Add up the ranks of all the matched pairs â€“ M-rank, W-rank â€¢ Suppose that the preferences are completely random â€“ If there are n Mâ€™s, and n Wâ€™s, what is the expected value of the M-rank and the W-rank What is the run time of the Stable Matching Algorithm? Initially all m in M and w in W are free While there is a free m w highest on mâ€™s list that m has not proposed to if w is free, then match (m, w) else suppose (m 2 , w) is matched if w prefers m to m 2 unmatch (m 2 , w) match (m, w) Executed at most n 2 times O(1) time per iteration â€¢ Find free m â€¢ Find next available w â€¢ If w is matched, determine m 2 â€¢ Test if w prefer m to m 2 â€¢ Update matching Page 2 1 CSE 421 Algorithms Richard Anderson Lecture 3 Classroom Presenter Project â€¢ Understand how to use Pen Computing to support classroom instruction â€¢ Writing on electronic slides â€¢ Distributed presentation â€¢ Student submissions â€¢ Classroom Presenter 2.0, started January 2002 â€“ www.cs.washington.edu/education/dl/presenter/ â€¢ Classroom Presenter 3.0, started June 2005 Key ideas for Stable Matching â€¢ Formalizing real world problem â€“ Model: graph and preference lists â€“ Mechanism: stability condition â€¢ Specification of algorithm with a natural operation â€“ Proposal â€¢ Establishing termination of process through invariants and progress measure â€¢ Underspecification of algorithm â€¢ Establishing uniqueness of solution Question â€¢ Goodness of a stable matching: â€“ Add up the ranks of all the matched pairs â€“ M-rank, W-rank â€¢ Suppose that the preferences are completely random â€“ If there are n Mâ€™s, and n Wâ€™s, what is the expected value of the M-rank and the W-rank What is the run time of the Stable Matching Algorithm? Initially all m in M and w in W are free While there is a free m w highest on mâ€™s list that m has not proposed to if w is free, then match (m, w) else suppose (m 2 , w) is matched if w prefers m to m 2 unmatch (m 2 , w) match (m, w) Executed at most n 2 times O(1) time per iteration â€¢ Find free m â€¢ Find next available w â€¢ If w is matched, determine m 2 â€¢ Test if w prefer m to m 2 â€¢ Update matching 2 What does it mean for an algorithm to be efficient? Definitions of efficiency â€¢ Fast in practice â€¢ Qualitatively better worst case performance than a brute force algorithm Polynomial time efficiency â€¢ An algorithm is efficient if it has a polynomial run time â€¢ Run time as a function of problem size â€“ Run time: count number of instructions executed on an underlying model of computation â€“ T(n): maximum run time for all problems of size at most n Polynomial Time â€¢ Algorithms with polynomial run time have the property that increasing the problem size by a constant factor increases the run time by at most a constant factor (depending on the algorithm) Why Polynomial Time? â€¢ Generally, polynomial time seems to capture the algorithms which are efficient in practice â€¢ The class of polynomial time algorithms has many good, mathematical properties Ignoring constant factors â€¢ Express run time as O(f(n)) â€¢ Emphasize algorithms with slower growth rates â€¢ Fundamental idea in the study of algorithms â€¢ Basis of Tarjan/Hopcroft Turing AwardRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!