{{ message }}

Instantly share code, notes, and snippets.

# Per Vognsen pervognsen

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
Created Mar 12, 2014
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
Last active Aug 29, 2015
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)
Last active Aug 29, 2015
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.
Last active Aug 29, 2015
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).
Last active Aug 29, 2015
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
Last active Aug 29, 2015
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:
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) = = 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|| 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 , we also get T*(w) = ||T*(w)|| v. Finally, ||T(v)|| ||w|| = ||v|| ||T*(w)||
Created Apr 19, 2014
blah.cpp
View blah.cpp
 template auto make_resource(C constructor, D destructor, Args&&... args) { return std::make_unique_ptr(constructor(std::forward(args)...), destructor); }
Last active Aug 29, 2015
martinshuffle.txt
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