Cp QUIZ

In backtracking, what is pruning?

• 1. Trimming unwanted branches in the search space.

• 1. The process of selecting the best solution

• reversing the steps taken

• 1. The process of finding the optimal solution.

What is the key feature of a problem that makes it suitable for a backtracking solution?

• 1. The problem has overlapping subproblems.

• 1. The problem has an optimal substructure.

• 1. The problem can be divided into smaller independent subproblems.

• 1. The problem exhibits a recursive structure and can be solved by trying out different possibilities.

The first step in the naïve greedy algorithm is?

• adding flows with higher values

• reversing flow if required

• analysing the zero flow

• calculating the maximum flow using trial and error

Which of the following algorithms is the best approach for solving Huffman codes?

• greedy algorithm

• exhaustive search

• divide and conquer algorithm

• brute force algorithm

Which bit is reserved as a parity bit in an ASCII set?

• first

• seventh

• eighth

• tenth

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

• Optimal substructure

• Overlapping subproblems

• Greedy approach

• Both optimal substructure and overlapping subproblems

In dynamic programming, the technique of storing the previously calculated values is called ___________

• Saving value property

• Storing value property

• Memoization

• Mapping

Which of the following problems should be solved using dynamic programming?

• Mergesort

• Binary search

• Longest common subsequence

• Quicksort

If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.

• Overlapping subproblems

• Optimal substructure

• Memoization

• Greedy

When a top-down approach of dynamic programming is applied to a problem, it usually _____________

• Decreases both, the time complexity and the space complexity

• Decreases the time complexity and increases the space complexity

• Increases the time complexity and decreases the space complexity

• Increases both, the time complexity and the space complexity