Updating maximum sum subrectangle in a sparse matrix when one element is changed I have an m x n matrix which is sparse with N non-zero entries. A modified version of Kadane's 2-d algorithm can find the maximum sum subrectangle in O(m N log n) time, which beats traditional Kadane's 2-d algorithm of O(m^2 n) for sufficiently sparse matrices. The sparse matrix algorithm, which is also O(m^2 n) time for dense matrices, matching Kadane's algorithm, can be found here https://stackoverflow.com/questions/17558028/maximum-sum-subrectangle-in-a-sparse-matrix .Now I want to know if the optimal solution can be updated quickly if one entry in the matrix is changed. By "quickly" I mean something like O(m log n) time or better. It's possible that perhaps the matrix does not have to be sparse to work out a solution, however a solution when N = O(min(m,n)) would be ok. Preprocessing is also ok as long as the amortized cost of preprocessing time per element changed matches or beats something like O(m log n) time for m changes.

Yes, absolutely.  There is a straightforward way to do what you want, if you work through the details of the algorithm given at the link in your question.  The trick is to use persistent data structures, to avoid re-computing data multiple times.

The algorithm given at your link builds a one-dimensional array A[] for each i,j (where $1\le i \le j \le m$), where A[k] = sum{B[i..j,k]}.  So, let's keep a copy of each of those arrays.  That can be done by using a persistent data structure for the array, say, a persistent balanced binary tree.  In this way, the output of the algorithm shown there is $m(m-1)/2$ 1-D arrays, one for each i,j.

Now let's say that the entry B[i*,k] gets modified in the matrix B.  Obviously, this affects the entry A[k] in each of the arrays for i,j, where i <= i* <= j.  That's at most $O(m^2)$ of the 1-D arrays.  And, we can go update that one entry of those arrays in $O(m^2)$ time.  In fact, for a sparse matrix, the running time is even less: it is something like the square of the number of non-zero entries in the k-th column of the matrix B.


Uniqueness of non-dominated two-dimensional points This question is a nice variant of How to compare n number of m-dimensional points among one another with minimum time complexity? for two dimensions.

We say point $p_i=(x^i_1, x^i_2)$ dominates point $p_j=(x^j_1, x^j_2)$ if $x^i_1 \geq x^j_1$ and $x^i_2 \geq x^j_2$. Prove that if in a set of $n$ points there are no pairs such that one dominates the other, that the points can be ordered such that one dimension is strictly ascending and the second is strictly descending.

For $n=1$ the statement is trivially true. Otherwise $n > 1$.

Sort the points in each dimension in ascending order. Let $r^i_1, r^i_2$ be the rank of point $i$ in each dimension, rounding ties down. (Thus if there is a duplicate value (1,2,2,3) we take the index of the first appearance in the list). We use 0-based indexing.

First we note that for a point $p_i$ that $w_i = r^i_1 + r^i_2$ gives an upper bound on the number of points that can't dominate $p_i$. Therefore, by a counting argument, if $w_i < n-1$ there must be a point that dominates $p_i$.

We will now assume that we have a set of points that doesn't have a dominated pair. For convenience, we rename all the points such that they are ordered in the first dimension, thus $p^0_1 \leq p^1_1 \leq \dots p^{n-1}_1$.

We will now prove that $r^i_1 = i$ and $r^i_2 = n - 1 - i$.

Clearly $r^0_1 = 0$. Therefore, $r^0_2 = n-1$, otherwise $w^0 < n-1$, and there is a point dominating $p_0$. Since $r^0_2 = n-1$ there is no point having the same value in the second dimension (otherwise, $r^0_2 < n-1$).

Assume that we have proved for the first $j$ points, we now prove for $j+1$. Note that since each of the first $j$ points have $r^i_2 = n-1 - i$, this means that there are no other points having those rankings. Since the points are in ascending order in the first dimension, $r^{j+1}_1 = j$ or $r^{j+1}_1 = {j+1}$. Let us assume by contradiction the former. Therefore, since there are no dominated pairs, we have that $r^{j+1}_2 \geq n - 1 - j$, which is a contradiction (to no other points having those rankings). Therefore, $r^{j+1}_1 = {j+1}$ and since there are no dominated pairs, $r^{j+1}_2 = n - 1 - {j+1}$, and no other point may have that value.


Recursive language with non-recursive subsets I have a professor who is really poor at explaining the material, which is what makes answering his questions very hard. Here is the question:

  Recursive language with non-recursive subsets. Does one exist?

I'm sure it is a very simple and easy answer but I can't figure it out. Don't give me the answer just point me in the right direction and I'm sure I'll figure it out.

Hint. Take a very big recursive language over any alphabet you like. Verrrry big. Something so big it has all kinds of subsets.


Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function? Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I cannot find a proof (or counter-proof) that you can invert TCFs this way. AFAIK, all injective functions are invertible, but can we also invert a non-injective function and compute all the possible inputs that would result in the desired output?

In general, no, we can't conclude that $B$ is recursive. We can choose $f$ so that $B$ is the halting problem, for instance.

To do that, choose any TM $M_0$ which halts on the empty input.

We define $f(x)$ as follows. Let $M,n$ be such that $\langle M, k \rangle = x$ where
$\langle -, - \rangle$ is any computable pairing function (bijection).
Then, run $M$ on empty input for $k$ steps. If that halts, return $\langle M \rangle$, otherwise return $\langle M_0 \rangle$.

It is then easy to verify that, using such $f$, we have

$$
\begin{array}{ll}
B &= \{ \langle M' \rangle \ |\ \exists M,k. f(\langle M,k \rangle)= \langle M' \rangle \}
\\
&= \{ \langle M' \rangle \ |\ \exists k. M' \mbox{ halts in $k$ steps } \}
\\
&= \{ \langle M' \rangle \ |\ M' \mbox{ halts} \}
\end{array}
$$

With some more effort, we can even make $f$ injective, yet obtain the same $B$ (halting problem).

Indeed, a well-known result states that any RE nonempty set $A$ is the image of some total computable function $g: \mathbb N \to \mathbb N$. For the halting problem $A$ is infinite and RE, so there is such a $g$. Exploiting $g$ we can define $f(x)$ as $g(y)$ where $y$ is the least number such that $\{g(0),g(1),\ldots,g(y)\}$ contains exactly $x+1$ (non-duplicate) elements.

Note that $y$ exists since the image of $g$ ($A$) is infinite.

In such way the image of $f$ is the same as the one of $g$, i.e. $A$, but $f$ is now injective by construction. ($f$ is not surjective, of course)


I want a fast rank only shuffling algorithm for a full 52 card deck My goal is to do some large iteration Monte Carlo simulation of different card games that require on the order of 1 billion random decks to get a reliably accurate answer.  The bulk of the computer time is actually shuffling/preparing the decks, not searching for the "hit" criteria I am looking for.

I am using an string function rich interpreted language.  I have bit functions available that work up to 32 bit at a time.  I am only interested in the ranks of the 52 card deck, not the suits.  So I am looking for a fast algorithm that will give me 4 of each of the 13 ranks for a full 52 card deck.  It doesn't matter which order the suits of a particular rank come in since we are ignoring the suits (other than we are enforcing that there only be 4 of each suit for each rank).

My first attempt was to just generate a normal deck with the ranks and suits "encoded" using cards numbered 1 thru 52 with an array of flags telling which cards were already seen.  Each random number generated, (from 1 to 52), was for determining the next card (if there was no collision).  This algorithm worked but was kinda slow, only producing about 6000 full decks per second on a 3.06 Ghz dual core computer (using only about 50% of the CPU).

My 2nd attempt was just to tweak the first attempt by only picking the first 48 cards (since the "seen" ratio is very high for the last 4 cards and likely many collisions will occur, slowing it down), then choosing a random number from 1 to 24 to handle the permutations of the last 4 "missing" cards which are known from simply scanning the flag array and finding the 4 that are marked "false" meaning they haven't been seen yet.  This was roughly 50% faster as I was able to generate about 9000 full decks per second vs. about 6000 previously.

For my 3rd attempt, I am using a 32 bit random number to place 4 or 8 cards at a time from the unshuffled deck into a built up shuffled deck.

Any help/ideas would be greatly appreciated.

I'm pretty sure there's no way to take any significant advantage of the fact that you don't care about the suits.  The most effective solution is likely to just generate random permutations of the integers from 0 to 51, and map these to card ranks by dividing by 4 and rounding down (which can be done with a simple bit shift, since 4 is a power of 2).

As Apass.Jack notes in their answer, for generating the permutations you almost certainly want to use some form of the Fisher–Yates–Durstenfeld–Knuth shuffle, since it avoids the inefficiency of the sample-and-reject-duplicates method when only a few valid choices remain.  Since you're generating permutations of consecutive integers, you may want to consider using the "inside-out" variant of the shuffle (probably first described by Knuth in 1994):

for i from 0 to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i
        a[i] ← a[j]
    a[j] ← i

The main advantage of this algorithm over the "standard" FYDK shuffle is that you don't need to initialize the results array a before shuffling it, since it gets dynamically initialized during the shuffle.

Nonetheless, you may want to implement both a standard FYDK shuffle and the inside-out variant and benchmark them, since their different memory access patterns can affect real-world performance in ways that are hard to predict in advance.

In any case, at this point the biggest remaining opportunities for optimization are likely to be:

using random numbers more efficiently,
using a faster random number generator, and
switching to a lower-level language.

Of these three, I'd actually recommend starting with #3; this is exactly the kind of problem where using a low-level compiled language like C or C++ (or even a mid-level language with a good JIT compiler, like Java) can provide significant performance benefits with relatively little cost in development effort.

Once you've ported your code to a low-level language, you may want to consider optimizing your choice of RNG.  There are some pretty fast PRNGs out there (my personal favorite being Bob Jenkins' "flea" RNG, as reviewed e.g. here), but to properly realize their benefits, you need to also minimize the overhead cost of calling the generator (ideally, letting your compiler inline the PRNG code directly into your shuffling loop).

Finally, it's worth noting that most PRNGs generate something like 32 or more bits of (pseudo)randomness per call, whereas a Fisher-Yates shuffle of a 52 card deck only uses less than 6 bits per iteration.  Thus, there could certainly be room for optimization by splitting RNG outputs into smaller pieces and reusing them for multiple iterations of the shuffling loop.

That said, I'd personally rather avoid this option, at least until I had exhausted all other possible avenues for optimization.  One problem is that, even if your RNG provides perfectly random outputs, it's easy to introduce subtle bugs in the splitting process that can bias your results in ways that may not be so easy to detect.  Another problem is that trying to squeeze every last drop of entropy out of your (P)RNG output is a good way to magnify any non-random biases that output may have.  Personally, I would feel safer using a fast but possibly not quite perfect PRNG to generate lots of extra random bits, and converting them to random numbers in the required range in a simple and relatively foolproof way, than trying to use up every last bit of my RNG output and relying on that RNG and my conversion code having no subtle weaknesses.

Still, there are some simple optimizations you can safely make here.  For example, you can trivially save one RNG call (and some other unnecessary work) per shuffle by modifying the code above to look like this:

a[0] ← 0
for i from 1 to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i
        a[i] ← a[j]
    a[j] ← i

The only difference between this code and the version I copied from Wikipedia above is that I skipped the first iteration, where we always had i = j = 0, and instead just initialized a[0] before the loop.  While such little optimizations won't have much effect alone, they're pretty easy and safe and can add up.

In fact, since you said don't care about the card suits, I guess we can save a few more RNG calls:

for i from 0 to 3 do
    a[i] ← 0
for i from 4 to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i
        a[i] ← a[j]
    a[j] ← ⌊i / 4⌋

This generates the card ranks directly, by doing the division by 4 inside the initialize-and-shuffle loop, and splits the first four iterations of that loop (where all elements of the array are still identical) into a separate loop.  This way, you'll only need 48 RNG calls to shuffle 52 cards.  That's almost an 8% speedup (assuming that random number generation dominates the time cost), which might be significant just by itself.

Ps. FWIW, while precalculating the shuffled decks and storing them on disk is certainly an option worth considering, I very much doubt it is optimal.  With a fast shuffle and a fast RNG, both implemented in a low-level language, shuffling the decks dynamically should be orders of magnitude faster than reading them from even a very fast solid-state disk.

Addendum: There's a potential advantage to reshuffling your previously shuffled decks, rather than generating a new deck for each shuffle: it can smooth out possible biases in your shuffling process and give you a more uniform distribution of shuffles.

Basically, if you start with a new in-order deck for each shuffle (or generate one during the shuffle, like the code above does), then you're repeatedly sampling decks from the same distribution.  If your RNG (or the way you convert its output into array indices) is not perfect, then this distribution may be biased.

In particular, if you're using a PRNG with less than $\log_2(52!) \approx 225.6$ bits of internal state, then you're guaranteed to have some decks that you can never generate by shuffling an in-order deck, simply because there will be more possible decks than there are possible initial states for your PRNG at the beginning of the shuffle.  If you don't care about the suits, the corresponding threshold drops to $\log_2(52! \mathbin/ 4!^{13}) \approx 166$ bits.  But of course, in either case, you'd need at least twice as many bits just to be reasonably sure that all possible decks can be generated, and even more to guarantee a reasonable level of uniformity.

On the other hand, if you keep reshuffling a previously shuffled deck, then you're effectively performing a (pseudo)random walk on the set of possible permutations, with the possible transitions defined by the relation "$A$ can be shuffled into $B$ by the PRNG".  As long as this random walk is ergodic (and it should usually be, even for pretty crappy RNGs), it should converge towards a uniform distribution on the set of all possible permutations (since the transition kernel is also invariant with respect to the semigroup action).

Thus, if you could keep shuffling the same deck over and over, even with a poor-quality PRNG, you should in principle have a pretty high chance of eventually encountering each possible shuffle equally often.  Of course, the order in which you'd encounter these shuffles might not be fully random, and (if you never reseeded the PRNG from a truly random source) there would still be a small probability of getting caught in a short cycle that visits only some of the possible shuffles.  And of course, with a 52 card deck (with or without suits), you'd never actually be able to test this within your lifetime on any computer you could possibly build.

But still, in general, a good rule of thumb is that reshuffling the same deck over and over will tend to smooth out any possible biases in the shuffling process, compared to starting from an unshuffled deck each time.  In fact, that's pretty much the reason why the often rather imperfect shuffling done by humans using a physical deck of cards is still sufficient to avoid generating noticeably biased decks, and why card players are advised to be extra careful in shuffling a new deck before using it for the first time.

Fortunately, both the standard Fisher-Yates shuffle and the inside-out version described above can be easily made to reshuffle an existing deck.  In fact, the standard version does that by default, while for the inside-out variant the changes are minor.  Specifically, assuming that a is already a (possibly shuffled) permutation of n cards, either of the following loops will serve to reshuffle it:

// standard FYDK shuffle (descending order)
for i from n - 1 down to 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i: swap a[i] and a[j]

// "inside-out" version (Knuth 1994)
for i from 1 up to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i: swap a[i] and a[j]

Either of these will require $n-1$ RNG calls to (re)shuffle an $n$ card deck; unfortunately, in this case, I really don't see any practical way to save any more RNG calls even if some of the cards in the deck are known to be equivalent.

Addendum 2: If your language / CPU can do fast 256-bit math (specifically, division and remainder), and you have access to a high-quality RNG than can generate 256-bit numbers quickly (such as using two calls to AES_CTR_DRBG, which should be pretty fast on x86 CPUs that support the AES-NI instruction set, if your crypto library makes use of it), then you could do something like this:

r ← random 256-bit integer (i.e. 0 ≤ r < 2^256)

// optional bias elimination via rejection sampling
while r < 2^256 mod 52!
    r ← random 256-bit integer (i.e. 0 ≤ r < 2^256)

// inside-out FYDK shuffle-and-initialize
a[0] ← 0
for i from 1 to 51 do
    j ← r mod (i + 1)
    r ← ⌊r / (i + 1)⌋
    if j ≠ i: a[i] ← a[j]
    a[j] ← i

where hopefully either your compiler is smart enough to fuse the modular reduction and division of r by i + 1 into a single operation, or your language directly provides a combined "divmod" operator or function for it.

As noted in the comments above, the bias elimination by rejection sampling is not strictly required; omitting it just means that about 30% of all possible shuffles are very slightly more likely (about $1 + \frac{52!}{2^{256}} \approx 1.0000000007$ times as likely, to be exact) to occur than the rest.  It's up to you to decide whether that bias is something you're willing to accept.  If you do decide to use the bias elimination, do precalculate the constant 2^256 mod 52!, as calculating it from scratch is likely to be almost as expensive as the shuffle itself.

If you don't have access to efficient 256-bit math, you can always split the shuffling loop into smaller pieces.  For example, $20!$, $32!\mathbin/20!$, $43!\mathbin/32!$ and $52!\mathbin/43!$ are all less than $2^{64}$, so using 64-bit math you could do something like this:

s ← 1
a[0] ← 0
for t in (20, 32, 43, 52) do
    m ← 2^64 mod (t! / s!)
    r ← random integer such that m ≤ r < 2^64
    for i from s to t - 1 do
        j ← r mod (i + 1)
        r ← ⌊r / (i + 1)⌋
        if j ≠ i: a[i] ← a[j]
        a[j] ← i
    s ← t

where I'm assuming that the code used to generate a random integer such that m ≤ r < 2^64 internally consumes 64-bit random numbers and does any rejection sampling needed to ensure that the fall into the desired range.  Of course, in practice you'd probably want to unroll the outer loop and to precalculate the m values for each iteration, or at least to store them in a look-up table.

If you're limited to 32-bit math (or, in particular, if you only have a 64 → 32 + 32 bit divmod operation), you can instead iterate over t in (12, 19, 25, 30, 35, 40, 44, 48, 52) and set m to 2^32 mod (t! / s!).  Note that this requires nine iterations of the outer loop instead of eight, since there will be some unused entropy left in r at the end of each iteration.  In principle we could recycle this entropy, but that would complicate the code even more, so I'll leave that as an exercise. ;-)

In any case, whichever method you choose, you will definitely want to test your code very throughly before using it.  I have not done so myself for the pseudocode examples above, so they might contain bugs, and porting them from pseudocode to your actual programming language could easily introduce more.

Unfortunately, shuffling is exactly the kind of task where it's very easy to make subtle mistakes that are hard to catch in testing due to the inherent stochasticity of the task.  Some useful tests I'd recommend include:

shuffling a small deck of, say, 3 to 5 cards many times, and checking that each possible shuffle occurs approximately equally often (e.g. using Pearson's $\chi^2$ test);
shuffling a full 52 card deck many times (starting with an ordered deck each time, to maximize any observable bias), recording the position of some specific card in the deck, and checking that those positions are approximately uniformly distributed (again using e.g. a $\chi^2$ test; repeat this for each of the 52 cards);
same as above, but instead recording the distribution of cards occurring in a given position in the shuffled deck;
same as the two tests above, but instead record the difference in the positions of two specific cards (modulo 52) or the difference in the card values at two specific positions in the shuffled deck (note that in both cases there will be 51 possible differences, since 0 is not a possible result);
same as above, but instead of just recording the difference, record each observed pair of positions or card values (note that you'll need more shuffles per test for this, since there will now be 52 × 51 possible outcomes);
count the number of disjoint cycles in the permutation generated by the shuffle, and check that the distribution of this count over many shuffles matches the expected distribution given by the Stirling numbers of the first kind (in particular, this test should catch any off-by-one errors leading to an accidental implementation of Sattolo's algorithm instead of the standard FYDK shuffle);
other statistical randomness tests, especially any tests that would directly measure some specific property that you both care about in your actual simulation and can predict the theoretically expected distribution of.


Is this language regular or not? $L_1=\{a^ku \mid u \in \{a,b\}^* $ and $u$ contains at least $k$ a's, for $k\geq 1\}$.

If it is regular, I haven't found its regular expression or any closure property to prove it.

If not, it seems pumping theorem holds for it...

Also, what about the language where the above "at least" is changed to "at most"?

Take $k=1$. No need to go further, any more $a$ can be absorbed by $u$ without risk.

So you need $u$ to have at least 1 $a$ and only $a$'s or $b$'s. Therefore, $L_1$ is described by $a(a|b)^*a(a|b)^*$ and is regular.

For the side question (at most $k$ $a$'s, let's call that language $L_2$), you can reason in a similar fashion to get $u$ as small as possible. For simplicity let's consider $L_3$ the intersection of $L_2$ with the one denoted by $a^*ba^*$. You have $L_3=\{a^k b a^j, k \geq j\}$. Intersection with its reverse yields $\{a^kba^k\}$ which is not regular, therefore $L_2$ is not regular either since regular languages are closed under intersection and reversal.


Can Floyd-Warshall be used to solve an APSP problem without copying the matrix? According to CLRS, each iteration of the outermost loop (on $k$) makes a new copy of the adjacency matrix. Is it safe not to copy the matrix on every iteration?

What I mean is, according to CLRS:

$d_{ij}^K = \min(d_{ij}^{K-1}, d_{ik}^{K-1} + d_{kj}^{K-1})$

Is the following possible?

$d_{ij} = \min(d_{ij}, d_{ik} + d_{kj})$

I have tried not copying the matrix, and got the same result before as the one which makes a copy after each iteration, but did I just get lucky?

No you are not lucky, it is possible to use the program that way. The notation $d_{ij}^k$ probably is used for better explaining what the algorithm has achieved in the $k$th step. Note that the variant where one overwrites the matrix as you suggest is presented in Exercise 25.2-4 (in my second edition of the book, which is not the latest).

The secret to that puzzle is in principle that an assignment to $d_{i,j}^k$ is only done once, and that value is never again used in the computation, except for the case where either $i=k$ or $j=k$. However, the algorithm does not change those values in the $k$th step. You figure out why.


Computability - Can a Turing Machine calculate the input's length? I have looked for an answer for this question which seems trivial, but I didn't find any.

  Can a Turing machine, given a word $w$, calculate the length of the word?

Yes, of course it can. As a simple intuition, replace "Turing machine" with "computer program" and the answer shouldn't change, assuming that the Church–Turing thesis is true.

Just use a portion of the tape after the input as a binary counter and shuttle back and forth increasing that counter by one for every character in the input, marking the characters that you've already counted.


$O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree I'm having trouble making an algorithm to fit these specs:

Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves.
Reading the leaves from left to right makes a sequence of integers (we can assume we have an array)

Goal: How can we minimize the number of inversions in that array only by choosing non-leaf nodes and swapping the the subtrees under the given nodes. For example, if the sequence is (4,2,1,3), then choosing the root (swapping its direct children) followed by choosing the right child of the root (and swapping its direct children) turns the sequence into (1,3,2,4), which has only one inversion. This would be the minimum number of inversions.

My approach: My idea was to use something like merge sort but modified. First i would recursively split the array and then when I merge back together I'd need to change the strategy. For the first level of merges (say I have the integers [2] and [1]) I can simply put those in the correct order because our swapping operation doesn't prevent this.

However, once I have to merge something like [1,2] and [3,4] (and larger groups which are powers of 2), I have to move those groups as single units (because of the operation we have to use). I can't put it in exact order like I want but I was thinking maybe it would be best to merge the larger groups by summing up all the numbers inside the groups and moving the groups with the smallest sums to the left to minimize inversions. That seems inefficient though. All the while I have to somehow count inversions. I'm really kind of lost on what to do besides what I've thought of so far. Would anyone be able to help?

Let us denote by $L(x)$ the set of leaves in the subtree rooted at $x$. The idea is that the decision whether to switch the two children $x_1,x_2$ of $x$ depends only on $L(x_1),L(x_2)$, and depends on how many of the pairs $(a,b) \in L(x_1) \times L(x_2)$ satisfy $a < b$ and how many satisfy $b < a$.

If the sets $L(x_1),L(x_2)$ were available to you in their sorted forms, then you could count the number of pairs of each type by merging these sets and doing some accounting. This suggests a recursive algorithm which sorts the leaves using the merge sort strategy.

Details left to you.


Elegant algorithm to semi-decide if two lambda calculus terms are equivalent Given two lambda terms $t_1$ and $t_2$, it is semi-decidable if they are equivalent (i.e. can be rewritten as each other using alpha, beta, and eta conversions). An algorithm to do this is to try every sequence of rewrites starting with $t_1$, and if any of them end with $t_2$, then output true.

What other algorithms can be used? Are there any more "elegant" algorithms?

EDIT: [This] claims that a generalization of the Knuth-Bendix completion algorithm can semidecide the word problem. It has not citations though.

Let’s first suppose we can reduce both $t_1$ and $t_2$ to their $\beta \eta$-normal forms;
$$t_1 \twoheadrightarrow_{\beta \eta} M \qquad \text{and} \qquad t_2 \twoheadrightarrow_{\beta \eta} N$$
If $M$ and $N$ are identical, we are done. Otherwise, we check $\alpha$-equivalence by induction on term complexity:

if $M$ is a variable

if $N \equiv M$, output true

if $M$ is an abstraction $(\lambda x. M_1)$

if $N$ is an abstraction $(\lambda y. N_1)$

output whether $N_1[y:=x]$ and $M_1$ are $\alpha$-equivalent

if $M$ is an application $(M_1\ M_2)$

if $N$ is an application $(N_1\ N_2)$

output whether both $M_1$ is $\alpha$-equivalent to $N_1$ and $M_2$ is $\alpha$-equivalent to $N_2$

(You could also use de Bruijn notation and avoid the need for $\alpha$-conversions.)

For non-normalising terms, you can at best use the above procedure after each $\beta \eta$ reduction, but it shouldn't be possible (because of Halting problem) to have anything better than “iterative trying”.


Finding the kth element of a permutation Is there a way to generate a random permutation of the numbers 1 to N such that I can find the k-th element of the permuted list without needing to either 1) store the entire permuted list, or 2) compute the elements 1..k-1?

Problem statement

Your question is unclear, but here is how I interpret it:

  Input: a positive integer $n$, and $k$ distinct values $x_1,\dots,x_k \in \{1,2,\dots,n\}$
  Output: the values $\pi(x_1),\pi(x_2),\dots,\pi(x_k)$, where $\pi$ is a random permutation on $\{1,2,\dots,n\}$

You are looking for an efficient algorithm to solve this problem.

An efficient solution

If that is indeed what you are looking for, there is a very efficient way to solve this problem.  Basically, all you need to do is randomly choose $k$ distinct integers from the set $\{1,2,\dots,n\}$.  This is sampling without replacement.  Here is a simple algorithm:

Initialize $S$ to be the empty set.
For $i=1,2,\dots,k$:

Pick $r$ uniformly at random from $\{1,2,\dots,n\}$.  If $r\in S$, pick a new $r$ (and keep repeating until $r \notin S$).
Set $x_i$ to $r$, and add $r$ to $S$.

You can use any number of data structures for storing the set $S$; it could be a bitvector of length $n$, or a hashtable.  (A bitvector is probably better if $k$ is not too much smaller than $n$, say $k \ge n/64$ or so; a hashtable is probably more efficient if $k$ is small compared to $n$.)

Performance analysis

If $k \le n/2$, the expected running time is linear in $n$, so this is very efficient.

If $k \ge n/2$, there are better algorithms.  For instance, once you reach $i \ge n/2$, then rather than choosely uniformly, you can choose uniformly at random from $\overline{S}$ (the complement of $S$).  If you use the right data structures, you can make the expected running time be linear in $n$.  (Basically, once $i\ge n/2$, you compute $\overline{S}$ and throw away $S$.  In each step, you choose a random element of $\overline{S}$, then remove it from $\overline{S}$.  Choosing a random element of a set can be done in $O(1)$ expected time.)


Does Reverse Polish Notation have an LL grammar? Let L be the language of all arithmetic expressions written in Reverse Polish Notation, containing only binary operators. $\Sigma(L) = \{n, o\}$, n := number, o := operator.

Is there an LL grammar G so that L(G) = L?

Yes,

$
G = (\{E,S,R\}, \{n,o\}, P, E)\text{, with productions}\\
E \rightarrow n\ |\ SR \\
S \rightarrow nEo \\
R \rightarrow EoR\ |\ \epsilon \\
$

Proof:

Observation $(*)$: Each word of L represents an arithmetic expression, the result of calculating such an expression is essentially again a number. So whenever we have $w \in L$, we can treat $w$ as a number.
Theorems:

$L(G) \subset L$
$L(S) \subset L$
$w \in L(R) \implies w=\epsilon \lor (w=w_1 o, w_1 \in L)$

Inductive proof of above theorems on derivation step count $n$:

Basis $n=1$

$E \Rightarrow n\\
            \land \\
            n \in L
            $
$S\text{ can't generate any words in one step. }\\
            \land \\
            \emptyset \subset L
            $
$R \Rightarrow \epsilon, w=\epsilon$

Basis $n=2$

In all 3 cases nothing can be generated in 2 steps, and the theorems hold trivially.
Inductive step: $n=k>1,$ induction hypothesis (IH): assume theorems hold for $n<k$

$E \Rightarrow SR \Rightarrow^{k-1} w_1 w_2\, \\
           \text{where }w_1 \in L\text{ because of IH of theorem 2,} \\
           \text{and } w_2 = \epsilon\text{ or }w_2 = w_3 o, w_3 \in L\text{ because of IH of theorem 3.}$

First case: $w_2 = \epsilon$, then $w_1 w_2 = w_1 \in L$.
Second case: $w_1 w_2 = w_1 w_3 o =^{(*)} nno$, which is a valid RPN expression, thus $w_1 w_3 o \in L$

$S \Rightarrow nEo \Rightarrow^{k-1} nwo$, where $w \in L$ because of IH of theorem 1. $nwo =^{(*)} nno$, which is a valid RPN expression, and thus $n w o \in L$
$R \Rightarrow EoR \Rightarrow^{k-2} w_1 o R$, where $w_1 \in L$ because of IH of theorem 1. The last step can only be $w_1 o R \Rightarrow w_1 o \epsilon$, which satisfies theorem 3.

$\square$
Theorem: $L \subset L(G)$

Proof: induction on length of $w \in L$, show that $E \Rightarrow^* w$

(I got lazy from this point on, I might fill this in later)

$\square$
$(1) \land (2) \implies L(G) = L$
Theorem: G is LL(k) grammar, $k \in \mathbb{N}$

Proof: Pick a k large enough, then show that for each non-terminal you can decide which production rule to use by looking at the k next terminals.

$\square$

$\square$


Complexity of forming a min heap out of a given array with k inversions If a given heap has $k$ inversions, what is the complexity of making it into a valid min heap? We could define an inversion as a tuple (node, descendant), where the node has a key value strictly higher than its descendant (all nodes have distinct key values).

This isn't an interview question, but is something that I thought of while learning about heaps. Searching for it on google gives zero hits.

Back when we learnt arrays and how to sort them, we were told that sorting arrays requires $\mathcal{O}(n + k)$ ($k$ = number of inversions) time complexity in insertion sort. I wonder if something similar exists for making a heap out of a given array.

I attempted to approach this problem in the following way. Assume a full binary tree (one with number of nodes equal to $2^h - 1$ ($h$ = height)). Note that we perform the sift down operation only when there exists an inversion. In the best case, the input array is already sorted so complexity is just order $n$, no sift downs are performed. In the worst case, input array is reverse sorted, so each internal node needs to be sifted down. That's summation of $\frac {(n + 1)}4 + \frac {(n + 1)}8\cdot2+\frac {(n + 1)}{16}\cdot3+\ldots= n-1$ siftdowns (solving it as a arithmetico geometric sequence) in the worst case, plus having to loop through the entire array .

In a more general case, I would say that we are visiting each node internal node once, performing a comparison with its children for cost $c$, and if it is out of place, perform a siftdown for additional cost $d$. If $i$-th internal node undergoes siftdown $k_i$ times, then we can formulate the total complexity as:

$$=\sum_{i=1}^{(n + 1) / 2}(c\cdot(k_i+1) +d\cdot k_i)$$

(as you always perform comparisons one more time than total number of siftdowns, except when you reach leaf node, which I approximated away)

This gives us:

$$=(c+d)k+\frac{(n+1)}2\cdot c$$

This suggests to me that that in worst case reverse sorted array, the order should be $n^2$, as the number of inversions $k$ is of that order. However, that we already know is not the case. Where is my analysis going wrong then?

We remove the inversions by beginning from the bottom (furthest level from the root) and going breadth-first up.

Start at the bottom level.  We have a set of leaves, each satisfying the heap property.
Move one level up. If there is an inversion at this level, we fix it by sifting down. Now all sub-heaps from the bottom up to and including this level satisfy the heap property.
Continue applying 2. until finishing at the root level.

Suppose in the worst case that the $k$ inversions fill the top levels of a heap of height $h = \lfloor log(n) \rfloor + 1$. We have at most $\Sigma^{\lfloor log(k) \rfloor + 1}_{i = 0} 2^i \cdot (h - (i + 1))$ swaps for sifting down, where $2^i$ represents the number of inversions at a given depth from the root. This is $O(n)$.


How is the Subset Sum Problem NP-Complete? You can't find a solution online for it that doesn't run in polynomial time complexity, when using dynamic programming. Have all these sites secretly solved P=NP, and no one knows about it?

The dynamic programming approaches only solve the problem in pseudopolynomial time.

Recall that the definition of (nondeterministic) polynomial time is that the problem must be solvable by a (nondeterministic) Turing machine whose running time is bounded by some polynomial in the size of the input.  The size of the input is the number of bits required to write it down.

Suppose we want to solve a subset sum instance where the set has size $k$ (i.e., contains $k$ integers), and suppose this takes $n$ bits to write down. The dynamic programming approach builds up a table with $k$ rows and one column for each possible partial sum. How big is this table? Well, surely $k\leq n$, since we can't write down more than $n$ numbers in only $n$ bits.  However, a partial sum is the sum of some number of integers, each of which takes about $n/k$ bits to write down. So that sum is also going to take roughly $n/k$ bits to write down. That means that there are roughly $2^{n/k}$ columns in our table, so our table is exponentially large and we can't populate it in polynomial time.

The algorithm runs in pseudopolynomial time, which means that it runs in time bounded by some polynomial in the numbers represented in the instance, rather than in the number of bits required to write them down.

(In fact, this dynamic programming approach uses even more memory than doing dynamic programming on subsets.  Suppose, for example, that your set is $\{1,100\}$. There are only three nonempty subsets but you're likely to decide that a partial sum could be anywhere between $0$ and $101$, giving a table with two rows and $101$ columns, instead of two rows and three columns.


Recurrence relations and induction: guessing the right bound I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$
This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of $$T(n)=T(n-1)+n$$ and $$T(n)=T(\sqrt{n})+1$$ because they were both easier to solve.
Does it makes sense to guess an upper bound for the original recurrence relation (and try to confirm that guess through induction) based on the complexities I obtained for both for these (i.e. use the one with larger order of growth for example)?
If not then what are some ways to find/guess an upper bound for such a relation?

For sure, $T(\sqrt{n})\leq T(n)$, so $T(n)\leq 2T(n-1)+n$, but this produces an exponential upper bound, which is correct but to big to be useful.
Anyway, in this case if we start from the solution of the recurrence $S(n)=S(n-1)+O(n)$, which is $O(n^2)$, we observe that $S(\sqrt{n})=O(n)$, so also the solution of $T(n)=T(\sqrt{n})+T(n-1)+O(n)$ is in $O(n^2)$.
I have to admit that this approach doesn't seem (also to me) very formal, so I've confirmed that guess by explicit calculation.
Indeed, suppose $T(n)=an^2+bn+c$, then $T(\sqrt{n})+T(n-1)+n=an^2+(1-a)n+b\sqrt{n}+a-b+c$: we have equality if $a=1$, $b=0$ and $c=-1$, so $T(n)=n^2-1$. Clearly, this is not an exact solution as it depends on the starting point, I mean, it is correct only if $T(1)=0$; in general you have to check that $T(n)=O(n^2)$ (actually, $T(n)=\Theta(n)$) by induction.

So, returning to your question: no, you cannot simply split the equation and take the solution with larger order of growth.
E.g., consider the recurrence $T(n)=T(n^{3/4})+T(n-1)+n$: if $S(n)=O(n^2)$, then $S(n^{3/4})=n^{3/2}$ is no more a $O(n)$, so we cannot conclude as before.
But if you have a recurrence of the form $$T(n)=T(f(n))+T(g(n))+O(h(n))$$
(with reasonable assumption of functions $f,g,h$, I mean, positive, monotone, ...)
and the solution of, say, $S(n)=S(g(n))+O(h(n))$ is such that $S(f(n))=O(h(n))$, then you can make the (more than) reasonable assumption that $T(n)=O(S(n))$, and confirm it by induction.


parsing at semantic level due to ambiguities I have a VHDL elaboration engine/simulator. As I understand it, the language syntax allows for ambiguities at syntax level. That is, an assignment

pin_value <= bus(5)

can be interpreted as picking a child of the bus by index. Here the bus is a signal (an object). However, it can also be that paranthis are applied to a type

int_signal <= integer(1.1)

which should be interpreted as type conversion.

I wonder. The elaborator should take the parse tree, instantiate objects and tie them together resolving the names. However, the parser has no idea if the prefix at the parensis is a type or array. So, it treats all parensis as indexed objects.

simple_assignment ::= target <= value_expression { , value_expression }
value_expression ::= name | literal | function_call | type_conversion
name ::= simple_name | indexed_name
indexed_name ::= prefix ( expression { , expression } ) // example: REG_ARRAY(5)
type_conversion ::= type_mark ( expression )

I do not see how can I distinguish between value_expression and type_conversion at syntactic level. My parser parses both as indexed_name and name resolution, when fails to find array object, falls back into type conversion. I am asking if such case analysis it the only way to handle the problem or more strighnforward approach exists that I am missing?

There is no reason to "distinguish between value_expression and
type_conversion" since, according to the grammar a type_conversion is
a value_expression.

You probably mean to distinguish between indexed_name and
type_conversion ... and possibly also function_call, but you do not
give its syntax, so I am not sure.

I do not know VHDL, but it may be that the syntax you have is the
syntax used to explain the language to users, not the syntax actually
used in the parser. The parser could simply use a grammar that does not distinguish between
indexed_name and type_conversion, and leave the distinction for a
later processing stage, when the lexical entities have been identified
and their "nature" is known: array, type or function name.

Alternatively, and more likely, it is possible that symbol tables are built as the
program is parsed, and when an identifier is found by the lexer
(lexical analyser), the lexer will look in the table and will tell the
parser whether it is a type_mark or a prefix (i.e., array identifier) before
the parentheses. Then the parser can proceed with the proper rule for
type_conversion or indexed_name.


Optimization of Thompson Construction of an NFA I would like to ask under which circumstances can these optimizations be used,supposed that they are part of a bigger NFA and when can they lead to an error ??

In general these reductions are OK when there are no other edges incident to the edges you are contracting. Whenever there are other edges there can be unexpected paths.

I do not know of a good characterization when they can be used. If such an improvement would have been obvious, I think Thompson would have included it.


Approximate the order of summation of two vectors Assume we are given two vectors $A,B$ that each contains $c$ numbers: $A=[a_i>0]_{1 \times c}$. We want to see the weighted summation of which one is larger. In other words, given two vectors $A$ and $B$:

$$ws(A) = \sum_{1 \leq i \leq c}{i.a_i}, ~~~~ws(B) = \sum_{1 \leq i \leq c}{i.b_i}$$

we want to know $ws(A)>ws(B)?$

For making the problem simpler, I add another condition to the problem:

$$\sum_{1 \leq i \leq c}{a_i} = \sum_{1 \leq i \leq c}{b_i}$$

Now, is there any way to approximately claim which one of these vectors is larger without running the summation (We may consider the summation of a small number of elements and decide based on that)?

Let's consider the problem of comparing the sums of two vectors $A$ and $B$ that have all their $N$ real values in the range $[0, c]$.

First, let's start with two facts.

Union Bound.
Let $Y_1, \ldots, Y_K$ be K events in a probability space. Then
\begin{equation}
Pr\left(\bigcup_{j=1}^KY_j\right) \leq \sum_{j=1}^K Pr\left(Y_j\right).
\end{equation}
(The inequality is equality for disjoint events $Y_j$.)

Hoeffding Bound (1, 2).
Let $X_1, \ldots, X_R$ be $R$ independent random variables, each taking values in the range $\mathcal{J} = [\alpha, \beta]$. Let $\mu$ denote the mean of their expectations. Then
\begin{equation}
Pr\left(\left|\frac{1}{R}\sum_{i=1}^RX_i - \mu\right|\geq \epsilon\right) \leq e^{-2R\epsilon^2/(\beta-\alpha)^2}
\end{equation}

Idea

The first idea is that we are going to approximate the values of the sums for the two vectors $A$ and $B$ within some precision $\varepsilon$ with high probability (high confidence if you prefer). Then the argument that the two expectations that we have for the actual sums of the vectors $A$ and $B$ are well separated will be a simple application of the Union bound assuming that we have very high confidence for both expectations.

Definitions

Let $S(A), S(B)$ be the actual sum for the vectors $A$ and $B$ respectively and $S^*(A)$ and $S^*(B)$ be the approximations of the two values that we are going to come up with. In particular,
$$\begin{array}{rcl}
S(A) &=& \mu_A\cdot N \\
S(B) &=& \mu_B\cdot N
\end{array}$$
where $\mu_A$ and $\mu_B$ are the true mean values of the entries of the vectors respectively.

We now reduce the problem of approximating the sums to that of approximating the mean values $\mu_A$ and $\mu_B$; let's call the approximations $\mu_A^*$ and $\mu_B^*$.

Well Separated Approximations of Sums.
We will say that the two approximated sums are well separated if the following holds:
\begin{eqnarray}
\left|S^*(A) - S^*(B)\right| &=& \left|\mu_A^*\cdot N - \mu_B^*\cdot N\right| \\
 &=& \left|\mu_A^* - \mu_B^*\right|\cdot N \\
 &\geq& 2\cdot\epsilon\cdot N
\end{eqnarray}
where $\epsilon$ is the accuracy within which we have approximated the means $\mu_A^*$ and $\mu_B^*$.

(The intuition is that the sums are well separated if their respective mean values are well separated.)

Continuation

By the Hoeffding bound, if we require that our estimate is incorrect bounded by some small probability $\delta/2$ (it will be apparent soon why I divide $\delta$ by two), then we need
$$R \geq \left\lceil\frac{(\beta-\alpha)^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil = \left\lceil\frac{c^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil$$
samples (runs) so that we can come up with the real values $\mu_A^*$ and $\mu_B^*$ that approximate the true real values $\mu_A$ and $\mu_B$ respectively within $\epsilon$ with probability at least $1-\frac{\delta}{2}$. In other words, it is only with probability at most $\frac{\delta}{2}$ that we will not have good estimates for each of the $\mu_A^*$ and $\mu_B^*$.

Now, by the Union bound, either of our estimates is incorrect with probability at most $\delta/2 + \delta/2 = \delta$. Or, the other way around, with probability at least $1-\delta$ both of our estimates $\mu_A^*$ and $\mu_B^*$ are within $\epsilon$ of their true values.

Theorem

Drawing $R$ samples from each vector where
$$R \geq \left\lceil\frac{c^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil$$
it is guaranteed that with probability $1-\delta$
both of our estimates for $\mu_A^*$ and $\mu_B^*$ are within $\epsilon$ of their true values, and thus the approximations $S^*(A)$ and $S^*(B)$ that we have for the sums $S(A)$ and $S(B)$ are within $\epsilon\cdot N$ of their true values. Thus, it suffices to check if the inequality
$$\left|S^*(A) - S^*(B)\right| \geq 2\cdot\epsilon\cdot N$$
holds. If the inequality holds, then with probability $1-\delta$ (that's our confidence) the two sums are different and in fact we can say which one is bigger with the same confidence.

Concluding Remark

Just to note that with the approach above we need $\epsilon^{-1} = o\left(\sqrt{N}\right)$ so that the number of samples/runs $R$ is sublinear (btw, sublinear algorithms is an active field of research) and thus it makes sense to take samples from the huge vectors $A$ and $B$ rather than computing the sums directly. This also means that with this approach the separation bound between the two approximated sums should be $\Omega\left(\sqrt{N}\right)$.

References

[1] Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13–30, March 1963

[2] L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.

Code

Below is some code that I wrote yesterday for playing around with the problem. The difference is I think that I did not divide by 2 the $\delta$, and moreover, for the approximations I am expressing $\delta$ as a negative power of $e$ ($\approx 2.71828\ldots$) so that I can simplify the calculations and not take logarithms.
Other than that, I generate two big arrays with slightly skewed entries; the first one with values between 0 and 9 and the other one with values between 1 and 10. In principle this needs a GMP implementation, but I guess the following will do for now. I really enjoyed the problem! Thanks! I am of course very interested in seeing different approaches to the problem.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <ctgmath>

#define SIZE 1000000
#define EPSILON 0.1
#define DELTA_EXPONENT 4

#define MIN_VALUE  0
#define MAX_VALUE 10

/************************************************************************************/

void assignRandomValues (unsigned int * array, const unsigned long int size, const int low, const int high);
unsigned int trueSum (unsigned int * array, const unsigned long int size);
bool areTheApproximationsSufficientlyDifferent (const unsigned long int size, const long double epsilon, const unsigned int difference);
unsigned int approximateSum (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent);
long double approximateMean (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent);

/************************************************************************************/

int main () {
    unsigned int * a1, * a2, s1, s2, s1Approx, s2Approx, difference;
    bool flag;
    time_t timer;

    // Randomize
    timer = time(NULL);

    // Print the basic properties
    std::cout << "Timer seed: " << timer << std::endl;
    std::cout << "Size      : " << SIZE << std::endl;
    std::cout << "Epsilon   : " << EPSILON << std::endl;
    std::cout << "Delta exp : " << DELTA_EXPONENT << std::endl << std::endl;

    // Reserve memory
    a1 = new unsigned int [SIZE];
    a2 = new unsigned int [SIZE];

    // Generate the arrays
    assignRandomValues (a1, SIZE, MIN_VALUE, MIN_VALUE + (MAX_VALUE - MIN_VALUE)/2 + 4);
    assignRandomValues (a2, SIZE, MIN_VALUE + (MAX_VALUE - MIN_VALUE)/2 - 4, MAX_VALUE);

    // Find and print the true values
    s1 = trueSum (a1, SIZE);
    s2 = trueSum (a2, SIZE);
    std::cout << "The true sum value for a1 is: " << s1 << std::endl;
    std::cout << "The true sum value for a2 is: " << s2 << std::endl;

    // Find and print the approximate values
    s1Approx = approximateSum (a1, SIZE, MAX_VALUE, EPSILON, DELTA_EXPONENT);
    s2Approx = approximateSum (a2, SIZE, MAX_VALUE, EPSILON, DELTA_EXPONENT);
    std::cout << "The approximate sum value for a1 is: " << s1Approx << std::endl;
    std::cout << "The approximate sum value for a2 is: " << s2Approx << std::endl;

    // Print the approximate difference and indicate if they are sufficiently separated
    difference = static_cast<unsigned int>(fabs(static_cast<long double>(s1Approx) - static_cast<long double>(s2Approx)));
    std::cout << "The approximated difference is: " << difference << std::endl;
    flag = areTheApproximationsSufficientlyDifferent(SIZE, EPSILON, difference);
    std::cout << "The approximated difference is sufficiently big (w.h.p.): ";
    std::cout << (flag ? "YES" : "NO") << std::endl;

    // Deallocate memory
    delete [] a1;
    delete [] a2;

    return 0;
}

/************************************************************************************/

void assignRandomValues (unsigned int * array, const unsigned long int size, const int low, const int high) {
    unsigned long int i;

    for (i = 0; i < size; i++) {
        array [i] = low + (rand() % (high - low + 1));
    }
}

/************************************************************************************/

unsigned int trueSum (unsigned int * array, const unsigned long int size) {
    unsigned long int i, sum = 0;
    for (i = 0; i < size; i++)
        sum += array[i];
    return sum;
}

/************************************************************************************/

bool areTheApproximationsSufficientlyDifferent (const unsigned long int size, const long double epsilon, const unsigned int difference) {
    unsigned int bound = static_cast<unsigned int>(ceil(2.0*size*epsilon));
    if (difference > bound)
        return true;
    return false;
}

/************************************************************************************/

unsigned int approximateSum (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent) {
    long double mean = approximateMean (array, size, maxValue, epsilon, deltaExponent);
    return static_cast<unsigned int>(round(mean * size));
}

long double approximateMean (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent) {
    unsigned long int samples, i, sum, pos, integerPart;
    long double floatingPart, mean;

    samples = static_cast<unsigned long int>(ceil(maxValue * maxValue * deltaExponent / (static_cast<long double>(2.0) * epsilon * epsilon)));

    std::cout << "Requiring " << samples << " samples for the approximation." << std::endl;

    sum = 0;
    for (i = 0; i < samples; i++) {
        pos = rand () % size;
        sum += array[pos];
    }

    integerPart  = sum / samples;
    floatingPart = static_cast<long double>((sum - integerPart * samples)) / static_cast<long double>(samples);
    mean = static_cast<long double>(integerPart) + floatingPart;
    return mean;
}

/************************************************************************************/

Wrapping Up for the Original Question

In the original question we want to approximate values of the form $i\cdot a_i$ or $i\cdot b_i$ and this means that these new values are now in the range $[0, c\cdot N]$ assuming that $a_i, b_i \in [0, c]$ for $i\in{0, 1,\ldots, N}$.

Above, I assumed that $c \ll N$. However, since the number of samples that is required has quadratic dependence on the maximum value that can be found in these new vectors, we really need to draw $R \geq \Omega\left(\frac{c^2\cdot N^2}{\epsilon^2}\ln\left(\frac{1}{\delta}\right)\right)$ samples. On the other hand, a direct summation will perform $O(N)$ additions of $O(N)$ multiplications. Thus, sampling would make sense in terms of savings if we could say that $R=o\left(N\right)$. In other words, ignoring the logarithmic dependence on $\delta$, we want
$$\frac{c^2\cdot N^2}{\epsilon^2} = o(N)\;.$$
This would be true if
$$\epsilon = \omega(c\cdot N^{1/2})$$
thus yielding $R=o\left(N\right)$.

The question is if this $\epsilon$ is meaningful for comparisons. The answer is yes when the two vectors are significantly different (contrary to the helper that original vectors have values that add up to the same number). Let's see what I mean by an example.

Example

Let $c=N$. Moreover, let
$$
\begin{array}{rcl}
A &=& \left\langle 1, 1, \ldots, 1, \ldots, 1\right\rangle \\
B &=& \left\langle 1, 2, \ldots, i, \ldots, N\right\rangle
\end{array}
$$
be two vectors with $N$ elements. Then, the requested summation of the products $i\cdot a_i$ and $i\cdot b_i$ can be seen as the summation on the vectors
$$
\begin{array}{rcl}
F &=& \left\langle 1, 2, \ldots, i, \ldots, N\right\rangle \\
G &=& \left\langle 1^2, 2^2, \ldots, i^2, \ldots, N^2\right\rangle
\end{array}
$$
Note that $S(F) = \sum_{i=1}^N f_i = \Theta\left(N^2\right)$ and $S(G) = \sum_{i=1}^N g_i = \Theta\left(N^3\right)$. Similarly, their mean values are significantly different, since $\mu_{F} = \Theta\left(N\right)$ while $\mu_G = \Theta\left(N^2\right)$

The accuracy $\epsilon$ that we are talking about involves the estimate of these last true mean values $\mu_F$ and $\mu_G$. Thus, if we set
$$\epsilon = \Theta\left(c\cdot N^{1/2+\xi}\right) = \Theta\left(N^{3/2+\xi}\right)$$
for some $\xi\in(0,1/2)$ there will be cases (like in this example) where the mean values will be significantly far away on the real line and thus we will be able to tell which one is bigger than the other with few samples (and as a consequence we will be able to separate the two sums on the real line with that many samples).

Concluding the Wrap-Up

Now if we revisit our definition for well-separated sums, we are going to require the following inequality for our definition:
$$\left|S^*(F)-S^*(G)\right| \geq 2\cdot N^{5/2+\xi}$$
for some $\xi\in\left(0, 1/2\right)$. Actually any $\xi\in\left(0,1/2\right)$ will do. The larger the $\xi$ the fewer samples that we draw. However, the catch is that the larger the $\xi$, the more restrictive our inequality is for separating the two sums. In other words, the closer $\xi$ is to $1/2$ the more unlikely it is to encounter vectors that can be separated using our method, since we require the gap between their true values to be even larger.

I believe the above clears up everything, but in case it does not, just drop me a line and I will try to explain more the details.


How to prove that the pre-order tree traversal algorithm terminates? I see structural induction the usual way for proving an algorithm's termination property, but it's not that easy to prove by means of induction on a tree algorithm. Now I am struggling on proving that the pre-order tree traversal algorithm is terminable:

preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left)
  preorder(node.right)

How should I prove?

Hint (by Raphael):  How do you prove that the recursive factorial function terminates?

Answer (by Kejia): The recursive factorial function's universe is non-negative integers, which is countable and so well-found, and so it is very easy to prove with mathematical induction.

By analogy, we can find a mapping from trees to a well-founded universe so that a similar proof works.

   Our mapping is to the size of the subtree.
 At each recursive call, the size of a subproblem (i.e. a subtree) is strictly decreasing and always non-negative. Therefore, we can proceed by induction.

 Suppose (induction hypothesis) that the function on a tree of size of at most k terminates. Now consider an input tree with k+1 nodes...


Approximability of convex programming (convex optimization) Convex optimization is defined here: https://cstheory.stackexchange.com/questions/22314/definition-of-convex-optimization-problem-by-stephen-boyd-and-lieven-vandenbergh

The problem is NP-hard: https://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti

But is anything known about the approximation complexity of the problem?  Does it have a PTAS (poly time approximation scheme)?  Or is there a proof that a PTAS is impossible unless P=NP?  Are there any known results on upper/lower bounds on its approximability?

Any information will be much appreciated.

You haven't defined convex optimization in general, and indeed it is not clear how one would encode a general convex optimization problem. However, to answer your question it suffices to consider the special case of copositive programming. It is known that Independent Set can be expressed as a copositive program, and this problem is NP-hard to approximate up to a factor of $n^{1-\epsilon}$ for every $\epsilon > 0$. In particular, there is no PTAS.


Turing Machine remembering copied symbols So, I know that any multiple-tape TM can be in theory turned into a one-tape TM. However, it is too easy to copy, let's say, binary numbers from one tape to another. That's why I thought about putting a separator between the two copies and then taking symbols one after the other and writing them after the separator until the separator itself is encountered. The problem, however, is that I am not sure how it could remember places where it has already been/copied the characters. Example:

First we have:

##1011##

Then we put the separator '&' at the end

##1011&##

Read back to beginning and change the state accordingly so that it will write $1$ or $0$ after the separator. So far, so good, then we read back again, and now:

How could we know that we have already copied the first $1$ and must now copy the $0$ without putting any restriction on the input length (in regards to the number of states)? In other words, how could we remember the last copied symbol?

I have thought of putting an extra parameter - just a integer ≤ length (something like $\delta (z_1,1,L,1)$ where the last one would be the number of already written-out symbols). This would be easy to understand, but would be nowhere near the definition of Turing machine. So, any useful ideas?

Thanks.

Once you've hit the '&' separator, move left until you see the '#', then move one cell to the right and replace the '1' with an 'x' (and change to state $p$ to "remember" you've seen a 1) or a '0' with a 'y' (changing to state $q$ to "remember" you've seen a 0). Now move right until you pass the '&' separator and see a '#'. Replace that with a '1' if you were in state $q$ or with a '0' if you were in state $p$. Now move to the left until you see a 'x' or a 'y', move one cell to the right and repeat what you've done before. Continue the process until everything on the left is a string of 'x's and 'y's, then make one more pass, restoring the values to their originals.


Changing probabilities to 0/1 in definition of class IP A language $L$ belongs to $\mathbf{IP}$ if there exists $V,P$ such that for all $Q$, $w$,
$$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
$$w\notin L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\leq1/3$$

I am trying to understand the claim that changing the $1/3$ to $0$ for the $w \notin L$ case is equivalent to having a deterministic verifier, thus reducing the class to $\mathbf{NP}$. Is this because, in this case, we could rig all of the $V$'s interactions with $P$ so that whenever $Pr[V\leftrightarrow P\text{ accepts }w]>0$, it now determinstically accepts?

If this is correct, then why can't we do a similar thing for the hypothetical situation where the $2/3$ is replaced by a $1$ (apparently doing this does not change $\mathbf{IP}$)? My intuition is that we can't make a similar modification because it would require modifying $V$'s behaviour for all $Q$. But my thoughts are bit fuzzy here...

Can someone please help clarify?

Suppose you have a (randomized) verifier $V$ such that, for all $Q,w$,

$$\begin{align*}
w\in L &\implies \Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3\\
w\notin L &\implies \Pr[V\leftrightarrow Q\text{ accepts }w]= 0.
\end{align*}$$

Since $P$ is one possible value of $Q$, it follows that

$$w\notin L \implies \Pr[V\leftrightarrow P\text{ accepts }w]= 0.$$

This means that for all $w \notin L$, there is no choice of random bits such that $V\leftrightarrow P$ accepts $w$, while for all $w \in L$, there is a choice of random bits such that $V\leftrightarrow P$ accepts $w$.

This gives you a certificate for the claim that $w \in L$: namely, the random bits used during some accepting execution of $V \leftrightarrow P$ on $w$.  By the above arguments, if $w \in L$, such a certificate is guaranteed to exist, whereas if $w \notin L$, no such certificate exists.  $V \leftrightarrow P$ can be used as a verifier to check the certificate.  Since $V \leftrightarrow P$ runs in polynomial time, we have a polynomial-sized certificate and a polynomial-time verifier for $L$, so it follows that $L$ is in NP.

This also helps answer your second question.  If you change the $2/3$ to $1$ but don't change the $1/3$ to $0$, the above argument doesn't go through: you can't conclude that there is no certificate for $w \notin L$, so you no longer have a certificate and verifier for $L$.


Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks? Python quite famously uses indentation to syntactically define blocks of code. (See Compound statements in the Python Language Reference). After years of using Python I'm still intrigued by and very fond of this syntax feature.

But I wonder: Apart from Python and its "predecessor"(*) language ABC which other programming languages are out there using indentation for definition of code blocks? Code blocks means here "multiple statements which in some way are treated as one component".

I'm particularly interested in practical programming languages, but esoteric languages might be worth mentioning as well.

(*): "Predecessor" is my choice of word in default of knowing here a better one. Guido van Rossum, the creator of Python, described the relationship between Python and ABC regarding indentation in an interview like this: "The choice of indentation for grouping was not a novel concept in Python; I inherited this from ABC."

Wikipedia has an extensive list of languages that use the off-side rule1:

  ABC
  Boo
  BuddyScript
  Cobra
  CoffeeScript
  Converge
  Curry
  Elixir (, do: blocks)
  Elm
  F# (if #light "off" is not specified)
  Genie
  Haskell (only for where, let, do, or case ... of clauses when braces are omitted)
  Inform 7
  ISWIM, the abstract language that introduced the rule
  LiveScript
  Miranda
  Nemerle
  Nim
  occam
  PROMAL
  Python
  Scheme, when using e.g. SRFI 119
  Spin
  XL

1: I've never heard this term before myself.


Why is NP in EXPTIME? Is there an easy way to see why NP is in EXPTIME?  It seems to me a priori conceivable that there could be a problem which requires super-exponential time to solve, but whose solution could be verified in polynomial time.

Any problem in NP is in EXPTIME because you can either use exponential time to try all possible certificates or to enumerate all possible computation paths of a nondeterministic machine.

More formally, there are two main definitions of NP.  One is that a language $L$ is in NP iff there is a relation $R$ such that

there is a polynomial $p$ such that, for all $(x,y)\in R$, $|y|\leq p(|x|)$,
given the string $x\#y$, we can determine in time polynomial in $|x\#y|$ whether $(x,y)\in R$, and
$L = \{x\mid (x,y)\in R\}$.

So, if we have exponential time and we want to know if $x\in L$, we can just try all $|\Sigma|^{p(n)}$ possible values for~$y$ and see if $(x,y)\in R$ for any of those.  That takes time $2^{O(p(n))}$, so $L\in\,$EXPTIME.

Alternatively, we can define NP as the set of languages decided by polynomial time nondeterministic Turing machines.  In this case, suppose that $L$ is decided by machine $M$ in time $p(n)$ for some polynomial $p$, for inputs of length $n$.  Then $M$ makes at most $p(|x|)$ nondeterministic choices while determining if $x\in L$. By examining $M$'s transition function, we can find a constant $k$ such that $M$ has at most $k$ nondeterministic choices at each step of the computation (independent of the input), so it has at most $k^{p(|x|)} = 2^{O(p(|x|))}$ different sequences of nondeterministic choices while reading input $x$.  Given exponential time, we can simulate each of these possibilities one after another and see if any of them accepts.


Cook completeness of a variant of Vertex Cover Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$?

Input: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$

Output: YES if there exists a vertex cover $C'\subseteq V$ such that $|C'|=|C|-1$, NO otherwise

First it is obvious that the above problem is in NP.
I think there is even a Karp reduction from the well-known clique problem. It uses the well-known reductions from clique problem to independent set problem and from  independent set problem to vertex cover problem.

The clique problem is as follows:

Given: a graph $G$ of size $n$, parameter $k$

Output: Yes iff there is a clique in $G$ of size $k$.

Now, first we add a clique  of size $k-1$ in $G$. For sake of presentation, we denot the resulted graph by $G'$. Then, we create the corresponding complement of $G'$, denoted by  $\hat{G}$. Denote $\hat{G}=(\hat{V},\hat{E})$ and let $V_{clique} \subseteq \hat{V}$ be the set of vertices corresponding to the original clique of size $k-1$ in $G$. The reduction is a polynomial transformation. Note that $|\hat{V}|=n+k-1$

The graph $G$ contains a clique of size $k$ if and only if $G'$ contains a clique of size $k$, since adding a clique  of size $k-1$ does not effects if $G$ has a clique of a larger size. Using the same arguments done in reduction from clique problem to the independent set problem and from independent set problem to vertex cover problem,  we derive that    $G$ contains a clique of size $k$ if and only $\hat{G}$ contains a vertex cover of size $|\hat{V}|-k=n-1$.

Using similar arguments, we derive that $V_{clique}$ is an independent set in $\hat{G}$, and thus  the set $\hat{V}\setminus  V_{clique}$ is a vertex cover in $\hat{G}$ of size $|\hat{V}|-(k-1)=n$.

Finally, let $L_{clique}$ and $L_{vertex}$ be the corresponding languages of the clique and the described vertex cover problems. Then, $(G,k) \in L_{clique}$ iff $(\hat{G},\hat{V}\setminus  V_{clique}) \in L_{vertex}$ (i.e., there exists a clique of size $k$ in $G$ iff there is a vertex cover of size $|\hat{V}\setminus  V_{clique}|=n-1$ in $\hat{G}$).


What does it mean by "not recursively enumerable"? I came across following therem:

  There exists a recursively enumerable language whose complement is not recursively enumerable.

Now, I know following definitions:

  Recognizable language is one which have one-to-one correspondence with the natural number with the additional property that we could specify an algorithm to enumerate the language elements.
  Given the string not in the co-recognizable language, we can give Turing machine which can eventually confirm that the string indeed does not belong to the language.

Then what does the above theorem mean?:

$L'$ does not have one-to-one correspondence with the natural numbers?
We cannot give an algorithm to enumerate the $L'$s elements?
$L'$ is co-recognizable.

I'm using r.e. to mean "recursively enumerable" and co-r.e. to mean "the complement is recursively enumerable". I'm assuming by $L'$, you mean the complement of $L$.

To answer your questions directly:

This is not correct. Every language over a finite alphabet $\Sigma$ has a one-to-one correspondence to the natural numbers. To show this, you would have to construct a one-to-one function that maps the words of your language to natural numbers. This isn't difficult at all, but a bit technical, so I'm only going to sketch the construction: Pick some well-founded total order $\leq$ on $\Sigma^*$, for example the lexicographic order. For $w \in L$, define $$predecessors(w) := \{ v \in L \mid v \lneq w\}$$ to be the set of words in $L$ preceding $w$ according to your order. Define a mapping $f: L \to \mathbb N$, by $f(w) := |precedessors(w)|$, assigning to each word the number of its predecessors. You could then show that $f$ is in fact a one-to-one mapping. This construction works for any language, though it is not necessarily computable for all languages.
Correct, when $L$ is not co-r.e., by definition $L'$ is not r.e., so there cannot be an algorithm that enumerates $L'$.
Correct, your theorem says $L$ is r.e., therefore $L'$ is co-r.e. Note this follows from the first premise of your theorem, not from the latter premise. In general, $L'$ being not r.e. on its own does not imply $L'$ being co-r.e. In other words, there are languages that are neither r.e. nor co-r.e., see here.

To elaborate a bit more on what the theorem means: It says there is a language $L$ that is r.e. but not co-r.e.

The important insight is that if a language $L$ is r.e. and co-r.e., then it is decidable. Assume you have a TM $M$ for enumerating $L$ and a TM $M'$ for enumerating its complement $L'$. Then you can build a new TM $M^\star$ for deciding $L$: For a given input $w$, $M^\star$ simulates $M$ and $M'$ in parallel. Since either $w \in L$ or $w \notin L$, one of $M$ or $M'$ has to enumerate $w$ eventually. At this point, $M^\star$ stops the simulation and accepts or rejects $w$ based on which of $M$ and $M'$ enumerated it. It follows that $M^\star$ halts on all inputs and accepts $w$ iff $w \in L$. Therefore, $L$ is decidable.

Based on this insight, if you can find a language $L$ that is r.e. and undecidable, you can then conclude that it cannot be co-r.e. Since if it would be co-r.e. it could not be undecidable.

The usual example would be some variant of the halting problem, e.g. $H = \{ \langle M,w\rangle \mid M$ is a Turing Machine that halts on input $w\}$. You should know that $H$ is undecidable. To show that $H$ is r.e., you would have to construct a TM that enumerates $H$. I'm only going to sketch the proof: Your TM $M^*$ would iterate over triples of the form $\langle M, w, n \rangle$ for a TM $M$, $w \in \Sigma^*$ and $n \in \mathbb N$ in some fixed order (e.g. lexicographic order). When looking at such a triple, $M^*$ would simulate $M$ on $w$ for at most $n$ steps. If $M$ halts on $w$ within these $n$ steps, $M^*$ prints $\langle M, w \rangle$. It's not difficult to see that $M^*$ will eventually print every pair $\langle M,w \rangle$ for which $M$ halts on $w$, as for every such pair, there is some $n \in \mathbb N$, such that $M$ halts on $w$ within $n$ steps. Therefore, $M^*$ enumerates $H$, thus $H^\star$ is r.e.

Based on knowing that $H$ is r.e. and undecidable, you can conclude that $H$ cannot be co-.r.e. which proofs your theorem.


Towers of Hanoi First Move I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below.

However one thing still bugs me - I can't yet work out how this simple seeming algorithm can "know" which move to make first - whether to the destination peg or the spare peg.

I can see it depends on whether there is an odd or even number of discs, and I understand how the algorithm works, thanks to this great article: https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

It's just that first move that remains a mystery to me. Any clarification musch appreciated.

def hanoi(n, from_peg, to_peg, spare_peg):
    if n == 1:
        print("Moving disc from " + from_peg + " to " + to_peg)
        return
    hanoi(n-1, from_peg, spare_peg, to_peg)
    print("Moving disc from " + from_peg + " to " + to_peg)
    hanoi(n-1, spare_peg, to_peg, from_peg),

print (hanoi(4, 'A', 'C', 'B'))

If you trace the recursion calls that your algorithm makes before it prints its first line, you will have if the first call is  hanoi(n, 'A', 'B', 'C') :

hanoi(n, 'A', 'B', 'C')
hanoi(n-1, 'A', 'C', 'B')
hanoi(n-2, 'A', 'B', 'C')
...
hanoi(1, 'A', $ , €)
Moving disc from A to $

To see if $ is equal to B or C, you just have to remark that the value of to_peg and spare_peg alternate each time so the disk to move only depends on the parity of n. In our example :

If n is odd then \$ = B and otherwise, \$ = C


Recommendations for a good (rigorous) text to study Computational Complexity. I look for a good text to learn basics of computational complexity.

I've read some parts of the first two chapters of "Computational Complexity: A Modern Approach" by Boaz Barak and Sanjeev Arora, it's readable and gives the big picture but I find it  not to be rigorious enough for me. I'm a mathematics student so I want a more rigorous treatment of the subject. So, the text I look for should:-

1- Define Turing machines formally and prove the basic results in a formal way not using  handy-waving arguments. For example, Boaz treatment of Turing machines is not rigorous and so I'd love to see more precise treatment of that.

2- Give proofs that are rigorous enough like those I read in mathematics texts and are not just "overviews".

What are your recommendations? What is the texts that satisfies my needs as close as possible?

Following are my recommendations:

Introduction to Theory of Computation by Michael Sipser. It is an introductory book. Although proofs are complete and not hand waving, but not much maths is needed as a pre requisite. Although Turing machines are covered nicely.
Complexity and cryptography by Talbolt and Welsh. In this book little math background is required. Turing machines is not covered in much details. But the book gives proofs for almost all theorem's it introduces.
From my experience ( as I am a beginner myself ) Sanjeev Arora and Boaz Barak is the most concise with covering advanced topics like quantum computation etc. Although I think you should have a back ground in probability, number theory to read the part I of the book intended to be for undergraduates, as the book leaves some proofs upto the readers. Again for number theory the book I find readable as ( as there is no pre requisite ) :
Number theory by Willian Stein.


Finding the Best Fitting Plane Given a Set of 3D Points Suppose that we have $n$ points in 3D.

I want to find a plane $ax + by + cz + d$ such that sum of all the orthogonal distances to the plane is minimum.

I read this article. However, I need an algorithmic solution.

So far, this answer from SO was the simplest one. However, this solution projects the points onto $z=0$ plane all the time.

Could you help me to write the algorithm? I'll code it in Java.

This is exactly the problem that PCA (principal component analysis) solves.  So, use PCA -- that provides an algorithmic solution to this problem.  See this explanation over at Statistics.SE for an explanation of why PCA solves this problem.

[Least squares fitting is almost a solution to this problem, except that it doesn't minimize the orthogonal distance -- it minimizes the distance along the $y$ axis, or any single axis you might pick.]

If for some reason you didn't want to use PCA, you could frame this as a mathematical optimization problem (the objective function is the total orthogonal distance) and then use any standard optimization technique -- e.g., gradient descent -- to find an approximate optimum.


Is a Petri net without places well-defined? I'm a bit confused about the definition of a Petri-Net. From Wikipedia (EN) I have this defintion:

A Petri-Net is a 5-Tupel (P, T, F, W, s)
P and T are disjoint finite sets of places and transitions, respectively.

So the defintion says: $P \cap T = \emptyset $ &  $P \cup T \neq \emptyset $
Let's say T is $ \emptyset $ and P = { p } so both prerequisites are given. I think that is okay. We have a system which stays allways in one state and can not change to another so we do not need any other state or transition.
Now think about the other case: T = { t } and P is $ \emptyset $. Now we have a system which does not have a state. The transition can't do anything because we do not have any states and it does not have any meaningful meaning in this case.
So does any Petri-Net which has minimum one transition need two places? Or have I missed out something?

A net without place does have "state", or a marking in proper terminilogy; as that is a mapping from the set of places into $\Bbb N$, technically this does exist even when the set of places is empty (as a kind of empty relation).

A net with one place and one transition can even change state. If the transition has an outgoing arrow to the place, the transition can add tokens into the place. (Tokens can be created, they aren't physically moved from one place to another.) Effectively the behaviour will be that of a upward counter.


A question on instruction executing speed I am new to computer science, so excuse me if the question is inappropriate or sounds absurd to you.
In the textbook, it says that a typical laptop can execute 1 billion instructions per second. Therefore, I thought that if I wrote a never-ending piece of algorithm, it would generate tons lines in the program counsel after running it for 10 seconds. Taking into account the time it needs to convert to machine instructions, and the fact that other programs needed to be executed as well, the number I expected was some where about one million of instructions per second and thus 10 millions per 10 second.
I tried to run something like this:
        While 1+1=2:
               Print(0)

To my surprise, I found that the print instruction had been executed for less than 4,000 times within 10 seconds. I know that my original estimation was not meant to be accurate but I was not expecting the speed to be this slow. I think maybe the read-writing speed of my ssd was the major drawback. I know that sending instruction to the screen is even slower, but that should not affect the CPU's performance.
So, here are my questions:

What are the major factors that slow down the speed?

Are there any other factors that I overlook?

Is there a way to know exactly or make reasonably accurate estimation of the Python code execution rate?

And are there any suggestions to speed up the execution rate?

Even if it takes time to send instructions to the monitor, the processor can still utilize the gap in between to execute other instructions. So, does that exclude slow I/O speed as a drawback?

If the hidden layer between me and the machine already figures out what to do in the beginning, is it going to repeat the same instruction without executing extra instructions?

It is possible to have the processor focus on a piece program without executing any other program at all?

Thank you for your help in advance.

There are a number of reasons for this.

Other processes were probably running at the same time.
Printing to the console takes many, many instructions per print, especially when the console starts to scroll.
You may have been using an interpreted language. In this case, the computer must  figure out what each line of your program means before running it. Some interpreters figure this out again every time they come to a line, even if they've run it before. Again, this takes many, many instructions per line.


Does co-inductive and co-recursive types also have their recursors? I'm new to type theory, and recently read introductory materials where dependent type are discussed. One of my friend asked me, "Those dependent types are having recursors & 'inductors'(dependent eliminators), but how about those types that is co-inductive/co-recursive?"

Some related example is much appreciated.

To understand coinduction, it helps to understand the categorical presentation of induction (since, as far as I know, coinduction comes from dualizing it there).

The idea behind induction is that we have a functor $F : C → C$, and we consider algebras $(A,\ α : F A → A)$. The operation $α$ specifies how to interpret the structure given by $F$ into $A$. Then, an inductively defined type is an initial algebra $(μF, \mathsf{in} : F μF → μF)$, which mean there is a unique homomorphism $\mathsf{fold}_A : μF → A$ to any other algebra. This homomorphism is the recursor, and the uniqueness allows us to define the induction principle in various ways, depending on the setting.

Coinduction flips most of these arrows around. Instead of algebras, we have coalgebras, $(A, α : A → F A)$. And instead of being initial, the coinductively defined type is final, so we get a unique $unfold_A : A → νF$ from any other coalgebra. So, instead of a recursive way of "eliminating", we get a recursive way of "introducing," and the eliminators are non-recursive.

However this flipping around makes some thing not work quite as nicely with coinductive types. I have an Agda development here that tries to explain the stuff about induction above in more detail, with the idea of finding something similar for coinduction. But I never got around to figuring that part out. And as far as I know, there is no known 'nice' interpretation of the coinductive case similar to the inductive one. The one thing to note is that 'just do the same thing with slices as induction' turns out to be uninteresting for coinduction.

One promising thing I have seen is that in cubical type theory, definition by coinduction gives a natural way of showing that two values of a coinductive type are equal, because it automatically corresponds to bisimulation, which is the usual notion of equality for coinductive things. The idea is that an identity from $x : A$ to $y : A$ is a function $eq : \mathbb{I} \to A$ (where $\mathbb{I}$ is an 'interval' type with distinguished values $0$ and $1$) such that $eq\; 0$ evaluates to $x$ and $eq \; 1$ evaluates to $y$. Then $unfold_\mathbb{I}$ gives us a principle for proving $x = y : νF$ by breaking things down to individual pieces like $\mathsf{step} : \mathbb{I} \to F\ \mathbb{I}$. You can see an example of this here.

I don't know if that completely answers your question or not. Hopefully it helps some.


Chernoff-like Concentration Bounds on Permutations Suppose I have $n$ balls. Among them, there are $m \leq n$ black balls and the other $n - m$ balls are white. Fix a random permutation $\pi$ over these balls and denote by $Y_i$ the number of black balls in the first $i$ positions of our permutation $\pi$. I would like to show that $Y_i$ is sharply concentrated around its mean.

The expected value

It is not hard to compute the expected value of $Y_i$: the probability that a black ball appears somewhere along the first $i$ positions is $i/n$; moreover, there are $m$ black balls, hence $$\mathbb{E}[Y_i] = \frac{m\cdot i}{n}.$$

But can we show that $Y_i$ is actually very close to its mean?

A failed attempt

For every black ball $b$, one can define an indicator variable $X_b$ which equals 1 if $b$ appears in the first $i$ positions of $\pi$ and 0 otherwise. Denoting the set of all black balls by $B$, we have

$$ Y_i = \sum_{b \in B} X_b.$$

I was hoping to be able to use a Chernoff bound type of a concentration bound, but unfortunately for two black balls $b$ and $b'$, $X_b$ and $X_{b'}$ are not completely independent. If $X_b = 1$, then there are only $i-1$ spots left for $b'$ to appear in the first $i$ locations and hence the probability of $X_{b'}$ being 1 gets smaller.

Chernoff's bound applies to negatively correlated random variables, such as your hypergeometric distribution. You can find a full treatment in Dubhashi and Panconesi's very useful monograph Concentration of measure for the analysis of algorithms, as well as in many lecture notes, such as this one by Hariharan Ramesh.


"State of the art" algorithms deciding entailment of propositional formulas? I fail to find much about how to efficiently calculate whether a propositional formula entails another.
Considering the following two points...

We can check, for each truth assignment which makes the first formula true, whether it also makes the second true. If all of them do, the first entails the second. It works for disjunctive normal forms, conjunctive normal forms, ... anything really. But this can be prohibitively expensive for large numbers of propositions.
If we translate both formulas to disjunctive normal form we can more efficiently check for entailment, but we need to do the transformation to DNF first.

... what are the best algorithms to check entailment?
I was under the impression that this must be a problem that's long been solved, but where are the papers that deal with entailment of arbitrary propositional formulas? How do I calculate a yes/no answer without using DNFs?

Checking whether $P \Rightarrow Q$ is the same as checking that $P \land \lnot Q$ is unsatisfiable. Using the Tseytin transformation, you can convert $P \land \lnot Q$ into a form suitable for a SAT solver.
Conversely, satisfiability is a special case of your problem, since $P \Rightarrow \bot$ iff $P$ is unsatisfiable.


All pair shortest path in a tripartite graph I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination vertex. Also, all vertices in the source set are connected to all vertices in the bridge set, and all the vertices in destination set are connected to all the vertices in the bridge set.

Let $n$ be the cardinality of both the source and the destination set, and $m$ be the cardinality of the bridge set.

A naive algorithm can compute these in $\mathcal{O}(n^{2}m)$ comparisons.
On the other hand, since we are computing $n^{2}$ quantities, so the complexity will be at least $\mathcal{O}(n^{2})$.

My guess is that it can be done in $\mathcal{O}(n^{2}\log m)$ using priority-queue.
So question is, whether my guess is correct and if not, then what is the complexity of solving this problem?

Edit:

Note that shortest path between a vertex in the source set to any vertex in the bridge set is the direct link, and same holds for the shortest path between the bridge and destination set.

Your problem is essentially $(\min,+)$ matrix multiplication, also known as tropical matrix multiplication. This is because you're computing
$$
C_{ik} = \min_j (A_{ij} + B_{jk}),
$$
which is the same formula as usual matrix multiplication, with $\min$ replacing sum and $+$ replacing product.

Usual fast matrix multiplication algorithms cannot be used for this task. Furthermore, the APSP hypothesis in fine-grained complexity states that there is no $O(n^{3-\epsilon})$ algorithm for APSP. Since APSP reduces to logarithmically many tropical matrix multiplications, this implies that the latter also has no $O(n^{3-\epsilon})$ algorithms.

On the other hand, some $n^{o(1)}$ factors can be shaved, so for example a paper of Ryan Williams, Faster all-pairs shortest paths via circuit complexity.


Regular expression of a language over {a,b,c} which does not contain substring bbb I'm trying to figure out how to build a regular expression for a language that doesn't contain substring bbb. The alphabet is {a,b,c}. I'm trying to construct a DFA and convert to help me get the Regular Expression but still stuck as I found the DFA a bit complicated. I appreciate any help. Thanks!!!

Ok, here is the Regular Expression I've worked on to help me solve the above question.
ac[(acb)* U (acbb)]ac*

Test:
aaaa ccccc acbacbacb aaaaaaa ccccc (OK)
aa acbb acbb acbb acbb cccccccc (OK)

But how about cab or cabb?
I then modified the above expression to:
ac[(acb)* U (acbb)* U (cab)* U (cabb)]ac*

I'm I heading to the right direction?

Thanks again!

The following regular expression (where $\cdot$ stands for $a|b|c$) will match all strings with lengths divisible by 3 not containing the string $bbb$ and not starting with a b.

$((a|c)\cdot\cdot)^*$

Can you modify this to get the expression you want?


Determining the existence of a forced win vs determining the best outcome A large body of work looks at the computational complexity of games. In particular, identifying a forced win from a given position.

Is this problem equivalent under polynomial-time reduction to identifying the best forced outcome of a game, where that outcome might not be a win?

If necessary, assume that it’s a two player zero-sum game that pays out 1 for a win, 0 for a draw, and -1 for a loss.

They are equivalent under Turing reductions, assuming that the game has finite/polynomial-size branching factor (i.e., only that many moves are possible from each position).  I don't know if they are equivalent under Karp reductions.

Consider a position $P$.  Assume there are $k$ moves that are legal there.  Let $P_1,\dots,P_k$ denote the possible positions after making a single move.

Check whether $P$ is a forced win for player #1.  If yes, you are done.

Check whether any of $P_1,\dots,P_k$ is a forced win for player #2.  If they are all a forced win for player #2, then $P$ is a forced lose for player #1.

Otherwise, $P$ is a forced draw for player #1.


Is there a different resolution of the "dangling else" problem other than "match closest"? The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for else and $c$ stands for some other kind of instruction or block):
$$
\begin{aligned}
S &\rightarrow aSbS \;|\; aS \;|\; c\\
\end{aligned}
$$
For example, $aacbc$ can be parsed as $(a(acbc))$ or as $(a(ac)bc)$ (this is the simplest/shortest ambiguous word for this grammar).

The "standard" way to resolve this "dangling else" ambiguity forces the "else" ($b$) statement to pair with the closest/innermost "if-then" ($a$).  This can be accomplished as follows:
$$
\begin{aligned}
S &\rightarrow aTbS \;|\; aS \;|\; c\\
T &\rightarrow aTbT \;|\; c\\
\end{aligned}
$$
This grammar is unambiguous.  In the above example, it forces the $(a(acbc))$ parsing.

Question: Is there another natural way to resolve the ambiguity that would force the $(a(ac)bc)$ parsing of $aacbc$?  In other words, I am looking for a grammar that generates the same language as the two above, that is unambiguous, and that parses $aacbc$ as $(a(ac)bc)$.

Remark: My first attempt was as follows:
$$
\begin{aligned}
S &\rightarrow aSbS \;|\; aU \;|\; c\\
U &\rightarrow aU \;|\; c\\
\end{aligned}
$$
which resolves the ambiguity of $aacbc$ as required — but this grammar is still ambiguous: $aacbacbc$ can be parsed as $(a(ac)b(acbc))$ or as $(a(acb(ac))bc)$.

This problem is an exact analogue of the problem of matching parentheses in an expression in which some of the close parentheses have been omitted. Here an "if" (or $a$ in the representative grammar) is an open parenthesis and an "else" ($b$) is a close parenthesis. (From the sequence of $a$s and $b$s you can mechanically insert $c$s by placing one before each $b$ and one at the very end.) Because it fits better with my parenthetic brain, I write as though that were the problem at hand.

The traditional "match closest" dangling-else resolution matches each close with the most recent as-yet-unmatched open. That means that there is never an unmatched open (or close, for that matter) between a matched open and its matching close.

One possible alternative would be to match each close with the earliest feasible unmatched open. "Feasible" here means that the open could be matched without violating parenthetic nesting (eg. the first $($ in $()()$ cannot feasibly match the last $)$).

This matching has to be done outside-in, so that a match for a close is not attempted until all the enclosing pairs have been matched. This fact makes it impossible to produce a parse with a bounded-lookahead algorithm, since the parse has to work inwards from both ends, after having split the string into completely matched segments (because those effectively limit the range of potential matches).

However, the fact that an online left-to-right parser doesn't exist does not imply that there is no unambiguous CFG. (Evidently: a palindromic language must be parsed from both ends towards the middle, but it's easy to write an unambiguous grammar).

To produce a grammar for the "furthest-match" parenthesis problem, I relied on the fact that an unmatched open cannot be followed by a matched open. If it were, then the furthest-match property wouldn't apply because the unmatched open could have matched the matched open's close, so the fact that it is unmatched violates the furthest-match property.

So here's the slightly clunky grammar:

$$
\begin{aligned}
S&\to U \;|\; M \\
U&\to T \;|\; a U b T \;|\; a U b c \;|\; a M b U \\
M&\to a M b M \;|\; c \\
T&\to a T \;|\; a c \\
\end{aligned}
$$

$S$ is the start symbol; $M$ are fully-matched statements; $U$ are definitely unmatched statements (which means they include at least one unmatched $a$, so they can't be empty) and $T$ is a "tail" consisting only of unmatched $a$s. The above fact about unmatched open's can be read directly from the grammar: all unmatched opens are derived from $T$, a $T$ can only appear at the end of a $U$, and a $U$ can only be followed by a $T$.

The clunkiness comes from preventing $U$ from matching the empty string. That prevents a bunch of what I consider spurious ambiguities: They are spurious in the sense that the matching of the opens and closes is the same in all alternative parses. If $U$ is allowed be nullable, it will also derive a completely balanced string. Since $S$ is, in effect, $M^* U$, that leads to an ambiguity in which you could consider a completely-balanced $S$ to be a series of $M$ followed by an empty $U$, or one fewer $M$ followed by a completely balanced $U$.

Probably there's a better workaround than the one I chose. But this one seems to work, and it plays well with Bison's GLR parser which I used to test it; that parser complains about ambiguous parses unless you write extra code to handle the ambiguity, and I was too lazy to do that. I tested it with strings of up to 20 open+closes, and it seems to have produced an unambiguous parse for every correctly-nested sequence, without producing parses for incorrectly-nested sequences.