CS2800 Assignment 1: Incremental Design solved




1. (a) Given that there is a number present in all the three sorted arrays x[1] ≤ · · · ≤
x[p], y[1] ≤ · · · ≤ y[q], z[1] ≤ · · · ≤ z[r],find it (atleast one of them if there are many
common elements) in O(p + q + r) time.
(b) Suppose we do not know in advance that such a common element exists. Determine
whether or not it exists and locate it(atleast one) when it does.
2. Generalisation : Given a matrix A[1 · · · n][1 · · · m] where each row is sorted and there is
an element common in all rows, find its position.
Naive algorithm generalising problem 1 will be O(nm2
). Can you obtain a O(nm) algorithm?
3. (a) Two arrays A[1 · · · p] and B[1 · · · q] are strictly increasing.Find the number of common elements in both. That is number of t such that t = A[i] = B[j] for some i, j.
(b) How is the solution altered if A[1] ≤ A[2] ≤ · · · ≤ A[p] and B[1] ≤ B[2] ≤ · · · ≤ B[q],
that is, the arrays are non-decreasing rather that strictly increasing.
4. If A(x) = anx
n + · · · + a1x + a0, then the derivative of A(x), A0
(x) = nanx
n−1 + · · · + a1.
Devise an algorithm which produces the value of a polynomial and its derivative at a point
x = v. Determine the number of required arithmetic operations.
5. Let A(x) = anx
n + · · · + a0, p = n/2 and q = bn/2c. Then a variation of Horner’s rule
states that
A(x) = (· · ·(a2px
2 + a2p−2)x
2 + · · ·)x
2 + a0 + ((· · ·(a2q−1x
2 + a2q−3)x
2 + · · ·)x
2 + a1)x
Show how to use this formula to evaluate A(x) at x = v and x = −v.
6. Given the polynomial A(x) as above in problem 5, devise an algorithm which computes
the coefficients of the polynomial A(x + c) for some constant c.
7. Given n points (xi
, yi), 1 ≤ i ≤ n, devise an algorithm which computes both the interpolating polynomial A(x) and its derivative at the same time. How efficient is your algorithm?
8. Given n points (xi
, yi), our task is to find the coefficients of the unique polynomial A(x)
of degree ≤ n − 1 which goes through these n points. Mathematically the answer to this
problem was given by Lagrange
A(x) = P
(x−xj )
(xi−xj )ffl 
(a) Verify that A(x) satisfies the n points.
(b) Analyse and prove that the naive algorithm for Lagrange interpolation takes O(n
(c) Let Gj−1(x) interpolate j − 1 points (xk, yk)1 ≤ k ≤ j such that Gj−1(xk) = yk. Also
let Dj−1(x) = (x − x1)· · ·(x − xj−1). Then we can compute Gj (x) by the formula
Gj (x) = (yj − Gj−1(xj ))(Dj−1(x)/Dj−1(xj )) + Gj−1(x)
Using this formula, the algorithm for computing the interpolating polynomial takes
) time . Verify and prove the same.
9. A group of n persons have an independent information for gossip known only to himself.
Whenever a person calls another person in the group, they exchange all the gossip information
they know at that time of calling. What is the minimum number of calls they have to make
in order to ensure that everyone of them knows all the information.
10. Give a linear-time algorithm that takes as input a directed acyclic graph G = (V, E) and
two vertices s and t, and returns the number of simple paths from s to t in G. For example,
the directed acyclic graph of Figure 1 contains exactly four simple paths from vertex p to
vertex v: pov, poryv, posryv and psryv. (Your algorithm needs only to count the simple
paths, not list them.)
Page 2
Figure 1: A DAG
11. Let G = (V,E) be a directed graph in which each vertex u ∈ V is labeled with a unique
integer L(u) from the set {1, 2, …., |V |}. For each vertex u ∈ V , let R(u) = {v ∈ V : u / v}
be the set of vertices that are reachable from u. Define min(u) to be the vertex in R(u) whose
label is minimum, i.e., min(u) is the vertex v such that L(v) = min{L(w) : w ∈ R(u)}. Give
an O(V + E) time algorithm that computes min(u) for all vertices u ∈ V .
12. Let P be a simple, but not necessarily convex, polygon and q an arbitrary point not
necessarily in P. Design an efficient algorithm to find a line segment originating from q that
intersects the maximum number of edges of P. In other words, if standing at point q, in what
direction should you aim a gun so the bullet will go through the largest number of walls.
A bullet through a vertex of P gets credit for only one wall. An O(n log n) algorithm is
13. Consider an n × n array A containing integer elements (positive, negative, and zero).
Assume that the elements in each row of A are in strictly increasing order, and the elements
of each column of A are in strictly decreasing order. (Hence there cannot be two zeroes in
the same row or the same column.) Describe an efficient algorithm that counts the number
of occurrences of the element 0 in A. Analyze its running time.
14. Design an incremental algorithm that constructs a permutation given it’s inversion vector. What is the complexity of your algorithm? Can you design an O(nlogn) solution for
the same?
Page 3
15. (a) Let n=2k
-1, k≥1. Find out exact number of comparisons done to build heap
i. in a top-down fashion.
ii. in a bottom-up fashion.
(b) Show that if heapsort is performed after building the heap in bottom up fashion, it’s
complexity is 2nlog(n+1)-2n (for n=2k
-1, k≥1). Construct an input that makes this
many comparisons (building worst case examples).
16. The transitive closure Gt of a directed graph G is a directed graph with the same
vertices as G, that contains any edge u → v if and only if there is a directed path from u to
v in G. A transitive reduction of G is a graph with the smallest possible number of edges
whose transitive closure is GT
.The same graph may have several transitive reductions.
(a) Describe an efficient algorithm to compute the transitive closure of a given directed
(b) Prove that a directed graph G has a unique transitive reduction if and only if G is
(c) Describe an efficient algorithm to compute a transitive reduction of a given directed
17. Suppose we are given a directed acyclic graph G with a unique source s and a unique
sink t. A vertex v ∈/ s,t is called an (s,t)-cut vertex if every path from s to t passes
through v, or equivalently, if deleting v makes t unreachable from s. Describe and analyze
an algorithm to find every (s,t)-cut vertex in G.
Figure 2: A directed acyclic graph with three (s,t)-cut vertices
Page 4