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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s