So is $\Theta$ undefined for insertion sort?

This question contains a category error. It's like saying, "I know that Donald Trump has a height of at least 5 and at most 7. So are numbers undefined for Donald Trump?

$\Theta$ is notation for expressing the growth rate of mathematical functions. "Insertion sort" is not a mathematical function, so if you want to talk about $\Theta$ and insertion sort in the same sentence, you need to say what property of insertion sort you're measuring with a mathematical function that you wish to describe with $\Theta$.

We measure the resource usage of algorithms in terms of the length of the input, which is usually denoted $n$.  You've proposed a function which is the number of execution steps of insertion sort on some input. However, this is a function of the input itself, not of its length. Some inputs of length $n$ will take roughly $n$ steps to sort (I'm using "roughly" to hide constant factors), and some inputs of length $n$ will take roughly $n^2$ steps. So you can't write this as a function of $n$ at all – the number of steps required isn't just a function of the length of the input but, rather, it's a function of the whole input.  Because the thing you're trying to measure isn't a function of the length of the input, you can't directly measure it using $\Theta$ at all.

So we need to come up with a function that does just depend on the length of the input. Two natural functions are the best-case and worst-case number of execution steps. We know that, for an input of length $n$, the best case is that insertion sort finds that the input is already sorted, and in this case, it takes a linear number of steps.  No more, no less, so we're entitled to say that the best-case running time of the algorithm is $\Theta(n)$. Similarly, we're entitled to say that the worst-case running time is $\Theta(n^2)$.

If the best and worst case was (asymptotically) the same (up to constant factors), then the running time would actually just be a function of the length of the input, so it would make sense to say that the running time was, e.g., $\Theta(n\log n)$. However, unless the running time really is a function of $n$, this is an abuse of notation. In the case or insertion sort, where the best and worst case running times are different, we can abuse notation a little harder and say the running time is $\Omega(n)$ and $O(n^2)$. This says that, for any (sufficiently large) input, the running time will be somewhere between $n$ and $n^2$ steps (up to constant factors) but, again, there is no actual function of $n$ that is "the running time." It would be more formal to say that the running time $T(x)$ for an input $x$ satisfies $c|x|\leq T(x)\leq c'|x|^2$ for large enough $|x|$ and some constants $c$ and $c'$.


Should Kolmogorov complexity include all resources or just program size?

Should Kc be restated as being resource based and not solely program size based?

No.  If you change the definition like that, you get a different concept, and the different concepts deserves its own different name.  If you want to examine that concept, you should give it its own name.  Kolmogorov complexity is a standard term with an accepting meaning; trying to "change" its meaning would only cause confusion.

Instead, if you want to study that alternative concept, give it a new name, and then study its properties.  There's no need to change the existing definition of Kolmogorov complexity: Kolmogorov complexity is an interesting and useful concept to have in one's vocabulary.  Removing it from our mental toolbox would only make our intellectual scope poorer.

To give you an analogy: If curves of the form $y=ax^2+bx+c$ are more useful in a practical application than lines, should we re-define the term "linear" to mean a function that can be expressed as $y=ax^2+bx+c$?  No, that would only cause confusion.  Instead, we give a different name (quadratic) to the different concept.


Is this possible to solve satisfiability by using Quine McCluskey algorithm to simplify the whole given boolean formula by simplifying subformulas?

If you're planning to apply this to each subformula with 16 variables:

No, that doesn't work for the same reason given in ratchet freak's answer.  As the Wikipedia article states, Quine McCluskey is functionally identical to Karnaugh maps, so your idea has the exact same problem.

If you're planning to apply this to the entire formula:

No, that doesn't work.  Quine McCluskey outputs a DNF formula or CNF formula.  That alone doesn't tell you whether the resulting formula is satisfiable or not.  You haven't said how to test whether there is a "contradiction"; testing for a "contradiction" is exactly the problem of testing satisfiability, so this hasn't gained you anything.

In any case, Quine McCluskey takes exponential time in the worst case.  Therefore, this approach is inefficient for formulas of any substantial size.  As far as asymptotic worst-case running time is concerned, you might as well just enumerate all possible assignments and see if any of them satisfy the algorithm -- that also takes exponential time.


Hardness of approximating Minimum Cardinality Exact Cover

Suppose that we are given an instance of EXACT 3-COVER (in which every set contains 3 elements) with $m$ sets on $n$ elements; EXACT 3-COVER is known to be NP-complete. Create a new instance in which each element is replicated $t$ times, each of the original $m$ sets contains each copy of each element, and additionally all $tn$ singletons are available. When the original EXACT 3-COVER instance is a YES instance, the new instance can be exactly covered using at most $m$ sets. When the original EXACT 3-COVER is a NO instance, every exact cover of the new instance requires at least $t$ sets (since every disjoint union of the original sets misses at least one original element, and so requires $t$ singletons in the new instance).

Now let us choose $t = mn^\theta$, for some constant $\theta$. The new instance contains $N = mn^{1+\theta} \leq n^{4+\theta}$ elements, and has a gap of $n^\theta \geq N^{\theta/(4+\theta)}$ between the YES and NO instances. As $\theta \to \infty$, the ratio $\theta/(4+\theta)$ approaches $1$. We conclude that your problem is NP-hard to approximate to within $n^{1-\epsilon}$ for any $\epsilon > 0$. In contrast, there is a trivial $n$-approximation algorithm, which just takes all the singletons.


How to find n-1 complete matches for bipartite graphs that are related (speed-date)?

Your problem seems to be the same as that of constructing a Room square. Let me quote from The existence of Room squares by Mullin and Wallis:

A Room square of side $2n+1$ is a $2n+1$ by $2n+1$ array of cells and a set $S$ of $2n+2$ objects called symbols which satisfy the following conditions:
(i) Every cell of the array is either empty or contains an unordered pair of distinct symbols from $S$.
(ii) Each symbol occurs in every row and column of the array.
(iii) Every unordered pair of symbols occurs precisely once in the array.

Mullin and Wallis state that a Room square of size $v$ exists for all odd positive $v$ except for $v=3,5$. This explains why your construction for $n=4$ (which corresponds to $v=3$) wasn't successful.
To construct a Room square, look into the article Construction of Room Squares by Stanton and Mullin.


Here is one example for an algorithm, which can run at $O(4^m \cdot m+ n\cdot m)$ time, which is $o(n^2)$ if $m\ll c\log n$ for every $c<0.5$.

We convert a subset $B_i$ into an ordinal number $1\leq j\leq 2^m$, a number of $m$-bits, in $O(m)$ time, where the $k^{\text{th}}$ bit of $j$ euqals one iff $k\in B_i$. Now, for every ordinal number $j$ we save a link list $L_j$ which contains pointers to all subsets $B_i$ that are associated with ordinal number $j$. This can be done in $O(n\cdot m)$ time.

Second, since all subsets with the same ordinal number are containing the same elements, using $O(m)$ time we can determine for every ordinal numbers $j_1,j_2$ if the corresponding subsets of $L_{j_1},L_{j_2}$ have a common element (i.e., there exists $1\leq k\leq m$ s.t., the $k^{\text{th}}$ bit  of both $j_1$ and $j_2$ is one) or not. In case the corresponding subsets have empty intersection, and in case that $L_{j_1}$ and $L_{j_2}$ are non empty, and it is NOT the case where $L_{j_1},L_{j_2}$ containing a single subset, pointing respectively to to $B_{n}$ and $B_{-n}$, then we can find $B_{i}$ and $B_{j}$ satisfying the above condition in $O(1)$.

In the worst case, we run over all ordinal numbers $1\leq j_1,j_2\leq m$ in $O((2^m)^2)=O(4^m)$ time, and checking an empty intersection takes $O(m)$ time. Since the first step takes $O(n\cdot m)$ time, the complexity of the algorithm is  $O(4^m \cdot m+ n\cdot m)$.


I'm an idiot.

Of course (y < 10) implies (x > 0 OR y < 10). I was somehow mistaking OR for AND. I'm dumb.


Minimal class of grammar required to run program

Determining whether a context-free grammar generates a regular language is undecidable (this is exercise 9.107 in Singh's Elements of computation theory; the reduction is from the Post correspondence problem). So if you are OK with a language being given to you as a context-free grammar, then even determining whether a language is regular or context-free but not regular is undecidable.


There is a mathematical meaning for the empty string. Indeed the concatenation product of words is an associative operation. But this operation also has a neutral element, namely the empty word. For this reason, the empty word is also frequently denoted by $1$, which allows one to write, for each word $u$,
$$
1 \cdot u = u = u \cdot 1
$$

Of course, if the alphabet is $\{0, 1\}$, it is not a good idea to denote the empty word by $1$ and this is probably the reason why the notation $\varepsilon$ (or sometimes $\lambda$) was introduced. But as Yuval Filmus pointed out, the empty word is a word of length $0$, that is, it contains no letter.

It is certainly disturbing to denote the empty word by $1$ (or by a greek letter $\varepsilon$ or $\lambda$), but you have to take it as a conventional notation, in the same way you denote the empty set by $\emptyset$.


Interval Scheduling Problem with more than One Resource

Plot the intervals for all the jobs (sorted by earliest finishing time) on the x axis. Start with y = 1.

If two jobs overlap, then plot the intervals of the later job on a higher y -- i.e.,  above the already plotted job interval. Stop when all jobs have had their intervals plotted. Sort the levels such that the bottom most level has the maximum number of jobs and the top most level has the least number of jobs.

Now, start at the lowest bottom most level of your plot (i.e., y = 1). Allocate all the jobs at this level to machine 1. Then move to y = 2 and allocate all these jobs to machine 2. Repeat till all available machines have jobs.

The number of jobs that can be allocated to k machines is optimal (simple greedy exchange argument).


Can quantum computers really compute a vast number of possible solutions simultaneously?

They are not constrained to stepwise calculations

As far as I know, all QC models are stepwise.

  Under the laws of nature, the ball spins either to the right or to the left, but never in both directions at the same time. The world of quantum computing is different: Here, the ball can revolve in both directions simultaneously

I think this is the source from which comes all this “QC is a massive parallel computation”.

It is not exactly wrong to think of superposition $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$ as “both $|0\rangle$ and $|1\rangle$ at the same time”, but it’s confusing. It might make you think that both things are simultaneously available for arbitrary processing, which you can fully control. As if preparing a superposition is something like creating clones.

A more precise way to think about superposition is interpreting it as uncertainty. So, less confusing statement would be “neither $|0\rangle$ nor $|1\rangle$, until the setup forces it to be definite”.


How to determine seed collision probability in a PRNG?

It depends on the PRNG.  But it doesn't matter in practice.  As long as the probability of collisions is low enough, who cares?  These are pseudorandom numbers, so no one ever claimed they are perfect (exactly uniformly distributed); at best they are indistinguishable from random by any procedure that uses a limited amount of computing power.


Problem of finding pairs of elements that co-occur in some number of sets

You can look into bipartite graphs; the item-set relationships form this type of graph, and the process of clustering highly-connected nodes (loosely speaking) is called community detection (it's similar to frequent itemset mining).


Create an instance $y_1,\ldots,y_n$ of bin packing by taking $y_i = \max(x_i^1,\ldots,x_i^d)$, and solve it using the given approximation algorithm. The solution is feasible for the vector bin packing problem. On the other hand, given a solution for the vector bin packing problem, you can construct a solution for the "max" bin packing problem using at most a factor $d$ more bins by splitting each bin into $d$ bins according to the largest coordinate.


Languages that satisfy the pumping lemma but aren't regular?

The language $\{ \$ a^nb^n \mid n \ge 1 \} \cup \{ \$^kw \mid k\neq 1, w\in \{a,b\}^* \}$ seems to be simple. The second part is regular (and can be pumped). The first part is nonregular, but can be pumped "into" the second part by choosing $\$$ to pump.

(added) Of course, this can be generalized to $\$L \cup \{ \$^k \mid k\neq 1 \} \cdot \{a,b\}^*$ for any $L\subseteq \{a,b\}^*$. Sometimes the formulation is in the "if ... then ..." style: if $w$ starts with a single $\$$ then it is of the form. That I personally find less intuitive.

As noted by @vonbrand the (possibly) non-regular part of the language is isolated by intersecting with $\$\{a,b\}^*$. This can be separately tested using the pumping lemma if needed.


Infinite sequence has $m$ consecutive digits – regular languages

You don't explain how the input to $L_k$ is encoded, but $L_k$ will be regular under any reasonable encoding.

Indeed, if $w$ contains a run of $m$ many $k$'s, then it also contains a run of $m'$ many $k$'s for any $m' \leq m$. Therefore either $L_k$ is finite (indeed, of the form $\{0,\ldots,m\}$) or it consists of all of $\mathbb{N}$.

You seem to be troubled by the fact that $L_k$ is not necessarily computable from (a description of) $w$. But there is absolutely no such requirement – all we have to show is that for each $w$, the languages $L_k$ are regular. We are not claiming that we can compute $L_k$ from (a description of) $w$.


Good introduction to Turing's work and complexity theory?

Some popular books are Computational Complexity by Papadimitriou and Introduction to the Theory of Computation by Sipser. If you are very ambitious, you can also try Computational Complexity: A Modern Approach by Arora and Barak, which is an advanced textbook.

I would recommend against the historical approach of reading old papers. While some old papers are a good read (some of Turing's papers, Shannon's 1948 paper), old papers tend not to follow modern conventions, have a somewhat different focus, are less streamlined than modern treatments, could contain weaker results, and (in some cases) wrong results or at least wrong proofs. A good textbook is much preferable.

Regarding Turing machines, while they have some theoretical advantages in some circumstances, they are poor models of actual computers. Indeed, even in the theoretical computer science community, algorithms are usually described in the so-called RAM machine model which conforms much more closely to actual computers. Even historically speaking, Turing's model wasn't the first universal computation model, though (if I remember correctly) it was the first one that Gödel found convincing (Gödel's own general recursive functions, for example, predates it).

On your way to complexity theory, don't forget to stop at recursion theory (sometimes called computability theory), which had been practiced for a few decades before modern complexity theory started in the early 1970s. The usual course sequence indeed starts at (very basic) recursion theory and progresses to complexity theory.


An efficient way of calculating ((p*q)) where p and q are prime

No, not efficiently, not in general.  Suppose $p=2p'+1$ and $q=2q'+1$ where $p',q'$ are prime.  Then factoring $pq$ is believed to be hard.  (Indeed, these primes are known as safe primes, and factoring a product of two safe primes is believed to be hard.)  However we have
$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$
If you could compute $\varphi(\varphi(pq))$ from $pq$ efficiently for $p,q$ of this form, then you could factor $pq$ efficiently for $p,q$ of this form.  The reduction works as follows.  Consider the quadratic function $f$ given by
$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$
We can compute the coefficients of $f$, as
$$p'+q'=[pq-2\varphi(\varphi(pq))+3]/4$$
$$p'q'=[pq+2\varphi(\varphi(pq))-5]/8$$
so you can use the quadratic formula to solve for the roots of $f$ and recover $p',q'$. From this the factorization of $pq$ can be recovered.
So, no, you are not overlooking anything.  There is likely no efficient way to compute $\varphi(\varphi(pq))$ for arbitrary numbers $pq$ (unless factoring is easy).


Finding the (probable) maximum of a large set of integers *without* iterating over all of the values

Tricky.

As an approximation, assume that the number n is in the set with a probability p (n), and the sum of p (n) over all integers n is finite, so we may guess that the set is finite.

You'd have to check enough values n to make some reasonable assumptions about p (n), and then based on those assumptions make a reasonable guess about the upper bound.

But let's say that p (n) = $1 / n^2$. The probability that there is any element n ≥ N is about 1/N. So 10 is an upper bound with probability 90%, 100 is an upper bound with probability 99% and so on. On the other hand, your checks will likely show that 1 is an element and find no others. p (n) could be any of a gazillion of possible probabilities.

Your chances are much better if you have some knowledge about the distribution.


If Data-Flow Analysis is able to approximate, what does that mean?

All of the problems we want to solve with static analysis are undecidable.  We have a yes-or-no question ("will this expression be available?", "is this variable live?", etc.).  Ideally we'd like an algorithm that takes as input the program, terminates in a finite amount of time, and outputs the correct answer to the question.  Unfortunately, the problem is undecidable, so there is no such algorithm.

But we're not willing to give up.  So, we accept algorithms that always terminate but sometimes output "I'm not sure".  There are basically two kinds of such algorithm.  One can will either output "Definitely yes" or "I'm not sure (might be yes, might be no)".  The other kind will either output "Definitely no" or "I'm not sure (might be yes, might be no)".

Underapproximation vs overapproximation just refers to the difference between those two kinds of algorithms.

How do you pick one or the other?  That depends on what you're ultimately trying to achieve.  In some situations, it's more useful to know that the answer is "definitely yes".  In others, it's more useful to know that the answer is "definitely no".

Of course, these two notions can be combined, so you can get an algorithm that will output either "Definitely yes", "Definitely no", or "I'm not sure (might be yes, might be no)".  But you can't avoid the possibility of an "I'm not sure" answer; that's an unavoidable consequence of undecidability.


How to formulate constraints in zero-one linear programming


okay, what you are talking about can be explained using the concept of Kolmogorov Complexity.

Let's understand the Kolomogorov complexity and randomness.

Suppose you have a string $A = HHHHH$ and $B = TTHTH$, now intuitively it seems $B$ has more randomness than $A$, however, statistically, both strings have an equal probability of being chosen. This troubled researchers for sometime untill Kolmogorov and Chaitin (independently) came up with a notion of randomness.

A string is said to be random if it cannot be compressed, that is it has no 'structure' in it.
Formally, for any word $x \in (\Sigma_{bool})^*$, the Kolmogorov Complexity $K(x)$ of the word is the binary length of the shortest program generating it.

A word is said to be random if it is not compressible. i.e. $K(w_n) \geq |w_n| + c$

If you want to look up more on this, you can start with this wonderful survey note by Lance Fortnow

Now, as I understand your question, you are asking how is an a word that is incompressible be 'information' while we use the same notion for randomness.

So, this is a bit philosophical... well, randomness is always philosophical! anyway, What we call/define to random is actually information without a structure. The outcome of an unbiased coin toss is also random, i.e. it should not have any structure to it, and one should never be able to find any patterns or periodic repetitions in the string.

Information is basically a numerical measure of the uncertainty of an experimental outcome.

Now, let's use the K-Complexity... suppose we start writing down the outcomes of a coin toss. Now without the information you basically do not have an metric to evaluate randomness of the string. The randomness is more of a property associated with information.
You can probably associate a certain degree of randomness to anything that's based on experiments.

The K-complexity is just a measure of randomness in information.
For an completely 'random' string, the $K(w_n) = |w_n| + c$ and for a completely 'non-random' string, the $K(w_n) = \delta + c$ where $\delta$ is some small quantity.


Your problem is equivalent to exact learning of monotone DNFs. This task is equivalent to learning all minterms of a monotone function, whereas you are interested in learning all maxterms of a monotone function, but the two problems are equivalent. (Look these terms up if you are not familiar with them.)

If the only queries you allow are membership queries (test whether a given set is feasible or not) then your problem is rather difficult. Theorem 2 in Angluin's Queries and Concept Learning shows that $2^n-1$ queries are required even if there are only $2n$ objects and $n+1$ minterms. See the paper for other models in which your problem can be solved efficiently.


The Church-Turing Thesis (Hello World tester) contradiction and randomized algorithms

The Church-Turing thesis proves that there is no algorithm (or program)  that says whether a program  written in a language, say , on an input  outputs the sentence Hello World or not. This is his proof, visit Hopcraft and etc.

The Church-Turing thesis is introduced in the book as "the unprovable assumption that any general way to compute will allow us to compute only the partial-recursive functions (or equivalently, what Turing machines or modern-day computers can compute)". It has little to do with undecidability directly. I will treat "The Church-Turing thesis proves that" as a typo that should not exist.

  Please explain where I am wrong about this.

In fact, you are not necessarily wrong at all. It is just that your argument does not lead us anywhere.

What have been proved in the book is that there is no non-randomized algorithm that can decide whether a non-randomized program on an input outputs "Hello World" or not. No, there is no such adjective "non-randomized" in the original statement in the book. However, it does not matter much whether we add it or not. Why?

Because a randomized algorithm cannot decide anyway. It can only say something like the probability a given program on some given input outputs "Hello world" is less than 23 percent. I will not call that probabilistic prediction a decision. You have not found anything valuable or interesting by considering randomized algorithms. All you have observed is that the proof does not apply to randomized algorithms, which we do not have to consider in the first place anyway.

We might be thinking, wait, there is some information if we can be certain the probability a given program on some given input outputs "Hello world" is less than 23 percent. That could be mean that the undecidability only holds in some relative sense.

However, the conclusion is still something along the line that there is no algorithm, whether randomized or not, can always provide non-zero information regarding whether a deterministic program on a input outputs "Hello world" or not. You can read the question can a probabilistic Turing machine solve the halting problem? and its answers for more explanations.


Why is it true that the relation R and its negation are not semi decidable?

If the relation $R$ was semi-decidable, then the halting problem would be decidable: if you want to know whether program $x$ terminates, just enumerate the elements of $R$ until you find either $(x,0)$ or $(x,1)$. In the first case, output "$x$ halts"; in the second, "$x$ does not halt." One of these is guaranteed to happen, so you have a decider for the halting problem, contradicting the undecidability of that problem.

The argument for the complement of $R$ is nearly identical: observe that $\overline{R} = \{(x,1-y)\mid (x,y)\in R\}$.


Decidability of the TM's computing a non-empty subset of total functions

For any function $f: \Sigma^* \rightarrow \Sigma^*$, let

$$L_f = \{ x \# y \mid y = f(x) \}$$

For any Turing machine $M$, we can construct the description of a Turing machine $M'$ such that $M'$ recognizes $L_f$ if and only if $M$ computes $f$. $M'$ will receive a string, check that it is of the form $x \# y$ and then simulate $M$ with input $x$. If the simulation returns $w$, $M'$ accepts if $w = y$. Therefore, the language

$$ A_f = \{ \langle M \rangle \mid M \text{ is a TM that computes the function $f$} \}$$

reduces to the language

$$B_f = \{\langle M \rangle \mid L(M) = L_f \}$$

The class

$$L_S = \{ L_f \mid f \in S \}$$

is a nontrivial class of Turing-recognizable languages and therefore the decision problem $B_f$ is undedicable by Rice's theorem.


I'm sure someone will manage to come up with a more efficient idea, but here's a basic one:

Have both sides of the river be nodes in the graph. Define the disk used for these nodes as having 0 cost and 0 radius.
Split each pile into B nodes in the graph, one for each type of disk.
Connect each pair of nodes where the sum of the radius of the 2 disks of these nodes is less than or equal to the distance between the nodes.
Define the cost of an edge as the cost of the disk of the destination node. The cost of the source node will already have been included in the previous step.
Note that this should be dynamically calculated - one can approach an edge from either side, thus it can take on the value of either node, thus could have different costs at different times.
Run Dijkstra's algorithm as per usual from the source side of the river.

One can get a more efficient but more complex algorithm by only having a single node for each pile and storing the radius of the chosen disk at each point.

Note that any disk type A with cost cA and radius rA can be discarded if there exists a disk type B with radius rB >= rA and cost cB <= cA, or, equivalently, if there's a bigger and cheaper disk type, since it would always be more efficient to use that one instead.


Algorithm for solving system of congruences

It is often less confusing to refrain from using congruences and simply write what it means in extension. I.e. when the textbook says to take an $x$ which is equal modulo $M$ to $r_0\cdot w_0 + \dots + r_{n-1}\cdot w_{n-1}$, it means that any $x$ of the form $x=r_0\cdot w_0 + \dots + r_{n-1}\cdot w_{n-1} + k\dot M$, with $k\in \mathbb{Z}$, is a solution. Under this form it should be clearer that $x$ is indeed a solution since $\forall i\in \mathbb{N}_n,x\equiv_{(m_i)}r_i\cdot w_i + \sum_{j\neq i}r_j\cdot w_j+ k\cdot M\equiv_{(m_i)}r_i$ (as $m_i|M$, $w_i\equiv_{(m_i)}1$, and for $j\neq i$ $m_i|w_j$).


Connection between Pseudo random generators and hardness

Theorem 1 in [Nisan Wigderson 1988] implies:
For any function $l\le s(l)\le 2^l$, the following are equivalent:

For some $c>0$, there exists a quick PRG $G: l\to s(l^c)$.
For some $c>0$, there exists a function $f$ in EXPTIME with hardness $s(l^c)$.

Although their definition of (quick) PRG and hardness are slightly different from yours, I think the conclusion is still the same (as long as $\epsilon <1/2$, and your conclusion should be $H_{avg}(f)\ge S(l^c)$ for some $c$ rather than $H_{avg}(f)\ge S(n)$).
The proof can be summarized as follows:

Regard the PRG as an extender from string of length $l$ to string of length $l+1$, and consider the boolean function $f$ corresponding to this extender.

Show that $f$ cannot be approximated by circuits of size $S(l^c)$, i.e., for some constant $k$, all large enough $l$, and all circuits $C_l$ of size $S(l^c)$, $\mathrm{Pr}_{x\in U_l}[C_l(x)\neq f(x)]>n^{-k}$ (note this is a weaker condition compared to the definition of hardness, i.e. your $H_{avg}$).

Use Yao's lemma [Yao 1982] to xor multiple copies of $f$ to obtain a function $f'$ such that $H_{avg}(f')\ge S(l^c)$.

You can see more details in [Nisan Wigderson 1988].


Is there a technique for statically checking that a function is only called at a particular rate?

The property you mention is probably not something that sounds like an ideal fit for enforcement by type systems, so it's not the first example I would suggest looking at, if you want to learn more about how type systems can be used to enforce a variety of properties.  (I'm not saying it is impossible to enforce that property using a type system, but it might not look natural or feel super-useful to an everyday programmer, and the type system might need some hand-holding or help from the programmer.)

However, there are other properties that are a better fit for type systems.  For instance, you might look at dependent type systems, which can be used to enforce many properties.

In my experience, type systems tend to be more useful for enforcing safety properties.  It tends to be harder to reason about time or liveness properties using a type system (I'm not saying it is impossible, but it might be harder or less natural).

You might also enjoy reading about the Curry-Howard correspondence, which shows a correspondence between theorems and types (and between a proof of a particular theorem vs a particular program that can be given a particular type).  Proof-carrying code is one example of a system that relies heavily on this view of proofs-as-programs.  The goal there is to prove non-trivial properties of a program.  The theorem you want to prove gets encoded as a type, and the proof gets encoded as an expression in an abstract language; then checking the validity of the proof becomes as simple as checking that the expression has the claimed type.  This essentially shows how you can reduce "showing that the program satisfies a particular safety property" to type-checking.

In a similar but not identical vein, you might also enjoy looking at languages like Haskell and the QuickCheck tool, which uses the rich type information available from the Haskell type system to synthesize test cases.  Anecdotally, QuickCheck is effective at finding many bugs.  This is not an example of using the type system to enforce absence of a particular kind of bug, so much as using the type system to make random testing more effective and thereby tend to help programmers catch many bugs earlier.


No. Here is a counterexample: $X=\{a,b\}, Y=\{c,d,e,f\}, E=\{ac, ad, ae, be, bf\}, k=2$. The first iteration of your algorithm could choose $\{ae,bf\}$ (in particular, the edge $ae$), preventing a solution from being found even though one does exist: $\{ac, ad, be, bf\}$.


Closure against right quotient with a fixed language

To answer these question, we need allow any $L_2$. So let's think that $L_2$ is a very complex language (say, some undecidable language.)

Lets start from the easy question: $A_l(L)$  (question part 2). Take $L_2$ to be undecidable, and $L=\{\varepsilon\}$. What happens?

(moral: Always check the "extremes": empty $L$, $L=\{\varepsilon\}$ and $L=\Sigma^*$...)

Now for $A_r$. This is a great question (usually bonus question in Final/Homeworks). Indeed, regular languages are closed under $A_r$ for any language $L_2$. Even undecidable $L_2$. Cool, right?

So how can we build an automaton for $A_r(L)$ if there is no machine that accepts $L_2$?

Here comes the magic of "abstract thinking",i.e., existential proof. If someone gives us $L_2$ we can use this information to show that there exists some automaton to solve $A(L)$. Now the details.

We start from the automaton of $L$ (call is $DFA_L$).
Assume that after processing $x$ we end up in a state $q$. We need to accept if there exists $y\in L_2$ such that if we continue from $q$ processing $y$ we will end up in a final state of $DFA_L$. There is no machine that can tell us if $y$ is in $L_2$, but we can make $q$ a final state of $DFA_{A_L}$ if the above condition holds, i.e., if there exists some $y\in L_2$ such that if we start at $q$ and process $y$ we end up in a final state of $DFA_L$.

so to build $DFA_{A_L}$ we examine each one of the states of $DFA_L$ and make each state $q$ an accepting state if we can take some $y\in L_2$ and this $y$ will lead us from $q$ to an accepting state of $DFA_L$.

So ok, $L_2$ is infinite, and we might have no computer to list all the words in $L_2$, but all of this doesn't matter... the above automaton is well-defined, even if I can't draw it to you state by state. Magic.


How to describe the time complexity of a continually running program with a stream of inputs?

I would say that you should not look at the overall runtime (as it will be dominated by $m =\infty$ anyway) and instead look at the expected complexity of processing a single element (or a group of them if it doesn't scale linearly).

I'm not entirely sure what you mean with "Tree lookup" but I will just guess and provide an answer for that:

Calculating the hash of a key with length $k$ is done in $\mathcal O(k)$.
The corresponding field in the hashmap/table/set is then retrieved with a single lookup.

Assuming your tree is a BST where each node is a key (256 chars, alphabet of size 26) and you compare either left or right side and you have 10 nodes in the tree:

The tree has $log_2(10) \approx 4$ levels (1,2,4,2 nodes)
For a lookup, in each level the current key has to be compared to the node's key. The chance that the first characters match is $\frac1{26}$. That the first two match $\frac1{26^2}$, and so on.
In most cases, you will have a mismatch at the all four nodes where a value is compared
Your average case thus involves a few (2-4) lookups (following left or right child pointers in the tree) and comparing a few letters. If the key matches, the whole key is compared but I assume that this doesn't happen very often.

Thus, the BST lookup has a better performance without further modifications.

Maybe more fitting for stackoverflow than cs.stackexchange but still, my suggestion for your problem would be the following:

Determine if the values in the collection have some pattern (if they are SHA hashes of random data or similar, very very likely not the case)
Look at the percentage of successful matches (I would guess very low)
Implement a custom "Hashing". If the items in your collections start with different letters (or 2, whatever), you only need the first letter of each element in your stream to know with which item from your collection you have to compare it (for equality).


What architectural features will allow this microprocessor to access a separate "I/O space"?

The CPU uses the same address/data bus to access both the memory space and the I/O space. They are however distinguished by an extra signal that tells whether the address/data is in the memory space or the I/O space. For instance, in x86 this signal is called $M/\overline{IO}$ (pin 28).


Understanding facts about regular languages, finite sets and subsets of regular languages

One useful fact about regular languages is that a union of finitely many regular languages is regular. From this it follows that all finite languages are regular: the language that recognizes a single constant string is always regular, and a finite language is a union of finitely many constant strings.

(Proof: remember that regular languages are exactly those representable by regular expressions. A regular expression can be trivially written to recognize a single constant string. To recognize a finite union of regular languages, simply combine their regular expressions with the union operator. Now you have a (potentially enormous but) finitely-long regular expression recognizing the entire language.)

This means that 1 is true, because a finite set is equal to the union of all its proper subsets, and an infinite language always has a non-regular subset.

(Proof: if a language $L$ is finite, then it has finitely many subsets, and is equal to the union of these subsets. If $L$ is infinite, then it has uncountably many subsets. But there are only countably many regular languages over a given alphabet, because regular expressions are strings and thus can be enumerated. Thus by diagonalization there exists a non-regular subset.)

2, on the other hand, is false as long as there exists an infinite non-regular language. (And such a language does exist: $\{ 0^n 1^n | n \in \mathbb{N} \}$ is a classic example.) It's not regular, but all its finite subsets are finite, and thus regular.

Your intuition is correct: 3 is false. The non-regular language I just mentioned is a proper subset of $\{ 0^a 1^b | a, b \in \mathbb{N} \}$, which is regular.

4 is also true, since any subset of a finite set is always finite.


Can we use a different encoding scheme to solve an unsolvable language?

Ultimately, no.

First, remember that a language is, literally, a set of strings over some alphabet. There is no coding at this level: a string (a sequence of characters from the alphabet) is either in the language or it's not.  For example, the language of even-length strings over $\{0,1\}$ is what it is; if you change it at all, it's a different language.

However, you probably don't mean for your question to be interpreted so literally, and you're presumably asking about languages such as "the set of strings that encode Turing machines with property $X$."  Strictly speaking, the description of such a language should always say, "Fix an encoding scheme $f$ of Turing machines as strings. Now consider the language of strings $f(M)$ such that $M$ is a Turing machine with property $X$." After all, if you don't say what the encoding is, you can't know if a particular Turing machine is in the language or not. So, presumably, your question is "Well, what if I use some other encoding scheme, instead?"

As long as there's a computable translation between the two encoding schemes, changing the encoding can't alter the computability of the language.  To see this, fix any set $S$ of Turing machines and consider codings $f$ and $g$ of these machines as strings. Suppose there's a computable translation between $f$ and $g$, i.e., a computable function $t$ such that, for all $M$, $g(M) = t(f(M))$.  If the language $L_g = \{g(M)\mid M\in S\}$ is decidable, then we can decide $L_f = \{f(M)\mid M\in S\}$, too.  To decide whether $w\in L_f$, just ask if $t(w)\in L_g$.  The reason people tend to be quite informal and just talk about "the language of Turing machines with some property" is precisely this: it doesn't matter what encoding you use, as long as you stick to encodings you can computably translate to the "standard" encoding, whatever reasonable encoding you want to view as standard.

In a strong sense, it's impossible to use any other encoding. For example, consider an encoding $f$ that isn't computably translatable to some standard encoding. Now, suppose I describe a Turing machine to you by listing the symbols in the alphabet, the states, the transition function and so on. You can't even compute $f(M)$, so you can't do anything useful with that encoding.

There are even encodings that make the halting problem decidable but they're a trick: they're not computable, so you can't actually use them.  For example, fix a computable encoding $g$.  Now, define $f(M)$ (uncomputably) as follows. If $M$ halts when started with a blank tape, let $f(M)$ be $2n$ written in binary, where $n$ is the number of Turing machines $M'$ such that $M'$ halts when started with a blank tape and $g(M')$ lexicographically precedes $g(M)$. Otherwise, let $f(M)$ be $2n+1$, where $n$ is the number of Turing machines $M'$ that do not halt when started with a blank tape and whose encoding $g(M')$ lexicographically precedes $g(M')$.  Now, the language $\{f(M)\mid M \text{ halts when started with a blank tape}\}$ is decidable: it's just the set of even numbers in binary.  But, as I said, this is a trick: it doesn't really let you decide the halting problem because, again, you can't compute $f(M)$ given a description of $M$.  (In particular, you can't even tell if $f(M)$ is even or odd.)


Generalized Büchi Automata - Formal definition of a state appearing infinitely often?

The definition and example are both correct.

If the automaton reads $a$ in state $2$ or reads $b$ in state $1$, then it rejects, because it has no state to go to.  So, if the machine reads an infinite amount of its input, then it must read $a$ every time it is in $1$ and read $b$ every time it is in $2$.  If the machine reads $b$ only a finite number of times, it only enters $2$ a finite number of times, so it must reject. Therefore, any string that's accepted must contain an infinite number of $b$s.  Since $b$s can only be read in state $2$ and the only way of getting there is to read an $a$ from state $1$, any accepted string must contain an infinite number of $ab$s.


Regular Language - Context Free Language

Your second method to arrive at $\phi$ is bogus - consider the case where $B$ is the empty language. Where you are confused here is you are looking at the difference between the sets of all regular languages and all context free languages, instead of the difference between the two concrete languages.

The correct answer is d. None  (you can't say anything)

Because

$R=\overline{A}-B = \overline{A \bigcup B} $

Since $A \bigcup B$ is clearly a $CFL$, this answer applies which states that the complement of a $CFL$ is not necessarily $CFL$ itself ($CFL$ are not closed under complement).


The following paper uses DFA minimisation for a minimal LR(1) parser: https://www.researchgate.net/publication/258746690_An_LR_parser_with_less_states


It looks like magic because the proof of Kirchhoff's Matrix Tree Theorem is nontrivial.
It relies on several algebraic properties of the matrix constructed in steps 1-3, which is called the Laplacian matrix of the graph.
Let $A$ be the adjacency matrix, and let $D$ be the diagonal matrix with the degrees of the nodes on the diagonal. Steps 1-3 build the matrix $L = D-A$: this is the Laplacian matrix of the graph.

So the question becomes, why should a minor of the Laplacian matrix be equal to the number of spanning trees of the graph?

To answer this question, we need to use other properties of $L$. One property is that we can also write $L$ as $B \cdot B^\top$ where $B$ is the oriented incidence matrix of the graph, that is, a matrix with one row per node $u$ and one column per edge $e$, where entry $B_{ue}=1$ if $e=\{u,v\}$ with $u<v$, $B_{ue}=-1$ if $e=\{u,v\}$ with $v < u$, and $B_{ue}=0$ if $e$ does not contain $u$.
For example, for a triangle graph, the Laplacian matrix is
$$ L=\left[\begin{array}{ccc} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{array}\right] $$
and the incidence matrix is
$$ B=\left[\begin{array}{ccc} 1 & 1 & 0 \\ -1 & 0 & 1 \\ 0 & -1 & -1 \end{array}\right]. $$
Note that the inner product of two distinct rows of $B$ is $-1$ if the corresponding nodes are adjacent, and 0 if they are not. The inner product of a row of $B$ with itself equals the degree of the corresponding node. (Just use the definition of $B$.) This is why $L=B\cdot B^\top$.

Assuming the graph is connected, the rank of $B$ is exactly $n-1$ where $n$ is the number of nodes of the graph. It is not $n$ because if you sum all rows, you get a zero vector. It is $n-1$ because the number of independent columns of $B$ is $n-1$: if you take any subset of columns corresponding to the set of edges of any spanning tree of the graph, these columns will be independent; the only way to have a dependent set of columns is when the edges selected contain a cycle.

If we delete a row and corresponding column of $L$, we obtain a matrix $M$. If we delete the corresponding row of $B$, we obtain a matrix $C$. Now $M=C \cdot C^\top$ for the same reasons that $L=B \cdot B^\top$. We are interested in $\det(M)=\det(CC^\top)$. In the example of the triangle graph above,
$$ M=\left[\begin{array}{cc} 2 & -1 \\ -1 & 2 \end{array}\right] $$
and
$$ C=\left[\begin{array}{ccc} 1 & 1 & 0 \\ -1 & 0 & 1 \end{array}\right]. $$

The last step is to invoke another algebraic fact, the Cauchy-Binet formula. This says that for any matrix $C$,
$$ \det(C C^\top) = \det (C_{K_1}) \det(C_{K_1}^\top) + \ldots + \det (C_{K_q}) \det(C_{K_q}^\top) $$ where each $C_{K_i}$ denotes an $(n-1) \times (n-1)$ submatrix of $C$ and the sum runs over all such submatrices. Thus,
$$ \det(C C^\top) = \det (C_{K_1})^2 + \ldots + \det (C_{K_q})^2. $$

However, $\det(C_{K_i})=\pm 1$ if the edges corresponding to $C_{K_i}$ comprise a spanning tree, while $\det(C_{K_i})=0$ otherwise (because then the set contains a cycle and the corresponding columns are not independent). Thus, the value of the sum is exactly the number of spanning trees.


How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?

The $k$-coloring problem is usually defined only for constant $k$, so $n$-coloring doesn't make sense. For every constant $k \geq 3$, the reduction you mention works. By adding a superconstant number of vertices you can show, for example, that $(n/2+3)$-coloring is NP-complete.


What is Herbrand interpreration and model?

Herbrand models have special domains. The domain of every Herbrand model for $S$ (which is a set of formulas of $L$) is the Herbrand universe $U_L$ for $L$. The set $U_L$ cannot be $\{0, 1\}$, it has a totally different form, see the definition of Herbrand universe in Chapter 1 “Preliminaries”, §3 “Interpretations and models”. The set $U_L$ can contain $p(a)$, $p(b)$, $p(f(g(a)))$ where $a$ and $b$ are constants of $L$, $p$ is a predicate symbol of $L$, $f$ and $g$ are function symbols of $L$, such things. It cannot contain $0$ or $1$.


Let's assume that optimal answer is $A = \{(free_1, paid_1), ..., (free_n, paid_n)\}$ where $\forall i: free_i \le paid_i$, also sort this pairs by $paid$, i.e. $paid_1 \le paid_2 \le ... \le paid_n$.

I will use pairs to show products grouping - 1st product in pair I get for free, and for 2nd I need to pay.

If there is such $i$ that $paid_{i-1} > free_i$, take 2 pairs
$(free_{i-1}, paid_{i-1}), (free_i, paid_i)$ (in this case we need to pay $paid_{i-1} + paid_{i}$) and swap prices:

In case $free_{i-1} \le free_i$ we got $(free_{i-1}, free_i), (paid_{i-1}, paid_i)$ (need to pay $free_i + paid_i$);
In case $free_{i-1} > free_i$ we got $(free_{i}, free_{i-1}), (paid_{i-1}, paid_i)$ (need to pay $free_{i-1} + paid_i$).

In both cases we don't do solution worse (we can not improve solution because we suppose that $A$ is optimal, but there is case that after swapping solution will not changed, e.g. $free_i < free_{i-1} = paid_{i-1} < paid_i$).

We have:

$paid_1 \le paid_2 \le ... \le paid_n$, that gives sorted sequence:
$\{paid_1, paid_2, ..., paid_n\}$
$\forall i: paid_{i-1} \le free_i \le paid_i$ (more intuition: in sequence from p.1 we insert $free_i$ on appropriate places), that gives sorted sequence: $\{free_1, paid_1, free_2, paid_2, ..., free_n, paid_n\}$

So we show that optimal answer can be expressed in form of sorted array.


Why does $L = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belong to $\mathrm{P}$?

You can easily write a polynomial-time algorithm to decide $L_1$ (just count the zeros and check you see the same number of ones), so the language is in $\mathrm{P}$.

Most non-regular languages are not in $\mathrm{P}$ because there are uncountably many languages in total, but only countably many languages in $\mathrm{P}$.

The halting problem is not in $P$. If you want a computable example then, by the time hierarchy theorem, any language that is $\mathrm{EXP}$-complete is not in $\mathrm{P}$.

This answer is intentionally brief because all the things I've mentioned are well-known facts that you should be able to look up, now that you know what to look for. If you need more detail, I suggest asking a new question about that, after checking that we don't already have a question about it.


an appropriate data-structure to represent a family of sets (Which supports exactly MAKE-SET(x), UNION(S1,S2), REPORT(S))

What they mean is: find data structures and algorithms to implement the MAKE-SET, DISJOINT-UNION, and REPORT operations.  That's all that they mean by "represent the family of sets".  The representation is the data structure where the data is stored.


There is left recursion in the grammar, so it isn't $LL(1)$.

The set of $LL(1)$ grammars is a proper subset of the $LR(1)$ grammars, see for example this summary, which incidentally also shows that $LL(1)$ isn't a subset of $LR(0)$. The first part is is intuitively easy to see, the $LL(k)$ parser has to decide looking only at the $k$ first symbols; the $LR(k)$ has the whole left hand side (and $k$ extra symbols) at its disposal.


Proving a PDA with CFG Transitions recognizes Context Free Languages

Hint: Try replacing each such transition by an appropriate PDA.


If you're asking how Google actually works, you'd have to ask Google.

If you're asking how a search engine could plausibly achieve this functionality in a reasonable amount of time (say, within 1 second), here are several strategies, any one of which could work fine:

Use a SSD.  Normally, a search index is a map from a search term to a sorted list of document IDs (the IDs of the documents that contain that search term).  Because these lists are sorted, you can compute the intersection of two lists in time linear in the length of those lists, by using the "merge" algorithm from mergesort.  (This is faster than the quadratic algorithm you list.)

As a result, the intersection can be computed in one pass, a streaming fashion.  For the parameters you mention, the bottleneck will be the time to read in those sorted lists from disk.  If you store them on a SSD, this can be relatively fast.  Some modern SSDs can achieve a read bandwidth of perhaps 2500 MB/s.  If each document ID is 4 bytes, reading in 4 billion document IDs will take about a half a second. The computation time is negligible in comparison, so the intersection could be computed under a second if indices are stored on a fast SSD.
Parallel computation. If you split the indices across multiple SSDs (say, using RAID or striping), you can increase the read bandwidth.  If you use a cluster of machines, each with their own SSD, you can parallelize both data transfer and computation.  The intersection task is trivially parallelizable, so you can achieve excellent speeds this way.  For instance, if you're using magnetic hard disks with read bandwidth of 200MB/s, striping the indices and computation across 8  machines is enough to finish this task in under a second.
Caching. You only need to do this work once.  Once you've computed the size of the intersection once, you can store it in a table and cache it for some time period (a month or more), as it's unlikely to change much in the future, and then once someone else asks the same cache, you can return the number of results instantaneously.
Estimation via random sampling. An even better approach is to avoid computing the entire intersection, but just estimate its size through random sampling.  You repeatedly do the following: randomly choose a document that contains computer, and check whether it also contains science.  Each trial (randomly picking a document that contains computer) can be done in one operation, by picking a random offset into the sorted list for computer, and then it's easy to check whether that document also contains the word science (say, by binary search into the sorted list for science).  Repeat this 1000 times, and you can get a good estimate of the fraction of documents containing computer that also contain science -- this uses the same principles as political polling, where we survey a random sample of people and then extrapolate to draw inferences about the entire population.  Multiply that fraction by the total number of documents containing computer, and you've got an estimate of the size of the intersection.

You can apply similar ideas to count the number of documents containing the phrase "computer science".


Can the Same Function Have Different Asymptotic?

The asymptotic behaviour of a function always depends on the parameter in the function. So for your example, I'd say that claiming that the function is exponential w.r.t. $k$, but polynomial w.r.t. to $n$ is correct.

When we look at the running time of algorithms, we consider it to be a function of the size of the input (usually the number of bits in a binary encoding). So, for an algorithm, it is always well defined whether it is for instance polynomial or not, but this can depend on how you define or encode your input.


Shortest path form node X to nodes A, B, C in graph

Use BFS, and keep prev pointers.  Good textbooks will have a chapter on shortest-path algorithms where they describe how to reconstruct the paths themselves (not just the distances) using prev pointers; use that method, and then you'll be able to reconstruct a shortest path from $X$ to any other node.  Initially the estimated distance to all nodes is $+\infty$.  Whenever you update the distance to something lower, update its prev pointer to point to the node where you came from.


Regular expression for odd binary numbers without leading zeros

First you might just add that single $1$ to your expression as an alternative to what you already have. One obtains $1 \cup 1(0\cup 1)^*1$.

An alternative is $1(0^*1)^*$. That one is shorter, but not necessarily better.

Actually that expression I obtained by starting with the FSA below, and realizing that the rightmost two states could be replaced by iterating $0^*1$.


Due to the dubious nature of the question, I only provide hints.

Have you tried the obvious? With probability $\frac{1}{n}$, add the new element to the sample. If it is added, choose one of the elements already in the sample uniformly at random and drop it. Sounds about fair, does it not?

For a proof, you will have to proceed inductively. In the step, you assume that $S_{n-1}$ is indeed a uniform sample. From this and the way you choose whether to include $x_n$ and which element to drop, you have to get that $S_n$ is a uniform sample, too.

Try if you can prove above idea correct. If it is not, find out where the problem is and fix it. See this answer to a similar question for a detailed application of this technique.


Input to make worst case on big O not possible?

It matters what is actually happening in the code. The following pseudocode is O(1)

loop_factor = input()

for x between 0 and loop_factor():
    for y between 0 and loop_factor():
        terminate

However, it doesn't matter what is likely or reasonable to happen. If the body of your loop makes it "virtually" guaranteed that the loop will terminate next iteration, that means nothing; you need an actual hard proof that the loop will exit early for all input, no matter how absurd.

Essentially if you can rewrite your algorithm so that the loop clearly can't iterate n times without changing the meaning (i.e. replace the loop with just a few copies of the loop body in if statements, or something), then you are justified in saying that the loop isn't going to do n iterations. If you really need the loop to be there in the code as a loop that can iterate up to n times, then the big-oh complexity of the loop almost certainly does have to be n times the complexity of the loop body.


Blob detection as Constraint satisfaction problem?

The constraint satisfaction problem (CSP) is NP-complete.  Identifying blobs is a question about graph connectivity which is in P.  Therefore, yes, the question you're asking reduces to CSP but this doesn't tell you anything useful: it just says that CSP is at least as hard as this problem but it might be harder.  (In fact, it is strictly harder if P$\neq$NP.)  Since your problem is in P, it is not (believed to be) NP-complete.

A related question is whether the problem can be expressed directly as a CSP without needing a reduction.

If a blob is any connected region then, in particular, any blob contains two adjacent pixels and any two adjacent pixels are part of a blob.  Therefore, if all you want to know is whether an image contains at least one blob, this is a constraint satisfaction problem.

However, if you want to identify a whole blob (e.g., output a list of all the pixels within some blob) or identify or count all the blobs, the problem is no longer a CSP.  The reason for this is that CSPs are not able to express connectivity conditions: there is no CSP in a finite constraint language that says "This graph is connected" because every instance of CSP is equivalent to a first-order formula and first-order logic can't tell the difference between connected and disconnected graphs.


Decide whether a context-free languages can be accepted by a deterministic pushdown automaton

There is no algorithm that given a context-free grammar, decide if a DPDA recognizes the same language and computes it if it exists.

Because if such an algorithm existed, we would be able to decide the undecidable problem of the universality of a context-free grammar i.e. whether a given context-free grammar $G$ on $Σ$ recognizes the whole language $Σ^*$.

Suppose there is such an algorithm $A_{DPDA}$. Let $G$ be some context-free grammar. Let $L$ be $\mathcal L(G)$. Then the algorithm $A_{DPDA}$ will decide if there is a DPDA $A$ recognizing $L$.

If there is no such DPDA, then $L$ is not recognizable by a DPDA, in particular it is not regular, so it can't be $Σ^*$.
If a DPDA $A$ exists then we can decide if $L$ is equal to $Σ^*$ because universality is decidable for DPDAs.
Why? Because:

DPDA languages are closed under complementation (because DPDAs are deterministic)
emptiness is decidable for DPDAs (because it is for PDAs)

Using $A_{DPDA}$ we have built an algorithm deciding whether $L(G)=Σ^*$ for any context-free grammar $G$, which has been proven impossible. Therefore $A_{DPDA}$ does not exist.


Model for formula $\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)$

If you're just asking for any model satisfying the formula, you simply try to make one of these the case

The left hand side false
The right hand side true

Let's just pick number 2.  You have to make a model (with a state $\sigma$) where $\Box \psi \lor \Box \phi$ is the case.  Even easier is $\Box \phi$.

Create a (trivial) model where every state $\sigma$ has $\sigma \models p$ for all propositions $p$.

If you want to see if the formula is valid then the answer is no.  You should now be able to create a model that falsifies the formula.


The notation is a crossover between

$\qquad\displaystyle \max_{i}$

and

$\qquad\displaystyle \max \{ \dots \mid i \}$.

It means the same as

$\qquad\displaystyle \max \{ G(W - s_i) + v_i \mid 0 \leq i \leq n, w_i \leq W \}$,

guessing about the domain of $i$.


What are some possible "functional" memory structures?

The topic is fairly broad.

Functional hardware has been explored in e.g. Lisp machines.

More on the theoretical side, you may want to read about the various abstract machines which have been proposed for running functional languages.
Some of them are the SECD machine, the CAM (categorical), the Krivine machine, the STG machine.

Perhaps a more radical approach can be learnt by looking at the various graph-reduction machines. A pioneering work by Lamping describes how lambda can be run faster by rewriting graphs (!), instead of expressions.
More recently, linear logic simplified the several rewriting rules.

Some of these approaches can give you some hint at how a custom functional hardware should be made to speed up execution.

For conventional hardware, the STG machine seems one of the most promising approaches.


Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?

Maybe the following perspective helps:

When you are trying to construct a Eulerian path, you can proceed almost greedily. You just start the path somewhere and the try to walk as long as possible. If you detect a circle, you will delete its edges (but record that this circle was constructed). By this you decompose the graph in circles, which can be easily combined to an Eulerian tour. The point is, none of your decision "how to walk across the graph" can actually be wrong. You will always succeed and never get stuck.

The situation with Hamiltonian paths is different. Again, you might want to construct a path by walking along edges of the graph. But this time you can really make bad decisions. This means you cannot continue the path, but not all vertices have been visited. What you can do is back-track. That means you revert some of your old decisions and continue along a different path. Essentially all algorithms that are known for the general problem rely on some way or the other on back-tracking, or trying out a large set of solutions. This, however, is characteristic for NP-complete problems.

So (simplified) bottom-line: Eulerian path requires no back-tracking, but Hamiltonian path does.

(Notice that it might be that P=NP and in this case a clever Hamiltonian path algorithm would exist.)


T1 is a schematic variable. Every consistent substitution of T1 with a type produces an instance of the rule. In a simple enough system, the inference rules can be used directly as the blueprint for a type-checking algorithm. In languages with richer type systems, type-checking algorithms become more complex or even undecidable (which is not a desirable features). Let me give an example where I type-check the program using a simple derivation.

Let's say I have the following program I wish to type-check:

(lambda x: nat. x = 0)(4)

First, we can deduce that 4 : nat by using the usual typing rules for natural numbers, which I will not reproduce here. Then we type-check the lambda abstraction with following derivation (I apologize for the sloppy latex):

$$ \underline{x : nat ⊢ x: nat \quad x: nat ⊢ 0 : nat} $$
$$ \underline{x : nat ⊢ x = 0 : bool}$$
$$ \underline{\lambda x: nat. \ x = 0 : nat \to bool} $$

Finally, using the application rules:

$$ \underline{\lambda x: nat. \ x = 0 : nat \to bool \quad 4 : nat} $$
$$ (\lambda x: nat. \ x = 0)(4) : bool $$

Note that type-checking is much simpler when we're working in a type system without subtyping, in that ever expression is monomorphic. The typing rules are syntax-directed. That is, the structure of the program dictates the type of every expression.


Algorithm for identifying correct subset

You can solve this by looking for a maximum cardinality matching in a bipartite graph, then covering remaining vertices arbitrarily.

Make a bipartite graph:

In the left part of the graph, make a vertex for every capital letter.
In the right part of the graph, make a vertex for every combination of lowercase letter and number.
For each record, make an edge (which necessarily goes from a vertex on the left to one on the right) corresponding to the two vertices covered by the record.

Now run an algorithm for finding a maximum cardinality matching in a bipartite graph, such as the Hopcroft-Karp maximum flow algorithm.  This picks a subset of edges (records) that together cover the most possible distinct combinations of capital letter and (lowercase letter + number).  That is, each chosen record hits both a capital letter, and a (lowercase letter + number) pair that are not hit by any other chosen record.

If the matching saturates (touches) every vertex, you have a "perfect" solution!  Otherwise, for each remaining vertex, you need to pick a record incident on that vertex -- it doesn't matter which record you pick, because it definitely won't be incident on any untouched vertices on the other side (if it was, then it would have been included in the matching already).


Does it matter if I reverse the arguments order of a lambda calculus function?

You can compute either of them from the other, by using the aforementioned "reverse arguments" function.

However, they are very different as functions. For instance, the usual encoding of true is $\lambda xy.\, x$ while false is encoded as $\lambda yx.\, x$ ($\alpha$-equivalent to $\lambda xy.\, y$), which is the flipped version of true. True and false are meant to be different.

Indeed, if we had true and false equal then, for any $M,N$
$$
M =_\beta^2 (\lambda xy.\, x) M N =_{Hp} (\lambda yx.\, x) M N =_\beta^2 N
$$
So, we would get that all $\lambda$-terms are equal, making the whole theory of lambda calculus trivial.


Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?

Use nondeterminism to guess an index $i$ for which $w_i \neq w_{i+1}$. The machine reads its input until it nondeterministically chooses a $w_i$ and places it on the stack. Afterwards, it compares $w_{i+1}$ to the content on the stack symbol by symbol. If the comparison fails, the machine accepts.


Is the mate-in-n problem of infinite chess with each color using traditional pieces plus one huygens decidable?

Presburger arithmetic with a predicate for the primes is probably undecidable, so at least the technique used by your question's link should not easily generalize to allowing a huygens.

For example, although decidability of the special case I'm about to mention

would follow from there being only finitely many positive even integers that

are neither prime gaps nor sums of two distinct primes, I don't see any way of

proving decidability of mate-in-ONE for king+huygens against a smothered king:


Mathematical proofs implemented purely by Lambda Calculus

So, the trick is that the untyped lambda calculus is not very useful as a mathematical proof, since it has non-halting terms.

Lambda Calculus as a proof system is most useful with types, particularly in terms of the Curry-Howard Isomorphism. Phillip Wadler has a great article outlining this.

The basic idea is that lambda abstraction corresponds to the way that you prove an implication. To write a function of type $A \to B$, you assume you have a value of type $A$, and use it to construct a return value of type $B$.
This is exactly how you prove $A \implies B$: assume that $A$ holds, then use this to prove $B$.

Not every lambda term corresponds to a mathematical proof in the sense we're used to, although each term can be regarded as a proof that its type is inhabited. In particular, to prove anything really useful, you need dependent types, where types are allowed to be indexed by values.

For Church-Numerals, their typed version if $\forall a \ldotp a \to (a \to a) \to a$, which, when interpreted as a proposition, is really boring. It's saying that if something holds, and it implies itself, then that something still holds.

For more information on the various type systems for Lambda Calculi, I'd start with the Lambda Cube.


You can iterate over all of the edges in $O(|E|)$ time.  So, construct a copy of the graph with reversed edges as follows: iterate over all the edges, and as you examine each edge, add the reversed edge to the copy.  That takes $O(|E|)$ time in total, and you only need to do it once, as a pre-processing step.  Now, during Kosaraju's algorithm, if you ever need to walk edges in a reversed fashion, you can just refer to the reversed graph you created earlier.


Enumerate probabilistic and other kinds of Turing machines together

When we talk about the enumeration of TM's, do we mean the "regular" deterministic ones?

We mean an enumeration of whatever kind of Turing machines we're talking about at the moment. Unless stated otherwise, "Turing machine" is normally taken to mean deterministic Turing machine.

  Perhaps one could think of a way to create some universal coding of TM's to strings that works for all different kinds of TM's?

There's no fixed list of "all different kinds of TM's", so I don't see how this would be possible.

  A related question, does a TM know it's own description?

It's not clear to me what it means for a TM to "know" anything.  A Turing machine is just its state set, transition function and so on.


Turn words array from a document with their coordinates into sentences

On this site, we only care about algorithm itself and not javascript. From what I gathered, your problem statement (without the javascript part) is:

  Given a set of rectangles in described in Cartesian coordinate,
  (1) partition the set into "lines"
  (2) sort rectangles within each "line" by their position along the "line"

The reason I put the word "line" in quotation is because there are many ways to define it, and you didn't give enough information to decide which one.

Let's formulate this a bit: we are given

set $S$ of rectangles
four functions $t,b,l,r \colon S \rightarrow \mathbb{N}$ standing for top, bottom, left and right coordinate of the rectangle respectively.

We need to output:

ordered partition of $S$ such that "each partition is a line"

For convenience, I'm going to let $\sim \subseteq S \times S$ denotes the equivalence relation that partition $S$ into lines.

Here are three separate (not exhaustive) examples of definition of a line:

Two rectangle is in the same line if they have the same bottom $y$ value.$$x \sim y \iff bx = by$$
A rectangle is in the same line with its nearest neighbour in $y$ direction that is not further than some threshold.
$$y = min_z |bx-bz| \implies (|bx-by| \leq T \implies x \sim y)$$
don't forget to make $\sim$ transitive.
Decide on the direction of a line first which may not be parallel to $x$ axis. Change the basis of coordinate. Then apply one of the above.

Decide on one you want according to the degree of sophistication needed to handle your input. Once you have the partition (supposed by $y$ value), you can then sort each by $x$ value.

Finally, there is also the alternative to do Hough Transform which is also generally applicable to bitmap images. In our case, our image is one of rectangles (or centre of rectangles, or corner of rectangles).


You ask for a graph where your (nondeterministic) algorithm gives the optimal solution even in the worst case. We're looking for a set of vertices that cover all edges. The difficulty with your algorithm is not only that it could pick the edges in an "inconvenient" order, but also that it adds both vertices belonging to the edge, which is suboptimal in most cases (since adding one of the vertices already covers the edge).

An example where your algorithm does always find the optimal solution of size 10, is the graph below. If you meant the problem the other way around (cover all vertices), the same graph applies.


You are right that the outer-loop is executed $N$ times, and you are almost right regarding the inner loop. Observe that the inner-loop does not loop the same amount of times at every iteration of the outer-loop. In particular, it will first loop $N-1$ times when $i = 0$, then it will loop $N-2$ times when $i = 1$, $N-3$ times when $i = 2$, and so forth. Therefore, the inner-loop is executed $(N-1) + (N-2) + \ldots + 1 + 0$ times which is the following well known summation: $$\sum_{i=0}^{N-1}i = \frac{(N-1)\cdot N}{2}$$

A similar argument can be made to show what the runtime of the inner-most-loop is. In particular, you will get a similar type of summation.

In general, you will model the loops as summations, and simply evaluate the sum. In your example, you will have that: $$T(N) = \sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}}O(1)$$ and evaluating this will give you your $O(N^3)$ answer. Remember that the goal is to "count" the number of primitive operations by the algorithm in question.


What is the meaning of phenotype could be represented by a number of different genotype

The same function can be described in several ways.
If you're familiar with finite automata, then you should know that the same regular language ("phenotype") can be represented by many different finite automata ("genotype").
The same holds in many other cases, unless you choose an encoding which guarantees that every function has a unique description. It is not clear whether this is even desirable. For example, the genetic code has some redundancy which causes the same DNA sequence to encode the same proteins.


Solving recurrence relation with two recursive calls

As you mention, the Akra–Bazzi theorem shows that the solution to the recurrence $T(n,p)$ is $O(n\log n)$ for all $p \in (0,1)$. However, this does not reveal the nature of the dependence on $p$. To determine the latter, we can use a recursion tree approach.

At the root of the recursion tree is the interval $\{1,\ldots n\}$. Its two children are the intervals $\{1,\ldots,pn\}$ and $\{pn+1,\ldots,n\}$, whose total length is again $n$. Each of these nodes has two children (assuming $n$ is large enough), and so on. For simplicity we ignore rounding errors, that is, we assume that $pn$ is an integer; this is just a technicality, and I wouldn't worry about it. We stop the process whenever a node has length at most $1$. The complexity of the algorithm is proportional to the total length of intervals in the tree. When $p \neq 1/2$, the leaves (nodes at which we stop the process) have different depth, and that makes it more difficult to determine the overall complexity.

We can obtain a simple upper bound by noting that the tree has at most $\log_{1-p} (1/n)$ levels: each node is at least a factor of $1-p$ smaller than its parent. Just like in the analysis for $p = 1/2$, the total length of intervals at any level is at most $n$, and we obtain an upper bound of $O(n\log_{1-p} (1/n))$ on the running time. Since $\log_{1-p} (1/n) = \log n/\log (1-p)^{-1}$ and $\log (1-p)^{-1} = -\log (1-p) = p \pm O(p^2)$ for small $p$, we can write this as $O(n\log n/p)$.

Here is a more accurate calculation. Consider level $t$. Suppose we don't stop the process upon reaching a small interval. We can generate a random vertex by taking $t$ steps, in each of which we go left (say) with probability $p$ and right (say) with probability $1-p$. Each time we take a left step the log of the length of the interval decreases by $-\log p$, and each time we take a right step it decreases by $-\log (1-p)$. A vertex is in the actual tree of the log of the length decreased by at most $\log n$. The total weight of intervals on level $t$ of the tree is exactly the probability that a vertex generated according to this process correspond to a decrease of at most $\log n$. That is, if $D$ is the distribution which is equal to $-\log p$ with probability $p$ and to $-\log(1-p)$ with probability $1-p$, and $X_1,\ldots,X_t \sim D$ are independent, then the total weight of level $t$ is $\Pr[X_1+\cdots+X_t \leq \log n]$. For super-constant $t$, the random variable $X_1+\cdots+X_t$ is roughly normally distributed with mean $[-p\log p-(1-p)\log(1-p)]t$ and variance linear in $t$, so for $t$ satisfying $[-p\log p-(1-p)\log(1-p)]t \leq (\log n)/2$, say, the probability will be very close to $1$, while for $t$ satisfying $[-p\log p-(1-p)\log(1-p)]t \geq 2\log n$, say, it will be very close to zero. Defining $h(p) = -p\log p-(1-p)\log(1-p)$ (known as the binary entropy function), we conclude that the running time is $\Theta(n\log n/h(p))$ (uniform in $p$, as $n\to\infty$). As $p\to 0$ we have $h(p) \approx -p\log p$, and so our earlier estimate was not tight.

Another way of looking at the same analysis is by having an infinite sequence of independent random variables $X_1,X_2,\ldots$ as before, and defining a stopping time $T$ to be the first time $t$ such that $X_1 + \cdots + X_t \geq \log n$. The running time is then proportional to $n\mathbb{E}[T]$. The elementary renewal theorem then states that $\lim_{n\to\infty} \mathbb{E}[T]/\log n = 1/\mathbb{E}[D] = 1/h(p)$, implying that the total size of intervals equals $(1+o(1))n\log n/h(p)$. More accurately, for every constant $p$ the total size of intervals is $(1+\alpha_p(n))n\log n/h(p)$, where $\alpha_p(n) = o(n)$. The convergence in the elementary renewal theorem is exponential in the time parameter — $\log n$ in our case — so should be polynomial in $n$, that is, $\alpha_p(n) = O(n^{-C_p})$. The convergence is also probably uniform for $p \in (\delta,1-\delta)$ for any $\delta > 0$.

Summarizing, the total length of intervals in the recursion tree, which is proportional to the running time, is of the following form for every $p$: $$ T(n,p) = (1+o(1)) \frac{n\log n}{h(p)}, $$ where $\log n$ and $h(p) = -p\log p-(1-p)\log(1-p)$ are taken to the same base, and the $o(1)$ is a function depending on $p$ and tending to $0$ with $n$.

Moreover, it is probably true that for any $\delta > 0$ and any $p \in (\delta,1-\delta)$ it is true that the total length of intervals is of the form $$T(n,p) = (1+O(n^{-C_\delta})) \frac{n\log n}{h(p)}, $$ where $C_\delta > 0$ and the hidden big O constant depend only on $\delta$. In particular, it should be the case that for all constant $p_1,p_2$,
$$\lim_{n\to\infty} \frac{T(n,p_1)}{T(n,p_2)} = \frac{h(p_2)}{h(p_1)}, $$
and the convergence is polynomially fast.


Find non-overlapping subsets that maximize the sum of their values

Yes this problem has already been studied. It is a well-known $NP$-complete problem known as Set-Packing. Your problem is a weighted optimization variation, but the same principles apply.


What is the difference between "Decision" and "Verification" in complexity theory?

The task of deciding membership is: given any input $x$, decide wether $x \in L$, i.e. compute the following function:

$\qquad \displaystyle \chi_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$

On the other hand, the task of verifying membership is: given any input $x$ and a (proposed) proof (or witness) of membership, check quickly wether $x\in L$ by that proof¹.

For example, consider prime factorisation. Given $n \in \mathbb{N}$, compute all prime factors of $n$. On the other hand, given $(n, \{i_1, \dots, i_k\})$, verify that $\prod_{j=1}^k i_j = n$. Which is easier?

Another example: Given a weighted graph $G = (V,E)$, decide wether there is a Hamilton circle (that visits all nodes) with weight at most $k$. On the other hand, given $(G, (v_1, \dots, v_n))$, verify wether the path $v_1 \to \dots \to v_n$ visits all nodes exactly once and has weight at most $k$. Which is harder?

So you will say "no" if $x \in L$ but the proof is wrong. That is fine, though, as we consider nondeterministic machines in this context; it is only important that we can guess the correct proof and verify it (quickly).


Does there exist an equivalent arithmetic circuit for each computable function?

Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit.  Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$.  Then there exists a multivariate polynomial $p(x_1,\dots,x_n)$ such that $f(x_1,\dots,x_n) = p(x_1,\dots,x_n)$ for all $x_1,\dots,x_n$, where arithmetic is done modulo two (i.e., over the field $\mathbb{F}_2=\{0,1\}$).  Now every multivariate polynomial can be computed by a an arithmetic circuit, so $f$ can be computed by an arithmetic circuit.

In some sense the restrictions to fixed-length inputs is unavoidable, as any circuit inherently has a fixed number of inputs and a fixed number of outputs.   So once you decide to focus on boolean functions, then the statement you saw in the crypto literature is justified: any boolean function that can be computed by a circuit, can be computed by an arithmetic circuit.  And, any computable boolean function can be computed by arithmetic circuits, where we understand "computed" to mean that there is a family of arithmetic circuits, one per input length (the non-uniform model; this is unavoidable if you want to compute using circuits, as any one circuit can only have a fixed input length).


Nondeterministic automaton accepting only words whose first letter is identical to their next to last letter

Hint: you want to make states $x/y/z$  which mean that $x$ is the first symbol of the word, $y$ is the second to last symbol seen, and $z$ is the last symbol seen.

I will show you half of the final machine, the one for words starting with $a$. Note that "!a" here means any symbol not equal to a, or no symbol at all.


Negative cycle detection using Bellman-Ford and its correctness

If there are no negative cycles then you can indeed perform the relaxation until all values remain the same.
In the $i$-th round of relaxation you are ensured to have correctly computed all finite distances towards all vertices whose hop-distance from $s$ is at most $i$ (the hop distance is the number of edges in a shortest path).

Therefore stopping after the $(n-1)$-th iteration ensures that:

All finite distances have been correctly computed
The algorithm terminates on graphs with negative cycles.

Notice that there are graphs where all $(n-1)$ iterations are needed to properly compute the distances. E.g., a path.

Regarding 2), your question is not completely clear to me. In the proof there is no particular edge to visualize. The proof just shows that if it impossible for these two conditions to be simultaneously true:

There is some  negative weight cycle $C$.
No relaxation happens, i.e., $v.d \le u.d + w(u,v)$  for all vertices $v$ of the cycle. This is used in the second centered inequality.


Methods for Finding Asymptotic Lower Bounds

You can codify your method in the following lemma.

Lemma. If $f(n)/g(n) \rightarrow C$, where $C > 0$, then $f(n) = \Theta(g(n))$.

The proof is the same as the one you gave. After you prove this lemma once and for all, you can use it forever. That's actually a good way of verifying $f(n) = \Theta(g(n))$.

Note that the converse to the lemma isn't true. For example, let $f(n) = n$ and let $g(n) = \exp\lfloor\log n\rfloor$. The ratio $f(n)/g(n)$ moves inside the interval $[1,e)$, and in particular does not tend to a constant limit.


Why are PTAS-Reductions used to establish APX-Hardness?

Let me correct two misconceptions in your question:

$PTAS$-reductions are approximation-preserving
$APX$ is the class of problems that have constant-factor approximations

The big open question isn't whether $APX$ problems have constant-factor approximations (by definition, they do), but whether they have polynomial time approximation schemes. The meaning of $APX$-complete is "As hard as any problem in $APX$ to find a polynomial time approximation scheme for". A $PTAS$ from $A$ to $B$ reduction allows any polynomial time approximation scheme for $B$ to be used for $A$.


Type system with subtyping on abstract data types?

You want to write some executable code (is_left_restartable) and use it inside a type annotation. This is, by definition, a dependent type.

The problem when you have dependent types is that it's hard to keep type checking usable for a programming language. It's generally desirable to keep the type system decidable, because programmers tend to be annoyed when a programming error causes the compiler to loop forever. So at the very least the type constraints need to stick to a subset of the language that guarantees termination. And of course since type constraints are evaluated at compile time, they can't contain any side effects.

It isn't too difficult to define a subset of the language without arbitrary recursion. For example, just forbid recursive functions. And, to keep things simple, forbid the use of library functions or functions defined in a different module — if you don't do this then library functions need to be annotated, not only so that the type checker knows that they're allowed in types, but also so that the compiler knows what to make of them.

Even if type constraints are in a subset of the language that always terminates, that doesn't make them decidable. For example, if the type constraints can include enough arithmetic to encode addition and multiplication of variables — a context in which this comes up naturally is array lengths — then the type system encodes Diophantine equations and is therefore undecidable. It's possible to keep the system decidable if it only allows additions and not multiplications of variables, as in Dependent ML.

Even when type checking remains decidable, it's a lot harder to keep type inference decidable. That's not a big problem in itself, because programmers who want to benefit from the finer-grained types can just write type annotations. But it can be difficult to precisely define when type annotations are needed and when they aren't. It's still a difficult problem to find a good balance between requiring a lot of annotations, and making it easy for programmers to know when annotations are needed.

When the type constraints are purely defined in terms of pattern matching, as in your example, they can be expressed using generalized algebraic datatypes (GADT). GADT have matured enough to be supported in mainstream languages, notably OCaml. To avoid extensive analysis of which functions are allowed in types, most implementations of GADT including OCaml's use the type system to express constraints, not the term syntax. You would need to define is_left_rotatable as a type, and to write a transformation function from matching trees to is_left_rotatable.


A simpler way to see that this grammar is not LALR(1) is to look at the LR(1) item sets:

$S' \rightarrow \bullet A,\enspace \$$
$A \rightarrow \bullet aBb,\enspace \$$
$S' \rightarrow A\bullet ,\enspace \$$
$A \rightarrow a\bullet Bb,\enspace \$$
$B \rightarrow \bullet b,\enspace b$
$B \rightarrow \bullet ,\enspace b$
$A \rightarrow aB\bullet b,\enspace \$$
$B \rightarrow b\bullet ,\enspace b$
$A \rightarrow aBb\bullet ,\enspace \$$

You can see that in state 3 the shift/reduce conflict remains, even in LR(1). This grammar is not LR(1), and thus not LALR(1).


How can Weighted MaxSAT be in $FP^{NP}$ when dealing with large weights?

The input length is not $m$. To represent an integer of $2^{2^m}$, one needs $\log_2{2^{2^m}}=2^m$ bits. Hence an algorithm taking $2^m$ steps is considered linear in the input length, which is $2^m$.

A number like $2^{2^m}$ can be represented by just giving $m$, but it is usually assumed that numbers are given in binary. And the result that MAX-SAT is in $FP^{NP}$ only holds when that encoding is used.


Streaming digit-to-digit conversion from decimal to hexadecimal

I don't think this is possible. Changing a high-order digit in a base-10 number -- say, changing 5000000 to 6000000 -- can change bits in its binary equivalent all the way from high-order bits to fairly-low-order bits:

10011000100101101000000
10110111000110110000000

It doesn't change the very lowest bits: Since $10 = 5\times 2$, the digit in position $k$ in a decimal number is a multiple of $10^{k-1} = (5\times 2)^{k-1} = 5^{k-1}2^{k-1}$, so changing it will never change the lowest $k-1$ bits of the binary representation. But it can change the $k$-th bit, and bits in positions up to $\log_2(9\times 10^{k-1}) = (\log_2 10)(k-1) + \log_2 9 \approx 3.322(k-1) + 3.170$. This is true for any $k$, so the range of affected digits grows indefinitely as $k$ increases.

If you were, say, trying to convert between base 4 and base 8, you could group each block of 3 base-4 digits into a base-64 "superdigit", which you could then convert back down to 2 base-8 digits since 8^2 = 64.

But there is no "right" superdigit base for the bases 10 and 2, since 10 contains 5 as a factor and 2 does not: every positive integer power of 10 contains 5 as a prime factor, and no positive integer power of 2 does, so by the uniqueness of prime factorisations there is no integer that is a power of both 2 and 10.


If you have only positive examples (strings that are in the language), in principle, no, you cannot infer the grammar.  For all you can tell, the language might be $\Sigma^*$: no matter how many example strings you have, you'll never be able to rule that out as the language.

However, if you have a little more information, there are known solutions.  You can take a look at Angluin's algorithm.  If you need a software implementation, take a look at LearnLib.  See also Wikipedia's page on grammar induction for other approaches.

Another approach is to try to find the smallest context-free grammar that can generate every string in your set of examples, and nothing else.  Finding the absolute smallest CFG is probably hard, but there are known heuristics that tend to give a good solution in practice.  I'd recommend the Sequitur algorithm, if you need something in practice and have only positive examples.  This gives up generalization -- there might be an even simpler/smaller CFG that can generate every one of your example strings as well as some others -- but for some applications it works reasonably well in practice.


Printing actual solutions for the coin exchange problem

Assuming that you want the minimum number of coins to achieve a desired value and that you have a sufficient number of coins of every value we have this relation of recurrence:

Let $S(i,k)$ be the minimum number of coins to achieve the value $k$ considering the first $i$ coins. Also, let $V[i]$ be the value of the $i$-th coin.

So:

$$S(i,k) = \begin{cases}
0 & i = 0 \land k = 0\\
-\infty & i = 0 \land k > 0\\
S(i-1,k) & i > 0 \land V[i-1]-k < 0\\
\max(S(i-1,k),S(i,k-W[i-1])) + 1 & \text{otherwise}
\end{cases}$$

Case 1 = Base case, considering the first 0 coins and the value 0 you pay 0 coins.
Case 2 = Base case, considering the first 0 coins and a value greater than 0 you cant pay the value.
Case 3 = Considering the first $i$ coins you can pick the solution to pay the value $k$ without considering the $i$-th coin, which is in $S(i-1,k)$.
Case 4 = Considering the first $i$ coins, you should maximize between the solutions considering the $i$-th coin and not considering it. If the i-th coin is considered, you increment the number of coins in the solution, because you used the $i$-th coin.

A recursion based solution follows in verbatim from this relation of recurrence, but in Dynamic Programming you will replace a recursive call by a table lookup. So basically, where is $S(a,b)$ you will replace by a table access $S[a,b]$.


Counting elements that are greater than the median of medians

In

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg)
$$

we are subtracting 2 in order to discard the group containing the median of medians and the group of leftovers. So, 2 is the number of groups we are discarding.

First of all, note that there may not be a group of leftover elements: if $n$ is an exact multiple of 5 there will be no leftover group. We are interested in bounding from below the number of elements greater than the median-of-medians in the worst case, so suppose that a leftover group exists. Therefore, it will contain  at least an element and no more than 4 elements. If you want to reason in terms of elements to be discarded and not in terms of groups, then we must discard exactly 3 elements for the group containing the median of medians (including the median of the medians), and at most 2 element from the leftovers group (if this group contains 1 or 2 elements you do not discard any element; if this group contains 3 or 4 elements, then you discard respectively 1 or 2 elements which are greater than the group's median). So, you discard in the worst case (leftover group with 4 elements) 3 + 2 elements:

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 5
$$


Does there exist a problem that is hard to do in parallel?

Linear programming is P-complete with respect to either logspace or NC reductions (I'm not sure which).  As such, it's unlikely to be efficiently parallelizable because, for either kind of reductions, that would imply that P$\,=\,$NC. It's generally believed that P$\,\neq\,$NC.

There's more information on Wikipedia's P-completeness page.


What does big O mean as a term of an approximation ratio?

The expression "$A(L) \le (1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$" is, as usual, shorthand for the following:

  There exist constants $c>0$ and $\varepsilon_0>0$ such that for all $\varepsilon$ with $0<\varepsilon<\varepsilon_0$, the inequality $A(L) \le (1 + \varepsilon) \text{Opt}(L) + c/\varepsilon^2$ holds.


Will the randomized Quick sort will have same runtime in terms of big O for A1, A2, A2

Statements like this do not make any sense. For any given input, any algorithm has running time O(1).

Note that Landau notation (here) inherently contains a "for size to infinity" clause. Therefore, it makes only sense for infinite input sets.

Then, yes, the result depends a lot on the input sequences you consider. If you average over all inputs, you get $\Theta(n \log n)$. If you average over all worst-case inputs, you get $\Theta(n^2)$.


Is the complement of $ww^R$ context-free?

If you want to show that $L$ is context-free, you can proceed as follows:

Build a push-down automaton $P$ that accepts $L$. $P$ will read the input and put all the read characters on its stack. At some point it guesses (non-deterministically!) that half of the input has been read. Then it reads the remaining input and checks it a against its stack. If $P$ finds a mismatching character it accepts, if it does find not a mismatch, or the guess for the middle of the word was wrong, it rejects.


Given $\phi$ and an assignment $\overline{y}$, the problem of deciding if there exists a satisfying assignment $\overline{x} \le \overline{y}$ (w.r.t. the lexicographical order) is in NP.
This can be seen by either designing a nondeterministic Turing machine that solves the problem in polynomial time (nondeterministically guess $\overline{x}$, then deterministically check if $\overline{x} \le \overline{y}$ and $\phi(\overline{x}) = \top$, if so accept, otherwise reject), or by noticing that $\overline{x}$ itself is a yes-certificate for the instance (that can be deterministically checked in polynomial-time).

Then your original problem is in $\Delta_2 = P^{NP}$: perform a binary search on the space of the $2^n$ possible assignments to find the smallest satisfying assignment $\overline{x}^*$ for $\phi$. This can be done by repeatedly solving the above problem, each time halving the search space. After $O(\log 2^n) = O(n)$ iterations you are left with $\overline{x}^*$. Check whether $\overline{x}^*_n = 1$ and answer accordingly.


What is wrong with this reduction from vertex cover to binary programming?

Your example does not hold since the first entry of $Ax$, 0 is smaller than 1, the first entry of $b$.

$$
\begin{array}{c c c}
&Ax &  &b\\
& \begin{bmatrix}0 \\1 \\2 \\1 \\1\end{bmatrix}
& \not\ge\
& \begin{bmatrix}1 \\1 \\1 \\1 \\1 \\\end{bmatrix}
\end{array}
$$

Please note the condition $Ax\ge b$ means every entry in $Ax$ is no less than the corresponding entry in $b$. In term of the corresponding problem, the vertex cover problem, it means every edge is incident to at least 1 vertex. It is not about the $L_1$ norm; otherwise, it should be written as, for example,  $||Ax||_1\ge ||b||_1$.

Yes, we want to minimize the number of 1's in $x$, which is the same as minimizing $||x||_1$. However, the condition $Ax\ge b$ is a requirement on $x$. The requirements on the variable that are usually read as "subject to ..." and the objective function could be seen as irrelevant or independent to each other.


Unless I misunderstood your question, in a NFA $N$ that is a path one vertex has in-degree $0$ and outdegree $1$, one vertex (possibly the same) has in-degree $1$ and out-degree $0$, and all the other vertices have in-degree $1$ and out-degree $1$.

Let $N'$ be the NFA obtained by identifying all the vertices in the same component of the (undirected version of the) subgraph induced by all the edges labelled $\varepsilon$ in $N$. All vertices of $N'$ have maximum out-degree $1$, moreover $N'$ contains no edge labelled $\epsilon$. This shows that $N'$ is a DFA. The process can be performed in linear time.

A note: when a set $S$ of vertices from $N$ is identified into a single vertex $v$ in $N'$, you will need to mark $v$ as a final state in $N'$ iff at least one the vertices in $S$ is a final state in $N$.


Reduction from 3 SAT to Monotone Exact 1 in 3 SAT

Here are some ideas to get you started. You can find on the internet simple gadget reductions from 3SAT to 1-in-3SAT. In monotone 1-in-3SAT you are not allowed to use negations, but if you allow clauses of width 2, you can add clauses
$$ x_i^+ \lor x_i^- $$
for each variable $i$. This clause forces $x_i^- = \lnot x_i^+$, and so allows you to simulate negations. If you really insist that your clauses have width 3, you need to be slightly more devious. Try to figure out a way yourself, and only if you're unsuccessful, take a look at my solution below:

   For example, you can add three new variables $a,b,c$, replace $x_i^+ \lor x_i^-$ with the pair of clauses $ x_i^+ \lor x_i^- \lor a$, $x_i^+ \lor x_i^- \lor b$, and add the clause $ a \lor b \lor c$.


How to pass comma separated values from yacc to cpp file node

args_list’s type can be vector.
Then, instead of calling to new array_node you can have a factory method (array_node::factory) which parses the type, casts the args and returns the array_node object


Any Non-trivial Logic System Defined with only Equality

If all you have is equalities and uninterpreted function symbols, then you have an algebraic theory a la universal algebra. A singleton set (or a collection of them in the multi-sorted case) is always a model of an algebraic theory. That is, every algebraic theory is, at least, trivially satisfiable. So if both $S$ and $F$ are required to simply be conjunctions of equations, then $SAT(S)=SAT(F)=SAT(S\land F)=\top$.