Design and Analysis of Algorithms Ekesh Kumar April 7 2020 These are my course notes for CMSC 451 Design and Analysis of Algorithms taught by Professor Clyde Kruskal Gaps in lecture material are lled in with CLRS and Kleinberg Tardos Please send corrections to ekumar1 terpmail umd edu Contents 1 Tuesday January 28 2020 1 1 Introduction 1 2 Stable Marriage Problem 2 Thursday January 30 2020 2 1 Optimality and Correctness of Gale Shapley 3 Tuesday February 4 2020 3 1 Graph Terminology 3 2 Graph Representations 3 3 Graph Traversal 4 Thursday February 6 2020 4 1 Articulation Points 3 3 3 5 5 6 6 6 7 9 9 5 Tuesday February 11 2020 12 5 1 Articulation Point Algorithm Implementation 12 12 5 2 Strongly Connected Components 5 3 Classifying Edges in a DFS Tree 14 6 Thursday February 13 2019 15 6 1 Kosaraju s Algorithm 15 6 2 Topological Sorting 16 6 3 Bipartite Graphs 19 7 Tuesday February 18 2020 21 7 1 The Union Find Data Structure 21 7 1 1 Motivating the Union Find Data Structure 21 Email ekumar1 terpmail umd edu 1 Ekesh Kumar April 7 2020 Design and Analysis of Algorithms 7 1 2 Implementation of the Union Find Data Structure 23 7 1 3 Analysis of Union Find Operations 25 7 2 The Minimum Spanning Tree Problem 26 7 2 1 Problem Statement 26 7 2 2 Kruskal s Algorithm 26 7 2 3 Prim s Algorithm 28 8 Thursday February 20 2020 30 8 1 Interval Scheduling 30 32 8 2 Caching 32 8 3 Farthest in Future Algorithm 33 8 1 1 Extensions Minimizing Lateness 9 Tuesday February 25 2020 9 1 Pre x Codes 34 34 9 1 1 Constructing a Hu man code 35 9 2 Matrix Multiplication 37 10 Thursday February 27 2020 38 10 1 Strassen s Algorithm 38 10 2 Closest Pair of Points 39 11 Tuesday March 3 2020 11 1 Closest Pair of Points 11 2 Counting Inversions 40 40 41 12 Thursday March 5 2020 44 12 1 Convolutions 44 12 2 The Fast Fourier Transform 45 12 2 1 Polynomial Evaluation 46 12 2 2 Polynomial Interpolation 47 13 Tuesday April 7 2020 49 13 1 Subset Sum Problem 49 2 Ekesh Kumar April 7 2020 Design and Analysis of Algorithms 1 Tuesday January 28 2020 1 1 Introduction This is CMSC 451 Design and Analysis of Algorithms We will cover graphs greedy algorithms divide and conquer algorithms dynamic programming network ows NP completeness and approximation algorithms Homeworks are due every other Friday or so NP homeworks are typically due every other Wednesday There is a 25 penalty on late homeworks and there s one get out of jail free card for each type of homework 1 2 Stable Marriage Problem As an introduction to this course we ll discuss the stable marriage problem which is stated as follows Given a set of n men and n women match each man with a woman in such a way that the matching is stable What do we mean when we call a matching is stable We call a matching unstable if there exists some man M who prefers a woman W over the woman he is married to and W also prefers M over the man she is currently married to In order to better understand the problem let s look at the n 2 case Call the two men M1 and M2 and call the two women W1 and W2 First suppose M1 prefers W1 over W2 and W1 prefers M1 over M2 Also suppose that M2 prefers W2 over W1 and W2 prefers M2 then If both W1 and W2 prefer M1 over M2 and both M1 and M2 prefer W1 over W2 then it s still easy to see what will happen Mi will always match with Wi Now let s say M1 prefers W1 to W2 M2 prefers W2 to W1 W1 prefers M2 to M1 and W2 prefers M1 to M2 In this case the two men rank di erent women rst and the two women rank di erent men rst However the men s preferences clash with the women s preferences One solution to this problem is to match M1 with W1 and M2 with W2 This is stable since both men get their top preference even though the two women are unhappy The solution to the problem starts to get a lot more complicated when the people s preferences do not exhibit any pattern So how do we solve this problem in the general case We can use the Gale Shapley algorithm Before discussing this algorithm however we can make the following observations about this problem 3 Ekesh Kumar April 7 2020 Design and Analysis of Algorithms Each of the n men and M woman are initially unmarried If an unmarried man M chooses the woman W who is ranked highest on their list then we cannot immediately conclude whether we can match M and w in our nal matching This is clearly the case since if we later nd out about some other man M2 who prefers W over any other woman W may choose M2 if she likes him more than M However we cannot immediately rule out M being matched to W either since a man like M2 may not ever come Just because everyone isn t happy doesn t mean a matching isn t stable Some people might be unhappy but there might not be anything they can do about it if nobody wants to switch Moreover we introduce the notion of a man proposing to a woman which a woman can either accept or reject If she is already engaged and accepts a proposal then her existing engagement breaks o the previous man becomes unengaged Now that we ve introduced these basic ideas we can now present the algorithm Input A list of n men and n women to be matched Output A valid stable matching stable matching set each man and each woman to free while there exists a man m who still has a woman w to propose to let w be the highest ranked woman m hasn t proposed to if w is free m w become engaged else let m be the man w is currently engaged to if w prefers m to m m w remain engaged else m w become engaged and m loses his partner Proposition 1 1 The Gale Shapley algorithm terminates in O n2 time Proof In the worst case n men end up proposing to n women The act of proposing to another person is a constant time operation Thus the O n2 runtime is clear 4 Ekesh Kumar April 7 2020 Design and Analysis of Algorithms 2 Thursday January 30 2020 2 1 Optimality and Correctness of Gale Shapley Last time we introduced the Gale Shapley algorithm to nd a stable matching Today we ll prove that the algorithm is correct i e it never produces an unstable matching and it is optimal for men i e the men always end up for their preferred …
View Full Document