International Collegiate Programming Contest

Greedy Algorithms

This session focuses on greedy algorithms. If you are not familiar with the relevant concepts and algorithms, or you need a refresher, you can use the resources below.

Problem Set

1. Horror Film Night
2. Ornaments on a Tree
3. Assigning Workstations
4. Installing Apps
5. Minimum Scalar Product
6. Bank Queue

Note: All problems expect I/O to be done using standard input and standard output. The solution to problems must be written in a single file. If you are programming in Java the application class should be called "Main".

Resources

Greedy Algorithms

Many computational problems can be cast in the following format: You are given a system consisting of a number of components that each can be set in various ways. Your goal is to set them in such a way that a given objective is optimized. A greedy approach to such a problem iterates over the components in a well-chosen order, and sets them in a way that is locally optimal (according to a well-chosen metric), rather than trying to figure out what will work long-term. Most objectives are too complex for such a myopic approach to yield a global optimum. But if it does, then the resulting algorithm is often very efficient.

Designing a greedy algorithm boils down to determining the order in which to consider the components, and figuring out the right metric. In doing so, it is important to verify that this combination leads to the correct solution - ideally by reasoning about the algorithm (charging arguments, exchange arguments, greedy stays ahead), or else by developing appropriate test cases.

Examples of problems for which a greedy approach exists include: scheduling problems like unweighted interval scheduling and minmizing maximum lateness, off-line caching, Huffman codes, shortest paths with nonnegative lengths, minimum spanning trees. See this tutorial for more examples.