Dynamic Programming and Backtracking Challenge

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

• O(n + W)

• O(n * W)

• O(W)

• O(n)

Explain the difference between the Floyd-Warshall algorithm and Dijkstra's algorithm for finding shortest paths.

• Dijkstra's algorithm finds paths for all vertices simultaneously.

• Floyd-Warshall only works for directed graphs.

• Floyd-Warshall finds shortest paths between all pairs of vertices; Dijkstra's finds shortest paths from a single source.

• Floyd-Warshall is faster than Dijkstra's algorithm.

In the context of the Resource Allocation Problem, what is the significance of the 'feasible region'?

• The feasible region is the area where no constraints are met.

• The feasible region defines the set of all possible resource allocations that meet the problem's constraints.

• The feasible region indicates the optimal solution to the problem.

• The feasible region represents the total amount of resources available.

Describe how backtracking can be used to solve the n-Queens problem.

• Backtracking randomly places queens until a solution is found.

• Backtracking can be used to systematically explore and place queens on the board while ensuring no two queens threaten each other.

• Backtracking eliminates all queens from the board after each placement attempt.

• Backtracking only works for even-numbered boards in the n-Queens problem.

What is the main idea behind the Branch and Bound technique?

• To randomly guess solutions without any structure.

• To focus solely on the best solution found so far.

• To create a single path to the solution without considering alternatives.

• To systematically explore and optimize solutions by dividing the problem and eliminating suboptimal solutions.

How does the Travelling Salesman Problem illustrate the challenges of combinatorial optimization?

• The TSP can be solved exactly using simple algorithms for all instances.

• The TSP illustrates the challenges of combinatorial optimization through its factorial growth in possible solutions, making exact solutions impractical for large instances.

• The TSP has a linear growth in possible solutions, making it easy to solve.

• The TSP is only relevant for small datasets and has no real-world applications.

What is the role of memoization in dynamic programming?

• Memoization helps optimize recursive algorithms by caching previously computed results.

• Memoization is used to eliminate the need for recursion.

• Memoization increases the time complexity of algorithms.

• Memoization is a technique for sorting data efficiently.

Explain how the Hamiltonian Cycle problem can be approached using backtracking.

• The problem can be approached by using a greedy algorithm to select the shortest edge at each step.

• The Hamiltonian Cycle can be solved by iterating through all possible vertex combinations without backtracking.

• The Hamiltonian Cycle problem can be approached using backtracking by recursively exploring paths, marking vertices as visited, and backtracking when necessary.

• The Hamiltonian Cycle problem can be solved using dynamic programming by storing all possible paths.

What are the key differences between dynamic programming and greedy algorithms?

• Dynamic programming uses overlapping subproblems and optimal substructure, while greedy algorithms make local optimal choices without considering future consequences.

• Dynamic programming always produces the best solution, while greedy algorithms can fail.

• Greedy algorithms use dynamic programming techniques to solve problems efficiently.

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

How can graph coloring be applied in scheduling problems?

• Graph coloring assigns colors to tasks based on their priority.

• Graph coloring helps in scheduling by assigning time slots to tasks while avoiding conflicts.

• Graph coloring helps in visualizing the relationships between tasks.

• Graph coloring is used to determine the optimal number of tasks.