<p>Theoretical computer science is a broad field and the importance of programming depends on what you do in TCS.  I will mention two ways in which programming can help you, without implying that these are the only ways.</p>

<p>First, if you design algorithms for problems of practical importance, implementing your algorithms and making the code available to others can be a big plus.  For example, the convex hull problem arises in many fields, and people use software packages such as <a href="http://www.ifor.math.ethz.ch/~fukuda/cdd_home/index.html">cdd</a> by Komei Fukuda and <a href="http://cgm.cs.mcgill.ca/~avis/C/lrs.html">lrs</a> by David Avis to solve this problem.  If they had published their algorithms only in papers, probably less people would have used their algorithms.  More users mean more feedback and probably also more opportunities to collaborate, which is invaluable.</p>

<p>Second, even if you do not work in algorithms, writing a one-time code helps you to test a simple conjecture when the conjecture is suitable to numerical calculation.  For example, if you wonder whether the product of three positive definite matrices always has a positive trace, it is easy to write a code to test it for some random choices of 2×2 or 3×3 positive definite matrices and find a counterexample.  Although you do not advertise that you wrote any program to test the conjecture, programming can save the time which would have been spent in vain trying to prove a false statement.</p>

<p>The programming language to choose depends on what you want to do with programming, and it can be a topic for a whole book in my opinion.  But if you design algorithms and want to implement your algorithms so that other people can use the implementation, then one important factor is availability.  Although you can expect that most potential users of your code have access to a C compiler, you cannot expect that the same people have access to a Haskell compiler.  For one-time programs, the choice is more based on available libraries, and includes the environments such as Matlab.</p>

<p>By the way, programming can also be fun.</p>

CC BY-SA 3.0
2011-11-08T02:13:50.740Z
@SureshVenkat: In fact, if programming is fun, the question “How important is programming?” may not be very relevant.  But then the most part of my answer will become irrelevant.  How sad! :)
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-08T17:18:07.377Z
I did not think of your second argument before, indeed it seems a really good idea to test a conjecture with a short program! As for programming can be fun, so it seems, but I have yet to see over all the long week-end learning =).
Gopi
CC BY-SA 3.0
2011-11-09T15:05:08.450Z
@Gopi: That said, many conjectures do not fit in this “test with a simple program” framework.  For example, we usually cannot test asymptotic behaviors (at least by a simple program).  But when you have some conjecture that can be tested, a little programming can be a powerful tool.  As for fun, yes, I understand.  I just did not want to ignore the “fun” viewpoint by only listing some motivations from the “usefulness” viewpoint.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-02T06:37:14.943Z
Knuth's notes on a problem solving class have a wonderful example of the interplay between conjectures and code (see Problem 1): http://www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf (I particularly like the image of someone rushing into the classroom bearing a heap of printouts)
Suresh Venkat
CC BY-SA 3.0
2011-11-07T22:37:38.513Z
2011-11-07T22:37:38.513Z
Tsuyoshi Ito
<p>I feel compelled to cite Doron Zeilberger on this:</p>

<p><a href="http://www.math.rutgers.edu/~zeilberg/Opinion37.html">Opinion 37</a>: Programming is Even More Fun Than Proving, and, More Importantly It Gives As Much, If Not More, Insight and Understanding.</p>

<p>Read the opinion, it's full of gems (btw he tends to be deliberately provocative). For example, "The best way to understand something is to teach it. But even better then teaching it to humans is to teach it to a computer".</p>

<p>My personal experience is that even when doing purely theoretical work you will need some computing tools. I avoid a lot of tedious routine algebraic manipulations with Mathematica. I test my half-baked conjectures by brute-forcing small instances on Matlab or Python. I have co-written one paper that's pure combinatorics, and that's the work that has benefited most from running extensive computer experiments to understand what's going on. Euler made huge tables of tedious calculations to get insight into problems. We owe it to him to use our tools to automate this process when we do mathematics.</p>

<p>Aside from that, if you'll work on algorithms and data structures, programming will give an irreplaceable perspective on issues of efficiency and usability. My opinion here differs with others somewhat. I think learning a functional language so that you get to write proofs that type correctly is a waste of time (I think it's a great point that people who have experience with a strongly typed language probably tend to write more carefully structured proofs; I just don't think it's worth your time to go through that exercise). Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues (and, of course, learning functional programming is probably a must and will come somewhat naturally if you're interested in logic/PL semantics). Similarly, I think getting into the OO details of Java and C++ is also not the optimal way to spend your time, as the purpose of OO is to write modular re-usable code. It's the way to go if you'll produce code for others to use. But in case you want to get insight into efficiency and running time, if you care about really efficient algorithms and data structures, I second the suggestion to look into C. It lets you stay close to the machine while still providing a reasonable level of abstraction. This way you get a feel of what's fast and what's slow, what is a reasonable data structure, etc.</p>

CC BY-SA 3.0
2011-11-08T17:15:22.810Z
Very good points in favor of C.
Peter Shor 
CC BY-SA 3.0
2011-11-08T17:40:40.330Z
"Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues". Fighting words :)
Suresh Venkat
CC BY-SA 3.0
2011-11-08T18:55:52.317Z
"Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues." Which is why it is a good choice if you work in the logic or semantics side of TCS. :)
Radu GRIGore
CC BY-SA 3.0
2011-11-09T04:46:21.677Z
Now when I reread it sounds a little too curt. I agree that FP goes great with logic and semantics and am willing to be disproved
Sasho Nikolov
CC BY-SA 3.0
2011-11-09T12:31:15.023Z
[Ahem.](http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki)
Jeffε
CC BY-SA 3.0
2011-11-10T00:42:04.967Z
@JɛﬀE That's a question with a terrific answer. But looking over Okasaki's thesis still leaves me with the impression that reasoning about data structure efficiency in a functional language is possible, but can be a headache, even for data structures we consider simple.
Sasho Nikolov
CC BY-SA 3.0
2011-11-10T08:44:12.547Z
@Sasho: All ordinary techniques still work in functional languages. The only "problem" is that functional programming encourages a style of programming and data structure design which ordinary techniques of algorithmic analysis are under-equipped to handle. (E.g., what's the big-O of function composition? The operation is *trivial*, but it completely breaks the assumptions of asymptotic complexity -- there's no simple numeric metric of size for a functional input.)
Neel Krishnaswami
CC BY-SA 3.0
2011-11-10T14:09:10.377Z
@SashoNikolov: Whenever I teach a graduate data structures class, I really really wish I could assume that everyone had some functional programming experience.  Instead of spending three 90-minute lectures to explain persistence, I could just say "Hey, did you notice that your data structures already do THIS?"
Jeffε
CC BY-SA 3.0
2011-11-10T14:48:43.933Z
@NeelKrishnaswami: Well, lazy evaluation means that you need to think about what gets evaluated when you analyze the algorithm rather than when you write the code. So, in a sense, lazy evaluation makes algorithm analysis harder (although you don't really do more work overall).

It's a bit like the difference between memoized recursive implementations versus dynamic programming ones: For memoization you *don't* need to figure out the space usage before you write the code, so, in a sense, analyzing the space usage of a memoized implementation can be more work.
Radu GRIGore
CC BY-SA 3.0
2011-11-29T00:51:44.130Z
It depends on what you mean by "functional programming". If you mean programming in a pure functional language with lazy evaluation then yes, reasoning about complexity becomes difficult, and in order to get decent performance you'll probably have to force eager evaluation and implement state machines on the top of the functional layer, hoping that the complier optimizes them. If you mean using elements of the functional paradigm on a multiparadigm language such as the ML family or the Lisp family, then reasoning about complexity and getting good performance becomes more feasible.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-11-08T16:09:40.157Z
2011-11-10T00:49:29.077Z
2011-11-10T00:49:29.077Z
Sasho Nikolov
<p>You can be a quite successful theoretical computer scientist without programming. For a few people, programming is quite difficult, and if you are one of them you shouldn't despair and switch fields.</p>

<p>However, for most math and computer science graduate students, learning to program is not particularly difficult, and is a skill which is very useful. You should learn a programming language, and if you enjoy it, you should try to get enough practice to become reasonably proficient at it. Then, when the point comes (and it will) that it will be useful in your research to write a program, you will be able to do it. </p>

<p>If you don't learn to program now, it is quite likely that when you eventually need to write a program, you won't have time to learn, and so you may not actually write it, and end up being less effective in your research. While getting a grad student or an undergrad to do this for you isn't too hard, there are a lot of times when it's much easier and less time-consuming to do it yourself rather than explain the problem to them. </p>

<p>What language should you learn? I'd recommend an object-oriented language, since these are the ones that are currently in most use, and I suspect this will be more true in the future.  Maybe Python or Java&mdash;they're both object-oriented languages, and while they're used less in practice than C++, my impression is that they're both much, much easier to learn. (Caveat: I don't know C++, despite having worked at Bell Labs, so maybe I'm wrong about this.)</p>

CC BY-SA 3.0
2011-11-08T17:29:48.517Z
I see the truth in your third paragraph :).
Gopi
CC BY-SA 3.0
2011-11-08T19:24:10.790Z
"However, for most people, learning to program is not particularly difficult" -- my experience leads me to disagree with this, but most people are not TCS researchers.
Max
CC BY-SA 3.0
2011-11-08T19:36:55.737Z
@Max: You're absolutely right; let me change my answer.
Peter Shor 
CC BY-SA 3.0
2011-11-09T13:08:32.273Z
if you come from math, maybe it would be easier to learn something like Mathematica or Maple. That way you won't have to bother with memory handling and other stuff.
Marcos Villagra
CC BY-SA 3.0
2011-11-09T16:36:17.853Z
@Marcos: Certainly learning Mathematica or Maple is good, but I suggested an object oriented language partly because of the point Martin Berger brought up in his answer ... if you end up in a computer science department, it's good to have some common ground with your colleagues, and maybe knowing how to program will help in your teaching.  If object oriented languages are indeed the way the world is going (as it seems right now), it will be good to know one of them.
Peter Shor 
CC BY-SA 3.0
2011-11-10T01:14:17.987Z
@Peter: that's a good point.
Marcos Villagra
CC BY-SA 3.0
2011-11-11T13:37:06.280Z
With the rise of Sage, it is possible to work with a nice, popular language like Python while still having Mathematica/Maple/Matlab style mathematical libraries instantly available.
András Salamon
CC BY-SA 3.0
2011-11-29T01:10:08.977Z
C++ has the most advanced type/metaprogramming system of any mainstream general purpose programming language I've seen, except the family of Lisp languages. So if you are into type theory, language design or compiler theory, or more broadly into formal semantics, you may want to be familiar with it. In addition to C++, Java and C# are a must if you want to do research in experimental Computer Science, or hope to get a job as a programmer or software engineer in the industry. Python should be taught in high schools :D
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2012-03-31T01:19:04.630Z
@AntonioValerioMiceli-Barone: I have to disagree, at least for type theory, language design, formal semantics and programming language theory (PLT) in general: C++ is _not_ the language to learn for those fields; TT and formal semantics relate almost exclusively to functional programming, while the PL community is more diverse, but prefers languages more elegant than C++. Haskell is the "mainstream" language with the most advanced type system, followed by Scala (less advanced, a bit more mainstream). C++ does have interesting features, but is too low-level for modern taste.
Blaisorblade
CC BY-SA 3.0
2011-11-08T14:48:31.197Z
2011-11-08T20:07:55.823Z
2011-11-08T20:07:55.823Z
Peter Shor 
<p>There's another answer that no one has really brought up. Programming can actually lead to interesting theory. A lot of the recent developments in hashing (especially tabulation hashing) are motivated not by theoretical concerns per se, but by the fact that the theoretically optimal algorithms aren't that great in practice. This of course is something you don't know unless you can write code. </p>

<p>Even in the realm of exact exponential time algorithms, a motivation is producing algorithms that can actually work. SAT solvers are the canonical example of this. </p>

<p>In short, the ability to code allows you to realize shortcomings and weaknesses in what might look like optimal theoretical results, and that in turn opens up new theoretical research directions. </p>

CC BY-SA 3.0
2011-11-18T15:15:41.093Z
Your answer could maybe help on the question about [Empirical results in TCS](http://cstheory.stackexchange.com/questions/5080/empirical-results-in-cs-papers).
Gopi
CC BY-SA 3.0
2011-11-18T16:20:25.440Z
maybe: but that thread has long died out :)
Suresh Venkat
CC BY-SA 3.0
2011-11-19T10:39:04.997Z
Indeed, I did not look at the date, it was in the last newsletter I received, in the section "Greatest hits from previous weeks" =).
Gopi
CC BY-SA 3.0
2011-11-10T04:22:35.970Z
2011-11-10T04:22:35.970Z
Suresh Venkat
<p>Three points:</p>

<p>1) There is an approach to mathematics called <a href="http://en.wikipedia.org/wiki/Experimental_mathematics">Experimental Mathematics</a> (see also <a href="http://en.wikipedia.org/wiki/Computer-aided_proof">wikipedia://Computer-aided proof</a>) where you use computer programs to investigate about patterns and structures of objects in order to come up with analytic proofs about these objects. For this approach, you better know how to program. You can be sure you will find yourself in the need of this approach to prove very theoretical statements. I believe that snobbery against programming often turns out not to be really helpful in TCS research.</p>

<p>2) When you learn how to program, as byproducts you learn skills that are useful in TCS. One example above all: I found out that people with coding background tend to type-check their proofs more. Even better, they tend to very often define the type of the objects they are considering (ex.: "let's consider the operators $A \in L(X,Y)$ and $B \in L(Y,C)$). This is good for the readers of a manuscript. Compilers (and interpreters) turn us into good scientists :) For this kind of skills, I feel to suggest some strongly-typed functional language.</p>

<p>3) When you say "to program" do you also mean "to <em>linear program</em>" or "to <em>semidefinite program</em>"? :) </p>

CC BY-SA 3.0
2011-11-08T14:37:11.017Z
Nobody I know uses "to program" for "to linear program" or "to semidefinite program". You would say "to construct/solve a linear program" instead.
Peter Shor 
CC BY-SA 3.0
2011-11-08T14:43:51.480Z
@PeterShor Point 3 was not serious
Alessandro Cosentino
CC BY-SA 3.0
2011-11-08T14:50:54.203Z
And of course, you **should** also learn to linear program and to semidefinite program ... both useful skills.
Peter Shor 
CC BY-SA 3.0
2011-11-08T14:56:59.257Z
Point 2 alone deserves +1. I've given up on implementing an algorithm from a highly cited paper once because it just did not type.
Peter Taylor
CC BY-SA 3.0
2011-11-08T16:44:15.090Z
@PeterShor I totally agree. Also, I am glad to see that you started to use this terminology too ;-)
Alessandro Cosentino
CC BY-SA 3.0
2011-11-08T17:27:36.257Z
+1 for point 2, I actually was taught a little OCaml when I was an undergrad, even-though I only used it for one year, I took the habit to check the types of my proofs.
Gopi
CC BY-SA 3.0
2011-11-09T12:33:04.180Z
I program [dynamically](http://cstheory.stackexchange.com/questions/5635/if-you-could-rename-dynamic-programming)!
Jeffε
CC BY-SA 3.0
2011-11-08T13:06:44.457Z
2011-11-08T13:13:28.940Z
2011-11-08T13:13:28.940Z
Alessandro Cosentino
<p>Thank you Gopi for this question. I'd like to extend the many
interesting answers in another dimension that hasn't been mentioned
yet.</p>

<p>Research is not the only thing we do at university: if you want to
stay in academia, eventually you will have to teach. If you are lucky,
you'll have to teach courses that are quite far away from your area of
specialisation. Quite likely you'll be assigned courses with a
substantial programming component. This is where even a moderate
ability to program helps substantially: you'll be much better a
teacher if you know how to program. First and foremost, you'll be more
comfortable with the material, you'll be able to answer student
questions better, and you understand the difficulties that students
have with learning to program, as you've experienced this learning
process yourself.  Moreover, you can produce better teaching material.
For instance you can test programming exercises yourself before giving
them to students, and fine-tune the level of difficulty.</p>

<p>There's an additional pragmatic dimension: teaching involves various
repetitive tasks that a skilled programmer can often automate, like
quickly making  a website that students can use to submit
coursework, and have it graded automatically (according to the number
of automated tests the code passes).</p>

CC BY-SA 3.0
2011-11-09T13:16:15.513Z
“If you are lucky, you'll have to teach courses that are quite far away from your area of specialisation.”  Is that lucky…?
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-09T14:00:18.623Z
@  Tsuyoshi: Well, it forces you to familiarise yourself with a  new subject area.  In the short term, that means a lot of work (which amortise in the long run, as you'll likely to teach this material more than once). At the same time, it broadens your intellectual horizons considerably.
Martin Berger
CC BY-SA 3.0
2011-11-10T14:10:09.487Z
@TsuyoshiIto: Yes!
Jeffε
CC BY-SA 3.0
2011-11-09T12:15:22.700Z
2017-08-04T13:36:58.883Z
2017-08-04T13:36:58.883Z
Martin Berger
<p>Programming is a good way to improve your understanding of various concepts, but it is also a dangerous time sink.</p>

<p>A typical argument <em>against</em> programming is that it makes you spend time with unimportant details; a typical argument <em>for</em> programming is that it makes you realise that details you thought are unimportant are in fact important. Becoming good at programming mainly means becoming able to deal with the unimportant parts quickly. Becoming good takes a <em>long</em> time.</p>

<p>As for the programming language to learn: "all of them" is my (tongue-in-cheek) answer.</p>

CC BY-SA 3.0
2011-11-08T23:58:59.293Z
Finaly an argument against programming :).
Gopi
CC BY-SA 3.0
2011-11-09T11:21:10.037Z
@Gopi, I think that programming can be a lot of fun and that the better understanding you gain is very important. The other answers give great examples of how programming helps understanding. So I would encourage you to learn programming, and not give up if the enterprise does not seem to pay off quickly.
Radu GRIGore
CC BY-SA 3.0
2011-11-09T12:34:17.767Z
Proving theorems is also a good way to improve your understanding of various concepts, but it's also a dangerous time sink.
Jeffε
CC BY-SA 3.0
2011-11-09T21:27:44.083Z
@JɛﬀE, my opinion is preserved by the substitution [pseudocode->proof on paper, code->proof in a proof assistant].
Radu GRIGore
CC BY-SA 3.0
2011-11-08T19:10:01.397Z
2011-11-08T19:10:01.397Z
Radu GRIGore
<p>I'm late to the party, and these are all great answers, but I have another reason: </p>

<p>Visualization. </p>

<p>Yes, often you will work with things that can't be visualized, but often you will work with things that can. Knowing how to program is indispensable for this task, and visualization can offer you a lot of insight into a problem.</p>

CC BY-SA 3.0
2011-11-09T12:27:30.037Z
I know how to program, and I am absolutely hopeless at visualization. I also suspect that there are tools that will let you visualize things without doing a lot of programming; if there aren't, there should be, and maybe will be in a few years.
Peter Shor 
CC BY-SA 3.0
2011-11-09T13:17:11.113Z
@PeterShor: Because you do not use C++!  (Just kidding)
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-09T20:00:23.200Z
@PeterShor: I'm not referring to any specific language or environment; MATLAB counts here. But knowing how to program can get you visualizations that would otherwise be incredibly inconvenient. For example, the space of two-dimensional positive-definite matrices is three-dimensional, and I wanted to visualize a family of constructs in this space. I had to come up with a transformation and then code it up to really see my objects.
Josephine Moeller
CC BY-SA 3.0
2011-11-09T20:13:38.410Z
@John ... you're right, I don't think you could have done that any other way.
Peter Shor 
CC BY-SA 3.0
2011-11-08T18:37:01.490Z
2011-11-08T18:37:01.490Z
Josephine Moeller
<p>Just a quick point: knowing how to program gives me an additional tool in theory research.  When I have an algorithm that I think will work, if it's easy enough, I might code it up and check if it actually does.  If my idea doesn't (even) work in practice, it's not very likely to work in theory, and this approach often saves me from sinking an enormous amount of time trying to prove something that's false.</p>

CC BY-SA 3.0
2011-11-21T09:46:09.273Z
Tsuyoshi Ito wrote a similar argument in his answer (second point :)).
Gopi
CC BY-SA 3.0
2011-11-21T16:21:48.427Z
Oops you're right - I missed it.
Lev Reyzin
CC BY-SA 3.0
2011-11-20T19:15:34.977Z
2011-11-20T19:15:34.977Z
Lev Reyzin
<p>No one here has addressed the practical issues of why someone studying TCS should learn programming.</p>

<p>If you are planning to do a PhD in TCS in a Computer Science department, there is a good chance you will need to take some non-Theory courses, and those will almost certainly be very programming-intensive. Depending on the program you are in, you may also need knowledge of non-Theory subjects to pass your qualifying exams.</p>

<p>When you finish your PhD, most job opportunities for TCS are in academia. If you work in academia, you will be expected to teach, and you might be expected to teach an intro-level undergrad CS class that will be more programming than theory. Even if you are teaching a theory class to undergrads, like say Algorithms, you can expect that your students will know more about programming than theory, and without knowing what your students know, it will be difficult for you to bridge the gaps in their understanding. I shudder at the thought of CS undergrads being taught by someone who does not know programming!</p>

<p>If you don't care about these practical concerns, then you can probably get by doing research without really knowing anything about programming. Certainly you have plenty of company in the TCS community, but mileage will vary depending on what exact area of Theory you're working in. For instance, if you're doing pure computational complexity theory, proving lower bounds on classes that no one has ever heard of, then it's likely that programming will be of no use to you. But if you're doing something more algorithmic, then I feel that being able to write good clean working code will strengthen your intuition if nothing else.</p>

<p>I recommend learning C (not C++). Pick-up a copy of K&amp;R and read it front-to-back. C doesn't have many of the fancy features of modern languages, but it does have simple but elegant syntax and semantics, which you should be able to learn in entirety. However, even when you understand the language in entirety, it still takes practice to master writing good elegant bug-free code in C. Nevertheless, if you can master coding in C, you will be able to master any programming language you encounter. Furthermore, that discipline will help you think how the hardware thinks, which will be beneficial when designing algorithms. </p>

<p>Ideas like pointers are very important to anyone who does algorithm design, but unfortunately, languages like Java and Python obscure them from you, so that's why I don't recommend them as a first language to someone with a math background. OOP is more important for people who have to maintain huge software projects, not someone who is designing algorithms.</p>

CC BY-SA 3.0
2012-11-09T05:27:30.270Z
2012-11-09T05:27:30.270Z
Mark
<p>An example of a C++ implementation of an interactive proof system is the following paper:
Time-Optimal Interactive Proofs For Circuit Evaluation, by Justin Thaler. It is available at <a href="http://people.seas.harvard.edu/~jthaler/" rel="nofollow">http://people.seas.harvard.edu/~jthaler/</a>. It appears to be a step towards the goal of developing a practical implementation of general-purpose interactive proof systems.</p>

<p>Similar papers and related source codes appear at the website mentioned above.</p>

CC BY-SA 3.0
2013-04-12T02:37:22.343Z
Would you explain how this paper is related to the question i.e _How important is knowing how to program for TCS_?
Nobody
CC BY-SA 3.0
2013-04-12T08:41:03.147Z
Even if it was an *example* of theoretical result which benefited from programming, it would not answer the original question?
J.y B.y
CC BY-SA 3.0
2013-04-14T11:02:54.957Z
The question asks if there is a need for a complexity theorist to know coding. The paper mentioned above clearly uses experimental results to complement theoretical concepts; this requires coding.  In any case, it took me a very long time to find a programming project that is so closely related to a central concept in theoretical computer science. I hope this post might be useful to someone on a similar search.
lgidwani
CC BY-SA 3.0
2013-04-11T16:13:06.163Z
2013-04-22T17:16:57.593Z
2013-04-22T17:16:57.593Z
lgidwani
<p>I would suggest you do not await the beginning of your course since computer science at any level involves implementing algorithms through a computer in order to accomplish/verify/solve any theory you will have to face throughout your course, ESPECIALLY at your level. </p>

<p>I had to program in grade 10 (high school) first, and I already knew how to use a command line and this really helped (this is to show you how "basic" programming skills are considered in CS). </p>

<p>The astonishment of your peers is well founded, since pseudocode and algorithms are among the first things one has to learn in order to program. </p>

<p>However, you are not to be completely lost in your forthcoming course since you can use your broader math skills (on your own) at your advantage to skip object-oriented programming to catch up faster learning a functional programming language. </p>

<ul>
<li>Functional programming is VERY math-oriented, considered harder to learn for its math background needed, considered very powerful (in its "simple", mathematic way to accomplish hard problems through elegant and "clean" means).</li>
<li>Object-orientation is good when you do not want to understand underlying algorithms and implementation principles and simply want to "reuse" already existing objects. </li>
</ul>

<p>I think you could tackle Haskell (usually not a first language) because it is purely mathematic, functional and can do basically anything you want it to. Learning Haskell would put you at a level where you would not need to learn much more to keep up, and would even put you in a situation of control and power over your course. If you're into statistics, learning R is a plus, but not near as much as Haskell. I have seen reports from mathematicians stating how surprised they were about its closeness to math and how it embraced their way of thinking. </p>

<p>Also, a challenge worth tackling (to get your hands accustomed to a programming environment fast) would be to install and use Linux (Ubuntu Linux will do). Trust me, you will learn a lot by playing with it... </p>

<p>These advices are the best way I know of catching up fast and surely for a mathematician in computer science. Besides, the open source community is very friendly and helpful and if you're stuck, IRC being the most direct way to talk about any subject through specialized channels (connect on FreeNode). Remember: asking is the only way to solve questions, be it to yourself, a forum, a search engine or in chatrooms.</p>

CC BY-SA 3.0
2011-11-20T15:45:44.280Z
I don't know how much you are answering the original question: I did not ask "how to", but more "what for".
Gopi
CC BY-SA 3.0
2011-11-18T17:15:30.097Z
2011-11-20T16:08:00.027Z
2011-11-20T16:08:00.027Z
Samuel Duclos
<p>Coming from a more mathematical background, I never really learned how to code.
I am starting a PhD in TCS and many people were surprised by how little I knew about programming (and about computer in general). I can write algorithms in pseudo-code, but I don't really know any programming language.</p>
<p>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?</p>
<p>How important is knowing how to code in TCS (in fields where programming is not directly involved)?
Are there reasons which could bring a CS 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?</p>

CC BY-SA 3.0
2011-11-07T16:48:18.870Z
Answering your last question: you should stick to an imperative language, since it's close to the RAM model (my recommendation is C, it is very simple and ubiquitous; learn from Kernighan & Ritchie's book). Learning OO is only reasonable for software engineers, and functional is nicer for mathematicians but far from the CC viewpoint.
didest
CC BY-SA 3.0
2011-11-07T18:47:35.667Z
You should have programmed some in order to write meaningful, i.e. definite and runtime-reflecting, pseudo-code. Mathematicians often do neither. Also, if you want to actually *use* the theory you develop, chances are you will have to implement something. As for languages, you are probably better off learning something functional. C is nice for performance but hard to reason about and messy in many aspects. (As you can see, YMMW)
Raphael
CC BY-SA 3.0
2011-11-08T09:17:10.147Z
I guess knowing how to program is definitely a (big?) advantage but is not essential. In the same way, depending on your specialty, some areas of maths for instance can be of great help. Yet, nobody knows everything that could be useful, so you have to make choices which depend on several factors amongst which are the relevance to your field and (very important!) your taste! As said in Tsuyoshi's answer, learn how to program if you find it fun. Last point, if you'd like to be able to quickly program some simple algorithms mainly for yourself, you could try Python which is quite easy to learn.
Bruno
CC BY-SA 3.0
2011-11-08T09:52:31.803Z
I concur with "Mathematicians often do neither."  A simple test for whether a mathematician describing an algorithm has ever really programmed is to ask "What _exactly_ do you mean by 'Given an X...'?"
Jeffε
CC BY-SA 3.0
2011-11-08T17:02:33.620Z
The answers here are pretty good, I just want to add my anecdotal evidence from the other side: while working on my MS in CompSci, I encountered dozens of theoretical PhDs that couldn't program worth beans -- basically I had to re-write all the code they gave me to make it actually "work" for more than the one case they thought about. Eventually, you are going to want to write a program to demonstrate or test your ideas, and you'll need to know how to to program anyways, so why not start out on the right foot now? (Also, it's fun!)
Chris Phillips
CC BY-SA 3.0
2011-11-08T20:02:12.113Z
Programming, what's that? Theorems are my programs. A cooking procedure is different from the cooking art. Sorry, in more than 20 years I cannot read any program code. Actually, I hate this "being realized on PC" mess. (Already this notation makes ill.) Euclid could not program. Yet he made programs for centuries.
Stasys
CC BY-SA 3.0
2011-11-08T20:28:24.090Z
@Diego: imperative languages are obsolete.
Andrej Bauer
CC BY-SA 3.0
2011-11-08T21:20:17.273Z
@AndrejBauer even if he uses a modern language, he doesn't need to understand inheritance, closures or lambda expressions to help him as a theorist. I strongly agree with Sasho's answer.
didest
CC BY-SA 3.0
2011-11-08T21:58:43.970Z
It is dependent on what you want to do. If want to something like PL theory or automated theorem proving then probably functional programming, if you want to work in combinatorics or learning probably something like MathLab is better, if you want to do algorithms/complexity then imperative is probably better (and even there you don't need to be very proficient). (ps: I hate to say it but if you want to do numerical analysis research then unfortunately you *have to* learn fortran.)
Kaveh
CC BY-SA 3.0
2011-11-09T12:27:08.397Z
@StasysJukna: Euclid was actually a really really crappy programmer.  He not only never implemented his algorithms, he never even ran them by hand on moderately complicated test cases.
Jeffε
CC BY-SA 3.0
2011-11-16T18:31:26.947Z
@JɛﬀE: Yes, Euclid was a crappy programmer, exactly this I wanted to say. We, in TCS, are tending to not distinguish between cooking books and cocking art. Euclid could. I have a great respect to people who CAN program. But I don't think that this feature means "one CAN in TCS". It will just not hurt.
Stasys
CC BY-SA 3.0
2011-12-01T07:39:32.533Z
As a day-job programmer, I have a lot of respect for TCS gurus. I say that programming is worth the required effort to learn. Real work can be done simply by supplying a symbolic/linguistic description of what to do. At the very least, it allows you to eliminate repetitive computer work: anyone who does frequent work on a computer can realize a sizable benefit. (May I suggest the ruby programming language as a great starting point)
Roy Tinker
<soft-question><big-list><advice-request><career>
How important is knowing how to program for TCS?
Gopi
# How important is knowing how to program for TCS?

(Asked by: username_0 on 2011-11-07)

Coming from a more mathematical background, I never really learned how to code.
I am starting a PhD in TCS and many people were surprised by how little I knew about programming (and about computer in general). I can write algorithms in pseudo-code, but I don't really know any programming language.

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?

How important is knowing how to code in TCS (in fields where programming is not directly involved)?
Are there reasons which could bring a CS 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?

**Tags:** soft-question, big-list, advice-request, career

> **Comments:**
> **username_1**: Answering your last question: you should stick to an imperative language, since it's close to the RAM model (my recommendation is C, it is very simple and ubiquitous; learn from Kernighan & Ritchie's book). Learning OO is only reasonable for software engineers, and functional is nicer for mathematicians but far from the CC viewpoint.  
> **username_2**: You should have programmed some in order to write meaningful, i.e. definite and runtime-reflecting, pseudo-code. Mathematicians often do neither. Also, if you want to actually *use* the theory you develop, chances are you will have to implement something. As for languages, you are probably better off learning something functional. C is nice for performance but hard to reason about and messy in many aspects. (As you can see, YMMW)  
> **username_3**: I guess knowing how to program is definitely a (big?) advantage but is not essential. In the same way, depending on your specialty, some areas of maths for instance can be of great help. Yet, nobody knows everything that could be useful, so you have to make choices which depend on several factors amongst which are the relevance to your field and (very important!) your taste! As said in Tsuyoshi's answer, learn how to program if you find it fun. Last point, if you'd like to be able to quickly program some simple algorithms mainly for yourself, you could try Python which is quite easy to learn.  
> **username_4**: I concur with "Mathematicians often do neither."  A simple test for whether a mathematician describing an algorithm has ever really programmed is to ask "What _exactly_ do you mean by 'Given an X...'?"  
> **username_5**: The answers here are pretty good, I just want to add my anecdotal evidence from the other side: while working on my MS in CompSci, I encountered dozens of theoretical PhDs that couldn't program worth beans -- basically I had to re-write all the code they gave me to make it actually "work" for more than the one case they thought about. Eventually, you are going to want to write a program to demonstrate or test your ideas, and you'll need to know how to to program anyways, so why not start out on the right foot now? (Also, it's fun!)  
> **username_6**: Programming, what's that? Theorems are my programs. A cooking procedure is different from the cooking art. Sorry, in more than 20 years I cannot read any program code. Actually, I hate this "being realized on PC" mess. (Already this notation makes ill.) Euclid could not program. Yet he made programs for centuries.  
> **username_7**: @Diego: imperative languages are obsolete.  
> **username_1**: @AndrejBauer even if he uses a modern language, he doesn't need to understand inheritance, closures or lambda expressions to help him as a theorist. I strongly agree with Sasho's answer.  
> **username_8**: It is dependent on what you want to do. If want to something like PL theory or automated theorem proving then probably functional programming, if you want to work in combinatorics or learning probably something like MathLab is better, if you want to do algorithms/complexity then imperative is probably better (and even there you don't need to be very proficient). (ps: I hate to say it but if you want to do numerical analysis research then unfortunately you *have to* learn fortran.)  
> **username_4**: @username_6Jukna: Euclid was actually a really really crappy programmer.  He not only never implemented his algorithms, he never even ran them by hand on moderately complicated test cases.  
> **username_6**: @JɛﬀE: Yes, Euclid was a crappy programmer, exactly this I wanted to say. We, in TCS, are tending to not distinguish between cooking books and cocking art. Euclid could. I have a great respect to people who CAN program. But I don't think that this feature means "one CAN in TCS". It will just not hurt.  
> **username_9**: As a day-job programmer, I have a lot of respect for TCS gurus. I say that programming is worth the required effort to learn. Real work can be done simply by supplying a symbolic/linguistic description of what to do. At the very least, it allows you to eliminate repetitive computer work: anyone who does frequent work on a computer can realize a sizable benefit. (May I suggest the ruby programming language as a great starting point)  

---

## 12 answers

### Answer by username_10 on 2011-11-07. Score: 61

Theoretical computer science is a broad field and the importance of programming depends on what you do in TCS. I will mention two ways in which programming can help you, without implying that these are the only ways.

First, if you design algorithms for problems of practical importance, implementing your algorithms and making the code available to others can be a big plus. For example, the convex hull problem arises in many fields, and people use software packages such as [cdd](http://www.ifor.math.ethz.ch/~fukuda/cdd_home/index.html) by Komei Fukuda and [lrs](http://cgm.cs.mcgill.ca/~avis/C/lrs.html) by David Avis to solve this problem. If they had published their algorithms only in papers, probably less people would have used their algorithms. More users mean more feedback and probably also more opportunities to collaborate, which is invaluable.

Second, even if you do not work in algorithms, writing a one-time code helps you to test a simple conjecture when the conjecture is suitable to numerical calculation. For example, if you wonder whether the product of three positive definite matrices always has a positive trace, it is easy to write a code to test it for some random choices of 2×2 or 3×3 positive definite matrices and find a counterexample. Although you do not advertise that you wrote any program to test the conjecture, programming can save the time which would have been spent in vain trying to prove a false statement.

The programming language to choose depends on what you want to do with programming, and it can be a topic for a whole book in my opinion. But if you design algorithms and want to implement your algorithms so that other people can use the implementation, then one important factor is availability. Although you can expect that most potential users of your code have access to a C compiler, you cannot expect that the same people have access to a Haskell compiler. For one-time programs, the choice is more based on available libraries, and includes the environments such as Matlab.

By the way, programming can also be fun.

> **Comments:**
> **username_10**: @SureshVenkat: In fact, if programming is fun, the question “How important is programming?” may not be very relevant.  But then the most part of my answer will become irrelevant.  How sad! :)  
> **username_0**: I did not think of your second argument before, indeed it seems a really good idea to test a conjecture with a short program! As for programming can be fun, so it seems, but I have yet to see over all the long week-end learning =).  
> **username_10**: @username_0: That said, many conjectures do not fit in this “test with a simple program” framework.  For example, we usually cannot test asymptotic behaviors (at least by a simple program).  But when you have some conjecture that can be tested, a little programming can be a powerful tool.  As for fun, yes, I understand.  I just did not want to ignore the “fun” viewpoint by only listing some motivations from the “usefulness” viewpoint.  
> **username_11**: Knuth's notes on a problem solving class have a wonderful example of the interplay between conjectures and code (see Problem 1): http://www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf (I particularly like the image of someone rushing into the classroom bearing a heap of printouts)  

---

### Answer by username_12 on 2011-11-08. Score: 51

I feel compelled to cite Doron Zeilberger on this:

[Opinion 37](http://www.math.rutgers.edu/~zeilberg/Opinion37.html): Programming is Even More Fun Than Proving, and, More Importantly It Gives As Much, If Not More, Insight and Understanding.

Read the opinion, it's full of gems (btw he tends to be deliberately provocative). For example, "The best way to understand something is to teach it. But even better then teaching it to humans is to teach it to a computer".

My personal experience is that even when doing purely theoretical work you will need some computing tools. I avoid a lot of tedious routine algebraic manipulations with Mathematica. I test my half-baked conjectures by brute-forcing small instances on Matlab or Python. I have co-written one paper that's pure combinatorics, and that's the work that has benefited most from running extensive computer experiments to understand what's going on. Euler made huge tables of tedious calculations to get insight into problems. We owe it to him to use our tools to automate this process when we do mathematics.

Aside from that, if you'll work on algorithms and data structures, programming will give an irreplaceable perspective on issues of efficiency and usability. My opinion here differs with others somewhat. I think learning a functional language so that you get to write proofs that type correctly is a waste of time (I think it's a great point that people who have experience with a strongly typed language probably tend to write more carefully structured proofs; I just don't think it's worth your time to go through that exercise). Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues (and, of course, learning functional programming is probably a must and will come somewhat naturally if you're interested in logic/PL semantics). Similarly, I think getting into the OO details of Java and C++ is also not the optimal way to spend your time, as the purpose of OO is to write modular re-usable code. It's the way to go if you'll produce code for others to use. But in case you want to get insight into efficiency and running time, if you care about really efficient algorithms and data structures, I second the suggestion to look into C. It lets you stay close to the machine while still providing a reasonable level of abstraction. This way you get a feel of what's fast and what's slow, what is a reasonable data structure, etc.

> **Comments:**
> **username_13**: Very good points in favor of C.  
> **username_11**: "Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues". Fighting words :)  
> **username_14**: "Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues." Which is why it is a good choice if you work in the logic or semantics side of TCS. :)  
> **username_12**: Now when I reread it sounds a little too curt. I agree that FP goes great with logic and semantics and am willing to be disproved  
> **username_4**: [Ahem.](http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki)  
> **username_12**: @JɛﬀE That's a question with a terrific answer. But looking over Okasaki's thesis still leaves me with the impression that reasoning about data structure efficiency in a functional language is possible, but can be a headache, even for data structures we consider simple.  
> **username_15**: @Sasho: All ordinary techniques still work in functional languages. The only "problem" is that functional programming encourages a style of programming and data structure design which ordinary techniques of algorithmic analysis are under-equipped to handle. (E.g., what's the big-O of function composition? The operation is *trivial*, but it completely breaks the assumptions of asymptotic complexity -- there's no simple numeric metric of size for a functional input.)  
> **username_4**: @SashoNikolov: Whenever I teach a graduate data structures class, I really really wish I could assume that everyone had some functional programming experience.  Instead of spending three 90-minute lectures to explain persistence, I could just say "Hey, did you notice that your data structures already do THIS?"  
> **username_14**: @NeelKrishnaswami: Well, lazy evaluation means that you need to think about what gets evaluated when you analyze the algorithm rather than when you write the code. So, in a sense, lazy evaluation makes algorithm analysis harder (although you don't really do more work overall).  It's a bit like the difference between memoized recursive implementations versus dynamic programming ones: For memoization you *don't* need to figure out the space usage before you write the code, so, in a sense, analyzing the space usage of a memoized implementation can be more work.  
> **username_16**: It depends on what you mean by "functional programming". If you mean programming in a pure functional language with lazy evaluation then yes, reasoning about complexity becomes difficult, and in order to get decent performance you'll probably have to force eager evaluation and implement state machines on the top of the functional layer, hoping that the complier optimizes them. If you mean using elements of the functional paradigm on a multiparadigm language such as the ML family or the Lisp family, then reasoning about complexity and getting good performance becomes more feasible.  

---

### Answer by username_13 on 2011-11-08. Score: 36

You can be a quite successful theoretical computer scientist without programming. For a few people, programming is quite difficult, and if you are one of them you shouldn't despair and switch fields.

However, for most math and computer science graduate students, learning to program is not particularly difficult, and is a skill which is very useful. You should learn a programming language, and if you enjoy it, you should try to get enough practice to become reasonably proficient at it. Then, when the point comes (and it will) that it will be useful in your research to write a program, you will be able to do it.

If you don't learn to program now, it is quite likely that when you eventually need to write a program, you won't have time to learn, and so you may not actually write it, and end up being less effective in your research. While getting a grad student or an undergrad to do this for you isn't too hard, there are a lot of times when it's much easier and less time-consuming to do it yourself rather than explain the problem to them.

What language should you learn? I'd recommend an object-oriented language, since these are the ones that are currently in most use, and I suspect this will be more true in the future. Maybe Python or Java—they're both object-oriented languages, and while they're used less in practice than C++, my impression is that they're both much, much easier to learn. (Caveat: I don't know C++, despite having worked at Bell Labs, so maybe I'm wrong about this.)

> **Comments:**
> **username_0**: I see the truth in your third paragraph :).  
> **username_17**: "However, for most people, learning to program is not particularly difficult" -- my experience leads me to disagree with this, but most people are not TCS researchers.  
> **username_13**: @username_17: You're absolutely right; let me change my answer.  
> **username_18**: if you come from math, maybe it would be easier to learn something like Mathematica or Maple. That way you won't have to bother with memory handling and other stuff.  
> **username_13**: @Marcos: Certainly learning Mathematica or Maple is good, but I suggested an object oriented language partly because of the point username_23 brought up in his answer ... if you end up in a computer science department, it's good to have some common ground with your colleagues, and maybe knowing how to program will help in your teaching.  If object oriented languages are indeed the way the world is going (as it seems right now), it will be good to know one of them.  
> **username_18**: @Peter: that's a good point.  
> **username_19**: With the rise of Sage, it is possible to work with a nice, popular language like Python while still having Mathematica/Maple/Matlab style mathematical libraries instantly available.  
> **username_16**: C++ has the most advanced type/metaprogramming system of any mainstream general purpose programming language I've seen, except the family of Lisp languages. So if you are into type theory, language design or compiler theory, or more broadly into formal semantics, you may want to be familiar with it. In addition to C++, Java and C# are a must if you want to do research in experimental Computer Science, or hope to get a job as a programmer or software engineer in the industry. Python should be taught in high schools :D  
> **username_20**: @AntonioValerioMiceli-Barone: I have to disagree, at least for type theory, language design, formal semantics and programming language theory (PLT) in general: C++ is _not_ the language to learn for those fields; TT and formal semantics relate almost exclusively to functional programming, while the PL community is more diverse, but prefers languages more elegant than C++. Haskell is the "mainstream" language with the most advanced type system, followed by Scala (less advanced, a bit more mainstream). C++ does have interesting features, but is too low-level for modern taste.  

---

### Answer by username_11 on 2011-11-10. Score: 34

There's another answer that no one has really brought up. Programming can actually lead to interesting theory. A lot of the recent developments in hashing (especially tabulation hashing) are motivated not by theoretical concerns per se, but by the fact that the theoretically optimal algorithms aren't that great in practice. This of course is something you don't know unless you can write code.

Even in the realm of exact exponential time algorithms, a motivation is producing algorithms that can actually work. SAT solvers are the canonical example of this.

In short, the ability to code allows you to realize shortcomings and weaknesses in what might look like optimal theoretical results, and that in turn opens up new theoretical research directions.

> **Comments:**
> **username_0**: Your answer could maybe help on the question about [Empirical results in TCS](http://cstheory.stackexchange.com/questions/5080/empirical-results-in-cs-papers).  
> **username_11**: maybe: but that thread has long died out :)  
> **username_0**: Indeed, I did not look at the date, it was in the last newsletter I received, in the section "Greatest hits from previous weeks" =).  

---

### Answer by username_21 on 2011-11-08. Score: 19

Three points:

1) There is an approach to mathematics called [Experimental Mathematics](http://en.wikipedia.org/wiki/Experimental_mathematics) (see also [wikipedia://Computer-aided proof](http://en.wikipedia.org/wiki/Computer-aided_proof)) where you use computer programs to investigate about patterns and structures of objects in order to come up with analytic proofs about these objects. For this approach, you better know how to program. You can be sure you will find yourself in the need of this approach to prove very theoretical statements. I believe that snobbery against programming often turns out not to be really helpful in TCS research.

2) When you learn how to program, as byproducts you learn skills that are useful in TCS. One example above all: I found out that people with coding background tend to type-check their proofs more. Even better, they tend to very often define the type of the objects they are considering (ex.: "let's consider the operators $A \in L(X,Y)$ and $B \in L(Y,C)$). This is good for the readers of a manuscript. Compilers (and interpreters) turn us into good scientists :) For this kind of skills, I feel to suggest some strongly-typed functional language.

3) When you say "to program" do you also mean "to *linear program*" or "to *semidefinite program*"? :)

> **Comments:**
> **username_13**: username_28 I know uses "to program" for "to linear program" or "to semidefinite program". You would say "to construct/solve a linear program" instead.  
> **username_21**: @PeterShor Point 3 was not serious  
> **username_13**: And of course, you **should** also learn to linear program and to semidefinite program ... both useful skills.  
> **username_22**: Point 2 alone deserves +1. I've given up on implementing an algorithm from a highly cited paper once because it just did not type.  
> **username_21**: @PeterShor I totally agree. Also, I am glad to see that you started to use this terminology too ;-)  
> **username_0**: +1 for point 2, I actually was taught a little OCaml when I was an undergrad, even-though I only used it for one year, I took the habit to check the types of my proofs.  
> **username_4**: I program [dynamically](http://cstheory.stackexchange.com/questions/5635/if-you-could-rename-dynamic-programming)!  

---

### Answer by username_23 on 2011-11-09. Score: 17

Thank you username_0 for this question. I'd like to extend the many
interesting answers in another dimension that hasn't been mentioned
yet.

Research is not the only thing we do at university: if you want to
stay in academia, eventually you will have to teach. If you are lucky,
you'll have to teach courses that are quite far away from your area of
specialisation. Quite likely you'll be assigned courses with a
substantial programming component. This is where even a moderate
ability to program helps substantially: you'll be much better a
teacher if you know how to program. First and foremost, you'll be more
comfortable with the material, you'll be able to answer student
questions better, and you understand the difficulties that students
have with learning to program, as you've experienced this learning
process yourself. Moreover, you can produce better teaching material.
For instance you can test programming exercises yourself before giving
them to students, and fine-tune the level of difficulty.

There's an additional pragmatic dimension: teaching involves various
repetitive tasks that a skilled programmer can often automate, like
quickly making a website that students can use to submit
coursework, and have it graded automatically (according to the number
of automated tests the code passes).

> **Comments:**
> **username_10**: “If you are lucky, you'll have to teach courses that are quite far away from your area of specialisation.”  Is that lucky…?  
> **username_23**: @  Tsuyoshi: Well, it forces you to familiarise yourself with a  new subject area.  In the short term, that means a lot of work (which amortise in the long run, as you'll likely to teach this material more than once). At the same time, it broadens your intellectual horizons considerably.  
> **username_4**: @TsuyoshiIto: Yes!  

---

### Answer by username_14 on 2011-11-08. Score: 13

Programming is a good way to improve your understanding of various concepts, but it is also a dangerous time sink.

A typical argument *against* programming is that it makes you spend time with unimportant details; a typical argument *for* programming is that it makes you realise that details you thought are unimportant are in fact important. Becoming good at programming mainly means becoming able to deal with the unimportant parts quickly. Becoming good takes a *long* time.

As for the programming language to learn: "all of them" is my (tongue-in-cheek) answer.

> **Comments:**
> **username_0**: Finaly an argument against programming :).  
> **username_14**: @username_0, I think that programming can be a lot of fun and that the better understanding you gain is very important. The other answers give great examples of how programming helps understanding. So I would encourage you to learn programming, and not give up if the enterprise does not seem to pay off quickly.  
> **username_4**: Proving theorems is also a good way to improve your understanding of various concepts, but it's also a dangerous time sink.  
> **username_14**: @JɛﬀE, my opinion is preserved by the substitution [pseudocode->proof on paper, code->proof in a proof assistant].  

---

### Answer by username_24 on 2011-11-08. Score: 12

I'm late to the party, and these are all great answers, but I have another reason:

Visualization.

Yes, often you will work with things that can't be visualized, but often you will work with things that can. Knowing how to program is indispensable for this task, and visualization can offer you a lot of insight into a problem.

> **Comments:**
> **username_13**: I know how to program, and I am absolutely hopeless at visualization. I also suspect that there are tools that will let you visualize things without doing a lot of programming; if there aren't, there should be, and maybe will be in a few years.  
> **username_10**: @PeterShor: Because you do not use C++!  (Just kidding)  
> **username_24**: @PeterShor: I'm not referring to any specific language or environment; MATLAB counts here. But knowing how to program can get you visualizations that would otherwise be incredibly inconvenient. For example, the space of two-dimensional positive-definite matrices is three-dimensional, and I wanted to visualize a family of constructs in this space. I had to come up with a transformation and then code it up to really see my objects.  
> **username_13**: @John ... you're right, I don't think you could have done that any other way.  

---

### Answer by username_25 on 2011-11-20. Score: 7

Just a quick point: knowing how to program gives me an additional tool in theory research. When I have an algorithm that I think will work, if it's easy enough, I might code it up and check if it actually does. If my idea doesn't (even) work in practice, it's not very likely to work in theory, and this approach often saves me from sinking an enormous amount of time trying to prove something that's false.

> **Comments:**
> **username_0**: username_10 wrote a similar argument in his answer (second point :)).  
> **username_25**: Oops you're right - I missed it.  

---

### Answer by username_26 on 2012-11-09. Score: 5

No one here has addressed the practical issues of why someone studying TCS should learn programming.

If you are planning to do a PhD in TCS in a Computer Science department, there is a good chance you will need to take some non-Theory courses, and those will almost certainly be very programming-intensive. Depending on the program you are in, you may also need knowledge of non-Theory subjects to pass your qualifying exams.

When you finish your PhD, most job opportunities for TCS are in academia. If you work in academia, you will be expected to teach, and you might be expected to teach an intro-level undergrad CS class that will be more programming than theory. Even if you are teaching a theory class to undergrads, like say Algorithms, you can expect that your students will know more about programming than theory, and without knowing what your students know, it will be difficult for you to bridge the gaps in their understanding. I shudder at the thought of CS undergrads being taught by someone who does not know programming!

If you don't care about these practical concerns, then you can probably get by doing research without really knowing anything about programming. Certainly you have plenty of company in the TCS community, but mileage will vary depending on what exact area of Theory you're working in. For instance, if you're doing pure computational complexity theory, proving lower bounds on classes that no one has ever heard of, then it's likely that programming will be of no use to you. But if you're doing something more algorithmic, then I feel that being able to write good clean working code will strengthen your intuition if nothing else.

I recommend learning C (not C++). Pick-up a copy of K&R and read it front-to-back. C doesn't have many of the fancy features of modern languages, but it does have simple but elegant syntax and semantics, which you should be able to learn in entirety. However, even when you understand the language in entirety, it still takes practice to master writing good elegant bug-free code in C. Nevertheless, if you can master coding in C, you will be able to master any programming language you encounter. Furthermore, that discipline will help you think how the hardware thinks, which will be beneficial when designing algorithms.

Ideas like pointers are very important to anyone who does algorithm design, but unfortunately, languages like Java and Python obscure them from you, so that's why I don't recommend them as a first language to someone with a math background. OOP is more important for people who have to maintain huge software projects, not someone who is designing algorithms.


---

### Answer by username_27 on 2013-04-11. Score: 0

An example of a C++ implementation of an interactive proof system is the following paper:
Time-Optimal Interactive Proofs For Circuit Evaluation, by Justin Thaler. It is available at <http://people.seas.harvard.edu/~jthaler/>. It appears to be a step towards the goal of developing a practical implementation of general-purpose interactive proof systems.

Similar papers and related source codes appear at the website mentioned above.

> **Comments:**
> **username_28**: Would you explain how this paper is related to the question i.e _How important is knowing how to program for TCS_?  
> **username_29**: Even if it was an *example* of theoretical result which benefited from programming, it would not answer the original question?  
> **username_27**: The question asks if there is a need for a complexity theorist to know coding. The paper mentioned above clearly uses experimental results to complement theoretical concepts; this requires coding.  In any case, it took me a very long time to find a programming project that is so closely related to a central concept in theoretical computer science. I hope this post might be useful to someone on a similar search.  

---

### Answer by username_30 on 2011-11-18. Score: 0

I would suggest you do not await the beginning of your course since computer science at any level involves implementing algorithms through a computer in order to accomplish/verify/solve any theory you will have to face throughout your course, ESPECIALLY at your level.

I had to program in grade 10 (high school) first, and I already knew how to use a command line and this really helped (this is to show you how "basic" programming skills are considered in CS).

The astonishment of your peers is well founded, since pseudocode and algorithms are among the first things one has to learn in order to program.

However, you are not to be completely lost in your forthcoming course since you can use your broader math skills (on your own) at your advantage to skip object-oriented programming to catch up faster learning a functional programming language.

* Functional programming is VERY math-oriented, considered harder to learn for its math background needed, considered very powerful (in its "simple", mathematic way to accomplish hard problems through elegant and "clean" means).
* Object-orientation is good when you do not want to understand underlying algorithms and implementation principles and simply want to "reuse" already existing objects.

I think you could tackle Haskell (usually not a first language) because it is purely mathematic, functional and can do basically anything you want it to. Learning Haskell would put you at a level where you would not need to learn much more to keep up, and would even put you in a situation of control and power over your course. If you're into statistics, learning R is a plus, but not near as much as Haskell. I have seen reports from mathematicians stating how surprised they were about its closeness to math and how it embraced their way of thinking.

Also, a challenge worth tackling (to get your hands accustomed to a programming environment fast) would be to install and use Linux (Ubuntu Linux will do). Trust me, you will learn a lot by playing with it...

These advices are the best way I know of catching up fast and surely for a mathematician in computer science. Besides, the open source community is very friendly and helpful and if you're stuck, IRC being the most direct way to talk about any subject through specialized channels (connect on FreeNode). Remember: asking is the only way to solve questions, be it to yourself, a forum, a search engine or in chatrooms.

> **Comments:**
> **username_0**: I don't know how much you are answering the original question: I did not ask "how to", but more "what for".  

---

