Prove that regular expression is unambiguous I've got following definition:

Function $f$ is a valid mapping of word $w$ to regular expression $R$, if any of following conditions is true:

$R = w$ and $f$ is the identity or $R = \epsilon$ and $w = \epsilon$;
$R = R_1 + R_2$ and $f$ is a valid mapping of $w$ to $R_1$ or $f$ is valid mapping of $w$ to $R_2$;
$R = R_1R_2$, and $w$ can be written as $w_1w_2$ such that $f$ limited to $w_1$ is a valid mapping of $w_1$ to $R_1$, and $f$ limited to $w_2$ is a valid mapping of $w_2$ to $R_2$; or
$R = S^*$ and $w$ can be written $w = w_1w_2\dots w_k$ for some $k \geq 0$ and, for all $1\leq i\leq k$, $f$ limited to $w_i$ is a valid mapping of $w_i$ to $S$.

A regular expression $R$ is deterministic (unambiguous) if, for every $w\in L(R)$, there exists exactly one valid mapping from $w$ to $R$.

I need to prove that the regular expression $R = 0^*(11^*000^*)^*11^*01(1+0)^*$ is deterministic. I think that first I should prove that there exists a valid mapping for every word $w$ to $R$ and then assume that there's a different mappings and lead to a contradiction. But I've got problems with details (especially with the second part of the proof).

This answer has 3 parts:

I first answer the question as asked,
sketching the beginning of a proof concerning the example given. A
full proof is too long and tedious to be given here.
Then I give a general procedure to solve the problem and decide
whether a regular expression is deterministic/unambiguous.
Finally I discuss some difficulties and problems with the statement
of the question.

A direct answer to the question

What you may first prove, though it should be obvious, is that for any
regular expression $R$, there is a valid mapping of any word $w\in L(R)$
to $R$.

Then you consider the regular expression $R = 0^*(11^*000^*)^*11^*01(1+0)^*$ to be analyzed, and you
procede to decompose it structurally, showing  that at every step,
there is only one way to decompose a string $w\in

For example, you show that there is only one way to decompose a string
$w\in L(R)$ as $w=uv$ with $u\in L(0^*)$ and $v\in
L((11^*000^*)^*11^*01(1+0)^*)$. The reason is that $u$ contains only
$0$, and $v$ begings necessarily with a $1$. So the string $w$ must be
cut just before the first one. Then there is only one way to get a
valid mapping for the whole expression, from valid mapping of the two
subexpressions. If the subexpressions are themselves proved
detrministic, i.e. with only one valid mapping fo any string in their
language, then the whole expression must be deterministic.

Hence you now have to prove only that, $0^*$ and
$(11^*000^*)^*11^*01(1+0)^*$ are deterministic, since their
concatenation has a unique decomposition.

So you go on decomposing the expression into subexpression, such that
you have a unique way of matching them with a string of the language.

The next step is to show there is only one way to decompose a string
$w$ in $L((11^*000^*)^*11^*01(1+0)^*)$, as $w=u01v$, with $u\in
L((11^*000^*)^*11^*)$ and $v\in L((1+0)^*)$

And so on ... For each subexpression, you must perform the analysis
according to the type of the subexpression, following the definition
given for each of the four types in the definition of valid mapping.

In the case of $R=S+T$, where  $S$ and $T$ are subexpressions of $R$, you only have to prove that $L(S)\cap L(T)=\emptyset$.

This gives you the general idea of a proof on a given example, such as the one above.

However, such a proof is very tedious and prone to errors.

So you would be better off designing an algorithm that will decide mechanically whether a regular expression is ambiguous or not. The problem is decidable, and not so hard. I follows the same lines I sketched: recursive decomposition of the regular expression, which things to be checked depending on the operator (concatenation, union, Kleene star).

A procedure to decide ambiguousness of a regular expression.

To decide ambiguousness of a regular expression, one must
recursively decompose the expression into 1 or 2 subexpressions
dominated by an operator, down to the leaf level.

Given a regular expression $R$,

If $R=w\in \Sigma+$, then $R$ is unambiguous;
If $R=R_1+R_2$, then $R$ is unambiguous iff both $R_1$ and $R_2$
are unambiguous, and $R_1\cap R_2=\emptyset$. If the intersection is
not empty, any valid mapping from string to $R_1$ could instead map
validly to $R_2$; hence there would be two valid mappings. Also, if
there were two distinct valid mappings to one daughter, say $R_1$,
then by application of rule 2 of the definition, there would be two
valid mappings to $R$.
If $R=R_1 R_2$, then $R$ is unambiguous iff both $R_1$ and $R_2$
are unambiguous, and there is only one way to decompose any string
$w\in L(R)$ into 2 substrings as $w=w_1 w_2$ such that $w_1\in
 L(R_1)$ and $w_2\in L(R_2)$. $R_1$ and $R_2$ must be both unambiguous
because, as before, if one were ambiguous, say $R_1$ for a string
$w_1$, if would be possible to build two valid mappings for $R$,
which would thus be ambiguous.

But how does one check that string $w\in L(R)$ can be decomposed in
only one way into two substrings
$w=w_1 w_2$ with $w_i\in L(R_i)\text{ for }i=1,2$? This can be
checked by attempting to simulate 2 simultaneous generations of a
string in $L(R)$, such that 2 distinct prefix of the substring will
be associated to $R_1$.

Let $A_1$ and $A_2$ be two FA recognizing $L(R_1)$ and $L(R_2)$,
having (to simplify) one start state and one accepting state.
A FA for $L(R)$ can be obtained by linking then with an empty
transition from the accept state of $A_1$ to the start state of
$A_2$.

Then one can build a new FA $A^2$ by doint a cross product of the
state set of $A$ with itself to simulate 2 computations at the same
time. Both computations must be synchronized so that they scan the
input together, though not necessarily following the same
computational paths for each simulated automaton. Both computations
must at some point cross the linking transition. This is memorized in
the final state so that the double computation ends in acceptance iff
the both reach the final state of $A_2$, but after crossing the
linking transition at different points in the input.

This automaton $A^2$ recognizes the language $\{w\in L(R)\mid
 w=uv=u'v' \wedge u\neq u' \wedge u,u'\in L(R_1) \wedge v,v'\in L(R_2)$

Hence, strings in $L(R)$ can be decomposed unambiguously in two
strings belonging respectively to $L(R_1)$ and $L(R_2)$ iff
$L(A^2)=\emptyset$.
If $R=S*$, then $R$ is unambiguous iff $S$ is unambiguous, and
there is only one way to decompose any string $w\in L(R)$ into a
concatenaton of substrings in $L(S)$.

The technique is similar to the one used for concatenation. You take
a FA $A_S$ recognizing $L(S)$, with a single accept state, and you
connect the accept state to the start state with an empty "looping" transition,
to get a FA $A$ for $L(R)$. Then, you buils a FA $A^2$ that simulates
two computations of $A$ and accepts only when they both accept, but
with the constraint that they must have crossed the looping
transition at least once while being at different points of the input
(or possibly a different number of times).

Again, strings in $L(R)$ can be decomposed unambiguously in a
sequence of strings in $L(S)$ iff $L(A^2)=\emptyset$.

Caveats

Some care must be taken with the empty word $\epsilon$. It is not
clear that the problem is always well defined in this respect.
The empty word $\epsilon$ may be used in regular expressions but will have no
apparent counterpart in strings of the language. They can be ignored,
But then, what of a Kleene star $R=S^*$ when  $\epsilon\in L(S)$.
Should it be considered always ambiguous.

Another point is that the concept of valid mapping is really a mapping
of occurrences of words to occurrences of regular expressions, i.e., to
the syntactic instances, rather than to regular expressions as
abstract concepts.

For example, consider the string $w=011001$ and the regular expression
$R=(01)^*100(111)^*1$. There is a valid mapping $f$ of $w$ to
$R$. However it associates the first instance of $01$ with $(01)^*$,
and the second instance of $01$ with $0(111)^*1$.

What is worse, even considering occurences, $f$ is not a mapping since
it associates the first instance of $01$ with both $(01)^*$ and the
regular expression $01$ to which the Kleene star is applied. Hence
$f$, as it is defined, cannot be considered a mapping.

Actually, it seems that $f$ should be defined as a mapping of $R$ and each
subexpression occurrence in $R$ to
substrings of $w$.

But up to that rephrasing of the problem, everything holds.


What is the complement of Halting Problem? I understand that Halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. That is, there are two options for HP: Halt (accept/reject) OR loop.

With this definition of HP, I am unable to understand what is co-HP, since any program can have only 2 options, Halt or loop, so what is co-HP? How do we even know co-HP exists?

The complement of a language $L$ is the language of all strings (over the same alphabet) not in $L$. So the complement of any language exists, by definition. It may be empty, which seems to be the case here.

However, your definition of HP is a bit strange, as every program for a given input either halts after a finite number of steps or does not. So, including both in HP obviously gives you all programs.

It might be more useful to consider something similar to the halting set $K := \{ (i, x) | \text{program $i$ halts when run on input $x$}\}$ (see wikipedia),
i.e. the language of all programs that halt.

The complement of $K$ is then, of course, the set of all programs that do not halt.


Definition of Disjointness for binary strings Basically, most of the definition for disjointness are such that $DISJ(A, B) = 1$ if $A \cap B = \emptyset $ and $DISJ(A, B) = 0$ for other case. My confusion is how is $0$'s influence in here. For example, is all-zeros string considered as $\emptyset$ and therefore the result will be $1$ no matter what the other string is ? Another case is if two disjoint string, e.g., $01$ and $10$ becomes not disjoint after same number of $0$ appended to each string.
Currently my thought is, based on most research papers in communication complexity field, that $DISJ(A, B) = 0$ iff there exists one entry is $1$ for both $A, B$. Would like some clarification and related detailed definition with source.

We identify a binary string with a set in the following way: $x \in \{0,1\}^n$ corresponds to the set $\{ i \in [n] : x_i = 1 \}$. In particular, $0^n$ is identified with the empty set.


If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$? I came across this question while studying for an exam:

  T/F: Suppose we can show for some fixed $k$, an NP-complete problem P has a time $O(n^k)$ algorithm. Then every problem in NP has a $O(n^k)$ time algorithm.

I think the answer is false, since we can't reduce NP-complete to NP-hard in linear time, right? Or am I completely misunderstanding reductions/NP problems? Any help would be greatly appreciated. Thank you.

Yes, the answer the the question is "false".

By contradiction, assume every problem in $NP$ has a $O(n^k)$ algorithm, for some fixed $k$. That is, $NP \subseteq {\sf DTIME}(O(n^k))$

This would contradict the time hierarchy theorem, which implies the strict inclusion

$$
{\sf DTIME}(O(n^k)) \subset
{\sf DTIME}(O(n^{2k}))
$$

However, we also have

$$
{\sf DTIME}(O(n^{2k})) \subseteq NP \subseteq
{\sf DTIME}(O(n^{k}))
$$

which contradicts the previous strict inclusion.


Composition of functions computable in logspace The bit-graph of $f\colon \{0,1\}^* \rightarrow \{0,1\}^*$ is the language:

$\text{BIT}_f := \{\langle x,i \rangle : 1\leq i \leq|f(x)| \text{ and the $i$-th bit of } f(x) \text{ is } 1\}$

It is said that $f$ is logspace computable if $\text{BIT}_f$ is decidable in space $O(\log n)$. Decidable means that there exist a Turing Machine $M$ such that:

if $\langle x,i \rangle \in \text{BIT}_f$ then $M(\langle x,i \rangle) = 1$
if $\langle x,i \rangle \notin \text{BIT}_f$ then $M(\langle x,i \rangle) = 0$

Prove that the composition $(f \circ g)(x)=f(g(x))$ of two logspace computable functions $f,g$ is also a logspace computable function.

Any hint on this exercise? What I tried so far is playing with the composition of the two Turing Machines associated with $f$ and $g$, but I didn't succeed because it always end up with a case analysis exercise.

The idea is quite simple. We are going to simulate running $M_f$ (the machine for $f$) on $g(x)$. Let $m = |g(x)|$, and note that $\log m = O(\log n)$. In order to do that, we keep track of the location of the input tape head of $M_f$ (this takes $O(\log m)$ space), as well as the contents of the work tapes (which also takes $O(\log m)$ space). Whenever $M_f$ attempts to read from the input tape, we invoke the machine computing $\mathrm{BIT}_g$, which also uses up $O(\log n)$ steps; we know which input $i$ to give, since this is just the location of the head.


MIPS Architecture : PC-relative addressing In case of branch Instructions such as beq, bne, we use PC-relative addressing.
But I am really not clear why it is said in most of the books that MIPS address(while calculating branch target) is actually relative to the address of following instruction PC+4 as opposed to the current instruction PC?

Anybody please explain me.
Thanks.

Branch instructions in MIPS have a 16-bit offset value which is sign-extended to provide offsets between -32768 and 32767 words (-131072 and 131068 bytes). This offset is added to the Next PC value rather than the PC of the branch itself.

Why the NPC is used rather than the PC of the branch is not obvious (to me). This may have been related to the use in the Stanford MIPS project of an assembler which performed the limited instruction reordering for filling the delayed branch slot with a previous instruction. With such a design, the offset for forward branches (i.e., branches with positive offsets, commonly used to implement if-then, conditionally branching over the then clause) would never be changed during the conversion and the offset for backward branches (i.e., branches with negative offsets, commonly used for loops) would only be changed when the delay slot had to be filled with an extra no-op instruction. This might simplify compiler development.

An alternative speculation would be that such slightly simplified the initial implementation where the branch was evaluated in the second pipeline stage when the current PC is the NPC relative to the branch instruction.

A third speculation is that such was considered conceptually cleaner given the use of a delayed branch slot. The offset then becomes relative to the instruction in which the branch is "activated".


Perfect Hash Function: How does it cope with lookups outside the set of keys? I'm currently looking at perfect hash functions. One thing I miss from the texts I've read so far is, how they cope when attempting to look up with a key that is outside of the set from which the perfect hash was generated from.

Given a set of keys, a “perfect” hash function is one that gives a different hash for each key. As soon as you try to apply it to a key outside that set, it is quite likely not “perfect” anymore.

Let’s say you are writing a compiler, and you found a”perfect” hash function that maps each reserved identifier of your programming language to a different hash code. And I give you a word that is not one of the reserved words of the language. If you apply your “perfect” hash function then the hash code is either not the hash code of a reserved word (you need to check for that case), or it may be the hash code of a reserved word ( you need to check for that as well). The advantage is that at most one check is needed.


Prove "almost clique" is NP complete Given $G=(V,E)$, undirected graph, a group of vertices $S$ is called almost clique if by adding a single edge, $S$ becomes a clique.

Consider the language:
$L=\{\langle G,t\rangle \mid \text{the graph \(G\) contains a \(t\)-sized almost-clique}\}$.
Prove that $L$ is NP-complete.

Obviously, it is solved by polynomial reduction, but is it from Clique or 3SAT?
And how?

You can reduce to this from $CLIQUE$.

Given a graph $G=(V,E)$ and $t$, construct a new graph $G^*$ by adding two new vertices $\{v_{n+1},v_{n
+2}\}$ and connecting them with all of $G$'s vertices but removing the edge $\{v_{n+1},v_{n+2}\}$, i.e. they are not neighbors in $G^*$. return $G^*$ and $t+2$.

If $G$ has a $t$ sized clique by adding it to the two vertices we get an $t+2$ almost clique in $G^*$ (by adding $\{v_{n+1},v_{n+2}\}$).

If $G^*$ has a $t+2$ almost clique we can look at three cases:

1) It contains the two vertices $\{v_{n+1},v_{n+2}\}$, then the missing edge must be $\{v_{n+1},v_{n+2}\}$ and this implies that the other $t$ vertices form a $t$ clique in $G$.

2) It contains one of the vertices $\{v_{n+1},v_{n+2}\}$, say w.l.o.g. $v_{n+1}$, then the missing edge must be inside $G$, say $e=\{u,v\}\in G$. If we remove $u$ and $v_{n+1}$ then the other $t$ vertices, which are in $G$ must form a clique of size $t$.

3) It does not contain any of the vertices $\{v_{n+1},v_{n+2}\}$, then it is clear that this group is in $G$ and must contain a clique of size $t$.

It is also clear that the reduction is in polynomial time, actually in linear time, log-space.


One $O(n^k)$ algorithm requiring only one $O(2^n)$ computation (for all n instances) is P or NP Let $a$ one decision problem and $A$ one algorithm solving it in $O(n^k)$.

But, to construct $A_n$ we need to compute certain thing (strategy path, magic numbers, ...), we can compute that using certain general algorithm $R$ in $O(2^n)$.

Obiously, $A$ is polynomial (then, all $A_n$ are in P) and $R$ is exponential.

We can not solve big instances because $R$ is not practical.

But, in practice, we will can solve big instances after a big effort computing $A_n = R(n)$.

My question is twofold:

How are such problems considered in theory?
Have they been studied explicitly? Is there a particular case? some literature to read?
How are such problems solved in practice?
Have they been studied in general? Is there is a particular case? some literature to read?

If the "thing" is polynomial-size, then it's in P/poly, a class that has been studied intensively, although this is a very interesting subclass of it which I don't believe been studied. If you have an algorithm that falls into this subclass, I believe theoretical computer scientists might be interested in it.

If the "thing" can be exponential size, then the "thing" could just be a table of all the answers for the instances of size $n$, so all algorithms in EXPTIME would fall into this class. And in fact, this class would be equal to EXPTIME, since the algorithm R followed by A is in EXPTIME.


Dangling else problem I was reading a book about compiler design, then in the CFG section, they introduced the dangling-else problem. They offered to match the the else with the last if. I still don't see how this solves the problem. Can somebody give me an explanation?

I searched before I put the question and none answered my question

The problem is that the code is ambiguous. You can interpret it either as

If C1 then
   If C2 then
     S1
   else
     S2

or as

If C1 then
   If C2 then
     S1
else
   S2

The compiler needs to choose one way and covert it into machine language. The solution of "choose the last if" means the compiler will choose solution number 1 -- will attribute the "else" to the last (open, non-matched) "if" statement.


Difference between data duplication and data redundancy My Computing teachers talk about data duplication and data redundancy in terms of databases as different things, but I'm struggling to differentiate them. The context is database normalisation, and in particular why the third normal form is important: because it eliminates data duplication and redundancy. But as far as I can see, both of these terms relate to data appearing more than once in a database. Yes, I asked my teachers, but I didn't understand the explanation and it was a group revision session that I didn't want to hold up.

(1) Duplication

When you create tables in a database, you may want to create duplication:

CREATE TABLE user (name TEXT, id INTEGER);
CREATE TABLE friends (name TEXT, friend_of_id INTEGER);

Here you would duplicate the name of the user in both tables. That way when you display the list of friends, you do not have to access the user table to read the name. This is a simple example, but it shows what we call data duplication.

Duplication means YOU are responsible for also updating the name parameter in the friends table, when you change the name in the user table. If you do not do that consistently, then your data becomes inconsistent and users start seeing "strange things happening."

(2) Redundancy

In case of redundancy, you do not yourself have two copies of any piece of data. The database can though. This is useful for safety. For example, you can place your database on two separate computers. If one computer goes down, the same data is available on the other computer.

Redundancy is definitively a copy, but the access to either version of the data is 1 to 1 exactly the same to you. The RDBM may choose one or the other based on different parameters such as how fast or whether the other computer network connection is down.

The RDBM manages the copies in very consistent ways, the same problem I just mentioned about user names. If the RDBM is asked to update the user name, it has to update all the versions (all copies). The good thing is it does not have to do it at the time you do the INSERT or UPDATE, it can delay the update on the copy computer. So... the implementers of the database do exactly the opposite of what they were told and make duplicates of the data! (which is probably the main source of confusion in this realm.)

You may want to read about Cassandra for fun things in that respect. Cassandra is the type of database used by Google which update data in a ring of computers with possibly heavy redundancy.

(3) Even More Duplication

Since you asked, I'll also let you know that RDBMs make use of what we call Indexes... And Indexes duplicate your data further. To continue with the user example, the name of the user could be used in an index. The Index would then look like this, for example:

Alexis
Henri
Margarette
Phyllis
...

When you do an UPDATE of the users table, the RDBM needs to also update its index and move the name to the new position, and all of that with maintaining consistency (SQL warrants that the data is always 100% consistent...)

So, renaming Alexis as Tristan would give a new index:

Henri
Margarette
Phyllis
Tristan
...

And here we see that the duplication is actually necessary. And if you see how you can handle that properly, without ever losing any existing data, you understand why duplication is difficult to deal with.


How to use Runge–Kutta methods in a second order ODE Consider a second order equation $F=ma=m\ddot{x}$.
In the language of Euler's method

$\ddot{x}(t+dt)=F(t,x(t),\dot x(t))$
$\dot{x}(t+dt)=\dot x(t)+\ddot x(t)dt$
$x(t+dt)=x(t)+\dot x(t)dt$

Basically, the entire iteration was the second order force equation $F(t,x(t),\dot x(t))$.
However, here one wanted to apply Runge–Kutta method(standard "RK4", not Runge–Kutta–Nyström or else) to solve that equation.
For notation simplicity, let $v\sim \dot x$, $a\sim \ddot x$(velocity and acceleration).
From $x(t),v(t),a(t)$:
$ka1=F(t,x(t),\dot x(t))$; $kv1=v(t)+a(t)\frac{dt}{2}$; $kx1=x(t)+v(t)\frac{dt}{2}$;
$ka2=F(t+\frac{dt}{2},kx1, kv1)$; $kv2=kv1+ka1\cdot \frac{dt}{2}$; $kx2=kx1+kv1\cdot \frac{dt}{2}$;
$ka3=F(t+\frac{dt}{2},kx2, kv2)$; $kv3=kv2+ka2\cdot dt$; $kx3=kx2+kv2\cdot dt$;
and finally
$ka4=F(t+dt,kx3, kv3)$;
The final acceleration was collected to be
Iteration Update Method 01
$\ddot x(t+dt)=(ka1+ka2\cdot 2+ka3\cdot 2+ka4)/6$; where
$\dot x(t+dt)=\dot x(t)+\ddot x(t)dt$;
$x(t+dt)=x(t)+\dot x(t)dt$
with such loop the iteration was able to run in RK4 method and things worked very nicely and coincided with the analytical calculation for an example which Euler method was known to fail.(Tested)
However, my question arise from a mistake where it made the code fail to work. It went like this:
In addition to the $\ddot x(t+dt)$ condition, one further to average the speed directly,
Iteration Update Method 02
$\ddot x(t+dt)=(ka1+ka2\cdot 2+ka3\cdot 2+ka4)/6$;
$\dot x(t+dt)=(\dot x(t)+kv1\cdot 2+kv2\cdot 2+kv3)/6$; and
$x(t+dt)=x(t)+\dot x(t)dt$;
Notice that the new update method attempted to use the $\dot x(t)$  to take care of the "overflow". Intuitively, not only the acceleration $\ddot x$ was "RK4"-ed, but also, the velocity $\dot x$ was "RK4"-ed as well. However, thought still able to produce a sensible graph, the Iteration Update Method 02 was proven to have failed after the analysis.
Question 1: Why Iteration Update Method 01 worked? Even though it approximated $\frac{d^2y(t)}{dt}=f(t,y(t),\dot y(t))$ instead of $\frac{d y(t)}{dt}=f(t,y(t))$?
Question 2: Why Iteration Update Method 02 failed? Shouldn't it work better since it averaged more stuff?

I think there is a mistake in your post: the first equation should be $\ddot{x}(t) = F(t, \dot{x}(t), x(t))$ (and not $\ddot{x}(t + dt)$).
Also, in the computation of $kv_i$ and $kx_i$, it should be $kv_i = v(t) + ka_{i-1}\Delta t$ and $kx_i = x(t) + kv_i\Delta t$ (where $\Delta t = dt$ or $\frac{dt}{2}$). $kv_i$ does not use $kv_{i-1}$ (except in the computation of $ka_{i-1}$), and same thing for $kx_i$.
Question 1: in the differential equation $\ddot{x}(t) = F(t, \dot{x}(t), x(t))$, if you consider the vector $Y(t) = \begin{pmatrix}x(t)\\\dot{x}(t)\end{pmatrix}$, then you have $\dot{Y}(t) = \begin{pmatrix}\dot{x}(t)\\\ddot{x}(t)\end{pmatrix} = \begin{pmatrix}\dot{x}(t)\\F(t, \dot{x}(t), x(t))\end{pmatrix} = \tilde{F}(t, Y(t)) $. That explains why the method works (since the formulas will be the same as with a first order differential equation). Actually, the approximation should be better with the corrections I proposed.
Question 2: With your formulas, a bit of simplification gets you $v(t+dt) = v(t) + \frac{dt}{6}\left(5a(t) + 2ka_1 + 2ka_2\right)$ which is not coherent.
Even with the corrections I proposed, it is incorrect. My guess is that you should compute $x(t+dt)$ and $\dot{x}(t+dt)$ as a whole (as in the vector $Y(t)$) instead of trying to compute them one after the other. The system $\left\{\begin{array}{rcl}\dot{x}(t+dt) &= &\dot{x}(t) + \ddot{x}(t)dt\\ x(t+dt) &=&x(t) + \dot{x}(t)dt\end{array}\right.$ can be seen as $Y(t+dt) = Y(t) + \dot{Y}(t)dt$.


A regular language derived from another This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular:
$$
\{x|\exists y \; |y| = 2^{|x|} and \; xy \in A\}
$$
I'm aware of the notion of regularity preserving functions, and that it would suffice to show that $f(x) = 2^x$ satisfies the property that for an ultimately periodic set $U$, $f^{-1}(U) = \{m|f(m) \in U\}$ is ultimately periodic. I'm struggling to $f$ has this property, but the book from which this comes implies a solution not using this is possible. It appears to be looking for a construction.
I can see that by repeated application of the idea behind the Pumping Lemma, if $A$ has DFL with $k$ states, that for any $x$ with $|x| \geq k$ then
$$
\exists y \; |y| = 2^{|x|} and \; xy \in A\ \implies \exists y \; |y| \leq k \; and \; xy \in A\
$$
But this doesn't give anything going in the opposite direction, that shows that some suitably short $y$ guarantees the existence of a $y$ of the required length.
Any help in solving this, or hint at how to progress would be very helpful.

In order to show that $f$ is regularity preserving, it suffices to show that $f^{-1}(U)$ is eventually periodic for $U = \{ n : n \equiv b \pmod{a} \}$, where $a$ is a prime power (here we are using the Chinese remainder theorem and the fact that the eventually periodic sets are closed under intersection).
For $f(n) = 2^n$, we consider two cases:

If $a = 2^k$ then $f(n) \equiv 0 \pmod{a}$ for large enough $n$.

If $a = p^k$ for an odd prime $p$, then $(2,a) = 1$, and so we can think of $2$ as an element of the multiplicative group $\mathbb{Z}_a^\times$. In particular, $2^n \bmod a$ is periodic, the period being the order of $2$ in the group.


What is the time complexity of the piece of code given below int IsPrime(n)
{
    int i, n;
    for (i=2; i<=sqrt(n);i++)
        if(n%i == 0)
            {printf("Not Prime \n"); return 0;}
    return 1;
}

Here the loop executes for $ \Theta (\sqrt{n}) $ time . But my teacher said that it is not  because the lower bound is $ \omega (1) $ I was not able to understand why it so .

Q1] Could some of you explain which one of us is right justifying reason ?

Q2] What is the importance of  " return 0 " ? What would have been the change if there had no " return 0 inside looping function ?

Q3] In general What is the meaning of return 0, 1, -1 in C programming language ? I have read this from stackoverflow but that didn't solve . Need little bit explanation

The loop executes at most $O(\sqrt n)$ times because i is incremented in every iteration of the loop. You claim that it is also executed at least $\Omega(\sqrt n)$ times. This is not true because it has an early exit (the return statement). For example for even numbers the function returns during the first iteration.

If you recall the definition of $\Omega$, we have $f(n) \in \Omega(g(n))$ if there is some constant $n_0$ such that for all $n>n_0$ we have $c*g(n) < f(n)$ for some constant $c$. By this definition the runtime of your program can't be $\Omega(\sqrt n)$ because the loop makes only one iteration for infinitely many inputs (that is, you can't find a suitable $n_0$).

You can of course restrict your analysis to the worst case ($n$ is a prime number). Then you are correct in saying that the runtime is $\Theta(\sqrt n)$. There is a question about the relation of $O$, $\Omega$, best and worst case in case you find this confusing.


Do the following concepts belong to syntax or semantics? I am not very sure about the difference between syntax and semantics.

Does each of the following concepts belong to syntax or semantics?

terms
values:   terms that are possible ﬁnal results of evaluation.
types
(typing) context
evaluation (rules)
typing (relation)?

Here are two examples from Types and Programming Languages by Pierce.

For example, I thought evaluation (rules) belongs to operational semantics, so values should also belong to operational semantics, by the definition of values. Why does the book list "values" under "Syntax"?

It's not really a good idea to try to divide everything in PL into "syntax" and "semantics". Often we mix things. Nevertheless, as for your question, we normally divide things up like this:

terms, values and types are syntactic entities, as each of them is described by grammatical rules, so these are syntax
a typing context is syntax in simple cases, when we can describe contexts using grammatical rules
the typing relation is considered to be part of static semantics, i.e., the typing relation is determined by the structure of the terms (as opposed to their operational behavior),
the evaluation relation is part of dynamic semantics, i.e., the evaluation rules explain the operational (dynamic) behavior of terms.

You did not mention denotational semantics, which gives mathematical meaning to terms and types. It is considered to be a separate thing of its own.


What does it mean when $A$ is a NP-Complete Problem but $\bar{A} = NP$? I'm still in the process of grokking computational complexity.

However, I came across a statement like the above in an old midterm paper I'm reviewing, and I'm not sure I completely follow its logic.

$NP$ is the class of solveable decision problems that can be verified in polynomial time.

So when we say that $A$ is a NP Complete problem, it is understandably contained within the $NP$ class.

However, if $\bar{A}$ is included in the class $NP$, wouldn't these two postulates essentially indicate that ALL problems are $NP$?

Any insight into how to look at this would be much appreciated!

If $A$ is ${\sf NP}$-complete and $\bar A$ is in $\sf NP$ then we can show that ${\sf NP = coNP}$. This would imply that the polynomial hierarchy collapses to the first level, which implies ${\sf NP = coNP = PH}$.

However, this implies not that all problems are in NP. Just an easy example. There are problems like the halting that are undecidable, and they will remain undecidable even if ${\sf NP = coNP}$, since the proof that the halting problem is undecidable does not use the concept of $\sf NP$ at all.


Which languages, decided by a turing machine are decidable? How do I decide if a language is decidable and/or semi-decidable?

I have theses languages:

a) { < M > | L(M) ⊆ 0*}

b) { < M > | L(M) contains at least one word of even length}

c) { < M > | L(M) is semi-decidable}

d) { < M > | L(M) is decidable}

My problem is, that I don’t quite now how to interpret this notation. I know that <M> is the code of a turing-machine and L(M) is the language decided by the turing machine.

But I’m not quite sure if I understand “language decided by a turing machine” correctly.

Does is mean the following? I run the turing machine M and “collect” all possible words accepted by the turing machine. The collection of these words is the language?

Also: if L(M) means this is the language DECIDED by a turing machine, doesn’t this imply decidability? How can L(M) be semi-decidable if it is supposed to be the language decided by the TM?

I guess there’s a major flaw in my thoughts, but which is it?

For a) and b) I would think that they are not decidable because of the sentence of Rice: There must exist TMs which decide on a language that is element of 0* and those that don’t. Hence the problem is not trival and it is also a functional property of the TM. Same for b.

How do I figure out if these languages a) and b) are semi-decidable? I could construct a TM that excepts all words of the form 0* (and no other words), hence I would say that a is semi-decidable. But then I think, I could just as well construct a TM which rejects all words not of form 0*. And that would mean that this is decidable. But that contradicts my interpretation of the sentence of Rice.

b is more difficult (in my mind at least), because the check if L(M) contains at least one word of even length I would have to check all words of L(M) and since L(M) might be infinite this may not be possible. So it would not be decidable. But it would be semi-decidable, because if I construct a TM to decide over L(M) and I run over a word with even length, I could accept it.

I know there are many errors in my argumentation (but don’t know which these are). This topic is very new to me. I’m thankful about hints on how to solve these kind of decidablity questions. The most examples I found online are about deciding whether M, not L(M) is decidable: { | M does this or that}.

Nice question.

Notations and terms

$M$ or $N$ means a Turing machine (TM), whose specification may or may not given. $\langle M\rangle$ is the description of $M$ according to a predefined effective encoding scheme for TMs.

$L(M)$ is the language recognized by $M$, i.e., the set of words accepted by $M$. At least that is what I have seen everywhere.

Whether a language is decidable or a language is decided by a TM is an entirely different although closely related concept. Let me quote the definition in the book introduction to the theory of computation by Michael Sipser. You could take a look at its definition at Wikipedia as well.

  We prefer Turing machines that halt on all inputs; such machines never loop. These machines are called deciders because they always make a decision to accept or reject. A decider that recognizes some language also is said to decide that language.

  DEFINITION 3.6. Call a language Turing-decidable or simply decidable if some Turing machine decides it.

Note that if $M$ is a decider, then $M$ decides $L(M)$. If it is said that a Turing machine $N$ decides some language $A$, then $N$ must be a decider and $A=L(N)$.

Application of Rice's theorem

Here is the Rice's theorem.

  Let $P$ be any nontrivial property of the language of a Turing machine. Then whether a given Turing machine’s language has property P is undecidable.

  In more formal terms, let $P$ be a language consisting of Turing machine descriptions where $P$ fulfills two conditions. First, $P$ is nontrivial—-it contains some, but not all, TM descriptions. Second, $P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $\langle M_1\rangle \in P$ iff $\langle M_2\rangle \in P$. Here, $M_1$ and $M_2$ are any TMs. Then $P$ is an undecidable language.

a) $P=\{\langle M \rangle\mid L(M)\subseteq 0^*\}$.

WLOG, let 1 be an input alphabet symbol other than 0. $P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\{0\}$ but $P$ does not contain the description of a Turing machine whose language is $\{1\}$.
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)\subseteq 0^*$ iff $L(M_2)\subseteq 0^*$

By Rice's theorem, $P$ is undecidable.

b) $P=\{\langle M \rangle\mid L(M)\text{ contains at least one word of even length}\}$.

$P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\{00\}$ but $P$ does not contain the description of a Turing machine whose language is $\{0\}$.
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ contains at least one word of even length iff $L(M_2)$ contains at least one word of even length.

By Rice's theorem, $P$ is undecidable.

c) By the definition of semi-decidable, a.k.a Turing-recognizable, $L(M)$ is semi-decidable for any $M$. Hence $\{ \langle M \rangle \mid L(M)$$\text{ is semi-decidable}\}$ contains all TM descriptions, which is a decidable language.

d) $P=\{\langle M \rangle\mid L(M)\text{ is decidable}\}$.

Let $R=L(D)$ be a decidable language. For example, we can take $R=\{0\}$ and $D$ is a Turing machine that accepts 0 and rejects all other inputs. $\langle D\rangle\in P$. Let $H=L(N)$ be a semi-decidable but not decidable language. For example, we can take $H$ to be the language of the halting problem. Then $\langle N\rangle\not\in P$. Hence $P$ is nontrivial.
$P$ is a property of the TM's language—-whenever $L(M_1) = L(M_2)$, we have $L(M_1)$ is decidable iff $L(M_2)$ is decidable.

By Rice's theorem, $P$ is undecidable.

 For case a), if we restrict the input alphabets of all Turing machines to be the unary set $\{0\}$, then, of course, for every $M$, $L(M)\subseteq 0^*$. Then $\{ \langle M \rangle \mid\text{0 is the only tape alphabet symbol and } L(M) \subseteq 0^*\}$ contains all TM descriptions. It is decidable.


Efficient algorithm to check if a vector exists in the span of a subset of vectors I have a binary vector $v \in \mathbb{F}_2^m$ and a set of binary vectors $Q=\{q_1,q_2,\dots,q_n\}$ each belonging to $\mathbb{F}_2^m$ and I know that $v \in \text{span}\{Q\}$ but I want to know if there exists a subset $Q_k \subset Q$ of at most $k$ vectors ( i.e. $|Q_k| \le k < n$ ) such that $v \in \text{span}\{Q_k\}$. Is there a fast algorithm to do this other than the naive way of checking all the subsets of cardinality at most $k$? Assume that all of the operations are done in GF(2).

Equivalently, your problem can be stated as:

Given a $m \times n$ matrix $M$ over $\mathbb{F}_2$ and a vector $v \in \mathbb{F}_2^m$, find a vector $x\in \mathbb{F}_2^n$ such that $M x=v$ and the Hamming weight of $x$ is as small as possible.

There are some hardness results for this problem.  For instance, this post argues that the problem can't be approximated within a constant factor, within polynomial time (even for randomized algorithms), assuming standard complexity-theory assumptions.

See also https://cs.stackexchange.com/a/59922/755 and https://cstheory.stackexchange.com/a/10112/5038 and https://cstheory.stackexchange.com/q/27460/5038 and https://cstheory.stackexchange.com/q/10396/5038 for related work, including some algorithmic techniques that might be relevant.


Multi-dimensional Knapsack with Minimum Value constraints for Dimensions In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.
I want to add a conditional constraint: $V = {V_1, V_2, ..., V_d}$, where each $i$-th dimension in the knapsack must have a value sum greater than threshold $V_i$. I am not so much concerned with the total value sum.
I would like to show this problem is NP-hard. My intuition is that the additional constraint makes this problem harder than MKD and therefore is NP-hard. But clearly this doesn't constitute a formal proof.

Your intuition is right on.  If I understand correctly, when $V_1=\cdots=V_d=0$, then your problem becomes exactly the ordinary knapsack problem.  So, the knapsack problem is a special case of your problem.  That means that your problem is at least as hard as the knapsack problem, i.e., your problem is NP-hard.
You can prove this formally by exhibiting a reduction that converts a knapsack problem to an instance of your problem by setting $V_1=\cdots=V_d=0$; thus any algorithm that can solve your problem can be used to solve the knapsack problem, too.


Dijkstra for negative weights by adding a constant I have slight modification for graphs which has negative weights for finding shortest path . If the graph has all non negative weights then by Dijkstra's algorithm , it can be done in O(VlogV + E) . So for the graphs having negative edge weights , find min(weights) = K and subtract K from all weights so that we end up with positive weights. Then apply Dijkstra's instead of bellman ford algorithm which takes O(VE) time to find path and then add K to all paths.
Does this method work? If it does then why bellman ford algo is still relevant , If not why?

No, this doesn't work. A path of length $\ell$ will have $\ell K$ added to its weight, so your transformation can make a path with several light edges weigh more than a path with a few medium-weight edges.  (Consider the effect of adding $2$ to each weight in a path of two weight-$1$ edges vs a path of a single weight-$3$ edge.)


Why is the opcode 0 for all r-type instructions? Please explain your answer I can't seem to find the explanation for why all r-type instructions have opcode 0 always. Can anybody explain why this is so.

In designing an ISA, there are many tradeoffs that can/need to be taken.
This makes it slightly challenging to answer why questions but I will do my best.

In mips I am sure you are aware of the three instruction classes: I, J, and R.

For this explenation I belive only I and R are relevant.

    Type    [31-26] [25-21] [20-16] [15-11] [10-06] [05-00]
    R-Type  [opcode] [$rs]   [$rt]  [ $rd ] [shamt] [funct]
    I-Type  [opcode] [$rs]   [$rt]  [         imm         ]

First lets examine the implications of using [31-26] for R-Type [funct] information.

This would limit the total number of R + I + J instructions to 64. To increase this field for all instructions would limit the size of immediate values.

Additonaly, [5-0] of R instructions would be freed up but not used, not very efficient. By moving R-type opcodes to [funct] the total possible instructions jumps to ~127, while keeping 16 bit immediates.

Finally, if you notice in the data path below there is almost no cost to moving R instruction opcodes to the [funct] field, and it makes room for future instructions to be added to the ISA.

I hope this helps


A recursively enumerable language and a recursively enumerable set I am confused between these two terminologies: recursively enumerable language, recursively enumerable set.

Do they have the exactly same meaning?

No they do not have exactly the same meaning. A language is a set of strings, whereas a set can be virtually anything. Usually such a set is a set of (natural) numbers, but we also can consider sets of graphs.

However, when the sets are accepted or generated by Turing machines, then they have to be represented on a tape (for input or output). This means they have to be represented as strings anyhow. Hence for the Turing machine itself there is no difference. Only for the human beholder there is an interpretation of the string as number or graph.


Solve Recurrence Relation I'm trying to solve the following recurrence relation. I've gotten through two iterations, but I don't see any pattern. I would appreciate any help with this.

$T(1)=1$

$T(n)=6\ T(n/6)\ +\ 2n\ +\ 3$

I've manually ran through two iterations and found the following:

$T(n/6)= 36T(n/36)+14n+21$

$T(n/36)=216(n/216)+86n+129$

The pattern that I see is:

$T(n) = 6^k(n/(6^k))+ (I\ can't\ determine\ the\ pattern\ of\ these\ terms)$

It's probably easier solving this using the Master Theorem.

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

So in this case A=6, B=6, and D=1 because f(n) = 2n + 3 and 2n^1 + 3 = 2n + 3

We of course assume the base case is a constant such that T(1) = C

So we can easily see that the answer for this is

  T
  (
  n
  )
  =
  Θ
  (
  n log n
  )
, since A is equal to B to the power of D.

We can see that is true just by plugging in the values

= A = B^D

= 6 = 6^1

= 2 > 1 (which is always true)

This guy on YouTube has a very nice video explaining how to solve recurrences using the Master theorem, I will leave the link here.


Would it ever be possible for computer viruses to evolve new "genes" to allow them to perform their job? As an A-level Biology student, I have thought a lot about the links with Biology and Computer Science, and something that often comes to mind are the links between Immunology and Computer Security/Viruses. For example, I (through reading about how the anti-virus programs work) decided that the way the immune system handles viruses is very similar to anti-virus programs (both contain a database of virus definitions (be it, $\beta$ memory cells or virus signatures) and both contain a method of extrapolation). The natural progression for me was then thinking about natural evolution of viruses compared to computer viruses. So on to my question:

Would it ever be possible for computer viruses to evolve into new strains which possess new "genes" to allow them to perform their job?

It seems like this sort of thinking could only really apply to viruses, I mean your regular old calculator is never going to be subject to "natural selection". But as far as I know viruses do mutate themselves, in order to avoid anti-virus programs, but presumably these are rather controlled, so that the virus wouldn't gain non-beneficial mutations that might otherwise render it useless. If the true random nature of nature could be applied to viruses, would they ever be able to evolve new functionality, like for example becoming a retro-virus that takes over an anti-virus program, or mutating to include new code that allows it to bring down a firewall? Would they be involved in some sort of computational natural selection, where the strongest viruses survive and pass on their beneficial genes?

I suppose it would be possible in theory, but computer malware (viruses, worms, etc.) typically don't work this way today, and there are good reasons why they're written the way they are.

You might be interested in polymorphic code, which changes itself to evade detection.  It changes the sequence of instructions to some other sequence of instructions that will have the same effect, but will have a different binary.  This helps evade detection by anti-virus tools that are looking for a specific "signature" of bytes.  However, this is not the form of mutation you are asking about, because it will never cause the malware to "evolve" some new behavior it didn't already have.

Really, there is not much reason why malware authors would want or need their malware to evolve new functionality.  They can either build the desired behavior into the malware.  Or, they can have the malware contact a central "command & control" server to download new code ("software updates" for the malware) periodically, to let them control the behavior of the malware.  Usually the bad guys work out offline what attacks they want to mount, and then implement this in the malware or command the malware to perform those attacks.

By working out the attacks offline, in advance, the attackers can test those attacks on their own systems and make sure they'll work properly and won't be detected.  From the attacker's perspective, this is a lot better than writing malware that randomly tries stuff in hopes it'll evolve to a useful attack; malware that tries random stuff will be a lot more likely to set off alarms and be detected.

So, there's not really any need or motivation for using "natural selection" in malware, and it's not typically seen in practice.


Prove that L $\in$ NP implies L* $\in$ NP I have been trying to solve this problem with witness theorem. So the problem is as below:
Define $L^* := \{x \in \Sigma^*|$there exists k and $x_1,...,x_k\in L$ such that $x=x_1x_2...x_k\}$. Prove that $L \in NP$ implies $L^* \in NP$.

So my initial thought is to find a witness language $\in P$ for $L^*$ from the fact that L has a witness language L1 $\in P$. However, I am not sure how to find the right partition of x such that I can use the witness $(x_1,y_1),...,(x_k,y_k) \in L1$.

Does anyone have any thought on it? Much appreciated!

Lets hop back to the definition of a NP language, there exists a non-deterministic Turing machine NTM that halts when given $x$.

It's not that much work to create a non-deterministic Turing machine that first splits the input string into parts non-deterministically and then simulates running NTM on each of the parts and only halts when all parts make the NTM halt.


How feasible is it for a non-distributed web crawler running on consumer hardware to search the internet? I am looking for an automated way to answer the question: what are the URLs on the world wide web that contain at least two strings from a set of strings.

So if I have a set of strings {"A", "B" and "C"} -- I want to know, what pages on the world wide web contain "A" and B", "A" and "C", "B" and "C" or "A", "B" and "C."

Obviously, for this simple example: Google it!

But I want a scaleable, automated, and free solution. Google does not permit automated queries. Yahoo makes you pay.

One idea I have is (1) start with a URL, (2) check the text at that URL for the search strings (3) parse out the links from the text (4) record that you have checked the page and if it contains the strings then (5) search the links from the initial URL. Repeat until you have searched the tree.

How feasible is this in terms of time and space on a single commodity machine -- given the size the internet? The internet is really, really big -- but only a comparatively few pages will contain these strings (they are proper names).

I don't want to index the whole web as if my laptop were google!

Most of the crawler's time will be spent confirming that the pages don't contain the strings.

I'm trying to get a rough ballpark to understand if this is even remotely feasible.

This is not remotely feasible. The number of pages indexed by Google and Bing are in the tens of billions. To get anything close to what they are doing you are going to need to process terabytes of data. It will take you days to download all of these webpages using your home internet connection at full speed. And you will probably hit some bandwidth cap by your ISP before you finish. Even if there was no bandwidth cap from your ISP you would have to be careful in how you request the pages. If you request too many from one server in too short a time you'll probably get your ip blocked by that server. So you'll need some kind of program to optimize the order in which you visit these hundreds of millions of URLs. You will never be able to finish visiting all of the URLs in your queue. New content will be added to the internet faster than you can keep up with it.


Least Common Non-Divisor Basically, the problem is: For a set $S$ of positive numbers, find a minimal number $d$ that is not a divisor of any element of $S$, i.e. $\forall x \in S,\ d \nmid x$.

Denote $n = |S|$ and $C = \max(S) $.
Consider the function $F(x) = $ the least prime number not dividing $x$. It is easy to see that $F(x) \leq \log x$. And for a set $S$, let $F(S) = $ the least prime that doesn't divide any element of $S$.  We have an upper bound

$$F(S) \leq F(\operatorname{lcm}(S)) \leq F(C^n) \leq n \log C.$$

Therefore a simple brute-force algorithm, which enumerates all numbers from $1$ to $n \log C$ and checks if it doesn't divide any element of $S$, is polynomial and has time complexity $O(n^2 \log C)$.

The other way to solve the problem is to compute all factors for every element of $S$ and use them in brute-force algorithm to check if $x$ is an answer in $O(1)$ time. This algorithm has time complexity $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ and uses $O(n \log C)$ memory, because we don't need to compute and store factors greater than $n \log C$. For small $n$ and $C$ it performs better.

In detail, the algorithm consists of two parts:

Construct a set $\hat{S}$ composed of all factors of all elements of $S$, i.e. $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$
This can be done in $O(n \cdot \min (\sqrt{C}, n \log C))$ time and $O(n \log C)$ memory.  (Where does this come from?  For any element of $S$, we can factor it using either trial factorization with all numbers up to $\sqrt{C}$ or all primes up to $n \log C$, whichever is smaller; thus each element of $S$ can be factored in time $O(\min (\sqrt{C}, n \log C))$ time.)
Find minimal number $d \notin \hat{S}$. This step requires $O(|\hat{S}|) = O(n \log C)$ time, if checking whether $x \in \hat{S}$ can be done in $O(1)$ time.

I have two questions that I'm interested in:

Is there a faster algorithm to solve the problem?
For given $n$ and $C$, how can we construct a set $S$ with maximal least common non-divisor?

It is possible to improve on your second algorithm by using better algorithms for integer factorization.

There are two algorithms for integer factorization that are relevant here:

GNFS can factor an integer $\le C$ with running time $O(L_C[0.33,1.92])$.
ECM can find a factors $\le n \log C$ (if any exists) with running time $O(L_{n \log C}[0.5,1.41])$; finding all factors will take $O(\log C / \log(n \log C))$ times as long (which is relatively small compared to the running time of ECM).

Here $L_n[\alpha,c] = \exp\{c (\log n)^\alpha (\log \log n)^{1-\alpha}\}$.

That's a pretty horrendous-looking expression for the running time, but the important fact is that this is faster than the methods you mentioned.  In particular, $L_C[0.33,1.92]$ is asymptotically much smaller than $\sqrt{C}$, i.e., GNFS is much faster than trying all possible factors $\le \sqrt{C}$.  Also $L_{n \log C}[0.5,1.41]$ is asymptotically much smaller than $n \log C$, i.e., ECM is much faster than trying all possible factors $\le n \log C$.

So, the total running time for this method is roughly $\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$, and this is asymptotically better than your first method and asymptotically better than your second method.  I don't know if it is possible to do even better.


Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?) I've been trying to wrap my head around Co-NP, and how it's different to NP, but I am having some trouble.

Co-NP is defined by Wikipedia as this: "A decision problem $\mathcal{X}$ is a member of co-NP if and only if its complement $\overline{\mathcal{X}}$ is in the complexity class NP."

When it was explained to me in class, and after reading about it, my understanding is that if a problem $\mathcal{X}$ is defined to be the answer to $x \in L$ for some $x$ and some language $L$, and $\overline{\mathcal{X}}$ is defined to be $x \notin L$ for the same $x, L$.

Am I right? If I am, how is it different to find the answer to $\mathcal{X}$ and $\overline{\mathcal{X}}$? Knowing that $\mathcal{X}$ results to true or false would tell you that $\overline{\mathcal{X}}$ results to the opposite, wouldn't it?

Edit: I believe this question to be different enough to "Why can't we flip the answer of a NDTM efficiently?" to have merit, as the discussion is being held in a different language and approach.

The Definitions

This comes from the one-sidedness of the definition $NP$, that (we think) is inherent to the class.

One definition of $NP$ is the set of languages $L$ such that there is some for every $x \in L$, there exists a certificate $c$ polynomial-sized relative to $x$, and an algorithm to check if $c$ is a valid certificate that runs in polynomial time.

This definition says absolutely nothing about strings $y \not \in L$. If a word is in our language, there's some certificate. But there might not be certificates for each string not in the language.

So, if we have a magic guessing machine (aka non-determinism, the $N$ of $NP$), we can magically guess a certificate for any $x$ that is in $L$, but to show that $y$ is not in $L$, we have to iterate through all potential certificates and show that none of them are valid.

Example

This is probably made more clear with an example. Let's suppose we have some problem where we have two sets $A$ and $B$, and we want to test if $A \subseteq B$. Let's assume all members of $A$ and $B$ are polynomially sized, and there's a polynomial check to test if any given member is in $A$ or $B$, but there's potentially exponentially many elements in both $A$ and $B$.

This problem is in $co-NP$. Why? Because there's an easy certificate for the "no" case. If $A \not \subseteq B$, then we can just say "Look, I know it's not a subset, since I found this element in $A$ that's not in $B$".

But, to show that there is a subset, we have to go through all elements and show that none of them are in $A$ but not in $B$. So this problem is easy to certify in the no case, but hard in the yes-case.

Implications

Why does this matter? In practice, it tells us the direction that is easy to guess, the direction where heuristics or local search help us the most, and the direction that has the potential to be fast.

For example, consider the travelling salesman problem. Say we want a path shorter than $k$. We can use a bunch of heuristics to try to find the shortest path through all cities. If it finds one of length less than $k$, then we know the solution to the decision problem: a tour of length $k$ or less exists. If it doesn't find one, we have no extra information. There could have been some path that our heuristics missed.

$NP$ problems are ones where the "yes" instances give us this certainty, a "for-sure yes" answer. We search, and if we find one solution/certificate, we know the answer is yes. But to say no, we need to look at all certificates.

$Co-NP$ is where we are searching for a certificate that says "for-sure no", where a yes is only found by looking at all potential certificates and seeing none work.


Fine-Grain parallel algorithm for LU-decomposition How would you understand this pseudocode of parallel algorithm for LU-decomposition ? I'm confused mostly with the
min(i; j) - 1,

because I have no idea, what the author wanted to say by it. I know that it means " choose the lesser number of 'i' and 'j' and then substract one", but I don't know what is I and J here (maybe coordinates of the current task? Or is it written from the task's point of view, so the whole pseudocode runs at every task?) etc.
The whole presentation with this code (slide 12) is here.

Pseudocode and diagram of tasks

Bigger picture here.

It will be clearer if you look at 1 slide before (10/42). The algorithm does not decide on how do you assign to node. It just says that the algorithm can be consisted of many parallel tasks. Each task has identification of $(i,j)$ and each executes the algorithm in slide (12/42).

More specifically, each task is assigned an entry $a_{ij}$ of the matrix ($n^2$ number of tasks), and at the end of the algorithm that entry becomes $u_{ij}$ if $i \le j$ or $l_{ij}$ if $i>j$.


How to Apply Elementary Axioms from Kleene Star to an Inequality Axioms For *

\begin{align}
1 + aa^* &\leq a^* \\
1 + a^*a &\leq a^* \\
b + ax &\leq x \to a^*b \leq x \\
b + xa &\leq x \to ba^* \leq x \\
\end{align}

Elementary Results

\begin{align}
a \leq b &\to a + c \leq b + c \\
a \leq b &\to ac \leq bc\, \wedge\, ca \leq cb \\
a \leq b &\to a^* \leq b^*
\end{align}

Problem

Prove the following identity in a Kleene algebra using only the axioms
    and elementary results. $$(a + ab + b)^* = (a + b)^*$$

Solution:
\begin{align}
  (a + b)^* &= (a + ab + b)^* \\
  (a + b)^* &\leq (a + ab + b)^* \\
  1 + (a + b)(a + b)^* &\leq 1 + (a + ab + b)(a + ab + b)^* \\
  (a + b)(a + b)^* &\leq (a + ab + b)(a + ab + b)^* \\
\end{align}

Quesiton

So for them to be equal the sets should be contained in each other. At which point do I transition to an inequality?
Is it right to say a $*$ cannot be removed since it has no inverse?
Can I distribute into a $*$? Say $(a +b)(a + b)^*$ or do they need to have the same $*$ height?

Some hints to get further would be greatly appreciated.

I assume that in your definition $a \leq b$ iff $a + b = b$.

First, note that if $a \leq b$ and $b \leq a$, then $a = a + b = b + a = b$.
Therefore, in order to show that $a = b$, it is sufficient to show that $a \leq b$ and $b \leq a$.

Now, you want to show that $(a + b)^\ast = (a + ab + b)^\ast$. As explained in the previous paragraph, it is sufficient to show that inequalities with $\leq$ in both directions hold ("[...] for them to be equal the sets should be contained in each other").

The inequality $(a + b)^\ast \leq (a + ab + b)^\ast$ is almost trivial:

$$(a + b) + ab = a + ab + b $$

therefore $(a + b) \leq (a + ab + b)$, and by monotonicity (your ER-3), it thus holds

$$(a + b)^\ast \leq (a + ab + b)^\ast.$$

The other direction is a bit trickier.

By monotonicity (ER-2), (def-$\leq$), (Ax-1):

$$a(a + b)^\ast \leq (a + b)(a + b)^\ast \leq 1 + (a + b)(a + b)^\ast \leq (a+b)^\ast$$

Analogously, $b(a + b)^\ast \leq (a+b)^\ast$.

From both previous statements, again using monotonicity (ER-2):

$$ab(a+b)^\ast \leq a(a+b)^\ast \leq (a+b)^\ast.$$

To summarize: so far, we know that $a$,$b$ and $ab$ are all $\leq (a+b)^\ast$.

Now, observe that from (ER-1), it follows that if $x \leq w$ and $y \leq w$, then $x + y \leq w + y \leq w + w = w$. Thus, from $a\leq (a + b)^\ast$, $ab \leq (a + b)^\ast$ and $b \leq (a + b)^\ast$, you obtain:

$$(a + ab + b)(a+b)^\ast = a(a+b)^\ast + ab(a+b)^\ast + b(a+b)^\ast \leq (a + b)^\ast.$$

Since additionally $1 \leq (a+b)^\ast$ (directly from Ax-1), you obtain:

$$1 + (a + ab + b)(a+b)^\ast \leq (a+b)^\ast.$$

With (Ax-3) it follows:

$$(a + ab + b)^\ast = 1\cdot(a + ab + b)^\ast \leq (a + b)^\ast$$

Thus, both inequalities hold, hence we get the equality.

You cannot simply "remove" $^\ast$, nothing is told about "inverse" in the definition of a Kleene algebra. I also don't know what you mean by "$\ast$-height".


Mathematical model on which current computers are built It is said that "The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation." [Wikipedia]

So on which model current machines are built?

The one closest to typical CPUs is probably the register machine or random access machine (RAM). A RAM has

an infinite number of registers, each of which stores an arbitrarily large number,
a set of operations on these registers (typically $\{+ 1, = 0\}$),
a programming language including these operations as well as control structures for looping/branching (until/if some register holds $0$) and
a program counter pointing to the next operation (in some program).

Real CPUs are quite similar, with some changes:

There are only finitely many registers (which may exist only virtually), and each stores only numbers of bounded size.
There are more operations.

Apart from that, it's very close indeed. It is common to extend the RAM model to account for memory hierarchy, which makes results a lot more applicable.


Language intersections (set theory) - Understanding better I've joined computer science classes at high school because I have a wide knowledge and a few years of experience in programming in multiple of languages, however I didn't fit in the requirements of the class, which is a specific mathematics level. I am a low level mathematics student, I don't really know formal mathematics or any proofs besides a simple proof like proving that an angle is 90 degrees.

So besides programming, there is this subject we started studying about finite deterministic automatons, stack automatons, turing machines and regular languages, etc.

I understand the concept very well, especially when it comes to building turing machines, finite and stack diagrams. At the class, we solve these automatons with diagrams, not in a formal way.

So besides that, my teacher gives us a lot of questions about union, intersection and I am getting really confused with intersection.

Surely I can understand the basic intersections with set of words:

$L = \{aab, bba, aa\}$
$L' = \{a, bbba, aab, aa\}$

So $L\cap L'$ would be $\{aab, aa\}$

I also understand basic language intersections like this:

$L = \{a^n b^n \mid n \ge 0\}$, $L' =  \{a^n \mid n \ge 0\}$

$L\cap L'$ would be $\{a^n \mid n \ge 0\}$

But when it comes to something like this:

$L = \{a^{2n} b^m a^k \mid n,m \ge 0, k = m \mod 2\}$

$L'$ = set of string elements such that the length $|w|$ is even

$L\cap L'$ = I don't know the answer for

The second part of the language which defines the length of the elements (e.g on $n$, of $m$, of $k$) really confuses me in intersections and unions, I am not really sure why. Does that part matters in intersections? I am always getting lost in these cases.

How can I understand this concept a bit better mathematically?

In your last example, when trying to deduce $L \cap L'$, the trick is to trying to understand which strings in $L$ have even length. You can do this as follows:

$$L = \{a^{2n} b^m a^k | n,m >= 0, k = m \pmod 2\}.$$

We can forgot about the first substring of $a$'s, because they always come in pairs (or there are none. In either case, they contribute an even number of characters. Now consider $\{b^m a^k | m >= 0, k = m \pmod 2\}$. The length of the strings in this set is $m+k$. Since $k = m \pmod 2$, we have $m+k = m + m = 2m = 0 \mod 2$. Therefore, $m+k$ is always even, and so $b^m a^k$ always contributes an even number of characters as well. Since $even + even = even$, every string in $L$ is even. Therefore, $L \cap L' = L$.


I don't see why the array[1..3, 1...2] is faster to index than array[1...2, 1...3]? In my programming concept class we learned that for the array type it's faster to index  in memory if the length of an element is = $2^n$. This case make us only need to offset instead of actually doing multiplication.

We also learned about the representation of multivariable arrays with row major. It was then said that the array[1...3, 1...2] is faster to index compared to array[1...2, 1...3] because we have the length of an element being = $2^n$. I don't understand why you can determine this?

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


What is With High Probability on Probabilistic Algorithms? I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still didn't get it.

They just said, "Event $E$ occurs with high probability (w.h.p.) if, for any $\alpha\geq1$, there is an appropriate choice of constants for which $E$ occurs with probability at least $1 − O(1/n^\alpha)$".

Something from algorithmist.com didn't help, either.

What is $\alpha$ and what is $1 − O(1/n^\alpha)$? Not understanding this thing make me confused of the analysis of why "With high probability, every search in an $n$-element skip list costs $O(\lg n)$".

An event happens with high probability with respect to a parameter $n$ if it happens with probability $p_n$ and $\lim_{n\to\infty} p_n = 1$. Usually the parameter $n$ is clear from the context. In this case, for example, it is probably the number of elements in the list.

The definition of "with high probability" in the lecture notes is even more specific, specifying how fast $p_n$ should converge to $1$: an event happens with high probability if it happens with probability $p_n \geq C/n^\alpha$ for some $C,\alpha>0$. For example, if you choose a random number from $\{0,\ldots,n\}$ then it is non-zero with high probability since the probability that it is non-zero is $1-1/(n+1) \geq 1-1/n$ (so in this case $C=\alpha=1$).


Big-O notation for the given function whose runtime complexity grows faster than the input I struggle to determine the runtime complexity of a function I thought of while trying to solve this LeetCode quiz. The quiz itself goes like this:

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 are the first 11 ugly numbers (n=1 up to n=11). On the other hand, 14 does not classify as an ugly number because it has the factors of 2 and 7. The same goes for 33, which has factors of 3 and 11.

If hypothetically, I come up with a function isUgly(i) which can determine whether a given number classifies as an ugly number in O(1) time, I can just brute-force it by testing for every number from 1 to infinity. What would be the algorithmic complexity of such implementation the with respect to the value of n?

int nthUglyNumber(int n):
  nth = 1
  for i = 1..INFINITY:
    if (isUgly(i)):
      nth++;
    if (nth == n):
      return nth;

boolean isUgly(int i):
  # a function that runs in O(1) time that can determine
  # whether a number classifies as an ugly number by returning true / false

The function will return 12 for n=10, and 1536 for n=100 and based on our brute force implementation the function has to iterate 12 and 1536 times to come up with those answers.

We can generalise that if the function returns x for some n, it will have to iterate x times. Therefore, is it acceptable to conclude that this function runs in O(fn(n)) time?

NOTE: There exist a more efficient solution to the problem but that is not what I'm interested in. I am here to understand how to describe the algorithmic complexity of the definition above.

If you express the runtime relative to the input value, it is O(f(n)). But often we describe the runtime relative to the input size; for k bit input it is $O(f(2^k-1))$.

Now  I guess the m-th ugly number is greater than $2^{m^{1/3}}$,  so this grows quite quickly. It would grow so fast that divisibility by 2,3 and 5 only cannot be checked in constant time.

Since others will be interested in an efficient solution: an ugly number is either 1 or a smaller ugly number multiplied by 2, 3 or 5. Algorithm:

Create a priority queue q.
Add 1 to the queue q.
For k = 1 to m
    Extract the smallest number u from the queue q.
    u is the k-th ugly number.
    Add 2u, 3u and 5u to the queue q.

This takes O(m log m) time And O(m) space. Time and space can be greatly reduced by finding a good lower and upper bound for u(m), counting the ugly numbers less than the upper bound in a double loop, and only adding numbers less than the upper bound to the priority queue.

PS You can’t classify a number as ugly in constant time.

PPS. Finding the first n ugly numbers can be done in O(n) operations except that the numbers involved might get large by merging arrays 2k, 3k and 5k in some range. Finding the n-th ugly number might be possible faster than O(n), but that’s tricky.


What impact does the modulo operator have in a for-loop? Here's an example of what I mean:

def complexity(n):
    count = 0
    for x in range(1, n+1):
        for y in range(1, (n*n)+1):
            if y % n == 0:
                for z in range(1, n+1):
                    count += 1
    return count

The first for loop is of course θ(n), the second one θ(n^2).
But what impact does the modulo operator have? And what would then be the complexity of the whole thing?

It feels like you're trying to think in terms of pre-defined recipes, rather than just figuring it out by reasoning about the situation. The if statement triggers every time $y$ is a multiple of $n$. So just work out how many different values in $\{1, \dots, n^2+1\}$ are multiples of $n$, and that's how many times the innermost for loop runs.

Of course, your code is just an example but, in real life, with something as simple and predictable as the modulo operator, you wouldn't use this approach of "generate every possible value of $y$ and see which ones pass the test". It's much more efficient to just write a for loop that directly assigns the values $n, 2n, \dots, n^2$ to $y$.


How to prove this isomorphism-related graph problem is NP-complete? Consider the following problem:  Given two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ and some non-negative integer $k \in \mathbb{N}$, is it possible to delete at most $k$ vertices from $G_1$ to obtain $G_1'$ such that $G_1' \cong G_2$, i.e. the resulting graph is isomorphic to $G_2$.

I have to show that this problem is NP-complete.

Can somebody help me with this problem? It is school homework and I don't know how to solve it.

Here's a hint:  Consider Vertex Cover, which is NP-complete.  If $G = (V,E)$ has a vertex cover of size $k$, then you can remove $k$ vertices from $G$ to obtain $G'$ such that $G'$ is an edgeless graph on $n-k$ vertices.

Edit:  The correct reduction (by using Vertex Cover) shows the problem to be NP-hard.  Given the correct witnesses, you can easily show that it is in NP.


I'm trying to understand DFAs is my DFA correct in this question if not why? I have the following alphat {0,1}.

I'm told to draw a DFA which fulfills the following: {w|w starts with 1 and ends in 0}

This is the DFA I came up with.

This dfa is incorrect.
To start, a dfa MUST define a transition for every node, including accepting nodes.

Anyhow, the current dfa would have accepted the language L = { w | w is a series of 1's and a single 0 at the end }

To correct this, you need to add another transition from B to A when it recieves 1 and a transition from B to itself when recieving 0. This is required to allow strings with 0 in the middle to also be accepted


What are possible uses for cross, back and forward edges after the DFS visit? The depth-first search visit of a graph produces, in some implementations, a labeling of the edges as "Cross", "Back" and "Forward". I know "B" edges can be used to detect cycles.

What are other useful algorithms that use these labels?

Think of the following problem:
Given a directed graph $G = (V,E)$, determine whether there is a pair of vertices $u, v$, s.t $u\neq v$ and $\mathit{and}$ there are at least two $\mathbf{simple}$ paths from $u$ to $v$.

Hint: use the edge labels given by the $DFS$.

Solution:

   If and only if there are any "cross" or "forward" arcs in the tree given by a $DFS$ tour on $G$, then a pair of vertices $u, v$ exists s.t are at least two $\mathbf{simple}$ paths from $u$ to $v$.

Proof:

   1. Suppose no "Cross" or "Forward" Arcs exist. Then the tree given by the $DFS$ is a directed tree, with some "Backwards" arcs. A tree by definition has only one path between every pair of vertices, and below it is shown backwards arcs only add new simple paths.

Consider the backward arc $(u,v)$:

 $\bullet$ for all the ancestors of $v$, it only adds non simple paths.

$\bullet $ for all the descendants of $v$ and ancestors of $u$, denoted by $w$ (vertices between $u$ and $v$ on the tree), it adds one simple path from $w$ to any vertex below (including) $v$ and above (excluding) $w$. All these paths are new because the tree is directed, and all other paths are non-simple, because they contain a cycle.

 $\bullet $ for descendants of $u$, it makes no difference.

2.

 $\bullet$ Suppose a "Cross" arc exists between $(u,v)$. Then $u$ cannot be the root of the tree (the proof is trivial and omitted). Which means the following simple paths exist: $r \rightarrow v$, $r \rightarrow u$, $r \rightarrow u \rightarrow v$

 $\bullet$ Suppose a "Forward" arc exists between $(u,v)$. Then $v$ is a descendant of $u$, but not a child of $u$, therefore there are at least two simple paths from $u$ to $v$.


State Machine and State transition Table - Explanation and Creation Of How do I create a state transition table/array in actual code/pseudo-code?

I haven't experienced the "ah-ha" moment yet with the state machine to coding (and I really want to). I've looked at several code sample and read blog posts, but it's not clicking yet.

I'm looking for a pragmatic explanation of how the state transition table works and how it's created in an array format. If possible, is there a "step-by-step" method to get to the solution?

The particular case/excercise I'm working on is this:
I'm writing a gray-code rotary encoder driver for A micro-controller based on the .netMF framework. It's not real-time and therefore changes the rules a little. Interrupts are captured and queued and then run in a high priority thread. There is a delay so it makes capturing the state of the both encoder pins at the actual time of interrupt in-accurate. In-accurate enough to cause some errors. That being said, when the interrupt is queued, it's state IS captured at that time. When the ISR is finally executed, the pin's state state is passed into it as an argument. Therefore, I can only get ONE pin's state at a time. I think that's sufficient to get this working.

Encoder States For Pin A and B:
A B
0 1
0 0
1 0
1 1 - base state(neutral position of the encoder) (move up for one direction and down for opposite direction)
0 1
0 0
1 0

The mechanical bounce in the encoders will be captured and queued as well, but from what I understand, the state machine can handle these "errors" and continue to produce a good result if the device makes it through a cycle.

I hope this question is clear. I can add additional information as needed.

The state transition function just says "If you're in state $X$ and receive input $Y$, go to state $A_{X,Y}$", for every possible $X$ and $Y$.

Designing the transition function is a matter of programming; implementing it is just a case of

state := start_state
while state is not a terminating state do
    input := read_input ();
    state := A[state, input];
done


Distribute to pairs with efficient algorithms The task is to find a efficient algorithm to the following problem. There are n boys and n girls who need to be divided to pairs. You get a list with all possible pairs that could be made. It means that if the pair (a,b) is in the list then the boy a can be paired with the girls b.

It is known that each boy appears in exactly two pairs, and each girls appears exactly in two pairs. I need to find an algorithm which will find me a proper division to pairs.

My idea was to define a graph. The vertices will be the n boys and the n girls. The edge (a,b) Will be in the graph if the pair (a,b) is the list of possible pairings.

Because each boy and girl appear in exactly two pairs, then each vertex in the graph will be of degree 2.
So every vertex in the graph will be of an even degree.

A connected graph with vertices that are only of even degree has an euler cycle. That way, each connected component in the graph I built will have such a circle.

For each component we fake the circle, with a boy being the starting vertex, and then we erase the last edge in the cycle. Then I define the pairing like this: a boy will be paired with the girl in front of him in the cycle, and the opposite for girls.

This will give me the needed division. Is it good enough?

Yes, that works, but I would skip making/faking Eulerian cycles and just execute your idea directly:

If the list is empty, you're done. Otherwise, choose an arbitrary $(a, b)$ from your list, output it and remove it.
Find the unique $(c, b)$ in your list, output it and remove it.
If $(c, d)$ exists in the list, output it and remove it. Otherwise go to 1.
Find the unique $(e, d)$, output it, remove it, let $c \leftarrow e$ and go to 3.


Why do puzzles like Masyu lie in NP? The puzzle is made up of (n x n) squares so when taking the problem the input size would be n.

Rules of Masyu:

The goal is to draw a single continuous non-intersecting loop that properly passes through all circled cells. The loop must "enter" each cell it passes through from the center of one of its four sides and "exit" from a different side; all turns are therefore 90 degrees.
White circles must be travelled straight through, but the loop must turn in the previous and/or next cell in its path.
Black circles must be turned upon, but the loop must travel straight through the next and previous cells in its path.

Because a problem is in NP if, and only if, "yes" instances have succinct certificates. Informally, this means that the solution to any instance is at most polynomially large in the size of the instance, and if you're given an instance and something that is claimed to be a solution to it, you can check in polynomial time that it really is a solution.

More formally, a language $L\subseteq\Sigma^*$ is in NP if, and only if, there is a relation $R\subseteq \Sigma^*\times\Sigma^*$ such that:

there is a polynomial $p$ such that, for all $(x,y)\in R$, $|y|\leq p(|x|)$;
the problem of determining whether $(x,y)\in R$ is in P;
$L = \{x\mid \exists y\,(x,y)\in R\}$.

For example, consider graph 3-colourability.  You can describe a graph on $n$ vertices just by writing out its adjacency matrix, which requires $n^2$ bits.  If a graph is 3-colourable, you can describe a colouring in $2n$ bits: just list the colour of each vertex in turn (say, $00$ for red, $01$ for green, $10$ for blue).  So, if a string $x$ describes a graph, and that graph is 3-colourable, each 3-colouring can be described in a string $y$ with length $2\sqrt{|x|}\leq 2|x|$.  Furthermore, if I give you a decription of a graph and a description of a 3-colouring, you can easily check in polynomial time that it really is a 3-colouring: just check that adjacent vertices always have different colours. So, the relation
$$\{(x,y)\mid x\text{ describes a graph $G$ and $y$ describes a 3-colouring of }G\}$$
proves that 3-colourability is in NP.

So, to show that Masyu is in NP, we just need to construct the corresponding relation $R$.  We can describe an $n\times n$ instance of Masyu in $2n^2$ bits: for each square in turn, write $00$ if it's blank, $01$ if it contains a black circle and $10$ if it's a white circle.  We can describe a solution in $3n^2$ bits: for each square in turn, write $000$ if the square isn't on the solution path, and $100$, $101$, $110$ and $111$ if it's on the path and the next square is the one to the right, left, up and down, respectively. It's easy to check in polynomial time that a claimed solution really is a solution: just find a square that's on the path, follow the path and check it satisfies the criteria.


How to use DFA/NFA to prove the language {$0^n 1^$ | x ∈ Σ*, n ≥ 1} is regular? I'm trying to prove the language L = {$0^n 1^$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA.
I'm thinking to have n+1 states in a NFA, with the start state as the accepting state. The NFA reada $0$s to go from q$0$ to q$n+1$, then reading $1$s or $0$s to stay in the q$n+1$, then reading the same number of $1$s to go back to the q$0$. Is this a valid way to prove L is regular?

Your language consists of all words starting with $0$ and ending with $1$.


Building automaton from regular expression Let $L=a(a+b)^*b$, a regular expression. I will try to build the automaton by the $a^{-1}L$, $b^{-1}L$ rule

$a^{-1}L = \{a,b\}^* b=M$.
$b^{-1}L=\emptyset$.
$a^{-1}M=b\cup\{a,b\}^*b=N$.
$b^{-1}M=\{\varepsilon\} \cup \{b\}\cup \{a,b\}^*b = P$

But why are the result of 3 and 4 when doing $a^{-1}M$ and $b^{-1}M$ as given?

You failed to notice that your $M$ and $N$ states are indistinguishable. Let's take a walk around the problem first.

We can express this all in regular equations, in the notation of John Conway's Regular Algebra and Finite Machines:

$\begin{align}
L &= a M\\
M &= a M + b P\\
P &= 1 + a M + b P
\end{align}$

We can see that $L$

starts with an $a$;
remains in $M$ for as many $a$s as you like;
goes to $P$, the only terminal state, at the first sign of a $b$;
stays in the terminal $P$ for as many $b$s as you like;
returning to $M$ at the first sign of an $a$.

These equations translate immediately into a DFA. We can also solve them:

$M = a M + b P$

... has solution

$M = a^*bP$

Substituting this into

$P = 1 + a M + b P$

... we get

$\begin{align}
P &= 1 + a a^*bP + b P\\
&= 1 + a^*bP
\end{align}$

... which has solution

$\begin{align}
P &= (a^*b)^*\\
&= 1 + (a + b)^*bP
\end{align}$

Now we can solve for $M$:

$\begin{align}
M &= a^*bP\\
&= a^*b(a^*b)^*\\
&= (a+b)^*b
\end{align}$

And for $L$:

$\begin{align}
L &= a M\\
&= a(a+b)^*b\\
\end{align}$

How do we solve the equations above? The solution to the equation

$X = \mathcal {x} + \mathcal y X$

... ,where $\mathcal {x}$ and $\mathcal {y}$ are regular expressions independent of $X$, is

$X = {\mathcal y}^* \mathcal {x} $

OK. What did you miss?

$\begin{align}
a^{-1}M &= b + (a + b)^* b\\
&= (1 + (a + b)^*) b\\
&= (a + b)^* b\\
&= M
\end{align}$

Even if you miss this, you should find out by further beheading that $M$ and $N$ are indistinguishable.


Languages having only one Myhill–Nerode equivalence class Consider the alphabet $\{a,b\}$, for which languages does the Myhill–Nerode equivalence relation have exactly one class?

From what I understand about equivalence classes, each state is considered a class. So would $\{ a^n : n>0\}$ be the one class?

Assuming that you mean the Myhill-Nerode relation, the Myhill-Nerode theorem states that the number of equivalence classes exactly equals the number of states in the minimal DFA accepting the language (if it's regular; otherwise there are infinitely many equivalence classes). So we have reduced the question to the following one:

  Which regular languages can be accepted using a DFA having only one state?

I'm sure you can answer this one yourself.


Is finding the smallest collection of subsets so that the number of elements among the subsets is <= the number of subsets NP-hard? Given a collection of non-empty subsets of $\{1,2,\ldots,N\}$ ($N$ not fixed), the problem is to find the smallest non-empty collection of subsets so that the number of distinct elements appearing among the union of subsets is less than or equal to the number of subsets chosen. This seems like an NP-hard problem but I can't prove it. Any help?

This is too long for a comment but is not really a full answer.

Let's re-formulate the problem setting slightly as a bipartite graph $G$, with $\{1,2,\ldots,N\} = X$ as one set of vertices and the collection of subsets (say, $Y$) as the other set of vertices, with an edge between $i \in X$ and $J \in Y$ iff $i \in J$. For any set of vertices $W$ in $Y$, define $N(W)$ to be the neighborhood of $W$ in $G$ -- namely, the set of all vertices in $X$ that are adjacent to at least one vertex in $W$.

Then, the problem asks to find a minimal subset $W \subseteq Y$ such that $|N(W)| \leq |W|$. However, if we change the criterion slightly to $|N(W)| \lt |W|$, we find that such a subset exists if and only if there does not exist a matching between $X$ and $Y$ that covers $Y$, for it is exactly equivalent to Hall's Marriage Theorem.

Since such matchings are findable in polynomial time (e.g.: via Hopcroft-Karp), I think this version of the problem should probably be relatively easy but I'd have to do some more work to figure out if and how the standard algorithms for bipartite matching expose these deficient sets and whether or not minimal deficient sets can also be obtained easily. Furthermore, I can't tell right away how much harder the original version of the problem (which allows $|N(W)| = |W|$) is than this modified version.


Finding all "basic" cycles in an undirected graph? Say you have a graph like

a — b — c
|   |   |
e — f — g

and you would like to find the cycles c1, {a,b,f,e}, and c2, {b, c, g, f}, but not c3, {a, b, c, g, f, e}, because c3 is not "basic" in the sense that c3 = c1 + c2 where the plus operator means to join two cycles along some edge e and then drop e from the graph.

I invented my own terminology in the above but basically I want to find all cycles in a graph that cannot be decomposed into smaller cycles. Does this problem have a name? Is there a known best algorithm for solving it?

I understand that enumerating all cycles runs in exponential time because there may be an exponential number of cycles but my intuition is that the number of basic cycles as defined above is related only  polynomially to the number of edges in the graph.

You might be interested in a cycle basis, especially a fundamental cycle basis (which actually consists of cycles).


Best pathfinding algorithm for undirected unweighted graph I have an unweighted undirected graph with every node connected with an average of two hundred other nodes (nodes are people from social network). What will be the fastest algorithm to find the shortest path from one node to another?

assuming you don't have any heuristic function about the distance to the target, a good solution that is valid is bi-directional BFS:
Algorithm idea: do a BFS search simultaneously from the source and the target: [BFS until depth 1 in both, until depth 2 in both, ....].
The algorithm will end when you find a vertex v, which is in both BFS's front.

Algorithm behavior: The vertex v that terminates the algorithm's run will be exactly in the middle between the source and the target.
This algorithm will yield much better result in most cases then BFS from the source [explanation why it is better then BFS follows], and will surely provide an answer, if one exist.

why is it better then BFS from the source?
assume the distance between source to target is k, and the branch factor is B [every vertex has B edges].
BFS will open: 1 + B + B^2 + ... + B^k vertices.
bi-directional BFS will open: 2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2) vertices.

for large B and k, the second is obviously much better than the first.

NOTE, that this solution does NOT require storing the whole graph in memory, it only requires implementing a function: successor(v) which returns all the successors of a vertex [all vertices you can get to, within 1 step from v]. With this, only the nodes you open [2 + 2B + ... + 2B^(k/2) as explained above] should be stored. To further save memory, you can use Iterative Deepening DFS from one direction, instead of BFS, but it will consume more time.

In your case, the difference between BFS and bi-directional BFS, assuming 6 degrees of seperation is between developing ~200^6 = 2.4e13 nodes, and 2*200^3=16,000,000. As you can see, bi-directional BFS needs much less nodes to be developed than the alternative.

Disclaimer: Most of this answer (except the last part) is copied from my answer on StackOverflow.com, as suggested in meta (and effectively applied by a mod in security.SE)


Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b
\}$ is not regular.

I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. Could someone please help me?

I tried to use the pumping lemma with the word $w=a^{2p}b^p$. It is easy to see that for $p=1$ it cannot be "pumped". However, for the case $p=2$ and, particularly,  splitting the string $w=aaaabb$ into $x=\lambda$, $y=aa$ and $c=aabb$, it is true that $\forall i \quad xy^iz\in L$ . Examples for the case $p=2$ are: $i=0 \mid w=aabb$ which can be split into $x=aab$ and $y=b$, $ i =1 \mid w=aaaabb$ into $x=aaaa$ and $y = bb$, $ i =2 \mid w=aaaaaabb$ into $x=aaaa$ and $y = aabb$, etc. So we can't reach to a contradiction.

Here are several routes to proving this:

Intersect with $a^*b^*$ and apply an appropriate inverse homomorphism to reduce to the language $\{a^nb^n : n \ge 0 \}$, which you know isn't regular.
Use Myhill–Nerode theory: the words $\{a^n : n \geq 0\}$ are pairwise inequivalent.
Use the pumping lemma on the word $a^{2p} b^p$, where $p$ is the pumping constant.


Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely.

Could you explain how to efficiently calculate those mod operations  through mod(2^w) and can we extend it to a more common case of mod(w +/- c)?

Another question if we mod by a constant primary number in many places they mention different tricks compilers can do to avoid expensive division operation. Any ideas about those tricks?

Mod(2^N-1) algo:

Split number into N-bit parts (i.e. extract digits in 2^N-ary system). Sum up these parts. If result is higher than 2^N-1 - reiterate. Because

256 mod 255 = 1
2*256 mod 255 = 2
256*256 mod 255 = 256 mod 255 = 1
...
A*2^N mod (2^N-1) = A
A*2^N*2^N mod (2^N-1) = A*2^N mod (2^N-1) = A
...

Mod(2^N+1) algo:

Split number into N-bit parts. Sum up these parts with changing signs. If result is higher than 2^N+1 - reiterate. Because

256 mod 257 = -1 mod 257
2*256 mod 257 = -2 mod 257
256*256 mod 257 = -1*256 mod 257 = 1
...
A*2^N = -A (modulo 2^N+1)
A*2^N*2^N = -A*2^N = A (both equations are modulo 2^N+1)
...

Mod(2^N-K) - multiply by K each next digit

Mod(2^N+K) - multiply by -K each next digit