Efficiently finding "unfounded edges" in a strongly connected graph While implementing a debugger I've encountered a problem I need to solve concerning dependency graphs. I've simplified it as follows:

Consider a strongly connected graph G = (V,E).

We define a subset of vertices S ⊆ V as source vertices.
We call an edge e = (a,b) unfounded if there is no simple path from any source vertex to b that includes e. In other words, all paths from a source vertex that include edge e, must include vertex b at least twice.

The problem:

Find all unfounded edges in G.

There are some obvious ways to solve this inefficiently (e.g. a depth-first traversal for each edge in G), but I was wondering if there was any O(|E|) approach. I've been struggling with this for a while and I keep "almost" solving it in linear time. Perhaps that's impossible? I have no idea what the lower bound on efficiency is, and I was hoping some readers here could help me discover some efficient approaches.

An illustrative example is a simple 3-cycle.  Pick any one vertex as the source vertex. The edge coming into the source vertex is unfounded.

I believe that computing graph dominators will solve your problem. This can be done in $O(|E|\log |V|)$ time (or even faster, though they describe the faster algorithm as "sophisticated") using a 1979 algorithm by Lengauer and Tarjan, which is (at least currently) described here (21 pages -- I have only read the first few pages myself).

Add a new "start" node with an out-edge to every source node, run the dominator algorithm to determine dominators for every node, and then check each edge $uv$: $uv$ is unfounded if and only if $v$ dominates $u$. (Each of these checks can be done in constant time using a lowest common ancestor (LCA) algorithm, although that may be overkill here -- for an edge $uv$, we only care about whether or not $LCA(u, v) = v$.)


Are the languages $\{w\in \{a,b\}^* : \#_a(w) > \#_b(w) \}$ and $\{w\in \{a,b\}^* : \#_a(w) \neq \#_b(w) \}$ context free? So at the beginning I was aiming at $L_{a\neq b} = \{w\in \{a,b\}^* : \#_a(w)  \neq \#_b(w) \}$. But figured out that is would be better to first deal with: $L_{a>b} = \{w\in \{a,b\}^* : \#_a(w)  > \#_b(w) \}$, due to the fact that $L_{a>b} \cup L_{b>a} = L_{a\neq b}$.

My attempts so far for $L_{a>b}$ - I proved that this language is pump-able:
Choosing $N=2$ For $z\in L$ contains only $a$s the pump it pretty basic, on the other hand words contain $b$s: $\#_b(z) > 0 \Rightarrow \#_a(z) > \#_b(z) >0  $ so $z$ must include the couple $ab$ or $ba$ as a sub string, so $ z= \gamma ab\delta \Rightarrow \gamma|a|\varepsilon|b|\delta$ is a valid splitting, and $\gamma a^ib^i\delta\in L$ because the relation between $a$'s and $b$'s appearances is preserved.

So I was hoping this language might be context free and tried to form a Grammar which generates the language, However I didn't succeed in it, due to the fact that a general word of the form: $a^{i_1}b^{j_1}a^{i_2}b^{j_2}...a^{i_n}b^{j_n}$ when $i_k,j_k \in \mathbb{N}\cup\{0\}$ satisfies $\sum i_k > \sum j_k$ and I am having hard time dealing with cases in which $i_l <j_l$ (for example $aaaababb$ when the second pair is $abb$).

I don't know whether I may proceed from my best attempt, yet, in case  $ z = a^{i_1}b^{j_1}a^{i_2}b^{j_2}...a^{i_n}b^{j_n}$ satisfies $i_k > j_k \forall k\in [n]$ The grammar $A\rightarrow a | AA|AAB|BAA , B\rightarrow b$ with A as the initial term, should work (I didn't formally prove it so I might be wrong).

I also tried to work with closure properties but couldn't even find an idea to start with...

Here is a hint. Given a word in $L_{a\gt b}$, if you remove $ab$ or $ba$ from it repeatedly until you cannot any more, what kind of word will you end up with?

Here is an almost complete answer.

   The language $L_{a\gt b}$ is similar to the language where the number of "a"s is equal to the number of "b"s, except there can be arbitrary number of extra "a"s at any position and there must be at least one extra "a" somewhere.

 Here is its context-free grammar:
 $\quad S \to TaT$
 $\quad T \to TT|bTa|aTb|aT|\epsilon$

 As a part of a proof that the above grammar generates $L_{a\gt b}$, let us show that $T$ stands for a word that has no less "a"s than "b"s. $T$ can only generate such kind of word, since whenever a "b" is included, an "a" is included. Now suppose $Z$ is such a word that is not empty. There are two cases.

 If $Z$ starts with a "b", let us walk through the symbols in $Z$ from its beginning, counting how many "a"s and how many "b"s along the way. So initially we have zero "a" and one "b". At some point of this walk, we will count an equal number of "a"s and "b"s since $Z$ has no less "a"s than "b"s. That means $Z=bXaY$ for some words $X$ and $Y$, where $bXa$ has the same number of "a"s and "b"s and where $Y$, the remaining part, must have no less "a"s than "b"s. Note that both $X$ and $Y$ are shorter than $Z$.

 The other case is when $Z$ starts with an "a", that is, $Z=aW$ for some word $W$. If $W$ has no less than "a"s than "b"s, we are in good condition since $W$ is shorter than $Z$. Otherwise, $W$ has (exactly one) less "a"s than "b"s. There are two subcases. If $W$ ends with a "b", then $Z=aUb$, where $U$ has no less "a"s than "b"s and $U$ is shorter than $Z$. Otherwise, $W$ ends with an "a". Now let us walking through symbols of $W$ from its end, counting the number of "a"s and the number of "b"s along the way. At some point of our walk, we will count an equal number of "a"s and "b"s. That means $W=UV$ for some word $V$ that has the same number of "a"s and "b"s. So $Z=aUV$, where $aU$ must have no less "a"s than "b"s. Note that both $U$ and $V$ are shorter than $Z$.

 The preceding two paragraphs shows that $Z$ must comes from two or one shorter word that also has no less "a"s than "b"s by the production rule of $T$.  Since $T$ can be replaced by the empty word $\epsilon$, we see that $T$ can generate all words that has no less "a"s than "b"s.

Exercise
Is the language $L_{a\gt b\gt c} = \{w\in \{a,b,c\}^* \vert \#_a(w)  > \#_b(w) > \#_c(w)\}$ context free?


Dijkstra's algorithm on huge graphs I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to have the graph in memory, so the graph is stored on disk in a database.

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

Fetching the adjacency list of each vertex visited would require about 1,500 database queries per 10,000 nodes according to my statistical data, so that clearly is not how they do it. That would be way too slow.

How do they do it? I am trying to implement it myself.

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

You can use a DB, a custom file format to be read from disc and an in-memory setting.

But from my experience using a DB is roughly 5 to 10 times slower and a lot more memory intense than writing your own file format based on a 'simple' linked list format.

The good thing is there are several software frameworks using OSM which are open source so you can look right into the code e.g. see here. In the GraphHopper open source routing engine it is very easy to switch from a memory mapped setting (disc based) to the in-memory setting - both using the same format. The "mmap" setting even allows usage on memory restricted mobile devices and the latter performs a lot faster if you have the necessary RAM e.g. on a server. E.g. for a world wide graph (>100mio nodes) you then need around 8-10gb RAM, plus lot of more RAM if you want to speed up everything further e.g. with Contraction Hierarchies - roughly 5-8gb more for every vehicle you want.

The format is very simplistic and basically stores only the data you need with a few tricks to make it compact. Read more about it here. Disclaimer: I'm the author of GraphHopper.

Regarding the other answers:

  Dijkstras algorithm while applicable is regarded as not optimal for this problem

The 'normal' Dijkstra can perform very reasonable (<1s for country-wide queries like your 3mio nodes example) and is optimal in the 'theory sense' but needs a bit tuning to get fast in production scenarios. And techniques like Contraction Hierachies use a bidirectional modification of it and perform very well.

  road networks are hierarchical and planar.

road networks are hierarchical for car only and not planar (bridges, tunnels, ...)


Universal Quantifiers in QBFs I've been looking into reductions to/from the TQBF language and have managed to get stuck on something that is almost certainly not true (or, if it is true I'm missing a significant computational cost associated with it) with respect to simplifying TQBF instances.
For the sake of simplicity, let's restrict attention to TQBF instances in prenex normal form and CNF with no free variables. My hypothesis (which I strongly suspect is wrong, but have been unable to find a counter-example) is that such a TQBF is satisfiable if and only if the TQBF that results from removing all instances of universally quantified variables from the sentence is satisfiable. For example, take the following instance:
$\exists a \forall b \exists c \forall d$ $\psi(a,b,c,d)$
$\psi(a,b,c,d) = (\neg a \vee b \vee c)\wedge (\neg b \vee \neg c \vee d)\wedge (a \vee c \vee \neg d)$
First, I contend that this instance is not satisfiable (easily verifiable by hand). If we apply the method I describe above, we get the following "core":
$\exists a \exists c$ $\phi(a,c)$,
$\phi (a,c) = (\neg a \vee c)\wedge (\neg c) \wedge (a \vee c)$
which is clearly not satisfiable. If instead of this example we look at this:
$\exists a \forall b \exists c \forall d$ $\psi(a,b,c,d)$
$\psi(a,b,c,d) = (\neg a \vee b \vee \neg c)\wedge (\neg b \vee c \vee d)\wedge (a \vee c \vee \neg d)$
which clearly is satisfiable (set c to true, a to false) and which has a "core" of
$\exists a \exists c$ $\phi(a,c)$,
$\phi (a,c) = (\neg a \vee \neg c)\wedge  (c) \wedge (a \vee c)$
that is also satisfiable with the same variable settings.
If this method always works, that would seem to imply that there is a reduction from TQBF to SAT in time linear in the number of universal quantifiers and the number of occurrences of the universally quantified variables in the formula, showing that TQBF is NP-Complete (it is already known to be PSPACE-Complete and thus NP-Hard, so if it is in NP it is NP-Complete) and furthermore that NP=PSPACE. I would be utterly stunned if this is the case, but I have been unable to find a counterexample (or a missing computational cost in the reduction that makes it not polynomial time). What am I missing?

Your intuition was right.  It doesn't work.  Here is a counterexample.
Consider $\forall a \exists b  \varphi(a,b)$ where $\varphi(a,b) = (a \lor \neg b) \land (\neg a \lor b)$.  This statement evaluates to true.
However, if we remove $a$ following your procedure, we get $\exists b \psi(b)$ where $\psi(b) = ((\neg b) \land (b))$; and that statement evaluates to false.
One way to understand why your method doesn't work is that $\forall a \exists b  \varphi(a,b)$ isn't equivalent to $\exists b \forall a  \varphi(a,b)$.  At most your method might work if all of the $\forall$'s are on the inside, i.e., for a sentence of the form $\exists \cdots \exists \forall \cdots \forall$, but not for any other pattern of $\exists$ and $\forall$.


computability - decidability of a prefix language For any language $L$ over $\{0,1\}^*$, a language $L'$ can be defined as $\{ a | ab \in L \text{ for some } b \in \{0,1\}^* \}$.

If $L$ is decidable, is $L'$ decidable?

I think that $L'$ should be decidable because we can create a Turing machine for $L'$ that will run the decider for $L$ on the input $w$ for $L'$, accept if it accepts, and otherwise will enumerate all the possible strings $b$ and run $wb$ on $L$. Does that make sense?

Pick some self-terminating encoding of Turing machines. (That means that the encoding of one Turing machine is never a prefix of the encoding of another.) Consider the language $L$ consisting of strings $Mn$, where $M$ is an encoded Turing machine, $n$ is interpreted as a number, and $M$ halts within $n$ steps (on the empty input).

Does that answer your question?


Prove or disprove that $NL$ is closed under polynomial many-one reductions If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$.
  Prove that the above claim is correct, incorrect, or equivalent to an open question.

Trying to solve this, I was pretty sure that the statement is either incorrect, or at least equivalent to an open question. My reasoning was that the statement is correct if the reduction is promised to be a log-space reduction (uses only $log \ n$ space). Removing this demand seems to be too much, but I wasn't able to prove this.

I was then told that this statement is equivalent to the open question $NL = P$. I thought of this, and tried proving that if the statement is correct, then one can define a Karp reduction from any $L \in P$ to a language in $NL$, therefore proving $L \in NL$ and $P \subseteq NL$. However I couldn't find such a reduction.
The only reduction I could think of that could help would be to transform the operations of a deterministic polynomial Turing machine $M_L$ to a configurations graph (a directed graph with an edge $(u,v)$ iff there exist two consecutive configurations $u, v$ in $M_L$. However, this reduction would take exponential $2^{p(n)}$ time, and not polynomial.

Any contribution would be appreciated.

Let's prove the two directions separately. Suppose first that $\mathsf{NL}=\mathsf{P}$. In order to prove the statement, suppose that $B \in \mathsf{NL}$ and that there is a polytime many-one reduction from $A$ to $B$. Since $\mathsf{P}$ is closed under polytime many-one reductions and $B \in \mathsf{NL} = \mathsf{P}$, clearly $A \in \mathsf{P} = \mathsf{NL}$, proving the statement.

Suppose next that the statement is correct. Let $B$ be any non-trivial language in $\mathsf{NL}$ (for example, $B = \{\epsilon\}$), and let $A \in \mathsf{P}$ be arbitrary. Since $A \in \mathsf{P}$ there is a polytime function $f$ computing it. We can easily modify $f$ to a polytime reduction from $A$ to $B$ by fixing some YES instance and NO instance in $B$ (here we need that $B$ be non-trivial). The statement implies that $A \in \mathsf{NL}$. Since $A$ was arbitrary, we deduce that $\mathsf{P} \subseteq \mathsf{NL}$ and so $\mathsf{NL} = \mathsf{P}$.


Proof: Kolmogorov complexity of string concatenation Does there exist a universal constant $c$ such that for any strings $x, y$, we have: $$K(xy)\leq K(x) + K(y) + c$$
where $K(\cdot)$ denotes the Kolmogorov Complexity of a binary string and $xy$ means the concatenation of $x$ and $y$? I know the answer to this problem is no but I am seeking a proof for this, any hint?

Update: for reference, this is stated at the top of page 266 in Sipser's famous book "Introduction to the Theory of Computation", third edition, and is listed as Problem 6.19 in the book. I've tried to prove it but didn't succeed, just curious to know what proof technique should be used in order to prove it.

Kolmogorov complexity = length of shortest program to generate a string. Take the program generating x, add the fixed size code that makes it continue with a second program instead of halting, then add the second program generating y.


Is P the set of all algorithms whose run-time is $O\left( n^{ O \left( 1 \right) }\right)$? I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some proposition $P \left( x \right)$, and then iterate over the universe of objects, applying $P \left( x \right)$ to each; keep the objects for which $P \left( x \right)$ is true; exclude each object for which $P \left( x \right)$ is false.

So, when we define a class of objects called $\mathbb{P}$ (as in P vs NP), I really need to see a formal definition of the proposition used to build that class--as well as a formal definition of the universe of objects we're starting with.

Defining the Universe of Discourse, $\mathbb{U}$

My understanding is that, for the question of $\mathbb{P}$ vs $\mathbb{NP}$, our universe of discourse is all decision problems that are satisfiable. Namely, problems that can be implemented in boolean logic, return a boolean result, and that someone somewhere at some point has found a finite sequence of inputs that cause the implementation to return $TRUE$.

In spite of Russell's Paradox, let us define our universe of discourse as the set $\mathbb{U}$.

Defining $\mathbb{P}$

$\mathbb{P}$ is a subset of $\mathbb{U}$. Namely, it is the set of all objects in $\mathbb{U}$ for which the following proposition returns $TRUE$:

  This object can be written as a decision problem that returns a boolean value--and that decision problem takes at most $O \left( n^{O \left( 1 \right)} \right)$ time.

That is, given some implementation of a decision problem in $\mathbb{U}$, if that implementation takes at most polynomial time, we can include that implementation in $\mathbb{P}$.

The Point I Need Clarified

Are we really using $O \left( n^{O \left( 1 \right)} \right)$ to define $\mathbb{P}$? Or are we using $\theta \left( n^{O \left( 1 \right)} \right)$? $O \left( n^{O \left( 1 \right)} \right)$ seems right to me, but--so often material I study from doesn't distinguish between Big-O and Big-Theta. So, I need to clarify.

For example, given the following simple, Java-like implementation of an algorithm:

function boolean isOne(int input) {
    return input == 1;
}

Should I include this algorithm in $\mathbb{P}$? It is clearly faster than polynomial time; it is constant time. So, it is $O \left( n^{O \left( 1 \right)} \right)$ but not $\theta \left( n^{O \left( 1 \right)} \right)$--as long as zero $\not\in O \left( 1 \right)$?

Should I include it in $\mathbb{P}$?

If zero $\in O \left( 1 \right)$, then is a constant time algorithm in $\theta \left( n^{O \left( 1 \right)} \right)$?

Should I include this algorithm in $\mathbb{P}$?

Yes. Since the algorithm is asymptotically bounded above by $O(n)$ the algorithm is in $\mathbb{P}$.

  If zero $\in O(1)$, . . .

Zero is in $O(1)$.

  . . . so often material I study from doesn't distinguish between Big-O and Big-Theta

big-O pertains to an asymptotic upper bound, where big-Theta pertains to an asymptotic tight bound.

The formal definition: $$f(n) \in O(g(n)) \iff \exists N_0,c\in\mathbb{R}^+ \text{ such that } n>N_0 \implies 0 \leq f(n) \leq cg(n)$$ Also, $$f(n) \in \Theta(g(n)) \iff \exists N_0, c_1, c_2 \in \mathbb{R}^+ \text{ such that } n>N_0 \implies c_1g(n)\leq f(n)\leq c_2g(n)$$

For example, $f(n) = n^2 + 3n \in O(n^3)$ and $f(n) \in O(n^2)$. But, $f(n) \not\in \Theta(n^3)$, yet $f(n) \in \Theta(n^2)$.

We can't use $\Theta(n^{O(1)})$ to describe $\mathbb{P}$, as $O(lg(n))$ isn't in $\Theta(n^{O(1)})$, but is in $O(n^{O(1)})$ (and is in $\mathbb{P}$).


Doubt on Token in Compiler Design Say i have code snippet like -->

m -= n;

is minus and assignment considered as a single token or they will be considered as different token?

So the total token count will be 4 or 5?

In the C language you cant insert space between '-' and '=', so you are better to implement '-=' as the single lexeme.


Cost of computational representation in PAC-learning definition I'm currently reading Foundations of Machine Learning by M. Mohri, A. Rostamizadeh, A. Talwalkar and according to their definition a concept class $C$ is said to be PAC-learnable if

$$Pr_{S \sim D^m}[R(h_s)\leq\varepsilon] \geq 1-\delta$$

holds for any sample size $m \geq poly(1/\varepsilon,1/\delta,n,\mathrm{size}(c))$.

I have problems understanding the definition of the parameters $n$ and $\mathrm{size}(c)$. The book defines them as follows:

  We denote by $\mathcal{O}(n)$ an upper bound on the cost of the computational representation of any element $x \in \mathcal{X}$ (the input space) and by $\mathrm{size}(c)$ the maximal cost of the computational representation of $c \in C$.

A general answer would be greatly appreciated but I also have two examples I would like to understand in detail:

Axis-aligned rectangles: Each rectangle can be represented by its corners which are points in $\mathbb{R}^2$, so the computational cost is constant. Therefore, $poly$ is actually a polynomial in $1/\varepsilon$ and $1/\delta$, correct?
Universal concept class: Consider $\mathcal{X} = \{0,1\}^n$ and let $U_n$ be the concept class formed by all subsets of $\mathcal{X}$. Here the computational cost for an element $x \in \mathcal{X}$ is $n$, so $poly$ is a polynomial in $1/\varepsilon, 1/\delta$ and $n$ … ?

Especially the second example illustrates my problem very well: Taking $n$ as an additional parameter only makes sense (imho) if one considers all concept classes $U_n$ at once, because for a fixed class $U_n$ the cost of the computational representation is again constant.

I think my problem is that I don't understand the part

  … denote by $\mathcal{O}(n)$ an upper bound on the cost …

I assume that this is big O notation, but how can we say that $\mathcal{O}(n)$ is an upper bound on the cost?
And why can we not say that it is constant in the second example?

I found a satisfactory answer in chapter 1.2.2 of "An Introduction to Computational Learning Theory" by Michael J. Kearns and Umesh V. Vazirani.

Basically they consider for each natural number $n$ a concept class $\mathcal{C}_n$ over $\mathcal{X}_n$ (where $\mathcal{X}_n$ is either $\{0,1\}^n$ or $\mathbb{R}^n$), and let $\mathcal{C} = \bigcup_{n \geq 1} \mathcal{C}_n$ and $\mathcal{X} = \bigcup_{n \geq 1} \mathcal{X}_n$. So it is indeed necessary to look at all concept classes at once in order to make sense of the parameters $n$ and $\mathrm{size}(c)$ in the polynomial that gives a lower bound of the required sample size.

In the cases $\mathcal{X}_n = \{0,1\}^n$ or $\mathbb{R}^n$ it is also clear that the cost of computational representation is in $\mathcal{O}(n)$.

All this makes sense in any setting that works for arbitrary $n$, e.g. learning axis-aligned rectangles (or $n$-dimensional boxes) can (in a natural way) be generalized to $\mathbb{R}^n$ and the universal concept class $U_n$ is obviously another example.


Worst simultaneous blowup when converting to CNF and DNF I know that converting between CNF and DNF produces an exponential blowup in size, but I would like to know which is the bound in size for a converted formula when one can choose between any of the two normal forms. Or, stated otherwise, given the predicate $p$, how to find:

$$
\rho = \max \min \left\{\alpha, \beta\right\}
$$

where

$$
\alpha = \mathcal{O}(\text{CNF}(p))
$$

$$
\beta = \mathcal{O}(\text{DNF}(p))
$$

You haven't explained how you measure the size of a CNF/DNF – two common options are number of clauses/terms and total size of the clauses/terms.

The worst example is parity. Any CNF/DNF for parity must contain $2^{n-1}$ terms of size $n$. In contrast, this answer on cstheory shows that every CNF/DNF contains at most $2^{n-1}$ terms.

In the monotone case, the worst example is Majority. Majority has $\binom{n}{\lfloor n/2 \rfloor}$ many minterms/maxterms (for odd $n$), each of size $\lceil n/2 \rceil$. Since the set of minterms/maxterms is an antichain, by Sperner's theorem it contains at most $\binom{n}{\lceil n/2 \rceil}$ many minterms/maxterms. Moreover, the LYM inequality easily implies that the maximum total size of sets in an antichain is $\lceil n/2 \rceil \binom{n}{\lceil n/2 \rceil}$, exactly matching the performance of Majority.


Lexical analysis and reserved words My book says lexical analysis detects reserved words.

How can lexical analysis detect whether we are using reserved words in incorrect places ?

For eg :- while(a>0) and int while = 5.

How can lexical anaylsis differentiate the usage of while in both the above examples based on the context?

Briefly, lexical analyzer reads source code character by character and generates tokens. It does not care about in what order tokens are generated. Relationship between tokens are checked by syntax analyzer and specified by a context free grammar. Let me give you a simple example. Consider the following piece of code

 int while = 5

Lexical analyzer emmits the following tokens:

KEYWORD (INT)
KEYWORD (WHILE)
ASSIGN (=)
NUMBER (5)

Then then syntax analyzer checks these tokens, detects (based on the corresponding CFG) that the keyword WHILE cannot be lvalue, and reports the syntax error. In fact the syntax analyzer expects IDENTIFIER after the token KEYWORD (INT).


Algorithm for finding best match between two database rows Let's say we have a database with a given table named food. The food table has many columns but we are interested in only 3 of them:

buyorsell, which specifies if the food is for selling or buying.
amount, which is the amount of food to be bought or sold.
isVegan, which is set true if the food is vegan.

The goal is to find the best match between 2 rows. The best match should satisfy the following rules:

Both rows have the same value for 'isVegan'
One row should be buy/sell and the other row must be the opposite
Both amounts must be equal

The table will have millions of rows and the table is changing rapidly.

What is the right algorithm in matters of speed and resource usage for this matching problem?

Assuming we're talking about a relational database, a straightforward query would be to do a theta-join on two copies of the food relation, renamed $a$ and $b$, with the condition
$$
\theta = (a.isvegan)\land\neg(a.buyorsell=b.buyorsell)\land(a.amount=b.amount)
$$
Without knowing the internal workings of the DB engine, your question about the "right" algorithm to use is impossible to answer. For instance, does the engine use, say, merge join or hash join to answer the query; is the table sorted by some attribute, do you have indexes to help you, if so how are they implemented?


Why is this verifier for primality wrong? We are provided with the following verifier of primality:

Verifier for prime

Input: integer n ≥ 1
       integer d

if 1 < d < n and d divides exactly n then
    return ’no’
else
    return ’yes’

But the answer is that it is wrong:

  Note that in order to be a verifier it is required that for every n, n
  is a positive instance (that is, n is a prime) if and only if there
  exists one d such that the verifier with input n and d returns ’yes’.
  However, in the algorithm for Primes we have that n is a negative
  instance if and only if there exists one d such that the verifier with
  input n and d returns ’no’.

But I do not understand this answer or why "in order to be a verifier it is required that for every n, n is a positive instance (that is, n is a prime) if and only if there exists one d such that the verifier with input n and d returns ’yes’"

Here are the semantics of a verifier for primality. The verifier gets two inputs, an integer $n$ and a witness $w$. The following two properties must hold"

Soundness: if the verifier accepts $n$ and $w$, then $n$ is prime.
Completeness: if $n$ is prime, then there is a witness $w$ such that the verifier accepts $n$ and $w$.

We also usually ask that the verifier run in polynomial time in $n$.

Your verifier isn't sound (take any odd composite $n$ and $d = 2$) but is complete.

However, if you flip the return value, you do get a verifier for compositeness:

If $d \mid n$ and $1 < d < n$ then $n$ is composite.
If $n$ is composite then there exists $d$ such that $d \mid n$ and $1 < d < n$.

The notion of a verifier is asymmetric. Your verifier works for compositeness, but not for its complement, which is primality.


Datastructure for insertion and scored extraction I have a simple program (assume a shop) that is actually just returning the $m$ most active customers from a total list of $n$ users (so $m \leq n$). I only use this program on one machine with one process, so assume no distribution of data to be necessary.

I require a data structure storing $\mathrm{userId}$ and $\mathrm{score}$, where $\mathrm{score}$ is an unsigned integer. In the beginning it's $\mathrm{score}:=0$  for all $n$ users. I can extract $m$ users beginning with the highest $\mathrm{score}$ (filling up with any other user, so the first extract just returns any $m$ users).

I have an increment(x) function that is called often. It increases $\mathrm{score}$ of the user with $\mathrm{userId} = x$ by $1$. Afterwards I want to call extract again, where the result may differ by $1$ user (the last incremented score may lead to that $\mathrm{userId}$ replacing another $\mathrm{userId}$ within the $n$ members).

At the moment my prototype uses a hashmap for the scoring and a linear min-search, so complexity for increment is $O(1)$ and for extract is $O(n\cdot m)$. I feel like there should exist a data structure where extract is $O(m)$ (min-heap maybe?) while increment is either $O(\log n )$ or even $O(1)$. Assuming $m = \log n$, this would lead to a speedup of $n$ which would be immense even for small datasets.

What data structure should I use? Is there such a data structure for the operations extract and increment(x)? And if not, is there a theoretical proof that there is none?

You can use left threaded AVL trees with score as key and hash (expected $\mathcal O(1)$ insert/delete or simple AVL, logarithmic but with value much smaller than $n$) as values to keep id's, and all the time keep the data sorted with $\mathcal O(1)$ inorder traversal and $\mathcal O(\log n)$ insert (which in case of your increment operation is one delete, one insert). Also you might want to keep the last result (which is sorted) to check whether some new id appeared and use binary search if it did.

Overall this gives $\mathcal O(m)$ extract (which cannot be better) and two $\mathcal O(\log n)$ operations per increment.


Bottom-Up Evaluation of Inherited Attributes I came across $2$ translation schemes of Syntax Directed Translation (SDT) in compilers which are as follows :

Using a top-down translation scheme, we can implement any
$L$-attributed definition based on a $LL(1)$ grammar.
Using a bottom-up translation scheme, we can also implement any
$L$-attributed definition based on a $LL(1)$ grammar (each $LL(1)$ grammar
is also an $LR(1)$ grammar).

What these $2$ Definitions actually mean ? I am not getting ..

I am well aware of $L$-attributed definition and $S$-attributed definition of SDT and top down parsing and bottom up parsing but It is just that I am unable to recollect this information and phrase it according to the definitions given above.

It would be good, if I can get one example of both definitions so, that I can phrase it meaningfully of what is said .

Using a top-down translation scheme, we can implement any $LL$-attributed definition based on $LL(1)$ grammar.
Using a bottom-up translation scheme, we can also implement any $LL$-attributed definition based on $LL(1)$ grammar (each $LL(1)$ grammar is also an $LR(1)$ grammar).  Using bottom-up translation scheme, we implement $LR$ grammar actually but since $LL(1) \subset LR(1)$ we can safely implement $LL(1)$ grammar as well.


Ternary processing instead of Binary Most of the computers available today are designed to work with binary system. It comes from the fact that information comes in two natural form, true or false.

We humans accept another form of information called "maybe" :)

I know there are ternary processing computers but not much information about them.

What is the advantages / disadvantages of designing and using ternary or higher levels of data  signals in computers?
Is it feasible?
In which domain can it be better than classic binary systems?
Can we give computers the chance to make mistakes and expect to see performance
improvements in most situations by this way? (I think performance gains can be observed if computers are not so strict about being absolutely correct)

EDIT: Are there difficulties differentiating between 3 levels of signal? Would it be too hard to keep data in memory since memory voltage is frequently released and loaded, (maybe hundreds of time a second?).

Are there difficulties differentiating between 3 levels of signal?

That's more electronic than computer science (and the issue could be different with other technology). The 2 levels signals we use are generated by putting transistors in a saturation state(*). They behave like switches and the whole technology is driven to optimize this behavior(+). Even without considering that historical skew, generating an intermediate level at a fixed value is more difficult than using saturation, will consume more power (a big part of the power is currently consumed in the transition between saturating state, you will need to stay in that mode where power leaks a lot), reduce the resistance to noise (can be reduced by increasing the supply voltage and thus the power consumption) leading to reduced fabrication yield.

(*) Historically, there has been computer working with transistor in a non saturated state. There is a speed advantage to that. Power consumption (and needs for dissipation) killed the practice.

(+) Analog circuits are made with different processes which are deemed unsuitable for large digital circuits and even small one which don't need an analog part.


How does one use the Nerode-Myhill theorem to prove that a language is regular? Showing that a language is not regular is straight-forward, because all one needs to do is find an infinite set of inputs which has an injective mapping to the set of equivalence classes which compose that language.

How does one show that the set of equivalence classes of $L$ is finite? For instance, how would one show that the simple language $L = \{s:  |s| \equiv 0 \mod 2\}$ has a finite number of equivalence classes?

I think that showing that there is a surjective mapping is not sufficient, because the image may still be of infinite size.

It is just as straightforward to show a language is regular using Nerod-Myhill theorem as to show a language is not regular using that theorem since Nerode-Myhill theorem characterizes when a language is a regular.

For example, let us take the simple language $L=\{s: |s|\equiv 0 \text{ (mod 2)}\}$. There are two equivalent classes of $L$, assuming $a$ is a letter in the alphabet.

$\left[\epsilon\right]_{\equiv_{L}}=\left\{s: |s|\equiv 0\text{ (mod 2)}\right\}$
$\left[a\right]_{\equiv_{L}}=\left\{s: |s|\equiv 1\text{ (mod 2)}\right\}$

It should be easy for you to show that the above two classes are well-defined equivalence classes of $L$. There are no other equivalence class of $L$, since every word belongs to one of two classes. If a word is of even length, it belongs to class $\left[\epsilon\right]_{\equiv_{L}}$; otherwise, it belongs to class $\left[a\right]_{\equiv_{L}}$.

Hence, there are two equivalence classes of $L$ in total. That is, the number of equivalence classes of $L$ is finite. According to the Nerode-Myhill theorem, $L$ must be regular.

  I think that showing that there is a surjective mapping is not sufficient, because the image may still be of infinite size.

I am not sure which surjective mapping you are talking about.

As you can see from the example above, it is enough to show that the union of the finitely many equivalence classes you have found contains all words. Why? If we have another equivalence class $E,$ let $w\in E$. Then $w$ must belong to $F$, one of the equivalence classes you have found. Since $E$ and $F$ share one word, they are the same equivalence class. That is, $E$ has been found.

You may want to check a few related questions and answers such as finding separating words (Nerode) and how I can find all equivalence classes by Myhill-Nerode?.


Do computers actually use carry-lookahead adders? There are plenty of details about carry lookahead adders such as Kogge-Stone, Lander-Fischer, etc. in college CS courses. They are described as "common in the industry".  However, I can't find any evidence (aside from maybe the Manchester carry chain) from recent times that they are actually used anywhere specifically. A Google search only returns pages of journals and academic research. At most, hypothetical implementations are given.

My question is, are there any specific places/implementations carry-lookahead adders are used? Or are they irrelevant to the real world?

This is a straightforward question with a very complex answer.

First off, some background.

Real-world VLSI design is an extremely technical field which features a constantly-changing balance of tradeoffs. The time that a circuit takes to calculate an answer is rarely the only important factor. There's also power draw and physical area, plus a bunch of factors which reveal that the circuits you're designing are actually analogue (e.g. wire resistance, parasitic capacitance). All of these are important in a real circuit and may impact which design is chosen.

Secondly, you have to consider the entire life-cycle of a project. An adder which is appropriate for a VLSI realisation may not be appropriate for an FPGA realisation. If the design is going to go through a phase being tested on an FPGA... you get the picture.

Thirdly, not every adder is made equal. On a typical CPU, there are lots of adders hanging around which do different tasks; there are probably several integer ALUs, a floating point mantissa adder, an adder which does address calculation, an adder which calculates branch targets, and so on. That's not counting the carry-save adders that you find in modern multiplication units. Each has its own peculiarities and constraints.

Branch target calculation, for example, typically involves adding a small constant to a full word, which suggests a different adder design from one which adds two full words together. Similarly, floating point addition requires a post-addition rounding step which might take less than a cycle, so there's no reason why you couldn't steal the rest of the cycle to finish off the addition.

Lastly, and perhaps most importantly, the big players (e.g. Intel, AMD, NVIDIA) are fairly tight-lipped about low-level implementation details for obvious reasons, unless they think they can get a paper and/or patent out of it. Even then, you often can't be sure what they actually did without reverse-engineering.

Having said that, there are a few things we know.

The key thing you need to realise is that carry-lookahead methods are building blocks, and not necessarily methods in themselves. An analogy might be in order here.

If you think about algorithms classes, you probably learned a bunch of sorting algorithms such as quick sort, merge sort, insertion sort, and so on. In the real world, if sorting is a performance bottleneck, any decent engineer would think of these as primitive building blocks from which a "real" sort can be constructed.

The sort algorithm from the GNU C++ standard library, for example, uses quick sort, using insertion sort when the intervals get small enough. However, if after a few passes it looks like the quick sort partitioning has hit pathological behaviour, it falls back to heap sort. That's three different sort algorithms to make one industrial-strength sort.

The same is true of adder circuits. It is known, for example, that the Pentium 4 integer unit used a Han-Carlson adder, which is a mix of Kogge-Stone and Brent-Kung. (Han-Carlson is especially interesting, because it's a "sweet spot" in the tradeoff between propagation delay and die area which also being quite power-efficient.) It often pays to use a mix of several methods.

"Pure" carry-lookahead adders are still very much the norm in synthesised circuits (e.g. if you feed a Verilog "+" operator to Cadence or Synopsys), when it comes to hand design, modern high-end CPUs with their superscalar out-of-order execution engines seem to be moving towards a slightly different design for their integer units.

Speculative adders are circuits which have extremely low propagation delay, but only work correctly some of the time (95% of the time is typical), and it's possible to tell with very little logic whether the speculative adder returns the correct result or not. So the idea is to do a speculative addition and half of a carry-lookahead addition in parallel, in one cycle. If the speculative adder returned the correct answer, the instruction is done. Otherwise, stall the pipeline and do the other half of the accurate addition.

Because you know that the slow path will take two cycles, the designers could use a more space and power-efficient method even if it would be too slow for general use.


Given a set of numbers (negative or positive), and a maximum weight w, find a subset that is maximal whose sum is less than w The aim of this problem is to find a subset (need not be consecutive) of a given set such that the sum is maximal and less than some given number $w$. (Note, we are trying to find a subset that is less than or equal to $w$ and not closest to $w$).

For example, given a set $\{1, 3, 5, 9, 10\}$ and maximum weight 17, the maximal subset is $\{3, 5, 9\}$ since its sum is exactly 17.

Another example: given a set $\{1, 3, 4, 9\}$ and maximum weight 15, the maximal subset is $\{1, 4, 9\}$ since its sum is 14, and there are no other subsets whose sum is 15.

Example with both positive and negative numbers: given a set $\{-3, 2, 4\}$ and maximum weight 3, the subset is the set itself since -3 + 2 + 4 = 3.

I know how to solve it with only positive numbers, but I am struggling to find an algorithm to solve this problem for the general case with both positive and negative numbers. Obviously, my goal is not to use the brute force approach and check every possible subset since the complexity would be $O(n2^n)$.

I stumbled upon an idea on another post that suggested adding a sufficiently large number to every elements in the set and subsequently changing the maximum weight. That is given a set $R = \{ a_1, a_2, ... , a_n \}$, we add some number $X$ (we can pick some number greater than equal to the absolute value of the smallest negative number) to get a set that looks like $\{ a_1 + X, a_2 + X, ... , a_n + X \}$ and change the maximum weight to $nX + w$ where $w$ was the original weight. Now, we have reduced the problem to only non-negative numbers. However, I could not see a way to actually find the subset that was closest to the original weight, but only whether any elements add up exactly the original weight (ie, there is no way to actually find the subset, but only to determine that some subset exists).

Is there any other clever trick like this one to solve the problem for both positive and negative numbers? Any help would be thoroughly appreciated.

This problem can be solved by a rather simple dynamic programming:

Given a set of numbers $\{a_1,\dots,a_n\}$, let $best(i, w)$ be the best solution using only a subset of the elements $a_i,\dots,a_n$ with a maximum value $w$, then $$best(i,w) = max(a_i + best(i+1,w-a_i), best(i+1,w))$$
With boundaries conditions $best(n + 1,w) = -\infty$ for any $w < 0$,
and $best(n + 1,w) = 0$ otherwise.

Note that this problem is NP-hard because it solves the partition problem, in particular the running complexity of the above program depends on the given numbers, and can be exponential in the size of the input in the worse case.


Union of two automata I need to find a minimal DFA given the following information:

  $ \{a^nb : n\geq 0\} \cup \{b^na: n \geq 1\}$

Now, maybe I'm not seeing this properly, but I don't see how this is possible: the first one will take 0 or more a's followed by one b, whereas the second one will take a 1 or more b's followed by one a.

Drawing the combined automata only brought me to trap states. Any suggestions?

As @vonbrand suggested, using one automata (without attempting to combine them) is sufficient. Combining them will prove to be more work than it's worth.

Basically, here's the idea:

If you get an $a$, begin looping on $a^nb$. If you get a $b$ after this, accept. But anything further goes to the trash can.
If you get a $b$, accept for $a^0b$. If you get another $b$, you can then loop on $b$ under $b^na$. At any point in the loop, if you get an $a$, accept. But if you get anything after that $a$, go to the trash can.

Here is a textual representation (t is the "trash can" or trap state; + represents an accept state).

  | 0   | 1   | 2+  | 3+  | 4+  | 5
a | 1   | 1   | 4   | t   | t   | 4
b | 2   | 3   | 5   | t   | t   | 5

And here is a generated visual version:

(I'm not 100% sure this is minimal, but if it's not, it's a good exercise.)


Defining a new operator in CTL Lets consider a new operator $B$ where $a B b$ means "in every execution, if $b$ holds some time, then $a$ does so before it" and we're asked to define it in CTL.

My working: the system can only fail if $b$ holds. If $b$ doesn't hold, we're in the clear - so one possible path could be $(¬ □ b)$. The only other path that could hold is one where $a$ happens before $b$, so $(a$ $U$ $b)$ is another path. Overall we're left with $∀((a U b) ∨ (¬ □ b))$. For every path either $a$ happens before $b$ OR $b$ never happens.

Is the way I reasoned about this question correct? Are there any holes in my logic that I should re-consider? Please reply as a comment if possible, and many thanks in advance for any input.

For the answer $\forall \lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$:
I think you have got the right idea. However, this formula is not in CTL since $\lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$ is not a path formula.

By $\forall \lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$, I think you want to say $\forall \Box \left( \lnot \exists \left( \left( \lnot a \right) \bigcup b \right) \right)$, which is the answer.

(If you are observing the system from the very start (i.e., its initial state), the simpler and weaker one $\lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$ would be also acceptable. Please check it and let me know whether it is right.)

As I have mentioned in the comment, there are past CTLs (PCTL) which incorporate past operators facilitating the expression of "time going backwards". Using PCTL (for example in [1]), your property can be directly rendered by $\forall \Box (b \implies \Diamond^{-1} a)$ (Note its syntax!). You can guess the meaning of $\Diamond^{-1}$ easily.

[1] Specification in CTL+Past for Verification in CTL (2000)


Heuristics vs meta-heuristics vs hyper-heuristics? The wikipedia page on meta-heuristics states that they are "heuristics designed to find, generate, or select a heuristic".

The wikipedia page on hyper-heuristics states that they are "heuristic search methods that seeks to automate [...] the process of selecting, combining, generating or adapting several simpler heuristics".

Moreover, it also states that "The fundamental difference between metaheuristics and hyper-heuristics is that most implementations of metaheuristics search within a search space of problem solutions, whereas hyper-heuristics always search within a search space of heuristics."

This leaves me confused: it seems like the hyper heuristic page is contradicting the meta-heuristic page. How can a meta-heuristic search for heuristics, if its search space is the problem space rather than the space of heuristics?

What really is the difference between metaheuristics and hyperheuristics?

Defining meta-heuristics as "heuristics designed to find, generate, or select a heuristic" seems too broad. A meta-heuristic is commonly understood as an algorithmic template that defines how different low-level heuristic components (e.g. constructive procedures, local searches, solutions recombinations) interact in the search. After instantiating these components for a specific problem, you get a heuristic which searches in the solution space.

Gendreau, Potvin, Handbook of Metaheuristics define them as

  solution methods that orchestrate an interaction between local improvement strategies and higher-level strategies to create a process capable of escaping from local optima and performing a robust search of a solution space

and chapter "Defining the term 'Metaheuristic'" of Zäpfl, Braune, Bögl, Metaheuristic Search Concepts summarizes

  A metaheuristic relies on a high-level strategy which builds upon a particular basic search principle
  The high-level strategy is problem-independent and can be seen as an abstract framework
  The high-level strategy has to properly realize a balance between the two forces intensification and diversification.

Thus, a short answer could be: in a meta-heuristic the designer instantiates low-level heuristics; a hyper-heuristic automates the selection or generation of the low-level heuristics.


Hough Transform, Computer Vision There is some thing i dont understand about Hough Transform in polar coordinates.

From wikipedia article:

"The simplest case of Hough transform is detecting straight lines. In general, the straight line y = mx + b can be represented as a point (b, m) in the parameter space. However, vertical lines pose a problem. They would give rise to unbounded values of the slope parameter m. Thus, for computational reasons, Duda and Hart[5] proposed the use of the Hesse normal form
$R = X*Cos(\theta) + Y*Sin(\theta)$ ,
where $R$ is the distance from the origin to the closest point on the straight line, and $\theta$   is the angle between the x axis and the line connecting the origin with that closest point."

now the issue im having with this is:
The Distance from the origin to the closest point on the straight line would be
$\sqrt{x^2 + y^2}$ by the euclidean metric
and not
$R = X*Cos(\theta) + Y*Sin(\theta)$

Consider a vector $\mathbf v$ of any dimension. The hyperplanes orthogonal to that vector are given by the equation $r = \mathbf u\cdot \mathbf v$ for various $r$s. That is, the collection of vectors $\mathbf u$ satisfying $r=\mathbf u\cdot\mathbf v$ describe a hyperplane orthogonal to $\mathbf v$. If $\varphi$ is the (acute) angle between $\mathbf u$ and $\mathbf v$ (in the plane that they span, not to be confused with the hyperplane the earlier equation describes), this can be written as $r=|\mathbf u||\mathbf v|\cos\varphi$. From this we can see that $|\mathbf u|$ is minimum when $\varphi = 0$ so that $\cos\varphi=1$, the maximum value of $\cos$. If we choose $\mathbf v$ to be a unit vector, i.e. $|\mathbf v|=1$, then the point on the hyperplane closest to the origin is $\mathbf u=r\mathbf v$ and has distance $r$, i.e. $|\mathbf u|=r$.

In the 2D case, the "hyperplane" is actually a line. A unit vector in the plane has the form $\mathbf v = (\cos\theta,\sin\theta)$ for some $\theta$. The dot product equation describing the line is then $r=\mathbf u\cdot\mathbf v = u_x\cos\theta + u_y\sin\theta$ where $\mathbf u = (u_x,u_y)$. The point on the line closest to the origin is then $r\mathbf v = (r\cos\theta,r\sin\theta)$ which is a vector of length $r$ just as stated in the article. As mentioned in the previous paragraph, if $\mathbf v$ is chosen as a unit vector (and it always can be), then this is true in general: $r$ is the distance of the closest point to the origin of the described hyperplane, and that closest point is $r\mathbf v$.


Feature selections : Still a high dimentionality One of the advantage of using a features reduction/sub feature selection is to avoid a high dimentionality.

The most known method is the Forward selection, where it finds the best combinations of features among others, iteratively. Now please have a look at this picture retrieved from a ppt slide on the internet.

The second row of the table shows that the 11 features are the features selected/reduced from initial 20 features. My question is that, the 11 features are still considered as a high-dimensional features set, indeed one can't just subtitute it over a KNN function. Now I'm confused as to how he/she then adapt it to the KNN classifier for the 11 features?

There seems to be a misconception.  You can use $k$-nearest neighbors with any number of dimensions.  There is no prohibition on using it with a large number of features.  And in some cases $k-NN will work well even in high dimensions (a large number of features); it all depends on the dataset, and to find out whether it will work well, you have to try it.  In general, feature selection might make the algorithm work better, or it might make it work worse -- it all depends.


Are Test and set primitives as powerful as semaphores? I get confused because i don't know if it is possible to use Test and Set primitives in case where more then one process can be enter in critical section at the same time.

Your hunch is correct, they aren't equivalent. Test-and-set has a consensus number of 2, which means, roughly speaking, that it is only able to efficiently synchronize between 2 processes. See Why is the consensus number for test-and-set, 2?. Semaphores allow synchronization between an arbitrary number of processes (assuming no bound on the number of processes waiting on a semaphore).

It isn't really a “fair” comparison, since test-and-set is a hardware primitive while semaphores are a software interface. But if does show that test-and-set isn't sufficient to implement (wait-free) semaphores.


NFA models with characters on nodes, not edges I am attempting to understand the inner workings of the open source string matching library Hyperscan.

It takes a multiple-engine approach to the problem of generating string matches, and I'm still in the early stages of following through the debugging output to see how it does what it does.

However, one design decision already visible at this point puzzles me: when constructing an NFA, it doesn't use the traditional model of a directed graph with edges labeled with characters, and nodes labeled with whether or not they accept. Instead, it seems to use a model (*) of a directed graph with unlabeled edges and nodes labeled with a set of characters that can reach this node, along with designated special nodes for accepting strings. (specifically, it has a special NODE_ACCEPT node and a special NODE_ACCEPT_EOD node; nodes that mean "accept and ignore remaining input" have edges to NODE_ACCEPT and nodes that mean "accept if at end of input" have edges to NODE_ACCEPT_EOD)

I think this model is equivalent to the standard NFA model, but I can't find any references to this NFA model anywhere; I wonder if it goes by a standard name that I just don't know, and therefore can't search for. (My attempts just get buried in page after page of explanations of the standard NFA model)

So, has anyone seen an NFA model like this before? Are there any references I can look at to find out why one might prefer a model like this?

(On the off chance that anyone has already written up something on how the compiler and the various string matching engines embedded inside the Hyperscan library work, I'd also love any pointers to that. I primarily want to learn about state-of-the-art string-matching techniques, not about how to reverse-engineer C++.)

(*) I'm simplifying slightly here and ignoring bits of node and edge labels that seem unused at the initial stages.

Hyperscan chief architect here.

The buzzword you are looking for is a Glushkov NFA, as opposed to a Thompson NFA.

The 'traditional model' you refer to is a Thompson NFA but is by no means the only choice. Both have their strengths and weaknesses, but we found the Glushkov NFA quite economical and it maps very nicely to a bitwise implementation (the "LimEx" NFA is a concrete NFA implementation, as opposed to the NFAGraph, which is an abstract representation). The joy of the Glushkov NFA is that the calculation of "reach" (which states are reached on which characters) and "succ" (which states can succeed other states) are completely independent and can be combined with a simple AND operation.

Gonzalo Navarro has a number of very nice papers and an excellent book on this subject. In terms of underlying approaches (if no the specific algorithms) we are entirely indebted to him.

Feel free to contact the Hyperscan list or alias if you want more information. We have been very lax in terms of writing up our approach.


Can we express the program to find last element of a list as a catamorphism? So I've got a bit of category theory under my belt, and I am reading a few papers about calculating functional programs.  I've expressed  programs like summing a list as a catamorphism, and I've fused some catamorphisms, too.

I thought it might be interesting to see how far I could take what I now know about catamorphisms by applying it to 99 Haskell Problems .  It turns out that I can't take it very far at all because the first problems have me stumped.

I'm aware that the old saying "if the only tool you have is a hammer, then every problem looks like a nail" applies to me. But if we are asked to provide a program that finds the last element of a list, can we express that program as a catamorphism?  If not, then why?

Thanks in advance!

I'm a bit old-fashioned so I'll let Erik Meijer do most of the talking here.

Let's look at the classical definition of a list-catamorphism. More commonly, we call these functionals "folds" over some operator, because you can visualize it as bamboo scroll being folded into each other. (Except in this analogy, when we fold one piece into the other, we're left with a single piece).

Given a list over type $\alpha$ to fold over, an operation $\otimes : \alpha \times \beta \to \beta$, and an initial value $b : \beta$, we can define the $(b, \otimes)$ induced catamorphism $h : \alpha \textrm{ list} \to \beta$ as
\begin{align*}
h([]) &= b \\
h(a :: l) &= a \otimes h(l)
\end{align*}

In Meijer's (in)famous notation, we'll say that $h = (\!|b, \otimes|\!)$. We can do this because every catamorphism is uniquely determined by such a pair, and every pair defines a catamorphism, so we have an equivalent representation.

So let's now see whether there's some pair $(\!|b, \otimes|\!)$ such that the induced catamorphism finds the last element of the list. First, let us define the last function. You'll immediately notice a problem:
\begin{align*}
\textrm{last}([]) &= \bot \\
\textrm{last}(a :: l) &= \dots
\end{align*}

last is a partial function! Catamorphisms are by definition total functions, so we immediately see that a straightforward translation is impossible.

However, if we're allowed to use isomorphic representations, then we can consider the Maybe/Optional/Point functor that designates a special $\bot$ point that can be treated as the least element of the partial order. Let's say that the pointed type $\beta_{\bot}$ is either $\textrm{Some } b : \beta_{\bot}$ or $\bot_{\beta}$. The question now is whether there is some $(\!|a_{\bot}, \oplus|\!) : \alpha \textrm{ list} \times \alpha_{\bot} \to \alpha_{\bot}$ that models the last function. Some equational reasoning will quickly give a derivation

If
$$
\textrm{last}' = (\!|a_{\bot}, \oplus|\!) : \alpha \textrm{ list} \times \alpha_{\bot} \to \alpha_{\bot}
$$
then $a_{\bot} : \alpha_{\bot}$ and $\oplus : \alpha \times \alpha_\bot \to \alpha_\bot$.
Expanding the definition of a catamorphism out, we have
\begin{align*}
\textrm{last}'~[] &= a_{\bot} \\
\textrm{last}'(a :: l) &= a \oplus (\textrm{last}' ~l)
\end{align*}
The true last function ought to satisfy the equations
\begin{align*}
\textrm{last} ~ [] &= \bot_{\alpha} \\
\textrm{last}(a :: l) &= \textrm{match } \textrm{last}~l \textrm{ with} \\
&~~~~~ \mid~ \bot \to \textrm{Some } a \\
&~~~~~ \mid~ \textrm{Some } a' \to \textrm{Some } a'
\end{align*}

Equating last' and last then gives
\begin{align*}
a_\bot &= \bot_{\alpha} \\
a \oplus a' &= \textrm{match } \textrm{last}~l \textrm{ with} \\
&~~~~~ \mid~ \bot \to \textrm{Some } a \\
&~~~~~ \mid~ \_ \to a'
\end{align*}

which uniquely defines the pointed last' function as a catamorphism. To get the partial last function, just compose it with the partial function $\textrm{get}_{\alpha_\bot} : \alpha_\bot \to \alpha$.

Now, this proposal of returning to partiality has an interesting structure:
$$
\textrm{last} = \textrm{get}_{\alpha_\bot} \circ (\!|\bot_{\alpha}, \oplus|\!)
$$

The astute reader may point out that this seems to be of a form that is amenable to the catamorphic fusion law. And you are right, it has the correct syntactic form. To quote Meijer again, the fusion law is the extensional (since it is (usually) not an intensional reduction rule) equality that
$$
f \circ (\!|a, \otimes |\!) = (\!|b, \oplus |\!) \Leftarrow b = f~a \wedge f~(x \otimes x') = x \oplus (f ~ x')
$$
Unfortunately, neither of these conditions hold. In particular, $\textrm{get}_{\alpha_\bot} \bot$ is not valid (since get is partial at $\bot$).


How can I prove this language is not context-free? I have the following language

$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$

I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-sensitive grammar so I know it is atleast context-sensitive. It seems like it wouldn't be possible to make with a context-free grammar, but I'm having a problem proving that.

It seems to pass the fork-pumping lemma because if $uvwxy$ is all placed in the third part of any word (the section with all of the $2$s). It could pump the $v$ and $x$ as many times as you want and it would stay in the language. If I'm wrong could you tell me why, if I'm right, I still think this language is not context-free, so how could I prove that?

You can force the pumping to be in some places, using Ogden's lemma, for example by marking all the 0's.

Suppose it is context free, then Ogden's lemma gives you a $p>0$, you give it $w=0^p1^p2^p$ which is in the language, and you "mark" all the 0's. Then any factorisation $w=uxyzv$ must be such that there is a $0$ in $x$ or $z$. You can also assume $x=a^k$ and $z=b^m$ since $xx$ and $zz$ must be substrings of your language.

If $z=0...0$ then $w=ux^2yz^2v$ has more 0's than 1's
If $x=0..0$ and $z=1..1$ then $w=ux^2yz^2v$ has more 1's than 2's.
If $x=0..0$ and $z=2..2$ then $w=ux^2yz^2v$ has more 0's than 1's.

So $ux^2yz^2v$ is not a word of your language. Therefore, it is not context-free.

For other techniques, see the discussion: How to prove that a language is not context-free?


What do we gain by having "dependent types"? I thought I understood dependent typing (DT) properly, but the answer to this question: https://cstheory.stackexchange.com/questions/30651/why-was-there-a-need-for-martin-l%C3%B6f-to-create-intuitionistic-type-theory has had me thinking otherwise.

After reading up on DT and trying to understand what they are, I'm trying to wonder, what do we gain by this notion of DTs? They seem to be more flexible and powerful than simply typed lambda calculus (STLC), although I can't understand "how/why" exactly.

What is that we can do with DTs that cannot be done with STLC? Seems like adding DTs makes the theory more complicated, but what's the benefit?

From the answer to the above question:

  Dependent types were proposed by de Bruijn and Howard who wanted to
  extend the Curry-Howard correspondence from propositional to
  first-order logic.

This seems to make sense at some level, but I'm still unable to grasp the big-picture of "how/why"? Maybe an example explicitly show this extension of the C-H correspondence to FO logic could help hit the point home in understanding what is the big deal with DTs? I'm not sure I comprehend this as well I ought to.

Expanding my comment: Dependent types can type more programs. "More" simply means that the set of programs typable with dependent types is a proper superset of the programs typable in the simply-typed $\lambda$-calculus (STLC). An example would be $List_{2*3+4}(\alpha)$, the lists  of length $10$, carrying elements of type $\alpha$. The expression $2*3+4$ is at the same time a program and part of a type. You cannot do this in the STLC.

The key rule that distinguishes dependent from non-dependent types is application:

$$
\newcommand{\TYPES}[3]{#1 \vdash #2 : #3}
\newcommand{\SUBST}[2]{\{#1/#2\}}
\frac{
   \TYPES{\Gamma}{\color{red}{M}}{A \rightarrow B}
      \qquad
   \TYPES{\Gamma}{\color{red}{N}}{A}  }{
 \TYPES{\Gamma}{\color{red}{MN}}{B}   }
      \qquad
\frac{
   \TYPES{\Gamma}{{\color{red}M}}{\Pi x^A. B}
      \qquad
   \TYPES{\Gamma}{\color{red}{N}}{A}  }{
 \TYPES{\Gamma}{{\color{red}{MN}}}{B\SUBST{{\color{red}N}}{x}}   }
$$

On the left you have the STLC, where programs in the premises 'flow' only  into the program of the conclusion. In contrast, in the dependent application rule on the right, the program $N$ from the right premise 'flows' into the type in the conclusion$^1$.

In order to be able to parameterise types by programs, the syntax of dependent types must be richer, and to ensure that types are well-formed we use a second 'typing system' called kinds that constrains the types. This kinding system is essentially the STLC, but "one level up".

There are many explanations of dependent types. Some examples.

Dependent Types at Work, by Bove and Dybjer.
Dependent Types, by Aspinall and Hofmann.
Dependently Typed Programming in Agda, by Norell and Chapman.
Lambda Calculi with Types, by Barendregt.

$^1$  In terms of colours: with non-dependent types, black expressions in the conclusion are constructed from black expressions in the premises while
red   expressions in the conclusion are constructed from red expressions in the premises. With dependent types the colours can be mixed by having black parts of the conclusion being constructed from red and black parts of the premise.


Big O notation for finding duplicates in a list using binary search I've written an algorithm to find duplicate integers in a sequential list of integers, but I'm running into issues when trying to calculate it's worst case complexity.

Given a sequential list of integers the algorithm is as follows:

1. get the length of the list of integers, assign to list_length - O(1)
2. while list_length is greater than 0: O(n)
  1. remove the item at index 0 from the list and assign to checking - O(1)
  2. set list_length to the current length of the list
  3. perform a binary search of the remaining list for the value assigned to checking - O(log n) where n is the current length of the list
  4. if the item is in the list return True
3. if none of the binary searches found a match return False

My understanding is that the complexity of a binary search is $O(\log n)$ and if I were not to remove an item from the list on each iteration, the complexity of my algorithm would be $O(n \log n)$ (as I am running an $O(\log n)$ algorithm $n$ times).

What I am not sure of is how the shortening of $n$ will affect the binary search, as on each iteration the complexity of the binary search will change: $O(\log (n - 1))$ on the first iteration, then $O(\log (n - 2))$ on the second.

How do I represent the diminishing size of $n$?

I have two different points:

As for complexity of your algorithm I believe this still to be O(N*log N). Consider the first half of the checks. For each check you do a binary search over the list of the size at least N/2 so it is O(log (N/2)) but given that log (N/2) = log(N) + constant it is just O(log N). And you do at least N/2 such checks. So it is O(N*log N)
If your list is not sorted, just sorting it to use binary search will take at least O(N*log N) so this is the lower bound anyway. And if it is sorted, your algorithm is very inefficient. You can do it in just O(N) by comparing each 2 sequential elements in the list (duplicates obviously have to be next to each other in a sorted list).


If L1 ⊆ L2 and L2 is regular, then L2 − L1 is regular I'm having trouble being 100% sure about this answer. I feel like it's false but I'm having trouble coming up with a complete answer. Can someone explain this step by step?

Thanks.

You can show that if $L_1 \subseteq L_2$ and $L_2$ is regular, then $L_2 \setminus L_1$ is regular iff $L_1$ is regular. This follows from the product construction, for example. Taking $L_2 = \Sigma^*$, we find that $\Sigma^* \setminus L_1$ is regular iff $L_1$ is regular. Hence if $L_1$ is any non-regular language, then it refutes your statement taken with $L_2 = \Sigma^*$.


Dynamic Programming - How to get the solution from the predecessor matrix Whenever I'm coding a dynamic program , I usually struggle building the solution from the predecessor matrix . How should use the predecessor matrix to find the solution ?

Thanks,

That depends a lot on the question, really. But basically, since you have the values of the all your "sub-problems", and you know your formula for the problem (Meaning, how the current problem is solved using the optimized solutions for the smaller problem), you can just check which cells (That are possible optimized solutions) in the matrix satisfy this formula.

Then, you can know that this cell is part of the solution.

Continue this way from top to bottom - and you'll get your whole solution (And not just the value, which is I guess was your problem).


Type checking relation to logic I am learning logic and functional programming and there is a topic called Type checking and their relationship to logic , I am unable to find any source that can help me in understanding this topic. Please help .

https://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ - This book.

A type for a parameter is like a precondition, and a type for a return value is like a postcondition.  Structs function as an AND operator, and Unions function as an OR operator.  When you say

performTransaction(x : DollarAmount) : Result

If x had to be constructed as a valid DollarAmount type, then this function is only callable if that was possible.  Also, the Result type is guaranteed to have some fields on it (error codes, transaction id, etc); and performTransaction has to construct the object to give it to you.  So, if you view statements like "x : int" as "x is proven to be an integer", then it is not a stretch to have something more elaborate like:  " x : int, x > 0, x < MAXINTEGER " to assert that x is a positive integer (a DependentType is a type that depends on the value, typically notNull, notZero, etc).

You can make functions take in very specific types that indicate an initial state, and return new types that indicate new states; and use types to enforce constraints on following a state machine - at compile time in many cases.


Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$ Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$.
For eg. Let the array be $1,2,3$ then my answer will be calculated as-
$(2-1)$.$(3-1)$.$(3-2)$=$2$
As number of elements in the array could be large (upto $10^5$) I am looking for solution of order $nlogn$.
I have tried representing array as a polynomial but could get anything out of it.
Please help.

The product $$V=\prod_{i<j}(a_j-a_i)$$ is the determinant of the Vandermonde matrix of the numbers $a_1,a_2,...,a_n$.
The square of this number is the discriminant  $D$ of the polynomial $$p(x)=\prod_i(x-a_i)$$
This in turn is equal to $$V^2=D=(-1)^{n(n-1)/2}\prod_ip'(a_i)$$
You can quickly compute the coefficients of $p(x)$ and thus $p'(x)$, evaluate it at the $n$ points $a_1,a_2,...,a_n$ and their product. Then compute square root. The sign of $V$ you determine by sorting and counting the parity of the number of switches.
You can do all this in $O(n\log^2(n))$.
See the relevant algorithms here.
For the modular square root, you can use Tonelli-Shanks for efficiency. Although the theoretic order of this step is constant since the prime $998244353$ is fixed.


Calculating traversal position of a node in a full binary tree, given its path Given a path down a full binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing "go left" and $1$ representing "go right"), how would one find the position of the node in the preorder traversal. In other words the $i$th node in the preorder traversal will end up with at this node.

Obviously something better than brute force would be nice.

Essentially the algorithm is:

Each time you go left, you add one.
Each time you go right, you add the size of the left sub-tree, and you add one.

The size of a full binary tree can be calculated as $2^{h+1}-1$. Thus, the height of the left sub-tree can be calculated by $2^{h_{\text {subtree}}+1}-1=2^{h-l+1}-1$ where $l$ is the level of the left sub-tree.

#WARNING: non tested, python-ish

def calc_tree_size(tree_height):
  return (1<<(tree_height+1)) - 1

def inorder_traversal_position(tree_height,path):

  result = 0

  for level in range(len(path)):
    if path[level] == 0:
      #If we go left,

      #Preorder goes left after visiting a node.
      #Add one for the node we just visited.
      result += 1
    elif path[level] == 1:
      #If we go right,

      #Preorder normally goes left, visiting all the nodes
      # in the left sub-tree before going right.
      #Add the number of nodes in the left sub-tree.

      left_subtree_level = level + 1
      left_subtree_height = tree_height - left_subtree_level
      left_subtree_size = calc_tree_size(left_subtree_height)

      result += left_subtree_size

      #Add one for the node we just visited.
      result += 1

    return result


Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph? A minimum-spanning-tree (MST) path is always $V-1$ edges and a Hamiltonian Cycle (HC) is always $V$ edges.

Because the HC has an extra edge we could say that in general, the weight of every Hamiltonian cycle of a connected graph will be more.

If we take an edge of every Hamiltonian cycle we will find an MST and by that, the MST weight will be always lower than HC.

There is a way to prove this where MST tree not necessary belongs to the HC?
There is more definitive proof for this?

Suppose:

$G$ is some graph with non-zero, positive weights.
The minimum spanning tree of $G$ is denoted by $MST$
$H_C$ is a hamiltonian cycle in $G$.
$H_P$ is a hamiltonian path in $G$, given by removing any one edge of $H_C$.

Since all the edges are positive and non-zero, we immediately get that:

$$w(H_C) > w(H_P)$$

Also, $H_P$ is a subgraph that includes all vertices of $G$ (and connects them), so $H_P$ in fact spans $G$.

Hence, by definition of minimum spanning tree:

$$w(H_P) \geq w(MST)$$

It follows that $$w(H_C) > w(H_P) \geq w(MST)$$

In case we allow zero weights, the inequality holds, it simply will not be strictly greater (for the same reasons noted in the answer). That is:
$$w(H_C) \geq w(H_P) \geq w(MST)$$


Can an operating system without api still work? In theory operating system is a special program run by itself without help so that also mean normal program can still run by itself mean that the need for api is not must have so finally can we have an os without api ?

No, the other programs sit on top of the operating system(OS) and the OS runs on top of the hardware. The OS provides these programs with basic resources the programs will need to run like CPU, memory and input/output from for e.g. mouse and keyboard. The API is the only way they can get these resources, so normal programs will not be able to work on an OS without API. The new browser analogy is wrong since using IE is just a way to download the new browser files(can do it from command line, without IE). New browser still needs the OS to run.


Robustness of Turing Machines - 3 dimensional case How can one show that a machine with a three dimensional memory arranged in an infinite grid can be simulated by a single-tape Turing machine? I'd imagine there's some sort of mapping possible from three dimensional coordinates to single coordinates (eg. (0,0,0) -> 0, (1,0,0) -> 1, (-1,0,0) -> 2, ...) but I can't figure it out. Or maybe there's some clever way to separate the points using special symbols. Either way, I'm at a loss.

If you are not concerned with efficiency this trivial and time-wasting approach can also work (it only shows how it can be done without taking too much care of coordinate-mappings ... in other words the bad way to do it :-)).

Use the single tape to store a list of quadruples $...\#x,y,z,v\#...$.

Each quadruple holds the value $v$ stored on the 3D tape at point $(x,y,z)$. Initially the single tape is filled with a finite list of the non-blank values of the 3D tape along with their coordinates, and the head is on the left of the quadruple that represents the head position in the 3D tape.

Every step of the original 3D machine can be simulated in the following way:

apply the original transition, and update the value $v$ to $v'$ in $(x,y,z,v)$
now, suppose that the head must move to the adjacent 3D point $(x',y',z')$, then search in the tape from left to right for a quadruple that matches its coordinates;- if you find it, then move the head on it and go to (1);- if you don't find it, just append a new quadruple $(x',y',z',blank)$ to the end of the tape, move  the head on it and goto (1)

For every state of the original 3D machine you must have many states on the single tape machine in order to perform the operations at step 2 and at the same time keep track of the current state of the original machine.


How do you find an infinite regular language that is a subset of a non-regular language? In order to do this, we would probably need the non-regular language to be infinite as well, then find some definition for the non-regular language in order to fulfill the requirement, but I don't know how to construct one.

Note that any non-regular language is infinite, since any finite language is regular.

Instead of searching for infinite regular subset in some given non-regular language, why don't we try to construct a non-regular language that contains an infinite regular language?

To do that we can take some context-free language, which is not regular, e.g. classical $a^nb^n, n \ge 0$, and "add" some infinite regular language to it. By "add" I mean the union operation on sets.

I should notice that one has to be careful while "adding" an infinite regular language to a non-regular one, since $L(a^nb^n) \cup \Sigma^* = \Sigma^*$, which is obviously regular.

So let's take a regular language $L(a^*)$, which has only one string in common (the empty string) with $L(a^nb^n), n \ge 0$ as our candidate "addition".

It's easy to prove the language $L(a^*) \cup L(a^nb^n), n \ge 0$ is non-regular (context-free). And its regular subset $L(a^*)$ is infinite.


Is the consensus number of SetAgree(3, 2) 2 or 1 (proof needed)? SetAgree(n, k)

An object that allows n threads to propose() n values.
It guarantees Each thread will decide() on a (single) value.
The cardinal number of the set of all values decided on is lower or equal to k.
All values decided on were proposed.

It is obviously trivial if n <= k so the first interesting case is SetAgree(3, 2).

Consensus(n) is the same as SetAgree(n, 1).
A consensus number of an object is the highest number of threads that can arrive at a consensus using that object and shared memory access.

Alright, I'll start by saying I think the consensus number of SetAgree(3, 2) is not two.

My line of proof is that I assume there is a protocol that solves a binary consensus(2) using the strongest SetAgree(infinity, 2).

At some point in the algorithm (which has to be deterministic) we arrive at a node where if thread A acts, the consensus will be its proposal (without loss of generality 1) and if thread B acts, it will be its proposal (without loss of generality 0).

Lets say, both of them wish to access the SetAgree object at this node, they could get the values they proposed no matter the order of access they use so the state of the system will be the same (no matter the order). If only one of them accesses the object and the other one reads or writes to a memory register then the order is meaningless for sure simply because memory doesn't affect the SetAgree object and SetAgree doesn't affect any of the shared memory registers. So obviously regardless of the order, the state of the system will be the same after these two operations which means, it is not possible that one leads a consensus on (1) and the other on (0).

The line of proof that suggests consensus number 2 states (the known fact) that setAgree(3, 2) cannot be build with shared memory alone. This is well known but it doesn't suggest setAgree(3, 2) has a stronger consensus number cause that line of proof only applies to data structures, cause it relies on universal construction.

Is there any stronger proof that it's consensus number 1 or 2?

We can prove that 2-set-consensus among 3 processors (noted (3,2)) cannot be used (together with registers) to solve consensus among 2 processors (noted (2,1)) using the Borowsky-Gafni simulation (BG simulation for short).

The BG simulation allows 3 processors using registers only to simulate any algorithm in which 2 processors use registers and (3,2).
Therefore, the BG simulation transforms an algorithm A solving consensus among 2 processors using (3,2) into an algorithm B solving consensus among 3 processors using registers only.
Since the latter is impossible, there is no such algorithm A.

Note that by solving I mean solving wait-free.

This proof first appeared in Borowsky and Gafni, "Generalized FLP impossibility result for t-resilient asynchronous computations." Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. ACM, 1993. (In particular see the end of section 3.3).


Is $O(T+\log T)= O(T\log T)$? Is $O(T+\log T)= O(T\log T)$?

I think this is true but I do not know how to show it mathematically?

Please show it using the definition.

Also, if it is true, is the following true?

$O((T+\log T)^{1/n})= O((T\log T)^{1/n})$

Let $b$ be the base of the logarithm. If $T > \max(b^2, 2)$, then $\log T =\log_b T> 2$. So
$$T\log T - (T+\log T) = (T-1)(\log T -1) -1 > 1\times 1 -1 =0$$
i.e., $T+\log T< T\log T$.

So, any function that grows asymptotically slower than $T+\log T$ modulo a constant factor also grows asymptotically slower than $T\log T$ modulo the same constant factor. According to the definition of multiple usages of big O-notation,
$$O(T+\log T)= O(T\log T)$$

Yes, it is true that $O((T+\log T)^{1/n})= O((T\log T)^{1/n})$, where we consider $n$ as a constant.


$\mathsf{RegExpEq_*} \in \mathsf{coNPC}$ but why isn't in $\mathsf{P}$ Hello for a homework I have to show that deciding whether a regex over $\Sigma = \{0,1\}$ descibes $\Sigma^*$ is $\mathsf{coNP}$ complete (this is irrelevant for the question though).

The thing which irrs me is that I think this problem is in $\mathsf{P}$.

Here is my argumentation:

Let $R$ be a regex, then we have $$L(R) = \{0,1\}^* \Leftrightarrow \overline{L(R)} = \varnothing$$

Given $R$ we can consruct an NFA with $\epsilon$ moves for $L(R)$ in poly. time; eliminating the $\epsilon$ moves (again poly. time: $O(|Q| \cdot |\delta| \cdot |\Sigma|)$) we obtain an NFA $M$.

By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline {L(R)}$, whose emptiness we can check with a BFS (again in poly. time).

$\leadsto \mathsf{RegExpEq_{*}} \in \mathsf{P}$

Where does my argumentation shatter? If both my argumentation and the question is correct, then $\mathsf{P} = \mathsf{coNP}$ which seems highly doubtful.

By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline{L(R)}$.

Well, that's not true. You won't get $\overline{L(R)}$. That would have happened if $M$ was a DFA, rather than a NFA. So you have to first convert $M$ to $M'$ which is a DFA, but then you would have to spend an exponential time there.


2-opt vs 3-opt comparison I have a question regarding performance of 2-opt and 3-opt algorithms.

I tried implementing the 3-opt and 2-opt algorithms and most of the time 3-opt outperforms the 2-opt algorithm around 5%.

Surprisingly, in few cases my 2-opt algorithm outperforms the 3-opt algorithm. I am wondering, is it some kind of error or it may happen that the 2-opt algorithms sometimes end in the better local optimum?

(I know that if solution is 3-opt, then it is also 2-opt. But we can find multiple 2-opt or 3-opt solutions in the same route, don't we?)

Your experiments show that 2-opt could outperform 3-opt. The reason is that there are many local optima, and some of the are better than others. Local search guarantees reaching a local optimum with respect to the moves being considered, but it doesn't provide any guarantee beyond that. It could be that one point which is locally optimal with respect to 2-opt is better than another point which is locally optimal with respect to 3-opt.

You can modify your algorithm to first try local search with respect to 2-opt and then with respect to 3-opt, and take the better solution. You could improve this by running a 3-opt local search starting at the 2-opt local minimum.

There are other degrees of freedom in the local search algorithm: for example, when there are several possible local improvements, which do you choose? A uniformly random one? The first one you found? The one which results in the best improvement? A random one chosen in proportion to the improvement? And so on. Each of these could result in a different solution. If you use a randomized strategy, each single run using the same heuristic could result in a different solution, so it makes sense to run local search many times.

An even more drastic option would be to replace local search with simulated annealing, which sometimes allows taking a local change which worsens the situation a bit. This might fare better on some instances.


Finding minimum path in a matrix algoritm I'm looking for an algorithm that do the following thing.

Given $n$ the number of rows and columns of a matrix of positive integers.

Given $(x_1,y_1)$ the starting coordinates.

Given $(x_2,y_2)$ the ending coordinates.

and $k$ an integer.

This are some rules of how you can travel through the matrix:

When stepped in some coordinate $(x,y)$ with a given value $w$, you can travel to $(x \pm w,y)$ or any value between this range or $(x ,y \pm w)$ or any value between this range.
Also you can spend the integer $k$ in order to travel a little further in a row or a column. For example with $k=4$ you can travel to $(x ,y + w + 3)$ spending $3$ of your $k$. In this case, now you only have $k=1$ to spend.

The objective here is find the minimum path between $(x_1,y_1)$ and $(x_2,y_2)$.

I already implemented an algorithm that do this in $O(n^3k)$, the problem it's that given the implementation it's very difficult to justify its correctness.

How would you resolve this problem in a way that is easily shown it's correctness?

A conceptually simple approach is to form an unweighted graph with $(k+1)n^2$ vertices: one copy of the matrix for each possible number of credits remaining.  Each edge represents a way you can travel in a single step.  You start at $(x_1,y_1,k)$ and want to end at $(x_1,y_1,0)$.  Now, look for the shortest path in this graph.  There is a straightforward algorithm to find the shortest unweighted path in such a graph.  Also, any good algorithms textbook will tell you how to justify its correctness.

This should produce an approach where it is very easy to justify its correctness.  Its running time is not the best possible, but it's not too terrible, either.  The running time is something like $O(n^2 k^2 w)$: the degree of each vertex is $O(kw)$, and there are $O(n^2 k)$ vertices, so $O(n^2 k^2 w)$ edges in total.  This is $O(n^3 k^2)$, so not too much slower than your algorithm.  If your primary criterion is ease of justifying correctness, this might be a simple solution.


How does the number of clauses affect the difficulty of a 3-SAT problem? What is the relationship between the number of clauses and the difficulty of a 3-SAT problem?

In general, there is no connection. An instance with a "small" number (say a few thousands) of clauses can be very difficult to solve in practice, while an instance with a "large" number (say several millions) of clauses is easy. It's the structure that matters, not the number of clauses.

For random 3-SAT, you can have a look at the satisfiability threshold.


Generate algorithmically all grid points inside a hypercube $\def\R{\mathbb{R}}\def\Z{\mathbb{Z}}\def\n#1{\|#1\|_\infty}$The problem comes directly from computational mathematics, and can be stated as follows:

Given a regular matrix $M\in\R^{d\times d}$, find effectively all vectors $v\in\Z^d$ such that $\n{Mv}\leq1$, where $\n{Mv}$ is the maximal component of the vector in modulus.

I give an algorithm below, but it's very inefficient, since it has much more steps than the number of grid points. It is still bearable for $d=5$ in my case, but it fails completely for $d=6$, I don't have that much time; moreover, I'd like to make some work on higher dimensions as well.

My current algorithm is based on the following (disclaimer: contains more math):
First, compute $\n{M^{-1}}$. Then, we observe that $\n{v}\leq\n{M^{-1}}\n{Mv}\leq\n{M^{-1}}$. This means that we can compute $L=\operatorname{floor} \n{M^{-1}}$ and then try all vectors $v\in\lbrace-L,-L+1,\dots,L-1,L\}^d$; there is exactly $(2L+1)^d$ of them. (And here lies the problem: if $d=6$ and $L=18$, I get $2.5{\rm\small E}9$ iterations, which is orders of magnitude larger than the number of points I think there are.)

Here's another way of looking at the problem: You have a lattice generated by the columns of $M$. Use the Lenstra–Lenstra–Lovász (LLL) algorithm to obtain a reduced basis of this lattice. If you replace $M$ by a new matrix formed by the output of LLL, then the columns of $M$ will still generate the same lattice, but the basis vectors will be closer to being orthogonal to one another, and the entries of $M^{-1}$ should have smaller magnitude.

From there, it would also help to bound each component of $v$ separately: i.e., you can bound the $i$th component $|v_i|$ by $\sum_{j=1}^d |(M^{-1})_{ij}|$. (By the way, the bound $\|v\|_\infty \leq \|M^{-1}\|$ is not correct; we need to use the sum of the elements on each row, not the maximum.)

For values of $d$ up to about 30, the LLL algorithm will finish practically instantly. Asymptotically, it takes $O(d^6)$, so it will slow down for very large $d$, but at the same time the number of points we need to check grows exponentially in $d$, so the run-time of the LLL is not really the bottleneck. On the other hand, the savings in the number of points needing to be checked can be enormous. I wrote some GAP code to generate a random regular (stochastic) matrix $M$ and compare the bounds on the components of $v$ that we obtain using the original basis, compared to the LLL-reduced basis (By the way, we do not need to assume that the matrix is regular; I made this restriction only because this was the case in your application):

d:=8;
M:=IdentityMat(d);
for i in [1..d] do
  for j in [1..d] do
    M[i][j]:=Random([-10^8..10^8]);
  od;
  M[i]:=M[i]/Sum(M[i]);
od;
L:=LLLReducedBasis(M).basis;
MM:=M^-1*1.0;
LL:=L^-1*1.0;
for i in [1..d] do
  for j in [1..d] do
    MM[i][j] := MM[i][j]*SignFloat(MM[i][j]);
    LL[i][j] := LL[i][j]*SignFloat(LL[i][j]);
  od;
od;

Print("Bounds for original basis: ");
ones:=[1..d]*0+1;
v:=MM*ones;
for i in [1..d] do
  v[i]:=Int(Floor(v[i]));
  Print(v[i]);
  Print(" ");
od;
Print("\n(");
Print(Product(v*2+1));
Print(" points to check)\n");

Print("Bounds for LLL basis: ");
v:=LL*ones;
for i in [1..d] do
  v[i]:=Int(Floor(v[i]));
  Print(v[i]);
  Print(" ");
od;
Print("\n(");
Print(Product(v*2+1));
Print(" points to check)\n");

The following output (based on the default random seed, with $d=8$) is not atypical:

Bounds for original basis: 9 23 24 4 23 16 23 4
(258370076349 points to check)
Bounds for LLL basis: 3 3 2 2 3 4 2 3
(2701125 points to check)

Edit: This problem is a special case of the general problem of enumerating lattice points in convex polytopes, which it turns out is a well-studied problem, and there are more efficient algorithms than the one described above. See this this paper for a survey.


Are $AC^{0}$ algorithms interesting to research communities? I have seen many research papers with log space algorithms, but not many with $AC^0$ algorithms. Is there any reason for this.

Question : Are $AC^{0}$ algorithms interesting to research communities?

$\mathsf{AC^0}$ algorithms are quite weak. For example, $\mathsf{AC^0}$ cannot compute parity or majority. However, it can compute approximate majority, as shown by Ajtai; see Viola, On Approximate Majority and Probabilistic Time, for a better construction and for references to Ajtai's work.

$\mathsf{TC^0}$ is a slightly stronger class, also consisting of polynomial size circuits having constant depth, but allowing threshold gates. Such circuits can compute division, as shown by Hesse, Division is in Uniform $\mathsf{TC^0}$, improving on works of others (starting with Beame, Cook and Hoover). The related problem of iterated integer multiplication is also in $\mathsf{TC^0}$.


"OOD allows ADTs to be created and used." I just had a CS mid-term and one of the questions was:

  OOD allows ADTs to be created and used.

  True
  False

I answered false, but my answer was marked as incorrect. I suspect what the question means is "objected-oriented design can be used to implement abstract data types", but if that's what it means it seems very clumsily worded to me. My rationale for answering false was ADTs are conceptual and exist outside of any particular programming paradigm, so "creation" of an ADT is purely a theoretical exercise.

To me it seems like the question is analogous to saying "OOD allows algorithms to be created". You might use OOD in the implementation of an algorithm, but it has nothing to do with its creation.

Would I be right in appealing my mark? My professor is kind of an idiot and I've already corrected him on several other points throughout the term, so I'm trying to avoid antagonizing him if I'm wrong.

First, if this is exactly the sentence on the exam and not your translation, it's ambiguous. It could mean that OOD is one possible way to create and use ADT, or that creating and using ADTs requires OOD.

Furthermore, ADT can mean two things: abstract data type or algebraic data type. The two concepts are completely different but are often confused. An algebraic data type is a type that is defined by its recursive structure, or equivalently by the ways to build an object of that type. An abstract data type is a type that is defined by its properties, with the way to build objects remaining hidden.

The second interpretation — that you need OOD for ADTs — is definitely false. There are programming languages which have no object orientation whatsoever but have ADTs in one sense or the other or both. Standard ML is a prime example: record and sum type definitions provide algebraic data types, while the module system provides abstract data types.

The first interpretation — that ADTs can be implemented with OOD — is contentious, because it depends on terminology that isn't standard. In typical languages that provide objects, you can build algebraic data types: define several implementations of a class to make a sum type, and put multiple fields in a class to make a product type. However this is not intrinsic to object-oriented programming. Regarding abstract data types, most object-oriented languages provide some kind of abstraction facility by hiding the implementation of a class under some interface. However, this isn't intrinsic to OOP: the key feature of objects is inheritance, and you can have inheritance without any abstraction whatsoever.

The question may be making a difference between object-oriented design and object-oriented programming construct, but OOD isn't really on the same plane as ADTs.

All in all this is a poorly-worded exam question. The connection between OOD and ADTs is an interesting subject, but the question is not phrased in a meaningful way.


Transition Function in MDP I got a question about who and how sets the transation function values in markov decision processes?
I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right by %10 each. How did he know that? Do we have to determine the transition probability for each step or agents have to? Simply, it should be non-deterministic process, so how could someone tell the probability of that transition?
It should be %25 for each direction!!

I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right by %10 each. How did he know that?

There are a couple of scenarios that could lead to an agent stepping up with probability 0.8 and left/right with probability 0.1/0.1. The simplest case, and the one you would likely encounter first is that the agent takes an action determined by the agent's policy but the environment dynamics do not map that state-action pair deterministically to a next state, but to a distribution over possible next states. Then taking the same action in the same state multiple times will not always result in the same transition. The agent may choose to go up, but the environment dynamics assign a small probability that if the agent moves up while in the current state the agent may end up moving left or right instead. The dynamics are a feature of the environment, they are independent of the agent, for example they may be observed probabilities in a video game which was developed by other people than the ones develop the RL algorithm to play it.
Another scenario that could explain the probabilities you asked about is the agent could learn a stochastic policy, meaning instead of using a deterministic policy $$\pi:S\to A$$
The agent uses a stochastic policy $$\pi:S\to prob(A)$$ which maps states to probability distributions over actions. In this case, even if the environment is deterministic the agent may choose to move up with probability 0.8 and left or right with probability 0.1 each.

It should be %25 for each direction!!

This could happen if the environment dynamics did not allow the agent to make a meaningful choice at that state, or the agent's policy assigned each action an equal probability at that state. RL agent's are often explicitly programmed to behave highly randomly in the beginning, maybe even following a uniform random policy, which would assign a probability of .25 for each direction in each state. The amount of random actions the agent takes is then annealed over time as more information is obtained about the environment and the estimate of the value function is refined.