Design Ch.11

Greedy Technique Overview

• A greedy technique constructs solutions to optimization problems step by step, making locally optimal choices at each step.
• The choices made in each step must be:
  • Feasible: The choice must be valid; it should satisfy the constraints of the problem.
  • Locally optimal: The choice must appear to be the best at that current step.
  • Irrevocable: The choice made cannot be changed later.
• For certain types of problems, a greedy approach can yield optimal solutions for every case.
• For most problems, however, it doesn't always produce optimal solutions but can be useful for creating approximations efficiently.

Applications

• Optimal solutions:
  • Coin change making (with typical denominations).
  • Minimum spanning trees (MST).
  • Single-source shortest paths.
  • Simple scheduling.
  • Huffman codes.
• Approximations:
  • Traveling salesman problem (TSP).
  • Knapsack problem.
  • Other combinatorial optimization problems.

Change-Making Problem

• Given a set of denominations of coins (e.g. 25c, 10c, 5c, 1c), find the smallest number of coins required to make a specific amount of change.
• A greedy approach to this problem may not always be optimal depending on the set of denominations.

Minimum Spanning Tree (MST)

• A spanning tree is a subset of edges of a connected graph that connects all vertices without forming cycles.
• A minimum spanning tree (MST) is a spanning tree with the smallest possible total weight (sum of edge weights).

Prim's Algorithm

• Prim's algorithm is a greedy algorithm for constructing an MST.
• It starts with a single vertex of the graph and adds the closest vertex to the existing subtree, repeatedly, until all vertices are in the tree.
• Prim's algorithm requires a priority queue to efficiently locate the closest fringe vertex at each step.
• Its complexity is O(n^2) for a matrix representation and O(E log V) for an adjacency list representation (using a min heap).

Kruskal's Algorithm

• Kruskal's algorithm is another greedy approach to finding an MST.
• It sorts edges in increasing order of their weights.
• It adds each edge (without cycles) to the minimum spanning tree.
• It uses a concept called union–find algorithms to efficiently determine if adding an edge creates a cycle.

Dijkstra's Algorithm

• Dijkstra's algorithm finds the shortest paths from a single source vertex to all other vertices in a weighted graph.
• It uses a priority queue to find the vertex with the smallest path cost from the source in each step.
• Like Prim's algorithm, its efficiency depends on how the graph is implemented (weight matrix or adjacency list) - O(V^2) or O(E log V)
• It does not work for graphs with negative weights.

Huffman Codes

• Huffman codes are a variable-length encoding method for efficiently encoding characters by assigning shorter codes to more frequent symbols and longer codes to less frequent ones.
• The corresponding encoding algorithm is a greedy algorithm.
• It aims to minimize the average codeword length.