Algorithms For Dummies

  Working with Greedy Algorithms 

     295

Apart from graphically drafting the unbalanced structure, a greedy algorithm can 

also construct an unbalanced tree. The idea is to build the structure up from the 

root, starting with the least frequently used characters. The algorithm creates the 

upper levels of the tree by aggregating less frequent characters in sequence until 

there are no more characters and you reach the top.

To demonstrate the greedy recipe behind the algorithm, this section provides a 

Python code example based on DNA. DNA is represented as a sequence of the let-

ters A, C, T, and G (the four nucleotides present in all living beings). A good trick is 

to use just two bits in order to represent each of the four letters, which is already 

a good memory-saving strategy when compared to using a full ASCII encoding 

(which is at least 7 bits).

The nucleotides aren’t uniformly distributed. The distribution varies depending 

on what genes you study. The following table shows a gene with an uneven distri-

bution, allowing for a predominance of A and C nucleotides.