.png)
Mobiprep has created last-minute notes for all topics of Algorithm to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Algorithm.
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
What is the Activity Selection Problem in Greedy Algorithms?
Explain Prim's minimum spanning tree for adjacency list representation.
What is the difference between 0/1 knapsack and fractional knapsack?
Greedy Algorithm
Question- 1) What is Greedy Algorithm and its properties?
Answer: A greedy algorithm is a simple, intuitive algorithm that is used in optimization problem. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem.
An optimization problem is the problem of finding the best solution from all feasible solutions where the objective function reaches its maximum (or minimum) value. For example, the most profit or the least cost.
In Greedy method the following activities are performed.
First, we select some solution from the input domain.
Then we check whether the solution is feasible or not.
From the set of feasible solutions, a particular solution that satisfies or nearly satisfies the objective of the function. Such a solution is called an optimal solution.
The Greedy method works in stages. At each stage only one input is considered at each time. Based on this input it is decided whether a particular input gives the optimal solution or not.
For a problem with the following properties, we can use the greedy technique:
Greedy Choice Property: This states that a globally optimal solution can be obtained by locally optimal choices.
Optimal Sub-Problem: This property states that an optimal solution to a problem, contains within it, an optimal solution to the sub-problems. Thus, a globally optimal solution can be constructed from locally optimal sub-solutions.
Question- 2) What is the Activity Selection Problem in Greedy Algorithms?
Answer: Activity selection problem is an optimization problem which is used to find the optimal solution to conduct maximum number of nonconflicting activities in a given time frame.
Notation:
s, k=array of start time and end time
k= the index that defines the subproblem Sk that to be solved
n= size of the original problem
Pseudo code:
RECURSIVE-ACTIVITY-SELECTOR (s, f, k, n)
1 m = k+1;
2 while m <=n and s[m] < f [k] // find the first activity in Sk to finish
3 m-m +1
4 if m <=n
5 return {am} Union [ RECURSIVE-ACTIVITY-SELECTOR (s, f, m, n)
6 else return ΦLet's take an example
Consider six activities
Activity | A1 | A2 | A3 | A4 | A5 | A6 |
Start Time | 0 | 3 | 1 | 5 | 5 | 8 |
Finish Time | 6 | 4 | 2 | 9 | 7 | 9 |
Step1:
Arrange it the ascending order of the time required to complete the activity
Activity | A1 | A2 | A3 | A4 | A5 | A6 |
Start Time | 1 | 3 | 0 | 5 | 8 | 5 |
Finish Time | 2 | 4 | 6 | 7 | 9 | 9 |
Step 2:
Now start from the beginning and include all those activities whose finish time is smaller than another activity start time
A3->A2->A5->A6
Maximum four activities can be conduct
Code implementation:
// C++ program for activity selection problem.
// The following implementation assumes that the activities
// are already sorted according to their finish time
#include<stdio.h>
// Prints a maximum set of activities that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start time of all activities
// f[] --> An array that contains finish time of all activities
void printMaxActivities(int s[], int f[], int n)
{
int i, j;
printf ("Following activities are selected n");
// The first activity always gets selected
i = 0;
printf("%d ", i);
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
printf ("%d ", j);
i = j;
}
}
}
// driver program to test above function
int main()
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = sizeof(s)/sizeof(s[0]);
printMaxActivities(s, f, n);
return 0;
}
Question- 3) Explain Container loading problem using greedy approach?
Answer: A large ship is to be loaded with containers of cargos. Different containers, although of equal size, will have different weights. We want to find out a way to load the ship with the maximum number of containers, without tipping over the ship.
Example:
1) Find the optimal solution for the following data:
n = 8 | c | w8 | w3 | w1 | w4 | w5 | w2 | w7 | w6 |
| 400 | 20 | 30 | 50 | 80 | 90 | 100 | 150 | 200 |
Solution:
Step1: Sort the Containers in the increasing order
n = 8 | c | w8 | w3 | w1 | w4 | w5 | w2 | w7 | w6 |
| 400 | 20 | 30 | 50 | 80 | 90 | 100 | 150 | 200 |
Step 2: Select the containers with minimum weight
(i) 1st minimum Container 20
Remaining weight = 400-20 (20<=400) (T)
= 380
(ii) 2nd minimum Container 30
Remaining weight = 380-30 (30<=380) (T)
= 350
(iii) 3rd minimum Container 50
Remaining weight = 350-50 (50<=350) (T)
= 300
(iv) 4th minimum Container 80
Remaining weight = 300-80 (80<=300) (T)
= 220
(v) 5th minimum Container 90
Remaining weight = 220-90 (90<=220) (T)
= 130
(vi) 6th minimum Container 100
Remaining weight = 130-100 (100<=130) (T)
= 30
Now if we select the next container of weight 150 then it would exceed the capacity.
Optimal Solution Set
[x1, x2, x3, x4, x5, x6, x7, x8] = [1,1,1,1,1,0,0,1]
Question- 4) Explain Travelling Salesperson Problem?
Answer: Travelling Salesman problem is one of the computational problems that can be solved by using a greedy approach.
The problem states that you have a number of places to visit and you know the cost or distance of all possible pairs. The traveler has to visit every place exactly once and come back to the initial place at the end that also only in such a way that the cost or distance covered is minimized.
Notation
S = set of all cities
C=cost to travel all cities from all possible points
Pseudo code
C ({1}, 1) = 0
for s = 2 to n do
for all subsets S Є {1, 2, 3, … , n} of size s and containing 1
C (S, 1) = ∞
for all j Є S and j ≠1
C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠j}
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)Consider an example
A B C D
A. {-1, 10, 15, 20}
B. {10, -1, 35, 25}
C. {15, 35, -1, 30}
D. {20, 25, 30, -1}
We are trying to find out the path/route with the minimum cost such that our aim of visiting all cities once and return back to the source city is achieved. The path through which we can achieve that, can be represented as 1 -> 2 -> 4 -> 3 -> 1. Here, we started from city 1 and ended on the same visiting all other cities once on our way. The cost of our path/route is calculated as follows:
A -> B = 10
B-> D = 25
D -> C = 30
C -> A = 15
Hence, total cost = 10 + 25 + 30 + 15 = 80
Code implementation:
// C# program for the above approach
using System;
using System.Collections.Generic;
class TSPGreedy{
// Function to find the minimum
// cost path for all the paths
static void findMinRoute(int[,] tsp)
{
int sum = 0;
int counter = 0;
int j = 0, i = 0;
int min = int.MaxValue;
List<int> visitedRouteList = new List<int>();
// Starting from the 0th indexed
// city i.e., the first city
visitedRouteList.Add(0);
int[] route = new int[tsp.Length];
// Traverse the adjacency
// matrix tsp[,]
while (i < tsp.GetLength(0) &&
j < tsp.GetLength(1))
{
// Corner of the Matrix
if (counter >= tsp.GetLength(0) - 1)
{
break;
}
// If this path is unvisited then
// and if the cost is less then
// update the cost
if (j != i &&
!(visitedRouteList.Contains(j)))
{
if (tsp[i, j] < min)
{
min = tsp[i, j];
route[counter] = j + 1;
}
}
j++;
// Check all paths from the
// ith indexed city
if (j == tsp.GetLength(0))
{
sum += min;
min = int.MaxValue;
visitedRouteList.Add(route[counter] - 1);
j = 0;
i = route[counter] - 1;
counter++;
}
}
// Update the ending city in array
// from city which was last visited
i = route[counter - 1] - 1;
for(j = 0; j < tsp.GetLength(0); j++)
{
if ((i != j) && tsp[i, j] < min)
{
min = tsp[i, j];
route[counter] = j + 1;
}
}
sum += min;
// Started from the node where
// we finished as well.
Console.Write("Minimum Cost is : ");
Console.WriteLine(sum);
}
// Driver Code
public static void Main(String[] args)
{
// Input Matrix
int[,] tsp = { { -1, 10, 15, 20 },
{ 10, -1, 35, 25 },
{ 15, 35, -1, 30 },
{ 20, 25, 30, -1 } };
// Function call
findMinRoute(tsp);
}
}
Question- 5) Explain coin exchange problems using a greedy approach?
Answer: You have given an amount M and you want to change for that value and you have infinite supply of each of the denomination in Indian Currency(let's consider) i.e. {1,2,5,10,20,50,100,500,2000) valued notes and coins so we need to find out what is the minimum number of notes required to make the change equals to the given value M.
Pseudo code:
COIN-CHANGE-GREEDY(n) //n is the input value i.e. the value whose change needs to be calculated
coins = [20, 10, 5, 1]
i = 0
while (n)
if coins[i] > n
i++
else
print coins[i]
n = n-coins[i]Let's take an example to understand it better
Suppose you have amount =181 and you want to convert it into change
Step 1:
Find the denomination which is nearer but smaller to the given number from the given denomination set. In this case it is 100.
Step 2:
Create an empty array and add 100 in the array now subtract 100 from the amount 181-100= 81. Now repeat steps 1 and 2 until you get an amount as zero.
So Arr={100}
81 -50=31
Arr={100,50}
31-20=11
Arr={100,50,20}
11-10=1
Arr= {100,50,20,10}
1 – 1 =0
Arr= {100,50,20,10,1}
So, for 181 the change with minimum notes/coin is 5
Code implementation:
// C++ program to find minimum
// number of denominations
#include <bits/stdc++.h>
using namespace std;
// All denominations of Indian Currency
int deno[] = { 1, 2, 5, 10, 20,
50, 100, 500, 1000 };
int n = sizeof(deno) / sizeof(deno[0]);
void findMin(int V)
{
sort(deno, deno + n);
// Initialize result
vector<int> ans;
// Traverse through all denomination
for (int i = n - 1; i >= 0; i--) {
// Find denominations
while (V >= deno[i]) {
V -= deno[i];
ans.push_back(deno[i]);
}
}
// Print result
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
}
// Driver program
int main()
{
int n = 93;
cout << "Following is minimal"
<< " number of change for " << n
<< ": ";
findMin(n);
return 0;
}Question- 6) Explain Dijkstra's Algorithm?
Answer: Dijkstra's Algorithm is a shortest path algorithm used to find the shortest path from source to all the possible vertices present in the graph. The algorithm used a greedy approach to solve this problem. It is one of the most efficient algorithms but is not efficient to deal with negative weighted graph
The time complexity for all V vertices is V * (E*logV) i.e O(VElogV).
Notation:
G =Weighted directed graph
S= Set of vertices
w (u, v) = the weight
Pseudo code:
of the edge between u and v
s=source vertex
DIJKSTRA (G, w, s)
Initialize-single source (G, s)
S=Φ
Q=G.V
While Q != Φ
U=EXTRACT-MIN(Q)
S=S U {u}
for each vertex v € G.Adj[u]
RELAX(u,v,w)Consider the below graph:
We will be using Dijkstra's algorithm to find the shortest distance from vertex V1 to all other.
V1 | V2 | V3 | V4 | V5 | V6 |
0 | ∞ | ∞ | ∞ | ∞ | ∞ |
As our starting vertex is V1 so choose V1 and explore all the possible vertex that can be accessed through V1
V2 | V3 | V4 | V5 | V6 |
2 |