Analysis of Algorithms Quiz

Which of the following standard algorithms is not Dynamic Programming based.

• Bellman–Ford Algorithm for single source shortest path

• Floyd Warshall Algorithm for all pairs shortest paths

• 0-1 Knapsack problem

• Prim's Minimum Spanning Tree

We use dynamic programming approach when

• We need an optimal solution

• The solution has optimal substructure

• The given problem can be reduced to the 3-SAT problem

• It's faster than Greedy

Which of the following standard algorithms is not a Greedy algorithm?

• Dijkstra's shortest path algorithm

• Prim's algorithm

• Huffman Coding

• Bellmen Ford Shortest path algorithm

Consider the following two sequences :

The length of longest common subsequence of X and Y is :Consider the following two sequences :

X = < B, C, D, C, A, B, C >, and Y = < C, A, D, B, C, B >

The length of longest common subsequence of X and Y is :

• 5

• 3

• 4

• 2

The following paradigm can be used to find the solution of the problem in minimum time: Given a set of non-negative integer, and a value K, determine if there is a subset of the given set with sum equal to K:

• Divide and Conquer

• Dynamic Programming

• Greedy Algorithm

• Branch and Bound

What happens when a top-down approach of dynamic programming is applied to any problem?

• It increases both, the time complexity and the space complexity

• It increases the space complexity and decreases the time complexity.

• It increases the time complexity and decreases the space complexity

• It decreases both, the time complexity and the space complexity

Consider a job scheduling problem with 4 jobs J₁, J₂, J₃, J₄ and with corresponding deadlines: ( d₁, d₂, d₃, d₄) = (4, 2, 4, 2). Which of the following is not a feasible schedule without violating any job schedule?

• J₂, J₄, J₁, J₃

• J₄, J₁, J₂, J₃

• J₄, J₂, J₁, J₃

• J₄, J₂, J₃, J₁

What is the other name of Dijkstra algorithm?

• single-source shortest path problem

• multiple-source shortest path problem

• multiple-destination shortest path problem

• single-destination shortest path problem

What is the difference between 0/1 Knapsack problem and knapsack problem by greedy

• In 0/1 knapsack problem we can not put some portion of object into the knapsack

• In knapsack problem by greedy approach we can put some portion of object also in the knapsack

• 0/1 knapsack is example of dynamic programming

• All three options are correct

In travelling salesman problem, we are interested in finding

• shortest path from one source to multiple destinations

• A salesman is expected to start from one source and by visiting all locations he/she should come back to the source in minimum time

• longest available path in the graph

• A Salesman is expected to complete the task in given deadline