# The Role of Algorithms in Computing

• an algorithm is 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. An algorithm is thus a sequence of computational steps that transform the input into the output.
• An input sequence is called an instance of the sorting problem
• Which algorithm is best for a given application depends on-among other factors

• the number of items to be sorted
• the extent to which the items are already somewhat sorted
• possible restrictions on the item values
• The kind of storage device to be used
• An algorithm is said to be correct if, for every input instance, it halts with the correct output
• Why are NP-complete problems interesting?

• First, although no efficient algorithm for an NP-Complete problem has ever been found, nobody has ever proven that an efficient algorithm for one cannot exist.
• Second, the set of NP-Complete problems has the remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exists for all of them. This relationship among the NP-Complete problems makes the lack of efficient solutions all the more tantalizing

Third, several NP-Complete problems are similar, but not identical, to problems for which we do know of efficient algorithms. A small change to the problem statement can cause a big change to the efficiency of the best known algorithm.