What is a greedy algorithm?
Group of answer choices
An algorithm that always finds the globally optimal solution
An algorithm that solves all problems in linear time
An algorithm that makes the locally optimal choice at each stage
An algorithm that uses recursion to solve problems
An algorithm that makes the locally optimal choice at each stage
Which of the following is NOT a component of a greedy algorithm?
Group of answer choices
A randomization function
A candidate set
A feasibility function
A selection function
A randomization function
What is the main advantage of using a greedy algorithm?
Group of answer choices
It has no disadvantages
It works for all types of problems
It is easy to implement and analyze
It always guarantees the optimal solution
It is easy to implement and analyze
What is the main advantage of using a greedy algorithm?
Group of answer choices
It has no disadvantages
It works for all types of problems
It is easy to implement and analyze
It always guarantees the optimal solution
It is easy to implement and analyze
Which algorithm is used to find the Minimum Spanning Tree (MST) of a graph?
Group of answer choices
Merge Sort Algorithm
Binary Search Algorithm
Prim’s Algorithm
Dijkstra’s Algorithm
Prim’s Algorithm
What is the time complexity of Prim’s Algorithm when using an adjacency matrix?
Group of answer choices
O(V²)
O(V log E)
O(E²)
O(E log V)
O(V²)
What is the purpose of Kruskal’s Algorithm?
Group of answer choices
To sort edges in ascending order
To find the Minimum Spanning Tree (MST) of a graph
To detect cycles in a graph
To find the shortest path in a graph
To find the Minimum Spanning Tree (MST) of a graph
What is the time complexity of Kruskal’s Algorithm?
Group of answer choices
O(E²)
O(E log E)
O(V log V)
O(V²)
O(E log E)
Which algorithm is used to find the shortest path from a single source node to all other nodes in a graph?
Group of answer choices
Kruskal’s Algorithm
Dijkstra’s Algorithm
Floyd-Warshall Algorithm
Prim’s Algorithm
Dijkstra’s Algorithm
Who invented Dijkstra’s Algorithm?
Group of answer choices
Edsger W. Dijkstra
Vojtech Jarnik
Robert C. Prim
Joseph Kruskal
Edsger W. Dijkstra
What does Dijkstra’s Algorithm use to determine the shortest path?
Group of answer choices
Breadth-First Search
Greedy approach with edge weights
Depth-First Search
Dynamic Programming
Greedy approach with edge weights
What is a Minimum Spanning Tree (MST)?
Group of answer choices
A tree that only connects two vertices
A tree that connects all vertices with the minimum total edge weight
A tree that includes cycles
A tree that contains all the edges of a graph
A tree that connects all vertices with the minimum total edge weight
Which of the following is NOT an application of Minimum Spanning Trees?
Group of answer choices
Sorting algorithms
Real-time face tracking
Cluster analysis
Network design
Sorting algorithms
In Kruskal’s Algorithm, how are edges processed?
Group of answer choices
In ascending order of weight
Based on the degree of vertices
Randomly
In descending order of weight
In ascending order of weight
In Prim’s Algorithm, how is the next edge selected?
Group of answer choices
The edge with the lowest weight connecting a vertex in the tree to a vertex outside
The first edge in the sorted list
The edge with the highest weight
Any random edge
The edge with the lowest weight connecting a vertex in the tree to a vertex outside
What is the main disadvantage of Prim’s Algorithm?
Group of answer choices
It always produces incorrect results
It is too slow for small graphs
It cannot handle disconnected graphs
It requires searching the list of edges repeatedly
What happens if adding an edge in Kruskal’s Algorithm forms a cycle?
Group of answer choices
The edge is added anyway
The graph is considered invalid
The edge is discarded
The algorithm stops
The edge is discarded
What is the initial step in Dijkstra’s Algorithm?
Group of answer choices
Assign maximum distance to all vertices
Mark all vertices as visited
Assign zero distance to the source vertex
Sort all edges by weight
Assign maximum distance to all vertices
What data structure is commonly used in Dijkstra’s Algorithm to improve efficiency?
Group of answer choices
Priority Queue
Stack
Linked List
Array
Priority Queue
Which of the following is TRUE about greedy algorithms?
Group of answer choices
They require dynamic programming to work
They may yield locally optimal solutions that approximate a globally optimal solution
They are only used for sorting problems
They always guarantee the optimal solution
They may yield locally optimal solutions that approximate a globally optimal solution
What is the primary difference between Prim’s and Kruskal’s Algorithms?
Group of answer choices
Prim’s Algorithm builds the MST one vertex at a time, while Kruskal’s builds it one edge at a time
Kruskal’s Algorithm uses a priority queue, while Prim’s does not
Prim’s Algorithm is recursive, while Kruskal’s is iterative
Prim’s Algorithm is used for directed graphs, while Kruskal’s is for undirected graphs
Prim’s Algorithm builds the MST one vertex at a time, while Kruskal’s builds it one edge at a time
What is Dynamic Programming?
Group of answer choices
A method for solving problems by breaking them into independent sub-problems
A method that avoids recursion
A method for solving problems by breaking them into overlapping sub-problems and storing their results
A method that only works for greedy algorithms
A method for solving problems by breaking them into overlapping sub-problems and storing their results
Who developed the Dynamic Programming method?
Group of answer choices
Alan Turing
Richard Bellman
Edsger Dijkstra
Donald Knuth
Richard Bellman
Which of the following is NOT a characteristic of Dynamic Programming?
Group of answer choices
Overlapping sub-problems
Memoization
Independent sub-problems
Optimal substructure
Independent sub-problems
