1
What defines a greedy algorithm?
Correct Answer
An algorithm that makes the locally optimal choice at each step.
☑ MCQ PRACTICE
Design and Analysis of Algorithms Unit 4
Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.
Design and Analysis of Algorithms - Unit-4
2
In which scenario is a greedy algorithm guaranteed to find the global optimum?
Correct Answer
When the problem exhibits the property of "greedy choice property" and "optimal substructure."
3
What is the "greedy choice property" in the context of greedy algorithms?
Correct Answer
A global optimal solution can be arrived at by choosing the local optimum.
4
Why might a greedy algorithm not always produce an optimal solution?
Correct Answer
Because it may make a choice that seems best at the moment but is not optimal overall.
5
Which characteristic does a problem need to have for a greedy algorithm to be applicable?
Correct Answer
The problem should allow a global optimal solution to be assembled from local optima.
6
What is the primary difference between dynamic programming and greedy algorithms?
Correct Answer
Dynamic programming solves each subproblem once and stores the result, while greedy algorithms make decisions from the given solution set without looking back.
7
Which of the following is a characteristic of greedy algorithms?
Correct Answer
They make a series of choices that are locally optimal, aiming for a global optimum.
8
What can be a downfall of using a greedy algorithm for a particular problem?
Correct Answer
They may not consider the overall problem, leading to suboptimal solutions.
9
What is the main objective of the job sequencing with deadlines problem?
Correct Answer
To maximize the total profit while respecting job deadlines.
10
In the context of job sequencing, what does a deadline signify?
Correct Answer
The time by which a job must be completed.
11
Which strategy is typically used to solve the job sequencing problem using a greedy algorithm?
Correct Answer
Selecting jobs in descending order of their profits.
12
Why is the greedy choice property useful in solving the job sequencing problem?
Correct Answer
It focuses on selecting jobs that offer the highest profit first.
13
What does the feasibility check involve in job sequencing with deadlines?
Correct Answer
Checking if a job can be completed before its deadline after scheduling.
14
Which of the following is a true statement about the job sequencing problem?
Correct Answer
It may not be possible to complete all jobs within their deadlines.
15
What limitation does the greedy algorithm face when solving job sequencing problems?
Correct Answer
It may not always lead to the optimum solution of sequencing all jobs.
16
In a job sequencing scenario, what happens if a job cannot be completed by its deadline?
Correct Answer
The job is typically not included in the sequence.
17
Which factor is NOT usually considered while applying a greedy method to job sequencing with deadlines?
Correct Answer
Number of resources needed
18
What is the ideal outcome when applying a greedy approach to job sequencing with deadlines?
Correct Answer
Maximizing the total profit while adhering to the deadlines of as many jobs as possible.
19
What distinguishes the Fractional Knapsack problem from the 0/1 Knapsack problem?
Correct Answer
Items can be divided into smaller parts in the Fractional Knapsack.
20
What is the main objective of the Fractional Knapsack problem?
Correct Answer
To maximize the total value of items in the knapsack.
21
Which strategy is typically employed to solve the Fractional Knapsack problem using a greedy method?
Correct Answer
Selecting items based on maximum value-to-weight ratio.
22
Why is the greedy algorithm suitable for solving the Fractional Knapsack problem?
Correct Answer
It efficiently utilizes the knapsack's capacity to maximize total value.
23
What does the 'greedy choice' involve in the Fractional Knapsack problem?
Correct Answer
Taking the item with the highest value-to-weight ratio first.
24
In the context of the greedy method for the Fractional Knapsack, what must be done before making selections?
Correct Answer
Items must be sorted by value-to-weight ratio in descending order.
25
What is a limitation of the greedy algorithm when applied to the 0/1 Knapsack problem instead of the Fractional Knapsack?
Correct Answer
It cannot guarantee the optimum solution.
26
What happens when an item is selected for inclusion in the knapsack in the Fractional Knapsack problem?
Correct Answer
Only a fraction of the item may be taken.
27
Which of the following scenarios best applies the Fractional Knapsack problem's solution method?
Correct Answer
Loading cargo of various sizes and values into a ship without exceeding the weight limit.
28
What characteristic of items is irrelevant to solving the Fractional Knapsack problem using the greedy method?
Correct Answer
The color of the items.
29
The main time taking step in fractional knapsack problem is ___________
Correct Answer
Sorting
30
Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.
Correct Answer
110, 80
31
Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.
Correct Answer
60
32
What is the primary goal of constructing a Minimum Cost Spanning Tree (MCST) in a weighted graph?
Correct Answer
To connect all vertices with the least total edge weight without creating cycles.
33
Which algorithm is a popular greedy method used to find the MCST of a graph?
Correct Answer
Kruskal’s Algorithm
34
What is the key characteristic of Kruskal’s algorithm when forming a minimum spanning tree?
Correct Answer
It sorts all edges in ascending order by weight and includes them if they don’t close a cycle.
35
In the context of MCST, what role does a "cycle" play?
Correct Answer
It must be avoided to ensure a valid spanning tree.
36
What is the objective of the Single Source Shortest Path problem?
Correct Answer
To find the shortest paths from a specific source vertex to all other vertices in the graph.
37
Which algorithm is a well-known greedy method for solving the SSSP problem in graphs without negative weight edges?
Correct Answer
Dijkstra’s Algorithm
38
What is a characteristic feature of Dijkstra’s algorithm?
Correct Answer
It uses a priority queue to choose the vertex with the smallest known distance from the source.
39
How does Dijkstra’s algorithm determine the next vertex to process?
Correct Answer
By selecting the vertex with the smallest tentative distance to the source.
40
In Dijkstra’s algorithm, what happens if a shorter path to a vertex is found after it has been processed?
Correct Answer
The priority queue is updated with the new shorter distance.
Fill in the Blanks
41
The Greedy method is a heuristic strategy used to find __________ solutions at each step, with the hope of finding a global optimum.
Correct Answer
Locally optimal
42
At each step of the Greedy method, a decision is made that appears to be the __________ choice at that moment.
Correct Answer
Best (or optimal)
43
Greedy algorithms do not always guarantee an __________ solution.
Correct Answer
Optimal
44
The choice made by a Greedy algorithm is based only on the information available at the __________, without considering future consequences.
Correct Answer
Current step
45
Greedy algorithms are often used for __________ problems where a sequence of choices needs to be made.
Correct Answer
Optimization
46
The Greedy method is particularly effective when __________ subproblems can be solved independently.
Correct Answer
Subsequent
47
Greedy algorithms are well-suited for problems with _____________ choices, where the locally optimal choice also leads to a globally optimal solution.
Correct Answer
independent
48
However, the greedy method might not always find the _____________ solution, as it focuses on short-term gains.
Correct Answer
optimal
49
An example of a problem where the greedy method works well is finding the minimum spanning tree of a graph, using algorithms like Prim's or Kruskal's. Here, choosing the _____________ edge at each step contributes to the overall goal.
Correct Answer
lowest weight
50
In Job Sequencing with Deadlines, each job has a __________ and a __________ associated with it.
Correct Answer
Deadline, profit
51
The Greedy method for Job Sequencing with Deadlines involves selecting jobs based on their __________, starting with the job that has the __________ deadline.
Correct Answer
Profit, earliest (or closest)
52
If a job cannot be scheduled due to lack of available slots within its deadline, it is __________.
Correct Answer
Rejected (or skipped)