What is the time complexity of the 0/1 Knapsack Problem using dynamic programming?

• O(n + W)

• O(W)

• O(n * W)

• O(n)

Explain the difference between the 0/1 Knapsack Problem and the Fractional Knapsack Problem.

• The 0/1 Knapsack Problem focuses on maximizing weight, while the Fractional Knapsack Problem focuses on minimizing weight.

• The 0/1 Knapsack Problem allows only whole items, while the Fractional Knapsack Problem allows fractions of items.

• The 0/1 Knapsack Problem is solved using dynamic programming, while the Fractional Knapsack Problem uses brute force.

• The 0/1 Knapsack Problem allows any number of items, while the Fractional Knapsack Problem allows only whole items.

How can backtracking be applied to solve the N-Queens Problem?

• Backtracking can be applied by placing queens row by row, checking for conflicts, and backtracking when necessary.

• Place all queens in the first row only.

• Use a random placement of queens without checking for conflicts.

• Only check for conflicts after all queens are placed.

What is the maximum number of queens that can be placed on an 8x8 chessboard without threatening each other?

• 7

• 9

• 6

• 8

Describe a dynamic programming approach to solve the Subset Sum Problem.

• Iterate through all possible subsets and check their sums recursively.

• Sort the set and use binary search to find the target sum.

• Use dynamic programming to create a table that tracks achievable sums with subsets of the given set.

• Use a greedy algorithm to select the largest elements until the sum is reached.

What is the relationship between the Subset Sum Problem and the Knapsack Problem?

• Both problems are unrelated and have different applications.

• The Subset Sum Problem can be solved in linear time while the Knapsack Problem cannot.

• The Knapsack Problem is a special case of the Subset Sum Problem.

• The Subset Sum Problem is a special case of the Knapsack Problem.

In string editing, what is the Levenshtein distance?

• The Levenshtein distance is the total number of characters in a string.

• The Levenshtein distance is the number of characters that are the same in both strings.

• The Levenshtein distance measures the length of the longest common substring.

• The Levenshtein distance is the minimum number of edits needed to transform one string into another.

How can dynamic programming be used to find the minimum edit distance between two strings?

• Count the number of matching characters without considering operations.

• Apply a greedy algorithm to select the best character match.

• Use a 2D table to compute the minimum edit distance based on character comparisons and operations (insertions, deletions, substitutions).

• Use a 1D array to store only the last row of calculations.

What is the purpose of graph coloring in algorithms?

• To ensure all vertices in a graph have the same color for uniformity.

• To create a visual representation of data without any constraints.

• To ensure that adjacent vertices in a graph have different colors, optimizing resource allocation and scheduling.

• To color the graph for aesthetic purposes.

How can backtracking be used to solve the Graph Coloring Problem?

• Backtracking eliminates all vertices that cannot be colored.

• Backtracking assigns random colors to vertices without checking adjacency.

• Backtracking is used to find the shortest path in a graph.

• Backtracking is used to recursively assign colors to vertices while ensuring no two adjacent vertices share the same color.