Chapter1: The role of algorithms in computingEdit


  • 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.


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.