Problem Detail: Consider the following problem. I have a pattern $P$ of length $100$ and a text $T$ of length $n$. I want to find the minimum number of operations to transform $P$ into $T$. The operations are: Insert a single Read More …
Author: ignougroup
[Solved]: Variable Length Encoding of Integers Using a Modulus Algorithm
Problem Detail: Continuing on the theme from my last question Variable Length Encoding of Integers, I have come up with a simple encoding scheme, but for which an efficient algorithm eludes me. The constraints are simple enough: no (binary representation) number Read More …
[Solved]: Meaning of empty clause
Problem Detail: Why does the empty clause is logically equivalent to a contraddiction: $square cup square Longleftrightarrow perp$ and why the empty cube is logically equivalent to a tautology: $square cap square Longleftrightarrow top$ ? Asked By : alessandro Answered By : zarathustra Read More …
[Solved]: If $log xy=log x+log y$ then why multiplication is harder than addition?
Problem Detail: Someone told me that the $log$ function was introduced to make the calculation easier. If we have to calculate $xy$, we can calculate instead $log x+log y$ since $log xy=log x+log y$. How this can make the calculation easier? Read More …
[Solved]: How to evaluate all derivatives of a polynomial at a point with FFT?
Problem Detail: I found this problem: Evaluating all derivatives of a polynomial at a point Given a polynomial A(x) of degree-bound n, its tth derivative is defined by From the coefficient representation $(a_0, a_1, . . . , a_{n-1})$ of A(x) Read More …
[Solved]: Combinatory interpretation of lambda calculus
Problem Detail: According to Peter Selinger, The Lambda Calculus is Algebraic (PDF). Early in this article he says: The combinatory interpretation of the lambda calculus is known to be imperfect, because it does not satisfy the $ξ$-rule: under the interpretation, $M Read More …
[Solved]: Why is the PageRank vector also the eigenvector of the web adjacency matrix?
Problem Detail: From wikipedia: The PageRank values are the entries of the dominant eigenvector of the modified adjacency matrix. This makes PageRank a particularly elegant metric Can anyone please elaborate on the connection between the eigenvector and the PR vector? Why Read More …
[Solved]: Non-termination of types in Martin-Löf’s Type:Type?
Problem Detail: In the pre-history of dependent type theory, Per Martin Löf introduced a calculus that is in some sense the simplest dependent type theory and the most general form of impredicative polymorphism. It is often referred to as Type:Type because Read More …
[Solved]: A hash function with predicted collisions
Problem Detail: As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with predicted collisions? In other words, a hash function that collides for some known set Read More …
[Solved]: Is $L_p$ decidable when p is a trivial property?
Problem Detail: If $qquaddisplaystyle L_p = { langle M rangle : p in P(L(M)) text{ s.t. } p text{ is a specific trivial property} }$, where a trivial property is a property that is shared by all recursively enumerable languages or Read More …
