Master Greedy Algorithms: A Comprehensive Guide for Computer Science MSc Students

Question 1

For a scheduling problem involving tasks with varying deadlines, which greedy algorithm is most appropriate?

Accepted Answer

Earliest deadline first (EDF)

Answer

Shortest job first (SJF)

Answer

Longest job first (LJF)

Answer

Round-robin scheduling

Question 2

What is a significant limitation of greedy algorithms?

Accepted Answer

They may not always yield optimal solutions.

Answer

Their implementation is inherently complex.

Answer

They require excessive memory resources.

Answer

They are only suitable for solving small-scale problems.

Question 3

Regarding the time complexity of greedy algorithms, which statement is accurate?

Accepted Answer

Their time complexity varies based on the algorithm and problem being considered.

Answer

They invariably run within polynomial time.

Answer

They may have exponential time complexity in certain cases.

Answer

They always have constant time complexity.

Question 4

When solving a fractional knapsack problem, which item sorting strategy aligns with the greedy approach?

Accepted Answer

Arranging items based on value-to-weight ratio

Answer

Arranging items based on weight

Answer

Arranging items based on value

Answer

Randomizing the item order

Question 5

What does the exchange property of greedy algorithms describe?

Accepted Answer

Locally optimal choices made by greedy algorithms do not guarantee globally optimal solutions.

Answer

If a greedy algorithm makes locally optimal choices, it will always achieve a globally optimal solution.

Answer

Adjacent elements in a sorted array can be swapped without impacting the solution's optimality.

Answer

The exchange property applies exclusively to problems with a single objective function.

Question 6

Which characteristic is NOT essential for defining a suitable problem for greedy algorithms?

Accepted Answer

A guarantee of finding the best solution

Answer

A clear objective function

Answer

A set of potential solutions

Answer

A method to evaluate the local optimality of choices

Question 7

Which characteristic is NOT associated with greedy algorithms?

Accepted Answer

Guaranteed optimality

Answer

Myopic decision-making

Answer

Incremental construction

Answer

Simplicity

Question 8

Which greedy algorithm is guaranteed to find the optimal solution to a problem?

Accepted Answer

Huffman Coding

Answer

Traveling Salesman Problem

Answer

Knapsack Problem

Answer

Vertex Cover Problem

Question 9

For a greedy algorithm to find the optimal shortest path in a weighted graph, which property of the graph is necessary?

Accepted Answer

Triangle inequality

Answer

Negative edge weights

Answer

Positive edge weights

Answer

Complete graph

Question 10

In the context of scheduling jobs on a single machine, which greedy algorithm prioritizes jobs with the shortest processing time?

Accepted Answer

Shortest Job First (SJF)

Answer

Earliest Deadline First (EDF)

Answer

Longest Processing Time First (LPT)

Answer

First Come First Served (FCFS)

Question 11

Which of the following is a fundamental limitation of greedy algorithms?

Accepted Answer

They are prone to getting stuck in local optima.

Answer

They can always guarantee the globally optimal solution.

Answer

They are applicable to all optimization problems.

Answer

They are non-deterministic algorithms.

Question 12

Which of the following is NOT a characteristic of an optimal solution obtained from a greedy algorithm?

Accepted Answer

Being the first solution found

Answer

Feasibility

Answer

Highest possible objective value

Answer

Satisfying all constraints

Question 13

In the context of the set cover problem, which heuristic is commonly used by greedy algorithms to select the next set to add to the cover?

Accepted Answer

Set that covers the most uncovered elements

Answer

Set with the largest size

Answer

Set with the highest cost

Answer

Set with the smallest intersection with the current cover

Question 14

In the context of a greedy algorithm designed for job scheduling, what does it mean for the algorithm to be non-work-conserving?

Accepted Answer

It may leave the machine idle even when there are tasks that need to be processed.

Answer

It invariably processes tasks in a fixed order.

Answer

It consistently finds the optimal solution.

Answer

Its time complexity is O(n^2).

Question 15

Which of the following statements does NOT accurately describe greedy algorithms?

Accepted Answer

They invariably produce the globally optimal solution.

Answer

They make locally optimal choices at each step.

Answer

They are relatively efficient to implement.

Answer

They are commonly employed to solve optimization problems.

Question 16

Can greedy algorithms effectively solve NP-hard problems?

Accepted Answer

Yes, but only for specific instances of NP-hard problems.

Answer

Yes, they can always solve NP-hard problems.

Answer

No, they can never solve NP-hard problems.

Answer

Only if the NP-hard problem in question is convex.

Question 17

What is a primary limitation of using greedy algorithms?

Accepted Answer

They may not produce the optimal solution due to their focus on local optimality.

Answer

They can only be used for small-scale problems.

Answer

They are difficult to implement and require extensive coding.

Answer

They are not suited for problems with multiple objectives.

Question 18

During the design of a greedy algorithm, which step is NOT essential?

Accepted Answer

Mathematically proving that the algorithm always finds the optimal solution.

Answer

Defining the problem and establishing the objective function.

Answer

Developing a heuristic or rule for making locally optimal choices.

Answer

Evaluating the time and space complexity of the algorithm.

Question 19

For the problem of scheduling jobs on a single machine, which greedy heuristic is effective in minimizing the total completion time?

Accepted Answer

Shortest Job First (SJF)

Answer

Earliest Deadline First (EDF)

Answer

Longest Processing Time First (LPT)

Answer

First Come First Served (FCFS)

Question 20

Which of the following characteristics does NOT apply to greedy algorithms?

Accepted Answer

Guaranteed to find the globally optimal solution

Answer

Myopic focus on local optima

Answer

Simplicity and efficiency

Answer

Suitability for problems with overlapping subproblems

Question 21

What is the fundamental idea behind the greedy algorithm for finding the Minimum Spanning Tree?

Accepted Answer

Starting with an empty tree, iteratively add the lowest-weight edges that connect unconnected vertices

Answer

Starting with a complete graph, iteratively remove the highest-weight edges that do not form cycles

Answer

Initializing a spanning tree with a single vertex and repeatedly adding the vertex with the lowest weight that is not already in the tree

Answer

Generating all possible spanning trees and selecting the one with the lowest total weight

Question 22

Which of the following is a key characteristic of an optimal solution in a greedy algorithm?

Accepted Answer

It is locally optimal at every step

Answer

It is always globally optimal

Answer

It is the first solution found

Answer

It has the lowest computational cost

Question 23

In the context of a greedy algorithm for the knapsack problem, which of the following strategies is commonly used to select the next item to add to the knapsack?

Accepted Answer

Choose the item with the highest value-to-weight ratio

Answer

Choose the item with the lowest value

Answer

Choose the item with the largest weight

Answer

Choose the item that is most similar to the previous item added

Question 24

Which of the following problems is NOT typically solved using greedy algorithms?

Accepted Answer

Sorting an array in ascending order

Answer

Assigning tasks to processors to minimize completion time

Answer

Finding the minimum spanning tree of a graph

Answer

Making change for a given amount of money using the fewest coins possible

Question 25

Which of the following is a key characteristic of greedy algorithms?

Accepted Answer

They make locally optimal choices at each step, not necessarily leading to a global optimum

Answer

They are guaranteed to run in polynomial time

Answer

They always find the optimal solution to the problem

Answer

They require knowledge of the entire problem space before making any decisions

Question 26

Consider a greedy algorithm that constructs a Huffman tree for a set of characters with given frequencies. What is the primary goal of this approach?

Accepted Answer

To minimize the expected length of encoded messages

Answer

To obtain a tree with the maximum number of leaves

Answer

To create a tree with the smallest possible height

Question 27

Consider a greedy algorithm for finding the maximum weight independent set in a graph. Which of the following strategies does this algorithm typically employ?

Accepted Answer

Selecting vertices in decreasing order of their degree

Answer

Constructing a minimum spanning tree of the graph

Answer

Finding the maximum clique in the graph's complement

Question 28

Consider a set of n jobs, each with a start and finish time. A job can be scheduled only if no other job overlaps with it. Suggest an algorithm to determine the maximum number of jobs that can be scheduled.

Accepted Answer

Greedy Algorithm: Select the job with the earliest finish time, then iteratively select the job with the earliest finish time that does not overlap with any previously selected job.

Answer

Dynamic Programming: Break the problem into overlapping subproblems and store the optimal solution for each subproblem.

Question 29

Which of the following is a potential limitation of greedy algorithms?

Accepted Answer

They may not always find the optimal solution, even if a feasible solution exists.

Answer

They can only be used for problems with a small number of variables.

Answer

They are always computationally expensive.

Question 30

Consider a set of activities, each with a start and finish time. Two activities are incompatible if their time intervals overlap. Suggest an algorithm to select the maximum number of mutually compatible activities.

Accepted Answer

Greedy Algorithm: Sort the activities in ascending order of their finish times. Iteratively select the activity with the earliest finish time that does not overlap with any previously selected activity.

Answer

Dynamic Programming: Construct a table where each cell represents the maximum number of compatible activities that can be selected from the first i activities while ending with activity j.

Question 31

Which of the following is a key characteristic of a greedy algorithm?

Accepted Answer

It makes a locally optimal choice at each step, without considering the global implications.

Answer

It always produces the optimal solution for a given problem.

Answer

It is guaranteed to run in polynomial time.

Question 32

Consider a weighted graph with positive edge weights. Suggest an algorithm to find the minimum weight spanning tree.

Accepted Answer

Kruskal's Algorithm: Start with a forest of n trees, where each vertex is a separate tree. Iteratively add the edge with the smallest weight that does not create a cycle.

Answer

Dijkstra's Algorithm: Iteratively find the shortest path from a source vertex to all other vertices.

Question 33

Which of the following is an example of a problem that cannot be solved using a greedy algorithm?

Accepted Answer

Traveling Salesman Problem: Finding the shortest Hamiltonian cycle in a graph.

Answer

Activity Selection Problem: Selecting the maximum number of mutually compatible activities.

Answer

Job Scheduling Problem: Scheduling a set of jobs to minimize the total completion time.

Question 34

What is the primary characteristic of a greedy algorithm?

Accepted Answer

It makes locally optimal choices at each step, hoping to find a globally optimal solution

Answer

It uses dynamic programming techniques to optimize the solution

Answer

It explores all possible solutions to guarantee finding the optimal one

Question 35

Which of the following is NOT a limitation of greedy algorithms?

Accepted Answer

They are generally slower than brute-force approaches

Answer

They require problems to exhibit optimal substructure

Answer

They may not always find the optimal solution

Question 36

In the context of greedy algorithms, what does 'optimal substructure' mean?

Accepted Answer

The optimal solution to the problem contains optimal solutions to its subproblems

Answer

The algorithm's structure is optimized for performance

Answer

The problem can be divided into independent subproblems

Question 37

What is the time complexity of Kruskal's algorithm for finding the minimum spanning tree of a graph with V vertices and E edges?

Accepted Answer

O(E log V)

Answer

O(V^2)

Answer

O(E + V)

Answer

O(V log E)

Question 38

Dijkstra's algorithm is a greedy algorithm used for:

Accepted Answer

Finding the shortest path from a single source vertex to all other vertices in a weighted graph

Answer

Finding the minimum spanning tree in a weighted graph

Answer

Sorting a list of elements in ascending order

Question 39

Which greedy algorithm is used for finding the optimal way to schedule a set of activities on a single resource?

Accepted Answer

Activity Selection Algorithm

Answer

Huffman Coding Algorithm

Answer

Prim's Algorithm

Answer

Fractional Knapsack Problem Algorithm

Question 40

In the context of the Fractional Knapsack Problem, how does the greedy approach maximize the value of items chosen?

Accepted Answer

It prioritizes items with the highest value-to-weight ratio

Answer

It selects items based on their individual values, regardless of weight

Answer

It sorts items by weight and chooses the lightest ones first

Question 41

Which data structure is commonly used to implement Prim's algorithm for finding the minimum spanning tree?

Accepted Answer

Priority Queue

Answer

Queue

Answer

Linked List

Answer

Stack