Unit 3: Greedy Method - Subjective Questions

The greedy method constructs a solution incrementally by choosing the locally optimal option at every step, without reconsidering previous choices.

Its main components are:

• Candidate set: Elements from which the solution is constructed.
• Selection function: Selects the most promising candidate.
• Feasibility function: Determines whether adding a candidate keeps the solution valid.
• Objective function: Assigns a value to a complete or partial solution.
• Solution function: Determines whether a complete solution has been obtained.

A greedy algorithm is correct when the problem has the greedy-choice property and optimal substructure.

Greedy-choice property: A globally optimal solution can be obtained by making a locally optimal choice first. Once this choice is made, it does not need to be reconsidered. For example, in fractional knapsack, selecting the item with the highest profit-to-weight ratio is always safe.

Optimal substructure: An optimal solution to a problem contains optimal solutions to its subproblems. For example, after selecting an edge in a minimum spanning tree, the remaining edges must optimally connect the resulting components.

Both properties are generally needed to prove the correctness of a greedy algorithm.

The general development process is:

1. Identify the candidates used to construct the solution.
2. Define a rule that selects the locally best candidate.
3. Check whether the selected candidate maintains feasibility.
4. Add feasible candidates until the solution is complete.
5. Prove that the greedy choices produce an optimal solution.

Common correctness techniques include:

• Exchange argument: Show that an optimal solution can be transformed to include the greedy choice without worsening its value.
• Stays-ahead argument: Show that the greedy solution is at least as good as any competing solution after every step.
• Cut-and-paste argument: Use optimal substructure to replace a nonoptimal subproblem solution with an optimal one.

Thus, dynamic programming performs a more exhaustive comparison, whereas the greedy method commits to one choice at each step.

Suppose item has profit , weight , and selected fraction . For a knapsack of capacity , the problem is:

subject to

The greedy solution is:

1. Compute the ratio for each item.
2. Sort items in nonincreasing order of .
3. Insert each complete item while capacity permits.
4. If the next item does not fit, insert the fraction required to fill the remaining capacity.

Sorting takes time, while selection takes time. Therefore, total time complexity is .

Compute the profit-to-weight ratios:

• Item 1:
• Item 2:
• Item 3:

Select items in decreasing ratio order:

1. Take item 1 completely: weight , profit , remaining capacity .
2. Take item 2 completely: weight , profit , remaining capacity .
3. Only units of item 3 can be taken, so its selected fraction is .

Profit obtained from item 3 is:

Therefore, the maximum profit is:

The selected fractions are , , and .

In fractional knapsack, items are divisible. Therefore, selecting as much as possible of the highest profit-to-weight ratio cannot prevent the unused capacity from being filled optimally. This supports an exchange argument.

In knapsack, each item must be selected completely or rejected. A locally best ratio may consume capacity needed for a better combination.

For capacity , consider items :

• with ratio
• with ratio
• with ratio

The greedy ratio strategy selects the first two items, obtaining profit and using weight . The third item cannot then fit. However, selecting the second and third items uses weight and produces profit .

Hence, ratio-based greediness is not always optimal for knapsack.

For a connected, undirected, weighted graph , a spanning tree is a connected, acyclic subgraph that contains every vertex. A minimum spanning tree (MST) is a spanning tree whose total edge weight is minimum among all spanning trees.

Important properties are:

• An MST contains exactly edges.
• It has no cycles.
• Removing any MST edge disconnects the tree.
• Adding any non-tree edge creates exactly one cycle.
• If all edge weights are distinct, the MST is unique.
• Equal edge weights may result in multiple MSTs with the same minimum cost.
• If the graph is disconnected, a spanning tree does not exist; MST algorithms instead produce a minimum spanning forest when applied component-wise.

Cut property: A cut partitions the vertex set into two nonempty subsets. If an edge has minimum weight among all edges crossing a cut, that edge is safe for some MST. If it is the unique lightest crossing edge, it belongs to every MST.

Cycle property: In any cycle, an edge having strictly greater weight than every other edge in that cycle cannot belong to an MST. More generally, a maximum-weight edge of a cycle can be excluded from at least one MST.

Prim's algorithm repeatedly applies the cut property to the cut separating its current tree from the remaining vertices. Kruskal's algorithm also uses safe light edges, while rejecting edges that create cycles.

Prim's algorithm grows one tree from a chosen source vertex.

Procedure:

1. Assign key to the start vertex and to every other vertex.
2. Place all vertices in a min-priority queue ordered by key.
3. Extract the vertex having minimum key.
4. For each unselected neighbor , if is smaller than the current key of , update its key and set its parent to .
5. Repeat until every vertex is selected.

The parent edges form the MST.

Time complexity:

• Adjacency matrix with linear search: .
• Adjacency list with a binary heap: .
• Fibonacci heap: .

The algorithm requires the graph to be connected for a single spanning tree.

Start with .

1. From , candidate edges are and . Select .
2. The tree contains . Crossing edges are , , and . Select .
3. The tree contains . The useful crossing edges include , , and . Select .
4. The tree contains . Crossing edges to are and . Select .

Thus, one MST is:

Its total cost is:

The edge is not selected because , , and are already connected more cheaply through and .

Kruskal's algorithm constructs an MST by processing edges globally in nondecreasing order of weight.

Procedure:

1. Create a separate component for each vertex using MAKE-SET.
2. Sort all edges by nondecreasing weight.
3. For each edge , compare FIND-SET(u) and FIND-SET(v).
4. If the endpoints belong to different components, add the edge and perform UNION(u,v).
5. Stop after selecting edges.

The disjoint-set structure efficiently detects whether an edge would create a cycle. With path compression and union by rank or size, its operations take nearly constant amortized time.

Sorting dominates the execution time, giving:

The edges are already listed in nondecreasing order.

1. Select : components become , , , .
2. Select : components become , , .
3. Reject because and are already in the same component; selecting it would create a cycle.
4. Select : components become and .
5. Reject because and are already connected.
6. Select : all vertices now belong to one component.

The selected edges are:

The MST cost is:

Since , the algorithm stops after selecting four edges.

Both are greedy algorithms justified by the cut property and both find an MST in a connected, undirected, weighted graph.

A disconnected graph has no spanning tree because no subgraph can connect all vertices using only its existing edges.

• A standard execution of Prim's algorithm from one source constructs an MST only for the connected component containing that source. Restarting Prim's algorithm from each unvisited vertex constructs one tree per component.
• Kruskal's algorithm naturally selects safe edges within individual components. Since no edge joins different graph components, its final result remains a forest.

The resulting minimum spanning forest contains an MST for every connected component. If the graph has vertices and connected components, the forest contains:

edges.

The single-source shortest-path problem asks for the minimum path distance from a source vertex to every other reachable vertex in a weighted graph. For a path , its cost is the sum of its edge weights:

A shortest-path tree preserves the shortest distance from a particular source to every reachable vertex. A minimum spanning tree minimizes the total weight of edges needed to connect all vertices.

Key differences are:

• A shortest-path tree depends on the selected source; an MST does not.
• An MST minimizes total tree weight, not source-to-vertex distances.
• A shortest-path tree may not be an MST, and an MST may not preserve shortest paths from any chosen source.
• Shortest paths can be considered in directed graphs, while the standard MST problem is defined for undirected graphs.

Dijkstra's algorithm finds shortest paths from a source when all edge weights are nonnegative.

Algorithm:

1. Set and for every .
2. Insert vertices into a min-priority queue keyed by tentative distance.
3. Extract the vertex with minimum tentative distance. This distance is finalized.
4. Relax each outgoing edge by testing:

If true, set and set .

5. Repeat until the queue is empty.

Complexity:

• Adjacency matrix: .
• Adjacency list with binary heap: , commonly written as for connected graphs.
• Fibonacci heap: .

Initialize:

1. Finalize . Relax its edges: and .
2. Finalize because it has the smallest distance .
   • Through , update .
   • Through , set .
3. Finalize with distance .
   • Through , update .
4. Finalize with distance .
   • Through , set .
5. Finalize with distance .

Final shortest paths are:

• To : , distance .
• To : , distance .
• To : , distance .
• To : , distance .
• To : , distance .

Dijkstra's algorithm assumes that once the smallest tentative distance is extracted, no later path can reduce it. This is valid only when extending a path cannot decrease its cost, which requires nonnegative edge weights.

Consider the directed edges:

Dijkstra's algorithm may finalize first with distance . Later, after processing , it discovers the path:

with cost:

This is shorter than , contradicting the finalization of . Implementations that do not reopen finalized vertices therefore return an incorrect result.

For graphs containing negative edges, the Bellman-Ford algorithm should be used. It can also detect a reachable negative-weight cycle.

Let be the set of vertices whose shortest distances have been finalized. The invariant is that, for every , the tentative distance satisfies , where is the true shortest distance from to .

Base case: The source is extracted first with .

Inductive step: Let be the next vertex extracted with minimum tentative distance. Assume, for contradiction, that a shorter path from to exists. On that path, let be the first vertex outside , and let be its predecessor inside . When was processed, edge was relaxed, so:

Because all remaining edge weights are nonnegative, the path prefix to cannot cost more than the full path to :

Therefore, , contradicting the choice of as the unfinalized vertex with minimum tentative distance. Hence .

By induction, every extracted vertex receives its correct shortest distance, proving the algorithm's correctness.