PowerPoint Presentation
Exam 1 Review Session
CSCI 570
Summer 2020
Stable Matching:
Matching N women with N men so that they can stay happily ever after.
A stable matching is perfect and has no instability
Our approach: Gale-Shapely algorithm with time complexity
Hint1: Gale-Shapely algorithm can find two solutions for stable matching problem, but there can be more that two stable matching.
Hint2: In the version of Gale-Shapely algorithm that men propose, men end up with their best valid partner and women end up with their worst valid partner and vise versa if women propose …
2
Sample Questions:
1. A stable matching is a perfect matching (True/False)
Answer: True
2. There are at most 2 distinct solutions to the stable matching problem: one that is
preferred by men and one that is preferred by women (True/False)
Answer: False
3. In an instance of the Stable Matching problem, man m has claimed “I’m gonna marry w, anyway!” and by that, he means in every stable matching, m must marry w — or equivalently, if in a matching, m and w do not pair up, then the matching is definitely unstable. It is a strong claim and you want to figure out if it is true. Design an O(n^2) algorithm that, given an instance of Stable Matching problem as well as man m and woman w, checks whether m marries w in every stable matching or not.
Answer:
We run Gale-Shapley algorithm twice: once with men being proposing and then, with women proposing. In the first execution of the algorithm we learn whom is the best woman that m can hope to marry in a stable matching. In the second execution, we see whom is the worst woman he may ever marry in a stable matching. If they are both equal to w, it means that m must marry w. Otherwise, there exists a stable matching (basically, one of the two matchings we have found) in which m marries someone other than w. The complexity of the Gale-Shapely algorithm is O(n^2) therefore running it twice with men proposing and women proposing will result in O(2*n^2) = O(n^2).
4. Given an instance of the original Stable Marriage problem with n couples (so that every man ranks every woman and vice versa), where there is a man M who is last on each woman’s list and there is a woman W who is last on every man’s list. Prove or disprove the following statement: if we run the Gale-Shapley algorithm on this instance, then M and W will be paired with each other.
Answer:
True. Note that no man will propose to W unless he has been rejected by all n-1 other women. Let X be the first man to propose to W. At the time this happens, all the other women must be engaged to men they prefer to X. This can only happen if X is M, as otherwise M would have been preferred to X by some woman. So M proposes to W, she accepts and then everyone is engaged, and the algorithm stops
Asymptotic notations:
: the lower bound of an algorithm’s running time
: the upper bound of an algorithm’s running time
: the tight running time of an algorithm
Sample Questions:
If f(n) = O(g(n)), then g(n) = (f(n)).
Answer: True
2. If f=O(g)and g=O(h), then f=O(h).
Answer: True
3. Height of a binary heap is O(n)
Answer: True
4. If f (n) = O(n2) and g(n) = O(n2), then f (n) = O(g(n)).
Answer: False
Counter example: f is merge sort and g in binary search
Heap:
1. The key value for the element at the last index of a binary max-heap will be the smallest.
Ans = False
2. Given a n×n matrix where each of the rows and columns are sorted in ascending order, find the k-th smallest element in the matrix using a heap. You may assume that k < n. Your algorithm must run in time strictly better than O(n2). Answer: Build a min heap containing the first element of each row and then run extractMin to return the smallest element. If the element from the i-th row was deleted, then insert another remaining element in the same row to the min heap. Repeat the procedure k times. The total running time is O(n + k log n). Minheap is built in O(n), and an extractMin operation is O(log n), since there are n elements in the heap. To find the kth smallest elements we require k extract and k-1 insert operations. Dynamic Programming: Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: - Insert a character - Delete a character - Replace a character For example, word “Sunday’’ can be converted to the word “Saturday” using a minimum of three operations: 1) replace ‘n’ with ‘r’ 2) insert ‘a’ after ‘s’ 3) insert ‘t’ after the recently added ‘a’. Define (in plain English) subproblems to be solved. Answer: DP[i][j] = minimum number of operation required to convert word1[0:i-1] to word2[0:j-1] b) Write the recurrence relation for subproblems. If word1[i-1]. == word2[j-1]: DP[i][j] = DP[i-1][j-1] Else: DP[i][j] = 1 + min(DP[i][j-1], DP[i-1][j], DP[i-1][j-1]) c) Using the recurrence formula in part b, write pseudocode to compute the minimum number of operations required to convert a word to another word. (6 pts) Make sure you have initial values properly assigned. Answer: m = length (word1) n = length (word2) DP = an (m+1)*(n+1) matrix of zero elements for i = 0 to m: DP[i,0] = i end for j = 0 to n: DP[0,j] = j end for i = 1: m for j = 1: n if word1[i-1] == word2[j-1]: DP[i,j] = DP[i-1][j-1] Else: DP[i,j] = 1 + min(DP[i][j-1], DP[i-1][j], DP[i-1][j-1]) Return DP[m,n] d) What is the time and space complexity of the pseudocode in part c? Answer: Both time and space complexity are O(mn), where m is the length of word1 and n is the length of word2. For better understanding watch this Youtube video: https://www.youtube.com/watch?v=We3YDTzNXEk&t=488s /docProps/thumbnail.jpeg