Design and Analysis of Algorithms MCQs with answers Page - 38

A

Admin • 833K Points
Coach

Q. Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.

• (A) true
• (B) false
• (C) ---
• (D) ---

Show Answer Discuss Share

Correct answer - Option (A)

Explanation:

consider the strings “abcd” and “efghi”. the string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. the cost of transformation is 5, which is equal to the length of the larger string.

A

Admin • 833K Points
Coach

Q. Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?

• (A) 3
• (B) 4
• (C) 5
• (D) 6

Show Answer Discuss Share

Correct answer - Option (B)

Explanation:

“monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. so, the edit distance is 4.

A

Admin • 833K Points
Coach

Q. Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?

• (A) 0
• (B) 4
• (C) 2
• (D) 3

Show Answer Discuss Share

Correct answer - Option (B)

Explanation:

the empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. thus, the edit distance is 4.

A

Admin • 833K Points
Coach

Q. What is the time complexity of the Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?

• (A) o(1)
• (B) o(n+m)
• (C) o(mn)
• (D) o(nlogm)

Show Answer Discuss Share

Correct answer - Option (C)

Explanation:

the time complexity of the wagner–fischer algorithm is o(mn).

A

Admin • 833K Points
Coach

Q. Which of the following is NOT a Catalan number?

• (A) 1
• (B) 5
• (C) 14
• (D) 43

Show Answer Discuss Share

Correct answer - Option (D)

Explanation:

catalan numbers are given by: (2n!)/((n+1)!n!).

A

Admin • 833K Points
Coach

Q. Which of the following methods can be used to find the nth Catalan number?

• (A) recursion
• (B) binomial coefficients
• (C) dynamic programming
• (D) recursion, binomial coefficients, dynamic programming

Show Answer Discuss Share

Correct answer - Option (D)

Explanation:

all of the mentioned methods can be used to find the nth catalan number.

A

Admin • 833K Points
Coach

Q. Which of the following implementations of Catalan numbers has the smallest time complexity?

• (A) dynamic programming
• (B) binomial coefficients
• (C) recursion
• (D) all have equal time complexity

Show Answer Discuss Share

Correct answer - Option (B)

Explanation:

The time complexities are as follows:
Dynamic programming: O(n2) Recursion: Exponential Binomial coefficients: O(n).

A

Admin • 833K Points
Coach

Q. Which of the following methods can be used to solve the assembly line scheduling problem?

• (A) recursion
• (B) brute force
• (C) dynamic programming
• (D) all of the mentioned

Show Answer Discuss Share

Correct answer - Option (D)

Explanation:

all of the above mentioned methods can be used to solve the assembly line scheduling problem.

A

Admin • 833K Points
Coach

Q. What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?

• (A) o(1)
• (B) o(n)
• (C) o(n2)
• (D) o(2n)

Show Answer Discuss Share

Correct answer - Option (D)

Explanation:

in the brute force algorithm, all the possible ways are calculated which are of the order of 2n.

A

Admin • 833K Points
Coach

Q. In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?

• (A) 0
• (B) 1
• (C) 2
• (D) 3

Show Answer Discuss Share

Correct answer - Option (C)

Explanation:

in the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the minimum time and the other for storing the assembly line number.

• Previous
• First
• 38
• 39
• 40
• 41
• 42
• Last
• Next

Jump to Go