Language to define perfectly a programming problem

This question is somewhat unclear to me; however, under one interpretation there is a result which indicates that the answer is unsatisfyingly yes: namely, the existence of Friedberg numberings. Roughly speaking, a Friedberg numbering is a programming language which is Turing complete but in which no two programs perform the same task.

(More formally: a Friedberg numbering is a computable function $\varphi$ of two variables such that for each computable function $\psi$ of one variable there is exactly one $e_\psi^\varphi$ such that $\lambda x.\varphi(e_\psi^\varphi,x)\cong\lambda x.\psi(x)$.)

A simple proof of the existence of such numberings was given by Kummer.

That said, it's easy to show that we can never "translate into" a Friedberg numbering, which renders the positive result above somewhat misleading at best: if $(\theta_i)_{i\in\mathbb{N}}$ is the usual numbering of computable functions of one variable and $\varphi$ is a Friedberg numbering, the map $$(*)_\varphi:\theta_i\mapsto e_{\theta_i}^\varphi$$ is not computable. Essentially, what this means is that programming in the usual sense is impossible in the context of a Friedberg numbering: while every computable function has a corresponding program, there's no way to find it.

To prove this, simply note that from the map $(*)_\varphi$ we can compute the set of indices for the never-defined function: let $c$ be the unique number such that $\lambda x.\varphi(c,x)$ is never defined, and to tell whether $\theta_i$ is never defined just check whether $(*)_\varphi(i)=c$. (Note that this can be improved: if we replace the never-defined function with the identity function, or more generally any partial computable function with infinite domain, the resulting set of indices is strictly more complicated than the halting problem - it has Turing degree $\bf 0''$. So in fact "translating into a Friedberg numbering" is really very impossible indeed.)

This "impossibility of translation" is what breaks the "obvious" proof that Friedberg numberings are impossible. It also points the way to the general study of numberings, which is a fruitful area of study within computability theory. The numberings which are Turing complete in a "non-stupid" way are the acceptable numberings, which are also those which are maximal in a certain natural pre-ordering on numberings.


Finding the largest possible area covered by M rectangle under a given histogram

What are the subproblems of this problem when we try dynamic programming? Or what is the table?

The subproblems are finding $dp[m][n]$, the largest area possible by $m$ non-overlapping rectangle

which are under the first $n$ leftmost bars and,
the rightmost of which contains the $n$-th bar.

Let $dp2[m][n]$ be the the largest area possible by $m$ non-overlapping rectangle

which are under the first $n$ leftmost bars and,
the rightmost of which is not to the right of the $n$-th bar.

The answer is the maximum of $dp2[M][n]$, where $M\le n\le N$.

$dp[m][n]$ is the maximum of $dp2[m-1][n-1] + R_{n,1}$, $dp2[m-1][n-2] + R_{n,2}$, $\cdots$, $dp2[m-1][n-i] + R_{n,i}$, $\cdots$, where

$R_{n,1}$ is the area of $n$-th bar
$R_{n,2}$ is the area of the rectangle which expands the $n$-th bar and $(n-1)$-th bar horizontally and which contains $n$-th bar
$\cdots$, where $R_{n,i}$ is the area of the rectangle which expands the $n$-th bar and $(n-i+1)$-th bar horizontally and which contains $n$-th bar.

$dp2[m][n]$ is the larger of $dp2[m][n-1]$ and $dp[m][n]$.

The initial values of the two tables and boundary relations should be easy to determine.

There might be optimization tricks to speed up computation besides the standard memorization. You can check whether this naive dynamic programming is fast enough, whose worst behavior is about $\Theta(MN^2)$, which happens when all bars are becoming shorter and shorter from left to right.


Recalling that a directed graph is a graph where the edges have an associated direction with them.

Using a directed graph you can represent asymmetrical relationships between nodes, while in undirected graph we can represent only symmetrical relationships.

Practically, using a directed graph you can represent:

Road networks (using a directed graph you can represent streets'  direction);
hyperlinks connecting web pages;
dependencies in software modules;
prey-predator relationships;
deterministic finite automaton.

Besides these classical examples, you can depict many other real-world scenarios (financial trade, scheduling, infectious disease, citation, control flow, etc) that needs an ordered relationship [1].


Why are regular expression used in lexical analysis instead of grammars?

Regular languages are faster to recognize, and so they are preferred whenever possible. Fortunately, regular expressions are usually good enough for describing the lexemes of a language.

Indeed, in some sense the separation between lexical analysis and parsing is exactly due to this fact, that lexical analysis can be done more efficiently than parsing.


The significance of bounded parameters in complexity

When you see that a parameter is bounded, you shouldn't think of the value of the parameter of a single graph, but of a class of all graphs that satisfy the bound on the parameter.

So, to say that graph isomorphism is in polynomial time for bounded degree graphs really means that, for every $d$, there is a polynomial time algorithm $A_d$ that decides graph isomorphism on the class of all graphs of degree at most $d$.  However, the running time of $A_d$ depends on $d$.

And, yes, the take-home is generally that there are decent algorithms as long as the parameter is small. What counts as decent will depend on your circumstances: what sorts of inputs you need to deal with and how much computing time you have available.


How do we guess the recurrence relation from the given equation

To guess simple recurrences most useful step is to study basic intuition beyond so-called master theorem that looks at any recursion as if it is implicit tree.

Your case is admissible for it and thus easy: on each step you have half of task (peek one branch down in tree), and $O(n)$ work. Multiply tree height and amount of work on each step and you will get your guess. But you will probably never guess any inadmissible case.


How to find max margin for non-separable SVM?

Map all the points to the new space.  Then find the maximum-margin linear separator of those mapped points.  Algorithms for finding a maximum-largin linear separator are described in the literature on SVMs (that's exactly what you need to do to train a linear SVM).  In other words, you can map the points to the new space, then can take those mapped points and train a linear SVM on them.  That's conceptually how to do it.

In practice, nonlinear SVMs use clever tricks to do the same thing, but do it faster (using the kernel trick).


Generating general term of union of two countably infinite sets

In functional programming languages, there is a technique called lazy evaluation, to deal with infinite sets. In lazy evaluation, the sets are used as generators, and the elements of the set are only generated when they are needed.

We can even have lazy operations on lazy data: like lazy union, lazy intersection, and the like, particularly if the lazy generation spits out elements in some order. Particularly, lazy union is very efficient. Lazy intersection and lazy minus are problematic in cases such as yours.


What is the average degree of a complete graph and why?

In a complete (undirected) graph with $n$ vertices, every vertex is connected to all other $n-1$ vertices, so the degree of every vertex is $n-1$. In particular, the average degree is $n-1$.


Call‑by‑name will succeeds where call‑by‑value may fails: some example cases?

Call-by-value evaluates the arguments to a function exactly once.  Call-by-name evaluates the arguments to a function, zero, once, or more times.  Call-by-need evaluates the arguments to a function zero or once, but not more than once.

The trick you are looking for here is a case where call-by-value needs to evaluate an argument once while call-by-name does not need to evaluate its argument at all.  The particular thing that Church and Rosser were worried about was that the argument might be an infinite loop.

So if I have the following

fun call_by_name (cond a b) =
  if cond
    a
  else
    b

and

fun loop_forever () =
   loop_forever()

Then

call_by_name(true, 1, loop_forever())

will return 1 while

call_by_value(true, 1, loop_forever())

will loop forever.

Actually, call-by-name is super cool because it allows you to implement control-flow constructs like if-then-else and while-do.  Suppose, for example that your language doesn't have if-then-else built in.  You can implement boolean values True and false and if-then-else in call-by-name as follows:

fun True  (t f) = t
fun False (t f) = f
fun if_else (cond t f) = cond(t f)

Now

if_else(True, 1, loop_forever())

returns 1 and

if_else(False, loop_forever(), 0)

returns 0.


Optimizing method for counting length of elements between blocks

One gap can be calculated as tetrahedral number $P(x) = \sum \limits _{i = 1} ^{i=x} f(i) = \frac{x * (x + 1) * (x + 2)}{6}$ where $f(i) = \frac{i * (i + 1)}{2}$
After calculating all gaps to calculate chopped off sum you need to subtract $P(x) - P(x-1)$ from the sum.


What is the duality between path cover and flow?

Presumably, the flow would send $k$ units of flow along the edge $(u,v)$, where $k$ is the number of paths in the path cover that traverse that edge.
I haven't verified that this will always be guaranteed to be a valid flow for all possible path covers, but it doesn't seem like it on first glance, so more context might be needed to resolve that.


How powerful is a k-stack pushdown automaton with a unary stack alphabet?

Such automata are called counter-automata. Each counter holds a natural number, which can be tested for zero. (So your UPDA has a single stack symbol plus a way to recognize the empty stack.)

Two push-downs are Turing complete, i.e., they can compute any Turing computable function. Basically, because two stacks can simulate a queue. So you have proved yourself that 3-UPDA is Turing complete. But actually two counters are enough. The trick is to code two numbers $(i,j)$ into a single number $2^i 3^j$ and doing your own construction again.

The family of languages is called one-counter languages, which have some fame in formal language theory. I browsed my own old answers and found: Which languages are recognized by one-counter machines?

Also: The simulation of TM's by counter automata is explained in the old textbook by Hopcroft and Ullman (Intro to Automata Theory, Languages, ...) in two steps. First using four counters and coding the contents of (half of) a working tape of a TM by a single number. The result is attributed to Minsky (1961).


Set $A = B$ and $|U| = \Theta(\log |A|)$, and you run up against the Orthogonal Vectors Conjecture trying to do better than $|A|^{2-o(1)}$.


This paper uses the phrases "compact model" and "multiscale simulation". Perhaps it is relevant. Indeed, Googling "multiscale simulation compact model" yielded lots of results.

The back cover of the book you refer to states:

  Compact Models of circuit elements are models that are sufficiently simple to be incorporated in circuit simulators and are sufficiently accurate to make the outcome of the simulators useful to circuit designers. The conflicting objectives of model simplicity and accuracy make the compact modeling field an exciting and challenging research area for device physicists, modeling engineers and circuit designers.

My understanding is that a compact model is a parametric equation with certain parameters determined that models the phenomenon of interest to some degree of precision.


Where does entanglement fit into quantum computing?

The entanglement of quantum particles is, implicitly or explicitly, the reason why quantum computing is so fast. You will know by now that a qubit (implemented for example as a photon's polarization) can be represented as a unit vector of two complex numbers, and that it may be manipulated by a 2-by-2 matrix of complex numbers. If you have two quantum systems described by their respective state vectors $|a\rangle$ and $|b\rangle$, which describe the two systems in isolation, their composite state is described by the tensor product of these two vectors: $|a\rangle \otimes |b\rangle$. If you operate on $|a\rangle$ with matrix $U$, you get the composite state $(U|a\rangle) \otimes |b\rangle$, and so forth.
Entanglement comes when you operate on this composite state and bring it to a state which cannot emerge as the tensor product of two state vectors. For example, the state $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ is not the tensor product of any two vectors (verify this as an excercise). In such states, measuring qubit $|a\rangle$ has an effect on $|b\rangle$. For example, if you performed a partial measurement (that is, a measurement of ostensibly only one qubit) on the most significant bit of $\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$, and you measured it to be $0$, then measuring the least significant bit will yield $0$ with certainty, too, and vice versa.
A good first example for studying entanglement is Deutsch' problem, where the algorithm goes from $(|0\rangle+|1\rangle) \otimes (|0\rangle - |1\rangle)$, a state which can be expressed as the tensor product, to a state which can no longer be expressed as any tensor product, using an operator which cannot be expressed as the tensor product of two operators.


Perhaps you want a hint first?
Of course you start by considering all vectors $(a_i,b_i)$ first. The vector $(a_i,b_i)$ indicates the amounts you earn by working one hour on job $i$.

What is the meaning of any point on the line segment between points $(a_i,b_i)$ and $(a_j,b_j)$?

If any point $(a_k,b_k)$ is within the triangle $(0,0)$, $(a_i,b_i)$, $(a_j,b_j)$ why can you discard it?


Problems that provably require quadratic time

Finding an envy-free cake-cutting requires $\Omega(n^2)$ queries. However, this does not directly answer your question as the computational model is different than a Turing machine.

By the way, currently the quickest known algorithm for this problem requires $n^{n^{n^{n^{n^{n}}}}}$ queries, so there is a huge gap from the lower bound -
probably one of the largest gaps in computer science.


Spatial Locality in Cache - Which addresses are loaded?

When inserting an entry in the cache, an entire block of addresses is copied. In your case 2 words (8 bytes) are inserted.

So when address 12 is reached, the block of 8 bytes  having address 12 is inserted into cache.

Likewise in case of subsequent misses a maximum of 8 such "blocks" can be inserted into cache, after which eviction process shall start. Further sequence of cache hits/misses shall depend on the eviction policy.


Since $1+2+\cdots+n = \frac{n(n+1)}{2}$, your expression is equal to
$$
C_1 n + C_2 (nm+n^2) - C_2 \frac{n^2+n}{2} = C_2(nm+n^2/2) + (C_1-C_2/2)n.
$$
This shows that for constant $m$ and large enough $n$, your expression is at least $(1/2-\epsilon)C_2(nm+n^2)$ (for any $\epsilon > 0$ and, if $C_1 \geq C_2/2$, even for $\epsilon = 0$), and at most $(1+\epsilon)C_2(nm+n^2)$ (for any $\epsilon > 0$ and, if $C_1 \leq C_2/2$, even for $\epsilon = 0$).


Find a $\log_2(|V|)$ long cycle where each node is of different color

The idea is to use dynamic programming. For every pair of vertices $x,y$ and subset $S$ of colors, you determine whether there is a path from $x$ to $y$ of length $|S|$ (measured in vertices) which uses all colors in $S$, each of them exactly once.

What is this good for? Usually our graphs are not colored. The idea of color coding is that finding cycles (and other structures) is much easier if vertices or edges are colored: instead of having to remember all vertices visited in the cycle being constructed, it suffices to remember the colors encountered. Therefore we need to introduce the colors into our graph. How do we do that? In the simplest possible way: randomly.

Suppose that we want to find a directed cycle of length $k = \ln n$ in a directed graph. We color the vertices of the graph randomly with $k$ colors. If there is a directed cycle of length $k$, then the probability that all of its vertices are colored with different colors is $k!/k^k \approx e^{-k} = 1/n$. Therefore if we try (say) $n\log n$ different random colorings, then it is highly likely that one of these colorings would color the vertices of the cycle with different colors. When that happens, the dynamic programming algorithm outlined above will find the cycle. Conversely, if there is no directed cycle of length $k$, then no coloring would confuse us.

All in all, we obtain a randomized algorithm, running in polynomial time, that finds a cycle of length $k$, if one exists, with high probability.


black-box function optimization with binary vector input: terminology and NP-hardness proof

NP-hardness is a property of languages, that is, of subsets of $\Sigma^*$ for some finite alphabet $\Sigma$. Your problem is not of this form, since you also need to give the algorithm access to the function $f$. Such problems are known as "optimization with a value oracle" (and several other similar names) — the value oracle in your case is the function $f$.

To show that such a problem is hard, we typically given an information-theoretic lower bounds on the number of value oracle calls of any valid algorithm. This captures much, but not all, of the difficulty of solving the problem (it ignores the computational complexity of deciding which questions to ask the oracle). In your case, it is easy to show that any valid algorithm must query the oracle at all possible inputs, using an adversary argument. This makes your problem not so interesting.

In practice, problems tend to have more structure. For example, if you know that for each $\vec{y}$, the function $\vec{x} \mapsto f(\vec{x},\vec{y})$ is submodular, then you can use approximation algorithms for (non-monotone) submodular maximization. In some cases, for example maximizing supermodular functions, there are efficient algorithms that find an optimal solution. In other cases, for example maximizing submodular functions, finding even an $\alpha$-approximate maximum can be hard (requiring exponentially many value oracle queries) if $\alpha$ is too close to 1, but at some point the problem becomes easy again (can be solved in polynomial time).

Any heuristics to your problem will have to rely on some properties of your function. So your first task is to learn more about the structure of your function. In some cases, such as cryptography, there is nothing more to learn, and then there is no real way to speed up the search. But in most optimization contexts you are able to say more about your function, at least roughly, and this informs the algorithms and heuristics that you subsequently use.


Proving parametricity for Gallina functions

My belief has always been that you cannot prove such free theorems from within Gallina about Gallina terms, but I don't have a definite reason why. I certainly can't imagine how this proof would work, given that there's no way to analyze functions like instances of nat' other than applying them.

As you mentioned, you can (in principle) do a parametricity proof for a deeply-embedded language.


Are $A$ and $B$ necessarily be decidable if $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable and $A$ & $B$ being exhaustive?

It is possible for $A$ & $B$ to be mutually exclusive and yet be exhaustive. Now this can happen even when one of them is not decidable. So option A.

The analysis above is correct except the last conclusion "So option A". We cannot exclude the possibility that $A$ and $B$ are both decidable. In fact, it happens in the current situation because of the extra condition, as shown in the latter part of this answer.

Hints, try using the following facts. If you do not know them, prove them first.

For any two languages $X$ and $Y$, if $X$ is exhaustive and $Y$ is decidable, then $X\cap Y$ is exhaustive. (Moreover, $X\setminus Y$ is exhaustive, too. We do not need this fact, though.)
For any language $X$, $X$ is decidable if (and only if) both $X$ and $\overline X$ are exhaustive.

Here is how we can find both $A$ and $B$ are decidable.

Since $A$ is exhaustive and $(A\cap \overline B)\cup(\overline A\cap B)$ is decidable, $A\cap ((A\cap \overline B)\cup(\overline A\cap B))=A\cap\overline B$ is exhaustive. Since $A\cup B=\Sigma^*$, $A\cap\overline B=\overline B$. Since $B$ and $\overline B$ are exhaustive, $B$ is decidable.

Symmetrically, $A$ is decidable.


That depends on context. In theoretical computer science, usually every polynomial time algorithm is considered 'efficient'. In approximation algorithms for example a runtime of $n^{1/\epsilon^{1/\epsilon}}$ would be considered efficient, even though it won't be usable in practice for any reasonable value of $\epsilon$. An algorithm for SAT that runs in $n^{2^{100}}$ would be an amazing breakthrough.

In classic algorithmics, i.e. algorithms from the 80's and before, runtimes below $n^3$ or so (think matrix multiplication, min cost matching, flows, linear programming) are considered efficient. They still are considered efficient by most people, I'd say. Of course a $n^2$ algorithm is not considered efficient if a $n\log n$ algorithm is known, as for sorting for example.

Nowadays there is a trend towards sublinear algorithms or streaming algorithms that are able to deal with terabytes of data. Try using matrix multiplication to compute the page rank of all pages in Google's index. That won't work.

Of course, while certainly useful, the asymptotic runtime of an algorithm doesn't tell the whole story. There are algorithms that have good asymptotic runtime, but constants that are so huge that they effectively can't be used. Ever. Lipton calls them Galactic Algorithms. Robert Sedgewick even states that worst case bounds are "often useless for prediction, often useless for guarantees" and "worst-case analysis is useless for predicting performance" in his talk Putting the Science Back Into Computer Science.


Understanding $O(2^n)$ time complexity due to recursive functions

If you look at the code, it is quite obvious that there are exactly fib(N) - 1 additions. Therefore the time complexity is $\Theta(fib(n))$.


Because we can simulate QTM with DTM and it is an easier proof method than proving directly for QTM (which we can do). Also, this method of simulating a model with DTM to prove they are equivalent in power is somewhat a standard tool, not just for various TMs, but also for other computaitonal models ($\lambda$-calculus, RAM-machines,$\ldots$)

I think this question and answers address everything else you may be wondering

References on comparison between quantum computers and Turing machines


Exhaustive search algorithms for np-complete problems

$O(2^{n/2})$ is still $\mathcal{EXP}$.

The claim you report is known as the exponential-time hypothesis and is a stronger statement than $\mathcal{P} \neq \mathcal{NP}$. We don't actually know if it's true or not.


The list of open problems in bioinformatics: string matching is outlined in Some string matching problems from Bioinformatics which still need better solutions this article is old, but problems remain.
There is also presentation Analytic pattern matching: From DNA to Twitter.

Some are related to graph automorphism (so may remain open for a bit longer) for example:

  Extend String Pattern Matching to Graph Pattern Matching, that is, replace the text T by a graph G and find the number of occurrences of a given subgraph/pattern g in G for different models of graph G generation.


Strictly contained means $\subsetneq$, i.e. it is the definition, it is not a result. So what you are saying is
$$\mathsf{NP} \subsetneq \mathsf{ExpTime} \implies \mathsf{NP} \subsetneq \mathsf{ExpTime}$$
 which is trivially true.

If you are asking if $\mathsf{NP}\subsetneq \mathsf{ExpTime} $ then the answer is: it is unknown.

You may want to check the Wikipedia article about Exponential Time Hypothesis which many experts believe is true.


Find all edges in a tree whose removal doesn't separate color classes

A useful lemma

First, root the tree arbitrarily if necessary, and orient all edges towards the root.

Denote by $b(v)$ the number of colours that appear at least once in the subtree rooted at $v$, and by $e(v)$ the number of colours that are completely contained in the subtree rooted at $v$.  The following lemma is key to efficiently finding all separators:

Lemma: The edge from $v$ to its parent is a separator iff $b(v) = e(v)$.

Proof sketch: The direction "the edge from $v$ to its parent is a separator $\implies b(v) = e(v)$" is easy to see: some number $k$ of colours appear in their entirety in the subtree rooted at $v$, so it must be that $b(v) = e(v) = k$.  The converse can be shown by induction on the number of colours in the entire tree, but intuitively, if we perform a series of steps, in each of which we insert a set of vertices of a fresh colour into the entire tree, then every step that adds a colour that is completely contained in the subtree rooted at $v$ increases both $b(v)$ and $e(v)$ by 1, every step that adds a colour that appears both inside and outside this subtree increases just $b(v)$ by 1, and there is no way to increase just $e(v)$, so it is impossible to recover the state $b(v) = e(v)$ while an incompletely contained colour remains in the subtree.

Computing $b(\cdot)$ and $e(\cdot)$ using deltas

Define $b^+(v)$ to be the number of colours that appear at $v$ but nowhere else in the subtree below it.  Clearly $b(v) = b^+(v) + \sum_{u \in \{u: (u,v)\in E\}} b(u)$, which we can compute in a single bottom-up pass over $T$ if we can compute $b^+(v)$ for each vertex.  Notice that $b^+(v)$ is either 1 or 0, since the only colour that can possibly contribute is the colour of $v$ itself.

Similarly define $e^+(v)$ to be the number of colours that are completely contained in the subtree rooted at $v$, but not in any proper subtree.  Clearly $e(v) = e^+(v) + \sum_{u \in \{u: (u,v)\in E\}} e(u)$.  Notice that, unlike for $b^+(v)$, $e^+(v)$ can be larger than 1, since a vertex can be the LCA of multiple colours.

Computing $b^+(\cdot)$ efficiently

Perform a bottom-up depth-first traversal, using an array $s$ of $N$ flags to keep track of whether or not a colour has been seen in any of the child subtrees.  Specifically:

Initially, set every element of $s$ to false.
On entry to a vertex $v$ having colour $c(v)$:

Set $s[c(v)]$ to false.
Recurse to process all children.
If $s[c(v)]$ is still false, then colour $c(v)$ appears at $v$ but nowhere below it, so set $b^+(v) = 1$.  Otherwise set $b^+(v) = 0$.
Set $s[c(v)]$ to true.

Computing $e^+(\cdot)$ efficiently

Every colour $c$ for which $LCA(c) = v$ contributes 1 to the value of $e^+(v)$.  Thus it suffices to calculate the LCA for each colour, and increase a counter at the corresponding vertex each time.

The total number of LCA computations is $O(N)$, since the colours partition the tree vertices, and the LCA of a set of vertices $\{v_1, v_2, \dots\}$ can be computed as $LCA(v_1, LCA(v_2, LCA(\dots)))$.  Using Farach-Colton and Bender's LCA algorithm, after $O(N)$ preprocessing each LCA can be computed in constant time, for $O(N)$ computation of all $e^+(\cdot)$ values overall.

Final pass

A final bottom-up pass computes $b(v)$ and $e(v)$ for each vertex $v$ from $b^+(v)$ and $e^+(v)$ and the values of $b(v)$ and $e(v)$ of child subtrees as outlined above.  At each vertex $v$, test whether $b(v) = e(v)$, and if so output the edge leading from $v$ to its parent as a separator.  This takes constant time per tree edge, so $O(N)$ overall, making the entire algorithm $O(N)$-time.


Use the pumping lemma to show the language is not regular

Assume $L$ is regular, and let $p$ be as in the pumping lemma.

Note that $s = a^pb^{(2p)^2}a^p\in L$.
Now, by the pumping lemma, we have a decomposition of $s = xyz$.
As $|xy|\leq p$, we must have that $y\subseteq a^p$, Say that $y = a^k$ for some $k\leq p$ (and by the property that $|y|>0$, we have that $k\geq 1$).

Then, we have that:
$$s = \underbrace{a^{p-k}}_x\underbrace{a^k}_y\underbrace{b^{4p^2}a^p}_z$$
Again, by the pumping lemma, we have that $L\ni xz = a^{p-k}b^{4p^2}a^p$.
But, we have that $n_a(xz) = 2p-k$, and $n_b(xz) = 4p^2$, but $n_a(xz)^2 = 4p^2-4pk+k^2\neq 4p^2 = n_b(xz)$, where the lack of equality holds because $1\leq k\leq p$, as stated before.

So, we have a contradiction to the pumping lemma, so $L$ isn't regular.

This all is entirely standard, and the only "trick" is picking the right string $s$.
A few tips for this:

$s$ will generally need to depend on $p$ in some way so it's "long enough to be pumped"
You'll want to carefully choose the first $p$ characters of $s$. If it can all be one character repeated (like in this case we had $a^p$), it makes determining what $y$ is much easier, and you can do the proof with a single case.
Besides that, you want to choose the rest of the string so $s\in L$, and some "pumped version" of $s$ isn't in $L$. This is clearly the hardest part, and the part I don't have a great procedure for. Generally trying a few things ends up with something working eventually. For "counting" based ones like the one you posted (some number of one symbol is equal to some number of some other symbol), usually having the part you pump be of the form $a^k$ is enough to mess with the counting.


Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost

I traced the LP back to this article. Here you can find the answer to your question presented in Theorem 2.

It might be helpful to look at the dual problem of your LP. This is analyzed in the above paper in Theorem 1. In this dual program your variables are defined as variables $z_e\ge 0$ for the edges. Then they show that the optimal cycle is given by the edges for which $z_e>0$ in the optimal solution. Then you can use the complementary slackness condition. It follows that the tight inequalities in your program define the optimal cycle.

Note also that the author provide an interpretation for the variables in your LP. The value of $p_i$ of a vertex not in the optimal cycle denotes the "least length of the path from the vertex $v_i$ to the optimal cycle".


Is the language $L=\{a^nb^m \mid n>2^m\}$ context-free?

According to Parikh's theorem, if your language were context-free, then the set S = $\{(n,m) : n > 2^m\}$ would be semi-linear. Every linear subset of $S$ has a constant second coordinate, as we show below. Therefore you need an infinite number of linear sets to cover $S$, showing that it is not semi-linear.

It remains to show that every linear subset of $S$ has constant second coordinate. Indeed, consider any linear subset of $S$. By definition, such a subset is of the form $u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_r$. By assumption there exists some $i > 0$ such that $u_i = (a,b)$, where $b \neq 0$. Let $u_0 = (n',m')$. It is not hard to check that for some $t$, $n' + at \leq 2^{m' + tb}$, since the left-hand side grows linearly, whereas the right-hand side grows exponentially. This contradicts the fact that the subset is a subset of $S$.


Functional dependencies with the same key?

I think you're misjudging what an insertion anomaly is. It does make sense for the FD to be

carID -> manufactory, model, outletNo**

since this is just a way to say that the same carID always has the same manufactory, model and outletNo.

Now, if you leave aside for a moment custId and custName, and you decompose the relation this way:

R1(carID, manufactory, model, outletNo), R2(outletNo, location)

you see that this is a fine decomposition that meets 3NF and is free from insertion anomalies: infact you just cannot have, for example, the same carID in two distinct outlets, or the same outletNo with different location.

You're right that adding a car with no outletNo would be no good since outletNo is a foreign key to R2, infact most DBs won't allow you to do such a thing. But this is a different story. Not providing values for mandatory fields is just wrong, and that of course doesn't mean the design of the database is not correct.


Is this language recursively enumerable?

Thanks to @Yuval and @chi, I've been able to find a working reduction.

The reduction is $\overline{L_{halt}} \leq L$. For an input $<M><w>$ we build the following TM $N_w$:

Runs $M$ on $w$ for $k$ steps, where $k$ is the length of the input for $N_w$.
If $M$ was able to accept or reject $w$ within $k$ steps in the above simulation, $N_w$ will reject. Otherwise, accept.

This way, if $<M><w>\in \overline{L_{halt}}$ then  $M$ does not halt on $w$ for any length $k$, thus $N_w$ will accept every string. Then, $L(N_w)=\Sigma^*\in P$ and $<N_w>\in L$.

Else, if $<M><w>\notin \overline{L_{halt}}$ then a $n\in\mathbb{N}$ exists s.t. $M$ halts on $w$ within $n$ steps. Thus, for all inputs of length $\geq n$ the TM $N_w$ will reject, and it will only accept inputs of length $ < n$, and not satisfaying the property $P$. Hence, $<N_w>\notin L$.

And since $\overline{L_{halt}}\notin RE$, it follows that $L\notin RE$ as well.


Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm

The lower bound is for the worst-case number of comparisons. Every comparison-based sorting algorithm performs $\Omega(n\log n)$ comparisons in the worst case. This means that the tree has depth $\Omega(n\log n)$.

If you don't like the tree argument, here is an adversary argument which is basically a reformulation of the tree argument. We will maintain the set $\Pi$ of all permutations consistent with the answers so far. When the algorithm compares $i$ to $j$, we answer the result which reduces $\Pi$ by at most a half (one of the two answers must have this property). After $\log_2 (n!/2)$ steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least $\log_2 n! = \Omega(n\log n)$ comparisons on this branch.

In fact, we can strengthen this result (going back to the tree argument): every comparison-based sorting algorithm makes $\Omega(n\log n)$ comparisons on average (when the input is a random permutation of $1,\ldots,n$). For the proof, note that there can be at most $2^k$ leaves at depth $k$. In particular, the number of leaves at depth $(\log n!)/2$ is at most $\sqrt{n!}$. Therefore for at least $n! - \sqrt{n!}$ permutations, all leaves are at depth more than $(\log n!)/2$, and for this $1-o(1)$ fraction of permutations, the algorithm will make at least $(\log n!)/2 = \Omega(n\log n)$ comparisons.

Finally, let us show that you cannot possibly know the correct permutation if you perform less than $n-1$ comparisons. Construct a graph whose vertices are the elements of the array, and $(i,j)$ are connected if you compared the elements at these positions. If you make less than $n-1$ comparisons, then the graph won't be connected. In particular, you can partition the vertex set into two non-empty parts $A,B$ such that no element of $A$ was compared to any element of $B$. In particular, there is a permutation consistent with the performed comparisons in which all elements of $A$ are smaller than all elements of $B$, and another one in which all elements of $A$ are larger than all elements of $B$.


Find close pairs of real points in a set

Hint: by the pigeon principle, if $n$ pigeons have to go into $n- 1$ holes, at least one hole has two pigeons in it. Now let your pigeons be numbers, and make sure that if two numbers go in the same hole, they solve your problem.


The class BQP (see also Complexity Zoo: BQP) was defined by

E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing 26, pp. 1411-1473 (1997).

The class QMA (see also Complexity Zoo: QMA) was defined by

A. Kitaev. Quantum NP. Talk at AQIP’99: Second Workshop on Algorithms in Quantum Information Processing, DePaul University (January 1999).

which apparently built on the idea of a "quantum proof" suggested by

E. Knill. Quantum randomness and nondeterminism. Technical Report LAUR-96-2186, Los Alamos National Laboratory (1996). [arXiv:quant-ph/9610012].

An important relative to QMA, which is perhaps more delicate but which in a certain respect is a more exact analogue of NP for quantum computation, is the class QMA1 (Complexity Zoo), in which the completeness constraint is perfect (i.e. for YES instances, there is a "quantum proof" with acceptance probability 1, albeit for a noiseless quantum computer). This was defined in

S. Bravyi. Efficient algorithm for a quantum analogue of 2-SAT (2006).
[arXiv:quant-ph/0602108]

There are other interesting quantum classes, of course. If you want an introduction to the subject, a good start would be

John Watrous. Quantum Computational Complexity. Encyclopedia of Complexity and System Science, Springer (2009). [arXiv:0804.3401].


Determining on whether topology is a tree or a hypercube

As you have noticed, a simple solution is to generate a token at the initiator and then forward the token through the network using a DFS strategy.

If this token encounters a node that is a leaf, the node will record this information in the token before it is sent back. So when the token has completed the DFS, it will have returned to the initiator who then inspects the token to check if it has encountered any leaf.

The O(m) message complexity follows from the message complexity of DFS, and to show this it's sufficient to prove that the token is sent a constant number of times over each edge.


Designing a rationing algorithm for a store

This sounds like a maximization problem. The algoritm should try to maximize something, let us call it utility.  What You need to start with is to define the utility funktion: is it better to sell all to first customer or end the day with unsold goods?


Trying to understand a way to split an AVL tree in O(log n)

So, basically, what you are saying, is that you have a bunch of left leaning avls and want to merge them?
That's what I understand from the first graph.
You can merge and rebalance them in O(log(n)) time.

What I did was to make each tree a right child of the previous one, and then you start to rebalance at the root and moving to the right, with the rebalancing being a single or double rotation depending on the balance factors of the node and its children, and then you move to the right children and repeat.

@staticmethod
def ReBalanceRightist(parent, node):
    assert parent is not None
    while node is not None:
        AvlNode.UnlinkNodes(parent, node)
        node = AvlNode.ReBalance(node)
        AvlNode.LinkNodes(parent, node)
        parent = node
        node = node.right

First you unlink them, because you don't know if node will still be the root of that subtree, rebalance, and set the result of that rebalance as the new child.
Then rinse and repeat.

This works with O(log(n)) complexity as each left subtree is already balanced, and you just need one rebalance operation to balance a node (O(1)), then you repeat this along the branch, and the branch length is at most log(n), so you get O(log(n)) complexity.

I had to implement a remove_below(x) and remove_above(x) functions for an Avl, so that all the nodes with keys lesser than x or bigger than x would be removed from the tree, respectively, and the problem in the end is the same, which is, how to merge k right/left leaning trees.

You can look at the code here:

https://github.com/Izikiel/AvlPython


Why is every finite language A ⊆ Σ* regular

The proof goes something like this:

If $A$ is a finite language, then it contains a finite number of strings $a_0, a_1, \cdots , a_n$.
The language $\{a_i\}$ consisting of a single literal string $a_i$ is regular.
The union of a finite number of regular languages is also regular.
Therefore, $A = \{a_0\} \cup \{a_1\} \cup \cdots \cup \{a_n\}$ is regular.


What are the examples of scalable and non-scalable data structures?

If I understand correctly, scalable structures refer to structures that can grow with the input grows without concern for memory. Off the top of my head I'd imagine scalable structures such as a tree structure that can grow and search elements quickly, generally O(log(n)) even tho they're a bit more memory intensive.

Where a non scalable structure would be something like an array or any type of structure that has its memory statically allocated to it. While it takes longer to search, generally O(n) but has a predictable memory size. I hope this helps. Note that trees (or other structures that often are dynamically allocated) can be written as array based such as an array based heap that has both static memory allocation but O(log(n)) search capabilities.

It would make sense for big data to use scalable structures since the amount of data is by definition- big and they likely need to query it in an efficient way.  I hope I understood your question and this helps.


Is IP masquerade and Network Address Port Translation(NAPT) the same?

IP masquerade is the same as NAPT and the only difference is that when NAPT is used in Linux, it is called IP masquerade. The mechanism is the same, it's just the place where the technology is implemented is different.


Why the most dominant programming languages didn't follow CSP thread model?

There are many approaches for concurrency, with different tradeoffs.  We have threads with shared mutable state (e.g., SRC-style threading).  We have coroutines (like Go).  We have actor models with independent processes communicating via message passing (like Erlang or E).

I would put CSP on a different level.  It's not the same sort of thing.  The form of CSP that I am familiar with is a mathematical, theoretical formalism that can be used to model concurrent systems.  It's not really a model of programming that can be directly used in programming languages.  It's more like the lambda calculus.  You can build programming language APIs inspired by CSP, just like Lisp and Scheme are inspired by the lambda calculus, but it's not directly a design of a thread API itself.

Why did early languages choose to follow the SRC model rather than something inspired by CSP?  Well, all I can share with you is speculation.  The SRC model is a low-level model that maps pretty closely to the primitives provided by processors: it is a thin level of abstraction over that.  Just like C is a thin layer over assembly language (and doesn't use, say, functional or declarative paradigms), it's not surprising that early languages would provide a thin layer over processor primitives (rather than, say, other theoretical paradigms).  Also, the SRC model works well with existing code and existing programming languages.  You can take existing sequential code and then add threads.  When you're writing threaded code, the sequential part of the computation looks just like code written for a non-threaded language.  That backwards compatibility and familiarity was probably significant.  The SRC model could be deployed as a library, without requiring changes to programming language syntax or compilers.  I have to imagine that might have been a significant factor in its adoption.  Also, the SRC model is somewhat similar in many ways to existing Unix primitives for running code in parallel in multiple processes, which I imagine might also have been beneficial for adoption.  This is just my speculation.  Perhaps someone else will be able to provide a more researched answer.


Terminology for reducing runtime of an algorithm by using a property of the problem?

I'd call it "special-casing".

There are variations. Variation 1 would be: You examine the input, and if the input has a special form, then you use an algorithm that cannot handle every input, but only input like the one you detected.

Variation 2: You run an algorithm that will run fast, but will not be successful for every possible input. You may detect while you run the algorithm or after you ran it that it failed, and use a more general algorithm.

Variation 3: You run a general algorithm, knowing that it will be fast in some cases, and hope your case is a fast one.


Solving the recurrence $T(n)=T(n-2)+n^2$ with the iterative method


How do RNN's handle providing output with different dimension than input

So Basically what happens is the input x is multiplied by a hidden layer U to yield a state vector s, which transforms it to a new dimensionality.  Then The recurrent layer W is always a square matrix to maintain the dimensions of s.  Lastly, the output matrix V is multiplied to update the matrix to the output dimensionality.

So if you had a vector that was 5 dimensions, and you wanted to multiply it into a state vector of 20 dimensions and an output vector of 2 dimensions, your dimensions would be:

x is 5x1
s is 20x1
y is 2x1

U is 20x5
W is 20x20
V is 2x20

and your formula is:

s = Ux + W*s_(t-1)
y = Vs


Creating a Grammar that is equivalent to "RegEx A, RegEx B, or BOTH"

$S \to S_1 | S_2$

That is correct. A grammar doesn't care which derivation it used, or how many could have been used, as long as at least one derivation is valid.

Now if the question said but not both, then it would get complicated!


Proof that shortest path with negative cycles is NP hard

Copied from my answer on cstheory.stackexchange.com:

Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.

This can be reduced from the longest-path problem.  If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.

Thus your problem is NP-Hard.


The problem is not in NC unless P=NC. Jones and Laaser showed in "Complete Problems for Deterministic Polynomial Time" that the problem (therein called CFMEMBER) is P-complete.
Interestingly, Ullman and Van Gelder showed in "Parallel Complexity of of logical query programs" that the same problem where the input CFG has no epsilon productions is in NC (Corollary 7.2).


Constraint Satisfaction: maximizing total value with no overlaps

You are looking for a maximum weight independent set in an interval graph, which can be solved in linear time (by a deterministic algorithm). By the way, the same is true also for a superclass of interval graphs, namely chordal graphs.

One such algorithm is based on dynamic programming, you can see e.g., [1] for details and discussion.

[1] Hsiao, Ju Yuan, Chuan Yi Tang, and Ruay Shiung Chang. "An efficient algorithm for finding a maximum weight 2-independent set on interval graphs." Information Processing Letters 43.5 (1992): 229-235.


What is the definition of computable partial function?

A Turing machine $\Phi$ computes a partial function $f:$ $\subseteq\mathbb{N}\rightarrow\mathbb{N}$ iff:

For each $n\in dom(f)$, $\Phi(n)$ halts and equals $f(n)$.
For each $n\not\in dom(f)$, $\Phi(n)$ diverges (that is, never halts).

What about when we feed $\Phi$ a "nonsense" input - that is, some string not corresponding to a natural number? Well, we don't actually place any requirements on how $\Phi$ behaves in such a case, so there isn't anything to say there. (One reason this should feel fine is that it is computable to tell whether a given finite string represents a natural number - so we're not missing anything interesting by ignoring the behavior of $\Phi$ on nonsense inputs.)

Note that there is a related, weaker notion:

One partial function $f$ extends another partial function $g$ if $dom(f)\supseteq dom(g)$ and for all $n\in dom(g)$ we have $f(n)=g(n)$.
We can say that a partial function $g$ is extendible to a partial computable function if there is some computable partial function $f$ which extends $g$.

It turns out that "extendible to a partial computable function" is a strictly weaker condition than being a partial computable function; this is easy to prove by a simple cardinality argument (exercise).

More interestingly, we can cook up partial computable functions which are not extendible to any total computable function - sort of "fundamentally incomplete" functions which are nonetheless computable. A classic example comes from Godel's incompleteness theorem:

  Fixing some appropriately-computable bijection $b$ between sentences in the language of arithmetic and natural numbers, let $h(x)$ be the least $n$ such that there is a proof of $b^{-1}(x)$ of length $n$, and be undefined otherwise. Then $h$ is a partial computable function which cannot be extended to a total computable function.

Here "proof" means "proof from PA" (or your favorite axiom system). The reason that $h$ can't be extended to a total computable function is simple: if $f$ were a total computable function extending $h$, we could tell whether a given sentence $\varphi$ was provable from PA by searching for a proof of $\varphi$ of length at most $f(b(\varphi))$ - if we find one it is, and if we don't find one it isn't. But from this data we could built a complete consistent computable extension of PA (exercise), contradicting Godel's incompleteness theorem.

The (non-)extendibility of partial computable functions to total, or otherwise "frequently-defined," computable functions is an important topic in computability theory.


Here is one example:
 (λx.(λx.x(λy.x)x)x)x

And by applying alpha equivalnce I can rewrite it to:
 (λw.(λz.w(λy.z)z)w)x

Is my understanding correct ?

There is a small error in your rewriting: at λz.w you have changed the meaning of the expression, because now the bound variable refers to the outer lambda abstraction, instead of the inner lambda abstraction as before. Instead, it should be λz.z. Other than this, the rewriting is correct.

Basically can I think it in this way: as long as I make sure all the bound variables and their corresponding abstractions are noted as the same letter, the new expression is alpha equivalent to the old one?

Yes, this understanding is correct.


Qualifications for a problem to be solved as a single source shortest path problem

Wonderful question!

In spite of the question been very general, this is indeed a research topic by itself. I will rephrase slightly the question as follows: "what are the conditions that enable the applicability of Dijkstra and/or A$^*$ to solve a problem?" Obviously, for those cases that could be identified, the translation you mention to a single-source shortest path comes from the fact that either Dijkstra or A$^*$ (if a heuristic function is available) can solve the problem.

As a matter of fact, your initial guess, optimal substructure is not far from the real answer. As others might not know this concept, let me please introduce a related concept to that:

Definition (Prefix Optimality) A solution path $\pi=\langle s, v_1, v_2, \ldots v_k\rangle$ is prefix-optimal if each of its prefixes is an optimal solution to the corresponding partial problem.

This definition is a specialized version of optimal substructure for the path-finding problem.

This said, the answer to your problem are Cost Algebras. Cost algebras propose a general notion of costs under which various
search algorithms can be reformulated. More recently, an
abstract formalism based on cost algebras has been introduced for
costs suited for heuristic search algorithms such as A$^*$. See Stefan Edelkamp, Shahid Jabbar and Alberto Lluch Lafuente. Cost-Algebraic Heuristic Search. American Association for Artificial Intelligence, 2005, 1362-1367.

Definition (Monoid) Let $A$ be a set and $\times : A\times A\rightarrow A$ be a binary operator. A monoid is a tuple $(A, \times, \mathbf{1})$, if
$\mathbf{1}\in A$ and for all $a,b,c\in A$: (1) $a\times b\in A$; (2) $a\times (b\times c)= (a\times b)\times c$; (3) $a\times\mathbf{1}=\mathbf{1}\times a=a$.

We have a set, and an operation defined over the elements of our set. Let us now define a total order over them:

Definition (Total order) Let $A$ be a set. A relation $\preceq\in A\times A$ is a total order whenever for all $a,b,c\in A$: (1) $a\preceq a$; (2) $a\preceq b \wedge b\preceq a\Rightarrow a=b$; (3) $a\preceq b\wedge b\preceq c\Rightarrow a\preceq c$; (4) $a\preceq b\vee b\preceq a$.

Additionally, the least and greatest operations, denoted as
$\sqcup$ and $\sqcap$ respectively, are defined as follows: $\sqcup
A=c$ such that $c\preceq a, \forall a\in A$ and $\sqcap A=c$ such that
$a\preceq c, \forall a\in A$. A set $A$ is isotone if $a\preceq b$
implies both $a\times c\preceq b\times c$ and $c\times a\preceq
c\times b$, $\forall a, b, c\in A$.

With all these elements we can finally introduce Cost Algebras:

Definition (Cost Algebra) A cost algebra $\mathcal{A}$ is defined as a 6-tuple $\langle A, \sqcup, \times, \preceq, \mathbf{0}, \mathbf{1} \rangle$, such that:

$\langle A, \times, \mathbf{1} \rangle$ is a monoid
$\preceq$ is a total order induced by $\sqcup$
$\mathbf{0}=\sqcap A$
$\mathbf{1}=\sqcup A$
$A$ is isotone

Now, any problem whose formulation satisfies the defintion of a Cost Algebra, can be solved with Dijkstra and/or A$^*$. The following are instances of cost algebras given by the authors:

$\langle \{\top, \bot\}, \vee, \wedge, \Rightarrow, \bot, \top \rangle$ (boolean): Network service availability
$\langle \mathbb{R}^+\cup \{+\infty\}, \min, +, \leq, +\infty, 0\rangle$ (optimization): Price, propagation delay
$\langle \mathbb{R}^+\cup \{+\infty\}, \max, \min, \geq, 0, +\infty\rangle$ (max/min): Bandwidth
$\langle [0,1], \min, \cdot, \geq, 0, 1\rangle$ (probabilistic): Performance and rates
$\langle [0,1], \max, \min, \geq, 0, 1\rangle$ (fuzzy): Performance and rates

Just a minute! What about your initial guess? Well, the authors proved that Cost Algebras actually imply prefix optimality (and hence, optimal substructure) so that their answer is more general than just saying that the problem has to verify the latter. As a matter of fact, Cost Algebras are verifiable whereas optimal substructure can not be immediately decided.

Hope this helps,


Memory banks were an abstraction paired with a hardware implementation to extend the amount of memory normally available to a particular architecture.

For example, the PDP-8 had a "page" size of 128 12-bit words, and most instructions could only address memory on the same page as itself.  Other instructions could access the full memory complement of 2^12 (4K!) 12-bit words.  To go beyond 4K, special techniques could address memory outside the normal 4K. When implemented, the original 4K became (memory) bank 0 and other
memory banks numbers 1, 2 etc might exist.

The details varied, as computers worked their way up to today's standard
of 64 bit address space.


Can an exponential algorithm for an NPC problem be transformed into an algorithm for other NP problems in polynomial time?

If you have an algorithm running in time $f(n)$ that solves an $\mathsf{NP\text{-}complete}$ problem, you can use it to solve any $\mathsf{NP}$ problem and the running time will be $g(n)=f(n^k) + p(n)$ ($k$ is a constant which depends on the reduction between the problems, $p(n)$ is a polynomial essentially giving the running time of the reduction function).

I am not sure what you mean exactly by exponential time, but the result above is general and will work for any $f$, e.g.:

If $f$ is a polynomial, then $g(n)$ is also a polynomial,
If $f(n) = 2^{\epsilon n}$, then $g(n) = 2^{\epsilon n^k}+p(n)$,
If $f(n)= 2^{n^\epsilon}$ then $g(n) = 2^{n^{k\epsilon}}+p(n)$.

I am not sure what you exactly mean by transforming an algorithm, but

what is essentially needed is that we are given a reduction algorithm from $Q'$ to $Q$. If we have that, it is easy to compose it with any algorithm $A$ for $Q$ to obtain an algorithm for $Q'$.
If this is given as an input to the transformation, it can transform an algorithm $A$ for $Q$ to an algorithm for $Q'$ very easily (in polynomial time): it will output the code resulting from composing the code for the reduction from $Q'$ to $Q$ with the code for the algorithm $A$. In fact, this can be done in linear time.

If the reduction is not given as an input then the algorithm has to find it. It can be done under some conditions but essentially we have to provide the transformation with enough information so that the transformation can find the needed reduction algorithm. If we don't provide enough information to find the reduction then this cannot be done. At least not uniformly in $A$. Here is an argument:

The transformation has to return an algorithm that is essentially the composition of a reduction function from $Q'$ to $Q$ with $A$. However the transformation cannot check what a given algorithm $A$ for $Q$ is really doing (because of Rice's theorem). So we can give an identity algorithm as $A$ and the transformation will not notice this and will return an algorithm which is essentially the composition of a reduction from $Q'$ to $Q$ with the identity function. But that is equal to the reduction function from $Q'$ to $Q$. So the output will be a reduction algorithm from $Q'$ to $Q$.


Yes there can be different suffixes, and the IP absolutely does not determine the suffix. You determine the suffix based on how many other computers you want networked together in that subnet group.


Proving following problem NP Hard using known NP Hard partition problem

Assuming that an "airport" cannot be visited more than once, you can reduce HAMILTONIAN PATH to your problem: given a graph $G = (V,E)$, $|V|=n$; suppose that there are two airlines such that $E(1)=E(2)=E$ (i.e. both airlines cover all edges). Then set the price of each edge = $1$. One of the two companies gives no discount, the other gives a (big) discount $d$% (such that $n - \frac{n * d}{100} < 1$) if the cost of the travel is $\geq n$.

Then $G$ has an Hamiltonian path from $s$ to $t$ if and only if the minimum cost of the travel is $< 1$ (i.e. the airline which gives the discount is more convenient).

Note: if an airport can be visited more than once I think that the problem is no more NP-hard (but  I didn't think of it too much). In this case a modified version of a shortest path algorithm should work: just augment the shortest path traversing multiple times an edge of each airline and check if the total cost decreases after reaching the discount treshold.


looking for a strongly NP Complete related problem

Wikipedia's list of NP-complete problems lists the following problem:

Input: positive integers $A,B,C$
Question: do there exist positive integers $x,y$ such that $Ax^2+By-C=0$?

This is a NP-complete problem that has only 3 input values (which is certainly at most poly-log of the input size).

You can find another example of a NP-complete problem with only 3 input values at A Query regarding Quadratic Residuocity Problem.


How to solve for p in Akra-Bazzi method for analyzing time complexity?

You don't solve for $p$ by hand. You use a computer to get a numerical solution. In general, there is no reason to expect that $p$ have some nice form.

Since the left-hand side of the equation is monotone decreasing, there is at most one solution. Furthermore, when $p \to -\infty$ the left-hand side tends to $\infty$, whereas when $p \to \infty$ it tends to $0$. This shows that a solution does exist. The computer can find it using standard root-finding methods.

This kind of situation is encountered in many other places in computer sciences. Here are two examples:

The approximation ratio of the Goemans–Williamson algorithm is
$$ \min_{0 \leq \theta \leq \pi} \frac{2}{\pi} \frac{\theta}{1-\cos\theta} \approx 0.878, $$
which doesn't have a closed form. Surprisingly, assuming the unique games conjecture, this approximation ratio is the best that polynomial time algorithms can achieve in the worst case.
Running times of fast matrix multiplication algorithms are of the form $O(n^\rho)$ where $\rho$ is in simple cases the solution of an equation similar to the one you describe, and in other cases the solution of a much more complicated optimization problem. Again, there is no closed form for $\rho$ in most cases (other than Strassen's algorithm, perhaps).


Complexity of Block edit distance with Swapping only

When one operation is exactly "removing a block and inserting it between two other positions", the problem of computing the string distance is known as Transposition Distance. It is NP-hard even if both input sequences are $p$-sequences, that is, if every letter occurs only once in each input sequence:

Laurent Bulteau, Guillaume Fertin, Irena Rusu:
Sorting by Transpositions Is Difficult. SIAM J. Discrete Math. 26(3): 1148-1180 (2012)


Projecting points on a Pareto-front onto a (hyper)plane?

I'm not sure if this should be considered a computer science question or not, it seems more an algebra question than anything else.

A vector is a direction vector of a hyperplane if it is parallel to that hyperplane (source).

For any vector $\vec{v} = (v_1, . . . , v_n)^T$ you can find a plane parallel to it by taking the dot product of $v$ and your variable vector $\vec{x} = (x_1, . . . , x_n)^T$ and setting the result equal to some constant $c$.

Consider $\eta$ as described in the paper, then the hyperplane he is referring to will be $$\eta_1 f_1 + . . . + \eta_n f_n = c $$ for a constant $c$. Because you are only interested in the distance between the points after projection, and not the location of the projected points, you can select $c = 0$, as shifting around the hyperplane won't affect the distances between the projected points.

Since the origin is contained in this hyperplane, the hyperplane is a subspace, call it $H$. We can then represent each $p_i$ as a vector $\vec{p_i}$ and project the vector onto the subspace.

To project a vector onto $H$ we need to find a basis for $H$. This can be done by making $n - 1$ similar vectors to $\eta$, where the difference is a single value is set to $0$ (distinct from previous selections). E.g., the plane $3x_1 + 4x_2 + 5x_3 = 0$ has a basis of $$\Bigg\{\begin{bmatrix}3 \\ 4 \\ 0\end{bmatrix}, \begin{bmatrix}3 \\ 0 \\ 5\end{bmatrix}\Bigg\},\Bigg\{\begin{bmatrix}3 \\ 4 \\ 0\end{bmatrix}, \begin{bmatrix}0 \\ 4 \\ 5\end{bmatrix}\Bigg\}, \text{ or } \Bigg\{\begin{bmatrix}0 \\ 4 \\ 5\end{bmatrix}, \begin{bmatrix}3 \\ 0 \\ 5\end{bmatrix}\Bigg\}$$

Once you have a basis of $H$ you can use this guide guide to perform the projection. Note, since you have to do this multiple times, coming up with $Q$ as described in the guide and saving it will allow you to perform the process on many points.


The original paper contains such an example (on page 5):
$$
\begin{gather*}
(1 \lor \lnot 2 \lor 3) \land (1 \lor \lnot 3 \lor 4) \land (1 \lor \lnot 4 \lor \lnot 2) \land (1 \lor 5 \lor 2) \land (1 \lor \lnot 5 \lor 2) \land \\
(\lnot 1 \lor \lnot 6 \lor 7) \land (\lnot 1 \lor \lnot 7 \lor 6) \land \dots \land (\lnot 1 \lor \lnot 98 \lor 99) \land (\lnot 1 \lor \lnot 99 \lor 6)
\end{gather*}
$$
The first five clauses force $1$ to hold. Indeed, suppose that $\lnot 1$. Clauses 4 and 5 force $2$, and so clauses 1 and 3 force $3 \land \lnot 4$, contradicting 2. The entire formula is satisfiable, for example by the all-true assignment.

If the starting assignment is not satisfiable or very close to satisfiable, then the authors claim that the large number of clauses of the form $(\lnot 1 \lor \cdot \lor \cdot)$ will ensure that $1$ remains false throughout the algorithm. See if you can substantiate this claim.


What is the expected time complexity of checking equality of two arbitrary strings?

In order to discuss the expected time complexity of an operation, you have to specify a distribution on the inputs, and also explain what you mean by $n$.
One has to be careful, however. For example, consider the suggestion in the comments, to consider some kind of distribution over words of length at most 20. In this case, string comparison is clearly $O(1)$, since 20 is just a constant. There are several ways to avoid it:

Ask for a non-asymptotic time complexity. Since time complexity is highly dependent on the computation model, you can count (for example) the number of input memory cells accessed.

You can specify an input distribution which depends on a parameter $m$, and then ask for the asymptotic complexity in terms of $m$.

Here is an example. Given two random binary strings of length $n$, there will be roughly 4 accesses in expectation. In contrast, if the strings are chosen at random from the collection $0^i1^{n-i}$, the number of accesses will be roughly $(2/3)n$. These two distributions can be separated even if we use asymptotic notation: the algorithm runs in $O(1)$ on the first distribution, and in $\Theta(n)$ on the second.
Another issue is the meaning of $n$. Consider for example a string $0^m$, where $m \sim G(1/2)$ is a geometric random variable. When run on inputs of lengths $a,b$, the running time is $\Theta(\min(a,b))$. How should we express this in terms of $n = a+b$? One choice is to ask for the expected running time given that the input length is $n$. In this case,
$$
\mathbb{E}[\min(a,b)] = \sum_{a=1}^{n-1} \frac{(1/2)^a (1/2)^{n-1-a}}{\sum_{a'=1}^{n-1} (1/2)^{a'} (1/2)^{n-1-a'}} \min(a,n-a) = \frac{1}{n-1} \sum_{a=1}^{n-1} \min(a,n-a) \approx \frac{n}{4},
$$
so the expected running time is $\Theta(n)$.


What is the set of all maximal 3CNF formulas?

There are $2^n$ maximal 3CNFs; here I am assuming that each 3-clause contains at most three different literals (corresponding to different variables), and that the clauses are different and unordered (both within each clause, and across the formula). Indeed, I show below that if $\varphi$ is a maximal 3CNF then there is a truth assignment $\alpha$ such that $\varphi$ consists of all 3-clauses consistent with $\varphi$, and conversely, each such formula is maximal.

Indeed, let $\varphi$ be a maximal 3CNF. Suppose first that $\varphi$ has at least two different truth assignments $\alpha,\beta$. There is a variable $x_i$ whose truth value is different in $\alpha$ and $\beta$, say $x_i$ is true in $\alpha$ but false in $\beta$. In particular, the clause $x_i$ is not in $\varphi$ (since $\beta$ doesn't satisfy it), and if we add it then the formula remains satisfiable. We conclude that $\varphi$ has a unique satisfying assignment $\alpha$. If $\varphi$ doesn't contain all 3-clauses consistent with $\alpha$ then we can add the missing ones while keeping the formula satisfiable. Thus $\varphi$ must consist of all 3-clauses consistent with $\alpha$.

Conversely, suppose that $\varphi$ consists of all 3-clauses consistent with $\alpha$. Since $\varphi$ contains all clauses of width 1, $\alpha$ is the unique satisfying assignment. By definition, any other 3-clause is inconsistent with $\alpha$, and so $\varphi$ is maximal.

You might be interested in E3CNFs, in which each 3-clause contain exactly three literals, each corresponding to a different variables. These can probably be analyzed using the same approach - if you're interested, you're welcome to work it through.


Finding non-trivial NFA that accepts all short strings

Your question is very similar to a similar question about regular expressions. My answer there (citing a paper of Jeff Shallit and his students) gives an example in which the minimal word not accepted has length exponential in the number of states (using the fact that a regular expression of length $\ell$ can be converted an NFA of length $O(\ell)$). Moreover, the NFAs are over a fixed alphabet.


Your post contains two problems. I will only address the first.

There is a simple $O(n)$ algorithm for computing $A \cap B$, which involves an array of length $n$.

Another algorithm sorts $A \cup B$ to find the intersection in time $O(n\log n)$. In contrast to the previous algorithm, this algorithm can be implemented using only comparisons. There is a matching $\Omega(n\log n)$ lower bound in the algebraic decision tree model; see for example lecture notes of Otfried Cheong.


Explain $\log_2(n)$ squared asymptotic run-time for naive nested parallel CREW PRAM mergesort

You want to compute this sum:
$$
\sum_{i=1}^{\mathrm{log}\left( n\right) }\mathrm{log}\left( \frac{n}{{2}^{i}}\right)
$$

This can be easily rewritten to:
$$
\sum_{i=1}^{\mathrm{log}\left( n\right) }\mathrm{log}\left( n\right) - \sum_{i=1}^{\mathrm{log}\left( n\right) }i
$$

The first term is clearly $(\log(n))^2$. The second term is $(\log(n))^2/2+o((\log(n))^2)$. Summed, the result is $\Theta((\log(n))^2)$.


What benefits are obtained by allowing the occurrence of free variables and open terms in lambda calculus?

A subterm of a closed term is not necessarily a closed term. A calculus of closed terms would have to model open terms as well anyway. Pretty much any definition on terms relies on induction over the structure of the terms, and to define something for closed terms of the form $\lambda x. M$, you need to define that thing for the open term $M$.
There are plenty of models of computation. What's the benefit of using combinator calculus when you can use Turing machines or Conway's game of life? Combinator calculus is a natural model of function application, but doesn't capture function definition. The lambda calculus, with variable names, models function definitions with variable names, which a core concept of most programming languages. For this reason, it's a more useful model of programming languages than combinator calculus.
The point of a theory is not just to be internally simple, it's also to be useful for reasoning.


Is there a grammar for this language? $w^{m-1}aca^m$?

You attack it from the exact wrong side.
First, the language is the same as $\{w^m aca a^m|w\in\{a,b\},m\in\mathbb{N}\}$. For this, you apply a rule that adds $w$ on the left and $a$ on the right repeatedly, and then inserts $aca$ in the middle and is done. By using one rule that adds both on the left and the right side, you make the number of w's and a's the same.
$S \rightarrow WSa$
$S \rightarrow aca$
$W \rightarrow a|b$
That’s it.


Advantages of adaboost over gentleboost in applications, or vice versa?

Genetellboost is developed to cope with labeling noise, i.e., when some samples are wrongly labeled. Though, it wasn't so successful in that respect, from my experience it is quite good in handling noisy features which are kind of outliers in dataset. That being said, there is no proof for neither of the things that you asked (nor the things that you mentioned are true). In fact, we know that these algorithms are so similar that it is practically impossible to predict which one works better on which dataset. You have to test it and that's it.


Show: "Checking no solution for system of linear equations with integer variables and coefficients" $\in \mathbf{NP}$

There is a polynomial time algorithm that determines whether a system of linear equations over the integers has a solution. The algorithm uses Hermite normal form, which can be computed in polynomial time. See lecture notes of Swastik Kopparty: Hermite normal form and finding integer solutions.

Your proof that your problem is in coNP is incomplete, since you haven't shown that the witness has polynomial size. Assuming you did manage to show it, all this implies is that the problem is in coNP, not that it is coNP-hard. There's absolutely no issue for a problem to be in both NP and coNP. Indeed, every problem in P is also in NP and coNP. If you can put a problem in both NP and coNP, then this suggests that it might actually be in P, though it is conjectured that $\mathsf{P} \subsetneq \mathsf{NP} \cap \mathsf{coNP}$. One problem which might lie in the middle is (a decision version of) integer factorization.


The upper bound on a Nondeterministic Finite Automata's configurations number

Remember that:
We can view a nondeterministic computation as a directed acyclic graph of configurations indexed by time.

I have a guess that in your eyes:
$2^n$ for both, one directs itself and one directs others and at most every has the $\Sigma$ chance to go next state, maybe to itself, maybe the other state, so from $1$ to $n$ state, an NFA produces at most $\mid\Sigma\mid^n$ configurations.

Here are more details: http://www.cse.msu.edu/~torng/360Book/NFA/


Where should I start to understand how computers work?

You're asking a very broad question that isn't particularly easy to answer "correctly".

What you are describing is what you learn if you follow through with a degree in computer science or maybe more precisely in electrical engineering and computer science.

So I would recommend you to do exactly that:  Go to you favorite university websites and look up what the content of a degree in EE/CS is.

For example, I've heard that MIT has a degree in EECS, so I looked it up, and found a long list of courses.

There I found a course called 6.01 —  Introduction to Electrical Engineering and Computer Science I which even has a downloadable lecture notes document:

  6.01 Course Notes, Spring 2011 (PDF - 4.9MB)

in which the basics of circuits are covered in Chapter 1.

Summa summarum you're asking for what goes into a degree in electrical engineering and computer science, and the best way to find the answer to that is to go to the source.

Universities and schools exist for a reason. :)


If $f(n) = \Theta(g(n))$, do both functions bound each other for all $n$ or only sufficiently large $n$?

If we restrict consideration to $\mathbb{N}$ and both functions are strictly positive on every $n \in \mathbb{N}$, then it is true that, if $f(n) \in \Theta(g(n))$, then there exists a $c$ such that $f(n) \leq cg(n)$ for all $n$, and vice versa.

(As pointed out in the comments, if the functions can be negative, then the answer is clearly "no", since we could take $f(1) = -1$ and $g(1) = 1$.)

The proof is straightforward. If $f(n) \in O(g(n))$, then there is an $N$ and a $C$ so that, whenever $n \geq N$, $f(n) \leq C g(n)$.

Now consider $n = 0,1,2,\dots,N-1$. For each $n$, if $g(n) > f(n)$, pick some $c_n$ so that $f(n) \leq c_n g(n)$. We can easily do this because there's only $N$ of these numbers to check.

Now pick $K = \max\{C,c_0,c_1,\dots,c_{N-1}\}$. By construction, $f(n) \leq K g(n)$ for all $n$. So we're done.

The intuition here is not tricky: We know that, if we go far enough out, $C g(x)$ bounds $f(x)$. So we just check all the cases up to that point and pick the biggest bound.

If we consider strictly positive functions defined on the reals, it is not much different to prove that, if $f$ and $g$ are both continuous and bounded below by some $\delta > 0$, we get the same result.


Finding an instance of an n-element set cover

I think you are being confused by the way the question is phrased. The question asks for a sequence of instances $I_n$, consisting of triples $\langle X_n,F_n \rangle$, such that $|X_n| = n$ and GREEDY-SET-COVER$(X_n,F_n)$ could have $C^n$ many results, for some constant $C>1$. These results come from the fact that at step 4 there could be many sets that are eligible.

For some reason, the question asks you for an algorithm which generates the sequence: given $n$, it should output $\langle X_n,F_n \rangle$. Since the instances you are going to construct will be pretty simple, you should have no problem writing an algorithm that generates them, but in fact no one cares about this algorithm; the point is only that these "bad" instances exist (they're not actually bad, mind you).

The easiest way to construct these instances is to use a gadget, say $F_3 = \{(1,2),(1,3),(2,3)\}$. You can check that running the greedy algorithm can result in three different covers. I'll let you continue from here.


How to use Runge–Kutta methods in a second order ODE

I think there is a mistake in your post: the first equation should be $\ddot{x}(t) = F(t, \dot{x}(t), x(t))$ (and not $\ddot{x}(t + dt)$).
Also, in the computation of $kv_i$ and $kx_i$, it should be $kv_i = v(t) + ka_{i-1}\Delta t$ and $kx_i = x(t) + kv_i\Delta t$ (where $\Delta t = dt$ or $\frac{dt}{2}$). $kv_i$ does not use $kv_{i-1}$ (except in the computation of $ka_{i-1}$), and same thing for $kx_i$.
Question 1: in the differential equation $\ddot{x}(t) = F(t, \dot{x}(t), x(t))$, if you consider the vector $Y(t) = \begin{pmatrix}x(t)\\\dot{x}(t)\end{pmatrix}$, then you have $\dot{Y}(t) = \begin{pmatrix}\dot{x}(t)\\\ddot{x}(t)\end{pmatrix} = \begin{pmatrix}\dot{x}(t)\\F(t, \dot{x}(t), x(t))\end{pmatrix} = \tilde{F}(t, Y(t)) $. That explains why the method works (since the formulas will be the same as with a first order differential equation). Actually, the approximation should be better with the corrections I proposed.
Question 2: With your formulas, a bit of simplification gets you $v(t+dt) = v(t) + \frac{dt}{6}\left(5a(t) + 2ka_1 + 2ka_2\right)$ which is not coherent.
Even with the corrections I proposed, it is incorrect. My guess is that you should compute $x(t+dt)$ and $\dot{x}(t+dt)$ as a whole (as in the vector $Y(t)$) instead of trying to compute them one after the other. The system $\left\{\begin{array}{rcl}\dot{x}(t+dt) &= &\dot{x}(t) + \ddot{x}(t)dt\\ x(t+dt) &=&x(t) + \dot{x}(t)dt\end{array}\right.$ can be seen as $Y(t+dt) = Y(t) + \dot{Y}(t)dt$.


Expected behavior in the min max random assignment problem

See Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research, 36 (2): 205-226, 2011.


It sounds like you're looking for a polynomial-time approximation algorithm for the 3-dimensional matching problem (which is, as you noted, NP-complete - the decision problem is one of Karp's 21 NP-complete problems).

In 2014, Ostrovsky and Rosenbaum proved that 3D matching is APX-complete. This implies the existence of an efficient algorithm that produces a result within a "fixed multiplicative factor of the optimal answer" - in their case, $4/9$.


Perhaps the simplest way is to implement the following algorithm:

Initialize $y$ to 0
Initialize $n$ to 0
Compare $y$ to $x$; if $y = x$, accept; if $y > x$, reject; otherwise, continue
Add $2n+1$ to $y$
Increment $n$ by 1
Jump to 3

The idea is that $y = n^2$ always. This is ensured using the formula $(n+1)^2 = n^2 + (2n+1)$.


Canonical solutions to the broadcast problem include, as you mention, flooding (controlled & uncontrolled, although uncontrolled flooding is untenable for a variety of reasons), as well as spanning-tree based approaches and N-way unicast (which is basically just to point out that broadcast protocols don't represent fundamentally more powerful communication mechanisms).

What you're asking about sounds somewhat similar to a sort of controlled flooding with fault tolerance. Alternatively, you might conceive of your scheme as a spanning-tree approach where multiple redundant spanning trees are defined for each node. In fact, a hybrid of these approaches would help avoid loops, explosion, etc.

Kurose and Ross provide a good explanation in their book "Computer Networks - A Top Down Approach", which you might use to develop your own broadcast protocol.


Is a single symbol, not in a set, a language?

By the standard definitions, a language is always a set of (finite-length) words. This means that "$a$" is not a language, but either a symbol or a word.

If $R$ denotes all the regular languages (or alternatively, all the recursive languages), then indeed $a \notin R$. On the other hand, $\{a\}$ is a language, which is also regular (and recursive).

To complete the standard definitions:

an alphabet is a finite set of symbols
a word is a finite-length string of symbols
a language is a set of words (and can be finite or infinite)

of course, there are many possible extensions to the above definitions, such as infinite-alphabet, infinite-length words, etc.


Is this problem NP-hard? Maximizing selected sets so that their union is less than k?

Very easy. Clique problem reduces to yours.

Each set is the 2-element edges $\{u,v\}$ of $G$.

A $k$-clique has as many edges as possible while only involves $k$ vertices. So, $K={k \choose 2}$.


Understanding the bandwidth problem on graphs

I think you got the definition of bandwidth wrong. Here is your definition of the bandwidth of an ordering of the vertices:

  The bandwidth is the maximum distance in the graph between adjacent nodes in the ordering.

The correct definition is:

  The bandwidth is the maximum distance in the ordering between adjacent nodes in the graph.

Your problem is equivalent to the usual one – just take the inverse of the ordering permutation to get from one to the other.


Byzantine generals problem with signed messages (Lamport)

Maybe this is what confuses you -- mixing the byzantine agreement problem (broadcast: where there is one transmitter and multiple receivers) and the byzantine consensus (where every party starts with an input, and if all have the same input, this should also be their output). The bound of at most half traitors stems from the consensus requirement.

Say we have $n$ generals, out of which $t$ are traitors and $\ell=n-t$ are loyal. Assume general $i$ holds the input bit $b_i$

Now assume they all perform a distributed majority vote protocol. Is the protocol guaranteed to succeed?
This questions is actually not a well defined. The success of the protocol can be interpreted in two different ways:

All loyal generals output the same answer: $MAJ ( b_1, \ldots, b_n)$
All loyal generals output the same answer: $MAJ (L)$ where $L=\{b_i \mid $ general $i$ is loyal$\}$.

Note that using Lamport's result you mentioned, if $n>t+2$ then all the loyal parties are guaranteed to output the same output even if the traitors misbehave and don't follow the protocol, but which output do they output? Assume $\ell=3$ as you suggest, and assume they all hold the input $0$. The "traitors" can still force the loyal generals to output "1": they just set their input to $1$ and behave honestly! Remember that the loyal parties don't know who is loyal and who isn't (or even if there are traitors at all -- maybe everyone is loyal). From their point of view, there are $t$ votes for "1" and only 3 votes for "0", and since everybody behaves as supposed by the protocol -- the output must be 1! This suits interpretation number (1) above.

Thus, interpretation number (2) above makes sense only for the case where  setting the input of the traitors does not affect the majority.
A special case is the consensus problem: if all the $\ell$ parties hold (say) "0", we want to guarantee that they all outputs a 0. Of course, if $t>\ell$ then the simple "attack" described above will work. So we need $t<\ell$, or equivalently, $$n=t+\ell \ge t+(t+1)=2t+1.$$

In the most general case of byzantine major-vote,
the loyal parties may be split
(e.g., $\lfloor \ell/2\rfloor$ votes vs. $\lceil \ell/2\rceil$ votes). In this case, even a single traitor (playing honestly) can determine the result by himself.


Winning strategy for a given game on graphs

The short answer is, Player two wins if and only if the corresponding graph admits a matching that "covers" the set $H$.

Here is a bit of explanation.

Your idea is almost right. However, the proof is not intuitive and you might miss some details which you need if it is a theoretical question or if you need to design the exact winning strategy and not only output the winning player.

So let us start with the part missing from your answer. Assume a given instance corresponds to a graph that admits a perfect matching. According to your strategy, Player 2 wins in this case which is right. Now assume the same instance is given with one more villain, or ten more villains or one thousand of them. Clearly, player two still wins since adding villains, regardless to how we assign them, only helps the second player. So your claim does not always hold. However, your answer is very close to my claim and have the same intuition. It is only missing a bit of formality.

Claim. Assuming both players are playing optimally, Player 1 wins if and only if, given an instance $I$, the corresponding graph does not admit a matching saturating the set $H$.

So what does that mean? A matching saturates a set of vertices $S$, if each vertex in $S$ is incident to a vertex in the matching.
Now we prove the claim. We show two winning strategies one for Player two when the graph admits a matching the saturates the set $H$ and one for Player two when the graph does not admit such a matching.

Proof. Now assume the graph admits such a matching. Let this matching be $M$. The strategy goes as follows. As long as Player one did not lose, for each choice $h \in H$ for Player one, choose $v \in V$ the vertex matched to $h$ in $M$.

The correctness follows directly from the fact that each vertex of Player two is unique and adjacent to the choice of Player one (due the properties of a matching). Intuitively, Player one will run out of moves at some point (possibly after choosing all heroes in the set $H$).

Now assuming the graph does not admit a matching saturating $H$, according to Hall's theorem, there is a subset $A \subseteq H$, such that $|N(A)| < A$. Choose such a set that is minimal inclusion-wise. We claim that there is a matching $M'$ that saturates $N(A)$. Assuming otherwise, again due to Hall, there is a subset $S \subseteq N(A)$ such that $|N(S)| < S$, but then removing $N(S) \cap A$ from $A$ and $S$ from $N(A)$ yields a subset of $A$ that also contradicts Hall's condition which forms a contradiction to the choice of $A$ to be minimal. Hence, there is a matching $M'$ that saturates $N(A)$.

Now the strategy goes as follow. Choose a vertex in $A$ that is not incident to any edge in $M$. Such a vertex exists since $|N(A)| < |A|$. Choose this vertex at first and for each choice $v \in V$ of player two, choose the vertex $h \in H$ matched to $v$ in $M'$.

Again, it is easy to see that Player two will run out of moves at some point (possibly after choosing all vertices in $N(A)$) and hence, Player one wins.


Both $\overline{A_{TM}}$ and $\Sigma^*\backslash A_{TM}$ are not turing-recognizable?

Usually the second language is denoted by $A_{\overline{TM}}$, exactly to avoid the confusion with the complement.
This is actually a common question, and it has to do with the encoding of TMs and words.
When we write $\langle M,w\rangle$, we mean that we give some agreed-upon encoding of a Turing machine and a word over its alphabet. We usually don't go to much into it, but it is agreed that the encoding is simple enough so that another Turing machine can easily parse it (where easily usually means either in logarithmic space, or polynomial time, or something of the sort).
Now, intuitively, in an agreed encoding, some words represent $M,w$ such that $M$ accepts $w$, some represent $M,w$ such that $M$ does not accept $w$, and some are meaningless gibberish.
When the encoding is easy to parse, we can kind of ignore this gibberish. However, it does pose a small problem when we start complementing languages.
Indeed, $\Sigma^*\setminus A_{TM}$ should, formally, also contain all strings that are not legal encodings.
However, since determining whether an encoding is legal is easy, then it doesn't effect the recognizability or decidability of the language. You can always start by checking the legality of the encoding, and accept if the encoding is illegal.
There is another way around it, which I like: you can define the encoding such that every string is a legal encoding. You do that by using some encoding of your liking, and adding to it the statement that any string that is not a legal encoding is now interpreted as some fixed TM $T$ and the empty word. Then, you actually get that $A_{\overline{TM}}=\overline{A_{TM}}$, and the problem goes away.


Average codeword length in a Huffman tree is $\Omega(\log n)$

This answer assumes that by average you mean just that – the sum of all codeword lengths divided by $n$.

Let us show that any prefix code satisfies your property. Consider any prefix code whose codewords have lengths $\ell_1,\ldots,\ell_n$. Kraft's inequality shows that
$$
2^{-\ell_1} + \cdots + 2^{-\ell_n} \leq 1.
$$
The function $x \mapsto 2^{-x}$ is convex, hence
$$
\frac{1}{n} \geq \frac{2^{-\ell_1} + \cdots + 2^{-\ell_n}}{n} \geq 2^{-(\ell_1+\cdots+\ell_n)/n}.
$$
It follows that
$$
\frac{\ell_1 + \cdots + \ell_n}{n} \geq \log_2 n.
$$
Since $x \mapsto 2^{-x}$ is strictly convex, there can be equality only if $\ell_1 = \cdots = \ell_n$, that is, only if all codewords are of length exactly $\log_2 n$. That can only happen if $n$ is a power of 2. This leaves open the following question:

  What is the minimum average codeword length of a prefix code on $n$ symbols?

(We note in passing that every prefix code satisfying Kraft's inequality tightly is a minimum redundancy code for some distribution, namely the one in which the probability of the $i$th symbol is $2^{-\ell_i}$.)

To answer this, let us note that convexity implies that if $a < b$ then
$$
2^{-a} + 2^{-b} \geq 2^{-(a+1)} + 2^{-(b-1)}.
$$
(We can also see this directly: without loss of generality $a=0$, and then we need to prove $1 + 2^{-b} \geq 1/2 + 2 \cdot 2^{-b}$, that is, $1/2 \geq 2^{-b}$, which follows from $b \geq 1$.)

Applying this operation repeatedly starting at some arbitrary integer solution of Kraft's equation, we eventually reach a solution which involves at most two different values $\ell,\ell+1$. If $n = 2^k + m$, where $0 \leq m < 2^k$, then this solution must consist of $2^k - m$ many $k$'s and $2m$ many $k+1$'s. Hence the optimal average codeword length is
$$
\frac{k(2^k-m)+(k+1)2m}{2^k+m} = k + \frac{2m}{2^k+m}.
$$


Application of difference array for overlapping glass-tint problem

First, I will look at this problem from a more (high-level) theoretical perspective and then go through the details required in an implementation, based on the solution you linked to.

Given all the rectangles, we can divide the area in rectangular portions such that every portion is rectangular and all points in the same portion intersect the same set of rectangles. An division of the example input in rectangular portions can be seen below:

Our task is to identify the rectangular portions of glass that have at least the required tint $T$. To do this, it is necessary that we iterate in some manner over all these rectangular portions to determine their tint. It is also sufficient: the portions are determined by considering all rectangles they intersect, at which point we can inspect their tint. So, we can create an algorithm that solves this problem in $O(R)$, where $R$ is the number rectangular portions and this is (asymptotically) the best we can do.

But how big can $R$ become? If we have some collection of rectangular portions of the intersection of $i$ rectangles and add a new rectangle, we create one new portions for each portion that is intersected by one of the four edges of the new rectangle. So how many portions can intersect the same horizontal line? At most $2i-1$, since the same horizontal line can be intersected by at most $2$ vertical lines for every rectangle added (apart from the first). So, after adding all rectangles, we get $R\leq \sum_{i=1}^N 4\cdot (2i-1) = O(N^2)$.

So, our algorithm will run in $O(N^2)$. Given that $N\leq 10^3$, it should be fast enough if we implement it efficiently.

But implementing this efficiently could be rather tricky. Sure, it's easy to say that you can just add rectangles and create new portions as a result of their intersection, but that would be pretty cumbersome to implement and possibly inefficient.

This is where the 'difference array' approach comes in. The principle is slightly easier to explain with a 1D-array, so we will restrict the problem to that for now. Suppose we have input

x1 x2 t
11 20 1
13 14 2
17 18 1
12 19 1

So, we can draw it like this:

The array $A$ contains the tint values over all contiguous 'rectangles' in 1d, which is what we need. The array $dA$ is the difference array of $A$. Observe that this difference array can be easily found: after sorting the endpoints of our 'rectangles', we add the tint-value of the rectangle on the left side (when 'entering' the rectangle) and subtract it on the right side (when we 'leave' the rectangle). After we found are difference array $dA$, we can compute $A$ by noting that $A[i] = \sum_{j=1}^n dA[j]$. Then, we scan $A$ to find the areas that have tint $\geq T$ and add the area to our final value and we're done.

For 2D arrays, we do exactly the same thing, but now with an extra dimension to keep track of.

Let me make a final remark: it is in general very hard to 1. reconstruct an algorithm from an implementation and 2. understand an implementation of an algorithm without understanding the algorithm. Therefore, just inspecting source code to understand an algorithm is generally a hopeless task. In this case, I could only understand the implementation in this source after I understood the explanation.


Number of conflict serializable schedules

While checking for conflict serializable schedules, we should be sure to avoid RW, WW, WR conflicts. Also the relative order of operations internal to each transaction also needs to be maintained. For example T1's operations on $X$should come before T1's operations on $Y$. Also since $Y$ is the common datum here, therefore either all of T1's operation on $Y$ occur before T2's $Y$ operations or they may occur later, but they shouldn't be interleaved.

So let's try to see the number of such serializable schedules:
Here is $T_1$:

  (a)  $r_1(X)$ (b) $w_1(X)$   (c) $r_1(Y)$  (d)  $w_1(Y)$  (e)

Since $Y$ is the common datum so I pick it first from $T_2$.
put $w_2(Y)$ at position (a)

  (a1) $w_2(Y)$ (a2) $r_1(X)$ (b) $w_1(X)$   (c) $r_1(Y)$  (d)  $w_1(Y)$  (e)

We now have two new positions (a1) and (a2). Now, see that $r_2(Y)$ can come only at (a1) since it cannot come after $w_2(Y)$. Now The $Z$ operations of $T_2$ remain. See that they can come at any of the 5 postions starting from (a2) till (e). So for this case, we get total schedules as

$1 *( \binom{5}{1} + \binom{5}{2}) = 15$

$\binom{5}{1}$ is the case when both $r_2(Z)$ and $w_2(Z)$ come together. $\binom{5}{2}$ is the case when they are separated. Note that $r_2(Z)$ and $w_2(Z)$ have not been permuted to maintain their relative order.
Similarly, you can move $w_2(Y)$ through positions (b) (c) and (e)  (note that (d) is an excluded possibility since interleaving is not allowed) to get $20, 18, 1$ as the answer respectively for each individual case. They sum up to $54$.

In case you need the explanation for all cases, you can look up here.


How to find long trails in a multidigraph

Here's a suggestion for a simple greedy heuristic to apply to the big SCC. It's based on the observation that a cycle of edges can be traversed a number of times equal to the minimum multiplicity of any edge in the cycle, so looking for cycles in which all edges have large multiplicity may be a good strategy:

Order edges in the big SCC in decreasing order by multiplicity. Call this list of edges $X$. (Note: Each edge appears in $X$ just once, regardless of its multiplicity.)
Set $Y$ to be an empty list of edges.
If no edges remain in $X$, go to 7.
Choose the edge $e$ with highest multiplicity remaining in $X$. Remove it from $X$ and add it to $Y$.
Test whether $Y$ now contains a cycle (since this cycle must contain $e$, this check can be done quickly using a union/find data structure): If so, let $Z \subseteq Y$ be the edges in this cycle. Add the pair $(Z, m)$ to the set $C$, where $m$ is the minimum multiplicity of any edge in $Z$, clear out $Y$ and start over (recurse) with $X\setminus Z$.
Otherwise, go to 3.
At this point, we have a set of edge-disjoint cycles in $C$, as well as the maximum number of times each can be completely traversed. Note that if $(Z, m) \in C$, then the cycle $Z$ can be entered at any of its vertices, traversed $m$ times, and then exited at the same vertex; or entered at any vertex, traversed $m-1$ times, then (possibly after a further partial traversal) exited from any vertex, giving us some flexibility.
Find the vertex $v_1$ that is shared by the largest number of cycles in $C$; let these cycles be $C_1 \subseteq C$. If $C_1 = C$ then stop here: We can start at $v_1$ and traverse each cycle the full number of times in any order.
Otherwise, find the vertex $v_2$ that is shared by the largest number of cycles in $C\setminus C_1$ and is adjacent to $v_1$. Repeat this for $v_3$, etc., until $C$ is exhausted.
Starting at $v_1$, for each $i$ in increasing order, and for each cycle $C_{ij} \in C_i$ (in no particular order), add either $m_{ij}$ or $m_{ij}-1$ traversals of $C_{ij}$ to the the trail, whichever is larger and still allows us to stop at $v_{i+1}$ in preparation to begin traversing the following set of cycles.

Since the procedure is fairly quick, it may be worthwhile to rerun it many times, choosing a different order of edges each time, and pick the best overall.


It would be nice if you stated the problem. I assume that you have $n$ items $x_i$, each having profit $p_i$ and weight $w_i$. You want to maximize your profit under the constraint that the total weight is at most $W$. For each item $x_i$, you are allowed to put any fraction $\theta \in [0,1]$ of it, which will give you profit $\theta p_i$ and weight $\theta w_i$.

Here is an example. You have raw gold, with a profit of $1000$ and weight $1$. You also have bananas, with a profit of $1$ and weight $10$. Suppose you can carry a weight of $2$. What would you do? Naturally, you would first put as much gold as you can - namely, all of it, and then you would put it as many bananas as you can - namely, a tenth of it, for a total profit of $1000.1$.

The general algorithm is similar. Suppose you divide $W$ into a $1000$ "slots", which you want to fill with the most profitable item-parts of weight $W/1000$. For an item weighing $w_i$, we have $w_i/(W/1000)$ pieces (suppose for the moment that this is an integer), and each of them is worth $p_i/(w_i/(W/1000))$. When choosing what to put in a slot, we would like to maximize our profit, and so we choose the item with maximal $p_i/w_i$, and put it as many pieces as possible. If we run out, we choose the item with the next largest $p_i/w_i$, and so on.

You can implement this without dividing $W$ into a $1000$ pieces: Choose the item with maximal $p_i/w_i$, and put as much of it as possible. If you run out, choose the next one, and put as much of it as possible. And so on. Implementing this algorithm requires sorting the list $p_i/w_i$, which takes time $O(n\log n)$. The algorithm you describe uses the same trick use in quickselect to reduce the running time to $O(n)$, at the cost of making the algorithm randomized.

I suggest the following route to understand the algorithm:

Understand the classical greedy algorithm for fractional knapsack.
Understand quickselect.
See how the algorithm you quote combines the technique of quickselect with the greedy approach.