Description
1. (25 Points) Chapter 1 – Stable Marriage. Consider the following preference lists for
men and women:
Man # Preference List
1 1 2 3 4
2 2 1 4 3
3 3 4 1 2
4 4 3 2 1
Woman # Preference List
1 4 3 2 1
2 3 4 1 2
3 2 1 4 3
4 1 2 3 4
(a) (5 Points) Find the man optimal stable matching. Show some intermediate steps of your
answer.
(b) (5 Points) Find the woman optimal stable matching. Justify your answer
(c) (5 Points) Suppose that in another problem setting all men have identical preferences.
How many steps does it take for the algorithm to converge? Justify your answer.
(d) (10 Points) Truthfulness in Stable Marriage.
The classic stable matching problem assumes that all men and women state their true
preferences. Let us now consider a version of the problem in which people can lie about
their preference. More specifically, let us consider the following restricted scenario.
Consider three men m1, m2, m3 and three women w1, w2, w3. Everybody states their
true preferences except for woman w3, who can lie to some extent: she can look at her
true preference list and switch the place of two men in her list with each other (she can
only flip a pair). Woman w3 has no control over the true preference lists (her own or
other people’s). The only decisions she can make are: (1) whether to lie or not (in the
way mentioned above, i.e., switching a pair of men in her list); and (2) if she decides to
lie, she can also choose which pair (among all three pairs of men) to switch in her list.
The GS algorithm then runs with input the declared preference lists and produces as
output a stable matching.
The question is: can woman w3 get a better match by lying about her preferences?
Resolve this question by doing one of the following:
i. (5 Points) Prove that, for any set of preference lists, switching the order of a pair
on the list cannot improve a woman’s partner in the GS algorithm; or
ii. (5 Points) Give an example of a set of preference lists for which, there is a switch
that would improve the partner of a woman who switched preferences. And if she
decides to lie, which pair of men should she switch in her preference list?
1
2. (40 Points) Chapter 2 – Running Time Analysis.
(a) (20 Points) Growth Rates Order the functions in ascending order of growth rate. That
is, if function g(n) immediately follows function f(n) in your list, then it should be the
case that f(n) is O(g(n)).
g1(n) = 2
√logn, g2(n) = 2n, g3(n) = n(logn)
3, g4(n) = n
4
3 , g5(n) = nlogn, g6(n) = 22n
, g7(n) = 2n2
(b) (20 Points) Consider the problem below:
You’re given an array A consisting of n integers A[1], A[2], …, A[n]. You’d like to output
a two-dimensional n-by-n array B in which B[i, j] (for i < j) contains the sum of array
entries A[i] through A[j]–that is, the sum A[i] + A[i + 1] + … + A[j]. (The value of array
entry B[i, j] is left unspecified whenever i ≥ j, so it doesn’t matter what is output for
these values.)
Here’s a simple algorithm to solve this problem:
for i= 1, 2,…, n do
for j= i+1, i+2,…, n do
Add up array entries A[i] through A[j]
Store the result in B[i, j]
end for
end for
(1) For some function f that you should choose, give a bound of the form O(f(n)) on
the running time of this algorithm on an input of size n (i.e. a bound on the number of
operations performed by the algorithm).
(2) For this same function f, show that the running time of the algorithm on an input
of size n is also Ω(f(n)). (This shows an asymptotically tight bound of Θ(f(n)) on the
running time.)
(3) Although the algorithm you analyzed in parts (1) and (2) is the most natural way to
solve the problem – after all, it just iterates through the relevant entries of the array B.
filling in a value for each – it contains some highly unnecessary sources of inefficiency.
Give a different algorithm to solve this problem, with an asymptotically better running
time. In other words, you should design an algorithm with running time O(g(n)), where
limn→∞ g(n)
f(n) = 0.
So in particular, you are required to:
i. (10 Points) Analyze the simple algorithm described there (steps (1) and (2)).
ii. (10 Points) Design a faster algorithm and analyze its running time (step (3)).
3. (35 Points) Chapter 3 – Graphs.
(a) (10 Points) DFS vs. BFS : Given a connected graph G = (V, E), and a specific node
u ∈ V . You run BFS from u, and you find the BFS tree T rooted at u. You run DFS
from u, and you find the same DFS tree T rooted at u. Prove that G = T, i.e., G cannot
contain any edges that do not belong to T.
(b) (10 Points) Connectivity : Consider an undirected graph G = (V, E) with |V | = n
nodes. Assume that there are two nodes s and t with distance between them strictly
greater than n
2 .
2
• Prove that there must exist some node v, different from s,t, such that deleting v
from G disconnects s from t.
• Draw one example of G, s,t, v.
• Provide an algorithm that finds such a node v in O(m + n) time.
(c) (5 points) You are visiting Irvine and you want to explore the city of Irvine and visit as
much places as possible. You start your special tour from one place and you need to end
your special tour at the same place. You want to minimize the effort so you don’t want
to visit the same place twice (except for the start point). Assume that the city of Irvine
is represented as a directed graph with N node and M edges. Where a node is one place
to visit and an edge is the route to take to this place. Your special tour in this graph
starts at node u is a simple path that begins and ends at the same node u. Formally, a
special tour is path u, v1, v2, …, vi, …, u where vi are distinct and not equal to u for all i.
For every node in the given graph, tell whether it is possible for you to do
your special tour starting at that node.
Given: N = 5, M = 6
Graph represented as adjacency list as follows:
1 2
2 3
3 4 1
4 2 5
5
(d) (5 points) Indicate which one of these two graphs is bipartite. Justify your answer.
(e) (5 points) Robotics Motion Planning
In autonomous robot navigation problem, you want to design a controller that can navigate the robot within a bounded space. Assume that you have a localization algorithm
running. Basically the robot can localize itself within this room. Assume you can discritize the space of your room into discrete number of squares. The robot does not know
the structure of the room. Hence, you can not just draw a line between the initial position and the destination that the robot can follow. The visual capability of the robot
can only let it see the neighboring discrete locations. Can you design a controller on the
robot that can take the robot from one initial position to a destination position?
i. (2 points) Specify one of the algorithms that you learnt in the class to plan the
motion of the robot.
3
ii. (2 points) Draw the route that the robot will take to reach its destination.
iii. (1 points) After the robot reached its destination (From C to F) as indicated in the
discretized space below, the robot wants to go back to its initial location. Draw the
path that the robot will take. What is the distance that the robot had to cover (in
terms of discretized blocks) to return to its initial location?
Initial
location
Destination
Room with finite edges Space can be discretized
Food for the thought! – No Credit
We studied the stable matching problem. A variant to it is when you have unequal number of men
and women and the men and women only list who they are willing to marry to (not everyone and
not in order of preference). Now suppose that the bipartite graph you indicated in question 3.e,
if the blue set is the men and the red set is the women. The edge indicates a possible marriage
between this man and this woman. How many compatible marriages are possible at the same time,
and how can we find such an optimal matching?
In graph theory, this is called a matching problem of maximum cardinality. In the example
3.e, try to think of an algorithm to find this number; the maximum cardinality of the matching.
4