How does a computer determine the data type of a byte?

Your suspicion is correct. The CPU doesn't care about the semantics of your data. Sometimes, though, it does make a difference. For example, some arithmetic operations produce different results when the arguments are semantically signed or unsigned. In that case you need to tell the CPU which interpretation you intended.

It is up to the programmer to make sense of her data. The CPU only obeys orders, blissfully unaware of their meaning or goals.


Call stack is hard to maintain in my brain. What should I?

Do not consider call stacks for recursive algorithms. Ever. Forbidden!
Learn to understand recursive algorithms like any other algorithm that calls other procedures: Assume the calls do their work correctly, and concentrate on making sure the right calls are made, and the results are combined correctly.
Separately, try to find some criterion by which the recursive calls are to "smaller" instances of the problem (assuming instance sizes are e.g. positive integers), and that all "small enough" instances are solved correctly by "base cases" (without recursive calls).
Often the recursive algorithm is modelled on some recursive definition of the structure at hand, then the mapping is simple to prove correct. For an entertaining example of a recursive program that doesn't clearly fall into this category, read and understand Rob Pike's regexp matcher (exegesis by Brian Kernighan)


Are EAX , EBX registers 64 bit in length in modern processors

No, they still refer to a 32bit register. But they are part of 64bit registries RAX, RBX and RCX.
The main reason for this is backward compatibility.


How to implement the details of shotgun hill climbing to make it effective?

The general idea behind doing multiple climbs is to try to avoid local optima. This is the reason shotgun climbing might work better than just a plain hill climbing method.

Usually one starts with a random value. On the other hand if one can guess something better, that can be used as a initial value as well. If there is no knowledge of what a good start value should be, it makes sense to use a random one.

The suitable value for $N$ varies. Usually one has to define a stopping criterion. A suitable criterion might depend on your specific domain. For example, if for some small number of moves you don't improve your solution at all, you stop. In general, you don't know -- you are using heuristics and they give you no guarantees. You might want to even determine a suitable $N$ experimentally.


Can regular languages be Turing complete?

In short, the answer is yes.

But you're mixing two completely unrelated meanings of the term "language" (yes, this is confusing):

A set of strings. "Context-free language" means "a set of strings which can be recognized using a context-free grammar".
A way of specifying a computation. "Turing-complete language" means "a way of specifying programs in which the Turing machine can be specified".

Note that you can talk about "the C++ language" from two completely unrelated viewpoints, using the two unrelated meanings of the word "language":

C++ as a set of strings which are legal according to the C++ grammar
C++ as a way of specifying programs.

The traits of "the C++ language" from these two viewpoints are unrelated.

More examples to help you separate these concepts:

The expression "[a-z]+@[a-z].[a-z]" describes a set of strings recognizable by finite automata, i.e. a regular language. However, it's just that - a set of strings: is not a way of specifying programs (unless you ascribe a way to interpret each such string as a program), so it does not make sense to talk about whether or not it is Turing-complete.
The language of flowcharts is a way of specifying programs; depending on the particular flavor of flowcharts, it may or may not be Turing-complete. However, flowcharts aren't strings, so it makes absolutely no sense to talk about flowcharts in the sense "language as a set of strings".


Is Wadler's 'Theorems for Free' as general as Design By Contract for establishing correctness?

"Theorems for free" are so-called because they follow from the type of the program, without looking at the the program code!

"Contracts" are clearly not free theorems, because they depend on the code of the program, not merely the type.

However, the connection you do want to make is between types and specifications.  Specifications are in a way "more detailed" types.  Or, state the other way, types are more basic specifications.  Martin-Lof type theory is precisely about fusing the two ideas into one.


finding a an object with constant velocity on an infinite grid in discrete time steps

Hint: "Guess" the starting point and the velocity, and use diagonalization. (I.e. make a list $\langle p_i, v_i \rangle$ of pairs of starting points and velocities, and at time $t$ test $p_i + tv_i$.) I'll let you figure out why it works.


Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT

Yes, the number of minimal unsatisfiable partial assignments is upper-bounded by a polynomial.

Suppose there are $n$ clauses.  There are $n$ ways to choose which clause is unsatisfied, call it $C$.  Suppose  clause $C$ mentions variables $x_i,x_j,x_k$.  Then the partial assignment must assign values to $x_i,x_j,x_k$ but not to any other variable.  (If it assigned a value to $x_\ell$, then unfixing $x_\ell$ would leave clause $C$ without a free variable, which violates the second requirement.)  There is only one way to assign values to $x_i,x_j,x_k$ to make clause $C$ unsatisfied.  So, there are at most $n$ minimal unsatisfiable partial assignments.


How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?

Let $S$ be your input sequence and denote by $S[i:j]$ the subsequence going from the $i$-th to the $j$-th element of $S$ (inclusive).

Let $OPT[i]$ be the minimum amount of continuous palindromic subsequences in which $S[1:i]$ can be partitioned. Let $OPT[0]=0$. For $j=1,\dots,|S|$, you have:

$$
OPT[j] = \min_{\substack{i=1,\dots,j\\S[i:j] \text{ is a palindrome}}} \{1+ OPT[i-1] \}.
$$

The value you are looking for is $OPT[|S|]$. This algorithm requires time $O(|S|^2)$. Notice that all the pairs $(i,j)$ for which $S[i:j]$ is palindrome can be precomputed in $O(|S|^2)$ time.


No. The problem is trivial, since taking $I$ to be the empty set always results in a solution to the problem.

Yes, it is NP-complete. Note that if there is a solution, that is

$\Sigma_{i\in I} x_i = \Sigma_{i\not\in I} x_i$

then

$\Sigma_{i\in I} x_i - \Sigma_{i\not\in I} x_i = 0$.

Since we have

$\Sigma_{i\in I} x_i + \Sigma_{i\not\in I} x_i = 0$

then $\Sigma_{i\not\in I} x_i = 0$ and $\Sigma_{i\in I} x_i = 0$.

Proof of NP-hardness is by reduction from partition. For a given instance of the partition problem, a multiset $S$ of integers, where $\Sigma_{s\in S}=2N$, create an instance of Partition with 0-SUM, by adding 2 copies of $-N$ to $S$.

Clearly, if the Partition instance has a solution then so does the modified problem, by adding $-N$ to each half of the partition. If the Partition with 0-SUM restriction has a solution, then so does the original Partition problem: since all the integers in the original partition problem are positive, each 0-SUM "half" of the 0-SUM partition must contain one of $-N$, and the rest must sum to $N$.


Boolean variable that captures whether an inequality holds

Add the inequalities

$$\begin{align*}
a_1 x_1 + \dots + a_n x_n &\ge b - M (1-y)\\
a_1 x_1 + \dots + a_n x_n &< b + M y,
\end{align*}$$

where $M$ is chosen sufficiently large.

Why does this work?  If $y=1$, then the first inequality forces $a_1 x_1 + \dots + a_n x_n \ge b$ to hold.  If $y=0$, then the second inequality forces $a_1 x_1 + \dots + a_n x_n < b$ to hold, i.e., $a_1 x_1 + \dots + a_n x_n \ge b$ to be false.

How large does $M$ need to be?  If the $x_i$'s are zero-or-one variables, then it suffices to take $M$ to be at least $\max(b,a_1+\dots+a_n-b+1)$.  In general, if you have upper and lower bounds for each $x_i$, you can derive how large $M$ needs to be.


What is the strongest weaker version of the halts() function?

The gist of the argument is that the assumption that a one can write a function halt(f) that always halts and always answers correctly if f halts leads to a contradiction (by way of self-reference, applying it to a variant of itself), thus such function can't be written.
Sure, you can write functions that answer "Yes", "No", or "Don't know" (or even never stop) always correctly. Say we consider C programs only, it is (more of less) easy to check they are just a main function that doesn't include any loops, and so answer "Yes" for them, and "Don't know" for anything else. You can certainly refine the above a lot, and each refinement can in itself be further refined (if a program could identify the cases where all have to answer "Don't know", it'd know that for them the answer is "No" --just running the program would tell eventually if the answer is "Yes"). The point is there can't be a way to answer all cases correctly.


Is a language recursive? 2 wrong ways of solving

I'll assume that $R$ is the set of recursive languages and that in the definition of $NPA$ we are talking about Nondeterministic Polynomial Time.

You are just proving that, for $L \in R$, $L \subseteq Disagree(M_1, M_2)=\Sigma{}^*$ which says nothing about $NPA = R$.

To accept a language $L$, there must be some machine $M$ such that for each string $x \in L$ the computation $M(x)$ halts in the accepting state and for each string $x \not\in L$ the computation $M(x)$ does not halt. To decide a language $L$, the machine must halt in all inputs and, furthermore, if $x \in L$ the machine halts in accepting state, otherwise the machine halts in rejecting state.
That doesn't mean that the machine is "tested" simultaneously on an infinite number of strings.

That being said, when you want to prove that two sets are equal you need to prove that each one includes the other.
When you want to prove that two sets are different, it is sufficient to find some language that is in one set but non the other.
In your case, the requirement that $M_1, M_2$ must halt in a polynomial number of steps is suspicious.
If $L \in NPA$, then there are Nondeterministic machines $M_1, M_2$ such that they both halt in a polynomial number of steps and disagree precisely on $L$. From those machines, you can construct a Nondeterministic machine $M_{1,2}$ that decides $L$ in polynomial time, hence $L \in \mathcal{NP}$ and this proves the inclusion $NPA \subseteq \mathcal{NP}$ by generality of $L$.
By the Time Hierarchy Theorem,
$$NPA \subseteq \mathcal{NP} \subsetneq \mathcal{N}EXP \subseteq R$$
Hence $NPA \neq R$.


Why do we need epsilon-transitions in Thompson's construction?

What you're looking at there is what's known as Thompson's construction. The idea is that any node in the regular expression parse tree corresponds to an NFA with a single entry and exit point. To see why the epsilon transitions are useful, try applying the construction to, say, $(a \cup b^*)c$.

Thompson's construction is particularly easy to understand and implement but it is also, as you rightly say, a bit wasteful. It is possible to construct Thompson's automaton with the epsilon transitions removed using Glushkov's method. You may also be interested in Xing's construction.


Regularity condition in the master Theorem in the presence of Landau notation for f

Suppose that $T(n) = aT(n/b) + \Theta(f(n))$. What this means is that $T(n) = aT(n/b) + g(n)$, where $g(n) = \Theta(f(n))$, say $c_{LB} f(n) \leq g(n) \leq c_{UB} f(n)$. Consider now the following two recurrences:
$$
T_{LB}(n) = aT_{LB}(n/b) + c_{LB} f(n), \\
T_{UB}(n) = aT_{UB}(n/b) + c_{UB} f(n),
$$
with the same initial conditions as the initial recurrence. You can show inductively that $T_{LB}(n) \leq T(n) \leq T_{UB}(n)$. Assuming that the function $f(n)$ does satisfy the regularity conditions, you can use the master theorem to solve the two auxiliary recurrences, and hence to deduce the solution to the original recurrence.


Under what circumstances are one-way functions reducible to their hard-core bits?

Inverting a one way function is not always reducible to evaluating a hardcore bit. As an example, consider trivial hardcore predicates. Let $f$ be one way and define $g(x,b)=f(x)$ where $b\in\{0,1\}$. Obviously $b$ (the rightmost bit of a string) is a hardcore predicate for $g$, however knowing it does not bring you any closer to finding the rest of the string. The problem is that such predicates are probably of no use. Usually, we cant afford to lose information (e.g. while constructing pseudorandom generators), so we won't be able to base hardcore predicates on a part of the input that we're not using.

To overcome the above problem (i.e. ignoring trivial hardcore predicates), we can demand that evaluating the predicate will help us reverse the function (if this is the case, then $f(x)$ and $h(x)$ cannot be independent). The generic construction in Goldreich-Levin's theorem indeed yields such a predicate. If $f$ is one way and $g(x,r)=(f(x),r)$, then an algorithm computing $h(x,r)=\langle x,r\rangle$ can be used to find $x$ (just feed it $f(x)$ along with different values of $r$).


Here is a counterexample, with $p = 2$:

stack 1: $600,600$.
stack 2: $1000,0$.
stack 3: $1000,0$.

Your algorithm will choose the top element from stack 1 and one of the top elements from the other stacks, but it is better to choose the top elements of stack 2 and stack 3.

Disclaimer: This is based on your description of the algorithm. I don't understand some of the notation in the algorithm itself.


I propose this, more direct to code (in java, c, etc.)

read each line (until CR/LF)
at begining, read a number, until spaces => number n
after that, take next characters of line
split them by ,
for each, trim (delete space before or after) => strings s1, s2, s3
then output n s1  CRLF n s2 CRLF n s3, etc.


Search Space for Population Metaheuristic Optimization Problem

There are $|x|^{|y|}$ configurations.  Then you want to generate $N$ configurations.  By the same reasoning, there are $(|x|^{|y|})^N$ ways to do that.


Maximize distance between k nodes in a graph

No, the problem is NP-complete.

Let $(G,k)$ be an instance of INDEPENDENT SET.  Construct $G'$ by adding a universal vertex $u$ to $G$.  The crucial observation is that the distance between two vertices in $G$ is 1 in $G'$ if and only if they are adjacent in $G$, and 2 otherwise.

Now, the optimal solution of SCATTERED SET on input $(G',k)$ is $2\binom{k}{2}$ if and only if $G$ has an independent set of size $k$.


Hardness of $2$ edge-disjoint spanning trees decomposition

Your problem is in $\mathrm{NP} \cap \mathrm{co}$-$\mathrm{NP}$.

First, it is obviously in $\mathrm{NP}$. The verifier receives the certificate consisting of two edge-disjoint spanning trees that consumes all the edges in $\mathrm{E}$

Second, by Tutte & Nash-Williams theorem [1], your problem is also in $\mathrm{co}$-$\mathrm{NP}$. The co-nondeterministic machine guesses any partition $\mathrm{P}$ of $\mathrm{V}$ and check that $|\mathrm{E}_\mathrm{P}(\mathrm{G})| \geq 2(|\mathrm{P}| - 1)$. Also, it must check that $|\mathrm{E}| = 2(|\mathrm{V}| - 1)$ to be sure that the tree packing of the above theorem is indeed a decomposition by trees.

[1] Tomas Kaiser, A short proof of the tree-packing theorem, https://arxiv.org/pdf/0911.2809.pdf


Do "Type-2" Turing machines with infinite length inputs have more computational power?

Type-2 Turing machines are not more powerful than ordinary Turing machines in the sense that any map $\mathbb{N} \to \mathbb{N}$ that can be computed by a type-2 machine can also be computed by an ordinary machine. To see this, suppose a type-2 Turing machine $T$ computes a function $f : \mathbb{N} \to \mathbb{N}$. We can convert $T$ to an ordinary machine by modifying it so that it stops as soon as it writes $f(n)$ on the output (and we can tell when this happens because the output is a single finite number, so it cannot take forever for the machine to produce it).

It is far more interesting to go up one level and compare computability of functionals, which are maps
$$F : \mathbb{N}^\mathbb{N} \to \mathbb{N}$$
that take an infinite sequence of numbers as an input and output a number. Now there is a difference between type 1 and type 2.

Say that a functional $F$ is type-2 computable if there exists a type-2 Turing machine $T$ such that, for any sequence $\alpha \in \mathbb{N}^\mathbb{N}$, when $\alpha$ is written on the input tape and machine $T$ is run, it writes $F(\alpha)$ on the output tape (and terminates).

Say that a functional $F$ is type-1 computable if there exists a type-1 Turing machine $T$ (i.e., an ordinary one), such that, for any computable sequence $\alpha \in \mathbb{N}^\mathbb{N}$, if we write onto the input tape the encoding $n$ of a machine that computes $\alpha$, then $T(n)$ writes $F(\alpha)$ on the output tape (and terminates).

Notice that a type-1 computable functional only accepts computable inputs, whereas a type-2 computable functional accepts all inputs. If we write $\mathcal{R}$ for the set of all computable sequences of numbers (i.e., the total computable functions), then a type-1 computable functional is a map $F : \mathcal{R} \to \mathbb{N}$ computed by some type-1 machine, whereas a type-2 computable functional is a map $F : \mathbb{N}^\mathbb{N} \to \mathbb{N}$ computed by some type-2 machine.

Because $\mathcal{R} \subseteq \mathbb{N}^\mathbb{N}$, we can convert any type-2 functional to a type-1 functional by simply feeding it only computable inputs. We have:

  Theorem: When a type-2 computable functional is restricted to computable inputs, it becomes a type-1 computable functional.

Proof. The theorem is not a complete triviality. The input is presented to a type-2 functional as a sequence, whereas to a type-1 functional it is presented as a description of a Turing machine computing the sequence. So, suppose $F$ is a type-2 functional computed by a type-2 machine~$T$. We convert $T$ to a type-1 machine as follows: when given an input $n$ which described a machine $M$ that computes some $\alpha \in \mathcal{R}$, we simulate an input type for $T$ so that whenever $T$ wants the $k$-th cell of the input, we run $M(k)$ to compute $\alpha(k)$ and give $T$ the answer. $\Box$

Can we go in the other direction? Suppose $F : \mathcal{R} \to \mathbb{N}$ is computed by a type-1 machine $T$. Perhaps we can extend $F$ to all of $\mathbb{N}^\mathbb{N}$ to get a computable $\overline{F} : \mathbb{N}^\mathbb{N} \to \mathbb{N}$ which agrees with $F$ on $\mathcal{R}$? The anwser is negative! (See Exercise 15-40 in H. Rogers Jr. "Theory of Recursive Functions and Effective Computability".)

The moral of the story is this (as I have often repeated on these forums): all known notions of computability of functions from numbers to numbers agree, but notions of computability of functionals do not, and they are incomparable in general.


Reducing the integer factorization problem to an NP-Complete problem

Just to be absolutely clear, Integer Factorization is not known to be NP-intermediate, just suspected to be based on the lack of either NP-completeness proof or polynomial-time algorithm (despite lots of work put into both). I don't know of any natural problem (i.e. not constructed by Ladner for the proof) that is definitely NP-intermediate if P and NP are different.

Okay, after that disclaimer, Graph Isomorphism is another likely candidate for a natural NP-intermediate problem. There's a simple polynomial-time reduction from it to Subgraph Isomorphism - just leave the graphs the same! Graph Isomorphism is just the special case of Subgraph Isomorphism where both graphs have the same size. The final touch is that Subgraph Isomorphism is NP-complete.

Apart from that, there is always of course the not-so-informative reduction promised by the  Cook-Levin Theorem, we known that any NP-intermediate problem has some nondeterministic polynomial-time Turing Machine that decides it, and we can convert this into an instance of SAT (just have to build the TM!).


How are variables accessed in the correct order from the stack?

That depends on how your program is written, its language, and how exactly your compiler implements variables. Some languages just don't place variables on any stack (everything is global). This is how FORTRAN and early versions of BASIC used to work. "Normal" languages (like C, Pascal and such) allocate a structure (often called activation record) on the stack, containing space for the local variables, and use architecture-dependent (and compiler-dependent) code to get at the variables. Many scripting languages will have the variables handled by allocating space elsewhere and just linking to the values from an activation record-like place in the stack. Even other languages, particularly LISP-derived ones, don't enforce the last call done -- first call finished rule, and thus can't use a stack for activation records. As @YuvalFilmus comments, there are languages like FORTH around, where it is your responsibility to manage such details.


This is doable with a DFA. Hint: We need to keep track of three things simulataneously:

The parity of a's (have we seen an odd or even number of a's so far?)
The parity of b's
The parity of c's

So there are 8 possibilities for what we've seen so far:

Even number of a's, even number of b's, even number of c's.
Odd number of a's, even number of b's, even number of c's.
Even number of a's, odd number of b's, even number of c's.
...

Does that help?


See also this question: "How is Lambda Calculus a specific type of Term Writing system?".

Term rewriting, as introduced in (1), and described in e.g. (2), is a first-order system that cannot handle binding. Consider the $map$ function.

$$
  \begin{array}{lcl}
  map(f, []) &\rightarrow& [] \\
  map(f, cons(x, l)) &\rightarrow& cons( f\ x, map\ f\ l)
  \end{array}
  $$

The problem is that $f$ is used both as a variable and a function
  symbol, which is not permitted by first-order term-rewriting system.

This lead to higher-order rewriting, see e.g (3) for an overview. Another approach to unification of term-rewriting with the $\lambda$-calculus is
the rewriting calculus (4). Yet another approach  towards rewriting with binders -- arguably the most modern -- is nominal rewriting (5).

D. E. Knuth, P. Bendix, Simple Word Problems in Universal Algebras.
F. Baader, T. Nipkow, Term Rewriting and All That.
T. Nipkow, C. Prehofer, Higher-Order Rewriting and Equational Reasoning.
H. Cirstea, C. Kirchner, Introduction to the rewriting calculus.
M. Fernandez, M. J. Gabbay, Nominal Rewriting.


Why comparison is dominant time consumption for comparison-based sorting algorithms?

Because the number of comparisons dominates the number of other operations. Since costs of all operations are usually pretty much the same (within a constant factor), costs of non-comparison operations get eaten by constants in the asymptotic measure.


NP-complete language as a result of xoring two PTIME languages

This seems like a rather difficult question. Here is one approach.

Every 3CNF on $n$ variables can be encoded as a binary string of length $8n^3$ (how?). Consider the following two languages:
$$
\begin{align*}
L_1 &= \bigcup_{n=1}^\infty \{ xy0^{8n^3} : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \}, \\
L_2 &= \bigcup_{n=1}^\infty \{ x0^{8n^3}y : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \}.
\end{align*}
$$
These two languages are clearly in P, and so their XOR is clearly in NP. However,
$$
(L_1 \oplus L_2) \cap \bigcup_{n=1}^\infty \{0^ny^2 : |y|=8n^3\} = \bigcup_{n=1}^\infty \{0^n y^2 : |y|=8n^3, y \text{ is satisfiable}\},
$$
showing that $L_1 \oplus L_2$ is NP-complete.


Dataflow framework for global analysis: Why meet, then apply?

It's the classic precision/efficiency tradeoff. You can, in fact, move the meet outside, since $f(x \sqcap y) \sqsubseteq f(x) \sqcap f(y)$. A canonical example of where this makes a difference is in the following constraint-propagation problem:

IF b
  x = 1
ELSE
  x = -1

y = x*x

The Dragon Book's suggestion will compute $(x=1) \sqcap (x=-1)=\top$ before evaluating $x*x$, and will thus not capture that $y$ is a constant. By computing the meet after (twice) evaluating the multiplication, yours will. What you have effectively done is added a small amount of path-sensitivity, for a small price in efficiency. You can continue down this path arbitrarily. Two steps of this analysis may compute $f(f(w\sqcap x) \sqcap f(y\sqcap z))$. Your suggestion would instead compute $f(f(w)\sqcap f(x))  \sqcap f(f(y) \sqcap f(z))$, but you can take this farther and increase the path-sensitivity by computing $f(f(w))\sqcap f(f(x))\sqcap f(f(y)) \sqcap f(f(z))$. The fully path-sensitive MOP (meet-over-paths) solution is undecidable. The Dragon Book's algorithm gives an MFP (maximal fixed point) solution, which safely approximates the MOP. You've simply refined the approximation a bit.


Reducing 3CNF to Clique: Why do we omit negated literals?

What is meant, is that literals that are the negation of each other are not connected. The reason for this is that they cannot both be satisfied at the same time. (The idea of the reduction is, that the graph contains a clique containing nodes corresponding to one literal from each clause, exactly if all these literals can be satisfied at the same time.)


You need more carefully defined $\theta$-join and then set difference:

$$R1 := \rho_{name1/name,hobby1/hobby}(Person)$$
$$R2 := Person \bowtie_{(hobby=hobby1) \land (name \neq name1)} R1$$
$$R3 := \pi_{hobby}(Person) \setminus \pi_{hobby}(R2)$$


what would be the time complexity of DBSCAN algorithm?

As the graph is sparse, if you have a data structure to query in $O(\log{n})$, you can reach to $O(n \log{n})$ for your case. More details in this link:

DBSCAN visits each point of the database, possibly multiple times (e.g., as candidates to different clusters). For practical considerations, however, the time complexity is mostly governed by the number of regionQuery invocations. DBSCAN executes exactly one such query for each point, and if an indexing structure is used that executes a neighborhood query in $O(\log n)$, an overall average runtime complexity of $O(n \log n)$ is obtained (if parameter $\varepsilon$ is chosen in a meaningful way, i.e. such that on average only $O(\log n)$ points are returned). Without the use of an accelerating index structure, or on degenerated data (e.g. all points within a distance less than $\varepsilon$), the worst case run time complexity remains $O(n^2)$. The distance matrix of size $(n^2-n)/2$ can be materialized to avoid distance recomputations, but this needs $O(n^2)$ memory, whereas a non-matrix based implementation of DBSCAN only needs $O(n)$ memory.


Can the Euclidean distance function be computed using only XOR's

No.  It's not possible.  Any function that can be computed using just XOR's is affine over $GF(2)$.  However, the Euclidean distance is not affine over $GF(2)$, so there is no hope of representing it with just XOR's.

Recall that $GF(2)$ denotes the finite field with two elements; you might also see it indicated by $\mathbb{F}_2$, and it is the field $(\{0,1\},\oplus,\times)$, where $\oplus$ represents the XOR operation (i.e., addition modulo two) and $\times$ represents the AND operation (i.e., multiplication modulo two).

Recall that a function $f$ is linear if it can be expressed as a linear map, i.e., $f(x+y)=f(x)+f(y)$ holds.  More specifically, suppose we have a function $f:GF(2)^n \to GF(2)^m$ that maps from a vector space over $GF(2)$ to a vector space over $GF(2)$.  Then $f$ is linear if $f(x \oplus y)=f(x) \oplus f(y)$ for all $x,y$, where $\oplus$ denotes element-wise XOR.  Equivalently, $f$ is linear if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1), such that $f(x) = Mx$.

A function $g$ is affine if it is of the form $g(x)=f(x)+c$, where $f$ is linear and $c$ is an arbitrary constant.  In our case, $g$ is affine if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1) and a constant $c \in GF(2)^n$, such that $g(x) = Mx+c$.  See, e.g., this Wikipedia article for more.

The XOR operation is linear.  Also, because the set of $GF(2)$-affine transformations is closed under composition (this follows because $(\{0,1\},\oplus)$ is a group), it is easy to see that any circuit built solely out of XOR's must be $GF(2)$-affine.  (Why affine, rather than linear?  Because a circuit can contain constants: it can take an input and XOR it with the constant 1.  That makes it affine, rather than linear.)

Now it is easy to verify that the Euclidean distance is not $GF(2)$-affine, just by looking at a few values: e.g., you can look at $d(0,0)$, $d(0,1)$, $d(1,0)$, $d(1,1)$.  If $d$ were affine, we would have the relationship

$$d(0,0) \oplus d(0,1) \oplus d(1,0) \oplus d(1,1) = 0.$$

Since this relationship does not in fact hold, $d$ is not $GF(2)$-affine.

And since $d$ is not an affine function of its inputs, this means it cannot be expressed using only XORs.

Certainly NAND gates would be sufficient, as they are universal. It could also be expressed using just XORs and ANDs, as those two are also universal.  There are many other options.


Cost of solving a matrix equation using the FFT

If $m \times m$ symmetric matrix $\rm H^{\top} H$ is circulant, then its spectral decomposition is
$$\rm H^{\top} H = Q \Lambda Q^*$$
where the eigenvalues of $\rm H^{\top} H$ are given by the Discrete Fourier Transform (DFT) of the first row of $\rm H^{\top} H$, and where the eigenvalue matrix is
$$\rm Q =  \frac{1}{\sqrt m} \, F_m$$
where $\rm F_m$ is the $m \times m$ Fourier matrix. Hence,
$$\rm H^{\top} H + I_m = Q \Lambda Q^* + I_m = Q \Lambda Q^* + Q Q^* = Q \, (\Lambda + I_m) \, Q^*$$
and
$$\rm  \left( H^{\top} H + I_m \right)^{-1} U = Q \, (\Lambda + I_m)^{-1} \, Q^* U = \frac 1m \, F_m \, (\Lambda + I_m)^{-1} \, F_m^* U$$
The Fast Fourier Transform (FFT) algorithm can now be used to factor the Fourier matrix $\rm F_m$ and its Hermitian transpose. What is the cost?

Computing $\Lambda$ requires one DFT of length $m$. Using the FFT, that costs $O (m \log (m))$.
Computing $\rm F_m^* U$ requires $n$ DFTs of length $m$. Using the FFT, that costs $O (n \, m \log (m))$.
Multiplying $\rm (\Lambda + I_m)^{-1}$ and $\rm F_m^* U$ costs $m$ additions and $m \, n$ divisions.
Computing $\rm F_m \, (\Lambda + I_m)^{-1} \, F_m^* U$ requires $n$ DFTs of length $m$. Using the FFT, that costs $O (n \, m \log (m))$.
Dividing $\rm F_m \, (\Lambda + I_m)^{-1} \, F_m^* U$ by $m$ costs $m \, n$ divisions.

Thus, the total cost is $O (n \, m \log (m))$.

References

Robert M. Gray, Toeplitz and circulant matrices: a review.
Complex matrices; fast Fourier transform, MIT 18.06SC Linear Algebra, Fall 2011.


To generate an empty string you take: $(b+c)^*$ as $\epsilon$, and all the following elements which have a Kleene-star as $\epsilon$ (I will use $\epsilon$ instead of $\lambda$).

Then you have: $$\epsilon(a+\epsilon)\epsilon(a+\epsilon)\epsilon$$
Which is equivalent to: $$(a+\epsilon)(a+\epsilon)$$

Which is essentially picking two options a or $\epsilon$ twice back to back. If you take $\epsilon$ transition each time, which is actually a transition that does not consume an input, it will essentially accept an empty string as input.


How can a distributed system cooperate to determine rules of its environment?

This is a non-mathematical riddle, so part of the solution is determining the rules of the game. The computer science way of solving this, however, would be to use a Gray code and a synchronized system. The idea is as follows. Suppose that there were only 3 switches. You will go over their states in the following order:
$$
000\\001\\011\\010\\110\\111\\101\\100
$$
(Here 0 is the original state of the switch, and 1 is the other state of the switch.)
Decide on a reasonable time interval $t$. There will be 8 rounds (or, in general, $2^k$ rounds if there are $k$ switches), each taking $t$ units of time. Each round other than the first begins with the appropriate person changing one of the switches (the appropriate person can be determined in advance once we know how many switches are in each room). Then they all record the "output" that they see in their room. When this process ends, they can compare notes and reconstruct the entire function.

This strategy is optimal with respect to the number of switch flips. While it takes $2^k$ rounds for $k$ switches, you can't really do any better since the function converting the input (switches) to the output (lights) is completely arbitrary. This does mean that it doesn't scale at all. If you want a strategy that does scale, you'll have to adjust the problem by restricting the set of possible functions (switch–light correspondences).


Just some pointers:

I remember seeing a paper about kd-trees being executed on a GPU, which I think implied them being presorted and then moved into GPU memory. Kd-Trees are not BVHs though.

Also, there are bulkloaded R-Trees (R-Trees are basically BVHs), such as the STR-R-Trees (sort-tile-recurse) which pre-sort primitives, but not necessarily with memory locality in mind, but that could easily be achieved.

Finally, there is the PH-Tree (disclaimer: I wrote the paper about it). It stores all geometric data for each node in a single byte-stream for this node (maximum memory locality), however, the parent and children of a node are not necessarily neighbors in memory (the actual implementation, e.g. V13, uses object pooling, so many nodes are likely to be close in memory, but that is not a given, let alone scientifically evaluated. Also, the PH-Tree is not a BVH, it is more like a quadtree. Also, the PH-Tree has come a long way since the original version, it now supports rectangles/boxes (the original paper only mentions points).


Basically Dual-pivot Quicksort buys you two items:
The best case running time is $\Theta(n \log_3 n)$ instead of $\Theta(n \log_2 n)$ since each partition is the third part of the entire current range. Also, if one pivot is not good (it is close to one of the ends of the current range), there is a good chance that the second pivot will be better.


You can start with Data Mining: Concepts and Techniques.

To see data mining algorithms in practice you can use Weka.


The running time of the InsertTerm subroutine is $\Theta(n)$ where $n$ is the number of terms in the polynomial, and this is the worst-case complexity as well as the average-case complexity absent any information about the monomial being inserted.

The outer loop of PolynomialAdd runs MaxDegree(Poly1.head, Poly2.head) times. Inside each iteration, the inner loops search for a node with the right degrees in each polynomial. For terms of degrees that are absent from the monomial, or present near the end of the monomial, the running time of the inner loop is $\Theta(n)$ where $n$ is the number of terms in the respective monomial. The running time of InsertTerm has been discussed above; here all I need to know is that its $\Theta(n)$. Hence the running time of PolynomialAdd is $\Theta(\max(x,y) \cdot (x + y))$ where $x$ and $y$ are the number of terms in the polynomials Poly1 and Poly2 respectively.

The number of calls to InsertTerm in PolynomialMul is clearly $xy$, since the outer loop always runs $x$ times and the inner loop always runs $y$ times. I assume that Node1.Deg + Node1.Deg is a typo and you really meant Node1.Deg + Node2.Deg. I won't give a full proof here, but intuitively speaking, this is going back and forth inside the result list, and so on average the time spent in insertTerm is about half the length of the list: $\Theta(x+y)$. Therefore the running time of PolynomialMul is $\Theta(x\,y\,(x+y))$.

It is possible to implement polynomial addition and multiplication with faster running times, but you'll need to improve your code. The core idea is that you waste a lot of time in InsertTerm, inserting at random positions in the result list. Instead, arrange to construct the result list in order: first the lowest-degree term at the end of the list, then the previous term, etc. (Alternatively, if you find it easier, construct the list in the other order, starting with the highest-degree term and maintaining a pointer to the next pointer in the last node). Furthermore, do not traverse the arguments again on each iteration through the loop: in addition, iterate over the two arguments simultaneously; in multiplication, where you need to combine terms of different degrees, remember where you stopped so you can start again from the same point.


What are some examples of types that can't be derived set theoretically?

There are several type-theoretic constructions that cannot be easily handled with set theory. Note that when we say "set theory" we mean that we intend to interpret types as sets and type-theoretic functions as set-theoretic functions. In particular, the set-theoretic interpretation of types requires that a function type A → B must be interpreted as the set of all set-theoretic functions from A to B.

If our type theory has general recursion then it cannot be interpreted set-theoretically. General recursion allows us to define, for any type A, the fixed-point operator fix : (A → A) → A

fix f = f (fix f)

but the only sets which have such a fixed-point operator are the singletons. For example, if we take A to have two elements, then it will have a function without fixed point (the one that swaps the elements).

Another reason that set theory may not be sufficient is polymorphism, as you indicated. Here the reasons are perhaps a bit technical and it is best to read the famous paper Polymorphism is not set-theoretic by John Reynolds. Beware: reasoning about how one might get away with a polymorphic identity function is not proof that set theory models polymorphism. In any case, your suggestion to use universes is not going to work for System F. You can have an identity function that works for one universe, but to make it work for all universes you will have to make it universe-polymorphic, and so you're back to square one.

A third reason that a type theory may not be set-theoretic is that it allows constructions of types that do not exist in set theory. For example, in many programming languages we can define recursive types (Haskell and ML are like this) such as

type t = bool + (t -> t)

The set-theoretic counterpart of this is a set T such that
$$T \cong 2 + T^T$$
but such a set $T$ does not exist, because the cardinality of $2 + T^T$ is strcictly larger than the cardinality of $T$.

A fourth reason that a type theory may not be set-theoretic is that it may contain constructs that prevent this. For example, we could have a type theory with a timeout construct which works as follows: timeout k x e computes e for at most k steps (where "step" need to be suitably defined). If e finishes with result y within k steps then the overall result is y, otherwise the overall result is the "fallback" value x. From a programming point of view, this is a reasonable construct that can actually be implemented. However, as soon as we have timeout we can write down functions that do not exist in set theory. One such function is the modulus of continuity which witnesses the fact that "all functions are continuous". In set theory there are many discontinuous functions.

Lastly, if we take "spartan" type theory without any special features (no general recursion, no polymorphism, no recursive types, etc.) then it is set theoretic. You need to extend type theory in some fashion to break the set-theoretic interpretation.


Big O notation comes from number theory.

It's not about time or space at all. It's about the rate of growth of functions.

Even in computer science, we use it measure many other quantities, for example the number of rounds in a protocol, the depth of a circuit, the error probability of an algorithm, and so on.


Concatenation among different language types

The language $L'$ contains all possible strings, and so it is in particular regular. This is because the empty word is in $L$, and so $L\cdot \{0,1\}^* \cdot L^R$ contains $\{0,1\}^*$. If you "proved" that it's not regular using the pumping lemma, you have made a mistake applying it. Try to find it; this will lead to better understanding of the pumping lemma.


Note: this answer assumes that we are considering polynomial-time reductions (and not e.g. log-space ones).

If $A$ belongs to $P$, then we can reduce $A$ to any nontrivial language, i.e. any $B\neq \emptyset,\Sigma^*$.

Reducing $A$ to $B$ can be done as follows. Fix $b_1\in B, b_0 \in \overline B$ arbitrarily. The reduction algorithm then takes an input $x$ and tests whether $x\in A$: if that holds, return $b_1$, otherwise return $b_0$.

Note that all of this can be run in polynomial time since $A$ belongs to $P$. This allows to solve the $A$ instance in the reduction algorithm itself, trivializing the reduction.

This proves that problems in $P$ are indeed the easiest possible ones, according to the "polynomial-time reduction" preorder.


The link doesn't say what you say it does.  I don't see the number 180 appearing anywhere on that link.  And that link doesn't say the purpose is to prove $T(n) \le 5 n \log n$ for all $n \ge 0$; it says to prove that $T(n) = O(n \log n)$.  Check the definition of big-O notation; it doesn't require proving $T(n) \le c n \log n$ for all $n \ge 0$; it suffices to prove it for all $n \ge 180$ (or for all $n \ge n_0$ for any other constant $n_0$ of your choice).


Yes, this can be solved efficiently using standard methods for bipartite matching and the assignment problem.  Let me build up to a solution, so you can see the ideas underpinning it.

If you want to minimize the maximum affinity, you can do that with binary search.  Pick a threshold $t$, and check whether there is a valid solution using only assignments that have an affinity $\le t$.  That check can be done by looking for a perfect matching in a bipartite graph, which can be done in polynomial time for a single value of $t$.  (The graph has an edge from a packet to a node if their affinity is $\le t$, otherwise the edge is absent.)  Now do binary search over $t$ to find the smallest $t$ for which such an assignment exists.

If you want to minimize the sum of the affinities, this is an instance of the assignment problem.  There are polynomial-time algorithms for the assignment problem, which you can use directly.

If you want to minimize the max of the affinities, but break ties by choosing the one with the lowest sum, then you can combine above two methods.  First, find the smallest $t$ such that there exists an assignment using only affinities $\le t$.  Then, create an instance of the assignment problem, using only affinities that are $\le t$, and solve the corresponding assignment problem.  This gives an efficient algorithm to solve your problem.


Is Smoothed Analysis used outside academia?

I could be wrong, but I view smoothed analysis as a way to explain the in-practice behaviour of algorithms that have bad theoretical guarantees (simplex, k-means, and so on). I'm not sure what it would mean to use smoothed analysis in practice, except to justify the use of a particular heuristic with bad worst-case performance ("My heuristic has blah blah worst-case behaviour but a smoothed analysis indicates that it will do well in practice etc etc")


Extracting intersecting objects of the same colour from an image

First, I would suggest you to take a look at morphological operations on images, especially dilation and erosion. Dilation grows the boundary of foreground pixels (gets rid of holes), and erosion shrinks the boundary of foreground pixels (gets rid of bridges). In your case, erosion with an appropriate kernel might get rid of those unwanted lines. Then you apply dilation with the same kernel to preserve the circles. The two of them applied together in this order is called opening. Those functions are predefined in OpenCV, check out morphologyEx function.

Second, I would suggest you to take a look at convexity of shapes. The output circles in your images are convex, but the ones with lines are now. Thus, you can find the non-convex points of the contours (that you already found), and connect the contours from those points, so that you have convex shapes, i.e. desired output circles. To accomplish this, you can find the convex hull and convexity defects using related OpenCV functions.


This is the Steiner Tree problem, specifically the Steiner Tree problem in graphs: the vertices in $H$ are the terminals.  Unfortunately it's NP-hard, so it's very unlikely that a polynomial-time algorithm exists.

If $E$ describes a metric, then the minimum spanning tree on $H$ gives a 2-approximation.


What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights?

It is called a SumTree. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.


In each step of the Huffman coding algorithm the list of probabilities is being sorted and the 2 lowest of them are merged into a new node of the tree, resulting into a new probability. As for your  example probabilities the below illustration shows:

step 1:  [1/55,2/55,3/55,4/55,5/55,6/55,7/55,8/55,9/55,10/55]
step 2:  [3/55,3/55,4/55,5/55,6/55,7/55,8/55,9/55,10/55]
step 3:  [4/55,5/55,6/55,6/55,,7/55,8/55,9/55,10/55]
step 4:  [6/55,6/55,7/55,8/55,9/55,9/55,10/55]
step 5:  [7/55,8/55,9/55,9/55,10/55,12/55]
step 6:  [9/55,9/55,10/55,12/55,15/55]
step 7:  [10/55,12/55,15/55,18/55]
step 8:  [15/55,18/55,22/55]
step 9:  [22/55,33/55]
step 10: [1]

So in each step the set of the corresponding probabilities is reduced by 1. This corresponds to the size of the tree being increased by one.
Without drawing the tree we can quickly deduce that the length (or height depending on how you visualize it) will be 10.This is because the algorithm terminates when we reach the root of the tree that corresponds to probability of 1. As you can see there is absolutely no difference with the case of probabilities being all equal or any other specific distribution of probabilities among the symbols.

Note that there is not direct link to the average length of the resulting code and the length/height of the Huffman tree. The former depends very much on the probability distribution of the alphabet symbols. The best metric that we can use to address this issue is the entropy of the source that uses the alphabet under consideration. Entropy is a measure of the average uncertainty that we have about which symbol will appear next (at source's output) and is defined as this
$$H(\Phi) =\sum_{i=1}^{N} p(s_i)\cdot log_2(1/p(s_i))$$
Entropy indicates the minimum average codelength that we can achieve in coding the source $\Phi$. In general, when the symbols have all equal probabilities of appearance the entropy is maximized and $H(\Phi)=log_2N$. The intuition behind this is that when all symbols are equiprobable then our uncertainty about the source's output is maximized.


What is the algorithm for Blockchain's Byzantine Fault Tolerance?

Actually the differences are more intricate than that. A problem here might be that the properties of "blockchains" are not very well specified and the term is used for a wide variety of things (going as far as simple databases) for marketing. So let's see what is out there.

When you are designing a fault tolerant system there are multiple properties to take into account. These include:

Crash or byzantine failures

  Should the system be designed to withstand nodes just stopping to do anything (i.e. no messages at all) or should it also consider nodes which exhibit arbitrary behaviour?

Eventual or strong consistency

  Should the system provide certainty, that some state is final and not revertible or are we okay with irreversibility with high probability?

Open or closed membership

  Is it known in advance (and to all nodes) who is participating in the protocol? E.g. a reliable database used by google has a defined number of nodes, which are known to all other nodes. In Bitcoin it is unclear even how many miners are participating in the consensus algorithm.

There are a few more things, but these are the most important ones. I am regularly contacted by people who want to use blockchain technology and the conversations always come down to figuring out what requirements regarding these three properties they have and then I recommend some system.

For the most well known ones the properties are:

Bitcoin / Ethereum: Byzantine failures, eventual consistency, open membership
RAFT / Paxos: Crash failures, strong consistency, closed membership
PBFT / Zyzzyva: Byzantine failures, strong consistency, closed membership

When choosing a system you try to take the easiest one possible, as the stronger models normally come with a large penalty in latency and throughput for transactions.

Crash failures are easier than byzantine failures. This is easy to show, as byzantine failures include crash failures. Most of the algorithms include some kind of voting. Having a majority is sufficient with crash failures to make decisions, while byzantine failing nodes might send different votes to different receivers. This might lead to two honest nodes seeing different results for the overall vote and getting out of sync.

Open membership is much more difficult than closed membership, as sibyl attacks, where an attacker generates many identities need to be counteracted by something like proof-of-work or proof-of-stake. This is the main new thing Bitcoin invented and that created the blockchain hype. A chain of blocks of transactions has existed before, as batched commits of transactions was a standard thing for at least 20 years before Bitcoin.

Applying this to the algorithms I listed:

The overhead of RAFT is small, PBFT and Zyzzyva already have a significant amount of communication overhead ( O(n^2) messages and a large number of signatures). Systems like Bitcoin and Ethereum have latencies in the order of minutes to hours (depending on your required level of security).


Is there a research name for "systems that steadily grow in complexity as they are computed"?

Hypothesis could be :

The time is discrete, let $s_i$ be the state of your system at $t=i$.
Your system is deterministic and  its transition function $f$ is computable.
Its complexity $c : \mathbb{N} \to \mathbb{N}$ is the Kolmogorov complexity, $c(i)$ is the length of the shortest C++ program which prints $s_i$.

Then you have a bound : $$c(i) \leq O^+(1) + c_0 + |f| + |i| = O^+(1) + |i| $$

($O^+(1)$ is a notation for a positive constant, |x| is the Kolmogorov complexity of x)

And more generally for any computable function $g$ : $$c(g(i)) \leq O^+(1) + c_0 + |f| +|g| + |i| = O^+(1) + |i| $$

The system complexity grows more slowly that any computable function !

Conclusion :

You should look at systems which are not deterministic or whose transition function is not computable. Or use an other definition for complexity (like this one : Chaos Theory).
With Kolmogorov complexity, chaotic states are more complex than states with lifeforms defending themselves, but may be one can define a physical macroscopic Kolmogorov Complexity where the  unbreakable basic components for describe the world are quite big and their internal features are negligible. Then it becomes more complex to describe tangle of life and vacuum than homogeneous chaos.


Asymptotic time complexity of a two-loop program

The first loop has $y$ iterations, each iteration takes constant time ($O(1)$), so all together we have $O(y)$. The second loop has $\log_2(y)$ iterations of constant time, giving a complexity of $O(\log_2(y))$. Both loops together we have: $O(y + \log_2(y)) = O(y)$ because $y$ dominates $\log_2(y)$.


Are there any algorithms that run in (2 ↑ ↑ n)?

Yes! A simple automaton-based algorithm for answering first-order queries in Presburger arithmetic (and some extensions) has worst-case running time about $2 \uparrow\uparrow n$, where $n$ is the number of quantifier alternations in the query.   Despite this formidable worst-case running time the algorithm has been implemented and gives useful results (see Hamoon Mousavi's implementation here).


Surely multiple randomly addressed writes would potentially overwrite critical data...

Nope.  The oblivious RAM data structures take care to ensure that, when doing reads and writes at random locations, they don't mess up the data.  For instance, if doing an extra write, then they make sure to write the same value that was already there (except in encrypted form), so that it doesn't change what value is stored there.

  batching the writes would stop an attacker knowing exactly which addresses were written to at a given time

But the attacker would still know which set of addresses were written, which is leakage of partial information.  Oblivious RAM aims to eliminate even this partial leak.  So oblivious RAM achieves a stronger property than batching could ever provide.


Are there any compression algorithms based on PI?

Your suggestion doesn't make much sense, for many reasons. First of all, when trying to compress a large file, say a file of size $16$ bytes, you will have to find a place in the binary expansion of $\pi$ which agrees with your file. Since the file is $128$ bits long, one would expect this place to be around the $2^{128}$th bit. So it would be rather hard to find. This is not only because we have to go far into the expansion, but also since we expect to try $2^{128}$ different locations before finding a hit.

Second, while in some cases your scheme will result in a major compression, this will only happen when a certain string appears comparatively early in the expansion of $\pi$. There is no reason you would ever want to compress that sort of string. In contrast, other compression algorithms try to find structure in the data, and have guarantees that show that if such a structure exists, then they can always exploit it.

Changing $\pi$ with any other number wouldn't change the picture. The algorithm is too specific, compressing only strings we aren't really interested in; and very inefficient in the compression phase.


Are there any problems in $APX - PTAS$ that are not $APX$-complete?

Yes, at least under some reasonable assumptions. Crescenzi, Kann, Silverstri & Trevisan show that Minimum Bin Packing, Mininum Degree Spanning Tree and Minimum Edge Coloring are APX-intermediate unless the polynomial hierarchy collapses.

Considering that the paper is from 1996, I'm sure there's now a significantly larger number of known APX-intermediate problems.


How to rank these functions in increasing order of complexity [Algorithms]?

I solved it after understanding asymptotic notation and the complexity of some common functions. Here's the order from least expensive to most expensive:

  log log n, log n ~ ln n, (log n)^2, sqrt(n), n, n log n, n^(1+x), n^2,
  n^3, n-n^3+7n^5, 2^(n-1) ~ 2^n, e^n, n!


Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph

Let $R(s,t)$ be the least integer $k$ such that every graph on $k$ or more vertices contains either a $s$-clique or independent set of size $t.$

It turns out that this number is well defined (called Ramsey number) and the statement in your question merely amount to saying that $$R(t,t) \leq 2^{2t}.$$

A well known upper bound for Ramsey number states $$R(s,t) \leq R(s,t-1)+R(s-1,t) \leq {s+t-2 \choose t-1} \; \; \; (1)$$ if $s = t$ then the above reduces to the central binomial coefficient ${2t-2 \choose t-1}$ which is always smaller than $2^{2t}$

To prove $(1)$ one can use induction on $s+t$.  Leaving the induction base $R(1,t), R(s,1)$ as an exercise for you let us suppose the inequality holds for all $s+t < k$ and let $G$ be a graph with $R(s,t-1)+R(s-1,t)$ vertices.

Let $v$ be an arbitrary vertex of $G$ and partition the remaining vertices of the graph into two groups $A,N$ - those adjacent with $v$ and those that are not adjacent with $v.$ Now since $$|A|+|N|+1 = R(s,t-1)+R(s-1,t)$$ we have either $$|N| \geq R(s,t-1) \quad \mbox{ or} \quad |A| \geq R(s-1,t).$$ Now if the first inequality is satisfied then the graph induced by $N$ either contains a $s$-clique or the graph induced by $N \cup \{v\}$ contains an independent set of size $t.$ In particular this implies that in this case $G$ either contains a $s$-clique or independent set of size $t.$ The second case is verified analogously and establishes the first part of the stated bound. For the last part observe that $${s+t-3 \choose  s-1} + {s+t-3 \choose s-2} = {s+t-2 \choose s-1}.$$


Algorithms which are both deterministic and non-deterministic

First of all, your terminology is at odds with computability and complexity theory. What you are asking is whether it makes sense for an algorithm to have both randomized and non-randomized components. A good example are algorithms which have to be unpredictable (say for cryptographic reasons), but for the purpose of testing have to be predictable. In this case, we substitute a pseudorandom number generator for the true (say, physical) random number generator for testing purposes.

That said, the class of algorithms you are describing are just randomized algorithms. Nothing forces a randomized algorithm to use randomization, it's just a possibility in the model, in the same way that a non-deterministic Turing machine can be deterministic, or that a real number can be rational.


What is polynomial-time reduction?
Let us recall the definition of polynomial-time reduction (function) as presented in section 34.3, NP-completeness and reducibility
CLRS, third edition.

Let $\Sigma=\{0,1\}$. A language $L_1$ over $\Sigma$ is polynomial-time reducible to a language $L_2$ over $\Sigma$, written $L_1 \le_p L_2$, if there exists a polynomial-time computable function $$f: \{0, 1\}^*\to\{0,1\}^*$$ such that for all $x\in \{0,1\}^*$,
$$x\in L_1\Longleftrightarrow f(x)\in L_2.$$ We call the function $f$ the reduction (function), and a polynomial-time algorithm $F$ that computes $f$ is a reduction (algorithm).

Examples

[FALSE]$\ \ $ If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X \not\in \bf{P}$.

What is $O(2^n)$? It is not $\Omega(2^n)$! For example, a constant function is in $O(2^n)$. If set $Y$ can be solved in constant time and $Y \leq_p X$ then $X$ can be in $\bf{P}$. For example, we can let $X=Y$.

[FALSE]$\ \ $ If $Y\le_p X$ and $X$ is solvable in constant time, then $Y$ is solvable in constant time as well.

You cannot ignore the time spent in the reduction step. $Y\le_p X$ tells us that it takes no more than polynomial time to map (a.k.a. reduce) an instance (a.k.a a word) of $Y$ to an instance of $X$. That polynomial time, as you suspected, is significant.
In fact, the complexity class $\mathbf P$ can be defined as all $Y$s such that $Y\le_p X$ for some $X$ that is solvable by constant time.

[ALMOST TRUE]$\ \ $ Say you have $SORT$ which checks if the list of ints is sorted, then for all $X$ we have $SORT \leq_p X.$

There is a polynomial-time computable function $f$ that maps a word in $\{0,1\}^*$ that encodes a sorted list of ints to 1. Basically, we can use an algorithm that checks each int in the list is not greater than than the next int in the list. This algorithm is, in fact, linear-time.
Suppose word $x_0\not\in X$ and $x_1\in X$. Let $g$ be a function that maps 0 to $x_0$ and 1 to $x_1$. $g$ can be computed by a constant-time algorithm, since both $x_0$ and $x_1$ are fixed sequences of 0s and 1s. $g\odot f$ is a polynomial reduction from $SORT$ to $X$.
As long as $X$ is not the empty set nor the set of all words over $\Sigma$, $SORT \leq_p X.$
If $X$ is empty set, there is no reduction of any kind. If $X$ is the set of all words, then any map to $X$ will map any instance, including a "no" instance to a "yes" instance of $X$. Because of these two exceptions, we can say the proposition is false.

[TRUE]$\ \ $ Assume $Y \leq_p X$, if $Y$ doesn't have a polynomial time algorithm to solve it, then there isn't one for $X$ either

$Y \leq_p X$ implies
$\quad X$ is solvable in polynomial time $\Longrightarrow$ $Y$ is solvable in polynomial time.
Note that contrapositive of that implication is exactly
$\quad Y$ is not solvable in polynomial time $\Longrightarrow$ $X$ is not solvable in polynomial time.
Exercises
Check whether the following propositions are true.
Proposition 1.  If set $Y$ can be solved in $\Omega(2^n)$ and $Y \leq_p X$ then $X \not\in \bf{P}$.
Proposition 2.  If set $X$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $Y \not\in \bf{P}$.
Proposition 3.  If set $X$ is solvable by polynomial time, then $\mathbf P$ can be defined as all $Y$s such that $Y\le_p X$.


Why do Computers use Hex Number System at assembly language?

Computers don't use the hexadecimal number system for assembly language. Assembly language, or rather machine code, uses base 256 (typically): instructions are encoded in units of bytes. When displaying machine code, it is customary to use octal or hexadecimal. The reason is that in many cases, the byte is further subdivided into bitstrings, and identifying these bitstrings is easier when using a base which is a power of 2. Hexdecimal is particularly compact since each byte can be encoded using exactly two hexadecimal digits.


Context Free Grammar to Regular Expression?

The set of all regular languages is a subset of context free languages. So if you have a context free grammar (CFG) that generates a regular languages, you most certainly can convert it to a regular expression (RE), regular grammar (RG), or finite automata (FA).
Before I go further with your example, I will simplify it so that we only deal with 3 terminals (instead of 8). In the example below, the terminals a,b,c will be represented by the single terminal a, the terminals x,y,z will be represented by x, and the terminals p,q will be represented by p.
S -> N V
N -> a N | N N | N a | x
V -> N V | p

There is no real procedure in converting it, so we will take it step by step. First we need to see what kinds of strings the variable N can produce.
We can see that for every N introduced, it terminates with x. The a's can be on either side of x and repeat as many times as needed. This entire pattern can be repeated as many times as needed, but be produced at least once. So N generates the same strings as $(a^*x^+a^*)^+$ RE.
Next we look at V. It can produce any amount of N's but must terminate with a single p. So we have $((a^*x^+a^*)^+)^*p = (a^*x^+a^*)^*p$.
Finally, S produces NV which is similar to our RE for V. Note that there is at least one N produced. So that CFG is converted to $(a^*x^+a^*)^+p$.
To put it in terms of your original grammar, it would look something like this $((a|b|c)^*(x|y|z)^+(a|b|c)^*)^+(p|q)$. Again, because of the amount of terminals in the original grammar, it is easier to simply things to help see the pattern the grammar is actually showing.
As a disclaimer, this is not a proof, but it shows the reasoning as to how I created an RE from the CFG you provided. To know if this is correct, you would need to know the exact language the CFG produces. Unfortunately, the grammar is not easily recognizable.
I used the following CFG Developer tool to help see a pattern from your grammar.


Yes, approximate-any-quantum-gate implies can-solve-BQP-efficiently.

Even if the cost of approximating gates is very high, you only need to approximate Hadamard, CNOT, and $Z^{1/4}$ operations to some constant fidelity before error correction starts to work. So although you may pay a large constant overhead to get "good enough", once you get there the extra overhead to achieve better and better precision becomes reasonable.


Here is an idea. By factoring the numbers, we are reduced to the following problem:

  Given a set $S$ of vectors in $\mathbb{N}^k$, find a maximum-size subset $T \subseteq S$ such that for every $x \in T$ we have $x \leq \sum_{y \in T - x} y$ (pointwise).

If there is some $x \in S$ and some coordinate $i \in [k]$ such that $x_i > \sum_{y \in S - x} y_i$, then clearly $x_i$ cannot belong to any such set $T$, and we can simply remove it. Keep removing such elements from $S$ until no such elements exist. Then for every $x \in S$ and $i \in [k]$ it is the case that $x_i \leq \sum_{y \in S-x} y_i$, and so the filtered set $S$ is the unique solution.

Let me demonstrate this solution using your example $2,3,4,5,7,8,9,10$. Only 4 prime factors appear here (2,3,5,7), and converting $2^x3^y5^z7^w$ to the vector $xyzw$, we obtain the following vectors:
$$
\begin{align*}
2 &= 1000 \\ 3 &= 0100 \\ 4 &= 2000 \\ 5 &= 0010 \\
7 &= 0001 \\ 8 &= 3000 \\ 9 &= 0200 \\ 10 &= 1010
\end{align*}
$$

We remove 7 due to the 4th coordinate. We then remove 9 due to the 2nd coordinate. We then remove 3 due to the 2nd coordinate. We cannot remove any more numbers, and so are left with the answer 2,4,5,8,10.

The challenge is to implement this greedy algorithm efficiently, which you can do by maintaining the sum of all elements left in the set, and using several priority queues (though perhaps there is a better solution). Details left to you.


CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof

Note: The notations and definitions used below are borrowed from the third edition of the book.

To answer this question, first, observe that if $(u,v) \notin E$, then by flow definition,

$$f(u,v) = f'(u,v) = (f \uparrow f')(u,v) = 0 \, .$$

Furthermore, since $f'(v,u) \le c_f(u,v) = f(u,v)$, it is obtained that $f'(v,u) = 0$. This simply implies that $\forall (u,v) \notin E$,

$$(f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) = 0 \, .$$

Therefore, the definition of augmented flow can be generalized for all $(u,v) \in V \times V$ to be as follows:

$$ (f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) \, .$$

The rest of the proof follows from this observation which, of course, is not explicitly explained in the text.

P.S. Please note that the formal definition of flow in the third edition of the book is significantly different from that in the second edition. In particular, in the second edition, there is a flow property named skew symmetry that requires $f(u,v) = - f(v,u), \forall u,v \in V$. This property has been removed in the third edition due to the assumptions that $(v,u) \notin E$ if $(u,v) \in E$ and $f(v,u) = 0$ if $(v,u) \notin E$. Because of this, the definitions of flow conservation in two editions are also different. Lots of such confusions, in fact, come from this change of definition that is presumably intended to simplify the proofs, but turned out being more perplexing. I personally would rather to stick to the second edition of the book for this particular chapter.


How many operations of flipping all brackets on a substring of a string of brackets are needed to make the string 'correct'?

The DP suggested in the comments by Yuval Filmus indeed works: we can solve the problem in $\mathcal{O}(n^{2})$ by DP.

First note that we may assume that intervals are not allowed to overlap. Take any two overlapping intervals $[a, b)$ and $[c, d)$. WLOG $a \leq c$. Then we can replace the two intervals with the intervals $[a, c)$ and $[\min(b, d), \max(b, d))$ that do not overlap, have shorter total length and cover exactly the same elements.

Replace opening brackets with $1$, closing brackets with $-1$. Now the problem corresponds to applying the minimum number of operations "multiply interval by $-1$" such that every prefix has nonnegative sum, and the sum over the entire array is zero.

We construct a solution left-to-right. At every position we can either start an interval, or end an active interval.

Let $DP[m][s][0]$ denote the minimum number of intervals we need to use such that every prefix sum in the first $m$ elements is nonnegative, the sum of the first $m$ elements is $s$, and we do not have an active interval. Similarly $DP[m][s][1]$ is the same value where we do have an active interval.

If the $m$th value is $1$, for $0 \leq s \leq m$ we set

$DP[m][s][0] = DP[m-1][s-1][0]$
$DP[m][s][1] = DP[m-1][s+1][1]$

Otherwise we set

$DP[m][s][0] = DP[m-1][s+1][0]$
$DP[m][s][1] = DP[m-1][s-1][1]$.

Then we end and start intervals, setting

$DP[m][s][0] = \min(DP[m][s][0], DP[m][s][1])$
$DP[m][s][1] = \min(DP[m][s][1], DP[m][s][0] + 1)$

The base case is $DP[0][0][0] = 0$, $DP[0][0][1] = 1$.

There are $\mathcal{O}(n^{2})$ states, and we do $\mathcal{O}(1)$ work to calculate each of them, therefore the algorithm runs in $\mathcal{O}(n^{2})$. The DP can be implemented to use $\mathcal{O}(n)$ memory by only storing the values of $DP$ for the current $m$.

Here is a C++ implementation of the algorithm.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}


Asymptotic analysis of a real-valued function involving complex numbers

Only the root(s) with largest magnitude matters (for generic initial conditions), and the asymptotic rate of growth is exponential in this magnitude (assuming no repeated roots). In your case this root is real, and it's a simple exercise to show that the others don't affect the asymptotic rate of growth.

A more complicated case is recurrences such as $a_n = a_{n-2}$. In this case there are two roots of largest magnitude, both complex. This corresponds to the periodic nature of the recurrence. Nevertheless, for generic initial conditions, the growth rate is $\Theta(1)$, agreeing with the first sentence above.


One possibility is to merely apply the definition. That is, we see that if $\lim_{n \to \infty} f(n) / g(n) = 0$, then $f(n) = o(g(n))$. Computing this, we have that $$\lim_{n \to \infty} f(n) / g(n) = \lim_{n \to \infty} n^n/10^{10n} = \infty \neq 0.$$ We conclude that $f(n) = o(g(n))$ does not hold.


Can there be 'dead states' in a context-free grammar?

Context-free grammars are allowed to contain unproductive rules. This is accepted, because every CFG generates the same language as some proper CFG which contains no unproductive rules, no empty string productions, and no cycles; so it is safe to assume that a CFG is proper without loss of generality.


How can an approximation ratio be less than 1?

For maximization problems, if the optimal solution is $O^*$ and the worst possible approximate solution is $O$, then the standard way is to consider $O^*/O$ as the approximation ratio. But in some text books, the ratio $O/O^*$ is considered for both minimization and maximization problems and it causes the ratio to be smaller than 1.

You may refer to Approximation Algorithm for more details.


Applicative-order languages don't support constant time array writes? If not, why not?

Skiena didn't say "applicative order", just "applicative". This is sometimes used as meaning something like "purely functional", or a language that evaluates via the application of functions as opposed to the execution of state manipulating commands. Mathematica (at least nowadays) isn't purely functional, but it does seem that it strongly encourages a purely functional style of programming.

In a purely functional language, such as Haskell, you apply functions to values and produce new values just as in mathematics. Like math, in such a language, variables are just names for values. If you say "let $x$ be $1$", then $x$ and $1$ are everywhere interchangeable. It makes no more sense to talk of "mutating" $x$ to be $2$ than it does to say to set $1$ to be $2$. For array this means that to "update" an array, you build a new array with the changes. Obviously, building an entire copy of an array except for the one entry you're changing is expensive. This is almost certainly the issue Skiena is referring to.

There is, to my knowledge, no fully satisfactory answer to this. That is, there is no purely functional data structure that provides constant time lookup and updates to all versions. You can make (externally) pure data structures that provide constant time lookup and update for the latest versions, but accesses to older versions of the array become slower. You can use monads or uniqueness types to enforce a usage of arrays that allows the compiler to use in-place updates, but this is tantamount to using an imperative approach (albeit in a controlled and contained manner). In practice, programmers in purely functional languages simply don't use arrays nearly as much as imperative programmers, and when they do use arrays, they tend to use bulk operations. If you are going to touch every element of an array anyway, then the cost of copying the array is constant per element.

While there are definitely times where the limitations of purely functional programming make efficient implementation non-obvious, most of the time it is just a matter of applying different design and implementation techniques than are typical/practical in imperative languages. Purity also affords guarantees that make many designs, optimizations, and sometimes entire technologies practical. For the first, most purely functional data structures are designed to share as much as possible. For the second, a major technique for improving performance of bulk operations is fusion which combines multiple bulk operations into one to avoid intermediates. For the last, there was an attempt to add Software Transactional Memory to C# that was given up because it relied on the programmer not using side-effecting procedures in the transactions but could not enforce this practically.


Why is memory different from a hard disk?

Because hard disks have different performance characteristics than RAM.

With hard disks, seeking is extremely slow.  Sequential reads are much faster than random-access reads.  In other words, it's much faster to read data that is stored consecutively than to store data that's scattered all around the disk.  Therefore, there are benefits to making sure your files are contiguous, as much as possible.

RAM doesn't have the same property.  With RAM, there is no penalty for "seeking".  You can pick any page and read from it, and the cost will be the same, no matter where the page is located.  For instance, reading page X and then page Y will have the same cost regardless of whether X and Y are adjacent or not.

So, you end up with different algorithms that are optimized for hardware with different performance characteristics.

Why do hard disks have this strange property?  Because they are based on a rotating piece of iron.  If you read block X on the hard disk, and next want to read block Y, but Y is on the other side of the platter, then you'll have to wait for the platter to finish rotating far enough for Y to be under the read head.  That takes time.  RAM doesn't have this property.

Interestingly, the differences are becoming less these days.  Today, SSD (solid state storage devices, based on Flash storage) are becoming a popular replacement for hard disks.  SSD's have their own performance characteristics, but they're more like RAM than like magnetic hard disks.  This means that the filesystem optimizations you'd do for a SSD-oriented filesystem are different from the ones you'd do for a hard-drive-oriented filesystem.  Many of today's filesystems were designed decades ago when magnetic hard disks were dominant, and optimize for the performance characteristics of magnetic hard disks.

Why not harden software by deliberately leaving space between buffers?

You are implicitly proposing a scheme for making software more robust against out-of-bounds errors and buffer overruns: leave plenty of unallocated space between each pair of buffers allocated on the heap.

That's not a bad idea.  It's been proposed before and studied in considerable depth.  It does add some robustness against bugs.  It can also make buffer overrun attacks harder, especially if you randomize the location of all heap buffers.  It's also relatively easy to deploy in a way that is compatible with legacy software.  So it does have some quite attractive advantages.

However, it also has some disadvantages.  It imposes some performance overhead -- not a huge amount, but enough to be a bit painful.  Why does it impose performance overhead?  Largely because it reduces spatial locality.  Consider two 16-byte allocations.  Current allocators try to pack them together into a single page.  In your scheme, we'd have to put each allocation onto its own page.  That means we have a lot more pages, which means that we get a lower TLB hit rate.

There are different variants on this scheme, with different performance implications, but they all run up against the challenge: in exchange for the robustness and security benefits, there is some non-zero performance overhead.  So that's one reason why people might not adopt it.

The other big reason is: we're using platforms and allocators that were designed decades ago.  At the time, security wasn't as critical as it is today, so this sounded like a pretty unattractive proposal: I get to implement something more complicated and fiddly, and it'll make my entire system slower?  No thanks.

Today given the magnitude of security problems we're facing, there's gradually increasing interest in these alternatives.  But they still face an uphill battle, because of the non-zero performance implications.

To learn more about academic research on this subject, read research papers on the Diehard, Dieharder, and Archipelago systems.  They discuss the design in a very accessible way and measure the performance and other costs of such a scheme.  If you're still intrigued, you can explore the literature where other researchers have explored other points in the design space to understand their implications.

Bottom line: you're not the first to think of this, and it is a pretty attractive idea, but it also comes with some significant costs.


Having read all your answers to my questions, I come to the ultimately weakest reduction for 3-$\mathrm{SAT}$

The weakest reduction is $\mathrm{NC}_0^0$. This reduction does not use even $\mathrm{NOT}$  gate. Absolutely, almost nothing at all.

Consider the very first part of the very first row in your answer here. As you mentioned there, this only needs some indexing work of the $\mathrm{DLogTime}$-constructor. It turns out that all that is needed to be done is to put $\lnot$ symbol to the soon-to-be-reduced-to formula by copying the actual input bits themselves.

In particular, consider the 10th cell $c_{10}$ of the first row, this cell is equal to $x_{10}$ i.e. the 10th bit of the actual input.

Depending on whether $x_{10}$ is 0 or 1, the corresponding clause will be:

$$ \lnot c_{10} \lor \lnot c_{10} \lor \lnot c_{10} $$

or

$$ c_{10} \lor c_{10} \lor c_{10} $$

All the $c_{10}$'s are hard-coded similarly as the rest of the constructed constant-depth circuit. The $\lnot$ or nothing (actually a dummy symbol in the soon-to-be-reduced-to formula) is copied from the actual input bit $x_{10}$.

So, the weakest reduction is $\mathrm{NC}_0^0$. It copies the input bits to some output gates of the constructed 0-depth circuit. All the other output gates of the constructed 0-depth circuit are constantly hard-coded.


How to solve this Planning Domain Definition Language (PDDL) question?

I will turn my comment into an answer.  Recall that if your state is $\{P,Q,Y,Z\}$, and an effect of an action is $\sim\!Z$ (from now on written $\neg Z$), then the new state will not contain $Z$, i.e., the state will be, if nothing else is an effect, $\{P,Q,Y\}$.

Since the question asks what the result of a sequence of actions will be, we need to solve this in the order of that sequence.  The sequence asked was
$[E,D,A,B,C]$, and the state was $\{P,Q,Y,Z\}$?  Observe that we by square brackets denote a sequence (i.e., an ordered list) and by curly brackets, an unordered set (the usual kind).

Action $E$ in state $\{P,Q,Y,Z\}$:  Precondition $Z$ is good since $Z$ is in the state.  Effect is "when $Q$, $\neg Z$".  The new state will thus be $\{P,Q,Y\}$.  We omit writing $\neg Z$ since every element not occurring in the state will be assumed to be not held.

Action $D$ in state $\{P,Q,Y\}$:  Precondition $\neg X$ is good.  Effect: "when $Q$, $X$".  Hence new state will be $\{P,Q,X,Y\}$.

Action $A$ in state $\{P,Q,X,Y\}$:  Precondition is good, $X$ is in the state.  Effect: "when $P$, $\neg X$, and $Z$".  $P$ is in the state, hence we remove $X$ and we also add $Z$.  New state is $\{P,Q,Y,Z\}$.

Action $B$ in state $\{P,Q,Y,Z\}$: Precondition $Y$ is good.  Effect "when $Z$, $\neg P$, also $\neg Y$, $\neg Z$ and $X$".  $Z$ is true, hence we lose $P$.  We also lose $Y$ and $Z$ and gain $X$.  New state is $\{Q,X\}$.

Action $C$ in state $\{Q,X\}$: Precondition is $\neg Z$, so good.  Effect: "when $P$, $\neg X$, and $Y$".  This is the first time we encounter an implication in which the antecedent $P$ is false, so we don't remove $X$.  We still add $Y$, though.  Hence the new, and final state is
$$
\{Q,X,Y\}.
$$


Can synchronous data transfer be used for transferring large data in case of computer architecture and organization?

I think that the question has no clear answer. Data can be transferred in a synchronous or asynchronous manner. Each has its own pros and cons. Synchronous communication is irrelevant for some systems, e.g., when there is no joint clock or where the distance causes too large clock skews. Both methods are capable of transferring large amounts of data. For instance, USB is kinda asynchronous, in the sense it has no clock (it uses synchronization strings to maintain synchronization) and yet it is capable of transferring large amount of data.
DMA is a mechanism within some chip that allows transferring data (small amount or large amount) without the involvement of the CPU. Within a chip most communication is synchronous (there are exceptions). However, the DMA communication might have gaps within its transmissions as the BUS might be needed for the CPU. It might depend on the exact mode of DMA operation.


Partitioning list into two parts of almost equal sum

As Yuval Filmus points out, this is an optimization version of the PARTITION problem. The problem is weakly NP-complete, so any polynomial time solution to your problem would immediately solve partition (simply check if the minimum difference between the sums of the two sets is $0$).
You can solve the problem in pseudo-polynomial time $O(nS)$, where $S$ the sum of the input integers, using dynamic programming, or in time $O(n \cdot 2^{n/2})$ using the split-and-list technique. Pick the best of the two algorithms depending on the value of $S$.
The dynamic programming algorithm is as follows.
Let $A = \{a_1, \dots, a_n\}$ be the input (multi-)set of numbers, and let $S=\sum_{a \in A} a$.
Consider a partition of $A$ into two sets $B$ and $C$, and assume w.l.o.g. that $\sum_{b \in B} b  \le \sum_{c \in C} c$ (since otherwise you can swap $B$ and $C$).
The cost (to minimize) of this partition is:
$$
\sum_{c \in C} c - \sum_{b \in B} b =
\left(S- \sum_{b \in B} b\right) - \sum_{b \in B} b
= S - 2 \sum_{b \in B} b.
$$
Showing that the problem is equivalent to finding a subset $B$ of $A$ whose sum of elements is at most $\lfloor S/2 \rfloor$ and, subject to this constraint, it is maximized.
For $i=0, \dots, n$, and $x=1,\dots,\lfloor S/2 \rfloor$, let $OPT[i,x]$ be true if and only if there exists a subset $B$ of $\{a_1, \dots, a_i\}$ with $\sum_{b \in B} b = x$.
Then $OPT[0,0]=\top$ and, for $x>0$, $OPT[0,x]=\bot$.
If $i>0$:
$$
OPT[i,x] = \begin{cases}
OPT[i-1,x] \vee OPT[i-1,x-a_i] & \mbox{if $a_i \le x$} \\
OPT[i-1,x] & \mbox{otherwise}
\end{cases}.
$$
There are $O(nS)$ values $OPT[i,x]$ and each of them can be computed in constant time (in increasing order of $i$).
The maximum value of $\sum_{b \in B} b$ is $\max \left\{ x \in \{0, \dots, \lfloor S/2 \rfloor \} \mid OPT[n, x] = \top \right\}$.


Is there a Zero-Knowledge proof for SAT?

Here is a zero-knowledge protocol for E3SAT, the variant of SAT in which each clause contains exactly three literals.
Consider an instance of E3SAT, consisting of variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$.
Prover chooses a color in $\{1,2,3,4\}$ for each of the following:

Variable literals $V(x_i), V(\lnot x_i)$ ($2n$ colors in total).
Literals appearing in clauses ($3m$ colors in total): for each clause $C_j$ and literal $\ell$ appearing in it, $C_j(\ell)$.
Three additional values $a,b,c$.

Verifier makes one of the following checks:

The colors assigned to $a,b,c$ are all different.
For a variable $x_i$, the colors assigned to $V(x_i),V(\lnot x_i),b,c$ are all different.
For a clause $C_j$ consisting of literals $\ell_1,\ell_2,\ell_3$, the colors assigned to $C_j(\ell_1),C_j(\ell_2),C_j(\ell_3),a$ are all different.
For a clause $C_j$ and a literal $\ell$ appearing in it, the colors assigned to $V(\ell),C_j(\ell)$ are different.

If the formula is satisfiable, the prover acts as follows:

It chooses random colors for $a,b,c$. We call these colors $a,b,c$, and the remaining color $d$.
If $x_i$ is assigned true then we color $V(x_i)$ by $a$ and $V(\lnot x_i)$ by $d$, otherwise we color $V(x_i)$ by $d$ and $V(\lnot x_i)$ by $a$.
For a clause $C_j$, choose a satisfied literal $\ell$, assign $C_j(\ell)$ the color $d$, and assign the other two $C_j(\ell'),C_j(\ell'')$ associated with the clause the colors $b,c$.

It is not hard to check that this satisfies all constraints checked by the verifier. Moreover, since we chose $a,b,c,d$ at random, verifier can simulate the answers on her own, and so this is a zero knowledge protocol.
Finally, suppose that all potential checks of the verifier pass. Let $a,b,c$ be the colors assigned to $a,b,c$, and let $d$ be the remaining color. For each variable $x_i$, the variable literals $V(x_i),V(\lnot x_i)$ are assigned the colors $a,d$. We extract a truth assignment as follows: if $V(x_i)$ is colored $a$ then we let $x_i$ be true, otherwise it is false. Each clause $C_j$ is colored using $b,c,d$, and so some clause literal $C_j(\ell)$ is colored $d$. The corresponding variable literal $V(\ell)$ must be colored $a$, and so it satisfies the clause.


Find amount of elements greater then number k in a BST

You can do it in $O(h)$ time only if you know some additional information at every node about the subtree rooted at that node. (Maybe @greybeard is suggesting the same in the comments). For example:
Suppose $x$ is any node in the tree, and suppose you know the number of nodes in the sub-tree rooted at $x$. Let us call this variable "x.total". Then, the following algorithm works in $O(h)$ time:
fun(root,K) // It returns the number of elements greter than K
---if (root = NULL)
------- return 0;
---if(root.value > K)
-------- return fun(root.left_child,K) + 1 + root.right_child.total
---else
-------- return fun(root.right_child,K)

The correctness of the above algorithm follows due to the fact that the given tree is a Binary Search tree (BST).
Moreover, you can maintain the extra information (i.e, x.total) for all nodes by traversing the tree only once. You can use DFS procedure for the same. Thus, the preprocessing time is only $O(n)$. And, the query time complexity would be just $O(h)$.

If you do not store any kind of extra information, then you can not do better than $O(n)$. For example: suppose the tree contains only positive elements and the query is for $K =  0$. Then, this query is the same as finding the total number of elements in the tree, which requires you to traverse every node and it essentially requires $\Omega(n)$ time.


construct a TM decides in linear time, if valid bracket

If you are not allowed to use two or more tapes then as Yuval Filmus commented you cannot solve in linear time. Otherwise you can convert the following steps into TM instructions:

 Initially input on the tape 1, the tape 2 is empty.
 Machine reads input symbols stored on the tape 1, and tape 2 is used as stack (for push/pop operations).

 1)  x = Read a symbol.
 2)  If x is '[' or '(' Then
 3)    push x and go to 1)
 4)  Else If x is ')' Then
 5)    sym = pop()
 6)    If sym != '(' Then
 7)       Reject and Halt.
 8)    Else
 9)       go to 1)
 10) Else If x is ']' Then
 11    sym = pop()
 12)   If sym != '[' Then
 13)      Reject and Halt.
 14)   Else
 15)      go to 1)
 16) Else If x is '$' Then (if end of input)
 17)   If stack is empty Then
 18)      Accept and Halt
 19)   Else
 20)      Reject and Halt
 21) Else
 22)   Reject and Halt

I think translation to a TM of this piece of code is quite tedious work.

In computability theory if you want to prove existence of a TM then informal description (or just description using one of the high-level programming languages) is enough. You may use a single tape TM model or multitape model. However, when dealing with time complexity selection of a model matters.


The Cook–Levin theorem shows how to construct a circuit of size $f(n)^{O(1)}$. I'm not sure what's the best exponent.

The opposite direction is impossible, since circuits of size 1 can compute the following language:
$$ \{ w : \text{the $|w|$th Turing machine halts on the empty input} \}. $$
More generally, circuits of size 1 can compute any language in which the answer depends only on the length of the input.


Difference between Bandwidth and Propagation Speed in computer networks?

These two terms are actually completely unrelated. Bandwidth is a way of expressing how much "stuff" you can send on a network link at a time. Think of it like a highway. If you have only one lane on the highway, then you have a bandwidth of 1 car per some unit of time (let's say seconds). So every second, only 1 car can pass through that particular segment of roadway. But if you widen the road to have 4 lanes, then you can get 4 cars per second. It's literally the width of the frequency band you can send data over.

Now propagation speed is how quickly something can propagate, or move a certain distance. Consider the cars again. If they are driving 60 mph, then then it will take one hour to travel 60 miles. Regardless of how many lanes are on the highway, each car will still take one hour to travel that whole distance. Cars in the front and the back of each lane will take one hour. By the way, the reverse is true as well: increasing the speed of each car has no affect on how many you can fit side by side on any stretch of road.


How Is a Computer Able to Store and Quickly Manipulate All the Data Required For A Computer Display?

You're confusing the number of possible values that a pixel can display with the amount of data being shown at any given instance. The number you give is the number of possible pixel states that your display can be in, multiplied by the number of pixels, which isn't really a meaningful number.

(EDIT: As Mehrdad and phihag point out, I'd incorrectly assumed you'd given the number of possible images. That number is actually $(256 \times 256 \times 256) ^ {1920 \times 1080}$, which is much larger than your number.)

The important detail is, at any time, a pixel is only in one state.

There are 256 possible values for each pixel, but we only are in one of them at any given time.

Any number between 0 and 255 can be encoded using 8-bits, just the same way you can write any number between 0 and 999999 using only 6 decimal digits. So there are 24 bits per pixel, or 3 bytes per pixel.

So 3*1920*1080=6220800 bytes, or just over 6MB.

Think of it like this, you as a person can verbally list all the digits in some 20-digit number, but you can't possibly list every 20-digit number. Your monitor could never in its lifetime display all possible images, but it certainly display one of those images.


What is $Prop$ in the calculus of constructions?

In traditional Martin-Löf type theory there is no distinction between types and propositions. This goes under the slogan "propositions as types". But there are sometimes reasons for distinguishing them. CoC does precisely that.

There are many variants of CoC, but most would have
$$\mathsf{Prop} : \mathsf{Type}$$
but not $\mathsf{Type} : \mathsf{Prop}$. Another difference shows up when we have infinitely many type universes and make $\mathsf{Prop}$ impredicative (this is what Coq does). Concretely, consider a variant of CoC where we have $\mathsf{Prop}$ and infinitely many type universes $\mathsf{Type}_1$, $\mathsf{Type}_2$, $\mathsf{Type}_3$ with
\begin{align*}
\mathsf{Prop} &: \mathsf{Type}_1 \\
\mathsf{Type}_1 &: \mathsf{Type}_2 \\
\mathsf{Type}_2 &: \mathsf{Type}_3 \\
&\vdots
\end{align*}
The formation rule for $\prod$ has to explain how to form $\prod_{x : A} B(x)$ when $A$ is either a proposition or a type, and $B(x)$ is either a proposition or a type. There are four combinations:

$$\frac{A : \mathsf{Prop} \qquad x : A \vdash B(x) : \mathsf{Prop}}
     {\prod_{x : A} B(x) : \mathsf{Prop}}$$
$$\frac{A : \mathsf{Type}_i \qquad x : A \vdash B(x) : \mathsf{Prop}}
     {\prod_{x : A} B(x) : \mathsf{Prop}}$$
$$\frac{A : \mathsf{Prop} \qquad x : A \vdash B(x) : \mathsf{Type}_i}
     {\prod_{x : A} B(x) : \mathsf{Type}_i}$$
$$\frac{A : \mathsf{Type}_i \qquad x : A \vdash B(x) : \mathsf{Type}_j}
     {\prod_{x : A} B(x) : \mathsf{Type}_{\max(i,j)}}$$

The most interesting is the difference between the second and the fourth case. The fourth rules says that if $A$ is in the $i$-th universe and $B(x)$ is in the $j$-th universe, then the product is in the $\max(i,j)$-th universe. But the second rule is telling us that $\mathsf{Prop}$ is not just "one more universe at the bottom", because $\prod_{x : A} B(x)$ lands in $\mathsf{Prop}$ as soon as $B(x)$ does, no matter how big $A$ is. This is impredicative because it allows us to define elements of $\mathsf{Prop}$ by quantifying over $\mathsf{Prop}$ itself.

A concrete example would be
$$\prod_{A : \mathsf{Type}_1} A \to A$$
versus
$$\prod_{A : \mathsf{Prop}} A \to A$$
The first product lives in $\mathsf{Type}_2$, but the second one is in $\mathsf{Prop}$ (and not in $\mathsf{Type}_1$, even though we are quantifying over an element of $\mathsf{Type}_1$). In particular, this means that one of the possible values for $A$ is $\prod_{A : \mathsf{Prop}} A \to A$ itself.


Finding all paths with lengths in a fixed interval in sparse graphs

Assuming a directed graph.

Paths of length $1$ are simply the edges.

paths of length $i+1$:

Unite on all nodes $v \in V$ {concatenate all paths of length $i$ that end with $v$ with all paths of length $1$ that start with $v$}.

repeat for $i=1$ to $7$.

Note that this method avoids redundancies, so you don't need to check for them.


Iterated multiplication of permutation matrices

Ben Rossman showed that any unbounded fan-in depth $d$ circuit for your problem has size at least $n^{\Omega(m^{1/2d})}$. Conversely, a simple recursive construction gives an unbounded fan-in depth $d$ formula of size $n^{O(m^{1/d})}$.


how to construct a formula with an opposite SAT value of another one

The existence of such an algorithm would imply co-NP is included in NP which is unlikely

Checking that a formula is satisfiable: NP, generate proof by providing a solution

Checking that a formula is unsafisfiable: co-NP, generating proof can be harder, in classical proof systems the shortest proof of unsatisfiability of an arbitrary formula can be exponentially long

The algorithm you are looking for would mean all problems in co-NP have a short refutation, by providing a solution to the "opposite" formula. Therefore we are unaware of the existence of such an algorithm.


importance of alternate storage in external sort

I believe the alternation is done to ensure that the data is split as closely as possible into equal-sized subsets, which minimizes the time spent on each later pass.


The value of $i$ at the $k$'th iteration (starting from zero) is $i_k := 2^k$. The inner loop runs $i_k$ times, for a total of $i_0 + i_1 + \cdots + i_K$, where $K$ is the largest number such that $i_K \leq n$, that is $\lfloor \log_2 n \rfloor$. Therefore the running time is
$$
\sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k = 2^{\lfloor \log_2 n \rfloor + 1} - 1 = \Theta(n).
$$


How do I show that whether a PDA accepts some string w is decidable? or undecidable?

Given a PDA and a string $w$, there are several algorithms that decide whether the PDA accepts $w$. In fact, for a fixed PDA, such algorithms run in time $O(|w|^3)$ or less. The most well-known algorithm is the CYK algorithm. Although CYK expects the language in the form of a context-free grammar rather than in the form of a PDA, there is an algorithm that converts a PDA to a context-free grammar generating the same language.

I expect every decent textbook on automata theory to contain a proof that the acceptance problem for PDAs (given a PDA and a string, determine whether it accepts the string) is decidable, say along the lines above.


How can I check if $n >m$ in $a^n b a^m$?

Start with placing tape over $b$, then go to the rightmost $a$, put blank, go back to $b$ and delete the rightmost $a$.
Every time you scratch out $a$s on both sides, $n - m$ does not change until one side is blank.
Check if the left side is not empty, delete $b$ (and if it is required, go back to the beginning of the tape) and accept, otherwise reject.


All regular languages have LL(1) grammars.  To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar.  This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or one produces ε and has $ as a lookahead token.  Consequently, all regular languages are also LR(1), since any LL(1) grammar is LR(1).  Additionally, using an important result from this paper, you can show that any LR(1) language has an SLR(1) grammar, meaning that any regular language has an SLR(1) grammar.

However, the regular languages are not all LR(0).  The LR(0) languages have very specific properties - in particular, they must be prefix-free.  Thus the regular language {a, aa} is not LR(0), though it's clearly regular (regex a|(aa)).  However, the LR(0) languages are not properly contained within the regular languages; this grammar for { 0n21n | n ≥ 1 } is LR(0), but the language is not regular:

S -> E
E -> 0E1 | 2

Hope this helps!