Suppose you're trying to place $Q$ queens, $R$ rooks, $B$ bishops, $N$ knights, and $K$ kings.  Then doing things the way you're doing them now, at least provided the language isn't clever enough to memoize the pure function calls for you, means that you're processing each solution $Q!R!B!N!K!$ times, rather than once, since in a solution containing $Q$ queens you could have placed them in any of $Q!$ different orders, and so forth.

Similar logic also applies to the partial solutions in your call stack.

If you're just trying to place one of each piece then this isn't so bad.  If, on the other hand, you're trying to place 8 queens on an 8 x 8 board, this means each solution gets generated 8! = 40,320 different times.

This is probably the single largest issue you're seeing here.  I tested this out by writing a naive python program, and it was able to do 8 queens on an 8x8 board in considerably less than fifteen minutes running on a single core of my twelve-year-old laptop with 1GB of RAM.

I'm not particularly familiar with Scala but it's possible you could just keep your existing code but tell it to memoize your function, at least provided it's written as a pure function.

Other optimizations would be to parallelize the analysis (which, again, a functional language like Scala might be able to do near-automatically for you), and to take advantage of the four- or eightfold-symmetry of the problem (depending on whether the board is square or just rectangular) by putting everything into a canonical form.

One last thing to check is that the intermediate data is stored in such a way that you're not having to recalculate anything.  When checking for a blank square, you want a stored list of blank squares you can iterate over.  When checking to see if the piece you just added is threatening something already on the board, you want a stored list of occupied positions to work with.


Find the number of values between i & j(given as input) in an unsorted array in O(1) time

In $A$, $rank( A[i] ) = \left\vert\left\{ j \in A : -\infty < j < A[i] \right\}\right\vert $

So you could sort the array by putting each element at its rank (up to duplicates, which can also be counted with 2 range queries), so if you could answer queries like this in $O(1)$ time and $O(n)$ preprocessing time and space, you would have an $O(n)$ sorting algorithm.

The latter does exist of course, but only under certain constraints, eg on the range of values.


This explanation is for the Homo sapiens sapiens subspecies of Cercopithecidae (old world monkeys).  For an explanation suitable for other subspecies you'll have to try Knuth.

I'll assume you are talking about collision resolution by open addressing, and double hashing to determine the probe sequence.  Further we'll assume that the hash functions are good (that is: that they are essentially producing uniformly distributed, independent random integers.)

We will use $N$ for the number of objects already in the hash table, $M$ for the total number of buckets in the hash table and $\alpha = N/M$ as the load factor.  The load factor is the fraction of buckets that are already taken, and is really the important thing here.

If I try to insert a new item in a hash table with load factor $\alpha$ what is the probability that I will get a collision on my first probe?  Answer: $\alpha$.  Thus the probability that I find an open bucket on my first probe is $1-\alpha$.

What is the probability that I will find an open bucket on exactly my second probe?  Well the probability that I failed to find an open bucket on my first probe is $\alpha$ and the probability that I succeed on my second probe is $1-\alpha$, which gives a total probability of $\alpha (1-\alpha)$.

What is the probability that I will find an open bucket on exactly my third probe?  Well the probability that I failed to find an open bucket on my first and second probes is $\alpha^2$, and the probability that I succeed on my third probe is $1-\alpha$ so I have a total probability of $\alpha^2 (1-\alpha)$.

I'm an engineer, not a mathematician, so that's good enough for me to assume that the pattern holds for all positive integers.  That is I've just "proved" that the probability I will take $k$ probes to find an open bucket is
$$ p(k) = \alpha^{k-1} (1-\alpha). $$

(Exercise: make sure that this is a good probability by showing that $\sum_{k=1}^\infty \alpha^{k-1}(1-\alpha)=1$.)  Now what's the expected number of probes to find an open bucket?

$$ \begin{eqnarray}
   E[\mathrm{number\ of\ probes}] &=& \sum_{k=1}^\infty k p(k) \\
                                  &=& \sum_{k=1}^\infty k \alpha^{k-1}(1-\alpha) \\
                                  &=& (1-\alpha)\sum_{k=1}^\infty k \alpha^{k-1} \\
                                  &=& \frac{1-\alpha}{\alpha}\sum_{k=1}^\infty k \alpha^k.
\end{eqnarray}$$

I look up this series on Wikipedia and see that $\sum_{k=1}^\infty k \alpha^k = \alpha / (1-\alpha)^2$ so

$$ E[\mathrm{number\ of\ probes}] = \frac{1}{1-\alpha}.  $$


How to count the bits with a 1 bit error correction Hamming code?

Yes, it is about what bit-endianness you choose. Just make sure you are using the same interpretation on both ends.

(However if on 'Endian ordering' you meant byte order, that does not really apply here. As most Hamming codes do not transfer a whole number of data bytes, it is far simpler to think about the input as a stream of bits)


What does a kernel of size n,n^2 ,... mean?

The point of investigating a parametrized problem is that we hope or assume that the parameter will be fairly small or even bounded by a known small constant in some particular case you encounter in practice. In that case, algorithms with FPT could be called efficient.
So yes, you can definitely pick an arbitrary parameter that will be very large in practice, but then a linear kernel will probably not be useful, because you are measuring the wrong parameter.
As a side remark, this is not something specific to parametrized complexity. In any type of complexity, you must be careful that the thing your are investigating the complexity of is actually meaningful.


Is there any graph problem that, when restricted to trees, has $\Omega(n^2)$ time complexity?

Yes. By the time hierarchy theorem, there is a (tractable, solvable in $O(n^2 \log n)$ time) problem $X$ that (on an $n$-bit instance) can not be solved in less than $\Omega(N^2)$ time.

Given an $n$-bit string, I can encode it as a tree, for instance by taking a path $p_1,\ldots, p_n$ of length $n$ and adding an additional leaf vertex to vertex $p_i$ if the corresponding bit $i$ in the string is $1$ (and perhaps adding some constant-size gadget to mark the beginning of the string).

Now I will define problem $Y$ to be to recognize the trees that encode a bitstring that is a (valid) instance of $X$. Clearly this problem requires at least quadratic time (or otherwise we would have a faster algorithm for $X$).

This is of course a rather contrived and artificial example, but there are some  natural problems that are hard for trees as well. See e.g. NP-hard problems on trees.


Dynamic programming: how to solve a problem with multiple constraints?

The practical solution is to formulate this as an instance of integer linear programming and apply an ILP solver.  There will be a clean formulation as ILP, and it might work pretty well.  For each item, you have an associated variable $v_i$ that is zero or one according to whether item $i$ is included in the basket or not (one means that it is included); then every one of your requirements can be expressed as a linear inequality on the $v_i$'s.

For example, the requirement that you have exactly $c$ items in the basket corresponds to the linear equality

$$v_1 + v_2 + \dots + v_n = c.$$

The requirement that min(avg(w), avg(x), avg(y)) > d is equivalent to the requirements that the sum of the $w$-fields is at least $c \times d$, and the sum of the $x$-fields is at least $c \times d$, and the sum of the $y$-fields is at least $c \times d$.  The former can be expressed as

$$w_1 \cdot v_1  + w_2 \cdot v_2 + \dots + w_n \cdot v_n > c \times d,$$

where $w_i$ is the value of the $w$-field for the $i$th possible item.  Note that $w_1,\dots,w_n,c,d$ are all constants (known from the problem statement), and $v_1,\dots,v_n$ are the variables, so this is a linear inequality.  Similarly for the sum of the $x$-fields and $y$-fields.

Finally, the goal of maximizing the average of the $z$-fields is equivalent to maximizing the sum of the $z$-fields of the selected items.  This corresponds to maximizing the following (linear) objective function:

$$z_1 \cdot v_1 + \dots + z_n \cdot v_n.$$

All of these are linear.  Finally, you can express the requirement that each $v_i$ must be either 0 or 1 by adding linear inequalities $0 \le v_i \le 1$ and requiring that $v_i$ be an integer.

The dynamic programming solution involves subproblems of the following form:

What's the maximum achievable value for the sum of $z$-fields, when restricted to choosing exactly $i$ of the first $j$ items, such that the sum of the $w$-fields is at least $\alpha$, the sum of the $x$-fields is at least $\beta$, and the sum of the $y$-fields is at least $\gamma$.

You get a subproblem for each combination of values for $i,j,\alpha,\beta,\gamma$.  That's a lot of subproblems, so the dynamic programming algorithm will probably be very slow.


Floyd's Cycle Detection Algorithm Proof In Laymen

The easiest way to understand this is really to draw it out and move your fingers on a graph, so I recommend literally pulling out a piece of paper to follow along.
Picture the part before the cycle as a line, and the cycle is a circle. So we have a straight line of arrows pointing into a circle of arrows. The length of the line is X steps, and the length of the circle is Y steps.
After X steps, the tortoise has gotten into the cycle, and the hare is further ahead, so it definitely is in the cycle too.
To understand why the tortoise and hare meet after they get into the cycle, think about the distance between the two in the circle. Assume the hare is BEHIND the tortoise--it's a circle, so while the hare is ahead, it's also fine to think of it as behind. It's at most Y steps behind in the circle, because the circle is only size Y.
At each step, the hare moves two steps, and the tortoise only moves one step, so the hare "catches up" one step. Eventually it will catch up to the tortoise. It catches up in the number of steps the hare started behind the tortoise, again at most Y steps.
So it does catch up, and it catches up in at most X + Y steps.


How many permutations for generating a specific binary search tree?

In a BST we can't say anything regarding the order of elements that are on separate sides of a node (e.g. 4 and 8, because they are on separate sides of node 6), however, we know that if a node is a parent of another node, it must have been inserted before it.

So 6 is always going to be the first element. Then either 4 or 7 can come (two choices). Then if we look at the remaining structure, 4/2 and 7/8 have exactly the same structure, so we can analyze just one.

Without loss of generality, assume we picked 4. Afterwards we can choose either 2 or 7 (two choices).

If we chose 2, no choice is left. However if we chose 7 either 2 or 8 can come next (two choices). Then we're left with no choice.

So the total number of permutations is $2(1 + 2) = 6$. The permutations are:

64278
64728
64782
67842
67428
67482


Determining recursive enumerability of given languages

If (1) means exactly two strings of different lengths, not r.e. (2) is r.e.: guess two strings, check their lengths are different, verify that $M$ accepts both.

Use the extension to Rice's theorem to prove (1) isn't r.e.


$\pi$-calculus can represent all sequential behaviour. The key rule responsible for sequential behaviour is that for input:

$$
  \overline{x}y \ |\ x(v).P \quad \rightarrow\quad P\{y/v\}
  $$

(and its replicated variant).
  The process $P$ becomes active only after the interaction at $x$
  has taken place. You can generalise this: if $X$ and $Y$ are two
  arbitrary processes such that $Y$ should execute only  after $X$
  has terminated, you can use something like:

$$
  (\nu a)(X' \ |\ a().Y)
  $$

Here $a$ is a  fresh name, i.e. does not occur in $X$ and $Y$.  The
  process $X'$ is exactly like $X$, except it outputs an empty message
  on $a$ upon termination of $X$.  Defining $X'$ depends on the precise nature of $X$ since
  $X$ may itself have multiple threads. If $X$ is sequential, then
  it's easy to define $X'$, just replace $0$ by
  $\overline{a}\langle\rangle$.
The whole purpose of the handshake on $a$ is to exchange one bit of information, namely that $X'$ has terminated.

The answer to your question "Does passing of common names over common channels shared between two Agents, represent a sequential execution?" is positive in a narrow sense that the continuation of the input side will only start after this interaction. However the sender might do other things in parallel. BTW, the rule you give isn't quite right. You need two $\tau$-actions because you are doing two interactions. Moreover, it looks like you are doing a bound output of $c$ abd $c''$, so the resulting processes should have an outermost $(\nu c'')(\nu c)$, or something like that.

You can also define subcalculi of $\pi$-calculus where all computation is sequential: for example by considering only processes that have at most one active output (heriditarily). An output is active, it it's not under an input.  This property being heriditary means simply that it's stable under reduction.

I close with a quote of R. Milner's from his "Elements of interaction":

  I make a disclaimer. I reject the idea that there can be a unique conceptual
  model, or one preferred formalism, for all aspects of something as large as concurrent computation, which is in a sense the whole of our subject -- containing sequential computation as a well-behaved special area.


Yes, $(0+10^*1)^∗$ denotes the  set of all binary strings with even number of ones. Or more technically $L(\ (0+10^*1)^∗ \ ) = \{ w \ |\ w$ is a binary string containing even number of 1's $\}$. We denote language of a regular expression $E$ as $L(E)$.

To understand regular expressions, you need to understand the recursive definition of regular expressions.

if $E$ and $F$ are regular expressions $E$+$F$ is regular expression.
if $E$ and $F$ are regular expressions $EF$ is regular expression.
if $E$ is regular expression $E^*$ is regular expression.
For basis, $\epsilon$ and symbols from alphabet $\Sigma$ are also regular expressions.

Next language of regular expressions for each of the above operations is defined: union, concatenation and repetition, respectively. For basis, it is sets of empty string or a single symbol, as the case may be.

Now if $w \in L(E)$ then $L(E^*)$ is not just $wwwww...$, it is also any $w_1w_2w_3...$ (0 or more times) such that $w_1 \in L(E)$,   $w_2 \in L(E)$, $w_3 \in L(E)$, etc.

So $(0+10^*1)^*$ is really $(0+10^*1)(0+10^*1)(0+10^*1)...$ (0 or more times). Thus, you work with the outer $*$ operator first and then work with the inner $*$ operator.

Next comes the question of simplification. Either you want to describe the language of a regular expression in most simplest manner possible, or you want to describe the most simple regular expression for a given language. Both these are hard to do. Even if you are given a minimum DFA of the language, to compute minimum regular expression for it is NP-complete (the decision version: does there exist a regular expression of less than $k$ length for the given DFA).

We can minimize DFA but unfortunately we do not have efficient algorithms to minimize NFA or regular expressions unless $P = PSPACE$. See Minimizing NFA’s and Regular Expressions
Gregor Gramlich and Georg Schnitger.

However $(0+10^*1)^*$ is set of all binary strings with even number of ones. Yet another expressions are $0^*(10^*10^*)^*$, $(0^*10^*1)^*0^*$, $(0^*10^*10^*)^*$ and so on. The outline of proof that the regular expression  $(0+10^*1)^*$ is indeed the language mentioned above is as follows:

First we draw a DFA for the language. If we eliminate the state $q_1$ we get the equivalent (enhanced) DFA in the right. It is easy to see that the equivalent regular expression is same. This is kind of reverse-engineering.

Sometimes it is easy to go this way, rather than finding the language of regular expression by automated procedures. Sometimes we can use regular expression algebra also to analyze and simplify regular expressions.


Balanced Weight Distribution in Bins/Buckets

It seems that this is exactly the $k$-partition problem, which is NP-hard even in the $k=3$ case.

There are decent approximation algorithms, though:

Greedy provides a $\tfrac{4}{3} - \tfrac{1}{3k}$-approximation (a PTAS).
FPTAS exist.


How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$

Here is the idea. When $n$ is even,
$$ \frac{T(n)}{n} \approx \frac{1}{2} \frac{T(n/2)}{n/2}. $$
In contrast, when $n$ is odd,
$$ \frac{T(n)}{n} \approx \frac{T(\lfloor n/2 \rfloor)}{\lfloor n/2 \rfloor}, $$
due to the factor 2 in the recurrence.
This suggests that in order to find your set $X$, you want to hit the "odd" case all the way. If $m = \frac{n-1}{2}$ then $n = 2m+1$, so if $m$ is a good choice, so is $n$. This suggests considering the sequence defined by $n_0 = 1$ and $n_{t+1} = 2n_t+1$, which is $1,3,7,15,\ldots$. As you can see, $n_t = 2^{t+1}-1$. The value of $T$ on this sequence is $1,2,4,8,\ldots$, that is, $T(n_t) = 2^t$.
We can now prove by induction that $T(2^{t+1}-1) = 2^t$. When $t = 0$, this just states the base case $T(1) = 1$. When $t > 0$,
$$
T(2^{t+1}-1) = 2T\left(\frac{2^{t+1}-2}{2}\right) = 2T(2^t-1) = 2\cdot 2^{t-1} = 2^t.
$$
Finally, note that
$$
T(2^{t+1}-1) = 2^t \geq \frac{1}{2} (2^{t+1}-1),
$$
and so you can take $X = \{ 2^{t+1}-1 : t \in \mathbb N \}$ as your infinite set.


Pros and Cons of Average Memory Access Time When Increasing Cache Block Size

An increased block size is indeed good for spacial locality.

On the other hand, a large block size increases the possibility of fragmentation and false sharing (in multiprocessor system).

Another way of thinking about this problem is if your cache size is fixed (based on cost, etc.), and you are changing the block size. In this case, as you increase your cache block size, accessing adjacent memory locations will have more hits (spacial locality), but there is a disadvantage considering temporal locality. Consider the extreme case, in which the cache has one block. Of course, this would be good for spacial locality, but it is terrible for a program repeatedly accessing two memory locations that are at least one full block size away from each other. The cache will miss every time.

EDIT

Consider this: you have a process with data in consecutive memory locations "A" through "H" of size "1." You have a warm cache of size "4" (ignoring compulsory misses, the misses/repeat below are average case) and an LRU cache replacement policy.

Let the cache block size be 4 (the "largest" block size case).

For repeated, in-order memory accesses A-H, this cache has 2
misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F,
C, D, G, H, this cache has 4 misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F, this cache has 2 misses/repeat.
For repeated, random memory accesses A, E, B, F, this cache has 4 misses/repeat.

Let the cache block size be 1 (the "smallest" block size case).

For repeated, in-order memory accesses A-H, this cache has 8 misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F, C, D, G, H, this cache has 8 misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F, this cache has 0 misses/repeat.
For repeated, random memory accesses A, E, B, F, this cache has 0 misses/repeat.

Let the cache block size be 2 (the "optimal" block size case).

For repeated, in-order memory accesses A-H, this cache has 4
misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F,
C, D, G, H, this cache has 4 misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F, this cache has 0 misses/repeat.
For repeated, random memory accesses A, E, B, F, this cache has 2 misses/repeat.

The "largest" block size case is best for repeated, in-order memory accesses (best for spacial locality) and worst for repeated, random memory accesses (worst for temporal locality).

The "smallest" block size case is worst for repeated, in-order memory accesses (worst for spacial locality) and best for repeated, random memory accesses (best for temporal locality). It is good for out-of-order memory accesses, depending on the size of the working set.

The "optimal" block size case is good for repeated, in-order memory accesses and good for repeated, random memory accesses, but it is not the "best" for either case.


Any regular expression satisfies $r^+ = rr^* = r^*r$. In fact, one often defines $r^+$ using one of these formulas, usually $r^+ := rr^*$.


Context-free grammar for language with unequal numbers of a and b

Here are some hints:

Break the language into two parts: $L_a = \{ w : \#_a(w) > \#_b(w) \}$ and $L_b = \{ w : \#_a(w) < \#_b(w) \}$. Below we concentrate on $L_a$.
Figure out a grammar for the language $L_= = \{ w : \#_a(w) = \#_b(w) \}$. Here the idea is that $L_= = (aL_=b + bL_=a)^*$.
Use the identity $L_a = L_=(aL_=)^+$ to construct a grammar for $L_a$.


Longest path in a cyclic, directed and weighted graph

Longest Path is NP-hard; the reduction from Hamiltonian Path is almost trivial.

That means that we do not know any algorithm with even polynomial running-time. You have to compromise.

Of course, the problem is easier for special classes of graphs, for instance both undirected and directed acyclic graphs.


"Semantic Web", "Semantic Network", "Semantic Search", "Knowledge graph"(not Google's Knowledge Graph) and "knowledge base"

Semantic Web is a set of technologies that want to make the data on the web readable and understood by machines. The domain that semantic web is the web. Therefore the URI is in the bottom of the technologies stack.

Semantic Network is a graph model to store the information. If you can model your data as a graph with node and edge, you can think it as a semantic network.

Knowledge graph is also a kind of graph model. However, it emphasis the store of all data on the level of both schema and individual. Therefore, it has no essential difference with Semantic network.
Knowledge base is an instantiated storage of a domain knowledge. You can think it as a database. It has not to be a graph model, if you can store the knowledge in some way, you can call it as knowledge base.


Dynamic algorithm: what's the difference between memorization and bottom-up algorithm?

The algorithms are indeed very similar, but there are several differences:

Order of evaluation: The bottom-up algorithm specifies a particular order of evaluation, which ensures that when OPT[i] is due to be computed, all the prerequisites have already been computed. In the memoization algorithm, this is taken care of automatically.
Evaluated entries: The bottom-up algorithm evaluates all entries of OPT, even though only OPT[n] is needed. The memoization algorithm only computes the entries that are necessary for computing OPT[n].

Two other differences, which are not encountered in this example:

Indexing: The bottom-up algorithm stores its entries in a simple array. The memoization algorithm, in more general instances, uses an association array (i.e., dictionary or hash table).
Memory term: The memoization algorithm remembers all entries which have been computed. A smart bottom-up algorithm could "forget" some of them.

Summarizing, the memoization algorithm is simpler to program. In terms of efficiency, the memoization algorithm has the advantage that only the necessary entries are calculated. In other instances, however, a lot can be saved by implementing a dedicated algorithm, in terms of indexing cost and, especially, memory usage.


Do any decision problems exist outside NP and NP-Hard?

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case.

If, however, $P \neq NP$, then there are languages which are neither in NP nor NP-hard.

For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this language is not computable, it is clearly outside of $NP$. As this language is sparse, $P \neq NP$ together with Mahaney's theorem implies that it is not NP-hard.

If we want a computable counterexample, we can take a language $L$ that is not in EXPSPACE. We number all finite words in increasing order as $(w_n)_{n \in \mathbb{N}}$, and now consider the language $L' = \{1^n \mid w_n \in L\}$. Again, Mahaney's theorem ensures that $L'$ is not NP-hard. If $L'$ were in NP (or even PSPACE), then an EXPSPACE algorithm for $L$ would be available in "Given w_n, compute 1^n and run the PSPACE-algorithm for $L'$ on it."

See here https://math.stackexchange.com/questions/235162/if-an-unary-language-exists-in-npc-then-p-np for a proof of Mahaney's theorem. Note that Yuval speaks about starting with an NP-complete unary language, that assumption is not used - the argument only needs an NP-hard unary language.


Find all edges of G contained in some MSP

We call an edge superheavy if it is the unique heaviest edge in some cycle. This post shows that an edge $e\in A$ if and only if $e$ is not superheavy.

To find all edges that are not superheavy, we can first sort the edges according to their weights from small to large. Then, we remove all edges, re-add them in this order, and track the connected components by a disjoint-set data structure.

Now we can check whether an edge $e$ is superheavy by checking whether it connects two vertices in different connected components in the graph with edges whose weights are less than $w(e)$: If $e$ is superheavy, then the two endpoints of $e$ are connected by a path on which the edges have weights less than $w(e)$, so the two endpoints must lie in the same connected components in the graph with edges whose weights are less than $w(e)$. On the other hand, if $e$ connects two vertices in the same connected components in the graph with edges whose weights are less than $w(e)$, then we can find a path connecting the two endpoints of $e$ on which the edges have weights less than $w(e)$, so $e$ along with this path forms a cycle and  $e$ has the largest weight in this cycle, so $e$ is superheavy.


strong reduction of $\lambda$-terms, useful?

There are several possible answers to your question:

1) Strong reduction is not implemented because it is not that useful: why take the trouble to reduce a term with un-instantiated variables when you'll have to go back in later to do the reduction when the variables get values anyway? And if the variables never get instantiated, then you've wasted your time entirely! More generally, it's easier to compute with concrete values than symbolic ones.

2) Strong reduction is implemented, because it is useful. It's just that this is usually done at compile time: inlining and constant propagation is just that, a way to do strong reduction.


What is the difference between oblivious and non-oblivious merging, sorting etc

Oblivious means that the control flow is independent of some properties of data. For example Bitonic Sort (also known as sorting net_ is oblivious, because it always compares the same elements disregarding data it gets, while Quick sort (or merge sort, or any adaptive sorting) are non-oblivious, because the algorithm steps change based on data. Bitonic sort does exactly the same steps in the best and the worst case, while non-oblivious algorithms may vary from $n$ steps to $n^2$ (for example).

This definition for cache is very similar, it means that it takes advantage of cache independently of its size (cache length).


Is it possible to shorten this Finite Automata Transition Graph?

Each string that is input to an automaton takes you to some state. So you can see each state an encoding some kind of information about the inputs the machine has seen if it's in that state. For example, an automaton might have a state that corresponds to "all words with an even number of $b$s."

Why am I telling you this? Because, when you're designing an automaton, it's often helpful to think about what information you need to store about the input to accept the language you want. In this case, you want to accept all words whose last letter has already appeared in the string. So, the information you need to decide the language is "What letters have I seen so far?"  If you encode that information in some states of the automaton, it should be easy to add the right transitions to accept the language you want.


If you take $S$ to be the sum of all the weights on all the edges in the graph and you add $S$ to all the weights in the graph, then a regular maximum weight matching will find you the matching you are looking for, since now with the large weights on all the edges, it will prefer a matching that uses the most number of edges first.
In your example of 1--2--3--4 with weights 1, 10, 1, here we have $S=12$, so add 12 to all the edges to have edge weights of 13, 22, 13 and now a regular max weight matching would prefer 13+13 over 22.
I'm not sure if it is easy to prove that $S$ is quite big enough, but it should be easy to prove that $mS$ is big enough to all to all edges (that is, sum of all edges times the number of edges).


Do $s$-$t$ cuts partition contingent vertices?

The example is correct: in this $s$-$t$ cut the capacity of the cut is indeed $3$. However, the min-cut in the max-flow min-cut theorem talks about the capacity of the minimum $s$-$t$ cut. So one must take an $s$-$t$ cut that gives minimum capacity: what you have in your example is not one of them.


Is TD-learning considered a model-based algorithm?

The previous answer is wrong. TD-learning is a model-free algorithm.

You compute $V_{\pi}(s)$ for a fixed policy $\pi$, then you update your policy based on $V$ a la policy iteration.

Source: https://webdocs.cs.ualberta.ca/~sutton/book/ebook/node60.html


My metric of choice would be the communication by direct message. However, this metric is hard to come by since measuring it requires the user's consent.

I do not think that using similar hashtags or terms has any say over friendship. People tend to adjust to the language they read and do not require personal bonding to do so.

I think mentions are a good way to identify friends and foes alike. A good way would probably be to see whether mentions beget a reply. Users tend to 'reward' pleasant and useful mentions with replies. However, the semantics of these messages are very important and only quantified analysis may not be enough.

Since I cannot comment yet, I would like to reply to the suggestion of using machine learning. I do not think that machine learning can effectively identify friends, even if one manages to get 'sufficient' data. Using Twitter is a rather creative process and generally not uniform across social circles.


Why do we use big O rather than $\Omega$ when discussing best case runtime?

The symbols $O$, $\Omega$ and $\Theta$ mean at most, at least and exactly, respectively. What these bounds are about, is an entirely separate issue. They can be about best-case or worst-case performance, but you can use these symbols throughout mathematics. To describe a function, one of the things you can do is to give $O$ and $\Omega$ upper and lower bounds, independent of whether your function is related to computer science.

For example, to describe an complicated algorithm (or language) for which you don't have precise bounds yet, but for which you do have rough preliminary bounds, you can say: the best-case of this algorithm runs in $\Omega(n^2)$ and $O(n^3)$ (meaning no better than $n^2$ but no worse than $n^3$) and the worst-case runs in $\Omega(2^{\sqrt{n}})$ and $O(2^{n^{2}})$. This means: I don't know what the worst-case running time is exactly, but my analysis thus far puts it between $2^{\sqrt{n}}$ and $2^{n^{2}}$. Later, it may turn out that the worst-case running time was in fact $\Theta(2^{n})$, and then your $O(2^{n^{2}})$ upper bound, while correct, was not strict.


A data model is set of general abstraction mechanisms: for instance you have the relational data model, with mechanisms as the relation, primary and foreign keys, etc. Or an object oriented data model with mechanisms like classes, aggregation, generalization, etc.
The schema instead is the description of a particular slice of reality for modeling purposes, for instance to build a database, expressed using a specific data model.


Is this computational complexity of the k-NN (custom distance) correct?

The running time of a nearest neighbor classifier is the time to compute the distance between two examples, multiplied by the number of pairs of examples you need to compute the distance between.  So, all you need to do is figure out each of those two numbers.

For ordinary k-nn, it takes $O(d)$ time to compute the distance between two $d$-dimensional examples, and to classify an example, you need to compare it to all other examples, i.e., $n$ pairs.  So, the running time to classify a single point with ordinary k-nn is $O(dn)$ (not $O(dn^2)$ as you wrote).

For your scheme, it appears it takes $O(dm^2)$ time to compute the distance between two examples (you need to run the DTW algorithm $d$ times, and running DTW once takes $O(m^2)$ time).  The number of pairs doesn't change; to classify a single example, you still compute the distance to each example in the training set, so $n$ distance computations.  Therefore, the running time to classify a single point in your scheme is $O(dm^2n)$ (not $O(dm^2n^2)$ as you wrote).


TM recognizing $0^n1^n$ requires Ω(log n) space

As you correctly point out by counting configurations, it holds that $SPACE[o(\log n)]\subseteq TIME[o(n)]$.

There is a theorem stating that $TIME[o(n\log n)]=REG$. See e.g. here.

If, by contradiction, we had $\{0^n1^n: n\in \mathbb{N}\}\in SPACE[o(\log n)]$, it would then follow that $\{0^n1^n: n\in \mathbb{N}\}\in REG$, which is clearly false.

Thus, $\{0^n1^n: n\in \mathbb{N}\}$ cannot be solved in $SPACE[o(\log n)]$.


What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class?

There is no "method". You need to use an ad hoc proof, that for each pair of words $a,b$ comes up with a word $w$ such that either $aw \in L$ and $bw \notin L$ or vice versa. We can assume that $|a| \geq |b|$.

If $b$ is not a prefix of $a$ then $aa^R \in L$ but $ba^R \notin L$, since otherwise $ba^R = (ba^R)^R = ab^R$, implying that $b$ is a prefix of $a$.

If $b$ is a prefix of $a$ then $|b| < |a|$, since otherwise $b = a$.
Let $\tau$ be a letter such that $b\tau$ is not a prefix of $a$ (i.e., if $a = bx$, where $x \neq \epsilon$, let $\tau$ be some letter different from the initial letter of $x$). Then $a\tau a^R \in L$ but $b\tau a^R \notin L$, since otherwise $b\tau a^R = (b\tau a^R)^R = a \tau b^R$, implying that $b\tau$ is a prefix of $a$.


Does JPEG compression use a heuristic model similar to MP3?

There are several lossy aspects of the JPEG algorithm. The main one is quantization of high-order Fourier coefficients, and a more minor one is downsampling the color components.

JPEG compression of a black and white image (we deal with color images later on) is composed of four main steps:

Divide the image into $8 \times 8$ blocks.
Perform a two-dimensional Fourier transform on each block (specifically, apply the discrete cosine transform).
Quantize each of the Fourier coefficients.
Encode the Fourier coefficients using Huffman coding.

In addition, the DC component (the average of each block) is encoded differentially (with reference to the previous block). The lossy aspect here is the quantization, specified by a quantization matrix. Higher order coefficients are quantized more heavily, and the coefficients were originally chosen experimentally (though in principle they can be optimized for each image, since they are stored in the JPEG file). The quality parameter mainly affects the quantization matrix.

Color images are encoded by first moving into the YCbCr color space (similar to television's YPbPr), in which Y is the saturation components, and Cb and Cr are the color components. The latter two components are downsampled by a factor of 2 in the horizontal dimension (this is the most common choice, though others are possible), since the human visual system is less sensitive to this kind of data. Each of the color components is then encoded as a black and white image, using two different quantization matrix, one for the Y component, the other for the Cb and Cr components. The latter matrix quantizes more heavily.


Replace 1's with -1's and vice versa in a matix

Your matrix encodes a directed graph in which the in-degree and out-degree of each vertex is 1. In other words, your graph is a collection of directed cycles.

If you swap rows $i$ and $j$ and columns $i$ and $j$, then you have swapped vertices $i$ and $j$ in the graph. This has the effect of switching the direction of the edge between $i$ and $j$, but also affects other edges touching $i$ and $j$.

In order to finish the solution, it suffices to consider a single directed cycle involving all vertices, say $1 \to 2 \to \cdots \to n \to 1$. We would like to swap vertices so that the the cycle becomes $1 \gets 2 \gets \cdots \gets n \gets 1$.

We now consider two cases:

$n = 2k+1$ is odd. In this case, we swap $(1,n), (2,n-1), \ldots, (k,k+2)$ to get
$$
n \to n-1 \to \cdots \to k+2 \to k+1 \to k \to \cdots \to 1 \to n.
$$
$n = 2k$ is even. In this case, we swap $(1,n), (2,n-1), \ldots,(k,k+1)$ to get
$$
n \to n-1 \to \cdots \to k+1 \to k \to \cdots \to 1 \to n.
$$


Let $l$ be the number of distinct characters in the input string. So our input size is summarized by $n, k, l$, with $k \le n$ and $l \le n$.

Here is one efficient way to do it. In the first step, since the order of characters in the string doesn't matter, let's turn it into a map:
$$
M = \{a \mapsto 1, d \mapsto 3, y \mapsto 1\}.
$$
The idea of our algorithm is to first calculate the number of possible permutations of $k$ elements from $M$, and then to use this to generate one randomly.

Step 1: calculating the number of possible permutations

We use dynamic programming. We actually calculate, more generally, the quantity
$$
p[i,j] \qquad \text{ for } 0 \le i \le k \text{ and } 0 \le j \le l,
$$
which represent the *number of permutations of length $i$, which use only the first $j$ elements of the map. For example, in the example problem (input "daddy", $k = 2$), we have
\begin{align*}
p[0, 0] &= p[0, 1] = p[0, 2] = p[0, 3] = 1 \quad \text{(empty string)} \\
p[1, 1] &= 1 \quad \text{(strings of length 1 using only a -- so just "a")} \\
p[1, 2] &= 2 \quad \text{(strings of length 1 using a and d -- so "a" and "d")} \\
p[1, 3] &= 3 \quad \text{("a", "d", and "y")} \\
p[2, 1] &= 0 \quad \text{(no strings of length two using only a since only one a is allowed)} \\
p[2, 2] &= 3 \quad \text{("ad", "da", and "dd")} \\
p[2, 3] &= 7 \quad \text{("ad", "da", "dd", "ay", "ya", "dy", "yd")}
\end{align*}

Now how do we calculate $p$? We can use a recursive algorithm. Let $M[j]$ denote the value of $M$ on the $j$th character (so in our example, $M[1] = 1, M[2] = 3, M[3] = 1$). Then
$$
p[i, j] = \sum_{i' = 0}^{M[j]} \binom{i}{i'} p[i - i', j-1].
$$

What this formula says is: pick $i'$ places to put character $j$. For example, in our running example for $p[2, 3]$, it says pick $i'$ places to put the character $y$ in a string of length $2$. Then for the remaining $i- i'$ places, we fill them in with a string only using the first $j-1$ characters (which can be done in $p[i-i', j-1]$ ways). The variable $i'$ ranges from $0$ to $M[j]$ because we can only use character $j$ at most $M[j]$ times.

This recurrence allows us to calculate the entire table of $p[i,j]$ in approximately $O(nk)$ time.

Step 2: Picking a permutation at random

The total number of permutations is $p[k, l]$. So pick a random number $r$ from $1$ to $p[k, l]$.

Now recall the recurrence relation
$$
p[i, j] = \sum_{i' = 0}^{M[j]} \binom{i}{i'} p[i - i', j-1].
$$

Very roughly, we can use this recurrence relation to enumerate the $r$th permutation.
To evaluate the $r$th permutation of $p[i,j]$ total, evaluate the above sum and locate the term where the $r$th permutation would fall. For example if $r = 4$ and there are $7$ total permutations, and the sum gives you $3 + 4$, then $4$ falls fourth out of $7$, so it falls in the second group. Then, we are looking for the first out of $4$ permutations in the second group, which we can recursively find by picking a random permutation from $p[i - i', j-1]$.


What's the difference between studying "Software Development", "Software Engineering", "Computer Science" and "Information Technology"?

As D.W. wrote this is somewhat subjective since there is no standard definitions for those fields of study.
Regarding your last question, my experience in a couple of European universities is that "Computer Science" is a more theoretical program, often branched from a math faculty while "Software Engineering" is more practical, often part of the Engineering faculty.


We start in store(1,laurence) and since 1 is empty, we simply put laurence in 1.

We then go in store(1,ron) and see that 1 is not empty so we compare ron to the value of 1: laurence, and since laurence$\not>$ron, we then go to store(1.upper,ron). So since 1.upper$=$3, we are now in store(3,ron). Since 3 is empty, we simply put ron in 3.

Now, since we always check that the spot is empty before settings its data, the data of 3 will never change. So at the end, it's still ron.

The tree is just here to tell you that 1.upper$=$3.

But you can "run" the algorithm on this visual representation of the tree: Start at the leftmost node. If there's nothing written, write whatever you want to write, otherwise, depending on how what you want to write compares to what is written, either go up or down.

By the way, having "upper" pointing down and "lower" poiting up is really confusing...


Why does it take so long to prove optimality when warm-starting from optimal solution

An IP-solver can use relaxations of variants of the integer program (that is, the linear program where the integrality constraints are dropped) among other steps to compute the final solution.

For these individual relaxations, the solver can indeed efficiently verify that it has an optimal basis. However, solving a relaxation is only a subproblem of solving the original IP. Therefore, even if you give an optimal solution to the original IP, this does not (necessarily) directly correspond to a basis in a relaxed LP, and the solver has to inspect other solutions than checking a basis.

There is one case in which providing an IP solution does allow for a fast check of optimality: when the relaxation of the IP is guaranteed to have the same solution as the original IP. (This is the case when the matrix describing the IP is totally unimodular or equivalently when the solution space is an integral polyhedron)

However, it is unlikely that the solver will be able to detect when this is the case. So, you will have to do that by some other means, and if the relaxed solution indeed solves the IP, you can let the solver solve the relaxed instance, and then the LP solver can quickly verify if your solution is optimal.


compute a gradient with "minimal" colorstops from a ordered set of RGB colors

What you want to do is fit a piecewise linear function to your data.

No noise

If the data is perfect and has no noise, this is easy:

Form a line from the first points.  Remember those two points as the endpoints of the line.
If the third point lies on this line, discard the right endpoint and replace it with the third point.  Otherwise, start a new line from the second point and third point.
Repeat.

That can be done with a simple linear scan.

Noisy data

If the data is imperfect and noisy, you want to do a best fit of a piecewise linear function to your data.

There's no universal answer, as there are multiple ways to fit a piecewise linear function.  If you have $n$ points, you can always get a perfect fit by drawing $n-1$ lines (one line between each consecutive pair of points), but the resulting function might be very wiggly and not what you are looking for.  In practice, we probably have the idea that a solution with few pieces (few lines) is probably more likely than one with more pieces, all being equal.  On the other hand, with too few pieces, you might get a very poor fit.

Thus, you need a parameter to balance the number of pieces against the amount of error in your fit, and then you can try to find an optimal solution.  So, the first step will be to define a loss function that quantifies how good/bad each candidate solution is.  Once you have that, there are various algorithms for finding the best fit.  One approach is to use dynamic programming.  See https://en.wikipedia.org/wiki/Segmented_regression, https://dsp.stackexchange.com/q/1227/5874, https://stackoverflow.com/q/22028529/781723, and probably many other sources.

My guess is that if there is any noise/error in  your data, it will be very small, so any reasonable procedure will work well.


Why does $2^{O(\log n)} = n^{O(1)}$ hold?

This is simple math. An expression of the type $O(\log n)$ is at most $C\log n$ for some $C > 0$ and large enough $n$. So for large enough $n$, the entire expression $2^{O(\log n)}$ is at most
$$
2^{C\log n} = n^C = n^{O(1)}.
$$
The first equation follows from the definition of the logarithm $2^{\log n} = n$, which in this case I conveniently assumed is taken to the base 2 (though it makes no difference in this case – can you see why?).


How can I solve the recurrence $f(n) = 3f(\frac{n}{4}) + \log(n)$?

The given recurrence is: $T(n) = 3T(n/4) + \log n$

Using the substitution method, we get:

\begin{align}
T(n) &= 3^2T \left(n/4^2\right) + \log n + 3\log (n/4) \\
     &= 3^3T \left(n/4^3\right) + \log n + 3\log(n/4) + 9 \log(n/4^2)\\
\end{align}
and so on.

Can you see a pattern now?


A pretrained model for mathematical equations characters detection

Detexify is a service that recognizes LaTeX symbols from handwritten figures. Their training dataset is freely available on Github.


SAT for positive CNF clauses with exactly half of the variables being true

Your problem is NP-complete by the modern presentation of Schaefer's dichotomy theorem.

You can also prove its NP-completeness by direct reduction of SAT to your problem.  If a CNF formula has $n$ variables $x_1 \dots x_n$ introduce $n$ new variables $y_1 \dots y_n$ and add 2-CNF clauses that force each $y$ variable to have the opposite value of the corresponding $x$ value.
I.e.
$$(x_1 \lor y_1)$$
$$(\lnot x_1 \lor \lnot y_1)$$
$$(x_2 \lor y_2)$$
$$(\lnot x_2 \lor \lnot y_2)$$
$$\dots$$
$$(x_n \lor y_n)$$
$$(\lnot x_n \lor \lnot y_n)$$

All solutions to the resulting formula will have half the variables with true values and half false.

For unaltered formulas, you don't need a special algorithm to find half-true half-false solutions.  Take any CNF formula with an even number of variables and then add CNF clauses encoding a chain of adder circuits that sums the values of all the variables.  Next, add a comparison circuit that is only satisfied if the sum is one-half the total number of variables.  Run a normal SAT solver on the result and it will output only solutions where one-half the original variables have a true value.  This is a somewhat naive solution but it gets the job done.

Search the literature a bit more and you will discover SAT solvers that accept pseudo-Boolean constraints in addition to CNF.  With these you can write out the $x_1 + x_2 + x_3 + \dots + x_n = n / 2$ equation explicitly and the solver will either churn out the adder circuits for you or just handle the equation internally.

Your special SAT problem is also readily transformed into a 0-1 integer programming problem for which there are solvers available.


Unambiguous context-free grammar for strings with at least as many a's as b's

Here is an unambiguous grammar for strings with at least as many $a$'s as $b$'s.  $\def\L#1{{\mathcal L(#1)}}$

$$\begin{align}
S&\to EM\mid E\\
M&\to aDM\mid aD\\
E&\to aBE\mid bAE\mid\epsilon\\
D&\to aBD\mid\epsilon\\
B&\to b\mid aBB\\
A&\to a\mid bAA\\
\end{align}$$

The following table should help us understand the strings generated by each non-terminal.

$$  \text{number of $a$'s minus number of $b$'s} $$

\begin{array}{|c|c|}
\hline
&\text{in the whole string} & \text{in every proper prefix}\\\hline
A&1& \lt 1\\\hline
B&-1&\gt -1\\\hline
D&0&\ge0\\\hline
E&0&\text{no restriction}\\\hline
M&\gt0&\gt0\\\hline
S&\ge0&\text{no restriciton}\\\hline
\end{array}

Some notations. For all string $w$, let $d(w)=|w|_a-|w|_b$, i.e., the number of $a$'s minus the number of $b$'s. Define $d_w:\{1,\cdots, |w|-1\}\to \mathbb N$, $w(i)=d(p_i(w))$, where $p_i(w)$ is the proper prefix of $w$ of length $i$. For example, for $w=abb$, $$\begin{align}d_w(1)&=d(a)=1 - 0=1,\\ d_w(2)&=d(ab)=1-1=0.\end{align}$$

Given a string $w$ and one of its prefixes $p$, let $w-p$ denote $w$ with $p$ removed, i.e. $w = p(w-p)$.

Continuity Lemma. $d(\cdot)$ is continuous in the sense that $d(w)$ changes at most by 1 if $w$ is extended or shrunk by one terminal. $d_w(\cdot)$ is continuous in the sense that $d_w(i)$ changes at most by 1 if $i$ becomes one less or bigger. So we have "intermediate value theorem" for $d(\cdot)$ and $d_w(\cdot)$.

Linearity Lemma. Given two strings $p$ and $w$, we have
$$\begin{align}|w-p|&=|w|-|p|,\\
d_{w-p}(i) &= d_{w}(|p| +i) - d(|p|),\color{#d0d0d0}{\text{ for } i=1,2,\cdots, |w|-1}
\end{align}$$
Proof. By definition. $\blacksquare$

Proposition AB. We have two equivalences,
$$\begin{align}
w\in \L A &\iff d(w) =1\text{ and } d_w \lt 1,\\
w\in \L B &\iff d(w) =-1\text{ and } d_w \gt -1.
\end{align}$$
Proof: By induction on $|w|$, it is straightforward to establish the "$\Rightarrow$" implications.

Let us prove the "$\Leftarrow"$ implications by induction on $|w|$ as well. The base cases when $|w|=1$ are immediate to verify. Suppose $w$ is of greater length.

$d(w) =1\text{ and } d_w \lt 1$. Since $d_w(1)\lt 1$, $w$ starts with $b$, i.e, the first value of $d_w$ is $d(b)=-1$. Since $d(w)=1$, $d(p)=0$ for some proper prefix $p$ of $w$. Let $b\mu$ be the shortest such prefix. Since $d_\mu < 1$, $d(\mu)=d(b\mu)-d(b)=1$, and $\mu$ is shorter than $w$, we have $\mu\in \L A$ by induction hypothesis.

Since $d_w\lt 1$ and $d(a\mu)=0$, $d_{w-b\mu} \lt 1$. Also note $d(w-b\mu)=1-0=1$. Since $w-b\mu$ is shorter than $w$, $w-b\mu\in\L A$ by induction hypothesis. So $w=b\mu(w-b\mu)$ can be generated from $A\to bAA$.
$d(w) = -1\text{ and } d_w \gt -1$. This case is the same as the case above, but with $-1$ and $1$ switched, $>$ and $<$ switched, $a$ and $b$ switched, $A$ and $B$ switched. We obtain that $w$ can be generated from $B\to aBB$. $\blacksquare$

Proposition DE. We have two equivalences,
$$\begin{align}
w\in \L D &\iff d(w)=0\text{ and } d_w \gt 0,\\
w\in \L E &\iff d(w)=0.
\end{align}$$

Proof: By induction on $|w|$, it is straightforward to establish the "$\Rightarrow$" implications.

Let us prove the "$\Leftarrow"$ implications by induction on $|w|$ as well. The base cases when $|w|=0$ are immediate to verify. Suppose $w$ is of greater length.

$d(w)=0$ and $d_w>0$. Since $d_w(1)>0$, $w$ starts with $a$. Let $a\mu$ be the shortest non-empty prefix with $d(a\mu)=0$. Then $d(\mu)=-1$ and $d_{\mu}\gt0$, which means $\mu\in\mathcal L(aB)$. Since $d(a\mu)=0$, have $d_{w-a\mu}\gt0$. Since $d(w-a\mu)=d(w)-d(a\mu)=0$ and $w-a\mu$ is shorter than $w$, $w-a\mu\in\L D$ by induction hypothesis. The rule $E\to aBE$ tells that $w=a\mu(w-a\mu)\in D$.
$d(w)=0$.

$w$ starts with $a$. Let $a\mu$ be the shortest prefix of $w$ such that $d(a\mu)=0$. Then $d(\mu)=-1$ and $d_\mu > -1$, which means $\mu\in \L B$. Since $d(w-a\mu)=d(w)-d(a\mu)=0$ and $w-a\mu$ is shorter than $w$, $w-a\mu\in\mathcal L(E)$ by induction hypothesis. The rule $E\to aBE$ tells that $w=a\mu(w-a\mu)\in E$.
$w$ starts with $b$. This case is the same as the case above, but with $-1$ and $1$ switched, $>$ and $<$ switched, $a$ and $b$ switched, $A$ and $B$ switched. We obtain that $w\in E$. $\blacksquare$

Proposition M. $w\in \L M \iff d_w \ge 1$.
Proof. The "$\Rightarrow$" direction is implied by the proposition above immediately since $M$ becomes multiple $aD$'s.
To prove the "$\Leftarrow$" direction, suppose $d_w\ge1$. Note that $w$ starts with $a$. Let $p$ be the longest prefix of $w$ such that $d(p)=1$, which implies $d_{w-p}\ge1$. Since we also have $d_p\ge1$, $p\in\L U$. If $p=w$, $w$ can be generated from $M\to U$. Otherwise, since $w-p$ has the same restriction as $w$, $w$ can be generated from $M\to UM$. $\blacksquare$.

Proposition S. $w\in \L S \iff d(w) \ge 0.$
Proof. The "$\Rightarrow$" direction is implied by proposition E and proposition M immediately.
 To prove the "$\Leftarrow$" direction, consider a string $w$ with $d(w)\ge0$. If $d(w)=0$, then $\mu\in\L E$. Otherwise, $d(w)>0$. Let $p$ be the longest prefix of $w$ such that $d(p)=0$. Then $p\in\mathcal L(E)$. Consider $w-p$. We must have $d_{w-p}\ge 1$; otherwise, we can extend $p$. So $w-p\in \mathcal L(M)$. $w=p(w-p)$ can be generated by $S\to EM$. $\blacksquare$

Proposition unambiguity. The grammar is unambiguous.
Proof. Given the propositions above that characterize each language involved numerically, it is relative easy to prove as the following.

Let $s\in\L S$.

$d(s)=0$. Then $s$ has to be parsed by $S\to E$.
$d(s)\gt 0$. Then $s$ has to be parsed by $S\to EM$. Suppose $s=e_1m_1=e_2m_2$, where $e_1,e_2\in\L E$ and $m_1, m_2\in\L M$. Since $d_{m_1}>0$, if $m_2$ is a proper suffix of $m_1$, i.e., $m_1-m_2$ is a proper prefix of $m_1$, we would have $d(m_1-m_2)>0$, which contradicts with $d(m_1-m_2)=d(m_1)-d(m_2)=(d(s)-d(e_1))-(d(s)-d(e_2))=0$. This contradiction means $m_1$ cannot be a proper suffix of $m_1$. By symmetry, $m_2$ cannot be a proper suffix of $m_1$, either. Hence, $m_1=m_2$ and $e_1=e_2$.

Let $m\in\L M$.

$\min d_m=1$. Then $m$ has to be parsed by $M\to aD$.
$\min d_m>1$. Then $m$ has to be parsed by $M\to aDM$. Suppose $m=ad_1m_1=ad_2m_2$, where $d_1,d_2\in\L D$ and $m_1, m_2\in\L M$. Since $d_{m_1}>0$, if $m_2$ is a proper suffix of $m_1$, i.e., $m_1-m_2$ is a proper prefix of $m_1$, we would have $d(m_1-m_2)>0$, which contradicts with $d(m_1-m_2)=d(m_1)-d(m_2)=(d(s)-d(ad_1))-(d(s)-d(ad_2))=0$. This contradiction means $m_1$ cannot be a proper suffix of $m_1$. By symmetry, $m_2$ cannot be a proper suffix of $m_1$, either. Hence, $d_1=d_2$ and $m_1=m_2$.

Let $e\in\L E$.

$|e|=0$. Then $e$ has to be parsed by $E\to \epsilon$.
$|e|>0$.

$e$ starts with $a$. Then $e$ has to be parsed by $E\to aBE$. Suppose $e=ab_1e_1=ab_2e_2$, where $b_1,b_2\in\L B$ and $e_1, e_2\in\L E$. Since $d_{b_1}>-1$ and $d(b_2)=-1$, $b_2$ cannot be a proper prefix of $b_1$. By symmetry, $b_1$ cannot be a proper prefix of $b_2$, either. Hence, $b_1=b_2$ and $e_1=e_2$.
$e$ starts with $b$. This case is symmetric to the case above.

Let $w\in\L D$.

$|w|=0$. Then $w$ has to be parsed by $D\to \epsilon$.
$|w|>0$. Then $w$ has to be parsed by $D\to aBD$. Suppose $w=ab_1q_1=ab_2q_2$, where $b_1,b_2\in\L B$ and $d_1, d_2\in\L D$. Since $d_{b_1}>-1$ and $d(b_2)=-1$, $b_2$ cannot be a proper prefix of $b_1$. By symmetry, $b_1$ cannot be a proper prefix of $b_2$, either. Hence, $b_1=b_2$ and $d_1=d_2$.

Let $w\in\L B$.

$|w|=1$. Then $w$ has to be parsed by $B\to b$.
$|w|>1$. Then $w$ has to be parsed by $B\to aBB$. Suppose $w=ab_1b_3=ab_2b_4$, where $b_1,b_2,b_3,b_4\in\L B$. Since $d_{b_1}>-1$ and $d(b_2)=-1$, $b_2$ cannot be a proper prefix of $b_1$. By symmetry, $b_1$ cannot be a proper prefix of $b_2$, either. Hence, $b_1=b_2$ and $b_3=b_4$.

Let $w\in\L A$. This case is symmetric to the case above. $\blacksquare$

Here is a simpler unambiguous grammar given by Yuval.
$$\begin{align}
S&\to SaU \mid X\\
X&\to aUbX\mid bDaX\mid\epsilon\\
D&\to bDaD\mid\epsilon\\
U&\to aUbU\mid\epsilon\\
\end{align}$$

Here is the numerical characterization for the language generated by each terminal. Check his answer for visual explanations.
$$  \text{number of $a$'s minus number of $b$'s} $$
\begin{array}{|c|c|}
\hline
&\text{in the whole string} & \text{in every proper prefix}\\\hline
S&\ge0&\text{no restriciton}\\\hline
X&0&\text{no restriciton}\\\hline
U&0&\ge0\\\hline
D&0&\le0\\\hline
\end{array}


lexicographic depth-first search complexity class

The formal name for a problem where you want to actually produce the solution as the output (not just say yes or no to whether one exists) is a Function Problem if every input has an associated output, or a Search Problem if some inputs might not have any solution (of course a function problem is just a special case of a search problem).

In this case, every graph has a lexicographic depth first ordering, so for any graph there is some output that can be produced, and you have a function problem. The class of function problems that can be computed in deterministic polynomial time is (cunningly) called FP.

Going out on a limb (with regards to my knowledge, someone else might be able to confirm this), I suspect that the obvious relationship1 between P and FP holds for complete problems too, so your problem should also be FP-complete.

Note that this relationship normally relies on Turing reductions, but seeing as P=co-P there shouldn't be too much of a problem here.


Is it possible to create a chatbot that doesn't fall into an infinite loop under some restrictions?

If the computer can retain state between inputs (e.g., you're using an interactive Turing machine), then yes, you can avoid an infinite loop.

For instance, the machine can just have a counter that counts 1,2,3,4,5,...; it can then map the counter to a sentence.  When the counter is $i$, it can look up the $i$th bit of the binary expansion of pi; if this bit is even, it outputs "Not so good, and you?" and if it is odd, it outputs "Good, and you?".  Since the bits of pi never repeat, this will never repeat either.  There are other ways to do it as well; this is just one example.

To respond to the original version of the question: If invoke the Turing machine separately on each input string, then it will have no way to retain state across sentences.  In that case, no,  It's not possible.  By the pigeonhole principle, there will exist a loop.  The set of possible sentences is finite, so this will eventually enter a loop.

If you take any function $f:S \to S$ where $S$ is a finite set, and you pick a single starting point $x \in S$ and then compute the sequence $x,f(x),f(f(x)),\dots$, eventually some value must appear twice.  In particular, once you've looked at $n+1$ different values, each of which is selected from a set of size $n$, by the pigeonhole principle, there must be some value that appeared at least twice.  In other words, $f^i(x)=f^{i+r}(x)$ for some $i,r$.  This means that $f$ has entered a cycle: $f^{j+r}(x)=f^j(x)$ for all $j\ge i$.

Here $S$ represents the set of all sentences (there are finitely many of them), and $f$ represents the function computed by your chatbox (which accepts a single sentence on its input, and outputs a single sentence, and is deterministic).

Of course, with an appropriately constructed algorithm, it may take longer than the lifetime of the universe to enter a loop.  Nonetheless, mathematically, it will eventually loop.

Your specific example doesn't work: it can't be implemented by a deterministic function.  If on input "Good, and you?" it outputs "Not so good, and you?", then that's what it will always output on that input.  Thus, you can't have a Turing machine that on input "Good, and you?" will sometimes output "Not so good, and you?" and sometimes output "Good, and you?".  Code running on a Turing machine is deterministic and memoryless.


Is an irregular language concatenated with a language with which it has no common symbols irregular?

First, your $L1L2$ is wrong. $$L1L2 = \{a^ib^ic^j\ | \ i>0, j>0\}$$
Your conclusion is right, $L1L2$ is irregular(as long as $L2\neq\phi$, otherwise  $L1L2=\phi$ is clearly regular). This can be proved using Myhill–Nerode theorem.

Suppose $X$,$Y$ are any 2 different equivalence classes of $R_{L1}$, $x\in X, y\in Y$, then there exists string $z$ such that $xz \in L1$ while $yz \notin L1$.

If $L2=\{\epsilon\}$, then $L1L2$=$L1$ is irregular. Otherwise, take any string $w\in L2, w \neq \epsilon$, then $xzw \in L1L2$, but $yzw\notin L1L2$
(consider that, due to no common symbol, no suffix of $yzw$ longer  than $|w|$ in L2, and no prefix of $yzw$ shorter than $|yz|$ in $L1$).

This shows that $x$,$y$ belongs to different equivalence classes of $R_{L1L2}$, too. ie. there must be at least the same number of equivalence classes in $R_{L1L2}$ as in $R_{L1}$

From Myhill–Nerode theorem, $L1$ has infinite number of equivalence classes. Thus $L1L2$ also has infinite number of equivalence classes, which means $L1L2$ is irregular also.


Is modulus capable of universal computation?

You have to distinguish between two meanings of computation:

Computation of functions on a finite domain (e.g. circuits).
Computation of functions on an infinite domain (e.g. Turing machines).

A single division operation cannot be universal in terms of the second meaning, since division is total: it always halts (even division by zero halts). However, it could possibly be universal in terms of the first meaning. For example, if we encode the input using different primes, then the Chinese Remainder Theorem shows that $x \mapsto n \pmod{x}$ is universal, that is, for every Boolean function $f$ on some set $S$ of finite primes there is a number $n$ such that for every $x \in S$, $n \mod{x} = f(x)$.


ML Algorithm for getting top pick in each sample

You will have to restructure your data in such a way that one input contains data pertaining to only one street (but of all the houses.) This involves grouping the data by street_id.
You should then use several inputs in such a way to train your model to find out the popular house. Since it will be a supervised-learning task, you'll have to label your data accordingly.
But there's a problem here. Each street has different number of houses. One way to handle this problem is by fixing an upper bound on the number of houses per street and padding your data up to this upper bound.


Are there NP problems, not in P and not NP Complete?

Are there any known problems in NP (and not in P) that aren't NP Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

No, this is unknown (with the exception of the trivial languages $\emptyset$ and $\Sigma^*$, these two are not complete because of the definition of many-one reductions, typically these two are ignored when considering many-one reductions). Existence of an $\mathsf{NP}$ problem which is not complete for $\mathsf{NP}$ w.r.t. many-one polynomial time reductions would imply that $\mathsf{P}\neq\mathsf{NP}$ which is not known (although widely believed). If the two classes are different then we know that there are problems in $\mathsf{NP}$ which are not complete for it, take any problem in $\mathsf{P}$.

  If there is a problem that is NP (and not P) but not NP Complete, would this be a result of no existing isomorphism between instances of that problem and the NP Complete set?

If the two complexity classes are different then by Ladner's theorem there are problems which are $\mathsf{NP}$-intermediate, i.e. they are between $\mathsf{P}$ and $\mathsf{NP\text{-}complete}$.

  If this case, how would we know that the NP problem isn't 'harder' than what we currently identify as the NP Complete set?

They are still polynomial time reducible to $\mathsf{NP\text{-}complete}$ problems so they cannot be harder than $\mathsf{NP\text{-}complete}$ problems.


Actually you should be thinking about a geometric random variable, not a binomial RV, since you're interested in the number of times that you have to sample before you hit a prime. And each sampling event is actually a Bernoulli trial (with probability of choosing a prime $p = \Theta(1/\log {2^n}$), where $n$ is the number of bits).

And for showing that the expected value is $O(n)$, you don't need to show that it's less than $n$. You actually need to show that there are some constants $k$ and $N$ such that the expected value is less than $kn$ for all $n \ge N$.

But besides that, you're on the right track.


Matrix element value counting in O(1) space

Checking whether the number of nonzero elements on each row is at most $2$ can be done in $O(1)$ space on a row-by-row basis by simply counting those elements.

Therefore the only interesting part is checking the condition over the columns.
This can be done in $O(M)$ space by keeping a counter for each column. In details, the counter $c_i \in \{0,1,2\}$ associated with the $i$-th column will be the number of rows seen so far that contain a nonzero element in column $i$. As soon as a row with a nonzero element in column $i$ is seen and $c_i$ was already $2$, you can immediately return "false". If the whole matrix is processed without this happening you can return "true".

Unfortunately, your problem cannot be solved using $x= o(M)$ bits.
Suppose this were the case and consider some matrices with $M$ of columns and $N=2M+1$ rows, of the form described in the following.

The $i$-th of the first $M$ rows will have zeros in all columns $j \neq i$, while $i$-th column will either contain a $0$ or a $1$.

The number of distinct choices for the first $M$ rows is $2^M$, yet there are at most $2^x < 2^M$ (for sufficiently large $M$) different possible states of the $x$ bits of memory. This means that there are (at least) two distinct choices $R$ and $R'$ of the first $M$ rows that leave the algorithm in the same internal state.

In other words, for any choice of the $(M+1)$-th to $(2M+1)$-th rows, the algorithm must behave in the same way, regardless of whether the set of the first $M$ rows was $R$ or $R'$.

Since $R$ and $R'$ are distinct, there must be (at least) one index $i$ such that
the element $r_i$ in the $i$-th column of the $i$-th row of $R$ is different from the element $r'_i$ in the $i$-th column of the $i$-th row of $R'$. Without loss of generality assume that $r_i = 0$ and $r'_i=1$.

For $i=1,\dots,M$, let the $(M+i)$-th row be the row containing a single $1$ in the $i$-th column. Finally, choose the $(2M+1)$-th row to have exactly one $1$ in the $i$-th column.

This leads to a contradiction: On one hand, if the set of the first $M$ rows is $R$, the algorithm must return "true" since there is at most one nonzero element per row and at most two nonzero elements per column; on the other hand, if the set of the first $M$ rows is $R'$, the algorithm must return "false" since column $i$ has $3$ nonzero elements (in the $i$-th, $(M+i)$-th, and $(2M+1)$-th rows).


O(1) access into an array-like data structure with numerical ranges for keys

Perhaps what you're looking for is a Direct-adress Table

You can set up the keys as the ranges you've provided. Since the set of keys is quite small (4 intervals), a Direct-adress Table is a simple solution to your problem. It has the advantage of retrieving data in O(1)

The keys would hold a pointer to the data you want to retrieve.

For example, you can set a variable key1 as the interval [0..0.3).
We generate a random number x, and get 0.1.
Since 0.1 meets the conditions of the first key ( x >= 0 and x < 0.3), we can retrieve the data stored in key1 in O(1) time.

If you want more information about a Direct-adress Table or O(1) operations on dictionaries, I recommend Introduction to Algorithms, 3rd Edition, Chapter 11


No, you cannot simplify to $(A<B)_i = B_i + (A<B)_{i-1}$, Take for example $A=11$ and $B = 10$.

Then $(A<B)_2$ = False, $B_2$ = True, and $(A<B)_1$ = False. If you substitute the values above then the equation is not satisfied. The original equation(s) is correct.

$(A<B)_i = \neg A_i B_i + (\neg A_i+B_i)(A<B)_{i-1}$
$(A<B)_1 = \neg A_1 B_1$

In your derivation of simpler formula, $B_i + (A<B)_{i-1} = Q$ but you are incorrectly substituting $B_i (A<B)_{i-1} = Q$ in rightmost term.


In context of data mining, what does it mean for an association rule measure to be maximal?

I believe that in the context of that paper (PS), you can read "maximal" as "maximized". That is to say, the conviction function $P(A)P(\neg B)/P(A, \neg B)$ attains its greatest value when $A \implies B$.


Name for the "starting vertex" and "ending vertex" of a directed edge

$a$ is the tail or initial vertex of the edge $(a,b)$
$b$ is its head or terminal vertex.


What does "monotonicity" mean in the context of mutability

The author appears to be using the same (general) concept of "monotonicity" as in pure mathematics.

Using the example of a vector, if the size of some particular instance of vector is monotonic, then it would seem reasonable to assume that the memory location of any previously pushed element will not be subsequently modified, and thus that it is safe to directly change the value of that element without having to synchronize with the vector's subsequent push operations.

This assumption seems reasonable for much the same reason why it seems reasonable to assume that the memory location of an element previously pushed onto a (non-circular, array-based, unbounded) stack whose size is strictly increasing will not be affected by a future push operation.  This stands in contrast to a stack on which both push and pop operations are being invoked, and so the memory location of a previously pushed element may be "removed" by a pop operation, and thus available to be assigned to once again (i.e. modified) by a subsequent push operation.

The author's point is that this assumption is not correct, since even in a data structure whose size is strictly increasing, future insertions may affect previously inserted elements by triggering an internal reallocation of some sort that is distinct from the "logical" effect of the insertion.


Why are HMMs appropriate for speech recognition when the problem doesn't seem to satisfy the Markov property

On that subject I recommend you to read a very good paper by James Baker and others who were actually responsible for introduction of HMM in speech:

A Historical Perspective of Speech Recognition
http://cacm.acm.org/magazines/2014/1/170863-a-historical-perspective-of-speech-recognition/abstract

  Using Markov models to represent language knowledge was controversial.
  Linguists knew no natural language could be represented even by
  context-free grammar, much less by a finite state grammar. Similarly,
  artificial intelligence experts were more doubtful that a model as
  simple as a Markov process would be useful for representing the
  higher-level knowledge sources recommended in the Newell report.
  However, there is a fundamental difference between assuming that lan-
  guage itself is a Markov process and modeling language as a
  probabilistic function of a hidden Markov process. The latter model is
  an approximation method that does not make an assumption about
  language, but rather provides a prescription to the designer in
  choosing what to represent in the hidden process. The definitive
  property of a Markov process is that, given the current state,
  probabilities of future events will be independent of any additional
  information about the past history of the process. This property
  means if there is any information about the past history of the ob-
  served process (such as the observed words and sub-word units), then
  the designer should encode that information with distinct states in
  the hidden process. It turned out that each of the levels of the
  Newell hierarchy could be represented as a probabilistic function of
  a hidden Markov process to a reasonable level of approximation. For
  today’s state-of-the-art language modeling, most systems still use
  the statistical N-gram language models and the variants, trained with
  the basic counting or EM-style techniques. These models have proved
  remarkably powerful and resilient. However, the N-gram is a highly
  simplistic model for realistic human language. In a similar manner
  with deep learning for significantly improving acoustic modeling
  quality, recurrent neural networks have also significantly
  improved the N-gram language model. It is worth noting that
  nothing beats a massive text corpora matching the application domain
  for most real speech applications.

Overall, the Markov model is pretty generic model for decoding black-box channel with very relaxed assumption on the transmission thus it is a perfect fit for the speech recognition, however, the question remains what to encode as a state indeed. It is clear that states should be more complex objects than what we assume now (just few preceding words). It is ongoing research to reveal true nature of such structure.


Hindley-Milner type inference for language with implicit type casting

Hindley-Milnor type inference doesn't support implicit type casting, so you can't fix that easily.  You'd need a fundamentally different algorithm for type inference, and I'm not sure whether such a thing exists.  I think there are ways to handle type inference with implicit type casts if you don't care about supporting polymorphic types, but as far as I know, the combination of polymorphic types, type inference, recursion, and implicit type casts is hard to handle simultaneously.

In contrast, it's straightforward to extend HM type inference to handle explicit type casting.


Is huffman coding tree a heap or a trie?

A Huffman tree is a trie: its edges are labeled by $0,1$, and its paths spell out binary words.

Huffman's algorithm uses a min-heap to construct the Huffman tree. At each step, we choose the two items with minimal probability, and merge them.


You're confusing classical and quantum computation, so let me ignore the quantum aspects for now. If you forbid the unary NOT gate then you can use a binary NOT gate, say $g(a,b) = \lnot a$. You can also simulate NOT using natural gates: $XOR(a,1) = \lnot a$ (and this gate can even be made reversible!). So this kind of restriction is not really meaningful.

It is more meaningful to ask what happens if all gates are monotone, that is, they satisfy $g(x_1,\ldots,x_n) \leq g(y_1,\ldots,y_n)$ whenever $x_i \leq y_i$ (here $\text{FALSE}\leq\text{TRUE}$). Such circuits are known as monotone circuits, and they can only compute monotone functions. One natural complete basis is $\{\text{AND},\text{OR}\}$. You can show that this basis is complete using DNFs.


How to find examples of best cases for sorting algorithms?

Bubble sort can "stop early" should the array already be sorted. Other algorithms have their own advantages or applications, but none of the algorithms mentioned in your question - other than bubble sort - can "stop early".

Therefore for any input Insertion & Selection runtime will be $\Omega (n^2) $, and Mergesort $\Omega(nlog(n))$, so the order of elements doesn't matter at all.

$\bullet $ If you perform bubble sort on an already sorted array, the algorithm can stop when not performing any swaps, and run at $O(n)$

$\bullet $ Merge sort (to which you refer as 'fusion sort' from some reason) is the only algorithm that requires $O(nlog(n))$ rather than $O(n^2)$

$\bullet $ Insertion sort is useful when receiving the array online (one element at a time) and maintaining it sorted. Its noteworthy that since you maintain a sorted array, new elements can be inserted via binary search, which make the insertion sort perform $O(nlog(n))$ comparisons, but still cost $O(n^2)$ due to moving elements.

$\bullet $ Selection sort is very easy to implement and intuitive to explain


If lower bound of a problem is exponential then is it NP?

No. For example, the halting problem has an $\Omega(2^n)$ lower bound, but it is not in NP (since it is not computable).

The nondeterministic time hierarchy theorem shows that any NEXP-complete problem is another example (with $2^n$ potentially replaced by a smaller exponential function $c^{n^\epsilon}$).

NP is an upper bound on the complexity of a problem.


If a language decidable by a PDA then it is also decidable by a TM. In other words TM are more computationally powerful than PDA, i.e., the class of languages decidable by PDA is a proper subclass of the class of languages decidable by TM. You can also easily simulate a PDA on a TM.

However not all languages are decidable by PDA. So your approach does not work in general.

As to CFG to PDA conversion I would recommend the textbook by Sipser (pg 116). Google search for "CFG to PDA" also gives a good result.


Neural Network weight selection using Genetic Algorithm

Your understanding is correct.

Yes, you do create a new neural network for each chromosome (although you're considering the network structure as fixed, so technically you could reuse them by just resetting the weights anew for each chromosome.
For the error, you're on the right track. For a GA, generally only relative differences in fitness are important, so it doesn't really matter if you divide by 100 or not -- that's just linearly scaling the fitness values. That might matter for some choices of genetic operators (e.g., roulette-wheel selection can be sensitive to absolute fitness values), but often it won't matter at all.


Is it possible to encode logical expression and interpret it with SQL?

Using disjunctive normal form (DNF) representation. The following 3 tables arrangement seems to solve the problem (NB: using better names for tables, not same as in the question):

> select * from F;
+------+------+
| f1   | f2   |
+------+------+
|    1 |    1 |
|    1 |    2 |
+------+------+

> select * from C;
+------+------+
| c1   | c2   |
+------+------+
|    1 | A    |
|    1 | B    |
|    2 | C    |
+------+------+

> select * from V;
+------+------+
| v1   | v2   |
+------+------+
| A    |    0 |
| B    |    0 |
| C    |    1 |
+------+------+

Where F is a table for formulae, mapping from formula number to a table of conjuncts (C), which has a pointers into table of variables (V). The formula encoded here is (A AND B) OR C.

Doing conjunction is simply a matter of applying min() and disjunction is done by max().

Evaluating formula (number 1 in the example above) can be done by the following query:

> select max(A.v) as result from F, (select min(v2) as v, c1 from C, V
                                     where c2 = v1 group by c1) as A
  where c1 = f2 and f1 = 1;
+--------+
| result |
+--------+
|      1 |
+--------+

The above approach is a bit simplified - NOT is not possible to express, but it is easy to add it as an extra boolean column of table C and XORing it with the variable value.


Can a CS grad student work on quantum field theory and string theory problems?

There are plenty of computer scientists working on quantum computation and quantum information so, yes, there should be plenty of opportunities to work on that sort of thing as a CS grad student.

I'm not aware of any computer scientists working on string theory but it's far from my area of expertise so it's possible it happens without my knowing about it. However, I've been to plenty of theoretical CS conferences where there were a couple of talks about quantum things but I don't remember any talks at all about string theory. And, of course, if you try to Google for something like "string theory computer science", Google thinks you mean strings of text.


You are working harder than you have to. There are lots of ways to prove this but in general the idea is that you should just find some constants that work, not worry about finding precise small constants.

In this case we don't even need constants! Assuming $n \geq 1$, we have
$$n^4 + 2n \geq n^4$$
always. And
$$n^4 \geq n^2$$
always.

So $n^4 + 2n \geq n^2$, which means $n^4 = \Omega(n^2)$.

...

An easier definition of $\Omega$ is that you need to find a positive constant $C$ so that
$$C(n^4 + 2n) \geq n^2$$.
As mentioned above, $C = 1$ works!

...

Finally, for your example, as in the comment on cstheory, if you want to do it your way, you can always just pick a really high $n_0$ and check that it does indeed work. In general, you can try to solve the equation $C(n^4 + 2n) = n^2$ for $n$, once you have picked a constant $C$ using your limit approach.


Bubble Sort with "while" loop - why is average case n^2?

Let's prove a more general result:

  Any sorting algorithm which only swaps adjacent elements makes $\Omega(n^2)$ swaps on average.

Let us assume that the elements being sorted are $1,\ldots,n$, and their positions are $i_1,\ldots,i_n$. We need to move element $j$ from position $i_j$ to position $j$. Each swap changes the position of two elements by 1. It follows that the number of swaps is at least
$$
\frac{1}{2} \sum_{j=1}^n |i_j - j|.
$$
The marginal distribution of each $i_j$ is uniform over $\{1,\ldots,n\}$, hence the expected number of swaps is at least
$$
\frac{1}{2n} \sum_{i=1}^n \sum_{j=1}^n |i-j| = \frac{n^2-1}{6}.
$$


Time complexity for calculating the $LPS$ array (failure function) in KMP algorithm preprocessing

I've copied below the wikipedia algorithm for computing the LPS array (which is usually called the failure function because in the main KMP algorithm you refer to this table whenver there's a failed match). They denote $T[]$ where you use $LPS[]$

  algorithm kmp_table:
      input:
          an array of characters, W (the word to be analyzed)
          an array of integers, T (the table to be filled)
      output:
          nothing (but during operation, it populates the table)

define variables:
    an integer, pos ← 1 (the current position we are computing in T)
    an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring)

let T[0] ← -1

while pos < length(W) do
    if W[pos] = W[cnd] then
        let T[pos] ← T[cnd]
    else
        let T[pos] ← cnd
        let cnd ← T[cnd] (to increase performance)
        while cnd >= 0 and W[pos] <> W[cnd] do
            let cnd ← T[cnd]
    let pos ← pos + 1, cnd ← cnd + 1

let T[pos] ← cnd (only need when all word occurrences searched)

The running time will be dictated by how many times "cnd" gets assigned to. The while loop inside the for loop ($pos$) might make you think the algorithm is $O(m^2)$ but as you learned it is $O(m)$.

Inspect how $cnd$ may change during one step of the for loop; it can either increase by +1, or it can decrease inside the while loop. And when it decreases, it decreases by at least 1, since $T[]$ satisfies $T[x]<x$ for all $x$ ("proper" in the definition of LPS). Since $cnd$ can increase only by +1 and there are $m$ steps in the for loop, this means the overall increase is bounded by $+m$.  You might visualize each change to $cnd$ as a stair of integer height, with upstairs and downstairs representing increases and decreases to $cnd$; the upstairs are all height 1, and the downstairs are each height at least 1.  Because the overall height never falls below 0 (that is the termination condition for the while loop), you can bound the total number of stairs by $2m$; there are at most $m$ "up" stairs and there can't be more "down" stairs than up stairs since their height is $\geq 1$.

To put another way, this is basically a twist on the saying "what goes up most come down"; here we have "what comes down must have gone up before"


In contrast to your example, Chaitin's constant is not defined as follows:

$$ \Omega = \sum_{n\colon \text{$n$th program halts}} 2^{-n}. $$

Instead, there is a set $\Pi \subseteq \{0,1\}^*$ of allowed programs which is prefix-free (no string is a prefix of another string). Each of the programs in $\Pi$ is legal (this negates your Java example). If the programs are encoding in unary then it is indeed the case that the $n$th program has length $n$, and then your definition of $\Omega$ works. But for other encodings, the definition of $\Omega$ is

$$ \Omega = \sum_{ p \in \Pi\colon p \text{ halts} } 2^{-|p|}, $$
where $|p|$ is the length of the binary string $p$. Kraft's inequality shows that $\sum_{p \in \Pi} 2^{-|p|} \leq 1$.

Chaitin's constant is algorithmically random: the (prefix) Kolmogorov complexity of the first $n$ bits is $n - O(1)$. To show this, note first that $\Omega_n$, the first $n$ bits of $\Omega$, suffice to determine whether a program of length $n$ (under the encoding $\Pi$) halts or not. Indeed, as a fraction, $\Omega_n \leq \Omega < \Omega_n + 2^{-n}$. Run all programs in parallel, and whenever $p$ stops, add $2^{-|p|}$ to some counter $C$ (initialized at zero). Eventually $C \geq \Omega_n$ (since $C \to \Omega$ from below). At this point, if the input program of length $n$ didn't halt, then you know that it doesn't halt, since otherwise $\Omega \geq C + 2^{-n} \geq \Omega_n + 2^{-n}$.

Given this, suppose that for some $K>0$ and infinitely many $n$, you could compute $\Omega_n$ using $n - K$ bits. For each such $n$, you can find a string whose Kolmogorov complexity is larger than $n$, by considering the output of all halting programs of length at most $n$.  For large enough $K$, the result is a program of length at most $n$ for computing the a string whose Kolmogorov complexity is more than $n$. This contradiction proves that for some $K$, the Kolmogorov complexity of $\Omega_n$ is at least $n-K$.

Algorithmic randomness of $\Omega$ implies, in particular, that the frequency of 0s and 1s in its binary expansion tends to 1/2. Indeed, suppose that for some (rational) $\epsilon > 0$ there exist infinitely many $n$ such that the fraction of 1s in $\Omega_n$ is at most $1/2-\epsilon$. Since there are only at most $2^{h(1/2-\epsilon)n}$ strings with at most $1/2-\epsilon$ many 1s, we can compress $\Omega_n$ to size $h(1/2-\epsilon)n + 2\log n + C_\epsilon$ (the constant $C_\epsilon$ depends on $\epsilon$ since the program needs to know $\epsilon$). However, this is $n - \omega(1)$, contradicting the algorithmic randomness of $\Omega$.


If $PSPACE^{SAT}=PSPACE$ and $PSPACE \subseteq EXP$, then why does $EXP^{SAT}$ not necessarily equal to $EXP$?

The fact that the base class can simulate the oracle does not mean that the oracle does not give additional power. Consider the polynomial hierarchy, $\mathsf{NP,NP^{NP},NP^{NP^{NP}}},...$ at the $i$'th level you get an oracle for the $i-1$ level, so following your line of thought we should not gain additional power. However a naive simulation of the oracle does not suffice, since taking the wrong path may lead us to accept an input outside the language (we need to be sure of the oracle's answers).
A class which is famously not low on itself is $\mathsf{EXP}$, since $\mathsf{EXP^{EXP}=2EXP}$. A naive simulation in your case fails for similar reasons, as a machine in $\mathsf{EXP^{SAT}}$ can ask the about the satisfiability of exponentially long formulas.


Show that boring boolean circuit belongs to NP-complete class

The problem is PP-hard. This means that unless the polynomial hierarchy collapses to NP, then deciding whether a circuit is boring is not in NP (and consequently is not NP-complete). The collapse follows from the fact that PP is closed under complement, so $\mathsf{PP=NP}$ implies $\mathsf{NP=coNP}$. We now show that deciding whether or not a circuit is boring is PP-hard.

Suppose $L\in PP$, then there exists a probabilistic polynomial Turing machine $M$ such that $x\in L \iff \Pr\left[M(x)=L(x)\right]>\frac{2}{3}$. Now consider the machine $M'$ which tosses two coins, if both output "heads" accept, otherwise execute $M$. If $x\in L$ then $M'$ accepts $x$ with probability $\frac{1}{4}+\frac{3}{4}\Pr\left[M(x)=L(x)\right]>\frac{3}{4}$. Now, let $C_x$ be the corresponding circuit for $M'$ on input $x$ (its inputs are the coins for $M'$), then $x\mapsto C_x$ is a reduction from $L$ to your problem, since $x\in L\iff C_x \text{ is boring}$. To see why, note that if $x\in L$ then $C_x$ accepts more than $\frac{3}{4}$ of the possible inputs, and if $x\notin L$ then $C_x$ accepts $\frac{1}{4}\le t\le \frac{3}{4}$ of the possible inputs.

In fact, your problem is PP-complete. To see why this language lies in PP, Let $L$ be the language of circuits who accept more than a $\frac{3}{4}$ fraction of their input, and $L'$ be the language of circuits who reject more than a $\frac{3}{4}$ fraction of their inputs. Clearly $L,L'\in PP$, and since PP is closed under union, deciding whether a circuit is boring, i.e is in $L\cup L'$, is in PP. Note that both here and in the above we used the fact that the constant in the definition of PP can be changed to any rational number.

If we want to avoid using closure properties of PP, then an argument along the following lines should work. Consider the machine $M$, which upon given an $n$-input circuit $C$, approximates the acceptance probability of $C$ by evaluating it on different uniformly distributed random length $n$ strings. Let $\hat{p}$ denote our evaluation. If $\hat{p}\ge\frac{1}{2}$, then $M$ evaluates $C$ on a random string and accept iff $C$ accepts, otherwise $M$ accepts iff $C$ rejects.
Let $E$ denote the event that $|p-\hat{p}|\le \frac{1}{4}$, where $p$ is the real acceptance probability of $C$. By evaluating $C$ on polynomially many strings, we can make sure that $\Pr\left[E\right]\ge 1-\frac{1}{2^{2n}}$. If $C$ is boring, then conditioned on $E$, $M$ obtained the right evaluation of the majority of $C$ and accepts with probability $>\frac{3}{4}$. Thus, if $C$ is boring $M$ accepts with probability $>\frac{3}{4}\left(1-\frac{1}{2^{2n}}\right)$. If $C$ isn't boring, then $C$ outputs either $0$ or $1$ with probability of at most $\frac{3}{4}-\frac{1}{2^n}$. Thus, regardless of our evaluation $\hat{p}$, $M$ accepts $C$ with probability of at most $\frac{3}{4}-\frac{1}{2^n}<\frac{3}{4}\left(1-\frac{1}{2^{2n}}\right)$, which puts our language in PP.


Hint: Your string is of the form Dice+Dice+Dice+Int. Figure out how to obtain this from Roll using only the first, third and fourth rule.


Use of Big O Notation in a recent paper by Khot et al

In general, when you see big-O notation in algorithms, the default assumption is that the number that's varying is the size of the input.  Here the input size is $n+m$.

In this case the claim is valid if you think of it in terms of $m$, the number of constraints.

The claim that is being made here is a very basic claim.  It's basically a consequence of the fact that $\text{Var}[X] \to 0$ as $m \to \infty$, where the random variable $X$ is the fraction of constraints satisfied by a random assignment.  (Heuristically, if you were willing to assume independence, it would follow from the Central Limit Theorem.  In this case, you cannot assume independence, but a similar result follows nonetheless.)

If you are not sure how to prove this claim, or were unable to recognize this as a fairly standard concentration result, then you're probably going to find the  rest of the paper very difficult going, and you might  need to start by reading more basic textbooks and papers before diving into this paper.


How to formally prove that if triangle inequality is satisfied in a bunch of edges, then each edge has a positive value?

Let us first go into the proof. Let us then review any further considerations as you do (ie., whether the graph should be complete or not).

Lemma Given an undirected graph $G=(V,E), |V|\geq 3$, and a cost function $c$ defined over $E$, if the triangle inequality is satisfied, then $c(u,v)\geq 0, \forall \langle u,v\rangle \in E$.

Note that the lemma does not require the graph to be complete ---a graph is complete if there is an edge for every pair of vertices, i.e., $\langle u, v\rangle\in E, \forall u, v\in V$.

To prove the statement above take any three vertices $u, v, w\in V$ which are related to each other, i.e., that form a triangle. Let $\alpha=c(u,v), \beta=c(v,w), \gamma=c(u,w)$. Let us assume further without loss of generality that these edge costs are sorted in increasing order of cost: $\alpha\leq\beta\leq\gamma$ ---and this order necessarily exists as discrete optimization problems are usually defined over total orders.

Now, let us proof by contradiction the lemma. There are three different cases (all somehow related to each other, if you manage to understand the first, the others are rather equivalent but I wrote them down here for your convenience).

Case 1 (only one negative edge cost)

Assume that $\alpha<0$. Because triangle inequality is assumed by hypothesis then: $\alpha+\beta\geq\gamma$. To make signs apparent, take absolute values: $|\beta|-|\alpha|\geq |\gamma|$, where I considered $\beta, \gamma\geq 0$. Obviously, $|\gamma|\geq |\gamma| - |\alpha|$ and this is true for all plausible values of $\gamma$ (also negative ones). Thus:

$
|\beta|-|\alpha|\geq |\gamma|\geq |\gamma| - |\alpha|
$

leading to $\beta\geq\gamma$ which contradicts our first assumption ($\beta\leq\gamma$).

However, devil's in the details so let us consider the frontier case where $\beta=\gamma$. In this case, take now the other relationship that results from triangle inequality: $\alpha+\gamma\geq\beta$. Since $\beta=\gamma$, the preceding relationship simplifies to $\alpha\geq 0$ which, again, contradicts our second assumption, $\alpha<0$. Hence, $\alpha\geq 0$.

It is straightforward to prove that the same reasoning applies in case $\beta<0$ or, equivalently, that $\gamma<0$. Note, however, that from the order we assumed over these costs, $\beta<0$ implies that there are two edge costs which are negative, and that $\gamma<0$ implies that all of them are negative. These cases are examined next.

Case 2 (two negative edge costs)

Still, there is a caveat in the preceding reasoning. When taking absolute values to make the signs apparent, I considered $\beta, \gamma\geq 0$. You might think that the lemma might not hold in case that two edge costs are negative. Let us assume that both $\alpha, \beta<0$, then as triangle inequality is assumed $\alpha+\beta\geq\gamma$ and again, after taking absolute values the following results: $-|\alpha|-|\beta|\geq|\gamma|$, which is clearly impossible, as the left hand is a negative number and the right hand is a positive number.

And this completes the proof for the second case. If you are thinking of trying the same proof for $\beta, \gamma<0$ or $\alpha,\gamma<0$, note that all edge costs would be necessarily negative as they are sorted in increasing order of cost. This observation leads us to the third case.

Case 3 (all edge costs are negative)

To conclude, what if all edge costs are negative, $\alpha, \beta, \gamma<0$? Oh, well, then it just suffices to combine two expressions resulting from triangle inequality: $\alpha+\beta\geq\gamma$ and, since all of these are negative numbers, then $-|\alpha|-|\beta|\geq -|\gamma|$, but also $\alpha+\gamma\geq\beta$ and, again, because these are all negative numbers then $-|\alpha|-|\gamma|\geq-|\beta|$. Now, the observation is that the first inequality shall hold for values larger or equal than $-|\beta|$ and hence: $-|\alpha|-(-|\alpha|-|\gamma|)\geq -|\gamma|$ which leads to $|\gamma|\geq -|\gamma|$, which is only possible if $\gamma=0$ but this contradicts our assumption that $\gamma<0$ and hence the third case is proven as well by contradiction.

Note to the third case - in case you have difficulty to follow how the last inequality is hold, transform all $\geq$ to $\leq$ by multiplying all inequalities by $-1$. Now, only with positive numbers it might be easier to follow the reasoning.

Observations

Nowhere in the preceding proof I assumed the graph to be complete and, indeed, there might well be a pair of vertices $u,v\in V$ which are not directly related to each other through an edge. What we actually did is to prove that every three vertices connected to each other shall be non-negative given that triangle inequality is verified. This does not prevent some edge costs to be negative. It just suffices that the vertex connected to an edge with a negative cost is not connected to any other vertex. This is true because if the degree of a vertex equals 1 then triangle inequality can not be verified.

Equivalently, if the degree of each vertex is larger or equal than two, triangle inequality can be always verified and, in case it holds, then all edge costs are necessarily non-negative.

Hope this helps,


Why is BNF considered an unsatisfactory technique for describing a language?

You mention one reason.

The other reason is that the syntax of programming languages isn't context-free, unless you define syntax to be that which can be, or is, described by a context-free grammar.

When Strachey's paper was written, the syntax of a new language, Algol 68, was being defined in a new formalism, two-level grammars, that was used to describe syntactic validity in full, including many things that, brainwashed by the "BNF is the syntax" meme, many of us do not consider part of syntax at all, such as all variables needing to be declared before use.

Most of us won't go that far, but will still agree that non-context-free syntactic features in programming languages exist.