1

I am a Computer Science student who is greatly intrigued by algorithms.

However I am curious whether computer scientists who study algorithms teach themselves to formally analyze algorithms and prove the correctness of algorithms as is done in the CLR book, or do they mostly focus on the technique and design of the algorithms.

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Isaac Kleinman
  • 135
  • 2
  • 1
    I am not sure analysis and development can be separated (if you are interested in truth, not broad rules). – Raphael Jul 26 '11 at 18:38
  • 7
    They are both artist and art critics. :) More seriously, the level of formality depends on the audience, the proofs need not be completely formal, they need to convince the audience (other researchers) about the correctness of the claims, e.g. in a research paper giving an informal description of the proofs would suffice when readers can carry out the details themselves, but when required (e.g. asked by a referee) the authors should be able to give a more formal proof till the referee is convinced, i.e. they know how to give formal proofs but that is seldom required. – Kaveh Jul 26 '11 at 18:49
  • 1
    There are many different computer scientists, and they work in many different ways. If you want to be an academic theoretical computer scientist, you should know how to prove the correctness of algorithms. If you're talking about computer scientists in general, the question is probably so broad as to be unanswerable. – Peter Shor Jul 28 '11 at 16:38

2 Answers2

8

Theoretical computer scientists both design algorithms and prove their correctness and running time. For some algorithms, the correctness and running time are evident, while others require proof. For the latter, without a proof it's hard to know whether the algorithm actually does what it should. There are countless examples of small subtleties in algorithms that make enormous differences for performance (e.g., take a look at union-find data structures in CLRS).

An alternative could be running the algorithm and experimenting with it. This is often an excellent first step when you try to figure out if you actually have a good algorithm or not. Experimenting is especially useful when a rigorous analysis seems hard, or when you're still trying to figure out the exact formulation of the algorithm's task (e.g., think of the Netflix challenge, where you want to recommend movies to users given data about their history. It's not even clear what it is exactly that you want your algorithm to do).

Ultimately, though, a clear understanding of what the algorithm guarantees is sought after, and for the most part, you need a proof for that.

Dana Moshkovitz
  • 10,979
  • 1
  • 50
  • 77
2

Although I am mostly into complexity theory, here's what I've seen from papers on algorithms. Usually these kind of papers prove both that :

a) Their algorithm is better in some special interesting cases or an interesting model of analysis (see also the question Paradigms for complexity analysis of algorithms than the ones already existing.

b) That their algorithm is correct under the kind of computation they are using (deterministic or no error, probabilistic or small error, approximation and its quality ) .

If a problem is studied well or there is a similar analysis in a previous paper, a reference or a small modification might suffice. Since a lot of algorithms are improvements of older results, to prove that the improvement does not interfere with the correctness of the algorithm suffices.

Community
  • 1
chazisop
  • 3,796
  • 2
  • 29
  • 37