COS 423: Theory of AlgorithmsTheory of AlgorithmsImagine: A World With No AlgorithmsWhat is COS 423?Administrative StuffApproximate Lecture OutlineSlide 7College AdmissionsSlide 9Love, Marriage, and LyingStable Matching ProblemSlide 12Slide 13ExampleSlide 15Slide 16Stable Roommate ProblemPropose-And-Reject AlgorithmImplementation and Running Time AnalysisA Worst Case InstanceProof of CorrectnessSlide 22Understanding the SolutionProof of Fact 3Slide 25Slide 26Extensions: Unacceptable PartnersExtensions: Sets of Unequal SizeExtensions: Limited PolygamyApplication: Matching Residents to HospitalsSlide 31Deceit: Machiavelli Meets Gale-ShapleyLessons LearnedLove, Marriage, and Lying: Extra SlidesExample With a Unique Stable MatchingHow to Represent Men and WomenHow to Represent MarriagesFilling in Some of the CodeRepresenting the Preference ListsInitializing the Preference ListsDumpingKeeping Track of Men’s ProposalsSlide 43Try Out The CodeSlide 45Slide 46Why So Slow?An Auxiliary Data StructureSlide 49Check if Marriage is StableSlide 51Princeton University • COS 423 • Theory of Algorithms • Spring 2002 • Kevin Wayne COS 423: Theory of Algorithms Princeton University Spring, 2001Kevin Wayne2Algorithm. (webster.com)A procedure for solving a mathematical problem (as of finding the greatest common divisor) in a finite number of steps that frequently involves repetition of an operation.Broadly: a step-by-step procedure for solving a problem or accomplishing some end especially by a computer."Great algorithms are the poetry of computation." Etymology."algos" = Greek word for pain."algor" = Latin word for to be cold.Abu Ja'far al-Khwarizmi's = 9th century Arab scholar.–his book "Al-Jabr wa-al-Muqabilah" evolved into today's high school algebra textTheory of Algorithms3Imagine: A World With No AlgorithmsFast arithmetic.Cryptography.Quicksort.Databases.FFT.Signal processing.Huffman codes.Data compression.Network flow.Routing Internet packets.Linear programming.Planning, decision-making.4What is COS 423?Introduction to design and analysis of computer algorithms.Algorithmic paradigms.Analyze running time of programs.Data structures.Understand fundamental algorithmic problems.Intrinsic computational limitations.Models of computation.Critical thinking.Prerequisites.COS 226 (array, linked list, search tree, graph, heap, quicksort).COS 341 (proof, induction, recurrence, probability).5Administrative StuffLectures: (Kevin Wayne)Monday, Wednesday 10:00 - 10:50, COS 104.TA's: (Edith Elkind, Sumeet Sobti)Textbook: Introduction to Algorithms (CLR).Grading:Weekly problem sets.Collaboration, no-collaboration.Class participation, staff discretion.Undergrad / grad.Course web site: courseinfo.princeton.edu/courses/COS423_S2001/Fill out questionnaire.6Approximate Lecture OutlineAlgorithmic paradigms.Divide-and-conquer.Greed.Dynamic programming.Reductions.Analysis of algorithms.Amortized analysis.Data structures.Union find.Search trees and extensions.Graph algorithms.Shortest path, MST.Max flow, matching.7Approximate Lecture OutlineNP completeness.More reductions.Approximation algorithms.Other models of computation.Parallel algorithms.Randomized algorithms.Miscellaneous.Numerical algorithms.Linear programming.Princeton University • COS 423 • Theory of Algorithms • Spring 2002 • Kevin Wayne College AdmissionsSample problem.Algorithm.Analysis.References:The Stable Marriage Problem by Dan Gusfield and Robert Irving, MIT Press, 1989.Introduction to Algorithms by Jon Kleinberg and Éva Tardos.9College AdmissionsGoal: Design a self-reinforcing college admissions process.Given a set of preferences among colleges and applicants, can we assign applicants to colleges so that for every applicant X, and every college C that X is not attending, either:C prefers every one of its admitted students to X;X prefers her current situation to the situation in which she is attending college C.If this holds, the outcome is STABLE.Individual self-interest prevents any applicant / college to undermine assignment by joint action.Princeton University • COS 423 • Theory of Algorithms • Spring 2002 • Kevin Wayne Love, Marriage, and LyingStandard disclaimer.11Stable Matching ProblemProblem: Given N men and N women, find a "suitable" matching between men and women. Participants rate members of opposite sex.Each man lists women in order of preference from best to worst.Zeus Bertha AmyDiane Erika ClareYancey Amy ClareDiane Bertha ErikaXavier Bertha ClareErika Diane AmyWyatt Diane AmyBertha Clare ErikaVictor Bertha DianeAmy Erika ClareMan1st2nd3rd4th5thMen’s Preference Listworstbest12Stable Matching ProblemProblem: Given N men and N women, find a "suitable" matching between men and women.Participants rate members of opposite sex.Each man lists women in order of preference from best to worst.Each woman lists men in order of preference.Erika Yancey ZeusWyatt Xavier VictorDiane Victor YanceyZeus Xavier WyattClare Wyatt YanceyXavier Zeus VictorBertha Xavier YanceyWyatt Victor ZeusAmy Zeus WyattVictor Yancey XavierWoman1st2nd3rd4th5thWomen’s Preference Listworstbest13Stable Matching ProblemProblem: Given N men and N women, find a "suitable" matching between men and women.PERFECT MATCHING: everyone is matched monogamously. –each man gets exactly one woman–each woman gets exactly one manSTABILITY: no incentive for some pair of participants to undermine assignment by joint action.–in matching M, an unmatched pair (m,w) is UNSTABLE if man m and woman w prefer each other to current partners–unstable pair could each improve by dumping spouses and elopingSTABLE MATCHING = perfect matching with no unstable pairs.(Gale and Shapley, 1962)14Lavender assignment is a perfect matching.Are there any unstable pairs?Men’s Preference ListWomen’s Preference ListZeusYanceyXavierManABA1stBAB2ndCCC3rdClareBerthaAmyWomanXXY1stYYX2ndZZZ3rd Yes. Bertha and Xavier form an unstable pair. They would prefer each other to current partners.BXExample15ExampleGreen assignment is a stable matching.ABAC XXYYYXZZZMen’s Preference ListWomen’s Preference ListZeusYanceyXavierMan 1stBAB2ndCC3rdClareBerthaAmyWoman 1st2nd3rd16ExampleOrange assignment is also a stable matching.A XXYYZZMen’s Preference ListWomen’s Preference