Greedy

Definition

Greedy algorithms make locally optimal choices at each step, aiming to find the overall optimal solution.

The "making change" scenario, where a cashier, when asked to give change with the fewest coins, selects the largest coin denomination at each step until the correct change is reached.

Despite not considering the global picture, this strategy often leads to an efficient and reasonably optimal solution.

Prefix-free codes

Prefix-free codes, also known as "unambiguous codes" or "prefix codes," are a type of uniquely decodable code used in information theory and data compression. In a prefix-free code, no codeword is a prefix of another codeword.

This property ensures that a sequence of encoded symbols can be uniquely and unambiguously decoded without the need for delimiter symbols or spaces between codewords.

An example of a prefix-free code is the Huffman coding algorithm, which generates variable-length prefix codes based on the frequency of symbols in the input. The resulting code is efficient in terms of both compression and decoding.