Algorithms - 2nd Quiz
-
Time and Space complexities are the prime concerns to measure efficiency of algorithm.
-
True
-
False
-
About This Quiz
The 'Algorithms - 2nd Quiz' assesses understanding in graph theory, complexity theory, and algorithmic growth. It tests knowledge on Dijkstra's algorithm, big-O notation, and problem tractability, vital for students and professionals in computer science.
Quiz Preview
- 2.
Which of the following case does not exist in complexity theory?
-
Best Case
-
Worst Case
-
Null Case
-
Average case
Correct Answer
A. Null CaseExplanation
The null case does not exist in complexity theory. In complexity theory, we analyze the performance of algorithms based on different scenarios or inputs. The best case refers to the scenario where the algorithm performs optimally, while the worst case represents the scenario where the algorithm performs the worst. The average case considers the average performance of the algorithm across all possible inputs. However, the null case does not have a specific meaning in complexity theory, as it does not represent any particular scenario or input.Rate this question:
-
- 3.
Big-O notation is used to denote ______________
-
Reduction of functions
-
Growth of functions
-
None of the above
Correct Answer
A. Growth of functionsExplanation
Big-O notation is used to denote the growth of functions. It is a mathematical notation that describes the upper bound or worst-case scenario of the growth rate of a function. By using Big-O notation, we can analyze the efficiency and performance of algorithms and determine how they scale with input size. It helps in comparing different algorithms and choosing the most efficient one for a given problem.Rate this question:
-
- 4.
Worst case scenario for Mergesort is ----
-
O(n log(n))
-
O(n)
-
O(n^2)
Correct Answer
A. O(n log(n))Explanation
The worst case scenario for Mergesort is O(n log(n)). This means that the time complexity of Mergesort in the worst case is proportional to the product of the number of elements to be sorted (n) and the logarithm of that number (log(n)). In other words, as the number of elements to be sorted increases, the time it takes to sort them increases at a logarithmic rate. This makes Mergesort an efficient sorting algorithm, especially for large datasets.Rate this question:
-
- 5.
A problem that can be solved with polynomial worst-case complexity is called _____________.
-
Tractable
-
Unsolvable
-
Intractable
Correct Answer
A. TractableExplanation
A problem that can be solved with polynomial worst-case complexity is called tractable. This means that there exists an algorithm that can solve the problem efficiently, with a runtime that grows at most polynomially with the size of the input. In other words, the problem is manageable and can be solved in a reasonable amount of time, making it tractable.Rate this question:
-
- 6.
Time complexity refers algorithm's performance regarding space.
-
True
-
False
Correct Answer
A. FalseExplanation
The given statement is incorrect. Time complexity refers to the amount of time an algorithm takes to run, not its performance regarding space. Space complexity, on the other hand, refers to the amount of memory an algorithm requires to run. Therefore, the correct answer is False.Rate this question:
-
- 7.
Which one is not the properties of algorithm?
-
Correctness
-
Finiteness
-
Infiniteness
-
Generality
Correct Answer
A. InfinitenessExplanation
The property of "Infiniteness" does not apply to algorithms. Algorithms are step-by-step procedures that solve a specific problem within a finite number of steps. They have a clear and well-defined set of instructions, making them finite in nature. Infiniteness refers to the opposite, indicating an endless or infinite process, which is not a characteristic of algorithms.Rate this question:
-
- 8.
The following are the applications of Dijkstra Algorithm--
-
Routing
-
Shortest path finding
-
Traffic Optimization
-
All of the above
Correct Answer
A. All of the aboveExplanation
The Dijkstra Algorithm is a popular graph traversal algorithm that is used for finding the shortest path between two nodes in a graph. It can be applied to various applications such as routing, where it helps in finding the optimal path for data packets to reach their destination. It is also used for shortest path finding, where it helps in determining the most efficient route between two locations. Additionally, the algorithm can be utilized for traffic optimization, where it aids in minimizing congestion and improving overall traffic flow. Thus, all of the given applications are valid uses of the Dijkstra Algorithm.Rate this question:
-
- 9.
What is the running time of Dijkstra Algorithm?
-
O(|V|^4 + |E|)
-
O(|V|^2 + |E|)
-
None of the above
Correct Answer
A. O(|V|^2 + |E|)Explanation
The running time of Dijkstra's algorithm is O(|V|^2 + |E|), where |V| represents the number of vertices and |E| represents the number of edges in the graph. This is because the algorithm iterates through each vertex in the graph, performing operations that take O(|V|) time. Additionally, for each vertex, it explores its adjacent edges, which takes O(|E|) time. Therefore, the overall time complexity is O(|V|^2 + |E|).Rate this question:
-
- 10.
BFS and DFS follows _____________ and ________________ respectively.
-
LIFO and FILO
-
Push-Pop and Queue-Dequeue
-
FIFO and LIFO
-
None of the above
Correct Answer
A. FIFO and LIFOExplanation
BFS (Breadth First Search) follows FIFO (First In First Out) order, where the nodes are explored in the order they were added to the queue. On the other hand, DFS (Depth First Search) follows LIFO (Last In First Out) order, where the nodes are explored by going as deep as possible before backtracking.Rate this question:
-
- 11.
For snake game, we can use the following algorithms.
-
BFS
-
DFS
-
MST
-
All of the above
Correct Answer
A. All of the aboveExplanation
The correct answer is "all of the above" because all three algorithms (BFS, DFS, and MST) can be used for the snake game.
- Breadth-First Search (BFS) can be used to find the shortest path from the snake's current position to the food, ensuring that the snake takes the most direct route to its target.
- Depth-First Search (DFS) can be used to explore all possible paths the snake can take, allowing for more strategic decision-making and potentially finding alternative routes to the food.
- Minimum Spanning Tree (MST) algorithms can be used to create a connected graph of the game board, ensuring that the snake can reach any part of the board without getting trapped.Rate this question:
-
- 12.
Dijkstra's algorithm only can work for directed weighted graph.
-
True
-
False
Correct Answer
A. FalseExplanation
Dijkstra's algorithm can work for both directed and undirected weighted graphs. The algorithm finds the shortest path from a starting node to all other nodes in the graph, regardless of whether the graph is directed or undirected. The algorithm uses the weights of the edges to determine the shortest path, and it does not depend on the direction of the edges. Therefore, the statement that Dijkstra's algorithm only works for directed weighted graphs is false.Rate this question:
-
- 13.
Which one has the fastest growth?
-
N*n*n*
-
N!
-
Nlog(n)
Correct Answer
A. N!Explanation
The correct answer is n!. The factorial function (n!) has the fastest growth rate compared to the other options. As n increases, the value of n! increases at a much faster rate than n*n*n or nlog(n). This is because n! is calculated by multiplying all the positive integers from 1 to n, resulting in exponential growth. In contrast, n*n*n and nlog(n) have polynomial and logarithmic growth rates respectively, which are slower compared to the exponential growth of n!.Rate this question:
-
- 14.
Dijkstra's algorithm - is a solution to the _________________ shortest path problem in graph theory.
-
Multiple Source
-
Double Source
-
None of the above
Correct Answer
A. None of the aboveExplanation
Dijkstra's algorithm is a solution to the single-source shortest path problem in graph theory. It is used to find the shortest path between a single source vertex and all other vertices in a graph. The algorithm works by iteratively selecting the vertex with the smallest distance from the source and updating the distances of its adjacent vertices. This process continues until all vertices have been visited. Therefore, the correct answer is "None of the above" as neither "Multiple Source" nor "Double Source" accurately describe the problem that Dijkstra's algorithm solves.Rate this question:
-
Quiz Review Timeline (Updated): Mar 21, 2023 +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Mar 21, 2023Quiz Edited by
ProProfs Editorial Team -
Jul 24, 2013Quiz Created by
Hazen_ice