Does This Prove $P \neq NP$? (Randomly Populated Binary Tree)

No, it doesn't. Your input size is exponential in terms of n. So the proper way to look at it would be to define k=2n-1 and solve the problems in terms of k.


Example for a non-trivial PCP verifier for an NP-complete problem

Following up on a comment by sdcvvc I checked out example 11.7 in Computational Complexity: A Modern Approach by Arora and Barak (Draft of 2008). There, the authors describe a "PCP algorithm" for the problem Graph Non-Isomorphism (GNI):

  Input: Two graphs $G_0$ and $G_1$ with $n$ vertices each.

  Output: Accept if and only if $G_0$ and $G_1$ are not isomorph (write
  $G_0 \not\equiv G_1$).

We denote the certificate (they call it "proof") by $\pi$ and with $\pi(i)$
the $i$-th bit of $\pi$.

The algorithm $A$ proceeds as follows:

Choose a bit $b \in \{0,1\}$ uniformly at random.
Choose a permutation $\sigma \in S_n$ (of the vertices of $G_b$).
Accept if $\pi(\langle\sigma(G_b)\rangle) = b$, reject otherwise.

Here, $\langle \_ \rangle$ is some computable bijection from $\mathbb{N}^n$
to a suitable range $[0..N] \subseteq \mathbb{N}$. We assume that if the derefenced
bit in $\pi$ does not exist, i.e. the certificate is too short, we reject.

Claim: By above algorithm, GNI is in $\operatorname{PCP}(n \log n, 1)$, i.e.

the algorithm uses $O(n \log n)$ random bits and queries $O(1)$ bits of $\pi$,
$(G_0, G_1) \in \mathrm{GNI}$ implies that there is some certificate $\pi$
 so that $\Pr[A(G_0, G_1, \pi) \text{ accepts}] = 1$, and
$(G_0, G_1) \notin \mathrm{GNI}$ implies that
 $\Pr[A(G_0, G_1, \pi) \text{ rejects}] \geq \tfrac{1}{2}$ for all certificates
 $\pi \in \{0,1\}^*$.

Ad 1: Clear from the algorithm by noting that uniform permutation sampling
is possible with $\approx n \log n$ random bits¹.

Ad 2: Consider the certificate

$\qquad\displaystyle \pi(\langle H \rangle) =
  \begin{cases}
0 &, H \equiv G_0, H \not\equiv G_1 \\
1 &, H \equiv G_1, H \not\equiv G_0 \\
\text{arbitrary} &, \text{ otherwise}
  \end{cases}$

where $H$ are all graphs with $n$ nodes. Since $G_0 \not\equiv G_1$ and
$\sigma(G_b) \equiv G_b$, we have $\sigma(G_b) \not\equiv G_{1-b}$ for all $b$ and
$\sigma$. The query to $\pi$ therefore always yields $b$ and thus always accept.

Ad 3: Let $\pi \in \{0,1\}^*$ arbitrary and $H = \sigma(G_b)$ the chosen
query graph. If our query hits a non-existing bit of $\pi$ we reject by assumption,
which is correct. Otherwise, we calculate

$\qquad\begin{align}
  \Pr[\text{accept}] &= \Pr[b=0] \cdot \frac{\#[\pi(H) = 0 \mid H \equiv G_0]}{\#[H \equiv G_0]}
                  + \Pr[b=1] \cdot \frac{\#[\pi(H) = 1 \mid H \equiv G_1]}{\#[H \equiv G_1]} \\
                 &= \frac{1}{2} \cdot \left( \frac{\#[\pi(H) = 0 \mid H \equiv G_0]}{\#[H \equiv G_0]} +
                                             \frac{\#[\pi(H) = 1 \mid H \equiv G_0]}{\#[H \equiv G_0]}
                                     \right) \\
                 &= \frac{1}{2}
\end{align}$
using that $H \equiv G_1 \iff H \equiv G_0$ in this case.

Thus, the claim is proven.

Some observations that helped me grasp these concepts better.

The certificate $\pi$ can be arbitrarily long and arbitrarily complex. Note that
"good" certificates for the above algorithm essentially solve the same problem
as the algorithm (many times).
But that does not imply that any decision problem can be solved in PCP style
by "just providing the answer in the certificate". Condition 3 prevents any
naive attempt of that kind.
It is in general not possible to derive an efficient (randomised one-sided-error)
algorithm that guesses the certificate (as is the case for NP-certificate verifiers).

Strictly speaking, this assumes that $n!=2^k$ (which of course almost never holds)
since we have infinite worst-case runtime
for other $n$. However, Arora/Barak seem to ignore this aspect.


Pick elements that don't exhaust any set

This is the hitting set problem in disguise.
Let $U=\cup_{A_i \in \mathcal{C}} A_i$ be the universe and $\overline{X} = U \setminus X$.  Then your problem can be equivalently stated as follows: given $\mathcal{C}$ and $k$, find $\overline{X}$ that has $|U|-k$ elements, and such that $A_i \cap \overline{X} \ne \emptyset$ for each $A_i \in \mathcal{C}$.  That is exactly the hitting set problem.


What is the difference between Big O and asymptotic notation?

Bachmann–Landau notation or asymptotic notation is collection of notations one of which is Big-$O$. So they are not interchangeable, because as asymptotic notation also is known little-$o$, big-$\Omega$, big-$\Theta$ etc.
Historically this symbol was introduced by German  mathematician Paul Bachmann and then adopted by German number  theoretician  Edmund Landau and American mathematician L.E. Dickson . Big-$O$ was shorthand for function rate of growth, which is called its order.
History also can be viewed in the book by Florian Cajori - A history of mathematical notations-Dover Publications (1993), page 31.


Number of descendants of each node in a DAG

Topologically sort the nodes in your DAG.
For each node N, set N.QueryCount = 0.
For each node N, in reverse topological order:

Set N.Descendants = {N} U {C.Descendants | C in N.Children}.
Yield (N, N.Descendants.Count) from the algorithm.
If N.Parents is empty, you can dispose of N.Descendants.
For each C in N.Children, increment C.QueryCount. If C.QueryCount == C.Parents.Count, you can dispose of C.Descendants.

This of course is expensive if your node degrees are large. Worst case complexity may not be significantly better than your unspecified "naive algorithm."

The issue is that this is a very difficult problem to solve.  Suppose there is a DAG with millions of nodes, millions of edges, etc. I show you this portion of the graph:

A--> B
 \-> C

How many descendants does A have?  The number of descendants of B plus the number of descendants of C minus the number of common descendants of B and C.  It's the third term that creates the difficulty.  You can't know just the number of descendants of B and C - you need to also know what the descendants are.


Time Complexity proof for Segment Tree implementation of the ranged sum problem

The claim is that there are at most $2$ nodes which are expanded at each level. We will prove this by contradiction.

Consider the segment tree given below.

Let's say that there are $3$ nodes that are expanded in this tree. This means that the range is from the left most colored node to the right most colored node. But notice that if the range extends to the right most node, then the full range of the middle node is covered. Thus, this node will immediately return the value and won't be expanded. Thus, we prove that at each level, we expand at most $ 2 $ nodes and since there are $ \log{n} $ levels, the nodes that are expanded are $ \boxed{2 \cdot \log{n} = \Theta\left( {\log{n}} \right)} $


Naive Bayes where Feature Space is LDA Output

The topic scores (the numbers in the first $K$ columns) come from a Dirichlet distribution.  The marginals of the Dirichlet distribution are a beta distribution.

Therefore, it would be reasonable to model the distribution on each feature as beta-distributed, not normally-distributed.  With this adjustment, all the math for Naive Bayes goes through.

Let me flesh this out.  Given some data $x=(x_1,\dots,x_k)$, the Naive Bayes classifier computes the likelihood of a class $c$ as

$$L(c) = P(c) \prod_{i=1}^k P(x_i | c).$$

Here $x_i$ is the value in the $i$th column (the estimated probability the document came from topic $i$).  Given the comments above, we will estimate that the conditional distribution $P(x_i | c)$ has a beta distribution with some parameters, i.e., $\text{Beta}(\alpha_i,\beta_i)$.  Thus,

$$P(x_i | c) = {1 \over B(\alpha_i,\beta_i)} x_i^{\alpha_i-1} (1-x_i)^{\beta_i-1}$$

for some parameters $\alpha_i,\beta_i$.

Where do we get the parameters from?  From the training set, as usual.  In other words, we take from the training set just the documents that are classified with class $c=0$, and from those, we fit a beta distribution to the conditional distribution $P(x_i | c=0)$ and find the parameters $\alpha_i,\beta_i$ that make the beta distribution best fit the observed values of $x_i$ (out of the training documents classified as class $c=0$).  We use those as our estimate for $P(x_i | c=0)$.  How do we find $\alpha_i,\beta_i$?  By using standard methods for estimating the parameters of a beta distribution, given a bunch of observations drawn from it.

Then, we do the same for the documents in the training set that are classified as $c=1$, to fit a beta distribution and use that as the distribution for $P(x_i | c=1)$.

Finally, once you have formulas for $P(x_i | c=0)$ and $P(x_i | c=1)$, you plug that into the definition of $L(c)$ above and use that in the Naive Bayes classifier just as normal.


Dynamic programming table for finding similar substrings is too large

One can reduce your problem to the following. Given a sequence of $N$ numbers, find a contiguous subsequence of length at most $K+1$ having maximal sum. This problem, in turn, is solvable in time $O(N)$.

What's the connection between your problem and mine? Let the positions of the mistakes be $I_1,\ldots,I_t$, and add $I_0 = 0$, $I_{t+1} = N+1$. The sequence in question is $J_1 = I_1 - I_0,\ldots,J_{t+1}=I_{t+1}-I_t$. Every $K+1$ consecutive numbers $J_a,\ldots,J_{a+K}$ correspond to a maximal solution for your problem of length $J_a + \cdots + J_{a+K} - 1$. The entire algorithm takes linear time.

Edit: This calculates the maximal $L$ such that $M(i,i,L) \leq K$ for some $i$. The actual problem wanted to find the maximal $L$ such that $M(i,j,L) \leq K$ for some $i,j$. By considering all possible shifts, we can solve this in $O(N^2)$ time and $O(K)$ space.


Better suitable for math.stackexchange.com.

It is quite widely known that about n / ln (n) numbers are primes, so you get $n^{1/2}$ iterations in about n / ln (n) cases.

You can try to figure out how often you have more than $n^{1/3}$ iterations: That happens if there is no prime factor less than $n^{1/3}$, and therefore the number is either prime or the product of two primes. So you either have a prime, and there are about n / ln n of those, or you have a product of two primes, that is a product of one prime p from $n^{1/3}$ to $n^{1/2}$, and one prime from p to n/p, and there only about (n/p) / ln (n/p) of those.

All other numbers take less than $n^{1/3}$ iterations.


information theory, find entropy given Markov chain

You can make the golloowing set of equations, where s1 - the probability of being in s1 state:

s1 = 0.25s1 + 0.5s2
...
s1+s2+s3=1

I don't know the theory, but think that entropy of each state can be computed as follows:

e1 = - 0.25*log(0.25) - 0.75*log(0.75)

with overall entropy given already computed probability and entropy of each state

e = e1*s1 + e3*s3 + e3*s3

I don't know what H(...) means.


Your first language is actually regular: if $s$ is the substitution mapping $0$ to $\{0,1\}$, then
$$
\{ 0^x 1^y : 0^{x+y} \in L \} = s(L \cap 0^*) \cap 0^*1^*.
$$
Your second language is context-free, since we can write it as $L \cap 0^*$ concatenated with $\{0^y 1^y : y \geq 0\}$. It need not be regular, as the example of $L = \{\epsilon\}$ demonstrates: in this case, your language is just $\{0^y1^y : y \geq 0\}$.


Detecting conservation, loss, or gain in a crafting game with items and recipes

Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (a) every element is $\ge 0$ and (b) at least one element is $> 0$.

(Notice that the order of the operations doesn't matter: Running them in some order might cause the quantity of some item to dip below zero, but we can just look for the low-water-mark and suppose that we have at least that many of each item to start with.)

I think this can be solved by linear programming: Make a variable for each coefficient, add $\ge 0$ constraints for each element in the output vector (each element is a dot product of coefficient variables and constant coefficients from recipes), more $\ge 0$ constraints for each coefficient variable, and set the function to maximise to be the sum of all elements. To make it bounded, set the sum of coefficient variables to some constant, e.g. 1. Iff the solution value is $> 0$, you have non-conservation!

Note that fractional values are not an issue: They must be rational, so you can always multiply through by all denominators to get a pure-integer solution.


Regarding the proof of the statement you quoted (to complement Juho's answer):

Let $G$ be a connected planar graph with $V > 2$ vertices, $E$ edges and $F$ faces. We know from Euler's formula that $V-E+F=2$.

Now let us count the number $q$ of $(e,f)$ pairs where $e$ is an edge and $f$ is a face incident to $e$. Because every edge is incident to at most two faces, $q \leq 2E$. Because every face is incident to at least $3$ edges, $q \geq 3F$. Thus, $3F \leq 2E$. Using this together with Euler's formula we get that $3V = 3E - 3F + 6 = E +6 + (2E - 3F) \geq E+6$. Thus $E \leq 3V-6$.

Now, if some graph had a clique of size $5$, by taking this clique as a subgraph we would have that the complete graph on $5$ vertices $K_5$ is planar. But this graph has $V=5$ and $E=10$, thus $E > 3V-6$, which contradicts what we have just shown. Thus, $K_5$ is not planar and our original graph has no clique of size $5$ or more.


If you don't know anything about the contents of the matrix (such as some kind of monotonicity property), linear time is the best you can do for a one-off search with a deterministic algorithm by a simple adversary argument: if you don't look at everything, then you can't distinguish between the cases where the maximum component is/isn't one of the ones you didn't look at. If you want to maintain max-information for a dynamic matrix, then there might be suitable preprocessing and maintenance (for example, a search tree) that can speed things up.


Decidability of whether a language described by Turing machine is regular

This language/problem is neither decidable nor partially decidable (r.e). You can use Rice's theorem to prove it. The following proves that the language is not decidable.

"$L$ is regular" is a nontrivial property of recursively enumerable languages since there are regular and non-regular languages which are r.e. For example, $L_1 = \{0^{2n} \mid n > 0\}$ is regular, while $L_2 = \{0^n1^n \mid n > 0\}$ is not regular, but both are r.e. Hence, by Rice's theorem the language $\{\langle M \rangle \mid L(M) \text{ is regular } \}$ is not decidable.

In order to prove that this language is not r.e. you could use Rice's theorem for recursively  enumerable index sets.


What is correct time complexity of the substring generation algo

To be blunt, the Stack Overflow question and its answers illustrate why you want to ask about such things here.

The propsed algorithm clearly does not run in quadratic time.
Since the length $n$ of the original string is our input size, and the length of the longest possible result string, we can not assume that string comparisons run in constant time.
The bound you give is therefore also wrong, since you can not check in constant time if any string is in a list of size $L$.

Instead, the running time of the algorithm is more complicated and depends on several factors (new variable names).

The length $N$ of the input string.
The number $m$ of output strings. $m \in \Omega(n) \cap O(n^2)$.
The total length $M$ of all output strings. $M \in \Omega(n^2) \cap O(n^3)$.

You should be able to derive rough bounds using standard approaches. Keep in mind to fix the dictionary implementation you use for the "list"! Using, say, tries you get lookup (and insertion) costs bounded by the length of the string at hand.


Each cycle in the graph, the edge with the minimum weight belongs to MST

Following is a simple counterexample: Take a complete graph on four vertices: ${u_{1},u_{2},u_{3},u_{4}}$, with edge weights $w(u_{1},u_{2}) = 1$, $w(u_{2},u_{3}) = 2$, $w(u_{1},u_{3}) = 4$, $w(u_{1},u_{4}) = 5$, $w(u_{2},u_{4}) = 3$, and $w(u_{3},u_{4}) = 6$. Here MST is composed of edges: $(u_{1},u_{2})$, $(u_{2},u_{3})$, and $(u_{2},u_{4})$ with total weight $6$. And, no edge of the cycle $(u_{1},u_{3},u_{4})$ is part of the MST.


Which word could I use for the pumping lemma?

So it has to be something like this $w=b{a}^{2m+2}b^mc^m$.

$b{a}^{2m+2}b^mc^m$ is not the general form for $w=bxc^m\in S$. If $x$ must be in the form of $a^*b^*$, $w$ will be something like $b{a}^{m+n+k+2}b^nc^m$ for some $n,k\ge0$. Just for completeness, $w$ could be like $baba^{m+1}c^m$ or  $baba^{m+1}a^kb^kc^m$ or many other forms. Of course, it is totally fine if you just meant to choose one word so as to apply the pumping lemma.

Can you check word $ba^{p+2}c^{p}$, assuming the pumping length is $p$? This word is about as simple as you could get.

Exercise 1. Assuming the pumping length is $p$, can we pump $ba^{p+3}bc^p\in S$?

Exercise 2. Assuming the pumping length is $p$, can we pump $ba^{2p+2}b^pc^p\in S$?


If a Language is Non-Recognizable then what about its complement?

Assuming that you can prove statement 1 and 2 above, you have just presented a proof. You're trying to show that there exists a language which is non-recognizable such that its complement is recognizable. You then prove that $!A(TM)$ has this property. Then you want to show that there exists a non-recognizable language whose complement is also non-recognizable and then you show that $EQ(TM)$ has this property.

The point is that to prove that you can't comment, you need only to show that both possibilities are possible ie. that examples of each exist.


In syntax-directed definition, terminals are assumed to have synthesized attributes only, definition doesn't provide any semantic rules for terminals?

It's not a claim; it's a definition. In mathematics, we can define things however we want.  [See Note 1]
Our only obligation is to make sure we've shared the definition with our readers.
In any event, it doesn't make the slightest difference. If we want to define an inherited attribute for a terminal, we can just replace the terminal throughout the grammar with a non-terminal with a single production whose right-hand side consists only of the terminal. Then the surrogate non-terminal can carry whatever attributes we want it to carry.
This transformation does not in any way affect the parse (provided it is done consistently throughout the grammar).

Notes

It's not a coincidence that Lewis Carroll was a mathematics professor.


An elaborate hint: recall that the proof of the Myhill-Nerode theorem works (in one direction) by constructing a DFA for a language, given its equivalence classes.

In the constructed DFA (i.e the minimal DFA), each state corresponds to an equivalence class. We then set the accepting states to be those that correspond to equivalence classes that are contained in the language.

Now, suppose you create the DFA for the equivalence classes of $L$, without knowing in advance which equivalence classes are in L, and which aren't. If you choose one particular class, and set the state that corresponds to it to be accepting, then the language of the DFA is exactly that equivalence class, which is what you wanted.

Indeed, the property of the minimal DFA is that for every two words $w,w'$, the runs of the DFA on $w$ and on $w'$ end in the same state iff $w\equiv_L w'$.

Observe that you may end up with a DFA that is not minimal for the equivalence class.


Scientifically acceptable method for comparing performance of algorithms

There is no single answer.  The answer depends upon the specific situation you are in.  It's not that there is a single scientifically accepted way of evaluating performance.  Instead, a paper should be driven by the claims you want to make.  First, figure out what claims you want to make about your scheme.  Then, figure out what evidence is needed to support those claims.

For instance, perhaps you would like to claim that your scheme is fast enough to deploy on low-cost embedded systems.  Well, then your next step is to make that claim more precise: what counts as fast enough? how do you know? what specific systems do you mean?  Then, you can evaluate performance on those systems, by that metric, and assess whether it is fast enough.

Or maybe you would like to claim that your scheme is faster than previously published approaches.  Your next step would be to make that more precise: which previous approaches are you going to compare to?  on what platform?  with what workload?  And then you'd evaluate on those platforms.

The right metric to use for performance will depend on your specific situation.  For some, maybe it is wall-clock time.  For others, maybe it is energy consumption (power).  For still others, maybe it is guaranteed low-latency, or memory usage, or something else entirely.

In short: there is no single scientifically accepted method.  Instead, think of science as (a) being precise about what claims you are making, and then (b) providing appropriate evidence to support those claims.  What constitutes "appropriate evidence" will depend upon your specific situation.  You can often look to other publications in your field to see what evaluation method they used, as initially guidance, but ultimately this is a matter of critical thinking: evaluating evidence in a logical, careful, thoughtful manner.


Is this simplified consensus problem easier than the original?

What you're describing as simplified problem is usually called consensus with clean crashes.
You can just compute the maximum of all received messages once. To see that this is sufficient, observe that everyone receives the exact same messages after the first round. Thus everyone agrees on the same maximum value and all nodes decide correctly.

To solve crash-fault consensus on a general graph you need to assume $(f+1)$-connectivity. Then you could simulate each round of the FloodSet algorithm by flooding through the entire graph (taking $D$ rounds), yielding $D(f+1)$ rounds in total. I would be surprised if there's a more efficient way to do this (without additional assumptions on the graph, .e.g., high expansion).


Both versions of Peterson's algorithm are correct.

The version at Operating System Concepts (OSC) is slightly better if you would believe the natural meaning of turn as whose turn it is to enter the critical section or who has the priority to enter the critical section. The version at Modern Operating Systems (MOS) is slightly better for its better variable name interested.

Let us verify that the two versions are equivalent to each other. Let us rename the variable turn in the version at MOS to wait, (which should be a better name for that variable), meaning who should be waiting or who should yield to the other process regarding entering the critical section. Now you can see two versions are similar. The version at MOS say that the current process intends to wait behind the other process when it sets the wait to be itself and checks its value later. The version at OSC says the other process should have the turn to enter the critical section when it sets the turn variable to the other process and checks its value later. Now you can feel that those two versions seems doing the same thing.

To go a step further, after we have renamed turn to wait in the version at MOS, let us further imagine that the way the computer for MOS implements wait=0 is actually set some memory location to 1 and will name that location as turn'. It will implements wait=1 as setting that location turn' to 0.  Also when it checks wait == 0 it actually checks turn' == 1. When it checks wait == 1, it actually checks turn' == 0. Other than this particular implementation for the wait variable, this computer is completely the same as another computer that runs the version at OSC. Now if you skip the intermediate syntactic step that set or check wait and view turn' at the computer for MOS as equivalent to turn at the computer for OSC, (and rename several other variables), you can see they are actually executing the same code.

(In short, if you imagine that, only for the original wait variable at MOS version, 1 means 0 and 1 means 0, then you can see both version are executing same kind of code.)

Another way to see the equivalence of the two versions is to notice, as the questioner has noted, each version sets some variable to some value and then checks whether that variable is still that value. This variable is only used in these two places. There are only two values for that variable. It does not matter what is name of the variable or what are those two values. As long as the code sets some variable to some value and then checks whether that variable is still that value, that part of code has same behavior. Of course, this reasoning here is somewhat shady. It can certainly to help your understanding, though.

Every time we refer to Peterson's algorithm, it is obligatory to praise what a simple and great distributed algorithm it is. How deceptively simple it is and how smart it deals with the intricacy of concurrency!

For a much more complete understanding of the Peterson's algorithm and why it is indeed correct, please check The assertional versus Tarskian methods.


Priority queue of constant size fit for extraction of K highest priority elements

If that's practical question, sorted array may be faster than other approaches. The only O(N) operation you will do is memcpy in L1 cache whose speed using AVX2 is 32 bytes per CPU cycle, i.e. ~100 GB/sec.

You will need 2 arrays to make merge. But then you can use spare space for other computations. More complex data structure may easily run out of L1 cache size.


How to store set of long char strings to search for long char string key

One approach is to use a suffix array (or suffix tree).  That allows very fast searching for a match.

Given multiple words, there is a standard way to compute a suffix array (or suffix tree) associated with them: concatenate them, separated by some separator.  For instance, if the words are APPLE, CAT, and DOG, you obtain the string APPLE\$CAT\$DOG\$.  Then, compute the suffix array/tree of that single long string.


How to efficiently find line-segment intersections between two sets?

The problem you describe is known as the red-blue intersection problem. Here, we have a red set of $n_1$ segments and a blue set of $n_2$ segments and we know that there are only intersections between segments of different colour.  Although this special case has been extensively studied, the $O(n\log n + k)$ algorithm, with $n=n_1+n_2$ is still optimal1 when if we have no further information.

In particular, we cannot easily combine the two approaches. To get some intuition on why adapting the sweepline algorithm in particular doesn't simply work, consider the case where $n_1=1$ and $n_2 = 1000$ and take a large blue segment such that the rectangle that has this segment as a diagonal contains all endpoints of the red segments. In this case, all red segments could be intersecting the single blue segment, so the sweepline has to consider all points in $n_2$ as event points and hence it is possible we have to spend at least $\Omega(n_2\log n_2)$ time on our sweepline algorithm.

There is one special case in which we can be faster. A planar subdivision is simply connected when each closed path over the edges within the same region of a subdivision can be topologically contracted to a point, i.e. a region cannot contain another region (similar to a simply connected space). If the two sets of segments form two simply connected planar subdivisions, we can use the algorithm by U. Finke and K. Hinrichs. to find all intersections in $O(n+k)$ time.

1. Optimal if $n_1\approx n_2$. Of course, if $n_2 \ll\log n_1$, we can do better with the naive algorithm, but that is rarely the case.


Data structure for interval subset queries

Let $F(I) = |\{s \in S : s \subseteq I\}|$ where $I$ is an interval.
If $[a, b]$ is our query interval, we can make the following partition where $R$ is our desired result:
$$R =n -F((-\infty, b)) - F((a, \infty)) + F((a, b))$$
The first two queries can be answered simply using a sorted data structure of respectively endpoints and startpoints.
The last query is the dual of this problem, which has an answer here on this site.


Difference between ways to compare floating-point numbers

You are rightfully confused, because these answers mix up incompatible concepts into a right mess.

If you want to know whether two floating point numbers are equal then you use the "==" operator, which will tell you absolutely correctly whether they are equal.

If you want to know whether they are identical, that's slightly more tricky: There are +0 and -0 which are equal but not identical, and there are NaNs (Not-a-Number) which are not equal, not even equal to themselves, but can be identical.

Now if you perform floating-point arithmetic, then it can happen that two calculations that should have given the same mathematical result do give different results due to rounding errors. It can also happen that two calculations that should have given different mathematical results do give the same result.

There is no quick and easy rule. You need to think about what your goal is, and how to achieve it. And every case is different.

PS. (4) is just awful. Totally, totally wrong. If you use double precision and one of x, y is greater than 10^160, then almost any two numbers will be considered "equal" by this code.

PS. (1-3) are equally awful, because they claim that 0 ≠ 0.

PS. (3) is awful - it completely destroys the idea of gradual underflow.

PS. As a rule, you should use double precision instead of single precision, unless you have a very good reason not to; a reason that you can explain and defend.


Computation Complexity books for a mathematician

Michael Sipser's text book Introduction to the Theory of
Computation
is a classic introduction to computation theory, and gives an
introduction to complexity theory in the end.
I don't know how to answer the question better than just providing the
table of contents of the book.
PART 1: AUTOMATA AND LANGUAGES.
1. Regular Languages.
2. Context-Free Languages.

PART 2: COMPUTABILITY THEORY.
3. The Church-Turing Thesis.
4. Decidability.
5. Reducibility.
6. Advanced Topics in Computability Theory.

PART 3: COMPLEXITY THEORY.
7. Time Complexity.
8. Space Complexity.
9. Intractability.
10. Advanced Topics in Complexity Theory.


Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria

Without loss of generality, each asub$i$ can be taken to have exactly one element (size 1).  (If there is any solution, then there is a solution where all asub$i$'s are of size 1.)

Now it's easy to iterate over all sets of size 1 and determine which are valid for asub$i$.  Let $A$ be the collection of all such sets.  There is your solution.  As a bonus, I even gave you a solution where $A$ is as large as possible.

The running time is polynomial (in fact, quadratic), so this should be an efficient algorithm.


Examples of difficult Hamiltonian Cycle Problems

TSPLIB contains some instances of Hamiltonian Cycle. Haythorpe [1] proposes a set of around a thousand instances which are claimed to be "structurally difficult" (not necessarily large).

Haythorpe, Michael. "FHCP Challenge Set: The first set of structurally difficult instances of the Hamiltonian cycle problem." arXiv preprint arXiv:1902.10352 (2019).


How feasible is it for a non-distributed web crawler running on consumer hardware to search the internet?

This is not remotely feasible. The number of pages indexed by Google and Bing are in the tens of billions. To get anything close to what they are doing you are going to need to process terabytes of data. It will take you days to download all of these webpages using your home internet connection at full speed. And you will probably hit some bandwidth cap by your ISP before you finish. Even if there was no bandwidth cap from your ISP you would have to be careful in how you request the pages. If you request too many from one server in too short a time you'll probably get your ip blocked by that server. So you'll need some kind of program to optimize the order in which you visit these hundreds of millions of URLs. You will never be able to finish visiting all of the URLs in your queue. New content will be added to the internet faster than you can keep up with it.


cheap multi agent path planning algorithms

I would do a unique breadth exploration from the exit to get the shortest distance to exit of any position. Only obstacles (like walls) should be considered, not critters. This exploration should be done again each time an obstacle is added or removed. With some optimization, you may not have to recompute all the positions.

Then each time a critter should move, check if any accessible position has a better (lower) distance to exit. If not, the critter stay in position, else it moves to the one with the lowest distance to exit.

By "any accessible position", you can consider either up-down-left-right or something more complicated (moving more than one space, jumping obstacles and so on...).


When was the terminology *tracing collector* introduced to denote both mark-and-sweep and copy collectors

The terminology was introduced in Lang and Dupont, Incremental Incrementally Compacting Garbage Collection, SIGPLAN 87. This is the paper which consolidated several lines of enquiry into one common language.

The way I found this out was by consulting Paul Wilson's 1992 survey, Uniprocessor Garbage Collection Techniques, which is required reading if you need to know stuff like this.


Any option other recursive search possible to go from one 2d point to another point with fixed set of possible moves?

There is a simple method that is often faster: If you have $n$ moves to go from $A$ to $B$, determine the set of all points that you can reach from $A$ in $\lfloor \frac{n}{2} \rfloor$ moves, and the set of all points from which $B$ can be reached in  $\lceil \frac{n}{2} \rceil$ moves, and then find if there are points in the intersection of these sets.


Problem class of assigning N persons to N tasks, zero costs with prefs

This problem is known as maximum matching of a bipartite graph.
Basically let vertex $p_i$ (resp., $q_i$) represent the $i$th person (resp., task).
And we connect $p_i$ and $q_j$ with an undirected edge iff person $i$ can do task $j$.
The answer of the original problem is exactly the maximum matching of the new graph.

For algorithms, the classical Hungarian algorithm, of complexity $O(n^3)$, is a nice choice. Certainly you can reduce this problem to network flow, and then apply any max-flow algorithm.
If you are looking for some "advanced" choices, refer to Wikipedia.


How to calculate complexity of an algorithm which calls a subroutine?

This sentence: "In a single run of algorithm $A$, algorithm $B$ is called at most $10n^2$ times" is vague. If it means in each iteration of $A$, then as each time the calling $B$ takes $10n^2\times O(n^3) = O(n^5)$, we can say $A$ will be run in $n^4 \times O(n^5) = O(n^9)$.

On the other hand, if it means in all round of $A$, it calls $10n^2$ times $B$, as you said the time complexity would be $O(n^5)$.


First, let's simplify your F a bit. Instead of

if (s x = 1): F g s = s[x ->1]
otherwise:    F g s = g s[y -> y*x, x -> x -1]

we can equivalently write

if (s x = 1): F g s = s
otherwise:    F g s = g s[y -> y*x, x -> x -1]

since s is the same as s[x->1] in the case s x = 1.

Second, we need to be more precise. We can't write s[y -> y*x, ...] since at the left of -> we need a value, and y*x is not a value but an expression. More in detail, y is a variable name whose value (in the current state) is s y. So, we should write instead s[y -> s y * s x, ...]. We get:

if (s x = 1): F g s = s
otherwise:    F g s = g s[y -> s y * s x, x -> s x - 1]

Now, let's check your fixed point claim. Let g be defined as follows:

if (s x >=1): g s = s[x -> 1]
otherwise:    g s = undefined

and let's compute F g s, aiming to check whether F g s = g s for all s.

F g s
= { definition of F }
if (s x = 1): s
otherwise:    g s[y -> s y * s x, x -> s x - 1]
= { let's call s' the last state }
if (s x = 1): s
otherwise:    g s'
      where s' = s[y -> s y * s x, x -> s x - 1]
= { definition of g }
if (s x = 1): s
otherwise:    if (s' x >= 1): s'[x -> 1]
              otherwise:      undefined
      where s' = s[y -> s y * s x, x -> s x - 1]
= { definition of s' }
if (s x = 1): s
otherwise:    if (s x - 1 >= 1): s[y -> s y * s x, x -> 1]
              otherwise:      undefined
= { arithmetics }
if (s x = 1): s
otherwise:    if (s x >= 2): s[y -> s y * s x, x -> 1]
              otherwise:      undefined

This looks quite different to g s! Indeed, your g is not a fixed point.

Intuitively, that code computes the factorial of x (times the original value of y) inside y,
and loops forever on nonpositive x,
so I would expect a fixed point to be

g s = if (s x >= 1):  s[y -> (s y) * (s x)!, x -> 1]
      otherwise:      undefined


How to explain rehosting and retargeting with T-diagrams?

Retargeting refers to having the compiler generate code for a different CPU or instruction set.
A different CPU would be X86 vs PowerPC.
A different instruction set would be ARM vs THUMB or x86 vs x86-64 (same CPU, but different mode).

Rehosting means running the code on a different machine than the code was compiled on.
The new machine usually has the same architecture.
Rehosting need not be trivial, because e.g. the filesystem may look different on the compiler system.

See: http://www.cs.southern.edu/halterman/Courses/Spring2009/425/Slides/ch11.pdf

  Retargetability
  Easily modified to generate code for a different target language

  Rehostability
  Easily modified to run on a different machine

Collectively the two terms are often combined in the term portability.
Code that is portable is not tied to an architecture (target) and not tied to the setup of a specific machine (host).

refering to your question
Rehosting does not mean compiling for another platform!
Retargeting is compiling for another platform.
Rehosting is moving your program to another computer (same platform) (and keeping your fingers crossed to see if it works)


Are real computers finite state machines?

Yes, real computers are finite state machines: they have finite memory so there's a finite number of states the machine can be in. One consequence of this is that a real computer can't recognise $\{a^nb^n\mid n\geq 0\}$.

"But hang on a second!" you're saying, "Any idiot could write a program that recognises that language."  Well, suppose your computer has $n$ bits of total storage (memory, disk, anything else you might have plugged in).  Even if you use all of that storage to count how many $a$'s you've seen, you can only count up to $2^n$.  That means your program can't tell the difference between a string that starts $a^{(2^n)}$ and one that starts $a^{(2^n+1)}$.

But you need to consider the scale of these numbers. A typical computer has, say, 1TB of storage.  That means that $n=8\times 2^{40}$ and $2^n \approx 10^{2,600,000,000,000}$.  In contrast, the number of atoms in the universe is only about $10^{80}$ and some physicists estimate that the universe will cease to exist in any interesting way in only about $10^{100}$ years, which is about $3\times 10^{116}$ nanoseconds.  (Fun fact: the number of seconds in a year is within half a percent of $\pi\times 10^7$.)

In other words, your 1GHz computer only has time to read in about $3\times 10^{116}$ characters before the heat death of the universe, and that's a looong way short of the number of characters you need to feed it to verify that it can't actually accept $a^nb^n$.  So, in practical terms, you can consider your computer to be a Turing machine instead of a finite state machine.


Which is more efficient? lg(n+10^n) higher than 2^lgn

Compute $\lim_{n\to\infty}\frac{\log(n+10^n)}{2^{\log(n)}}$. This is
$$\begin{align}\lim_{n\to\infty}\frac{\log(n+10^n)}{2^{\log(n)}}&=\lim_{n\to\infty}\frac{\log(n+1+10^{n+1})-\log(n+10^n)}{1}\\
&=\lim_{n\to\infty}\log\left(\frac{(n+1)+10^{n+1}}{n+10^n}\right)\\
&=\lim_{n\to\infty}\log\left(\frac{(n+1)/10^n+10}{n/10^n+1}\right)\\
&=\log(10)\\
&>1
\end{align}$$
where the first equation was using Stolz-Cesaro theorem (L'Hospital for sequences).
That this limit is larger than $1$ implies that for $n$ large enough $\log(n+10^n)$ becomes larger than $2^{\log(n)}$.


Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?

Suppose the input is $a,b$, two $n$-digit long numbers. We allow leading zeroes (we will see in a moment why). Let $c$ be the longest common prefix of $a,b$, and let $a=cA$, $b=cB$.

If $A = 0^{n-|c|}$ and $B = 9^{n-|c|}$ then we simply output $c$ (this includes the case $|c|=n$).

Otherwise, let $d_A$ be the first digit of $A$, and let $d_B$ be the first digit of $B$.

Recursively find a solution for the ranges $[A,d_A 9^{|A|-1}]$ and $[d_B 0^{|B|-1},B]$, and prefix $c$ to everything. Also, add $c(d_A+1),\ldots,c(d_B-1)$.

Here is an unoptimized python implementation:

def prefixes(a,b,C=''):
     n, m = len(a), max(i for i in range(len(a)+1) if a[:i] == b[:i])
     c, A, B = C+a[:m], a[m:], b[m:]
     if A == '0'*len(A) and B == '9'*len(B):
         yield c
     else:
         yield from prefixes(A[1:],'9'*(len(A)-1),c+A[0])
         for i in range(int(A[0])+1,int(B[0])):
             yield f'{c}{i}'
         yield from prefixes('0'*(len(B)-1),B[1:],c+B[0])

For example, if you run list(prefixes('50000000','55399999')) then you get the following output:
['50', '51', '52', '53', '54', '550', '551', '552', '553']


Why is the complexity of this nested for loop not $O(n^2)$?

Because $n$ is bounded by $50$, which is simply a constant. Observe that when $n$ is larger than $50$, you simply have a recursive call. It's only when $n \leq 50$ that you go into the first portion of the if statement and execute the for-loops. Therefore, both nested loops take $\Theta(1)$ time. Hence the total time complexity of the mystery function is linear.

Note that $O(n^2)$ is technically correct, though not tight since $O(1) \subset O(n^2)$. The exact running time is $\Theta(1)$ as pointed above.


Minimal colouring problem aproximation threshold

Consider 3-coloring and suppose that a $\delta$-approximation algorithm $A$ for the minimum coloring problem with $\delta < \frac{4}{3}$ exists.

Let $G$ be the input graph and $x$ be the solution returned by $A$.

If $G$ is 3-colorable then $A$ would return $3$.
In fact, $x \lt 4$ since $A$ would return a solution $x \lt \ ( 3\cdot \delta)=3* \frac{4}{3}=4$ by hypothesis.
If $G$ is not 3 colorable then $A$ would return $x \geq 4$ since $G$ needs at least $4$ colors.

Hence, with $A$ you would be able to determine whether $G$ is 3 colorable or not.

But 3-Coloring is NP-Complete (contradiction).


What is a "wasteful" execution? And a "schedule"?

I'm not completely sure of my answer since I don't have the book but I think that:

By "wasteful" execution they mean an execution that follow $A$ but with a lot of messages. There are trying to prove that for $n$ processes you may need $\Omega(n\log(n))$ messages. So they consider a ring with $n/2$ processes and the worst execution and they want to combine two of this rings and of those executions to prove that for $n$ processes you will need a least $n\log(n)$ messages.

By scheduler I think the mean a function $\sigma$ that a each state of your system associate a process and an action to be performed. A fixed system and a scheduler are equivalent to an execution (since you can see it as $s\xrightarrow{\sigma(s)}s_1\xrightarrow{\sigma(s_1)}s_2\xrightarrow{\sigma(s_2)}\dots$ But schedulers are often more easy to work with since they are functions so in the proof you don't need to manipulate indexes of where you are in the execution.

I hope it helps, please ask if I missed something.


How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount

As you knew intuitively, you just missed the solution by a millimeter, which, however, may look like a mile away.

$S\rightarrow aabbb/aSb/aSbb$

The idea is simple. Since $ab$ and $abb$ should not be generated, what is the shortest or simplest word that can be generated?

Here is a sketch of a NPDA. When it reads the first $a$, it goes to state $q_1$. When it reads the second $a$, it goes to state $q_2$. Then every time if it reads one $a$, it will push one or two $a$'s nondeterministically onto the stack. Then when it reads the first $b$ it goes to state $q_4$.  When it reads the second $b$ it goes to state $q_5$. When it reads the third $b$ it goes to state $q_6$. Then every time if it reads one $b$, it pops out one $a$ from the stack, staying at state $q_6$.

I will let you flesh out the details.


The question asks for a loop invariant. This has nothing to do with termination. (D) does look reasonable but you may want to check with the usual tools such as Hoare logic, that (D) holds before the loop and is re-established by the loop body if the guard holds.

PS Your idea of an algorithm may need some work.


Can you use binary files to reverse engineer cpu architecture?

This was certainly possible with early microcomputers such as the Altair 8800. Each instruction or data value was encoded as a binary number, set up by flipping a line of toggle switches up or down, and when the switches were all set correctly another switch was used to write that number into the next memory address.
Once you have done this once or twice you realise how tedious it is. Hence the rapid development of peripherals such as paper tape readers, punched card readers and eventually keyboards, all of which require some sort of operating system, even if a primitive one. In parallel, programming aids such as assemblers, programming languages, compilers and IDEs made programming simpler and quicker, at the cost of creating distance between the programmer and the hardware.
I doubt it would be possible to write binary instructions directly into the memory of a modern laptop, partly because of all the layers of peripherals and operating system functions that stand between you and the CPU, and partly because such a feature could be maliciously misused, so there are security features that prevent it. But it is certainly possible with a microcontroller board such as an Arduino - or you could build your own Altair 8800 !


If I understand correctly, you want to print every substring of length $k$ from the original text. To do this you will need to invert the Burrows-Wheeler transform completely at some point, which is indeed what you do in your pseudocode. One improvement for your method would be to just store the $k$ latest characters instead of storing the whole string.

Your method is already as good as it gets, as it is equivalent to doing one pass over the string and directly printing the substrings, which is the minimum you have to do in any case.

--

Edit: so we want to print each substring only once. Now the problem becomes more interesting. An easy solution is to store the substrings in a hash map, for example, and thus avoid printing duplicates. If you can afford storing the original string and the inverse suffix array, then there is a sophisticated solution available which is good if $k$ is small.

A basic operation on the FM index is a left extension of a string. If we know the range of suffixes in the suffix array that start with the string $\alpha$, we can compute in constant time the range of $w\alpha$ for any character $w$. Here's how. Let $(i,j)$ be the range of the string $\alpha$. The range of $w \alpha$ is:

$$(C[w] + occ(w, i - 1) + 1,\;\; C[w] + occ(w,j)) \;.$$

We can start with the range of an empty string, which is $(1, n)$, and do a depth-first search of left-extensions down to a depth of $k$. At depth $k$ we will print the substring corresponding to the current range. For this we need to have the original string and the inverse suffix array $ISA$, which is defined by $ISA[SA[i]] = i$, where $SA$ is the suffix array. The substring corresponding to the range $(i,j)$ is the first $k$ characters of the suffix $ISA[i]$.

This method is very efficient in practice if $k$ is small, as it often is in bioinformatics applications. For a more thorough explanation on the backwards search I recommend e.g. this blog post: http://alexbowe.com/fm-index/


Trying to understand this Quicksort Correctness proof

We are indeed assuming $P(k)$ holds for all $k < n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with.

The proof you describe is known as the principle of strong mathematical induction and has the form

  Suppose that $P(n)$ is a predicate defined on $n\in \{1, 2, \dotsc\}$. If we can show that

  $P(1)$ is true, and
  $(\forall k < n \;[P(k)])\Longrightarrow P(n)$

  Then $P(n)$ is true for all integers $n\ge 1$.

In the proof to which you refer, that's exactly what's going on. To use quicksort to sort an array of size $n$, we partition it into three pieces: the first $k$ subarray, the pivot (which will be in its correct place), and the remaining subarray of size $n-k-1$. By the way partition works, every element in the first subarray will be less than or equal to the pivot and every element in the other subarray will be greater than or equal to the pivot, so when we recursively sort the first and last subarrays, we will wind up having sorted the entire array.

We show this is correct by strong induction: since the first subarray has $k<n$ elements, we can assume by induction that it will be correctly sorted. Since the second subarray has $n-k-1<n$ elements, we can assume that it will be correctly sorted. Thus, putting all the pieces together, we will wind up having sorted the array.


Just to add on to the answer provided by @Yuval Filmus to further illustrate why the pair $Y_{i-1},Y_{n-i}$ should be independent on $Z_{n,i}$.

Here is what I got wrong:

From $Y_n = \sum_{i=1}^{n} Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))$,  I had mistakenly thought that $i$ is a random variable. When I put this back into the definitions: $Z_{n,i}$ denotes the indicator random variable for the event that the rank of the root node is $i$.  $Y_{i-1}, Y_{i-1}$ denotes the exponential height of a randomly built binary search tree with $i$ elements and $i-1$ elements respectively. In this case, since $Z_{n,i}, Y_{i-1}, Y_{i-1}$ all dependent on this random variable $i$, I assumed that they must be dependent (through $i$).

Here is how I should have seen the equation above. By expanding out the summation:
$$Y_n = Z_{n,1} (2\cdot max(Y_{1-1}, Y_{n-1})) + Z_{n,2} (2\cdot max(Y_{2-1}, Y_{n-2})) + ... + Z_{n,n} (2\cdot max(Y_{n-1}, Y_{n-n}))$$

Thus, $i$ is just a variable and should not affect the independence between the pair $Y_{i-1},Y_{n-i}$ and $Z_{n,i}$. For instance in the first term $Z_{n,1} (2\cdot max(Y_{1-1}, Y_{n-1}))$, $Z_{n,1}$ denotes the indicator random variable for the event that the rank of the root node is 1. On the other hand, $Y_{1-1}, Y_{n-1}$ denotes the exponential height of a randomly built binary search tree with $0$ elements and $n-1$ elements respectively. Thus, from the definition alone, it should be clear that the pair $Y_{i-1},Y_{n-i}$ should not depend on $Z_{n,i}$.


Is Universality Theorem applicable to Halting problem?

By this book notation we have

$Halt(x,y)$ $\iff$ Program number $y$ eventually halts on input $x$.

Since there $Halt(x,y)$ is not computable predicate (theorem 2.1 page 68) there is no program that check if program number $y$ halts in input $x$ (for every $y$ and $x$), but this not mean that there is no program that run program number $y$ on input $x$!

By using universal program $\phi(x,y)$ we can run program number $y$ on input $x$. This means that $Halt(x,y)$ is r.e.

+if you think a bit more you can observe that program number y can get stuck in loop on input x, and that's why $Halt(x,y)$ is not computable.


Can an artificial neural network convert from cartesian coordinates to polar coordinates?

i dont know if this answers your question (or at least part of it)

According to the Universal approximation theorem for ANNs, it is possible (at least within a region of interest).

The question about how many hidden layers (and architecture) an ANN should have, is, AFAIK, an open problem, in the sense that there is no result to determine architecture and/or number of layers wrt specific final results (partly, this is due to the non-constructive proof of the above result), although you might want to see here and here.

Here is a review on methods to fix number of hidden layers in ANNs during the past 20 years: Review on Methods to Fix Number of Hidden Neurons in Neural Networks

Most ANNs are built by a trial and error process.

update (just an idea)

By modeling the transformations from cartesian to polar (and approximating square roots,..) as a discrete system, maybe one can transfer this design into ANN model (but i wont pursue this further right now)


Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular

The easiest way is probably to use the pumping lemma on the complement language $\overline{L} = \{ a^m : m \neq n! \}$. Suppose that $L$ were regular. Than $\overline{L}$ would be regular. According to the pumping lemma, there is a pumping length $p$ such that every word $w$ of length at least $p$ in $\overline{L}$ has a decomposition $w = xyz$ such that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in \overline{L}$ for all $i \geq 0$. Take $w = a^{p\cdot p!} \in \overline{L}$ (without loss of generality, $p > 1$). Suppose that the decomposition is $w=xyz$, where $y=a^t$. Since $t \leq p$, it follows that $t \mid p!$. But then $xy^{1+p!/t}z = a^{p\cdot p! + p!} = a^{(p+1)!} \notin \overline{L}$.


If you want rigorous proof, the following lemma is often useful resp. more handy than the definitions.

If $c = \lim_{n\to\infty} \frac{f(n)}{g(n)}$ exists, then

$c=0 \qquad \ \,\iff f \in o(g)$,
$c \in (0,\infty) \iff f \in \Theta(g)$ and
$c=\infty \quad \ \ \ \iff f \in \omega(g)$.

With this, you should be able to order most of the functions coming up in algorithm analysis¹. As an exercise, prove it!
Of course you have to be able to calculate the limits accordingly. Some useful tricks to break complicated functions down to basic ones are:

Express both functions as $e^{\dots}$ and compare the exponents; if their ratio tends to $0$ or $\infty$, so does the original quotient.

More generally: if you have a convex, continuously differentiable and strictly increasing function $h$ so that you can re-write your quotient as
$\qquad \displaystyle \frac{f(n)}{g(n)} = \frac{h(f^*(n))}{h(g^*(n))}$,
with $g^* \in \Omega(1)$ and
$\qquad \displaystyle \lim_{n \to \infty} \frac{f^*(n)}{g^*(n)} = \infty$,
then
$\qquad \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$.
See here for a rigorous proof of this rule (in German).

Consider continuations of your functions over the reals. You can now use L'Hôpital's rule; be mindful of its conditions²!

Have a look at the discrete equivalent, Stolz–Cesàro.

When factorials pop up, use Stirling's formula:
$\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$

It is also useful to keep a pool of basic relations you prove once and use often, such as:

logarithms grow slower than polynomials, i.e.
$\qquad\displaystyle (\log n)^\alpha \in o(n^\beta)$ for all $\alpha, \beta > 0$.

order of polynomials:
$\qquad\displaystyle n^\alpha \in o(n^\beta)$ for all $\alpha < \beta$.

polynomials grow slower than exponentials:
$\qquad\displaystyle n^\alpha \in o(c^n)$ for all $\alpha$ and $c > 1$.

It can happen that above lemma is not applicable because the limit does not exist (e.g. when functions oscillate). In this case, consider the following characterisation of Landau classes using limes superior/inferior:

With $c_s := \limsup_{n \to \infty} \frac{f(n)}{g(n)}$ we have

$0 \leq c_s < \infty \iff f \in O(g)$ and
$c_s = 0 \iff f \in o(g)$.

With $c_i := \liminf_{n \to \infty} \frac{f(n)}{g(n)}$ we have

$0 < c_i \leq \infty \iff f \in \Omega(g)$ and
$c_i = \infty \iff f \in \omega(g)$.

Furthermore,

$0 < c_i,c_s < \infty \iff f \in \Theta(g) \iff g \in \Theta(f)$ and
$ c_i = c_s = 1 \iff f \sim g$.

Check here and here if you are confused by my notation.

¹ Nota bene: My colleague wrote a Mathematica function that does this successfully for many functions, so the lemma really reduces the task to mechanical computation.
² See also here.


More details on a language decided in $\Theta(\log \log n)$ space

The trick here is to forget about the details as stated in the answer, and think about what would make the claim correct.

If $k$ were known, you could verify that the input is indeed $b(0)\#\cdots\#b(2^k-1)$ as follows: (below, a word is stuff between adjacent sharp signs)

The first word is $0^k$.
For any two contiguous words $x,y$, it holds that $y=x+1$.
The last word is $1^k$.

This can be accomplished in space $O(k)$.

Unfortunately, we don't know $k$ in advance, and even if we did, it's not necessarily the case that $k = O(\log \log n)$ – there could be much less than $2^k-1$ words. Therefore we use a slightly different approach. Let $K$ be the length of the first word. For each $t \leq K$, we verify the following:

The first word ends with $0^t$.
For any two contiguous words $x,y$, the $t$-bit suffixes $x',y'$ satisfy $y'=x'+1$ modulo $2^t$.
The last word ends with $1^t$.

If these tests pass for all $t \leq K$, then we accept the word. The $t$th test can only pass if the input is at least $(t+1)2^t-1$ symbols long and uses only $O(\log t)$ space, and this implies that the algorithm uses $O(\log\log n)$ space.


Characterizing cycles in a directed graph with optional edges

Yes, this is doable.  An encoded string of length $O(N^2)$ suffices.

Let me describe how to do it.  Let $V'$ denote the set of vertices that are the endpoints of the optional edges.  Obviously, $|V'| \le N$.  I'll describe the two procedures P,Q below.

Procedure P: Compute reachability information for each pair of vertices in $V'$.  In other words, for each $s,t \in V'$, compute whether $t$ is reachable from $s$ in the original graph (without using any optional edge); the answer is either "yes" or "no".  Note that there are $O(N^2)$ pairs $s,t$, so we can encode the answer to all those questions using $O(N^2)$ bits (one bit per pair $s,t \in V'$).  Let this be the encoded string.  Of course, the length of this encoded string is polynomial in $N$.

In particular, we can think of this encoded string as the representation of a graph $G'=(V',E')$.  $G'$ has vertices $V'$ and has an edge $s\to t$ if and only if $t$ is reachable from $s$ in the original graph (without optional edges).  The length of the encoding of $G'$ is $O(N^2)$, so polynomial in $N$.

Procedure Q: Given a set $S$ of optional edges and the encoded string, here's how we can tell whether adding those edges would create a cycle.  Basically, add every edge in $S$ to the graph $G'$.  (The encoded string tells us $G'$, so we can treat $G'$ as known, i.e., it is one of the inputs to Q.)  Now you can do depth-first search in the resulting graph, $G''=(V',E' \cup S)$, to test whether $G''$ contains any cycle.  $G''$ will have a cycle if and only if adding $S$ to the original graph (without any other optional edges) has a cycle.


What is the name of this problem (the dual of the asymmetric k-center problem)

It is not entirely clear to me where the warehouses are allowed to be placed. I will assume here that a warehouse can be placed in any city given by the input1.

instead of minimizing the distance [$t$], I want to fix it and minimizing the number of warehouses. is this problem NP-Complete also?

Observe that we may assume the maximum allowed distance $t=1$, because we can simply scale the input by a factor of $1/t$. This problem is known as the DISCRETE UNIT DISK COVER problem (DUDC).
DUDC is NP-hard. To see why, first note that the problem is equivalent to the dominating set problem on unit disk graphs.2 The dominating set problem is NP-hard for general graphs, but this does not imply that it remains hard for unit disk graphs in particular. However, the dominating set problem is known to be NP-hard on "grid graphs": unit disk graphs that have an embedding where all vertices lie on an integer grid with disks of radius $1/2$.3 Since all grid graphs are unit disk graphs, the dominating set problem is NP-hard for unit disk graphs, and hence DUDC is NP-hard.

1: Another option is that there is a finite number of fixed sites for warehouses, which are not necessarily inside a city. But this has the problem I discuss here as a special case, so my discussion here shows that both problems are in fact NP-hard.
2: Technically, we need to restrict ourselves to unit disk graphs for which we can compute an embedding in polynomial time, as this is not known to be possible for an arbitrary unit disk graph. Fortunately, this is possible for "grid graphs" (what helps is that these graphs are planar, unlike general unit disk graphs), so the construction works out fine.
3: See the paper Unit disk graphs by Clark, Colbourn and Johnson. They also note there exists an earlier proof for the hardness of the DUDC problem in the conference paper "S. Masuyama, T. Ibaraki and T. Hasegawa, The computational complexity of the M-center
problems in the plane" from 1981, but this paper appears to be accessible only for members of the Japanese institute that published the conference proceedings)


The answer depends on your computation model. Let's consider the case of Turing machines, and the language $L$ over $\{0,1\}$ of words ending in $1$. This language has time complexity $n+1$.

Blum's speedup theorem states that optimal algorithms don't exist for all problems, in a very strong sense (which is explained in the Wikipedia article).

Finally, let me mention that your notion of optimality is too restrictive. Given an algorithm with running time $T(n)$ for any problem, it is easy to construct (in the Turing machine model) another algorithm whose running time is also $T(n)$. So no language can have an optimal algorithm in this very strong sense. Even if you consider only running times, it is easy to construct (in the same model) another algorithm with the different running time $T(n)+1$. So no non-trivial language can have an optimal running time in your very strong sense.


How to calculate Huffman code length without generating the actual huffman code?

You can count the distribution of frequency of the alphabet you want to Huffman encode.
If this distribution is skewed Huffman encoding will perform poorly.
See: When would the worst case for Huffman coding occur?

If this distribution is flat Huffman encoding will perform well.
The more letters in your possible alphabet do not occur in your text the better Huffman performs.

If however you have a flat distribution and most or all of the possible encoding space in your alphabet is used, then Huffman encoding will not be able to compress it.

If you want to generate the lengths of the codes that Huffman would create without actually doing Huffman encoding you will need to create a algorithm so close to Huffman as to not make very much difference, especially not in running time.

Note that the bulk of the running time of Huffman encoding is taken up by frequency counting.
For a text of length $n$ with an alphabet of $a$ characters the running time of Huffman is $O(n+a)$ and because $a$ is almost always insignificant (as well as being a constant) in comparison to $n$. The running time is $O(n)$.

You can skip the counting step if you want by making assumptions about your input.
For instance if you know your input is English text or C-source code, than you can simply use the average frequencies for typical English texts (or C-source code) to generate your Huffman code.
If so you will already know the lengths of your codes, because you are simply loading a precomputed table of Huffman codes.

Needless to say this risks suboptimal compression.


Are there any "complete" languages in $coNP -NP$?

If we are assuming that $coNP≠$,

we can conclude that every language that is $co
NP$ complete is not in $NP$ (a contradiction to your given assumption).

Thus, every language we already know of that is $coNP$ complete, is complete as well in $coNP -NP$.


Prove that $L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$ not recursively enumerable

First, recall that the problem "$L(M)\neq\emptyset$" is semidecidable.

Define $f(M)$ as $a^i$ where $M_i$ is a TM such that

it accepts $aa$ iff $L(M)\neq\emptyset$,
it accepts any other string (including $a$).

For the first step: when $M_i$ receives $aa$ as input, it semi-decides $L(M)\neq\emptyset$. If that holds, the semi-decider halts in finite time, so $M_i$ can accept. If that does not hold, the semi-decider diverges, making $M_i$ diverge. This is fine, since $aa$ is not accepted.

Note that we never reject $aa$, because we do not have a full decider for $L(M)\neq\emptyset$. This however does not matter: we do not have to reject $aa$, we only have to avoid accepting it, and diverging suffices.


What's the purpose of the "o(1-o)" in the back propagation algorithm

Backpropagation is a gradient descent algorithm for minimizing the squared error of the learned network on the data given. In order to minimize by following the gradient, you need to know where the gradient points, this is done using calculus.

Along the way of calculating the gradient, you have to find the derivative of the activation function. When you take the most common activation function, i.e. the logistic rule or sigmoid function $o(z) = \frac{1}{1 - e^{-z}}$ and you differentiate it with respect to the neurons' input $z$ then you get $do/dz = o(1 - o)$. Hence, you are correct, this is related to the use of the sigmoid function, and figuring out in which direction the gradient points.

If you want a more thorough description then consult these notes (pdf).


Verification condition in case of array theory

Sure, if the user provides inductive invariants, you can try to check the validity of the verification conditions.  However, this remains undecidable, as it requires checking the validity of a formula in first-order logic (with quantifiers and array expressions), and that's undecidable.

It might be feasible often enough in practice to be useful, especially since we might hope that programmers have a reason why their code is correct and won't write code that requires overly complex reasoning to prove correct.  But in general, it is undecidable.


Where does the process reside in memory?

A process is not a single data structure. In the Windows operating system, for example, a running process has a number of different structures in its memory including a copy of its PE header and its environment variables. Here is a table from a debugger showing the layout of one process after it has been loaded into memory:

The various pieces of data have different structures. For example, the PE header is a record, but the heap is usually some kind of tree or list.


What is the complexity of comparing point sequences?

Here's a start: an upper bound is $O(n^3)$.

Note that we need either $0$ or $1$ moves: any two moves could be expressed as one.
Furthermore, this one move is commutative with all other operations: it may occur at any point in time, the end result will still be the same.

Barring some degenerate cases, consider one point $X_i$ which does not get deleted and moves into $Y_j$.
There are a total of $n^2$ such possibilities.
For each fixed $i$ and $j$, first, we know whether we need a move, and second, for all other points, we can establish which $X_u$ move into which $Y_v$ in $O(n)$.
For example, put all $Y_v$ in a hash table in $O(n)$, iterate over all $X_u$ and search for them in the hash table in $O(n)$ total.

Here's a speedup to $O(n^2)$.

Consider all possible $n^2$ move distances: each "$X_i$ to $Y_j$" produces a distance.
Some of the distances may turn out to be the same.
In your example of $X = (1, 2, 3)$ and $Y = (2, 4)$, the $X_1 \to Y_1$ and $X_3 \to Y_2$ produce the same distance of $2$.
So, in the end, each distance will have several pairs associated with it.

Now, we will need all $X_i$ to be different, and all $Y_j$ to be different.
Then, if a distance $d$ has $r$ pairs associated with it, all $X_i$ in these pairs are pairwise different, and all $Y_j$ in these pairs are also pairwise different.
It means that, when we move points by distance $d$, we will have $r$ matching points, and all other points will be non-matching, so will have to be deleted from $\{X\}$ or inserted into $\{Y\}$, respectively.

So, implementation-wise, maintain a hash map which maps a distance to the number of times we encountered such distance.
Iterate over all pairs of "$X_i$ to $Y_j$" and fill the map, in $O(n^2)$ total.
Now iterate the map and find the minimum cost, also in $O(n^2)$ total.
For a distance $d$, when the number of pairs with such distance is $r (d)$, the cost is the sum of the following:

$p_m$ if $d$ is nonzero, or $0$ if $d$ is zero;
$p_d \cdot (l_X - r (d))$, where $l_X$ is the length of $\{X\}$;
$p_a \cdot (l_Y - r (d))$, where $l_Y$ is the length of $\{Y\}$.

It may be possible to handle the case when the sequences can contain equal elements, but the details look cumbersome.

All this assumes $O(1)$ performance of hash sets and hash maps.
If that is a problem, at the very least, we can add logarithms and use tree sets and tree maps, respectively.

Also, the solution does not address precision loss for floating point operations.
For example, the implementation may use integers, by multiplying the given floating point values values by a constant.


Maximum number of distinct values for bitwise OR

Notice that the max value here given is 1e9. Therefore at most log(1e9) bits can be there. Suppose we fix an 'a' and iterate over 'b' such that b>=a. Thus this will form a monotonic function as bitwise OR can only increase the value of the initial operands. Moreover the OR operation can only turn a bit ON from OFF and not the other way round. So whenever the values increases that means a new bit has to be set ON. However for a fixed value of 'a' we can only turn on at most log(1e9) bits. Hence when we iterate over 'a' we can have a maximum bound of O(n)O(log(1e9)) distinct values. Hence the bound is O(nlog(MAX_VALUE))


You've exactly described the first situation, i.e. we indeed say that $u$ and $v$ are non-adjacent. For the second we do the same, but we want to also specify they are in the same component of $G$ which contains them if $G$ is not connected.

These are already simple and well-understood descriptions and there's nothing "more standard". However, you are also free to use your own definitions in your actual use case if it's worth it.


Proof regular languages are closed under homeomorphism

This proof looks correct. You can shorten it a bit (it doesn't need to be so descriptive), and you would get the following proof:
$h(L)=h(L(r_1\cup r_2))=h(L(r_1)\cup L(r_2)) = h(L(r_1))\cup h(L(r_2)) = L(r'_1)\cup L(r'_2)=L(r'_1\cup r'_2)$
Where the transition $h(L(r_1)\cup L(r_2)) = h(L(r_1)) \cup h(L(r_2))$ can be shown for any function $h$ (not necessarily a homeomorphism!).


Suppose that you are given the last $n$ digits of $x$, which is the same as knowing $x \bmod 10^n$. You want to find the last $n$ digits of $y$, that is, $y \bmod 10^n$, given that $xy \bmod 10^n = 1$. Since $xy \equiv 1 \pmod{10^n}$, the solution is $y \bmod 10^n = (x \bmod 10^n)^{-1}$, the inverse being taken in $\mathbb{Z}_{10^n}$. The condition $x \bmod 10 \in \{1,3,5,7\}$ guarantees that $(x,10^n) = 1$, and so the inverse always exists.

In order to calculate the inverse, use the extended GCD algorithm to find $a,b$ such that $a(x \bmod 10^n) + b10^n = 1$, and take $y \bmod 10^n = a \bmod 10^n$.

For example, suppose you know that $x \bmod 10^5 = 11327$. The extended GCD algorithm gives
$$
23263 \cdot 11327 - 2635 \cdot 10^5 = 1,
$$
and so $y \bmod{10^5} = 23263$.


Application of Brent's Cycle Detection Algorithm

If the numbers in the list are stored in memory as a list, you can just use a hashtable to look for duplicates, or you can sort them and then look for duplicates.

Brent's algorithm is primarily useful in situations where you don't want to store all of the numbers in memory, because the memory cost would be too high -- but that doesn't apply if you have a list with the numbers, because then you're already committed to storing all the numbers in memory.


Prove that the class of CFG languages that are closed under reversal is undecidable

Let $G_1,G_2$ be two context-free grammars. We can construct a context-free grammar $G$ such that
$$
L(G) = \#L(G_1) \cup L(G_2)^r\#,
$$
where $\#$ is a new symbol. The language $L(G)$ is closed under reverse iff $L(G_1) = L(G_2)$.


This is a simple question on the definition of routing tables. I will add a brief explanation.

Let's take the SALES router. It has two interfaces.

The interface top (65.21.1.2) is connected to the network 65.21.1.0/24.

The interface bottom (65.21.6.1) is connected to the network 65.21.6.0/23.

This can be expressed as the following routing table:

network          via        interface
---------------+-----------+---------
65.21.1.0/24     direct      top
65.21.6.0/24     direct      bottom

Now we have two research networks accessible via the router RESEARCH. This router has an ip address 65.21.1.3 on the network 65.21.1.0/24. This network is already in the routing table, so the traffic to the research networks can be routed with the following rules.

network          via        interface
---------------+-----------+---------
65.21.100.0/24   65.21.1.3   top
65.21.200.0/24   65.21.1.3   top

Finally the traffic to all other networks should be sent to the GATEWAY for further processing. Here is the final routing table.

network          via        interface
---------------+-----------+---------
65.21.1.0/24     direct      top
65.21.6.0/23     direct      bottom
65.21.100.0/24   65.21.1.3   top
65.21.200.0/24   65.21.1.3   top
default          65.21.1.1   top

The routing table for the RESEARCH router can be assembled following the same logic.


Prove the upper bound on $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$

By simple substitution, you can see that $T(n) = O(\sqrt{n}) + O(\sqrt{\log n}) + O(\sqrt{\log\log n}) + \dots = O(\sqrt{n})$.


While both Operations Research and Data Science both cover a large amount of topics and areas, I'll try to give my perspective on what I see as the most representative and mainstream parts of each.

As others have pointed out, the bulk of Operations Research is primarily concerned with making decisions. While there are many different ways to determine how to make decisions, the most mainstream parts of OR (in my opinion) are focused on modelling decision problems in a mathematical programming framework. In these kinds of frameworks, you typically have a set of decision variables, constraints over these variables, and an objective function dependent on your decision variables that you are trying to minimize or maximize. When the decision variables can take values in $\mathbb{R}$, the constraints are linear inequalities over your decisions variables, and the objective function is a linear function of the decision variables, then you have a linear program -- the main workhorse of OR for the past sixty years. If you have other kinds of objective functions or constraints, you find yourself in the realm of integer programming, quadratic programming, semi-definite programming, etc...

Data Science, on the other hand, is mostly concerned with making inferences. Here, you're typically starting with a big pile of data and you'd like to infer something about data you haven't seen yet in your big pile. The typical sorts of things you see here are: 1) the big pile of data represents the past results of two different options and you'd like to know which option will yield the best results, 2) the big pile of data represents a time series and you'd like to know how that time series will extend into the future, 3) the big pile of data represents a labelled set of observations and you'd like infer labels for new, unlabelled observations. The first two examples fall squarely into classical statistical areas (hypothesis testing and time-series forecasting, respectively) while the third example I think is more closely associated with modern machine learning topics (classification). Fun trivia: I believe that for a long time, the job title at Google for people doing what we now call Data Science was (is?) "Statistician".

So, in my opinion, Operations Research and Data Science are mostly orthogonal disciplines, although there is some overlap. In particular, I think that time-series forecasting appears in a non-trivial amount in OR; it's one of the more significant, non-math programming-based parts of OR. Operations Research is where you turn if you have a known relationship between inputs and outputs; Data Science is where you turn if you're trying to determine that relationship (for some definition of input and output).


Find the smallest element greater than current element

A better solution would be using a balanced binary search tree.
You can process the elements from the right to left and for each element you find the vertex in the tree with the smallest key greater than this element (a search query on the tree suffice) and then you add the element to the tree.
Total complexity is $O(n\log(n))$ since we are iterating over the elements once and having one query and one insert operations in each iteration.


Decomposition of a directed graph into Hamiltonian paths

Finding an Hamilton path in directed (and un-directed) graphs, is an $NP$ complete problem.
Thus, there is probably no efficient algorithm (polynomial) to split a given graph to several hamiltonian paths.


Using the pumping lemma for a proof by contradiction

$u$ and $v$ are supposed to be strings such that $uv$ is a prefix of a
string in the language longer than $p$ symbols, $p$ being the pumping length. Furthermore, you do not
get to choose them. All you know is that their total length does not
exceed $p$ and they are prefix of a word $x$ in  the regular language, of length $n$.

You do not get to choose them because they are existentially
quantified in the statement of the pumping lemma ... you could choose
them if they were universally quantified. If you do not understand
this last remark, just ignore it.

What you can choose is the value of $n$ and the string $x=uvw$ of size $n$
that will be used for pumping.  You choose $n$ in relation to the
pumping length $p$ which depends only on the regular language.

I would suggest to choose $n$ quite big, so that you make sure $uv$ is
in the first half of the string $x$, since $| uv| ≤ p$.

I would also choose my string $x$ with an appropriate pattern of a and
b  ... and then check what happens when I pump. It may seem odd, but
you have to get even with that problem.


If $D$ is low for itself ($D^D = D$) then $C,O \subseteq D$ should imply $C^O \subseteq D$, though it might depend on the exact definition of the oracle model (for resource-restricted classes there are sometimes delicate issues there). In contrast, if $D$ isn't low for itself then taking $C=O=D$ we get a counterexample.


$O(n \log n)$ algorithm to find next interval that is also disjoint

For interval i, you can binary search end[i] among the sorted array begin[]. Each binary search takes log n time.


Can someone explain in a simple way what "reducible" mean in complexity theory?

The most common notion of reducibility is many-one polynomial time reducibility.

A problem $A$ is many-one polynomial time reducible to a problem $B$ if there is a polynomial time function $f$ such that $x \in A$ iff $f(x) \in B$.

This definition implies that if $B$ is solvable in polynomial time, then so is $A$.

Other notions also exist, but at this stage you're probably better off concentrating just on this one, since it is the one used to define NP-completeness.


What algorithm may be used to solve the re-assembly of shredded papers?

If the cuts are in the middle of letters, then I think your solution in the last paragraph is a good one.

If the cuts go between letters, then I think your approach of finding pairs of strips of papers is a good one.  I would start by finding all pairs of strips that could have been adjacent, based on which digraphs (pairs of characters) can appear in some word.  Then, I would try to extend to find all triples of strips that could have been adjacent: for each possible pair of adjacent strips $s_1,s_2$, find all $s_3$ such that $s_2,s_3$ is a pair of possible adjacent strips; then test whether if you past together $s_1,s_2,s_3$ that all trigraphs (triples of characters) can appear in some word.  Then, I would extend to 4-tuples of strips, filtering them based on 4-graphs of characters, and so on.  The worst-case complexity could be horrible in principle, but in practice I expect that you'll very quickly filter out all false matches, so running time will probably be very good.

For fun, you might enjoy reading about the DARPA shredding challenge (summary on Wikipedia).


Terminology - machine code and byte code

Both are sequence of instructions encoded as binary data. The difference being that "Machine code" is executed by the CPU whereas "byte code" is executed by a software (which itself is made up of machine code and executed by CPU).


How to construct XOR gate using only 4 NAND gate?

From that formula? It can be done. But it's easier to start with this one: (using a different notation here)

a ^ b = ~(a & b) & (a | b)

Ok, now what? Eventually we should derive ~(~(~(a & b) & a) & ~(~(a & b) & b)) (which looks like it has 5 NANDs, but just like the circuit diagram it has a sub-expression which is used twice).

So make something that looks like ~(a & b) & a (and the same thing but with a b at the end) and hope that it'll stick around: (and distributes over or)

(~(a & b) & a) | (~(a & b) & b)

Pretty close now, just apply DeMorgan to turn that middle or into an and:

~(~(~(a & b) & a) & ~(~(a & b) & b))

And that's it.


Your problem (assuming I understand your English correctly) is counting the number of cliques in a graph of size $n = 50$. Counting the number of cliques in a graph is #P-complete (see this paper, which shows that counting the number of independent sets in a graph is #P-complete even for bipartite graphs).

Several efficient exponential time algorithms for the problem (efficient in the sense that their running time is $O(c^n)$ for $c<2$) are described in Jeff Erickson's lecture notes - see section 4.2 on page 4. The simplest algorithm, whose running time is $O(\phi^n)$ (where $\phi$ is the golden ratio), is as follows. For an arbitrary vertex $v \in G$ with neighborhood $N(v)$, we have the following recurrence for the number $I(G)$ of independent sets in $G$ (to get the number of cliques, complement $G$):
$$ I(G) = \begin{cases} 2I(G-v), & N(v) = \emptyset, \\ I(G-v) + I(G\setminus(N(v)+v)), & \text{otherwise}. \end{cases} $$

This algorithm might be practical for $n=50$. If it isn't, you can try the other algorithms described in the lecture notes. Some of them require some modification for your case, and therefore the running times listed there might not hold in your case.


How to design a formal grammar to convert EBNF description to a list of CFG production rules

I have a solution as below:

Given G0 = (N0, Σ0, P0, S0) is grammar of object language generated by EBNF descriptions. Where: N0 and P0 is unknown and needed to be generated by another language.
Given G1 = (N1, Σ1, P1, S1) is grammar of language generating EBNF descriptions.

G = (N, Σ, P, S) is EBNF description to production rules conversation grammar which is defined as below:

N = {'(', ')', '∣', ',', '[', ']', '{', '}', '='}
Σ = N0 ⋃ Σ0 ⋃ {'→', '/'}

Production rules:
A = α, (γ), β ⟶ A = α, YA, β / YA = γ
Where:

A, YA ∈ N0
α ∈ N1 ⋃ Σ1 ∖ {'('}
β ∈ N1 ⋃ Σ1 ∖ {')'}
γ ∈ N1 ⋃ Σ1 ∖ {'ε'}

A = α ∣ β ⟶ A = α / A = β
Where:

A ∈ N0
α ∈ N1 ⋃ Σ1 ∖ {'(', ')', '[', ']', '{', '}'}
β ∈ N1 ⋃ Σ1 ∖ {'(', ')', '[', ']', '{', '}'}

A = α[γ]β ⟶ A = α, (γ), β / A = α, β
Where:

A ∈ N0
α ∈ N1 ⋃ Σ1 ∖ {'['}
β ∈ N1 ⋃ Σ1 ∖ {']'}
γ ∈ N1 ⋃ Σ1 ∖ {'ε'}

A = α{γ}β ⟶ A = α , YA, β / YA = γYA / YA = ε
Where:

A, YA ∈ N0
α ∈ N1 ⋃ Σ1 ∖ {'{'}
β ∈ N1 ⋃ Σ1 ∖ {'}'}
γ ∈ N1 ⋃ Σ1 ∖ {'ε'}

A = B,C ⟶ A = BC
Where:

A, B, C ∈ N0

A = B ⟶ A → B
Where:

A, B ∈ N0

Start rule:
S ⟶ a

Where a ∈ Σ1

This grammar will re-write EBNF description to a terminal string like: A → B / B → C / B → D which means that the generated production rules are the set {A → B, B → C, B → D}. The token '/' is list seperator.


Indexing a huge dataset (that does not fit into central memory)

The other approach that I can think of is the obvious one: process the file one line at a time, and consult a dictionary of "seen" lines. What may not be obvious is how to represent the dictionary.
There are plenty of on-disk data structures that would work, and this is a well-researched area given that this is what databases do for a living. Some variant of B-trees, or a hash table (e.g. extensible hashing) would work. Consider Berkeley DB if you need something off the shelf.
If that is too slow, you could use a Bloom filter as an in-memory cache. Then, you need only consult the on-disk data structure if you get a hit in the Bloom filter.


Many-One Reducibility of decision problems for complexity theory?

NP-hardness (and so NP-completeness) are defined using many-one reductions. When you show that a problem is NP-hard, you have to follow the definition and use many-one reductions. All proofs that you see of NP-hardness use many-one reductions.

One thing to note is that usually, one does not show how to reduce an arbitrary problem in NP to the target problem. Rather, one reduces a problem already known to be NP-hard to the target problem. The starting point of this endeavor is Cook's theorem (independently proved by Levin), which shows that SAT is NP-hard.

The other common type of reduction is oracle reduction (there are other types as well, but they are less common). Oracle reductions cannot distinguish NP from coNP: every coNP-hard problem in the many-one sense is NP-hard for oracle reductions. Most researchers believe that NP is different from coNP, and this is one of the reasons we insist on using many-one reductions.


There are a lot of slightly different definitions of Turing machines out there! They usually differ in small but subtle ways. For example, some authors say that a Turing machine's head moves left or right, and writes the symbol; some authors say that it can also stay still. You have seen that Papadimitriou and Lewis allow either replacing the character on the tape, or moving left or right, which is slightly different than both replacing the character on the tape and moving left or right.

That sounds like bad news, but the good news is that you can prove that all of these different definitions are equivalent. Your textbook will have some exercises related to that. For example, we can prove:

That Turing Machines that can move left, right, or stay still are equivalent to ones that just move left or right.

Proof Idea: The Turing Machine that can only move left or right can "mimic" staying still by first moving one step to the right, then moving one step to the left. It takes $2$ steps instead of $1$, but it does the same thing.
That Turing Machines that move the head OR write a symbol are equivalent to those that move the head AND write a symbol at each step.

Proof Idea: the one that moves-or-writes can simulate the behavior of the one that moves-and-writes by first writing, then moving. So it takes $2$ steps instead of $1$, but it does the same thing. On the other hand, the one that moves-and-writes can simulate the behavior of the moves-or-writes one as follows: in order to move without writing, it should write the same symbol that is already on the tape (so that the write has no effect). And in order to write without moving, it should move left and then right, so that there is no net effect.


Determining interests from Twitter text using Latent Dirichlet Allocation

Thanks for your comments, reformulating the question lead me to a different way of thinking about the problem.

Getting an interest category list is actually reasonably straightforward for broad level hobbies it is just the labelled training data that may be hard to produce.

I found this paper on unsupervised text classification and this is probably a better fit than topic models in this scenario. It uses a small number of keywords (average 3) per category and segmented sentences to produce training data for a naive Bayes classifier.

I think I will use this with some Twitter specific text pre-processing and some sentiment classification to see if the categories are spoken of in a positive light.


Are the non-regular languages closed under reverse, union, concatenation, etc?

Non regular languages are closed under reverse, because $L = (L^R)^R$. Same is true for complement.

Non regular languages are not closed under most other basic operations though. Consider, for example, that $L \cup \overline{L} = \Sigma^\star$. Similarly, if $L = \{1^{x^2} | x > 1\}$ then $\overline{L} \circ \overline{L} = 1^\star$.

There is no complete list of operations on languages, so a complete answer cannot be given.


Finding the maximum disjoint weight in a weighted node graph

The problem that you are trying to solve is called "maximum weight independent set". It is NP-hard so not much hope for exactly solving it efficiently. There exist efficient approximation algorithms though (see e.g. this question).


Is UTF-8 the final character encoding for all future time?

UTF-8 might not last forever, but you probably don't have to worry too much.

Two universal truths:

We can't predict the future.
Nothing lasts forever, especially in software.

But that doesn't mean the benefit of (trying to) future-proof your code always outweighs the cost.

Is UTF-8 likely to become obsolete any time soon?

I would say no. UTF-8 is quite common, which makes it harder to replace. Unicode also still has quite a bit of empty space, meaning there isn't likely to be a pressing need to replace it soon. Between 2010 and 2020, less than 40k characters have been added. It will take about 240 years to use up the remaining ~1 million unallocated characters if we assume we keep going at the same rate. This is a lot faster than I imagined, but still quite a while away and assuming it will keep going at the same rate is quite an assumption.

It also doesn't seem like there'd be a need to replace it due to a fundamental flaw in the encoding. With other types of standards or technologies there may be some security issue that could be exploited, but this doesn't seem likely with character encodings that only tells you how characters are stored.

I speculate if a need to replace it arises, it would be due to inefficiencies or  constraints in new technology. Someone could develop some new piece of technology that rethinks how data is stored or loaded, which might make UTF-8 less than ideal or unusable. But there would still be plenty of systems without that technology for quite a few years.

Note that I didn't ask "are we likely to see a new character encoding any time soon". Anyone can create a new standard, but that doesn't mean it will be widely adopted nor replace other standards.

How bad would it be for you if there's a new standard?

Probably not that bad.

Even if there is a new standard that's widely adopted, your system will likely keep functioning for the foreseeable future with little to no changes. There are a lot of legacy systems out there.

If your system doesn't support the new encoding, you may have some issues with the user or other systems trying to send you data you don't support. But your system could still use UTF-8 internally, even if this means you don't support some characters (which might not be good, but it won't necessarily break your system).

Also, if it were to be replaced due to a reason other than running out of space (which, as noted above, doesn't seem likely any time soon), UTF-8 could likely be extended to include any characters in the new encoding. Meaning you can just convert from one encoding to the other where required and UTF-8 would still be usable.

Unicode versus Unicode?

The difference between UTF-8, UTF-16 and UTF-32 seems minor when compared to other (non-Unicode) encodings. They all support the same characters, so it shouldn't be a huge issue if one replaces the other.

If another one of those were to become the widely adopted one, it would probably be trivial to convert between them where required and continue to use UTF-8 everywhere else.


Computing the closest match of an automaton and a string

You can adopt the usual dynamic program to compute the Levenshtein distance between a word $w$ and a regular language $L$ computed by some given NFA without $\epsilon$ transitions. Suppose $w$ has length $n$. For each $0 \leq \ell \leq n$ and state $s$ of the NFA, we will compute $A(\ell,s)$ which is the minimum Levenshtein distance between the $\ell$th prefix of $w$ and a word that causes the NFA to reach state $s$. This quantity is given by the following calculation, involving an auxiliary array $A'$:

$A(0,s)$ is the length of the shortest path from the initial state of the NFA to $s$ [insertion].
$A'(\ell+1,s)$ is the minimum of the following quantities:

$A(\ell,t)$ if there is a transition from $t$ to $s$ marked $w_{\ell+1}$.
$A(\ell,t)+1$ if there is some transition from $t$ to $s$ [substitution].
$A(\ell,s)+1$ [deletion].

$A(\ell+1,s)$ is the minimum of $A'(\ell+1,t)+\kappa(s,t)$ over all $t$, where $\kappa(s,t)$ is the length of the shortest path from $t$ to $s$ in the NFA [insertion].

Finally, the distance is the minimum of $A(n,s)$ taken across all accepting states $s$.

This calculation requires that you compute in preprocessing the all-pairs-shortest-path matrix for the directed graph underlying the NFA. Some of the quantities arising in the computation could be infinite.


General number field sieve is slower then exhaustive search for 'small' numbers?

First of all, the number 120 that you got is completely meaningless. There is a scaling factor that can only be determined experimentally. Even worse, there are lower order factors which are probably very significant for such small numbers. Finally, the running time you quote is heuristic – it's just an educated guess.

You are correct that GNFS is a lot less efficient than trivial methods for small numbers. That's why you don't use it for small numbers. The better asymptotics kick in only for large enough numbers.


Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity?

After some more thought here is my own attempt at a solution:

Assume for contradiction that the depth $d$ isn't $\Omega(\log \log n)$. Then it must be that

$\forall C,N:\exists n > N: d < C \lg \lg n$.
(Base 2 is an arbitrary choice for the logarithm.)

In particular if $C = \frac 1 2$ then

$\forall N: \exists n > N: 2^{2^{2d}} < n$.

At this point the Switching Lemma is required. The Switching Lemma is stated in The Nature of Computation as follows:

  Consider a circuit with $n$ inputs $x_1,...,x_n$ consisting of a layer of OR gates which feed into a single AND gate, where both types of gates have arbitrary fan-in. Now suppose that we randomly restrict this circuit as follows. For each variable $x_i$, with probability $1-n^{-\frac 1 2}$ we set $x_i$ randomly to true or false, and with probability $n^{-\frac 1 2}$ we leave it unset. For any constant $a$, if there are $O(n^a)$ OR gates, then with probability $1-o(n^{-a})$ the resulting circuit can be expressed as a layer of a constant number of AND gates, which feed into a single OR gate.

The Switching Lemma is symmetric with respect to AND and OR. So every time the Switching Lemma is applied the top two layers are switched and the second and third layer can then be merged into a single layer leaving a circuit of depth $d-1$. Thus after applying the Switching Lemma $d-2$ times the circuit has depth $2$ remaining.
Applying the Switching Lemma one last time no longer reduces the depth of the circuit but does leave a circuit that only depends on a constant number of inputs. (This follows from details of the proof of the Switching Lemma.)
At the same time the number of remaining unset variables is

$\sim n^{\frac{1}{2^d}} > (2^{2^{2d}})^{\frac{1}{2^d}} = 2^{\big(\frac{2}{\sqrt 2}\big)^{2d}} = 2^{2^d}$.

And since a previous result established that Parity isn't in $AC^0$, we know that $d$ and for that matter $2^{2^d}$ eventually exceeds any constant.
If we were then to set those variables on which the circuit still depends, we'd arrive at a constant circuit computing Parity with some variables still unset, which yields a contradiction.
Also note that the width remained polynomial since the Switching Lemma increases it by a constant factor $m$ each time it is applied. So the width is multiplied by

$m^{d-1} < m^{\frac{1}{2} \lg \lg n} = (\lg n)^{\frac{1}{2} \lg m} = poly(n)$.

Hence $d = \Omega(\log \log n)$.

I want to point out however that this proof is fairly out of my personal comfort zone. So I don't want to make any guarantees.


Explain why a language can be generated by a context free grammar

Usually, to prove that some language is a CFL (which is equal as asking whether it is generated by some CFG) you can show:

It is generated by some CFG. Proving is usually done by induction, where one direction is an induction on the number of derivation steps, and the other direction is usually an induction on the length of the word.
Showing a PDA that accepts the language.
Using closure properties of CFL, and generate the language from some finite number of CFL/regular languages using closure properties (like concatenation, union, etc..)