ADVANCED DATA STRUCTURES & ALGORITHM ANALYSIS CT-5(1)

What is dynamic programming and how does it differ from divide and conquer?

• Both dynamic programming and divide and conquer solve problems in a similar way without any overlap.

• Dynamic programming solves overlapping subproblems with memoization, while divide and conquer solves non-overlapping subproblems independently.

• Dynamic programming is only applicable to sorting algorithms, while divide and conquer is used for searching.

• Dynamic programming uses recursion while divide and conquer uses iteration.

Explain the concept of the sum of subsets problem.

• The sum of subsets problem involves sorting a set into ascending order.

• The sum of subsets problem is about finding the largest element in a set.

• The sum of subsets problem focuses on counting the total number of elements in a set.

• The sum of subsets problem is about finding subsets of a set that sum to a specific target.

How can dynamic programming be applied to solve the 0/1 knapsack problem?

• Utilizing a simple linear array to track item weights without considering values.

• Using a greedy algorithm to select the highest value items first.

• Dynamic programming can be applied by creating a 2D array to store maximum values for each weight limit and item combination.

• Applying a depth-first search to explore all combinations of items.

What is the time complexity of the dynamic programming solution for the N Queen problem?

• O(N log N)

• O(N^2)

• O(N!)

• O(2^N)

Describe the backtracking approach in solving the N Queen problem.

• The backtracking approach randomly places queens on the board until a solution is found.

• The backtracking approach only checks the first row for valid queen placements.

• The backtracking approach systematically explores all possible configurations of queens on the board, ensuring no two queens threaten each other.

• The backtracking approach uses a greedy algorithm to place queens in the most optimal positions.

What are the key characteristics of a problem that can be solved using dynamic programming?

• Can be solved with brute force only

• Only requires a greedy approach

• No subproblems involved

• Key characteristics include overlapping subproblems and optimal substructure.

How does string editing relate to dynamic programming?

• String editing relates to dynamic programming through the use of algorithms that solve edit distance problems by breaking them into smaller, manageable subproblems.

• String editing is unrelated to dynamic programming.

• String editing algorithms do not use subproblems for solutions.

• Dynamic programming only applies to numerical problems, not string editing.

What is the purpose of graph coloring in algorithms?

• To create a uniform color scheme for aesthetic purposes.

• To assign the same color to all vertices for simplicity.

• To visualize the graph structure without any constraints.

• To ensure that adjacent vertices in a graph have different colors, facilitating efficient resource allocation and conflict resolution.

Explain how backtracking can be used to solve the sum of subsets problem.

• Backtracking can be used to explore all subsets of a set to find those that sum to a target value.

• Backtracking only finds the maximum subset sum.

• Backtracking is not applicable to the sum of subsets problem.

• Backtracking can only be used for sorting subsets.

What is the difference between a greedy algorithm and dynamic programming?

• Greedy algorithms always provide the optimal solution, while dynamic programming does not.

• Greedy algorithms focus on local optimization, while dynamic programming considers global optimization through subproblem solutions.

• Greedy algorithms solve problems in a single pass, while dynamic programming requires multiple passes.

• Dynamic programming is faster than greedy algorithms in all cases.