SUNY Geneseo Department of Computer Science

Greedy Algorithms

Return to List of Lectures

Misc

Exam 2 is next Thursday (April 11)

• Material since 1st exam (e.g., dynamic programming, shortest-path algorithms, greedy algorithms, minimum spanning trees)
• Rules and format otherwise similar to 1st exam, esp. open-references rules

Questions?

Greedy Algorithms

Example: I want to put my most favorite songs on a CD, which holds a total of C songs (oddly, they’re all the same length). I have a collection of S > C songs, each with a rating, r_i, of how much I like song s_i. Give and prove correct a strategy for creating a CD with the maximum total rating for the songs it contains.

• Algorithm (typically the easy part with greedy algorithms)

        while CD not full
            find highest-rated song, s, not yet on CD
            burn s to CD

• Proof (theorem: first n songs put on CD have highest total rating of any set of n songs)
  • Induction on n
  • Induction hypothesis: the first k songs have the highest total rating for any set of k songs
  • Show that the first k+1 songs burned to the CD must therefore have the highest total rating of any set of k+1 songs
    • Lemma: the set, O, containg the k+1 highest-rated songs is optimal, i.e., has highest total rating of any (k+1)-song set
      • Let X be a set of k+1 songs ≠ O
      • So at least one song from O must be missing from X and replaced with something rated no higher, so total rating of X must be no higher than total rating for O, i.e., O is an optimal set.
  • Base case: n = 1
    • Highest rated song clearly has a rating equal to or higher than the rating of any other single song
• Most greedy algorithms can be proven correct by proven something analogous to the above lemma, i.e., proving that the solution constructed by the algorithm is equivalent to any hypothetical optimal solution. Authors typically don’t do the full induction.

Running time of above algorithm if it starts by sorting S songs by rating

    sort S songs into decreasing order by rating    // Θ(S logS) time
    i = 0
    while CD not full                               // C songs to fill CD, Θ(C) time
        burn sortedSongs[i] to CD

• Time is Θ( C + SlogS )
• Or, realizing that C < S, O( S + SlogS ) = O(SlogS)

Now suppose songs have different lengths, s_i lasts m_i minutes, CD holds M minutes

• Counter-example, showing that the greedy strategy of burning songs in decreasing order of rating doesn’t necessarily work
• Consider 2 minute CD
  • s₁ lasts 2 minutes w/ rating 10
  • s₂ lasts 1 minute w/ rating 9
  • s₃ lasts 1 minute w/ rating 3
• Greedy strategy would put s₁ with total rating 10 on CD, but one could put s₂ and s₃ with total 12 on
• This sort of counter-example is typical of proofs that greedy algorithms don’t solve a problem

Could we solve this version of the CD problem by dynamic programming?

• R(M,S) = max rating achievable for M minutes of CD with songs 1 .. S
  • = max( R(M-m_S,S-1) + r_S, R(M,S-1) ) if M ≥ m_S and S > 0
  • = R(M,S-1) if M < m_S and S > 0
  • = 0 if S = 0

Hand out greedy algorithms problem set

Next

Minimum spanning trees

• i.e., trees made from the edges of a graph that connect all of its vertices and have minimal total edge weight

Chapter 23