Algorithms

External

• Based on Introduction to Algorithms, 3^rd edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (CLRS)

Internal

• Software Engineering

Algorithm Definition

An algorithm is any well-defined computational procedure consisting in a sequence of steps, which takes some value or set of values, called input and produces a value, or a set of values, called output. The algorithm solves a well-specified computational problem.

In this context, a specific set of input values provided to the algorithm is called an instance of the problem. Algorithms manipulate data structures in various ways.

Algorithms should be considered a technology, the same as computer hardware or object-oriented programming. Total system performance depends on choosing efficient algorithms as much as on choosing fast hardware. Having a solid base of algorithmic knowledge and techniques is one of the factors that separates a skilled programmer from a novice.

An algorithm should be correct, in that it should produce the correct solutions of the computational problem. The algorithm correctness can be formally demonstrated using various mathematical tools and techniques. Additionally, an algorithm should be usable practically, in that it should complete within a finite amount of time, faster the better, and should use a finite amount of computational resources. The completion time and resource requirements are analyzed as part of algorithm efficiency analysis. A good predictor of how much time and resources an algorithm needs is provided by its complexity.

Algorithm Correctness

One of the most important characteristics of an algorithm is its correctness. An algorithm is said to be correct if, for every input instance, it halts with the correct output. It is almost always desirable for an algorithm to be correct. However, in some cases, even incorrect algorithms are useful if we can control the error rate. An example of such algorithm is Miller-Rabin primality test. One of the techniques that can be used to demonstrate that an algorithm is correct is the loop invariant method.

Algorithm Efficiency

Another characteristic of algorithms is efficiency. The obvious reason to analyze the efficiency of an algorithm is that the computing time and the space in memory, are bounded resources and they must be utilized efficiently. Algorithm complexity analysis provides good predictions of an algorithm's efficiency.

Algorithm Complexity

The efficiency of an algorithm can be analyzed through formal methods and expressed using a special notation called asymptotic notation. The asymptotic notation uses functions that bound the algorithm's running time from above and from below. To say that the running time is asymptotically bounded from above by a specific function, say n², we use the "big-O" notation: O(n²). For more details see:

Algorithm Complexity

Iterative vs. Recursive Algorithms

Algorithms can be coarsely categorized in iterative and recursive.

Algorithm Paradigms

Individual algorithms may belong to a number of paradigms, which are general techniques that apply to different problems from different domains. Example of such paradigms are divide and conquer, randomized algorithms, greedy algorithms and dynamic programming.

Iterative Algorithms

Iterative algorithms are also called "incremental".

Recursive Algorithms

A recursive algorithm solves a problem by calling itself recursively one or more times to deal with closely related sub-problems, usually of smaller size. The running time of recursive algorithms can be estimated using recurrences, or recurrence equations. A recursive algorithm requires a base case, where the input is sufficiently small that the output can be immediately computed, rather than recursing further. A typical class of recursive algorithms are "divide and conquer" algorithms, explained below.

Note that not all recursive algorithms are "divide and conquer" algorithms. The Huffman algorithm is a recursive greedy algorithm that does not follows the "divide and conquer" paradigm.

The fundamental intuition behind why a recursive algorithm may be better than a brute force iterative algorithms is that while the number of sub-problems to be resolved grows, the size of the sub-problem, and the work required to solve it, decreases, and in some cases, the rate of sup-problem proliferation (RSP) is smaller than the rate of work shrinkage (RWS).

Divide and Conquer

A common recursive technique is "divide and conquer". The "divide and conquer" is an algorithm design paradigm that has proven useful in solving a specific class of computational problems that involves breaking down a large problem into smaller sub-problems and recursing. The technique consists in three steps, applied at each level of the recursion:

1. Divide the problem into several sub-problems that are similar to the original problem but smaller in size. The problems can be equal in size or not.
2. Conquer the sub-problems by solving them recursively, applying the same procedure in which we're currently in. If the sub-problem size is small enough, it may be solved through iterative techniques, or it may be a trivial case that does not need any work. When we reach this stage, we say that the recursion "bottomed out" and we have gotten down to the base case.
3. Combine the solutions to the sub-problems to create a solution to the original problem. This is usually the step that requires the largest amount of ingenuity, so the work is done as efficiently as possible.

Examples of algorithms that use divide-and-conquer method are:

• Binary search of sorted or unsorted arrays
• Merge sort. This is the canonical "divide and conquer" algorithm example
• QuickSort
• Karatsuba multiplication, which multiplies two n-digit integers in a time better than n²
• Strassen's algorithm for matrix multiplication
• Finding the number of inversions in an array
• Maximum subarray problem
• Closest pair problem

Recursive Algorithms Complexity

As long as the size of the sub-problems is equal, the "divide and conquer" algorithm complexity can be precisely described using the Master Method. For other cases, the complexity can be determined using recursion trees and other methods. More details about recursive and "divide and conquer" algorithm complexity in:

Recursive Algorithms Complexity

Randomized Algorithms

Algorithms whose behavior is determined not only by input, but also by the values produced by a random-number generator, invoked in the algorithm code, are called

randomized algorithms. Randomized algorithms are relatively common algorithm design paradigm, which often leads to simpler, more practical or more elegant algorithms. A randomized algorithm implies an inherent probability distribution for one or more variable, so the running time of such an algorithm may differ on different inputs on the same size. Probabilistic analysis is used to analyze running time of randomized algorithms. The canonical example of a randomized algorithm is randomized QuickSort, primality testing, graph partitioning, hashing. See:

Randomized Algorithms

Sorting

Sorting a sequence of numbers into nondecreasing order is a problem that arises frequent in practice. The class of algorithms that addresses this problem are the sorting algorithms. Sorting algorithms may perform key comparison or not. When analyzing sorting algorithms, characteristics such as whether the algorithm is in place' or whether the algorithm is stable may be discussed. Examples of sorting algorithms are insertion sort, merge sort.

Sorting Algorithms

Partitioning

The Partition Subroutine

The Selection Problem

The i^th order statistic problems require selecting i^th smallest element of a set. Finding the median is a particular case of a i^th order statistic problem. These problems are known as the selection problem. They can be resolved generically by sorting the entire set and then selecting the desired element. However, key comparison sorting cannot be done more efficiently than Ω(n lg n), and more specialized and faster algorithms O(n) for the selection problem exist.

Selection Problem

Also see:

The Median Maintenance Problem

Graph Algorithms

Graph Algorithms

Tree Algorithms

Tree Algorithms

Greedy Algorithms

Greedy algorithms use a design paradigm that involves making at each step of the algorithm a myopic decision, doing something that seems to be a good idea at the time. The decision made by a greedy algorithm at a certain step is irrevocable, it cannot be changed later as the algorithm progresses. Interestingly enough, this approach works out just fine sometimes, greedy local decisions lead some times to an overall optimal solution, but this is not a given. The correctness of a greedy algorithm must be formally proven to ensure that the algorithm is any good.

A strength and a weakness of the greedy algorithm paradigm is just how easy it is to apply. It is often quite easy to come up with plausible greedy algorithms for a problem, even multiple, different plausible greedy algorithms. This is a point of contrast with the divid-and-conquer algorithms, which are non-trivial to come up with.

A general approach to designing greedy algorithms has two steps. The first step involves looking at a few particular cases of the problem, where is reasonably intuitive what should be the optimal thing to do. While doing so attempt to come up with a single greedy score (or criterion) that aggregates various parameters of the individual elements of the problem. Then attempt to use the score and prove that it optimizes the objective function we are trying to compute in the algorithm. The weakness of greedy algorithm design, however, is that is really easy to come up with alternative "obvious" scores that might do the wrong thing. It is not obvious that a greedy algorithm that uses a particular score always minimizes the objective function. The correctness must be proven formally.

Greedy algorithms are usually easy to analyze from a running time perspective. However, they are generally much harder to be proven correct, it takes a lot of creativity and has a bit of an ad hoc flavor. Greedy algorithms can be proven correct by induction, as in the case of Dijkstra's shortest-path algorithm. Some text books call this method "greedy stays ahead", meaning that you prove that the greedy algorithm does the right thing iteration by iteration. The second method of proving greedy algorithms is by exchange argument.

⚠️ Most greedy algorithms are NOT correct, unless they are formally proven correct.

Examples of greedy algorithms and computational problems greedy algorithms are useful for:

• The optimal caching problem
• The job scheduling problem
• Graph algorithms:
  • Dijkstra's shortest-path algorithm
  • The minimum spanning tree problem:
    • Prim's Algorithm
    • Kruskal's Algorithm
• The clustering problem. Also see clustering algorithms below.
• Compression. Greedy algorithms can be used to compute optimal variable-length binary codes, and the canonical example is the computation of the Huffman codes with the Huffman algorithm.

Clustering Algorithms

Clustering algorithms aim to identify the best clustering of a set of objects according to some objective function, which is to say they aim to solve the clustering problem. Some of the most well known clustering algorithms are greedy.

Clustering

Dynamic Programming Algorithms

A dynamic programming solution usually starts with an analysis of the optimal solution ("how would the optimal solution look like, and what happens if a specific element is part or is not part of the optimal solution"). The goal is to express the optimal solution as a recursive function of smaller subproblem solutions. The reasoning used for the optimal solution (n items) applies to an intermediary smaller subproblem of i size.

Once the recurrence expression is established for i, the algorithm proceeds by "brute force" computation of the smaller solutions starting with i = 1, and the selection of the optimal solution at step i by comparing results computed at previous steps and selecting the maximum. This "brute force" approach is feasible because the number of smaller solutions is asymptotically small, so it makes sense to compute them in an efficient running time.

The solution of the smaller subproblems is stored in a global array as the algorithm progresses. This technique is also called memoization. The semantics of storing the solution in the array is that the i^th entry of the array is the solution of the i^th subproblem. In a recursive call, if the smaller problem has been solved already (the array has a value), then that value is used. This is why it is crucial that we solve the subproblems in the right order, from smallest to largest. If the subproblem is not solved when we need it, the problem must be solved and the result stored. Once stored in the array, the subproblem solutions can be retrieved in O(1) later, to be used in computing the solution of larger problems.

The global array is unidimensional or bidimensional, depending on how many dimension the problem has. For example, the maximum weight independent set problem uses a unidimensional array, while the knapsack problem uses a bidimensional array.

The third step of the algorithm is executed after the final optimal solution is computed, and consists in backtracking the array of smaller solutions and establishing what input elements contributed to the optimal solution.

"Dynamic programming" is a term invented by Richard Bellman. Also see:

Principles of Dynamic Programming in "Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming" by Tim Roughgarden

Canonical Use:

• Maximum weight independent set problem
• The knapsack problem
• The sequence alignment problem
• Compute optimal binary search trees
• Distributed shortest path problem: Bellman-Ford Shortest-Path Algorithm

Number-Theoretic Algorithms

Number-theoretic algorithms are important due in large part to the invention of cryptographic schemes based on large prime numbers. Algorithms in this category are used to generate large prime numbers. Some of these algorithms, for example Miller-Rabin primality test algorithm, are not entirely correct, the sense that there is a very small chance of error, but the chance of error is so small that is considered acceptable.

NP Completeness

Almost all the algorithms mentioned so far have been polynomial-time algorithms, which is to say that on an input of size n, their worst running time is O(n^k) for some constant k. Generally, we think of a problem that is solvable by a polynomial-time algorithm as tractable or easy. A problem that requires super-polynomial time is designated intractable or hard. There are also problems whose status is unknown: no polynomial-time algorithm has been yet discovered for them, nor has anyone yet been able to prove that no polynomial-time algorithm can exist for any of them. This class of problems is called NP-complete problems. The set of NP-complete problems has the property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. There are methods to show that a problem is NP-complete, and if that is the case, an approximation algorithm instead of a polynomial-time algorithm, can be developed form it.

NP Completeness

Multithreaded Algorithms

Multicore processors require algorithms designed with parallelism in mind. These are the multithreaded algorithms:

Multithreaded Algorithms