Generating a set of minimal-length strings that, together, invoke every production of a context free language Problem (tl;dr)

Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once.

How and how fast can it be done?

Background

I'm working on a compiler whose parser is implemented with a tool similar to Yacc+Antlr. I've written up most of the parser code, and I'd like to generate some code of the object language that invokes every production of the grammar at least once so that I can feed it to the parser and make sure that nothing is wrong.

In the interest of good testing, what I'd really like is one, short test file that has a particular production "under test" -- so, for each production rule, I want to generate a minimal string that takes the parser from the start state, through the production being tested, to a set of terminals.

Possible solutions

I imagine there is an elegant solution using graph theory, but I'm not quite sure what it is. I would like to just use Dijkstra's algorithm to find shortest paths through some appropriate structure, but I think that a string is parsed by a context free grammar in a tree structure rather than a path, so I don't know how to make that work.

I think there might be a clever way to pose it as a network flow problem. Something like this: take a graph that has a vertex for every symbol (terminal and nonterminal) and a vertex for every production. If a nonterminal has a production, add a directed edge from the nonterminal to the production. If a production produces a symbol,  add a directed edge from the production to the symbol. Add a source with some capacity $c$ and attach it to the vertex corresponding to the start symbol. Add a sink with infinite capacity and attach it to each terminal.

If a nonterminal has an in-arc with a capacity $k$, add an arc from the nonterminal to each of its productions with capacity $k$. If a production has an in-arc with capacity $k$ and it has an out-arc to $n$ nonterminals, add an arc with capacity $\frac k n$ from the production to each nonterminal.

Then run some maximum flow algorithm on the network and let the productions "trickle down" from the start symbol to the terminals. You should end up with a flow $c$ coming out of your source, and you can return all of the terminals you hit with a nonzero flow as your result string. Then you end up with something like $O(n^3)$ time complexity for each run, where $n$ is the sum of the number of terminals and nonterminals in your grammar -- not too bad.

However, I'm still not really sure what this graph looks like: I think that it needs to be infinite and I'm not sure if you can find the maximum flow of an infinite flow network. Past that, I'm not sure how to "remove" a production from consideration so that I'm guaranteed to get a new one for each test run.

I Googled and I couldn't find anything. Is there a nice solution to this problem?

In a nutshell

Not knowing enough the literature, I worked out a solution which is
presented in the next section, together with a proof for the hardest
part. Once I knew what was needed, I could search the literature for
the right ideas. Here is a quick presentation
of the algorithm, based on the literature, which is essentially the
same I developed.

The first thing to do is to find a size-minimal terminal string
$\sigma(U)$ for every non-terminal $U$ of the grammar. This can be
done by using Knuth's extension to conc-or graphs (also known as CF
grammars) and and-or graphs of Dijkstra's shortest path algorithm.
Example B in Knuth's paper does what is needed, almost.

Actually, Knuth computes only the length of these terminal strings,
but it is quite easy to modify his algorithm to actually compute one
such terminal string $\sigma(U)$ for each non-terminal $U$ (as I do it
in my own version below). We also define $\sigma(a)=a$ for every
terminal $a$, and we extend $\sigma$ as usual into a string
homomorphism.

Then we consider a directed graph where non-terminals are the nodes,
and there is an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha
V\beta$. If several such rules can produce the same arc $(U,V)$, we
keep one such that the length $|\sigma(\alpha\beta)|$ is minimal.
The arc is labeled with that rule, and that minimal length
$|\sigma(\alpha\beta)|$ becomes the weight of the arc.

Finally, using Dijkstra's shortest path algorithm, we compute the
shortest path from the initial non-terminal $S$ to each non-terminal
of the grammar. Given the shortest path for a non-terminal $U$, the
rule labels on the arcs may be used to get a derivation
$S\overset{*}{\Longrightarrow}\alpha U \beta$. Then, to every rule of
the form $U\rightarrow\gamma$ in the grammar, we associate the
size-minimal terminal string $\sigma(\alpha\gamma\beta)$ which can be
derived using that rule.

To achieve low complexity, both Dijkstra's algorithm and Knuth's
extension are implemented with heaps, AKA priority queues. This gives
for Dijkstra's algorithm a complexity of $O(n\log n +t)$, and for
Knuth's algorithm a complexity $O(m \log n +t)$, where there are $m$
grammar rules and $n$ non-terminals, and $t$ is the total length of
all rules. The whole is dominated by the complexity of Knuth's algorithm since $m\geq n$.

What follows is my own work, before I produced the short answer above.

Deriving the solution from the useless symbols elimination algorithm.

There are several aspects to this algorithm. For better intuition I
chose to present it in three successive versions that introduce
progressively more features. The first version does not answer the
question, but is a standard algorithm for useless symbols elimination that suggests a solution. The second version answers the question without the minimality constraint, The third version gives an answer to the question, satisfying thye minimality constraint.
This third solution is then improved by using an adaptation to
and-or graphs of Dijkstra's shortest path algorithm.

The end result is a very simple algorithm, that avoids reconsidering computations already done. But it is less intuitive and does require a proof.

This answer only tries to answer the question as made precise by the OP's
comment: "for each production rule, I want to generate a minimal
string that takes the parser from the start state, through the
production being tested, to a set of terminals." Hence I only try to
get a set of strings such that for each rule, there is a string in the
set that is one of the size-minimal strings of the language having a
derivation using the rule.

It must be however noted that the fact that a string "invokes" a rule,
that is has a derivation using that rule, does not necessarily means
that the rule will be considered by a parser that work with ambiguous
grammars and resolves ambiguities arbitrarily. Handling such a
situation would probably require more precise knowledge of the parser, and
might well be a more complex question.

The basic algorithm

To solve this question, one can start with the classical algorithm for useless
symbols removal in context-free grammars. It is in section 4.4, pp
88-89, of Hopcroft & Ullman, 1979 edition. But the presentation here may be a bit different.

The algorithm aims precisely at proving the existence of such a covering as
requested by the OP, and consists in two parts:

lemma 4.1 of H&U, page 88: removal of all unproductive non-terminals. This
is done by trying find for each terminal a terminal string it can
derive on. A simple way to explain it is as follow: You create a
set $Prod$ od productive symbols, which you initialize with all
terminals. Then for each rule, not yet processed, that has all its
right-hand-side (RHS) symbols in $Prod$, you add the left-hand-side
(LHS) non-terminal to the set $Prod$, and you remove all rules with the
same LHS  non-terminal from the set of rules to be processed. You iterate the process until there is no rule left with
all its RHS symbols in $Prod$. The remaining non-terminals, not in $Prod$ at the end of this process,
are non-productive: they cannot be derived into a terminal string,
and can thus be removed from the grammar.
lemma 4.2 of H&U, page 89: removal of all unreachable
symbols. This is done by the classical node reachability in
directed graphs, by considering non-terminals as nodes and having
an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha$ such that
$V$ occurs in $\alpha$. You create a set $Reach$ of reachable
symbols which is initialized with only the initial symbol $S$. Then,
for every non-terminal symbol $U$ in $Reach$ or later added to it,
and for every rule $U\rightarrow \alpha$, you add to $Reach$ all
the symbols in $\alpha$. When all non-terminals in $Reach$ have
been thus processed, all symbols (terminal or non-terminals) that
are not included in $Reach$ cannot appear in a string derived from
the initial symbol, and are therefore useless. Thus they can be
removed from the grammar.

These two basic algorithms are useful to simplify the raw results of
some grammar construction techniques, such as used for the
intersection of a context-free language and a regular set. In
particular, this is useful in cleaning up the results of general CF
parsers.

Useless non-terminal symbols removal is necessary in the context of
solving the question asked, as the rules using them cannot be
"invoked" (i.e. used in its derivation) by any string of the language.

Building a set of string that invoke every rule

(We are not looking yet for minimal strings.)

Now answering specifically the question, one must indeed remove all
useless symbols, whether unreachable symbols or unproductive
non-terminal symbols, a well as useless rules having such useless
non-terminals as LHS. They have no chance of being ever invoked
usefully while parsing a terminal string (though some may well waste
the processing time of a parser when they are not removed; which ones
may waste time depends on the parser technology).

We now consider, for each (useful) rule, the production of a terminal string that
invokes it, i.e. that may be generated by using this rule. This is
essentially what is done by these two algorithms above, though they do
not keep the information, as they are satisfied with proving the
existence of these strings to ensure that non-terminals are both
reachable and productive.

We modify the first algorithm (lemma 4.1) by keeping with each
non-terminal $U$ in the set $Prod$ a terminal string $\sigma(U)$ it
derives on: $U\overset{*}{\Longrightarrow}\sigma(U)$. For every terminal we define the $\sigma$ as the
identity mapping. When $U$ is added to the set $Prod$ because a rule
$U\rightarrow\gamma$ has all its RHS symbols in $Prod$, then we define
$\sigma(U)=\sigma(\gamma)$, extending $\sigma$ as a homomorphism on strings, and we remove all $U$-rules, that is all rules with $U$ as LHS.

We modify the second algorithm (lemma 4.2) by keeping with each
non-terminal symbol $U$ added to $Reach$ the path used to reach it
from the intial symbol $S$, which gives the successive rules to get a
derivation $S\overset{*}{\Longrightarrow}\alpha U \beta$.

Then, for each rule $U\rightarrow\gamma$ in the grammar, we produce a
terminal string that "invokes" this rule as follows. We take from the
result of the second algorithm the derivation
$S\overset{*}{\Longrightarrow}\alpha U \beta$. Then we apply the rule
to get the string $\alpha \gamma \beta$. A terminal string
"invoking" the rule $U\rightarrow\gamma$ is $\sigma(\alpha \gamma \beta)$

Building a set of minimal strings that "invoke" every rule

We ignore the issue of eliminating useless symbols, which can be a
by-product of these modified algorithms.

Building a set of minimal strings relies on first getting a minimal
derived string for each non-terminal. This is done by further
modifying the first algorithm (lemma 4.1). First we remove from the
set of rules to be processed all recursive rules (i.e. with a LHS
symbol occurring in the RHS string). It is obvious that none of these
rules can derive to a shorter terminal string than the non-recursive
rules with the same LHS. And there must be at least one non-recursive
rule if the LHS is not a useless non-terminal (because
non-productive).

Then we procede as before to build the set $Prod$ of productive
symbols, associating with each synbol $U$ a terminal string, which we
note $\sigma(U)$. The string $\sigma(U)$ is produced as before by
application of the rule $U\rightarrow\gamma$, substituting each
non-terminal $V$ occurring in $\gamma$ with $\sigma(V)$. So far, it
was necessary to apply this to only one rule with a given non-terminal $U$
as its LHS, the first that would have all its RHS non-terminals in
$Prod$, and then ignore the others, because any such derived string
would do. But we are now looking for a minimal derived string. Hence,
for a non-terminal $U$, this has to be done for all rules with $U$ as
LHS. But we keep only one terminal string $\sigma(U)$, replacing the
current one by the newly found one, whenever the new one is smaller.

Furthermore, whenever the string $\sigma(U)$ is replaced by a smaller
one, all rules with an occurrence of $U$ in the RHS that had been
already processed have to be put back in the set of rules to be
processed, since change allows deriving their RHS on a shorter string.
So doing this will call for more iterations, but will eventually end
since none of these strings ever gets much shorter than the empty
string.

At the end of this first algorithm, the string $\sigma(U)$ is one of
the smallest strings that can be derived from $U$. There may be
others.

Now we also have to modify the second algorithm to get, for every
non-terminal $U$, (one of) the shortest string containing U as the
only non-terminal. To do this, we keep the same directed graph with
non-terminals as nodes, and having an arc $(U,V)$ iff there is a rule
$U\rightarrow \alpha V \beta$. But now we put weights on the arcs, to
compute the minimum length of the terminal context that has to be
associated with reachable non-terminals. The weight associated with
the arc $(U,V)$ above is the length $|\sigma(\alpha\beta)|$, where the
mapping $\sigma$ is extended to terminals as the identity, and then
extended again as a string homomorphism. It is the length of (one of)
the shortest terminal strings that can be derived from the string
$\alpha\beta$. Note that $V$ is removed in this calculation. HOwever,
when there are several occurences of $V$ in the RHS, only one must be
removed.  There may be several possible $(U,V)$ arcs, with different
weights, if there are several rules with $U$ as LHS and $V$ in the
RHS. In such a case, only (one of) the lighter such arc is kept.

In this graph, we no longer look just for reachability of nodes from
$S$, but for the shortest weighted path that reaches every node from
the initial symbol $S$. This can be done with Dijkstra's algorithm.

Given the shortest path for a non-terminal $U$, we read it as before
as a sequence of rules, from which we get a dérivation
$S\overset{*}{\Longrightarrow}\alpha U \beta$. Then to every rule of
the form $U\rightarrow\gamma$ in the grammar, we produce a minimal
terminal string that "invokes" this rule as
$\sigma(\alpha\gamma\beta)$

Remark: The same minimal string may probably be used for several rules. But the fact
that one of the strings uses a rule $\rho$ in its derivation does not
necessarily mean it is a minimal string for that rule $\rho$, as it may have
been found for another rule, while a shorter one can be found for $\rho$.
It may be possible to increase the likelyhood that the same minimal
string will be found for several rules by using some priority policy
whenever there is flexibility. But is it worth the trouble?

A faster algorithm for minimal terminal string deriving from a non-terminal

Building the function $\sigma$ such that $\sigma(U)$ is a minimal
terminal string deriving from $U$ is done above with a rather naive
technique that requires iteratively reconsidering work already done
when a new smaller derived string is found for some non-terminal. This is wasteful, even if
the process will clearly terminate.

We propose here a more efficient algorithm, that is, in essence, an
adaptation to the CF grammar graph of an extension of Dijkstra's
shortest path algorithm to and-or graphs, with a proper definition of
the path-concept for an and-or graph. This variant of the
algorithm probably exists in the literature (assuming it is correct),
but I have been unable to find it in the resources I can access.
Hence I am describing it in more details, together with a proof.

As previously, we first remove from the set of rules to be processed
all recursive rules (i.e. rules with a LHS symbol occurring in the RHS
string). It is obvious that none of these recursive rules can derive
to a shorter terminal string than the non-recursive rules with the
same LHS. And, for a LHS $U$ there must be at least one non-recursive
$U$-rule if the symbol $U$ is not a useless non-terminal (because
non-productive). This is not strictly necessary, but reduces the
number of rules to be considered later.

Then we procede as before to build the set $Prod$ of productive
symbols, associating with each synbol $X$ a terminal string, which we
note $\sigma(X)$, which is a size-minimal terminal string derivable from
$X$ (in the previous algorithm, that was true only after
termination).The set $Prod$ is initialized with all terminal symbols,
and for each terminal symbol $a$, we define $\sigma(a)=a$.

Then we consider every rule $U\rightarrow\gamma$ such that all RHS
symbols are in $Prod$, and we choose one such that $\sigma(\gamma)$ is
size-minimal. Then we add $U$ to $Prod$, with $\sigma(U)=\sigma(\gamma)$,
and remove all $U$-rules. We iterate until all productives
terminals have been entered in $Prod$. Any non-terminal $U$, once entered in
$Prod$, never has to be considered again to change $\sigma(U)$ for a
smaller string.

Proof:

The previous algorithms were more or less intuitively obvious.
This one is a bit trickier, because of the and-or character of the
graph, and a proof seems more necessary. All we need is actually the
following lemma, which establishes the correctness of the algorithm
when applied to the last iteration.

Lemma: After each iteration of the algorithm, $\sigma(X)$ is a size-minimal
terminal string derivable from $X$, for all $X$ in $Prod$.

The base step is obvious, since this is true by definition for all
terminals in $Prod$  when it is initialized.

Then, assuming it is true after some non-terminals have been added to
$Prod$, let $U\rightarrow\gamma$ be the rule chosen to add a new
non-terminal to $Prod$. We know that this rule is chosen because
$\gamma\in{Prod}^*$ and $\sigma(\gamma)$ is size-minimal over all RHS of all
rules with a RHS in ${Prod}^*$. Then $U$ is added to $Prod$, and we have only
to prove that $\sigma(\gamma)$ is a size-minimal terminal string
derivable from $U$.

This is obviously the case for all derivations beginning with the rule
$U\rightarrow\gamma$, since by induction hypothesis, application of mapping $\sigma$ is such that all
non-terminals in $\sigma$ are substituted with size-minimal terminal strings
deriving from them. Hence no other derivation can produce a shorter terminal string.

We thus consider only derivations starting with another $U$-rule
$U\rightarrow\beta$, such that
$\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$,
where $\Sigma$ is the set of terminal symbols.

If $\beta\in{Prod}^*$, then a minimal string it can derive on is
$\sigma(\beta)$. But, since we chose the rule $U\rightarrow\gamma$, it
must be that $|\sigma(\beta)|\geq|\sigma(\gamma)|$. So the rule
$U\rightarrow\beta$ does not derive on a smaller terminal substring.

The last case to consider is when $\beta\notin{Prod}^*$, and we then
consider a derivation $\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$.
If that derivation involves only non-trminals in $Prod$, then
$\beta\in{Prod}^*$, which is a case we have already seen. Hence we consider only
derivations that have steps using a rule with its LHS not in $Prod$.
Let $V\rightarrow\alpha$ be such a rule, such that
$\alpha\in{Prod}^*$.There must be at least one such rule since they
are partially ordered by derivation order, and $w\in{Prod}^*$.

Thus we have $U\Longrightarrow\beta\overset{*}{\Longrightarrow}\mu
V\nu$. We know that $\mu$ and $\nu$ derive on a string of
size at least 0, and since no $V$-rule with a RHS in ${Prod}^*$ was chosen, they
derive on terminal strings of length at least equal to
$|\sigma(\gamma)|$. Hence, with the rule $U\rightarrow\beta$, $U$
derives on a terminal string of length at least equal to
$|\sigma(\gamma)|$.   $\blacksquare$


What is the Expected run time of an algorithm that randomly generates N unique strings of length D? I was trying to rigorously/mathematically analyze the runtime of the following algorithm:

while i < n {
    b_D = randomly_generate_bit_array_length(D) # simply selects each bit randomly with 1/2 prob of choosing 0 or 1.
    if b_n NOT in HashTable[b_D]:
        HashTable[b_D] = b_D
        i++
}

First I started by thinking what is the probability of two strings matching and realized that the probability is equal to the probability of all bits matching:

$$ Pr[b^1 = b^2] = Pr[\cap^D_{i=1} \{ b^1_i = b^2_i\} ] = \frac{1}{2^D} = 2^{-D}$$

Then I realized that its crucial to know what the probability of a collision happening with something in the hash table if the hash table has $k$ elements (notice that its an equality because there are no intersections with events since all elements in the hash table are assumed to be unique):

$$ Pr[collision] = Pr[\cup^k_{i=1} \{ b^{current} = b^{HashTable}\} ] = k 2^{-D} $$

now the way I would normally proceed to calculate this is by writing the runtime $T(n)$ in terms of indicator random variable or some type or random variable and them compute an expectation over the distribution of coin flips of the algorithm.

$$ \mathbb{E}[T(n)]$$

however, I am having difficulties writing this step. The main issue is that it seems that in principle this algorithm could run forever (with low probability) so its possible that we loop several time in the same iteration trying to find a non colliding binary string. I think this weird unknown repetition is what I am having a hard time including in the summation. Anyone has any suggestion on how to proceed?

I think I just had a realization of maybe how to do this. Define:

$$ X_i = \text{variable indicating if it took i steps to complete} $$

then we can do:

$$ T(n) = \sum^{\infty}_{i=1} i X_i $$

the difference from usual algorithms like this is that the first $n$ terms have to be zero since we need $n$ strings, so we can never take less than $n$ steps since we need $n$ strings.

Now I just need to compute $Pr[X_i]$.

The usual way to approach your problem is as follows. When you select the $i$th string, there are $i-1$ previous strings that you have to avoid, so the probability that you generate a new string successfully is $\frac{2^D-(i-1)}{2^D}$. The expected number of strings generated before you generate a new string is thus $\frac{2^D}{2^D-(i-1)}$ – this is just the expectation of a geometrically distributed random variable. Considering all $N$ steps, the overall expectation is
$$
\sum_{i=1}^N \frac{2^D}{2^D-(i-1)} = 2^D \sum_{j=0}^{N-1} \frac{1}{2^D-j} \approx 2^D \log \frac{2^D}{2^D-N} \approx \frac{2^D}{2^D-N} N.
$$


Substring in a infinite sequence of numbers I have an infinite sequence of numbers, starting from 1 and need to find position of begin of some given substring of numbers.

Example:

1234567891011121314151617181920 ...

S = 141

Result: 18

All i think about is convert sequence to string and find substring using Rabin-Karp or KMP. But i feel that i can use it as numbers and there is some O(1) solution using math.

Another thought is split S on pieces:

141 = [(1, 4, 1), (1, 41), (14, 1), (141)]

And i have (1-9)(10-99)(100-999)(1000-9999)... which represents infinite sequence.

Than i can use this algo:

For (1, 41): try to find 1 from (1-9) and what goes next, if 41 is not next number, than try next tuple.

For (14, 1): try to find 14 from (10-99) and and what goes next, if 1 than find position of '14'.

But i'm not sure that this is correct solution.
Maybe some advices?

Your algorithm is not correct. Consider 21:

21 = [(2, 1), (21)]

First we find 2 in (1-9): 123456789. However, a 3 follows, so it's not a solution.

Then we try to find 21 in (10-99). This finds a solution, but it's 21. However there is an earlier solution:

123456789101112131415161718192021

So the solution is not correct.

The sequence you're after is A229186, but no simple formula is posted there.


Why closedness of complement of randomized classes imply containment of complement of contained classes? Suppose if class $\mathcal C$ is in $PP$ or $BPP$ does it mean complement also belongs to $PP$ or $BPP$ respectively? Does it immediately follow from $PP=coPP$?

Yes, you should follow the definitions, if $L\in \mathcal{C}\subseteq PP$, then $\overline{L}\in PP$. It immediately follows that $co-\mathcal{C}=\{L | \overline{L}\in \mathcal{C}\}\subseteq PP$.


Fastest algorithm for finding the number of primes in a range Is there an algorithm for finding the number of primes in a given range $[N, M)$ that works in time linear to $M-N$? For context, $N$ and $M$ can go up to $10^{10}$, but the distance between N and M is at most $2\times10^7$. I know that the sieve of Eratosthenes method works in $O(n\log\log n)$ time, but it would require calculating the number of primes up to $M$, which goes up to $10^{10}$ so it would be too slow.

Using the Sieve of Eratosthenes this takes $O((M-N) + M^{1/2}) \log \log M)$. This will be the fastest unless M is quite large and / or N is quite close to M.

If you had a case like $M = 10^{100}$, $N = 10^{100} - 10^{10}$ you would likely start with a sieve to throw out all of the 10 billion candidates that have a small divisor, leaving you with say $10^9$ candidates. Then you'd use Fermat's primality test to find all probable primes. Then you'd either say "that's good enough", or you follow it by a deterministic primality test for the remaining 43.4 million or so probable primes.

If you do a deterministic primality test then you would run Fermat's test with fewer individual tests since you don't mind a few "probable primes" that are composite. If you don't do a deterministic primality test then you would run Fermat's test for a bit longer. In practice the question would be: What is the chance that there is a "probable prime" that is really composite, vs. what is the chance that a number is reported incorrectly as prime / non-prime because of a hardware problem.


Converting if-then-else condition to integer linear programming with equality constraints I have an if-then-else condition with three binary variables $A$, $B$ and $C$:

if A = 1
       then B = 1
else
       B = C

How do I express this as an integer linear program with equality constraints?

We have three binary variables $x, y, z \in \{0,1\}$ and the following if-then-else (ITE) condition

$$\text{if } x = 1 \text{ then } y = 1 \text{ else } y = z$$

If $x = 1$, then $y = 1$ but $z \in \{0,1\}$. If $x = 0$, then $y = z \in \{0,1\}$. Therefore, we have the following $4$ vertices of the $3$-cube

$$\{ (0,0,0), (0,1,1), (1,1,0), (1,1,1) \}$$

Using SymPy, we obtain the following product of sums (POS):

>>> from sympy import *
>>> x, y, z = symbols('x y z')
>>> minterms = [[0, 0, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]]
>>> POSform([x, y, z], minterms, [])
And(Or(Not(x), y), Or(Not(y), x, z), Or(Not(z), y))

Converting the formula in POS, i.e., in conjunctive normal form (CNF), to integer programming, we obtain the following system of linear inequalities

$$\begin{array}{rl} (1-x) + y &\geq 1\\ x + (1-y) + z &\geq 1\\ y + (1-z) &\geq 1\end{array}$$

which can be rewritten as follows

$$\begin{array}{rl} -x + y &\geq 0\\ x - y + z &\geq 0\\ y -z &\geq 0\end{array}$$

Verifying in Haskell:

λ> triples = [ (x,y,z) | x <- [0,1], y <- [0,1], z <- [0,1] ]
λ> filter (\(x,y,z)->(-x+y>=0) && (x-y+z>=0) && (y-z>=0)) triples
[(0,0,0),(0,1,1),(1,1,0),(1,1,1)]


Algorithm comparison I am learning Big O and Big theta notation and confused the certain case.
I have two functions,
function 1(f1)
$$ n * n^{1/2} $$
function 2(f2)
$$ 1.001^n $$

in smaller cases (10,000) f1 is much faster than f2, however, it is vice versa for bigger case (10,000,000). For the smaller case, I can say
$$ f2 = O(f1) $$
In the bigger case, I can say
$$ f1 = O(f2) $$
and I think this case is,
$$ f1 = \theta(f2) $$
(If ^ this is wrong, please let me know)
At this case, can I say ??
$$ f1 \equiv f2 $$

No, you can't say that, because $O$ doesn't mean "For small inputs, [something] happens" and $\Theta$ doesn't mean "For some inputs, one of the functions is bigger and, for other inputs, the other one is." In mathematics, it is essential to use the actual definition of the concepts that you're working with, and to prove that the definition applies in your situation.


k-th smallest element in sliding segment Consider an array $a[1\ldots n]$ and another array $l = a[0]$ (initial value). At each turn we may add next element to array $l$, or remove first element from array $l$. F.e. after first iteration it could be empty or could become $a[0, 1]$. We want to find k-th smallest element at each iteration in array $l$.
First of all if size of $l$ is less than $k$ the answer is 'No'. Let's consider more interesting case.
I've decided to have two heaps (one min and one max heap).
Max heap contains all k-th smallest elements from $a[l..r]$ and min heap contains elements which are greater than the k-th smallest element. Then answer is head of max-heap (we can take it in O(1)).
But there is a small problem. What if need to consider $a[l+1 .. r]$ (so we need to push left bound). Now of course if $r - l < k$ the answer is 'No', but what should we do otherwise? I thought we should do following: if $a[l] > maxheap[0]$ then the answer doesn't change (because we will delete element greater than k-th smallest element), but what should we do with our heaps? Unfortunately I can't delete in heap by position (it takes a long time). The best we can do is delete root node in O(log n). How should I affect them?

Maintain an AVL tree $B$ that stores the elements in $l$.
In addition, for each element $a$ in $l$, keep a pointer $p_a$ to the corresponding node in $B$.

When an element $x$ is added to $l$, then simply insert a new node $v$ representing $x$ into $B$ and make $p_x$ point to $v$.

When the first element $y$ of $l$ needs to be removed, delete (the node pointed by) $p_y$ from $B$.

To report the $k$-minimum element in $l$, simply look for the minimum element in $B$ (i.e., the one stored in the leftmost node). This can be done in $O(\log n)$ time by just keeping, in each node $v$, the size of the subtree of $B$ rooted in $v$.

By combining the above operations, each turn of your problem will require $O(\log(1 + |l|)) = O(\log n)$ time.


ICP algorithm with misaligned point I am currently working on a project that involves taking a single color frame, performing image segmentation and then visualization of the scene.

I am currently at the stage of performing alignment between two objects - one in my database and one segmented from picture.

Picture data is processed: for each pixel in the color frame, I have depth data, so from a color frame I am capable of generating a (x,y,z) point for each pixel. Therefore, given my segmentation I am capable of generating a Point Cloud for each object.

So given model in my database and a point cloud ( which might not represent full object - example: I might just see a corner of a table, but I still need to align full table model), I  would like to align object in my database with points in the cloud.

I have done some research and it seems that the method widely used is the Iterative Closest Point (ICP) algorithm. But I have also a different idea, and I would appreciate your evaluation, as I have some concerns regarding ICP.

METHOD 1:ICP

Given that my model and point cloud might not be aligned by default, I have decided to pick points that should be aligned in the result output (assigning corresponding points). So I pick for instance 4 points that should be aligned. However, the issue is obviously that my selection will not be precise and therefore two points sets do not differ just by rotation and translation, but also by small point misalignment.

I want to simplify calculations as much as possible to achieve some kind of convergence.

So I was wondering whether someone has any ideas on how to solve it, and whether you can actually use ICP given this misalignment..

METHOD 2: NON-ICP

Not use ICP, but rather use a simple one iteration calculation. Calculate centroid of selected points and pick one point from model and a corresponding point from the point cloud (obviously this is approximation, because I can't pick exact point), and create two vectors :
"model centroid-to-point" vector and "point cloud centroid-to-point".

Then I could just calculate rotation and translation between these two vectors.

QUESTIONS:

1) Is there a way of solving the ICP issue?

2) Which method seems to be more sensible in terms of accuracy and possible errors?

I think you've misunderstood how to apply ICP.  If you apply it correctly, ICP shouldn't have the problem you're worried about.

You're supposed to apply ICP to all the points.  Don't just select 4 of the points and apply ICP to those points; apply it to the entire set of points.  If you pick only 4 points, yes, ICP will have the problem you describe (it'll be sensitive to small errors in the point locations).  That's why we don't do that.  Instead, ICP applies least-squares regression to all the points.  This eliminates the problem: any small errors in the point locations are averaged out, by the least-squares regression.  So, try that.  I suspect you'll be fine.

I don't expect your centroid method to work very well.  It has several potential problems:

It matches the "centroid of visible points" (from the picture) to "centroid of all points" (from the database). However, there's no reason to expect those two centroids to be in the same place.  Consider an asymmetrical object with parts that are not visible; the two centroids might be at different positions, and if so, this will introduce a systematic and potentially large error into your results.
Matching only one vector isn't enough to allow you to correct for both translation and rotation.
It requires you to know, for the selected point from the picture, which the corresponding point in the database is.  However the whole point of this problem is that we don't know the correspondence.  You could try to select the closest point in the database, but this might be wrong, since the two point-clouds haven't been registered into the same coordinate system, so this might go horribly awry.

For these reasons I don't think your method sounds very promising.

Last remark: The problem you're trying to deal with is called point set registration.  I recommend you read up on standard methods for that problem before trying to invent a scheme of your own.


Process graphs and finding infinite processes I am reading on concurrent processes and algorithms which find infinite processes by searching the process graph recursively.

Most of the material I have found is not for beginners. I am looking for references / algorithms that can help me understand:

What are process graphs?
How to search for infinite processes in these graphs?

Thanks in advance

As you propably know, a process (in terms of process algebra like CSP) can consume an input and will the behave like another process (unless it is a process that does not accept input, usually called STOP).

You can construct a graph where the nodes are the processes and the outgoing edges the input that the node can consume, directed to the node (process) that gives the new behaivior. If such a graph contains a directed path back to a starting node (i.e., a circle), you have an infinite process.

Finding a circle in a graph is a standard problem in graph theory and is usually done by DFS.

A good introduction to CSP is Tony Hoare's Book on that subject, what is easy to read also for beginners. (However, Hoare does not use the term "process graph" but talks only on "graphs".) The standard text book for CCS is Milner's "Communication and Concurrency" published by Prentice Hall.


Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function? I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square root).

I was wondering if using the previous fact and also that we knew we had a number of the form $N = 4k+3$ (not necessarily prime), then maybe there is a different primality testing for (any?) $N$ using the square root function (i.e. $SQRT_N(a) = a^{k+1} $).

So the algorithm that I thought was the following:

Choose a Quadratic Residue (QR) $a \in \mathbb{Z}^*_N$ (one can easily do this by checking if $a^{\frac{p-1}{2}} \equiv 1 \pmod p$ holds). Once we have a QR, compute $a^{k+1} = x_a$ and check if $x_a^2 $ is equal to $a$. If its true, then we conclude that $a$ is prime. Otherwise, we choose a different QR $a' \in \mathbb{Z}^*_N$ and repeat the algorithm. One can repeat this algorithm $k$ times. If after $k$ times there is no success then conclude the number is composite.

I have mainly intuitions on why its correct but not a formal proof. From the first fact that $x_a = a^{k+1}$ is a square root when $p$ is prime, it must mean that $x_a^2 \equiv a \pmod p$. Therefore, if $a$ is a QR then that check will pass (half the time we will choose a QR so the probably that we choose a non QR is only 1/2).

However, if $N$ is composite, it seems we have no guarantee that $x_a^2 \equiv a \pmod N$. So if it doesn't hold we are sure its not prime. But if it does hold then if its prime we are right but if its composite we might be wrong? Basically, is it possible to use the SQRT function when $N = 4k+3$ to decide if $N$ is prime or not?

I also thought of an another algorithm that deserved its own question: Is computing a square root of a number and having more than 2 roots a reliable way to decide primality?

Let me start with a counterexample where your algorithm gives the wrong answer: i.e., where $N$ is composite but your algorithm concludes it is prime.  Suppose $N=91$ and $a=9$.  Then $a^{(N-1)/2} = 9^{45} \equiv 1 \pmod{91}$, so $a$ passes your check to be a QR.  Also, $a^{(N+1)/4} = 9^{23} \equiv 81 \pmod{91}$ and $81^2 \equiv 9 \pmod{91}$, so this passes your second test, your algorithm will conclude that 91 is prime.  However, 91 is not prime: $91=7 \times 13$.  Thus your algorithm has drawn the wrong conclusion in this case.  This demonstrates that your algorithm can output incorrect answers in at least some cases.

Actually, there is a more serious problem with your algorithm.  There is no number $N$ where your algorithm will ever output "composite".  It thinks that all numbers are primes.  More precisely, for every $N$, your algorithm will either loop forever (trying to find a number that passes the QR test, in vain), or will terminate and output "prime".  So, your algorithm is about as wrong as could be.

You can see this by applying some number theory.  You have a test whether $a$ is a QR and a second test based on the square root insight.  If $a$ passes the first test, it will pass the second one.

Here's why.  Your QR test succeeds if $a^{(N-1)/2} \equiv 1 \pmod N$.  Your second test succeeds if $(a^{(N+1)/4})^2 \equiv a \pmod N$.   The latter is equivalent to $a^{(N+1)/2} \equiv a \pmod N$.  But $a^{(N+1)/2} \equiv a \times a^{(N-1)/2} \pmod N$.  Therefore, if $a^{(N-1)/2} \equiv 1 \pmod N$, then (multiplying both sides by $a$) we immediately see that we must have $a^{(N+1)/2} \equiv a \pmod N$.

Each of the $k$ passes of your algorithm basically amounts to looking for an $a$ that passes the first test, and then checking whether it passes the second test -- but based on the prior insight, we see that any $a$ that passes the first test will be guaranteed to pass the second test as well.  Thus, if the algorithm ever finds any value $a$ that passes the QR test, the second test will automatically pass and the algorithm will output "prime".

The lesson to learn: any time you think you have an algorithm that looks promising, it's worthwhile to code it up and try it on some test cases and see if it seems to work well.  Trying it on a few test cases is not a substitute for a proof of correctness, but it can be a helpful way to weed out some incorrect algorithm quickly.

Finally, on to your real question: can we use something like this to build a primality test? Well, you can think of the Miller-Rabin primality test as loosely based on something like this.  They are based on a characterization of what the square roots of $1$ should look like, if $N$ is prime.  If you encounter a square root of $1$ that is not $1$ or $-1$, you can conclude that $N$ is not prime.  However, it's not limited to numbers $N$ of the form $N=4k+3$, so in that sense it is definitely different.


Difference between SRSW and MRSW safe Boolean registers I'm reading The Art of Multiprocessor Programming and am currently trying to understand Chapter 4 — The Foundations of Shared Memory.

In section 4.2 it is shown how to build a multi-reader, single-writer (MRSW) safe Boolean register from a single-reader, single-writer (SRSW) safe Boolean register. So, the only difference is that the new register supports multiple readers, but the consistency guarantee (safe) is the same.

The implementation (figure 4.6) uses an array of SRSW safe Boolean registers, with one element for each reader. What I don't understand is why can't we treat a SRSW safe Boolean register as a MRSW safe Boolean register, already?

The definition for the safe consistency level says that a register is safe if:

A read call that does not overlap a write call must return the value written by the most recent write call.
A read call that overlaps a write may return any value within the register's allowed range of values (in the case of a Boolean register, just 0 and 1).

It seems to me that a SRSW safe Boolean register can already be treated like a MRSW safe Boolean register because any number of reads concurrent with a write will return either 0 or 1. Non-overlapping reads are obviously fine.

Is there a nuance I'm missing here or is it just a self-imposed limitation that a SRSW safe Boolean register can't be used with multiple readers, just by the definition? I understand this whole register derivation tower is pretty artificial and used mostly for theoretical considerations, so I'm thinking such an artificial limitation is very possible.

You do not know anything about the behavior of the register if read calls overlap.

Perhaps the register is a sensitive electrical component and overlapping reads will blow it up?

Perhaps reading (counter-intuitively) requires changing the state of the register, for instance writing the target memory location which the value must be read in to? If two reads overlap then it might end up writing the value to the wrong location or to only one of the two locations?


What's the difference between Computer Science and Informatics? The Terms are much used in actual IT (Information Technology). Is it possible to make a difference or are this terms nearly synonyms for the same fact?

I deliberately use very common, not necessarily professional resource.

Computer Science

  Computer science is the study of the theory, experimentation, and engineering that form the basis for the design and use of computers. It is the scientific and practical approach to computation and its applications and the systematic study of the feasibility, structure, expression, and mechanization of the methodical procedures (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information. An alternate, more succinct definition of computer science is the study of automating algorithmic processes that scale. A computer scientist specializes in the theory of computation and the design of computational systems.

source: Computer Science @ Wikipedia

Informatics

  Informatics is a branch of information engineering. It involves the practice of information processing and the engineering of information systems, and as an academic field it is an applied form of information science. The field considers the interaction between humans and information alongside the construction of interfaces, organisations, technologies and systems. As such, the field of informatics has great breadth and encompasses many subspecialties, including disciplines of computer science, information systems, information technology and statistics. Since the advent of computers, individuals and organizations increasingly process information digitally. This has led to the study of informatics with computational, mathematical, biological, cognitive and social aspects, including study of the social impact of information technologies.

source: Informatics @ Wikipedia

It is for sure time and place dependent, after further research it seems that the German term Informatik was a synonym of the Computer Science at first, was adapted virtually everywhere, but evolved since 1956, and diverged with meaning, but it is still overlapping. Tt seems that currently Informatics is used more as applied Computer Science (ref: search engine coin toss).

The IT (Information Technology) in some languages has broader meaning, and simply merges telecommunication with computer sciene and informatics. Unfortunately this is not well-defined term, it is part of the language so it may vary in time up to the moment when people think it is too broad and start some finer classification.

Please see also Informatics vs. Computer Science


Writing a factorial function in ARM assembly language I am required to write a factorial function in ARM assembly language that takes an integer $ n $ as input and returns the value of $ n! $. However, I can only use the $ 4 $ basic arithmetic operations $ + - * / $ (so no if-else or loop or recursion). Can anyone suggest a hint to do that? I can only do if I am allowed to use if-else or recursion.

we were required to do something similar. We were given a number to calculate, which was 7!.r0 will hold the final value. I ended up doing the following:

MOV r1, #7
MOV r1, #6
MOV r1, #5
MOV r1, #4
MOV r1, #3
MOV r1, #2
MOV r1, #1

MUL r0, r1, r2
MUL r0, r0, r3
MUL r0, r0, r4
MUL r0, r0, r5
MUL r0, r0, r6
MUL r0, r0, r7


Recurrence relations when function call is made inside loop int fun (int n)
{
  int x=1, k;
  if (n==1) return x;
  for (k=1; k<n; ++k)
     x = x + fun(k) * fun(n – k);
  return x;
}

  What is the value of fun(5)?

I find it difficult to realize a recurrence tree when the functions are called inside loops so I decided to go with the recurrence relations.

This is what I came up with :

However, the recurrence relation given in the solution book is slightly different:

I don't understand where I went wrong. I included 1 inside the summation since x loops with every iteration. So why is the 1 in the second equation outside?

First, those two summation are not equivalet, the reason that the $1$ is outside is because this line in your code:

 int x=1,k;

Try to run this "by hand" and you will understand why you are addidng $1$ only once.

$\text{fun}(1)=1\\
\text{fun}(2)=2\\
\text{fun}(3)=5\\
\text{fun}(4)=15$

$$\Longrightarrow \text{fun}(n)=\begin{cases}
1;&&&&&&&&n=1\\
\color{red}1+\displaystyle\sum\limits_{k=1}^{n-1}\text{fun}(k)\times \text{fun}(n-k)&&&&&&&&n>1
\end{cases}$$

EDIT:

Step by step for n=3:

int fun (int 3)
{
  int x=1, k;
  if (3==1) return x;
  for (k=1; k<3; ++k)
     x = x + fun(k) * fun(3 – k);
  return x;
}

First loop $k=1:$

$x=\color{green}1+\underbrace{\text{fun(1)}}_{=1}\times \underbrace{\text{fun(3-1)}}_{=2}=\color{red}3$

Second loop $k=2:$

$x=\color{red}3+\underbrace{\text{fun(2)}}_{=2}\times \underbrace{\text{fun(3-2)}}_{=1}=\color{blue}5$


How to prove that a minimum edge cover is a forest? How can it be proved that any minimum edge cover is a forest? As far as I understand an edge cover could be one connected component therefore a spanning tree). If it's the case then it wouldn't be a forest.

A forest is a graph in which every component is a tree. If there is only one component, and that component is a tree, the graph is a forest.

So why is every minimum edge cover a forest? Suppose you have a graph $G=(V,E)$ and an edge cover $C\subseteq E$. Suppose some component of the graph $(V,C)$ contains a cycle, say $x_1x_2\dots x_kx_1$. Then $C\setminus\{x_1x_2\}$ is a smaller edge cover than $C$: $x_1$ is covered by the edge $x_kx_1$, $x_2$ is covered by $x_2x_3$ and every other vertex in $V$ is still covered by whatever covered it in $C$. Therefore, every minimum edge cover must contain no cycles, and an undirected graph that contains no cycles is a forest.

Indeed, we can go even farther. If an edge cover $C$ contains a path $x_1x_2x_3x_4$ then $C\setminus\{x_2x_3\}$ is a smaller edge cover, by essentially the same reasoning as above. Therefore any minimal edge cover is a forest that contains no path of three or more edges. So, not only is every minimum edge cover a forest, but it's a forest where every component is a star (a complete bipartite graph $K_{1,k}$ for some $k\geq 1$; note that $K_{1,1}$ is an edge and $K_{1,2}$ is a two-edge path).


Can P=PSPACE and PSPACE problems be formulated as $\Pi_1$ formula? To say simply, can PSPACE problems be written as $\Pi_1$ formula? Or how can these problems be written in terms of (first-order) arithmetic hierarchy?

edit:also currently, by what arithmetic hierarchy formula can P=PSPACE be written?

and what would be the consequence of being able to write P=PSPACE as $\Pi_1$ formula?

You can get a $\Sigma_2$ sentence for $\mathsf{P}=\mathsf{PSPACE}$, using the same technique as in the blog post, only replace $SAT$ by $QBF$. I doubt there is a known sentence of lower complexity.


How to Optimise my Time Optimisation Algorithm I recently encountered a problem which goes like this :
A student is given N number of questions and T time in total. Each question requires different time to complete and carries different marks. The problem asks to find the maximum marks the student can get by attempting some of the N questions within T time (Assuming if a question is attempted, it must be fully completed,no partial attempt of a question is allowed).

I tried to solve the problem by computing all possible combinations of questions which takes <= T seconds to complete but soon found out its ineffective for large datasets.

How can I optimise my solution? Is there any alternative solution available?

You're trying to solve a knapsack problem – you're trying to choose items of maximum value, given a constraint on their total size. These problems are NP-complete but can be solved reasonably efficiently in practice. The standard technique is to use dynamic programming. This gives a solution in time polynomial in $N$ and $T$. This is still, technically, an exponential-time algorithm (since an input of length $\ell$ could give $T$ as large as $2^\ell$) but it works well in practice.

I won't give details of how to do the dynamic programming, since knapsack is one of the standard examples of the technique so it's easy to find the details online and in textbooks.


Approximation Algorithm for Independet Set Problem: Any Explanation Please? I am reading this note on approximation algorithms for independet set problem. I am confused of Theorem 1. and Corollary 3.

Here is the statement of Theorem 1.

Theorem 1 (Hastad [1]) Unless P = NP there is no $\frac{1}{n^{1-\epsilon}}$-approximation for MIS for any fixed $\epsilon>0$ where $n$ is the number of nodes in the given graph.

Here is the statement of Corollary 3.

Corollary 3
Greedy gives a $\frac{1}{\Delta+1}$-approximation for (unweighted) MIS in graphs of degree at most $\Delta$.

I feel like there is a contradiction between Theorem 1. and Corollary 3., no? Or because the graph in Corollary 3. is a special one with degree at most $\Delta$?

[1] J. Hastad. "Clique is Hard to Approximate within $n^{1-\epsilon}$". Acta Mathematica, 182:105{142, 1999.

In general, the maximal degree in a graph can be as large as $n-1$. Therefore on general graphs, the greedy algorithm is only guaranteed to give a $1/n$ approximation, which you can also obtain by returning an arbitrary vertex.

What Corollary 3 does imply is that the graphs that Håstad uses have maximal degree $\Omega(n^{1-\epsilon})$.


Randomized convex hull I've been recently studying Monte-Carlo and other randomized methods for a lot of applications, and one that popped into my mind was making an (approximate) convex hull by examining random points, and try to get them inside the convex hull. I would like to know if there are algorithms for convex hulls that can improve the $O(n \log n)$ bound of comparison based algorithms, and the $O(n\cdot h)$ bound for Jarvis march and related to $O(n)$, either by building an approximate convex hull in $O(n)$ (with or without some approximation criteria) or by building an exact convex hull in expected linear time.

Two linear time approximation algorithms in the two-dimensional case are due to Bentely, Preparata and Faust and Stojmenović and Soisalon-Soininen.

A fast exact algorithm which works in expected linear time is due to Bentley, Clarkson and Levine. The paper is quite old, so maybe there are newer developments.


Balancing a Binary Search Tree I was reading about binary search trees on it's Wikipedia article. I was a little confused by this image. Why is it that the right branch to the head node does not have a sub-tree? I understand why it can be valid like this but surely the "8" could branch to "13" instead, then "10" and "14" could become the descendants of "13". It seems like this would be far more balanced. So I researched around for more information about binary search tree balancing and I'm still unsure. Why is the diagram in the Wikipedia article was favored? Is my suggestion wrong?

Depth-first in-order traversal still works as I presume the same for all other traversal methods.

Yes, the right subtree could be $13(10,14)$.
But notice that the article you've linked discusses the most naive version of building a Binary Search Tree, in which numbers are simply inserted into the tree one-after-another without balancing. So in your example first the $10$ was inserted, then the $14$, then $13$.
Of course there are plenty of other algorithms that balance the tree (they are also linked in the Wiki-article).


What does synchronous and asynchronous mean in computer science? Words synchronous and asynchronous can be met several times, in different contexts, when studying computer science. As an example :

Synchronous and asynchronous circuits.
Synchronous and asynchronous calls.
Synchronous and asynchronous messages.

I never really understood the real meaning of those terms, and also the common sense that different usages of synchronous and asynchronous have.

So my question is : What does synchronous and asynchronous really mean in computer science ?

As Discrete lizard suggests, there is not some precise CS-wide definition for these terms. Generally, you should not expect terms and notation to always mean the same thing even within a single field.

Nevertheless, a vague general statement is that in "synchronous" systems, things "wait" for other things, while in "asynchronous" systems, things don't "wait".

That said, it's probably better to split this into two broad interpretations of this. There's "synchronous" in the sense of everything moving in lock-step (i.e. everyone "waits" for the next "round" or everyone "waits" on a "clock"). This interpretation is probably the closer of the two to the colloquial notion. This applies to synchronous circuits, Bulk Synchronous Processing, and synchronous data flow. A synchronous circuit has a clock signal and it executes in time with the clock. An asynchronous circuit allows each subcomponent to execute whenever it's ready. It requires careful timing to make sure all the inputs to each subcomponent are ready when that subcomponent is ready.

The other interpretation is blocking where one thing makes a request to another thing and then sits there waiting for the response. The "waiting for the response" aspect is what is called "blocking". Synchronous calls/messages would fall under this. The alternative is to send a message and then continue on without waiting for a response. Any response is either ignored or collected in a "mailbox" to be read at some later time. This is often handled by the framework you're using which will then dispatch events to which you register.

The Ptolemy Project is a fantastic resource for in-depth thoughts on different models of computing and their notion of time.


Space complexity of directed and undirected graph I have started reading graph theory from Introduction to Algorithm. The author starts by saying that if the graph is dense then:

$$|E|\text{ close to }|V|^2$$ else if the graph is sparse then:

$$|E|\text{ is much less than }|V^2|$$

According to me the above two relations makes sense in respect of a complete graph where the total number of edges is $\frac{(V)*(V-1)}{2}$ hence, $E = O(V^2)$.

Hence, we choose adjacency list representation where the length of the list is $\text{2|E|}$ for undirected graph and $\text{|E|}$ for directed graph. After that he simple concludes that space requirement for the adjacency list representation is $\Theta(V+E)$. I am really stuck on how he came to this conclusion without any explanation. According to me it should be $O(V*(V-1))$ because for each vertex the maximum possible edge is $V-1$. What I am doing wrong?

It's hard to know for sure from what you've written, but I suspect what you're doing wrong is that you're considering what the space requirement would be for a complete graph.  For a complete graph, the space requirement for the adjacency list representation is indeed $\Theta(V^2)$ -- this is consistent with what is written in the book, as for a complete graph, we have $E=V(V-1)/2 =\Theta(V^2)$, so $\Theta(V+E)=\Theta(V^2)$.

However, you shouldn't limit yourself to just complete graphs. There are other graphs that aren't complete, and have fewer edges than the complete graph.  In general, the space for the adjacency list representation is $\Theta(V+E)$; this fact holds for all graphs, regardless of how many edges they have.

Why is this true?  It's because for each vertex you have a pointer to the head of a linked list.  That's $\Theta(V)$ space for all of those pointers.  Also, the total number of nodes across all the linked lists is equal to $2E$, as each edge $(u,v)$ appears twice: once in the list for $u$, and once in the list for $v$.  Therefore the space needed for all of the linked lists is $\Theta(E)$.  Adding the space for the pointers and the space for the lists gives $\Theta(V+E)$.

You could say that the space requirement for the adjacency list is $O(V^2)$.  It's true that it will never be more than that.  However, for some graphs it will be much less.  For instance, in a graph that is a simple path ($v_1 \to v_2 \to \dots \to v_n$), there are $V$ vertices and $E=V-1$ edges in total.  For that graph, the adjacency list representation will need $\Theta(V+E)=\Theta(V)$ space.  Thus the $O(V^2)$ upper bound is very loose and too pessimistic.


High dimensional Pareto dominance query data structure I have a large (10 million+) set $X$ of  data points in some high dimensional $\mathbb{R}^d$ ($d \geq 500$) space. Each data point is quite sparse, e.g. has around $10$ components. Every missing component can be seen as having value $-\infty$ for the purposes of this problem. Associated with each data point $X_i$ is a price $y_i$.
As a quick refresher, a Pareto order is a partial order that orders vectors by those that are 'strictly better', component-wise. That is, for $a, b \in \mathbb{R}^d$ we have
$$a \preceq b \iff \forall i  : a_i \leq b_i.$$
In this case we also say that $b$ dominates $a$ (although not strictly, $a$ and $b$ could be equal). Finally note that this is very much a partial order, it very often happens that $a$ and $b$ are incomparable.
Let $D(z) = \{x \in X : z \preceq x\}$ be the elements in our dataset that dominate $z$ (taking into account only the data points, not their associated prices). I wish to know if there exists an efficient data structure that can answer two things about some $z \in \mathbb{R}^d$  (even sparser, e.g. around $4$ to $5$ components):

the number of items that dominate $z$, or $|D(z)|$, and
the cheapest $k$ prices among those that dominate $z$, or the smallest $k$ elements of $\{y_i : X_i \in D(z)\}$.

Note that $k$ is small here (e.g. $10$) even though $D(z)$ might contain thousands of elements.

Does a data structure solving this problem efficiently exist? Every approach I can think of suffers badly from the curse of dimensionality.

Here is one approach you could consider.  If the number of non-missing coordinates is tightly concentrated around 10, it might help you partly avoid the curse of dimensionality.  I don't know whether it will be useful in practice.
Choose a random hash function $h:\{1,\dots,d\} \to \{1,\dots,10\}$.  If $x \in \mathbb{R}^d$ is a data point, let $f(x)$ be its signature, where $f:\mathbb{R}^d  \to \mathbb{R}^{10}$ is defined as
$$f(x) = (x^*_1,\dots,x^*_{10})$$
where $x^*_j = \max \{x_i \mid h(i)=j\}$.
Notice that the signature is dense, i.e., $f$ maps a sparse high-dimensional vector to a dense low-dimensional vector.
Also, notice that $f$ is monotonic: if $z \preceq x$ then $f(z) \preceq f(x)$.  The converse does not necessarily hold.
The approach will be to build a data structure that, given a query $z$, helps us enumerate all $z$ such that $f(z) \preceq f(x)$; then we will check each such $x$ to see whether $z \preceq x$, and count the number that do, or output the lowest-priced ones that do.  This reduces the problem from a 500-dimensional problem (on sparse data points) to a 10-dimensional problem (on dense data points).
How does the 10-dimensional data structure look?  We can use a simple trie, where the $i$th level branches on the value of $x^*_i$, and each leaf stores one data point.  In practice, I suggest organizing the list of children at the $i$th level using a binary search tree keyed on $x^*_i$, rather than as a list.
Now, the lookup algorithm simply traverses the trie recursively, but with the traversal pruned in the obvious way.  In other words, at each level we only explore the children $x^*_i$ where $z^*_i \le x^*_i$ (for query $z$).  Using the binary search tree data structure, at each level it is easy to enumerate only those children without having to enumerate the other children.
What is the running time of this algorithm?  The worst-case time could be bad, but I'll analyze the average-case running time, via an extremely crude heuristic.  If $z,x$ are two randomly chosen data vectors, then crudely $\Pr[z^*_i \le x^*_i] \approx 1/2$ for each $i$, as we have two randomly chosen numbers from $\mathbb{R}$ and it is roughly equally likely which one is larger.  Therefore, we can expect that only about a $1/2^{10}$ fraction of the data points $x$ will satisfy $f(z) \preceq f(x)$.  And, the running time of the recursive traversal of the trie will be approximately proportional to the number of such data points $x$.  Therefore, this heuristic predicts the average-case running time of this algorithm, on a random query $z$, to be something like $O(|X|/2^{10})$ time.  In other words, this is approximately a 1000-fold speedup over the naive algorithm of enumerating all data points in your dataset.  This crude analysis is overly optimistic and probably the true running time will be worse (e.g., due to collisions in the hash function, as this analysis implicitly assumed that both $z$ and $x$ have exactly 10 components and there are no collisions in the hash function, but in practice neither of those will always be true).

P.S. There are multiple variants possible.  We can also consider replacing 10 by an arbitrary $d'$ and optimizing over $d'$.  Also, we can alternatively define $f$ by
$$f(x) = (x^*_0,x^*_1,\dots,x^*_{d'})$$
where $x^*_0$ is the number of $x^*_1,\dots,x^*_{d'}$'s that are not $-\infty$.  I don't know whether either of those would be better, but they could be variants to try on your data set.
Another possible optimization is to precompute a dozen different copies of the data structure for a dozen different hash functions.  Then, when you want to answer a query for $z$, check which hash function maximizes the number of coordinates in $f(z)$ that are not $-\infty$, and use the corresponding data structure for the lookup.  If $x$ has exactly 10 non-missing coordinates, then it is very likely that one of these hash functions leads to a signature with only 0, 1, or 2 coordinates at $-\infty$.  Also you could consider an approach where $d'$ is large, say $d'=20$; then there is a good chance that there will be one hash function that does not introduce any collision... though I'm not sure what the effect of increasing the dimension like that might be on running time.


Is this a known problem in graph theory? My basic problem includes a graph where each node $i$ is associated with a weight $c_i$, and the problem is to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$. This is I believe a well-known problem in graph theory that is well-studied for different types of graphs.
Now, suppose I am dealing with a generalized form of the problem as following. The weight of each node can take $p$ different values, that is each node is associated with $p$ different weights. The aim is again to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$, however, each type of weight can be selected only once. Precisely, if the weight type $j$ is selected for the node $i$, i.e., we select the weight $c_{ij}$, then the other selected nodes cannot take a weight of type $j$.
My question is that, is this still a graph theory problem? Is it a known generalization in the graph theory problems?
Any help and/or reference is appreciated.

If $G=(V,E)$, with $V=\{v_1,v_2,...,v_n\}$ and weights $\{c_{i,j}, i=1,2,...,n, j=1,2,...,p\}$ is the given graph, then we can construct the strong product (I finally found the name of the operation) $G\boxtimes K_p$ of $G$ and $K_p$, where $K_p$ is the complete graph with $p$ vertices. This is the graph with vertices $\{v_{i,j},i=1,2,...,n, j=1,2,...,p\}$ and edges $\{v_{a,b},v_{c,d}\}$ where either:

$a=c$,
$b=d$ or
$\{v_a,v_c\}\in E$. (The actual condition of the strong product reduces to this since in $K_p$ all vertices are adjacent).

We give the vertex $v_{i,j}$ the weight $c_{i,j}$, for $i=1,2,...,n$ and $j=1,2,...,p$.
The problem on $G$ is equivalent to the problem minimum (maximum) weighted independent set in the weighted $G\boxtimes K_p$. If a vertex $v_{i,j}$ of the new graph is chosen this corresponds to choosing vertex $v_i$  of the original graph and using the $j$-th weight $c_{i,j}$ corresponding to it.
The set of edges of $G\boxtimes K_p$ are exactly those that prevent the corresponding choices in $G$ to use adjacent vertices or reusing weights with the same index:

Condition $1$ defines edges in the strong product that prevent the equivalent of using two weights from the same original vertex.
Condition $2$ prevents using the weights with the same index from different vertices of the original graph.
Condition $3$ prevents that two vertices that were neighbors in the original graph are selected.

Example:
If $G$ is the graph

and $p=2$, then $G\boxtimes K_2$ would be the graph

Images created with this tool.


Finding the grammar type of the programming language How can someone find what type of grammar for a given programming language?

Formerly I'm looking for a grammar type for most popular programming languages: C, C++, C#, Java, List, OCaml, Haskell etc.

Programming languages are typically defined in several stages. A language in formal language theory is a set of strings, but that isn't a very useful concept to explain programming languages. The meaning of a source program is defined by several stages of translation; here are typical stages in the compilation of a translation unit:

Lexical analysis, i.e. splitting the program into tokens. Token recognition is often performed by finite automata, but not always (e.g. languages with nested comments need a stack at this stage).
Parsing. This stage is usually described by a context-free grammar. Although lexical analysis could be described by that same context-free grammar, this would typically result in an extremely complex and slow-to-parse grammar, which is why the two stages are separate.
Variable binding, i.e. associating the different uses of the same name to mean the same variable. In particular, in most languages, variables need to be declared before use. This cannot be described by a context-free grammar.
Typechecking, if the language has a static type system. There is a lot of variability here.
After that point, subsequent compilation stages tend not to have failure cases. There are exceptions, for example some languages regulate recursive definitions at a late stage.

There's no grammar type that describes valid programs in typical programming languages (unless you go for a formalism that can describe all decidable languages or more, such as unrestricted grammars). Many languages can be described by a context-free grammar up to stage 2, but there are exceptions (for example, C has feedback from variable binding to parsing because something like f(); foo * bar; is valid in C89 if foo is a variable but not if foo is a type defined by typedef). When you reach the binding stage, there has been work on general models for binding, but I'm not aware of any name for the kind of languages and transducers that correspond to context-free-grammars-plus-bindings. For typechecking, the sky's the limit: there are languages with Turing-complete type systems, and even the ones that aren't are typically very ad hoc and don't particularly fit any interesting category other than decidable.


Variant of 3-SAT is NP complete? Consider a restriction on 3-SAT in which no literal occurs in more than two clauses.
How do we show that this is NP complete ?

(edit - I was getting confused over the definition on the 3-SAT,here by 3-SAT it implies that a clause can have at most 3 literals.)

I have found a reduction from 3-SAT.

For every instance of variable $y$, I will put a new variable $y_i$ in its place. Suppose there were $K$ such instances then after replacing each instance of $y$, I will add clauses  $\bar y_1 \vee y_2, \bar y_2 \vee y_3, \ldots, \bar y_K \vee y_1$. This ensures that $y_1,\ldots,y_K$ will be assigned the same value.


Automated reasoning with real numbers I have a large number of equivalences which look like:
$(a \leq 0.54 \wedge b \geq 0.12) \vee (c \gt 0.98)$ $\Leftrightarrow$ $(x \leq 0.25) \vee (x \gt 0.91 \wedge y \geq 0.01)$
This is just an example. In general, formulae on either left or right side of the equivalence  could be anything that takes the form of a disjunctive normal form (DNF) clause, the numbers could be any real numbers with a fixed precision, and the inequality signs could be $\leq$, $\lt$, $\geq$, or $\gt$.
What is important is that the possible variables on the left side of all the formulae (here $\{a, b, c\}$) form a set that is distinct from the possible variables on the right side of all the formulae (here $\{x, y, z\}$). There could be any fixed number of variables on either side: doesn't need to be 3 variables, and doesn't need to be an equal number on either side.
I also have some implications of the form:
$(a \leq 0.32 \wedge b \geq 0.62)$ $\Rightarrow$ $(c \gt 0.00)$
Here both left and right sides are just conjunctions of inequalities, but what is important is that the set of variables on both left and right sides, i.e. $\{a, b, c\}$ here, is the same as the set of variables on only the left side of the previous kind of the formula (i.e. the equivalences).
My question is: what kind of automated reasoner would I need to find the logical consequences of a set of such formulae? I am just looking for a concrete identification of the general class of problems this belongs to, and any out-of-the-box reasoners which may be available. Perhaps this is an SMT problem?

In your case, the simplest solution may be to use SAT.
Your first clause includes $x \le 0.25$ and $x > 0.91$. This means that there are five regions of interest for the variable $x$, which we identify with boolean variables: $X_1 \equiv x \in(-\infty, 0.25)$, $X_2 \equiv x = 0.25$, $X_3 \equiv x \in (0.25, 0.91)$, $X_4 \equiv x = 0.91$, $X_5 \equiv x \in (0.91,\infty)$.
Create a boolean variable for each of these ranges, and convert the clause to use them. So, for example, $x \le 0.25$ would convert to $X_1 \vee X_2$, and $x < 0.91$ would convert to $X_1 \vee X_2 \vee X_3$.
More clauses would mean more constants, and hence more ranges of interest for a primitive variable.


how does the shap algorithm work in polynomial time? I'm trying to understand how the shap algorithm calculates in polynomial time an estimation to the feature attribution function that satisfies the shapely value attributes (specifically for tree based models!).
A simplified version of the feature attribution function for the feature $i$ of the model $f$  prediction for the input instance $x$ is: $\phi_i(f, x)=\sum_{S \in N /\{i\}}[f_x(S\bigcup{i})-f_x(S)]$ - i.e. sum the change in the model prediction for every set of features $S$ that does not include the feature $i$ from the same set when $i$ is introduced.
The naive exponential estimation for a tree based model (Algorithm 1 in the paper), estimates $f_x(S)$ by recursively following the decision path for $x$ if the split feature is in $S$, and taking the weighted average of both branches if the split feature is not in $S$ (weights are the coverage of train samples in that branch). We do that for every set $S$ in the powerset of features.
So far so good. But now the paper describes Algorithm 2 - a polynomial method for computing the same values, basically by "running simultaneously for all $2^N$ subsets"! I can't understand that, no matter how much I try (see my notebook).
Can someone enlighten me and explain how is that working? how are we tracking the number of sets and the coverage in every path?
Note that the real algorithm is much more complex than what I'm presenting here, as the real feature attribution function weights each set $S$ proportionally to the number of features in it $|S|$ - but I'm not interested in that complexity, only in the basic simplified setup I've presented here.
Thanks for your efforts, this is something that's eluding me for years

First, some notation.
A decision tree is a binary tree in which each internal node is labelled by one of $x_1,\ldots,x_n$, and has two outgoing edges labelled $0$ and $1$. Leaves are labelled with real numbers. To evaluate the decision tree on an input $(x_1,\ldots,x_n) \in \{0,1\}^n$, we just follow the tree from the root to a leaf, and output the value on the leaf. From now on, we fix a decision tree $T$, as well as a reference output $y$.
A decision tree is irredundant if no root-to-leaf path contains the same variable twice. We can easily make a tree irredundant in linear time, and so we assume that $T$ is irredundant. (For some reason, the paper doesn't make this assumption.)
Given a subset $S \subseteq [n]$, let $f(S)$ denote the expect output of $T$ when run on a random input $x$ subject to $x_S = y_S$ (i.e., $x_i = y_i$ for all $i \in S$). Alternatively, it is the expected value of the following process. Start at the root and proceed to a leaf. At any given node, if the node queries a variable $i \in S$, go to the branch labelled $y_i$. Otherwise, take a random branch. Thus $f([n])$ is the value of $T$ on $y$, and $f(\emptyset)$ is the value of $T$ on a random input.
For $i \in [n]$, we define the Shapley value $\phi(i)$ to be
$$
\phi(i) = \sum_{i \notin S} \frac{|S|!(n-|S|-1)!}{n!} (f(S \cup \{i\}) - f(S)).
$$
For the actual algorithm, the coefficients won't matter much. Indeed, we will calculate directly
$$
\alpha_+(i,\ell) = \sum_{\substack{i \in S \\ |S|=\ell}} f(S), \\
\alpha_-(i,\ell) = \sum_{\substack{i \notin S \\ |S|=\ell}} f(S),
$$
from which we can determine $\phi(i)$ using the formula. In the same way, we can compute other power indices, such as the Banzhaf index.
Let $v$ be any node in $T$. Define $\alpha_{\pm}(i,\ell,v,s_0,s_1)$ as the same value as above, when run on the decision tree rooted at $v$, given that we have already put $s_1$ nodes inside $S$, and $s_0$ nodes outside $S$. Thus we are interested in $\alpha_-(i,\ell,r,1,0)$ and $\alpha_+(i,\ell,r,0,1)$, where $r$ is the root of $T$.
If $v$ is a leaf then $\alpha_{\pm}(i,\ell,v,s_0,s_1)$ is just the label of $v$ multiplied by the number of possible sets $S$, which is $\binom{n-s_0-s_1}{\ell-s_1}$. Now suppose that $v$ is an internal node labelled with $x_j$ and having children $v_0,v_1$. If $j = i$ then
$$
\alpha_+(i,\ell,v,s_0,s_1) = \alpha_+(i,\ell,v_{y_i},s_0,s_1), \\
\alpha_-(i,\ell,v,s_0,s_1) = \frac{\alpha_-(i,\ell,v_0,s_0,s_1) + \alpha_-(i,\ell,v_1,s_0,s_1)}{2}.
$$
(In fact, it doesn't matter whether we choose $\alpha_+$ or $\alpha_-$ on the right-hand side.) If $j \neq i$ then
$$
\alpha_{\pm}(i,\ell,v,s_0,s_1) = \alpha_{\pm}(i,\ell,v_{y_j},s_0,s_1+1) + \frac{\alpha_{\pm}(i,\ell,v_0,s_0+1,s_1) + \alpha_{\pm}(i,\ell,v_1,s_0+1,s_1)}{2}.
$$
The actual algorithm in the paper is some sort of mild optimization of this idea.


Minimum pumping length of concatenation of two languages there's this small part of my homework that I just can't figure out.

Let us denote $p(L)$ as the minimum pumping length of some language $L$. I'm supposed to find two regular languages $A,B$ so that

$$
p(AB)=p(A)+p(B)
$$

But whatever I try, I can only find languages so that

$$
p(AB) < p(A)+p(B)
$$

I've been sitting at this the whole day and I'm just going in circles. Can someone please give me a hint?

For a language $L$, denote $P(L)$ as the minimum pumping length of $L$. It is implied that $P(L)\ge1$.

Proposition. Let $A,B$ be two languages with finite minimum pumping lengths. We have $P(AB)\le P(A)+P(B)-1$. Moreover, there exist regular $A,B$ such that the equality holds.

Proof. Let $w=w_Aw_b\in AB$, where $w_A\in A, w_B\in B$. Assume $|w|\ge P(A)+P(B)-1$. Then either $|w_A|\ge P(A)$ or $|w_B|\ge P(B)$; otherwise, $$|w|=|w_A|+|w_B|\le P(A)-1 + P(B)-1\lt P(A)+P(B)-1,$$
which contradicts the assumption.

Now there are two cases.

$|w_A|\ge P(A)$. Since $P(A)$ is a pumping length for $A$, $w_a\in A$ can be written as $w_a=xyz$, satisfying the following conditions:

$|y|\geq 1$
$|xy|\leq P(A)$
$\forall n\geq 0, xy^{n}z\in A$

Hence, $w$ can be written as $w=xyz_B$, where $z_B=zw_B$, satisfying the following conditions:

$|y|\geq 1$
$|xy|\leq P(A) + P(B)-1$ (since $P(B)\ge1$)
$\forall n\geq 0, xy^{n}z_B=(xy^nz)w_B\in AB$.

That is, $w$ can be pumped with pumping length $P(A)+P(B)-1$.
$|w_B|\ge P(B)$. This case is similar to the case above.

Combining the two cases, we have proved $P(A)+P(B)-1$ is a pumping length for $AB$.

Let $A=\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{n-1}, \beta^n, \beta^{2n}, \beta^{3n}, \cdots, \}$, which is a regular language of minimal pumping length $n$.  Let $B=\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{m-1}, \beta^m, \beta^{2m}, \beta^{3m}, \cdots\}$, which is a regular language of minimal pumping length $m$. Since $\alpha^{n-1}\alpha^{m-1}$, which is a word in $AB$ of length $n+m-2$, cannot be pumped, $AB$ is a regular language of minimal pumping length $n+m-1$.


is any faster algorithm to calculate this series? ∑∑ai/aj I am wondering if it is possible to calculate the following double sum, where $a_1,\ldots,a_n$ are positive integers, in time faster than the trivial $O(n^2)$:
$$
\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{a_i}{a_j} \right\rfloor.
$$
For example, if $a_1 = 1, a_2 = 2, a_3 = 3$ then the sum is $9$.

Assuming that your numbers $a_i$ are small enough and $n$ is large enough, the following algorithm may work better in practice.
For each $a_i$, for all possible division results $d_j$, find minimum $v_j$ such that $\lfloor \frac {a_i} {v_j} \rfloor = d_j$. The idea is the following:

There can't be too many different $d_j$. E.g. for $a=10^9$ there are about $6 \cdot 10^4$ possible $d_j$. It's possible to show that there are $O(\sqrt{a})$ possible values of $d_j$ (about $2 \sqrt a$). Note that it's possible to iterate all possible $d_j$'s in time linear of their amount.

All numbers between neighboring $v_j$'s give the same result after division.

Therefore, the algorithm is the following:

Sort $a_1, \ldots, a_n$
For each $a_i$, find all possible $\{(d_j, v_j)\}$ as described above. Using binary search on array of $a_i$, for all $j$ find the number of $a_i$ lying between $v_j$ and $v_{j+1}$. Division by any of them results in $d_j$.

P.S.: This algorithm can take exponential time (since it's polynomial on the numbers themselves), but it can have a guaranteed $O(n^2 \log n)$ time when we ignore $d_j$ which can't be achieved: when we've found the last number $a_k$ which lies between $v_j$ and $v_{j+1}$, we select the next $d$ to consider based on $a_{k+1}$. Additional $\log n$ comes from the binary search.


Unique number to represent a combination of 5 numbers 1-39 This is a related question poker hand representation and I got a great accepted answer. The problem can be reduced to a virtual 39 card deck that from what I can tell is 16 bits.

I have 5 numbers 1-39 with none repeating. I need to uniquely identity those 5 numbers with the smallest possible number and not order dependent on the 5.  I am pretty sure the number is 2^16. From the accepted answer to the link you go 01, 10, 100, ... and then start folding back.  Then use an XOR on that matrix.  I tried but I cannot figure out when / how to start folding back.

What is the matrix / array?

This can't be encoded into 16 bits.  The number of such hands is ${39 \choose 5} = 575757$ (is that a pretty number or what?), and $\lg(575757) \approx 19.1$, so a 5-card hand be encoded into 20 bits, but it can't be encoded in 16 bits.

You can use the methods shown there (1, 2) to construct an encoding into 20 bits.  Alternatively, if you want a coding-theory-based answer, analogous to Yuval's answer there (the accepted answer), you'll need to find a linear code of appropriate parameters.  16 bits isn't enough.  Even 20 bits won't be enough; you'll need a slightly longer encoding, as the coding-theory-based solutions are fast to compute but yield an encoding that is slightly-longer-than-optimal.


Branch & Bound: Avoiding equivalent solutions There is a certain family of typical branch & bound problems in which we have to put $n$ objects into $m$ indistinguishable bags.

Usually solutions are represented by $n$-size vectors in which $V[i]$ means that the $i$-th element is in the $V[i]$-th bag.

Is there a way to avoid generating equivalent solutions without performing an $\mathcal{O}(n)$ time check once the potentially equivalent solution has been built?

I was trying to do something similar as when avoiding circular permutations, but no adaptations seems to work.

You could impose a canonical ordering on the bags.

For instance, in each bag find the lowest-numbered item in that bag, and  imagine labelling the bag with that number.  Now add the additional constraint that to be a valid solution, the bags must be in sorted order according to their label.  In other words, the label on the $i$th bag must be less than the label on the $i+1$st bag.

If you can express this constraint within your system, it ensures that each equivalent solution will be generated only once.


What is the triangulation angle? I start to work in the field of computer vision and read a paper in which the author states "When suitable correspondences between salient image structures have been established, the 3D uncerntainty of these structures mainly depends on the triangulation angle between the oberservations and the 3D structures". So what is the triangulation angle? In the wikipedia article on triangulation (http://en.wikipedia.org/wiki/Triangulation_%28computer_vision%29) there is a really nice pictures that explains the triangulation but which angle in this picture is the trinagulation angle?

The angle between the projections of the target point, along the host surfaces, is technically called Triangulation Angle.


Mean geodesic distance between two points in Delaunay Graph If I have a Delaunay Graph, what is the mean geodesic distance between two randomly chosen nodes.
I know that in a small world network, it is in O(log(N)), with N being the number of nodes.

Thank you!

As you have probably come to the right conclusion by now, for a Delaunay graph, the magnitude of the mean distance between two randomly chosen nodes depends on the particular configuration of the points.

Here is one extreme example. Let each one of the six sided of the triangulated honeycomb have $n$ edges. We will have $3n(n+1)+1$ points. The average distance between two nodes is $\Theta(n)$, which is $\Theta(\sqrt {3n(n+1)+1})$.

We can also consider the row of triangles just above the middle line in that honeycomb as a separate graph. It has $4n+1$ nodes. The average distance between two nodes is $\Theta(n)=\Theta(4n+1)$.

It is intuitive clear that for any given Delaunay graph of $N$ points, the mean distance between two nodes is between $\Theta(\sqrt{N})$ and $\Theta(N)$, which grows much faster than $O(\log(N))$, the mean distance between two nodes in a small-world network. That is one evidence why we call that kind of network small world!


Vertex Cover approximation algorithm I have an algorithm that solves the Vertex Cover problem.   The algorithm is

  Repeat while there is an edge:

  Arbitrarily pick an uncovered edge $e = uv$ and add $u$ and $v$ to the solution.  Delete $u$ and $v$ from the graph.

I know this strategy is a 2-approximation to Vertex Cover and that its worst example is the complete bipartite graph $K_{n,n}$.  In this graph, the algorithm will return a vertex cover of size $2n$ whereas the optimal solution is of size $n$.

Question: Does there exist a graph with Minimum Vertex Cover of size 10 where this strategy finds a minimum vertex cover?

You ask for a graph where your (nondeterministic) algorithm gives the optimal solution even in the worst case. We're looking for a set of vertices that cover all edges. The difficulty with your algorithm is not only that it could pick the edges in an "inconvenient" order, but also that it adds both vertices belonging to the edge, which is suboptimal in most cases (since adding one of the vertices already covers the edge).

An example where your algorithm does always find the optimal solution of size 10, is the graph below. If you meant the problem the other way around (cover all vertices), the same graph applies.


Problem A is polynomially reducible to problem B... what can we say about A and B? This is a question on a practice final.

  Problem A is polynomially reducible to problem B. Which of the following
  statements is correct?

  I. If problem A is solvable in a polynomial time then problem B is solvable in polynomial time.

  II. If problem A is NP-complete then problem B is NP-complete.

  III. If problem A is NP-hard then problem B is NP-hard

  a) I

  b) II

  c) III

  d) I and II

  e) I, II and III

We are told that the solution is (c), but there's no explanation why on the key. I have tried to figure this out, and the only conclusion I've come to is:

(I) cannot be true because if A is polynomially reducible to B, this implies B is at least as hard as A. (Not sure if this is a correct conclusion, so feedback on this would be appreciated.)

This is the first time I'm learning about the notion of hardness, so I don't understand most of the technical explanations I've found. Any clarifications on why II is incorrect, and why III is correct would be appreciated.

Self study I've done includes reading multiple StackExchange posts, multiple Wiki pages, and the corresponding section in the Cormen book. I just personally understand concepts better if I see different explanations.

Your intuition about "relative hardness" is correct, the underlying mathematics is why III. is true. However your justification about I. is a little off (not wrong, but the reasoning is possibly not accurate).

It might help to think about reductions in these terms (everything I'll talk about here will be polynomial time, so I will leave that out just so I don't have to type it over and over); a reduction (from A to B) is just an algorithm that turns an instance of A into an instance of B, with the special property that if we know/can figure out/can use magic to find out the answer to the instance of B, we know the answer to the original instance of A. This gives us a way of solving problem A if we already know how to solve B.

This is why we say things like "B is at least as hard as A", because any algorithm for B immediately gives an algorithm for A. To flip it around, if we knew B was "easy", then A must also be "easy" (for some notion of "easy").

Notice that this relationship is not symmetric - knowing how to solve A doesn't tell us anything about how to solve B (given that all we have is the single reduction). If we had more information, maybe it would, maybe it wouldn't, but from the reduction alone we get nothing in that direction.

So then for I., we know we can turn an A into a B, and that we can solve an A, but this tells us nothing about B.

For III., we already know that A is hard (NP-hard!), and the reduction tells us that B is at least as hard as A, so B must also be NP-hard. The formal truth behind this intuition comes from the definition of NP-hardness. Remember that A being NP-hard means every single problem in NP has a reduction to A. We also know that A reduces to B, so how does this show B is NP-hard? We can compose the reductions. For every C in NP, we can reduce every instance of it to an instance of A, then take that instance of A and use our new reduction to turn it into an instance of B (as an exercise you might want to think about why we still know this is all polynomial time etc.). So this gives us a way of turning every problem C in NP into problem B, which is the definition of NP-hardness.

Coming back to II., this one again relies on definitions. NP-completeness is NP-hardness, plus the additional property that the problem is in NP. So saying problem A is NP-complete means problem A is NP-hard and A is in NP. We've just seen that the reduction to B tells us that B is NP-hard, so we have that part, but just like part I., where A being in P didn't tell us whether B was in P or not, A being in NP doesn't tell us whether B is in NP or not. It might be, but the reduction doesn't give us this information.


Would using mouse position in the below scenario generate true random numbers? I'm having trouble wrapping my head around random number generation so I figure it would be better to ask now, rather than screw up later.

Let's say I want to write a function that generates a random lucky number from 0-9 when the user clicks on a button.

I'm thinking of using the last digit of the multiple of the x and y coordinates of the click position as the output.

Assuming that the user have no intention of gaming the output, would this be true randomness because there's no way for a 3rd party to predict where on the button the user will click next?

Usually, mouse click position is highly correlated. Just as an example, take a look to a typical mouse interaction with a browser:

So, the use of raw mouse click positions without pre-whitening is discouraged.


Data Compression: Which one is Better "Compress before Encrypt" or "Encrypt before Compression" Which one is better approach do data compression before encrypting it  or Encrypt data before compression ? I think it is biased towards the application requirement.  Please share your views.

Compressing encrypted data doesn't work.  Encrypted data looks pseudorandom, therefore if you try to compress it, you'll find that the compression is ineffective.

Try it.  You'll see.  It's a very simple experiment -- give it a try.


Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence? Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong.

I have a puzzle: Given two numbers which define a set of continuous counting numbers of the same number of digits, between roughly 5 and 12 digits long (IE 50000 and 60000, 32325600000 and 32399999999), what's the fastest and most efficient way to condense this down to a set of prefixes which "contain" all permutations of subsequent digits?

The approach we've been using is a hybrid of treating these as numbers and character strings. First remove any pairs of matched 0's and 9's at the end of the start/end. Second create the full sequence copied to two columns, where the second column is always a substring with the rightmost digit removed relative to the first column. From there I can recursively count how many times any given one-digit-shorter substring occurs, keep the items where N-count<10, and where N-count>=10 remove another digit from both columns and repeat.

What I'm wondering is if there's a quicker and more efficient way to do this. String operations instead of math was an obvious quick fix, but the general approach still relies on recursively grouping and chopping off characters. I've considered making a full series of Prefix and N-count columns going back to the highest digit but at least instinctively that feels like it would be less efficient than operating recursively on a decreasing pool of numbers.

IE
Input:
Start=50000000
End=55399999

which becomes
Start=500
End=553

Cycle one creates two sequence columns like this:

String   Prefix     N-Count
500        50          10
501        50          10
etc..
510        51          10
etc..
550        55          6
551        55          6
552        55          6
553        55          6

Cycle two keeps everything where N-count<10 the same, but reduces the rest by 1
digit each and recalculates N-count (while getting rid of duplicates).

String   Prefix     N-Count
50        5          5
51        5          5
52        5          5
53        5          5
54        5          5
550       55         4
551       55         4
552       55         4
553       55         4

Output:  50,51,52,53,54,55,550,551,552,553
```

Suppose the input is $a,b$, two $n$-digit long numbers. We allow leading zeroes (we will see in a moment why). Let $c$ be the longest common prefix of $a,b$, and let $a=cA$, $b=cB$.

If $A = 0^{n-|c|}$ and $B = 9^{n-|c|}$ then we simply output $c$ (this includes the case $|c|=n$).

Otherwise, let $d_A$ be the first digit of $A$, and let $d_B$ be the first digit of $B$.

Recursively find a solution for the ranges $[A,d_A 9^{|A|-1}]$ and $[d_B 0^{|B|-1},B]$, and prefix $c$ to everything. Also, add $c(d_A+1),\ldots,c(d_B-1)$.

Here is an unoptimized python implementation:

def prefixes(a,b,C=''):
     n, m = len(a), max(i for i in range(len(a)+1) if a[:i] == b[:i])
     c, A, B = C+a[:m], a[m:], b[m:]
     if A == '0'*len(A) and B == '9'*len(B):
         yield c
     else:
         yield from prefixes(A[1:],'9'*(len(A)-1),c+A[0])
         for i in range(int(A[0])+1,int(B[0])):
             yield f'{c}{i}'
         yield from prefixes('0'*(len(B)-1),B[1:],c+B[0])

For example, if you run list(prefixes('50000000','55399999')) then you get the following output:
['50', '51', '52', '53', '54', '550', '551', '552', '553']


Space complexity of a variant of st-connectivity Consider a variant of STCON, called 2STCON, which is defined like this:
$$2STCON = \{\langle G,u,v \rangle \} \mid \text{$G$ is a graph with } \mathit{two} \text{ paths from $u$ to $v$} \} $$
This means the only difference to the "normal" STCON is that there are two paths instead of just one between $u$ and $v$.
I need to show that 2STCON belongs to NL.
What is the  best way to approach this problem?

The usual proof that STCON is in NL works as follows: you guess a path from $u$ to $v$, and verify it step by step.
A very similar proof works for 2STCON: you guess two paths from $u$ to $v$, and verify them step by step. As you verify them, you also verify that they are different: either the length is different, or the $i$-th vertex is different, for some $i$.


Find the intersection point between two sorted arrays with unknown lengths in lesser than O(n) Two sorted arrays of positive integers, X[] and Y[] are given.But, the array sizes are unknown to us. We may assume that accessing any index beyond the last element of the array returns -1. The elements in each array are distinct but the two arrays may have common elements. An intersection point between the two arrays is an element common to both the arrays, i.e., p ( p>0 ) be an intersection point if there exists i,j such that X[i]=Y[j]=p
Given a positive integer q, how can we design an algorithm ( in pseudocode ) to check if q is an intersection point between X and Y in strictly less than O(n) time complexity.

 I proceeded by thinking of applying binary search on both the arrays X and Y, since they are sorted and trying to find if q exists in both of them. But not knowing the lengths leads me astray.

Could anyone please help me with this ?

We need to first find the length of array in long time as it is not given.

Start with length as 1 and increase it as multiple of 2.
Check whether element at length-1 position is positive or not.
If so repeat steps 1 and 2.
If not return the index position it will be the maximum size of the array. As it is mentioned beyond the maximum position element value is negative.
Once the length of array is known simple binary search alto will be applied to search element and it will be searched in both the array and intersection point will be determined.