{{ message }}

Instantly share code, notes, and snippets.

# Per Vognsen pervognsen

Created Mar 12, 2014
earley/cyk duality
View gist:9503919
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 >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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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