-1

friends i am doing BS(it) i want simple and easy answer for this questio can anyone help me.
what is algorithm explain it?analysis of algorithm?

Votes + Comments
_
8
Contributors
9
Replies
13
Views
6 Years
Discussion Span
Last Post by jon.kiparsky
0

More explicitly, an algorithm is a comprehensive, language-independent description of a procedure for solving a problem, in a finite time.
I think that about covers it. You might want to read what wikipedia has to say about it, for a bit more detail.
Or, if you're feeling really ambitious, you might consult one of your textbooks.

0

Some algorithms are easier to explain with math, some with natural language.

How to multiply a matrix requires math to explain.
A recipe for making a cake is an algorithm. Try to explain it using math.

0

Yes dude i understood..
Very good example given for me...
Thnks buddy...I hope to refer more..

2

More explicitly, an algorithm is a comprehensive, language-independent description of a procedure for solving a problem, in a finite time.
I think that about covers it.

That's one definition. I would argue for these differences:

1. An algorithm does not have to take finite time. For example, it could be something describing an infinite process like "add 1 to each number that comes out of this pipe and put it into that pipe." Or it could be something like, "walk down this infinite tape and flip every bit." Or it could be 10 PRINT "u suck" 20 GOTO 10 , or it could just be a broken, incorrect algorithm.

2. An algorithm does not have to be for solving a problem. For example, you can randomly generate computer programs that describe algorithms, and they'll not be "for solving a problem." They'll just "do stuff." What you say is correct in a certain context, e.g. where problem means some language you wish to recognize, where you're writing an algorithm that can either accept or reject inputs or fail to terminate. This is not really a difference then, but I want to make it clear what it is you are probably saying.

So far, I think difference #1 is non-controversial, and difference #2 is really a pedantic disagreement on terminology. There is a third difference I'd argue, though.

3. Algorithms are not language-independent. Some languages are more powerful than others, either in terms of the set of problems they can solve, or the number of operations needed to solve them. For example, consider finite automata, push-down automata, turing machines, and von neumann machines. The first three have different strength in terms of the problems they solve, and the last two differ in how performant they can be.

One might then argue that algorithms are still not tied to the language they're written in. For example, is an algorithm written in Java a different algorithm than one written in C++? How about one written in C#? Forth? Haskell? At what point do they become different?

Are the following two algorithms different?

// A:
    int fact(int n) { return n == 0 ? 1 : n * fact(n - 1); }
    // B:
    int fact(int x) { return x == 0 ? 1 : x * fact(x - 1); }

We could argue that certain programs are equivalent. We could then create equivalence classes of programs, and that's what an algorithm is, an equivalence class of programs across different languages. But what about this?

// A:
    Integer sum(Integer[] xs) {
        Integer acc = "";
        foreach (Integer x in xs) { acc = acc + x; }
        return acc;
    }
    // B:
    int sum(int[] xs) {
        int acc = 0;
        foreach (string x in xs) { acc = acc + x; }
        return acc;
    }

One might argue that these programs are equivalent, or similar, or something, and that they're the same algorithm. However, the first version is capable of throwing an exception.

4. Algorithms do not have to be comprehensive.

For example, an algorithm could require you to have a source of uniformly distributed random numbers.

Or it could be less descriptive. For example, an algorithm for computing the first twenty decimal digits of the square root of two could start with "Pick a rational number between 1 and 2."

And of course computer programs written in high level languages do not specify the actual behavior of the computer, and often they leave aspects of the high-level semantics unspecified.

As two descriptions of a procedure are different if one is written using British spelling instead of American spelling, it's the case that algorithms can be distinguished by the language they're written in. So your definition of language-independent description is plainly self-contradictory. I'd say an algorithm is an equivalence class of descriptions of a procedure. Or more simply, an algorithm is a procedure. I'm not sure what equivalence relationship is appropriate, though. Whatever programs describe the same "procedure." I think the term kind of algorithm should be used for broad equivalence relationships, like the kind that considers quicksort for arrays to be equivalent to quicksort for linked lists.

Edited by Rashakil Fol: n/a

3

With all due respect, that's a lot of quibbling to throw into a pretty non-controversial topic.

1. I suppose you're right, in so far as I could ask for an algorithm to occupy my computer's entire memory forever, locking it up into a useless boat anchor, and you could probably come up with a few. (Simplest one: install Windows. Cheap shot, I know) Finite time would not be a requirement there. However, it's hard to think of a lot of real-life cases in which eventual termination is not a requirement of an algorithm. So okay, you can have that one, but why do you want it?
2. An algorithm without a purpose is not an algorithm. A list of steps isn't a procedure until it has a purpose. "Solving a problem" is one way of characterizing this requirement. Your program can generate sequences of steps, but I don't think anyone would call them algorithms unless there was a purpose for them. You can get into some formerly interesting philosophical questions here - now pretty well worked over, I think - but in a nutshell, I think "solve a problem" is a non-controversial requirement. The thing has to do something, and that something has to be stated at the outset.

Point three is really where we disagree, and I think you're not going to convince me or anyone that I know on this one. Algorithms are not written in programming languages, implementations are. Algorithms, by their nature, are abstract entities. They might be implemented well or poorly, a language might be better suited to one class of algorithm than to another, but the implementation is not the algorithm. This is the point of algorithms, in fact: that they abstract the problem away from the details of how it's dealt with on this machine in this language.

So your first example is simply not an example. Those aren't two algorithms, those are two implementations of a standard recursive factorial algorithm, where you've changed a symbol.
In your second example, again you've got the same algorithm twice. It's not that one "might" argue that they're similar, they're the same algorithm. The fact that one might be a potentially flawed implemenation doesn't change that - surely you wouldn't say that every DS&A student who screws up a bubblesort has come up with a "new algorithm"?

Point 4, okay, I'll allow you that you might not require an algorithm to be comprehensive. You might not, for example, mind if I gave you a sort algorithm that sometimes returned the contents of the collection unsorted a little bit. "GoodEnoughSort" - nobody's going to look at the last elements, anyway, right? Doesn't matter if they're a little out of order maybe.
However, I don't think you're going to find a lot of takers for that one.

I'm not sure what the part about British and American spelling is meant to be about.
You wouldn't say that multiplication is a different process in Berlin and Paris, because it's described in German in one city and French in another - why would it matter if you describe selection sort in Esperanto or Swahili? The steps will be the same in each case, and it's not difficult to establish whether we're talking about the same steps.
"Language-independent" referred, and I thought this would be pretty clear, to the language of implementation, not the language of description, but it doesn't make a difference here. Translate Sedgewick or Knuth into Polish and the material is the same unless you screw up the translation. Implement Floyd-Warshall in Java or Python, it's still Floyd-Warshall, unless you screw up the implementation.

Votes + Comments
You are correct, Sir!
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.