Match the following:

List 1

(P) Prim’s algorithm for minimum spanning tree
(Q) Floyd-Warshall algorithm for all pairs shortest paths
(R) Mergesort
(S) Hamiltonian circuit

List 2

(i) Backtracking
(ii) Greedy method
(iii) Dynamic programming
(iv) Divide and conquer

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n−1] is given below.

Let L_i, denote the length of the longest monotonically increasing sequence starting at index i in the array. Initialize L_n−1=1.

For all i such that $$0 \leq i \leq n-2$$

$$L_i = \begin{cases} 1+ L_{i+1} & \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases}$$

Finally, the length of the longest monotonically increasing sequence is max(L₀, L₁,…,L_n−1)
Which of the following statements is TRUE?

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?