Classify the set of all TMs whose languages from the accepting problem Let $$L = \{ \langle M \rangle \mid M \text{ is a Turing machine so } A_{TM}  \leq_m L(M) \}$$
The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in $\overline{\mathcal{RE} \cup co-\mathcal{RE}}$ ?

I gained some progrees showing  $L \notin co- \mathcal{RE}$:

Define reduction $f:A_{TM}\rightarrow L$ on input $\left\langle M,w\right\rangle$ returns:

if $M$ accepts $w$ return $ \left\langle U_{TM}\right\rangle $
($L \left(U_{TM}\right)=A_{TM}$ so $\left\langle U_{TM}\right\rangle \in L$)
if $\left\langle M\right\rangle$ rejects $w$ return 1 (not a TM encoding hence not in L)

$f$ is computable and $\left\langle M,w\right\rangle \in A_{TM}\iff f\left(\left\langle M,w\right\rangle \right)\in L$ hence $A_{TM}\leq_m L \implies L\notin co-\mathcal{RE}$.

Now I want to show that $L \notin \mathcal{RE}$. And I'm stuck..

Notation:

$A_{TM} = \{ \langle M,w \rangle \mid  M \text{ is a TM}, w \in L(M)\}$

$H_{TM} = \{ \langle M,w \rangle \mid  M \text{ is a TM and $M$ halts on $w$} \}$

As suggested in the comments, the extended version of Rice's theorem clearly states this language is not in $RE$. Nevertheless, let us prove this claim via a direct reduction from a language known not to be in $RE$, let's say
$$ \overline{HP} = \{\langle M,w\rangle \mid M \text{ doesn't halts on }w \}$$

We will show that $\overline{HP} \le L$ and conclude that $L \notin RE$.

The reduction will assume we have a machine that recognizes $A_{TM}$ (call it $R$) and goes as follow. Given an input $\langle M,w\rangle$ we construct the output string $\langle M_w\rangle$ which is a machine that, on input x, does:

repeat the loop:
1.1 run one step of $M$ on $w$
1.2 run one step of $R$ on $x$
1.3  if 1.1 halts - the machine $M_w$ rejects. If 1.2 accepts - the machine $M_w$ accepts.

It is easy to verify this is a computable reduction. Let's just verify it is valid.

Case I: $\langle M,w\rangle\notin \overline {HP}$, then eventually (say after $T$ steps)  $M$ will halt on $w$ before the computation of 1.2 concludes, thus $L(M_w)$ can be decided in less then $T$ steps and in particular it is decidable. Therefore $A_{TM} \not\le L(M_w)$ and thus $\langle M_w\rangle \notin L$.

Case II: $\langle M,w\rangle\in \overline {HP}$, then $M$ never halts on $w$, which means that only step 1.2 is relevant, which means that $M_w$ behaves in this case just like $R$. So it holds that $L(M_w) = A_{TM}$ and in particular, $A_{TM} \le L(M_w)$. Then, $\langle M_w \rangle \in L$.


Examples for CFG that cannot be expressed by regular language There are nice examples for context free grammars which cannot be expressed with regular language, for example the palindrome and a similar contrived example here, but they are very intuitively applicable for formal languages, e.g. checking for balanced nested parentheses and such.

Can you conceive an example that is pertinent to natural languages?

Part of the motivation to this question is that in one view, regular expressions are practically intractable when it comes to combining and scaling them to describe natural language phenomena; they don't compose as nicely as grammars. But at the same time I can't easily think of an actual example where regular expressions should not be enough for describing natural languages.

An example, therefore, for some natural language phenomena that cannot be modelled with regular language, would be very nice and interesting!

Theoretically, you can nest sentences arbitrarily depth, by using subclauses and this excluded any finite state mechanism. The inventor of the phrase structure grammars himself looked at finite state languages, and compared them with the model of phrase structure grammars. The abstract of his paper Finite State languages reads:

We find that no finite-state Markov-process [...] can serve as an English grammar [...]

The idea to use finite Markov processes, which came down to finite automata in Chomskys work, go back to ideas of Shannon (see his seminal work A mathematical theory of communication). If this caught your interest, you might also take a look at the two works Three models for the description of language and Syntactic structures by N. Chomsky, where he further discusses the adequacy of grammars and finite state processes for language description (or production thereof).
Later, these ideas, which originally came from linguistics and where therefore closely related to research on natural languages, where later adapted by computer scientists to describe programming languages. I refer to the seminal papers Two families of languages related to ALGOL by Ginsburg and Rice or Revised Report on the Algorithmic Language Algol 60, where the BNF was introduced, the first papers using this phrase structure (or nowadays context free) grammars to describe programming languages.
But on the other side, you seldom find "arbitrary" complex nested sentences, as, in general, the "cognitive" system could not handle them, or said differently this could be conceived as a finite state systems. I refer, for example, to the famous paper The magical number seven, plus or minus two by G. Miller, which states that for numbers the human brain can only store a finite number $7 \pm 2$ of digits. Similar restrictions might hold for language processing, see the textbook The psychology of language by T. Harley.


No common terms between polynomials: an efficient check? The "common term" would be in standard form, but the two input multivariate  polynomials needn't be, e.g $x(1+y)+y$ and $y(x+a+b)$ have one common term, $xy$.

A brute force solution would be to expand both polynomials to standard form, then check for common terms. e.g. $x+xy+y$, $xy+ay+ab$.

Is there a better way?

EDIT if it makes it easier, we can loosen "same term" to allow different coefficients, so that e.g. $2xy$ and $3xy$ count as the "same term". (there must be a more mathy way to say that)...
so, perhaps it becomes like a single component in Fourier analysis?

Maybe, a specific term could be identified by differentiating its factors by their power number of times to eliminate it (e.g. $x^2y^3$, differentiate by $x$ twice and by $y$ three times). Though, seems inefficient, and unclear how to extend that to checking all terms apart from brute force.

BTW "no common terms" is the opposite of "all terms in common" (in a sense), i.e checking for identical polynomials. This does have an efficient algorithm, using the Schwartz-Zippel lemma (see Is there an efficient algorithm for expression equivalence?).

Here is an approach that might occasionally be a bit better in practice, but is still exponential-time in the worst case, so it is not a satisfying answer to your question.  Suppose we want to determine whether the polynomials $f(x,y,\dots),g(x,y,\dots)$ have a common term.  First write

$$\begin{align*}
f(x,y,\dots) &= f_0(y,\dots) + x f_1(y,\dots)\\
g(x,y,\dots) &= g_0(y,\dots) + x g_1(y,\dots).
\end{align*}$$

Then recursively check whether $f_0,g_0$ have a common term; and check whether $f_1,g_1$ have a common term.

To express $f$ in that format, note that

$$f_0(y,\dots) = f(0,y,\dots)$$

so it suffices to plug in $x=0$ into the expression for $f$ to get an expression for $f_0$.  Try to simplify that expression as much as possible using standard rules for simplifying polynomials.  Then, you can write

$$f_1(y,\dots) = (f(x,y,\dots) - f_0(y,\dots))/x.$$

Simplify that expression as much as possible.

If no simplification is done, the running time is exponential in $n$, the number of variables.  We obtain a recurrence of the form $T(n) = 2 T(n-1) + O(1)$, so the worst-case running time is exponential.  The room for hope is that if simplification is done at each stage, it's possible that for some inputs this might be faster than that.  In general it will still be exponential-time in the worst case, though, so I don't know whether this will actually be any better in practice.


Orthogonal range reporting with fixed upper rectangular corner Consider the following special case of orthogonal range searching:

Given a set $S$ of $n$ points in $d$ dimensions, and rectangular queries with a fixed "upper-left" rectangle corner $(0,0,...0)$, report the total number of points inside the rectangle.

This is different in that all rectangles queried have a fixed corner. In this case, will we have a dynamic algorithm with a better runtime, or is the problem still as hard as general orthogonal range searching?

The count of any rectangle $C(U, L, D, R)$ can be obtained combining the counts of 4 fixed "upper-left" retangles:

$C(U, L, D, R) = C(0, 0, D, R) - C(0, 0, U, R) - C(U, 0, D, L) + C(0, 0, U, L)$,

noting $C(up, left, down, right)$ the count in the rectangle delimited by $(up, left, down, right)$.

Thus, you cannot expect more than a factor 4 runtime improvement.


How can I get O(1) prepend on a random-access list? I need a data structure that has the following operation:

$\operatorname{prepend}([x_{n - 1}, ..., x_0], x_n) = [x_n, ..., x_0]$

$\operatorname{prepend}$ should be in $O(1)$.

Assume that you have only randomly-accessible lists available. That is the following operations are available that are all in $O(1)$:

$\operatorname{update}([x_n, ..., x_0], i, y) = [x_n, x_{i + 1}, y, x_{i - 1},  x_0]$
$\operatorname{at}([x_n, ..., x_1], i) = x_i$
$\operatorname{append}(([x_n, ..., x_1], x_0) = [x_n, ..., x_0]$

You could of course reverse the list in $O(n)$ each time but then $\operatorname{prepend}$ would also be in $O(n)$. So the list has to be reversed in real-time at each call of $\operatorname{prepend}$. Is there such data structure?

A deque with growing arrays provides the operations you need in (amortized) constant time. Reversing a deque is simple, you don't move data around, you just switch the meaning of prepend and append and massage the index for at and update.

But you don't seem to want to reverse the list anyway.


How to solve recurrence $T(n) \le 2T(n/3) + c\log_3 n$ using substitution method Show by induction that any solution to a recurrence of the form
  $ T(n) \le 2T(n/3) + c\log_3 n $ is $O(n\log_3 n)$.

Hoping someone can help me with the correct solution.  I attempted two ways to get the solution (but I think that they're both incorrect):

SOLUTION A

\begin{align}
T(n) &\le 2T(n/3) + c \log_3 n \\
&\leq 2[k(n/3)\log_3(n/3)] + c\log_3 n \\
&= (2/3)kn(\log_3 n-1) + c\log_3 n \\
&= (2/3)(kn)\log_3 n \\
&= (2/3)kn + c\log_3n \\
&= [(2/3)kn + c]\log_3n - (2/3)kn
\end{align}

SOLUTION B

\begin{align}
T(n) &\le 2T(n/3) + c \log_3n \\
&\le 2 [ k(n/3)\log_3(n/3) ] + c \log_3n \\
&= (kn - kn/3)(\log_3n - 1) + c \log_3n \\
&= (kn)\log_3n - (kn/3)\log_3n - kn + c\log_3n \\
&= (kn)\log_3n - (2/3)kn + (c - kn/3)\log_3n
\end{align}


How is pre-computation handled by complexity notation? Suppose I have an algorithm that runs in $O(n)$ for every input of size $n$, but only after a pre-computation step of $O(n^2)$ for that given size $n.$ Is the algorithm considered $O(n)$ still, with $O(n^2)$ amortized? Or does big O only consider one "run" of the algorithm at size $n$, and so the pre-computation step is included in the notation, making the true complexity $O(n^2+n) = O(n^2)$?

I understand that you have some computational problem with input size $n$, and you use $f(n)$ time for preprocessing. Perhaps after that, you can answer some kind of queries in $g(n)$ time. Both $f$ and $g$ are functions of the input size, and you can now apply Big Oh and say, for instance, that $f(n) = O(n^2)$ and $g(n) = n$.

Now, nobody is forcing you to "consider the runtime to be $O(n)$" or anything like that. So why not just say it like it is, e.g., "after a $O(n^2)$-time preprocessing step, queries can be answered in $O(n)$ time", or "there is an $O(n^2)$-time algorithm for solving the problem", or whatever it is precisely that holds. It's up to you how you present it.

In particular, I want to clear the misconception that "big O would consider one 'run' of the algorithm". If you look at the definition of Big Oh, you'll see that it says nothing about algorithms or their "runs".


Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n$ Consider the recurrence

  $$ a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n. $$

I tried to solve this as follows. First, I found the homogeneous solution:
$$
a_n^{(h)} = r^2 - 3r + 2r \\
(r-2)(r-1) = 0 \\
r = 2,1 \\
a_n^{(h)} = A \cdot 2^n + B
$$

While trying to solve for the particular solution (adding $n$ for linear independence), I get an answer which is a false statement:
$$
a_n^{(p)} = Cn2^n \\
Cn2^n - 3[C(n-1)2^{n-1}] + 2[C(n-2)2^{n-2}] = 6\cdot 2^n \\
4Cn - 3[2Cn-2] + 2[Cn-2] = 6 \cdot 2^2 \\
4Cn - 6Cn + 6 + 2Cn - 4 = 24 \\
0Cn+2 = 24 \\
0Cn = 22
$$

I’m not sure where the issue lies. Am I performing the problem incorrectly, or does the problem have an issue?

Your calculation is an example of proof by contradiction. You assumed that $a_n = Cn2^n$, and reached a contradiction $0 = 22$. You can conclude that $a_n \neq Cn2^n$.

Your calculation shows that the general solution to your equation is
$$
a_n = A + 2^n B + n2^n C.
$$
For some reason you forgot about the first two terms.

Let $P(x) = \sum_{n=0}^\infty a_n x^n$. Setting $a_{-1} = a_{-2} = 0$, we have
$$
(2x^2-3x+1) P(x) = \sum_{n=0}^\infty x^n (2a_{n-2} - 3 a_{n-1} + a_n) = \\
a_0 + (a_1 - 3a_0) x + \sum_{n=2}^\infty x^n (6 \cdot 2^n) = \\
a_0 + (a_1 - 3a_0) x + 24x^2 \sum_{m=0}^\infty (2x)^m = \\
a_0 + (a_1 - 3a_0) x + \frac{24x^2}{1-2x}.
$$
Since $2x^2-3x+1 = (2x-1)(x-1)$, it follows that
$$
P(x) = \frac{(1-2x)(a_0 + (a_1 - 3a_0) x) + 24x^2}{(1-2x)^2(1-x)} =
\frac{a_0 + (a_1 - 5a_0)x + (24-2a_1+6a_0)x^2}{(1-2x)^2(1-x)}.
$$
Routine calculation shows that
$$
\frac{1}{(1-2x)^2(1-x)} = \sum_{n=0}^\infty (1+2^{n+1}n)x^n,
$$
and so for $n \geq 2$ we get the formula
$$
a_n = a_0 (1 + 2^{n+1}n) + (a_1 - 5a_0) (1 + 2^n(n-1)) + (24 - 2a_1 + 6a_0) (1 + 2^{n-1}(n-2)).
$$
Opening this up, we get the solution
$$
a_n = 24 - a_1 + 2a_0 - (24 - a_1 + a_0) \cdot 2^n + 12 \cdot n2^n.
$$


What is the time complexity in big-O notation of Algorithm X? Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that solves the NP-complete problem exact cover (EC). (It actually finds all solutions to EC.)

I do not understand how such algorithm could do that. What is the time complexity of this algorithm in terms of big-O notation?

Here is the algorithm from Wikipedia.

  If the matrix $A$ has no columns, the current partial solution is a valid solution; terminate successfully.
  Otherwise choose a column $c$ (deterministically).
  Choose a row $r$ such that $A_{r,c} = 1$ (nondeterministically).
  Include row $r$ in the partial solution.
  For each column $j$ such that $A_{r,j} = 1$,

  for each row $i$ such that $A_{i,j} = 1$,

  delete row $i$ from matrix $A$.

  delete column $j$ from matrix $A$.

  Repeat this algorithm recursively on the reduced matrix A.

Step 3 of the algorithm is done nondeterministically. What does this mean? (I think this is the point why I cannot find the big-O complexity of the algorithm.)

An implementation of Algorithm X in python can be found in Algorithm X in 30 lines! where I cannot find the nondeterministic choice of step 3.

Its worst-case running time is exponential.

By "nondeterministic", this essentially means "try all possibilities".


What should I read before tackling Michael Huth's Logic in Computer Science: Modelling and Reasoning about Systems? I have to read Logic in Computer Science: Modelling and Reasoning about Systems by M. Huth and M. Ryan for a class next semester. However Amazon reviews say it's hard to read unless you're an advanced student and I'm very new to computer science. Is there any other book I may read before I approach this one that would make it easier to understand?

From the Preface of the 2nd Edition:

  The book requires that students know the basics of elementary
  arithmetic and naive set theoretic concepts and notation. The core
  material of Chapter 1 (everything except Sections 1.4.3 to 1.6.2) is
  essential for all of the chapters that follow. Other than that, only
  Chapter 6 depends on Chapter 3 and a basic understanding of the static
  scoping rules covered in Chapter 2 – although one may easily cover
  Sections 6.1 and 6.2 without having done Chapter 3 at all.

Of course, having elementary prerequisites and being easy are two different things. I've only read the first two chapters as a way to self-teach some logic so I can't comment on the 'latter' material.

The cool thing is that you're only obligated to read the first chapter and then you can proceed to read most of the other chapters in whichever order suits you. If you want a free supporting material, there's the Stanford Logic MOOC and the Mathematics for Computer Science course from MIT.


Which Grows Faster: Factorial or Double Exponentiation Which of the functions among $2^{3^n}$ or $n!$ grows faster?

I know that $n^n$ grows faster than $n!$ and $n!$ grows faster than $c^n$ where $c$ is a constant, but what is it in my case?

You can find the result by taking a $\log$. Hence:

$$\log(2^{3^n}) = 3^n$$
$$\log(n!) \leqslant \log(n^n) = n\log n$$

(In the latter equation, we have used the fact that $n! \leqslant n^n$, as you note in the question.)

Of course $3^n$ grows faster than $n \log n$.
As $\log$ is an increasing function, we can say $2^{3^{n}}$ grows faster than $n^n$, and also $n!$.


Float multiplication While doing the multiplication 1.4*0.8 in a python program, I got the result as 1.1199999999999999.

Why didn't I get 1.12 exactly?

In C programming language, the same expression gives 1.1200.

$1.4$ and $0.8$ cannot be represented exactly in a IEEE floating point number.

This means that the actual number stored and operated on is really $1.4+\epsilon$ and $0.8+\epsilon$ where $\epsilon$ is the rounding error and when you multiply those two ends up as $1.12 + 2.2\epsilon+\epsilon^2$.

This rounding error propagation can bite you in the *** at the weirdest times (like making a platform drift slowly upwards enough to allow niche players to shave off a specific button press) and make the results at the end completely wrong if enough operations align to make the error significant enough to matter. One of the major operations to watch out for in this regard is subtraction of nearly equal numbers so the mathematical result becomes close to the error on the inputs.


How is the set of functions from ${\{a,b\}}$ to $N$ countable? Assume a set of functions from ${\{a,b\}}$ to $N$

Where $N$ is the set of Natural numbers.

Let us assume that the size of $N$ is $n$.
i.e $|N|=n$

The first element $a$ have $n$ choices for mapping.
The second element $b$ have $n$ choices for mapping as well.

So the number of functions = $n.n$ = $n^2$.
which  is strictly greater than $n$ and hence the size of $N$.
So "Set of functions from ${\{a,b\}}$ to $N$", should not be countable. But it is. I am just a beginner in discrete maths, so this might be a stupid question for some. But please explain.

You are confusing countable and finite. A finite set is always countable, however a countable set can be infinite.

You only need to find an injection from your set and $\mathbb{N}$, it means that you can identify each element of your set using a natural number (a code if you prefer). For instance you can code the set of functions from $\{a,b\}$ to $\mathbb{N}$ using the injection $\alpha$ below:

$\alpha : \mathbb{N}^{\{a, b\}} \rightarrow \mathbb{N} : f \mapsto 2^{f(a)}(2f(b)+1)$


Query regarding the structure of Graph over All (known/unknown) NPC Problems? Let us consider the set of all NPComplete problems. Since every problem in the set is Reducible to/from at least one known NPComplete problem, lets create a directed Graph with the following conventions:

If a problem B is Reducible from Problem A, create an edge from A to B. We assume an oracle who knows all possible reductions who creates the edges.

Here are a few questions regarding the Graph.

Q1. Is the graph strongly connected (i.e. every problem in the Graph is reachable from or reducible from every other problem for every instance?

Guess: I presume the answer is yes.

Q2. For any two problems (say A, B), no matter what the distance b/w them is, there is guaranteed at most Polynomial Blowup in problem size when we reduce, from A to B?

Guess: Unsure. For any problem P, if we reduce from one of its neighboring problem, there is polynomial increase or decrease in space. But, not sure if it holds if the problems are arbitrarily large distance apart. The definition of NPC, needs one single reduction in Polynomial time, but space analogue of reduction for All NPC Problem pairs seems out of reach.

The definition of NP-complete is that the problem is in NP and every problem in NP (including every other NP-complete problem) is reducible to that problem. So the graph you describe is not only strongly connected: it is a complete graph.
By the above, the distance between any two problems is 1. But, even if you follow a longer path of $k$ reductions, where the $i$th has polynomial blow-up $p_i$, the total blow-up for an input of size $n$ is $p_k(p_{k-1}(\cdots p_1(n)\cdots))$, which is still a polynomial.


Left-Factoring a grammar into LL(1) I have a homework assignment where I need to convert a grammar into LL(1). I've already removed the left recursion, but I'm having trouble doing left-factoring. All of the examples I've found are simple, and look something like this:

A -> aX | aY
becomes:
A -> aZ
Z -> X | Y

I understand that. However, my grammar looks more like this:

X -> aE | IXE | (X)E
E -> IE | BXE | ϵ
I -> ++ | --
B -> + | - | ϵ

I'm not sure how to apply the simpler example to this. I've been trying for at least a couple of hours and I've lost track of all of the things I've tried. Generally, my attempts have looked something like this:

X  -> X' | IXE
X' -> aE | (X)E
E  -> IE | BIX'E | BX'E | ϵ

And I then try to convert the E rules into ones having only one production starting with + or -:

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> IE | B'IX'E | IX'E | B'X'E | X'E | ϵ

And then...

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> +P | -M | ϵ
P  -> +E | IX'E | +X'E | X'E
M  -> -E | IX'E | -X'E | X'E

And so on. But I continually end up with a lot of extra nonterminals, and some very long productions / chains of productions, without actually having left-factored it. I'm not sure how to approach this - I can't seem to eliminate some nonterminal having multiple productions starting with a + and with a -.

Let's have a look at your grammar:

$\qquad \begin{align}
X &\to aE \mid IXE \mid (X)E \\
E &\to IE \mid BXE \mid \varepsilon \\
I &\to \text{++} \mid \text{--} \\
B &\to \text{+} \mid \text{-} \mid \varepsilon
\end{align}$

Note that $X$ does not need left-factoring: all rules have disjoint FIRST sets¹.
If you want to make this obvious, you can drop $I$ and inline it:

$\qquad \begin{align}
X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\
E &\to \text{++}E \mid \text{--}E \mid BXE \mid \varepsilon \\
B &\to \text{+} \mid \text{-} \mid \varepsilon
\end{align}$

Similarly, we can inline $B$:

$\qquad \begin{align}
X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\
E &\to \text{++}E \mid \text{--}E \mid \text{+}XE \mid \text{-}XE \mid XE \mid \varepsilon
\end{align}$

Now we see that we actually have to do left-factoring on $E$: we have obvious conflicts, and we get additional conflicts via $XE$. So, let's inline $X$ once at $XE$:

$\qquad \begin{align}
X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\
E &\to \text{++}E \mid \text{--}E \mid \text{+}XE \mid \text{-}XE \mid aEE \mid \text{++}XEE \mid \text{--}XEE \mid (X)EE \mid \varepsilon
\end{align}$

And now we can left-factor as easily as in your example:

$\qquad \begin{align}
X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\
E &\to \text{+}P \mid \text{-}M \mid aEE \mid (X)EE \mid \varepsilon \\
P &\to \text{+}E \mid XE \mid \text{+}XEE \\
M &\to \text{-}E \mid XE \mid \text{-}XEE
\end{align}$

By now we can see that we are not getting anywhere: by factoring away $\text{+}$ or $\text{-}$ from the alternatives, we dig up another $X$ which again has both $\text{+}$ and $\text{-}$ in its FIRST set.

So let's have a look at your language. Via

$\qquad \displaystyle X \Rightarrow aE \Rightarrow^* aI^n E \Rightarrow aI^nBXE$

and

$\qquad \displaystyle X \Rightarrow aE \Rightarrow^* aI^n E \Rightarrow aI^nIE$

you have arbitrarily long prefixes of the form $+^+$ which end differently, semantic-wise: an LL(1) parser can not decide whether any given (next) $\text{+}$ belongs
to a pair -- which would mean choosing alternative $IE$ -- or comes alone -- which would mean choosing $BXE$.

In consequence, it doesn't look like your language can be expressed by any LL(1) grammar, so trying to convert yours into one is futile.

It's even worse: as $BXE \Rightarrow BIXEE \Rightarrow^* BI^n X E^n E$, you can not decide to chose $BXE$ with any finite look-ahead. This is not a formal proof, but it strongly suggests that your language is not even LL.

If you think about what you are doing -- mixing Polish notation with unary operators -- it is not very surprising that parsing should be hard. Basically, you have to count from the left and from the right to identify even a single $B$-$\text{+}$ in a long chain of $\text{+}$. If I think of multiple $B$-$\text{+}$ in a chain, I'm not even sure the language (with two semantically different but syntactically equal $\text{+}$) can be parsed deterministically (without backtracking) at all.

That would be the sets of terminals that can come first in derivations of a non-terminal/rule alternative.


Arithmetic coding and "the optimal compression ratio" Trying to learn more about compression techniques and found something in the wikipedia article on arithmetic coding that I'm not sure I fully grok. In describing how Huffman Coding can sometimes be inefficient, the author refers to an 'optimal compression ratio' that seems to be a function of the probabilities of a given symbol being represented at any given position in the dataset. Am I correct in understanding this to mean:

Given a set of data and a set of probabilities describing the likelihood of any given member of the dataset being a given symbol, then there is no way to represent that data encoded in that manner in fewer bits than the calculated optimal compression ratio?

In other words: there's no way to encode something in few than 'optimal' bits so don't try?

Beware: The phrase "optimal compression ratio" is perhaps a bit misleading.  It is intended to make you think of "the best compression ratio that is achievable", but there are some assumptions that it comes with -- you should really think of it as "the best compression ratio that is achievable, under a certain set of assumptions" (or "the best compression ratio that is achievable by a certain type of compression algorithm").  Since those assumptions often aren't literally true, there's no real guarantee that this is truly the smallest something can be compressed to.

In particular, one key assumption is that the symbols come from a memoryless iid source: i.e., there is a distribution on characters, and each character is sampled randomly from this distribution, independent of all previous characters.  For a source that satisfies this assumption, we can calculate the best achievable compression ratio; it is the entropy.

Of course we know this isn't true in practice; in English text, if the previous letter was 'q', the next one is much more likely to be a 'u' than otherwise.  So really you should think of the entropy as telling you "if you didn't take advantage of that type of knowledge, what is the best compression ratio you could achieve?".


Lack of Stack Pointer Register Suppose a processor lacks STACK Pointer Register. But, It does have STACK.
Then, in my opinion, a program will still be able to call subroutines but, will be unable to return back from the subroutines.
Please do clarify me where I have made a wrong assumption.
Also do mention the possible outcomes of the scenario.

Using a stack for function calls does not require any special support from the processor. It's up to the compiler to decide where to put the data relative to a function call (return address, parameters, possibly reserved space for the return value). A common convention is to designate one particular register as the stack pointer. This does not require any special processor instruction, it can be a general-purpose register. A function call looks like this:

Write parameters to the memory region at address SP (stack pointer register)
Decrease SP by the size of the parameters
Write PC (program counter register) to the address SP
Decrease SP by the size of PC
Jump to the function entry point

Returning from the function looks like this:

Load a PC-sized value from SP into a register A
Increase SP by the size of PC
Jump to A

Some processors have a particular register R with instructions to store a word in memory at the address designated by R and decrement R, and to load a word in memory at the address designated by R and increment R. In this case, the processor documentation typically describes R as the stack pointer register and compilers use it to store the address of the function call stack. But if the processor doesn't have such instructions, the compiler just emits separate instructions for load/store and for increment/decrement. The register doesn't need any special properties.


Not quite-infinitely expandable human-friendly naming system? This may be a known problem, with known approaches, but I can't find the right way to search for it.

I would like to name points along a line of unknown final length such that their name reflects their relative position to all other named points on that line.  One should be able to insert an arbitrary number of names at any point along the line including outside the existing first and last named points. A lexicographical sort of the point names would always result in a list of points in a monotonic order.

An order of magnitude estimate of the total number of points to be ultimately named can be supplied up front

Additional restrictions:

Names must be stable, no-renaming after initial assignment
Names may be constructed from a limited character set: 25 lowercase letters a-z with 'L' removed.
The naming scheme should not require an extreme fan-out of name length when adding names either outside the existing points or between two adjacent points. E.g. Imagine that I want to add something before the name 'a', that wouldn't be possible while maintaining linear order during sorting.  Starting with 'b' only delays the issue.  Same for z on the other end.

Names should be of the shortest possible length such that a human could easily glance at one and then write it out elsewhere for most names.

It is highly likely that one would want to insert names between previously adjacent names, and then later between adjacent named points in that previous insertion.

The real-life use case for this is the creation of spatial names for all features of a given kind, say genes, in a species when we don't know in advance the total set of features.  This is because different individuals only contain a subset of the total sequence space that the whole population of organisms encompass.  The problem is easy to solve with static sets of sequences, but not if you allow them to expand at any point along the line (chromosomes) with the addition of new information.  The set sizes of interest encompass 10^5 -10^7 items.

As David points out in a comment, you are asking for an impossible thing because the lexiocgraphic order does not have infinite descending chains, and so you will run out of names if you keep adding points on the far left side. So forget the lexicographic order. (You may keep it if you have an upfront upper bound on the number of points.)

You can use the naming scheme x_N_M where N and M are numbers. Think of this as indexing a point with the fraction N/M. Because fractions are dense, you will never run out of them. To insert a new point on the left of the leftmost point x_N_M, name the new point x_N_2M. To insert on the right of the rightmost point x_U_V name the new point x_2U_V. And to insert between adjacent points x_A_B and x_C_D, name the new point x_E_F where E/F is the average of A/B and C/D.


Why is $A \lor (A \land \neg B) \equiv A$? I would like to know if there is a rule to prove this. For example, if I use the distributive law I will get only $(A \lor A) \land (A \lor \neg B)$.

I find pictures are great for anything simple enough to use them, which this is.

Remember:

AND means the area taken up by both things. So the middle one is what is taken up outside B, but also inside A. Their junction is not counted because it is inside A but not outside B.

OR means it is covered by either one or both. Both of them cover the part of A that is outside B, and the junction is covered by A (first picture) so it is counted too.
All in all, you just have A again.

Sorry if this is too simplistic, not sure what level you are at.


O(n+m) vs O(n+2m) time complexity Are $O(n+m)$ and $O(n+2m)$ the same?
If $m>n$, then both complexities are $O(m)$. Likewise, if $n>m$, then they are $O(n)$. Is this correct?

I would like to try an intuitive explanation.
Assume your algorithm works in $2m$ time units on your current machine. If you run it on a machine twice as fast, then it takes $m$ times units. As we do not know (and do not care) on which machine(s) the algorithm will run, this makes the $2$ factor irrelevant. This is what the big-$O$ notation captures, in a sense.
(In addition, if we know that $n>m$ then we have $3n > n+2m$, and so anything below $n+2m$ also is below $3n$. As big-$O$ deals with upper bound, this means that $O(n+2m)$ complexity is, in this case, in $O(3n)$ complexity which, as explained above, is nothing but $O(n)$.)
Hope this helps.


n-state DFA that requires n-2 steps to check equivalence We have a DFA $A = (Q,\Sigma, \delta, q_0, F)$.
States $p, q$ $\in Q$ are equivalent, $p \sim  q$ if $ \forall w \in \Sigma ^ \ast$ $ \delta^*(p,w) \in F \iff \delta^*(q,w) \in F$

States $p,q$ are equivalent after $i$ steps, $p \sim ^i q$, if $ \forall w \in \Sigma ^ \ast$ such that $|w|\le i$ $ \delta^*(p,w) \in F \iff \delta^*(q,w) \in F$

$p \sim q$, if $ \forall i$  $p \sim ^i q$

State equivalence $\sim$ creates a partition $Q/\sim$ of states to equivalence classes.

I am trying to find a $n$-state DFA for all $n \ge 2$ where the state equivalence relation $\sim$ is equal to the state equivalence relation after $n - 2$ steps, $\sim^{n-2}$, but is not equal to the state equivalence relation after $n - 3$ steps, $\sim^{n-3}$.

So I'm searching for DFAs which require exactly $n - 2$ transitions to check the equivalence. I don't know how to approach this problem.

Consider the following DFA on the alphabet $\{0\}$:

The states are $q_1,\ldots,q_n$, with $q_1$ initial and $q_n$ final.
$\delta(q_i,0) = q_{i+1}$ for $i < n$, and $\delta(q_n,0) = q_n$.

Consider the pair of states $q_1,q_2$. For $i < n-2$, $\delta^*(q_1,0^i),\delta^*(q_2,0^i) \notin F$, whereas $\delta^*(q_1,0^{n-2}) = q_{n-1} \notin F$, $\delta^*(q_2,0^{n-2}) = q_n \in F$.


Why does the formula 2n + 1 find the child node in a binary heap? I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the indicies of the children of element at index n can be found with

$leftchild = 2n + 1$

$rightchild = 2n + 2$

I can see that this formula works and have played around with it for a little bit looking at examples, but I still don't understand why it works. Can anyone help me understand the intuition behind why this is correct?

I would like to propose my revisited version of Hiroki's answer.
Currently it's been sitting in peer-review (https://cs.stackexchange.com/review/suggested-edits/66932) for a while, so it's not being of use to anyone.
Credits to Hiroki for the original answer and structure.
I've simply clarified the math and made every step explicit and chosen a slightly different terminology.

Let's assume that each tier of the heap is an array.
T1 [                n0                 ]

T2 [      n1,                n2        ]

T3 [  n3,     n4,       n5,       n6   ]

T4 [n7, n8, n9, n10, n11, n12, n13, n14]

It may not be clear, but I want you to imagine that $n0$ is the parent of $n1$ and $n2$.
Likewise,  $n1$ is the parent of $n3$ and $n4$.
For example, $T2$, the second tier, contains nodes $[n1, n2]$ and has length $2$.
Let's say $i$ is the global index of the node in question (i.e. the node's index if the entire tree were to be collapsed within a single array), and
$j$ is the local index of the node, i.e. the index of the node within its tier.
For example, in the diagram above, if the node in question is $n3$, $i = 3$ and $j = 0$, because $n3$ is the first element in the 3rd tier.
i = global index of a node n
j = local index of a node n within the tier where the node exists
T = tier

The maximum number of nodes in a tree up to a certain tier can be expressed by:
$total\_nodes\_up\_to(T) = 2^T - 1$
e.g. when you have 3 tiers, you can have at most 7 nodes, as $2 \cdot 2 \cdot 2 - 1 = 7$
This is because there are $2^{T-1}$ nodes in each tier (note: tier numbering in our example arbitrarily starts from $1$, not $0$) and the sum of powers of $2$ up to $n$ is equal to $2^{n+1} - 1$, as you can see here https://math.stackexchange.com/questions/1990137/the-idea-behind-the-sum-of-powers-of-2
Since indexes start from 0, the index of the last node in an array of nodes will be $numNodes - 1$. This means that the global index of the last node in some tier $T$ is:
$i_{last} = total\_nodes\_up\_to(T) - 1 = 2^T-1-1$
While the local index of the last node in the tier is:
$j_{last} = 2^{T-1} - 1$ // since there are $2^{T-1}$ elements in tier $T$
We can now compute the global index of the first node in the tier by subtracting the local index of the last node in the tier from its global index. You can visualize it mentally as "walking backwards" starting from the the last node - if you take local-index-many steps back you land onto the first node in the tier:
$i_{first} = i_{last} - j_{last}$
$i_{first} = 2^T - 1 - 1 - j_{last}$
$i_{first} = 2^T - 1 - 1 - (2^{T-1} - 1)$
$i_{first} = 2^T - 2^{T-1} - 1$
$i_{first} = 2*2^{T-1} -2^{T-1} - 1$
$i_{first} = (2 - 1)*2^{T-1} - 1$
$i_{first} = 2^{T-1} - 1$
We can now compute the global index of a node $n$ by adding its local index and the global index of the first node in its tier:
$i = i_{first} + j$
$i = 2^{T-1} - 1 + j$
Let's now think about the first (left) child of the node in question.
The left child, n', will be in the next tier, T+1.
The indices in T+1 will be referred to as i', j', i'_first ...

Based on what we've shown so far, we can say that the global index of the first node in the next tier is:
$i_{first}' = 2^{T+1-1} - 1 = 2^T - 1$
Now, for each predecessor of the parent node $n$ in tier $T$ there will be 2 predecessors of left-child node $n'$ in $T+1$. Also, given index $j$ in $T$, we know there are $j$ predecessors of $n$ in $T$ - i.e. the index of a node is equal to the number of its predecessors. So we can conclude that:
$j' = 2j$
Putting it all together, we can conclude that
$i' = i_f' + j'$
$i' = 2^T - 1 + 2j$
Now let's rework the previous equation for the global index of parent node $n$, $i = 2^{T-1}-1+j$ to the following:
$i + 1 = 2^{T-1} + j$
Finally, let's compare that to the equation of the global index of the left-child node:
$\begin{align}
i' &= 2^T - 1 + 2j\\
   &= 2*2^{T-1} + 2*j - 1\\
   &= 2*(2^{T-1} + j) - 1\\
   &= 2*(i + 1) - 1      \text{//NOTE: Here we use $i + 1 = 2^{T-1} + j$ mentioned above}\\
   &= 2i + 2 - 1\\
   &= 2i + 1\\
\end{align}$
Although the question was why the $2n + 1$ formula works, note that I used $i$ instead of $n$!
Let me know if there is anything unclear.


Many-one-reductions with finite image Let $K$ be the halting set and suppose $K \leq_m A$ (under some function $f$), that is, $K$ is many-one-reducible to $A$.

How can $f(K)$ be a finite set?
Why if $B$ is recursive, is $f^{-1}(B)$ also recursive?

As the name suggests, a many-one reduction can map many instances of $K$ onto a single instance of $A$.  If there are no restrictions on the power of $f$, then you can pick some $a\in A$ and $b\notin A$ and then define
$$f(x)=\begin{cases}
a &\text{ if }x\in K\\
b &\text{ if }x\notin K\,.
\end{cases}$$

However, if $f$ is restricted to be computable then the image of $f$ is necessarily infinite. This is because every finite set is computable so, if the image of $f$ were finite, you'd have a computable reduction from the halting set to a computable set, which is impossible because that would mean the halting set would be computable too.

If $B$ is recursive and $f$ is computable then you can decide whether $x\in f^{-1}(B)$ just by checking whether $f(x)\in B$. If $B$ isn't recursive or $f$ isn't computable, all the bets are off.


How do I construct reductions between problems to prove a problem is NP-complete? I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How should I approach a problem that asks me to prove a problem is NPC?

There is no magic bullet; NP-hardness proofs are hard.  However, there is a general framework for all such proofs.  Many students who struggle with NP-hardness proofs are confused about what they're supposed to be doing, which obviously makes it impossible to figure out how to do it.  So here is what to do to prove a problem NP-hard.

First, unless you're just doing homework, you have to decide which NP-hard problem to reduce to your problem.  This is largely a question of "smell".  If the number 3 appears anywhere in the problem statement, try reducing from $\mathsf{3SAT}$ or $\mathsf{3Color}$ or $\mathsf{3Partition}$.  (Yes, I'm serious.)  If your problem involves finding an optimal subsequence or permutation or path, try reducing from $\mathsf{HamiltonianCycle}$ or $\mathsf{HamiltonianPath}$.  If your problem asks for the smallest subset with a certain property, try $\mathsf{Clique}$; if it asks for the largest subset with a certain property, try $\mathsf{IndependentSet}$.  If your problem involves doing something in the plane, try $\mathsf{PlanarCircuitSAT}$ or $\mathsf{PlanarTSP}$.  And so on.  If your problem doesn't "smell" like anything, $\mathsf{3SAT}$ or $\mathsf{CircuitSAT}$ is probably your best bet.

Obviously, you need to already know precisely how all these problems are defined, and the simpler the problem you reduce from, the better.  So as cool as the result might look in the end, I don't recommend reducing from $\mathsf{Minesweeper}$ or $\mathsf{Tetris}$ or $\mathsf{OneCheckersMove}$ or $\mathsf{SuperMarioBros}$.

Second, the actual reduction.  To reduce problem X (the one you know is NP-hard) to problem Y (the one you're trying to prove is NP-hard, you need to describe an algorithm that transforms an arbitrary instance of X into a legal instance of Y.  The reduction algorithm needs to do something specific with each "feature" of the X-instance; the portion of the output for each "feature" is usually called a gadget.

But what's a feature?  That depends on problem X.  For example:

To transform an instance of $\mathsf{3SAT}$, you'll need a gadget for each variable and for each clause in the input formula.  Each variable gadget should have two "states" that correspond to "true" and "false".  Each clause gadget should also have multiple "states", each of which somehow forces at least one of the literals in that clause to be true.  (The states are not part of the output of the reduction algorithm.)
To transform an instance of $\mathsf{3Color}$, you'll need a gadget for each vertex and each edge of the input graph, and another gadget to define the three colors.
To transform an instance of $\mathsf{PlanarCircuitSat}$, you'll need a gadget for each input, for each wire, and for each gate in the input circuit.

The actual form of the gadget depends on problem Y, the one you're reducing to.  For example, if you're reducing to a problem about graphs, your gadgets will be small subgraphs; see the Wikipedia article.  If you're reducing to a problem about scheduling, each gadget will be a set of jobs to be scheduled.  If you're reducing to a problem about Mario, each gadget will be a set of blocks and bricks and Koopas.

This can get confusing if both problems involve the same kind of object.  For example, if both X and Y are problems about graphs, your algorithm is going to transform one graph (an instance of X) into a different graph (an instance of Y).  Choose your notation wisely, so that you don't confuse these two graphs.  I also strongly recommend using multiple colors of ink.

Finally, your reduction algorithm must satisfy three properties:

It runs in polynomial time.  (This is usually easy.)
If your reduction algorithm is given a positive instance of X as input, it produces a positive instance of Y as output.
If your reduction algorithm produces a positive instance of Y as output, it must have been given a positive instance of X as input.

There's an important subtlety here.  Your reduction algorithm only works in one direction, from instances of X to instances of Y, but proving the algorithm correct requires reasoning about the transformation in both directions.  You must also remember that your reduction algorithm cannot tell whether a given instance of X is positive or negative—that would require solving an NP-hard problem in polynomial time!

That's the what.  The how just comes with practice.


Creating an O(n log n) time and O(n) space algorithm for counting pairs in an array Given an integer array $a$, create a function, $\text{int} \; \text{pairs}( \text{int} \;a[\;])$ that returns the number of equal element pairs in the array. For example, given the array $a=[2,5,1,2,5,1,1,6]$ the pairs are $(2,2), (1,1), (1,1), (1,1)$ and $(5,5)$, so the function should return $5$. The solution needs to run in $O(n \log n)$ time and $O(n)$ space.

My algorithm first sorts the array using  quick sort in $O(n \log n)$ time, then go through the sorted array and for each chunk of equal elements, keep track of the size of the group(which resets to $1$ when a distinct element is next), runs in $O(n)$ time.

If the next element equal the previous element, then increase the group size variable.

Otherwise, if the group size variable is bigger than $1$, add $n \choose 2$, where $n$ is the group size, to the overall sum of pairs variable(initially $0$), then reset the group size variable to $1$.

The problem I have is that, although the algorithm is correct, the algorithm runs in $O(n^2)$, which I think is because of the $n \choose k$ method.

The pseudo-code for my $n \choose k$ method is:

int binomial(n,k)
    if(k>(n-k)) k=n-k

    int b=1
    for(int i=0, m=n; i<=k; i++, m--)
        b=b*m/i

    return b

If the method does run in $O(n^2)$, then can I modify it to make it $O(n \log n)$. If its not possible to make a binomial coefficient method to run faster than $O(n^2)$, then does anyone have another algorithm for achieving the number of pairs from the array.

Just evaluate $\binom k2$ with $\frac{k(k-1)}2$, this takes $O(1)$.

Note that if the pairs are to be counted "without replacement", the formula is $\lfloor\frac k2\rfloor$.


Length of the solution calculation in Breadth-first I'm trying to figure out how to calculate the route cost on this graph (it's the missionaries and cannibals game)

I have my definition as:

Mi = Missionary on the initial side, C = Cannibal on the initial side, B = Boat [I = Boat in the Initial Side, F = Boat on the Final Side],
Mf = Missionary on the other side of the river, Cf = Cannibal on the other side of the river
State: (Mi, Ci, B, Mf ,Cf)
Initial Status: (3, 3, I, 0,0)
Final Status: (0, 0, F, 3,3)
Status Space (All the valid statuses):
{(3,3,I,0,0),(3,2,F,0,1),(2,2,F,1,1),(3,1,F,0,2),(3,2,I,0,1),(3,0,F,0,3),(3,1,I,0,2),(1,1,F,2,2),(2,2,I,1,1),(0,2,F,3,1),(0,3,I,3,0),(0,1,F,3,2),(0,2,I,3,1),(2,2,I,1,1),(3,2,I,0,1),(0,0,F,3,3)}

Rules:

1.  Bote can only carry two people
2.  One person has to drive the boat
3.  Cannibals can't outnumber the missionaries or they the missionaries will be eaten.
Cost: 1 per crossing.

Exhaustive Search (or Brute Search):

(3, 3, I, 0, 0) -> (2, 2, F, 1, 1) -> (3,2,I,0,1), -> (3,2,I,0,1) -> (3,2,1,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,F,1,1) -> (0,2,F,3,1) -> (0,3,I,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (0,0,F,3,3)

According to me and the graph the route cost for Exhaustive Search would be 11.

How can I calculate the route cost for that graph for Breadth-first?

I do know that Breadth-first I have to separate the graphs on levels and it will test each node on that level against the final result (depending on the direction, clockwise, or counterclockwise) but I'm not sure if I should take each node as a crossing (I'm getting 14 as length of the solution). For instance in the image I take the crossing from (3,3,I,0,0) to (3,2,F,0,1) as 1 and then there isn't more child-nodes on that branch so I should get back to (3,3,I,0,0) in order to reach the branch of (2,2,F,1,1) this I don't know If I should count it too or not

To get 14 I'm doing. (3, 3, I, 0, 0) -> (3,2,F,0,1) -> (2,2,F,1,1) -> (3,1,F,0,2) -> (3,2,I,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,I,1,1) -> (0,2,F,3,1) -> (0,3,1,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (2,2,I,1,1) -> (0,0,F,3,3)

Because of this doubts I have troubles calculating the Length of the solution

I do not know how your sources define "route cost" (I've never heard that term).

There are two points of view I can imagine.

Length of the solution

Once you reach a fitting leaf you have found your solution and can
   abort. The length of the solution, i.e. the number of steps you have
   to perform to get everybody across, is the length of the path from the
   root to that leaf.
Cost of the algorithm

The number of steps the algorithm has to perform is different, of
  course; it may visit many nodes that are not part of the final
  solution. The details depend on the specific implementation at hand.

Specifically, you seem to be concerned about backtracking out of
  dead ends. The usual way to implement BFS is using a queue which
  makes backtracking free since you don't actually do it; the next
  node to visit is already at the front of the queue.

If you don't use a queue and backtrack explicitly, well, you get
  quadratic worst-case performance. Don't do it.


ANN - Backpropagation with multiple output neurons Can I utilize the backpropagation algorithm in a layered, feed-forward ANN in instances where there are multiple output neurons? If so, how? Links to (somewhat) comprehensible resources would be greatly appreciated, if nothing else.

The background is that I'm working on a simple C program that can create, propagate, and train dynamically sized, layered feed-forward ANNs. For the most part, everything's been going swimmingly. However, I'm having a little trouble wrapping my head around backpropogation. My main concern right now is how to use the backpropagation method for training a network that has multiple output neurons. All the examples/explanations I've found only use one output neuron. I'm assuming this is for the sake of simplicity. But, I'm wondering if, perhaps, this is because the backpropagation algorithm is only designed to works with one output neuron at a time. In other words, it can only be applied relative to one output neuron every time an feed-forward ANN is propagated. This would make sense, as it is known to be among the simplest ANN training methods.

Here are links to my aforesaid resources (or at least, the ones I found intuitive):

http://home.agh.edu.pl/~vlsi/AI/backp_t_en/backprop.html
https://www.youtube.com/watch?v=GlcnxUlrtek
https://www.youtube.com/watch?v=IruMm7mPDdM (I'm actually not entirely certain as to whether or not this explanation accounted for multiple output neurons; if it did, it must've went over my head)

Thanks!

Backpropagation works for feed-forward ANNs with multiple output neurons.

For an output neuron $z_r$ in an ANN, the delta function is

$$
\delta_r = \frac{\partial f_r(a_r)}{\partial a_r} e_r\qquad,
$$
where $f_r(a_r)$ is the activation function of $z_r$, $a_r$ is the sum of weighted inputs of $z_r$ and $e_r$ is the error of $z_r$, $e_r$ = $z_r$ - $y_r$ ($y_r$ is the target value).

for a hidden neuron $z_k$ the delta function is the sum of weighted deltas of the neurons in the next layer (in forward direction) of $z_k$. So, for a neuron in the layer next to the output layer, the delta function is:

$$
\delta_k = \frac{\partial f_k(a_k)}{\partial a_k} \sum_{r\in post(k)}\delta_r w_{kr}\qquad,
$$

where $w_{kr}$ is the weight between neurons $z_k$ and $z_r$. I suggest to have a look at the Wikipedia article about Backpropagation, especially the subsection 'finding the derivative of the error'. Following the link at the end of this section (https://www4.rgu.ac.uk/files/chapter3%20-%20bp.pdf), the first five pages or so might be helpful for a better understanding.


what is meant by support of a filter? what is meant by support of a filter in context of image processing?
In the attached link of a short tutorial for detecting bar in an image by gabor filter,it is said that γ=1 helps in finding the support of the filter.
link1

Many filters, particularly linear time-invariant ones, are represented by a kernel function. The output of a filter at a point is calculated by a weighted average of all the points of the input where the weights are specified by the kernel function. The kernel function takes displacements from the current output point we're calculating to other points, so it is always relative to the output point.

The support of a filter is then, intuitively, the "size" of the kernel. Any displacement for which the kernel function is $0$ means that we don't have to consider the corresponding point at all when calculating the value of an output point. Therefore, the most strict definition of support is that it is the set of displacements where the kernel function is non-zero. This could be a quite complicated set in general, and so isn't particularly helpful for understanding or calculation. A looser definition would be the support is any set (of displacements) which contains all the displacements where the kernel function is non-zero. This allows us to conservatively approximate the support with some simple-to-describe shape. This will usually be something like an ellipse or rectangle or square (or their lower-/higher-dimensional analogues). Given such a class of approximate shapes, the support will usually be taken to be the smallest approximate shape which contains all the displacements for which the kernel function is non-zero.

For that page, the support is the smallest ellipse which contains all the non-zero inputs of the kernel function. For discrete kernels that are typically used to implement these filters on a computer, usually a rectangular support is used. This allows calculating the weighted average by iterating only over the points in a (typically much smaller) sub-rectangle of the input, rather than iterating over the entire input while multiplying most values with zero. It also means the kernel function can be described by only specifying its values for that rectangle, and this is usually represented by a matrix called the mask in the 2D case.


Diagonalization argument for MAJORITY For any language $A$, define a language $L_{A}$ as:

$L_{A} = \{0^{n}: \text{Number of strings in $A$ of length $n$ is more than $2^{n-1}$} \}$

I am trying to construct an $A$ such that $L_{A} \notin P^{A}$. It should intuitively be true, as a polynomial time machine cannot query an exponential number of strings and check whether a majority of them belongs to a language.

The proof boils down to a diagonalization argument. But I am unsure on how to construct the sets.

Let $T_1,T_2,\ldots$ be an enumeration of all timed polytime machines, machine $T_i$ running in time $p_i(n)$. We will construct $A$ in stages. At each stage, the truth value of $A$ is defined on only finitely many inputs.

Stage $i$ handles $T_i$. Choose an input length $n$ such that (i) $A$ is completely undefined and (ii) $p_i(n) < 2^{n-1}$. Run $T_i$ on $0^n$. Each time $T_i$ queries some yet undefined string in $A$, answer arbitrarily and fix the value of this string in $A$. Since $p_i(n) < 2^{n-1}$, in particular $T_i$ queries fewer than $2^{n-1}$ strings of length $n$. If $T_i$ answered "Yes", then define all remaining strings of length $n$ to be outside $A$. If $T_i$ answered "No", then define all remaining strings of length $n$ to be inside $A$. Either way, the machine $T_i$ is wrong on input $0^n$.

After infinitely many steps, we have defined $A$ at infinitely many strings, but probably not all strings. Define $A$ arbitrarily on all remaining strings.

We note that the same proof works for every (time constructible) complexity class in which a machine cannot make at least $2^{n-1}$ queries on input of length $n$.


Where does the terminology of open addressing resp. closed hashing come from? One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books).

Why the names "open" and "closed", and why these seemingly contradictory names for the same method?

The short answer is that the terms were coined by different people for different purposes, and it's because hash tables historically had two different contexts: in-memory data structures (I believe that compiler symbol tables was one of the first "killer app" uses) and external-memory data structures (file-based databases).

According to Knuth, the first mention of hashing in the literature is from an internal IBM memo from 1953, and it describes hashing with separate chaining. I don't have a copy of the memo, so I don't know what it was used for. I also don't know (possibly nobody does) who coined the term "closed hashing", but it makes sense to me that with "closed hashing" everything is stored in the table itself, with no need for secondary data structures to do collision resolution. In that sense, the hash table is "closed". From the context, it seems that this was an in-memory use.

We do know who coined the term "open addressing scheme". It's from W.W. Peterson's 1957 paper Addressing for Random-Access Storage (IBM Journal of Research and Development 1.2), though the idea goes back a bit further. The context here is clearly searching in files. The addressing scheme that Peterson analysed was "open", as opposed to "structured" (e.g. sorting the data and using binary search).


What is wrong with the following $P$ problem? Our teacher gave us the following statement and we were wondering what is wrong with it.

  Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$,
  we cannot check for each permutation whether it is sorted, in a total time which is polynomial in $n$.
  Therefore, sorting $A$ cannot be in $P$.

Obviously this is wrong.
My friend thought it should just be: therefore sorting $A$ cannot be in $NP$.
Is this correct or are we thinking about it to easily?

Very simple: We can sort an array without checking every possible permutation. (Many times we don’t check any permutation of the array, we just re-arrange the order of items so we can guarantee the array is sorted, without ever checking it. )


Context-free grammar of the concatenation of a string S and subsequence of reversed S I have to find a Context-Free grammar that generates the language:

$L_1 = \{x\#y\ |\ y$ is a subsequence of $x^R$, and $x\in\{a,b\}^*\}$, $\Sigma=\{a,b,\#\}$

The concatenation of two mutually reversed strings are pretty simple, but I just can't figure out how to express "plugging in random terminals in $x$" so that $x^R$ could contain $y$ as its subsequence.

Let me start with a grammar for the language of words of the form $x\#x^R$:
$$
S \to aSa \mid bSb \mid \#
$$
This is our starting point. Now there are two interpretations of the term subsequence. Under the first interpretation, a subsequence is obtained by removing any number of symbols. This just means that we can omit the second side of each production of the form $S \to \sigma S \sigma$, resulting in the grammar
$$
S \to aSa \mid bSb \mid aS \mid bS \mid \#
$$
Under the second interpretation, the subsequence must be contiguous. Each derivation should therefore be in three steps: first only on the left side, then on both sides, then finally again only on the left side. This requires three nonterminals, and results in the following grammar:
$$
S \to aS \mid bS \mid T \\
T \to aTa \mid bTb \mid U \\
U \to aU \mid bU \mid \#
$$


Vector clocks: Why is it necessary to increment my clock on receiving a message? Assume I have a distributed system of entities, each with a replica of the same data object that can be modified by broadcasting the changes and I'm using vector clocks to know how to order changes.

In this scenario, Why would I need to increment my own clock if I receive an update? (I noticed in the original paper on vector clocks, they didn't mention this rule, yet followed it in the examples...) Would it be sufficient if I only incremented my clock when I change the data object?

Look at the definition of $<_H$.

We say that $e_1<_H e_2$ (event 1 happened before event 2) if:

$e_1,e_2$ took place in the same process, and $e_1$ happened first (events within the same process are ordered).
$e_1,e_2$ are the sending and receiving of some message $m$, correspondingly.

Finally, we take the transitive closure of the above, and this yield Lamport's happened before relation.

Our objective is to assign time stamps to events, $T_{e_i}$ with a partial order $<_t$, such that $e_1<_H e_2 \iff T_{e_1}<_t T_{e_2}$.

The timestamps suggested here are vectors in $\mathbb{N}^n$, with the ordering $T_{e_p}<_t T_{e_q} \iff T_{e_p}[p]<T_{e_q}[p]$ where $e_p,e_q$ are events in processes $p,q$ correspondingly (assume each time stamp contains the process id).

Back to your question, not updating your clock upon receiving a message would cause your new relation $<_t$ to disagree with $<_H$ in events within the same process. For example, you would have $c\not\rightarrow d$ (figure 3). In addition, this is mentioned in the paper (rule 2, increase the local clock at each atomic event, which is either sending or receiving a message).


Is queue a storage allocation area in memory? We mainly study about heap and stack data structures which act as storage allocation area in memory. Is it that queue is also a storage allocation area in memory? As far as I know, process control blocks are made in OS region and actually they also act as storage allocation area only so can I consider queue to be a storage allocation area in memory?

You've been misled by homonyms.

There is a data structure called stack: a container where items can be added at any time but only the most recently added can be removed. And there is an area in memory called stack, which is where function arguments, local variables, return values and return addresses are stored¹. There's one stack memory area per thread. The two concepts have the same name because the stack memory area is organized as a stack data structure: an item is added when a function call is executed, and it is removed upon return from a function; since function calls are nested, the item that's removed is the last one that was added and not yet removed.

There is a data structure called heap: a tree of ordered items where each node holds a smaller value than all of its children². And there is an area in memory called heap, which is where storage is allocated dynamically. There is one heap per process. The two concepts are completely unrelated, they have the same name because there's a finite supply of English words with roughly the right connotations and it happens that the same word was picked for both.

There is no reason why a word that is a name for a data structure should also be a name for an area in memory. There can be queue data structures in an operating system, of course, but there's no area in memory that's called “the queue”.

Process control blocks are not organized as a queue, and they are not a storage allocation area, they're just a common name for the place in memory where the operating system stores information about each process (and not every operating system has all the information in one place, so not every OS's description mentions a “process control block”).

¹  This is just the 10000-foot view. Return addresses and arguments could be placed in different areas, some arguments typically end up in registers, etc.
²  That's a min-heap; a max-heap is a tree where each node holds a larger value than all of its children.


What makes a pseudorandom generator, a high quality one? Reading this answer to this SO question: Why do we not combine random number generators?, it talks about

  very high-quality PRNG (Pseudo Random Number Generator)

so it makes me wonder what constitutes a high-quality PRNG, I assume you can sum it up as it being "more random", but

Question1: Which qualities of a PRNG are used to describe how 'random' or 'good' it is?
Question2: If you have a 'bad quality' PRNG, is there a way to make it better quality?

There are several criteria for the quality of a PRNG:

How fast it is. This includes how fast it is to setup it, and how fast it is to produce a single bit (amortized).
How difficult it is to guess the next bit given all previous bits.
How difficult it is to distinguish between output of the PRNG and truly random bits.

The last two criteria are strongly related.

If you have a bad quality PRNG, you can often make it better by hardness amplification. Take several copies of the PRNG (using different random keys) and XOR them together. In many (though not all) cases this will significantly improve its quality.


$L=\{a^ib^i|i\geq0\}$, cfg for $L^2$ $L=\{a^ib^i|i\geq0\}$, cfg for $L^2$

can you write cfg for $L^2$ where $L=\{a^ib^i|i\geq0\}$?

the professor's answer sheet says it's $S\to AA\\ A\to aAb|\lambda$

but I think it is wrong because two $L$ have to be identical with each other.

can you help me figure out if there is cfg describing $L^2$?

The square language $L^2$ is defined as follows:
$$
L^2 = LL = \{ xy : x,y \in L \}.
$$
There is no requirement that $x = y$. Indeed, in your case $L^2 \supsetneq \{ w^2 : w \in L \}$.


Algorithm to detect if word belongs to pushdown automaton I am creating a simple program to detect if the given pushdown automaton accepts the given word, and I have a problem in finding an algorithm that does that.

My thought at first would be to go through all possible transitions, and check if we didn't match this word in accepting state, but got in problem with (epsilon, epsilon)/V where we can put V into stack without reading anything and getting from stack.

Is there any good algorithm which could work, or is this task impossible?

As adrianN notes in their comment, your task is certainly algorithmically possible. There are algorithms that take a PDA $A$ and outputs a context-free grammar $G$ such that $L(A) = L(G)$, and others (such as CYK) that take a context-free grammar $G$ and a word $x$ and determine whether $x \in L(G)$.

There might be shortcuts, but at least this shows that your problem is decidable. In fact, since both algorithms run in polynomial time, the problem belongs to $\mathsf{P}$.

Judging from the literature, it seems that this chain of reductions is the standard way of solving the membership problem for pushdown automata. See for example these notes from Hendrik Jan Hoogeboom and Joost Engelfriet.


Satisfiability where each clause contains almost all variables Suppose that we have a CNF SAT instance where each clause contains all variables (i.e. in each clause for each variable either the variable or its negation is presented). Such problem can be trivially solved, since any such instance either contains all possible clauses or is satisfiable.

Question: is there some a similar (i.e. with bounded number of variables that are not presented in each clause) NP-complete problem?

Suppose every clause contains all but c variables. I think the problem is in $P$, which I believe can be seem from your example with $c=0$. In your case, every clause "forbids" exactly one satisfying assignment. Suppose we have $n$ variables, then the formula is satifiable when there is at least one satisfying assignment that remains, and thus, when not all $2^n$ possible assignments are forbidden.

I believe we can generalize this idea: keep a list of all such "forbidden" assignments: for each clause, add the $2^c$  assignments it forbids to the list (the opposite of the clause, with all possible extensions to the missing variables).  If in the end, the list contains all $2^n$ assignments, the formula is unsatisfiable. Else, it is satisfiable

Note that this is polynomial time, if there are $m$ clauses, the list contains at most $2^c \cdot m$ forbidden assignments.


How to prove $0\neq1$ using the J rule? Suppose I have a simple dependent type theory with bottom, unit, sums, dependent pairs, dependent functions, natural numbers and homogeneous identity with J-elimination.

Is there a way to prove $(0 = 1) \rightarrow \bot$? Or do I need K for that?

First define a type family $P : \mathtt{Nat} \to \mathtt{Type}$ such that
$P\,0 \equiv \top$
and
$P\,1 \equiv \bot.$
For instance, we could define it by induction as
\begin{align}
P\, 0 &\equiv \bot \\
P\, (\mathtt{succ}(n)) &\equiv \top.
\end{align}
Let $\mathtt{tt}$ be the inhabitant of $\top$.

Suppose $e : 0 = 1$. Then, using $J$ we can formulate the transport map $\mathtt{transport}^P_e : P\,0 \to P\,1$, and use that to transport $\mathtt{tt} : P \, 0$ to
$$\mathtt{transport}^P_e(\mathtt{tt}) : P \, 1.$$
We are done because $P\,1 \equiv \bot$.


Language that system calls are implemented in Lately, I have been reading about operating systems design.  The idea that all user space programs utilize Kernel services via a "System Call Interface" have got me thinking further into this.

Is system call implemented in specific language like C/C++ on each operating system or it is some sort of assembly language or machine code?

System calls are usually implemented in C (or at least that used to be the case) mixed with assembly language. That said, everything gets translated eventually to machine code.


Is the inverse of MST cycle property always true? Why? I am trying to find an algorithm which would check for each edge in a given weighted undirected graph whether it belongs to any of the graph's Minimum Spanning Trees.

I have found many potential solutions to this problem, which use the cycle property of MSTs, that is (quoting Wikipedia):
For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to a MST.

It is obvious to me how this property can be used to determine which edges can definitely not belong to any of the graph's MTSs, but I have doubts if the inverse of the cycle property is also true, that is if: For every cycle C in the graph, if the weight of an edge e of C is less or equal to the individual weight of any other edge of C, then this edge belongs to at least one MST.

In other words, is edge e not being the heaviest edge in every cycle containing e only a necessary condition, or a sufficient condition to e belonging to an MST?

If the above is false, then all I would want to see is a counterexample. If however this is true, could anybody prove why it is so?

If you want to test whether a specific edge belongs to some MST, you can use the following property.

Claim. An edge $e$ belongs some MST if and only if for every $\epsilon > 0$, if we reduce the weight of $e$ by $\epsilon$ then it belongs to all MSTs.

Proof. We first show that if $e$ belongs to some MST then for every $\epsilon > 0$, if we reduce the weight of $e$ by $\epsilon$ then it belongs to all MSTs.

Suppose that MSTs in the original graph have weight $w$. When we decrease the weight of $e$ by $\epsilon$, only trees containing $e$ have decreased weight. Since $e$ belongs to some MST, the new graph has MSTs of weight $w - \epsilon$, and all of them contain $e$.

We complete the proof by showing that if $e$ doesn't belong to any MST then for small enough $\epsilon > 0$, if we decrease the weight of $e$ by $\epsilon$ then $e$ still belongs to no MST. Indeed, suppose that MSTs in the original graph have weight $w$, and the lightest spanning tree containing $e$ has weight $w+\delta$ for $\delta > 0$. If we decrease the weight of $e$ by less than $\delta$, it still belongs to no MST. $\qquad \square$

I'll let you figure out how to use the claim to test whether $e$ belongs to some MST; it suffices to find one MST in one graph. The same approach seems wasteful if you want to test all edges. I'll leave you to ponder whether any optimization is possible in that case.


What is the computational power of Parsing Expression Grammars? Parsing Expression Grammars were introduced by Bryan Ford in Parsing Expression Grammars: A Recognition Based Syntactic Foundation.. Wikipedia says that it is an open problem to provide a Context Free language that can not be recognized by a PEG.

I am trying to understand the results from this paper -- The computational power of Parsing Expression Grammars by Loff et al. However, I am struggling to understand the notation used. What does the # mean in the following quote?

  We show that PEGs are computationally "universal". Take any
  computational function $f: \{0,1\}^{*} \rightarrow \{0,1\}^{*};$ then
  there exist a computable function $g:\{0,1\}^{*} \rightarrow N$ such
  that

  $\{ f(x)\#^{g(x)}x | x \in \{0,1\}^{*}  \}$

  has a PEG.

They use a slightly different symbol in Theorem 18.

  $ L = \{ f(x){⧖}^{g(x)}x | x \in \{0,1\}^{*}  \} \in PEG $

Where they talk about the $⧖$ as the number of symbols read (interpretation mine). How do I read this?

Further, can I take this to mean that the question whether a CFL exist that can not be recognized by a PEG is settled?

Essentially, if there exist a PEG for a P complete language, then all other problems in P can be reduced to it. Given that recognizing CFLs are in P, all CFLs should be reduced to recognizing this language.

Note that a similar question was asked by another user three years back, but this is new research.

$\#$ here is just a symbol; it has no special significance. (It's often used in the construction of an modified language to indicate a new symbol which is not in the alphabet of the original language.)

$\#^{g(x)}$ is, therefore, the unary encoding of $g(x)$; in that sense, it is a count.

The double-triangle used in the later proof is just another such symbol without special significance.

In response to your second question, the paper seems to be pretty clearly state (on page 4) that the question of whether there is a CFL with no PEG is still open. In particular, it is not known whether the language of even-length palindromes has a PEG, although it is certainly a CFL.


Do you get DFS if you change the queue to a stack in a BFS implementation? Here is the standard pseudocode for breadth first search:

{ seen(x) is false for all x at this point }
push(q, x0)
seen(x0) := true
while (!empty(q))
  x := pop(q)
  visit(x)
  for each y reachable from x by one edge
    if not seen(y)
      push(q, y)
      seen(y) := true

Here push and pop are assumed to be queue operations. But what if they are stack operations? Does the resulting algorithm visit vertices in depth-first order?

If you voted for the comment "this is trivial", I'd ask you to explain why it is trivial. I find the problem quite tricky.

No, this is not the same as a DFS.

Consider the graph

If you push the nodes in right to left order, the algorithm gives you a traversal:

$A, B , E, C , D$

while a DFS would expect it to be

$A,B,E,D,C$

The problem occurs because you mark it as seen at the time of pushing, rather than at the time of visiting. As pointed out in the comments, if you mark at the time of visiting, your space requirements might go up to $\Theta(V+E)$ rather than $\mathcal{O}(V)$.

I agree, the problem is not trivial.


Intro to Martin-Löf type theory What would be the best introduction to Per Martin-Löfs ideas about type theory? I've looked at some lectures from the Oregon PL summer school, but I'm still sort of puzzled by the following question:

What is a type?

I know what a set is, since you can define them by the usual ZF axioms and they have a very intuitive concrete model; just think of a basket filled with stuff. However, I've yet to see a reasonable definition of a type and I was wondering if there is some source that would distill this idea for dummy.

A type is a property of computations. It's what you write on the right-hand side of a colon.

Let me elaborate on that. Note that the terminology isn't completely standard: some articles or books may use different words for certain concepts.

A term is an element of an abstract syntax that is intended to represent computation. Intuitively, it's a parse tree. Formally, it's a finite tree where the nodes belong to some alphabet. An untyped calculus defines a syntax for terms. For example, the (untyped) lambda calculus contains terms (written $M$, $N$, etc.) built from three types of nodes:

variables, of arity 0 (a denumerable collection thereof), written $x$, $y$, etc.;
application of a variable, of arity 1 (a denumerable collection thereof, with a bijection to variables), written $\lambda x. M$, etc.;
application, of arity 2, written $M \, N$.

A term is a syntactic construction. A semantics relates terms to computations. There are many types of semantics, the most common being operational (describing how terms can be transformed into other terms) or denotational (describing terms by a transformation into another space, usually built from set theory).

A type is a property of terms. A type system for an untyped calculus describes which terms have which types. Mathematically, at the core, a type system is a relation between terms and types. More accurately, a type system is a family of such relations, indexed by contexts — typically, a context provides at least types for variables (i.e. a context is a partial function from variables to types), such that a term may only have a type in contexts that provide a type for all its free variables. What kind of mathematical object a type is depends on the type system.

Some type systems are described with types as sets, using notions of set theory such as intersection, union and comprehension. This has the advantage of resting upon familiar mathematical foundations. A limitation of this approach is that it doesn't allow reasoning about equivalent types.

Many type systems describe types themselves as terms in a calculus of types. Depending on the type system, these may be the same terms or different terms. I'll use the phrase base term to refer to a term of the calculus that describes computation. For example, the simply typed lambda calculus uses the following calculus of types (written $\tau$, etc.):

base types, of arity 0 (a finite or denumerable collection thereof), written $A$, $B$, etc.;
function, of arity 2, written $\tau_0 \rightarrow \tau_1$.

The relation between terms and types that defines the simply typed lambda calculus is usually defined by typing rules. Typing rules are not the only way to define a type system, but they are common. They work well for compositional type systems, i.e. type systems where the type(s) of a term is built from the types of subterms. Typing rules define a type system inductively: each typing rule is an axiom that states that for any instantiation of the formulas above the horizontal rule, the formula below the rule is also true. See How to read typing rules? for more details. Does there exist a Turing complete typed lambda calculus? may also be of interest.

For the simply typed lambda calculus, the typing judgement $\Gamma \vdash M : \tau$ means that $M$ has the type $\tau$ in the context $\Gamma$. I've omitted the formal definition of contexts.
$$
\dfrac{x:\tau \in \Gamma}{\Gamma \vdash x : \tau}(\Gamma)
\qquad
\dfrac{\Gamma, x:\tau_0 \vdash M : \tau_1}{\Gamma \vdash \lambda x.M : \tau_0 \rightarrow \tau_1}(\mathord{\rightarrow}I)
\qquad
\dfrac{\Gamma \vdash M : \tau_0 \rightarrow \tau_1 \quad \Gamma \vdash N : \tau_0}{\Gamma \vdash M\,N : \tau_1}(\mathord{\rightarrow}E)
$$

For example, if $A$ and $B$ are based types, then $\lambda x. \lambda y. x\,y$ has the type $(A \rightarrow B) \rightarrow A \rightarrow B$ in any context (from bottom to top, apply $(\mathord{\rightarrow}I)$ twice, then $(\mathord{\rightarrow}E)$, and finally $(\Gamma)$ on each branch).

It is possible to interpret the types of the simply typed lambda calculus as sets. This amounts to giving a denotational semantics for the types. A good denotational semantics for the base terms would assign to each base term a member of the denotation of all of its types.

Intuitionistic type theory (also known as Martin-Löf type theory) is more complex that simply typed lambda calculus, as it has many more elements in the calculus of types (and also adds a few constants to the base terms). But the core principles are the same. An important feature of Martin-Löf type theory is that types can contain base terms (they are dependent types): the universe of base terms and the universe of types are the same, though they can be distinguished by simple syntactic rules (usually known as sorting, i.e. assigning sorts to terms, in rewriting theory).

There are type systems that go further and completely mix types and base terms, so that there is no distinction between the two. Such type systems are said to be higher-order. In such calculi, types have types — a type can appear on the left-hand side of the $:$. The calculus of construction is the paradigm of higher-order dependent types. The lambda cube (also known as Barendregt cube) classifies type systems in terms of whether they allow terms to depend on types (polymorphism — some base terms contain types as subterms), types to depend on terms (dependent types), or types to depend on types (type operators — the calculus of types has a notion of computation).

Most type systems have been given set-theoretical semantics, to tie them with the usual foundations of mathematics.
How are programming languages and foundations of mathematics related? and
What is the difference between the semantic and syntactic views of function types? may be of interest here. There has also been work on using type theory as a foundation of mathematics — set theory is the historic foundation, but it is not the only possible choice. Homotopy type theory is an important milestone in this direction: it describes the semantics of intentional intuitionistic type theory in terms of homotopy theory and constructs set theory in this framework.

I recommend Benjamin Pierce's books Types and Programming Languages and Advances Topics in Types and Programming Languages. They are accessible to any undergraduate with no prerequisite other than basic familiarity with formal mathematical reasoning. TAPL describes many type systems; dependent types are the subject of chapter 2 of ATTAPL.


Determine saving moves for a checked king In my chess code I explore the whole tree of possible movements to find saving moves for a checked king. That is, for every one of the checked king's side pieces I search their whole tree of moves and keep those that remove the king from check in a list.
Not like it's particularly expensive computationally-wise with a board of 8x8, but just for the sake of knowledge - is there a more efficient algorithm to calculate the saving moves?

Well, you could try to directly use the geometry the attacking piece and possible defenders to see if an intersection is available. This would be faster.
But there is a lot of cases to be taken into consideration : multiple checks, pinned defenders, half-pinned defenders, en passant rules... It's much easier to code that wrong, so be careful, and prepare lots of test cases to compare to the "simple" version, to check that you're not mixing things up.
Computing "long" lists of legal moves isn't hard for a computer, there's less than 200 anyway. What's hard in chess computer programs is the exponential search tree  and deciding when to stop recursing and evaluate.


Is program analysis part of programming language theory? If I am correct, programming language theory studies

syntax and semantics of programming languages, and
design and implementation of programming languages (e.g. compiler, ...)

Does programming in programming languages, i.e. creating programs in
programming languages, belong to programming language theory?
Does program analysis (correctness and performance of programs)
belong to programming language theory? My thought is:

semantics of a programming language is used for verifying correctness of programs in the language, so it seems like the answer
is yes, although I am not sure if analysis of programs' performance
belongs to programming language theory.
program analysis also seems to belong to software engineering, which makes me feel perhaps it doesn't belong to programming
language theory.

Thanks.

"Programming language theory" more or less includes everything you have listed, but of course there is overlap with other areas, such as software engineering, algorithms, security, human-computer interaction, and good old mathematics.

For instance, if you look at last year's programme of the Principles of Programming Languages (POPL) conference you will see not only topics about design, implementation and semantics of programming languages, but also about security, program analysis, papers about resource complexity, and many others.

In general I would say it good to be open about what "belongs" to a "research area". It is a shame to miss opportunities for new discoveries because of narrow-mindedness.


Contradiction between best-case running time of insertion sort and $n\log n$ lower bound? If the best case for Insertion sort & bubble sort is $O(n)$ then how is lower bound for any comparison sort is $\Omega(n\log n)$? I mean, $O(n)$ is obviously smaller than $\Omega(nlogn)$. What am I missing here?

The lower bound of $\Omega(n \log(n))$ is a lower bound for the worst-case behavior of a sorting method. Both insertion sort and bubble sort have $O(n^2)$ worst-case complexity.


When represented as a function, why is the input of a decision problem a natural number? Our professor explained that all programs can be thought of as the set of natural numbers, while decision problems can be thought of as the set or rational numbers.

Our notes say a decision problem can be represented as a function which takes a natural number as input and maps it to either 0 or 1.
That the range is 0 or 1 is obvious but why is the input a natural number?
What does it represent? I understand that a program can be represented by a natural number but a program isn't the input for a decision problem, is it? What is the input of a decision problem and why is it represented by a natural number?

It's probably easier to understand if you think of a program as a bit-string, i.e., an element of $\{0,1\}^*$; and think of a decision problem as a function that maps a bit-string to either 0 or 1, i.e., a function $\{0,1\}^* \to \{0,1\}$.  The input to the decision problem is a bit-string.

Why is this reasonable?  Any program can be expressed as a sequence of bits (e.g., convert each character to bits, and concatenate them).  The input to the program can be expressed as a sequence of bits.  So everything is bits.

Hopefully that approach makes sense.

Now, why does your professor/textbook talk about natural numbers instead of bit-strings?  That's just a convention.  It turns out that every bit-string can be encoded as a natural number, and vice versa.  Given a bit-string, you can think of it as the binary representation of a number; and given a number, you can turn it into a bit-string by expressing it in binary.  So bit-strings and natural numbers are in some sense interchangeable or equivalent.


Could anyone prove that this is a context free language or not? Possible Duplicate:
  Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free

Can anyone prove that the following is a CFL? or not? why?

$$L=\{w=w_1w_2 \mid len(w_1)=len(w_2) \mbox{ and $w_1$ does not equal $w_2$}\}$$

This must be a classic in formal language theory. The Pumping Lemma will not help, because, unexpectedly, it is context-free. (I did not see the answer here, but it might be overlooked)

The $w_1$ and $w_2$ parts must have a position where they differ. Unfortunately, we cannot distinguish the middle and the two matching positions at the same time. However, we can find matching positions without knowing the middle.

With some effort you can convince yourself that your language $L$ equals
$$\{ x_1 a x_2 b x_3 \mid a,b \in \Sigma, a\neq b, |x_1|+|x_3| = |x_2| \}.$$
Once you have shown that, write a grammar using that formulation.


Is there a difference between the Bulk Synchronous Parallel Computing model and the Turing Machine The Turing model of computing is widely accepted, as a Tape, Head, State register, and a finite state Table to manage transitions. The Bulk Synchronous Parallel Machine model has for its part similarity to the PRAM model, but with additional features in state management, by communication, and synchronization. So, in a sense it implies barrier synchronization, communication, and concurrent communication implicit in its workings, with processors having an order imposed on them. Does this conflict with the Turing machine model(?). Can one simulate one model by the other? Are they equivalent, or are there differences between these models?

I don't know the particulars of the bulk synchronous parallel machine, but it is highly likely that both have the same computational power, that is, both machines compute exactly the class of recursive languages. The difference between the models lies in their corresponding complexity measures: a language that has a certain (time or space) complexity in one model could have a different complexity in the other model.


Find a 3-colouring using the 3-colourability decision problem I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to enumerate the vertices of $G$ and delete any vertex that if your decision function tells you is not in the clique) But for 3-COLOR problem, I have no idea of how to link decision problem to search problem. Can anybody help me?

Let the vertices of the input graph $G$ be $\{v_1, \dots, v_n\}$.  First, check if $G$ is 3-colourable: if not, output "No 3-colourings" and quit.

Otherwise, add new vertices called $r$, $g$ and $b$ to $G$ and add the edges $rb$, $bg$ and $br$. Call this graph $G_0$.  Note that $G_0$ is 3-colourable and, in any 3-colouring of $G_0$, the three new vertices must receive different colours. Since the names of the colours are arbitrary, we will call the colour that $r$ gets, red; call $g$&'s colour, green; and call $b$'s colour blue.

We'll now create a sequence of graphs $G_1, \dots, G_n$, each of which will be 3-colourable, creating $G_i$ from $G_{i-1}$ as follows.

Set $G_i = G_{i-1} + \{rv_i, gv_i\}$ (i.e., the graph made by adding edges $rv_i$ and $gv_i$ to $G_{i-1}$) if this graph is is 3-colourable. Since $v_i$ is adjacent to both $r$, which is red, and $g$, which is green, $v_i$ must be blue.
Otherwise, set $G_i = G_{i-1} + \{gv_i, bv_i\}$, if this graph is 3-colourable. In this case, $v_i$ must be red.
Otherwise, set $G_i = G_{i-1} + \{bv_i, rv_i\}$.  Since $G_{i-1}$ was 3-colourable (you can prove this by induction), and we couldn't find a colouring with $v_i$ blue or red, $v_i$ must be green.

The above procedure produces a 3-colouring of the $n$-vertex graph $G$ with $2n+1$ calls to the oracle (procedure) for checking 3-colourability.


operator precendence grammar According to this post https://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel with operator. Actually i dont understand the rules which tells how to build such table.
For example take last production term   -> '(' expr ')' do we use rule terminal nonterminal because of ( expr or  do we use rule nonterminal terminal because of expr ) or do we use rule terminal nonterminal terminal shoudl we divide production or treat as whole? Then is there any other rule applicable in example from link then terminal nonterminal terminal ?

I think that answer is clear (although of course I would do, because I wrote it).

What it says is:

  if you find

$$nonterminal\; TERMINAL$$

  in any production, then you add the precedence relations $TRAIL \gtrdot TERMINAL$ for every $TRAIL$ in $Trailing(nonterminal)$. Similarly, every occurrence of

$$TERMINAL\; nonterminal$$

  generates the relationships $TERMINAL \lessdot LEAD$ for every $LEAD$ in $Leading(nonterminal)$.

So in $'(' expr ')'$, you have both an instance of $TERMINAL\; nonterminal$ and an instance of $nonterminal\; TERMINAL$, and you need to deal with both of them independently.


Determine whether a TM visits each of its states exactly once during computation (Decidable or not?) Formulate the following problem as a language:
  Given a Turing machine $M$ and a string $w$, determine whether $M$ visits each of its states exactly once during the computation with input string $w$. Prove your answer.

So the problem above is what I am trying to solve. I am looking for a general direction to solve this so far this is what I am thinking but I may be completely wrong.

My Thoughts: This problem is decidable because the Turing machine can have a list of all possible paths ,$E^*$, and we could check $E^*$ to ensure that each state was visited once and only visited once within the computation. However this doesn't seem like nearly enough and I am not sure what direction to head.

Hint: If a Turing machine has $m$ states and it visits each of them exactly once, then it terminates after $m$ steps.


Prove that a finite language is regular I want to prove that $L(G) = \{01; 11110; 10101; 000\}$ is regular.

Is it correct if I write there exists a regular expression, which is: $(01|11110|10101|000)$?

How can I also prove it using a DFA?

The regular expression is correct.

You can use a trie-like structure, i.e.


Complexity of a naive algorithm for finding the longest Fibonacci substring Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows:

$$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\
\text{a} &\mbox{if } k = 1 \\
F(k-1) \star F(k-2) &\mbox{else} \end{cases} $$

with $\star$ denoting string concatenation.

Thus we'll have:

$F(0) = \text{b}$
$F(1) = \text{a}$
$F(2) = F(1) \star F(0) = \text{ab}$
$F(3) = F(2) \star F(1) = \text{aba}$
$F(4) = F(3) \star F(2) = \text{abaab}$
...

Given a string $S$ formed by $n$ symbols, we define a Fibonacci substring as any substring of $S$ which is also a Fibonacci string for a suitable choice of $\text{a}$ and $\text{b}$.

The problem

Given $S$, we want to find its longest Fibonacci substring.

A trivial algorithm

For each position $i$ of the string $S$, suppose that $F(2)$ starts there (it's enough to check that the $i$-th and $(i+1)$-th symbols are distinct). If that's the case, check if it can be extended to $F(3)$, then $F(4)$, and so on. After that, start again from the position $i+1$. Repeat until you reach the position $n$.

We must look at each symbol at least once, so it's $\Omega(n)$. There are only two for loops involved, so we can furthermore say that it's $O(n^2)$.

However (somewhat unsurprisingly) this naive algorithm performs much better than usual quadratic algorithms (if it does a lot of work on the $i$-th position, it won't do a lot of work in the next positions).

How can I use Fibonacci properties to find tighter bounds for the execution time of this algorithm?

Say that $F(n)$ occurs at some position if the substring starting at that position is compatible with either $F(n)$ or its complementation. How close can occurrences of $F(n)$ be? Take as an example $F(4) = abaab$. If $F(4)$ occurs at position $p$ then it cannot occur at position $p+1$ or $p+2$, but it can appear at position $p+3$. We let $\ell(n)$ be the smallest number such that two occurrences of $F(\ell)$ can occur at distance of $\ell$. You can prove by induction that for $n \geq 4$ we have $\ell(n) = |F(n-1)|$ (for example, $\ell(4) = 3$).

Given a string of length $N$, for each $n$ let $P(n)$ be the set of positions at which $F(n)$ occurs. We can upper bound the running time of your procedure roughly by $\sum_n |P(n)| |F(n)|$, where the sum runs over all $n$ such that $|F(n-1)| \leq N$ (say). Since occurrences of $F(n)$ are separated by at least $|F(n-1)|$, we see that the running time is bounded by order of
$$ \sum_n |F(n)| \left(\frac{N}{|F(n-1)|} + 1\right). $$
Since the lengths of the Fibonacci words increase exponentially, $\sum_n |F(n)| = O(N)$. The remaining term is $\sum_n O(N) = O(N\log N)$, since the sum contains $\log N$ many terms. We conclude that the running time is $O(N\log N)$.

Conversely, the running time on $F_n$ is $\Omega(|F_n|\log|F_n|)$, as can be proved by induction. We conclude that the worst case running time on strings of length $N$ is $\Theta(N\log N)$.


What does distinct mean in terms of an array? I've tried searching this up, but from my what I think it is. It means there are no duplicate elements (ie. all elements are unique elements)?

Yes you are right..
An array is distinct if it contains unique elements i.e. no duplicates