How the closure properties of the formal languages dictate decidability of their problem

If a family $\mathcal F$ of languages is closed under some operation, say intersection, then you are right that it is decidable whether the intersection of any two particular languages from $\mathcal F$ also belongs to $\mathcal F$. The answer is always Yes.

The converse, however, isn't true. Consider the family $\mathcal F_m$ of all regular languages which are accepted by some DFA having at most $m$ states, for some parameter $m$. When $m > 1$, this language family isn't closed under intersection, but given any two languages from $\mathcal F_m$ (in any reasonable encoding), it is decidable (depending on the encoding, efficiently) whether their intersection belongs to $\mathcal F_m$.


Traveling Salesman -- number of qubits required?

The notebook describes how to solve combinatorial optimization problems by encoding them as minimizing a binary quadratic form, which can in turn be phrased as finding the minimal eigenvalue of a Hamiltonian, and so solved by a quantum computer. The number of qubits needed is the dimension of the Hamiltonian, which is also the number of bits in the encoding.

In TSP, the optimization is over permutations. The notebook suggests encoding a permutation by encoding its permutation matrix, which is an $n\times n$ binary matrix. Since the rows and columns sum to 1, we can deduce the final row and column from the rest of the entry, and so need to keep only $(n-1)^2$ variables. In your example, $n = 4$ and so $(n-1)^2 = 9$.


Quick sort worst case complexity improvement

The simplest way is to choose the median as pivot. Since the median can be found in linear time, the overall algorithm would satisfy the recurrence
$$ T(n) = T(\lfloor \tfrac{n-1}{2} \rfloor) + T(\lceil \tfrac{n-1}{2} \rceil) + O(n), $$
whose solution is $T(n) = O(n\log n)$.


Partial answer:

It works for some pairs $b_1$ $b_2$, but may not work for every pair.

Partial solution:

for pairs $b_1$ $b_2$ where there is an $x, p_1, p_2 \in \mathbb{Z}$ such that

$\begin{alignat*}{4}
x^{p_1} & {}={} & b_1\\
x^{p_2} & {}={} & b_2
\end{alignat*}$

you can divide $n$ of $b_1$ into sections of $p_2 $ digit sections, which you can then convert into $b_2$.

If you want to query a slice in the result $b_2$, you need to calculate the section number by dividing by $p_1 $

3 -> 10 doesn't work with this, but I will give you an example

8 -> 16:

$x = 2, p_1 = 3, p_2 = 4$

8  [....][1][2][3][4][..p2 * x blocks..]
2        001010011100
16 [....][ 2][ 9][ C][..p1 * x blocks..]

3 -> 9:

$x = 3, p_1 = 1, p_2 = 2$

3  [....][1][0][2][1][..p2 * x blocks..]
3          1  0  2  1
9  [....][   3][   7][..p1 * x blocks..]


Is there a name for an inverted state machine?

If I understand you correctly, you could achieve this using transducers (i.e. automata which also produce outputs when taking a transition).

Suppose we are given a DFA $A = (Q,q_0,\Sigma,\delta)$ describing which events lead to which state transitions. Here $Q$ is the set of states, $q_0$ is the initial state, $\Sigma$ the alphabet of events, and $\delta:Q\times\Sigma\to Q$ the transition function. Then we can define a (nondeterministic) transducer $A'$ as $(Q,q_0,Q,\Sigma,\delta')$ as follows:

$Q$ is the same set of states as before, and $q_0$ is still initial;
The input alphabet is now also $Q$ (representing the target state you are trying to reach);
$\Sigma$ is now the output alphabet;
The transition relation $\delta'$ contains a tuple $(q,\delta(q,a),a,\delta(q,a))$ for each $q\in Q$ and $a\in\Sigma$ (representing the fact that to get from $q$ to $r$, you can use $a$ if $r=\delta(q,a)$).

Note that I'm assuming that you actually want to proceed to the given target state, otherwise you need to adapt the transition relation. Also, if there is no transition from $q$ to $r$, the computation simply fails; you may want to handle this case differently.


Nope, this algorithm doesn't work.  It is possible to find an explicit counterexample.  Since it sounds like this is an exercise you're doing to learn algorithms, I won't spoil the exercise for you, but I'll just give you some hints that may help you find a counter example.

Start with a graph containing just a single path from $s$ to $t$, and nothing else.  Make it a fairly short path, say, 5 edges long.
Introduce a long path from $s$ to $t$ (say, 10 edges long or so) that coincides with the short path for a brief while then diverges.
Now introduce a second long path from $s$ to $t$ with two properties: (a) it is edge-disjoint with the first long path, (b) it has at least one edge in common with the short path.

Finding a counterexample is a little tricky, but draw it out and try some ideas, and I bet you'll be able to figure out.

Your approach doesn't work, but there are other algorithms to solve this problem.  However, they're fairly complicated: more complicated than your could reasonably be expected to discover on your own.  Assuming this is a homework/exercise, I can't just can't believe your teacher would assign you an exercise that requires you to independently re-discover those algorithms -- so there must be some other trick or background information available to you.  You might check in with your teacher.

The other algorithms use the following idea: Look for a "funnel" edge $e$ such that all paths from $s$ to $t$ "funnel through" the edge $e$ (i.e., all paths from $s$ to $t$ must include the edge $e$).  If you find such an edge, obviously there is no pair of edge-disjoint paths from $s$ to $t$.  If you don't find such an edge, then it turns out that there's guaranteed to exist two edge-disjoint paths from $s$ to $t$.  Proving this is tricky, though, as is devising an efficient algorithm to rapidly test for the existence of such an edge.

Since you asked for references, this problem is solved by the following characterization: there are two vertex-disjoint paths from $s$ and $t$ if and only if $s,t$ are part of the same biconnected component.  There are fancy algorithms to decompose a graph into biconnected components in linear time.  Similarly, there are two edge-disjoint paths from $s$ and $t$ if and only if $s,t$ are part of the same 2-edge-connected component.  There are fancy algorithms to decompose a graph into 2-edge-connected components in linear time (or, you can reduce to the problem of computing biconnected components by computing a new graph that swaps vertices and edges).

So, an efficient answer to your question is: decompose the graph into 2-edge-connected components (using the algorithms mentioned in the previous paragraph), then test whether $s$ and $t$ are in the same component.

For more, see e.g., https://en.wikipedia.org/wiki/Biconnected_component and  https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29 and https://en.wikipedia.org/wiki/K-edge-connected_graph.


How Can we make $O(N)$ order statistic queries with Fibonacci heap in $O(N)$?

Well, you can build a Fibonacci heap in $O(N)$ time. Assuming you will get the proposed order statistic also in $O(N)$ time for the index set $\{1,2,3,\ldots,N\}$, then we can sort the stored set in linear time.

You probably know that (comparision based) sorting takes $\Omega(N \log N)$ time. Since you have no information about the universe of your elements you cannot use tricks like bucket sort or sorting on the word ram to get a linear time sorting algorithm. So you can't solve your problem in $O(N)$ time.


Is the union of computable enumerable sets computably enumerable

Every language can be written as a countable union of singletons $\{x\}$.
On the other hand, the union of finitely many c.e. languages is c.e.


How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?

To reduce $k$-CNF to CNF: every instance of $k$-CNF is an instance of CNF, so the reduction is trivial.

To reduce CNF to $k$-CNF, where $k \ge 3$: convert the CNF formula to a circuit that computes it; then convert the circuit to a 3-CNF formula using the Tseitin transformation.  (If your definition of $k$-CNF requires that there be exactly $k$ literals in every clause, then you can pad: introduce $k$ new variables $y_1,\dots,y_k$; for every clause that has less than $k$ literals, add $\lor y_1 \lor y_2 \lor \dots$ to pad it out to exactly $k$ literals; and then add clauses that force all of $y_1,\dots,y_k$ to be false.)

If this is too terse, see our reference question and a good textbook to learn the fundamentals of reductions.


Sorting n elements in worst case of $\sqrt{n}\log n$

This is impossible. You cannot sort $n$ elements without examining each element at least once, which takes at least $n$ operations.

$n=\sqrt{n}\cdot\sqrt{n}\ge\sqrt{n}\cdot\log{n}$ for all $n>1$, assuming the logarithmic base is at least 2. (Of course, if you assume something completely asinine like $\log_{1.000001}n$, it would be technically possible for some values of $n$.)


What are the current state of art approximation algorithm for NP-Hard problems?

First, there are two aspects to separate here: theoretical approximation and practical approximation (i.e., heuristics). With heuristics, such as in the NIPS paper you mention, the goal is roughly to propose some method, take a large bunch of actual instances of a problem, benchmark empirically the method, and draw conclusions as to how well we did in terms of approximation.

This is in contrast to (theoretical) approximation algorithms that give a formal guarantee on solution quality, on all possible instances. For example, the guarantee could be "the solution returned by this algorithm is either optimal or at most three less than the optimal". But as you might know, there is an enormous amount of hard problems that can be wildly different in terms of approximation. Maximum clique or chromatic number, for instance, are very hard to approximate theoretically.


Length of the certificate in complexity classes

I'm a little confused by your quote.

There are two equivalent definitions of the NP complexity class in terms of Turing Machines:

The class of problems for which a deterministic verifier exists whose runtime is bounded by a polynomial in the size of the problem input.
The class of problems for which a nondeterminstic decider exists whose (nondeterministic) runtime is bounded by a polynomial in the size of the problem input.

So a nondeterministic machine trying to decide membership in a language wouldn't be presented with a certificate; that's not what it means to decide membership in a language. It's the deterministic verifier that gets a certificate - a verifier over language L is a decider over the language of pairs of an element of L and a certificate proving the element in L (that's why the definition is asymmetric and there's no certificates for non-membership; the verifier only answers "yes this is an element of L together with a certificate for this element", or "no this is either not an element of L or not a certificate for this element").

That aside, on to your questions.

If the running time of the verifier in O(f(n)), then the certificate (in general) is also in O(f(n)). It's possible the verifier needs to read the whole certificate and then do some trivial computation with it that doesn't increase the big-oh complexity over the time needed to simply read the certificate. Particular verifier algorithms for particular problems may well have much shorter certificates (implying that their runtime is occupied with much more computation than simply reading the certificate). But you can't say anything in general about an unknown verifier's certificate length just from knowing its runtime (well, anything more specific than that it's certificate length bound must be short enough to be read within its run time bound).

You also ask about how the existence of a deterministic verifier for a problem implies the existence of a nondeterministic decider for the same problem. The implication actually goes both ways (which is why the two definitions of the NP complexity class are equivalent).

Given a deterministic verifier you can construct a nondeterministic decider. The verifier is a decider over the language <e, C(e)> (where e is an element of L and C is a function that computes a certificate for e). The machine we're trying to construct will be given e as input. If it could come up with C(e) it could simply run the verifier on the pair and it would have its answer.

But our decider has the advantage of nondeterminism. It can simply guess a value for C(e) and run the verifier, and nondeterminism implies that if there is such a value that leads to acceptance then the machine will have picked the correct one. The "guessing" can be (almost) implemented by having a state that nondeterminsitically writes a symbol from the alphabet (any symbol) on the current cell, moves the tape head right, and then nondeterministically chooses to remain in the same state or to move on to the verifier stage.

Since the certificates must be within O(f(n)) length, and all we do before running the verifier is write down the certificate, the runtime of this machine on an e that is in L is O(f(n)) + O(f(n)), which is simply O(f(n)).

The only catch is that if e is not in L, then there is no such C(e) that will lead to the verifier accepting. But we can't let our machine keep trying longer and longer guesses for C(e); our machine is a decider, so it is required to halt for all input. The machine needs to know when to give up; it must only be capable of generating a finite number of guesses for C(e).

This means that machine must be able to calculate an upper bound to the length of C(e), and only guess strings up to that length. This means that the upper bound has to be a total computable function of e. I'm not 100% certain if that's possible in general for verifiers with completely arbitrary runtime complexity O(f(n)), because f might not be a computable function, and the exact certificate length can be larger than f(n) because of the details big-oh notation abstracts away from (constants, lower-order terms, and the fact that the bound only has to apply for sufficiently large n; maybe someone who knows a bit more can add something here). But for verifiers with polynomial big-oh complexity, there always exists a polynomial in n which is strictly larger than the minimum certificate length for any e with length n.

So we can presume the existence of a nondeterminstic machine which for an element e of length n, calculates this upper bound, guesses any string whose length is within the bound, and runs the verifier on it. Since guessing a string within a polynomial bound takes at most polynomial time, and the verifier had a polynomial run time bound, and the sum of two polynomials is still a polynomial, the nondeterministic decider always halts within a polynomial bound.

The other direction (the existence of a polynomial nondeterminsitic decider implies the existence of a polynomial deterministic verifier) is much easier. Let the certificate for any e in L simply be a record of all the transitions used by the nondeterministic decider when processing e. All the verifier has to do is check that this record forms a valid path through the nondeterministic decider leading to an accept state. Since checking this doesn't require exploring all the nondeterministic possibilities, a deterministic verifier can do this with overhead of a constant multiplier over the nondeterministic decider's runtime (it only needs to check each transition against the decider's set of possible transitions, which is a constant).

I've answered a slightly weaker question than you asked, however. I've only shown that you can come up with a decider for verifiers with a polynomial runtime bound (although similar reasoning applies to exponential bounds, and most other functions that actually get used very often when talking about big-oh complexity). I also haven't shown that a verifier with runtime in O(f(n)) implies the existence of a decider with runtime in O(f(n)), even for polynomial f; all I've shown is that if the runtime bound of the verifier is a polynomial then the runtime bound of the decider is still a polynomial; it might be larger one. I don't actually know whether a verifier always implies a decider with the same runtime bound; I'd welcome an addition from someone who knows for sure either way.


What is the optimal solution to prove the reachbility of a node from the root?

This seems to be a difficult problem. For undirected graphs, this is known as "dynamic connectivity". You can see slides describing an $O(\log^2 n)$ algorithm, or the paper itself. For directed graphs, there is an algorithm no better than DFS described in this paper (the algorithm is better than DFS if you are making several connectivity queries each time). A paper by Pătraşcu gives evidence that polylogarithmic update time isn't possible for directed graphs.


Smarter recursion to compute #tilings of $m \times n$ board with $2 \times 1$ dominoes?

From my answer on math.SE:

If you just used $1\times2$ rectangles, then this is same as finding the number of matchings in the $m \times n$ rectangle graph, and a formula for that has been given by Kastelyn:

$$ \sqrt{\left|\prod_{j=1}^{m}\prod_{k=1}^{n} \left(2 \cos \frac{\pi j}{m+1} + 2i\cos \frac{\pi k}{n+1}\right)\right|}$$

This was done, by mapping the number to the square root of the determinant of a weighted adjacency matrix of the graph.

You can find a nice exposition for the $1\times 2$ case in the first chapter of Kenyon's lecture notes.


No, that doesn't prove there's no polynomial time solution for 3-SAT, for a couple of reasons.

Saying that you have an $O(2^n)$ algorithm for something only provides an upper bound. The algorithm takes no more than some constant times $2^n$ steps, for big enough $n$ but I can tell you that I have no more than one trillion dollars in the bank and you still have no idea how wealthy I am.
If your suggested argument was solid, the following would be a direct proof that $\mathrm{P}\neq\mathrm{EXP}$. Here's an exponential-time, brute-force recursive algorithm for graph connectivity: check that every proper subset of the graph's vertices is connected and sends an edge to at least one vertex not in the subset. This can't prove that there's no polynomial time algorithm for graph connectivity because we already know that plenty of those exist. Similarly, observing that you have an exponential-time algorithm for 3-SAT doesn't prove that there isn't also a polynoial one.
$\mathrm{P}\subseteq \mathrm{NP}\subseteq \mathrm{EXP}$ so we already know there is an exponential-time algorithm for every problem in $\mathrm{P}$ and $\mathrm{NP}$. Knowing that 3-SAT is in $\mathrm{EXP}$ tells you nothing new.  However, if you could prove that 3-SAT is $\mathrm{EXP}$-complete, that would prove that $\mathrm{NP}=\mathrm{EXP}$ and, since we know that $\mathrm{P}\neq\mathrm{EXP}$ from the time hierarchy theorem, that would prove $\mathrm{P}\neq\mathrm{NP}$. But it's very unlikely that 3-SAT is $\mathrm{EXP}$-complete. :-)

  [...] how can you prove that problem is EXPTIME and not super-polynomial time?

"Super-polynomial" just means "more than a polynomial". EXPTIME is an example of a super-polynomial time complexity class.

  Also please tell me what is the deference between super-polynomial and polynomial times in context of polynomial expression.

That doesn't make sense. A polynomial is a polynomial so it can be expressed as a polynomial; a function that's super-polynomial isn't a polynomial so it can't be expressed as a polynomial.  I'm not sure why you've latched onto this phrase "polynomial expression".


Design a Turing Machine Checking if Apples and Bananas are Even

I'm not going to give you a direct solution, but let's think about this problem together, shall we? We will focus on 4 states. Why four? Well, you have two variables, each with two possible states, so $2^2 = 4$. So, for right now let's call our states $1$, $2$, $3$ and $4$:

$1$ is the state denoting an even number of apples and bananas. This is our start state.
$2$ is the state denoting an odd number of apples and an even number of bananas.
$3$ is the state denoting an even number of apples and an odd number of bananas.
$4$ is the state denoting an odd number of apples and an odd number of bananas.

Now, let's see how we move between states. For the moment, let's ignore the possibility of $\varepsilon$ for the input.

From state $1$ ($a$=even, $b$=even):

If we get an $a$, go to state $2$. Eat the apple and output nothing.
If we get a $b$, go to state $3$. Eat the banana and output nothing.

From state $2$ ($a$=odd, $b$=even):

If we get an $a$, we go to state $1$. Eat the apple and output nothing.
If we get a $b$, we go to state $4$. Eat the banana and output nothing.

From state $3$ ($a$=even, $b$=odd):

If we get an $a$, we go to state $4$. Eat the apple and output nothing.
If we get a $b$, we go to state $1$. Eat the banana and output nothing.

From state $4$ ($a$=odd, $b$=odd):

If we get an $a$, we go to state $3$. Eat the apple and output nothing.
If we get a $b$, we go to state $2$. Eat the banana and output nothing.

At this point we are pretty full and sick of apples and bananas. So let's consider what happens when we run out of food. It should be clear that we are going to be in one of the four states above. So let's augment each of them with an additional rule each:

The rule is simple: when the input for any one of those states is $\varepsilon$, output the correct sequence of characters for that state and then go to a $halt$ state.

I hope this helps!


Amount of expected loop iterations when searching an array by random index

Let $N$ be the geometric R.V. that returns the number of times the array was accessed in order to search for the element, $A[x]$ until we successfully find it. We want to know $\mathbb{E}[N]$.

We can view the iterations of the while loop as a sequence of IID Bernoulli trials, each with a probability $p$ of succeeding, and $q = 1 - p$ of failure. Given the question, we want to know how many trials are needed to obtain a "success" which would be finding the element $A[x]$ thus the while loop terminates.

Since the $\Pr\{N = k\} = q^{k-1}p$, we have that $\mathbb{E}[N] = \sum\limits_{k = 1}^\infty k \: q^{k-1}p$.

Thus, $\mathbb{E}[N] = \dfrac 1p$ where $p = \dfrac kn$ so $\mathbb{E}[N] = \dfrac nk$.

So on average, it takes $\dfrac nk$ accesses before we find the element, $A[x]$.


Travelling Salesman Problem Easy Algorithms

It is an extremely hard problem to solve. But some reasonable heuristics are easy to explain/code.

One is to start at a random vertex, each step move to the vertex that hasn't been visited yet that is closest. Rinse and repeat.

Another is to start with a minimal spanning tree of the graph, pick any vertex as starting point (root), and visit the vertices in preorder. If you are asked to visit a vertex that you already visited, just skip it for the next one in preorder. Think about it as walking along the "outside" of the tree, taking shortcuts to the next when asked to visit a vertex again. This works rather well if the distances have the triangular property (i.e., $c(u v) \le c(u x) + c(x v)$ for all vertices).

See if you can come up with another idea.


Simple discrete math problem: A and B in 3CNF

How about $(A \lor A \lor A) \land (B \lor B \lor B)$?

If you need three different variables in each clause, you can use

$$
(A \lor x_1 \lor x_2) \land (B \lor x_1 \lor x_2) \land \\
(\lnot x_1 \lor y_1 \lor z_1) \land (\lnot x_1 \lor y_1 \lor \lnot z_1) \land
(\lnot x_1 \lor \lnot y_1 \lor z_1) \land (\lnot x_1 \lor \lnot y_1 \lor \lnot z_1) \land \\
(\lnot x_2 \lor y_2 \lor z_2) \land (\lnot x_2 \lor y_2 \lor \lnot z_2) \land
(\lnot x_2 \lor \lnot y_2 \lor z_2) \land (\lnot x_2 \lor \lnot y_2 \lor \lnot z_2).
$$


Big O of an algorithm that relies on convergence

Usually we prove something about the rate of convergence.  For instance, we might prove that after $k$ iterations, the relative error is $1/2^k$.  Thus if each iteration takes (say) $O(n^2)$ time, and we want an answer that has relative error at most $\epsilon$, then we have found an algorithm whose running time is $O(n^2 \lg (1/\epsilon))$.  Notice how the running time now depends both on the input size and on the desired accuracy of the answer.

For instance, PageRank uses power iteration.  As you can see from the Wikipedia page on power iteration, it is possible to prove results about its rate of convergence (as a function of the first two largest eigenvalues $\lambda_1,\lambda_2$).


Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings

Your solution is correct but not complete.

You have not proven the correspondence to the colouring problem given as an intuition in the hint

You could say something on the lines of:- If z distinguishes x and y, we have xz belongs to L but not xy(or vice versa). This is homomorphic(? not sure about this, have to check) to colouring dots x and y with different primary colours, because indistinguishability is transitive, reflexive etc

You have only proven that you have a solution using log n strings but not that log n strings are required

This could be by contradiction. eg. assume that fewer than log n colours can be used to distinguish the dots. Represent the dots as binary strings consisting of the colours they have. Then you have fewer than log n bots required to represent n numbers in binary

IMHO you can skip the colouring and directly prove correspondence with binary strings


Can Chomsky Normal Form have more than one terminal?

The above given CFG cannot be in Chomsky Normal Form since the production
B→abcd has multiple terminals on left hand side of the production.
In order to convert the given CFG to Chomsky Normal Form, will need to replace the terminals on lhs of production B→abcd as follows -
B->abcd
B->FG
F->AE
G->CD
E->b
C->c
D->d.


what are the BUS MASTERS in a processor?

(a) "System bus" was a common aggregation term for "data bus" and "address bus". There are a lot of other buses depending on your machine, e.g. between RAM and video card, or between SCSI controller and devices (hard disks, scanner, whatever).

(b) There's no such thing as "the" memory, it's a whole hierarchy of different memory systems, varying in speed/size/cost. For example, the fastest memory part are the on-processor registers. You can transport their content from and to the data or address bus (to move values to and from RAM), but for example the ALU won't access the registers via "system bus".

(c) Other devices which are able to "drive" the bus. For example, consider a SCSI controller, a scanner or a network card wanting to write something (a disk block, a scanned image, a received packet) to a previously assigned RAM area. Of course, the controller has to harmonize it's RAM access with the CPU. So the device will ask (via an extra control wire) to grant the bus, and wait. After the CPU acknowledges with a signal, the device becomes temporarily bus master and may use data and address bus exclusively (at least for some time), before it has to hand back control. As the CPU is present in every system, but (for example) a network card is not, it's a sensible design choice to make the CPU bus master.


Master Theorem: How to find the value of b in this recurrence relation

You can't use the Master theorem on that function $T$.

However, as Raphael suggests, you could consider the related function

$$T'(n) = T'(n/4) + f(n),$$

use the Master theorem to find a solution for $T'$, and then check whether that's a valid solution for $T$ too.  No guarantees that it will be, but you could check.

In other words, you could use the guess-and-check strategy to solve the recurrence for $T$, where your "guess" comes from solving $T'$ using the Master theorem.  See also Solving or approximating recurrence relations for sequences of numbers for an explanation of guess-and-check (also called guess-and-prove).

One caveat is that guess-and-check will probably require an explicit solution to $T$, with specific constants.  In other words, it's usually not enough to guess that $T(n) = O(g(n))$; you will typically need to guess a specific constant $c$ such that $T(n) \le c \cdot  g(n)$, one that will enable the proof to go through.


Can choice function in SHA algorithm be used in a simplied way?

I'm not familiar with the details of SHA but
if we interpret $0$ as false and $1$ as true, then $a+b$ and $a \oplus b$ only differ when $a=b=1$.
In your specific case $(x \wedge y)$ and $(\neg x \wedge z)$ cannot both be true.
This is easy to see since you would need to simultaneously have $x=1$ and $x=0$.
It follows that  $(x \wedge y) \oplus (\neg x \wedge z)$  and $(x \wedge y) + (\neg x \wedge z)$ are equivalent. The same holds true if $x$, $y$, and $z$ are binary numbers and $\neg$, $\wedge$, and $\oplus$ are interpreted as bitwise operators.
This equality does not hold for the case of $\text{Maj}(x,y,z)$, as you can check by setting $x=y=z=1$.


Kleene positive closure - help in proofing this claim

Let's use $A$ for $L_1$ and $B$ for $L_2$.
If you unpack both sides, you get
$$
(AB)^+ = AB + ABAB + ABABAB + \cdots \\
A^+B^+ = AB + AAB + ABB + AABB + \cdots
$$
Perhaps this can give you some ideas.


Decoding problem and conditional probabilities

Maximizing $P(r|t)$ is known as the Maximum Likelihood (ML) principle, while maximizing $P(t|r)$ is known as the Maximum A Posteriori probability (MAP) principle.

Here are some facts that answer your question:

Optimal decoding (minimizing the probability of error) is achieved by the MAP principle. See p. 152 of the book.
However, using MAP would require a different decoding algorithm for every distribution on $t$. I.e. you would have to adapt decoding to the statistical properties of the source. To avoid this, it is typical to assume a uniform distribution on $t$. In this case, MAP and ML are equivalent because $P(t|r)$ becomes proportional to $P(r|t)$ (see p. 152 again).
I agree with you he should have started with the MAP problem of maximizing $P(t|r)$, since that's the correct goal anyway. But I presume that he is assuming a uniform distribution on $t$, in which case the difference doesn't matter anyway.


Efficient algorithms for dealing with linear algebra over the rationals

One trick I've seen elsewhere is to pick a random prime $p$, reduce everything modulo $p$, and check whether the vectors are linearly independent over $(\mathbb{Z}/p\mathbb{Z})^n$.  If $p$ is not a divisor of any of the entries of the vectors, and if $v_k$ is not in the $(\mathbb{Z}/p\mathbb{Z})^n$-span of $v_1,\dots,v_{k-1}$, then $v_k$ isn't in the $\mathbb{Q}$-span of $v_1,\dots,v_{k-1}$, either.  By picking $p$ to be large enough (larger than the largest of the vector-entries), you can be sure $p$ won't be a divisor of any of the entries.

So, this provides a pre-test you can use.  You run the pre-test first (working modulo $p$), and if it outputs "linearly independent", then you don't need to run the expensive $\mathbb{Q}$-span test; on the other hand, if it outputs "linearly dependent", then you do need to do the expensive $\mathbb{Q}$-span test (e.g., Gaussian elimination).

And, I think there's a heuristic argument that if $p$ is random and large enough, then if it's $\mathbb{Q}$-independence then with high probability (over the choice of $p$) it'll be $(\mathbb{Z}/p\mathbb{Z})^n$-independent, too.  Or something like that.  But it's just a heuristic and no guarantee that it'll work for all situations.

I hope I have this right.  I'm going from memory so I might have something backwards.  Check my logic, and try it on your situation, and see if it helps in your application or not.


Is concatenation of regular language with any other language regular?

As you show, if $L = \emptyset$ then $LM$ is regular for any language $M$. Conversely, for languages over $\{0,1\}$ (or any non-unary alphabet), there is a language $M$ such that if $L \neq \emptyset$ then $LM$ is not regular:
$$
M = \{10^p : p \text{ prime}\}.
$$
Indeed, suppose that $w \in L$. Then
$$ w^{-1}(LM \cap w10^*) = M. $$
Since all of the operations preserve regularity, we conclude that $LM$ is not regular.

Over a unary alphabet, the picture is a bit different. Let
$$ M = \{ 0^{n!} : n \geq 0 \}. $$
If $L \neq \emptyset$ is finite then $LM$ is not eventually periodic, and so not regular. If $L$ is infinite and not regular, then $L\{\epsilon\}$ is not regular. If $L$ is infinite and regular, then it is eventually periodic. For every language $M$, $LM$ is also eventually periodic (with the same period), and so regular.


Need help about solving a recurrence relation

For $\sum_{0 \le r \le k} r \cdot 2^r$, start with:
$$
\frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} z^r
$$
As this is a polynomial, the following mangling doesn't need any justification:
$$
z \frac{d}{dz} \frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} r z^r
$$
Doing the operations indicated:
$$
\sum_{0 \le r \le k} r z^r = \frac{z^k (k z^2 - (k + 1) z) + z}{(1 - z)^2}
$$
Finally:
$$
\sum_{0 \le r \le k} r 2^r = (2 k - 2) 2^k + 2 = \Theta(k 2^k) = \Theta(n \log n)
$$


Anonymous Visibility Check in P2P networks

Ok, so after realizing my previous solution didn't work I've put this problem on ice for a while, but now I have one in which I am fairly confident. If you find any obvious flaws, please let me know. This is the first time I'm answering a question, and I'm trying to be as transparent as possible where all my ideas came from so that anyone can find errors easier. Thus my answer will be quite long.

To start with, I've limited it to determining if the distance between two players (two points) is bellow a certain therhold. It can however be extended to a vision field.

My current solution relies on a homographic encryption which can do addition (such as Paillier).
To start with I note the expression which I ultimately want to evaluate, which is the distance between two points being within a certain distance:
\begin{equation}
(x_a -x_b)^2 + (y_a - y_b)^2 - d < 0
\end{equation}
However, since the distance you want to check will in many cases be very similar for both players, your opponent can make good guesses as to what $d$ is, which means your opponent has access to a boundary on your position (one equation, two unknowns in a 2D environment). Thus we need to add a slight modification to avoid this, and ultimately evaluate the following equation:
\begin{equation}
r(x_a -x_b)^2 + r(y_a - y_b)^2 - rd < 0
\end{equation}
The multiplication of $r$ here does not change the truth value of the expression, but it does add one unknown, thus the only constraint we can get is that the unknown point is on a plane, which does not add any new information.

In order to use the additive homographic property of our encryption we need to fully expand this equation:
\begin{equation}
rx_a^2 +rx_b^2 -2rx_a x_b + ry_a^2 + ry_b^2 -2ry_a y_b - rd < 0
\end{equation}
Let us assume that we are player b. We have access to $x_b$ and $y_b$ and we are going to be choosing $r$ and $d$. From the equation above it's then obvious that player b needs information about $x_a$, $y_a$, $x_a^2$ and $y_a^2$, thus player a will now encrypt those values and send them to player b, together with the public key to for the encryption.

Here comes my breakthrough, player b is only able to do addition with the encrypted values we received from player a, thus the terms $rx_a^2$,$ry_a^2$,$-2rx_a x_b$,$-2rx_a x_b$ are impossible for player b to compute. However, if we restrict r to be integers player b can compute $rx_a^2$ and $ry_a^2$ by simply adding $x_a^2$ and $y_a^2$ to themselves $r$ times. In practice this would be multiplying the encrypted values $r$ times (assuming we use Paillier encryption).

This only leaves $-2rx_a x_b$ and $-2rx_a x_b$, which we can solve by letting player a do the actual multiplication. If player b sends:
\begin{equation}
-2rx_b
\end{equation}
\begin{equation}
-2ry_b
\end{equation}
Player a can preform the multiplication. However, we run into the same problem in the beginning, now player a can put a constraint on the position, since we are sending two equations and three unknowns, thus we need to modify what we send to keep our information hidden. Thus player b instead sends:
\begin{equation}
-2rx_b + C_1
\end{equation}
\begin{equation}
-2ry_b + C_2
\end{equation}
Where $C_1$ and $C_2$ are integers. Since they are integers, and we know they are going to be multiplied by $x_a$ and $y_a$ we can do the same trick as before and account for this in our addition of the encrypted values.

Thus the last thing to work out is what to encrypt and send back, which is rather easy. We simply have to account for the added $C_1$ and $C_2$ and subtract them. Thus player b sends:
\begin{equation}
\mathcal{E} (rx_a^2 +rx_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2)
\end{equation}
Where $\mathcal{E}$ stands for "encrypted". There's a note to be made here about speeding up the computation of $\mathcal{E} (rx_a^2)$ which using a naive approach would require us to do $2r + C_1 + C_2$ encryption computations, however this can be sped up considerably by simply adding the newly encrypted sum to itself, thus making the process exponential and reducing the computations down to somewhere above $ log_2 (r) + log_2(max(C_1,C_2))$, but this is only important for the implementation. Later I will represent this type of multiplication with $\times$.

Let's now look at all the transactions which take place:

Player b sends a request to Player a (this step can be skipped if the transactions are continuous)
Player a sends $\mathcal{E}(x_a)$, $\mathcal{E}(y_a)$, $\mathcal{E}(x_a^2)$, $\mathcal{E}(y_a^2)$ and  $\mathcal{E}$.
Player b sends:

$r \times (\mathcal{E}(x_a^2) \mathcal{E}(y_a^2))\mathcal{E}(rx_b^2) \mathcal{E}(ry_b^2)\mathcal{E}(-rd) C_1 \times \mathcal{E}(-x_a) C_2 \times \mathcal{E}(-y_a)$
$-2rx_b + C_1$
$-2ry_b + C_2$

Player a then:

Decrypts the encrypted part to get $[rx_a^2 +x_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2]$
Multiplies $-2rx_b + C_1$ and $-2ry_b + C_2$ with $x_a$ and $y_a$ respectively.
Adds this all together to get:
\begin{equation}
[rx_a^2 +rx_b^2 + ry_a^2 + ry_b^2 - rd - x_a C_1 -y_a C_2] + x_a[-2r x_b + C_1] + y_a[-2r y_b + C_2]
\end{equation}
which Equates to:
\begin{equation}
rx_a^2 +rx_b^2 -2rx_a x_b + ry_a^2 + ry_b^2 -2ry_a y_b - rd
\end{equation}
Player a checks if this value is smaller than 0, if so player a sends it's position to player b, if not it sends a "false" message.

I hope this answer was clear, or at least understandable. When I used the [ ] brackets it was only to notate what came as one number, so from the perspective of player a, everything inside of a bracket is just one number.

A thing to note here is that it's player a can still cheat by just refusing to send the position ( and Player b could for example send vision checks where he shouldn't), but this sort of cheating can be caught by keeping a log of all player positions (and vision checks) throughout the game (or a subset of them to save memory) which when the game is over, or enough time has passed, can be used to verify that neither player was cheating. If a player disconnects suddenly they can just be asked to send their log when they go online again, thus sudden disconnects is not a problem either.


Does $E_{TM}$ accpets the empty word $\varepsilon$?

I would answer that no, $\varepsilon \notin L$.

The reason is that the typical definition of a Turing machine is that its representation should contain a non-empty set of states and a non-empty tape alphabet.

In order to represent those, you typically would need a non-empty string.

However, as Yuval points out, you are free to define your own Turing Machine description language, and if you were to say "We use $\varepsilon$ to denote the "empty" TM (with alphabet 0), the TM that runs forever", you are free to do so, in which the answer becomes Yes.

I would go with No, $\varepsilon \notin E_{TM}$.


Almost the same as Yuval's answer, except...

If I gave you two 1025 x 1025 matrices, you wouldn't extend them to 2048 x 2048. You'd extend them to 1026 x 1026, and use one layer of Strassen's algorithm with 513 x 513 matrices - if you decided that this is faster than direct calculation of a 1025 x 1025 product. One recursion level lower, you'd decide whether your seven 513 x 513 products are faster to calculate directly or as a 514 x 514 product using one layer of Strassen's algorithm and so on.

I very much doubt that Strassen's algorithm will be an improvement for 65 x 65 products. There are fewer floating-point operations, but probably a lot more overhead.

For non-square matrices: If you want to multiply a (100x100) by a (1000x100) matrix, that can be done trivially by calculating ten (100x100) x (100x100) products. Filling up to 1000x1000 would be madness.


Context free language and the complement of it

Sorry, your approach does not work.

Breaking down $L_1$ into two parts is a good idea. Unfortunately you proof these parts are context-free cannot be correct, as one can give a grammar for each of them.

As for the complement, there is no such thing as a intersection rule. The fact that context-free languages are not closed under intersection simply states that there exist two context-free languages the intersection of which is not context-free. The intersection of any random pair of context-free languages can be context-free (e.g., if the intersection is empty).

Back to the drawing board.


Variant of the "Stable Roommates Problem" when room has not 2 but "n" mates

The stable roommates problem is to find a perfect matching in a non bipartite graph which is "stable". "Perfect" means that every one is assigned to a pair. "Stable" means that it does not exist 2 persons which would prefer to be together instead of their assignement. Note that the stable roommates may have no solution.

Now about your problem, the point is to define the "stable" statement on groups of 6 or 8. And as you said, you want to maximize the global affinity score which is quite different from looking for a stable situation.

Globally your problem is a "graph partition" which is NP-complete, and there is no "efficient" way to find a solution better than try all combinations. Some heuristic algorithms can provide very good results nevertheless.


Studies of file access patterns in embedded systems

There is a good paper titled "The Case for Efﬁcient File Access Pattern Modeling" by Thomas M. Kroeger and Darrell D. E. Long. It reviews two classic model for file access pattern "The ﬁrst model is based on a graph, that keeps frequency counts for all ﬁles accessed within a window following an access to each ﬁle. The second model was adapted from the text compression technique ﬁnite multi-order context modeling (FMOC), to track ﬁle access patterns. It uses a tree to keep frequency counts of access patterns, tracking a ﬁnite number of multiple-order patterns."

I think these techniques could be applied for different small scale file systems such as hard disk, flash memory, etc on pc or embeded systems.

This paper "Analysis of Disk Access Patterns on File Systems for Content Addressable Storage" written by Kuniyasu Suzaki, Kengo Iijima, Toshiki Yagi, and Cyrille Artho is also very useful, while the OS of many embedded systems are Linux-based.


Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST

You are definitely on the right track. As D.W. notes, you have to prove two things:

The new tree is a spanning tree.
There is no spanning tree of lower total weight (i.e. minimality).

For (1), consider what it means to be a spanning tree:

Every vertex must be a part of it (this is the spanning part).
It must be a tree (i.e. a connected acyclic graph).

So with your construction, you have a starting MST $T$ for the graph $G$, and you create a new potential MST $T'$ for $G'$, which is $G$ with a single modified edge weight (which may or may not be the added edge).

Is every vertex of $G$ (and hence $G'$) in $T'$?
Is $T'$ connected?

For (2), you want to show that there's no other tree that is better. Proofs of this kind are normally done by contradiction. So start by assume there is a tree $R$ that is a spanning tree of $G'$ and has lower weight than $T'$, what would this imply?

In thinking about this consider what it means for $R$ to be different, and what this would imply for $T$, the original MST.


Yes, an open interval in $\mathbb{R}$ is defined as $(a,b) = ]a,b[ = \left \{ x \in \mathbb{R}|\,a<x<b\right \} $. It has two parameters $a$ and $b$. The sets of all open intervals, i.e. $\left \{  \left \{ x \in \mathbb{R}|\,a<x<b\right \} | a,b \in \mathbb{R}\right\}$ has a VC dimension of 2 for the reason you mention. Keep in mind that the VC dimension of a hypothesis set $H$ is the most points $H$ can shatter.). To put it graphically:

(image from CalTech's free machine Learning online course by Yaser Abu-Mostafa Learning from Data)


How to calculate the total error from an arbitrary hidden layer in a neural network back propogation?

The short answer is yes, $\frac{\partial E_{total}}{\partial w_1} = \frac{\partial E_{j_1}}{\partial w_1} + \frac{\partial E_{j_2}}{\partial w_1}$.

The long answer. The key formula is the chain rule, as D.W. mentioned:

$\frac{\partial E_{total}}{\partial w_1} = \frac{\partial E_{total}}{\partial out_{h_1}} \cdot \frac{\partial out_{h_1}}{\partial net_{h_1}} \cdot \frac{\partial net_{h_1}}{\partial w_1}$

What's good about it is that all three components on the left are local information. No matter what the next or previous layers are,

$\frac{\partial out_{h_1}}{\partial net_{h_1}} = out_{h_1} (1 - out_{h_1})$

$\frac{\partial net_{h_1}}{\partial w_1} = i_1$

Hence, the calculation is the current node depends only on forward messages from direct neighbors to the left and backward messages from direct neighbors to the right:

$out_{h_1}$ and $i_1$ are known from the forward pass, and $\frac{\partial E_{total}}{\partial out_{h_1}}$ is the total backward message.

In the architecture from the post, the node $h_1$ has two direct neighbors to the right: $o_1$ and $o_2$, and that explains the sum $\frac{\partial E_{total}}{\partial out_{h_1}} = \frac{\partial E_{o_1}}{\partial out_{h_1}} + \frac{\partial E_{o_2}}{\partial out_{h_1}}$. In your example, the neighbors are $j_1$ and $j_2$, so it will be the sum  $\frac{\partial E_{total}}{\partial out_{h_1}} = \frac{\partial E_{j_1}}{\partial out_{h_1}} + \frac{\partial E_{j_2}}{\partial out_{h_1}}$. If $h_1$ has even more connections, all of them will pass the backward message and they will be added up.


Does a Context-free language have a grammar that has either 3 or 0 nonterminals on the right hand side?

Hint, can the production rules of that form generate a word  of length 2? Is there a context-free language that contains a word of length 2?


Min weighted edge cover: don't follow proof in Schrijver

Let $M$ be a maximal subset of $F'$ which is a matching. Any vertex $v$ not covered by $M$ must be covered by some edge $e_v=(v,w)$ in $F'$. Since $M$ is maximal, $w$ must be covered by $M$. It follows that if $v_1 \neq v_2$ are not covered by $M$, then $e_{v_1} \neq e_{v_2}$.
The matching $M'$ consists of the two copies of each edge in $M$, and of the edges $(v,\tilde{v})$ for each $v$ not covered by $M$. Edges of the first type have total weight $2w(M)$. Since $w(v,\tilde{v}) \leq 2w(e_v)$, edges of the second type have total weight at most $2w(F' \setminus M)$ (this crucially uses that $e_{v_1} \neq e_{v_2}$ for any $v_1 \neq v_2$ not covered by $M$). Hence $w(M') \leq 2w(F')$.


Preconditions and postconditions are just ways to describe a function in more detail, and give some hints on how you can use this function or what to expect from it.

Preconditions are conditions that have to hold before (pre is Latin for before) the function gets called by a user. These are usually conditions about the parameter. E.g. a simple precondition for the function square_root(x) might be: x has to be non-negative. Because the function cannot handle negative numbers, maybe even crashes, or just return wrong values. But there are even other preconditions. Other preconditions could involve global states, or the state of objects. E.g. before you call this function you need to call another. So the user has to make sure, that all the conditions are satisfied, before he calls the method.

Postconditions are about after the call (again, Latin). That can mean the return value of the function, or the global state of the program or object after calling the function. This are conditions a user can expect from the program. It is kinda like a guarantee, if a user calls the function in a way that satisfies all preconditions, then he will get something that is described in the postconditions.


If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$?

This is an open research question. At our current state of knowledge, knowing $\mathbf{P}=\mathbf{NP}$ would neither imply $\mathbf{L}=\mathbf{NL}$ nor $\mathbf{L}\neq\mathbf{NL}$. And, conversely, knowing $\mathbf{L}=\mathbf{NL}$ or $\mathbf{L}\neq\mathbf{NL}$ wouldn't imply anything about the $\mathbf{P}$ vs $\mathbf{NP}$ question.  (But it's possible that the proof of $\mathbf{L}$ vs $\mathbf{NL}$ would tell us something about $\mathbf{P}$ vs $\mathbf{NP}$ or vice-versa.)

We know $\mathbf{L}\subseteq \mathbf{NL} \subseteq \mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE} = \mathbf{NPSPACE}$, where the equality follows from Savitch's theorem.  The nondeterministic version of the space hierarchy theorem says that $\mathbf{NL}\neq \mathbf{NPSPACE}$ so we know that at least one of the set inclusions must be strict. We kinda think they're all strict but our current knowledge doesn't rule out any subset of them, as long as it includes at least one between $\mathbf{NL}$ and $\mathbf{PSPACE}$.


Which are the most effective sorting algorithms for a large dataset?

quick sort. in C++, it's better to use std::sort rather than qsort(), since it allows compiler to perform much better optimization (both implements quick sort algorithm)
depending on your data, sometimes better: http://en.wikipedia.org/wiki/Counting_sort and http://en.wikipedia.org/wiki/Radix_sort

  simultaneously perform sorts on multiple large datasets?

i've not heard of such algorithms at all. but you can distribute tasks among CPU cores. moreover, you can split one dataset between two cores, and then merge results of sorting


Why is there no one to many Multithreading Model?

Actually, there is such a model, though it is typically not thought of as one of the "multi-threading models."

One to many would mean one thread distributed across many processors.  At first that should look silly.  After all, you only have one thread.  What are the other processors to do?  However, superscalar architectures are designed to do roughly this sort of operation.  In superscalar architectures, instructions are decomposed and the CPU identifies the best ways to do these decomposed pieces in parallel, utilizing as much of the hardware as possible.  As a trivial example, they might do a floating point operation and an integer operation at the same time.  Or they might take both branches of a conditional jump at the same time, only settling on one branch later when data becomes available.

This isn't quite a "multi-threading" model, because there's no crisp clean boundary between CPUs.  In superscalar architectures, the hardware utilization is much more fluid.  But it does accomplish something which is very similar in nature: it executes many instructions from one thread in parallel.


Computational Complexity of a special case of Integer Programming

It is NP-hard, by reduction from 3SAT.

Your problem is equivalent to the following: given a system of inequalities of the form $x \not\equiv A_i \pmod{B_i}$, where the $A_i,B_i$ are given, test whether any solution exists.  (Why?  If $0 < c_i^2 < B_i^2$ then $c_i \not\equiv 0 \pmod{B_i}$, and vice versa.)

Now 3SAT can be reduced to this problem (satisfiability of a system of inequalities), so it follows that this problem is NP-hard.  Here's how the reduction works.

Let $\varphi$ be a 3SAT instance, with variables $v_1,\dots, v_n$.  Let $p_1,\dots,p_n$ be the first $n$ primes.  Add inequalities of the form $x \not\equiv 2 \pmod{p_i}$, $x \not\equiv 3 \pmod{p_i}$, ..., $x \not\equiv p_i-1 \pmod{p_i}$ for each $i$, forcing $x$ to be either 0 or 1 modulo each prime.  Now, suppose we have a clause $v_i \lor v_j \lor v_k$.  This translates to an inequality $x \not\equiv 0 \pmod{p_i p_j p_k}$.  The clause $v_i \lor \neg v_j \lor v_k$ translates to $x \not\equiv \alpha \pmod{p_i p_j p_k}$ where $\alpha$ is the unique value such that $\alpha \equiv 0 \pmod{p_i}$, $\alpha \equiv 1 \pmod{p_i}$, and $\alpha \equiv 0 \pmod{p_i}$ (you can find $\alpha$ using the Chinese remainder theorem).  And so on -- in this way, each clause can be translated into an inequality.

Finally, there exists a value $x$ that satisfies all of these inequalities if and only if there exists an assignment that satisfies $\varphi$.  (Why?  $x\equiv 1 \pmod{p_i}$ corresponds to setting $v_i$ to true, and $x\equiv 0 \pmod{p_i}$ corresponds to setting $v_i$ to false.  You can then verify equivalence between clauses and inequalities.)  Since the resulting system has size polynomial in $n$, this gives a polynomial-time reduction from 3SAT to your problem.


Reference needed: lower bound on sample size for determining which side of coin is biased with high probability

Yes.  You need approximately $\sim 1/|p - 1/2|^2$ observations (that many are necessary and sufficient), assuming $p$ is close to $1/2$.  I've omitted constant factors, but the constant is small.  The exact constant will depend on the degree of confidence you want, but it will vary as something like $\log (1/\delta)$ (or lower): $\delta$ drops exponentially fast in the number of observations.

For more details and analysis, see https://cstheory.stackexchange.com/q/22328/5038.  You might also be interested in https://cstheory.stackexchange.com/a/30938/5038.


minimum number of states in cross product of two minimum DFAs

You probably know that if $\cal A$ and $\cal B$ are DFA, then their product recognizes the language $L({\cal A}) \cap L({\cal B})$. Now if ${\cal A} = {\cal B}$, then $L({\cal A}) \cap L({\cal B}) = L({\cal A})$. Thus if $\cal A$ is a minimal DFA with at least two states, ${\cal A} \times {\cal A}$ is never minimal.


Suppose that you have arrays $A_1,\ldots,A_d$ of sizes $n_1,\ldots,n_d$. The total number of tuples is thus $n_1 \times \cdots \times n_d$. Given a number in the range $1,\ldots,n_1 \times \cdots \times n_d$, you can decipher it into a tuple (I leave this part to you). It now remains to compute a pseudorandom permutation of the numbers $1,\ldots,n_1 \times \cdots \times n_d$, another task I leave to you.


Number of IEEE 754 doubles between two adjacent single-precision floats

Let's consider two made-up number systems: 2-dec and 3-dec. In 2-dec, numbers are specified to two decimal points (in decimal). In 3-dec, it's three. Between, say, 1.2 and 1.3, which are adjacent in 2-dec, we have 1.21, 1.22, 1.23, 1.24, 1.25, 1.26, 1.27, 1.28, 1.29 in 3-dec.

Hope this helps.

As an aside, the answer might potentially depend on whether the numbers are denormalized or not.


Problem with Understanding "correlated attributes into a set of values of uncorrelated attributes" in PCA

It looks like you are using RapidMiner documentation as a medium to study. If that is case, then the best answer to your question and probably to some other questions of yours should be, I believe, a recommendation of related textbook, tutorial or lecture notes.

For the current question, I recommend you to read a tutorial on Principal Components Analysis by Lindsay I Smith, a tutorial that is self-contained and easy to read.

Now let me get back to you question, assuming we have gone through that tutorial up to and including section 3.1 or any equivalent materials.

  What is meant by transforming "correlated attributes into a set of values of uncorrelated attributes" in Principal Component Analysis"?

That just means, given existing $x$ axis and $y$ axis, and a set of data points with their coordinates (a set of observations of possibly correlated attributes), PCA will produce their eigenvectors and, using these eigenvectors as the new $x$ axis and $y$ axis as well as moving the origin to the center of the data points, obtain the new coordinates of those data points (principal components). The crux of the PCA is that the new $x$ coordinates and the new $y$ coordinates of the data points are 2 uncorrelated variables (uncorrelated attributes) in the sense that their covariance is 0. I am talking about 2-dimensional data for simplicity; PCA applies to 3 or more dimension the same way. In higher dimensions, the new coordinates of the data points are a set of variables every pair between which are uncorrelated.

All these concepts become very much alive and easy to understand once you have gone through several end-to-end computations. That is probably the fastest way to understand these concepts.


O(n) time algorithm for maximum earnings

You can use DP for solving this problem.

Let's iterate $i$ from $1$ to $n$ and calculate next values for each $i$:

$m_{i,0}$ - biggest sum of money from plates $j \le i$ which is divisible by 3
$m_{i,1}$ - biggest sum of money from plates $j \le i$ which have reminder 1 after division by 3
$m_{i,2}$ - biggest sum of money from plates $j \le i$ which have reminder 2 after division by 3

Base case:
$m_{0,0} = 0, m_{0,1} = -\infty, m_{0,2} = -\infty$

Iteration:

$k \in [0, 1, 2]: m_{i, k} = m_{i-1, k}$
$k \in [0, 1, 2], m_{i-1,k} \ne -\infty: m_{i, (m_{i-1,k} + a_i)\%3} = max(m_{i, (m_{i-1,k} + a_i)\%3}, m_{i-1,k} + a_i)$

And result will be $m_{n,0}$.


The idea behind the state of Imperative languages

The simplest kind of state is the configuration of memory. In C this memory is accessed through variables (and arrays and pointers, but let us ignore those), so the state is the values of variables.

For example, suppose we have variables x and y whose values are 23 and 42 respectively (and no other variables). Then we could write the state as
$$[x \mapsto 23, y \mapsto 42]$$
If we run the program

x = 1 + y

the state will change to $[x \mapsto 43, y \mapsto 42]$. When we declare a local variable, the state will be extended temporarily with that variable.

There are many other kinds of state, such as:

in an object-oriented language each object has its own state, namely the values of its attributes
a finite state automaton has states, obviously

In general, there is going to be a set $S$ of all possible states. For instance, 1 GB of memory corresponds to $S$ with $2^{2^{30}}$ elements because that's how many states there are for 1 GB of memory. A program which uses state and computes a value of type $A$ can then be thought of as a function $S \to A \times S$: it takes the initial state $s \in S$ and returns a pair $(a, s')$ where $a$ is the computed value and $s'$ the final state.

It is not true that functional languages have no state! The pure functional languages such as Haskell and do not have built-in state, but other functional languages do have state. For instance OCaml and SML both have references, which are just mutable memory locations, so they have state. Racket and Scheme have state as well, and they are functional languages.

Perhaps a clarification is in order: a language is functional if functions are values, which means that we can do with functions whatever we can do with other values (pass them around, make arrays of functions, etc.). For some reason people often confuse pure and functional languages.

Supplemental: Since we're on the brink of a religious war about "Does C++/Java/whatever have first-class functions?", let me throw the first grenade. For a language to be functional the following have to be possible:

Read an integer n from standard input and create a list or an array of functions $[f_1, \ldots, f_n]$ where $f_i(x) = x + i$. This disqualifies C.
Allow function abstractions in the sense that it is possible to create a function based on a function rule, written as $\lambda x . E$, or $x \mapsto E$, or lambda x: E. Very importantly, there must be no scoping limitations on the abstraction, which means that $E$ may refer to any variables that are in scope. This disqualifies Java and C++.

There are fundamental mathematical reasons why function abstraction must be unrestricted. With restricted function abstraction we just don't get what is mathematically called a "function". We get something else, but not functions.


Prove that regular expression is unambiguous

This answer has 3 parts:

I first answer the question as asked,
sketching the beginning of a proof concerning the example given. A
full proof is too long and tedious to be given here.
Then I give a general procedure to solve the problem and decide
whether a regular expression is deterministic/unambiguous.
Finally I discuss some difficulties and problems with the statement
of the question.

A direct answer to the question

What you may first prove, though it should be obvious, is that for any
regular expression $R$, there is a valid mapping of any word $w\in L(R)$
to $R$.

Then you consider the regular expression $R = 0^*(11^*000^*)^*11^*01(1+0)^*$ to be analyzed, and you
procede to decompose it structurally, showing  that at every step,
there is only one way to decompose a string $w\in

For example, you show that there is only one way to decompose a string
$w\in L(R)$ as $w=uv$ with $u\in L(0^*)$ and $v\in
L((11^*000^*)^*11^*01(1+0)^*)$. The reason is that $u$ contains only
$0$, and $v$ begings necessarily with a $1$. So the string $w$ must be
cut just before the first one. Then there is only one way to get a
valid mapping for the whole expression, from valid mapping of the two
subexpressions. If the subexpressions are themselves proved
detrministic, i.e. with only one valid mapping fo any string in their
language, then the whole expression must be deterministic.

Hence you now have to prove only that, $0^*$ and
$(11^*000^*)^*11^*01(1+0)^*$ are deterministic, since their
concatenation has a unique decomposition.

So you go on decomposing the expression into subexpression, such that
you have a unique way of matching them with a string of the language.

The next step is to show there is only one way to decompose a string
$w$ in $L((11^*000^*)^*11^*01(1+0)^*)$, as $w=u01v$, with $u\in
L((11^*000^*)^*11^*)$ and $v\in L((1+0)^*)$

And so on ... For each subexpression, you must perform the analysis
according to the type of the subexpression, following the definition
given for each of the four types in the definition of valid mapping.

In the case of $R=S+T$, where  $S$ and $T$ are subexpressions of $R$, you only have to prove that $L(S)\cap L(T)=\emptyset$.

This gives you the general idea of a proof on a given example, such as the one above.

However, such a proof is very tedious and prone to errors.

So you would be better off designing an algorithm that will decide mechanically whether a regular expression is ambiguous or not. The problem is decidable, and not so hard. I follows the same lines I sketched: recursive decomposition of the regular expression, which things to be checked depending on the operator (concatenation, union, Kleene star).

A procedure to decide ambiguousness of a regular expression.

To decide ambiguousness of a regular expression, one must
recursively decompose the expression into 1 or 2 subexpressions
dominated by an operator, down to the leaf level.

Given a regular expression $R$,

If $R=w\in \Sigma+$, then $R$ is unambiguous;
If $R=R_1+R_2$, then $R$ is unambiguous iff both $R_1$ and $R_2$
are unambiguous, and $R_1\cap R_2=\emptyset$. If the intersection is
not empty, any valid mapping from string to $R_1$ could instead map
validly to $R_2$; hence there would be two valid mappings. Also, if
there were two distinct valid mappings to one daughter, say $R_1$,
then by application of rule 2 of the definition, there would be two
valid mappings to $R$.
If $R=R_1 R_2$, then $R$ is unambiguous iff both $R_1$ and $R_2$
are unambiguous, and there is only one way to decompose any string
$w\in L(R)$ into 2 substrings as $w=w_1 w_2$ such that $w_1\in
 L(R_1)$ and $w_2\in L(R_2)$. $R_1$ and $R_2$ must be both unambiguous
because, as before, if one were ambiguous, say $R_1$ for a string
$w_1$, if would be possible to build two valid mappings for $R$,
which would thus be ambiguous.

But how does one check that string $w\in L(R)$ can be decomposed in
only one way into two substrings
$w=w_1 w_2$ with $w_i\in L(R_i)\text{ for }i=1,2$? This can be
checked by attempting to simulate 2 simultaneous generations of a
string in $L(R)$, such that 2 distinct prefix of the substring will
be associated to $R_1$.

Let $A_1$ and $A_2$ be two FA recognizing $L(R_1)$ and $L(R_2)$,
having (to simplify) one start state and one accepting state.
A FA for $L(R)$ can be obtained by linking then with an empty
transition from the accept state of $A_1$ to the start state of
$A_2$.

Then one can build a new FA $A^2$ by doint a cross product of the
state set of $A$ with itself to simulate 2 computations at the same
time. Both computations must be synchronized so that they scan the
input together, though not necessarily following the same
computational paths for each simulated automaton. Both computations
must at some point cross the linking transition. This is memorized in
the final state so that the double computation ends in acceptance iff
the both reach the final state of $A_2$, but after crossing the
linking transition at different points in the input.

This automaton $A^2$ recognizes the language $\{w\in L(R)\mid
 w=uv=u'v' \wedge u\neq u' \wedge u,u'\in L(R_1) \wedge v,v'\in L(R_2)$

Hence, strings in $L(R)$ can be decomposed unambiguously in two
strings belonging respectively to $L(R_1)$ and $L(R_2)$ iff
$L(A^2)=\emptyset$.
If $R=S*$, then $R$ is unambiguous iff $S$ is unambiguous, and
there is only one way to decompose any string $w\in L(R)$ into a
concatenaton of substrings in $L(S)$.

The technique is similar to the one used for concatenation. You take
a FA $A_S$ recognizing $L(S)$, with a single accept state, and you
connect the accept state to the start state with an empty "looping" transition,
to get a FA $A$ for $L(R)$. Then, you buils a FA $A^2$ that simulates
two computations of $A$ and accepts only when they both accept, but
with the constraint that they must have crossed the looping
transition at least once while being at different points of the input
(or possibly a different number of times).

Again, strings in $L(R)$ can be decomposed unambiguously in a
sequence of strings in $L(S)$ iff $L(A^2)=\emptyset$.

Caveats

Some care must be taken with the empty word $\epsilon$. It is not
clear that the problem is always well defined in this respect.
The empty word $\epsilon$ may be used in regular expressions but will have no
apparent counterpart in strings of the language. They can be ignored,
But then, what of a Kleene star $R=S^*$ when  $\epsilon\in L(S)$.
Should it be considered always ambiguous.

Another point is that the concept of valid mapping is really a mapping
of occurrences of words to occurrences of regular expressions, i.e., to
the syntactic instances, rather than to regular expressions as
abstract concepts.

For example, consider the string $w=011001$ and the regular expression
$R=(01)^*100(111)^*1$. There is a valid mapping $f$ of $w$ to
$R$. However it associates the first instance of $01$ with $(01)^*$,
and the second instance of $01$ with $0(111)^*1$.

What is worse, even considering occurences, $f$ is not a mapping since
it associates the first instance of $01$ with both $(01)^*$ and the
regular expression $01$ to which the Kleene star is applied. Hence
$f$, as it is defined, cannot be considered a mapping.

Actually, it seems that $f$ should be defined as a mapping of $R$ and each
subexpression occurrence in $R$ to
substrings of $w$.

But up to that rephrasing of the problem, everything holds.


How to decide which bytes will form a packet ?(computer networks)

A packet is a sequence of bytes. Nothing more, nothing less.

When transmitting packets, a signal is formed in such a way that boundaries between packets are easily identified, and that the bytes forming the packets can be transmitted and decoded by the receiver.

Electrical signals at high frequencies must be formed in such a way that they are not damaged during transmission. A digital signal (low signal = 0, high signal = 1) at high frequency has no chance to survive transmission because of higher frequencies added by sharp signal changes.

In addition, information for error detection and correction is added before transmitting and checked + removed after receiving the signal, so a package that is sent cannot only be received, but checked for correctness.

(The actual way the signal is formed will only be known by a handful of highly specialised engineers. It's no secret, just very difficult and not of any interest to most people. As I said in a comment, "applied magic").


Give the Regular-Expression (NFA) with specific Separation Patterns

I'll assume that no $a$s can appear together without interruption by a group of $(bb)^+$s, even if they form a group of odd $a$s. In that case
$$
a(bb)^+ (a(bb)^+ a(bb)^+)^*
$$
should suffice, where $x^+$ is defined simply as $x^+ = x x^*$.


Build a regular expression to define a regular language

One way to do it by hand, in such a simple case, would be to build a FA for
condition 2, i.e. strings that start with $1a$, and another FA for
condition 3, i.e. strings that contain $aa$.  Both FAs have only 3
states.

Then you use the intersection construction to have an automaton that
obeys both conditions. That remains simple enough if you organize your
state pairs as a 3 by 3 matrix.

From that you can easily deduce a regular expression:
 $1(a+a(a+b+1)^*a)a(a+b+1)^*$

Your solution can be proved consistent (compliant with the stated conditions) with a case analysis over the two main star operators (cases depending on whether there is zero occurrence or at least one). One also has to prove it is complete, i.e. that it does cover all compliant strings.

If you have a constraint regarding the use of parentheses, you should state it in your question. Is there a reason for the constraint ?

Find more details in the answer to your other question about this language, and a comment on how to better write the question.


Double-nested loop with bitwise operation

The number of foo() calls is the number of 1 bits in all numbers from 0 to $n$ (or all even numbers between $0$ and $2n$ - same thing). Asymptotically, it's $O(n \log n)$, because the number of 1 bits is around $\log_2(n)/2$.

I don't have an exact function. It won't be a smooth function - for example, $f(1023)-f(1022)=10$, but $f(1024)-f(1023)=1.$


Hash for verifying both compressed and uncompressed data?

In most situations you probably don't want to have D and compress(D) to have the same hash value, as that leads to hash collisions.  Usually hash functions are designed to avoid hash collisions -- and this is a good thing.  For instance, in cryptographic contexts, any hash scheme that has the properties you ask for would automatically be considered cryptographically insecure.

Therefore, trying to design a hash function with this property is probably a bad idea.  Instead, you should probably use the alternative solution: when you verify a hash value, hash both the data D and the compressed version compress(D) and see if either of those hash digests match the expected value.  That's probably a much better solution in practice.

If you absolutely must achieve this by artificially introducing collisions into your hash, here is a way you can do it.  Disclaimer: This is totally theoretical; it is not useful in practice.

Define the verify procedure as follows:

Verify(D, Y):
1. If Hash(D)==Y or Hash(Compress(D))==Y or Hash(Uncompress(D))==Y, return true; otherwise, return false.

Yes, this is totally trivial.

No, I don't think you'll find anything that is faster than this and that also satisfies the properties to be a good hash function.  Hash functions are specifically designed to avoid having any mathematical structure, while at the same time being very fast.  Mathematical structure is considered a weakness in a hash function.  In contrast, you are asking for a hash function with some structure.  Inserting such artificial structure into the hash function might be possible, but the natural ways of doing it probably will either introduce lots of bias into the hash function (e.g., lots of collisions) or slow it down a lot.

To put it another way, right now hash functions are optimized to meet two criteria:

Be fast.
Be "random-looking" (few collisions, unbiased, etc).

You are proposing to look for a hash function that meets three criteria:

Be fast.
Be "random-looking" (few collisions, unbiased, etc).
Also, satisfy the additional properties you requested that verify(compress(D), getHash(D)) == verify(D, getHash(compress(D))) == verify(D, getHash(D)) == true.

Obviously, it's harder to meet three criteria than to meet two.  If you want to meet three criteria, something will have to give: and in your situation, that means the resulting hash function will either be slower or less "random-looking" than standard hash functions (probably significantly so).

So, I don't expect there's any better solution for what you want.  Instead, just do the natural solution you mention of hashing twice.


CFGs: detecting infinitely many derivations of a single string

If a nonterminal can derive itself ($A \to A$) then you can have an infinite number of derivations deriving whatever else that nonterminal can derive. There is no need for it or any other nonterminal to derive $\epsilon$ (unless you are only concerned with an infinite number of parses for the empty string.)

In other words,

$$A \to A \mid a$$

can produce infinitely many parses for the string $a$. By contrast,

$$A \to A A \mid a$$

can only produce exponentially many parses for the string $a^n$.

As far as I know, the existence of a useful nonterminal which can (possibly indirectly) derive itself is necessary and sufficient for the existence of an infinite number of possible parses.

It's easy to detect whether a nonterminal can derive itself. First, use the standard algorithm to find all nullable nonterminals. Then define the relation
$$ R = \{ (A, B) \mid A \to \omega B \chi \wedge \omega \to \epsilon \wedge \chi \to \epsilon \}$$
which you can do in linear time by scanning all the productions keeping track of nullability.

Then construct $R^+$. If it contains $(A, A)$ for any nonterminal, you have a possibly indirect self-derivation.


What are efficient data structures for inserting and accessing elements?

A balanced binary tree should meet your needs.  You can achieve $O(\lg n)$ time for both operations, as long as the tree is kept reasonably balanced.

To support the "access by index" operation, you can augment the tree so that each internal node contains the number of children underneath it.  Insert operations still take $O(\lg n)$ time (find the place where to insert a new leaf, then traverse the path from that leaf to the root, incrementing the counter in each such node).  The "access by index" operation can be done using the counts in each node; they tell you at each stage whether to recurse to the left child or right child.

There are probably other data structures as well, but this should meet all of the requirements you listed.


Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?

Because the actual running time (in seconds) of real code on a real computer depends on how fast that computer runs the instructions and how fast it retrieves the relevant data from memory, how well it caches it and so on. Insertion sort and quicksort use different instructions and hava different memory access patterns.  So the running time of quicksort versus insertion sort for any particular dataset on any particular system will depend both on the instructions used to implement those two sorting routines and the memory access patterns of the data.  Given the different mixes of instructions, it's perfectly possible that insertion sort is faster for lists of up to ten items on one system, but only for lists up to six items on some other system.


The oracle runs in a single step. Yes, it would take an ordinary Turing machine some number of steps to read the input but an oracle isn't an ordinary Turing machine – that's almost the whole point of using them. Also, the time taken for the oracle to read its input is essentially accounted for by the time it took the calling machine to write that input.  So, oracles return in $O(1)$ steps. More precisely, they return in exactly one step.

Also, it's not quite clear what you mean by "$O(n)$ steps". $n$ usually denotes the length of the input we're trying to compute on, which would be the input to the calling machine, not the oracle. The input to the oracle could be arbitrarily long.  For example, you could have a machine that takes an input $x$ and calls an oracle to ask if the string consisting of $2^{2^{2^{|x|}}}$ zeroes is in the language decided by the oracle. Moral of the tale: don't write functions of $n$ without saying what $n$ is.


If a language is m-reducible to a regular language, does it mean that this language is also necessarily a regular language?

The answer to your question is no. There's a general result you can use in this case:

Theorem. If $A$ and $B$ are any decidable languages and $B\ne\varnothing$ and $B\ne\Sigma^*$, then $A\le_\text{M} B$.

This says that any nontrivial decidable languages are mapping reducible to each other. In other words, mapping reducibility tells you nothing about decidable languages.

Here's an example. Let $L=\{0^n1^n\mid n\ge 0\}$. This is a well-known non-regular language. Now let $R$ be, say the regular language $\{0\}$. Then $L\le_\text{M} R$ by the mapping $f:\{0, 1\}^*\rightarrow\{0, 1\}^*$ defined by
$$
f(s) = \begin{cases}
0\quad\text{if $s=0^n1^n$ for some $n\ge 0$}\\
1\quad\text{otherwise}
\end{cases}
$$
It's obvious that $f$ is Turing-computable and that $s\in \{0^n1^n\} \Longleftrightarrow f(s)\in R$, which is exactly what you need to show that this non-regular language is mapping reducible to this regular language.


You can naively compute ALL-SAT in $2^npoly(n,m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. You clearly need $\Omega(2^n)$ time in the worst case just to write down the assignments (in the case of a tautology). If the strong exponential time hypothesis (SETH) holds, then this is not much harder than SAT itself, so under SETH the complexity of SAT, ALL-SAT, #SAT is the same (up to polynomial factors).
Moreover, without SETH you can claim that given access to a $\#SAT$ oracle, you can output all satisfying assignments in time $k(\varphi)poly(n,m)$ where $k(\varphi)$ is the number of satisfying assignments for $\varphi$ (just see if the number of satisfying assignments changes when substituting $1$ or $0$ to some variable $x_i$). This also shows that in some sense ALL-SAT is not much harder than $\#SAT$.


When two siblings in a heap are equal, how do you bubble down?

Picking either should work. The heap property (assuming you have changed it to mean parent $\le$ children) will not be violated.


How exactly MOV AX will load data from RAM?

I am not sure if this is actually on-topic here, but anyway.

The main memory in x86 architectures is addressed byte-wise. If you want to retrieve 16 bits from address 2000h (note that AX is a 16 register), then you will need to read 8 bits from 2000h and 8 bits from 2001h. This is why the operation needs to read "2 cells". Note that the term "cell" is not the correct one, as it typically refers to individual 1-bit memory units without addressing logic.

Note that the processor actually doesn't read the two bytes separately. Rather, the content from bytes 2000h and 2001h are fetched at the same time as the data bus to cache and main memory is >8 bits and the addresses you have here as examples are aligned, so the underlying architecture supports the parallel read.


No, a dynamically allocated array is created when the program creates it, in the size the program wants to create it, and it exists until the point of time when the program destroys it.


Monitors and Semaphores are to accomplish the same task, to ensure that between n processes/threads that each enter their critical section atomically. Although Monitors go towards a Object Ordinate Approach to this, making the code easier to read for example. In this case a Monitor is at a higher level then a Semaphore. You can use a Semaphore to implement a Monitor. In that case a Monitor has a counter variable in the same way a Semaphore does.

The V and P of a Semaphore is very much like the wait and signal of a Monitor. In which wait and signal are used on a Monitors condition variables. They can be used to implement the same functionality of a Semaphore. Even though there are some minor differences, such as for signal with no process in need of being unblocked there is no affect on the condition variable. Along with that locks are also used within the procedure.

While in most cases you don't want to. You can use a Monitors condition variables and lock outside of it (monitor.lock,monitor.condition_i), basically doing the normal things we do within a procedure but on the outside, not within it's function. This is assuming you want to have the critical section outside of the monitor, otherwise there is no need in doing this:

// monitor enter
monitor.lock.acquire();
while(...)  monitor.condition_i.wait( monitor.lock );

runCriticalSection();

// monitor exit
monitor.condition_j.signal();
monitor.lock.release();


algorithms, number of instructions in the code

The factors of $\tfrac12$ come from the fact that $1 + \dots + N = \tfrac12N(N+1)$.

j is incremented at the end of the loop. This is standard syntax for languages such as C and Java.


Determining Language from Context Free Grammar

Structural induction would prove the following:

All words generated from $S$ have the same number of 0s and 1s.
All words generated from $A$ have an excess of one 0.
All words generated from $B$ have an excess of one 1.

Presumably the reverse is also true, but I'll leave such pondering for you.


pseudo-polynomial reduction from 3-Partition to Partition

The claim

  It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is strongly NP-complete, and $\Pi' \leq_{pp} \Pi$, then $\Pi$ is strongly NP-complete.

is wrong (at least for how "pseudo-polynomically reducible" is defined here).

If $\Pi'$ is strongly $NP$-complete, then ``pseudo-polynomially reducible'' is equivalent to polynomially reducible.

Recall that a problem is strongly $NP$-complete if it is $NP$-complete even if we assume all the integers that appear in the input are polynomial in the length of the input.

Recall that an algorithm runs in pseudopolynomial time if it runs in polynomial time in the integers that appear in the input.

So, a pseudopolynomial reduction must run in time polynomial in the integers that appear in the input. Which, for a strongly $NP$-complete problem, can be assumed to be polynomial in the length of the input. Which means the reduction must run in time polynomial in the length of input.

So, if $\Pi'$ is strongly $NP$-complete, $\Pi' \leq_{pp} \Pi$ is equivalent to $\Pi' \leq_p \Pi$. Clearly, the existence of such a reduction does not imply that $\Pi$ is strongly $NP$-hard.

The only place in the literature that I can find any mention of this notion of ``pseudopolynomial reduction'' is in the appendix an OR & Management Science book. I cannot find any other literature mentioning this notion; one would expect to be able to find some mention of it in complexity theory circles.

We should use a different definition for $\leq_{pp}$. A pseudopolynomial reduction should be defined as a reduction, running in pseudpolynomial time, that in addition does not increase integer values in the input more than polynomially. Then the claim would hold true.


Autocorrect algorithm - How to implement a decent "apostrophe & elision" feature?

You've asked two questions: about what algorithm can be used, and how it is implemented in Android.  Only the former is on-topic here, so I'll answer the former.  (Also, our guidelines are that you should generally ask only one question per post.)

Suppose French has the rule that the two words "X Y" are always replaced by an elided single-word replacement if X is one of ce, je, ne, me, te, se, le, la, de, que, or si and if Y starts with a vowel or silent "h".  I don't know French well enough to know if this is indeed the rule, so I'll assume that's how French works.

To suggest elisions, you could precompute a mini-dictionary of all words Y that start with a vowel or silent "h".  Then, it is easy to search all text entered to see whether it contains a pair of words of the form "X Y" where X is one of ce, je, ne, me, te, se, le, la, de, que, or si and Y is in the mini-dictionary.  If you find such a pair, then you can programmatically generate the correct elision and automatically suggest it.  This should be straightforward to implement.

Precomputing the mini-dictionary should be feasible.  It should be easy to find a dictionary of all valid French words and identify which ones start with a vowel and which ones start with an "h".  The trickiest bit is you'll need a way to identify all French words that start with a silent "h".  I don't know enough about French to know whether there's a clever way to do that.  However, a brute-force method is probably sufficient: I expect it would be sufficient to do it manually (list all words that start with a "h" and identify which have a silent "h"), or crowdsource it (something like Amazon Mechnical Turk, targeted at native French speakers).  This only needs to be done once, so generating the mini-dictionary should be feasible.

I'll also mention a complementary method that's probably also worth adopting.  Compute the list of all elisions, as above (by iterating over all valid pairs "X Y" that will trigger elision, then programmatically computing the correct elision).  Then, add each possible elided form listed above to your spelling dictionary.  In other words, extend your dictionary to include all valid elisions that can ever be encountered.  This may be a useful supplement to the method above, as it will help detect typos when people try to type in the elided form but make a small mistake.

These two methods are complementary.  In particular, if someone types the unelided form (e.g., "Ce est"), the first method above will auto-suggest correcting that to the elided form ("C'est").  And, if someone tries to type the elided form but makes a typo (e.g., "C'ext"), the second method will auto-suggest how to correct the typo ("C'est").  You can decide whether both of those problems are important to solve, or whether you only want to solve one of these two problems, and use that to determine which of these methods to implement.


This problem is as hard as comparison sorting, given n input number sort them.

You can make interval set from input number set $S$ (w.l.o.g suppose input numbers are in $Z^+$) as follow:

$ \Gamma = \{(a,b) \mid a\in S \wedge b=\max_{t\in S} \{2\cdot t - a + 1 \} \}$

Above transformation can be done in $O(n)$.

But if you find a nesting relation in this interval set in $o(n \log n)$, you can sort input array in $o(n \log n)$, But comparison sorting barrier is $\Omega(n \log n)$, So the algorithm which finds interval nesting cannot be better than $\Omega(n \log n)$ with respect to comparision sorting barrier, But also $O(n \log n)$ algorithm is trivial.


NFA models with characters on nodes, not edges

Hyperscan chief architect here.

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

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

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

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


Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm'

Here is a Python function that is about as simple as possible and as fast as possible, assuming the input is valid.

def find_nb(m):
    return int(math.sqrt(2 * (math.sqrt(1.0 * m))))

If the input can be invalid, such as 10252519345963644753026 in the question, and the function should return None accordingly, the Python program can be the following.

def find_nb(m):
    # Use float since math.sqrt is wrong for big integers.
    target = int(math.sqrt(2 * (math.sqrt( 1.0 * m))))
    # or target = int(1.4142135623730951 * m ** 0.25)

    if (target * (target + 1) // 2) * (target * (target + 1) // 2) == m:
        return target
    else:
        return None

What is happening? According to Daniel Castle's comment, for $m\ge1$,

$$ n=\frac{-1+\sqrt{1+8\sqrt{m}}}{2}=\frac{-1}2+\sqrt{\frac14+2\sqrt{m}} $$
It can be checked easily that  $$ n + 0.4 < \sqrt{2\sqrt m} < n + 0.5$$

That means, $n = \lfloor \sqrt{2\sqrt m} \rfloor$ with plenty of room to prevent an error.


What is the generating function for the sequence $\{kH_k\}_{k \geq 1}$

We know that a generating function for the Harmonic series is:

$$
\sum_{i =1}^{\infty} H_i z^i = -\frac{\log(1-z)}{1-z}
$$

you may verify it by taking the MacLaurin expansion.

Taking the derivative with respect to $z$:

$$
\frac{d}{dz} \left ( \sum_{i =1}^{\infty} H_i z^i \right ) = \frac{d}{dz} \left ( -\frac{\log(1-z)}{1-z} \right )
$$

yields:
$$
\sum_{i = 1}^{\infty} iH_i z^{i-1} = \frac{1 -\log(1-z)}{(1-z)^2}
$$

Notice that LHS is exactly the formal series you mentioned.


Maximise sum of "non-overlapping" numbers in square array - help with proof

Actually, I don't believe your proposed solution is correct. An example where you might need this case

|   #    |
| #   # #|
| #   # #|
| #   # #|

might be

| 1 2 1 1|
| 2 1 1 1|
| 1 1 1 2|
| 1 1 2 1|

The optimal solution consists of all 2s, while there are only 1s in the corners; therefore, you cannot find an optimal solution just by starting at the corners.


Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time

Let $n$ denote the length of the array. We will find the largest $N$ such that there are at least $N$ elements whose value is at least $N$.
Make a pass through the array, counting the number of elements of value $1,2,\ldots,n$; if any element has value larger than $n$, count it as $n$.
Using this, determine, for each value $m \in \{1,2,\ldots,n\}$, the number of elements whose value is at least $m$.
Now you can easily determine the solution.


If a language has any single occurrence of a letter, is it not context-free?

No: context free languages are closed under union, so for any CFL language $L$, we have $L \cup \{ a \}$ is context free, for any letter $a$.

The trick is that, when applying the pumping lemma, we don't get to choose the length $L$.

For a finite language, you just choose $L$ to be larger than any word in the language, and the pumping lemma trivially holds. (Remember, $a \implies b$ is true whenever $a$ is false).

As an intuition, you can see the "length" part of the lemma as being how long of words we need to get to a part of the automaton with loops, or a part of the grammar with recursion. So the small examples will in general not affect the pumping property.


Proof by Reduction: From Empty Language to Halting Problem on Empty Input

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

$H$ is Turing-recognizable but not co-Turing-recognizable.

$E$ is co-Turing-recognizable but not Turing-recognizable.

Their undecidabilities are of different kind. So we need to reduce $M$ to $N$ in such a way that:

$\langle M \rangle \in E$ if and only if $ \langle N \rangle \not\in H$.

Consider the following reduction from $M$ to $N$. Turing Machine $N$ on empty input will simultaneously generate all input and run $M$  as a universal Turing Machine on that input (again simultaneously) and halts (either accept of reject, doesn't matter) if some simultaneous thread of $M$ accepts on some input. On non-empty input it does not matter what $N$ will do.

We can easily see that if $M$ does not accept anything then it implies $N$ will never halt on empty input.
If $M$ accepts something then it implies that $N$ will halt on empty input.

Therefore, $\langle M \rangle \in E$ if and only if $ \langle N \rangle \not\in H$.

So, we have got a Turing  reduction (in fact, a polynomial time Karp reduction).

$E \leq_M \overline{H}$


Multiple choice knapsack dynamic programming

It turned out we can achieve it in $O(nM)$ time where $n$ is the number of distinct items in the store, and $M$ is the final bill.

We can build a 2-dimensional array with size $C[T, M]$ as follows:

$C[i, j] = 1$, if there exists a way to add items from $\{t_1,t_2,...,t_i\}$ that adds up to $M$.

$C[i, j] = 0$, if we cannot find items that adds up to $M$.

Finally, it's useful to use one extra row and column to make the calculation easier in the recursive solution.


Encoding the sequence 0110 and determining parity, data bit and value

Well, these examples are not easy to read, by they are indeed correct.

e.g.1:

The word to code has 4 bits, and lets call them $b_1 b_2 b_3 b_4$.
To this "data" word add 3 parity bits
(adding is over $GF(2)$):

$p_1 = b_1 \oplus b_2  \oplus b_3$,
$p_2 = b_1 \oplus b_2 \oplus b_4$, and
$p_3 = b_1 \oplus b_3 \oplus b_4$.

[remark: for odd parity, add "1" to each equation, e.g., $p_1 = b_1 \oplus b_2  \oplus b_3 \oplus 1$]

Then we transmit the code word

$$C= b_1 b_2 b_3 p_1 b_4 p_2 p_3$$

Why this particular order? They want  the "position" of the parity bits to be "1" "2" and "4" (starting to count from the right side) which corresponds to bit positions "001" "010" and "100". This is meaningful in order for the decoding to work as they demonstrate.

You can see by the colors which parity bit belongs to which data-bits.

(Awful explanation in my eye, but, oh well.)

as for the decoding: e.g. 2

the procedure to decode is the following:

recompute $p_1, p_2, p_3$ from the received $b_1b_2b_3b_4$
if you got the same values as the received codeword (the $p_1,..$ you received) - then everything is fine
Otherwise - the error is located in position $x$ where $x$ is the sum of locations of the parity bits $\{1,2,4\}$. For instance, if only $p_3$ is incorrect, than the error is in bit no "1" - $p_1$ itself is the only one got flipped. If $p_3$ and $p_1$ mismatch, than you need to flip the bit in location $1+4=5$, that is, $b_3$.

Note that this code fixes only a single error.


How to convert statement with the existential quantifier to statement with universal quantifier?

Let's give names for the atom formulas:

$n>1$ will be $\phi$ and $x(n) \neq 1$ will be $\psi$
Now what we have is:
$$\exists{n} (\phi\rightarrow\psi)$$
$$\exists{n} (\neg\phi \lor\psi)$$
$$\neg\neg \exists{n} (\neg\phi \lor\psi)$$
$$\neg\forall{n} \neg(\neg\phi \lor\psi)$$
$$\neg\forall{n} (\phi \land \neg\psi)$$
$$\neg\forall{n}((n>1) \land \neg(x(n)\neq 1))$$
$$\neg\forall{n}((n>1) \land (x(n) = 1))$$


Decidability of Turing machines that never move their heads past any input string

The halting problem, $\mathsf{HALT}$ reduces to $\overline{L_2}$.

Given a TM $T$ and input $w$, create a new TM $N$ that on any input of length $n$, simulates $T$ on input $w$ for $n$ steps and then stops except that if $T$ ever halts before $n$ steps, $N$ will move its head to the right forever.

There is a gap in the above reduction. When $N$ simulates $T$ on $w$ for $n$ steps, it may move out of the input when it moves left (we assume that input is put to the right of the origin, the initial position of $N$'s head, inclusively). This gap can be resolved by the classic trick of "translating the tape". When the simulation is about the move to the left of origin, let $N$ translate the current of the tape one cell to the right. Then $N$ goes to the origin, as if it were the cell to the left of the origin. In this way, we will make sure $N$ will never move out of the input string as long as the simulated $T$ on $w$ does not halt. (To enable $N$ to recognize the origin, it should always mark the origin with a "compound" symbol that also tells its original symbol. For example, if the original symbol at the origin is $A$, $N$ should change it to $A_o$, a symbol that is not $A$ but points to $A$. "Compound" symbols are also used when $N$ translates the content of the tape.)

Since $\mathsf{HALT}$ is not decidable, $\overline{L_2}$ is not decidable. So, $L_2$ is not decidable.


Amortized analysis - adding operations to a data structure

I don't know much about the amortized running time of binomial heap, but after reading Wikipedia, I suspect the following might be true: the amortized time of a long sequence of consecutive insert operations is $O(1)$; but this is only true for consecutive insert operations that don't have any other operations mixed in.  Based on that, I wouldn't really summarize the running time of a binomial heap by saying that insert takes $O(1)$ amortized time, without further caveats.
As you quite astutely point out with your example based on a binary counter, the amortized running time of an operation depends on the full set of operations that are allowed to be performed.  So I suspect that the resolution is that the claim about the amortized running time of inserts into a binomial heap wasn't quite right, or had some additional caveats.  I don't know that for sure, as I don't know much about binomial heaps, but that would be my running hypothesis at this stage.