/ software engineering blog by Maryna Savchenko

Reduction. Algorithm Series


Reduction is a basic technique in algorithm design.

A problem A reduces to problem B if we can use an algorithm that solves B to develop an algorithm that solves A.

This concept should be pretty familiar in software development. For example, when you use method evaluate() of Apache Commons library to solve a problem, your problem is reduced to the one solved by library method.

Simple example of reduction would be finding a median in a collection. This operation is a common computation in statistics and in various other data-processing applications.

Finding a median can be reduced to Sorting.

Let’s start with Unit tests that will check two main cases:

    void valueInTheMiddleWhenNumOfObservationsIsOdd() {
        List<Double> dataset = Arrays.asList(12.5, 18.3, 11.2, 19.0, 22.1, 14.3, 16.2, 12.5, 17.8, 16.5, 12.5);

        Double median = Median.getMedian(dataset);

        assertEquals(16.2, median);

    void averageOfMiddleWhenNumOfObservationsIsEven() {
        List<Double> dataset = Arrays.asList(12.5, 18.3, 11.2, 19.0, 14.3, 16.2, 12.5, 17.8, 16.5, 12.5);

        Double median = Median.getMedian(dataset);

        assertEquals(15.25, median);


After test cases are defined, writing implementation (can be found on GitHub) is pretty easy.

    public static Double getMedian(List<Double> input) {
        int size = input.size();
        if (size % 2 == 0) {
            return (input.get(size / 2) + input.get(size / 2 - 1)) / 2;
        } else {
            return input.get(size / 2);

To solve “Finding the median” we used Sorting reduction. Efficient sorting algorithm is useful for efficiently solving many problems. Among them:

A large number of important problems can be solved applying Shortest-paths and Maxflow reductions. Let’s mention them here.

Shortest-paths reductions

Maxflow reductions

Reduction plays important role in studying relationships between diverse problems. Many of the problems seem to be unrelated directly, but at the same time can be reduced to sorting, shortest-paths, maxflow, etc.


  1. Algorithms by Robert Sedgewick.
  2. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.