DFS produces the correct Topologically ordered sequence

Before I get to the proof, let me just clarify that the algorithm using DFS would be to process edges in decreasing order of finishing times while running DFS on the input graph.
Now to prove that the above algorithm returns a topological sorting, we can use some lemmas about DFS $-$ namely the Parenthesis Theorem as well as the White Path Theorem. I will not get into the proofs of each lemma but we will use the following:
A corollary of the parenthesis theorem, as follows:

Consider vertices $u$ and $v$ in $G$. Then $v$ is a descendant of $u$ in the DFS forest of $G$, if and only if $d(u)<d(v)<f(v)<f(u)$, where $d(x')$ is the discovery time of vertex $x'$ and $f(x')$ is its finish time.

Also, we will use the white path theorem which states that

Vertext $v$ is a descendant of vertex $u$ in the DFS forest if and only if at time $d(u),$ there exists a white path from $u$ to $v.$

Now let $e = (u,v)$ be an edge in the input graph. We want to prove that in our output, $u$ comes before $v$. We can show that by proving that in our DFS traversal, $f(u) > f(v).$
CASE I: $d(u) < d(v)$
By the White Path Theorem, $v$ is a descendant of $u$. This is because at time $d(u)$, there is a white path in $G$, which must be from $u$ to $v$ as there exists edge $e = (u,v)$. Hence, we can use the corollary of the parenthesis theorem to show that $f(u) > f(v).$
CASE II: $d(v) < d(u)$
At time $d(v)$, there is no white path from $v$ to $u$, as that would imply that $G$ has a cycle (meaning that it is not a DAG), and hence $u$ cannot be a descendant of $v$ in the DFS forest of $G$. So by the parenthesis theorem, we have $d(v) < f(v) < d(u) < f(u)$. Again, we proved that $f(u) > f(v)$.
Hope that helped :)


In the text, they seem to suggest that there is a way of quoting characters so that they can be used as terminals even if they have the visible form as a non-terminal. One common quoting form is quotes ('B') which is illustrated.

Character classes ([bB]) are another quoting form. The B in that character class cannot be a non-terminal because it is precisely a character. So the non-terminal B, although it looks very similar, is distinct, and the Bs in the strings are characters, necessary by the definition of string they are using.


Understanding of SPACE in non deterministic Turing Machines

A nondeterministic Turing machine is a Turing machine that has a "guessing" mechanism. It accepts an input if there is a sequences of guesses that leads it to an accepting state. It rejects an input if all guesses lead it to a rejecting state.

The time complexity and space complexity of the Turing machine are defined in exactly the same way as for deterministic Turing machines:

The time complexity on inputs of size $n$ is the maximum number of steps that the machine executes before halting over all inputs of size $n$ and all guesses.
The space complexity on inputs of size $n$ is the maximum number of tape cells that the machine uses over all inputs of size $n$ and all guesses.

If your machine always uses only a polynomial amount of space, then it is is NPSPACE. Note that NPSPACE=PSPACE, a consequence of Savitch's theorem, and so you can convert it to a deterministic machine using polynomial space (the amount of space used could increase).


Why does the solution of an NP problem have to be polynomial size?

First, let's refresh the proof that the definition given is indeed equivalent to the standard definition of NP, i.e., the class of languages accepted by polynomial-time nondeterministic Turing machines.

Suppose $L$ is accepted by a polynomial-time Turing machine $M$. There is some $c$ such that $M$ runs in time $|x|^c$ for all inputs $x$. The verification algorithm is as follows: given $x$ and $y$, interpret $y$ as being a sequence of states of $M$ (expressed in some appropriate alphabet), and accept the pair $(x,y)$ if, and only if, $y$ describes an accepting path of $M$ on input $x$. Now, for any string $x\in L$, $M$ has an accepting path of length at most $|x|^c$, there exists a $y$, also of length at most $|x|^c$, such that $A$ accepts $(x,y)$. If $M$ rejects $x$, then there is no accepting path, so no string $y$ can describe an accepting path, so $A$ rejects $(x,y)$ for any string $y$.

Conversely, suppose that a polynomial-time algorithm $A$ exists with the properties stated in the question. We can construct a nondeterministic polynomial-time algorithm for $L$ as follows.  Given input $x$, nondeterministitically "guess" (generate) a string $y$ of length at most $|x|^c$ and see if $A$ accepts $(x,y)$. If $x\in L$, then there is a string $y$ of length at most $|x|^c$ such that $A$ accepts $(x,y)$, so our machine accepts; if $x\notin L$, then no string $y$ has the desired property, so our machine rejects. This is a nondeterministic polynomial time algorithm because it does a polynomial about of guessing and a polynomial amount of simulation of $A$.

So, what goes wrong with this if we remove the condition that there exists some $y$ specifically with length at most $|x|^c$?  Well, the first half of the proof still works: if $L$ is in NP then $A$ exists and, hey, it still happens to have the property that $|y|\leq |x^c|$, even though that wasn't required. However, the other half of the proof breaks. We no longer have the guarantee that it's enough to guess $|x|^c$ bits. In fact, we have no guarantee at all. We'd have to keep guessing longer and longer strings to test with $A$ and, actually, the procedure would never terminate for $x\notin L$: there's no way to tell if there really is no $y$ for which $A$ accepts $(x,y)$ or if there is such a $y$ but it's just so long that you've not seen it yet (undecidability of the halting problem).

So, without the polynomial bound on $|y|$, every NP langauge can still be expressed in this way but, unfortunately, so can all recursively enumerable languages. The polynomial bound is required to restrict the class of languages described to just NP.


Let me first repeat the setting. There are $k$ sticks, one of them distinguished. We randomly choose $k$ different positions for them from $1,\ldots,n$, and put a special stick at $0$. How far to the left of the distinguished stick is the closest stick?

The trick here is to observe that we obtain the same distribution if we first choose positions for the sticks and then permute the $k$ sticks (without changing the set of $k$ positions). This is equivalent to choosing the $k$ positions and then choosing one of the sticks at random as the distinguished one. If the positions are $i_1 < \cdots < i_k$, the average distance to the left is
$$\frac{(i_1 - 0) + (i_2 - i_1) + \cdots + (i_k - i_{k-1})}{k} = \frac{i_k}{k}. $$
Therefore the average distance to the left is $\mathbb{E}[i_k]/k$.

It remains to compute the average position of the maximum of $k$ distinct random positions. There is probably a smart way of doing that; here is a brute force calculation. The number of choices in which the maximum is $\ell$ is exactly $\binom{\ell-1}{k-1}$. Hence the average is
$$
\frac{1}{\binom{n}{k}} \sum_{\ell=k}^n \ell \binom{\ell-1}{k-1} =
\frac{k}{\binom{n}{k}} \sum_{\ell=k}^n \binom{\ell}{k} =
\frac{k}{\binom{n}{k}} \binom{n+1}{k+1} = \frac{k(n+1)}{k+1}.
$$
Overall, we get that the average distance to the left is
$$
\frac{1}{k} \cdot \frac{k(n+1)}{k+1} = \frac{n+1}{k+1}.
$$


Single-source shortest paths as a linear program

What you have here is a dual formulation of the problem (not the standard one, but an equivalent one). According to strong duality, both the optimal primal and the optimal dual problem have the same objective value (i.e., the shortest path distance from $s$ to $t$). The constraints of the dual problem are then the optimality criteria of the shortest path problem. Note that you can obtain the actual shortest path by finding any $s$-$t$-path in the subgraph that is induced by the edges for which the corresponding dual constraint is tight.

By the way, there is a neat interpretation of this formulation: For each edge $(u,v)$, consider a string with length $w(u,v)$ and tie the ends of these strings together at the corresponding nodes they share. If you put the knot for $s$ and the knot for $t$ as far away from each other as possible, you will end up with several tight strings, which then describe the shortest path.


Why descriptive power of context-free grammar is greater than regular expression?

Let the set of languages that can be represented by regular languages be $R$. And set of languages that can be generated by a context free grammar be $G$. Then surely $ R \subset G$. For the proof that every regular language has a context free grammar that generates it, I encourage you to look up Michael Sipser's book on complexity. And for the second part, there are many languages which have a context free grammar generating them but are not regular. For example $L=\{ww^{reverse}\}$, where $w^{reverse}$ is reverse of the string $w$. How do we know $L$ has a context free grammar ( you can easily come up with a push down automata for it ), look up Sipsers. And look up pumping lemma in the book to prove $L$ is not regular.

To get an intuition, any regular language can be represented by a finite state automata $FSA$ and vice versa. And any context free grammar can be represented by a push down automata $PDA$ and vice versa ( again read the proof from Sipsers ). And in a  $PDA$ in addition to the states ( like in $FSA$ ) you also have an infinite memory stack. Thus intuitively context free grammars have "power" greater than that of $FSA$.


Calculating speedup of this parallel program

Kind of application you mention seems to be I/O bound i.e., application execution time is dominated by I/O time (Ti). In this case using multiple threads is not going to be advantageous as there is only one connection between your I/O device (permanent storage) and CPU (having multiple cores). That one connection is the bottleneck. You will not observe much of a speed-up as you increase the number of threads. There may be slight gain as number of threads increase initially, as threads try to saturate and use the maximum bandwidth possible for the I/O connection. Gain will also depend on how much time is spend on I/O and how much on processing of read data. Both of them can run in parallel for two different threads. But your question seems to suggest that I/O time (to get data) >> compute time (to process data). Hence there will be limited gain by increasing the number of threads. Instead, try to optimize the I/O. Keep it sequential and read in larger blocks.


Matrix equality up to row/column permutations problem name

After a few observation in the comments (thanks to Hendrik Jan, Yuval Filmus, and D.W), I post an extended comment as an answer.

It seems (unless I'm missing something) that the problem is equivalent to Hypergraph isomorphism (HI):

to prove that it is equivalent to HI, it is enough to use incidence matrices: every column represents a node of the hypergraph, every row represents an hyperedge (the $1$s are placed on the columns corresponding to the nodes of the hyperedge).

  The question remains valid ... is there a short name for the problem other than Hypergraph Isomorphism (if it appears somewhere not related to graph theory) ?

(if nobody post another answer in a few days I'll temporarily accept mine).

Additional stuff:

for proving that it is GI-complete it is enough to consider the incidence matrix of the source graphs $G_1, G_2$;
the reverse reduction is similar to the well known reduction from HI to GI: it is enough to consider the incidence matrix of the source hypergraphs $H_1, H_2$, transform them to graphs: every column becomes a node $c_i$, every row becomes a node $r_i$; an edge $(c_i,r_i)$ is added if and only if the corresponding cell contains a $1$; and finally a new triangle is linked to every set of nodes $\{c_{i_1},...,c_{i_m}\}$ that represents an hyperedge to preserve hyperedge mapping.


What is the difference between symbol and enumerated datatypes?

This is again much a question about terminology, without only history
as a possible authority to determine "what is right".

These two kinds of values are very similar in the sense that they
should be considered as atomic entities, distinguished only by their
representation as a string of character over some alphabet, possibly
with some minor constraints regarding the use of some characters (e.g.,
should start with alphabetic character,).  These constraint are really
immaterial, since what matters mainly is whether two symbols are the
same or are different.

A major difference is that the set of symbol is potentially infinite
(like the set of strings meeting the constraints) though actually
limited by the implementation of the language, like anything else.

An enumerated type, is defined by giving explicitly an enumeration of
the values of that type, which also have a representation as a string
of characters. Since the enumeration is explicit, there is only a
finite number of values in an enumeration type. Languages often consider that
these values are ordered in by the order of the definition. Thus these enumerated
value can be compared for equality, of for order.

Symbols can only be compared for equality. Sometimes, an arbitrary (alphabetical ?) ordering may be provided as it may help for some algorithms. But there is no semantics attached to it.

In a language, You usually have only one type for symbols. However, it
is easy to make more when you have data abstraction available. Symbols
are usually implemented like identifier tables in interpreted
languages, and can actually stand for identifiers in meta-circular
interpreters.

Enumerated types are defined by the programmer, and he may define
several such types.  One source of problems is that he may (at least in some languages)
use the same name for different enumerated values, not in the same
type of course, but in different enumerated types.

type month = (January, February, March, April, ...)
type girl = (Mary, April, Nancy, Ann, ...)
type city = (London, Paris, Nancy, Roma, ...)
type writer = (Hemingway, London, ...)

Of course, I am abbreviating illegally, since the list must be
completely enumerated.

But if I use the identifier Nancy in the program, I may not know
which is meant, the girl or the city. This can be resolved by various
means (scoping, casting, etc.)

You do not usually get this problem with symbols, as there is only one
type and a specific syntax for its values.

If you can define more by abstraction, then you usually have to use
different syntaxes for the values. But this is getting into other
issues.

For more specific points.

Your quote would be more accurate if it said "Symbol is a primitive
datatype ..." A symbol is a value in that datatype.

It is likely that some people will talk of symbols for values of an
enumerated type. Another word is token.  But these two words have so
many uses...  Again, I do not wish to enter a terminology dispute. It
is moderately constructive.


Why is constant always dropped from big O analysis?

When we evaluate complexity of algorithms, we count the number of computation
steps, or of memory locations.  But these costs are in arbitrary
units. For example we have no idea how long it takes on computer X to
actually execute one step of the algorithm.  If you double the
computer speed, you divide the time taken by 2, independently of the
complexity formula, of the big-O complexity.

Hence this complexity is meaningful only up to a constant.

Hence, the 1/2 factor you mention is irrelevant. It is just the same
as changing the computer, or changing the time unit. If you count in
hours rather than seconds, you can get a whooping improvement factor of 3600.
But you wait just as long to get the answer.

Here I did not mention that since it is supposed to be an asymptotic estimate,
we first remove all that is asymptotically negligible

Another useful aspect of this definition of big-O is that you can
ignore in the analysis the fact that some computations steps are more
expensive than others. As long as there is a bound to the cost ratio
between steps, they can simply be all considered costing the
same. This can impact the total time only by a constant factor.
It does make complexity analysis simpler.


quicksort invariant 3 conditions with loop invariant

If $p \leq k \leq i$ then $A[k] \leq x.$
  In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have i = p-1

Although, as you have observed, $i$ is always smaller than $p$ at the start of the loop, it might become bigger because the statement "$i=i+1$" in the loop could be executed. Once $i$ has been increased, for at least $k=p$, we have $p\le k\le i$.

Note that when $p\le i$ does not hold, i.e., when there is no $k$ such that $p\le k\le i$, the condition "if $p \leq k \leq i$ then $A[k] \leq x$" holds automatically. (Recall that the proposition "if false, then anything can happen" is always true.) To falsify that condition, we have to find an instance of $(p,k,i)$ such that $p \leq k \leq i$ but $A[k]\gt x$.

You should be able to figure out the case of the second loop invariant now.


Additional clarification about Simultaneous Multithreading

The confusion seems to be different terminology used in different sub-communities of computer science.  To most computer scientists, simultaneous multithreading, is thought of as any situation in which two threads seem, to the operating system, to be physically executing in parallel.  When computer architects (including the well-known textbooks by Hennessy and Patterson) use the term they are referring specifically to the technique described in the paper: Tullsen, Dean M; Eggers, Susan J; Levy, Henry M: Simultaneous Multithreading: Maximizing On-chip Parallelism, Int'l Symp Comp Arch, (ISCA-22):392-403, 1995.

That is, computer architects are specifically referring to providing two or more hardware thread contexts on the same super-scalar core, and not to simultaneously executing threads on different cores.

Hyperthreading is typically used, by computer architects, as a synonym for the same thing: providing two or more hardware thread contexts on the same physical super-scalar core.  As pointed out by @PaulA.Clayton the term "Hyper-Threading" was invented by Intel as a marketing term, but Intel has sometimes used it to refer to hardware simultaneous multithreding, and sometimes to refer to coarse-grained hardware multithreading on the Itanium 2, but then does not use Hyper-Threading to describe the fine-grained hardware multithreading on the Xeon Phi.


Probabilistic algorithm with two-sided error

Monte Carlo methods are inherently not one-sided, though it's dubious whether they're usually two-sided. The general idea is that in order to estimate the expectation of a random variable $X$, we take the average of many samples of $X$.

For example, suppose that you're a petroleum company, and you're trying to decide where to look for oil. For every square in some grid you have some random variable $X_i$, expressing the probability that there is oil in square $i$, that you can estimate using your (noisy) data. You have some threshold $\theta$ in mind, and will start drilling in every square $i$ for which $X_i \geq \theta$. Using a Monte Carlo algorithm (say, simulating the geological history of the area), you can determine $X_i$ up to some error $\epsilon$. This translates to a two-sided error algorithm.

You can also think of computation in general as having two-sided error. Hardware errors occur with extremely low probability, and they can affect the answer in every which way.


You are indeed allowed to have unreachable states in DFAs (or NFAs, or various other automata models).

You may wonder what is the point of having them, given that they are unreachable and have no effect on the language.

Well, automata are typically not designed by hand. Rather, they are usually obtained algorithmically by translation from other types of specifications, models, etc.

These translation algorithms often don't guarantee that there are no unreachable states, and very often there are many unreachable states.
For example, take the subset construction, that transforms an NFA to an equivalent DFA. There are typically many unreachable states in the naive construction (although it can be optimized to construct only the reachable states).

However, there are other constructions that are much more involved (e.g., the translation of Linear Temporal Logic to Nondeterministic Buechi automata).

In fact, one of the most fundamental algorithms on automata is that of emptiness -- check whether the language is empty. To do so, we look for a reachable accepting state. If automata only had reachable states, we would only have to check whether there are accepting states, but this is not enough.

Finally, I'll remark that this algorithm is often symbolic, in that you don't run it on an explicit automaton, but on a symbolic representation. For example, you can check emptiness of a DFA constructed by determinizing an NFA without actually contstructing the whole thing.


Is a grammar that accepts function declarations, function calls and expressions (at any order!) necessarily cyclic?

There is just no need for rules (or non-terminals) that are cyclic,
which I understand means that, for some non-terminal $X$, you have
$X\stackrel*\Rightarrow X$.

What you often need is recursive rules and non-terminals, such that
$X\stackrel*\Rightarrow uXv$, where $u$ and $v$ are strings of
symbols. Without them, the language is finite.

For example, in the case of expressions you may have:

$Expr \to Term + Expr \mid Term$
$Term \to Factor * Term \mid Factor$
$Factor \to Ident \mid Literal \mid ( Expr )$

This said, you are right that cyclicity, as you define it, does make
the grammar ambiguous iff the cyclic symbol can also derive on a
terminal string.


Proving non-confluency and adding an equation to make it confluent and terminating

The notion you are looking for is that of critical pair (see the wikipedia entry for instance). The idea is to find the "most simple" term which allows both rewrite rules to be applied. In this case the rewrite rules are:

$$ f(f(x))\rightarrow x$$
$$ f(a) \rightarrow b$$

To find a critical pair, you look for the most general (in a precise sense) instance of the variables on the left-hand side which allow one term to be the (non-trivial) subterm of another. In this case, we can instantiate $x$ to $a$ and obtain

$$ a\leftarrow f(f(a)) \rightarrow f(b)$$

This is a most general instantiation: we can't apply both rules if $x$ isn't sent to $a$. The equations you gave imply $a = f(b)$. To obtain a confluent rewrite system, we therefore need to add one of two rules:

$$ a \rightarrow f(b)$$
or
$$ f(b)\rightarrow a $$

Note that either rule will not make more terms equal, as the equality already holds! We can choose either rule to add to our system, but it is tempting to add the second one, as it seems more "computational". Now you have made your critical pair harmless: $f(f(a))$ rewrites to $a$ regardless of our choice of rule applications.

But we are not done! We have a new critical pair:

$$ b\leftarrow f(f(b))\rightarrow f(a)$$

However that critical pair is harmless, as both sides reduce to $b$.

Now every critical pair is harmless, and so we have verified the property of local confluence. This by itself is not enough to have confluence! However in your case, you have the additional property of termination: no term has an infinite rewrite sequence. This, in combination with local confluence, implies confluence, thanks to Newman's lemma.

Note that this whole approach (find critical pairs, add rewrite rules, check for termination, repeat) can be made systematic, to attempt turning any rewrite system into a terminating one; it is often called Knuth-Bendix completion.


Ordered set cover problem: is it NP-hard?

The decision version of your problem is NP-hard (and so, NP-complete), by reduction from SAT.

Let $\varphi$ be a SAT formula on variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. The universe will be $\{x_1,\ldots,x_n,C_1,\ldots,C_m\}$. For every literal $x_i$ or $\bar{x}_i$, there will be a set $S_i$ or $\bar{S}_i$ consisting of $x_i$ together with all clauses satisfied by the literal, in which all elements have unit weight. This instance has a solution of weight at most $n$ if and only if $\varphi$ is satisfiable.

Indeed, if $\varphi$ is satisfiable, then the sets corresponding to a satisfying assignment are a solution of weight $n$, in any order.

Going in the other direction, Suppose that $T_1,\ldots,T_r$ is a solution of weight at most $n$. Any solution must cover $x_1,\ldots,x_n$, so it must contain either $S_i$ or $\bar{S}_i$. If a solution contains both $S_i$ and $\bar{S}_i$, then the one which appears later must have zero cost, that is, its elements must all be covered by preceding sets; so the solution remains a solution even if we remove it. Therefore we can assume that exactly one of $S_i,\bar{S}_i$ appears. The corresponding truth assignment is easily seen to be a satisfying assignment of $\varphi$.


What is the complexity of this prime trial division algorithms?

The first one is easy: Figure out how often you will iterate through the loop in the worst case.

The second one is harder: Again, you need to figure out how often you will iterate through the loop. However, you also need to figure out how long it takes to calculate the list of primes, and how long it takes to enumerate all those primes.

In practice, you would likely check many numbers for primality, so you wouldn't create a complete new sieve every time, but keep the previous sieve, and extend it when checking a larger prime number.


what is the difference between Operating system and Window Systems?

I think you misunderstand the window systems. It is software to manage different parts of the display screen, not the Windows OS. In Microsoft's Windows OS, the window system is Desktop Window Manager.


When the row and column permutations are different and the consecutive triples have to be increasing: The answer is always YES.

Suppose the matrix has size $N\times N$. Consider a random permutation of the columns. Each row (by itself) is a random permutation. The probability that the numbers $i,i+1,i+2$ appear in positions $t,t+1,t+2$ is $1/(N(N-1)(N-2))$. There are $N-2$ choices for $t$ and $i$, and $N$ different rows. Therefore the expected number of consecutive triples is $N(N-2)^2/(N(N-1)(N-2)) < 1$. We conclude that there is some permutation of the columns, under which there are no consecutive triples in any of the rows. Now repeat the same argument for the columns - note that permuting the rows cannot create a consecutive triple in any of them.

When the row and column permutations are the same, and consecutive triples can be either increasing or decreasing: The answer is still YES, for large enough $N$.

The idea is to use the lopsided version of the Lovász local lemma, via Lu and Székely's paper Using Lovász local lemma in the space of random injections. In the earlier proof, we considered events $X_{\ell,i,t,\sigma}$ for $\sigma \in \{\pm 1\}$, which for a line $\ell$ (either a row or a column), state that $\ell(i+\sigma\delta)=t+\delta$ for $\delta \in \{0,1,2\}$. These are examples of the canonical events considered by Lu and Székely: if the random permutation (permuting both rows and columns) is $\pi$, then they are of the form $\pi(t)=j_0,\pi(t+1)=j_1,\pi(t+2)=j_2$, where $j_\delta = \ell^{-1}(i+\sigma\delta)$. Two events $X_{\ell,i,t,\sigma},X_{\ell',i',t',\sigma'}$ conflict if $\{t,t+1,t+2\} \cap \{t',t'+1,t'+2\} \neq \emptyset$ or $\{j_0,j_1,j_2\} \cap \{j'_0,j'_1,j'_2\} \neq \emptyset$ (this is actually only a necessary condition). Each event conflicts with at most $2N\cdot 2\cdot 2\cdot 5 - 1= 40N-1$ other events ($2N$ lines, two orientations, two ways to conflict, five conflicting positions). While non-conflicting events are in general dependent, using the lopsided version of the Lovász local lemma we can ignore this, and let our dependency graph include edges only for conflicting events. Since the probability that each event happens is $p = 1/(N(N-1)(N-2))$ and the size of each neighborhood is $d \leq 40N-1$, the lemma applies whenever $ep(d+1) \leq 1$, that is
$$ 40eN \leq N(N-1)(N-2). $$
This condition is satisfied for $N \geq 12$. We conclude that for $N \geq 12$, the required permutation always exists. Using the recent constructive version of LLL, we can even find it efficiently.


A restatement of Moore's law that takes into account quantum computing

Quantum computers are interesting, but I don't think the primary motivation for quantum computers has anything to do with Moore's law.  You might want to double-check where you got that impression from.  Quantum computers -- if possible -- will be faster for some narrow set of problems, but by no means for all problems.  See Why and how is a quantum computer faster than a regular computer? and Is it proven that quantum computation is no better at solving NP complete problems than classical computation?.

It's not really accurate to say that adding another qubit doubles the computational power of the computer.  I suspect you might be falling for a common misconception about quantum computing (that they "try all possible combinations...").  See The Limits of Quantum by Scott Aaronson for some explanation.

I don't think there is any need to restate Moore's law.  It is a rough rule of thumb about classical computers.  It doesn't claim to say anything about quantum computers or computational power in general.


What is the maximum number of shortest paths between any pair of vertices in a chordal graph?

It can be exponential in $n/2$.  The following graph has $2^{(n/2) - 1}$ shortest paths between the endpoints:

This graph has $2^{(14/2)-1} = 2^6 = 64$ different shortest path, each corresponding to a selection of "ups" and "downs".


'Texas Hold Em Poker' Agent Heuristics to help decide whether to fold or bet?

Here are some of the heuristics I use when playing online on XBOX live against bots, but the game is so much better with human players, bots are boring and predictable.

Obviously, what are you hold cards. Rockets to 7-2 off suite. There are many poker tables that give you the odds for the hold cards.
How many players at the table. The more players you have the better your hand has to be because more cards are in play for making better hands. When you get down to one-on-one, even a high card is often good, but with a table of 10, you should be holding at least a high pair after the river.
Is the card generator truly random. For the XBOX live games it is rumored they use a card generator named the "Action Engine" because it is designed to generate action on the table by setting up possible flushes and straights. You would not believe how many people chase down the river hoping for a straight or flush, problem is they tend to get it more often than random because of the simulated gambling.
Is there a pattern to the players betting? Do they continue to bet on each card? Do they slow play when then have a good hand or the nuts? Do they bet really big when bluffing? Do the bet really big when they have a high card or better? I their betting related to the the cards they have? Do they ever bluff?
Are you allowed to keep a database of all hands? This is a big advantage if allowed.
Position. Are you the dealer or in the blind? Ever heard the saying that poker is a game of position.
Does a player re-raise?
Does a player fold before or on the river to hide their cards if they don't believe they have a good hand even if they can check?
Do they play most hands or are conservative. A conservative player will bet only on good cards and you can pretty much count on that, while a player who plays most to all hands means that you have to more attentive to them having the nuts from the flop no matter what the flop is.
Does the player have a limit they never bet or raise beyond?
How many out cards do you have versus all of the possible out cards.
Does the player play the heavy? At what level will they play the heavy against another player?
Is the player afraid to call an all-in.
Is there a level below they will not raise? I.e. only raise if a King or higher in their hold cards, or have a pair or higher with what's on the table?
Do they go all in if the best hand can only be made by the cards on the table?
Do they bluff more when A's, or possible straights or flushes appear?
Is there betting based on money amounts or multiples of the blind?
Does there style of play changed based on their money amount? Based on a multiple of the blind? Based on who sits next to them?
Can you use the length of time the opponent uses to play a turn to your advantage?
Is the player trying to win the game or just play to make it to the money rounds?
Are the players susceptible to being pulled into betting wars?
Can betting big on the river cause the player to fold more than normal?
Can always re-raising a player get them to change their playing style?
Are their bet amounts increasing or decreasing as the hand progresses?
Is there a minimum amount they always bet no matter what they have in the hold?

These are just the basic ones for playing a bot, if you add a human player the list of heuristics gets much more complicated.


How expensive is it to verify that a gate is universal?

The problem is actually much more tractable than the other answers suggest.
Specifically, for your first problem

assume we are given  two input, one output gates, where the gates are specified as a truth table.

I give an $O(n)$ solution. The problem is more difficult in the generalization to where each gate has $m$ inputs, where the solution below will be $O(n \cdot m \cdot 2^m)$. But this is in principle kind of unavoidable, because it actually takes $n \cdot 2^m$ just to write out all the truth tables. In other words, if you don't spend this amount of time, you won't even be able to test all possible inputs to your existing gates, so it makes sense you wouldn't be able to determine universality. It's possible the additional $O(m)$ factor can be avoided, though it's not very significant compared to the $2^m$.
I will give a solution that:

Either proves universality or disproves universality, in a finite amount of time; and
Works for any number of gates.

The solution actually falls out of a very beautiful and lesser-known theorem of universal algebra due to Emil Post in 1941. Your problem is, given a set of gates, to determine if they are Functionally Complete.
In what follows, we assume that constants are not allowed; but if you prefer to allow the constants $1$ and $0$, then just add constant gates (with 0 inputs) that output $1$ and $0$, respectively.
Theorem (Post, 1941). A set of gates is NOT functionally complete if and only if one of the following five conditions is satisfied:

All of the gates are monotone. This means that if any of the inputs change from false to true, the output will only change from false to true and never from true to false (if it changes at all). For example, AND and OR are monotone; NAND, NOR, and NOT are not.

All of the gates are affine. This means that the output depends in a "linear" way on the input; it means that the gate is really just an XOR of some of the input variables. NOT is also affine.

All of the gates are self-dual. This means that switching false and true in all inputs always switches false and true in the output. For example, NOT is self-dual as is the MAJORITY gate, but AND, XOR, and OR aren't. Note also that if you allow constant inputs (1 and 0), then these are not self-dual and so this criterion is not satisfied.

All of the gates are  truth-preserving. This means that if all inputs are true, the output is true. For example, the constant 1 is truth-preserving, as is AND, but 0 is not.

All of the gates are false-preserving. This means if all inputs are false, the output is false.

We can use this theorem to derive the following $O(n \cdot m \cdot 2^m)$ decision procedure for deciding whether $n$ gates, with $m$ inputs each, are expressively complete.

First run through all the gates, and check if they are truth-preserving or false-preserving. This can be done in $O(1)$ per gate because we only have to check two inputs (all false, and all true). If all gates are truth-preserving or all are false-preserving, return false.

Next run through all gates and check if they are self-dual. This takes $O(2^m)$ per gate because we need to check, for each input, how it compares to the negated input where true and false are switched. If all gates are self-dual, return false.

Next we run through all gates and check if they are monotone. This requires checking for each of the $2^m$ possible inputs, what happens if any of the $m$ input wires switch from false to true, so it takes $m \cdot 2^m$. If all gates are monotone, return false.

Finally, we run through all gates to check if they are affine. Iterate through each of the $m$ input wires. For each wire, then try all possibilities for all the other $(m-1)$ wires, with that wire both true and false. If the gate is affine, you should see that irrespective of the other wires, either this wire always has no effect on the output, or it always flips the output. If neither of these behaviors is observed for some input wire then the gate is not affine. If all gates are found to be affine, return false.

Otherwise, once all of these checks pass (there's at least one non-truth-preserving gate, at least one non-false-preserving gate, at least one non-monotone gate, at least one non-self-dual gate, and at least one non-affine gate), then return True.
Note: If you are allowing constant inputs 1 and 0, then modify the algorithm by removing the "self-dual", "truth-preserving", and "false-preserving" checks. So, all you have to do is check if all your gates are monotone and if all your gates are affine.

Finally, here are a couple of examples to illustrate the way the theorem works. First, for the NAND gate: NAND is special because it is not false-preserving, not truth-preserving, not monotone, not self-dual, and not affine. As a result, it alone is functionally complete. Another common example of a functionally complete set of gates is NOT and AND. In this case: NOT is not truth-preserving, false-preserving, and monotone, covering those three requirements; and AND is not self-dual or affine, covering the other two requirements. But if either AND or NOT is dropped, then not all five requirements are satisfied.


Question in coreset construction fro K-median clustering

Of course not. Otherwise the construction would be "pick an arbitrary set of centers".
You can follows the proof and see that the size of the coreset depends polynomially on $\beta$ and $\alpha$.
If they are $O(1)$ they can be hidden in the $O()$ notation. Otherwise, someone needs to  pay.  See more details in Section 6 here:
https://arxiv.org/abs/2011.09384


Converting Vor's comment into an answer:

the table looks incorrect.

Specifically: for P3, P4, P5 the table wrongly reports (completion time - processing time) instead of (completion time - arrival time).


Solving a graph problem by Gaussian elimination

As, no good solutions were given and my research else where proved to be helpful, I am answering my own question. The main idea of the solution is correct.

The number of independent variables controls the total possible way of coloring but the matrix construction is little different.

The matrix will look like this for the following graph.

A graph with 4 nodes $\{1,2,3,4\}$ and 4 edges $\{(1,2),(2,3),(3,4),(4,1)\}$ provides us the equations,

$col_1 \equiv (col_2+col_4)\mod k$

$col_2 \equiv (col_1+col_3)\mod k$

$col_3 \equiv (col_2+col_4)\mod k$

$col_4 \equiv (col_1+col_3)\mod k$

Providing us equations like,

$(col_1 -col_2-col_4)\mod k \equiv 0$

$(col_2 -col_1-col_3)\mod k \equiv 0$

$(col_3 -col_2-col_4)\mod k \equiv 0$

$(col_4 -col_1-col_3)\mod k \equiv 0$

We form matrix like this for these equations:

$$
\begin{bmatrix}
1 & k-1 & 0 & k-1\\
k-1 &1 & k-1 & 0\\
0 &k-1 & 1 & k-1\\
k-1 &0 & k-1 & 1\\
\end{bmatrix}
$$

Not to mention for every step of Gaussian elimination we have to use mod operation, if any number is negative take the equivalent positive mod.

Then, for every independent variable we can assign a value from 0 to (k-1) and get solution for every of these equations. If number of independent variables is $x$ then the answer will be $k^x$


Applying dynamic programming to a simple two-person game of perfect information

Since you want to calculate $X(1), X(2), X(3)$,... and not just some $X(i)$, you can start from $X(1)$. Let's denote the case where there is a winning strategy for first player by $1$ and the other case by $0$.

Clearly, value of $X(i)$ for $i \in \{1,2,3,4,5\}$ is $1$. Let's store the values of $X(i)$ that we computed in an array. For $i>5$, if at least one of the values of $X(i-2), X(i-3), X(i-5)$ is $0$, then the value of $X(i)$ will be $1$. If none of them is $0$, then the value of $X(i)$ will be $0$.


How is the Delta Rule derived in neural networks and what is the explanation for the algebra?

Your equations are wrong on several counts. First of all, the weights and the inputs are both vectors. Second, the value of actual is given by $\operatorname{sgn}(\langle \mathit{Input}, \mathit{Weights} \rangle)$, in words, the sign of the inner product of the input and the current weights. Similarly, the desired output is either $+1$ or $-1$. Therefore the error is either $+2$ (if the desired was $+1$ but the actual was $-1$) or $-2$ (in the opposite case). Third, we don't want to "solve" for the weights, since this would erase everything that we have learned so far.

The idea of the learning process is to give negative feedback. Suppose that we got $-1$ but we expected $+1$. We want to change the weights so that on the same input, $\langle \mathit{Input}, \mathit{Weights} \rangle$ will be larger. The most economical way (in some sense) is to update the weights with a new vector proportional to the input, since the input is the vector most correlated with itself (that is, the unit vector $w$ maximizing $\langle \mathit{Input},w \rangle$ is proportional to $\mathit{Input}$). Thus we increase the weights with some multiple of the input. If the error were in the other direction, we would decrease instead of increase — which is why we multiply the input by the error.


Hilbert's 10th Problem and Chaitin's Diophantine Equation "Computer"?

Good question.  It sounds like you might need some additional background on Hilbert's 10th Problem.  I hope this isn't overkill.
The problem asks:

Is there an algorithm that, given a Diophantine polynomial, decides whether or not there is a setting of its variables that makes it equal to $0$?

This was resolved in the 70's as a consequence of the MRDP (also called Matiyasevich's theorem, if you feel like searching it) which states:

Define: A set $D \subset \mathbb{N}$ is Diophantine if there is a Diophantine polynomial $p$ on $k+1$ inputs such that $D = \{ x \, | \, \exists y \in \mathbb{R}_+^k \, p(x, y) = 0\}$.
The Diophantine sets are precisely those that are recognizable by Turing machines.

This theorem is obvious in one direction (every Diophantine set is recognizable by a Turing Machine -- on input $x$, simply have your machine start guessing vectors $y \in \mathbb{R}_+^k$, evaluate $p(x, y)$, and halt if/when you find that $p(x, y) = 0$).  It is very non-obvious in the other direction -- why is it true that every Turing recognizable set is Diophantine?  The encoding schemes are disgusting, but trust me, it can be done.
Anyways, how does the MRDP theorem resolve Hilbert's 10th problem?  Well...
For the sake of contradiction, let's pretend we have an algorithm that, given a Diophantine polynomial $p(y)$, decides whether or not there is an input vector $y$ that causes $p(y) = 0$.
Now I'm going to use this magical algorithm to solve the halting problem.  Given a machine, I will use the disgusting encoding of Diophantine equations to convert the problem "Does $M$ halt on input $x$?" into the problem "Does the Diophantine polynomial $p(y | x)$ have a set of inputs that make it equal to $0$?"  Then I will use my magical algorithm to solve this problem, and now I have solved the halting problem.
Of course, this is impossible, so in reality there can't be a magical algorithm that searches for an input vector that causes $p(y) = 0$.  Similarly, there can't be an algorithm that looks at two Diophantine polynomials and decides if they're ever equal.  That's what Chaitin is saying.


Reviews of work in the field of partial evaluation (post 1993)

The PEPM (Partial Evaluation and Program Manipulation) Symposium Series is still running. That'd be a good place to start to see what the current hot topics are and who is still working on Partial Evaluation.


Do deterministic context free grammars always have corresponding deterministic push down automata?

I would agree with you, but local definitions may differ.

One point might be the definition of $L(M)$. What is the acceptance type of the PDA? That might be "empty stack" or "final state". For deterministic PDA the two modes of acceptance are not equivalent. But also here wikipedia agrees that $L$ indicates final state, which is commonly used for DCFL.


Does a multi-agent system have to have a synchronous component in order for the agents to cooperate?

You're asking about a problem known as leader election.  There are various computational models one can consider, based on what we assume about how the network works and what agents are allowed to do.

The Wikipedia article claims there are no deterministic algorithms for leader election in a setting where all agents start from the same state (have no identity) and are situation in a ring (so connectivity is symmetrical); see https://en.wikipedia.org/wiki/Leader_election#Anonymous_rings.

At the same time, there are randomized algorithms for leader election that work if we make some assumptions about network delay (e.g., that messages won't be delayed forever), and if you're willing to accept algorithms with a finite expected running time.  For instance, a very simple starting point is for each node to pick a random number and broadcast it, and then select the agent with the lowest number as the leader.  In case of ties, repeat the entire procedure.  There are additional details one must work out, depending on the model of computation and the assumptions about communication.

There's lots of research on this topic in the distributed systems literature.  You might want to spend some time reviewing the papers that have been published in that field, to see what you can find.


Fast and space efficient data structure for nearest neighbors in 3 dimensions?

I like Drost's hierarchical voxel hashing. It has an average time complexity of $O(log(log(|D|)))$, where $|D|$ is the number of points in data cloud. While the construction is a bit more tedious, searching gets much faster.

The method is also extended to a journal version, found under this link.


Among $k$ unit vectors, find odd set with sum length less than 1

The latter problem feels similar to the Shortest Vector Problem (SVP) in integer lattices.

The Shortest Vector Problem is:

Input: vectors $v_1,\dots,v_k$
Goal: find a non-empty subset of vectors whose sum has length as short as possible

Your problem is:

Input: vectors $v_1,\dots,v_k$
Goal: find a non-empty subset of vectors whose sum has length $\le 1$, such that the number of vectors in the subset is odd

If we omit the "odd-size" constraint for the moment, the two are very similar: one asks for the sum to be as small as possible, the other asks for the sum to be $\le 1$.  Thus, any algorithm for SVP would immediately yield an algorithm for your problem (ignoring the odd-size constraint).  And solving your problem sounds like it might be about as hard as the SVP (if we replace $\le 1$ with $\le t$ where $t$ is an additional input, your problem becomes as hard as the SVP; reduction by binary search on $t$).

Unfortunately, the SVP is hard: roughly speaking, it's hard if $P \ne NP$ (this isn't quite right, but it's close).  This makes me think that your problem might be hard, too.

That said, there are approximation algorithms for the SVP.  You can use LLL lattice reduction to find a subset whose sum is not too much larger than the shortest possible.  Unfortunately the gap between "the true minimum" and "what LLL finds" is pretty large, so this might not be good enough in practice.  But it is something you could try and see if you get lucky.

I'm not sure how to accommodate the extra restriction that the subset be of odd size.  You could try solving with LLL reduction and hope the resulting subset has odd size (50% chance). I can't think of a better technique, unfortunately.


Table-driven lexers in Engineering a Compiler 2nd Edition

Let me answer your questions very quickly:

NextChar(char) reads a character and assigns it to the variable char.
The new character is appended to the current lexeme being built via the command lexeme = lexeme + char.
The table Delta implements the transition function $\delta$ of a DFA (sometimes called an FSM). There is a lot of information on DFAs on the web and even on Computer Science.

I was able to answer these questions via a combination of common sense and a very rudimentary knowledge of how lexers work. More generally, when faced with code or pseudocode which you don't quite understand, you should try to figure out what the code is trying to accomplish, and how. For example, NextChar surely reads a character. You might expect it to return it, but from the context it is clear that it is actually stored in its argument. The fact that it is adjoined to lexeme significantly strengthens this guess.


I don't see anything wrong with storing a playlist as a plain text file.  Simplicity is not a disadvantage.  It's likely to be more than efficient enough, given the size of a typical playlist (implement it and see!).


Insertion sort vs Merge sort - memory access

The implementation of merge sort that your instructor has in mind accesses memory sequentially, in the sense that merging steps from left to right over the two arrays being merged and the target array as well.  Insertion sort has a more complicated memory access pattern.

As you note, if you sort linked lists instead of arrays, insertion sort also conceptually moves from left to right.  However, the implementation of linked lists will still do pointer operations that lead to non-sequential memory access.


Why the given lexical specification will not process the following strings?

The strings not processed successfully are 1, 2, and 3. Only string 4 is processed successfully.

I think your problem is not with interpreting the meaning of regular
expressions, but in understanding the process of lexical analysis, at
least as intended in your course.

Normally, a regular expression is supposed to match a string from
beginning to end. But when doing lexical analysis of a program, you
are supposed to cut the program text in small chunks coresponding to
the lexical elements of the language, which in turn can be taken (up
to some details not relevant here) as the terminal alphabet of the
(usually Context-Free) grammar used to define the language you are parsing.

So, during lexical analysis, you have nothing to indicate the end of a
lexical element, as the program text goes on to give the next lexical
element. For example, if you are scanning the string $foobar$, is it
the identifier $f$ followed by $oobar$, or $foo$ followed by $bar$, or
$fo$ followed by $oba$ and $r$. For a strict lexical point of view,
all these possibilities would be correct ... though the grammatical
parser that will use the lexical element can be unhappy with some
choices.

To simplify matters, a simple rule is often followed by scanners performing lexical analysis, called maximal munch rule, or longest match rule. It works as follows:

While recognizing a lexical element, the lexical analyzer
will keep reading the input string as long as it is reading a prefix
of a lexical element, according to the lexical specification, and will
halt when the next symbol to be read would no longer constitute such a
prefix if added to the part of the input already scanned. At that
point, if the scanned string corresponds to a complete lexical element
(i.e. the scanning automaton is in an accepting state), this lexical
element has been recognized. If it is only a prefix of a lexical
element that cannot be completed with what follows into a proper
lexical element, you have a lexical analysis error.

Thus with your example 1, $0111110$, the lexical analyser will start
recognizing the second regular expression $01^+$, and will scan
$011111$ as one lexical element. Then it is left with only $0$ which
is the prefix of a word in the first two regular expression $(00)^*$
and $01^+$. But then the string stops, so that it cannot be part of a
complete lexical element. hence the lexical analysis fails with an
error at that point.

You could say that if you had stopped the first lexical element one
symbol earlier, thus recognizing $01111$. Then you would be left with
$10$ which is recognizable by the third regular expression $10^+$. But
that is not how things work. There is no backtracking (actually, some scanners have more complex rules allowing for some backtrack, for example for the programming language C). Allowing this
would also make thigs a lot more ambiguous as I explained in the
$foobar$ example.

In the second example $01100110$, you get $011$, then $00$, and you
are left with $110$. The first $1$ is a prefix for the regex $10^+$,
but it should then be followed by at least one $0$, which is not
there. Hence lexical analysis fails.

However, the third example $0001101$ should fail too. The reason is
that symbols are read one by one. The first $0$ is a prefix for both
regex $(00)^*$ and $01^+$. But, on scanning the second $0$, we know we
are looking for a lexical element defined by the forst regex
$(00)^*$. Then the third $0$ is ok too, since $000$ is a prefix of
$0000$ which is recognized by the first regex. So it is scanned. But
now we need a $0$, and we find a $1$. So the lexical analysis fails.

My guess is that the designer of the exercise recognize too quickly
that it could work, by stopping one $0$ early (and I did too the first
time I read this). But the computer does not have this global
perception, and proceeds one symbol at a time.

The fourth example $01100100$ works fine, yielding $011$, $00$, and $100$.

If backtracking were allowed, all four strings could be scanned into
lexical elements.

But the fourth string could then be scanned as:

$011$, $00$, $100$, or
$01$, $10$, $01$, $00$

Though you can use a rule that you backtrack only in case of failure,
to avoid such an ambiguous situation.

Of course, there is the possibility that your instructor defined things differently, but this is the best I can do with the information I have.


How to get Algorithm complexty based on another 2 algorithms?

The total running time of $_3$ will be bounded by $()+()$ where $$ is the size of the input to $_1 $and $$ is the size of the output of $1$. Now time complexity is usually written in terms of the size of the input of the algorithm and nothing else, so if $=()$ then the running time of $_3$ will be $\mathcal{O}(p(x)+q(f(x)))$


How can i solve a recursion equation with square root using recursion tree method?

If you apply the recursive formula again to $T(n/2)$ you get the following:
$$ T(n) = \sqrt{2}\cdot T(n/2) + \sqrt{n} \\T(n)= \sqrt{2}(\sqrt{2}\cdot T(n/4) + \sqrt{n/2}) + \sqrt{n} \\T(n)= 2\cdot T(n/4) + 2\sqrt{n}$$

For this formula you are now probably able to draw a recursion tree.


Find a CFG for $\{a^ib^jc^k \mid i,j,k\ge0 , \text{if } j=1 \text{ then } i=k\}$

$ S =>S_1 \mid S_2 \mid S_3 $

$ S_1 =>AC  $

$ S_2 => aS_2c  \mid b $

$ S_3 => AbbBC $

$ A =>aA \mid epsilon  $

$ B =>bB \mid epsilon  $

$ C =>cC \mid epsilon  $


$\lceil \lg n \rceil$.

For example, for $n=10$, try ABACABADAB.  See if you can work out the pattern.

(I'll leave it at that, as this is a nice exercise problem and I'll let you have the joy of solving it on your own.)


I cannot find an invariant for the following program

Figure out what the value of y is, depending on x, a, and c. Prove that your formula is correct before the first iteration, and prove that if it is true before an iteration then it is also true after the iteration.


Pay no attention to the letter $Q$.  $Q$ is just a "short-hand" for "the $N$th letter".  Think of $Q$ as a kind of variable, rather than a letter itself.

In other words, ignore the Q bit, and keep reading.  If you like, think of it as A, B, C, ..., L, and pretend that was just a typo.  Keep reading.

Let me give you some advice about reading papers.  If you find some detail you don't understand, often you can keep reading and see if you can still understand what is going on.  Sometimes there will be a typo in the paper that is small or inconsequential.  Sometimes it's a detail but if you keep reading you can still understand much of the rest of the paper.  Sometimes the paper is actually correct and once you absorb the rest of the ideas in the paper, when you go back and re-read the paper you'll realize what the authors actually meant.  (Of course, occasionally you'll discover a serious fundamental flaw in the paper.  But don't jump to assuming that's the case; that should be your last hypothesis, rather than your first hypothesis.)

If you still can't understand the paper, try to find other papers that cover related topics -- e.g., that it cite or that cite it -- and build up your understanding of the area.  Then, come back and read the paper again.

Often, if you follow these strategies, you'll be able to work out what is going on.  These are useful skills -- they will make you more self-reliant and more effective at getting value out of the research literature.


Does a reentrant list for signal queue in a single-thread environment exist?

Finally I found a solution, which handles the whole problem at once. It is relatively easy. They key to the solution: we can use the signal stack as a "to-do stack".

Important to remember, that although this problem is also about race condition eliminiation, its solution differs significantly from the "lock everything what you use, do your task, release everything" solutions. It is because it is not about parallelisation, it is about reentrancy. The common lock-based solutions would lead to deadlock here, because the parent (in the example) signal1 handler will be surely suspended while the whole execution of the handler of signal2.

So, this is a disadvantage, but it is an advantage as well. We can guarantee, that signal1 won't do anything while our signal2 runs. We can't simply lock things, but we also don't need to do them.

So, that blocking locks are closed out, only the nonblocking locks left. What I invented, is the following C code:

#define STORE(a, b) __atomic_store(&(a), &(b), __ATOMIC_SEQ_CST)
#define SWAP(a, b) __atomic_exchange(&(a), &(b), &(b), __ATOMIC_SEQ_CST)

// action handler wrapper
void ss_wrapper(int signum, siginfo_t* siginfo, ucontext_t* ucontext) {
  // currently top element on the signal stack
  static struct ss_hit *top = NULL;

  struct ss_hit *hit = ss_hit_new(signum, siginfo, ucontext);
  struct ss_hit *bkp;

  again:

  bkp = hit;
  SWAP(top, hit);
  if (!hit) { // we got the lock, we are the master
    ss_fire(bkp);
    SWAP(top, &bkp->next); // release the lock, find out if there is new element
    if (bkp->nxt) { // there IS

      hit = bkp;
      free(bkp);
      goto again;

    } else
      free(bkp);
  } else { // we didn't got the lock, but we got the top in hit
    STORE(hit->next, bkp);
  }
}

As we can see, it had been very beautiful to have a separated, reentrant stack (and not list) data structure.

The main problem was to understood, that

adding new element in the stack, AND testing if it is empty, they should be done in a single atomic operation (this is why top serves as both of spinlock and pointer to the top of the stack)
similarly, removing element from the stack, and to know, if it is now empty, should be done also atomically.

I also learned from this some days of thinking, that
* constructing reentrant algorithm is much harder as to contrust a multithread
* the most important thing is that reentrant algos should have only very few variables to interact eachother through them, and all operation should be atomic on them.


Basic control statements for Turing equivalence?

for(X; Y; Z) { Body; } is just syntax sugar for {X; while (Y) { Body; Z; }}.

if can be simulated easily: rewrite if (X) { Body; } as while (X) { Body; break; }.


How do IR researchers evaluate the ranks of documents?

If I understand what you're trying to achieve correctly, you can use this technique discounted cumulative gain.

$$DCG_p=\sum_{i=1}^{p}{\frac{2^{rel_i}-1}{\log_2{(i+1)}}}$$

$i$ is the rank, and $p$ is the number of results that you want to evaluate. For example, if you evaluate DCG for the first 10 results, then $p=10$.

NDCG is a form of DCG that involves normalizing the result. This is useful if p differs when you compare DCG scores.
$$NDCG=\frac{DCG}{IDCG}$$ where IDCG is the ideal DCG. This is found by calculating the DCG up to $p$ under ideal conditions (all documents have a relevance of 1).

Note that neither recall nor precision are used here. Relevance and rank are the factors to compare. You still need to give the documents a relevance factor, that's unavoidable, but you don't need to establish a threshold as you would with other evaluation metrics.


Is unconstrained quadratic programming NP-hard?

1-IN-3SAT is an NP-complete variant of 3SAT in which the goal is to determine whether some assignment satisfies exactly one literal per clause. We can convert an instance of 1-IN-3SAT (even without the restriction on the number of literals per clause) to an equivalent instance of quadratic programming in which all the variables are constrained to be non-negative as follows:

For each variable $x_i$, the quadratic program has two variables $x_i^+,x_i^-$, constrained to be non-negative.
The objective is to minimize

$$
\sum_i (x_i^+ + x_i^- - 1)^2 + x_i^+ x_i^- + \sum_j (C_j - 1)^2,
$$
where $i$ goes over all variables, $j$ goes over all clauses, and $C_j$ is the sum of all literals in $C_j$: for example, if the $j$th clause is $x_1 \lor \bar{x}_2 \lor x_3$ then $C_j = x_1 + (1-x_2) + x_3$.

By construction the objective function is always non-negative. The first two summands are zero if the $x_i^\pm$ encode an assignment to the original variables, and the third is zero is this assignment satisfies exactly one literal per clause.

Without any constraints, the problem becomes easy. The law of inertia (which can be implemented efficiently) shows that up to a linear change of basis, we can assume that the quadratic to be minimized is
$$
\sum_{i \in A} z_i^2 - \sum_{j \in B} z_j^2 + 2\sum_k c_k z_k + M,
$$
where $A,B$ are disjoint. If $B$ is non-empty then the quadratic form is unbounded from below, so let us assume that $B = \emptyset$. If $c_k \neq 0$ for some $k \notin A$, then the quadratic form is also unbounded from below, so let us assume that the $c_k$ are supported on $A$. Therefore the quadratic is equal to
$$
\sum_{i \in A} [(z_i + c_i)^2 - c_i^2] + M,
$$
showing that the minimum is $M - \sum_i c_i^2$.

A third variant that can be considered is a homogeneous objective function with non-negativity constraints. This variant is also easy.

The law of inertia transforms the problem into that of minimizing
$$
\sum_{i \in A} z_i^2 - \sum_{j \in B} z_j^2
$$
under some arbitrary linear constraints.

Using linear algebra, we can check whether the linear constraints force $z_j = 0$ for all $j \in B$. If not, then the quadratic form is unbounded from below, so let us assume it is the case. Our quadratic form is thus positive semidefinite, and so convex optimization algorithms can be used to solve it (see Wikipedia).


eliminate left recursion of below grammar

$$ → YX \ | \ Y \\
Y → Ab \ | \  b \\
X → ABX \ | \  AB \\
A → SB \ | \  BS \ | \ a \\
 →  \  | \ d$$

At first I say which rules have a left recursion, considering that the middle tree which is A(the one that A node is the root) has not called itself in its children from the beginning of the left of each child so there is no left recursion in tree which A is root.Similarly the right tree(the one that B node is the root) in its children has not called itself from the beginning of the left of each child, so they do not need to remove the left recursion, so They they have the previous rule (the fourth and fifth lines of my answer A→SB|BS|a,→|d ).
So our problem is the tree with the S root.
I come and look at the children of the S root, there is only one child who starts with S from the beginning of the left of child, so I just have to correct one left recursion to right recursion,
Now I know that there are two children left of the tree with S root, since I only have a left recursion which I want to convert to the right recursion, So I have to put those two children on the left side of this conversion to the right! (For example, if we have two of these conversions we have to pack each of two children(with no recursion) with those two conversions.)
So I write the second line of my answer (Y→Ab|b) and then I write the third line of my answer (X→ABX|AB), which is actually the left-to-right conversion, The first line that these two children connect to each other,
and the last two lines are the two trees in the middle and right.


Break an authentication protocol based on a pre-shared symmetric key, with message numbers

(re-post of my comment as an answer)

The only party that generates encryptions of messages $m$ such that $m$:

contains 3 parts
begins with a "2"

is Alice. Each time she generates such a chipertext, the last component is $P_A$. If $E$ is a strong enough encryption (non malleable), then Trudy will not be able to generate by herself a an encryption  $E(m)$ of a massage in the formt $m=\langle 2,R,P_T \rangle $ that Bob would accept (except with negligible probability).


where is all deleted data will go from memory system/internet?

Deleting is not necessarily destroying data. It can be done (much faster, indeed) by making it inaccessible. You can do it by erasing critical information from the data structures that are used to index the data you want to delete. How exactly this is done depends on how the storage device is organized (formatted).


How to determine convergence when using Q-learning?

There are two ways that I know of:
First, based on how many iterations, like you would do.
Second, based on the difference between current Q value and previous Q value (i.e., insignificant difference means termination).


Syntax and formal grammar of a formal language

Syntax is a very general term that encompasses the description and
properties of physical representation of languages, i.e. of sets of
sentences intended to convey ideas, concepts, meanings, etc.  It is to be
contrasted with semantics that is concerned with what is being
conveyed.

Syntax is often thought of as structured sets of strings of symbols on
a given alphabet (sentences), but that is the simpler form. Many syntaxes have a
more complex structure, such as spoken natural language, signed
language, graphical languages, musical scores, etc.

Syntax could be thought of as just a way to describe the set of
legitimate representations, but it is usually expected to also
associate structure with these representations. This structure is the
scaffolding that is used to associate meaning (semantics) with a
syntactic construct.

Grammars are a specific way to define these sets of sentences. There
are other ways, such as automata (e.g. FA, PDA, TM), or string set
expressions (regular expressions). Some types of grammars
(Context-free in particular, but not the only one) are the preferred
medium for expressing syntax as they are complex enough to provide
structure allowing to express semantics with enough perspicuity, while
remaining simple enough to be intellectually tractable.

Regular grammar, for example, do not provide enough structure and
expressive power for general syntactic structure, but are often
adequate for the structure of simpler semantics constituants
(identifiers, numbers, morphological  strcture of natural languages).

On the other hand, while context-sensitive languages can define more
complex sets of sentences, the associated structure is usually too
complex for deriving semantics from it in a simple enough way.

Context-free grammar are convenient because they associate a tree
structure with sentences. This tree structure can be seen as an
expression in a formal algebra, from which meaning can be derived by a
convenient and well understoof mathematical tool: the homomorphism.

There are other ways of associating a tree structure with a sentence,
for example by considering derivation trees with the structure (see
mildly context-sensitive formalisms).

One could also define the syntax with automata, but this is much more
computational and less perspicuous.

Denotational vs operational aspects

The preference for grammars over automata may also be related to the
preference for denotational definitions over operational definition.
Many grammars may be seen as more denotational as they may be read as
equational definitions of syntactic structures. Though it may sometimes be
disputed, denotational definitions are perceived as closer to the
essence and mathematical properties of the defined entity, as giving a
more perspicuous understanding, more appropriate for mathematical analysis, while operational semantics are more
encumbered with technical computational or algorithmic details on the
use of these entities.

Hence, it is common practice to prefer denotational definitions as
reference, including for syntax. Operational tools (such as parsers)
are then derived for practical computational work, and have to be
proved equivalent.

Meta-language issues

Note that, when I say that a grammar "may be read as equational
definitions of syntactic structures", I assume that the grammar itself
is a sentence in a formal language (the language for writing grammar)
and that this language may be assigned one or several semantics by
appropriate means. Indeed, there is at least one well known
standardized language for writing context-free grammars which is the
Backus-Naur Form (BNF).

Actually, different semantics can often be associated with the same
syntax, though they will often be in some mathematical relation,
possibly isomorphic. This is in particular the topic of what is called
"abstract interpretations" and
"non standard interpretations" of languages.

Remark on the question

When answering the question, I did take the expression "formal
language" in a general sense of language formally defined, as often
used in mathematical context, with syntax and semantics. But the
discussion is very much the same in the case of natural language.

Now it is possible that the question was intended only for the
consideration of formal languages as simple sets of strings, as in
formal language theory.

I would tend to think that this should not change much the answer,
since even formal language theory often sees more in its formal
languages than simple set of strings. This is typically the case when
it makes a difference between strong and weak equivalence of grammars.
Furthermore, a grammar is usually only one possible way to define the
language and/or give it structure.


A clarification on the taxonomy of Evolutionary Algorithms

I'm not 100% sure I understand your formulation (things like "our current hypothesis is neutral compared to our current hypothesis" are a bit confusing), but if I understand it correctly, it's this:

You have a current solution and at each time step, you generate a new one based on the current one and some random variation operator. If the new one is better than the current one, you accept the new one. Otherwise, you keep the current one.

That's a $(1+1)$-ES.

A $(1,1)$-ES always accepts the new hypothesis/solution, regardless of quality. A $(1,1)$-ES is just a random walk on the graph defined by your variation operator. For a $(\mu$, $\lambda)$-ES, the algorithm generates $\lambda$ hypotheses at each step, and selects the best $\mu$ of them to form the population for the next generation -- the current hypotheses never survive (unless your variation operator produces a copy of one of them). The $(\mu+\lambda)$ strategy takes the best $\mu$ from the union of the current population and the new one.


Which instruction yields atomicity in this expression that makes the result 2?

The point you are missing is that in thread $y$ is loaded into $r1$ and that any subsequent changes to $y$ will not affect the value stored in $r1$. Thus, the value in $r1$ is $0$ even after statement $y=1$. From this it is easy to see that the result is $x=2$.


Maximal cut is different from maximum cut (MAX-CUT). In maximum cut, the goal is to find a cut cutting the maximal number of edges. In maximal cut, the goal is to find a local maximum: a cut such that switching the side of any single vertex does not result in more edges being cut. Such a cut exists, since the maximum cut is also maximal. But finding a maximum cut is apparently harder than finding just a maximal cut.


Solving $T(n)=4T(n/2)-1$ without using the master theorem

The idea is to convert this recurrence to the simpler recurrence
$$ S(n) = 4S(n/2). $$
How do we do this? Let $S(n) = T(n) + f(n)$. Since
$$
S(n) = T(n) + f(n) = 4T(n/2) - 1 + f(n) = 4S(n/2) - 4f(n/2) - 1 + f(n),
$$
we need that
$$
f(n) = 4f(n/2) + 1.
$$
Luckily, $f(n) = -1/3$ is a solution. So $S(n) = T(n) - 1/3$ satisfies
$$ S(n) = 4S(n/2), \qquad S(4) = 14/3. $$
You take it from here.


Flaw with Cross Entropy Error in Neural Networks

Make sure you use softmax as your final layer.  This will ensure that the outputs sum to 1.  You need this for cross-entropy loss to be meaningful.

Note that the correct cross-entropy loss is

$$-\frac{1}{n} \sum_{i=0}^9 y_i \log \hat{y}_i,$$

where $i$ ranges over all of the classes.  You omitted the dependence on the classes.

Once you change the outputs to use softmax, the anomaly you saw can't happen.  The network can't cause all nodes to output 1, because softmax renormalizes the outputs so they sum to 1.  This then works cleanly with cross-entropy loss, which only makes sense if the outputs are guaranteed to sum to 1 (i.e., cross-entropy loss only makes sense if we have $\sum_i y_i = 1$ and $\sum_i \hat{y}_i = 1$).


Why do we proof the halting problem with turing machines?

You could totally do that, but there are some consequences it's worth being aware of.

TM proofs only show difficulty of the halting problem for TMs, but here's a crucial thing that you might be overlooking: it is easy to implement a simulator of a TM in any language of one's choice.  That can probably be done in a few dozen lines of code and it is conceptually straightforward.  This lets us very easily see that the halting problem is also hard in those other languages, too.
The same is not true for Python.  You can't write a Python interpreter in a few dozen lines of code.

Let me try it another way.
Some languages don't have a __file__ global variable or anything with similar semantics.  That makes it unclear whether your result applies to other languages.
Sure, we could try to write down a reduction.  In some other language, we could build a Python interpreter that supports __file__.  But that's not a trivial exercise!  We might need to implement a filesystem, library functions that interact with the filesystem, a parser for Python code, an interpreter for Python code, and so on.  Nothing you can code up in a few hours, and it's not trivial to construct such a reduction.

Now, sure, your argument does work, so it's just a matter of taste which you prefer.  I am showing you some reasons why someone might prefer the TM proof.  If you prefer the Python proof, that's fine.  That's your choice. I just want you to be aware of the implications of your choice, and for you to understand all of the steps of reasoning that you have to go through, if you want to use it to draw conclusions about other programming languages.  Arguably your choice makes some parts of the reasoning easier, and some parts (the application to other programming languages) harder.


Johansson gave a nearly linear time algorithm (in terms of the output size!) in his paper Efficient implementation of the Hardy-Ramanujan-Rademacher formula. This work is mentioned at the very end of the Wikipedia article on the partition function.


Constant terms at each level of a recursion tree

For each specific level $i$, it is true that the cost is $(3/2)^i n - O(1)$. However it would be misleading to state this in general. Suppose for example that the cost at level $i$ were $(3/2)^i n + 2^{2^i}$, and that there were $\log n$ levels. The dominant factor in the total cost would be the "constant" term.
However, in your case, you can say that the cost at level $i$ is at most $(3/2)^i$, which gives you the required upper bound.


The two sets are clearly different – there are Turing machines whose language is infinite but doesn't consist of everything. However, both languages belong to the same Turing degree, that is, each of them can be reduced to the other (computably).

Given an instance $M$ of ALLTM, construct a Turing machine $M'$ which on input $x$ runs $M$ on all inputs $y \leq x$ (in some arbitrary computable ordering of all strings). Then $M$ is total (i.e., halts on all inputs) iff $M'$ halts on infinitely many inputs.

Given an instance $M$ of INF, construct a Turing machine $M'$ which on input $x$ runs $M$ in parallel on all inputs $y \geq x$, and halts once one of the runs halts. Then $M$ halts on infinitely many inputs iff $M'$ is total.

(In fact, both ALLTM and INF are $\Pi_2$-complete.)


Largest N squares that fit in a rectangle

Let

\begin{align}
C&=\left\lfloor\frac WL\right\rfloor&
R&=\left\lfloor\frac HL\right\rfloor
\end{align}

be the maximum number of rows and columns respectively. It sounds as though you're looking for the maximum $L^*$ such that, when $L=L^*$, we have $CR\ge N$. Let

\begin{align}
L_0&=\sqrt{\frac{WH}N}\\
C_0&=\left\lceil\frac W{L_0}\right\rceil=\left\lceil\sqrt{\frac{WN}H}\right\rceil&
R_0&=\left\lceil\frac H{L_0}\right\rceil=\left\lceil\sqrt{\frac{HN}W}\right\rceil.
\end{align}

Observe that $L\le\min{\{W/C_0,H/R_0\}}$ is sufficient, and $L\le L_0$ is necessary:

\begin{align}
\frac{WH}{L^2}&\ge\left\lfloor\frac WL\right\rfloor\left\lfloor\frac HL\right\rfloor=CR\ge N\\
L&\le\sqrt{\frac{WH}N}=L_0,
\end{align}

with equality only if $W/L_0$ and $H/L_0$ both are integers. As a result, the optimal solution has dimension either $C_0\times\lceil N/C_0\rceil$ or $\lceil N/R_0\rceil\times R_0$.


How to generate a pushdown automata for accepting a language?

Designing an PDA (or a NFA, DFA, or any other automaton) is essentially programming (in a weird, extremely limited language). Just as there is no sure-fire way to write a program from some description, there isn't for automata either. The only way of becomming proficient is to practice. You'll find plenty examples here...

For some cases there is a way of translating a more human-readable description of the language into an automaton, like starting with a regular expression and getting an NFA, massage that one and you'll finally get the minimal DFA; or starting with a context free grammar and constructing a PDA. The results aren't always exactly pretty, but guaranteed to work.


PDA that accepts if there is an "a" in the second half of the string

The PDA has three phases. In the first phase, it adds $A$ to the stack per character. It switches to the second phase nondeterministically. In the second phase, it removes $A$ per character. It switches to the third phase nondeterministically, during which it empties the stack. The PDA accepts if it encountered an $a$ during the second phase.


Certainly it is possible. For example, in the following study the Indian railway network was analyzed.

Small-world properties of the Indian railway network.
Parongama Sen, Subinay Dasgupta, Arnab Chatterjee, P. A. Sreeram, G. Mukherjee, and S. S. Manna. Phys. Rev. E 67, 036106 – 2003

In another study, the Chinese railway network was considered.

W. Li, X. Cai, Empirical analysis of a scale-free railway network in China. Physica A: Statistical Mechanics and its Applications, Volume 382, Issue 2, 2007, Pages 693-703.

The main problem is probably obtaining good data sets. However, train time tables are public, so in principle you could use data from any available time tables to reconstruct the network topology. If you also want the spatial embedding (the geographical coordinates), those might be more difficult to obtain.


Show complement of language in same complexity class?

Hint: Given a polynomial time algorithm for $L$, come up with a polynomial time algorithm for $\overline{L}$.


If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$?

Yes, the answer the the question is "false".

By contradiction, assume every problem in $NP$ has a $O(n^k)$ algorithm, for some fixed $k$. That is, $NP \subseteq {\sf DTIME}(O(n^k))$

This would contradict the time hierarchy theorem, which implies the strict inclusion

$$
{\sf DTIME}(O(n^k)) \subset
{\sf DTIME}(O(n^{2k}))
$$

However, we also have

$$
{\sf DTIME}(O(n^{2k})) \subseteq NP \subseteq
{\sf DTIME}(O(n^{k}))
$$

which contradicts the previous strict inclusion.


How to transform lambda function to multi-argument lambda function and how to rewrite or approximate terms?

You are looking for currying and uncurrying which transform functions of type $A \times B \to C$ to functions of type $A \to (B \to C)$, and vice versa. Currying takes IS to is, while uncurrying takes is to IS. This is a standard and very basic technique in $\lambda$-calculus. There are many manifestations of currying and uncurrying, for instance in arithmetic it is the identity $c^{a \cdot b} = (c ^ b) ^ a$.

It is largely a matter of taste how you write multi-argument functions. The uncurried form $A \to (B \to C$ has the advantage that you can apply the function only to the first argument. In your case is boss is a useful concept which is expressible very neatly. With the other function you have to write λ x . IS (boss, x).

Note however that sometimes people do not include product types $A \times B$ in their versions of $\lambda$-calculus, in which case of course currying is unavailable (but nothing much is lost).


Significance of including $S \to ε$ production rule in regular grammar?

This production rule allows the grammar to generate the empty string. We restrict it to the start symbol so that it can fulfill its function but not interfere with the properties of the grammar in any other way.

In short, it's a hack to allow regular grammars to generate the empty string.


The labels $c_v$ and $c_p$ are relative. So when a node (parent in your example) having $c_v = 1010010000$ receives from its parent (grandparent in your example) an id $c_p = 0010110000$, the difference, as you correctly point out, is in the fifth position.

Now, the total number of bits in the original ids is 10, so representing any index (0-9) will require 4 bits. So, the new id will have 4 bits from the position difference + 1 bit for the differing bit. Now,
$$(5)_{10} = (0101)_2$$

Note, we use 4 bits as discussed above, so that all new ids, can have the same number of bits. Then, $c_v(5) = 0$ is concatenated towards the LSB side, giving the new id: $01010$.


Weighting function for Non Uniform Learning

For every $n\in \mathbb{N}$, and $h\in H_n$, we can use $w(h)$ = $\frac{2^{−n}}{|H_n|} $.


Is it possible to prove $\mathsf{BPP = NP}$ statistically?

One way to interpret your statement is:

  Suppose that $\mathsf{L\in NP}$, and there exists a polynomial time deterministic algorithm $A$ such that for all $n$: $\Pr\limits_{x\sim U_n}\left[ A(x) = L(x)\right]\ge 0.99$, where $U_n$ is the uniform distribution over $\{0,1\}^n$, does this imply $\mathsf{L\in BPP}$?

As Yuval mentioned, the question (at heart) relates to the difference between randomized complexity and distributional (average case) complexity. Randomized complexity is the time required to correctly decide the membership of all inputs with high probability (where the probability is over the inner randomness of the algoirthm), whereas average case complexity is the time required for a deterministic algorithm to correctly decide "most" instances (relative to some distribution $\mathcal{D}$ over possible inputs).

This means that the question translates to whether the worst case hardness of an NP problem implies its average case hardness (the opposite direction is a result of Yao's principle, see this question for details). To the best of my knowledge, this is an open problem. There are many works on the subject, e.g.
On Worst-Case to Average-Case Reductions for NP Problems by Andrej Bogdanov and Luca Trevisan. The paper defines what it means for a language to have a worst to average case reduction, and shows that unless the polynomial hierarchy collapses, such reductions cannot exist for NP complete problems (the implication might still hold, but not through their form of reduction).


PDAs that are allowed to have more than one initial state (let's call them PDAIs) are computationally equivalent to conventional PDAs:

Trivially, every conventional PDA can be considered as a PDAI that happens to have one initial state.
Every PDAI can be converted to an equivalent PDA with the process you describe.

So yes, PDAIs accept exactly the context free languages.


Converting a NFA to its equivalent regular expression

Technically it can be reduced, by introducing a regular expression for the empty set, which represents the missing edge.

However, $q_4$ is completely useless for the language. They can be dropped without changing the accepted language. That should save some work.


Does no parents imply variable independence in a Bayesian network?

Yes, they would be unconditionally independent.

This is simply a consequence of the factorisation of a Bayesian network into conditional probabilities. For example, this network will factorise as $p(A,B,C)=p(C|A,B)p(A)p(B)$, implying that $p(A,B)=p(A)p(B)$, which is the very definition of unconditional independence for the parent-less nodes $A$ & $B$:

As for the factorisation $p(A,B,C)=p(C|A,B)p(A)p(B)$ that led us here, this is definitional for Bayesian networks. I recommend Section 3.3 of Barber for a fuller explanation.

On the other hand, they are conditionally dependent if conditioned on a collider. For example, nodes $x$ and $y$ are graphically conditionally dependent when conditioning on the collider $z$ in each of these 2 BNs:

Chapter 3 of the same source contains a fuller description of BNs and similar graphical networks, together with various possible tests for conditional independence.


Greedy algorithm for a variation of the $k$-center problem

As a hint, let me work out the case $k = 1$ for you. We are given that some set $C$ of size 1 satisfies $p(v) d(v,C) \leq r^*$ for all $v \in V$. Let $C = \{x\}$. Then $p(v) d(v,x) \leq r^*$ for all $v \in V$.

The given algorithm picks the point $c$ which maximizes $p(c)$, and then removes from $S$ all points in $A = \{ v \in V : p(v) d(v,c) \leq 2r^* \}$. We will show that $A = V$, and so the algorithm terminates after one step, outputting the set $C = \{c\}$. By construction, $p(v)d(v,c) \leq 2r^*$ for all $v \in V$, so this is a 2-approximation.

It remains to show that $A = V$, that is, that all vertices $v \in V$ satisfy $p(v) d(v,c) \leq 2r^*$. Indeed, since $p(v) d(v,x), p(c) d(c,x) \leq r^*$, the triangle inequality implies that
$$ p(v) d(v,c) \leq p(v) d(v,x) + p(v) d(c,x) \leq p(v) d(v,x) + p(c) d(c,x) \leq 2r^*, $$
using the obvious $p(v) \leq p(c)$.

All that remains is to generalize this proof for larger $k$.


It's back to the mechanism of cache. When the cpu wants a data in cache, try to read data from cache. If there is the data in cache, It will fetch data from cache. This time of reading data from cache (the different between the speed of cache memory and register!) will be denoted by Hit time.

If the wanted memory in the related instruction  does not exist in the cache memory, it should be read from RAM, hence, it takes more cpu clock to read the specified address and this time is calculated by the multiplication of the miss rate and the penalty of this miss in time of reading data from RAM which is denoted by miss penalty.


Clarifying what it means to be Strongly NP-Complete

Yes, that's correct.  You'll probably have to figure out the polynomial yourself.  The way to find the polynomial is to look at the reduction, and from that you should be able to deduce a polynomial.

In your case, I believe there is a reduction from 3D-MATCHING to 3PARTITION, so you would analyze that reduction to find the polynomial.  Given an instance of 3D-MATCHING, the reduction explicitly constructs an instance of 3PARTITION whose solution can be used to solve the 3D-MATCHING instance; so you'd analyze how large the parameter of 3PARTITION instance could possibly be, as a function of the size of the set, and that would tell you the polynomial $p$ you are looking for.


Searching for points near given point in a multidimensional space

If you don't want the exact nearest neighbour but would be satisfied with finding points that are not too far off, then you should take a look at Approximate nearest neighbour search.

Wikipedia suggests the following approaches:

Locality-sensitive hashing
Best bin first
Balanced box-decomposition tree

Depending on the distribution of your data, not all dimensions may be equally relevant (maybe all points are bunched together along some line or hyperplane) and you could also use dimensionality reduction techniques, the main one being PCA (or maybe autoencoders nowadays).

Of course you can combine both, and that is also what I would recommend you to do in most cases.

If you want the exact nearest neighbour, unfortunately research suggests that this is very hard in high dimensions (see curse of dimensionality), and with a 512 dimensional space "clever" methods can very well end up being worse in practice than simply searching through all points.


What can a quantum query to a function do?

the gate $f$ performs the transformation
$$\rvert x\rangle \rvert0\rangle \to \rvert x\rangle \rvert 0\oplus f(x)\rangle, $$

but $0$ is idempotent for $\oplus$ so you simply get $\rvert x\rangle \rvert f(x)\rangle$.
Now, by linearity, if you input a superposition instead of a basis states, you'll get a superposition of the "answers", e.g.,

$$\frac1{\sqrt2}(\rvert 0\rangle \rvert0\rangle+\rvert1\rangle |0\rangle) \to \frac1{\sqrt2}(\rvert 0\rangle \rvert f(0)\rangle+\rvert 1\rangle \rvert f(1)\rangle)$$

Then, if you start with a Hadamard, and get an equal superposition of all basis states, you end up with a superposition of all possible "answers".
$$\frac1{N} \sum_x \rvert x\rangle \rvert 0 \rangle \to \frac1{N} \sum_x \rvert x\rangle \rvert f(x) \rangle.$$

The fact that $x$ or $0$ are in fact a "string" over $\{0,1\}$ doesn't make any difference - treat them as a single quantum system of higher dimension (or treat each qubit as a separate function $f_i$ where $f_1()f_2()\cdots f_n()=f()$ are the bit-wise functions.


Algorithm for finding the minimum index in array with value exceeding x

Assuming the $s_i$ positive (which wasn't said in the OP), the prefix sum of $s_i$ forms a monotonic sequence.

You can start a simultaneous exponential search from both ends, followed by a standard binary search when the half sum has been crossed. The left exponential search takes $O(\log(j))$ and the right one $O(\log(k-j))$. As they are performed simultaneously, the fastest "wins".


Set that keeps unique categories of objects

There is no official operation that accomplishes what you want, but you can always define an operation $\cup_{\succ}$ which does so. Just define the operation in words.

If for some reason you want a "physical" implementation, then here is one way. Each set is a collection of pairs, i.e.
$$
\begin{align*}
S_1 &= \{ (apple,apple), (orange,orange), (pear,pear) \}, \\
S_2 &= \{ (apple,betterApple), (orange,orange), (banana,banana) \}.
\end{align*}
$$
Furthermore, there is some partial order $\prec$ such that $(x,y),(z,w)$ are comparable iff $x = z$. When you take the union $S_1 \cup S_2$, you get
$$
S_1 \cup S_2 = \{ (apple,apple), (apple,betterApple), (orange,orange), (pear,pear), (banana,banana) \}.
$$
Then you can define a function
$$
\phi(S) = \{ x \in S : \text{ no $y \in S$ satisfies $y \succ x$ } \}.
$$
What you want is $\phi(S_1 \cup S_2)$.


Implement Mathematica's capability of rationalizing machine reals

The continued fraction algorithm is easy enough to implement. The first step is to compute the continued fraction of the input $x = [c_0;c_1,\ldots]$. You start with $x_0 = x$, and use the recurrence $c_i = \lfloor x_i \rfloor$, $x_{i+1} = 1/(x_i - c_i)$. You stop when $x_i - c_i$ is "small enough". The next step is to compute the convergent of the continued fraction. You can find the appropriate formulas on the web. In practice, both steps are performed at the same time.

There are some issues with numerical stability, and that might make it difficult to match the performance of Mathematica, but for simple cases it works well enough.

The resulting rational number is not actually equivalent to the floating point number - there's probably some small error. In fact, the rational approximation may be more accurate in some cases, and off the mark in others. However, floating point numbers are secretly rational numbers - they are of the form $\pm 2^x M$, where $x$ is the integer exponent (positive, zero or negative) and $M$, the mantissa, is a rational number between $0$ and $1$ (or $0$ and $2$). In fact, it's always of the form $A/2^B$, where $B$ is the length of the mantissa and $A$ is some non-negative integer. If you really care for it, you could decode a real number into this representation, and thus obtain a truly equivalent rational number.


Is there a name/interest for regular languages that have a non-ambiguous ending?

According to your alternative definition, you're looking for a  language such that $u\in L\Rightarrow \forall v\neq\epsilon, uv\notin L$ (where $\epsilon$ denotes the empty string).

That property defines a useful kind of language in coding, called prefix-free codes. Note that this language class doesn't include nor is included in regular languages.

So what you're looking for is the intersection of those two classes. That would be a prefix-free regular language.

As for the interest, it seems to have some, since a google search returned this research paper.


When popping the root, it is first replaced by the very last element, and then a heapify operation is performed to maintain the heap invariant, namely, that every node is smaller than its children.

Since we are removing the very last leaf, the heap always remains balanced, in the sense that all levels but the last will be full, and the last level will consist of a prefix of the set of potential vertices.

The three steps are illustrated in the Wikipedia article. We start with a max-heap:

We remove the root, and replace it with the very last element:

Finally, we perform a heapify operation on the root:


Is there a known way to convert any $QBF_2$-formula into an equisatisfiable $QBF_2$-formula in CNF in polynomial time?

Yes, for exactly the reasons you listed.
I don't know of any way to do what you want.  However, it is possible to convert it to a formula of the form $\neg \forall x \exists y \Psi$ (negate it, then convert $\neg \Phi$ to CNF via the Tseitin transform and let $\Psi$ be the result), so if you have an oracle that will solve QBF2-CNF queries, it can be used to solve QBF2 queries.


Read and write ports in a register file?

A "register file" is an aggregation of registers. That is, it is one component that holds several different registers.

How many read/write ports?  Well, this depends. It can be 1 and 1, or more, according to the specific system. If you are the engineer, you can design a register file with as many read and write ports as you desire. The maximal number would probably be the number of registers in the file because there is no point in placing more read/write ports than actual registers (=memory cells).


Confused about substitution in grammar in certain cases

There's no particular reason why the first $T$ should be replaced by $empty$. The other replacement would have been equally acceptable. A grammar rule says "you can replace this string by this other" and no more. In other words, a grammar may generate several strings, depending on which of the grammar's replacement rules are called into play at any stage.

In answer to your last question, there are no rules to specify which substituition you use: the choice is up to you.


"Most Similar Vector Problem" on an Integer Lattice

I don't know of a good approach to this, or whether there's any literature on it.

However, if you're completely stuck, one possible approach is to use integer quadratic programming and binary search.

WLOG we can assume $\|u\|=1$ (otherwise replace $u$ with $u/\|u\|$).  Now the decision problem is, given $\alpha$, to determine whether there exists $w$ such that $u \cdot w / \|w\| \ge \alpha$, i.e., such that $(u \cdot w)^2 \ge \alpha^2 \|w\|^2$.  Define

$$\Phi(w) = \alpha \|w\|^2 - (u \cdot w)^2.$$

Note that $\Phi$ is a quadratic function in the unknowns $w_1,\dots,w_n$, and the decision problem can be solved by maximizing $\Phi(w)$ subject to the constraints $-M \le w_i \le M$.  The answer to the decision problem is yes iff there's a solution to this integer quadratic program where $\Phi(w) \ge 0$.  Now if you could solve the decision problem, you could use binary search on $\alpha$ to find the largest $\alpha$ for which a solution exists.

Unfortunately this requires integer quadratic programming, which might be very hard.  One heuristic approach might be to relax to semidefinite programming instance (with real numbers instead of integers), look for a solution (in the reals), round to the nearest integer point, and see if that gives you a valid solution.  This is not likely to give you an exact solution but it's possible it might give you some kind of approximation to the correct answer.  Unfortunately, I have no idea how good or bad an approximation it might be.