When are 2 decision/optimization problems equivalent?

Suppose $L_1$ and $L_2$ are two decision problems, and $\mathcal{A}$ is a class of algorithms (like $P$). Say that $L_1$ is $\mathcal{A}$-reducible to $L_2$ if there is an $f \in \mathcal{A}$ such that $x \in L_1$ iff $f(x) \in L_2$. Say that $L_1$ and $L_2$ are $\mathcal{A}$-equivalent if each is $\mathcal{A}$-reducible to the other. For example, all NP-complete problems are $P$-equivalent. If you want a finer notion, you can consider more restricted classes, such as log-space or even AC0. Such notions of reducibility actually come up in refinements of Schaefer's dichotomy theorem.

As for optimization problems, let's consider maximization problems. With each maximization problem $L$ (which is a function mapping instances to optimal values), you can associate the decision problem $L'$ consisting of pairs $(x,v)$ such that $L(x) \geq v$. Now you can define reducibility and equivalence as before.


Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$

Your summary of the proof of undecidability is not accurate.  Your specification of $\overline{A_{TM}}$ is not correct.

For a reasonable exposition of the proof, see https://liacs.leidenuniv.nl/~hoogeboomhj/second/codingcomputations.pdf particularly the beginning of Section 1 and Section 3.

The intuition is not easy to convey, as the proof is not entirely trivial.  But here is the core fact.  Let $v,w$ be two configurations of a Turing machine.  Write $n(v)$ to be the next configuration of the Turing machine after a single step of computation, if you start at configuration $v$.  Define the language

$$L = \{v \# w^R \mid n(v) \ne w\}.$$

Then the key fact is that $L$ is context-free.  This takes some proof; proving that is a key step in the proof.  However, that's the answer to your question: $L$ is context-free but not regular.  As a result, we can reduce the halting problem to $ALL_{CFG}$ but not to $ALL_{REX}$.

I have skipped many steps to give you an overview of the main idea.  You will need to read the full proof to fill in the details.  I suggest that you next read and understand the proof, with this perspective in mind, and then revisit what I've written here.  Hopefully that will help you understand why the proof holds for context-free languages but would fail for regular languages.


Backpropagation on a matrix of functions

The problem isn't well-defined as you've stated it.  Backpropagation involves updating the weights, i.e., finding weights that cause the neural network to behave well.  If you have no weights, then there's nothing to update.

For these reasons, the standard approach to building neural networks involves both weights and univariate functions.  In the standard perceptron architecture, there are weights $w_{ij}$ along each edge (from neuron $i$ to neuron $j$), and a univariate function $f_j$ applied to the output of each neuron (neuron $j$).  So standard artificial neural networks already incorporate the univariate function.  The univariate function $f_j$ is called an "activation function".

Standard backpropagation does work with arbitrary activation functions.  You don't need to modify or generalize it: it already deals with them.  In particular, backprop can be used with an arbitrary activation function, as long as you know its derivative.  So, I suggest you take another look at how standard backprop works.

Backprop is basically just (a) computation of the partial derivatives (the partial derivative of some objective function, with respect to the weights), computed using the chain rule, plus (b) gradient descent.  Introducing arbitrary univariate functions affects only part (a), and the chain rule from calculus tells you how to calculate the partial derivatives.


Since a customer must either be assigned all the requested hours or none at all, this problem is $NP$-complete. This can be seen by reduction from Exact Cover.

A polynomial algorithm is unlikely to exist. Starting with biggest job first might be a reasonable heuristic for many cases, but there are no performance guarantees.


The three cases of the Master Theorem that you refer to are proved in the Introduction to Algorithms by Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest and Clifford Stein (2nd Edition, 2001).

It is correctly observed that the recurrence in question falls between Case 2 and Case 3. That is $f(n) = n \log n$ grows faster than $n$ but slower than $n^{1+\varepsilon}$ for any $\varepsilon > 0$.

However the theorem can be generalized to cover this recurrence. Consider

Case 2A:
Consider $f(n) = \Theta (n^{\log_b a }\log_b^k n)$ for some $k\geq 0$.

This case reduces to Case 2 when $k = 0$. It is intuitively clear that along each branch of the recurrence tree $f(x)$ is being added $\Theta (\log_b n)$ times. A sketch of a more formal proof can be found below. The final result is that

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n)$$.

In the Introduction to algorithms this statement is left as an exercise.

Applying this statement to the recurrence in question we finally get

$$
    T(n) = \Theta(n \cdot \log^2 n).
$$

More details on the Master Theorem can be found in the excellent (imho) Wikipedia page.

As @sdcvvc points in the comments to prove that Case 3 does not apply here one can invoke L'Hospital's rule that says that

$$
   \lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)}
$$

for any functions $f(x)$ and $g(x)$ differentiable in the vicinity of $c$. Applying this to $f(n) = n \log n$ and $g(n) = n^{1+\varepsilon}$ one can show that $\log n \not\in \Theta (n^{1+\varepsilon}).$

Sketch of the Proof of the Master Theorem for Case 2A.

This is a reproduction of parts of the proof from Introduction to Algorithms with the necessary modifications.

First we prove the following Lemma.

Lemma A:

Consider a function

$$
 g(n) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j)
$$

where $h(n) = n^{\log_b a} \log_b^k n.$ Then
$g(n) = n^{\log_b a} \log_b^{k +1} n.$

Proof:
Substituting the $h(n)$ into the expression for $g(n)$ one can get
$$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}}  \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$$

QED

If $n$ is an exact power of $b$ given a recurrence

$$
 T(n) = a T(n/b) + f(n),\quad  T(1) = \Theta(1)
$$

one can rewrite it as

$$
 T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j f(n/b^j).
$$

Substituting $f(n)$ with $\Theta(n^{\log_b a} \log_b^k n)$, moving $\Theta$ outside and applying Lemma A we get

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

Generalizing this to an arbitrary integer $n$ that is not a power of $b$ is beyond the scope of this post.


Good question! The proof given in Mohri's book indeed assumes continuity of the distribution, but this can be avoided with a finer definition of the $r_i$'s. Such a correction appears in these lecture notes who cite this paper.

Recall that you want the rectangles to be small enough, such that if $R_S$ intersects all of them, then $R\setminus R_s$ is small enough. Simultaneously, you want the rectangles to have large enough mass such that with high probability you do not miss a rectangle (here you use a simple bound on a geometric random variable as stated in the second point).

Suppose $R=[a,b]\times [c,d]$, and let us focus on $r_1$, the subrectangle having $[a,b]$ as an edge (if we are able to satisfy the above constraints for $r_1$, you can apply a similar construction for the rest of the rectangles). Define $r_1=[a,b]\times[c,c+h]$, where:

$h=\inf\big\{h'\big|\Pr\left[[a,b]\times[c,c+h']\right]\ge \frac{\epsilon}{4}\big\}$.

Note that $\Pr[r_1]\ge\frac{\epsilon}{4}$. To see why, let us assume that $\Pr[R]\ge\epsilon$ (otherwise we are done) and let $[a,b]\times[c,c+h']$ be some rectangle with mass $\ge \epsilon/4$. Now define the sequence of events
$x_i=[a,b]\times[c,c+h+2^{-i}\Delta]$, where $\Delta=h'-h$, and identify the rectangle $x_i$ with the event that a point drawn from our distribution lies inside the rectangle. Now we have:

$\Pr\left[r_1\right]=\Pr\left[\bigcap\limits_{n=1}^\infty x_n\right]=\Pr\left[\lim\limits_{n\rightarrow\infty}x_n\right]=\lim\limits_{n\rightarrow\infty}\Pr[x_n]\ge \frac{\epsilon}{4}$.

To see why the last inequality holds note that the series converges, since it is decreasing and lower bounded by $\frac{\epsilon}{4}$ (by our choice of $h$). See this question for a discussion on the probability of limit events. This shows that you are covered on the second point, and can upper bound the probability that at least one of the rectangles is missed.

It remains to show what we should do in the case that $r_i\cap R_s\neq\emptyset$ for all $i$. We can no longer immediately claim that $\Pr\left[\bigcup\limits_{i}r_i\right]\le\epsilon$, but a more sensitive approach would do the trick. Let us define $r_i'$ to be the interior of the rectangle $r_i$ along with its corresponding edge from $R$. Note that if $R_S\cap r_i\neq\emptyset$ then $R\setminus R_S\subseteq\bigcup\limits_{i}r_i'$ (geometric argument). We can now conclude the proof by showing that $\Pr[r_i']\le\epsilon/4$. You can prove this by a similar approach, define a sequence of events converging to $r_1'$, and use the fact the the probability for each event in the sequence is upper bounded by $\epsilon/4$.


Prove that AVL tree has this kind of property with Fibonacci sequence

Let $T$ be an AVL tree of $n > 0$ nodes having height $h \ge 0$. You can prove that $n > F(h)$ by induction on $h$.

For $h=0$ the claim is true since $n=1$ and $1 > 0 = F(0) = F(h)$.
For $h=1$ the claim is true since $n \ge 2$ and $2 > 1 = F(1) = F(h)$.

For $h \ge 2$, let $r$ be the root of the AVL tree. The subtree $T_\ell$ rooted in the left child of $r$ and the subtree $T_r$ rooted in the right child of $r$ exist are both AVL trees. Moreover, since $T$ is balanced, at least one tree $T'$ among $T_\ell$ and $T_r$ must have height $h-1$, while the other tree $T''$ must have height at least $h-2$.

By inductive hypothesis the number $n'$ of nodes of $T'$ is more than $F(h-1)$, while the number of nodes of $T''$ is more than $F(h-2)$.
Therefore, the number of nodes $n$ is:
$$
n = 1 + n' + n'' \ge 3 + F(h-1) + F(h-2) = 3 + F(h) > F(h).
$$


Set theory pertaining to category theory and functional programming

The notation $f:E\times F \to G$ means that $f$ is a function that needs two arguments, one from $E$, one from $F$, and the image is in $G$.
This is how the function $\text{Union}$ is defined: the two arguments $A$, $B$ are in $\mathcal{P}(X)$ and the image $\text{Union}(A, B) = A\cup B$ is in $\mathcal{P}(X)$.


Optimization of Hierarchical Data Propagation

I am guessing that you used a technique known as "Adjacency list" to store your tree in the database. However, other solutions are also available, including "Path enumeration", "Nested sets" and "Closure table". The latter one, closure table, is the best one and you may want to design again your database using this technique for storing your hierarchical data.

For more information, see these slides, in particular the section on naive trees which starts at the slide #48. Or, this book from the same author. Finally, a more formal treatment of this subject is also included in this book.


Minimum cost problem of breaking containers in $O(n\log n)$

To solve this problem in $O(nlogn)$, We can use a min-heap.
Consider $s_i = \Sigma_{k=i}^{n}{a_k}$ and $b_i = s_i + c_i - a_i$. You can see that if $b_i - s_j < 0$ for $j < i$, by starting from $j$ and breaking every container from $j$ to $i$, container $i$ will break by the amount of water from the containers $j$ to $i$.
First set $cost = 0$ and $min = p_i$. Then do the following from $n$ to $1$:

Calculate $s_i$.
Calculate $b_i$.
Add $p_i$ to $cost$.
Add $b_i$ to the mean-heap and heapify it.
While $b_j - s_i < 0$ ($b_j$ is the root of the heap): Remove the root and subtract $p_j$ from $cost$.
If $cost < min$, update $min$.

At every container, we know that if we start from that container, we need to break some of them and the rest will break by the water. When we remove a container from the heap, we can be sure that if we start from that container, the removed container will break by itself, and the total cost will be to break the rest, so we can subtract the cost of breaking the removed container from the total cost.
Since the while loop is run once for each container, and the for loop runs n times, the total time will be $O(nlogn)$.


Finding a solution to a satisfiable formula

Absolutely, a hash function is a prime example of a function (which can be modelled by a very complex binary formula of its inputs) where it is easy to find the output given an input, but finding an input which matches an output is very hard.

But since we generated the original output we know that there must be a solution.

This construction requires the ability to forget information (the original input) however.


Can minimum or maximum height of the binary search tree be constrained by the position of some elements

The question you were asked talks about 4 levels, which is a height of 3, not a height of 4.

Answer 1 is incorrect because there is a tree of height 3 in which G is at the root (you provided an example already).

Answer 3 is incorrect because of the following tree:

         F
       /  \
      /    \
     /      \
    B        J
   / \      / \
  A   D    H   L
     / \  / \ / \
    C   E G I K M

Answer 4 is incorrect because of the following tree:

           G
         /  \
        /    \
       /      \
      D        K
     / \      / \
    B   F    I   M
   /\  /    / \ /
  A  C E    H J L

Answer 2 is, as you answered correctly, the only true one.

To see this: Assume T is a tree which satisfies the constraints, i.e.

           1
         /  \
       /      \
     /          \
    B            K
  /   \        /   \
  2   3       4     5
 / \ / \     / \   /  \
6  7 8 9   10  11  12 13

Where the numbers 1 to 13 represent unknowns from A,C,D,E,F,G,H,I,J,L,M and two empty symbols.

As you can see, both the left and the right subtree can contain at most 6 elements. Thus, the root has to be $1 \in \{F,G,H\}$.

If $1=F$, then the right sub-tree has to contain {G, H, I, J, K, L, M}. However, K is the root of the right sub-tree and therefore $\{4,10,11\} = \{G,H,I,J\}$, which is impossible. Using symmetrical arguments we can show that the root cannot be H either.

Therefore it must be $1 = G$. But then $\{3,8,9\} = \{C,D,E,F\}$ which is a contradiction as well.


Using the substitution method, we find out that
$$
\begin{align*}
T(n) &= n + 3T(n-1) \\ &=
n + 3(n-1) + 3^2T(n-2) \\ &=
n + 3(n-1) + 3^2(n-2) + 3^3T(n-3) \\ &= \cdots \\ &=
n + 3(n-1) + 3^2(n-2) + \cdots + 3^{n-1}(n-(n-1)) + 3^n T(0) \\ &=
\frac{3^{n+1}-2n-3}{4} + 3^nT(0) \\ &= \Theta(3^n).
\end{align*}
$$
Even without doing the full calculation it is not hard to check that $T(n) \geq 3^{n-1} + 3^n T(0)$, and so $T(n) = \Omega(3^n)$. A cheap way to obtain the corresponding upper bound is by considering $S(n) = T(n)/3^n$, which satisfies the recurrence relation $S(n) = S(n-1) + n/3^n$. Repeated substitution then gives
$$
\frac{T(n)}{3^n} =\sum_{m=1}^n \frac{m}{3^m} + T(0).
$$
Since the infinite series $\sum_{m=1}^\infty \frac{m}{3^m}$ converges, this implies that $\frac{T(n)}{3^n} = \Theta(1)$ and so $T(n) = \Theta(3^n)$.


Are there a lambda-mu expression equivalent to the yin yang puzzle?

You can get an important hint to solution by thinking how to make the yin-yang puzzle work in a typed language, see this question. OCaml computes the type of yin and yang to be ('a -> 'a) as 'a, which is a recursive type equal to its own function space. Such a type is precisely what it takes to implement the untyped $\lambda$-calculus in a typed language.

What does this have to do with your question? In the untyped $\lambda$-calculus (or typed calculus with general recursive types) we can define $\mu$ and other fixed-point combinators. So, since yin and yang cannot be given types, we must use the untyped $\lambda$-calculus, but then $\mu$ is not needed as a primitive. In fact, the CPS transform of the puzzle will be just pure $\lambda$-calculus.

You can compute the CPS transform in the privacy of your mind. Here is my version, written in Ocaml. To run it, you need to pass -rectypes to Ocaml:

let callcc f k = f k ;;
let yin c = callcc (fun x -> x x) (fun k -> print_char '@'; c k) ;;
let yang c = callcc (fun x -> x x) (fun k -> print_char '*'; c k) ;;
let _  = yin yang (fun x -> x) ;;

Clearly, the let statements are just a convenience. Without them, and with callcc expanded out, we get:

(fun c -> (fun x -> x x) (fun k -> print_char '@'; c k))
(fun c -> (fun x -> x x) (fun k -> print_char '*'; c k))
(fun x -> x)

We could remove the print_char statement and $\eta$-reduce:

Start with:

(fun c -> (fun x -> x x) (fun k -> c k))
(fun c -> (fun x -> x x) (fun k -> c k))
(fun x -> x)

Reduce fun k -> c k to c:

(fun c -> (fun x -> x x) c) (fun c -> (fun x -> x x) c) (fun x -> x)

Reduce fun c -> (fun x -> x x) c to fun x -> x x:

(fun x -> x x) (fun x -> x x) (fun x -> x)

So the essence of the yin-yang puzzle is just self-application of self-application. How appropriate! As a last step, we can put in the print_char statements again, to get a one-liner:

(fun x -> x (fun k -> print_char '@'; x k)) (fun x -> x (fun k -> print_char '*'; x k)) (fun x -> x)


Why N-Queens Problem is not used as experiment in CSP thesis?

n-queens problem can be solved quite efficiently with a very simple algorithm (finding all solutions takes ages, because the number grows exponentially).

Getting anywhere near that efficiency with a general method is impossible.


Chinese Postman Problem: finding best connections between odd-degree nodes

As remarked in the comments, Wikipedia gives a reduction from route inspection to minimum-weight matchings.  Vladimir Kolmogorov has published a fast implementation of the weighted version of Edmonds' blossom algorithm, in C++ [1].

[1] V. Kolmogorov, Blossom V: A new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, 1(1):43–67, 2009.


Language of Turing machines that never visit some given state

I will assume that you're using $E_{TM}$ to mean the language $HALT=\{\langle M\rangle|\text{$M$ does not halt}\}$ and $B=A=\{\langle M\rangle|\text{$M$ is $TM$ and there is a state $q$ in $M$ that $M$ never visits}\}$. Also, you should state what your mapping is because if it is just the identity (which it seems to be here) then this won't work. This is because we can have a turing machine that halts right away but also happens to have an extra state that it never reaches, so it is not the case that $B\subset E_{TM}$.

Instead, it may help to think about this more informally. If have the ability to tell whether or not a turing machine visits all of its states, how might we use this superpower to decide the halting problem? The simplest, most direct approach is to see if we can answer the question of whether $M$ visits a specific state $q\in Q$ using knowledge of $B$. Then we can reduce to the halting problem by simply asking if a given TM $M$ visits any of its accepting states.

To do this, let's see what "subsets" of $M$ are still in $B$. By this I mean that we will choose a subset $P\subset Q$ and then on any transition that goes from a state in $P$ to one in $Q\setminus P$ we will instead reroute it to a halting state. Let's call the new machine with the new accepting state along with $P$ as its states as $N_P$.

Now, we start off by looking asking if $N_P\in B$ for $P$ being the set containing just the starting state. If this TM is in $B$ then we know $M$ never visits any state other than its initial state. If it is not in $B$ then we continue by adding a new state to $P$ and asking if the new TM is in $B$, continuing until we get to a TM which is in $B$. The $P$ we end on will have to be the set of states the TM visits, and all other states are unvisited. Thus, we can tell whether a $M$ visits a certain state $Q$ by simply checking if $q$ is in the final version of $P$.


Can deterministic Turing machine beats/wins (if possible) the "Bombs and Levers" game in polynomial time?

Your problem is NP-hard. It is an easy proof In fact, it is NP-complete because we can reduce it to SAT in polynomial time

We reduce 3-SAT to your problem.

We have a lever for each variable and a bomb for each clause, the red cables are connected to clauses/bombs that have positive literals belonging to that variable/lever and the green cables are connected to clauses/bombs that have negative literals belonging to that variable/lever.

Each bomb has the number 3 written on it, meaning that the bomb will explode if it is decremented three times. Whenever we set a lever that is connected to the bomb in the direction that doesn´t deffuse the bomb we decrement the counter in the bomb. This is the same as setting a variable true if the literal in a clause is false or viceversa. If we do this three times that means that the clause has not being satisfied in the original 3-SAT problem and the bomb explodes.

If the instance is satisfiable, you can always choose the right positions for the levers so that no bomb explodes. If there is a variable assignment that satisfies the clauses that means that the bombs can be defused. A defused bomb cannot explode anymore so that we don´t have to worry about a defused bomb anymore.

So, can your problem be solved in polynomial time? We don´t know. People will have to give a solution to the P vs NP problem first, come back in a hundred years and maybe we will have an answer


Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists

Input size refers to memory size needed to represent the input. In this case, it means number of edges + number of vertices, and you could also add size of the weights (which is logarithmic in their values).
No. It is written that we do $\log T$ calls and $T \leq |E| K$ (and this value can be reached), so the number of calls is at most $\log (|E| K) = \log |E| + \log K$.
Yes. It is never used in the algorithm that weights must be integers.
A $NP$-complete problem is a $NP$-hard problem which also needs to be in $NP$. So when speaking about a $NP$-complete problem, it is not false to state that it is $NP$-hard. However, $NP$ is a set of decision problems, therefore, TSP-OPT being an optimization problem cannot be in $NP$. We can still speak about $NP$-hardness as it can be informally defined for a non-decision problem as "a problem more difficult than all problems in $NP$". When you say "I thought that Traveling Salesperson Problem was NP-Complete", it refers to the decision version, denoted TSP in your reference.


Does this LCS algo generate all the CS or only all the LCSs?

Wikipedia is being sloppy. The procedure returns all LCSs of $X[1..i]$ and $Y[1..j]$, which corresponds to $C[i,j]$. It should mention that in order to obtain all LCSs, we need to set $i=m$ and $j=n$.
If $X[i] = Y[j]$, then every LCS of $X[1..i]$ and $Y[1..j]$ is obtained by taking an LCS of $X[1..i-1]$ and $Y[1..j-1]$, and adding to it $X[i] = Y[j]$.
If $X[i] \neq Y[j]$, then every LCS of $X[1..i]$ and $Y[1..j]$ must be either an LCS of $X[1..i-1]$ and $Y[1..j]$, or an LCS of $X[1..i]$ and $Y[1..j-1]$ (or both). If $C[i-1,j] > C[i,j-1]$, then only the former are LCSs of $X[1..i]$ and $Y[1..j]$. If $C[i-1,j] < C[i,j-1]$, then only the latter are LCSs of $X[1..i]$ and $Y[1..j]$. If $C[i-1,j] = C[i,j-1]$, then both types are LCSs of $X[1..i]$ and $Y[1..j]$.
This recursive procedure could count the same sequence more than once — this happens for example for the arrays $ab$ and $ac$, where $a$ will be reached twice.


Is a non-deterministic turing machine that both accepts and rejects the same input valid?

A non-deterministic Turing machine accepts a word if an accepting computation exists. There can be many non-accepting computation paths. This is what makes recognizing the complement of the language more difficult than just inverting accepting an rejecting states as you would do with a deterministic machine.


Unable to understand an inequality in an application of the pumping lemma for context-free languages

The Pumping Lemma requires $|vxy| \le m$ so that the pumped parts are of bounded length. Thus $k_1+k_2\le m$. With this it is easy.

As $k_2 \neq 0$, we must have $k_1<m$. Also $m>0$ as the pumping constant must be positive (but in fact we can assume it to be as large as we want, of course).

Now $2m-1 \ge m > k_1$.

That's all.


Starting from this system:

$$ \begin{cases} T(1) = 1 \\
 T(n) = 2T(n-1) + n \end{cases} $$

To use repertoire method to solve the system, we'll generalize it as this:

$$ \begin{cases} T(1) = \alpha \\
 T(n) = 2T(n-1) + \beta n + \gamma \end{cases} \tag 0 $$

The result must look like this:

$$ T(n) = A(n) \alpha + B(n) \beta + C(n) \gamma $$

I. Let's try T(n) = 1
$$ \begin{cases} T(1) = 1 = \alpha \\
 T(n) = 1 = 2T(n-1) + \beta n + \gamma = 2 \cdot 1 + \beta n + \gamma \end{cases}$$
Thus:
$$ (\alpha, \beta, \gamma) = (1, 0, -1) $$
Which means that
$$ T(n) = A(n) - C(n) = 1  \tag 1 $$.

II. Now try T(n) = n
$$ \begin{cases} T(1) = 1 = \alpha \\
 T(n) = n = 2T(n-1) + \beta n + \gamma = 2n - 2 + \beta n + \gamma \end{cases}$$
Thus:
$$ (\alpha, \beta, \gamma) = (1, -1, 2) $$
Which means that
$$ T(n) = A(n) - B(n) + 2 C(n) = n  \tag 2 $$.

III. Also, for $ (\alpha, \beta, \gamma) = (1, 0, 0) $:
$$\begin{cases} T(1) = 1 \\
T(n) = 2T(n-1) = 2^n \end{cases}$$
Which means that
$$ T(n) = A(n) = 2^{n-1}  \tag 3$$.

From (1) and (3):
$$ 2^{n-1} - 1 = C(n) $$

Now from this equation and (2):
$$2^{n-1} - B(n) + 2 (2^{n-1} -1) = n$$
$$2^{n-1} - n + 2^n -2 = B(n) $$

Final result for $ (\alpha, \beta, \gamma) = (1, 1, 0) $:
$$ T(n) = A(n) + B(n) $$
$$ T(n) = 2^{n-1} + 2^{n-1} - n + 2^n -2 $$
$$ T(n) = 2^{n+1} - n - 2$$


Find long connected similar subsequences in two given sequences

Let's call this problem LCCS, which is different with LCS. One straightforward way is to use a brute force algorithm with time complexity $O(nm(n+m))$.

 1. Input: A[1..n], B[1..m]
 2. Output: Length of the longest common connected subsequence
 3. max = 0
 4. for i from 1 to n
 5.    for j from 1 to m
 6.        if (lowercase(A[i]) = lowercase(B[j]))
 7.           i' = i
 8.           j' = j
 9.           len = 1
 10.          while (i' <= n and j' <= m)
 11.             i'++
 12.             j'++
 13.             if (lowercase(A[i']) != lowercase(B[j'])) break;
 14.             else len++;
 15.          if (len > max) max = len
 16. return max


Does "not regular" imply "acceptor needs memory"?

Every language $L \subseteq X^{\ast}$ for $X$ a finite alphabet could be accepted by the following (in general infinite) "automaton" (in the usual notation as "alphabet, states, start state, transition relation and final states")
$$
 \mathcal A = (X, Q, L, \delta, F)
$$
with $Q := \{ L/w : w \in X^{\ast} \}$, $\delta(L/w, u) := L/(wu)$
and $F := \{ L/w : \varepsilon \in L/w \}$, where
$$
 L/w := \{ u \in X^{\ast} \mid wu \in L \}
$$
is the quotient of the language (i.e. we take away prefixes from words in $L$). The set of quotients could be regarded as the states, or the memory. Which is finite if $L$ is regular (and more this construction gives a minimal finite automaton), and is infinite if $L$ is not regular (for example consider $L = \{ a^n b^n \mid n \ge 1 \}$ over $X = \{a,b\}$).

So in short in this (somehow canonical) model even a regular language has some kind of memory (a state which signalizes some property of the string being processed), but the crucial property is that we can get along with finitely many (memory) states, whereas in the non-regular case in this model we always need an "unbounded" memory/states.


Distinct variables for different clauses

Edit: I found a better example. Consider these clauses:
\begin{align}
& \lnot P(x) \lor P(f(x)) \\
& P(x) \\
& \lnot P(f(f(x)))\\
\end{align}
Obviously, this set of clauses is contradictory. But without renaming variables, the only possible resolvent is $P(f(x))$ and no more resolvents are possible - all lead to substituting $f(x)$ for $x$, which is impossible.

Edit: Consider the meaning of clauses. Each clause is implicitly universally quantified. So the meaning of its variables isn't fixed to anything. Now let's say you have two clauses both containing $x$. If you perform resolution without renaming $x$ in one of them, then you add a meaning to $x$ which it doesn't have: you say that $x$ means the same thing in both clauses, which is not true.
If you don't have distinct variables in your clauses, resolution will give you too weak conclusions.

(The original answer.)
For example, let's have 4 clauses:

$A\lor B(x)$
$\lnot A\lor C(x)$
$\lnot B(c)$
$\lnot C(d)$

where $x, y$ are variables and $c, d$ constants. If we perform resolution on the first two without renaming $x$, we'll get $B(x)\lor C(x)$. We can proceed with $\lnot B(c)$ to get $C(c)$ but now we cannot resolve it with $\lnot C(d)$.

On the other hand, if we rename $x$ to $y$ in the second one to have disjoint set of variables, we'll get $B(x)\lor C(y)$ from the first resolution step and we can derive an empty clause using $\lnot B(c)$ and $\lnot B(d)$.


How to find maximum matching edges in undirected tree

It is correct and runs in linear time. You can run a DFS to find the height and the parent node  of each vertex and visit the vertices according to their heights in ascending order.

The correctness of such algortihms is usually proved using an exchange argument. Assume $M$ is the matching computed by your algortihm and $M_{\mathrm{OPT}}$ an arbitrary maximum matching. Show that you can turn $M_{\mathrm{OPT}}$ into $M$ by removing and adding edges to the matching where its size never gos smaller.


What algorithm is most suitable for large text compression?

The Linux kernel has a huge source code, with about 3.2 million lines of code. Source code is totally text, so this can give you an idea about the level of compression that is possible. The entire source code is distributed as a .tar.xz file. Its size is close to 110 megabytes. This offers great compression. Decompress it and see the difference in file size!


Sorting $n^2$ numbers which consist of numbers from 1 to $n$

Given your contraints, I think Counting sort or Radix sort will do the job.

https://en.wikipedia.org/wiki/Counting_sort

https://en.wikipedia.org/wiki/Radix_sort


What category of AI would a 2048 bot be considered?

I would initially say that you can classify 2048 as a MDP problem.

For this reason, I would consider looking at Reinforcement Learning (an area of Machine Learning).

Another option, however, more specific would be to look at the performance of Monte Carlo Tree Search.

There is a great discussion in StackOverflow about 2048 different approaches have been tried:
https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048


The language $L_1$ is the quintessential example of a non-regular language. Intuitively, finite automata cannot count, so they cannot ascertain that the number of $a$'s is the same as the number of $b$'s. Alternatively, an automaton must "remember" how many $a$'s it has seen, which is impossible since there are infinitely many possible number of $a$'s. This intuition can be formalized using Myhill–Nerode theory: if $q_n$ is the state that a DFA for $L_1$ is at after reading $a^n$, then $q_n \neq q_m$ for $n \neq m$, since $a^nb^n \in L_1$ while $a^mb^n \notin L_1$; so there must be infinitely many states.
The language $L_2$ corresponds to the regular expression $a^*b^*$, so is regular.
The language $L_3$ is a "generalization" of $L_1$ (this can be made precise: $L_1$ is a quotient of $L_3$, $L_1 = L_3/\{cd\}$). Once again, an automaton needs to count how many $a$'s there are, which is impossible.


What should I do with a bunch of 16-17 year olds to get them interested in computer science?

You can have them draw pictures using context-free grammar. context free art This also works for people who never programmed before and scales to experienced programmers. The basic language is easy enough to explain in maybe half an hour.
Learning something about geometry using Turtle graphics should be nice too. Logo was designed for children, so highschool students should have no problem. There are nice videos about children using Logo on youtube
If you can get your hands on some MindStorms robots, programming them is lots of fun.
There are a variety of programming games in which you program robots to fight each other, or assembly programs that try to overwrite each other in a virtual machine. Wikipedia on the topic, related stackoverflow question
You can also think about some kind of hardware project. Making a microcontroller blink a LED depending on the number of unread e-mails in your inbox for example.
Have them implement different maze generation algorithms, try to come up with criteria that make mazes "difficult for humans". If time permits extend the algorithms to include not only corridors but also rooms.
Buy a couple of Arduinos and LEDs. Let them program the blinkenlights.


Are every 2 DFAs with $n$ states for a language $L$ isomorphic to each other?

Let $M$ be a DFA for the language $L$ and let $M_1$ and $M_2$ be $M$ with two different collections of some number $m$ of unreachable states added. $M_1$ and $M_2$ both have the same number of states and both accept $L$, but they need not be isomorphic.

For a less trivial example, consider the following two DFAs:

Start state: 1
Accepting states: 2, 4
1 -a-> 2   1 -b-> 1
2 -a-> 3   2 -b-> 2
3 -a-> 4   3 -b-> 3
4 -a-> 1   4 -b-> 4

Start state: 1
Accepting states: 2, 4
1 -a-> 2   1 -b-> 3
2 -a-> 3   2 -b-> 4
3 -a-> 4   3 -b-> 1
4 -a-> 1   4 -b-> 2

These two 4-state DFAs are non-isomorphic, but both accept the same language, namely the language of all strings over the alphabet $\{a, b\}$ which have an odd number of $a$s.

Note that if two DFAs accepting the same language have the same number of nodes, and that number is minimal among DFAs accepting that language, then the two DFAs must be isomorphic. See DFA minimization.


How a program is copied to RAM from harddisk

The operating system (with help from the CPU) keeps a page table, which is a mapping of each virtual page for to the physical page it is mapped to.  The page table also includes a bit for whether a particular page is currently mapped.  For every load and store instruction the hardware walks the page table (or at least a cached portion of it.)  If the virtual page is currently mapped to a physical page, the hardware figures this out and returns the right data.

If the virtual page is currently unmapped then the operating system receives an interrupt.  At this point it looks into the memory map for the process.  This is a list of ranges of virtual memory, the permissions that should be applied to that range, and the file (if any) on disk that stores the data from that range when it is not in RAM.  Typically for the main executable there will be a text segment, data segment and sometimes a read-only data segment (for constants), as well as a bss (zero initialized data) segment, a stack, and the heap managed by malloc.  There may be (usually are) additional text and data segments for each shared object (shared library) that the program needs to load.

You can use mmap() to tell a Posix operating system to create a new region in the memory map, the permissions for that region, and which file to use to back that region.  On Linux, for an existing process you can get a listing of its currently mapped regions using the pmap command.


3SAT is reduced to the Hitting Set problem. Given a 3SAT $\phi$ having $m$ clauses and $n$ variables, define

$$S = \{ x_1, \dots x_n, \overline{x_1}, \dots , \overline{x_n}\}$$
$$S_i=\{y_1, y_2, y_3\}, \text{ if } y_1,y_2,y_3 \in S \text { and } (y_1 \lor y_2 \lor y_3) \text{ is a clause.} $$
$$S_x=\{x, \overline{x}\}, \text{ for all variable } x.$$
$$k=n$$

Assume $\phi$ is satisfiable, then there a is true-value assignment for $n$ variables. So, add $x$ to $S'$ if $x=true$, otherwise add $\overline{x}$ to $S'$.

Now, assume the HS problem has a solution $S'$. Then since for every variable $x$, $S' \cap S_x \neq \emptyset$, $S'$ has at least $n$ literals of the form $x$ or $\overline{x}$ for each variable $x$. Furthermore, no $x$ and $\overline{x}$ may belong to $S'$ at the same time since the size of $S'$ is at most $n$. Also, for each clause $C_i$, $S' \cap S_i \neq \emptyset$ and so for each clause we select $y_i\in S' \cap S_i$, and set $x=true$ if $y_i=x$ and $x=false$ if $y_i=\overline{x}$.


Is there a name for an "array with no holes"?

The data structure itself is unambiguously called a contiguous array. Depending on the context and language I would call it "initialized" or "having only non-null elements" or similar to describe the contents.


Dealing with test condition '=' for a while loop when determining a bound function/loop variant

$n-j+1$ should work as it satisfied the three properties of a bound function.

It is definitely an integer valued function as all variables and 1 are integers.
Since $j$ is increased by 1 in every iteration, the function decreases by 1 each time. For example let's say $n$ was 5 and $j$ was 4. Then for the first iteration it would be 5-4+1=2, then the second iteration would be 5-5+1=1, and then when $j$ is 6, 5-6+1=0, which is also the upper bound for the number of executions of the loop body left.
Finally, if the value of the function is at most 0 then the test has to fail, and that is true for this function since if
$n-j+1\le0$ then $n+1\le j$, which means that $n < j$, since both $n$ and $j$ are integers. Since $j>n$, that means the test must fail and that satisfies the final condition.

Thus $n-j+1$ is a bound function for this algorithm. The answer below is wrong: if $n$ was 5 and $j$ was 4 then $n-j-1$ would be 5-4-1=0 and so the function is at most 0, meaning that the test $j\le n$ must fail, but $4\le 5$ does not fail.

Furthermore, stating that $n-j-1\le0$ then $j\ge n-1$ implies $j>n$ is incorrect, as if $j\ge n -1$ how would $j$ be greater than $n$ for sure when it was just stated that $j$ could be greater than or equal to $n-1$? I am pointing out that the answer is wrong because I too had this same exact question and believed the answer provided before realizing it was incorrect, and so hopefully others would realize that too.


Bfs and Dfs both are good state space search algorithms. If search space is infinite then its good to use Bfs because dfs can be lost in infinite space and will not return any result.
Also, Bfs searches result in neighbors and then go neighbor by neighbor on other hand dfs searches for answer branch by branch. If you search key is near starting point then go for bfs


Encoding System that Assign Same Number of Bits for Each Character

The usual way to solve this problem is by adding leading zeroes. So i would still be represented by 1101001, while ! will be represented by 0100001.

This is similar to how you digital clock might use 06:40 for 6:40, or 12:05 for 12:5.


Is there a query language variant of Turing Completeness?

The most you could expect out of a query language would be Turing completeness. In other words, the most powerful you could make a (physically realizable) query language would be to allow operations equivalent to treating the entire database as a single string and running an arbitrary program with that string as input.
Any real-world database query language that includes WHILE loops in the query language (e.g. PL/SQL) is probably Turing-complete in this sense. With such a language, you can go all the way down to reading and writing single rows at a time as necessary to read arbitrary data out of the database and interpret a Turing machine with the data as input. Of course, this is horrifically inefficient, but that's beside the point!


Does every Partially Ordered relation and its dual have the same number of topological orderings?

Is it the case that both the poset and its dual poset have the same number of topological orderings?

Yes, you have observed/discovered a fact about partially ordered set (poset). In fact, there is a stronger and more pleasing fact, which is a special case of the duality of order theory.

The dual order of a topological ordering of a poset is a topological order of the dual order of that poset.

Given a poset $p$, let $p^{d}$ be the dual order of $p$.  Let $p\rightarrowtail$q mean $q$ is a topological ordering of $p$. Then the above claim can be expressed as

$$ p\rightarrowtail q\ \Leftrightarrow p^d \rightarrowtail q^d$$

Proof: All we need to do is to follow the definitions. Let the underlying set of $p$ be $S$, which is also the underlying set of $q$, $p^d$ and $q^d$. For a poset $p$, we use "$\preceq_p$" to denote the binary relation on of $p$ $S\times S$.

"$\Rightarrow$":

Let $s_1,s_2\in S$ such that $s_1\preceq_{p^d} s_2$. Then by the definition of the dual order, $s_2\preceq_{p} s_1$. By the definition of a topological sort, $s_2\preceq_{q} s_1$. By the definition of the dual order, $s_1\preceq_{q^d}s_2$.
Since $q$ is a total order, so is $q^d$.

"$\Leftarrow$":

Let $s_1,s_2\in S$ such that $s_1\preceq_{p} s_2$. Then by the definition of the dual order, $s_2\preceq_{p^d} s_1$. By the definition of a topological sort, $s_2\preceq_{q^d} s_1$. By the definition of the dual order, $s_1\preceq_{q}s_2$.
Since $q^d$ is a total order, so is ${(q^d)}^d=q$.

In fact, the implication "$\Leftarrow$" is the dual of the implication "$\Rightarrow$". Replacing $p$ by $p^d$ and $q$ by $q^d$ in the implication "$\Rightarrow$", we get "$\Leftarrow$".

Q.E.D.

The claim above shows that given a poset $p$, whenever we can construct a topological order $q$ for $p$, we also have $q^d$, a topological order for $q^d$.
Hence $q\to q^d$ maps the topological orders of $p$ to the topological orders of $p^d$.

Similarly, whenever we can construct a topological order $r$ for $p^d$, we also have $r^d$, a topological order for ${(p^d)}^d=p$.

The map $q\to q^d$ and $r\to r^d$ are inverse functions to each other. So, each map is, in fact, a one-one correspondence. So the number of topological orderings of $p$ equals the number of the topological orderings of $p^d$.

Be careful that the topological orders of the original poset $p$ and its dual $p^d$ might not be same, although they are dual to each other.

For example, we can check the poset $p=\{a,b,c\}$ with $a\preceq_p b$ and $a\preceq_p c$. All topological orders of $p$ shares the unique least element $a$ but don't share greatest elements. All topological orders of $p^d$ shares the unique greatest element $a$ but don't share least elements.

Exercise. A poset is connected if the directed graph representing the poset is connected. Show that the maximum number of topological orderings of a connected poset of $n$ vertices is $(n-1)!$.


After how many iterations will an integer circle back to 0 in Python?

Your question is about python, but let me make it more general. Integers are represented in three major ways in modern computers:

Unsigned integers of a fixed number of bits.
Signed integers of a fixed number of bits.
Bignums, also known by various other names such as multiple precision integers.

The first two exhibit the wrap-around behavior. The third doesn't.

Python uses three different representations for integers:

Small integers are stored as "constants".
Integers which fit into a signed machine word (plain integers) are stored as such.
Larger integers (long integers) are stored as bignums.

This is described in the python documentation.

Plain integers are automatically promoted to long integers if need be. Therefore the wrapping around behavior does not happen.

On a 64-bit system, $2^{63}-1$ is the largest plain integer:

>>> (2**62-1)*2+1
9223372036854775807
>>> 2**63
9223372036854775808L

Note the suffix L, which indicates a long integer.


There are two possible interpretations for "running time of an algorithm". The first interpretation is the worst-case running time, depending on some parameters such as the input length $n$. The second interpretation is that the running time is some bound that holds for all inputs with the given parameters. When we give a big $O$ estimate, both interpretations amount to the same thing: if an algorithm has a running time of $O(n^2)$, then this is both a worst-case bound and a bound which is valid for all inputs of length $n$.

What is then the interpretation of $\Theta(n^2)$ in your case? It's hard to say without more details, and could depend on the context. If it's a worst-case bound then the meaning is "there is a family of inputs for which the algorithm runs in $\Omega(n^2)$ time". If it's a global bound then the meaning is "the algorithm runs in $\Omega(n^2)$ time on all inputs". Out of these two possible interpretations, the first seems slightly more likely, but others may hold different opinions.


Is this a correct approch of finding expected runtime of an algorithm?

First of all, notice that in TwoMax1, $A[i]$ is always compared to $L$. This already gives you $n$ comparisons. If $A[i]$ is not the current maximum, then it is compared to $S$. This happens with probability $1-1/i$ (see below). Therefore the total expected number of comparisons is
$$
n + \sum_{i=1}^n \left(1 - \frac{1}{i}\right) = 2n - H_n = 2n - \log n - \gamma + O\left(\frac{1}{n}\right).
$$

In TwoMax2, $A[i]$ is always compared to $S$. Again, this gives you $n$ comparisons. If $A[i] > S$, which happens when $A[i]$ is one of the two maximal elements, then $A[i]$ is compared to $L$. When $i = 1$, it is always the case that $A[i] > S$, and otherwise it happens with probability $2/i$. Therefore the expected number of comparisons is
$$
n + 1 + \sum_{i=2}^n \frac{2}{n} = n + 2H_n - 1 = n + 2\log n + \gamma - 1 + O\left(\frac{1}{n}\right).
$$

The second algorithm thus makes roughly half as many comparisons than the first algorithm.

You mention that the sample space consists of all outcomes. But in fact, the sample space consists of all inputs, or in your case, all input permutations. You are analyzing the algorithm with respect to the uniform distribution over this sample space.

Also, the probability that $A[i] > A[1],\ldots,A[i-1]$ (numbering elements from zero) is not $i/n$ (consider for example the case $i=1$!) but rather $1/i$. The reason is that if $A[1],\ldots,A[n]$ is a random permutation then $A[1],\ldots,A[i]$ is a random permutation of $\{A[1],\ldots,A[i]\}$. In particular, $A[i]$ is a random element of $\{A[1],\ldots,A[i]\}$, and so it equals the maximum with probability $1/i$.


Dijikstra implementation in books subtly different

Usually algorithms are specified in a somewhat high level format. Later one might fine tune some of the implementation details to get the complexity right.
Usually we call the various implementations all Dijkstra's algorithm. (And yes, I consider those implementation details, even though we are not coding in a specific language.)

How do we store the distances so that we easily find the one with shortest distance from the start node?
How do we store the graph: adjacency lists or adjacency matrix?
It might be a good idea to compute 'temporary' distances for nodes not yet completed, so that we do not have to look at all edges between nodes that are completed and those that are not yet completed.

In the special case of Dijkstra's algorithm the type of graphs we consider might influence the implementation details. We might choose a certain type of priority queue when the graphs are sparse or not.


This is a special case of maximum weighted independent set on an interval graph. Another way to phrase your problem is as follows: choose a subset of your neighbors of maximal sum in which no two elements have difference exactly 1.

One simple way to solve your problem is using dynamic programming. First sort the list, and remove duplicates (but remember how many of each number appear in the original list). Now use dynamic programming to calculate the optimal solution for every prefix of the sorted list.


Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves

No, your reasoning seems right. Sometimes problem setters just throw in such things in order to make the problem sound harder than it is.


Set them up as recurrences. First, note that both just return $N$ characters $x$. Call the time taken by the first function for $N$ $A(N)$ and similarly $B(N)$ for the second. For the first version, the function calls itself with $\lfloor N / 2 \rfloor$ (I'm taking your language to be Java or similar, dividing integers truncates), and then concatenates some strings. As noted, $f(N)$ is just $N$ times 'x'. Consider teh different cases, and what work is done in each of them:

$$A(N) = \begin{cases}
            0                                           & N = 0 \\
            A(\lfloor N / 2 \rfloor) + 2 \cdot N / 2   & N > 0 \wedge 2 \mid N \\
            A(\lfloor N / 2 \rfloor) + 2 \cdot (N - 1) / 2 + 1     & \text{otherwise}
         \end{cases}$$

You see that both last cases simplify to just $A(\lfloor N / 2 \rfloor) + N$. Your recurrence is $A(N) = A(\lfloor N / 2 \rfloor) + N, A(0) = 0$

For the second one, you get $B(N) = B(\lfloor N / 2 \rfloor) + B(\lceil N / 2\rceil) + N, B(0) = B(1) = 0$


Is "Solving two-variable quadratic polynomials over the Integers" is an NP-Complete Problem?

As you noted, solving that Diophantine equation is not complicated, mathematically.
All is needed is to find the necessary remainders $r$ of $x$ modulo $B$ such that $Ax^2-C$ is a multiple of $B$, then all integer solutions are of the form $x=Bn+r$ and $y=(C-Ax^2)/B=(C-A(Bn+r)^2)/B$.
One way to find the remainders $r$ is to

factor $B=\prod_i q_i^{a_i}$, where $q_i$ are different primes,
solve the congruences $Ax^2-C\equiv 0\pmod{q_i}$, which in the worst case have two solutions $\pm t_i$,
lift these solutions to solutions $\pm\theta_i$ of $Ax^2-C\equiv 0\pmod{q_i^{a_i}}$ and
glue these solutions, using the Chinese Remainder Theorem to get a solution of $Ax^2-C\equiv0\pmod{B}$. Note all the $\pm$ choices.

Factoring $B$ is possibly hard, but maybe it isn't. My outdated knowledge is that nobody knows. Also maybe it is also possible to find the remainders $r$ without factoring $B$. What the proof that I saw exploits to conclude that the problem is NP-complete is the decision that still remains to be made.
The original decision problem becomes checking if one of the choices of $\pm$ is such that the interval $x\geq0$, in other words $n\geq -r/B$, intersects (and intersection contains an integer) the interval where $n$ is such that $y\geq0$. Compared to the bit size of $(A,B,C)$ there can be many remainders $r$ to test. I will not quantify this claim. Let the proof of its NP-completeness give evidence of it.
In Moore and Mertens' The Nature of Computation, section 5.4.4 there is a reduction (with parts left as exercises) of the SUBSET SUM decision problem to this decision problem (let's call it QDE).

Let me sketch their argument just to get a taste of how the input to SUBSET SUM is encoded in the input to QDE and how the choices of $\pm$ correspond to the subsets that one can consider in SUBSET SUM. Maybe I or someone else can expand the details later.
SUBSET SUM gets a set (or maybe a multi-set) $X=\{x_1,x_2,\ldots x_n\}\subset\mathbb{N}$ and $t\in \mathbb{N}$ and asks if there is a subset $Y\subset X$ such that the sum of its elements is $t$. If one defines $S=2t-\sum_{k=1}^{n}x_k$ then SUBSET SUM is equivalent to the existence of $\sigma_i\in\{-1,1\}$ such that $$S=\sum_{k=1}^{n}\sigma_kx_k$$

Here we have already choices of subsets encoded as choices of $\pm$.

Taking $m$ such that $2^m>\sum_{k=1}^{n}x_k$ this equation is equivalent to $$S\equiv \sum_{k=1}^{n}\sigma_kx_k\pmod{2^m}$$
If we choose $q_1,q_2,...,q_n$ relatively prime odd numbers (the first odd primes suffice), the Chinese Remainder theorem ensures that there are $\theta_1,\theta_2,\ldots,\theta_n$ such that
$$
\begin{align}
\theta_k&\equiv x_k\pmod{2^m}\\\
\theta_i&\equiv0\pmod{\prod_{k=1,k\neq i}^{n}q_k^m}\\\
\theta_k&\not\equiv0\pmod{q_k}
\end{align}
$$

The $\theta_i$ will be, for the QDE problem to be created, the solutions $\theta_i$ that we mentioned at the beginning.

The first group of these congruences imply that SUBSET SUM is equivalent to $$S\equiv \sum_{k=1}^{n}\sigma_k\theta_k\pmod{2^m}\qquad\qquad(*)$$

Now they build the quadratic equation, which solubility is equivalent to the solubility of this congruence.

They define $H=\sum_{k=1}^n\theta_k$ and $K=\prod_{k=1}^{n}q_k^m$. Observe that any $x$ of the form $$x=\sum_{k=1}^{n}\sigma_k\theta_k$$ satisfies $$H^2-x^2\equiv0\pmod{K}$$
Then, through a pair of exercises, they argue why there are choices for picking $q_i$ and a $\lambda_1$ large enough such that $2H<K$, and $|t|<H$, and ensuring that $(*)$ has a solution if and only if the Quadratic Diophantine Equation
$$\underbrace{(\lambda_12^{m+1}+K)}_{A}x^2+\underbrace{2^{m+1}K}_{B}y-\underbrace{(\lambda_12^{m+1}H^2-KS^2)}_C=0$$
has a solution $x,y\geq0$.
Notice how this equation re-writes as
$$\lambda_12^{m+1}(H^2-x^2)-K(S^2-x^2)=2^{m+1}Ky,$$
The choices made in the technical details are such that when there is a solution $x,y\geq0$ for this equation it is always the case that $H^2-x^2$ is already known to be a multiple of $K$ and $S^2-x^2=(S+x)(S-x)$ a multiple of $2^{m+1}$.


Let $L_n$ consist of all words over $\{a,b\}$ such that the $n$th symbol from the right is $a$. The minimum number of states in a DFA accepting $L_n$ is $2^n$.

First, let us construct a DFA with so many states. The states of the DFA correspond to strings of length $n$ over $\{a,b\}$. The starting state is $b^n$. When in state $\sigma_1\ldots \sigma_n$ and reading $\sigma$, we move to state $\sigma_2 \ldots \sigma_n \sigma$. A state is accepting if the first symbol is $a$.

Second, we use the Myhill–Nerode theorem to show that $2^n$ states are necessary. We claim that all words of length $n$ are pairwise inequivalent. Indeed, let $x \neq y$ be words of length $n$. Then $x_i \neq y_i$ for some $i$, say $x_i = a$ and $y_i = b$. This implies that $x b^{i-1} \in L_n$ whereas $y b^{i-1} \notin L_n$, showing that $x,y$ are inequivalent modulo $L_n$.


Usually, languages of the form "The number of $x$s is equal to the number of $y$s" aren't regular because you could have an arbitrarily long sequence of $x$s with no $y$s but a finite state automaton can't remember how long that sequence was.

However, in this case, any time you see $011$, either the rest of the string contains only $1$s or the string looks like $0111^k0\ldots$ for some $k\geq 0$ and you've found the matching $110$.  If you think about this for a bit, and try some examples, you should be able to figure out some simple rules that determine whether a string is in the language, and then implement that as a regular expression.


Sum of two elements in set evenly divisible by k

This solution actually works in time $O(n+k)$. The idea is to maintain an array $m_0,\ldots,m_{k-1}$, where $m_r$ is the number inputs seen so far which leave a remainder of $r$ after division by $k$. When we see a new input which leaves a remainder of $r$ after division by $k$, we count $m_{k-r}$ new pairs (where $m_k = m_0$), and then update the array $m$.

A simpler solution is to first compute a histogram $m_0,\ldots,m_{k-1}$, where $m_r$ is the number of inputs in total which leave a remainder of $r$ after division by $k$. For each pair $s+t = k$, we count $m_sm_t/2$ pairs, and for $s=t=0$, we count $m_0(m_0-1)/2$ pairs (exercise), for a total of
$$ \frac{m_0(m_0-1)}{2} + \sum_{s=1}^{\lfloor k/2 \rfloor} \frac{m_sm_t}{2}. $$


Building automaton from regular expression

You failed to notice that your $M$ and $N$ states are indistinguishable. Let's take a walk around the problem first.

We can express this all in regular equations, in the notation of John Conway's Regular Algebra and Finite Machines:

$\begin{align}
L &= a M\\
M &= a M + b P\\
P &= 1 + a M + b P
\end{align}$

We can see that $L$

starts with an $a$;
remains in $M$ for as many $a$s as you like;
goes to $P$, the only terminal state, at the first sign of a $b$;
stays in the terminal $P$ for as many $b$s as you like;
returning to $M$ at the first sign of an $a$.

These equations translate immediately into a DFA. We can also solve them:

$M = a M + b P$

... has solution

$M = a^*bP$

Substituting this into

$P = 1 + a M + b P$

... we get

$\begin{align}
P &= 1 + a a^*bP + b P\\
&= 1 + a^*bP
\end{align}$

... which has solution

$\begin{align}
P &= (a^*b)^*\\
&= 1 + (a + b)^*bP
\end{align}$

Now we can solve for $M$:

$\begin{align}
M &= a^*bP\\
&= a^*b(a^*b)^*\\
&= (a+b)^*b
\end{align}$

And for $L$:

$\begin{align}
L &= a M\\
&= a(a+b)^*b\\
\end{align}$

How do we solve the equations above? The solution to the equation

$X = \mathcal {x} + \mathcal y X$

... ,where $\mathcal {x}$ and $\mathcal {y}$ are regular expressions independent of $X$, is

$X = {\mathcal y}^* \mathcal {x} $

OK. What did you miss?

$\begin{align}
a^{-1}M &= b + (a + b)^* b\\
&= (1 + (a + b)^*) b\\
&= (a + b)^* b\\
&= M
\end{align}$

Even if you miss this, you should find out by further beheading that $M$ and $N$ are indistinguishable.


Why is the sequence, "1,3,2,4", not a bitonic sequence?

In this sequence, lets consider 3 as the bitonic point. So 1,3 makes for a strictly increasing series.

However after we cross the bitonic point 3, 2 and 4 do not make a strictly decreasing series.

Another point in Bitonic Series' is that we have to take into account circular bitonic patterns. So a series like 1 2 5 0 -5 -2 is bitonic since we monotonically increase from 1 to 5, then monotonically decrease from 5 to -5 and again we monotonically increase from -2 to 5.

In the case of 1 *3* 2 *4* 1, there are 2 peaks occurring and hence its not even circularly bitonic.


Yes, these can all be viewed as operators at the type level, but they're not all completely analogous. Most of these are type constructors in that they're formation operators for types, though type-level application is simply a type operator.

$\to$ may be viewed as an ordinary type constructor. In Pierce's notation, this is denoted $\lambda X . \lambda Y . X \to Y$. You can just as well think of it as binary algebraic structure on the set of types $(-) \to (-) : \star, \star \to \star$, where $\star$ is the kind of types. (If you have a higher kind above this, it could live there, but this depends on precisely what your calculus is.) The product of types, $\times$, may be viewed similarly. Type-level application is also a type operator.

$\forall X$, $\exists X$ and $\lambda X$ are also type constructors, but they're a little different from the previous two in that they're binding operators: just like the $\lambda$ term operator, they bind a variable in the context (though in this case, a type variable). This means these type constructors are no longer algebraic operators à la universal algebra like the simple type constructors $\to$ and $\times$.


Finding representatives of equivalence classes

The most efficient way known of doing this is the union-find algorithm. The idea is to keep a forest (but with links "upwards", not downwards), and squash long branches. You start with each element in its own forest. To make $a$ and $b$ equivalent, you check it $a$ and $b$ are already in the same class by following their links to the respective roots. If the roots are different, make the smaller tree a subtree of the larger one. And each time you follow a chain to a root, afterwards revisit all nodes on the path and make them point directly to the root, effectively making later searches take one step.

This is rather simple to program with an array for the nodes, and array indices for links.


How to explain/understand brackets of applicative functor [[f u1... un]]?

In it's simplest, original form, $[\![f\ x \ y]\!]$ just means $\eta(f)\circledast x \circledast y$ where $\circledast$ is what Haskell calls <*> and $\eta$ is what Haskell calls pure. Of course, this is only type correct if $x$, and $y$ have types like $\mathcal{F}(\dots)$ where $\mathcal{F}$ is an applicative functor. If they don't, we can be a bit smarter and automatically use $\eta$/pure to "lift" them to that type. From there, the translation can simply be $[\![f\ x_1\dots x_n]\!]\leadsto [\![f]\!]_1\circledast [\![x_1]\!]_1\circledast\cdots\circledast [\![x_n]\!]_1$ where $[\![e]\!]_1$ is either $e$ or $\eta(e)$ depending on the type of $e$. More systematically, $[\![e\ x]\!]\leadsto [\![e]\!]\circledast [\![x]\!]_1$ where $[\![e]\!] = [\![e]\!]_1$ when $e$ is not an application. You can easily imagine a variation that recursively applies the transformation.

The idiom brackets are just for convenience. The example you show of an applicative expression would become [[3 + 5]] using idiom brackets which is quite a bit shorter and more readable than pure (+) <*> pure 3 <*> pure 5 (which is in this case just pure (3 + 5) and thus is a fairly trivial case).

I have no idea what you mean by [[F(tau)]]. Idiom brackets don't apply to types.

There's a quasi-quoter that implements a notation similar to idiom brackets. Idiom brackets are also implemented by the Strathclyde Haskell Enhancement (SHE) which is made by the person who originally introduced the notation and author of that Functional Pearl, Conor McBride.


Why using Hyper-threading can lead to performance degradation

It would seem that the answer, as per usual, has something to do with caches. Since hyper-threads utilize the same L1 and L2 caches, one hyper-thread can trash another's caches. In the worst case the threads take turns trashing the other's cache and performance degrades as the caches are re-filled only to be trashed again.

Of course, this is likely very workload specific, which would explain why the problem is mostly seen on servers.

It is also worth noting that the answer depends in part on what you mean by "performance." For example, in real-time systems your performance metric is predictability instead of throughput, which hyper-threading negatively impacts by introducing unpredictable stalls.


Is a stack overflow detected by hardware or software?

It can be software, or hardware, or both, or none.

There are two kinds of overflows: overflow when growing the stack (when entering a function), and overflow when accessing an array on the stack. Overflows when growing the stack can be detected by making a bounds check on function entry, to verify that there is enough room (and either signal an error or grow the stack if there isn't). Overflows when accessing an array on the stack are only an issue in low-level languages that don't verify array bounds; the solution there is to verify array bounds.

These software approaches have the advantage that they work fully reliably: you can be sure that any stack overflow will be detected. Their downside is that they increase the code size and the execution time. Hardware can help by providing a method to detect most overflows at no cost as long as no overflow occurs. On an architecture with an MMU¹, the runtime environment can arrange to map the stack on a page boundary, with the next page remaining unmapped.

+---------------+---------------+---------------+---------------+
| stack                         | unmapped      | other stuff   |
|    ----> direction of growth  |               |               |
+---------------+---------------+---------------+---------------+
^               ^               ^               ^               ^  page boundaries

That way, if the software attempts to access data beyond the page boundary (whether because the stack pointer has moved beyond the boundary or because the array access is out of bounds and beyond the boundary), it will cause a fault by accessing an unmapped area. This only happens if the overflow is small enough: if the amount of overflow is too large, the program may end up accessing other stuff on the other side of the gap in the address space.

The downsides of the hardware approach are that it isn't fully reliable since an overflow by a large amount may not be detected, and that it doesn't detect array overflows that remain within the addressable space.

To detect array overflows, another software technique is a canary: put a special value at the top of the stack or between frames, and check that the canary value hasn't changed on function return. This is also an imperfect technique since the overflow might avoid the canary altogether or might not be detected because the canary value has been restored by the time it is checked. Nonetheless, it is useful to make it harder to exploit some security vulnerabilities.

The safest and cheapest way to avoid stack overflows is to calculate the amount of stack that the program will need before starting to execute it, by static analysis. However this is not always practical: the amount of stack needed by a program is undecidable in general and depends on the data that's manipulated by the program.

¹  The same principle can also be applied with just an MPU, or with no memory protection if there is a single thread whose stack is at the edge of the existing physical mappings.


What do these Big-O notations mean in context of comparison

In this context, this comparison means the subset of. Hence, $O(n\log n) > O(n)$ means All members of $O(n)$ exist in $O(n \log n)$ as well or $O(n) \subset O(n \log n)$. For example, $f(n) = \sqrt{n} \in O(n)$ and $f(n) \in  O(n\log n) $ and $g(n) = n \log n \not \in O(n)$ and $g(n) \ \in O(n \log n)$.


Signed and Unsigned Loads in a 32-bit Registers

A $n$-bit bitstring can be interpreted semantically both as an unsigned integer in the range $0$ to $2^n-1$, and as a signed integer in the range $-2^{n-1}$ to $2^{n-1}-1$. There is always a way to assign an $n_1$-bit bitstring to an $n_2$-bit bitstring so that both have the same semantics, but the way to do that depends on whether the semantics is unsigned or signed. In the unsigned case, we use zero extension: we affix $n_2-n_1$ zeroes on the left. In the signed case, we use zero extension: we affix $n_2-n_1$ copies of the sign bit on the left.

As an example, consider $x=1111$, and suppose that we wish to assign it into an 8-bit bitstring. In the unsigned case, the value of $x$ is $15$, and the extension is $00001111$. In the signed case, the value of $x$ is $-1$, and the extension is $11111111$.

When $n_2 = n_1$, there is nothing to extend, so the signed and unsigned cases are the same. That's why the point is moot in such cases.


Is the Backus-Naur Form a type 2 grammar? If So why?

Backus-Naur Form is a conventional notation for writing Context-Free Grammars.

Its usefulness comes from the need to distinguish the character encoding standards that are used to write texts in various computer languages from the higher-order alphabets of terminal and non-terminal symbols (corresponding to lexical units and syntactical variables, respectively) used in the definition of grammars.

The very idea of using CFGs to define the syntax of high-level programming languages was remarkably precocius, which is another reason why the work of John Backus and Peter Naur was so appreciated at the time.


Is there an online/offline tool that can perform K-means/median, given an initial centroid from the user?

I think this should be possible using the scikit-learn implementation; see here: https://stackoverflow.com/questions/38355153/initial-centroids-for-scikit-learn-kmeans-clustering.


Can we apply the Master Theorem to the following recurrence?

So, we have that $f(n) = O(n^c \log^k(n)) = O(n^0 \log^2(n))$; and since $log_b(a) = log_2(1) = 0 = c$, we are in the 2nd case of the Master's theorem (work to divide the problems is comparable to the work on subproblems (wiki)); thus, applying the theorem, we get $T(n) = \Theta(log^3(n))$.

On the floor operation, I don't know what is the cleanest way of solving it; one way could be to prove it for $n = 2^m$, and then extend to all $\mathbf{N}$ by monotonicity.

We can also calculate $T(n)$ directly:

$$T(n) = T(n/2) + log^2(n) = \sum_{j=0}^{log(n)} log^2(2^j) = log^2(2) \sum_{j = 0}^{log(n)} j^2 = \theta(log^3(n))$$


If we think of the universe as finite, then anything that needs more memory than that finite amount is beyond our computational ability.

However this is not a good model for studying computability, the Turing machine model works much better in reality and that is the reason we use it for studying computation on real computers. A Turing machine doesn't really need an infinite amount of memory, it only needs an unbounded amount of memory. For example, we can provide additional memory to a computer over time (as the computer needs more and more memory) and then we have something similar to a Turing machine. If we assume that we have unbounded amount of time and memory for finishing our computation then the Turing machine captures this concept of computability in principle quite nicely.

Check the Wikipedia article about Turing machines, there is a section that discusses the relevance of the model.

If you are interested in feasible computability, then complexity theory (where we consider various amount of resources like time and space for performing a computational task) is closer to the what we can really do in practice than computability theory. Many experts state that the feasible computations fall in the complexity class $\mathsf{P}$ (and more recently in probabilistic and quantum versions of $\mathsf{P}$, i.e. $\mathsf{BPP}$ and $\mathsf{BQP}$).


You can represent a function by its truth table.  Then, any two functions with the same truth table will be the same function, in the sense that they map the same inputs to the same outputs, so this gives you a way to recognize those.

The truth table has 4 entries, each of which are 2 bits, so the truth table is 8 bits long.  Thus, each function can be associated with an 8-bit binary string, or equivalently, an integer between 0 and 255.  You can "increment" the function by incrementing the corresponding integer and converting it back to a truth table.


A data structure that supports efficient insertion of arbitrary integers, value lookup, and removal of all integers smaller than a given threshold?

If you accept randomized algorithms you could use TREAP. This data structure is BST where each node is augmented with priority, a random number. The only one invariant over normal normal BST is that parent's priority must be greater than children's. This results in a very simple implementation of Insert and Delete functions (recursive variant is 10-15 lines of clean C code).
The complexity of basic operations is $O(\log N)$ on average.
It is possible to cut-off all nodes below threshold in $O(\log n)$ time assuming that nodes below the threshold are not disposed.
Node cut(Node node, int threshold) {
   if (node->key < threshold) {
      // optionally dispose node, and subtree at node->left
      return cut(node->right, threshold);
   }
   node->left = cut(node->left, threshold);
   return node;
}

root = cut(root, threshold);

Note, that there is no rebalancing because the node is replaced by one of its children (or subchildren). As result the priority invariant in satisfied.
Disposal of nodes with a key below the threshold will increase complexity to $O(k + \log n)$, where $k$ is a number of disposed nodes.
Cost of disposal will be amortized to $O(1)$ over multiple operations because each node is created and disposed only once.
Removal of nodes above a given threshold will require symmetrical functions.


Can one find an algorithm whose running time is larger than Ackermann's function?

$A(n,n)$ is computable. So a trivial algorithm with complexity $O(A(n,n)^2)$ is the following:

Compute $x = A(n,n)$.
Loop $x^2$ times, doing nothing.


Is $a^n b^m$ never regular if n and m have some relation between them?

For a relation $R(n,m)$, let $L_R = \{ a^n b^m : R(n,m) \}$. Call a relation residual if for some $k \geq 1$ and for some $A \subseteq [k]^2$,
$$ R(n,m) \Leftrightarrow (n,m) \pmod{k} \in A. $$
Call a relation semi-residual if it differs from a residual relation by a finite number of points.

Claim: $L_R$ is regular iff $R$ is semi-residual.

Proof: It is not hard to check that if $R$ is semi-residual then $L_R$ is regular. For the other direction, consider an automaton for $L_R$. For each state $\sigma$, let $L_\sigma$ be the set of all $n$ such that upon reading $a^n$, the automaton reaches $\sigma$. Since $L_\sigma$ is unary, it is eventually periodic. By taking the least common multiple of all periods, we see that the state that for $n \geq n_0$, the automaton find itself upon reading $a^n$ depends only on $n\pmod{k_a}$ from some $k_a$. Doing the same for $b^m$, we see that for $n \in L_\sigma$, the set of all $m$ such that $a^n b^m \in L$ is eventually periodic, and so for $m \geq m_0$, depends only on $\sigma$ and on $m\pmod{k_b}$ for some $k_b$. Taking $k$ to be the LCM of $k_a,k_b$, we find that for $n \geq n_0, m \geq m_0$, $a^n b^m \in L$ depends only on $(n,m) \pmod{k}$. Hence the corresponding $R$ is semi-residual.


For signed integers, why don't representative the smallest number as all zeros in binary, and the largest as all ones?

This would make it basically impossible to implement the C language. In the C language, a value that can represented both as a signed and unsigned integer must have the same bit representation.

There are other problems, like you can’t use the same hardware for adding signed and unsigned integers, conversion between signed and unsigned requires an actual hardware operation.


Algorithm for getting symetric vertex sets of undirected graph

You want to know the orbits of the action of the automorphism group of a graph on its vertices. This is equivalent to graph isomorphism, for which no really simple algorithms are known. Practical graph isomorphism algorithms, which work fast in practice, are known – check nauty for example. Apparently nauty can compute the automorphism group directly, from which you can easily compute the orbits of its action on the vertices.

Solving GI using your task. Given connected graphs $G_1,G_2$, we want to know whether they are isomorphic. Compute the orbits, and check whether any of them mixes vertices from $G_1$ and $G_2$.

Solving your task using GI. Given a graph $G$ and two vertices $x,y$, create two copies of $G$ and attach a long path to $x$ in one of them and to $y$ in the other. The two vertices belong to the same orbit if these graphs are isomorphic.

The second reduction involves $n^2$ invocations of GI, whereas $\log B_n \approx n\log n$ (here $B_n$, the $n$th Bell number, is the number of partitions of $\{1,\ldots,n\}$). This means that any reduction needs $\Omega(n\log n)$ invocations of GI, and suggests that my reduction can be improved.


Do finite state machines need transitions for all symbols?

Your question isn't entirely clear but it's easy enough to just list all the possible answers that could arise, depending on exactly what you mean.

If you're asking about nondeterministic finite automata (NFAs) then you don't need to account for every symbol. The rule is that, if you're in a state and you encounter a symbol that has no transition, then that branch of the computation rejects immediately.

If you're asking about deterministic finite automata (DFAs), then it depends on exactly what definition you're using. The classical definition (e.g., in Sipser) is that every state must have exactly one transition for each possible symbol. In that interpretation, you need a trap state, since you must specify what happens for every possible symbol you could read. Other authors, though, say that each state of a DFA has at most one transition for each symbol. In that case, you don't need a trap state: as with an NFA, if you read a symbol that has no transition, you reject.


What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to

The trivial implications are:

$\mathsf{NP^{EXP}=EXP\subseteq NEXP \subseteq EXP^{NP}\subseteq EXP^{PSPACE}\subseteq EXP^{EXP} = 2EXP}$

I suggest that you try proving these relationships yourself. $\mathsf{NEXP\subseteq EXP^{NP}}$ requires a simple padding argument, and for $\mathsf{2EXP\subseteq EXP^{EXP}}$ observe that the language $L=\{\left(M,x,t\right) | \text{M accepts $x$ within $t$ steps}\}$ is EXP-complete (when $t$ is encoded in binary). Anything more than that is probably hard, e.g. $\mathsf{NEXP\subsetneq EXP^{NP}}$ implies $\mathsf{NP\subsetneq P^{NP}}$ via a padding argument.


Convolutional Neural Networks - Where should I start from?

I know this is a link only answer, but the question is a reference request.

Neural Networks and Deep Learning is a free online book. The book will teach you about:

Neural networks, a beautiful biologically-inspired programming paradigm which enables a computer to learn from observational data
Deep learning, a powerful set of techniques for learning in neural networks


I would suggest letting cost(i,j,k) be the cost of transforming [the first i-1 segments of clean, followed by the first j elements of the ith segment of clean] into [the first k elements of segmented].

You can then write a recurrence relation that expresses cost(i,j,k) in terms of values of cost(i,j-1,k), cost(i,j,k-1), and cost(i,j-1,k-1) (with a convention that cost(i,0,k) = cost(i-1,len(clean[i-1]),k)).  Then, you can use dynamic programming to fill in these values.


Just observations that do not fit on the comments:

I made a little research, and here are what I found + some of my observations:
1) You can use exhaustive search to find whether a solution exist. [so it is decidable]
2) In case $\delta$ is not restricted, all you need to check is the sum of all ranges and compare it to the distance between the farthest two points. If greater or equal, then there exist a solution.
3) In case $\delta$ is restricted, then you are trying to restrict the distance traveled by sensors to at most $n \delta$. In case the sensing ranges are not equal, then this problem is still open [1].

I would suggest you look in the same reference for a solution for the case of equal sensing ranges. So I think a greedy solution exist.

[1] On Minimizing the Maximum Sensor Movement for Barrier Coverage of a Line Segment. J. Czyzowicz , E. Kranakis , D. Krizanc , I. Lambadaris , L. Narayanan , J. Opatrny , L. Stacho , J. Urrutia, and M. Yazdani.


You are right. Any problem in $\mathsf{P}$ can be (polytime) reduced to the halting problem, for example. (In fact, any problem in $\mathsf{P}$ can be polytime reduced to any non-trivial language, that is any language other than $\emptyset$ or $\Sigma^*$.)

What is true is that if A reduces to B and B is easy, then so is A. In particular, if A polytime reduces to B and B is in $\mathsf{P}$, then A is also in $\mathsf{P}$.


The definition you are looking for is "defective coloring":

A $(k, d)$-coloring of a graph G is a coloring of its vertices with k colours such that each vertex v has at most d neighbours having the same colour as the vertex v. We consider k to be a positive integer (it is inconsequential to consider the case when k = 0) and d to be a non-negative integer. Hence, $(k, 0)$-coloring is equivalent to proper vertex coloring.
The minimum number of colours k required for which G is $(k, d)$-colourable is called the $d$-defective chromatic number, $\chi _{d}(G)$.


Looking at the code the tutorial provides answers your questions. First of all, as it's described/implemented, crossover doesn't create a new string, it just modifies the two selected ones. So,

Yes, mutation always occurs
You mutate both A and B. There is no C
Yes.


Leader Election: Every bit-reversal ring is $\frac{1}{2}$-symmetric

We will prove your formula for all $\ell$, with a bound of $\lceil \frac{n/2}{\ell} \rceil$. We can assume that $\ell < n/2$, since otherwise $\lceil \frac{n/2}{\ell} \rceil = 1$, and there is nothing to prove. Also, if $n = 1$ then the result is trivial, so we can assume that $n \geq 2$.
The relative order of elements in the interval of length $n/2$ starting at $i$ is the same as the relative order of elements in the ring of length $n/2$, when read from position $i$. For example, here are all intervals of length $4$ in the ring of length $8$, and the corresponding intervals in the ring of length $4$:
\begin{align}
&0,4,2,6 & 0,2,1,3 \\
&4,2,6,1 & 2,1,3,0 \\
&2,6,1,5 & 1,3,0,2 \\
&6,1,5,3 & 3,0,2,1 \\
&1,5,3,7 & 0,2,1,3 \\
&5,3,7,0 & 2,1,3,0 \\
&3,7,0,4 & 1,3,0,2 \\
&7,0,4,2 & 3,0,2,1
\end{align}
To see this, note first that each interval on the left doesn't contain a pair of elements which differ only in their LSB. Therefore, we can ignore the LSB of all elements on the left. One way to do it is to divide all elements on the left by two. This results in the intervals on the right.
This property immediately implies a similar property for all intervals of length $\ell \leq n/2$: the relative order of elements in the interval of length $\ell$ starting at $i$ is the same as the relative order of elements in the interval of length $\ell$ starting at $i \bmod (n/2)$ in the ring of length $n/2$. This implies (by induction) that an interval of length $\ell \leq n/2$ has at least this many order-equivalent intervals: $2\lceil \frac{n/4}{\ell} \rceil \geq \lceil \frac{n/2}{\ell} \rceil$.


Is unambiguous because there is no string of rule A which is a string or substring of B. And viceversa.


How would one construct conjunctively local predicate of order k for checking if a shape is Convex?

One way to construct $\Psi_{\mathrm {CONVEX }}$ is as follows:
define $\phi_{i,j,k}(X) := \begin{cases} 1 & \text{if $(x_i,x_j \in X \Rightarrow x_k\in X)$ } \\ 0 & \text{otherwise}\\\end{cases}$.

Now, we define the set $\Phi$ by picking all pairs of $x_i,x_j\in R$ and all $x_k$ that lie on the line segment between them, i.e. $\phi_{i,j,k}\in \Phi$ for all $x_i,x_j\in R$ and all $x_k\in \{x\in R\mid \exists\lambda\in [0,1]: x=\lambda x_i + (1-\lambda)x_j\}$.

Note that each $\phi_{i,j,k}$ depends on only three values of $R$ and that the shape $X$ is convex if and only if all $\phi_{i,j,k} \in \Phi$ have value $1$. So, according to your definition, $\Psi_{\mathrm {CONVEX }}$ is conjuctively local of order $3$.

This does not seem like a very practical approach to determine the convexity of a shape, in particular when $R = \mathbb{R}^2$, since that means $\Phi$ is of infinite size.

So the basic idea is that for given indices $i,j,k$, the $\phi_{i,j,k}$ are functions of $X$ and exactly three points of $R$: $x_i,x_j$ and $x_k$. The selection of their indices (i.e. the set $\Phi$) is independent of $X$, but does depend on $R$.


This can be solved in $O(n \log n)$ time by a greedy algorithm.  Take the earliest week you need to cover (that isn't covered yet).  Pick the set of days-of-the-week that you need to cover in that week.  Choose a filtered data interval that starts with that week, uses that mask, and extends as far as possible.  Add that to your collection, and repeat.

I'll let you work out the proof that it is correct, via an exchange argument.  How to prove greedy algorithm is correct may be helpful.

To make this run efficiently with a $O(n \log n)$ worst-case time, you'll need a proper data structure for storing the filtered intervals and figuring out how far you can extend an interval.  I'll let you figure that out, but a hint: a balanced binary search tree provides $O(\log n)$ running time for all basic operations.


Are some real world compression algorithms sometimes producing unexpectedly large files?

If you take vanilla RLE in bitmap which does not have any consecutive runs it will increase file size two times. It is apparently very rarely used fact that BMP, TIFF and PCX allows compression, (not all applications supporting these formats even implement RLE scheme). This is very pathological case and since it mostly increase file size it is abandoned.

Normal compression algorithms include information of failure, so instead of huge increase you can expect several bytes per chunk increase. In those that do not check there are three methods of checking how far we can increase file: take already compressed file, take encrypted file or find pathological cases from algorithm.

I have generated $256 \text{ bytes}$ file with consecutive numbers.
Compressed as 7z LZMA: $349 \text{ bytes}$, LZMA2:$356 \text{ bytes}$, Deflate or Deflate64: $400 \text{ bytes}$, bz2: $388 \text{ bytes}$, PPMd: $421 \text{ bytes}$ so not that cool.


Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables

Chord is meant to be used in a distributed system where we need to be concerned with load balancing and handling failures of individual machines.

If you try to maintain an AVL tree in a distributed system by spreading the nodes among the available machines, the machine that has to take care of the root node will have a very high load as it is involved in every single request. Moreover, if this machine failed, the AVL tree would be partitioned, which requires you to introduce additional pointers for redundancy (similarly to what is done in Chord using "fingers").

A data structure that is suitable for distributed systems are Skip Graphs, which essentially have the same functionality as balanced trees, in particular, they provide $O(\log n)$-time operations. Moreover, a Skip Graph has built-in fault-tolerance (i.e. can handle churn), as it contains an expander graph as a subgraph (with high probability), and therefore can withstand even a constant fraction of node failures.


expected pairwise square euclidean distance between points

Let $\vec{x},\vec{y}$ be two random $d$-dimensional vectors chosen uniformly and independently from $[0,1]^d$. That is, $x_1,\ldots,x_d,y_1,\ldots,y_d$ are all uniform random samples of the uniform distribution over $[0,1]$. Then
$$
\mathbb{E}[\|\vec{x}-\vec{y}\|^2] =
\mathbb{E}\left[\sum_{i=1}^d (x_i-y_i)^2\right] =
\sum_{i=1}^d \mathbb{E}[(x_i-y_i)]^2 =
d \operatorname*{\mathbb{E}}_{x,y \sim [0,1]} [(x-y)^2].
$$
Let $C = \mathbb{E}[(x-y)^2]$. Then the expected squared distance of two points in $[0,1]^d$ is $Cd$.

It is not hard to calculate $C$ explicitly:
$$
C = \mathbb{E}[((x-1/2) - (y-1/2))^2] =
\mathbb{E}[(x-1/2)^2] + 2\mathbb{E}[(x-1/2)(y-1/2)] + \mathbb{E}[(y-1/2)^2] = \\
2\mathbb{E}[(x-1/2)^2] + 2\mathbb{E}[x-1/2] \mathbb{E}[y-1/2] =
2\mathbb{E}[(x-1/2)^2] = \\ 2\int_0^1 (x-1/2)^2 \, dx = 2\int_0^1 x^2-x+\frac{1}{4} \, dx =
2\left(\frac{1}{3} - \frac{1}{2} + \frac{1}{4}\right) = \frac{1}{6}.
$$


Looking for an algorithm to iterate over essentially different solutions

All solutions are equivalent modulo the equivalence you have given.

Suppose $(a_{i,j})_{1\le i\le 4,1\le j\le 6}$ is some solution. Each row misses two labels, and these pairs of labels form a partition of $\{1,\dots,8\}$ (otherwise some label would occur too often). But then we can choose an exchange of labels modulo which row $1$ misses $7,8$; row $2$ misses $5,6$; row $3$ misses $3,4$; and row $4$ misses $1,2$.

Each row can then be reordered to arrive at the solution

$A=\begin{pmatrix}1&2&3&4&5&6\\1&2&3&4&7&8\\1&2&5&6&7&8\\3&4&5&6&7&8\end{pmatrix}$

Since every solution is equivalent to $A$, by transitivity, they are all equivalent.


Yes.  Construct the product automaton.

The "product construction" is a standard construction from automata theory class (e.g., typically taught in the context of finite-state automata).  It can be applied to HMM's as well, and it will do exactly what you want.

For your example, the resulting HMM will have 9 states.  Each state in the resulting HMM will a pair $(s,t)$, where $s$ is a state of the accelerometer HMM and $t$ is a state of the video stream HMM.  Transitions between them and probabilities are derived in the obvious way.  For instance, if there is a possible transition $s \to s'$ in the accelerometer HMM and a possible transition $t \to t'$ in the video stream HMM, then the product HMM will have a transition $(s,t) \to (s',t')$ (and its probability will be the product of the probabilities of the underlying transitions).  The output distribution is obtained by multiplying probabilities: if $p(x|s)$ denotes the probability of outputting $x$ when in state $s$ in the accelerometer HMM, and $p(x|t)$ the probability of outputting $x$ when in state $t$ in the video stream HMM, then we use $p(x|(s,t)) = p(x|s) p(x|t)$ as the probability of outputting $x$ when in state $(s,t)$ in the product HMM.

This assumes that the internal states of the two HMM processes are independent.  That's something you'll need to verify yourself, to see whether the independence assumption seems reasonable in your particular application domain.


Less used data (1 byte) in memory address holding 4 bytes

So your computer has 32 bits as the smallest addressable unit.

Your compiler has two choices: It can store var1 and var2 in two different sets of 8 bits in the same 32 bit unit, or it can store var1 and var2 in to different 32 bit units. The former produces likely more code, the latter uses more memory. It's up the compiler to decide.

If your programming language supports "pointer to char" as a type, then a pointer to var1 and a pointer to var2 will be different. Even if both are stored in the same 32 bit unit. A "pointer to char" will not be an address as it is used by the computer, but a combination of an address, plus some indication which of the four bytes of a 32 bit unit to access. Cray built machines that worked that way.

In the end, the compiler for your programming language is responsible to make everything work the way it is supposed to work according to the definition of the programming language, no matter how the underlying hardware works.

PS. The compiler also has the option to make char = 32 bit.


Why is CAN protocol preferred to be used in automotive application?

A few reasons :

CAN was developed by BOSCH, which have a lot of influence in automotive equipment (engine control, braking, body, gearbox control...). BOSCH ensured that CAN killed competitors like the VAN protocol. (CAN was patented, and BOSCH sells CAN controller IPs)
CAN is much cheaper than Ethernet.
There were no suitable industrial bus at the time, using physical layers like RS-485 : Modbus, Profibus...

Now several other busses are used in automotive applications :

LIN : Slower, cheaper than CAN. For very simple devices.
FlexRay : Faster than CAN, deterministic. For advanced real time functions like dynamic suspension.
Ethernet : The future, particularly in a 2 wires implementation. For a few advanced applications, including steer-by-wire, video...

Anyway, CAN is here to stay as it offer a good balance between performance and cost of implementation.


Multiple-Choice Questions about decidability

Regarding 1 - $\Sigma^*$ is a superset of every language, not just "many". This is a very general and important point: the measure of how "complicated" a language is, is not in a direct correlation with how "big" the language is.

In 2 - you are correct.

For 3 - the answer is no - if $L_1$ and $L_2$ are CFL, then $L_1\cap L_2$ is decidable. Indeed - decidable languages are closed under intersection, and every CFL is decidable.

As for 4 (assuming that by $\le$ you mean "mapping-reducible") - observe that $0^*1^*$ is a regular language, and in particular - decidable. Thus, if $L\le_m 0^*1^*$, then surely $L$ is decidable.

Conversely, assume that $L$ is decidable, then there exists a mapping reduction from $L$ to every non-trivial language. Indeed, you can decide $L$ within the reduction, and just output a fixed string. So the answer is yes.


How can I develop a pseudo-polynomial time algorithm for a non-integer problem?

Classifying algorithms as pseudo-polynomial time is not really a meaningful concept if there are no numbers (integers) in the instances. Of course, it is up to you to define what parts of the input should be considered "numbers".

Using real numbers in the inputs is a bad idea in the first place if you want to be able to analyze complexity or computability of the problem, as there is no way to encode all real numbers as finite strings from a finite alphabet.

For your problem, you may be able to turn it into an equivalent integer problem using some scaling, but it is impossible to say from the description given. Otherwise I would suggest you redefine the problem with rational parameters instead. This allows you to analyze it as a normal computational problem, and you could also meaningfully talk about pseudo-polynomial time if you, for example, consider numerators and denominators as separate integers.


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


For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$

It seems that $\dagger\dagger$ is consistent with $\|$. You just need to pick a constant $c$ that is larger than or equal to the constant $\gamma$ hidden in the $O(1)$ notation in the definition of $T(n)$ for $n < 140$ (i.e., the line marked with $\ddagger$).
Then, for any $n \in \{1, \dots, 139\}$, you have $T(n) \le \gamma \le c \le cn$, as desired.


Are there any LTL to _non_ deterministic Rabin automaton translators?

You can easily translate LTL to non-deterministic Buchi automata, which can be thought of as a simple fragment of Rabin automata (although they are equally expressive).
I don't think any tool would actually output the acceptance condition described as a Rabin condition, but this is very easy to deduce from the Buchi states.

An example of an online tool to do this conversion is:
http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/

But I'm sure there are many others, as the construction is relatively simple.


Chomsky form for language of single alphabet member

The grammar is similar to what you say:
$$
S \rightarrow S S \mid a
$$
This can't generate $\epsilon$, which any true CFG can't.


Efficient algorithm to replace list of integers with nearest bigger element

The issue is how to find "the next bigger integer on their right", which sounds like a stack operation.

Here is the algorithm in its essence.

Create an empty stack.
Iterate over the given list of integers from left to right.

Push the current integer to the stack.
While the top of the stack is smaller than the next integer in the list, replace the integer in the list that corresponds to the top of the stack by that next integer in the list followed by popping the stack.

The idea of the algorithm is to let the stack store the integers for which we have not found their next bigger integers yet, in the natural order in which they have been examined. Those integers will be strictly decreasing.

In the actual implementation, in order to locate the integer in the given list that corresponds to the top of the stack, the indices of the integers should be stored in the stack instead of the integer themselves.

Here is code in Python:

l = [2, 1, 4, 5, 3, 6, 7, 9, 4, 8, 5, 1 ,3, 8]
s = []
for i in range(len(l) - 1):
    s.append(i)
    while s and l[i + 1] > l[s[-1]]:
        l[s.pop()] = l[i + 1]
print(l)

For readers who does not use Python, s[-1] is the last element of the list s.

Since each index of the given list is appended once and popped at most once and the last index is not even included, the time-complexity of the algorithm is $O(n)$, where $n$ is the length of the given list.


By definition MST or Minimal spanning tree is defined on undirected graph only!

But if you are really want to (and I wander why) You can "make" Kruskal's algorithm work on it ,but you have to make sure you are ignoring loops because otherwise if you got a loop with small weight the algorithm will count it on the "MST" (because it isn't really MST).

Regarding to Prim's algorithm I can't see a way you cane make this work on directed graph.

I don't know other uses of Kruskal's and Prim's and I don't believe there are. Usually you make a slight changes on the algorithm in order to make them do something slight different.


Bounded Quadratic Congruence Problem Variant (for square Residue)

The problem is NP-complete.  Let $d = \gcd(M,b)$.  If $a$ is not a multiple of $d$, then there is no solution.  Otherwise, let $a' = a/d$ and $B = b/d$ and $c = M/d$ and $A \equiv a' c^{-2} \pmod B$.  Then the original equation has a solution if and only if $x^2 \equiv A \pmod B$ has a solution with $x<L$.  As you previously noted, the latter problem is NP-complete.


Number of Retransmission in case of Go Back N

GBN is resending ACK's for the discarded packets .

Excerpt from what I can find:

The receiver's actions in GBN are also simple. If a packet with sequence number n is received correctly and is in-order (i.e., the data last delivered to the upper layer came from a packet with sequence number n-1), the receiver sends an ACK for packet n and delivers the data portion of the packet to the upper layer. In all other cases, the receiver discards the packet and resends an ACK for the most recently received in-order packet. Note that since packets are delivered one-at-a-time to the upper layer, if packet k has been received and delivered, then all packets with a sequence number lower than k have also been delivered. Thus, the use of cumulative acknowledgements is a natural choice for GBN.


Why the number of equivalence classes for the intersection of an irregular language L2 and a regular languge L3 (with 3 EC) can't be determined?

Assuming you are meaning Nerode equivalence classes, the number of classes of a language is finite iff that language is regular.

We cannot make any statement for the intersection of a regular and a non-regular language. That intersection can non-regular, but also regular.
Similar for the star of a non-regular language.

Stating that the number of classes is at least one is not very instructive. Isn't that true for all equvalence relations?