# 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 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.
- Discrete
- Stepwise; jagged; cut into a finite number of pieces. Opposite of
*continuous*. - Dynamic programming
- 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*.). - 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.