Greedy Algorithms

Minimum Product Subset of an array

For a given array of elements, we have to find the non-empty subset having the minimum product. We will explore two techniques brute force O(2^N) and Greedy algorithm O(N)

algorithm

Maximum Product Subset of an array

For a given array of elements, we have to find the non-empty subset having the maximum product. We will explore two techniques brute force O(2^N) and Greedy algorithm O(N)

algorithm

Greedy approach to find a single maximal clique in O(V^2) time complexity

There can be more than one single maximal clique in a non-complete graph (since complete graph is a maximal clique itself). To find a single maximal clique in a graph we use a straightforward greedy algorithm in O(V^2) time complexity

algorithm

Divide numbers from 1 to n into two groups with minimum sum difference from O(2^N) to O(N)

For numbers from 1 to given n, we have to find the division of the elements into two groups having minimum absolute sum difference. We will explore two techniques Brute force which will take O(2^N) time complexity and Greedy algorithm which will take O(N) time complexity

algorithm

Activity Selection Problem using Greedy algorithm

For activity selection, Dynamic Programming Approach takes O(n^3) time while Greedy Approach takes O(n) time when unsorted and O(n log n) when sorted. It follows Greedy approach as at every step, we make a choice that looks best at the moment to get the optimal solution of the complete problem

graph colouring

Graph Coloring Greedy Algorithm

In this article, we have explored the greedy algorithm for graph colouring. graph coloring is a special case of graph labeling ; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

graph algorithm

Kruskal Minimum Spanning Tree Algorithm

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step