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 |
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 |
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) |
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. |
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). |
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: |
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 |
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) = <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)|| |
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<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); | |
} |
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 |
OlderNewer