Today I Learned

Some of the things I've learned every day since Oct 10, 2016

192: GIGO

Garbage In, Garbage Out

“If you have a really fancy method and give it garbage data, what you’ll get out is some really fancy garbage.”


191: Stability, Instability of Numerical Integration, Differentiation

Numerical integration methods such as use of the composite Simpson’s rule, composite trapezoidal rule, etc., are stable. That is, their round-off error as a result of being performed with machine arithmetic does not depend on the number of sub-intervals the integrating interval is split up into.

By contrast, numerical differentiation methods such as the 2-point, 3-point, and 5-point formulas are unstable, because these formulas involve division by the width of the step-size h used. So at a certain point as h \rightarrow 0, round-off error overtakes the increased accuracy of a small step-size and the approximations actually start to get worse.

190: A Greedy Scheduling Algorithm

Suppose you have a ‘time’ interval (a, b) with a, b \in \mathbb{R}, a < b, and that you have a set E of ‘events’ (s_1, t_1), (s_2, t_2), \dots, (s_n, t_n) with a \leq s_i < t_i \leq b for all i. And suppose you want to schedule as many events from E into (a, b) as possible. That is, you want to select a subset of non-overlapping members of E of maximum size. The following greedy algorithm does this in an optimal way (optimal solution, not necessarily runtime):


The total runtime is O(n \log n).

189: Depth-First, Breadth-First, Uniform Cost, and A* Search Differ Only In Their Fringe

As graph exploration algorithms through search problem state spaces, depth-first, breadth-first, uniform cost, and A* search all have the following general form:


Credit: University of California, Berkeley

They differ only in the type of fringe used. Depth first uses a stack, breadth-first a queue, and both uniform cost and A* use a priority queue. (Uniform cost’s priority is based on the distance from the starting point to a given node, while that of A* is the sum of this distance and the node’s heuristic function.)


188: Lagrange Interpolation

Given a real function f, a set of n+1 points x_0, \dots, x_n, and the values f(x_0), \dots, f(x_n) of f at those points, the Lagrange polynomial uses this information to give an n-th degree polynomial P which approximates f. The formula for P is

P = L_0 f(x_0) + \cdots + L_n f(x_n),


L_k = (\prod_{i \neq k} (x - x_i))/(\prod_{j \neq k} (x_k - x_j)).

Example: where n = 1 and we are given x_0, x_1, f(x_0), f(x_1), the Lagrange polynomial approximating f is

P = \frac{x - x_1}{x_0 - x_1} f(x_0) + \frac{x - x_0}{x_1 - x_0} f(x_1).

Examination of the polynomial should make it clear that it is, in a way, the simplest polynomial where P(x_k) = f(x_k) at each x_k.

187: Craig Interpolation Theorem

Where \Gamma is a set of first-order formulas, let \mathcal{A}_\Gamma be the set of function, relation, and constant symbols which occur in \Gamma. That is, the smallest set \mathcal{A} such that each formula of \Gamma is an \mathcal{L}_{\mathcal{A}}-formula.

Suppose that \Gamma is any set of formulas, \varphi_1, \varphi_2 are formulas, \Gamma \vdash (\varphi_1 \rightarrow \varphi_2), and that \mathcal{A}_{\{\varphi_1\}} \cap \mathcal{A}_{\{\varphi_2\}} \subseteq \mathcal{A}_\Gamma. Then the Craig Interpolation Theorem states that there is an \mathcal{L}_{\mathcal{A}_\Gamma}-formula \psi, the interpolant, such that

\Gamma \vdash (\varphi_1 \rightarrow \psi)


\Gamma \vdash (\psi \rightarrow \varphi_2).

186: Proof by Contradiction

Suppose \Gamma is a set of first-order formulas, \varphi is a first-order formula, and that \Gamma \cup \{\neg \varphi \} is inconsistent. Then \Gamma \vdash \varphi. This can be seen as a formal statement of the legitimacy of proof by contradiction.

Sketch of proof: If \Gamma itself is inconsistent, then it’s trivial that \Gamma \vdash \varphi. Otherwise if \Gamma is consistent, it’s clear that the problem with consistency is the addition of \neg \varphi to \Gamma, implying that \Gamma \vdash \varphi.

185: The Deduction Theorem

Let \Gamma be a set of first-order \mathcal{L}-formulas. Then for \mathcal{L}-formulas \varphi_1, \varphi_2,

\Gamma \cup \{\varphi_1\} \vdash \varphi_2 \Leftrightarrow \Gamma \vdash (\varphi_1 \rightarrow \varphi_2).

The implication from right to left is obvious, and the converse can be proven by induction on formulas.

184: TreeMap vs. HashMap vs. LinkedHashMap (Java)

In Java, TreeMap, HashMap, and LinkedHashMap are all implementations of the Map interface, and are all just different ways of mapping keys to values. Importantly, though, they differ in their lookup and insertion times, as well as ordering they maintain.

  • HashMap is implemented as an array of linked lists, and is the implementation of a hash table most people are probably most familiar with. It offers O(1)  lookup and insertion, but doesn’t maintain any ordering of its keys.
  • TreeMap is implemented as a red-black tree, and so offers O(\text{log} N ) lookup and insertion. However, its keys are ordered according to its keys’ implementation of the \texttt{Comparable} interface.
  • LinkedHashMap is implemented as a linked list and like HashMap offers O(1) time, but in addition maintains ordering of its keys according to the order in which they were added to the map.

When to use which? If you need to retrieve keys ordered by their implementation of \texttt{Comparable} (perhaps when the keys are Integers or Strings), TreeMap can do that. If you need to retrieve keys ordered by their insertion time (as in a caching system), LinkedHashMap can do that. If neither of these orderings is needed, HashMap is the best go-to, being typically faster with less overhead than the other two options.

183: Cauchy’s Argument Principle

In complex analysis, Cauchy’s Argument Principle relates the value of the contour integral of a meromorphic function along a closed curve to the number of poles and zeroes of that function inside the curve:

Suppose f is meromorphic (holomorphic except for on a set of isolated poles) on an open set which contains a closed curve \gamma and its interior, and that f has no zeroes or poles on \gamma. Then

\int _\gamma \frac{f'(z)}{f(z)}dz = 2 \pi i (Z - P),

where Z is the number of zeroes of f inside \gamma, and P the number of poles.