The Greedy Paradigm

Construct a solution iteratively, via a sequence of myopic decisions, and hope that everything works out in the end.

Features and Bugs of the Greedy Paradigm

- Easy to come up with one or more greedy algorithms
- Easy to analyze the running time
- Hard to establish correctness

Warning: most greedy algorithm are not always correct.

## A Scheduling Problem

In scheduling, the jobs have different length, which is the amount of time required to process the job, also each job has a weight, with higher weights corresponding to higher-priority jobs.

These two scoring functions lead to two different greedy algorithms:

- GreedyDiff: schedule the jobs in decreasing order of (weight — length)
- GreedyRatio: schedule the jobs in decreasing order of (weight/ length)

XOR is a logical bitwise operator that returns 0 (false) if both bits are the same and returns 1 (true) otherwise. In other words, it only returns 1 if exactly one bit is set to 1 out of the two bits in comparison.