String searching, where we allow characters to almost-match Let $\Sigma= \{1,...,n\}$.  Let $T$ and $Q$ be two strings with characters from the alphabet $\Sigma$ of lengths $n,k$, respectively.  I am looking for an algorithm to test whether $Q$ appears as a substring of $T$, except that I have a more relaxed notion of when two characters match.

Two characters in these strings are similar if $|Q[j] - T[l]|\leq 1$. Call the indices $i,j$  a good pair if $|Q[j] - T[j+i-1]|\leq 1$, that is if the characters in the $j+i-1$'s cell in $T$ and the $j$'s cell in $Q$ are similar. An index $i$ is good for all if for all $1\leq j \leq k$, the pair $i,j$ is a good pair.

I'd like to find all the good-for-all indices. That is,
I aim to find all the indices $1\leq i\leq n$ s.t. for all $1\leq j \leq k$, we have $|Q[j] - T[j+(i-1)]|\leq 1$.

I'm at a loss even where should I begin from. Obviously I can solve naively, but this is not interesting at all. I'm not even sure what should be the optimal time for this problem. Also, I don't see any lower bound on the running time (except $O(n)$ obviously).

How efficiently can we find all the good-for-all indices?  What algorithm can I use for this?

You're looking for all instances of $Q$ as a substring of $T$, except that two symbols are still considered to match even if they differ by one, so this is basically a generalization of substring search (string matching).

This particular problem can be solved efficiently using convolution methods.  The running time will be something like $O(n \lg n)$, times some small factors.  Let me outline the algorithm, and then explain why it works.

The algorithm

Step 1: We will construct binary strings $T' \in \{0,1\}^{6n}$, $Q' \in \{0,1\}^{6k}$, with a special property:

If index $i$ is good-for-all, then there are $\ge k$ indices $j$ where both $T'_j$ and $Q'_{j+6i}$ are 1.
If index $i$ is not good-for-all, then with probability at least $1/2$, there are $< k$ indices $j$ where both $T'_j$ and $Q'_{j+6i}$ are 1.

Let me outline how to construct $T',Q'$.  First, pick a random hash function $h:\Sigma \to \{1,2,\dots,6\}$.  Next, define a code $C_T:\Sigma \to \{0,1\}^6$ like this: $C_T(x)$ is a 6-bit string that is 1 at index $h(x)$ and 0 at all other positions.  Also, define a code $C_Q:\Sigma \to \{0,1\}^6$ as follows: $C_Q(x)$ is a 6-bit string that is 1 at indices $h(x)$, $h(x-1)$, and $h(x+1)$, and 0 at all other positions.

Finally, define the binary string $T'$ to be the concatenation of codewords

$$T' = C_T(T[0]) C_T(T[1]) \cdots C_T(T[n-1]),$$

and similarly $Q'$ to be the concatenation of codewords

$$Q' = C_Q(Q[0]) C_Q(Q[1]) \cdots C_Q(Q[k-1]).$$

You can check that these two strings satisfy the properties above.

Step 2: We will use convolution (polynomial multiplication) to find all indices that are good-for-all.  Define polynomials $T(x),Q(x)$ from the binary strings $T',Q'$ as follows:

$$\begin{align*}
T(x) &= \sum_j T'_j x^j\\
Q(x) &= \sum_j Q'_j x^{6k-1-j}
\end{align*}$$

Multiply these two polynomials to get the polynomial $P(x) = T(x) Q(x)$.  Let $p_i$ be the coefficient of $x^i$ in $P(x)$, so that $P(x) = \sum_i p_i x^i$.

We have the following nifty property: $p_{6k-1-6i}$ counts the number of indices $j$ where both $T'_{j}$ and $Q'_{j+6i}$ are 1.  Thus, we can immediately read off a set of "suggested" indices that are "suggested good-for-all".  Every index that is actually good-for-all will appear in that set, and every non-good-for-all index has at most a probability $1/2$ of appearing in the set of "suggested" indices.

Step 3: Repeat Steps 1 and 2 80 times, and keep only those indices that are suggested in every iteration.  Output that list.

Correctness

All of the good-for-all indices will remain and appear in the output.  Also, there's at most a $n/2^{80}$ probability that any non-good-for-all index survives all 80 iterations.  This probability is small enough as to be negligible.

Running time

The running time of this algorithm is dominated by the time to multiply two polynomials of degree $6n,6k$.  Assuming $n \ge k$, this running time is basically $O(n \lg n)$ (ignoring log-log factors) using standard techniques.

In practice there are a number of ways one could optimize this further.  For instance, we can often stop early without doing all 80 iterations: once the set of surviving suggested indices is small enough, we can just check each one directly and output only the correct ones.

Other approaches

Since your problem is a generalization of string matching, you could also look at other algorithms for string matching and see if any of those techniques can be generalized to your situation.  For instance:

It would be straightforward to adapt finite automaton based search methods: you can build an automaton based on $Q$ that accepts all strings that would match $Q$ as a substring (where "match" allows two similar characters to be treated as matching).  Building such a DFA might be very slow, but once you have the DFA, testing whether $T$ is a match can be done very fast -- in linear time.
It might be possible to adapt the Knuth-Morris-Pratt algorithm to your situation.  It might take some thought to work out the details, but if it works out, you might get a linear-time algorithm, i.e., $O(n)$ running time.
Also, take a look at Boyer-Moore.

I would especially suggest you take a look at KMP -- it looks plausible to me that this might yield a viable algorithm.


Can normal physics laws be simulated in Digital physics? Physics is defined as the study of an object {matter or energy} with its interaction with other objects:

  Physics is the study of matter, energy, and the interaction between them.

On the other hand, Digital physics is  based on computations and information.

  Digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable.

If we have a universal computer {a universal turing machine} and a program that can compute the evolution of the universe (Digital Physics) running on it, can this specific program simulate our normal physics laws like the classical mechanics laws or quantum mechanics laws ?

1- Can we simulate a universe with its fundemental laws {i.e physics} and change these laws by a universal computer accordingly ?

2- How a simulation of a universe (if any) with fundemental laws {like physics} would help to further understanding in physics ?

3- Is there any form of universal turing machine to apply these simulation ?

The laws of physics are stated in the form of mathematics. Differential equations are pretty popular, for example classical mechanics can be described with differential equations.

You can program a computer to take some initial state of the universe and apply all the laws of physics to it to get a new state of the universe. This comes with a couple of caveats. First, you need to somehow discretize the time steps you compute. Differential equations operate under continuous time, but a numerical simulations does discrete steps. It's reasonably well understood how to do that without losing too much precision. This brings us to a second problem, precision. Physics is generally formulated using real (or complex) variables, but computers only deal with finite precision. Usually this is ok, because in reality we can also only distinguish things with finite precision. Lastly, our laws of physics are not yet complete. There are a number of phenomena where we don't really know what's supposed to happen, so the simulation won't represent the real universe perfectly, even if we start with a proper starting state (which we can also only guess) and use sufficient precision and sufficiently small time steps.

Note that it is completely impractical to simulate all laws of physics as we know them on real computers. Even simulating single molecules with all relevant laws is very hard even for supercomputers.

Nevertheless, physicists simulate things all the time, sometimes using bold approximations to cut down the required computation. It's really important in physics to do simulations. Wikipedia has on overview article on Computational Physics and Richard Feynman has written a classic paper called Simulating Physics with Computers.

It is of course also possible to tweak the laws of Physics a bit and do your simulation. You can change the equations, or the constants and see what happens to your simulated system. You can for example find that changing some constants just a little produces an inhospitable universe.

Now I don't think it's possible to change fundamental mathematical truths in your simulated universe, because Physics makes no prediction about mathematics. You can't change the laws of Physics such that 1+1 != 2.


Solving a graph problem by Gaussian elimination I have been given a graph with n nodes. Now, I have to color every node of this graph by k colors, number from 0 to k-1. Now, there is a rule.

For a node $x$ with adjacent nodes $y_1 , y_2, y_3, y_4,... y_m$, $color(x)=(color(y_1)+color(y_2)+color(y_3)+...+color(y_m)) \pmod k $

where $color(a)$ indicates a color number from 0 to k-1. I have to find number of ways I can color the whole graph.

My approach to the problem was simple. I was constructing a $n*n$ matrix for n nodes in graph with equations like $col(x)-col(y_1)-col(y_2)-col(y_3)...-col(y_m)$. And trying to find number of all zero rows, which will provide us number of free variable. Is my approach correct?

As, no good solutions were given and my research else where proved to be helpful, I am answering my own question. The main idea of the solution is correct.

The number of independent variables controls the total possible way of coloring but the matrix construction is little different.

The matrix will look like this for the following graph.

A graph with 4 nodes $\{1,2,3,4\}$ and 4 edges $\{(1,2),(2,3),(3,4),(4,1)\}$ provides us the equations,

$col_1 \equiv (col_2+col_4)\mod k$

$col_2 \equiv (col_1+col_3)\mod k$

$col_3 \equiv (col_2+col_4)\mod k$

$col_4 \equiv (col_1+col_3)\mod k$

Providing us equations like,

$(col_1 -col_2-col_4)\mod k \equiv 0$

$(col_2 -col_1-col_3)\mod k \equiv 0$

$(col_3 -col_2-col_4)\mod k \equiv 0$

$(col_4 -col_1-col_3)\mod k \equiv 0$

We form matrix like this for these equations:

$$
\begin{bmatrix}
1 & k-1 & 0 & k-1\\
k-1 &1 & k-1 & 0\\
0 &k-1 & 1 & k-1\\
k-1 &0 & k-1 & 1\\
\end{bmatrix}
$$

Not to mention for every step of Gaussian elimination we have to use mod operation, if any number is negative take the equivalent positive mod.

Then, for every independent variable we can assign a value from 0 to (k-1) and get solution for every of these equations. If number of independent variables is $x$ then the answer will be $k^x$


Is computing 2^n NP-complete problems EXPTIME or NEXPTIME complete? Given a NP-complete problem $A$, with parameter $a$ and a problem $B$ with parameter $b$, such that a problem in $A$ of size $\mathcal{O}(2^a)$ is $\mathcal{O}(b)$ when translated to $B$, is $B$ EXPTIME or NEXPTIME complete? I.e. If a problem of exponential size relative to a NPC problem is of linear size in another problem, is the other problem exponential time complete? (I think there needs to be an upper bound on the complexity of translating, but I'm not entirely sure what that would be.)

I am not 100% sure that I understand the question but here is an attempt where I reformulate your problem.

You have $A,B\subseteq \{0,1\}^*$ and know that $A$ is NP-complete. Furthermore you have a reduction $f$ such that $f(x)\in B$ iff $x\in A$ and such that $|f(x)|$ is in $\log(O(|x|)$. Does that make $B$ NEXPTIME-hard?

Well, since $A$ is NP-complete, I can translate any question $y$ of the the form "does a nondet. TM $M$ halts in time $n$?" into an equivalent question $g(y)$ for $A$, using the reduction that establishes the NP-hardness of $A$. It is thus possible to translate an NEXPTIME-hard question $y$ of the form "does $M$ halts in time $2^n$?" into an equivalent $g'(y)$ for $A$. That reduction is very simple to describe but it produces instances of exponential size. If we could compute $f(g'(x))$ efficiently, we would have a reduction showing that $B$ is NEXPTIME-hard. This is possible in many cases --remember that $g'$ is very simple and that $|f(g'(x))|$ is in $O(|x|)$-- but this depends on knowing $f$ and how nicely it interacts with $g'$.

So I'd say that in general you cannot say that $B$ is NEXPTIME-hard but in many specific cases you'll manage to show it is.

(Final note: the above is about lower bounds. You cannot provide upper bounds for the complexity of $B$ from the assumptions. They only talk about the part of $B$ that is in the image of $f$).


If $f(n)=O(g(n))$ can I say there exists a $n_0$ for a specific $c$? I've been working on an asymptotic proof and I want to start with saying that since $\log z=O(z)$ then $\log z\le\frac1 9z$ for $z\ge z_0$. In this example I'm picking $c=\frac1 9$ and hoping $z_0$ exists, but is $z_0$ guaranteed to exist if I pick $c$?

Let's take as an example $f(n) = g(n) = n$ and $c = 1/2$. Does there exist an $n_0$ such that $f(n) \leq cg(n)$ for all $n \geq n_0$?
In your case, you know more: $\log n = o(n)$. This means that
$$
\lim_{n\to\infty} \frac{\log n}{n} = 0,
$$
which implies that for every $c$ there exists $n_0$ such that $\frac{\log n}{n} \leq c$ for all $n \geq n_0$.


Minimum number of components in graph Minimum number of components in graph where we have 69 vertices and 43 edges. I think the best way is to create a path? One path and the rest would be isolated components. Since in path we use only one edge for 2 vertices. Correct?

Yes, this is correct.

The easiest way to get to the result is to look at a graph with $v$ vertices and $0$ edges. It obviously has $v$ components. Adding an edge between two vertices $a$ and $b$ reduces the number of components if $a$ was not reachable from $b$ before adding the new edge.

Concerning  "best" solution: Your approach yields an optimal solution, though it is only one way to do it - there are other ways (e.g. 26 components with either 2 or 3 vertices) that work equally well.


Searching through a heap complexity Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the property of a max-heap doesn't really help us unlike a bst. Thanks.

You are correct: it's $\Theta(n)$ in the worst case. Suppose you're looking for something that's no bigger than the smallest value in a max-heap. The max-heap property (that the value of every node is at least as big as everything in the subtree below it) gives you no useful information and you must check both subtrees of every node.


Is there a correlation of zip compression ratio and density of information provided by a text? I'll phrase my question using an intuitive and rather extreme example:

Is the expected compression ratio (using zip compression) of a children's book higher than that of a novel written for adults?

I read somewhere that specifically the compression ratio for zip compression can be considered an indicator for the information (as interpreted by a human being) contained in a text. Can't find this article anymore though.

I am not sure how to attack this question. Of course no compression algorithm can grasp the meaning of verbal content. So what would a zip compression ratio reflect when applied to a text? Is it just symbol patterns - like word repetitions will lead to higher ratio - so basically it would just reflect the vocabulary?

Update:

Another way to put my question would be whether there is a correlation which goes beyond repetition of words / restricted vocabulary.

Tangentially related:

Relation of Word Order and Compression Ratio and Degree of Structure

Shannon's noisless coding theorem is the formal statement that the size of an optimally compressed data stream is equivalent to the amount of information in that data stream.

But you are also right that the definition of "amount of information" depends on your probability model for the data stream.  If you have a correct table of letter probabilities before you start the compression then Huffman coding gets within a constant factor of optimal, Arithmetic coding gets even closer to optimal.  But if there are correlations between neighboring symbols (which there are in real human produced text) you can do better by choosing codes for pairs of letters.  And you can do even better if you look at triples, and so on.  Additionally, you typically don't have a very good probabilistic model of your data stream when you start, so you need to adaptively construct the probability table and then assign variable length symbols depending on the probabilities as you learn more.

The kinds of compression used in zip/gzip,  compress, and 7-zip are all variants of Lempel-Ziv coding.  Lempel-Ziv coding is adaptive, builds probability tables over varying length chunks of letters, and is optimal in the sense that given an infinite random stream that is ergodic (the probabilities are stable over time) it will, in the limit, adaptively find a table that takes into account correlations over arbitrary distances, and then use that table to produce a stream that approaches optimally coded.

Of course, neither children's books nor novels for adults are infinitely long ergodic random processes (although some of them may seem like they are) so the conditions of the theorems don't hold.

Here's an interesting interview with Jacob Ziv where he talks a little about the universality of Lempel-Ziv coding:
http://www.ieeeghn.org/wiki/index.php/Oral-History:Jacob_Ziv#Lempel-Ziv_algorithm.2C_Viterbi_algorithm.2C_and_Ziv-Zakai_bound.


Relation between Undecidable problems and NP-Hard I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)
I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.

And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)

I believe that this answer by Yuval Filmus all the questions you have asked.

  If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.

  We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.

  The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s \in SAT$ iff $f_i(s) \notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s \in A$ iff $|s| \in K$.

  By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n \in K$ (for $n \geq 2$) by taking a majority of three strings of length $n$.

To summarize,

Halting problem is NP-hard.
If $P\ne NP$, not all undecidable problems are NP-hard.
If $P = NP$, all non-trivial sets are NP-hard.

The original answer had not addressed the last part of your question, namely, are there problems which are neither NP nor NP Hard? I will be lazy again and quote another answer, this time by Peter Shor.

  There is a problem which is both NP-hard and in coNP if and only if NP = coNP.

  If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.

  On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have  coNP ⊆ NP. This means NP = coNP.

  The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.

So, assuming $NP \ne coNP$, there exist problems that are decidable but neither in NP nor NP-hard. Note that we don't know that $NP = coNP$ implies $P = NP$. So this is a stronger assumption than the one you had suggested ($P \ne NP$).


Simulate NPDAs with DTMs using only polynomial overhead We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$.

Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} \subseteq \mathrm{P}$ and $\mathrm{CFL} \subseteq \mathrm{NP}$,
respectively. We simply use the TM tape as stack, readig and writing only at one end of the used area. The only element we can not immediately translate is transitions which push more than one symbol on the stack; for such we add intermediate states. We get a TM that stays within a constant factor both in terms of size and runtime of the original PDA.

As a follow-up to my overly optimistic answer here (thanks @A.Schulz for exposing my mistake) I wonder: can we combine the two? That is, is there a (more or less) direct simulation from NPDA to DTM?

Naive translations as the above do not work because of the blow-up needed to resolve the nondeterminism. We may be able to make use of some normal forms such as absence of $\varepsilon$-transitions (are there others?), though.

We can combine two known techniques: CYK -which you mention- and the PDA to CFL construction.

Assume that the PDA is in "Chomsky Normal Form": it reads iff it pops, and pushes two symbols otherwise.
Formally, its instructions are of the form

$(p,\varepsilon,A) \mapsto (q,BC)$
$(p,a,A) \mapsto (q,\varepsilon)$

Recall that this can be transformed into CFL using non-terminals of the type $[p,A,r]$, and the productions

$[p,A,r] \to [q,B,s][s,C,r]$ for any "guessed" states $r,s$
$[p,A,q] \to a$

Note that $[p,A,r]$ is a non-terminal that derives all strings using certain computations (see below).

We do not have to explicitly perform the latter construction, but we can build it in the CYK itself, by introducing a table $P(i,j)$ that contains elements that are such triplets. So this would mean $[p,A,r] \in P(i,j)$ iff there is a computation on $w_i\dots w_j$ starting in state $p$ and ending in state $r$ that starts with $A$ on the stack and ends with an empty stack.


What's the difference between a broadcast algorithm and a flooding algorithm? Both the broadcast algorithm and the flooding algorithm seem exactly the same to me, some sites try to explain the difference but then other sites contradict their statements. At the moment I see both algorithms starting at a specific starting node. This starting node will send a message to all of its neighbors, and once received, the neighbors will send the message to all of their neighbors in turn, etc, etc. What is the difference?

Does the broadcast algorithm use a spanning tree, and the flooding algorithm doesn't? Does the flooding algorithm use previously used edges, whereas the broadcast algorithm only use edges that aren't used yet?

Broadcast routing is of three types :

1.) N-way unicast routing - There are N destinations and the source sends a copy of the packet to each destination by making N copies of the packet
and addressing each copy to a different destination.

2.) Uncontrolled flooding - The source node sends a copy of the packet to
all of its neighbors. When a node receives the packet, it
duplicates the packet and send to all of its neighbors except the sender.

3.) Controlled flooding - A source node puts its address and broadcast
sequence number into the packet. It sends the packet to all of it's neighbor. Each node maintains a list of the source address and
sequence number of each broadcast packet it has received. When a node receives a broadcast packet. If the received broadcast message has the source address and sequence number already present in the list then it will drop the packet otherwise make a copy and forward it to all the neighbors except sender.


Prove $\{abc : a+b=c\}$ is not context-free using pumping lemma I have the following alphabet:
$Σ = {0, 1, . . . , 9}$

and the Language $L$ defined as:
$L = \{ abc | a + b = c\} $

where substrings $a$, $b$ and $c$ are interpreted as ordinary integers.

My answer so far:

Assume $L$ is context-free. Then the pumping lemma for context-free languages applies to $L$.

Let $n$ be the the constant given by the pumping lemma.

Let $z=10^n20^n30^n$ clearly $z \in L$ and $|z| \geq n$

By the lemma we know that $z = uvwxy$ with $|vwx| \leq n$ and $ |vx| \geq 1$

There exists possibilities...

My questions:

I can see 8 possibilities where $vwx$ can be within $z$. For example in the beginning including the 1 and overlapping with the initial $0^n$. Another example the initial $0^n$. Is this one way to think in this particular question? How can I pump and show that the result does not belong to $L$?

Thank you for your time.

Suppose that $L$ were context-free. Then $L \cap 10^*20^*30^*$ would also be context-free. What is this language? It is easy to see that each of $a,b,c$ needs to contain a non-zero digit. Therefore $a = 10^i$, $b = 0^j20^k$, and $c=0^\ell30^m$. Clearly $i=k=m$, and so
$$L \cap 10^*20^*30^* = \{10^{i+j}20^{i+\ell}30^i : i,j,\ell \geq 0\} = \{10^i20^j30^k : i,j \geq k\}.$$

To make our life easier, let us consider instances with more structure: $L \cap 30^*130^*160^*2$. Consider any word $30^i130^j160^k2$. The only way in which $a+b$ ends with $2$ is if $a,b$ end with $1$, and so $a=30^i1$, $b=30^j1$, $c=60^j2$. This shows that
$$
L' \triangleq L \cap 30^*1 30^*1 60^*2 = \{ 30^i130^i160^i2 : i \geq 0\}.
$$
If $L$ were context-free, so would $L'$ be. Now define a homomorphism $h$ which maps $1,2,3,6$ to themselves and $a,b,c$ to $0$. Clearly
$$
L'' \triangleq h^{-1}(L') \cap 3a^*13b^*16c^*2 = \{3a^i13b^i16c^i2 : i \geq 0\}.
$$
If $L'$ were context-free so would $L''$ be. Finally, define a homomorphism $k$ which erases $1,2,3,6$ and fixes $a,b,c$. Then the following language would also be context-free:
$$
k(L'') = \{ a^i b^i c^i : i \geq 0 \}.
$$
However, this language is well-known to be non-context-free.

If for some reason you want to prove that $L$ is not context-free using the pumping lemma (the only reason I can see is that you were given this as an exercise), then you could consider instances of the form $30^n130^n160^n2$, which might be easier to handle than your original suggestion.


prove: max (w(E), w(E)) is a 1/2 approximation to the value OPT Hey I would like to find a answer for b. for a  look to the picture that is my answer for it. But I dont habe any Idea how i can solve this. Thank you guys. (I had to translate it to english maybe it will be hard to understand it sorry about that).

I don't know the definition of $1/2$-approximation algorithm, but it looks like what you will need to do is the following argument:
For an enumeration $\sigma:V\to\{1,2,...,n\}$ of the vertices, let, for each input graph $G=(V,E)$, the output of the algorithm be $A_\sigma(G)=\max(w(\overrightarrow{E}),w(\overleftarrow{E}))$.
We have that $OPT(G)\leq w(E)$.
On the other hand,
$$
\begin{align}
A_\sigma(G)&=\max(w(\overrightarrow{E}),w(\overleftarrow{E}))\\
&\geq\frac{w(\overrightarrow{E})+w(\overleftarrow{E})}{2}\\
&= \frac{w(E)}{2}
\end{align}$$
The last equation is because $\overrightarrow{E},\overleftarrow{E}$ is a partition of $E$.
Putting these two inequalities together we get $$OPT(G)\leq w(E)\leq 2A_\sigma(G)$$
Therefore $$\frac{A_\sigma(G)}{OPT(G)}\geq \frac{1}{2}$$


The order of which time complexity is higher, 3 ^ log(n) or n ^ 3? Which one has a higher order time complexity:

$n ^ 3$
$3 ^ {\log n}$

I know that an exponential time order is higher than polynomials. However, it uses a logarithmic power which is low for a large n, while n^3 or more could remain still high, not?

The answer easily follows from the identity $3^{\log n} = n^{\log 3}$. Whether or not $\log 3 < 3$ depends on the basis of the logarithm.


Maximize number of subsets Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words,
$$\max_{S \subset U\\ |S| = k} \sum_{i = 1}^n \mathbb{1}_{S_i \subseteq S}$$
Where $\mathbb{1}$ is an indicator function.
For my application, $n, m \approx 10000$, $k = 16$, and $|S_i| = 3$. Thus the naive brute-force approach will not work. (I think this is an NP-hard problem in general if you allow $k$ to vary).
Question: Find algorithm that get closest to the optimal solution within reasonable time ( ex $O(n^2)$)
As an approximation algorithm, I have tried the following greedy algorithm, but I would like a solution that gets closer to the optimal solution.
We will start with $S = \emptyset$ and add one element at a time to $S$.
Take $U = \{e_1,\ldots, e_m\}$. Rank each element using the following.
Define $H_{j,c}$ as number of sets $S_i$ such that $|S_i \setminus (S\cup \{e_j\}| = c$. i.e.
$$H_{i,j} = \sum_{i = 1}^n \mathbb{1}_{|S_i \setminus (S\cup \{e_j\}| = c} $$
Add that element $e_j$ to $S$ which has the maximum ordered value $(H_{j,1}, H_{j,2}, \ldots, H_{j, m})$ as per the lexigraphical ordering. (Use $H_{j,1}$ as the main score, and use $H_{j,2}$ as a tie breaker and so forth).
Repeat until $|S| = k$.
PS.

I think I did a poor job of explaining the problem and my attempt at the problem. I would appreciate any edits to make this question clearer.
I am trying to use this problem, as a greedy approach to my previous question Graph partition that maximize the number of triangles within its parts. But I think this question is interesting as well.

I'm not sure how well it'll work, but the idea is simple:

Consider a continuous relaxation of the function
Run projected gradient descent

1.) First, consider a discrete case: let $x_i$ be $1$ if we pick an $i$-th element, and $0$ otherwise. The constraint is $\sum_i x_i \le k$. For each set $S_j$, we want to write a function which is $1$ when all $i \in S_j$ are picked, and $0$ otherwise. A natural choice is $g(S_j, x) = \prod_{i \in S_j} x_i$. Our objective is $f(x) = \sum_j g(S_j, x)$
Now, to make it continuous, let $x_i$ vary in the range $[0,1]$ - in other words, it represents a probability that we pick the $i$-th element.
Now, $g(S_j, x)$ represents the probability that the set $S_j$ is chosen.
The constraint $\sum_i x_i \le k$ and the objective $f$ are as before.
Therefore, the continuous relaxation is the following:
\begin{align*}
    f(x) &= \sum_j \prod_{i \in S_j} x_i \to \max & s.t.\\
    x_i &\in [0,1] \ \ \forall i \\
    \sum_i x_i &\le k \\
\end{align*}
2.) The gradient has a relatively simple form:
$$(\nabla f(x))'_{x_i} = \sum_{j\colon i \in S_j} \prod_{i' \in S_j \setminus \{i\}} x_{i'}$$
In other words, it's a sum of over terms containing $x_i$: product of all factors except $x_i$.
Since the problem is constrained, you need to run  $projected$ gradient descent. I.e.
$$x^{(t+1)} \gets Proj(x^{(t)} - \gamma \nabla f(x^{(t)})),$$
where $Proj$ is a projection on the set $\{x | \sum_i x_i \le k \land x_i \in [0,1] \ \ \forall i\}$. It may be hard to find the exact projection, but you can use Alternating projection or, better, Dykstra's projection.
For that purpose, we rewrite our constraint set as
$$\{x| \sum_i x_i \le k\} \cap (\cap_i\{x| x_i \le 1\}) \cap (\cap_i\{x| x_i \ge 0\}).$$
Now, we can project at each set in turns. Note that projection on $\{x| x_i \le 1\}$ is trivial: when $x_i \le 1$, don't do anything, otherwise $x_i \gets 1$.
I'm not sure that the function is "good", and therefore I would try a smaller step size first. There are multiple optimizations that one can do, but I omit them here.


Speaking of "randomness" in computing terms, to what sense can any extant digital processor make "random" results? From a very strictly adhering sense to the hardware and circuit-level operations of any standard (non-specialized, DSPs, or supercomputing systems, etc.) microprocessor follow very similar, almost exact in some ways, operations.

The typical role of the (main) processor in a computer, integrated with other hardware circuits or not, and excluding DMA is to have a memory subsystem fetch byte(s) for it to "process" in whatever way. To have a processor "randomly" selective something can be abstracted and seen from a data algorithm HLL-type point of view, but on the circuit-level the operations can only get so complex. I know some Assembly of x86, so I can demonstrate further on the details of what I'm asking.

If you fetch a byte, or series of bytes, and then use some schematic to cycle through potential jump offsets, that is the only way to do randomness? Are their other ways?

Everything you can do in a high-level language can be done in assembly. After all, the high-level language is compiled to machine code.

What you seem to be describing is pseudorandom numbers, which are numbers generated by a computer using an algorithm, and look (computationally) random. It is also possible to generate "somewhat random" numbers by harvesting (say) thermal heat, or other "random" phenomena. The result won't quite be a sequence of i.i.d. fair coin tosses, but if you run it through an extractor it will look (computationally) pretty similar, and be theoretically unpredictable (since it's based on actual physical randomness).


Are all relational schemas with partial dependencies not in 3NF? From Database Management Systems, by Raghu Ramakrishnan, Johannes Gehrk

  Let  R be a  relation schema,  F  be the set of functional
  dependencies (FDs) given  to hold over  R ,  X  be a  subset of the
  attributes of R, and A be an attribute of R.  R is in third
  normal form if,  for  every FD  X -> A in  F,  one of the
  following  statements is  true:

  A  $\in$  X;  that is,  it is  a trivial FD, or
  X  is  a  superkey,  or
  A  is  part of some  key  for  R.

  Suppose that a  dependency  X -> A  causes  a  violation  of 3NF.
  There are two  cases:

  X  is  a proper subset of some  key K. Such a dependency is  called  a  partial dependency.
  X  is  not a  proper subset  of  any  key.  Such  a  dependency  is     called  a  transitive  dependency,  because  it  means  we
  have  a  chain  of dependencies  K->X-> A.

Am I correct that  "Figure 19.7 Case 1" and "Figure 19.8 Case 1" are
not 3NF, while "Figure 19.8 Case 2" is 3NF?
Why is there no either "Figure 19.7 Case 2: A in KEY" or "Figure
19.7 Case 2: A in KEY1" where "KEY1" is different from "KEY"?  Does that case exist?

Am I correct that

If that case can exist, it will be 3NF.
If that case can't exist, all relational schemas with partial dependencies are not in 3NF?

Thanks.

Premise: The figures depict functional dependencies, not relation schemas. It is improper to say that a functional dependency is or not in any normal form. So, I suppose that you are asking if the functional dependencies violate or not a normal form.
You say:

Suppose that a dependency  X -> A causes a violation of 3NF. There are two cases:
• X is a proper subset of some key K. Such a dependency is called a partial dependency.
• X is not a proper subset of any key. Such a dependency is called a transitive dependency, because it means we have a chain of dependencies  K->X-> A.

You have given one correct definition of 3NF a few lines above, and according to this definition the two cases are true only if A is not a prime attribute (that is, is not part of a key), otherwise the dependency does not violate the 3NF.
So the answer to the question which is title of your post: “Are all relational schemas with partial dependencies not in 3NF?” is NO.

Am I correct that "Figure 19.7 Case 1" and "Figure 19.8 Case 1" are not 3NF, while "Figure 19.8 Case 2" is 3NF?

Yes, if you mean that in these cases the dependencies do not violate the 3NF.

Why is there no either "Figure 19.7 Case 2: A in KEY" or "Figure 19.7 Case 2: A in KEY1" where "KEY1" is different from "KEY"? Does that case exist?

Yes, both cases could exists: in general in a relation scheme there can be multiple candidate keys (and possibly with empty intersection).

Am I correct that
If that case can exist, it will be 3NF.
If that case can't exist, all relational schemas with partial dependencies are not in 3NF?

Since both cases can exists, the relevant dependencies do not violate the 3NF, while it is incorrect the assertion that “all relational schemas with partial dependencies are not in 3NF” (if a partial dependency determines a prime attribute, than it does not violate the 3NF).


Show that the regular language is contained in another Let L1 and L2 be two non empty regular language. How can I show that the following expression is correct with an example ?
$\bigotimes$ denote the transducer cross product.

$L_1^+ \bigotimes L_2^+$ contains $(L_1 \bigotimes L_2)^+$

============================================================================

Thanks PHPNick. Would my version (rewritten from yours) be correct ? I am just trying to make it more explicit to verify my doubts. If my understanding of the cross product and the + operator is correct.

Let $L_1$ and $L_2$ be the following

$L_1 = \{u_1,u_2,u_3\} $ $L_2 = \{v_1,v_2,v_3\} $

Then $L_1^+$ and $L_2^+$ would be the set of all strings that can be made by concatenating finitely many (and at least one) strings (corrected by David Richerby)

$L_1^+ = \{u_1,u_1u_1,u_1u_1u_1,...,u_2,...,u_3,..., u_1u_2,u_1u_2u_1,\dots\} $

$L_2^+ = \{v_1,v_1v_1,v_1v_1v_1,...,v_2,...,v_3,..., v_1v_2,v_1v_2v_1,\dots\} $

The two sets defined in the question are thus

$L_1^+ \bigotimes L_2^+ = \{ (u_1,v_1), (u_1,v_1v_1), \dots, (u_1u_1,v_1), \dots, (u_1u_1,v_1v_1), \dots \}$
$(L_1 \bigotimes L_2)^+ = \{ (u_1,v_1), (u_1,v_2), (u_1,v_3), \dots, (u_2,v_1), \dots \}$

The set $L_1^+ \bigotimes L_2^+$ thus contains $(L_1 \bigotimes L_2)^+$ because we can see that $(u_1,v_1), (u_1,v_2)$ etc are present in $L_1^+ \bigotimes L_2^+$

It is just a simple subset proof:

Let $(u, v) \in (L_1 \otimes L_2)^+$. Thus, there is a decomposition of $(u, v)$ into $(u_1 \ldots u_k, v_1 \ldots v_k)$ with $u_i \in L_1$ and $v_i \in L_2$ and $k > 0$. Hence, we have $u \in L_1^+, v \in L_2^+$. So overall we have $(u, v) \in L_1^+ \otimes L_2^+$.


Are the capabilities of programming languages the same? Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could (theoretically) do the exact same thing with ever language, don't you?

The answer to the question depends on what you mean by "the same".

It is a famous result of computability theory that many reasonable models of computation all calculate the same nubmber-theoretic functions. That is, all reasonable general-purpose programming languages compute the same partial functions $\mathbb{N} \to \mathbb{N}$. So in this sense the capabilities of all programming languages are "the same". By the way, this is not the Church-Turing thesis, contrary to what you may be told.

However, a programming language can do many other things in addition to computing with numbers. For instance, it may access external devices, run parallel programs etc. While these features do not allow it to compute any extra number-theoretic functions, they may make a difference when it comes to computing other functions. For instance, a famous early example is that of the language PCF. It can simulate Turing machines, but it cannot compute the "parallel or" function, while its parallel variant PCF++ can.

When we look at higher-order functions languages differ in their capabilities. A purely functional language such as Haskell cannot compute the modulus of continuity but a functional language extended with local state can.

So it really depends on what you mean by "the same".


Grammar for a language: odd length, middle character not repeated Consider the following language over the alphabet $\mathcal{A} = \{a,b,c\}$:
$$L = \left\{w \in \mathcal{A}^* \mid \text{\(|w|\) is odd and the middle character in \(w\) occurs nowhere else in \(w\)} \right\}$$

I am trying to come up with a grammar for $L$, but I'm getting nowhere. I came up with some sample strings from the language which would be accepted: b, abcab, accbcaa
I understand the length of the string has to be odd, and the middle character cannot be repeated anywhere in the string.

Therefore, the above three strings are accepted. However, something like aabbb will not accepted, because even though the length is odd, the middle character is repeated.

Can someone help with a grammar for $L$?

Assume the middle character is $a$. Then a grammar is
$$A \rightarrow bAb | bAc | cAb | cAc | a$$
Similarly, we can define nonterminals $B$ and $C$ for the strings in our language where $b$ and $c$, respectively, are the middle symbols. Given those, you can get a grammar for your language by taking the union:
$$S \rightarrow A | B | C$$


Finding a local peak in an array in O(log N)? So I watched a couple of videos regarding this and the divide and conquer made sense to me. But I am still not convinced as to how recursing on the side with the larger number guarantees us the solution.

Please can someone explain it Mathematically.

No, it is not possible to find the max (peak) element in an unsorted array better than $\mathcal{O}(n)$.

When you executed your algorithm $\mathcal{A}$ that has $c \log n$ compare operations, that means; $\mathcal{A}$ only compared $c \log n$ elements. The remaining are not compared by $\mathcal{A}$.

We can easily construct an adversary argument for any $\mathcal{O}(\log n)$ algorithm by just placing the peak, within the elements for $\mathcal{A}$ didn't touch.


Asymptotic Proofs - BigOh/BigTheta This is not homework, but from a past exam. I do not know how to solve this one at all. Can anyone please take the time and show me how to do these? Thank you.

  Prove that $5^n \in O(6^n)$, but that $5^n \notin \Theta(6^n)$. (Doing this shows that $6^n$ bounds $5^n$ from above, but that $6^n$ is not the tightest such bound.)

I am familiar with the definitions, but it seems that $5^n$ is clearly $\lt 6^n$. and $5^n$ is not $\gt 6^n$.

Hint: Show that $$\lim_{n\to\infty} \frac{5^n}{6^n} = 0.$$


Minimum distance between two convex hulls maximized I want to implement a program that splits a set $S$ of $n$ points in the plane into two sets such that the distance of the convex hulls of the two sets is maximized.

It should be done in $O(n^3)$.

I have several ideas but I'm not sure whether they are correct:

I sort points by $X$ and then for each two points I find the distance but only if there's no any other point between them. Then I choose the closest point to the first one on the left and the closest point to the second one on the right (first point would be part of the first polygon and second one of the second polygon).

Then I find distance between point and line, line and line, line and
point and point and point(but I already know that). That's how i
find the maximal distance and then with Graham scan I create a
convex hull. I repeat everything for $Y$, because maximal distance
could be on $Y$, not on $X$.
I sort points by $X$ and then create a convex hull for first $3$ and another convex hull for other points. Then find a minimum distance between these two hulls. I save the distance and if it's greater than distance i saved before I overwrite it and remember polygons. And last step is when only $3$ points are left for the second convex hull. Then I do all these steps for $Y$.

What do you guys think about my ideas? Do you have any improvements or maybe another, better idea?

Given a pair of points $A,B$, you can split the the data into the points that are to the left of the line $AB$ (or on the line) vs the points that are strictly to the right of $AB$.  Then you can compute the convex hulls of these two sets and you can find the distance between the convex hulls in $O(n)$ time, for a particular split  (use a Graham scan; pre-sort the points once).  Since there are ${n \choose 2} = O(n^2)$ ways to choose $A,B$, this immediately gives a $O(n^3)$ time algorithm.

In fact, you don't need to compute both convex hulls.  It suffices to find the points that are closest (on each side) to the line $AB$.  It might be possible to do this faster than $O(n)$ time, which would improve the overall running time.  I think it suffices to compute a Voronoi diagram of all the points (a one-time $O(n \log n)$ time cost), then find all Voronoi cells that the line $AB$ goes through.  I don't know whether the worst-case complexity will be less than $O(n)$ but I bet in practice this will often lead to significant speedups.


Are space allocated to C/C++ variables in secondary storage also in Compiled file? Are data segments,heap,stack etc also present in secondary memory with compiled code then later mapped by OS to RAM when I open it?

Under most operating systems the binary executable and object files stored on disk contain three segments:

the .text segment (the code)
the .data segment stores the initial value for any global and static  variables that need to be initialized to specific values other than zero.
the .bss segment stores the global and static variables that don't need to be initialized, or are initialized to 0.  Typically only the size of the .bss segment is stored since the loader can easily create a segment in RAM of this size and fill it with zeros without wasting the time and disk space to store a bunch of redundant information in the executable stored on disk.

The wikipedia page https://en.wikipedia.org/wiki/Data_segment#Data gives some examples.

The stack and heap are typically not stored in the binary executable.  They are set up by the loader in RAM when the program is started.


Could be solved a NP-complete problem in constant time? Under the assumption that P would be equal to NP, it could exist a NP-complete problem that is solved in constant time?

Write down the definition of NP-complete. Then take your assumption that P = NP, so in the definition of NP-completeness you can replace "NP" with "P". Figure out which functions exactly are NP-complete. (Hint: There is a simple and obvious solution that is almost but not quite correct. Read the definition carefully). Do these functions contain any constant time solvable problems?

Each step is actually quite simple, you just have to follow all the definitions very precisely.


Verifying execution of code in trustless environment Let us assume I have a Program P running on remote computer generating output O. Without trusting the remote environment and not having to verify the output O, is there is a way to validate that Program P has indeed been executed and resulted in output O ?

Let me know if the question is too vague. I will clarify.

This is the problem of securely outsourcing computation.  There's lots of work on this problem in the cryptographic literature; if you do a search at [Crypto.SE] and [Security.SE], you should find some references.  Many of the schemes are probabilistic: if you the remote computer cheats, you have some chance of detecting that fact.  I know of two general approaches: one based on cryptographic commitments, and another based on SNARKs. You should be able to turn up papers on  how SNARKs work.


How hard is this constrained $n$-rooks problem? I asked this over on math.stackexchange.com, then I found out about this forum.

Suppose you have an $(n\times n)$-chessboard, together with a constraining function $C : n \times n \to 2$ where $C(i,j) = 1$ iff you're allowed to place a rook in the $ij$-square.  Consider the problem:

  Can $n$ non-attacking rooks be placed on the board in squares allowed by $C$?

Is it NP-Hard?

Here's an alternative formulation: Let $x_1, \dots, x_n$ be elements (integers, say) and $P_1, \dots, P_n$ unary predicates such that $P_ix_j$ can be evaluated in constant time.  Is there a permutation $\sigma \in S_n$ such that $P_ix_{\sigma(i)}$ for all $i$?

The equivalence can be seen by letting $C(i,j) = 1$ iff $P_i(x_j)$.  Then a placement of rooks yields a witness to the permutation problem by letting $\sigma(i) = j$ iff there's a rook in square $ij$.  $\sigma$ is a permutation because all $n$ rooks are placed in a non-attacking arrangement.  $P_ix_{\sigma(i)}$ holds because $\sigma(i)=j$ implies theres'a  rook in the $ij$ square, which implies $C(i,j) =1$, which, by definition, implies that $P_i(x_j)$.

This problem can be solved in polynomial time, using bipartite matching.

For a bipartite graph with $n$ vertices on the left, corresponding to the $n$ rows, and $n$ vertices on the right, corresponding to the $n$ columns.  Include an edge from $i$ to $j$ if $C(i,j)=1$, i.e., if you're allowed to place a rook in the $(i,j)$ square (in the $i$th row and $j$th column).  Now check whether there exists a perfect matching of this bipartite graph.  This can be done in polynomial time using standard algorithms.

Notice that there exists a perfect matching if and only if there exists a way to place the rooks so they are non-attacking.  Each edge in the matching corresponds to a place where a rook should be placed.  Two rooks can attack each other only if they share the same row or the same column.  A matching cannot have two edges that share the same left-vertex (same row) or same right-vertex (column), which means that any matching containing $n$ edges corresponds to a way to place $n$ rooks so they don't attack each other.


When does $p$ break the pumping lemma I want to prove that $\{A^iB^jC^k \mid i=j \text{ or } j=k\}$ is a not a regular language using the pumping lemma.

I've found that the only way to obtain a contradiction is when $x \in A^*$, $y \in B^*$, $z \in C^*$,
 as $y$ is unable to be pumped up and still fit in the language. However if I have any combination of
 $y \in B^*C^*$ or $y \in A^*B^*$ and either $x$ or $z$ is empty,
 it appears as if $y$ can be pumped and thus this would be a regular language. The only way I can think that this would violate the rules of pumping lemma is if $|xy| ≤ P$. Assuming that $P$ is $2$ (which may be completely wrong), then the above still wouldn't violate the pumping lemma and thus this would be a regular language, right?

Let's start with stating the pumping lemma, in its contrapositive form:

  Suppose that $L$ is a language such that for all $p>0$, the following holds. There exists a word $w \in L$ of length at least $p$ such that for every decomposition $w=xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$, there exists $t \geq 0$ such that $xy^tz \notin L$. Then $L$ is not regular.

Now let us prove that your language is not regular. Given $p > 0$, let $w = a^pb^p \in L$, which certainly has length at least $p$. Given a decomposition $w = xyz$ with $|xy| \leq p$ and $y \neq \epsilon$, we see that $y = a^i$ for some $i \neq 0$. Therefore $xy^0z = a^{p-i}b^p \notin L$. Hence the pumping lemma applies, and shows that $L$ is not regular.


Proving a language comprised of 2 languages is regular So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.

The question:
$L_1$ and $L_2$ are regular languages over the same $\Sigma$. prove that the following language is regular as well:

$L^\frown \:=\left\{\:w\:\in L_1 | \:w=\sigma _1\mu _1\xi _1\sigma \:_2\mu \:_2\xi \:_2...\sigma \:_n\mu \:_n\xi \:_n\right\}$ Where $n \geq 0$, for every i:$\left(1\:\le i\:\le n:\:\sigma _i\mu _i\xi _i\:\in \Sigma \right)$, $\mu_1\mu_2...\mu_n \in L_2$.

Prove using:
1)Closure properties.
2)Building an multipication automaton

My try:

1)I do not understand how to define the homomorphism from which I can deduct using closure properties that the given language is indeed regular.

2)Since both $L_1$ and $L_2$ are regular, There exist two deterministic finite automatas that can accept them: $A^i\:=\:\left(\Sigma ,\:Q^i,q_0^i,F^i,\delta ^i\right)$ ($i\:\in \left\{\:1,2\right\})$. So, let L be the automaton that accepts those two languages: let L be $L\:=\:\left(\Sigma \:,\:Q^1\:X\:Q^2,\left(q_0^1,q_0^2\right),F^1X\:F^2,\delta \:\right)$. However, here I don't know what its transition function should be

Would really appreciate your help with it, if possible with explanations to understand so I'll be able to overcome similar questions in the future.

Thank you so much!

Proof using closure properties

Let $add\colon \Sigma \to \Sigma^*$ be a regular substitution that maps $\mu \in \Sigma$ to $\{ \sigma \mu \xi : \sigma, \xi \in \Sigma \}$ (the image is regular since it is finite). Then your language is $L_1 \cap add(L_2)$.

Proof using product automaton

Let $(\Sigma, Q^i, q_0^i, F^i, \delta^i)$ be automata accepting $L_i$ (for $i = 1,2$). We construct a new automaton $(\Sigma, Q, q_0, F, \delta)$ where:

$Q = Q^1 \times Q^2 \times \{1,2,3\}$.
$q_0 = (q_0^1,q_0^2,1)$.
$F = F_1 \times F_2 \times \{1\}$.
$\delta((q^1,q^2,1),\sigma) = (\delta^1(q^1,\sigma),q^2,2)$.
$\delta((q^1,q^2,2),\sigma) = (\delta^1(q^1,\sigma),\delta^2(q^2,\sigma),3)$.
$\delta((q^1,q^2,3),\sigma) = (\delta^1(q^1,\sigma),q^2,1)$.

The product automaton keeps track of the state in both automata, as well as the location within the triple $\sigma_i \mu_i \xi_i$ (this is the purpose of the third argument).


Maximal minimal DFA for some language of n-bit strings Notation: $M$ is a DFA; $L(M)$ is the language accepted by $M$; $\min(M)$ is the minimal automaton equivalent to $M$ derived from a minimization algorithm such as the Hopcroft algorithm; and $|M|$ is the size of $M$: the number of states in $M$.
We are given the alphabet $\{0,1\}$ and some $n \in \mathbb{N}$.
Let's define some sets to set up the question.
$$ A = \{M \mid L(M) \subseteq \{0,1\}^n\}$$
So $A$ is the set of all automata that accept some language whose words are composed of $n$-bit binary strings. My intention here is also to require that all members of $A$ reject strings of other lengths. Building from this, consider
$$ A_{\min} = \{ \min(M) \mid M \in A \}  $$
So $A_{\min}$ is the set of all minimized automata from $A$. Building further, let
$$ x = \max \{ |M| \mid M \in A_{\min}\} $$
So $x$ is the size of the largest automaton from $A_{\min}$. Now we can specify the automaton or automata we're looking for:
$$S = \{ M \mid M \in A_{\min} \, \, \text{and} \, \, |M| = x  \} $$
How would one go about constructing a member (or members) of $S$? Any will do, but simpler constructions are preferred.
My initial naive attempt to do this failed. I tried building it up by induction, starting from a basis state which had two states: an accepting state and a non-accepting state. For the inductive step, I tried to build a binary tree composed of two different subtrees built from the previous step. This failed because minimization still merged common subtrees together.

Your question is solved in Cezar Câmpeanu and Wing Hong Ho, The Maximum State Complexity for Finite Languages, Corollary 10.


Finding Feature Representation Such That Two Samples Are Similar in Feature Space Consider one specific useful function of our human brain: abstraction of object. Take the example of two pictures: if we are told the pictures are similar, we actually make conclusion about the aspects in which they are close to each other.

I'm considering whether machine can have the ability described. More accurately, is it possible to find and select a set of feature representations of two samples (e.g. image, sound) such that under those representations, the samples are similar with respect to a metric, say weighted euclidean norm?

I think you're looking for metric learning or Manifold learning. At a very high level, the idea behind both of these approaches is to learn the space (or transform) over which a set of (labeled) examples are close to one another.


Is there an example of a recursive language which is not context sensitive? I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for context free languages and $a^nb^nc^n$ for context sensitive languages. I usually consider the language which is accepted by a universal Turing machine (UTM) as prototypical of recursively enumerable. However for the the recursive languages I don't have one. I used to think that $\{1^p | p \text { is prime}\}$ was recursive but verifying a number is prime can be done by a bounded Turing machine. I also had $\{1^{2^{n}}\}$ but again verifying this can be done by a bounded Turing machine.

On the other hand, the other options I have found are computing Turing machines that requiere that the output of the computation to be store somewhere in the machine, however the output is no part of the accepted language which makes every of those language regular or context free so far. For instance the machine that sums two numbers represented by 1s and separated by a space, and puts the result after. In this case, the accepted language is actually $1^*B1^*$ which is regular! If we try to do it like verification if become context free $1^nB1^mB1^{n+m}$ but no recursive!

So is it possible to talk about a recursive language which it might be regular in essence but since it is conditioned to do the computation and put a result in the output as a kind of recursive language? Those definitely can not be done in a bounded Turing machine.

Here's a more formal proof, by the standard trick of diagonalization
(it must be folklore, but I saw it recently here)

Let $G_1, G_2, ...$ be some enumeration of context sensitive grammars (convince yourself that there are only countable many of them; Why can they be enumerated?),

Let $x_1, x_2, \ldots,$ be enumeration of $\Sigma^*$ (i.e., $x_1=\epsilon$, $x_2=0$, $x_3=1$, $x_4=00$, etc. in the case of binary alphabet).

Consider the language:

$$L = \{ x_i \mid x_i \notin L(G_i)\}.$$

Claim 1 $L$ is not context sensitive: if it was, there was a specific $G_j$ generating it, but $x_j\in L$ while $x_j \notin G_j$.

Claim 2 $L$ is decidable: given $x_i$ we just check if $G_i$ generates it (this problem is known to be PSPACE complete, thus decidable).


Amortized analysis of base Fibonacci counter We just started learning the potential method this week and I'm having a bit of trouble on this problem regarding Fibonacci numbers; specifically I'm having some difficulty thinking of a good potential function.

Suppose instead of powers of two, we represent integers as the sum of Fibonacci numbers. In other words, instead of an array of bits, we keep an array of fits, where the $i$th least significant
fit indicates whether the sum includes the $i$th Fibonacci number $F_i$. For example, the fitstring 101110 represents the number F6 + F4 + F3 + F2 = 8 + 3 + 2 + 1 = 14.

a. Describe an algorithm for an increment operation.

b. Show that a sequence of $n$ operations is amortized $O(n)$ using the potential method.

c. Do the same thing above, but now add a decrement operation.

This is what I started out with:

The general rule is to never let two consecutive Fibonacci numbers exist in the counter at the same time. In other words, no two 1's can occur consecutively. This is because of the definition of Fibonnaci numbers, i.e. a number such as 011 can be replaced by 100.

In general, when incrementing, change the least significant bit that's a 0 to 1 (this is one of the two "1" representations that are the first two bits in the counter). Starting from the most significant bit, if some positions $i$ and $i-1$ have 1's, then change them to 0's and change position $i+1$ to a 1. Keep recursing until there are no more consecutive 1's.

Now we will use the potential method to show that the amortized cost of $n$ consecutive increment operations is $O(n)$.

We will define our potential method as follow: (this is one part I'm having trouble with)

I then made the following observation:
Suppose the $i-th$ operation makes $x_i$ Fibonnaci conversions (changing consecutive 1's to 0's and changing the next significant bit to a 1). Then the actual cost is $1 + 3x_i$.

Any help is appreciated! Thanks!

As far as I know, there's no general method for designing a potential function, which makes sense when you consider that they can be used for different purposes. I've been trying on and off for 20 years, and to this day, I have no idea how Sleator and Tarjan came up with the function they used to prove the optimality (with respect to an arbitrary PDF) of splay trees.

Having said that, it often helps to work backwards. I'm going to show you what I mean for the algorithm for incrementing binary numbers. This should give you some ideas about how to proceed.

Let's start by simply checking the number of bit-flips required to increment numbers, starting with zero:

+--------------+---------+
| Bit sequence | # flips |
+--------------+---------+
|            1 |       1 |
|           10 |       2 |
|           11 |       1 |
|          100 |       3 |
|          101 |       1 |
|          110 |       2 |
|          111 |       1 |
|         1000 |       4 |
|         1001 |       1 |
|         1010 |       2 |
+--------------+---------+

So that's the ruler function, which you may recognise as being the solution to the Tower of Hanoi problem. It satisfies the recurrence:

$$a(2n) = 1$$
$$a(2n+1) = 1 + a(n)$$

But that's neither here nor there. What's interesting is that as you go on, the average number of flips per increment seems to trend towards 2; you can write a little program yourself to verify this, or you can note that half the increments flip one bit, a quarter flip two bits, and in general $\frac{1}{2^i}$ of them flip $i$ bits for $i>0$. Do the sum yourself.

So we need to design a potential function so that each increment "costs" two flips. If the increment only flips one bit, we want to put another flip in the bank, as it were, so we can withdraw it later. If the increment flips two bits, we want the potential function to be the same, and so on.

Recall that for an operation which transform the state $S_b$ into the state $S_e$:

$$T_{\hbox{amortised}}(S_b \rightarrow S_e) = T_{\hbox{actual}}(S_b \rightarrow S_e) + \Phi(S_e) - \Phi(S_b)$$

In our case, we want all increments to have their amortised time to be at most 2. So:

$$2 \ge T_{\hbox{actual}}(0 \rightarrow 1) + \Phi(1) - \Phi(0) = 1 + \Phi(1) - \Phi(0)$$
$$2 \ge T_{\hbox{actual}}(1 \rightarrow 10) + \Phi(10) - \Phi(1) = 2 + \Phi(10) - \Phi(1)$$
$$2 \ge T_{\hbox{actual}}(10 \rightarrow 11) + \Phi(11) - \Phi(10) = 1 + \Phi(11) - \Phi(10)$$

And so on. This gets us somewhere, because it gives us some bounds on what the potential function might be.

There are a number of potential functions which could satisfy these constraints. In this case, however, there's a straightforward optimal solution. Setting $\Phi(0) = 0$ and making the inequalities equalities gives us the potential function:

$$\Phi(0) = 0$$
$$\Phi(1) = 1$$
$$\Phi(10) = 1$$
$$\Phi(11) = 2$$
$$\Phi(100) = 1$$

There's no obvious pattern so far, but if you extend this on, you'll find that $\Phi(S)$ is the number of 1's in $S$ (i.e. the Hamming weight of $S$). This makes intuitive sense, when you think about it: Incrementing a zero takes only one flip, but incrementing a one takes more than one. So the number of ones in the string is a measure of how "hard" it will be to increment it in the future. It's a reasonable analogue of "potential energy".

Now that we've identified a candidate potential function, we can now work forward again to try to prove the result.


undecidability of virus detection I have been reading the following document about the undecidability of virus detection, available at:

https://enterprise.comodo.com/whitepaper/Impossibility_of_Virus_Detection_WP.pdf

the problem that I have is in the following part:

The part that I do not understand is the one that says:

Halts(P)=not(DetectVirus(MakeVirus(P)))

Because for what I read if P behaves like a virus, which is made by the function MakeVirus(P), then I suppose that DetecVirus() will detect it and because of that this program will halt. So I will end up with:

Halts(P)=(DetectVirus(MakeVirus(P)))=true

but why do they negate that term? is it because P is a virus, but DetectVirus failed to detect it, so their answer instead of being true is false because of:

Halts(P)=not(DetectVirus(MakeVirus(P)))= not(DetectVirus(MakeVirus(P)=returns virus)=false)=true

I am assuming that P is a virus, but DetectVirus() returns false because it failed to detect it; then the negation of this would be a true value, so in this case Halts(p) will also halt the program.

Could somebody explain me what am I doing wrong?

Thanks

Abstracting away the details of their argument, what they're saying is basically:

  Suppose we have a Turing machine DoesItZork(P) that takes a program P and decides whether it zorks or not. Now we can build a Turing machine RunThenZork(P) = P() then Zork() which first runs its input, then zorks. Now, if DoesItZork(RunThenZork(P)) returns True (and P itself does not zork), then P must halt on the empty input. On the other hand, if it returns False, then P must not halt on the empty input. So we just invert the output: DoesItHalt(P) = not DoesItZork(RunThenZork(P)). So if we have a way to ensure that P never zorks on its own (which we do), then having DoesItZork gives us a solution to the Halting Problem. We know that there is no solution to the Halting Problem, therefore, there can be no DoesItZork.

As a matter of fact, this proof skips over some important details. For one, Turing machines have no concept of files, so there needs to be some mapping between Turing machines and actual computer programs. (Fortunately, such a thing does exist.)

In addition, there's an easier way to prove this, once you allow for the idea that a Turing machine can be a virus. Rice's Theorem effectively says that all non-trivial semantic properties of a program are undecidable, where a property is trivial if all Turing machines have it or no Turing machines have it, and a property is semantic if it has to do with the program's behavior rather than its encoding. Since there exist programs that are viruses, and programs that are not viruses, and viruses are defined by their behavior, it's undecidable which are which.


Efficient algorithms for finding a region in $\mathbf R^2$ This question is an extension of a previous question I've asked.

Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 (We have to check each point to know its kind).

Assume that somehow we know that the points of kind 1 (and so the points of kind 2) form a connected region (i.e. , 1s and 2s are not scattered in the plane arbitrarily). Given the condition of being of kind 1 or 2, The goal is to find the region occupied by 1s (a search problem). Consider somehow we know the following attributes of the region occupied by 1s: (one at a time)

The region occupied by 1s forms a convex set (so it is 1-connected too).

2.The region occupied by 1s forms a simply connected region , but not necessarily convex.

The simplest algorithm for finding the region of 1s is to simply start from bottom of the rectangle and sweep it and check all of the points in the rectangle to determine their kind and this way find the region.This is not an efficient algorithm, because we can use the known fact of convexity (or simply-connectivity) of the region of 1s to find it more easily without inspecting all of the points.

What more efficient algorithms are there to find the region , as fast as possible? (with an acceptable accuracy, which is about 0.001 in my work). The regions may have sharp edges. But their detection is limited to the mentioned accuracy too. (It is clear that finding the boundary of the region suffices)

Please don't forget that the problem is to find an unknown set of points, not bound a known set of points. i.e., it's a search problem , not a convex hull finding problem.

(also, speed is very important for me)

EDIT1:

After some suggestions (in the comments) I should say that I think we can take advantage of simply-connectivity of the region to write an algorithm that tries to find the boundary of the region instead of checking more points to find the region directly.

Here's an idea that might be quick in practice. Judging from the OP's comments, this is idea is implementable.

The idea is that we start scanning from a corner and approach the center of the rectangle. Once the scan finds a vertex $v$ with label $1$, it halts. Start a DFS from $v$. Keep a stack $F$ that represents the frontier into which you can expand the search. A vertex is put into the stack if and only if it has at least one neighbor whose label is $0$. The idea is to complete a cycle, while staying on the boundary.

The figure above is a rough representation of the initial region of the green vertices labeled $1$. Say we start scanning from the upper right corner. The vertex $29$ is the one we hit, and the one from which we start a DFS.

The DFS was started from the purple vertex $29$. In the figure, $F$ would contain $9$ and $28$, because they are the only neighbors we can visit next that have at least one neighbor with the label $0$. The cycle is completed when we come back to $29$ or when the frontier meets.


Pumping lemma for $\{110^n10^{n-m}1^m: 1\le m<n\}$ How can I prove that the language $L=\{110^n 10^{n-m} 1^m \mid 1 \le m < n \}$ is not regular using pumping lemma?

I chose the word $w = 110^{2p} 10^{2p-q} 1^q$ to prove the non-regularity.
Then I started partitioning the word to $xyz$ with $|y| \ge 1$, $|xy| \le p$ and for each $i\ge 0$, $xy^iz$:

\begin{align*}
x &= 110^r\\
y &= 0^s\\
z &= 10^{2p - q} 1^q\,,
\end{align*}
where $r + s = p$
and $s > 0$.

The second partition:
\begin{align*}
x &= 1\\
y &= 10^{2p}\\
z &= 10^{2p-q}1^q\,.
\end{align*}

However, I got stuck at this point because I am not really sure how to find the other partitions and how the choose the correct $i$ for those which I already have.
Any help with this will be appreciated.

You're basically there.  Taking $w=110^{2p}10^{2p−q}1^q$, there are actually three cases (you missed the first one).

$x=\varepsilon$, $y=110^{p-2}$, $z=0^{p+2}10^{2p-q}1^q$.
$x=1$, $y=10^{p-1}$, $z=0^{p+1}10^{2p-q}1^q$.
$x=110^r$ for some $r\in\{0, \dots, p-3\}$, $y=0^{p-r-2}$, $z=0^{p+r+2}10^{2p-q}1^q$.

In all three cases, taking $i=0$ means that the string $xy^iz$ is not in $L$.  I'd suggest trying $i=0$ and $i=2$ as your first two guesses in pumping lemma proofs – one of them usually works.

Notice that nothing above actually depends on the choice of $q$, so you can simplify things very slightly by just taking $q=1$ (or any other fixed, legal value).


Is the k-clique problem NP-complete? In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete:

  Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

But in this other Wikipedia article about the Clique problem in CS
 it says it is solving the problem for a fixed size k is a problem in P, it can be brute forced in polynomial time.

  A brute force algorithm to test whether a graph G contains a k-vertex clique, and to find any such clique that it contains, is to examine each subgraph with at least k vertices and check to see whether it forms a clique. This algorithm takes time O(n^k k^2): there are O(n^k) subgraphs to check, each of which has O(k^2) edges whose presence in G needs to be checked. Thus, the problem may be solved in polynomial time whenever k is a fixed constant. When k is part of the input to the problem, however, the time is exponential.

Is there something I am missing here? Maybe a difference in the wording of the problem? And what does the last sentence mean, that "When k is part of the input to the problem, however, the time is exponential."? Why is there a difference when the k is part of the input to the problem?

My idea is that to find a clique of size k in a graph G, is that we first choose a subset of size k of nodes from G, and test wether they are all related to the other k nodes, which can be done in constant time. And repeat this until we have a clique of size k. The number of sets of k nodes we can choose from G is n! / k!*(n-k)!.

Just elaborating what @Lamine pointed out : When $k$ is part of the input, $k$ can be as large as $\frac{n}{2}$, in which case the number of potential clique sets are $\binom{n}{\frac{n}{2}}$ which is at least $\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$. Hence your naive algorithm would take time $2^{\frac{n}{2}}$ which is clearly exponential in input length $|x|+|k|=n+\log n$. The parameterized version $G(n,k)$ where we are looking for $k$-cliques in an $n$-vertex graph captures the hardness of the problem in its most generalized form because $k$ is part of the input. Hence a poly-time algorithm for $G(n,k)$ would also imply a poly-time algorithm for any specific $k$.


Sublinear Homomorphism Property Testing Counter Example This is a homework question, so I'm not looking for answers, just general guidance.

I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of homomorphisms from $\left(\mathbb{Z}_{n}, +\right)$ to $\left(\mathbb{Z}_{n}, +\right)$ (where + is the modulo addition) in particular.

Since $$f:\mathbb{Z}_{n}\to\mathbb{Z}_{n}\ is\ a\ homomorphism\iff\forall x\in\mathbb{Z}_{n}:\ f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$$
(I've managed to prove that), it is suggested to property test $f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$.

To counter that suggestion it is said that for a sufficiently large $n$, $$f:\begin{array}{lll}
\mathbb{Z}_{n} & \to & \mathbb{Z}_{n}\\
x & \mapsto & x\ \left(mod\ \left\lceil \sqrt{n}\right\rceil \right)
\end{array}$$ maintains $f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$ for $1-\frac{1}{\sqrt{n}}$ fraction of the $x\in\mathbb{Z}_{n}$ (managed to prove that), but that $f$ is $1-\frac{1}{\sqrt{n}}$-far from any homomorphism (where $\epsilon$-far means that in order to get a homomorphism out of $f$ we have to change at least $\epsilon n$ outputs of $f$).

We're asked to show a counter example of a function that passes the test for $1-o\left(1\right)$ fraction of the inputs, but is $\frac{1}{100}$-far from homomorphisms, which is a bit easier.

So I wanted to show $f$ as my example. I managed to prove what I wrote so far, but I'm still trying to prove $f$ is $1-\frac{1}{\sqrt{n}}$-far.

What I've tried:

Assume by contradiction that $\delta\left(f\right)<n-\sqrt{n}$ (where $\delta\left(f\right)$ is the distance from homomorphisms), that is there exists $h$, an homomorphism, with less than $n-\sqrt{n}$ different (compared to $f$) outputs.

I've divided into 2 cases.

First case is $h\left(1\right)=f\left(1\right)$ which means $h\left(1\right)=1$. It is easy to get a contradiction this way, since then there exists $x>\sqrt{n}$ such that $h\left(x\right)=f\left(x\right)$ (otherwise, contradiction to $\delta\left(f\right)<n-\sqrt{n}$). Since $h$ is a homomorphism, we get $$h\left(x\right)=\underset{i=1}{\overset{x}{\sum}}h\left(1\right)=\underset{i=1}{\overset{x}{\sum}}1=x\neq f\left(x\right)$$

Now the other case where $h\left(1\right)\neq f\left(1\right)$ is where I'm stuck. It's hard for me to get intuition since apparently this is only true for large $n$'s, which makes it hard to look at basic examples. I'm not even sure dividing to these cases is the best approach, and would love some help. Thanks!

Edit:

As requested, a link to the survey by Ronitt Rubinfeld.
Only managed to find it in ps format.

Thanks to the help in the comments I was able to unfixate and find an answer to the question. I prove $\delta\left(f\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$.

Let $h:\mathbb{Z}_{n}\to\mathbb{Z}_{n}$ be an homomorphism.

• If $h\left(1\right)=f\left(1\right)$ then $h\left(1\right)=1$ and h is the identity function, since $h\left(0\right)=0$ and $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ due to homomorphisms definition and properties. We get $\delta\left(f,h\right)=1-\frac{1}{\sqrt{n}}\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$ (since they disagree on $n-\sqrt{n}$ values).

• Otherwise, $h\left(1\right)\neq f\left(1\right)$, that is $h\left(1\right)\neq1$. Assume by contradiction that exists $x\in\mathbb{Z}_{n}$ such that $h\left(x+1\right)=h\left(x\right)+1$, but due to homomorphisms definition we get $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ which is a contradiction to $h\left(1\right)\neq1$. Since our function $f$ maintains that $$h\left(x+1\right)=h\left(x\right)+1$$ for $x\in\mathbb{Z}_{n}\backslash\left\{ q\sqrt{n}|0\leq q\leq\sqrt{n}-1\right\}$ , which means $n-\sqrt{n}$ “bad” pairs of $x$ and $x+1$. This means that in order to get any homomorphism, including $h$, we have to change at least one value for each pair, which means at least $\frac{\sqrt{n}-1}{2}$ values changed for each interval $\left[q\sqrt{n},\left(q+1\right)\sqrt{n}\right)\cap\mathbb{Z}_{n}$ (where $0\leq q\leq\sqrt{n}-1$), otherwise due to to the pigeonhole principle we have two consecutive values that are unchanged which is again a contradiction since then $h\left(x+1\right)=h\left(x\right)+1$. So in total we have at least $$\sqrt{n}\frac{\sqrt{n}-1}{2}=\frac{n-\sqrt{n}}{2}$$ values changed, which means $$\delta\left(f,h\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$$


Is O(n log n) exponential speedup over O(n^2)? I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?

$O(n \log n)$ is a polynomial speedup over $O(n^2)$, in particular almost a quadratic speedup. $O(n \log n)$ is big-O of $O(n^k$) for all $k > 1$. Its runtime is therefore between linear and any powerfunction whose exponent is strictly greater than 1.

Let $f(n)=n \log n$. Raise it to a power of some value slightly less than 2 to approximate the original runtime. We conclude $f(n) \approx n^{2-\varepsilon} (\log n)^{2-\varepsilon}$ and in $O(n^2)$. If we square $f(n)$, we have $n^2 (\log n)^2$, slightly less efficient than the original $n^2$, hence it is basically a quadratic speedup.

Instead, $O(\log n^2) = O(\log n)$ is an exponential speedup over $O(n^2)$. If $g(n) = 2\log(n)$, then $e^{g(n)} = n^2$.


What is an instruction bus? I understand how the control, data and instruction buses form the system bus in von Neumann architecture but in the context of Harvard architecture, my textbook refers to "parallel data and instruction buses". The Wikipedia article for Harvard architecture also refers to an instruction bus: "TMS320 C55x processors, for one example, feature multiple parallel data buses (two write, three read) and one instruction bus."

What is an instruction bus? Based on its name, I'd guess it allows the processor to send instructions to components but in that case, how does it differ from a control bus?

I believe you have one bus too many. Taking the image from teach-ict.com:

The diagram shows two buses with memory and one internal bus. One memory bus fetches instructions (stored in memory) to the Control Unit and data (stored in the same memory) to the ALU. The second bus is the Address Bus which says which memory to read or write (both for instructinos and data).

The Control Unit decodes the instruction and tells the ALU what to do (add, subtract, divide...). The Control Unit and the ALU together are called the CPU.

There is no separate Control Bus with the memory. The Control "Bus" is internal in the CPU.

In the Harvard Architecture there is physically separate memory for instructions and data. It means there are 4 buses, 2 data buses (1 for instructions and 1 for data) and two address buses (1 to address the instruction memory and 1 to address the data memory). The "Control Unit" in the diagram is the combined Control Unit and ALU from the previous diagram, the CPU. Any Conrol "Bus" is internal to that unit.

To summarize the answer: a Control Bus is internal to the CPU and should not be considered in discussing interactions with memory. There is no Control Bus with memory.

(Note: The Input and Output shown in the Von Neumann diagram should be ignored, or should be considered also present in the Harvard Architecture.)


3-sat to 2-sat reduction It is known that 3-SAT belong to - NP-Complete complexity problems, while 2-SAT belong to P as there is known polynomial solution to it.

So you can state that there is no such reduction from 3-SAT to 2-SAT unless $P=NP$.

I am looking for strong proof for this state, regardless NP belong to P or not.

You can prove it by contradiction:

Suppose that $P \neq NP$ and there is a polynomial-time reduction from 3-SAT to 2-SAT; then 2-SAT is NP-complete, but 2-SAT is also solvable in polynomial time, so
for all decision problems $A \in NP$ you can decide $x \in A$ reducing $x$ to the corresponding 2-SAT instance in polynomial time and solve it in polynomial time (and the total time is still polynomial); so $A \in P$ and hence $NP \subseteq P$. But we also have $P \subseteq NP$, so $P = NP$ which is a contradiction. :-)


Decision problems whose verifier is NP We define $\mathbf P$ as the set of problems solvable in polynomial time. We define $\mathbf{NP}$ as the set of problems with a verifier $ \in \mathbf P$.

Is there a name for problems whose verifiers are $\in \mathbf {NP}$ (e.g., $\mathbf{N(NP)}$)? I can't see this being a very useful complexity class, but, for example we have that $\mathbf{NP} \neq \mathbf{N(NP)} \implies \mathbf{P} \neq \mathbf{NP}$, so it might be an area of research for that reason alone.

Suppose you had a problem such that for any $x \in L$, there was a verifier $v$ such that $v$ could be checked against $x$ by a nondeterministic polynomial time algorithm. For a valid $(x, v)$ pair, there is some verifier $v'$ such that it takes polynomial time to check $((x, v), v')$ is a correct verification.

But then, you could simply combine $(v, v')$ into a single witness, and run the check in deterministic polynomial time.

Thus, the class ${\bf N(NP)}$ you describe is really just equal to ${\bf NP}$.


primitive recursion on untyped lambda calculus Does a definition of primitive recursion exist for the untyped lambda calculus? Does the definition of primitive recursion require typing for natural numbers?

The only definitions I can find are for the typed lambda calculus: http://www.math.nagoya-u.ac.jp/~garrigue/lecture/2013_tenbo/recfun_en.pdf. Perhaps if I just ignore the types it will still be valid?

Famously, the fixed-point operator $Y$ of the untyped $\lambda$-calculus, which has the property that
$$ Y\ F=_{\beta}F\ (Y\ F)$$
for every term $F$, is enough to implement primitive (and indeed, non-primitive!) recursion.

Given any encoding of the natural numbers which allows decrementing, if you have an expression
$$ e(n)=C[e(n-1)]$$
where $C$ is some programatic context, you can create a term, $P_e$, defined by:
$$ P_e\equiv\lambda F\ n.C[F\ (n-1)] $$

Now it's easy to show that
$$(Y\ P_e)\ n = P_e\ (Y\ P_e)\ n= C[(Y\ P_e)\ (n-1)]$$
and so it makes sense to define the function $e$ as $Y\ P_e$.


Why is $BPP$ closed under complement? Why is $\text{BPP}=\text{co-BPP}$?
I tried to find a proof online but couldn't.
Can anyone please provide a quick explanation (if it's trivial and I just can't see it) or a link to a proof?

It follows directly from the definition of BPP.

The definition says that a problem with a yes-or-no answer is in BPP if there is a randomized algorithm that gets the correct answer with probability $\ge 2/3$ on all possible instances.  This means that on all instances where the correct answer is YES, the algorithm has to output YES with probability at least $2/3$; and on all instances where the correct answer is NO, the algorithm has to output NO with probability at least $2/3$.

Therefore, if a problem $P$ is in BPP, its negation is also in BPP.  Take the algorithm for $P$, and just flip its output.  That will be a valid algorithm for the negation of the problem.


Difference between consensus number n and consensus number infinite In book Concurrent Programming: Algorithms, Principles, and Foundations of Michel Raynal, in Section 16.5.1, Theorem 75 says

  Compare&swap objects have infinite consensus number.

and in Section 16.5.2, Lemma 40 says

  The mem-to-mem-swap object type has consensus number n in a system of n processes.

Then, in Section 16.1, author puts in table both Compare&swap and men-to-mem-swap as objects with consensus number infinite.

So, what is the difference between objects with consensus number n and objects with consensus number infinite?

The consensus number of an object is the maximum number of concurrent processes that you can synchronize with one such object in a wait-free manner (I won't go into what wait-free means here). For example, a register with only read and write operations doesn't help with wait-free synchronization at all, so it has consensus number 1. A register with a test-and-set operation can be used to synchronize two processes in a wait-free manner, but not three or more, so the consensus number of test-and-set is 2.

$n$-register assignment, where a process can atomically write to multiple registers, allows up to $2n-2$ processes to synchronize wait-free if there are $n$ registers. More processes require more registers. Therefore the consensus number of an objet consisting of $n$ registers that can be assigned atomically is $2n-2$.

A single register with a compare-and-swap operation is sufficient to synchronize any number of processes wait-free. Therefore the consensus number of compare-and-swap is infinite.

Lemma 40 states that a mem-and-swap object allows the wait-free synchronization of all the processes in a system of $n$ concurrent processes, for any number $n$. This means that for any number $n$, the consensus number of mem-and-swap is at least $n$. (Stating that the consensus number is $n$ in a system of $n$ processes is a bit of a misnomer since the definition of the consensus number doesn't actually depend on the total number of processes.) Since consensus number of mem-and-swap is at least $n$ for any $n$, it's infinite.

If you prefer another source than Raynal's book, you can read the original paper by Maurice Herlihy.


Is CYK still relevant today? I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today.

Is it or an extension of it still being used in compilers (for example), or have other algorithms proven to be better?

CYK is still relevant, afaik, as the simplest example of a family of general
parsing algorithm based on dynamic programming, ranging over all
parsing technique (that I know of) and many syntactic formalisms. There is a simpler
general parsing algorithm (below), but where the dynamic programming (DP)
aspect is no longer visible. as things are defined more globally.

What I mean by general parsing algorithm, is a parsing algorithm that
can parse all memeber of a family of languages, according to their
given grammar, and produce all the possible parse structures when the
parsed string is ambiguous, combined in a condensed form called a
(shared-)parse-forest. Though this is often considered only for
context-free (CF) grammars, it does generalize to other formalisms.

Most known such algorithms are for CF grammars: such as CYK, Earley,
GLR, GLL with diverse variants. They are also known as chart parsers,
and extend beyond formal languages to some logical formalisms, often introduced by computational linguists via so-called feature structures. They can all be seen as extensions or refinement of CYK, though that is often a subjective assessment. They can also be seen as extensions or refinement of the more basic algorithm presented below.

My experience (but new research might prove me wrong) is that the DP
structure of CYK is a proper route to understand, in a simple context,
some of the issues raised by the various techniques for improving the
performance of those parsers in the structured context of the DP
calculation, or to introduce various features such as Viterbi selection of the best parses.

Some of the most basic issues, such as the grammatical forms to be
used to keep a low time and space complexity (cubic), or how to
represent parse-forests. can be more readily viewed and understood
from the simplest algorithm, which is the old cross-product
construction (Bar-Hillel, Perles and Shamir, 1961) between a CF grammar and
a FSA, to produce the grammar of the CF intersection of their
languages. This view is developed in a paper by (Lang 1995) along with extensions to other formal languages.

From a practical point of view, i.e. for use in actual parsers, some
of the more recent general parsers may be better tool. But I believe
that CYK remains an important and simple educational step, more so in
my opinion than Earley's algorithm that is much more complex. Which of
the other DP algorithm should be used for actual systems remains the
object of some debate, as performance issues are somewhat subtle.

I discuss some aspects a bit more in depth in another answer.


Why MIT lecture breadth-first search algorithm is so complicated? I watched a video for BFS from MIT and the algorithm the lecturer presented was really complicated compared to what I came up. My solution seems to work fine and walk through the vertices in the correct order. Am I missing something?

public static void BFS(GraphNode currentNode, GraphNode searchedNode) {
    if (currentNode.index == searchedNode.index) {
        System.out.println("Found!");
        return;
    }

    if (visited[currentNode.index]) {
        return;
    }

    visited[currentNode.index] = true;

    for (GraphNode child : currentNode.children) {
        if (!visited[child.index]) {
            nodeQueue.add(child);
        }
    }

    if (!nodeQueue.isEmpty()) {
        BFS(nodeQueue.poll(), searchedNode);
    }
}

One drawback is that it keeps running after finding a node, but that could be fixed easily by clearing the queue when element is found.

I think this is best handled by contacting the lecturer, but here are four reasons.

A Kain0_0 remarks, your solution is recursive, while his isn't.

Didactic considerations behind this might be:

Recursion is hard for some students. Perhaps it hasn't been taught at this point in the course, or is considered an unnecessary burden.
Most BFS implementations in practice do not use recursion. Programmers need to spot algorithms in other peoples' code all the time. There is value in presenting algorithms in their most common form.

Furthermore,

You're sweeping some stuff under the carpet. He makes his data structures explicit, because he wants to show how much time and space his algorithm uses. You don't: you leave the recursive call stack implicit, and you don't show how .children and .index are represented or created.
He's doing more. He can report the level at which the node was found. You don't keep that information.


Context Free Grammar Exercise I'm studying Context free Grammar and I have a question to a specific Exercise:

Why is i. True? How is this possible?

For every nonterminal $A$ it always holds that $A \Rightarrow^* A$. This is because $\Rightarrow^*$ is the reflexive transitive closure of $\Rightarrow$. In words, $A \Rightarrow^* \alpha$ is $\alpha$ can be obtained from $A$ by applying zero or more productions.

The similar notation $\Rightarrow^+$ is the transitive closure of $\Rightarrow$, and corresponds to one or more productions. In your grammar, it isn't the case that $T \Rightarrow^+ T$.


How does make/scons manage dependency graph and figure out which file need to be recompiled? what I understand is that, the file dependency is organized as a graph. Make/scons check the timestamp of each file, when a source file's timestamp is newer than the output, it re-compile everything depend on this file.

What kind of algorithm does Make/scons use to travel the graph? what if there are circles?

I have been searching around on internet but somehow I cannot find a lot of insights.

Can someone explain to me how does make/scons work?

I do not how SCons works in details so I will focus on Make. I am not sure anyone really knows what is the algorithm Make uses because it is so complicated and error-prone, it is loosely described in the manual . But at the high-level, Make takes as input rules as described in the manual of form $$target: dependencies$$
Furthermore, when running make one has to specify one or more targets to build (if you give no target, it builds "default"): make target1 target2 ...
This essentially describes a graph and a set of nodes to be built.
In terms of graph, one could say that Make performs a depth-first search1 from those to-be-built nodes, but this hides many details like PHONY/FORCE rules, intermediate files, secondary-expansions, the fact that a file can actually be built twice, parallel make and more features. Make considers dependency loops to be an error and will break them arbitrarily (and display a warning).

In fact, one could say that Make performs two different (but related) functions: building the dependency graph and rebuilding everything according to the graph. The difference between Make and other tools is that other tools mostly take as input a complete description of the graph. On the other hand, Make provides a whole range of tool to dynamically create the graph. This creates a lot of confusion because you can literally have a 5 lines Makefile that will generate a graph with thousands of nodes and runs all kinds of tools to figure out the dependencies. SCons, CMake and friends will usually let other tools do this work for them and focus on just rebuilding everything. Also Make's approach makes it somewhat inefficient because just building the graph may involve running some tools, and not just reading the Makefiles.

1The order in which Make builds file is completely unspecified, except for the fact that it is a topological order (and even that is not entirely true because Make may actually build some targets more than once)


Dijkstra Partitioning Algorithm : Special Case I have been exploring Dikstra partitioning Algorithm. Below are my given:

R = Red
W = White
B = Blue

I have this unpartitioned array.

| W | B  | R |  W  | R  | W | B |  W  |  W |

I want it partition in the format: R, W, B consecutively.

| R  |  ?  | W  |  B |
0     i     j    k    n

Given:

 i = 0
 j = n
 k = n
 n = number of elements

Below is my algorithm:

 while  (i < j)
 {
     case a[i]:
         R : i++;
         W : j--; swap(a[i], a[j]);
         B : j--; k--; swap(a[i], a[k]); swap(a[i], a[j]);
     end case
 }
 //Done Sorting

The output should be like this:

 |  R  | R  | W  |  W  |  W  |   W  |  W  |  B  |  B |

My question is:

Can I reduce the number of swaps? If yes, how?
Is the algorithm applicable if there are 4 colors to be partitioned?

Thank you. I really need to understand this concept.

Short answer: No. Note that the worst case of this algorithm is when all elements are blue. In such case, you will need $2\cdot n$ swaps in the worst case. When all elements are blue the number of swaps can be zero.

Optimal algorithm:

I think that the following algorithm is the optimal one:

Count the number of Reds, Blues and Whites in the array.
Denote $n_{color}$ the number of elements of $color\in \{ Blue,Red,White \}$ in the array.
Define $i=0, j=n_{Red}-1$, and $k=n_{Blue}+n_{Red}-1$,  i.e., counters over the Reds,Blues and Whites arrays in the corresponding  , respectively.
Increase i,j,k until either the counter is lager than the size of the corresponding array (i.e., $i=n_{Red},j=n_{Blue}+n_{Red}$ and $k=n$), or that the corresponding element is not in the appropriate color (i.e., $a[i]$ is not red, $a[j]$ is not blue, $a[k]$ is not white). The algorithm stops iff when all counters are lager than the size of the corresponding array $i=n_{Red},j=n_{Blue}+n_{Red}$ and $k=n$.

Now, if $a[i]$ is blue and $a[j]$ is red, then we can swap between them, and increase the counters of $i$ and $j$ until possible.  The same can be said if $a[i]$ is white and $a[k]$ is red or  $a[j]$ is white and $a[k]$ is blue. Thus if there are two elements of  $(a[i],a[j],a[k])$  with the same color- we can swap the corresponding pair, and  increase the corresponding counters.

In the edge case where $a[i]$ is blue and $a[j]$ is white, and $a[k]$ is red, we must do $2$ swaps. The same happens if $a[i]$ is white and $a[j]$ is red, and $a[k]$ is blue.

The number of swaps in such algorithm is at most $\frac{2}{3}n$, in case the array begins with $\frac{n}{3}$ blues,  continues with $\frac{n}{3}$ whites, and ends with $\frac{n}{3}$ reds.

I think that this is the optimal algorithm, I will try to show later the correctness.

2.Is the algorithm applicable if there are 4 colors to be partitioned?
I think it does. In the worst case, you can use counting sort, which runs at $O(nk)$ given $n$ elements and $k$ colores.


Is there a name for this tree traversal? This came when I was looking at block scoping in compiler design.

{   A   { B }   { C {D} {E} }   }

For the above pseudo code, the order in which the scope varies as we scan left to right is A B A C D C E C A, where A to E represent scopes.

A parse tree can be constructed for the above pseudo code:

  A
 / \
B   C
   / \
  D   E

Is their a term for such a traversal order, which for the above tree is A B A C D C E C A?

For a binary tree that is triple order; each node is visited three times in pre- in- and post-order.  Knuth cites it from a paper by Lindstrom and Dwyer; it can be done without a stack by updating the tree in place.