Scribd
Upload
43 views1 page

Greedy Algorithms: Key Concepts & Applications

This document provides a quick revision of greedy algorithms, highlighting their properties and applications. It covers specific problems like the Fractional Knapsack Problem, Minimum Spanning Tree, and algorithms such as Prim's and Kruskal's, including their complexities. The document also discusses the characteristics and limitations of greedy algorithms, noting their efficiency and potential for non-optimal solutions.

Uploaded by

atharvbhavsars
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
43 views1 page

Greedy Algorithms: Key Concepts & Applications

This document provides a quick revision of greedy algorithms, highlighting their properties and applications. It covers specific problems like the Fractional Knapsack Problem, Minimum Spanning Tree, and algorithms such as Prim's and Kruskal's, including their complexities. The document also discusses the characteristics and limitations of greedy algorithms, noting their efficiency and potential for non-optimal solutions.

Uploaded by

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

Module 3 – Greedy Algorithms (Quick Revision

Notes)

Introduction & Properties


• Greedy algorithm: makes best local choice at each step.
• Builds solution step by step (iterative).
• No backtracking – once chosen, decision not changed.
• Efficient and simple but not always optimal.

Fractional Knapsack Problem


• Items can be broken into fractions.
• Choose items with highest profit/weight ratio first.
• Applications: logistics, finance, ML model optimization.
• Complexity: O(n log n) (sorting required).

Minimum Spanning Tree (MST)


• Spanning Tree: connects all vertices with no cycles.
• MST: spanning tree with minimum total edge weight.
• Applications: network design, clustering.

Prim’s Algorithm
• Start with any vertex.
• Add the smallest edge connecting new vertex to tree.
• Repeat until all vertices included.
• Complexity: O(E log V) with binary heap, O(E + V log V) with Fibonacci heap.

Kruskal’s Algorithm
• Sort edges by weight.
• Pick smallest edge that doesn’t form a cycle.
• Repeat until MST formed.
• Complexity: O(E log E) ≈ O(E log V).

Greedy Algorithms – Characteristics & Limitations


• Pros: Simple, fast, efficient in many problems (e.g., Huffman coding, MST).
• Cons: May not give optimal solution (e.g., coin change with tricky denominations).

You might also like