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

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 vs. Recursive Algorithms

Algorithms can be coarsely categorized in iterative and recursive.

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. A special class of recursive algorithms are the "divide-and-conquer" algorithms, but not all recursive algorithms belong to this class.

Recursive Algorithms

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

Dynamic programming algorithms are optimized recursive algorithms, where we store the solution of smaller subproblems and use them in computing the solution for larger subproblems, avoiding duplicate work and yielding superior running times. The classic example where the difference between the straightforward recursive solution and the corresponding dynamic programming solution is obvious is computing Fibonacci numbers.

Dynamic Programming

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

NP Completeness

Multithreaded Algorithms

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

Multithreaded Algorithms

Optimization Algorithms

Optimization Algorithms

Organizatorium

• CS261 Stanford: https://www.youtube.com/playlist?list=PLEGCF-WLh2RJh2yDxlJJjnKswWdoO8gAc