1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any
justification.
[ TRUE/FALSE ]
Assume that no two men have the same highest-ranking woman. If the women carried
out the proposal to men, then the Gale-Shapley algorithm will contain a matching set
where every man gets their highest-ranking woman.
[ TRUE/FALSE]
Consider a binary heap with n nodes stored as an array. The parent, left child and
right child of the node with index 11 are at indices 6, 22, and 23 respectively.
[ TRUE/FALSE ]
Inserting an element into a binary min-heap takes O(1) time if the new element is
greater than all the existing elements in the min heap.
[ TRUE/FALSE ]
Using the master’s theorem the asymptotic bounds for the recurrence 2T(n/4) + n is
Θ(n).
[ TRUE/FALSE ]
Consider a version of the interval scheduling problem where all intervals are of the
same size. A greedy algorithm based on earliest start time will always select the
maximum number of non-overlapping intervals.
[ TRUE/FALSE ]
For any tree with n vertices and m edges we can say that O(m+n) = O(m).
[ TRUE/FALSE ]
A directed graph G is strongly connected if and only if G with its edge directions
reversed is strongly connected.
[ TRUE/FALSE ]
The number of binomial trees in a binomial heap with n elements is at most
O(log n).
[ TRUE/FALSE ]
A minimum spanning tree of a bipartite graph is not necessarily a bipartite graph.
[ TRUE/FALSE ]
In Fibonacci heaps, the decrease-key operation has an amortized cost of 𝑂(1).
第 2 ⻚，共 8 ⻚
2) 16 pts.
A Maximum Spanning Tree is a spanning tree with maximum total weight.
a) Present an efficient algorithm to find a Maximum Spanning Tree of an undirected
graph G. (8 pts)
b) Prove the correctness of your solution in part a. (8 pts)
第 3 ⻚，共 8 ⻚
3) 16 pts.
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. For example, if w
is the topmost choice of m and m is also the topmost choice of w, they must pair up in
every stable matching and thus, the claim is true in this case. 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.
第 4 ⻚，共 8 ⻚
4) 10 pts
Rank the following functions in order from smallest asymptotic complexity to largest. No
justification needed.
(lg is log base 2 by convention)
第 5 ⻚，共 8 ⻚
5) 16 pts
The Fractional Knapsack problem is described as follows. We have a resource (knapsack)
with capacity W, i.e. it can hold items of total weight at most W. There are n items, each
of weight w1, w2, . . . , wn. Each item also has a value v1, v2, . . . , vn. You are allowed to
put all or any fraction of an item (say, 1/3 of an item) into the knapsack. The goal is to
select a set of fractions p1, p2, . . . , pn for all items in order to maximize the total value
p1v1 + p2v2 + . . . pnvn subject to the capacity constraint p1w1 + p2w2 + . . . pnwn ≤ W.
a) Present an efficient solution to solve the Fractional Knapsack problem
b) Prove that the solution provided in part a is correct.
第 6 ⻚，共 8 ⻚
6) 10 pts
Below figure shows graph G along with its edge costs marked on each edge. Use
Dijkstra’s algorithm to find the shortest paths from node a to all nodes that can be
reached from a. You should list all shortest paths in the order they are found.
a
b
c
d
e
0
10
0
2
5
3
g
2
0
f
1
2 2
第 7 ⻚，共 8 ⻚
7) 12 pts
Given an array of n distinct integers sorted in ascending order, we are interested in
finding out if there is a Fixed Point in the array. Fixed Point in an array is an index i
such that arr[i] is equal to i. Note that integers in array can be negative.
Example:
Input: arr[] = {-10, -5, 0, 3, 7}
Output: 3 // since arr[3] == 3
a) Present an algorithm that returns a Fixed Point if there are any present in array,
else returns -1. Your algorithm should run in O(log n) in the worst case. (6 pts)
b) Use the Master Method to verify that your solutions to part a) runs in
O(log n) time. ( 3 pts)
c) Let’s say you have found a Fixed Point P. Provide an algorithm that determines
whether P is a unique Fixed Point. Your algorithm should run in O(1) in the worst
case. (3 pts)
第 8 ⻚，共 8 ⻚