DAA Quiz 4/ GLBITM

What is dynamic programming and how does it differ from other algorithmic approaches?

• Dynamic programming is a method for solving problems by breaking them into simpler subproblems and storing their results, differing from other approaches by avoiding redundant calculations.

• Dynamic programming is the same as greedy algorithms in all cases.

• Dynamic programming is a technique that only works for linear problems.

• Dynamic programming requires a complete enumeration of all possible solutions.

Explain the Floyd-Warshall algorithm and its time complexity.

• The Floyd-Warshall algorithm is used for sorting arrays.

• The time complexity of the Floyd-Warshall algorithm is O(V^2).

• The Floyd-Warshall algorithm only works for directed graphs.

• The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number of vertices in the graph.

How does backtracking work in solving puzzles like Sudoku?

• Backtracking only works for puzzles with a single solution.

• Backtracking eliminates all possible placements before starting the puzzle.

• Backtracking systematically explores possible placements of numbers in Sudoku, ensuring each placement adheres to the game's rules.

• Backtracking randomly places numbers without following any rules.

Describe the branch and bound technique and provide an example of its application.

• An example of branch and bound is the traveling salesman problem, where the algorithm explores different routes, calculates their costs, and prunes routes that exceed the current best cost.

• The branch and bound technique is only used for sorting algorithms.

• Branch and bound is a method for solving linear equations.

• An example of branch and bound is the binary search algorithm.

What are the main differences between Dijkstra's algorithm and the Floyd-Warshall algorithm?

• Dijkstra's algorithm is single-source shortest path; Floyd-Warshall is all-pairs shortest path.

• Dijkstra's algorithm can handle negative weights; Floyd-Warshall cannot.

• Dijkstra's algorithm uses dynamic programming; Floyd-Warshall uses greedy approach.

• Dijkstra's algorithm finds all pairs shortest paths; Floyd-Warshall finds single-source paths.

List and explain two common graph traversal methods.

• Binary Search (BS)

• Linear Search (LS)

• Depth-First Search (DFS) and Breadth-First Search (BFS)

• Random Walk (RW)

How can backtracking be used to find the sum of a subset?

• Backtracking can only be used for sorting elements in a list.

• Backtracking can find subsets that sum to a target value by recursively exploring inclusion/exclusion of elements.

• Backtracking can only be applied to linear data structures.

• Backtracking is a method for finding the maximum element in a set.

What is the 0/1 knapsack problem and how can it be solved using dynamic programming?

• The 0/1 knapsack problem does not involve any weight limits or item combinations.

• The 0/1 knapsack problem can be solved using dynamic programming by creating a table to store maximum values for each weight limit and item combination.

• Dynamic programming requires a recursive approach for the 0/1 knapsack problem.

• The 0/1 knapsack problem can only be solved using brute force methods.

Explain the graph coloring problem and its significance in scheduling.

• Graph coloring is used to enhance image quality in photography.

• The graph coloring problem is crucial in scheduling as it helps in resource allocation and conflict avoidance.

• The graph coloring problem is only relevant in computer graphics.

• The graph coloring problem is a method for sorting data in databases.

What is the n-queen problem and what strategies can be used to solve it?

• The n-queen problem involves solving a Sudoku puzzle.

• The n-queen problem involves placing n queens on an n x n chessboard without them threatening each other.

• The n-queen problem is about placing knights on a chessboard.

• The n-queen problem requires placing queens in a single row.