WorksheetsDAA Quiz 4/ GLBITM
Total questions: 15
Worksheet time: 5mins
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.
How does dynamic programming optimize the solution to the 0/1 knapsack problem?
Dynamic programming eliminates the need for recursion in the 0/1 knapsack problem.
Dynamic programming increases the space complexity of the 0/1 knapsack problem significantly.
Dynamic programming solves the 0/1 knapsack problem using a greedy approach.
Dynamic programming reduces the time complexity of the 0/1 knapsack problem from exponential to polynomial by storing intermediate results.
What are the advantages of using the Floyd-Warshall algorithm over other shortest path algorithms?
Floyd-Warshall is faster than Dijkstra's algorithm for large graphs.
Floyd-Warshall finds shortest paths between all pairs of vertices and handles negative weights.
Floyd-Warshall only finds the shortest path from a single source.
Floyd-Warshall cannot handle graphs with cycles.
In what scenarios is backtracking preferred over other search techniques?
Backtracking is best when solutions cannot be incrementally validated.
Backtracking is preferred for problems with large solution spaces, constraint satisfaction, and when incremental solutions can be easily validated.
Backtracking is ideal for problems with no constraints.
Backtracking is preferred for problems with small solution spaces.
How can branch and bound be used to solve optimization problems?
Branch and bound is used to randomly select solutions without any pruning.
Branch and bound solves optimization problems by using a single solution approach.
Branch and bound relies solely on heuristic methods to find solutions.
Branch and bound can be used to solve optimization problems by systematically exploring and pruning the solution space to find the optimal solution.
What is the role of recursion in backtracking algorithms?
Recursion is only used for sorting algorithms.
Recursion enables exploration of all potential solutions and facilitates backtracking to previous states.
Backtracking algorithms do not use recursion at all.
Recursion limits the number of solutions explored.
