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!