Skip to main content
Share Your Experience: Take the 2024 Developer Survey
124 votes
Accepted

How/when is calculus used in Computer Science?

I can think of a few courses that would need Calculus, directly. I have used bold face for the usually obligatory disciplines for a Computer Science degree, and italics for the usually optional ones. ...
Jay's user avatar
  • 1,349
30 votes

How/when is calculus used in Computer Science?

This is somewhat obscure, but calculus turns up in algebraic data types. For any given type, the type of its one-hole contexts is the derivative of that type. See this excellent talk for an overview ...
Tuomas Laakkonen's user avatar
16 votes

What is the meaning of $O(m+n)$?

Part 1 I'm going to do something I decided I wouldn't do: try to nutshell my research on this topic. I'll go over on how the algorithmic O-notation must be defined, why it is probably not what you've ...
kaba's user avatar
  • 431
13 votes

How/when is calculus used in Computer Science?

Automation - Similar to robotics, automation can require quantifying a lot of human behavior. Calculations - Finding solutions to proofs often requires calculus. Visualizations - Utilizing ...
LJones's user avatar
  • 139
13 votes

How/when is calculus used in Computer Science?

Numerical Methods. There exist cumbersome calculus problems that are unique to specific applications, and they need solutions faster than a human can practically solve without a program. Someone has ...
Jonah Havel's user avatar
11 votes

What is the meaning of $O(m+n)$?

Part 2 $$ \newcommand{\TR}{\mathbb{R}} \newcommand{\TN}{\mathbb{N}} \newcommand{\subsets}[1]{\mathcal{P}(#1)} \newcommand{\setb}[1]{\left\{#1\right\}} \newcommand{\land}{\text{ and }} $$ Algorithms ...
kaba's user avatar
  • 431
8 votes
Accepted

What is the "continuity" as a term in computable analysis?

Different people have different views on what the definition of continuity should be, but the way I see it, we should define continuity to be computability relative to some oracle. For example: ...
Arno's user avatar
  • 3,103
8 votes

What is the "continuity" as a term in computable analysis?

Arno's answer provides some very useful background reading material, I would just like to address your specific question about $\mathbb{R}$. Let us first recall a result by Peter Hertling, see Theorem ...
Andrej Bauer's user avatar
  • 30.5k
7 votes

How/when is calculus used in Computer Science?

The fact is that there's very little chance you'll ever use calculus. However, virtually every other scientific discipline DOES use calculus and you are working on a science degree. There are certain ...
Scott B's user avatar
  • 97
6 votes
Accepted

How does sum of first $k$ integers equal $k(k+1)/2$

Let me tell you the story of young Carl Friedrich Gauss. He was six years old and in a small school with one class for everyone from 6 to 16. His teacher needed some quiet time for some job, so he ...
gnasher729's user avatar
  • 30.4k
6 votes
Accepted

How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?

Let $S(n) = T(n) - 2n - 2$. You can check that $S(n) = S(n-1) + S(n/2)$ (ignoring the fact that $n/2$ need not be an integer). This shows that the additive $n$ term doesn't make a big difference. For ...
Yuval Filmus's user avatar
5 votes

Can someone explain why there are two summations here?

And why are they exactly the same? I showed a math professor and he thinks they're labelled wrong but couldn't figure it out. I don't even get why there are two. When in doubt, check the book's ...
Aristu's user avatar
  • 1,483
5 votes

How/when is calculus used in Computer Science?

Many people already provided applications in CS. But sometimes you'll find Calculus when you least expect: Regular-expression derivatives reexamined If you know automata this pdf might be worth ...
Aristu's user avatar
  • 1,483
5 votes
Accepted

What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

Let $f(n) = n/\log n$, and denote by $g(n)$ the number of applications of $f$ it takes to get $n$ below some arbitrary constant. On the one hand, $f^{(t)}(n) \geq n/\log^t n$, and so $$ g(n) \geq \...
Yuval Filmus's user avatar
4 votes

How/when is calculus used in Computer Science?

Some more specific examples: Calculus is used to derive the delta rule, which is what allows some types of neural networks to 'learn'. Calculus can be used to compute the Fourier transform of an ...
bfair's user avatar
  • 143
4 votes
Accepted

Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() Why?

If you picture these as distances along a road, it should be very intuitive. If (for example) you start at kilometer #7, then proceed through kilometers #45, #81, and #97, then the distances you ...
ruakh's user avatar
  • 633
4 votes
Accepted

Do formulas involving fewer repetitions of variables give higher numerical precision?

First, I want to say that it is not the case in general that an algorithm that minimizes the number of uses of the inputs is more accurate, at least for IEEE 754 floating point. For example, ...
Derek Elkins left SE's user avatar
3 votes

What is the exact definition of undirected graph, directed graph, unidirectional graph, bidirectional graph?

I've only ever heard of directed and undirected graphs, whose definitions can be found in Wikipedia. Rudimentary search reveals the following interpretations of unidirectional and bidirectional graphs;...
Yuval Filmus's user avatar
3 votes
Accepted

Set of all rational numbers less than given computable real number is decidable

I would approach this problem as follows. Let $a$ be the computable real, and $A = \{x\in\mathbb{Q}\ |\ x<a\}$. If $a \in \mathbb{Q}$, then $A$ is decidable since $x<a$ is a comparison between ...
chi's user avatar
  • 14.6k
3 votes

How/when is calculus used in Computer Science?

Calculus -- the integral portion -- is used directly in CS as a foundation for thinking about summation. If you work through any portion of Knuth's Concrete Mathematics section on summation, you will ...
Jess's user avatar
  • 31
3 votes

Hash function to hash 6-digit positive integers

I think you've missed the point of hash tables. Hash tables are used to give array-like access to a dataset that's too big and sparse to store in an array. So, for example, it sounds like you're ...
David Richerby's user avatar
3 votes

Hash function to hash 6-digit positive integers

A hash function cannot avoid collisions when the size $M$ of the hash table is smaller than the size of the universal set $U$ that you are hashing. This is a consequence of the compression step. In ...
Mario Cervera's user avatar
3 votes

Hash function to hash 6-digit positive integers

A hash table usually uses two different things: One, a hash function that maps an item to a hash code (with the requirement that equal items are mapped to equal hash codes), and two, a function that ...
gnasher729's user avatar
  • 30.4k
3 votes

How/when is calculus used in Computer Science?

To these other excellent answers I add this point: rigor in testing. In creating test cases for some applications I have had to make use of calculus to predict expected running times, memory sizes, ...
Paul Chernoch's user avatar
3 votes

Complexity of computing the antiderivative of a given function

Kawamura, in his paper Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete, mentions a classical result of Friedman (Theorem 3.4) which implies that computing the ...
Yuval Filmus's user avatar
3 votes

Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?

First, let us note that for monotone $f$, the statement holds for some $c > 1$ iff it holds for all $c > 1$. Indeed, let $1 < c_1 < c_2$. If the statement holds for $c_2$ then $f(c_1n) \...
Yuval Filmus's user avatar
3 votes

Can most programs (except the IO part) be re-written as a sequence of matrix operations?

If you regard the output of a program as a function of its input then matrices can be used to represent some programs, namely those where the output is a linear function of the input. So a program ...
gandalf61's user avatar
  • 1,589
3 votes

Why postfix is used more often than prefix expression?

The evaluation is easier for postfix-notation expressions. The evaluation is done easily using a stack. The expression is processed from left to right, one token at a time: operand -> put it on ...
axiac's user avatar
  • 131
3 votes

Decryption of RSA

You'll need to factor the base of the RSA public key to be able to decrypt. That is the whole point: cracking RSA is equivalent to factoring, and factoring is (presumed to be) very hard.
vonbrand's user avatar
  • 14.1k

Only top scored, non community-wiki answers of a minimum length are eligible