Skip to content

Instantly share code, notes, and snippets.

pervognsen / gist:9503919
Created Mar 12, 2014
earley/cyk duality
View gist:9503919
Anyway, onward to the duality. Using Haskell-style notation for types,
notice that cyk :: (Int, Int) -> Bool and earley :: Int -> Set Int.
Curry cyk's type to get (Int, Int) -> Bool = Int -> (Int -> Bool). But
this Int -> Bool is just the indicator function of a set. (In fact, we
are dealing with bounded integers here, so it's isomorphic to a
Boolean array.) This gives a natural type-level isomorphism between
CYK and Earley that already hints at some of the differences and
similarities between the two algorithms. For example, you'd expect a
specialized set data type (e.g. a hash table or balanced tree) to be
superior for representing sparse sets. In contrast, the blackbox
View gist:9506986
>ok, here's my overview on how to do lagrangian mechanics, hamiltonian
>mechanics, quantum mechanics, statistical mechanics, symplectic
>geometry, contact geometry, calculus of variations, dynamic
>programming, and feynman path integrals.
>dynamic programming teaches us to multiply matrixes of "transition
>costs" using a weird sort of "linear algebra" in which the role of
>addition is played by minimization of costs, and the role of
>multiplication is played by addition of costs. when this technique is
View gist:9800778
For given values of x and y, define the following function of a real parameter t:
f(t) = cos(tx) cos(x + y - tx) - sin(tx) sin(x + y - tx)
Note that f(0) = cos(x + y) and f(1) = cos(x) cos(y) - sin(x) sin(y), so this is a
smooth deformation between the two sides of the cosine addition formula. The addition
formula will follow if we can prove df/dt = 0. Let us compute:
d/dt cos(tx) cos(x + y - tx) = -sin(tx) cos(x + y - tx) + cos(tx) sin(x + y - tx))
d/dt sin(tx) sin(x + y - tx) = cos(tx) sin(x + y - tx) - sin(tx) cos(x + y - tx)
View gist:9866317
8.7 Circle through a point P and tangent to a line L with a given radius R.
Their solution: Three pages of formulas and two pages of code.
Geometric solution: The circle center C must lie on the circle with
center P and radius R and on the line resulting from displacing L by
distance R towards P. This is just a circle vs line intersection problem.
View gist:9866444
8.5. Lines tangent to two circles
Their solution: Are you fucking kidding me?
Geometric solution: Let the circles have centers A and B with radii a < b.
Consider an inner tangent with contact points P and Q. The intersection C of
PQ and AB defines a pair of similar right triangles APC and BQC with ratio a/b.
Thus C is the barycentric combination of A with weight b and B with weight a.
The case of outer tangents is similar. This reduces the problem to finding
tangents to a circle through a point (section 8.3).
View gist:9890590
Let D be a finite-dimensional real division algebra.
For any element x of D, we have an associated endomorphism on D that acts by left multiplication.
Since the endomorphism algebra over a finite-dimensional vector space is itself finite dimensional,
the elements 1, x, ..., x^m must eventually develop a linear dependency if we choose m sufficiently
large. Thus there exists real numbers a_i such that
a_0 + a_1 x + ... + a_m x^m = 0
Considering this as a real polynomial, we get a factorization into linear and irreducible quadratic
View gist:9887146
Every time we say 'polynomial' we will mean a polynomial with real coefficients.
Suppose f is a polynomial that is everywhere non-negative, i.e. f(x) >= 0 for all x.
We may assume f is monic. Indeed, we can divide by any positive number
without changing the matter, and after such normalization the leading
coefficient cannot be -1 or f would assume negative values for large enough x.
First suppose f factors completely into linear parts:
pervognsen / gist:9982014
Last active Aug 29, 2015
Variational formulation of SVD without Lagrange multipliers
View gist:9982014
Let V and W be inner product spaces and let T : V -> W be a linear map.
Define a bilinear form B : V x W -> R by B(v, w) = <T(v), w> = <v, T*(w)> and consider its
restriction to the unit spheres in V and W. Since B is continuous and the unit spheres are
compact, it must attain its maximum there. We have <T(v), w> = ||T(v)|| ||w|| cos(T(v), w)
where the two-argument cos denotes the cosine of the angle between two vectors. For fixed v,
B(v, w) is maximized by varying w so as to maximize the cosine factor since ||w|| = 1 is constant.
But the cosine is greatest when the angle is least, reaching zero when T(v) and w are collinear.
Thus at a maximum (v, w), which we know exists, we must have T(v) = ||T(v)|| w. Using the transposed
formula <v, T*(w)>, we also get T*(w) = ||T*(w)|| v. Finally, ||T(v)|| ||w|| = ||v|| ||T*(w)||
View blah.cpp
template<typename C, typename D, typename... Args>
auto make_resource(C constructor, D destructor, Args&&... args)
return std::make_unique_ptr(constructor(std::forward<Args>(args)...), destructor);
pervognsen / gist:11145747
Last active Aug 29, 2015
View gist:11145747
Let's say the cost to shuffle is C1 and the cost to press next/previous is C2,
Consider the space of songs as a continuous interval of length L.
Then the task is to select a strategy parameter r that defines the
radius of attraction: when you get within distance r, you switch to
using next and previous to converge to the target.
Dimensional analysis solution:
The relevant constants are C1, C2 and L, and r is an unknown parameter