Turing Machines: Arbitrary alphabet equivalence with binary alphabet

I am answering the question "Can Turing Machines with binary alphabet decide the same languages as Turing Machines with 3 or more alphabet symbols?"

Now, on the one hand, it's not well-defined what happens if you take a string with three different alphabet symbols and give it to a TM that only is designed to see a binary alphabet on the tape. So in that sense, a three-symbol Turing Machine can decide languages with these strings, while the two-symbol machine isn't allowed to read them. (For instance, if the language has "a", "b", and "c" in it, then there is no TM with a binary alphabet that reads these strings.)

But you might ask this question instead. Let's consider only languages whose strings have two symbols, in order to give a fair comparison between the two-symbol TM and the three-symbol TM. Now, can the three-symbol TM decide more of these languages, simply because it can write more types of symbols on the tape while it is computing?

The answer here is "no". The idea is that we have to take any three-symbol Turing Machine and show that there is a two-symbol TM that essentially takes the same "steps" and accepts whenever the original one accepts, etc. Just as a hint, the idea here is to make a TM with a modified transition table so that it can "act like" it's writing the third symbol down, even though it's only using two symbols.


Way to solve 5-dimentional Linear assignment problem

If you had as much people as number of people in your clusters (each people must have a dot in each cluster) then maybe you could hope for some divide-and-conquer strategy with polynomial runtime, because of greedy-like regularities. For example, in 1D and with 3 people only, after sorting the points along the axis a greedy sweeping algorithm yields an optimal solution ; with some tweaks maybe this kind of ideas could work in higher dimensions. But with some people who can not be part of a specific cluster, this doesn't seem to work anymore.
If I were you, I'd look for approximation algorithms (good ones are known for the 3d matching). Maybe some of them can yield good approximation factors with your problem's structure.


What kind of order is binary tree ancestry?

Your condition is almost equivalent to the statement that the partial order is a tree.

Consider the following two conditions on a partial order $\ge$:

C1: There exists a top element $r$ (also called "the root") such that $\forall x . r \ge x$.

C2: For all $x,y,z$, $x \ge z \land y \ge z$ implies $x \ge y \lor y \ge x$ (this is your condition).

Notice that every tree satisfies both conditions (i.e., its isAncestor partial order satisfies both of these conditions).

Moreover, I claim that every partial order that satisfies both of these conditions has a Hasse diagram that is a tree.

Why?  Well, if C1 is true, then C2 is equivalent to

C3: For all $v$, there is a single unique path from $v$ to the root $r$ in the Hasse diagram of $\ge$.

This is easy to prove by looking at the contrapositive: if there were two incomparable paths from $v$ to the root, then we could find a violation of C2 (let $x,y$ be two incomparable elements, each on one of the paths).

And if C1 and C3 is true, then the Hasse diagram is a tree.

Bottom line: there's no particular reason to expect any special name for your property.  Your property almost characterizes trees, once we take into account the correspondence between a partial order and its Hasse diagram (which is a DAG).


Is there such a problem as b-Matching with different b values?

I'm not sure if it's a standard problem, but it seems this problem is described in Solving the Many to Many assignment problem by improving the Kuhn–Munkres algorithm with backtracking.
(the other closest things I found are https://en.wikipedia.org/wiki/Generalized_assignment_problem and https://link.springer.com/content/pdf/10.1007/BF02190106.pdf, but they are talking about one-to-many assignments).
Anyway, you can solve it using maximum flow. For $b=1$ (usual matching) you can check these slides, namely this picture:

I.e. we create auxiliary vertices $s$ and $t$, create edges $(s, u)$ for all $u$ in the left part and $(v, t)$ for all $v$ in the right part. All edges have capacity one. By solving maximum flow on this graph, you'll find maximum matching (Note: you have to find an integral solution, i.e. where flow through each edge is either 1 or 0, but standard maximum flow algorithms will do that).
For $b>1$ the graph is the same. The difference is that all edges $(s,u)$ have capacity $b_L$ and $(v,t)$ have capacity $b_R$.
If your edges have weights, then you can negate edge weights and solve min-cost max-flow on this graph.


Why do I get different results from two calculation methods?


Does dependent type checkers need to store lambda parameter type in their core language?

In general, type inference for dependent types is undecidable. This means that when checking a function, we need some way to know what type its argument has.

In the case of Idris, they simply annotate lambdas with parameter types. This is very common in type theory, since it makes your type system syntax directed in a very simple way. When you do this, you can usually view the typing judgment as having the type as an output parameter (i.e. given the input term, you can determine its type).

I don't know what MiniAgda does in particular, but the other main way is to treat the type as an input to the checking judgment. So in this case, you don't need to store the type of the function in the AST, but when typechecking, you will use the context in some way to get the type of the function (i.e. from an annotation).

Generally this is done using bidirectional typechecking. This paper and this post both give excellent overviews of how this can be done in practice.


How to determine enumerability after applying Rice's theorem?

You can use the fact that if $L$ is undecidable and $\overline{L}$ is enumerable then $L$ is not enumerable (since if both $L$ and $\overline{L}$ are enumerable, then $L$ is decidable). In order to determine whether an undecidable language is enumerable or not, you can try to construct an enumerator for the language or its complement.


About showing algorithmic gap instance for the Goemans-Williamson SDP

A graph for which $Alg(G) = \beta OPT(G)$ is, by definition, a graph on which the algorithm has approximation ratio $\beta$. You can use this insight to answer the first question.

As to your second question, suppose that $Alg(G) \leq (\alpha_{GW}+\epsilon) OPT(G)$. Since $Alg(G) \geq \alpha_{GW} SDP(G)$, we deduce that
$$
\alpha_{GW} SDP(G) \leq Alg(G) \leq (\alpha_{GW}+\epsilon) OPT(G).
$$
Therefore $SDP(G) \leq (1+O(\epsilon)) OPT(G)$.


Difference between algorithm and procedure

Let me cite the classic -- D.E. Knuth's "The Art of Computer Programming", 3ed (1997).

Some terminology first.

  The modern meaning for algorithm is quite similar to that of recipe, process, method, technique, procedure, routine, rigmarole, except that the word "algorithm" connotes something just a little different.

Note: the bold face is mine.
Then Knuth goes on:

  A procedure that has all of the characteristics of an algorithm except that it possibly lacks finiteness may be called a computational method.

It turns out that one of the earliest examples of a computational method belongs to Euclid:

  Euclid originally presented not only algorithm for the greatest common divisor of numbers, but also a very similar geometrical construction for the "greatest common measure" of the lengths of two line segments; this is a computational method that does not terminate if the given lengths are incommensurable. Another example of a nonterminating computational method is a reactive process, which continually interacts with its environment.

It seems that by the second case Knuth meant operating systems, web-servers and so on, i.e. the programs that are supposed to run "forever", but do something useful along the way.


Try these slides http://www.cs.bgu.ac.il/~frankel/HonoraryDay09/Slides/AmirPnueli.pdf or these ones http://www.cs.rice.edu/~vardi/papers/fmco06.ps.gz.

Also try googling "From Verification to Synthesis" and look at the work of Moshe Vardi and Orna Kupferman.


Is there a generic algorithm to optimally combine elements by some arbitrary scoring method?

In your formulation, you need to compute score of each reduced list individually. So, if there are 2^(n-1) possible reduced lists, you need to perform at least O(2^n) operations.

Unless you can figure out some restrictions or relations between scores of related lists (such as "longer lists always have better scores"), it will remain O(2^n) problem.


Threads
On a platform that supports multi-threading the threads run in parallel.
That means that multiple threads can run at the same time.
This depends on the numbers of cores the CPU makes available.
If the programmer insists on running more threads than the CPU has cores then the threads will be time-sliced.
How much time each thread gets depends on the priority of that thread.
A thread can also choose to yield, which means that it will transfer execution time to another thread before its time slice is up.
If a thread does not yield the scheduler (which is part of the operating system) will pause the thread and force another thread to run.

Interrupt handler
An interrupt handler interrupts the main program. That means that the state of the thread is saved and execution is paused.
The interrupt handler is executed and when the interrupt handler yields the state of the main program is restored and execution of the main program resumes.

In many systems the interrupt handler is assigned a standard interruption schedule, e.g. 50 times a second.
The interrupt is always given preference over the main program, so if the interrupt takes up a lot of time the main program will get very little or no time to run. The interrupt gets scheduled no matter what. The main program gets whatever time is left over.
An interrupt handler is not subject to a scheduler, although possibly the interrupt can be interrupted by another interrupt.

Time slicing
In contrast, threads (insofar as threads outnumber CPU cores) are time sliced. Every thread gets the same amount of time. If there is a high priority thread it may get more time or get scheduled more often, but the scheduler makes sure every thread does get a time slot now and then.

Interrupts don't play nice
Because an interrupt handler will get prioritized over the main execution it is unwise to treat it like a thread. If you do heavy calculation in an interrupt handler your main program will never run!
This is made worse by the fact that interrupts are usually scheduled to run many times a second.

Alternatives
There is an alternative to abusing the interrupt handler for multi-threading.
You can use fibers on Arduino.
Fibers are cooperative threads, that means that a single thread will run until it yields.
After a yield the next fiber in line will run.
As long as all fibers yield in a cooperative manner this works very much like real pre-emptive threads.
If one fiber does not yield, none of the other fibers will get any running time.
This is the multi-tasking mechanism that was used in Windows 3.x

Just to make things confusing libraries that support this behavior talk about threading, not fibers.
Note that threading is impossible on Arduino, so these misnamed 'threads' are really fibers.


Why is testing if x > y primitive recursive?

Hint: One possible approach is to compose the functions $x\dot{-}y = \max(x-y,0)$ and $\delta(z) = \begin{cases} 0 & z=0, \\ 1 & z>0 \end{cases}$.


Complexity for merging 3 sorted arrays using this specific algorithtm

Assuming that you're using some random-access model of computation (i.e., not an ordinary Turing machine) and that comparisons can be done in constant time, the algorithm you describe is linear. Each element of the final array is produced by comparing at most three elements of the original arrays, so each element of the output is produced in constant time.

Perhaps you misunderstood the question and they were actually asking about something else? Perhaps they mis-stated their question and they were trying to ask about the complexity of three-way mergesort (sorting an array by splitting into three parts, recursively sorting the parts, then merging them)? Perhaps they were just wrong.


Showing that a bijection preserves homomorphism

The symbol $0^{\mathbb R}$ is a 0-ary function symbol, and you need to handle it as well. Since $-0 = 0$, this is not a problem.
As for $+^{\mathbb R}$, high school arithmetic shows that
$$
-(x+y) = (-x) + (-y).
$$
More generally, $-$ is an automorphism of any Abelian group. An Abelian group is a set together with a binary operator $+$, a unary operator $-$, and a constant $0$ such that:

$x+y = y+x$.
$(x+y)+z = x+(y+z)$.
$x+0 = x$.
$x+(-x) = 0$.

The mapping $x \mapsto -x$ is an automorphism. Notice that

For all $x$, $(-x)+x=x+(-x)=0$.
For all $x$, $(-x)+(-(-x))=0$.
Hence $x = x+0 = x+((-x)+(-(-x))) = (x+(-x))+(-(-x)) = 0+(-(-x)) = (-(-x))+0 = -(-x)$.

Therefore $-$ is an involution. In particular, if $-x=-y$ then $x=-(-x)=-(-y)=y$, so that $-$ is one-to-one. Since $-(-x)=x$, it is also onto.
Since $0 = 0 + (-0) = (-0) + 0 = -0$, we see that $-$ maps $0$ to itself.
Since $-(-x) = -(-x)$, we see that $-$ maps $-$ to itself.
Finally,
$$
(x+y)+((-x)+(-y)) = (y+x)+((-x)+(-y)) = ((y+x)+(-x))+(-y) = (y+(x+(-x)))+(-y) = (y+0)+(-y) = y+(-y) = 0.
$$
Therefore
$$
-(x+y) = (-(x+y)) + 0 = (-(x+y)) + ((x+y)+((-x)+(-y))) = ((-(x+y))+(x+y)) + ((-x)+(-y)) = ((x+y)+(-(x+y))) + ((-x)+(-y)) = 0 + ((-x)+(-y)) = ((-x)+(-y)) + 0 = (-x)+(-y).
$$
This shows that $-$ maps $+$ to itself.


Does the order in which qubits are measured matter in quantum computing?

No, the order doesn't matter.

Proofs

Algebra. Take an input state $\sum_k c_k |k_0 k_1 k_2 ...\rangle$. Apply the definition of measurement from your textbook to it. Compute the expression for the probabilities and outputs of each case when measuring qubit 0 then qubit 1. Do the same for measuring qubit 1 then qubit 0. Notice that the two expressions are equal. Generalize.
Circuit moves. Measurement is equivalent to a CNOT gate from the target qubit onto an ancilla qubit that you simply don't use for anything else:

So if you think you can change the outcome statistics by reordering measurements, you should think you can do the same without involving measurements at all (until a simultaneous measurement of all qubits at the end of the circuit). All you should need is independent CNOTs. But clearly independent CNOTs can be re-ordered.
Play. For me, the fact that ordering doesn't matter wasn't proven so much as experienced. I dragged gates around in Quirk and noticed that measurement is easily the most boring operation. All measurement does is throw away off-diagonal density matrix elements. Even for the target qubit, measurement doesn't change the computational basis probabilities.


What exactly is the difference between supervised and unsupervised learning?

The difference is that in supervised learning the "categories", "classes" or "labels" are known. In unsupervised learning, they are not, and the learning process attempts to find appropriate "categories". In both kinds of learning all parameters are considered to determine which are most appropriate to perform the classification.

Whether you chose supervised or unsupervised should be based on whether or not you know what the "categories" of your data are. If you know, use supervised learning. If you do not know, then use unsupervised.

As you have a large number of parameters and you do not know which ones are relevant, you could use something like principle component analysis to help determine the relevant ones.


Finding the Entropy of a random experiment with probability of $\frac{1}{3}$

Your formula is totally inapplicable in computer randomness harvesting.  I think that people use it because it's easy to write down.  Even then, it's not really usable - what's i exactly?  For any non trivial application, there are correlations.  Try using this formula for the English language. No you can't say there are just 26 letters as they are hugely correlated. There are two, three, four letter combinations, and then there are words and sentences that have lexological and grammatical structure. I don't know what you do with full stops.  The entropy rate will very much depend on who wrote the words and about what.  If you try the Shannon formula in it's most simplistic typical use case, "1111111111...0000000000..." has exactly 1 bit/bit of entropy. Clearly it doesn't.

Entropy harvesting by a computer kernel consists of sucking up hardware device interrupts including keyboard presses.  Non of this is uncorrelated.  The official cryptographic term is non IID (non independent and identically distributed). And for measurement of such non IID entropy,  there is no set standard. The best we have currently is either direct compression, or the NIST SP800-90B_Entropy Assessment tools (which also include compression as one of the tests). They may have been written by a chap using up his spare time.

Is von Neumann's randomness in sin quote no longer applicable? is a currently open question  featuring such entropy measurements.  So essentially coin toss randomness is completely different to operating system randomness.


How are games like chess provably harder than NP?

The fault lies in this statement:

  So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win.

The second sentence might be right, but it might not.  Perhaps there is a cleverer, faster way that the verifier can check a certificate, or a cleverer format for the certificate that makes it easy to check.  How do we know that's impossible?  We don't.  That would need proof.

The argument has made an assumption about how a verifier "would have to" behave, without substantiating or proving that assumption.  This is basically an argument from failure of creativity: "I can't think of any other strategy a verifier could plausibly use, so there must not exist any valid strategy".  Needless to say, this is not a persuasive form of argument.

For instance, let me give you an example.  Suppose we replace "generalized chess" by "generalized tic-tac-toe", which works as follows: we have a nxn game board, and the first person to get three in a row wins.  Try working through the same argument.  It's tempting to draw the same conclusion, that generalized tic-tac-toe is NP-hard.  But there are reasons to doubt that conclusion: for instance, this form of generalized tic-tac-toe is always a first-player win when you start from the empty board, for all $n>3$.

There are better examples.  In particular, there are games where there are in fact polynomial-time algorithms to play optimally, but the algorithm/strategy is not at all obvious, and if you weren't already aware of it, you might be inclined to be persuaded by the above reasoning that the game is NP-hard.  Examples include Nim, Brussels Sprouts, and Wythoff's game.  This illustrates that the line of reasoning can't possibly be right -- it leads you to draw conclusions that are false.


How to find a Deterministic PDA for an intersection of languages

Your conjecture is right. $L$ is context-free, but not deterministic context-free.

To see that it is context-free, take a repaired verion of the grammar from @Raphael's comment: $S \rightarrow aSbS ~|~ bSaS ~|~ aSbSbS ~|~ bSaSbS ~|~ bSbSaS ~|~ \epsilon$.

Now, assume there is a DPDA $A$ that accepts $L$, and consider words of the form $b^na^m$.

Since the set of suffixes that complete $b^n$ to a word in $L$ differs for each $n$ and $A$ is a DPDA, we can conclude that after reading $b^n$, $n$ larger than some threshold $n_0$, $A$ will be in a state $q_n$ with stack contents of the form $\gamma' \gamma^{i_n} \gamma_n$ and the size of all $\gamma_n$ is bounded by a constant.

Now we group the numbers $n>n_0$ into equivalence classes, based on $q_n$ and $\gamma_n$. Since there are only finitely many equivalence classes, at least one of the equivalence classes wil contain infinitely many values. In the following, we only consider values from this equivalence class $C$.

Now assume, there is $n_1 \in C$, so that when reading $a^{n_1}$ $A$ will go from stack $\gamma'\gamma^{i_{n_1}}\gamma_{n}$ and state $q_n$ to stack $\gamma'\gamma\gamma_{n_1}'$ and state $q_{n_1}'$ without looking at $\gamma'$. Since $b^{n_1}a^{n_1}\in L$, $q_{n_1}$ is accepting. However, since $A$ did not look at $\gamma'$, it will perform the same computation, if it starts reading $a^{n_1}$ with stack contents $\gamma'\gamma^{i_{n_2}}\gamma_n$, $i_{n_2}>i_{n_1}$. By the infiniteness of $C$, it contains $n_2>n_1$ with $i_{n_2}>i_{n_1}$. Thus $A$ would accept $b^{n_2}a^{n_1} \notin L$. So, such an $n_1$ can not be in $C$.

From the previous observation, we can conclude that for each $n_i\in C$ there is a value $n_i'<n_i$, so that after reading $b^{n_i}a^{n_i'}$, $A$ is in a state $q_{n_i}'$ and $A$'s stack contains $\gamma'$. Since $C$ contains infinitely many values $n_i$, we can find $n_1<n_2\in C$ so that $q_{n_1}' = q_{n_2}'$. Now we distinguish 2 cases:

If $n_1-n_1' > n_2-n_2'$, $b^{n_1}a^{n_1'+(n_2-n_2')} \notin L$, but since $A$ can not distinguish, if it has read $b^{n_1}a^{n_1'}$ or $b^{n_2}a^{n_2'}$ and $b^{n_2}a^{n_2'+(n_2-n_2')} \in L$, $A$ can not handle both words correctly.
If $n_1-n_1' \leq n_2-n_2'$, $b^{n_1}a^{n_1'+(n_2-n_2')+n_2} \notin L$, while $b^{n_2}a^{n_2'+(n_2-n_2')+n_2} \in L$, and as in the other case $A$ can not distinguish them.

Thus, such an $A$ can not exist.


Variant of (WEAK) PARTITION with 2 distinct solutions

No such reduction is likely to exist (unless P=NP).  In particular, there's a pseudo-polynomial time algorithm for your problem, so your problem isn't strongly NP-hard (unless P=NP).

The algorithm uses dynamic programming and is a straightforward modification of the dynamic programming algorithm for PARTITION.  Define $f(j,y,z)$ to be 1 if there exists two non-zero disjoint vectors $x,x'$ of the required form such that

$$\sum_{i=1}^j x_i a_i = y, \sum_{i=1}^j x'_i a_i = z.$$

Otherwise, $f(j,y,z)=0$.  Also define $g(j,y)$ to be 1 if there exists a non-zero vector $x$ such that $\sum_{i=1}^j x_i a_i = y$, or 0 otherwise.

Note that $f,g$ satisfy the following recurrence relations:

$$\begin{align*}
f(j,y,z) = &f(j-1,y,z) \lor f(j-1,y-a_j,z) \lor f(j-1,y+a_j,z) \lor f(j-1,y,z-a_j)\\
&\lor f(j-1,y,z+a_j) \lor (g(j-1,y) \land z=\pm a_j) \lor (g(j-1,z) \land y=\pm a_j).\\
g(j,y) = &g(j-1,y-a_j) \lor g(j-1,y+a_j) \lor g(j-1,y) \lor (y=\pm a_j).\end{align*}$$

The base cases are $f(0,y,z)=0$ and $g(0,y)=0$ for all $y,z$.

With this recurrence, evaluate $f(j,y,z)$ and $g(j,y)$ for all $0 \le j \le n$ and all $y,z$ satisfying $|y|,|z| \le a_1 + \dots + a_n$.  Each such value can be computed in $O(1)$ time using memoization / dynamic programming.

Finally, look at the value of $f(n,0,0)$ that you computed.  If $f(n,0,0)=1$, then there is a solution to your problem (i.e., there exists two disjoint vectors $x,x'$ that each represent two disjoint weak partitions).

What's the running time of the algorithm? If the inputs are represented in unary, the number of $f$-values we compute is polynomial in the size of the input, and each $f$-value can be computed in $O(1)$ time using the recurrence relation above.  It follows that this dynamic programming algorithm runs in polynomial time, if the inputs are provided  in unary.


How does the runtime of the Ukkonen's algorithm depend on the alphabet size?

As @jogojapan mentions in the comments, hasing generally is only amortized $O(1)$, so you would only get amortized bounds for the algorithm. However, I think you do not even get these: In order to get amortized $O(1)$ hashing, the hash tables have to be of size $\Omega(\Sigma)$, so you still have $\Theta(m\Sigma)$ space (and the same time requirement for initialization).

What's more, in practice the time for setting up all these hash tables will be much higher than the time to set up arrays.

You might fare better with using a global hash table that is indexed with (node, character)-pairs, but at least the "only amortized" argument will remain.


Is there a generally agreed short notation for "a points to b"

The problem with your question is that pointers and pointers semantics
may vary significantly from language to language. Even your question
is ambiguous. So you are asking a question about notation, i.e., about
syntax, which is largely a matter of arbitrary convention, but it is
not even clear what is the semantics intended by your question.

You apparently use as synonyms "a points to b", "a is a pointer to b",
"a -> b". But I am not sure what is the meaning and context. Does it
assert that a is actually pointing to b (descriptive meaning) or
does it modify the data so that a is now pointing to b (imperative
meaning). Then what is b, or what can b be. Is it the location of
some value, or is it the value of whatever is pointed by a. Is it
intended to be part of a programming language syntax, or of the
metalanguage used to discuss about programs.

If you have a -> b and c -> b, does it imply that a = c. Furthermore, if a and c are pointers, what is the meaning of
a = c? See for example "shallow and deep equality".

Actually all this is often an issue of designation of container and
content. A pointer is a designation for a container (a memory
location, for example), and the content of that container may vary.
But the content may also include container designation.

One major problem is that notations are often ambiguous as they often
do not clearly distinguish between container and content, often implicitly
casting one into the other.

If you consider a variable, say an integer variable x in some
programmning language, this variable is actually a container where you
can change the content (which is supposed to be an integer). But,
within the scope of its declaration, x will always be the same
container. An integer variable is actually a pointer constant: a
location designator.

Then, can you write x -> 3 to indicate that x denotes a pointer
constant toward a location containing the value 3?

Or is the arrow supposed to point on the right to whatever container
is "designated" by the expression on the left. But if you have a
pointer constant (i.e. a pointer value) on the left, what is the
meaning of the notation.

Now, you can have pointer variables, which may contain a
container. They can appear through explicit declaration, or via other
mechanism such as parameter passing by reference.

When sharing a meal with other people, you can ask for the bottle or
for the wine. It will mean the same. But in programming context, more
precision may be needed.

So my first reaction to your question is: Could you be more precise
about the semantics you intend to express, before you suggest agreeing
on a standard notation?

Another minor point is that, while asking your question, you seem to
suggest that a double shafted arrow => would be better than a single
shafted on ->. But you do not give any hint as to why it might be
better. This makes me uneasy, especially wen I am not even sure of
what you want to talk about, and in what context.

Since this is supposed to be an answer rather than further questions,
I would suggest that the lack of a standard may well come from the
fact that programming languages vary significantly in their use of
pointers, and on the semantics attached to various constructs using
pointers. We can hardly standardize notation when what is to be denoted is
not itself standardized.

Hence, our only recourse is to choose for ourselves a notation that is intuitive and
consistent in its intended context, and define it precisely together
with the associated semantics. I insist on consistency since there are
many things you may want to do with pointers, and it is important
that the notations for each remain intuitive, and that they combine
naturally and consistently. The issue of equality is an example.


Dual-pivot Quicksort reference implementation?

I tried to do exactly such a comparison in my master thesis, which thus naturally includes pseudo-code of “basic” versions of several dual-pivot Quicksorts (there is a list of them on page 9).

Here is my basic implementation of Yaroslavskiy's algorithm (the dual-pivot scheme that is used in Java 7):

void sort(int[] A, int left, int right) {
    if (right > left) {
        // Choose outermost elements as pivots
        if (A[left] > A[right]) swap(A, left, right);
        int p = A[left], q = A[right];

        // Partition A according to invariant below
        int l = left + 1, g = right - 1, k = l;
        while (k <= g) {
            if (A[k] < p) {
                swap(A, k, l);
                ++l;
            } else if (A[k] >= q) {
                while (A[g] > q && k < g) --g;
                swap(A, k, g);
                --g;
                if (A[k] < p) {
                    swap(A, k, l);
                    ++l;
                }
            }
            ++k;
        }
        --l; ++g;

        // Swap pivots to final place
        swap(A, left, l); swap(A, right, g);

        // Recursively sort partitions
        sort(A, left, l - 1);
        sort(A, l + 1, g - 1);
        sort(A, g + 1, right);
    }
}

void swap(int[] A, int i, int j) {
    final int tmp = A[i]; A[i] = A[j]; A[j] = tmp;
}

The partitioning loop maintains the following invariant:

(Initially, the “?”-area is the whole array, at the end it is gone; the indices are moved in the direction indicated by the arrays, so $\ell$ and $k$ start at the left, $g$ at the right end of $A$.)

I did a mathematical average case analysis for these algorithms to determine the expected number of key comparisons, element swaps and also instruction counts for some specific low-level implementations (in Java Bytecode and MMIX, an RISC assembly language).

The main result is that Yaroslavskiy's algorithm uses $1.9n \ln n + O(n)$ comparison, which is 5% less than the $2n \ln n + O(n)$ comparisons of classic single-pivot Quicksort (both average case on random permutations).
However, it needs $0.6 n\ln n + O(n)$ swaps for that, where classic Quicksort only needs $\frac13 n \ln n + O(n)$ swaps;
similarly, my instruction counts also indicate that classic Quicksort is more efficient.
What exactly makes Java 7's dual-pivot algorithm faster remains an open question.
(In case you are interested in more details on that, I could elaborate further.)

Tweaks of the algorithm like switching to Insertionsort for subproblems smaller than some (constant) threshold or optimizing code outside the partitioning loop (while(k <= g) { ... }) will only change the numbers hidden by $O(n)$.
This means that for large lists, they are not important.
For practical input sizes, they still help a lot, so having them in library code is a must.


Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?

$x_1=5, x_2=7$ is the smallest example where there is no common ancestor. Any ancestor of $x_1$ is in the range $2 \cdot 2^k + 1 \le z \le 3 \cdot 2^k - 1$, any ancestor of $x_2$ is in the range $3 \cdot 2^k + 1 \le z\le 4 \cdot 2^k - 1$. These are non-overlapping intervals with a gap of one number in between.


Computing a histogram with the number of extant values not known in advance

Often, in order to improve a sorting-based algorithm from $O(n\log n)$ to $O(n)$, one can use hash tables. In this case, you would use a hash table of size $O(n)$. Each entry of the hash table would store an integer and its count. The entire algorithm would now run in expected time $O(n)$.


Why is a Knapsack problem not an LP problem?

You can set up the knapsack problem as an integer linear program: To each item associate a 1/0 variable (include/exclude that item). Setting up the restrictions and the objective function from here is straightforward.

The point here is that the variables are restricted to be integers, while (regular) linear programming assumes real variables. They look similar, but are quite different beasts, computationally.

One successful technique to construct an approximate solution to the knapsack problem makes up a (continuous) linear programming problem, solve that one and tweaks the resulting values.


Prerequisites of computational complexity theory

Here are some prerequisites:

Mathematical maturity. You get this by taking math courses.
Mathematical induction. Important.
Rudimentary calculus. That also includes all you need to know about big O notation, which you can learn as part of your study of algorithms and complexity. Calculus is mainly used for estimating sums and in general asymptotic analysis.
Rudimentary linear algebra. Not relevant for everything, but common enough.
Basic discrete probability theory (linearity of expectation, Markov's and Chebyshev's inequalities, Bernoulli random variable, binomial distribution, indicator variables). Very helpful. Part of it (Chernoff's bound) you will learn as part of your study.
Basic graph theory. Most people probably don't actually have any background in graph theory to begin with, and learn whatever they need as part of their algorithms course.

Since calculus and linear algebra are common enough, what is probably most challenging is discrete probability theory. There are many textbooks covering this, and probably all of them are fine. Whatever you don't learn ahead of time you will pick up in your algorithms and complexity classes.

On the other hand, it is important to be proficient in induction and arithmetic manipulations, and to have some basic level of mathematical maturity. The only way to achieve this is to gather experience in doing basic proof-based math.


Proving formula for derivative of Kleene star

Using structural induction seems like overkill, or, which is more likely in your case, overly formal in a way which complete obstructs what is going on.

Here is a simple proof that explains why $\partial_a(r^*) = \partial_a(r)r^*$. We consider two cases:

$\epsilon \notin L[r]$. This implies that $\partial_a(r^{n+1}) = \partial_a(r)r^n$. Since $\partial_a(\epsilon) = \emptyset$, we get
$$
\partial_a(r^*) = \bigcup_{n \geq 0} \partial_a(r^n) = \bigcup_{n \geq 1} \partial_a(r)r^{n-1} = \partial_a(r) \bigcup_{n \geq 1} r^{n-1} = \partial_a(r) r^*.
$$
$\epsilon \in L[r]$. Write $r = \epsilon + s$, where $\epsilon \notin L[s]$. Then $r^* = s^*$, and so using the preceding case applied to $s$, we get
$$
\partial_a(r^*) = \partial_a(s^*) = \partial_a(s)s^* = \partial_a(r)r^*,
$$
since $\partial_a(r) = \partial_a(\epsilon) \cup \partial_a(s) = \partial_a(s)$.

If you did want to use a proof by structural induction, then you would need to let us know what identities of the Brzozowski derivative and of regular expressions you are allowed to use.

For example, if you are allowed to use $\partial_a(L_1 \cup L_2) = \partial_a(L_1) \cup \partial_a(L_2)$, then you immediately get the inductive step for union.

As another example, for the base case $r = b$, you can use the fact that every word in $b^*$ is either empty or starts with a $b$, and consequently $\partial_a(b^*) = \emptyset$. Since also $\partial_a(b) = \emptyset$, you would deduce this base case. Perhaps the identities you are allowed to use can implement this argument.


First of all $\min (|E|) = 0$ since the graph can be disconnected. $\min(|E|) = |V| - 1$, is true only for connected graphs. Whether a vertex is needed to be connected to the graph depends on the problem being considered. In general, a vertex can be isolated. So, in general, $0 \leq |E| \leq {{|V|}\choose{2}}$, if the graph is not a multi-graph. If the graph is a multi-graph then there is no upper limit to $|E|$.

Secondly if we are comparing $O((\log|V|^2||E|))$ against something like $O(|V|^2+|E|)$, former will be always better than the latter , since $O(\log(|V|^2)|E|) = O(\log|E|+2\log|V|)$.

So the question is, whether to analyze algorithms in terms of $|E|$ (i.e $|E|$ and $|V|$) or only in terms of $|V|$.

Of course what you say about needing to relate $|V|$ and $|E|$ is correct. However, whenever a complexity is stated in terms of $|E|$, it is better than, say, substituting $|V|^2$ for $|E|$. Note that $|E|$ is always $O(|V|^2)$ even for the cases when it is smaller, for example, for trees. $O()$ is upper bound.

If the analysis of an algorithm is in terms of $|E|$ than we get the complexity bound for all the cases, whether the graph is dense or sparse. Thus $|E||V|$-time algorithm is considered better than a $|V|^3$-time algorithm.

In the cases, if the graph is a tree, or a graph with a max degree $d=O(1)$, then $|E|$ is only $O(|V|)$. So, as an example, an $O(|E||V|)$ algorithm will be considered better than $O(|V|^3)$ algorithm. Thus, if we are able to do a tighter analysis, we are sure that the algorithm will fare better in case of non-worst case input.

As pointed by Raphael, $\Theta(|E|)$ is not same as $O(|V|^2)$. $\Theta$ analysis is better wherever applicable. But usually we don't give $\Theta$ analysis, because if we say some algorithm is $\Theta(f(n))$, and for some easy input the algorithm runs in $o(f(n))$ time, our statement will be wrong.


Why would it take longer than a few nanoseconds to get a message to the Moon and back? Because physics. Nothing can go faster than the speed of light.

Instead of packets on a network, think of suitcases on the baggage reclaim belt at an airport. The number of suitcases the airport workers put on the belt each second is the data rate; the length of time it takes a suitcase to go all the way around the belt is the round-trip time.

Suppose the airport employs more staff to throw luggage around. They can now put, say, twice as many suitcases onto the belt every second, but the belt doesn't move any faster so each individual bag still takes the same amount of time to go around.  They've increased the data rate but not the round-trip time. Because they're putting bags onto the belt more quickly, but the belt itself isn't moving any faster, there will be more bags in transit on the belt at any time.

Suppose that, instead of hiring more staff, they make the belt move twice as fast.  Now, you don't get any more bags per second but each bag only takes half the time to go around. They've decreased the round-trip time but not the data rate. Because bags now get delivered to waiting passengers faster, but they only appear at the original rate, there will be fewer bags in transit on the belt at any time.

So, you see that data rate and round trip time are essentially independent. The data rate is how many bits you can send each second, and the trip time is how long each individual bit takes to reach its destination.  You should now be able to figure out what the round trip time is, and also answer more complicated question like, "How long does it take to get a gigabyte of data to the moon on this link, and receive an acknowledgment that the final packet arrived?"


Is this DO LET sugar considered pure Lambda calculus and nullipotent / side-effect-free?

Anything that can be encoded in the pure lambda calculus, as you realize in the last paragraph, can not have side effects. Otherwise, the lambda calculus itself would be able to express those side effects as well.

However, note that your encoding looks a bit weird. For instance,

(LET a 1 b 2 e) = (λ a . (λ b . e) 1 2)

does not bind 1 to a and 2 to b. You probably want instead

(LET a 1 b 2 e) = (((λ a . (λ b . e)) 1) 2)

which does the correct binding. The other encoding should be fixed similarly.

I would suggest you "test" these encoding by performing $\beta$ steps. If you don't reach $e\{1/a,2/b\}$ something looks wrong.


Let S denote the solution sum.  Besides the trivial O(1) solution with S=0, other solutions if any can be found by an easy O(n2) method.  Let A denote a given array of positive integers.  Consider two kinds of partitions of A:  (B, C, E, D) and (F, E, G, H), where each letter represents a sequential part of A, with A=B+C+E+D or A=F+E+G+H; C or G possibly empty; with E representing the extracted sequence.  We suppose a solution has either S = sum(B) = sum(C+D) = (sum(A)-sum(E))/2 or S = sum(F+G) = sum(H) = (sum(A)-sum(E))/2, and claim that any solution has either an intact prefix or an intact suffix, or both, uninterrupted by extraction E.

To test for a solution of the first kind:  Let S be a prefix sum of A.  We look for a solution for S by advancing the beginning of E through A, and after each advance, solving (at O(1) amortized cost) for the end of E.  With O(n) prefix sums and O(n) beginnings-of-E, overall cost is O(n2).

Testing for solutions of the second kind is analogous.  The lightly-tested program shown below does this step by testing reversed(A).

#!/usr/bin/env python3
# Program written by James Waldby on 16 June 2019
# re: https://cs.stackexchange.com/questions/101950,
# "Array subset division with equal sums"
# Copyright © 2019 by James Waldby.  Offered without warranty under
# GPL v3 terms as at http://www.gnu.org/licenses/gpl.html

def findPrefixSol(A):
    S=0; U=sum(A); H=U//2; n=len(A); print (A)
    for i in range(n):        # prefix = first i elements
        S += A[i]
        if S>H: break
        Esum = 0                # sum of extract E
        Etarget = U - 2*S       # required size of E
        k = i+1                 # k -> after last element of E
        for j in range(i+1, n-1): # j -> first element of E
            while Esum < Etarget and k<n-1:
                Esum += A[k]
                k += 1
            if Esum > Etarget:
                Esum -= A[j]    # remove first element of E
                continue        # go try next E
            if Esum < Etarget:
                break           # can't extract enough to win; advance i
            print('Sol. for partition {}...{}...:  S={}, Es={}, U={}'.format(A[:i+1], A[j:k], S, Esum, U))
            break

A=[7, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))
print()
A=[7, 5, 9, 1, 5, 9, 1, 3, 9, 9, 1, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))


Where does the CPU get its first instructions from?

1. (A summary of the answer-in-comments by Jukka)

Startup code is stored in ROM (non-volatile memory) at a fixed address X.

When you activate the "reset" signal in the CPU, the CPU will initialise its registers to certain hard-coded values. The instruction pointer is one of these registers that are initialised to certain hard-coded values. In essence, the CPU manufacturer picks this hard-coded address X.
Hence, when you reset your CPU, the instruction pointer is reset to the same fixed address X. The CPU starts to execute instructions as usual: fetch the next instruction from address X, decode it, execute it, etc

Then whoever puts together a complete computer has to make sure that there is something useful at address X (e.g., a ROM memory chip with meaningful startup code).

2. Elaboration

The CPU has a very simple way of working, known as the FETCH-EXECUTE cycle:

(a)  FETCH: It goes to the memory and brings the instruction that
 is at address [PC].  (PC is a name of an internal CPU register; it
    holds the address of the instruction we need to perform next..).
(b) Execute: The PC executes the instruction it has just
    retrieved from the memory
(c) PC $\gets$ PC+1.(*)
(d) Go back to (a).

This fetch-execute loop happens all the time, regardless of the program you are running. In particular, when the CPU boots up (say, when its power goes from 0 to Vcc) the CPU simply begins to perform the above loop.

The initial value of PC depends on the specific CPU. It can be that the CPU wakes up with PC=0, or it can be that PC=0xFFF0 (as happens with Intel's X86 family), or with any other value PC=$PC_{init}$.
If you press the reset button, or turn the power off and on, the CPU  restores the PC to its initial value $PC_{init}$ and the CPU begins running the program that is in the memory at address $PC_{init}$, through the fetch-execute loop.

Now it is the computer designer task to make sure that the BIOS sits in the memory at address $PC_{init}$. The BIOS usually resides in a non-volatile memory so there is always a program to run in that address, even if you just turned the power off and on (this deletes the RAM but not the BIOS. It is more difficult to delete/change the BIOS, although possible and happens, e.g., when your device updates its "firmware").

(*) Advancing the PC by +1 assumes that each instruction takes 1 address of the memory space. The is rarely the case. In real systems we may see here PC+4 (as in the 32b MIPS) or PC+x (with $x\in\{1,...,7\}$ which depends on the instruction itself) as in the X86 family, etc.


Artificial intelligence - bridge and torch problem

Before you can calculate the size of the [thing], you need to decide exactly what the [thing] is.

In this case, you've decided that the state space is the set of people on the left side of the bridge. The people on the left can be any subset of the people, so any subset of $\{A, B, C, D, E\}$. The number of subsets of an $n$-element set is a well-known fact you should recall from your discrete mathematics classes.

Note that people moving across the bridge is not part of the state: it's a transition from one state to another (also known as an action). If you included that information in the state, you'd just make the search take longer.  For example, instead of having the state "$A$, $B$, and $E$ are on the left" transitioning to "$A$ and $E$ are on the left", you'd have it transition to "$A$ and $E$ are on the left and $B$ is on the bridge", which would then have no choice but to transition to "$A$ and $E$ are on the left" (and nobody is on the bridge). Adding a bunch of states that have only one successor is only going to slow down your search.


The authors suggest a new computation model that solves NP problems in polynomial time. Another such model has been known for a long time – non-deterministic Turing machines. They can also solve NP problems in polynomial time. In fact, one common definition of NP is the set of problems solvable by non-deterministic Turing machines in polynomial time.

If the authors succeed in realizing their machine physically (which is doubtful), then this shows that the "efficient Church–Turing thesis", which states that all physically realizable computation models can be simulated by a Turing machine using only polynomial overhead – is false. Another candidate for refuting this thesis is quantum computers, but they are conjectured not to be able to solve all NP problems in polynomial time.


Linear Temporal Logic with non-Boolean propositions (e.g. Integers)?

There has been some relatively recent work on constructive/intuitionistic variants or interpretations of LTL.

Kojima's and Igarashi's Constructive Linear-Time Temporal Logic: Proof Systems and Kripke Semantics is a decent place to start and references a bit of earlier work. In particular, Maier's Intuitionistic LTL and a New Characterization of Safety and Liveness. More recently, there was Jeffrey's LTL types FRP which showed that proofs of (constructive) LTL formulas corresponded to some FRP (Functional Reactive Programming) programs. Logics with tighter connections were formulated in later work, but this prompted some other work. One recent paper working in a linear logic setting shows a Curry-Howard correspondence between a LTL and event-driven programming: Paykin's, Krishnaswami's, and Zdancewic's The Essence of Event-Driven Programming.

At the level of logic, intuitionistic logic corresponds to having a Heyting algebra of truth values as opposed to a Boolean algebra. In a slightly different vein, Robust Linear Temporal Logic by Tabuada and Neider illustrates a many-valued (5-valued particularly) semantics for a LTL. They don't explore a proof theory except demonstrating that their rLTL can be translated to LTL.

While I didn't mention any, there is undoubtedly work in category theory that relates and would provide another perspective and categorical semantics. E.g. and related to the work above Jeltsch's Towards a Common Categorical Semantics for Linear-Time Temporal Logic and Functional Reactive Programming.


Is it possible to build regex-based-map with search asymptotically faster then hashmap?

One possible approach is to store the keys in a trie, convert the regex to a DFA (remove all useless states from it and optionally minimize it), and then use that to search the trie.
In particular, you can construct a recursive algorithm for traversing the trie.  The root of the trie is associated with the start state of the DFA.  For each edge out of the root, you look at the letter on that edge, advance the DFA to the appropriate state, and associate that state with the corresponding child.  If it causes the DFA to reject, then you can prune exploration of that node in the trie.  In this way, each node in the trie gets associated with a state of the DFA, you recursively explore the trie, pruning when you hit dead ends, and if you hit a leaf in the trie, if the DFA is in an accept state at that point, you have found a match.
However the running time to convert a regex to a DFA can take exponential time.  Also this only works with language-theoretic regular expressions, not Perl- or POSIX-style regexps, which are more expressive and cannot be converted to a DFA.  So, whether this will be attractive might depend on your application.


What is the simplest algorithm to compress a string?

If you need something reasonably effective but not very taxing to implement, I would recommend LZW.
LZW has several advantages, not the least of which is that it uses fixed-width codes (the width strictly increases as compression proceeds), rather than Huffman or arithmetic coding. It also does not require string searching through a sliding window, instead performing hash table or tree lookup per input character. This means that it requires significantly less code to implement than methods based on LZ77.


does mathematical function set in Genetic Programming can have two input values?

There are a couple of weird ideas here, I think. First, generally, you're not going to have all your trees the same size and shape. The algorithms should be allowed to create variations there.

Second, you should certainly be able to use functions with more than one argument. You can do this a number of ways. One, give each operator a "class" that you use to determine where it may legally appear. For instance, the "+" operator might be defined to take two operands, and thus it could only appear at a node with two children. Alternately, you can take the Common Lisp approach and simply define the result of applying those operations on too few arguments. For example, you might take that "+" operator and fill out any missing operands with 0s, so that applying (+) yields 0, (+ 5) yields 5, etc.

You're the one writing the program. You're allowed to make it behave however you like. I don't think you'll find a lot of references in the literature about this sort of thing because, honestly, it's an implementation issue that isn't interesting enough to publish.


Why is And-Or-Graph-Search called a search algorithm?

You can view And-Or Graph search as a search algorithm in two ways:

As search in the state space: Here, the "items" from the Wikipedia definition are the states, and an "item with specified properties among a collection of items" is a goal state. With And-Or Graph search, finding one such item is generally not enough. Under this view, the definition on Wikipedia is a bit too narrow.
As search in the space of partial conditional plans: Here, the "items" are partial conditional plans, and an "item with specified properties among a collection of items" is a total conditional plan, i.e., a partial conditional plan with the specified property that it is guaranteed to reach a goal state after a finite number of steps. Unlike a total conditional plan, a partial conditional plan may contain leaf nodes that are neither goal nodes nor have an associated action in the plan. Search steps in this search space are extensions of partial conditional plans by one action, i.e., these steps take a partial plan P and return a new partial plan P' that is like P, but with one non-goal leaf replaced by a valid action assignment to that leaf node.

Both views are legitimate, and the second one is perfectly consistent with the Wikipedia definition.

The analogous distinction in regular graph search would be between searching for a goal state and searching for a path to a goal state.


Adjacent house , dynamic programming problem

I'll just leave a broad hint. Suppose $H(1:n)=[h_1,h_2\ldots,h_n]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h_{n-1}$ in its optimal list,  or it doesn't. If it does include $h_{n-1}$, then we can't add $h_n$ to the list and we are done. If it doesn't include $h_{n-1}$, then we can check if the profit rises or drops with the inclusion of $h_{n}$.

Can you now write down a recurrence? And solve the recurrence efficiently? What happens when we have one or two houses in all?

Update:@user: Sorry, I forgot that there are negative values! You do need a 2D array and split the problem into to the small pieces $[h_i \ldots h_j]$ for  $1\leq i < j\leq n$,


Expected behavior of the maximum ranking generated in optimal assignment

Frieze and Sorkin showed that in the optimal solution of the assignment problem with weights chosen uniformly in $[0,1]$, the maximal value is $\Theta\bigl(\frac{\log n}{n}\bigr)$.
This suggests that the answer in your case is $\Theta(\log n)$.
I found this reference in the survey of Krokhmal and Pardalos mentioned in my answer to your original question. I suggest consulting the survey on your own for any further questions.


Prove that language of possible stack content is regular

Here is the basic idea. Assume for simplicity that each transition increases the size of the stack by at most one (you can always arrange that using epsilon transitions).

Suppose that the stack at some point is (bottom to top) $A_1 \ldots A_n$. At the time $t$ of the snapshot, $A_1$ is at the bottom of the stack. Consider the earliest time $t_1$ such that from time $t_1$ to time $t$, $A_1$ was always the bottom of the stack. At time $t_1$, the stack is simply $A_1$.

Similarly, there is an earliest time $t_2$ at which $A_2$ was second from last symbol on the stack, and at time $t_2$, the stack is $A_1 A_2$. We can similarly define times $t_3,\ldots,t_n$. We can describe the state of the stack schematically as follows:
$$
\bot \vdash^* A_1 \vdash^* A_1 A_2 \vdash^* \cdots \vdash^* A_1 A_2 \ldots A_n.
$$
The first step is special, so let's consider any other step. Think about what information is required to known whether you can get from $A_1 A_2 \ldots A_i$ to $A_1 A_2 \ldots A_{i+1}$, without every removing $A_1 A_2 \ldots A_i$. If the amount of information is finite, then you can use it to construct an automaton for your language.


Transitive reduction with vertex additions?

I don't think that any such "small" graph can exist in general.

Let $n$ be a multiple of $4$ and pick your favorite binary string $s = \langle s_0, \dots, s_{\ell-1} \rangle$ of length $ \ell = \frac{n^2}{4}$.

Build a directed bipartite graph $G_s = (A \cup B, E)$ on $n$ vertices where $A = \{a_0, \dots, a_{\frac{n}{2}-1}\}$ and $B = \{b_0, \dots, b_{\frac{n}{2}-1}\}$. $E$ contains the edge $(a_i,b_j) \in A \times B$ iff $s_{\frac{in}{2} + j}$ is $1$.

Let $G'_s$ be the smallest graph obtainable from $G_s$ that preserves connectivity relations.
Notice that, from $G'_s$, it is possible to recover the whole string $s$.

There are $2^\ell$ choices for $s$, which means that, for at least one graph $G_s$, the minimum number of bits needed to encode $G'_s$ must be at least $\ell = \Omega(n^2)$.

Notice that $O(m \log n)$ bits suffice to encode any graph with $m$ edges and $n$ vertices. This means that $G'_s = (V', E')$ must be such that $|E'| \cdot \log |V'| \cdot \log n = \Omega(n^2)$.


Computational complexity of coefficients

You also need to take into account the size of the coefficients. Adding integer coefficients of bit-length $\ell$ takes time $O(\ell)$, and multiplying them takes time $\tilde{O}(\ell)$, i.e. $O(\ell (\log \ell)^k)$ for some $k$ (any $k > 1$ will do). Your case is slightly more complicated, since the answer is rational and uses the "indefinite" value $e^{1/a_0}$, so in general it is going to be a polynomial in $e^{1/a_0}$ with rational coefficients. This further increases the running time.


Fixpoints of a transformation of an extended WHILE program

Suppose $f$ is a fixpoint of $A$. First,
$$
f(0) = f(1) = f(2) = f(3) = 3f(3),
$$
and so $f(0) = f(1) = f(2) = f(3) = 0$. Second,
$$
f(5) = 5f(4) = 5f(5),
$$
and so $f(4) = f(5) = 0$. Third, if $n = 4m+3 \geq 7$ then $$f(n) = n f(2m+3),$$ while if $n = 4m+1 \geq 9$ then $$f(n) = n f(2m+2) = nf(2m+3).$$ In both cases, $2m+3 < n$, and so you can prove by induction that $f(n) = 0$ for all odd $n$. That implies that $f(n) = 0$ also for all even $n$, and we conclude that $f(n) = 0$ for all $n$.

Edit: This is the maximal fixpoint. The minimal fixpoint is $\bot$. There are two other fixpoints: $f(n) = 0$ for $n \leq 3$ and undefined otherwise, and $f(n) = 0$ for $n > 3$ and undefined otherwise.


Size of address spaces (logical and physical)

The size of a frame is the same as that of a page, so the size of a frame is 1024 bytes (210 bytes).

If the physical memory is 32MB (225 bytes), the number of frames is 225 / 210 = 215 and this is also the maximum number of pages that can be present in memory at the same time.

The logical address space is larger than the physical address space, a process can address 232 memory locations that is 232 / 210 = 222 pages.


Kernel Perceptron vs Polynomial Perceptron

A SVM with a polynomial kernel is a SVM classifier.

A kernel perceptron is a perceptron classifier, or in other words, a neural net.

A SVM is quite different from a neural net.  So, that's one way that they differ.

However, Wikipedia says that SVMs are in some respects a generalization of a kernel perceptron, generalized with regularization.  Regularization is basically a form of Occam's razor: it says that, all else being equal, simpler models are preferred over more complex models.  Regularization helps avoid overfitting and thus is very useful in practice.

(Related: See also Support Vector Machines as Neural Nets? -- a SVM with a linear kernel is similar to a single-layer perceptron classifier, in case that's what you were thinking of.)


When does the function mapping a string to its prefix-free Kolmogorov complexity halt?

I think you are right; $K$ is a specific function which can not be computed. The author likely means to use some (arbitrary) approximative implementation; so no, this does not seem to be well-defined, if you are pedantic. You can also call it abuse of notation.

Consider this instead:

$\qquad \displaystyle \forall {M \in \mathcal{M}_K}.\ \sum_{M(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$

with $\mathcal{M}_K = \{M\ \mathrm{TM} \mid M(\sigma)\!\downarrow\ \implies\ M(\sigma)=K(\sigma) \}$ the set of all Turing machines that compute subfunctions of $K$.

In essence, this means: the bound holds no matter for which strings your implementation can compute the Kolmogorov complexity.

As Carl notes in the comments, it is plausible that the notation has nothing to do with halting or computing, as $K$ is not computable. Read $\sum_{K(\sigma)\!\downarrow}$ as sum ranging over the domain of $K$.


No polynomial time approximation algorithm better than $n^{1 − ε}$

The sentence means that for every $\epsilon > 0$ there is a polytime reduction $f_\epsilon$ that takes an instance $\phi$ of SAT into a pair $(G,k)$ such that:

If $\phi$ is not satisfiable then $G$ has no $k$-clique.
If $\phi$ is satisfiable then $G$ has an $n^{1-\epsilon} k$-clique.

An $n^{1-\epsilon}$-approximation algorithm for MAX-CLIQUE can be used to distinguish the two cases.

The running time of $f_\epsilon$ indeed depends on $\epsilon$, which probably appears in the exponent, that is, $f_\epsilon$ runs in time $n^{g(\epsilon)}$, where $g(\epsilon)$ tends to $\infty$ as $\epsilon \to 0$.


How to embed Pearson distance into Euclidean space

Yes.  Normalize the vectors, then use the Euclidean ($L_2$) distance.

In particular, map the vector $v=(v_1,\dots,v_n)$ to the vector

$$\tilde{v} = ((v_1-\mu)/s,\dots,(v_n-\mu)/s)$$

where $\mu=(v_1+\dots+v_n)/n$ is the mean of the elements and $s=\sqrt{(v_1-\mu)^2 + \dots + (v_n-\mu)^2}$.  (In the special case where $s=0$, define $\tilde{v}=(1/\sqrt{n},\dots,1/\sqrt{n})$.)  Then the vector $\tilde{v}$ has unit length.

Now the Pearson distance $d_P$ satisfies

$$d_P(u,v) = 1 - \tilde{u} \cdot \tilde{v} = \|\tilde{u} - \tilde{v}\|^2 / 2,$$

where $\|\cdot\|$ is the Euclidean ($L_2)$ norm.  (See here and here for a derivation of the above equation.)

Thus, minimizing the Pearson distance between $u,v$ is equivalent to minimizing the Euclidean distance between $\tilde{u},\tilde{v}$.  So once you've mapped vector $v$ to its embedding $\tilde{v}$, you can use a standard nearest neighbor data structure (with Euclidean distance) to answer nearest neighbor searches.


What is the formal description of a Turing machine?

In class you must have seen a formal definition of a Turing machine, such as the one given by Wikipedia. Formally, a Turing machine is given by a bunch of sets and functions. A formal description of a Turing machine is just this data. You can check out some examples on Wikipedia.

The definition in Wikipedia is only one possible definition — you will need to use the formal definition given in class. While the different formal definitions give rise to slightly different Turing machine models, these models are always equivalent in power (up to some small differences), in particular they are equivalent in terms of which functions can be computed in them.

Programming a Turing machine "formally" is like writing a program in a programming language (or assembly language). In contrast, informal descriptions of Turing machines are similar to pseudocode or to informal descriptions of algorithms. Programming Turing machines is very messy, and the point of this exercise is just to show you that it is possible in principle, and to help you understand how a Turing machine actually "works".


Min spanning tree that preserves total weight of original graph

Let us represent the people involved by numbers $1,\ldots,n$. For person $i$, let $\delta_i$ be the total amount that person $i$ is owed minus the total amount that she owes; notice that $\sum_{i=1}^n \delta_i = 0$. After all transactions have cleared, the capital of person $i$ should change by $\delta_i$. I will now show how to implement this scheme using at most $n-1$ transactions, using an iterative procedure.

If all $\delta_i$ are zero then no transactions need to be done, so we can assume that there exists some non-zero $\delta_i$. Let $i$ be a person such that $|\delta_i|$ is minimal. Since the $\delta_i$ sum to zero, there must be some $\delta_j$ with opposite sign. By our choice of $\delta_i$, $|\delta_j| \geq |\delta_i|$. If $\delta_i > 0$ then we tell person $j$ to pay person $i$ the amount of $\delta_i$, and if $\delta_i < 0$ then we make the opposite transaction. We update the $\delta$ vector accordingly: $\delta_i := 0$ and $\delta_j := \delta_j + \delta_i$ (maintaining the invariant that the $\delta_i$ sum to zero), and continue to the next iteration. In each iteration we zero out at least one $\delta_i$, so in iteration $n-1$ there will be at most two non-zero $\delta_i$, which will both be zeroed during the iteration (since they sum to zero). This shows that there are at most $n-1$ transactions in total.

Minimizing the total number of transactions is NP-hard, by reduction from the following problem:

  Given $n$ numbers in the range $[-n,+n]$ summing to zero and an integer $k$, can the numbers be partitioned into $k$ sets summing to zero?

This problem is shown to be NP-hard on math.se.

We will reduce this problem to the following:

  Given an owe graph and an integer $\ell$, can the graph be implemented using at most $\ell$ transactions?

Suppose that we are given a list of $n$ numbers $x_1,\ldots,x_n$ summing to zero and an integer $k$. Running the algorithm above, we construct an owe graph in which $\delta_i = x_i$. I claim that this owe graph can be implemented using $n-k$ transactions iff the list can be partitioned into $k$ parts summing to zero.

Suppose first that the list can be partitioned into $k$ parts summing to zero. Running the algorithm above for each of the parts, we end up with $n-k$ transactions. Conversely, suppose that the graph can be implemented using $n-k$ transactions. Thought of as a graph, these support at least $k$ connected components, each of which corresponding to a list summing to zero.


Here's how you can detect whether a weighted graph $G$ contains a zero-length cycle, assuming it does not contain any negative cycle.

Run Bellman-Ford on it to compute the distance $d(v)$ from the source to $v$, for each vertex $v$.
Color each edge $(v,w)$ red if $d(v) + \text{wt}(v,w) = d(w)$.
Form a new unweighted, directed graph $G'$ containing just the red edges from $G$.  Check whether $G'$ has any cycles, using a standard algorithm (e.g., depth-first search).  This can be done in linear time.

I'll leave it to you as an exercise to prove that the original graph $G$ contains a zero-length cycle if and only if the new graph $G'$ has a cycle.


Consider the oracle machine $N$ that decides $L \in NP^{\oplus P}$. For each computational branch of $N$, if it ends with $\textsf{YES}$, do nothing. If it ends with $\textsf{NO}$, branch and output once $\textsf{YES}$ and once $\textsf{NO}$. Therefore, $L\in  PP^{\oplus P}$.


You're right that physical computers have finite memory and so are not Turing-complete. There are other ways in which computability theory is not a good model for computing - it doesn't take into account time and memory constraints. Complexity theory was invented (perhaps) as a more realistic depiction of computing, but IMHO suffers from similar (but subtler) problems.

On the other hand, in order to mathematically study the capabilities and limits of computing, we need to use some abstraction which is unconstrained. That makes the analysis possible. Similarly, in statistical mechanics we assume that the number of elements (atoms or molecules) is so large, that the behaviour is close to the limit (that is, we let the number of elements tend to infinity). Studying computing from an asymptotic perspective has similar advantages, but sometimes is misleading. Here are some examples of the latter:

In cryptography, exponential algorithms are sometimes feasible. If we choose the wrong security parameters, our encryption might be insecure even though it's "provably secure".
Polynomial-time algorithms are supposed to represent efficient and feasible computing, but many of them aren't feasible. As an example, most sophisticated matrix multiplication algorithms aren't used in practice.
Modern complexity theory is obsessed with worst-case performance, and cannot analyze heuristic algorithms which are used in practice. NP-hard problems are considered infeasible, yet they are being solved in practice all the time.

A separate issue is that real computers don't work like Turing machines at all. They work like RAM machines, which are a better abstraction for actual computing.


Does P = NP in Cellular Automata of Hyperbolic Spaces?

The P vs. NP problem is a question about Turing machines $T$, because the complexity classes P and NP are defined in terms of these theoretical machines. Let's call these classes $P_T$ and $NP_T$ from now on. The paper introduces a new theoretical computation machine   $H$ that has associated classes $P_H$ (runs in polynomial time on the hyperbolic cellular automaton) and $NP_H$ (runs in non-deterministic polynomial time on the hyperbolic cellular automaton).
The first step in this paper is a proof that the 3SAT problem, a well known $NP_T$-complete problem, can be solved in polynomial time on this machine, i.e. this problem lies in $P_H$. Next, they show any polynomial time reduction on a Turing machine can be performed in polynomial time on their hyperbolic automaton. Since 3SAT is $NP_T$-complete, any $NP_T$ instance can be reduced to a 3SAT instance in polynomial time (on $T$ by definition, so also on $H$ by their lemma) and then be solved by solving 3SAT in poly-time, both on the hyperbolic automaton. In other words, the main result of this paper (Theorem 1) can be written as $NP_T \subseteq P_H$ in our notation. This does not give a solution to the P vs. NP problem, because that would need to relate the classes $NP_T$ and $P_T$.
Note that the authors include some remarks on the P vs. NP problem in section 4.2, where they claim their result is evidence for P$\neq$NP (!):

A third direction consists of the new light shed on the P=NP question in the
ordinary settings. As the hyperbolic space has properties which are very different from the properties of the euclidean space, in particular, it has many more directions, would not that be a hint favorable to prove that P$\neq$NP in euclidean conditions? It seems that
for the last ten years the works in the field of complexity incline people to believe
more in P$\neq$NP. Apparently, the present result also belongs to that trend.


Your misunderstanding might be a false assumption that there is a unique vertex cover. This is hardly the case – there could be many different ones.

The set of all vertices always forms a vertex cover. However, there are always smaller vertex covers (even in the complete graph!), and we are usually interested in finding a vertex cover which is as small in size as possible.


Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

Here is an excerpt from the introduction to an earlier paper of Svensson, Tarnawski and Végh, which was the first to give a constant factor approximation algorithm for ATSP:

Without any assumptions on the distances, a simple reduction from the problem
of deciding whether a graph is Hamiltonian shows that it is NP-hard to approximate
the shortest tour to within any factor. Therefore it is common to relax the problem by
allowing the tour to visit cities more than once. This is equivalent to assuming that the
distances satisfy the triangle inequality: the distance from city $i$ to $k$ is no larger than
the distance from $i$ to $j$ plus the distance from $j$ to $k$. All results mentioned and proved
in this paper refer to this setting.


How can I optimise this bitmask generation algorithm?

You can compute a power of 2 using the operation of left shift, in C and related languages <<. For example, $2^n$ is the same as 1 << n.

An alternative is to precompute the mask for all possible input values, and store them in the array. You'll have to try it out to see whether this is faster than the other suggestion.


Find coverage for plane from half-planes

I believe the connection between Helly's theorem and linear programming
stems from this paper:

  Amenta, Nina. "Helly-type theorems and generalized linear programming." Discrete & Computational Geometry 12, no. 3 (1994): 241-261.
  (Springer link.)

This arose from Nina Amenta's Ph.D. thesis (PDF download),
under the direction of Raimund Seidel.


Why does Fleury's algorithm have to return to the starting node?

Suppose you end up at a vertex different from the start. You may have visited the vertex before, say $k$ times. Each time you visited the vertex you used up one edge to enter it and one edge to leave it. So $2k$ edges, an even number. When you enter it for the last time, you used up $2k+1$ edges, an odd number. Since the degree of all nodes is even, there must be an edge left over which you can leave the vertex and the algorithm wouldn't have stopped.

The start vertex is special because you don't need to enter it to visit it the first time (right at the start).

Note that a graph can also be eulerian if it has exactly two vertices with odd degree. Then you have to choose one of them as a start vertex and you will end up at the other odd-degree vertex at the end of the algorithm. I leave it to you to prove why this is the case.


Your question is very poorly stated, except for the title. There is not a single sentence that is really correct or meaningful semantically.

So I will stick to the title, and explain what is wrongt with the text.

Activation records are a programming language implementation concept. Programming languages
can be used to implement algorithms in programs, but the concept of an
algorithm is an abstract notion, rather than a concrete realization in
a specific programming language.

An activation record is a chunk of memory containing usually the local
data necessary to execute a subprogram call (the name vary with
languages, such as function, procedure, method, subroutine ...), as
well as memory and code control flow. More dynamic parts of the data
used may be stored in other places (heap).

Thus an activation record is not the number of whatever. But the number
activation records in use do, in general, correspond to the number of
calls that have not been returned ... though that is not
necessarily true in some languages (see below).

In simpler programming languages, subprogram calls are well nested so
that the first subprogram to be returned from is the last one that was
called. Hence activation records can be stored on a pushdown stack.
That will not apply to such control structures as coroutines.

Also, it may be that data in activation records can still be used by
the program after the subprogram has been returned. This happens for
example when the result of a subprogram can be another subprogram to
be executed later (I skip the details).

So, in such a case, one may have to keep in memory more activation
records than there are unfinished calls. And the pushdown stack no
longer works properly without specific techniques to handle the problem.

Last, this is a general concept. I have no idea what your input array is for or what it does in your program. So that I cannot answer you. Many programs do not have arrays at all, but do have activation records.


Proving the language of non-primes is in NP

If you created a deterministic polynomial-time algorithm $A$ that can check a "yes"-certificate for Not-Prime (of polynomial length in the size of instance), then you already proved that your problem is in $\mathsf{NP}$.
Say that a polynomial upper bound on the length of the certificate is $p(s)$, where $s$ is the size of the instance. A non-deterministic polynomial-time algorithm for Not-Prime can do the following:

Guess the length $\ell$ of the certificate in $\{0, \dots, p(s)\}$.
For $i=1, \dots, \ell$: guess the $i$-th bit $c_i$ of the certificate.
Run $A$ on the certificate $c_1 c_2 \dots c_\ell$. If $A$ accepts, accept. Otherwise reject.

A certificate for an instance $n$ of Not-Prime is just a non-trivial prime factor of $n$ (which requires at most $\lceil \log n \rceil$ bits to be represented, so you can pick $p(s)=s$).


Algorithm for finding all the heaviest edges in a graph

In line with what Amir Nasr said in his comment above, I think the cycle property of MSTs would imply that finding a solution to your problem in linear time would find an MST in linear time.

From the Wikipedia page on MSTs and a few of the specific algorithms, it seems you can only currently do better be exploiting specific properties of your graph or using randomness.

You may find the $O(\left\vert{E}\right\vert\log{}\left\vert{V}\right\vert)$ complexity preferable to the $O(\left\vert{E}\right\vert+\left\vert{V}\right\vert\log{}\left\vert{V}\right\vert)$, and it seems that would just require a different choice of data structures or using either Kruskal's or Borůvka's.

For complexity with no $\log{}$ factors, it seems (for lack of a known general linear, deterministic, MST algorithm) you need either dense graphs, integer weights, or to use the expected linear time MST algorithm below.

https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm


Well, there is obviously a system. Someone wrote code to calculate the hash codes for strings, and that is the system that the hash code follows.

For normal software development purposes, it's Ok if there is a system that you can recognise, as long as different strings are mapped to different hash codes most of the time. For cryptography, for example when you calculate a hash code for a password, you want hash codes where it is practically impossible to determine the string from the hash code.

For a cryptographic hash, given a hash h, the only way to find a string s with hash(s) = h is to try out all possible strings s calculating hash(s) for each, until we find an s with hash(s) = h. Given a cryptographic hash for the string "1234", you would find such an s quickly.

For ordinary hash functions, if you are given how the hash code is calculated, it is often possible to calculate which is the shortest string s with hash(s) = s. However, any function that maps from an infinite set (strings) to a finite set (fixed length hash codes) must allow many strings to map to the same hash code. So if you map 500 bit strings to 256 bit hash codes, you cannot possibly determine which string was hashed, because many strings have the same hash code.


One common keyword that denotes this concept in contradistinction to asymptotic complexity is concrete complexity.


Do L-systems have a corresponding automata?

Lindenmayer's original papers define them using arrays of finite state machines. The outputs at each time are the states at the next time, which also serve as inputs to the neighbors, much like a cellular automaton. Unlike cellular automata, the machines can output strings, and each additional symbol becomes the state of a new machine in the array.


How can simulated annealing be related to the vehicle routing problem?

Simulated annealing is an optimization paradigm, in which (very roughly speaking) you start with some solution, and then try to make local changes that improve it, sometimes making a local change even if it doesn't improve.

Vehicle routing is an optimization problem. It is likely that the simulated annealing paradigm can be applied to it, probably in many different ways (corresponding to different notions of local change).


Here is a different proof using Berry's paradox instead of the liar paradox. Suppose that the halting problem (for programs with no input) were decidable. For each $n$, let $f(n)$ be the smallest number which cannot be computed by a program of length at most $n$ (without inputs). Consider the following program for computing $f(n)$:

  Go over all programs of length at most $n$, and for each one that halts, store the number it computes. Output the smallest number not encountered in this way.

This is computable since we can solve the halting problem for the relevant programs, and so we can determine which programs halt. What is the length of this program? The code itself is fixed apart from the length $n$, which can be encoded using $2\log n$ bits. All in all, this program has length $2\log n + C$ for some constant $C$. For large enough $n$ we have $2\log n + C \leq n$, and so there is a program of length at most $n$ which computes $f(n)$! This cannot be, and we are forced to conclude that the halting program is not computable.


The readme file lists the following uses for the dataset:

1. Cyber Security

2. Machine Learning

3. Recommender System

I believe that you already know point 3 since you specified that you want to use the dataset to build a recommender system.

About Point 2: You can use the information in the dataset to train a machine learning algorithm. The former could, for example, learn to recognize the relationships between surnames and nationality, therefore, after the training, you could pass one or more surnames as an input to the  algorithm and it could return the country.

About Point 3:
Here the subject becomes wider:
such a database can have great potential in the field of security.
 For example it could be used to perform password penetration tests, towards servers, using the list as a dictionary. For this same reason, however, it could also be useful to any attackers with malicious intent. Another example: imagine you have gained access to a confidential database that stores all user passwords and usernames. However, these data are hashed. You could submit all dataset records to the same hash function and compare them with database hashes to see if you find matches.


Amortized Analysis for Addition of $n$ numbers

You should be slightly more careful in your argument. Let the actual numbers you are adding be $x_1,\ldots,x_n > 0$, where $\ell_i = \lfloor \log_2 x_i \rfloor + 1$. The complexity of adding two numbers $x,y>0$ is $O(\log(x+y))$. In our case, assuming we are doing the addition sequentially, the numbers we are adding are $x_i$ and $x_1 + \cdots + x_{i-1}$, for $i=2,\ldots,n$. Therefore the entire complexity is
$$ O\big(\sum_{i=2}^n \log (x_1 + \cdots + x_i)\big). $$
Suppose now that we arrange the numbers in non-decreasing order $x_1 \leq x_2 \leq \cdots \leq x_n$. Then
$$
\sum_{i=2}^n \log (x_1 + \cdots + x_i) \leq \sum_{i=2}^n \log (ix_i) \leq n\log n + \ell_1 + \cdots + \ell_n.
$$
This is tight (up to constant factors) when all $\ell_i$ are equal. In particular, when adding $1$ to itself in this fashion, the complexity is $O(n\log n)$ rather than $O(n)$.

Can you think of a better way?


Why are programs executed in main memory?

They are not.  On modern desktop/server OSes, the program generally mmapped (or equivalent) into virtual memory and the currently running parts are paged in as needed.  However, the remainder of the program can sit on secondary storage and never be accessed.

The reason for the currently executing parts of memory being paged in as opposed to running directly from secondary storage is performance.  In general, any read access to secondary storage tends to be cached in memory, either directly through virtual memory or indirectly through something like a disk cache.  In fact, in the main memory there's an extensive cache hierarchy (typically 3 layers on x86 Intel / AMD processors) so even the idea that the program is store in "main" memory is mostly a convenient simplification, not a complete description of reality.  What actually happens is that some parts of the program are paged into main memory (by the OS) and some parts of the the program from main memory is cached into the L3 cache (by the CPU) and some parts of that are cached into the L2 cache(by the CPU) and some parts of that are cached into the L1 instruction cache (by the CPU).

On embedded systems and more exotic architectures, deviations from this pattern definitely exist.  Execute-in-place was already mentioned but another example is Harvard architecture processors, where instruction and data memory are completely separate and code runs from the instruction memory which isn't addressable as data.  Small embedded microcontrollers like PIC and AVR are examples of such processors.


Converting a digital circuit to two layers of OR and AND gates

Yes, it's true.  You can use  conjunctive normal form to express the circuit in two layers, where the first layer has OR gates and the second layer consists of $m$ (multi-input) AND gates.  However, there's a catch: you have to have a way to complement (negate) some of the inputs to the OR gates for free.  If you want to count the OR gates as a separate layer, then it takes three layers; if you imagine that your OR gates actually allow you to complement any subset of their inputs (e.g., the gate can compute $x \lor y$, $x \lor \neg y$, $\neg x \lor y$, or $\neg x \lor \neg y$), then it's just two layers.

Or, you can use disjunctive normal form to build a two-layer circuit where the first layer uses AND gates and the second layer contains $m$ (multi-input) OR gates.  Again, the same catch applies: you need to be able to complement the inputs to the AND gates "for free".

You can use disjunctive normal form to build a circuit where at most one input to any OR gate will ever be true at a time.  This means that you can replace the OR gate with an XOR gate without changing its functionality.  Therefore, yes, you can built a two-layer digital circuit where the first layer has only AND gates and the second layer has only XOR gates -- assuming you can complement some of the inputs to the AND gates for free.

For "XOR-of-ANDs", you can actually write any N-to-1-bit circuit as an XOR of ANDs, without any complementation at the input, if you allow the final XOR to optionally include an additional input that's held at the constant 1 (or, equivalently, if you allow the final gate to be either a XOR or a NXOR).  In particular, given any boolean function $f:\{0,1\}^N \to \{0,1\}$, you can write it as a multivariate polynomial $f(x_1,\dots,x_N)$ modulo 2.  Now $x^2=x \pmod 2$, so since everything is modulo 2, that means that you can eliminate all powers of two or higher: every multivariate polynomial can be expressed in the form

$$f(x_1,\dots,x_N) = \sum_S c_S \prod_{i \in S} x_i \pmod 2,$$

for some constants $c_S$, where $S$ ranges over all subsets $S \subseteq \{1,\dots,N\}$.  (For example, we might have $f(x_1,x_2,x_3) = x_1 x_2 + x_2 x_3 + x_3 + 1 \pmod 2$ as an example of such a polynomial.)  Now note that product modulo 2 is AND, and sum modulo 2 is XOR, so we get a XOR-of-AND representation of any boolean circuit.

As your colleague mentioned, in the worst case these circuits might need approximately $2^N$ gates, so this can be highly inefficient in some cases.

I don't know if it is possible to write every circuit as an AND-of-XORs (with some complements or constants somewhere).


Confused between bandwidth and frequency

"Bandwidth" has several different meanings. Among others, it can refer to either a frequency range or to data rate in bits/second. You have to use the context to figure out which is meant.

These two notions of bandwidth are not directly related, but a signal with a wider frequency range (i.e., higher signal bandwidth) can usually transmit data at a higher rate (i.e., has higher data bandwidth). However, the relation also depends on how much noise is present.


Data flow equations to determine value dependencies

Well, it seems that this can be reduced to the Reaching Definition problem, who's equations are:

$REACH_{in}(S) = \bigcup_{p \in pred(S)} REACH_{out}(p)$

$REACH_{out}(S) = GEN(S) \cup (REACH_{in}(S) - KILL(S))$

$GEN[d: y \rightarrow f(x_1, .., x_n)] = {d}$

$KILL[d: y \rightarrow f(x_1, .., x_n)] =DEFS(y) - {d}$


Embedding high dimensional vectors into low dimensional space preserving similarity

Locality-sensitive hashing is one reasonable approach for this.  I suggest reading standard resources on locality-sensitive hashing (LSH).  In your case, a locality-sensitive hash is a hash function that maps $h:\mathbb{R}^n \to S$ where if $x,y \in \mathbb{R}^n$ are close enough, then we'll have $h(x)=h(y)$ with high probability.

To get started, tead https://en.wikipedia.org/wiki/Locality-sensitive_hashing and https://cstheory.stackexchange.com/q/10053/5038.

Do understand that LSH is fundamentally probabilistic: if $x,y$ are similar, they will have a high probability of being mapped to the same bucket, but this cannot be guaranteed.

Alternatively, you might be interested in metric space embeddings.  An embedding $E:\mathbb{R}^n \to \mathbb{R}^d$ has the property that if $x,y$ are close (i.e., $\|x-y\|_2$ is not too large), then $E(x),E(y)$ will be close (i.e., $\|E(x)-E(y)\|_2$ will be not too large).  This could then provide a solution to your scheme, if you are satisfied that similar inputs map to buckets that are "nearby" but not necessarily identical.

For more on metric space embeddings, you can start with https://cs.stackexchange.com/a/27923/755, https://cstheory.stackexchange.com/a/6818/5038, https://cstheory.stackexchange.com/q/21487/5038, https://cstheory.stackexchange.com/questions/tagged/embeddings.


I'm not sure what you mean by "a set complement of $S$."

If you mean to allow complements with respect to different universal sets, then the statement in the question is not true. For example, let $S=\{1\}$. Its complement $S'$ with respect to $\{1,2\}$ is $\{2\}$. $\{1,2\}$ is a superset of $S'$ but its set complement with respect to $\{1,2,3\}$ is $\{3\}$, which is not a subset of $S=\{1\}$.

On the other hand, if you mean "the set complement of $S$" with respect to some fixed universal set $U$,the statement is true. We have $S'=U\setminus S$ and choose some $T \supseteq S'$. Then $U\setminus T \subseteq U\setminus S' = S$.


Algorithm for solving incremental max flow problem

You can do it in $\small \mathcal{O}(m + n)$ time where $\small m$ and $\small n$ are the # of edges and vertices respectively. Let the edge to be updated be $\small e = (u, v)$.

If you increment the capacity of $\small e$ by $\small 1$, the maximum flow increments by at most $\small 1$. Hence, starting with the current max flow $\small f$, you only need to find an augmenting path in the residual graph one more time, which costs $\small \mathcal{O}(m + n)$ time. Recall that each augmentation increments the flow value by at least $\small 1$. Therefore, it is guaranteed after the augmentation (if any), the flow attained is maximum.
If you decrement the capacity of $\small e$ by $\small 1$, the maximum flow decrements by at most $\small 1$. If the new capacity (after decreased by $\small 1$) $\small c(e) \geq f(e)$, where $\small f(e)$ is the current flow value of $\small e$, then nothing need to be conducted. Otherwise, we have to decrease the flow value of $\small e$. Let $\small s \rightarrow u$ be a simple path from $\small s$ to $\small u$, in which all edges have positive flow values and similarly define $\small v \rightarrow t$. We then decrease the flow values by $\small 1$ for all edges in the path $\small s \rightarrow u \rightarrow v \rightarrow t$. Finally, we again search for an augmenting path in the resultant residual graph.


In simple implementations, byte addressable is more important for writes than for read.
Because, with RAM, you read all 32 or 64 bits then steer data with a multiplexer. For writes, you need to be able to selectively update each part. (An alternative, in early DEC Alpha processors, was not to provide any byte wide access instructions, they eventually added these 8/16 bits accesses in later models)

In a less ideal world, several issues may need to be considered:

Some I/O ports may have side effects on reads, so that it is important to know whether each individual byte is read.
With EDC memory (error detection and correction), you cannot read or write only a byte, as error detection and correction is only efficient when handling at least 32 or 64 bits at once.


Problems for which algorithms based on partition refinement run faster than in loglinear time

Some linear time modular decomposition algorithms use (some type of) partition refinement, see e.g. these algorithms for directed and undirected graphs.


Either there is an additional constraint, either this problem is far more simpler than task scheduling.

Well you have to identify the limiting criterium of your problem which is 50 molds maximum in the kiln.

Let's call S = A+B+C = 536, the total number of molds. So You cannot do better than 11 firings (11*50=550).

First compute the euclidean division of the required elements to get the quotient and the remainder, that will be the constant molds and the variable molds to use.

- x, a = A/11 = 9, 3
- y, b = B/11 = 33, 1
- z, c = C/11 = 6, 4

So the constant molds are (x, y, z) = (9, 33, 6), that is to say 48 molds.

You now have 11 firings on the 2 (50-48) variables molds to complete the (a, b, c) = (3, 1, 4) remaining elements.
Let's say we want to minimize the number of molds to manipulate. Then just take one extra mold of each A, B, C to have a total of 51 molds.


Time complexity for concatenating strings

How does O(x + 2x + nx) reduce to O(xn^2) ?

O(x + 2x + nx) will be reduced to o(xn). But as your text says O(x + 2x + ... + nx) will be reduced to o(xn^2). (So if you have n = 5 for example you have the time complexity O(1x + 2x + 3x + 4x + 5x) which is equal to O(15x).) The time complexity of 1 + 2 + ... + n is O(n^2) (since 1 + 2 + ... + n = (n^2+n)/2, see my comment below). But in your case every addend in the sum must be multiplied with x, so you have O(x*n^2) as final result.


Is there a fast algorithm for computing the rolling mode of an array of integers?

Maintain two data structures as you move along.

A hash $H$ table of frequencies.
An array of sets $A$ containing the integers in each frequency. So $A[1]$ is the set of all integers that occur once in the window, $A[2]$ all that occur twice, etc.

When you move the window, you need to do two updates, one to increment a frequency of the new integer and one to decrement the frequency of the integer that left the window. For both the process is similar:

Look up the frequency $f$ of the integer in $H$ in $O(1)$ time.
Remove the integer from set $A[f]$ and add it to $A[f \pm 1]$ in $O(1)$ time (using hash sets).
Increment/decrement the frequency in $H$ in $O(1)$ time.

You don't need to track $A[0]$. The mode is any of the integers in the highest $A[f]$ which is non-empty, which you can keep track of in $O(1)$ time.

The total runtime is $O(n)$.


Online approximation algorithm for median?

If you need the exact median, store the last $k$ elements in a self-balancing binary search tree.  Also keep a linked list of the last $k$ elements.  At each time step you can delete the oldest element (the list will tell you which one) from the tree, then insert the newest one into the tree.  It is easy to obtain the median from the tree in $O(\log k)$ time.  Thus, you will do $O(\log k)$ work at each time step, and you will need $k$ space.
If you want to use much less than $k$ space, and are satisfied with the approximate median (you don't need the exact value), you can use various methods for approximating a streaming histogram.


If x operations cost O(x) amortized then how much xy operations cost?

Amortized is not just probabilistic, it means that for some big enough $y$,  $xy$ operations can't take a long time and will guaranteed to be $O(x)$ in average in worst case (and therefore $O(xy)$ for all $xy$ operations), even through some of operations may take even $O(xy)$ time itself.

https://stackoverflow.com/questions/200384/constant-amortized-time


For any language $L$, by definition
$$ L^* = \bigcup_{i=0}^\infty L^i, $$
where a word in $L^i$ is the concatenation of $i$ words from $L$. In particular, $L^0 = \{ \epsilon \}$ since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing zero words from $L$.


How can I derive a formula that produces a set of numbers per index?


What is the difference between a 'page' of memory and a 'frame' of memory?

Short version: "page" means "virtual page" (i.e. a chunk of virtual address space) and "page frame" means "physical page" (i.e. a chunk of physical memory).

That's it, pretty much. It's important to keep the two concepts distinct because at any given time, a page may not be backed by a page frame (it could be a zero-fill page which hasn't been accessed, or paged out to secondary memory), and a page frame may back multiple pages (sometimes in different address spaces, e.g. shared memory or memory-mapped files).


The best case for Shell sort is when the array is already sorted.
In that case the inner loop does not need to any work and a simple comparison will be sufficient to skip the inner sort loop.

A best case of $Θ(N)$ is reached by using a constant number of increments.
But the problem is that the best value for the gapping depends on the input. Therefore you cannot choose a single best value for the gap and must suffer a $log^2(N)$ delay due to repeated compares.

So you are almost correct. Obviously there is no way to compare fewer than N-1 elements before we can conclude that the array is already sorted, so $Θ(N\space log^2(N) )$ it is.

Note that this best case is for randomized Shell sort which is subtly different from the original.

See: https://arxiv.org/pdf/0909.1037.pdf

All this means that Shell sort is not a particularly good algorithm for a (nearly) sorted array. The gapping introduces redundant compares whereas other sorting algorithms only have to go over the array once in the best case.
When the array is random, the gapping works in your favor, and these other algorithms that perform so wonderfully on a (nearly) sorted array perform at a dismal $O(N^2)$


Algorithm for maximizing the number of same-sized groups

Hint:

 Try working through some examples.  Can you narrow down the set of possible values that might appear in the largest group in the best solution?  (For instance, your second example has 2's as the value, and your third example has 4's or 5's.)  Can you see how to use that to help you do better than brute force?


What is the set of languages accepted by empty stack pda?

When defining the semantics of PDAs accepting with an empty stack, we initialize the stack with a special "bottom-of-stack" symbol. This solves your difficulty.

The set of languages accepted by empty-stack PDAs is the context-free languages. It is exactly the same set of languages accepted by final-state PDAs. The picture changes when considering deterministic PDAs: final-state DPDA accept the deterministic context-free languages, whereas empty-stack DPDAs accept the prefix-free deterministic context-free languages.