Font size
WorksheetsDAA 4th Sem
Total questions: 20
Worksheet time: 13mins
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
The Topological Sorting of a directed acyclic graph (DAG) results in:
A tree structure
A sorted list of vertices such that for every directed edge u→v, vertex u comes before v
A cyclic graph
A minimal spanning tree
The Ford-Fulkerson Algorithm is used for solving:
Minimum spanning tree
Network flow problems
Shortest path problems
Traveling salesman problems
In Backtracking, the process of moving back in the search tree is known as:
Exploring
Branching
Pruning
Backtracking
In the Knapsack Problem, if the items are divisible, which algorithm would be more efficient?
Greedy Algorithm
Dynamic Programming
Brute Force
Backtracking
The (a) algorithm design strategy makes the locally optimal choice at each stage with the hope of finding the global optimum.
The (a) method for solving recurrences involves drawing a tree-like diagram to visualize the recurrence’s computation at each level.
The (a) algorithm is commonly used to find the shortest path in a graph when all edges have non-negative weights.
The (a) problem is an example of an NP-hard problem that can be solved using dynamic programming to find the optimal solution efficiently.
(a) search is a graph traversal technique where we visit all the vertices of a graph level by level, starting from the source vertex.
In a DFS (Depth First Search) traversal of a graph, we use which data structure?
Queue
Stack
Array
Priority Queue
