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

4 thought

Cantor

Closest Pair

Gregory the Grasshopper

Medals
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.
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 on Topcoder
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:
 Take your problem of size N and divide it into a number of subproblems
of smaller size.
 Solve each of the subproblems recursively.
 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! 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
breadthfirst search on the space of states of the game.
You can imagine the states of the game being the vertices of a graph, with directed
edges correponding 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. The general approach is to search, breadthfirst,
along the edges of the graph, finding edges dynamically by computing how applying
each move would change the current state. Since it is often too difficult to keep all
possible states in memory, instead one can store encodings of all the previouslyvisited
states in a selfbalancing tree in order to relatively quickly check whether a state has
been visited before, so as to avoid wasting time repeating alreadycompleted searching.
This page
discusses state space search, both depthfirst and breadthfirst style. It also has a (small)
illustrated example.
