Application of calculus in computer science

Where are derivatives and integrals used in the field of Computer Science? What are their applications?

• For one thing, anytime you "choose an epsilon to be optimized later". Mar 13 '12 at 14:06
• Whenever a "Turing machine" is used to control/process/simulate something "physical" (robotics, CAD/CAM, image processing, computational chemistry, ...) Mar 13 '12 at 16:08
• I am not sure if this is a suitable question for cstheory, the scope of this site is research-level questions in theoretical computer science, please see the FAQ. Mar 13 '12 at 17:13
• I also have mixed feelings, even though I answered ! Mar 13 '12 at 17:39
• I just feel like the question should got moved, no downvoted! Its a perfectly legitimate question for, say, stackoverflow. Isn't it? Oct 18 '13 at 15:30

This depends on what you mean by "applying calculus to computer science." In your comment to Quaternary's answer, you make a distinction between "direct" and "indirect" application, but it's not clear to me exactly what distinction you're making. Following are some areas of computer science where calculus/analysis is applicable.

1. Scientific computing. Computer algebra systems that compute integrals and derivatives directly, either symbolically or numerically, are the most blatant examples here, but in addition, any software that simulates a physical system that is based on continuous differential equations (e.g., computational fluid dynamics) necessarily involves computing derivatives and integrals.

2. Design and analysis of algorithms. The behavior of a combinatorial algorithm on very large instances is often most easily analyzed using calculus. This is especially true for randomized algorithms; modern probability theory is heavily analytic. In the other direction, sometimes one can design an algorithm for a discrete problem by considering a continuous analogue, using calculus to solve the continuous problem, and then discretizing to obtain an algorithm for the original problem. The simplest example of this might be finding an approximate root of a polynomial equation; using calculus, one can formulate Newton's method, and then discretize it.

3. Asymptotic enumeration. Sometimes the only way to get a handle on an enumeration problem is to form a generating function and use analytic methods to estimate its asymptotic behavior. See the book Analytic Combinatorics by Flajolet and Sedgewick.

The Flajolet-Sedgewick book on analytic combinatorics demonstrates how to analyze running times of algorithms by looking at the poles of a related complex function.

There are a bunch of approximation algorithms with approximation ratio that is not a rational number. Such a number is often arrived as as the optimum of some continuous function, or as a limit. The most notorious of them is probably (1-1/e) , which can be arrived at in a surprising number of ways.

The Goemans-Williamson max cut algorithm (http://people.orie.cornell.edu/~dpw/maxcut.ps) also has an approximation ratio that is the optimum of some function.

Factor revealing LP's model worst case instances of a given size. As instance size goes to infinity the optimal LP solution sometimes approaches some continuous function. A toy example of this would be Section 4 in http://arxiv.org/pdf/cs/0612052v1.pdf (I'm sure there are others, this one I'm familiar with because I'm a coauthor on the paper).

In stochastic simulation, we are often interested in estimating the expected value of a random variable. The expected value of a continuous random variable is an integral over the real numbers. To estimate this quantity, we use the Monte Carlo method which consists of generating instances of this random variable from pseudorandom uniform variables. From these uniform variables, we can generate random variables from a given distribution by inverting the cumulative distribution function which is defined itself as an integral.

Oh hell yes!

1. Lagrange Multipliers (Entropy example)
2. Relation between crossing numbers of complete and complete bipartite graphs
3. Simpler version of Stirling’s approximation
4. It is impossible to write computer game without calculus. Many computer games use calculus.

It is used but I don't think it is used enough.

• Tetris needs calculus?! Mar 13 '12 at 23:28