A compiler translates code written in one programming language into code in another language -- normally, with the semantics of the output code being the same as the input code (or with a strong relationship).

Personally, if you asked me to use the word strictly, I wouldn't call Doxygen a compiler.  The output isn't executable code, and doesn't have anything like the same semantics as the input source code.

See also Wikipedia's definition/explanation.

That said, there are many situations where we use a word loosely, when from context it will be understood what we're referring to -- so I'm not sure how useful it will be to look for a super-precise definition of the word.  If the specific definition is important in your writing, then it might be best to define how you plan to use the term.


Asymptotic notation and random variables

On first look, the notation $X = O(Y\,\log{n})$ seems intuitively reasonable since $X$ is always upper bounded by $c (Y\,\log n)$ for some constant $c$. ($c$ must be positive since $X,Y\ge1$).
Can we formalize the exact meaning of that notation?
Here is one natural definition.

Let $(\Omega,S,T)$ represents a set of 2-dimensional random vectors on $\Omega$ parameterized by $n$, i.e., for all $n$, $(S_n, T_n)$ is a random vector from $\Omega_n$ (which is a set of possible outcomes) to ${\Bbb R}^2$. We write
$$S=O(T){\text{ as }}n\to \infty $$
if and only if there is a positive constant $c$ such that for all sufficiently large values of $n$, for all $\omega\in\Omega_n$, the absolute value of $S_n(w)$ is at most $c\,T_n(w)$.

We can apply the above definition to $(I, X, Y\,\log n)$ where $I_n=[1,n]$.


How can I create a language using set operation to prove a language is not regular?

It looks like you are onto the right track. However, your notation is confusing me.

I would believe the following is what you are coming at.

$$\overline{(A\cap L(b^*c^*))} \cup \{\epsilon\} = \left\{b^{n} c^{n} \mid n \in \mathbb{N}\right\}$$
where $\overline S$ is the language of words not in $S$, a.k.a. the complement of $S$. Here are the facts that you will use.

$b^*c^*$ is a regular expression.
the intersection of two regular languages is regular.
the complement of a regular language is regular.
$\{\epsilon\}$ is a regular language.
the union of two regular languages is regular.
$\{b^{n} c^{n} \mid n \in \mathbb{N}\}$ is not regular.

I will leave the rest of reasoning to you.


That's a tough one.  I don't know what could cause that.
It can be hard to know why we see the results we do, when working with neural nets.  Often the best we can do is form several hypotheses, and then devise experiments to try to test those hypotheses.
Some possible explanations that you could try to test:

Perhaps it is noise / random chance

Perhaps the 50-pixel images are fairly homogenous and the 150-pixel images are fairly homogenous, and taking a combination of these two yields more diversity, which helps the network learn (e.g., it doesn't overfit to either)

Perhaps the 50-pixel objects don't come from the same distribution as the 150-pixel objects (e.g., the 50-pixel images are of children and the 150-pixel images are of adults; these differ in more ways than just size; or the background is correlated to the size of the object), and you get more regularization from exposing the network to both, or something (this is vague and might not be very different from the second explanation)

Maybe you can think of other possibilities.


Algorithm for dividing items into buckets while minimizing total weight

I assume that in the $k$ bucket case, each rock has up to $k$ colors (buckets) associated with it, which are the ones it can be put into.

It seems to me that a polynomial time algorithm can be obtained by reduction to a minimum-cost flow problem, which can be solved in polynomial time. Create a network with $k + n + 1$ nodes: $n$ rock nodes, $k$ bucket nodes, and $1$ source node. The source node is adjacent to each of the rock nodes, with edge capacity 1 and edge cost equal to the weight of the rock. Each rock node is also adjacent to all the bucket nodes it can be put into, with edge capacity 1 and edge cost 0. The source node has a supply of $2k$ units, and each bucket node has a demand of 2 units. Any integer flow of value $2k$ corresponds to a feasible assignment of $2k$ rocks to the buckets. The minimum cost integer flow corresponds to an assignment of minimum weight.


Help with understanding why we need an expectation in the loss

It's because $z$ is a random variable, and the term is a function of $z$.  So, without the expectation, the $\log$ term would be a random variable, and you can't use that as a loss; the loss needs to be a number.  You can use its mean (its expectation).


I think the question you are trying to ask is "is computability theory constructive?". And this is an interesting question, as you may see by this discussion on the Foundations of Mathematics mailing list.

Unsurprisingly, it has been considered, since a lot of recursion theory was developed by people with constructive sensibilities and vice versa. See e.g. Besson's book and the venerable Introduction to Metamathematics. It's pretty clear that the first couple of chapters of recursion theory survive moving to a constructive setting with minimal changes: e.g. the s-n-m theorem, Rice's theorem or the Kleene recursion theorems survive unchanged.

After the first chapters though, things get a bit tougher. In particular, the higher levels of the arithmetic hierarchy are usually defined by a notion of truth. In particular, widely used theorems such as the Low Basis Theorem seem to be explicitly non-constructive.

Perhaps a more pragmatic response, though, is that these "paradoxically computable languages" are simply an idiosyncrasy, that can (and have!) been studied at great length, like non-measurable sets of reals, but that once the initial surprise has been overcome, one can move on to more interesting things.


Do Kernel-Mode Windows Services Considered Part of Kernel?

Are kernel-level services considered as a part of the kernel?

That can be debated, but for me the answer is yes.

You might run into a purist who considers only the code from the manufacturer in the kernel to be part of the kernel and extensions as an add on the kernel. I would ask you instructor for his answer, you are the customer, right?

  If so , does writing kernel-mode services mean extending Operating System?

For me it surely does.

The easiest way to think of this is adding a device that requires installing a kernel mode device driver. Once the kernel mode device driver is installed all the code has access to the device driver in the same way all the code has access to the kernel. That is simplified but you should get the analogy.


Difference between graph-partitioning and graph-coarsening

They are different because... :

Graph Partitioning:

Giving a graph $G=(V,E)$, it is possible to partition $G$ into smaller components with specific properties.
e.g. the k-way graph partitioning is the problem to divide the vertex set $V$ into $k$ disjoint partition $P_1, P_2,...,P_k$ such that the number of the edges $e = (u,v) \in E, s.t. u \in P_i , v \in P_j, i \neq j $ is minimum.

Graph Coarsening:

Graph Coarsening is the first phase of a Multi-level Method, a method that partitions a graph applying one or more stage. Usually the first phase is the Graph Coarsening. This works by collapsing pairs of nodes and edges using a determinate criteria. Graph Coarsening takes as input a graph $G$ and gives as output a smaller graph $G^{'}$.
We use the Graph Coarsening because  the size of the graphs may be too big to be partitioned using well known algorithms (i.e. FM, KL) in an acceptable time.  e.g. METIS uses multi-level methods and, in this Coarsening Phase, merges pairs of nodes having a matching.

In your analysis you can use Graph Partitioning Software (METIS, Chaco, etc) in order to divide you graph and (for example) put each partition on a different node and doing distributed computing.


The counting principle that applies here is inclusion-exclusion.

$$ \left|X \cup Y\right| = \left|X\right| + \left|Y\right| - \left|X \cap Y \right|$$

To make the numbers work out, $\left|X \cap Y \right|$ must be 10000.

A Venn diagram may be more convincing to someone who may be intimidated by the notation.


Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints

One way which comes to mind is to use the fact that if $\sum_{a_i \in p_j} y_i > 1$ for some $j \in [m]$ then $x_j = 0$ and so the path $p_j$ is irrelevant. However, consider a graph with exponentially many paths in which the source has capacity 1 and all other vertices have capacity 2. The optimal solution is 1 and it is obtained by $y_s = 1$ and $y_v = 0$ for all $v \neq s$, and so all the inequalities considered above are tight. (For a "generic" graph, however, we can expect the optimal solution to be obtained at a vertex, and so have at most $n$ tight constraints.)

Another way is to notice that if the primal has an optimal solution then it has one which is a vertex, and so has at least $m$ tight inequalities. At least $m-n$ of them are of the type $x_j \geq 0$, and so there is an optimal solution using at most $n$ paths. However this is not helpful in the context of the exercise.


Can a node of Radix tree which represents a valid key have one child?

I've used patricia tries extensively, but haven't implemented a radix=2 patricia tree. (I generally used radix=256.)

  So my question is that whether "no parent with on child" rule is coined into the definition of radix tree

Not that I'm aware of. That sounds like an detail of a particular implementation.

Any time you have a valid key, you have a node. Any time you have a longer key that starts with that key, you have a child. So there will be lots of cases (on the order of some log function) of parents with one child, but those parents that have one child will imply a valid key in most implementations.

In your example, "smile" and "smiled" are two nodes, and "smiled" is a child of "smile". Both are valid keys. The "smile" node would have one child, "smiled".

Note that if a parent has only one child (e.g. after a node removal), and the parent does not represent a valid key, then the parent can combine itself with that one child. (That is an implementation choice.) So in your example, if we remove the key "smile", then we can either mark that node as "not holding a key any longer", or we can get rid of it, sliding the "smile" node up the tree.


Find a list of actions that result in desired state

It depends on what the rules are.  For your particular rules, this can be handled very simply by counting the number of events of each type seen in the given time window; then predictActions can easily compute the additional number of each type of action needed.


I can't access the paper itself, but judging by its abstract and a mention on p. 5 of this paper, a slight generalisation of your problem was proved NP-hard in 1978: Complete-Link Cluster Analysis by Graph Coloring (Pierre Hansen and Michel Delattre).  I say "slight generalisation" because (I assume that) the problem proved hard allows arbitrary distances between points; it's possible that Euclidean version of the problem, which you seem to have, is easier.  Maybe even the metric version is easier.

For the case of exactly 2 clusters, Wikipedia gives a poly-time algorithm based on 2SAT.


A Guess Turing Machine that accepts a random Binary number

There can't be "random numbers", each number is exactly that one, not at all "random". You can talk about getting a number at random from a set, perhaps according to some distribution. You might talk about a stream of bits, each of which is selected at random. But then the sequence 010101... is perfectly possible as an outcome (if it can't appear, it isn't random!).


Show that $(\log(n))^\alpha = O(n^\beta)$

You can use the following identities:
$$
(\ln n)^a \le n^\beta \iff \ln (\ln n)^a \le \ln n^\beta \iff
a \ln \ln n \le \beta \ln n.
$$
This is trivial if $\alpha \le 0$, so we consider the case $\alpha > 0$.
For simplicity substitute $t= \ln \ln n$ and $\gamma = \frac{\alpha}{\beta}$. Notice that $\gamma \ge 0$. We obtain:
$
\gamma t \le  e^t \iff \gamma t - e^t \le 0
$
To show that $\alpha t \le \beta e^t$ for sufficiently large $t$, we take the derivative of $h(t) = \gamma t - e^t$:
$$
h'(t) =\gamma - e^t.
$$
This shows that for $t \ge \ln \gamma$, $h(t)$ is monotonically non-increasing.
Moreover, for $t=\ln \gamma$ we already have $h(t) \le 0$, indeed $h(\ln \gamma) =\ln \gamma-\gamma \le 0$ since the logarithm is a monotonically increasing function.
Hence, in the definition of big-Oh with $n_0$ and $c$, we can pick $n_0 = \ln \gamma = \ln \frac{\alpha}{\beta}$ and $c=1$.


It seems that you are looking for a maximum matching in a graph where vertices represent people and an (undirected) edge $(u,v)$ means that $u$ and $v$ have not met before.
This problem can be solved in time $O(n^{1/2} \cdot m) = O(n^\frac{5}{3})$, where $n$ is the number of people and $m$ is the number of pairs of people that have not yet met.


What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic?

There is an answer in Graph Theory by Bondy and Murty:

It is clear that both graphs are isomorphic. Their respective duals are not, because each face of the first dual has degree 3  (except the unbounded one, of degree 5), and there are two faces of degree 4 in the second dual.


Designing CFG that accepts $b^m a^n$ ($m ≤ n$)

You can write this language as
$$
\{ a^k b^m a^m a^\ell a^k \mid k,m,\ell \in \mathbb{N} \}.
$$
This description easily lends itself to conversion into a context-free grammar.


Why addition algorithm is not pseudo- polynomial?

The reason is that the runtime of addition is proportional to the number of digits, not the value of the numbers, as it is for subset sum. Remember that the number of digits is the size of the input.


Why does taking advantage of locality matter in multithreaded systems?

Ask yourself: How long does it take to load data from memory, and how long does it take to stop one thread from running and start another thread? Starting another thread would usually take a lot longer, plus a new thread would have the exact same problem, having to wait for data to be ready.
An exception is hyperthreading cores. A hyperthreading core can officially run two threads simultaneously, but doesn’t actually have twice the processing power of a normal core, so it cannot actually perform twice as many instructions or anywhere near that. Such a core can however process operations of the second thread immediately when the first thread cannot proceed for any reason.
Now it’s debatable if hyperthreading is actually a win, especially since it gives hackers ways that operations in one thread can very subtly affect operations in another thread, leading to massive security problems. As a result, many high-performance ARM processors don’t implement hyperthreading at all.


Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?

If $optTSP$ is in $NP$, then $coNP = NP$.  The latter is unresolved currently.

Proof: if $optTSP$ is in $NP$, then $coTSP$ is in $coNP$ (the certificate being whatever certificate was provided to verify a solution to $optTSP$ was minimal, and then comparing the value of that solution to the desired bound). And because $TSP$ is $NP$-complete then this implies $NP = coNP$.


Difference between DNS Spoofing and DNS Hijacking?

One way of explaining the primary difference between DNS Spoofing and DNS Hijacking is given by this site as:

While DNS spoofing is often confused with DNS hijacking as both happen at the local system level, they are two different types of DNS attacks.
Most of the time, DNS spoofing or cache poisoning just involves overwriting your local DNS cache values with fake ones so you can be redirected to a malicious website.
On the other hand, DNS hijacking (also known as DNS redirection) often involves malware infections in order to hijack this important system service. In this case, the malware hosted on the local computer can alter the TCP/IP configurations so they can point to a malicious DNS server, one that will eventually redirect the traffic to a phishing website.

So, DNS spoofing is where some malware or something else changes values in your local DNS cache (on your PC, for example), with fake values so you would query and go to the wrong destination.
DNS hijacking, on the other hand, is not so much about attacking your local DNS cache, but something else like the TCP/IP configurations so your PC's pointer to DNS is diverted to a malicious DNS server that could redirect traffic to a malicious website.


Why does A* fail to find the fastest path when it reaches the goal?

Your misunderstanding is that A* doesn't return success until it pops a goal node, in your terminology.

So, in your example, when it pops $C$, it puts $D$ in the open list, with quite a high value. It then pops $B$ and puts $D$ in the open list again, with a lower value. So the first time that $D$ is popped will be from the route $A\to B\to D$, as it should be.


Fast ways to compute the smallest prime with a given substring?

This answer only shows that every string actually appears in some prime. Without loss of generality, $\omega$ doesn't start with zero (otherwise, consider $1\omega$ instead). Consider all digits in the range $\omega \times 10^N$ to $\omega \times 10^N + 9 (10^{N-1} + \cdots + 10^0)$, an interval of length $10^N$. Let $M = \omega \times 10^N$. According to the prime number theorem, there are roughly $(M+10^N)/\log M - M/\log M \approx 10^N/\log M$ prime numbers in this interval. Since $10^N/\log M \to \infty$, for large enough $M$ there will be a prime number in the interval, and its most significant digits would be exactly $\omega$.

I don't expect there to be an algorithm much faster than going over all primes in sequence. If you expect the answer to be one of the first few primes (here few can be a rather large number, say $10^9$), then you can probably do some preprocessing to be able to handle such queries fast.


How to find number of combinations of choosing one from k subsets

You can solve this problem with the inclusion exclusion principle.

Assume you have two subsets $S_1, S_2$, then the number of ways to choose two elements is the number of ways to choose a number from $S_1$ multiplied by the number of ways of choosing an element from $S_2$ minus the number of ways of choosing the same number from $S_1$ and $S_2$.

Now given three sets $S_1, S_2, S_3$, the number of ways of choosing one element from each such that all elements are different is
$$|S_1||S_2||S_3| - |S_1 \cap S_2| |S_3| - |S_1 \cap S_3||S-2| - |S_2 \cap S_3| |S_1| + |S_1 \cap S_2 \cap S_3|.$$

Now given a family of $k$ subsets, you can use the inclusion-exclusion principle to prove that the count can be given by the formula
$$
\prod\limits_{i \in [k]}|S_i| + \sum\limits_{I \subseteq [k], |I|\geq 2}(-1)^{|I|} \left|\bigcap\limits_{i \in I}S_i\right|\prod\limits_{i \notin I}|S_i|
$$


How can there be stop and wait protocol for a simplex channel?

Some writers use the term "simplex" to mean that communication is only possible in one direction. Others use it to mean that communication is possible in both directions but not at the same time; this is also called "half-duplex". I suspect that the protocol you're talking about is for a half-duplex channel: the sender transmits for a while and then pauses to allow the receiver to use the channel in the opposite direction for acknowledgments.


These are a different level classifications:
A method is a function (or procedure) associated with object – a concept from Object Oriented Programming.

A function is the logical unit (a piece of reusable code called by name) independent of any objects (those might not even exist in particular language). So the method is a function, but a function exists also in non-OO languages, so the reverse is not true.


All pair shortest path in a tripartite graph

Your problem is essentially $(\min,+)$ matrix multiplication, also known as tropical matrix multiplication. This is because you're computing
$$
C_{ik} = \min_j (A_{ij} + B_{jk}),
$$
which is the same formula as usual matrix multiplication, with $\min$ replacing sum and $+$ replacing product.

Usual fast matrix multiplication algorithms cannot be used for this task. Furthermore, the APSP hypothesis in fine-grained complexity states that there is no $O(n^{3-\epsilon})$ algorithm for APSP. Since APSP reduces to logarithmically many tropical matrix multiplications, this implies that the latter also has no $O(n^{3-\epsilon})$ algorithms.

On the other hand, some $n^{o(1)}$ factors can be shaved, so for example a paper of Ryan Williams, Faster all-pairs shortest paths via circuit complexity.


Inserting values at maximal distance from current value

Use an interval tree to store a set of intervals, where you have one interval for each chunk of contiguous 0's.  Now to figure out where to put the next 1, you need to find the longest interval in the interval tree.  You can keep track of the longest interval in the interval tree by augmenting the data structure: store in each node the length of the longest interval under that node.  Each operation can be done in $O(\log n)$ time.


Impact of Polynomial Time Algorithm for an NP Complete problem on Complexity Theory

If P=NP, then it follows that P=co-NP, and NP=NP-complete (i.e. there are no NP-intermediate problems, which are in NP but not NP-complete).

But there are plenty of other divisions in the hierarchy which might still hold, and might not. P=NP wouldn't necessarily tell us anything about this.

On the higher end of things, how does NP relate to PSPACE? It's entirely possible that they're the same (only if P=NP: if P≠NP, they're definitely different), in which case all the classes in the middle (such as PP, which uses a probabilistic Turing machine) are collapsed together too.

On the lower end, how does P relate to L (logarithmic space)? There are various classes between these ones too, such as NL (nondeterministic log space), and these might all be collapsed into a single class also.


How to Find the minimum permanent which is pumping lemma for language context-free?

I presume by "permanent" you mean the integer of the Pumping Lemma, that is the integer $p>0$ such that for any string $s$ in the language with length $p$ or greater we can express $s=uvxyz$ with . . . [blah blah blah, I'm not going to write the statement here].
If you've read the proof of the PL, you know that it relies on guaranteeing that in a parse tree for a string of sufficient length, there will always be some path from the root to a leaf which contains a repeated variable. When that happens, we can replace the subtree rooted at the "lower" repeated variable with a copy of the subtree rooted at the "upper" repeated variable and have a parse tree for a new string also in the language: i.e., you've pumped the string.
For the grammar you've given, it is particularly easy to find the shortest strings in the language with a repeated variable in a path from the root to a leaf. Here are the trees for the shortest such strings:

There are two other of the right-hand form, but because of the way your grammar is formed, any string of length greater than or equal to 3 generated by the grammar must be formed by extending one of these two. In other words, the integer of the pumping lemma can be 3 or greater. It can't be 1 or 2, since while the strings $1$ and $11$ are in the language, there are no repeated variables in their parse trees (meaning they can't be pumped). Finally, then, the integer you want is 3.


We typically analyze algorithms in the so-called "RAM machine" or "transdichotomous model". In this model, operations on machine words take $O(1)$, and a machine word has length $O(\log n)$ bits, where $n$ is the size of the input (in bits), or any other polynomially related quantity.
If $R$ is polynomial in $n$ (in this case, the length of the array), then an integer in the range $\{1,\ldots,R\}$ can be stored in a single machine word, and so operations on such integers take constant time in this model.


Selection of pivot in quicksort partitioning of Hoare and Lomuto

As you now correctly, every arbitrary but fixed choice of pivot is equally bad; the cases are symmetric.

The difference is probably historical and may not exist in all write-ups of the algorithms.

Note that you have to change the for-loops if you switch from hi to lo or the other way around, but that is not a conceptual difference.


Similarly structured loops with different big-O time complexities?

In the second algorithm, the total number of increment operations would be $$\sum_{i=0}^{\lceil\lg n\rceil } \frac{n}{2^i}$$, which is $\leq 2n$. See this Wikipedia article about infinit geometric series and the inequallity should be clearer.


If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?

Assume that $L$ contains two words $w_1$ and $w_2$ such that the lengths of these words, $|w_1|$ and $|w_2|$, have no factors in common. Then, we have that the longest word that cannot be formed by concatenating these words has length $(|w_1|-1)(|w_2|-1) - 1$ (Frobenius number). That is to say, if there are words in the language whose lengths don't have a common factor, then all words of a certain minimal length are in the language $L^*$. It's easy to see this is regular since, of necessity, there are a finite number of equivalence classes under the Myhill-Nerode indistinguishability relation.

What if the lengths of all words in $L$ share a common factor? Well, It's not hard to see that in such cases, $L^*$ is also regular. Simply note that instead of all words whose lengths are greater than some minimal length being in $L^*$, it will instead be true that all words whose lengths are a multiple of the GCD of word lengths will be in $L^*$, and no words whose lengths aren't multiples of this GCD will be, and since $(L^k)^*$ is regular for any integer $k$, $L^*$ is also regular.

This is pretty informal, but everything you need to formalize this should be here.


Simplest Turing-complete ruleset for Markov algorithm

Rule 110 is universal, and can be expressed as a Markov algorithm.

In particular, Rule 110 corresponds to the Markov system with alphabet $\{0,1,\verb!^!,|,\$ \}$ and a pair of bits for each element in the automaton. The pair of bits records the current status of that element (empty or filled) and the previous status.  Elements are updated by doing a left-to-right scan; the marker $|$ keeps track of where we are in the scan, $\verb!^!$ indicates the start of the string, and $\$$ indicates the end of the string.  We obtain the following $2^6 + 2^2 + 2^6 = 132$ rewriting rules:

$uv|wxyz \to uvxt|yz$ where $t = \text{Rule110}(u,x,z)$,
$|uv\$  \to vv\$ $
$\verb!^! uvwxyz \to \verb!^! vv|wxyz$

where $u,v,w,x,y,z$ are meta-variables that range over $\{0,1\}$.  In other words, the first bullet item corresponds to $2^6$ rewriting rules: $00|0000 \to 0000|00$, $00|0001 \to 0001|01$, etc.; the second bullet item corresponds to $4$ rewriting rules, corresponding to all possible ways to assign $0$ or $1$ to $u$ and $v$; and the third bullet item corresponds to $2^6$ more rewriting rules.

What's going on with this crazy re-writing system?  It's actually not as ridiculous as it looks.  For a cellular automaton with $n$ elements, we start with a string of length $2n+2$ of the form $\verb!^! 0x_1 0x_2 0x_3 \dots 0x_n \$ $, where each $x_i$ is $0$ or $1$ according to whether that element is empty or filled.

The interpretation of the pair of symbols $uv$ is that the current status of the element is given by $v$, and the previous status is given by $u$.  We scan over the elements from left to right, updating the status of each element.  The marker $|$ indicates where we are in the scan right now.  Notice that we need to keep track of both the previous and current state of each element, which is why I use a pair of bits for each element rather than one bit per element.

The first bullet item takes care of the left-to-right scan.  The second bullet item makes sure that the scan terminates, and removes the $|$ marker.  The third bullet item ensures that if there is no $|$, then we re-start the scan starting at the left.

You can also play a similar trick with any Turing machine, and thus emulate a universal Turing machine with a Markov algorithm.

Suppose we have a Turing machine with tape alphabet $\Gamma$ and finite state space $Q$.  Then the Markov system has alphabet $\Sigma = \Gamma \cup Q \cup \{\text{<}\}$.  The idea is that the string $t_1 t_2 \cdots t_i \text{<} q t_{i+1} \cdots t_n$ corresponds to a configuration of the Turing machine that has $t_1 t_2 \cdots t_i t_{i+1} \cdots t_n$ on its tape, has state $q$ in its finite-state control, and where the head is positioned over $t_i$ in the tape.  The marker $\text{<}$ indicates the current position of the head.

Then it's easy to write a finite set of rewriting rules that correspond to the operation of the Turing machine.  In particular, the behavior of the Turing machine depends only on the symbol under the head and the state of the finite control.  Thus, we'll get a set of rewriting rules of the form $t \text{<} q u \to t' u \text{<} q'$ (for transitions where the head moves right) and $s t \text{<} q \to s \text{<} q' t'$ (for transitions where the head moves left).  Since the finite-state control has only finitely many state transitions, we'll need only finitely many rewriting rules in the Markov algorithm.

Finally, we can apply this to your favorite universal Turing machine.  The smaller the universal Turing machine, the simpler the resulting Markov algorithm will be.


You have to interpolate the missing heat values. There's some mathematics that explains this pretty well (man, it's been a while) but, if I recall correctly, the correct physical way to do this (assuming no heat sources in the area being interpolated) is the following:

For each pixel for which there wasn't original data, assign the value of the pixel to the average value of all surrounding pixels.
Repeat (1) until no pixel changes its value by at least some $\epsilon$

To be safe, you should probably double-buffer this process, so that while doing the first step, changing the value of the first pixel doesn't affect the value for the second pixel. Example:

   5.0 4.0 4.0 3.0    5.0 4.0 4.0 3.0    5.0 4.0 4.0 3.0    5.0 4.0 4.0 3.0
   2.0 --- --- 1.0    2.0 3.0 2.5 1.0    2.0 2.6 2.6 1.0    2.0 2.8 2.5 1.0
   1.0 --- --- 3.0 => 1.0 2.0 2.5 3.0 => 1.0 2.4 2.4 3.0 => 1.0 2.3 2.5 3.0
   3.0 3.0 2.0 4.0    3.0 3.0 2.0 4.0    3.0 3.0 2.0 4.0    3.0 3.0 2.0 4.0

=> 5.0 4.0 4.0 3.0
   2.0 2.7 2.6 1.0
   1.0 2.3 2.5 3.0 ...
   3.0 3.0 2.0 4.0

Already the values are beginning to settle down a bit. This is easy and fast to automate, though naturally, you'll only get an approximation. See here and here for more information on the physics and mathematics behind this (and whether this is even applicable to your situation!!!)


Need a polynomial time reduction from 3SAT to INDEPENDENT-SET

The simplest is to reduce Clique to Independent Set using the complement graph, as discussed in the comments.

Alternatively, you can construct a graph to directly reduce 3SAT to Independent Set using "gadgets". One possible start is to do the following: for each clause, construct one node for each of the three variables in the clause. Now, we want to place edges such that:

No two variables in the same clause can be members of the same independent set.
No two variables which are the negations of each other can be members of the same independent set.

If you can accomplish this, then for a boolean formula with $m$ clauses, there is an independent set of size $m$ in your constructed graph if and only if the boolean formula is satisfiable, thus giving the desired reduction.


Loop invariant: decreasing a variable and swapping it

There isn't a single loop invariant: any property that remains true during the execution of the loop is a loop invariant. For example, “I am not the Pope” is an invariant of this loop, but it is not a useful one. A useful loop invariant is one that helps in proving some property of the program.

Here, presumably, the ultimate point of the exercise is to determine the return value of the function (as a function of the arguments a and b). The only way this function can return is on normal exit of the while loop, returning a in a state of the program where the condition a >= 0 and b >= 0 is false.

The property a >= b isn't likely to be relevant because it's neither true at the start of the function nor when the function returns.

Given the objective to figure out the value of a when the loop exits, it is useful to look at what happens in the last iteration of the loop. We know that a >= 0 and b >= 0 is true on entry to the function, so there will be at least one loop iteration. Let $a'$ and $b'$ be the values of a and b at the start of the last iteration, and $a''$ and $b''$ the values at the end. We know from the loop condition that $a' \ge 0$, $b' \ge 0$, and $a'' \lt 0 \vee b'' \lt 0$. This can only happen when the else branch is taken. Therefore $a'' = a' - 1$ and $b'' = b'$. Plugging these equalities into the inequalities we had, we get that $b'' \ge 0$ so $a'' \lt 0$ and also $a'' \ge -1$.

It appears that b >= 0 and a >= -1 are two invariants of the loop — they're true on entry and they're true on return. Furthermore, if the initial values of a and b are integers, the property “a and b are integers” are also loop invariants. If a and b are integers, then the only possible value for $a''$ given the inequalities above is $-1$, so this function can only return the value $-1$.

Follow-up exercices:

If a and b aren't constrained to be integers, what does the function return? You'll need to find another invariant to determine the value of $a''$.
If a and b are nonnegative integers, I've proved that this function can only return the value -1. I haven't proved that this function is equivalent to return -1, however: it might also loop infinitely. Prove that (given the precondition that the arguments are non-negative) the function always terminates.


Difference between order of convergence and order of consistency?

A quick and dirty answer: by definition.

Let's use the definition from Wikipedia.
Let $\delta^h_{n+k}$ be the local error.
A method has order $\textbf{p}$ if
$$\delta^h_{n+k} = O(h^{\textbf{p+1}}) \text{ as } h \to 0.$$

Notice $p$ and $p+1$ in the definition. Since the explicit Euler method has local error of order $O(h^2)$, $p+1 = 2$, hence $p = 1$.

On the other side, if you want to know the reason behind such definition, then I think it is about showing you the part of the solution's Taylor polynomial which the method reproduces correctly (by giving you the degree of the last correct term).


Amortized analysis - increment in ternary counter

The amortized cost per increment will be $O(1)$. In order to show it let's use the aggregate method.

0  - 000
1  - 001
2  - 002
3  - 010
4  - 011
5  - 012
6  - 020
7  - 021
8  - 022
9  - 100
10 - 101
11 - 102
12 - 110
13 - 111
14 - 112
15 - 120
...

We can notice that the bits in the 0th place are changing in every increment operation ($3^0$). The bits in the 1th are changing in every 3th increment operation ($3^1$). The bits in the 2th place are changing in every 9th increment operation ($3^2$). And so on.

The total number of changes equals to the sum of times that every bit has changed. Let's assume $n\lt 3^{k+1}$ for some $k$.
So the total number of changes in $n$ increments is no more than
$$n+\frac n3+\frac n9+\frac n{3^3}+....+\frac n{3^k} < \frac32n$$
Assuming it takes $O(1)$ to perform the change of one bit and the associated bookkeeping, the total cost of the sequence is $O(n)$.
So the amortized cost per operation is $O(n)/n= O(1).$


Prove that every two longest paths have at least one vertex in common

Assume for contradiction that $P_{1} = \langle v_{0},\ldots,v_{k}\rangle$ and $P_{2} = \langle u_{0},\ldots,u_{k}\rangle$ are two paths in $G$ of length $k$ with no shared vertices.

As $G$ is connected, there is a path $P'$ connecting $v_{i}$ to $u_{j}$ for some $i,j \in [1,k]$ such that $P'$ shares no vertices with $P_{1} \cup P_{2}$ other than $v_{i}$ and $u_{j}$. Say $P' = \langle v_{i},x_{0},\ldots,x_{b},u_{j}\rangle$ (note that there may be no $x_{i}$ vertices, i.e., $b$ may be $0$ - the notation is a bit deficient though).

Without loss of generality we may assume that $i,j \geq \lceil\frac{k}{2}\rceil$ (we can always reverse the numbering). Then we can construct a new path $P^{*} = \langle v_{0},\ldots,v_{i},x_{1},\ldots,x_{b},u_{j},\ldots,u_{0}\rangle$ (by going along $P_{1}$ to $v_{i}$, then across the bridge formed by $P'$ to $u_{j}$, then along $P_{2}$ to $u_{0}$).

Obviously $P^{*}$ has length at least $k+1$, but this contradicts the assumption that $G$ has no paths of length greater than $k$.

So then any two paths of length $k$ must intersect at at least one vertex and your observation that it must be in the middle (if there's only one) follows as you reasoned.


How strong "Consistent Guessing Problem" is?

Andy Drucker, in a comment (with follow-up) to Scott Aaronson's blog post, shows that

  HALT does not reduce to Consistent Guessing (CG).

Here is his proof (copied verbatim), which uses diagonalization:

  We’ll build a language $L$ that’s a solution (i.e., refinement) of CG. On stage $i$ we’ll try to set finitely many bits of $L$ so as to ensure that the $i$th machine $M_i$ doesn’t solve HALT when given oracle access to $L$.

  If this works, then we’re done! So assume for contradiction’s sake that we get stuck on some stage $i$. We’re going to use this premise to solve HALT — without an oracle. This absurdity will prove the result.

  So — say we’re stuck at stage $i$, and we have some finite setting $L[i]$ to some of the bits of $L$, consistent with CG.

  Let $L^*$ be $L[i]$ augmented with all of the bits ‘forced’ by CG: i.e., $L^*(M) = 0$ whenever $M$ halts with output $0$, and similarly for $1$. So, $L^*(M)$ still is undefined for all but finitely many of the machines $M$ that run forever.

  Now, for each input $M$ to $M_i$, by our assumption we have that

  $$ M_i^{L’}(M) = HALT(M) $$

  whenever $L’$ is an extension of $L^*$. An application of König’s lemma tells us that for each $M$ there is a number $n = n(M)$ such that any extension of $L^*$ with arbitrary values up through input lengths $n$, causes $M_i(M)$ to output $HALT(M)$.

  So, here’s how we can determine the value $HALT(M)$: we dovetail simulations of all Turing machines. On stage $j$ we simulate the first $j$ machines for $j$ steps each. Whenever a machine halts with output ($0$ or $1$), we extend our finite approximation of $L^*$. (This approximation begins with the finitely many values of $L[i]$, hard-coded into the algorithm). Let $L^*[j]$ be the finite approximation to $L^*$ on the $j$th stage.

  On the second part of stage $j$, we simulate $M_i(M)$ on all extensions of $L^*[j]$ up to length $j$. That is, we take the values we have so far, and we try extending them in all possible ways.
  We then simulate $M_i(M)$ on all of these extensions as oracle, for $j$ steps each. If on all such simulations, the machine halts with some output $b$, without ever trying to access an undefined oracle bit, then we output “$HALT(M) = b$”.

  The claim is, this always halts with the right answer. Using our earlier analysis with König’s lemma (and the fact that $L^*[j]$ converges to $L^*$), we find that for large enough $j$, we will output the correct bit, if we reach stage $j$.

  So we just need to argue that we never output a wrong bit earlier. But this is easy: at every stage $j$, at least one of our simulations is an initial segment of a correct simulation of $M_i(M)$ on a valid CG oracle. Thus that simulation always either halts with the correct output, or doesn’t halt, or tries to access an undefined oracle bit. So we never get a unanimous incorrect vote.


Turing machine algorithms for $\{0^n1^n\}$ using one and two tapes

If you are allowed an auxiliary tape, then the algorithm is very simple:

Scan to the end of the input, while checking that the input belongs to $0^*1^*$.
Copy the input in reverse to the auxiliary tape, switching 0s and 1s.
Check that both tapes contain the same word.

If the input is $0^a 1^b$ then the second tape will contain $0^b 1^a$, so the algorithm will accept if and only if $a = b$. It clearly runs in linear time.

If you only have one tape, then the algorithm is more subtle. We scan the input from left-to-right, maintaining a counter just left of the current symbol being scanned. At each step, we do as follows:

Read the next symbol $\sigma$ and remember it.
Copy the counter one step to the right; this step takes $O(\log n)$ time.
Either increment the counter (if $\sigma = 0$) or decrement it (if $\sigma = 1$).

At the end, we accept if the input belongs to $0^*1^*$, and additionally the counter has the value zero.

Using crossing sequences, you should be able to show a matching $\Omega(n \log n)$ lower bound for one-tape Turing machines. The idea is to consider the set of inputs $0^m1^m,\ldots,0^{2m}1^{2m}$, and to consider the states that the Turing machine is when it crosses the window between the $m$th and $2m$th position. There must be $m+1$ different crossing sequences, hence there must exist a crossing sequence of length $\log m$, which corresponds to a running time of $\Omega(m\log m) = \Omega(n\log n)$.


Efficiently finding the min-cost path of an AVL tree

Searching in an AVL tree is anyways only at most O(log n) (see on @Wikipedia: https://en.wikipedia.org/wiki/AVL_tree?wprov=sfta1). If you do not care about the higher cost of rebalancing AVL tree instead of BSTree, this tree will have even the advantage of always maintaining the AVL-min-cost path on the left edge. Search the left edge has also O(log n) so no cheaper than other trees. Balancing a tree is only nesessary if building a tree can cause massive imbalance,  only than AVL has a marginal advantage above BST.

To your counter example on AVL tree with a not-left-edge min-cost: This is to my quick grasp the furthest imbalance one can find before need of rebalancing of AVL is needed. Hence no need to worry about finding the minimum cost path in AVL tree may be more difficult due to tree depth. So searching the minimum path within the left and not totally left path is O(log n +1) equaling O(log n). So it is basically not harder to find the actual minimum path than finding the obvious left edge.


Behavior of iterative application of LZ77

Lempel and Ziv proved that under some reasonable assumptions, the limiting rate of their algorithm is equal to the entropy of the text. That means that in the limit, the output should be completely random. Random text cannot be compressed (on average), so you should expect that if you take a long text and apply Lempel-Ziv twice, then the second time wouldn't compress the text at all.


Does it hold that $F \equiv \sigma(F)$ for a CNF formula $F$ and a permutation $\sigma$ s.t. $F \vDash \sigma(F)$?

The crucial observation is that if $A \vDash B$ then also $\sigma(A) \vDash \sigma(B)$. This follows since all $\sigma$ does is rename variables and flip some variables. For example, if $\sigma(x) = \lnot y$, $\sigma(y) = z$, and $\sigma(z) = x$, then $A(x,y,z) \vDash B(x,y,z)$ implies also $A(\lnot y, z, x) \vDash B(\lnot y, z, x)$.

Let $G$ be the set of all permutations of literals satisfying your condition. I claim that $G$ forms a group with respect to composition. Since $G$ is finite and composition is associative, it suffices to check that it is closed under composition. Indeed, if $\sigma(\lnot x) = \lnot \sigma(x)$ and $\tau(\lnot x) = \lnot \tau(x)$ then $\sigma(\tau(\lnot x)) = \sigma(\lnot\tau(x)) = \lnot\sigma(\tau(x))$.

Since $G$ is a group, $\sigma^{|G|}$ is the identity. If $F \vDash \sigma(F)$ then, applying $\sigma$ on both sides, we get $\sigma(F) \vDash \sigma^2(F)$. More generally, we get $\sigma^n(F) \vDash \sigma^{n+1}(F)$, and so $\sigma^n(F) \vDash \sigma^m(F)$ whenever $m \geq n$. In particular, choosing $n = 1$ and $m = |G|$, we obtain $\sigma(F) \vDash F$.

The group $G$ is known as the signed symmetric group, denoted $B_n$, where $n$ is the number of variables.


Taking the transpose and using the list based on finishing time both together ensure that if you have edge A->B(in original graph) where A and B are simply connected sub-graphs than in second dfs A would have finished before start of B(See that in transposed graph edge is from B->A). If we do not take transpose then this is not ensured.

Example:

1->2

2->3

3->4

4->2

3->5

dfs(decreasing finishing time finishing times):1,2,3,5,4
Now if you start from 4 you will visit 5 through 4->2->3->5. But 4 and 5 are not simply connected.

For the second part you may or may not get reversed arrays depending on the order of supplying vertices.


Here's what goes on; there are three different cases:

If $x<y$, you pass from $(x,y,z)$ to $(x+1, y, z)$ and add 1 to the eventually returned result.
If $x\ge y$ and $y<z$, you pass from $(x,y,z)$ to $(x,y+1, z)$ and add 2 to the result.
If $x\ge y$ and $y\ge z$ you return z (plus all the additions you made in cases (1) and (2).

Suppose, for simplicity's sake, we start with $(2,4,6)$. First, we're in case (1), so we pass from $(2,4,6)$ to $(3,4,6)$ and add 1. We then pass to $(4,4,6)$, adding another 1 and pass to case (2). In general, we'll add $1\cdot(y-x)$ in this case.

Now we alternate between case (2) and case (1). In this example, we'll go from $(4,4,6)$ to $(4, 5,6)$ (case 2) and add 2 and then from $(4,5,6)$ (case 1), add 1, and go to $(5,5,6)$, so we've gone from $(4,4,6)$ to $(5,5,6)$ and added 3. Another case (2), case (1) will get us to $(6,6,6)$ In general, we'll add $3\cdot(z-y)$ in this case.

Finally, we arrive at $(6,6,6)$ and find ourselves in case (3) where we return 6 plus the adds we made earlier, namely 2 to get from $(2,4,6)$ to $(4,4,6)$, 6 more to get from $(4,4,6)$ to $(6,6,6)$ for a grand total of $f(2,4,6)=2+6+6=14$.

In general, when $x\le y\le z$ we'll have
$$
f(x,y,z)=1\cdot(y-x)+3\cdot(z-y)+z=4z-2y-x
$$

It's not hard to establish similar results in the cases where $x,y,z$ aren't sorted in increasing order.

[By the way, $f(12,14,20)=4\cdot20-2\cdot14-12=80-28-12=40$.]


If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$

In fact, if $L$ is context-free then so is $L^*$. The easiest way to see that is using context-free grammar. Every context-free language $L$ is generated by some context-free grammar $G$ with starting symbol $S$. Now add a new starting symbol $S'$ and the productions $S' \to S'S|\epsilon$. The new grammar $G'$ is also context-free and generates $L^*$.


Static access pattern in Distributed Databases

I found what you copied in the following text

The idea is that users access (querying, updating or etc ..) of the database changes with time. It may be at its peaks in sale seasons for example if the database belongs to a commercial applications. etc .. - if it is always fixed and predicted then it is static.

From your copied text: it says that: "it is difficult to find many real-life distributed applications that would be classified as static. The significant question, then, is not whether a system is static or dynamic, but how dynamic it is." --

perhaps, a static access pattern is a collection of sensor nodes that update the database with their readings in a periodic time, with equal size updates always. -- or a set of servers that get a synchronization clock in a periodic manner  (quite theoritical i guess)


It is my very personal opinion that the book of Jon Kleinberg and Éva Tardos is the best book for studying the design and analysis of efficient algorithms. It might be not as comprehensive as Cormen et al. but it is a great textbook. Let me point out, why I think this book might suit your interests best

you don't need heavy math machinery for the proofs
the book gives often a great intuition why something is working (or not), this is in my opinion very important for beginners and self learners
a very intuitive approach to NP-completeness
it has a great chapter how to deal with NP-complete problems in practice
it focuses on design patterns, which might help you to design your own clever algorithms

You should also notice, that there is a lot of free material in the WWW available. Great lecture notes are provided by Jeff Erickson. And you can even watch the whole MIT class on "Introductions to algorithms" taught by Charles Leiserson and Erik D. Demaine. Cool stuff!


What is the state of the art in efficient boolean function operations?

The obvious method is to use BDDs.

Given a BDD for two boolean functions $f,g$, you can form a BDD for $f \land g$, $f \lor g$, $\neg f$, $f \implies g$, $f \oplus g$ (xor), and many other binary operations on them.  Also, given BDDs for $f,g$, you can test whether $f$ and $g$ are the same boolean function.

The worst-case behavior is that their size might grow to be exponential in $n$, the number of boolean variables, but empirically, the size often remains manageable in many real-world applications, e.g., when there is suitable structure in the underlying boolean functions.  In the model-checking world, designs with 50-200 boolean variables are routinely handled using BDDs.

It's also possible to manipulate boolean expressions in symbolic form, and then use SAT solvers or SMT solvers to test for equivalence.  This is another plausible alternative.

My advice is: try BDDs first, then if they don't scale well enough for your needs, you can try SAT-based solutions.  If that still doesn't work, come back to ask for more suggestions (providing more details about your specific setting and what you've tried).


Given many partial orders, check them for consistency and report any that are not consistent

This sounds like weighted FAS (Feedback Arc Set).  Find a minimal (weight) feedback arc set in a directed graph and report the assertions that contributed to the wrongly directed arcs.

For each pair of symbols s and t, there is an arc saying how many assertions have s < t and how many assertions have t < s.

This is a known NP-complete problem.

On a different note, your problem is a classic social choice problem where each of the "assertions" are votes.


Fastest way to find the smallest interval of a number

The relevant phrase is  "predecessor search" .

For that, you can dynamically choose whether-or-not equality is allowed by

for each number in the range, storing 2 times that number rather than that number directly
and
for each actual query q, submitting  (2*q) ± 1  instead of q,

where the sign depends on whether you want to allow equality
and
dividing by 2 before returning

.

With that, the greater one can be found using predecessor search in the negatives of

the actual numbers.    For your case, you could simply reverse the range, like storing

10000-23,10000-1456,10000-280,10000-3586  rather than  23,1456,280,3586 .

Page 6 of this pdf gives upper bounds for dynamic predecessor searching

and references for data structures achieving those bounds.

This pdf gives another data structure which does what you want and much more.


How can I model overlapping service times in queueing model?

That's not in series.  If their times are overlapping, they're not in series.

You mentioned that in your particular example, the latency is $t_1 + t_2 - \min(t_1,t_2)$.  This quantity can be more cleanly expressed as $\max(t_1,t_2)$.

As a result, your queries are certainly not in series -- on the contrary, they are in parallel.  And, there are clean and simple ways to model two queues in parallel.

In particular, assuming the queue times are independent and letting $t=\max(t_1,t_2)$, we have

$$\Pr[t \le x] = \Pr[t_1 \le x] \times \Pr[t_2 \le x].$$

Thus, the cumulative distribution function (CDF) for $t$ is the product of the CDF's for $t_1,t_2$.  The CDF for a single queue is easy to compute given standard properties of the queue (e.g., it's easy to compute the CDF from the PDF).


This hash function is very similar to a linear congruential generator, a type of naive pseudorandom number generator. By now there are much better hash functions out there, and I suggest not using this one.


There is Otsu method to use variance when splitting.

Taking your own steps you should convert RGB to grayscale (simple mean like $(R+G+B)/3$, or use luminance grayscale).

The next step is to give some threshold, from Otsu or arbitrary given by your choice, and operating on grayscale image everything below (or equal) is 0, so it will be black, and greater than threshold is 1 (white).

Operations on other scheme like HSL is exactly taking luminance, but the full change RGB -> HSL is not needed because you discard color info.

Situation when values are out of range does not occur, so do not worry.


This is best explained in the base 10 equivalent: scientific notation

In scientific notation you have a mantissa and a exponent such that the value is $\mathrm{mantissa} \cdot 10^{\mathrm{exponent}}$.

In a computer floating point the mantissa is always the same size of significant digits (a double precision has around 16 digits) and the exponent is bounded.

Let's take a arbitrary format for our examples: a 4 digit mantissa and a 1 digit exponent

1 is then represented by $1.000 \cdot 10 ^ 0$
the maximum value you can represent is $9.999 \cdot 10 ^ 9$
the minimum absolute value you can represent in a normalized fashion (first digit is not 0) is $1.000 \cdot 10 ^ {-9}$
$2\,147\,483\,648$ is most closely represented by $2.147 \cdot 10 ^ 9$ (note that this is actually $2\,147\,000\,000$)

Here you'll see that to represent that large number there is an absolute error of $483\,648$ or a relative error of $0.0002$.

A denormalized value would be when the first digit is 0 like with $0.001 \cdot 10 ^ {-9}$, here it isn't that significant but in binary the first digit of the mantissa is assumed to be $1$. So that first bullet point is false, denormalised is all values in $(0,B^{\mathrm{minExp}}) $and $(-B^{\mathrm{minExp}},0)$.

Our machine epsilon here is $0.001$ (going from 1 to the next representable value 1.001).

So for numbers with exponent $0$ there is an accuracy of $0.001$, while for numbers with exponent 5 there is a accuracy of $100$.


Calculating the number of assignments satisfying a general propositional formula

As I have mentioned in the comments, being able to determine the number of truth assignments of a generic formula in polynomial time would imply not only $\textbf{P} = \textbf{NP}$ but actually the much, much stronger $\textbf{#P} = \textbf{P}$ (see Yuval Filmus' answer).

What Papadimitriou really means in this context is that the number of truth assignments of each $\phi_i$ depends on the value of only $k$ variables, with $k$ being constant with respect to $n$. Thus, determining the number of truth assignments can be done in constant time (relative to $n$, not to $k$; for a more precise runtime bound, see again Yuval Filmus' answer).

For reference, here is the earlier paragraph from the text (emphasis mine):

  In this problem we are given a set of Boolean expressions $\Phi = \{ \phi_1 , ... , \phi_m \}$ in $n$ variables, where each [...] is a general Boolean expression involving at most $k$ of the $n$ Boolean variables, where $k > 0$ is a fixed constant [...]


Is order of bits in byte really not of concern?

Bytes are transferred from memory to disk using an I/O protocol (e.g. SCSI) that specifies the bit order of transmission in the case of a serial protocol, or for parallel protocols specifies which pin upon which each bit in a byte should be transmitted. For bytes moved from memory over the network, the network link level protocol (e.g. Ethernet) specifies the bit order.  In either instance, an application programmer need not concern herself with the details; the operating system in concert with disk or network controllers will maintain the correct bit order end-to-end so that the correct values are transmitted/received or store/retrieved.

N.B.: byte order is another matter altogether.


Reduce Vertex Cover with size k to Vertex Cover with size n/2

For $k<n/2$, add an isolated complete graph with $n-2k+2$ vertices (note it takes at least $m=n-2k+1$ vertices to cover this complete graph). Now there is a vertex cover of size $(n+(n-2k+2))/2=n-k+1$ in the new graph iff there is a vertex cover of size $(n-k+1)-m=k$ in the old graph.

For $k>n/2$, add $2k-n$ isolated vertices. Now there is a vertex cover of size $(n+(2k-n))/2=k$ in the new graph iff there is a vertex cover of size $k$ in the old graph.


How to prevent deletion in an array in the B method

You cannot add such a property to your invariant because the invariant describes how a valid state might look like but not how it can be altered.

The operations are responsible for specifying the behaviour of the model. If you want to prevent that an element will be removed from the array, just do not specify that as a possible behaviour. In your example above, just remove the operation remove.

Every valid refinement is then not allowed to remove an element.


Is there a PDA for every Type 3 Grammar?

You need to check the definitions: type-3 (regular) is a (proper) subset of type-2 (context-free). Therewith, every type-3 language has a PDA that accepts it.

Essentially, you take a finite automaton for your type-3 language, add the stack but never use it. Up to minor definitory differences (e.g. w.r.t. acceptance), this gives you a PDA for the language. This is also one way to prove that all regular languages are context-free!


Are there any functions with Big O (Busy Beaver(n))?

The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of $\Theta(\mathit{BB}(n))$, or indeed $\Omega(\mathit{BB}(n))$. Indeed, such an algorithm could be used to solve the halting problem (assuming you knew a constant $c>0$ such that the running time is at least $c\mathit{BB}(n)$), since you could use the algorithm to get an upper bound on $\mathit{BB}(n)$.
On the other hand, any algorithm has a running time of $O(\mathit{BB}(n))$, precisely because the busy beaver function grows faster than any computable function.


What does it mean to have tokens at a state in a balancing network?

It seems that there is a typo – $s$ and $B$ represent the same thing. It looks like the original $s$ was changed to $B$, but the author of the question forgot to delete $s$.

The state of the network is the state of all balancers – which way they point.


"...asking myself daily when I would use these concepts in my daily life as a developer." The answer depends on the job. It sounds like you don't like math/theory, so you would not apply for/ get a job that requires a deeper understanding of CS, as many higher-level jobs do.

However, the truth is that the vast majority of software engineering jobs requires very little math or theoretical computer science, or even a good understanding in computer systems (which you didn't mention). If you just want to write code for websites or applications or do front-end, you can do that just fine without knowing most of the topics taught in a CS curriculum. Most of this knowledge is simply uneccessary, although having a degree will certainly help you get a job. However I know people who went into the software engineering profession with degrees in journalism or theater or other completely unrelated fields.

Also, there are some colleges that offer a degree in Software Engineering, which is much more focused on the practical side, including software development cycles and practices.

This is all practical advice. As for what Computer Science is, there is probably no universally accepted answer. It's a broad field, with many different sub-fields. However, most people would probably not consider simple software programming as Computer Science.


Number of integers in a certain range with certain properties

Hint: Decompose the range $[1,x]$ into more manageable ranges of the form $[N\cdot 10^{k+1},N\cdot 10^{k+1} + d \cdot 10^k)$, where $d < 10$. Enumerate over the "popular" digit, and use inclusion-exclusion.


Composition of combinators with arities greater than one

One methodical way of accomplishing this is to construct a corresponding lambda term and to then convert it to a CL term using pseudoabstraction.

First some definitions. You want to compose two combinators $A$ and $B$ with arities $p$ and $q$, respectively. Let $C^\lambda_{p,q}$ represent the lambda term accomplishing this.

$C^\lambda_{p,q}$  must first accept $A$, then $B$, then the $q$ arguments $b_1,\ldots,b_q$ of $B$, and then $p-1$ remaining arguments $a_1, \ldots, a_{p-1}$ of $A$ (note: '$p-1$' because the argument $B(b_1\ldots b_q)$ has already been accepted). So $C^\lambda_{p,q}$ must accept $ p + q + 1$ arguments in total, and it must satisfy:

$$C^\lambda_{p,q} A B b_1 \ldots b_qa_1\ldots a_{p-1} \rhd_\beta A(Bb_1\ldots b_q)a_1 \ldots a_{p-1}$$

This easily works for:

$$C^\lambda_{p,q} \equiv \lambda xyb_1 \ldots b_q a_1 \ldots a_{p-1}.x(yb_1 \ldots b_q)a_1 \ldots a_{p-1}$$

So in your example with $p = 4$ and $q = 2$, we get:

$$C^\lambda_{4,2} \equiv \lambda xyb_1b_2 a_1 a_2 a_3.x(yb_1 b_2)a_1 a_2 a_3 $$

Now for the conversion. To this end we introduce the notion of pseudo-abstraction, as defined below by Hindley & Seldin in Lambda-calculus and Combinators:

Definition 1. (Abstraction) For every CL-term $M$ and every variable $x$, a CL-term called $[x].M$ is defined by induction on $M$, thus:

$[x].M \equiv \mathsf{K}M$ $\hspace{29.8mm}$if $x \not\in FV(M)$
$[x].x \equiv \mathsf{I}$
$[x].Ux \equiv U$ $\hspace{33mm}$if $x \not\in FV(U)$
$[x].UV \equiv \mathsf{S}([x].U)([x].V)$ $\hspace{3mm}$if neither (1) nor (3) applies

Here, $\equiv$ denotes syntactical equivalence, and $[x]$ is not really part of the language of combinatory logic itself. Intuitively, a term $[x].M$ is just a name for a valid CL term which we can recover using the above definition. The definition will eliminate all bound variables. For example:

$$[xy].xyx$$
$$[x].([y].(xy)x)$$
$$[x].(\mathsf{S}([y].xy)([y].x))\text{(Def. 1.4)}$$
$$[x].(\mathsf{S}([y].xy)(\mathsf{K}x))\text{(Def. 1.1)}$$
$$[x].(\mathsf{S}(x)(\mathsf{K}x))\text{(Def. 1.3)}$$
$$[x].(\mathsf{S}x)(\mathsf{K}x)$$
$$\mathsf{S}([x].\mathsf{S}x)([x].\mathsf{K}x) \text{(Def. 1.4)}$$
$$\mathsf{S}([x].\mathsf{S}x)(\mathsf{K}) \text{(Def. 1.3)}$$
$$\mathsf{S}(\mathsf{S})(\mathsf{K}) \text{(Def. 1.3)}$$
$$\mathsf{SSK}$$

So $[xy].xyx \equiv \mathsf{SSK}$, i.e. when we write $[xy].xyx$, we really mean $\mathsf{SSK}$. You can verify that $\mathsf{SSK}$ captures the intended functionality:

$$\mathsf{SSK}xy \rhd_{1w} (\mathsf{S}x)(\mathsf{K}x)y \rhd_{1w} xy(\mathsf{K}xy) \rhd_{1w} xyx$$

similarly, the CL term $C^{CL}_{p, q}$ for $C^\lambda_{p, q}$ is simply:

$$[xyb_1 \ldots b_q a_1 \ldots a_{p-1}].x(yb_1 \ldots b_q)a_1 \ldots a_{p-1}$$

Of course, to do the elimination of variables manually even for $C^{CL}_{4,2}$ is tedious, but the point is that the meaning is fixed (and the process of elimination could easily be automated).


How about a bitwise trie? For 3D, you would interleave the bits of your three values into a single bitstrings, which could be used as a binary key.
The maximum depth is determined by the number of bits. If x, y and t each have 32 bits, the depth is limited to 3*32=96 bits. Usually the depth is much less, because depth is solely determined by the type of data, not by the insertion order. Insertion and deletion time does also not change over time, only with the size of the tree.

The bit-interleaving imposes a z-order on the tree which helps with window queries by roughly translating spatial proximity into neighbourness in the tree.

A Java example, with support for kD-window queries, can be found here (my own code). THis also contains code to do the bit-interleaving, also for floating-point values.

If you do bit-interleaving, it may be worthwhile to transform the coordinates to a similar value range. For example if x and y range from 0 to 10000, then it may be useful to multiply and/or add a constant to t, such that it also ranges from 0-10000 (you can also transform x,y instead). This is not essential. You may also want to use t as the first dimension, because it sounds like you perform a lot of window queries over t to remove old values. Having t as first dimension should improve such queries.

If you are looking for something more sophisticated, especially with more dimensions or large datasets, there is the PH-Tree. It is similar to a bitwise trie, but uses larger nodes like a quadtree, so the maximum depth is more limited. The linked website also links sourcecode and a description, including a performance comparison of kDtree, bitwise tries (critbit tree) and PH-Tree.

Disclaimer: The last part is basically self-advertising, but to the best of my knowledge, the PH-tree may be the best solution in your case, at least if you have large datasets.


Usefulness of a linked list with a cycle

In the case of circular linked list - this might be a buffer, neat structure to handle operations that must be consecutive or form a ring (like in parallel programming).

What if not the whole list is cycle?
This might be intended like conflict resolving, and thanks to cycle it will not go further.
It might be the case that every operation changes state so there is cycle, but it will eventually resolve.

If you write a turn-based game with general loop, there might be cycle if user can do something multiple times per turn. So here it is intended.

And totally not constructive - cycle came from bug, so it pushes application into infinite computation.


Tiling an orthogonal polygon with squares

I will try to show this problem is NP-hard, by reduction from $\text{Planar-}3\text{-SAT}$.

Reduction from $\text{Planar-}3\text{-SAT}$

Some basic Gadgets

Gadgets are internal configurations of geometry that will allow us to construct gates for use in a circuit, to which we will reduce $\text{Planar-}3\text{-SAT}$.

4X3-gadget

This gadget has two valid minimal-square-partition-states:

LeftA 4X3-gadget.Middle and right:Two possible minimal-square-partition-states.

5X4-gadget

This gadget, is exactly like a 4X3-gadget, just with larger dimensions.

LeftA 5X4-gadget.Middle and right:Two possible minimal-square-partition-states.

endpoint-gadget

An endpoint-gadget is a 5X4-gadget. It is frequently used as an endpoint/pin of a gate. One of the two states of an endpoint can be valued as true, and the other false. An endpoint marks the two ends, one as $T$ and the other as $F$. The end that is covered by the large square is the value of the endpoint.

Left: Wireframe of endpoint-gadget. Center:True-valued endpoint. Right: False-valued endpoint.

i-wire gadget

An i-wire gadget is short for implication wire.

Rules:

An i-wire gadget consists of a odd-length rectangle of a length of more than $2$ and a width of $2$.
An i-wire gadget can have $3$ minimal-square-partition-states, pushed from one side, the other, or neither; an i-wire in this third state shall be called locally unconstrainted.

Example:

Figure 7: An i-wire gadget of length $7$, and width $2$.

Here is how it is used:

Figure 8,9, Left: wireframe i-wire across two endpoints. Right: Union.

Now, if one endpoint is in the right state, it forces the other endpoint into a pushed-position. Example:

Left: Square partition diagram; left switch is down, "pushes" all the squares down the i-wire and finally, pushes the other switch (endpoint). Right: Square partition diagram; left endpoint is full, "pushes" all the squares down the i-wire, and forces the endpoint on left to be "up".

This is essentially a logical implication. Consider "down" to be true, then we have $A \implies \neg B$. We can also do $A \implies B$ by simply flipping the endpoint on the right.

However, this leaves the unconstrainted case:

If we combine two i-wires, we can get a two-way implication, essentially a boolean (in)equality:

So, two i-wires can carry a full equality relationship, much like a circuit - in fact, it is a circuit. We will use these pairs to construct a usable wire.

Each i-wire gadget contributes $\frac{l-1}{2}+2$ partition-squares to the minimal-square-partition, save for the shared-corners with other gadgets.

i-wires can be oriented as needed.

wire

A wire consists a pair of i-wires that are connected to the same gates at each endpoint.

The i-wires are colored red and green.
The pair must be separated by $3$ spaces (convention).
Each gate pin will have a green and red contact; a wire must correctly connect.
Invariant rule: one i-wire be pushed in the opposite direction of the other i-wire, each gate assumes this, and makes certain of this (unless otherwise noted).
Since each wire contains a two-way implication, it carries the values from gate to gate like a wire in a circuit.
Every wire must be connected to a gate at both ends.. Failing this can ruin the assumptions of some gates that I describe, and the invariant rule above; however, gates that have endpoints across the leads are safe - you can connect stray wires to these endpoints without worrying about it ruining the gate.
wires must be of odd-length, including the leads to any circuit it connects to; however I will describe an odd-skip-gate below that allows an even-lengthed wire to become odd-lengthed.

Pictures:

Above: A wire.

Left and right: Two possible minimal-square-partition-states of a wire. Note that if the wire is only this length, it will not be able to shift off to the right or left, and will have to break one square into smaller pieces.

wires can be oriented as needed.

bend-gate: Bending a wire

Left: Wire-frame view. Right: Union view.

Note the use of the 4X3-gadget. It is used to fix the red lead to odd length.

Following are the two possible minimal-square-partition-states of the bend:

Left and right:Two possible minimal-square-square-partition-states of a bending wire.

The gate can be oriented as needed. Obviously, this gate can be mirrored to work for the other direction.

Skewing a wire

It is easy to shift a wire over. Wireframe illustration:

named-value-gate

A named-value-gate is essentially an endpoint as a gate with one wire contact:

odd-skip-gate: Odd skipping a wire

Sometimes it is inconvenient to only have odd-length wires. For example:

As you can see, that little bit of extension is a bit annoying. Here is a corresponding solution, using the 4X3-gate:

So, turning this into a gate, we get the odd-skip-gate (in wireframe):

The gate can be oriented as needed.

twist-gate: Twisting a wire

Somtimes you get the red and black i-wires on the wrong sides for use with a gate. In this case, a twist-gate is provided, to twist the red and black i-wires to the opposite sides.

Wireframe illustration:

Convince yourself it works:

Start from $A$, follow the push-arrows, everything else should be forced and consistent.

The gate can be oriented as needed.

split-gate: Splitting a wire

Splitting a wire, wireframe:

Convince yourself that it works:

Figure:Start from $A$, follow the push-arrows. Everything should be forced and consistent.

Figure:Start from $A$, follow the push-arrows. Everything should be forced and consistent.

Note: Every wire coming in and out of the splitter absolutely must connect to an endpoint somewhere, in order to maintain the invariant. Alternatively, you can add endpoints to each of the pairs of leads of the splitter.

The gate can be oriented as needed.

not-gate

The not gate takes a wire and outputs a wire that has the reverse implications. It is basically a twist-gate, except that it relabels the colorings of the wires. The not-gate looks like this:

And a view of the two possible states:

The gate can be oriented as needed.

clause-gate

For the clause-gate, we first introduce the clause-gadget:

Left to right: 1 clause-gadget. 2-4: $3$ different minimal-square-partition-states.

This is what the gate looks like:

We can demonstrate the different states of this gate (explanation underneath all $3$ illustrations):

Explanation:

Start at the clause-gadget and follow the arrows.
Non-arrow-lines mean that it is part of a circuit, but it is not forced into a state by the gate.
The state of the clause-gadget forces one of the endpoints to be valued true.

As you can see, at least one of the inputs will have to be valued as true. This is exactly what a $3\text{-CNF}$ clause requires.

The gate can be oriented as needed.

Reduction

Let $\Phi(\mathbf x)$ be a $\text{Planar-}3\text{-SAT}$ formula, where

$$\Phi\left(\mathbf x\right)={\huge\wedge}_i^n C_i,\\
C=\left\{(x_j \vee x_k \vee x_l)\right\}
$$

A visual aid (original source: Terrain Guarding is NP-Hard (PDF), reproduced in tikz):

Then:

For each variable $x_i\in\mathbf x$, place two named-variable-gates next to each-other,  name one of them $x_i$ and the other $\neg x_i$.
Connect the gates to each-other with a not-gate, so that they logically negate each-other's values.
Place the variables' gates' polygons at their locations in the planar-embedding.
For each clause, place a clause-gate at the clause's location in the planar-embedding.
Using the gates described above, connect all the variables to their clauses.
Run a minimum-square-paritioning-algorithm on the resulting union of the all of gate's polygons (the entire circuit).
If the algorithm returns the sum of all the gate's minimal-square-partition-state sizes (subtracting for shared-corners) then it is satisfiable. If it is not satisfiable, it will force a constrained gadget to split into smaller squares, thus increasing the number of squares required to partition the circuit.

Why it works

Each gadget has a minimal-square-partition-state size; that is, a minimal-square-partition of that gadget is a certain size.
Some gadgets have several states with this size; each of these states are valid minimal-square-partitions.
When gadgets are combined only in the corners, the sum of the minimal-square-partition-states of the gadgets is *still the minimUM-square-partition-state of the union of them; you can see this intuitively: joining at the corner does not give ample space for a square to expand/connect with a square from another gadget.
While combining gadgets at the corner does not decrease the total minimum-square-partition size, it does relate and constrain the gadgets with each-other.
With the gates shown above, you can constrain the states enough, so that if the logical formula is unsatisfiable, then one or more gadets will have to break into even smaller squares, and increase the minimum-square-partition size.

graph sources

squaretilings1.tex (writelatex)
squaretilings2.tex  (writelatex)
clausegate.tex (writelatex)

You can also see larger images by removing the "s", "m", "l", suffixes of the imgur urls. For example, You can see a larger image of this: http://i.stack.imgur.com/6CKlGs.jpg by going to
http://i.stack.imgur.com/6CKlG.jpg. Notice the missing "s" before the .jpg.


Complexity of the V-opt heuristic Traveling Salesman algorithm

According to the original 1973 paper, the Lin-Kernighan algorithm

  ...produces optimum results with high frequency, in running times
  that grow about as $n^2$.

The iterated Lin-Kernighan variant, proposed by Johnson in 1990, offers an observed improvement to $O(n^{1.25})$; an experimental treatment of this and many other local optimization TSP heuristics can be found here.


Grammar that numbers of letters `c` is greater than number of letters `b`

Your grammar never accepts a word since you can't make the $S$ disappear.

If you want to create more $c$ than $b$ you just have to make sure that when you create a $b$ you create a $c$ with it (but be careful they don't need to be side to side). You can also generate as much $a$ or $c$ as you want.

If you need more indication please ask.


Understanding tables in Dynamic programming

dp[i][j] represents whether text[i..] matches pattern[j..].

If pattern[j..] is starting with x* for some symbol x (including .), then text[i..] matches pattern[j..], or x*pattern[(j+2)..], if and only if

text[i..] matches pattern[(j+2)..] (i.e. x* matches an empty string), or
text[i] is x and text[(i+1)..] matches x*pattern[(j+2)..] (i.e. x* matches a non-empty string).

This is implemented by this part of code:

if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
}

On the other hand, if pattern[j..] is not starting with x*, text[i..] matches pattern[j..] if and only if text[i] matches pattern[j] and text[(i+1)..] matches pattern[(j+1)..]. This is implemented by this part of code:

else {
    dp[i][j] = first_match && dp[i+1][j+1];
}


Understanding The Mapping Of Edges to Nodes In A Graph Theory Problem

$a[0] = 1, a[1] = 2, a[2] = 3$.

"The arrow from place $i$ points to place $a[i−1]$"

So yes, all $3$ places in this sample point to themselves. It actually says in the explanation that "in each round each token will stay in the same place".

In the second sample, all three places point towards the first one.

In the third sample, you have a $2$-cycle: $1$ points to $2$ and vice-versa.

Is everything clear now?


These are sometimes called (static) online data structures or online query data structures. It's actually rather hard to find a definition written down and the notion is "soft", in the sense that you can reasonably argue that almost anything would qualify especially if you allow updating. Here's one definition and mini-taxonomy:

  Online data structures support query operations in a continous manner. When the data items do not change and the data strucuture can be preprocessed before any queries are made, the data structure is known as static. When the data structure supports insertions and deletions of items, intermixed with the queries, the data structure is called dynamic.

The term online algorithm is used with a related meaning. It seems to be more widespread (as a term) than its counterpart for data structures. Since the query is the stuff/input that's online in your case, "data structure for online query" is more explicit; searching this as an entire phrase doesn't find much, but as nearby terms you'll get relevant hits e.g. from books [1] [2] [3] [4] etc. Likewise one can speak of "data structure" for "online updating".


Will this program terminate for every Integer?

The correct answer is that this function does not terminate for all integers (specifically, it does not terminate on -1). Your friend is correct in stating that this is pseudocode and pseudocode does not terminate on a stack overflow. Pseudocode is not formally defined, but the idea is that it does what is says on the tin. If the code doesn't say "terminate with a stack overflow error" then there is no stack overflow error.

Even if this was a real programming language, the correct answer would still be "does not terminate", unless the use of a stack is part of the definition of the language. Most languages do not specify the behavior of programs that might overflow the stack, because it's difficult to know precisely how much stack a program will use.

If running the code on an actual interpreter or compiler causes a stack overflow, in many languages, that's a discrepancy between the formal semantics of the language and the implementation. It is generally understood that implementations of a language will only do what can be done on a concrete computer with finite memory. If the program dies with a stack overflow, you're supposed to buy a bigger computer, recompile the system if necessary to support all that memory, and try again. If the program is non-terminating then you may have to keep doing this forever.

Even the fact that a program will or will not overflow the stack is not well-defined, since some optimizations such as tail call optimization and memoization can allow an infinite chain of function calls in constant-bound stack space. Some language specifications even mandate that implementations perform tail call optimization when possible (this is common in functional programming languages). For this function, f(-1) expands to f(f(-2)); the outer call to f is a tail call so it doesn't push anything on the stack, thus only f(-2) goes onto the stack, and that returns -1, so the stack is back to the same state it was in at the beginning. Thus with tail call optimization f(-1) loops forever in constant memory.


As is often the case, the Wikipedia article is misleading.

A problem involving integers parameters is:

Strongly NP-complete if the problem is NP-complete when the parameters are encoded in unary (i.e., $n$ is encoded as $0^n$).
Weakly NP-complete if the problem is NP-complete when the parameters are encoded in binary (which is the usual encoding).

In other words, there is only one notion of NP-completeness, and the confusing terms strongly and weakly NP-complete simply refer to different encodings of problems.

For a problem like SAT, these terms are simply inapplicable, since SAT has no integer parameters. The terms do apply to the related problem of weighted MAX-SAT, in which the input is a set of weighted clauses and a target, and the problem is to determine whether there is an assignment which satisfies clauses whose total weight exceeds the target.


Are there inherently ambiguous and deterministic context-free languages?

If a language $L$ is deterministic, it is accepted by some deterministic push-down automaton, which in turn means there is some LR(1) grammar describing the language, and as every LR(1) grammar is unambiguous, this means that $L$ cannot be inherently ambiguous. Knuth proved this in his paper in which he introduced LR(1) (On the Translation of Languages from Left to Right).

A language can be described by some context-free grammar if and only if it can be recognized by some nondeterministic automaton. As a special case of this, inherently ambiguous context-free grammars can be parsed by some nondeterministic automaton.

On a final note, any deterministic push-down automaton is also nondeterministic (this is the case for just about anything that can be nondeterministic, for a reasonable definition of nondeterminism).


Inviting an optimal subset of persons such that all friends of a person invited are invited

This is known as the closure problem. I quote the Wikipedia paragraph describing the reduction to the max flow problem here.

As Picard (1976) [1] showed, a maximum-weight closure may be obtained from $G$ by solving a maximum flow problem on a graph $H$ constructed from $G$ by adding to it two additional vertices $s$ and $t$. For each vertex $v$ with positive weight in $G$, the augmented graph $H$ contains an edge from $s$ to $v$ with capacity equal to the weight of $v$, and for each vertex $v$ with negative weight in $G$, the augmented graph $H$ contains an edge from $v$ to $t$ whose capacity is the negation of the weight of $v$. All of the edges in $G$ are given infinite capacity in $H$.
A minimum cut separating $s$ from $t$ in this graph cannot have any edges of $G$ passing in the forward direction across the cut: a cut with such an edge would have infinite capacity and would not be minimum. Therefore, the set of vertices on the same side of the cut as $s$ automatically forms a closure $C$. The capacity of the cut equals the weight of all positive-weight vertices minus the weight of the vertices in $C$, which is minimized when the weight of $C$ is maximized. By the max-flow min-cut theorem, a minimum cut, and the optimal closure derived from it, can be found by solving a maximum flow problem.

[1]  Picard, Jean-Claude (1976), "Maximal closure of a graph and applications to combinatorial problems", Management Science, 22 (11): 1268–1272, doi:10.1287/mnsc.22.11.1268, MR 0403596.


Better results for minimum vertex cover algorithms

A short trip to wikipedia will tell you that there is no known better approximation algorithm for vertex cover (at least when by "better" we require an improvement by a constant independent of the input).

This is what is known so far:

The best known approximation achieves an approximation factor of $2-\Theta\left(\frac{1}{\sqrt{\log V}}\right)$ [1].
VC is NP-hard to approximate within a factor of $1.3606$ (meaning that if we have a polynomial approximation algorithm with this factor then $\mathsf{P}=\mathsf{NP})$ [2].
If the unique games conjecture holds, then VC is NP-hard to approximate within a factor of $2-\epsilon$, for all $\epsilon>0$ [3]. So if there exists a $2-\epsilon$ approximation for VC, then either $\mathsf{P}=\mathsf{NP}$, or the unique games conjecture fails.

Thus, any better approximations than the naive one you presented will solve open questions in complexity, so you are not likely to find them here (and they might not exist at all).

1. G. Karakostas, A better approximation ratio for the vertex cover problem, ACM Trans. Algorithms (TALG) 5 (4) (2009) 41.

2. Dinur, Irit; Safra, Samuel (2005). "On the hardness of approximating minimum vertex cover". Annals of Mathematics. 162 (1): 439–485.

3. Khot, Subhash; Regev, Oded (2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. 74 (3): 335–349.


how to check whether a flow network contains unique maximum flow?

Find a maximum flow.  Then create m new flow networks: one for each edge in the maximum flow.  In each new configuration, reduce the capacity of one of the edges to an amount just below its flow.  Find the maximum flow on each of the new flow networks.  If any of the new configurations generate the same maximum flow value as the original graph, then that new flow is also a maximum flow in the original graph.  Hence, the original maximum flow is not unique.


Number of substrings possible with even characters

Assuming that your alphabet has constant size, you can solve your problem in linear time in the length of the input string.
Let  $\Sigma = \{a_1, a_2, \dots, a_m\}$ be your alphabet and $s = s_1 s_2 \dots s_n$ be your input string.
For $i=0, \dots, n$, and $j=1,\dots,m$ let $n_j(i)$ be $0$ iff the number of occurrences of $a_j$ in $s_1 \dots s_i$ is even and $1$ otherwise.
Let $\eta(i) \in \{0,1\}^{m}$ be the vector $(\eta_1(i), \dots, \eta_m(i))$.
Consider any substring $s_{hk} = s_{h+1},s_{h+2}, \dots, s_k$ of $s$, where $0 \le h < k \le n$.
The number of occurrences of each $a_j$ in $s_{hk}$ is even if and only if $\eta(k)-\eta(h) = (0, \dots, 0)$, where the difference is taken modulo $2$, i.e., iff $\eta(k)=\eta(h)$.
Then your problem is equivalent to counting the number of unordered pairs of distinct indices $\{h,k\}$ for which $\eta(h)=\eta(k)$.
This can be done as follows: given $x \in \{0,1\}^{m}$ let $\alpha(x)$ be the number of times of $x$ appears in $\eta(0), \dots, \eta(n)$, so that the number of unordered pairs $\{h,k\}$ for which $\eta(h) = \eta(k) = x$ is $\binom{\alpha(x)}{2} = \frac{\alpha(x) (\alpha(x)-1)}{2}$.
To find the find the overall number of substrings of interest it suffices
to sum the above quantity over all choices of $x \in \{0,1\}^m$:
$$
\sum_{x \in \{0,1\}^m} \binom{\alpha(x)}{2} = \frac{1}{2} \sum_{x \in \{0,1\}^m} \alpha(x) (\alpha(x)-1).
$$
Since $m=O(1)$, all values of $\eta(i)$, for $i=0, \dots, n$ can be computed in $O(nm) = O(n)$ time. Moreover, all values of $\alpha(x)$ for $x \in \{0,1\}^m$ can also be found in $O(n m \log \min\{n, 2^m\}) = O(n)$ time by scanning $\eta(0), \dots, \eta(n)$ once and maintaining a counter for each $x$ (these counters can be stored in a dictionary with at most $\min\{n,2^m\}$ elements).
Finally, the final sum can be computed using $O(\min\{n, 2^m\}) = O(1)$ arithmetic operations (as it only needs to extend to $x \in \{0,1\}$ for which $\alpha(x) > 0$).

An example implementation due to @orlp of the above in Python using a binary integer as the vector $x$ and storing all $a(x)$ in a hashmap counter is as follows:
def num_even_substrings(s):
    a = {0: 1}
    x = 0
    for c in s:
        x ^= 1 << ord(c)
        a[x] = a.get(x, 0) + 1
    return sum(ax*(ax-1)//2 for ax in a.values())


Finding a suitable NP-complete problem for reduction

This is SAT in disguise. Every name corresponds to a clause. Every paper corresponds to a variable. Each side of the paper corresponds to a possible truth assignment to the variable.

If this is unclear, I suggest working out an example.


Is there a relationship between "sound and complete" in logic and "type safety" in PLs?

Soundness and completeness of logic are semantic notions which say that logic and its models fit together nicely. We can find similar theorems in the theory of programming languages but they are not necessarily about mathematical models of programming languages.
A general way to understand soundness is that "bad things do not happen" (logic does not prove invalid things). A general way to understand completeness is that "good things happen" (there are sufficiently many models).
A programming language typically has several kinds of semantics:

static semantics explains how to assign types to programs
dynamics (operational) semantics explains how to run programs, more or less
denotational semantics is more akin to models in logic and it explains how to map programs to mathematical objects.

There are theorems which relate these semantics. For instance:

Preservation: If a program p has type T and p evaluates to p' then p' has type T.

This is like soundness (bad things don't happen, namely a program will not become untyped). Another one is:

Progress: If a program p has type T then it is either a value (it's finished) or it has another step of execution.

This is like completeness (good things happen, namely a program will make the next step).
When we put these two together, we get safety.
Another kind of theorems relates denotational semantics to operational semantics. For instance:

Adequacy: if p and q are denoted by the same mathematical object then they are observationally equivalent.
Full abstraction: if p and q are observationally equivalent then they are denoted by the same mathematical object.

Adequacy says that the model is not too small and full abstraction that it is not too big. It makes a bit less sense to relate these two to soundness and completeness, but if I had to, I would say that full abstraction is like soundness and adequacy is like completeness.


Sorting an array where the largest element appears once, the second largest appears twice and in general the $k$-th element appears $2^{k-1}$ times

If I understand correctly the title (which is a bit clearer than the post itself), an example of such an array would be $[1, 4, 1, 2, 1, 2, 5, 2, 1, 1, 4, 1, 2, 1, 1]$.
If that's the case, you can:

Count the number of occurrences of each value, with a hashtable for example;
Sort the unique values with descending order of occurrences;
Recreate the sorted array by repeating each value by the number of occurrences.

This algorithm is indeed in time complexity $O(n)$, since the array contains only $\log_2 (n+1)$ unique values. That means that even the worst case of operations in the hashtable is in complexity $O((\log n)^2)$, and sorting the unique values array can be done in $O(\log n \log \log n)$. The last step is done in $O(n)$.


How can I keep track of the state of a sequence after rotating parts of it multiple times?

But the problem here is that the values of the elements do not matter,
since the rotations can change the order arbitrarily (actually, I do
not understand why they are first sorted).

You want to find an element according to its index in the list, not
its value. A way to do that is to keep with each node of the tree
the number of list elements (leaves) dominated by its left daughter.
Then very simple arithmetics will tell you at each node whether the
$n^th$ element of the list is to be found under the left or the right
daughter, and you acess it in $O(\log n)$ steps if the tree is
properly balanced.

Then the element in inserted at the beginning, which can also be done
in $O(\log n)$ steps.

Then you need to rebalance the tree when it gets unbalanced. But there
are techniques to maintain balancing.

The same should be possible with skiplist, again relying on some size
information to access by index rather than by value.


A reflective tower is a model for language extension. It is modeled as an infinite (tower) series of interpreters. Each interpreter is executing a program which is the interpreter one level bellow it with the programmers' program being at level 0.

Each program is a piece of code that performs computation and in that sense a function but it is also a modifiable struct (it is a data-structure).

You can read about it here


Find isomorphism of graph with maximal number $x$ such that $f(x)\neq x$ - assuming $NP=P$

Consider the decision version of computing $\#G$:

$L=\{(G,k) | \text{$G$ has an automorphism $f$ with $\#f\ge k$}\}$

$L$ is obviously in NP (an automorphism $f$ with $\#f\ge k$ is a witness). If $\mathsf{P=NP}$ then $L\in P$, and you can compute $\#G$ in polynomial time using binary search.


Can't find a mistake in reduction from RE language to a non-RE language

Your reduction actually shows that $L_m$ is not co-RE. Indeed, if $L_m$ were co-RE, then your reduction shows that $L_u$ is also co-RE. However, $L_u$ is known to be RE but not recursive, hence cannot be co-RE.

Similarly, you can show that $L_m$ is not RE, by reduction from the complement of the halting problem: given an instance $(M,w)$ of $L_u$, create a new machine $M'$ which on input $n$ simulates $M$ on $w$ for $n$ steps. If $M$ halts, $M'$ gets into an infinite loop, and otherwise it halts. You can check that $M$ halts on $w$ iff $L(M')$ is finite.

The language $L_m$, usually known as INF, is actually one of the canonical examples of $\Pi_2$-complete languages, making it harder than the halting problem.

Your title suggests that you believe that RE languages cannot be reduced to non-RE languages. But in fact, every recursive language can be reduced to every non-RE language. I'll let you work this out.


Efficient algorithm to find all distances to a specific node in a tree

Assuming your edges are not directed (which seems to be the case in case you are dealing with trees), you can calculate the distance by starting a breadth-first search from node 2. Then, you get the number of steps necessary to go from node 2 to each node $n$, which, as the graph is undirected, is the same as the number of steps necessary to go from node $n$ to 2.

If your had a directed graph, you can basically do the same, but you have to traverse edges in the opposite direction. E.g. if you are at node $n_1$, and have the edges $n_1 \to n_2$ and $n_3 \to n_1$, you would then process $n_3$ as a successor, but not $n_2$.


It is possible to write any program (i.e. Turing complete) with just one single expression?

I think that your general question is pretty broad, because you'd need to specify what you consider a program (e.g. is the identity function that outputs the input it receives a program?).

It is possible to have some sort of control flow in lambda expressions (there are only expressions in lambda calculus); consider e.g. Church Booleans that enable conditionals.

If you would like to see examples of lambda calculus expressions put to work like regular programs, I can recommend John Tromp's binary lambda calculus. I have been able to evaluate some of his programs using plain β-reductions (examples), so I can say it's definitely possible to write programs even with pure lambda calculus.


Algorithm to evenly distribute a hierarchical dataset

You want to use an algorithm for graph layout.  There are many out there, as well as some tools.


Try to use closure properties instead.

Closer hint:

   CFL is closed against (pre)image of language homomorphisms and intersection with regular languages.


Tips on speeding up hierarchical linkage clustering algorithm

Yes.  After you merge two points, you can update the distances of just the affected nodes, without having to recompute all pairs of distances again.  That will be vastly faster.


Regular Expression from Context Free Grammar

Denote your grammar by $G$ and let
$$
M=\{w\in\{a,b\}^*\mid |w|_a\equiv 0\pmod 2\}
$$
where $|w|_a$ is the number of $a$s in $w$. In other words, $M$ is the set of all strings of $a$s and $b$s with an even number of $a$s. We claim $L(G)=M$.

First, it is clear that any word in $L(G)$ must have an even number of $a$s, so $L(G)\subseteq M$. All we now have to do is show $M\subseteq L(G)$, in other words, that every string in $M$ can be generated by $G$. We'll show this by induction on the number, $n$, of $a$s in a word.

If $n=0$, we can generate strings consisting only of $i\ge 0\ b$s by one of two derivations:
$$\begin{align}
S &\Rightarrow A\Rightarrow \epsilon \\
S &\Rightarrow A\Rightarrow bA\stackrel{*}{\Rightarrow} b^i
\end{align}$$
So we can generate all strings with no $a$s.

If $n=2$, any string in $M$ with exactly two $a$s must have the form $b^iab^jab^k$ with $i, j, k\ge 0$. Write such a string as $(b^i)(ab^ja)(b^k)$. We've seen that we can generate the $b^i$ and $b^k$ portions from $A$. We can also generate the $ab^ja$ part from $A$:
$$
A\Rightarrow aAa\stackrel{*}{\Rightarrow} ab^ja
$$
so we can generate $b^iab^jab^k$ by
$$
S\Rightarrow ASA\Rightarrow AAA\stackrel{*}{\Rightarrow} b^iAA\stackrel{*}{\Rightarrow}b^iab^jaA\stackrel{*}{\Rightarrow}b^iab^jab^k
$$
and it's clear that we can continue this process for even $n>2$, simply by starting with the requisite number of $A$s. In short, we've shown that any word in $M$ can be generated by the grammar $G$, and this, combined with the first part, shows that $L(G)=M$.

Of course, $M$ is regular, if for no other reason than it is denoted by the regular expression $(ab^*a+b)^*$. Also, it would also be easy to construct a finite automaton for $L$ as well.


What do we call a greedy algorithm that tracks the best $n > 1$ solutions?

You might be interested in beam search, which could be viewed as working in more or less this way.