Problem solving techniques (Example problems) (Cont.)

In this post i will show you how to use the greedy approach, solving specific set of problems that may match a specific property. You may need to visit this post in order to understand the whole idea.

In the last post we discussed how to use DP technique to solve problems, Greedy and DP techniques are to solve optimization problems "Those which asks to find the optimal solution" (e.g., Finding the shortest path, min cost, or max profit).

Problem 8 (Activity Selection Problem)

In this problem we are given set of competing activities that require exclusive use of a common resource, with a goal of selecting a maximum size set of mutually compatible activities.

Suppose we have a set S = {a1, a2, ...., an} of n proposed activities that wish to use a resource, such as a lecture hall, which can be used by only one activity at a time. Given the start, and finish time of each task, Select the maximum size subset of manually compatible activities.

Solution

Sort the tasks in monotonically increasing finish time. By default include the first activity in our result subset, Then loop all other activities comparing it with the last included activity, if its not overlapped include it.

struct Activity {
    int stime, ftime;
};

bool operator < (const Activity& a1, const Activity& a2) {
    return a1.ftime < a2.ftime;
}

vector<Activity> greedy_activity_selector(vector<Activity> activities) {
   
    vector<Activity> res(1);
    int i, j = 0;
   
    sort(activities.begin(), activities.end());
    res[0] = activities[0];
   
    for(i = 1; i < activities.size(); i++) {
        if(activities[i].stime >= activities[j].ftime) {
            res.push_back(activities[i]);
            j = i;
        }
    }
   
    return res;
}

Problem 9 (Huffman Codes)

Huffman Codes are a widely used and very effective technique for compressing data: savings of 20% to 90% are typical, depending on the characteristic of the data being compressed. Data considered data to be sequence of characters. In order to understand the whole idea read this.

Huffman's greedy algorithm uses a table of the frequencies of occurrence of the characters to build up an optimal way of representing each character as a binary string.

Example

Frequency in thousands	a	b	c	d	e	f
Variable length code	45	13	12	16	9	5

Tracing Algorithm

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

 Step 6:

Solution

Hufman(C) {
    n = size(C)
    Q = C // Priority queue
   
    for i = 1 to n-1
    do allocate a new node z
        left[z] = x = extract_min(Q)
        right[z] = y = extract_min(Q)
        f[z] = f[x]+f[y]
           
        insert(Q, z)
    done 
    return extract_min(Q)
}

In the next post i will show you how to use backtracking solving specific set of problems.