# Algorithms in C++

### Introduction

The purpose of this article is to introduce the reader to four main algorithmic paradigms: complete search, greedy algorithms, divide and conquer, and dynamic programming. Many algorithmic problems can be mapped into one of these four categories and the mastery of each one will make you a better programmer.

### Complete Search

Complete search (aka brute force or recursive backtracking) is a method for solving a problem by traversing the entire search space in search of a solution. During the search we can prune parts of the search space that we are sure do not lead to the required solution. In programming contests, complete search will likely lead to Time Limit Exceeded (TLE), however, it’s a good strategy for small input problems.

#### Complete Search Example: 8 Queens Problem

Our goal is to place 8 queens on a chess board such that no two queens attack each other. In the most naive solution, we would need to enumerate 64 choose 8 ~ 4B possibilities. A better naive solution is to realize that we can put each queen in a separate column, which leads to 8⁸~17M possibilities. We can do better by placing each queen in a separate column and a separate row that results in 8!~40K valid row permutations. In the implementation below, we assume that each queen occupies a different column, and we compute a valid row number for each of the 8 queens.

For TC=8 and an initial queen position at (a,b) = (1,1) the above code results in the following output:

which indicates that there are four possible placements given the initial queen position at (r=1,c=1). Notice that the use of recursion allows to more easily prune the search space in comparison to an iterative solution.

### Greedy Algorithms

A greedy algorithm takes a locally optimum choice at each step with the hope of eventually reaching a globally optimal solution. Greedy algorithms often rely on a greedy heuristic and one can often find examples in which greedy algorithms fail to achieve the global optimum.

#### Greedy Example: Fractional Knapsack

A greedy knapsack problem consists of selecting what items to place in a knapsack of limited capacity W so as to maximize the total value of knapsack items, where each item has an associated weight and value. We can define a greedy heuristic to be a ratio of item value to item weight, i.e. we would like to greedily choose items that are simultaneously high value and low weight and sort the items based on this criteria. In the fractional knapsack problem, we are allowed to take fractions of an item (as opposed to 0–1 Knapsack).

Since sorting is the most expensive operation, the algorithm runs in O(n log n) time. Given (value, weight) pairs of three items: {(60, 10), (100, 20), (120, 30)}, and the total capacity W=50, the code above produces the following output:

We can see that the input items are sorted in decreasing ratio of value / cost, after greedily selecting items 1 and 2, we take a 2/3 fraction of item 3 for a total value of 60+100+(2/3)120 = 240.

### Divide and Conquer

Divide and Conquer (D&C) is a technique that divides a problem into smaller, independent sub-problems and then combines solutions to each of the sub-problems.

Examples of divide and conquer technique include sorting algorithms such as quick sort, merge sort and heap sort as well as binary search.

#### D&C Example: Binary Search

The classic use of binary search is in searching for a value in a sorted array. First, we check the middle of the array to see if if contains what we are looking for. If it does or there are no more items to consider, we stop. Otherwise, we decide whether the answer is to the left or the right of the middle element and continue searching. As the size of the search space is halved after each check, the complexity of the algorithm is O(log n).

The code above produces the following output:

Note if the query element is not found but we would like to find the first entry not smaller than the query or the first entry greater than the query, we can use STL lower_bound and upper_bound.

### Dynamic Programming

Dynamic Programming (DP) is a technique that divides a problem into smaller overlapping sub-problems, computes a solution for each sub-problem and stores it in a DP table. The final solution is read off the DP table.

Key skills in mastering dynamic programming is the ability to determine the problem states (entries of the DP table) and the relationships or transitions between the states. Then, having defined base cases and recursive relationships, one can populate the DP table in a top-down or bottom-up fashion.

In the top-down DP, the table is populated recursively, as needed, starting from the top and going down to smaller sub-problems. In the bottom-up DP, the table is populated iteratively starting from the smallest sub-problems and using their solutions to build-on and arrive at solutions to bigger sub-problems. In both cases, if a sub-problem was already encountered, its solution is simply looked up in the table (as opposed to re-computing the solution from scratch). This dramatically reduces computational cost.

#### DP Example: Binomial Coefficients

We use binomial coefficients example to illustrate the use of top-down and bottom-up DP. The code below is based on the recursion for binomial coefficients with overlapping sub-problems. Let C(n,k) denote n choose k, then, we have:

Notice that we have multiple over-lapping sub-problems. E.g. For C(n=5, k=2) the recursion tree is as follows:

We can implement top-down and bottom-up DP as follows:

For C(n=5, k=2), the code above produces the following output:

The time complexity is O(n * k) and the space complexity is O(n * k). In the case of top-down DP, solutions to sub-problems are stored (memoized) as needed, whereas in the bottom-up DP, the entire table is computed starting from the base case. Note: a small DP table size (V=8) was chosen for printing purposes, a much larger table size is recommended.

### Code

All code is available at: https://github.com/vsmolyakov/cpp

To compile C++ code you can run the following command:

### Conclusion

There are a number of great resources available for learning algorithms. I highly recommend Steven Halim’s book [1] on competitive programming. In addition to the classic Algorithm Design Manual [2] and CLRS [3]. There are a number of great coding challenge web-sites some of which are mentioned in [4]. In addition, [5] has a fantastic collection of algorithms and easy to understand implementations. A great resource if you are building your own library or participating in programming competitions.