Introduction to Greedy Algorithm

1.  Greedy Algorithms : Iteratively make "myopic" decisions, hope everything works out at the end.

    Example: Dijkstra's shortest path algorithm (processed each destination once, irrevocably)

 

2.  Contrast with Divide & Conquer

    a)  Easy to propose multiple greedy algorithms for many problems.

    b)  Easy running time analysis.

    c)  Hard to establish correctness. (Most greedy algorithms are NOT correct.)

 

3.  Proofs of Correctness :

    a)  Induction. ( i.e. correctness proof for Dijkstra's algorithm)

    b)  "Exchange argument"

         -- by Contradiction ( to assume there is some optmial algorithms else )

         --  convert the assumed optimial algorithms to the one to be prooved without making it worse

 

4.  The Optimal Caching Algorithm :

    Theorem: The "furthest-in-future" algorithm is optimal (i.e., minimizes the number of cache misses).

    1.  Serves as guideline for practical algorithms (e.g., Least Recently Used (LRU) should do well  provided data exhibits locality of reference).

    2.  Serves as idealized benchmark for caching algorithms.