In the questions above, we are saying that a special case of any of the problems above are NP-complete complete. This seems like a misnomer though. Shouldn't this be a specialization rather than a generalization?

No.  The problem you are proving NP-complete is a generalization of a known NP-complete problem.  E.g. the MAX-SAT example contains Boolean satisfiability; just set $g$ large enough to demand satisfaction of all the clauses.

Another part of my confusion is how these so-called generalizations compare or contrast to reductions. Are we saying that some (special) version of a problem is NP-complete and therefore all the other instances are NP-complete? I thought that we needed to show that all instances of the problem are the NP-complete problem.

No, we're saying that if an NP-complete problem can be specified using the rules that describe a different problem without changing those rules, then that different problem is NP-hard, and is also NP-complete if that different problem is in NP.

Regarding the direction of reductions: we reduce from a NP-complete problem (the hard problem) to the problem that we have at hand. For example, in the reduction from 3SAT to independent set we reduce from 3SAT that we know is NP-complete to what we have at hand, the independent set - did I misunderstand? Are these reductions generalizations? I thought that they were for all instances of the independent set.

No, you should just think of reductions as reductions.  A generalization of an NP-complete problem contains that problem as a special case within the generalized problem.  A reduction provides a way to go from an instance of one problem to an instance of another without regard to whether one problem is a special case of another.

Are generalizations reductions?

No, they are an expansion of the original problem that still contains the original problem.  E.g. Boolean satisfiability is a generalization of 3-satisfiability because 3SAT is contained within the expanded problem set.


Is string spliting formally defined when the string delimiter is an empty string?

Given sequences $A = [a_1, \ldots, a_n]$ and $B = [b_1, \ldots, b_m]$, write $A + B = [a_1, \ldots, a_n, b_1, \ldots, b_m]$ for their concatenation. Given a sequence of sequences $C = [C_1, \ldots, C_n]$, write $\Sigma(C) = C_1 + \cdots + C_n$ for their concatenation.
Define a splitting of a sequence $X$ by a sequence $Y$ to be a sequence of sequences $Z = [Z_1, \ldots, Z_k]$ such that $Z_i \neq Y$ and $Z_i \neq []$ for all $i = 1, \ldots, k$, and
$$X = \Sigma [Z_1, Y, Z_2, Y, z_3, \ldots, Y, Z_k].$$
For example, $[[a], [], [b, c]]$ is a splitting of $[a, u, v, u, v, b, c]$ by $[u, v]$.
Splitting by the empty sequence is not unique: $[a, b, c]$ may be split by $[]$ in several ways, among others $[[a],[b],[c]]$, $[[a,b], [c]]$ and $[[a,b,c]]$. From a theoretical point this is a rather trivial and non-interesting observation. The implementors of various string libraries need to deal with splitting by the empty sequence somehow, and as you show, they do.


Efficient algorithms for checking non-emptiness of the language of a Turing machine

The problem is undecidable. There are no algorithms for it, so there are no efficient algorithms.


Hypothetical question on floating point normalization

So first off, the implicit digit to the left of the radix point is not called an "integral". That's a very confusing use of that word. But I digress.

Having an unnormalised representation for floating-point numbers may simplify the final step of any basic floating point operation, because you don't need to re-normalise the result. But in turn, the initial steps of just about every floating point operation become more complex.

Let's take division as an example. Most modern floating-point hardware use Goldschmidt's algorithm, which is based on this idea:

Suppose that we want to calculate $\frac{n}{d}$, where $d$ is close to (but not equal to) one. Then we multiply both the numerator and the denominator by $2-d$.

Suppose $d = 1 + \epsilon$, then the new division problem is:

$$\frac{n}{1+\epsilon} = \frac{n(2-d)}{(1+\epsilon)(1-\epsilon)} = \frac{n(2-d)}{1-\epsilon^2}$$

This results in a denominator which is quadratically closer to 1. Repeat this operation until it gets close enough.

So Goldschmidt's algorithm works as follows. To calculate the quotient of two floating point numbers:

$$\frac{m_1 \times 2^{e_1}}{m_2 \times 2^{e_2}}$$

where $m_1$ and $m_2$ are between 1 and 2, we use a lookup table to find an approximation to $\frac{1}{m_2}$, which we will call $R$. Then we calculate:

$$n_1 = m_1 R$$
$$d_1 = m_2 R$$
$$n_{i+1} = n_i (2-d_i)$$
$$d_{i+1} = d_i (2-d_i)$$

and when we have done enough iterations (say $j$), we return:

$$n_j \times 2^{e_1 - e_2}$$

The final step will involve normalisation; $n_j$ will not, in general, be between 1 and 2. So if we could have unnormalised floating point numbers, the final step will be a bit simpler.

But in return, the table lookup operation will be more complex. With normalised numbers, you can just use the first few bits of the significand. ("Significand", incidentally, refers to the part of the mantissa that is actually stored in a normal floating-point number, without the implicit leading 1.)

So in that sense, there is no advantage to having an unnormalised representation for floating-point numbers. What you gain in a simpler final step you lose by having more complex initial steps.


Do theorem provers demonstrate their own correctness?

I recommend reading Pollack's How to believe a machine-checked proof. It explains how proof assistants are designed to minimize the amount of critical code.

There are many levels of formal verification (that's the phrase you're looking for in place of "proven") of a proof assistant:

Verify that the algorithms used by the proof assistant are correct.
Verify that the implementation of (the critical core of) the proof assistant is correct.
Verify that the compiler for the language in which the proof assistant is implemented is correctly designed and implemented.
Verify that the hardware on which the proof assistant runs is correctly designed and built.
Compute the probability that a cosmic ray passes through the CPU and tricks your proof assistant every time you run it.
Estimate the likelihood that you are insane.

People put serious effort into these (well, at least the first four). For example,
steps 1 and 2 are addressed in Coq Coq Correct!, and steps 3 and 4 in the amazing award-winning CompCert project.


A question about proving Rice's Theorem by reducing it to the Halting Problem

However, as far as I know, the impossibility of the Halting [Problem] only occurs if the program checking whether something halts or not is trying to prove the hypothetical does_it_halt(a, i) wrong by using self-referencing tricks. But, in this proof, the oracle that is trying to decide the property is not trying to do that. So, it should be able to do its job without solving the Halting Problem.

The proof shows that, if we had a machine $M$ to decide a nontrivial semantic property, we can craft another machine $N$ to solve the Halting problem.

With "$N$ solves the Halting problem" we mean that $N$ can decide the termination of absolutely any other Turing machine, including those using "self-referencing tricks" -- no exceptions.

In a nutshell, "for all" means "for all". If we show that a machine decides a problem, then it must always do its job on all inputs. The mentioned proof crafts a machine $N$ which does not "decide the Halting problem, except for self-referencing cases" (whatever that might actually mean in formal terms). $N$ is proved to work "for all" inputs.

By the way, it's a common misconception to think that we actually detect when a program is "self-referencing", and that we could work around the impossibility of deciding the halting problem by weakening the goal to "decide whether $T$ halts on input $x$, as long as there is no self-referencing". What actually happens is that there are infinitely many machines $U$ equivalent to $T$ we could use for the "self-referencing", and
(by Rice!) deciding whether $T$ and an arbitrary $U$ are equivalent or not is impossible. No algorithmic "syntactic inspection" on two programs can hope to decide whether they are equivalent on all cases.

Indeed, at first the self-referencing trick looks as a quite unsatisfactory negative proof, making one think that it could be worked around easily by just excluding that case. However, it is far more general than it looks at first.


OOP: exampe and references on constructor anomalies

"Constructor anomaly" is not a bug or anything; it is simply an anomaly on the classification of constructor functions. ie. constructor functions are different from member functions in the following ways.

Anomalous classifications:

While most member functions require an instance and work on an instance, a constructor does not require an instance, but still works on an instance:

  f.bar(); // instance of f, can call bar(). bar() does stuff to/with f.

  new F(); // no instance, yet called F::F(). Yet F::F() does works on an instance.

Most member functions can replace or extend their base-class functions with the same name; that is, a member function can entirely override a base-function (replacement), ...   or ... it can override, and call the base function as well (extension). However, the constructor (in these languages) must extend, that is, call the base-class constructor first. (This is to delegate the base-class's construction to the base-class, first, and then construct the derived class):

struct F{
    F(){/*stuff*/}
    virtual void bar(){/*stuff*/}
    virtual void baz(){/*stuff*/}
};
struct G : public F{
    virtual void bar()
    {
      //Do stuff
      F::bar(); // extend F::bar()
      //Do more stuff
    }
    virtual void baz()
    {
      //Do stuff
      //Do more stuff
      //No call to F::baz(), replaced it
    }
    G::G(){
      //this MUST extend F::F(); in C++ F() is called implicitly in this case.
      //However, if F() takes parameters, it must be called explicitly
    }
};

Most member functions can be dynamically bounded; that is, you never know if a (virtual) function F* f; f->bar() is calling F::bar() or if f is a type that derived from F; and thus a different bar is being called. However, constructors are always static, you must know exactly which class you are creating when you create it:

H* h = get_h();
h->bar(); // this function can be H::bar(), or anything defined in the virtual table; hence it is dynamic; h can be any derivative of H, overriding H::bar().

F* f = new F(); // the call to F::F() MUST be (statically) linked to F(), not a derivative of F


Build LL(1) parsing table for grammar S -> iSeS | iS | a

Eventually you will end up with having to choose  between $S'\to\epsilon$ and $S'\to eS$.

The grammar says that's a conflict.  But can't we deduce which is correct? What if we choose $S\to\epsilon$? Will we ever be able to match the e?


Where can I find an original reference for this integer square root algorithm

The wikipedia article on Methods of computing square roots: base 2 presents a strikingly similar snippet of C-code [a], but the link to the source is dead. Let's try to do better.

The snippets from both wikipedia and the question are very similar to Martin Guy's widely circulated C implementation [b]. which contains a comment: From a book on programming abaci by Mr C. Woo. Search engine use suggests this is [1] - one edition seems to be from 1930; it has been reprinted, e.g. [2].

The age of the method is bound to be on the order of two millenniums - the original reference might be difficult to obtain.

A purportedly[z] very similar Algorithm has been presented by TIJ Rolfe, who in turn refers to [3].

Woo, C.C. The Fundamental Operations in Bead Arithmetic. How to Use the Chinese Abacus, China Lace Co., Ltd., Hong Kong
Kwa Tak Ming, C. C. Woo, The Fundamental Operations in Bead Arithmetic. How to Use the Chinese Abacus, Literary Licensing, LLC, United States, 2012, 9781258466855
Hart, W.L. "College Algebra" 4th ed., Boston, 1955, p.424


The minimal number of rooms needed can be computed by considering the classes in order of finish times, and if a class can't be fit into any one of the rooms in use, create a new room for it. See e.g. Erickson, "Algorithms", section 4.2.

This is the problem of asking if an interval graph can be colored with $N$ colors (the rooms). Perhaps digging into scheduling nets some algorithm(s). It isn't a problem for which I've seen a simple algorithm. Determining if a general graph is $N$ colorable is NP-complete (i.e., no much better solution expected than just trying all possibilities) if $N \ge 3$, perhaps being an interval graph is enough of a restriction to make it tractable...


By using the fast Fourier transform, multiplications on $k$-bit numbers can be done in time $\tilde{O}(k)$ (where the tilde signifies that we're ignoring polylogarithmic factors). By repeated squaring, we can compute $n^{n^2}$ with $O(\log n)$ multiplications, and each multiplication involves no number larger than $n^{n^2}$, which has roughly $n^2 \log_2 n$ bits. So the total amount of time required is $\tilde{O}(n^2(\log n)^2)=\tilde{O}(n^2)$.


Solving recurrence with logarithm squared $T(n)=2T(n/2) + n \log^2n$

This is indeed the second case in the Master Theorem. For the standard recursion form $$T(n)=a\;T(n/b)+f(n),$$
you get $a=b=2$, and therefore  $f(n)=\Theta(n^{\log_b a} \log^2 n)=\Theta(n  \log^2 n)$.

Applying the Master theorem yields $T(n)=\Theta(n\log^3 n)$.


Multitape Turing machines against single tape Turing machines

Look at the original paper by Hennie and Stearns:

F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", Journal of the ACM (JACM), Volume 13 Issue 4, Oct. 1966, pp. 533-546

The construction is a little bit elaborate, but not extremely difficult to understand. The basic idea is to store and keep the current symbol of each tape in the same fixed column (home column) and simulate a shift of the $k$ tapes using a series of partially filled "buffers" of increasing length placed on the two tapes on the left and right side of the home column in order to avoid a full shift (that would require $O(t(n)^2)$ steps). If you need further help, modify the question and ask about the points in the paper that are not clear.


What problems are believed to have an efficient algorithm?

I'll cover problems that are easy to solve (i.e. in $P$) and problems whose solutions are easy to verify (i.e. in $NP$), and some problems that are probably not, and try to explain why people think one way or the other.

Under standard complexity-theoretic assumptions, $P=BPP$, meaning that most randomized algorithms can be "derandomized" (this family of conjectures is called the derandomization hypotheses). You read about a specific example, PRIMES, and it is expected that that is an instance of a more general phenomenon. So for example, polynomial identity testing probably has a polynomial-time algorithm.

For similar reasons, it is conjectured that $NP=MA=AM$. See the Complexity Zoo for definitions of these classes). One language in $AM$ is graph non-isomorphism: the language of all pairs of graphs that are not isomorphic. Clearly its complement it in $NP$ (because you can check whether a purpurted permutation is in fact an isomorphism), so surprisingly the fact that two graphs are not isomorphic is something that is expected to be easy to verify given some proof. Yet (afaik) we do not know which $BPP$-language we have to derandomize to obtain this result. If $NP=MA$ or $P=RP$, then it is easy to verify that an arithmetic circuit is not minimal.

These sets, $BPP$ and $AM$ are (afaik) the "largest" classes of problems that are expected to collapse to $P$ and $NP$ respectively, meaning they are expected to be easy to solve, respectively, to verify.

So we do not know how to verify non-isomorphism yet, much less decide it (as in, solve it in $P$). Is it hard? Is it easy? Interestingly, if Graph isomorphism is so hard that it's NP Complete, then a widely believed complexity-theoretic hypothesis (that "the polynomial hierarchy is infinite") fails, so graph isomorphism is probably not NP-Complete. We do not know of any hypothesis that fails under the assumption that graph isorphism is easy, i.e. in $P$ or in $BPP$. The same goes for factoring: probably not NP-Complete, not known to be easy.*

Problems in this Wikipedia list of NP-Intermediate problems are not expected to be in $P$.

Linear programming has a polynomial algorithm if you only count the number of arithmetic operations ($+,-,\times$ etc). However, those arithmetic operations may involve numbers that are more than polynomially long, so the algorithm is called weakly polynomial. It is expected that there is an algorithm that doesn't suffer from this, called a strongly polynomial algorithm. For example, Mihály and Vempala [1] recently presented a plausible-looking candidate for such an algorithm.

*Scott Aaronson once quiped that factoring might as well be in $P$. It would collapse the world economy, sure, but it wouldn't collapse the polynomial hierarchy, so wouldn't be that impressive.

[1] Bárász, Mihály, and Santosh Vempala. "A new approach to strongly polynomial linear programming." (2010).


Shortest hamiltonian path for different dimension points

Your problem is a variant of Euclidean TSP in which you are looking for a path instead of a cycle. You can (essentially) reduce your problem to the usual Euclidean TSP by adding a point at infinity.

Here is a quick summary of what is known about Euclidean TSP, paraphrasing a survey of Czumaj from the Encylopedia of Algorithms:

For every fixed $k$, there is a randomized PTAS due to Arora and Mitchell. The running time has been improved by Rao and Smith, and by Bartal and Gottlieb (in the real RAM model).
Trevisan showed that there is no PTAS when $k = \log n$ (unless P=NP).
Euclidean TSP with an unbounded number of dimensions is known to be NP-hard. The same isn't known for fixed $k$!


Computational complexity classes not based on input size?

No, not really: there's no framework for this that turns out to be very useful.  There is a reason that in theoretical work we often use asymptotic complexity.

In principle, you could talk about the concrete complexity of the problem of chess on a 8x8 board.  One way to measure that would be to use the worst-case running time of the fastest program to solve chess on a 8x8 board: not the asymptotic running time, but the actual wall-clock time, measured in seconds.  However, this has multiple problems.  One problem is that it is obviously super-specific to a particular computer: if I buy a different computer, the wall-clock time might be very different, even though I haven't changed the algorithm.  So now the running time is no longer a property of the algorithm; it also depends intimately on which computer I run it on.

Or, perhaps we could count the number of instructions executed.  But now that will depend on the particular computer architecture; when we compile to x86, the number of instructions might be different than when we compile to ARM.  So the complexity still depends  on the computer.

Finally, there is the problem that it is very hard to reason about this number through theoretical analysis.  Given some pseudocode, can you analyze how many instructions or how many seconds it will take to run that pseudocode?  That's very hard, since the pseudocode first has to be implemented in some language, then compiled to machine language, then run.  (And good luck reasoning about the effect of caches and the memory architecture on the time it takes to, e.g., perform a single read or write to memory; that's very hard to predict.)  At best, it gets super messy; at worst, it's just not predictable in a reasonable way.

If you read Knuth, you'll find that he tries to do this kind of analysis.  He defines an artificial computer architecture called MIX, which is fully specified.  He then implements his algorithms carefully in MIX machine language, and finally mathematically analyzes the number of MIX instructions the algorithm might take.  If you go through some of his demonstrations you'll see just how painful and messy it is.  He ends up doing this only for some pretty simple algorithms, and the calculations are still ugly; doing that for something as complex as a chess algorithm sounds horrendously painful.

Finally, there's the problem that we don't know what is the optimal program for playing 8x8 chess. That's a famous open problem.

So, yes, in principle, it is possible to reason about running time without relying on asymptotics.  In practice, it usually gets so messy that you drown in details and have a hard time extracting useful insights.


Try constructing CFGs for the two related languages
$$
\{a^ib^j : 2i > 3j + 1\}, \quad \{a^ib^j : 2i < 3j+1\}.
$$
This can be accomplished by constructing a grammar for
$$
\{a^ib^j : 2i = 3j + 1\}
$$
and some related languages.


Karp hardness of a diameter-decreasing planted clique

This problem is $NP$-complete. Reduce from Exact Cover by $3$-Sets (X3C).

Given an X3C instance, its ground set is $\mathcal{U}=\{e_1,e_2,\cdots,e_n\}$. Its collecion of $3$-subsets is $\mathcal{C}=\{s_1,s_2,\cdots,s_m\}$.

  For each element in the ground set and each subset in the collection,
  we create a new vertex (which will be referred to by the same name,
  henceforth).

  For each pair of element $e_i$ and subset $s_j$ such that $e_i\in s_j$, connect the two
  vertices.

  For $s_j$'s vertices:
  Connect all pair of $s_j$'s vertices to make these a clique.

  Then, create a new vertex $s$ and connect it to all $s_j$'s vertices.

  For $e_i$'s vertices: For each pair of elements $e_{i_1}, e_{i_2}$ that share no
  common subset, we create a new vertex $e_{i_1i_2}$ and connect it to both of
  $e_{i_1}$ and $e_{i_2}$.

  Then, create a new vertex $e$ and connect it to all $e_{i_ai_b}$'s vertices.

  Connect $s$ and $e$ by an edge. Create a new vertex $t$ and connect it
  to both of $s$ and $e$.

  Call the newly constructed graph $G$. Set $k=\frac n3+1$.

Clearly, we only need to decrease the distance from $t$ to each of $e_i$'s vertex.

If in the planted clique, we do not choose $t$, then for each $e_i$, we need to connect it to either $s$ or $e$. Because $s$ and $e$ are all the neighbors of $t$. That is going to exceed the bound of $\frac n3+1$ on the cardinality of the clique.

So, $t$ must be included in the planted clique. Denote by $x$, $y$ and $z$ (in this order) the number of vertices included in the planted clique among the $s_j$'s vertices, $e_i$'s vertices and $e_{i_ai_b}$'s vertices (resp.)

We can see that each one in $x$ vertices of $s_j$'s vertices will decrease the distance from $t$ to $3$ $e_i$'s vertices.

Similarly, each one in $y$ vertices of $e_i$'s vertices will decrease the distance from $t$ to $1$ $e_i$'s vertices.

And, each one in $z$ vertices of $e_{i_ai_b}$'s vertices will decrease the distance from $t$ to $2$ $e_i$'s vertices.

So, we must have $3x+y+2z\geq n$. But also, $x+y+z=\frac n3$.

We deduce that $x=\frac n3$ and $y=z=0$


Same thing does not hold for an NFA. Example

q0 -> 0 -> q1
q0 -> 0 -> q2

q0 is the start state, q1 is the final state.


Generating cyclical dependency graphs from k-way partitions of DAGs representing boolean networks

Consider the following graph on three vertices:

$$u \to v \to w$$

This is acyclic.  If you set $A_1 = \{u,w\}$ and $A_2 = \{v\}$, you end up with a dependency graph that is cyclic: it has an edge $A_1 \to A_2$ (due to the edge $u \to v$) and an edge $A_2 \to A_1$ (due to the edge $v \to w$).


Given A to C, and B to C with known complexities, what can be said about A to B?

We can have sets $A, B, C$ with linear-time computable maps $f : A \to C$ and $g : B \to C$ such that there exists a map $h : A \to B$ with $f = g \circ h$, but the needed time complexity/Turing degree for $h$ is as high as you want.

Proof: Pick a map $H : \Sigma^* \to \Sigma^*$ which is hard in whatever sense you have chosen. Now let $A = C = \Sigma^*$, and $B = \{\langle w, H(w)\rangle \mid w \in \Sigma^*\}$. Let $f = \mathrm{id}$ and $g = \pi_1$, i.e. $g(\langle w,u\rangle) = w$. Now $A,B,C$ and $f,g$ meet the criteria of the claim, and the only map $h$ that works is $h(w) = \langle w, H(w)\rangle$, which is essentially as hard as $H$.


The number of operations of Explicit and Implicit Euler for 1D hear equation


Reduction from Maximum Independent Set to Independent Set Decision Problem

It is certainly possible to do so, as every $\mathcal{NP}-$complete problem is self-reducible.

Let us first remember the definition of decisional maximum independent set: given an undirected graph $G=(V,E)$ and $k \in \mathbb{N}$, does there exist $S \subseteq V$ with $|S| = k$ such that $\forall x,  y \in S \ . \ (x, y) \notin E$ ?

By a standard binary search argument, we can find the size of the maximum independent set with a polynomial number of queries to that oracle.

Let $s$ be the size of the maximum independent set of $G$. We pick some $v \in V$ and we use our construction to determine the size of the maximum independent set of $G \setminus v$. That can be either $s$ or $s-1$. If it's $s$, then there exists a maximum independent set in $G$ that does not include $v$, therefore we can exclude $v$ from our search.

Eventually, we'll reach a point where we can't exclude any other node. That means that the remaining nodes form a maximum independent set.


Is it possible to support .(any symbol) or \d, \w, \W in DFA

The symbols you mention represent sets of characters. For example, \d represents the set $\{0,1,2,3,4,5,6,7,8,9\}$. Whenever you want to place \d, replace it with 10 parallel edges labeled with all digits instead. The same works for your other examples, as long as each symbol represents one character. (Otherwise you would get a "generalized NFA".)


Quantum Computing - Relationship between Hamiltonian and Unitary model

To show that Hamiltonian evolution can simulate the circuit model, one can use the paper Universal computation by multi-particle quantum walk, which shows that a very specific kind of Hamiltonian evolution (multi-particle quantum walks) is BQP complete, and thus can simulate the circuit model.

Here is a survey paper on simulating quantum evolution on a quantum computer. One can use the techniques in this paper to simulate the Hamiltonian evolution model of quantum computers. To do this, one needs to use "Trotterization", which substantially decreases the efficiency of the simulation (although it only introduces a polynomial blowup in computation time).


Proof that the set of all universal CFGs is co-RE complete

In the proof we construct grammar $g(n)$ such that it has same alphabet as the Turing machine + symbols for states + separator "#", which is defined to be:

$\Sigma_n = \{0, 1, \triangleright, B, \#, q_0, q_1 . . , q_n \}$

So essentially $\Sigma_n = \Sigma_{g(n)}$. $\Sigma_n$ is a superset of $\{0, 1, \triangleright, B\}$.


In Boolean Algebra we have:

\begin{align*}
a \cdot b &= \min{(a,b)}\\
a + b &= \max{(a,b)}
\end{align*}

So, by the first definition it's obvious that:

$$ x \cdot 1 = \min{(x,1)} = x$$

Since $x \leq 1$.

By the same reasoning:

$$1 + y = \max{(1,y)} = 1$$
since $y \leq 1$.

So you have:

\begin{align*}
x + x \cdot y &= (x \cdot 1) + (x \cdot y)\\
&= x \cdot \color{red}{(1 + y)}\\
&= x \cdot \color{red}{1}\\
&= x \cdot 1 = x
\end{align*}


How is a Transition System in Operational Semantics defined?

Operational semantics utilizes the tools of logic, so as a prerequisite we must understand judgements and inference rules.

A judgement is like a proposition, but more general. It asserts a relation between two entities of our language. For example, in programming, we often employ the judgement $e: \tau$, asserting that expression $e$ has type $\tau$.

Inference rules are used to define judgements. They have the general form

$$ \frac{J_1 \dots J_n}{J} $$

which reads: if we know judgements $J_1$ through $J_n$, we can infer judgement $J$. For example, we may have the following self-explanatory inference rule for the previously defined typing judgement:

$$ \frac{n: \text{int} \quad m: \text{int}}{n+m: \text{int}}. $$

A structural operational semantics is defined using a transition system between states. In a programing language, the states are all closed expression in the language, and the final states are values. Formally, we make use of two judgements:

$e_1 \to e_2$, stating that expression $e_1$ transitions to state $e_2$ in one step
$e \space \text{final}$, stating that expression $e$ is a final state of the system.

Here are some example inference rules in a language with arithmetic and function abstraction:

$$ \frac{}{n \text{ final}} $$
$$ \frac{}{n+0 \to n} $$
$$ \frac{n + m \to k}{s(n) + m \to s(k)} $$
$$ \frac{}{\lambda x. e \ \text{final}} $$
$$ \frac{(\lambda x. e_1)e_2}{[e_2/x]e_1} $$

Most languages do not have a formal definition, including Java (as far as I know). There are also other methods for defining the semantics of a language, but for describing an optimization, I believe structural dynamics is a wise choice, as it has a natural notion of time complexity (the number of transitions).


Big-endian systems and the smallest memory address

If the map of memory bytes were arranged from left to right in incremental address order, the smallest address is on the left.  The largest address is on the right.
Let's say you are storing the 32-bit value, 19088743, which is 0x01234567 in hex, at address 0x1000.  Hence, the 4-byte value will span over the 4 bytes at memory address 0x1000, 0x1001, 0x1002, and 0x1003
In big endian, the 01 is stored at 0x1000 (the smallest address) and the 67 is stored at 0x1003 (the largest address).  Exactly how you would think of it if you had never heard of little endian.
In little endian, the 01 is stored at 0x1003 (the largest address) and the 67 is stored at 0x01000 (the smallest address).
Big Endian and Network Byte Order generally mean the same thing.
Big Endian
|===================================|
| 0x1000 | 0x1001 | 0x1002 | 0x1003 |
|-----------------------------------|
|  0x01  |  0x23  |  0x45  |  0x67  |
|===================================|

Little Endian
|===================================|
| 0x1000 | 0x1001 | 0x1002 | 0x1003 |
|-----------------------------------|
|  0x67  |  0x45  |  0x23  |  0x01  |
|===================================|


Turn one string into another with single letter substitions

The graph I consider has the valid words for vertices and edges correspond to one-letter substitutions. In this graph the Hamming distance never overestimates the distance but can underestimate it (e.g. between $aa$ and $cc$ in the set of valid words ${aa,ab,bb,bc,cc}$)

You don't need an actual graph, you just need a representation of it. The hard part is computing the neighbors : you may want to store the valid words into a prefix tree. But for the search algorithm you already have a non-overestimating distance so you can use that as a admissible heuristic for the $A^*$ algorithm. You can use an hash table to store the marked vertices.

Building the prefix tree

To list all the neighbors of $w$ first use this function that computes all words $v$ such that $w$ and $v$ differs only on the $i$th letter. It runs in $O(|Σ||w|)$ if you implement it correctly : $w$ must be in the form of a list for the tail() dans head() operation to be in constant time. The operation prefix . c . tail(w) just has to be in linear time.

neighbors(i, prefix, w, trie) =
  if(i == 0) :
    for c in 'a' .. 'z' :
      if(tail(w) is a word of trie) :
        add(prefix . c . tail(w))
  else :
    neighbors(i-1, prefix . w[0], tail(w), trie[head(w)])

Then to list all the neighbors, just run:

for i in 0 .. length(w) - 1 :
  neighbors(i, emptyprefix, w, trie_of_valid_words)

Which runs in $O(|Σ||w|^2)$.

Compared to other methods, where $N_V$ the number of valid words.

if you use a hash table and enumerate all the potential neighbors: $O(|Σ||w|^2)$ in the practical case and $O(|Σ||w|^2N_V)$ in the worst case. It might be faster in practice though.
if you use a binary search tree: $O(|Σ||w|\log N_V)$ in the worst and average case.

Precomputation

At first the goal was to get all the neighbors in only one look up in time $O(|w|)$ by previously having computed some kind of prefix tree with wildcards. (I don't really know the name of this data structure) Then I realized that it can simply be done with just a reverse search.

I insist that this is only interesting if you only care about the look up time. I would probably be a good idea if you have to find the shortest path between several pairs of words. If it's only one time the method above will be enough.

This is really very simple : for each word $w$, enumerate all the possible neighbors $v$ of $w$ and check if they are valid. This is in $O(N_V\log N_V |w||Σ|)$ or $O(N_V^2)$ if $N_V$ is small enough for this to be interesting. Add them to your automaton / prefix tree / hash table with the key $v$ and the value $w$.

Then getting all the neighbors of $v$ is looking up in this structure and getting back all the $w$'s. So you can make your search algorithm with this.

Implementation details:

generic binary tree : look up in $O(\log(N_V|Σ||w|))$ which is $O(|w|+\log|Σ|)$ but you don't care about the $\log|Σ|$.
trie : look up in $O(|w|)$
hash : look up in $O(|w|)$ (and worst worst case)

Conclusion

If the set of valid words does not change I would suggest precomputing and storing in a hash table and using the A* with the hamming distance admissible heuristic.


What does a solution to the Rectangle-Fit problem look like?

You can simply list the coordinates of the upper-left corner of each rectangle (and its orientation, if you're allowed to rotate rectangles).  That completely determines its position, and thus listing that for all rectangles completely identifies the configuration of all rectangles.


Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?

The symbol $\leq_m$ means many-one reducible, contrast to reductions such as turing reducible (denoted by $\leq_T$) and one-one reducible (denoted $\leq_1$).

A many-one reduction from $L$ to $L′$ (given an alphabet $\Sigma$) is a (computable) function $f:\Sigma^* \to \Sigma^*$ such that for every $w \in \Sigma^*$, we have that $w \in L$ if and only if $f(w) \in L′$.  The "many-one" means that we allow $f(w) = f(w′)$ (it does not have to be injective).  In your setting, it basically means that you can transform an input to $A_{TM}$ to $HALTING$ such that $A_{TM}$ accepts an input $w$ if and only if $HALTING$ accepts the transformed input $f(w)$.


I didn't realize what is your problem with Kruskal algorithm. To me, a usual Kruskal has time complexity $O(E \ log E)$ that $E$ is the number of edges in a graph, and I don't have any difficulty to ignore those edges which make a cycle.

To answer you question, all adjacency lists, maintaining adjacent vertices, can be sorted in an ascending order. Then, you can find the position of each adjacent node with $O(log N)$, where $N$ is the number of vertices.

You should also define two one-dimensional arrays, $nex$ and $pre$ for each adjacency list, where $nex$ maintains the position of next vertex in an adjacency list, and $pre$ holds the previous position.

When edge $e = (a, b)$ is about to be removed, the position of $b$ in the adjacency list of $a$ can be found with $O (log  \ N)$.

Then, do two following steps to remove $a \to b$:

$nex [ \ pre [b] \ ] = nex [b]$
$pre [ \ nex [b] \ ] = pre [b]$

Do it also in the adjacency list of $b$ to remove $b \to a$.

If you want to traverse in an adjacency list, the next index can be reached by the means of $nex$ array.

To traverse an adjacency list from the beginning a random value, as a dump, can be utilized since the first node might be removed.


Is $L_p$ decidable when p is a trivial property?

If $p$ is a trivial property of r.e. languages, it either applies to all r.e. languages or applies to no r.e. language. That means that either

$L_p$ is the set of all TM descriptions or
$L_p=\emptyset$.

In the first case, a decider for $L_p$ ignore the input $\langle M\rangle$ and immediately accept and in the second case, a decider would similarly reject. In either case, $L_p$ is clearly decidable. While we don't necessarily know which decider is the right one to use, that doesn't matter, since the existence of a decider is all that we need.


Reduction from SUBSET-SUM to 0-1-INT-PROG

Let $\langle S, k \rangle$ be an instance of subset sum, where $S=\{a_1, a_2, \dots, a_n\}$. Construct an $0$-$1$-integer program with $n$ binary variables $x_1, \dots, x_n$ and the following constraints:
$$
\begin{align}
a_1x_1+a_2 x_2+ \dots+a_n x_n &\le k \\
-a_1x_1-a_2 x_2 - \dots-a_n x_n &\le -k
\end{align}
$$
Or, in matrix form:
$A =
\begin{bmatrix}
a_1 & a_2 & \dots & a_n \\
-a_1 & -a_2 & \dots & -a_n
\end{bmatrix}$ and $b=\begin{bmatrix} k \\ -k\end{bmatrix}$.
If you have a solution $S' \subseteq S$ to the subset sum instance, then you can pick $x$ as the characteristic vector of $S'$ to satisfy the constraints (as you correctly point out in your question). I.e., set $x_i = 1$ if and only if $a_i \in S'$ so that $Ax = \begin{bmatrix} k \\ -k\end{bmatrix} = b$.
On the other hand, if $Ax \le b$ then the first constraint is $a_1 + a_2 + \dots + a_n \le k$ and second constraint implies $a_1 + a_2 + \dots + a_n \ge k$. Then, we necessarily have $a_1 + a_2 + \dots + a_n = k$, showing that $S' = \{ a_i \mid x_i = 1\}$ is a solution to the subset sum instance.


Union of infinitely many regular languages

Is $A_n$ a language or an alphabet, since it's a subset of $\Sigma^*$?

A member of the alphabet, $\Sigma$ is called a symbol or a letter.
A member of $\Sigma^*$ is called a string or a word, which is a finite sequence of symbols or letters.
A subset of $\Sigma^*$ is called a language.

  If $A_n\subseteq \Sigma^*$ is regular for each $n\in\Bbb N$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular.

As you suspected, this is not true. For example, let $A_n=\{a^nb^n\}$. Then $\bigcup\limits_{n=0}^{\infty} A_n$ is the well-known non-regular language of words with equal number of $a$'s and $b$'s. Infinity should indeed be treated carefully.

Exercise 1. Give an example of a non-regular language $L$ over unary alphabet such that $L=\bigcup\limits_{n=0}^{\infty} A_n$ where $A_n$ is a regular language for all $n$.

Exercise 2. Let $L$ be any language. Then $L=\bigcup\limits_{n=0}^{\infty} A_n$ for some regular language $A_n$.


complexity of a variant of the subset sum problem

It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset $N'$ is at least $B$ (which implies that it must actually be exactly $B$) if and only if the corresponding subset sum instance has answer "yes".


Each recursive function should have some initial values to stop the computation. For the last two recursive functions, the program will not be stopped and trapped in an infinite loop or it has no meaning (for case 2, what is the value of $f(1)$?). Also, for the last case, if we have a random initial value, we can compute the complexity in average:
$$\frac{1}{n}(n + (n-1) +\cdots+1)=O(n)$$
As Probability of each random value between $1$ to $n$ is $\frac{1}{n}$, the average complexity is $O(n)$, as shown in the above.


Tarjan's Algorithm failure case, what am I missing?

Answer:  the low-link value is not the identifier.  I eventually found this while researching during the writing of this question.  Question posted because I wrote it and hey, maybe this will help someone else.

Everything up to the current node is popped off the stack when identifying an SCC.  My misunderstanding was trying to pop only what has the same low-link value.


No, it is not true in general.

A general problem being NP-Hard does not imply a specialization will be NP-Hard. It is true the other way round.

For instance, MAX-CUT is NP-Hard for general graphs, but for the class of planar graphs, it is in P.

In your case, the $d$-regular graphs are a special case of graphs of max degree $d$, so NP-Hardness for max degree $d$ is not an automatic proof of NP-Hardness of $d$ regular graphs.

In fact, for a concrete example, look at this cstheory question: Is there a problem that is easy for cubic graph but hard for graphs with maximum degree 3? with the following answer(by David Eppstein) in the affirmative (copied for convenience):

  Here's a reasonably natural one: on an input $(G,k)$, determine
  whether $G$ has a connected regular subgraph with at least $k$ edges.
  For 3-regular graphs this is trivial, but if max degree is 3 and the
  input is connected, not a tree, and not regular, then the largest such
  subgraph is the longest cycle, so the problem is NP-complete.


What should I read before tackling Michael Huth's Logic in Computer Science: Modelling and Reasoning about Systems?

From the Preface of the 2nd Edition:

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

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

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


The natural numbers don't exist natively in the world of lambda calculus, and so if we want to use them, we have to define them somehow. You are describing the Church numerals, one possible definition which supports arithmetic. Church defines $n$ to be the function $(s,z) \mapsto s^{(n)}(z)$ that maps a pair $(s,z)$ into an $n$-fold application of $s$ to $z$. In particular, when $n = 0$ we get $(s,z) \mapsto z$.

Why this definition and not any other one? No reason. It is just a common definition, but you can use any other definition you like, or even come up with a new one. This particular definition supports arithmetic – you can define addition, multiplication and so on. See Wikipedia for the details.


a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation.
But I don't find any reason for the right to left direction. how can the inexistence of such variable guarantee satisfaction of CNF?

Think of a variable assignment for some unsatisfiable 2-SAT instance.  This means one or more clauses must remain unsatisfied whatever the assignment.  You change the setting of one or more variables to satisfy those clauses, but this unavoidably leaves some new clause or clauses unsatisfied because the instance is unsatisfiable.  The failure of your change to satisfy the instance implies that some other variable's value must change.  You repeat the procedure again and again, changing other variables as implication demands, but never succeed in satisfying all the clauses.  Eventually, because the number of variables is finite, a failure implies that you change the value of a variable you've already visited... and that is your circular implication from $x$ to $\bar{x}$ back to $x$.  Without a circular implication you will eventually reach the end of the implication chain and have a satisfying assignment.  The only way not to reach the end of the chain is for the chain to be circular between a variable and its negation.


Is $L=\{\langle M \rangle|M$ makes more than 10 steps on some input$\}$ decidable?

Your first statement is true. The second is not true. You can construct infinetly many TMs accepting the same language by introducing redundant states and transitions (as you already mentioned). "Minimizing" a TM has nothing to do with the second statement since two machines accepting the same language do not have to be identical and minimizing a TM gives you another machine while you compare M1 and M2.


Complement of Non deterministic Finite Automata

I'm going to assume that you know that there is an equivalence between DFAs and NFAs in the following sense: For every NFA $M$ there exists a DFA $M'$ such that $L(M') = L(M)$. I'm also going to assume that you know how to, given $M$, calculate $M'$. These are standard methods and they (and their proofs) can be found in any good textbook on automata such as: Hopcroft and Ullman

Given these facts the result is almost immediate: Given an NFA $N$ all you have to do is calculate the corresponding DFA $N'$ and use the complement algorithm which you've mentioned you already know. The resulting DFA is an NFA (since DFAs are just special cases of NFAs) which accepts the complement of the language accepted by the NFA you started with.

So to answer your question, yes it is possible to construct such an NFA, however, if you want to do it quickly you may have some problems


An example of a non-regular grammar for a regular language?

Regular Language L = {aab}

Non-regular grammar

S -> aAb

A -> a


Function whose implementation is difficult (computationaly) to work out

If the function $f$ is computable, then $\mathrm{verify}f$ is computable too: to work out if $y=f(x)$ for some given $x$ and $y$, just compute $f(x)$ and see if it's equal to $y$. That tells you nothing about the implementation of $f$.

The relationship between the difficulty of computing $f$ and $\mathrm{verify}f$ is the essence of the P-vs-NP problem.


How the website owner keep track of your times of access?

I am not sure how this website keeps track but I can tell you the general flow how usual websites keep track of user's data.

If the you are registered user on the site it doesn't matter which ip you use it can be tracked easily.
To be more specific when you read the complete article a tracker can be anywhere from page-end scroll to read-more button.

Edit1: Looks Like the website you are talking tracks user based on (article click+ip+ cookie) so it is easy just to choose new ip + incognito browsing to get 30 article limit each time.


There exist many interesting languages that do not have the full expressiveness of Turing Machines: these languages are traditionally called subrecursive.

The typical example is the language of primitive recursive algorithms, provably equivalent to the language of algorithms that can be written with "for-like" statements (fixed step, fixed bounds). Primitive recursive algorithms are total, hence they are not complete (that means that there are total functions not expressible in the formalism). A famous example of a total function not expressible in the primitive recursive setting is Ackermann function.

Other examples of subrecursive languages come from logic. It is well know that no logical system (rich enough to allow to reason about natural numbers) is complete. Hence you cannot expect to prove the totality of all algorithms in them. That is to say that any logical system characterizes a set of computable functions that are provably total in the given system. For instance, the set of computable functions provably total in Peano arithmetics is the so called Goedel's System T (a higher order generalization of primitive recursion); similarly, the set of computable functions provably total in second order arithmetics is Girard's System F, also know as polymorphic lambda calculus.

The interest of considering subrecursive languages consists in the fact of capturing statically , i.e. by the way the program is written, relevant dynamic aspects of the algorithm, such as totality, or complexity properties.

The problem of providing syntactical characterizations of subrecursive complexity classes such as P, Pspace, etc. has received much attention in the literature. The recent field of Implicit Complexity aims at studying the computational complexity of programs with no reference to a particular machine model and explicit bounds on time or memory, but instead relying on logical or computational principles that entail complexity properties, typically via a controlled use of the available resources. For an introduction to this topic, you may consult the special issue on Implicit Computational Complexity, ACM Trans. Comput. Log., Vol 10, n.4 2009.

Other interesting characterizations have been obtained restricting the interpretation of programming languages to finite domains. The seminal result in this area is an old work of Gurevich ("Algebras of feasible functions", FOCS 1983) where he proved that interpreting primitive recursive functions (resp. recursive functions) over finite structures one precisely get the log-space (resp. polynomial time) computable functions.

Please have a look at my article "Computational Complexity via Finite Types", ACM Trans. Comput. Log., Vol 16, n.15 2015, for more references in this area.


Start / End-Point in TSP - How to consider in an algorithm

The result of any algorithm for TSP is a tour, that is a cycle in the graph. When translating that answer into practice, you can pick any node as starting point without changing the cost of the tour at all.


Big-O complexity of finding exception handler for zero-cost exceptions

The crucial data structure here is an interval tree, that can be pre-computed at compile time, which has a complexity of $O(\log n + k)$ to find all $k$ ranges that contain a certain point, assuming there are a total of $n$ ranges. Here your ranges are exception blocks in the compiled code and your point is the instruction address.

I will assume the C++ model of one try block followed by one or more catch blocks that may or may not match a thrown exception and I will assume that a compiled program has $n$ try blocks in total.

Then when an exception is thrown it takes $\log n$ time to find the $k$ relevant try blocks in the current call frame (which we order by specificity, which is done by minimizing range size). And for each relevant try block there may be one or more relevant catch block, which may or may not match. If none match we go to our caller and search again.

But at some point we find a matching exception (or halt). The total complexity then is $O(c\log n + k)$, where $c$ is the number of calling frames we had to go up, and $k$ is the total number of relevant catch blocks that we considered for matching.

This is assuming that you do exception type matching at runtime, instead of maintaining separate tables per exception type. Since $k$ is generally very small, this is a sensible approach. You can get better asymptotic runtimes in terms of $k$, but I described a practical approach.


Time complexity of the travelling salesman problem (Recursive formulation)

The full recursion tree for your problem has as root $(1,\{2,\ldots,n\})$. The children of a node $(i,S)$ are $(j,S \setminus \{j\})$, where $j$ ranges over all elements of $j$. Nodes with $S = \emptyset$ have no children.
Let us annotate each node in the tree by its "history". Instead of annotating each node by an index and a set, we annotate it with a sequence and a set. The root is $(1;\{2,\ldots,n\})$. The children of a node $(a;S)$ are $(a,j;S \setminus \{j\})$ for all $j \in S$. For example, if $n = 3$ then the nodes are:

$(1;\{2,3\})$.
$(1,2;\{3\})$.
$(1,3;\{2\})$.
$(1,2,3;\emptyset)$.
$(1,3,2;\emptyset)$.

A node $(a_1,\ldots,a_m;S)$ in the new tree corresponds to the node $(a_m,S)$ in the original tree. Conversely, each node $(a,S)$ corresponds to nodes $(1,a_2,\ldots,a_{m-1},a;S)$, where $m = n - |S|$ and $\{1,a_2,\ldots,a_{m-1},a\} = \overline{S}$. There are $(n-2-|S|)!$ ways to choose $a_2,\ldots,a_{m-1}$, and so the node $(a,S)$ appears $(n-2-|S|)!$ times in the original tree.
This shows that the full recursion tree for your problem does contain duplicates.


Why are bytes treated like the base unit?

For historical reasons.

In the early days and even so today a byte represented the most commonly used data.

A byte represents one character in ASCII.

A byte was and still is the size of the instruction for the most commonly used opcodes at the assembly level. Having the most common instructions in one byte saved the most amount of memory.

It is a power of two so 8 is better than 7,6, and 5.

You can get two BCD digits in one byte.


Behavior of different multiplied and added time complexities

Let $f(n)\in \theta(h_1(n))$ and $g(n)\in \theta(h_2(n))$.

We start with multiplication:
It is easy to prove (from the basic definitions) that $f(n)\cdot g(n)\in \theta ((h_1\cdot h_2)(n))$, and similarly for $\Omega,o,\omega$.

Accordingly, multiplication of functions is preserved in all the asymptotic notations ($O,\Omega,\theta,o,\omega$)

As for addition, the idea is to make the following observation:
$$f(n)+g(n)=\max\{f(n),g(n)\}+\min\{f(n),g(n)\}$$
But $\min\{f(n),g(n)\}\le \max\{f(n),g(n)\}$, so $f(n)+g(n)\le 2\max\{f(n),g(n)\}$. Thus, we get
$$\max\{f(n),g(n)\}\le f(n)+g(n)\le 2\max\{f(n),g(n)\}$$

This implies that the asymptotic behavior of $f(n)+g(n)$ differs from that of $\max\{f(n),g(n)\}$ by a multiplicative constant, which means that they have the same order of magnitude, and in particular the relation is preserved under all the asymptotic notations.

To add some detail to the above, we use the observation that if e.g. $f(n)\in \Omega(h_1(n))$ and $g(n)\in \Omega(h_2(n))$, then $\max\{f(n),g(n)\}\in \Omega(\max\{h_1(n),h_2(n)\})$. This is relatively easy to prove.


Complete $\mu$-recursive function that is not primitive recursive

There are two standard approaches: diagonalization and rate of growth.

The definition of primitive recursive functions (whichever one you use) allows enumerating them $f_1,f_2,\ldots$. Since each primitive recursive function is total, the function $f(n) = f_n(n)+1$ is recursive. It is clearly not primitive recursive.

The other approach is exemplified by the Ackermann function, which is clearly recursive but grows too fast to be primitive recursive.


Prove that Weighted Independent Set is NP Complete using Independent Set?

You reduce to this problem quite easily from the Independent Set problem.

Given a graph $G=(V,E)$ and a natural number $k$ define a simple weight function $w:V\to\mathbb{R}$ by

$$\forall v\in V:w(v)=1$$

The output of the reduction is $\langle G'=(V,E,w),k\rangle$.

If $G$ has an Independent set $S$ of size at least $k$ then $S$ is an independent set in $G'$ and

$$\sum\limits_{v\in S}w(v)=\sum\limits_{v\in S}1=|S|\geq k$$

So, $G'$ has an independent set of weight at least $k$, as needed.

If $G'$ has an Independent set $S'$ such that

$$\sum\limits_{v\in S'}w(v)\geq k$$

Then, observe that $S'$ is an independent set in $G$ also and

$$|S'|=\sum\limits_{v\in S'}1=\sum\limits_{v\in S'}w(v)\geq k$$

So, $G$ has an Independent set of size at least $k$, as needed.


Closure of Star-Free Languages under Substitution

I do not understand your proof sketch. Where do you want to subtitute $\sigma(1)$ under a complement. The only thing substituable in the star-free expression for $1^*$ is $0$. But 0, or $\sigma(0)$ is an independent element in the substitution, it is in no way related to the complement of $\sigma(1)$. So this can in no way make a proof.

Actually, if there was such a closure property, it should be easy to find in
the literature on star-free RE. But all closure results under substitution put
constraints on the type of substitution, such as being length
preserving, or being injective.
See in particular papers by Jean-Eric Pin and others.

Also,Pin defines star-free substitutions on $\Sigma$ as requiring an additional property, namely that $(\sigma(\Sigma))^*$ is star-free. (though I did not check
the precise role of this property)

It seems that you have just proved that star-free languages are not closed under star-free substitution as you define it.

This does not seem too surprising, since non injective substitution does not in general commute with complement or distribute with intersection.

Among other papers:
Jean-Eric Pin, H. Straubling, and D. Thérien. Some results on the generalized star-height problem. May 12 2002.


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

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

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


I'm not sure how to approach your particular problem, but here is an attempt.

Consider the recipe you are using as a collection of steps, some of which depend on others; for a salad you might have "make dressing", "shred lettuce", "slice cucumber" etc. The dependencies are given through resources, which here are ingredients, possibly in some processed state, like oil, vinegar, cucumber, sliced cucumber, etc.

To model this process as a Petri net, you use

places to represent the various resources, i.e. you have a "vinegar" place, a "shredded lettuce" place, etc,
tokens on those places to represent the amount of each resource you have; initially this would be something like one token on each unprocessed ingredient,
transitions to model actual steps in the recipe; for example you could have a "make vinaigrette" transition consuming a token from the "oil" and "vinegar" places and producing a token in the "dressing" place.

The amount of detail here depends on what you want to do with the model; you might for example want to keep track of equipment in addition to ingredients (with the "make vinaigrette" transition additionally consuming a clean whisk and producing a used whisk), etc.

Is this the kind of example you had in mind?


Karp reduction from NP-hard problem to unknown problem

Short answer, yes. I won't provide an actual proof (you probably saw one in class), but rather, a sort of mnemonic that helps if this comes up on an exam.

A Karp reduction is also known as a polynomial-time reduction. If you can reduce from $A$ to $B$, that means if I give you a subroutine that solves $B$, you can build an algorithm to solve $A$, which does at most polynomial-time work and then calls the $B$ subroutine to get the answer.

The question is now, if you can reduce from $A$ to $B$, and $A$ is $NP$-hard, then is $B$ $NP$-hard?

Assume it isn't. In other words, assume $B$ can be solved in polynomial time. Then that means $A$ can be solved in polynomial time: run the polynomial-time reduction, call $B$ which takes polynomial time, and you have a solution to $A$ in polynomial time. We've proven $P = NP$ and earned a million dollars!

Since we haven't proven anything of the sort, our assumption must be false. In other words, $B$ must be NP-hard.

(Now, this would be a formal proof if $P \neq NP$ were a known result. But it isn't. So while this is good enough to remember on an exam, and the fact that $B$ must be $NP$-hard is in fact true, I haven't actually given a full proof of that fact.)


generating mazes using Eller's algorithm - why do I get loops?

here I get two blocks of the same set, but they don't go one after the other. So I join the second one go it's own unique set

Don't do that; this is not a step mentioned in your first reference! Two cells are in the same set when there is already a path between them (by going up though the already generated portion). By arbitrarily placing the second block into a new set, you are ignoring the fact that it is connected to other cells.

When you leave the 3 blocks alone, you will get

(03 17)03
 03(03 03)

You are required to place a wall between two blocks of the same set, because they already have a path between them. Thus you produce

 03 03|03

And don't had a loop.


Time complexity of finding an integer between $x$ and $2x$

You can speed up this algorithm somewhat by generating a random integer which is coprime to all small primes. This can be done efficiently using a sieve: pick an appropriately sized random interval inside $[x,2x]$, and cross off all integers in the interval which are multiples of small primes (you can do this efficiently by finding the first multiple of a given prime, and then iterating over the remaining multiplies). Now use your favorite algorithm to find a prime within the integers not ruled out. The size of the interval should be chosen so that it guarantees that there is a prime (so about $\log x$ or somewhat larger).


How to use the Pumping Lemma to prove that a restricted subset of 0*1*2*3*, where there are as many 3's as 0's and 1's, is not a CFL?

Use $|uyv|\le p$ to avoid the cases you mention, e.g., that $u,v$ pump both the $1$'s and the $3$'s. You can choose $p,q$ in $w$ such a way that this way of pumping is not possible. There is no problem in choosing $p=q$!


Show that function is not turing-computable?

This proof is correct as written, well done :) Remember this pattern, because an identical proof can be used in a wide variety of similar problems such as rational/irrational numbers and polynomials/non-polynomials


Sippu and Soisalon-Soininen (1982) carefully distinguish between two definitions of LL(k) grammars, one of which -- the one I think you are using -- they call strong LL(k):

A grammar $G$ is $\text{LL}(k)$ if $\text{FIRST}_k(\omega_1\delta)$  and $\text{FIRST}_k(\omega_2\delta)$ are disjoint whenever $xA\delta$ is a left sentential form of $G$ and $A \to \omega_1$ and $A \to \omega_2$ are distinct productions of $G$.
Grammar $G$ is $\text{strong LL}(k)$ if $\text{FIRST}_k(\omega_1\text{FOLLOW}_k(A))$ and $\text{FIRST}_k(\omega_2\text{FOLLOW}_k(A))$ are disjoint whenever $A \to \omega_1$ and $A \to \omega_2$ are distinct productions of $G$.

The difference has to do with the state machine. A grammar is $\text{strong LL}(k)$ if you can use the same procedure to decide which production for a non-terminal to use regardless of the contents of the parser stack. An $\text{LL}(k)$ grammar, on the other hand, can use the contents of the stack ($x$ in the above definition) as well as the lookahead. (For these purposes the contents of the stack can be condensed into a finite state automaton.)
While the two definitions are not equivalent -- the strong condition is much more restrictive -- it can be demonstrated that every $\text{LL}(k)$ grammar can be changed to a $\text{strong LL}(k)$ grammar simply by labelling each usage of a non-terminal. So in the case of your grammar, which is $\text{LL}(k)$ but not $\text{strong LL}(k)$, we can create the equivalent grammar:
$\begin{align}
S &\to A_1abA_2ba \\
A_1 &\to a | \epsilon \\
A_2 &\to a | \epsilon \\
\end{align}$
which is $\text{strong LL}(k)$.
For more details, see the paper linked above.


Is there a complexity viewpoint of Galois' theorem?

I assume you are considering polynomials with integer coefficients.

You've taken the wrong starting point for your investigations; your goal is to find good estimates for the real roots. Looking for an algebraic formula so that you can evaluate it to enough precision is something you can do, but it's not really the right thing to do here. (unless, of course, "the k-th largest real root of a polynomial" is one of your algebraic operations)

A much better starting point is to use Sturm's theorem to isolate the roots of the polynomial. You can then produce better estimates by binary search, but if that's too slow, you can use Newton's method to quickly produce estimates of high precision.

But that's just about finding certificates. There's still the question of what certificates can exist.

First off, I will point out that you can directly compute whether or not two of the roots are exactly $k$ units apart, e.g. by computing $\gcd(p(x), p(x-k))$. You will also have to decide what you want to do about repeated roots and deal with appropriately. I assume you will deal with these case specially.

If we know the two roots are not exactly $k$ units apart, that means that you can produce an estimate of sufficient precision to prove that they are either greater or less than $k$ units apart. e.g. there are two kinds of certificates:

The first kind (proof in the negative) is

$a$ is not a root of $p$
$p$ has no roots in $(a-k, a)$
$p$ has three roots in $(a, \infty)$

The second kind (proof in the positive) is

$a$ is not a root of $p$
$p$ has at least two roots in $(a-k,a)$
$p$ has two roots in $(a, \infty)$

A certificate can be verified by using Sturm's theorem. Now, your question about the size of a certificate boils down to finding how many bits of precision you need to represent $a$.

In other words, what are the bounds on the possible values of $a-b-k$, where $a,b$ are roots of $f$?

I'm not sure of a great approach, but one that should give you something is to observe that all of these values are roots of the polynomial:

$$ g(x) = \mathop{\text{Res}_y}(f(y), f(x + y + k)) $$

Why? Recall that the resultant of two monic polynomials is the product of all differences of their roots, so

$$ g(x) = c^{d^2} \prod_{a,b}(b - (a - x - k))
= \prod_{a,b} (x - (a-b-k))$$

where $c$ is the leading coefficient and $d$ is the degree of $f$. (maybe I've written the formula for $-g(x)$ instead of $g(x)$; I'm never sure on the sign)

So the question is to find estimates for how large the coefficients $g$ can be, and then once you know that, find estimates to how close a root of $g$ can be to zero.

(or, alternatively, find the largest magnitude that a root of the reverse polynomial of $g$ can have; the roots of the reverse polynomial are the inverses of the roots of $g$)


Scheduling algorithm to minimize the number of late jobs

For an optimal selection, one possible sequencing is always the one respecting the order of arrival time $S_0$. Another may be possible, but you can check that you always can do the switches to obtain $S_0$. This is due to the fact that all jobs have the same $d$.

Thus, your problem is equivalent to select the subset of jobs which do not overlap if they are executed as soon as possible in arrival time order.

Then you can do an approximative greedy algorithm considering jobs in increasing duration order. Counting the duration sorting, this has a $O(N \log(N))$ time complexity. It would generally give a very good result but might fail for example on $(a[i], t[i]) = [(0, 60), (30, 50), (60, 60)]$ with $d = 60$.

Or you can do a dynamic programming on $T$ array of $t(n)$, the soonest time at which $n$ jobs are achieved.

Initially, $T_0 = [0, +\infty, +\infty ..., +\infty]$, it has size $N+1$, the number of jobs (+ 0 index). The jobs are considered in increasing arrival time order. $T_k$ is the state of $T$ after considering $k^{th}$ job.

To keep track of the selection, you need an array $previous$ of size $N \times N$ and an array $lastElement$ of size $N$. All are initially filled with -1. $lastElements[i]$ tracks the index of the last added job for $T_{i+1}$. $previous[i][j]$ tracks the element added just before j for $T_{i+1}$.

Then the sub-problem is to compute $T_{k+1}$ from $T_{k}$.

This is the pseudo-code:

function next_job(T_last, a_k, t_k, d):

    T = T_last

    for i from 0 to N-1 do:
        if T_last[i] == +inf then break

        begin = max(a_k, T_last[i])
        end = begin + t_k

        if (end > a_k + d) then continue

        if (T[i+1] < end) then:

            T[i+1] = min(T[i+1], end)
            lastElement[i] = k
            if(i > 1) previous[i, k] = lastElement[i-1]
        end
    end

    return T

The final result is of course the largest $i$ such that $T[i]$ is not $+\infty$.
It has a $O(N^2)$ overall time complexity.

To obtain the selection, you pick $elem0 = lastElement[i-1]$, then $elem1 = previous[i-1, elem0]$, then $elem2 = previous[i-2, elem1]$ and so on until you have your i elements.

Let's make a small example with $(a[i], t[i]) = [(0, 60), (10, 30), (50, 20)]$, $d=60$ :

$T_0 = [0, +\infty, +\infty, +\infty]$ => initialization
$T_1 = [0, 60, +\infty, +\infty]$ => one job may be achieved at time=60
$T_2 = [0, 40, +\infty, +\infty]$ => up to now only one job may be selected, but job (10, 30) took the place of (0, 60) as it can be achieved sooner.
$T_3 = [0, 40, 70, +\infty]$ => optimal solution selects 2 jobs.

At the end, $lastElements = [1, 2, -1]$ (starting job indexing at 0)
and $previous = [[-1, -1, -1] [-1, -1, 1] [-1, -1, -1]]$. This let you track the optimal selection $\{1, 2\}$.


You should consider (one of) the word $w$ of minimal length in $S$, and show that for this word in particular, you can reach the conclusion that $|l| = 0$.


Algorithm suggestion for ticket routing system using Machine Learning

Linear regression does not seem like the right tool here.  This isn't a regression problem; it is a classification problem.  Regression outputs a continuous number; you need to output a category (which place the ticket should be routed to; presumably there is a finite list of candidate places).

I would suggest that you learn about natural language processing.  The very simplest thing you could try would be naive Bayes with bag-of-words features.  Fair warning: I would not expect that you will get especially good results without a lot of knowledge of NLP (and maybe not even then); it's probably going to be challenging to find a good solution for your problem.


Remove parallel edges in a directed graph in linear time

Get a list of the edges, this should take no more than $O(|V|+|E|)$ in usual representations.

Run through the edges and check/add them to adjacency matrix represented as hash-table or sparse array. If an edge's entry has been set you know they are parallel. Do some constant time operations during and after iteration to handle the parallel edges how you'd like.


Efficiently selecting a random subset of size $m$ from a set of size $n$

The probability that the element $1$ belongs to a random $m$-subset of an $n$-element set is $m/n$. Therefore you should include $1$ in your subset with probability $m/n$.
If you put $1$ in your subset, then you are left with choosing an $(m-1)$-subset of an $(n-1)$-element set.
If you didn't put $1$ in your subset, then you are left with choosing an $m$-subset of an $(n-1)$-element set.
This means that you have to slightly update your algorithm, replacing $m$ with $m-|L|$.
The resulting algorithm is somewhat similar to reservoir sampling.
A third approach, with some similarities, is generating a random permutation of $1,\ldots,n$ and selecting the first $m$ entries.
The downside of all of these approaches are that they run in time $\Theta(n)$, whereas for $m \ll \sqrt{n}$, your first algorithm runs in (expected) time $\tilde\Theta(m)$.
We can improve on the $\Theta(n)$ running time as follows. We will generate a random ordered $m$-subset given $m$ indices $i_1,\ldots,i_m$, where $i_j \in \{1,\ldots,n-(j-1)\}$. The $j$'th element in the subset will be the $i_j$'th smallest number in $\{1,\ldots,n\}$ out of the numbers not already chosen.
In order to complete the description of the algorithm, we need to solve the following problem: given $S \subseteq \{1,\ldots,n\}$ and $i$, find the $i$'th smallest element in $\overline{S}$. We can assume that $S$ is stored in a structure (such as a self-balancing binary tree) which can efficiently answer the following type of query: given $x$, how many elements in $S$ are smaller than $x$. We can then find the $i$'th smallest number in $\overline{S}$ using binary search.
Overall, this algorithm runs in $\tilde\Theta(m)$ for all values of $m$, where the tilde hides factors logarithmic in $n$. (When $m \ll \sqrt{n}$ we can use your first approach, thus getting rid of this dependence on $n$.)


Hamiltonian path is a special case of your problem. Given a graph $G$, let $f(n,m) = 1$ if the edge $(n,m)$ exists, and $f(n,m) = 2$ otherwise. The minimum value of $g(\sigma)$ equals 1 iff $G$ contains a Hamiltonian path.


How does increasing the page size affect the number of page faults?

Since the number of frames is equal to the size of the memory divided by the page size, increasing the page size will proportionately decrease the number of frames.

Having fewer frames will tend to increase the number of page faults because of the lower freedom in replacement choice.  Imagine a system with four frames with the reference history of 0, 4, 3, 1.  On a page fault, LRU would victimize frame 0.  With a doubling of page size the reference history becomes 0a, 1b, 1a, 0b; so the LRU victim would be 1 (corresponding to small page frames 3 and 4) when one would prefer to victimize 0a (the first half of 0).

Large pages will also waste more space with internal fragmentation.  If a typical process has three sections (text, heap, stack), on average about half a page per section is unused so 1.5 pages worth of memory are unused per process.  If page size is doubled, this waste is doubled.

On the other hand, using larger pages will draw in more memory per fault, so the number of faults may decrease if there is limited contention and/or reasonably high spatial locality at the scale of page size (e.g., references to the high half of a double-size page occurring near in time to references to the low half would make replacement of a double-size page a close approximation of the replacement for the two smaller pages of which it is composed).  (If memory is abundant, first reference [a.k.a. compulsory] page faults will tend to dominate, so larger pages will reduce the number of page faults.)  Of course, the OS can use prefetching to accomplish the same reduction in faults with the benefit of being able to throttle prefetching under heavy memory pressure or poor prefetch behavior while avoiding the above mentioned disadvantages of large pages.

Of course, larger pages do reduce the number of TLB misses (sometimes called minor page faults), and an OS can support multiple page sizes and aggregate smaller pages to form larger pages (for reducing TLB misses) and deaggregate larger pages to from smaller pages (to reduce the volume of memory swapped and to reduce the above negative effects of larger pages).


Here are a few books I recommend:

Discrete math: Concrete Mathematics: A Foundation for Computer Science, Don Knuth. (http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025).

It's very complete and also pretty approachable for someone without much of a theoretical math background.

Algorithms: Algorithms, Kevin Wayne and Bob Sedgwick. Again, very complete and presents all algorithms with motivation and extremely well-written Java code. There's also a really good website with a lot of the info available for free (http://algs4.cs.princeton.edu/home/).

Systems: Computer Systems: A Programmer's Perspective, Bryant and O'Halloran. This one is a little more dense than the two above, but it's a great resource if you know what you want to learn about (e.g. processes, floating point arithmetic). (http://www.amazon.com/Computer-Systems-Programmers-Perspective-Edition/dp/0136108040)

I've had experience with all of these at the undergrad level, so they don't require an enormous amount of experience or higher-level coursework.


Set cover problem with constant size subset

The problem is NP-hard for $k\ge3$. It has a straightforward reduction from the  3-dimensional matching problem.


Find the k-th member of the recursive sequence

Something like this?

$$
\begin{bmatrix}
5 & 2 & 3 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\cdot
\begin{bmatrix}
a_n     & a_{n-1} & 0 \\
a_{n-1} & a_{n-2} & 0 \\
1 & 1 & 0
\end{bmatrix}
=
\begin{bmatrix}
a_{n+1} & a_n     & 0 \\
a_n     & a_{n-1} & 0 \\
1       & 1       & 0
\end{bmatrix}
$$

Therefore $a_k$ is the first element of the matrix:
$$
\begin{bmatrix}
5 & 2 & 3 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}^{k-2}
\cdot
\begin{bmatrix}
a_2     & a_1 & 0 \\
a_1 & a_0 & 0 \\
1 & 1 & 0
\end{bmatrix}.
$$

This only requires $O(\log k)$ matrix multiplications, each of which can be done using a constant amount of arithmetic operations on scalars.


Does space complexity analysis usually include output space?

Typically, we consider space complexity in terms of Turing machines with:

one read-only input tape
one write-only output tape
however many read-write working tapes you want.

The space usage is the number of cells used on the working tapes, so input and output space typically aren't counted.  (See, e.g., Section 2.5 of Papadimitriou.)

Obviously, we don't want to count input space since, then, every algorithm would have to use linear space.  Likewise, we don't want to count output space as that stops us from distinguishing between problems that are hard simply because the output is big (e.g., given an integer $n$, write the list $1, 2, \dots, n$) and problems that are hard because even computing a single output is hard (e.g., output a list of all $3$-colourings of the input graph).

On the other hand, not all authors do this. Sipser defines space usage as just the number of tape cells read by an ordinary Turing machine (Section 8) and the says, more or less, "Oops but that doesn't let us consider any kind of sublinear space, so we'd better redefine it not to include the input" (Section 8.4; he's only considering decision problems, so there's no output to worry about).

I'm not a fan of the redefinition approach but, either way, we need to exclude the input and output if we want to talk about any kind of sublinear space bound.

References
C.H. Papadimitriou, Computational Complexity. Addison–Wesley, 1992.
M.  Sipser, Introduction to the Theory of Computation (3rd edition). Cengage Learning, 2013.


Finding certain elements when only able to ask in chunks

You can eliminate the noise.  Any time you make a query, repeat it 1000 times, use the average of the 1000 responses, and round it to the nearest integer.  The noise in the result before rounding will have variance $1/1000$, so the probability that rounding creates an error is $\operatorname{erfc}(\sqrt{125})$, which is less than $10^{-54}$... i.e., negligibly small (smaller than the probability that a cosmic ray strikes your computer and causes it to give an incorrect result).  This will increase the number of queries by a factor of 1000, i.e., by a constant factor, so it will not affect the asymptotic complexity.
Now once there is no noise, it becomes much easier to solve it.  For instance, you can first find a set of $k$ objects known to be red, then repeatedly randomly sample $n/b$ unknown objects, add $k-n/b$ known-red objects, and query the result; if the response is 1, then you know that one of those is blue, and you can use binary search to find it.  This will require about $O(b \log b)$ queries.  I expect it should be possible to reduce this to $O(b)$ with more cleverness, but I haven't figured that out yet.  A good question is whether you can do substantially better than $O(b)$, if $k \gg b$.


Relaxing the stack in a push down automata

I think the answer is no, even if we disallow unreachable states.

Consider the language $L$ given by the grammar $S ::= \varepsilon \mid abS \mid aSb$.  In this language, every word $w \in L$ has the same number of $a$'s and $b$'s, and every prefix of $w$ has at most as many $b$'s as $a$'s.  Also, if $w \in L$ is not empty, then $w$ starts with $a$ and has length $\ge 2$.

First PDA

Here's one PDA that can recognize that grammar.  It has two states $q_0,q_1$, and the following transitions:

$q_0 \stackrel{a,\epsilon\to \alpha}{\to} q_0$

$q_0 \stackrel{b,\alpha \to \epsilon}{\to} q_0$

$q_0 \stackrel{\epsilon, \epsilon \to \epsilon}{\to} q_1$.

The state $q_1$ is the accept state, and both states are reachable.

If you convert this to a NFA, then the NFA accepts the language $(a|b)^*$.

Second PDA

Here's another PDA that accepts the language $L$.  It has four states $q_0,q_1,q_2,q_3$, and transitions

$q_0 \stackrel{a,\epsilon \to \alpha}{\to} q_1$

$q_1 \stackrel{a,\epsilon\to \alpha}{\to} q_2$

$q_1 \stackrel{b,\alpha \to \epsilon}{\to} q_2$

$q_2 \stackrel{a,\epsilon\to \alpha}{\to} q_2$

$q_2 \stackrel{b,\alpha \to \epsilon}{\to} q_2$

$q_2 \stackrel{\epsilon, \epsilon \to \epsilon}{\to} q_3$

Here $q_0,q_3$ are the accepting states.  All states are reachable.

If you convert this to a NFA, it accepts the language $\varepsilon | a (a|b)^*$.


You're treating resolution as if it were a purely syntactic rule.  It works that way with traditional CNF clauses because that corresponds with the underlying rule of inference.  But a CNF clause with the added restriction of only one literal allowed to be true no longer corresponds to what the resolution rule can be validly applied to.

The Boolean expression $(a \lor b) \land (\lnot{a} \lor \lnot{b}) \land (\lnot{a} \lor b)$ is unsatisfiable as a 1-in-k-SAT formula but naively applying the resolution rule produces $a = false, b = true$ as a (wrong) solution.


What's the Big O runtime of a DFS word search through a matrix?

The complexity will be $O(m*n*4^{s})$ where m is the no. of rows and n is the no. of columns in the 2D matrix and s is the length of the input string.

When we start searching from a character we have 4 choices of neighbors for the first character and subsequent characters have only 3 or less than 3 choices but we can take it as 4 (permissible slopiness in upper bound). This slopiness would be fine in large matrices. So for each character we have 4 choices. Total no. of characters are $s$ where s is the length of the input string. So one invocation of search function of your implementation would take $O(4^{s})$ time.

Also in worst case the search is invoked for $m*n$ times. So an upper bound would be $O(m∗n∗4^{s})$.


Can a non-deterministic machine merge its branches?

One view, explained by Tom here, is that nondeterministic branches work in parallel.

A more standard view, I think, is to view nondeterminism the way it is treated in physics, in logic, and in Dijkstra/Hoare style algorithm specification: at certain points, multiple continuations are possible, one of which will be taken. The 'multiple possible universes' do not exist in parallel, but they are alternative potential states of the world, alternative ways for the algorithm to continue, one of which will become reality.

So no, steps taken in one branch are not available in another branch. You either follow one branch or the other.


To answer this question properly, one needs two things: a model of computation and a notion of (time) complexity. Especially when talking about sub-linear complexity, the influence of the model of computation is extremely important. Starting from linear-time (and especially when dealing with polynomial time), it becomes mostly irrelevant and people avoid mentioning it. Consider addition for example:

Turing machine1 with classical time complexity: addition takes linear time on the size of the input because the machine has to read the inputs and that takes linear time.
Straight-line program(SLP) counting number of instructions: addition is in constant time because there is an instruction for that.
Boolean circuit with depth complexity: addition takes logarithmic time in the size of the input (using an optimized adder).

In fact Turing machines are not a very accurate model of current computers because they cannot do random accesses2 and very little can be done in constant time. This why counter machines and RAM models are more accurate, but also come with their drawbacks. Models such as SLP where addition is a constant time operation are known to be unrealistic because they can produce numbers of exponential size in the number of instructions.

When dealing with numbers, it is common to refer to "bit-complexity" and what it really means is a model that deals with bits and has random access memory. In this kind of model, addition can be done in linear time and multiplication in $O(n\log n \log\log n)$ where $n$ is the number of bits. Wikipedia has a page listing other operations.

1I am going to ignore the possible variations on the number of tapes, in this example we can consider that the two numbers are on different tapes and we have a dedicated output tape.

2Though one can argue that current computers are really only finite automata because they are finite, but this is not necessarily a useful point of view; or that computers really have logarithmic time random access in the size of the memory.


For each of the eight inputs, you compute the output. You will get a table with eight rows and $3+5=8$ columns, containing the three input bits and the five output bits.


Using B trees to search inside dynamically changing array segments

I assume the "B-tree" in your post is in fact a "B+-tree" and array $\small A$ is stored in an increasing manner. Your idea is almost good and needs some small revision.

You need to test whether $\small A[l] \leq key$ and $\small A[r] \geq key$. If $\small A[l] = key$ or $\small A[r] = key$, it is done.
If it is found that $\small A[l] < key$ and $\small A[r] > key$, find the LCA of the blocks containing $\small A[l]$ and $\small A[r]$, as you have done. The height of the LCA is of $\small \mathcal{O}(\log_B(n))$.
If $\small A[l] > key$ or $\small A[r] < key$, then obviously $\small key$ does not exist in $\small [l, r]$.

Why testing $\small A[l] \leq key$ and $\small A[r] \geq key$ is important?

The LCA block may contain entries that direct to blocks outside $\small [l, r]$. If you start from the LCA, you may find a $\small key$ even if $\small key$ does not exist in $\small [l, r]$.


How is Dijkstra's algorithm related to breadth first search(BFS)?

Yes the shortest path trees produced by djikstra's and BFS are identical in the case where the graph edge weights are represented by hop counts or in other words all the edge weights are 1 . Multiple Short Paths don't actually signify any relation with BFS . For finding the shortest Paths with BFS in a weighted graph we have modified versions of the algorithm.


Finding a minimal cover of a subset of a finite cartesian product by cartesian products

NM reformulates this problem in comments as finding minimum number of bipartite cliques (bi-cliques) that cover a bipartite graph. the two sets you mention are the 2 vertex sets of the bipartite graph. the cartesian products of subsets of the two vertex sets are bicliques. wikipedia states this is the bipartite dimension problem and is problem GT18 in Garey and Johnson, proved NP complete based on straightforward reformulation of set basis problem SP7.


Efficient algorithm for rectangle containment

Have you considered multi-dimensional indexes? They are usually quite efficient to find overlapping or included rectangles.

I personally wrote a kind of prefix-sharing binary quadtree: Java sources
It has an API for rectangles with a special method for searching rectangles included in another rectangle: PhTreeSolidF.queryInclude().

I'm not sure what the complexity is but it's roughly something in the order of O(n*k*log n) to build the tree and O(k*log n) for each query (k is the number of dimensions). For strongly clustered datasets it may even become something lose to O(1) for each query (I tested this with n=10.000.000 and 2<=k<=15).


Do there exist fast multiplication algorithms for two integers with one of them being static?

If $N$ is fixed (at least for a very long time), why not do some pre-computation. For example, you can pre-compute the product of $N$ with any 16-bit integer. Just save these values in a lookup table (there are only $2^{16} = 65536$ elements).
Represent $M$ in base $2^{16}$. i.e. $M = a_0 + a_1 * 2^{16} + a_2 * 2^{32} \ldots a_{63}(2^{16})^{63}$.
Well, $M = (N * a_0) + (N * a_1) * 2^{16} + (N * a_2) * 2^{32} \ldots ( N * a_{63}) * (2^{16})^{63}$. Instead of computing $N * a_i$, we can search the lookup table.


Serializable schedules but not view serializable

No.
There doesn't exist any serializable schedule which is not view serializable.


Does a simple calculator require an operating system?

No.

Operating systems have several purposes, such as interfacing with the hardware and, managing multiple concurrent or sequential applications and providing protection between different users. A calculator has only user and only one application so there's nothing to manage there.  And the hardware is simple enough that the single application may as well just talk directly to it, rather than going through the intermediate layer of an operating system.


It is well-known, and stated in Wikipedia (which gives a reference: Lange and Leiß), that there is an algorithm transforming an arbitrary context-free grammar $G$ into a grammar in Chomsky normal form of size $O(|G|^2)$.

The following grammar might be an example showing that the quadratic blow-up is necessary:
$$
\begin{align*}
&S \to A_1 \ldots A_m \\
&A_1 \to A_2 \mid \sigma_1 \\
&A_2 \to A_3 \mid \sigma_2 \\
&\cdots \\
&A_{m-1} \to A_m \mid \sigma_{m-1} \\
&A_m \to \sigma_m
\end{align*}
$$
This grammar has size $\Theta(m)$, and it seems that every grammar in Chomsky normal form for this language must have size $\Omega(m^2)$.


How to come up the number of nodes on a given level in heaps?

You use the principle of scientific induction: you try a few examples and guess a good bound, and then try to prove it. Simultaneously, you try to construct counterexamples. Sometimes your failed attempts at proving a bound help you find a counterexample refuting it.

Often in research one of the hardest steps is to come up with the correct conjectures. This is a creative endeavor and there are no rules which guarantee success. Skill and experience help, but sometimes you just need to be lucky.


How to use the concept of loop invariant to reduce errors in loops?

I'm not terribly familiar with the topic, and as such let's discuss a simpler
variation of your problem. In particular, rather than consider a sorted subarray,
let's suppose our function is given a sorted array instead.

So we are given a value e and a sorted array a[0..r], and our goal
is to have the array a[0..r+1] sorted after insertion of e. For reference, let us
introduce some abbreviations.

$$ Sorted \; a[m..n] ∶≡ (∀ i : m..n • aᵢ ≤ aᵢ₊₁) $$

Now our program has precondition and post-condition

Pre : Sorted a[0..r] ∧ a = A₀
Pos : Sorted a[0..r+1] ∧ e ∈ a[0..r+1] ∧ a is a permutation of A₀ with e inserted

The A₀ is used to make sure that no elements of a are deleted or rewritten;
indeed, setting all elements of the array to e gives us a sorted array that contains
e! But we can simplify matters by simply putting a constraint on the code:
only array swaps are allowed.

Pre : Sorted a[0..r]
Pos : Sorted a[0..r+1] ∧ e ∈ a[0..r+1]

Now a usual way to obtain an invariant from the post-condition is to replace a constant with
a variable and adding an equality to regain the post-condition, so let's try replacing 0 in Pos with j
and add an equality for the two:

Sorted a[j..r+1] ∧ e ∈ a[j..r+1] ∧ j ≈ 0

This clearly establishes the post-condition, so we're on the right track!
Let's simplify it further by breaking the equality up:

Sorted a[j..r+1] ∧ e ∈ a[j..r+1] ∧ j ≤ 0 ∧ 0 ≤ j

Now half of this is easily made-true by taking j ≔ r+1 and aᵣ₊₁ ≔ e
---since Sorted a[r+1..r+1] ≡ aᵣ₊₁ ≤ aᵣ₊₁ and e ∈ a[r+1..r+1] ≡ aᵣ₊₁ ≈ e---
and thus this half we take to be the invariant

P : Sorted a[j..r+1] ∧ e ∈ a[j..r+1] ∧ 0 ≤ j

and the rest we take to be the negation of the loop guard, and so our loop has condition

B : 0 ≤ j - 1

Summarizing so far:
if our loop has guard B and invariant P, then if the loop terminates we must have
the guard is false and the invariant still holds, ie
$Sorted\; a[j..r+1] ∧ e ∈ a[j..r+1] ∧ j ≤ 0 ∧ 0 ≤ j$, and from this the post-condition is
established!

To continue the derivation of our program, we need to the loop (whatever it is, since we have
not yet found it) to terminate, since the above summary said if the loop terminates.
The guard gives us that j is a positive value and so a good
candidate for a bound on the number of iterations in the loop.
It can be decreased by each iteration of the loop by incrementing it, j ≔ j -1, and so that is what we try do.

Of course the invariant, by definition, must be left-true by the body of the loop.
In particular, assuming the invariant and the guard, we must show that the invariant still holds
after execution of the proposed loop-body j ≔ j -1.

  P still holds after execution of j ≔ j - 1
≡⟨ definitions ⟩
  Sorted a[j-1..r+1] ∧ e ∈ a[j-1..r+1] ∧ 0 ≤ j-1
≡⟨ 0 ≤ j - 1 follows from B ⟩
  Sorted a[j-1..r+1] ∧ e ∈ a[j-1..r+1]
≡⟨ e ∈ a[j-1..r+1] ≡ e ≈ aⱼ₋₁ ∨ e ∈ a[j..r+1], and this follows from P ⟩
  Sorted a[j-1..r+1]
≡⟨ By P we know that Sorted a[j..r+1],
   so a[j-1..r+1] is sorted precisely when aⱼ₋₁ ≤ aⱼ ⟩
  aⱼ₋₁ ≤ aⱼ

So we need the decrement to be guarded by this condition.
But what if this condition does not hold; ie instead we have aⱼ < aⱼ₋₁?
Then we can obtain the needed condition by swapping the indices and so
the loop body becomes

if aⱼ < aⱼ₋₁ then swap(j, j-1);
j ≔ j-1;

So we've obtain a terminating loop and so our summary above means we are done.
So the resulting program is:

j ≔ r+1;
aᵣ₊₁ ≔ e;
while 0 ≤ j - 1:
   if aⱼ < aⱼ₋₁ then swap(j, j-1);
   j ≔ j - 1

That is,

aᵣ₊₁ ≔ e;
for(int j = 0; 0 < j; j--)
   if aⱼ < aⱼ₋₁ then swap(j, j-1);

Let's try it out.

Given sorted array a = [1,2,3,4,5] and value e = 3
we get $r = 5$ and so, letting | denote where we are looking
in the array, the loop looks as follows:

j  a
6  [1,2,3,4,5 | 3]
5  [1,2,3,4 | 3,5]
4  [1,2,3| 3,4,5]
3  [1,2| 3,3,4,5]
2  [1| 2,3,3,4,5]
1  [|1, 2,3,3,4,5]

In particular, note that since the array is initially sorted, the moment
we stop making swaps we no longer make any swaps at all and just decrement
the counter. With this mind, we can be a bit perverse (for the sake of efficiency?)
and write

aᵣ₊₁ ≔ e;
for(int j = 0; 0 < j; j--)
   if aⱼ < aⱼ₋₁ then swap(j, j-1) else return;

Hope this helps!


4-bit input, 5-bit output, logical right shift by 2, which is the correct set of 5 output bits?

There are two ways to do a shift: either the "new"  digit (the leftmost, msb) is set to zero, or it is set to the digit that was there before. The former is usually called logical shift while the latter preserves the sign of the number (in case you use the complement representation) and is called arithmetic shift. But sometimes both are just called shift, and one needs to clarify the desired behavior.

Since you as about buffers of length 5 bits, the msb is anyway 0 so logical shift-arithmetic shift, and I'd say the 2-bit right shift is:

01110  -> 00111 -> 00011
01111  -> 00111 -> 00011


How to initialize the first h in an RNN?

There are a few different ways. One way is to always give it a zero vector, or some other constant that means "new sequence". Another way is to train the initial state vector just like you train any other weight: initialize it randomly, then apply gradient descent during training. The former is easier and faster, but the latter can sometimes make the RNN more effective.


Proof: There exists an irregular language L such that LLLL is regular

Let us prove a more general result:

  For each $m \geq 2$ there is a language $L$ such that $L,L^2,\ldots,L^{m-1}$ are not regular but $L^m$ is regular.

The language we construct will be unary, that is, of the form $L = \{a^n : n \in S\}$, where $S \subseteq \mathbb{N}$ is
$$
S = \{ km : k \geq 0 \} \cup \{ m^k + 1 : k \geq 1 \}.
$$
Let $1 \leq p \leq m-1$, and consider $p \cdot S$, i.e., the set of all sums of $p$ elements from $S$. Since all elements in $S$ are equivalent to either $0$ or $1$ modulo $m$, if $a \in S$ is equivalent to $p$ modulo $m$ then it must have the form
$$a = m^{k_1} + 1 + \cdots + m^{k_p} + 1. $$
The base $m$ representation of $a$ thus has at most $p+1$ non-zero digits (it could have fewer if some of the $k_i$ are equal). It is easy to check that a vanishing fraction of numbers have this property.

Let $L_{m,p} = \{ a^{km+p} : k \geq 0\}$. It follows that $L' = L^p \cap L_{m,p}$ is an infinite language with vanishing density, and so it cannot be regular (since regular unary languages are eventually periodic, and so if they have vanishing density they must be finite). Since $L_{m,p}$ is regular, it follows that $L^p$ isn't regular.

In contrast, $m \cdot S$ is cofinite — it contains all integers which are at least $m^2-1$ — and so $L^m$ is regular.

The language constructed above has the "regularity profile" $\{k : k \geq m\}$. This is the set of powers $k \geq 1$ such that $L^k$ is regular ($L^0$ is always regular). This prompts the following question:

  What regularity profiles are possible?

Any regularity profile is closed under addition, but are there any other constraints?