International Collegiate Programming Contest

Divide & Conquer and Search

This session focuses on binary search, divide and conquer, and state space search. 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. Cantor
2. Gregory the Grasshopper
3. Frosh Week
4. Arachnophobia
5. Blazing New Trails
6. Popping Balloons

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" and should be in the default package.

Resources

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. This tutorial has a good discussion of binary search and its applications and implementation.

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 significantly 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). In many cases, you can quickly figure out the running time of a Divide and Conquer algorithm by analyzing the recursion tree and aggregating the work done per level. As recursive algorithms in general are diverse, there are many variants on Divide and Conquer. Keep an open mind while working! These slides have good information on Divide and Conquer algorithms.

Searching State Spaces

Imagine you are playing a game. At any point the game has some state, and some moves you could follow to go to one of a number of different states. You need to know whether, or how fast, you can get from a given start state to a given end state. How do you figure this out?

In general this is a difficult problem, and unless your game has some very nice properties that allow you to greatly simplify it, there is not much else you can do besides "brute force". The (intelligent) implementation of such a brute force tactic often takes the form of a breadth-first search on the state space graph of the game, where vertices correspond to the states, and directed edges correpond to moves that take you from one state space to another. Often this graph will be very large -- so large that computing all the vertices and edges in the graph is prohibitively expensive -- but you are still interested in trying to find paths through the graph. This tutorial discusses state space search, including breadth-first style and beyond.

Meet in the Middle

Meet in the middle is a classic trick to speed up brute force algorithms. The main idea is to split the state into two halves and efficiently combine the possibilities for the two halves, often through the use of appropriate data structures. You can find an example here with the corresponding problem here.

Fast Fourier Transform and friends

The Fast Fourier Transform (FFT) is a divide-and-conquer algorithm to compute the discrete Fourier Transform (DFT) and is considered by some as the most important among all algorithms. This is due to the prevalence of convolutions, or equivalently, products of polynomials described by their sequence of coefficients. The FFT enables computing such products of polynomials of degree n in time O(n log n), improving over the O(n²) time of the straightforward approach.

The DFT and FFT involve complex numbers and therefore require operations with reals and accuracy considerations. There exists an equivalent of the DFT over prime fields (integers modulo a prime p), and a similar divide-and-conquer strategy as the FFT, called the Number Theoretic Transformation (NTT). The NTT only involves operations on integers modulo p, and works for polynomials up to degree n, where 2ⁿ is the largest power of 2 that divides p-1. See this tutorial for more information.