## Greedy Algorithm

- Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.
- At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.
- If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem
- Greedy algorithms cannot always be applied.

### Kruskal’s Minimum Spanning Tree

- Given a connected and undirected graph, a
*spanning tree*of that graph is a subgraph that is a tree and connects all the vertices together. - A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree.
- A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.
- Algo
- Sort all the edges in non-decreasing order of their weight.
- Pick the smallest edge. Check if it forms a cycle with the spanning tree

formed so far.- If cycle is not formed, include this edge.
- Else, discard it.

- Repeat step#2 until there are (V-1) edges in the spanning tree.

Cycle Detection in undirected graph (Union Find Method)

- A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
- Performs two useful operations on such a data structure
Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.**Find:**Join two subsets into a single subset.**Union:**

- This method assumes that graph doesn’t contain any self-loops.
- We can keeps track of the subsets in a 1D array, lets call it parent[].

### Huffman Coding:

- Lossless data compression algorithm.
- The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters.
- The most frequent character gets the smallest code and the least frequent character gets the largest code.
- The variable-length codes assigned to input characters are Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to one character is not prefix of code assigned to any other character
- Two major parts in Huffman Coding
- Build a Huffman Tree from input characters.
- Build Maximum Heap Tree
- Right child edge have 1, left have 0 ( a => 0011)

- Traverse the Huffman Tree and assign codes to characters.

- Build a Huffman Tree from input characters.
- Complexity O(nLogn)

### Prim’s MST:

- It starts with an empty spanning tree.
- The idea is to maintain two sets of vertices.
- The first set contains the vertices already included in the MST,
- The other set contains the vertices not yet included.

- It considers all the edges that connect the two sets, and picks the minimum weight edge from these edges.
- After picking the edge, it moves the other endpoint of the edge to the set containing MST.

### Dijkstra’s Shortest Path Algo:

- We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree.
- At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has minimum distance from source.
- Algorithm
- Create a set
*sptSet*(shortest path tree set) that keeps track of vertices included in shortest path tree - Assign a distance value to all vertices in the input graph.
- Initialize all distance values as INFINITE and assign distance value as 0 for the source vertex so that it is picked first.

- Pick vertex with min distance which is 0 then update all connected vertices distance from source to main set.
- Update Parent as source in another set of parent
- Distance formula D+w

- Create a set

Job Sequencing Problem

- Given an array of jobs each job have a deadline and profit if completed in time.
- Maximise the profit
- Single job run at a time
- Algorithm
- Greedy Approach
- Sort all jobs in decreasing order of profit.
- Initialize the result sequence as first job in sorted jobs.
- Do following for remaining n-1 jobs
- If the current job can fit in the current result sequence without missing the deadline, add current job to the result.
- Else ignore the current job.

- Disjoint Approach
- All time slots are individual sets initially.
- We first find the maximum deadline of all jobs. Let the max deadline be m. We create m+1 individual sets.
- If a job is assigned a time slot of t where t => 0, then the job is scheduled during [t-1, t].
- So a set with value X represents the time slot [X-1, X].

- We need to keep track of the greatest time slot available which can be allotted to a given job having deadline.
- We use the parent array of Disjoint Set Data structures for this purpose.
- The root of the tree is always the latest available slot.
- If for a deadline d, there is no slot available, then root would be 0.

- Greedy Approach

Minimum No of Coins for change

- Initialize result as empty.
- find the largest denomination that is smaller than V.
- Add found denomination to result. Subtract value of found denomination from V.
- If V becomes 0, then print result.
- Else repeat steps 2 and 3 for new value of V

- Failure case : for 11 this will print 9,1 and 1 but answer can be 5 and 6

Advertisements

## Leave a Reply