The most efficient way of finding/storing neighbourhood info during octree creation

I don't know if there is a way while constructing the oct tree.
But here is way after you created the tree, which runs in O(N), where N is the number of Nodes.
For each node there has to be a maximal comparison of 8*6+7 = 55.
This might can be reduced but this might be fast enough.

loops through all nodes breadth-first.
A neighbour of a child is a neighbour child of the parent or a child of a the parents neighbours.

The comparison if two points are neighbours is here distance(node_1,node_2) == SMALLEST.
I don't know how you compare it. Maybe you can insert your code.
You could caluclate for each level the Euclidian distance of the points if you have equally spaced cuboids
and compare them. That would be the fastest way.

when nothing works, you can just make a list for each of the 8 comparisons, sort them and keep the lowest one.

call function calc_neighbours(root_node) after you created the oct tree

class Node:
    Node **childs // array of size 8 and pointers to the child node pointers
    Node *parent
    Neighbours **neighbours

function calc_neighbours(root_node):
    queue = create_queue()
    queue.add(root_node)
    while (queue.isEmpty() == false)
    {
        parent_node = queue.pop()
        for (int i = 0; i < 8; i++) // for each child_cube
        {
            queue.push(parent_node->child[i])
            for (int j = 0; j < 8; j++) // for each neighbour child_cube
                 if (i != j && distance(parent_node->child[i],parent_node->child[j]) == SMALLEST)
                    // filter out those who share only vertex/edge
                    parent_node->child[i]->neighbours.add(parent_node->child[j])
        }
        if (parent_node != root_node)
        // root node has no neighbours, loops through all neighbours of the parent's neighbour's child
            for (int n = 0; n < parent_node->neighbours->size(); n++)
                for (int i = 0; i < 8; i++) // for each child_cube
                    for (int j = 0; j < 8; j++) // for each neighbour child_cube
                         if (distance(parent_node->child[i],parent_node->neighbours[n]->child[j]) == SMALLEST)
                            parent_node->child[i]->neighbours.add(parent_node->neighbours[n]->child[j])
    }


Your question is equivalent to asking whether or not $DSPACE(O(n)) = NSPACE(O(n))$, which is an open problem, known as the first LBA problem.


Least number of comparisons to identify 6 numbers with values from 1 to 6 (without repetition)

According to Wikipedia, the minimum number of comparisons needed to sort 6 numbers is 10. The lower bound follows from the usual decision tree argument.


It might be useful to take a look at the ZFC axioms. The existence of one element sets is guaranteed by the Axiom of pairing.

The axiom of pairing says that given $A$,$B$ sets, one can construct a third set $C = \{A, B\}$. Formally:
$$ \forall A. \forall B. \exists C.\forall D. (D \in C \iff D = A ~\lor~ D = B) $$

A singleton set is just the pairing $\{A,A\} = \{A\}$.

The axiom of union says that for any set $A$ there is a set $U$ whose elements are exactly the elements of the elements of $A$. That is:

$$ \forall A. \exists U. \forall c. (c \in U \implies \exists D.(c \in D ~ \land ~ D \in A)) $$

  A set $X$ is the union of all its subsets containing just one element.

Let's look at some example, let $X = \{a, b\}^\star$ be a set, take $X^\prime = \{\{a\},\{b\}\} $, which is also a set by the axiom of pairing. By the axiom of union there exists a set $\cup X^\prime$ such that:

$$ \cup X^\prime = \{a,b\} = X$$

So you can look at the Union Axiom and try to modify to fit your problem, you have to make a union on a set of singleton sets, which means you have to find a way to define $X^\prime$.

$\star$: I'm assuming $a$ and $b$ are also sets.

  EDIT: Regarding problem 4.: My main problem is that I am not really
  sure, how to express or write down the solution - I am not too sure,
  what is allowed, what not. Thus I take any idea that seems remotely
  right or constructive.

Well, from your previous answers it seems you're only allowed to use basic operations like membership and equality, if more stuff is allowed you can literally just write something that looks like natural language while still being formal.


As pointed out in the comments, the first term seems broken - too many $x$es.

The key is that function application is not associative (both in the lambda calculus and outside it). In particular, $a(bc)$ is different from $(ab)c$. In the first term, we apply $b$ to $c$ and then $a$ to the result. In the second term, we apply $a$ to $b$ and then apply the result on $c$.

In your case $xx(\lambda x.x)yx$ is parenthesised as $(((xx)(\lambda x.x))y)x$, because function application associates to the left. This means that there is no redex there, it can't be reduced further.

Your mistake was in that you added parentheses like $xx((\lambda x.x)y)x$, which is a completely different term.


Is monoid the category for untyped lambda calculus?

$C$-monoids and their variants is what you are looking for. You can find further references and an account of what is what in Martin Hyland's Towards a Notion of Lambda Monoid.


What is the diference between $\lambda x.1$ and $1$?

$\lambda$-contraction is defined as $(\lambda v.M)N \triangleright_\beta M[v/N]$. A $\lambda$-term of the form $(\lambda v.M)N$ is called a redex (= reducible expression). In order to reduce a term, you need a redex -- that's just how $\lambda$-contraction is defined.
The reason that $\lambda x.1$ can not be any further reduced is that it does not contain any redex: It is not and does not contain any terms of the form $(\lambda v.M)N$, so $\lambda$-contraction is just not applicable anywhere. The term thus already is in normal form.
In contrast, $(\lambda x.1)0$ contains a redex, namely itself -- with $v = x$, $M = 1$ and $N = 0$ --, and $\lambda$-contraction yields the normal form $1$.
Obviously $\lambda x.1$ and $1$ are non-equivalent normal forms: One is a function that yields a number, the other one is a number.
$(\lambda x.1)$ is different from $(\lambda x.1)0$ in the same way in which, say, $f: x \mapsto x^2$ is different from $f(2)\ (= 4)$. A function is not the same as the value of the function at an argument, and a function can not be applied to yield a value without an argument present.


Computing Hamming Distance Between Binary Vectors

You say in the comments that we might have $c \approx 15$ or so. There should be very efficient algorithms in this case, using locality sensitive hashing.

For example, here is a simple LSH.  Randomly choose a set of about 10,000 indices (out of the 1,000,000).  Hash each vector by computing some standard hash of the 10,000 bits in those positions (ignoring the other 990,000 bits entirely).  Store all the vectors in a hashtable using this hash.  Now look for all pairs of vectors that have the same hash.  This can be done by storing all the vectors in a hashtable using this hash and looking at all collisions within a single hash bucket, or by sorting the hashes and looking at adjacent pairs.

Suppose the pair of vectors $b_i,b_j$ are at distance $\le 15$.  Then with probability about 0.86, they will agree in the selected 10,000 positions and thus have the same hash.  In other words, about 86% of the pairs of vectors at distance $\le 15$ will be found in this way.

Now you can repeat this multiple times to ensure you find all of the pairs, with high likelihood.  If you repeat this about 10 times with a different random set of indices each time, then only about $10^{-8}$ of the pairs that are close will be missed.  If you repeat it 100 times, each close pair has only a $10^{-85}$ probability to be missed.  That probability is so low it can be safely ignored: essentially, all close pairs will be found.

The running time is $O(n^2)$: $O(n)$ time to compute each hash, and then you do that $n$ times for $n$ different vectors.  In practice it might be even faster than that if you can take advantage of the fact that most of the bit positions are ignored during the hashing.


Proof of correctness of A star search algorithm

Check the original paper which talks about its correctness -

Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. "A formal basis for the heuristic determination of minimum cost paths." Systems Science and Cybernetics, IEEE Transactions on 4.2 (1968): 100-107.

See especially Section II and Theorem 1.


A graph $G$ whose nodes are numbered is uniquely described by its adjacency matrix. Concatenating the matrix's rows yields a natural number $\cal{G}$ in binary representation; in order to deal with leading $0$, prepend a $1$. This mapping is obviously injective. For easier decoding, you might want to use Cantor's pairing function on $(\cal{G}, |V|)$ and use the result as graph number.

Computing this mapping is easy, but the resulting number can be huge ($\approx 2^{|V|^2}$).

In the case nodes cannot be identified, the (conjectured) hardness of Graph Isomorphism (probably) prevents an efficient, real mapping from Graphs to the naturals; for now, we have to be satisfied  with a mapping from graph presentations to naturals---or show considerable genius.


How can a set offer better search performance than an array

I think the key is that NSSets aren't required to "maintain order," meaning that you cannot access elements with an index, nor can you extract elements in any particular order.  Because NSSets don't offer those kinds of accesses the implementation is free to use hashing, trees or anything else that gives speedier membership checks.


Is there any property about height of PDA?

If you could bound the stack height, say to some constant $c$, then it would have been possible to define an NFA for the task: Simply encode in the NFA states another $c$ values that represent the current values in the stack (by defining $\hat Q=Q\times\Sigma^c$. The rest i will leave to you)

This would contradict the non-regularity of this language, and therefore you cannot give such a bound.


Help need to learn Quantum Computation and Information

I haven't watched them myself, but you could probably do worse than Michael Nielsen's videos, Quantum Computing for the Determined.

I'd recommend also that you look online for written lecture notes; there is a very strong culture in the field of having students scribe notes which then have a habit of finding their way online. These can sometimes vary substantially in quality, but often the lecturer will take them and edit them, resulting in quite a good set of notes. Just as an example that I grabbed off the top of Google, Ronald de Wolf's lecture notes seem fairly comprehensive; but others surely exist, and if you find the going hard with those notes, you will probably find one set of notes which better suits your learning style.


Mutual information tells you how much you learn about $X$ from knowing the value of $Y$ (on average over the choice of $Y$). In other words, mutual information measures how many fewer bits you need to encode $X$ if you already know $Y$, than if you didn't. In your example, learning $Y$ enables you to guess $X$ correctly with probability 0.75, but as $H_2(0.75)>0.5$ ($H_2$ being the binary entropy function), you still need more than half a bit to encode the correct value of X even if you know Y. So your "savings" in encoding length are less than 0.5.

Here is a more illustrative example, I think. You have three random bits, $X$, $Y$, $Z$. $X$ and $Y$ are independent and unbiased, while $Z$ is the exclusive or of $X$ and $Y$. Then $H(X,Y) = 2$, while $H(X,Y|Z=z) = 1$ for any $z \in \{0,1\}$, because knowing $z$ and the value of $X$ determines $Y$. Then $I(X,Y;Z) = H(X,Y) - H(X,Y|Z) = 1$. In words, if you know $Z$ you only really need to encode $X$ rather than both $X$ and $Y$.


Implement opposite() method to tell if there are two opposite numbers, (x,-x)

Here is what they intended you to do. You keep a counter of the number of opposite elements, which starts at zero. When inserting an element $x$, you insert both the true element $x$ and the dummy element $-x$; if $-x$ was already there, then you increase your counter of opposite elements. Similarly, when deleting $x$ you delete both $x$ and $-x$, and possibly decrease the counter.


You don't need to redo the proof for this, simply note that $n$ symbols of an alphabet of size $k$ can be represented with $n \log_2(k)$ bits.  The Lempel-Ziv bound is then:

$\mbox{# phrases} \leq \frac{n log_2 k}{(1-\epsilon_{n \lg k})log_2(n \log_2 k)}$

Dividing numerator and denominator by $\log_2 k$ then gives:

$\mbox{# phrases} \leq \frac{n}{(1-\epsilon_{n \lg k})\left(log_k(n) + \log_2(\log_2(k))/log_2(k)\right)}$

Since $\epsilon_n \longrightarrow 0$ as $n \longrightarrow \infty$, the result follows.


If $n$ is odd, the graph has an Euler trail, i.e., a simple walk on all $\tfrac12n(n-1)$ edges.  This is obviously optimal, since it uses every edge in the graph.

If $n$ is even, delete a matching of size $\tfrac12n-1$, i.e., delete a set of that many edges, no two of which share an endpoint. The resulting graph $G$ has two odd-degree vertices and $n-2$ even-degree vertices, so it has an Euler trail, which is a simple walk of length $$\tfrac12n(n-1) - (\tfrac12-1) = \tfrac12n(n-2)+1\,.$$ This is optimal. Any simple walk is an Euler trail of the graph formed from the vertices and edges of the walk. But any simple walk in $K_n$ longer than the one just described would have to contain at least four vertices of degree $n-1$, which is odd. And no graph with four odd-degree vertices has an Euler trail.


Path in a vertex-weighted undirected graph

So this is a simple solution to this question. Given an instance of Hamiltonian path problem $G(V, E)$. Just set $w$ and $\mathrm{max-visit}$ to be equal to $1$ everywhere and $W=|V|$. A path in $G$ satisfies the requirements in our problem now corresponds to a Hamiltonian path in the original instance, and vice versa.


Determining the intersections of a line segment and grid

I suggest using a simple iterative method.
Let's first find the places where it crosses a vertical grid lines.  These are places where the line goes through a point $(x,y)$ where $x$ is an integer.  The points $(x,y)$ on the line can be written in the form
$$(x,y) = (x_0,y_0) + t (x_1-x_0,y_1-y_0),$$
where $(x_0,y_0),(x_1,y_1)$ are the two endpoints of the line and $t \in [0,1]$ is a free variable.  Now this point crosses a vertical grid line if $x$ is an integer, i.e., if $x_0 + t(x_1-x_0)$ is an integer.  This has solutions of the form $t = (i - x_0)/(x_1-x_0)$, where $i$ is an integer with $x_0 \le i \le x_1$.
Therefore, to find all places where the line crosses a vertical grid line, you can iterative over $i$ in the range $\lceil x_0 \rceil,\dots,\lfloor x_1 \rfloor$, and for each such $i$, compute $t = (i - x_0)/(x_1-x_0)$ and then compute the point $(x,y) = (x_0,y_0) + t (x_1-x_0,y_1-y_0)$.  This enumerates all such points on the line.
You can repeat the same for places where the line crosses a horizontal grid line, i.e., where $y$ is an integer.  You can then merge these two sequences, sorting them by increasing value of $t$ (note that no sort operation is needed as the list of horizontal crossings and the list of vertical crossings are both already sorted; you just need to merge these two sorted lists).
The running time is linear in the number of such points.  This is asymptotically optimal; obviously any algorithm to output all such points must take at least $O(1)$ time per point, so needs to take at least linear time.
This does not have problems with accumulation of floating point errors, as far as I can see.  I don't see how this would cause missed or double crossings.  I find it elegant, though of course that is a matter of personal taste.


Prove ALL$_{\text{TM}}$ is undecidable reduction problem

You can reduce from $H_{TM}$:

For input $<M,w>$ return (the encoding) for a machine $M_ {M,w}$ such that on input $x$:

Simulate $M(w)$
$Accept$

It’s easy to show
$M_{M,w} \in ALL_{TM} \leftrightarrow <M,w>\in H_{TM}$


Why is reduction mostly associated with proving hardness?

Actually, people do commonly use reductions for both purposes: both for proving lower bounds, and for designing algorithms to handle a certain problem.

For instance, it's very common to reduce a problem to linear programming, to a max-flow problem, or to another well-studied problem.  This is using reductions for solving problems.

Any particular textbook might focus more one or the other use of reductions.  That's a philosophical choice on the part of the author.


DFA for even number of As, odd number of Bs and precisely one C

Divide and conquer. You could design a DFA over the alphabet $\Sigma = \{A,B,C\}$

for an even number of A, call it $M_1$
for an odd number of B, call it $M_2$
accepting exactly one C, call it $M_3$

Then design a new DFA equivalent to $M_1 \cap M_2 \cap M_3$ (by closure properties of regular languages).


Imagine an NFA with a single state, which is final/accepting. It has no edges.

This NFA accepts the language $\{\varepsilon\}$—that is, only the empty string. If it is given a non-empty string, it looks for appropriate edges leading away from the starting state, finds none, and fails.


The concept of a "best" algorithm is not as simple as you'd expect. It depends on at least two more parameters: the machine model and the numbers involved (i.e., how large are the numbers being operated on). For a thorough discussion of this as regards integer multiplication, see Fürer's paper How Fast Can We Multiply Large Integers on an Actual Computer?

There is a wikipedia page devoted to the computational complexity of mathematical operations, including everything you mention. However, from a practical point of view, I would rather look at the source code of a strong library for multiprecision arithmetic like GMP. Such a library is optimized for fastest performance on actual computers. The source code of GMP is readily available, and you can peek under the hood.


Data strucutre for finite graphs on a cylinder

Let the vertices at the top be $a_0, \dots, a_{n-1}$ and those at the bottom be $b_0,\dots, b_{n-1}$, both ordered, say, clockwise. If the graph has no edge-crossings, the edge set can only be $\{(a_i,b_{i+k})\mid 0\leq i\leq n\}$ for some $k$, with addition carried out modulo $n$. So the edge set is uniquely determined by the value of $k$.

Beyond that, though, it's not clear what you're asking. The embedding of the graph in the surface of the cylinder could be much more complicated than you're suggesting. For example, the edges could all spiral anticlockwise around the cylinder thirteen times. Or they could spiral anticlockwise three times, then clockwise four times, and then wiggle around lots. Perhaps you have a requirement that the edges can't spiral multiple times? And/or that they're straight lines if you "unwrap" the cylinder and lay it flat?  If so, note that gluing two cylinders together doesn't maintain this property: for example, if you glue the cylinder that has edges $(a_i,b_{i+1})$ using shortest paths to the cylinder that has edges $(a_i,b_{i-1})$ using shortest paths, you get a cylinder whose edges zig-zag, so aren't straight lines, don't use shortest paths and don't "go the long way around". Likewise, if you glue $2n$ copies of the cylinder that uses shortest paths to link $a_i$ to $a_{i+1}$, you get a cylinder whose edges spiral twice.


What is the difference between halting, accepting, and deciding in the context of Turing machines?

Accepting and rejecting the state a Turing machine may eventually enter, is based on the string read from the tape, not just the symbol from one cell. Of course, the decision about entering an accepting or rejecting tape is ultimately made on the basis of one symbol.

A Turing machine can either eventually enter an accepting state, enter a rejecting state, or loop forever. If it enters either an accepting or rejecting state, then it halts.

A Turing machine is said to be total if it halts on all inputs.

The language accepted by a Turing machine is the set of all words that that, when provided as input to the Turing machine, cause the Turing machine to enter an accepting state.

A language is said to be decidable if and only if there exists a total Turing machine that will accept the language.


Given two sorted arrays check if one is subset of another

There is a O(n) solution to this.

Finding all possible start index of the subset can be eliminated

while(loc > -1) {
    allIndexes.push(loc);
    loc = a1.indexOf(a2[0], loc + 1);
}

And, there seems to be an edge case where it will attempt to access element out of the array's bounds. I mean, the input like the one below

A1 = [-1, 0, 1, 3, 1, 2], A2 = [1, 2, 3]

The below pseudocode-like is a starting point, there is still optimisations left in this algorithm.

Given array A, find the presence of sub array B,

matchPointer = 1
for i = 1 to A.length
  if A[i] == B[matchPointer]
    if matchPointer == B.length
      "Subset Found"
    matchPointer = matchPointer + 1
  else
    matchPointer = 1;


The Whitney rank polynomial, an analog of the well-known Tutte polynomial of graphs, enumerates the number of subsets of a matroid of given size and rank. It can be computed using a deletion-contraction recurrence essentially the same as the recurrence for the Tutte polynomial. You can find the details in Welsh's Matroid Theory, §15.4. From the rank polynomial it is easy to read off the expected rank of $S_i$.

Granted, this algorithm takes exponential time, which is not necessarily better than direct counting. Computing the coefficients of the rank polynomial is #P-hard, which suggests that computing the expectation might be hard as well. You can estimate it to your heart's content by sampling, though.


Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not

Since $M_0$ and $w_0$ are fixed parameters of the problem, the answer is yes: for every fixed $M_0$ and $w_0$, there exists a Turing machine $M_{M_0, w_0}$ (depending on  $M_0$ and $w_0$) such that, for the input $(M_0, w_0)$, $M_{M_0, w_0}$ returns $1$ if $M_0(w_0)$ halts and 0 otherwise.

In particular one such Turing machine $M_{M_0, w_0}$ must be one of the following two machines:

$M'_1$: Write $1$. Halt.
$M'_0$: Write $0$. Halt.

If, instead, you are looking for an algorithm that takes $M_0$ and $w_0$ as input and outputs a machine $M_{M_0, w_0}$ with the above property, then you are out of luck: there is not such algorithm in general (it might exist if you restrict the set of input machines $M_0$).
Suppose that such an algorithm (i.e., Turing machine) $A$ existed, then it would allow to solve the halting problem:

Given $M_0$ and $w_0$, compute $M_{M_0, w_0}$ by simulating $A$ on input $(M_0, w_0)$.
Simulate $M_{M_0, w_0}$ on input $(M_0, w_0)$. By definition of $M_{M_0, w_0}$ this step requires finite time.
Return "yes" if the output of $M_{M_0, w_0}( (M_0, w_0) )$ was $1$, otherwise return "no".


I would suggest keeping a hash table (which you possibly are) to search for addresses.  Use one table for all the different pools.  Do not keep separate tables for each pool.

The idea is that you start from a newly released block. You know its start address and its length.

To find blocks after the newly released one we simply calculate the first address after the block and search for it.  If we find one we join them.

Now we search backwards.

To search backwards our address table must contain not only the start, but the end of blocks.

We search the table for entries matching our end-of-block address.  Again if we find them we join.

If we are doing this check every time we get a newly released block then we do not need to check more than one post- and pre- address block each time.  As these are hash table look-ups they'll be fast.

If we do this check periodically we will need to scan all blocks systematically for matches, including rechecking new joined up super blocks for additional matches.


Can we make a non-regular language regular via concatentation?

Yes this is possible. Consider the example given below:

Let $B = 1^p$ where $p$ is prime. This is non regular.
Let $A = 1^n$ where $n \in \mathbb{N}$. This is regular.

$AB$ will simply give us $1^n$ with $n > 2$ and this is regular since any number greater than $2$ can be reprsent as $2+x$ where $x > 0$


Since the number of bins is fixed, the problems boils down to a job shop scheduling with atomic jobs. See https://en.wikipedia.org/wiki/Job_shop_scheduling#Atomic_jobs

A solution is given by $\max\{ 1/m \sum_{i=1}^n t_i, max_i t_i  \}$
where $t_i$ represents the $i$th integer and $m$ represent the set length. The wiki reference above includes a paper with the proof.

EDIT after request on polynomial time
Since it's equivalent to the partition problem, which is NP-hard, this problem is also NP-hard and therefore not solvable in polynomial time.


Min-max the component-wise sum of two sets

Let $f$ be an optimal solution in which $f(a_1) < f(a_2)$ for some $a_1 < a_2$. Let $g$ be obtained from $f$ by switching the values at $a_1$ and $a_2$:
$$
g(a) = \begin{cases} f(a_2) & a = a_1, \\ f(a_1) & a = a_2, \\ f(a) & \text{otherwise}. \end{cases}
$$
Then
$$
\begin{align*}
a_1 + g(a_1) &= a_1 + f(a_2) < a_2 + f(a_2), \\
a_2 + g(a_2) &= a_2 + f(a_1) < a_2 + f(a_2), \\
a + g(a) &= a + f(a) & \text{otherwise}.
\end{align*}
$$
It follows that $\max g \leq \max f$.

Consider now $f$ as a permutation on $\{1,\ldots,n\}$: the first element is the index of $f(a_n)$, the second element is the index of $f(a_{n-1})$, and so on. It is a classical result that $f$ can be sorted by transposing pairs of numbers in the wrong order, an operation which corresponds to the transformation above (one way is to put $n,n-1,\ldots,2$ in their right place, if needed, in this order). The correctness of your algorithm immediately follows.

Comment: This sort of analysis is very reminiscent of the analysis of greedy algorithms.


Job sites for applied/interdisciplinary mathematics related to computer science?

There are 2 google lists:

Imageworld

visionlist

You can join these. They have a lot of information.


High Level Explanation of the Pumping Lemma

By definition, a language is regular if, and only if, it is accepted by a deterministic finite automaton (DFA). So, given a language $L$, suppose it is accepted by some DFA $M$. $M$ has some number of states: let's call it $p$.  Now, consider the operation of $M$ on a string $w\in L$ that has length greater than $p$.

If $M$ accepts $L$, then it must accept $w$.  By the pigeonhole principle, there must be at least one state $q$ that $M$ visits twice. Write $w=xyz$, where $x$ is the sequence of characters that $M$ reads until it first reaches $q$, $y$ is the sequence of characters read between the first and second visits to $q$ and $z$ is the rest of $w$. Note that $y$ must be at least one character, since it occurs between the first and second visit to $q$, which are different positions in the input. Observe that:

from the initial state, reading $x$ takes you to state $q$;
from state $q$, reading $y$ takes you back to $q$;
from state $q$, reading $z$ takes you to an accepting state.

The key point is that, from $q$, reading $y$ any number of times, including zero, will return you to state $q$ and you can then read $z$ to get to an accepting state. Therefore, the machine $M$ accepts any string of the form $xy^rz$ for $r\geq 0$.  We have just proved the pumping lemma.

For examples of using the pumping lemma, see our reference question. In essence, you say, "If this language was regular, it would have to obey the pumping lemma. But if it did that, it would have to include all of these strings that it doesn't include. Therefore, it's not regular."


You're on the right track.  For the simpler code, you correctly wrote down the sequence of values that are produced: $2^0,2^1,2^2,\dots$.  In particular, the $t$th output is $2^t$.  Then you were able to find where the loop stops by setting $2^t=n$ and solving for $t$.  That's a great approach.

Try doing the same thing for your actual example.  Hint: the first two outputs are $j$ and $j^2$.  What's next?  Can you generalize What is the $t$th output?  Can you write an equation that represents where the loop stops and solve for $t$?


Applying a multi qubit quantum gate to specific qubits

Don't use the swap method, it's very inefficient. And the other person's answer is specific to the CNOT gate, and to be frank, over-complicates things.

Here's a very simple algorithm that solves your problem for every single case, not just the CNOT gate, for any arbitrary bits.

The algorithm:

let sys = matrix representing the current state of the system
let n = number of qubits being simulated
let lgm = logic gate matrix of size 2^n by 2^n
let f = our logic gate transformation function
for i = 0 to (2^n) - 1:
    lgm[column = i] = f(i)
sys = sys × lgg

In classical computers, there's something known as the "decoder". Let's say I have only 3 wires, effectively, 3 bits. But I want to control 8 wires. Can that be done? Yes, because 3 bits has 8 different possibilities: 000, 001, 010, 011, 100, 101, 110, 111. So we can assign each possibility to one of our 8 output wires. This is called "decoding".

If I pass in the number 101 and we have 3 bits, we know 101=5, so then I will be setting output wire 5 to a high voltage and the other 7 output wires will be 0, which we can represent like this: decode(101) = [0, 0, 0, 0, 0, 1, 0, 0].

In this algorithm, I mention the "transformation function" called "f". For classical computers, the transformation function is just taking in an input value and returning the "decoded" version of the output value. So if we have 3 bits, and the output is 4, then we will be returning [0, 0, 0, 0, 1, 0, 0, 0]. We then assign that as the column of our matrix for that value.

Let's think of "decoding" in terms of qubits. How can we decode the qubits |101>?

We know that for our qubit probability vectors, |0> is [1, 0] and |1> is [0, 1]. Decoding qubits can then be done what's called the Kronecker product.

So if we convert each bit to the probability vector equivalent and take the Kronecker product of all of them, we get...

|101> = |1> ⊗ |0> ⊗ |1> = [0, 1] ⊗ [1, 0] ⊗ [0, 1] = [0, 0, 0, 0, 0, 1, 0, 0]

This is how we'd want to decode qubits. This algorithm can be applied to qubits just the same using this.

Let's try this algorithm on a simpler problem.

Let's assume we have a system with only 2 qubits. If we want to apply the Hadamard gate to just 1 qubit, we can generate a logic gate for both qubits that only applies the Hadamard gate to a single qubit. Let's assume the single qubit we want to apply it to is our most significant qubit and the least significant will be unaffected.

We want a transformation function that for each of our possible inputs, produces the correct output. We have two qubits, this means there are four possible outputs.

f(|00>) = ?
f(|01>) = ?
f(|10>) = ?
f(|11>) = ?

We know the least significant qubit will be unaffected, so we can fill that in.

f(|00>) = ? ⊗ |0>
f(|01>) = ? ⊗ |1>
f(|10>) = ? ⊗ |0>
f(|11>) = ? ⊗ |1>

We also know what the Hadamard does to a qubit, such that:

H(|0>) = 1/sqrt(2)|0> + 1/sqrt(2)|1>
H(|1>) = 1/sqrt(2)|0> - 1/sqrt(2)|1>

So our transformation function is simply:

f(|00>) = (1/sqrt(2)|0> + 1/sqrt(2)|1>) ⊗ |0>
f(|01>) = (1/sqrt(2)|0> + 1/sqrt(2)|1>) ⊗ |1>
f(|10>) = (1/sqrt(2)|0> - 1/sqrt(2)|1>) ⊗ |0>
f(|11>) = (1/sqrt(2)|0> - 1/sqrt(2)|1>) ⊗ |1>

Expand this out to our normalized probability vector form...

f(|00>) = [ 1/sqrt(2), 1/sqrt(2) ] ⊗ [ 1, 0 ]
f(|01>) = [ 1/sqrt(2), 1/sqrt(2) ] ⊗ [ 0, 1 ]
f(|10>) = [ 1/sqrt(2), -1/sqrt(2) ] ⊗ [ 1, 0 ]
f(|11>) = [ 1/sqrt(2), -1/sqrt(2) ] ⊗ [ 0, 1 ]

Now let's actually solve this...

f(|00>) = [ 1/sqrt(2), 0, 1/sqrt(2), 0 ]
f(|01>) = [ 0, 1/sqrt(2), 0, 1/sqrt(2) ]
f(|10>) = [ 1/sqrt(2), 0, -1/sqrt(2), 0 ]
f(|11>) = [ 0, 1/sqrt(2), 0, -1/sqrt(2) ]

That's our transformation function.

Our  logic gate matrix, "lgm", is of size 2^n by 2^n where n = number of qubits being simulated, so in this case it's 2^2 by 2^2 or 4x4.
Our algorithm tells us that for each column i, set the column equal to f(i). We've defined our probability transformation function, so we can easily fill out these columns.

lgm =
    |00>       |01>        |10>        |11>
[ 1/sqrt(2),         0,  1/sqrt(2),          0 ]
[         0, 1/sqrt(2),          0,  1/sqrt(2) ]
[ 1/sqrt(2),         0, -1/sqrt(2),          0 ]
[         0, 1/sqrt(2),          0, -1/sqrt(2) ]

Now the final step in our algorithm is simply matrix-multiplying our matrix representing the entire quantum system, sys, by this logic gate, lgm.

And that does what we want. It will apply the hadamard gate only to the most qubit and leave the least significant qubit alone.
If you don't believe me, you can try it yourself and see that it works.

The reason this is so powerful is because it applies to any case.

Let's try this algorithm on your problem.

Imagine we have a 3 qubit system and we want to apply a CNOT gate to qubit[0] and qubit[2]. If you look up the CNOT matrix on Wikipedia, that matrix only applies to a 2-qubit system. A naive solution would be to append identity matrices to it using the Kronecker product to make it work on systems with three qubits. But this fails here: qubit[0] and qubit[2] are not adjacent, so simply appending identity matrices won't work.

We could swap qubit[0] with qubit[1], apply the CNOT gate, then swap them back. But that's slow. Instead, we could simply generate a non-adjacent CNOT gate for our problem using the algorithm above.

We first need to come up with a transformation function for each case.

f(|000>) = |0> ⊗ |0> ⊗ |0>
f(|001>) = |0> ⊗ |0> ⊗ |1>
f(|010>) = |0> ⊗ |1> ⊗ |0>
f(|011>) = |0> ⊗ |1> ⊗ |1>
f(|100>) = |1> ⊗ |0> ⊗ |1>
f(|101>) = |1> ⊗ |0> ⊗ |0>
f(|110>) = |1> ⊗ |1> ⊗ |1>
f(|111>) = |1> ⊗ |1> ⊗ |0>

If you understand the CNOT gate, you can understand why this is our function. Think of this like a truth table. Since our control qubit is the most significant qubit, qubit[2], only when that qubit is |1> will the least significant qubit, qubit[0], be negated.

Expand this out to our normalized probability vector form...

f(|000>) = [ 1, 0 ] ⊗ [ 1, 0 ] ⊗ [ 1, 0 ]
f(|001>) = [ 1, 0 ] ⊗ [ 1, 0 ] ⊗ [ 0, 1 ]
f(|010>) = [ 1, 0 ] ⊗ [ 0, 1 ] ⊗ [ 1, 0 ]
f(|011>) = [ 1, 0 ] ⊗ [ 0, 1 ] ⊗ [ 0, 1 ]
f(|100>) = [ 0, 1 ] ⊗ [ 1, 0 ] ⊗ [ 0, 1 ]
f(|101>) = [ 0, 1 ] ⊗ [ 1, 0 ] ⊗ [ 1, 0 ]
f(|110>) = [ 0, 1 ] ⊗ [ 0, 1 ] ⊗ [ 0, 1 ]
f(|111>) = [ 0, 1 ] ⊗ [ 0, 1 ] ⊗ [ 1, 0 ]

Now let's actually solve this...

f(|000>) = [ 1, 0, 0, 0, 0, 0, 0, 0 ]
f(|001>) = [ 0, 1, 0, 0, 0, 0, 0, 0 ]
f(|010>) = [ 0, 0, 1, 0, 0, 0, 0, 0 ]
f(|011>) = [ 0, 0, 0, 1, 0, 0, 0, 0 ]
f(|100>) = [ 0, 0, 0, 0, 0, 1, 0, 0 ]
f(|101>) = [ 0, 0, 0, 0, 1, 0, 0, 0 ]
f(|110>) = [ 0, 0, 0, 0, 0, 0, 0, 1 ]
f(|111>) = [ 0, 0, 0, 0, 0, 0, 1, 0 ]

Let's make these the columns of our lgm matrix.

lgm =
[ 1, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 1, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 1, 0, 0 ]
[ 0, 0, 0, 0, 1, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 1 ]
[ 0, 0, 0, 0, 0, 0, 1, 0 ]

Now if the matrix-multiply our entire system matrix, sys, by our logic gate matrix, lgm, our result will be the effect of applying the CNOT gate to qubit[2] and qubit[0] where qubit[2] is the control qubit.


Why is the lower bound of element uniqueness in $\Omega(n\log n)$?

We assume the comparison model in the lower bound of the element uniqueness problem. That is, the key operations are to compare elements. In particular, hashing is not allowed.


Solve X(n) = 2X(n-1) + 2 recurrence relation

Your $Y_0$ is probably wrong. $Y_0$ must be equal to $X_0+2=0+2=2$. Then $Y_n=2^{n+1}$ and hence $X_n=2^{n+1}-2$. Please double check.


You can unite them exactly as said in the solution, "simply
add a new final state to the original automaton, add epsilon transitions from every old final state to the new final state, and change every old final state into a regular state."

Suppose $N$ is the original NFA at a final state $F$. Suppose it can go to one of states $E_1, \cdots, E_m$ without any input if there is an epsilon transition from $F$. Suppose on input symbols $s$, $N$ changes to one of states $S_1, \cdots, S_n$.

Let $N'$ with its unique final state $U$ be the new NFA as constructed above from $N$. When $N'$ is at its regular state $F$, what will happen?

It can stay at $F$ without further input.
It can go to any one of $E_1, \cdots, E_m$ as before because of the possible epsilon transition.
On input $s$, it will go to one of $S_1, \cdot, S_n$.
It can go to $U$ without any further input because of the epsilon transition from $F'$ to $U$.

Note that in case 2, 3 and 4 where $N$ has moved to state $s'\in\{E_1, \cdots, E_m, S_1, \cdots, S_n\}$, $N$ can move to another state without further input if there is epsilon transition from $s'$. Furthermore, $N$ can move to still another state without further input if there is still epsilon transition. And so on.

In particular, if $N'$ stays at $F$ on input $s$, it can go to $U$ without any further input.

Yes, an epsilon transition functions like teleporting magically.


(Minimum number of codewords) (Binary complete) Huffman code of maximal code length $n$ must have at least $n+1$ codewords.

The maximal code length of codewords $\{01, 10\}$ is 2. However, there are only two codewords. So those codewords is not a Huffman code.

(Exercise.) Prove the claim of the minimum number of codewords of Huffman code.


First, note that $M$ and $w$ in $M_2$ are fixed. So whatever is the input, $M$ always accepts or rejects $w$. Second, note that $M_2$ is not built to run.

Then:

You want to map $<M,w>$ to a regular language $L$ if and only if $M$ accepts $w$. Fix $L$, in that case you choose $\Sigma^*$. However, if $M$ rejects $w$ you don't want $L$ regular (otherwise $R$ will accepts), so you choose $L'\subset L$ such that $L' = \{0^n1^n\}$ which is not regular.

Now you have two cases:

1) if $M$ rejects $w$, then $M_2$ will accepts only the strings of the form $0^n1^n$, then $R$ will reject.

2) if $M$ accepts $w$, then $M_2$ will accepts all  the strings of the form $0^n1^n$ and all other strings in $\Sigma^*-0^n1^n$, so $R$ will accept.

However in poor words, it consists to map an "yes istance" of $<M,w>$ to a single "yes instance" of $L$. Let me do an example:

You want to prove that $L=\{M |\ if\ M\ accepts\ w\ then\ M\ accepts\ flip(w) \}$, where $flip(w)$ is the bitwise of all the string $w$ (For example if $w$ = $100$ then $flip(w) = 011$.), is undecidable with a reduction from $A_{tm}$.

Suppose $L$ is decidable, then exists a $TM$ $R$ that decides $L$. So we can build a new $TM$  $S$ that decides $A_{tm}$.

We will doing something like this:

  $S$ on input $<M,w>$: "build a new $TM$ where $M$ and $w$ are constants. Call it $N_{<M,w>}$, then run $R$ on input $N_{<M,w>}$ and do what $R$ does."

Inside $N_{<M,w>}$ we have our reduction.
Take in mind we want this:

  $M$ accepts $w$ if and only if $R$ accepts $L(N_{<M,w>})$

First, we fix $L(N_{<M,w>})$ = $\{100,011\}$ (This is just an "yes instance" of $L(N_{<M,w>})$

Now our $N_{<M,w>}$

  $N_{<M,w>}$ on input $x$:

  if $x$ = $100$ then accepts

  else if $x$=011 then run $M$ on $w$ and do what $M$ does.

Then "run" $R$ on $N_{<M,w>}$ and $S$ will accept if $R$ does:

if $M$ rejects $w$, the only string could be accepted by $N_{<M,w>}$ is $100$ then both $R$ and $S$ will reject.

Otherwise if $M$ accepts $w$, $N_{<M,w>}$ will accept both $100$ and $011$ then both $R$ and $S$ will accept.

So $S$ can decide $A_{TM}$ which is impossible, the "error" was to suppose the existance of $R$.


Is a graph of zero nodes/vertices connected?

These issues are discussed in the classical paper Is the null graph a pointless concept? by Harary and Read. The conclusion is that usually when we think of graphs, we don't think of them as having zero nodes. Definitions which are equivalent for non-empty graphs can differ on the null graph. Whenever we use null graphs we have to be very careful and choose our definitions according to usage.

Given a definition of connectedness, you can check whether the null graph satisfies it. For example, taking your definition (there is a path connecting any two vertices), the null graph is connected since this condition is satisfied vacuously.


Assignment Problem -- finding the $k$ agents with the best assignment

The assignment problem can be extended to solve this problem. The regular problem without the $k$ restriction can be solved by building a Minimum Cost Maximum Flow network is as follow:

We have a source $S$ a sink $T$ and the corresponding bipartite graph in the middle. Note that each edge has two values $f/c$ which denote maximum flow allowed through this edge and cost of each flow unit. Now, the problem is that we want to allow at most $k$ units of flow from $S$ to $T$. To do this, just duplicate node $S$ into $S_1$ and $S_2$ and put an edge among them such that cost of each unit is 0 (no penalty) and maximum flow allowed is $k$. The new graph will look like this:

The minimum cost maximum flow from $S_1$ to $T$ is the solution to the original problem for a fixed $k$.


Minimum number of exchanges needed to get all negative values left of all positive ones

You can keep a pointer to the currently first positive value in the list, which initializes to 0. Then scan through the list, when you see a negative value swap it with the positive value, and increment your pointer.

You get O(n) swaps in the worst case.

If the first half is positive and second half is negative, you have to have at least n/2 swaps, as the second half needs to swap places with the first half.

To actually get n/2 swaps, you can first count the # of positive values, and if the positive values are greater, iterate the list in reverse order, and keep a pointer first negative value in the list. You can then stop if you have swapped all the positive or negative values.


What does "cavallier extension claim" in The Algorithm Design Manual mean

The phrase means "cavalier" in the ordinary English sense of the word, i.e., it is talking about a claim in a proof that is made carelessly.  Without more context or examples I'm not sure exactly what pattern of flawed proof it is referring to, but it has something to do with making an assumption/claim (without justifying it) that the solution for $n+1$ is related to the solution for $n$ in a particular way.

"Cavallier extension claim" is not a technical phrase.  It's just some English that the author is using.


I don't believe there is a single word term for this. Edge count seems to be the closest thing to what you are after. Mathematically it can be expressed as E(g).

http://mathworld.wolfram.com/EdgeCount.html


There's a simple $O(N^3 \log N)$ algorithm, though you might be able to do much better. First, compute all $N^3$ quadruples, and the corresponding linear combinations $\sum_i c_i n_i$. Then sort them. Then find the location of the given quadruple. Then compute the running sum.


What does it mean if we disable K-rule in Agda?

Axiom K is related to "Uniqueness of Identity Proofs", which says is that any two proofs of equality are themselves equal to each other (i.e. are both Refl). Agda doesn't include K as an axiom, but it (and UIP) can be proved as a theorem using Agda's dependent pattern matching.

Axiom K is inconsistent with homotopy type theory, where the univalence axiom provides ways of constructing equalities other than refl. For example, if there are two functions that are pointwise equal, univalence asserts that there is an equality term equating them, but it cannot be refl if the functions have different implementations.

All removing K from Agda does is add restrictions to pattern matching, making fewer matches typecheck. The runtime semantics are unchanged, and no new programs typecheck.

For some excellent introductions on the subject, I recommend:

Pattern Matching without K

Unifiers as Equivalences

Both of these have more detailed versions in JFP if you have access to a subscription.


You have the basic intuition right.
The variable $[p,A,q]$ represents the set of (strings accepted by) computations from state $p$ to state $q$ that will pop the topmost symbol $A$ from the stack.

Technicaly the relation between grammar $G$ and pda $M$ is given on the top of the slide you show.
Then the construction follows recursion. If the pda pops $A$ but pushes $B_1B_2B3$ the grammar will replace the computation on $A$ starting in $p$ and ending in $q$ into three separate computations $[q_1,B_1,q_2][q_2,B_1,q_3][q_3,B_1,q]$. Here the intermediate states $q_2,q_3$ are unknown and are guessed by the grammar. Only $q_1$ is known, as it is the state where the pda instruction moves to.

Your observation is right. This standard construction might introduce triplets $[p,A,q]$ that will be useless. In your example there will be no computations from $q$ to $p$ so a triplet $[q,A,p]$ is never used in a succesful derivation. That is not problamatic. The construction just produces all possibilities, and variables that turn out to be useless can be removed afterwards if one really wants.
Note. The other question you link to uses a different Sipser style automaton model! There stack symbols are pushed one by one without popping at the same time. To add to the confusion the answer given at that question perfectly matches the construction from your slide!


Definitional equality of two propositions about propositional equality

Recall that (a few paragraphs above)

  two objects are definitionally equal if after certain computation steps they evaluate
  to identical results.

Assume throughout this post that $M$ and $N$ are definitionally equal. This means that there is a series of computation steps $M_0 \leftrightarrow M_1 \leftrightarrow \ldots \leftrightarrow M_n$ where I use $\leftrightarrow$ do denote a computation step, and $M_0$ is the term $M$ and $M_n$ is the term $N$.

Any computation step can be applied in any context. This is part of the definition of computation rules for calculi used in logic (as opposed to calculi used to model programming languages with side effects). So if you stick $M_0$ in some context $P$, there is a series of computation steps $P(M_0) \leftrightarrow P(M_1) \leftrightarrow \ldots \leftrightarrow P(M_n)$. This means that $P(M_0)$ and $P(M_n)$ are definitionally equal, i.e. $P(M)$ and $P(N)$ are definitionally equal.

Apply this to a property $P(X)$ that expresses “$M$ is propositionally equal to $X$”, no matter how this is expressed in a particular calculus. $P(M)$ is definitionally equal to $P(N)$, i.e. a property that expresses “$M$ is propositionally equal to $M$” is definitionally equal to “$M$ is propositionally equal to $N$”.

Strictly speaking, there isn't necessarily a single proposition stating that $M$ is propositionally equal to $N$ — there may be ways to state this that are not definitionally equal (it depends on the exact calculus. If a calculus has multiple ways to express this, there can be two (or more) non-definitionally-equal propositions stating that $M$ is equal to itself, and then there are also multiple non-definitionally-equal propositions stating that $M$ is equal to $N$. But for each proposition stating that $M$ is equal to itself, that proposition is definitionally equal to a proposition stating that $M$ is equal to $N$, by applying the computation steps that rewrite $M$ to $N$.

Reasoning about equality can be difficult to follow. We tend to have an intuition that equality is just equality, dammit. It's a bit difficult to internalize that there are different concepts of equality, and worse, they coexist in the same theory. I think it helps if you use words other than “equality”. If two terms are written exactly in the same way (as strings or at least as abstract syntax trees), they're identical. As long as you're not reasoning about variable binding, you can extend that to terms that are identical except for variable names, i.e. terms that are alpha-equivalent. Beyond that, don't use the word “equal”. If there's a series of computation steps that leads from $M$ to $N$, say that $M$ and $N$ are computationally equivalent or rewritable to each other. They're not necessarily “equal”, but they're equivalent for a certain equivalence relation. Then it's obvious and not particularly confusing that there can be coarser equivalences between terms. For example, there's an equivalence relation between terms defined by “if you replace $M$ by $N$ in a true proposition, you get a proposition that's still true”. This is a form of observational or extensional equivalence of propositions. It can be called “observational equality” or “propositional equality”, but to form an intuition, don't call it that. And then it's not so shocking that if $N$ can be rewritten to $M$, then any proposition stating that $M$ is whatever-equivalent to $N$ can be rewritten to a proposition that states that $M$ is equivalent to itself.


How to express taking the next bit of an infinite string in small-step semantics?

In general, the only persistent pieces information in a deduction rule (like the ones in the wikipedia article) are the variables which are shared between one of the premises and the conclusion of the rule.

So in effect, a findOne function that operates on a given (fixed) string and returns the position of the first bit which is one would have to pass the string to the conclusion of the rule. Thus one possible formulation would be

$$ \frac{\mathrm{findOne}(str)}{\mathrm{findAux}(str,0)}$$

where findAux is defined by

$$ \frac{\mathrm{findAux}(str, n)\quad \mathrm{nextBit}(str)=0}{\mathrm{findAux}(\mathrm{getTail}(str),n+1)}$$

$$ \frac{\mathrm{findAux}(str, n)\quad \mathrm{nextBit}(str)=1}{n}$$

And nextBit is defined by other rules. One often uses pattern notation instead, so if strings of bits are represented $1.0.0.1.1.0.0.1\ldots$ (so concatenation is "$.$"), the first rule would be

$$ \frac{\mathrm{findAux}(0.str, n)}{\mathrm{findAux}(str,n+1)}$$

Note that the free variables $str$ and $n$ are implicitly universally quantified, so the first rule reads

  For any value of $str$, the value of $\mathrm{findOne}(str)$ is the value of $\mathrm{findAux}(str, 0)$.

Having "side conditions" such as $str\in\{0,1\}^\omega$ can clarify, but is usually clear from the context. Note that the $str$ in the premisse and the conclusion are the same, by definition of what a deduction rule is.


Solving T(n)=T(n−1)+2T(n−2) using substitution

The secret of effective substitution is to find the magic numbers -1 and 2. Look and behold.

$$ T(n)+T(n-1)=2T(n-1)+2T(n-2)=2(T(n-1)+T(n-2))$$
Let $S(n)=T(n)-(-1)T(n-1)$. Then
$$S(n)=2S(n-1)=2^2S(n-2)=\cdots=2^{n-2}S(2)\tag{I}$$

$$ T(n)-2T(n-1)=-T(n-1)+2T(n-2)=-(T(n-1)-2T(n-2))$$
Let $R(n)=T(n)-2T(n-1)$. Then
$$R(n)=-R(n-1)=R(n-2)=\cdots=(-1)^nR(2)\tag{II}$$

Eliminating $T(n-1)$ from formula ($\text{I}$) and ($\text{II}$), we obtain $$T(n)= \frac{2S(n) + R(n)}3=\frac{2^{n-1}S(2) + (-1)^nR(2)}3=\frac{S(2)}62^n + O(1)$$

So, $T(n) = O(2^n)$.

It is assumed in the above that S(2) and R(2) are defined or, what is equivalent, T(2) and T(1) are defined. Their actual values do not affect the conclusion.

In fact, we can be more precise. If $T(2)+T(n-1)>0$, i.e., $S(2) > 0$, we will have $T(n)=\Theta(2^n)$. If $T(2)+T(n-1)=0$, we will have $T(n)=O(1)$. If $T(2)+T(n-1)<0$, we will have $-T(n)=\Theta(2^n)$.

How to find those two magic numbers?

Consider T(n) as $x^2$, T(n-1) as $x$ and T(n-2) as 1. Then you get $x^2 = x + 2$. Solving that equation, you get $x=-1$ or $x=2$.

(Exercise.) Let $F(n)=F(n-1)+F(n-2)$ for $n\in\Bbb N$, $n\ge2$. Show $F(n)= O(\alpha^n)$, where $\alpha = \frac{1+\sqrt 5}2$.


Rigorous proof against pseudorandom generator

Your definition of pseudorandomness is misleading. A better definition would start with a function with "expansion", and then state then it is indistinguishable from random. In your case, the function is "expanding" since it takes $n$ bits and outputs $n+1$ bits. However, the $n+1$ bits it produces don't look random. Can you tell why?


Proving that a context-free grammar is unambiguous

Consider the word $abab$. It has two derivation trees (rendered using syntree):

Hence your grammar is ambiguous. In order to make an unambiguous grammar, we have to force the parse to be unique. We identify the word with a path in which $a$ corresponds to $\nearrow$ and $b$ to $\searrow$. We're looking for a non-empty path that ends at level ground.

If the path starts with $\nearrow$, then we can look at the first time at which it returns to level ground, and decompose the path accordingly: $\nearrow x \searrow y$, where $x$ is a path that never goes below level ground, and $y$ is an arbitrary path that ends at level ground. Hence we need a way to capture paths that end at level ground and never go below level ground. Such a path can also be decomposed uniquely as $\nearrow x \searrow y$, where this time both $x$ and $y$ never go below level ground.

The considerations above lead to the following unambiguous grammar:
$$
\begin{align*}
&S \to aAbS' \mid bBaS' \\
&S' \to aAbS' \mid bBaS' \mid \lambda \\
&A \to aAbA \mid \lambda \\
&B \to bBaB \mid \lambda
\end{align*}
$$

As a somewhat degenerate example, the derivation tree for $abab$ is:

The proof that this grammar is unambiguous goes along the description above, though the formal proof by induction is somewhat challenging.


Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$

You can reduce your $N \lceil \log_2 M \rceil$ bits to $\lceil N \log_2 M\rceil$ by using Dodis et al's "Changing Base without Losing Space".

I don't think you're going to get much smaller than $N \log_2 M$ bits. For $N \gg M$, many functions will be surjective. In particular, there are $\{{N \atop M}\}$ surjective functions, which is at least $M^{N-M}$.
Thus, at least $\log_2 \left(M^{N-M}\right) = N \log_2 M - M \log_2 M \in \Omega(N \log_2 M)$ bits must be used to represent one, on average.


What algorithm would compute the maximum choices from two sets?

Hint: Use dynamic programming. For each $z,l$, compute the optimal way to insert $z$ zeroes to the prefix of length $l$ of the smaller array.


How to prove the structured program theorem?

The Böhm-Jacopini theorem essentially says that a program based on 'goto' is functionality equivalent to one consisting of 'while' and 'if'.

Sketch of proof based on the following lecture notes:

Say you have a program that consists of a sequence of statements $S_i$; prefix each statement with a label $S_i^{\prime} \gets L_i: S_i$ and update existing goto statements to point to the right locations. Declare a location variable, $l \gets 1$, and wrap the prefixed statements in a while loop that will continue until the last statement is reached, $\textbf{while} (l \neq M) \ \textbf{do} \ S^{\prime}$.

Apply the following rewrite rules to $S^{\prime}$:

Goto rule: Replace $L_i \ \textbf{goto} \ L_j$ with $\textbf{if} \ (l = i) \ \textbf{then} \ l \gets j$
If-goto rule: Replace $L_i : \textbf{if} \ \text{(cond)} \ \textbf{then} \ \textbf{goto} \ L_j$ with $\textbf{if} \ (l = i \land \text{(cond)}) \ \textbf{then} \ l \gets j \ \textbf{else} \ l \gets l + 1$
Otherwise rule: Replace $L_i : S_i$ with $\textbf{if} \ l = i \ \textbf{then} \ S_i,  \quad l \gets l + 1$

The resulting program is then free of goto statements showing the correspondence between the two paradigms.

A more formal proof is provided in your second reference.

Update

After studying the paper in greater detail, this is my interpretation:

Based on the definitions in CACM, let $\mathcal{B}^{\prime} = \mathcal{D}(\alpha, \lbrace \lambda, R \rbrace)$ be the class of Turing machines represented by the language $\mathcal{P}^{\prime}$ that covers flow diagrams. Let $\mathcal{B}^{\prime \prime} = \mathcal{E}(\alpha, \lbrace \lambda, R \rbrace)$ be the class of Turing machines represented by the language $\mathcal{P}^{\prime \prime}$ that covers the transformation covered above.

According to CACM, the author wants to prove that if a Turing machine exists in the family of Turing machines described by $M \in \mathcal{B}^{\prime}$, then there exists a corresponding Turing machine in the family of Turing machines described by $M^{*} \in \mathcal{B}^{\prime \prime}$.

Sketch of the author's proof: He does this by drawing from the derived relationship $M \in \mathcal{B}^{\prime}$ and $M \in \mathcal{E}(\cdots)$ (definition (5)) and then sets up the relationship $M^{*} \in \mathcal{E}^{*}(\cdots)$. For each component of $\mathcal{E}(\cdots)$ he draws a one-to-one mapping with those of $\mathcal{E}^*(\cdots)$. Thus by establishing the bridge between $M$ and $M^{*}$ through $\mathcal{E}(\cdots)$ the author proves $M \in \mathcal{B}^{\prime} \implies M^{*} \in \mathcal{B}^{\prime\prime}$.


How to prove the emptiness of intersection of two context free languages is undecidable?

A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.

The following is a proof taken from this note by Rob van Glabbeek.

Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.

Proof: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem.
Given a set $d_1,\cdots,d_n$ of dominos where, for $i=1,\cdots,n$, the top string of $d_i$ is $w_i$ and the bottom string of $d_i = x_i$. Consider the context-free grammars

$$W\to w_1Wd_1\mid w_2Wd_2\mid\cdots\mid w_nWd_n\mid w_1d_1\mid w_2d_2\mid\cdots\mid w_nd_n$$
and
$$X\to x_1Xd_1\mid x_2Xd_2\mid\cdots\mid x_nXd_n\mid x_1d_1\mid x_2d_2\mid\cdots\mid x_nd_n.$$

Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.


Solving Subproblem in Logic (first-order, propositional, pddl)

In general, using mathematical induction to prove theorems automatically is quite difficult. First, note that this isn't really a problem of first-order vs second-order logic, since induction can easily be expressed as a schema in FOL, and generally be reduced to a finite set of axioms. It's more useful though to keep it as a schema, and add induction as a logical rule rather than a list of axioms.

This has been studied quite a bit, but success of general purpose automatic theorem provers is somewhat limitied in the presence of induction, for the following reasons:

(Of course) the first order (quantifier free) theory with induction is undecidable. A good milestone of how undecidable a theory is is to measure how expressive the resulting theory is, and the theory with induction is essentially capable of expressing a large part of elementary mathematics quite easily. This is a pretty bad sign.
Induction is always applicable: any goal which contains some occurrence of an inductive data type (like a list or a natural number) may be proven (indeed, may need to be proven) by induction. Clearly there needs to be a clever heuristic to decide when to apply induction. The general rule is: do everything but induction, and apply induction as an absolute last resort! Even with this heuristic, you need to know when to give up, which is again undecidable, but necessary if any kind of backtracking is to be performed.
Sometimes the goal needs to be generalized. This is a distinctive phenomenon of induction, that sometimes the induction hypothesis is too weak to prove the conclusion, and as a result the whole goal needs to be strengthened, which is rather counter-intuitive (failure to prove a goal results in trying to prove a stronger one!). Finding and proving these strengthenings automatically is the subject of exciting current research in computer science (in the field of loop invariant synthesis).

Given all these difficulties, it's clear there's no general purpose algorithm for proving theorems by induction in full generality. However the problem itself is being actively studied, and I'll just leave you with this link to a workshop specifically addressing this problem.

As a footnote, your problem doesn't seem to be solvable with much else than standard "brute force" (or resolution), since the algorithm needs to verify that the last step is reachable by explicitly going through all the steps. Unless you have further knowledge (e.g. each step corresponds to a natural number), you need to verify that each step can be taken, and that there are no "breaks".


Proof that L(M) = {accepts the string 1100 } is undecidable

The usual reduction from the halting problem: for example, the same reduction that shows the zero-input halting problem to be undecidable.

   Suppose you can determine whether a machine $M$ accepts some magic string (such as $1100$).  You can then decide whether an arbitrary machine $M$ halts when given input $x$ as follows. Produce a machine $M_x$ that ignores its input and simulates $M$ running on input $x$. If $M$ halts, $M_x$ accepts whatever input it was given; otherwise, $M$ doesn't halt so nor does the simulation $M_x$. So $M_x$ accepts the magic string if, and only if, $M$ halts on input $x$. Hence, if you could decide whether a machine accepts the magic string, you could decide the halting problem.


How to evaluate the learned prototypes for multivariate time-series (e.g. motion)?

You note " but with more than one prototype per class/cluster."

We often call this a polymorphic class. Consider the analogue in text..

C1 = { dpacekfjklwalkflwalkklpacedalyutekwalksfj}
 C2 = { jhjhleapashljumpokdjklleaphfleapfjjumpacgd}

Here the class 1 prototypes are polymorphic {walk OR pace}, and so is class 2 {leap or jump}.

You can learn these prototypes with a dictionary building method, and "measure their quality in a numerical way" with just classic accuracy (or precision recall etc).

Using nearest neighbor, the distance between and unknown item, say 'balk' is just defined as:

dist('balk', C1) = min(dist('balk','walk'),dist('balk','pace'))
and
dist('balk', C2) = min(dist('balk','leap'),dist('balk','jump'))

Paper [a] explains one nice dictionary building method, but there are other ways.

[a] http://www.cs.ucr.edu/~eamonn/SDM_RealisticTSClassifcation_cameraReady.pdf


Is this a Fixed Parameter Tractable algorithm?

First and foremost, I would advise having another look at the basic definitions. An FPT instance is identified by a string $x$ and an integer $k$ such that $(x, k)$ is a yes-instance.

Put briefly, if $f(k)$ is not polynomial in terms of $n$ and still depends on $n$, then you cannot obtain an FPT algorithm. We require that $k$ is fixed, or independent of $n$, and thus $f(k)$ is always independent of $n$. However, if $f(k) = n^{O(1)}$, then our FPT algorithm is in fact a polynomial time algorithm. Hence, if $f(k) = O(2^n)$, the answer is definitely no.


Upper bounds for $NP$ based on $NEXP = EXP$

If someone has demonstrated that $EXP=NEXP\implies NP\subseteq SUBEXP$, then that guy has unconditionally proved a long-sought separation $P^{NP}\subsetneq NEXP$.

Proof: If $EXP\neq NEXP$, then obviously, $P^{NP}\neq NEXP$.

So assuming $EXP=NEXP$, the above statement gives us $NP\subseteq SUBEXP$. We have:

$$P^{SUBEXP}=SUBEXP$$

So, $P^{NP}\subseteq SUBEXP\subsetneq EXP$.$\blacksquare$


How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way?

Both (1) and (2) are possible.  (It's also possible to have a combination of them.)  It doesn't really matter which holds; either way, that means that $f$ is not one-way.

You say (2) is false because of the preceding discussion, but I'm not exactly sure why you think it is false.   One-wayness is not a property of a specific value of $x$; rather, it is a property of a function $f$.  And, just because a function $f$ is not one-way doesn't mean it can be inverted for every possible output.  If $f$ can be inverted on a significant fraction of outputs, it is not one-way.  If $f$ can be inverted on all outputs, with a significant probability, it is not one-way.

Perhaps the confusion comes from a misunderstanding about what the definition of a one-way function is.  The definition you quote at the beginning is not the definition of a one-way function.  Rather, it's the definition of a hardcore bit.

The part you quoted appears to claim/imply that it is the definition of a one-way function with hardcore bit (which is not the same as the definition of a one-way function).  That claim/implication is not correct.  The precise statement is that this is the definition of a function with hardcore bit.  This definition implies nothing about onewayness.  So why did they call it the definition of a one-way function with hardcore bit? I don't know; you'd have to ask the author. But my guess is that this definition is normally only used with functions you already know to be one-way, so there's an implicit assumption that $f$ is already known to be one-way, and given such an $f$, the definition is describing what it means for $b$ to be hardcore for $f$.

You say "suppose $f$ isn't one-way, then this expectation will be noticeably different from 1/2".  That actually doesn't follow.  You can have a function $f$ that isn't one-way but does have a hardcore bit.  Then the expectation will not be noticeably different from 1/2.  E.g., consider the function $f$ given by $f(x)=0$: it's not one-way, but it does have a hardcore bit, and the expectation is exactly 1/2.

It sounds like you want to understand one-wayness.  If so, hardcore bits are a distraction.  You should be looking for the definition of a one-way function and trying to understand that, not looking at the definition of a hardcore bit.


Optimality in multi-agent multi-target path finding

Read the following paper on the generalization of your problem with "makespan" as the objective. The proposed algorithm should work even if $m\neq n$.

H. Ma and S. Koenig. "Optimal Target Assignment and Path Finding for Teams of Agents." http://idm-lab.org/bib/abstracts/papers/aamas16a.pdf


Is it reasonable to consider a book's table of contents as a hierarchical collection? if yes, what does the root node represent?

The root node is the entire book.
Its children are chapters.
Their children are sections. And so on.

This is reflected in the standard numbering system, in which chapters are labeled by numbers, sections are labeled by numbers within chapters, and so on.

As an example, we can take the table of contents of the book you mention. The root has 15 children: an introduction, 12 chapters, an appendix, and the index. The first child (introduction) is a leaf. The second child has 9 children, which are the various sections: basic program elements, control statements, and so on. The first child (basic program elements) has 19 children, all leaves: programs and modules, an example python program, and so on.


Time complexity in Big O notation for Harmonic series with first k terms missing

We can estimate your sum using an integral:
$$ \int_k^{n+1} \frac{dx}{x} \leq \sum_{i=k}^n \frac{1}{i} \leq \int_{k-1}^n \frac{dx}{x}. $$
Evaluating the integrals, we obtain
$$ \log \frac{n+1}{k} \leq \sum_{i=k}^n \frac{1}{i} \leq \log \frac{n}{k-1}. $$
We can conclude that for $k \geq 2$,
$$ \sum_{i=k}^n \frac{1}{i} = \log \frac{n}{k} \pm O(1). $$


Non-Parametric Methods Like K-Nearest-Neighbours in High Dimensional Feature Space

This problem is known as the curse of dimensionality. Basically, as you increase the number of dimensions, $d$, points in the space generally tend to become far from all other points. This makes partitioning the space (such as is necessary for classification or clustering) very difficult.

You can see this for yourself very easily. I generated $50$ random $d$-dimensional points in the unit hypercube at 20 evenly selected values of $d$ from $1..1000$. For each value of $d$ I computed the distance from the first point to all others and took the average of these distances. Plotting this, we can see that average distance is increasing with dimensionality even though the space in which we are generating the points in each dimension remains the same.

Average distance vs. dimensionality


Is there an abstract machine that can capture power consumption?

There isn't an established model yet, but this is an area of active research right now. One of the experts on the algorithms side of things is Kirk Pruhs. His papers have more information, and you can also browse this presentation.


Regular language where syntactic right congruence and syntactic congruence differ

Definition: An equivalence relation $\sim$ on $\Sigma^*$ is a right (left) congruence if $x\sim y$ implies $xv\sim yv$ (respectively $vx\sim vy$) for every $x, y, v \in\Sigma^*$.
Definition: Given a language $L$ over an alphabet $\Sigma$, the canonical right congruence $\sim_L$ is defined by $x\sim_L y$ if and only if for all $z\in\Sigma^*$ we have $xz\in L\iff yz\in L$. Similarly, for the canonical left congruence $x{}_{L}\sim y$ if for all $z\in\Sigma^*$ we have that $zx\in L\iff zy\in L$.
Example: Consider the (regular) language $L=\{ab,abb\}$ over $\Sigma^*$. For this language, the relations $\sim_L$ and ${}_L\sim$ are not the same.
In fact, according to ${}_L\sim$ the words $x=ab$ and $y=abb$ are in the same class. This is because if we prepend any $z\in\Sigma^*$ to $x$ and $y$, both word $zx$ and $zy$ are in $L$ or not simultaneously. In fact, for $z=\epsilon$ both $zx=\epsilon ab=ab$ and $zy=\epsilon abb=abb$ are in $L$. However, when $z\neq \epsilon$, then both $zx$ and $zy$ are not in $L$. Therefore $ab{}_L\sim abb$.
Now, when we consider the relation $\sim_L$, we have that $ab\not\sim_L abb$. In fact, if we take $z=b$ we get that $xz=abb\in L$ but $yz=abbb\not\in L$.
So, the regular language $L$ is an example for which its left and right canonical congruences are not the same relation.


What is the global function we are trying to Optimise with Clustering Algorithms?

About your first, general question: generally, the cost function we want to optimize in clustering algorithms is double: we want to both minimize intra-class variance while maximizing extra-class variance. Replace class by cluster and you understand easily what it means: inside a cluster, we want the elements to be as similar as possible, while elements between different clusters must be as dissimilar as possible. The basic idea is very simple and natural.

Different algorithms will only tweak the way they measure this intra-class similarity and the extra-class dissimilarity, usually in the goal to optimize for a particular kind of dataset with known properties.

About the second, more specific question: I did not read those papers, but from a first look, it seems gchen is using L1-norm (absolute value measure) while gmine is using L2-norm (euclidian measure). gahmadfard seems to only be the L2-norm plus feature scaling or some kind of tf-idf (anyway what is certain is that they are pondering the similarity measure with the number of elements in the group, but I don't know for what purpose).

I can't advise when to use which clustering algorithm, you should read the intro of the papers or find a survey, but usually the best way to find the best clustering algorithm for you is to try several on your dataset and manually select which one fits the best your purpose (since there's no objective way to find which clustering is the best, it all depends on your subjective needs, after all, clustering algorithms belong to the class of unsupervised learning).


What does Tarski's Fixed-Point theorem give us that that Y-Combinator does't

If by Tarski's fix point theorem you mean the Knaster–Tarski fixpoint theorem, then it's widely applicable and very general. All you need is a complete lattice and a monotone function on the lattice.  There are many rather different examples of those.
Tarski-Knaster is for example used in the coinductive definition of bisimilarity. Another application is to construct models of logical formulae (e.g. for logics with fixpoints, such as
the modal $\mu$-calculus and the various fixpoint logics that are used to characterise complexity classes). It is also used in set theory and in program analysis.

The Y-combinator on the other hand is a specific piece of syntax in the $\lambda$-calculus. You don't need to prove the existence of the Y-combinator.


Is there any example of automatas (or similar) systems that emerge complex internal structures on its own?

It seems very hard to define the phrase "internal structures that defend their own existences" in a rigorous or precise way, so it is not clear that the question is well-defined.  However, some very simple systems can admit behavior that might be described in these terms.

For instance, consider Conway's game of life.  It is known to allow for replicators: i.e., there are self-replicating patterns which create a complete copy of themselves.  Replication can be thought of as a "strategy" for "defending your own existence"; if you spawn many copies of yourself, then even if someone messes up one of the copies, the other copies will still exist.

So, to the extent that the phrase "internal structures that defend their own existence" is well-defined, self-replicators in Conway's game of life might be considered a form of internal structure that will defend its own existence.

Conway's game of life is very simple.  Another very simple example is Rule 110, which is an extremely simple cellular automaton.  It is known that Rule 110 is Turing complete, which means that it is possible to simulate Conway's game of life in a Rule 110 cellular automaton, which means that a Rule 110 cellular automaton can be argued to allow for "internal structures that defend their own existence".  It's probably going to be hard to find a system that's much simpler than a Rule 110 cellular automaton.

In general, we should probably be careful about anthromorphicizing the behavior of computational systems like this.  Just because they behave in ways that resemble the behavior of people or animals doesn't necessarily mean it's necessarily going to be super-meaningful to describe them as acting with a 'purpose' (like self-defense).  Ascribing human motivations or emotions to them runs the risk of misleading our intuition.


How to group intervals which overlap by some amount?

Here is one interpretation of your problem:

Given $n$ observed intervals $I_1,\dots,I_n$ and $k$, find $k$ disjoint inferred intervals $J_1,\dots,J_k$ that maximizes the number of observed intervals are covered by at least one of the inferred intervals.  Say that $I_i$ is covered by $J_j$ if they have at least 95% overlap, where the overlap between $I_i,J_j$ is measured as $|I_i \cap J_j|/|J_j|$ where $|\cdot|$ denotes the length of an interval.

This problem can be solved with dynamic programming.  Sort the endpoints of the observed intervals.  For each endpoint $e$ and each $k_0$ with $0 \le k_0 \le k$, let $f(e,k_0)$ denote the maximum number of observed intervals that can be covered by $k_0$ disjoint inferred intervals that are all in $[-\infty,e]$.  Then you can write a recurrence relation for $f$: in particular,
$$f(e',k_0) = \max(f(e^*,k_0), \max \{f(e,k_0-1) + \eta : e<e'\})$$
where $e^*$ is the endpoint immediately before $e$, and $\eta$ is the number of observed intervals that are covered by $[e+1,e']$.

That said, I suspect a more pragmatic approach might be to use some standard clustering algorithm, adapted for this problem.  For instance, you might use k-means on the centers of the intervals.  Given a set of intervals that have been clustered together, you might use the median of their left endpoints and median of their right endpoints to define a new interval that serves as the clusterhead.  You can probably come up with other heuristics.  It's plausible that this might be adequate in practice.


What language does this deterministic finite automaton accept?

$(a^+b \mid b^+a)^*$. I am not sure there is a "simple" description of your language in plain English, but directly from the regex you get that it is the language that has the empty string and all strings that can be partitioned in such a way that each part is either multiple $a$'s (at least one) followed by one $b$, or vice versa.
In my opinion the regex and the automaton describe the language better than a "natural language description" in this case.


Well, you could just implement a counter.  I'll assume that the tape alphabet is $\{0,1,\#\}$.

First, scan to the end of the input, and write $\#0$ to the tape after the last character. The string of zeroes and ones after the $\#$ will be a binary counter.

Second, convince yourself that a Turing machine can add one to a number in binary.

Third, peform the following until you run out of input.  Scan back to the first $1$ on the tape, replace it with a $\#$, scan back to the counter and add one to it.

Finally, when you've run out of input, check that the value of the counter is a number of the required type. For example, it has the value $2^k$ for some $k$ precisely if it matches the regular expression $10^*$. For $3^k$, you can either convince yourself that Turing machines can divide a binary number by $3$ or – easier! – keep your counter in ternary instead of binary.


If the hash function takes the whole string into account, then the hash calculation takes $\Omega(k)$ time where $k$ is the length of the string. So the hash table lookup takes $\Omega(k)$ time.

The hash table lookup takes $\Theta(k)$ time if the hash calculation is done in linear time in the length of its input, which is typical for hash functions, and the lookup of the value takes $O(k)$ time. That part is usually not the case. With a typical hash table, looking up the bucket for the hash value in the table takes constant time $O(1)$ with respect to the length of the string $k$ and the size of the hash table $n$. But that's not the end of the lookup.

If the bucket is empty, the value is absent and the lookup ends there, having consumed $\Theta(k)$ time. If the bucket contains a value, you need to be compare it with the string that you're looking up, and that takes $O(k)$ time. If the value in the bucket is equal to the value that you're looking up, the lookup ends there, having consumed $\Theta(k)$ time. But what if the value is different? What happens next depends on the variant of the hash table data structure.

In a variant where collisions are handled by growing the hash table until there are no more collisions, the lookup ends here and the cost of the lookup is indeed $\Theta(k)$. This variant has efficient lookup, but pays for it by making addition potentially very expensive (depending on the growing strategy when a collision happens).
In a variant where collisions are handled by putting the value in the next bucket (for some traversal strategy), the search can potentially cover the whole table, with one string comparison for each bucket. The worst-case cost of each string comparison is $\Theta(k)$ (with a typical string comparison algorithm, the worst case is reached if the strings have the same length and differ towards the end). In the worst case, the total cost of the search is therefore $O(k \cdot n)$.
In a variant where collisions are handled by storing values that land in the same bucket in a secondary lookup structure (such as a list, a hash table with a different hash function, or a search tree), the cost depends on what the secondary data structure is. It's unlikely to be $O(1)$ with respect to the number of values in the bucket, so the worst-case cost of the lookup is not $O(k)$.

Hash tables only have constant-time operations in the average case with some “reasonable” (or not) hypotheses over the data, not in the worst case. See also (When) is hash table lookup O(1)?


Regular expression for words longer than 2 containing at most two x-s

Your regular expression accepts the word $xxxy$, which contains too many $x$s.
We can break down words in your language into three different kinds:

No $x$s, and so at least three many $y$s.
One $x$. In that case, the word is of the form $y^ixy^j$, with $i+j \geq 2$. This means that either $i = 0$ and $j \geq 2$, or $i = 1$ and $j \geq 1$, or $i \geq 2$.
0 Two $x$s. In that case, the word is of the form $y^ixy^jxy^k$, with $i+j+k \geq 1$. This means that either $i=j=0$ and $k \geq 1$, or $i=0$ and $j \geq 1$, or $i \geq 1$.

Putting everything together, we reach
$$
yyy^+ + xyy^+ + yxy^+ + yy^+xy^* + xxy^+ + xy^+xy^* + y^+xy^*xy^*.
$$
As a bonus, this regular expression is "unambiguous", in the sense that each word belongs to exactly one summand.
We can shorten this expression in many ways. For example, notice that if we consider only words with exactly two $x$s, we can obtain all words in the language by optionally replacing an $x$ with a $y$. This gives us the simpler expression
$$
(x+y)^2y^+ + (x+y)y^+(x+y)y^* + y^+(x+y)y^*(x+y)y^*.
$$
If we want something more symmetric, we can take
$$
y^+(x+y)y^*(x+y)y^* + y^*(x+y)y^+(x+y)y^* + y^*(x+y)y^*(x+y)y^+.
$$


Construct a new graph whose vertex set is the strongly connected components. Now go over all edge in the original graph, and if they connect two different strongly connected components, add the corresponding edge to the new graph if it's not already there.


Is the set of all possible finite alphabets uncountable?

Your approach can essentially be summarized as:

I define an injection between $\mathbb{N}$ and my set $S$.
This injection is not a bijection because some elements of the codomain are left unmapped.
Therefore there exists no bijection between $\mathbb{N}$ and $S$.

Stated like this, it is perhaps clear that the last statement does not follow from the others. An example of where this reasoning would fail is if we let $S = \mathbb{Z}$ and let the injection be the identity function (mapping naturals to themselves). This leaves all the negative integers in the codomain unmapped, but we know that $\mathbb{Z}$ is countable.


Only in one direction. As $\mathsf{P}=\text{co-}\mathsf{P}$, if $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ then we would know that $\mathsf{P}\neq\mathsf{NP}$. However the reverse implication doesn't hold. If $\mathsf{P}\neq\mathsf{NP}$ then it's possible that either $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ or $\mathsf{NP}=\text{co-}\mathsf{NP}$.


Lower bound on algorithm solving certain recurrence

There's quite a lot of confusion here:

$\Omega(n)$ and $\Omega(n-1)$ are absolutely the same.
You don't an adversary argument to show that this algorithm runs in $\Theta(n)$. It follows immediately from the description of the argument.
There is a difference between analyzing the running time of a particular algorithm and showing that every algorithm that correctly solves a problem must run in at least so many steps.

In order to show that any algorithm computing $F_n$ correctly must run in time $\Omega(n)$, we will show that any such algorithm must read all inputs $p_1,\ldots,p_n$. The starting point is the following observation:

The correct output is different for the instances $p_1=\cdots=p_n=0$ and $p_1=\cdots=p_{i-1}=0,p_i=1,p_{i+1}=\cdots=p_n=0$.

Given that, we can use a simple adversary argument to show that any algorithm correctly computing the function must read all $p_j$. Indeed, run the given algorithm, answering $0$ whenever it queries the value of some $p_j$. If it announces the answer without querying, say, $p_i$, then it cannot tell apart the two instances above, and in particular, its answer will be wrong on at least one of them.


In-place matrix transposition using rotations

After the array is rotated with dst == N - 1 (so the condition (dst + 1) % N == 0 is about to fire), the tail of the array starting from index N looks like a representation of a N×(M-1) matrix with the values of the original matrix without the first column:

11 21 31 12 13 14 15 22 23 24 25 32 33 34 35
         ^ starting from here

looks like a representation of the

12 13 14 15
22 23 24 25
32 33 34 35

matrix

which immediately suggests how to simplify the algorithm:

template<typename T>
void inplace_transpose_using_rotations(T* matrix, int N, int M)
{
    if (N == 1 || M == 1)
        return;

    for (int dst = 1; dst != N; dst++)
        std::rotate(matrix + dst, matrix + dst * M, matrix + dst * M + 1);

    inplace_transpose_using_rotations(matrix + N, N, M - 1);
}

This explains how the algorithm works: rotations move first elements of each row into their proper position in the transposed matrix and at the same time shift the other elements to the right forming a representation of a smaller N×(M-1) matrix in the right side of the array. Then this smaller matrix is transposed, until we get a N×1 matrix.


The common usage is for KB, MB, GB, TB, and so on to denote powers of 2 rather than powers of 10. There are ways to denote powers of 10, but they are infrequently used. See for example the Wikipedia page on kibibyte.


The catch is that $D_0$ is only a partial recursive function and it may not be possible to verify that $D_0(\alpha) = x$ in finite time. There is no way around that because $D_0$ must be universal, and there is no way a machine implementing it would halt on every input, because not every Turing machine halts on every input.


Does a Turing machine really need an infinite tape

The answer to your alternative question is "yes". A Turing machine that halts, halts in a finite number of steps, and it can only move the head a finite distance from the starting position in a finite number of steps.

However, a Turing machine need not halt and may use up an ever growing number of tape positions as it executes. Further, we cannot in general tell how much tape a Turing machine will need to execute correctly.

Sometimes people speak of needing an "unbounded" or "ever extendable" tape rather than an "infinite" tape. About the only significance to this difference in wording is that the former wording makes it a bit clearer that the notion of a Turing machine should not be problematic to a finitist (though perhaps still for an ultrafinitist).


Time complexity of a language whose alphabet has a single symbol

The language $\{a^n : \text{ the $n$th Turing machine halts on the empty string} \}$ is undecidable.

In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.


How do I arrive at the multiplication function in lambda calculus?

You know that $(\bar{n}\ s)$ corresponds to $s^{(n)}$, i.e. function $s$ applied $n$ times to its argument. You want to obtain a function that iterates some function $s$ exactly $n \cdot m$ times. From the above observations and some simple rules for the composition of functions we can immediately derive the body of $\textsf{mult}$:

$$s ^ {(n \cdot m)} =
\left( s ^ {(m)} \right) ^ {(n)} =
\bar{n} \left(s ^ {(m)} \right) =
\bar{n}\ (\bar{m}\ s)
$$

Hence

$$ \textsf{mult}\ :=\ \overbrace{\lambda n m.}^\text{  parameters}\underbrace{(\lambda sz.n\ (m\ s) z)}_{\text{Church numeral}}$$

or, if we $\eta$-contract, we get

$$ \textsf{mult}\ :=\ \lambda nms.n\ (m\ s)$$


Complexity of Hamilton path in directed complete bipartite graphs

These problems can be solved efficiently.

For Problem 2, both [1] and [2] prove that the problem is solvable in $O(n^{2.5} / \log n)$ time. That is, this is the variant of Hamiltonian path with specific start and end vertices.

For Problem 1, i.e., when the input graph is a semicomplete bipartite digraph, it appears (see [3]) that a Hamiltonian path is found in polynomial-time via bipartite matching.

There's a good amount of research on these type of problems on tournaments and other digraphs. You will find more general results by looking at papers that cite the ones I mentioned.

[1]  J. Bang-Jensen, Y. Manoussakis, Weakly hamiltonian-connected vertices in bipartite tournaments, J. Combin. Theory B 63 (1995) 261–280.

[2] J. Bang-Jensen, G. Gutin, J. Huang, Weekly hamiltonian-connected ordinary multipartite tournaments, Discrete Math. 138 (1995) 63–74.

[3] J. Bang-Jensen, M. El Haddad, Y. Manoussakis, T. Przytycka, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, Algorithmica 17 (1997) 67–87.


How to identify statistically distinct features of different sets?

This looks like a standard machine learning problem.  You could use any machine learning technique.  You might start with Naive Bayes.

If you want to evaluate a single feature, you could use information gain or BIC.

For the combination of all features, you can use a machine learning algorithm.  As I mentioned, I would suggest trying Naive Bayes first.  If you need something more powerful, there are many other classifiers: random forests, SVM's, k-nearest neighbors.  Read a textbook on machine learning to learn more about the subject.


Does $\mathsf{NSPACE}( f (n)) = \mathsf{coNSPACE}( f (n))$ hold for $ f(n) < \log (n) $?

Immerman–Szelepcsényi theorem  works under logarithmic reductions. Sublogarithmic space classes have different reductions. The TMs working within sublogarithmic space cannot even record the the length of the input. It has been shown that the space hierarchy for any sublogarithmic bound in Ω(log log n)-- o(log n) is inﬁnite. You can find it in following references:

V. Geffert. Sublogarithmic σ2-space is not closed under complement and other separation
results. Theoretical Informatics and Applications, 27:349–366, 1993.

M. Liśkiewicz and R. Reischuk. Separating the lower levels of the sublogarithmic space
hierarchy. In Proceedings of the Symposium on Theoretical Aspects of Computer Science,
pages 6–27, 1993.

B. von Braunmuhl "Alternation for two-way machines with sublogarithmic space". In Proceedings of the Symposium on Theoretical Aspects of Computer Science, pages 5–15, 1993.

The paper The complexity world below logarithmic space by M. Liśkiewicz and R. Reischuk contains an excellent wrap up of the sublogarithmic space.


Discrete fourier transform of a polynomial whose degree is not a power of 2

There are FFT algorithms for prime sizes such as Rader's algorithm. Given a factorization of $n$ as a product of (not necessarily different) primes, you can compute the DFT by running Rader's algorithm for each prime, in the same way that the usual FFT works by in effect computing FFTs of size $2$. You can read the details in a paper by Frigo and Johnson which describes the FFTW library, which computes length $n$ DFTs in $O(n\log n)$ for all $n$. You can also just use the library if all you really need to do is compute FFTs (rather than solve some programming exercise in some course).


This language is not CFL.

Consider the language $L \cap a^*b^*c^*$ . Assume that $L$ is CFL, now, as $ a^*b^*c^*$ is regular and CFL are closed under intersection with regular languages, $L \cap a^*b^*c^*$ would be CFL. But $L \cap a^*b^*c^* = a^nb^nc^{2n}$, which is not context free (The proof is similar to this). Hence the contradiction!

Thus the given language is not CFL.


Can a trend of android phones slowing down after 2-3 years of usage be attributed to the low durability of RISC CPU used in them?

Android phones slow down because the software applications are rapidly changing. More features get added, and this makes the software consume more memory (RAM) and CPU time. Software keeps getting updated and each update results in it requiring more resources. In response to this, smartphone manufactures have increased the capabilities of the hardware they manufacture. RAM, CPU Frequency, number of cores are increased, and this increases the performance. Thanks to Moore's law, the hardware capabilities and performance tend to be increased without any noticeable increase in cost.
One more reason why smartphones need to be changed continuously is because the Operating System gets updated. Google and Apple allows users to update their Operating Systems by using the same phone only a limited number of times. After this limit, users have no other choice but to buy a new phone to use the newer operating systems. As the support of applications on older models of smartphones gets dropped, the user has no other choice but to upgrade to newer phones. This is known as planned obsolescence.
For x86, a similar phenomenon is observed, especially in Windows based laptops. As Windows keeps getting updated, you will observe that the laptop gets slower. This problem can be solved to some extent by increasing the RAM (which is not possible in the case of smartphones). For PCs, you can upgrade the CPU, GPU, RAM and storage, so they tend to be used the longest. For PCs, the Operating System can also be easily changed, and a lighter operating system can be used, which improves the performance.


Both problems are NP-complete and, by definition, there is a direct reduction between any pair of NP-complete problems.


Developing a Context Free Grammar whilst knowing the number of terminals

Your attempt was pretty close! But I think that this is the way to go for you

$$S \rightarrow a a a a X$$

$$X \rightarrow a X a \mid b b$$

The way that these rules come together forces there to be the four necessary $a$'s at the start and then it's a matter of matching $a$'s with $b b$ in the middle.

So after that, it's a question of making a CFG that generates $L = \{a^n b b a^n \mid n \geq  0\}$. That's exactly what $X$ does. Every time you see a $X$ you have to put a leading and trailing $a$ in and you can't terminate until you put the $b b$ in the middle since otherwise the $X$ gets expanded to another $X$.


Why is the distinction between linear and context-free grammars useful?

Let $\cal F$ and $\cal G$ be two classes of grammars, or what ever language defining devices you want. We assume that $L({\cal F}) \subset L({\cal G})$, the languages defined by the first class are included in those of the second.

Why consider both ${\cal F}$ and $\cal G$?

The most obvious reason is that the "models" in $\cal F$ are usually easier to handle to those in $\cal G$. That means it is in general easier to understand, write and analyse grammars in $\cal F$ than those in $\cal G$.  So whenever it is possible to work in the smaller class we might work there.

Sometimes we want to study and understand what makes a certain type of grammar hard to handle. We know that it is undecidable whether two context-free grammars generate the same word. For regular languages (given by right-linear grammars or finite automata) it is simple to construct the intersection and decide its emptiness. Now it is a matter of curiosity to know what happens in between: what about emptyness of intersection of linear languages?

Things are not always that straightforward. Deterministic pushdown automata are strictly less powerful than the general family (which generates context-free languages). They even allow a decidable equality test which is interesting for modellers. On the other hand, except for closure under complement, they have little closure properties.


Why Isn't This Outlier Score/Reconstruction Error Not Squared?

there is a good explaination squarred vs flat.

But from the simple view squarred error aims at variance while flat at median.
Different outliers comes from both versions, this is task dependent - the choice has been made by authors.

In fact yes, it is called roboust (somehow missused term), but it is not "better" for time series, just gives better estimator for outliers in presented method, which from given equation uses neither mean error nor mean square error - it uses custom made estimator with variance calculated on it's own.


Understanding $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$

Suppose that $M$ is a deterministic Turing machine that runs in space $s(n)$ and halts on all inputs. We show below that $M$ has $U(n) = 2^{O(s(n))}$ many configurations. I claim that if $M$ doesn't halt within $U(n)$ steps, then it never halts; since we assumed that $M$ always halts, this means that it always halts within $U(n)$ steps. To see the claim, let $\sigma_0,\ldots,\sigma_{U(n)}$ be the configurations after $0,\ldots,U(n)$ steps. Since there are only $U(n)$ different configurations but $U(n)+1$ many $\sigma_i$'s, there must be $i<j$ such that $\sigma_i = \sigma_j$. Therefore starting at $\sigma_i$, the machine will repeatedly go through the configurations $\sigma_i,\ldots,\sigma_{j-1}$, and in particular, will never halt.

It remains to count the number of configurations. Suppose that $M$ has $Q$ states, $C$ tapes, and tape alphabet $\Sigma$. We can describe a configuration of $M$ by specifying the state ($Q$ options), the head locations ($s(n)^C$), and the tape contents (at most $|\Sigma|^{Cs(n)}$; in these bounds we used the fact that at most $s(n)$ cells are used in each tape. In total, the number of configurations is at most
$$
U(n) = Q s(n)^C |\Sigma|^{Cs(n)}.
$$
You can show that $U(n) = 2^{O(s(n))}$ using standard manipulations, completing the proof.


Uniform random number generation from random bits

First we need reduce our rand(from, to) function just to rand(n) = returns uniformly random number from [0, n); and later we will be able construct original function as rand(from, to) = rand(to - from) + to.

  $rand(n)=$

  Take $k$ random bits such where $n \le 2 ^ k$ (actually we can choose any $k$ that satisfy this condition, but in practice make sense to choose minimal among all possible $k$) and interpret this sequence as binary integer $r$.
  If $r < n$ return $r$ else go to step 1.

Now let's calculate probability that some number $r$ will be choosen:

Probability that algorithm will stop after one iteration is $\frac{n}{m}$, probability that we will reach 2nd iteration is $\frac{m-n}{m}$; more generally probability that algorithm will reach $step$ interation is $Pr(step) = (\frac{m-n}{m}) ^ {step - 1}$.
Probabilities that algorithm will return some $r$ on 1st iteration:

$
Pr(0) = \frac{1}{m}\\
Pr(1) = \frac{1}{m}\\
Pr(2) = \frac{1}{m}\\
...\\
Pr(n - 1) = \frac{1}{m}\\
$

Probabilities that algorithm will return some $r$ on 2nd iteration:

$
Pr(0) = \frac{m-n}{m}*\frac{1}{m}\\
Pr(1) = \frac{m-n}{m}*\frac{1}{m}\\
Pr(2) = \frac{m-n}{m}*\frac{1}{m}\\
...\\
Pr(n - 1) = \frac{m-n}{m}*\frac{1}{m}\\
$

Probabilities that algorithm will return some $r$ on $step$ iteration:

$
Pr(0) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\
Pr(1) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\
Pr(2) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\
...\\
Pr(n - 1) = (\frac{m-n}{m}) ^ {step - 1}*\frac{1}{m}\\
$

And probability that some $r$ will be choosen (after any number of interations) will be the same regardless of $r$:

$
Pr(r) = \frac{1}{m} + \frac{m-n}{m}*\frac{1}{m} + ... + (\frac{m-n}{m}) ^ s*\frac{1}{m} + ... = \frac{1}{m}\sum\limits_{s=0}^\infty(\frac{m-n}{m}) ^ s = \frac{1}{m} \frac{1}{1 - \frac{m - n}{m}} = \frac{1}{m} \frac{m}{n} = \frac{1}{n}
$