U.C. Berkeley — CS170 : Algorithms Final
Lecturers: Prasad Raghavendra and Satish Rao Dec 19, 2019
Final
Name: Targaryen
SID: 0123456789
Name and SID of student to your left: Lannister
Name and SID of student to your right: Stark
Exam Room:
RSF Fieldhouse Soda 405 Wozniak Lounge Other
Please color the checkbox completely. Do not just tick or cross the box.
Rules and Guidelines
• The exam is out of 194 points and will last 170 minutes. Roughly, one should expect to spend just
less than a minute for a point.
• Answer all questions. Read them carefully first. Not all parts of a problem are weighted equally.
• Write your student ID number in the indicated area on each page.
• Be precise and concise. Write in the solution box provided. You may use the blank page on the back
for scratch work, but it will not be graded. Box numerical final answers.
• The problems may not necessarily follow the order of increasing difficulty. Avoid getting stuck on a
problem.
• Any algorithm covered in lecture can be used as a blackbox. Algorithms from homework need to be
accompanied by a proof or justification as specified in the problem.
• Good luck!
Final P. Raghavendra & S. Rao
Discussion Section
Which of these do you consider to be your primary discussion section(s)? Feel free to choose multiple, or
to select the last option if you do not attend a section. Please color the checkbox completely. Do not just
tick or cross the boxes.
Arpita, Thursday 9 - 10 am, Dwinelle 223 Avni, Thursday 10 - 11 am, Dwinelle 215
Emaan, Thursday 10 am - 11 pm, Etcheverry 3107 Lynn, Thursday 11 am - 12 pm, Barrows 118
Dee, Thursday 11 am - 12 pm, Wheeler 30 Max, Thursday 12 - 1 pm, Wheeler 220
Sean, Thursday 1 - 2 pm, Etcheverry 3105 Neha, Thursday 2 - 3 pm, Dwinelle 242
Julia, Thursday 2 - 3 pm, Etcheverry 3105 Henry, Thursday 3 - 4 pm, Haviland 12
Kedar, Thursday 3 - 4 pm, Barrows 104 Ajay, Thursday 4-5 pm, Barrows 136
Varun, Thursday 4-5 pm, Dwinelle 242 Gillian, Friday 9 - 10 am, Dwinelle 79
Hermish, Friday 10 - 11 am, Evans 9 Vishnu, Friday 11 am - 12 pm, Wheeler 222
Carlo, Friday 11 am - 12 pm, Dwinelle 109 Tarun, Friday 12 - 1 pm, Hildebrand B56
Noah, Friday 12 - 1 pm, Hildebrand B51 Jiazheng, Friday 1 - 2 pm, Wheeler 30
Claire, Friday 2 - 3 pm, Barrows 155 Jialin, Friday 1 - 2 pm, Wheeler 30
Teddy, Friday 1 - 2 pm, Dwinelle 105 Jierui, Friday 2 - 3 pm, Wheeler 202
David, Friday 2 - 3 pm, Wheeler 130 Nate, Friday 2 - 3 pm, Evans 9
Rishi, Friday 3 - 4 pm, Dwinelle 243 Tiffany, Friday 3 - 4 pm, LeConte 385
Ida, Friday 3-4 pm, Dwinelle 109 Don’t attend section.
2
SID: Final P. Raghavendra & S. Rao
1 SCCs (10 points)
Execute a DFS on the directed graph shown below starting at node A and breaking ties alphabetically.
B
A J
C D E
F
G H
1. Fill in the table of pre and post values.
Node pre post
A
B
C
D
E
F
G
H
J
3
Final P. Raghavendra & S. Rao
B
A J
C D
E
F
G
H
J
Node pre post
A 1 12
B 2 9
C 4 5
D 6 7
E 13 18
F 10 11
G 3 8
H 14 17
J 15 16
4
SID: Final P. Raghavendra & S. Rao
2. In the DFS execution from above, mark the following edges as as T for Tree, F for Forward, B for Back
and C for Cross.
Edge Type
E→ G
C
C → B
B
A→ D
F
H → J
T
3. List the strongly connected components of the above graph in a linearized order. (Note that the
number of SCCs is possibly smaller than the number of rows provided in the table below)
SCC no. Vertices in the component
1
2
3
4
5
6
7
8
9
10
A BCG D EHJ F
5
Final P. Raghavendra & S. Rao
2 Runtime Analysis (5 points)
Consider the following snippet of code.
Function what(n) {
what(
√
n)
what(
√
n)
for k = 1 to n {
print BLAH
}
}
Write a recurrence relation for the runtime.
T(n) =
2T(
√
n) +O(n)
Write the tightest upper bound for runtime.
T(n) = O(n)
3 Linear-Time Selection for the Median (5 points)
Consider the execution of the linear-time selection algorithm to find the median element of the following
array:
1 3 5 7 9 2 4 6 8
1. What is the best possible value of the first pivot element (one that would make the algorithm terminate
the fastest)? 5
2. Give an example of the worst possible sequence of choices of pivot elements for finding median using
the algorithm (one that would make the algorithm terminate the slowest)?
1, 2, 3, 4, 9, 8, 7, 6, 5
3. What is best possible value of the first pivot if the input was the following array?
9 8 7 6 5 4 3 2 1
5
6
SID: Final P. Raghavendra & S. Rao
4 Post Values (4 points)
A part of a directed graph is shown below. There are other vertices and edges in the graph that are not
shown in the picture (but all edges between vertices A, B,C, D are shown).
A
B
C
D
Consider a DFS run on the entire graph. Indicate whether each of the following subsets of post-values is
possible or impossible.
Vertex v post[v]
A 22
B 100
C 64
D 36
Vertex v post[v]
A 22
B 36
C 64
D 100
Table 1 Table 2gpossible gpossibleg impossible g impossible
Solution:
The text of the question suggests that there are other vertices in the graph with incoming and outgoing
edges to this cycle. Both Table 1 and Table 2 are possible, as per the text of the question.
However, unfortunately, the picture is a little misleading in that all the arrows seems to be pointed away
from the cycle, with no dashed edges shown coming in. With this interpretation, Table 1 is possible, but
Table 2 is impossible.
For grading, we have given full credit to ”possible” for table 1 and either possible/impossible for table 2.
5 Floyd-Warshall algorithm (4 points)
Consider the following undirected graph G on vertices numbered {1, 2, 3, 4, 5, 6}, with edge lengths shown
below.
1 5 3 2 4 6
37 132 237 13 1237
Consider the execution of the Floyd-Warshall algorithm for all-pairs shortest paths on graph G. The dis-
7
Final P. Raghavendra & S. Rao
tance values between pairs of vertices converge to their true value as the algorithm executes. Order the
following distance values from the earliest to converge, to the last to converge.
d(1, 3), d(3, 6), d(4, 6), d(2, 5)
Assume that the Floyd-Warshall algorithm uses the same ordering of vertices as the given names of the
vertices.
First Second Third Fourth
d(4, 6) d(2, 5) d(3, 6) d(1, 3)
6 Unique MST (5 points)
Consider the undirected graph below with edge weights omitted. Suppose the dashed edges represent the
unique minimum spanning tree (MST) in the graph.
A
B
C
D
E
F
G
H
I
1. How many edges are necessarily heavier than the edge FE?
AD, BD,CE, FH, FI, all the other edges across the cut
2. How many edges are necessarily lighter than the edge DH? DE, EG,GH,
all the other edges along the cycle
3. Suppose k is the number of distinct edge weights in the graph, what is the smallest possible value of
k?
2
8
SID: Final P. Raghavendra & S. Rao
7 Min Cuts (4 points)
Assume that the capacity of every edge in the graph below is equal to 1. How many distinct minimum cuts
are there in the following graph with source S and sink T?
S
A
B
C
D
E
F
T
P
Q
Solution: Minimum cut value is 3, by cutting SA,SB,SC. Any minimum cut will have to cut one edge along
each path from S to T.
Along SBET, this gives 3 choices. Along the other two branches, there are two choices each – SC or FT and
SA or DT. So total number of minimum cuts is 3× 2× 2 = 12
9
Final P. Raghavendra & S. Rao
8 Kruskal and Prim’s Algorithm (5 points)
B A J
C D E
F G H
The ordering of the weights of the edges in the above graph is as follows.
AB < EH < AD = FG < GD < BC < CD = AE < CF < AC < EG < AJ < GH < JH
(Assume all ties between edge-lengths are broken alphabetically)
1. What are the first 4 edges that Kruskal’s algorithm includes in the tree? Write the edges in the order
they are included.
First edge Second edge Third edge Fourth edge
AB EH AD FG
2. What are the first 4 edges that Prim’s algorithm starting at A includes in the tree? Write the edges in
the order they are included.
First edge Second edge Third edge Fourth edge
AB AD GD FG
9 Two-Player Game (5 points)
There are n2 soldiers standing on a n× n-grid (in n rows of n soldiers each).
Pick the tallest soldier from each row and then the shortest among them, call him A. Alternately, pick the
shortest soldier from each column and then the tallest among them, call him B.
Which of the following statements are true? (If there are multiple true statements, mark all that are true.
5 points for marking all true statements, -3 for each false statement marked true. Negative points on this
question will apply to the exam total score.) (Hint: Is there a two-player game lurking beneath?)
© Depending on the heights of soldiers, A can be taller than B or vice versa.
© A is always at least as tall as B.
© B is always at least as tall as A.
© A and B are always the same height.
10
SID: Final P. Raghavendra & S. Rao
© A and B are always the same person.
Solution: Suppose H is the n× n matrix of heights of soldiers then,
height of A = min
i
(
max
j
H[i, j]
)
height of B = max
j
(
min
i
H[i, j]
)
This is just the values of the two player game with only pure strategies allowed for each player. In one case,
the min player goes first, and in other the min player goes second. The min player is at a disdavantage
when going first, so height of A ≥ height of B.
10 NP-completeness true/false (10 points)
For each of the following questions, there are four options:
(1) True (T); (2) False (F); (3) True if and only if P = NP; (4) True if and only if P 6= NP.
Circle one for each question.
Note: By “reduction” in this exam it is always meant “polynomial-time reduction with one call to the
problem being reduced to.”
If a statement is True or False without any assumptions on P and NP, pick that option over the other three.
1. Minimum Spanning Tree problem is not NP-complete hT hF hP = NP hP 6= NP
P 6= NP
2. CircuitSAT reduces to 3-SAT. hT hF hP = NP hP 6= NP
T
3. 3-SAT reduces to CircuitSAT. hT hF hP = NP hP 6= NP
T
4. Every NP problem reduces to integer programming. hT hF hP = NP hP 6= NP
T
11
Final P. Raghavendra & S. Rao
5. 3-SAT reduces to HornSAT. hT hF hP = NP hP 6= NP
P = NP
12
SID: Final P. Raghavendra & S. Rao
11 Buggy Distinct Elements (6 points)
The following code was intended to estimate the number of distinct elements in a stream of integers in the
range {1, . . . , n}. But the code is buggy.
h← a pairwise independent hash function from {1, . . . , n} → (0, 1)
1. s← first element of stream
2. α = h(s)
3. For each upcoming stream element r do
4. If (α < h(r)) α← h(r)
5. Return d1/αe.
1. What is the first line number for which the code behaves differently from the distinct elements algo-
rithm given in class?
4
2. Re-write only line 5 of the buggy code so that the estimate for the number of distinct elements is
correct. 1
(1−α) or
1
1−α − 1
Note: a slightly more accurate estimate is 1/α− 1. Recall that minhash maps the k elements into the
interval of length 1. Thus, the expected length of the first interval is 1k+1 , or E[α] =
1
k+1 . Solving this
for k, gives an estimate of k = 1α − 1. Either solution was fine.
13
Final P. Raghavendra & S. Rao
12 True/False (14 points)
1. Suppose all the capacities in a graph are even numbers then the value of Maximum Flow is an even
number.
hTrue hFalse True
2. Suppose all the capacities in a graph are odd numbers then the value of Maximum Flow is an odd
number
hTrue hFalse True
3. The knapsack problem can be approximated to a factor of 1+ 10−6 in polynomial time.hTrue hFalse
True
4. Let G = (V, E) be a graph with edge weights we for each edge e ∈ E, and a unique minimum spanning
tree T. Here the edge weights can be positive or negative. Suppose we change the edge weights to
w′e = w2e for each edge e ∈ E, then T is also a minimum spanning tree for the new weights w′e.
hTrue hFalse False
5. Let G = (V, E) be a graph with edge weights we for each edge e ∈ E, and a unique minimum spanning
tree T. Here the edge weights can be positive or negative. Suppose we change the edge weights to
w′e = 2we for each edge e ∈ E, then T is also a minimum spanning tree for the new weights w′e.
hTrue hFalse True
6. Consider a graph G all of whose edge weights are either positive integers or are equal to−1. Dijkstra’s
algorithm on G will always return the correct shortest path distances while updating each edge once.
hTrue hFalse
Solution: False. Consider that contains the a path of length k of negative edges, a source vertex with
an edge of length two to the begining of the path, and an edge of length 1 to the middle of the path,
then the labels of the last half of the path will be 0,−1, . . . and they should be 2− k/2− 1, 2− k/2−
2, . . .. Below is a figure for k = 4. The correct distances are above the vertices and the ones produced
by Dijkstra’s algorithm are below. A2 is labelled 0 or 2 depending on whether the implementation
allows for updates of visited vertices.
S A0 A1 A2 A3 A4
2 -1 -1 -1 -1
1
0 2 1 0 -1 -2
0 2 1 0 or 1 0 -1
14
SID: Final P. Raghavendra & S. Rao
7. Suppose a graph G with edge weights contains a cycle C, then the edge with the largest weight on C
cannot be in any minimum spanning tree.
hTrue hFalse
Solution: True or False.
True. Consider a tree T containing the heaviest edge e on cycle C. Removing the heaviest edge in T
produces two connected components in the graph with edges T − e. The cycle contains at least one
edge e′ 6= e between the two components as there is a path between the endpoints of e in the cycle
that does not use e. This edge is lighter than e′ and adding it produces a spanning tree of lower costs.
This contradicts the existence of T.
False. If there are ties, then the above argument is false.
15
Final P. Raghavendra & S. Rao
13 Fill in the Blanks (24 points)
When asked for a bound, always give the tightest bound possible. In particular,
if an exact bound is possible, then give it instead of an asymptotic bound. Some
questions have choices in parentheses after the answer box.
1. The node that receives the highest post (pre/post) number in a depth-first
search must lie in a source (source/sink) strongly connected component.
2. For a degree n− 1 polynomial p(x), its evaluation p(0) can be computed in time
from its coefficient representation. However, it takes time to compute
p(0) from its value representation given by (p(1), p(ω), . . . , p(ωn−1) where ω is a primitive nth root
of unity. (Assume n is a power of 2).
O(1),O(n log n)
3. Recall the linear programming relaxation for Vertex Cover problem. Suppose the optimal vertex cover
in a graph G is of size α, while the optimal solution to the LP relaxation has value β then,
× α ≤ β ≤ × α
.
1
2 , 1
4. Let h : {1, . . . , n} → {1, . . . , 1000} be a hash function chosen uniformly from a pairwise independent
hash familyH. Then for a pair i 6= j,
Pr[h(i) ≤ 300 and h(j) > 700] =
300/1000× 300/1000 = 0.09
5. Suppose an element occurs f times in a stream, then the count-min algorithm’s estimate for its fre-
quency is (write one of ≥ f or ≤ f or = f ).
≥ f
6. In union/find data structure of n items, if we use union by size without path compression then any
combination of m unions and/or find operations takes at most O(m log n)
time.
16
SID: Final P. Raghavendra & S. Rao
7. Recall that Dijkstra’s algorithm is run using a priority queue (whose implementation is a heap) where
one uses the operations DeleteMin which returns and deletes the minimum valued entry in the queue
and and DecreaseKey which decreases the value of the key for an item in the queue. Consider a graph
G with n vertices and m edges and non-negative edge weights.
(a) Give an asymptotic upper bound on the number of DeleteMin operations when Dijkstra’s algo-
rithm is run on G. O(n)
(b) Give an asymptotic upper bound on the number of DecreaseKey operations when Dijkstra’s
algorithm is run on G. O(m)
8. Any acyclic undirected graph with n vertices and exactly n− 1 edges is a
tree.
Solution: This is a definition of a tree, which we proved to be equivalent to others such as being
acyclic and connected.
9. What is the minimum number of connected components in an undirected graph with n vertices and
m edges?
max(1, n−m)
10. A vertex of the feasible region for a linear program with m constraints and n variables has at least
n tight constraints. (A constraint of the form a · x ≤ b is tight if a · x = b.)
11. For the Knapsack Problem without repetition for items with values v1, . . . , vn and weights w1, . . . ,wn,
where K(w, i) is the maximum value subset of the first i elements of weight w. The recurrence is
K(w, i) = max(K(w− wi, i− 1) + vi,K(w, i− 1) .
12. For the multiplicative weights algorithm with e > 0 on n experts whose losses in the range (0, 1] (each
expert always has a non-zero loss), the potential function which is the sum of the weights of all the ex-
perts is strictly decreasing . (Answer should be increasing or decreasing.))
17
Final P. Raghavendra & S. Rao
14 3-SAT for Powers of Two (8 points)
Prof. Bluffman has discovered an algorithm PowerSAT that solves 3-SAT instances in m clauses only when
m is a power of two, in time O(m3). Complete the following argument that Prof. Bluffman has proved
NP = P.
Proof: We use PowerSAT algorithm to solve the 3-SAT problem on all in-
stances. Since the 3-SAT problem is NP-complete,
this implies that NP = P.
Given an instanceΦ of 3− SAT problem, we construct an instanceΦ′ as fol-
lows,
We then run the PowerSAT algorithm on Φ′.
Let us suppose Φ has n clauses. Suppose 2k−1 < n ≤ 2k, add 2k − n clauses of the form xi ∨ yi ∨ zi
for i − 1, . . . , 2k − n, where the variables xi, yi, zi are entirely new variables. The resulting instance has a
number of clauses which is a power of two, and so we can run PowerSAT algorithm on it
18
SID: Final P. Raghavendra & S. Rao
15 Happiest Increasing Subsequence (15 points)
You are given an array of positive numbers a[1], . . . , a[n]. For an increasing subsequence of numbers, a[i1] <
a[i2] < · · · < a[it], its happiness score is given by
t
∑
`=1
` ∗ a[i`]
For example for the input a = [22, 44, 33, 66, 55], the increasing subsequence [22, 44, 55] has happiness score
(1) ∗ (22) + (2) ∗ (44) + (3) ∗ (55) = 275 while the increasing subsequence [22, 33, 55] has happiness score
(1) ∗ (22) + (2) ∗ (33) + (3) ∗ (55) = 253.
Devise a dynamic programming algorithm to compute the happiest increasing subsequence.
1. Subproblems
2. Recurrence Relation
3. Runtime
Solution:
1. L(i, `) is the happiest subsequence that ends at the i items and using the ith element for a subsequence
of length `.
19
Final P. Raghavendra & S. Rao
2. L(i, `) = maxj3. O(n3) since there are at most O(n2) entries and each entry take O(n) time to compute.
20
SID: Final P. Raghavendra & S. Rao
16 Weakest Link
The country of Snowland has n cities which are connected by a road network, specified by a graph G =
({1, . . . , n}, E).
Excessive snowfall often disrupts the edges in the network. Every edge (u, v) ∈ E has an associated strength
s[u, v] – a positive number. The strength of an edge indicates how much snowfall it can withstand.
For a path P in the graph, its strength s(P) is the minimum strength of an edge on the path P. (A path is only
as strong as the weakest edge on it).
For a pair of vertices i, j, let D[i, j] denote the strength of the strongest path from i to j. Formally,
D[i, j] = max
paths P from i to j
s(P)
1. (10 points) Recall the dynamic programming based algorithm for all-pairs shortest path (Floyd-Warshall
algorithm). We will (slightly) modify it to compute D[i, j] for all pairs of vertices i, j.
(a) The definition of subproblems d[i, j, k] is,
Solution: d[i, j, k] = strength of the strongest path from i to j that uses only vertices {1, . . . , k} as
intermediaries.
(b) The base cases are given by,
Solution:
d[i, j, 0] =
{
s(i, j) (i, j) ∈ E
−∞ otherwise
(c) The recurrence relation would be
Solution:
d[i, j, k] = max (min(d[i, k, k− 1], d[k, j, k− 1]), d[i, j, k− 1])
21
Final P. Raghavendra & S. Rao
22
SID: Final P. Raghavendra & S. Rao
2. (6 points) We will now modify Djikstra’s algorithm so as to compute strongest paths from a single
vertex. Here is the pseudocode for Djikstra’s algorithm on a graph G with edge lengths `[u, v].
procedure Djikstra(G, edge lengths `)
1 for i = 1 to n
2 dist[i] = ∞
3 prev[i] = null
4 dist[1] = 0
5 H =makequeue(V)
6 while H is not empty
7 u =deletemin(H).
8 for all edges (u, v) ∈ E
9 if dist[v] ≥ dist[u] + `[u, v]:
10 dist[v] = dist[u] + `[u, v]
11 prev(v) = u
12 decreasekey(H, v)
How would you modify the following line so as to compute strongest paths instead of shortest paths?
If (dist[v] ≥ dist[u] + `[u, v]): dist[v] = dist[u] + `[u, v]
Your modification will appropriately use s[u, v] – the strengths of roads in the graph G.
(Hint: the dist[u] values in the modified code do not need to exactly equal the strengths of the paths,
but prev pointers would yield the strongest path)
Solution: If (dist[v] ≥ max(dist[u], 1/s[u, v])) set dist[v] = max(dist[u], 1/s[u, v]).
To see why this works, first let us formally define the distance values.
dist[v] = max
paths P from 1 to v
(
min
edge e∈P
s(e)
)
23
Final P. Raghavendra & S. Rao
and the strongest path is nothing but
P∗ = arg max
paths P from 1 to v
(
min
edge e∈P
s(e)
)
Note that the above path can also be obtained as,
P∗ = arg min
paths P from 1 to v
(
max
edge e∈P
1
s(e)
)
(1)
To see this, observe that for every path
1
s(P)
= max
e∈P
1
s(e)
and that,
arg min
P
1
s(P)
= arg max
P
s(P)
Equation (1) expresses strongest path in manner similar to shortest paths. Recall that shortest paths are
given by,
P′ = arg min
paths P from 1 to v
 ∑
edge e∈P
`(e)

where `(e) is the length of the edge e. If we consider 1/s(e) to be the length of edge `(e) then only difference
between shortest paths and strongest paths now, is that ∑e∈P is replaced by maxe∈P. The modification in
the code changes the values of dist[v] so that they reflect maxe∈P instead of ∑e∈P.
24
SID: Final P. Raghavendra & S. Rao
17 NP-Completeness Reductions (10 points)
Show that the following problems are NP-complete by providing a polynomial-time reduction. You may
assume that the following problems are NP-complete: Rudrata (Hamiltonian) Path, Rudrata (Hamiltonian)
Cycle, Vertex Cover, Independent Set, 3-SAT and Integer Programming.
1. Far-Away Points
Input: Distances {d[i, j]} between n cities numbered {1, . . . , n} such that they satisfy the triangle
inequality:
d[i, j] + d[j, k] ≥ d[i, k] ∀i, j, k
and positive numbers k and D.
Solution: A set S of k cities that are at least D away from each other, i.e.,
d[i, j] ≥ D ∀i, j ∈ S
Proof. It is clear that Far-Away Points problem is in NP. Now we will use a polynomial time reduction to show
that the problem is indeed NP-complete.
Given an instanceΦ of the problem we will construct an instanceΨ of the problem
as follows.
The proof that this is a valid reduction is as follows:
25
Final P. Raghavendra & S. Rao
Solution: Given an instance Φ of the Independent Set problem we will construct an instance Ψ of the
problem FarAway points problem as follows.
Suppose the instance consists of Φ = ((V, E), size s), we will set d[i, j] to be the shortest path distance
between i and j in the unweighted undirected graph Φ.
Set k = s and D = 2.
By running all pairs shortest paths, one can construct Ψ from Φ in polynomial time. Since shortest
path distances satisfy the triangle inequality, our instance is a valid instance of Φ∗.
Suppose A ⊆ V is an independent set of size s, then for every pair of vertices i, j ∈ A, we will have
d[i, j] ≥ 2. So S = A yields a set of k = s points that are D = 2 away from each other.
Conversly, if the set S of k points are distance 2 away, then no pair of them are connected by an edge
in Φ. So A = S is an independent set of size k in Φ.
Alternatively, one can set d[i, j] = 1 when (i, j) ∈ E and d(i, j) ∈ [1, 2] for (i, j) 6∈ E. Other construc-
tions where d[i, j] = s for (i, j) ∈ E, and d[i, j] = 2s for (i, j) 6∈ E, and use D = 2s. This obeys the
triangle inequality and the previous argument works for arguing that a solution here corresponds to
an independent set solution.
26
SID: Final P. Raghavendra & S. Rao
18 Usage Logs (15 points)
A network router is monitoring login/logout requests to a social media platform. Each request that the
router observes is of the form below.
Request r{
• r.Time # a number in {1, . . . ,m} indicating the time (in minutes from start of the day)
at which request is received.
• r.Id # a number in {1, . . . , n} that is the identity of the user.
• r.Type # either LOGIN/LOGOUT indicating the type of the request.
}
The router is trying to estimate the average time spent by a user on the website using a streaming algorithm.
Assume that the stream of requests is a valid in that,
1. There is never a logout request for a user who is not currently logged in.
2. The system begins with no user logged in, and all the users logout by the end of the stream.
Note that the same user can have multiple login/logout sessions in the stream. Fill in the pseudocode on
the next page.
27
Final P. Raghavendra & S. Rao
1 h← a random hash function from {1, . . . , n} → (0, 1)
2 Define your variables here (indicate the type of each variable, and its initial value).
3 for each request r in stream do
4 if (r is a LOGIN request) {
5
6 }
7 if (r is a LOGOUT request) {
8
9 }
10 end For loop
11 Return
Solution: Here are three solutions to the problem.
Solution 1:
Estimate number of distinct users logging in using minHash algorithm, and compute the total time spent,
and then use the two to compute the average.
total = 0 : integer
minHashValue = 1 : real number in (0, 1)
1. If (r is a LOGIN request){
2. total = total − r.Time
28
SID: Final P. Raghavendra & S. Rao
3. minHash = min(minHash, h(r.Id))
4. }
5. If (r is a LOGOUT request){
6. total = total + r.Time
7. minHash = min(minHash, h(r.Id)) }
8. return minHash ∗ total
Solution 2:
Estimate number of distinct users logging in using minHash algorithm, and compute the total time spent
(in a different way than solution 1), and then use the two to compute the average. (solution assumes that
the time on the very first request is 0, one would have to slightly modify the initialization otherwise)
currentNumUsersLoggedIn = 0 : integer
previousUpdateTime = 0 : integer
totalTime = 0: integer
minHashValue = 1 : real number in (0, 1)
1. If (r is a LOGIN request){
2. total = (r.Time− previousUpdateTime) ∗ currentNumUsersLoggedIn
3. currentNumUsersLoggedIn++
4. previousUpdateTime = r.Time
5. minHash = min(minHash, h(r.Id))
6. }
7. If (r is a LOGOUT request){
8. total = (r.Time− previousUpdateTime) ∗ currentNumUsersLoggedIn
9. currentNumUsersLoggedIn−−
10. previousUpdateTime = r.Time
11. minHash = min(minHash, h(r.Id))
12. }
13. return minHash ∗ total
Solution 3
Here we sample a uniformly random user who has logged in using the minHash algorithm, and output the
total time spent by that user. The answer is equal to the average in expectation. Solution assumes no two
hash values are exactly equal, which is reasonable since the range is a real number in (0, 1), or in general a
large range.
29
Final P. Raghavendra & S. Rao
totalTimeOfMinHashUser = 0: integer
minHashValue= 1 : real number in (0, 1)
1. If (r is a LOGIN request){
2. if(h(r.Id) < minHashValue) then {
3. minHashValue = h(r.Id)
4. totalTimeO fMinHashUser = −r.Time.
5. }
6. if(h(r.Id) == minHashValue) then {
7. totalTimeOfMinHashUser = total - r.Time.
8. }
9. }
10. If (r is a LOGOUT request){
11. if(h(r.Id) == minHashValue) then {
12. totalTimeO fMinHashUser = total + r.Time
13. }
14. }
15. return totalTimeO fMinHashUser
30
SID: Final P. Raghavendra & S. Rao
19 Three-Tour (15 points)
Recall that a TSP tour is a cycle that visits all the vertices of a graph exactly once.
Analogously, a three-tour consists of three disjoint cycles C1,C2,C3 such that each vertex appears in exactly
one of the cycles exactly once. The cost of a 3-tour is the sum of the lengths of the edges on the three cycles.
(Here a single vertex is considered a cycle of length 1, so one or more of the cycles C1,C2,C3 can consist of
a single vertex.)
Suppose you are given a complete graph on n vertices with distances dist(·, ·) between pairs of vertices.
Assume that the distances satisfy the triangle inequality in that for each triple of vertices i, j, k,
dist(i, j) + dist(j, k) ≥ dist(i, k)
Describe a 2-approximation algorithm for the minimum cost three-tour problem. (Give a succinct but clear
description of your algorithm in at most four sentences)
We will now sketch a proof that the algorithm yields a 2-approximation to the Three-Tour problem (on next
page).
31
Final P. Raghavendra & S. Rao
Proof of approximation factor: We will split the proof into the following two claims.
Claim 1: Cost of the optimal Three-Tour is at least the cost of ..
Proof of Claim1: The claim holds because,
Claim 2: Cost of Three-Tour output by the algorithm is at most twice the cost of..
Proof of Claim 2: We will omit the proof of claim 2 here.
Solution: Compute the Minimum Spanning Tree (MST) and delete the two heaviest edges to recover a
forest with three trees T1, T2, T3. The rest of the algorithm is analogous to the TSP approximation algorithm,
but on three trees T1, T2, T3. In words, perform a DFS on each of the three trees T1, T2, T3 to obtain a traversal
Γ1, Γ2, Γ3. Shortcut the traversals to not have any vertex appearing more than once. This yields a Three-Tour
solution.
Claim 1: Cost of the optimal Three-Tour is at least the cost of the (Minimum spanning 3-forest), which is
the minimum cost graph that connects the vertices into three connected components.
Proof of Claim1: Take a 3-Tour consisting of cycles C1,C2,C3 and delete one edge from each cycle to get a
forest with three paths P1, P2, P3. The cost of the three cycles ≥ cost of three paths. Since the three paths is
a forest that connects the graph into three components, its cost is at least the cost of Minimum spanning 3
forest.
Claim 2: Cost of Three-Tour output by the algorithm is at most twice the cost of Minimum spanning 3
forest.
Proof of Claim 2: We will omit the proof of claim 2 here.
Remark: we only gave any credit when one computed the minimum spanning forest with three components
as above. Partial credit was only awarded if one got this far.
32
SID: Final P. Raghavendra & S. Rao
20 Multiplicative weights intuition.(10 points)
Recall that the multiplicative weights method starts with a weight wi of 1 for each expert i. Furthermore, on
a day where an expert i suffers a loss of `i, the weights are updated by multiplying the weight of an expert
by (1− e)`i if the loss for expert i is `i. The algorithm chooses an expert with probability proportional to wi
and suffers the loss of the chosen expert.
1. Consider a simple situation with two experts A and B where expert A loses 1/3 every day and expert
B loses 2/3 every day. If one runs the multiplicative weights framework on this situation, with e =
1/2.
(a) What is the weight of expert A on day d?
2−d/3
(b) What is the probability of choosing expert A on day d? 2
−d/3
2−2d/3+2−d/3
(c) How many days does it take so that one chooses expert A with probability at least .99?
Solution: Let d be the days, we want 2
−d/3
2−2d/3+2−d/3 ≥ .99.
We can set x = 2d/3, and obtain the equation xx2+x ≥ .99, or x ≥ .99(x2 + x).
Solving one get x = 2−d/3 ≥ 1/99, and then solving for d, we get d ≥ 3 log 99.
2. What if there are n+ 1 experts and the first expert loses 1/3 and all other experts lose 2/3 every day,
how many days does one need for the probability of choosing first expert to be least .99?
Solution:
The ratio is now 2
−d/3
n2−2d/3+2d/3 ≥ .99. Again, we substitute x = 2−d/3 into the equation getting x ≥
.99(nx2 + x) or x ≤ 199n .
Thus, we get d ≥ 3 log(99n) = 3(log 99+ log n).
Notice that the logarithm one pays for the number of experts, n, is only additive with the logarithm
that one pays to drive down the probability of choosing the wrong expert to .01.
33
Final P. Raghavendra & S. Rao
21 Linear Programming relaxation of Travelling Salesman (10 points)
For the Traveling Salesman problem, one is given a set of cities V = [1, . . . , n] and distances d(i, j) between
pairs of cities. A tour is a circular ordering of the cities.
Thus, we formulate an (integer) linear programming relaxation where a variable xi,j is 1 if the pair i, j are
adjacent in a tour and zero otherwise: in some sense these are the edges in the cycle that form a tour. Also,
we note that xi,j is unordered in that there is only one variable for xi,j and xj,i.
The linear program’s objective function is
min ∑
i,j∈V
d(i, j)xi,j
The notion that an edge cannot be used more than once can be enforced by equations of the form:
∀i, j ∈ V, xi,j ≤ 1.
We call these the packing constraints.
Also, notice for a tour, each vertex is incident to exactly 2 edges.
∀i∑
j
xi,j = 2
which we call the degree constraint.
Moreover, the number of edges between the two sides of a partition V = S ∪ S of the cities, must be at least
two as a tour should be connected and enter and leave any subset.
∀S ⊂ V, ∑
i∈S,j∈V−S
xi,j ≥ 2
These constraints are the subtour elimination constraints. And finally, we have that xi,j ≥ 0. for all i, j.
The dual linear program will have dual variables yi,j for each packing constraint for pair of vertices i, j, and
yi for each degree constraint for each vertex i, and yS for each subtour elimination constraint for each set
S ⊂ V. Write the dual linear program using these variables.
1. What is the objective function?
34
SID: Final P. Raghavendra & S. Rao
2. What are the constraints?
Solution:
max∑i∈V 2yi +∑S⊂V 2yS −∑i,j∈V yi,j
∀i, j ∈ V yi + yj − yi,j +∑S3i,V−S3j yS ≤ d(i, j)
yi,j ≥ 0
yi are unrestricted
35