Chapter 9 Greedy

Question 1

Discuss Prims Algorithm and walk through an example

Answer 1

Step 1: Determine an arbitrary vertex as the starting vertex of the MST. We pick 0 in the below diagram.

Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST (known as fringe vertex).

Step 3: Find edges connecting any tree vertex with the fringe vertices.

Step 4: Find the minimum among these edges.

Step 5: Add the chosen edge to the MST. Since we consider only the edges that connect fringe vertices with the rest, we never get a cycle.
Step 6: Return the MST and exit.

Question 2

Discuss Kruskals Algorithm and walk through an example

Answer 2

A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected, and undirected graph is a spanning tree (no cycles and connects all vertices) that has minimum weight. The weight of a spanning tree is the sum of all edges in the tree.

In Kruskal’s algorithm, we sort all edges of the given graph in increasing order. Then it keeps on adding new edges and nodes in the MST if the newly added edge does not form a cycle. It picks the minimum weighted edge at first and the maximum weighted edge at last. Thus we can say that it makes a locally optimal choice in each step in order to find the optimal solution. Hence this is a Greedy Algorithm.

Below are the steps for finding MST using Kruskal’s algorithm:

1. Sort all the edges in a non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the cycle is not formed, include this edge. Else, discard it.
3. Repeat step 2 until there are (V-1) edges in the spanning tree.

Question 3

Fractional Knapsack Problem

Given two arrays, val[] and wt[], representing the values and weights of items, and an integer capacity representing the maximum weight a knapsack can hold, the task is to determine the maximum total value that can be achieved by putting items in the knapsack. You are allowed to break items into fractions if necessary.

Note: Return the maximum value as a double, rounded to 6 decimal places.

Examples:

Input: val[] = [60, 100, 120], wt[] = [10, 20, 30], capacity = 50
Output: 240
Explanation: By taking items of weight 10 and 20 kg and 2/3 fraction of 30 kg.
Hence total price will be 60+100+(2/3)(120) = 240

Input: val[] = [500], wt[] = [30], capacity = 10
Output: 166.667