# Computing Science Dictionary

I prefer being precise with terminology, sometimes to the point of annoying
others.^{1}^{1} I have learned recently that this is a general trait among hackers,
which is interesting. So here’s a list of good words to know, if you, too, want
to be precise.

I’ll start with just a few and then expand on it as I go, when I remember to.
Actually, the primary reason I’m writing it now is that I *always* forget
*pathological*, but now I have it written down!

- Amortized analysis
- Figuring out the average performance of an algorithm
when it is run a bunch of times, instead of just once
^{2}^{2}This is an important distinction. Some algorithms, like for example quicksort, is generally only run once. Others, like inserting an element into a hashtable, is generally run many times in sequence.. This is interesting because some algorithms are designed such that when they are run over and over, it is*impossible*for them to exhibit worst-case performance each time; often they are designed such that the worst case only happens very rarely, and then we want to know that when comparing it to similar algorithms. - Continuous
- Smooth; ongoing. Opposite of
*discrete*. - Deterministic
- Not random; running with the same inputs gives you the same outputs; independent of time or other hidden variables.
- Dirac delta function
The not-quite-actually-a-function \(\delta(x)\) can be intuitively be thought of as having value 0 everywhere except in one point: when \(x=0\). At that point, \(\delta(x)\) takes a value \(y\) that is sufficiently high to make the integral

\[\int_{-\infty}^{+\infty} \delta(x)\;\mathrm{d}x = 1.\]

In other words, the improper function \(\delta(x)\) has all of its unit area concentrated not in a tiny region, but under a single point. And because the function has unit area, all concentrated at \(x=0\), we also get (among many others) the relation

\[\int_{-\infty}^{+\infty} \delta(x) f(x)\;\mathrm{d}x = f(0).\]

This not-quite-a-function \(\delta(x)\) isn’t super easy to understand, but it has a bunch of interesting analytical properties. I mention this here mostly because I previously confused this with the Kronecker delta, but they are absolutely not the same thing, despite the similar name.

- Discrete
- Stepwise; jagged; cut into a finite number of pieces. Opposite of
*continuous*. - Dynamic programming
- Has nothing to do with dynamic languages or dynamic type systems.
- Entropy
- Concept from information theory; essentially synonymous with “how
many bits are needed to reconstruct this, if trying to use as few
as possible?” In other words, when you remove all redundancies, how
much information remains
^{3}^{3}Note that this implies that a completely random string has the most information, because it cannot be generated by any other means than storing it in full.? Used when talking about compression (lower entropy means it’ll get smaller when compressed), password strength (lower entropy means it’s easier to guess), randomness (lower entropy is less random) and physical processes (lower entropy means less work, because it implies some sort of order already exists, and as long as you follow that you are being helped by the universe^{4}^{4}In other words: the common saying not wanting to*burn any bridges*can in many cases be put more literally as wanting to*maintain a low entropy*or*not increase entropy without good reason*.). - Indicator function
- See the Kronecker delta function.
- Kronecker delta function
The function \(\delta(i)\) takes the value 1 when \(i = 0\), and 0 otherwise. Informally, one can also speak of the indicator function \(1_{i=0}\); these are two and the same.

This is not to be confused with the Dirac delta function (which I embarassingly did at first, but since then have fortunately been corrected by a mathematically inclined reader.)

- Metasyntactic variable
- A placeholder in general code examples that you’re supposed to replace with your concrete code.
- Nondeterministic
- Appears random. Gives different results even when run with the same inputs.
- Pathological case
- Evil case. Insidious input. Input that in some way
triggers bad performance. A situation that leads to a known bad code
path.
^{5}^{5}As an example of pathological input, feed a list that is sorted in reverse to the insertion sort algorithm, and you get terrible performance.