Regular expression for the strings without a particular substring

I did the following multistep technique.

Step 1: make a DFA that accepts all strings with "110".  I am able to construct a DFA that accepts all strings with substring "110" and has just 4 states.

Step 2: Flip all the accepting states to non-accepting and all the non-accepting states to accepting.  This page at Old Dominion describes the technique quite succinctly.  This creates a DFA that accepts the language you want.

Step 3: Now you need to convert the DFA back to a regular expression.  As @Alejandro Sazo mentioned there is a proof that this is possible.  But you need an algorithm.  This paper by Christoph Neumann describes three different techniques.  The easiest one is the "state removal technique."   You remove a state and replace all the edges between states that were connected to the removed state with edges labeled with regular expressions.  As you reduce in this way you eventually get to a regular expression for the whole DFA.  (Note that Figure 4 in the paper I linked is not quite right.  The self-loop on state $q_j$ should have the regular expression "c e* b", not "c e* d".)

By going through this process it became clear that: the language you are going to need to solve for this particular problem has the property that once you have seen the sub-string "11" then you can never see another "0".


Terminology for a graph with ports on its nodes

I was wondering the same thing. It seems that there are a number of publications revolving around this idea, most of them at the TERMGRAPH workshop. They are usually called “port graphs” there.

Tracing the related work of a random sample of papers yields that the following might be the prime paper that introduces this formalism:

  Andrei, O. and H. Kirchner, A Rewriting Calculus for Multigraphs with Ports., in: Proceedings of RULE’07, Electronic Notes in Theoretical Computer Science 219, 2008, pp. 67–82.

One that I find particularly interesting is

  Sandra Alves, Maribel Fernández, and Ian Mackie. A new graphical calculus of proofs. In TERMGRAPH, volume 48 of EPTCS, pages 69–84, 2011


How to implement GREEDY-SET-COVER in a way that it runs in linear time

Here is some Python code that should implement Greedy Set Cover in linear time:

(Warning, it empties the input sets during the processing!)

from collections import defaultdict

F = [set([1,2,3]),
     set([3,4,5,6]),
     set([2])]

# First prepare a list of all sets where each element appears
D = defaultdict(list)
for y,S in enumerate(F):
    for a in S:
        D[a].append(y)

L=defaultdict(set)
# Now place sets into an array that tells us which sets have each size
for x,S in enumerate(F):
    L[len(S)].add(x)

E=[] # Keep track of selected sets
# Now loop over each set size
for sz in range(max(len(S) for S in F),0,-1):
    if sz in L:
        P = L[sz] # set of all sets with size = sz
        while len(P):
            x = P.pop()
            E.append(x)
            for a in F[x]:
                for y in D[a]:
                    if y!=x:
                        S2 = F[y]
                        L[len(S2)].remove(y)
                        S2.remove(a)
                        L[len(S2)].add(y)

print E

It uses a dictionary D to store a list of all sets with a particular element.

It uses an array E to store which sets currently have each size.  In other words, E[sz] will contain information about all the sets that currently have exactly sz elements.

The key to showing that this is linear is to observe that the innermost loop removes an element from a set, so cannot be executed more times than the total number of elements in all sets.


Traveling Salesman Problem with Neural Network

there are many papers on using artificial neural networks to solve TSP including recurrent and Hopfield networks, and they "succeed" in a rough sense, but so far there does not seem to be any evidence that the techniques are in any way (strongly?) superior to other algorithmic approaches, so its something more like a research curiosity at the moment. the use of ANNs for this problem is indeed counterintuitive from the pov of combinatorial algorithmics and the mechanisms by which the problem inputs/ outputs are encoded are novel and tend to vary, and maybe are not yet so standardized. the authors seem maybe more interested in demonstrating "proof of concept" and a comparison with other algorithm types seems more rare (there is some in the last paper). see eg

Traveling salesman problem using neural network techniques / Abdel-Moetty
Using Hopfield Networks to Solve Traveling Salesman Problems Based on Stable State
Analysis Technique / Feng, Douligeris
Comparison of Neural Networks for Solving the Travelling Salesman Problem / La Maire, Mladenov
A Recurrent Neural Network to Traveling
Salesman Problem / Siqueira, Scheer, Steiner


Select a subset of the columns in $3\times n$ matrix, is it NP-hard?

Your problem is NP-complete, indeed. You can, e.g., reduce PARTITION to your problem. If you want to know if there is a subset of the set $\{d_1,\ldots,d_k\}$ that sums up to exactly $D := \frac{1}{2} \sum_{i=1}^k d_i$, you can use your problem by setting $b_i := 1$ and $a_i := d_i$ for all $i$ and by setting $c_1 := D$, $c_2 = 0$, and $c_3 := D$ as well as $b := n-1$.


How can I show this language is Regular? (Foundations of computing)

Your question was already asked before, but got no answer: How to prove for string of triplets that it is a Regular Language?. I merely summarize the comments given there.

You need to implement binary addition. That is easier when you consider first the language in reverse, the lower bits first.

Standard letters are (in a more intuitive notation) [00|0], [01|1], [10|1], [11|0]. In the last case however, we realize that we should take a carry to the next position. This can be solved by adding a special state for that case, and adapting the letters accordingly.


Hardness of problem related to number of subsets that satisfy a particular property

The problem is NP-hard: in fact, it is #P-complete.  Therefore, it is unlikely you'll be able to find an efficient solution for this problem.  The proof is by reduction from #Monotone-SAT.

As Ricky Demer explains, without loss of generality we can take the "predefined set" to be equal to the union of all properties.  (If the predefined set is larger than that, the answer to your problem is 0.  If the predefined set is smaller than that, then we can remove all elements that mention a property not found in the predefined set, and we get a new problem instance with the desired property.)  So let's focus only on this case.

Here is the reduction from #Monotone-SAT.  Suppose we have a CNF formula $\varphi$ over $n$ variables and with $m$ clauses, where all of the literals in each clause are positive (i.e., no variable is negated).  Then we can define an instance of your problem that corresponds to $\varphi$.  The problem instance has $n$ elements, one element for each variable, and $m$ properties, one property for each clause.  The set of properties of a variable is just the set of clauses that mention that variable.  Then the number of solutions to this problem instance is exactly the number of satisfying assignments to $\varphi$.

It follows that your problem is exactly as hard as #Monotone-SAT: any algorithm for your problem gives a solution to #Monotone-SAT.  However, it is known that #Monotone-SAT is #P-complete.  (In fact, we can make a stronger statement: #Monotone-2SAT is also #P-complete.)  It is widely believed that #P-complete problems cannot be solved in polynomial time.  Thus, there is unlikely to be any polynomial-time algorithm for #Monotone-SAT -- or for your problem.

That's the bad news.  Now one slight bit of hope.  There are off-the-shelf #SAT solvers out there that you could try applying to your problem.  See, e.g., https://cstheory.stackexchange.com/q/1295/5038 for some pointers.  Now you shouldn't expect them to be efficient -- they are subject to the same hardness result, and so they might be very slow for all but small problem instances.  However, if you absolutely must solve your problem in practice, this is something you could try.  There are also tools for approximate model counting, which could be used to compute an approximation/estimate for the number of solutions to your problem -- however, again, this is a hard problem and you shouldn't expect algorithms with a good worst-case running time.

My thanks to Ricky Demer for the key insight that enabled me to recognize the relationship to #Monotone-SAT.


Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)

Yes, they are different. $L(M)$ is the set of all inputs accepted by a Turing machine, so $E_{TM}$ asks if a Turing machine doesn't accept any inputs. $H_0$ asks whether a particular input (the empty string) is accepted. BTW, $E_{TM}$ should be co-Turing-recognizable, but not Turing-recognizable.


How to partition disagreeable people into compatible groups

You are essentially asking this:
"Given a graph $G=(V,E)$ where each vertex in $V$ denotes a person and each edge $(u,v) \in E$ means that $u$ is incompatible with $v$, what is the minimum number of colors required to color the vertices of $V$ such that no edge in $E$ has both endpoints of the same color?"

In other words, given any graph $G$ (which can always be realized with a suitable set of incompatibilities), find the chromatic number $\chi(G)$ of $G$.

This is a well-known NP-hard problem. In particular, it is already NP-hard to decide whether $\chi(G) \le 3$.
For the special case of $2$ colors, $\chi(G) \le 2$ can be decided in linear time (just check whether $G$ is bipartite, which also gives you the corresponding coloring if that is the case).

However, since you are just asking for an algorithm (no mention of a polynomial-time complexity or even efficiency) you might as well enumerate all existing colorings in $O(3^{|V|} + \dots + \chi(G)^{|V|}) = O(\chi(G)^{|V|})$ time.
This can be improved to $O(2.2461^{|V|} )$ time, see:
https://epubs.siam.org/doi/10.1137/070683933

Finally, there is simple linear-time greedy algorithm that uses at most $\Delta(G)+1$ colors, where $\Delta(G)$ is the maximum degree of $G$: Examine the vertices of $G$ one at a time, color a vertex with any color that is not already used by any of its neighbors.

This is the relevant Wikipedia page: https://en.wikipedia.org/wiki/Graph_coloring .

EDIT

Your algorithm is iteratively computing maximal independent sets of $G$. Similarly to the greedy algorithm, it will return a coloring with at most $\Delta(G)+1$ colors.
To see this, suppose that there is a vertex $v$ of color (group) $\Delta(G)+2$. Then, since $v$ has not been added to any of the first $\Delta(G)+1$ groups, it must have at least one neighbor in each of those groups. This means that the degree of $v$ is at least $\Delta(G)+1$, a contradiction.

Here is a tight example for both algorithms (vertices are examined in increasing order of their label):


Does a context switch happen when a process has terminated?

Yes, a context switch happens. After P1 ends the state of P2 must be loaded. The only difference with a regular context switch is that the state  of P1 does not need to be saved as it is not needed for a later restore.

Whether the OS actually applies this optimization or simply performs a regular context switch and then later discards the saved context for P1 depends on the implementation.


Find proportion of 'important' edge among all edges in a graph

The problem you asked can be actually generalized to an arbitrary total order $\mathcal{O}$ on the vertices: a vertex $x$ is important iff at least $\frac{1}{3}$ of its neighbors are smaller than $x$ according to $\mathcal{O}$. For the order on degrees we can break the ties arbitrarily, which will only make important vertices and thus important edges less.

We prove it by the adjacency matrix $M$. Suppose the vertices are ordered: $x_1<_\mathcal{O}\cdots<_\mathcal{O}x_n$, where $n=|V|$. Then $M\in\{0,1\}^{n\times n}$ with $M_{i,j}=1$ iff $(x_i,x_j)\in E$. In the rest part of the proof we abuse the notation of $M_{i,j}$ to represent the grid in the matrix $M$, and for a set of grids $S$ we use $|S|$ to denote the number of $1$'s among these grids.

The matrix $M$ is naturally divided into two triangles:
$$L=\{M_{i,j}\mid i>j\},\quad U=\{M_{i,j}\mid i<j\}.$$
Denote the $i$-th row by $R_i$, so $|R_i|=\deg(x_i)$. Now $x_i$ is important iff $|L\cap R_i|\geq \frac{1}{2}|U\cap R_i|$. On the other hand, since $|L|=|U|=|E|$ which means $\sum_i |L\cap R_i|=\sum_i |U\cap R_i|=|E|$, we know
$$\begin{align*}
|E_1|&\geq\sum_i\left\{\,|L\cap R_i|\;\middle|\; |L\cap R_i|\geq \textstyle\frac{1}{2}|U\cap R_i|\,\right\}\\
&=|E|-\sum_i\left\{\,|L\cap R_i|\;\middle|\; |L\cap R_i|<\textstyle\frac{1}{2}|U\cap R_i|\,\right\}\\
&>|E|-\frac{1}{2}\sum_{i=1}^n|U\cap R_i|=\frac{1}{2}|E|.
\end{align*}$$


"Searching and sorting" algorithm to find the natural logarithim of a number?

Suppose you have an array $A = [e^0, e^1, e^2, \dots]$. You do a search in this array, and try to find the biggest value in the array that's smaller than or equal to $x$.

You find this value at position $n$. What is the value of $A[n]$?
What can you say about $\ln(x)$ in relation to $n$?
Can you find the correct $n$ quickly? Does it help that $A$ is sorted?


Is it valid to make an admission of a topological space by a "partial quotient map"?

When we implement a space we do not actually implement the space itself, but rather a representation of it. That is, an implementation of $X$ consists of a datatype $T$ and a partial surjection $\delta : T \to X$, as in Type Two Effectivity. When $\delta(p) = x$ we say that the datatype value $p \in T$ represents or realizes the point $x \in X$. Cruicially, there may be many values that represent the same point. Only $T$ exists in the computer, $X$ and $\delta$ are mathematical objects. A particularly well-behaved kind of representation is an admissible one, as you mention.
In your case, you correctly implemented an admissible representation of the Sierpinski space: $X$ is the Sierpinski space, $T$ is Sierpinski, and the surjection $\delta$ maps $\omega$ to $\bot$ and $\mathtt{Succ}^n \,\mathtt{Zero}$ to $\top$. There is no need for further quotienting.
The attempt to define == on Sierpinski is not about quotienting, but rather trying to define the characteristic map $\mathrm{eq} : X \to \{0,1\}$ of equality as a map into Booleans, which is only possible when the space is discrete. You discovered that the Sierpinski space is not discrete.
If we have a representation $\delta : T \to X$ then we can form the representation of a quotient $Y = X/{\sim}$ as $\delta' : T \to Y$ where $\delta'(p) = [\delta(p)]_{\sim}$. That is, quotienting affects the map but not the datatype.


Dependent type system with different computation model

Yes, realizability theory allows you to model dependent type theory based on a variety of computational models, such as: Turing machines (with or without oracles), various $\lambda$-calculi, topological models of computation, sequential functionals, game-semantics computational models, and many others.

References:

Jaap van Oosten: Realizability: an introduction to its categorical side, Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008
You could also peek in Section 1.1. of my PhD thesis.


Hash function to return only positive number from integer

From your comments, it appears all you need a bijection from $\mathbb{Z}$ to $\mathbb{N}$ that is easy to compute.

The simplest one I can think of: $x \mapsto 1/2 + 2 \mid\!(x - 1/4)\mid$.

This isn't really a hash function: it doesn't "hash" (scatter its consecutive function values across their range).


Recall that the Myhill-Nerode indistinguishability relation $\sim_L$ is defined on the set $\{0,1\}^{*}$ of all inputs as $u \sim_L v$ iff for all $w$, $uw \in L \Leftrightarrow vw \in L$.  The Myhill-Nerode Theorem states that $\sim_L$ has finitely many blocks iff $L$ is regular.

Let $\alpha_i = 1^i0^i1$ for each $i\ge 1$.  I claim that $[\alpha_i]_{\sim_L} = [\alpha_j]_{\sim_L} \Rightarrow i = j$.  Hence $\{[\alpha_i] \mid i=1,2,\dots\}$ forms an infinite subset of the blocks of $\sim_L$.  Therefore $\sim_L$ must have infinitely many distinct blocks, so $L$ cannot be regular.

To prove the claim, suppose that $[\alpha_i]_{\sim_L} = [\alpha_j]_{\sim_L}$ for some $i,j \ge 1$.  Then $\alpha_i \sim_L \alpha_j$, so for any suffix $w$, $1^i0^i1w \in L \Leftrightarrow 1^j0^j1w \in L$.  In particular this must hold for $w=1^j0^j$, and since $1^j0^j11^j0^j \in L$, it must hold that $1^i0^i11^j0^j \in L$.  Hence $i=j$.

(Finding an infinite subset that worked required an odd number of cups of tea.  But using Myhill-Nerode means not having to remember the various pumping lemmas.)

Edit 2015-10-28: was answering the question about $\{xyx\mid x\in\{0,1\}^{+},y\in\{0,1\}^{*}\}$, now fixed.


Let us enumerate the students $s_1, \dots, v_n$. Let $A$ be the set of students and $B$ the set of subjects. Moreover, let $S_i$ be the set of subjects the student $s_i$ likes. The dynamic programming table will be $C\left(A, 2^B\right)$, where $C(s_i, S)$ says in how many ways we can assign the subjects in $S$ to the first $i$ students. Note that if $|S| \neq i$ we have $C(s_i, S) = 0$.

The recursive function is given by the formula $$C(s_i, S_i) = \sum_{p \in S \bigcap S_i} C(s_{i-1}, S\setminus {p}).$$

To implement the solution you need a loop over all the students and for each student iterate over all possible bit masks. For the student $i$ ignore all bitmasks with number of ones not equal to $i$. Now use the formula above to compute the value for each student and bitmask based on the values of previous students.

Notes:

Checking if $M$ contains $k$ by $M \& (1<<k)$
Adding subject $k$ to bitmask $M$ by $M = M | (1 << k)$
Removing subject $k$ from bitmask $M$ by $M = M \& (((1<<n) - 1) - (1<<k))$.


Closest arithmetic progression to an array

Let's call your array $a$. The goal is to find $x,k$ such that $\sum|a_i-(ix+k)|$ is minimized. Fix $x$ and replace $a_i$ by $b_i=a_i-ix$. Now the goal is to minimize $\sum|b_i-k|$, so $k$ is obviously the median of $b$. Since it's not hard to solve this problem with fixed $x$, it's natural to consider if there's any monotonicity on $x$.

Note that the error can be written as $\sum_{b_i\in upper\,half}b_i-\sum_{b_i\in lower\,half} b_i$. Substitute $b_i$ by $a_i-ix$ and we'll get a formula like $c-(\sum_{b_i\in upper}i-\sum_{b_i\in lower}i)x$, which is linear. The optimal $x$ can be found trivially in this case, but the order of $b$ changes when $x$ incerases (decreases). Let's see how it changes.

Scan $x$ from negative to positive. At some points a "swap" may happen: originally $b_i<b_j$ but after this point $b_i>b_j$. This only happens when $i<j$. If they are originally in the same half then nothing happens. But if originally $i$ is in the lower half and $j$ is in the upper half, now $i$ moves to the upper half and $j$ moves to the lower half. This increases the slope by $2(j-i)$. Median should be excluded from both halves if $N$ is odd but the conclusion "slope is increasing" remains.

Now we know the error is a convex function so we can find the minimum by ternary search on $x$. Since we can compute the error in $O(N)$ if we fix $x$ and the range of $x$ is bounded by $O(M)$, the total complexity  is $O(N \log M)$. (Here I consider the cost of each arithmetic operation as a constant.)


Lower bounds for space with some probability of error

In "Network applications of Bloom filters: A survey", Broder and Mitzenmacher show an $x \log_2 (1/p)$ lower bound on the space usage.


Let $\varphi$ and $\psi$ be formulas of propositional logic. We write, as Norvig says, $\varphi\vDash \psi$ iff $M(\varphi)\subseteq M(\psi)$: that is, iff every truth assignment that makes $\varphi$ true also make $\psi$ true. This is the case iff $\vDash \varphi\Rightarrow\psi$, i.e., if the formula $\varphi\Rightarrow\psi$ is true in all truth assignments (is a tautology).

Entailment and implication operate at different levels. An implication is something that may be true or false, depending on which truth assignment you're considering at the moment, whereas an entailment is a statement about all truth assignments.  In particular, the truth of the entailment $\varphi\vDash\psi$ depends only on truth assignments that make $\varphi$ true. If a particular truth assigment makes $\varphi$ false, then it cannot make the entailment false. Similarly, if an assignment makes $\varphi$ false, it cannot make the implication $\varphi\Rightarrow\psi$ false.


Is there a metric for the similarity of two image filters?

The ‘k-translation correlation’ is probably a good candidate for what you are looking for. It measures the maximum correlation between a pair of two filters $\mathbf{W_i}$ and $\mathbf{W_j}$ achieved by translating one filter up to k steps along any spatial dimension and then selecting the maximum thereof:

$$\rho_k(\mathbf{W_i,W_j})=\max_{(x,y)\in \{-k,...,k\}^2\setminus(0,0)} \frac{\langle\mathbf{W_i}, T(\mathbf{W_j}, x,y)\rangle_f}{\left \|  \mathbf{W_i}\right \|_2 \left \|  \mathbf{W_j}\right \|_2}\,,$$

where $T(\cdot, x,y)$ refers to the translation of its first operand by $(x,y)$ and $\langle\cdot,\cdot\rangle_f$ denotes the flattened inner product of the two filters (the second of which is translated). Note that both filters are reshaped to column vectors to perform the inner product. For more details refer to Doubly Convolutional Networks (Zhai, Cheng, Lu, Zhang, in Proceedings of 30th Conference on Neural Information Processing Systems (NIPS 2016)).


Note that
$$
L = \{ a^n b^x c^n d^y : n,x,y \geq 0 \} \cup \{ a^n b^x c^m d^x : n,m,x \geq 0 \}.
$$
Try showing that each of these is context-free individually.


What is the time complexity of this nested loop code?

We just have one comparison when  $n$ is odd. So, the total complexity is (if we suppose $n$ is even, w.l.o.g.):

$$T(n) = \frac{n}{2} + (n + (n-2) + (n-4) + ... + 2) $$
$$= \frac{n}{2} + 2 \sum_{i=1}^{\frac{n}{2}}i = \frac{n}{2} + 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \Theta(n^2)$$


Why CLRS example on residual networks does not follows its formula?

That's not what the formula gives you.  As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$.  Therefore we send 4 units of flow along the augmenting path from $s$ to $t$, namely, the path $s \to v_2 \to v_3 \to t$.  In particular, $f(s,v_2)=8$, $f'(s,v_2)=4$, and $f'(v_2,s)=0$, so the updated flow is $8+4-0=12$.


Halting problem for polynomial space bounded Turing machines

You don't need to know $f$. It is sufficient to use the fact that there are only finite possible configurations.

Given an input $\langle \langle M\rangle,w\rangle$ where $M$ is a polynomially bounded TM, simulate $M$ on $w$ and record its configuration at every step. Whenever we find a repeated configuration, we can assert that $M$ does not halt on $w$.

Note if $M$ does not halt on $w$, it must experience a repeated configuration, so the process described above will always halt. Therefore this process is the decider for the halting problem.


What doest it mean: "computer is an intelligence amplifier"?

Let's first clarify the scenario. What you're basically asking is why it is more likely to randomly write a computer program that outputs the works of Shakespeare than writing the works of Shakespeare directly.

The simple answer to this is that there are many ways to write a program that outputs a fixed string, but only one way to directly write this string. This may sound a bit strange, because there is clearly a mapping from strings that describe a computer program that outputs a string to another string (that is, the string outputted by the described program), and we could interpret a large amount of strings as descriptions of programs that outputs something. So why are the sizes different?

The reason is that these mappings are not bijective: the map from programs to strings outputted is clearly surjective, as we can output any string, but also clearly not injective, as there are multiple programs that output the same string. So, the set of programs must be larger than the set of strings outputted by them. That means if we sample over the set of programs, we need to sample over a much smaller set to get strings of a certain size, than if we were to sample over the strings directly.


Why is Heapsort in O(n log n) if not all n operations take time log n?

$n \log n$ means each $n$ nodes has $\log n$ operation.

No, it does not. That's like saying:

  \$100 means I sold 100 drinks for \$1 each

Obviously, you could have sold any number of things as long as they add up to \$100.

With algorithm costs it's the same. A sequence of operations taking "time" $\Theta(n \log n)$ means that the "time" costs of all the operations add up to something that behaves roughly like $n \log n$.

Once Landau terms enter the pickture, things get muddled. It's tempting to tread $\sum_{i=1}^n O(\log i)$ in the same way as $\sum_{i=1}^n \log i$, but the former sum doesn't really make sense. I recommend you read our reference questions on algorithm analysis and asymptotics to see how one can arrive at the final result here.


Does computability according to Church-Turing thesis include side effects?

The Church-Turing thesis says that Turing machines capture precisely the effectively calculable functions from natural numbers to natural numbers. It says little about what happens when we attach a robotic arm to a computer.

Any kind of machine needs to represent numbers in some way, obviously since numbers are abstract entities. A Turing machine represents them with 0's and 1's written on a tape. In $\lambda$-calculus we represent them with Church numerals. If we attached a robotic arm to an iPhone, we could represent them with a suitable number of up-down movements by the arm. The question of representation is separate from the question of side effects. In particular, the question of what can be computed is separate from how the results can be communicated. Lamenting about the fact that $\lambda$-calculus has no input/output, for instance, would be misguided.

There is a well understood theory of computational side effects. According to this theory, Turing machine have certain side effects. They carry state in their cells, that is a side effect. We can implement quoting on Turing machines, that is the side effect which converts a closure to source code. Turing machines with oracles can be seen as having the "input" side effect (known as a reader monad in functional programming).

In summary, the Church-Turing thesis is largely independent of what computational effects might be present in the computational model. This is so because the Church-Turing thesis is about numer-theoretic functions, not about how computers interact with their environment.


In the "tall cache assumption" what does $\Omega$ represent?

It's the lower bound counterpart to O($\cdot$). Z is larger than some constant times $L^2$


The process that you've described happens only if interrupts are enabled. The IRQ request (via INTR line) asks the CPU to handle the interrupt. If the CPU accepts, it will issue an INTA as you describe.
The CPU doesn't always accept interrupts. For instance, if the CPU is "in the middle of something", then it might delay handling the interrupt (for instance, until the instruction which is currently being executed, finishes). Additionally, the CPU has an internal flag that indicates whether or not is should accept interrupts. In the x86 family, this is the IF (interrupt flag), and you can control it by the commands STI (set interrupt flag == enable accepting interrupts) and CLI (clear interrupt flag == disable accepting interrupts). In other CPUs the naming might be different or there might be a more sophisticated mechanism setting/clearing interrupts of specific type/priority.
If the IF is cleared and interrupts are disabled, the CPU just "ignores" the input INTR line. This is known as masking interrupts. The CPU just continues as if the INTR line is low... Once you set the IF, then the CPU will stop ignoring the interrupt and will handle it according to the standard procedure (save flags and return address, and jumps to the ISR, issuing INTA, etc.)
Just to make it clear, enabling/disabling interrupt does not change the way the external I/O creates the interrupt. It just changes the way the CPU behaves in case of an external interrupt: if enabled, the interrupt is processes. If disabled/masked, interrupts are ignored.


Why quicksort instead of a B-tree construction?

A B-tree has one significant disadvantage on the fastest deep cache machines, it depends on pointers. So as the size grows each access have a greater and greater risk of causing a cache-miss/TLB-miss.
Effectively getting a K value of z*x, x=sum(cache/TLB-miss per access, L1-TLB misses are typically size of tree / total cache size), z ~= access time of least cache or main memory that can hold the entire tree.

On the other hand the "average case" quicksort streams memory at maximum pre-fetcher speed. Only drawback here is the average case also cause a stream to be written back. And after some partitions the entire active set sit in caches and will get streamed quicker.

Both algorithms suffers heavily from branch mis-predictions but quicksort, just need to backup a bit, B-Tree additionally needs to read in a new address to fetch from as it has a data dependency which quicksort doesn't.

Few algoritmes are implemented as pure theoretically functions. Nearly all have some heuristics to fix their worst problems, Tim-sort excepted as its build of heuristics.

merge-sort and quick-sort are often checked for already sorted ranges, just like Tim-sort. Both also have an insertion sort for small sets, typically less than 16 elements, Tim-sort is build up of these smaller sets.
The C++ std::sort is a quicksort hybrid with insertion sort, with the additional fallback for the worst case behaviour, if the dividing exceed twice the expected depth it changes to a heap-sort algorithm.

The original quicksort used the first element of the array as pivot, this was quickly abandoned for a (pseudo)random element, typically the middle. Some implementations changed to median-of-three (random elements) to get a better pivot, recently a median-of-5-median (of all elements) was used, and last I saw in some presentation from Alexandrescu was a median-of-3-medians (of all elements) to get the a pivot that was close to the actual median (1/3 or a 1/5 of the span).


Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem

$X$ doesn't exist (unless $P = NP$ in general) because your description is self-contradictory. You claim it is NP-hard, yet its input domain can be split in a finite number of disjoint poly-time solvable problems. This makes it $P$.
The idea of executing these algorithms in parallel adds nothing. Even on a single machine you can run N programs 'simultaneously' by distributing computational time in a round-robin fashion, leading to an overhead factor of N to any single program. Set N to be equal to your number of algorithms (which was, by your description, a finite constant), and you end up with a poly-time algorithm.


Max flow algorithm for floating-point weights and E~=10*V

Orlin's algorithm can solve max flow in sparse graphs in $O(|V| |E|)$ time.  See

Max flows in O(nm) time, or better.  James B. Orlin. STOC 2013.

You'll have to decide whether the potential speedup is worth the time to implement it, as I believe the algorithm is quite complex.  I don't know whether the algorithm is better in practice.

Perhaps someone else will have better suggestions for you.


Definition of “infix” in formal languages

Yes, if $A$ is the alphabet, then $L = A^*aabA^*$.

Now, what about terminology?
Lothaire in the first chapter of his book Combinatorics on words gives the following definitions. A word $v \in A^*$ is said to be a factor of a word $x \in A^*$ if there exist words $u, w \in A^*$ such that $x = uvw$. A factor is proper if $v \not= x$.

In my opinion, the word infix is also perfectly fine, since it gives a natural counterpart to prefix and suffix. Terms involving "sub" like subword and substring are also frequently used in the literature. I personally prefer to follow Lothaire and say that a word $v \in A^*$ is a subword of a word $x \in A^*$ if $v = a_1a_2 \cdots a_n$ (where $a_i \in A$ and $n \geqslant 0$) and there exist $y_0, ..., y_n \in A^*$ such that $x = y_0a_1y_1a_2 \cdots a_ny_n$. This definition makes the term subword a synonym of subsequence, which I find quite natural.

Anyway, with so many different terminology around, it is not a bad idea to remind the reader of precise definitions if there is any risk of ambiguity...


Longest Even-Length Palindromic Subsequence (with distinct adjacent characters except for the center 2 letters)

Golden Rule
Here is the golden rule of dynamic programming.
When solutions to smaller subproblems cannot be combined into solutions to larger subproblems because of missing information, extend the subproblems by adding parameters that give that missing information.

First attempt
$S$ is a sequence of $n$ letters or, $S[0:n].$
Let $L[i][j]$ be the length of the longest palindromic subsequence of $S[i:j]$. It is easy to figure out the base cases and, by increasing $i$  and/or decreasing $j$, the recurrence relations for $L[i][j]$.

Now add the condition of even length. Let $E[i][j]$ be the length of the longest even-length palindromic subsequence of $S[i:j]$. We can figure out the base cases and the recurrence relations for $E[i][j]$, similar to those of $L[i][j]$.
Now add the condition of distinct adjacent letters, i.e., no letter can appear twice in a row except the letter at the center. Let $D[i][j]$ be the length of the longest even-length distinct-adjacent-letter palindromic subsequence of $S[i:j]$. As you might have noted, we cannot figure out the recurrence relations for $D[i][j]$, since extending such a subsequence to a longer one might introduce repeated letters.
The golden rule comes to rescue. Add another parameter that classifies the letter at the end of the longest subsequence found so far, so that we can determine how to extend that subsequence properly.
Let $D[i][j][\lambda]$ be the length of the longest even-length distinct-adjacent-letter palindromic subsequence of $S[i:j]$ that ends in letter $\lambda$. That is, we will compute $D[i][j][\text{'}a\text{'}]$, $D[i][j][\text{'}b\text{'}]$, $D[i][j][\text{'}c\text{'}]$, $\cdots$, $D[i][j][\text{'}z\text{'}]$.

The final answer is the larger of $\max_\lambda D[0][n-1][\lambda]$ and $0$.

Suppose the first $\text{'}a\text{'}$ in $S$ at or after $S[i]$ appears at $S[\vec {i_{\text{'}a\text{'}}}]$. Suppose the first $\text{'}a\text{'}$ in $S$ appears at $S[\overleftarrow{j_{\text{'}a\text{'}}}]$ before $S[j]$ searched backwards. $\vec {i_{\text{'}a\text{'}}}$ or $\overleftarrow{j_{\text{'}a\text{'}}}$ is set to $-1$ if $\text{'}a\text{'}$ is not found respectively. We have, for $j\ge i+2$,
$$D[i][j][\text{'}a\text{'}] =  \begin{cases}
\max(2, 2 + \max_{\mu\not=\text{'}a\text{'}}D[\vec {i_{\text{'}a\text{'}}}+1][\overleftarrow{j_{\text{'}a\text{'}}}][\mu])& \text{ if } 0\le \vec{i_{\text{'}a\text{'}}}  \lt \overleftarrow{j_{\text{'}a\text{'}}},\\
 -1 &  \text{ otherwise,}\\
\end{cases} $$
where $\mu$ runs through all lowercase English letters.

The base case is $$D[i][i][\text{'}a\text{'}] = 0.$$

Generalizing $\text{'}a\text{'}$ to variable $\lambda$, we can write the recurrence relation and base case for $D[i][j][\lambda]$.
Note that with the extra information embodied in the $\lambda$ parameter, it is easy to deduce the recurrence relation.
While this attempt is successful, we can do better.

Second attempt
We can simplify the subproblems.
Let $F[i][j]$ be the length of the longest such subsequence that starts at $S[i]$ and ends at $S[j]$. Then we have
$$F[i][j] =  \begin{cases}
\max(2, 2 + \max_{\mu\not=S[i]}F[\vec{i_\mu}][\overleftarrow{j_\mu}])&\text{ if } S[i] = S[j],\\
 -1 & \text{ otherwise,}\\
\end{cases} $$
where $-1$ stands for "Not Found". For all lowercase English letter $\mu$, $S[\vec{i_\mu}]$ is the first $\mu$ that appears after $S[i]$, and $S[\overleftarrow{j_\mu}]$ is the first $\mu$ that appears before $S[j]$ searched backwards.  If one of them cannot be found, the term $F[\vec {i_\mu}][\overleftarrow{j_\mu}]$ is ignored.
The final answer is the larger of $\max_{i, j} F[i][j]$ and 0.


Right as far as it goes, but the differences aren't that clear cut. E.g. in Linux (quite monolithic) you'll find FUSE (Filesystems in USErspace). In Unix (monolithic) the graphics system is X, and that one (while userspace) is (or was) granted direct access to interrupts and I/O under Linux at least. It is quite common to have IPC in userspace, while in Windows (was once a microkernel, now a strange hybrid) it is completely part of the sort-of microkernel.

Just for laughs, a while back the "monolithic" Linux kernel was smaller than the Mach "microkernel" alone...


Lets recall that input for flow problems is a graph with capacities on their edges. Let $G(V,E)$ where $V$ denotes the vertex set of the graph and $E$ denotes the edge set. Let $f_{\text{max}}$ denote the maximum possible flow. It is an easy caluclation that input size is $\mathcal{O}(V+E \log (f_{\text{max}}))$ bits as  writing $f_{\text{max}}$ takes $\mathcal{O}(\log f_{\text{max}})$ bits. Since $f_{\text{max}}$ may be arbitrarily high (it depends neither on $V$ or $E$), this running time could be arbitrarily high, as a function of $V$ and $E$.

A algorithm is said to  have a polynomial runnning time if its runtime in input size in bits where as pseudo-polynomial runtime means runtime of the algorithm is polynomial in numeric value of the input (see Pseudo-polynomial time)


You're right, {b, d, e} should be a final state. Otherwise the DFA would reject 0001 while the "equivalent" NFA accepts it.


Parallelization of an iterative function application

A good starting point is the Wikipedia article on Prefix Sums.  A particularly good source is Guy Blelloch's article about Prefix Sums.

The idea is this: if you have an associative operator (e.g., "+"), you can turn a long dependent chain of those operators into a tree that is more balanced.

For the example you gave, $f(x,y,z) = x + (y-x)/(z+1)$ we can actually generalize to an entire class of problems.
$$
\begin{array}{rcl}
x_{i+1} & = & x_i + (y_{i+1}-x_i)/(z_{i+1}+1)                                     \\
        & = & \frac{y_{i+1}}{z_{i+1}+1} + \frac{x_i (z_{i+1}+1) - x_i}{z_{i+1}+1} \\
        & = & \frac{y_{i+1}}{z_{i+1}+1} + \frac{z_{i+1}}{z_{i+1}+1} x_i           \\
        & = & a_{i+1} + b_{i+1} x_i\mathrm{,}
\end{array}
$$
where the $a_i$ and $b_i$ can be calculated completely in parallel.  So the calculation looks like:

Ok.  So let's look at a few iterations starting at $x_i$ through $x_{i+3}$:
$$
\begin{array}{rcl}
x_{i+2} & = & a_{i+2} + b_{i+2} x_{i+1}                                        \\
        & = & a_{i+2} + b_{i+2} (a_{i+1} + b_{i+1} x_i)                        \\
        & = & (a_{i+2} + a_{i+1} b_{i+2}) + b_{i+2}b_{i+1} x_i                 \\
x_{i+3} & = & a_{i+3} + b_{i+3} x_{i+2}                                        \\
        & = & a_{i+3} + b_{i+3} (a_{i+2} + a_{i+1} b_{i+2} + b_{i+2}b_{i+1}x_i)\\
        & = & (a_{i+3} + a_{i+2}b_{i+3}  + a_{i+1}b_{i+3}b_{i+2}) + b_{i+3}b_{i+2}b_{i+1}x_i\\
        & = & A_{i+1,i+3} + B_{i+1,i+3}x_i
\end{array}
$$

and so on.  The interesting thing is that we can calculate $x_{i+k}$ as $A_{i+1,i+k} + B_{i+1,i+k}x_i,$ where large chunks of computation can be summed up independently in the $A_{i+k}$ and the $B_{i+k},$ without knowing $x_{i+1}, \cdots, x_{i+k-1}.$

Now let's chunk up the work of calculating the $x_i$'s.  Here's what it might look like if we divided the calculation up into 4 equal parts and put each part on a different thread:

So each thread works completely independently to calculate the $A_i$ and $B_i$.  Then we have a final (sequential) phase where we calculate $x_{n/4}, x_{2n/4}, x_{3n/4},$ and $x_n$.

As Guy Blelloch's article shows, you can actually calculate all the partial sums with one last step, if you need them.


If you found Structure and Interpretation of Computer Programs interesting, you might like Functional Differential Geometry (It's from the same authors) .

Differential geometry is deceptively simple. It is surprisingly easy to get the right answer with unclear and informal symbol manipulation.  To address this problem we use computer programs to communicate a precise understanding of the computations in differential geometry.  Expressing the methods of differential geometry in a computer language forces them to be unambiguous and computationally effective. The task of formulating a method as a computer-executable program and debugging that program is a powerful exercise in the learning process.  Also, once formalized procedurally, a mathematical idea becomes a tool that can be used directly to compute results.

Taken from Sussman, Wisdom: Functional Differential Geometry


First of all I think that the direction of the reduction of your question is from Hampath to Hamcycle (you prove the NP-hardness of Hamcycle reducing the NP-complete problem Hampath to it).

Now given an instance of Hampath: $G,s,t$:

1) there is an edge between $s$ and $t$
2) there is not an edge between $s$ and $t$

In both cases the extra node $u$ is needed in order to force $s,u,t$ to be consecutive nodes in  the Hamiltonian cycle.

The new graph $G'$ with a new node $u$ and new edges $(s,u), (u,t)$ (in the first case you split the original edge) will have an Hamiltonian cycle iif the original graph $G$ has an Hamiltonian path from $s$ to $t$.

You can "play" with these two graphs:


A simple clarification on $\#P$ closure properties

Yes, that's exactly what it means. Closure under addition can also be phrased as follows: if $f(x)$ and $g(x)$ are $\#P$ functions, then $h(x)=f(x)+g(x)$ is also a $\#P$ function. As an exercise: How do you construct the machines $N_+$ and $N_\times$? Check that these definitions mean the same. $\#P$ has extraordinary closure properties, for example if $f\in \text{FP}$ and $p\in\#P$ then

$$\sum_{y=0}^{f(x)}p(y)$$

is also a $\#P$ function. We say that $\#P$ is closed under exponential sums.

In general, to say that some set $O$ is closed under an operation $\triangle$, means that if you take $a,b\in O$, then $a\triangle b\in O$. In other words, you can't "get out of $O$" by applying $\triangle$ to elements inside $O$. For example, $NP$ is closed under set intersection, because $L,K\in \text{NP}\implies L\cap K\in\text{NP}$ (why?).


Is my simplified explaination of the XOR swap correct?

Your proof is correct in intention, but the style is not adequate.

Of course, there is no perfect style, and most of us could improve
their style, myself included.

Still, hoping readers will not be too harsh, here is an attempt at
writing it, as an example, following your own proof. It may be too
verbose, one of my own failings. (it is also a bit intentional here)

Actually the style usually depends also on the audience you are addressing. If the intended audience is very competent in the field, you can skip a lot of details. Nevertheless, careful notation always helps (like the indexing $a_0$ below).

The XOR swap is a well-known in-place algorithm to swap two values, by
XOR:ing them bitwise. It goes as follows for two variables a and b, using the notation of the C programming language:

a = a^b

b = a^b

a = a^b

Correctness proof

We note the XOR operation $\oplus$ as is common in mathematical uses. This notation is justified by the isomorphism between XOR on the booleans and the addition in $\mathbb{Z}/2$.

The algebraic properties of XOR extend to bitwise operations on bit
vectors (i.e., sequences of bits) of equal sizes. In particular it
remains associative and commutative, and we have for any sequence $x$
of bits: $x\oplus x=\vec{0}$ where $\vec{0}$ is a bit vector of $0$´s of the
same length, and $x\oplus\vec{0}=x$.

Assume the initial values of a and b are respectively $a_0$ and
$b_0$.

The 3 assigments above are then equivalent to:

a =$a_0\oplus b_0$

b =$(a_0\oplus b_0)\oplus b_0$   which simplifies algebraically to $a_0$ as indicated above

a =$(a_0\oplus b_0)\oplus a_0$   which simplifies to $b_0$

The initials values of a and b have been swapped bitwise. $\;\Box$

Though I may be in some disagreement over this with other users, I do not
see the usefulness for this proof of insisting on the relation between
XOR and addition (other than for justifying the notation). Of course,
the generalized view of Yuval Filmus]1 brings wider understanding, but
the point for me is to have a simple proof, not to write a treatise.

Note that I have been using distinct notation for syntax (taken fron
C) and for the semantics of these operations. This justifies having
two notations for the XOR operator, and gives a cleaner presentation
of the proof, which may sometimes be important.

Of course, one is not always that careful, but it is better to have
these principles in mind, without overdoing it, depending on the
purpose and audience of what is being written. I think the most important here was to distinguish a and $a_0$.

Hoping this version will satisfy most readers. Further comments welcome.

With my thanks to all for all the very useful comments. Perfection is not of this world.


Solving a recurrence relation with √n as parameter

In your comment you mentioned that you tried substitution but got stuck. Here's a derivation that works. The motivation is that we'd like to get rid of the $\sqrt{n}$ multiplier on the right hand side, leaving us with something that looks like $U(n) = U(\sqrt{n}) + something$. In this case, things work out very nicely:

$$\begin{align}
T(n) &= \sqrt{n}\ T(\sqrt{n}) + n & \text{so, dividing by $n$ we get}\\
\frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 &\text{and letting $n = 2^m$ we have}\\
\frac{T(2^m)}{2^m} &= \frac{T(2^{m/2})}{2^{m/2}} + 1
\end{align}$$
Now let's simplify things even further, by changing to logs (since $\lg \sqrt{n} = (1/2)\lg{n}$). Let
$$\begin{align}
S(m) &= \frac{T(2^m)}{2^m} & \text{so our original recurrence becomes}\\
S(m) &= S(m/2)+1
\end{align}$$
Aha! This is a well-known recurrence with solution
$$
S(m)=\Theta(\lg m)
$$
Returning to $T(\,)$, we then have, with $n=2^m$ (and so $m=\lg n$),
$$
\frac{T(n)}{n} = \Theta(\lg\,\lg n)
$$
So $T(n) =\Theta(n\,\lg\,\lg n)$.


Backus Normal Form does not define special syntax for %token.  So that would be a special syntax custom-added by a particular person or web page or tool.  Tool support is off-topic here, but if search for "%token" on the first link you gave, you'll find a brief explanation that appears to describe what %token means in the context of that particular example.

In other words: if you only want to understand BNF at a conceptual level, ignore it.  That's something that's not part of BNF, but is an add-on that was added for some special purpose.  If you want to understand that the specific syntax used by some specific tool (e.g., YACC), your best source is probably the reference manual for that tool.


Big O notation: removing big O from denominator

Let's start out simple:

$${1 \over 1 + x} = 1 - x + x^2 - \cdots$$

so it follows that

$${1 \over 1 + O(x)} = 1 + O(x)$$

as $x \to 0$.

(Background: I interpret $O(x)$ as representing any function $f(x)$ where $|f(x)|$ is asymptotically no larger than $x$, i.e., there exist constants $c_0,x_0$ such that $|f(x)| \le c_0 |x|$ for all $-x_0 \le x \le x_0$.  This is the likely meaning of big-O notation in this context, where we are concerned about the asymptotic behavior as $x \to 0$ and where values can be either positive and negative.   If it looks a little different from what you are used to in computer science, that's because in CS we most commonly deal with the situation where we have a function $f(n)$ where $n \to \infty$ and where all values are positive, so the definition looks a bit different in that context.)

Now suppose $v=O(1)$, and take a more complex expression:

$${1 \over 1 + v + O(x)} = {1 \over 1+v} \cdot {1 \over 1 + O(x)} = {1 \over 1+v}(1 + O(x)) = {1 \over 1+v} + O(x),$$

where I have used that $v \cdot O(x)=O(x)$, etc.

Finally, if $u=O(1)$, we can multiply both sides by $1+u$ to see that

$${1+u \over 1+v+O(x)} = {1+u \over 1+v} + O(x).$$

Now plug in $x=\xi^3$ and $u = \xi$ and $v = -\frac12 \xi + \frac13 \xi^2$, and we obtain

$$
\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2+\mathcal{O}(\xi^{3})}=\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}+\mathcal{O(\xi^3)}
$$

which is the step of the derivation you are asking about.


What is the time complexity for getting the size of a heap?

If you're talking about an ADT, you can't really say. It depends on the implementation. You can certainly do it in O(1) (for example by keeping a counter).


Is the complement of { ww | ... } context-free?

It's context-free. Here's the grammar:

 $S \to A | B|AB|BA$
 $A \to a|aAa|aAb|bAb|bAa$
 $B \to b|aBa|aBb|bBb|bBa$

$A$ generates words of odd length with $a$ in the center. Same for $B$ and $b$.

I'll present a proof that this grammar is correct.  Let $L = \{a,b\}^* \setminus \{ww \mid w \in \{a,b\}^*\}$ (the language in the question).

Theorem. $L = L(S)$.  In other words, this grammar generates the language in the question.

Proof.  This certainly holds for all odd-length words, since this grammar generates all odd-lengths words, as does $L$.  So let's focus on even-length words.

Suppose $x \in L$ has even length.  I'll show that $x \in L(G)$.  In particular, I claim that $x$ can be written in the form $x=uv$, where both $u$ and $v$ have odd length and have different central letters.  Thus $x$ can be derived from either $AB$ or $BA$ (according to whether $u$'s central letter is $a$ or $b$).  Justification of claim: Let the $i$th letter of $x$ be denoted $x_i$, so that $x = x_1 x_2 \cdots x_n$.  Then since $x$ is not in $\{ww \mid w \in \{a,b\}^{n/2}\}$, there must exist some index $i$ such that $x_i \ne x_{i+n/2}$.  Consequently we can take $u = x_1 \cdots x_{2i-1}$ and $v = x_{2i} \cdots x_n$; the central letter of $u$ will be $x_i$, and the central letter of $v$ will be $x_{i+n/2}$, so by construction $u,v$ have different central letters.

Next suppose $x \in L(G)$ has even length.  I'll show that we must have $x \in L$.  If $x$ has even length, it must be derivable from either $AB$ or $BA$; without loss of generality, suppose it is derivable from $AB$, and $x=uv$ where $u$ is derivable from $A$ and $v$ is derivable from $B$.  If $u,v$ have the same lengths, then we must have $u\ne v$ (since they have different central letters), so $x \notin \{ww \mid w \in \{a,b\}^*\}$.  So suppose $u,v$ have different lengths, say length $\ell$ and $n-\ell$ respectively.  Then their central letters are $u_{(\ell+1)/2}$ and $v_{(n-\ell+1)/2}$.  The fact that $u,v$ have different central letters means that $u_{(\ell+1)/2} \ne v_{(n-\ell+1)/2}$.  Since $x=uv$, this means that $x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2}$.  If we attempt to decompose $x$ as $x=ww'$ where $w,w'$ have the same length, then we'll discover that $w_{(\ell+1)/2} = x_{(\ell+1)/2} \ne x_{(n+\ell+1)/2} = w'_{(\ell+1)/2}$, i.e., $w\ne w'$, so $x \notin \{ww \mid w \in \{a,b\}^*\}$.  In particular, it follows that $x \in L$.


When you have a collection of rules, an inversion lemma lets you prove the premises of a rule from the conclusion. You can't just assume that inversion is true. You have to prove it by rule induction. However, classes will often give it to you because it is often tedious and easy to prove. The reason inversion doesn't always work is that there may be multiple rules which match the conclusion you are trying to use inversion on, and then you only know that the premises of one of those rules is true, but not which rule.


Divide and Conquer majority element algorithm

It's not correct. On input [a a b c], the left side yields [a, 2], the right side yields [nil, 1]. They would be merged into [a, 2].

I'll outline a linear time solution. If there exists a value $x$ such that more than $n/2$ of the elements of $A$ have value $x$, then certainly the $n/2$-th order statistic of $A$ must be $x$. The selection problem is solved in linear time using, for example, median of medians; checking that such value does indeed appear at least $n/2$ times is trivially linear time.


Conversion from base $b^k$ to base $b^l$ can be done by reading the original number in chunks of length $\mathrm{lcm}(k,l)/k$, and converting each such chunk into $\mathrm{lcm}(l,k)/l$ digits in the new base. For fixed $b,k,l$, this is linear time.

There is a non-trivial algorithm for base conversion in time $O(M(n)\log n)$, where $M(n)$ is the time it takes to multiply two $n$-bit numbers, $n$ is the length of the number (in digits), and the two bases are fixed. See for example page 14 of these notes by Brent.

The question you are asking is, for fixed $b_1,b_2$ which cannot be written in the form $b^k,b^l$, whether there exists a linear time algorithm for converting from base $b_1$ to base $b_2$. One possible approach to show that this is impossible might be by reducing multiplication (or any other equivalent operation, such as division) to base conversion for some fixed constant bases -- but it's not clear if it is in fact possible to build such a reduction or not. I don't believe the question has been asked in the literature.


How to use Parikh's Theorem to show language is not context free

If $L$ were context free, then the set
$$ H = \{(m,n) : m > n\} \cup \{(m,n) : m \leq n \text{ and } m \text{ is prime}\} $$
would be semilinear. The set $\{(m,n) : m \leq n\} = \mathbb{N} (1,1) + \mathbb{N} (0,1)$ is also semilinear. The intersection of semilinear sets is also semilinear, so the set
$$ H' = \{(m,n) : m \leq n \text{ and } m \text{ is prime}\} $$
is also semilinear. The projection of a semilinear set is semilinear, and so the set of primes is semilinear. But one-dimensional semilinear sets with asymptotic density zero are finite, whereas the set of primes is an infinite set with asymptotic density zero.


LOGSPACE in different Turing Machine variants

Let T(n) be the time complexity of problem on two tapes Turing machine then time complexity on single tape Turing machine is going to $O(T(n)^2)$ (more precisely $10 \times T(n)^2$). You have mentioned that your problem is in $LOGSPACE$, So $T(n)$ will be going to be some polynomial in $n$. To simulate two tapes Turing machine by single tape encode locations 1,3,5,7... to encode the first tape and locations 2,4,6... to encode second tape and also use symbol for the encoding of head positions. Now to simulate the one movement of two tape Turing machine you need to first find the head position (swap left to right) so you need $O(T(n))$ steps. Now to simulate the $O(T(n)$ many steps you need $O(T(n)^2)$ time.


No, not equivalent and not redundant.

Consider $p$ being true if and only if $j$ is even.  $\mathbf{G}p$ is not true (obviously, since $p$ is false in every odd state), but $\mathbf{GF}p$ is always true.


Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

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

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


Necessity of convolution operations for product of two polynomials via brute force method

In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c_k = \sum_{i=0}^k a_i b_{k-i} \right)$ which takes $\mathcal{\Theta}(n^2)$ time.

That's not what it says. It says firstly that convolution is equivalent to polynomial multiplication (i.e. an algorithm for convolution is also an algorithm for polynomial multiplication and vice versa); and secondly that

  The direct approach is to compute all $c_k$ using the formula above

and that this approach has complexity $\Theta(n^2)$. The FFT approach calculates a convolution (and indeed, the continuous Fourier transform produces a convolution of two functions: the convolution of two coefficient sequences is a discrete analogue).


Finding corresponding node in a duplicate binary-tree

I'm not going to provide a code example.
Your approach would work, and takes time proportional to the size of the tree (i.e., its number of vertices) in the worst-case. This can be improved to only take worst-case time proportional to the depth of the vertex of interest.
If the tree is balanced, there would be an exponential difference in the running times.

Keep track of the path from the node of interest to the root $r$ of Tree $A$. In particular, for each node  $x \neq r$ of the path, push into a stack $S$ either $L$ or $R$ depending whether $x$ it is the left or right child of its parent.

Then, start from the root of Tree $B$, iteratively pop from a value $y$ from $S$ and move to the left or right child depending on whether $y=L$ or $y=R$, respectively. The node you're at when the stack is empty is exactly the node you're looking for.


Converting any computable function into a sequence of additions

I don't quite see the connection between the preamble and the question.

Regarding the three fundamental operations, this is of course an arbitrary selection. On one hand, you could say that the most fundamental operation is the unary successor function $x \mapsto x+1$. On the other hand, you have hyperoperations, some of them occurring naturally in Ramsey theory and combinatorial pseudorandomness.

Regarding your actual question, the answer is plainly no. No finite sequence of addition operations can compute the function $(x,y) \mapsto xy$, for example. Indeed, the output of any given sequence of additions on inputs $x,y$ is $O(x+y)$, which grows too slowly.

This is a special instance of a more general theorem about nested bounded iteration, which states that a function $f(n)$ can be computed using $m$ nested bounded loops iff it is recursive and eventually bounded by $A(n,m)$ (the binary Ackermann function). This is part of the circle of ideas around primitive recursive functions.


Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine

A Turing machine is a computation model in theory only, able to simulate any computer algorithm. By formally defining this model mathematically, Its possible to draw conclusions and limits regarding the abilities of our computers.

There are many more models, and much more literature about each of them, but below is a short review of the three mentioned in your question

Deterministic Turing Machine (DTM):

For any given state $Q_i$ the machine is presently at, and for any given symbol under the input alphabet $\Sigma$ the head is at, there is exactly one action the machine can perform.

It means in every step, the transition (and write operation) is well established, or deterministic, under a certain set of rules predefined into the machine.

Non-Deterministic Turing Machine (NTM):

A machine like the DTM, with the important exception that in every step, it may make more than one transition. So for input symbol $s$ and state $Q_i$, it may transition to to $Q_j$, but it may also transition to $Q_k$ and so forth.

Since in no step is the transition well established, we say the NTM "guesses" the best transition that eventually leads to an accepting state $Q_{F}$ (if such a transition path exists).

Imagine being in a maze, and constantly having to decide whether to turn left, or right. If you always guessed the correct choice, then you will find the find the quickest way out possible (if there was one).

Probabilistic Turing Machine (PTM):

A machine like the NTM, only its transition is subject to a probabiliy function (that is well established) and not "guess" like the NTM. For example, suppose the current input symbol is $s$ and state $Q_i$, a transition can be defined as follows:

Flip 2 coins.

If the result is ($head$, $head$), move to state $Q_j$
Else, move to state $Q_k$

Unlike the DTM, we cannot say we know how the machine will act given the situation, since we don't know what the coin flip will show. However, its also not as "lucky" as the NTM, and we can often measure accurately the probability of a mistake.

Further reading on probabilistic classes:

Randomized polynomial time class

Bounded error polynomial time class


Are IEEE floating point numbers intervals or point values?

That has been long established. Most IEEE 754 floating point numbers represent exactly one real number. The exceptions are +0 and -0, +Inf and -Inf, and NaN with special meanings.

If you tried to claim that IEEE 754 floating point numbers did represent intervals, then you would run into deep, deep trouble when you try to define floating-point arithmetic.


What all can be said when you say that the CPU is 32 bit?

An $n$-bit processor is a processor for which the preferred integer size is $n$ bits.  That's usually the size of the integer or general purpose registers (a processor may not have exposed registers in its ISA, a processor may have some other kind of registers of different width, a processor may provide instructions to do some integer operations on different -- smaller or wider -- width, the width of buses used in the ISA implementation do not define its architectural width: there may be several implementations using buses of several sizes).

Data of that size is usually called a word, but when an ISA exist as a family and is extended to provide wider registers, the term word tend to continue to refer to data of the width adequate for the first member of the family (thus the continued use of word to refer to 16-bit quantities in the x86 world which has grow now to a 64-bit ISA).

The address space size is determined by the ISA width only if the ISA is using the same registers for address computation as for integer one.  That's a very common property of later architectures, but it has not always be the case (the 8086 used 24-bit addresses but its word size was 16 bits, Cray had 64-bit data register but its address registers were 24 bits IIRC).  Even when the registers used are the same, the amount of addressable memory may be different, either because some bits are not used for addresses (the 68000 for instance, and programmers making use of that caused issues for their followers when all of the bits were token into consideration), or because virtual memory allows for a process $n$-bit addressable space to be mapped into a wider physical address space (you could consider the 24-bit address of the 8086 a special case of that).


You can reduce addition to a circuit with XOR, AND, OR gates.

Each element of the sum must first be ANDed with an extra variable that is true if the element belongs to the subset, and false otherwise.

Then the circuit can be trivially reduced to 3-SAT. The clauses are determined by the gates.

For example each AND gate (A & B = C) requires these 4 clauses:

(A | !B | !C)

(!A | B | !C)

(A | B | !C)

(!A | !B | C)

Why? Because:

false & true != true

true & false != true

false  & false != true

true & true != false

Each clause eliminates one impossible situation for the gate.

Then if you want the result of the sum to be zero, you add one unit clause for each bit of the result.


How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications?

Here is a proof in the real case. For general fields, this only gives a lower bound of $\lceil n/2 \rceil$, though the correct lower bound should indeed be $n$. For more, take a look at the monograph Algebraic complexity theory by  Bürgisser, Clausen and Shokrollahi.

Model

It will be easier to give a lower bound on computing the inner product of a vector with itself; this is a potentially easier task. Consider an arithmetic "straight-line" program for computing the squared norm $\sum_{i=1}^n x_i^2$. Such a program consists of the following operations: addition, subtraction, multiplication, division, all of which of the form $a \gets b \circ c$. We are also allowed to "load" input variables and arbitrary field constants. The final answer must be found in some variable. Since we don't care about space, we can assume that every operation assigns its output to a new variable.

For simplicity we will not allow division in what follows, though divisions can always be eliminated (this is a famous result of Strassen), without too much trouble.

Here is an example of such a program:

  $t_1 \gets x_1 \cdot x_1$

  $t_2 \gets x_2 \cdot x_2$

  ...

  $t_n \gets x_n \cdot x_n$

  $s_2 \gets t_1 + t_2$

  $s_3 \gets s_2 + t_3$

  ...

  $s_n \gets s_{n-1} + t_n$

The variable $s_n$ contains the inner product.

Normal form (1)

The first step is coming up with a program in normal form. Let $t$ be a variable occurring in the program. The value of $t$ is always a fixed polynomial in the inputs (if we allowed divisions, it could be a more general power series). We write $t$ as a sum $t = t^{(0)} + t^{(1)} + t^{(2)} + t'$, where

$t^{(0)}$ is a constant.
$t^{(1)} = \sum_i c_i x_i$.
$t^{(2)} = \sum_{i \leq j} d_{ij} x_i x_j$.
$t'$ consists of all monomials of degree larger than 2.

We will convert an arbitrary program into one which computes only the parts $t^{(0)},t^{(1)},t^{(2)}$, and furthermore contains no more "essential" multiplications than the original program; a multiplication is not essential if one of the operands is a constant. Since the output variable $o$ satisfies $o = o^{(2)}$, the new program also computes the squared norm.

The base cases are when $t$ is constant or an input variable. In both cases no computation is needed, since each part is either zero, a constant, or an input variable.

We replace the operation $a \gets b + c$ with the sequence $a^{(0)} \gets b^{(0)} + c^{(0)}$, $a^{(1)} \gets b^{(1)} + c^{(1)}$, $a^{(2)} \gets b^{(2)} + c^{(2)}$. Subtraction is similar.

The most interesting operation is $a \gets b \cdot c$, which we replace by the sequence

  $a^{(0)} \gets b^{(0)} \cdot c^{(0)}$

  $a^{(1')} \gets b^{(0)} \cdot c^{(1)}$

  $a^{(1'')} \gets b^{(1)} \cdot c^{(0)}$

  $a^{(1)} \gets a^{(1')} + a^{(1'')}$

  $a^{(2')} \gets b^{(0)} \cdot c^{(2)}$

  $a^{(2'')} \gets b^{(1)} \cdot c^{(1)}$

  $a^{(2''')} \gets b^{(2)} \cdot c^{(0)}$

  $a^{(2'''')} \gets a^{(2')} + a^{(2'')}$

  $a^{(2)} \gets a^{(2''')} + a^{(2'''')}$

The only essential multiplication is involved in computing $a^{(2'')}$.

It is routine to check that the new program indeed computes $t^{(0)},t^{(1)},t^{(2)}$ correctly for all $t$ occurring in the original program.

Normal form (2)

Consider the new program. It is not hard to prove by induction that for each original variable $t$,

$t^{(0}$ is a constant.
$t^{(1)}$ is a linear combination of inputs, i.e. of the form $\sum_i c_i x_i$.
$t^{(2)}$ is a linear combination of the results of essential multiplications (multiplications of the form $s^{(1)} \cdot r^{(1)}$).

In particular, if there are $m$ multiplications in the original program then there are $m$ essential multiplications in the new program, and so it is semantically equivalent to the following program:

Compute $2m$ linear combinations $\ell_1,\ldots,\ell_{2m}$ of the inputs.
Compute $m$ essential multiplications $p_i \gets \ell_{i_1} \cdot \ell_{i_2}$, for $1 \leq i \leq m$.
Output a linear combination $\sum_{i=1}^m c_i p_i$.

In fact, without loss of generality we can assume that $c_i = 1$.

Rank lower bound

Given a program computing the inner product $\sum_{i=1}^n x_i y_i$ using $m$ multiplications, we have shown how to obtain a representation
$$
\sum_{i=1}^n x_i^2 = \sum_{j=1}^m \ell_j r_j,
$$
where $\ell_j,r_j$ are linear combinations of the $x_i$. Replace $\ell_j,r_j$ with coefficient vectors of length $n$, say column vectors. The representation then implies the matrix identity
$$
I_n + S = \sum_{j=1}^m \ell_j r_j^T,
$$
where $S$ is a skew-symmetric matrix (we get $S$ since $x_ix_j$ can be represented in two ways for $i \neq j$). If we are working over the reals, then all eigenvalues of $S$ are either zero or pure imaginary, and so $I_n + S$ has full rank. The right-hand side implies that the rank is at most $m$, and we conclude that $m \geq n$.

When working over the complex numbers, we can have shortcuts such as
$$
(x_1 + ix_2)(x_1 - ix_2) = x_1^2 + x_2^2.
$$
The same method still shows that $n/2$ multiplications are needed, and indeed the optimal number of multiplications to compute the squared norm is $\lceil n/2 \rceil$.


Should you use Genetic algorithm for an extremly large unstructured search space?

No.  Just knowing the size of the search space is not enough to tell whether GA will work or not.  It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying or not, how many local minima it has, and so on.

There is no good theory to know whether GA will work or not.  Ultimately, all you can do is try it and see.

As a side note: Generally speaking, for most problems, other approaches tend to do better than GA.  This is not a theorem; it's just experience / a rule of thumb that seems to often hold.


Here is pseudocode for computing your function:

  Parameters:

  Integer $n$
  Arrays $W,V,S$ of length $n$

  function G(w):

  If $w = 0$, return $0$
  Let $\mathrm{max} \gets -\infty$
  For $i$ from $1$ to $n$:

  If $W[i] \leq w$:

  Let $x \gets G(w-S[i])+V[i]$

  If $x > \mathrm{max}$, let $\mathrm{max} \gets x$

  Return $\mathrm{max}$

I used the notation $W[i],V[i],S[i]$ rather than $w_i,v_i,s_i$.


Time complexity of expanding decimal to new base

Let me start with a short introduction on computation models. A (C-like) computation model specifies the inventory of operations, and the cost of each operation. Two popular computation models are the bit complexity model and the word RAM model, though the latter doesn't really have a canonical description.
In the bit complexity model, all basic operations operate on bits (except for instructions like JUMP, which we ignore here for simplicity), and they all have constant cost. The exact cost of each operation, and the exact repertoire of operations, isn't important (as long as we have a complete set of operations!), since it only affects the running time by a constant factor.
In the word RAM, we associate with each input a parameter $n$ which is a "yardstick" for the input. For example, a function that accepts an array of length $n$ will use the input length as a parameter (but this only works if the array entries are "small" – more on that later). In the word RAM, all basic operations operate on machine words. What is a machine word? It is a value which is $C\log n$ bits long, for some constant $C$ depending on the algorithm (we will see that $C$ doesn't really matter shortly). Each operation on machine words takes time $O(1)$. The operations allowed are arithmetic operations (addition, subtraction, multiplication, division with remainder), comparisons, bitwise operations (NOT, AND, OR, XOR), and shifts. Since we can simulate an operation on words of width $C\log n$ bits using $O(1)$ operations on words of width $\log n$ bits (where the constant depends on $C$), the value of $C$ doesn't really matter.
Let us now come back to the definition of $n$. We usually assume that the input consists of $Cn$ machine words of length $\log n$ bits (for some constant $C$ depending on the algorithm), for a total input length of $Cn\log n$ bits. We obtain an equivalent definition by setting $n$ to be the input length in bits, essentially since $\log(Cn\log n) = \Theta(\log n)$.
(We have not touched on the random access aspect of the RAM model, and on the uniformity aspect of both models, since these are not relevant here.)

Now back to your question. Since your array consists of numbers of length $3\log n$ bits (so we are using $n$ as our yardstick for the word RAM model), we can assume that each of them fits into a single machine word. Packing and unpacking these numbers to base $n$ is very easy:

UNPACK($m$):

$m_0 = m \bmod n$.
$m_1 = \lfloor m/n \rfloor \bmod n$.
$m_2 = \lfloor m/n^2 \rfloor$.
return $m_2,m_1,m_0$.

PACK($m_2,m_1,m_0$):

return $n^2 m_2 + n m_1 + m_0$.

You can see that both operations use $O(1)$ operations, so take $O(1)$ time in the word RAM model. With some care, the implementation can be improved to use $O(d)$ operations for numbers up to $n^d$:

UNPACK($m$):

$m_0 = m \bmod{n}$, $m = \lfloor m/n \rfloor$.
$m_1 = m \bmod{n}$, $m = \lfloor m/n \rfloor$.
$m_2 = m \bmod{n}$.
return $m_2,m_1,m_0$.

PACK($m_2,m_1,m_0$):

return $m_0 + n(m_1 + n (m_2))$.


Computability of a function and decidability

Since $L_f = \{x\#f(x);x ∈ A^*\}$, $f$ must be total, otherwise $L_f$ isn't defined at all. So, we suppose that $f$ is total.

Let's prove : $L_f$ is recursively enumerable $=> f$ is computable. We will use a technic called dovetailing. For the need of the proof, suppose that $c_i$ denotes the $i^{th}$ element of $A^*$ (it's a function, we write $c_i$ instead of $c(i)$ for clarity). We use the lexicographic order to define the $i^{th}$ element of $A^*$.

$L_f$ is recursively enumerable, there exists so a Turing machine $M_{L_f}$ that, for each input $x ∈ (A \cup\{\#\}\cup B)^*$, halts if and only if $x ∈ L_f$.
Let's try to define a Turing machine $M$ that computes $f(x)$ foreach $x∈A^*$.
We will just describe this machine, we won't give a formal definition. Let $x$ be the input of $M$, the machine will proceed by this way :

Execute one step of $M_{L_f}$ with input : $x\#c_0$. If $M_{L_f}$ halts, then $f(x) = c_0$. Else, continue.
Execute two steps of $M_{L_f}$ on both inputs : $x\#c_0$ and $x\#c_1$ sequentially. If $M_{L_f}$ halts on one of them, let's call it $x\#c_i$, then $f(x) = c_i$. Else, continue.
Go by this way, at step $i$, $M$ executes $i$ steps of $M_{L_f}$ with inputs : $x\#c_0, x\#c_1 ... x\#c_i$. If $M_{L_f}$ halts on one of them, suppose it's $x\#c_k$, then $f(x) = c_k$.

Since $f$ is total, $x\#f(x)$ exists for each $x$. In addition, $L_f$ is recursively enumerable, so, when $M$ arrives to $x\#f(x)$, $M_{L_f}$ will halt after $k$ steps because $x\#f(x) ∈ L_f$. $M$ then computes $f(x)$ for every $x∈A^*$.

I hope i have explain it well.

To complete the proof, $c_i$ must be proved to be computable, it's somewhat easy to do.


Is it possible to train a neural network to solve NP-complete problems?

To answer your question, I would to point you to the field of computational learning theory (CLT), which applies complexity theoretic approaches to analyse machine learning.
An important concept in CLT is probably approximately correct (PAC) learning: in simple terms, a problem is PAC learnable if there exists an efficient algorithm which learns the data using a polynomial number of samples from the underlying distribution of the problem with an (polynomially small) error of $\epsilon$ and (polynomially small) failure probability $\delta$.
Unfortunately, there is a big disconnect between results in CLT and results in applied machine learning, so you are unlikely to find result proving or disproving the learnability of NP complete problems using deep neural networks as it is still an active area to research.
Here are some resources to computational learning theory:

Wikipedia: https://en.wikipedia.org/wiki/Computational_learning_theory
The original paper on CLT by Leslie Valiant: http://web.mit.edu/6.435/www/Valiant84.pdf
The hardness of training a particular neural network is NP complete: https://people.csail.mit.edu/rivest/pubs/BR93.pdf
Very good set of notes on CLT:

https://www.cs.ox.ac.uk/people/varun.kanade/teaching/CLT-HT2018/lectures/lecture01.pdf
Section 3 defines and gradually introduces the concept of PAC learning

Section 5.1 of these notes show how 3-COLOURABILITY can be phrased in the PAC learning framework:
In Section 5 as well, the notes show how "3-TERM-DNF is not efficiently PAC learnable (take II) unless RP = NP"


Solving systems of linear equations over semirings

I don't think there's any general algorithm that works for arbitrary semirings.  The requirement to be a semiring doesn't give us a lot to work with.
However, if you have a closed semiring, then there are algorithms for solving systems of linear equations over the semiring.
Closed semirings
A closed semiring is a semiring with a closure operator, denoted $*$, which satisfies the equation
$$a^* = 1 + a \times a^* = 1 + a^* \times a.$$
A closed semiring is also known as a star semiring.
The intuition is that $a^*$ is intended to be the sum of the infinite series
$$1 + a + a^2 + a^3 + \dots$$
For instance, the regular languages form a closed semiring under union and concatenation; the $*$ operator is the Kleene star.  The real numbers form a closed semiring under addition and multiplication; the $*$ operator is $a^* = 1/(1-a)$.
Systems of linear equations over a closed semiring
Now, if you have that kind of structure, then there is an analog of Gaussian elimination.  In particular, if you have a linear system of equations
$$Ax+b = x$$
where $x$ is a vector of variables over the closed semiring, $b$ is a vector of constants, and $A$ is a matrix of constants, then this has the solution
$$x = A^* b.$$
The closure operator on matrices takes a bit of work to define, but it can be computed efficiently using an analog of Gaussian elimination.
For a careful development of the theory, I recommend the following papers:
Stephen Dolan.  Fun with Semirings: A functional pearl on the abuse of linear algebra.  International Conference on Functional Programming, ICFP '13.
Daniel J. Lehmann.  Algebraic structures for transitive closure.  Theoretical Computer Science, vol 4 pp.59--76, 1977.


When should you disable all interrupts in a program?

To implement atomic routine like a semaphore, for example. When a thread call routine to gain some critical section acess, the routine needs to change the value of semaphore's variables and it must be atomic. This change cannot be interrupted otherwise other thread, or process, can use or change some values that are under some critical section. You can find more info on Andrew Tanenbaum or William Stallings book.


create large data sets for machine learning

I know nothing about machine learning, so take the following with a pinch of salt. (I originally posted it as a comment and was encouraged to repost as an answer, so I guess it can't be terrible.)

You get more data by, well, collecting more data...

Simply using some algorithm to generate more data similar to the data you already have won't help, because it doesn't change the distribution of the data, so doesn't do anything to address the problem that your data might not be representative of reality. For example, suppose I make a crappy painting (I can't paint at all) and I ask ten people from my family and close friends if it's any good. They all say, "Yes, David, it's wonderful" because they don't want to hurt my feelings. If you advise me to ask more people's opinion, that's because you feel that I didn't get a proper variety of opinions. Just asking the same ten people again won't change anything: it'll just make me more confident in my bad data because now "twenty" people have told me that my crappy painting is wonderful.

Ultimately, the same problem applies to any algorithmic approach: the best it can do is to generate more data like the data you already have, but that can't possibly have higher quality. And note that any algorithmic approach is, essentially, "use machine learning to generate more data like the data I already have, and then use machine learning to do X with all that data" so it can't be any better than just using machine learning on the original dataset.


Recovering the transition function of a Turing machine with a known number of states

Yes, this is possible.  This is not really a question about Turing machines so much as a question about learning DFAs given membership queries (you provide an input to the DFA and learn whether it accepts or not, and in the case of a finite-state transducer, the output it produces).  Therefore, decidability doesn't really enter into it.

If you know the number of states in the FSM of the Turing machine, yes, observing its behavior on finitely many strings is enough.  You can use Biermann's algorithm to infer a FSM that is consistent with the observed behavior.

You can think of Biermann's algorithm as basically just using SAT, where for each string $u$, you have a variable $s_u$ to represent the state the FSM is in after reading string $u$.  If the FSM has $n$ states, then each $s_u$ must be one of $n$ possible values.  You can use the outputs to deduce some relationships on these variables: e.g., the FSM's behavior on input sequence $u$ differs from its behavior on input sequence $v$, then we obtain the constraint $s_u \ne s_v$.  Also, you get some additional relationships due to the fact that this is a FSM: $s_u = s_v \implies s_{uw} = s_{vw}$ for all $u,v,w$.

Biermann's algorithm yields an (exponential-time) algorithm for finding a FSM that is consistent with all of the observations, if one exists.  Learning a FSM given just membership queries is NP-hard, so you can't expect a more efficient solution in this model.

Biermann's algorithm only promises to give you a FSM that is consistent with all of the observations.  How do we know whether this will match the FSM of the Turing machine?  In general, we don't, but in this case we can use our knowledge of the number of states of the FSM to solve this.  In particular, suppose we know there are $n$ states in the FSA of the Turing machine (after it has been minimized).  We apply Biermann's algorithm to check whether there exists a FSM that's consistent with all the observations and uses $n$ states, and use Biermann's algorithm to check whether there exists a FSM that's consistent with all the observations and uses $n-1$ states.  If the answers are yes and no, respectively, we are done.  If the answers are yes and yes, then we generate more observations until we're done (this can be done systematically in a way that will terminate, by using knowledge of the candidate FSM with $n-1$ states).

I am assuming by "observe its behavior" you mean "observe each step of the execution of the Turing machine on some input".  This lets you treat the FSM as a finite-state transducer and observe the output of the FSM for any desired sequence of inputs, by providing an appropriate input to the Turing machine.

If you don't know the number of states in the FSM, it's easy to prove that you can never know when you have the full thing (this is an easy adversary argument).


How to stop genetic algorithm population converging to a single value

Your selection method may lie at the root of this. You are currently using truncation selection, which applies a very high selective pressure and reduces diversity by not allowing elements from worse solutions to be preserved to possibly be useful again in future generations.

You should try different selection methods, in particular roulette selection or tournament selection, and see if that makes a difference. Most implementations I have seen also keep all generated offspring, regardless of quality. The intuition is that, if a child has low quality they will eventually die out anyway, and they might still carry useful information.


maximum flow with all or nothing through each edge

Your problem is NP-hard. There is a reduction from Independent Set to its decision version.

Consider an instance $G=(V,E)$ of Independent Set, you construct a network with vertices $\{s,t\}\cup V\cup V'$ where each vertex in $V'$ corresponds to a pair of vertices in $V$. For example, if $V=\{1,2,3\}$, then $V'=\{v_{12},v_{23},v_{13}\}$. Then we construct the edges as follows:

For each vertex $x\in V$, add an edge $(s,x)$ with capacity $|V|-1$.
For each vertex $v_{xy}\in V'$, add two edges $(x,v_{xy})$ and $(y,v_{xy})$. Both edges have capacity 1.
For each vertex $v_{xy}\in V'$ where $(x,y)\in E$, add an edge $(v_{xy},t)$ with capacity 1.
For each vertex $v_{xy}\in V'$ where $(x,y)\notin E$, add two edges $(v_{xy},t)$ with capacity 1 (if multiple edges are not allowed, we can add another two vertices $u_1,u_2$ and add two paths $v_{xy}\rightarrow u_1\rightarrow t$ and $v_{xy}\rightarrow u_2\rightarrow t$, which has the same effect).

Now $G$ has an independent set of size $k$ if and only if the constructed network has a flow of value $(|V|-1)k$.


You seem to be overloading the term 'blocking'.

Any context switch you make to the kernel, you have to wait for it to switch back to the usermode before your application can continue. This is not what is usually called 'blocking'.

In the current kernel design, blocking calls are calls where the kernel returns only when the request is complete (or error happens). These calls usually take longer amounts of time and usually lead your process to be scheduled out. For instance, many IO calls are blocking.

There are system call which provides asynchronous IO and they are non-blocking. Note that there is still a context switch that happens here, only the application has to take care of the asynchronous nature of the call.

The paper seems to aim to do away with this context switch back and forth (exception-less system calls) and try to make all the calls asynchronous.


I'm not sure there are any really simple solutions. One algorithm is due to Fernau, and uses an enumeration of all vertex covers of size $2k$; within each of these, a simple dynamic programming algorithm attempts to find a small edge dominating set. Another (earlier) approach, due to Prieto, uses kernelization.


Need help with recurrence relation and postcondition of a function

Without having checked if $T(n)$ is correct, you can find the closed form by:
$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lceil\dfrac{n}{2}\rceil - 1) + n*c_1 + c$$
If n is odd, you can rewrite $T(n)$ as:
$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lfloor\dfrac{n}{2}\rfloor) + n*c_1 + c = $$
$$T(n) = 2T(\lfloor\dfrac{n}{2}\rfloor) + n*c_1 + c $$
If you substitute $T(\lfloor\dfrac{n}{2}\rfloor)$ you get
$$T(n) = 2( 2T(\lfloor\dfrac{n}{4}\rfloor) + \dfrac{n}{2}*c_1 + c  ) + n*c_1 + c =$$
$$T(n) = 4T(\lfloor\dfrac{n}{4}\rfloor) + 2n*c_1 + 3c $$
If you substitute $T(\lfloor\dfrac{n}{4}\rfloor)$ you get
$$ T(n) = 4 (2T(\lfloor\dfrac{n}{8}\rfloor) + \dfrac{n}{4}*c_1 + c) + 2n*c_1 + 3c = $$
$$ T(n) = 8T(\lfloor\dfrac{n}{8}\rfloor) + 3n*c_1 + 7c$$
Now you can observe the pattern and see that after substituting $\dfrac{n}{2^{k-1}}$
$$ T(n) = 2^kT(\lfloor\dfrac{n}{2^k}\rfloor) + k*n*c_1 + (2^0 + 2^1 +...+ 2^k)c$$
Let $n = 2^k$
$$ T(n) = nT(1) + n*log_2n*c_1 + (2^0 + 2^1 +...+ n)c = $$
$$ T(n) = n + n*log_2n*c_1 + (2^n - 1)c = $$
$$ T(n) = n + n*log_2n*c_1 + 2^n*c - c = $$
So you have $O(2^n)$
Now if n is even, you have
$$T(n) = T(\dfrac{n}{2}) + T(\dfrac{n}{2} - 1) + n*c_1 + c $$
And you follow the same method as before (i.e., start by substituting n/2 and find the pattern after a few iterations).


Closure properties between two languages from different grammars

A grammar produces exactly one language; it makes no sense to speak of two languages produced by the same grammar.

The closure properties of regular languages apply to any regular languages.


Free variables of (λx.xy)x and bound variables of λxy.x

Your answer is correct, $y$ is surely free. The model one is wrong. Maybe there was a typo and the answer was meant for $(\lambda y.xy)x$
It depends on the precise definition of $BV$. Often only $FV$ is defined formally, because it's more important. (Bound variables can be freely renamed in a subterm, but free variables can't.) So if $BV$ is defined as
\begin{eqnarray*}
      BV(x) &=& \{\} \\
      BV(M N) &=& BV(M)\cup BV(N) \\
      BV(\lambda x.M) &=& \{x\}\cup BV(M) \\
    \end{eqnarray*}
then the model answer is correct. Note that this definition makes sense: If you have a term $M$ and substitute for a free variable $x$ another term $N$ with no bound variables ($BV(N)=\{\}$), you expect that $BV(M)=BV(M[x:=N])$. If you'd consider only bound variables that also appear under the $\lambda$, this property wouldn't hold.


Get a fixed-size family of k-element subsets

In general, what you are looking for is a combinatorial number system (of degree $t$) , i.e., a correspondece between $\mathbb{N}$ and all $t$-combinations.

There is a large number of algorithms for $t$-combination generation from the last (at least) 50 years. In particular, the operations you are interested in are typically called rank and unrank.

For much more than what the Wikipedia article contains at the time of writing, you can have a look at say the book of Knuth [1] or the one by Kreher and Stinson [2]. Knuth's book contains pseudocode that is straightforward to write in your favorite language, and the nook of Kreher and Stinson is accompanied by source code (in C) that can be found online as well.

[1] Knuth, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Pearson Education India, 2011.

[2] Kreher, Donald L., and Douglas R. Stinson. Combinatorial algorithms: generation, enumeration, and search. Vol. 7. CRC press, 1998.


Time complexity of combinations of n pairs of parentheses

Actually, for every combination of parenthesis, your algorithm performs $\Theta(n)$ amount of work (to build the string and append it to your list of combinations).

The number of valid combinations of $n$ pairs of parenthesis is the $n$'th Catalan Number $C_n = \frac{1}{n+1}\binom{2n}{n}$.

Thus, your algorithm runs in $\Theta(nC_n)$ which is also equal to $\Theta(\frac{4^n}{\sqrt{n}})$, because $C_n$ grows as $\Theta(\frac{4^n}{n^{3/2}})$ (see the linked Wikipedia article).


Why do you need to fill the first element of array when implementing heap?

It is not some magic element but $-\infty$, which is because this is min-heap, in max-heap it would be $\infty$.
The sole purpose is consistent representation of all elements inserted - it guarantees that the next element can be compared and it will be smaller (or bigger - for appropriate heap type) - just to avoid checking whether inserted element is the first one or not and then it would be compared to existing ones. In this form you avoid something like isEmpty everytime you insert element, so it saves time, redundant function calls and (rather unwanted) conditional statement at the cost of one element called "guardian" or sometimes "terminator" (popular name in the lists where you check for this element instead of some NULL or isEnd).


How can we combine badly trained decision trees to a good one?

Your question is a good one and note that in the extreme case, if every leaf node contains only one data point then you are almost certainly over-fitting and/or missing the "true" dimensions that separate the two points above. One way around this problem is to not split at a node (make it a leaf) if it contains fewer than C points, where C is something like 10. Also, a decision tree in the Brieman/Cutler framework uses $\sqrt{N}$ randomly chosen dimensions to try to split on, at a node with N points. Thus you are somewhat avoiding over-fitting because of this (but it's random so it's not very reassuring). The best solution is to create many (like 100 or more) bootstrap replicates of your data and build a decision tree for each bootstrap replicate. Then for prediction, you run the point through all 100 trees and take the average of the prediction indicator vectors to get predicted class probabilities. You can take the highest probability to be the predicted class. This strategy is much more robust to over-fitting because splits with low data support in one tree will only appear in the majority of trees (either exactly or approximately) if they have higher overall data support.


As far as I know, they do the same way they created things like Penn tree bank.
They have a panel of experts, usually linguists, who sat together and decided synset taxonomy based on various widely used dictionaries.

PS: Please up-vote me so I can up vote others, thanks :)


Proving that no 2-state DFA decides the language A = {x ∈ {0, 1}* | bnum(x) is divisible by 3}

Remainder values is indeed the clue! Obviously the strings $1$ and $10$ cannot end in a final state as they represent number 1 and 2 respectively. But can they end in the same state?


How would the Internet work between planets?

There would be special protocols for interplanet communication. Right now there are already different routing protocols for connecting different cities, different countries and different continents.

BGP (Border Gateway protocol) is a routing protocol used between continents mainly. It has different parameters and behavior than OSPF or RIP or other protocols used between different LAN's or WAN's.

Read about BGP. Some other protocols would probably be developed for even larger distances and for connecting different planets.


No way to say. $T(n) = O(n \log n)$ means there exist constants $c > 0, N_0$ so that for all $n \ge N_0$ it is $T(n) \le c n \log n$. They are anything, i.e., it might be valid only for ridiculously large $n$ (large $N_0$), or even for small $N_0$, like $N_0 = 10$, the constant $c$ could be such that all you know is that $T(100) \le \text{one milisecond}$ or $T(100) \le \text{one week}$.


difference between predictive modeling and clustering?

Predictive models are sometimes called learning with a teacher, whereas in clustering you're left completely alone.

Predictive models split data into training and testing subsample which is used for verifying computed model. Predictive (or regression) model typically assign weights to each attribute. From clustering you can compute some internal evaluation metric, but that doesn't necessarily correlate with (desired) human judgment. Unsupervised learning (clustering) mostly treats all attributes as equal as without external information, as one can't say which attribute is more important than the other.


Indexed family of all unary partial computable functions

Recall that a collection $\mathcal{F}$ of computable partial functions admits a computable numbering if there is a computable function $f : \mathbb{N} \to \mathbb{N}$ such that $\mathcal{F} = \{\varphi_{f(e)} \mid e \in \mathbb{N}\}$, where $(\varphi_e)_{e \in \mathbb{N}}$ is a standard enumeration of the computable partial functions.

Let $\mathcal{I}$ be the collection of computable partial functions whose domain is either $\mathbb{N}$ or some $\{0,\ldots,n\}$.

Claim: $\mathcal{I}$ admits a computable numbering.

Proof: Let $\iota(n)$ denote the program:

Input $k \in \mathbb{N}$
For each $0 \leq i < k$ simulate $\phi_n(i)$.
Simulate $\varphi_n(k)$ and output its output

Clearly, if $\varphi_n$ is total, then $\varphi_{\iota(n)} = \varphi_n$. Otherwise $\varphi_{\iota(n)}$ is defined in some initial segment of $\mathbb{N}$. Thus, $\iota$ is a computable numbering of $\mathcal{I}$.

Let $\mathcal{C}$ be the collection of partial computable functions admit a computable total continuation. It is easy to see that $\mathcal{C}$ is also the class of partial computable function admitting an extension in $\mathcal{I}$. As the domain of a partial computable function is c.e., we can then show:

Claim: $\mathcal{C}$ admits a computable numbering.

Proof: Let $\langle \ , \ \rangle$ be a standard pairing function. We define $c : \mathbb{N} \to \mathbb{N}$ by letting $c(\langle e, n \rangle)$ be the program:

Input $k \in \mathbb{N}$
Simulate $\varphi_n(k)$
Simulate $\varphi_{\iota(e)}(k)$ and output its result.

Now $c$ is a computable numbering for $\mathcal{C}$. To see this, we first note that $\varphi_{c(\langle e,n\rangle)}$ is the restriction of $\varphi_{\iota(e)}$ to the set $\operatorname{dom}(\varphi_n)$. This establishes  $\varphi_{c(\langle e,n\rangle)} \in \mathcal{C}$ for any $e, n$. Conversely, assume that $f$ is a partial computable function with a total computable continuation $g$. Let $f = \varphi_n$ and $g = \varphi_e$. Then $f = \varphi_{c(\langle e, n\rangle)}$, so we do get indeed each member of $\mathcal{C}$ in the range of $c$.