PadhaikoAll subjects

Greedy Algorithms

Analysis of Algorithms (ENCT 388)

Open in the Padhaiko app

4.1 Basic concepts

A greedy algorithm builds a solution step by step, always making the choice that looks best at the current moment (a locally optimal choice) without reconsidering previous choices, hoping this sequence leads to a globally optimal solution.

Definition

Two Essential Properties for Greedy Optimality

For a greedy algorithm to guarantee a globally optimal solution, the problem must exhibit two properties:

  1. Greedy-Choice Property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice first, without solving all subproblems beforehand.
  2. Optimal Substructure: An optimal solution to the whole problem contains within it optimal solutions to its remaining subproblems.
AspectGreedy MethodDynamic Programming
Decision StrategyMakes one irreversible locally optimal choice at each stepEvaluates all choices across overlapping subproblems
DirectionTop-down (commit choice, reduce to one smaller subproblem)Typically bottom-up (or memoized top-down)
Subproblem DependencyChoice does not depend on subproblem solutionsChoice depends directly on solutions to subproblems
Speed vs. GeneralityFaster ( typical) when valid, but works on fewer problemsBroader applicability, usually or

4.2 Fractional knapsack problem

Given items where item has weight and value/profit , and a knapsack of capacity , select fractions to:

Greedy Strategy: Compute the value-to-weight ratio for each item and sort items in non-increasing order of . Take as much of the highest-ratio item as fits; if the remaining capacity , take fraction and stop.

Fractional Knapsack AlgorithmC
// Items must be pre-sorted in decreasing order of profit[i] / weight[i]
double fractionalKnapsack(int n, double weight[], double profit[], double W) {
    double totalProfit = 0.0, rem = W;
    for (int i = 0; i < n && rem > 0; i++) {
        if (weight[i] <= rem) {
            totalProfit += profit[i];
            rem -= weight[i];
        } else {
            totalProfit += profit[i] * (rem / weight[i]);
            rem = 0;
        }
    }
    return totalProfit;
}

4.3 Job sequencing with deadlines

Given unit-time jobs, where job has a deadline and profit (earned only if completed by time , with at most one job scheduled per unit time slot ), find a feasible subset of jobs maximizing total profit.

Greedy Strategy:

  1. Sort all jobs in non-increasing order of profit .
  2. Maintain an array of time slots slot[1 .. d_max] (initially empty).
  3. For each job in sorted order, scan backward from down to and assign job to the latest free slot (leaving earlier slots open for tighter-deadline jobs).
Job Sequencing with DeadlinesC
int jobSequencing(int n, int deadline[], int profit[], int maxD) {
    // Assumes jobs are sorted in decreasing order of profit[]
    int slot[maxD + 1];
    for (int t = 0; t <= maxD; t++) slot[t] = -1;
    int totalProfit = 0;
    for (int i = 0; i < n; i++) {
        int limit = (deadline[i] < maxD) ? deadline[i] : maxD;
        for (int t = limit; t >= 1; t--) {
            if (slot[t] == -1) {
                slot[t] = i;
                totalProfit += profit[i];
                break;
            }
        }
    }
    return totalProfit;
}
Example 1

1 (6 marks)

  1. Solve the Fractional Knapsack instance with and items .
  2. Find the optimal schedule and maximum profit for Job Sequencing with Deadlines given jobs:
    • , , , , .

Fractional Knapsack (): Compute profit-to-weight ratios :

  • Item 1:
  • Item 2:
  • Item 3:

Already sorted in decreasing ratio order ():

  • Take all of Item 1 (, profit , remaining ).
  • Take all of Item 2 (, profit , remaining ).
  • Take fraction of Item 3 (profit , remaining ).

Total maximum profit .

Job Sequencing with Deadlines (): Sort jobs by profit descending: , , , , . Initialize 3 unit slots :

  • : assign to latest free slot Slot 2 ([_, J1, _]).
  • : Slot 2 taken, assign to Slot 1 ([J3, J1, _]).
  • : Slot 1 taken rejected.
  • : Slot 1 taken rejected.
  • : assign to Slot 3 ([J3, J1, J5]).

Optimal sequence is with total profit .

Answer:
  1. Fractional Knapsack optimal vector gives total profit .
  2. Optimal job schedule is in slots with total profit .

4.4 Analysis of minimum spanning trees related algorithms

A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is an acyclic subset connecting all vertices (so ) with minimum total edge weight .

Theorem

Cut Property (Safe-Edge Theorem)

Let be any partition (cut) of the vertices of such that no edge in a partial MST crosses the cut. If is a light edge crossing (minimum weight among all edges with one endpoint in and one in ), then is safe to add to (it belongs to some MST extending ).

Kruskal's Algorithm

Kruskal's algorithm grows a forest of trees by processing edges globally in increasing weight order:

  1. Sort all edges in non-decreasing order of weight .
  2. Initialize disjoint singleton sets (MAKE-SET(v)).
  3. For each edge in sorted order: if FIND-SET(u) != FIND-SET(v), add to and execute UNION(u, v) (otherwise skip to avoid a cycle).

Prim's Algorithm

Prim's algorithm grows a single tree starting from an arbitrary root :

  1. Initialize key[v] = infinity for all , key[r] = 0, and insert all vertices into a min-priority queue .
  2. While is non-empty, extract .
  3. For each neighbor of still in : if , set and DECREASE-KEY(v, w(u, v)).
AspectKruskal's AlgorithmPrim's Algorithm
Growth PatternGrows a forest of trees merged globallyGrows a single tree from start vertex
Core Data StructureEdge sorting + Disjoint-Set Union (Union-Find)Min-Priority Queue (Binary Heap / Array / Fibonacci Heap)
Time Complexity array; binary heap; Fibonacci heap
Best Graph DensitySparse graphs ()Dense graphs (, with array/Fib heap)
Example 2

2 (7 marks)

Find the Minimum Spanning Tree (MST) and its total weight for the -vertex undirected graph with vertices and weighted edges:

using Kruskal's algorithm, and verify the same MST weight via Prim's algorithm starting at .

Kruskal's algorithm (edges sorted by weight): Sorted edges: , , , , , , , , .

  1. Add weight — components: .
  2. Add weight — merges .
  3. Add weight — merges .
  4. Add weight — merges .
  5. Skip weight — and already in (would form cycle ).
  6. Add weight — merges with into one spanning tree ( edges). Remaining cross edges and are heavier, so is optimal. Total MST weight .

Prim's algorithm starting from :

  • Start: . Lightest edge out of : .
  • Out of : , , , pick .
  • Out of : , , pick .
  • Out of : , pick .
  • Out of : (vs ) pick .

Edges selected: , identical to Kruskal's with total weight .

Answer:

Both Kruskal's and Prim's algorithms select the MST edges with total minimum weight .


4.5 Analysis of single source shortest path algorithm

Given a weighted directed (or undirected) graph with edge weights and a source vertex , Dijkstra's algorithm finds the shortest-path weight from to every vertex .

Definition

Dijkstra's Greedy Relaxation Principle

Dijkstra's algorithm maintains a set of vertices whose final shortest-path weights from are already determined, and a min-priority queue keyed by current distance estimates (, for ). At each step:

  1. Extract with minimum and add to .
  2. Relax each outgoing edge :
Dijkstra's Algorithm (Adjacency Matrix Version)C
void dijkstra(int V, int graph[V][V], int src, int dist[]) {
    int visited[V];
    for (int i = 0; i < V; i++) { dist[i] = 1000000000; visited[i] = 0; }
    dist[src] = 0;
    for (int count = 0; count < V; count++) {
        int u = -1;
        for (int v = 0; v < V; v++)
            if (!visited[v] && (u == -1 || dist[v] < dist[u])) u = v;
        if (u == -1 || dist[u] == 1000000000) break;
        visited[u] = 1;
        for (int v = 0; v < V; v++) {
            if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
        }
    }
}

Complexity & Negative-Weight Limitation:

Example 3

3 (7 marks)

Run Dijkstra's algorithm from source vertex on the directed weighted graph with vertices and directed edges:

Show the distance table after each vertex extraction.

Initialization and iterations: Initially , .

Dijkstra Shortest-Path Trace from Source S
Extracted Relaxations Performed
Init—
(),
(),
(),
()
()No outgoing edges
Answer:

Shortest path distances from : (e.g., shortest path has total weight ).


Exercises

Exercises — Greedy Algorithms

Question 1

Explain the Greedy-Choice Property and Optimal Substructure. Using the items , , with capacity , prove why sorting greedily by fails when items cannot be split (0/1 Knapsack).

Greedy properties:

  • Greedy-Choice Property: A locally optimal choice at the current step can always be extended to a globally optimal solution, without reconsidering earlier decisions.
  • Optimal Substructure: After making the greedy choice, the optimal solution to the whole problem combines that choice with an optimal solution to the resulting subproblem.

Counterexample on 0/1 Knapsack (): The profit-to-weight ratios are , , :

  • Greedy by picks Item 1 (), then Item 2 (), using capacity ; Item 3 () no longer fits (), yielding profit .
  • Optimal 0/1 solution skips Item 1 and takes (total weight ), yielding profit .
Answer:

Greedy fails on 0/1 Knapsack because choosing Item 1 () leaves capacity, forcing profit , whereas skipping Item 1 and choosing achieves the optimal .

Question 2

Find the optimal solution for the Fractional Knapsack instance with capacity and items:

Computing ratios and sorting descending:

  • Item 1:
  • Item 2:
  • Item 3:
  • Item 4:

Sorted order: Item 1 (), Item 2 (), Item 3 (), Item 4 ().

Greedy selection up to :

  • Take Item 1 completely: , profit , remaining .
  • Take Item 2 completely: , profit , remaining .
  • Take of Item 3: profit , remaining .

Total profit .

Answer:

Take for a maximum profit of .

Question 3

Using the greedy Job Sequencing with Deadlines algorithm, find the optimal schedule and total profit for unit-time jobs with profits and deadlines .

Sorting jobs in decreasing profit order: , , , , . Maximum deadline , so slots are .

Assigning each job to the latest free slot :

  • : assign to Slot 3 .
  • : assign to Slot 1 .
  • : assign to Slot 2 .
  • and cannot fit (all slots are full).

Total profit .

Answer:

Optimal schedule: in slots with maximum profit .

Question 4

Find the Minimum Spanning Tree weight using Kruskal's algorithm on the -vertex undirected graph with edges:

State the asymptotic time complexities of Kruskal's algorithm and binary-heap Prim's algorithm.

Kruskal's algorithm trace (sorted edges): Sorted weights: , , , , , , , , , .

  1. Add
  2. Add
  3. Add
  4. Add
  5. Skip (cycle ).
  6. Add ( edges chosen; stop).

Total MST weight .

Asymptotic complexities:

  • Kruskal's algorithm: (dominated by sorting edges; Union-Find takes ).
  • Prim's algorithm (binary heap): for connected graphs (or with an unsorted array).
Answer:

MST edges: with total weight . Both Kruskal's and binary-heap Prim's algorithms run in time.

Question 5
  1. Trace Dijkstra's algorithm from vertex on the -vertex directed graph with edges:
  1. Give a concrete -vertex example showing why Dijkstra's algorithm fails when an edge has a negative weight.

Dijkstra trace from vertex :

  • Start: .
  • Extract (): , .
  • Extract (): , .
  • Extract (): , .
  • Extract (): (along path ).
  • Extract (): done.

Negative-weight counterexample ( vertices ): Let edges be , , and . Dijkstra extracts , sets and , then extracts first (since ) and permanently finalizes . Later when is extracted, path has length , so Dijkstra misses the true shortest path to .

Answer:
  1. Final shortest distances from vertex : .
  2. With , , , Dijkstra prematurely locks before discovering of length .
← Divide and Conquer AlgorithmsDynamic Programming →