Chapter1: The role of algorithms in computingEdit
BasicsEdit
- An algorithm is either
- any well defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output. OR
- a tool for solving a well-specified computational problem
- An instance problem consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem. Example: {1, 5, 4, 3} is an instance of the sorting problem
- An algorithm is said to be correct, if for every input instance it halts with the correct output.
- Incorrect algorithms can be useful, if their error rate is controlled.
Applications of algorithmsEdit
- The human genome project made great progress toward finding all genes in human DNA by sorting and analyzing information with help of algorithms.
- Internet search engines, protocols make extensive use of algorithms.
- Personal privacy in e-commerce is achieved by numerical algorithms and number theory.
- In allocating resources beneficially for manufacturing and commercial enterprises.
Data structuresEdit
- A data structure is a way to store and organize data in order to facilitate access and modifications.
Other stuffEdit
- N-P complete problems: Till date, no one knows whether or not efficient algorithms exist to these type of problems and so in real world an approximate solution is acceptable. Example: The travelling salesman problem
- Parallelism: Increasing efficiency of algorithms by taking advantage of multi-threaded algorithms which use multiple cores of CPU.
EfficiencyEdit
Different algorithms devised to solve the same problem often differ dramatically in their efficiency. Example:
Insertion sort | Merge sort |
---|---|
$ Running time = c_{1}\cdot n^{2} $ | $ Running time = c_{2}\cdot\lg n $ |
where n connotes the number elements in the input array (or list). When n grows larger, the efficiency of a task is significantly influenced by the selected algorithm, even more than hardware and software. Here's a comparison:
Property | Computer A (fast) | Computer B (slow) |
---|---|---|
Number of instruction executed per second | 10^{10} | 10^{7} |
Uses | Insertion sort | Merge sort |
Total time to sort 10^{7} numbers | $ \frac{2\times (10^{7})^{2}}{10^{10}} = 20,000 sec \approx 5.5 Hrs $ | $ \frac{50\times 10^{7}\times lg 10^{7}}{10^{10}} = 1,163 sec \approx 20min $ |
Importance of algorithmsEdit
- Total system performance depends on choosing efficient algorithms as much as fast hardware (sometimes more!).
- At larger problem sizes efficient algorithms are prominent.