Thomas Cormen: Algorithms and Academia

“Computer Science is not really about computers. It’s about how we solve problems through computing and through computation.”

Thomas Cormen is a Professor of Computer Science at Dartmouth College. He wrote the textbook “Introduction to Algorithms” with Charles Leiserson, Ronald Rivest, and Clifford Stein, and it is one of the default manuals for learning about algorithms.

With the growing scope of Computer Science, Dartmouth has been hiring lecturers into niche areas. I asked if the faculty responded to this by narrowing the definition of Computer Science.

“Actually it’s the opposite. We have been broadening what the field of Computer Science is. One of the things we find is that Computer Science is in almost any field.”

From Digital Arts to Machine Learning, Computer Science is being deployed to solve all sorts of problems–both theoretical and practical.

“If you are really looking for a major impact, it’s gotta go through industry,” Professor Cormen said. “People who have really good ideas in academia will often commercialize them themselves. ”

When I asked how about the state of academic publication , he expressed concern at the growing rate of low-quality material that floods academia in response to broadly defined Computer Science conferences.

“With the proliferation of conferences out there, a lot of really sub par papers are getting published, and I think that drags down the field quite a bit.”

I attempted to wade into Professor Cormen’s deeper intellectual waters by challenging an answer to a Quora question he had given. In comparing the past strategy of computer programming to the present, he asserted:

“Then there’s today.  Students have their own computers, which is a good thing, but the computer helps them maybe too much.  Interactive development environments tell them their syntactic and even some semantic errors as they’re entering their code.  Runs are free.  No need to understand your program; just randomly morph it until it works.  And then, once it works, you don’t know why it worked.”

To me, this seemed like an unfair criticism of modern engineering. Our most pressing engineering problems today all boil down to NP-complete problems.  My objection to Professor Cormen is based on the idea that an engineer submitting answers to his compiler is no different than a Turing machine submitting problems to an oracle machine.

The Turing machine is not ashamed to invoke dynamic programming and present all sorts of potential solutions to an oracle. A student with thousands of lines of code should not be ashamed to alter his code  until it executes.

“What we do for NP-complete problems is we have approximation algorithms. There, we can prove properties. The running time is related to the quality of the approximation in an inverse relationship. You don’t typically just send things to an oracle–the oracle doesn’t really guide your search.”

But, I argued, the oracle in this case is the compiler. It tells you what line of code your program failed on.

“I don’t see that as related to NP-completeness in any way,” he responded.

I took this as a sign that there is some fundamental problem with my whole compiler-as-an-oracle proposition and moved onto the next question.

Is there a friction between the world of academia and the world of engineering, which does not prove its solutions mathematically?

“Not as much any more. We’ve kind of given up on proving programs correct. We might try to prove algorithms correct, but an algorithm is different from a program. A program is an embodiment of an algorithm in a particular language. [For proving algorithms,] we are trying to explain the essence of a solution without getting mired in the details.”

Last year, Leslie Lamport told me in an interview that he was working with TLA+ to assure that some industry code was thoroughly correct. Thinking back to that, I wondered about other ways to prove higher-level structures as correct. For example, if you can write a proof for each of the algorithms within Quora, can you extrapolate that to being able to prove that Quora does what it claims it does?

“I don’t think it does. If there are algorithms behind Quora, you don’t know whether Quora is a faithful implementation of those algorithms and you don’t know whether Quora is handling all the other conditions that can be happening…memory leaks, user error, or overflow.”

But if you prove that all of the underlying algorithms of Quora fit the spec of what they are designed to do, can you pull out a proof of something that is composed of those algorithms?

“I suppose you can. You have to show that all of the pieces fit together. There’s also a couple of other factors–even if you have the Quora code and you could show that the Quora code does what it’s supposed to do, the Quora code is probably run through a compiler or interpreter, which have to do the right thing, and it’s running on hardware, and the hardware has to do the right thing. So there are lots of opportunities for error that can pop up, even if your source code is proven correct.”

As Professor Cormen said, the standards of rigor at the algorithmic level of abstraction are higher than at the programmatic level. So how can a programmer be sure that his code is correct?

“Often it is done statistically. You look at statistics and you have an idea of what is considered a good rate of having a right answer.” There are some problems where there is just no right answer, but you do still have criteria for what a right answer is.

Though Professor Cormen is not a hardware expert, he explored some obstacles to the continued march of Moore’s Law.

“Power is becoming a gating factor. Why did Google put their data farm on the Colombia River? Because they can use that to cool it.”

“Ultimately we have all these transistors and we need to power them. No matter what we are going to hit some limits and at some point we are probably going to be needing to be thinking about a completely different technology of devices. If we look 100 years from now, it might be a completely different technology, just as 100 years ago we were looking at mechanical computing devices rather than electronic ones.”

This segued into a short discussion of futurism. I asked what he thought of the Ray Kurzweil approach: speculate to the furthest possible degree in hopes that the speculation becomes a self-fulfilling prophecy.

“To some degree it gives people something to shoot for and think about. I grew up thinking about Star Trek, and it’s a wonderful thing to try to shoot for. These things aren’t necessarily rooted in reality in any way; Kurzweil makes predictions, and some of them will come true and some of them will not.”

To conclude, I asked what kept him from stepping from academia into industry.

“There’s one thing that keeps me in academia and that’s the students. I really wanted to teach. To me, the important thing was to be able to work with students. It turns out I like it even more than I thought I would.”

“I really like taking students who are taking an introductory Computer Science course for who knows what kinda reason, and getting them excited and interested in Computer Science and what I really love is when there is a student who is not planning to study Computer Science, and they take a course from me and they end up studying Computer Science.”

“The advice I give to teachers is to be yourself. Don’t be your teachers, be yourself. Let your personality come through. Don’t be anyone else.”

Right-click to download.

Comments

comments

admin