Greedy Algorithm

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
    • Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
    • Union: Join two subsets into a single subset.
  • 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.
  • 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

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.

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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: