DAA 4th Sem

The best-case complexity of an algorithm refers to:

• The time complexity under the least favorable conditions

• The time complexity under the most favorable conditions

• The average time complexity

• The time complexity for recursive algorithms

Which of the following is NOT a method used for solving recurrence relations?

• Substitution method

• Recursion tree method

• Master's theorem

• Divide and conquer method

In Big-O notation, the function O(n^2) represents:

• Constant time complexity

• Linear time complexity

• Quadratic time complexity

• Exponential time complexity

What is the primary characteristic of the Greedy algorithm?

• It always makes the optimal choice at every step

• It tries to explore all possibilities before making a choice

• It uses dynamic programming

• It avoids recursion

Which of the following is a common application of Dynamic Programming?

• Sorting an array of integers

• Solving problems like the Knapsack Problem

• Searching a tree

• Implementing graph algorithms

Which algorithmic technique is used in the Traveling Salesman Problem (TSP) to find the optimal solution by exploring all possible solutions?

• Dynamic Programming

• Brute-Force

• Greedy

• Backtracking

Depth First Search (DFS) is most useful for:

• Finding the shortest path between two nodes in a graph

• Traversing a tree or graph by visiting each node once

• Sorting elements in a graph

• Searching in a binary search tree

Which of the following is true for Breadth First Search (BFS)?

• It uses a stack for storing nodes

• It is faster than DFS for all graph types

• It explores all the nodes at the present depth level before moving on to nodes at the next depth level

• It does not find the shortest path in an unweighted graph

Dijkstra's Algorithm is used to find:

• Minimum spanning tree

• Shortest path in a weighted graph

• The path with the largest weight in a graph

• Transitive closure of a graph

In Prim’s Algorithm, what is the goal?

• To find the minimum spanning tree

• To find the shortest path between nodes

• To explore all the vertices in a graph

• To find the maximum weight edge