Greedy Algorithms

This summary is based on <<Introduction to Algorithms>>, Third Edition

Characteristics:

  • Take the optimal choice at each step, thus leading to globally optimal solution in the end
  • Similar to dynamic programming, but merely takes only one greedy choice for the subproblems, without considering and comparing all of the subproblems.
  1. Activity selection: we have a collections of activities S={a1,a2,…,an} that share the same room, but the room can only be taken by one activity for one time. Every activity a_i has a start time s_i and finishing time f_i. Suppose that the activities’ finishing time’s are sorted in ascending order. The goal is to select a maximum number of activities for the room.
  • Denote S_{ij} as the collection of the activities that start after the finishing time of a_i and ends before the starting time of a_j. Denote c[i,j] as the number of activities in such a collection.
  • DP recursive formula: c[i,j] = max(c[i,k]+c[k,j]+1) for a_k in S_{ij} if S_{ij} is not empty. c[i,j] = 0 if S_{ij} is empty.
  • Greedy choice: always choose the activity that ends as early as possible
Recursive-activity-selector(s,f,k,n):
    m = k+1
    while m&lt;=n and s[m]&lt;f[k]: //find the first activity in S_k to finish
        m=m+1
    if m&lt;=n:
        return a_m+Recursive-activity-selector(s,f,m,n)
    else:
        return empty set 

Greedy-activity-selector(s,f):
    n = s.length
    A = {a1}
    k = 1 for m=2 to n:
        if s[m]&gt;=f[k]:
            A = A + a_m
            k = m
    return A

2. Huffman code: Details can be seen in chapter 16 of the book

HUFFMAN(C):
    n = |C|
    Q = C
    allocate a new node z
    z.left = x = EXTRACT-MIN(Q) // choose the node with the smallest frequency in each step
    z.right = y EXTRACT-MIN(Q)
    z.freq = x.freq + y.freq
    INSERT(Q,z)
    return EXTRACT-MIN(Q)

 

Proof techniques of greedy algorithms:

  1. Greedy always stay ahead: By induction, we can prove that greedy algorithms always give us the optimal solution from the very first step to the end.
  2. Local swap: it’s always safe to include one greedy choice in the optimal solution. For any optimal solution OPT assumed, construct an OPT’ that is not worse than OPT, but also includes the greedy choice. (swap one choice in OPT with a greedy choice and argue that the swap does not make things worse)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s