Repetitions and periods in strings constitute one of the most fundamental
  areas of string combinatorics.1

The shortest prefix T of S where,

$S = T^k.Q , s.t: k>= 1,  Q =$ some prefix of T, then |T| is called the period of string.

  We say that string w has period p if w[i] = w[i + p] 1

Conventionally, finding T can be done by the Knuth–Morris–Pratt algorithm as well as Boyer–Moore string search algorithm.

Proving the correctness is beyond the scope of this answer.(More precisely, beyond my scope). See 1 for a better idea.

Before I came to know this, I attempted to solve this using KMP. And later, luckily, others have confirmed it. This could be helpful if one is wondering how could one possibly get an idea that KMP would work. I first tried to figure out the pattern and thought KMP could do the job.

Wondering how ? Our aim is to make $S$ a prefix of $T^n$ i.e. $TT \cdot .... \cdot T$, $n$ times. You can see that T is repeating itself, so, should some prefix of $S$ too.

E.g. take $S = abc$, the only way you can have $TTT$ and $S$ as a prefix of $TTT$ ($T^3$) is if $T = abc$, then $abc$ is a prefix of $abcabcabc$. The minimum part which is repeating is the complete string $abc$. Hence, $T = abc$.

But, if $S = aba$, then $T$ can be $ab$, and $aba$ is a prefix of $TTT$ i.e. $ababab$. The minimum part which is repeating is just the string $ab$. Hence, $T = ab$.

You're roughly getting the idea that finding that part of prefix of $S$, where it is repeating itself in the rest of $S$ and ending with some part of it.

Final e.g. would be $S = abababa$, then again $T$ would remain $ab$, i.e, the prefix which is getting repeated and ending with some part of it. We could form $S$ as $T^k.Q: s.t. k >= 1, Q =$ some prefix of $T$, here $a$.

Now your job is pretty easy. For every prefix in $S$, check if it is present in the rest of $S$ as described above. The shortest one you find would be the answer.

KMP has an essential part called "Prefix Function". Below is the code for the Prefix function in C / C++. When I ran it over a couple of strings S, I found good results.

void make_prefix_fun(char pat[], int a[], int m){
    // i is moving forward, and j is staying behind.
    a[0] = 0 ;
    for ( int i = 1, j = 0 ; i < m ; i++ ){
        while ( pat[j] != pat[i] && j > 0 )
            j = a[j-1];
        if ( pat[j] == pat[i] )
            j++;
        a[i] = j;
    }
}

Sample Cases:
aba
a b a
0 0 1
//  ^ T = S[1..(|S| - 1)]

adbashdbhabsjd
a d b a s h d b h a b s j d
0 0 0 1 0 0 0 0 0 1 0 0 0 0
// T is the complete S    ^

abcdabcda
a b c d a b c d a
0 0 0 0 1 2 3 4 5
//              ^. T = S[1..(|S| - 5)]
// Cool. Found something here.

abababababababababa
a b a b a b a b a b a b a b a b a b a
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// Cool. Found something here.              ^. T = S[1..(|S| - 17)]

abababababababababaaaa
a b a b a b a b a b a b a b a b a b a a a a
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 1 1
// Working exactly as expected.                   ^

Found a pattern? Yes, we do.

If you observe the array, after the first couple of consecutive 0s,

if we get the series, 1,2,3...x strictly upto the end, we can have our T = S[1..(|S| - x)] and the length of your required T is N - a[N] where N = |S|.
else T = entire string S.

The required T is the longest prefix of S, which is repeating itself in S, and S ends with some prefix of T or in other words T = S[1...|T|], where |T| is called the period of the string.

References:

1 - Repetitions in strings: algorithms and combinatorics, Crochemore et al.

Credits:

devnum, Mihai Calancea, Hendrik Jan.


A Turing machine $M$ can be described as a 7-tuple $(Q,F,q_0,\Sigma,\Gamma,\delta, blank)$. This means that if someone gives you this 7-tuple, then the TM is well-defined, and you can precisely define how it behaves, etc.

The encoding of a TM, usually denoted as $\langle M \rangle$ is a string that encompasses all the information of the 7-tuple describing $M$. You can think of it as "writing the 7-tuple as a binary string" (but this is a simplification). So the encoding of M, is just a string that describes how the TM works.

The last observation is that if you know the encoding - you know everything about the TM; specifically, if $\langle M \rangle$ is given as an input (to a machine $M'$), the TM $M'$ can "run" or "simulate" what $M$ would have done on any given input -- the machine $M'$ knows the states $Q$ of $M$ and the transition $\delta$ of $M$, so it can imitate its actions, step by step.


How to solve this partial order reduction in $O(n^2)$?

I think I am able to solve it.

First, have a lookup array for each sequence where array[element] = element's position in sequence [O(1)].

Phrased another way, this algorithm will find all "successors" for each of the elements in the first sequence. Finding successors for each element will take O(n) time.

For i in range(0,n):
    initialize most_recent_successor to None
    For j in range(i+1, n):
        if pos. of seq_1[j] > pos. of most_recent_successor in both sequences:
            advance j
        else:
            most_recent_successor = seq_1[j]
            add (seq_1[i], seq_1[j]) to result

Essentially, if a valid pair (seq_1[i], seq_1[j]) exists, then any pair (seq_1[i], seq_1[k]) will not be valid if the position of seq_1[k] in comes after the position of seq_1[j] in both sequences.

So, for the example in the question, (1, 3) is a valid pair. Therefore, (1,4) and (1, 5) are not valid pairs since 4 and 5 come after 3 in both sequences.

Edit: Please look at ruakh's insightful answer on lookup arrays I used here.


AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?

You've misunderstood the book.  It's not describing the AC-3 algorithm; it's describing some other algorithm.  The book is describing an algorithm that combines both guess-and-backtrack together with arc consistency.  The AC-3 algorithm doesn't do any guess-and-backtrack; it uses only arc consistency checks.

Thus, AC-3 does terminate if there is some variable whose domain set becomes empty; in this case, AC-3 declares the constraint system unsatisfiable (inconsistent).  This is the correct thing to do, in the context of the AC-3 algorithm.

Of course, if you're talking about some totally different algorithm (like the book is), that other algorithm might do something totally different.  No great surprise there.

I don't see anything wrong with the answer to the Stack Overflow question you link to.


Finding all unique paths from a source to a sink in a specially-formed DAG

If you are interested enumerating all the unique paths, then a recursion would be suitable since it is a dag. Observe that suppose v is a non source vertex and has incoming arcs from X1,...,Xn then every path from the source through v needs to pass through X1,...,Xn. . So if you enumerated all the paths from the source to each of these vertices you simply need to append v to them to compute all the paths through v originating from the source. This computation can be done very efficiently via dynamic programming. The reason DP will work is precisely because none of the paths from source to X1,...,Xn would have contained v since it is a dag.You should be able to work out the time complexity for the algorithm i described easily since it has a standard dp structure.


How many registers does a computer *need*?

You need to make your question a bit more precise.

First, regarding your request to avoid "unlimited" registers -- I assume you mean registers that can hold an arbitrary value (e.g., any natural number).

If you a-priori bound your registers, then the possible states your machine can be in is finite. That is, you have a deterministic finite automaton (or transducer, if you allow inputs and outputs). In this case, you don't need any register, but the machine would be huge without them. For example, you can replace 32 binary registers with $2^{32}$ states.

If you do allow arbitrary values, then 2 counters suffice to simulate a Turing Machine using a Minsky Counter Machine, under certain assumptions.


What is the use of finding minimum number of straight lines to cover a set of points?

Although many papers in theoretical computer science claims practical applications for their work, this is unfortunately often simply not the case.  Usually, either the problems are too far away from being something useful (too simplified), or the algorithms are too far away from being practical (e.g. hiding big constants in the O-notation).

However, you can look at the papers

Approximation algorithms for hitting objects with straight lines (Hassin & Megiddo) and
On the complexity of locating linear facilities in the plane (Megiddo & Tamir).

They claim, e.g.

  The problem of hitting objects in the plane with a minimum number of straight lines has a military application.  In many cases when a bomber attempts to destroy
  targets on the ground, protected by anti-aircraft  missiles, it has to spend as little time as possible close to the targets. Thus, careful planning of an air raid on a multi-target site (for example, a cluster of fuel tanks) calls for a minimum number of times a bomber has to fly across the site. Moreover, each pass has to be carried out as fast as possible, hence for each dive into the site there exists a straight line (a "stick") along which targets are destroyed. Another application
  (in three dimensions) is in medicine where radiotherapy is administered
  by inserting a minimum number of radioactive needles into a certain area of the body so as to achieve a required level of radiation.

And also:

  For example, we may view the problems faced by a planner who has to locate r (linear) segments of a new railroad system so as to minimize the average cost to the users who have to reach the tracks from a number of different small communities. Thus, a straight line or a line segment is of natural importance in this context. Sometimes such problems are easier than those with point facilities. For example, it is much easier to find a line, so as to minimize the sum of distances to it from a set of given points, than to find a single point with the same objective.


Every undecidable yet semi-decidable language provides an example: its complement.

That is because if $L$ and $\overline{L}$ are both semi-decidable, they are also both decidable -- proving that is an easy exercise.

You should know at least one such language from class.

   The Halting language, and probably numerous others from exercise problems.


Shortest directed path connecting given subset of vertices

This problem is NP-complete, by reduction from Hamiltonian path. Given an instance $G=(V,E)$ of Hamiltonian path, add a new vertex $s$ connected to all original vertices; this edges are directed from $s$, and all the original graph edges are bidirectional. Give all edges unit weight. There is a path from $s$ visiting all of $V$ of weight $|V|$ if and only if $G$ has a Hamiltonian path.


Shortest path tree from each vertex implies a unique MST?

Here is a hint:

   Pick any edge $e$ not in $T$. If you add $e$ to $T$, you will get a cycle. Can you show that $e$ is the unique heaviest edge in that cycle?

If you have seen the above hint, it is unlikely that you will not be able to complete what that hint ask you to do. In case you are still wondering what to do next, here is the hint for the next step.

   You are almost done! Can an MST contain the unique heaviest edge in any cycle?


Some questions on kernels and Reinforcement Learning

Is that valid? My question is how can I distinguish between a valid kernel and a nonvalid kernel if I'm given a kernel in the test?

Yes, it will be a valid kernel for all practical purposes, because kernel functions measure the similarity of some points relative to other ones (that's why they are also called similarity functions). Making your kernel function twice as big doesn't change that.

The next quote is from Wikipedia:

Although no single definition of a similarity measure exists, usually such measures are in some sense the inverse of distance metrics: they take on large values for similar objects and either zero or a negative value for very dissimilar objects. E.g., in the context of cluster analysis, Frey and Dueck suggest defining a similarity measure $s(x,y)=-\|x-y\|_{2}^{2}$
where $\|x-y\|_{2}^{2}$ is the squared Euclidean distance.

As you can see, a kernel function can be negative, if that's convenient in a particular problem. I don't know any example of an asymmetric kernel function. See this question for more examples.

The answer to your question boils down to this: can you apply a particular kernel function to a particular method? So it depends on a problem to large extent.

  Where does upper bound confidence enter?

In general, Upper Confidence Bound (UCB) is a Bayesian Optimization method, that aims to deal with exploration-exploitation trade off in the multi-armed bandit problem. In this problem, there is an unknown function, which we can evaluate in any point, but each evaluation costs (direct penalty or opportunity cost), and the goal is to find its maximum using as few trials as possible. Basically, the trade off is this: you know the function in a finite set of points (of which some are good and some are bad), so you can try area around the current local maximum, hoping to improve it (exploitation), or you can try a completely new area of space, that can potentially be much better or much worse (exploration), or somewhere in between.

Just as a side note, Bayesian Optimization methods, UCB in particular, build a model of the target function using a Gaussian Process (GP) and at each step choose the most "promising" point based on their GP model.

In Reinforcement Learning, the same exploration-exploitation dilemma arises as well. When an agent chooses an action to make, it has a choice between low uncertainty actions with a known value (exploitation) and high uncertainty actions (exploration). Without proper exploration, an agent would always do the same actions and never actually learn.

In this setting, UCB is counting how many times each action $a$ has been selected, $N_t(a)$, and maximizes the following expression:

$a_t = \underset{a∈A}{\operatorname{argmax}} Q(a) + \sqrt \frac{2 log t}{N_t(a)}$

where $Q(a)$ is an action-value function. If you compare this formula to the one used in Bayesian Optimization, you'll notice it's actually the same idea.


Encoding a "not-k-out-of-n" constraint for SAT solvers

Assuming you work in CNF, construct  "at least $k+1$-out-of-$n$" and add "or $p$" to each disjunction. Do the same for "at most $k-1$-out-of-$n$" and add "or $q$" to each disjunction.

Then add one extra term to your main conjunction, $\neg p \vee \neg q$.


I don't see why the array[1..3, 1...2] is faster to index than array[1...2, 1...3]?

Two-dimensional arrays are stored as one-dimensional arrays. Your first array is stored as
$$ A[1,1], A[1,2], A[2,1], A[2,2], A[3,1], A[3,2], $$
so the offset of $A[x,y]$ is $2x+y-3$. In contrast, the third array is stored as
$$ A[1,1], A[1,2], A[1,3], A[2,1], A[2,2], A[2,3], $$
so the offset of $A[x,y]$ is $3x+y-4$. Multiplying by 2 could be faster than multiplying by 3 – for example there might be a suitable addressing mode in your instruction set.


Can a collection of oracle machines decide every language?

This answer assumes that "a collection of oracle machines" means "a sequence of oracles", that is, you have a Turing machine with access to a sequence of oracles.

A sequence of oracles is equivalent to a single oracle: if the original sequence is $O_i$, choose some pairing function $\langle \cdot,\cdot \rangle$ (e.g. $\langle x,y \rangle = 2^x (2y+1)$), and define a single oracle $O$ by $\langle x,y \rangle \in O$ if $y \in O_x$.

It is known that a machine with oracle access to $O$ cannot decide all languages, for reasons of cardinality. We can also exhibit a specific language undecidable by such a machine, namely the halting problem for oracle machines with oracle access to $O$.


It could be that the analysis works either way, or perhaps the analysis (or the algorithm) could be slightly modified to handle this change. I suggest you go over the correctness proof of the algorithm and see where this step is used (if at all).


Why is tabulated hashing 3-wise independent but not 4-wise independent?


How do you analyse the time complexity of a piecewise function?

There seems to be a misconception here: every function $f$ has a "nice" asymptotic form, in the sense that $f = \Theta(g)$ for some function $g$ given by a reasonable formula. Some examples of reasonable formulas include $c^nn^k\log^\ell n$ for various values of $c,k,\ell$. However, this isn't always the case. Consider for example the function
$$
f(n) =
\begin{cases}
n & \text{if $n$ is odd}, \\
n^2 & \text{if $n$ is even}.
\end{cases}
$$
There is no "nice" function $g$ such that $f = \Theta(g)$. It is apparent that $f = \Omega(n)$ and that $f = O(n^2)$, but there is no value of $k$ for which $f = \Theta(n^k)$.

In practice, such examples occur only rarely, and so usually it is the case that we can find a nice order of growth for functions that occur in practice.

This discussion is related to another misconception, that we can always compare two functions asymptotically. That is, that for any two functions $f,g$, either $f = o(g)$, or $f = \Theta(g)$, or $f = \omega(g)$. While these three possibilities are indeed mutually exclusive, there is a fourth possibility, namely, that $f$ and $g$ are incomparable. As an example, if we take the function $f$ considered above and try to compare it to $g(n) = n^{3/2}$, then we find that none of $f = o(g)$, $f = \Theta(g)$, $f = \omega(g)$ holds. However, the trichotomy does hold when $f$ and $g$ are "nice" functions (defined using only arithmetic operations, logarithm, and exponential).

Finally, there is one special case which is easy to handle: if
$$
f(n) = \begin{cases}
g(n) & \text{if } n < C, \\
h(n) & \text{if } n \geq C,
\end{cases}
$$
Then $f(n) = \Theta(h(n))$. This is the case in your example.


Find the max of a convex function in fewest samples

As the function $f$ is convex, its maximum value in interval $[a,b]$ is either $f(a)$ or $f(b)$.  Otherwise, it will violate Jensen's inequality.


Bankers Algorithm-Is the system in safe state?

you can say there is no deadlock if there is a safe sequence for the completion, after $P1$ request is granted there must be a safe sequence where by which every process is completed.

After P1 request is granted
                      |   P1  |  P2  |   P3   |
Max Requirement       |   8   |  7   |   5    |
Current Allocation    |   4   |  1   |   3    |
Balance Requirement   |   4   |  6   |   2    |
now the resources left over are 10-4-1-3=2

so can we complete with 2 resources? any sequence is possible?

YES

if P3 is given 2 resources it will complete and release all the current allocated resources so our resource count becomes 5 , now we have 5 and we can complete P1 and get back 4 now our resource count is 9 and i need just 6 to complete P2 so a safe sequence is possible.
so safe sequence will be

$P3 \rightarrow P1\rightarrow P2$

so $P1$ request is granted


Create an Finite Deterministic Automata for a regular expression

I think your problem could be understood in two ways:

$abb$ is a subword of $w$ and the word $w$ doesn't start with $abb$
$abb$ is a subword of $w[1:]$, but the word $w$ can start with $abb$

I will assume the first one but correct me if I'm wrong.
One way to create an automaton for this language would be as follows:

From the start state $q_0$ go to $q_a$ on input $a$ and to $q_{abb?}$ on input $b$
From $q_a$ go to $q_{ab}$ on $b$ and to $q_{bb?}$ on $a$
From $q_{ab}$ go to $q_{reject}$ on $b$ and to $q_{bb?}$ on $a$
From $q_{abb?}$ loop on $b$ and go to $q_{bb?}$ on $a$
From $q_{bb?}$ go to $q_{b?}$ on $b$ and loop on $a$
From $q_{b?}$ go to $q_{accept}$ on $b$ and to $q_{bb?}$ on $a$
Loop on $q_{accept}$, which is the accepting state

The graphical representation would look as follows:

So what we are doing, in essence, is first checking if the word $w$ starts with $abb$ and if it does reject it and if it does not, then look for the subword $abb$.
Answering the other part of your question:

There is an algorithm that transforms regular expressions to Nondeterministic Finite Automata
Developing intuition is just a matter of practice. You have to write as many automata for regular languages as possible and see what are the common tricks and methods, and what are some traps that await you when constructing automata.


Paxos: Accepting Proposals With Different Values and Consensus in Paxos

Question 1: This means that an acceptor can accept a proposal with a value $v_2$ after it has accepted a proposal with value $v_1$. Otherwise, I don't see how it can be guaranteed that a majority of acceptors accept proposals with the same value. Is this correct?

Yes, it is possible for an acceptor to accept a proposal with number $n_2$ and value $v_2$ after it has accepted a proposal with number $n_1$ and value $v_1$. Consider the following scenario where there are two proposers $p_1$ and $p_2$ and three acceptors $a_1, a_2,$ and $a_3$:

$p_1$ proposes $\texttt{propose}(n_1,*)$ to $a_1$ and $a_2$.
both $a_1$ and $a_2$ respond to $p_1$ with (a) a promise never again to accept a proposal numbered less than $n_1$ and (b) no proposal because they have not accepted any ones.
$p_1$ receives the two responses from $a_1$ and $a_2$. Now $p_1$ is free to select its own value $v_1$. $p_1$ sends $\texttt{accept}(n_1, v_1)$ to $a_1$ and $a_2$.
$a_1$ accepts $(n_1, v_1)$ but $a_2$ does not (maybe this message to it has been lost; note that an acceptor can ignore any request without compromising safety).
$p_2$ proposes $\texttt{propose}(n_2, *)$ to $a_2$ and $a_3$ ($n_2 > n_1$).
Because, in 4, $a_2$ does not accept $\texttt{accept}(n_1,v_1)$ from $p_1$, both $a_2$ and $a_3$ respond to $p_2$ with a promise never again to accept a proposal numbered less than $n_2$.
$p_2$ receives the two responses from $a_2$ and $a_3$ and is also free to select its own value $v_2$. $p_2$ sends $\texttt{accept}(n_2, v_2)$ to $a_1$ and $a_3$.
$a_1$ can now accept the proposal $(n_2, v_2)$ from $p_2$.

  Question 2: (1) Does this mean that if a proposer proposes a value, $v_1$, that is accepted by a majority, it is now impossible for the same proposer, or another proposer, to propose another value, $v_2$? (2) If they want to make a proposal, they must propose the same value, $v_1$? (3) The only way they could propose a different value would be to start a new instance of Paxos. (4) The reason you would want to make a proposal with the same value as the chosen value is because the chosen value might not have been received by any of the learners. Is this correct?

For (1): yes; For (2), yes. The invariant $\texttt{P2B}$ in Paxos is the key to its correctness.

For (3): I think you have confused an instance of Paxos with a round in an instance of Paxos. They are two important concepts. We call a round the collection of all messages labeled with some particular proposal $n$. An instance of Paxos consists of multiple rounds, each round corresponding to a proposal with a different number. If you consider multiple instances of Paxos, please refer to Section 3 "Implementing a State Machine" in the paper. It is often called "multi-Paxos".

For (4): in page 6, it reads "A proposer can make multiple proposals, so long as it follows the algorithm for each one. It can abandon a proposal in the middle of the protocol at any time". That is to say, as a proposer, you are free to make multiple proposals as you want, for no matter what reasons. However, a major reason would be to learn the value already chosen: at phase 2(a), you will have to select the value chosen, if any.

  Question 3: Can an acceptor respond to a proposer with a promise if consensus has already been reached?

Yes, it does no harm. Again, the invariant $\texttt{P2B}$ works.

  Question 4: The promises guarantee that a majority of acceptors will always accept a value, because the proposer must receive a promise from the majority of the acceptors before it can send a proposal, correct?

Are you discussing about the correctness of Paxos? Are you regarding the "promise mechanism" as the key to success? If so, you are almost right: however, it is hard to identify a single factor in Paxos. If it must be done, once again, it is the $\texttt{P2B}$ invariant.


ML Algorithms to discriminate "known" from "unknown" instances

I would use a two-step pipeline where the first step discriminates between known and unknown and the second step performs the actual classification. This approach has a number of benefits.

Separating the two problems allows you to judge the accuracy of each step. You can assess the quality of your known/unknown discrimination independently of your actual classifier and vice versa. This will tell you where you need to focus your efforts.
You don't need to worry about your classifier being over confident for examples you aren't actually interested in since presumably you're taking care of this beforehand.
The known/unknown discrimination is just the problem of outlier detection. There are lots of ways to approach this and you may be able to find methods designed to work within your specific problem domain. I frequently hear 1-class SVMs (support vector machines) come up in this context, but have never worked with them personally.

If you think about the way decision trees work it is pretty easy to see why a single tree is going to be overconfident. There are lots of different ways to learn decision trees, but in general you can think about them as trying to make the leaves as pure as possible, i.e., we want the leaves to contain instances that all have the same class. Since an unknown example is just going to follow some path down the decision tree, it will end up in a leaf, which by construction, contains little class variability. From this observation it is easy to see why combining many different trees (like in Random Forests) is going to help avoid this problem.

As for why Naive Bayes is being overconfident, I would guess this is due to some combination of one of the class priors $P(y)$ being larger than the others, and/or having most features be unknown for your unknown example (so $P(x_i|y)$ is approximately the same for all $y$ and most $i$ if you're smoothing the estimates) and a couple show up in one class causing the $\prod_i P(x_i|y)$ term to blow up for one $y$ relative to the others. This is just a guess without the data.


Show that the Turing Machine domain can be viewed as a classical planning domain

In order to show that the computation of a Turing machine can be modeled as a planning problem, you can encode the tape symbols, the head position and state, and the execution of a transition using states:

symb(i,x)   : i-th cell of the tape contains symbol x
head(i,q)   : head is over cell i in state q
exec(i,q,x) : execute the transition at i-th cell in state q over symbol x
accept      : accept the input

At the beginning symb(i,x) are true/false according to tape content; head(1, q0) is true; and all other states are false. The goal G is {accept}.

Actions are built using the transition table of the Turing machine; suppose that you have the transition:

 a, q0 -> b, q1, Left

Then for every cell i of the tape you can add the actions:

 symb(i,a) AND head(i,q0) => !head(i,a) AND exec(i,q0,a)
 exec(i,q0,a) AND symb(i,a) => !symb(i,a) AND symb(i,b)
 exec(i,q0,a) AND symb(i,b) => !exec(i,q0,a) AND head(i+1,q1)

The actions for the transitions to accepting states are similar.

Note that actions with only 2 positive preconditions and two postconditions are enough to "simulate" the behaviour of a Turing machine.


Why are there only NOR and NAND flashes?

NAND and NOR are the only two binary gates that are functionally complete, which means that using just one gate type you can implement any circuit.

This greatly simplifies fabrication. As long as you can construct a single type of gate many times using the same technique, and can connect them arbitrarily, you can create any circuit.


Compute minimum hamming distance of a code

When the code is linear, there is no need to go over all pairs of codewords, due to linearity. Indeed, since $d(x,y) = d(x\oplus y, 0)$ and for any two codewords $x,y \in C$, linearity implies that $x\oplus y \in C$, we see that the minimal distance is the minimal weight of a non-zero codeword. There are other ways characterization of the minimal distance, for example in terms of the generator matrix. See also this question.

By the way, an $(n,k,d)$-code is one with $2^k$ codewords of length $n$ and minimal distance $d$. So if you have a $(7,4,3)$-code, the minimal distance must be...?


Why can PDAs only write one symbol to the stack according to this definition?

The addition of $\epsilon$ to the alphabets allows the pop and push operations. For example, if you want to push the letter $a$ in state $q$, without reading anything from the input, you can have the transition $\delta(q,\epsilon,\epsilon)=\{(s,a)\}$, where $s\in Q$.

And if you want to pop $a$ without reading anything from the input, you can have $\delta(q,\epsilon,a)=\{(s,\epsilon)\}$.

Of course you can combine the two for a simultaneous pop/push, and you can do that while reading from the input.


Complexity of Verification for Clique with Adjacency Matrix

Here is an algorithm for verifying that the clique $C[1],\ldots,C[k]$ is contained in the graph whose adjacency matrix is $A$:

for i from 1 to k:
   for j from 1 to i-1:
      if A[i,j] = "no edge", then return "No"
return "Yes"

What is the running time of this algorithm?


DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?

Any graph of this type can be represented using this simplified model (left):

where M1, M2, and M3 are metanodes that can represent 0 or more nodes, and edges involving M1, M2, and M3 can represent 0 or more edges.
In order to split the graph in the manner I am seeking, it's required to classify these nodes using the reachability algorithm.  The members of M1 are all nodes $k \not \in \{A, B\}$ such that $A \not \le k$.  The members of M2 are all nodes $k \not \in \{A, B\}$ such that $A \le k \land B \not \le k$.  Finally the members of M3 are the remaining nodes $k \not \in \{A, B\}$ and $B \le k$.
The members of M2 are duplicated along with B and A.  All edges from M1 to M2 or B are routed to M2' and B' instead.  And the edges from M2 and B to
M3 are duplicated for M2' and B'.  Finally, an edge from B' to A' is made.
The algorithm fails to place A' if and only if there are no edges connecting M1 to B and there are no edges from M1 to M2 or M2 to B, which represents the fact that there is no path to B without going through A, so there is no possible way to place A'.
So this problem can be solved with $O(n)$ lookups using pretty much any general reachability algorithm.


Notice that the loop will only occur once! In the beginning num will be 0. At this point, we enter the if statement:

if we got that str[0] == ch (notice that num==0 and thus str[0]==str[num]), then we return some string
otherwise we return another string

The important thing here, is that no matter what - we will quit in the first iteration of the for loop.
To fix this, consider placing the return str outside the for loop (without else as well)


How many $(x, y)$-paths of length $20$ are there, where $x$, $y$ adjacent vertices in cycle $C_5$?

Hint: consider powers of adjacency matrix of $C_5$ (Wiki: Matrix powers).


Compact, reversible mapping from set partitions of length k to integers

The idea is to use the recurrence
$$
\newcommand{\stirling}{\genfrac{\{}{\}}{0pt}{}} \stirling{n}{k} = k \stirling{n-1}{k} + \stirling{n-1}{k-1}.
$$
This recurrence holds since either element $n$ belongs to one of the $k$ partitions of a partition of $1,\ldots,n-1$ into $k$ parts (say, ordered by minimal element), or it forms a singleton partition, joining a partition of $1,\ldots,n-1$ into $k-1$ parts.

Accordingly, partition the range $[0,\stirling{n}{k})$ into $k$ parts of length $\stirling{n-1}{k}$ and one of length $\stirling{n-1}{k-1}$. Given a partition, determine which of the $k+1$ intervals you belong to, remove $n$, encode the remaining partition of $n-1$ recursively, and locate it inside the chosen interval. The base cases are $\stirling{0}{0} = 1$ and $\stirling{n}{0} = \stirling{0}{n} = 0$ for $n > 0$.

The same algorithm can be reversed and be used to decode a number in $[0,\stirling{n}{k})$ into a partition of $1,\ldots,n$ into $k$ parts.


When is it best to use the second chance replacement algorithm?

Farthest-in-future is optimal, second chance can't be better. Second chance is a way to approximate LRU when the required hardware (access times, sort them) isn't available. Both try to approximate the optimal strategy, there certainly can be cases where one or the other is better.


What is the relation between differential-privacy mechanism and entropy?

In general, if you're not sure about the significance of mathematical results in a published paper, often a good first place to look is the paper's introduction and/or conclusion.  The authors often try to provide some explanation why you should care about their results in the introduction and conclusion.

In this case, the following two quotes from the introduction of the paper you cited provide a pretty clear explanation for why the authors care:

  we first study an $\epsilon$-differentially private noise-adding mechanism
  for one-shot queries that provides the best output accuracy,
  which is measured by the Shannon entropy. [...]

  In Section III, we prove that, for a one-shot $n$-dimensional
  input, there is a lower bound $n + n \ln(2\epsilon)$ on the entropy of
  the output for an $\epsilon$-differentially private noise-adding mechanism, and the lower bound is achieved by Laplacian noise
  with parameter $\epsilon$.

In other words, the Shannon entropy measures the accuracy of the output after adding the noise (lower is better); Theorem 8 proves that Laplace noise achieves the lowest possible Shannon entropy, in a particular situation; therefore, we can conclude that Laplace noise is optimal in  the sense that it achieves the highest possible output accuracy, in that situation.


If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)?

No. You can't. As $\lim_{n\to\infty} \frac{n!}{n! \times n} = 0 $. Hence, $n! \times n  = \omega(n!)$ or $n! = o(n\times n!)$ (little-oh).


If an algorithm solves an NP problem, for what f(n) can we claim that R belongs to TIME(f(n))?

Suppose, for clarity:

$X$ is the input, and $|X|$ = $n$
$Y^*$ is a "yes" certificate, $|Y^*| \leq 5\log n$ bits
$M$ is an algorithm that verifies the instance $X$ given certificate $Y^*$ in
$O(n^3)$ time.

There are $2^{|Y^*|}$ possible binary certificates of length $|Y^*|$, so algorithm $A$ that checks all possible certificates $Y_i$ of length $5\log n$ will have exactly $ 2^{5\log n} = n^5$ certificates to check.

Since each certificate takes $O(n^3)$ time to verify (with $M$), $A$ will run in $O(n^8)$. If $X \in R$, a certificate $Y^*$ that verifies it exists and $A$ will find it (because it checks them all).

It follows that $A$ accepts $R$ and runs in $O(n^8)$ time, so $R \in \textbf{TIME}(n^8)$


is this an example of nominal unification?

Sure, these unify under nominal unification.  You get a unifier like $X = (b\ a)\bullet\lambda c.c$ which simplifies to $X = \lambda c.c$.  Figures 1 and 3 of Nominal Unification describe the relevant details of the algorithm.  In particular the transitions will be $\approx?$-abstraction-2 and $\approx?$-variable followed by $\#?$-abstraction-2 and $\#?$-atom.


Is topological sort of an original graph same as post-ordering dfs of its transpose graph

Let $G$ be a graph and $G'$ be it's transposed version. Your property follows from the following two facts:

1) The order in which vertices are visited by a postorder visit on $G'$ is the reverse of a topological order $\sigma'$ for $G'$ (in fact, that's a standard way to compute a topological order).
You can see that this is true by noticing that if $(u,v) \in G'$ then $v$ must be visited before $u$ can be visited, i.e., $v$ follows $u$ in $\sigma'$.

2) If $\sigma'$  is a topological order for $G'$, then the linear order $\sigma$ obtained by reversing $\sigma'$ is a topological order for $G$.
You can see that this is true because, for every edge $(u,v)$ of $G$, $G'$ contains $(v,u)$ and therefore $v$ precedes $u$ in $\sigma'$. This means that $(u,v) \in G \implies u$ precedes $v$ in $\sigma$.


Does splitting a process across 4 terminal windows decrease the time it takes?

What you describe (split job into parts, total CPU usage stays the same) indicates that your task is (or gets) I/O (or perhaps RAM) bound. Try splitting among several machines, not just several processes on the same machine. If the program you are using comes from somewhere else, see if there are newer versions, bug reports on performance, or perhaps tricks and suggestions, on its webpage or user sites.

Use the tools on your operating system to see what the bottleneck really is. As you don't say what operating system this is, I can't give concrete suggestions. Perhaps look into  uxix.stackexchange.com, superuser.com, or serverfault.com (all part of the stackexhange network).


Check the definitions. The language accepted by an automaton is the set of strings it accepts. So, for an automaton to accept a particular language (e.g., $\{a^nb^n\mid n\geq 1\}$), it must not only accept every string in the language, but also reject every string not in the language. Your suggestion of the automaton that just accepts every input meets the first criterion but not the second.


Overlapping between two intervals: reasoning / algorithm to find the set of disjoint and overlapping intervals

For two integers $A$ and $B$ where $A\le B$, let $[A,B)$ denote the half-closed half-open interval that consists of the numbers $A, A+1, \cdots, B-1$. In particular, if $A<B$, then there are $B-A$ numbers in $[A,B)$. If $A=B$, then there is no numbers in $[A,B)$. For example,

$[0,1)$ means the number 0.
Both $[0,0)$ and $[3, 3)$ mean no numbers.
$[5,11)$ means the numbers $5,6,7,8,9,10.$
To denote the numbers $-2, -1, 0, 1, 2$, we can use $[-2, 3)$.

A nice property of half-closed half-open interval: If $L\le M \le R$, then $[L,R) = [L,M) \sqcup [M,R)$.

Proof: I am afraid it is obvious by definition. Done.

Suppose we are given $[A, B)$ and $[C, D)$, where $A\lt B$ and $C\lt D$. Then $[A,B)$ overlaps $[C,D)$ if and only $\max(A,C)\lt \min(B,D)$.

Proof:

"$\Rightarrow$": Let $n$ be a number in both $[A,B)$ and $[C,D)$, i.e.,
$A\le n\lt B$ and $C\le n \lt D$. Then $\max(A,C)\le n\lt \min(B,D)$.

"$\Leftarrow$": $A\le \max(A,C)\lt \min(B,D)\le B$, i.e., $\max(A,C)\in [A,B)$. Similarly, $\max(A,C)\in [C,D)$. So $[A,B)$ overlaps $[C,D)$.

Done.

Suppose $[A,C)$ and $[B,D)$ overlap. Then we have the following set decompositions.

$[A,B) = [A, \max(A,C))\sqcup[\max(A,C), \min(B,D)]\sqcup[\min(B,D), B)$
$[C,D) = [C, \max(A,C))\sqcup[\max(A,C), \min(B,D)]\sqcup[\min(B,D), D)$

Proof:

We have $A\le \max(A,C) \le \min(B,D)\le B$. So,

$$\begin{align}
[A,B) &= [A, \max(A,C))\sqcup[\max(A,C),B)\\
&= [A, \max(A,C))\sqcup[\max(A,C), \min(B,D)]\sqcup[\min(B,D), B).
\end{align}$$

Example 1: If $I = \{2, 3, 4, 5, 6, 7, 8, 9\}$ and $J = \{4, 5, 6, 7\}$, then $I=[2,10)$ and $J=[4,8)$. We have the following set decompositions.

$[2,10) = [2, 4)\sqcup [4, 8) \sqcup [8,10)$.
$[4,8) = [4, 4)\sqcup [4, 8) \sqcup [8,8) = [4,8)$.

Example 2: If $I = {2, 3, 4, 5, 6, 7, 8, 9}$ and $J = {4, 5, 6, 7, 8, 9, 10, 11, 12}$, then $I=[2,10)$ and $J=[4,13)$. We have the following set decompositions.

$[2,10) = [2, 4)\sqcup [4, 10) \sqcup [10,10)= [2, 4)\sqcup [4, 10)$.
$[4,13) = [4, 4)\sqcup [4, 10) \sqcup [10,13)= [4, 10) \sqcup [10,13)$.

The above examples should indicate clearly enough the algorithm that decomposes two overlapping intervals into disjoint intervals.


Bottom-up algorithm to build subset of maximum weight

This is the maximum-weight independent set problem, which is known to be NP-hard.  Therefore, there is unlikely to be any efficient solution. However, you could use any of the standard algorithms for this problem, if you're willing to accept an exponential-time algorithm.


Example for an undecidable language L such that L is reducible to its complement and vice versa

Let $K$ be some undecidable problem, and define
$$
L = \{0x : x \in K \} \cup \{1y : y \notin K \}.
$$
(I'm assuming the alphabet is $\{0,1\}$.)
Then
$$
\overline{L} = \{\epsilon\} \cup \{0x : x \notin K \} \cup \{1y : y \in K \}.
$$
I'll let you take it from here.


Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree

Average degree and mean degree are the same. In the $G(n,m)$ model, the average degree is $2m/n$. In the $G(n,p)$ model, the expected average degree is $np$. The actual average degree has normal distribution with mean $np$ and standard deviation $\sqrt{2(1-\tfrac{1}{n})p(1-p)}$, so it is pretty close to $np$ with high probability.

When $p=c/n$ for fixed $c$, the degree of a single vertex has roughly Poisson distribution (with mean $c$); formally, as $n\to\infty$ the distribution tends to Poisson. In practice, this means that for "small" $c$ and "large" $n$, the degree will be Poisson. Furthermore, while there is some dependency between vertices, we still expect the entire empirical degree distribution to be close to the same Poisson distribution (i.e., we expect the fraction of coordinates having degree $d$ to be roughly $e^{-c} c^d/d!$); this is probably proved formally in the literature.

When $p$ is constant, the degree of a single vertex has roughly Gaussian distribution, and it is probably the case that the joint distribution is also close to the appropriate multivariate Gaussian.


Shortest path in a maze where you can break one wall

You can use any search algorithm (including A*) with a tiny alteration from the standard one.

In each node you store whether the path from the start has a broken wall or not. Then when generating the neighbours you can move into a wall only if that flag is false and the neighbours that move into a wall get it set to true.

When Comparing Nodes for equality (for replacing in the heap and or the closed set) that flag counts alongside the position.


Policies for handling symbols leaking out of a lexical scope

Your (let (x) 'x) will just return the atom x, and obviously all of those are the same. That you define variables called x (and give them no value whatsoever, and never use them) is just confusing the issue. I.e., your code is a roundabout way to write (eq 'x 'x).

How could a name "escape" from a lexical scope? The scope is precisely where the name has a particular meaning, an "escape" would just expand that scope somehow.

E.g. in Steelbank Common Lisp:

* (let (x) 'x)
; in: LET (X)
;     (LET (X)
;       'X)
;
; caught STYLE-WARNING:
;   The variable X is defined but never used.
;
; compilation unit finished
;   caught 1 STYLE-WARNING condition
X

enter code here


Working out the connectives (And, Or, Not) in a Truth Table that has the outputs

Generally speaking, there is no unique boolean function $f(p, q)$ that produces your output. For your example, the function $f(p, q) = p$ would be a valid solution, as well as $f(p, q) = (p \vee q) \wedge (p \vee \neg q)$, and $f(p, q) = (p \wedge q) \vee (p \wedge \neg q)$.
You can find an equisatisfiable function to the one that produced the given output, and there are a number of approaches to do so.

A simple approach would be the enumeration of variable constellations that produce $\top$, and disjunct them. For your example that would mean first finding the constellations that produce $\top$:

$p \wedge \neg q$
$p \wedge q$

and finally producing $f(p, q) = (p \wedge q) \vee (p \wedge \neg q)$

This way you produce a function in disjunctive normal form (DNF). A similar approach works for CNF, but in both cases you end up with a fairly large function.

More complex approaches are Karnaugh Maps and the Quine McCluskey algorithm. They can produce much more concise, even minimal equisatisfiable functions.

As far as I know, most approaches focus on CNF (and sometimes DNF), i.e. use only conjunctions, disjunctions and negations, and don't nest operators any further.


Hash function which is invariant under small changes

Use locality-sensitive hashing. Make sure you're not breaking the law.


"Compressing" rationals given error bounds

Continued fractions are an efficient way to enumerate rational numbers that are a good approximation of your number $x$.  In particular, given a real number $x$, you can generate a sequence of truncated continued fractions $a_i/b_i$, where each rational number $a_i/b_i$ is a better approximation to $x$ than any other fraction whose denominator is $\le b_i$.  So, a reasonably good algorithm for your problem is to compute the sequence of truncated continued fractions, and keep the last one whose denominator is smaller than your bound.  This doesn't find the best rational approximation for a given number of bits, but it does give you a best rational approximation for a given upper bound on the size of the denominator.

To compare to KWillets' excellent answer: KWillets' method takes something like $\Theta(a+b)$ steps, but finds the optimal solution (measured by bits).  Continued fractions takes something like $\Theta(\lg b)$ steps, but isn't guaranteed to find the optimal answer (measured by number of bits); it's only guaranteed to find the optimal answer if you measure by the size of the denominator.  KWillets' method seems better if $a,b$ are not too large.  However, if they are very large, then a continued fractions-based method might become more attractive.


How exactly do we define parametric polymorphism?

An informal, but better way of explaining parametric polymorphism is that the term has a uniform definiton/semantics for all types. A simple example is the identity function:

$$λ x. x$$

This is one term that can be reasonably given the type $ℕ → ℕ$, $\mathsf{Bool} → \mathsf{Bool}$, etc. Therefore, we also consider it reasonable for it to give it the type $∀a. a → a$, because it is a single term that works for every type.

If you want to talk about terms where types are explicitly talked about, then this becomes somewhat less clear. However, an informal idea of what must be going on in those definitions is that the type variables are completely unknown to the definition. So in:

$$Λa. λ(x : a). x$$

even though we get syntactically different terms for each choice of $a$, the definition didn't specify what happens for particular choices of $a$, or something of that sort.

The more formal/precise way of explaining all of this is usually relational parametricity. That's kind of complicated to get into, but it says that there are ways of interpreting our definitions into relations in addition to the normal semantics. In this explanation, parametric polymorphism is about preserving relatedness. So, if you instantiate a polymorphic value to related types, the values you get are related in a coherent way. And the reason why relations are used is that they give a precise (but general) way of talking about what it means for things to be 'uniform' like above.


You've basically got the answer already: the s register is number 0b10001 = 17, the t register is number 0b10010 = 18.

The instruction is not quite the way you've said it: standard MIPS has the registers in the opposite order, so it's opcode rs rt immediate. The opcode is 0b001000 = 8 = ADDI; rs is 0b10001 = 17 = $s1; rt is 0b10010 = 18 = $s2; the immediate value is 0b0000000000001111 = 15.

(The prefix 0b indicates that the following number is in binary.)


Carry is generally used for unsigned arithmetic and overflow is used for signed arithmetic.

This unsigned 8-bit operation results in Carry, but no overflow (the sign of the result is correct):

0xC0 + 0xD8 = 0x98

If we're doing unsigned 8-bit arithmetic, that's fine and we're only interested in the carry bit in this case, which tells us that the "correct" answer is actually 0x198.

If we look at the same operation and the same operand values, but consider that the operands are signed, we have the equivalent:

-0x40 + -0x28 = -0x68

In this case, there is also no "overflow" and the result of the arithmetic is correct.

Consider this unsigned operation, however:

0x70 + 0x68 = 0xD8

No overflow here -- and no carry. The unsigned arithmetic is simple. But now look at the operands as signed values:

0x70 + -0x98 = 0x28

The answer is obviously wrong. We have subtracted a larger number from a smaller one and ended up with a positive value. The carry is not set here, so it doesn't offer a clue of the problem. The overflow flag reveals that the "correct" signed answer is -0x28.

source


Finding an element in array, whose index number and element value same

If the array had $A[i]=i, \forall{i}$, then the complexity would have been $\theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1.  The complexity is indeed $\theta(log_2n)$


cardinality of recursive/r.e/not r.e languages?

I assume you're talking about the cardinality of the sets $R$, $RE$, and $\overline{RE}$, as the set of all words in a language is always countable.

$R$ (the family of recursive langauges) is countable, because there the set of Turing Machines is countable, and there is at least one TM for each $R$ language.
$RE$ is countable, by the same logic, since there is a TM semi-deciding each $RE$ language.
The set of non-$RE$ languages, $\overline{RE}$, is not countable, then by process of elimination. The set of all languages, $\mathcal{L}$, over an alphabet $\Sigma$ is $\mathcal{P}(\Sigma^*)$ i.e. the powerset of the set of all words.
This set is uncountable, since $\Sigma^*$ is countable, and the powerset of a set always has higher cardinality.

$\mathcal{L} = RE \cup \overline{RE}$, and $RE$ and its complement are disjoint, so since $RE$ is a countable subset, there must be an uncountable number of words in $\overline{RE}$.


Is there any bitwise multiplication algorithm that is sub O(n^2)?

Is Karatsuba algorithm simple enough? It's complexity is $O(n^{1.59})$.


Why are multi-threading programs more prone to errors?

Overview

Multi-threaded programs are more prone to errors than single-threaded programs because of the problem of concurrency bugs.  Concurrency is hard for most developers to reason about, which causes many bugs in multi-threaded programs; this issue normally doesn't arise in single-threaded programs, because single-threaded programs typically have no concurrency.

Mutable shared state, and plan interference

The core problem is due to the combination of multi-threaded programming plus mutable shared state.  If there was no shared state, or if all shared state was immutable, then you wouldn't have to worry about concurrency bugs.  But when you have mutable shared state, then the programmer has to start thinking about all possible interleavings of the thread A's accesses to the shared state with thread B's accesses to the shared state.  There can be exponentially many possible interleavings that the programmer needs to reason about, if they want to avoid concurrency bugs, and no surprise, that's non-trivial.

Mutable shared state introduces the possibility of data races and other kinds of concurrency bugs.  These can be tricky to reason about.

Multi-threaded programming makes it easy to have plan interference problems.  Programmers tend to think in a single-threaded way: they think about a single sequential path of execution.  When they're writing the code for a particular function/method/module, they build in their head a "plan" of the operations/actions they want to have happen, typically based on a single-threaded mental model (e.g., based on the implicit assumption that nothing else will interrupt them in the middle of this sequence of actions or concurrently modify their internal state).  However, when you have multiple threads with mutable shared state, they can cause unexpected interference while the code is in the middle of execution (changing something out from under the code while it is in the process of executing the programmer's plan).

For example, here is one classic example of plan interference.  Imagine you have a publish-subscribe data structure that lets clients register themselves as observers, and delivers events to all registered observers.  Imagine its code is in the middle of delivering an event to the observers, one by one, and the code of one of the observers happens to mutate the underlying state; this mutation might cause the notifications to the other observers to happen in the wrong order, or to expose an inconsistent state to them.

Further reading

For a more general description of the plan interference problem and more general discussion of why multi-threaded programming is more error-prone, I recommend the following papers:

The Problem with Threads.  Edward A. Lee.  IEEE Computer, May 2006.
Concurrency Among Strangers: Programming in E as Plan Coordination.  Mark S. Miller, E. Dean Tribble, and Jonathan Shapiro.  TGC 2005.  (See especially Sections 1-4.)

Candidate solutions

Multiple candidate solutions have been proposed:

One possible solution is to avoid using threads, and program in a sequential single-threaded way.  This is how Javascript works in browsers, for instance.
Another is to use threads but avoid all mutable shared state.  For example, Erlang.
A third is to use message-passing rather than mutable shared state for interaction between the threads.  One can build systems based on the actor model.  For example, E.
A fourth is to use threads with mutable shared state, but just be really careful.  You can have systematic ways of locking shared data and preventing data races and avoiding plan interference and so on.

See also https://cs.stackexchange.com/a/27803/755 for similar ruminations (I borrowed some text from there).


Countability doesn't imply (un)decidability: the set of even numbers and the set of codings of Turing machines that halt on input zero are both countable but the first is decidable and the second isn't.

Conversely, for any finite alphabet $\Sigma$, the set $\Sigma^*$ of all finite strings over $\Sigma$ is countable, since each string can be seen as a natural number written in base $|\Sigma|$. Therefore, any language (i.e., any subset of $\Sigma^*$) is also countable.

The only place that uncountability comes in is that there are uncountably many different languages over any finite $\Sigma$. This gives an immediate proof of the existence of undecidable languages: there are uncountably many languages but only countably many Turing machines.


Should crossover operation in a genetic algorithm modify individuals in order to be "valid"?

In my experience, a well crafted operator that avoids or repairs constraint violations is nearly always far preferable to one that relies on selection alone to find feasible solutions.


Organisation and Architecture of Quantum Computers

What you describe as current computers is known as the von Neumann architecture. This approach is one of many ways to think about classical computation and there are other classical approaches that might or might-not have relevant generalizations to quantum computing. The von Neumann architecture seems to be unlikely to be relevant to quantum computing, due to its difficulty from both the theoretical and implementation side.

However, as I mentioned on cstheory there is an article on implementing a quantum von Neumann architecture. They do this via superconducting qubits, of course the implementation is very small, with only 7 quantum parts: two superconducting qubits, a quantum bus, two quantum memories, and two zeroing registers. This allows their quantum CPU to perform one-, two-, and three-qubit gates on qubits, and the memory allows (data) qubits to be written, read out, and zeroed. Implementing a quantum superposition of gates is very difficult, and so the program is stored classically.

More likely models of quantum computing to be implemented include: measurement-based, topological, and adiabatic models. Typical implementations of these models look more like physics experiments (which they are!) than computers. Some of the common strategies for implementation include trapped ions, quantum optics, and superconducting circuits.

The circuit approach has been placed on chips and in fact D-Wave (a spin-off from UBC in Vancouver) claims to have built quantum-like computers using the adiabatic model to implement quantum simulated annealing. They have managed to sell this computer to Lockheed Martin but their approach has been met with heavy skepticism.

Lastly, the NMR approach mentioned by @RanG. is interesting, but suspected to be not equivalent to full quantum-computing. It is equivalent to the one-clean qubit model (also known as DQC1) and suspected to be strictly weaker than full quantum computing.


One direction is easy: if $xy = yx$ then $x^2y^2 = xxyy = xyxy = (xy)^2$.

In the other direction, we split into cases. If $|x|=|y|$ then, as you mention, $x = y$.

If $|x|<|y|$ then let $y=y_1y_2$, where $|y_1|=|y|-|x|$ and $|y_2|=|x|$. We have $z = x^2y_1$ and $z = y_2y = y_2y_1y_2$. Since $|x| = |y_2|$, it follows that $x = y_2$. Substituting this, we obtain $y_2^2 y_1 = y_2y_1y_2$, and so $y_2y_1 = y_1y_2$. This implies that $xy = y_2y_1y_2 = y_1y_2y_2 = yx$.

If $|y| < |x|$, then notice that $(y^R)^2(x^R)^2 = (z^R)^2$ (where $w^R$ is the reverse of $w$) and $|y^R| < |x^R|$, so we can apply the previous case to deduce that $y^R x^R = x^R y^R$ and so $xy = yx$.

Let us use this opportunity to characterize when $xy=yx$, by proving that there exist a word $w$ and integers $n,m$ such that $x = w^n$ and $y = w^m$ iff $x^2y^2$ is a square.

One direction is easy: if $x = w^n$ and $y = w^m$ then $x^2y^2 = w^{2n+2m} = (w^{n+m})^2$.

In the other direction, we use induction on $|x|+|y|$. The base case $x=y=\epsilon$ is trivial. For the inductive case, we split into cases. If $|x| = |y|$ then $x = y$ and so we can take $w = x = y$.

If $|x| < |y|$ then as before we get that $y = y_1 x = x y_1$, which implies that $y_1^2 x^2 = (y_1 x)^2$. The inductive hypothesis shows that there exist $w,n,m$ such that $y_1 = w^n$ and $x = w^m$. Then $y = y_1 x = w^{n+m}$.

We have shown that $xy = yx$ iff there exists a word $w$ and integers $n,m$ such that $x = w^n$ and $y = w^m$.

Equivalently, let us define the radical $\sqrt{x}$ of a word $x$ as the shortest word such that $x$ is a power of $\sqrt{x}$. Then $xy = yx$ iff $\sqrt{x} = \sqrt{y}$.

Indeed, if $\sqrt{x} = \sqrt{y}$ then clearly $xy = yx$. Conversely, suppose that $xy = yx$. Then there exist $w,n,m$ such that $x = w^n$ and $y = w^m$. We can assume that $w = \sqrt{w}$. I claim that $\sqrt{x} = w$. Otherwise, there exists a word $z$ shorter than $w$ and an integer $\ell$ such that $x = z^\ell$. The word $x$ thus has both $|w|$ and $|z|$ as periods ($p$ is a period of $x$ if $x_i = x_{i+p \bmod |x|}$ for all $i$), and so $|w| \bmod |z|$ is also a period. If $|w| \bmod |z| \neq 0$ then this contradicts the fact that $z$ is the radical of $x$ (since $x$ is a power of $x_1 \ldots x_{|w| \bmod |z|}$). If $|z|$ divides $|w|$ then $w = z^{|w|/|z|}$, contradicting the assumption $w = \sqrt{w}$. We reach a contradiction either way, and so $\sqrt{x} = w$. By the same reasoning, $\sqrt{y} = w$, and so $\sqrt{x} = \sqrt{y}$.


Decomposition of the set of computable functions into base functions

Unlambda is an example of a Turing-complete programming language that implements your requirements.

Unlambda has only one type, functions. They are also its only basic syntactic elements. In particular there are no variables.
Its expressive power only requires two base terms, s, and k. They would be your base $B$. k takes two arguments and returns the first, while s takes three arguments, and applies the result of applying the first one to the third one, to the result of applying the second one to the third one.
It has an additional construct, `, which represents function application. It would be your binary operator $(\cdot)$. It is written in a prefix manner.
So for any term X, Y and Z we have ``kXY = X, and ```sXYZ = ``XZ`YZ. These simple rules, believe it or not, are sufficient to make Unlambda Turing-complete.
Unlambda has a few more built-ins but they are just here to make the programmer's life easier (although mentioning easy anywhere in the context of this language is probably an overstatement).

Natural numbers can be represented using Church's method, e.g. $3$ can be written as ``s``s`ksk``s``s`kski (note i, the identity, can be written as ``skk). Pretty simple, no? Recursion can be defined by building a fixed point combinator, and from there the usual techniques can be applied to define more and more complex functions until an universal Turing machine has been simulated.

This language is based on SKI combinator calculus, which itself finds its source in Combinatory Logic. There is a simple mapping between the Lambda and SKI calculi, which luckily makes proving Turing completeness much easier than actually doing the work!

Now that I've introduced the programming language, which is the most interesting part and the crux of this answer, let's go through the tedious details of how to use it to formally answer your question.

First define an embedding $\phi$ of unlambda programs (restricted to s and k) into the natural numbers. We could use base-4 encoding by mapping its alphabet $\Sigma = \{\text{k}, \text{s}, \text{`}, \text{^}\}$ with $\{0, 1, 2, 3\}$ ($\text{^}$ is the start-of-string character). So for example $\phi(k) = \phi(\text{^k}) = 30_4 = 12$, and $\phi(i) = \phi(\text{^``skk}) = 322100_4 = 3728$.
We can then define $\phi^{-1}$ as the opposite operation, except that for convenience, we'll remove the starting $\text{^}$. So $\phi^{-1}(12) = \text{k}$
Let's also define an unlambda evaluation function $\text{uneval}$, partially defined on $\mathbb{N}\times\mathbb{N}$ and mapping to $\mathbb{N}$. For any $p$, $q$, $\text{uneval}(p,q)$ is defined as the number of stars printed when compiling and running $\text{``}||\phi^{-1}(p)||church(q)||.*$ as an Unlambda program, where $church(q)$ is the representation of the $q$-th church numeral in Unlambda, $.*$ is the Unlambda function which prints one star, and $||$ represents string concatenation. If the Unlambda program thus defined doesn't compile or never halts, then $\text{uneval}$ isn't defined on $(p,q)$.
Then define the following functions

$k : \mathbb{N} \to \mathbb{N}, n \mapsto 2\phi(\text{^k})+1 = 25$
$s : \mathbb{N} \to \mathbb{N}, n \mapsto 2\phi(\text{^s})+1 = 27$
$init : \mathbb{N} \to \mathbb{N}, n \mapsto 2n$

Let $B = \{k, s, init\}$
Define $h : \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ as follows

$h(2p, n)$ is undefined
$h(2p+1,2q+1) = 2\phi(\text{^`}||\phi^{-1}(p)||\phi^{-1}(q))+1$, if $\phi^{-1}$ is defined on $p$ and $q$, and undefined otherwise
$h(2p+1,2q) = \text{uneval}(p,q)$, if $\text{uneval}$ is defined on $(p,q)$

Define $(\cdot)$ as $(f\cdot g)(n) = h(f(n),g(n))$.

Using these definitions, we have

$h \in C_M$, because $\phi$, $\phi^{-1}$, $||$, $\text{uneval}$ and basic arithmetic are all computable.
and $\forall f,g \in C_M : \forall x \in \mathbb{N} : (f\cdot g)(x) = h(f(x), g(x))$, by definition of $(\cdot)$

Finally, $(B, \cdot)$ generates $C_M$ entirely, because

Unlambda (restricted to s and k) is Turing-complete, so I can build a (restricted) Unlambda function for any computable function in $C_M$.
I can build a constant function whose value is the representation of that Unlambda function using $s$, $k$ and $(\cdot)$. For example, for add1 =  `s``s`ksk, I can build $s\cdot((s\cdot(k\cdot s))\cdot k)$ whose constant value is $2\cdot3212212010_4+1 = 1889033$
I can build a function that evaluates any function $f$ built by the above process on $\mathbb{N}$, simply as $f \cdot init$.


Determine image of hypercube under linear map

I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in An Efficient Algorithm for Generating Zonohedra (PostScript file) by Paul Heckbert.


Do lossless compression algorithms reduce entropy?

A lot of casual descriptions of entropy are confusing in this way because entropy is not quite as neat and tidy a measure as sometimes presented. In particular, the standard definition of Shannon entropy stipulates that it only applies when, as Wikipedia puts it, "information due to independent events is additive."

In other words, independent events must be statistically independent. If they aren't, then you have to find a representation of the data that defines events in ways that make them truly independent. Otherwise, you will overestimate the entropy.

To put it yet another way, Shannon entropy only applies to true probability distributions, and not to random processes in general. For concrete examples of processes that don't fit the assumptions of Shannon entropy, consider...

Markov processes

A Markov process generates a series of events in which the most recent event is sampled from a distribution that depends on one or more previous events. Obviously a huge number of real-world phenomena are better modeled as Markov processes than as discrete, independent probability distributions. For example: the text you're reading right now!

The naively calculated Shannon entropy rate of a Markov process will always be greater than or equal to the true entropy rate of the process. To get the true entropy of the process, you need to take into account the statistical dependence between events. In simple cases, the formula for that looks like this:

$$ H(\mathcal{S}) = - \sum_i p_i \sum_j  \  p_i (j) \log p_i (j) $$

This can also be represented like so:

$$ H(Y) = - \sum_{ij} \mu_i P_{ij} \log P_{ij} $$

Again quoting Wikipedia, here "$\mu_i$ is the asymptotic distribution of the chain" -- that is, the overall probability that a given event will occur over a long horizon.

This is all a complicated way of saying that even when you can calculate the overall probability of a given event, certain sequences of events are more likely than others to be generated by a Markov process. So for example, the following three strings of English words are increasingly less likely:

They ran to the tree
The tree ran to they
Tree the they to ran

But Shannon entropy will assess all three strings as equally likely. The Markov process entropy takes the difference into account, and as a result, it assigns a lower entropy rate to the process.

Entropy rates are model-dependent

If you zoom way out, here's the big picture: the entropy rate of a given sequence of events from an unknown source is model-dependent. You'll assign a different entropy rate to a particular series of events depending on how you model the process that generated them.

And very frequently, your model of the process isn't going to be quite correct. This isn't a simple or easy to solve problem. In fact, in general, it is impossible to assign a true entropy rate to a sufficiently long and complex sequence of events if you don't know what the true underlying process is. This is a central result in algorithmic information theory.

What it means in practice is that given an unknown source of sequences of events, different models will yield different entropies, and it's impossible to know which is correct in the long run -- although the one that assigns the lowest entropy is probably the best.


(I completely removed the previous answer, which was applicable only to this particular example).

Your grammars seem to be known as ground term rewriting systems nowadays.

They are rather old. They might be introduced by W.S. Brainard: Tree generating regular systems. Inform. and Control 14 (1969) 217-231.

Concerning your question. I googled a paper of a good old collegue. Joost Engelfriet: Derivation trees of ground term rewriting systems. If my hunch, that this is the correct model, is correct, I like to cite Theorem 4 of that paper:

  For every extended ground tree grammar $G$ a regular tree grammar $G'$ with $L(G') = L(G)$ can effectively be constructed.

It is in the section called "New proofs for old results", so that must be a known result.


Let $m$ and $n$ be the lengths of two given strings,
Linear time assuming the size of the alphabet is constant.
Yes, the longest common substring of two given strings can be found in $O(m+n)$ time, assuming the size of the alphabet is constant.
Here is an excerpt from Wikipedia article on longest common substring problem.

The longest common substrings of a set of strings can be found by building a generalized suffix tree for the strings, and then finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it.

Building a generalized suffix tree for two given strings takes $O(m+n)$ time using the famous ingenious Ukkonen's algorithm. Finding the deepest internal nodes that come from both strings takes $O(m+n)$ time. Hence we can find the longest common substring in $O(m+n)$ time.
For a working implementation, please take a look at Suffix Tree Application 5 – Longest Common Substring at GeeksforGeeks
(Improved!) Linear time
In fact, the longest common substring of two given strings can be found in $O(m+n)$ time regardless of the size of the alphabet.
Here is the abstract of Computing Longest Common Substrings Via Suffix Arrays by Babenko, Maxim & Starikovskaya, Tatiana. (2008).

Given a set of $N$ strings $A = \{\alpha_1,\cdots,\alpha_N\}$ of total length $n$ over alphabet $\Sigma$ one may ask to find, for each $2 \le k\le N$, the longest substring $\beta$ that appears in at least $K$ strings in $A$. It is known that this problem can be solved in $O(n)$ time with the help of suffix trees. However, the resulting algorithm is rather complicated (in particular, it involves answering certain least common ancestor queries in $O(1)$ time). Also, its running time and memory consumption may depend on $|\Sigma|$.
This paper presents an alternative, remarkably simple approach to
the above problem, which relies on the notion of suffix arrays. Once
the suffix array of some auxiliary $O(n)$-length string is computed, one
needs a simple $O(n)$-time postprocessing to find the requested longest
substring. Since a number of efficient and simple linear-time algorithms
for constructing suffix arrays has been recently developed (with constant
not depending on $|\Sigma|$), our approach seems to be quite practical.

Here is the general idea of the algorithm in the paper above. Let string $\alpha$ be concatenation of all $\alpha_i$ with separating sentinels. Construct the suffix array for $α$ as well as its longest-common-prefix array. Apply a sliding window technique to these arrays to obtain the longest common substrings.


Proving at least $n-1$ comparisons are needed to test if an array is sorted

You can use a simple adversary argument (in Jeff's lecture note) to prove that every correct algorithm has to compare $a_i$ with $a_{i+1}$ for $i=0,1, \ldots, n−2$.

If it is not the case, you can carefully choose the values such that $a_{i+1} < a_{i}$, without violating any other comparison results.

You are encouraged to fill the details.


The result that $\mathrm{MOD}_{2^m}\mathrm P=\mathrm{MOD}_2\mathrm P$ only applies when $m$ is constant. Thus, your strategy only works if $t$ is constant, which is a trivial case. You would need it to apply to $t\approx n^c$. (Actually, the argument works for $m=O(\log n)$, but this is still not enough.)
Specifically, the reduction of $\mathrm{MOD}_{2^m}\mathrm P$ to $\mathrm{MOD}_2\mathrm P$ relies on the simple number-theoretic fact that
$$2^m\mid s\iff2\mid s\land2\mid\binom s2\land2\mid\binom s{2^2}\land\dots\land2\mid\binom s{2^{m-1}}.$$
If $s$ counts the number of objects satisfying some property, then $\binom s{2^r}$ counts the number of $2^r$-element sets of objects with that property.
That is, given a language $L\in\mathrm{MOD}_{2^m}\mathrm P$ of the form
$$w\in L\iff2^m\mid\#\{x<2^{n^c}:R(w,x)\},$$
where $n$ denotes $|w|$ and $R\in\mathrm P$, we can express $L$ as
$$w\in L\iff\forall r<m\ 2\mid\#\{(x_0,\dots,x_{2^r-1})\in[0,2^{n^c})^{2^r}:R_r(w,x_0,\dots,x_{2^r-1})\},$$
where
$$R_r(w,x_0,\dots,x_{2^r-1})\iff x_0<\dots<x_{2^r-1}\land\forall i<2^r\:R(w,x_i).$$
(These $m$ instances of $\oplus\mathrm P$ can be then combined to a single $\oplus\mathrm P$ predicate as $\oplus\mathrm P$ is closed under poly-time Turing reductions; in fact, even $\mathrm{\oplus P^{\oplus P}=\oplus P}$.)
As long as $m=O(\log n)$, the sequences $(x_0,\dots,x_{2^r-1})$ can be represented with $n^{O(1)}$ bits, and the predicates $R_r$ are computable polynomial time, but neither is true for larger $m$.


Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

You could break down the language into simpler parts, e.g., you can generate languages separately for $a^i$ and $b^na^n$, then concatenate them in the end (we know that CFG's are closed under concatenation).

In your case, you can do

  A $\rightarrow$ aA | $\epsilon$

to generate $a^i$, and

  B $\rightarrow$ bBa | $\epsilon$

to generate $b^na^n$, then concatenate by doing:

  S $\rightarrow$ AB


Why can no task have a utilization rate greater than one?

It appears that you have a periodic scheduling system on a single processor where task $i$ must run for $C_i$ seconds out of every $T_i$.

If this is the case, then the requirement that $\tfrac{C_i}{T_i}\le1$ is just saying that $C_i\le T_i$, i.e., you're not saying something like "Task 3 must run for 15 seconds out of every 10 seconds", which is physically impossible.

It looks like there's actually a mistake in the statement of the theorem. I think it should say that the utilization of task $i$ is given by $U_i=\tfrac{C_i}{T_i}$, then define the total utilization to be $U = \sum_{i=1}^n U_i$ and then require the stronger condition that this $U$ satisfies $U\leq 1$. That is, you don't just require each task individually to use at most 100% of your resources: you require the whole ensemble to use at most 100%. You can think of it this way: if I'm supposed to spend $p_1\%$ of my time on task 1, ..., and $p_n\%$ of my time on task $n$, I'd better not be committing more than 100% of my time!

The physical significant of defining $\hat{T} = \mathrm{lcm}(T_1, \dots, T_n)$ is that it's the shortest period of time in which every task is supposed to run an integer number of times. It's not essential that you consider the shortest such period: the proof would work fine if you used any period in which every task needs to run an integer number of times. Perhaps it would be conceptually easier to set $\hat{T} = \prod_{i=1}^n T_i$ instead.


How to find the asymptotic runtime of these nested loops?

$j$ satisfies the recurrence $j_k = j_{k-1}+k$. Note that another sequence, $s_k = k^2$ satisfies $s_k = s_{k-1} + 2k-1$.

$$j_k = \sum_{i=1}^k i = \frac 1 2\sum_{i=1}^k 2i = \frac 1 2(s_k+k)$$

This should give you enough to find the largest $k$ such that $j_k < n$.


How to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$?

You can notice that $T(n) < 3T(n-2)$. This gives you the complexity as $O(3^{n/2})$. You can also observe that $T(n) > 2T(n-3)$. This gives you the complexity as $\Omega(2^{n/3})$. Now, you can at least tell that the complexity is an exponential one.


How do you apply a multi qubit gate to specific qubits in a multi qubit circuit?

Imagine that the qubits were $0$ and $1$ (or $1$ and $2$, depending on your numbering scheme). You want to apply the Hadamard gate on the first two coordinates, and nothing – the identity – on the rest. This leads to a block diagonal matrix whose second block is the $4\times 4$ identity.

Now make the necessary arrangements for the qubits you're interesting it.


Chomsky normal form and regular languages

Assuming that $B$ is regular, then $L(G)=B \cup \lbrace w \in L(G) \mid \vert w \vert \leq 2^k \rbrace$ is also regular because the union of a finite number of regular languages is regular  (especially, $k$ is a constant as the number of variables in the Chomsky normal form).

This can not be true in general because there are context free languages which are not regular.


Is the lambda calculus referentially transparent?

Quoting the paper referenced in that thread, i.e. What is a Purely Functional Language by Amr Sabry:

  Finally, two informal definitions of purity: referential transparency
  and independence of order of evaluation, do not have universally
  agreed-upon definitions and are not considered any further. (See,
  however, the treatment of referential transparency by Søndergaard and
  Sestoft (1990).)

This refers to the paper Referential Transparency, Definiteness, and Unfoldability by Harald Søndergaard and Peter Sestoft.

So, first off, there is no "right" definition of referential transparency (especially of an entire language as opposed to a single context) to which to contrast to "wrong" definitions. Secondly, the devil is in the details, which is part of why there is no universally agreed-upon definition. Probably the main factor as alluded to by the original Reddit post is: what notion of equality should we use? Obviously using contextual equivalence would be an absurd choice for this purpose. It would make all contexts referentially transparent tautologically. Another factor is what is the domain of things we're considering plugging into the context: raw terms, $\alpha$-equivalence classes of terms, terms-in-context, closed terms? To extend referential transparency to a whole language further requires specifying what exactly the set of contexts is. Finally, often the term "referential transparency" refers (at least roughly) to what Søndergaard and Sestoft call "unfoldability". This is the ability to replace a variable with what it is bound to without changing meaning.  For the pure untyped lambda calculus, this just means the full $\beta$ rule holds which is true for call-by-name but not call-by-value.

In their paper, Søndergaard and Sestoft essentially answer the above questions as follows (extrapolating to the untyped lambda calculus): equality is denotational equality with respect to a given semantics; the domain is raw terms (or perhaps $\alpha$-equivalence classes of terms, whichever the semantics operates over); contexts are as follows: $$\mathcal{K}[\_] ::= \_\mid (\mathcal{K}[\_]) E \mid E (\mathcal{K}[\_]) \mid \lambda x.(\mathcal{K}[\_])$$ where $x$ stands for any variable. At any rate, the upshot of these choices is that your example and psygnisfive's example fail to demonstrate a violation of referential transparency (in this sense) because the terms you are plugging in to the context are not denotationally equal in the first place. In fact, any compositional denotational semantics will guarantee that all contexts are referentially transparent in this sense. Indeed, the example from the paper of a non-referentially-transparent language also has a non-compositional denotational semantics which is "fixed" by making it compositional.

The issue with this definition for more elaborate languages, particularly languages with side-effects, is that we can almost always give a compositional semantics to a programming language. Certainly we can for the lambda calculus extended with mutable state, for example. This leads to the notion not having much bite. The lambda calculus with mutable state equipped with a compositional denotational semantics will be referentially transparent in the above sense because two expressions that have potentially different side-effects won't be considered equal in the first place.


There is no relativizing technique to show that $\mathrm{IP}$ is closed under complement.

Clearly, $\mathrm{NP}\subseteq\mathrm{IP}$.

Fortnow and Sipser gave an oracle relative to which $\mathrm{co}$-$\mathrm{NP}$ does not have interactive proof system.

So, you have to study the arithmetization technique that settles down this conjecture (long ago).

Are there interactive protocols for CO-NP


Finding Statistical Signifigance for a Classifier

You can take a look at McNemar's Test or a Bayesian Testing. If you are comparing two or more classifiers, you can perform a to evaluate their performances.

Evaluating learning is actually a pretty wide research topic. A good book to refer to would be Japkowicz-Shah. This is a really nice book on evaluating classifiers and performances. To get some idea about the topic, take a look at this ICMLA talk.

If this is a one time thing, get done with McNemar or Bayesian test, however if you continue to work in the field, do see the book.

P.S. ask you boss if he means any real stat tests (like those mentioned above). Once I was working on a classifier, my professor asked me to evaluate its performance, after a long period of pain and agony of cluelessness, it turned out he just wanted me to test it on other 'toy problems'.


Category theory structures to describe topics and queues

A data structure Queue is very close to the concept of a List, however a Queue is a First-In-First-Out (FIFO) data structure. The available operations to interact with the List structure then, are limited to enqueue() and dequeue() (it is not a case in fact that a queue can be implemented using a List structure).

In the context of Category Theory you might find a parallelism between a List data structure and a Free Monoid https://ncatlab.org/nlab/show/free+monoid which can provide a recursive implementation of a List data structure. The same category equipped with ad-hoc morphism can be used to describe the behaviour of Stacks and Queues data structure.

In the case of Kafka and other similar queue services, besides the complications coming from the distributed case scenario, they don't really resemble the usual case of a Queue data structure. In fact, such a data structure is always supposed to be finite - they are rather implementing the concept of a stream (which could be finite or infinite) under the access condition of a queue (to be completely precise, for Kafka that's not even completely true, since you have the ability to access elements arbitrarily from the topic/queue using an offset). To model such kind of streaming structures an approach similar to this https://ncatlab.org/nlab/show/stream could be used.


Google Deep Dream has these understandings?

"Understanding" is a human concept ie a term used for human psychology. It may be used with machine learning systems informally. However, being flexible in interpretation of your question & not strictly literal, there is of course an open scientific question/ research program of how these systems actually "work". In ML, one "trains" systems and the systems exhibit the desired "behavior" but some of this relates to an old psychology theory of "behaviorism" where only the observed behavior is seen to be relevant and attributing particular mental states is seen to be something of a problematic/nonobjective ("anthropomorphic") projection by the experimenter.

With that caveat, the current scientific understanding of (deep) neural networks, with lots of related research and active/ongoing, is roughly that they build/ use feature detection. This overlaps with neurobiology theory and knowledge of the visual cortex in mammals. The exact features that are evolved (via "emergence") in the network are somewhat unique to each network, but general trends have been observed also, namely orientation columns (eg esp in "lower levels"). These types of features are also known to arise with sparse coding techniques/ mathematics.

There is a hierarchy of features. Higher level features are built out of lower level features inside the network hierarchy.

So the answer is roughly "yes", the network develops "spatial/ visual concepts" in the form of  features. The networks recognize structural patterns in common across many images of real-world objects. These types of patterns include different/ various orientations, placements, relative spatial relationships, and sometimes more abstract "styles" of images found eg in paintings/even architecture etc.


There exists an algorithm to find grammar of complement of a function?

Contrary to what you wrote, context-free languages are not closed under complement.  See Examples of context-free languages with a non-context-free complements for some examples.  As a result, there is no such algorithm.

Also: It's decidable whether $L(S)=\emptyset$, but it's not decidable whether $L(S)=\Sigma^*$.  If you could compute the complement, then you could decide the latter using the algorithm for the former.

In contrast, deterministic context-free languages are closed under complement, and the proof of that fact likely identifies an algorithm that will work when you have a deterministic context-free language.  Another way to handle it: convert to a deterministic pushdown automaton, then it is clear how to complement it.


Do all decidable problems lie in the class NP?

No to the question in your title; yes to the question in the body of your post.

By the non-deterministic time hierarchy theorem, every decidable NEXP-hard decision problem is "a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable".


Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones?

Before giving the answers, some discussion on your direction for the proof:

It is highly unlikely that a proof of this claim would use the containment $REG\subseteq CFL$, since the pumping lemma is not an exact characterization, and if a language satisfies the regular pumping lemma, it doesn't proof that the language is regular.

Thus, the proof will have to go into the "guts" of the lemmas.
Now for the proof:

Consider a language $L$ that satisfies the regular pumping lemma. Thus, there exists some $p>0$ such that for every word $w\in L$, if $|w|>p$, then there exists a partition $w=xyz$ such that $|xy|\le p$, $|y|>0$ and for every $i$ it holds that $xy^iz\in L$.

We want to prove that there exists some $q>0$ such that for every word $w\in L$, if $|w|>q$, then there exists a partition $w=uvstr$ such that $|vst|\le q$, $|vt|>0$ and for every $i$ it holds that $uv^ist^ir\in L$.

Seeing things stated as above, the rest is just "pattern matching":
Let $q=p$, and consider a word $w\in L$ such that $|w|>q$, then there exists a partition $w=xyz$ as above. Let $u=x,v=y,s=\epsilon,t=\epsilon$, and $r=z$. Clearly $uvstr=xyz=w$. Also, $|xy|\le p$, so $|vst|=|y|\le p$ and $|y|>0$ so $|vt|=|v|=|y|>0$. Finally, for every $i$ it holds that
$$uv^ist^ir=xy^iz\in L$$
and we are done.


Is the Projection Matrix estimated using least-squares pose specific?

Yes, that is correct.  If you move the camera, the projection matrix changes.

However, fortunately you don't have to start from scratch.  If you know the new position of the matrix relative to the old one, you can adjust the projection matrix.  Or, if you don't know how the camera has moved, you'll need to re-estimate the extrinsic parameters, but the intrinsic parameters will remain unchanged (the projection matrix is the composition of an intrinsic matrix and an extrinsic matrix, and only one depends on the camera's position).

See https://en.wikipedia.org/wiki/Camera_matrix and https://en.wikipedia.org/wiki/Camera_resectioning.


Suggest a Data Structure To Manage 2 Sets

You are on the right approach to attach "more data" to a balanced search tree.

For all $x\in A\cup B$, let $$d(x)=\left | \left \{ y\in A: y<x \right \} \right | - \left | \left \{ y\in B: y>x \right \} \right |,$$ which is an increasing function on $x$.

For simplicity, let us assume all elements are distinct first. We can use a balanced search tree $T$ to store all elements in $A$ and $B$, keeping track of whether each element comes from $A$ or $B$.

We will also store $(x_\ell, \delta_\ell)$ , where $x_\ell$ is the largest element $x$ in $T$ such that $d(x)\le0$ and where $\delta_\ell=d(x_\ell)$.
We will also store $(x_r, \delta_r)$ , where $x_r$ is the smallest element $x$ in $T$ such that $d(x)\ge0$ and where $\delta_r=d(x_r)$.

Either pair might not exist. However, at least one pair must be available, which is enough to identify the wanted $x\in A\cup B$, i.e., $d(x)=0$, if exists.

Suppose $v$ will be inserted into $T$. Here is a sketch of what to do to maintain the data structure. The idea is simply to move $x_\ell$ or $x_r$ to its neighbor one or two times.  Several obvious boundary cases such as when $d(x)>0$ for all $x$ in $T$ before or after $v$  is inserted have been skipped.

Insert $v$.
Update $(x_\ell, \delta_\ell)$ as the following.

Do the following.

find $x_{-1}$, the predecessor of $x_\ell$. Compute $d(x_{-1})$.
find $x_{-2}$, the predecessor of $x_{-1}$. Compute $d(x_{-2})$.
find $x_{1}$, the successor of $x_\ell$. Compute $d(x_1)$.
find $x_{2}$, the successor of $x_1$. Compute $d(x_2)$.

Let $x_{\text{new}}$ be the largest element $x$ among $x_{-2}, x_{-1}, x_\ell, x_{1}, x_{2}$ such that $d(x)\le0$. Update $(x_\ell, \delta_\ell)$ to $(x_{\text{new}}, d(x_{\text{new}}))$

Update $(x_r, \delta_r)$ similarly, which should take $O(\log n)$ time as well.

Any kind of balanced search trees can be used as long as the insertion, finding the predecessor and finding the successor can be done in $O(\log n)$. In particular, we can use AVL tree or red-black tree.

Step 1 takes $O(\log n)$ time.
Each search for predecessor or successor in Step 2 takes $O(\log n)$ time. Each computation of $d(*)$ takes $O(1)$ time, as we know $d(x_\ell)$. For example, $d(x_{-1})=d(x_\ell)-\lambda_A(x_{-1})-\lambda_B(x_\ell)$, where $\lambda_A(x_{-1})$ is 1 if $x_{-1}\in A$ and 0 otherwise. $\lambda_B(x_{\ell})$ is 1 if $x_{\ell}\in B$ and 0 otherwise. Similarly, $d(x_1)=d(x_\ell)+\lambda_A(x_\ell)+\lambda_B(x_1)$. So step 2 takes $O(\log n)$ tims.
Similarly, step 3 takes $O(\log n)$ time.

When there are duplicated elements in $A$ and $B$, the idea is similar but somewhat more complicated. A balanced search tree $T$ will store all distinct elements in $A$ and $B$. Each node will store

a distinct element $x\in A\cup B$,
how many time that element appears in $A$,
and how many time that element appears in $B$.

The order of the node is determined by the order of that element. Attached to the whole $T$ are the two pairs $(x_\ell, \delta_\ell)$ and $(x_r, \delta_r)$ defined the same as above.

Exercise 1. Refine the algorithm so that at any point of time, only one of the pairs $(x_\ell, \delta_\ell)$ and $(x_r, \delta_r)$ is maintained.

Exercise 2. Refine the algorithm so that only 1 or 2 cases in step 2.1 are needed by considering $v<x_\ell$ or not, $v=x_{-1}$ or not, $v\in A$ or $v\in B$, etc.

Exercise 3. Consider using one balanced search tree for elements in $A$ and another one for elements in $B$ instead of using one for both of them. Will it work?


Demonstration that every finite set is computable

Given any finite set, it's trivial to write a program that accepts exactly the members of the set: just compare the input against each element of the set in turn.


The result is in #P.  Suppose there are 50 states, and each state has 10 cities.  Then how many cities are there in total?

Now suppose we have a polytime verifier for states: $S(x)$ outputs 1 iff $x$ is a state.  We also have a polytime verifier for cities: $C(x,y)$ outputs 1 iff $y$ is a city in state $x$.  Then counting the number of states is in #P: it's the number of $x$ such that $S(x)=1$.  If you think a bit, you can see that counting the number of cities is also in #P: it's the number of pairs $(x,y)$ such that $S(x)=1 \land C(x,y)=1$.  Can you come up with a polytime verifier $V$ such that $V(x,y)=1$ iff $x$ is a state and $y$ is a cities in that state?  I bet you can.  Consequently, counting the number of such pairs (i.e., counting the number of cities) is in #P.

Now apply the same idea to your problem, and you should be able to figure out the answer.


Transforming an array into one with descending order

There is an efficient dynamic programming solution if the input domain is small.

Let $C_i(v)$ be the cost of increasing/reducing elements such that $\hat a_i = v \wedge (\forall j >i)[\hat a_{j} \leq v]$.

It should be obvious that $C_n(v)$ is simply $|a_n - v|$, and thus computing $C_n$ completely is easy.

Then $C_{i}(v)$ is $|a_i - v| + \min(C_{i+1}(0), C_{i+1}(1),\dots,C_{i+1}(v))$. Using this we can compute $C$ as a table, using $C_{i+1}$ to fill $C_i$, working backwards all the way to $C_1$. Then choosing the minimal element of $C_1$ and working forwards again you have found the solution.


Fastest search algorithm in a sorted list with certain error rate-limiting constraints

For simplicity of analysis I will say that 'too high' is the error condition, which is just the problem inverted, $64^{64}-n$. I also assume that requests are instant.

It takes some thinking, but waiting is never an optimal strategy. So we view the problem as just a series of guesses, done in blocks of 13 (unless we hit the 90 second timeout). Instead of timeouts our penalty will be losing guesses, and instead of minimizing time we will minimize guesses used. I write $V_2$ for the value of a guess (in bits) when we are in the state where we guessed too high twice in this block. Similarly I will write $V_1, V_0$. I write $g \in \{0\dots13\}$ for the number of guesses left in the block, including the current one.

I will evaluate a strategy where we pick three numbers $p_0$, $p_1$, $p_2$, where each $p$ encodes how skewed the binary search is for when we've guessed $0$, $1$ or $2$ wrong times in this block.

The expected value (in bits) of a guess $p \in [0, 1]$ (where $0$ is the lowest guess and $1$ is the highest) is the binary entropy function $H(p) = -p \log_2 p - (1 - p)\log_2(1-p)$.

However, for $V_2(g)$, if we guess wrong we lose the rest of this block and the next two blocks, $B$ is the value of a block in bits.

$$V_2(g) = H(p_2) - 2p_2B - p_2\sum_{k=1}^{g-1}V_2(k)$$

If we write $E_2(g)$ as the value in bits of being in state $2$ with $g$ guesses left:

$$E_2(g) = \sum_{k=1}^{g} V_2(k) = \sum_{k=1}^g \big( H(p_2) - 2p_2B - p_2E_2(k-1)\big ) $$
$$E_2(g) = g(H(p_2) - 2p_2B) - p_2 \sum_{k=1}^g E_2(k-1)$$

This recurrence can be solved:

$$E_2(g) = (H(p_2)/p_2 - 2B)(1-(1 - p_2)^g)$$

Similarly, if we guess wrong for $V_1$, we lose our advantage from state $1$:

$$V_1(g) = H(p_1) - p_1(E_1(g-1) - E_2(g-1))$$
$$E_1(g) = \sum_{k=1}^{g} V_1(k) = \sum_{k=1}^{g} \big( H(p_1) - p_1(E_1(k-1) - E_2(k-1))\big )$$

$$E_1(g) = g(H(p_1) - p_1E_2(g-1)) - p_1\sum_{k=1}^{g}E_1(k-1)$$

$$E_1(g) = (H(p_1)/p_1 - E_2(g-1))(1-(1 - p_1)^g)$$

And $E_0$ is directly analogous. Now, since $B = E_0(13)$ we have:

$$E_0(g) = (H(p_0)/p_0 - E_1(g-1))(1-(1 - p_0)^g)$$
$$E_1(g) = (H(p_1)/p_1 - E_2(g-1))(1-(1 - p_1)^g)$$
$$E_2(g) = (H(p_2)/p_2 - 2E_0(13))(1-(1 - p_2)^g)$$

Oh boy... With a CAS I found:

$$E_0(13) =\frac{1}{2P_0P_1P_2 + 1} \left(\frac{P_0H(p_0)}{p_0} - \frac{P_0P_1H(p_1)}{p1} +\frac{P_0P_1P_2H(p_2)}{p_2}\right)$$

where $P_0 = 1-(1-p_0)^{13}$, $P_1 = 1-(1-p_1)^{12}$ and $P_2 = 1-(1-p_2)^{11}$. This is the expression we want to maximize.

Numerically  maximizing this expression gives $E_0(13) \approx 6.72$ bits with:

$$p_0 \approx 0.1854365,\quad p_1 \approx 0.1422816,\quad p_2 \approx 0.0000899$$

This means that in order to get $\log_2(64^{64}) = 384$ bits we expect to need 57.1 blocks, or 1714.3 seconds.

This isn't even optimal yet, though. $p_0, p_1, p_2$ should actually be functions of $g$ (consider that if you are on your last guess in state $0$, then you can be really greedy and not get punished). I will see if I can improve my answer.


Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call.  For example, the function

int f(int x, int y) {
  if (y == 0) {
    return x;
  }

  return f(x*y, y-1);
}

is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive:

int g(int x) {
  if (x == 1) {
    return 1;
  }

  int y = g(x-1);

  return x*y;
}

since it does some computation after the recursive call has returned.

Tail recursion is important because it can be implemented more efficiently than general recursion.  When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function.  This means that we need a call stack whose size is linear in the depth of the recursive calls.  When we have tail recursion we know that as soon as we return from the recursive call we're going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller.  That means we don't need a call stack at all for all of the recursive calls, and can implement the final call as a simple jump, which saves us space.


How is the control unit affected by pipelining?

One, the control unit is pipelined. Two, because everything is pipelined, it's busy all the time and must be able to produce at least one instruction per cycle. Third, if you have a processor capable of executing more than one instruction per cycle, the control unit must be capable of handling more than one instruction per cycle, which includes decoding multiple instructions per cycle, preloading memory containing instructions before they are needed etc.