DAA Unit 4 Quiz

Choose the more appropriate options related to Convex Hull Problem.

• Computing the convex hull is a problem in computational geometry.

• A few of the applications of the convex hull are Collision avoidance.

• Convex hull is possibly a geometry that encloses the vertices of the input geometry

• A convex hull is the smallest convex polygon containing all the given points.

Which of the following is/are property/properties of a dynamic programming problem?

• a. Optimal substructure

• b. Overlapping subproblems

• c. Bound Function

• Option a & b

• Option a , b & c

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called

• Dynamic programming

• Greedy

• Divide and conquer

• Recursion

Which of the following problems is NOT solved using dynamic programming?

• 0/1 knapsack problem

• Matrix chain multiplication problem

• Fractional knapsack problem

• Maximum distance problem

Which data structure is used for implementing a FIFO branch and bound strategy?

• stack

• Queue

• Linked List

• Priority Queue

Which of the following can traverse the state space tree only in DFS manner?

• branch and bound

• dynamic programming

• greedy algorithm

• backtracking

Kruskal’s algorithm uses-------- and prim’s algorithm uses------ in determining the MST

• edges,vertex

• vertex,edges

• edges,edges

• vertex,vertex

From the following algorithm design techniques which one is used to find all the pairs of shortest distances in a graph?

• Backtracking

• Greedy

• Dynamic programming

• Divide and Conquer

Time complexity of Floyds algorithm is

• O(nlogn)

• O(n3)

• O(n2)

• O(2n)

For the branch and bound algorithm the efficiency mainly relies on

• Stack Data Structure

• Queue Data Structure

• Priority Data Structure

• Bound Function