1A. Let A be the adjacency matrix of an undirected graph. Defining each of the f

Question

1A. Let A be the adjacency matrix of an undirected graph. Defining each of the following explain what property of the matrix indicates that i) the graph is complete. i) the graph has a loop. ili) the graph has an isolated vertex 1B. The brute-force algorithm for computing the value of a polynomiat at a given point Xo is given below Algorithm Brute ForcePolynomial Evaluation(P[o.n).x) Input: Array P/o.n] of the coefficients of a polynomial of degree n, // stored from the lowest to the highest and a number Output: The value of the polynomial at the point x p-0.0 for i- n downto 0 do power 4-1 for j ? 1 to ido power ? power *x p ? p + P [i] * power returnp i) Analyse the efficiency of this algorithm considering multiplication as the basic operation ii) Design an algorithm with an efficiency better than this and prove it

Explanation / Answer

1.A. From the given adjacency matrix A of graph G we can conclude about the properties of G as follows:

(i) If each A[i][j] contains 1, then there exists edge from each vertex to each vertex and the graph is complete.

(ii) For any 1<=i<=n, ifA[i][i] contains a, then there is an edge from ith to same vertex, thus G has a loop

(iii) if there exists a column j in A such that all entries are 0, then there is no edge to jth, vertex, So there exists an isolated vertex.

1.B.

(i) In the given code the first for loop(variable i) iterates i times, and the for loop insede this iterates i times for each value of i.

Thus running time of this alcorithm =1+2+...+n=n(n+1)/2=O(n2)

(ii) We can improve the given algorithm to an O(n) time algorithm, The idea is in given algoritm we calculate xi in each iteration. But we can store value of xi-1 in previous iteration and by multiplying x to it we can get xi.

The algorithm is as follows:

1. p=0

2. power=1

3. for i=0 to n do

4. p=p+p[i]*power

5. power=power*x

6. return p

Here the for loop iterates n times, and each instruction in for loop executes once for each iteration, Thus running time of this algorithmis O(n).

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.