When and how to generate parse tree while top down parsing I am trying to build a parser that will eventually output a 3 address code.

My question is, how do I build the parser to go from parsing in a table driven top down parsing to then give me a parse tree?

I am looking for more psudo code than anything. Not anything concrete. For example, I have a table with the first and follow sets of all non-terminal. I take this non terminal and do the standard parsing technique for table driven parsing.

When and how do I take those choices for the parsing to create the parse tree?

Below is the grammar I am trying to parse out, I take the corresponding first and follow sets to the grammar and the parse out the input using the table driven parsing technique.

Grammar

  expr        ::= term {addop term}
  term    ::= factor {mulop factor}
  factor     ::= variable| unsigned-number| ( expr)
   variable ::= identifier
  addop ::= + | -
  mulop ::= * | /

As the name indicates, the parse tree is generated top-down. Specifically, you start with a place-holder node for the start symbol. Each time you predict a production, you fill in the placeholder with the right-hand side of the production, where each symbol is represented by a placeholder. Each time you shift over a token, you fill in the placeholder with the token's semantic value.

Since parsing nodes are expanded into the tree before their children, it's not possible to compute synthesized attributes with this algorithm, although inherited attributes can be computed when the node is predicted. You can slightly modify the algorithm to allow the computation of synthesized attributes by adding an "end production" pseudo-token at the end of every production. When a such a token is encountered, instead of shifting a token from the input, the code associated with the production is executed to fill in the synthesized attributes. However, it might be easier to compute attributes post-parse by performing one or more traverses over the parse tree.


Shifted Big Os. How to say O((n+c)!) = O(n!)? Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is
$nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$
Strictly, there is no constant factor that would make $n!$ greater than $(n+1)$, but it seems pointless to indicate that there is a constant shift.
Is it ok to write $O((n+c)!) ≈ O(n!)$ or even $O((n+c)!) = O(n!)$, when $c$ is constant?

No, $(n+1)!$ is not $O(n!)$.  There is no constant factor $c_0$ so that $(n+1)!$ is at most $c_0 \times n!$.
You can say that $(n+1)!$ is in $O(n! \times \text{poly}(n))$.  Here $\text{poly}(n)$ represents the class of functions that grow polynomially fast in $n$; so in other words, this statement says that there is a polynomial $p(n)$ so that $(n+1)!$ is in $O(n! \times p(n))$.  Indeed, it is also true that $(n+c)!$ is in $O(n! \times \text{poly}(n))$.  This may be enough for your purposes.
Sometimes people may define new notation for this kind of case.  For instance, if we are dealing with functions that grow exponentially fast, and we don't care about a factor of $n$ (which grows much more slowly than any exponential function), we might define $f(n) = O^*(g(n))$ if $f(n)$ is in $O(g(n) \times \text{poly}(n))$.  Then it is true that $(n+c)!$ is in $O^*(n!)$.


Yes.  This page says there are 98 5-state Turing machines whose halting statuses are unknown.  Annoyingly, it does not give any examples of such machines, but this 26-year-old page gives 2 5-state Turing machines whose halting statuses were apparently unknown at that time.  (Searching for "simple counter" will take you right between those 2.)  I copied them here in case that link goes down:

Input Bit   Transition on State     Steps            Comment
             A   B   C   D   E

    0       B1L C1R D0R A1L H1L   > 2*(10^9)       ``chaotic''
    1       B1R E0L A0L D0R C0L

    0       B1L A0R C0R E1L B0L       ?        complex ``counter''
    1       A1R C0L D1L A0R H1L


Proving the lower bound of compares in comparison based sorting I'm reading Sedgewick and Wayne's book of Algorithm. When I read the following proof in the attached picture, I don't understand why it assumed the comparison number is lg(number of leaves). Any help is appreciated!

A sorting algorithm using at most $h$ comparisons on all inputs corresponds to a tree of height at most $h$. Such a tree has at most $2^h$ leaves. On the other hand, each permutation of $1,\ldots,N$ must land at a different leaf, and so there must be at least $N!$ leaves. Putting these together, we deduce that $2^h \geq N!$ and so $h \geq \log_2 N! = \Omega(N\log N)$ (using Stirling's approximation). So every sorting algorithm must use at least $\log_2 N! = \Omega(N\log N)$ comparisons in the worst case (on some inputs it can use less).


Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness? NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction.
According to these posts :
Why not polynomial-space reductions for $PSPACE$-hardness?
PSpace-completeness under PSpace reductions
Every PSPACE language would be PSPACE-Complete if we defined completeness using a
Poly-SPACE reduction (instead of a poly-TIME reduction).
My question is, why does Log-space reduction doesn't imply completeness for every $L \in NL$, for the same reasoning?
Take any A,B $\in$ NL , and fixed $y,n$ s.t $y\in A$ and $n\notin A$.
We can define the following log-space reduction $f$ :
$$f(x)=\begin{cases}\ y&\text{if }x\in A\\
                    \ n&\text{if }x\notin A.\end{cases}$$
Just solve A in log-space and let our output be the fixed instance according to the right case.
How come log-space reductions are NOT useless for NL completeness while Pspace reductions are useless for PSPACE completeness? What am I missing ?

Your reduction $f$ works in nondeterministic logspace, which is conjectured to be stronger than logspace. Assuming this conjecture, it follows that the concept of NL-completeness is not trivial, that is, not all problems in NL are NL-complete; in particular, problems in L are not NL-complete.

What might be confusing you is that PSPACE=NPSPACE, which is proved using Savitch's theorem. In the context of logarithmic space, the theorem only shows that problems in NL can be decided in space $O(\log^2 n)$.


Does register renaming remove all kinds of WAR hazard? For the following two instruction

[Note: MOV Destination, Source ]

i1 : MOV R1, R2
i2 : ADD R2, R3

Since i1 is reading from R2 and i2 is writing to R2 there is a WAR data dependency and by register renaming like below we can remove this hazard

i1 : MOV R1, R2
i2 : ADD R4, R3

What are the other possible situations where such WAR hazard can occur ? and does register renaming solve all kinds of WAR hazard ?

Write-after-read (WAR) hazards are pervasive throughout all of computer systems, although different subfields call it different things.  Renaming of one kind or another (and called one thing or another) is the most general method I can think of for working around these kinds of problems.

Register renaming is the form of renaming used in CPUs that want to expose more instruction-level parallelism.  It can be made relatively efficient because the number of programmer-visible register names on most architectures is bounded and small.

From a computer architecture point of view, an additional problem for write-after-read hazards is dealing with load and store operations to main memory.  Register renaming won't help with this problem, because the space of visible memory locations is enormous compared to the number of available registers.  For this problem a different kind of "renaming" is done where store operations are buffered in a store queue for a period of time.  The store queue can be made relatively small because on most CPUs the number of stores that we want to have "in-flight" simultaneously is relatively small.  Thus the store-queue can be relatively small and we can afford to have every load operation perform an associative search of the store queue.

But the renaming concept is fundamental outside of computer architecture too.  An analogous situation occurs in the implementation of any programming language with automatic local variables (which is most programming languages.)  You can view the locally declared variables in the source code as analogous to register names and activation records (stack frames) as analogous to renamings of the registers.  This concept is leveraged in several parallel programming languages, for example in the Id programming language (one of the precursors to Haskell) and the Cilk programming language (an extension to C) the fact that each procedure writes its local variables in a different activation record is used to allow procedure calls to execute in parallel.

In transaction processing systems used in large databases multiversion concurrency control is analogous to renaming.  Each transaction sees, and modifies, its own "snapshot" of the entire memory and the snapshots are committed atomically.  The snapshots are generally implemented using techniques that are more similar to store queues than to register renaming.

Renaming is also a fundamental technique used in non-blocking synchronization.  Suppose you have some container data type (like a map) where you have a unique pointer to the root of the implementation.  You can implement lock-free atomic operations by copying the pointer, allocating a new data structure, copying the entire data structure from the old copy to the new, modifying the new version and then trying to compare-and-swap the pointer to the new copy for the pointer to the old copy.  Copying an entire data structure would be ridiculously expensive, so in general if you want to do this you would use purely functional data structures.

If you couldn't already tell, this is my favorite topic, and I could go on for hours.  So I'll stop here since I've probably written way more than you wanted.


Constraint propagation using Projection rule I've found this example of constraint propagation using projection rule

We have

C = { x1 ≠ x2, x1 ≥ x2 }

< C; x1 ∈ {1,2,3}, x2 ∈ {1,2,3} >

They say that applying propagation rule, does not give any simplification.

I'm not sure why this is the case. Shouldn't we get?

< C; x1 ∈ {2,3}, x2 ∈ {1,2} >

Other steps in the example, make sense that to me, e.g.

< C; x1 ∈ {2}, x2 ∈ {1,2,3} >

produces

< C; x1 ∈ {2}, x2 ∈ {1} >

You apply the propagation rule to a single constraint.

The rules are defined in such a way that they can be applied efficiently.
Otherwise, by applying the "generalized propagation rule" you could declare that a SAT instance is unsatisfiable in a single step.


How can I show a linear languages are closed against concatenating with regular ones? This was given as a homework problem but I have already submitted the assignment.  I'd like to resolve it at this point for my own satisfaction.

Given that $L_1$ is a linear language and $L_2$ is a regular language, show that $L=L_1L_2$ is a linear language.

Recall that a linear grammar $G=(\Sigma, V, P, \sigma)$ has productions $A\to yBz$ for some $y,z \in \Sigma^*$ and $A,B \in V$.

I use the theorem that every regular language can be represented by a right linear grammar.

Then I use the theorem that every right linear grammar is the reverse of a left linear grammar (being a little careful about what I mean by reverse)... $L(rev(G))=rev(L(G))$...

Next each left linear grammar is the reverse of a regular language, but the reverse of a regular language is regular, so left linear grammars also represent regular languages.

So our productions in $L_2$ are of the form $x \to Ca \mid a$ for some $C \in V_{L_2}$ and $a \in \Sigma_{L_2}$.

Now on to the show...

What we are looking for is $L = L_1.L_2$, $L$ is linear (to show).

So this has the form $S \to yBzCa \mid yBzaa$

So far so good, the second production is linear and within our expectations for set inclusion.

I'm having a devil of a time reducing $yBzCa$ however ...

If I introduce $V\to BzC$ that linearizes $S$ but $V$ is not linear ...

If I give $T\to z$ to get $V\to BTC$ I'm not much better off

If I use $V_1\to Bz$ (ok linear!) but then $V\to V_1C$ (not linear)

What is the piece of the puzzle I'm missing?

I have a suspicion that my woes are because I failed to have a production that is $B\implies^*a$ for some terminal $a \in \Sigma_{L_1}$ but I haven't observed that in the definitions thus far... and further unless B only goes to a terminal I'm in the same mess (if $B\to t$ where $t \in \Sigma_{L_2} \bigcup {\epsilon} $ then I think I'm finished but how do I justify it?

The piece of the puzzle is not to start $L_1$ and $L_2$ in parallel, but to first generate the regular suffix (strings in $L_2$), then (when the left-linear grammar finishes) continue with the linear prefix (strings in $L_1$).

(added, deadline closed) Thus we assume we have grammar $G_i = (\Sigma,V_i,P_i,S_i)$ for language $L_i$, where $G_1$ is linear, and $G_2$ is left-linear, following your own suggestion, and generates the regular language "in reverse".
Given two strings $w_1$ and $w_2$ in the respective languages, having derivations $S_1 \Rightarrow^*_{G_1} w_1$ and $S_2 \Rightarrow^*_{G_2} B w' \Rightarrow_{G_2} w_2$, we glue these together as
$S_2 \Rightarrow^*_{G_2} Bw'\Rightarrow S_1 w_2 \Rightarrow^*_{G_1} w_1 w_2 $. Thus, first generate $w_2$, in the last step switching to the axiom $S_1$ of $G_1$, then generate $w_1$.

Technically this is achieved by requiring $V_1 \cap V_2 = \varnothing$, choosing all productions in $P_1$ and $P_2$ except that "final" productions $A\to a$ with $a\in\Sigma$ in $P_2$ are changed into $A\to S_1a$.


What is the intuition behind Strassen's Algorithm? I came across Strassen's algorithm for matrix multiplication, which has time complexity $O(n^{2.81})$, significantly better than the naive $O(n^3)$. Of course, there have been several other improvements in matrix multiplication since Strassen, but my question is specific to this algorithm.
If you see the algorithm, you'll notice that 7 matrices $M_1$ to $M_7$ have been defined as intermediate computation steps, and the final matrix product can be expressed in terms of these. I understand how to verify this claim, and arrive at the expression for the desired time complexity, but I'm unable to grasp the intuition behind this algorithm, i.e. why are the matrices $M_1$ through $M_7$ defined the way they are?
Thank you!

The real answer to this question is that if you play with it long enough, you'll hit an algorithm requiring 7 multiplications – not necessarily the same as Strassen's, but an equivalent one, in a certain sense: it is known that all such algorithms are equivalent, as shown by de Groote in his 1978 paper, On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for 2 × 2-matrix multiplication.
There are many attempts in the literature to explain how one could come up with such an algorithm, for example:

Gideon Yuval, A simple proof of Strassen’s result, 1978. We explain this approach below.
Ann Q. Gates, Vladik Kreinovich, Strassen's Algorithm Made (Somewhat) More Natural: A Pedagogical Remark, 2001. The idea is to use symmetries to guess the linear combinations corresponding to one of the matrices being multiplied, and then to pair them intelligently with linear combinations of the other matrix.
Jacob Minz, Derivation of Strassen's Algorithm for the multiplication of 2×2 matrices, 2015. The idea is to apply linear transformations to obtain a simpler looking problem, and then to solve it by hand.
Christian Ikenmeyer, Vladimir Lysikov, Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective, 2017. The idea is to consider a basis for the $2\times 2$ traceless matrices, and use its multiplication table to construct Strassen's algorithm.
Joshua A. Grochow, Christopher Moore, Designing Strassen’s Algorithm, 2017. The idea is to start with vectors which form the vertices of an equilateral triangle in the plane, and use elementary properties of these vectors to come up with an algorithm.

Gideon Yuval shows how you could come up with Strassen's algorithm. The starting point is to convert matrix multiplication to the problem of computing a matrix-vector product: computing
$$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \times \begin{pmatrix} e & f \\ g & h \end{pmatrix} $$
is the same as computing
$$
\begin{pmatrix}
a & 0 & b & 0 \\
0 & a & 0 & b \\
c & 0 & c & 0 \\
0 & d & 0 & d
\end{pmatrix}
\times
\begin{pmatrix} e \\ f \\ g \\ h \end{pmatrix}
$$
Suppose that we could write the matrix on the left as a sum $\ell_1 M_1 + \cdots + \ell_7 M_7$, where $\ell_i$ is a linear combination of $a,b,c,d$ and $M_i$ is a rank one matrix, say $M_i = x_i y_i^T$. The product we are after is thus
$$
\sum_{i=1}^7 \ell_i M_i \begin{pmatrix} c\\d\\e\\f \end{pmatrix} =
\sum_{i=1}^7 \ell_i x_i y_i^T \begin{pmatrix} c\\d\\e\\f \end{pmatrix} =
\sum_{i=1}^7 \ell_i r_i x_i,
$$
where $r_i$ is a linear combination of $e,f,g,h$. This shows that each entry of the product matrix is some linear combination of the products $\ell_i,r_i$.
Let us now show how one could find the decomposition. We start by cancelling the top left and bottom right entries, in a way which avoids hitting zero entries:
$$
\begin{pmatrix}
a & 0 & b & 0 \\
0 & a & 0 & b \\
c & 0 & d & 0 \\
0 & c & 0 & d
\end{pmatrix} =
\begin{pmatrix}
a & 0 & a & 0 \\
0 & 0 & 0 & 0 \\
a & 0 & a & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & d & 0 & d \\
0 & 0 & 0 & 0 \\
0 & d & 0 & d
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & a-d & 0 & b-d \\
c-a & 0 & d-a & 0 \\
0 & c-d & 0 & 0
\end{pmatrix}
$$
This results in a mess, which we try to fix by "flipping" the inner square:
$$
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & a-d & 0 & b-d \\
c-a & 0 & d-a & 0 \\
0 & c-d & 0 & 0
\end{pmatrix} =
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & a-d & a-d & 0 \\
0 & d-a & d-a & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & 0 & d-a & b-d \\
c-a & a-d & 0 & 0 \\
0 & c-d & 0 & 0
\end{pmatrix}
$$
Since $d-a = (b-a)-(b-d)$ and $a-d = (c-d)-(c-a)$, it is easy to represent the last matrix as a sum of four rank one matrices:
$$
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & 0 & d-a & b-d \\
c-a & a-d & 0 & 0 \\
0 & c-d & 0 & 0
\end{pmatrix} =
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & 0 & b-a & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & d-b & b-d \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & c-d & 0 & 0 \\
0 & c-d & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
c-a & a-c & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix}
$$
In total, we obtain the following representation:
$$
\begin{pmatrix}
a & 0 & b & 0 \\
0 & a & 0 & b \\
c & 0 & d & 0 \\
0 & c & 0 & d
\end{pmatrix} =
\begin{pmatrix}
a & 0 & a & 0 \\
0 & 0 & 0 & 0 \\
a & 0 & a & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & d & 0 & d \\
0 & 0 & 0 & 0 \\
0 & d & 0 & d
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & a-d & a-d & 0 \\
0 & d-a & d-a & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & b-a & 0 \\
0 & 0 & b-a & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & d-b & b-d \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & c-d & 0 & 0 \\
0 & c-d & 0 & 0
\end{pmatrix} +
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
c-a & a-c & 0 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix}
$$


Given a PRAM may use arbitrarily many processors, why is Hamiltonian Cycle not in NC? In my parallel algorithms class, the PRAM model is described as having an "arbitrary number of processors, bounded by some polynomial in the input size."

I think that this may be missing a constraint.  For example, this would imply that finding a Hamiltonian cycle is in NC:

If I give all of the permutations of the vertices of a graph as input,
then I can assign a processor to each permutation, and each processor can
then check for the appropriate edges in O(|E|) time, which would mean that
finding a Hamiltonian cycle would be in NC.

So is there some constraint that is missing from the definition we are using in class, or am I missing something else?

Edit

For clarification:  Consider a classical TM, which accepts as input a sane representation of a graph, followed by all of the permutations of a graph's vertices.  It then performs the best currently known algorithm for finding Hamiltonian Cycles, and as output writes out a permutation of the vertices describing such a cycle.

The algorithm would perform in time linear in the input size, but in time factorial in the order of the input graph.  (The extra inputs don't seem to count as computations for a classic TM.)

In the PRAM model (as I have described it), the algorithm would perform in time linear in both the input size, and in the order of the graph.  (The extra inputs seem to count as computations for the PRAM model...  Which makes me think that "computation" means something subtly different here...)

If this is the way it is supposed to work: awesome.  If not, than am I missing some constraints on what the allowed inputs are?

If I give all of the permutations of the vertices of a graph as input

That's not the input for Hamiltonian Cycle; you only get the graph.

  then I can assign a processor to each permutation

Since there are $n! \in \omega(c^k)$ many permutations, you don't have that many processors.

Here's the twist: if you were allowed to use all permutations as input, you'd of course have polynomially many processors in $n!$ at your disposal. But since your input is the graph you only get polynomially many in $n$.


Vertex cover problem modification such that every vertex is connected to the set, NP-Hard? Being new to complexity problems, I've met a question that is quite similar to the Vertex Cover Problem and I am not sure if this one is NP-Hard. We know that the vertex cover problem is the following: given a graph $(V, E)$, selecting a set of vertices $S$ such that every edge $e \in E$ in the graph is connected to some vertices in $S$. The problem of minimizing the vertex cover problem is a well-known NP-hard problem.

My question is the following: given a graph $(V, E)$, selecting a set of vertices $S$ such that every node $v \in V$ is either in $S$ or connected to the nodes in $S$. Is this problem of minimizing the set of $S$ NP-Hard? This problem seems to be quite intuitive after learning the vertex cover problem, but I didn't find a similar question after searching. I apologize if I asked duplicated questions.

This is called the Dominating Set problem, and it is indeed NP-hard. In fact, it's in some sense harder than Vertex Cover, since it's not fixed parameter tractable (FPT) with respect to the solution size $k$.


Draw a graph of DFA for a regular language I'm trying to draw a DFA graph for the regular language where every chain:

* consists of symbols from the set {1,a,b}.
* starts with the subchain '1a'.
* includes at least one subchain 'aa'.

Output chains: $1aa, 1abaa, 1aaba, 1aaa, 1aaab, 1aab1a, \space ..., \space etc.$

There's no problem with checking the $'1a'$ subchain, but there's a problem with the double repeating action for an $'a'$ terminal in any part of the chain for getting at least one $'aa'$ subchain. The shortest chain here is $'1aa'$ and graph states change from $q_0$ to $q_3$ (which will possibly be the DFA's end state). If I draw a $(1,b)$-cycle for the $q_2$ state, the DFA might come to the end state $q_3$ on reading the wrong chain like $1aba$. From the other side, my DFA will only allow chains starting from $1aa$ (not $1a$) and that is not correct either.

My attempts leaded to this:

What should I correct here to add "at least one $'aa'$ check" feature? Or offer your version of this DFA graph.

$T$ is a 'trap state' $q_3$ is final accepting state. From state $T$ all inputs $a$, $b$, $1$ will direct to $T$ itself. There's a self loop over state $q_4$ for inputs $1$ and $b$.


Proving that a language satisfies the pumping lemma condition I have to proof that $L = \{ a^{2i} b^{2j} \mid i,j \in \mathbb{N} \}$ is a regular language, and how it meets the Pumping Lemma condition.

For the PL, there is a string $xyz \in L$ such that $y \neq \epsilon$ and any string $xy^nz$, for any $n \ge 0$, is in $L$.

From what I understand, I cannot use the pumping lemma to prove that a language is regular.

I am a bit puzzled how I have to show that this $L$ meets this condition.
Do I have to divide a string into $xyz$ again?

The language is regular since it is the language of the regular expression $(aa)^*(bb)^*$.

Every regular language satisfies the conditions of the pumping lemma – this is precisely the statement of the pumping lemma! So one way to show, from first principles, that this language satisfies the conditions of the pumping lemma would be to just repeat the proof of the pumping lemma.

However, in this case we can show this more directly. We will show that the pumping lemma holds with a pumping constant of $p = 2$. Suppose that $w = a^{2i} b^{2j} \in L$. Note that $|w| \geq 2$. We consider two cases:

Case 1: $i \neq 0$. In this case, we can break $w$ in the following form: $x = \epsilon$, $y = a^2$, $z = a^{2(i-1)} b^{2j}$. We have $w = xyz$, $|xy| = 2 \leq p$ and $y \neq \epsilon$. For every $n$, $xy^nz = a^{2(i-1+n)} b^{2j} \in L$.
Case 2: $i = 0$. In this case, $j \neq 0$. We break $w$ into $x = \epsilon$, $y = b^2$, $z = b^{2(j-1)}$. The rest of the proof is very similar.


undirected graph without weights and DFS following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times.

check that G is bipartite.
check G has one simple cycle.
find number of connected component G
with given two vertex u, v, find a path between u and v with minimum edges

anyone can describe, how the authors of this note claim that all of them can be checked with DFS and in O(|V|+|E|) times?

The time complexity of DFS is O(|V|+|E|), therefore if one can solve these problems with DFS, it follows their time complexity is also O(|V|+|E|), remains only to proof that complexity, for which I should recommend a reading on Cormen.

1) To check if G is bipartite, tag each visited vertex with a color. Initially, all vertex are, say, WHITE. When you start the DFS with a vertex, tag it with RED. Everytime a RED vertex visits a WHITE vertex, tag that WHITE vertex with BLUE, and when a BLUE vertex visits a WHITE vertex, tag it with RED. If a vertex visits another vertex of the same color, then that graph is not bipartite. This is because a graph is bipartite if and only if it is 2-colorable, that is, its chromatic number is 2. In short, every pair of adjacent vertices of that graph can be colored with 2 different colors, and only 2 colors are needed to color the entire graph.

2) Here, a similar approach, but with only WHITE and BLACK. All vertices are initially WHITE. Start the DFS in a vertex and tag it with BLACK. Everytime a BLACK vertex visits a WHITE vertex, tag it with BLACK. If a BLACK vertex visits another BLACK vertex, then there is a cycle in the graph.

3) Start with a counter=1 and start the DFS. If at any point the vertices stack is empty, that is, you have backtracked all the reacheble vertices from the origin and need to access the vertex list once again, then increment the counter variable. That variable indicates the number of connected components of your graph.

4) It is NOT possible to solve this problem with DFS. It is probably a trick.
Why can't DFS be used to find shortest paths in unweighted graphs?


Understanding trap and dead state in automata Well, this sounds somewhat basic definitions, but I feel they needs to be clearly defined.

In book by Hopcroft et. al., there is an excerpt:

  ...a dead state, that is, a nonaccepting state that goes to itself on every possible input symbol...

In book by Peter Linz, there is an excerpt:

  ...the automaton finds itself in state $q_2$, with the transition $\delta(q_2,0)$ undefined. We call such a situation a dead configuration...

The same book have following excerpt too:

  ... the dfa goes into state $q_2$, from which it can never escape. The state $q_2$ is a trap state.

So I want to know if following facts are correct:

Trap state is one from which we cannot escape, that is, it has either no transitions defined or transitions for all symbols goes to itself.
I feel, definition on this page for dead state is more correct:

  Once the machine enters a dead state, there is no way for it to reach an accepting state.

So a trap state can be final or non final, since both can have either no transitions defined or have transitions for every symbol happening to itself.
Earlier I felt:

  A final state cannot be a dead state, as we can read $\epsilon$ and stay in the same state, which is final state.

But this, seems incorrect, as epsilon moves are not allowed in DFAs.
Thus trap state is always a dead state.
It does not makes sense to have non-trap dead state. I mean it makes no sense to show outgoing transition from dead state, if that transition does not lead to some final state further on its path. Thus dead state is always a trap state. Right?
As I write these points and think, now, I feel both concepts are one and the same and I am unnecessarily getting confused.
This page also has following statement:

  Techincally, this automaton is not a DFA, because it lacks transitions on most symbols from each of its states.

then it says:

  ...add a transition to the dead state from each other state $q$, on all input symbols for which $q$ has no other transition. The result will be a DFA in the strict sense.

I feel DFA (regardless of any attribute attached to it: strict or non strict) can have dead state as it does not eliminates its "deterministic" nature. Right?

The concepts you mention are not formal concepts. You can define several notions of a dead state, for example (focusing on DFAs):

A dead state is a non-accepting state with self-loops for all symbols.
As in definition 1, but we also require the state to be reachable.
A dead state is a state from which no accepting state is reachable.
As in definition 3, but we also require the state to be reachable.

If we allow some transitions to be "missing" (i.e., our definition of DFA defines the transitions function as a partial function rather than as a function) then we have more possibilities, for example:

A dead state is a non-accepting state in which all outgoing transitions are self-loops.
As in definition 1, but we also require the state to be reachable.
A dead state is a non-accepting state without outgoing transitions.
As in definition 3, but we also require the state to be reachable.

If the exact definition used matters, the concept should be explicitly defined. It is usually used in a somewhat informal way, in which the intended meaning is usually obvious from context.


Is generating MIN-3-UNSAT $\mathsf{NP}$-hard? Input: amount of variables (with minimum of $10$ since otherwise problem is unsolvable).

Output: unsatisfiable formula.

Restrictions:

Every clause contains exactly 3 variables.
Every clause differs by at least one variable.  For example, a pair of clauses $(x\lor y\lor z)\land(x\lor \overline y\lor\overline z)$ is forbidden.
Every variable must be involved.
Removing any clause makes the formula satisfiable.

No set of clauses is given as input. Is this problem in $\mathsf{FP}$ or is it $\mathsf{NP}$-hard?

The smallest formula with $n=10$ can be written as follows:

$(x_1\rightarrow(x_2\rightarrow x_3))\land(x_1\rightarrow(x_3\rightarrow x_4))\land(x_1\rightarrow(x_4\rightarrow\overline{x_2}))\land$
$(x_1\rightarrow(\overline{x_2}\rightarrow x_5))\land(x_1\rightarrow(x_5\rightarrow x_6))\land(x_1\rightarrow(x_6\rightarrow x_2))\land$
$(\overline{x_1}\rightarrow(x_2\rightarrow x_7))\land(\overline{x_1}\rightarrow(x_7\rightarrow x_8))\land(\overline{x_1}\rightarrow(x_8\rightarrow\overline{x_2}))\land$
$(\overline{x_1}\rightarrow(\overline{x_2}\rightarrow x_9))\land(\overline{x_1}\rightarrow(x_9\rightarrow x_{10}))\land(\overline{x_1}\rightarrow(x_{10}\rightarrow x_2))$

It satisfies all of the restrictions.

As you can see, it is just two unsatisfiable 2-SAT formulas one of which is implied by $x_1$ and another by $\overline{x_1}$. We can add arbitrary amount of vertices to any of these implication chains, so, generating such formula for any $n\ge10$ can be done in linear time.


Operating System: Busy waiting is not eliminated with semaphore? Why the busy waiting is not eliminated even after we put the current process into the process list and "block()"ed it? So even if the process is in waiting state we still call it "busy waiting"?

I'm reading Operating System Concepts, Silberschatz, 9th ed., pages 215~217.

So even if the process is in waiting state we still call it "busy
waiting"?

In the book, they are calling the mechanism as Busy Wait not because of the processes waiting in queue but rather for the fact that when multiple processes are trying to execute Wait() or signal() operation concurrently, they will have to busy wait.
Note that the variable "value" in the code of Wait() and signal() is a shared variable and hence critical section. Two processes should not be allowed to modify this variable concurrently. For synchronisation, we prefer the busy wait(spin lock) over non busy wait synchronisation mechanism because the code of Wait() or Signal() is pretty small and so processes which are waiting to execute "Wait()" will not have to spend much time waiting. Moreover, if you choose non busy waiting synchronisation mechanism in situation when the length of critical section is small(as it is here) then context switch overhead will waste more CPU time compared to the CPU time wasted in busy wait.
So what we have done is that we limited the busy waiting only to the critical section of Wait() and signal() operation. Earlier busy waiting was present in critical section of our application program.


Set Associative Cache - duplicate Tag In a set associative cache (in this case 4-way) what happens when you try to read an entry with e.g. the tag 0x3B and this tag appears two times within the same set. Given the first is invalid, would you search on for the second (which is valid) or simply get a miss? And why do would there be a duplicate line at all?

The CPU tests all caches ways and selects the one that is both valid and have a matching tag address. It may occur concurrently on all ways or be sequential (with a preferred way, depending on the address)

When invalidating cache lines, only the valid bit needs to be cleared, the tag address value do not need to be modified, so it may contain stray values.

(Cache lines may be invalidated by the operating system for coherency with some DMA peripherals, because of self-modifying code, by hardware cache coherency algorithms like MEI/MESI, etc. Depends on the architecture.)

You cannot have several lines that are simultaneously valid and with the same tag address [and different data].

It may occur at power-up, if registers are not automatically reinitialized, and the boot sequence may have to manually clear the cache before enabling it using special accesses and/or instructions.


Deterministic Turing Machine with infine tape in both directions Consider a deterministic Turing Machine $D$ which has an infinite tape in both directions. We don't have exact information about it; what we know is that its alphabet is $\{a, b, c\}$ and there are at least three states $q_1, q_s, q_f$ where $q_s$ is the start state, $q_f$ is the final state. At some step of the computation, all the tape is blank except one cell containing the symbol $a$, the state is $q_1$ and the head is currently at a blank cell.

I need to write states and transitions that will guarantee to enter to final state from state $q_1$ but I have difficulties since $D$ is both deterministic and with infinite tape in both directions.

You can design a Turing Machine that goes one step left, then two right, then 3 left and so on...
You don't need too much states for that: just put two markers on the tape: $b$ for the current left boundary and $c$ for the current right boundary of what you explored, and push them back from one cell each time you reach them.
You have one state $q_b$ going left until $b$ is reached, and one state $q_c$ going to the right until $c$ is reached. Plus special states to shift them by one position.

You will eventually find the $a$ letter, at which point you just go to $q_f$.


The ultimate virtual machine It seems to me that one way computer science could be divided up, is into three domains:

What is efficient for humans to represent and comprehend
What is efficient for computers to represent and process
An idealized form of how computation/problems are defined that is extremely succinct, specific, and not tied to human or computer limitations

What I am most interested in, is this third domain. I believe if a lot of effort is invested there, it will drive the advancement of the other two domains.

Towards that end, I am interested in the development of an "ultimate" virtual machine. Something with a gratuitously minimal and impoverished grammar, and an extremely advanced type system.

I am wondering if anything like this exists. I am also trying to develop something like this, with the idea that it doesn't.

I have not heard of any computational problem that cannot be solved by an Universal Turing Machine, and UTM itself fits on a single page:

https://rosettacode.org/wiki/Universal_Turing_machine

In accordance with your plan, it totally disregards human and hardware limitations, by using up both time and space extravagantly. If you disregard some limitations, the quality of an answer quickly degrades to the point of being irrelevant.

IMHO the art of computing is in seeing the equivalence classes and transforming some initial solution to re-balance resources for the specific prioritized objectives. In the absence of priorities and limitations, there is no art. This quest is provably inexhaustible and will never be possible to automate.

BTW, I am also working on a new computing platform (a CPU and a programming language) that is an order-of-magnitude better in one aspect (speed, low transistor count, low energy consumption, easy comprehensibility, short programs), while matching existing solutions on the other aspects. It is a synergy based on closer matching the actual problem and balancing the workload among transistors, microcode and high-level-code. I see a big unused slack in the current technologies, and the gains can be spent on the mentioned objectives.


Find a schedule with lowest total penalty Given a set of n jobs with [arriving time, service duration time,
  penalty per unit of time] find a schedule with lowest total penalty.

Notes:

Arriving time is the time when objects aarivies to processing system.
All objects can arrive at the same time
Processor is able to process only one object at the same time
Servicing time is the time required to process the object
Penalty is calculated as (penalty * time spent in the system), i.e. departure time - arrival time

The easiest way to understand the problem is to imagin a loggistic company with a number of trucks that are waitings loading/unloading of the cargo. Trucks arraives at a given time and can wait on a parking. There is only one terminal that process loading and unloading. It's required to find an optimal schedule of processing.

Example of the input data:

t,tau,a
5,4,12
4,6,2
9,2,1
11,4,5
13,4,5
16,3,2

The question here - which approach is required to solve this and similiar problems? I assume these algorithms are providing solutions close to a brute force.

This problem is called "minimization of total weighted flow time". It is very hard, especially when jobs cannot be preempted by the processor. Even when jobs can be preempted, it is NP-hard, so you cannot expect to have algorithms that construct optimal solutions efficiently.

If you are willing to accept non-optimal solutions, then there are efficient heuristics that find a solution of cost equal to $C$ times the optimal cost, for some large constant $C$, but they are not very practical (see the first link). A more practical approach might be to resort to a local search heuristic.


How is a communication protocol a mechanism? Given a finite set $\Sigma$ and a positive integer $n$, a mechanism is a set $\{ \mu_x \vert x \in \Sigma^n \}$ such that $\mu_x$ is a probability measure on some $\sigma-$algebra for each $x$.

Now given a communication protocol $P$ between two privately coin-flipping parties $A$ and $B$ who start with the inputs $x$ and $y$ respectively one defines this quantity called the $VIEW^A_P(x,y)$ : ``a joint probability distribution over $x$, the transcript of the protocol $P$, private randomness of the party $A$, where the probability space is private randomness of both parties"

What does the stuff in the quotes mean?
Can someone help understand how is this $VIEW^A_P(x,y)$ a ``mechanism" as defined earlier? (For this to be a mechanism, $VIEW^A_P(x,y)$ for a fixed $x$, has to assign a probability to some set of outcomes and I am unable to see as to which set of outcomes is it assigning a probability and how)

A transcript of a protocol will be a sequence of private coin tosses and bits exchanged in every step. So if one fixes both $x$ and $y$ then I can imagine that a probability can be assigned to a protocol - which would be the probability for that sequences of coin tosses to have happened. But still whaht is an "event" here is not clear since I can't see a natural way to group together these "outcomes" (each of which is now a possible transcript when started with a $x$ and $y$).

But if one fixes only $x$ then nothing is clear to me..

Reference : http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/diffprivacy.pdf

The view of Alice is what Alice gets to see; it is a probability distribution that depends on the inputs of both players $x,y$. It is a distribution over triples $(x,\tau,r_A)$, where $x$ is Alice's input, $\tau$ is the transcript of the protocol, and $r_A$ is Alice's private randomness. This probability distribution depends both on $x$ and on Bob's input $y$.

Here is how to generate this probability distribution, given a protocol $P$ and the inputs $x,y$ of both players. Generate the shared randomness $r$ according to its distribution, and Alice's private randomness $r_A$ according to its distribution. Run $P$, obtaining a transcript $\tau$. Output $(x,\tau,r_A)$.


Simplified Maximum Diversity Problem The Maximum Diversity Problem calls for choosing $m$ items from a list of $n$ items, such that the diversity defined as some metric distance between items is maximized.

I have a simpler problem, which I was hoping I could solve in a simpler manner. In my case I have a list of $n$ items each with a certain non-unique key. I want to chose $m$ items from my list so that the maximal number of items per key is minimized.

e.g., if my list is:

('a', 5), ('b', 4), ('c', 2), ('a', 6), ('b', 5)

and we must choose $m=3$ items, an optimal solution would be a list containing one item for each key.

Is there an algorithm for doing this that is simpler than those for the Maximum Diversity Problem?

The following algorithm should work.

The algorithm proceeds in several rounds. At each round, let $m'$ be the number of remaining items to take. Take one item per key, up to $m'$ items, and remove these items. If we took $m'$ items, the algorithm terminates. Otherwise, continue to the next round.

We leave the correctness proof (or a counterexample) to the reader.


Queue, moving the element at the tail to the head Suppose I have a queue where I pull from left and push to the right, and suppose I have the contents in the queue as $a b c @ d e$ (from left to right, left is head, right is tail).

Is there a simple algorithm that doesn't require extra structures that makes $e$ at the head? meaning to get us to the queue $eabc@d$?

P.S.: I need an algorithm like that for the purpose of a queue automaton.

If you can only push (enqueue) or pull (dequeue) from the queue, then your only option is to pull all the elements and re-enter them.

If you need such an operation, you can use deque (double-ended queue). See: http://en.wikipedia.org/wiki/Double-ended_queue .


Median of two sorted arrays of different size in logarithmic time? The solution given in Cormen is as follows:

Reading this solution, the first doubt that comes in my mind is what if the median lies in array B. According to this solution, we are applying binary search on A only, then how will we get the median if it lies in B. Also the pseudo code is less than understandable. Can anybody simplify it to me.

Given two sorted arrays $A[1],\ldots,A[\ell]$ and $B[1],\ldots,B[m]$, the goal is to find the median. Let's assume for simplicity that $n := \ell+m$ is odd, and that all elements are distinct. Therefore we are looking for the element which has exactly $\frac{n-1}{2}$ below it in both arrays.

Given an element in one of the arrays, it is easy to find whether it is the median, smaller than the median, or larger than the median. For example, suppose that the element in question is $A[i]$. There are $i-1$ elements below it in $A$. If it were the median, then there would be exactly $j := \frac{n-1}{2} - (i-1)$ elements below it in $B$, which would put it between $B[j]$ and $B[j+1]$. Checking whether this holds, there are three cases:

$B[j] < A[i] < B[j+1]$. In this case $A[i]$ is the median.
$A[i] < B[j]$. In this case there are fewer than $j$ elements below $A[i]$ in $B$, and so there are fewer than $\frac{n-1}{2}$ elements below $A[i]$. In other words, $A[i]$ is smaller than the median.
$A[i] > B[j+1]$. Symmetrically, in this case $A[i]$ is larger than the median.

Suppose that the median belongs to the array $A$. Using the test described above, we can find it using binary search: we start with the middle element of $A$. If it is the median, we're done. If it is larger than the median, we continue with the middle element of the first half of $A$, and if it smaller than the median, we continue with the middle element of the second half of $A$. Continuing in this way, we will eventually find the median in at most (roughly) $\log_2 \ell$ steps.

What if the median doesn't belong to $A$? Our algorithm will get stuck. Since this is an identifiable situation, this suggests an algorithm which finds the median:

Try to find the median in $A$ using binary search.
If the binary search algorithm gets stuck, find the median in $B$ using binary search.

Note that if the first step fails, the second must succeed. The overall running time is $O(\log \ell + \log m) = O(\log n)$.


Context free grammar problem for number of a's is twice the number of b's Can you to find for me a context free grammar for the following language?
$$\{w\in\{a,b\}^*: \#_a(w)=2\#_b(w)\} $$
Here $\#_a(w)$ counts the number of $a$'s in $w$.

Let $c(w)=2\#_b(w)-\#_a(w)$. Your language is exactly $\{w\mid c(w)=0\}$.
Now consider a string $w$ with $c(w)=0$ and $|w|\ge 2$. If we can split $w$ into three parts: $w=pms$ such that $c(p)$ and $c(pm)$ have different signs, i.e., $c(p)c(pm)<0$, then there are two cases:

$c(p)>0$ and $c(pm)<0$. Note each time we append a character to string $x$, $c(x)$ is either increased by 2 or decreased by 1, so we can always split $m$ into two parts $m_1m_2$ such that $c(pm_1)=0$.

$c(p)<0$ and $c(pm)>0$. In this case  we can always split $m$ into two parts $m_1m_2$ such that either $c(pm_1)=0$, or $c(pm_1)=-1$ and $m_2$ begins with $b$.

As a result, either $w=w_1w_2$ where $c(w_1)=c(w_2)=0$, or $w=w_1bw_2$ where $c(w_1)=c(w_2)=-1$.
If $w$ cannot be split into such three parts, then $w$ must be either $bw_1aa$ or $aaw_1b$ where $c(w_1)=0$.
So, if we let $S_-$  generate the language of strings where $2\#_b-\#_a=-1$, then we have the following grammar
\begin{align}
S&\rightarrow SS\mid S_-bS_-\mid bSaa\mid aaSb\mid\epsilon\\
S_-&\rightarrow aS\mid SS_-
\end{align}


Maximum number of positive literals in 2SAT MAX 2SAT is NP complete.

Instead of satisfying the maximum number of clauses, I have a fully satisfiable 2SAT formula and I want to have the maximum number of positive literals in the assignment (such that all the clauses are satisfied, of course).

What is the difficulty of this problem?

This problem is NP-hard (and in addition hard to approximate and W[1]-hard), because maximum independent set can be reduced to it. Reduction: Each variable represents a vertex and each clause represents an edge.


Circuit size for "at least n inputs are true" Say you have $m$ boolean inputs, and you are given a threshold $n$. You need to construct a boolean circuit  that evaluates to true if at least $n$ of the inputs true. You may use AND, OR, NOT, or XOR gates (restricted to fan-in two, with arbitrary fan-out). Asymptotically how small can you make this circuit?

Any reasonably tight upper bound would be appreciated. I keep on thinking of ways to recursively construct such a circuit but I can't find anything good. Also, any results for any other reasonable basis of allowed gates would also be useful.

From S. Chaudhuri, J. Radhakrishnan. Deterministic Restrictions in Circuit Complexity:

Theorem 6.1: A circuit computing $T_k^n$ with $k \leq n^{1/3}$ has $\Omega(k^2(\ln n)/\ln k)$ gates

Where $T_k^n$ is the boolean function that has the value 1 iff at least $k$ of its inputs have the value 1 (threshold function).


FInding number of ancestors at given depth I have a rooted tree with $n$ vertices.

I want to be able to answer the given queries in logarithmic time after setting up some sort of data structure (preferably in time $n\log n$.

The query is given by $v$ and $k$.

I want to find the number of ancestors of $v$ of degree less than or equal to $k$.( I call ancestors of degree $1$ sons).

I don't know how to do it.

At first I thought that I should only store the number of ancestors of $v$ of degree less than $2^j$. But this doesn't seem to work.

We do a dfs starting from the root. we save the entry-time and exit time of each vertex. We build a list containing (height(v),entrytime(v)). Where entrytime is the time in the dfs where we first reached vertex v.

we now sort our list lexicographically (this takes time $\mathcal O(n\log(n))$ ) . Inside this order, the vertices at height $h$ that are ancestors of a vertex $v$ are the elements in the list that are between $(h,entrytime(v))$ and $(h,exittime(v))$.

So the problem is essentially reduced to the following:

Suppose we have an array of integers $a_1,a_2,\dots, a_n$, given $x$ and $p$ how can we find the number of elements in the range $a_1,a_2,\dots, a_p$ that are greater than $x$? (we just need $p-k$).

Various efficient solutions to this are discussed here:


Why would you introduce the goto statement into a modern language? I just found out something really quite extraordinary.  While looking through Stackoverflow, I came across a question about removing goto from a php function.  PHP doesn't have goto I thought and looked it up on php.net.

It turns out I was sort of right.  PHP introducted goto in version 5.3 which was release in 2009.  PHP didn't start out with gotoit actually introduced it into the language in 2009!

Why on earth with all the horror stories we have from 40 years of bad programs written with goto in other languages would php actually decide to introduce it?

The php.net website even has this XKCD image suggesting no programmer should ever use goto.

Question:

What possible reason from a technical point of view could there be for introducing a the goto feature, which I nievely thought had been vanquished from modern computer programming languages?

There are two kinds of programmers: Those who for whatever reason never, ever use goto, and go to any lengths to avoid it, and those who use goto in one of the very rare situations where it is the best solution. (Someone said here in a comment that goto could be misused and programmers would find ways to misuse it - but those people are not programmers).

It makes sense to add "goto" to a language that doesn't have it if there is evidence that there are situations where it improves the code, and if it is not too difficult to implement. So I would assume that there was such evidence.


Complexity of Subset Sum where the size of the subset is specified I know it should be easy but I'm trying to determine the complexity of the following variant of Subset Sum.

Given a subset $S$ of positive integers and integers $k>0$ and $N>0$, is there a subset $T\subset S$ such that $|T|=k$ and the members of $T$ sum to $N$ ?

All of the formulations of subset sum that I've seen don't specify $k$ so I'm wondering if this problem can be solved in polynomial time. If $k$ is fixed for all instances, then I know that the problem is in P and solvable by brute force in $O(n^k)$ time. However, I'm allowing $k$ to vary from instance to instance.

There are $\binom{n}{k}$ $k$-subsets of an $n$ set, and $\binom{n}{k} = n (n - 1) \dotsm (n - k + 1) / k!$, which is $O(n^k)$, as you observe. The brute force complexity is a bit more (need to add up the numbers too and check), but that is ballpark.
This is polynomial for any fixed $k$, but not polynomial in $n$ if e.g. $k = n / 2$ (that is the Partition problem, known NP-complete).


Question concerning subset sum problem: split into 3 equal subsets Task: Given an array $arr[a_1, a_2, \dots, a_n]$ of integers, let $A = \sum\limits _{i\in \{1, 2, \dots, n\}}a_i$.  Determine whether it is possible to spit $arr[]$ into 3 subsequences of equal sum, i.e. if $s_1 =s_2 = s_3 =\dfrac{A}{3}$ where $s_1 ,s_2 , s_3$ denoted the splitted arrays.
My thoughts: I will first examine whether there exists some sequence of numbers that sums up to $\dfrac{A}{3}$ via dp, then I will backtrack those numbers, "throw them out" (meaning I won't consider them anymore), and proceed with the remaining numbers of the array. After doing this a second time I examine whether the numbers left sum up to $\dfrac{A}{3}$ and return true if this is the case. Even though this sounds valid to me I somehow doubt the correctness of this.
Recurrence of DP: $dp[i][j] = dp[i-1][j-a_j] \text{ OR } dp[i-1][j]$
$dp[]$ is a boolean array of dimension $n \times\dfrac{A}{3}$.

I don't think the proposed algorithm is correct. It may happen that the first solve for $A/3$ picks a set of numbers that makes it impossible to split the remainder into equal halves. Consider this example:

Given the set of numbers $\{1,1,3,3,3,4,8,10\}$, which sum to $A=3*11$
Assume that the first DP picks $||\{1,1,3,3,3\}||_1=11$
It is impossible to split the remaining set $\{4,8,10\}$ into equal halves.

Here's a recursive function in pseudocode instead which computes what you need in a single step:
bool CanBuild3EqualSums(int sumA, int sumB, int sumC, int[] numbers)
{
    if(numbers is empty)
        return sumA == sumB && sumB == sumC;
    else
        return CanBuild3EqualSums(sumA + numbers[0], sumB, sumC, numbers.WithoutFirst())
            || CanBuild3EqualSums(sumA, sumB + numbers[0], sumC, numbers.WithoutFirst())
            || CanBuild3EqualSums(sumA, sumB, sumC + numbers[0], numbers.WithoutFirst())
}

This is a pure function (without side-effects). Add memoization and you'll end up with a DP algorithm. Of course, there are many other ways to formulate this. There is some potential for a more efficient, practical implementation:

You could pass the index of the next number, instead of the whole array.
You could get rid of sumC, and compute when needed, based on sumA and sumB
If you have small values, a bottom-up formulation might be more efficient.


Prove $\{xy \mid |x|=|y|, x \neq y\}$ is not a linear language Show the language
$$L = \{xy \mid |x| = |y|, x\neq y\}$$
is not linear.

I've seen and proved a pumping lemma for linear languages, mentioned here:

If $L$ is linear then there exists a constant $p$ such that for all $w \in L$ with $|w| \ge p$ there is a decomposition $w = uvxyz$ such that:

$|uvyz| \leq p$.
$|vy| > 0$.
$uv^ix^iz \in L$ for all $i \geq 0$.

I'm trying to find a counterexample string.

Consider this string: $w=a^kb^ka^{2k+2k!}b^ka^k$. We will show that we can't write this string in form of $uvxyz$ in a way that the conditions of pumping lemma for linear languages statisfy.
Because $|uvyz|\leq k$ we have :  $|uv|\leq k$ and $|yz|\leq k$
So we can write: $uv=a^{f_1}$ ,  $yz=a^{f_2}$ ,   $y=a^{g_1}$ , $v=a^{g_2}$ where $g_1+g_2>0$ (because  $yv$  is cannot be empty string) and $g_1+g_2\leq k$.
Now we pump $v$ and $y$  $n$-times and we have: $w'=a^{k+ng_1}b^ka^{2k+2k!}b^ka^{k+ng_2}$
We want to conclude this string is not in language for some $n$. So if we rewrite $w'$ as $w'=a^{k+ng_1}b^ka^xa^{2k+2k!-x}b^ka^{k+ng_2}$,
we should have:
$k+ng_1=2k+2k!-x$  and  $x=k+ng_2$
so $k+ng_1=2k+2k!-k-ng_2 \to n(g_1+g_2)=2k! \to n=\frac{2k!}{g_1+g_2}$.
Notice that $g_1\leq k , g_2 \leq k \to g_1+g_2 \leq 2k$  $\to$  $g_1+g_2| 2k!$
So we only need to set $n=\frac{2k!}{g_1+g_2}$ to have $w'=w''w''$ and this is a contradiction. So $L$ is not linear.


Reinforcement Learning - Agent training In RL, in a game situation, usually the agent is trained by playing against itself.

When we should not depend on this self-training, and switch to train the agent with a real or different player agent other than the agent it self?

I mean is there any characteristics of the environment that would make self-play worse choice than playing against an existing player?

Ideally when training an agent you would reach an equilibrium between both player strategies strategies (hopefully a Nash equilibrium). When using only self-play this equilibrium might be different to the one you would reach when competing against a specific player, in particular, taking into consideration that the other player might not be very efficient, may have a different reward structure, etc.

Now, answering your specific question about the environment.. I would say that the critical aspect is the game being played. You should check if you are dealing with a zero-sum game, cooperative vs non-cooperative, etc.


Computability of an expression of a function rather than a function itself? Let's assume we're talking about real functions purely for clarity purposes, but my question is more general.

We say that a function $f$ is computable, if for a given $x$, a turing machine can output $y$ such that $f(x)=y$.

However, I'm wondering whether there is some concept of "computability for the expresssion of a function". For example, let's say I have some implicitly defined function $f$, and let's say that this function is equivalent to $g(x)=\sin(x)$, but we don't know this yet. Then what we would want is to compute the fact that $f(x)=\sin (x)$, but we don't necessarily need to compute that $f(0.45)=0.434965534...$

Is there a concept that rigorously captures this idea of the expression of a function being computable, rather than the function itself being computable? In other words, it may be that a function is incomputible, but that there is at least a finite number of computations we can do to derive that it has a certain closed form expression.

I assume that a closed form of a function is a finite expression involving function symbols from some fixed natural finite list together with some real[1] parameters. Since we know what it means to compute a real number, and since we know what it means to compute finite tuples of stuff we know how to compute with, we obtain in a direct way a notion of what it means to compute a closed form of a function.

Then in particular we can ask questions such as "given these parameters for the differential equation, can we compute a closed form of the solution".

Note however that all usual continuous functions are computable. Given a closed form of a function $f$ and some input $x \in \mathbb{R}$, we can compute $f(x)$. However, the problem "given a continuous function that has a closed form, find that closed form" is not computable.

So asking for closed forms is asking for more, not asking for less.

[1] If you don't like computing with real numbers, go for parameters from the algebraic closure of $\mathbb{Q}[\pi,e]$ instead.


Proving that $S_1+S_2 \leq f^{-\omega(1)}$ I am trying to show  for every c, there exists $M\text{ such that }(x,y,z)\geq M$ then $S_1(x,y,z) + S_2(x,y,z) \leq ( f (x,y,z))^{-c} $  . For a particular $S_1,S_2,f$. Does it suffice to prove there exists M1, for corresponding $S_1$, with $S_1(x,y,z) \leq (f(x,y,z))^{-c} $ and $M_2$ for $S_2({x,y,z)} \leq (f(x,y,z) )^{-c} $?

This is in the same spirit as showing $O(S_1+S_2) \leq T$ can be done by showing individual upper bounds.

All functions are  strictly positive increasing functions.  In particular, $f$ is not a constant.

I am trying to show that there for large enough $x,y,z$, $S_1 + S_2$ is smaller than the inverse of any polynomial in $f$.

I am looking to solve it for a particular case of $f=x^2 y^2+xz\ log (xz)$ but general answers are also appreciated.

Let's consider the simpler case in which $f$ only has one input — the general case is the same, given that you use the correct definitions.

Here is what we want to prove:

  Suppose that $\lim_{n\to\infty} f(n) = \infty$.

  If for all $c \geq 0$ there exists $N$ such that for all $n \geq N$, $S_1(n) \leq f(n)^{-c}$ and $S_2(n) \leq f(n)^{-c}$, then for all $c \geq 0$ there exists $N$ such that for all $n \geq N$, $S_1(n) + S_2(n) \leq f(n)^{-c}$.

Let us be given $c \geq 0$. Let $N_1$ be such that $f(n) \geq 2$ for all $n \geq N_1$, and let $N_2$ be such that for all $n \geq N_2$, $S_1(n),S_2(n) \leq f(n)^{-(c+1)}$. Let $N = \max(N_1,N_2)$. Then for $n \geq N$,
$$
S_1(n) + S_2(n) \leq 2f(n)^{-(c+1)} = \frac{2}{f(n)} f(n)^{-c} \leq f(n)^{-c}.
$$


How does a computer compute negative(-) and positive(+) Infinity? If we divide (1.0/0.0) we will get +Infinity and if we divide (-1.0/0.0) we will get -Infinity.

How does a computer calculate this value internally?

The simple answer is that a computer that follows a floating point standard such as IEEE 754 does not really compute +/- infinity at all. Instead it treats it as an exception - a special case. Whenever the processor detects an attempt to divide a non-zero floating point number by zero, it sets the result to a special value that is then interpreted as +/-infinity, where the sign depends on the sign of the original number.

In IEEE 754 I believe the special values of +/- infinity are represented internally as a floating point number with a sign bit, an exponent set to all $1$s, and a significand set to all $0$s. This is a value that cannot result from normal (non-exceptional) floating point operations.


Formal definition of an empty stack accepting PDA PDA's are usually defined using the 7-tuple convention.

$M=(Q, \Sigma, \Gamma, \delta, q_{0}, Z, F)$

F is the set of accepting states.

I want to design a PDA accepting by empty stack, so using this notation makes no sense, as I don't need F and I want to make the acceptance condition clear.

How is this usually done? Can I just dismiss F?

$M'=(Q, \Sigma, \Gamma, \delta, q_{0}, Z)$

When the stack is finished you can go to the specified state which shows the empty stack. In addition, when you reach in a state which you found it's a solution but the stack is not empty, iterate over a "pop" action to empty the stack and finally go the empty stack state.

Hence, you can explain this PD using the defined notation.


Proving NP completness without reductions What methods are there to prove a language is NP-complete? I already know the reduction method, but are there more sophisticated/advanced methods to prove this?

To prove that a problem is NP-complete, you must show that it's in NP and that every problem in NP reduces to it.  As far as I'm aware, there are only really two ways of doing the latter:

show that some problem already known to be NP-complete reduces to your problem;
show directly that every problem in NP reduces to your problem by showing that your problem can essentially simulate a nondeterministic polynomial-time Turing machine.


Does any one know what this problem is called? We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$.  We wish to determine whether there is a function $A\to B$  so that no member of $B$ is the image of more than $k$ members of any $T\in S$.

This is an example of a constraint satisfaction problem. The variables of the problem are the "colors" of the elements of $A$, where $B$ is the set of colors. For each set $T \in S$ and each $(k+1)$-subset $T'$ of $T$, there is a constraint stating that the elements of $T'$ cannot all have the same color.

If $k=1$ and all $T \in S$ have cardinality $2$, then this is just graph coloring. You can similarly put graph hypercoloring in this framework.


A regular expression for a given formal language I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and in which between each pair of consecutive $a$'s there is an even number of $b$'s (and an arbirtary number of $x$'s).

For example, $babbxbbxabbxaabxxbax \in L$, $bab \in L$, while $abba \notin L$ and $abbbaa \notin L$.

What is the approach?

Try and build it step by step:

a language with an odd number of $a$'s: $a(aa)^*$;
between which there is an even number of $b$'s: $b^*a((bb)^*a(bb)^*a)^*b^*$;
and an arbitrary number of $x$'s: $(b+x)^*a(x^*(bx^*bx^*)^*ax^*(bx^*bx^*)^*a)^*(b+x)^*$.


Reaching Shannon capacity of a channel Suppose I have the following from alphabet $\mathcal{X} = \{0 ,1\}$ to $\mathcal{Y} = \{0 ,1\}$. The channel simply does

\begin{align}
 0 \rightarrow 0&\quad  \text{with probability 1} \\
 1 \rightarrow 0&\quad  \text{with probability 1/2}\\
 1 \rightarrow 1&\quad  \text{with probability 1/2}
\end{align}

The classical capacity of this channel is given by the mutual information between the input register, $X$ and output register $Y$ maximized over input probability distributions, $p(x)$. That is,

$$C = \max_{p(x)} H(Y) - H(Y|X)$$

The appropriate distribution turns out to be $(0.6, 0.4)$ and the capacity is $0.3219$ bits.

How does one actually use this result to practically communicate (in the asymptotic limit) over this channel at this rate? Does it mean that I should use input codewords that obey these statistics over the input alphabet for example?

Your channel is known as the Z-channel. Take a look at Marco Mondelli, S. Hamed Hassani, and Rüdiger Urbanke, How to Achieve the Capacity of Asymmetric Channels.


The well-known classifiers that can be trained/tested in linear time I am interested in collecting the list of the classifiers that (depending on their setting) can have linear time complexity (both in training and testing step) with respect to the number of samples $n$, the number of features of each sample $m$, and the number of classes $c$.

In other words, I am seeking for a list of the well-known classifiers that can have the complexity of $\mathcal{O}(mnc)$ or lower.

1- I know that Naive Bayes classifiers are so; given that the parameters of the utilized probability distributions can be estimated in linear time (e.g. Poisson Naive Bayes and Multinomial Naive Bayes)

2- I also know that when K-NN is utilized as classifier (counting the K-nearest neighbors and choosing the most-voted class), it is also included in this list.

Although this list, in theory, can be extended infinitively, I am interested in completing the list by the well-known classifiers by the CS community.

I searched the web, a lot, but seemingly, there is no page even speaking about such subject or such list. The only thing that I found was a lot of info about "linear classifiers" whose scope is much more general than my question (even their list includes SVM and etc.).

You might want to read my blog post Comparing Classifiers, especially the MNIST summary.

Time Complexity of Training

By Training Samples

Let $n$ be the number of training samples.

The following classifiers can perform at least on training / fitting step in $\mathcal{O}(n)$:

Neural Networks: You can take a fixed batch size. Then increasing $n$ is simply having more mini-batches to train on.
$k$-nearest-neighbors: All "training steps"

The following classifiers cannot perform at least one training / fitting step in $\mathcal{O}(n)$:

???

I am unsure about the following:

SVMs
Decision Trees: I'm relatively sure it is linear, but I would need to go through one of the training algorithms

By classes

If $n$ is the number of classes, then the training of $k$-NN is in $\mathcal{O}(1)$. If you keep the number of samples and k constant, then it doesn't matter if you have 2 classes or $10^{100}$.

I'm unsure about:

Neural Networks: The size of the last layer grows. My intuition is that this is in $\mathcal{O}(n)$, but I need to put more thought into it. I am, however, not sure if the Big-O Time Complexity makes a lot of sense for this classifier. If you look at the tables in Appendix D, you see that in real problems the FLOPs are dominant in the beginning. Given a problem, you usually you can't influence the number of classes. And the wall-clock time complexity of training for two classes is vastly different for different classifiers. So much, that up to a reasonable amount of classes you will likely not see the asymptotic behavior.
Decision trees might even be in $\mathcal{O}(1)$. I have to give impurity measures a closer thought.


Induction details for proof of closure of regular languages under unions I was reading M. Sipser, Introduction to the theory of computation 3ed. where he presents a proof by construction that the class of regular languages is closed under unions (Theorem 1.25). However, he omits the induction details for a formal proof of correctness. I tried filling in the details myself but it was a mess; how is this usually done?

Given a transition function $\delta\colon Q\times\Sigma\to Q$, the standard argument proceeds by defining an extended transition function $\hat{\delta}\colon Q\times\Sigma^*\to Q$ (following the notation in Sipser)
that acts on strings (see J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages and Computations 3ed., section 2.2.4 for a reference).
This function is defined recursively by specifying
$$\hat{\delta}(q,\varepsilon)=q \qquad\hbox{and}\qquad
\hat{\delta}(q,Wa)=\delta\bigl(\hat{\delta}(q,W),a\bigr)$$ for $W \in \Sigma^*$,
$a\in\Sigma$ and $q\in Q$, and it is a simple exercise (with a proof sketched below) to show that (following the definition in Sipser)
a finite automaton $M=(Q,\Sigma, \delta, q_0, F)$ accepts a string $w\in\Sigma^*$ if and only if $\hat{\delta}(q_0,w)\in F$.

The heart of our desired inductive argument lies in the following result.

  Let $w\in\Sigma^*$. Then, with notation as in the proof of Theorem 1.25 in Sipser,
  we have
  $$\hat{\delta}\bigl((r_1, r_2), w\bigr)
= \bigl(\hat{\delta}_{\!1}(r_1, w),
\hat{\delta}_{\!2}(r_2,w)\bigr).$$

Proof. We proceed by induction on $|w|$. The result follows from the definitions when $|w|=0$
as we must have $w=\varepsilon$. Suppose inductively that the result holds for all $w$ with $|w|<n$.
Then, given $w \in \Sigma^*$ with $|w|=n$, we may write $w = w_1\dots w_n =: Ww_n$, so that
$$\begin{align}
\hat{\delta}\bigl((r_1,r_2),w\bigr)
&=\hat{\delta}\bigl((r_1,r_2),Ww_n\bigr) \\
&=\delta\Bigl(\hat{\delta}\bigl((r_1,r_2),W\bigr),w_n\Bigr) \\
&=\delta\Bigl(\bigl(\hat{\delta}_{\!1}(r_1,W),\hat{\delta}_{\!2}(r_2,W)\bigr),w_n\Bigr) \\
&=\Bigl(\delta_1\bigl(\hat{\delta}_{\!1}(r_1,W),w_n\bigr),
\delta_2\bigl(\hat{\delta}_{\!2}(r_2,W),w_n\bigr)\Bigr) \\
&=\bigl(\hat{\delta}_{\!1}(r_1, Ww_n),
\hat{\delta}_{\!2}(r_2,Ww_n)\bigr) \\
&= \bigl(\hat{\delta}_{\!1}(r_1, w),
\hat{\delta}_{\!2}(r_2,w)\bigr)
\end{align}$$
as needed.

Using the above result, it is straightforward to finish the proof of correctness.
Indeed, since $F = (F_1 \times Q_2) \cup (Q_1 \times F_2)$, it follows that
$$\hat{\delta}(q_0,w)\in F$$
if and only if
$$\hat{\delta}_{\!1}(q_1, w)\in F_1\qquad\hbox{or}\qquad\hat{\delta}_{\!2}(q_2, w)\in F_2.$$
In other words, $M$ recognizes a string $w\in\Sigma^*$ if and only if $M_1$ or $M_2$ recognizes it.

Addendum. We now sketch a proof that the two definitions of a finite automaton accepting a string are equivalent. The  first definition is given on page 40 of Sipser, we repeat it here for convenience:

  Let $M = (Q,\Sigma,\delta,q_0,F)$ be a finite automaton and let $w = w_1w_2\dots w_n \in \Sigma^*$ be a string. Then $M$ accepts $w$ if $w=\varepsilon$ and $q_0\in F$, or if $n>0$ and a sequence of states $r_0$,$r_1$, ..., $r_n$ in $Q$ exists such that $r_0 = q_0$, $\delta(r_i,w_{i+1}) = r_{i+1}$ for $0\le i\le n-1$, and $r_n \in F$.

We thus have to show the following:

  A finite automaton $M = (Q,\Sigma,\delta,q_0,F)$ accepts $w\in\Sigma^*$ if and only if $\hat{\delta}(q_0,w)\in F$.

Proof sketch. If $M$ accepts $w = w_1\dots w_n$, then $\hat{\delta}(q_0,w)=\delta\bigl(\hat{\delta}(q_0,w_1\dots w_{n-1}),w_n\bigr)=\delta(r_{n-1},w_n)=r_n$ by an inductive argument; intuitively this corresponds to showing that the recursive definition of $\hat{\delta}$ was defined 'correctly.' Conversely if $\hat\delta(q_0,w)\in F$, then we may build the sequence $r_0 = q_0$, $\;r_1 = \delta(r_0,w_1)$, ... inductively.


Time complexity of a 2-heap question The problem statement is pretty straight forward: given an array of integers and a window size, return an array of doubles of the median of each window.

arr = 1, 3, 5, 10, 6, 9, 2

k = 3

would yield a result of 3, 5, 6, 9, 6

Using std::priority_queue (in C++) for the heap implementation, there's a minHeap and maxHeap.  In a single iteration, insert the value entering our window in the correct heap, rebalance as necessary, add the median to the result (if the window is big enough), then remove the value which is leaving the window from whatever heap it's in: This could require moving all but 1 heap element to the other heap, then moving them back.

The lesson I saw this on actually inherits from priority queue and implements remove functionality: Linear search [O(k)], then removes the item [O(log k)].  It claims O(n * k) complexity as at each iteration the insertion is O(log k) and the search to remove is O(k). I assume in an interview extending a heap beyond it's traditional form is not only unnecessary but probably frowned upon.

I'm curious of the complexity at which the version w/o the direct removal would run.  The O(n) part is obvious but the sub operations not as clear to me.  A heap will generally have k/2 items in it.  In the worst case you delete [O(log k)] and then insert [O(1)] each one.  My mind is telling me O(n * k log k) but I wouldn't bet my house on it.

For the record: Not looking for an optimal solution - just the runtime of this one.

insert(num):

  if maxHeap is empty or maxHeap.top > num:
    push num on maxHeap
  else
    push num on minHeap

  // rebalance
  if maxHeap.size > minHeap.size + 1:
    move maxHeap.top to minHeap
  else if minHeap.size > minHeap.size
    move minHeap.top to maxHeap

get Median:
  if maxHeap.size == minHeap.size:
    return maxHeap.top + minHeap.top / 2.0
  else if maxHeap.size > minHeap.size
    return maxHeap.top
  else
    return minHeap.top

remove(num):

  if maxHeap.top >= num:
    move maxHeap.top to minHeap until maxHeap.top == n;
    remove maxHeap.top
    move minHeap.top to maxHeap until balanced
  else
    move minHeap.top to maxHeap until minHeap.top == n;
    remove minHeap.top
    move maxHeap.top to minHeap until balanced

findSlidingWindowMedian(arr, k):
  // This is where the mystery is.  Worst case we have to remove
  // a number at the bottom of a k/2 sized heap.  So that would be
  // log k for k/2 operations then O(1) for k/2-1 operations?
  left = 0
  for right = 0 to arr.size
    insert(arr[right]):

    if right >= k-1
      add median for current window to result
      remove(arr[left])
      left += 1

  return result

Store the window in a balanced binary search tree.  Each time a value arrives, add it to the tree, remove the one leaving the window, compute the median, and output it.  Each of those operations can be done in $O(\log k)$ time, so the total running time to process $n$ items will be $O(n \log k)$.


The exact relation between complexity classes and algorithm complexities Are all algorithms which have polynomial time complexity belong to P class ? And P class do not have any algorithm which does have not polynomial complexity ?

Are all algorithms which have non polynomial complexity belong to NP or NP-Hard or both ?

I am just trying to understand the basic relationship.

$P$ is defined as the class of (decision) problems that have an algorithm that solves them in polynomial time (in a TM, or a polynomially-equivalent model). Thus, $P$ contains exactly these problems, no more and no less.

As for $NP$- the situation is more delicate. A problem is in $NP$ if it has a nondeterministic algorithm that runs in polynomial time. An equivalent, more user-friendly definition, is that given a solution to the problem, you can verify it's correctness in time polynomial in the size of the problem. For example, given a graph and a path that claims to be a Hamiltonian, you can verify in polynomial time that it is indeed a Hamiltonian path. Thus, the problem of deciding if a graph has a Hamiltonian path is in $NP$.

Clarification: $NP$ is a class of problems, not of algorithms. An algorithm doesn't belong to $NP$.

Now, some problems are known not to have a polynomial time algorithm. This doesn't mean that they are in $NP$. In fact, some problems are known not to be in $NP$. For example, any $NEXP$-hard problem.

Regarding $NP$-hard problems - since we don't know whether $P=NP$ or not, we don't know if every problem outside $P$ is $NP$-hard. If $NP=P$, then every problem is $NP$-hard (except $\Sigma^*$ and $\emptyset$).

This answer (which is by far incomplete) covers about 3 weeks of material in a basic complexity course. Perhaps consider thoroughly reading a textbook, such as Sipser's "Theory of Computation".


BNF and Simultaneous Parsing Let's say we have the following grammar

expr1 ::= ... // Actual definition doesn't matter
expr2 ::= ... //
expr3 ;:= ... //
foo ::=  expr1 | expr2 | expr3

When it comes to parsing foo we note that foo could be parsed in parallel.

p1 = task parse( expr1 )
p2 = task parse( expr2 )
p3 = task parse( expr3 )

Question

Would continuing on the first to complete be better.

result = task.WaitAny( p1, p2, p3 ) // wait for any (parsing) task to complete

or would it be better to wait for all the (parsing) tasks to complete?

task.WaitAll( p1, p2, p3 ) // wait for all (parsing) task to complete

What are the potential issues with simultaneous parsing?
 or
Does the ordering of clauses matter?

If the grammar is amenable to limited-lookahead bottom-up parsing, then the parallelism is more or less implicit in the parsing algorithm, and there is little to be gained from parallel computing, at least in the sense proposed in the post. A standard LALR(k) parser is deterministic; it only does a single table-lookup for each action, based on the current state, the lookahead token(s) and -- in the case of reductions -- a single state value popped from a known location on the parse stack.

That's not to say that there is no possible benefit from the availability of multiple CPUs, but I suspect that benefit would come from segmenting the input using some kind of simple lexical analysis (text inside balanced braces, for example) and constructing individual parse trees for each segment.

If the grammar itself is highly ambiguous, as is the case for natural-language parsing, then different algorithms will be employed. CYK parsing, for example, used as the basis for many probabilistic parsers, can benefit significantly from parallel processing, and it is easy to find recent (and not-so-recent) papers on the subject on the internet. I found a dozen in a few seconds, and I won't bother pasting all of them particularly since I didn't read them, but I think that this paper by Mark Johnson has some pretty impressive results.

The answer dodges around the actual question, because I think the algorithmic analysis required to efficiently parallelise chart-parsing is more sophisticated than simply exploring alternative productions in parallel. But I hope it has some utility.


How to perform orthogonal check on two circular binary strings? Say we have two circular binary strings $a = a_0a_1...a_{n-1}$ and $b = b_0b_1...b_{n-1}$ with arbitary starting point, and define a and b are orthogonal if $\sum_{i=0}^{n-1}a_ib_i = 0$.
Is there a $O(nlogn)$ algorithm can tell a rotation of such circular binary string is orthogonal to another?

Say we have strings $a = a_0a_1...a_{n-1}$ and $b=b_0b_1...b_{n-1}$. First concatenate $a$ with itself and remove the last character. You should get a new string $a=a_0a_1...a_{n-1}a_0a_1...a_{n-2}$. Now we are interested in substrings of size $n$ in new string $a$ that are orthogonal to $b$ (this is a very classic trick to deal with cyclic strings/arrays).

Let's reinterpret them as polynomials in the following way.

For $a=a_0a_1...a_{2n-2}$ use value at position $i$ as the coefficient associated with power $i$ in a polynomial such that $P_a(x) = a_0x^0 + a_1x^1+...+a_{2n-2}x^{2n-2}$.

Now reverse $b$ and get the new string $b=b_{n-1}...b_1b_0$ and build a polynomial similarly as we did above. You get $P_b(x)=b_{n-1}x^0+...+b_1x^{n-2}+b_0x^{n-1}$.

Now let the magic happen. Multiply both polynomials into $P(x) = P_a(x) \cdot P_b(x)$ (Remember to do this fast). Wait, what ... where is the answer to the problem.

Let's see what is the $n-1$ coefficient of the new polynomial: $$P(x) = c_0x^0+c_1x^1+...+c_{3n-3}x^{3n-3}$$

Coefficient at position $n-1$ is equal to $$c_{n-1} = a_0 \cdot b_0 + a_1 \cdot b_1 + ... a_{n-1}\cdot b_{n-1}$$

Awesome, that is the dot product of original string $b$ with original string $a$ (without rotations). Keep looking at further terms of $P$. Coefficient at position $n$ is equal to $$c_{n} = a_1 \cdot b_0 + a_2 \cdot b_1 + ... + a_{n-1} \cdot b_{n-2} + a_{n} \cdot b_{n - 1}$$

But keep in mind that $a_n=a_0$ since this is just $a$ concatenated with itself. So we have the dot product of $a$ rotated one step to the left with $b$. You can see that terms of $c_{i}$ from $n - 1 \le i \le 2n - 1$ will give you the dot product of all rotations of $a$ with array $b$. Therefore, after computing $P$, you can find whether there is at least one dot product with value equals to $0$ easily.

In general polynomial multiplication is a useful representation to model convolutions of two arrays. It turns out that a lot problems can be modeled this way in areas such as: combinatoric, dynamic programming, string matching with least mismatches.

This is indeed relevant because there is a very efficient way to multiply polynomials which is via FFT in $O(n \log n)$ (or Karatsuba in $O(n^{\frac{3}{2}})$) instead of the naive $O(n^2)$ algorithm.


How to calculate probability of packet loss and drop rate? In a queuing system (M/M/1) with a finite packet capacity $z$, how do you determine the probability of packet loss if we assume that packets are dropped when the system is full? Packets arrive with a rate $\lambda$ and are served at rate $\mu$ (using the Poisson distribution).

My attempt at a solution:

Probability of packet loss = Probability that the system has exactly $n$ packets (i.e., it is at its capacity)?

I also have a formula from my notes where probability of packet loss is approximated at $(1 - \frac{\lambda}{\mu})(\frac{\lambda}{\mu})^z$ (so this is most likely correct but can someone please explain why?).

I'm not sure how to calculate the rate at which packets are dropped. I already know the probabilities $P(n)$ that there are $n$ packets in the system where $n = 0, 1, ..., z$ packets.

If you study M/M/1 queuing systems you'll probably know that such a queuing system can be seen as a markovian chain with birth rate λ and death rate $\mu$; that is to say that you change your state (and in an M/M/1 the state is the number of clients in the system) by unitary steps: $-1$ with rate $\mu$ and $+1$ with rate $\lambda$.

It is quite hard and long to explain in a thread like this and for this reason I suggest you to take a look at the markovian chains theory to understand why it works like this.
Anyway, I'll try to give you an idea: you can set a basic fluxus equation to describe the system:

$$P[x(t)=k] \mu = P[x(t)=k-1] \lambda$$

and analyzing the transition probabilities you will find:
$$
  P[x(t+h)=k+1 | x(t)=k] = \lambda h + o(h) \\
  P[x(t+h)=k-1 | x(t)=k] = \mu h + o(h)\\
  P[x(t+h)=k | x(t)=k] = 1-\lambda h-\mu h + o(h)\\
  P[x(t+h)=k+j | x(t)=k] = h + o(h)$$

with $h$ defined as very little piece of time.

So, defined $ρ=\frac{\lambda}{\mu}$ as the load factor of the system, you will find that (recalling the total probability theorem):

$$ P[x(t)=k] = (1-ρ) ρ^k $$

If you take a look at this result, you will recognize the answer to your question: if the system is a blocking system with blocking capacity $z$, the probability of packet loss is the following:

$$P[z\,\text{clients in the system}] = P[k\,\text{clients in the system}] = P[x(t)=k] = (1-ρ) ρ^k$$

Is it ok? :)


Is there a computer science theory behind automatic source code generation The OpenAPI specification aims at standardizing the representation of REST based systems in json and yaml formats. A short version of the petstore is below:

{
 "swagger": "2.0",
 "info": {},
 "host": "petstore.swagger.io",
 "basePath": "/v2",
  "tags": [],
  "schemes": [
 "http"
 ],
 "paths": {},
 "securityDefinitions": {},
 "definitions": {},
 "externalDocs": {
 "description": "Find out more about Swagger",
 "url": "http://swagger.io"
 }
}

Based on this document, client and server stubs can be generated in different programming languages/frameworks using the OpenAPI codegen project. Is there a computer science theory behind this ? To be more precise, I want to specifically know if there are theoretical concepts behind taking an input, (in this case a json/yaml document) and getting a source code representation in one or more programming languages that represents the initial input ?

I don't know anything about it but the field as a whole is called "automatic programming", which should give you pointers of where to look.


Does the complement of sigma Kleene star exist? If $\Sigma^*$ is the set of ALL strings including the empty string, then what can its complement possibly be?  The empty set?

Note that the complement of $A \subseteq \Sigma^*$ is defined as $\Sigma^* \setminus A$; so yes: the complement of $\Sigma^*$ itself is the empty set.

To be completely accurate, you need to state with respect to which universe you want to take the complement. For instance, if you were to take the complement of $\Sigma^*$ w.r.t. $\Sigma'^*$ where $\Sigma' = \Sigma \mathbin{\dot\cup} \{a\})^*$, $a \not\in \Sigma$, it would not be empty but $\Sigma'^* \cdot \{a\} \cdot \Sigma'^*$ (the set of words with at least one $a$).


Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time? Assumptions:

given a graph with N nodes, and two specific nodes A and B
the  graph is undirected and no edge has a negative cost
there exists at least one Hamiltonian path with A and B as an end points

Is there a way to find the shortest path from A to B that passes through all the other points?

Note: I'm only concerned with the specific given nodes A and B as endpoints, thus there's no need to compute for other Hamiltonian paths with different endpoints.

I'm thinking if it's possible to modify Dijkstra's shortest path algorithm to find Hamiltonian paths. Is it possible? If so, how? If not, is there any other algorithm that can be used? (in polynomial time)

The case you are describing is NP-complete, so the answer is no.

I don't know if still remains NP-complete if the graph is a Euclidean graph. Anyone knows?


How to prove that there is a function index t so that t³ + t + 1 is an index of the same function? I would like to prove $\exists t\phi_t = \phi_{t^3+t+1}$ where $\phi_0,\phi_1,\phi_2,...$ are sequence of all of the partially computable function.

$\phi_t = \phi_{t^3+t+1}$ only if $t = t^3+t+1$ and it means $t=-1$! and there is no program with number $-1$!

This is just a special case of Rogers' fixed-point theorem which says that, for any total computable function $f$, there exists $t$ such that $\phi_t = \phi_{f(t)}$.


Is Vertex Cover of size $k >100$ polynomial time solvable? I know that when we want to find out if Vertex Cover of size $k$ when $k
\leq C$, belongs to P or not (when $C$ is some constant), we actually
can find algorithm with polynomial time complexity (in the algorithm we
iterate over subsets $V'$ such that $|V'|=C$).  But what about $k \geq
C$?
I personally think it's not in P because $k$ can be as most in size
$|V|$, and therefore the time complexity is exponential, but I'm not
sure if I'm right (maybe it's unknown?)

We don't actually iterate over subsets $V'$ of size $C$, because that would be running in time $\Theta (n^k)$.  While that is polynomial for fixed $k$, there is an algorithm that runs in time $O(2^k \cdot n)$, which is much better.
The problem you have stated is not really very well defined, so let's try to clear it up.
The Vertex Cover problem is given a graph $G$ and a number $k$ and asks whether there exists a vertex cover in $G$ of size at most $k$.  This problem is NP-complete (as long as $k$ is not a constant).
However, if you ask to find any vertex cover in $G$, then you can reply with $V(G)$, which has size $n$.  This version is of course polynomial time solvable and uninteresting.
The answer is therefore: Vertex Cover is NP-complete.  If you fix the bounds, however, you can solve the problem in time "polynomial" time (exponential in the bounds).


Regular expression with out the substring bab or abb? I'm having a problem coming up with a regular expression for a language L = {a,b} with out the substring bab or abb?
I can come up with the one for just one substring, like

a*(b* aaa* )* b* a* to eliminates the bab and b*(a+ab)* to eliminates the abb substrings.

But putting them together is a huge animal :(

There are a couple tricks required to get this right.

First, this particular problem is a lot easier if you approach it backwards, starting at the end of the sting.

(abb,bab) is an exhaustive list of all the cases in which b is preceded by 2 different letters.  If you want to exclude these cases, you just have to ensure that b is preceded by less than 2 letters, or a double letter.

Second, notice that these rules imply that if there are 2 bs in a row, then they must be preceded by b all the way to the start of the string.  Otherwise the second-to-first b will be preceded by ab.

Working from the end, then, we can have a free mixture of a and aab, and then there are only a few ways to get to the beginning of the string when we encounter a b outside of that pattern:

(ab|b*)(aab|a)*


Converting to CNF - Distribution I am still trying to get my head around what is valid CNF and how distribution works, I am not even sure if the examples I have tried to convert are correct for one, but I am also unsure of the rule for distribution and when I have looked at other posts here it seems so complicated and the actual rule does not seem to me to be obvious.
I think the correct process is:

Elimate Bi-Directionals
Eliminate Implications
Apply De Morgans Law
Apply Distributive Law

Clause One
A V B => C
-(A V B) V C -- Remove implication
(-A ^ -B) V C -- De Morgans Law
(-A V C) ^ (-B V C) -- Is this right? I am unsure of exactly how to distribute the or.

Clause Two
A ^ B => C
-(A ^ B) V C -- Eliminate Implication
(-A V -B) V C -- Is this now valid CNF or is there something more to do?

Clause Three
-A ^ -B => C
(A ^ B) V C -- Elimate Implication - Is this correct for a negated expression?
(A V C) ^ (B V C) -- Distribute OR - Is this correct?

I am not able to access the set of maths symbols for some reason so have used the notation in my course book.
I am currently taking a self taught course and have an exam in two weeks and I know there will conversion to CNF involved so I am trying to make sure I understand the steps now but I am still not entirely sure what is valid CNF.
The course material states it is a conjunction of disjunctions which I get, but then it seems to imply that: A V B V C V ..n is valid CNF?

By definition - for example Herbert B. Enderton - A Mathematical Introduction to Logic-Academic Press (2001), page 53 - simply saying CNF is conjuction of disjuntions or product of sums.

So, as we agreed earlier,
$$(I \lor M) \Rightarrow H = (\neg I \lor H) \land (\neg M \lor H )$$

For $(I \land M) \Rightarrow H$ we can get $\neg (I \land M) \lor H=\neg I \lor \neg M \lor H$ and this last is CNF

For third case for $(\neg I \land \neg M) \Rightarrow H$ answer is analogical $2$d case: $\neg(\neg I \land \neg M) \lor H = I \lor M \lor H$ and this also is valid CNF.

And answer for the last question is yes - $A_1 \lor A_2 \lor \cdots  \lor A_n$ is valid CNF if each $A_i$ is  either a sentence symbol or the negation of a sentence
symbol - it's allowed to have just one conjuct.
Let me add, that one symbol is as CNF, so DNF.


Algorithm to find path with max sum of degrees in a tree structure Is there an efficient way to find a path from root to a leaf such that it has the maximum sum of degrees of nodes from all the paths possible in the tree.

For example if a tree is defined as the one in which each node is an integer and it has as many child nodes as the perfect divisors of the integer. And the root node is 16 then the sum of degrees of the required path would be 4+4+3+2+1 = 14.
The path being : 16->8->4->2->1.

In a tree, there is exactly one path from the root to any vertex. So just do depth- or breadth-first search on the tree and label each vertex with the sum of the degrees on the path from the root to there. Then pick the leaf with the smallest value.

An optimization could be to use greedy best-first search, where you maintain a queue of vertices in increasing order of their weight (sum of degrees on the path from the root). The first leaf you find would then be guaranteed to be the one of minimal weight. This would reduce the number of vertices that you look at but it's possible that the additional overhead of maintaining the priority queue would negate that benefit.


Does interrupt (for I/O and etc) requires support of Preemption? What is the relation between interrupts and Preemption in O.S? So i just don't understand the relation between interrupts and Preemption in O.S?

For example in Multi-programming, do we need the support of Preemption or not? when a process needs I/O and sends an interrupt, do we use Preemption here to remove that process in order to get another process running, or no need for Preemption ?

For Multiprogramming you may or may not need Preemption. It depends upon the scheduling policy that is being used. For example First in First Out is non preemptive but shortest CPU burst is preemptive.

One more thing you are mixing blocking and preemption. When a process needs I/O it uses a system call. This system call results in a trap(software interrupt). Now this process is said to be blocked(waiting for I/O). Here the scheduler will definitely remove this process from running state and bring in a new process. Now please note that this whole thing does not invlove preemption.

Preemption means that the process is not blocked, yet the CPU is taken from it and given to some other process. Suppose a process is running and an interrupt comes which has no relation with this process. Now even though the process wants to run the interrupt must be served. Here we say that the process has been preempted.

Another example would be a list of processes being scheduled by shortest cpu burst algorithm. Suppose a process A having CPU burst 20 sec is running. Now suppose a new process arrives having  a CPU burst of 10 seconds. Now A must be preempted to give chance to this second process.

Preemption is actually a good thing. It allows a CPU to serve more urgent things. Yet it may also cause some problems. A process may be preempted in the middle of updating a shared variable. This may lead to race condition.

Preemption can be simply avoided by disabling interrupts. But disabling interrupts is not a good thing at all. So nowadays all kernels used preemptive approach.


Sorting Algorithm with constraints I am looking for a sorting algorithm to help me in my work. My objective is the following: after receiving an input of this kind:

5 4
1 2
2 3
3 4
4 5

The first line tells me how many ids I have, and the second number tells me how many connections. The following lines tell me the connections, and tell me that the first Id comes before the second one, for example: 1 comes before 2, 2 comes before 3, and so on. And if an impossible situation occurs:

3 2
1 2
2 3
3 1

or

2 2
1 2
2 1

I want to be able to send an error message.

Or even when there is not enough information to have a conclusive sorting:

4 4
1 2
3 1
3 4
4 2

Is there an algorithm that already does this? or can u give me some guide lines to how to start my work? The sorting part is not hard, but the impossible/insuficient info cases is what I am struggling to implement.

Thanks in advance for your time.

In other words, you are given a directed graph, and you want to know:

Whether there are any directed cycles, i.e., whether your graph is a DAG.
Assuming there are no directed cycles, whether the corresponding partial order is a linear order.

As KWillets comments, this is just topological ordering. In your case, to find whether your digraph is a DAG supporting a unique topological ordering, try the following algorithm:

Verify that there is a unique source (a node with no incoming edges).
Remove the unique source, and repeat.

This succeeds iff your digraph is a DAG which has a unique topological ordering.