CSD 319 Design and Analysis of Algorithms

Final, Monsoon 2023- 24, Max 80, Time : 2.5 hrs

Name Roll No. Dept

Part A

1. Fill in the blanks or mark the correct answer - no explanation is required.

Negative 1 for incorrect answers to the Yes/No True/False questions.
( 4 × 10 )

(a) Consider the following recurrence that came from merging k sorted sequences each of length
n/k (2 ≤ k ≤ n) in a pairwise fashion

T (n, k) = T (n, k/2) + O(n) T (n, 1) = O(n)

Then the recurrence has solution T (n, k) = O(n log k)

(b) While constructing a skip list of size n suppose, we promote each element to the next level with
probability √1ni where ni is the number of elements in level i (the bottom level is i = 0). Then
the expected number of levels of skip list is O(log log n)
√
and the expected search time is O( n).
(c) We are given an undirected connected graph G with n nodes and the edges e ∈ E may have
negative weights w(e). Then

• We can compute the Minimum Spanning Tree (MST) using Kruskal’s algorithm (Yes ).
• Suppose every edge weight w(e) is multiplied by −6.2. Then the MST of the transformed
graph may be different from the original graph G. (Yes )
• Suppose every edge weight w(e) is squared to (w(e))2 . Then the MST of the transformed
graph may be different from the original graph G. (Yes)
(d) For which operation, the Binomial heap is preferred over the binary heap
(Find min / delete min / insertion / Merging two heaps ✓) - tick the right answer(s).
(e) Starting from an empty hash table of size m, we have a sequence of of T operations where each
operation is either search, insert, delete . The total number of (distinct) elements n involved in
the T operations 10m but T can be much larger than 10m, say m3 . If we are using universal
hash functions then the expected time for the entire sequence of T operations is O(T )
(f) If we use Rabin-Karp algorithm to find the first 1 ≤ k ≤ m − n + 1 matches of length n pattern
in m length text (m > n), then the expected time is O(n + k).
Further, if we wanted to guard against false positives by explicit verification, then we will need
O(nk) expected time.
(g) Given a set P of n points in the plane, where pi = (xi , x2i ) where xi > 0.
• Then the number of boundary points on the convex hull is O(n)
• The number of maximal points is one
(h) Consider the following modified knapsack problem, where the item i has weight w(i) but not
profits. We want to fill the knapsack of capacity B such that the residual capacity (B minus the
total weight) is minimized. For example, if B = 10 and w(1) = 4, w(2) = 8, w(3) = 7, w(4) = 5,
then we can choose items 1 and 4 and the residual capacity will be 10-9 = 1. Reduce this version
to the normal knapsack problem by defining some appropriate profit function prof it(i) = w(i)
 (i) We want to find the shortest path between all pairs of vertices comprising of at most 2 edges -
1 edge path is also fine. If there is no such path, then it is ∞. Consider the following procedure
to do this.
For each vertex v ∈ V , we consider the set of vertices w1 , w2 . . . wa that are in-coming neighbors
and the u1 , u2 . . . ub as the outgoing neighbors. The path ui , v, wj is a length two path between
ui and wj through v. Compute the minimum length Pi,j between ui and wj for all choices of
v ∈ V . Then output min{Pi,j , w(ui , vj )} where w() is weight of the edge.
• The running time of this procedure is O(n3 )
• Will the above algorithm compute the 2-edge shortest paths correctly ? (Yes)
(j) Let Π1 , Π2 be NPC problems and Π3 has a polynomial time algorithms. Then
• Π1 ≤poly Π2 (Yes )
• Π2 ≤poly Π1 (Yes )
• Π3 ≤poly Π1 (Yes)
• Π2 ≤poly Π3 (No) Comment : Not known is also acceptable

Part B
Note (i) An algorithm should be described in an English-like pseudo language. Do not write code.
(ii) You can quote any result covered in the lectures without proof but any other claim should be formally justified.
For any Dynamic Programming solution, you must begin with a clear recurrence - no credit otherwise.
2. We covered in the lectures that the 3-SAT problem is NP complete (NPC) and reduced 3-SAT to
Vertex cover (VC) to show that VC is also NPC. Consider the Independent set problem (IS), and
show that IS problem is also NPC by using the VC problem. Your answer must address the following
-
(i) Formal definitions of IS and VC problems.
IS : Given a graph G = (V, E) and and integer 1 ≤ k ≤ n, is there a subset W ⊂ V such that for all
x, y ∈ V , edge (x, y) ̸∈ E.
VC : Given a graph G = (V, E) and and integer 1 ≤ k ≤ n, is there a subset W ⊂ V such that for
all edges (x, y) ∈ E, {x, y} ∩ W ̸= ϕ.
(ii) The definition of NPC.
A decision problem Π is NPC iff the following hold - (i) Π ∈ N P (ii) For all Π1 ∈ N P Π1 ≤poly Π.
The class NP contains problems that are polynomial time verifiable.
(iii) The relation between the two problems by using reduction of one problem to the other. Recall
that reduction relation Π1 ≤ Π2 must satisfy certain condition for problems Π1 , Π2 . Clearly state
which problem is Π1 and which is Π2 when you do the reduction.
Hint: If an n vertex graph has a vertex cover of size k, then what does it imply about the size of an
independent set ?
Claim: For any graph G = (V, E), there is a vertex cover of size k iff there is an indepedent set of
size |V | − k.

Let W be a VC of size k, and let U = V − W . Then |U | = n − k where |V | = n. Clearly U is an IS

as for any x, y ∈ U (x, y) ̸∈ E ( otherwise W is not a VC.
The converse also holds, i.e., if U is an independent set, then W = V − U is a VC (otherwise some
x, y ∈ U will be an edge).
To show that IS is NPC, we must show that (i) IS ∈ N P and (ii) V C ≤poly IS.
For the first part, we can verify for any U ⊂ V that ∀x, y ∈ U , (x, y) ̸∈ E in at most O(n2 ) steps
(polynomial time verifiable).
For the second claim, given an input I = (V, E, k) of the VC problem, we create an instance I ′ =
(V, E, |V | − k) in polynomial time. From the previous claim it follows that I is true iff I ′ is true.
(2+2+6 )
3. Assume that your city map is available as a graph G = (V, E) and has McDonald outlets (denoted
by M ) marked out as some special vertices. For each vertex u ∈ V − M , we would like to find the
closest McDonald outlet N (u) as per the distances w : E → R+ given in the graph. Describe an
efficient algorithm that prints out all the N (u)’s.
You will receive full credits if your algorithm is close to O((|E| + |V |)). (10 )
This problem is easily solved by computing SSSP from each vertex u ∈ V and finding the nearest
Mcdonald (or alternately from APSP) - however this would take O(n3 ) steps where n = |V |.
Since distances are non-negative, we will apply Dijkstra’s SSSP algorithm from a new source s ̸∈ V
and add edges (s, x) to all vertices x ∈ M , i.e., a total of additional n edges. The weight (s, x) will
be set to 0.
Now we compute the SSSP from s and the print the distances to all vertex u inV − M as the distance
to the closest McDonald outlet for u. The shortest path subtree for each McDonald outlest also
contains the required information.
Correctness: Since the distance from s to each McDonald outlet is 0, the shortest path to each
u ∈ V M goes through the closest outlet (otherwise is contradicts the definition of the shortest path).
The running time is the same as Dijkstra’s i.e. O((|E| + n + |V | + 1) log |V |) where the number of
edges in |E| + n and number of vertices is |V | + 1 in the modified graph.
4. Given a set of integers S = {x1 , x2 . . . xn }, find out if there is a subset U ⊂ S such that xi ∈U xi = n2 .
P
For example, if S = {3, 9, 4, 6, 10}, then 9 + 6 + 10 = 25 = 52 . However for S ′ = {5, 2, 8} there is no
such subset that sums to 9.
Brute force algorithm will not earn any credits, i.e., trying all 2n subsets. Try to use dynamic
programming. (10 )
The solution is along the similar lines as the dynamic programming solution for Knapsack. Let S(i, j)
denote that there is a subset among x1 . . . xi that sums to j - these are boolean Yes/No entries. We
can write the following recurrence

S(i, j) = S(i − 1, j) ∨ S(i − 1, j − xj )

where the first term denotes that xj is not included and the second term denotes xj is included. The
symbol ∨ corresponds to logical OR.
Since we are only interested in S(n, n2 ), we will only need to fill up n2 columns, so the total time is
O(n3 ).
Note: If negative numbers are allowed then the number of columns may be more.
A direct reduction to Knapsack is possible by defining a profit function equal to the weight of the
elements and looking for toal profit = n2 . However this reduction has be precisely defined and not
ambiguously stated.
Common mistakes (i) Finding a pair of numbers that sum to n2 (instead of a subset)
(ii) Writing some tree based algorithm with back-tracking which doesn’t have a rigorous analysis.
(iii) Not writing any proper recurrence for DP based answer - no credits without that
(iv) Writing some code like answer without any clarity, justification or analysis. No credits given for
such attempts
5. Describe a divide and conquer based algorithm to compute the maximal points for a given set
S = {(x1 , y1 ), (x2 , y2 ) . . . (xn , yn )} that runs in O(n log n) time. Recall that a point is maximal, if
there is no other point dominating it.
The algorithm presented in the class based on scanning from right to left will not get any credits as
it is not divide-and-conquer. (10 )
This was discussed in class but the details of merge was not worked out. The overall algorithm is
(i) Divide the points into two equal sets N1 , N2 on the basis of x coordinates (by finding median).
The points in N1 has smaller x coordinates.
(ii) Recursively compute the maxima of the two sets S1 and S2 (the staircase). Denote them by S1
and S2 .
(iii) Merge the two staircases by extending the top-line ℓ of S2 left and deleting the part of S1 below
ℓ yielding the merged staircase.
This can be done easily in O(n) time and even in O(log n) time by binary search.
To analyse, we can write the recurrence as

T (n) = 2T (n/2) + O(n)

where O(n) captures the time for (i) (median finding to divide) and (iii) (merging the staircase).
This yields T (n) = O(n log n)
Altenately, the step (i) need not involve median finding and the two sets N1 , N2 may not be separable.
So the two staircases constructed recursively may be intertwined and merging would require more
careful processing that can still be done in linear time by a sweep method.

Common mistakes (i) Writing a solution for convex hull instead of maximal points - these are distinct
problems.
(ii) Just writing the generic divide-and-conquer without describing the merging step in details without
which one cannot analyse the algorith.
(iii) Writing solution for mergesort which is a 1-D problem.