Kleene star of an infinite unary language always yields a regular language Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$.

Thus $L$ consists of sequences of $a$ of all lengths, including a sequence
of length $0$. Let $L_2$ be any infinite subset of $L$. I need to show there always exists a DFA to recognize $L_2^*$.

If $L_2$ is a finite subset it is very obvious as $L_2$ would be a DFA and hence by Kleene closure $L_2^*$ would be recognized by a DFA. But I am unable to get it for infinite subset as $L_2$ may not be expressed as DFA when, e.g., string lengths are prime.

Suppose there are two words in the language whose lengths are relatively prime. Let these lengths be $x$ and $y$. We know (see this) that by adding these numbers to each other repeatedly, we can get any number greater than $(x - 1)(y - 1) - 1$. So if $x$ and $y$ are $13$ and $7$, we can write any number greater than $72$ as a linear combination of $7$ and $13$. What this means for us: $L_2^*$ consists of some arbitrary finite language (regular, as all finite languages), in union with the language $\{w \in a^* \mid |a| > (x-1)(y-1)-1\}$. This language is regular since it is the language of all words with a finite set of words removed. Since $L_2^*$ is a union of regular languages, it must also be regular.

If all words in $L_2^*$ have lengths which share a greatest common factor (call this common factor $m$), then repeat the above argument, but instead of using string lengths, use string lengths divided by $m$. In this case, $L_2^*$ will be the concatenation of an arbitrary finite language (regular) and the language $\{w \in (a^m)^* \mid |w| > m^2[(x/m - 1)(y/m - 1) - 1]\}$, also regular (since $(a^m)^* is regular and we are removing finitely many words from it).

For example, suppose all words in $L$ have a GCF of 2, and the language contains the words $a^4$ and $a^{10}$. We have $m = 2$, $x/m = 4/2 = 2$, and $y/m = 10/2 = 5$, which are relatively prime. Therefore, we know that we can get any word whose length is multiple of $m$ if the length is greater than $m^2[(x/m - 1)(y/m - 1) - 1] = 2^2[(2 - 1)(5 - 1) - 1] = (4)(3) = 12$ by concatenating $a^4$ and $a^{10}$.


Can we move quantifiers to the left in predicate logic? Say I have part of a query in the form: ∃xa(...)∧∃xb(...)∧∃xc(...), where a, b, and c are attributes and the ellipses can be anything (I'm looking for a general rule). Is this equivalent to saying ∃xa,xb,xc(...∧...∧...) - i.e. compacting all the existential quantifiers into one and 'anding' their domains together?

For example, if I have the query:

would it be correct (albeit unwieldy) to write it as:

{ xpid | ∃xpname,xcolor,xsid,xsname,xaddress,xcost,ysid,ysname,yaddress,ycost( PARTS(xpid,xpname,xcolor) ∧ SUPPLIERS(xsid,xsname,xaddress... (and then the rest of the query)

You are looking for prenex normal form in which all quantifiers "come first".

It exists for every first-order formula but you have to take care when transforming; multiple quantifiers may use the same variable (name) in the original formula, but they may not in the normal form.


What does binary NP-Hard exactly mean? Can someone tell me what binary NP-Hard exactly means.
My understanding was that if the problem is encoded in binary and if the problem is binary NP-Hard, its complexity of solving is NP-Hard. Is this the correct interpretation?

I also wanted to know, if binary NP-Hard also says something about Strong or Weak NP-Completeness of the problem.

The complexity of a computational problem depends on the exact representation of the input.

One of the go-to examples here is the Knapsack problem. Given $n$ items with (integer) weights $w_1,...,w_n$, and two integers $W,V$, decide whether there exists a subset $S\subseteq [n]$ such that $V\le \sum\limits_{i\in S}w_i\le W$. We know that the problem can be solved in time $O(nW)$ in the word-ram model. This means that assuming $P\neq NP$, knapsack is not NP complete if the input is of size $\Omega(nW)$, hence it is not complete when $W$ is encoded in unary. Thus, when talking about the NP completeness of knapsack, it is important to specify that we're talking about the version where $W$ is encoded in binary, or "binary knapsack" for short.


Whatever that can be done using algorithm can be done using Turing machine In 1937 how was Alan Turing so sure that all that can be done using algorithms can be implemented using a Turing machine?
Since that period many new algorithms were implemented. What was his hypothesis behind this theory ?

The hypotesis is the following:

"Since an algorithm is a well-defined sequence of steps we can always execute an algorithm in a piece of paper(sometimes we may need a really big paper) using a pencil."

Then he created the Turing Machine who can simulate a hand using a pencil with an infinite paper.


Conversion from Decimal form to BCD I have seen a way how to convert a decimal number to BCD (packed & unpacked) using 8,4,2,1 weighing forms but how to do it using 4,2,2,1 and 7,4,2,1 ? Any method please.Suggestions

If we want to represent 8 base 10 then it will be represented as follows:

A) 7421 code
   8(10)= 7+1 = 8
   1 0 0 1 -> 7 4 2 1 code
   1x7+4x0+2x0+1x1=7+0+0+1=8
   8(10)=1001(7421)

B) 5421 code
   8(10)= 5+2+1
   therefore   5 4 2 1
               1 0 1 1
  8(10)= 1011(5421)

C) 4221 code
   8(10)= 4+2+2
   therefore 4 2 2 1
             1 1 1 0
   8(10)= 1110(4221)

There you go. If this is helpful then please select this as an answer.


Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree? I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq i\leq n$ I would like to compute $|\lbrace j|j>i\wedge a_j > a_i\rbrace|$.

My idea: Implement an AVL tree, put elements from this sequence to this AVL tree from the last one to the first one. Before putting each element obtain the amount of larger elements the tree already contains. I can implement an AVL tree that would allow such operations.

But alas, I do have to implement such an AVL tree, since unfortunately the standard C++ std::set doesn't allow obtaining the distance between two iterators in logarithmic time.

Now I need this to solve a task from one of the former exams on algorithms and data structures. These exams usually contain two tasks, a "simpler" one and a "harder" one. And this is the "simpler" one. Now I doubt that a "simpler" task would require implementing an AVL tree. A "harder" task might; but a "simpler" one, doubtfully. Therefore, I would say, there should be a less laborious way to solve this task.

Is there any simpler way to compute what I need to compute?

You can use any balanced binary search tree data structure (doesn't have to be AVL tree).  Some such data structures are easier to implement (maybe a AA tree, left-leaning red-black tree, or splay tree?).  If you don't care about worst-case running time, it doesn't need to be balanced.  One pragmatic solution might be to use skip lists.

Are you sure the exam required students to implement their solution?  In my experience, exams in the algorithms and data structure courses I'm familiar with rarely require implementing the solution -- it is enough to describe the solution clearly.  A solution based on augmenting an AVL tree can be described in a fairly simple way: you say "take a AVL tree, and modify it in such-and-such a way", and that doesn't require re-describing all the details of how AVL trees work.  Only you know what the typical expectations are for the kind of exam you are looking at.


Redistributing a set of uniformly distributed numbers to an arbitrarily defined shape Lets say I have a random number generator that spits out uniform numbers from 0 to 1

Next, I have a shape defined by a series of vertices, like { [0, 0.4], [0.5, 0.2], [1, 0.4] }

In those vertices, the first value determines the position and second the  distribution weight in that point (interpolated in between).

Now I need a magic function to redistribute the uniform random numbers into a distribution that would statistically match the shape of the vertices provided.

Essentially, if I were to run 10000 random numbers through the function, sort them into buckets like { [0 - 0.1], [0.1 - 0.2] ... } and count the buckets so that [x = x, y = count], it should produce a shape similar to if I were to use the original shape as [x, y].

To illustrate

ms paint at its finest.

Anyways, the question - I'm looking for an algorithm to build that magic function.

The shapes that I want to feed it would be based on real world statistics which often don't fit any of the neat looking distributions like gauss or normal, I've seen all kinds of wonky lines.

Here is a simple algorithm. Suppose that the shape is given by a sequence
$$ (x_0,y_0), \ldots, (x_n,y_n). $$
Define $A_i = (x_i - x_{i-1}) \cdot (y_{i-1} + y_i)$ for $1 \leq i \leq n$, and let $A = \sum_{i=1}^n A_i$, $\alpha_i = A_i/A$, and $\beta_i = \sum_{j=1}^i \alpha_i$.

  Sample a value $x$ uniformly on $[0,1]$, and determine $1 \leq i \leq n$ such that $\beta_{i-1} \leq x < \beta_i$. Let $c = (x-\beta_{i-1})/(\beta_i-\beta_{i-1})$.

Note that $c$ is uniform on $[0,1]$.

Here is what we have accomplished so far:

The probability of obtaining a specific $i$ is proportional to the probability that a random point generated according to the desired density lies between $x_{i-1}$ and $x_i$.

This is because the area below the density curve between $x_{i-1}$ and $x_i$ is $(x_i - x_{i-1}) \frac{y_{i-1}+y_i}{2}$.

Consider now the function
$$
\begin{align*}
\varphi_i(t) &= \int_{x_{i-1}}^t y_{i-1} + (y_i-y_{i-1}) \frac{t-x_{i-1}}{x_i-x_{i-1}}  \, dt \\ &=
y_{i-1} (t-x_{i-1}) + (y_i - y_{i-1})\frac{(t-x_{i-1})^2}{2(x_i-x_{i-1})}
\end{align*}
$$
and its normalized cousin
$$
F_i(t) = \frac{\varphi_i(t)}{\varphi_i(x_i)} =
\frac{2y_{i-1}}{y_{i-1}+y_i} \frac{t-x_{i-1}}{x_i-x_{i-1}} + \frac{y_i-y_{i-1}}{y_i+y_{i+1}} \left(\frac{t-x_{i-1}}{x_i-x_{i-1}}\right)^2,
$$
which is the CDF of your density function restricted to the interval $[x_{i-1},x_i]$.

  Output $F_i^{-1}(c)$.

Since $c \sim U(0,1)$, the resulting element has CDF $F_i$, and so has the correct distribution. It remains to explicitly invert $F_i$. Let $a = \frac{y_i-y_{i-1}}{y_i+y_{i-1}}$, $b = \frac{2y_{i-1}}{y_i+y_{i-1}}$, and $s = \frac{t-x_{i-1}}{x_i-x_{i-1}}$ (note that $0 \leq s \leq 1$). If $F(t) = c$ then $as^2 + bs = c$, and so we can calculate the output $t$ as
$$
s = \frac{-b + \sqrt{b^2+4ac}}{2a}, \qquad
t = x_{i-1} + (x_i - x_{i-1}) s.
$$
The formula for $s$ simplifies to
$$
s = \frac{\sqrt{(1-c) y_{i-1}^2 + c y_i^2} - y_{i-1}}{y_i-y_{i-1}}.
$$
We can thus rephrase the second step as

  Output
  $$ x_{i-1} + (x_i - x_{i-1}) \frac{\sqrt{(1-c) y_{i-1}^2 + c y_i^2} - y_{i-1}}{y_i-y_{i-1}}. $$

Another option for the second step is rejection sampling. Let $A$ be the area below the rectangle bounded by $(x_{i-1},0),(x_{i-1},y_{i-1}),(x_i,y_i),(x_i,0)$, and let $R$ be the upper bounding rectangle $(x_{i-1},0),(x_{i-1},y),(x_i,y),(x_i,0)$, where $y = \max(y_{i-1},y_i)$. Generate random points $(x,y)$ in $R$ repeatedly until one of them belongs to $A$, and output its ordinate $x$. Since the area of $A$ is at least half the area of $R$, on average this requires at most two samples.

In the first step you have to determine $i$ such that $\beta_{i-1} \leq x < \beta_i$. While a naive implementation would take time $O(n)$, or $O(\log n)$ using binary search trees, you can use the alias method to reduce sampling time to $O(1)$.


Does every DAG have at most one "universal source"? A "universal source" in a directed graph is a vertex v for which out-deg(v)=n-1 and in-deg(v)=0.
I know that any DAG has at least one source but can it have more than one for a universal?
I know there can be none, and there can be one (binary tree for example, root is universal source) but can there be two?

Suppose towards a contradiction that a DAG $G=(V,E)$ on $n$ vertices has more than one universal source and let $u,v \in V$ be two distinct universal sources of $G$.
Since $\mbox{out-deg}(u)=n-1$, and $G$ contains no self-loops, vertex $u$ has edges towards every other vertex in $G$. In particular $(u,v) \in E$. As a consequence $\mbox{in-deg}(v) \ge 1 > 0$ showing that $v$ cannot be a universal source.


Finding Hamiltonian cycles in polynomial space Question: If $H = \{(G,m)$ $|$ $G$ is a graph with $m$ distinct Hamiltonian cycles $\}$ ($m$ is in binary), prove that $H \in$ polynomial space.

My thoughts: I thought that I could show that $H \in NP$, by which it would automatically follow that $H \in$ polynomial space. By the witness theorem, the $m$ distinct Hamiltonian cycles (call them the set $C$) would serve as a witness. However, what is not apparent is if $|C| \leq |G|^k$. In fact, that is the entire problem, isn't it? What am I thinking about wrong over here?

Observe that a naive witness for $m$ cycles is a list of the cycles, which may be exponential (in case the value of $m$ is exponential in the size of $G$).

So perhaps you should work directly with PSPACE.

A possible approach is to order the vertices of $G$, and then try all sequences of $n$ (the number of vertices) vertices, in lexicographical order (one at a time, erasing the last one every time you proceed to the next, so as not to waste space), and for each sequence check whether it is a Hamiltonian cycle, and increment a counter if it is. If the counter passes $m$ then you have $m$ distinct cycles.

If by "distinct cycles" you mean that you do not count cyclic permutations, then after you complete the entire count, simply divide the number of cycles you found by $n$, giving you the number of cycles without cyclic permutations, and compare this number to $m$.


Is "duplicate" in RPN enough for replacing variable binding in term expressions? I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, $\mathsf{mul}$, $\mathsf{neg}$, and $\mathsf{inv}$. Here $\mathsf{add}$ and $\mathsf{mul}$ are binary operators, $\mathsf{inc}$, $\mathsf{neg}$, and $\mathsf{inv}$ are unary operators, and $0$ is a $0$-ary operator (i.e. a constant). Because I want to be able to also store numbers like $(3^3+3)^3$ efficiently, I need some form of variable binding. I will use the notation $(y:=t(x).f(y))$ to be interpreted as $f(t(x))$ in this question. Now I can store $(3^3+3)^3$ as
$$(c3:=(1+1+1).(x:=((c3*c3*c3)+c3).(x*x*x))).$$
If I stick to the operators $0$, $\mathsf{inc}$, $\mathsf{add}$, and $\mathsf{mul}$, this becomes
$$(c3:=\mathsf{inc}(\mathsf{inc}(\mathsf{inc}(0))).(x:=\mathsf{add}(\mathsf{mul}(\mathsf{mul}(c3,c3),c3),c3).\mathsf{mul}(\mathsf{mul}(x,x),x))).$$
Using RPN with a "duplicate" operation written $\mathsf{dup}$ instead of variable binding, this becomes
$$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{dup}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{mul}\ \mathsf{add}\ \mathsf{dup}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{mul}.$$

My question is whether it is always possible to replace variable binding by the "duplicate" operation. The binary operations ($\mathsf{add}$ and $\mathsf{mul}$) are associative and commutative, but it seems to me that even this is not enough for ensuring that variable binding can be completely eliminated. Take for example
$$(c2:=(1+1).(x:=(((c2+1)*c2)+1).(y:=(x*x).((y+c2)*y)))).$$
If I stick to the operators $0$, $\mathsf{inc}$, $\mathsf{add}$, and $\mathsf{mul}$, this becomes
$$(c2:=\mathsf{inc}(\mathsf{inc}(0)).(x:=\mathsf{inc}(\mathsf{mul}(\mathsf{inc}(c2),c2)).(y:=\mathsf{mul}(x,x).\mathsf{mul}(\mathsf{add}(y,c2),y)))).$$
Using RPN with a "store" operation written $\mathsf{sto}(x)$ instead of variable binding, this becomes
$$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{sto}(c2)\ c2\ \mathsf{inc}\ c2\ \mathsf{mul}\ \mathsf{inc}\ \mathsf{sto}(x)\ x\ x\ \mathsf{mul}\ \mathsf{sto}(y)\ y\ c2 \ \mathsf{add}\ y\ \mathsf{mul}.$$
After eliminating $\mathsf{sto}(x)$ and $\mathsf{sto}(y)$ by $\mathsf{dup}$, this becomes
$$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{sto}(c2)\ c2\ \mathsf{inc}\ c2\ \mathsf{mul}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{dup}\ c2 \ \mathsf{add}\ \mathsf{mul}.$$
Using explicit substitution to eliminate $\mathsf{sto}(c2)$, this becomes
$$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{inc}\ \mathsf{mul}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{dup}\ 0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{add}\ \mathsf{mul}.$$
My issue with explicit substitution is that it might lead to an exponential increase in the size of the expression. It's easy to see that expressions like $(3^3+3)^3$ or $((3^3+3)^3+3)^3$ can't be stored efficiently without something like $\mathsf{sto}(x)$ or $\mathsf{dup}$. Is there another way to eliminate $\mathsf{sto}(x)$, like an additional first-in, first-out queue? Or can one prove that an exponential blowup of the expression won't happen, if only explicit substitution and $\mathsf{dup}$ are "suitably" used together?

Is “duplicate” in RPN enough for replacing variable binding in term expressions?

No, it is not strong enough. One can eliminate $\mathsf{dup}$ by replacing each sequence of $\mathsf{dup}$ by a sequence of $x$ preceded by one $\mathsf{sto}(x)$ operation. Since the single variable "$x$" is enough to eliminate all $\mathsf{dup}$ operations, any term expression which requires more than one variable to be stored efficiently can't be expressed (efficiently) using only $\mathsf{dup}$.

If the $\mathsf{inv}$ operation is omitted, then this whole intended representation by a term expression can be seen as a special case of the directed acyclic graph representation of a polynomial used in arithmetic circuit complexity. So the RPN stack from the question turns out to be just a representation of a tree. Now a directed acyclic graph can't be "emulated easily" by a tree, and especially a non-planar DAG will be "too difficult" for the $\mathsf{dup}$ operation.

In order to add the $\mathsf{inv}$ operation again, note that the ring of polynomials in $x_1,\dots x_n$ over $\mathbb Z$ is just the free commutative ring with generators $x_1,\dots x_n$. The corresponding free algebra with an $\mathsf{inv}$ operation would be the free commutative regular ring with generators $x_1,\dots x_n$. To be faithful to the canonical representation of the free algebra of a variety (equationally defined collection of algebras), the $\mathsf{inc}$ operation should be replaced by $1$.


Converting a greedy algorithm to a dynamic programming algorithm Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be:

First, find a maximum indpendent set of vertices in the graph, and give it one color.

Next remove the set of vertices found in the previous case from the graph, and repeat the same process till I reach the empty set.

Now, I agree that it is hard to find the maximum independent set of an arbitrary graph. But, is there a way where this greedy sort of simple algorithm could be converted to a dynamic programming type algorithm? Say, may be we could decompose the graph into two simpler graphs and find maximal independent sets in each of the subgraphs, and then try to club the two individual independent sets to form a larger independent set by checking for adjacency. Is such a kind of 'conversion' from greedy to dynamic programming or vice-versa always possible? Can this change the complexity of the problem radically? Thanks beforehand.

The example you specified is not turning a greedy algorithm to a dynamic programming solution. You reduced a problem to another using a greedy argument and solved the other problem using dynamic programming. That is why it is still not clear to me what do you mean by converting greedy to dynamic programming. However, that being said I have three points to comment on this area, you might find the answer you are looking for among which.

The first one, which is not an answer, but an important notice, is that even though you suggested a (dynamic programming) solution of independent sets, this dynamic program has to consider all partitions of the vertices to find an optimal set. There is probably no dynamic programming solution to this problem that runs in polynomial time, since this will mean that P=NP due to the fact that the maximum independent set problem is NP-complete. However, even though we expect the running time to be exponential, you can solve the problem using only polynomial memory using for example the inclusion exclusion principle (refer to Parameterized algorithms book by Cygan et. al.).

Now back to your question, dynamic programming is usually used to solve generalized versions of greedy problems. For example maximum independent set, maximum matching and minimum dominating set can be found in linear time on trees using greedy algorithms. Greedy algorithms fail however, if the tree is weighted and we are looking for the structure optimizing the total weight. However, these problems can easily be solved in a bottom up dynamic programming manner in linear time, where the dynamic programming states are the subtrees of the given tree.

The third and probably the more interesting part, many problems (even some NP-hard ones) in general graphs admit a dynamic programming solution on the tree decomposition of the given graph. The optimal solutions still  have exponential dependence on the tree width. However, they have only polynomial/linear dependence on the size of the input. Usually these problems admit greedy/dynamic programming algorithms on trees, since these algorithms use the fact that a tree decomposition decomposes the graph into small separators, which is trivial in trees. (Again refer to Parameterized Algorithms book by Cygan et. al.)


What does the language {a, b, c}* exactly mean? How will the automaton for this look like? What does the language {a, b, c}* exactly mean?

Any finite words composed of the characters $a,b$ & $c$ and the empty word are part of the language $\{a,b,c\}^*$. The automaton has one state which is the starting and ending state. That state has 3 recursive edges which are reading $a$,$b$ and $c$.


K Nearest Neighbor using K-D Tree (What ratio makes K-D beneficial)? I'm trying to implement a KNearestNeighbor model and came across the fact that many professional models use a K-D tree to index the K Nearest Neigbors. I also read that high-dimensional data makes a K-D tree less useful because you don't eliminate as many vectors for every branch in the tree when traversing it. All of that makes sense, but my question is at what ratio is there any benefit made of using a K-D tree?
For instance, I have a training set of shape (50000, 3072) but I am feeding only 10000 points to the model so the shape the model gets is (10000, 3072)... anyways, I assume these are the only two numbers which are relevant for the model to determine if a K-D would benefit it's runtime.
So in my fit method, I am making an if statement to either make a K-D model or not to make a K-D model for indexing, but I'm not sure what the condition should be. Given
n_data, n_dim = x.shape

I imagine the condition could be
if n_data / n_dim >= 1:
    pass

This is where my knowledge stops. I would be grateful if someone could propose a condition, and educate me about what makes a good condition.

There's no way to tell for sure without trying out.  That said, a crude rule of thumb is that k-d trees tend to be useful when the number of dimensions is up to about 10-20, but in higher dimensions, often they are little better than a naive linear search over all points.
See also Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?, How can I make k nearest neighbor queries fast on unit hypersphere?, https://en.wikipedia.org/wiki/K-d_tree#Degradation_in_performance_with_high-dimensional_data


Smallest number with in a larger number with a certain length I have a number with $n$ digits. I want to keep only $m$ digits out of it. What is the smallest possible $m$ digit number which can be generated from the larger number so that order of digits is retained.

Ex: 3422509739

I need the smallest 3 digit number by removing 7 digits with order retained which will be 039.

This problem is very similar to subsequence problem that is solved using dynamic programming. So, there are several ways to solve this problem, but the algorithm that you choose really depends on the input size ($n$, $m$ and base of numbers).

I here explain the simplest algorithm. I assume that the number is given in base 10, which means that your digits are all between 0 and 9. You just need to iterate over the smallest digits first and construct the smallest possible subnumber from the digits after that.

Algorithm SmallestSubNumber(number[1:n], m)
Smallest = \inf;
For i=0:9
   For j=1:n-m
      If (number[j] == i):
          Smallest = min(Smallest, i*10^(m-1) + SmallestSubNumber(number[j+1:n], m-1));
   If (Smallest != \inf) return Smallest;


Checking if a given flow is a maximum flow I'm curious as to if there's any way to check (without having to run a 'whole' maximum-flow-algorithm) whether a given flow $f_e$ is the maximum flow of the flow graph $G$ in $O(|E|)$ time complexity.

I've thought about running one iteration of Ford-Fulkerson to see if there is an augmenting path from the source $s$ to the sink $t$, but couldn't such a solution get a time complexity worse than $O(|E|)$ in the worst case?

A flow is maximum if there is no $s$-$t$ path in the residual network. You can check this in time $O(|E|)$.


What did Turing's mysterious small programme on the Manchester computer calculate? I am reading Turing's "Computing machinery and intelligence" paper (https://www.csee.umbc.edu/courses/471/papers/turing.pdf) and found a fragment in which he says:

  I have set up on the Manchester computer a small programme using only 1,000 units of storage, whereby the machine supplied with one sixteen-figure number replies with another within two seconds. I would defy anyone to learn from these replies sufficient about the programme to be able to predict any replies
  to untried values.

It looks like a machine learning problem to me :) but putting my interest on AI aside, my question is the following:

Does anyone know what this program was doing?

I am very curious.

PS: By the length of the input and output, I suspect it was an encryption algorithm, but I would appreciate any clue to the actual program.

You're right that this has to do with encryption, but it's not encryption per se. It's something called hashing. What his program does is take a number, hash it, and output the hash. What Turing created is now called a cryptographically secure hash.

A modern cryptographically secure hash must do the following. It should be easy to hash the input, but very difficult to 'unhash' an output to get the input. In this case, "very difficult" usually means "it would take months or years on a supercomputer, if not even longer."


Proof by induction over rules for mutually recursive relations Consider the (big-step) semantics of a language ($a, e$ terms, $v$ values), defined by two mutually recursive relations, $\downarrow$ and $\Downarrow$, given by a set of rule-schemata (simplified):

$\frac{a \cdot x \Downarrow e ~~ e \downarrow v}{a \cdot x \downarrow v}{\tiny PROJECT} ~~~~~~~ \frac{a \downarrow \{ \ldots x = e \ldots \}}{a \cdot x \Downarrow e}{\tiny{FLAT}}$

If I want to prove something about this semantics, I would naturally use induction over rules or judgements. However, when I arrive at rule
PROJECT, I would have to make an assertion about $\Downarrow$. And to do so, I would have to return to $\downarrow$.

Is it legit to just merge the proofs for both relations and assume the induction hypothesis for $\Downarrow$ when dealing with $\downarrow$?
Is there some clean way to not merge the proofs but deal with them separately (something similar to break the recursion of functions)?

Yes, it's legit; no, you'll, (usually) have to "merge" the proofs.

You are trying to prove some property of an inductively defined set. You can do so using (structural) induction along the inductive order induced by your definition.

In a nutshell, you'll assume the property for all terms up to "size" (t.b.d.) $n$ (which has to apply to all rule premises) and conclude the property for terms up to size $n+1$ (the conclusions).

In your case, coming up with a good measure of size may be the hardest part, since $a⋅x⇓e$ and $a⋅x↓v$ are of the same "size" if you count operators. What size measure will work is impossible to say without seeing the whole calculus, though. Of course, for structural induction you don't strictly need such a measure; you can just follow the inductive order (see here for examples). As long as your semantics is well-defined, that should work.


Reference request for coding Knight's Tour Could someone give an easily accessible reference containing an algorithm that could be conveniently implemented into a code for computing Knight's Tour (preferably also with fairly
good efficiency)?

The idea is that we have a board of size $n \times n$, where $n$ is say 8 for your usual chessboard. We start from one of the corners (typically), and place a knight chess piece to this corner cell. The question is, can we move the knight through the board such that we visit each cell exactly once?

In graph theoretic terms, this is the Hamiltonian path problem, which in general is NP-complete. The Warnsdorff's rule you describe in the comments is a way to solve the problem pretty efficiently in practice. More generally, the Warnsdorff's rule is a fail first heuristic. This means that by running into dead-ends quickly, we prune the search tree aggressively, and thus succeed quickly.

For a programming exercise (and for the easiness of presentation), it is convenient to represent the graph as an implicit graph: you will have no explicit graph stored, but instead you can just store the coordinates visited, and compute the edges "on the fly".

At every step, your knight is in position $v$ on the board. The set of possible next moves is given by the successor function ("what unvisited cells I can move to from my position $v$?"), let us denote the possible next cells by $N(v)$.
When considering what cell $u \in N(v)$ to pick, we look at the degree of the vertices in $N(v)$. In this case, the degree of a vertex $u \in N(v)$ is given by the number of possible moves the knight can take from $u$.
Let $N^\delta(v)$ denote the set of neighbors of a vertex $v$ with the smallest degree. Our goal is to choose the vertex with the smallest degree; this is really easy if there is only one choice, i.e. if $|N^\delta(v)| = 1$. If this is not the case, we can employ some tie breaking strategy.
A simple and a pretty effective tie breaking strategy is to pick the next vertex $u \in N^\delta(v)$ uniformly at random -- this is simple to implement as well.

For a programming exercise, I definitely recommend using implicit graphs, and also not fixing the chess piece as a knight. Instead, build say an array of moves your piece can take -- it's pretty fun to try to see how the set of possible moves affect path finding. It's also fun to experiment with vertex choosing heuristics other than Warndorff's, and similarly with tie-breaking strategies.


Joining tables with minimum number of joins I am working on a generalized problem where I am given only schema definition of multiple tables that i have.

Now i have to retrieve certain columns by joining multiple tables such that number of joins are minimized.(i will consider where condition in sql clause later)

Example: Suppose i have 3 tables and here is the list of columns that they have.

Table 1:(1,2,3,4,5), Table 2:(5,6,7), Table 3:(5,6,7,8)

Now suppose I have a query in which i want all the columns 1,2,3,4,5,6,7,8.

Now i can join either table 1,table 2 and table 3 OR table 1 and table 3.I would get the required information in both the cases but joining table 1 and table 3 would require only 1 join rather than 2 join in other case.

What i was trying was a greedy algorithm in which first i would consider table that has maximum number of required columns then eliminate the common columns between the query and table(from both query and table) and then consider updated required columns and update tables and so on.But i guess it would be slow.

So is there a generalized algorithm or if anyone can give me any hint in this direction?

I believe that your problem is NP-complete.

Showing that it's in NP is easy. To show that it's NP-hard, take any instance of the set cover problem. Add a new unique element to the universe, and add it to each set. Interpreting each set as a table, a solution to the minimum join problem is a solution to the original set cover problem.


Reason programming language B was named "B"? I’ve searched around for this already but ironically the results have been overshadowed by “Why C was named C” instead.

If C was named “C” because it came after B, why was B named "B", since the only languages preceding B were FORTRAN and Plankalkül?

Is it possible naming B - “B” was a play on “Assembly” abbreviated - “A” since B is higher level than Assembly and follows this same construct?

B was designed by Dennis Ritchie and Ken Thompson, as a cut-down version of BCPL, the Basic Combined Programming Language. Ritchie [1] says,

  [B's] name most probably represents a contraction of BCPL, though an alternate theory holds that it derives from Bon, an unrelated language created by Thompson during the Multics days. Bon in turn was named either after his wife Bonnie, or (according to an encyclopedia quotation in its manual), after a religion whose rituals involve the murmuring of magic formulas.

[1]  Dennis Ritchie, The development of the C language. ACM SIGPLAN Notices. 28 (3): 201–208, 1993.


Subset sum into a consecutive range vs. standard subset sum The following problems live in integer domain.

I want to find a subset of $\{x_0, x_1, \ldots, x_{n-1}\}$ such that the subset's elements sum to any number in a prescribed interval $[X,X+k]$, $k\geq 1$.

We call the above problem A.

An obvious approach is to solve $k+1$ standard subset sum problems with targets $X, X+1,\ldots,X+k$ . I would be satisfied once my algorithm finds a solution to any of these problems.

Now I am wondering, does there exist a single standard subset problem B: $\{y_0,y_1,\ldots,y_{m-1};Y\}$ where $Y$ is the target, such that if I solved B, I equivalently solved A, additionally, the conversion from B's solution to A's solution is fast, preferably in linear time.

To make it simpler, I am only considering $k=1$.

Thank you!

This answer assumes that a Yes instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$ is one in which there is a subset summing to either $X$ or $X+1$.

Given an instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$, construct an instance of subset sum with elements $x_0,\ldots,x_{n-1},1$ and target $X+1$. You take it from here.


Pseudocode for a searching tree I want to describe my search tree in an algorithm and describe how each level of the tree is created. But I cannot find good examples to help me express how to write it in an elegant way. Please if anyone can recommend a good resource for describing a search tree in detail in a pseudo code.

Probably the best way to explain how such an algorithm works is via diagrams showing it step by step for some examples, examples selected to exercise your code more or less fully (need not cover all left/right symmetric cases, for example).

If you use LaTeX, look for a package to typeset algorithms, like algorithm2e, and check out TikZ and it's facilities to draw trees. It's documentation is quite forbidding, search for tutorials or targeted explanations.

Place yourself in the shoes of your gentle reader: What would you like to see? What points of the algorithm are thorny? Any corner cases that need explaining? Any strange/surprising/seemingly useless lines?


Why is data fragmentation not possible on main memory (RAM)? I am wondering why data fragmentation is a problem on main memory.

On a software level, virtual addresses are used anyway. So why can one address space not be split up into multiple segments, like a hard disk might do? I don't see how the performance would be affected, as the time needed to access memory addresses does not vary. Is this just a limit of the MMU?

In other words, my question is why does a process need continuous memory segments? For example:

Process D requests a memory block that could fit into the two free segments, if the block were split into two pieces. Why can't this be done?

It would be great if you could add a source so I could read more about this topic, if you have one.

According to https://lwn.net/Articles/211505/, what you imagine should be done by the OS, is already done:

  Since Linux is a virtual memory system, fragmentation normally is not a problem; physically scattered memory can be made virtually contiguous by way of the page tables.

There are limits to this, as hardware devices may request contiguous hardware memory, and this creates memory holes (at least for hardware devices).

Another limitation is that doing all memory allocations and deallocations through page tables is inefficient. Setting up new page table entries takes longer than managing allocations through software and, if the page size is 4K, only works for allocations that are a multiple of 4K. Therefore the malloc and free glibc calls first allocate 4K blocks through mmap (using page tables) and manage this memory. They divide it into smaller contiguous memory areas and return them when a malloc call requests a small chunk of memory. Algorithms to reduce memory fragmentation of software-managed memory are for example the Buddy memory allocator.


does every CFL have an ambiguous CFG? some questions have been popping up recently on ambiguity in CFLs/CFGs which can have subtleties (eg languages vs grammars & ambiguity vs inherent ambiguity). wikipedia states:

  Many [context free?] languages admit both ambiguous and unambiguous grammars, while some languages admit only ambiguous grammars.

the sentence is phrased in wikipedia without the "CFL" inserted but am now wondering what effect it has on the logic. after pondering the technical defn of ambiguity (on wikipedia pg) & thinking about it a bit my question:

  does every CFL have an ambiguous CFG? if not what is a counterexample ie a CFL that does not have (any) ambiguous CFG?

(the question arose in that every CFL has multiple CFGs, ie a CFG is only unique to a CFL under additional restrictions, and it seems that given any (unambiguous) CFG one could add small chgs/productions rules to get an equivalent ambiguous CFG...? is this trivial? but rarely pointed out anywhere?)

somewhat related question somewhat involved in sparking this one: Are there inherently ambiguous and deterministic context-free languages?

Every nonempty context-free language has an ambiguous grammar. Consider any context-free grammar for the language with starting symbol $S$. We add new non-terminals $S',A',B'$, make $S'$ the new starting symbol, and add the following rules:
$$
\begin{align*}
&S' \to A' \\
&S' \to B' \\
&A' \to S \\
&B' \to S
\end{align*}
$$


Prove correctness of recursive multiplication algorithm I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together:

function multiply($n, $r) {
    if($n == 1)
 return $r;
    else if($r == 1)
 return $n;
    else
        return $r + multiply($n - 1, $r);
}

How do I prove my algorithm is correct?

A quick google search tells me I have to prove that it works for $n + 1$ and I have to prove that it terminates. Unfortunately I'm still incredibly new to this and haven't the faintest clue as to where to start for proving my algorithm correct, so I would really appreciate some help here. I think maybe I have to do some sort of proof by induction but as this is an algorithm, I wouldn't know where to start.

You need to do a proof by induction on $n + r$. Let $P(m)$ be the statement "for any $n,r \geq 1$ satisfying $n+r = m$, $\mathrm{multiply}(n,r) = nr$. The proof by induction goes along the following lines.

Base case: $m=2$, so $n=r=1$. By inspection, $\mathrm{multiply}(1,1)=1$.

Induction step: suppose $P(m)$ is true for some $m \geq 2$, and let $n,r\geq 1$ satisfy $n+r = m+1$. If $n=1$ or $r=1$ then $\mathrm{multiply}(n,r)=nr$ by inspection. Otherwise, by $P(m)$, $\mathrm{multiply}(n-1,r)=(n-1)r$ (since $n-1+r = m$), so $\mathrm{multiply}(n,r) = r+\mathrm{multiply}(n-1,r) = r+(n-1)r = nr$.

By the principle of mathematical induction, $P(m)$ is true for all $m$, and so for any $n,r\geq 1$, $\mathrm{multiply}(n,r)=nr$.


Why is discrete mathematics required for data structures? Data Structures is the second CS course taught at Columbia University and it lists Discrete Mathematics as a Co-Req.

I have a BSEE and have not taken any discrete mathematics and am having a hard time understanding why I need to take this to do things like create data structures?

Is this just so the university can cram useless info in my head and make more money, or is there a real relation to discrete math and data structures?

A course on data structures will not be about "creating data structures". You can expect to analyse data structures, prove various properties of them, and create your own to solve some highly nontrivial problems.

Every single data structure you intend to build must be rigorously defined. Each method on a data structure must be proven rigorously to be correct. The time and space complexity of each method must be rigorously proven to follow a particular asymptotic bound. This all involves some nontrivial discrete mathematics. You'd also need to have a solid handle on probability when randomized inputs and data structures start being used, which you should expect for a decent course on data structures. If you're still unconvinced, look up Cuckoo Hashing and show that the insert time is, on average, $O(1)$, or take a look at a van Emde Boes tree and just attempt to figure out how the hell it works in the first place. You'll quickly realise that there's far more to it than just writing code to build obvious structures.

However, if you go into this course believing it to be beneath you, I can guarantee that you'll get nothing out of it. I would be very surprised indeed if an Ivy League university is "trying to cram useless info into your head and make more money".


Examples of random deployment in wireless sensors networks I have been doing some research and have found a lot of papers on the subject of random deployment in wireless sensor networks, but I haven't found a single example of its usage. Has it been used before? What could be a very concrete context in which it could be used?
Thanks in advance.

One scenario that I've heard discussed is the idea that an airplane flies over a remote area and drops wireless sensors.  They fall somewhat randomly, and then need to establish a network amongst themselves.


Class P is closed under concatenation Proving that Class P is closed under concatenation.

The answer is given below:

But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?

With $n = |w|$ the length of $w$, step 2 is repeated exactly $n+1$ times.

But they assume implicitly that $n$ is the length of the input (which is canonical in complexity theory), i.e. $|\langle w \rangle|$ with an unspecified encoding $\langle.\rangle$ of strings.
(Why they insist to introduce that encoding here, I don't know.)

The $O$ (which should be a $\Theta$) comes from that encoding as well. While there are exactly $|w| + 1$ ways to cut $w$ in two parts, we don't know the exact figure in terms of $|\langle w \rangle|$.

They forget to mention their assumption that that encoding is reasonable in a certain way, i.e. $|\langle w \rangle| \in \Theta(|w|)$ for all $w$.


Algorithm for computing partitions of a set of n elements into subsets of size m I need an algorithm that can compute all the different partitions of a set of n elements into subsets of size m.

For example for $n=4$ for the set $\{a,b,c,d\}$ and $m=2$ the output should be

$\{\{\{a,b\},\{c,d\}\},\{\{a,c\},\{b,d\}\},\{\{b,c\},\{a,d\}\}\}$

Two possible  possible solutions.

Given a set $S$ of size $n$ and a positive integer $m < n$. First generate all $m$-size subsets of $S$, for example, in lexicographic order and store them. Let $C$ be the set of all $m$-size subsets of $S$. The size of $C$ is $\binom{n}{m}$. The following algorithm generates all partitions

Generate(S, Partition)
  if S is empty
    print Partition
    return

  for each T in C such as T is a subset of S
    add T to Partition
    Generate(S-T, Partition)
    remove T from Partition
end

This algorithm repeats partitions but you can check if a Partition repeats. If it does then do not print it. One possible solution is checking its lexicographic order.

The second approach, which I think is simpler, is to systematically generate all $(n/m)$-size subsets of $C$. If for some $(n/m)$-size subset $T$ all sets in $T$ are mutually exclusive, then $T$ is a partition and so print it.

Example: $S=\{a,b,c,d\}$ and so $C = \{\{a,b\},\{a,c\}, \{a,d\}, \{b,c\}, \{b,d\}, \{c,d\}\}$. Then using the second approach we systematically generate all $4/2=2$-size subsets of $C$. Thus while generating if we have $\{\{a,b\},\{a,d\}\}$ then we just skip it since it's not a partition. But if we have $\{\{a,b\},\{c,d\}\}$ then we print it since it is a partition. Furthermore, there is no chance of generating duplicate of a subset of $C$ since we generate all (distinct!) combinations of $4/2=2$ elements from $\binom{4}{2}=6$.

For generating combinations of $k$ elements from $n$ you could look, for example, here.


Proof of uniform convergence if VC dimension is finite In the book »Understanding Machine Learning: From Theory to Algorithms«, written by Ben-David and Shalev-Shwartz, there is a proof which I do not understand. The context is proving that if a hypothesis class $\mathcal{H}$ has finite VC dimension, then it enjoys the uniform convergence property.

The proof of this implication involves Sauer's Lemma (hypothesis classes with finite VC dimension have »small effective size«) and a theorem stating that hypothesis classes with »small effective size« enjoy the uniform convergence property. The proof of the latter sub-implication involves this theorem (Theorem 6.11 in the book):

  Let $\mathcal{H}$ be a hypethesis class of binary classifiers over a domain $\mathcal{X}$ and let $\tau_{\mathcal{H}}$ be its growth function (from Sauer's Lemma). Then, for all $m \in \mathbb{N}$, for every distribution $\mathcal{D}$ over $\mathcal{X} \times \{0, 1\}$ and every $\delta \in (0, 1)$:
  $$
\forall h \in \mathcal{H}: \mathbb{P}_{S \sim \mathcal{D}^m}\left[ | L_{\mathcal{D}}(h) - L_S(h) | \leq \frac{4 + \sqrt{\log(\tau_{\mathcal{H}}(2m))}}{\delta\sqrt{2m}} \right] \geq 1 - \delta
$$

In the proof for this theorem it is stated, that it follows immediately from the inequality
$$
\mathbb{E}_{S \sim \mathcal{D}^m}\left[ \sup_{h \in \mathcal{H}} | L_{\mathcal{D}}(h) - L_S(h) | \right] \leq \frac{4 + \sqrt{\log(\tau_{\mathcal{H}}(2m))}}{\sqrt{2m}},
$$
the fact that the random variable $\theta := \sup_{h \in \mathcal{H}} | L_{\mathcal{D}}(h) - L_S(h) |$ is nonnegative and Markov's inequality.

However, I do not see how it follows immediately from those facts. What am I missing?

Let $X = |L_\mathcal{D}(h) - L_S(h)|$. The statement on the expectation of the supremum of $X$ implies, in particular, that for some $M$,
$$
\mathbb{E}[X] \leq M.
$$
Since $X \geq 0$, Markov's inequality implies that
$$
\Pr\left[X \geq \frac{M}{\delta}\right] \leq \delta.
$$
This implies that
$$
\Pr\left[X \leq \frac{M}{\delta}\right] \geq
\Pr\left[X < \frac{M}{\delta}\right] =
1 - \Pr\left[X \geq \frac{M}{\delta}\right] \geq 1 - \delta.
$$


Time Complexity to find height of a BST Below is a question I was asked in an Interview
What is the best case time complexity to find the height of a Binary Search Tree?
I answered it explaining using the below algorithm

$\mathrm{height}(v)$
if $v$ is a leaf, return 0
otherwise, return $\max(\mathrm{height}(v.\mathit{left}), \mathrm{height}(v.\mathit{right})) + 1$

So, in best case, my recurrence would become
$$T(n)=2T\left(\frac{n}{2}\right) + c.$$
Here $T(\frac{n}{2})$ is for each of the recursive calls, and $c$ for all the rest. So even best case complexity is $O(n)$.
Now, in the worst case, my recurrence would become
$$T(n)=T(n-1)+c,$$
and this would be a case of a skewed BST.
Still, here complexity remains $O(n)$.
So, in all cases, the time complexity to find the height of a BST remains $O(n)$.
Is my claim correct?

Your algorithm runs in linear time on all inputs. The algorithm visits each node of the tree exactly once, and does $O(1)$ work per node. Therefore it runs in time $\Theta(n)$, where $n$ is the number of nodes.

The argument above is better than using recurrences, since it is more immediate. It also shows that if you had an arbitrary tree (not necessarily binary), the algorithm would still run in linear time.


Binary exponentiation of matrix - complexity I want to calculate complexity for binary exponentiation of matrix of size $k$. Let's say that I'm using the simplest approach to multiply matrices (so with three for loops). The complexity of this operation would be $O(n^3)$. Now, the powering of matrix. Pseudo code (n is the power, A matrix):
power(n, A)
 if n == 0
  return 1
 else
   res = power(n/2, A)
   if n%2 == 0
     return res * res
   else
     return res * res * A

If I write the equation:
$$T(n)=T(n/2) + O(k^3)$$
where $T(n)$ is the complexity, is it correct to think of cost to be $O(k^3)$?
Then we sum
$$\sum_{i=0}^{\log_2n}O(k^3) = O(k^3\log_2n)$$
and for us $k=27$ is constant.
Hence $T(n)=O(\log_2n)$

The solution of the recurrence
$$
T(n) = T(\lfloor n/2 \rfloor) + O(1)
$$
(this is the correct form of your recurrence) is $T(n) = O(\log n)$. If you want to be more accurate, the solution of the recurrence
$$
T(n) = T(\lfloor n/2 \rfloor) + C
$$
is (for $n \geq 1$)
$$
T(n) = C\lfloor \log_2 n \rfloor + T(1).
$$
In your case $C$ is not really constant, but rather depends on the parity of $n$. Accordingly, we can consider the recurrence
$$
T(n) = T(\lfloor n/2 \rfloor) + C_{n \bmod 2},
$$
whose solution is
$$
T(n) = C_1 \#_1(\mathrm{bin}(n)) + C_0 \#_0(\mathrm{bin}(n)) + T(0);
$$
here $\mathrm{bin}(n)$ is the binary representation of $n$, and $\#_0,\#_1$ is the number of $0$-s and $1$-s, respectively.


Understanding the definition of SPMD From Wikipedia

  SPMD (single program, multiple data) is a technique employed to achieve parallelism; it is a subcategory of MIMD. Tasks are split up and run simultaneously on multiple processors with different input in order to obtain results faster.

Does a program running on SPMD runs as either multiple processes or a process
with multiple threads? If former, are the multiple processes runs the same program?
Wikipedia tries to compare SPMD with SIMD:

  In SPMD, multiple autonomous processors simultaneously execute the same program at independent points, rather than in the
  lockstep that SIMD imposes on different data. With SPMD, tasks can
  be executed on general purpose CPUs; SIMD requires vector processors
  to manipulate data streams. Note that the two are not mutually
  exclusive.

What does "at independent points" mean? Does point means time? If
yes, isn't "at independent points" contradict "simultaneously"?
Wikipedia also compares SPMD with SMP:

  Unlike SPMD, shared memory multiprocessing, also called symmetric multiprocessing or SMP, presents the programmer with a
  common memory space and the possibility to parallelize execution by
  having the program take different paths on different processors. The program starts executing on one processor and the execution
  splits in a parallel region, which is started when parallel
  directives are encountered. In a parallel region, the processors
  execute a single program on different data.  A typical example is
  the parallel DO loop, where different processors work on separate
  parts of the arrays involved in the loop. At the end of the loop,
  execution is synchronized, only one processor continues, and the
  others wait. The current standard interface for shared memory
  multiprocessing is OpenMP. It is usually implemented by
  lightweight processes, called threads.

From Section 6.3 of Computer Organization and Design, Fifth
Edition: The Hardware/Software interface by David A. Patterson, John
L. Hennessy:

  programmers normally write a single program that runs on all processors of an MIMD computer, relying on conditional statements
  when different processors should execute different sections of
  code. This style is called Single Program Multiple Data (SPMD),
  but it is just the normal way to program a MIMD computer.

I don't quite understand how SPMD and SMP are different as stated in
Wikipedia, and maybe some paraphrasing may help? In particular,
Wikipedia says in SMP, a program can take different paths on
different processors. In Patterson's book, in SPMD, a program can
also run different sections of code on different processors.

Wikipedia says "The current standard interface for shared memory
multiprocessing is OpenMP".  Is multithreading by OpenMP or PThread
on multiple processors SPMD or SMP?

Thanks.

You are taking these definitions too literally (as if they were mathematical definitions that could be used in a proof.)  These terms all come from the "heroic" age of computer architecture when people were designing by the "seat of their pants" and kind of just getting a feel for what works and what doesn't.  Treat them more like terms for writing poetry than mathematics.

a. SPMD might refer to either multiple threads sharing an address space or multiple processes with independent address spaces sharing only through message passing or through the file system.
b. Typically with SPMD in an environment with separate processes each process would be loaded from the same executable file.

Each thread (or process) in a SPMD machine has its own instruction pointer (indicating what instruction should be executed next).  Each thread in a SPMD program updates its instruction pointer independently.  So the threads in a SPMD program execute simultaneously, but they are executing different instructions and there is no required correlation between the instructions those threads are executing.
In a SIMD program there is only one instruction pointer.  On every time step every execution unit is executing the same instruction simultaneously.  (The term NVidia uses for SIMD execution unit is "core", the term most other people use is "vector lane.")

a. SMP is not part of Flynn's taxonomy.  Flynn's taxonomy is SISD, SIMD, MISD, MIMD.  That's it.  "SPMD" is something that someone made up after the fact but is the same thing as MIMD (as pointed out by the Hennessy and Patterson quote you include.)  "SMP" is part of a completely different poem.  It might be best to think of SMP as a particular way of implementing SPMD computers.  SMP typically stands for "Symmetric Multiprocessor" not "Symmetric Multiprocessing".
b. Multithreading by OpenMP or Pthreads on multiple processors is SPMD (because you are running multiple independent threads on the same program executable.)  You might use a SMP to execute your SPMD OpenMP or Pthreads program, or you might use some other implementation of SPMD.


Which language is produced by this grammar? I was asked to define the language which is produced by the following grammar:

$G = (V, \Sigma, S, P)$

$V = \{S, A, B\}$

$\Sigma = \{a, b, c\}$

\begin{equation}
    P=
    \begin{cases}
      S \rightarrow cA | bB\\
      A \rightarrow c \\
      B \rightarrow aB|b
    \end{cases}
  \end{equation}

Obviously, you can produce $c^n$ and $b^n$, but since we can also produce $ccbab$ for example, I do not know how to find a formular for the language $L(G)$

Any help would be really appreciated!

Let's start with the nonterminal $B$. Since all productions of the form $B \to \alpha$ involve only $B$ (and no other nonterminal), we can easily find $L(B) = a^*b$ using Arden's rule. We also have $L(A) = c$. Finally,
$$ L(S) = L(cA) \cup L(bB) = cc + ba^*b. $$


Implement Mathematica's capability of rationalizing machine reals If I have a variable x bound to a machine precision real in Mathematica, I can use

 y = FromDigits[RealDigits[x]]

then y is bound to a completely equivalent rational number which has infinite precision.

What are the basic principles behind FromDigits and RealDigits?
How could I implement a similar conversion using common machine operations (fixed-size integers and floating point operations) to coerce a double in a rational, or at least obtain the long integer denominator and numerator of a double?

The continued fraction algorithm is easy enough to implement. The first step is to compute the continued fraction of the input $x = [c_0;c_1,\ldots]$. You start with $x_0 = x$, and use the recurrence $c_i = \lfloor x_i \rfloor$, $x_{i+1} = 1/(x_i - c_i)$. You stop when $x_i - c_i$ is "small enough". The next step is to compute the convergent of the continued fraction. You can find the appropriate formulas on the web. In practice, both steps are performed at the same time.

There are some issues with numerical stability, and that might make it difficult to match the performance of Mathematica, but for simple cases it works well enough.

The resulting rational number is not actually equivalent to the floating point number - there's probably some small error. In fact, the rational approximation may be more accurate in some cases, and off the mark in others. However, floating point numbers are secretly rational numbers - they are of the form $\pm 2^x M$, where $x$ is the integer exponent (positive, zero or negative) and $M$, the mantissa, is a rational number between $0$ and $1$ (or $0$ and $2$). In fact, it's always of the form $A/2^B$, where $B$ is the length of the mantissa and $A$ is some non-negative integer. If you really care for it, you could decode a real number into this representation, and thus obtain a truly equivalent rational number.


NFA for right left multiplication Given the following multiplication table how could one construct an NFA such that it accepts all strings that have a certain product (say a) ?

The string "abcb" would be evaluated as (a(b(cb))) = a

\begin{array}{c|ccc}
    \times & a & b & c \\
    \hline
    a & a & a & c \\
    b & c & a & b \\
    c & b & c &a
   \end{array}

I tried to take the transpose of the above matrix:

\begin{array}{c|ccc}
    \times & a & b & c \\
    \hline
    a & a & c & b \\
    b & a & a & c \\
    c & c & b & a
   \end{array}

And build an NFA for that. I then reversed all the transitions, but I don't think that works.

Start by checking that you would be able to build such a NFA if the multiplication table was associative.  That would be a good starting point for you to work on.  (If it's associative, the problem becomes very easy.)  Once you've done that, the next step is:

Now to accommodate the fact that the multiplication table is in fact not associative, and that you want to group multiplications on the right first, you can use the ideas from Louis's comment.  That should make it pretty easy for you to work out an answer to your own exercise, by yourself.


Inheritance problem (JAVA) Here I have created 2 classes , $A$ is the super class of $B$ , i.e , $B$ inherits the features of class $A$.

Now I don't know exactly what statement (1) does but I am speculating as follows ,kindly correct me if I am wrong ,

An object of $B$ is created whose address has been assigned to the variable $ob$ of class $A$.

Now when statement (2) is called the $add$ function of the class $B$ is executed , but when statement (3) is executed it gives an error saying $e$ doesn't belong to $A$. Why is that ?

With my understanding , I thought statement (1) creates an object of class $B$ via its parent class $A$. Then why its object can't access its data member ? Can anyone explain ?

The variable $ob$ is an object reference variable of type $A$.  As such, it can only reference those attributes and methods defined in $A$.  The attribute $e$ is defined in $B$, not $A$, so $ob$ cannot reference $e$.  It is okay to reference $add$ because it is defined in $A$, even though it is overridden in $B$.


DFS vs. Union Find for computing connected components of a static graph According to CLRS,

  When the edges of the graph are static—not changing over time—we can
  compute the connected components faster by using depth-first search.

However, I tried to do some runtime analysis, and in a graph $G(V, E)$ on which we have to answer $Q$ connectivity queries.

DFS would take $O(V+E)$ asymptotic time to calculate the connected components, followed by $O(1)$ to answer each query, which leads to a total running time of $O(V+E+Q)$.

Whereas, an optimised Union Find would take $O(E.α(V))$ time to “add” all the edges, followed by $O(α(V))$ per query, which gives a total running time of $O(α(V).(E+Q))$.

Now, as we, know $α$ can be taken to be a constant factor for all practically conceivable applications, so Union Find works out to be faster,
hence I am confused as to why the authors of CLRS call DFS faster.

Am I making a mistake with my analysis somewhere?

When the graph is dynamic, union-find can update the list of connected components in time $O(\alpha(V))$ per vertex or edge, whereas it is not clear how to run DFS progressively. So we can complement the statement you quote by

  When the edges of the graph are dynamic – changing over time – DFS is not a good choice since it cannot be applied progressively; we can compute the connected components faster by using union-find.

That said, union-find is helpful only if edges and vertices are never deleted.


Same notation/terminology for union of sets and concatenation (Kleene star)? For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology and operator?

The following is my understanding of the union of sets versus the concatenation of sets (Kleene star). Please correct me if I'm wrong.

Union of sets

For the two sets $\{a,b\}$ and $\{a,b\}$ we have the union
\begin{align}
\{a,b\}\cup\{a,b\}=\{a,b\} \tag 1
\end{align}
Update: For reference I used Union (set theory) from Wikipedia.

Concatenation of sets (Kleene star)

The concatenation of $\{a,b\}$ and $\{a,b\}$ is also a union (same notation?!) of two sets
\begin{align}
\{a,b\}^*&=\bigcup _{i=0}^{2} \{a,b\} ^2 \tag 2\\
&=\{a,b\} \cup \{a,b\} \tag 3\\
&=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,\dots\} \tag 4
\end{align}

Update: For reference  I used Kleene star from Wikipedia. And here's where my confusion lies because at Wikipedia they also use the notation with the union operator:
$$
V^* = \bigcup_{i\geq 0} V^i = V^0\cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots \tag 4
$$
Which is the same (?!) notation as in my $(2) - (3)$ but with the upper bound $2$. And the notation does not coincide with $(1)$.

Wikipedia is using $\cup$ in its usual meaning, set union. When Wikipedia defines
$$
V^* = \bigcup_{n \geq 0} V^n = V^0 \cup V^1  \cup V^2 \cup \cdots,
$$
it literally means that $V^*$ is the union of the sets $V^0,V^1,V^2,\ldots$

The concatenation happens in the definition of $V^n$, which can be defined as follows: $V^0 = \{\epsilon\}$, and $V^{n+1} = \{ xy : x \in V^n, y \in V \}$. In words, $V^n$ is the concatenation of $n$ words from $V$.


Find shortest prefix to generate original string by overlapping Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed).

For example, if $S = atgatgatatgat$, I want to find $P = atgat$; $P$ is the smallest prefix of $S$ that can be concatenated (in this case three times, starting at indices $\{0,3,8\}$ of $S$, where the first and second copies overlap but the second and third copies do not overlap) to equal $S$.

Obviously, there is an $\mathcal{O}(n^2)$ algorithm by checking each prefix of $S$, but a colleague mentioned it might be possible to do it in $\mathcal{O}(n \log n)$. I'm thinking of using suffix arrays for different prefixes of $S$ but haven't quite been able to proceed from there.

What you are looking for is called the quasiperiod of a string. If such a string has a quasiperiod of $|S|$ it is called superprimitive, and can not be covered by a substring.

A method for computing it in $O(n)$ time is given in "An On-Line String Superprimitivity Test" by Dany Breslauer. You might also be interested in "Of Periods, Quasiperiods, Repetitions and Covers" by Alberto Apostolico and Dany Breslauer.


Why Instruction Decode and Register Read are in the same stage of MIPS pipeline Why are instruction decoding and register read are combined in single stage of a 5-stage MIPS-pipeline, even though they serve two different operation?

Instruction Decode and Register Read are done in parallel on that stage in order to prevent needing to wait on either to complete.  There's no reason not to do this since they are both known at that point in time for the MIPS-Pipeline, and since they will most likely be needed for the next step (Execution Cycle).

By "no reason", I mean that you would effectively be using more power while separating them (as mentioned in the comments below).  You would also be adding a whole extra stage in that case, as the stage before (Instruction Fetch) is what actually gets the information for ID and RR, and adding it to the stage after would not work because that stage requires both.  Thus the only way to do it would be to add the stage in-between the ID stage and EX stage, which would add a whole extra cycle to every operation, which would obviously result in slow downs overall.

If you're interested in reading more about this, I'd recommend this textbook I'm using for a class (Computer Architecture: A Quantitative Approach by John Hennessy and David Patterson).  It's got a pretty handy reference for MIPS especially from what I've read so far and it's where I pulled this information from.


Adapt a one-tape turing machine's algorithm that find the center of a string in O(nlog(n)) to find the first third I have found this answer that finds the center of an input string in nlog(n) complexity. I have tried to use it as a starting point to find an algorithm that finds the character(s) that separate the string in two parts (1/3 + 2/3) by changing some elements of the initial algorithm but I can't find the right modifications that really works on every example. Which adaptations can be made to the initial algorithm that will work for every length ?
I add the image for the machine that finds the center.
Example: for n=3k+1 and n=3k+2
XXXX -> XMXX

XXXXX -> XMMXX

Let's start with a new way of computing the center. First of all, it's not so clear what to do with a string of even length. Fortunately, it doesn't matter, since we can fix it once and for all: initially, we determine the parity of the length of the input, and then add one symbol at the beginning or end (according to the definition of center for strings of even length).
From now on, we assume that we are given a string of odd length. Here is the idea in a nutshell:
\begin{align}
&\verb|XXXXX| &\verb|XXXXXXX| \\
&\verb|X X X| &\verb| X X X |
\end{align}
In words, we erase part of the input so that the remaining string has the same center. How we do this exactly depends on whether the input has length $4n+1$ or $4n+3$.

Let's move on to your case. The $1/3-2/3$ midpoint is well-defined for strings of length $3m+1$. You can reduce to this case by adding one or two symbols to either end of the string as before, so let us assume that our string has length $3m+1$. We again consider two cases, according to the parity of $m$:
\begin{align}
&\verb|XXCXXXX| &\verb|XXXCXXXXXX| \\
&\verb|X C X X| &\verb| X C X X Y|
\end{align}
We have highlighted the center using the letter C.
If the string has length $6n+1$, then we simply cross of every other letter. If the string has length $6n+4$, then we cross of every other letter (starting from the second), and then remove the final letter (which we denoted by Y in the example).


Algorithm to determine minimum server required? So I came across a problem that has be completely stumped. You're given n servers to store a file on and you need to find the minimum number of servers you need to store the file on so that you can minimize the cost of the client and to the user.

When the user tries to look for a file he will start at some unknown server, check to see if the file is there and if it's not will move on to the next server and do the same. The cost is the minimum distance between the user and the server with the file.

To upload the file to the i'th server it would cost the client c_i

The exception is that you can upload it to the n'th server for a cost of 0 (meaning that the user will never have to loop around and the worst case won't be n)

So basically I need to find an algorithm that will find a subset that will give us a balance between the cost to the client and the cost to the user.

This answer assumes that what you're trying to minimize is
$$
 \sum_{i \in S} c_i + \sum_{i=1}^n d(i,S),
$$
where $c_i$ is the cost of the $i$th server and
$$d(i,S) = \min_{\substack{j \in S \\ j \geq i}} \; j-i$$
is the distance from $i$ to the closest server.

Use dynamic programming. For all $j \leq j_0$, compute the minimum of
$$
 \sum_{i \in S} c_i + \sum_{i=j}^n d(j,S)
$$
over all $S \subseteq \{j,\ldots,n\}$ such that $\min S = j_0$.


Is boolean validity a harder problem than satisfiability? I am aware that satisfiability is NP complete and unsatisfiability is co-NP complete. But somehow I feel that labeling satisfiability as NP-complete and unsatisfiability as co-NP complete is papering over the fact that unsatisfiability (or equivalently validity) is inherently a harder problem than satisfiability. Suppose I have a NDTM. Then given a potential model I can surely check it in polynomial time. However to check unsatisfiability I would need to check all possible assignments, surely this makes the problem EXPTIME?

However to check unsatisfiability I would need to check all possible assignments, surely this makes the problem EXPTIME?

Well, $EXPTIME$ but not necessarily $EXPTIME$-complete.

Congratulations, you've found the (possible) difference between $NP$ and $Co-NP$.

The first thing to realize is that there's a duality here. Satisfiability requires only a single example to prove a YES, but (as far as we know) needs to search a possibly exponential space for a NO. Unsat is the exact dual of this: you need to search a possibly exponential set to prove a YES, but a single counter-example will prove a NO. So neither is a harder problem, it's just that one is easy for YES, and the other is easy for NO.

The second thing to realize is that every NP-complete problem has a dual like this, and that's exactly why we study $Co-NP$ complete problems. For Hamiltonian Path, one path proves it, and a full search is needed to disprove. The converse is true to for NOHAMPATH, it's complement problem. Every NP-problem has a dual by switching the "yes" and "no" cases.

Nobody knows if $NP = EXPTIME$, though it's pretty unlikely. But it seems like just having to do an exponential search isn't enough to characterize all exponential algorithms.


Minimum circles to cover a set of points and avoid another set of points Points are in 2d euclidean space. Given a set of n points, A, and a set of m points, B, what is the minimally sized set of circles such that this set of circles covers all points in A and no point in B is covered by a circle?

circles can have arbitrary radius

any thoughts about the difficulty of this problem? any thoughts on non trivial exact algorithms?

The following algorithm will find some set of circles, containing all the points in the set $A$ except all the points in the set $B$. This solution might be not optimal (please see the @j_random_hacker counterexample in comments), and it's unclear how close this solution will be to the optimal one. The time complexity of this algorithm is exponential, cause it needs the Set Cover Problem solution as one of its steps.

Step 1. Build Voronoi Diagram of the set $B$. This diagram will consist of cells, nodes, line segments and rays. Each node will correspond to (at least) three points from the set $B$, and each ray will correspond to exactly two points from the set $B$.

Step 2. For each Voronoi node construct a maximal empty open disk with center in this node. These disks will have (at least) three points from the set $B$ on their boundary, and they won't contain any points from the set $B$. The number of such disks will be $\Theta(|B|)$.

Step 3. For each Voronoi ray construct a maximal empty open disk with center at this ray and infinitely large radius - it'll be actually a halfplane, corresponding to two points from the convex hull of the set $B$. These "disks" will have exactly two points from the set $B$ on their boundary, and they won't contain any points from the set $B$. The number of such "disks" will be $\Theta(|B|)$.

Step 4. For each point from the set $A$ find all disks, constructed above, containing this point. Each such point may belong to more than one disk, and each disk may contain any number of points from zero to $|A|$. Find a minimal subset of the set of all disks, which contains all the points from the set $A$. This is the classic Set Cover Problem, which is NP-complete (it's tempting to try to use geometric nature of this sub-problem to accelerate the search, however it won't be possible - please see the Geometric Set Cover Problem page for more details).

I'm thankful to @DiscreteLizard for pointing my error out in the previous version of this answer, and for suggesting the term "disk", which looks more adequate than the "circle".

I'd call this problem a "Bomber Problem" - we try to use a minimal number of bombs to strike all needed locations except some friendly ones. Sorry for militaristic jargon!


Given the same set of nodes, why is it (generally) easier to find a Euler cycle than a Hamilton cycle? To find a Hamilton cycle is a NPC problem, but Euler is not.
Considering one can always transform the vertex as edge or vice versa conceptually. Then the vertex can be used to describe the information which originally edge does.

What properties make the Euler graph more easily to be resolved?

For example, in genome assembly problem, one can either consider a Kmer as vertex or edge(de bruijn graph), it's just two perspectives to look at the same thing. I think their should be additional or missing information between two kind of explanation.

Suppose you are trying to find a Hamiltonian cycle on a graph.

You can solve this efficiently in the manner you describe (i.e. converting vertices into edges and then solving for an Euler path) if and only if the graph is a line graph.

There are a number of characterisations of line graphs.

For example, a graph is a line graph if and only if it does not contain any of these 9 graphs below as a subgraph:

An alternative characterisation is that a graph is a line graph if and only if you can partition the graph into cliques such that every vertex belongs to exactly two cliques.

This characterisation is perhaps more useful as you can apply Euler's proof to these cliques.


Using hashing to solve 4-sum problem The famous 4-sum problem is to find 4 elements at unique indices in an array which sum to a given X. I was looking at one solution I found:
findFourElements(A[1], ..., A[n], X)

create hashtable mp
for each 1 ≤ i < j ≤ n:
   mp[A[i] + A[j]] ← (i,j)     // (i,j) is an ordered pair
end for
for each 1 ≤ k < l ≤ n:
   if mp contains A[k] + A[l]:
      (i,j) ← mp[X - (A[k] + A[l])]
      if i ∉ {k,l} and j ∉ {k,l}:
         return A(i),A(j),A(k),A(l)
      end if
   end if
end for

It is working fine on some test cases I tried. But I have a doubt: in the hashtable we are just storing one occurrence of each pair, but there can be a case in which a solution exists, but since we stored only one occurrence of each pair, we only have overlapping occurrences, and we may miss the non-overlapping ones. But still I am not able to produce any test case to fail it. Is this algorithm correct, or does it fail for some test case?

Suppose $A[i] + A[j] + A[k] + A[\ell] = X$. If there is a way to break this sum into two non-equal parts, then the problem you mention does not occur. Otherwise, we have
\begin{align}
A[i] + A[j] &= A[k] + A[\ell] \\
A[i] + A[k] &= A[j] + A[\ell] \\
A[i] + A[\ell] &= A[j] + A[k]
\end{align}
In fact, all of these are equal to $X/2$, and this implies that $A[i] = A[j] = A[k] = A[\ell]$.
The hashtable entry for $X/2$ can only contain two of the indices $i,j,k,\ell$, say $i,j$ (it might contain fewer). The algorithm then finds the correct solution when it reaches $k,\ell$ in the second stage.


Efficient way to find intersections I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

I am randomly creating a path thru all the vertices and I want to know if there is any efficient way to find all the intersections on my path.

A path of length $n$ consists of $n$ line segments in the plane.  You want to find all intersections between these line segments.  This is a standard problem that has been studied in depth in the computer graphics literature.

A simple algorithm is the following: for each pair of line segments, check whether they intersect (using a standard geometric algorithm).  The running time of this algorithm is $O(n^2)$.  In terms of worst-case complexity, this is the best we can hope for, as in the worst case, there can be $\Theta(n^2)$ intersections, so obviously it'll take at least $\Theta(n^2)$ time to output them all.

However, in many cases, we have an arrangement of line segments where there are only a few intersections, say at most $O(n)$ intersections.  In this case, there are algorithms whose running time is $O(n \lg n)$.  See, e.g., the sweep line technique; there are others as well.  In general, if there are $k$ intersections, the total running time for the sweep line algorithm to find all $k$ intersections is $O((n+k) \lg n)$ time.


Rectangle Coverage by Sweep Line I am given an exercise unfortunately I didn't succeed by myself.

  There is a set of rectangles $R_{1}..R_{n}$ and a rectangle $R_{0}$. Using plane sweeping algorithm determine if $R_{0}$ is completely covered by the set of $R_{1}..R_{n}$.

For more details about the principle of sweep line algorithms see here.

Let's start from the beginning. Initially we know sweep line algorithm as the algorithm for finding line segment intersectionswhich requires two data structures:

a set $Q$ of event points (it stores endpoints of segments and intersections points)
a status $T$ (dynamic structure for the set of segments the sweep line intersecting)

The General Idea: assume that sweep line $l$ is a vertical line that starts approaching the set of rectangles from the left. Sort all $x$ coordinates of rectangles and store them in $Q$ in increasing order - should take $O(n\log n)$. Start from the first event point, for every point determine the set of rectangles that intersect at given $x$ coordinate, identify continuous segments of intersection rectangles and check if they cover $R_{0}$ completely at current $x$ coordinate. With $T$ as a binary tree it's gonna take $O(\log n)$. If any part of $R_{0}$ remains uncovered that $R_{0}$ is not completely covered.

Details: The idea of segment intersection algorithm was that only adjacent segments intersect. Based on this fact we built status $T$ and maintained it throughout the algorithm. I tried to find a similar idea in this case and so far with no success, the only thing I can say is two rectangles intersect if their corresponding $x$ and $y$ coordinates overlap.

The problem is how to build and maintain $T$, and what the complexity of building and maintain $T$ is. I assume that R trees can be very useful in this case, but as I found it's very difficult to determine the minimum bounding rectangle using R trees.

Do you have any idea about how to solve this problem, and particularly how to build $T$?

Let's start with $n$ axis-aligned rectangles, since there is a kind of easy direct argument.  We'll sweep a vertical line.  The events are the endpoints of horizontal edges of the rectangles.  As we sweep we maintain a set of intervals on the sweep line that are "uncovered" by $R_i$, $i\ge 1$:

Add the vertical interval covered by the rectangle $R_i$ to the sweep line when we first encounter $R_i$
Remove the vertical interval covered by the rectangle $R_i$ from the sweep line when it moves past $R_i$

It's easy to do this with a binary tree so that updates take $O(\log n)$ time.  (The problem is, essentially, 1-dimensional.  You figure out if the endpoints are in an uncovered interval and extend/merge appropriately when adding and lengthen them when removing.)

Then you just check that, in the span of $R_0$, none of the uncovered intervals ever intersect the vertical span of $R_0$.  The whole thing is $O(n\log n)$ time an $O(n)$ space.

For the general case, the obvious trick is not quite so fast.  Use the standard sweep line algorithm to compute the whole planar subdivision induced by the rectangles.

Clearly some disk-like set $F'$ of the faces covers $R_0$.  By itself, this doesn't tell us enough, since what we are interested in is whether any of these faces is inside $R_0$ and outside the other rectangles.  To do this, we modify the construction a little bit, so that when we add an edge, we tag one side with the identity of the rectangle it's inside.  This adds $O(1)$ overhead, so the construction is $O(n^2\log n)$ time; with no assumptions on the rectangles, the output can be $\Omega(n^2)$ in size, so we are using that much space in the worst case, so the time is, "existentially optimal" though not "output sensitive".

Finally, $R_0$ is covered so long as none of the faces in $F'$ have only edges not tagged as being in one of the $R_i$.  The point is that if an edge of $f$ is in $R_i$, then the whole of $f$ is as well. Imagine sweeping a line over $f$ orthogonally along this edge: it can only leave $R_i$ either outside of $f$ or $f$ is bounded by more than one edge of $R_i$.

So the conclusion is that the special case is $O(n\log n)$ and the general one is $O(n^2\log n)$ at least, but I suspect it can be improved.


Proving using Beta Reductions (Lambda Calculus) I am working on proving something by using Lambda Calculus and Beta Reductions, and I was following along a tutorial on another problem and attempted to carry over the knowledge onto a different problem and I am a little confused on the last step.

The problem is to prove $\textbf{or true false}$.

Here are my steps: (if there are any improvements or errors please let me know)

Step 1: Begin writing the identity for OR along with the parameters true and false.

$(\lambda x. \lambda y.(x ~ true ~ y)) ~ true false$

Step 2: Replace the $x$ terms with true.

$(\lambda y.(true ~ true ~ y)) ~ false $

Step 3: Replace the $y$ terms with false.

$ true ~ true ~ false \equiv (true ~ true) false $

Step 4: (I am a little shaky on this step, however I saw it done this way). Expand on one of the terms by replacing with it's identity. So we break true into:

$ (\lambda x. \lambda y. x) true ~ false $

Step 5: Again, replace x with true.

$(\lambda y.true) ~ false$

Step 6: $\textbf{this is the step i am most confused on}$
It looks as if since there is no way we can distribute the false to the y we simply just drop both of them since it is not an applicable function. Which then returns you with true, which stands to reason that true or false is true.

Can anyone shed light on Step 6? Or if I am correct and thats the rationale please let me know!

First let:
$$ true = \lambda x ~ y . x $$
$$ false = \lambda x ~ y . y$$
$$ or = \lambda x ~ y .((x ~ true) y) $$
So this is what you wrote:
$$or ~ true ~ false \rhd_{\beta} true$$
$$  \Bigg ( \Big( \lambda x ~ y . (x ~ true) y \Big) true \Bigg) ~ false $$
$$ \Bigg ( \lambda y. \Big ((true ~ true) y \Big) \Bigg) false $$
$$ ((true ~ true) ~ false) $$
Unwrap $true$.
$$ \Big( (\lambda x ~ y . x) ~ true) \Big) ~ false $$
$$ \color{red}{(\lambda y . true) ~ false } \rhd true $$
In the red step, which is what's burdening you, you're just consuming the $false$, why? Because there are no free $y$ variables in $true \equiv (\lambda x~ y. x)$. This is rule-(e) for substitution.

Definition 1.12 (Substitution) For any $M, N, x$, define $[N/x]M$ to be the result of substituting $N$ for every free occurrence of $x$ in $M$, and changing bound variables to avoid clashes. The precise definition is by induction on $M$, as follows (after [CF58, p.94]).
(a) $[N/x]x \equiv N$
(b) $[N/x]a \equiv a$ for all atoms $a \not \equiv x$
(c) $[N/x](PQ) \equiv ([N/x]P)([N/x]Q)$
(d) $[N/x](\lambda x.P) \equiv (\lambda x.P)$
(e) $[N/x](\lambda y.P) \equiv P$ if $x \not \in FV(P)$.
(f) $[N/x](\lambda y.P) \equiv \lambda y. [N/x]P$ if $x \in FV(P)$ and $y \not \in FV(N)$.
(g) $[N/x](\lambda y.P) \equiv \lambda z. [N/x][z/y]P$ if $x \in FV(P)$ and $y \in FV(N)$.

Note: $FV(P)$ stands for the set of free variables of $P$.


Did I correctly prune this min-max search tree using alpha-beta pruning? I am studying some old past test questions.  Is this search tree correctly pruned?

I once implemented this in common lisp and running my program on your tree tells me that the pruned nodes are the one you marked and also the rightmost leaf and its parent.  The output of the program gives $\alpha$ and $\beta$ values for each node (if you mark from A through X in a BFS manner, left-to-right.  Then O and J are pruned).

MIN: K     -INFTY    11        [v:11]
MIN: L     11        INFTY     [v:9]
MAX: E     11        INFTY     [v:11]
MIN: M     -INFTY    4         [v:4]
MIN: N     4         11        [v:13]
MAX: F     4         11        [v:13]
MIN: B     -INFTY    11        [v:11]
MIN: P     11        12        [v:12]
MIN: Q     12        INFTY     [v:8]
MIN: R     12        INFTY     [v:4]
MAX: G     12        INFTY     [v:12]
MIN: C     11        12        [v:12]
MIN: S     12        INFTY     [v:9]
MIN: T     12        13        [v:13]
MIN: U     13        INFTY     [v:1]
MAX: H     13        INFTY     [v:13]
MIN: V     12        13        [v:12]
MIN: W     12        13        [v:9]
MAX: I     12        13        [v:12]
MIN: D     12        13        [v:12]
MAX: A     12        INFTY     [v:12]
12
21
T


Is there an NP-complete problem, such that the decision version of its counting problem is not PP-complete? Once we fix a polynomial time deterministic verifier V(input, certificate), its corresponding NP problem is the question: For this input, does a (polynomial size) certificate exist such that V(input, certificate) returns True?

The associated counting problem (#P class) is: How many certificates exist such that V(input, certificate) returns True?

#P is not a "decision problems" class, but a class of counting problems. The closest traditional "decision problems" class is PP, which has problems of the form: Do the majority of the certificates result in V(input, certificate) returning True?

I am interested in the decision version of the counting problem associated with a certain NP-complete problem + verifier, which would be: Given the input instance and a positive integer number K: Are there at least K different certificates such that V(input, certificate) returns True?

This decision problem is clearly equivalent to the counting version (via a Binary Search). If I am not mistaken, the class of all these "decision versions of the counting problems associated to NP problems" is exactly as hard as PP since:

1) Any of these "counting-decision" problems can be reframed as some other majority problem, by choosing an ad-hoc verifier definition where a lot of certificates are manually deemed to be True or False such that there are at least K True certificates in the original if and only if the majority is True in the resulting problem. Just as a simple example to illustrate the reduction idea, if there where 8 possible certificates, and we want to know whether there are at least 3 True ones, we might propose a different verifier having 11 possible certificates: for the 8 original ones it just checks normally, and for the other three it immediately returns True without looking at the input. Since the majority of 11 is 6, this new verifier accepts a majority of certificates exactly if the original one accepts at least 3.

Thus, all of these problems are in PP.

2) The corresponding "counting-decision" version for any PP-complete problem will obviously be PP-hard, since solving the original majority problem is simply solving the $(input, \left \lfloor \frac{  totalCertificates}{2} \right \rfloor + 1)$ problem. Thus, such problems are PP-complete.

So now, at last, can I clearly state my question, which is a "more sofisticated version" of the same idea shown in MAX,MAJ variants of NP complete problems:

Is there any NP-complete problem such that the decision version of its counting problem (which is in PP) is not PP-complete?

For example, in the case of Subset-Sum the associated decision problem I'm interested in would be: Are there at least K nonempty subsets of zero sum?

Since K is free and not limited to be near half of the certificates, the argument of the other answer does not apply.

Putting your question in more precise terms, you ask whether the following claim holds:

$* \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow count_R \text{ is PP-complete}$

Where $count_R$ is defined as follows:

$count_R=\left\{(x,k) \big| \hspace{1mm} \left\lvert\left\{y : R(x,y)\right\}\right\rvert\ge k\right\}$.

We call a relation $R(x,y)$ NP-complete if it is computable in polynomial time, and the language it defines $L_R=\left\{x | \exists y \hspace{1mm} R(x,y)=1\right\}$ is NP-complete.

We talk in terms of relations, since as you mentioned, the counting version has to be defined relative to some specific verifier.

It seems that this is an open question, as (*) implies:

$** \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow \#R\text{ is #P-complete}$

Where $\#R(x)=\left\lvert \left\{y : R(x,y)\right\} \right\rvert$.

To see why * implies the above, let $R(x,y)$ be some NP-complete relation. Using (*), $count_R$ is PP complete, so $count_{\text{SAT}}\le_p count_R$. In that case, $\#SAT\in\mathsf{FP}^{\# R}$ and thus $\#R$ is $\# P$-complete (use binary search, where in each cutoff you apply the reduction from $count_{\text{SAT}}$ to $count_R$ and query the $\#R$ oracle on the result).

To my knowledge, (**) is currently open. See this related question from cstheory. Also related.


Counting occurrences of word in a text Let's say I have a long text of 1M words and I would like to create a table of all the words ordered by the number of occurrences in the text.

One approach would be populating a dynamic array with each word and linear search them to count the occurrences in $O(n^2)$ then sort the array by occurrences in $O(n \log n)$.

Another approach would be to use y priority queue and a trie. The insertion in the priority queue is $O(\log n)$ and the build of the trie is $O(n)$. But traversing the trie to build the priority queue is somehow difficult to evaluate.

Eventually using a hash map seems to be the best solution, but computing the hash could cost a little bit of time even though it is just a constant. In this you have $n$ insertion/lookup in $O(1)$ then a final sort of the hashmap by occurrences in $O(n \log n)$.

So it is clear that the former approach is the worse and the latter the best. But how can I evaluate the complexity of the second one?

I'm not sure I understand why do you need a priority queue.

The best algorithm should be as follows (pseudocode):

1) count the words
2) sort them by count

Counting each word you can loop through each word and update the count in the hash table for each word.    This is done $n$ times and you need $O(1)$ for accessing + $O(1)$ updating the hash table thus $O(n)$.

Sorting is $O(n \log n)$. Thus the complexity is $O(n \log n)$.


Algorithm for checking unambiguity in the derivation of a string It is known that given a Context Free Grammar $G$, checking that it is ambiguous or not is undecidable. But, if I have a string $s \in L(G)$, does there exist an algorithm to check whether $s$ particularly can be derived unambiguously in $G$?

gnasher's comment more or less answers this. A sketch of an algorithm would be:

enumerate all derivations of the grammar that do not generate strings longer than $s$. This can be done, because CFGs do not have deleting rules (or if yours do, they can be converted for example to Chomsky Normal Form)
check how many of the strings generated are equal to $s$.

This takes a long time, of course. But I doubt that there is a fundamentally better way.


Approximation algorithm for Feedback Arc Set Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph.  The problem is to find the minimum cardinality such set.

I want to find out about is there some approximation algorithm around this problem.

Kann's online compendium of NPO problems is a good place to start. Feedback Arc Set (the "Directed part is redundant when you use "arc") is:

APX-hard,
Approximable within $\mathcal{O}(\log n \log \log n)$ (where $n$ is the number of vertices).

The problem is also fixed-parameter tractable1, so it might make more sense to solve the problem exactly, rather than use what looks like a bad approximation algorithm. (Or as Pål points out below, the running time is a bit... unpleasant, so maybe not.)

Notes

1 - JACM publication, Razgon & Sullivan's preprint, Chen, Liu and Lu's preprint - the problem was independently solved and the results combined to one publication


Find all the special graphs which can reduced to the shortest paths graph I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative cycle.

An execution of some algorithms will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves. For instance, Floyd–Warshall algorithm is straightforward, and it works. Let us denote the result by $G' = (V, E, W')$.

In $G'$, it is possible that for an edge from $i$ to $j$, $w'(i,j) = w'(i, k_0) + w'(k_0, k_1) + \dots + w'(k_n, j)$. Let us make from $G'$ another graph $G''$ whose any element is same as $G'$ except $w''(i,j) = \infty \neq w'(i,j)$. Therefore we know that an execution of a shortest paths algorithm on $G''$ will give $G'$.

So given a $G'$, I would like to find all the graphs like $G''$, such that for all $i$ and $j$, $w''(i,j) \in \{ w'(i,j), \infty\}$, and $G''$ can be reduced to $G'$ via a shortest paths algorithm.

Hope my question is clear... I do not know if an algorithm for this exists already, does anyone have any idea?

Nearest neighbor, nearest insertion, farthest insertion, and cheapest insertion are just some heuristics to get you started. You can also model the problem as a maximum flow integer program.

http://www.ida.liu.se/~TDDB19/reports_2003/htsp.pdf


Sorting post numbers in a graph in $O(n)$ time After running dfs on a graph, we get a list of n post and pre numbers. How do we sort this list in $O(n)$ time instead of $O(n\log n)$ time?

You cheat. At the moment where you assign the post number, you know that it's the greatest post number so far. So you just keep a list vertices and whenever a vertex gets assigned a post number, you push it at the head of the list. At the end, the list will contain all vertices in decreasing post order. If you want them in increasing post order, you just have to reverse it which is $O(n)$. The same thing works for pre numbers.


Testing whether a determinant polynomial is identically zero Suppose we are given matrices $A_1, \ldots, A_k$ which are $n \times n$ matrices with rational entries and are asked to determine whether the polynomial ${\rm det}(\alpha_1 A_1 + \alpha_2 A_2 + \cdots + \alpha_k A_k)$ is identically zero. How can we do this deterministically in polynomial time in $n$ and $k$?

I'm aware that black-box polynomial identity testing is a difficult problem, but then this is not quite a black box.

Is this a practical problem or a theoretical problem?

If it a practical problem, it looks to me like standard randomized algorithms for black-box polynomial identity testing should suffice to solve this.

Your polynomial is a multivariate polynomial of degree $n$ over the field $\mathbb{R}$.  Pick a set $S$ of real numbers with cardinality $2n$, draw $k$ numbers uniformly at random from $S$, and evaluate the polynomial at those points (substituting the first for $\alpha_1$, the second for $\alpha_2$, and so on).  Check whether the result is non-zero.  By Schwartz-Zippel, either your polynomial is identically zero or else the result will be non-zero with probability $\ge 1/2$.  Thus, we can repeat this test $m$ times.  If we get zero every time, output "the polynomial is identically zero".  Otherwise output "the polynomial is not identically zero".  You'll be wrong with probability at most $1/2^m$.

If you want to have a small seed, use a cryptographically secure pseudorandom number generator to generator the random numbers needed for this procedure.  Under a suitable cryptographic assumption, this will allow you to use only 128 bits of true randomness (or so).

This should be good enough for all practical applications.  Of course, it doesn't answer the theoretical question of whether this problem has a deterministic polytime algorithm.