How to efficiently compute the most isolated point? Given a finite set $S$ of points in $\mathbb R^d$, how can we efficiently compute a "most isolated point" $x\in S$?

We define a "most isolated point" $x$ by

$$x = \arg\max_{p \in S} \min_{q \in S \setminus \{p\}} d(p,q)$$

(I used the $x=\arg\min$ notation even though it is not necessarily unique. Here $d$ denotes the euclidean distance.)
So in other words we're looking for a point with the largest distance to the closest neighbour.

A naive algorithm would be computing all pairwise distances, finding the neighbour with the least distance for every point and then finding the maximum of these. This is takes $O(n^2)$ operations, but can we do better than that?

Use any algorithm for all nearest neighbors; then you can trivially solve your problem.  Such an algorithm finds, for each data point, its nearest neighbor.  The most isolated point is the one whose nearest neighbor is farthest away, so once you've solved all nearest neighbors, you can find the most isolated point by a simple linear scan.

Apparently all nearest neighbors can be found in $O(n \log n)$ time; see the references on Wikipedia.  Or, if you want something to implement, take any data structure for nearest neighbors, and for each point $p$, find its nearest neighbor.


Stuck on a combinations algo question There are x digits and y boxes where y is between 1 and x inclusive. I have to print all the possible digits in boxes (combinations) in any order.

For examples, if x = 5 and y = 2 we can have the following 4 combinations:

1234 5
123 45
12 345
1 2345

Similarly if x = 5 and y = 3

123 4 5
12 34 5
12 3 45
1 234 5
1 23 45
1 2 345

if x = 5 and y = 5 then there is only 1 combination

1 2 3 4 5

Both x and y are variable and I can't figure out even a brute force way of doing this. I have tried using three nested for loops but have no luck.

You can print numbers 1 to $x$ and print $y-1$ spaces between them in a brute force manner. The following algorithm does that:

function enumerate(string str, int s, int t, int y):
   /* base case: there is no space left and we print the string */
   if (y==0)
      string str2 = "";
      for i=s to t:
         str2.append(i);
       print str+str2;
       return ;

   /* recursive case: add one space and recursively call the function */
   for i=s to t:
      string str2 = "";
      for j=s to i-1:
         str2.append(j);
      str2.append("~");
      if (t-i >= y-1) call enumerate(str+str2, i, t, y-1);

You can call enumerate(str="", s=1, t=5, y=2) to print all combinations of numbers 1 to 5 and 2 spaces between them, which gives you a sorted embedding of numbers 1 to 5 in 3 boxes.


Amplification for Randomized Algorithms I'm trying to show Amplification works for randomized algorithms, and for randomized approximation algorithms.

Amplification for randomized algorithms:
Given a randomized algorithm with time complexity $f(n)$ and error probability $\frac{1}{4}$, show there is an algorithm that solves the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\varepsilon}\right)\right)$ run time, and error probability of $\varepsilon$, for a given $\varepsilon>0$.

I managed to show this running the original algorithm $k$ times, and choosing by majority vote the answer. Using Multiplicative Chernoff Bound (Which I've proven as well), I've shown $k\geq O\left(ln\left(\frac{1}{\varepsilon}\right)\right)$ gives us the required results.

Now I'm trying to do the same for approximation algorithms.

Amplification for randomized approximation algorithms: Given a randomized approximation algorithm that returns an $\varepsilon$-additive-approximation with a probability of $\frac{3}{4}$, with run time complexity of $f\left(n\right)$, show there is an algorithm that returns an $\varepsilon$-additive-approximation with a probability of $1-\delta$, for the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\delta}\right)\right)$ run time, for a given $\delta>0$.

The first thing that comes to my mind, is use a similar approach as before - run the original algorithm $k$ times, but this time instead of using majority vote, return the average.

I have to somewhow find a $k\geq O\left(ln\left(\frac{1}{\delta}\right)\right)$ such that $\mathbb{P}\left[\left|OPT-\frac{1}{k}\underset{i=1}{\overset{k}{\sum}}X_{i}\right|>\varepsilon\right]<\delta$.

I tried using the triangle inequality, then using union bound, but this doesn't lead me to being able to use Chernoff. In order to use Chernoff, I thought of defining an indicator random variable for each run of the original algorithm, stating if the result - $X_{i}$ is bad (that is, if $\left|X_{i}-OPT\right|>\varepsilon$), but this is where I get stuck.

Would appreciate any help. Thanks!

Use the median instead of the mean. The median can only be bad if more than half the samples are bad.

The problem with the mean is that the mean could be bad from a lot of the samples being a little bit bad, or from a few of the samples being really bad. However, in general, you don't know the probabilities of different degrees of sample badness; just the probability of bad-versus-good.


Why $P$ cannot have NULL string in Arden's Theorem? Arden's Theorem says that in the equation $R=Q+RP$, the $P$ cannot have NULL string. In this respect,the theorem will not be valid for the expression $R=Q+R(NULL+01)$. Am I correct? If so, then what will be the justification?

Here is the version of Arden's theorem on Wikipedia:

One solution of the language equation $R = Q+RP$ is $R = QP^*$.
If $\epsilon \notin P$, then this is the only solution.

When $\epsilon \in P$, there are more solutions. In fact, we can prove the following result:

The solutions of the language equation $R = Q+RP$, where $\epsilon \in P$, are $R=SP^*$ for all $S \supseteq Q$.

Proof. Let us first show that $SP^*$ is always a solution. Since $\epsilon \in P$, $RP = SP^+ = SP^*$. Since $SP^* \supseteq S \supseteq Q$, $Q + RP = Q + SP^* = SP^* = R$.
Let us now show that all solutions are of this form. Suppose that $R$ is a solution. Clearly $R \supseteq Q$. Since $\epsilon \in P$, this implies that $RP \supseteq R \supseteq Q$, and so $RP = Q + RP = R$. Induction shows that $RP^n = R$ for all $n \in \mathbb{N}$, and so $RP^* = R$. Since $R \supseteq Q$, this is a solution of the required form. $\square$


Range query for sum of vectors We have two sets of vectors of positive numbers, $X$ and $Y$ where for
$x\in X$ we write $x=(x_1,x_2,\ldots,x_k)$ and similarly for $y\in Y$
we write $y=(y_1,y_2,\ldots,y_k$).

We are given two vectors $l=(l_1,l_2,\ldots,l_k)$, and
$u=(u_1,u_2,\ldots,u_k)$ such that $l_i\le u_i$ for all $i$.

We want to find all pairs $(x,y)$, $x\in X$, and $y\in Y$ such that
$l_i\le x_i+y_i\le u_i$

Handwaving a bit, we can do this in a divide and conquer sort of way,
separating each set into pieces that are larger and smaller than
$l_i/2$ and throwing away the pairs where both are in the smaller
half.
This gives a recurrence
$$T(m,n) = T(m,n/2) + T(m/2, n/2) + c(m+n)$$
where $m=|X|$ and $n=|Y|$.  For equal size sets, this gives
$T(n,n) = O(n^{1.7})$, which is better than quadratic, but less than I
would hope for.

A similar question could be asked for three or more sets.

One approach would be to solve this using orthogonal range trees.  Orthogonal range trees allow range queries in $k$ dimensions.

Store the $n$ values of $Y$ in an orthogonal range tree.  The space complexity is $O(n (\lg n)^{k-1})$.

Next, for each $x=(x_1,\dots,x_k) \in X$, we're going to search for a matching $y \in Y$.  Notice that for $y$ to match this particular $x$, we must have $l_i - x_i \le y_i \le u_i - x_i$ for each $i$.  This means that $y$ must fall into the $k$-dimensional box $[l_1-x_1,u_1-x_1] \times \cdots \times [l_k-x_k,u_k-x_k]$.  So, we want to know if there is any element of $Y$ that falls within this box.  That's a $k$-dimension range query, which an orthogonal range tree can handle.

The time complexity is $O((\lg n)^k)$ for each range query.  We do $m$ range queries, so the total running time of this algorithm is $O(n (\lg n)^{k-1} + m (\lg n)^k)$.  Of course, there is a symmetry between $X$ and $Y$, so you can swap $m,n$ if that reduces the running time.

It is possible to reduce the asymptotic running time slightly further by using more sophisticated data structures and algorithms, but I don't know if they will actually help in practice.

Bottom line: A slightly pessimistic bound is that the running time is $O((n+m) (\lg n)^k)$ (but the preceding discussion shows you how to get a slightly tighter bound).  If $k$ is small enough this might be better than the $O(nmk)$ running time of the naive ("quadratic") algorithm.

Independently: Here is a heuristic that might help you in practice (even though it might not offer any guarantees in worst-case complexity).

Pick some value $k'$ such that $k'< k$.  Now randomly select a subset of $k'$ of the $k$ dimensions, and project everything to those $k'$ dimensions (so we temporarily ignore all of the other $k-k'$ coordinates).  That reduces the problem from a $k$-dimensional problem to a $k'$-dimensional problem.  In lower dimensions, the problem becomes easier, so you can solve the $k'$-dimensional problem to find all pairs $x\in X, y \in Y$ such that $x+y$ is correct in those particular $k'$ dimensions.  Then, you can test each such pair to see whether $x+y$ is correct in all $k$ dimensions.  The total running time will be the running time to solve the $k'$-dimensional problem, plus the running time to examine all pairs that survive the first phase.  You can then try to choose $k'$ to balance these two contributions to the total running time.

I suspect that if you experiment with this sort of idea, then in practice this might significantly improve performance (at least if you start with a large value of $k$).


Pumping lemma: the set of strings of 0s and 1s such that when interpreted as an integer, that integer is prime In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular.

I have not been able to solve this one:

  The set of strings of 0s and 1s, beginning with a 1, and interpreted
  as an integer, that integer is prime.

My attempt:

Assume to the contrary that the language is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s = 101$. The pumping lemma guarantees s can be broken into 3 substrings, x, y, z such that $|xy| \leq p$ and $y \neq \epsilon$....

Obviously this is where it breaks down, because I haven't given a string that is of at least length $p$ (ie $s = 10^p1$).

I believe what you are missing is Fermat's Little Theorem: If $p$ is a prime and $p$ does not divide $a$, then $a^{p-1}\equiv 1 \mod p$.

I'll give an example application in base 10. Let's assume that 2039 is the prime to which the pumping lemma is applied and the decomposition is 2 03 9. That is the pumping lemma would imply that all strings of the form $2(03)^n9$ denote prime numbers. At least it is true for $n\in\{0,1,2\}$. But without further calculation I know that it fails for $n=28$: The number $N=2030303030303030303030303030303030303030303030303030303039$ is divisible by $29$, which is the number at $n=0$. To see this, observe that
$N = 20\cdot 100^{28} + \sum\limits_{0\leq i< 28}30\cdot 100^i + 9
= 20\cdot 100^{28} + 30\cdot\frac{100^{28}-1}{100-1} + 9$ and apply Fermat's theorem.
Here, we also use that $29$ does not divide $100-1$.

I hope from this you are able to solve the exercise.


Closure Properties between different Language Classes I am trying to understand closure properties between different language classes. For example, if L1 is regular and L2 is recognisable, then is L1 intersection L2 decidable? My answer is that L1 is also recognisable and therefore L1 intersection L2 is recognisable. However, this cannot guarantee that it is decidable. Is this a correct solution?

Yours is a correct intuition: $L_1 \cap L_2$ is indeed recognisable.

However, you can't say that such language is not decidable only because you failed to prove it decidable. In theory, there could be a more complex argument that you were not able to find, which could establish that $L_1 \cap L_2$ is actually decidable.

To prove it, you need a counterexample. It is usually helpful to try corner cases, first.

For instance if $L_1 = \Sigma^*$, which is regular, we get $L_1 \cap L_2 = L_2$ which is decidable only if $L_2$ is such. Hence, since recognizable but non decidable languages exist, we get a counterexample.

Further, note that if we took $L_1 = \emptyset$, which is regular, then $L_1 \cap L_2 = \emptyset$ which is decidable, whatever $L_2$ is.

Hence, from the given hypotheses, we can not conclude that $L_1 \cap L_2$ is decidable, nor that it is not. This is because we found counterexamples to both conjectures.


How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ? How are these Context-Free Pumping Lemma Approaches differ?
Maybe this might help understand pumping lemma better

$(a^{i}b^{i}c^{j}d^{j} \mid i, j \geq 0$}

$(a^{i}b^{j}c^{i}d^{j} \mid i, j \geq 0$}

$(a^{i}b^{j}c^{j}d^{i} \mid i, j \geq 0$}

I understand we use contradiction with these conditions

$|vwx| \leq p$
$|vx| \geq 1$
for every $i \geq 0$, $uv^{i}wx^{i}y \in L$.

Not all three languages are in fact non-context-free. Try to spot those that have a CF-grammar, and apply pumping to the remaining example(s). That is the difference you mean, I presume?

(added) The grammars you give in a comment seem correct to me. General hints for applying the pumping lemma are given in various answers at this site, see in particular How to prove that a language is not context-free?


Is subset sum problem with multiplicities NP-complete? To be specific, the problem is formalized as follows.

Given a set of integers $\{a_1,\ldots,a_n\}$, determine whether there exist non-negative integers $x_1,\ldots,x_n$ such that $a_1x_1+\cdots+a_nx_n=0$ and at least one of $x_1,\ldots,x_n$ is positive.

Note this is not a duplicate of this problem. In that problem, the target sum is given as input, while in our problem, the target sum is fixed to be $0$.

I tried to follow the idea of the answer to that question to come up with a new reduction, but since a basic idea of that answer is to use big elements as well as big target to prevent an element from being chosen multiple times, while in our problem the target sum is $0$, I failed.

Related question: Is the following Subset Sum variant NP-complete?

The problem can be solved in polynomial time.

If any of the $a_i$ are zero, then the answer is "yes" (you can set the corresponding $x_i$ to 1, and all other $x_j$ to 0).  So let's assume all of the $a_i$ are non-zero.

If all of the $a_i$ are strictly positive, then the answer is "no" (if $x_i$ is the one that's set to something non-zero, then $x_i>0$ and $a_i>0$, so $a_1 x_1 + \dots + a_n x_n \ge a_i x_i > 0$).  So we can assume at least one of the $a_i$ is strictly negative.

If all of the $a_i$ are strictly negative, then the answer is "no" (if $x_i$ is the one that's set to something non-zero, then $x_i>0$ and $a_i<0$, so $a_1 x_1 + \dots + a_n x_n \le a_i x_i < 0$).  So we can assume at least one of the $a_i$ is strictly negative.

If at least one of the $a_i$ is strictly positive and at least one is strictly negative, say $a_i>0$ and $a_j<0$, then the answer is "yes" (you can take $x_i=-a_j$, $x_j=a_i$, and set all other $x$'s to zero; then $a_1 x_1 + \dots + a_n x_n = a_i x_i + a_j x_j = -a_i a_j + a_i a_j = 0$).

These cases cover all the possibilities: at least one of the above cases must hold.  So, we obtain a polynomial-time algorithm for the original problem.

Credit: I got the key idea from Discrete lizard.


How to reduce EQU to UNI? Let $$\texttt{EQU}=\{u\#v \mid T(M_u)=T(M_v)\} \\
\texttt{UNI}=\{w \mid T(M_w)= \Sigma^*\}$$

How can you prove $\texttt{EQU} \leq \texttt{UNI}$?

The idea I have so far is, to simulate the TM that decides whether a given $w = u\#v$ is in $\texttt{EQU}$ or not. In case it is, our TM halts and we simply accept everything ($f(w) \in \texttt{UNI}$). But, as far as I know, there are two options for $w \notin \texttt{EQU}$ :

The simulation won't ever stop
The simulation stops but not with $q \in F$

The first case isn't a problem as I think. We won't ever accept because the TM never finishes with simulating.
But the second case is a problem, as the TM accepts with $w \notin \texttt{EQU}$.

This answer assumes that $T(M)$ is the set of inputs on which $M$ halts.

Given an instance $u\#v$ of $\texttt{EQU}$, we construct a new Turing machine $w$ with the following input:

A string $x$.
An integer $t$.

The machine acts as follows.

Run $u$ on $x$ for $t$ steps. If $u$ halted, then run $v$ on $x$.
Run $v$ on $x$ for $t$ steps. If $v$ halted, then run $u$ on $x$.
Halt.

I claim that $w \in \texttt{UNI}$ iff $u\#v \in \texttt{EQU}$. To see this, consider some input $x$. We distinguish four different cases:

Both $u$ and $v$ halt on $x$. In this case $w$ will halt on $x,t$ for all $t$ (since "run $v$ on $x$" and "run $u$ on $x$" will always terminate).
Both $u$ and $v$ don't halt on $x$. In this case the test in steps 1–2 will always fail, and so $w$ will always reach step 3 and halt on $x,t$, for any $t$.
$u$ halts on $x$ after $t$ steps, and $v$ doesn't halt on $x$. In this case $w$ won't halt on $x,t$, getting stuck at step 1.
$v$ halts on $x$ after $t$ steps, and $u$ doesn't halt on $x$. In this case $w$ won't halt on $x,t$, getting stuck at step 2.

How did I construct this machine? First of all, let us note that $\texttt{UNI}$ is $\Pi_2$-complete. This means that we can reduce to it any language $L$ such that
$$
x \in L \leftrightarrow \forall y \exists z \, \Pi(x,y,z),
$$
where $\Pi$ is any computable predicate. Next, using $H(u,x,t)$ for "$M_u$ halts on $x$ within $t$ steps", we see that
$$
u\#v \in \texttt{EQU} \leftrightarrow \forall x (\exists s \, H(u,x,s) \land H(v,x,s)) \lor (\forall t \, \lnot H(u,x,t) \land \lnot H(v,x,t)).
$$
Rearranging, this is the same as
$$
u\#v \in \texttt{EQU} \leftrightarrow \forall x \forall t \exists s \, (H(u,x,s) \land H(v,x,s)) \lor (\lnot H(u,x,t) \land \lnot H(v,x,t)).
$$
Therefore $\texttt{EQU}$ should reduce to $\texttt{UNI}$. Taking a look at the $\Pi_2$-completeness proof, we reach the machine outlined above.

It is easy to see that $\texttt{UNI}$ reduces to $\texttt{EQU}$, by mapping $w$ to $w\#h$, where $M_h$ is a machine that always halts. We conclude that $\texttt{UNI}$ is also $\Pi_2$-complete.


Are combinatory logic terms always larger? So there is an algorithm to convert lambda calculus terms to combinatory logic using SK combinators. It produces things that explode in size. I would like to know more about this explosion in size. I can't seem to think of a better algorithm however. I have heard of functional languages being practically compiled to combinators so it seems that a better algorithm must exist. I looked up David Turner's paper on the topic and he basically just says to apply a few optimizations and that they cause a "considerable improvement".

Does "considerable improvement" mean that the size drops to only a polynomial increase? Is there a known way to convert lambda terms to combinatory logic with only a polynomial (or less?) increase in size? If such an algorithm exists is it practical?

not an expert on this but here are two historical papers that seem to be closely relevant to the question and it is possibly a semi active area of research. Turner proposed a set of combinators that can be reduced to SK combinators. this next paper argues that Turner combinators even not reduced to SK combinators leads to exponential blowup (and that presumably the reduction would to SK terms be even larger). but then the 2nd paper says there is an efficient O(n log n) space algorithm based on Turner combinators. (it appears maybe that claims have been made about polynomial efficiency that are regarded as not fully demonstrated/ unproved & are therefore regarded as conjectures...?) anyway apparently real functional evaluation in applied languages typically does not use combinator method so implementors are not too concerned with issues of theoretical efficiency of evaluation of functional expressions by combinator translation.

What is an Efficient Implementation of the λ-calculus? / Frandsen, Sturtivant (1991) (see p.18)

Furthermore, we show that implementations based upon Turner Combinators or Hughes Super-combinators have complexities $2^{Ω(ν)}$, i.e. an exponential lower bound.
It is open whether any implementation of polynomial complexity, $ν^{O(1)}$, exists, although some implementations have been implicitly claimed to have this complexity.

Translation of Turner Combinators in O(n log n) space / Noshita (1985)

A practical method for representing Turner Combinators is presented, which needs only O(n log n) space in the worst case for translating lambda expressions of length n.


Number of possible heaps on $\{1,...,2^h-1\}$ Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it.
Definition
A binary tree is ordered if the key at every node is smaller than the keys at its children.
An ordered binary tree of height $h$ is called a heap if the tree induced by all levels except the last is a complete binary tree and all leaves are "as much to the left as possible".

So what I've come up with is this expression:
$$C_h=\displaystyle\prod_{n=1}^{h} (2^{i-1})!$$
The intuition behind it is that with every  increment by $1$ of $h$ the tree gains $2$ times more leaves than before and the possibilities of ordering these leaves can be determined via the factorial operation. Does that make sense?

The definition you give looks like the definition of a complete tree. With the restriction that nodes are in $[\![1, 2^h-1]\!]$, then it is also a perfect tree of height $h$.

Instead of looking at the leaves, you should look at the root of the tree: since the tree is perfect, it has two children of size $2^{h-1}-1$ (this is how $C_{h-1}$ appears). You just have to think of how to split $2^{h}-2$ keys between left and right (the key of the root is uniquely determined, since it is a heap).

I will edit this answer if it is not clear enough.


How do you solve a recurrence relation with multiple subproblems of different sizes? For instance, consider the following recurrence relation.

  T(n) = T(n/2) + T(n/3) + T(n/4) + n

Would you use the substitution method for this?

You can find an upper bound like this:
$T(n)\leq 3T(n/2)+n$.

Solving using master theorem,
$T(n)=O(n^{log_23})$


What is the difference between speculative execution & branch prediction? In computer architecture I'm confused between speculative execution & branch prediction. Are the same or different?

“Branch prediction” will predict whether a particular branch is taken or not. The prediction can be right or wrong; whoever designs the hardware for it will want the prediction to be correct as often as possible.
Starting with a predicted branch, we don’t know if the instructions we execute should actually be executed, so we start with speculative execution. At some point the processor will learn correctly whether the branch should have been taken or not. If the branch was predicted correctly, the speculative execution is turned into non-speculative. If the branch was predicted incorrectly, all the results of speculative execution are thrown away and you continue with the correct branch.
Car analogy: You drive a car, I have the map. I say “I think you need to turn left” = branch prediction. You turn left = speculative execution. Later I tell you if the turn was correct or wrong.


Find all pairs of strings in a set with Levenshtein distance < d I have a set of $n = $ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that string.  The Levenshtein distance (also called the edit distance) between two strings is the number of insertions, deletions and/or replacements required to convert one string into the another.

This should be possible in $O((d + 1)^{2d + 1} \cdot l \cdot n)$ time with a Levenshtein transducer, which takes a single query string at a time and find all the matches in a set with Levenshtein distance $\le d$.  However, using the implementation at that link, it appears to take more like $O(n \log n)$ time rather than $O(n)$, and uses more than 200 GB of memory.

Is there an alternate $O(n)$ approach that might be faster in practice?  The Levenshtein transducer is more general than it needs to be for this application, since it finds matches for each string independently and doesn't exploit the fact that you're comparing every string against every other string.

There's a "trick" you can use that might potentially speed up your algorithm a little: shingling.  No guarantees that it'll necessarily help in your particular case, though.

Lemma. If the edit distance between two words $w,x$ is $\le 4$, and the two words both have length 20, then there exists some 4-gram that is common to both words (i.e., some $u$ of length 4 that is a substring of both $w$ and $x$).

This lemma then suggests the algorithmic trick.  Build a table with $4^4$ buckets, one bucket for each possible $4$-gram.  Given a word $w$, extract all of its 4-grams (there will be 17 of them) and insert it into those 17 buckets.  Do this for each word.

Now, if there is a pair of words at edit distance $\le 4$, then there must be some bucket that contains both words.  So, for each bucket, we search the set of words within that bucket for a pair of words at edit distance $\le 4$.  Use whatever algorithm you like for that task.  I would suggest trying BK-trees or metric trees.

Will this trick help?  The only way to know for sure is to try it.  But here's the intuition.  We'll have 256 buckets.  Each word will get mapped into 17 buckets.  Thus, heuristically, we expect each bucket to have $n'=17n/256$ words in it.  If we have an algorithm that can search for pairs of words at edit distance $\le 4$ among a set of words in $T(n)$ time, then applying that directly to the original set of words takes $T(n)$ time.  In contrast, after applying this trick, we apply it once to each bucket.  Now if $256 T(17n/256)$ is smaller than $T(n)$, this trick might yield improvements in running time.  My prediction is that it'll yield improvements for $\Theta(n^2)$-runtime algorithms, but not for $O(n \lg n)$ or $O(n)$ time algorithms.

This trick can be combined with any algorithm for looking for a pair of words with edit distance $\le 4$ in a set of $n$ words.

The "trick" can be improved further.  Define a "slate" of the word $w$ to be a pair $(i,u)$ where $i$ is a position ($1 \le i \le 17$) and $u$ is the 4-gram that occurs at position $i$ within $w$.  From each word you get 17 slates.  Now we get a refined lemma:

Lemma.  If the edit distance between two words $w,x$ of length 20 is $\le 4$, then there exists a slate $(i,u)$ of $w$ and a slate $(j,v)$ of $x$ such that $u=v$ and $|i \le j| \le 2$.

(It might be possible to improve the latter condition to $|i \le j| \le 1$, but I haven't tried to check.)

We'll do the same thing as before, but identifying each bucket with a slate.  We get $20 \times 256$ different buckets.  Now, for each word $w$, extract its 17 slates and store the word in the corresponding 17 buckets.  Let $B_{i,u}$ denote the set of words in the bucket for the slate $(i,u)$.  Finally, for each slate $(i,u)$, we check whether there exists a word $w \in B_{i-2,u} \cup B_{i-1,u} \cup B_{i,u} \cup B_{i+1,u} \cup B_{i+2,u}$ that is within edit distance $\le 4$ of some word in $B_{i,u}$.

Heuristically, we expect each bucket to have $n'=17n/(20 \times 256) \approx 0.0033 n$ words in it.  We expect the running time for each bucket to be something like $5 T(n')$, and we need to do that $20 \times 256$ times, for a total running time of $25600 T(0.0033n)$.

Is this better than the prior trick?  The only way to know for sure is to try it.  My prediction is that this'll be better for $\Theta(n^2)$-runtime algorithms, but worse for $O(n \lg n)$ or $O(n)$ time algorithms.

Finally, I don't think you have the running time of your scheme right.  I believe the Levenshtein transducer automata approach will have running time $\Omega(n^2)$ in your setting, as several folks have outlined in the comment thread under your question.


How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)? I've seen circuit level implementations of ALU's before, but how are NOT/AND/ADD performed mechanically?

Babbage's arithmetic unit (ALU) for the Analytical Engine was originally called the mill. It wasn't constructed out of binary logic gates (AND, OR, NOT). Instead it works on the basis of counting gear teeth and escapements.

The mill is essentially an entire Difference Engine designed to be mechanically controllable/programmable (rather than needing humans to set the input gears to the correct number). The Difference Engine is much more primitive than what we would call a "calculator" today. It is bascially a mechanical abacus. Only, instead of beads it represents numbers by the rotation of gears.

I haven't tried building one so can't quite tell you the exact detail of how it works but in general it works like this:

Two rows of input gears are spun to set it to two numbers.
The gears are connected together in such a way that when you rotate them one "cycle" both will rotate another row of output gears to produce a result. Note that a "cycle" literally means what it means - there is a crank on one end of the machine that you rotate with your arms one round to get the result.
The operation can either add the sum of the input gears or it can subtract one input from another.

That's all it can do, nothing else.

Given that it can do addition and subtraction, and given that we can calculate multiplication by repeated addition and division by repeated subtraction, we can perform any calculation.

In reality Babbage optimized his mill to do more than simply add or subtract (though, the machine can indeed do that). The gears are stacked on top of each other with the output of each stage being used as input for the next stage to calculate polynomials (somehow, I don't know the details). So you can arrange the output rows to represent multipliers in a polynomial equations and you can cycle the mill x number of times to get the result for f(x). But that's more to do with the Difference Engine. The mill for the Analytical Engine could do less specialized calculations.

So Babbage didn't design his "logic" the way a digital designer would design a circuit. He designed it the way a Swiss watch maker would design a complex feature for a handcrafted watch (moon phase display for example).


Filling Rows of a Matrix Subject to Conditions I'm seeking to write an algorithm which, given a value of N, will fill a matrix consisting of (N+1)(N+2)(N+3)/6 rows and 4 columns with the integers from 0, ... , N, subject to the conditions that:

The sum of values in any row is N
No rows are repeated (this should ensure that every such possibility is listed)

For example, with N=2, we have 10 (=3*4*5/6) rows:

2 0  0 0
1 1  0 0
0 2  0 0
1 0  1 0
1 0  0 1
0 1  1 0
0 1  0 1
0 0  2 0
0 0  1 1
0 0  0 2

I've been trying for a while to program this (in R, for what it's worth), but I'm struggling to get anywhere. Any advice?

If you are allowed to repeat rows, then a simple solution is to repeat the row $(N,0,0,0)$ as many times as needed.

If you are not allowed to repeat rows, this should also be pretty easy to solve.
This sounds like an exercise where you learn by doing, so I don't want to spoil it by giving away the answer, but I'll give you some tips and suggestions that will help you develop an answer:

What are the requirements for a row to be valid?  If $(w,x,y,z)$ are the four numbers in a row, what are the requirements on $w,x,y,z$ for this row to be allowable?
If I have one candidate row that meets all the requirements, and another candidate row that also meets all the requirements, can I put the first one in the first row of the matrix and the second row of the matrix?  Will that always be valid, or are there any constraints where my choice of the first row of the matrix restricts what I'm allowed to put in the second row of the matrix?  (If there are any restrictions, make sure you understand and can state precisely exactly what they are.)
How many possible ways are there to choose a single row that meets all of the requirements?  Hint: this is a standard problem in combinatorics/counting.  If you are in a computer science-oriented course on counting, your textbook will probably include a worked-out problem where it shows how to count the number of ways to place $k$ balls into $n$ bins with replacement, when order does not matter.  Make sure you understand the solution to that -- you might find it helpful.
How many different rows do you need?  Compare this to your answer to #2 above.  Relevance: If you need more rows than there are possibilities, and you need them to all be different, you're hosed.  If there are more possibilities than you need to list in your matrix, you can pick any subset.
How would you enumerate all valid rows?  You probably want to use some nested loops, e.g., loop over some range of values of $w$, and for each such $w$, loop over some range of values of $x$, and so on.  What range of values should you use for $w$?  (What values of $w$ are allowable?)  What range of values should you use for $x$?  (Since this is a nested loop, your range of values for $x$ is allowed to depend upon $w$.)  Fill out the rest of the details.

Update: Here's an overview of how to enumerate over these possibilities.  (This is really more of a Stack Overflow question than a question for this site, to be honest.)  I suggest you use three nested loops: loop over $w$ (over the range $0\ldots N$), then loop over $x$ (over the range $0 \ldots N-w$), then loop over $y$ (over the range $0\ldots N-w-x$), then set $z=N-w-x-y$.  In other words:

for w=0,1,2,...,N:
    for x=0,1,2,...,N-w:
        for y=0,1,2,...,N-w-x:
            z = N-w-x-y
            append the row (w,x,y,z) to the matrix

To generalize this code to enumerate all valid rows with $k$ columns, you should probably ask on Stack Overflow, as that's a coding question.  But here's a tip.  Think about how you'd enumerate all possible values of a $d$-digit odometer.  You'd create an array $A[0\ldots d-1]$, initially all zeros, to hold the $d$ digits, and you'd increment through odometer values, one by one.  How do you increment an odometer value?  Start with your finger pointing to the rightmost digit.  Increment that digit; except that if it increments from 9 to 10, that digit has rolled over, so change the 10 to a 0, move your finger left one place, and repeat the whole process (until nothing rolls over).  In code, here's how you increment an odometer value:

for i=d-1,d-2,...,2,1,0:
    A[i] = A[i]+1
    if A[i] == 10:
        A[i] = 0  // roll-over
    else:
        break out of the loop

What does this have to do with your problem?  Think of the first $k-1$ columns of each row as an odometer value.  We're going to enumerate through them.  Except, now the condition for when a digit rolls over is different: instead of rollover happening when that digit goes from 9 to 10, it will instead happen when the sum of that digit and all digits to its left goes from $N$ to $N+1$.  Everything else remains the same.  So, enumerate all possible values for the first $k-1$ columns, in this way.  Then, you can fill in the $k$th column to whatever it needs to be to make sure the entire row sums to exactly $N$.  If this doesn't help you, you might need to ask a separate question on Stack Overflow.

Once you work through the answers to all of these questions, you should have a solution.  If you have gotten stuck, edit your question show us how far you got so far (e.g., which of these questions you've figured out how to answer), at what stage you've gotten stuck, and what you've tried at that stage.


Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata? Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two NFA, one being in state $r$ and other being in $s$, if there is a transition of the type $r \xrightarrow{\epsilon} s$. If there is a cycle of the type $r \xrightarrow{\epsilon} s \xrightarrow{\epsilon} q_1....\xrightarrow{\epsilon} q_k \xrightarrow{\epsilon} r$, where $q_i$ are some states of NFA, then it's no use remembering another NFA in state $r$ upto the point where input has been read till alphabet $w_i$.
If a PDA ( non-deterministic ) is in state $r$ ( and input is read till $w_i$ ) and there exists a cycle $r \xrightarrow{\epsilon,\epsilon \to a} s \xrightarrow{\epsilon,\epsilon \to a} q_1....\xrightarrow{\epsilon,\epsilon \to a} q_k \xrightarrow{\epsilon,\epsilon \to a} r$ ( where transition $\epsilon,\epsilon \to a$ means thatnothing after $w_{i}$ is read from input, nothing is popped or read from stack and alphabet $a$ is pushed onto the stack ) then before reading the next input alphabet $w_{i+1}$ there will be infinite PDA in states $r,s,q_1,...q_k$ because unlike the NFA although the states are finite stack contents can be different ( infinite possibilities ), if I am not wrong.

As with NFA and PDA the power of non-determinism comes from $\epsilon$ transitions. So I assume that non-deterministic Turing machine also gets it's non-determinism from $\epsilon$ transitions like NFA and PDA ( more like PDA ). I know that a deterministic Turing machine can simulate a non-deterministic one ( I know the proof which uses bread-first search ). But now I am doubtful as to how that is possible. Because if a cycle of the type in PDA above, exists in the state diagram of the non-deterministic Turing machine then before reading the next symbol $w_{i+1}$ the deterministic Turing machine even when simulating a configuration in some branch of non-deterministic Turing machine ( while bfs ) would have to keep track of infinite Turing machine (  again the states are finite but the symbols on the tape have infinite possibilities ).
So how exactly non-determinism in defined in case of Turing machines ? Am I misunderstanding something trivial ? Do non-deterministic Turing machines use $\epsilon$ transitions ?

I am sorry for my trivial doubts. If anything is incorrect I can update my question.

Non-determinism is the same concept in all contexts – the machine is allowed several options to proceed at any given point. However, the semantics are a bit different since DFAs/NFAs and PDAs always define total functions, while Turing machines (deterministic or non-deterministic) in general define partial functions.

A partial function is one defined only on part of the domain. If $f$ is not defined on $x$ then we write $f(x) = \bot$. (So $f$ is really a total function, but there is a special element in the range signifying that the output is undefined.) A deterministic Turing machine $M$ defines a partial function as follows: if $M$ halts on $x$ then $M(x)$ is the contents of the tape when $M$ halts on $x$; and otherwise, $M(x) = \bot$.

A deterministic Turing machine decider has two kinds of halting states, accepting and rejecting, and defines a partial function as follows: if $M$ halts on $x$ at an accepting state, then $M(x)=1$; if it halts at a rejecting state, then $M(x)=0$; if it doesn't halt, then $M(x)=\bot$. If $M$ always halts then we say that it accepts the language $L = \{x : M(x) = 1\}$.

A non-deterministic Turing machine (which is always a decider) is allowed to "branch" (have several possible options at any given point in time), and has the following semantics:

$M(x) = 1$ if on input $x$, the machine $M$ halts on all branches, halting at an accepting state for at least one branch.
$M(x) = 0$ if on input $x$, the machine $M$ halts on all branches, always halting at a rejecting state.
$M(x) = \bot$ if on input $x$ there exists a branch on which $M$ doesn't halt.

Given this definition, it is hopefully clear how to simulate a non-deterministic Turing machine using a deterministic Turing machine decider: you try all branches, checking whether any of them leads to an accepting halting state. After all branches have halted, you can decide whether to go to an accepting state or to a rejecting state. If the non-deterministic Turing machine doesn't halt on some branch, then so would the deterministic one.

What about $\epsilon$-moves? They cause trouble in that the corresponding automaton might never halt. For finite automata (NFAs and PDAs) we silently ignore non-halting computations. Our reason for doing that is that the resulting languages are always computable, even though the naive algorithm for simulating them deterministically (simulating all computation paths) doesn't quite work. This is not so difficult for NFAs, which can be converted to DFAs. However, deterministic PDAs are strictly weaker than non-deterministic PDAs. Nevertheless, you can show that every PDA is equivalent to one without $\epsilon$-transitions (though the proof might go through context-free grammars).

You can simulate $\epsilon$-moves in Turing machines, but you have to be careful that there are no loops which cause non-halting computations. In some cases, however, we can use the same trick as above. For example, suppose that your Turing machine is space-constrained: we know an upper bound on the space that it uses (depending on the input length). In that case every non-halting computation necessarily cycles (since the Turing machine has finitely many states, including the tape contents), and so if we "ignore" non-halting computations as above, the resulting model of computation is still computable. More generally, this works as long as we are guaranteed that every non-halting computation cycles. (This is the case for NFAs but not for PDAs.)


Runtime complexity of unary languages I am trying to find a unary language whose runtime complexity is exponential in $n$ (e.g. $\Theta(2^n)$ or a similar expression). But I am not sure how to reason about the runtime of such languages.

I tried the language: $L_1=\{1^{2^k}\}$. This language can be identified by counting the number of ones in the input into a binary register, then checking if the binary register has only zeros and a leading one. This requires $O(n)$ steps to read the input, and probably $O(\log n)$ for each addition, so the total runtime is $O(n \log n)$. Is this correct?

What about the language: $L_2=\{1^{2^{2^k}}\}$? This language can be identified by counting the number of ones in the input into a binary register, then checking if the number of zeros in the register is in $L_1$. This seems like it can be done in time polynomial in $n$.

How can I construct a unary language that can only be identified in exponential time?

Let $L$ be a language in $\mathrm{TIME}(2^{2^n})$ but not in $\mathrm{TIME}(o(2^{2^n}/2^n))$ (such a language exists by the time hierarchy theorem). Define $U = \{1^n : n \in L\}$. Using an algorithm for $L$, we get that $U \in \mathrm{TIME}(2^n + O(n^2))$. Running the same argument backwards, we see that $U \notin \mathrm{TIME}(o(2^n/n))$ (here we use that $O(4^n) \ll 2^{2^n}/2^n$).


How does augmenting linear bounded automata tape alphabets increase memory? A linear bounded  automaton is a Turing machine that is restricted by memory.
How would augmenting  the tape alphabet of a linear bounded automaton
increase its memory? While the memory that the automata can
use is as size of the input?

If you consider an input, hence a tape, of size $n$ and a tape alphabet of
$b$ symbols, you get $b^n$ configurations possible on your tape. If
you measure memory in bits, the memory size is the base 2 logarithm of
the number of configurations, very simply because that is the number
of bits required to have the same number of configurations (rounding up
to the next integer, because half-bits have not been invented yet).

So the tape memory of your linear bounded automaton (LBA) is $\log_2
b^n$, which is equal to $n\log_2 b$.

Augmenting your tape alphabet does not increase your memory very
fast. Doubling the size of the alphabet is equivalent to a single extra bit per cell, i.e. adding $n$ bits total. The
positive side of it is that it does not take many bits per cell of the
tape to have a huge alphabet.


Figuring out the language of a non-linear CFG I have the CFG G with the following production rules:
$$
S \to aSaS \mid b
$$
Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, but it's not very helpful tho.

It's no wonder that you're having trouble with this; it's nasty. So as not to spoil the suspense, $L(G)$ is

  The set of all $w\in\{a, b\}^*$ such that $w = a^{i_1}b\,a^{i_2}b\dotsm a^{i_n}b$ with $i_k\ge 1$ for all $1\le k\le n$ and
  $$
\sum_{k=1}^n i_k=2n-2
$$

The proof is basically int two parts. First it's clear that any word generated by the grammar must end in $b$ and that no two $b$'s can be adjacent, so any word in $L(G)$ must have the form noted above.

To show the sum part, let's count the number of $S$'s, $a$'s and $b$'s in any sentential form that results from starting with $S$ and using either of the two productions of the grammar. Let $(s,a,b)$ represent these counts. We have

The production $S\rightarrow aSaS$ will change $(s,a,b)$ to $(s+1, a+2, b)$, since we're adding two new $a$'s and one more $S$.
The production $S\rightarrow b$ will change $(s,a,b)$ to $(s-1, a, b+1)$.
We start with the count $(1,0,0)$.
Note that production (1) followed by production (2) yields the same counts as we would have by using the productions in the opposite order, (2), (1). This observation isn't critical, but it means that we have a particularly pretty form when we apply the productions to the count tuples.
A count $(s,a,b)$ corresponds to a word in $L(G)$ only if $s=0$.

Starting with $(1,0,0)$ we now take D.W.'s tack and look at some small examples. Considering the counts with $s=0$, we find $(0,0,1), (0,2,2), (0,4,3), (0,6,4), (0, 8, 5)$ and so we guess that all the words in the language must have counts of the form $(0, 2n-2, n)$. We're done, right? Well, not quite. We need to show that (1) our guess about the counts was correct, and (2) that we actually can get any sequence of $i_k$'s satisfying these conditions. Fortunately, both pieces are more or less easy to show by induction, though the second one is somewhat messy.

By the way, we can also show that any string in $L(G)$ must have length $3n-2$ and that there are $\binom{n}{2}$ such strings.


Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$? Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?

I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (Just as the smallest upper bound is $n^7$)

The reason I say that the function is in the Omega class of functions larger than $n^5$ is because of the limit definitions of complexity [Source]:
$\require{enclose}$

$$\begin{array}{c|c|c}
\text{Big-}\mathcal O\ \text{notation} & \text{Comparison notation} & \text{Limit definition}\\ \hline
f \in \mathcal o(g) & f \; {\scriptstyle \enclose{circle}{\kern .07em \bbox[6px] \lt \kern .07em}}\ g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = 0\\
f \in \mathcal O(g) & f\; {\scriptstyle \enclose{circle}{\kern .07em \bbox[6px]\le \kern .07em}}\  g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} < \infty \\
f \in \Theta(g) & f\; {\scriptstyle \enclose{circle}{\bbox[7px]=}}\  g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} \in \mathbb{R}_{>0} \\
f \in \Omega(g) & f \;{\scriptstyle \enclose{circle}{\kern .07em \bbox[6px]\ge \kern .07em}}\ g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} > 0 \\
f \in \omega(g) & f\; {\scriptstyle \enclose{circle}{\kern .07em \bbox[6px]\ge \kern .07em}}\; g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = \infty \\
\end{array}$$

Using the limit definition of $\mathcal O$, we correctly identify that $n^5+n^7 \in \mathcal O(n^7)$ and $n^5+n^7 \notin \mathcal O(n^6)$

However, using the limit definition of $\Omega$ tells us that the function is in $\Omega(n^7)$! But isn't the largest lower bound for this function $n^5$?

The function $n^5 + n^7$ is big-$Ω$ of both. However, it is little-$\omega$ of $n^5$.

It happens that $n^5 + n^7 \in \Theta(n^7)$. These asymptotic-notations only describe the behavior of the function $f(n) = n^5 + n^7$ for large $n$, aka "for all $n > \textrm{some value}$". The function is a polynomial function, and the highest-degree term determines the order of growth.

From the definition of $Θ(g)$, it means that function $f$ is both big-$O$ and big-$Ω$ of $g$. The function is bounded by some constant multiple of $n^7$ for large $n$. Namely, the function is bounded above by $2n^7$ and below by $n^7$.

Nevertheless, $n^5 + n^7 \in \Omega{(n^5)}$; the function is of [strictly] greater order than a quintic. Equivalently, $n^5 \in O(n^5 + n^7)$.


Why is the satisfiability of ESO formulas not equal to the satisfiability of FO formulas? Existential second-order logic (ESO) formulas have the form
$$\Phi = \exists R_1 ... \exists R_k. \phi$$
where $R_1...R_k$ are relation symbols and $\phi$ is a FO formula,
which can use the relation symbols $R_1...R_K$ as well as other relation symbols.
My claim is that

  $\Phi$ is satisfiable if and only if $\phi$ is satisfiable.

Indeed, satisfiability of a FO formula means finding a universe and an interpretation of all relation symbols. Therefore, we have an implicit quantification $\exists R_1 ... \exists R_k$ in front of the FO formula $\phi$, when considering satisfiability. (For validity, the claim does  not hold.)

But the claim must be wrong since people study satisfiability of ESO separately from that of FO. What do I miss?

You're right: an ESO sentence is satisfiable iff its first-order "matrix" - with relation/function variables replaced with corresponding relation/function symbols - is satisfiable.

TI'm not an expert here, but I think what's going on is "linguistic convenience." There are other related questions where we don't get coincision. For example, checking whether a first-order sentence is true in a given finite structure is usually harder than checking whether one of its "second-orderizations" is true in that same structure${}$('s reduct). Similarly, as you say validity for ESO sentences is strictly more complicated than validity for FO sentences. In this way it may feel more consistent to talk about ESO satisfiability rather than FO satisfiability if we're also talking about ESO validity, ESO truth in a given structure, etc.


Why isnt node checked for nil value in start when transplanting binary tree Whilst I was reading CLRS I came across this:

When TRANSPLANT replaces the subtree rooted at node u with the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s parent ends up having v as its appropriate child.

TRANSPLANT(T, u, v)
1  if u.p == NIL
2      T.root = v
3  elseif u == u.p.left
4      u.p.left = v
5  else u.p.right =  v
6  if v != NIL
7      v.p = u.p

Lines 1–2 handle the case in which u is the root of T . Otherwise, u is either a left child or a right child of its parent. Lines 3–4 take care of updating u.p.left if u is a left child, and line 5 updates u.p.right if u is a right child. We allow v to be NIL, and lines 6–7 update v.p if v is non-NIL.

Why wasn't v was checked for nil value in the starting of the procedure and if it was not checked then why was it checked in line 6. If v is nil then its parent will be its original parent and u's parent will reference to v - wouldn't this cause inconsistency in tree ?
Context
Transplant is the sub-procedure used in deletion of a node from a binary search tree. It is used in binary search tree not in RB Trees or B-Trees.
Details about the book
Edition - 3rd
Print - 2nd
PageNo - 296

If $v$ is NIL then transplanting $v$ just transplants an empty tree. This is fine. It is handled in the exact same way as transplanting an actual tree, the only difference being that we don't need to update $v$'s parent pointer.

Could the code be structured differently? Probably. Why, then, did the authors choose this particular implementation? No deep reason. They programmed the algorithm, and that's the code they came up with. You might have come up with a different code. There's no one right answer in programming.


IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary? The SUBSET SUM decision problem consists of poitive integers a1,...,an; b.
We wish to know if for some subset S of the indices, $\sum_{i \in S}a_i = b$

I want to prove that if b is given in unary(and the ai's are gives in binary), that this decision problem is in P

Start by initializing a boolean array $T$ with indices from $0$ to $b$, inclusive. $T_0$ starts as true (because you can always achieve a sum of 0) and the rest of the array starts as false.
For each value $a_i$, we update the array by going though each value $x$ where $x+a_i\leq b$, and setting $T_{x+a_i}$ to true only if $T_x$ is true.
Essentially, at any point, the array describes which sums are possible using only the values of $a$ which have already been looked at. When a new $a_i$ is looked it, any value that can be made by adding $a_i$ to a currently possible sum becomes possible.
The final decision simply involves checking if $T_b$ is true.
The bulk of the program involves iterating over all $n$ values of $a$ and all $b$ elements of the array, for a total runtime of $O(nb)$. The size of the input is at least $n+b$, because it describes each value of a $a$, and $b$ is written in unary.
Because $O(nb)$ is polynomial with respect to $n+b$, the described problem can be decided in polynomial time.


Time complexity for searching $k-th$ element from starting and ending of a linked list What are the time complexities of finding $8th$ element from beginning and $8th$ element from end in a singly linked list? Let $n$ be the number of nodes in linked list, you may assume that $n > 8$.

The answer is given as $O(1)$ and $O(n)$.
What I learnt till now is that searching operation in linked lists takes linear time since it doesn't have indexes like arrays. Then why does searching the $8th$ element would take constant time?
Further explanation for the answer is as follows :

  Finding 8th element from beginning requires 8 nodes to be traversed which takes constant time. Finding 8th from end requires the complete list to be traversed.

Can someone explain me the concept behind this?

If you start from the beginning, it does not matter how big the list is, you have to go through the links a constant number of times no matter what.

n = 100, n = 1000, does not matter, you just have to follow exactly 7 links (independent of n).


Computing the Maximum in an MxM Matrix I have an MxN matrix where each element contains a positive numeric value.

I need to find those elements in the matrix that add up to the "maximum value". The caveat is that each row and column can be used at most once in calculating the total.

I have a brute force algorithm for doing this bit it's ugly. I was wondering if there is a well-known algorithm for accomplishing this.

Your problem is known as maximum weighted bipartite matching or the assignment problem, and has efficient algorithms such as the Hungarian algorithm.


Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1) There is a finite set of points $S$ in the plane with $ |S| = n$. MST is the minimal spanning tree of S. "Minimal" here refers to the Euclidean distance between the points of $S$, so the MST is the minimum spanning tree with the lowest overall distance.

I want to prove that the degree of every node is in O(1).

I tried to use Euler's Theorem but unfortunately this did not lead to a solution. Any ideas?

Here is a proof sketch from Robins and Salowe, On the Maximum Degree of Minimum Spanning Trees. Let $x$ be some vertex in the MST. We want to show that its degree $d$ is small.

Let $y_1,\ldots,y_d$ be its neighbors. Draw a small circle of radius $\epsilon$ around $x$, and "project" each $y_i$ to a point $z_i$ on the circle: the point $z_i$ is just the intersection of the line $\overline{x y_i}$ and the circle. The idea is to show that all of these projections are far from each other.

Indeed, consider any pair of points $y_i,y_j$, and suppose without loss of generality that $\|x-y_i\| \leq \|x-y_j\|$. Repeat the same process as before, but with a circle of radius $\|x-y_i\|$. The projections are $w_i = y_i$ and $w_j$. The triangle $\Delta xz_iz_j$ and $\Delta xy_iw_j$ are similar, and so $\|z_i-z_j\|/\epsilon = \|y_i-w_j\|/\|x-y_i\|$.

On the other hand, consider the circle $\Delta xy_iy_j$. Two of the edges are in the minimum spanning tree, so the remaining edge must be a heaviest edge. Since we assumed that $\|x-y_i\| \leq \|x-y_j\|$, this means that $\|y_i-y_j\| \geq \|x-y_j\|$. Therefore
$\|x-y_j\| \leq \|y_i-y_j\| \leq \|y_i-w_j\| + \|w_j-y_j\|$.
Since $w_j$ is on the line from $x$ to $y_j$, we have $\|x-y_j\| = \|x-w_j\| + \|w_j-y_j\|$, and so $\|x-w_j\| \leq \|y_i-w_j\|$. Since $w_j$ is on the circle of radius $\|x-y_i\|$ centered at $x$, this shows that $\|x-y_i\| \leq \|y_i-w_j\|$.

Combining the formula $\|z_i-z_j\|/\epsilon = \|y_i-w_j\|/\|x-y_i\|$ with the inequality $\|x-y_i\| \leq \|y_i-w_j\|$, we deduce that $\|z_i - z_j\| \geq \epsilon$. Summarizing, $z_1,\ldots,z_d$ are points on a circle of radius $\epsilon$ which are at distance at least $\epsilon$ from each other. This forces $d \leq 6$.

Perhaps the following diagram will be useful:

Suppose that the inner circle has radius $\epsilon$. We want to show that $\|z_i-z_j\| \geq \epsilon$. Due to the MST property, we know that $\|y_i-y_j\| \geq \|x-y_j\|$. Thus necessarily $\|y_i-w_j\| \geq \|x-w_j\|$. This implies $\|z_i-z_j\| \geq \|x-z_j\|$ due to similarity of triangles.

Robins and Salowe note that when $d = 6$, the points are packed tightly. It turns out that there is always an MST in which there is always some jiggle room, and so some MST has maximum degree at most $5$.

The same argument works in $D$ dimensions and in any metric, as long as there is a bound on the number of points on a unit ball which are at least a unit distance away from each other. This property holds in all $L_p$ metrics (for finite $p$!) in any dimension.


Rigorous proof that parametric polymorphism implies naturality using parametricity? This question asks for an informal explanation of why all polymorphic functions between functors are natural transformations (This is a claim made by Bartosz Milewski). One answer to that question refers to the Theorems for free! paper. However, after reading it I'm not seeing how it implies the result.
The parametricity theorem from "Theorems for free!" can be applied to a function that has the "natural transformation type signature": $\eta:\forall X,F (X) \to G (X)$ for some $F, G : \text{Type} \to \text{Type}$. Basically parametricity gives us (applying it to a functional relation):
For any types $A_1,A_2$ and function $f:A_1\to A_2$, the following equation holds:
$$f_G\circ \eta_{A_1}=\eta _{A_2}\circ f_{F}$$
where I define $f_G$ and $f_F$ as the relations that Wadler would write as $[[F(X)]]\mathcal A[f\setminus X]$ and $[[G(X)]]\mathcal A[f\setminus X]$ respectively (I can't write the double square bracket symbol \llbracket).
This looks like the right equation for $\eta$ to be a natural transformation, but the problem is that $f_G$ and $f_F$ aren't necessarily equal to the functions $G(f)$ and $F(f)$. In fact, we haven't even defined $F$ and $G$ as functors. Instead, $f_G$ and $f_F$ are the specific functions that you get when you apply Wadler's definition of the relation that belongs to each type.
Therefore I don't see how you would use the parametricity theorem to show that polymorphic functions between functors are natural transformations, because as far as I can tell, the parametricity theorem doesn't even allow you to specify the morphism part of the functors $F,G$. It only takes them as type constructors.
Is there something I'm missing? Is there a formal proof? It would be nice to have a self-contained proof that "parametric polymorphism implies naturality", that requires minimal background knowledge.

The missing part is the "identity extension lemma", which is mentioned in Reynolds' original paper but not in Wadler's.
For $F : \text{Type} \to \text{Type}$, this says that if the relational interpretation of $F$ is instantiated with a type $A$ and the identity relation
on $A$, we get the identity relation on $F\,A$.
For System F, identity extension can be proven for types-in-contexts, but note that there is no $F : \text{Type} \to \text{Type}$ in System F. To gracefully handle identity extension for type operators in general, it's better to switch to reflexive graph models, where identity extension is given mutually with the rest of the model.
Let's use the reflexive graph model of some type theory. This means that for every closed $F : \text{Type} \to \text{Type}$, we get a semantic $F^S : \text{Set} \to \text{Set}$, together with $F^R : (A, B : \text{Set}) \to \text{Rel}\,A\,B \to \text{Rel}\,(F\,A)\,(F\,B)$ where $\text{Rel}\,A\,B$ denotes a set of proof-irrelevant relations. We also get identity extension: $F^R\,A\,A\,(\text{Id}\,A) = \text{Id}\,(F\,A)$, where $\text{Id}\,A$ is the identity relation. In the following, let's omit all $^S$-es and don't talk about syntactic things, only about semantic things, so that we may write $F : \text{Set} \to \text{Set}$.
Assume $F, G : \text{Set} \to \text{Set}$ are functors, and $\eta : (A : \text{Set}) \to F\,A \to G\,A$. Let's write $\text{map}$ for functorial mapping.
We assume that everything is parametric. This means that we get $F^R$, $G^R$, $\eta^R$ and ${\text{map}_F}^R$ and ${\text{map}_G}^R$. Assume $f : A \to B$ and $x : F\,A$.
To show:
$$ \text{map}_G\,f\,(\eta_A\,x) = \eta_B\,(\text{map}_F\,f\,x) $$
By identity extension for $G$, this is equivalent to
$$ G^R\,B\,B\,(\text{Id}\,B)\,(\text{map}_G\,f\,(\eta_A\,x))\,(\eta_B\,(\text{map}_F\,f\,x)) $$
Category law:
$$ G^R\,B\,B\,(\text{Id}\,B)\,(\text{map}_G\,f\,(\eta_A\,x))\,(\text{map}_G\,id\,(\eta_B\,(\text{map}_F\,f\,x))) $$
To show the above, we use ${\text{map}_G}^R$, i.e. that $\text{map}_G$ preserves all relations. We have to pick two relations, one in $\text{Rel}\,A\,B$ and one in $\text{Rel}\,B\,B$ and show that $f : A \to B$ and $id : B \to B$ are pointwise related. We pick the graph of $f$ and $\text{Id}\,B$, and the functions are clearly pointwise related. It remains to show:
$$ G^R\,A\,B\,(\text{Graph}\,f)\,(\eta_A\,x)\,(\eta_B\,(\text{map}_F\,f\,x)) $$
We know that $\eta$ preserves all relations, so it's enough to show:
$$ F^R\,A\,B\,(\text{Graph}\,f)\,x\,(\text{map}_F\,f\,x) $$
Category law:
$$ F^R\,A\,B\,(\text{Graph}\,f)\,(\text{map}_F\,id\,x)\,(\text{map}_F\,f\,x)$$
We instantiate ${\text{map}_F}^R$ with $\text{Id}\,A$ and $\text{Graph}\,f$ and it remains to show:
$$ F^R\,A\,A\,(\text{Id}\,A)\,x\,x $$
By identity extension for $F$, this is equivalent to:
$$ x = x $$

The same thing in Agda:
-- Agda 2.6.1, stdlib 1.5

open import Relation.Binary.PropositionalEquality
  renaming (sym to infix 6 _⁻¹; cong to ap; trans to infixr 5 _◾_; subst to tr)
open import Function

coe : ∀{i}{A B : Set i} → A ≡ B → A → B
coe refl a = a

Rel : Set → Set → Set₁
Rel A B = A → B → Set

Id : (A : Set) → Rel A A
Id A x y = x ≡ y

Graph : {A B : Set} → (A → B) → Rel A B
Graph f a b = f a ≡ b

happly : ∀{i j}{A : Set i}{B : Set j}{f g : A → B} → f ≡ g → ∀ x → f x ≡ g x
happly refl x = refl

record Functor : Set₁ where
  field
    !      : Set → Set
    map    : {A B : Set} → (A → B) → ! A → ! B
    map-id : ∀ {A} → map {A} id ≡ id
    map-∘  : ∀ {A B C}(f : B → C)(g : A → B) → map (f ∘ g) ≡ map f ∘ map g

record Functorᴿ (F : Functor) : Set₁ where
  private module F = Functor F
  field
    !     : ∀{A₀ A₁} → Rel A₀ A₁ → Rel (F.! A₀) (F.! A₁)
    map   : ∀ {A₀ A₁}(Aᴿ : Rel A₀ A₁){B₀ B₁}(Bᴿ : Rel B₀ B₁)
            (f₀ : A₀ → B₀)(f₁ : A₁ → B₁)(fᴿ : ∀ {a₀ a₁} → Aᴿ a₀ a₁ → Bᴿ (f₀ a₀) (f₁ a₁))
            {fa₀ fa₁} → ! Aᴿ fa₀ fa₁ → ! Bᴿ (F.map f₀ fa₀) (F.map f₁ fa₁)

    idext : ∀ {A} → ! (Id A) ≡ Id (F.! A)

  reflexive : ∀ {A x} → ! (Id A) x x
  reflexive {A} {x} = tr (λ f →  f x x) (idext ⁻¹) refl

module _
  (F G : Functor) (Fᴿ : Functorᴿ F) (Gᴿ : Functorᴿ G) where

  module F  = Functor F   ; module G  = Functor G
  module Fᴿ = Functorᴿ Fᴿ ; module Gᴿ = Functorᴿ Gᴿ

  module _ (η  : ∀ {A} → F.! A → G.! A)
           (ηᴿ : ∀ {A₀ A₁}(Aᴿ : Rel A₀ A₁){fa₀ fa₁}
                 → Fᴿ.! Aᴿ fa₀ fa₁ → Gᴿ.! Aᴿ (η fa₀) (η fa₁)) where

    η-is-natural : ∀ {A B}(f : A → B) x → G.map f (η x) ≡ η (F.map f x)
    η-is-natural {A} {B} f x =
      let lem1 : Fᴿ.! (Graph f) (F.map id x) (F.map f x)
          lem1 = Fᴿ.map (Id A) (Graph f) id f (ap f) {x} {x} Fᴿ.reflexive

          lem2 : Fᴿ.! (Graph f) x (F.map f x)
          lem2 = tr (λ y → Fᴿ.! (Graph f) y (F.map f x)) (happly F.map-id x) lem1

          lem3 : Gᴿ.! (Graph f) (η x) (η (F.map f x))
          lem3 = ηᴿ (Graph f) lem2

          lem4 : Gᴿ.! (Id B) (G.map f (η x)) (G.map id (η (F.map f x)))
          lem4 = Gᴿ.map (Graph f) (Id B) f id id lem3

          lem5 : Gᴿ.! (Id B) (G.map f (η x)) (η (F.map f x))
          lem5 = tr (λ y → Gᴿ.! (Id B) (G.map f (η x)) y) (happly G.map-id _) lem4

      in coe (happly (happly Gᴿ.idext (G.map f (η x))) (η (F.map f x))) lem5


Not getting the clear picture of Goto actions , reduce and shift actions in SLR Parsing I am going through the following lecture notes on LR parsing :

https://www3.nd.edu/~dthain/courses/cse40243/fall2016/chapter4b.pdf

For the following grammar :

The following LR automation has been done :

and the following is the LR parsing table drawn for it :

In the table I can see that the alphabets "R" ,"G" and "S" denote the action being taken and the number following them is the index number of the state to which the transition is taking place .

Now , what I am unclear about is what exactly is a "goto"action ? I can see that goto actions , "G1" , "G8" , "G3", "G6" are occurring only in response to non- terminals "'E" and "T" . And all of them have two rules by using which we can reduce the expression to the start symbol.

But I am unable to draw any further patterns to interpolate what exactly is a "Goto action " .

Nevertheless , when at state 4 an input of "(" results in shift but how does an input of ")" or "+" result in reduction , which I ,with certain degree of confidence, guess to be , the action of replacing few symbols with the left hand side of certain production .

So , how exactly to make sense of this table ? What exactly is a GOto  and am I right about "reduction"?

Remember that a stack entry is a state and a symbol. (In fact, the symbols are not really important for the parser, but they will prove useful later on when you encounter semantic values.)

A reduction action consists of popping the right hand side of a production from the top of the stack and pushing the left hand side. (The number in the reduction action is the number of the production, so you know what the left- and right-hand sides are.)

When the right hand side is popped off the stack, a new state is revealed (at the top of the stack). The Goto action which corresponds to that state and the left-hand side non-terminal tells you which state to push along with the non-terminal.

The parser's actions are illustrated in the chart at the end of section 4.8 of your text, which I reproduce below. However, the reduction and subsequent goto action are combined in the chart:

Stack         Symbols       Input             Action
0                           id ( id + id) $   shift 4
0 4           id            ( id + id ) $     shift 5
0 4 5         id (          id + id ) $       shift 4
0 4 5 4       id ( id       + id ) $          reduce T → id
0 4 5 8       id ( T        + id ) $          reduce E → T
0 4 5 6       id ( E        + id ) $          shift 2
0 4 5 6 2     id ( E +      id ) $            shift 4
0 4 5 6 2 4   id ( E + id   ) $               reduce T → id
0 4 5 6 2 3   id ( E + T    ) $               reduce E → E + T
0 4 5 6       id ( E        ) $               shift 7
0 4 5 6 7     id ( E )      $                 reduce T → id ( E )
0 8           T             $                 reduce E → T
0 1           E             $                 accept

Let's look at what the parser does at the highlighted line in the above chart. We can see that the parser is in state 3 (which is the state at the top of the stack) and is about to perform a reduction.
 The right-hand side of the production to be reduced has three symbols – E + T – which we can also see at the top of the stack (in the Symbols column). So the first thing the parser does is pop the right-hand side of the production:

0 4 5 6 2 3   id ( E + T    ) $               pop E + T

Now, the parser is in state 5 and needs to do something with the E which was just reduced (that is, the left-hand non-terminal in the reduced production).

0 4 5         id (          ) $               push E

We consult the parser action chart, looking for the action for an E corresponding to state 5. That action is G6, meaning that the parser pushes state 6 onto the stack with the symbol E, giving us the next line:

0 4 5 6       id ( E        ) $               shift 7

Aside from the fact that it's a non-terminal rather than a terminal being pushed onto the stack, there is no difference between a shift and a goto action. Of course, the goto action does not consume the lookahead symbol, so that symbol is then used in the new state (resulting, in this case, in a shift action).


Is it possible to transfer a point from one camera to another, given n corresponding points? I have 2 images of a scene taken at one moment by two identical cameras (similar cameras intrinsic parameters) by to arbitrary locations and at two arbitrary orientations (different cameras poses).
On the images n points correspondence p_i1={x_i1, y_i1, z_i1}↔p_i2={x_i2, y_i2, z_i2}, i=1,2,...,n are given. Let for simplicity z_i1=z_i2=f for all the points.

Is it possible at any number of corresponding points n to derive a transformation relation from one camera view to another so that for an additional point p_01 known only at one image to be able to locate it on the second image p_02?

My guess is (due to the fact that projection on a camera sensor plane is 3d-to-2d) it is not possible! And at most one may find a line on the 2nd image on which the additional point could be positioned.

I know that the task is solved with a homography matrix for two cameras having one center.
I know it must be solvable for the case of all the points being coplanar.

But is it possible for arbitrary positioned cameras and arbitrary situated (non-coplanar in world frame) corresponding points?

Is it possible at any number of corresponding points n to derive a transformation relation from one camera view to another so that for an additional point p_01 known only at one image to be able to locate it on the second image p_02?

The answer is no - it is impossible. Each point on the image1 may in general correspond to an entire line on the image2 (see https://en.wikipedia.org/wiki/Epipolar_geometry). The homography matrix is a projection matrix of one plane on another and, therefore,  is useful when you have a plane object ( chessboard, book, painting etc.) pictured on both images.


Understanding terms related to 2SAT algorithm Recently I am learning about solution of the 2-satiability problem using strongly connected components. There is a theorem related to this problem given below:
Let $F = Q_lx_1 Q_2x_2\ldots Q_nx_n C$ be a quantified Boolean formula with no free variables, where each $Q_i$ is either universal or existential, and $C$ is in conjunctive normal form. That is, $C$ is a conjunction of clauses, each clause is a disjunction of literals, and each literal is either a variable, $x_i$, or the negation of a variable, $x_i$ ($1 \leq i \leq n$).

Theorem 2: The formula $F$ is true if and only if none of the following three conditions holds:
3(i) An existential vertex $u$ is in the same strong component as its complement $u’$.
3(ii) A universal vertex $u_i$ is in the same strong component as an existential vertex $u_j$ such that $j < i$ (i.e., $x_i$ is not quantified within the scope of $Q_i$).
3(iii) There is a path from a universal vertex $u$ to another universal vertex $v$. (This condition includes the case that $v = u$.)

In the proof they use this definition:
We call a vertex universal if the corresponding variable is universally quantified and existential otherwise.
But I am not familiar with the terms universal vertex and existential vertex. Can any one please explain these terms to me?

The terms universal vertex and existential vertex are not universal, but rather specific to this specific theorem. The context is a graph on the set of literals (variables and their complements). Presumably for every clause $\ell_1 \lor \ell_2$ in $C$, there is an arrow from $\bar{\ell}_1$ to $\ell_2$.

A vertex is called universal if its corresponding variable is universally quantified, that is, quantified as $\forall x_i$. In other words, if $Q_i x_i = \forall x_i$ then the vertices $x_i$ and $\bar{x}_i$ are universal.

Similarly, a vertex is called existential if its corresponding variable is existentially quantified, that is, quantified as $\exists x_i$.


Show $\{0^1^|≠\}$ is not regular So I have the question: show "Show $\{0^1^|≠\}$ is not regular". I've already seen various proofs for this question, but they all have one step I don't get.
They all take: $\bar{L}∩(0^∗1^∗)$ ($\bar{L}$ is the complement of $L$) and show that it's not regular. I don't get why we can't just take $\bar{L}$. Because isn't $\bar{L} = \{0^1^|m=n\}$ which is the same as $\{0^n1^n|n ≥ 0\}$ which we know is not regular? What am I missing?

Try to express in natural language what $\overline{L}$ contains; that is, what words $L$ doesn't contain. Most obviously, it's "words of the form $0^m0^n$, with $m = n$." However, it also contains "words that are not of the form $0^m1^n$", such as "$101010$". That's why the intersection with $0^*1^*$ is employed, to not bother with these words.
The demonstration is then possible because intersection and complementation are closed properties on the regular language. So if $\overline{L} \cap L(0^*1^*)$ is not regular, we know that $\overline{L}$ must not be regular, so its complement, $L$, must not be regular.


Proving of regular language Is this regular or not
L = {w1w^R | w ∈ {0,1}*
(where for any word w ∈ {0,1})*, w^R denotes the reverse of w)

L is not a regular language.
We can contradict by pumping lemma for regular languages.
Let assume L is regular, so there exists an integer $ k $ of pummping lemma.
$ w = a^kb $
$ w^R = ba^k $
$ ww^R = a^kbba^k \in L $
$ w' = a^{k-r}bba^k \notin L , r>0 $
Contradiction to $ w' \in L $.


A polynomial reduction from any NP-complete problem to bounded PCP Text books everywhere assume that the Bounded Post Correspondence Problem is NP-complete (no more than $N$ indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something that an undergrad can understand) polynomial time reduction from another NP-complete problem.

However every reduction I can think of is exponential (by $N$ or by the size of the series) in run-time. Perhaps it can be shown that it is reducible to SAT?

As is often the case with NP-reductions, it makes sense to look for similar problems. In particular, it is hard to encode global conditions such has "have seen some nodes" into PCP (with polynomially many tiles) which contraindicates graph problems, packing problems would require us to encode unary numbers in PCP (creating exponentially large instance), and so on. Therefore, a string problem with only local restrictions can be expected to work best.

Consider the decision version of the shortest common supersequence problem:

  Given two strings $a,b \in \Sigma^+$ with $|a|=n$ and $|b|=m$ and $k \in \mathbb{N}$, decide whether there is a string $c \in \Sigma^+$ with $|c| \leq k$ such that $a$ and $b$ are subsequences of $c$.

The idea is to let PCP build supersequences of $a$ and $b$ from left to right, encoding in the tiles' overlaps at which position we are in $a$ and $b$, respectively. It will use one tile per symbol in $c$, so $k$ corresponds to the BPCP's bound: if we can solve this PCP with $\leq k$ tiles, you can read off the common supersequence of equal length, and vice versa.

The construction of the tiles is a bit tedious, but quite clear. Note that we will not create tiles that do not forward $a$ or $b$; such can never be part of a shortest common supersequence, so they are superfluous. They can easily be added without breaking the properties of the reduction.

The numbers in the overlaps are encoded in binary, but using symbols outside of $\Sigma$ and padding them to a common length $\log \max(m,n)$. Thus we ensure that the tiles are used as the graphics suggest (tetris), that is characters and index-encoding overlaps do not mix (PCP does not prevent this per se). We need:

Starting tiles: $c$ can start with $a_1$, $b_1$ or both if they are equal.
Intermediate tiles: $c$ can proceed with the next symbol in $a$, in $b$ or both if they are equal.
Terminating tiles: $c$ ends with the last symbol of $a$ (if the last one of $b$ has been seen already), similar for $b$, or with the last symbol of both.

These are the tile schematics. Note that the intermediate tiles have to be instantiated for all pairs $(i,j) \in [n]\times [m]$. As mentioned above, create the tiles without $*$ only if the respective characters in $a$ and $b$ match.

[source]

The $*$ are symbolic for "don't care"; in the actual tiles, the other symbol will have to be copied there. Note that the number of tiles is in $\Theta(mn)$ and each tile has length $4\log \max(m,n) + 1$, so the constructed BPCP instance (over alphabet $\Sigma \cup \{0,1\}$ plus separation symbols) has polynomial size. Furthermore, the construction of every tile is clearly possible in polynomial time. Therefore, the proposed reduction is indeed a valid polynomial transformation which reduces the NP-complete shortest common supersequence problem to BPCP.


Counting permutations whose elements are not exactly their index ± M I was recently asked this problem in an algorithmic interview and failed to solve it.

Given two values N and M, you have to count the number of permutations of length N (using numbers from 1 to N) such that the absolute difference between any number in the permutation and its position in the permutation is not equal to M.
Example - If N=3 and M=1 then, 1 2 3 and 3 2 1 are valid permutations but 1 3 2 is invalid as the number 3 is at position 2 and their difference is = M.

I tried NxM Dynamic programming but failed to form a recurrence that doesn't count repetitions.

The first thing I would ask when given this question would be

  Do you want a polynomial time algorithm?

and then I'd hope the answer is 'no'. I suspect that this problem is NP-hard, for the following reason:

The natural approach to this problem is to consider the placement of the first number and derive a recursive formula to place the others. This works nicely for the $M=0$ case (i.e. counting the number of derangements), as it doesn't matter on what position you have placed the first number, since there is only one 'illegal' position of every number. In other words, this approach leads to independent subproblems.

For $M>0$, this is not so simple, as we now can have $2$ illegal positions for some numbers. Which of these positions remain in the subproblem is now relevant to the solution of the subproblem. Only considering the number of 'illegal' positions is not sufficient, as the 'chains' of numbers that share an illegal position are required to determine the structure of the subproblems of that subproblem. So, this approach essentially leads to the following subproblem:

  Given a set $A \subseteq \mathbb{N}$, a set $B \subseteq \mathbb{N}$ both of size at most $N$ and a natural number $M$, count the number of perfect matchings on the bipartite graph $(A,B,E)$, where $(a,b)\in E$ if and only if $|a-b|\neq M$.

This problem looks hard. The only approach to this problem I see is inclusion/exclusion, which will not lead to a polynomial time algorithm.

We can consider approaches that do not rely on the iterative placement of the numbers, but I have no clue how you would do this. (especially during an interview!)

Of course, all this is mere speculation and it is still possible that a clever trick can give a polynomial time solution, but I hope I have made convincing argument that this trick has to be very clever indeed.

Perhaps it is possible to show NP-hardness by reducing this problem to #2-SAT (the 'chains' of numbers that share illegal positions seem a non-trivial choice that could be matched with the selection of a truth-value), but I haven't seen an obvious way to do that as of now.

In case the interviewer would actually be satisfied with an exponential time algorithm, I'd simply generate all possible solutions by adapting a recursive backtracking algorithm to generate a permutation to exclude this particular case.


When does $1.00001^n$ exceed $n^{100001}$? I have been told than $n^{1000001} = O(1.000001^n)$. If that's the case, there must be some value $n$ at which $1.000001^n$ exceeds $n^{1000001}$.

However, when I consult Wolfram Alpha, I get a negative value for when that occurs.
http://www.wolframalpha.com/input/?i=1.000001%5Ex+%3D+x%5E1000001

Why is that? Shouldn't this value be really big instead of negative?

The $n$ where the two expressions are equal isn't all that huge. Here's how to calculate it.

We want
$$ 1.000001^n \approx n^{1000001}.$$
This is the same as
$$e^{n \log 1.000001} \approx e^{1000001 \log n}.$$
Now, taking the $\log$ of both sides, and using Taylor's formula to approximate the left-hand side, we get
$$ n*10^{-6} \approx 10^6 \log n,$$
or
$$\frac{n}{\log n} \approx 10^{12}.$$
Since this means $\log n \approx \log 10^{12},$ we get $$n \approx 10^{12} \log 10^{12} = 2.7 * 10^{13}. $$
More exactly, using Maple to solve the equation numerically (you have to give it the estimate above as a starting value or it gives up), we find that $n \approx 3.1*10^{13}$.


Filing systems using index blocks I know that a disadvantage of the index block system is that it can be wasteful of space if the files involved are mostly small in size, as index blocks are allocated from free space as required and at least one index block is needed for each file regardless of size. On average there is ½ block wastage per file in the index block system however what I don't understand is how the index block structure could possibly be modified to reduce this wastage.

If anyone can help it would be greatly appreciated.

First of all, it is not necessarily true that on average half a block is wasted. The main reason why this is false is that for small files it might be the case the more than half a block is wasted on average. Moreover, this is your main worry regarding this wastage, since is you waste half a block per large file, the fraction of blocks wasted is actually quite small. So you have to worry mainly about small files, whose size is at most a handful of blocks, and most of all for files whose size is much smaller than one block.

Second, you're asking how the index block structure can be modified to reduce this wastage. Here it's your time to be creative. One idea is to have special blocks for storing small files. I'll let you flesh this idea out. Another idea is to allow the first block of a file to start at the middle, so that two files can share one block. Of course this becomes somewhat problematic when files are updated.


Placing 1d items in a 2d grid with constraints I'M looking for an algorithm (preferably polynomial) for the following problem:

Input:
- an M x N grid, where each square can be either empty or occupied
- a list of items
- a list of constraints

Output:
the grid, such that all items are placed and the constraints aren't violated.

Each item is a 1d block of length k. Different items may have different length, and there may be several items with the same length. Items can't ovelap each other.

Example 1:
Given 1 x 5 grid and 2 items of lengths 1, 2 respectively. The following solutions are acceptable:

11100

10110

11010

and so forth.

Example 2:
Given 3 x 5 grid and 2 items of lengths 1, 2 respectively. The following solutions are acceptable:

00110
10000
00000

11000
10000
00000

etc.

Possible constraints:
a. Isolation - items may not touch each other. e.g. the following solutions is illegal:

Example 1:

11100

Example 2:

11000
10000
00000

However this is a legal solution:

01100
10000
00000

i.e. touching diagonals are legal.

b. Facing - 2 items must be placed one in front of the other. e.g.

11000
00000
11000

What I did so far is to find a solution for a simpler problem, where the grid is 1d and the only possible constraint is Isolation. I solved it by representing it as a search problem, and using A* with the heuristic: sum of lengths of items not placed yet. The problem is that it suffers from state explosion which will only deteriorate in higher dimensions.

The 1-dimensional case (a $1 \times n$ grid) is straightforward.  I'm not sure why you are having difficulty finding solutions when the grid is 1-dimensional.  If you don't have any constraints, then you just add up the lengths of the items; if their total length is $\le n$, you can solve it (just put the items next to each other), otherwise you can't.  To deal with the isolation constraint, you can note that the problem with tiles lengths $\ell_1,\dots,\ell_k$ and an isolation constraint is solvable if and only if the problem with tile lengths $\ell_1+1,\dots,\ell_{k-1}+1,\ell_k$ and no isolation constraint is solvable.

The 2-dimensional case (a $m \times n$ grid) looks much harder.  One approach, in practice, might be to use a SAT solver.  Introduce boolean variables $x_{i,j,k,d}$ and $y_{i,j}$, with the intent that $x_{i,j,k,d}=1$ if the $k$th tile starts at location $(i,j)$ on the grid and proceeds in direction $d$, and $y_{i,j}=1$ if location $(i,j)$ is covered by some tile.  Now you can formulate your problem as a set of boolean constraints on the $x$'s and $y$'s, then feed it to an off-the-shelf SAT solver.  You could experiment with this for the parameter sizes that tend to crop up for you in practice and see how well it works.  SAT solvers often work surprisingly well, though there is no guarantee: they are not a silver bullet, and the worst-case running time will remain exponential.  There are many other ways to represent this as a SAT problem, too, so you could try other representations as well to see which tends to work best with existing SAT solvers.

I'm not sure you're going to be able to do much better than this: as FrankW says, for 2-dimensional grids this smells like it might be NP-complete in the general case.


Distribute numbers 1,N on a grid as evenly as possible I'm working on a complex engineering problem that I've essentially reduced to this problem:

I have a set of natural numbers $1,N$ and a grid (square or hexagonal) of exactly $N$ cells. I have to map each number to each cell so that the distribution (in a geometric sense) is as flat as possible. I'm still working on the definition of flat, but so far

The average of the numbers of a cell and its nearest neighbours must be as close to $N/2$ as possible, for every cell.
The average of the distance between a cell and each neighbour must be as large as possible.

If a cell has a number $n$ and its neighbour $m$ the distance between these neighbours is $min(|n-m|,N-|n-m|)$. It's essentially cyclical.

If $.$ represents a small number and # a large number I'm looking chessboard-like configurations like

.#.#.#.#
#.#.#.#.
.#.#.#.#

I need to find the best configuration (or a very good one) without using brute force.

Can you point me to some good algorithms that may be useful for this problem? I could only get above-average results on my own.

In my problem $N\approx~500$ and there is no runtime constraint.

Simulated Annealing might work well for this problem.

The idea is to introduce a "temperature" component to your heuristic function to avoid getting stuck at local optima. Temperature corresponds to how willing the heuristic function is to accept an inferior arrangement. With simulated annealing, temperature starts off high and decreases until an optimal solution is found.

Here is solution to the Travelling Salesman Problem using simulated annealing

You can tinker with the starting temperature and its rate of change to try and find an optimal arrangement.


Can the memory cache hold instructions? My teacher told us that when the ram runs out of space it will push a program in the cache, i argued that the program should go to the swap space in the hard drive, plus the memory cache cannot hold instructions because instructions and data have different access patterns, it can only hold data frequently accessed.
So i am asking the experts, can the memory cache hold instructions ?
Edit : what i mean by memory cache is the L1 memory cache

tillz is broadly correct, however there is one more detail of many modern systems which you should be aware of.

On some modern CPUs, when the power is first turned on and the CPU transfers control to firmware, almost all of the hardware needs to be initialised before it's used. This includes the hardware which arbitrates between cores in a multicore machine. One upshot of this is that main memory may not be available.

So some CPUs (notably Intel-esque machines) do support a mode where cache can be used as if it were RAM. Intel calls this "no-fill mode", and AMD calls it "cache-as-RAM mode". This is handled by the same mechanism that the CPU uses to implement non-cached memory (e.g. memory-mapped I/O).

On most modern CPUs, L1 cache split in two: an instruction cache, which is read-only, and the data cache, which is read-write. It does this so that the CPU pipeline can maintain the illusion of a Harvard architecture on top of a von Neumann architecture: the L1 instruction cache is "program memory" and the L1 data cache is "data memory", and they sit on top of a combined lower-level (probably L2) cache. "Combined" here means "both instructions and data", that is, it implements the von Neumann memory model.

Because the L1 instruction cache is read-only, the only way you can get anything in it is by filling from somewhere, and that somewhere is the next-level cache. So it's actually the lower-level cache which is acting as RAM, not the L1 cache.


How to evaluate the accuracy of a method for the extraction of the principal lines of the palmprint Let's assume that I've implemented a method for the extraction of the principal lines of the palmprint. For instance, let's say that I'm able to do a transformation like the following one (image from Patprapa Tunkpien, Sasipa Panduwadeethorn and Suphakant Phimoltares):

Now, I want to make an evaluation of the accuracy level of my algorithm. In order to do this, I have only the algorithm, and a big set of palmprint images (on which I can execute the extraction procedure to obtain the corresponding set of binary images of principal lines of the palmprint).

How can I evaluate the accuracy level of my algorithm, without having any kind of reference extraction method?

To understand how to evaluate the accuracy of your algorithm, the best way will be to understand how the result of your algorithm will be used.

It is likely that your algorithm is just a component in a system.  After all, it's not like being able to visualize the right-hand picture is somehow a useful and important goal in its own right.  Rather, it is likely a useful stepping stone along the way to some more meaningful goal.

For instance, maybe you want to do biometric authentication of the individual, and you are planning to use the palm print for authentication, so it is helpful to first extract the three principle lines of the palm.  In that case, you will probably take the result of your transformation and then feed it in as input to the next step of processing; ultimately, the final answer of the authentication process will be "yes, accept this is the right person" or "no, this is not the right person".  So, in this example, the ultimate goal is authentication.  Therefore, I would suggest that the way to evaluate your algorithm is to evaluate how well the palmprint authentication process works, when it uses your algorithm.  We could ask about the false accept rate (if an imposter tries to authenticate, what is the probability he/she is wrongly accepted?) and the false reject rate (if the legitimate individual tries to authenticate, what is the probability he/she is wrongly rejected?).  Those are two useful metrics for evaluating the accuracy of biometric authentication, so you could evaluate how accurate the process is when using your particular transformation as one of the stages.

In general, a useful way to evaluate accuracy is to look at how the output of your transformation will be used, find some metric that is meaningful and relevant to that particular application, and then measure that metric when we use the output of your transformation as input to the next stage of processing.  Of course, this does mean that we cannot evaluate your transformation in isolation -- but you know what?  In some sense, that might be unavoidable.

There is another option, but it will require more work, and may yield results that are harder to interpret.  You could hand-label each of the input images with a manually drawn line for each of the three principle lines.  Call this the "golden reference" lines.

Then, you could manually or automatically process the output of your transformation to get the three lines (by extracting the center of each of the three broad brush strokes we can see in your right-hand image).  Call these the "algorithmically inferred" lines.

Next, you could define some metric for the distance between the golden reference lines and the algorithmically inferred lines: for instance, maybe the average distance, or the root-mean-square distance.  Finally, you could evaluate your algorithm on a reasonable test set, using this metric to quantify how close your lines are to the golden reference lines.

The problem with this approach is that it is harder to make sense of the results of such an accuracy metric.  How do you tell when your algorithm is "good enough"?  Beats me.  The only way to know that is to look at how the output of your algorithm will be used -- which gets us back to my original suggestion of evaluating your algorithm as part of a larger system.


Pseudo code algorithm for beauty contestant question Say beauty pageants are judged based on 3 criteria: 1) Appearance 2) Personality 3) Talent. A contestant $C$ will beat another contestant $C'$ if she gets higher scores in ALL THREE of the criteria.

There are $n$ girls competing. Contestant $C_i$ is "Model Material" if $C_i$ is not beat by any other contestant $C_j$. Pretend you're the announcer and you have a collection of tuples: $(A_i, P_i, T_i)$ for $i = 1, 2,...,n$

The $i$th tuple contains the appearance, personality, and talent rating for $C_i$ (higher scores are better). Return a list of the "Model Material" contestants in in $O(n\log{n})$ time.

Given a data structure w/ a set $E$ of ints that, given an int $a$, --- (1) tells if a is in $E$ (2) finds smallest value > $a$ or largest value < $a$ in $E$ (3) inserts or removes a from $E$ in $O(\log{|E|})$ time.

I am trying to write pseudo-code for this algorithm but am lost trying to think of a correct algorithm that also runs in $O(n\log{n})$ time. I thought about starting initially with the $A_1$, $P_1$, and $T_1$ values for the first contestant, and if another contestant has a higher score in each category, remove the current tuple and replace it with the higher tuple, then repeat this process starting with a different contestant each time, but that's obviously not $O(n\log{n})$, and probably doesn't even work.

(This question was from my algorithms professor, and I can't find it online or in our textbook)

You are asking for the Pareto-optimal front in 3D space.  This is a well-studied problem.

In 2D, there are $O(n \log n)$ time algorithms: see, e.g., What are some interesting applications of the skyline problem?, An online algorithm to find the Pareto frontier elements, minimum subset of dominating 2D points.

In 3D, life is more complicated, but apparently it is still possible to solve this in $O(n \log n)$ using fancy methods.  See the following paper:

On Finding the Maxima of a Set of Vectors.  H.T. Kung, F. Luccio, F.P.Preparata.  Journal of the ACM, vol 22 no 4, Oct 1975, pp.469--476.