Greedily Schedule Events based on value/hours

I'm assuming that the value given to $h$ in each step is "number of hours during the running of the event, which are not yet covered". (Your wording is somewhat ambiguous.)

In  the following I'll assume that all events start and end at full hours. For real valued times, just replace hours by an amount of time small enough that all the differences between relevant moments (start and end times) are multiples of that amount.

From the constraints given, we see that the event visited at one point in time has no influence on the profit we can make at a different moment in time. Thus, the optimal solution will be to visit the most profitable event at each point in time, i.e. during each hour. Now, we only have to show that the algorithm achieves this:

Assume that there is an hour $h$ during which the algorithm suggests to visit event $e$, while visiting $e'$ would be more profitable. Since $e'$ is more profitable, it will have been put before $e$ during the first step of the algorithm. Furthermore, since $e'$ has been scheduled for $h$, $h$ must have been available when the algorithm processed $e$ and (since the algorithm never frees an hour) also when it processed $e'$. But this means that the algorithm would have scheduled $e'$ for hour $h$, contradicting our assumption. Thus we conclude that the algorithm is correct.


Explanation of recursive structure of Van Emde Boas Tree

Well the crucial idea about vEB trees is the following: You store all the elements as a 0/1 bitvector of size $s$. For example the vector $(0,1,1,0)$ denotes that in your universe of size $s=4$, the third and second elements are present. Now you subdivide the vectors in blocks of size $\sqrt{s}$ and for every block you also store a flag, if there is at least one $1$ in the block. This gives you a set of $\sqrt{s}$ flag bits. If you store also the $\min$ and $\max$ for every block, then you can determine in which block you have to continue your search for the successor after either perform a successor query in the block of your query element or in the flag bit vector.

This implies that the sup-problem you are requesting has size $\sqrt{s}$. But this is the same statement as saying that you go from a $k$-bit universe to a $k/2$-bit universe.

And this is meant by shrinking the universe.


Identifying Coffman conditions in a given situation with deadlock

Considering the definition of circularity you exposed, it is important to highlight that ownership is not implemented in semaphores (it is for mutexes). So, in a way, each task is waiting for each other because each one has the possibility to "release" (i.e. perform a post to the semaphore since it starts from $0$) the resource (only if the condition inside the "if" is not satisfied). Extending this approach, also the task itself has the possibility to post to the semaphore. Moreover, note that the deadlock is present when $N>2$.


Existence of polynomial time reduction from P to R?

The claim is correct, therefore, you need to give a proof that such a reduction exists. I see that you're trying to prove it by contradiction, so your question is a bit unclear. If you did not get to a contradiction by assuming the correctness of the claim, that does not mean that the claim is correct. Instead, you're assuming that it is correct.

By a similar reasoning to yours: as far as i see, if $P\neq NP$ then everything is ok :) Or if $P=NP$ then everything is okay. So maybe the claim is not correct but we don't have the tools to show that yet. Or maybe you can assume both!

Regarding the specific claim you mentioned, consider the following more general claim.

Claim: every non-trivial language $L_2 \notin \{\emptyset, \Sigma^*\}$ is $P$-hard. That is, if $L_2$ is non-trivial language and $L_1\in P$, then $L_1 \leq_p L_2$.

To begin with, note that the claim you wrote is a special case to the above claim. Indeed, we just drop down the assumptions that $L_2$ is in $R$ and $L_1$ is non-trivial.

Solution: let $L_2$ be a non-trivial language and let $L_1\in P$.  We describe a reduction from $L_1$ to $L_2$. To begin with, since $L_2$ is non-trivial, we have that there is a word $x_{in}\in L_2$ and a word $x_{out} \notin L_2$.

Defining the reduction: the reduction, denoted $f$, operates as follows. For the input word $w$, check whether $w$ is in $L_1$. If $w\in L_1$, the reduction outputs $x_{in}$. Otherwise, the reduction outputs $x_{out}$.
Correctness: follows immediately from the fact that $w\in L_1$ iff $f(w) = x_{in} \in L_2$.
Runtime: note that the reduction runs in polynomial time in $|w|$ (the input's length). Indeed, since $L_1\in P$, we have that there is a deterministic TM that decides $L_1$ in polynomial time and thus one can decide whether $w\in L_1$ in polynomial time in $|w|$. $x_{in}$ and $x_{out}$ are constants (they do not depend on the input $w$), hence they do not affect the runtime of the reduction (you can think about them as words hardcoded in the reduction itself).

Note: a machine that decides $L_1$ in polynomial time exists, $x_{in}$ and $x_{out}$ exist and thus the reduction exists.


Bounds on update time in the RMQ problem subject to $O(1)$ query time?

You can divide the whole range into $n^{\frac{1}{3}}$ blocks, and for each block apply your $O\left(\sqrt{n}\right)$ approach. Then you can get $O\left(\sqrt{n^{\frac{2}{3}}}+n^{\frac{1}{3}}\right)=O\left(n^{\frac{1}{3}}\right)$ update time with constant query time.

Recursively, you can get $O\left(n^\epsilon\right)$ update time with constant query time for any constant $\epsilon>0$.


Why is factoring large integers considered difficult?

You are confusing the number $n$ with the number of bits needed to represent $n$.  Here $b = $ the number of bits needed to represent $n$ (so $b \approx \lg n$).  This makes a huge difference.  A $O(n)$-time algorithm is a $O(2^b)$-time algorithm -- exponential in the number of bits.  In comparison, the "efficient" algorithm you found has a running time that is subexponential in $b$.

Example: Consider $n = 2,000,000$ (2 million).  Then $b=21$ bits are enough to represent the number $n$.  So, an algorithm that is $O(2^{b^{1/3}})$ will be much faster than an algorithm that is $O(2^b)$.  An $O(n)$ algorithm falls into the latter category, i.e., very slow.

See https://en.wikipedia.org/wiki/Integer_factorization


It will be less confusing to reparametrize $T$ by switching the order in which the second parameter increases:
$$
T(n,k) =
\begin{cases}
1 & \text{if } n \leq C \text{ or } k = 0, \\
T(n-1,k) + T(n-m,k-1) & \text{otherwise}.
\end{cases}
$$
Having done this switch, let us get rid of $C$ completely. Including $C$ as the third parameter, notice that $T(n+C,k,C) = T(n+D,k,D)$, and so it suffices to solve the recurrence for some value of $C$. We choose $C = 1$.
Let us now unroll the recurrence. Suppose that $n > m$ and $k > 0$. Then
\begin{align}
T(n,k) &= T(n-m,k-1) + T(n-1,k) \\ &=
T(n-m,k-1) + T(n-m-1,k-1) + T(n-2,k) \\ &=
T(n-m,k-1) + \cdots + T(2-m,k-1) + T(1,k) \\ &=
T(n-m,k-1) + \cdots + T(2-m,k-1) + 1 \\ &=
T(n-m,k-1) + \cdots + T(2,k-1) + m + 1.
\end{align}
This gives us $T(n,1) = n-m-1+m+1 = n$ if $n > m$; you can check that the same formula works for all $n \geq 1$. Continuing,
$$
T(n,2) = T(n-m,1) + \cdots + T(2,1) + m + 1.
$$
If $n > m$ then we can compute exactly
$$
T(n,2) = (n-m) + \cdots + (2) + m + 1 = \frac{(n-m)(n-m+1)}{2} + m.
$$
When $1 \leq n \leq m$, you can check that $T(n,2) = n$.
At this point we can in principle continue and obtain exact formulas. However, they will be quite messy. Fortunately, when $m$ is constant, it is easy to prove by induction that $T(n,k) = \Theta(n^k)$; indeed, $T(n,k) = n^k/k! + O(n^{k-1})$. Obtaining an explicit dependence on $m$ is certainly possible, but unless it's expressly needed, I wouldn't bother.


Running-time cost of Tweaked Nested Loop


Hardness of approximation: what decision problem is hard exactly?

Most likely what is meant is the following statement:

If $P \ne NP$, then there is no polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor.

Or, equivalently: the existence of a polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor implies that $P=NP$.

Your proposed formulation at the end of your question might look tempting, but if you want to understand how to formalize the claim, I probably wouldn't suggest formalizing it that way -- that formulation introduces unfamiliar technical issues of its own.  The problem you listed is a promise problem (it's not a decision problem).  Promise problems are weird and some of your intuition that you've built up won't work quite right for promise problems.   Promise problems are weird and counter-intuitive; if you want to build your intuition, often it's best to simply avoid them, rather than try to absorb the messy details involved in formalizing them.


On the language of Turing machines not accepting their own encoding

In general, this problem is undecidable: that is, there is no general algorithmic solution.

Yuval gives a good answer for the specific question. Here are some general tips for showing the subset relation, that is, that $L_1 \subseteq L_2$:

Induction on word length. Show that the smallest string in $L_1$ is in $L_2$ and that having one string. This is most effective when there's some sort of inductive structure to the languages you are looking at.
Paths to accepting states. Look at how a word is actually accepted by your first machine, the states it travels through and what your tape looks like. For each step, show that you can do an equivalent step in the second machine which won't fail. The hard part is doing this abstractly enough so that it works for all words. This will usually break into a massive proof-by-cases.
Forget about Turing Machines. Look at the machines, find out what languages they accept as sets, and perform pure logic on those sets. This isn't very useful if you are given a random TM, but is handy if you know what one TM figures out. For example, if you realize that $L_1$ is the set of all primes larger than 10, and $L_2$ is the set of all odd positive integers, then it's pretty easy to show that $L_1 \subseteq L_2$


Formulating a constraint to exclude a single point from the feasible region of an IP?

You need to add an integer cut of the form:
$$
 \sum_i |x_i - y_i| \ge 1
$$
where $y_i$ is your point your want to exclude.

We can rewrite this as:
$$
  \begin{align}
     &\sum_i z_i \ge 1 \\
      &z_i \le |x_i - y_i|
  \end{align}
$$
The last inequality is identical to $z_i \le \max\{x_i-y_i, -(x_i-y_i)\}$. This again can be implemented using additional binary variables:
$$
 \begin{align}
    &z_i\le x_i-y_i+M_i\delta_i \\
    &z_i\le -(x_i-y_i)+M_i(1-\delta_i) \\
    &\delta_i \in \{0,1\} \\
    &M_i = U_i - L_i = 200
 \end{align}
$$
There are two special cases we can handle more efficiently. If $y_i=L_i=-100$ then we can write $z_i = x_i - y_i$. If $y_i=U_i=100$ then we can write $z_i=-(x_i-y_i)$.


Find The "Best" Permutation of Inputs to Maximize Sum of Functions (or approximate "best")

One approach is to view this as an instance of the assignment problem: you have a bipartite graph, with items on the left and positions on the right, and $f_i(p)$ tells you the value of matching item $i$ to position $p$, so draw an edge $i \to p$ with weight $f_i(p)$, and then find the maximum-weight bipartite matching.  This will give an optimal solution.  It also demonstrates that the problem can be solved in polynomial time, i.e., it is not NP-hard.  The running time will be $O(n^3)$, which might be reasonable if $n$ is not too large but might be too expensive if $n$ is very large.
It might be possible to find some other algorithm that is more efficient (i.e., has faster runtime), by taking advantage of the fact that each $f_i$ is monotonically decreasing.


Let $S(n) = T(4n-2)$. Then
$$
S(n) = T(4n-2) = 4T\left(\frac{4n-4}{2}\right) + \Theta(n^2) = 4T(2n-2) + \Theta(n^2) = 4S(n/2) + \Theta(n^2).
$$
The master theorem tells us that $S(n) = \Theta(n^2\log n)$, and so $T(n) = \Theta(n^2\log n)$.

More generally, the statement of the Akra–Bazzi theorem (specifically, the $h_i$ functions) makes it clear that the small perturbation in this recurrence ($\frac{n-2}{2}$ instead of $\frac{n}{2}$) doesn't change the asymptotics of the solution. From this theorem you can derive the solution directly without guessing the substitution $S(n) = T(4n-2)$.


How do the bits of a certain emoji code for all the colors?

That binary number does not contain the information about the pixels in the image which is used to show the emoji. It is only a number which, according to the Unicode standard, refers to that emoji. Every program which shows text (e.g. email reader, web browser, ...) must have a way to convert that number into the actual pixels. Usually, in modern computers, there is a font file, which contains all the information about the pixels of each character. So, when the program has to display the emoji, it accesses the file and reads the pixel data corresponding to the emoji, and sends those pixels to the screen.

Note that the Unicode standard does not specify what these pixels are, but only that they should represent, say, a "cake emoji". Every program might use a different font, showing the cake in a different way.

This also happens for regular characters. Unicode says that "A" is represented by number 65, but there are many fonts that can be used to show that "A".


Among a number of sets, how to find the one that includes the highest number of other sets?

From the answer linked in D.W.'s comments, you wont be able to do this in less than quadratic time without more information.  The problem you are trying to solve is more difficult than the Subset Containment problem, which is quadratic with the number of sets.  We can, however, explore ways to make the average case better.

The first step is to identify if there is any pattern to the data which can be leveraged.  For example, if the sets are random, then you can leverage that to find better runtimes with some partitioning tricks.  If the values all happen to be less than 64, you could encode each set as a 64-bit numbers and do comparisons that way.

The most generic approach, however, is to try to minimize comparison time.  The first step would be to sort the elements in each set.  That makes it so you can always determine if one set is a subset of the other in linear time by scanning it.

Beyond that, you could look at bloom filters.  A bloom filter is basically an array of bits, and each bit corresponds to the result of hashing the data differently.  What is nice about bloom filters is that they allow you to combine values using OR logic.  Use a bloom filter to hash each of the elements in a set, and OR the results together.  Now it is easy to see that if you have a set $S_1$ and $S_2$ such that $S_1\subseteq S_2$ and you have their corresponding bloom filter arrays $B_1$ and $B_2$, then every bit in $B_1$ must also be set in $B_2$ (i.e. $B_2\land B_1=B_1$).

Thus, you will have to do $O(n^2)$ comparisons of the bloom filter arrays (which are bit-fields, so you can process them 32 or 64 bits at a time natively).  If $B_i\land B_j=B_j$ for any $i, j$, then you have a potential subset.  It's possible that you just had a bloom filter collision, so we have to test the arrays, which is linear with the size of each array.

Thus in the worst case, we don't save any time, but in the average case, we may be able to dramatically reduce the cost of comparing the sets.

There's a few more steps involved to make sure we don't saturate the bloom filters, but those can only be worked out when you know a little about the sizes of your sets, which I do not.


Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator

Actually, generating a pseudorandom integer is very fast, so the simple approach will likely be quite efficient.  As always, beware premature optimization.  Benchmark it first before assuming it'll be too slow.

If you have a power-of-two denominator, it's easy to come up with a procedure that doesn't require as many random bits -- but in practice this doesn't matter, because with most PRNGs, it's just as fast to generate an entire word as to generate a few pseudorandom bits.


Complexity as it relates to verifiers of languages

It is an open question whether $P=NL$, where $NL$ is the class of languages verifiable in logarithmic space. It is known that $NL \subseteq P$ (why?), and strongly suspected that $NL \neq P$, but we don't know for sure.


How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $

We can compute
$$ f(\theta) = -N\log (2\pi)-\frac{1}{2}\sum_{i=1}^N (\langle x_i,\theta \rangle -y_i)^2. $$
Expanding this out, we get that $f(\theta)$ is some quadratic form:
$$ f(\theta) = \theta' A \theta + v'\theta + C, $$
where $A$ is symmetric.
The next step is to get rid of the linear term. Let $\theta = \psi + \epsilon$. Then
$$ \theta' A \theta + \langle v,\theta \rangle + C =
\psi' A \psi + (2\epsilon' A + v') \psi + (\epsilon' A \epsilon + v'\epsilon + C).
$$
So choosing $\epsilon' = -v' A^{-1}/2$ (assuming $A$ is invertible), we get
$$ f(\psi + \epsilon) = \psi' A \psi + C'. $$
The theory of quadratic forms tells us that if $A$ is invertible then we can write $A = P'DP$, where $D$ is a diagonal matrix with $\pm 1$ on the diagonal and $P$ is invertible. If $\psi = P \chi$ then
$$ f(P^{-1} \chi + \epsilon) = \chi' D \chi + C' = \sum_{i=1}^k \delta_i \chi_i^2 + C', $$
where $\delta_i \in \{\pm 1\}$. Suppose for example that the first $k_+$ are $+1$ and the rest $k_- = k - k_+$ are $-1$, and write $\chi = [\chi_+\;\chi_-]$. Then
$$ f(P^{-1} \chi + \epsilon) = \|\chi_+\|^2 - \|\chi_-\|^2 + C'. $$
If $k_+ = 0$ or $k_- = 0$ then the level sets are spheres or cospheres, up to an affine transformation of course. Otherwise it gets more complicated.

In your case, however, it is clear from the function $f$ itself then the quadratic form $A$ is negative semidefinite, probably in fact negative definite. In other words, $k_+ = 0$. So the sets you're after are affine transformations of cospheres. In other words, they are "outsides" of ellipsoids.

The only non-trivial step is finding the matrix $P$. Since your matrix is negative definite, you can use Cholesky decomposition.


Please note that the input to a nested word automaton is nested words instead of the usual words.

A nested word $n$ over $\Sigma$ is a pair $(a_1\cdots a_l; \leadsto)$, where $a_i\in\Sigma$ and $\leadsto$ is a matching relation of length $l$. Note that if there is no pending call nor pending returns (in which case $\leadsto$ is said to be well-matched), then the number of the calls and the number of returns are equal by the definition of a matching relation. This is the case when you use $\{ \langle  c, r\rangle\}$ as the alphabet of $L$ to represent the nested words.

What the nested word automaton in the question does mostly is, indeed, to check that all $\langle c$'s happens before $r\rangle$'s.

You are encouraged to read the seminal paper Adding Nesting Structure to Words by Rajeev Alur and P. Madhusudan. You might be delighted to find it is pretty easy to read, especially the relevant section 3.1.


Ellul, Krawetz, Shallit and Wang construct in their paper Regular Expressions: New Results and Open Problems a regular expression of length $n$ (for infinitely many $n$) such that the shortest string missing from its language has length $2^{\Omega(n)}$. Since a regular expression of  length $n$ can be converted to an NFA having $O(n)$ states, this gives, for infinitely many $n$, an NFA having $n$ states such that the shortest string not accepted by the NFA has length $2^{\Omega(n)}$.

Conversely, if an NFA having $n$ states doesn't accept all strings, then it must reject some string of length shorter than $2^n$. This follows from the pumping lemma once you convert the NFA to a DFA. Hence the construction in the paper mentioned above is optimal up to the constant in the exponent.


It is possible to determine whether a boolean expression is satisfiable, the question is how quickly it can be done.

If there are $n$ variables, then we can try all $2^{n}$ possible truth assignments, and eventually we'll find if there is a satisfying one, but this is not polynomial time with respect to the size of the input.

There might be some polynomial time algorithm that does solve SAT, we don't know, however SAT is NP-complete, which gives strong evidence that there isn't a polynomial time algorithm. It all comes down to whether P=NP or not.


Validate that a threaded binary tree works as intended

Shortly - no, it is not safe.
Huge random test does not guarantee success (but of course, when there is a bug, it finds it in the most cases).
To test threaded tree with deletion and insertion you need to have saturated all nodes (with thread links), make them change thread, the same for deletion.
To make sure it works all corner cases must be covered both for insertion and deletion. With huge input there is huge probability it works, but this is not conclusive. Also making more passes (more test) it increases probability of success, but nothing more.

To test it manually - case by case - you do not need very big tree (I did tests on double threaded AVL, tree height was maximally 5).


How can instruction fetch and decode pipeline stages run simultaneously in a CPU with dynamic branch prediction?

As an instruction must be decoded before branch prediction can occur or be deemed unneeded,

That can be avoided. The fetch stage can do prediction based purely on the current PC, without looking at the instruction. Branch Target Prediction also enters the picture here, otherwise without decoding the branch target would be unavailable. Accidentally applying branch prediction to an instruction that turns out not to be a branch is not a disaster, just something to detect and signal a misprediction if necessary.

So this can be done with no bubble.

As an example, here is a diagram of the pipeline of the RISC-V BOOM processor (source), showing PC going to next-line predictor and the I\$ in parallel

  any prediction must be made before the next instruction can be fetched

Why stop? Just keep predicting, it doesn't matter that the next instruction(s) have been fetched, flush them out if one of the later predictions "changes its mind". This gives you a lot of time to run slow but high quality predictors after the fast predictors. You could even do away with the fast predictors, but then there really would be a bubble for every "taken" prediction - an unconditional stall is overkill though, there's no reason to not at least fetch the next address (effectively predicting "not-taken").

As a practical example, AMD Bobcat takes several shots at branch prediction, some in parallel with decoding (Fetch3 through Fetch5):

In the BOOM diagram there are also several forms of branch prediction, but the Backing Predictor (the more complex predictor with higher accuracy) there is before decode rather than parallel with it.


What classes of data structures can be made persistent?

Positive result: persistence does not cost too much. One can show that every data structure can be made fully persistent with at most a $O(\lg n)$ slowdown.

Proof: You can take an array and make it persistent using standard data structures (e.g., a balanced binary tree; see the end of this answer for a bit more detail).  This incurs a $O(\lg n)$ slowdown: each array access takes $O(\lg n)$ time with the persistent data structure, instead of $O(1)$ time for the non-persistent array.  Now take any imperative algorithm whose running time in the RAM model is $O(f(n))$, where $n$ denotes the amount of memory used.  Represent all of memory as one big array (with $n$ elements), and make it persistent using a persistent map.  Each step of the imperative algorithm incurs at most a $O(\lg n)$ slowdown, so the total running time is $O(f(n) \lg n)$.

Apparently it is possible to do a bit better: apparently one can reduce the slowdown factor to $O(\lg \lg n)$ (expected, amortized time), using the techniques in the Demaine paper cited below -- but I am not familiar with the details of that work, so I cannot vouch for this myself.  Thanks to jbapple for this observation.

Negative result: you cannot avoid some slowdown, for some data structures. To answer your third question, there exist data structures where it is known that making them persistence introduces some slowdown.

In particular, consider an array of $n$ elements.  Without persistence, each array access takes $O(1)$ time (in the RAM model).  With persistence, it has apparently been shown that there is no way to build a persistent array with $O(1)$ worst-case complexity for accessing a random element.  In particular, there is apparently a lower bound showing that fully persistent arrays must have $\Omega(\lg \lg n)$ access time.  This lower bound is asserted on p.3 of the following paper:

Confluently Persistent Tries for Efficient Version Control.  Erik D. Demaine, Stefan Langerman, Eric Price.  Algorithmica, volume 57, number 3, 2010, pages 462–483.

The lower bound is attributed to Mihai Patrascu, but there is no citation to a source that gives the details of the proof of this asserted lower bound.

A rich area of research.  If we take an arbitrary data structure or algorithm, it's a bit of a delicate question whether you can make it persistent with at most $O(1)$ slowdown or not.  I don't know of any general classification theorem.  However, there is a lot of research into ways to make specific data structures persistent, in an efficient way.

There is also a strong connection with functional programming languages.  In particular, every data structure that can be implemented in a purely functional way (with no mutations) is already a persistent data structure.  (The converse is not necessarily the case, alas.)  If you want to squint your eyes, you could take this as some weak sort of partial classification theorem: if it is implementable in a purely functional programming language with the same time bounds as in an imperative language, then there is a persistent data structure with the same time bounds as the non-persistent one.  I realize this probably isn't what you were looking for -- it is mostly just a trivial re-phrasing of the situation.

How to make a persistent array. I won't try to describe the construction for how to build a fully persistent array with $O(\lg n)$ worst-case access time.  However, the basic ideas are not too complicated, so I'll summarize the essence of the ideas.

The basic idea is that we can take any binary tree data structure, and make it persistent using a technique called path copying.  Let's say we have a binary tree, and we want to modify the value in some leaf $\ell$.  However, for persistence, we don't dare modify the value in that leaf in place.  Instead, we make a copy of that leaf, and modify the value in the copy.  Then, we make a copy of its parent, and change the appropriate child pointer in the copy to point to the new leaf.  Continue in this way, cloning each node on the path from the root to the leaf.  If we want to modify a leaf at depth $d$, this requires copying $d$ nodes.

If we have a balanced binary tree has $n$ nodes, then all leaves have depth $O(\lg n)$, so this operation on the binary tree takes $O(\lg n)$ time.  There are some details I'm skipping -- to achieve $O(\lg n)$ worst-case time, we may need to rebalance the tree to ensure it remains balanced -- but this gives the gist of it.

You can find more explanations, with pretty pictures, at the following resources:

Read the sections labelled "Binary search trees" and "Random-access structures" (specifically, the tree method) at http://toves.org/books/persist/index.html.
Or, read http://netcode.ru/dotnet/?artID=6592#BinaryTrees and some of the subsequent sections.
Or, read the sections labelled "Functional data structures" and "Path copying" (starting on p.4) of the Demaine paper cited above: http://erikdemaine.org/papers/ConfluentTries_Algorithmica/paper.pdf

That will give you the main idea.  There are extra details to take care of, but the details are out of scope for this question.  Fortunately, this is all standard stuff, and there is lots of information available in the literature on how to build such data structures.  Feel free to ask a separate question if the above resources aren't enough and you want more information about the details of building a persistent array data structure.


The Latin-1 supplement was taken unaltered from the upper half of an existing standard, ISO 8859-1, which in turn was based on a standard published by the European Computer Manufacturers Association (ECMA) in the early 1980s as ECMA-94.
ECMA-94 was based on an actual hardware encoding, developed by Digital Equipment Corporation (DEC) for its popular VT-220 video display terminal, presumably on the basis of what they perceived as customer demand. But the various national standards associations negotiated some adjustments which, as is often the case, were hammered out in interminable meetings attended by well-meaning people with a lot if enthusiasm but without much expertise in designing character sets.
In the end, ISO 8859 was extended to a series of 8-bit encodings, ISO 8859-1 through ISO 8859-15, providing support for national languages which had not been well-served by the original encoding.
By then it was obvious that 256 codes were not enough for all the alphabets in use at the time, but there was still some reluctance to switch to a wider encoding for languages which could be shoe-horned into eight bits. Many manufacturers were quite prepared to sacrifice the possibility of representing multilingual documents (unless, of course, one of the languages was English), and the relatively simple Unicode proposal was countered within the ISO by a byzantine collection of unworkable multibyte shift encodings. Fortunately Unicode did eventually prevail, but the provisions for context-dependent shift encodings continue to complicate multilingual APIs.
For another view of this history and some interesting links, you can check out the Wikipedia entry on ISO 8859-1.


How does one formulate a backtracking algorithm

This answer begins with a first section explaining the problem in more
general terms. The direct answer to the question for the example given
by the OP is then given in a second section that illustrate the
discussion in the first.

You may well want to skip the first section and go direcly to the
second one, depending on whether you like to start with basic
principles or with the analysis of an example.

The principles : non-deterministic programming

My description is not intended for this algorithm only, but is more a
general way to design such algorithms.

The key idea is that backtracking is a technique to implement
non-determinism with depth-first exploration of the non-deterministic
space of possibilities.

Non-determinism allows you to separate the logic of the problem from
the non-deterministic exploration of the solution space. It makes
programs clearer, simplifies analysis and proofs of properties. This is
pretty much the same advantage that you get when using non-determinism
in Automata Theory, to simplify the design of automata performing a
given calculation. Non-determinism makes your technical life much easier.

This advantage is such that various programming experts and language
designers have analyzed or experimented with the introduction of a
standard non-deterministic functionality in various programming
languages, not to mention the language Prolog where non-determinism is
a central control feature.

Another advantage of using non-determinism is that it leave open the
implementation technique, that can also use breadth first exploration,
or even dynamic programming (to avoid repeating calculations). And the
handling of non-determinism, such as adding the backtrack control, is
done entirely by the compiler.

An interesting side-point is that BNF, the language of context-free
grammars, can be seen as a simple non-deterministic programming
language to write parsers. And you can compile it fairly simply into a
depth-first parser (some early ones were just that - Ned Irons, 1961),
or a breadth-first one, or a dynamic-programming one (CYK, Earley, and
some others).

However, backtracking requires mastering the state of the environment.
Without going into details, it is much easier to implement it in a
purely functional programming language that has no side-effects
(for example, no assignment to global variables), at least not in the
parts of programs that use non-determinism.

This is not in contradiction with the use of the global variable A
below, which is never read, except to collect the answers.

But it explains why I insist on starting with a recursive
non-deterministic program, rather than with an equivalent iterative
variant.

What is described below could well be done automatically by the
compiler of a non-deterministic language.

Description of the design for the given example

Here is how I would explain the design of this algorithm.

You consider an array A of bits where the permutation is stored before
printing. It can be a global variable.

First you write a non-deterministic algorithm, that will just produce
one permutation, a "random" one, chosen by the god of non-determinism
:)

This is a simple recursive procedure that ask the god's oracle
choose for each bit in succession. The choose oracle return
non-deterministically one of its arguments (here the word oracle is
used in its mythological sense, not in the usual sense of
computability theory). Using recursion is important, as I shall explain later.

void binary(int n)
{
    if(n < 0)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1]= choose('0','1')
        binary(n-1);
    }
}

You should agree that this algorithm will return one of the
permutation, anyone of them. You could organize the recursion differently, it does not really matter. All that matters is that you may follow any of the possible computations.

What you have done with this program is to prepare for all choices
that will make a permutation.

Then, instead  of making one choice non deterministically, you simply
try them all, one after the other, for each of the calls.

Since you have a list of the possible choices (there can be a variable
number of them), you just try them in succession. You can do that by
having a segment of code for each possible value. But when the
possible values are in a list of variable length, you can just loop
over that list.

Here you have just  2 values, so you just write twice the same code,
once for each of the values, so that:

        A[n-1]= choose('0','1')
        binary(n-1);

becomes

        A[n-1]= '0'
        binary(n-1);
        A[n-1]= '1'
        binary(n-1);

The first call to binary will produce all permutations with '0' in
position n and the second all permutations with '1'.

Instead of choising arbitrarily, you do one, then the other.

There is an invisible trick that helps you. This would be somewhat
harder if you had used an iteration rather than a recursion.

The reason is that, for each former call to choose, you have to
come back to it after trying all possibilities of later choices, and
you have to remember what are the choices you have not tried yet.

This is very easily handled by returns of the recursive call, where
you find the environment and the execution point where you left it, so
that you simply go on.

If you had used an iteration, you would have a beautiful mess managing
the data to recall how far you have dealt with each non-deterministic
choice.

You could have started with a very simple loop, that is also a
non-deterministic way of computing a single permutation.

void binary(int n)
{
    for (i=n-1; i=0; i--) {
        A[i]= choose('0','1')
    }
    printf("%s\n",A);
}

But transforming this program into a deterministic backtracking
program would be a lot harder.

Isolating each non-deterministic choice in a function makes your life
easy.

There is an old classical paper that talks of non-deterministic
algorithms, though I have not looked at it in a very long time, and I
have no memory of how it handles the problem. People were not using
recursion as much in those times. You may want to look at it. Bob
Floyd was one of the pioneers of computer science.

Non-deterministic algorithms, Robert W. Floyd, 1966.

I do not recall where it was published, but it is easy enough to find.

Note: The previous version of the answer was assuming arrays are indexed from 1 to n.  I changed that as it may put off users who recognize the code as C code. The site is normally language agnostic. The program given in the question is missing both A[0] and A[n].


Example algorithms for first class in programming for EE students

My favorite example of the value of efficiency is Fibonacci number computation.
A naive programmer could use the recursive top-down solution, which takes exponential time. A bottom-up iterative solution, on the other hand, runs in linear time.


Name of binary encoding scheme for integer numbers

The technique idea is perfectly described in Yuval Filmus answer. Even if slightly different, it is called Truncated binary encoding in Wikipedia. I couldn't find an original source for that, apart from a mention in a patent, in this book, or in this Google API
Another mention can be found in the ACM ICPC 2011–2012, Northeastern European Regional Contest, November 27, 2011.


How to verify that a heuristic is consistent?

Another option rather then verifying it for each couple node-child is to use some problem specific properties and prove it this way.

Iff it is known that the triangle inequality stands for the distance between the nodes in the specific problem, then the heuristic is consistent. The triangle inequality is part of definition of a metric. So if the distance in the problem space is some well known metric you can state that the heuristic is consistent. Example for that is the distance metric in the Euclidean geometry.


Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication?

It looks like the article was written by someone who does not understand matrix multiplication.

the number of additions is equal to the number of entries in the matrix, so four for the two-by-two matrices and 16 for the four-by-four matrices.

With the classic matrix multiplication algorithm (which is the one explained in the example) between two $4\times 4$ matrices, each coefficient of the product requires $3$ additions, so a total of $3\times 16 = 48$ additions, not $16$.
Usually, when it is said that only multiplications matter and not additions, it means of matrices, not coefficients.
For example, a "naive" divide-and-conquer strategy compute $A\times B$ where $A,B$ are matrices of size $n\times n$ by doing $8$ products of matrices of size $\frac{n}{2}\times\frac{n}{2}$ (and some additions of matrices, but those are done in complexity $O(n^2)$, which is negligible in front of the complexity of matrix multiplication). That way, the complexity verifies $C(n) = 8C\left(\frac{n}{2}\right) + O(n^2)$ and it is easily proven that $C(n) = O(n^3)$, so this strategy is not an improvement.
The Strassen algorithm use a divide-and-conquer strategy to improve complexity: it does $7$ products of matrices of size $\frac{n}{2}\times\frac{n}{2}$ and some additions, so the complexity verifies $C(n) = 7C\left(\frac{n}{2}\right) + O(n^2)$ and we get $C(n)\simeq O(n^{2.8})$.
In the two examples above, the number of matrices multiplications matter much more than the number of matrices additions. But in both, the number of multiplications/additions on coefficients is not compared.
It is confirmed in the article:

Volker Strassen reportedly set out to prove that there was no way to multiply two-by-two matrices using fewer than eight multiplications. Apparently he couldn’t find the proof, and after a while he realized why: There’s actually a way to do it with seven!


Showing that carbon is not a complexity measure per Blum

Papadimitriou is being extremely sloppy here. Let us consider part (b) first. What does Papadimitriou mean by "ink"? Suppose that he really means what he wrote: the number of times during computation that a symbol is overwritten by a different symbol. Consider a Turing machine which repeatedly goes right one step, then left one step, in an infinite loop. Then ink is 0, but the machine never halts, and so Axiom 1 seems to be violated. We conclude therefore that ink (and carbon) should be undefined if the machine doesn't halt.
The more challenging bit is proving Axiom 2. Given $M$, $x$, and $k$, we need to decide whether (1) $M$ halts on $x$ and (2) during this halting computation, a symbol is overwritten with a new symbol exactly $k$ times. It might seem at first that this shouldn't be decidable, since we are in some sense trying to solve the halting problem. However, we are given the crucial advice $k$. Let us see how it helps us. We simulate $M$ on $x$ until it either halts (in which case we declare No) or we have reached ink $k$. In the latter case, it remains to check whether $M$ halts on $x$, given the additional promise that the tape doesn't change any more.
The additional promise allows us to continue the simulation until one of the following happens: (1) carbon increases, (2) computation halts, (3) a configuration repeats, (4) we have determined that the machine is off on a tangent on one of the infinite ends of the tape. I leave further details to you.
A similar trick doesn't work for part (d). Indeed, we can arrange for a Turing machine to never overwrite a tape symbol with itself. The idea is that for each original tape symbol we will have two new ones, treated in exactly the same way, that are alternated if needed to insure that carbon is zero. It follows that the halting problem can be reduced to the problem of deciding whether carbon is zero or not.


I guess the proof is fine except for the fact that you have used same costant in two different eqns. Even if you use(and you must use, because the constant you choose is arbitrary) two different conts say c1 and c2, the solution will imply the same.


What can't be done with a neural network

This paper introduces a finite size neural network and proves that it can simulate a Turing Machine, meaning that this NN is Turing complete. Thus anything that may be computed using TMs can be computed by this type of NNs. You may want to read this too.


DFA that recognizes 0 in every odd position

Yes, since $|\epsilon| = 0$, there are no odd positions; therefore, that DFA would accept $\epsilon$.


How to make smart contracts work in a small network?

One approach is to use a system like Ethereum, Truebit, or their successors.  In Ethereum, every node checks that the smart contract was executed correctly.  In Truebit, there is a sophisticated way to assign the contract to untrusted nodes and check that they executed it correctly.

Another approach is to use trusted hardware, like SGX.

There are probably other options as well.

I suggest reading up on those systems.  There's lots written on them.


Your code has the property that if you reverse all codewords, then you get a prefix code. This implies that your code is uniquely decodable.

Indeed, consider any code $C = x_1,\ldots,x_n$ whose reverse $C^R := x_1^R,\ldots,x_n^R$ is uniquely decodable. I claim that $C$ is also uniquely decodable. This is because
$$
 w = x_{i_1} \ldots x_{i_m} \text{ if and only if } w^R = x_{i_m}^R \ldots x_{i_1}^R.
$$
In words, decompositions of $w$ into codewords of $C$ are in one-to-one correspondence with decompositions of $w^R$ into codewords of $C^R$. Since the latter are unique, so are the former.

Since prefix codes are uniquely decodable, it follows that the reverse of a prefix code is also uniquely decodable. This is the case in your example.

The McMillan inequality states that if $C$ is uniquely decodable then
$$
\sum_{i=1}^n 2^{-|x_i|} \leq 1.
$$
In other words, a uniquely decodable code satisfies Kraft's inequality. Therefore if all you're interested in is minimizing the expected codeword length, there is no reason to look beyond prefix codes.

Sam Roweis gives in his slides a nice example of a uniquely decodable code which is neither a prefix code nor the reverse of a prefix code:
$$
0,01,110.
$$
In order to show that this code is uniquely decodable, it suffices to show how to decode the first codeword of a word. If the word starts with a $1$, then the first codeword is $110$. If it is of the form $01^*$, then it must be either $0$ or $01$. Otherwise, there must be a prefix of the form $01^*0$. We now distinguish several cases:

$$
\begin{array}{c|cccc}
\text{prefix} & 00 & 010 & 0110 & 01110 \\\hline
\text{codeword} & 0 & 01 & 0 & 01
\end{array}
$$
Longer runs of $1$ cannot be decoded at all.


Are most machine learning problems the same problem? (NP-hard)

I don't find this a useful or accurate perspective.
It's not true that all NP-hard problems are identical, not even under polynomial-time reductions.  All NP-complete problems can be reduced to each other in polynomial time, but NP-complete is different from NP-hard.
When you see someone say something like "all NP-complete problems are the same problem", that is an informal slogan that should not be taken too seriously; you need to look at the technical statement behind that and see whether it is relevant to what you care about.  In the context of machine learning, I don't think it's very relevant or useful.
Machine learning is about average-case behavior, not worse-case behavior.  NP-hardness is about worst-case behavior.
In machine learning we focus more on behavior on typical problem cases, rather than worst-case problems.  For example, the no-free-lunch theorem demonstrates that no ML algorithm will work well on all problems.
In machine learning typically we are more interested in understanding their accuracy rather than their running time, and usually we are concerned with concrete performance on concrete tasks and empirical results rather than asymptotic running time or provable guarantees.
For these reasons, the tools built up for NP-completeness and NP-hardness may not add a lot of insight about machine learning.


You should perhaps look into Racket (formally known as Scheme, a derivation of Lisp). It's the language taught to first year CS students at my University. Since it's a functional programming language, the syntax and concepts are quite simple compared to C/C++, there are several libraries that can do some basic drawing or networking related things, and Dr. Racket as several debugging features... including a Stepper (i.e it will show and perform one substitution at a time when you click the "next" button). I think that it may be worth looking into: http://racket-lang.org/. It has several other features that you may like, such as teaching modules (beginner, intermediate, advanced, full student levels) and pretty good documentation and examples. The book: How To Design Program (http://www.htdp.org) is a great teaching reference for this language which has a few nice examples using some of the libraries I mentioned above.


Obtaining a computational history of a Turing Machine

It is correct that you cannot compute $C$ in case $M$ does not halt on $w$.

What can be done is to query $C$, that is for a given time $t$ to compute the $t$-th configuration of $M$ on input $w$. Also, you can compute finite prefixes of $C$ of given length. Possibly, these operations are already sufficient for the proof in the book that you read (which I did not read).

Also, from the outline you give it seems that it is not necessary to compute $C$ at all. If $M$ accepts $w$, there is a finite $C$ which will be recognized by $B$. The reduction has to compute $B$ from $M$ and $w$, not $C$ itself. $C$ is just the input that would witness non-emptyness of $L(B)$.


Counting number of perfect squares in an subarrays

Take random 64 bit integers. What are the chances that the AND of the first ten has more than one bit set? So for random numbers, I’d say the count is close to n^2 / 2, and it takes cn operations for small n to count them all.

If $x=0$ or $x=4^k$ then x is a square, and x AND y is a square for any y. So if the AND of the first five numbers for example is one of these squares, then the AND of the first six, seven, eight, ..., n numbers is a square. Here's a simple algorithm:

total = 0
for 1 ≤ i ≤ n
    x = (all bits set)
    for i ≤ j ≤ n
        x = x AND a[j]
        if x = 0 or x = 4^k for some k
            total += n - j + 1
            break from for loop for j
        else if x is a square
            total += 1

This works well when the numbers are random. To improve for the worst case (for example alternating between 2 and 3, where this simple algorithm would take quadratic time), calculate the AND of groups of 2, 4, 8, 16, 32 etc. numbers, and observe that when calculating the AND of say a million 64 bit numbers, there will only be 64 different values. This is slightly complicated but not hard to implement if you are really interested in the solution.


It depends on $x$ being bounded or not.

Suppose that $x$ is bounded as $x\in[0,x_{\mathrm{max}}]$. Then, the constraint $z=xy$ can be written as:
$$
\begin{cases}
z\leq x_{\mathrm{max}} y,\\
z\leq x,\\
z\geq x-(1-y)x_{\mathrm{max}},\\
z\geq 0.
\end{cases}
$$

You easily see that:

if $y=0$, then $z=0$; and
if $y=1$, then $z=x$.


How to check whether a graph is connected in polynomial time?

Make a BFS/DFS traversal on the graph. If you visited every vertex then it is connected otherwise not.
Note: You have to apply BFS/DFS only one time on the graph


Firstly, you need to decide if the floating point numbers you are working with are "normalized" or not.

Think about how binary numbers are represented in scientific notation.

Consider the number 100101.010101
The expression given above is not given in scientific notation, but what if we change that?
To re-write 100101.010101 in scientific notation, we move the binary point to the left until we have  $1.[\text{something}] * 2^{\text{some power}} $
For the specific example I gave, we have $(1.00101010101)_2*(2^5)_{10}$
Note that binary numbers written in scientific notation almost always begin as <one><dot><something>

As such, most computers today do not store the leading $1$. Normally, this leading $1$ would be the most significant bit of the mantissa. However, its existence is implied in normalized numbers. There is only one number whose binary scientific notation representation does not begin as "one-dot-something." That number, is zero. As such 1.0000[...] * 2 ^ [some large magnitude negative number] represents the number zero in many computer systems today.

You say that you want to represent $0.3$ as a floating point number.

First, I think it will help to represent $(1/2), (1/4), (1/8), (1/16),$ etc... in decimal form.

$(1/2) = 0.5$
$(1/4) = 0.25$
$(1/8) = 0.125$
$(1/16) = 0.0625$
$(1/32) = 0.03125$
$(1/64) = 0.015625$

Okay; $0.3 = 0.25 + 0.05$
$0.25 = (1/4)$. $0.05$ is the leftover remainder.

$0.05 = 0.03125 + 0.01875$
$0.03125 = (1/32)$.
$0.01875$  is the leftover remainder.

Okay; $0.3 = 0.25 + 0.03125 + 0.015625 + 0.00029296875$

We have $0.3 = (1/4) + (1/32) + (1/64) + 0.00029296875$
$(0.3)_{10} = (0.010011)_{2} + $ a remainder of $(0.00029296875)_{10}$

You said that you only wanted a 4 bit mantissa. I think our leftovers/remainder are small enough at this point.

Let's write the number in scientific notation.

$(0.3)_{10} = (1.0011)_{2} *(2^{2})_{10}  + $ a remainder of $(0.00029296875)_{10}$

I suppose we want the exponent in binary-format instead of decimal. We can do this:

$(0.3)_{10} \approx (1.0011)_{2} *(2)_{10}^{(100)_{2}}$

SIGN: POSITIVE
MANTISSA: 10011
EXPONENT: 100

You wanted a 4 bit mantissa, but I went out to 5 bits. We round the number to obtain that $0.3$ is represent-able as:

SIGN: POSITIVE
MANTISSA: 1001
EXPONENT: 100

A normalized float would omit the leading $1$ of the mantissa. However, simply explain in your homework, that it was not specified whether the float be normalized or non-normalized. Therefore, you chose to use non-normalized floating point numbers.

You asked about significant figures. There are many different definitions of "significant figure." All of these different definitions are about how many of the leftmost digits of the approximation are correct.

Imagine writing two numbers lined up on a sheet of paper

APROX: 0.00070384
EXACT: 0.00070392

Now, cover-up the rightmost digits with a blank sheet of paper

APROX: 0.0007
EXACT: 0.0007

They are both correct for the number 7. That's good. slide the topmost sheet of paper to the right

APROX: 0.00070
EXACT: 0.00070

They're still the same. That's 2 significant figures so far.

APROX: 0.000703
EXACT: 0.000703

Still the same up to 3 figures.

APROX: 0.0007038
EXACT: 0.0007039

Uh oh; 8 and 9 are different. So the exact value, and the approximation are the same up to 3 significant figures, but not 4 significant figures.

The above method does not work very well.

Note that 0.499999999999999999999999999999 is a very good approximation of 0.5 However, if you use the sliding paper method, then not a single digit matches, and so, the approximation is not correct to even 1 significant figure!

My procedure for calculating significant figures will be different from the sliding paper method. The procedure is as follows:

Put the exact value in scientific notation.
Put the approximate value almost in scientific notation. However, make sure the approximate number has same exponential term as the exact value. Maybe the approximation is not of the form X.XXX Maybe the approximate number looks like 0.0XXXX or XXX.X
Subtract the approximate from the exact, or vis versa.

The number of significant digits is the number of zeros on the left.
For example, 0.000XXX means 4 significant figures. 0.XXXXX means 1 significant figure.

To calculate teh number of significant figures, convert your floating-point number back into decimal:

SIGN: POSITIVE
MANTISSA: 1001
EXPONENT: 100

$(1.0011^{100})_{2} = (0.28125)_{10}$

Notice that the floating point approximation is not the same as the exact value of $0.3$
Just how different are they?

$3.0 *\text{some exponent} - 2.8125 *\text{the same exponent} = 0.1875$

The floating point approximation of 0.3 is correct to 1 significant figure.

Repeat the process for -0.29:
1. Calculate the floating point approximation.
2. Take the difference between the approximation and the exact value.
3. Count the number of leftward zeros in the difference.

$-0.29 = -(1/4 + 1/32 + 0.00875)$

Note that the remainder $0.00875$ is less than $(2^-6)$. Your mantissa is only 4 bits long, so we needn't worry about the remainder.

$-0.29 \approx -(1/4 + 1/32)$
$-0.29 \approx -0.28125$
$2.9 - 2.8125 = 0.0875$
The floating point approximation of 0.29 is correct to 2 significant figures.

The exact value of 0.3 + -0.29 is 0.01.

Compute the following:

(float approx of 0.3) + (float approx of -0.29) =
(2.8125) + -0.28125) =
0

Then compare the approximate value (0) to the exact value (0.1) for the number of significant figures of $z = float(x_1) + float(x_2)$

1.0 - 0.0 = 1.0

The result has zero significant figures of accuracy.

Note that your textbook's definition of significant figures is probably different than mine. In your homework, explain to your teacher what definition you used. The concept of significant figures is more important that the details. Knowing roughly how many digits of the approximation are correct is more important than knowing exactly how to compute the number of significant figures.


Is every X3SAT instance with no cycles satisfiable?

The graph below is a positive answer without words.

Here is the detailed proof.
Definitions
Let $X$ be an instance of X3SAT.

$X$ is linear if any two clause shares at most one variable.
$X$ is monotone if all literals in all clauses are positive.
A walk in $X$ is a sequence of clauses where each clause is not disjoint with the clause following it. The length of the walk is the number of its clauses. A walk starts with variable $v$ if its first clause contains $v$. A walk ends with variable $v$ if its last clause contains $v$. A walk is said to connect two variables if it starts with one of the variables and ends with the other variable. In particular, any clause connects all variables in it.
A trail is a walk in which all clauses are distinct.
$X$ is connected if there is a walk between any two variables.
A cycle is a walk whose first clause is its last clause. A simple cycle has no repeated clauses except the first and last clause. $X$ is acyclic if $X$ has no simple cycles, i.e., there is at most one trail between any two variables,
For any two variables, the distance between them is the minimum length of a walk that connects them. The distance between a variable and itself is 0.

A linear monotone acyclic instance of X3SAT is always satisfiable.
Let $X$ be a linear monotone acyclic instance of X3SAT whose set of variables is $V=\{v_1,v_2, \cdots, v_n\}$. Because of monotonicity, we will use variable and literal interchangeably. Each clause in $X$ is also treated as the set of three variables in it.
Assume $X$ is connected. Otherwise, $X$ is the union of two disjoint linear monotone acyclic instances of X3SAT that can be treated independently.
Let $d(u)$ denote the distance from $v_1$ to variable $u$.
Claim 1. For any clause $c=(t,u, w)$, $\{d(t), d(u), d(w)\}=\{\ell, \ell, \ell-1\}$ for some $\ell\ge1$.
Proof: If $c$ contains $v_1$, then it is easy to see that $\{d(t), d(u), d(w)\}=\{1, 1, 0\}$. Now assume $c$ does not contain $v_1$.
WLOG, let $d(w)=\ell-1 > 0$ be the minimum among the three distances. Let $c_1, \cdots, c_{\ell-2}, c_{\ell-1}$ be the unique trail from $v_1$ to $w$. The shared variable between $c_{\ell-2}$ and $c_{\ell-1}$ cannot be $t$ or $u$, since $d(t)\ge \ell-1$ and $d(u)\ge\ell-1.$ That means $c_{\ell-1}\not=c$. Suppose there is a trail $b_1, b_2, \cdots, b_{\ell-1}$ from $v_1$ to $t$. Then for the same reason, $b_{\ell-1}\not=c$. We can reduce the walk $c_1, \cdots, c_{\ell-2}, c_{\ell-1}, c, b_{\ell-1}, b_{\ell-2}, \cdots, b_1, c_1$ to a simple cycle, which is a contradiction, which implies that there is no trails of length $\ell-1$ from $v_1$ to $t$, i.e., $d(t)\gt\ell-1$. Since $c_1, c_2, \cdots, c_{\ell-1}, c$ is a walk of length $\ell$ from $v_1$ to $t$,  $d(t)=\ell$. Similarly, $d(u)=\ell.$ QED.
Fix a total order $\prec$ on $V$. For example, we can let $v_p\prec v_q $ if $p<q$.
Let $A_0=\{v_0\}$. For all $\ell\ge 1$, define $A_{\ell}$ recursively by
$$A_\ell=
\{t\in V: d(t)=\ell \text{ and the last clause of the shortest trail}\\
\text{ from } v_1\text{ to }t\text{ is }(t,u, w)\text{ for some }u,w\in V \text{ such that }\\
d(t)=d(u)=\ell\text{ and }d(w)=\ell-1\text{ and } w\not\in A_{\ell-1}\text{ and }t\prec u\}$$
Let $A=\cup_{\ell=0}^{\infty}A_\ell$. Note that if $d(t)=\ell$, then $t\in A$ iff $t\in A_\ell$.
Claim 2: $A$ shares exactly one variable with each clause.
Proof. Let $c$ be a clause in $X$. By claim 1, $c=(t,u,w)$ where $d(t)=d(u)=\ell$, $d(w)=\ell-1$ and $t\prec u$. The last clause of the shortest trail from $v_1$ to either $t$ or $u$ is $c$.

$w\in A_{\ell-1}$. By definition, $t$ and $u$ are not in $A_\ell$.
$w\not\in A_{\ell-1}$. By definition, $t\in A_\ell$ and $u\not\in A_\ell$.

QED.

Exercises
Let X be a linear monotone acyclic instance of X3SAT with $n$ variables and $m$ clauses.
Exercise 1..(One minute or two) Explain that $A_1$ is empty. Give an example where $A_3$ is not empty.
Exercise 2.. Show that $n= 2m+1$.


Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts

$\Omega(\cdot)$ means “at least that many steps” _up to a multiplicative constant. There's a gap between $n!$ and $n^n$, and that gap is more than a multiplicative constant. But we aren't looking for an asymptotic bound on the number of length of the list that can be sorted in $k$ steps, but on the minimum number of steps $S(n)$ that it takes to sort a list of length $n$ in the worst case.
You've seen that after $k$ steps, it's only possible to distinguish between $2^k$ different orderings of the list. You've also seen that the total number of orderings of the list is $n!$. The number of steps must be sufficient to distinguish between all orderings, therefore $2^{S(n)} \ge n!$. This condition can equivalently be stated $S(n) \ge \lg(n!)$ where $\lg$ is the logarithm in base $2$.
You want to prove $S(n) \in \Omega(n \lg n)$. (Or maybe $\Omega(n \log n)$ for some different logarithm base, but logarithm bases are equivalent up to a multiplicative constant.) You know that $S(n) \ge \lg(n!)$. Therefore it is sufficient to prove that there is a multiplicative constant $C$ such that for large enough $n$, $\lg(n!) \ge C n \lg n$. Note that this is equivalent to $n! \ge 2^{C n \lg n}$, i.e. $n! \ge n^{C n}$, and the family of functions $n \mapsto n^{C n}$ is not the same as the family of functions $n \mapsto C n^n$.
Stirling's formula, obtained via calculus, can give you a precise approximation of $n!$ from which you can prove the desired asymptotic equality. But here we only need a weak version of it that can be proved more easily. For $n \ge 4$:
$$ \begin{align}
\lg(n!) &= \lg(1) + \lg(2) + \ldots + \lg(n) \\
&\ge \lg \lceil n/2 \rceil + \ldots + \lg(n) && \text{(only sum the larger half of the terms)} \\
&\ge (n/2 - 1) \lg(n/2) && \text{(all terms are larger than the smaller term; count them and round down)} \\
&\ge \left(\frac{1}{2} - \frac{1}{n}\right) \dfrac{\lg(n) - 1}{\lg(n)} \; n \lg(n) && \text{(algebra)} \\
&\ge \frac{1}{8} n \lg(n) && \text{(approximate the complicated factor by a constant)} \\
\end{align} $$
For large enough $n$, $\lg(n!)$ is larger than $n \lg(n)$ multiplied by the constant $1/8$. This fits the definition of $\lg(n!) \in \Omega(n \lg(n))$.


Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$

There is a well-known classical result of the theory of $p$-degrees stating that every non-zero $p$-T-degree splits into two incomparable $p$-T-degrees.

So assuming $P\neq NP$, by the splitting theorem, the $p$-T-degree of Turing-complete problem for $NP$ splits into two non-T-complete incomparable $p$-T-degrees.

REFERENCES

Sublattices of the polynomial time degrees

LADNER, R. E. (1973), Polynomial time reducibility, in Proc. 5th Annual ACM Sympos. on Theory of Comput., pp. 122-129

LADNER, R. E. (1975), On the structure of polynomial time reducibility, J. Assoc. Comput. Math. 22, 155-171


Are all context-free and regular languages efficiently decidable?

Regular language membership can be decided in $\cal{O}(n)$ time by simulating the language's (minimal) DFA (which has been precomputed).

Context free language membership can be decided in $\cal{O}(n^3)$ by the CYK Algorithm.

There are decidable languages that are not in $\sf{P}$, such as those in $\sf{EXPTIME}\setminus \sf{P}$.


Balanced weight distribution into buckets, but with a twist (aka sharding a list into k even shards)

Yes, this can be solved as a straightforward application of dynamic programming, once you define an objective function to measure how "evenly divided" the buckets are.  Let $A[j]$ denote the value of the objective function for the best way to split integers 1..j.  Then you can compute the value of $A[j]$ given the values of $A[1],\dots,A[j-1]$ (you just consider all possibilities for how many integers go in the last bucket), so there is a dynamic programming algorithm with running time at most $O(n^2)$.

This problem is sometimes called the Linear Partition Problem, and a solution can be found in Section 8.5 of Skiena's "Algorithm Design Manual".


Do Nested Monte Carlo Algorithm always find the best score where score is the number of moves on the leftmost path

You've asked many questions.  The usual rule on this site is to ask one question per post.

The definition of sample is correct.  play evaluates where you end up after making a single move.  sample evaluates the result of a game where both players randomly choose a move.

In other words, imagine a particularly stupid strategy, where both players randomly pick a move (blindly, without taking into account the position or any other strategy; it's purely random) at each step.  Starting from position, you could simulate playing out a full game and see what happens.  The resulting score (which player won) gives you a very crude approximation of how you should evaluate position.  For instance, suppose in that random playout, the first player happens to win.  Then we might suspect that position is better for the first player than the second player.  Obviously, this is a crude approximation, but it's just a start.  And that's what sample computes.

So that approach computes the level-0 approximation of the evaluation of each position.

Of course, given a way to compute an evaluation score for any position, that gives you a way to play the game: whenever it is your turn, look at all possible moves you could make, evaluate the resulting position, and pick whichever move takes you to the position that looks most favorable for you.  That's what the logic is doing with the argmax.  So, this gives you a level-0 strategy.

Now we're ready to talk about how to compute a level-1 approximation of the evaluation of each position.  Basically, we simulate doing a playout -- we simulate playing the game -- but now rather than using a blind random strategy, we use a slightly smarter strategy.  In particular, each player uses the level-0 strategy described above to decide how to move.  So now simulate a game where both players are using the level-0 strategy, starting from position, and keep going until the end of the game.  See which player wins.  This is your level-1 evaluation of position.

You can use the level-1 evaluation to form a level-1 strategy: always make the move that leads to the position whose level-1 evaluation is as favorable as possible.

And now you can probably see how to use this idea to form a level-2 evaluation, and a level-2 strategy, and a level-3 evaluation, and so on.  That's the idea of nested Monte Carlo.


Find which vertices to delete from graph to get smallest largest component

The problem you are describing is known as Component Order Connectivity in the field of vulnerability measures of graphs.  The decision version of the problem is as follows:

  Component Order Connectivity:

  Input:  Graph $G = (V,E)$, integers $k$ and $\ell$

  Question: Does there exist a set of vertices $X \subseteq V$ of size at most $k$ such that the size of the largest component of $G - X$ is at most $\ell$?

The problem is obviously NP-complete since it generalizes vertex cover; the case when $\ell=1$ is vertex cover.  Hence the problem cannot be fixed parameter tractable when parameterized by $\ell$ (unless $FPT = W[1]$).  The problem is also known to be $W[1]$-hard when parameterized by $k$.  Hence, we have to resort to algorithms with an exponential running time in $k+\ell$.

Very interesting question.  For input $G,k,\ell$, a brute force approach would be:

branching(G,k,l):
    Find a connected set of vertices D of G of size l+1
    if no such D exists:
            return True // no component of size > l
    for v in D:
        if branching(G-v,k-1,l):
            return True
    return False

The algorithm runs in time $(\ell + 1)^k \cdot n^2$.

Observe that any yes instance $G,k,\ell$ of the problem has treewidth, and indeed pathwidth at most $k+\ell$.  This can be observed by seeing that taking a deletion set $X$ of size at most $k$ yields a graph $G-X$ where every connected component has size at most $\ell$.  Hence, a valid path decomposition is simply to construct one bag for each of the components in $G-X$ and then add all of $X$ to every bag.  It follows that any yes instance has $|E(G)| \leq n(k+\ell)$.

A related problem has been studied in the past under the name Graph Integrity, or Vertex Integrity to distinguish the vertex deletion version and the edge deletion version:

  Vertex Integrity:

  Input:  Graph $G = (V,E)$, integer $p$

  Question: Does there exist a set of vertices $X \subseteq V$ such that $|X| + \max_{D \in cc(G-X)}|D| \leq p$?

That is, the sum of the deletion set and the size of the maximal component should be minimized.  This problem is also NP-hard.  See, e.g.,

Clark, L.H., Entringer, R.C., Fellows, M.R.: Computational complexity of integrity. J. Combin. Math. Combin. Comput 2, 179–191 (1987)
Fellows, M., Stueckle, S.: The immersion order, forbidden subgraphs and the complexity of network integrity. J. Combin. Math. Combin. Comput 6, 23–32 (1989)


How to develop an $O(N)$ algorithm solve the 2-sum problem?

Let $A$ be the sorted input array. Keep two pointers $l$ and $r$ that go through the elements in $A$. The pointer $l$ will go through the "left part" of $A$, that is the negative integers. The pointer $r$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $0 \notin A$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $A$.

COUNT-PAIRS(A[1..N]):
 l = index of the last negative integer in A
 r = index of the first positive integer in A
 count = 0;

 while(l >= 0 and r <= N)
   if(A[l] + A[r] == 0)
     ++count; ++right; --left; continue;

   if(A[r] > -1 * A[l])
     --left;
   else
     ++right;

It is obvious the algorithm takes $O(N)$ time.


CFG for $w\#x$ where $|w| = |x|$ and $w \neq x^R$

A word belongs to your language if it has one of the following forms:
$$
\Sigma^i 0 \Sigma^j \# \Sigma^j 1 \Sigma^i \\
\Sigma^i 1 \Sigma^j \# \Sigma^j 0 \Sigma^i
$$
Given this, you should be able to construct a context-free grammar for $L$.


Merge two sorted arrays without using additional memory

Here, great solution, from: http://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/

Below is C++ implementation of above algorithm.

// C++ program for implementation of Sieve of Atkin
#include <bits/stdc++.h>
using namespace std;

// Merge ar1[] and ar2[] with O(1) extra space
void merge(int ar1[], int ar2[], int m, int n)
{
    // Iterate through all elements of ar2[] starting from
    // the last element
    for (int i=n-1; i>=0; i--)
    {
        /* Find the smallest element greater than ar2[i]. Move all
           elements one position ahead till the smallest greater
           element is not found */
        int j, last = ar1[m-1];
        for (j=m-1; j >= 0 && ar1[j] > ar2[i]; j--)
            ar1[j+1] = ar1[j];

        // If there was a greater element
        if (j != m-1)
        {
            ar1[j+1] = ar2[i];
            ar2[i] = last;
        }
    }
}


Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines

Here are some hints. The easy direction is simulating cellular automata with Turing machines. Turing machines can simulate C programs, and you can simulate cellular automata in C. (Replace C with your favorite programming language.)

Given a Turing machine, we want to construct a cellular automaton simulating it. We need to upgrade the alphabet by allowing, besides regular symbols $\sigma$, also symbols $\langle q,\sigma \rangle$ which signify that the head is currently at that point, the state is $q$, and the tape symbol is $\sigma$. The initial tape would contain $\langle q_0,\sigma_0 \rangle$ as the first symbol, where $q_0$ is the initial state and $\sigma_0$ is the first symbol on the input tape of the Turing machine.

It remains to show how to simulate the Turing machine by an appropriate choice of the propagation rules $\delta$. The basic idea is to maintain the invariant that the contents of the cells constitute of the tape of Turing machine, with the exception of the location of the head, which is of the form $\langle q,\sigma \rangle$. I'll let you work out the details.


What is postorder traversal on this simple tree?

You are not wrong.

A postorder  traversal visits the left subtree, then the right subtree, then the root of the current tree (recursively).


Partitioning a Number on the basis of an equation

Non-negative means that they can be 0. So set everything to $0$ except $b$ and $d$ because they have the highest coefficient.

$x=3*0+4b+2*0+4d$ and $0+b+0+d=5$

$x=4b+4d$ and $b+d=5$

$x=4(b+d)$ and $b+d=5$

$x = 4*5 = 20$


How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge?

Your problem is $\rm NP$-hard by a reduction from the minimum-weight Steiner tree problem.

Let $G=(V,E;w)$ be a graph with non-negative edge weights $w(e)$, $e \in E$, and let $S \subseteq V $ be a non-empty set of terminal vertices.

The vertex set in your problem will coincide with $V$. Choose the concave function $c_e(x)$  that describes the cost of sending $x$ units of flow across edge $e$ as $c_e(x) = w(e)$.
Pick an arbitrary terminal $s \in S$ and make it a source with supply $|S|-1$.
Make every vertex in $S \setminus \{ s \}$ a sink with demand $1$.

There is a Steiner tree $T$ of cost at most $k$ if and only if your problem admits a flow of cost at most $k$.

$\Rightarrow$) $s$ send one unit of flow to each vertex $v \in S \setminus \{ s \}$ using the unique path in $T$ between $s$ and $v$.

$\Leftarrow$) Consider the subgraph $H$ of $G$ induced by the set of edges traversed by non-zero flow. Since $H$ contains at least one path from $s$ to each vertex in $S \setminus \{ s \}$, it must have a connected component $C$ that spans all the vertices in $S$. Let $T$ be an arbitrary spanning tree of $C$. The cost of $T$ w.r.t. $w$ is exactly the contribution of the edges in $T$ to the cost of the flow. By our choice of the concave functions, this is upper bounded by the cost of the flow itself.

Notice that, by suitably subtracting epsilons from the cost functions, you can adapt this reduction to work for strictly concave functions. In this case it is convenient to relate  a flow of cost at most $k$ to Steiner tree of cost at most $\lceil k \rceil$.


The problem you have given is similar to KNAPSACK as Yuval Filmus mentioned.

KNAPSACK problem is defined as:

maximize $\sum_{i=1}^n v_i x_i$
subject to $\sum_{i=1}^n w_i x_i \leq W$ and $x_i \in \{0,1\}. $

I assume the pair (0,0) is used so that you may not choose pairs for some of the $M_j$'s. Otherwise (0,0) pair is irrelevant in the problem.

If this is so, then your problem can be easily shown to be NP-complete. We can reduce KNAPSACK to your problem by taking $N=n$ and have each $M_j$ as a copy to the KNAPSACK instance (after negating $v_i$'s and $w_i$'s of course).

If pair (0,0) is not used in a way that I described above, then too you can circumvent the issue by adding $N$ pairs $(x_{N+i,j},y_{N+i,j})$, for $1\leq i \leq N$ in set $M_j$ for $1 \leq j \leq N$, so that each $M_j$ has now additional $N$ pairs (total of $2N+1$). Each $x_{N+i,j} = y_{N+i,j} = 0$ for all $i$'s and $j$'s.

If you say that each pair need to be distinct, then we can take $x_{N+i,j} = y_{N+i,j} = \epsilon_{i}$ to make each pair distinct, where $\epsilon_{i} \ll 1$ is an arbitrarily very small quantity. We also replace $R$ by $R+\Sigma_i \epsilon_i$.


Is $L=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{+}\right \}$ Regular?

When is a string of the form $a^*ba^*b$ in the language $L$, i.e., of the form $wxw$, for nonempty $w,x$?

Or, to be more explicit, what is the language $L \cap a^*ba^*b$?


Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages.

Suppose $L$ is context-free. The pumping lemma says there exists some integer $p \ge 1$ such that every string $s$ in $L$ where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

Let $s$ be a string in $L$ longer than $p$, and $u$, $v$, $w$, $x$, and $y$ have the properties given by the pumping lemma. Thus $uwy, uvwxy, uv^2wx^2y\in L$. Let $a$ and $b$ be such that $$|uwy|=2^a, |uvwxy|=2^b$$ Note $b>a$. Then $$|uv^2wx^2y|=2|uvwxy|-|uwy| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ But $2^a(2^{b+1-a}-1)$ is not a power of 2, and so $uv^2wx^2y\notin L$.


What was the first Turing-Complete programming language?

Why not read this Wikipedia article.

  The first programming languages designed to communicate instructions to a computer were written in the 1950s. An early high-level programming language to be designed for a computer was Plankalkül, developed by the Germans for Z1 by Konrad Zuse between 1943 and 1945. However, it was not implemented until 1998 and 2000.

Also, I think that it is wrong to consider a programming language as such to be Turing Complete since the concept of Turing completeness applies to a computational model, not to a programming language itself. For example, it is Turing machine, RAM machine, or Post systems that is Turing complete and not a set instructions or programming languages used to program them.

If our real life computers had infinite memory we could consider them a Turing machine equivalent to our abstract model we use in CS and Math, meaning that it is not programming languages or instructions sets used to program CPU that makes real life computers not equivalent to the abstract model.


Infinite Boolean circuits as a model of computation

Your idea is equivalent in power to non-uniform circuits.  Thus, it doesn't formalize the concept you want it to formalize.  You were hoping that your notion of an infinite circuit would capture the power of uniform circuits / Turing machines, but it doesn't -- like non-uniform circuits, it is "too powerful" (more powerful than any uniform model).  Thus an infinite circuit is essentially still a non-uniform model of computation, even if it doesn't look like it on the surface.

Consider the following infinite circuit $C$: if the $i$th bit of the input is 1 and the $i+1$st bit is 0, then the $i$th output bit is $c_i$, otherwise that output bit is 0.  Here $c_i$ is a constant that is 1 if the $i$th Turing machine (in some canonical enumeration of all Turing machines) halts, or 0 otherwise.

This circuit is an infinite circuit, in your sense.  You can think of it as a sequence of circuits $C_1,C_2,\dots$, where $C_N$ is the circuit that takes $N$ bits of input and produces $N$ bits of output, obtained by zero-padding its input and feeding that to $C$.  Thus that sequence of circuits "converges" to $C$.

However, $C$ has the following peculiar property: given $C$, you can solve the halting problem.  In particular, if you feed in $i$ in unary as input to $C$, then the output will indicate whether the $i$th Turing machine halts or not.  Thus, infinite circuits can solve undecidable problems.  Like non-uniform circuits, infinite circuits are in some sense "too powerful" -- they're not realistic.

So your construction doesn't really eliminate any of the issues with the non-uniform circuit model.  It just recreates them, in a slightly different guise.

A separate challenge with your infinite circuit idea is that it is not clear how to handle circuits that produce a single bit of output.  Normally, in circuit complexity, we study circuits that take $N$ bits of input and produce a single bit of output.  It's not clear how such a sequence of circuits can "converge" to a single infinite circuit (what is its single output bit, and how is it computed?).


Algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$

Consider the NFA $A_1=(Q,\Sigma,q_0,F_1,\delta_1)$. Observe that an accepting run of $A_1$ induces an accepted word. That is, we don't really care about the alphabet of the automaton if we only want to consider word length.

Thus, instead of constructing the intersection automaton directly, first change the alphabet of both automata to be $\Sigma=\{a\}$, by changing the letters in all the transitions to $a$. That is, for a transition $\delta_1(q,\sigma)=q'$, change the transition to $\delta(q,a)=q'$.

Now construct the product automaton, and check emptiness.

I'm leaving the correctness proof as an exercise.


Algorithm undirected graph to directed strongly connected graph

The idea is that if we find a cycle in $G$, then we can orient its edges so that the nodes in the cycle will be all strongly connected. The cycle can then be collapsed into a single node. If the graph had no bridges the new graph will also have no bridges and this procedure can be repeated. Eventually, you will be left with a single node, meaning that the whole graph is a single strongly connected component, as desired.

More precisely, you can iteratively do the following:

Find a cycle $C $in $G$;
Orient the edges of $C = \langle u_1, u_2, \dots, u_k, u_{k+1} = u_1 \rangle$ in an arbitrary but consistent direction w.r.t. $C$. For example, for $i=1, \dots, k$ orient $(u_i, u_{i+1})$ towards $u_{i+1}$;
Orient the chords of $C$ in an arbitrary direction.
Identify the vertices in $C$, possibly creating parallel edges (but ignoring self-loops). This means replacing $u_1, \dots, u_k$ with a new super-vertex $\overline{u}$. For every edge $(x,y)$ where $x \in C$ and $y \not\in C$, add a new edge $(\overline{u}, y)$.
Repeat until a single vertex is left in $G$.

Notice that if there are two or more vertices left in $G$ then there must still be a cycle (otherwise there is a bridge that was also bridge in the original graph). This means that you will eventually be left with a single vertex. When this happens, all edges in the original graph $G$ must have been assigned a direction and you are done.

If you think of using the above algorithm while performing a single DFS visit to discover the cycles to contract, then all the cycles $C$ will be of the form $\langle u_1, \dots, u_k, u_{k+1} = u_1 \rangle$, where for $i=1,\dots,k-1$, $u_{i}$ is the parent of $u_{i+1}$ in the DFS tree, and $(u_k, u_1)$ is a back-edge. If you use the above choice for the orientation of the edges of $C$, then this is equivalent to this simpler algorithm:

Perform a DFS visit of $G$ from an arbitrary vertex $r$ to obtain a tree $T$.
Orient all the edges of $T$ away from $r$.
Orient the edges not in $T$ towards $r$ (notice that this is well defined since there will be no edges between two nodes at the same depth in $T$).

You can also give a direct proof that the orientation $G'$ computed by this second algorithm is a strongly-connected graph. It is clear that there is a path from $r$ to any other vertex in $G'$. The following claim implies the converse.

Claim: Let $(u,v)$ be an edge of $T$, with $u$ being the parent of $v$. There is a path from $v$ to $u$ in $G'$.

Proof:
Since $(u,v)$ is not a bridge, there must be a cycle of the form $C = \langle u_1 = u, u_2 = v, u_3, \dots, u_k, u_{k+1} = u_1 \rangle$.
Let $i$ be the smallest index in $\{1, \dots, k\}$ such that $u_i$ lies in the subtree $T_v$ of $T$ rooted at $v$ and $u_{i+1} \not\in T_v$ (this edge must always exist).
Since $u_i \in T_v$, there is a (possibly empty) directed path $P$ from $v$ to $u_i$ in $G'$.
Since $u_{i+1}$ is an ancestor of $v$ and $u_{i+1} \not\in T_v$, $u_{i+1}$ must be an ancestor of $u$ (possibly $u$ itself). This means that there is a (possibly empty) directed path $Q$ from $u_{i+1}$ to $u$ in $G'$.
Finally, $(u_i, u_{i+1})$ is not a tree edge, hence it is directed towards $u_{i+1}$. This means that $P \circ (u_i, u_{i+1}) \circ Q$ is a path from $v$ to $u$ in $G'$ (where $\circ$ denotes concatenation). $\quad\square$


Removing duplicates efficiently and with a low memory overhead

Why not bin and chain?

The idea is to store positive integers representable by $n = k+m$ bits in an array $A$ of $2^k$ entries representing ranges of values: entry $A[y]$, $y \ge 0$, represents the range $[2^m y, 2^m(y+1)-1]$.  For any $1 \le x \lt 2^n$ we may write $x = 2^m y + z$ where $y$ has $k$ bits and $z$ has $m$ bits.  Try to store $z$ (not $x$!) at location $y$:

When $A[y]=z$ already, do nothing: $x$ is a duplicate.
When $A[y]$ is uninitialized, store $z$ at $A[y]$.
Otherwise, store an index into a separate array used to chain the $z$'s (which have collided at $y$) in linked lists.  You will have to search linearly through the list headed by $A[y]$ and, depending on what the search uncovers, potentially insert $z$ into the list.

At the end, $f(S)$ is easy to recover by looping through the initialized entries of $A$ and--by merely concatenating two bitstrings--reassembling each $z$ found at location $y$ (either directly or within a chain referenced there) into the original value $x = 2^m y + z$.

When the distribution is close to uniform and $2^k$ exceeds $N$, there will not be much chaining (this can be assessed in the usual ways) and the chains will tend to be short.  When the distribution is nonuniform, the algorithm still works, but can reach quadratic timing.  If that's a possibility, use something more efficient than chains (and pay a little overhead for storage).

The storage needed is at most $2^n$ bits for $A$ and $2^{2k}$ bits for the chains (assuming $m \le k$).  This is exactly the space needed to store $2^k$ values of $n$ bits each. If you're confident in the uniformity, you can underallocate the storage for the chains. If nonuniformity is a possibility, you may want to increase $k$ and fully advocate the chain storage.

An alternative way of thinking about this solution is that it is a hash table with a particularly nice hash function (take the $k$ most significant bits) and, because of that, we only need to store the least significant $m=n-k$ bits in the table.

There are ways to overlay storage for the chains with the storage for $A$ but it doesn't seem worth the bother, because it wouldn't save much (assuming $m$ is much smaller than $k$) space and would make the code harder to develop, debug, and maintain.


Is the word problem for regular languages in ALogTime?

If the regular expression is not fixed, it is rather doubtful that your problem belongs to ALOGTIME. However, the phrase word problem usually refers to a fixed setting, which in this case means that the regular language is fixed.

If the regular language is fixed, this is apparently shown in Barrington's famous paper. Alternatively, you can describe a logtime game for deciding the word problem for regular languages. The game starts with the YES player stating the final (accepting) state and the state at the middle (the initial state is of course fixed). The NO player then chooses one of the halves, and the game continues until it comes down to a word of length 1, in which case the problem can be settled by examining one character of the input.


"Defining" a type is the act of building a new type composed of one or more pre-existing data types. For example, the "Complex Number" type is often declared as an ordered pair of "Real Numbers" :

Type Complex
  Real a
  Real b
End

a and b being the real and imaginary parts.

This sample of pseudo-code is a "Type Definition".


Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype?

If the functions are sufficiently well-behaved, as in your example, you can express f and g as regular transducers for trees.  Then you can compute the composition of two such transducers, which will also be a regular transducer (I believe), and convert it back to a Haskell function.

Another approach: in some cases, simple let-substitution might suffice.  For instance, given your f and your g, we can identify their composition fg via the following sequence of steps.  We know fg = f . g, so plugging in the definition of g, we get:

fg A = f(g(A)) = f A
fg (B x) = f(g(B x)) = f(B (B (B (g x))))

Now plugging in the definition of f, we get:

fg A = A
fg (B x) = B (B f(B (B (g x))))

Continuing to plug in the definition of f, we get:

fg A = A
fg (B x) = B (B (B B( f(B (g x)))))

And plugging in the definition of f once more:

fg A = A
fg (B x) = B (B (B B( (B (B (f(g x))))))

which simplifies to

fg A = A
fg (B x) = B (B (B (B (B (B (fg x)))))

And now you have your desired recursive definition of their composition.  Notice that this is the same as the function h you wanted to get out.  As far as I know, there's no guarantee that this procedure will always work, but it is easy enough to apply.


Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system?

You're right that this is an impossible problem to solve in an asynchronous distributed system, and you're also right that it would solve a lot of problems if we could get a totally ordered clock. But it only solves "all" our problems if the clock has the additional constraint of a meaningful relationship with real time.

The two best solutions we have are partial ordering (Lamport clocks) and consensus (which can be fault tolerant but is typically driven by an elected leader). The latter provides total order and works well in practice (with randomized timers), but is impossible to guarantee in theory (FLP).


I am not sure, if I understood the question correctly, but are you asking for the number of rooted binary trees of size $n$, with nodes labeled from $1,...,n$, where isomorphic trees with different labelings are counted as different?

If so, isn't your labeling just adding $n!$ different possible labelings for each class of isomorphic trees? I.e. your total number of trees would be $n!C_n$, where $C_n$ is the $n$-th Catalan number.


Context-sensitive grammar for the language of words concatenated with themselves

Indeed, there is a simple trick that allows you to add extra information at a certain position: just replace a letter adjacent to the position and mark it with the information, and the original letter.

In your example, have a nonterminal $M$ for the middle, but as it can not be deleted, it also counts as a normal letter. Thus we have two copies $M_a$ and $M_b$ to indicate the letters replaced.
In the end of the derivation the markers should be replaced by their letter content, by simple productions like $M_a\to a$.

In most cases the application of $M_a\to a$ needs to be performed at the end of the derivation process. In some constructions this does not need to be "timed": when the $M$ disappears too soon, the derivation cannot find a proper position and the process will not stop successfully. In other cases one does need a kind of control. This is sometimes done by introducing a nonterminal as a signal that moves along the letters. Again, this signal should also carry a terminal otherwise you end up in the same problems.

Moving information around is easy in so-called monotonic grammars ($\alpha\to \beta$ with $|\alpha|\le\beta|$) using rules like $XA \to AX$, which can be seen as $X$ jumping over $A$. For proper context-sensitive grammars one needs to split this in three steps: $XA \to XA^X, XA^X\to AA^X, AA^X\to AX$. in each production one letter is changed in a proper context. It takes quite some imagination to see this process does not interact with other parts of the derivation. E.g., what happens when the $A$ in the last step is first involved in another derivation step?

This might not work for very short words, when there is more information than positions available. The most simple solution to that is to ignore short strings in your construction, and generate them separately.


simple lower bound for constructing a Spanning tree

i tried to solve this problem in this way:

Assume that there exists a correct SPT protocol $A$ thatuses fewer than $m$ messages. This means that there is at least one link in $G$ where no message is transmitted.
Consider an execution of the algorithm on $G$, and let $e = (x, y) \in E$ be
the link where no message is transmitted by $A$.

Now construct a new graph $G^{'}$  from $G$
by removing the edge $e$ and adding a new node $z$ and two new edges $e1 = (x, z)$ and
$e2 = (y, z)$. Set $z$ in a noninitiator status ($z$ does not starts the execution of the algorithm). Run exactly the same execution
of $A$ on the new graph $G$   : since no message was sent along $(x,y)$ in the original execution in $G$, $x$ and $y$ never send a message to $z$ in the current execution in $G^{'}$   ; and since $z$ is not an initiator and does not receive any message, it will not send any message.

At the end of the alghoritm a tree $T$ should have been constructed,
however, $z$ is not part of $T$, and hence $T$ does not span $G$.

in other words $A$ works only if $z$  is in a initiator status, therefore $A$ is not correct.


Throwing an error when initializing an object in c++

Pet(const string & the_name, const string & the_species): name(the_name), species(the_species), age(0)
  {

     if (species == "cats" || species == "dogs")
        throw std::invalid_argument( "received negative value" );
  }


Take the graph $D_1$, and cut the bolded edge in the middle, so that each of its two halves has degree 3 (including the bolded edge). Take $k$ copies of this, and paste them along bolded edges in a cyclic fashion. You get $D_k$.


Balanced weighting of edges in cactus graph

So this question has been bothering me: why a cactus, if there's already a linear-time algorithm for a more general class?

The primal problem is known as the fractional matching problem, and, unsurprisingly, it has been studied as well. Balinski (whose result was made known to me via Schrijver's book Combinatorial Optimization) characterized the extreme points of the fractional matching polytope as consisting of an integer matching plus half of a collection of odd cycles. Given the relatively low input limits, I suspect that the intended solution of the problem poser was to modify Edmonds's blossom algorithm in a way that, for now, I will leave for you to discover. The structure of the cycles in a cactus makes this algorithm simple enough to be appropriate for a contest.

As sxu points out, this problem is amenable to linear programming. If you need just the objective value, the dual LP has the same objective value and is the fractional vertex cover problem. The nice thing about vertex cover is that it has a half-integral optimum; in linear time, you can use depth-first search to compute a tree decomposition of the cactus of width O(1) and solve the dual LP with a dynamic program that tries variable values in {0, 1/2, 1}.

If you actually need a solution for the primal, then complementary slackness might help, but I can't help but suspect that the restriction to cacti is supposed to allow a more elementary solution.