Solved-Assignment 1: Incremental Design- Solution

Description

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], nd 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, nd its position.

Naive algorithm generalising problem 1 will be O(nm2). Can you obtain a O(nm) algo-rithm?

3. (a) Two arrays A[1 p] and B[1 q] are strictly increasing.Find the number of com-mon 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) = anxn + + a1x + a0, then the derivative of A(x); A0(x) = nanxn 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) = anxn + + a0; p = n=2 and q = bn=2c. Then a variation of Horner’s rule states that

A(x) = ( (a2px2 + a2p 2)x2 + )x2 + a0 + (( (a2q 1×2 + a2q 3)x2 + )x2 + 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 coe cients 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 interpo-lating polynomial A(x) and its derivative at the same time. How e cient is your algorithm?

8. Given n points (xi; yi), our task is to nd the coe cients 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) = P1 i n Q (x x )
i6=j;1 j n j yi
(xi xj )
(a) Verify that A(x) satis es the n points.

(b) Analyse and prove that the naive algorithm for Lagrange interpolation takes O(n3) time.

(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 O(n2) 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 2 V is labeled with a unique integer L(u) from the set f1; 2; ::::; jV jg. For each vertex u 2 V , let R(u) = fv 2 V : u /vg be the set of vertices that are reachable from u. De ne 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 ) = minfL(w) : w 2 R(u)g. Give an O(V + E) time algorithm that computes min(u) for all vertices u 2 V .

12. Let P be a simple, but not necessarily convex, polygon and q an arbitrary point not necessarily in P. Design an e cient algorithm to nd 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 possible.

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 e cient 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 vec-tor. 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 e cient algorithm to compute the transitive closure of a given directed graph.

(b) Prove that a directed graph G has a unique transitive reduction if and only if G is acyclic.

(c) Describe an e cient algorithm to compute a transitive reduction of a given directed graph.

17. Suppose we are given a directed acyclic graph G with a unique source s and a unique sink t. A vertex v 2= 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 nd every (s,t)-cut vertex in G.

Figure 2: A directed acyclic graph with three (s,t)-cut vertices

Page 4