International Collegiate Programming Contest

Greedy and Divide & Conquer

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

Problem Set (#2)

1. Minimal Coverage
2. Station Balance
3. WiFi
4. Frosh Week
5. Workshops
6. Low Power

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).

Binary Search

Binary search is an efficient way of searching through an ordered set of objects to find one that you are interested in (or find that it doesn't exist). The classic example is searching through an ordered array, but there are many other ways to apply binary search: finding a value in the range of a nondecreasing function, for instance, or searching for the smallest "good" number in a range, where you know that if a number is "good", then so are all larger numbers.

The basic algorithm is this: you have a search space you are looking through. You take the midpoint of your search space, test it, and use that information to narrow your search space down to half the size; either on one side of the midpoint or the other. Check out the wikipedia page for more information here.

Divide and Conquer

Divide and Conquer is a name for a class of recursive methods for solving problems. Each recursive step looks something like the following:

1. Take your problem of size N and divide it into a number of subproblems of smaller size.
2. Solve each of the subproblems recursively.
3. Combine the solutions of the subproblems into a solution to the original problem.

Often, we break the problem into two subproblems of half the size each, and steps 1 and 3 take O(N) time. In this case, Divide and Conquer results in a running time of O(N log N). This isn't always the case; in general, you can use the master theorem or just analyze the recursion tree to find the running time of a Divide and Conquer algorithm. As recursive algorithms in general are diverse, there are many variants on Divide and Conquer. Keep an open mind while working!

There are a couple classical divide and conquer solutions that appear in ICPC. Counting Inversions appears often as well as the Closest Pair of Points problem in the plane.

Ternary Search

Ternary search is an extension of binary search and occasionally comes up in ICPC. If you are given a function that is not increasing or decreasing, but instead convex or concave, it is possible to find the maximum or minimum of the function via ternary search, in logarithmic complexity. The idea is instead of picking a single midpoint, we instead pick two. Based on the values of the function at these midpoints, either the leftmost or rightmost tri-section can be pruned. The details of ternary search can be found here.