Infix vs postfix vs prefix - which has the smallest processing time

You can express the same in prefix and postfix without brackets.

For example, a + b * c can be ambiguous so it can give 2 different results so you need some precedence to solve the expression(as you have mentioned BODMAS) but both the trees if traveled in prefix or postfix leads to a unique results like (a + b) * c will have postfix ab+c* and a + (b * c) will have abc*+.


RTU stands for Return To User. This is invoked when the OS first accesses a physical memory range, and upon doing so will return the memory range address (code).


CFG for $L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$

I'm going to address the second part of the question first, about a "smarter grammar." One improvement that can be made is omitting the rules

$$S \rightarrow Sc \hspace{10px}| \hspace{10px} Sd.$$

Assuming we have made that change, to answer the first part, if the grammar is correct we need to answer two questions.

Does $S$ only generate strings within $L$?
Can every string in $L$ be generated by $S$?

If the answer to these questions is both yes, then a string is in $L$ if and only if it is generated by $S$, which means that $S$ is a correct grammar for the language.

The answer to 1. is clearly yes because every string generated by $S$ must have the same number of $a$'s as it does $b$'s because in every rule where an $a$ is present a $b$ is also present, and vise versa.

The answer to number 2 is a bit trickier. We will use induction on $|\omega|_a = |\omega|_b$ to show that any string in $L$ can be generated by $S$

(Base case $n=0$) If $|\omega|_a = |\omega|_b = 0$, then $\omega$ consists of a sequence of $c$'s and $d$'s, and can be generated by scanning over it using the rules

$$S \rightarrow cS \hspace{10px} | \hspace{10px} dS$$

until we terminate with $S \rightarrow \epsilon$.

($n$ implies $n+1$) Assume by induction that for all $\omega \in L$ with $|\omega|_a = |\omega|_b \leq n$ that $\omega$ can be generated by $S$. Now let $\omega' \in L$ be such that $|\omega'|_a = |\omega'|_b = n+1$.

At some point in $\omega'$ there must be at least one time that an $a$ comes before a $b$ (with only $c$'s and $d$'s between them) or a $b$ comes before an $a$ (with only $c$'s and $d$'s between them). Without loss of generality, we can assume there is an $a$ that comes before a $b$.

Now, we can decompose $\omega' = XaYbZ$ where $|X|_a + |Z|_a = |XZ|_a = n$  (and the same for $b$) and $Y \in \{c,d\}^*$ . This holds because we are taking one $a$ and one $b$ from $\omega'$ which had $n+1$ of each which leaves $n$ in the rest of the string, and we know that there is a pair of $a$ and $b$ with just $c$ and $d$ between.

Now we can get a little clever and observe that the string $XcZ \in L$ and $|XcZ|_a = |XcZ|_b = n$ and therefore, by the inductive hypothesis, $XcZ$ can be generated by $S$.

Now here's the tricky part. Consider the process that generated $XcZ$. At some point in the generation, we must have used the rule $S \rightarrow cS$ to generate the $c$ between $X$ and $Z$. If we instead chose to use

$$S \rightarrow aS^*bS$$

as the expansion where $S^*$ generates $Y$ as in the case where $n = 0$, and did everything else exactly the same, then what happens is we replace the $c$ in $XcZ$ with $aYb$, and get the string $XaYbZ$. This demonstrates that $\omega'$ can be generated by $L$ because we have just found a process by which it can be generated by $S$.

Therefore by induction on $|\omega|_a = |\omega|_b$ every string in $L$ can be generated by $S$.


Example for the analysis of a recursive function

Here's the correct recurrence for the running time of rec:
$$
f(i,j) = \begin{cases} O(1), & i = 0 \text{ or } j = 0, \\
f(i-1,j) + f(i,j-1) + f(i-1,j-1) + O(1), & \text{otherwise}. \end{cases}
$$
The running time of the entire program is $f(n,n) + O(n^2)$. Now it remains to solve the recurrence for $f$, which I leave to you.


A context-free grammar for all strings that end in b and have an even number of bs

There is an easy and very natural way how to derive a context-free grammar $G=(V,\Sigma,R,S)$ from a DEA $M=(Q,\Sigma,\delta,q_0,F)$. We set

$V=Q$
$S= q_0$
$R$ consists of the following rules:

for all $X\in Q$ and $a\in \Sigma$ with $Y=\delta(X,a)$ we add the rule $X \to aY$
for all $X\in F$  we add the rule $X \to \varepsilon$
there are no other rules in $R$

It's an easy exercise to show that $L(G)=L(M)$. With this technique you can now build your automaton first (which is an easy two-state example in your case), and then apply this construction.


Formalism for unambiguous context-sensitive languages?

Actually, I found something close enough to what I want. They're unambiguous boolean grammars and they're both unambiguous and strictly more powerful than context-free grammars. Other people may find this useful, so I decided to share it.


Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions

The length of the walk is the number of edges in the walk. Suppose $p$ is a walk labeled $w$. We can decompose $p$ into $p_1 e_1 p_2 e_2 \cdots p_{|w|} e_{|w|} p_{|w|+1}$, where each $p_i$ consists only of $\lambda$-transitions, and $e_i$ is a transition labeled $w_i$. There is always an equivalent walk in which no transition is taken twice in each $e_i$ (this is what is proved in the paragraph you quote), and so $|p_i| \leq \Lambda$. Therefore the entire walk has length at most $(1 + \Lambda) |w| + \Lambda$.


Delaunay Triangulation on Convex Polytopes — Uniform Sampling

This is an active area of research. Fortunately, recently there has been a breakthrough due to Vempala and Cousins [1]. They provide a MATLAB implementation of their algorithm. If you're interested in the technical details, you can check out some slides from a recent workshop.

This algorithm only samples points approximately uniformly. Exact uniform sampling, or rather the related volume estimation problem, is known to be hard (under reasonable assumptions) in general. Your convex body isn't general, however – it's a polytope. Nevertheless, the answers to this question suggest that there is no better algorithm for this special case (they suggest employing general algorithms which are older than Cousins–Vempala).

Bypassing KLS: Gaussian Cooling and an $O^*(n^3)$ Volume Algorithm by B. Cousins and S. Vempala (2014, preprint)


Analyzing time complexity for change making algorithm (Brute force)

First, when computing the $n$-th fibonacci number $F(n)$, the number of branches (leaves) is not $2^n$, but exactly $F(n)$. But you can say it is $O(2^n)$.

As for the coin change problem it is not $O(n^C)$. $n^C$ is a polynomial, while the number of branches in the tree  grows exponentially. In other words, given $n$ number of coin denominations and constant $C$, each node has no more than $C$ children, and so the number of branches/leaves is at most $C\times C\times \dots C$ ($n$ times). In fact the actual number of branches is less than $C^n$, but is definitely bounded from above by $C^n$, and so is $O(C^n)$ (recall that big-O denotes the upper bound of a function).


Polytime algorithm for SUBSET-SUM assuming P=NP

I can half-answer this, but I believe the deeper question you are getting at is something I am in the process of learning better :)

The algorithm on wikipedia, call it W, is based on the idea: rather than guess at certificates why not just guess at the deterministic P algorithm D itself? This is expensive, but since it is independent of the input it is O(1) (if such an algorithm exists). The algorithm actually always decides even if P != NP, because there is of course a series of "brute force" programs that print out just one possible certificate then halt, so W can fall back to a very slow brute force.

The problem is that you actually have no way to verify the program it returns to you. You may imagine running W and find it seems to prefer a certain program, but you may find that on larger input it eventually finds a flaw in that program and moves on. It may seem to settle on an algorithm that seems to be $n^7$ but later on find a mistake in it and switch to an $n^{2000}$ algorithm. You will never know when it has found the "right" one.

This is actually the same idea used in the proof of the Karp-Lipton theorem: given enough computation power you can use it to just start guessing entire classes of programs and verify that they work (the proof is exactly, "guess a program, and verify that it works, then use it", which takes a bit of computational power - more than NP - to pull off.)

I am not aware of theory regarding how complicated a solution can be, but perhaps someone more knowledgeable can answer.

The more concrete scenario in the P=NP reality is that someone actually constructs an algorithm to any NP-complete problem, such as SAT.

I think you asked a good question and I'm curious how to fill in the gaps in my answer, regarding how W may be analyzed and made more useful in semi-practice.


The answers you give are wrong. It is easy to verify that $n, n\log n \in o(n^2)$, and similarly $n^2 \log n,  n^3 \in ω(n^2)$.

  Give two functions that is in $O(n^2)$ but not in $o(n^2)$.

Looking at the definitions, we see that there are two ways to come up with such a function:

Pick any function from $\Theta(n^2)$.

Besides the obvious candidates of the form $cn^2 + o(n^2)$, there are also more obscure ones like, for instance $ 2^{\frac{\sin n}{\log n}} \cdot n^2$.
Pick any function $f \in O(n^2)$ for which $\lim_{n \to \infty} f(n) \cdot n^{-2}$ does not exist.

Simple examples are $(2 + \sin(n)) \cdot n^2$ or $2^{\sin n} \cdot n^2$ or

$\qquad \displaystyle f(n) = \begin{cases}n^2, &n \in 2\mathbb{N};\\n, &n \in 2\mathbb{N}+1.\end{cases}$

There are many more.

I'll leave the proofs to you as an exercise, as well as the symmetric case with $\Omega$ vs $\omega$.


Show that LOOP is reducible to Complement of Halting problem

The question is given you have an oracle machine/black box for HPC can you decide if <M,w1,w2,w3> is in LOOP.
See the wikipedia page on that: https://en.m.wikipedia.org/wiki/Reduction_(recursion_theory)#Turing_reducibility
The proof is very straightforward as you already know.


How can I compare two recurrence relation to find which one is better on large inputs

The simplest way is to solve both recurrence relations, and see whether one of them grows faster. In your case there is actually no need to do that, since we can observe that on the one hand
$$
T_1(n) \geq 2T_1(n-1) \geq 2^2T_1(n-2) \geq \cdots \geq 2^{n-1}T(1) = 2^{n-1},
$$
and on the other hand
$$
T_2(n) = O(n^2),
$$
by the master theorem. This is enough to deduce that $T_2(n) = o(T_1(n))$, that is, $T_1(n)$ grows faster than $T_2(n)$.


Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?

Note

\begin{align}
0&=H(C|A,B)\\
&=H(A,B,C)-H(A,B)\\
&=H(B|A,C)+H(C|A)+H(A)-H(A,B)\quad\text{(chain rule)}\\
&=H(B|A,C)+H(C|A)-H(B|A),
\end{align}

so $H(C|A)=H(B)$ is equivalently $H(B|A,C)+H(B)-H(B|A)=0$. Also note $H(B|A,C)\ge 0$ and $H(B)\ge H(B|A)$, your condition is equivalently $H(B|A,C)=0\wedge H(B)=H(B|A)$.

For a human-readable explanation, $H(B|A,C)=0$ means $B$ is determined by $A$ and $C$, that is, for any fixed $a$ in the support of $A$, $f(a,b)$ as a function of $b$ with domain $\{b\mid \mathrm{Pr}\{A=a, B=b\}>0\}$ is an injection. $H(B)=H(B|A)$ means $A$ and $B$ are independent of each other.


Multitape Turing machine with multiple non-blank tapes

The restriction to a single non-blank tape at the start (and a single output tape too) is just convention – it makes the definitions a little simpler and maybe simplifies the analysis a little.

The reason we can make this restriction is that it makes no difference to the class of functions that are computable and it also makes no significant difference to the running time of algorithms. Any interesting Turing machine algorithm is going to need linear time since, otherwise, it can't even read all its input. For example, how would a Turing machine know to halt after $\log n$ steps? It's not read all its input in that time, so it doesn't even know what $n$ is!

This means that any linear-time preprocessing you do before the main part of your algorithm can't affect the asymptotic running time. So, in particular, you can check that, for example, your single input tape consists of three binary numbers separated by semi-colons, and copy those three numbers onto three separate tapes. Then you can run your main algorithm that thinks it has three different input tapes.
Likewise, any Turing machine must run in time at least linear in the size of its output. This means that, if you have a machine whose output is spread across multiple tapes, you can postprocess that by copying it onto a single tape with the different parts separated by some special character.

As Raphael points out in his comment, there is at least one model that has more than one non-empty tape at the start. Probabilitstic Turing machines can be defined either by having multiple possible transitions from each state, each with an associated probability. Alternatively, they can be defined as deterministic Turing machine that has access to an infinite tape initialized with random bits. Note that this takes us outside the standard Turing machien model because we now have an infinite input. (This equivalence of a probabilistic machine on deterministic data versus a deterministic machine on random data is closely related to Yao's principle.)


Algorithm to get the number of iterations needed, if possible, to get an specific 2 element array

You have observed several impossible situations for $x$ and $y$, such as when $x$ and $y$ are both even or multiples of $3$, etc. More generally, we have the following characterization. For all positive integer $x$ and $y$,
$$(x,y)\text{ is reachable} \iff \gcd(x,y)=1$$
where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$. That characterization can be proved easily by mathematical induction on $n=x+y$, since $$\gcd(x,y)=\gcd(x, x+y)=\gcd(x+y,y).$$
"The goal is to know how many steps are needed in order to get a given pair $(x,y)$." Here is a simple Python program that should be fast enough. It takes less than a hundredth of a second even if $x$ and $y$ have hundreds of decimal digits. The crux of the program is, count += x // y and x, y = y, x % y, which uses integer division and remainder to reduce $x$ to be smaller than $y$.
def number_of_iterations_needed(x, y):
    count = 0

    if x < y:
        x, y = y, x
    # Now x >= y

    while x % y != 0:
        count += x // y
        x, y = y, x % y
    # Now x % y == 0

    if y != 1:
        return None  # impossible
    else:
        count += x - y
        return count

In fact, the above program is just an augmented version of the well-known Euclidean algorithm, the granddaddy of all algorithms. Its time-complexity should be about the same as the time-complexity of the Euclidean algorithm, which is $O(\ln(\min(x,y))$. It uses about $O(1)$ space.
If you are searching for a closed form for the number of iterations needed given $x$ and $y$, you will probably not be able to find one since, as indicated on that Wikipedia page, nobody has come up with a closed form after more than two thousand years.


Let's assume that $3^n = O(n^2)$.

This would by definition mean that there are real positive numbers $a$ and $b$ such that for any sufficiently large $n$ (or to say as $lim_{n \to +\infty}$):

$ an^2 \leq 3^n \leq bn^2 $

Dividing everything by $3^n$ we get:

$ a\frac{n^2}{3^n} \leq 1 \leq b\frac{n^2}{3^n}$

And since if we let $lim_{n \to +\infty}$ we get a contradiction:

$ 0 \leq 1 \leq 0 $

Hence inital statement is false and $ 3^n \neq O(n^2) $


Checking whether two 32-bit integers are equal can be done in a single machine instruction.

Checking whether two strings are equal can take a lot longer.  If my two strings are each 100 characters long, then checking whether those two strings are equal might require the equivalent of about 100 machine instructions: I have to check them, character by character.

In asymptotic complexity terms: checking equality of (fixed-precision) integers takes $O(1)$ time, checking equality of strings takes $O(n)$, where $n$ denotes the length of each string.


Allowing an empty (epsilon) transition in a PDA

Some key points:

The only case where you want to accept $\epsilon$ is when you haven't had any other input and your stack is empty. Therefore you need an accepting state right at the beginning.
You need to take into consideration inputs such as: $bac, aac,...$ that will never result in an accepting state, or $abbb$ that results in an accepting state without containing any $c$'s
If you get a $b$ and your stack is empty you have more $b$'s than $a$'s so you need an accepting state
If you get a $c$ and and your stack is not empty you have more $a$'s than $b$'s so you need an accepting state
You reject everything else.


You need to define $L$ carefully. Currently, you seem to require only these properties:

"$L$ proves $[A \in \mathsf{P}]$" implies $A \in \mathsf{P}$
"$L$ proves $[A \in \mathsf{NP}]$" implies $A \in \mathsf{NP}$
"$L$ proves $[\mathrm{SAT} \in \mathsf{NP}]$"

Let $L$ be such that it ever proves only these two statements:

$[\mathrm{ONE} \in \mathsf{P}]$, where $\mathrm{ONE}$ is a dummy problem like "always accept", which is clearly in $\mathsf{P}$.
$[\mathrm{SAT} \in \mathsf{NP}]$

Then $\mathsf{ProvableP} = \{\mathrm{ONE}\}$ and $\mathsf{ProvableNP} = \{\mathrm{SAT}\}$, which are different even if $\mathsf{P}=\mathsf{NP}$. Note also that $\mathsf{ProvableP} \nsubseteq \mathsf{ProvableNP}$.


Find two contiguous subarrays with the greatest difference

Because the two subarrays are disjoint, there exists at least one index $m$ such that one entire subarray lies $\leq m$ and the other subarray lies $\gt m$.

But we do not know what this $m$ is, beforehand. So let us iterate over all the $n$ possibilities for $m$. Now if an $m$ is fixed, then the problem reduces to the Maximum subarray problem, and the Minimum subarray problem. This is because for the absolute difference to be the largest, one side of $m$ should have the maximum possible subarray, and the other side should have the minimum possible subarray. So we try both of these options and take the maximum absolute difference among the two.

But this is still $\mathcal{O}(n^2)$, because there are $n$ different values of $m$, and for each of those values, we have to spend $\mathcal{O}(n)$ time to compute the needed minimum and maximum subarrays.

The next observation is to note that a single $\mathcal{O}(n)$ run of the Maximum subarray algorithm on the entire array can actually give us one of the needed values for all values of $m$:

Given: int A[n]

MaxSubarrayTill[0] = A[0]
MaxSubarrayEndingAt[0] = A[0]
for(i = 1; i < n ; i++)
{
    MaxSubarrayEndingAt[i] = max{A[i], MaxSubarrayEndingAt[i - 1] + A[i]}
    MaxSubarrayTill[i] = max{MaxSubarrayTill[i - 1], MaxSubarrayEndingAt[i]}
}

Here, $\text{MaxSubarrayTill}[i]$ denotes the maximum sum subarray which ends $\le i$, and $\text{MaxSubarrayEndingAt}[i]$ denotes the maximum sum subarray which ends at index $i$.

Similarly, we can compute the $\text{MinSubarrayTill}[i]$ array in $\mathcal{O}(n)$ time. And by repeating the same two algorithms in reverse (ie. from the end of the array to the beginning), we can get $\text{MaxSubarrayFrom}[i]$ and $\text{MinSubarrayFrom}[i]$.

So in $\mathcal{O}(n)$ time we have precomputed all the values that we needed in the first algorithm, which we can now go back to. Interate over all the values of $m$, and find the largest absolute difference in $\mathcal{O}(n)$ time.

If the problem also stipulates that the two subarrays should be adjacent, then we can leave out $\text{MaxSubarrayTill}[i]$ and its analogous arrays, and instead only consider $\text{MaxSubarrayEndingAt}[i]$ and its analogous three other arrays. The rest of the algorthm remains the same.


What can be said about Θ-classes in m and n if we know that m < n?

If $m=\Theta(n^2)$, then indeed $\Theta(m\log n)=\Theta(n^2\log n)$.

However, you are only given that $0<m<n^2$, that is, $m=O(n^2)$ and you can only infer that the algorithm has complexity $O(n^2 \log n)$, but not $\Theta$ of the same quantity. For instance, assume $m$ is a constant, or assume $m=\sqrt{n}$, and you could see why it cannot be $\Theta(n^2\log n)$.


NP Problem that cannot be solved by a quantum computer in polynomial time

Nobody really knows whether quantum computers can solve all NP complete problems in polynomial time or not. There is strong evidence that they cannot: Strengths and Weaknesses of Quantum Computing, but no definite proof.


Proving that Turing Machine M runs in time $O(2^{dn})$

Your intuition is problematic, for the following reason: you are given a specific machine $M$, not a language. Therefore, if you describe an algorithm that runs in $O(2^{dn})$ and decides the same language, you effectively prove that $L(M)$ is decidable in $O(2^{dn})$, but that does not imply that $M$ itself runs in that time frame.

As the hint suggests, consider the number of possible configurations of $M$: recall that a configuration of a TM consists of the contents of the tape, the position of the head, and the state. Given that the alphabet of the machine is fixed, and that the tape used in the run of $M$ on $x$ is of size $c\cdot |x|$, try to bound the number of possible configurations (expressed in the size of $M$ and $|x|$)

Now, recall that $M$ always halts. What does that mean about the sequence of configurations it goes through in its run on $x$?

Combining these two observations you will get the answer. Comment if you need more hints.


Undecidability of whether a given TM halts or only has loops which can be detected by some TM

(too long for a comment)

Here's my attempt at an unambiguous version of what you are trying to get across.

  Is it the case that for every total Turing machine M,

  if[
  for all $\langle d,n\rangle$ in $\{0,1,2,3,...\}^2$, $\:$ if M accepts $\langle d,n\rangle$ then

  $d$ describes a Turing machine that enters a loop on input $n$,
  ]then[
  there is a many-one reduction from the Halting Problem

  to the set of $d$ in $\{0,1,2,3,...\}$ such that
  [
  $\hspace{.01 in}d$ describes a total Turing machine or $\big[\big[$for all $n$ in $\{0,1,2,3,...\}$,

  if $d$ enters a loop on input $n$ then M accepts $\langle d,n\rangle\big]$ and there exists such an $n\big]$
  ]?


In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular

It is not true that fractional solutions can necessarily be turned into integral solutions.  For example, suppose that 1 requires either slots A and B, or slots D and E; 2 requires either slots B and C, or slots E and F; and 3 requires either slots A and C, or slots D and F.  It's easy to check there is no integral solution at all (A,B,C together can accommodate at most one, and D,E,F together can accommodate at most one).  However there is a fractional solution of giving everyone 1/2 of every slot that might possibly accommodate them.
There are conditions such as total unimodularity that guarantee that there are optimal integral solutions.  In that case, the problem is in P, because all that is needed is to solve the LP relaxation which can be done in polynomial time.


50% I/O wait time means that a process is not in execution(i.e. CPU is sitting idle) for 50% of the total time a process requires from CPU to complete itself(its execution). Thus CPU Utilization turns out to be
//whereas 50% I/O time means it needs 50% of total execution time(10 minutes) to complete its I/O.

50%=50/100 = .5

thus the time needed to complete a process which requires 10 minute of CPU will be = CPU time required by process/CPU utilization=

10/CPU utilization=  10/0.5 =  20 minutes.

when two processes run sequentially(one after the other) then the total time required will be =  10/0.5 + 10/0.5 =  20+20=40 minutes (ANSWER)

in case of parallel execution we again find the CPU utilization..
since two processes are in parallel thus the formulae becomes-->

{1-(I/O time)^no. of processes in parallel execution}
=1-(0.5)^2=1-.25=0.75
now the CPU utilization for 1 process will be 0.75/2=0.375
Therefore the time required will be =
CPU time required by process/CPU utilization=
10/0.375=26.67 minutes.

Since the two processes are running in parallel thus the time required by 1 process will be the total time required by 2 process=26.67 minutes(ANSWER)


Algorithm for solving planar constraint problem ("Pokemon Go monster finding")

I think you could use a "spatial join". I haven't played the game, but I assume $d_{max}$ is rather small, i.e. there are in the order of 10 or so $n$ and $m$ in the neighborhood of each $m$. I further assume that $N$ and $M$ are large, say 1,000,000 or more.

Put all $m$ as 2D points in a spatial index
For each $m_1$ in the index, perform a spatial range query with distance $2*d_{max}$. This gives you all other $m_x$ that can potentially contain the same $n$ as $m_1$. This should be manageable because the number of $m_x$ should be small (as I assumed above).
Now, by getting all other estimated measurements for a particular $n$, you can try to approximate the correct $n$
(Potential optimisation): Depending on your spatial index, you can remove the $m_1$ after processing all it's $n$. This makes the dataset smaller for the following range queries. Also,

Somehow you would also need to uniquely identify each $n$, so that you don't calculate the position of $n$ again if it turns up when processing another $m$.

As an optimisation, you may want to use window queries (rectangular) rather than circular range queries. Window queries can be much faster and give only slightly more results. Also, it could be that the game actually does not use euclidean distance (circles) but the faster manhatten distance, which would be exactly a rectangle.

For such a spatial join you can use any spatial index, such as R-Tree, kd-Tree, quadtree or any of their variants.

For large datasets I would probably not use a R-Tree (R+tree, R*-tree, X-Tree), or a special variant of the quadtree, the PH-Tree, which is well suited for range queries as well as allowing fast removal (or addition) of points.

For Java, implementations of R-Trees can be found in the anywhere on the internet, for example in the ELKI framework or my own TinSpin Index library. The PH-Tree is also available in Java.

A generic spatial join algorithm is called TOUCH, but I don't think it is open source.


Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number?

Suppose there is an algorithm $A(G,c)$ which runs in time $T(n)$, where $n$ is the number of vertices in $G$, as long as $c$ is the vertex cover number.
Given a graph $G$, run $A(G,0),\ldots,A(G,n)$ in parallel, for $T(n)$ time each. Some of the copies will terminate within $T(n)$, outputting a set. Out of all such outputs which are vertex covers, choose the one of minimal size. This gives an algorithm for minimum vertex cover running in time $O(nT(n))$.


The constant $1/3$ is completely arbitrary. Let's say that $\mathsf{BPP}_p$ is the class of problems solvable in polytime with error at most $p$. Then $\mathsf{BPP}_p = \mathsf{BPP}_q$ for any $0 < p,q < 1/2$. The simple proof can be found in any decent textbook or lectures notes on complexity theory, and is also a nice exercise. The idea is that you can boost the success probability by running the algorithm several times and take a majority vote (details left to you).

Why do we like $1/3$, then? It's the "simplest" rational number in $(0,1/2)$: for example, it is the rational number in $(0,1/2)$ with the minimal possible denominator, and with the minimal sum of numerator and denominator.


Array with queries to decrement or find sum of range

Suppose that your array is $a_1,\ldots,a_n$, but instead of storing it this way, you store the differences $\delta_i = a_i - a_{i-1}$ (where $a_0 = 0$). Decrementing $a_i,\ldots,a_j$ by $x$ is then the same as decrementing $\delta_i$ by $x$ and incrementing $\delta_{j+1}$ by $x$. Querying the prefix sum $a_1 + \cdots + a_j$ (using which you can query the sum of any range) amounts to calculating
$$
\sum_{t=1}^j \sum_{k=1}^t \delta_k = \sum_{k=1}^j \sum_{t=k}^j \delta_k = \sum_{k=1}^j (j-k+1)\delta_k = (j+1)\sum_{k=1}^j \delta_k - \sum_{k=1}^j k\delta_k.
$$
The idea now is to use a Fenwick tree, which is an array data structure which can perform both element updates and prefix sums in $O(\log n)$. We use two Fenwick trees, one storing $\delta_1,\ldots,\delta_n$ and the other storing $\delta_1,2\delta_2,\ldots,n\delta_n$ (we can in fact merge them into a single Fenwick tree which stores information for both values at every node). Above we have outlined how to perform each of your two queries in $O(\log n)$.


What do you call a lower/upper bound that is the best one?

The phrase you're looking for is tight bound or in your case a tight upper bound.


Check the Regularity of the folowing Languages

Your reasoning regarding $L_1$ is wrong. What you show is that for each $n$, the following language is regular whenever $A$ is regular:
$$
L_1^{(n)} = \{ x : x^n \in A \}.
$$
The language $L_1$ is the infinite union of $L_1^{(n)}$ for all $n \geq 0$. Unfortunately, regular languages are not closed under infinite union (for example, every unary language is an infinite union of singleton languages).

Nevertheless, $L_1$ is regular. Given a DFA $\langle Q,q_0,F,\delta \rangle$ for $A$, we construct a DFA for $L_1$ whose set of states is the set of all functions $Q \to Q$. The initial state $id$ is the identity function, and we construction the automaton so that $\delta_{L_1}(id,w)$ is the function that maps $\sigma \in Q$ to $\delta(\sigma,w)$. This gives us enough information to determine whether any power of $w$ belongs to $A$.

The language $L_2$, in contrast, is not necessarily regular. For example, if $A = ab^*$ then $L_2 \cap ab^*ab^* = \{ ab^n ab^n : n \geq 0 \}$, which isn't regular.


How to determine if a state is a fixed point in a Hopfield network?

It's as simple as that.  Write out the state equation.  Substitute the state vector.  Verify that equality holds.   If it does, then you have a fixed point.

Note that what you're calling a state vector probably isn't one in the typical definition of that term.  The vector of neuron inputs is usually called the state vector. It would be unusual (though of course not impossible) for this to be all 1's.

If what you actually have is the output vector, then you can solve for the state vector using the feedback function.  Then verify the resulting state vector is consistent with the outputs.  If so, then you have a fixed point.


A program that cannot be written in (simply-)typed lambda calculus but only in lambda calculus or Turing-complete language

The distinction isn't just about being able to write non-terminating programs. There are significant differences even between normalizing lambda calculi. For example, consider System F. It's normalizing, so all its programs are terminating (so it's not Turing complete), but it has much more expressive power than the simply-typed lambda calculus (it can express any function that can be proved total in second-order Peano arithmetic).

Perhaps the simplest example is Church numerals. In System F Church numerals can be expressed as terms of type $\forall\alpha. (\alpha\to\alpha)\to(\alpha\to\alpha)$. Each natural number $n$ is then represented as
$$\Lambda\alpha.\lambda f:(\alpha\to\alpha).\;\lambda x:\alpha.\; f^n x$$ where $f^n x \equiv \underbrace{f(f(...f}_{n\mbox{-times}} (x)...))$. In the untyped lambda calculus it would be just $\lambda fx.f^n x$.

However, we cannot represent Church numerals and operations on them in the simply typed lambda calculus, because it lacks the necessary polymorphism.

Church numerals can be viewed as one of the simplest recursive data structures. In Haskell we could represent them as

data Nat = Z | S Nat

foldNat :: Nat -> (r -> r) -> (r -> r)
foldNat Z     f z  = z
foldNat (S n) f z  = f (foldNat n f z)

(Observe that foldNat actually converts our representation into the System-F representation.)

System F and the untyped lambda calculus allow us to represent any (inductive) recursive data structures such as list, trees etc. in the similar way as we represented Church Numerals (see System F Structures). This is not possible in the simply typed lambda calculus - it can express only non-recursive data structures with bounded size.

A good source of information is Proofs and Types by Jean-Yves Girard, Yves Lafont and Paul Taylor.


What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?

Your answer actually depends on what implementation of Dijkstra's algorithm is used. The textbook implementation inserts all nodes in the queue, and then proceeds with the extraction. The other starts with only the source in the queue. This is generally more efficient in practice, although it needs a bit of book-keeping.

For the standard implementation, you can do better than $O(n \log n)$. Instead of successively inserting each node in the heap based queue, you create an array, and "heapify" it. "Heapify" is a bulk operation for converting a list of numbers into a heap, in $O(n)$, or rather $\Theta(n)$ (see here or here). After that, there will be only one/two extract-min operations (one or two depending on whether the source is originally in the queue or not) in $O(\log n)$. So overall, $\Theta(n)$.

For the other implementation, you can do it in $\Theta(\Delta \log \Delta)$, where $\Delta$ is the degree of the source $u$.


What is the difference between a Neural Network, a Deep Learning System and a Deep Belief Network?

Artificial neural networks is a class of algorithms that include a lot of different kinds of algorithms based on graphs, so I won't detail here beyond what you asked because there's too much to say, since there are so many kinds of ANNs.

The first kind of artificial neural networks, the famous McCulloch-Pitts neurons, were linear, meaning that they could only solve linear decision problems (ie, datasets that could be linearly separable by drawing a line). Over time, this linear neural network model became known as the Perceptron or Adaline (depending on how you compute weights update).

Linear neural networks are just composed of a bipartite graph, where the left side nodes are the inputs and the right side nodes the output. Only the weights of the edges between these nodes are learnt (the nodes activation threshold can also be adjusted but this is rarely done).

A big step was taken when shallow neural networks were invented: instead of having only a bipartite graph, we use a 3partite graph: the input "layer", the output "layer", and one "hidden layer" between them. Thank's to the hidden layer, the network can now take non-linear decisions, and solve problems such as the canonical XOR.

Note that the "shallow" term was coined retrospectively when deep neural network (also called n-layers neural networks) were invented. This is to oppose neural networks with only one hidden layer, with deep neural networks with n hidden layers. As you can guess, using more hidden layers allow to decide on more complex datasets since there are more layers to modulate the decision (ie, in other words you're increasing the dimensionality of your decision boundary, which can lead to overfitting).

You may ask: why did no-one try to use multi-layered (deep) neural networks before? In fact, they did, as early as 1975 by Fukushima with the Cognitron and Neocognitron (which is in fact a convolutional neural network, but that's another story). However, the issue was that noone knew how to efficiently learn such networks, the big issue being the regularization. Hinton's AutoEncoders opened the way, and later the Rectified Linear Units of LeCun fixed the issue for good.

What about Deep Beliefs Networks (DBN)? They are just multi-layered semi-restricted Boltzmann machines. So they are a kind of deep neural network, but with a different basic network pattern (ie: the layer, this is the pattern that is repeated): Boltzmann machines are different from other networks in that they are generative, meaning that they are usually used to learn from your data to reproduce it ("generate" it), while usual deep neural networks are used to separate your data (by drawing a "decision boundary").

In other words, DNN are great to classify/predict a value from your dataset, while DBN are great to "repair" a corrupted data (when I say repair, it's not only from corrupted data, it can also be on a perfectly fine data that you just want to fix a little to be more stereotypical as to more easily recognize with another neural network, such as hand-written digits).

In fact, to neatly summarize, you can say that AutoEncoders are a simpler form of Deep Belief Network. Here is an example of a DBN trained to recognize faces but NOT numbers, the numbers are automatically faded away (this is the "fixing" effect of DBN):

So in the end, DBN and DNN are not opposite: they are complementary. For example, you can imagine a system to recognize hand-written characters that will first feed a character's image to a DBN to make it more stereotypical and then feed the stereotyped image to a DNN that will then output which character the image represents.

A last note: Deep Belief Nets are very close to Deep Boltzmann Machines: Deep Boltzmann Machines use layers of Boltzmann Machines (which are bidirectional neural networks, also called recurrent neural networks), while Deep Belief Nets use semi-restricted Boltzmann Machines (semi-restricted means that they are changed to unidirectional, thus it allows to use backpropagation to learn the network which is way more efficient than learning a reccurent network). Both networks are used for the same purpose (regenerating the dataset), but the computational cost is different (Deep Boltzmann Machines are significantly more costly to learn because of its recurrent nature: it is harder to "stabilize" the weights).

Bonus: about Convolutional Neural Networks (CNN), you will find a lot of contradictory and confusing claims, and usually you'll find that they are just deep neural networks. However, it seems the consensus is to use the original definition of Fukushima's Neocognitron: a CNN is a DNN that is forced to extract different features at different hierarchical levels by imposing a convolution before the activation (which a DNN can naturally do, but forcing it by setting a different convolution/activation function on different layers of the network may yield better result, at least that's the bet of CNN):

And finally, for a more rigorous timeline of Artificial Intelligence, see here.


Saying that CF grammars are properly contained in CS grammars is not quite
correct, at least according to some authors (Hopcroft-Ullman
1979, page 223). Their reason is that the CS languages cannot contain the empty
word $\epsilon$, at least according to a strict definition of what a
CS grammar is: the right-hand side must be at least as long as the
left-hand side. Other definitions of CS grammars, such as given in
wikipedia, do allow the rule $S\to\epsilon$, provided $S$ never
appears in a right-hand side. The purpose is to allow CS languages to
contain the empty word, so that they define the same family of
languages as the linear bounded automata (LBA). And it also makes CF languages a subset of CS languages.

Context-free (CF) languages can contain the empty word.

Thus, for an author belonging to the strict school (no $\epsilon$ in
CS languages), only $\epsilon$-free CF languages are contained in the
CS languages.

From what I read in your question, my understanding is that the
authors of your book belong to the strict school. So they will not
consider a CF language as CS, unless they first remove the empty word,
which does not change their CF character as shown in the answer by
D.W. that indicates how to obtain the CF grammar $G'$ from the CF
grammar $G$.

Apparently the author is analyzing the intersection of two CF grammar,
and wants to use the fact that (for him) $\epsilon$-free CF languages
are contained in the CS languages. So he considers separately the case
when the intersection contains $\epsilon$, and the case when it does
not contains it. If it does no contain it, he can remove it from the
two languages, and then consider them CS languages, for whatever he is
doing.

That is my explanation of what you are reading. Of course, a larger piece of context would help ascertain that view. Or even better, the definition of CS language they give.


Does the pigeonhole principle rule out the possibility of losslessly simulating a universe the size of our own?

No, the pigeonhole principle doesn't immediately imply that.  It might be true, but you'd need some additional reasoning to prove it.

For instance, you seem to be assuming that the way the simulation works is by separately simulating each simulated particle using one or more real particles, and that a single real particle cannot simulate more than one simulated particle. It's not obvious that either of these need to be true.  For instance, perhaps you can simulate K simulated particles using L real particles, using a complex algorithm that simulates them jointly without any clear mapping from simulated particles to real particles.  It's also not clear why we'd need to have $K \le L$; perhaps there is some algorithm where $L=K/2$ (say).  Some additional reasoning would be needed to rule out these possibilities -- the pigeonhole principle alone isn't enough.

It does seem like a plausible-ish sort of conclusion, under reasonable assumptions about your model of computation.  But I don't think it's that easy to prove.


Big-O Solving Recurrence Relation by iteration with fractions

We can rewrite your recursion as
$$
B(n) = B(n-4) + \Theta\left(\frac{1}{n}\right).
$$
It follows that
$$
\begin{align*}
B(n) &= \Theta\left(\frac{1}{n} + \frac{1}{n-4} + \frac{1}{n-8} + \cdots\right) \\ &=
\Theta\left(\frac{1}{n/4} + \frac{1}{n/4-1} + \frac{1}{n/4-2} + \cdots \right) \\ &=
\Theta(\log (n/4)) = \Theta(\log n),
\end{align*}
$$
using the formula for the sum of a harmonic series.


Use tree in-order traversal to determine whether a BST or Heap

None of them can be a BST. An in-order traversal of a BST visits the vertices in non-decreasing order of their keys (this is easy to prove by induction).

To determine if they are heaps, notice that by the number of elements in the list you already know the topology of the tree (heaps are completely binary trees up to the one-to-last level, and all the leaves on the last level are packed on the left side). Then the exercise boils down to writing down the given keys in the same order of the traversal and checking if the heap property holds.

In the specific example the first sequence cannot be a in-order traversal of a heap since the resulting tree would have a path with keys $23, 1, 53$ (in increasing order of depth).
The same argument applies to the second sequence for a path with keys $71, 32, 49$.


There can be many reasons, but one example would be fairness. Suppose you have a modified version of ALOHA where one priority user has transmission probability set to 1 and all others to 0. Assuming the priority user always has a message to send, this scheme has a throughput of 1. However, this is an awful scheme if you care about any of the other users, because they are going to experience infinite delay.
This is why researchers often prefer working with network utility functions as performance metrics to account for the welfare of the network instead of just overall throughput.


The random assignment algorithm can be derandomized (made deterministic) using the method of conditional expectations.

Let the 3SAT instance consist of clauses $C_1,\ldots,C_m$. During the algorithm we will assign values to variables. The score of a clause $C$ is defined as follows:

If $C$ is satisfied then its score is 1.
If $C$ is not satisfied and has $k$ unassigned literals then its score is $1-2^{-k}$.

Initially the score of each clause is $1-2^{-3} = 7/8$, and so the total score is $(7/8) m$. We now assign values to the variables $x_1,\ldots,x_n$ in order. Suppose that we have assigned values to variables $x_1,\ldots,x_{i-1}$, and the current total score is $S = S(C_1)+\cdots+S(C_m)$. Let $S_0,S_1$ the total score if we assign the values $0,1$ (respectively) to $x_i$. I claim that $S_0(C)+S_1(C) = 2S(C)$ for any clause $C$, and so $S_0 + S_1 = 2S$. Indeed:

If $C$ is satisfied (only given $x_1,\ldots,x_{i-1}$) or doesn't contain $x_i$ then $S_0(C) + S_1(C) = 2S(C)$.
Suppose that $C$ contains $k$ unassigned literals, including $x_i$. Then $S(C) = 1-2^{-k}$, $S_0(C) = 1-2^{-(k-1)}$, and $S_1(C) = 1$. Therefore
$$ S_0(C) + S_1(C) = [1 - 2 \cdot 2^{-k}] + 1 = 2(1 - 2^{-k}) = 2S(C). $$
A similar argument works when $C$ contains $\bar{x}_i$.

Since $S_0 + S_1 = 2S$, either $S_0 \geq S$ or $S_1 \geq S$ (possibly both). Therefore there is some assignment to $S$ such that after the assignment, the new score is at least $S$.

The initial score is $(7/8)m$ and the algorithm ensures that the score never decreases. At the end, the score of a clause $C$ is 1 if it is satisfied and $1-2^{-0}=0$ otherwise. Thus the final assignment satisfies at least $(7/8)m$ clauses.

Given that there is a deterministic algorithm, why are we interested in the randomized one? There are several reasons:

The randomized algorithm is much simpler.
The randomized algorithm is potentially faster.
The randomized algorithm can be converted to a deterministic one using the method of conditional expectations; we can think of it as a recipe for constructing a deterministic algorithm.

More generally, it is conjectured that every randomized polytime algorithm for a decision problem can be derandomized (this is the $\mathsf{P}=\mathsf{BPP}$ conjecture). Randomized algorithms will still be interesting for all the reasons enumerated above.


Asymptotic Properties of Functions in Complexity Analysis

It is safe to assume that $f$ is everywhere positive, hence, asymptotically positive. You can't use negative time or space.

It is not safe to assume that $f$ is asymptotically monotonically increasing, since this excludes constant functions, i.e., those which are $\Theta(1)$.

It isn't even safe to assume that $f$ is asymptotically monotonically non-decreasing; this precludes functions that oscillate. A good question might be "do any useful algorithms have asymptotically oscillating time or space complexities," but certainly you could create an algorithm that did.

I suppose a more rigorous answer would ask what your definition of "asymptotically monotonically increasing" means. If it means that it's $\Theta(g(n))$ where $g(n)$ is monotonically increasing for positive $n$, then the answer would be yes, by definition.


Proving that English is not a regular language

It is not easy to prove the complexities of natural languages. See Complexity of natural languages for some hint that English language is not regular.

In fact in Evidence Against the Context-Freeness of Natural Language,
Stuart M. Shieber shows that many natural languages are not even context-free.

However, I only know about Dutch and a dialect of Swiss German, for which proof of non context-freeness exists. And the proofs are quite old, the results about them were proved in 1980s.

For detail you can also refer - The Handbook of Computational Linguistics and Natural Language Processing
edited by Alexander Clark, Chris Fox, Shalom Lappin.


Bottleneck in Hoare Logic unable to arrive at my {P} from {Q}

You are doing it in the opposite order. You are starting with the postcondition
{i<=n, p = fib(i-1), c = fib(i)} and then computing the precondition relative to the first assignment. You should instead use the last assignment, and go backwards:

{Q} = {n>0}
{P3 = P2[i\1]} = {1<=n, 0 = fib(1-1), 1 = fib(1)}
C1 = i := 1;
{P2 = P1[c\1]} = {i<=n, 0 = fib(i-1), 1 = fib(i)}
C2 = c := 1;
{P1 = P[p\0]} = {i<=n, 0 = fib(i-1), c = fib(i)}
C3 = p := 0;
{P} = {i<=n, p = fib(i-1), c = fib(i)}

The steps above were computed bottom-up: you should read it in the same way.

It is then simple to check that Q and P3 are equivalent (assuming integer variables).


The flaw is that $R_\Gamma$ includes not just the natural number $10$, but any natural number which gives rise to the same partial recursive function. It will be infinite, and not recursively enumerable.

In general, for any partial recursive function $f$ you can think of, there will be many Godel numbers which describe it. In other words, many partial recursive function descriptions result in the same actual function. If you are more familiar with Turing machines, there will always be many different Turing machines which compute the same abstract function or language.

In summary: $\Gamma$ is any set of functions. However, $R_\Gamma$ is the set of natural numbers which encode that function. In your case, for $\Gamma = \{\phi_{10}\}$, $R_\Gamma$ is the set of natural numbers which encode the same function as $10$, and this set is not recursively enumerable.


How are matchings a lower bound for an approximate vertex cover?

Let $M$ be a maximal matching, that is, $M$ is a matching which is not contained in a larger matching. Note that $M$ need not be a maximum matching, which is a matching of maximal size.
If $M$ contains $m$ edges, then:

Any vertex cover contains at least $m$ vertices. This is because any vertex covers at most one edge of the matching.

There exists a vertex cover containing $2m$ vertices, namely, all vertices of the matching.  Indeed, if the vertices of the matching $M$ do not form a vertex cover, then there is some edge $e$ which is not covered by the vertices of $M$, and so $M$ is contained in the larger matching $M \cup \{e\}$, contradicting the definition of $M$.


Simplifying the boolean expression xy + (!x)z + yz with boolean algebra?

$$
xy + \bar{x} z + yz =
xy + \bar{x} z + (x+\bar{x})yz =
xy + \bar{x} z + xyz + \bar{x}yz =
xy(1 + z) + \bar{x} z(1 + y) = xy + \bar{x}z.
$$


Best data structure for queries about subsets?

There is a popular algorithm in bioinformatics for solving this exact problem. I believe it is known as the multi-set membership testing problem (MSMT).

BigSI

The idea in BigSI is that you represent each of the $N$ inserted sets as a bloom filter of length $m$ with $k$ hashes. Let $Q$ be our $m\times N$ table, where the columns represent each of the $N$ bloom filters for each of our $N$ sets $\{X_1, ... , X_N\}$.

Now we wish to query $Q$ for an input set $S$. Let $A=\{h_i(s) \;\;\forall i\in[k],s\in S\}$ be all of the hash values for the input set. We have the following condition
$$S\subseteq X_i \iff Q[r][i] = 1 \;\;\forall r\in A$$ It remains to find columns such that the right hand side holds true. To do this, we create a subset of the rows  $Q'=\{row_i(Q) \; | i \in A\}$ . Now our condition is that
$$S\subseteq X_i \iff Q'[r][i] = 1 \;\;\forall r\in [|A|]$$
i.e. any columns with all $1$s in $Q'$ is a superset of $S$. We can find such columns $C$ by performing
$$ R = \bigwedge_{r\in[|A|]}Q'[r]$$
$$ C = \{i \;\;| \;\; R[i] = 1\}$$
If $C\neq \emptyset$, then $S$ must have been a subset of one of the original $N$ sets. Of course this algorithm is also able to tell you which of the original sets $S$ is a subset of. Since your question doesn't need that information, there may be some minor optimizations.

Here is a figure from the BigSI publication, where the input sets are FASTQ files which are broken down into $k$-mers. Part (a) represents the 5 input sets, each of cardinality 2. Figure (b) shows the resulting $Q$ table and the $\texttt{AND}$ operation used to find the superset inputs. Figure (c) is a naive alternative, where each row represents a possible element from one of the input sets, however this table would have to grow vertically as well as horizontally for each input set, as we may see new elements.


If I draw the ER diagram by choosing telephone as a composite attribute having component attributes: telephone_number and location. In this case the DB Table for Employee will have 2 more columns telephone_number and telephone_location. This will lead to repetition which can lead to inconsistency.

Suppose, 2 different Employees (with id 1 and 2 respectively) share

telephone(111111, london) and
telephone(222222, paris)

Employee(id, name, street, city, telephone_number, telephone_location)

(1, xyz, abc, pqr, 111111, london)
(1, xyz, abc, pqr, 222222, paris)
(2, qwe, der, vfr, 111111, london)
(2, qwe, der, vfr, 222222, paris)

In above instance of table, not only the information is repeated but it creates a dependency telephone_number -> telephone_location which can lead to inconsistency , say if telephone_location of 111111 is changed from london to austria then, due to dependency you need to change telephone_location  value in (2, qwe, der, vfr, 111111, london) also. If forgotten then it will lead to inconsistency.

We are going to treat the telephone as an entity... In this case there will be a relationship entity which will translate to a independent DB Table (emp_telephone) having 2 columns Employee_id  and telephone_number. Therefore, the table instances will look like:

Employee(id, name, street, city)
(1, xyz, abc, pqr)
(2, qwe, der, vfr)

telephone(telephone_number, telephone_location)
(111111, london)
(222222, paris)

emp_telephone(Employee_id, telephone_number)
(1, 111111)
(1, 222222)
(2, 111111)
(2, 222222)

So, in above table instances no information is repeated and individual attribute/column value in table Employee and telephone can change independently yet linked via relationship emp_telephone.

Lastly, if telephone is kept as multi-valued attribute then it will lead to creation of a table similar to emp_telephone(Employee_id, telephone_number) in which each value of multi-valued attribute telephone along with primary-key of Employee will be kept.

That is:

Employee(id, name, street, city, telephone)
(1, xyz, abc, pqr, 111111/222222) //<-- note telephone is multi-valued
(2, qwe, der, vfr, 111111/222222) //<-- note telephone is multi-valued

will translate to

Employee(id, name, street, city)
(1, xyz, abc, pqr)
(2, qwe, der, vfr)

emp_telephone(Employee_id, telephone_number)
(1, 111111)
(1, 222222)
(2, 111111)
(2, 222222)

So, from above it seems that the conclusion is, if an entity has a composite attribute which can be shared then such attribute should be kept as separate entity.


DFA for language of all strings avoiding 'aa'

For an alphabet of $\{a, b, c\}$ constructing a DFA that accepts all strings not containing the substring 'aa' tells you several things about the number of states you need. Firstly, and this is true for any DFA, you need at least one accepting state. Since your DFA is meant to filter out some strings, it requires a 'trap' or 'dead' state, a state that may never reach an accepting state once reached. Now clearly the strings 'a', 'b', 'c', and '' (empty string) do not contain the substring 'aa', therefore we know our initial state must also be an accepting state, which eliminates the next obvious choice for a new state.

So you know you need at least two states in your DFA, one trap state and one accepting state (which is also your initial state). Now you may also know that to construct a DFA that accepts the string 'aa' would require two states at least, so this gives a good guess that one additional state is required before transitioning to the trap state. So now there are three states to work with, if more are required they should come up as you construct your DFA from there.


Is there a name for algorithms which detect nearly-similar structures?

The search terms you're probably looking for are "similarity measure", "dissimilarity", "distance function", or "metric"... applied to trees.

One approach to your probem is to invent a similarity measure or distance function/metric that can be applied directly to tree.  There are some references on that at https://stackoverflow.com/q/21897879/781723.  You can also easily envision some recursive algorithms for doing that.  For instance, if a tree $T$ has children $T_1,T_2$ (i.e., the left and right subtrees of $T$), you could define

$$d(T,T') = d(T_1,T'_1) + d(T_2,T'_2),$$

with some way to bottom out the recursion at leaves (e.g., if leaves are strings, then use edit distance at the leaves).  You could also combine the distances of the child subtrees in some other way, e.g.,

$$d(T,T') = \sqrt{d(T_1,T'_1)^2 + d(T_2,T'_2)^2}$$

or using any other norm.

Another approach is to identify a set of features that capture aspects of the trees that are important to you.  Then, each tree can be mapped to a feature vector, and you can measure similarity between two trees by computing the similarity of the two feature vectors.  There are many distance metrics one can use on feature vectors (e.g., L1 norm, L2 norm, etc.)

In some cases, there are sophisticated techniques that can be used to speed up the feature-vector-based approach.  See https://en.wikipedia.org/wiki/Tree_kernel.

Finally, you could also look at techniques like shingling or minhash and try modifying them to apply to trees instead of strings/sets.


Intersection between regular language and context-free language

Yes, there does.

The key is to represent your CFL as a pushdown automaton, and the regular language as a DFA. Then compute the product automaton of the CFL's states and the DFA's states, keeping the stack operations from the CFL.

In essence, what you're doing is running your pushdown machine, and keeping track of what state you would be in in the DFA if you were running it in parallel. Then, when you reach the end, you only accept if both machines would accept.


how does cpu read 32 bit word from memory

Address Space and Word Size are indeed two different things. If my processor has an $n$ bit address space, then it can address $2^n$ addresses. Note that this is merely the number of addresses and is not $2^n$ GB.

The word size of a memory refers to the size of the smallest addressable unit of the memory. In other words if my processor has an $n$ bit address space and a word-size of $b$ bytes, then my processor can address $2^n$ locations each of which are $b$ bytes long.


How to prove a side effect in a function

If the function has two outputs, a standard way to represent this is as a function $f: A \to (B \times C)$, i.e., $f$ outputs a pair of an AST and a symbol table.

If the function updates an existing symbol table, you could represent this as a function $f : (A \times C) \to (B \times C)$.  It takes as an input a pair of a string and a symbol table, and outputs a pair of an AST and an updated symbol table.

You could also read about monads, which are a way to structure and reason about side effects in a functional programming language.  They are notoriously challenging to understand.

You don't prove a side effect.  You can prove a fact about the possible side effects, but you need to state what you are claiming; a side effect isn't something that can be proven or not.  Similarly, you don't prove a function.  You can prove the correctness of a function, if you specify what correctness means for that particular function, but you don't prove the function.


When showing that something is decidable, we don't usually invoke the concept of Turing machines. Rather, we use the Church–Turing thesis that states that informally described algorithms are realizable by Turing machines. Even when describing Turing machines, there is no need to describe subroutines—that's a programming concept that you are misusing here. Finally, there is absolutely no need to add consistency checks to your code! This code isn't going to be compiled. You can assume that it is bug-free. That's why we only give an informal description, in which these messy details are missing.

Another mistake you make in describing your program is the input $W$. This input is constant, and so there is no need to include it. Also, you haven't explained how you represent $W$: the set of all strings containing $111$ is infinite.

Let me rephrase your algorithm informally. The algorithm gets as input a regular expression $r$, which it then converts to an equivalent DFA (there is no need to explicitly go through the intermediary NFA; we already know that regular expressions can be converted to equivalent DFAs). Then it goes over all strings containing $111$ in lexicographic order, and if the DFA accepts any of them, it outputs Yes.

Do you see the problem with your algorithm? It never outputs No. When the answer is No, it never halts. So you haven't shown that the problem is decidable, only that it is semidecidable (i.e. recursively enumerable).

Let me offer a different direction. Suppose I gave you a regular expression, and asked you whether the language it describes has a word containing $111$. How would you answer that? Can your answer be implemented mechanically? If so, you've found an algorithm and shown that the problem is decidable.


Can a functional language be homoiconic?

The definition implies not only that programs are represented by a "primitive" datatype, but presumably also that it is possible to inspect the elements of this type, i.e., one can actually get at the code (otherwise I can just declare a primitive abstract type code and never let you look at it).

In general, the construct you are looking for is known as quote. It takes a piece of code (in $\lambda$-calculus or anywhere else) and returns its representation, either as an abstract syntax tree, a string, or just an integer (because integers can encode syntax trees). Of course, in the case of $\lambda$-calculus such trees, strings or numbers would be encoded in the usual way that we encode datastructures in $\lambda$-calculus.

It is known that having quote in general increases the expressive power of the language. For example, in $\lambda$-calculus we cannot implement the statement "all functions are continuous" but we can if we also have quote at our disposal (this is the essence of Kreisel-Lacombe-Shoenfield-Tseitin theorem).

The opposite of quote is eval, which many languages have. However, eval does not add to the expressive power of a language because it can be implemented within the language, assuming the language is general enough (eval is essentially an interpreter for the language).

It is worth mentioning that quote is an abstract way of making a programming language be a lot more like the Turing machine model (TM) of computation. In the TM model a piece of code is a Turing machine, and it is represented on the tape as a sequence of symbols, which is the only datatype that Turing machines know about.

Note: it is common knowledge that "all models of computation are equivalent". What this means is that they compute the same class of functions from numbers to numbers $\mathtt{nat} \to \mathtt{nat}$, but they are not equivalent when it comes to higher-order functions such as $(\mathtt{nat} \to \mathtt{nat}) \to \mathtt{nat}$.


Suppose that your team contains $n$ people. Each round of discussions ("session") corresponds to a matching in the complete graph $K_n$. Therefore you want to partition into as few matchings as possible. The answer depends on the parity of $n$.

Case 1: $n$ is even. In this case, $K_n$ contains $\binom{n}{2}$ edges, and a matching contains at most $n/2$ edges. Hence we can hope for a partition of $K_n$ into $n-1$ perfect matchings. This is a standard problem, known as 1-factorization of the complete graph. Here is one solution:
$$
(0,n-1),(1,n-2),(2,n-3),(3,n-4),\ldots,(n/2-1,n/2) \\
(1,n-1),(2,0),(3,n-2),(4,n-3),\ldots,(n/2,n/2+1) \\
(2,n-1),(3,1),(4,0),(5,n-2),\ldots,(n/2+1,n/2+2) \\
\ldots
$$
Explanation: the $i$'th row consists of $(i,n-1)$ together with $(j+i,n-1-j+i \bmod n-1)$ for $1 \leq j \leq n/2-1$. For example, when $n = 6$ you get:
$$
(0,5),(1,4),(2,3) \\
(1,5),(2,0),(3,4) \\
(2,5),(3,1),(4,0) \\
(3,5),(4,2),(0,1) \\
(4,5),(0,3),(1,2)
$$

Case 2: $n$ is odd. In this case, $K_n$ still contains $\binom{n}{2}$ edges, but now each matching contains at most $(n-1)/2$ edges. Hence we can hope for a partition of $K_n$ into $n$ almost-perfect matchings. We can take the solution above for $n+1$, and just ignore the match of vertex $n$. This gives the following solution:
$$
(1,n-1),(2,n-2),(3,n-3),\ldots,((n-1)/2,(n+1)/2) \\
(2,0),(3,n-1),(4,n-2),\ldots,((n+1)/2,(n+3)/2) \\
(3,1),(4,0),(5,n-1),\ldots,((n+3)/2,(n+5)/2) \\
\ldots
$$
Explanation: the $i$th row consists of $(j+i,n-j+i \bmod n)$ for $1 \leq j \leq (n-1)/2$. For example, when $n = 7$ you get:
$$
(1,6),(2,5),(3,4) \\
(2,0),(3,6),(4,5) \\
(3,1),(4,0),(5,6) \\
(4,2),(5,1),(6,0) \\
(5,3),(6,2),(0,1) \\
(6,4),(0,3),(1,2) \\
(0,5),(1,4),(2,3)
$$


Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$?

If you could prove that implication, then lower bounds such as $NEXP \neq BPP$ would hold unconditionally. (proof: $NEXP = BPP$ implies $NEXP = \Sigma_2 P$ and $NP \subset BPP$, and if the latter also implies $NP$ is in $coRP$ then UNSAT is in $NP$. So $NEXP = \Sigma_2 P = NP$ which is false by the nondeterministic time hierarchy). Good luck!


What happens when there are two same IP addresses?

ISPs asign one IPv4 address to a customer, and your "WiFi box" acts as a router/NAT box/ DHCP server doling out addresses from a private range internally. It is possible that the "outside" IPv4 address is itself in a private range, leaving your ISP through a mere handful  of IPv4 addresses via NAT (real one, your box really does PAT, port forwarding through one IPv4 address).


If the language of a TM is TMs which cannot self recognize, can the original TM?

You have to argue formally. Intuition can be helpful in pointing the way, but you need a formal argument in the end.

Hint: Suppose that $\langle N \rangle \notin L_s$. Then $N$ accepts $\langle N \rangle$, and so $\langle N \rangle \in L(N) \subseteq L_s$, a contradiction.


Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity

Here is the critical observation.  We can combine the two conditions, there must be at least one difference and there must be at least one similarity between $x$ and $y$ into the following one condition.

Let $x=x_1x_2\cdots x_m$ and $y=y_1y_2\cdots y_n$, where $x_1, x_2,\cdots, x_m,y_1, y_2,\cdots, y_n\in \Sigma$. Then $x\#y$ is a word in the language if and only if there exists an index $i$ such that

$x_i\not=y_i$ and $x_{i+1} =y_{i+1}$ or,
$x_i=y_i$ and we do not have $x_{i+1} =y_{i+1}$.

The precise meaning of "we do not have $x_{i+1} =y_{i+1}$" is either exactly one of $x_{i+1}$ and $y_{i+1}$ is defined or $x_{i+1}\not= y_{i+1}$.

The basic motivation of the idea above is that an PDA can only keep track of one unbounded counter. So we should compress two unbounded counters, the index of the similarity and the index of the difference into one unbounded counter.


For even $a$ and $b \ne 0$ and integral division
$$ \frac{a}{b} = \frac{2a}{2b} = 2 \cdot \frac{( a / 2 )}{b} $$
Similarly for the remainder
$$a = 2 \cdot \frac{a}{2} \space (mod \space b)$$
Effectively transforming your problem of division of number with n bits into division of a number with n-1 bits (half as big number).

The algorithm uses integral division in the floor(x\2) part and there you might lose 1 if x was odd. You're giving it back with the if x is odd: block to the remainder and since this might make your reminder the same size as y you need to check if that happened and change the values accordingly. (Notice that r > y can never happen and there could be just as fine if r == y:.)

You just do this n times where n is the number of bits of x.

Finally the algorithm is not $O(n^2)$ but rather $O(n)$ in the number of bits of x. That's assuming the floor(x/2) part does not call the divide function, because that would end in infinite loop (you would need e.g. compute a/2 to compute a/b which would in turn need again computation of a/2. This can be avoided by using a>>1 instead of a/2 which also authomatically floors the result).


Algorithm to minimize distance variance between 2D coordinates

So here is a rather simple approach to solve this problem. You know that there are $O(n^2)$ different distances that matter. You can characterize the solution of your problem by the smallest and the largest distance ($d_\min$,$d_\max$) between your matched points. This gives you a set of $O(n^4)$ candidates.

So suppose you want to test, if there exists a matching where all distances are between $d_\min$ and $d_\max$. In other words, you want to solve the decision problem. This can be modeled as a perfect matching in a bipartite graph. Let $(u_1,\ldots,u_n)$ be the points in the first list and $(v_1,\ldots,v_n)$ be the points in the second list. Consider the bipartite graph that has an edge $(u_i,v_j)$ if and only if the distance between $u_i$ and $v_j$ is contained inside $[d_\min,d_\max]$. If this graph has a perfect matching, then there is an point-to-point assignment for the given distance constraints. Such a test can be done by the Hopcroft-Kahn algorithm, which needs $O(n^{2.5})$. A slightly faster solution can be achieved with fast matrix multiplication.

So you are left with trying out the candidates. This gives a $O(n^{6.5})$ algorithm. You can save a bit of running time by trying out all $d_\min$ values but then do a binary search for each $d_\max$ value. Now you have to solve only $O(n^2 \log n)$ decision problems (you also have to sort all distances, which is dominated by the overall running time) and hence the running time is only $O(n^{4.5}\log n)$.


When doing amortized analysis with a potential function, the potential function appears out of nowhere.  One way to come up with a potential function is to try picking some function, and then see if the calculation goes through.  If that doesn't work, one can try adjusting the potential function to make the calculation go through.  Sometimes we might let $\Phi(\cdot)$ be a placeholder, see what properties it needs to have to make the proof go through, and then try to come up with a function that has those properties.

In other words -- there is not necessarily any systematic way to find a potential function that works.  You might need to use trial-and-error, or a lucky guess, or other methods.


Quickly locating nearest rectangle from a point

I expect the best option is to use some kind of spatial index. Here's a first suggestion, but I'm sure there are better solutions.

Create a quad tree with a maximum bucket capacity of $m$.
For each new rectangle, traverse the tree, and store a pointer to the rectangle at each bucket that intersects the rectangle.

Now to find the nearest rectangle for a point $p$:

Find the bucket $B$ the point falls in.
Find the distance $d$ to the nearest rectangle $B$.
Check all surrounding buckets for rectangles that might be closer than $d$.

The last step might still be expensive if you're unlucky, but you can effectively eliminate all buckets that are itself further from $p$ than $d$.


Would it be feasible to use a breadth first search algorithm for finding a solution to the 3x3x3 rubiks cube?

For given Rubik's cube, the maximal number of moves required to solve any permutation of valid configuration is 26 in quarter-turn metric, but only 20 as half-turn metric, it means that if you have the most distant configuration amongst all possibilities the height of the tree is 20 levels, using BFS you have to store the previous level, using only quarter-turn metric the number is 26, but using unconstrained BFS the algorithm will terminate after 20 steps. It would also be nice to keep the path from current configuration to solved state if you wish to use it later. With majority of solutions at 18 moves as high as about $29*10^{18}$, the straightforward application of BFS is not really feasible for memory usage.

The worst case time required to solve puzzle from any configuration will traverse all solutions space, this is not feasible either. To put it in numbers, the empirical result to find the worst case number of moves took 35 cpu years, checking only solutions that require less than 20 moves, not aiming at the optimal state, reducing problem by symmetry and splitting to 55,882,296 sets that require checking shrinking actual number of states even further. These observations are not available using vanilla BFS. So the time usage is also not feasible.

As for the comments, using any algorithmic system of solving cube by human will not yield optimal solution, but will span at about 40 to 80 moves, but would be really straightforward to implement and both time and space would be negligible.

The Rubik's Pie (Domino) from the other answer is significantly easier, not only by removal of one layer, but some quarter turns are not possible to perform, but still it requires 18 moves in Half-turn metric and 19 in Quarter-turn metric, with solution space with only $406 425 600$ possible positions which is small when compared with $43 252 003 274 489 856 000$ ($10^{11}$ times smaller).


MST with degree constraints on some node

Here's an algorithm that just reduces to MST; no need to modify Prim's or some other algorithm. The idea is simple: remove $v$, compute the MSTs of the resulting components of the graph, and then stitch them together with $v$. The interesting case is when removing $v$ doesn't disconnect the graph.

I'll assume the input graph $G$ is connected, although it would not be difficult to generalize this idea to computing a minimum spanning forest. Also, obviously the degree of $v$ needs to be at least 2.

Algorithm

Start by removing $v$ and all incident edges; call this $G'$. Now compute the number of connected components in $G'$. This can be done with DFS or something similar.

More than 2 components:
If $G'$ has more than 2 connected components, no solution is possible.

Exactly 2 components: If $G'$ has exactly two connected components, then we can construct a solution by using $v$ as the "bridge" between the two components: just connect the MSTs of the components with the cheapest edges through $v$.

Exactly 1 component: If $G'$ has exactly one component, we can compute $T' = \text{MST}(G')$, and then we just need to stitch $v$ into $T'$ using two edges.

Find the cheapest edge incident on $v$ and add this to $T'$. Call this $T''$. Now we have a spanning tree, but not necessarily minimum.
Iterate over all other edges incident on $v$. For each of these, we will try to construct a MST where $d(v) = 2$. If we don't find one, then no solution is possible.

Consider some incident edge $(u,v)$ which is not the lightest edge on $v$.
Observe that if we added this edge to $T''$, it would create a cycle.
If $(u,v)$ is the heaviest edge on this cycle, then skip this edge, because no solution is possible using $(u,v)$.
Otherwise, we can take out the heaviest cycle edge and add $(u,v)$ instead. Now we have a spanning tree where $d(v) = 2$. If this spanning tree is minimum, we're done. (We can determine if a spanning tree is minimum just by computing any $\text{MST}(G)$ and comparing weights. This "reference" MST only needs to be computed once.)

It's not immediately obvious that this is within cost bounds, because for each of $O(|V|)$ edges incident on $v$, we have to compute the heaviest edge in the tree on the path between $v$ and some other vertex $u$. However, these "path queries" are well studied in the literature, and can be computed in $O(\log|V|)$ by preprocessing $T''$ into a balanced lookup structure. Some examples include binary lifting, Miller-Reif rake/compress tree contraction, and Sleator-Tarjan link/cut trees. The link/cut trees are actually far more general: they handle dynamic trees too! But here we only need to preprocess a static tree, i.e. $T''$.

Edit: My original idea was to do the following, which doesn't work (thank you @VladislavBezhentsev for pointing this out in the comments!). It doesn't work because, while we know that the cheaper of $e_1$ and $e_2$ is certainly in the MST (by the cut property), it's not necessarily true that the heavier of the two edges is!

  (Incorrect idea): Find the two cheapest edges $e_1$ and $e_2$ that are incident on $v$. Add $e_1$ and $e_2$ to $T'$: this creates a cycle. If the largest edge on this cycle is either $e_1$ or $e_2$, no solution is possible. Otherwise, remove the largest edge on the cycle.


Why does a Turing machine recognise exactly one language?

The language recognized by a Turing machine is, by definition, the set of strings it accepts. When an input is given to the machine, it is either accepted or not. Any particular input to that machine is either always accepted (in the language) or always not accepted (not in the language). So there's no mechanism by which a single Turing machine even could accept more than one langauge.


I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a formula in relational calculus to an SQL query ...

Why do people persist in this confusion? The semantics of SQL is different to Codd's Relational Model. Therefore no 'conversion' makes sense. Specifically:

Relations are sets vs SQL tables are multisets.
In Tuple Relational Calculus and Domain Relational Calculus, attributes are named, and that is the only way to access attributes vs SQL columns of an SQL table might or might not have names, might or might not have a unique name; can also be accessed by column position (under older SQL standards), and have an obtuse and incomplete algorithm for column positioning of query results.
For Relational Algebra, it gets messier: some versions (including in Codd 1972) access columns only positionally; some only by name.

The only formal conversion between any of these is given in Codd 1972 'Relational Completeness', where he uses conversion from TRC to Relational Algebra (not v.v.) to show the expressive completeness of (that version of) RA. (And actually, it's from his 'Alpha', which is an 'implementation' of TRC that was never implemented.)

  However, I cannot find any rules for such conversion and I would expect them to exist.

Please give some reference claiming they exist. The usual form of words is that SQL is "based upon" RA or TRC. That's not a claim of convertability, in either direction.

  I am specifically interested in how to systematically (automatically) convert predicates involving existential quantifiers.

Given some relation schema

S(SNO, SNAME, CITY, STATUS) with predicate 'Supplier identified by SNO is named SNAME, is located in CITY and has status STATUS',
a derived predicate 'exists STATUS s.t. Supplier identified by SNO is named SNAME, is located in CITY and has status STATUS'
is given by RA: pi(SNO, SNAME, CITY)(S).
That is, existentially quantifying an attribute is equivalent to projecting it away. "Projecting away" is also known as REMOVE or project ALL BUT.


Partitioning in time complexity of the sum

A Turing machine $T$ runs in polynomial time if there is a polynomial $p$ such that the running time of $T$ on an input of length $n$ bits is at most $p(n)$. The same definition works for other machine models such as the RAM machine.

Whether $O(M)$ is polynomial time or not depends on the way you encode the input. If the input is encoded in binary, then $O(M)$ isn't polynomial time, since the input could be of length as low as $O(\log M)$. If the input is encoded in unary (i.e., a number $x \geq 0$ is encoded as $1^x$) then $O(M)$ is polynomial time. It is part of the definition of the problem to specify the way the input is encoded.


Partitioning a set to the maximum number of subsets summing to zero

3-Partition reduces to this problem, so it's strongly $NP$-hard. Moreover, 4-Partition also reduces to it (and the blowup is linear), so assuming the exponential time hypothesis there's no $2^{o(n)}$ algorithm.

Using dynamic programming there's a $O^*(4^n)$ algorithm, it would be interesting if you could do $2^n$ or even $1.99^n$.


It will print 4 because sending by value will change the copy not the original variable which is x in your example.


Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$

This is from Hopcroft and Ullman's book,
Example 9.4, pg 220:

$$ S \rightarrow ACaB $$
$$ Ca \rightarrow aaC $$
$$ CB \rightarrow DB $$
$$ CB \rightarrow E $$
$$ aD \rightarrow Da $$
$$ AD \rightarrow AC $$
$$ aE \rightarrow Ea $$
$$ AE \rightarrow \epsilon $$

Update: in fact given grammar is unrestricted which can be modified as a context sensitive.

But if your ultimate goal is to prove that the given language is a CSL, then it is enough to create a linear bounded automaton - a TM whose computational ability is restricted to the portion of input. In other words, the head of the TM cannot move beyond the input area. LBA's and CSG's are equivalent.

You can just erase one input symbol at a time starting from the right, and each time you erase one symbol increase a counter by one (binary symbols 0 and 1) which are stored in place of erased symbols. When you erase all input symbols check if the counter is of the form 100...0. If yes then accept, otherwise reject). 100...0 means it is a power of 2.


Proof that Turing machines and computers have same power

Turing machines and Boolean circuits cannot really be compared, since Turing machines handle inputs of arbitrary length, whereas Boolean circuits only handle inputs of fixed length.

Furthermore, Turing machines and CPUs corresponds to two different computation models. Turing machines access their memory by moving a head across a tape. In contrast, a CPU accesses its memory via random access. The abstraction corresponding to CPUs is the random-access machine.

If we want to compare the power of Turing machines and circuits, we need to put them into equal footing. One way to do this is to consider a sequence of circuits $C_0,C_1,C_2,\ldots$, one per input length. Such a sequence computes a language in the natural way: an input $x$ belongs to the language if $C_{|x|}$ returns True when given $x$ as input. This circuit model is much more powerful than Turing machines – indeed, it can compute any language, whereas Turing machines can only compute decidable languages.

What went wrong? Let us consider your example, of circuits for parity. The circuits computing parity for different lengths of input are very similar to one another; they seem to be made from a "mold", a set of instructions which can be translated to a circuit of arbitrary length. In contrast, the circuit model considered in the preceding paragraph specifies no such relation between the different circuits. When we add this constraint – that the different circuits follow a "blueprint" – we do get a model equivalent to Turing machines. What exactly constitutes a blueprint is a bit technical (one option is to have the circuits generated by a Turing machine), but the intuitive idea should be clear.

Circuits also come up when trying to understand resource-bounded computation, such as the complexity class $\mathsf{P}$ of languages which can be decided in polynomial time. It is known that any such language can be translated to a "uniform" family of circuits of polynomial size. In this way, the fact that the language can be decided efficiently is reflected by the size of circuits that compute it.


Hard Drive Seek Time using FIFO, SSF, SCAN

@greybeard why he divided by 2
on average we will need to wait for half a rotation of the disk for the correct sector to come under the head. Thus, on average, the rotational latency is half the time it takes the disk to make a complete revolution.

do I need to multiply this by the number of tracks moved?
No. Because average rotational time is the time to move head from one sector to any other sector in same track. This movement is done by disk rotation.

In your question we will consider any sector in given track. So when track changes from 30 to 27, it takes 3 track movement and 1 average rotation so time 3*0.1+5

In general, total time = seek time + rotating latency

Seek time : time to change track

Edited

(3+102+19+76+39+106+31+54+56)*0.1 + number_of_time_movement_occured * rotational_latency
= 486 * 0.1 + 9 * 5
= 48.6 + 45
= 93.6


I'm not sure there is a well accepted definition of compiler. To some extent this is an informal concept, so you can't expect a mathematical definition like that of a derivative.

Judging from GCC documentation, the compiler proper converts (preprocessed) source code into object code. Several object codes are then linked together to an executable by the linker, but that doesn't form part of the compiler proper. The C/C++ preprocessor also doesn't form part of the compiler proper.

The compiler proper is further composed of two parts: a front end and a back end. The front end converts source code into intermediate code, and is language specific. The back end converts intermediate code into machine code, and is machine specific. GCC comes with several front ends and back ends, and this is why it is called a compiler collection.


Why doesn't descriptive complexity theory solve P = NP?

Note the difference between second-order logic, and existential second order logic. Full logic is much more powerful than existential logic.

Also, it's important not to underestimate the power of a least-fixed point operator. Linearly-ordered first order logic is likely far less powerful than the version with fixed-points.

In short, we know that vanilla first-order logic is weaker than vanilla second-order logic, but we don't know that linearly-ordered first order logic with a least-fixed point operator is weaker than the existential fragment of second order logic.


It is the other way around. We first model the system in a certain way, for instance we assume that there is a (or is no) global clock, or we assume that messages arrive or may fail, etc. Once we fix our assumptions, we can ask questions about the system we have characterized: does it allow computations of certain types or not?
For instance, if we assume all the nodes are identical and ask whether we can break symmetry, then the answer is no (in certain cases). If we assume there is no global clock, and ask whether the parties can synchronize, then probably the answer is no (it depends on what you mean by "synchronize"). However, can the system solve tasks without a global clock? Sure! there are plenty asynchronous algorithms that perform a large variety of tasks, like broadcasting, finding a leader, or computing a spanning tree.
So, communication via message-passing does not imply no global clock. These two are independent assumptions that characterize the system. Under these assumptions certain tasks are possible/fast and other might be impossible/slow.


Decide if a language has a word of a given size

There are two cases:

$L$ is empty. In this case, $L' = \emptyset$ is trivially decidable.
$L$ is non-empty. Let $m$ be the minimum length of a word in $L$. Then $L'$ consists of all words of length at least $m$, and is again trivially decidable (in constant time!).

As you can see, you never actually need an algorithm for $L$.

Similarly, the following language is always decidable:

$$L'' = \{w \in \Sigma^* \mid \text{ there exists a word $w' \in L$ such that $|w'| \geq |w|$}\}.$$

There are now three cases:

$L$ is empty. In this case, $L'' = \emptyset$ is trivially decidable.
$L$ is infinite. In this case, $L'' = \Sigma^*$ is again triviall decidable.
$L$ is finite. Let $M$ be the maximum length of a word in $L$. Then $L''$ consists of all words of length at most $M$, and is again trivially decidable (in constant time).

These are examples of non-constructive proofs, which you might not like. Instead of starting a discussion here, I refer you to this question.


Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$

$S \rightarrow$ $aSb$  |   $J$

$J \rightarrow aJbb$ | $ε$

This has only one derivation tree for a word in that language.


Finding the minimum number of calls in a tree

You can traverse the tree in postorder and compute for each node the number of rounds that the subtree below that node needs as follows:

If the node is a leaf, the subtree takes 0 rounds.
If the node is not a leaf, sort its children by the number of rounds their respective subtrees take, from longest to shortest. You will traverse them in this order. The number of rounds for the current node is $\max_i\{n_i +i\}$, where $n_i$ is the number of rounds the subtree of the $i$-th child (in sorted order) takes.

Regarding output: The best format depends on what you want to do with the data. Do you need information on which calls happen concurrently? Or do you want to actually implement the calls?
In the latter case, listing the processing order for each node seems like a reasonable format.
In the former case, your format is nice, but probably needs an additional traversal to be obtained.


What are the k characters which make the most complete words?

If you take each word as a set of characters, you're looking for sets of size k that contain the most words as subsets.  For a given word of j unique characters out of an alphabet of size N, you have (N-j) choose (k-j) possible supersets, ie all the sets of size k that have the original j characters plus any (k-j) others.

Some time ago I worked on an algorithm for a similar problem that might be modified for this case.  I'll try to sketch how it would work in this case.

Briefly, the solution is to walk all the "words" through their candidate supersets (a factorial number) in a fixed order, identify any runs of identical values that indicate a number of words that fit in the same superset, and to save the run that's longest.

This is essentially an n-way merge, looking for runs of identical values on the output.  I did this with a heap of iterators where I would pull the smallest value, count it, increment it (find the next superset in its range of possible supersets), and re-insert it into the heap.  This process provably visits every possible superset and counts the words that it covers.

What makes this possibly tractable is a pruning rule that skips candidates with sub-maximal runs.  What I realized while coding the above is that if my only interest is runs of length L or greater, then if I look L elements ahead I can see if the current run stops before L elements, and furthermore (with some careful reasoning) eliminate all intervening values from consideration and skip to whatever value is L elements ahead.

The problem I was solving originally was association-rule mining, which walks each set through its subsets rather than supersets, and this method worked well in that case.


What's the possibility of random guessing a youtube's video ID

Each YouTube id consists of 11 characters denoted by $v = [v_1, ··· ,
v_{11}]$.
  The first $10$ characters of a valid id contain any of the characters
  in $S = \{0 − 9,\_, −, A − Z, a − z\}$, i.e., $v_i ∈ S (i =
1, ··· , 10)$. The last (11-th) character $v_{11}$ only comes from $T =
\{0, 4, 8, A, E, I,M, Q, U, Y, c, g, k, o, s, w\}$, namely, $v_{11} \in T 1$.
  The size of video id space is, therefore, $64^{10}\cdot16$.

  We also observe that YouTube video ids are not generated in any sequence. Instead,
  YouTube picks an unused random id from this pool for each new
  video that is uploaded.

  Source: http://conferences.sigcomm.org/imc/2011/docs/p371.pdf

For instance, they show that YouTube video is randomly generated from the id
space and that the entire YouTube id space can be represented as $S = S^{10} × T$, where:

$S = \{0−9,\_, −, A−Z, a−z\}$
$T = \{0, 4, 8, A, E, I,M,Q, U, Y, c, g, k, o, s, w\}$.

Their estimation of the total number of youtube videos is $502\cdot10^6$.

Given these 2 information (video id space and estimation of the total number of videos) you can deduce the probability that, given an id of $11$ characters in $S^{10} × T$, it corresponds to the id of a valid video.


Is there a dual concept to "Turing Complete" in logic?

I'm not sure why you say "true" is ultimately undefinable, as there is a precise definition for what it means for a first order formula to be true.

What's unique in the case of computability, is that for any definition (as wild as your dreams) for a "computational model", you can finally associate it with a set of functions (the functions it can compute). Thus, you can naturally compare different models, and upon fixing one (based on some empirical justification such as "it is a good representation of computation in the real world") you can call any other model complete if it computes exactly the same set of functions.

However, how do you compare different logics? It seems there is no natural property you can attach to an arbitrary logic, and use it to compare it to other systems. You can perhaps, fix the logic, e.g. first order predicate logic, and ask about completeness of an axiomatic system. Suppose you work in ZFC, and believe it consists of the natural axioms that represent the world. Now, when given a different axiomatic system, you can ask whether they have the same theory, and call this system complete in the case the answer is yes. I think the difference from the computability case, is that for computability, there is a stronger consensus on what the "base model" should be. The reason for this consensus is that many independent models of computation were later shown to be equivalent, so this seems like a very strong empirical evidence for what our "base model" should be.


TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$

This is not true.

If $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ , then $c(x,z)\le c(x,y) + c(y,z)$

However it is true that, for $x,z \in V$ with $x \neq z$, you have $c(x,z) \le 100 d(x,z)$.
To see this let $P$ be a shortest path from $x$ to $z$. The proof is by induction on the number of edges $|P|$ of $P$.
If $|P|=1$ then $c(x,z) = d(x,z) \le 100 d(x,z)$.
If $|P| \ge 2$ then, let $y$ be the vertex immediately preceding $z$ in $P$.
By inductive hypothesis $c(x, y) \le 100 d(x,y)$ and you have
$$
c(x,z) \le c(x,y) + 100 c(y,z) \le  100 d(x,y) + 100 c(y,z) =100 d(x,z). \quad \square
$$
Consider a MST $M$ of $G$ and let $T$ be a Euler tour of $M$, starting from an arbitrary vertex.
Let $v_0, v_1, \dots, v_{n-1}$ be the vertices in $V$ in the order they appear for the first time in $T$ and let $v_n = v_0$. Consider the tour $T'$ that visits $v_0, v_1, \dots, v_n$ in this order.
For $i=0, \dots, n-1$ let $T_i$ be the portion of the tour between the first occurrence of $v_i$ in $T$ and the next occurrence of $v_{i+1}$ in $T$.
Given any graph $H$, let $c(H)$ be the sum of costs of the edges in $H$.
Let $T^*$ an optimal tour of $G$.
You have:
$$
\begin{align*}
c(T') &= \sum_{i=0}^{n-1} c(v_i, v_{i+1}) \le 100 \sum_{i=0}^{n-1} d(v_i, v_{i+1}) \le 100 \sum_{i=0}^{n-1} c(T_i) \\
&\le 100 c(T) \le 200 c(M) \le 200 c(T^*).
\end{align*}
$$


When $K = N$, the polynomial you are trying to compute is known as the permanent. The best algorithms for computing the permanent use $\tilde{O}(2^N)$ arithmetic operations, see Wikipedia. The VP≠VNP conjecture implies that the permanent cannot be computed using a polynomial number of operations.
For general $K$, your function is a known extension of the permanent. Ryser's algorithm, one of the $\tilde{O}(2^N)$ algorithms for the square case, extends to the rectangular case as well.


Determining if (infinite) binary language DFAs contain at least 1 prime?

It's a standard intro theory exercise that for any $d\ge 0$ there's a FA that accepts all and only those strings in $\{0, 1\}^*$ that are the binary representations of integer multiples of $d$. Thus, the answer to your second question is "yes".

For your third question, the answer is "no". Consider the regular language denoted by $1(10)^*0$. This language consists of those binary representations of
$$
\frac{10\cdot 4^n-4}{3}
$$
and clearly this sequence is too sparse to contain an arithmetic subsequence of any length greater than 2.


We say that $\alpha \Rightarrow^* \beta$ if $\beta$ can be derived from $\alpha$ in zero or more steps. (More fancily, $\Rightarrow^*$ is the reflexive-transitive closure of $\Rightarrow$.) In particular, it is always that case that $\alpha \Rightarrow^* \alpha$, for every $\alpha$, due to a derivation of zero steps.

In contrast, in your case it doesn't hold that $T \Rightarrow^+ T$. (This is derivation in one or more steps, or the transitive closure of $\Rightarrow$.)


Triple nested loop where outer and inner loop are dependent on n

In general, I am wondering if this approach of multiplying the iterations of each loop is a good approach to solving worst case running time and big-Theta estimates.

Basically, yes. But you don't really multiply: As explained here at length, you have nested sums. In your case,

$\qquad\displaystyle \sum_{i=1}^n \sum_{j=1}^{10} \sum_{k=n}^{n+5} 1$

(if we count the number of assignment operations) is easy to evaluate because the loops do not depend on each other. It looks like multiplication here, but if you get things like

  for i = 1 to n
      for j = 1 to i
          foo

that does not work anymore.

Note that worst-case considerations and asymptotics do not enter the picture here.


What if P implies Q is false when both P and Q are false?

This question is a soft question IMO, it assumes there's common ground about what "should be true" independent of definitions but it doesn't clarify what those assumptions are. If I were to break it down, I'd say it's looking for a particular bit of reasoning (e.g. a proof or an inference rule) to hold and then asking you to show that that reasoning would be invalid if we defined the semantics of implication differently. In essence it's asking if there exists a proof that, under this new model, would be invalid.

Consider $\neg (Q \vee \neg Q) \to \neg (Q \vee \neg Q)$ which is provable, and should be valid in all models (no matter what we assign to $Q$ that is). As a general rule of reasoning it should always hold that $P \to P$ no matter what. I posit this is sufficiently fundamental common ground of "what should be true". So if we find this reasoning invalid, we have our soft contradiction. We can construct instances of $P$ for which $P$ is certainly false as shown above. So despite the very reasonable proof of $\neg (Q \vee \neg Q) \to \neg (Q \vee \neg Q)$ that would actually be false under the model...in fact it's negation would be valid in the model!


Hamiltonian non intersecting path in plane

Hamiltonian path problem remains NP-complete in planar graphs [1], so your problem is also NP-complete since in a planar graph, two edges cannot intersect with each other.

[1] Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1976). The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4), 704-714.