Advanced algorithms - 1st internal QB

Advanced Algorithms

1. Draw the graphic examples of Θ, O and Ω notations and give the definitions of each notation.
2. What are o(little oh) and ω(little omega) notations. Compare the Θ,O,Ω,o,ω notations.
3. Ordering by asymptotic growth rates

   lg(lg*n)	2lg*n	(√2)lgn	n2	n!	(lg n)!
   (3/2)n	n3	lg2n	lg(n!)	Pow(2,pow(2,n))	n1/lgn
   lnln n	lg*n	n.2n	nlglgn	lnn	1
   2lgn	(lgn)lgn	en	4lgn	(n+1)!	√lgn
   lg*(lgn)	2√2lgn	n	2n	nlgn	2↑(2↑(n+1))

4. Solve the recurrence relation T(n)=2T(└n/2┘)+n using ther substitution method.
5. Solve the recurrence relation T(n)=3T(└n/4┘)+Θ(n²) using the recursion tree method.
6. Give the masters theorem and find the asymptotically tight bounds for the following recurrences
   a) T(n)=4T(n/2)+n
   b) T(n)=4T(n/2)+n²
   c) T(n)=4T(n/2)+n³.
7. Give the bellman-ford algorithm and solve it for the following graph with s as the source node.

8. Give the algorithm for sungle-source-shortest-path in a directed acyclic graph and solve it for the following digraph.

9) Describe the Johnson's algorithm for sparce-graphs.