Design and Analysis of Algorithms: The Role of Algorithms *

On any legal (meaning, consistent with algorithm specification) input, the procedure you are describing should always eventually stop, or terminate. (In this course we will not talk about algorithms that are intended to run "forever," such as the scheduler in an operating system.)

On any legal input, provided the procedure has terminated, the result that it produces has to be correct. Not sometimes correct, not mostly correct, but always correct.

You can measure performance in many different ways. The course will focus on the running time, but there are many others:

• space (memory use)
• disk use, amount of disk-memory communication
• number of processors in a parallel program
• total amount of work in a parallel program
• number of cores in a multi-core program
• total amount of communication in a distributed program
• power consumed in an algorithm tuned to low-power devices
• many others

So in short, when you describe a recipe for doing something, make sure it always stops, make sure it always produces correct answers, and only after that worry about how efficient it is. (Depending on the algorithm, some or all of these are very easy, and some may not be obvious at all. We will see examples later.)