Greedy Algorithm
The greedy method is one of the strategies like Divide and conquer used to solve the
problems. This method is used for solving optimization problems. An optimization problem
is a problem that demands either maximum or minimum results. Let's understand through
some terms.
The Greedy method is the simplest and straightforward approach. It is not an algorithm, but
it is a technique. The main function of this approach is that the decision is taken on the
basis of the currently available information. Whatever the current information is present, the
decision is made without worrying about the effect of the current decision in future.
This technique is basically used to determine the feasible solution that may or may not be
optimal. The feasible solution is a subset that satisfies the given criteria. The optimal
solution is the solution which is the best and the most favorable solution in the subset. In the
case of feasible, if more than one solution satisfies the given criteria then those solutions
will be considered as the feasible, whereas the optimal solution is the best solution among
all the solutions.
Characteristics of Greedy method
The following are the characteristics of a greedy method:
o To construct the solution in an optimal way, this algorithm creates two sets where
one set contains all the chosen items, and another set contains the rejected
items.
o A Greedy algorithm makes good local choices in the hope that the solution
should be either feasible or optimal.
Components of Greedy Algorithm
The components that can be used in the greedy algorithm are:
o Candidate set: A solution that is created from the set is known as a candidate
set.
o Selection function: This function is used to choose the candidate or subset
which can be added in the solution.
o Feasibility function: A function that is used to determine whether the candidate
or subset can be used to contribute to the solution or not.
o Objective function: A function is used to assign the value to the solution or the
partial solution.
o Solution function: This function is used to intimate whether the complete
function has been reached or not.
Pseudo code of Greedy Algorithm
1. Algorithm Greedy (a, n)
2. {
3. Solution : = 0;
4. for i = 0 to n do
5. {
6. x: = select(a);
7. if feasible(x)
8. {
9. Solution: = union(solution , x)
10. }
11. return solution;
12. }
13. }
Huffman Coding
Huffman Coding is a technique of compressing data to reduce its size without
losing any of the details. It was first developed by David Huffman.
Huffman Coding is generally useful to compress the data in which there are
frequently occurring characters.
How Huffman Coding works?
Suppose the string below is to be sent over a network.
Initial string
Each character occupies 8 bits. There are a total of 15 characters in the
above string. Thus, a total of 8 * 15 = 120 bits are required to send this string.
Using the Huffman Coding technique, we can compress the string to a smaller
size.
Huffman coding first creates a tree using the frequencies of the character and
then generates code for each character.
Once the data is encoded, it has to be decoded. Decoding is done using the
same tree.
Huffman Coding prevents any ambiguity in the decoding process using the
concept of prefix code ie. a code associated with a character should not be
present in the prefix of any other code. The tree created above helps in
maintaining the property.
Huffman coding is done with the help of the following steps.
1. Calculate the frequency of each character in the string.
Frequency of string
2. Sort the characters in increasing order of the frequency. These are stored in a
priority queue Q . Characters sorted
according to the frequency
3. Make each unique character as a leaf node.
4. Create an empty node z . Assign the minimum frequency to the left child of z
and assign the second minimum frequency to the right child of z . Set the
value of the z as the sum of the above two minimum frequencies.
Getting the sum of the least numbers
5. Remove these two minimum frequencies from Q and add the sum into the list
of frequencies (* denote the internal nodes in the figure above).
6. Insert node z into the tree.
7. Repeat steps 3 to 5 for all the characters.
Repeat steps 3 to 5 for all the characters.
Repeat steps 3 to 5 for all the characters.
8. For each non-leaf node, assign 0 to the left edge and 1 to the right edge.
Assign 0 to the left edge and 1 to the right edge
For sending the above string over a network, we have to send the tree as well
as the above compressed-code. The total size is given by the table below.
Character Frequency Code Size
A 5 11 5*2 = 10
B 1 100 1*3 = 3
C 6 0 6*1 = 6
D 3 101 3*3 = 9
4 * 8 = 32 bits 15 bits 28 bits
Without encoding, the total size of the string was 120 bits. After encoding the
size is reduced to 32 + 15 + 28 = 75 .
Decoding the code
For decoding the code, we can take the code and traverse through the tree to
find the character.
Let 101 is to be decoded, we can traverse from the root as in the figure below.
Decoding
Huffman Coding Algorithm
create a priority queue Q consisting of each unique character.
sort then in ascending order of their frequencies.
for all the unique characters:
create a newNode
extract minimum value from Q and assign it to leftChild of newNode
extract minimum value from Q and assign it to rightChild of newNode
calculate the sum of these two minimum values and assign it to the
value of newNode
insert this newNode into the tree
return rootNode
Activity Selection Problem
The Activity Selection Problem is an optimization problem
which deals with the selection of non-conflicting activities
that needs to be executed by a single person or machine in a
given time frame.
Each activity is marked by a start and finish time. Greedy
technique is used for finding the solution since this is an
optimization problem
What is Activity Selection Problem?
Let's consider that you have n activities with their start and
finish times, the objective is to find solution set
having maximum number of non-conflicting
activities that can be executed in a single time frame,
assuming that only one person or machine is available for
execution.
Steps for Activity Selection Problem
Input Data for the Algorithm:
act[] array containing all the activities.
s[] array containing the starting time of all the activities.
f[] array containing the finishing time of all the activities.
Ouput Data from the Algorithm:
sol[] array refering to the solution set containing the
maximum number of non-conflicting activities.
Following are the steps we will be following to solve the
activity selection problem,
Step 1: Sort the given activities in ascending order according
to their finishing time.
Step 2: Select the first activity from sorted array act[] and
add it to sol[] array.
Step 3: Repeat steps 4 and 5 for the remaining activities
in act[].
Step 4: If the start time of the currently selected activity is
greater than or equal to the finish time of previously selected
activity, then add it to the sol[] array.
Step 5: Select the next activity in act[] array.
Step 6: Print the sol[] array.
Activity Selection Problem Example
Let's try to trace the steps of above algorithm using an
example:
In the table below, we have 6 activities with corresponding
start and end time, the objective is to compute an execution
schedule having maximum number of non-conflicting
activities:
Start Time (s) Finish Time (f) Activity Name
5 9 a1
1 2 a2
3 4 a3
0 6 a4
5 7 a5
8 9 a6
A possible solution would be:
Step 1: Sort the given activities in ascending order according
to their finishing time.
The table after we have sorted it:
Start Time Finish Time
Activity Name
(s) (f)
1 2 a2
3 4 a3
0 6 a4
5 7 a5
5 9 a1
8 9 a6
Step 2: Select the first activity from sorted array act[] and
add it to the sol[] array, thus sol = {a2}.
Step 3: Repeat the steps 4 and 5 for the remaining activities
in act[].
Step 4: If the start time of the currently selected activity is
greater than or equal to the finish time of the previously
selected activity, then add it to sol[].
Step 5: Select the next activity in act[]
For the data given in the above table,
A. Select activity a3. Since the start time of a3 is greater
than the finish time of a2 (i.e. s(a3) > f(a2)), we add a3 to
the solution set. Thus sol = {a2, a3}.
B. Select a4. Since s(a4) < f(a3), it is not added to the
solution set.
C. Select a5. Since s(a5) > f(a3), a5 gets added to solution
set. Thus sol = {a2, a3, a5}
D. Select a1. Since s(a1) < f(a5), a1 is not added to the
solution set.
E. Select a6. a6 is added to the solution set since s(a6) >
f(a5). Thus sol = {a2, a3, a5, a6}.
Step 6: At last, print the array sol[]
Hence, the execution schedule of maximum number of non-
conflicting activities will be:
(1,2)
(3,4)
(5,7)
(8,9)
In the above diagram, the selected activities have been
highlighted in grey.
