Posts Tagged ‘programming’

How important is knowing how to program for TCS?

2011-12-05 by gopi. 1 comments

On 7/11/2011, I asked the question with the same name on the parent site. More precisely:

How important is knowing how to code in TCS (in fields where programming is not directly involved) : is there reasons which could bring a Computational Complexity theorist (for example) to know how to code? Is it worth spending a lot of time learning how to code? And if there are, is there a category (functional, imperative, object-oriented..) of programming language that would be more suited? I can imagine that someday I may have to implement some algorithms for my work, but then can I wait for this moment? Or is there something more?

I got so many good answers that I was advised to blog about it. This is my ‘grand debut’ so forgive me for my prose. I will not give every answers, only the part which I though were the most helpful to me. The rest of the answers can be found on the original question.


1. Testing a Conjecture by Tsuyoshi Ito

Testing a conjecture with numerical calculation can save the time which would have been spent in vain trying to prove a false statement.

1.5 Visualization by John Moeller

A computer is a great tool, it allows you for instance to see in different dimensions that are hard to imagine. Being able to see stuff helps for new ideas.

2. Theoretical results are not always real results by Suresh Venkat

Some optimal algorithms could be really hard to implement, and then not usable in practice, maybe an algorithm not as efficient but that can be implemented would be a better result. It opens up new theoretical research direction.

3. Type-Checking your proofs by Alessandro Cosentino

Learning a functional language forces you to type-check your programs, which can be a big asset for later when you start to type-check your proofs. This statement was however shaded by Sasho Nikolov who stated that even though this was true, maybe it was not worth the time if this was the only reason to learn a functional language.

4. Teaching by Martin Berger

There is a chance that someday a researcher in a university will be given courses with a substantial programming component. Being already comfortable can help being a better teacher.

5. If you know you will need to learn someday, the sooner the better by Peter Shor

Otherwise when you will really need it you will not have time for it.

6. Programming can be fun by Tsuyoshi Ito

Comment +1’d by 11 people! That says it all I guess.


1. (Strongly-Typed) Functional

(+) Teach to type-check, useful for proofs.

(+) A must for the logic/PL semantics field.

(-) Time consuming

(-) Hard to “see” things (see argument for imperative language).

2. Object-Oriented

(+) easy to learn and implement simple algorithms

(+) A must for software engineers (modular re-usable code)

(-) If you do not want to re-use it, not necessary to go that far (see Imperative)

3. Imperative

(+) Get a feel of what’s fast and what’s slow

(+) A must for people interested in efficient algorithms and data structures

(+) Widely used, almost “everyone” has a C compiler (if you want people to use your implementation).

To conclude, I got a lot of interesting answers, answers I did not think of before, so i am really grateful. If you have more arguments pros or cons (there was not that many argument against learning to program when you do not directly need it), feel free to add them. I will probably learn to program in C thanks to this useful discussion (in case some wondered what my final decision was :)). I think it took over my phlegm.

Oh, and also, I learned that “Euclid was a very crappy programmer”.