DSA Module-5 Quiz

What is the main idea behind the Decrease and Conquer strategy?

• The main idea is to solve a problem by dividing it into multiple smaller problems.

• The main idea is to solve a problem by reducing it to a smaller instance of the same problem.

• The main idea is to solve a problem by ignoring smaller instances of the same problem.

• The main idea is to solve a problem by combining solutions from unrelated problems.

Explain the difference between Depth First Search and Breadth First Search.

• DFS explores all neighbors before going deeper, while BFS goes deeper first.

• DFS uses a stack for exploration, while BFS uses a queue.

• DFS can only be implemented recursively, while BFS can only be implemented iteratively.

• BFS is faster than DFS in all scenarios.

What is the time complexity of Depth First Search in a graph?

• O(V)

• O(E)

• O(V * E)

• O(V + E)

How does Dynamic Programming differ from Divide and Conquer?

• Dynamic Programming uses recursion while Divide and Conquer does not.

• Both techniques solve problems in the same way, just with different names.

• Dynamic Programming focuses on overlapping subproblems and memoization, while Divide and Conquer deals with independent subproblems.

• Dynamic Programming is only applicable to sorting algorithms.

What is the formula for computing a Binomial Coefficient?

• C(n, k) = n! / (k! * (n + k)!)

• C(n, k) = (n + k)! / (n! * k!)

• C(n, k) = n! / (k! * n!)

• C(n, k) = n! / (k! * (n - k)!)

Describe the Greedy technique and its key characteristics.

• The Greedy technique is an algorithmic approach that makes the best choice at each step with the hope of finding the global optimum.

• The Greedy technique is a dynamic programming approach that considers previous decisions.

• The Greedy technique always guarantees the global optimum solution.

• The Greedy technique evaluates all possible solutions before making a choice.

What is Prim's algorithm used for in graph theory?

• To calculate the graph's diameter.

• To find the shortest path in a graph.

• To determine the connectivity of a graph.

• To find the minimum spanning tree of a graph.

How does the choice of data structure affect the performance of graph traversal algorithms?

• All data structures provide the same performance for graph traversal.

• Graph traversal algorithms do not depend on the underlying data structure.

• The choice of data structure has no impact on graph traversal algorithms.

• The choice of data structure affects the efficiency of graph traversal algorithms by influencing time complexity and memory usage.

Can you provide an example where a Greedy approach does not yield an optimal solution?

• Using coin denominations of 1, 3, and 4 to make change for 6.

• Using coin denominations of 1, 2, and 5 to make change for 7.

• Using coin denominations of 1, 2, and 3 to make change for 5.

• Using coin denominations of 2, 3, and 5 to make change for 10.

What are the advantages of using Dynamic Programming over simple recursion?

• Dynamic Programming is slower than simple recursion due to increased overhead.

• Dynamic Programming is more efficient than simple recursion due to reduced time complexity and avoidance of redundant calculations.

• Dynamic Programming is only useful for problems with no overlapping subproblems.

• Dynamic Programming requires more memory than simple recursion without any benefits.