1. What defines a greedy algorithm?
A . An algorithm that tries every possible solution to find the best one.
B . An algorithm that makes the locally optimal choice at each step.
C . An algorithm that reconsiders previous decisions based on future choices.
D . An algorithm that uses backtracking to ensure all possibilities are covered.
Answer
An algorithm that makes the locally optimal choice at each step.
2. In which scenario is a greedy algorithm guaranteed to find the global optimum?
A . When the problem has overlapping subproblems and optimal substructure.
B . When the problem exhibits the property of "greedy choice property" and "optimal
substructure."
C . When the problem is NP-complete.
D . When the problem can be divided into smaller instances that can be solved independently.
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?
A . A global optimal solution can be arrived at by choosing the local optimum.
B . The choice made at each step is reversible.
C . The choice depends on choices made in previous steps.
D . Multiple choices are evaluated before making a decision.
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?
A . Because it always makes the safest choice.
B . Because it may make a choice that seems best at the moment but is not optimal overall.
C . Because it evaluates all possible choices at each step.
D . Because it uses dynamic programming.
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?
A . The problem must be divisible into smaller independent subproblems.
B . The problem should allow a global optimal solution to be assembled from local optima.
C . The problem requires the solution to consider future consequences of current decisions.
D . The problem must be solved in polynomial time.
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?
A . Dynamic programming makes use of recursion, while greedy algorithms do not.
B . Greedy algorithms solve subproblems and combine their solutions; dynamic programming
does not.
C . Dynamic programming solves each subproblem once and stores the result, while greedy
algorithms make decisions from the given solution set without looking back.
D . Greedy algorithms are used for optimization problems, while dynamic programming is not.
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?
A . They are always the most efficient solution.
B . They can always backtrack to find the best solution.
C . They make a series of choices that are locally optimal, aiming for a global optimum.
D . They require complete knowledge of future decisions.
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?
A . They are too slow for large datasets.
B . They may not consider the overall problem, leading to suboptimal solutions.
C . They can only solve problems that can be expressed recursively.
D . They often require more memory than other algorithms.
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?
A . To complete all jobs within their deadlines.
B . To maximize the total number of jobs done.
C . To maximize the total profit while respecting job deadlines.
D . To minimize the total time taken to complete the jobs.
Answer
To maximize the total profit while respecting job deadlines.
10. In the context of job sequencing, what does a deadline signify?
A . The time at which a job must start.
B . The time by which a job must be completed.
C . The total duration of a job.
D . The waiting time before a job can be started.
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?
A . Selecting jobs in ascending order of deadlines.
B . Selecting jobs in descending order of their profits.
C . Selecting jobs in ascending order of their duration.
D . Selecting jobs randomly.
Answer
Selecting jobs in descending order of their profits.
12. Why is the greedy choice property useful in solving the job sequencing problem?
A . It helps in choosing the job with the maximum duration first.
B . It ensures that jobs with earlier deadlines are always completed first.
C . It focuses on selecting jobs that offer the highest profit first.
D . It ensures all jobs are completed without overlapping.
Answer
It focuses on selecting jobs that offer the highest profit first.
13. What does the feasibility check involve in job sequencing with deadlines?
A . Checking if a job can be completed before its deadline after scheduling.
B . Checking if jobs overlap with each other.
C . Checking if the total duration exceeds the total available time.
D . Checking if all jobs can be completed in a single sequence.
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?
A . It can always guarantee that all jobs will be completed within their deadlines.
B . It may not be possible to complete all jobs within their deadlines.
C . There is no need to consider deadlines as long as the profit is maximized.
D . The sequence in which jobs are selected does not affect the total profit.
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?
A . It cannot handle jobs with identical deadlines.
B . It may not always lead to the optimum solution of sequencing all jobs.
C . It requires that all jobs have different profits.
D . It must always select jobs in order of increasing profit.
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?
A . The job is done anyway, but the profit is not counted.
B . The job is typically not included in the sequence.
C . The deadline of the job is extended to accommodate the schedule.
D . The profit of the job is reduced proportionally to the delay.
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?
A . Profit of each job
B . Duration of each job
C . Deadline of each job
D . Number of resources needed
Answer
Number of resources needed
18. What is the ideal outcome when applying a greedy approach to job sequencing with
deadlines?
A . Completing all jobs irrespective of their profit.
B . Maximizing the total profit while adhering to the deadlines of as many jobs as possible.
C . Minimizing the total time taken for job completion.
D . Ensuring no two jobs overlap in the schedule.
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?
A . Items in the Fractional Knapsack can only be taken once.
B . Items can be divided into smaller parts in the Fractional Knapsack.
C . All items must be taken in the 0/1 Knapsack.
D . The knapsack has unlimited capacity in the Fractional problem.
Answer
Items can be divided into smaller parts in the Fractional Knapsack.
20. What is the main objective of the Fractional Knapsack problem?
A . To maximize the total weight of the knapsack.
B . To minimize the total weight of the knapsack.
C . To maximize the total value of items in the knapsack.
D . To minimize the total value of items in the knapsack.
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?
A . Selecting items based on maximum weight.
B . Selecting items based on maximum value.
C . Selecting items based on maximum value-to-weight ratio.
D . Selecting items based on minimum value-to-weight ratio.
Answer
Selecting items based on maximum value-to-weight ratio.
22. Why is the greedy algorithm suitable for solving the Fractional Knapsack problem?
A . It always finds the globally optimal solution.
B . It efficiently utilizes the knapsack`s capacity to maximize total value.
C . It prioritizes heavier items first.
D . It requires sorting items by their weights.
Answer
It efficiently utilizes the knapsack`s capacity to maximize total value.
23. What does the `greedy choice` involve in the Fractional Knapsack problem?
A . Taking the smallest item to save space.
B . Taking the item with the highest value first.
C . Taking the item with the highest value-to-weight ratio first.
D . Taking the item with the lowest weight first.
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?
A . Items must be sorted by weight in ascending order.
B . Items must be sorted by value in ascending order.
C . Items must be sorted by value-to-weight ratio in descending order.
D . Items must be divided into equal weights.
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?
A . It cannot guarantee the optimum solution.
B . It takes too long to compute.
C . It requires items to be divisible.
D . It must use a different sorting criterion.
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?
A . The item is taken in its entirety.
B . Only a fraction of the item may be taken.
C . The remaining items are re-evaluated.
D . The knapsack`s capacity is increased.
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?
A . Packing a bag with whole items for a camping trip where the bag`s capacity is limited.
B . Distributing resources in parts to different departments based on urgency and importance.
C . Choosing courses to meet as many graduation requirements as possible within a limited
number of slots.
D . Loading cargo of various sizes and values into a ship without exceeding the weight limit.
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?
A . The weight of the items.
B . The value of the items.
C . The color of the items.
D . The value-to-weight ratio of the items.
Answer
The color of the items.
29. The main time taking step in fractional knapsack problem is ___________
A . Breaking items into fraction
B . Adding items into knapsack
C . Sorting
D . Looping through sorted items
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.
A . 100, 80
B . 110, 70
C . 130, 110
D . 110, 80
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.
A . 60
B . 80
C . 100
D . 40
Answer
60
32. What is the primary goal of constructing a Minimum Cost Spanning Tree (MCST) in a
weighted graph?
A . To find the shortest path between two specific vertices.
B . To connect all vertices with the least total edge weight without creating cycles.
C . To find the longest possible path without repeating edges.
D . To maximize the differences in weight between consecutive edges.
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?
A . Dijkstra’s Algorithm
B . Kruskal’s Algorithm
C . Floyd-Warshall Algorithm
D . Bellman-Ford Algorithm
Answer
Kruskal’s Algorithm
34. What is the key characteristic of Kruskal’s algorithm when forming a minimum spanning
tree?
A . It starts from the highest weight edges and includes them if they don`t form a cycle.
B . It begins at a chosen vertex and explores adjacent vertices progressively.
C . It sorts all edges in ascending order by weight and includes them if they don’t close a cycle.
D . It selects edges randomly until all vertices are connected without cycles.
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?
A . It helps in reducing the total cost of the spanning tree.
B . It is necessary to ensure all vertices are connected.
C . It must be avoided to ensure a valid spanning tree.
D . It represents the maximum weight edge in the graph.
Answer
It must be avoided to ensure a valid spanning tree.
36. What is the objective of the Single Source Shortest Path problem?
A . To find the shortest paths from a specific source vertex to all other vertices in the graph.
B . To determine the longest path from a single source to a destination.
C . To calculate the shortest path that visits all vertices starting from a source.
D . To find a path that maximizes the total edge weights from a source to all other vertices.
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?
A . Kruskal’s Algorithm
B . Dijkstra’s Algorithm
C . Floyd-Warshall Algorithm
D . Bellman-Ford Algorithm
Answer
Dijkstra’s Algorithm
38. What is a characteristic feature of Dijkstra’s algorithm?
A . It re-evaluates the shortest path tree if a shorter path is discovered.
B . It processes all vertices and edges in a random order.
C . It requires the graph to be unweighted.
D . It uses a priority queue to choose the vertex with the smallest known distance from the
source.
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?
A . By selecting the vertex closest to the source based on physical distance.
B . By selecting the vertex with the smallest tentative distance to the source.
C . By choosing vertices in alphabetical order.
D . By randomly selecting any vertex that has not been processed yet.
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?
A . The algorithm backtracks to reconsider the best path.
B . The algorithm updates the distances for all adjacent vertices.
C . The algorithm does not allow updates; the path remains fixed.
D . The priority queue is updated with the new shorter distance.
Answer
The priority queue is updated with the new shorter distance.
41. The Greedy method is a heuristic strategy used to find __________ solutions at each step,
with the hope of finding a global optimum.
Answer
Locally optimal
42. At each step of the Greedy method, a decision is made that appears to be the __________
choice at that moment.
Answer
Best (or optimal)
43. Greedy algorithms do not always guarantee an __________ solution.
Answer
Optimal
44. The choice made by a Greedy algorithm is based only on the information available at the
__________, without considering future consequences.
Answer
Current step
45. Greedy algorithms are often used for __________ problems where a sequence of choices
needs to be made.
Answer
Optimization
46. The Greedy method is particularly effective when __________ subproblems can be solved
independently.
Answer
Subsequent
47. Greedy algorithms are well-suited for problems with _____________ choices, where the
locally optimal choice also leads to a globally optimal solution.
Answer
independent
48. However, the greedy method might not always find the _____________ solution, as it
focuses on short-term gains.
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.
Answer
lowest weight
50. In Job Sequencing with Deadlines, each job has a __________ and a __________ associated
with it.
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.
Answer
Profit, earliest (or closest)
52. If a job cannot be scheduled due to lack of available slots within its deadline, it is
__________.
Answer
Rejected (or skipped)
