Introduction to Algorithms and Complexity

What is an algorithm?

An algorithm is a sequence of instructions that we must perform to solve a well-formulated problem. We will specify problems in terms of their inputs and their outputs, and the algorithm will be the method of translating the inputs into the outputs. A well-formulated problem is unambiguous and precise, leaving no room for misinterpretation.

After designing an algorithm, two important questions to ask are: Does it work correctly? and How much time will it take? Certainly, we would not be satisfied with an algorithm that only returned correct results half the time or took 1000 years to arrive at an answer.

Pseudocode

To understand how an algorithm works, we need some way of listing the steps that the algorithm takes while being neither too vague nor too formal. We will use pseudocode: a language computer scientists use to describe algorithms. Pseudocode ignores many of the details that are required in a programming language. Yet, it is more precise and less ambiguous than a recipe in a cookbook.

A problem vs. a problem instance

A problem describes a class of computational tasks. A problem instance is one particular input from that class.

To illustrate the difference between a problem and an instance of a problem, consider the following example.

You find yourself in a bookstore buying a book for $4.23, which you pay for with a $5 bill. You would be due 77 cents in change, and the cashier now makes a decision as to exactly how you get it. You would be annoyed at a fistful of 77 pennies or 15 nickels and 2 pennies, which raises the question of how to make a change in the least annoying way. Most cashiers try to minimize the number of coins returned for a particular quantity of change. The example of 77 cents represents an instance of the Change Problem, which we describe below.

The example assumes that there are ...