Why are computable functions continuous? I am working on writing an easy to read document about denotational semantics of the lambda calculus. For that I introduce CPOs, monotonicity and continuity.
A CPO is a set $M$ with a partial order $\leq$ and a bottom element $\bot$, requiring $\bot$ to be the smallest element in $M$ and the existence of the least upper bound ($\bigsqcup$) for every chain $d_0 \leq d_1 \leq d_2 \leq ...$ in $M$.
A function $f$ between two CPOs $M$, $N$ is monotone, if for all $a, b \in M$ the following holds:

$$a \leq b \implies f(a) \leq f(b)$$

A function $f$ between two CPOs $M$, $N$ is continuous, if it is monotone and for all chains $d_0 \leq d_1 \leq d_2 \leq \dots$ we have

$$f(\bigsqcup_{i \in \mathbb{N}} d_i) = \bigsqcup_{i \in \mathbb{N}} f(d_i).$$

I want to give my readers a good intuition about the meaning of these definitions. However, I don't have one I could write down.
Following Glynn Winskel in his book »The Formal Semantics of Programming Languages« (1993), $a \leq b$ has to be read as $a$ approximates $b$ (page 72), meaning $b$ has at least as much information as $a$. This leads to monotone functions reflecting more information about the input in more information about the output (page 122).
This is somewhat understandable for me. However, the explanation of continuity is not clear for me:

  As we shall see, that computable functions should be continuous follows from the idea that the appearance of a unit of information in the output of a computable function should only depend on the presence of finitely many units of information in the input.

(page 73)

This is still unclear to me after reading the stream example in section 8.2 (pages 121–123), or this answer.

So my final question is: How do I convince my readers that computable functions are continuous? Why is there no computable function which is not continuous?

It would be nice if you can give me answers/examples which do not require the rigorous introduction of computability or fix-point theory, since I do not want to focus on those things.
Also it would be great if it is not necessary to know the lambda calculus and its denotational semantics in advance, because I want to (and have to) introduce monotonicity and continuity before them.

EDIT:
By computable I mean Turing-computable. Please correct me if I misunderstand Winskels definition of computable on page 337, since it is not explicitly defined as Turing-computable but in an equivalent (at least in my eyes) manner.

Also I want to point out another source I found which tries to explain my problem. But still I don't understand its example, since it is basically the same as the stream example from Winskel.

EDIT 2:
It would also be a good start in helping me to understand the matter to show that every computable function is monotone, i.e. there exists no non-monotone computable function.

There are several ways to explain "computable implies continuous", I shall give here two such explanations.

Turing machines compute continuous maps

Suppose we have a Turing machine which takes possibly infinite amount of input written down on an input tape. It writes the result on an output tape, where the output cells are write-once. There are workign tapes. The machine may run forever, filling up the outputs cells. This is known as a type two machine. (The argument for other kinds of machines is going to be similar but simpler.)

The following should be obvious: when the machine writes into an output cell, its workings up to that point only depends on a finite portion of the input tape, for the simple reason that in finitely many computation steps it could not have moved the input head past some point. Therefore, every input tape that agrees with the given one up to that point would have caused the machine to write the same answer to the same output cell.

But this is a form of continuity, if we put the correct topology on the spaces of input and output tapes.

First we put topology on the set $\Sigma$ of symbols that can be written onto tape cells. For this we just pick the discrete topology. A tape is an infinite sequence of symbols, so an element of $\Sigma^\omega$, which is a product of $\Sigma$'s. Let's put the product topology on it.

Recall that a basic open set on $\Sigma^\omega$ for the product topology is of the form $U(a_0, \ldots, a_{n-1}) = \{\alpha \in \Sigma^\omega \mid \forall i < n . \, \alpha_i = a_i\}$, where $a_0, \ldots, a_i \in \Sigma$. That is, a basic open set fixes an initial portion of the sequence to the given values $a_0, \ldots, a_n$.

Now we may check that the function $f : \Sigma^\omega \to \Sigma^\omega$ computed by the machine is indeed continuous. Take a basic open set $V = U(a_0, \ldots, a_{n-1})$ and let $W = f^{-1}(V)$. We need to verify that $W$ is open. For this purpose, consider any $\alpha \in W$. If we find a basic open set $W'$ such that $\alpha \in W' \subseteq W$, then we're done.

Because $\alpha \in W$, we have $f(\alpha) \in U$. Thus on input $\alpha$ the machine produces an output tape starting with $a_0, a_1, \ldots, a_{n-1}$. By the time it writes out these cells it has inspected at most the first $k$ cells of the input, for some $k \in \mathbb{N}$. We may take $W' := U(\alpha_0, \ldots, \alpha_k)$ and verify that $\alpha \in W' \subseteq W$. It is obvious that $\alpha \in W'$. To prove $W' \subseteq W$ take any $\beta \in W'$ and observe that $f(\alpha)$ and $f(\beta)$ agree on the first $n$ values of the output. This implies that $f(\beta) \in V$ and hence $\beta \in W$, as required.

Computable maps are continuous as maps between algebraic $\omega$CPOs

First, let me note that what you defined is usually called "$\omega$CPO" ($\omega$ in the name indicates we only require suprema of chains).

In denotational semantics datatypes correspond to $\omega$CPOs. In fact, they correspond to algebraic $\omega$CPOs (is this in your thesis?), which are $\omega$CPOs for which the compact elements form a base. Here are some definitions.

Definition: Let $D$ be an $\omega$CPO. An element $d \in D$ is compact if, for every chain $x_0 \leq x_1 \leq \cdots$ such that $d \leq \bigsqcup_i x_i$, there exists $j$ such that $d \leq x_j$.

Definition: An $\omega$CPO is algebraic if every $x \in D$ is the supremum of compact elements below it.

The intuition behind compact elements is that they contain "finite information".
A good example is $\mathcal{P}(\mathbb{N})$, the powerset of natural numbers ordered by $\subseteq$, where the compact elements are precisely the finite subsets of $\mathbb{N}$ (exercise!).
Another example: in the $\omega$CPO of continuous functions $\mathbb{N} \to \mathbb{N}_\bot$ the compact elements are those partial functions that are equal to $\bot$ everywhere, except at finitely many arguments.

To say that an $\omega$CPO is algbraic is to say that every element is completely determined by the finite pieces of information that approximate it. It is a fact that in denotational semantics datatypes correspond to algebraic $\omega$CPOs, unless we are doing something very unusual.

We can now explain why every computable map is continuous. Suppose $D$ and $E$ are $\omega$CPOS and $f : D \to E$ computable. Suppose $x \in D$, $e \in E$, $e$ is compact, and $e \leq f(x)$. Intuitively, this say that "finite piece of information $e$ appears in the output $f(x)$". Because $f$ is computable, it must be the case that it computed the information $e$ by accessing only a finite amount of information about $x$, i.e., there is a compact $d \in D$ such that $d \leq x$ and $e \leq f(d)$. This argument should be compared to the Turing machine argument above. We have established:

Lemma: If $f : D \to E$ is computable and $e \leq f(x)$ for some $x \in D$ and a compact $e \in E$, then there is compact $d \in D$ such that $d \leq x$ and $e \leq f(d)$.

We can usethe lemma to show that a computable $f$ is continuous. Suppose $x_0 \leq x_1 \leq \cdots$ is a chain in $D$. Because $f$ is monotone, we already know that $\bigsqcup_i f(x_i) \leq f(\bigsqcup_i x_i)$, but we also need the inequality $f(\bigsqcup_i x_i) \leq \bigsqcup_i f(x_i)$. Because $E$ is algebraic, it suffices to show that, whenever $e \in E$ is compact and $e \leq f(\bigsqcup_i x_i)$ then $e \leq \bigsqcup_i f(x_i)$. So assume $e \leq f(\bigsqcup_i x_i)$. By the lemma there exists a compact $d \in D$ such that $d \leq \bigsqcup_i x_i$ and $e \leq f(d)$. Because $d$ is compact, there exists $j$ such that $d \leq x_j$, hence by monotonicity of $f$ we have $e \leq f(d) \leq f(x_j) \leq \bigsqcup_i f(x_i)$. We are done.


Is every reduction function $f \in O(n)$? I have no detailed questions actually. My question is about a (maybe possible) generalization for reductions.

We defined reduction as following (If I translate a term false please correct me.):

$ L_1, L_2 \in \{0,1\}^* $ two languages.

One may reduce the language $L_1$ to $L_2$, if there is a total function:

$f: \{0,1\}^* \rightarrow \{0,1\}^* $ with the following properties:

$ \forall w\in \{0,1\}^* :w\in L_1 \Leftrightarrow f(w) \in L_2 $
The function is via a Turing Machine $M_f$ computable.

My question is the following:

If one may can reduce a language to another, then one may can construct a function from a language to another. It means intuitively for me that the reduction function has to go over $|L_1| = n$ operations. Which means that the reduction function is computable in $O(n)$. But I am not sure about any generalization. I mean does it imply that:

$f$ is a reduction function $\Rightarrow f\in O(n)$

I'm not sure exactly what you mean. In essentially all interesting cases, $L_1$ is infinite, so you can't say that $|L_1|=n$. Second, the function $f$ is a function from strings to strings, so it doesn't make sense to ask if it's $O(n)$ because $O(\cdot)$ is a class of functions from numbers to numbers.

However, you're most probably asking if all reductions are in $\mathrm{TIME}[O(n)]$, i.e., if they can all be computed in linear time. They can't.

By the time hierarchy theorem, for any $r>s$, there are languages in $\mathrm{TIME}[O(n^r)]$ that are provably not in $\mathrm{TIME}[O(n^s)]$. So, consider any problem $X$ that is P-complete under polynomial-time reductions. We must have $X\in\mathrm{TIME}[O(n^s)]$ for some $s$. By the time hierarchy theorem, there is some langauge $Y\in\mathrm{TIME}[O(n^{s+1})]\setminus\mathrm{TIME}[O(n^s)]$.  Since $X$ is P-complete and $Y\in{}$P, there must be some polynomial-time reduction $Y\to X$. However, this reduction cannot run in linear time. If the reduction did run in linear time, there would have to be some $k$ such that it transforms every length-$n$ instance of $Y$ into an instance of $X$ with length at most $kn$ (a function running in linear time can only produce linearly much output). But, then, we would be able to decide $Y$ via the reduction in time
$$O(n) + O((kn)^s) = O(n) +O(n^s) =O(n^s)\,,$$
contradicting our choice of $Y\notin\mathrm{TIME}[O(n^s)]$.

Note that, in general, if we're talking about computability rather than complexity, we only care that the reduction is computable – we usually don't care about its time or space complexity at all. However, in other contexts, we do care about linear-time reductions, for example in proving problems hard under the exponential time hypothesis.


Why is quiescent consistency compositional, but sequential consistency is not I'm having trouble in comparing these two memory consistency models.

Essentially for  sequential consistency I think of real code like this:

int x, y;

void ThreadA()
{
   x = 20; //Write
   int a = y; //Read
}

void ThreadB()
{
    y = 20;
    int b = x;
}

In a  sequential consistency environment it's impossible for a or b to not be 20. That is either a = 20, b = 20 or a = 20 && b = 20.

But how does quiescent consistency fit in to this example, and why is it compositional?

Sorry for the late reply, but I've just found the question (questions, indeed). I am studying concurrency as well and I'll try to share some ideas with you.

First, let's start with sequential consistency. A model has this property if operations appear to take effect in program order. In other words, the order in which lines of code are executed is the one specified in the source file. This prerequisite is thread-specific: operations involving different threads are unrelated by the program order. So, the property grants the following: operations issued by the same thread are executed in the same order specified by the thread source code. Operations issued by different threads can happen in any order. This prerequisite may seem obvious, but it is not always the case (compiler optimizations may change the order in which operations are issued, thus making the program order different from the source).

Your example is right, but let me give you some others. Consider this program P1 (I'll tag each line for an easy reference):

   int x = 1;

   void ThreadA()
   {
A1:    x = x * 2;
A3:    int a = x;
   }

   void ThreadB()
   {
B2:    x = 20;
   }

Is there a sequential execution in which, at the end, a = 40? Yes: B2, A1, A3.

B2 and A1 can be executed in any order (they belong to different threads). A1 is executed before A3 (program order = source code order).

Now consider this program P2:

   int y = 1;

   void ThreadA()
   {
A2:    y = 40;
   }

   void ThreadB()
   {
B1:    y = y / 2;
B3:    int b = y;
   }

Is there a sequential execution in which, at the end, b = 20? Yes: A2, B1, B3.

What about composition? Let's compose P1 and P2. We get P1∘P2:

   int x = 1;
   int y = 1;

   void ThreadA()
   {
A1:    x = x * 2;
A2:    y = 40;
A3:    int a = x;
   }

   void ThreadB()
   {
B1:    y = y / 2;
B2:    x = 20;
B3:    int b = y;
   }

If sequential consistency were compositional, then there should be an execution in which, at the end, a = 40 and b = 20. Is this the case? No. Let's give a formal proof oh why it can't be the case. I'll write "o1 → o2" to say that the operation o1 must be executed before operation o2.

In P1∘P2, due to sequential consistency, the following must holds: A1 -> A2 and B1 -> B2 (per-thread program order). In order to get a = 40 also B2 -> A1 must hold. In order to get b = 20 also A2 -> B1 must hold. Can you see the precedence chain? A1 -> A2 -> B1 -> B2 -> A1 -> ...

P1 and P2 were sequentially consistent, but their composition P1∘P2 was not.
Sequential consistency is not compositional. The example you provided was not tricky enough to show this fact.

Now, let's consider quiescent consistency. It's difficult for me to explain this property without using the object-oriented paradigm. In fact, quiescent consistency can be easily understood in terms of pending method calls on objects. Nevertheless, I'll try to stick with the imperative paradigm (pending method calls become functions started but not completed, objects become variables involved in functions).

A function call is composed by an invocation and a response. A function is pending if it has been invoked by a thread but it has not returned a response yet to such thread. A period of quiescence for a variable is a time interval in which there are no pending function calls (by any thread) operating on it.
A model has the quiescent consistency property if function calls operating on the same variable and separated by a period of quiescence appear to take effect in their real-time order (the one specified by source code). From the converse point of view, the definition states that operations on the same variable executed by functions called concurrently by different threads (not separated by quiescence) can happen in any order.

I've tried for many hours to design a meaningful example using only read-write operations to show you the difference between quiescent and sequential consistency, but I didn't succeed. Let me use another example involving sets. I will use a bit vector to keep track of which integers (from 0 to 4) are in the set:

   int set[5] = {0, 0, 0, 0, 0};  // 0 if i-th item is absent, 1 otherwise

   void add(int number) {
L1:    set[number] = 1;
L2:    temp foo = set[0];
   }

   void remove(int number) {
       set[number] = 0;
   }

   int contains(int number) {
       return set[number] == 1;
   }

   void ThreadA()
   {
A1:    add(1);
   }

   void ThreadB()
   {
B1:    add(2);
B2:    remove(2);
B3:    int res = contains(2);
   }

Is there a sequential execution in which, at the end, res = 1? No: due to sequential consistency B1 -> B2 and B2 -> B3, so B1 -> B3. So, remove(2) is always executed after add(2) and contains(2) will always returns 0.

Is there a quiescent execution in which, at the end, res = 1? Yes! Consider this execution:

Thread A invokes add(1) at A1.

Thread A executes L1 (but not L2). // since there is a pending call on the set, now Thread B is free to execute B2 before B1 because these calls involve the set as well

Thread B calls B2.  // invocation + response

Thread B calls B1.  // invocation + response

Thread A executes L2 and add(1) responds. // now there is quiescence on the set

Thread B executes B3.  // invocation + response

Now res = 1.

Unfortunately, I still can't answer the latest question on why quiescent consistency is compositional: I found your question while I was looking for this exact answer indeed. If I come up with something I'll let you know.

For a good reading on the topic have a look at chapter 3.3 of the book "The Art of Multiprocessor Programming" by Herlihy and Shavit.

EDIT: I've just found a great page explaining why quiescent consistency is compositional. And this is another very good reading!

EDIT2: Fixed little error in the sequential consistency composability example.


Merge sort worst case running time for lexicographical sorting? A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge step would be $O(n^2)$. So the recurrence should be of the form

  $$T(n) = 2T(\frac n2) + O(n^2)$$

By master's theorem it solves to $O(n^2)$.

Somehow some people on the internet claim the following explanation:
Merge sort makes $O(nlogn)$ comparisons and since it is lexicographical sort each comparison take $O(n)$ time, so worst case time is $O(n^2logn)$.

Which of the above is correct and if at some point i am incorrect please correct me.

The recurrence formula is incorrect.

Lets say you have $t$ strings, so the running time of merge isn't $O(t^2)$ but $O(t\cdot n)$.

Change variables: the input size is $m=n^2$, and the recurrence formula should be

$$T(m)=2 T\left( m/2 \right) + O(m) $$

So you get $T(m)=O(m\log(m))$ and therefore $T(n^2)=O(n^2\log(n))$.


How to solve T(n) = T(n-1) + n^2? See title. I'm trying to apply the method from this question. What I have so far is this, but I don't know how to proceed from here on:

T(n) = T(n-1) + n2

T(n-1) = T(n-2) + (n-1)2 = T(n-2) + n2 - 2n + 1

T(n-2) = T(n-3) + (n-2)2 = T(n-3) + n2 - 4n + 4

T(n-3) = T(n-4) + (n-3)2 = T(n-4) + n2 - 6n + 9

Substituting the values of T(n-1), T(n-2) and T(n-3) into T(n) gives:

T(n) = T(n-2) + 2n2 - 2n + 1

T(n) = T(n-3) + 3n2 - 6n + 5

T(n) = T(n-4) + 4n2 - 12n + 14

Now I have to find a pattern but I don't really know how to do that. What I got is:

T(n) = T(n-k) + kn2 - ...???

Don't expand the squared terms; it'll just add confusion. Think of the recurrence as
$$
T(\fbox{foo}) = T(\fbox{foo}-1)+\fbox{foo}\;^2
$$
where you can replace foo with anything you like. Then from
$$
T(n)=T(n-1)+n^2
$$
you can replace $T(n-1)$ by $T(n-2)+(n-1)^2$ by putting $n-1$ in the boxes above, yielding
$$
T(n) = [T(n-2) + (n-1)^2]+n^2 = T(n-2)+(n-1)^2+n^2
$$
and similarly
$$\begin{align}
T(n) &= T(n-2)+(n-1)^2+n^2\\
     &= T(n-3)+(n-2)^2+(n-1)^2+n^2\\
     &= T(n-4)+(n-3)^2+(n-2)^2+(n-1)^2+n^2
\end{align}$$
and in general you'll have
$$
T(n) = T(n-k)+(n-k+1)^2+(n-k+2)^2+\dotsm+(n-1)^2+n^2
$$
Now if we let $k=n$ we'll have
$$
T(n) = T(0)+1^2+2^2+3^2+\dotsm+n^2
$$
Now if you just need an upper bound for $T(n)$ observe that
$$
1^2+2^2+3^2+\dotsm+n^2\le \underbrace{n^2+n^2+n^2+\dotsm+n^2}_n=n^3
$$
so we conclude that $T(n)=O(n^3)$, in asymptotic notation.

For a more exact estimate, you can look up the equation for the sum of squares:
$$
1^2+2^2+\dotsm+n^2=\frac{n(n+1)(2n+1)}{6}
$$
so
$$
T(n)=T(0)+\frac{n(n+1)(2n+1)}{6}
$$


Is this language recursively enumerable? Let $P=\{L \mid  \exists w\in \Sigma^* s.t. w\in L  \wedge \forall z>w\colon z\in L\}$ .

Now denote $L=\{\langle M \rangle \mid L(M)  \in P \}$.

That is, $L$ is the set of all TMs $M$ s.t. there exists a $w\in \Sigma^*$ s.t. $w$ is accepted by $M$ and for each $z>w$, $z$ is accepted by $M$ as well.

I am trying to find out whether $L$ is in $RE$ or not.

I can easily show that $L$'s complement is $\notin RE$ using Rice's Theorem. But here, if using Rice's Theorem, I can only show that $L \notin R$, but I have no guarantee over $RE$.

I thought about using reduction - either to prove $L\in RE$ or to disprove, but none came about. I thought about using $L_{acc}$ or its complement, $L_{\Sigma^*}$, but could not come up with an idea that will work for either direction of the reduction.

Could someone assist?

Thanks to @Yuval and @chi, I've been able to find a working reduction.

The reduction is $\overline{L_{halt}} \leq L$. For an input $<M><w>$ we build the following TM $N_w$:

Runs $M$ on $w$ for $k$ steps, where $k$ is the length of the input for $N_w$.
If $M$ was able to accept or reject $w$ within $k$ steps in the above simulation, $N_w$ will reject. Otherwise, accept.

This way, if $<M><w>\in \overline{L_{halt}}$ then  $M$ does not halt on $w$ for any length $k$, thus $N_w$ will accept every string. Then, $L(N_w)=\Sigma^*\in P$ and $<N_w>\in L$.

Else, if $<M><w>\notin \overline{L_{halt}}$ then a $n\in\mathbb{N}$ exists s.t. $M$ halts on $w$ within $n$ steps. Thus, for all inputs of length $\geq n$ the TM $N_w$ will reject, and it will only accept inputs of length $ < n$, and not satisfaying the property $P$. Hence, $<N_w>\notin L$.

And since $\overline{L_{halt}}\notin RE$, it follows that $L\notin RE$ as well.


What are the differences between parse and decision trees? I have created a parse tree for the formula: a∧¬(b∨c)∨¬d∧(¬b) successfully.
I am now asked to create a decision tree for the same formula. What are the main differences between a parse tree and a decision tree?

A decision tree is an algorithm for computing a function, in your case the truth value of the formula. In your setting, each internal node of the decision tree is labeled by a variable, and it has two children; you go to the left one if the variable is false, and to the right one if it is true. Leaves are labeled by True or False, and this is the returned value.

For example, one decision tree for $a \land b$ is as follows. The root is labeled $a$. Its left child is a leaf labeled False. Its right child $x$ is labeled $b$. The left child of $x$ is a leaf labeled False, and the right child of $x$ is a leaf labeled True.


Does applying a homomorphism to the intersection of two CSLs yield RE languages? For each language $L \in L(RE)$ there are a homomorphism $h$ and two context-free languages $L_1$ and $L_2$ such that $L = h(L_1 \cap L_2)$.

I understand that this is because context-free languages are not closed under intersection so $L_1 \cap L_2$ will produce non-context-free languages. Since context-sensitive grammars doesn't allow erasing rules which context-free grammars allow to, then the language must be recursively enumerable language. Then recursively enumerable languages are closed under homomorphism.

If $L_1$ and $L_2$ are context-sensitive languages, does $L = h(L_1 \cap L_2)$ still result in $L \in L(RE)$, as context-sensitive languages do closed under intersection but not morphisms?

This follows from closure properties of CSL: it's closed against intersection and $\epsilon$-free homomorphism, but not against (general) homomorphism.

Thus, $h(L_1 \cap L_2)$ is always context-sensitive if $h$ is $\epsilon$-free.

If $h$ is not, $h(L_1 \cap L_2)$ may not be. As an example, take $L_1$ and $h$ from the proof that CSL is not closed against general homomorphism, and $L_2 = \Sigma^*$.

Since CSL $\subseteq$ RE and RE is closed against intersection as well as (general) homomorphism, $h(L_1 \cap L_2)$ is indeed always in RE.


How to construct the objective function for genetic algorithm optimization? I am trying to optimize a coefficients of  filter by minimizing sum-squared error.  I want to use a genetic algorithm (GA) optimization wherein the coefficients of filter form the GA's chromosome (a vector).

How can I construct the objective function, given that I want it to use least-squares minimization?

tl;dr-  Objective functions are supposed to quantify how good a set of parameters is.  It doesn't matter how you got the parameters; for example, it doesn't matter that you're using genetic algorithms.  You just need to create some function that says how well the parameters work.

So you're designing a filter, which requires that the filter's parameters be optimized to fit its application, and you'd like to use genetic algorithms for the optimization?

You're correct that the filter's parameters should be used to construct the chromosomes in the genetic algorithm.  The genetic algorithm then does its work by:

Calculates how well its chromosome (combination of parameters) performs.
Discards the chromosomes that didn't perform well.
Modifies (mutates) the parameter sets (chromosomes) that did perform well.
Goes back to Step (1), looping until either it finds a parameter set that's good enough or it gives up (fails to converge).

However, how should the algorithm assess how "good" the parameter sets are?  That's what the objective function's for.  The objective function takes the chromosome as input, then produces a result that quantifies how good that chromosome is.

Since chromosomes are sets of parameters, they're often represented as a vector (array).  For example, if your filter's, say,$$
f\left(x\right)=ax^2+bx+c,
$$then the chromosome's the array of the parameters $\left\{a,b,c\right\}$.

The question statement doesn't specify your filter or exactly what sort of problem you're working on.  However, since you want to use sum-squared error, that implies that your filter produces an output with quantifiable error.

So, presumably, your objective function would be$$
\text{error}=\sum_{{\forall}\text{data}~i}{\left(f_{\text{measured}}\left(x_i\right)-f_{\text{model}}\left(x_i\right)\right)}^2,
$$or something like that.  Some folks prefer to use the root-mean-square, i.e.$$
\text{error}=\sqrt{\sum_{{\forall}\text{data}~i}{\left(f_{\text{measured}}\left(x_i\right)-f_{\text{model}}\left(x_i\right)\right)}^2},
$$but that shouldn't matter here.

In general, I'd suggest seeing genetic algorithms as stepping functions.  Their core duty is to produce new guesses during an optimization process.  Objective functions live elsewhere in the optimization process's structure; this is, objective functions don't care how you're stepping - whether you're using genetic algorithms, Newton's method, Simplex, gradient descent, bisection, random guessing, or whatever else - it doesn't matter to the objective function.  All the objective function has to do is say how good a guess is, regardless of how that guess was generated.


True Error of a binary classifier For a given classifier h, How is the true error over a distribution D defined?
\begin{align*}
L_D(h) &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \Pr[h(x) \neq y] \\ &=
\sideset{\mathbb{E}}{}{}_{x,y \sim D}
\begin{cases}
\Pr[y \neq 0|x] & \text{if } h(x) = 0, \\
\Pr[y \neq 1|x] & \text{if } h(x) = 1.
\end{cases}
\end{align*}

I saw these two formulae here Showing that Bayes classifier is optimal Are these two equivalent?

The first line should read
$$
\Pr_{x,y \sim D}[h(x) \neq y].
$$
(This is assuming that the classifier is deterministic.)

We can sample $x,y \sim D$ in two steps: first sample $x \sim D'$, and then sample $y \sim C_x$, where $C_x$ is a distribution depending on $x$.

The second line expresses the idea
$$
\operatorname*{\mathbb{E}}_{x \sim D'} \Pr_{y \sim C_x}[y \neq h(x)]
$$
in an elaborate way.

Both of these are the same, and equal to
$$
\operatorname*{\mathbb{E}}_{x \sim D'} \operatorname*{\mathbb{E}}_{y \sim C_x} 1_{h(x) \neq y}.
$$


Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation This could relate to different applications, but my application of interest is in similarity-search systems based on high-dimensional feature vectors. In these systems, since search  based on Euclidean distance is costly, the vectors are encoded as binary vectors. Then the search is done based on Hamming distance computation which is supposed to be faster than the Euclidean counterpart. My question is, practically, how much is this speed-up for an average architecture?

More formally, suppose we have a database $\mathrm{X} = [\mathbf{x}_1, \cdots, \mathbf{x}_i, \cdots, \mathbf{x}_N]$ of $N$ vectors of dimension $n$, and a vector $\mathbf{y}$ of the same dimensionality. Now imagine two cases:

Vectors are real-valued, i.e., $\mathbf{x}_i \in \Re^n$. We are interested in finding the $\mathbf{x}_i$ from $\mathrm{X}$ with the minimum Euclidean distance to $\mathbf{y}$, i.e.:

\begin{equation}
i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} ||\mathbf{y} - \mathbf{x}_i||_2.
\end{equation}

Vectors are binary, i.e., $\mathbf{x}_i \in \mathcal{B}^n$ with $\mathcal{B} = \{0,1\}$. We are interested in finding the $\mathbf{x}_i$ from $\mathrm{X}$ with the minimum Hamming distance to $\mathbf{y}$, i.e.:

\begin{equation}
i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} \sum_{j=1}^n \big( \mathbf{y}(j) \oplus \mathbf{x}_i(j) \big),
\end{equation}
where $\oplus$ denotes the XOR operation.

Both of these operations have complexity of $\mathcal{O}(Nn)$. However, the real case requires doing the operations in floating-point arithmetic while the binary case enjoys the fixed-point binary operations which are faster.

My question is, in practice, how are these complexities different? Can we say, very roughly though, that they have different constant factors and the ratio of these factors is a constant value? What would that constant value be then? Around 10 or 100 maybe? And how much is it architecture dependent?

The asymptotic complexity is the same (assuming you treat each floating-point operation as a constant-time operation, which is probably the right assumption).  The practical running time may be different.  Asymptotics ignores constant factors, but constant factors can be important in practice.

The way to tell how much faster it is in practice is to implement it and do some experiments, i.e., benchmark it on realistic workloads.  Asymptotic analysis probably won't be very helpful in this case for predicting how much faster it will be.  No one is likely to be able to give you a prediction for what the results of those experiments will be; you'll just have to try it and see.


In a DAG, finding the path with the highest score Given a directed, acyclic graph in which each node has an assigned integer score, what is a fast way of finding the path from a start and end vertex with the highest cumulative score? I thought of a DFS approach in which we start at the end and run the graph in the reverse way, saving at each node the best cumulative score attainable. To print the results, we start at the first node and greedily pick the next node with the highest cumulative score. However, I don't think this is the best way as we might be traversing the same paths a lot of times if we are given an unfriendly graph. Is there a better way of doing this?

Hint: find a topological ordering, and for each vertex $v$, in the topological ordering, compute (the score of) the path with the highest score that ends at $v$.


$L = \{x\#x^R \mid x\in\{0,1\}^* \} $ not accepted by a queue automaton? It can be proven that class of languages accepted by queue automata is equal to class of languages accepted by Turing machines.
It was mentioned somewhere that the language $$L = \{x\#x^R \mid x\in\{0,1\}^* \} $$ can not be accepted by a queue automaton. But the language is accepted by a TM. Can somebody explain this apparent contradiction?

If a queue automaton is Turing-Complete, then it can compute (decide) any function (language) that a Turing machine can. And we know that TM can decide both $L = \{x\#x^R \mid x\in\{0,1\}^* \}$ and $L = \{x\#x \mid x\in\{0,1\}^* \}$, thus both can be decided by a queue-automaton.

"How?" you ask? For this you need to understand how a queue-automaton works. It starts with the input already in the queue (where the end of the input is marked by a special character $\$$), and then at every move it reads the letter at the head of the queue and can insert one or more characters to the end of the queue.

Let $M$ be a TM. The way to simulate $M$ over the queue automaton is to keep reading content out of the queue and then putting it back into the end of the queue. This allows us to make multiple passes over the "tape" of the TM. For instance, assume the queue holds "abc$". A "Cycle" (a pass on the queue) will look like (plotting the queue content):

 abc$ -> bc$a -> c$ab -> $abc -> abc$

and we are back to square one, allowing the machine now to take another pass on the input.

It is then trivial to simulate the TM moves as long the head moves to the right, or stays in place: we can denote the heads place by a special symbol ($\to$) that points on where the TM head looks at. E.g., at the very first move we do:

abc& -> bc$→a -> c&→ab -> ... -> →abc$

Then moving the head to the right is elementary:

→abc& -> abc$ -> bc&a→ -> ... -> a→bc$

It is a bit more tricky to simulate a move of the TM head to the left, because seemingly, we need to put the head even before we see the next letter that causes the move back.

The trick here is to use the current state in order to "keep one letter in the memory". So when we see a letter, we don't immediately put it back to the queue, but we "remember" it using a state (e.g. if the states of the TM are $q_1,q_2,..$ etc, we will move to $q_1^a$ if we see an a or to $q_1^c$ if we see a c, etc.)
Before putting the letter back to the queue we first we check the next letter, and if it is not the head, we put it back, If it is the head, we may move the head as needed.

The cycle of moving the head left will look something like the following:

a→bc$ ->(remember a using states)-> →bc$a -> bc& -> (*)

at this point the machine knows it needs to move the head to the left. It remembers a and so it put it back in the queue, now remembering b using the current state

-> c$→a -> $→ab -> ... -> →abc$


Is "capability-based security" vs "hierarchical-protection-domain based security" a false dichotomy? The wikipedia page on capability-based security states:

  Capability-based security is to be contrasted with an approach that uses hierarchical protection domains.

However, in order to implement capability-based security, we still need a kernel that ensures that user processes are only able to use the capabilities they have been assigned. Hence we still need a distinction between kernel mode and user mode, which is exactly what hierarchical protection domains are. In fact, as far as I know, most OS'es use only 2 hierarchical protection domains (user and kernel) in practice (I think Windows 10 has domains 0,1,2,3, but that 2 and 3 are only rarely used).

So it seems to me that kernels that implement capability-based security do not make less use of hierarchical protection domains than other operating systems.

Isn't it more accurate therefore to say that capability-based security is one way of using hierarchical protection domains to achieve security? (rather than fundamentally different from hierarchical protection domains)

No.  I don't think that would be a good summary, as it doesn't get to the heart of what I consider important about capability-based systems.  Your rephrasing is putting a focus on how the restrictions are enforced, but that is not the interesting part of capability-based models; the more interesting part is how we express our security goals as capabilities, and what advantages and disadvantages such an approach has.

First off, understand that the notion of capability-based security is not a precisely well-defined concept; it's a broad phrase that could cover multiple possible meanings. Different people use that phrase to mean different things.  So take everything here with a grain of salt.

I suggest that the best way to understand the phrase "capability-based security" is "a security architecture that relies heavily on capabilities".  So, then you need to understand what capabilities are, and why they might be useful.

If you keep reading that Wikipedia article, it contains some explanation of what capabilities are and some ways that they might be useful.

If you want to dive into the details of one particular view on capabilities, I recommend looking at https://en.wikipedia.org/wiki/Object-capability_model and Mark Miller's PhD thesis.  I think you'll find that to have a coherent, principled, and focused view.  It's not necessarily what everyone means when they use the word "capability", but it's one take on the subject that is internally consistent and interesting.


Evaluating predicate on binary strings Consider two unknown binary strings $$X = x_{1} x_{2} \dots x_{n^{2}}, \quad Y = y_{1} y_{2} \dots y_{n^{2}}, \quad x_{i}, y_{i} \in \{0, 1\} .$$ We may request a string $Z = z_{1} z_{2} \dots z_{n^{2}}$, where $z_{i} = x_{i}$ or $z_{i} = y_{i}$, no more than $n + 1$ times. So, for every request we set required $z_{i}$ (that is, $x_{i}$ or $y_{i}$) for every $i$.

Moreover, we have $n$ bits of unwritable memory, namely, every bit of that memory is set once and then does not change. This memory is avaliable all the time, but requested $Z$ strings drop out before the next request, so, we don't have complete list of all requested $Z$ strings.

The problem is to check if $X = Y$ with given $n$ bits and $n + 1$ times for $Z$ string request.

There is an extra question: is it possible to use $\mathcal{O}(\log^{2}(n))$ bits of memory and $\mathcal{O}(\log(r))$ requests.

I don't really understand area of CS that is closely related to the problem, could anyone give a hint?

You can think of $X,Y$ as $n\times n$ matrices with rows $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, respectively. Then $X = Y$ iff
$$
a_1 \oplus \cdots \oplus a_n = b_1 \oplus a_2 \oplus \cdots \oplus a_n = b_1 \oplus b_2 \oplus a_3 \oplus \cdots \oplus a_n = \cdots = b_1 \oplus \cdots \oplus b_n.
$$


Obtaining a recurrence from a rational generating function Looking at some Generating functions of a series, I have conjectured -

If $G(x) \ =\ \frac{1}{1-x^{t_1}-x^{t_2}-...-x^{t_n}}$, then the recurrence equation of the the series is -

$a_n = a_{n-t_1}+a_{n-t_2}+...+a_{n-t_n}$

How can I prove or disprove this?

Suppose that
$$ G(x) = \sum_{n=0}^\infty g_n x^n. $$
Using the given equation (ending at $i_m$, a better choice of variables), we have
$$
1 = (1-x^{i_1}-\cdots-x^{i_m}) G(x) =
\sum_{n=0}^\infty (1-x^{i_1}-\cdots-x^{i_m}) g_n x^n = \\
\sum_{n=0}^\infty g_n x^n - \sum_{n=i_1}^\infty g_{n-i_1} x^n - \cdots - \sum_{n=i_m}^\infty g_{n-i_m} x^n = \\
\sum_{n=i_m}^\infty (g_n - g_{n-i_1} - \cdots - g_{n-i_m}) x^n - H(x),
$$
where $\deg H(x) < i_m$. Comparing coefficients, we find out that for $n \geq i_m$,
$$ g_n = g_{n-i_1} + \cdots + g_{n-i_m}. $$

More generally, you could have allowed coefficients in front of the monomials.


Which algorithm to detect errors in 32bit data with 8bit parity I want to transmit a 32bit message in eight groups of 5bit each. This leaves me with 8bits to use for error checking.

Overall, a group is likely transmitted without error, but when there is an error transmitting a group, there are probably multiple bits wrong.

If I use one parity bit per group, I have a 50% chance to detect a wrong group. But I don't need to know which group of a message is wrong, I want to check the entire message.

I want 100% chance of detecting if one group of the message is incorrect, regardless of how many bits are flipped in that group. If possible, I also want to be able to check wheather two neighboring groups have been switched.

Which algorithm should I use for error checking / How should I code the data?

Think of your message as seven 5-bit numbers $x_2,\ldots,x_8 \in \{0,\ldots,30\}$. This gives you $7\log_2 31 \approx 34.68$ message bits. Calculate $x_1 = -\sum_{i=2}^8 ix_i \bmod{31}$, so that
$$
\sum_{i=1}^8 ix_i \equiv 0 \pmod{31}.
$$

It is easy to check that every single symbol error is detected, since $31$ is prime.

Now suppose that $x_i$ and $x_j$ are switched, but the equation above still holds. Then $ix_i + jx_j \equiv ix_j + jx_i$, and so $(i-j)(x_i - x_j) \equiv 0$, implying that either $i = j$ or $x_i = x_j$.


Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$ I am having difficulty with one of the exercises in the Dragon Book:

  Exercise 2.4.1(c): Construct recursive-descent parsers, starting with
  the following grammars:

  $$S \rightarrow 0S1\ |\ 01$$

Yet, for constructing a feasible parser, it is required that for two productions $A \rightarrow \alpha\ |\ \beta$, their FIRST sets are disjoint. But since:

  $$FIRST(0S1) = \{ 0 \} \hspace{2em}\&\hspace{2em} FIRST(01) = \{ 0 \}$$

this is not the case. How does one proceed here? Just state it is not feasible due to the stated conflict or is there alternative approach, like modfying the grammar?

You may need to modify the grammar. In general this is not necessarily possible (not every CFG is an LL(k) grammar - the class suitable for recursive descent predictive parsing). In this case we can modify the grammar to:

$$\begin{align*}
  &\mathtt{1.} & S &\rightarrow 0SA \\
  &\mathtt{2.} & S &\rightarrow \varepsilon \\
  &\mathtt{3.} & A &\rightarrow  1 \\
\end{align*}$$

Then we have an unambiguous first and follow set for each combination of terminal and non-terminal. So the parsing table looks something like:

$$\begin{array}{l|l|l}
    & 0           &  1 \\ \hline
  S & \mathtt{1.} & \mathtt{2.} \\ \hline
  A &             & \mathtt{3.} \\
\end{array}$$

This gives an LL(1) grammar - one that can be parsed with one symbol of lookahead. It is possible to parse the original grammar without modification using 2 symbols of lookahead (making it an LL(2) grammar), Raphael explains that approach excellently in his answer.

The details are all in the dragon book of course (what isn't!), and better explained there than I can do here.


Prove that $\text{EF p}$ can't be written in LTL Why can't we somehow represent it's negation in LTL and go from there? I think maybe because it has (effectively) two existential quantifiers, so negating it does not work. But how do I prove it?

There is a delicate point here, about the semantics of LTL vs CTL.

Given a formula $\psi$ in LTL, we say that it holds in a structure $K$ if every path in $K$ satisfies $\psi$.

In CTL, however, the path quantifiers are built in to the formula.

To make this more precise, you can think of LTL as the fragment of CTL* of the form $A\psi$, where $\psi$ doesn't contain any path quantifiers (i.e., it's in LTL).

Now, you suggest negating your formula, so you obtain $AG\neg p$. This formula is not an LTL formula, due to the quantifier $A$. But it does have an LTL equivalent, namely $G\neg p$.

However, if you try to negate back to CTL, the negation of the LTL formula is now $Fp$, but the semantic of LTL means that it is interpreted as $AFp$, whereas you wanted $EFp$.

To sum up, you just cannot express the path quantifier $E$ in LTL.

To prove that the formula $EFp$ does not have an LTL equivalent, consider (towards a contradiction) some equivalent LTL formula $\psi$, and take a structure that has two "branches" -- one with $p$ and one without (e.g., two states with self loops).
Since this structure satisfies the $EFp$, then it also satisfies $\psi$, meaning that every computation in it satisfies $\psi$. But now, if you remove one of the branches (the one with $p$), then $\psi$ is still satisfied (since you only removed computations). However, $EFp$ is not satisfies, so $\psi$ is not its equivalent.


Is DFA a Moore machine or not? I understand the difference between DFA (has finite set of accept states, and doesn't have output function, nor output alphabet) and Moore Machine (doesn't have accept states, but has output for every state). But when implementing DFA in programming language, it always generates output. That is, if it last state was accept then it returns TRUE, to indicate that string was in the language. And if the last state was not accept then it returns FALSE. Thus DFA has output function $G\colon Q \to A$, where $Q$ are finite set of states, and $A = \{TRUE, FALSE\}$

So my question is: doesn't that make DFA a Moore Machine?

Imagine a system S1->S2->S3(final).

DFA transition rules are (S1,a,S2) and (S2,b,S3).
Moore machine rules are (S1,(a,1),S2) and (S2,(b,2),S3).

For the input 'ab',

DFA will output 'ab'->TRUE
Moore machine will output 'a'->1, 'b'->2.

As you can see, DFA doesn't output at each stage. Independent of the input length, you have one output. However, for the Moore machine, size(input)=size(output). Since the input-output relations differ, you cannot conclude that a DFA is a Moore machine.


Is there an algorithm for random sampling from a priority queue with probability proportional to priority? Suppose I want to randomly sample from a large set of items, each of which has a "score".  I want my probability of sampling to be proportional to the score.  One simple way to achieve this is divide each score by the total, then randomly sample based on each probability.  This is at least O(N), and running it the next time will be O(N) as well since we have to renormalize.  Inserting is also O(N) because we have to renormalize.  I'm wondering if there is way we can utilize a priority queue or binary tree to make sampling and insertion less costly.
I am thinking for example, store every item in a priority queue, then to sample:
Look at the current item's score, the left item's sum of scores, and the right item's sum of scores.  Normalize by dividing each by the sum of all three, and sample the result.  If the result is the left, rerun the algorithm on the left node.  If the result is the right, rerun the algorithm on the right node.  Otherwise if it's the current node, remove the node and return it as the sample.  It is guaranteed to terminate when it gets to a leaf.  We would have to do some extra work to keep track of the sum, but I think this would make all operations O(log(N)).  Not sure this would sample with the actual required probability or if the time complexity is correct.  Is there any existing work on this?
Edit: I think I found the answer: https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Res

This is exactly what the A-Res algorithm is for
If you have a positive weight for each sample, then you can achieve a probability of sampling proportional to the weight, even without knowing all of the other weights at a given time.  The way you achieve this is:

For each sample: randomly generate a number between from 0 to 1
Raise the result to the power of (1/weight).

It can be shown that a sample with N times the weight of another sample is N times more likely to be greater (have higher priority)


If we execute kernel programs in the user mode and user programs in kernel mode what are some consequences Question on operating system
If we execute kernel programs in the user mode and user programs in kernel mode what are some consequences

Assuming a monolithic kernel like Linux, there just are no "kernel programs", every in-kernel thread is just a function running in the kernel's address space. If you copy that and place it in a userland program (given the correct environment in terms of available data structures and functions to call) it will work fine as long as it doesn't invoke any privileged operations. Any of those will give some sort of exception.
Placing a userland program into the kernel would mean to add a lot of infrastructure provided by the operating system: in C's terms, standard input and output, the contents of the standard C library and any others in use. Using a snippet of userland code in the kernel will work just fine, as long as any infrastructure/environment called upon is provided.
Kernel code and userland code are the exact same instructions (but the kernel has access to some privileged operations and registers that userland can't use).


All strings that contain no run of a's of length greater than two for $\Sigma = \{a,b,c\}$ The solution to this problem is $$(b + c)^*+(b + c)^*((a + aa)(b + c)^+)^*(a + aa)(b + c)^*.
$$
Isn't the $+$ sign a union between sets?, I am asking because I am viewing the line $(b + c)^*+(b + c)^*$
as $A\cup A$ which is $A$ so I do not see a reason to repeat the same set.

The $+$ sign stands for union, but you got the order of operations wrong. Your regular expression is the sum of $(b+c)^*$ and
$$ (b+c)^*((a+aa)(b+c)^+)^*(a+aa)(b+c)^*. $$


SAT not reducible to 2SAT Why is the reduction $\textbf{SAT} \leq_P \textbf{3SAT}$ possible, but $\textbf{SAT} \leq_P \textbf{2SAT}$ not possible, given, that $\textbf{SAT}$ is $\textbf{NP}$-complete, $\textbf{2SAT} \in \textbf{NP}$ and $\textbf{3SAT} \in \textbf{NP}$?

I believe the asker is wanting to know specifically why the standard approach to reducing $\text{SAT}$ to $\text{3SAT}$ does not continue to extend to the $\text{2SAT}$ case. Here is a walkthrough as to why.

Conversion of a SAT Instance to a 3-SAT Instance:

For convenience, let us assume everything is in $\text{CNF}$, or conjunctive normal form. The $\text{SAT} \le_p \text{3SAT}$ proof works by introducing dummy variables to spread the actual variables over multiple clauses.

Illustration: Consider a single clause in boolean formula $(x_1 \lor x_2 \lor x_3 \lor x_4)$. The $\text{3SAT}$ reduction works by introducing a dummy variable to represent a disjunction of two literals in hopes that it reduces the clause's length by one. For example, $y = x_3\lor x_4$. The clause can be rewritten as:

$(x_1 \lor x_2 \lor y) \land (\bar y \lor x_3 \lor x_4)$

Notice that these clauses are now in a $\text{CNF}$ for $\text{3SAT}$. If this is repeated multiple times for each clause, the final $\text{CNF}$ formula will be at most polynomial in length of the original. This is why a polynomial time reduction would suffice.

Attempting to Apply the Method to Convert to 2-SAT:

If we tried to use the trick above with a clause of length 3, $(a\lor b\lor c)$, then we would not get the desired improvement. Let our dummy variable here be $y=b \lor c$.

The result: $(a \lor y) \land (\bar y \lor b \lor c)$

As you can see, it still has a clause of size 3. If we used the method again on the second clause, we would end up with the same problem while also adding an additional clause of length 2.

It could be said that the simplest reason for this is because $\land$ and $\lor$ are binary operators. You still need to apply these operators on pairs of variables, then include an additional dummy variable (resulting in a clause of length 3).

There have been attempts at getting around this that are successful, but the resulting sequence of clauses become exponential in length. Handling such a formula is outside the scope of $\text{P}$, which is why such a reduction would not be a polynomial time reduction.


the height of a tree given n nodes and a condition I came across a question on which I got totally stuck :( a sort of homework question)

A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?

a) log_2 n
b) log_{4/3} n
c) log_3 {n}
d) log_{3/2} n

I cant imagine to solve this one. Intuitive based answer is most welcome.

The height of a tree is 1 + the height of its highest subtree. Which way of distributing the nodes to the subtrees will allow you to maximize that parameter?

   Put $\frac 13 n$ nodes into the left tree and $\frac 23 n$ into the right one (or vice versa).

If you apply this recursively, what do you get for the height?

   You get the recurrence $h(1) = 1$, $h(n) = 1 + h(\frac 23 n)$, $n>1$. This solves to
 $h(n) = 1+\log_{\frac 32}n$.


Proving that DFA equivalence is decidable The following question is taken from Sipser:

  Prove that $EQ_{\mathsf{DFA}}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.

Here is the answer:

  For any DFAs $A$ and $B$, $L(A) = L(B)$ if and only if $A$ and $B$ accept the same strings up to length $mn$, where $m$ and $n$ are the numbers of states of $A$ and $B$, respectively. Obviously, if $L(A) = L(B)$, $A$ and $B$ will accept the same strings. If $L(A) \neq L(B)$, we need to show that the languages differ on some string $s$ of length at most $mn.$ Let $t$ be a shortest string on which the languages differ. Let $l$ be the length of $t$. If $l \leq mn$ we are done. If not, consider the sequence of states $q_0,q_1,\dots,q_l$ that $A$ enters on input $t$, and the sequences of states $r_0,r_1,\dots,r_l$ that $B$ enters on input $t$. Because $A$ has $m$ states and $B$ has $n$ states, only $mn$ distinct pairs $(q,r)$ exist, where $q$ is a state of $A$ and $r$ is a state of $B$. By the pigeon hole principle, two pairs of states $(q_i,r_i)$ and $(q_j,r_j)$ must be identical. If we remove the portion of $t$ from $i$ to $j-1$, we obtain a shorter string on which $A$ and $B$ behave as they would on $t$. Hence we have found a shorter string on which the two languages differ, even though $t$ was supposed to be shortest. Hence $t$ must be no longer than $mn$.

Unfortunately, I do not understand the sequence of steps in the answer. Could anyone explain the answer for me in a simpler way?

Here is a slightly different proof, along similar lines.

Lemma 1. Let $A$ be a DFA having $n$ states, and let $B$ be a DFA having $m$ states. There is a DFA $C$ having $nm$ states such that $L(C) = [L(A) \setminus L(B)] \cup [L(B) \setminus L(A)]$.

The proof uses the product construction (exercise).

Lemma 2. Let $C$ be a DFA having $p$ states. If $L(C) \neq \emptyset$ then $L(C)$ contains some word of length at most $p-1$.

Proof sketch. The language $L(C)$ is non-empty if some final state $q_f$ is reachable from the initial state $q_0$. The shortest path from $q_0$ to $q_f$ has length at most $p-1$, and this corresponds to a word of length at most $p-1$ in $L(C)$.

Theorem. Let $A$ be a DFA having $n$ states, and let $B$ be a DFA having $m$ states. Then $L(A) = L(B)$ iff for all words $w$ of length at most $nm-1$, either $w \in L(A),L(B)$ or $w \notin L(A),L(B)$.

Proof. If $L(A) = L(B)$ then the condition clearly holds. If $L(A) \neq L(B)$ then $\Delta := [L(A) \setminus L(B)] \cup [L(B) \setminus L(A)] \neq \emptyset$. According to Lemma 1, there is a DFA having $nm$ states whose language is $\Delta \neq \emptyset$. According to Lemma 2 (with $p = nm$), there exists a word $w \in \Delta$ of length at most $nm-1$. This is a word for which it doesn't hold that either $w \in L(A),L(B)$ or $w \notin L(A),L(B)$.


Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS? I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.

Construct a new graph $G'$ with the same set of vertices, and with an edge $(u,v)$ iff there is a path of length 2 from $u$ to $v$ in the original graph.  Then, check whether $G'$ has any cycles of any length.  A cycle in $G'$ corresponds to an even-length cycle in the original graph, and vice versa, so this provides a correct algorithm.  The running time is $O(|V||E|)$.


Similarity between two geometric shapes I have two shapes in a 2D space, not necessarily convex, and I'd like to compare how similar they are. How can I define a robust distance metric to measure their similarity, and how can I compute it?

I am looking for a method which provides a short distance in case of:

scaling;
rotation;
perhaps local scaling or rotation.

I see two possible solutions:

transform the shapes into pixel-based matrices (bitmap) and compute a Levenshtein distance (but without enough robustness in the distance, in case of rotation for instance);
transform the shapes into graphs and try to define a distance between them.

One approach would be to use SIFT (or SURF, or other similar methods) to align one object to the other to account for scaling and rotation, and then compute a pixelwise distance based on the aligned images.

The right algorithm to use for alignment will depend upon the nature of the 2D images.  If they are natural-color photographs taken using a camera, SIFT, SURF, etc. might work well.  If they are black-and-white geometric shapes like shown in the question, you might do better to use image moments (e.g., Hu moments) or some other approach.


Terminology for a graph obtained from another by adding edges $H$ is a supergraph of $G$ if it can be obtained from $G$ by adding, edges, vertices, or both.

Is there a standard terminology for a graph that can be obtained from $G$ only by adding edges?

If $H$ is made by adding only edges to $G$, then $G$ is a spanning subgraph of $H$. However, I'm not aware of any way of phrasing it that makes $H$ the subject of the sentence.


Showing undecidability I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket notation to denote the encoding of the TM and input string)

Given that I know the set $A = \{\langle M,w\rangle : M \text{ accepts } w \}$ is undecidable but recognizable, I'm trying to show that $A$ reduces to $T$.
I start by assuming that $T$ is decided by a Turing Machine $R$ and then attempt to construct a new Turing Machine, $S$, that will decide $A$ by using $R$ as a subroutine.

To construct this new machine $S$, I will run $R$ on input $\langle M,w\rangle$. If $R$ accepts, then $\langle M,w\rangle$ is in $A$. However, $R$ rejecting doesn't necessarily mean that $\langle M,w\rangle$ isn't in $A$, since $M$ might reject $w$ reversed but accept $w$. So now I'm confused on how to actually construct the reduction. Any help would be great

I am interpreting the word "whenever" in the definition of $T$ to mean that $T$ consists of all pairs $\langle M, w \rangle$ such that either $M$ accepts $w$ and $w^R$ or $M$ rejects $w$ and $w^R$. Please, correct me if this is wrong.

I will show a reduction from $A$ to $T$. Input $\langle M, w\rangle$ will be transformed to $\langle M', w'\rangle$ as follows:

$w' = 0w1$
$M'$ on input $w'$ strips the first bit $b_1$ and last bit $b_2$ off $w'$. Let $w$ be the remaining string. If $b_1 = 0$ then $M'$ runs $M$ on $w$ and outputs accordingly. Otherwise, if $b_1 = 1$ then $M'$ simply accepts.

I claim that $\langle M, w \rangle \in A$ if and only if $\langle M', w' \rangle \in T$:

If $M$ accepts $w$ then $M'$ on $0w1$ simulates $M$ on $w$ and accepts. Also, $M'$ on $(0w1)^R = 1w^R0$ immediately accepts, since the first bit is $1$. Thus, $\langle M', w' \rangle \in T$.
If $M$ doesn't accept $w$ then $M'$ on $0w1$ simulates $M$ on $w$ and doesn't accept. However, $M'$ on $w^R = 1w^R0$ accepts. Thus, $\langle M', w' \rangle \notin T$.


How does the nearest insertion heuristic for TSP work? In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson Problem".

In it we covered the "Nearest Neighbor", "Closest Pair" and "Insertion" heuristics approach to solve the TSP Problem.

The first two are quite clear - the first one connects the starting point to the nearest neighbor and then connect that to its neighbor and so on. The second one you move to the point closest to one of the two ends of your current path. But I don't understand how the third one actually works.

The example is as follows:

And continue this five more times and you get the answer below.

I think that by "insertion heuristic" you mean "nearest insertion heuristic". If this is the case, here is how it works:

We're looking to construct a cycle $C$ containing all the nodes of our problem. We will do this by initially constructing a small cycle and slowly adding nodes to it until it contains all the nodes. We start by choosing some starting node $N$ and adding it to $C$. $C$ now contains a single node, $N$.
We want to add to $C$ the node which will increase its length the least. To do this we need to find which node to add to our cycle and then figure out where in the cycle to put it. We select this node by choosing the node (not in $C$) which is the closest to any node in $C$. We then insert this node between two nodes in $C$ such that the increase in length is minimal. More formally: Let $k$ be the node we selected. Find an edge $(i,j)$ such that $d_{ik}+d_{kj}-d_{ij}$ is minimal.
Add $k$ to $C$, remove edge $(i,j)$, and add edges $(i,k)$ and $(k,j)$.
If $C$ contains all the nodes, stop. Otherwise, go to 2.


Unary encoded language set While reading the book theory of computation by Michael Sipser, I did not understand the language given below. I will explain the problem first

  $$L = \{1^n :n \in \mathbb{Z}\}$$

Where $\mathbb{Z}$ is a set of integers.

Question :I am not able to understand the string that belong to the given set will look like.

I know if input alphabet is $\{0,1\}^*$ then string 0101 (5 in decimal).

Forget about strings meaning anything. For any symbol $a$ and natural number $n$, $a^n$ is the string made from $n$ copies of $a$. So $a^1=a$, $a^2=aa$, $a^5=aaaaa$ and $a^0$ is the empty string, usually written as $\varepsilon$ or $\lambda$.

The set $\{1^n\mid n\in\mathbb{Z}\}$ isn't well-defined (did Sipser really write that?), since $-1\in\mathbb{Z}$ but $1^{-1}$ doesn't make sense: what would $-1$ copies of the symbol $1$ look like?

However, the set $\{1^n\mid n\in\mathbb{N}\}$ is just $\{1^0, 1^1, 1^2, 1^3, \dots\}$, i.e., $\{\varepsilon, 1, 11, 111, \dots\}$ (I'm considering zero to be a natural number; delete $\varepsilon$ if you think that one is the first natural number). Now, strings such as $111$ can be interpreted as numbers written out in some base (unary, binary, decimal, whatever). But the definition is just giving you a set of strings.


Optimality in multi-agent multi-target path finding Suppose I have a regular rectangular weighted grid with multiple agents and obstacles. Agents cannot be in grid sites that contain obstacles, and for simplicity assume multiple agents can be in the same grid site.

If I select a single location on the grid and want to find the nearest agent to that location, a good solution is easy: I can simply do a breadth-first (BF) search.

However, suppose I have n target locations and m>=n agents. I want to visit the target locations with n agents simultaneously. I do not care which agent goes to which location, but the total distance travelled must be minimal. Or, to rephrase, I'm attempting to find a distance-weighted maximum matching for two sets of nodes on a graph.

One solution would be to calculate the shortest path from all agents to all targets and then do a bipartite matching. Since the graph may be disconnected by obstacles, this could result in needless multiple sampling of the entire grid space of a connected region. This hardly seems optimal. (Solution 1)

I propose the following 'algorithm' (Solution 2):

from each target location start a BF search until there is one agent in every target's searched space
if the number of unique agents in the searched spaces is less than n, continue searching from all target locations
if a matching between targets and agents in their respective searched spaces is not possible with full target covering, continue searching from the target locations where covering was not possible and all other target sites that share agents with the uncovered target sites all target locations.
the first matching that fulfils step 3 is the solution

now I have two questions:

is solution 2 optimal, i.e. is it guaranteed that I will select precisely those agents with the least total distance to their assigned targets? I.e. am I not neglecting any agents by not continuing the search for long enough?
if solution 2 is optimal, are there any further ways of reducing the computational complexity?

Read the following paper on the generalization of your problem with "makespan" as the objective. The proposed algorithm should work even if $m\neq n$.

H. Ma and S. Koenig. "Optimal Target Assignment and Path Finding for Teams of Agents." http://idm-lab.org/bib/abstracts/papers/aamas16a.pdf


Notation: SPACE(n) vs SPACE(O(n)) I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not preferred in this case? In particular, I'm writing a project in which I need to distinguish between problems solvable in space $c_1\cdot n$ and problems solvable in space $c_2\cdot n$ for $c_2>c_1$.

Which notation should I use? $SPACE(n)$ or $SPACE(O(n))$?
And how to distinguish between space $c_1\cdot n$ and $c_2\cdot n$ without confusion?

It depends on what definitions you use.  Sipser [1] defines $\mathrm{SPACE}(f(n))$ to be the class of languages decided by Turing machines using $O(f(n))$ cells on their work tapes for inputs of length $n$.  Papadimitriou [2], on the other hand defines it to be the class of languages decided by Turing machines using at most $f(n)$ cells on the work tapes.

However, the space analogue of the linear speedup theorem implies that, actually, these two definitions are equivalent, so you should pick whichever one is most convenient for you. Since you want to distinguish between machines that use up to $c_1n$ work space and those that use up to $c_2n$, the Papadimitriou-style definition seems more appropriate to your needs. Make sure you clearly and explicitly define $\mathrm{SPACE}(f(n))$ before using it. But do be aware that anything you can do with $n$ worktape cells using a $k$-symbol alphabet, I can do with $n/2$ cells by using an alphabet of size about $k^2$. Unless you're using a fixed tape alphabet, $\mathrm{SPACE}(c_1n)$ and $\mathrm{SPACE}(c_2n)$ are the same complexity class, even with the Papadimitriou-style definition.

References

Michael Sipser, Introduction to the Theory of Computation. Cengage Learning, 3rd edition, 2013. (Earlier editions almost certainly use the same definition.)
Christos H. Papadimitirou, Computational Complexity. Addison Wesley Longman, 1994.

Acknowledgments
Thanks to The Vee for pointing out an error in an earlier version of this answer.


Given a connected graph with edges >= vertices, find an algorithm in O(n + m) that orients the edges such that every vertex has indegree of at least 1 I'm not exactly sure how to approach this problem. I was thinking we would need to detect a vertex in a cycle, then run DFS on it while also orienting the edges along each vertex u in the cycle, to be directed from u to some vertex v incident to it. But I am not sure what edges cases I might be overlooking, or whether the idea is sufficient. Below is one such example.

Start with any vertex $v_s$, and do a BFS from that $v_s$ to discover the entire graph.  When you traverse an edge, you orient it away from the start node.

Now every vertex $v \in V \setminus \{v_s\}$ has $\deg_{\text{in}}(v) > 0$.

Find a path from $v_s$ to any vertex $v_t$ such that $\deg_{\text{in}}(v_t) \geq 2$.  Since the input graph is not a tree, such a vertex must exist.

Flip all edges in the path.

This graph satisfies your requirement since

every internal vertex $v_i$ in the path still has $\deg_{\text{in}}(v_i) > 0$,
$v_t$ now has $\deg_{\text{in}}(v_t) \geq 1$ (it decreased by one), and
$v_s$ has $\deg_{\text{in}}(v_s) > 0$.

Running time: $O(n + m)$.


Proving problem NP-completeness I am studying computational complexity and i am trying to solve this problem.
We are given a (non-bipartite) complete graph:

G = (V, W, E)

where the vertices can be divided in two classes V and W and the edges between any two vertices are weighted either 1 or 0.
w(x, y) = {0, 1} ∀ x, y ∊ V ∪ W

We need to:

calculate a subset I ⊆ V ∪ W that maximizes the sum of the weights of the edges that link the elements of I, divided by the I cardinality.
max(1 / |I| ∑ w(x, y) ∀ x, y ∊ I)
The calculated subset I must have the same number of vertices of V and W.
|I ∩ V| = |I ∩ W|

I would need to prove that this problem is NP-complete.

I have thought about reducing the problem to a vertex cover, removing the incident vertices to a 0 edge, but that would compromise the optimal solution.
And even considered this, i have found many difficulties trying to figure out a optimal certifier for the algorithm, which would prove the problem to be at least NP.
Any clues on a strategy to follow?

First, when doing complexity analysis, we usually think in terms of decision problems, i.e. the answer must be yes or no, and here you have an optimisation problem. This is why you are struggling to find a certificate here. If you reformulate your problem as a decision problem with an additional parameter $k$, and the question become "Is there a subset I such that the sum (...) Is greater than k ?", You will easily find the certificate : the list of the vertices in I, you can polynomially check that there are as many elements of V and W, and that the sum has the desired property.

Second, it seems like your are trying to reduce your problem to VERTEX-COVER. However, we already know that's possible because VC is NP-complete. To show that your problem is NP-Hard, you have to reduce a NP hard problem to it.

Finally, the reduction : maybe something from VERTEX-COVER will work : take an instance with a graph G=(V,E), make it complete by adding edges and put their weight to 0 (then your problem will not "try" to get them). If you find a clever way to divide V into V and W, the reduction might work.
However, it seems to me that VERTEX-COVER does not have a condition on sets and partitions, and you might have more luck with Subset-sum or 2-partition.

Edit : after a bit of thinking, If you make 2 copies of G (one becomes your V and the other W), and complete it with 0-weighted edges, you juste have to find the correct value for k... I think that's not too far.

I hope that helps.


Join large list of pairs I have a list of millions of pairs of strings, and I want to join all of the pairs that have matching members into lists without duplicates.

Example input:

[["A", "B"],
 ["A", "D"],
 ["M", "Q"],
 ["A", "F"],
 ["D", "E"],
 ["Q", "Z"]]

Example output:

[["A", "B", "D", "E", "F"],
 ["M", Q", "Z"]]

Does anyone know of an efficient algorithm for this?  I'm somewhat constrained by memory.  Anything that would square the memory from the input would not be an option.

You can use a two pass approach:

In the first pass, identify all the different strings appearing in your input. (This can be done in various ways, e.g. hashing, trie, BST)

For the second pass initialize a Disjoint-set data structure with the strings found in the first pass and perform a union operation for each pair in the input.


C(++) library for DFAs - free for academic use (I'm aware that software questions are better suited for stackoverflow, but since DFAs are not something that software developers usually care about, I hope it's alright if I ask here.)

I'm currently working on a project to do with regular overapproximations for context free languages. For this purpose, I need to implement stuff that requires me to represent regular languages in a minimized form, intersect them, complement them, etc. - i.e. everything that's easy and quick to do with DFAs. However, I'm having a hard time finding still-maintained libraries for DFAs in C++. I could find libfa which does everything quite nicely, but that's as far as I've gotten. Grail hasn't been maintained in 15+ years and the download link is dead. FAdo seemed interesting initially, but it's in Python and I can't determine whether there's a way to use it as a C++ library, or whether it offers the functionality I mentioned above (the Docs are a bit slim).

Do you know of C(++) libraries for DFAs that offer minimization, intersection and complementation that are free for academic use? I'd like to have at least one alternative to libfa that I can use.

I don't know of a full blown library, but based on [1] there is a really fast practical C++ implementation available from the author's homepage here.

[1] Valmari, Antti. "Fast brief practical DFA minimization." Information Processing Letters 112.6 (2012): 213-217.


What are some real world applications of graphs? Can you give some real world examples of what graphs algorithms people are actually using in applications?

Given a complicated graphs, say social networks, what properties/quantity people want to know about them?

—-

It would be great if you can give some references. Thanks.

Graphs are definitely one of the most important data structures, and are used very broadly

Optimization problems

Algorithms like Dijkstra's enable your navigation system / GPS to decide which roads you should drive on to reach a destination.

The Hungarian Algorithm can assign each Uber car to people looking for a ride (an assignment problem)

Chess, Checkers, Go and Tic-Tac-Toe are formulated as a game tree (a degenerate graph) and can be "solved" using brute-force depth or breadth first search, or using heuristics with minimax or A*

Flow networks and algorithms like maximum flow can be used in modelling utilities networks (water, gas, electricity), roads, flight scheduling, supply chains.

Network Topology

The minimum spanning tree ensures that your internet traffic gets delivered even when cables break.

Topological sort is used in project planning to decide which tasks should be executed first.

Disjoint sets help you efficiently calculate currency conversions between NxN currencies in linear time

Graph coloring can in theory be used to decide which seats in a cinema should remain free during a infectious disease outbreak.

Detecting strongly connected components helps uncover bot networks spreading misinformation on Facebook and Twitter.

DAGs are used to perform very large computations distributed over thousands of machines in software like Apache Spark and Tensorflow

Specialized types of graphs

Bayesian networks were used by NASA to select an operating system for the space shuttle

Neural networks are used in language translation, image synthesis (such as fake face generation), color recovery of black-and-white images, speech synthesis


Merge sort and quicksort recursion tree depth 1)
I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about 100 or 1000 elements? How do I determine recursion tree depth for them? Is there any pattern that I cannot see? What if someone would ask me for recursion tree depth for a string composed of one million elements?

2)
I need to determine the biggest and the smallest recursion tree depth for strings composed of 10, 100 and 1000 when using quicksort. So it's kind of similar but those could be any strings, so is there even constant number that defines the smallest and the biggest? How to count this?

3)
I need to provide a recursive dependency which value for the given $n$ is the number of recursion tree levels of recursive calls of merge sort for an $n$-element string.

There is a pattern, and it has to do with the fact that you are splitting the lists in half in each time. Keep in mind the runtime of mergesort is $O(n \cdot log(n))$, that should provide some hints as to where to go with this problem.
There isn't really a even constant unless you define the constant in terms of $n$. I wouldn't think about this problem in that way, instead I would consider the best and worst cases for quicksort, i.e what choice of pivot is the best / worst, and how does it affect the depth of the recursion tree?
This is very similar to the first problem, in fact, I believe if you figure out the first problem, then this one shouldn't be too hard to come up with. Once again, think about the fact that you are halving the size of the list each time. I'm not sure if you are familiar with recurrence relations, and if not that is something you will definitely want to take a look at.

Here is a good resources to look at:

The whole chapter will be a good read, but for your purposes, just the bits about mergesort and quicksort will suffice

http://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf

I have only given hints and general guidance because I think this is a good problem to think about and to test your understanding of general algorithm analysis, but if you need a stronger hint, feel free to comment.


Regular languages and constructing a regular grammar I'm pretty new to computer science and just read about the concept of grammars. Now, I have a practical problem to solve. Here is the alphabet {a, b, c, d}.

How can I determine if the language consisting of all strings a^k b^n c^m d^l, where all k,n,m,l >= 1 is regular. I need to do this because as far as I got all regular languages may be parsed by a regular expression. So, to avoid generating my own parser and lexer, is it possible to do so?

My first attempt was to construct a regular grammar generating the language. I failed, but that doesn't mean that the grammar does not exist. I would appreciate any advice.

First of all it is enough if we can give regular expression for a regular language. To determine if a language is regular you have to show existence of a DFA or a regular expression for the language. Or you can show it is regular if you can prove it is union, intersection, concatenation, etc. (operations under which regular languages are closed) of other known regular languages.

The language in question is regular because it has regular expression $aa^*bb^*cc^*dd^*$.

To construct a regular grammar you need to do it step by step.

$A \rightarrow aA\ \  | \ \ a$
$B \rightarrow bB\ \  | \ \ b$
$C \rightarrow cC\ \  | \ \ c$
$D \rightarrow dD\ \  | \ \ d$

Then finally,

$S \rightarrow ABCD $

Yet another method to get a regular grammar is to convert from DFA. Then you will get (which might be a little difficult to understand right away):

$S \rightarrow aA$
$A \rightarrow aA\ \ |\ \ bB$
$B \rightarrow bB\ \ |\ \ cC$
$C \rightarrow cC\ \ |\ \ dD$
$D \rightarrow dD \ \ |\ \  \epsilon $

My two cent opinion is directly write a lexer (or use automatic-lexer-generator like flex) rather than writing a parser (or using automatic-parser-generator like bison).


Infinite prefix-closed context-free languages contain an infinite regular subset The Problem:

Say that a language is prefix-closed if all prefixes of every string
in the language are also in the language. Let C be an infinite,
prefix-closed, context-free language. Show that C contains an infinite
regular subset.

Can we show this by using Myhill-Nerode Theorem?

Given a normal form grammer $G$ for an infinite prefix-closed $L$, examine the (almost) regular grammer $G'$ obtained by transforming rules of the form $A\rightarrow BC$ into $A\rightarrow B$. I leave it to you to show that $L(G')$ satisfies your requirements.


In the Gas-Up problem, how is the amount of gas the same up to a cyclic shift regardless of starting city? I'm working through Elements of Programming Interviews as practice for finding a job. I've spent a ridiculous amount of time on Problem 18.7.

  In the gas-up problem, $n$ cities are arranged on a circular road. You
  need to visit all of the $n$ cities and come back to the starting
  city. A certain amount of gas is available at each city. The total
  amount of gas is equal to the amount of gas required to go around the
  road once. Your gas tank has unlimited capacity. Call a city $c$
  ample if you can begin at $c$ with an empty tank, refill at it, then travel through each of the remaining cities, refilling at each, and
  return to $c$, without running out of gas at any point. See Figure
  18.3 for an example. [You can see Figure 18.3 on the Google Books result if you search for "Elements of Programming Interviews Problem
  18.7.]

  Given an instance of the gas-up problem, how would you efficiently [i.e. in $\mathcal{O}(n)$ time or better]
  compute an ample city, if one exists?

I couldn't figure it out. I read the hint, and I still couldn't figure it out. I gave up, and read the answer in the back of the book. I still couldn't figure it out. I searched Google and this site for a more complete solution, but didn't find one.

This is the part that's getting me:

  On closer inspection, it becomes apparent that the graph of the amount
  of gas as we perform the traversal is the same up to a cyclic shift
  regardless of the starting city.

I must not be inspecting closely enough, because this is not apparent to me at all. I tried calculating the remaining gas at each city during a traversal of an example circuit, starting at different cities (and permitting the number to be negative when necessary, as the solution suggests). There does not seem to be any relation between the series of numbers I get when starting at different cities. I understand, if we accept that the amount of gas remaining at each city is the same up to a cyclic shift, how the algorithm the solution gives would solve the problem. I cannot see how this is the case. What am I missing?

This is over a year later, but I also found this question really frustrating, but after reading other explanations, I've finally figured it out. So, I want to share with everyone my findings!

In this problem we're guaranteed that the amount of gas is enough to go around the road once. We then have this equality
$Amount_{gas}$ = $Amount_{distance}$
$$\sum_{i=1}^{n} x_{i} = 0$$
where $x_{i}$ is the Amount of gas at station i - the cost:
$$G[i] - D[i]$$

If we reach a point $j$ such that:

$$\sum_{i=1}^{j} x_{i} < 0$$

This must mean
$$\sum_{i=j + 1}^{n} x_{i} > 0$$

Why!?!??! Because the problem promises us enough gas to cover the distance!
$$\sum_{i=1}^{j} x_{i}  + \sum_{i=j + 1}^{n} x_{i} = 0$$

If we start at point $j + 1$, which is right after we don't have enough gas,
the equation becomes
$$\sum_{i=j + 1}^{n} x_{i} + \sum_{i=1}^{j} x_{i} = 0$$

Starting at $j + 1$ means we have $\sum_{i=j + 1}^{n} x_{i}$ gas before j, so we won't have a negative number.

This agrees with the solution in EPI because we are in fact doing a vertical shift on our piecewise function $\sum_{i=1}^{n} G_{i} - D_{i} $
The pictoral graph in EPI helps us see that it's not good enough to merely spit out the first j that gives us a negative value. If instead, we find the minimum, we will have more than enough gas before we reach j (first point that gives us negative amount of gas left) and cover subsequent negative gas stations until the aforementioned minimum.


Finding Big O of 1/n + 1/n+2 ... 1/n' The number of computations of an algorithm is $n'm\sum_{x=0}^{n'-m} 1/(m+x)$. What is the complexity of the algorithm ?

Thanx for help.

Selah, instead of asking for more references and definitions, you can just use the fact that for the n values n ≤ k < 2n, we have $1/{2n} ≤ 1/k ≤ 1/n$. So the sum of $1/k$ for n ≤ k < 2n is between 1/2 and 1.

Not nearly as nice as Yuval's result, but it should be more than good enough to solve your problem.


Generating hard puzzles for a backtracking snake Let $M$ be a matrix of height $h$ and width $w$. Each entry of $M$ is an integer.

There is a snake that starts from the "left side" of $M$, and its goal is to reach the "right side" of $M$. To get from one side to the other, i.e. to move from column $c$ to column $c+1$, the snake must choose an integer from both. Whatever the snake picks from column $c$, it can never pick the same integer again in $c+1$, nor from any column that appears later.

For example, suppose each entry in column 1 has integer 1, each entry in column 2 has integer 2, and so on. Now the snake can move very freely: in fact, we have $h$ choices in each of the $w$ columns. Even a blind snake gets through the matrix easily.

The goal is to generate matrices that are difficult for a snake that performs some kind of exhaustive backtracking search. The matrices can be tall, but preferably not wide. Can we assign the integers to $M$ such that there is exactly one (i.e. a unique) path through it? The hope is matrices with unique valid paths through them are difficult for a backtracking snake.

Here's an idea for generating instances with a non-unique solution that will be difficult to solve by backtracking but actually are quite easy to solve:

Let $M$ be $h$ tall and $2w$ wide. Take the integers ${1, 2, ... w}$ and fill $M$ with them randomly. For $i = 1$ to $w$, replace column $w + i$ to be the column with only the value $i$.

We know that $M$ has no solution, because it requires $2w$ unique integers to bring the snake across the matrix.

Now, for the first $w$ columns of $M$, replace a random element of column $i$ with the number $w + i$.

Then, it follows that the sequence of integers corresponding to any solution is $w + 1, w + 2 .... 2w, 1, 2, ...... w$. This is very easy to find, unless you are searching by backtracking. In particular, the first $w$ columns have a unique correct choice.

Here's an example of a matrix made by this algorithm:

$$ \begin{array}{ccc}
1 & 5 & 2 & 1 & 2 & 3 \\
3 & 3 & 2 & 1 & 2 & 3 \\
4 & 1 & 1 & 1 & 2 & 3 \\
2 & 2 & 2 & 1 & 2 & 3 \\
2 & 3 & 6 & 1 & 2 & 3 \\
3 & 1 & 3 & 1 & 2 & 3 \\
1 & 1 & 1 & 1 & 2 & 3 \\ \end{array} $$

To make a given instance harder, just make the matrix arbitrarily taller.


Regular expression notation clarification For the alphabet $Σ$={a,b,c}

I was wondering how you would say:

  T that has elements from Σ, so could be T=a, T=bc

I was considering maybe $Σ^*$ or $Σ^+$ would describe that, but I am not sure what both of them mean.

I guess $Σ^*$={aa, aaa, ba, abc, ...} and not sure what $Σ^+$ is.

Usually, $\Sigma^*$ denotes the set of all strings of length zero or more over the alphabet $\Sigma$. Thus, $\Sigma^* = \{\epsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, \ldots\}$, where $\epsilon$ denotes the empty string.

$\Sigma^+$ is the set of all strings of length $1$ or more over the alphabet $\Sigma$.  Thus, $\Sigma^+ := \Sigma^* - \{\epsilon\} = \{a,b,c,aa,\ldots\}$.


In top-down parser how do you match a product $A \rightarrow a_1 | a_2 | ...$, $a_i$s terminals One procedure for table-driven top-down parsing is given here:
https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html

This gives for matching the input the lines:

else if NextInputSymbol == top then
    /* Match terminal symbol in input */
    Pop(stack)
    /* Get next terminal symbol in input */
    scanner(NextInputSymbol)

Which seems to be assuming that every product leading to terminal symbols has only one terminal.

But what if the product leading to terminals is of the following form:
$$A \rightarrow a_1 | a_2 | ...$$
where $a_i$s terminals.

How do you match for such product?

Merely by trying out each terminal symbol?
But reading them all to the stack would cause some overhead for keeping account of how many terminals symbols were added?

In predict table form:

If a symbol is on the top of the stack, it must have gotten there after being pushed by the code just above the test:

        for each symbol on RHS #action do
            Push(symbol)

(There is a small imprecision in that code; it doesn't mention that "for each symbol on RHS" actually means "for each symbol on RHS from right to left" but that's evident from examining the example stack sequence.)

That code snippet, in turn, was executed after the parse table is used to decide which production will apply, which it did  by examining the next input token:

    if top is a nonterminal then
        action = ParseTable[top,NextInputSymbol]

So let's read the code forwards instead of backwards. We'll suppose that $A$ is on top of the stack, and that $A$ has productions as you indicate:

$$A\to a_1\\
A\to a_2\\
...\\
A\to a_n$$

Now, we can only push one of those productions. Which one will we push? By the construction of the $ParseTable$, we can say that we will push the production whose $FIRST$ set includes the next input symbol. But in this case, that's even simpler because the $FIRST$ set of each of those productions obviously comprises the single terminal on the RHS of the production. So if the next input symbol is $a_2$, for example, the ParseTable will indicate an action corresponding to $A\to a_2$. So the $A$ will be popped from the top of the stack and then $a_2$ will be pushed.

At the next step, the top of the stack is a terminal; precisely the terminal $a_2$. And, surprise!, the next input symbol is also $a_2$. So we can just pop the stack and continue with the parse.

In short, the $ParseTable$ lookup substitutes for that long imaginary sequence of if statements. The lookup could internally be implemented with such a chain, but in real-life it would probably turn out to be a more efficient table lookup algorithm.


Calculating the number of multiplications necessary to evaluate a polynomial I was watching a lecture and got confused over a slide. This is what it says:

Consider a polynomial - first representation
$$P = 2 + 4x^{3} + 8x^{6} + 7x^{25} + 6x^{99}$$

The space complexity is 100 memory locations.
The time complexity is:

Access lookup operations: 100
Multiplication operations: 4 + 7 + 26 + 100 = 137
Addition operations: 5
Total operations: 242

I don't get how the number of multiplication operations are counted. For example, if we consider $x^{3}$ then it should have just two multiplications, right? Such as $x \times x \times x$, isn't it?
Addition operation is 5 or 4...I think its 4?

I am not sure what the slide was intended for, so I just gave a
straight answer to your question in a comment, viz that the slide
really intended 3 multiplications for $4x^3=4\times x\times x\times
x$, and 4 additions to add the five terms.

Now of course, there are better ways to do that. Various powers of $x$
can be obtained in multiplying other powers of $x$ together using the
rule $x^m\times x^n=x^{m+n}$.

The method of repeated squaring presente by David Richerby in his
answer is a systematic way to get high powers of $x$ as fast as
possible. However, when you need a few specific powers, you can try to
adapt it to compute just these powers with as few multiplications as
possible.

So you can compute, for example:

$\begin{align}
x^2&=x\times x \\
x^3&=x^2\times x \\
x^6&=x^3\times x^3 \\
x^{12}&=x^6\times x^6 \\
x^{24}&=x^{12}\times x^{12} \\
x^{25}&=x^{24}\times x \\
x^{49}&=x^{24}\times x^{25} \\
x^{50}&=x^{25}\times x^{25} \\
x^{99}&=x^{49}\times x^{50}
\end{align}$

Hence you get all needed powers of $x$ with only 9 multiplications of
powers of $x$, to which you have to add 4 multiplications for the
coefficients, which makes a total of 13 multiplications. The number of
additions remains at 4.

But you can do a bit better using a technique that is most
efficient when all powers of $x$ are being used, rather than having a sparse
polynomial. The technique, known as Horner's method, consists in
factorizing some powers of the variable, when it helps the
computation.

In the case of your sparse polynomial, you may notice that
$7x^{25}+6x^{99}=x^{25}(7+6x^{74})$. Hence rather than computing
$x^{50}$ and $x^{99}$, you compute only

$x^{74}=x^{49}\times x^{25}$ and then $x^{25}(7+6x^{74})$.

This saves one multiplication, because both $7x^{25}+6x^{99}$ and
$x^{25}(7+6x^{74})$ take exactly 2 multiplications and one addition,
assuming the powers of $x$ are already computed, but computing the
needed powers takes one less multiplication.

So you are down to a total of 12 multiplications and 4 additions.

I do not see any way to do better on this example, but I have no
systematic algorithm to check that. However, I am rather confident
that someone must have worked on it.

BTW, what was the theme of the set of slides?


Size of Maximum Matching in Bipartite Graph Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $\min(|U|, |V|)$?

Given a bipartite graph $G = (U,V,E)$ and a maximum matching $M$ of $G$, via Konig's Theorem we see that $|M| = |C|$ where $C$ is a minimum vertex cover for $G$. Your statement is merely an upper bound on the size of the possible matching, not a strict equality.

The image on the wikipedia page provides a nice counterexample to your claim. We see that $|M| = 6$, while $\min(|U|,|V|) = 7$.

However, in the case of a complete bipartite graph $K_{n,m}$ your statement holds.


Does the master theorem apply to T(n) = 3T(n/3) + nlogn? I am given an example of a case where the master theorem does not apply, but it seems like it should apply.

This was the reasoning:

$T(n) = 3T(n/3) + n \log n$ with $
 a = 3, b=3, f(n) = n\log n$ and  $n\log_b a = n\log_3 3 = n$

$f(n)$ is asymptotically larger than $n\log_b (a)$
, but not
polynomially larger. The ratio $n \log n / n = \log n$ is
asymptotically less than $n^\epsilon$
for any positive $\epsilon$. Thus,
the Master Theorem doesn’t apply here

However, it seems like case 2 of the master theorem should apply here.
We have $f(n) = n\log n$, and thus $f(n) = \theta(n^{\log_3 3} \log n$)

Then: $T(n) = \theta(n^{\log_a b} \log^{k+1}n) = \theta(n\log^2 n)$

Which is correct?

Let's take the slightly more general case where $a=b$ and $f(n)=n\;log\;n$ (in your case, $a=b=3$). Assume the usual restrictions on $a$ and $b$ hold. Then $n^{log_ba}=n$. This might lead us to consider case 3 of the Master Theorem since $f(n)=\Omega(n)$.

However, the theorem requires that there exist an $\epsilon > 0$ such that $n\;log\;n = \Omega(n^{1+\epsilon})$. Is this condition met? Equivalently, is it true that $log\;n = \Omega(n^{\epsilon})$ ? As long as $\epsilon$ is positive, this is never true. The polynomial will grow faster. Therefore, the Master Theorem does not apply. You could use iteration or some other method to solve the recurrence.

After searching around, I've found a few references to a corollary of the Master Theorem that addresses polylogarithmic functions. In this version, if we can show that $f(n)=\Theta(n^{log_ba}log^{k}n)$ for some $k \geq 0$, then we can conclude that $T(n) = \Theta(n^{log_ba}log^{k+1}n)$. In our case, $f(n) = \Theta(n\;log\;n)$ with $k=1.$ Therefore, we could conclude that $T(n)=\Theta(n\;log^{2}n)$. However, I don't think this is commonly referred to (or taught) as part of the Master Theorem.

Reference 1

Reference 2


Basic notation in lambda calculus I have started learning lambda calculus from the book by Hindley and Seldin.

It brought up the concept with the function $x-y$, first as a function of $x$ and then as a function of $y$. In a way, it emphasized the difference between treating the expression as a function of $x$ and function of $y$, giving separate names to the functions.

$$f(x,y) =  x-y \qquad\text{and}\qquad g(y,x) = x -y$$
and, in $\lambda$ notion,
$$h = \lambda xy.x-y \qquad\text{and}\qquad g = \lambda yx. x-y\,.$$

If I am not wrong then it can be inferred that $f =\lambda x .(x-y)$ means that while computing the value of the expression the expression will vary only with  $x$ and similarly when $\lambda$ is placed with $x$ the other variable $y$ will be kept as a constant.

But then it said that this can be denoted as, with $h$ being the common name of the function
$$h = \lambda xy.(x-y)\qquad\text{and}\qquad h = \lambda yx.(x-y)\,.$$
Is it so that in the above expression the variable which is adjacent to $\lambda$ receives the value and the other one is constant?
The above function is called a two-place function; what does that mean?

Then he introduces the following function in $\lambda$ notation calling it a one-point function:
$$h^\star = \lambda x .(\lambda y . x−y)$$
and says that, for each number $a$, we have $h^\star(a)=\lambda y . a−y$.
Here $a$ is being provided as an argument but $\lambda$ is placed near $y$. Why is this?

And then it deduces that $(h^\star(a))(b)=(\lambda y . a−y)(b) = a−b = h(a,b)$ and says $h^\star$ can be viewed as "representing" $h$. Is "representing" a technical term? How was  $(\lambda y . a−y)(b) = a−b$ concluded?

If I am not wrong then it can be inferred that :

  $f=\lambda x.(x−y)$ means that while computing the value of the expression the
  expression will vary only with "x" and similarly when "lambda " is
  placed with x the other variable y" will be kept as a constant .

Yes, intuitively that's how it works.

What you're looking is called Currying and it's explained fairly early in this book (in fact, I think it's the next section but I don't have a copy now to check). So when we want to work with functions with many arguments we often do it like this:

$$ f(x,y,z) = x\times y + z$$

But you can break this into simpler functions, $(x \times y)$ and $(+z)$. The multiplication can be broken into even simpler terms, first I provide $x$, then just multiply by $y$, that is, $f^{\star}(y) = x\times y$.

Defining some 1-argument functions:

$$
\begin{align*}
plus_z &:= f^\prime(s) = s + z\\
 times_y &:= f^\star(s) = s\times y
\end{align*}
$$

Combining these we can rewrite $f$ as:

$$ f(x,y,z) = f^\prime(f^\star(x)) = plus_z (times_y ~ x) $$

Writing this in using $\lambda$ we have:

$$ \lambda x y z. (x\times y + z)  \equiv \lambda x.\bigg(\lambda y. \Big(\lambda z. (x\times y + z ) \Big) \bigg)$$

What the author has shown is that you can take a function with many arguments and transform it into many simpler functions with just one argument, the bigger function is just a composition of the simpler ones.

So just how the proof works? In your book the following functions are defined:

$$
\begin{align*}
h^\star &= \lambda x . (\lambda y . x − y)\\
h(x,y) &= x-y
\end{align*}
$$

You want to show that $ h^\star = h$. To do that just take any two arguments $a$ and $b$. First evaluate $h^\star$ in $a$.

$$ h^\star(a) = (\lambda x. (\lambda y. x - y))(a) = \lambda y. a - y$$

This gives you a simpler one argument function $h^\prime = h^\star(a)$.

  How was $(λy.a−y)(b)=a−b$ concluded

The same way $(\lambda x. (\lambda y. x - y))(a) = \lambda y. a - y$ was concluded. Just evaluate the function in $b$.

$$ h^\prime(b) = (h^\star(a))(b) = (\lambda y. a - y)(b) = a - b$$

Which is the same result computed by $h(a,b) = a - b$.