6 Pages

# 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

1. 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
2. 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 1010 107
Uses Insertion sort Merge sort
Total time to sort 107 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.