Courses

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