# Algorithm
- 10-20 unnanncounced quizes
- Exams on paper
- 4- 5 assignments cpp or free to choose
- slides: https://www.cs.princeton.edu/~wayne/kleinberg-tardos/
- book: https://github.com/davie890/CS102-Algorithm-Analysis/raw/master/Algorithm%20Design%20by%20Jon%20Kleinberg%2C%20Eva%20Tardos.pdf

------
### You dint start untill u know there is a soluttion
### this course is about explaining and understanding and even thinking of proof of algorithms not making new algorithms
## Stable matching Problem
if random matching, ignoring preferance we make unstable pair
preferance over the other one not 1st preferance
a perfect matching is when there are no unstable pair
matchinhgs is a set of a pair
an empty set is also a matching
Do stable matchings always exisit?
### self reinforcing method
- Gale-Shapely deferred acceptance
While each hospital hasnt offered to their preferance list (decreasing preferance list)
pick a hospital offer to first preffered student not offered to yet
if the student is somewhere, extend offer, if the student likes this more he will switch
else the student rejects (in each of these a hospital now is unmatched and will be reconsidered) (students accept in increasing preferance)
Return a stable matching
matching:
-no hospital is repeated since proposes if unmatched
student only accepts so only keeps one
all hospitals get matched:
-contradiction there is a hospital unmatched
-since student accepts and only trades up and the algorithm doesnt end until hospital doesnt offer all students, all hospitals get matched
\[counting] all n hospitals hence all h students matched haence it is a **perfect match**