How does one know what statements in Coq require Induction? I was trying to learn Coq using the famous book Software Foundations. In it I found the following:

Theorem mult_0_r : forall n:nat,
  n * 0 = 0.
Proof.
  induction n as [| n IHn].
  - simpl. reflexivity.
  - simpl. rewrite -> IHn. reflexivity.
Qed.

which I understand perfectly but find rather unintuitive. I understand perfectly how each step works but it would have never occurred to me to use induction to prove such a trivial fact. In fact in the mathematical proof I had in mind that would have been a fact/property (or I guess an axiom) of 0. i.e. $\forall n \in N, n \cdot 0 = 0$ is true by definition. I guess in Coq (or the way we set up numbers? thats not true).

My biggest complaint or worry is that if such a trivial thing requires induction I feel now I am unable to recognize what needs induction (at least in Coq). I know it needs it here because I am in the induction chapter. But in normal maths its usually quite obvious because the problem is obviously recursive. But I wouldn't have really thought of that proposition as recursive. For example it goes on to prove more things as exercises:

Theorem plus_n_Sm : ∀n m : nat,
  S (n + m) = n + (S m).
Proof.
  (* FILL IN HERE *) Admitted.
Theorem plus_comm : ∀n m : nat,
  n + m = m + n.
Proof.
  (* FILL IN HERE *) Admitted.
Theorem plus_assoc : ∀n m p : nat,
  n + (m + p) = (n + m) + p.
Proof.
  (* FILL IN HERE *) Admitted.

which I am sure are not too difficult, but my worry is that in isolation I would have never thought such trivial statements required something as sophisticated as induction. I didn't even learn induction until last 2 years of highschool and didn't really do it seriously until college. So now I see trivial statements requiring what seems to me, sophisticated mathematics.

I just feel my intuition got really lost. When I do Coq proofs (in isolation), how do I know when to use induction and on what? I doubt there is a general procedure (of course) but proofs do exist. So there must be something guiding us to use induction in Coq.

Coq allows one to prove mathematical theorems in a completely formal way. At first, this copes with our experience of doing maths, which is far more informal.

Most of the time, people doing maths are not exposed to mathematical logic. They do not know, for instance, how to define the set of real numbers. Or even the set of natural numbers. Numeric sets are simply taken for granted, together with their operations and related properties. On top of these "basic facts" people build more complex theorems. Essentially, the "basic facts" are used as if they were axioms.

Note that one could work at a similar level in Coq, if one wishes. One can import the Arith Coq library, which provides the basic facts of arithmetics, and exploit those.

However, the underlying logic of Coq does not take those properties for granted. The type of natural numbers, for instance, is not a primitive concept in the logic, but rather something which is defined using induction. Since that makes nat an inductive type, virtually every proof about naturals will require induction. (This also holds in set theory, e.g. Zermelo-Fraenkel, where naturals are also defined in a sort-of inductive way.)

Arithmetical operators are also defined using induction. Using a simplified syntax, one could define multiplication as

x * 0     = 0
x * (S y) = x + (x * y)

or, alternatively,

0 * x     = 0
(S y) * x = x + (y * x)

Both definitions are equivalent. However, using the first one will result in us being able to prove x * 0 = 0 "without induction" -- it follows by definition. In Coq, we can simply write reflexivity and let the system expand the definition for us.

By comparison, 0 * x = 0 is not a trivial equation which follows from the definition: to expand the definition we need to know what is the second argument of the multiplication, but here it's merely an unknown x. Hence, for this we do need induction over x. There's no way around that.

Note that, if we used the second definition instead, we would prove 0 * x = 0 immediately, and instead require induction for x * 0 = 0. So, no definition is strictly better than the other one.


Computer Vision - Algorithm for reconstructing tilted image Recently I've seen this very good apps

https://play.google.com/store/apps/details?id=com.kingjim.shotnote&hl=en
https://itunes.apple.com/JP/app/id411332997?mt=8

this apps reconstruct the image from the camera based on the marker (this is what I think :) ) it also have a special paper that have marker. What I've still haven't got is what is the algorithm to do this? what computer vision theory used in this one? I understand artificial intellegence and basic computer vision, is there anyone have the ide how can this be done? at first I thought this based on stereo image but based on what I've studied before stereo vision need two camera. I hope my question is clear enough but if is there any information needed please ask in the comment :)

Thank you!

It detects 4 markers lying on the corners of the note. One of the markers is unique to able to determine the orientation. Because the actual size and layout of the form is known, a perspective warp can be computed, bringing the scanned image to a canonical (fronto-parallel) form. Then, OCR is carried out in the region where date and time is expected. The rest of the content are taken as image and saved on the smartphone.

For OCR, character segmentation and classification might be your key words.
For Marker Detection, generally black-white polygonal regions are detected and expected to be quad-formed. The rest of the blobs are filtered out and you end up with the markers.


Does this proof work for infinite regular languages My proof was deemed false because it does not work for infinite regular languages, but I don't understand why.

Prove: "If we remove one string from any nonempty regular set, the resulting set is still regular.

I used to lemmas:

A set containing only one string is trivially a regular language
The union operator is closed in the class of regular languages

Given these two lemmas, I made the claim that any regular language $L$ can be written in the form
$$L = \bigcup_{e \in L}\{e\}$$

Then, one picks an arbitrary string $r \in L$ to remove, and expresses $L$ in the same manner with $r$ distinct:
$$L = \bigcup_{e \in (L - \{r\})}\{e\} \cup \{r\}, \quad r \in L$$

Finally, we simply remove $r$ from the union and obtain:
$$L' = \bigcup_{e \in (L - \{r\})}\{e\}$$

$L'$ is also regular by the two lemmas introduced earlier.

The problem with your argument is in the interpretation of the second lemma. Closure under union says "If $L_1$ and $L_2$ are regular languages, then $L_1\cup L_2$ is regular." By induction, then, the union of any finite collection of regular languages is regular. You cannot, however, conclude that the union of an arbitrary collection of regular languages is regular, as Raphael pointed out, since your observation
$$
L=\bigcup_{e\,\in\, L}\{e\}
$$
is true for any language at all, regular or not, so since a single string language is regular, then every language would be regular.

What you could do is exploit some other closure properties of regular languages. For instance

If $L_1$ and $L_2$ are regular languages, so is $L_1\cap L_2$.
If $L$ is a regular language, its complement $\overline{L}$ is too.
We can thus write the set difference $A\setminus B$ as $A\cap\overline{B}$ so regular languages are closed under set difference.
If $L$ is any regular language and $e\in L$ is any string in $L$, then $L\setminus \{e\}$ must also be regular.


Understanding Hoare Logic Axioms Given these 5 axioms of Hoare Logic:

\begin{array}{cl}
\frac{}{\{\phi([x \leftarrow E])\}\ x := E\ \{\phi(x)\}} & \mathtt{Assignment}\\\\
\frac{\{\phi\}\ P_1\ \{\eta\} \quad \{\eta\}\ P_2\ \{\psi\}}{\{\phi\}\ P_1; P_2\ \{\psi\}} & \mathtt{Sequencing}\\\\
\frac{\{\phi \land B\}\ P_1\ \{\psi\} \quad \{\phi \land \neg B\}\ P_2\ \{\psi\}}{\{\phi\}\ \mathtt{if}\ B\ \mathtt{then}\ P_1\ \mathtt{else}\ P_2\ \{\psi\}} & \mathtt{Conditionals}\\\\
\frac{\{\phi \land B\}\ P\ \{\psi\}}{\{\phi\}\ \mathtt{while}\ B\ P\ \{\psi \land \neg B\}} & \mathtt{Iteration}\\\\
\frac{\phi ⇒ \phi1 \quad \{\phi1\}\ P\ \{\psi1\} \quad \psi1 ⇒ \psi}{\{\phi\}\ P\ \{\psi\}} & \mathtt{Weakening \to Strengthening}
\end{array}

Trying to understand the following:

$\mathtt{Assignment}$

What $\phi([x \leftarrow E])$ means. In the presentation it says $\phi([x \leftarrow E])$ replaces every "free occurence" of $x$ in $\phi$ by $E$. I am confused because I thought that was what the assignment $x := E$ was doing. So my reading is: "precondition: replace each free occurrence of $x$ in state $\phi$ with $E$, program: assign $x$ to $E$, postcondition: $x \in \phi$". I am confused by both the pre and post conditions. To me it should be written $\{\phi[x] \land \phi[E]\}\ x := E\ \{\phi[x == E]\}$, that is, "given $x$ in state $\phi$ and $E$ in state $\phi$, when I assign $x$ to $E$, I get the new state where $x$ is equal to $E$". Wondering if someone could help clarify this my interpretation.

$\mathtt{Sequencing}$

This one makes sense. If program $P_1$ leads state $\phi$ to state $\eta$, and program $P_2$ leads state $\eta$ to state $\psi$, then program $P_3 := P_1 ; P_2$ leads state $\phi$ to state $\psi$.

$\mathtt{Conditionals}$

"If we're in state $\phi$ and we have variable $B$, then program $P_1$ leads to state $\psi$. Similarly for $P_2$, but when we don't have $B$ in state $\phi$"
This is essentially a sequential composition.
I would've written it as $\{\phi[B]\}\ P_1\ \{\psi\}$ and $\{\phi[\neg B]\}\ P_1\ \{\psi\}$, would be helpful to better understand the notation on why they wrote it with the $\land$. To me $\{\phi \land B\}$ says either "B is true in $\phi$ state" or "B exists in $\phi$ state", can't tell.

$\mathtt{Iteration}$

"If $B$ is in state $\phi$, and program $P$ leads to state $\psi$, then $\mathtt{while}\ B\ P$ leads to state $\psi$ without $B$". So this is an axiom.
I don't understand how this can be an axiom because there is so much that is going on (tons of iterations for example). Wondering what allows this to be an axiom.

$\mathtt{Weakening \to Strengthening}$

I don't understand this one yet.

To summarize, these are my questions:

What the notation is for having certain values in a state in the pre- or post-condition. If it's $\{\phi[B]\}$ or $\{\phi(x \leftarrow B)\}$ or $\{\phi \land B\}$ or $\{\phi(B)\}$. What the preferred notation is and its meaning. I have also seen $\{\phi[B/x]\}$
How to interpret the assignment rule.
How the while loop is allowed to be an axiom, when it does so much.

Thank you so much for the help.

Here are some answers and hints to pursue your reflexions.

$\mathtt{Assignment}$

What $\phi([x \leftarrow E])$ means. You said yourself that the semantic of the precondition confuses you that was what the assignment $x := E$ was doing. But in fact your are precisely pointing out the crux of this rule: it affects the precondition exactly as the assignment would do it. This is the core reason of why this rule is actually sound.

Let study an exemple and leave the abstraction for a bit.
Take the program $P = (z:=x+1)$.

Suppose we want to prove the postcondition $\phi(z) := \{z=2\}$
Intuitively what do we need to prove this ?  Obviously we need $x$ to be equal to $1$. Let see how it translates in Hoare's logic. The assignment rule tells us that the triple:
$$
\{\phi[z \gets x+1]\} (z:=x+1) \{\phi(z)\}
$$
is valid.

Unrolling the syntax gives:
$$
\{(z=2)[z \gets x+1] \} (z:=x+1) \{x=2\},
$$
that is
$$
\{x+1 = 2 \} (z:=x+1) \{z=2\},
$$
and a bit of meta-logic says:
$$
\{x = 1 \} (z:=x+1) \{z=2\}.
$$

Which is what you wanted.

In an nutshell the assignment intuitively says: "The postcondition is true as soon as when I replace everything by the value of E in it, it is true"

$\mathtt{Conditionals}$

First of all $B$ is not a variable but a boolean predicate (like $X==1$ for instance).

$\{\phi[B]\}\ P_1\ \{\psi\}$ doesn't make any sense. $\phi$ is a predicate, so does $B$, so that you can't apply one to another.
For instance if $\phi = (x==1), B = (y==2)$ you can speak of $\phi\wedge B$ but $\phi[B] has absolutely no meaning.
$\{\phi \land B\}$ is true says $\phi$ is true and $B$ is true.
With my previous instances:  $\{\phi \land B\}$ as precondition asserts that on the one hand $(x==1)$, and on the other $(y==2)$. Nothing else.

$\mathtt{Iteration}$
 This one is subtle. As long as it terminates, you can have arbitrary many iterations BUT still a finite number. Think of a while as a for loop on which you don't know a priori the number of runs in this case. To see why the rule is sound, think of it as a nested sequence of if :

if B then
     P
     if B then
         if B then
            P
            if B then
                 .....

And use a recurrence + conditional+ composition to convince you that the rule does what it is supposed to do.

If it doesn't terminates you can't say anything a priori so it doesn't matter. Remark that the rule DOES NOT say that the loop terminates.

$\mathtt{Weakening \to Strengthening}$
  It is the causal reasoning. Let us unroll the rule: Suppose that $\phi$ is true. Then $\phi$ is also true since  $\phi \Rightarrow \phi_1$. But the Hoare triple
$\{\phi_1\}\ P_1\ \{\psi_1\}$ is valid by hypothesis. Then $\psi_1$ is true. But we know that $\psi_1\Rightarrow \psi$. Hence $\psi$ is true as well: we just proved that $\{ \phi \} P \{\psi\}$ is a valid triple.


Is the language of all TMs *not* accepting a given string, Enumerable? Is the following language in RE?
$$L = \{\langle M\rangle : M\text{ is a TM that does not accept }010\}$$

I could use Rice's Theorem with the property $P = \{L : 010\text{ is not in }L\}$ to show it isn't in R, but how do I show it is in RE?

The classic technique of dovetailing can be used to show the complement of $L$, $\{\langle M\rangle : M\text{ is a TM that accept }010\}$ is recursively enumerable. Check this answer for details.

Since $L$ is not decidable as shown by Rice's theorem, $L$ cannot be recursively enumerable.

Exercise. Show that $\{\langle M\rangle : M\text{ is a TM that accept } 010\text{ and }101\}$ is not in RE.


Gale Shapley - Everyone ends up with second choice of partner So I was asked to prove (or not) whether, in gale shapley algorithm, everyone can end up married to their second partner of choice or not. I think not but then I am not able to come up with a proof.

Thanks! :)

Let us number the men $1,2,3,4$ and the women $a,b,c,d$ (the men propose to the women), with the following preferences:
$$
\begin{align*}
&1\colon b \succ c \succ d \succ a & a\colon 1 \succ 2 \succ 3 \succ 4 \\
&2\colon b \succ a \succ d \succ c & b\colon 3 \succ 4 \succ 1 \succ 2 \\
&3\colon a \succ d \succ c \succ b & c\colon 2 \succ 1 \succ 4 \succ 3 \\
&4\colon a \succ b \succ c \succ d & d\colon 4 \succ 3 \succ 2 \succ 1
\end{align*}
$$
Let us trace the Gale-Shapley algorithm:

Round 1M: $1,2$ propose to $b$; $3,4$ propose to $a$.
Round 1W: $b$ accepts $1$; $a$ accepts $3$.
Round 2M: $2$ proposes to $a$; $4$ proposes to $b$.
Round 2W: $a$ accepts $2$, throwing $3$; $b$ accepts $4$, throwing $1$.
Round 3M: $3$ proposes to $d$; $1$ proposes to $c$.
Round 3W: $d$ accepts $3$; $c$ accepts $1$.

In the end, everyone is married to their second choice.


Approximation algorithm for weighted set cover, using multiplicative weights It is known that the problem of fractional set cover
 can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows how to do so.
The running time depends on the "width" of the problem, which equals to the number of sets in the unweighted case. However, in the weighted case, the width of the problem depends on the weight function, hence the running time is exponential with respect to the representation of the problem. Is there a way to overcome this issue? Either a way to reduce it to polynomial running time or proof that it's impossible (under plausible complexity assumptions)?

Yes, fractional weighted set cover and, indeed, all explicitly given packing/covering LP's can be solved using multiplicative-weights algorithms in poly time independent of the width. There are many papers in this line of work. The earliest are probably due to Garg and Konemann. See e.g. https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388#14388 .


Access to publicly available project with all the artefacts (files) created during the development Does anyone know where I could get an access to a project that contains all the artefacts (documents) that were created during the development? So I would like to get all the word, pdf, power designer, etc. files as well as all the source code. If possible, I would prefer that all this files are stored in some of the software reporitories.

Your best bet is to go with major open source projects (Apache, Open Office, Mozilla, MySql, perhaps Linux).  Since these are done by large online communities all communication occurs online through bug databases and forums or mailing lists (which are usually archived).  If they do code reviews they may be archived with a tool like Review Board or will be done through the official archived mailing lists.  It seems unlikely that you will find a non-open source project/company willing to provide such detailed information.

An example of an academic software engineering study which quite successfully used open source artifacts is:

  Shan Lu, Soyeon Park, Eunsoo Seo, Yuanyuan Zhou: Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. (ASPLOS-XIII):329-339, 2008.

Prof. Y.Y. Zhou's research team at UCSD has done a variety of other studies mining open source bug databases to understand bug or failure characteristics.  http://opera.ucsd.edu/pub_system_depend.html#characteristic-study


What is the relation between a programming language and the language of its input? I find some references say that

  all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything that cann't.

and

  Actually, most of programming language is context-free language.

Q1: Are the claims correct? I did not find some bibiographies about a precise description or even a proof.

Let $\Gamma$ be the alphabet of the instructions of a programming language. Given a specific procedure $P$, all of its control flows belong to $L_{P}$. $L_{P}$ describes how does it control its data.

At the same time, for every $x \in \Sigma^*$, $P$ computes it and gives an output $P(x)$. Assume that $P$ is used to slove a decision problem, i.e., $P(x) \in \{ 0,1 \}$. There is a language $L'_{P} = \{ x \in \Sigma* \mid P(x) = 1 \}$. If we regard $P$ as a machine, $L'_P$ describes the computational power of $P$.

It is obvious that $L_P$ and $L'_{P}$ are totally different.

Q2: What is the relation between $L_P$ and $L'_{P}$? Is there a conclusion such that
$$L_P \in CFL \Leftrightarrow L'_P \in CFL$$
or
$$L_P \in CSL \Leftrightarrow L'_P \in CSL$$

There is no interesting relation between a programming language (the set of words which are syntactically valid programs) and the set of words that are accepted by a program written in said programming language.

Note that it is possible to design a Turing powerful programming language which, as a formal language, is the set $1^* = \{\epsilon,1,11,111,\ldots\}$.

Still, program $1^n$ will accept a language $L_n$ which is completely unrelated to $1^*$. Indeed, by Turing completeness, for any r.e. language $A$ there is some $n$ such that $A=L_n$.

The crucial aspect to consider here is the semantics of the programming language,
the way we map each program $1^n$ to its behavior, and ultimately to the set of accepted words $L_n$. Even if $1^*$ is a very simple language, the semantics can still make it Turing powerful, so that $L_n$ can be any r.e. language.


In principle, what is the relation between Artifical Intelligence and Turing machine? I am working on my cs project about AI & Turing machines, so i know that Artifical Intelligence is meant to implement different algorithms into the machine {the computer} to solve a problem or a set of problems together and i am getting AI as: (the machine is 'programmed' on a certain algorithms to solve problems or to show intelligent behavior when solving a specific problem).

  Artifical Intelligence is usually defined as the science of making computers do things that require intelligence when done by humans.

On the other hand, Turing machine just manipulates data of {0 & 1} on a tape according to a table of rules to solve a problem {calculate the input}.

  A Turing machine is an abstract machine that manipulates symbols on a strip of tape according to a table of rules.

So, generally speaking both AI and Turing machines are meant to compute the input and transfer it to a right answer {output} so here is what iam confused about :

What a formal defination would relate both of them ?
Can i say that both algorithms of AI and a table of rules of a
Turing machine are the same ?
Can i also say that AI is about choosing the best solution between
different solutions to the input and turing machine just
shows a solution of the input ?

Turing machines are a model of computation, one way of formally defining the concept of an algorithm. While Turing machines are usually defined using barebones input/output capabilities, it is not difficult to extend them so that they can apply to the kind of problems that AI is after.

The relation between AI and Turing machines is thus:

  Artificial intelligence is implemented by algorithms. Algorithms can be described by Turing machines.

Note, however, that Turing machines are not a great model for describing practical algorithms, since they work rather differently than actual machines, and as a consequence the complexity of algorithms is somewhat different when implemented in Turing machines compared to their real-world implementations. You should replace Turing machines with your favorite programming language.

Now I can answer your actual questions:

1) What a formal definition would relate both of them? Artificial intelligence is not a formal concept, so none.

2) Can I say that both algorithms of AI and a table of rules of a Turing machine are the same? Artificial intelligence is about algorithms performing some tasks, and Turing machines are a way of describing algorithms. So the answer to this question is positive.

3) Can I also say that AI is about choosing the best solution between different solutions to the input and Turing machine just shows a [sic] solution of the input? No, this is a false dichotomy. Algorithms implementing AI and algorithms implemented on Turing machines (with I/O) are exactly the same. There is absolutely no difference. Also, there is no such thing as a "best solution". So the answer to this question is negative.


Complement of HAMPATH Is the complement of the Hamiltonian Path problem known to be in $\mathsf{NP}$? I could not find explanations saying that it is, but then neither were there any claims saying that it is not in $\mathsf{NP}$.

The HAMPATH complement ("G does not contain an Hamiltonian path from s to t") is in co-NP; to be more precise it is  co-NP complete (it is easy to prove that $L$ is NP-complete if and only if its complement $\bar{L}$ is co-NP-complete).

The question if it is in NP is open.

But since HAMPATH is NP-complete, if its complement is in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{co\mbox{-}NP}$


Proving Infinite Turing Machine Language (with finite subset) is Recursively Enumerable I'm trying to answer this question:

Let $S$ be the strings $\langle P \rangle$ accepted by the Turing Machine $P$ with input alphabet $\{a,b\}$, where $P$ accepts an infinite number of strings beginning with $a$ and a finite number of strings beginning with $b$.

Is $P$ RE?

Is $P$ co-RE?

Regarding your first question, a reduction from the halting problem only shows that a problem is hard, not that it's easy. If the halting problem reduces to some problem $P$, then you know that $P$ isn't co-computably enumerable. So if you manage to reduce the halting problem to $L$, then this shows that $L$ is not co-computably enumerable. Perhaps that can inform your guess on the answer.

Regarding your second question, if you show that $L$ is c.e. but not computable, then indeed it follows directly that $L$ is not co-c.e. This is because a language that is both c.e. and co-c.e. is computable.

Let me give you a hint. Every Turing machine can be modified so that it accepts only strings beginning with 0: the new machine accepts $0x$ iff the old machine accepts $x$. Such a Turing machine belongs to $L$ iff it accepts infinitely many strings. Similarly, a machine which only accepts strings beginning with 1 belongs to $L$ iff it accepts finitely many strings.


How to challenge Hutter's algorithm? For a given sufficiently strong formal axiomatic system $\mathsf{F}$ (like $\mathsf{PA}$ or $\mathsf{ZFC}$) and any given function $p^*(x)$ that can be specified within the formal system $\mathsf{F}$, Hutter's algorithm $M_{\mathsf{F},p^*}$ computes the function $p^*(x)$ nearly as quickly as any (provably quick) algorithm $p$ provably computing $p^*(x)$. More precisely

  Let $p$ be any algorithm, computing provably the same function as $p^∗$ with computation time provably bounded by the function $t_p(\xi)$ for all $\xi$. $time_{t_p}(x)$ is the time needed to compute the time bound $t_p(x)$. Then Hutter's algorithm $M_{\mathsf{F},p^∗}$ computes $p^∗(x)$ in time
  $$time_{M_{\mathsf{F},p^∗}}(x) ≤ 5·t_p(x)+d_p·time_{t_p}(x)+c_p$$
  with constants $c_p$ and $d_p$ depending on $p$ but not on $x$.

Here "provably" means that a proof can be found in $\mathsf{F}$. The algorithm could be interpreted as a generalization and improvement of Levin search, but I wonder whether it is always an improvement.

Can we use the formal system $F$ to construct a function $p^*$ for which Hutter's algorithm $M_{\mathsf{F},p^*}$ performs badly? How about asking whether a short proof of $\bot$ (i.e. a contradiction) can be found in $\mathsf{F}$? A short proof would be a proof with fewer than $n$ symbols, and we would use $x$ to encode $n$ in binary form. The function $p^*$ would just be a brute force search for the contradiction.

I think this should give a problem in $NEXP$, but the optimal algorithm to compute $p^*$ would have complexity $O(1)$, because the answer is always "no". But $M_{\mathsf{F},p^*}$ will take double exponential time in the length of $x$ to arrive at that conclusion, if I'm not mistaken. Now I wonder whether there are more interesting ways to make $M_{\mathsf{F},p^*}$ look bad, perhaps similar in spirit to Rice's theorem?

But $M_{\mathsf{F},p^*}$ will take double exponential time in the length of $x$ to arrive at that conclusion, if I'm not mistaken.

That $M_{\mathsf{F},p^*}$ will take double exponential time is a conjecture at best. Too see that this conjecture is pretty strong, take any formula $\phi$ that is formally independent of $\mathsf F$, and ask whether a short proof of $\phi$ can be found in $\mathsf F$. Any algorithm that can answer this question quickly (with "no") can also answer the same question for $\phi=\bot$ quickly (with "no"), because any formula can be derived in a single step from $\bot$.

  Now I wonder whether there are more interesting ways to make $M_{\mathsf{F},p^*}$ look bad, perhaps similar in spirit to Rice's theorem?

Formal systems are not just bad at proving their own consistency, they are also famously bad at proving some sequence to be random. So we could ask whether a given finite sequence can be reproduced by some program shorter than $m$ symbols taking fewer than $n$ steps. The restriction to fewer than $n$ steps allows us to implement $p^*$ as a brute force search. If the sequence and $m$ are kept fixed and binary encoding is used for $n$, the resulting problem seems to be in $EXP$. Maybe it's better not to fix the sequence and $m$, because then the problem seems to be in $NEXP$.

What about a function $p^*$ based on Rice's theorem? No progress yet...


Is {wxw^r} a regular language? Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why?

The notation $W^{\mathrm{R}}$ means the reverse string of $W$?

If we consider the best answer in this solution, if the language is regular, then its FA should reject all strings not in the language. However, a string such as 0110100 would also be accepted by the FA, since it compares only the starting and end characters! Please explain.

$W^R$ means the reverse string of $W$.
You are right about the DFA. If a DFA $A$ accepts the language $L$ then it rejects all the words that are not in $L$. But the word $\sigma = 0110100$ is in the language!. Consider $W=0$ and $x=11010$.
As G.Bach eloquently stated in his comment(a very interesting property of the language):

$$\{WxW^R : W,x\in \{0,1\}^+\} = \{WxW : W\in\{0,1\} , x\in \{0,1\}^+\}$$

¿Why?

Because there is little restriction to $x$. We can consider that $x$ is almost the whole word with the exception of the first and the last symbol(because in the original language $|W|>0$). The reverse string of any word with unitary size is the same word. So words like:

$$\sigma_1 = 01110000$$
$$\sigma_2 = 11111101$$

Are in the language. All that matter is the first and the last symbol. This language is very interesting because it appears to be irregular at the first sight.


Finding an MST with one adding and removing vertex operation I am facing the following problem: Given an undirected complete Euclidean weighted graph $G(V, E)$ and its MST $T$. I need to remove an arbitrary vertex $v_i \in V(G)$, and given a vertex $v_j \notin V(G)$, I have to calculate the MST of $$G^{'}((V(G) \backslash \{v_i\})\cup\{v_j\}, (E\backslash\{(v_i, v_k): v_k \in V(G)\})\cup\{(v_k, v_j): v_k \in V(G^{'})\}),$$ i.e, the graph $G$ with the vertex $v_j$ (and edges from $v_j$ to every other vertex) and without the vertex $v_i$ (and its respective edges). To solve this, we can apply some well-known MST algorithms, such as Prim's, Kruskal's, Borukva's algorithm. Neverthless, if we do this we would not use the already existing MST $T$, i.e., we would calculate a new whole MST. So, I would like to know if there is any way to reuse the existing MST $T$.
There are two similar questions to this here (with edges, considering only the removing of them), and here (with vertex, considering only the adding of them).
The vertices are points in $\mathbb{R}^2$, and the weight on each edge is the Euclidean distance between the two points.

After long hours facing this problem, with my advisor help, we could solve this problem in $O(|E(G^{'})| log\text{ }C)$ time complexity by using one iteration of the Boruvka's algorithm, where $C$ is the number of connected components of $G^{''} (V(G^{'}), T\backslash \{(v_k, v_i): v_k \in V(G^{'})\})$, i.e., the number of connected components of the MST $T$ by removing $v_i$ (and edges from $v_i$ to every other vertex in $T$) plus one (due to the inserted vertex $v_j$).
Note that, this solution might have $O(|E(G^{'})| log\text{ }|V(G^{'})|)$ time complexity if the removing of $v_i$ in $T$ (and edges from $v_i$ to every other vertex in $T$) lead to a totally disconnected graph. Also, note that, this solution has $\Omega(|E(G^{'})|)$ if C is equals to 3.


Superdense coding - What are the individual qubits A and B? With reference to this  PDF discussing Superdense coding, it is mentioned that there are two qubits A and B whose superposition gives the system $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$. It is said that Alice has A while Bob has B. What are the individual qubits A and B?

Since the system is entangled, can there exist two qubits A and B such that their superposition is $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$ ? If the answer is no, how is $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$ actually shared between Alice and Bob (or maybe how is it realized in practise)? Is it just that A and B cannot be written using the standard basis?

Is it just that A and B cannot be written using the standard basis?

Correct.
Entangled qubits are not separable.
You can't factor them into a form like $(a_0 |0\rangle + a_1 |1\rangle) \otimes (b_0 |0\rangle + b_1 |1\rangle)$.

You can get a per-qubit density matrix by tracing out the other qubit, but the resulting density matrix doesn't capture the correlation between the two qubits. It just looks like a maximally mixed state.


Are two non-Turing-recognizable languages closed under union? If I have two languages that aren't Turing-recognizable, is the union between them always not T-recognizable? Why?

Let $U\subseteq \mathbb{N}$ be any unrecognizable set. Let $L_1 = \{0, 2, 4, \dots\} \cup \{2n+1\mid n\in U\}$ and $L_2 = \{1,3,5, \dots\} \cup \{2n\mid n\in U\}$. $L_1$ and $L_2$ are both unrecognizable but their union is $\mathbb{N}$.


What does it mean to fool a function? In computer science papers, I see about the term 'fooling' a function.

What does it mean to fool a function against a particular complexity class? Why is it important?

Let's start with some background. The context is derandomization:

  Given a randomized algorithm, is there an equivalent deterministic algorithm?

Let's consider a randomized algorithm for some decision problem. The algorithm makes use of some random bits $r_1,\ldots,r_n$. In practice, we run this algorithm by using an "informal" pseudorandom number generator, perhaps injecting some physical randomness. Perhaps we can do the same formally?

The best case scenario is that there exists some really complex sequence of random bits that "looks random" for every efficient algorithm; the complexity of the sequence should grow with the complexity of the algorithm, but we want the algorithm generating the sequence to be efficient (though perhaps less efficient than the algorithm itself). While one sequence is perhaps too much to ask for (how exactly would it work, anyway?), but we can hope that a simpler distribution causes the randomized algorithm to act in roughly the same way:
$$
\Pr[A(x,\mathbf{r})] \approx \Pr[A(x,\mathbf{g})],
$$
where $A$ is the randomized algorithm, $x$ is the input, $\mathbf{r}$ is a vector of random bits generated uniformly at random, and $\mathbf{g}$ is the same generated pseudorandomly. What we aim for is for $\mathbf{g}$ not only to be generated efficiently, but moreover we want the support of the distribution to have polynomial size. By enumerating all possible values of $\mathbf{g}$, we can derandomize $A$.

Now back to your question. A pseudorandom sequence $\mathbf{g}$ (or a collection of such sequences) is said to fool an algorithm $A$ if $\Pr[A(x,\mathbf{r})] \approx \Pr[A(x,\mathbf{g})]$. It fools a complexity class if it fools all algorithms in this class.

Another context in which similar concepts appear is cryptography. For example, in cryptography a pseudorandom number generator is defined (roughly) as an efficient algorithm producing a long random sequence which fools every polynomial time distinguisher (a distinguisher a machine trying to distinguish the YES case (truly random) from the NO case (pseudorandom)).


Is rejection sampling the only way to get a truly uniform distribution of random numbers? Suppose that we have a random generator that outputs
numbers in the range $[0..R-1]$ with uniform distribution and we
need to generate random numbers in the range $[0..N-1]$
with uniform distribution.

Suppose that $N < R$ and $N$ does not evenly divide $R$;
in order to get a truly uniform distribution we can use the
rejection sampling method:

if $k$ is the greatest integer such that $k N < R$
pick a random number $r$ in $[0..R-1]$
if $r < k N$ then output $r \mod N$, otherwise keep trying with other random numbers r', r", ... until the condition is met

Is rejection sampling the only way to get a truly uniform discrete distribution?

If the answer is yes, why?

Note: if $N > R$ the idea is the same: generate a random number $r'$ in $[0..R^m-1], R^m >= N$, for example $r' = R(...R(R r_1 + r_2)...)+r_m$ where $r_i$ is a random number in the range $[0..R-1]$

Yes and no, depending on what you mean by “the only way”. Yes, in that there is no method that is guaranteed to terminate, the best you can do (for generic values of $N$ and $R$) is an algorithm that terminates with probability 1. No, in that you can make the “waste” as small as you like.

Why guaranteed termination is impossible in general

Suppose that you have a deterministic computation engine (a Turing machine or whatever floats your boat), plus an oracle that generates random elements of the $R$-element set $[0..R-1]$. Your goal is to generate an element of the $N$-element set $[0,N-1]$. The output of your engine depends only on the sequence of values returned by the oracle; it is a function $f$ of that potentially infinite sequence $(r_0, r_1, r_2, \ldots)$.

Suppose that your engine calls the oracle at most $m$ times. There might be traces for which the oracle is called less than $m$ times; if so, calling the oracle extra times so that it is always called exactly $m$ times does not change the output. So without loss of generality, we assume that the oracle is called exactly $m$ times. Then the probability of the outcome $x$ is the number of sequences $(r_0, \ldots, r_{m-1})$ such that $f(r_0, \ldots, r_{m-1}) = x$. Since the oracle is a uniform random generator, each sequence is equiprobable and has the probability $1/R^m$. Hence the probability of each outcome is of the form $A/R^m$ where $A$ is an integer between $0$ and $R^m$.

If $N$ divides $R^m$ for some $m$, then you can generate a uniform distribution over $N$ elements by calling the random generator $m$ times (this is left as an exercise to the reader). Otherwise, this is impossible: there is no way to obtain an outcome with probability $1/N$. Note that the condition is equivalent to saying that all of $N$'s prime factors are also factors of $R$ (this is more permissive than what you wrote in your question; for example you can pick a random element among 4 with a 6-sided fair die, even though 4 does not divide 6).

Reducing the waste

In your strategy, when $r \ge k\,N$, you don't have to re-draw immediately. Intuitively, there's a bit of entropy left in $[k\,N .. R-1]$ which you can keep in the mix.

Assume for a moment that you will in fact keep generating random numbers below $N$ forever, and you generate $u$ of them at a time by making $d$ draws. If you do a straightforward rejection sampling on this grouped generation, the waste over $d$ draws is $\dfrac{R^d - k\,N^u}{d}$, i.e. the remainder $R^d \mathbin{\mathrm{mod}} N^u$ divided by the number of draws. This can be as little as $\gcd(R,N)$. When $R$ and $N$ are coprime, you can make the waste arbitrarily small by picking sufficiently large values of $d$. For general values of $R$ and $N$, the calculation is more complicated because you need to take into account the generation of $\gcd(R,N)$ and $N/\gcd(R,N)$ separately, but again you can make the waste arbitrarily small with large enough groups.

In practice, even with relatively inefficient random numbers (e.g. in cryptography), it is rarely worth doing anything but simple rejection sampling, unless $N$ is small. For example, in cryptography, where $R$ is typically a power of 2 and $N$ is typically hundreds or thousands of bits, uniform random number generation usually proceeds by straight rejection sampling in the desired range.


Minimal length of a string that contains two strings We have two strings $a,b$. I want to find string $c$ that includes $a$ as a subsequence and includes $b$ as a subsequence and the length of $c$ is minimal.  Is there an efficient algorithm for this problem?

For example, if $a=1011$ and $b=0100$, the minimal string that include both: $c=101100$.  As you can see string $c$ includes both $a$ and $b$ (with the characters of $a$ appearing in the same order in $c$, possibly with other characters interspersed, and the same for $b$).

I think it can be solved by a dynamic programming algorithm.

Following the explanation on Wikipedia,

obtain the longest common subsequence of $a$ and $b$ with a (quite elementary) dynamic programming approach and
insert the characters which are not part of the LCS in-order and in appropriate positions.

Note that the result of neither step is necessarily unique.

Writing actual (pseudo)code, correctness proof and runtime analysis are easy exercises.


Asymptotic growth of a function containing a sum How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails I take the limis of f'(x)/g'(x). But I'm not sure what to do in the following task (to prove whether the marked statement is true or not):

There is an explicit formula for $\sum_{i=0}^n i^3$, but even without it, you can estimate
$$
\int_0^n x^3 \, dx \leq \sum_{i=0}^n i^3 \leq \int_1^{n+1} x^3 \, dx.
$$
Since $\int x^3 \, dx = x^4/4$, this shows that the sum is very close to $n^4/4$, and in particular is $\Theta(n^4)$.

(The explicit formula states that the sum equals $n^2(n+1)^2/4$.)


Is there a task that is solvable in polynomial time but not verifiable in polynomial time? A colleague of mine and I have just hit some notes of one of our professors. The notes state that there are tasks that are possible to solve in polynomial time (are in the class of PF) but that are NOT verifiable in polynomial time (are NOT in the class of NPF).

To elaborate about these classes: We get some input X and produce some output Y such that (X,Y) are in relation R representing our task. If it is possible to obtain Y for X in polynomial time, the task belongs to the class of PF. If it is possible to verify polynomial-length certificate Z that proves a tuple (X,Y) is in relation R in polynomial time, the task belongs to the class of NPF.

We are not talking about decision problems, where the answer is simply YES or NO (more formally if some string belongs to some language). For decision problems it appears that PF is a proper subset of NPF. However, for other tasks it might be different.

Do you know of a task that can be solved in polynomial time but not verified in polynomial time?

This is only possible if there are many admissible outputs for a given input. I.e., when the relation $R$ is not a function because it violates uniqueness.

For instance, consider this problem:

  Given $n \in \mathbb{N}$ (represented in unary) and a TM $M$, produce another TM $N$ such that $L(M)=L(N)$ and $\# N > n$ (where $\# N$ stands for the encoding (Gödel number) of $N$ into a natural number)

Solving this is trivial: keep adding a few redundant states to the TM $M$, possibly with some dummy transitions between them, until its encoding exceeds $n$. This is a basic repeated application of the Padding Lemma on TMs. This will require $n$ paddings, each of which can add one state, hence it can be done in polynomial time.

On the other hand, given $n,M,N$ it is undecidable to check if $N$ is a correct output for the inputs $n,M$. Indeed, checking $L(M)=L(N)$ is undecidable (apply the Rice theorem), and the constraint $\#N > n$ only discards finitely many $N$s from those. Since we remove a finite amount of elements from an undecidable problem, we still get an undecidable problem.

You can also replace the undecidable property $L(M)=L(N)$ to obtain variations which are still computable but NP hard/complete. E.g. given $n$ (in unary) it is trivial to compute a graph $G$ having a $n$-clique inside. But given $n,G$ it is hard to check whether a $n$-clique exists.


Balanced allocation-Hash table- overflow probability My question is related to this:
Hash-Table in Practice

In [1] page 7, it is said that  if we throw $n$ balls into $k$ bins, then each bin contains at most $\frac{n}{k}+O(\sqrt[2]{(\frac{n}{k})\log k}+\log k)$ elements with a high probability.

Question 1: Why is $O()$ used in the above estimation?

Question 2: Does it mean the probability that a bin contains more than the above value is negligible?

[1]. http://www.pinkas.net/PAPERS/FNP04.pdf

A more formal statement of the claim is as follows. There is a constant $C > 0$ and for each $k$, a function $\epsilon(n)$ satisfying $\lim_{n\to\infty} \epsilon(n) = 0$, such that if you throw $n$ balls into $k$ bins, then with probability at least $1-\epsilon(n)$ the contents of each bin is at most $ \frac{n}{k} + C(\sqrt{(\frac{n}{k})\log k}+\log k)$.


What is the significance of the semi clustering formula in the Google Pregel paper? Semi clustering algorithm is mentioned in the Google Pregel paper. The score of a semi cluster is calculated using the below formula

$\qquad \displaystyle S_c =\frac{I_c - f_BB_c}{\frac{1}{2}V_c(V_c - 1)}$

where

$I_c$ is sum of the weights of all the internal edges,
$B_c$ is the sum of the weights of all the boundary edges,
$V_c$ is the number of edges in the semi cluster and
$f_b$ is the boundary edge score factor (user defined between 0 and 1).

The algorithm is pretty straight forward, but I could not understand how the above formula was derived. Note that the denominator is the number of edges possible between $V_c$ number of vertices.

Could someone please explain it?

Think about what a "good" cluster is. It is a set of nodes which

are strongly interconnected (strong cohesion) and
weakly connected with nodes outside of the cluster (weak coupling).

In particular, the connection among the nodes should be stronger than the connection with the outside. And this is what they do there: $I_c$ is a measure for cohesion -- more and stronger edges inside the cluster mean more cohesion -- and similarly $B_c$ is a measure for coupling. $f_B$ is used to control the influence of coupling.

As for the denominator, they justify it in the slides:

  The score is normalized by dividing with the number of
  vertices in the clique, so that large clusters do not receive
  artificially high scores.

That's actually wrong, but the idea is the same: they divide by the number of edges there could be -- which makes sense because they "count" edges in the numerator, too -- in order to get rid of size effects. Without this rescaling, a large cluster (with many edges) would have a higher score than a smaller on with the same or even better properties. You only want to score the quality of the clusters, though, so rescaling is in order.

I daresay that $\frac{I_c}{f_B B_c}$ would also make sense (and scale itself). Usually, such scores are formulated ad-hoc and their usefulness validated by experiments (over time). That is, somebody wrote it down, used it for clustering, looked at images and was satisfied with the result. Depending on what semantic the edge weights have, the score may also be a "good" approximation for a more complicated one that is harder to compute or makes clustering (computationally) harder. That said, most clustering algorithms in use are approximations -- because clustering is NP-hard -- so the choice of auxiliary score may influence runtime and result quality of those algorithms.


Pool of photos for term extraction I need a pool of photos (if possible with description) for my project. I mainly have to perform term extraction for semantic searching. Is there something available out there that is made available for such kinds of thing?

I'm going to mine the description of these photos, maybe build ontologies and then perform search on them. The result of the mining might give useful terms about the pictures.

One good way is to use Flickr. For your project you could use available API for downloading photos with related information.

If you are using Java you could use the classes on Google Codes.


Probably you should ask questions about how to ask on MathStack on their meta site! Each site on Stack Exchange has a Meta site to ask questions about asking questions! They even have a tutorial there: https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference

However, learning how to typeset mathematics is something Computer Science students and researchers have to learn how to do, so perhaps it could be considered just about on-topic!

MathJax is based on LaTeX which is a page description language used for writing documents which happens to be quite good at writing maths. LaTeX (created  by Leslie Lamport) was built upon TeX which was created by Donald Knuth. Both Computer Scientists.

The simplest way of using MathJax is to just use the dollar symbol $ to quote or surround your formula. If we take your first formula:

((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4)

Put it with the dollars, we get:

$((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4)$

which displays this:

$((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4)$

Now perhaps you want that to be a bit neater. They you can replace the slashes by some better arrangement and make them fractions. In MathJax w can invoke layout function by using the backslash \ to indicate a layout function name and give its arguments within curly braces {}. We want the \frac function like this:

$\frac{((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))}{(4)}$

$\frac{((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))}{(4)}$

We can do that again for each fraction:

$\frac{((50^A)*(((\frac{(50^B)((\frac{(50^C)+1)}{(4)}))+1)}{(4)}))}{(4)}$

$\frac{((50^A)*(((\frac{(50^B)((\frac{(50^C)+1)}{(4)}))+1)}{(4)}))}{(4)}$

Which can be tidied up further, but that gives you the basics!


2 SAT variants complexity class Question:
Which of the following languages are in P? which in NP? other classes?

a. EXACTLY-2-CNF (every clause in the formula has 2 differenet literelas)- does there exist a satisfying assignment s.t. at most k variables are TRUE.

b. same language but this time in each clause one literal is negated and the other isn't.

c. SAT-2-NAE - every clause has exactly 2 literals, is there an NAE satisfying assignment to the formula

d. mono-SAT-2-NAE - every clause as exactly 2 literals, none of them negated and it has a satisfying assignment

Thoughts:
We tried a lot of reductions from 2SAT and other problems and cannot really determine most of the questions. We'd like to know what is the effect of the "monotone" property on the satisfiability such formulae... We'd also like some hints on how to reduce to these problems.

b. is completely trivial - just set each variable to FALSE.

d. trivially reduces to c.    c. reduces to d. as follows:

For each double-negative clause, remove the negatives.  Replace each

single-negative clause with 2 clauses, each of which has one of the original clause's variables

and a new variable that's shared with the other of the 2 new clauses but otherwise unused.

That works because:

for 2-variable clauses, NAE is just ≠

for boolean variables,    x  NAE  not y    simplifies to  x = y

for boolean variables, [there exists a y such that    x ≠ y  and  y ≠ z ]  if and only if  x = z

By    variables <-> vertices  and  clauses <-> edges  ,    c. is equivalent to bipartiteness.

Bipartiteness is logspace-complete.  (Thus, c. and d. are logspace-complete.)

By throwing in k extra variables to handle "at most" vs. "exactly", a. is in W[P].

By    vertices -> variables  and  edges -> clauses  ,    vertex cover reduces to  a. .

(Thus, for unrestricted k, a. is NP-complete.)  However, a. is fixed-parameter tractable.

Proof:
By replacing each clause with k+1 copies of itself and then [for each variable, putting in a

clause whose literals are both the negation of that variable], a. reduces to Almost 2-SAT.

By part 2.1 of that paper, that paper handles the case of clauses whose 2 literals are the same.

Theorem 7 of that paper explicitly covers "possible repeated occurrences of clauses".

I have no clue regarding possible kernalizability of a. or

$\big[$the space requirements of algorithms for a. whose runtimes aren't  max$\hspace{-0.03 in}\big(\hspace{-0.04 in}$nΩ(k),$\hspace{.02 in}$2Ω(n)$\hspace{-0.03 in}\big)\big]$.


Are neural networks a type of reinforcement learning or are they different? Can neural networks be considered a form of reinforcement learning or is there some essential difference between the two?

By the same token could we consider neural networks a sub-class of genetic algorithms?

According to my current understanding the taxonomy is kind of like this:

   Reinforcement Learning
      Evolutionary Algorithms
         Genetic Algorithms
            Neural Networks

Is this right?

What is a neural network?

Neural networks are algorithms for function approximation. I like to call them a construction kit for functions. Their basic building block is a neuron, commonly visualized like this:

You can see the $n$ inputs $x_1, \dots, x_n$ ($x_0$ is typically constant 1), each multiplied with a weight $w_i \in \mathbb{R}$. This gets summed up and an activation function $\varphi$ (e.g. sigmoid $\varphi(x) = \frac{1}{1+e^{-x}}$) gets applied. So a neuron is a function

$$f(x_0, \dots, x_n) = \varphi(\sum_{i=0}^n x_i w_i)$$

The learning is just adjusting the weights $w_i$ automatically to something that makes sense in your context.

Now we can have arbitrary numbers of inputs $x_i$, but to have an arbitrary number of outputs we need more than one neuron. To get our model much more flexible, we stack them to a so called multilayer Perceptron (MLP):

So you can see, the output of one neuron (perceptron) can be the input of another! With backpropagation (a good implementation of gradient descent for this type of model) you can automatically adjust the weights.

What is reinforcement learning?

In machine learning you can distinguish 5 types of problems:

Regression: Predicting a continuous variable

You have a photo of a person and you want to tell how old the person is (e.g. howhot.io)

Classification: Predicting a variable with finite possible values

MNIST: You get a 28px x 28px image. You know it is either 0, or 1, or 2, ..., or 9. So a digit. You have to say which one.
ImageNet: You get a bigger image. You have to decide which one of a 1000 classes it is (dog, cat, car, house, ...). You can be sure it is one (and exactly one) of those.
http://write-math.com: Classify a handwritten symbol into about 380 classes
https://howhot.io/: Classify gender

Clustering: Grouping data

You have a lot of portrait images (or crops of images). You know there is exactly one persons face on it. You don't know how many people there are in total. Now you would like to group it so that each group is one person.
Species: You properties of animals and you want to group them. So you want a hierarchical clustering which puts closely related animals (dogs, cats; fly, moscito) closer together than not related ones (dogs, flys)

Collaborative Filtering: Filling gaps

Netflix: You have a lot of movies, a lot of ratings. However, not every person rated every movie. In fact, probably no person did. But you want to fill the gaps so that you can tell the users which movies they should watch because they will probably like it.
Amazon: pretty much the same as with Netflix, but for all kinds of products

Reinforcement learning (RL): Learning with environment

Self-driving cars
Playing games (e.g. Backgammon, Go, Atari (video))

What makes RL very different from the others is that you typically don't have a lot of data to start with, but you can generate a lot of data by playing. You have to deal with the problem that you have to make decisions, but it is not clear what is good (delayed reward). For example, it might take several moves until you know in Go if a move was smart.

What is different between neural networks and RL?

Neural networks are algorithms, RL is a problem type. You can approach RL with neural networks.

What is the relationship between neural networks and genetic algorithms?

Search for "the five tribes of machine learning", e.g. the image on http://www.welchlabs.com/blog/2016/2/16/whats-next-for-welch-labs


Is matching with mismatches a special(parametrized) case of Closest String problem? I am a bit confused. Somehow I have a problem connecting two problems together. The Closest String problem and the problem of matching with mismatches. They seam to be related but, I fail to see the connection. The Closest String problem is defined as :

Instance: Strings $S_{1},S_{2}...S_{n}$ over alphabet $\Sigma$ of length $L$ each and a non-negative integers $d$ and $n$.
Parameters: $n,d$
Question: Is there a string $s$ of length $L$ such that $\delta(s,S_{i})\leq d$ for all $i=1..n$?

Note: $\delta(x,y)\leq d$ is the Hamming distance between $x$ and $y$.
This problem is proven to be NP-complete.
On the other hand we have a problem of matching with mismatches, which is described as:

The problem of string matching with $d$ mismatches consists of finding all occurrences of a pattern of length $m$ in a text of length $n$ such that in at most $d$ positions the text and the pattern have different symbols. In the following, we assume that $0 < d < m$ and $m\leq n$.

Landau and Vishkin gave the first (to my knowledge) efficient algorithm to solve this problem in $O(kn)$ time.
Now my question is:
Is matching with mismatches, or can it be seen, as a special parametrized case of the Closest String problem and how is this connection made?

In the latter you are given the string $s$ that you are looking for in the former.

An algorithm for the first one is to search for a string $s$ (try all strings) and run the latter procedure and verify that the set you get is the entire set.


Sorting Algorithm which prevents strings with at least one identical char from being next to each other Imagine this Table:

All combinations represented in the table (1,2 ; 1,3 ; 1,4 ; etc.) are stored as strings in an array with a total of  (n^2-n)/2  elements (combinations).

I'm looking for an algorithm that sorts the elements so no number of a combination is next to a combination with the same number in it.

For example a sorted array with n=5: {1,2 ; 3,4 ; 5,1 ; 2,3 ; 5,4 ; 1,3 ; 2,5 ; 4,1 ; 3,5 ; 4,2}

Of course this algorithm would only work with n > 4.

Think of this like a chess board.  Visit all of the white squares first (in a left-to-right, top-to-bottom scan).  Then visit all of the black squares (in a similar order).


Compute pair of similar list from a collection of lists Given a list of list of integers how to find pair of lists which have overlapping i.e. 1 or more elements are common.

Is it possible to solve without having cartesian product of initial list with itself

Build a hash of element -> list of lists that contain that element. From that it's easy to find all pairs of lists that share an element. Of course listing all pairs is still $O(n^2)$, since there might be quadratically many. But finding just $k$ pairs is $O(k+m)$, where $m$ is the total number of elements in all sets.


What is the exact difference between a latch & a flipflop? From what I have understood :

A Flip Flop is a clocked latch i.e. flip flop = latch + clock
Latch continuously checks for inputs & changes the output whenever there is a change in input
Flip Flop also continuously checks input, but changes the output time determined by clock. [so, even though if inputs are changed, it may not change the output at the same time]
A latch with enable [i.e. gated latch], is different from that of clocked latch.

I am reading from Digital Logic by Morris Mano & Wikipedia.

As far as I understand, the difference is indeed the clock/enable.

A flip-flop samples the inputs only at a clock event (rising edge, etc.)

A Latch samples the inputs continuously whenever it is enabled, that is, only when the enable signal is on. (or otherwise, it would be a wire, not a latch).


Space optimised versions of Coin Change and Knapsack Problems in Dynamic Programming I have recently been focussing on DP formulation and space optimization in dynamic programming of some problems.
I have gone through the standard questions such as 0-1 Knapsack and Coin Change problems.

In the space optimization part, I haven't understood in which order should I fill the table to get the desired result. For instance, In the above 0-1 Knapsack Problem, which asks about max possible sum of values for a weight of at most w.

vector<int> dp(w + 1); // dp[j] max value that can be obtained with weight exactly j
  for (int i = 0; i < n; i++) {
    for (int j = w; j >= weight[i]; j--) // iterating from right to left here
      dp[j] = max(dp[j], val[i] + dp[j - weight[i]]);
  }

In the above snippet why the ordering is important? I am confused because for the space-optimized version of coin change problem mentioned above we iterate from left to right to get total no. of ways to get change, it goes as @qqibros answer shown here

 vector<int>dp(x+1); // dp[i]- no of ways to get coins with value exactly i
for(int i=0;i<n;i++){
  for(int j=a[i];j<=x;j++){ // iterating from left to right here
    dp[j]+=dp[j-a[i]];
  }
  cout<<dp[x]<<endl;

But if I change the above coin change problem adding the constraint that every coin can only be used exactly once, I should iterate from right to left to get the required answer.
For example,N = 4 and S = {1,2,3}, only one solution {1,3} so the output should be 1. And For N = 10 and S = {2, 5, 3, 6}, still only one solution {2, 3, 5} and the output is 1.
Just changing the line from for(int j=a[i];j<=x;j++) to for(int j=x;j>=0;j--) gives the answer.

I am not able to visualize or interpret correctly how ordering changes the value as in both cases the value only depends on previously stored values.

The difference is whether the solution to the "add element i" subproblem being considered (dp[j - weight[i]] or dp[j-a[i]], as the case may be) allows or forbids a contribution from the current element (value of i).

When the inner loop moves right-to-left, at the time dp[j - weight[i]] is evaluated, that table entry has not yet been updated in this iteration of the outer loop, so it definitely does not include a contribution from element i. Thus the candidate solution having value val[i] + dp[j - weight[i]] includes exactly one copy of element i (and the other candidate solution, dp[j], includes exactly zero copies of it).

OTOH, when the inner loop moves left-to-right, at the time dp[j - weight[i]] is evaluated, that table entry has already been updated in this outer loop cycle, so it may represent a solution that already contains an element i, to which we are now considering adding a second element i. In fact it may already contain multiple copies of element i, since that table entry may have been computed as the result of choosing val[i] + dp[j - weight[i] - weight[i]], etc.


Counting an integer's divisors without just enumerating them (or estimating if not possible)? I'm trying to count the number of divisors an integer $n$ has.  The simple way to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$.

For example, 28 has six divisors (1, 2, 4, 7, 14, 28). 15 has four (1, 3, 5, 15). I want to, say, figure out how many divisors 242134575355654335549798955848371716626563756785 has.

I'm not trying to factor the integer; I don't care about what two numbers or what three numbers and so on I can multiply to get $n$.

How can I count (or estimate, if need be) the number of divisors an integer has other than by enumerating them?  I don't need the actual values for each divisor; I just want to count them faster than by just enumerating them.  If that's not possible, I'd be OK with estimating the number of divisors (and, even better, using that estimate to help me find the actual number of divisors).

As far as I know we don't know a smart method of distinguishing between numbers which have $a$ divisors and numbers which have $b$ divisors, unless (say) $a$ is prime (in which case necessarily the number is an $(a-1)$th power of a prime, and we can use root extraction and primality testing). On the other hand, if you factor $n = \prod_i p_i^{d_i}$ then you can compute the number of factors using the formula $\prod_i (d_i + 1)$.


MergeSort k arbitrary words in linear time Given $k$ arbitrary words, such as $\{\text{"fjqke"}, \text{"gbqig"}, \text{"a"}\}$, is there a way to mergesort these words in linear time so that the final output would be "abefgggijkq"? I tried to approach it by first sorting all the words independently and then merging the words into the final output, but sorting all the words takes $O(kn\log n)$ time.

General case:

If there is a linear time sorting algorithm $\mathcal{A}$ for this problem, then one can divide a list into random parts, and use $\mathcal{A}$ to sort. But comparison based sorting has a lower bound $\Omega(n \log n)$. Therefore there is no such algorithm $\mathcal{A}$.

Note: Merge routine combines sorted arrays into one sorted array. There is a similar problem to your problem called k-way merging, but that is also required sorted arrays. The complexity of k-way is $\mathcal{O}(n \log k)$

Finite alphabet case:

If we assume that the alphabet is finite, and in your case it seems only lower case letters then one can use the Counting Sort algorithm.

Assuming that the total length of the words is $n$ and there are at most $t=26$ letters, the Counting sort can sort this array in $\mathcal{O}(n+t)$-time.

To achieve this with Counting sort, you need to convert this into an array and map the letters with an integer. And, call;

 countingSort(array,26)

The Counting sort is not in-place. The space requirement for this question is $\mathcal{O}(t)$

Note 1: Counting sort is not a comparison based sorting algorithm, it uses counting, thus it is not bounded by the lower bound of the comparison based sorting algorithms.
Note 2: Counting sort, also, can be implemented stable.


What is a continuous environment for an agent? I know the environment of an intelligent agent is divided to discrete and continuous. But I think they are relevant to sensors and actuators of the agent itself. Moreover, environment may have many mutable factors,(some continuous, some discrete).

For example for an agent which is an expert system (computer program) to play the role of a physician, what is the environment, is it continuous or discrete?

Please give some examples of continuous environments.

Continuous has its usual definition: a variable that "looks like the real numbers" in the sense that, for any value $x$ that the variable could take and any positive constant $\delta$, there's another value $y$ that the variable could take that's within distance $\delta$ of $x$.  So, for example, the environment of your physician expert system will include things like the patient's temperature and blood pressure, which are both continuous, but it will also include discrete things such as what medicines they're currently taking and substances they're allergic to.  There are also awkward cases such as how much pain they feel, which you might imagine to be continuous but is typically expressed on a discrete scale of 0 to 10.  (I guess it's on a discrete scale partly because it's completely subjective and partly because nobody could distinguish between 3.298364 and 3.298365.)

However, note that your agent is most likely running on a digital computer. Because of this, any inputs it receives will have been rounded to some level of precision, making everything discrete in the end.


Why do we use $\Gamma$ to denote a TM's tape alphabet? In many formal definitions of Turing machines, the Greek letter $\Gamma$ is used to denote the tape alphabet of the TM.

What is the origin of using $\Gamma$ for this? I'm having a hard time imagining what this might stand for.

Following up on @PartialOrder's comment, while $\Gamma$ is not used in Chomsky & Schutzenberger or in Chomsky's 1962/1963 papers on PDAs, it is used in Ginsburg and Greibach 1966 as follows:

  A pushdown automaton (abbreviated pda) is a 7-tuple $M=(K,\Sigma,\Gamma, \delta, Z_0, q_0, F)$ where [...]

Here $K$ is the set of states and $q_0$ is the start state. $\Gamma$ is the finite nonempty set of auxiliary symbols. $F$ is the set of final states. $\Sigma$ is the finite nonempty set of inputs. Etc.

Nowadays we would call the set of states $Q$ if the start state is called $q_0$. I think this just indicates that not too much consistency and reason was required for these letter choices.

This is "original research" but I figure $\Gamma$ may just have been used since it is the first capital Greek letter (to indicate the same type as $\Sigma$) which looks distinctly greek (A and B looking Roman as well).


Text features in decision tree Right now I am doing some problems on application of decision tree/random forest. I am trying to fit a problem which has numbers as well as strings (such as country name) as features. Now the library, scikit-learn takes only numbers as parameters, but I want to inject the strings as well as they carry significant amount of knowledge.

How do I handle such scenario, I can convert string to numbers by some mechanism such as hashing in python. But I would like to know the best practice on how strings are handled in decision tree problems.

Random forests don't allow you to use strings as features.  Instead, if you want to use random forests, you'll need to select new features and do some feature extraction, so that all of your features are numbers.  The features might be some function of the strings, e.g., a histogram of the lengths of the strings, or a count of the number of times each possible word appears in your document (see e.g. bag of words model).

The features that make sense for your application will depend heavily upon your specific application, so we can't give a one-size-fits-all answer.  The right set of features will be heavily domain-specific and application-specific, so you'll need to do some brainstorming about possible features and try out your ideas to see how well they work.  That said, if you want some hints or ideas to jumpstart your brainstorming about possible features that might make sense, the NLP (natural language processing) community might be a good place to start.


How different is the working of SNN (Spiking Neural Network) as compared to a real Neuron System in biological systems? Assuming its one step closer to realism as compared to ANN, DNNs and other Neural Network models, what are the primary differences between a real neuron system and SNN?

There are different types of spiking neural network models:

Hodgkin-Huxley: models the processes within a neuron with electrical parts. This results in differential equations with 4 variables (capacity of the membrane, resistance of the ion channels, balance potentials, openings of the ion channels).
Leaky integrate and Fire (LIF): Probably the simplest SNN; it is only an ordinary first order differential equation
Spike Response Model: models refraction time. It tries only to model the phenomena. Although it is simple, it is still more accurate than LIF.

I don't have a biology background, but I would say the Hodgkin-Huxley model is probably the closest to real neurons. However, as far as I know (which is very little), there is no (effective, plausible) training algorithm. So this is probably the key difference to the brain. Also the topology will certainly be different.

And, of course, we can model much less spiking neurons than we have natural neurons in a human. So the number of neurons is a key difference, too. I've heard SNNs have a few dozend neurons, probably up to several hundred neurons. The biggest MLP (CNN) models I've seen so far have about 150 000 neurons (see Deep Residual Learning for Image Recognition). The human brain has about 86,000,000,000 neurons (see Wikipedia).


Array subset division with equal sums Today I stumbled upon a problem which looked like the partition problem but certainly is different.

Given array of positive integers, guaranteed to not be divisible into two continious subsets of equal sum, remove a ceratin continious subset to form two subsets of equal sum.

Example:

Array: 7 5 9 1 3 9 6
Remove elements 9 and 1 to form array 7 5 3 9 6  that is divisible
into two subarrays of equal sum {7,5,3} and {9,6}

Another example:

Array: 1 10 100
Whichever subset to remove in the second case, it is not possible
to split the array into two parts with the same sum.

The limits for the array are 8000 elements and each element can be 1 bilion in size.

I'am just looking for algorithm help as I thought this was a variation of the partition problem and tried for some time to solve it, but i figured out it's beyond my knowledge. Any kind of help would be appreciated.

Let S denote the solution sum.  Besides the trivial O(1) solution with S=0, other solutions if any can be found by an easy O(n2) method.  Let A denote a given array of positive integers.  Consider two kinds of partitions of A:  (B, C, E, D) and (F, E, G, H), where each letter represents a sequential part of A, with A=B+C+E+D or A=F+E+G+H; C or G possibly empty; with E representing the extracted sequence.  We suppose a solution has either S = sum(B) = sum(C+D) = (sum(A)-sum(E))/2 or S = sum(F+G) = sum(H) = (sum(A)-sum(E))/2, and claim that any solution has either an intact prefix or an intact suffix, or both, uninterrupted by extraction E.

To test for a solution of the first kind:  Let S be a prefix sum of A.  We look for a solution for S by advancing the beginning of E through A, and after each advance, solving (at O(1) amortized cost) for the end of E.  With O(n) prefix sums and O(n) beginnings-of-E, overall cost is O(n2).

Testing for solutions of the second kind is analogous.  The lightly-tested program shown below does this step by testing reversed(A).

#!/usr/bin/env python3
# Program written by James Waldby on 16 June 2019
# re: https://cs.stackexchange.com/questions/101950,
# "Array subset division with equal sums"
# Copyright © 2019 by James Waldby.  Offered without warranty under
# GPL v3 terms as at http://www.gnu.org/licenses/gpl.html

def findPrefixSol(A):
    S=0; U=sum(A); H=U//2; n=len(A); print (A)
    for i in range(n):        # prefix = first i elements
        S += A[i]
        if S>H: break
        Esum = 0                # sum of extract E
        Etarget = U - 2*S       # required size of E
        k = i+1                 # k -> after last element of E
        for j in range(i+1, n-1): # j -> first element of E
            while Esum < Etarget and k<n-1:
                Esum += A[k]
                k += 1
            if Esum > Etarget:
                Esum -= A[j]    # remove first element of E
                continue        # go try next E
            if Esum < Etarget:
                break           # can't extract enough to win; advance i
            print('Sol. for partition {}...{}...:  S={}, Es={}, U={}'.format(A[:i+1], A[j:k], S, Esum, U))
            break

A=[7, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))
print()
A=[7, 5, 9, 1, 5, 9, 1, 3, 9, 9, 1, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))


Dfs algorithm and cycles question Is it true or false that for running a dfs on an undirected graph G with a simple cycle than this cycle will have exactly one back edge?

Looks to me likes its true ,is it?

No, it is not true. Consider the graph with vertices 1, 2, 3, 4, 5, 6 and edges 12, 23, 34, 45, 46, 56, 61. The dfs starting at vertex 1 yields two back egdes for the cycle (1,2,3,4,6).


If current time in milliseconds is considered good enough random seed for a pseudorandom number generator, why not just use that time directly? I was reading about pseudorandom number generators and how they need a seed and how that seed is usually current system time in milliseconds. One of the most common algorithms is the linear congruential generator, which is an algorithm that based on some fixed constants and this seed through some mathematical computations gives the final pseudorandom output.

But what are the disadvantages of using this time directly as a pseudorandom number?

The key property that we want from (non-cryptographic) pseudorandom numbers is that they "look" independent. In particular, say you have some algorithm that requires a PRNG to perform well and you give it a current time function as a PRNG. Then, if the algorithm repeatedly queries what is supposed to be a PRNG, it will actually see that it gets the same value many times in a row until, until it eventually increments by one. These values are very, very far from random and can be detrimental to algorithmic performance.


Isn't polynomial identity testing over arithmetic *expressions* trivial? Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial can be made exponentially large by repeated squaring. This question addresses the issue of how to work around this and keep the problem in randomized polynomial time.

On the other hand, when the problem is initially presented (e.g. here), it is often illustrated over arithmetic expressions containing only constants, variables, addition, and multiplication. Such polynomials have total degree at most polynomial in the length of the input expression, and for any such polynomial the size of the output value is polynomial in the size of the input values. But since a polynomial of degree $d$ has at most $d$ roots, isn't this trivial? Just evaluate the polynomial over the rationals at any $d + 1$ distinct points and check whether the result is zero at each point. This should take only polynomial time. Is this correct? If so, why are arithmetic expressions without shared subexpressions often used as examples, when sharing is essential to the difficulty of the problem?

For a univariate polynomial $p(x)$, yes, it's that easy.

For a multivariate polynomial $p(x_1,x_2,\dots,x_k)$, no, no such algorithm works.

In particular, when you write "a polynomial of degree $d$ has at most $d$ roots", that is true for univariate polynomials $p(x)$, but it is not true in general for multivariate polynomials.  Ricky Demer gives a simple example: $p(x,y) = xy$ is of degree two, but has infinitely many roots.


How can every regex be accepted by an infinite number of finite automata? In The (New) Turing Omnibus by A K Dewdney, chapter 2, it says:

  Moreover, for every regular expression there is an automaton which accepts the language symbolized by that expression. Thus, in a sense, regular expressions capture precisely the behavior of automata in terms of the language they accept. However, for every regular expression there are an infinite number of automata which accept that language.

But for a simple regex, e.g. a, I can think of exactly one finite automaton that corresponds to it: (start state) -a-> (accepting state). I don't see how there can be an infinite number. What am I missing?

For context, at this point in the book he has not yet introduced DFAs vs NFAs, and all examples of automata so far have been DFAs.

There are at least two ways of doing this.

The first is kind of trivial: there's no requirement that all states of an automaton be accessible from the start state. So, take your favourite automaton that accepts some language, and then add as many new states as you want, with arbitrary connections between them, as long as they're not connected to the original automaton.

A second way keeps the automaton connected. I'll give an informal description; I wrote a more formal one in response to another question. Take your favourite automaton and make $n$ copies of every state. Modify the transition function so that if, in the original automaton, $\delta(q,a)=q'$ then, in the new automaton, reading $a$ in the $i$th copy of state $q$ takes you to the $(i+1)$st copy of $q'$ (with addition modulo $n$). The start state is the first copy of the original start state; every copy of an accepting state is accepting. This isn't guaranteed to keep the automaton connected but you can delete the disconnected states and you are guaranteed to end up with an automaton with at least $n$ states.


Does $O(1) * o(1)$ equal a $o(1)$ function? Say I have two functions $f(x) = O(1)$ and $g(x) = o(1)$. Let $h(x) = f(x)g(x)$. Is $h(x) = o(1)$?

By definition of small-o $g(x)$ must approach 0 as $x \rightarrow \infty$, so I think yes. However, how can I formally prove it? Is my intuition correct?

The formal proof would proceed along these lines:
Let $C$ be a constant such that $f(n)\le C$ for all $n$ (such a constant exists since $f(n)\in O(1)$).
Then
$$\lim_{n\to \infty}f(n)\cdot g(n)\le C\cdot \lim_{n\to \infty}g(n)=0$$
So $f(n)g(n)\in o(1)$.


What does "lookahead" refer to? I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word.
What does "lookahead" refer to? How does this relate to LL, LR, LALR? Basic examples would be great, as I'm not well versed in this subject.

"A good driver drives in three cars. His own car, the car behind him, and the car in front of him". (Bertold Brecht).
"Lookahead" is what you do when you drive a car. You look ahead and make decisions not just based on things around you, but also based on things ahead of you.
A parser with a lookahead of 1 makes decisions based on the current symbol and the symbol ahead of it. That often keeps it from making the wrong parsing decisions.


Definition of a TM accepting a word The following is a quote from Sipser's "Introduction to the theory of computation"

  A Turing machine $M$ accepts input $w$ if a sequence of configurations
  $C_{1}, C_{1}, \ldots , C_{k}$  exists, where

  $C_{1}$ is the start configuration of $M$ on input $w$,
  Each $C_{i}$ yields $C_{i+1}$ , and
  $C_{k}$ is an accepting configuration.

The "if a sequence of configurations $C_{1}, C_{1}, \ldots , C_{k}$  exists" is a bit confusing. This is a deterministic TM, so there is only one sequence of configurations for a given machine and word, right? For instance, wouldn't the following do as a definition?

  A Turing machine $M$ accepts input $w$ if the state in the final configuration in $M$'s run on $w$ is an accepting state

Obviously, one has to formally define first what the run of a machine on a given word means.

There are two reasons to use this kind of definition:

It is a formal way to define the run of the machine.
It generalizes to the nondeterministic setting.

In the deterministic setting, an equivalent definition would be:

Define a (possibly finite) sequence $C_1,C_2,\ldots$ as follows:

$C_1$ is the start configuration of $M$ on input $w$,
For $i \geq 1$, $C_{i+1}$ is the unique configuration yielded by $C_i$, if such a configuration exists.

The machine $M$ accepts the input $w$ if the sequence is finite, and the last configuration is accepting.

This is not dramatically better than the quoted definition, and it doesn't generalize to the nondeterministic setting. It is a matter of taste which of the two to prefer.


Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular Given that language $L = \{a = b ⊕ c \mid a, b, c ∈ \{0,1\}^*, a = b \oplus c\}$, with an alphabet $Σ = \{⊕, =, 0, 1\}$, I need to prove that this language is not regular. The following is as far as I have gotten in my proof, but I am getting stuck when showing why it is contradicting the pumping lemma:

$s = (1^p = 1^p ⊕ 0^p)$

$x = 1^l$

$y = 1^m$, where $l+m \le p$ and $m > 0$

$z = (1^{p-l-m}=1^p ⊕ 0^p)$

Taking $i=2$, $xy^2z = (1^l1^{2m}1^{p-l-m}=1^p ⊕ 0^p) = (1^{p+m}=1^p ⊕ 0^p)$

—This is where I am getting stuck. From my example, this appears to be a contradiction, but there is nothing in the language dictating that $b$ and $c$ be of equal lengths. Were they to be different lengths, it could certainly be possible that no contradiction would be found by adding $m$ to $p$. How could I fix my proof via pumping lemma?

---EDIT: SECOND TRY---

$s = ((10)^p = (01)^p ⊕ (10)^p)$

$x = (10)^l$

$y = (10)^m$, where $l+m \le p$ and $m > 0$

$z = ((10)^{p-l-m}=(01)^p ⊕ (10)^p)$

Taking $i=0$, $xy^0z = ((10)^l(10)^{p-l-m}=(01)^p ⊕ (10)^p) = ((10)^{p-m}=(01)^p ⊕ (10)^p)$

Now, I have that $|a|<|b|$ and $|a|<c$, which is not possible, since the result of the exclusive-or must contain a leading 1, which cannot be truncated to a smaller string length. Therefore, this is a contradiction.

Is this a contradiction strong enough to prove the language is not regular? It only works in the case of a leading 1; do I need to show something that is a contradiction even with leading 0's?

Suppose $L$ were regular. Let $p$ be the pumping constant assumed to exist and consider the string

$$s = 1^p = 1^p \oplus 0^p$$

Clearly, $|s| \geq p$ so for some strings $x,y,z$ we have $s = xyz$ where

$|xy| \leq p$
$|y| > 0$
$xy^iz \in L$ for all $i \geq 0$

If condition 1 is to hold, $y$ must be a string of $1$s. If condition 2 is to also hold, then $y = 1^k$ for some $k > 0$. But then condition 3 fails, since $xy^0z \notin L$.

For $xy^0z =  1^{p-k} = 1^p \oplus 0^k$, and this identity is false irrespective of whether we require $w_1 \oplus w_2$ to be defined for strings of the same length only, or in general.


Prove that $L$ is closed under Kleene star iff $L=NL$ Prove that $L$ is closed under Kleene star iff $L=NL$

Hi,
I am trying to solve this exercise, but it is quiet difficult.
Of course first part is very easy:
Let assume that $L=NL$.  Lets consider language $A\in L$. We show that also $A^*\in L$.  It is easy because we can guess partition of word $w=w_1w_2..w_k$ and launch algorithm for each part. It is possible because $L=NL$ so being in class $L$ we can use guessing.

However, when we assume that $L$ is closed under Kleene star I am hopeless. Obviously, from assumption we know that $A\in L$ then also $A^*\in L$.  Of course, we know that $L\subseteq NL$.  However I must now show that $NL\subseteq L$ using assumption. This is hard for me.

Let $A$ be the language consisting of the following words:
$$
(u,v)|\Sigma^*|(v,w),
$$
where $u,v,w$ are numbers encoded in binary. This language is in $\mathsf{L}$.

Given a directed graph $G$, we can encode it as a list of edges in the following way:
$$
(x_1,y_1)(x_1,y_1)|(x_2,y_2)(x_2,y_2)|\cdots|(x_m,y_m)(x_m,y_m)
$$
where $x_i,y_i$ are vertex numbers encoded in binary. Furthermore, this string, which we denote by $\langle G \rangle$, can be output by a logspace machine.

Suppose now that we are given two vertices $s,t$, and that there is an $s$-$t$ path of length $\ell$ of the form $(s,x),\ldots,(y,t)$ in $G$. Then I claim that for all $L \geq \ell$,
$$
(s,x)|\langle G \rangle^L|(y,t) \in A^*.
$$
Conversely, if such a string belongs to $A^*$ then there is an $s$-$t$ path in $G$. In other words,
$$
\exists \text{$s$-$t$ path in $G$} \longleftrightarrow (s,t) \in G \lor \exists x,y \text{ s.t. } (s,x)|\langle G \rangle^n|(y,t) \in A^*.
$$

If we assume that $\mathsf{L}$ is closed under Kleene star then $A^* \in \mathsf{L}$, and so we can evaluate the right-hand side formula in logspace. Since $s$-$t$ reachability is $\mathsf{NL}$-complete, we deduce that $\mathsf{L}=\mathsf{NL}$.


Is it possible to solve 3SUM in $O(n^2)$ time? Problem: 3SUM

Input: Three lists A, B and C of integers and an integer k. Each list contain $n$ numbers.
Task: Decide whether there exists a tuple (a, b, c) ∈ A × B × C such that a + b + c = k.

Question : Is it possible to solve 3SUM in $O(n^2)$ time using constant space ? Prove or disprove it

A $O(n^2)$ algorithm (with $O(1)$ space) is as follows:

Sort $A$, $B$, and $C$ individually in $O(n \log n)$.
For each $a \in A$:

Search a pair of $b \in B$ and $c \in C$ such that $b + c = k - a$. This can be done in $O(n)$ by traversing $B$ from the smallest to the largest and $C$ from the largest to the smallest. (Tip: Comparing $b + c$ with $k-a$ each time.)


About independent set in triangle free graphs From Wikipedia :

  An independent set of $\sqrt{n}$ vertices in an $n$-vertex triangle-free graph is easy to find: either there is a vertex with more than $\sqrt{n}$ neighbors (in which case those neighbors are an independent set) or all vertices have less than $\sqrt{n}$ neighbors (in which case any maximal independent set must have at least $\sqrt{n}$ vertices)

Why does any maximal stable set have at least square root of $n$ vertices?

Thanks.

The point is that the graph is triangle free, so if $j$ and $k$ are both neighbours of $i$, then the edge $\{j,k\}$ is not in the graph.  This means that $N_i = \{j : \text{$i$ is a neighbour of $j$}\}$ is an independent set for any $i$.

The other fact being used is that a graph with $n$ vertices of maximum degree $\Delta$ has an independent set of size at least $\lfloor n/(\Delta+1)\rfloor$.


Find the k-th member of the recursive sequence I have a recursive sequence: $a_n = 5a_{n - 1} + 2a_{n-2} + 3$, for $n > 1$. And I could return $k-th$ member in $O(\log{k})$ of sequence i.e. $a_k$.
I know how to get the formula of the $k-th$ member using the generating function method, but I need to find a more algorithmic solution.
For example, like this one.

Something like this?

$$
\begin{bmatrix}
5 & 2 & 3 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\cdot
\begin{bmatrix}
a_n     & a_{n-1} & 0 \\
a_{n-1} & a_{n-2} & 0 \\
1 & 1 & 0
\end{bmatrix}
=
\begin{bmatrix}
a_{n+1} & a_n     & 0 \\
a_n     & a_{n-1} & 0 \\
1       & 1       & 0
\end{bmatrix}
$$

Therefore $a_k$ is the first element of the matrix:
$$
\begin{bmatrix}
5 & 2 & 3 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}^{k-2}
\cdot
\begin{bmatrix}
a_2     & a_1 & 0 \\
a_1 & a_0 & 0 \\
1 & 1 & 0
\end{bmatrix}.
$$

This only requires $O(\log k)$ matrix multiplications, each of which can be done using a constant amount of arithmetic operations on scalars.


How can I reduce the time of this program I solved a problem similar to the knapsack problem.

There are two packages with a capacity of $P$ on a production line. We want to put $N$ items in them with the weights $w_1,...w_n$ in a pre-defined order (the best order). We can put an item in the package 1 or the package 2 or close one package and replace it with a new package and put the item in it. What is the minimum number of packages?

Let $m(n,p1,p2)$ be the minimum number of packages for $n$ items where the capacity of package 1 is $p1$ and the capacity of the package 2 is $p2$.

I must keep track of the free capacity of each package which is not always $P$ (empty state)

let $w_n$ be the weight of the $n_{th}$ item.

It's my solution using dynamic programming:

def packaging(N, P1, P2, w):
    M = np.zeros((N+1, P1+1, P2+1))
    for n in range(N+1):
        for p1 in range(P1+1):
            for p2 in range(P2+1):
                wn = 0 if n == 0 else w[n-1]
                if n == 0:
                    M[n][p1][p2] = 0
                elif wn > p1 and wn > p2:
                    M[n][p1][p2] = M[n-1][p1][p2] + 1
                elif wn > p1:
                    M[n][p1][p2] = M[n-1][p1][p2-wn]
                elif wn > p2:
                    M[n][p1][p2] = M[n-1][p1-wn][p2]
                else:
                    M[n][p1][p2] = min(M[n-1][p1-wn][p2], M[n - 1][p1][p2 - wn])
    return M[N][P1][P2]

Its order is $O(NP^2)$. There is an $O(NP)$ solution for it. How can I enhance my solution to reach it?

Further updates might come to reformat the solution in a mathematical notation.

Source: Tehran University, Fall 2018, Advanced algorithms practice

A very nice question.

Here is the brief idea of a more efficient algorithm. The central idea is how to fill one package and close it with minimal unfilled capacity left. That is a standard knapsack problem that can done efficiently with dynamic programming.

However, now we have two packages available, each might have different initial capacities available, as you have pointed out.

What to do? Then do two knapsack problems at the same time!

Right after you have closed one package, you have two packages, one with $a_1$ available capacity and the other with $a_2$ available capacity. We have two knapsack problems here: how to fill the one with $a_1$ capacity as much as possible without bursting the other one and how to fill the one with $a_2$ capacity as much as possible without bursting the other one. Solve them separately. Compare the result to find which one get less free capacity left. Choose that package and its maximal filling found just now and close it. Fill the other one with the items that should have been used before closing the previous one. Repeat the process.

(Further update might come to clarify the above explanation. But this should get you going.)


ALOHA - Throughput and probabilities I have a few questions regarding slotted-ALOHA. Assume a network have 25 users and transmission request probability = 0.25.

1) What is the throughput and what is the probability that a user will successfully transmit a frame after three unsuccessful attempts? I have managed to calculate the throughput as 0.00627. But the major problem is the probability to succeed after 3 attempts. Should I use these two formulas?

$$ n_a = \sum_{n=0}^\infty n(1-p_a)^n p_a $$

$$ n_a = \frac{1-p_a}{p_a} $$

2) What is the average number of unsuccessful attempts before a user can transmit a frame in the above problem?

Can somebody assist me?

Best regards

I assumed that you have calculated the probability of successful transmit (which is about 1e-4 or something)

$$
P[trials =  3] = P[Fail] ^3 * P[Succ]
$$
$$
Average = E[X] = 1/P[Succ]
$$

Please revise or study (if you haven't) the geometric distribution


How many prefix code we can find for a given distribution of probability? A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the same performance (efficiency)?

There are infinitely many prefix codes over $\{a,b,c\}$ containing 5 elements, for example $a,ba,b^2,b^3a,b^{4+n}a$ for all $n \geq 0$. I'm assuming the question is concerned with "saturated" or "minimal" prefix codes, which are prefix codes which satisfy one of the following equivalent conditions:

Each string in $\{a,b,c\}^\omega$ contains some codeword as a prefix.
Kraft's inequality is tight.
The ternary tree corresponding to the code is full, that is, each internal vertex has exactly three children.

It's not hard to check that all such codes containing 5 codewords must look as follows:
$$
\alpha, \beta, \gamma\alpha, \gamma\beta, \gamma\gamma.
$$
For such a code to be optimal for your particular distribution, a necessary and sufficient condition is that $\alpha,\beta$ are assigned to the heavy elements and $\gamma\alpha,\gamma\beta,\gamma\gamma$ to the light elements. You can check it by direct calculation (there are only 3 options, up to symmetry), or by noticing that if a code uses a length-1 codeword for a light element and a length-2 codeword for a heavy element, then switching them reduces the average codeword length.

Indeed, if we fix the codewords, then it is easy to assign them to symbols. The more difficult task is to find the optimal set of codewords. In this case, there is only one set of codewords, so there is no need to run any fancy algorithm such as Huffman's.


Why is it important for functions to be anonymous in lambda calculus? I was watching the lecture by Jim Weirich, titled 'Adventures in Functional Programming'. In this lecture, he introduces the concept of Y-combinators, which essentially finds the fixed point for higher order functions.

One of the motivations, as he mentions it, is to be able to express recursive functions using lambda calculus so that the theory by Church (anything that is effectively computable can be computed using lambda calculus) stays.

The problem is that a function cannot call itself simply so, because lambda calculus does not allow named functions, i.e.,

$$n(x, y) = x + y$$

cannot bear the name '$n$', it must be defined anonymously:

$$(x, y) \rightarrow x + y $$

Why is it important for lambda calculus to have functions that are not named? What principle is violated if there are named functions? Or is it that I just misunderstood jim's video?

The main theorem regarding this issue is due to a British mathematician from
the end of the 16th century, called William Shakespeare. His best known
paper on the subject is entitled "Romeo and Juliet" was published in
1597, though the research work was conducted a few years earlier,
inspired but such precursors as Arthur Brooke and William Painter.

His main result, stated in Act II. Scene II, is the famous theorem:

  What's in a name? that which we call a rose
  By any other name would smell as sweet;

This theorem can be intuively understood as "names do not contribute
to meaning".

The greater part of the paper is devoted to an example complementing
the theorem and showing that, even though names contribute no meaning,
they are the source of endless problems.

As pointed out by Shakespeare, names can be changed without changing
meaning, an operation that was later called $\alpha$-conversion by Alonzo
Church and his followers. As a
consequence, it is not necessarily simple to determine what is denoted
by a name. This raises a variety of issues such as developing a
concept of environment where the name-meaning association are
specified, and rules to know what is the current environment when you
try to determine the meaning associated with a name. This baffled
computer scientists for a while, giving rise to technical
difficulties such as the infamous Funarg problem. Environments remain
an issue in some popular programming languages, but it is generally
considered physically unsafe to be more specific, almost as lethal as
the example worked out by Shakespeare in his paper.

This issue is also close to the problems raised in formal language theory,
when alphabets and formal systems have to be defined up to an
isomorphism, so as to underscore that the symbols of the alphabets are
abstract entities, independent of how they "materialize" as elements
from some set.

This major result by Shakespeare shows also that science was then diverging
from magic and religion, where a being or a meaning may have a true name.

The conclusion of all this is that for theoretical work, it is often
more convenient not to be encumbered by names, even though it may feel
simpler for practical work and everyday life. But recall that not
everyone called Mom is your mother.

Note:
The issue was addressed more recently by the 20th century American logician
Gertrude Stein. However, her mathematician colleagues are still
pondering the precise technical implications of her main theorem:

  Rose is a rose is a rose is a rose.

published in 1913 in a short communication entitled "Sacred Emily".