CSCI 570 – Summer 2020 – HW 1
Due July 10th
1 Graded Problems
1. State True/False: An instance of the stable marriage problem has a unique
stable matching if and only if the version of the Gale-Shapely algorithm
where the male proposes and the version where the female proposes both
yield the exact same matching.
2. A stable roommate problem with 4 students a, b, c, d is defined as follows.
Each student ranks the other three in strict order of preference. A match-
ing is defined as the separation of the students into two disjoint pairs. A
matching is stable if no two separated students prefer each other to their
current roommates. Does a stable matching always exist? If yes, give a
proof. Otherwise give an example roommate preference where no stable
matching exists.
3. Solve Kleinberg and Tardos, Chapter 1, Exercise 4.
4. N men and N women were participating in a stable matching process in
a small town named Walnut Grove. A stable matching was found after
the matching process finished and everyone got engaged. However, a man
named Almazo Wilder, who is engaged with a woman named Nelly Oleson,
suddenly changes his mind by preferring another woman named Laura
Ingles, who was originally ranked right below Nelly in his preference list,
therefore Laura and Nelly swapped their positions in Almanzos preference
list. Your job now is to find a new matching for all of these people and
to take into account the new preference of Almanzo, but you don’t want
to run the whole process from the beginning again, and want to take
advantage of the results you currently have from the previous matching.
Describe your algorithm for this problem.
Assume that no woman gets offended if she got refused and then gets
proposed by the same person again.
5. Solve Kleinberg and Tardos, Chapter 2, Exercise 3.
6. Solve Kleinberg and Tardos, Chapter 2, Exercise 4.
7. Solve Kleinberg and Tardos, Chapter 2, Exercise 5.
1
8. Which of the following statements are true?
(a) If f , g, and h are positive increasing functions with f in O(h) and g
in Ω(h), then the function f + g must be in Θ(h).
(b) Given a problem with input of size n, a solution with O(n) time
complexity always costs less in computing time than a solution with
O(n2) time complexity.
(c) F (n) = 4n +
√
3n is both O(n) and Θ(n).
(d) For a search starting at node s in graph G, the DFS Tree is never as
the same as the BFS tree.
(e) BFS can be used to find the shortest path between any two nodes in
a non-weighted graph.
9. Solve Kleinberg and Tardos, Chapter 3, Exercise 2.
2 Practice Problems
1. Reading Assignment: Kleinberg and Tardos, Chapters 1, 2, and 3.
2. Solve Kleinberg and Tardos, Chapter 1, Exercise 1.
3. Solve Kleinberg and Tardos, Chapter 1, Exercise 2.
4. Solve Kleinberg and Tardos, Chapter 1, Exercise 3.
5. Solve Kleinberg and Tardos, Chapter 2, Exercise 6.
6. Solve Kleinberg and Tardos, Chapter 3, Exercise 6.
2