Al Balqa Applied University



Question 2: Consider the powering number problem to solve the following: (5 marks)

a. Write the Standard algorithm and explain the running time for the powering number problem.

[pic]

b. Find the running time for divide- and- conquer algorithm for the powering number problem then solve it using the master method.

#include

Using namespace std;

int p(int x,int y)

{

if (y==1) return x;

if (y % 2 ==0)

return p(x,y/2)*p(x,y/2);

if (y %2 !=0)

return p(x,(y-1)/2) *p(x,(y-1)/2) * x;

}

main(){

int x=2;

int y=4;

cout array[i]) l = i; // Right half

}

return n; // Search value not in array

}

b. Find the running time (the recursive function) for the binary search problem and solve it by the master method.

□ T(n) = 2T(n/2) + Θ(n)

[pic]

Question 3 [6 marks]. Analysis the average-case for the quick-sort algorithm.

[pic]

[pic]

[pic]

[pic]

[pic]

Question 5. [8 marks] write a procedure to print out the vertices on a shortest path from s to v for some G(V,E), assuming that BFS has already been run .

□ compute the shortest-path tree.

□ PRINT-PATH( G, s, v)

□ 1 if v =s

□ 2 then print s

□ 3 else if π [v ] = NIL

□ 4 then print “no path from” s “to” v “exists”

□ 5 else PRINT-PATH( G, s,π[v ])

□ 6 print v

(a) Draw a directed graph, having as its eight vertices the strings ’ape’, ’ate’, ’eat’, ’era’, ’pea’,’rap’, ’rat’, and ’tea’, and including an edge from word x to word y whenever the last two letters of x are the same as the first two letters of y; for instance, you should include an edge from ’ape’ to ’pea’.

(b) Write down a sequence in which the vertices of this graph could be visited by breadth first search, starting from ’era’.

(c) Does this graph have a topological ordering? Explain why or why not.

(d) Draw an adjacency matrix representation of this graph.

(e) Draw an adjacency list representation of this graph.

[pic]

Good luck

-----------------------

nlogba= nlog21= n0= 1=f(n)=1 ⇒by CASE 2 for (k= 0)

⇒T(n) = Θ(lgn).

Ape6

Ate2

Eat 4

era0

Pea5

Rap7

1rat

Tea3

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download