Is $A \leqslant_P B \iff A \in \mathsf{P}^B$? If not are there counter-examples?

Assuming $\le_P$ is a polynomial many-one reduction (as opposed to a Turing reduction), the statement is incorrect.
For example, for any language $L$ we have $\overline{L} \in P^L$ (and in fact, in $O(1)$ time and space as well, so this is also an example for logspace many-one reductions)
But obviously if we take $L=\mathrm{Halt}$ to be the halting problem language, we wont have that $\overline{L} \le_P L$ since $\mathrm{Halt}\in \mathsf{RE}$ but $\overline{\mathrm{Halt}}\notin \mathsf{RE}$ and $\mathsf{RE}$ is closed under $\le_P$.


BSS-model Computational complexity of finding the roots of a polyomial

It's not too hard to find the real roots of a univariate polynomial, for example by using Sturm's theorem which allows you to easily identify the number of sign changes of a real-valued polynomial between two given bounds.

I believe it's not too hard to show that this technique, coupled with a simple divide-and-conquer technique or Newton's method and an elementary bound on the absolute value of the largest root as a function of the coefficients, gives a polynomial time algorithm for finding the roots of a polynomial, in the time of the degree $n$ and the desired precision $p$ (in digits).

For more information see the wikipedia article or this mathoverflow question.

Edit: The question was clarified to ask about exact solutions in the Blum-Shub-Smale model. In this situation, it is already impossible to get square roots, in particular to get exact solutions to the equation
$$ X^2 - 2 = 0$$

This result (and a much more general one) is proven in this paper by Calvert, Kramer and Miller.


Enumerating all partial permutations of given length in lexicographic order

Here is a simple iterative solution. We maintain two arrays, an output array $L$, and a Boolean array $A$, which keeps track of the elements currently in $L$. We update $A$ as we add and remove elements from $L$.
We initialize $L$ with $0,\ldots,k-1$, which is also our first output. Now we repeatedly try to "increment" $L$. If successful, we output the incremented $L$, and try to increment $L$ again. If unsuccessful, we have gone through all combinations, and can terminate.
In order to increment $L$, we start by trying to increment position $k-1$ (this is the rightmost position). We do so by scanning the array $A$ starting at $L[k-1] + 1$, until we find an element $x$ which is not in $L$. If this search is successful, we replace $L[k-1]$ with $x$. Otherwise, we try to do the same for $L[k-2],\ldots,L[0]$, until successful; if all of these fail, we declare failure (and terminate).
Suppose that we have successfully replaced $L[j]$. If $j = k-1$, we're done. Otherwise, we have to update $L[j+1],\ldots,L[k-1]$, which we do by scanning $A$ starting at $0$, inserting the first $k-j-1$ elements not already in $L$.
Here is a Python implementation:
def gen(n, k):
    A = [True] * k + [False] * (n-k)
    L = list(range(k))
    yield tuple(L)
    while True:
        j = k - 1
        while j >= 0:
            A[L[j]] = False
            t = L[j] + 1
            while t < n and A[t]:
                t += 1
            if t < n:
                A[t] = True
                L[j] = t
                r = 0
                j += 1
                while j < k:
                    while A[r]:
                        r += 1
                    A[r] = True
                    L[j] = r
                    j += 1
                yield tuple(L)
                break
            else:
                j -= 1
        if j == -1:
            break

An even simpler recursive solution simply iterates over all possible choices of the first element; within these, iterates over all possible choices of the second element; and so on.
Here is a Python implementation:
def gen_rec(n, k, L=[]):
    if len(L) == k:
        yield tuple(L)
    for i in range(n):
        if i not in L:
            yield from gen_rec(n, k, L + [i])


Prefix complexity of x conditioned on prefix complexity of x

For plain complexity the assertion is true. One direction is clear: $K(x|K(x))\leq K(x)$ (easier to describe x from something than from nothing). In the other direction one can argue by contraposition. Suppose one could find $x$s with programs $q$s of length $l(q)$ arbitrarily shorter than $K(x)$. Set $K(x)-l(q) \equiv C$. In other words one can find $x$s with arbitrarily large corresponding $C$s. To reconstruct $x$ one needs to only know $q$ and $C$, which can be encoded in $l(q)+2\log(C)$ bits. Now $K(x)-l(q)-2\log(C) = C-2\log(C)$ which can be made arbitrarily large for sufficiently large $C$. Hence, we have obtained a description of $x$ much shorter than $K(x)$, a contradiction. This may be found as problem 43 in the following book (in Russian): https://www.mccme.ru/free-books/shen/kolmbook.pdf (Vereschagin, Uspensky, Shen, "Kolmogorov complexity and algorithmic randomness").


Oracle machine solving halting problem for other oracle machines

The proof that a Turing machine with an oracle for $X$ can't solve the halting problem for Turing machines with an oracle for $X$ is identical to the proof that an ordinary Turing machine can't solve the halting problem for ordinary Turing machines.


Transitive Closure vs Reachability in Graphs

Your algorithm is known as Purdom's algorithm. There are two versions of transitive closure:

Calculate the transitive closure as a relation. This cannot run in time $O(|V|+|E|)$, since the output could be bigger than that (consider a directed path, for example).
Calculate enough information to be able to answer oracle queries to the transitive closure in $O(1)$. Even in this case, the algorithm doesn't seem to run in time $O(|V|+|E|)$. Hopefully the link would make it clear why.


How does one figure out where a class of languages falls under some complexity class?

Turing recognizable languages are not (generally) in P, as the time hierarchy theorem implies. To show that a class $L_1$ is contained in a class $L_2$, you need to show that every language in $L_1$ belongs to $L_2$. For example, to show that $L$ (logspace) is contained in $P$ (polytime), you argue as follows: every language in $L$ is decided by some machine running in logarithmic space; this machine must run in polynomial time; so the language is in $P$. In this example, the same machine was used, but this is not necessary. For example, Savitch's theorem shows that $\mathrm{NSPACE}(s(n)) \subseteq \mathrm{DSPACE}(s(n)^2)$, and here the same machine cannot be used (since a non-deterministic Turing machine is not necessarily deterministic).


Analyze Speed Up in A Dispatcher-Woker Model

Here is how you can compute its distribution.  Let $F(t) = \Pr[X_i \le t]$ (the cumulative distribution function of $X_i$), and $G(t) = \Pr[Y \le t]$ (the cumulative distribution function of $Y$).  Then

$$G(t) = \Pr[Y \le t] = \Pr[X_1 \le t, \dots, X_N \le t] = \Pr[X_1 \le t] \times \dots \times \Pr[X_N \le t] = F(t)^N.$$

Now the probability density function of $Y$, $g(t)$, is the derivative of the cumulative distribution function, so

$$g(t) = G'(t) = N F(t)^{N-1} f(t),$$

where $f(t)$ is the probability density function of $X_i$.  This directly gives you the distribution of $Y$: namely, $g(\cdot)$ is the distribution of $Y$.

This calculation also gives you a good way to compute tail bounds.  For instance, if you want to compute the probability that the whole process needs more than $t$ time, i.e., that $Y > t$, you can compute this as $1-G(t) = 1 - F(t)^N$.

See also https://math.stackexchange.com/q/89030/14578 for other useful facts about the distribution of $Y$.


Use dynamic programming to find division number of each node, For leaf nodes set it to $0$
Then recursively for parent of each leaf node set it to sum of division of it's child, and for each child because that child is not counted in division number of itself we should add its division number by one to calculate the parent division number:
$$\text{division}(v) = \Sigma (\text{division}(\text{child}_i)+1)$$
Use above recursion structure to set division number of each node, but if in some point if you have division number bigger than equal to $|V|/2$ output this node.

This is bottom up $O(|V|)$ algorithm because you will check every node at most once, and the operation which calculates division numbers is at most $\Sigma \text{ deg}(v_i) = 2|E| = 2|V-1|$.


Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?

Algorithms are usually analyzed under the word RAM model, in which basic operations on machine words cost $O(1)$. Machine words are defined as words of length $\log n$, where $n$ is the size of the input (in bits).

In the case of algorithms on weighted graphs, we could make the further assumption that weights are put in special registers for which "reasonable" arithmetic operations are $O(1)$. This assumption is made implicitly, without any mention of it, since the exact computation model isn't really needed when designing an algorithm, as long as you're not "cheating". It allows using floating point weights, for example.

The computation model serves two purposes:

To explain what constitutes "cheating", that is, what is not allowed (or rather, what is allow).
To allow proving lower bounds.

If we are not careful with the computation model, we could solve PSPACE-complete problems such as TQBF; see here.

One instantiation of the murky class of computation models for weighted graphs is allowing the weights to fit in a constant number of machine words; then we can just analyze the algorithm using the word RAM model. In this case, any weight encountered during Dijkstra's algorithm also fits in a constant number of machine words, since any such weight is the sum of at most $|V|-1$ weights. Therefore in the word RAM model, assignment (as well as addition) costs $O(1)$ rather than $O(\log s)$.


Why Does the Fixed Point Theorem Apply to Quines?

As Discrete Lizard points out, there exist more than one "fixed point theorem." The one you're mentioning makes sense in terms of topology and geometry, but you're right to realize that it does not apply to programming languages.

It turns out, though, that a more general notion of continuity, called Scott Continuity, can give you something that is applicable, namely the Kleene fixed-point theorem:

  Any Scott-continuous function over a directed-complete partial order has a least fixed point.

An earlier, and easier to understand, version of this is given by Knaster-Tarski:

  Any monotone function over a complete lattice has a fixed-point. In fact, the fixed points of such a function form a complete lattice.


Aussume P != NP, are these assertions valid?

Regarding 1: yes, since $B$ is $\mathsf{NP}$-complete it must be $\mathsf{NP}$-hard, i.e., for ever every problem $C$ in $\mathsf{NP}$ we have $C \le_P B$. Since $A \in \mathsf{P} \subseteq \mathsf{NP}$, we can pick $C=A$.
This is true regardless of whether $\mathsf{P}=\mathsf{NP}$.
Notice, however, that we are using the fact that $B$ is $\mathsf{NP}$-complete. In general it is not possible to reduce an arbitrary problem in $\mathsf{P}$ to an arbitrary problem in $\mathsf{NP}$.
Regarding 2: no. Here your reasoning is correct, $B \le_p A$ would imply $\mathsf{P} = \mathsf{NP}$.


How to prove that concatenating a language A and A* is commutative?

$AA^*$ is the set of all strings consisting of a string in A, followed by zero or more strings in A, which means all strings consisting of one or more strings in A. $A^*A$ is the set of all strings consisting of zero or more strings in A, followed by one string in A, which also means all strings consisting of one or more strings in A. So both are the same.


If a problem is not in NP, prove that every NP problem can be efficiently reduced to it

I suppose an analogous question can also be asked for P and NP. If a problem is in NP, then can every problem in P be reduced in polynomial time to it?

No. There is a stupidly simple argument here: the empty language (i.e., a problem with no yes-instances) is in NP, but no problem in P can be reduced to it.

  Does there exist a problem that is hard to solve but problems in NP cannot be reduced to it in polynomial time i.e. it does not satisfy the definition of NP-hard but is strictly not in NP?

Yes (conditional on some complexity theory assumptions). Let's take some stupidly hard problem $L$. To keep this answer as simple as possible we will assume that $L$ is undecidable but this is not necessary; a language obtained by applying the Time Hierarchy Theorem to the Ackermann function would easily suffice. Assume that instances of $L$ can be padded, i.e., adding extra zeroes at the end does not change whether an instance is a yes- or no-instance. Starting with undecidable language $L'$, $L$ could be obtained by taking every string from $L'$ and appending a $1$ followed by an arbitrary amount of zeroes. Clearly $L$ is still undecidable.

Now consider the subset of $L$ containing only those strings whose length can be expressed as a tower of powers of two (i.e., $1, 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \ldots$). We split this subset into three languages $L_0, L_1, L_2$, depending on the height of the tower of powers of two. $L_0$ contains those strings where the tower has a height which is a multiple of $3$, $L_1$ contains strings whose height is $1$ modulo $3$, $L_2$ those strings whose height is $2$ modulo $3$.

Neither $L_0, L_1$ or $L_2$ are in $NP$. If they were, we could decide $L$ by padding instances to make their length the appropriate tower of powers of two, and then solving them using the $NP$ algorithm. Obviously the padding can increase the length of the instance exponentially, but if $L$ is sufficiently hard (e.g., undecidable) this does not matter.

Now, to answer the original question, can every problem in $NP$ be reduced in polynomial time to $L_0, L_1$ and $L_2$ (all of which are outside $NP$)? If we take some problem instance of a problem in $NP$, then at least one of the reductions (to $L_0, L_1$ or $L_2$) will result in an exponentially smaller instance. This is because the reduction, being polynomial, cannot increase the size of the instance too much, so (due to the large gaps in instance sizes) must - for at least one of $L_0, L_1$ or $L_2$ - give a much smaller instance as output.

Intuitively, this sounds very unlikely. It would mean we could take an arbitrary problem in $NP$ and in polynomial time output an exponentially smaller instance (albeit of a much harder problem).

Formally, this would mean that $NP\subseteq P/poly$, a consequence which is regarded as unlikely since it would imply the collapse of the polynomial hierarchy.


Operating Systems - SJN/Round Robin - turn around time + waiting time

Turn Around time= Completion time - Arrival Time

and

Waiting time= Turn Around time - Burst time


Difference between $NP\cap coNP$ and $NEXP\cap coNEXP$

NO. Assume to the contrary that we have that equality, the LHS contains $EXP^{EXP}=EEXP$. So, we deduce that $NEXP=EEXP$.But then the LHS can even contain $EXP^{EEXP}=EEEXP$. That is way too much over $NEXP$.
YES. By the same proof for $P^{NP\cap coNP}=NP\cap coNP$, the NEXP machine simulates the oracle machine by guessing the oracle answer and the corresponding certificate of membership (non-membership) and verify by the verifier (refuter, resp.) of the NEXP (coNEXP, resp.) machine for the language of the oracle. Then, if at any time the certuficate does not prove the guess, refute and halt. Otherwise, return the same answer as the oracle machine.

Similarly for the coNEXP machine, but you have to accept if a guess is not proven by the certificate guessed after it.


solve a rational equation as fast as possible

It depends on what kind of answer you want. Finding closed-form algebraic solutions is different from finding numeric solutions.
Having said that, I agree with plop here. Your best bet is to get bounds on the roots, and then use an iterative algorithm. The good news is that for a cubic, it's not difficult to find bounds.
First off, I assume that you know to compute the roots of a quadratic using the Citardauq formula when appropriate. If $b\ge 0$ then:
$$x_1 = \frac{-b - \sqrt{b^2 - 4ac}}{2a}$$
$$x_2 = \frac{2c}{-b - \sqrt{b^2 - 4ac}}$$
Otherwise:
$$x_1 = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$$
$$x_2 = \frac{2c}{-b + \sqrt{b^2 - 4ac}}$$
Using this method, the addition/subtraction of $b$ and the square root of the discriminant have the same sign, so there is no cancellation there.
To find all roots of a cubic $p(x) = a x^3 + b x^2 + cx + d$ numerically, first find the roots of the derivative $x_1$ and $x_2$, and evaluate the cubic at those two points. Assuming that $x_1 \le x_2$, you have four cases to consider.

If $x_1 = x_2$, then the cubic is of the form $a(x - x_1)^3 + d - ax_1^3$. This means it has one real root at $\sqrt[3]{x_1^3 - \frac{d}{a}} + x_1$. If $ax_1^3=d$ then it's a triply-repeated root.
If $p(x_1)$ and $p(x_2)$ have opposite sign, then the cubic has
three distinct real roots. Specifically, there is a real root in each of the following ranges: $\left(-\infty,x_1\right)$, $\left(x_1,x_2\right)$, $\left(x_2,\infty\right)$. Use this to get an initial estimate and use a numeric root finder.
If $x_1 \ne x_2$ but $p(x_1)$ and $p(x_2)$ have the same sign, then the cubic has only one real root. It is either in the range $\left(-\infty,x_1\right)$ or $\left(x_2,\infty\right)$, depending on the sign of $a$.
If one of $p(x_1)$ or $p(x_2)$ are zero, then there is a repeated real root at that point and a third real root elsewhere. Again, it is either in the range $\left(-\infty,x_1\right)$ or $\left(x_2,\infty\right)$, depending on the sign of $a$.

Because you need the smallest positive root, you can eliminate ranges from consideration. For example, suppose you find yourself in case 2. If $x_2 \le 0$, you only need to check the range $\left(x_2,\infty\right)$ for a positive root, as the other two roots are guaranteed to be negative. You never have to perform the iterative algorithm on all three ranges in case 2.
Doing this kind of exhaustive case analysis becomes unwieldy for higher-degree polynomials, which is why we tend to prefer different methods there. This is beyond the scope of the question, but as a general guide:

It's usually worth performing squarefree factorisation if possible, because numeric methods tend to converge more slowly around repeated roots.
You can bound the roots using Vincent's theorem (or Sturm's theorem, which is slower but a bit easier to understand) and then use numerical root finding if you only need the real roots.
You can use something like Aberth's method if you need complex roots.


NLP - Deep belief neural networks or logic?

Very briefly:

Option 1 faces difficulties since certain connectionist models are incapable of learning natural languages.

Option 2 faces grave difficulties due to many negative results, notably Gold's theorem.
There's a nice overview which includes a discussion of probabilistic approaches.

Generally, the response to these difficulties has been to look at other sources of information beyond the linguistic input alone.


Subset sum, pseudo-polynomial time dynamic programming solution?

Rephrasing Kaveh's comment as an answer:

If you bound the size the values in the input (bound the number of bits for each value to be logarithmic in the total number of bits of the input) then the problem can be solve in polynomial time using dynamic programming. If they are not bounded they can have values which are exponentially large and the size of the table for the dynamic programming would be exponential.


What is the complexity of calling a trivial hash function $n$ times?

Your question is ill-defined, and it's precisely that that I believe to be your misunderstanding.

There isn't an inherent cost in Landau notation, or any complexity analysis measure for that matter. You first need to define a model, by defining exactly what consists of an operation.

For example you could model only assignments, in which case the complexity is $n$. You could also model only hash function calls, in which case the complexity is also $n$. Or you could consider both to be one unit of time, in which case the complexity is $2n$.

Or perhaps your hash function is $100$ times slower than an assignment, which we assign cost $1$. Then your complexity would be $101n$.


How to express the data structure in the pesudocode of your algorithm

There are no set rules, but these type of details are sometimes omitted from the pseudocode listing. You might see something like

ALGORITHM(S, n):
For i = 1 to n do
   S = ADD(S, i)
EndFor

Then followed by something like "... the algorithm performs $\Theta(n)$ units of work assuming that the set $S$ is implemented as blah so that the addition of an element ADD(S,i) runs in blah time ..."


Why isn't set $\{ \langle i, j \rangle \mid W_i = \overline{W_j}\}$ a recursively enumerated set?

Hint: Use a reduction for the proof. If your  language $L=\{ \langle i, j \rangle \mid W_i = \overline W_j\}$ is r.e. then of course  every language where the second machine $M_j$ is fixed is also r.e.. Say, you pick for $M_j$ the Turing machine that always accepts, then you are left with showing that the language $L_0=\{ i \mid W_i = \emptyset \}$ is not r.e.. This again can be shown with a reduction (i.e., show that $\overline{\text{HALT}}\le_p  L_0$). Alternatively, show that $L_0$ is not decidable (Rice's Theorem), but $\overline{L_0}$ is Turing-recognizable.


Hint...

There may be a direct application of the pumping lemma, but I suggest you take a look at closure properties. Consider the non-CFL in the first answer to the reference post, $P=\{a^p:p \text{ prime}\}$, which is clearly a cousin of $L$. Can you find a (fairly simple) operation on $L$ that preserves CFLs and more or less yields $P$?  If so, you are done, except perhaps to tidy up with some other operations to deal with special cases for $P$.

In general, when languages are relatively "dense", that is, have a high proportion of members to non-members for all given lengths, it's harder to apply pumping arguments, because it's more work to pump to get outside the "dense" set; in fact, sometimes it's impossible.  $P$ is a nice "sparse" set, so pumping works well, as shown in the reference post.  $L$ is quite a bit "denser", so transforming it to a "sparser" form is a good tactic to try.

The classical example of this principle (for non-regular languages) is the very dense set $\{a^ib^j:i \neq j\}$ and the corresponding sparse set is $\{a^ib^i\}$. The operation in this case is complement, again with a "cleanup" operation needed as well.  As part of the above hint, the operation there is not complement, which doesn't work for CFLs anyway.


An equivalent of $\neg ((a \wedge b) \Leftrightarrow c)$ based on a specific requirement

Outgoing from requirements can you  use $\oplus$? if yes, then, as we know, that $\neg(a\Leftrightarrow b) = a \oplus b$, then we can obtain
$$\neg ((a \wedge b) \Leftrightarrow c) = \neg (\neg a \lor\neg b) \oplus c$$
Update.
Accordingly to your update I wrote my one: not shorter, slightly different, but logically equivalent yours one
$$\neg \big[(a \wedge b) \Leftrightarrow c\big] = \\
=\neg \big[\big((a \wedge b) \Rightarrow c \big) \land \big(c \Rightarrow (a \wedge b)\big) \big]=\\
=\neg \big[ \big(\neg (a \wedge b) \lor c \big) \land \big( \neg c \lor (a \wedge b) \big) \big]=\\
=\neg \big[ \big(\neg a \lor\neg b \lor c  \big) \land \big(\neg c \lor \neg(\neg a \lor\neg b) \big) \big]=\\
= \neg\big(\neg a \lor\neg b \lor c \big) \lor \neg\big( \neg c \lor \neg(\neg a \lor\neg b) \big) $$


Given a set of n balls with different weights and a scale that compares two balls

Assume you have a sorted array of all weights. If any such element existed then more than %25 of that array had to be occupied with that element. Then either element at %25 marker, %50 marker and %75 marker has to contain such element. So we have 3 candidates but no such sorted array. Assume N is divisible by 4 below. There might some tweaks to be done for edge cases which can be handled.

Do Worst-Case Linear-Time Selection to find the median of the entire array.
Create two arrays of size |N / 2| both. For the first one but everything smaller than the median. For the second one put everything that is larger. If either of the arrays or not full pad the array with the median element. Then find the median of both of these arrays as mentioned in step 1.
We have 3 candidates. For each candidate count how many of them have equal weight. If any has counter more than |N / 4| output this element.

Runtime: Each step is linear with respect to input. We iterate over the entire balls multiple times but still it is O(N).

Problem with the proposed algorithm is mainly the probable imbalance of the random partitions of the set


What impact does the modulo operator have in a for-loop?

It feels like you're trying to think in terms of pre-defined recipes, rather than just figuring it out by reasoning about the situation. The if statement triggers every time $y$ is a multiple of $n$. So just work out how many different values in $\{1, \dots, n^2+1\}$ are multiples of $n$, and that's how many times the innermost for loop runs.

Of course, your code is just an example but, in real life, with something as simple and predictable as the modulo operator, you wouldn't use this approach of "generate every possible value of $y$ and see which ones pass the test". It's much more efficient to just write a for loop that directly assigns the values $n, 2n, \dots, n^2$ to $y$.


FCFS (First-Come, First-Served) scheduling can also cause blocking in a busy dynamic system in another way, known as the convoy effect.

When one CPU intensive process blocks the CPU, a number of I/O intensive processes can get backed up behind it, leaving the I/O devices idle. When the CPU hog finally relinquishes the CPU, then the I/O processes pass through the CPU quickly, leaving the CPU idle while everyone queues up for I/O, and then the cycle repeats itself when the CPU intensive process gets back to the ready queue.


printf("%d",~5); prints out -6 why is that?

That's because computers use $2$'s complement representation of negative numbers. $5$ in binary is $101$. Assume an $8$-bit architecture. Then $5$ would be represented as $00000101$. Hence ~$5$ will flip all the bits which gives $11111010$ which is the $1$'s complement of $5$. Adding $1$ to it gives you the $2$'s complement representation which the computer interprets as $-5$. Hence ~$5=11111010$ is $-5-1=-6$.


Time complexity of matrix multiplication in Big-Align

D.W. is absolutely right about the time complexity for $\bf X$. Meanwhile, I think the paper is vague on what they are saying and not exact on the complexity.

The paper is about network alignment, where $\bf A$ and $\bf B$ are adjacency matrices for bipartite networks, and $\bf P$ can be viewed as a matrix indicating alignment. $\bf P$ is dependent on $\bf B$ based on the equation. So it is better to view $\bf P$ as a function $\bf P(B)$ of $\bf B$, and $\bf X$ and $\bf Y$ are representation of function $\bf P$.

I believe the paper means first "pre"-compute $\bf X$ and $\bf Y$, store the results somewhere, and then for any given $\bf B$, they can compute the value of $\bf P$ given $\bf B$ using the pre-computed $\bf X,Y$.

The problem is, eventually one has to compute $\bf P (B)$ in order to determine the alignment result between $\bf A$ and $\bf B$. The complexity of that computation is $O(n^2d)$, since $\bf B$ is $n\times d$ and $\bf X$ is $d\times n$, and there is no guaranteed zero rows or columns in $\bf B$ or $\bf X$ to reduce computation.

Thus, the computation of $\bf P(B)$ requires indeed quadratic time. It is just that computation of the function $\bf P$ is $O(d^2n)$.


How to detect plurals in English sentences?

Morphological parsing requires a lexicon (stems and their part of speech) , morphotactics (ordering of morpheme classes), and orthographic rules (e.g. fox + PL = foxes rather than foxs).

The preferred approach is to use a composition of finite state transducers to map a surface level representation (e.g., foxes) into its lexical representation (e.g., fox +N +Pl).

For a robust method, you are better off using an existing system like Foma, lttoolbox, or SFST than writing your own system since these systems come with rich morphological data sets.


Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time?

It's impossible (assuming you only use comparisons). First, we augment all elements with indices: $a[i] \to (a[i], i)$. We'll need this when we'll remove the sequence from the array in linear time.
Consider the following sorting algorithm:
def sort(a):
    subseq = get_sorted_subseq(a)  # Your function. Assume takes O(n) time
    b = a.exclude(subseq)          # Since we know indices, takes O(n) time
    return merge(subseq, sort(b)). # Takes O(n) time (see merge sort) + recursive call of size <= n/2

In result, the running time is $O(n + \frac n2 + \frac n4 + ...) = O(n)$, which violates a well-known lower bound for sorting.


DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?

Q1. Of course you can consider a third variable in the recursion, but that would not simplify the analysis. In fact from the case where you put the single horizontal domino, the next step would automatically put the second horizontal one below it. So the given recursion takes a little shortcut.

Q2. That is precisely the point. We have to make sure the analysis steps from existing state to existing state, in a kind of unique way. If we overlook a state we miss possibilities. But here we easily see how the states are related, and how we step from one to another.


If A is not in NP, and A reduces to B, does this mean B is not in NP?

I'm assuming that both $A$ and $B$ are decision problems and that we are talking bout Karp reductions.
Suppose towards a contradiction that $A \not\in NP$, $A \le_p B$, and $B \in NP$.
Then, a non-deterministic polynomial-time Turing machine that decides $A$ would be the following:

Use the Karp reduction $f$ from $A$ to $B$ to transform an instance $x$ of $A$ into an instance $f(x)$ of $B$;
Simulate a non-deterministic polynomial-time Turing machine $T$ that decides $B$ on input $f(x)$ ($T$ exists since $B \in NP$);
If $T(x)$ accepts, accept. If $T(x)$ rejects, reject.

This is a contradiction.


Kernelization algorithm for the following problem

Your problem can be stated as $3$-path vertex cover problem. A simple google search gives this paper. The authors design a kernel of size $5k$ for this problem.


Turing, RAM, or Von Neumann --- which theory/model is the consensus?

It depends on the usage. For basic formal complexity theory, we usually work with Turing machines. However, RAMs and Von Neumann architectures are a better description for a real-world computer, so some may be more interested in them.
From my personal experience, TMs are the most popular in a CS degree, and in theory in general. I barely saw theoretical usages for RAM, and I never saw any Von Neumann architecture used in theory for computation, but I have seen models that describe a CPU in a specific course that covers that.


You can construct a DFS spanning tree or a BFS spanning tree in many ways. You could require the next edge to be traversed should be the cheapest one available, if that helps in any way or if you just like to do that. As long as you are using DFS or BFS, you will end up with a spanning tree.

However, if you do want to always traverse using next cheapest edge among all possible choices, "Queue: a c d b e f h g k m i j k" for BFS should be "Queue: a c d b e f h g k m i j l", which is I assume a typo.

"Is this a MCST?" No, none of the two is a minimum cost spanning tree, which is more commonly called minimum spanning tree (MST). The DFS spanning tree, {(a,c), (c,h), (h,g), (g,f), (f,b), (b,k), (k, j), (j,i), (i, l), (l,m), (m,e), (e,d)} could have less cost if (g,f) is replaced by (c,f). The BFS spanning tree, {(a,c), (a,d), (a,b), (a,e), (c,f), (c,h), (b,g), (b,k), (e,m), (h,j), (k,l)} could have less cost if (b,g) is replaced by (h,g). As you can see, there is no guarantee that a MST can be obtained if you use a DFS or BFS.

In fact, for this particular graph, no matter how you conduct BFS or DFS, you will not end up with a MST.


Rounds in communication complexity - definition

The notion of round should be quite similar to the intuitive idea of  "one step of the protocol". At any round you are allowed to send 1 message (of any size) and/or receive one message. The message you send at round $i$ may depend on all the information you have up to round $i$, but it cannot depend on the message you receive at round $i$ (or later). It follows that any information that depends on the the message you receive at round $i$ may be sent only at round $\ge i+1$. This sequentiality is the core of splitting into rounds, they just formulate the causality of the protocol

Since the above doesn't determine the size of each message sent, one can define the communication complexity to be exactly the number of bits communicated throughout.

As for simultaneous transmission of messages:
In the above informal description I wrote:

  At any round you are allowed to send 1 message (of any size) and/or receive one message.

note the and/or part. If simultaneous transmission is allowed, then each party sends a message and receives one. If no simultaneous messages allowed, then the party either sends or receives a message, but not both. This makes the partitioning to rounds more crisp: every time the sender party changes, it is a new round.

finally, I repeat the recommendation of @hengxin, and refer you to the book of Kushilevitz and Nissan.


Attribute grammars: How are attributes implemented?

Attribute grammars are a conceptual tool. You are mixing this up with implementation details.

There are many parser generators around (check for example the Wikipedia pages on compiler compilers and comparison of parser generators). They all implement some flavor of attribute grammar, in actual use you aren't interested in a parse tree or a derivation. The most used ones are (direct descendants of) old designs, which predate the current object oriented craze, and write parsers  implemented in languages like C, with no objects.


Knight's tour from all starting positions

The Wikipedia article links to several useful papers. According to the paper Solution of the knight’s Hamiltonian path problem on chessboards, there is no such tour; see Theorem 3.1(ii). They show that a knight's tour on the 5x5 board always starts or ends at a corner. It's also easy to see that both endpoint squares have the same color. Since the (5,4) square has a different color than the corners, no knight's tour starts at (5,4).


What's the vertex cover of the null graph?

The minimum vertex cover for a totally disconnected graph is the empty set. A vertex cover is a set of vertices that covers all the edges, i.e. every edge in the graph needs at least one of its endpoints in the vertex cover, so if there are no edges in the graph, no edges need covering.


Instead of solving the question for you, let me show you what steps you need to take in order to solve this problem on your own.

Suppose that $T(1) = T_0$ and $T(2n) = C T(n)$ for all $n$.

What is $T(2)$? What is $T(4)$? What is $T(8)$? What is $T(2^k)$?

Now suppose that $T$ is monotone: $T(n_1) \leq T(n_2)$ whenever $n_1 \leq n_2$.

If $2^k \leq n \leq 2^{k+1}$, what can you say about $T(n)$?
Can you now deduce the asymptotic rate of growth of $T(n)$ for arbitrary $n$?


How many queries does it take to find the best flight?

There are problem parameters where you need $2^k$ queries in the worst case.  I'll prove this by giving an explicit example of an instance where you need $2^k$ queries.

Suppose $X = \{0,1\}^k$ and $A_i = \{x \in X : x_i = 1\}$ (this is without loss of generality in any case).  Suppose $\alpha_i = 1/2^i$.  Pick a single value $x^* \in X$, and define

$$f(x) = 1 - g(x) - 2^{-k-1} [x = x^*].$$

To any query set $X'$ we can associate a single element $m(X') = \arg \max_{x \in X'} g(x)$.  Notice that the results of the query $X'$ depends only on $m(X')$, and there are $2^k$ possible values for $m(X')$.  Thus we can identify each query with the value of $m(X')$, so effectively there are only $2^k$ different queries (where I consider two queries different if their value of $m(\cdot)$ differs; formally, consider the equivalence relation induced by $m(\cdot)$, choose one canonical representative for each equivalence class, and from here on we will assume that each query is one of these $2^k$ canonical representatives).  Now I claim that out of these $2^k$ possible queries, there is only a single one that gives you any useful information about $x^*$.  In particular, the only thing you learn about $x^*$, when you query on the set $X'$, is whether $x^* = m(X')$ or not.  Why?  If $x^* = m(X')$, then the oracle will return $x^*$, and you can recognize that this has happened by looking at the value of $f$.  However, if $x^* \ne m(X')$, then the oracle will return $m(X')$ as well as the value of $f$ on that element, and that is something you could have computed on your own using your knowledge of $g$, so you have learned nothing about $x^*$ other than that it is different from $m(X')$.  Moreover, there is only a single (canonical) set $X'$ where $x^* = m(X')$.

So, you have a search space of size $2^k$, and each query only lets you test a single candidate for $x^*$.  It's like playing a game where I think of a secret number, and you can ask me questions like "is your number 17?" where you replace 17 with any number of your choice.  It's easy to see that this game will require $2^k$ guesses in the worst case, and $2^{k-1}$ guesses on average.

So for that setting of weights, you can't do any better than $2^k$ queries.

(As a generalization, for your Question 2, this will require ${k \choose k'}$ queries in the worst case.)

In contrast, there also exist choices of weights where this allows an efficient solution.  Consider the case where $\alpha_1=\cdots=\alpha_k=1$.  Then you can query on the subsets $X'_0 = \{x \in X : g(x) = 0\}$, $X'_1 = \{x \in X : g(x)=1\}$, .., $X'_k= \{x \in X : g(x)=k\}$.  Then, take the best of those results -- the one that has the smallest value of $f(x)+g(x)$.  After doing $k+1$ queries, this is guaranteed to find you the optimal solution to the problem.  As a generalization, if the set of sums $\{\sum_i c_i \alpha_i : c \in \{0,1\}^k\}$ has cardinality Q, then Q queries suffice to obtain the exact answer.

So, ultimately, the number of queries needed to the oracle depends on the weights.  There are some choices where this might require many queries, and other choices where very few queries suffice.

One nice thing is that you can approximate the optimal value to within an additive error of $\delta$ using $(\sum_i \alpha_i)/\delta$ queries.  In particular, query the subset $X' = \{x \in X : g(x) \le t\}$ for $t:=\delta,2\delta,3\delta,\dots,\sum_i \alpha_i$.  Take the best solution found over all of those queries, and that will be at most $\delta$ worse than the optimum.


Extension of Time Hierarchy Theorem to LBAs

It may help you to remember that LBA's are simply non-deterministic TM's with a limited tape (instead of infinite).


Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid

It is nice that you try to draw a comparison between two similar situations. However, it looks like you are driving too fast to stay on the right road. Henceforth I will be moving somewhat slowly so as to stay on the correct path.
What is generally considered as a distance? You might react, hi, I know what is a distance! Cool then. Here is the widely-agreed general definition of a distance according to Wikipedia as well as my years of practice in math and computer science.

In mathematics, in particular geometry, a distance function on a given set $M$ is a function $d: M \times M \to R$, where $R$ denotes the set of real numbers, that satisfies the following conditions:

$d(x,y) ≥ 0$, and $d(x,y) = 0$ if and only if $x = y$. (Distance is positive between two different points, and is zero precisely from a point to itself.)
It is symmetric: $d(x,y) = d(y,x)$. (The distance between $x$ and $y$ is the same in either direction.)
It satisfies the triangle inequality: $d(x,z) ≤ d(x,y) + d(y,z)$. (The distance between two points is the shortest distance along any path). Such a distance function is known as a metric. Together with the set, it makes up a metric space.

Now let us write out explicitly our distance functions and metric spaces.

In Q1, $f$ defines a distance function on all integers from 1 to $N$ such that $f(i,j) = |A[i] - A[j]| + |i - j|$. All integers from 1 to $N$, together with $f$ forms a metric space, say, $M1$.
Let $\Bbb Z^2$ be all the grid points in 2D. Let $d2$ be the minimal steps needed for you to move from point (x,y) to point (p,q), where each step must be one of the eight kind of steps listed. Then $\Bbb Z^2$, together with $d2$ forms a metric space, say, $M2$. Note that $d2((0,0),(0,1))=1$, $d2((0,0),(1,0))=1\,$ and $d2((0,0),(1,1))=1$.
Denote the Manhattan distance by $ma$, i.e., $ma((x,y),(p,q))=|x-p| + |y-q|$. $\Bbb Z^2$, together with $ma$ forms a metric space, say, $MA$. Note that $ma((0,0),(0,1))=1$, $ma((0,0),(1,0))=1\,$ and $ma((0,0),(1,1))=2$.

Now please follow my observations below.

$M1$ can be considered as a part of $MA$. Why? Define $e$: $i\mapsto (A(i),i)$. Then you can see that $d1(i,j)=ma(e(i), e(j))$, i.e., the distance between $i$ and $j$ in $M1$ is the same as the distance between $e(i)$ and $e(j)$ in $M2$. You can imagine that $e$ just embeds all integers $1, 2, \cdots, N$ in $M1$ to $MA$, keeping their pairwise distances. This is the simple reason why the accepted answer to Q1 can reduce it to given a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance).
$M1$ may or may not be considered as part of $M2$. It depends on how sequence $A$ is defined.

Let $A_k$ be 0 for all $k$. Then $M1$ is just those 1D integers with their usual Euclidean distance among them. It can be embedded easily into the $M2$, keep their pairwise distances.
Let $A_1=0$, $A_2=1$, $A_3=0$, $A_4=1$. Then you will find the four integers 1,2,3,4 in $M1$ has pairwise distance 2 except that $d1(1,4)=4$. However, you cannot find that kind of 4 points in $M2$. This particular example shows that your intuition "both these questions are exactly the same" is suspicious.

The distance in $M2$ is not a Manhattan Distance. You can have 8 points each of which is 1 distance away from any given points in $M2$. For example, $(1,0), (1,1), (0,1), (-1, 1), (-1,0), (-1,-1), (0, -1), (1, -1)$ are 1 distance away from $(0,0)$ in $M2$. However, there is only 4 points each of which is 1 distance away from any given point in $MA$. For example, $(1,0), (0,1), (-1,0), (0, -1)$ are 1 distance away from $(0,0)$ in $MA$. You can also check that $(0,0), (0,1), (1,1)$ is the vertices of an equilateral triangle in $M2$ with side length 1. However, you will not be able to find such an triangle in the Manhattan space $MA$.

Hopefully I have cleared all your doubts. Here are a few exercises for you to arrive at a better understanding of the concepts.
Exercise 0. Verify that $d1$, $d2$ and $ma$ are distance functions according to the definition.
Exercise 1. Suppose $A_1, A_2, \cdots, A_n$ is an increasing sequence of integers. Show that $M1$ can be considered a part of $M2$. Show that $M1$ can also be considered as a part of $MA$.
Exercise 2. Find 4 points in $M2$ whose pairwise distance are the same. Show that there is no 4 points in $MA$ whose pairwise distances are the same.
Exercise 3. Given an $m$ by $n$ grid in $M2$ with its bottom left corner $A$ at $(0,0)$ and its upper right corner $B$ at $(m, n)$. $0\le m \le 20$. $0\le n \le 20$.  Compute the number of paths starting at $A$ and ending at $B$, where you must always move closer to $B$ along the path.


Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity

You may get some inspiration from the articles The world's fastest scrabble program by Andrew W. Appel and A Faster Scrabble Move Generation
Algorithm by Steven A. Gordon.
Both algorithms rely on a clever use of finite automata.

See also this question on Stackoverflow.


Do different variants of Mergesort have different runtime?

Note first that we are talking about an algorithmic idea here; in order to apply a meaningful analysis, we would need at least pseudocode for the three variants.

Note furthermore that the given recurrence is most likely only valid in the limit. It is also not clear what the complexity measure is. Comparisons? In that case, it is clear that none of the adaptions change the measure at all. Basic operations? That would make more sense.

I agree with your reasoning; this seems to be the basic variant. Note again, however, that you'd have to look in the actual algorithm for its analysis. In particular, applying Mergesort in-place is uncommon.
Copying the entire array once adds a linear term globally, so the recurrence does not change. If you are only after $\Theta$-behaviour, ignore it (since the actual algorithm dominates).
Now this adds linear overhead to every call of the routine, changing the recurrence from $\ldots + n$ to something like $\ldots + 2n$. Of course, this results only in a different constant so the result is again not influenced (see Master Theorem).


Does a type-1 automaton always have to terminate?

Pushdown automata do not necessarily halt. They are not forced to read input each step, they can also do so-called $\lambda$-instructions where the tape is not advanced.
Then we can have an infinite loop at a certain tape position.

Likewise, linear bounded automata may loop, and do not always halt. However, they can be simulated by a Turing machine, which stores each configuration, and tests for loops. That is not efficient of course, but can be done. In that way we get halting machines, but of a different type.


To what extent is my interpretation of computable numbers correct?

This is exactly the incorrect interpretation of "computable", resulting of trying to replace the precise definition with (possibly misplaced) intuition.

$\pi$ or any other irrational number also has an infinite digit representation, so according to your logic, it shouldn't be computable. This just shows that it is meaningless to require all of the digits as output, and we actually need a "better" definition.

To fix this issue, we say a number $p$ is computable, if we can approximate $p$ up to any given precision. One way of formalizing this is requiring the existence of a program $M_p(n)$, which upon receiving a number $n$ outputs (in finite time) a number $\hat{p}$ such that $|\hat{p}-p|\le\frac{1}{n}$. The comic actually refers to this definition, as $\pi$ having an infinite expansion does not prevent the robot from dismembering the guy.

If your goal is to avoid dismembering, then it is not clear how to use uncomputable numbers. What exactly is the meaning of calculate $x$? If i ask for some fixed approximation of an uncomputable number, then the robot can give me one (sure, it has no way of algorithmically producing the approximation, but perhaps this is some weird robot with a table of all approximations to any natural constant up to $10^{-100}$). You would probably stand more chance with incompleteness issues, rather than with computability issues. I would ask the robot for a proof in $ZFC$ of its consistency. If it is consistent, he wont find any, and if it isn't, who wants to live anyway.


Saying that you can multiply two polynomials of degree $n$ in time $O(n\log n)$ implies that, in particular, you can multiply degree-zero polynomials, i.e., constants, in constant time.  Clearly, therefore, the claims "multiplying $n$-bit numbers takes time $O(2^{\log^*n}n\log n)$" and "multiplying degree-$n$ polynomials takes time $O(n\log n)$" are relative to different models of computation so are not directly comparable.


There are at least two ways to do it. The first is to take a disjoint sum of $B$ and $C$, which can be done in many ways, for example
$$
\{0x : x \in B\} \cup \{1y : y \in C\}.
$$
The second is to use an NP-complete language $L$ as an oracle. Since any problem in NP reduces to $L$ in polynomial time, you can simulate a $B$-oracle using an $L$-oracle.


Multiplication of polynomials in value representation as done for Fast Fourier Transform

If $P, Q, R \in \mathbb{R}[X], R = PQ$, then for any $x \in \mathbb{R}$, $R(x) = P(x)\times Q(x)$.
It means that if the value representation of $P$ is $[(x_1, P(x_1)); (x_2, P(x_2)); …, (x_n, P(x_n))]$ and the value representation of $Q$ is $[(x_1, Q(x_1)); (x_2, Q(x_2)); …, (x_n, Q(x_n))]$, then the value representation of $R$ is $[(x_1, P(x_1)Q(x_1)); (x_2, P(x_2)Q(x_2)); …, (x_n, P(x_n)Q(x_n))]$.
In your example, $(-2, 1)$ represents a couple $(x_i, P(x_i))$ and $(-2, 9)$ is $(x_i, Q(x_i))$, so it's normal that $(x_i, R(x_i))$ is $(-2, 1\times 9) = (-2, 9)$.


Clarifications about CPU working: as the functions to get the operands are physically generated?

It seems that you have two texts here, one talking about CPUs in the most clumsy way imaginable, and one sounding like a quite reasonable text book, and you can't get the terms of that clumsy text explained by the text book.

I suggest you read that text book, and that text book alone, because the other text isn't going to help your understanding at all. Something like "the control unit produces the sequence of pulses on each control signal line required to implement that instruction" sounds like someone with no understanding at all trying to hide behind big words.


First of all, it's not $2^{h-2}$, it's $2^h$.

The number of nodes $n$ in a full binary tree, is at most $n=2^{h+1}-1$, where $h$ is the height of the tree. A tree consisting of only a root node has a height of 0.

Straight outta wiki https://en.wikipedia.org/wiki/AVL_tree


How to enumerate minimal covers of a set

The problem is equivalent to translating a monotone conjunctive normal form Boolean formula to a monotone disjunctive normal form Boolean formula (also called "monotone dualization" in the literature).

Let us for example take $P = \{\{x,z\}, \{x,a\}, \{y,z \}, \{y,c\}\}$. We can translate $P$ to the following boolean formula: $ \psi = (x \vee z) \wedge (x \vee a) \wedge (y \vee z) \wedge (y \vee c)$ and ask for a valuation of the variables that makes the formula valid, but has as few as possible variables set to true as possible.

If we translate $\psi$ to disjunctive normal form, we obtain:
$$\psi' = (x \wedge y) \vee (x \wedge z \wedge c) \wedge (z \wedge a \wedge c)$$
It is now easy to list all ''minimal'' solutions to $\psi \equiv \psi'$.

The paper "Computational aspects of monotone dualization: A brief survey" by Thomas Eitera, Kazuhisa Makinob, and Georg Gottlob contains a nice survey on existing literature to the topic, including algorithms and complexity results.


Does having one large L1 cache instead of L1 and L2 cache makes computation faster?

Whether a shallower memory hierarchy provides better performance depends on the workload, the microarchitecture, and the implementation technology.

A workload that has a high miss rate for a "conventionally-sized" L1, when run on such a processor, would have more overhead in transferring cache blocks from L2 to L1 and (if writeback) dirty blocks from L1 to L2. In addition, if access to L2 was only started when a miss in L1 is determined, then latency for L2 would be larger (even if L1 in the shallow hierarchy processor used the same memory array implementation as L2).

A microarchitecture suited to modest-sized L1 caches would be biased (relative to one suited to huge L1 caches) toward speed-demon rather than brainiac design, exploiting the lower latency of a cache hit. (Workload, implementation technology, and other factors influence other tradeoffs with respect to speed-demon vs. brainiac.)

If the targeted workload can benefit from extensive hardware threading, providing a larger (and more associative) L1 can be advantageous as the thread-level parallelism can hide greater L1 access latency.

If the implementation technology reduces the latency penalty of a larger cache, the variety of workloads where the tradeoffs (in miss handling overheads and other factors) weigh in favor of a shallower memory hierarchy will increase. For example, in the future it is conceivable that 3D integration might be used for L1 cache and the memory used for this might have relatively high cell access latency (for low power to avoid thermal issues associated with 3D integration), so reduced distance (from 3D integration) and slower memory cells could increase the incentive for a larger L1 cache.

These types of questions become even more complex when one considers that the definition of L1 cache can get somewhat less clear. For example, if what would conventionally be called L2 cache is accessed in parallel with L1 but with higher latency, is it an L2 cache or part of a non-uniform cache architecture L1, especially if some cache blocks are never allocated to the smaller portion of the cache (cache bypassing has been proposed as a mechanism to better utilize capacity and bandwidth). (Even the NUCA L2 cache proposals allowed for transfers between slow and fast portions of L2.) Way prediction can also introduce variable latency for L1; if the prediction mechanism included consideration of expected criticality (and such was used for allocation to near or distant memory arrays within a NUCA design), one might reasonably consider the far memory arrays part of the L1 cache even though their inherent access latency is greater.

(Itanium 2 did not even probe the small L1 data cache for floating-point register loads, so for floating-point data one could almost consider the L2 cache as an L1 cache.)


First off, putting $k$ in the regular expression is not allowed by typical regular expression syntax, unless I'm mistaken. Even adding constant powers is a shorthand notation, not a part of the regular expression formalism. Even if it were possible, using that notation, you could mix $a$s with $b$s, so that not all $a$'s would necessarily come before all $b$s ... so that's not the right direction.

You want strings that begin with $a$s, end with $b$s, and have a total length that is divisible by three. There are a few ways you could go about this. Since you want a regular expression, we might try to develop one directly, without going through a finite automaton.

For a string $x$ from $a^*b^*$ to be in your language, its length must be divisible by three. In other words, it must be true that $|x| = 3k$. Let $x = yz$, where $y \in a^*$ and $z \in b^*$. Then $|x| = |y| + |z|$. So we must have that $|y| + |z| = 3k$. There are only a finite number of ways in which this can happen:

$|y| = 3k_1$ and $|z| = 3k_2$, or
$|y| = 3k_1 + 1$ and $|z| = 3k_2 + 2$, or
$|y| = 3k_1 + 2$ and $|z| = 3k_2 + 1$.

Suppose you can create regular expressions $r_1, r_2, r_3$ corresponding to those three cases. Then you can find the regular expression for your language by taking the union. Let's see how that would work for each case.

This case is easy: the number of $a$'s is divisible by 3, and so is the number of $b$'s. We get a regular expression $r_1 = (aaa)^*(bbb)^*$.
Based on the previous answer, this isn't so bad, either: $r_2 = (aaa)^*a(bbb)^*bb$.
Finally, $r_3 = (aaa)^*aa(bbb)^*b$.

We get an easy regular expression by taking the union of these (I use $+$, but $\cup$ is sometimes also used): $r = r_1 + r_2 + r_3 = (aaa)^*(bbb)^* + (aaa)^*a(bbb)^*bb + (aaa)^*aa(bbb)^*b$.


Term for array of identical type and different types

A structure containing only the same type is homogeneous, and a structure containing different types is heterogeneous.


Does this shuffle have non-zero probability for all permutations?

Yes. Your algorithm can return all permutations.
You can prove it by fixing any arbitrary permutation $\pi$ of the input string str and showing by induction that, after the $i$-th iteration of the outer loop, the first $i$ characters of str can match the last $i$ characters of $\pi$.

For $i=0$ this is trivial.
For $i>0$: Let $n$ be the lenght of str, $x$ be the character in position $1+n-i$ of $\pi$ (indexing positions from $1$), and $j$ be the index of the first occurrence of character $x$ in str with the additional constraint that $j \ge i$ (this index always exists by induction hypothesis). A string temp that will satisfy the induction thesis (as it will be assigned to str) can be found as follows:

copy the first $j-1$ characters from str to temp (by appending them to temp). In particular this copies the first $i-1$ characters of str which, by induction hypothesis, match the last $i-1$ characters of $\pi$.
prepend the $j$-th character of $x$ of str to temp.
append the remaining $n-j$ characters of str to temp.


What is a partially computable function?

The definition of partial function doesn't exclude the possibility that the function is total. On the contrary, every total function is a fortiori a partial function. Perhaps the terminology is unfortunate.

A function from $D$ to $R$ is a subset $f$ of $D \times R$ such that for all $d \in D$ there exists a unique $r \in R$ (denoted $f(d)$) such that $(d,r) \in f$. The domain of $f$ is $\operatorname{dom} f = D$.

A partial function from $D$ to $R$, where $\bot \notin R$, is a function $f$ from $D$ to $R \cup \{\bot\}$. When $f(d) = \bot$, we say that $f$ is undefined at $d$. The domain of $f$ is $\operatorname{dom} f = \{d \in D : f(d) \neq \bot\}$. If $\operatorname{dom} f = D$ then $f$ is total. For every partial function $f$, $f|_{\operatorname{dom} f}$ is a total function.

As you can see, a partial function is a function which can be undefined for some of the inputs; a total function is a partial function which happens to be defined everywhere.

Now regarding computability. Every program computes some partial function $f$ from $\mathbb{N}$ to $\mathbb{N}$; if the program doesn't halt on some input $x$, then $f$ is undefined on $x$, in other words, $f(x) = \bot$. A computable function is one computed by an algorithm which always halts.


Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The problem is in your poor definition of "algorithmically random number" as applied to irrational numbers. In particular:

has the same length (number of bits) as the number itself.

has no meaning if the number is of unbounded length.
Your Wikipedia link gives better definitions, which don't have this problem. For example (and paraphrasing formatting):

Kolmogorov complexity [...] can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits). It assigns to each such sequence $w$ a natural number $K(w)$ that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output $w$ when run. Given a natural number $c$ and a sequence $w$, we say that $w$ is $c$-incompressible if $K(w) \geq |w| - c$.
An infinite sequence $S$ is Martin-Löf random if and only if there is a constant $c$ such that all of $S$'s finite prefixes are $c$-incompressible.

This is a test passed by $\sqrt{e}$ by setting $c$ a bit larger than the program to generate $\sqrt{e}$ and including in it the length to generate.


Locality-sensitive hashing random projection

No.  The statement you're reading is correct.  Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens.  The set of points $v$ such that $v \cdot r = 0$ is a line; the set of points $v$ such that $v \cdot r \ge 0$ is a half-plane (e.g., the half-plane above that line).


Listing all prime numbers less than an integer N

Yes, but only after we have stated what is considered memory used by an algorithm or program.

For this particular problem, I would like to use one of the simplest choices. The memory used by the program is the extra or temporary space used excluding the input and output. Furthermore, each variable (that does not share its storage with others) uses a unit of space. One might argue the output should count towards memory usage. My point is to let us choose a usage model so that we can concentrate on the most relevant and interesting part, although in another situation, how to reduce the memory used by the output might be the more significant part.

Here is the snippet that use 3 units of memory, where I remove the call to sqrt(i). Each of $n$, $i$, $j$ uses 1 unit of memory. I comment out the output code to make it clear that its memory usage is not considered.

int n = N; // N should be given elsewhere
for (int i=2; i<n; i++)
    for (int j=2;; j++)
    {
        if ( j*j > i) {
            // cout << i << " ";
        }  else if (i % j == 0)
            break;
    }

But wait, how can we check j*j > i? Even if we assume the computing machine can compute j*j magically without using extra memory, it still needs to store the result of j*j so as to compare with i. So it is only reasonable that we add 1 or more unit of memory usage here. Then how about i % j? We would like add 1 or more unit of memory usage here.

If we dig deeper, we will ask whether those 2 and 0 in the program count towards memory or not. We may have to ask during the program execution, doesn't it need to use some space to remember where it is executing and how to jump around? If those memory are needed, can we reuse them during different execution time?

The more we study this way, the more uncertain the answer becomes. This is, in fact, the truth. It is almost impossible to get an accurate usage of memory theoretically unless we have an accurate model of storage and computation specified down to the bit. When we do have that accurate model, an accurate analysis to the bit may become so tedious and distracting we might lose the big picture.

The way out to get a healthy picture is the big $O$ or $\Theta$ notation. We will simply say that this program use $O(1)$ or $\Theta(1)$ memory. That is, for a reasonable model of storage and computation, there is a constant $C$, for any give $N$, the program will use less than $C$ units of memory. In practice, we usually mean a small or reasonable $C$.

By the way, the program in the question misses primes 2 and 3.


First of all, encoding is up to you — you get to decide the answer to the question you state.

Let's consider a more generic situation, in which you want to serialize (convert to bits) a sequence of values $x_1,\ldots,x_k$. If you know ahead of time what the length of $x_i$ is, then the most efficient encoding would be to put together all the bits of all values (no spaces!). (In practice, we also need to pack them into bytes, since data is passed around in byte chunks.)

If you don't know the length in advance, then there are several option. One option is to use some self-terminating encoding. For example, you could preface each bit by 0, and end the stream by a 1. A 2-bit string $b_0b_1$ would be encoded by $0b_00b_11$. Such an encoding is not very common. Another option is to store the length somewhere — this is quite common. For example, JPEG files store the dimension of the picture in a header. A third option is that the length, while not predetermined, is one of very few options. In that case it suffices to store just the index of the option in some header. This is probably what happens in cryptographic protocols.

Finally, there seems to be a basic misunderstanding in your question. Information is passed around in bytes. When you have a stream of bits, you pack them into chunks of 8 bits and send them in that way. There are only two options for bits — they can be either 0 or 1. What beginners sometimes do is send the bitstream as an ASCII or Unicode string, which does accept 0s, 1s, and spaces (as well as many other letters). However, this is very wasteful, spending at least 8 bits per one input bit.


Solving Recurrence Relations 'Chip & Conquer'


More the number of for loops greater the problems solved

Let us consider the LOOP programming language. For a program $f$, denote by $f_{\max}(n)$ the maximal value of a variable at the end of the program, given that initially, all variables are at most $n$. If $f$ has only one loop then $f_{\max}(n) = O(n)$. In contrast, using two nested loops you can compute the product function, and the resulting program $g$ satisfies $g_{\max} = \Theta(n^2)$. This separates $P_1$ and $P_2$.

More generally, $f_{\max}$ can be bounded in terms of the maximum nesting depth of loops in $f$. If the maximum nesting depth is $d$, then the growing rate of $f_{\max}$ is comparable to the $d$th level of the Ackermann hierarchy. This allows us to separate $P_i$ and $P_{i+1}$ for every $i$.


Is there a philosophical counterpart question to P != NP?

Shortly: No.

Gödel motivation was to give closure, in a sense the very same as Hilberts to make one connected field. This is meta-science (meta-mathematics) but not based on philosophy but mathematics.
The concept of truth was connected with logic (in logic it is just well defined symbol), and the idea was to give axiomatic (absolute truth), in order to achieve that the one obvious idea is to give a function (even oracle) that evaluates given object (explicitly loose statement, as it was (and is) underdefined). It was meant to rescue the concept (the truth depends on context, field given, e.g. in Psychology the absolute truth would not be of that much use), which is required to prove anything.

Gödel started as mathematician, the pursuit of closure pushed him to mathematical philosophy (self-studied, not at the professional level), which was used as meta-science, meta-logic, but every time any advancement was made it was back in the field of mathematics. The urge to prove was bigger than to disprove so he picked contraposition to get back to mathematics (CS). After that he succumbed into idealism.

Any proof in given field must be proved in given field, using provided tools, meta-tools and must be verified (and understood) by people from that field otherwise this is just loose statement. In example $P vs NP$ cannot be proved using philosophy, where it is undefined problem. Unfortunatelly it would require to take understanding of the whole field, define the problem using strict notation and use M or CS tools.

The philosophical counterpart does not exist, moreover in that field the $P vs NP$ problem might be defined with assumption of one being true, both or neither. Nothing prevents from defining problem as exclusive alternative or nonexclusive alternative. The concept will be well defined in any cases giving the frame of reference, outcomes and closed entity (world) where we can go further with provided axioms (and this is what we do in CS, there are conditional proofs "if P = NP then ..."). But the task to actually prove it is in the field of Mathematics or Computer Science.

There is no counterpart theory or framework of inference. The sentence you have provided is not proper. Any kind of paradox, tautology or too loose statement to deal with in some other field gives nothing and proves nothing. For the sake of argument if there were counterpart theory it still would be too weak to infer anything.
The paradox is something that goes beyond formalism or simply includes mistakes at language level - which are totally irrelevant when analysing in philosophy since it can be resolved at any level giving explicit assumptions.


Struggling to understand the symbolism around the big oh formal definition

T(n) is a function that has been conceived in a effort to describe the behavior of a program. There are many other possibilities, but that should be the case, in the context of computer science.

That doesn't mean we will actually write T(n) down, because i) it can be too complicated, and ii) it is probably not essential to do so.

Then comes f(n), which is another function. It indicates a set of functions, to which T(n) belongs, denoted by O(f(n)). Now, that doesn't say much about f(n), but we can use this construct to divide the universe of functions in categories, each one corresponding to a different f(n), chosen from a list of "archetypal" functions.

The definition of O(f(n)) may seem tricky, but it is consistent, and general, which is important if you're going treat the subject scientifically.

This division has immense practical benefits, since it gives us a language to talk about the behavior of programs in a way that is both precise and meaningful. Each of these function categories has functions that have something important in common, in the way that they grow.

The notation has limits, of course. It's not the only tool in our belt.


Let's try an example. Let's say you're trying to prove the following:

Simple Theorem over the natural numbers: If $n$ is even, then $n+1$ is odd.

What he's trying to say is that you don't need an independent proof that $n$ is even. In the natural numbers, this isn't even true, since not all numbers are even. What he's trying to say is that when trying to prove an implication like the Simple Theorem above, you're allowed to introduce the assumption that $n$ is even, and from that assumption, together with whatever other axioms you're using, try to prove that $n+1$ is odd. If you succeed in this, you can now correctly conclude that the implication is true.

From his paper:

  The rule makes intuitive sense, a proof justifying A ⊃ B true assumes, hypothetically, the left-hand side of the implication so that A true, and uses this to show the right-hand side of the implication by proving B true. The proof of A⊃B true constructs a proof of B true from the additional assumption that A true.

The whole painful stuff with the bars and labels is a variation of the pain that comes with other deduction systems when you're trying to create a proof context to hold the introduction of an assumption. When these contexts get nested in a complicated proof, it requires machinery analogous to lexical variable scoping rules in programming languages. The assumptions have to come and go properly so they don't allow unsound deductions in other parts of the proof.

EDIT: per request of original poster.

OK, let's dig into this some more. I'm going to use some different notation. The notation

$$
\Gamma \vdash \sigma
$$

means some set of axioms $\Gamma$ proves some formula $\sigma$, where the turnstile $\vdash$ means "proves". Now the inference rule we're looking at can be written like this. We can conclude

$$
\Gamma \vdash A \rightarrow B
$$

if we can prove

$$
\{\Gamma; A\} \vdash B
$$

where the semicolon means we've added formula $A$ to the set of axioms $\Gamma$. Note that this also creates what I've been calling a "proof context" where we're keeping track of assumptions we've been making. The Pfenning paper uses labels on bars to do the same thing.

Let's try it on a complicated example with nested proof contexts: prove the tautology

$$
A \rightarrow (B \rightarrow (C \rightarrow B))
$$

In our notation, proving this tautology looks like this:

$$
\{\} \vdash A \rightarrow (B \rightarrow (C \rightarrow B))
$$

That is, $\Gamma$ is empty since we're proving a tautology.

Here we go, using our rule of inference.

We can prove

$$
\{\} \vdash A \rightarrow (B \rightarrow (C \rightarrow B))
$$

if we can prove

$$
\{A\} \vdash B \rightarrow (C \rightarrow B)
$$

Let's keep going.

We can in turn prove

$$
\{A\} \vdash B \rightarrow (C \rightarrow B)
$$

if we can prove

$$
\{A, B\} \vdash (C \rightarrow B)
$$

One more application of our rule:

We can prove

$$
\{A, B\} \vdash (C \rightarrow B)
$$

if we can prove

$$
\{A, B, C\} \vdash B
$$

But this follows easily: since B is already an axiom, it follows that we can prove it. But we only got this axiom from our inference rule that allowed us to add it safely.


Why does Python allow stand-alone expressions?

The python creators decided that any expression is valid as a statement. While not all expressions are useful as statements, it would make the language more complex to have to remember which expressions may be statements and which can not.
A second reason is that many expressions that may seem "safe" can still have side effects, making it useful to evaluate them without using the return value.
Operators
Operators are the most obvious examples of expressions that you can easily add side-effects to. In your example 0 < 0 is equivalent to 0.__le__(0). You can overwrite the __le__ method or any operator special method to do whatever you want, including writing to a file or incrementing a counter.
You can also evaluate operator expressions just to make sure the types are compatible. For example, if you are going to do a very long computation on variables a and b that ends by dividing some value based on a by b you might evaluate a/b at the start of your function as a quick and dirty way to make sure the types can be divided and that b is not zero before spending a lot of time calculating.
Strings
Strings don't typically have any side effects, but string expressions are frequently used in python code as a type of comment. Specifically, docstrings are triple-quoted strings right after the heading of a class or function, and will be assigned to __doc__.
Variables
Evaluating variables has one important function: It will crash if the variable doesn't exit. For example, suppose I have a module server.py that must be configured server.host = 'localhost' before starting. I could write this:
try:
    host
except NameError:
    raise ConfigurationException("must set host")

Tuples
The tuple expression a, b where a and b are expressions will evaluate any side effects from a  b.
Others
Ok, there is little use for a loose None. However, only disallowing None, True, False, Ellipsis, NotImplemented, and ... would be a unnecessary special case that would make the language harder to learn for little benefit.


Does my "hollow list" structure exist already?

This is a sparse array data structure, but I haven't seen this exact data structure before.  It looks like your code builds a balanced binary tree, but with a particularly clever representation in memory.

One difference between other balanced binary trees is that the running time of your approach is $O(\lg m)$ where $m$ is the largest index written, whereas other balanced binary tree data structures (e.g., red-black trees) have a $O(\lg n)$ running time where $n$ is the number of indices written to.  Since $m \ge n$, in principle your approach might be slower if $n$ is small (few elements have been written) but the indices are large.  However in practice I don't expect this to make much difference, ordinarily.


Late and early only make sense when building the LTS. The notion of bisimulation stays the same.

However there are several notion of bisimilarities in the π-calculus for example. These are related to how new names are handled. It happens in the π-calculus because it is a name-passing process calculus. There is no such thing in CCS where names cannot be sent.

Usually, the notion of barbed equivalence or congruence is more unanimous. Then you have to prove the equivalence with the late/early/open bisimilarity to give it some credit.

To be quick about it, early transitions are that way:
$$
a(x).P \stackrel{a(b)}{\longrightarrow} P[b/x]
\qquad
\begin{array}{c}
P \stackrel{a(b)}{\longrightarrow} P'
\quad
Q \stackrel{\overline ab}{\longrightarrow} Q'
\\ \hline
P\mid Q → P' \mid Q'
\end{array}
$$

and late are like this:
$$
a(x).P \stackrel{a(x)}{\longrightarrow} P
\qquad
\begin{array}{c}
P \stackrel{a(x)}{\longrightarrow} P'
\quad
Q \stackrel{\overline ab}{\longrightarrow} Q'
\\ \hline
P\mid Q → P'[b/x] \mid Q'
\end{array}
$$

You see the difference is subtle and is just about where the substitution is done. My preference go to the late one because when I reason about processes, I just remember that the $x$ in the transition $a(x)$ is bound. Also the late bisimilarity is the strongest one (beside the open one which is really not the same) and the processes that are early but not late bisimilar are kind of weird, so you don't lose much.


Huck Bennett has answered this question on cstheory.SE here.

  This is a special case of the Travelling Salesman with Neighborhoods
  (TSPN) problem. In the general version, the neighborhoods need not all
  be the same.

  A paper by Dumitrescu and Mitchell, Approximation algorithms for TSP
  with neighborhoods in the plane, addresses your question. They
  give a constant factor approximation algorithm for a slightly more
  general problem (case 1), and a PTAS when the neighborhoods are
  disjoint balls of the same size (case 2).

  As a side comment, I think Mitchell has done a lot of work on
  geometric TSP variants, so you might want to look at his other papers.


Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation

The asymptotic complexity is the same (assuming you treat each floating-point operation as a constant-time operation, which is probably the right assumption).  The practical running time may be different.  Asymptotics ignores constant factors, but constant factors can be important in practice.

The way to tell how much faster it is in practice is to implement it and do some experiments, i.e., benchmark it on realistic workloads.  Asymptotic analysis probably won't be very helpful in this case for predicting how much faster it will be.  No one is likely to be able to give you a prediction for what the results of those experiments will be; you'll just have to try it and see.


Proving property of a term using Induction

A term is defined recursively.  You can do induction on recursive types, using structural induction.

For instance, suppose we say that a term is something of the form

$c$ (a constant), or
$t_1+t_2$, where $t_1,t_2$ are terms.

Then structural induction is (loosely) similar to doing a proof by (strong) induction on the size of the tree.  You prove that the property holds if the term has the form $c$ (that's the base case).  Then, you prove that if the property holds for terms $t_1$ and $t_2$, then the property holds for the term $t_1+t_2$.  You can probably see how to generalize this to terms whose syntax has a more complicated definition.


The most important optimization is to save resources, not only avoid traversing the full square. For this reason the best option is to calculate the upper quarter of circle (hull) and then use scanlines - traverse row for fixed number of steps. Exploiting symmetry by calculating octant algorithm may not be the best option due to random access in the array and subtraction used (it should make no difference, but it happens). This is know as the midpoint circle algorithm.

Standard way is to calculate 1/8 of the circle, reflect it and use the hull, dividing circle into rows. The naive algorithm to calculate starting points uses round operation, which is time consuming (but still worth something due to actual avoiding square traversal). More optimized version is due to Bresenham circle which avoids rounding operation.


How are programs split up into pages in Memory Paging?

The program is not really split up into pages. The program is unaware of where it lands in physical memory. This is all the essence of paging.
For example, if you take Linux on x86 CPUs and the C++ language, you will have the compiler generating machine code which will be linked into a final executable which has a .ELF extension.
ELF files support virtual addresses. ELF files specify the virtual addresses at which the code is going to land. The linker or compiler is going to write the starting virtual address at which the code is going to land. The default virtual address is 0x400000 with ld and g++.
So basically, the ELF executable specifies where the program lands in virtual memory. Since the default virtual address is always 0x400000, then a lot of programs will have that starting virtual address. The kernel thus creates page tables for each process (each executable that you start). These processes will land at different places in memory even if they all have the same virtual address. This is due to the fact that they have different page tables.
In fact Linux holds a page struct for every physical page in the system. This takes up quite some space and there have been discussion to change this pattern. I don't know if it is yet done. The page struct allows the kernel to map all physical pages to know what every page is used for.
So when you start an executable/process the kernel determines what physical pages are available and set up the page tables for that process so that virtual address 0x400000 lands there once translated by the MMU.
The JMP 8 instruction will be translated by the MMU before being placed on the address bus. So the 8 is a virtual address. This virtual address is determined by the compiler and the linker.
There are 2 different kinds of JMPs. Relative JMPs and absolute JMPs (far JMPs). Relative JMPs are calculated as an offset from the current position in the code. Far JMPs in the meantime are calculated as absolute address. They contain a virtual address where the JMP should go. They can JMP anywhere in RAM.
For example,
label:
jmp label

is a relative JMP, while
jmp 0x8000

is an absolute JMP. These jumps are calculated by the compiler and linker. The compiler places the functions you call from main at different positions in the code that it places in the relative JMPs. Far JMPs are mostly used in operating-system development.
The linker plays the role of linking several files. So you have a symbol section in the ELF file. This symbol section contains entries which associate each symbol with an address. I'm not totally aware since I never wrote an ELF interpreter. What I can tell is that the address is the address of the beginning of something like a variable or mostly functions. What happens is that the linker takes the symbol and checks it against other object files you included in the linking command. If it finds the symbol in another file, it places the address of the code in the relative JMP to tell the code where to JMP to get to that function. That is why it is called a linker, because it resolves links. This is why you have to include header files in C++. You tell the linker where to find these other symbols (functions, variables, classes).


Under which conditions a given program is deterministic on x86_64 machines?

I don't have all the details, but I think the conditions are not easy to identify.  I am aware of several categories of challenges:

Many instructions may have undefined behavior (e.g., the opcodes are reserved, or the spec does not define their behavior for some inputs), and thus it is possible that their behavior might vary on different CPU models.  For instance, many instructions specify that some aspects of their effects are undefined, e.g., the effect on some flag bits may be undefined.  As another example, SHLD says that the contents of the destination operand is undefined in certain cases.

There are certain instructions that explicitly perform I/O or read external data: e.g., IN, OUT, RDTSC, RDTSCP, RDRAND, RDSEED, etc.

Concurrency can cause nondeterminism, so you would have to rule out all associated instructions (e.g., LOCK).  Also I think there is a lot of nondeterminism in the memory model when there is any concurrency or shared memory.  So, you have to ensure that no other process/thread/etc. has access to any shared memory.  You'll also need to make sure that the program does not make a system call to the OS to initiate DMA.

System calls or interrupts (e.g., the INT, SYSCALL, SYSENTER instructions) might not have deterministic behavior.

I'm not sure, but I suspect reading machine state might have nondeterministic behavior, e.g., reading the machine status word, global descriptors, reading timers and performance counters (e.g., RDPMC), CPUID, model-specific registers (RDMSR), etc.

Supervisor-level / kernel-mode instructions are complex to analyze and I don't know whether they will be deterministic.  If you want to ensure determinism I would suggest you ensure the code runs in user mode (e.g., ring 3).  For instance, I don't want to think about instructions like VMLOAD, VMRUN, modifications to the page tables, etc.

The initial state of memory before it is written to is not defined and thus any program that reads from uninitialized memory may trigger nondeterministic behavior.  On the other hand, many operating systems zero out pages before handing them to the program, which eliminates this issue.

This is a complex topic and I wouldn't be surprised in the least to discover that I have missed other important challenges.
I don't know whether floating-point arithmetic is guaranteed to be deterministic and bit-for-bit identical on all platforms.
I think it is plausible that, given enough effort, you could come up with a subset of x86 instructions and an initial state for the process where, if the process only executes those instructions, its behavior will be deterministic.  However, coming up with this subset might be quite tricky and require a lot of time with the Intel manual.  Enforcing that the process only executes instructions from this subset will be quite challenging, given the ability to execute self-modifying code and runtime-generated code.  It is also not clear how you will deal with instructions where some of their results are undefined.  For instance, it's not clear how you'll deal with instructions that leave some of the flags undefined (and there are many of them), as there is a risk that a later instruction reads one of those flags whose value is undefined, and this could introduce nondeterminism (the spec makes no promises that undefined values will be a deterministic function of the inputs you care about).  So, I suspect ensuring determinism at the x86 level would be a non-trivial project.
If it is helpful, I know of some efforts to enforce determinism in the context of higher-level programming languages, where the enforcement becomes easier; you could ask a separate question about that, if it is of interest.


The case $k \ge n$ is trivial as you can give different value to every variable, which satisfy all inequalities and thus is optimal. So let's consider $k < n$.
This problem can be considered as building a paritition of the $n$ variables in $k$ subsets. All inequalities involving two variables in the same subset are unsatisfied, any other is satisfied.
I would first build an efficient structure to count the number of inequalities involving each pair of variables. Basically this is a $n^2$ array, built in $O(m)$. In case $m << n$, a graph may be more efficient than a sparse matrix.
Then, let's take arbitrarily $k$ variables and distribute them into the $k$ subsets (give them the $k$ different values). Any inequalities involving these first variables is satisfied (then the arbitrarily may target greedily the largest values in the array).
Then loop on the remaining variables. For each $x_i$, evaluate $A^i_k$, the number of unsatisfied inequalities (considering only the variables assigned so far), for each of the $k$ possible assignment. For this, one has to consider every assigned variable in the same subset, this step is $O(n)$.
Let's call $S_i = \sum_k A^i_k$.
By assigning $k_0$ to $x_i$,
you unsatisfy $A^i_{k_0}$ inequalities but satisfy $S_i - A^i_{k_0}$ ones.
So by picking $k_0$ that minimizes $A^i_{k_0}$, you unsatisfy at most $S/k$ inequalities, satisying at least $S(1-1/k)$ others. So overall you guarantee to satisfy $m(1-1/k)$ inequalities (and clearly $(1-1/k)OPT$ ones).
This achieves $O(m + n^2)$ in time and $O(n^2)$ in space.


Problem complete for the class of ALL languages

You haven't specified your notion of reduction, so I will assume that you choose some countable class of functions $\cal F$ which can be used for reductions (any subset of the computable functions would work here). Let $\cal L$ be any class of languages over some fixed alphabet $\Sigma$, say $\Sigma = \{0,1\}$. A language $K$ is hard for $\cal L$ (with respect to $\cal F$) if for every $L \in \cal L$ there exists $f \in \cal F$ such that $x \in L$ iff $f(x) \in K$. If also $K \in \cal L$ then we say that $K$ is complete for $\cal L$.

I will now show that no language is hard for $\mathsf{ALL}$. Suppose that $K$ were $\mathsf{ALL}$-hard. Let $f_x : x \in \Sigma^*$ be an enumeration of the functions in $\cal F$ (such an enumeration exists since both $\Sigma^*$ and $\cal F$ are countable). Define a language $L$ by
$$
L = \{x : f_x(x) \notin K \}.
$$
Since $L \in \mathsf{ALL}$, there exists a function $f \in \cal F$ such that for all $x \in \Sigma^*$, $x \in L$ iff $f(x) \in K$. Since $f \in \cal F$, there exists $x \in \Sigma^*$ such that $f = f_x$. For this particular $x$, $x \in L$ iff $f_x(x) \in K$. However, by definition $x \in L$ iff $f_x(x) \notin K$.


What is the relation between Time Sharing operating systems and Round Robin CPU scheduler?

No.  A time-sharing computer switches between processes in some way or other.  A time-sharing computer with round-robin scheduling switches between processes in a particular way.  For instance, suppose there are three processes, A, B, and C.  A round-robin scheduler would switch between them in the order ABCABCABCABC etc.  Some other scheduler might switch between them in the order AABAABAACAABAABAAC (for instance).  Both are examples of time-sharing, but the latter is not a round-robin scheduler.

I suggest reading https://en.wikipedia.org/wiki/Scheduling_(computing).


Define C = { $L | L$ is decidable by a turing machine with at most 42 states }

Notice that there is a finite amount of such languages, as there are a finite amount of turing machines with 42 states. for that reason, we have $C\ne\emptyset, \sum^*$

By Rice's theorem, the language $S=$ { $w | L(M_w) \in C$ } is undecidable. This language is precisely the language in question


Maximal size of a set of ordered words such that no pair of letters occurs twice

There is a simple upper bound of $$\frac{\binom{n}{2}}{k-1},$$ following from the fact that there are $\binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.

There is an almost matching lower bound of
$$
\frac{\binom{n-k+1}{2}}{k-1}.
$$
This shows that for fixed $k$, the answer is asymptotically
$$
\frac{n^2}{2(k-1)} \pm O(n).
$$

For every $c \geq 1$ and $1 \leq d \leq c$, we can consider the collection of ordered words of the form
$$
d,d+c,\ldots,d+(k-1)c \\
d+(k-1)c,d+(k+1)c,\ldots,d+2(k-1)c \\
\ldots
$$
These collections for all $c,d$ have disjoint pairs. For a given $m \leq n$ and $c$, there is a word of this type if $m-(k-1)c \geq 1$, that is, if $c \leq \frac{m-1}{k-1}$. Therefore, the total number of words is
$$
\sum_{m=k}^n \left\lfloor \frac{m-1}{k-1} \right\rfloor.
$$
We can estimate this sum roughly by
$$
\sum_{m=k}^n \left(\frac{m-1}{k-1}-1\right) =
\sum_{m=k}^n \frac{m-k}{k-1} = \frac{\binom{n-k+1}{2}}{k-1}.
$$


Find plane within margin of error of >50% of points

One reasonable approach is to use RANSAC.

Pick three points.  Find the plane that goes through them.  Iterate through all the points and keep the points that are near that plane (the inliers) and discard the rest (the outliers).  If fewer than 50% of the points are inliers, discard this plane.  Otherwise, discard the plane you have so far and use linear regression to find the best plane that fits the inliers as well as possible.  That's a candidate plane.

Repeat this 1000 times, to get 1000 candidate planes.  Take the best one.  You can measure how good a candidate plane is by taking the average distance from the plane to each point, averaged over all the points that are close to that plane (ignore the ones that are far away; if 50% or more are far away, discard the plane).


Sorting criteria for Kruskal's algorithm

Yes, for Kruskal's you have to sort it in ascending order of weights, for precisely the reason that you gave.
There is, however, another algorithm, namely Reverse-Delete which is essentially the opposite of Kruskal's. You start with the original graph, and process edges in descending order of weight. Then we remove each edge while the graph is still connected.


How to construct a grammar that generates language L?

One possible grammar is: $G = (N, \Sigma, P, S)$,
where

$N = \{S,U,V\}$

$\Sigma = \{a,b,c\}$

$P = \{
  S \to baUV,
  U \to ab|bUc,
  V \to a|aV
\}$

The key observation here is breaking $bab^nabc^na^p$ into 3 parts, $ba$, $b^nabc^n$, and $a^p$, one fixed, one growing bidirectionally, and one simple repeatition. Express the growing patterns first, then merge them along with the fixed parts.


Proving the Language is not regular for $(a^n)^n$

You're on the right track. Here are a few missing details. First, note that $(a^n)^n=a^{n^2}$, so you want to prove that $L=\{a^{n^2}\mid n\ge 0\}$ isn't regular.

Assume $L$ is regular. Since $L$ is infinite, there's an integer $p$ for which the PL applies, so choose $s=a^{p^2}$ and write $s=xyz$ with $|xy|\le p$ and $|y|\ge 1$. Hence, $y=a^k$ with $1\le k\le p$. Then the PL implies that $xz\in L$. Thus we know that $|xz| =p^2-k$, [You goofed here.] and since $k\le p$, we have
$$
|xz| =p^2-k\ge p^2-p >p^2-2p+1=(p-1)^2
$$
and so $(p-1)^2< |xz|<p^2$ and so $xz\notin L$, since $xz$ lies strictly between two adjacent (lengthwise) elements in $L$ and so can't be in $L$, a contradiction.

[The only way this could fail is if $-p\le -2p+1$ and that only holds when $p\le 1$ which we know must be true, since $p$ is the number of states of a FA that accepts $L$ and clearly a one-state FA won't recognize $L$.]


Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free

You've almost got it. Consider that $L_1$ is simply the concatenation of $L_a$ and $L_c$, where $L_a = \{a^ib^{2i} \;|\; i ≥ 0\}$ and $L_c = \{c^j \;|\; j ≥ 0\}$, since the two parts of each sentence are independent of each other.

That should suggest a grammar which starts with the production $L\to AC$, and which then proceeds to define $A$ and $C$ in the obvious way.


Why not do these checks on the number of clauses in 3-SAT?

There's no real reason not to do your checks given that they are computationally tractable, but there's very little point in doing them either.  Your checks make determining the satisfiability of easy random 3-SAT instances easier.  SAT solver authors are interested in algorithms that make hard SAT instances easier.

For random 3-SAT, the hardest instances are known to be near the phase transition point where instances on one side are almost always satisfiable and instances on the other are almost always unsatisfiable.  That transition point has been observed empirically to be when the ratio of the number of clauses and the number of variables is around 4.26.  Your checks would never be helpful with such instances.


Rules of converting a weighted digraph to an undirected graph?

There aren't any rules. Do whatever is most appropriate to your specific situation. What do the weights mean? That should probably tell you what weights to use in the new graph.

If there is no meaning, translation doesn't make sense: translation is, by definition, an operation that preserves meaning.  For example, suppose I give you the following exercise:

  Translate the program function int int (hello_) repeat end begin int into Java.

The program doesn't mean anything so it can't be translated. You can't possibly give me a Java program and say "This is the right one" because there's no definition of "right". Similarly, without saying what the edges and weights of some digraph mean, there's no way to justify the claim "This undirected graph is the correct translation."

There's no intrinsic equivalence between directed and undirected graphs. Usually, one associates an undirected graph with the directed graph in which every edge is replaced by a directed edge in each direction.  In many contexts, these behave the same way (e.g., if I can get from A to B in the graph, I can follow the same route in the digraph). In other circumstances, though, they might be different. For example, an undirected edge might represent the existence of a two-way road between two cities, whereas a pair of directed edges might represent separate one-way roads in each direction.


Why is it that Ternary search trees are memory efficient?

Tries

Tries store strings character by character. See the figure below of a tree that represents the same set of 12 words.

Each input word is shown beneath the node that represents it. In a tree representing words of lowercase letters, each node has 26-way branching. Searches are very fast: A search for "is" starts at the root, takes the "i" branch, then the "s" branch, and ends at the desired node. Unfortunately, search tries have exorbitant space requirements: Nodes with 26-way branching typically occupy 104 bytes, and 256-way nodes consume a kilobyte. Eight nodes representing the 34,000-character Unicode Standard would together require more than a megabyte!

Ternary Search Trees

Ternary search trees combine attributes of binary search trees and digital search tries. Like tries, they proceed character by character. Like binary search trees, they are space efficient, though each node has three children, rather than two. A search compares the current character in the search string with the character at the node. If the search character is less, the search goes to the left child; if the search character is greater, the search goes to the right child. When the search character is equal, though, the search goes to the middle child, and proceeds to the next character in the search string.

The figure above shows a balanced ternary search tree for the same set of 12 words. The low and high pointers are shown as solid lines, while equal pointers are shown as dashed lines. Each input word is shown beneath its terminal node. A search for the word "is" starts at the root, proceeds down the equal child to the node with value "s," and stops there after two comparisons. A search for "ax" makes three comparisons to the first letter ("a") and two comparisons to the second letter ("x") before reporting that the word is not in the tree.

Searching for a string of length k in a ternary search tree with n strings will require at most O(log n+k) comparisons.

The primary challenge in implementing digital search tries is to avoid using excessive memory for trie nodes that are nearly empty. Ternary search trees may be viewed as a trie implementation that gracefully adapts to handle this case, at the cost of slightly more work for full nodes. Ternary search trees combine the best of two worlds: the low space overhead of binary search trees and the character-based time efficiency of digital search tries.

Hope it helps! Reference: Link