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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- analysis of fibonacci series cryptography
- fibonacci numbers and recurrences
- the fibonacci sequence
- divide and conquer strassen s algorithm fibonacci numbers
- risk control in algorithmic trading using
- exercises siue
- al balqa applied university
- database systems florida institute of technology
- design analysis of algorithms ucf computer science
- operating system lab record
Related searches
- gadsden al property taxes
- gadsden al news
- gadsden al school calendar
- cooper applied behavior analysis citation
- al state withholding
- cooper applied behavior analysis
- city of gadsden al revenue
- al department of education
- al dept of education
- cooper applied behavior analysis textbook
- applied behavior analysis 3rd edition
- applied behavior analysis cooper flashcards