# UGCNET-Dec2015-III: 20

930 views

Floyd-Warshall algorithm utilizes _____ to solve the all-pairs shortest paths problem on a directed graph in ____ time

1. Greedy algorithm, $\theta(V^3)$
2. Greedy algorithm, $\theta(V^2 lgn)$
3. Dynamic programming, $\theta(V^3)$
4. Dynamic programming, $\theta(V^2 lgn)$

recategorized

Floyd-Warshall algorithm dynamic approch takes &Theta;(n^3) time.

## Related questions

1
2.4k views
Let $n=4$ and $(a_1, a_2, a_3, a_4)$=(do, if, int, while). Let $p(1:4)=\bigg (\dfrac{3}{8}, \dfrac{3}{8}, \dfrac{1}{8}, \dfrac{1}{8} \bigg)$ ... $q(i)$ denotes the probability with which we search $a_i$ and the identifier $x$ being searched satisfy $a_i < x < a_{i+1}$ respectively. The optimal search tree is given by:
The solution of the reccurence relation $T(n) \leq \begin{cases} \theta(1) & \text{ if } n \leq 80 \\ T\bigg(\dfrac{n}{s} \bigg)+T \bigg(\dfrac{7n}{10}+6\bigg)+O(n) & \text{ if } n> 80 \end{cases}$ is $O(\lg n)$ $O(n)$ $O(n \lg n)$ None of the above
If there are n integers to sort, each integer had d digits and each digit is in the set $\{1, 2, \dots, k\}$, radix sort can sort the numbers in $O(d \: n \: k)$ $O(d n^k)$ $O(d+n)k)$ $O(d(n+k))$
Given two sequences $X$ and $Y$: $X=\langle a, b, c, b, d, a, b \rangle$ $Y=\langle b, d, c, a, b, a \rangle$ The longest common subsequence of X and Y is: $\langle b, c, a \rangle$ $\langle c, a, b \rangle$ $\langle b, c, a, a \rangle$ $\langle b, c, b, a \rangle$