Lectrue 3: Algorithm - PowerPoint Presentation, Mathematics, Engineering Notes | EduRev

Created by: Shifali Jain

: Lectrue 3: Algorithm - PowerPoint Presentation, Mathematics, Engineering Notes | EduRev

 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 Award
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!