1

I am reading Think Python: How to Think Like a Computer Scientist, the author says that an algorithm is:

A general process for solving a category of problems.

But I don't know if that a right definition of an algorithm. Isn't an algorithm aimed at solving a specific problem [finding if a number is odd or even, for example]?

Note: I am a hobbyist and a beginner.

  • 3
    To me, "finding if a number is odd or even" is general while "finding if 5 is odd or even" is specific. – Captain Man May 6 '16 at 14:00
  • 1
    It would be nice if the author defined a general process, so you may want to think about it as it applies to a category of problems, like sorting. – JeffO May 6 '16 at 14:41
  • 1
    "A general process for solving a category of problems.": An algorithm does not necessarily solve a problem that is meaningful to us. Algorithm roughly means that you perform some computation / data transformation by repeatedly applying well-defined / discrete steps according to a finite description. If you want to be precise, lambda calculus and Turing machines are examples of formal definitions of what an algorithm is. Anyway: "solving a category of problems" is related to what algorithms are used for, not to what they are. – Giorgio May 6 '16 at 14:58
  • 2
    I don't want to ruin your fun pondering this question but I sincerely doubt that worrying about such informal definitions will gain you any insights of sustaining value. – 5gon12eder May 6 '16 at 16:14
4

A general process is something that works on different inputs.

Taking you example of odd or even.

If I check if the number input is 1 then output odd. This is not a general process. It only works on one very specific input.

If I instead check the modulus 2 of the input I would have a general process as it would work on all integer numbers as input. That is an algorithm.

But it only solves one problem not a full category?

Well a category of problems can be one single problem or a group of problems. There really isn't a reason for using a different term for something that solves one problem and not a category of problems.

3

I think that Wikipedia and the Encyclopedia of Mathematics definitions for algorithm are good complements for each other.

“Detailed instructions defining a computational process (which is then said to be algorithmic), which begins with an arbitrary input (out of a certain number of inputs which are possible for the given algorithm), and with instructions aimed at obtaining a result (or output) which is fully determined by the input.”

https://www.encyclopediaofmath.org/index.php/Algorithm

“In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms perform calculation, data processing, and/or automated reasoning tasks.”

https://en.wikipedia.org/wiki/Algorithm

Metaphorically, an algorithm is like a method of baking a specific cake. The amount of ingredients (input) may vary, thus changing the size of the cake (output). However, the method of preparing the dough is the same, it’s the set of steps followed to combine the ingredients in order to prepare the dough.

1

This is a category of problems:

  • "Sort a sequence of integers".

These are specific problems of that category:

  • "Sort the sequence [4, 3, 1, 8]".
  • "Sort the sequence [1]".
  • "Sort the sequence []".

The word category only means that some details are variable and thus there are actually many (possible infinitely many) specific problems the process could solve.

1

It's not necessarily the "wrong" definition, but it's not a very helpful one. Terms like general and specific (and category) are relative classifications. So, tossing them into a definition without context or further qualification doesn't tell us much.

A better definition would simply be: A set of steps to solve a problem.

From there, if a set of steps solves a problem, it's an algorithm. If you understand the problem as being a general problem, then it's a general algorithm. If you see it as a specific problem, it's a specific algorithm.

If we put your example in the spectrum going from pretty specific to pretty general, it might look something like this:

-- MORE SPECIFIC -- 

> Classify the number `1` as *Even* or *Odd*
> Classify a number `N` as *Even* or *Odd*
> Classify a number `N`
> Classify something `O`

-- MORE GENERAL -- 

You might come up with different generalizations -- hopefully better ones.

You can certainly create an algorithm to solve any one of those problems. And you can arguably call any one of the problems general or specific to suit your needs. But, what the author probably intends to say is, if the algorithm doesn't solve the problem as generally as it is presented, it's not a meaningful algorithm.

0

enter image description here

I also wonder if we can define algorithm in terms of functions only. An algorithm is very much like a function. The simple example is performing multiplication by using addition (3*4 = 4 times 3 = 4 times (+3) = +3 +3 +3 +3 = 12.)

It is important that you can reduce one problem to another which you see that we just did by reducing multiplcation to addition with an algorithm (a function).

One important category is decision problems where it is a question with an answer yes or no.

  • 1
    Please, define the domain of Input in your diagram: Apples? Numbers? Planets? Animals? – Giorgio May 6 '16 at 14:51
  • @Giorgio - How does knowing the domain of an input in this diagram help with the definition of an algorithm? – JeffO May 6 '16 at 19:03
  • @JeffO: As it is now, the diagram does not say much: it just says that something goes into something else, producing one out of two possible outcomes. This could mean anything. To make the diagram more meaningful one could say that the input is a natural number, or any piece of information that can be represented as a natural number. – Giorgio May 6 '16 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.