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. Building Fences
3. Fair Division
4. Assigning Workstations
5. Installing Apps

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, or else by developing appropriate test cases.

Examples of problems for which a greedy approach works include: shortest paths in graphs with nonnegative weights (Dijkstra's algorithm, which makes its decisions based on minimum distance) and minimum spanning trees (Prim's algorithm, which makes its decisions based on minimum edge weight).