Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular

Consider the intersection of your language $L$ with the regular language $L' = \{b^r a^m \mid r,m \ge 0 \}$.
Then $L \cap L'$ contains all the words of the form $a^k b^r a^m$ where $k=0$ and $m=k+r=r$. That is, $L \cap L' = \{ b^r a^r \mid r \ge 0  \}$, which is a well-known non-regular language.


Terminology - the reason for symbol reuse in programming languages

The main reason is very mundane. At the time C was designed, and
notations for many things, we did not have any form of graphics, or
very seldom (like one graphic screen for the whole university, even in major places). Actually, the main output devices were the teletype or the line-printer, with a standardized and
limited character set. Even the alphanumeric screen came later for most. No windows or mouse excepts in rare labs (Xerox).q

So that was a general constraint for everyone. For writing papers, we
could add hand-written symbols in blank spaces left by the typist. But
for more mechanized works such as programs listing (i.e. the printed
text of programs) and for execution result, we had to do with what
characters were available on the printing device.

Another problem was that increasing the number of symbols was limited
by the standard encoding in seven or eight bits. Memory was very
costly. The syntax of Fortran (the version of that time) was influenced by the format of punched cards.

Then there is a tradition. Mathematicians have been reusing symbols too. And so does natural language. We get diversity by composing them, or using context. And this was fortunate for Gutenberg, and made writing generally much easier. Compare Chinese and Latin writing.

Regarding how this could be called, I must say there is no word that
comes to my mind. Not even the feeling that there was a specific word
for that. I did quite a bit of theoretical and practical work on
programming language syntax and I do not remember this as an issue,
except as explained below.

Short of knowing what word you may look for, I can try to guess, and some
obvious candidates would be homonymy or homography. Or maybe polysemy.

A specific case, but which concerns more identifiers, is scoping
rules. In some languages they apply also to operators.

So far, that is the best I can contribute to this onomasiological issue.


Help Understanding the Type and Complexity of my Programming Task

Divide this problem into two parts.

  I am attempting to design a program to optimize daily fantasy baseball rosters given certain information. The context here is that I will be designing rosters of players from various games that consists of 2 pitchers and one player that plays each other position. This is complicated by the fact that each player is assigned a salary relative to their perceived ability and there is an overall cap on how much salary can be used in total. This means I am dealing with restrictions in terms of making sure that I do not exceed the combined salary cap, while also making sure that I have players at each position.

This sounds like the 0-1 Knapsack problem where you have an overall salary cap and salary and importance of each player.

So from a list of all the players available in the market, form your personal roster using this concept.

Now coming to the second part of your question,

  I want to be able to pick a few players (1-5 or so) at each position as my favorites, and have control over what % of my teams they appear in. That is, if I make 50 teams, I'd like to be able to make it so that I can generate these teams by inputting a list like: Player X (pitcher) 5%, Player Y (First Base) 50%, and so on.

You have a personal roster at hand and each player has a percentage attached to him. Try a greedy strategy to distribute players.

Pardon my ignorance of baseball's rules but here is a simple example to help you out. Suppose you have 10 teams where each team has to have only one keeper (the guy who stands behind the players with the bats). You have to distribute Keeper X, Y and Z among the two teams. X has a 10% percentage chance, Y has a 90% chance, Z has a 10% chance. So sort the players according in ascending order according to weightage and put X in team 1, Y in team 2 and Z in teams 3 through 10. Similarly sort according to your criteria, and develop your own heuristic  to fill each position.


Clarifications on polynomial reducibility for problems in P and NP-complete

As pointed out by @Vor the point of polynomial-time reductions is to show that if have a reduction from A to B and an algorithm to solve a problem B then you can use it to efficiently (i.e. in polynomial time) solve the problem A. Note that efficiently does not mean optimally, when you reductions, your solutions will not be better than the class your use for reductions (i.e. if you use a polytime reduction to reduce to a constant time language, you still have just a polytime algorithm).

I think what you are getting confused about is that reductions can be used to show that a problem is easy or that it is hard. In this case, they are used in two different ways. Suppose you have some problem X, and

you think it is easy (i.e. doable in polynomial time). In that case you find your favorite polynomial time problem B (say linear programming) and reduce X to B. Now you have an efficient algorithm for X: run the reduction and then run a polytime LP-solver. On the other hand,
you think X is hard (i.e. probably not doable in polynomial time). In that case you find your favorite NP-complete problem A (say 3-SAT) and reduce A to X. Now if you had an efficient algorithm for X, you would be able to solve A in polynomial time (reduction, then X). Since we suspect that A cannot be solved in polynomial time, this means we have a contradiction, so you cannot have an efficient algorithm for X.

There is no general rule for deciding if a given problem is in P or NP-complete, but we have a list of rules of thumb to help you.


What decompression algorithms have the shortest implementations?

I expect short decompressors with algorithms that do not maintain an explicit model and use "simple" encodings. An LZ encoding might use (length, offset) with Fibonacci coding, with an offset of 0 meaning a run of length literal codes, (minus) one a repetition of the last code, ….
I expect decompressor size to depend on (possibly abstract) machine - "MS Windows x64", NC4000, …
(The implied model being Things seen before are more likely than anything new, with short, local repetitions more likely than large ones from way back.)
That said, you may be after shortest length of compressed code+decompressor - Kolmogorov complexity.


Complexity Class of an Algorithm with two Inputs

You're confused because you've called part of your input $n$. When we say that the running time is some function of $n$, we almost always mean that $n$ is the length of the input string.

Your algorithm runs in time $|P|^L$, where $P$ is a string contained in the input and $L$ is a number represented in the input, presumably in binary.  If $L$ is a $b$-bit number, it could be as big as $2^b$.  Writing $n$ for the length of the input, we could, for example, have $|P|=n/2$ with $L$ being an $(n/2)$-bit number.  That case gives running time $(n/2)^{2^{n/2}}$, which is a long, long way from being polynomial.


Worst case running time of lexicographical sorting of a list of n strings each of length n using merge sort

The mistake and correction

$$T(n)= 2T(n/2) + \theta(n^2)$$

As you intended, $T(n)$ is the worst time of mergesorting $n$ strings of length $n$. Then, $T(n/2)$ on the RHS means the worst time of mergesorting $n/2$ strings of length $n/2$. So during the mergesort, the length of strings shrinks from $n$ to $n/2$!

What should have been done is using a different variable to express the number of strings at the start of each mergesort. Let us define $T(m, n)$ to be the cost of mergesorting $m$ strings of length $n$. Now, we will have

$$T(m, n)= 2T(m/2, n) + \theta(mn),$$

from which we can deduce $$T(m,n) = \theta(nm\log m).$$

Another correct approach

Mergesort of $n$ items takes $\theta(n\log n)$ time, assuming a unit cost of comparison. In fact, mergesort uses $\theta(n\log n)$ comparisons. Now that it costs $\theta(n)$ to compare two strings of length $n$ at worst time, the worst time of mergesort of $n$ strings of length $n$ should be $\theta(n\cdot n\log n)$.


Method for combining derivative free optimization results of different data inputs

You say you are overfitting.  The usual solution is to use more training data and/or regularization.

The easiest solution is probably going to be to train on all data, not just a limited time window.  Perhaps you can find a better mathematical optimization algorithm. You don't give any details on the optimization algorithm you are using or how you compute the loss function; perhaps using a stochastic version (e.g., analogous to SGD instead of GD) would provide better efficiency.  You could also consider Bayesian optimization, which constructs a differentiable model to estimate/predict the output of your loss function, and then uses SGD on it.  Another option is to use gradient-based methods and estimate the gradient using finite differences; if you have 10 parameters, you can estimate the gradient by evaluating the function 11 times on 11 different inputs.  Then you could combine that with gradient descent.

Or perhaps you can use regularization; for instance, if you have a prior on parameters, you might be able to choose a suitable regularization method.  I suspect it's going to be hard to say without getting into the specifics.


Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question

Note the following line of code:

powerSet.add(new ArrayList<>(SelectedSoFar);

Whenever we create a subset, we add the subset (list) to a list of list : power set. The size of subset will be $n$ (actually it will vary from $1$ to $n$, but we can take it to be $n$).

Even though adding a list requires one line of code, but it will involve copying all the elements. This is why it will take O(n) time.


Specific example of a problem that shows why **NP** isn't low for itself

As Pål GD mentions in the comments, $\mathsf{NP}^\mathsf{NP}$ is usually knows as $\mathsf{\Sigma}_2^P$, the second level of the polynomial hierarchy. If $L$ is any $\mathsf{\Sigma}_2^P$ complete problem, then $\mathsf{NP} \neq \mathsf{\Sigma}_2^P$ is equivalent to $L \in \mathsf{\Sigma}_2^P \setminus \mathsf{NP}$. So any $\mathsf{\Sigma}_2^P$-complete problem is a concrete example for a problem in $\mathsf{\Sigma}_2^P \setminus \mathsf{NP}$ under the reasonable assumption that $\mathsf{\Sigma}_2^P \setminus \mathsf{NP} \neq \emptyset$. In other words, these are the problems "most likely" to be the concrete examples you seek.

One canonical complete problem for $\mathsf{\Sigma}_2^P$ is $\exists \forall\mathsf{SAT}$: given a formula $\varphi$ on variables $\vec{x},\vec{y}$, is is true that there exists an assignment $\alpha$ to $\vec{x}$ such that $\varphi|_{\vec{x} = \alpha}$ becomes a tautology? It is easy to see that this can be solved by an $\mathsf{NP}^\mathsf{NP}$ machine: the machine guesses $\alpha$, and uses the oracle to verify that $(\lnot \varphi)|_{\vec{x} = \alpha}$ is unsatisfiable.

Generally speaking, the assumption $\mathsf{NP} \neq \mathsf{\Sigma}_2^P$ seems stronger than $\mathsf{P} \neq \mathsf{NP}$, and when proving conditional results, we prefer assuming the latter rather than the former. But it is generally conjectured that the entire polynomial hierarchy is strict, a much stronger assumption.


Alternative to Hamming distance for permutations

Finding the minimal distance is called the "Sorting By Translocation" problem. Part of an abstract from a paper:

"Given two signed multi-chromosomal genomes Pi and Gamma with the same gene set, the problem of sorting by translocations (SBT) is to find a shortest sequence of translocations transforming Pi to Gamma, where the length of the sequence is called the translocation distance between Pi and Gamma. In 1996, Hannenhalli gave the formula of the translocation distance for the first time, based on which an $O(n^3)$ algorithm for SBT was given. In 2005, Anne Bergeron et al. revisited this problem and gave an elementary proof for the formula of the translocation distance which leads to a new $O(n^3)$ algorithm for SBT."

What's called "translocation" here is called a transposition, i.e., a permutation of exactly two elements in a list, in traditional combinatorial language.


What does up arrow ($\uparrow$) mean in pseudocode?

The algorithms in the paper you link to are described in a notation quite similar to Pascal, a language that treats pointers in a very particular way. In Pascal, pointers are declared as references to values of specific types (a pointer to an integer can never refer to a boolean, for instance).

The upward arrow, in the example you reproduce, is a dereferencing operator. Clearly, node is a pointer to a value of a record type (not a record itself), of which p and mu are fields, so node.p has no meaning.

Check out this similar question for further clarification.


Some reasons for using more bits per color channel:

Tetrachromats. There are rare humans with four types of cone receptors in their retinas instead of the usual three.  These people can distinguish an order of magnitude more color shades than the rest of us.
Color gamut.  Your question assumes that the 16 million colors available in 8-bit per channel RGB exactly covers the colors that normal humans can see.  But if that were so then we would only need one RGB color space.  We have more..  More bits per channel allows a wider gamut of colors to be represented without posterization, because the increased bit depth means smaller gaps between the individual shades.
Image manipulation.  Every image manipulation, from switching color models for printing, to sharpening, to resizing, to tone curve adjustment, loses information.  The more information you start with the more you have at the end of post-processing.  The more information you start with the easier it is to avoid the introduction of visible artifacts like posterization.


Understanding the flaw in a proof attempt of the Communication Complexity of Equality

This vague argument can be made to work for deterministic communication complexity. In the randomized setting, protocols are allowed to err. Consider the standard protocol in which both players exchange a random hash of their inputs to some set of size $2^m$. They only learn $m$ bits of each other's input. When both hashes agree, they aren't completely sure that $X=Y$, and in particular no party has learned the other party's input.


Algorithm - Checking if an unconnected graph is cyclical

As part of the cycle checking, you already need to keep track of which vertices have been visited. So just restart at the first unvisited vertex each time you exhaust a component.


The classical version of this question is for Hamiltonian cycles, but there is probably little difference. I will only consider the version with cycles.

In order for a graph to contain a Hamiltonian cycle, the minimal degree should be at least 2. This is essentially the only obstruction for Hamiltonicity. To state this we need to define the following process:

For every pair $\{x,y\} \in [n]$, let $\theta_{xy} \sim U([0,1])$ (independently).
Define $G_p = \{ \{x,y\} : \theta_{xy} \leq p \}$.

By construction, $G_p \sim G(n,p)$. As $p$ goes from 0 to 1, more and more edges are "exposed". Bollobás proved the following result:

  Let $p_2$ be the minimum $p$ such that the minimal degree of $G_p$ is at least 2.

  Let $p_H$ be the minimum $p$ such that $G_p$ is Hamiltonian.

  With high probability, $p_2 = p_H$.

The expected degree of a vertex is $p(n-1) \approx pn$. This suggests looking at $p = c/n$. A simple calculation shows that for appropriate values of $c$, the degree of a vertex has distribution roughly Poisson with expectation $c$. In particular, the probability that a vertex has degree less than 2 is roughly $q = e^{-c}(1 + c)$. A further calculation shows that these events for different vertices are roughly independent, and so the distribution of the number of vertices of degree less than 2 is roughly Poisson with expectation $nq$. In particular, the probability that the minimal degree is at least 2 is roughly $e^{-nq}$, for appropriate values of $c$. If $c = \log n + \log \log n + r$ then $q = \frac{\log n + \log \log n + r + 1}{e^rn\log n} \approx \frac{e^{-r}}{n}$, and so $e^{-nq} \approx e^{-e^{-r}}$. This suggests the following result:

  The probability that $G(n,p)$ is Hamiltonian for $p = \frac{\log n + \log\log n + r}{n}$ tends to $e^{-e^{-r}}$ for constant $r$.

  If $r \to -\infty$ the probability tends to zero, and if $r \to \infty$ it tends to one.

This result indeed holds.

You can see a final project of Brunet for some pointers. For more information, consult any decent textbook on random graphs; Hamiltonicity is a classical topic which would be covered in many of them.


Sliding window protocol, calculation of sequence number bits

Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts.

When the data is transmitted using a duplex link, Round Trip Time (RTT) do not include the time taken by ACK frame to reach sender from the receiver. This is because the ACK frames are piggybacked with the data frames that are coming from the receiver for the sender (maybe a bit later).
Aforementioned, we must now calculate the number of frames transmitted during propagation time (rather than round trip time)

$No.\ of\ frames = \left(25*10^{-3}*10^{6}\right)/10^3 = 25$

Thus, we will need minimum of $5\ bits$ to represent sequence number distinctly.
HTH


Stroke Width Transform: Gradient Direction Computation

If $Gx = 0$ and $Gy > 0$, then we use $Gy / 0 = + \infty$. Note that $\arctan +\infty = 1$.

If $Gx = 0$ and $Gy < 0$, then we use $Gy / 0 = -\infty$.  Note that $\arctan -\infty = -1$.


Weak complexity classes will satisfy $\mathcal{D}^{\oplus P} = \oplus P$. For example, $P^{\oplus P} = \oplus P$.

Strong complexity classes will satisfy $\mathcal{C}^{\oplus P} = \mathcal{C}$. For example, $\mathsf{PSPACE}^{\oplus P} = \mathsf{PSPACE}$.


What kind of operations can we do with bits?

If you think about it, there are $2^4 = 16$ possible ways of combining two bits to give a single-bit ouput (AND, OR, NOR, NAND, XOR, ...).  Can you work out what they all are? This is because there are four possible input combinations ($00$, $01$, $10$, $11$) and any subset of those can be mapped to~$1$.  But we could combine more than two bits to give a single bit output – can you work out how many operators there are that take $k$ bits as input and output one bit?

And we're not even restricted to one bit of output: in general, we can have any number of bits of input and any number of bits of output. You mentioned shifts, which map $k$ bits to $k$ bits, as an example of this.

Overall, there are infinitely many ways of combining bits.


Computing Nash equilibria in discrete auctions

If there are only two players, you could use integer linear programming.

I'll introduce some zero-or-one integer variables to encode the (unknown) bidding functions (via a one-hot encoding).  Let $x_{v,b}=1$ if player $0$'s bid is $b$ when their valuation is $v$, and $0$ otherwise; and $y_{w,c}=1$ if player $1$'s bid is $c$ when their valuation is $w$, and $0$ otherwise.  In this way, if there are $n$ possible valuations, we obtain $2n^2$  zero-or-one integer variables.  We will write down linear inequalities on these variables that characterize the  optimality condition, then use an integer programming solver to find a solution that satisfies all of these inequalities.

Note that if player $0$'s valuation is $v$ and player $1$'s valuation is $w$, then player $0$'s payoff (in a first-price auction) is

$$\sum_{b>c} x_{v,b} y_{w,c} (v-b).$$

Therefore, if player $0$'s valuation is $v$, player $0$'s expected payoff is

$$\sum_w p_1(w) \sum_{b>c} x_{v,b} y_{w,c} (v-b),$$

where $p_1(w)$ represents the probability that player $1$ gets valuation $w$.  Now, we need this to be at least what it would be if player $0$ used any other bid for valuation $v$, i.e., any other choice of $x_{v,\cdot}$'s.  If there are $n$ possible valuations, there are only $n$ possible bids, so we obtain $n$ inequalities

$$\sum_w p_1(w) \sum_{b>c} x_{v,b} y_{w,c} (v-b) \ge \sum_w p_1(w) \sum_{b'>c} y_{w,c} (v-b'),$$

where we obtain one such inequality for each possible value of $b'$.  (The sum on the left-hand-side is over $w,b,c$ that satisfy the condition $b>c$; the sum on the right-hand-side is over $w,c$ that satisfy the condition $c<b'$.)

This is a quadratic inequality.  We'll turn it into a linear inequality using the techniques of Express boolean logic operations in zero-one integer linear programming (ILP).  In particular, introduce new zero-or-one variables $t_{v,w,b,c}$, with the intention that $t_{v,w,b,c}=x_{v,b} y_{w,c}$.  This can be enforced using the linear inequalities $t_{v,w,b,c} \ge x_{v,b} + y_{w,c} - 1$, $t_{v,w,b,c} \le x_{v,b}$, $t_{v,w,b,c} \le  y_{w,c}$, $0 \le t_{v,w,b,c} \le 1$.  Now the optimality condition becomes

$$\sum_w p_1(w) \sum_{b>c} t_{v,w,b,c} (v-b) \ge \sum_w p_1(w) \sum{b'>c} y_{w,c} (v-b'),$$

for each $v,b'$.  We obtain one such inequality for each $v$ and each $b'$.  These $n^2$ inequalities ensure that player $0$'s strategy will be optimal (given player $1$'s strategy).

Then, add similar inequalities to require player $1$'s strategy to be optimal (given player $0$'s strategy).

Also add the $n^2+n$ constraints that $0 \le x_{v,b} \le 1$ and $\sum_b x_{v,b}=1$ to require the $x$'s to correspond to a bidding function, and similarly for the $y$'s.

Finally, take all of these inequalities and feed them to an off-the-shelf integer linear programming solver.  If it finds a solution, then you have found a Nash equilibrium for your game.  ILP is NP-hard, so there is no guarantee that it will terminate in a reasonable amount of time, but in my experience often the solvers can handle surprisingly large systems of inequalities.

The same approach can handle all-pay auctions as well as first-price auctions.

In practice, you might be able to speed up the solver by adding some extra constraints to help it identify a solution faster.  In particular, I have a hunch that without loss of generality the optimal bidding function can be assumed to be monotonic: if we increase my valuation, my bid should never decrease.  We can add extra inequalities to the system to characterize this additional assumption, and this might narrow the search space and thus help the ILP solver find a solution more rapidly.

One big limitation is that this seems limited to two players (or a very small number of players).  If there are multiple players, the number of variables and inequalities will explode, and this might not be an effective approach.


Amortised analysis of binary heap insert and delete-min

First, for a bit of clarifying terminology:  rather than proving an amortized insertion cost of $O(\lg n)$ and an amortized deletion cost of $O(1)$, you are using those amortized costs to prove something about the total cost of a sequence of insertions and deletions, starting with an empty heap.  This might be a subtle distinction, but it is fairly important (at least to me).  If you allow yourself to start from a non-empty heap, you would also need to allow yourself to start with a $\Theta(n \lg n)$ potential, or else the deletion amortized cost won't work.  Or, if you were to add in an operation for the worst-case linear time build-heap operation, you would also need for that linear time operation to add $\Theta(n \lg n)$ to the potential function.

To use your desired amortized runtimes, each insertion has to prepay for a deletion to come later.  So, for instance, when inserting into a heap of size $n$, you can pay for the actual insertion $O(\lg n)$, but your amortized cost will pay that plus an additional $O(\lg n)$ for the worst-case runtime of deleting from a heap of size $n+1$.  Now, every time you delete from a non-empty heap?  That deletion's actual cost has already been prepayed by a previous insertion's amortized cost.  It costs 0 (amortized) to delete.  The only deletions that you still need to pay for are the ones from an empty heap, for when your deletions outnumber prior insertions, and those cost $O(1)$.

While these bounds are fine to use for a proof of efficiency for a sequence of insertions and deletions, they are slightly odd, in that in real life, the deletions generally take expected $\Theta(\lg n)$ time, and insertions take expected $\Theta(1)$ time, for some reasonable definitions of operating on a random heap of size $n$.

While I have presented this in terms of "prepaying" (or the accounting method), in this case, just writing it down as a more formal equation directly transforms it into the potential function method.  You will be able to prove that the potential of a heap with $n$ elements is at least $\sum_{i=1}^n f(i)$ where $f(i)$ is the worst-case price to delete the min item from a heap if $i$ elements.  You already start your question with a given $O(\lg i)$ bound on $f(i)$.


Prove $\epsilon(S\cap T)\subseteq S \cap T$

Since your definition of $\epsilon$-closure isn't really a definition, it is impossible to prove anything using it. Instead, let me use the following definition: the $\epsilon$-closure of a set $S \subseteq Q$ consists of all states $x \in Q$ which are reachable from a state in $S$ by a (possibly empty) $\epsilon$-path (which is a path consisting of $\epsilon$-transitions).

Suppose that $\epsilon(S) = S$ and $\epsilon(T) = T$, and let $q \in \epsilon(S \cap T)$. Thus $q$ is reachable by a state $r \in S \cap T$ via an $\epsilon$-path. Since $r \in S \cap T$, in particular $r \in S$, and so, by definition, $q \in \epsilon(S) = S$. Similarly, $q \in \epsilon(T) = T$. Therefore $q \in S \cap T$.


Is following grammar has language which is inherently ambiguous?

Your grammar $$\begin{eqnarray}S &\to& aSb &|& A \\ A &\to& aaAb &|& \epsilon\end{eqnarray}$$ is indeed unambiguous. The production $S \to A$ must occur precisely once in any derivation, and the productions which precede it cannot be replaced with any productions which succeed it or vice versa.


For data-path cycles in MIPS, what determines wheter a control signal gets the "don't-care" value?

A control signal controls a single component in the architecture. When the command that is now active is not using the component this control signal controls, the control signal gets the "don't care" value.

The principle is that you don't want to restrict yourself for not using this component (=0 value), because any constraint will create a more complex logic inside the cycle. Instead you are freeing yourself from this choice by assigning the control signal with a "don't care" value, which means you can minimize the logic in the cycle and allowing the irrelevant component to work in the background (with no obvious bad consequences).

As you mentioned in your example, while using the sw command, you don't need to read anything from the memory. You could assign MemRead with the value 0, but why overkill it? It's easier to don't care if it reads data from the memory or not (it will read gibberish though), and RegWrite=0 (which in turn controls the writing of what was read from the memory) won't allow the use of this read anyway.


Smallest(k) in red-black tree. How is it O(logn)?

The idea is to use an algorithm whose running time is linear in the height, which is $O(\log n)$ in a red-black tree. As JarkkoL mentions, you can maintain a count of the number of children in every subtree without effecting the asymptotic running time of the usual operations (insert, delete and search). You then go down the tree. Suppose you're at a vertex $v$ whose two children have subtrees of sizes $L,R$. If $k = L+1$ then $v$ is the $k$th smallest. If $k < L$ then you descend to the left child. If $k > L$ then you descend to the right child and replace $k$ by $k-L-1$. This algorithm runs in time $O(\log n)$.


How do I prove that SPACE($n^{555}$) $\neq$ NP?

According to the space hierarchy theorem, there is a language in $\mathrm{SPACE}(n^{556})$ which is not in $\mathsf{SPACE}(n^{555})$. A padded version of this language will be in $\mathsf{SPACE}(n^{555})$. If the latter is equal to $\mathsf{NP}$, then the original language would also be in $\mathsf{NP} = \mathsf{SPACE}(n^{555})$, since we can implement padding while remaining inside $\mathsf{NP}$.

I'll let you flesh out this argument.


How to find size of each tree in a forest?

You can use any number of Dynamic Connectivity data structures, namely, an euler tour dynamic connectivity tree.

To summarize the reference, if you label the vertices of the original tree $T$ according to the first (denoted $label_f$) and last (denoted $label_l$) euler-tour visit order on $T$, you can maintain a BST $T^*$.

Each node $x$ in $T$ is linked to two nodes in $T^*$: $v_1$, $v_2$, where $key(v_1) = label_f(x)$ and $key(v_2) = label_l(x)$. Note $|T^*| = 2n $ and BST operations on $T^*$ will cost $O(\log n)$

Now, we can support the following operations on $T$:

$cut(u, v)$: Disconnect the edge $(u,v)$. Denote $x$ the vertex whose $label_f$ is lesser. It is done simply by splitting from $T^*$ the interval $[label_f(x),label_l(x)]$ which can be done in $O(\log n)$ by splitting and merging.
$findroot(v)$: Since the root of the tree has the minimum $label_f$, the root of $v$ will be the minimum node in the euler-tour BST in which he belongs

Since each node $x$ in $T$ is represented by exactly two nodes in $T^*$, by simply saving rank (tree size) on the euler tour BST ($T^*$), and dividing by $2$ you can answer the question "How many nodes are in the tree of $x$?" in $O(1)$, granted you are willing to pay $O(\log n)$ each time you disconnect an edge.


Find out duplicate number between 1 to N numbers

Here is the question:

You are given a list of length $n+1$ which contains the numbers $1,\ldots,n$, one of them appearing twice (and the rest appearing once).
Find the number which appears twice.

The sum of numbers from $1$ to $n$ is $\frac{n(n+1)}{2}$, so if you subtract that from the sum of the list you get the number appearing twice.


occur-check, does nominal unification has it?

Yes, it has the occur check. The ~variable transformation rule of nominal unification has a condition which states

   provided X does not occur in t

what it is saying is exactly occur check.


Does the performance of matrix multiplication depend on the storage of the array?

The asymptotic complexity will not change with relation to how the matrices are laid out in memory, but the actual running time of the matrix multiplication will be very dependent upon the memory layout.  There are two papers that I know of that go into detail about this, one by McKellar in 1969 and another by Prokop in 1999.  Prokop's paper defines the concept of cache complexity which is related to the number of cache misses the algorithm will incur.

The two papers can be found here:
http://supertech.csail.mit.edu/papers/Prokop99.pdf and here: http://dl.acm.org/citation.cfm?id=362879

The short version is, an $O(n^3)$ algorithm will still be an $O(n^3)$ algorithm (assuming you are using the straightforward matrix-multiply).  However, by taking into account the memory hierarchy of the system, you can significantly speed up that $O(n^3)$ algorithm.


Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?

I can list three candidate approaches.  I'm not sure how to choose among them -- you might need to experiment among them to see which will work best in your situation.
Approach #1: sweepline algorithm
This can be solved with a straightforward application of a sweepline algorithm.
Sweep a vertical line from left to right, with increasing $x$-values.  At any value of $x$, you'll have a binary search tree that, given $y$, lets you look up which polygon the point $(x,y)$ is contained in.  There are two key ideas in sweepline algorithms: you only need one tree for each interval of $x$-values between two adjacent "events" (here each event is an intersection of two line segments from the exteriors of the polygons), so you only need only $O(n)$ binary search trees; and, each binary search tree differs from the previous one by a single insertion or deletion, so you don't need to store all of them separately, but you can store them jointly using a persistent data structure.
Now this makes it easy to solve your problem.  At any moment in time, we know the $(x,y)$ position of the point and can look up which polygon it is contained in and a trapezoid inside that polygon it is contained in.  As the point moves, once it leaves that trapezoid, we can query the data structure again.  Each lookup into the data structure takes $O(\log n)$ time, so will be efficient.
Approach #2: Graph of polygons
As a precomputation, build an undirected graph of polygons, where each polygon is a vertex, and two polygons are joined by an edge if they are adjacent (overlap in a point or line segment).  Store this graph in an adjacency list representation.  Also, find the polygon that contains the initial position of the point by any algorithm (e.g., linear scan over all polygons).
Note that you can answer point-in-polygon queries (given a point and a polygon, is the point inside that polygon?) in time linear in the number of vertices of the polygon.
Now, the algorithm is simple.  Watch the movement of the current point, and as soon as it leaves the current polygon, check which polygon it has moved into by doing a point-in-polygon query on each adjacent polygon.  Thus, when it leaves the current polygon, the work is proportional to the number of neighboring polygons, not to the total number of polygons.
There are various optimizations and improvements available:

Optimization 1: We can speed up the process of finding when the point leaves the polygon it is currently inside.  If we are guaranteed that once the point leaves a polygon, it will never come back to it, then we can use binary search over time to find the first instant when it has left the polygon.  Each iteration of binary search requires one point-in-polygon query and we do logarithmically many iterations.  If we don't have that guarantee, but we have an upper bound on the speed and/or acceleration and/or turning radius for the movement of the point, we can compute a lower bound on the time to leave the current polygon and return to it (based on the current position of the point and the polygon it is contained within), and use a modified binary search where we avoid jumping further into the future in any one step than given by that bound.

Optimization 2: We can sort each adjacency list.  Consider the adjacency list for polygon $P$.  Suppose the perimeter of $P$ has length $\ell$.  If you walk along the perimeter of $P$ starting at some point on the perimeter and returning to it, this maps each point on the perimeter to a number in the range $[0,\ell)$, which gives a total order on points on the perimeter.  This yields a total order on the polygons adjacent to $P$: map each neighboring polygon to the points of intersection on the perimeter of $P$, map those to numbers/intervals in $[0,\ell)$, then sort by that.  (We can resolve ties as follows: if two neighboring polygons both overlap with $P$ at the same point $p$, where $p$ is on some face of $P$, then imagine extending outward by a tiny bit $\epsilon$ from that face and look at the intersection with those two polygons.)  So, sort each adjacency list in this way, as part of the precomputation/setup phase.
This now speeds up the process of determining which new polygon the point has entered, when it leaves the current one: instead of using a number of point-in-polygon tests that is linear in the number of neighboring polygons, it goes by the log of the number of neighboring polygons.

Optimization 3: Compute the bounding box for each polygon.  Now, before doing a point-in-polygon test, you can first check whether the point is in the bounding box, which will enable quickly rejecting some polygons.
You could also use this to speed up finding the polygon the initial position is within. Store all bounding boxes in some appropriate data structure (e.g., a quadtree).  Now, given a point, use that data structure to enumerate all bounding boxes it is contained in, then test each with a point-in-polygon test.

Approach #3: Graph of triangles
During a precomputation, triangulate each polygon, i.e., decompose it into a union of triangles.  Now combine all these triangles, build a graph of triangles, and proceed as in approach #2, but using triangles instead of objects.
This replaces each point-in-polygon test with a point-in-triangle test, which is much faster; but because the point will traverse many more triangles than polygons, the number of iterations might be much larger.  I'm not sure which approach will be faster in the end.
Also, the type of triangulation used might affect performance.  I'm not sure whether it is better to choose a triangulation that minimizes the variance of the degrees in the graph or one that maximizes the variance (e.g., a fan decomposition).


Image registration using gradient descent

It doesn't feel wrong to me.

A rotation by a small amount, say one degree, changes the location of an object in the image by many pixels.  For instance, suppose you have a 1000x1000 image, and you rotate it by one degree around the upper-left corner.  Then an object near the upper-right corner moves upward/downward by about 17 pixels.  There is "leverage" proportional to the size of the image; rotate a long lever by a small rotation, and the end of the lever still moves a large way.

In contrast, a translation by a small amount, say one pixel, changes the location of an object in the image by only a little.  For instance, if you have that same image and you translate by one pixel, then the object moves by only 1 pixel.

So it is not surprising (to me) that the gradient in the first case might be much larger than the gradient in the second case.


Finding independent sets so that all nodes are hit frequently

Approach 1: Use ILP

If you want an algorithm that might work in practice as long as the graph is not too large, one approach is to formulate this as an integer linear problem.

That's pretty straightforward in this case.  We'll have $k|V|$ integer variables.  In particular, $x_{v,i}$ will be $1$ if the vertex $v$ is included in the independent set in the $i$th iteration and $0$ otherwise.

First, let's encode the constraint that the $x_{\cdot,i}$ have to encode an independent set in each iteration.  We get $0 \le x_{v,i} \le 1$ and

$$x_{v,i} + x_{w,i} \le 1 \quad \forall (v,w) \in E.$$

Next, note that $x_{v,1} + x_{v,2} + \dots + x_{v,k}$ counts how many times each vertex is covered across the $k$ iterations.  We want this to be at least $r_v$, so we get the constraint

$$x_{v,1} + x_{v,2} + \dots + x_{v,k} \ge r_v \quad \forall v \in V.$$

Now throw an integer linear solver at the problem, and hope that it finds a solution.  The worst-case running time is exponential, but integer linear solvers sometimes work a lot better than you'd expect, so as long as the graph is not too large, it might just work.

If you want to find the smallest $k$ such that this can be solved, use binary search or linear search on $k$.

You can also formulate a similar version that works using SAT, and then throw a SAT solver at it.  It's a little more complex because you'll need to encode the constraint $x_{v,1} + x_{v,2} + \dots + x_{v,k} \ge r_v$ in SAT, but it can be done (e.g., by building a circuit for a small adder and then translating it to SAT using the Tseitin transform).

Approach #2: A greedy heuristic

Here is an alternative approach, that might work even on larger graphs.  It won't find the optimal solution, but it might find a solution that is not too much worse than the optimal solution.

The problem reminds me of a set cover problem: in each iteration you select one set, and you want the union of the sets to cover the universe.  One natural approach to set-cover-like problems is to try to apply the greedy algorithm for set cover: in each iteration, choose an independent set that gives you as much progress as possible.

Let me start by assuming $r_v=1$ for all vertices $v$, for simplicity.  Then you could use the following algorithm:

Initially all vertices are uncovered.  Set $i=1$.
Find an independent set $I$ that covers as many of the uncovered vertices as possible.  Choose that one, and output it as the independent set $I$ as the one to use in the $i$th iteration.  Increment $i$ and go back to step 2.

You can now plug in any algorithm you like for finding independent sets, including a heuristic or approximation algorithm.  There's lots written on that subject so you might be able to re-purpose any of a number of different algorithms.

What about the general case where the $r_v$'s are arbitrary?  Well, in any given iteration, you can evaluate each candidate independent set by how much incremental coverage it adds, where now the coverage is given by the sum of the counters on all of the vertices.  So, in each iteration, choose the independent set with the largest incremental coverage that you can find.  This might give a reasonable approximation algorithm for your initial problem.


Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

DPBP is NP-complete.

I give a reduction from the partition problem. Define $\text{PART}=\left\{ {x_1,x_2,\ldots,x_n\in \mathbb{N}|\exists I:\sum_{i\in I}x_i=\sum_{i\not\in I}x_i} \right \}$.

Given an instance $\left \{ {x_1,\ldots ,x_n} \right \}$ of PART, we build a graph in the following way. For each $i\in \left \{{1,\ldots,n} \right \}$, we have a diamond like component. These components are connected in a row, starting from $s$ and ending at $t$:

The weight of the upper left edge in the $i\text{'th}$ component is $x_i$ and all other edges have weights $0$. The constant bounding the paths weight is $M=\frac{1}{2}\sum_{i=1}^n{x_i}$.

A path in this graph between $s$ and $t$ travels through all components. In order for two edge disjoint paths to fit in, each path should travel threw all components, taking either the upper or lower part of each.

Given a partition $I={i_1,\ldots ,i_k}\subset \left\{ {1,\ldots,n} \right\}$, let the first path go threw the upper parts of the components with indexes in $I$, and threw the lower parts of the other components. Since traveling threw the upper part of the $i$'th component costs $x_i$, the weight of this path is exactly $\sum_{i\in I}x_i$. In case the given partition is proper, this sum is exactly $\frac{1}{2}\sum_{i=1}^n x_i = M$.

The second path will be the complement path, i.e., it will go threw the lower part of each component with an index in $I$, and threw the upper part of each component with an index not in $I$. Therefore, its weight will be $\sum_{i\not \in I}x_i=\sum_{i=1}^n x_i - \sum_{i\in I}x_i=M$ as well.

Thus, the two paths are edge disjoint and bounded by $M$ as required.

Now, assume that we are given a pair of edge disjoint paths between $s$ and $t$, so that the weights of each is at most $M$. By the construction, the weight of each is exactly $M$. Let $I=\left\{ {i_1,\ldots,i_k} \right\}$ be the components with an upper part traveled by the first path. Obviously, $I$ partitions the $x_i$'s properly.


Functional data structure fast to add and unorded deletion

My recommendation is a straightforward hash map. If you have a good hash function for your distribution of keys, the time complexity for adding and removing (with an arbitrary key) is amortized $O(1)$.

EDIT: Hash maps can be purely functional if you want (example), they just become a whole lot less efficient. I don't think it's theoretically possible to get lower than $O(\log n)$, which is what you get from using a red-black tree as the backend. The linked HAMT implementation is also $O(\log n)$, just with a significantly smaller hidden constant.


Number of different output labels in Local Binary Pattern

A pattern with uniformity measure exactly 2 is determined by: the value $b$ of bit 0, the position $i>0$ of the first bit that is different from bit 0 and the position $j$ of the first bit after the $i$th that is different from bit $i$.  (We may have $j=0$, for example in the pattern 00001111, which has $b=0$, $i=4$, $j=0$.)  How many choices are there for the triple $(b,i,j)$? Clearly, there are two choices for $b$.  For $i$ and $j$, there are  $\tfrac12(P-1)(P-2)$ choices with $i<j$ and $P-1$ choices where $j=0$. Thus, the total number of choices for $i$ and $j$ is
$$ \tfrac12(P-1)(P-2) + P-1 = \tfrac12P(P-1)\,.$$

To that, you need to add three more labels: all zeroes, all ones and the label for all patterns of uniformity measure strictly more than 2.


For practical computing purposes, every algorithm is O(1)?

Sure. Time and memory are both finite, thus $O(1)$. But that isn't a very interesting (useful) result. Complexity is studied precisely because we do care how much time (or memory, or whatever other measure is of interest) algorithms take as a function of the input (size), even if we aren't willing to wait "finite, but very large" time nor to equip the machine with "finite, but very large" memory. We'd want to have an idea of how long we have to wait, or how much memory is enough.


Machine learning algorithm(s) for recognizing simple graph patterns

I suspect machine learning is the wrong approach.  Instead, I suspect you will do better to define a metric and measure the metric, or define a hypothesis and use hypothesis testing.  You are not trying to predict the future evolution of these values; that's something that ML might be suitable for, but that's not what you're trying to do, so ML doesn't seem like the right tool for the job.

Let me suggest an approach.  If $f(t),g(t)$ are the values of the measurements at time $t$, define $D(t) = |f(t)-g(t)|$ (the absolute value of the difference).  $D(t)$ measures how close they are.  Then, you want to test whether $D(t)$ is increasing or decreasing.  If $D(t)$ is decreasing, then you have a situation of "convergence"; if $D(t)$ is increasing, then you have a situation of "divergence".

How can you test whether $D(t)$ is increasing vs decreasing, over some time period?  Here's one simple approach.  You could separate your time window into two halves, the first half and the second half.  Calculate the average value of $D(t)$ over the first half, say $\mu_0$, and the average value of $D(t)$ over the second half, say $\mu_1$.  Now you can compare $\mu_0$ to $\mu_1$, to determine whether it is increasing or decreasing.

Alternatively, another approach would be to use simple linear regression on $D(t)$ to fit a linear model $D(t) \sim \alpha t + \beta$, and then test whether the slope $\alpha$ is greater than zero or smaller than zero.

However, one problem with this is that your conclusion might be confounded by noise: it might be that $D(t)$ is neither increasing nor decreasing, but all you're seeing is statistical noise.  So can you separate out the case where $D(t)$ is increasing from the case where $D(t)$ is decreasing?

The answer is yes: you can test for statistical significance using hypothesis testing.  If you observe $\mu_0 > \mu_1$, you can use a hypothesis test to test whether this difference is statistically significant (e.g., using a permutation test).  Or, if you fit a linear model and find $\alpha > 0$, you can use a hypothesis test to test whether the difference from zero is statistically significant (this is covered under standard textbooks on linear regression).

There's lots more one can say about hypothesis testing, but this should give you the general approach.  The short version is: don't use machine learning; using an appropriately chosen statistical measure or statistical hypothesis test.


3xN tiling problem with blocks of size 3x1 or 2x2

Here is a systematic way to approach it.  I suggest you define three values:

$A_0(n)$ is the number of ways to tile a $3 \times n$ region.

$A_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered.

$A_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of it already covered.

Then you should be able to express each $A_i(n)$ in terms of $A_j(m)$ for $m < n$.  This gives you a mutual recurrence relation for these three values.  It is easy to construct these recurrent relations based on a case analysis of how the leftmost column is covered.

You can then compute these using dynamic programming, in order of increasing $m$.  Or, you can substitute into each other and get a single recurrence relation for $A_0(n)$ in terms of $A_0(m)$ for $m<n$, if you prefer.

Regarding your solution:

Yeah, you're missing something.  For instance, a solution could start

┌───┬───┬─────┐
│   │   ├─────┤
├───┴─┬─┴───┬─┴
└─────┴─────┴──

and continue from there; that won't be counted in your case analysis.


Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?

Without loss of generality, assume $p_i> 0$. Otherwise we can set all $x_i=0$ where $p_i\le 0$ and consider the separated sequences by these $i$'s respectively.

Let $P(k)$ and $Q(k)$ be the highest possible points we can get for $p_1,\ldots,p_k$ where $x_{k-1}x_k=11$ and where $x_{k-1}x_k\neq 11$ respectively.

If the last two bits are $11$, $x_{k-2}$ must be $0$, and there are no constraint for $x_1,\ldots,x_{k-3}$, hence
$$P(k)=p_{k-1}+p_k+\max\{P(k-3),Q(k-3)\}.$$

If the last two bits are not $11$, there are two cases: $01$ or $10$. Note to get the highest points, the last two bits cannot be $00$.

If the last two bits are $01$, there is no constraint for previous bits, the highest possible points are $p_k+\max\{P(k-2),Q(k-2)\}$.
If the last two bits are $10$, then $x_{k-3}x_{k-2}\neq 11$, the highest possible points are $p_{k-1}+Q(k-2)$.

So

$$Q(k)=\max\left\{p_k+\max\{P(k-2),Q(k-2)\},p_{k-1}+Q(k-2)\right\}.$$

Use the two recursion formulas above, you can compute the final result $\max\{P(n),Q(n)\}$.


Construct one PDA for $n=m$ and another one for $n=2m$. Branch to one of them using an $\epsilon$ transition at the very beginning.


Is a language whose Turing Machine doesn't halt for some positive cases but for others does not recursive?

There are two important misunderstandings in your question.

You talk about "the Turing machine" for a language but there isn't just one: in fact, if a language is recursive (or RE) then there are infinitely many Turing machines that decide (or accept) it.
If a Turing machine decides a language $L$ then, by definition, it accepts every input in $L$ and rejects every input not in $L$ and, therefore, it halts on every input. It doesn't make sense to talk about a Turing machine deciding a language but not halting on some input, or not accepting some string that's in the language.

With that in mind, a language $L$ is:

Recursively enumerable if there is a Turing machine that accepts every string in $L$ and does not accept any string not in $L$. It may loop or reject strings not in $L$.
Recursive if there is a Turing machine that accepts every string in $L$ and rejects every string not in $L$.
Recursively enumerable but not recursive if there is a Turing machine that accepts every string in $L$ and does not accept any string not in $L$, but no TM that accepts everything in $L$ and rejects everything not in.  The "but..." part can be rephrased as "every Turing machine that accepts every string in $L$ must either also accept some string not in $L$ or must loop on some string not in $L$."
Not recursively enumerable if every Turing machine either accepts at least one string not in $L$, or loops or rejects at least one string in $L$.

For your specific language, I'm going to assume that $\Sigma=\{a,b\}$. If not, then the notation gets a little uglier but nothing fundamental changes.

If $L$ is RE but not recursive, then
$$L' =\{aw\mid w\in L\} \cup \{bw\mid w\notin L\}$$
is not RE. suppose it is RE and is accepted by some Turing machine $M$. Then we can decide if $w\in L$ by simulating $M(aw)$ and $M(bw)$ in parallel until one of them accepts.  If $M$ accepts $aw$, then $w\in L$; if it accepts $bw$, then $w\notin L$, and one of these two things must happen. This contradicts the assumption that $L$ is not recursive.


Regularity of unary languages with word lengths the sum of two resp. three squares

Let's start with $L_2$. It is known that the upper density of integers which are the sum of two squares is 0. If $L_2$ were regular then it would be eventually periodic, and so, since its upper density is 0, finite. But we know that there are arbitrarily large integers in $L_2$, so that $L_2$ cannot be regular.

Regarding $L_3$, consider the words $w_k = 1^{4^k 7}$. I claim that for $k < \ell$, the words $w_k,w_\ell$ are inequivalent. Indeed, $w_k 1^{4^k 8} \notin L_3$ while $w_\ell 1^{4^k 7} \in L_3$. The Myhill–Nerode criterion then shows that $L_3$ is irregular.


Depends on how deep you want to go.  I believe Russell was the guy who introduced the concept in a specifically set-theoretic context, but the concept itself is as old as the hills, it's really the notion of universals and particulars expressed in a modern mathematical / computational form.  I wouldn't be surprised if Liebniz did something vaguely like types, if you look at his stuff in the right way.

You might have better luck at the History of Math and Science exchange.


Relationship between Deterministic Finite Automata languages

There are a wealth of set theory symbols that are in wide usage. I have seen or used most of those symbols .

In particular, "$L(M) \supset L(M')$" means $L(M) $ is a superset of $L(M')$, but $L(M)$ is not equal to $L(M')$. This is consistent with the explanation given by Wikipedia. To be more specific, it means all words in $L(M')$ are in $L(M)$, but at least one word is in $L(M)$ but not in $L(M')$.

A simple example of that situation can be the following. $M'$ is the finite automaton depicted at Wikipedia example with $S_0$ being the only accepting state. $M'$ accepts words with even number of 0's. Let $M$ be the same as $M'$ except that both states are accepting states. Then $M$ accepts all words.


Assumption on weights in threshold circuits

Given $w_1,\ldots,w_n,t$, let $X$ be the set of assignments such that $\sum_i w_i x_i \geq t$, and consider the linear program with variables $z_1,\ldots,z_n$ and the $2^n$ constraints
$$
\begin{align*}
\sum_i z_i x_i \geq +1 & (x_1,\ldots,x_n) \in X \\
\sum_i z_i x_i \leq -1 & (x_1,\ldots,x_n) \notin X
\end{align*}
$$
This linear program (with a constant objective function) is feasible (since $z_i = w_i/t$ is a solution), and so has a solution $z_1,\ldots,z_n$ which is a vertex. As such, it is the solution of a system of $n$ equations of the form
$$
\sum_i z_i x_i = \pm 1.
$$
Cramer's rule gives each $z_i$ as a ratio of two $n \times n$ determinants of matrices of $0,\pm 1$ entries; in fact the denominator is the same. Each numerator $N_i$ and the common denominator $D$ is at most $n!$ in magnitude, so multiplying everything by $D$, we get an integral solution $N_1,\ldots,N_n,D$, where all the quantities are at most $n! \leq n^n = 2^{n\log n}$ in magnitude.


Efficiently map different codes to rotation-different codes

Here's a more efficient way of doing it. Let's map all the strings of length $n$ into strings of length $n+O(\sqrt{n} \log n)$ with no consecutive string of $0$'s of length more than $\sqrt{n}$. We then add a string $1 0^{a}1$ at the end, where $a \geq \sqrt{n} + 1$. Our mapping isn't always going to give us the same length string, so $a$ can vary.

How do we do this encoding? We need a way of encoding long string of 0's. Let's do that by
taking a string of $0$'s of length at least $t$ and mapping it to a string of zeros of length $t$ followed by a number telling us how many zeros were in it.

$$
\begin{array}{lcl}
0^{\sqrt{n}} & \rightarrow & 0^{\sqrt{n}}10\ldots000 \\
0^{\sqrt{n}+1} & \rightarrow & 0^{\sqrt{n}}10\ldots001 \\
0^{\sqrt{n}+2} & \rightarrow & 0^{\sqrt{n}}10\ldots010 \\
0^{\sqrt{n} +3} & \rightarrow & 0^{\sqrt{n}}10\ldots011 \\
0^{\sqrt{n} +4} & \rightarrow & 0^{\sqrt{n}}10\ldots100 \\
\vdots &\rightarrow & \vdots
\end{array}
$$
Because we will never have a string of more than $n$ 0's, we can use the first $\lceil\log n \rceil$ bits after the string $0^{\sqrt{n}} 1$ to encode the length of the string of 0's. Thus, the most we can increase the length of our code by is a factor of $1 + \frac{\log n+2}{\sqrt{n}}$. After this expansion of the code, we need to add at least $\sqrt{n} + 1$ consecutive 0's. This lets us take $m = n + \sqrt{n}(\log n + 3)$.

I think you can probably get $m \approx n + \log n\,$ by using the ideas behind arithmetic codes, but I don't have time to work the details out right now. If somebody else wants to work them out and post an answer, please feel free to do so.


Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?

Here is one special case that is solvable a bit more efficiently than brute force.  Suppose all of the fixed bits are consecutive and in the least significant bits.  For instance, we are given the desired value for the low $k$ bits.  Then this problem amounts to asking whether there is a divisor $d$ of $c$ such that $d \equiv f \pmod{2^k}$.

In other words, if $T$ is the multiset of prime factors of $c$, we are looking for a submultiset $S \subseteq T$ such that

$$\prod_{x \in S} x \equiv f \pmod{2^k},$$

where $f,k,T$ are given.  Let me sketch an algorithm for this special case.

How can we find a solution to this equation without enumerating all $2^{|T|}$ submultisets?  One way is to take discrete logs and reduce this to a subset sum problem.  In particular, the multiplicative group $(\mathbb{Z}/2^k\mathbb{Z})^*$ is isomorphic to $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2^{k-2}\mathbb{Z})$.  Let $\varphi$ be an isomorphism that maps $(\mathbb{Z}/2^k\mathbb{Z})^* \to (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2^{k-2}\mathbb{Z})$.  Then, we search for a $S$ such that

$$\sum_{x \in S} \varphi(x) = \varphi(f).$$

So, if we can compute $\varphi$ efficiently, this basically reduces to a subset sum problem modulo $2^{k-2}$.  And it turns out that $\varphi$ can be computed efficiently using Hensel lifting (basically, you find the discrete log of $x$ modulo 8, then modulo 16, then modulo 32, and so on; at each step there are only two possibilities for the discrete log, so you try them both).  So, you compute $T^* = \{\varphi(x) : x \in T\}$ and $f^* = \varphi(f)$ and then try to find a submultiset $S^* \subseteq T^*$ such that

$$\sum_{y \in S^*} y = f^*.$$

This is a subset sum problem modulo $2^{k-2}$ (if you allow me to handwave over the $\mathbb{Z}/2\mathbb{Z}$ part of the range of $\varphi$).

And finally, there are algorithms for the subset sum problem that are more efficient than brute force trial-and-error of all subsets.  This then gives you an algorithm for your original problem, in the special case where all the fixed bits are consecutive and in the least least significant bits.

This connection also suggests that your problem is probably not in P.  In particular, it appears that we can show that your problem is at least as hard as subset sum, which is known to be NP-hard.  Therefore, it looks like your problem will be NP-hard, too.


Which algorithms are usable for heatmaps and what are their pros and cons

If I have understood your question correctly (an illustrative example would have been helpful), I would recommend either Gaussian blurring or linear interpolation depending on the behavior you are after. Both are simple and should perform relatively fast even on a handheld device.

Linear interpolation (or rather bilinear interpolation) is simple but requires a square heat sample grid and you get some boundary effects that might be undesirable. The method is the most representative since "empty cells" (i.e., cells without heat information) are simply empty because of sparse sampling and not because they are void of heat. The interpolation tries to fill in the missing heat information in the empty cells by looking at the nearby heat samples.

Cell averaging will give you an equally high response in a cell neighboring the heat sample as in the heat sample cell itself (granted that the average is computed for all cells including the cells containing heat samples). If the average is computed for empty cells only (i.e., for cells with no heat information) then the cells with the heat sample will keep its full signal while adjacent cells will contain an average, which in a sparse sample grid will be 1/8 of the heat sample, resulting in a distribution almost as misleading as only using the original heat samples.

Gaussian blurring with a wide enough kernel is simple and gives a better  representation of the impact of the heat samples than the cell averaging. However, the values in the blurred heat map for the empty cells will only be affected by the heat "spread" from the sample cells. So if the heat map is sparse, there will likely be empty cells on equal distance between two heat cells that do not get any heat information at all.

I hope this helps.


Pumping lemma for context-free languages - Am I doing it right?

Bascially your approach is correct. I have not checked every detail, but have a few remarks:

you miss the cases where v or y include a border like v=0011; here pumping destroys the general structure of the word besides the number relations.
case 1 would have to be done for the 0s and the 2s, too


Is a system of equations derived from mutually recursive ADTs always uniquely solvable?

The initial assumption about such types having at most countably many elements is false. We can use inductive types to define a non-countable type, namely the countably branching trees:
(* Countably branching trees. *)
Inductive Tree : Type :=
  | Leaf : Tree
  | Node : (nat -> Tree) -> Tree.

Lemma nocycle (t : Tree) : forall (f : nat -> Tree), t = Node f -> forall a, f a <> t.
Proof.
  induction t as [? | f H].
  - easy.
  - intros g E n.
    injection E.
    intro E'; destruct E'.
    intro gN.
    now elim (H n f gN n).
Qed.

Corollary uncountable_Tree :
  ~ exists (f : nat -> Tree), forall t : Tree, exists n, f n = t.
Proof.
  intros [f H].
  destruct (H (Node f)) as [n ?].
  now pose (nocycle (Node f) f eq_refl n).
Qed.

In any case, counting elements of types is a tricky business. Consider the following inductive type:
Inductive cow (P : Prop) : Type :=
  | moo : P -> cow P.

Consider any propostion Q : Prop. If cow Q has zero elements then Q is false, and if it has an element then Q is true. So if we could count the elements of cow, we could also tell whether it has zero elements, and would be able to decide an arbitrary proposition, which would give us excluded middle.
You need to restrict the inductive types quite severaly to obtain a small enough family of them whose sizes can actually be counted.


2-SAT Problem with additional constraints on variable?

That is NP-hard by reduction from vertex cover, even when there are no negative literals.

If you meant to count by occurrences rather than just bounding the number of

distinct variables which are true, then use this paper's result and this paper's result.


As Aspass.Jack wrote in the comments, let's first define $L_3$ to be the language where each $a$ is followed by at least 2 $b$'s, and $L_4$ to be the language where each $b$ is followed by at least one $a$.

Now, if let's say you can define CFGs for $L_3$ and $L_4$ with start symbols $S_3$ and $S_4$. Then, we simply need to define a grammer with the transition:
$$S \rightarrow S_3|S_4$$
together with all the transitions from the other 2 CFGs. Hopefully this simplifies your problem.


Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$

Unfortunately your grammar generates only $\epsilon$ (which is not in the language, since $n$ and $m$ are greater than 0), as you don't delete the $A$; moreover you don't control that the number of $A$'s is thrice the numeber of $C$'s.
You can try something like this:
$S\rightarrow aaaS'c$
$S' \rightarrow aaaS'c | B$
$B\rightarrow Bb | b$


Okay, I think I have the solution to this one. It exploits the constraint (no overlaps) and the fact, that even a complex, multiple overlap problem, can actully be seen as a bunch of pairwise confilcts - at the end of the day no two circles can overlap.

Here is how it goes:
Find all points that can be covered by by a given circle and sotre these. Find the furthest point distance and set the radius of the circle to be that distance.
Now we probably have some overlaps. Create a priority queue and enter all the overlaping circles into the queue. The index of the queue is:

(distance from the furthest point) - (distance from the second furthest point).

Then we descrease the radius of the circle with the highest index so that now it's the distance to the second furthest point. Delete the circle from the queue, update the index and re-enter the circle into the queue if it still overlaps with any of the remainging circles. Keep repeating untill there is no more overlap in the system.

The solution is optimal, since the price for retracting the radius is constant (leaving out one point) and the gain is variable (and maximized by teh use of a priority queue).


Finding all marked elements using Grover's algorithm

After discussing the problem with some people from my institute that work on quantum computing, it turns out that one can augment the oracle to not provide elements that have already been found in previous iterations of the search. The trick is to modify Grover's algorithm as follows:

Say, we already know that 2 is an answer (from a previous iteration). After using the oracle to invert the phase of the marked elements within Grover's algorithm, we apply another operation that inverses the phase of the known answers again (thus cancelling the previous inversion for answers that are already known). Accordingly, the inversion about the mean in Grover's algorithm will not amplify the amplitude of these states.


Lower-bound complexities for finding common elements between two unsorted arrays

For the first question, when $m = n$, you can get an easy $\Omega(n\log n)$ lower bound (in appropriate computation models) by taking $A = B$. More generally, following the method outlined here, it seems that (assuming $n \geq m$) you can get a lower bound of $\Omega(\log (m! \binom{n+1}{m})) = \Omega(n\log m)$ by considering the problem of Set Intersection. (In the proof of Theorem 4, fix the order of the $X$s, and vary the order of the $Y$s and their location.)

As for your algorithm, perhaps it modifies the input arrays? Perhaps this is not allowed in the intended computation model, in which the input is read-only, the work tape is read-write, and the output tape is write-only. (This is just a guess.) In any case, it will really help if you explained your algorithm.


Could computer architecture be reworked to support switching from binary to ternary, for example?

Current computers use electronic parts which can easily distinguish between two states, by stating that high voltage = 0 and low voltage = 1, or vice versa. The hardware that is needed to combine two inputs x and y and produce an output equal to NAND (x, y) is very, very simple and any other logic can be produced very easily from this.

Your task in proposing ternary computers: Suggest how with current electronic parts, three states can be represented. Then suggest what would be a primitive operation that combines two ternary inputs and produces an output; what that operation would be, and how you would implement it. Then suggest how you could for example add two integer numbers that are made of 40 trits (I think that's the name, I might be wrong).

Of course your suggestion must not represent a trit using two binary states, because using two binary states you could easily represent four values with the same effort, which would surely be more efficient. So you might represent 0 = low voltage, 1 = medium voltage, 2 = high voltage. Have fun doing that reliably. (One problem that you have is that using low and high only, you can change states with force and therefore quickly. If you needed to change a state from high to medium voltage, you'd have to be careful not to overshoot to low voltage, so this would likely be slower).

Now it seems you not only want to implement ternary arithmetic, but you want to switch the hardware on the fly between binary and ternary. That's not running before you can walk, that's running before you even figured out that crawling might be a possibility.


Is there a term for a tree where the values of the children add up to a fixed value?

I believe it is creatively called a "sum tree."

Algorithmically it's not especially useful nor interesting because it is not efficiently modifiable.


A string representation of any Turing machine

Consider a Turing machine with $n$ tape symbols and $m$ states. We can assume that the symbols and the states are ordered, so that we can talk about the first, second, ..., $n$th tape symbol, and the first, second, ..., $m$th state. (This is similar to your idea of counting Turing machines up to isomorphism.) So without loss of generality, the tape alphabet is $\{1,\ldots,n\}$ and the states are $\{1,\ldots,m\}$. We will encode this Turing machine as the following sequence of statements in English: (the notation $\langle n \rangle$ means to replace $n$ with its decimal representation)

The number of tape symbols is $\langle n \rangle$.
The number of states is $\langle m \rangle$.
The starting state is $\langle s_0 \rangle$. [Replace $s_0$ with the starting state]
The accepting states are $\langle s_1 \rangle$, ..., $\langle s_k \rangle$. [Replace $s_1,\ldots,s_k$ with the accepting states]
When in state 1, upon reading symbol 1, write symbol $\langle \sigma \rangle$ and move $\langle D \rangle$ [Replace $\sigma$ with the tape symbol and $D$ with either "left" or "right"]
...

This is a description in English over a finite alphabet. In particular, it can be represented in ASCII. So there are only countably many descriptions.

As usul mentions, we tacitly assume that the underlying representation of everything in mathematics is a set, just like the description of everything in computers is in binary. Not all sets are finite, but if you only use hereditarily finite sets, then you can avoid forcing the tape alphabet to be $\{1,\ldots,n\}$, and instead allow arbitrary hereditarily finite sets. However, that doesn't buy you anything (unless you care about this point for philosophical reasons).

More generally, you might be worried that when I describe a Turing machine I use the symbol $\diamond$, a symbol not covered by the above (it's a set-theoretic "atom"), so this Turing machine doesn't have a description in my formalism. To counter this, I suggest you provide the description of your Turing machine as a LaTeX document (which is what I used when describing the machine in the first place). LaTeX has a finite alphabet (or finitely many possible finite alphabets), so again everything is countable.


Solution to the recurrence T(n) = 2T(n − 3)

It is easy to see the first nine terms of $\small T(n)$ is:

$$
\small
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
\color{red}{T(1)} & \color{blue}{T(2)} & \color{olive}{T(3)} & \color{red}{T(4)} & \color{blue}{T(5)} & \color{olive}{T(6)} & \color{red}{T(7)} & \color{blue}{T(8)} & \color{olive}{T(9)} \\ \hline
1 & 1 & 1 & 2 & 2 & 2 & 4 & 4 & 4 \\ \hline
\end{array}
$$

  Observation: For integer $\small k \geq 0$, $\small T(3k+1) = T(3k+2) = T(3k+3)$. You can prove it by induction, where the base case is $\small T(1) = T(2) = T(3)= 1$.

Given $\small n$, let $\small k$ be the smallest integer with $\small 3k \geq n$. In other words, $\small k = \lceil n / 3\rceil$. By the observation above, $\small T(n) = T(3k)$. Therefore, we have
$$
\small
T(n) = T(3k) = 2\cdot T(3(k-1)) = 2^2\cdot T(3(k-2)) = \cdots = 2^{k-1}T(3) = 2^{k-1} = 2^{\lceil n / 3\rceil - 1}
$$


Is there a "well known" example of a constraint satisfaction problem on a 3-element set which is polynomial-time solvable?

If you want a graph, it needs to be bipartite. Hence the path of two edges or any subgraph thereof. (Here I am following the convention that graphs have no loops. As David Richerby points out in a comment, graphs with loops also have polynomial-time CSPs (by virtue of triviality).)

A more interesting example is linear algebra over the three-element field: The domain is the set of congruence classes $\bmod 3$ and the constraint relations are given by linear equations.


Regular expression for a string not containing a set of substrings

Hint. Let $A = \{0,1\}$. A regular expression for the complement of your language $L$ is $A^*(101 + 001)A^* = A^*A01A^*$. Now, as Shaull reminded you, $L$ and its complement have the same minimal complete DFA, up to the final states. It is actually relatively small.

If you prefer, you could also take a purely combinatorial approach. Observe that the strings you want to avoid are $101$ and $001$. It means that if a word $u$ of $L$ contains the pattern $01$, then $01$ has to be a prefix of $u$. Now find a regular expression for the set of words not containing the pattern $01$ and from there you should be able to find a regular expression for $L$.


Notation for operational semantics that can be used in code comments

The input format for the tool OTT is based on ASCII and the rules look very much like type system/operational semantics rules. Maybe you could use that format. I'm sure that the parser for the input format is available as open source.


Algorithms for elementary operations using other elementary operators

Throughout this answer, when we say we will be using some operations, it implies that no other operations is allowed. We also assume 1 is available as an operand.

The above clarification is considered as an improvement of original statement of problems. There will be further modification/clarification of the original problems, which have to be made because of the ambiguity of the original problems.

Here is the answer to part (i)

  Part (i). The product of two non-zero numbers using only reciprocation operation and subtraction operation.

Please note I have replaced by addition by subtraction; otherwise, it is impossible. Also I removed the specification of $n$-bits, which seems distracting and harmful; otherwise, $\dfrac13$ is problematic. I have also added the condition that the numbers are non-zero. Otherwise, we have to add an operation that checks whether a number is non-zero and acts accordingly. Also 1 have to be available. Otherwise, we cannot produce 1, which is needed in the final operation.

Let the two non-zero numbers are $A, B$.

we get addition by $X+Y=X-((Y-Y)-Y)$.
we get 4=1+1+1+1.
we get $X\to \dfrac {X^2}4$ by $\dfrac {X^2}4=X+\dfrac1{\dfrac1{X-4}-\dfrac1X}$.
We get multiplication by $AB=\dfrac{(A+B)^2}4-\dfrac{(A-B)^2}4$.

This answer at mathoverflow uses division by 2 or multiplication by $\dfrac12$ without explanation, which can be considered as a minor flaw. In fact, we can do division by 2 as $\dfrac A2=\dfrac1{\dfrac1A+\dfrac1A}$.

  Part (ii). The square of a polynomial with given coefficients using only reciprocation and subtract operation.

Since the coefficient of the square of a polynomial is the sum of products of various coefficients of that polynomial, this part can be done easily as a consequence of part (i).

  Part (iii). The product of polynomials with given coefficients using only squaring and subtraction operations and division by 2.

We get addition by $X+Y=X-((Y-Y)-Y)$. We get multiplication by $XY=\dfrac{(X+Y)^2-X^2-Y^2}2$. Since the coefficient of the square of a polynomial is the sum of products of various coefficients of that polynomial, we can compute the product of two polynomials.

Note that division by 2 is needed. Otherwise, it can be proven that it is not possible to do multiplication although we have $2XY=(X+Y)^2-X^2-Y^2$.


To prove or disprove that language is regular

The language $L$ is regular as shown by the following "flip-flop" style minimal and deterministic automaton $\mathcal{A}$, the crux is that you need only two states (not an unbounded amount of memory) to check parity. $\mathcal{A} = \langle \{odd,even\}, \{0..9\}, even, \{even\}, \delta \rangle$ which transition function $\delta$ is defined by :

$\delta(x,even) = even$ when $x\in \{0,2,4,6,8\}$
$\delta(x,even) = odd$ when $x\in \{1,3,5,7,9\}$
$\delta(x,odd) = even$ when $x\in \{1,3,5,7,9\}$
$\delta(x,odd) = odd$ when $x\in \{0,2,4,6,8\}$


What will be big O complexity for this loop?

The inner loopnever stopped for $n \geq 1$ as for the first time i = 0 and j += i never increased the value of j. If we suppose i will be started from 1, for i = 1 the inner loop will be iterated $n$ times. for i = 2 as value of j is increased by step size 2, the number of iterations of the inner loop is $\frac{n}{2}$. Hence, the computation cost of the program is $\sum_{i = 1}^{n-1}\frac{n}{i} = n \sum_{i = 1}^{n-1}\frac{1}{i} = \Theta(n\log(n))$.


How come {ww} isn't regular when {uv | |u|=|v|} is?

well, there are things that a DFA can do, and things that DFA cannot do. A DFA is quite a simple machine, and it has no access to "memory". The only "memory" it has is its current state, i.e., a very limited memory. A DFA can do tasks that require finite amount of memory, but nothing more than that.

To check if the input is of even length  - is very simple task. It requires only 1 bit of memory (odd/even). therefore, it can be done by a DFA.

However, for the second language $\{ ww \mid w\in\Sigma^*\}$ the DFA needs to check that the first $w$ is identical to the second $w$. How can you do that with no memory? In fact, since $w$ can be of any length, a (one-pass) machine that checks that the two copies of $w$ are the same must have infinite memory (to accommodate any $w$..). But a DFA has only limited memory, and thus cannot solve this task.

at least, this is the intuitive explanation.


How do you obtain transition relation of a PDA?

As you can see, $\Delta$ is a set of pairs that represent a transition function.
First element of the pair is a triple $(q, a, X)$, where $q$ is a state, $a$ is an input symbol (possibly empty string), and $X$ is the top stack symbol.

The other element of the pair describes the action of PDA when its configuration fits the above triple. This other element is again a pair $(p, \gamma)$, where $p$
is a new state and $\gamma$ is a sequence of symbols replacing $X$. If $\gamma = \epsilon$, then $X$ is just popped.

It might help to view $((q, a, X), (p, \gamma))$ as

$$(q, a, X) \rightarrow (p, \gamma)$$


How to quickly find a few bisimulations on a given labelled digraph?

You can always return the bisimulation $∅$ in constant time.

You are right about the fact that in order to return $R$, you will have at least some sanity checks.

For example you could think that returning all bisimulations of the form $\{(p,q)\}$ when $p$ and $q$ have the same label and such that $p\not→$ and $q\not→$ is easy, but not that much: you need to proceed through $O(m+n)$ time and $O(n)$ space! (Or $O(mn^2)$ time and $O(1)$ space (not counting the output)). Checking that a small relation is a bisimulation is not a lot easier than finding the relation $\sim$.

The computation of $\sim$ uses clever properties specific to $\sim$ and fusing states tricks. These techniques would not be useful for several relations and doing better than $O(m\log n)$ (not loglinear) is hard. Also, computing "a few" bisimulation is of arguable interest.

Another thing: deciding if $p\sim q$ implies computing the relation $\sim$ on the union of the directed graphs $G_p=\{x ∣ p \stackrel{a_1\dots a_n}{\longrightarrow}x\}$ and $G_q=\{x ∣ q \stackrel{b_1\dots b_m}{\longrightarrow}x\}$ which can be a significant part of the graph. If however you know have information like the size of $G_p$ and $G_q$ then you can compute $\sim$ on smaller graphs. Keep in mind that algorithms with Tarjan in their name tend to have very tight bounds. This is not an exception.


What is the significance of negative weight edges in a graph?

Saeed Amiri has already given an excellent example in a comment: the weight on edges can represent anything in the real world, for example, the amount of money to be transferred from one account to another account. The amounts can be positive or negative. For example, if you want to go from $a$ to $b$ in your graph while losing as less money as possible (shortest path), then you can consider negative weights. For more, see this book chapter.
Apart from that, there are many more applications. The negative weights depend on what you model it to be. For example,
consider this graph

Chemistry: The weights can be used to represent the heat produced during a chemical reaction. (Nodes: compounds, Edge $e_{uv}$: if compound $v$ can be obtained ("chemically reduced") from $u$). In this graph: you produce $4$ kJ to convert $s$ to $a$ and $2$ kJ to convert $a$ to $t$. You need $5$ kJ to get back $s$ from $t$.

Real Life: Think of a driver, who gets paid to drive his employer from $s$ to $t$ but he pays between $a$ and $b$ (say traveling between his home and his workplace).

Games: Suppose you play rock-paper scissor for money. Nodes: rock, paper, scissors. Edges: any relation (clique). Weights: wager. In this graph: (forget about $b$), here, $s$ beats $a$, $a$ beats $t$ and $t$ beats $s$, and wins 4,2,-5 respectively.


Suppose that $\mathcal{F}$ is a nonempty collection of subsets of a finite set $U$ satisfying the following axiom:

  If $A \in \mathcal{F}$ and $B \subseteq A$ then $B \in \mathcal{F}$.

Consider the following algorithm, which gets as input a weight function $w\colon U \to \mathbb{R}_+$ (here $\mathbb{R}_+$ consists of all positive reals):

Set $S \gets \emptyset$.
While there exists an element $x \notin S$ such that $S \cup \{x\} \in \mathcal{F}$:

Let $x$ be an element of maximum weight among $\{ x : x \notin S \text{ and } S \cup \{x\} \in \mathcal{F} \}$.
Set $S \gets S \cup \{x\}$.

Return $S$.

We say that the algorithm is valid for $w$ if it returns a set $S$ maximizing $\sum_{x \in S} w(x)$ among all $S \in \mathcal{F}$.

  Theorem. The algorithm is valid for all $w\colon U \to \mathbb{R}^+$ iff $\mathcal{F}$ is a matroid.

You can find the proof of this theorem in lecture notes and in textbooks.

The algorithm given above is a specific greedy algorithm. This specific greedy algorithm is optimal if and only if the set system is a matroid. However, the (informal) notion of greedy algorithms encompasses more than just this specific algorithm. The theorem above doesn't apply to these algorithms.

In the two good examples you consider, the corresponding greedy algorithms (or at least one of their variants) are instances of the algorithm above. The same isn't true for the algorithm for your bad example.

For a formalized notion of "greedy-like" algorithms, consult (Incremental) priority algorithms by Borodin, Nielsen, and Rackoff. You can see that is is much more general than the simple algorithm stated above.

Another relevant notion is that of greedoid, for which a theorem similar to the one stated above does hold (see Wikipedia for details).


Are there FPTASs for the min cost flow problem?

If an optimal solution can be calculated in polynomial time, then the same algorithm gives you an FPTAS.

There might, however, be quasilinear time algorithms which give better and better approximations, running faster than algorithms for computing the min cost flow exactly.


Approximate Nearest Neighbour Problem in Spherical Setting

There is a reasonable distance metric on $\mathbb{Z}_2^n$ that allows one to define something that can be viewed as the analog of a sphere.  In particular, use the Hamming distance.  Then given any vector $c \in \mathbb{Z}_2^n$ and any positive integer $k$, the set $\{x \in \mathbb{Z}_2^n : d(x,c) \le k\}$ can be a ball centered at $c$ with radius $k$.  You could even call it a Hamming ball.

You can also define a version of nearest-neighbor search, using the Hamming distance on $\mathbb{Z}_2^n$ instead of the ordinary Euclidean distance on $\mathbb{R}^n$.  Everything carries over.  The algorithms/solutions may need to be different, though.  For approaches to this problem, you could look at metric trees and locality sensitive hashing.


Using the halting problem seems like the good solution. Suppose you have a function red that takes the code of a function (or λ-term) (or a untyped function), reduces one step (or β-redex) in it and returns the code of the resulting function. Suppose also that you have a function normal that says if the term is in normal form.

In Turing machines language, red would be the computation of one step and normal would return true when we are in a final state.

Let's simulate the computation of $n$ steps, returning $43$ instead of $1$ if we reach the end of the computation:

(define (run t n)
  (if (= n 0) 1
    (if (normal t) 43
      (run (red t) (n-1)))))

Then we can decide if the execution of a term will terminate or not:

(define (one x) 1)
(define (terminate t) (not (function=? (run t) one)))

From that we can use the usual diagonal argument:

(define (loop x) (loop x))
(define (f x) (if (terminate (code-of-application x (quote x))) (loop 0) 1)
(f code-of-f)

If f terminates on code-of-f then (terminate (code-of-application code-of-f (quote code-of-f)) will return true and then f will loop on code-of-f. So it should loop. Then (terminate ...) should return false and f will terminate on code-of-f, contradiction.

Technicalities: one need to define a base language which is expressive enough to be able to write everything is written above. You then need red and normal which can be tougher than one can imagine. You need also the standard quine techniques: quote which, given the code of a term, returns a term representing the code of the term, code-of-application a b is easy and self-explanatory, and of course you need to write everything above internally to write code-of-f.

The lambda-calculus is surprisingly simple and expressive to both write all this down and to prove its correctness, which is why Church used it to solve Hilbert's tenth problem, but one can do it in a lot of languages, possibly in a simpler way, using language-specific quine tricks.


Depth perception - detect how far into a scene a user is looking

If you know the gaze direction angles of each eye (as well as head position and orientation), then the corresponding rays intersect roughly at the fixation point in 3D.
This straightforward approach should work in theory, but in practice it is still quite challenging due to both technical and physiological factors.

Pfeiffer, Latoschik and Wachsmuth summarize quite accessibly the state of the art in 3D eye-fixation tracking as in 2008. Here, the intuitive approach I just described was still outperformed by another algorithm.

As the following link suggests, however, the problems with geometrical approaches may have been resolved since 2008. This commercial application appears to use the intersection-point method, though I doubt that the applied algorithms are published.


Is it possible for a syscall to pack together different places in memory?

No, that isn't possible in general, because the page tables work at a page granularity.  If the length of every buffer is an exact multiple of the page table size, and every buffer starts at a page table boundary, you could do what you're proposing, but otherwise you can't.  Since buffers usually won't satisfy those conditions, it's not very useful to create such a syscall.

There are techniques for structuring software to avoid making copies.  However, this often requires that you restructure the code to support this.  See https://en.wikipedia.org/wiki/Zero-copy.


I'm not sure how well it'll work, but the idea is simple:

Consider a continuous relaxation of the function
Run projected gradient descent

1.) First, consider a discrete case: let $x_i$ be $1$ if we pick an $i$-th element, and $0$ otherwise. The constraint is $\sum_i x_i \le k$. For each set $S_j$, we want to write a function which is $1$ when all $i \in S_j$ are picked, and $0$ otherwise. A natural choice is $g(S_j, x) = \prod_{i \in S_j} x_i$. Our objective is $f(x) = \sum_j g(S_j, x)$
Now, to make it continuous, let $x_i$ vary in the range $[0,1]$ - in other words, it represents a probability that we pick the $i$-th element.
Now, $g(S_j, x)$ represents the probability that the set $S_j$ is chosen.
The constraint $\sum_i x_i \le k$ and the objective $f$ are as before.
Therefore, the continuous relaxation is the following:
\begin{align*}
    f(x) &= \sum_j \prod_{i \in S_j} x_i \to \max & s.t.\\
    x_i &\in [0,1] \ \ \forall i \\
    \sum_i x_i &\le k \\
\end{align*}
2.) The gradient has a relatively simple form:
$$(\nabla f(x))'_{x_i} = \sum_{j\colon i \in S_j} \prod_{i' \in S_j \setminus \{i\}} x_{i'}$$
In other words, it's a sum of over terms containing $x_i$: product of all factors except $x_i$.
Since the problem is constrained, you need to run  $projected$ gradient descent. I.e.
$$x^{(t+1)} \gets Proj(x^{(t)} - \gamma \nabla f(x^{(t)})),$$
where $Proj$ is a projection on the set $\{x | \sum_i x_i \le k \land x_i \in [0,1] \ \ \forall i\}$. It may be hard to find the exact projection, but you can use Alternating projection or, better, Dykstra's projection.
For that purpose, we rewrite our constraint set as
$$\{x| \sum_i x_i \le k\} \cap (\cap_i\{x| x_i \le 1\}) \cap (\cap_i\{x| x_i \ge 0\}).$$
Now, we can project at each set in turns. Note that projection on $\{x| x_i \le 1\}$ is trivial: when $x_i \le 1$, don't do anything, otherwise $x_i \gets 1$.
I'm not sure that the function is "good", and therefore I would try a smaller step size first. There are multiple optimizations that one can do, but I omit them here.


I'll present two candidate solutions.

Solution #1: Associative hashing

Yes.  You can associate a hash value with the contents of any binary tree data structure (including a rope).  The basic idea is that you augment each node of the tree to store a hash value.  The hash for a node is $H(h_1,\dots,h_k,x)$ where $h_1,\dots,h_k$ are the hashes on its $k$ children and where $x$ is the value stored in the node.  In this way, any time you update a node, you can update its hash (and all of its ancestors' hashes) in $O(\log n)$ time.  Since all operations take $O(\log n)$ time anyway, this doesn't increase the asymptotic time of the basic tree operations.  Now the hash value at the root of the tree summarizes the contents of the entire tree, so can be used as the index into a hash table.  Basically, you use that hash value instead of using the address of the object.

You don't need to worry about hash collisions.  With a good hash function, hash collisions are sufficiently rare to not be worth worrying about.  And if you're using a hashtable, you always have the possibility of hash collisions, so you need a good hash function in any case.

The big shortcoming of this approach is that it doesn't take care of normalization; the hash value reflects both the contents of the nodes as well as the structure of the tree, so if you have two trees with the same contents but with a different structure, they will end up with a different hash value.  However, you can fix that up by a clever choice of the hash function.  In particular, I suggest you use an associative hash function, which is a function $H$ and a binary operation $\cdot$ where $H(x) \cdot H(y) = H(x,y)$.  Now you can use $h_1 \cdot H(x) \cdot h_2$ as the hash value for a node, where $h_1,h_2$ are the hashes of its two children and $x$ is the value stored in this node.  In this way the hash value at the root will be equal to what you'd get if you concatenated all of the values at all of the nodes (in infix order), then hashed them.  So now the hash value of the tree depends only on the contents of the tree, not on its structure.

Where do you find an associative hash function?  They take some cleverness to construct, but one option is to let $H$ denote the $SL_2(\mathbb{F})$-based hash function in https://crypto.stackexchange.com/a/17936/351 and $\cdot$ represent matrix multiplication.

With this technique, my construction is now normalizing as well, and it should be efficient.

Solution #2: SeqHash

A possible alternative would be to use the SeqHash data structure from the following paper:

VerSum: Verifiable Computations Over Large Public Logs.  Jelle van den Hooff, M. Frans Kaashoek, and Nickolai Zeldovich.  CCS 2014.

This data structure lets you store a sequence of characters in a deterministic tree-based data structure.  In particular, it provides a hash of the data in the data structure that is normalizing (because the data structure is deterministic).  It also provides $O((\log n)^2)$ time insertion, deletion, concatenation, and lookup into the data structure.  It's not a rope, but it might be a possible alternative to a rope that meets your interning requirements.

Related: see also Canonical representation of finite maps on non-overlapping finite rational intervals.


What is minimum cost perfect matching problem for general graph?

The minimum cost perfect matching problem is formally defined as an optimization problem where:

The set of instances is the set of all edge-weighted undirected graphs $G=(V, E, w)$, where $w : E \to \mathbb{R}$.
Given an instance $G=(V, E, w)$, the set of feasible solutions are the perfect matchings $M$ of $G$, i.e., all the sets $M \subseteq E$ such that, $\forall u \in V \; |M \cap \{ (u, v) \in E : v \in V \}| = 1$.
Given an instance $G=(V, E, w)$ and a feasible solution $M$ for $G$, the is a function called measure defined as $m(G, M) = \sum_{e \in M} w(e)$.
The measure is to be minimized.

As for the problem making sense... the problem is abstract in nature and it can be perfectly well-defined without any need for vertices, edges, weights or the matching itself to represent anything.

Of course it is fairly easy to come up with (mock) scenarios in which you might want to compute a minimum cost perfect matching of a suitable graph that is modelling some real-world entities, e.g., the one that follows.

You are organizing a trip for a (large) group of $n=4k$, $k \in \mathbb{N}^+$, participants that will travel together on a bus with $n$ seats. Bus seats are arranged in rows of $4$, with $2$ adjacent seats on each side and a corridor in the middle.
Not all of the participants enjoy their company equally (indeed, some of them categorically refuse to be close by) and you know, for each pair of people that can sit together, how much they'd happy (or unhappy) to be sat next to each other (say, in a scale from $-1$ to $1$).
Being a thoughtful organizer, you want to arrange seats in order to maximize the social welfare of the participants, i.e., the sum of the happiness of all pairs of neighbors in the arrangement you choose.


How to find spanning tree of a graph that minimizes the maximum edge weight?

What follows is taken from Tsuyoshi Ito's comment.

If you know Kruskal’s algorithm for the minimum spanning tree, it is an easy exercise to show that the output of Kruskal’s algorithm is a minimum bottleneck spanning tree. (I think that it is easier than showing that the output of Kruskal’s algorithm is a minimum spanning tree.)


A variation of the baseball elimination problem

I am not familiar with the baseball elimination problem, but nevertheless, if you can solve the original problem, then you can solve the new problem. Here is why. For each game that a team has to play, deduct 1 from its score. Instead of awarding it 1 point if it wins, award it 2 points. It still gets 0 if it loses. This moves us closer to the original problem.

In order to get the original problem as stated, we divide all scores by 2, converting the 2 point award to a 1 point award. This reduces the new problem to the original one, which you already know how to solve.


Evolutionary optimisation algorithm and graph based search

Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms

These are examples of meta-heuristics. Genetic algorithms are a class of Evolutionary algorithms which itself is one of many meta-heuristics.

  Both of these methods entail doing a search on a graph of candidate solutions.

Usually the "graph" is more conceptual than  physical. Meaning that it's not actually represented by a graph data structure living in memory due to the huge search space. These techniques go (or not) from one solution (or a set of solutions) to its "neighbor" using heuristics. For example a solution that has a better fitness value.

  Do all other evolutionary algorithms too entail - performing search on a graph?

Yes. Evolutionary algorithms are search based, meaning that we go from a set of solutions to another based on fitness functions. We also include a mutation step (and may include crossover).

This search happens on the "conceptual" graph of possible solutions.

It is worth to mention that this class is global search based in contrast with local search like the Simulated Annealing algorithm.

For more info check out this Wikipedia article on Meta-heuristics.


Consider a vector $\mathbf v$ of any dimension. The hyperplanes orthogonal to that vector are given by the equation $r = \mathbf u\cdot \mathbf v$ for various $r$s. That is, the collection of vectors $\mathbf u$ satisfying $r=\mathbf u\cdot\mathbf v$ describe a hyperplane orthogonal to $\mathbf v$. If $\varphi$ is the (acute) angle between $\mathbf u$ and $\mathbf v$ (in the plane that they span, not to be confused with the hyperplane the earlier equation describes), this can be written as $r=|\mathbf u||\mathbf v|\cos\varphi$. From this we can see that $|\mathbf u|$ is minimum when $\varphi = 0$ so that $\cos\varphi=1$, the maximum value of $\cos$. If we choose $\mathbf v$ to be a unit vector, i.e. $|\mathbf v|=1$, then the point on the hyperplane closest to the origin is $\mathbf u=r\mathbf v$ and has distance $r$, i.e. $|\mathbf u|=r$.

In the 2D case, the "hyperplane" is actually a line. A unit vector in the plane has the form $\mathbf v = (\cos\theta,\sin\theta)$ for some $\theta$. The dot product equation describing the line is then $r=\mathbf u\cdot\mathbf v = u_x\cos\theta + u_y\sin\theta$ where $\mathbf u = (u_x,u_y)$. The point on the line closest to the origin is then $r\mathbf v = (r\cos\theta,r\sin\theta)$ which is a vector of length $r$ just as stated in the article. As mentioned in the previous paragraph, if $\mathbf v$ is chosen as a unit vector (and it always can be), then this is true in general: $r$ is the distance of the closest point to the origin of the described hyperplane, and that closest point is $r\mathbf v$.