Algorithms: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(7 intermediate revisions by the same user not shown)
Line 32: Line 32:


==Recursive Algorithms==
==Recursive Algorithms==
<span id='Recursive_Algorithm'></span>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.
<span id='Recursive_Algorithm'></span>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 "[[Recursive_Algorithms#Divide_and_Conquer|divide-and-conquer]]" algorithms, but not all recursive algorithms belong to this class.
{{Internal|Recursive_Algorithms#Overview|Recursive Algorithms}}
{{Internal|Recursive_Algorithms#Overview|Recursive Algorithms}}
The running time of recursive algorithms can be estimated using <span id='Recurrence'></span>[[Recursive_Algorithms_Complexity#Recurrence|recurrences]], or [[Recursive_Algorithms_Complexity#Recurrence_Equation|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|"divide and conquer" algorithms]], explained below.
Note that not all recursive algorithms are "divide and conquer" algorithms. The [[Binary_Codes#The_Huffman_Algorithm|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_Paradigms|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:
# '''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.
# '''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'''.
# <span id='Combine'></span>'''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 [[#Algorithm_Efficiency|efficiently]] as possible.
Examples of algorithms that use divide-and-conquer method are:
* <span id='Binary_Search'></span>[[Binary Search|Binary search]] of sorted or unsorted arrays
* [[Merge_Sort#Overview|Merge sort]]. This is the canonical "divide and conquer" algorithm example
* [[Quicksort|QuickSort]]
* <span id='q23wLp'></span>[[Karatsuba Multiplication|Karatsuba multiplication]], which multiplies two n-digit integers in a time better than n<sup>2</sup>
* <span id='X4slMN'></span>[[Matrix_Multiplication#Strassen|Strassen's algorithm for matrix multiplication]]
* <span id='b3slp3'></span>[[Inversions in an Array|Finding the number of inversions in an array]]
* <span id='Rt3vlM1'></span>[[Maximum Subarray Problem|Maximum subarray problem]]
* <span id='R23wL0'>[[Closest Pair 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:
{{Internal|Recursive_Algorithms_Complexity#Overview|Recursive Algorithms Complexity}}


=Randomized Algorithms=
=Randomized Algorithms=
Line 113: Line 85:


=Dynamic Programming Algorithms=
=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.
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|Fibonacci numbers]].
 
{{Internal|Dynamic Programming#Overview|Dynamic Programming}}
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<sup>th</sup> entry of the array is the solution of the i<sup>th</sup> 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#Overview|maximum weight independent set problem]] uses a unidimensional array, while the [[The_Knapsack_Problem#Overview|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: {{External|[https://www.coursera.org/learn/algorithms-greedy/lecture/VEc7L/principles-of-dynamic-programming Principles of Dynamic Programming in "Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming" by Tim Roughgarden]}}
 
Canonical Use:
* [[Maximum Weight Independent Set Problem#Overview|Maximum weight independent set problem]]
* The [[The Knapsack Problem#Overview|knapsack problem]]
* The [[The Sequence Alignment Problem#Overview|sequence alignment problem]]
* Compute [[Optimal Binary Search Trees#Overview|optimal binary search trees]]
* Distributed shortest path problem: [[Bellman-Ford_Shortest-Path_Algorithm|Bellman-Ford Shortest-Path Algorithm]]


=Number-Theoretic Algorithms=
=Number-Theoretic Algorithms=
Line 136: Line 92:
'''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|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.
'''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|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=
=<span id='NP-complete_Problems'></span>NP Completeness=
 
<span id='NP-complete_Problems'></span>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<sup>k</sup>) 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 Completeness#Overview|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.
 
{{Internal|NP Completeness#Overview|NP Completeness}}
{{Internal|NP Completeness#Overview|NP Completeness}}


Line 147: Line 100:


{{Internal|Multithreaded Algorithms#Overview|Multithreaded Algorithms}}
{{Internal|Multithreaded Algorithms#Overview|Multithreaded Algorithms}}
=Optimization Algorithms=
{{Internal|Optimization Algorithms|Optimization Algorithms}}
=Organizatorium=
* CS261 Stanford: https://www.youtube.com/playlist?list=PLEGCF-WLh2RJh2yDxlJJjnKswWdoO8gAc

Latest revision as of 16:47, 6 October 2023

External

Internal

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 n2, we use the "big-O" notation: O(n2). 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 ith order statistic problems require selecting ith smallest element of a set. Finding the median is a particular case of a ith 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:

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

Retrieved from "https://kb.novaordis.com/index.php?title=Algorithms&oldid=102070"