How important is knowing how to program for TCS?

Question

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?

Answer 1

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 by Komei Fukuda and lrs 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.

Answer 2

I feel compelled to cite Doron Zeilberger on this:

Opinion 37: 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.

Answer 3

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.)

Answer 4

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.

Answer 5

Three points:

1) There is an approach to mathematics called Experimental Mathematics (see also wikipedia://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"? :)

Answer 6

Thank you Gopi 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).

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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 11

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.

Answer 12

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.