Scribd
Upload
12 views4 pages

Program 8

The document describes two algorithms: one for finding subsets of a set of positive integers that sum to a given target, and another for finding the Minimum Cost Spanning Tree of a connected undirected graph using Prim's algorithm. The first algorithm is implemented in Python, while the second is provided in C. Example usages for both algorithms are included to demonstrate their functionality.

Uploaded by

Zeenath Jahan Begum
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
12 views4 pages

Program 8

The document describes two algorithms: one for finding subsets of a set of positive integers that sum to a given target, and another for finding the Minimum Cost Spanning Tree of a connected undirected graph using Prim's algorithm. The first algorithm is implemented in Python, while the second is provided in C. Example usages for both algorithms are included to demonstrate their functionality.

Uploaded by

Zeenath Jahan Begum
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Program 8

8. Design an algorithm and implement a program to find a subset of a given set S = {Sl,
S2,.,Sn} of n positive integers whose SUM is equal to a given positive integer d. For
example, if S ={1, 2, 5, 6, 8} and d= 9, there are two solutions {1,2,6}and {1,8}. Display a
suitable message, if the given problem instance doesn't have a solution.

def subset_sum_recursive(nums, target_sum, index, path, result):

if target_sum == 0:

result.append(path)

return

if index >= len(nums) or target_sum < 0:

return

# Include the current number

subset_sum_recursive(nums, target_sum - nums[index], index + 1, path + [nums[index]],


result)

# Exclude the current number

subset_sum_recursive(nums, target_sum, index + 1, path, result)

def find_subsets_sum_to_d(nums, d):

result = []

subset_sum_recursive(nums, d, 0, [], result)

return result

# Example usage

S = [1, 2, 5, 6, 8]
d=9

subsets = find_subsets_sum_to_d(S, d)

if subsets:

print(f"Subsets that sum up to {d} are:")

for subset in subsets:

print(subset)

else:

print("No subset found that sums up to the target sum.")


9. Find Minimum Cost Spanning Tree of a given connected undirected
graph using Prim's algorithm
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define V 5
int minKey(int key[], bool mstSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
int printMST(int parent[], int graph[V][V])
{
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
printf("%d - %d \t%d \n", parent[i], i,
graph[i][parent[i]]);
}
void primMST(int graph[V][V])
{
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;

parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}
int main()
{
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
// Print the solution
primMST(graph);
return 0;
}

You might also like