Test: Algorithms - Computer Science Engineering (CSE) MCQ

Prim’s Minimum Spanning Tree is a Greedy Algorithm. All other are dynamic programming based.

The order of growth of option c is n^2.5 which is higher than n².

This is an implementation of Euclid’s algorithm to find GCD

Floyd–Warshall algorithm uses three nested loops to calculate all pair shortest path. So, time complexity is θ(n^3).

//The LCS is of length 4. There are 3 LCS of length 4 “qprr”, “pqrr” and qpqr

A subsequence is a sequence that can be derived from another sequence by selecting zero or more elements from it, without changing the order of the remaining elements.
Subsequence need not be contiguous.
Since the length of given strings A = “qpqrr” and B = “pqprqrp” are very small, we don’t need to build a 5×7 matrix and solve it using dynamic programming.
Rather we can solve it manually just by brute force.
We will first check whether there exist a subsequence  of length 5 since min_length(A,B) = 5.

Since there is no subsequence , we will now check for length 4. “qprr”, “pqrr” and “qpqr” are common in both strings.

X = 4 and Y = 3

X + 10Y = 34

The problem of finding whether there exist a Hamiltonian Cycle or not is NP Hard and NP Complete Both.

Finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 is also NP Hard.

Problem 1 is Hamiltonian Cycle problem which is a famous NP Complete problem.

Problem 2 is Euler Circuit problem which is solvable in Polynomial time.

Radix sort time complexity = O(wn)
for n keys of word size= w
=>w = log(n^k)
O(wn)=O(klogn.n)
=> kO(nlogn)

Knight tour problem, N Queen problem and M coloring problem involve backtracking. Tower of hanoi uses simple recursion.

 In a queue, the items are inserted from the rear end and deleted from the front end.