Showing Optimal Substructure for Stacking Boxes DP Problem? I am having trouble wrapping my head around the Stacking Boxes dynamic programming problem, and understanding how it has optimal substructure and overlapping subproblems.  If it has the optimal substructure and overlapping subproblems, then I can use dynamic programming to solve the problem. How do I know that the stacking boxes exhibits the optimal substructure?

I have read that it is similar to the longest-increasing-subsequence problem which exhibits optimal substructure and overlapping subproblems, but I am unable to see how it relates to the stacking boxes problem.

When people talk about this notion of an optimal substructure, they're just saying that you can solve a bigger problem by looking at the best solutions to smaller (sub)problems and somehow transforming these solutions to these subproblems back into a solution of the bigger problem.

So let's look at a modified version of this box-stacking problem that is also used in G4G's solution. Let $\text{Stack-Boxes-No-Rotation}(\mathrm{B})$ be the problem of finding a maximum stack of boxes in $B$ such that we are not allowed to rotate any of the boxes. Later on, we'll relax this restriction of not being able to perform rotations.

Now, let's get to the meat and potato of this concept. First, let's break down the phrase. What is a substructure? Well, the prefix "sub" suggests that this is a smaller problem structure than the whole problem. However, it's still a bit hazy what we mean by smaller. Are we talking about the number of boxes in $B$ to stack? Are we talking about volume? The height?

Unfortunately, there's no singular prescription that you can follow to figure this out. You'll have to rely on your intuition, and there are usually multiple valid ways to compare two things. The intuition however always comes back to the idea that if you have the solutions to the smaller problems, then you should be able to easily use them to create a solution to the big problem.

It's pretty hard to get a good feel for this unless we work through an example. Here, I'll start off with a way of defining "smaller" subproblems that is different from the way that G4G is doing, but which may have been one of your first instincts. Let's say a problem is smaller than another problem if its height is smaller than the other.

First thing first, since we're defining comparisons in terms of height, we need to create a parameter for it. So let $\text{Stackable}(B, h)$ determine whether it's possible to stack boxes in $B$ to a height of $h$. We wish to find the largest $h$ such that $\text{Stackable}(B, h)$ is still possible.

Now, we've talked about using the height to determine which problem is smaller. We say that $\text{Stackable}(B', h') \preceq \text{Stackable}(B, h)$ if $h' \le h$ and $B' \subseteq h'$. Now, we haven't shown that $\text{Stackable}(B, h)$ has the optimal-substructure property with respect to the order $\prec$ yet. Before we do so, let's review what optimal-substructure claims if it applies to this problem.

  If we know $\text{Stackable}(B', h')$ for every subset of boxes $B' \subset B$ or every height $h' < h$ (that is, $(B', h') \prec (B, h)$, then we would be able to use that information to find out whether $\text{Stackable}(B, h)$ is possible.

Okay, so how do we do that?

Well, a good approach is usually to think backwards. If it's possible for a set of boxes in $B$ to stack to height $h$, then let's consider the last move that we could have made. It could be any of the boxes in $B$. Suppose that we've picked a box $b$ to use as the top of the stack, then what? Well, it better be the case that the stack under it uses only boxes from $B - \{b\}$ and has height $h - h(b)$. In addition, it better be the case that the box immediately under $b$ must have an area large enough to accommodate $b$.

If you think about it for a moment, figuring out whether the stack under $b$ has height $h - h(b)$ can be accomplished by knowing $\text{Stackable}(B - \{b\}, h - h(b))$ (which literally tells me if it's possible to stack boxes from $B - \{b\}$ to a height of $h - h(b)$). However, there's no way to ensure that the box immediately under $b$ has to have a large enough area! Therefore, just knowing the solutions to the subproblems is not enough (in this formulation of the problem) to piece together a solution for the bigger problem.

But what went wrong here? It turns out that to stack a box on top of another box, we also need to know the area of the box on the bottom. Now, you have a few choices that you can make here. The problem at hand is that we're not tracking enough information, so one solution is to track more information. The other is to formulate an altogether different problem-structure.

Let's go with the former. How do we amend our process to keep track of the area of the box on top of a stack? Well, we could just add them as parameters of $\text{Stackable}$. Now, we interpret $\text{Stackable}(B, h, w, l)$ as whether it is possible to stack boxes from $B$ to a height of $h$ such that the box on the top of this stack has area $w \times l$. How's that for a mouthful. In addition, we need to also consider whether we should amend our denotation $\preceq$ of whether one subproblem is smaller than the other. While it's tempting to say that $(B', h', w', l') \preceq (B, h, w, l) \iff B' \subseteq B, h' \le h, w' \ge w, l' \ge l$, as you'll see, it's also okay if we just keep the original $\preceq$.

Now, let's see what optimal substructure claims here: If I have the answer to whether it is possible to stack boxes to a height of $h'$ using subsets of boxes that I am given, such that the final box of that stack is some $w' \times l'$, then I should be able to use that information to figure out whether it is possible to stack boxes to my desired height $h$ such that the final box has size $w \times l$.

Fortunately for us, it is now possible to do this. Once again, let's think backwards and consider the final box that we wish to stack: $b$. Now, we know that $b$ has an area of $w \times l$, so in order to stack it, we need to make sure that the preceding stack of boxes in $B - \{b\}$ has height $h - h(b)$ and whose final area is at least $w' \times l'$ where $w' > w$ and $l' > l$. Well, fortunately for us, this is literally what $\text{Stackable}(B - \{b\}, h - h(b), w', l')$ (for each $w', l' > w, l$) answers. Therefore, we know that our subproblem candidate space is
$$
\text{candidates}(B, h, w, l) = \bigcup_{b = (h(b), w, l) \in B, \\ w' > w, l' > l} \text{Stackable}(B - \{b\}, h - h(b), w', l').
$$
Now, given these candidates, how do we find $\text{Stackable}(B, h, w, l)$? Well, it's simple; if any of the candidate subproblems are possible, then so is the bigger problem. Therefore, we just have
$$
\text{Stackable}(B, h, w, l) = \bigvee_{b = (h(b), w, l) \in B, \\ w' > w, l' > l} \text{Stackable}(B - \{b\}, h - h(b), w', l').
$$

Now, there are $2^{|B|} \times H \times W \times L$ possible ways to fill the parameters $(B, h, w, l)$, so that's definitely a horrible solution, since you might have to find the value of each of these possible arguments in order to find the best result. Don't worry; this actually happens quite a lot in practice. Not everyone finds an acceptable solution on their first try.

After one iteration of a possible Dynamic Programming formulation that you find lacking, you can think about alternative formulations of your problem structure. In my example, I used the formulation $\text{Stackable}(B, h, w, l)$ to structure the solution space. There, I interpreted the result of $\text{Stackable}(B, h, w, l)$ as whether it is possible to stack boxes in $B$ to a height of $h$ such that the final box has area $w \times l$. Now, is there a better formulation that I can make?

Well, in the spirit of gradually refining your process, it's quite obvious that in the formulation $\text{Stackable}(B, h, w, l)$, the final box must have an area of $w \times l$. However, it's probably the case that not that many boxes share the same area. Therefore, we can probably gain back some time if we just outright say what the last box is: $\text{Stackable}(B, h, b \in B)$. Now, our dynamic programming formula becomes
$$
\text{Stackable}(B, h, b \in B) = \bigvee_{b' \in B-\{b\}\\w(b') \ge w(b) \\ l(b') \ge l(b)} \text{Stackable}(B, h - h(b'), b')
$$
Still, we're potentially looking at $|B| 2^{|B|} H$ arguments here.

Unfortunately, this is the extent of what the stackability formulation can do for us. However, we can try other substructure formulations.

And this is where the idea of the G4G solution comes into place. Let's number each of the boxes in $B$, so that $B = b_1 \le b_2 \le \dots \le b_n$ (with respect to their area). Now, instead of looking at this problem in terms of whether it is possible to stack some boxes to some height, let's look at what the maximum height of the set of boxes $b_1, \dots, b_k$ can reach.

This then gives another sub-structure ordering. We say that a problem on $(b_1, \dots, b_k)$ is smaller ($\prec$) than another problem on $(b_1, \dots, b_{k'})$ if $k < k'$. Now, let's consider the formulation $\text{Tallest}(b_1, \dots, b_k)$, which gives you the tallest stack you can build using just the boxes in $\{b_1, \dots, b_k\}$. Can we show that it has an optimal substructure?

Unfortunately, it's not all rainbows and sunshine: we run into the same problem that we've had before. Suppose we're considering the last box on a stack, we have no way to ensure that the box preceding it can fit the final box, just that its total area is larger. Therefore, let's try our parameterization trick from before; let $\text{Tallest}(n, b_k)$ denote the tallest tower that we can build using just boxes in $(b_1, \dots, b_n)$, such that the final box is $b_k$.

Third time's a charm, right? To see that this formulation has an optimal substructure property, let's try to build the tallest stack using the first $n$ widest boxes that ends at some $b_k$. Well, if we have $\text{Tallest}(n-1, b_{k'})$ where $b_{k'}$ is both wider and lengthier than $b_k$, then we could build an even taller stack. The tallest stack we can build is then the maximum of these candidates:
$$
\text{Tallest}(n, b_k) = \max_{b_{k'} \sqsubset b_k} \left(\text{Tallest}(n - 1, b_{k'})\right)
$$
where $b_{k'} \sqsubset b_k$ if $k' < k$ and $w(b_{k'}) \ge w(b_k), l(b_{k'}) \ge l(b_k)$. Now, shrinking $n$ is valid, but the astute reader will also notice that
$$
\text{Tallest}(n, b_k) = \max_{b_{k'} \sqsubset b_k} \left(\text{Tallest}(n, b_{k'})\right)
$$
will work just as well. In fact, we no longer need to keep track of the range of boxes to consider, and we can simplify this formulation down to just
$$
\text{Tallest}(b_k) = \max_{b_{k'} \sqsubset b_k} ~ \text{Tallest}(b_{k'})
$$
which can be interpreted as the tallest stack that you can build if the final block is $b_k$. This then concludes the formulation that G4G constructed.

I want to sign off with a few pieces of advice. Dynamic Programming is a very intuition-driven technique for problem solving. It might seem daunting at first, but with enough experience, you'll eventually view it as an extremely powerful tool. Personally, I find that the approaches that works best for me are:

Don't worry about the implementation of the actual dynamic program, and instead focus on its interpretation. When you see $\text{Tallest}(b_k)$, don't worry too much about what its code should look like; rather, stick to the high level interpretation and just read it out as "the tallest stack ending at the box $b_k$". This way, it makes reasoning about the correctness of the approach much easier.
Try to work backwards if possible. Dynamic programming is essentially just structural induction. It might seem daunting to have to build up the recursion tree in your head, so don't. Instead, the "inversion" trick of looking at the final operation of your program and working backwards is much less mentally taxing. On top of that, working this way will quickly tell you if your "induction hypothesis", or your "optimal substructure" hypothesis, actually holds or not.
Dynamic Programming is about decisions. Whenever you formulate a dynamic programming problem, always ask yourself: what is it that I need to choose and decide at every point? In the case of $\text{Tallest}(b_k)$, for each $b_{k'} \sqsubset b_k$, you have to decide whether you will include that box in your stack or not. You can explore all of these possibilities simultaneously, but at the end of the day, you have to commit to a concrete event. Therefore, it's important to figure out what your options/candidate subproblems are and how you can either combine them or choose the best outcome.


Is there a model of ZF¬C where some program always terminates but has no loop variant? Wikipedia has a proof that every loop that terminates has a loop variant—a well-founded relation on the state space such that each iteration of the loop results in a state that is less than the previous iteration's state under the relation. Here, well-founded refers to the usual classical definition of a well-founded relation: every nonempty subset has a minimal element.

The proof given in the linked article is as follows:

Let the loop variant be the "iteration" relation, i.e. the reflexive transitive closure of the transition relation.
Since the loop always terminates, the loop variant has no infinite descending chains.
Apply the axiom of choice to conclude that the loop variant is well-founded.

My question is about step 3. Using the full, uncountable axiom of choice here feels like swatting a fly with an atom bomb. Elsewhere on Wikipedia, we have the following:

  Equivalently, assuming the axiom of dependent choice, a relation is well-founded if it contains no countable infinite descending chains: that is, there is no infinite sequence $x_0, x_1, x_2, \dots$ of elements of $X$ such that $x_{n+1}\ R\ x_n$ for every natural number $n$.

So the much weaker axiom of dependent choice is sufficient.

It seems like it might be possible to weaken this assumption further. The state space of a computer program is not an arbitrary set from the entire Von Neumann universe of ZF. Maybe countable choice suffices, since the state space of any program is countable?

On the other hand, if dependent choice is required and countable choice will not suffice, then (assuming ZF is consistent) there must exist a model of ZF + countable choice where there is some program that (a) always terminates, (b) has an iteration relation with no infinite descending chains, yet (c) has no well-founded loop variant. This seems deeply weird.

My question is:

Is there a model of ZF where a program always terminates but has no loop variant?
If the answer to 1 is yes, then what is the weakest choice principle that, when added to ZF, changes the answer to no?
If the answer to 1 is yes, is it possible to write down an explicit example of such a program (a la Harvey Friedman's explicit formulas equivalent to the strengths of ordinals), or does such a program necessarily correspond to a non-standard natural number?

I think you are really asking a question about the definition of the notion of well-foundedness.

I think the notion of loop variants is a bit of a red herring here: I would argue that any reasonable definition of well-foundedness should enable proving that a loop is terminating iff there is a well-founded relation which acts as a variant for it, almost as a tautology.

The issue is that the classical definition of a well-founded order $<$ on $X$:

  There are no infinite sequences $x_1>x_2>x_3>\ldots$

is not a very nice definition, either from a constructive standpoint or when one is uncomfortable with the use of the axiom of (dependent, thanks Andrej!) choice. Assuming the latter, this definition is equivalent to the much nicer definition:

  Every non-empty subset $P\subseteq X$ has a minimal element, that is, some $x\in P$ such that $y \not< x$ for every $y\in P$.

This definition is already much nicer, and I think it can be used to prove the variant lemma without choice.

Finally, the constructive version of well-foundedness is this:

  For every $P\subseteq X$, if for every $x\in X$, $\{\ y\ |\ y < x\ \}\subseteq P$ implies $x\in P$, then $P = X$.

This definition seems more unwieldy, but it is actually the one you want: it enables induction over well-founded orders, without using either choice or excluded middle. Assuming excluded middle, it is equivalent to the previous one.

Finally, the business in the wikipedia article about ordinals is not really necessary for any technical analysis of termination, and, in addition, choice is not required if you define $\omega_1$ to be the order type of the set of countable ordinals (ordered by the prefix relation).


Grammar with fewest variables I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints.

The Myhill-Nerode Theorem provides the minimum number of states of a DFA to recognize a regular language. Argue that an analogue for context-free languages is unlikely to be discovered.
Prove that the grammar with fewest variables equivalent to a grammar G is uncomputable.

Let $L \neq \emptyset$ be a language over some alphabet $\Sigma$, let $|$ be a symbol not in $\Sigma$, and consider the language $|L = \{ |w : w \in L \}$. Suppose that $L$ could be generated using a context-free grammar with a single nonterminal $S$.

Since $L \neq \emptyset$, $S \Rightarrow^* |w$ for some word $w$. Therefore:

Every rule contains at most one $S$ on the right-hand side. Indeed, otherwise you could generate a word with more than one $|$.
Every rule containing exactly one $S$ must be of the form $S \to Sw$, where $w \in \Sigma^*$. Indeed, the rule cannot contain $|$, since otherwise $S$ would generate a word with more than one $|$; and the rule cannot contain anything to the left of $S$ since then $S$ would generate a word not beginning in $|$.
Every rule not containing any $S$ must be of the form $S \to |w$, where $w \in \Sigma^*$ (in fact, $w \in L$).

Let $A$ be the collection of words $w \in \Sigma^*$ for which there is a rule $S \to |w$, and let $B$ be the collection of words $w \in \Sigma^*$ for which there is a rule $S \to Sw$. Thus
$$ L = |AB^*. $$
Conversely, it is easy to check that every language of this form (with $A,B$ finite) has a context-free grammar with a single nonterminal. Considering also the empty language, we have shown:

  The language $|L$ can be generated using a context-free grammar with a single nonterminal iff $L = AB^*$ for some finite (possibly empty) $A,B$.

The collection of languages of the form $AB^*$ is closed under quotient from the left, which is the following operation: $\sigma^{-1}S = \{ w : \sigma w \in S \}$. Indeed, if $\epsilon \notin A$ then $\sigma^{-1}(AB^*) = (\sigma^{-1}A)B^*$, and if $\epsilon \in A$ then $\sigma^{-1}(AB^*) = (\sigma^{-1}A)B^* \cup (\sigma^{-1}B)B^*$. Therefore, Greibach's theorem shows that determining whether a context-free grammar generates a language of the form $AB^*$ is undecidable.

Given a context-free grammar $G$, we easily construct a context-free grammar for $|L(G)$. The language of this context-free grammar can be generated by a single nonterminal iff $L(G)$ is of the form $AB^*$, and so the following problem is undecidable: Given a context-free grammar, determine whether its language can be generated by a context-free grammar with a single nonterminal.


Classes of outer totalistic cellular automata I'm wondering if anyone knows of any place where the Wolfram classifications of many outer totalistic cellular automata have been catalogued. The classes of a few examples are given in A New Kind of Science, famously that of Rule 224 (Life) or more simply ones like Rule 0 which kills all of the cells. I'm wondering if there's any place where these classes have been collected, for a research project. Thanks!

Here is a fairly old link, which only lists a few classes specifically, but it might be a place to start.

I'd agree with David Eppstein that a longer list might not be all that useful.  There's no quick way to tell for sure whether a given CA rule is Class 4, except in the really simple cases.  In many cases, with enough work you may be able to design persistent structures that could support universal computation.


Is binomial(n, k)=0 (mod n) when gcd(n, k)=1? When gcd(n, k)>1? I was programming the AKS primality test, and I have two questions.

Is it correct that if gcd(n, k)=1, then binomial(n, k)=0 (mod n)?

Is it correct that if gcd(n, k)>1, then binomial(n, k)>0 (mod n)?

All variables are understood to be positive integers. Let $n\mid m$ mean $n$ is a factor of $m$, a.k.a. $m$ is divisible by $n$ or $m=0\pmod n$.

  Is it correct that if $\gcd(n, k)=1$, then $n\mid\binom nk$?

Yes.

Since $k\binom nk=n\binom{n-1}{k-1}$, we know $k\binom nk$ is divisible by $n$. Since $\gcd(n,k)=1$,  we must have $\binom nk$ is divisible by $n$.

  Is it correct that if $\gcd(n, k)>1$, then $\binom nk>0\pmod n$?

The relation of "greater than" or "less than" modulo $n$ does not make sense since, for example, $-1=1=2019\pmod 2$.

What you have in mind should be the following question.

  Is it correct that if $\gcd(n, k)>1$, then $n\not\mid\binom nk$?

Not necessarily.

The smallest counterexample is $\gcd(10,4)=2\neq1$ but $10\mid\binom{10}4=210$. In fact, if $n=2\pmod8$, then $n\mid\binom n4$.

Kummer's theorem provides a way to compute the exponent of the highest power of a given prime number dividing a binomial coefficient. Peter Taylor points out that it can be used to determine whether $n\mid\binom nk$ in polynomial time if we know the prime factorisation of $k$ or $n$. However, no algorithm is known to be able to obtain the prime factorisation of an integer in polynomial-time.

Here is a related interesting article, divisibility properties of binomial coefficients by K. R. Mclean.

Exercise 1. Show that if $m\mid n$ and $\gcd(m,k)=1$, then  $m\mid\binom nk$.

Exercise 2. Show that $2i\mid\binom{2i}4$ iff $i=1\pmod4$.

Exercise 3. Find infinitely many pairs of $n$ and $k$ such that $1\lt k \mid n$ and $n\mid\binom nk$. (Hint, one such family can be found by setting $k=6$.)


Reducibility in Computability Theory In Sipser's book of Theory of Computation, related to Reducibility, it's written

  if A is undecidable and reducible to B, B is undecidable.

The confusion is, only a solution to B determines a solution to A, if i'm not wrong.
So, for instance if B is decidable and A is undecidable, what does it mean? Here B isn't undecidable.

Hope you got it.

Suppose $A$ is undecidable and reducible to $B$. Given an algorithm for $B$, you can use the reduction from $A$ to $B$ to get an algorithm for $A$, which we assumed is impossible. Therefore $B$ must be undecidable.

If $A$ is undecidable and reducible to $B$ and $B$ is decidable then we obtain a contradiction and everything goes. Pigs can fly.


How to interpret parametric formulation of information bottleneck? I'm reading this paper on latent representations with the information bottleneck https://arxiv.org/pdf/1804.06216.pdf and in section three, the authors write that the parametric formulation of the information bottleneck is
$\max\limits_{\phi,\theta} - I_\phi(t;x) + \lambda I_{\phi,\theta}(t;y).$
My question is not about the information bottleneck entirely, but how to understand the first term $\max\limits_{\phi,\theta}$ where $\phi$ and $\theta$ are parameters of a model. This notation doesn't make sense to me as I usually expect something to follow the $\max$. Does it just mean the largest value over all the parameters in the model?

The notation stands for the maximum value of $-I_{\phi}(t;x) + \lambda I_{\phi,\theta}(t;y)$, where the maximum is taken over $\phi,\theta$. The result will be a function of $t,\lambda,x,y$.
Often in such a notation, the possible values of the variables being maximized over is restricted, and sometimes this forms part of the notation (say, $\max_{0 \leq \phi,\theta \leq 1}$). In other times, the possible values are restricted, but this is not reflected in the notation, and should be gleaned from context.


Graphs with chromatic number $(\chi(G) \ge 3 )$ other than odd cycle (Triangle free) Chromatic number denoted by $\chi(G)$ of graph $G$ is the minimum number of colours required to properly colour the given graph.

For ODD Cycle chromatic number is 3 and it does not contain triangle as a subgraph. I thought about complete , star, wheel graphs etc, but they don't satisfy the conditions.

I am looking for examples of graphs of $\chi(G)$ $\ge 3$, but does not contain a triangle or odd cycle as subgraph.

If a graph contains no odd cycle then it is bipartite and so 2-colorable.


Using the pumping lemma to prove that a language is context-free I am new to automata theory.

Could you give me a little hand with the correct use of the pumping lemma?
I understand now how to proof a language is not context-free, but how do I use the pumping lemma to proof it is?

Do I find one way to break the word into: uvwxy so that v and x can be pumped? Is that enough and can I pick it in such a way that u or w or y are empty. I understand from the lemma that as long as v or x are not empty it is good. But can only w be empty and the rest be at least one character?

I did read on this topic, but I am just trying to make sure that what I understood is correct and there aren't other not so obvious things I should consider. Please help.

I read How to prove that a language is not context-free? and it has a very detailed example of a demonstration using the pumping lemma. But you are looking for some general understanding of the method so I will tell you the steps I follow when I use pumping lemma to prove that $L$ is not CFL:

1) You suppose that $L$ is CFL. The idea is find a contradiction using the pumping lemma.

2) By pumping lemma exists a constant $N>0$ associated to $L$. Use a generic constant because if you use a fixed one like $N=1$ for example, and don't find a contradiction you have to try with $N=2,3,4,...$.

3) You have to choose a word $\sigma \in L$ such that $|\sigma|\geq N$. You have to use your creativity to choose a word that allows you to easily reach a contradiction in the next steps.

4) By the pumping lemma exists a factorization of your word $\sigma=uvwxy$ and the
following always complies:
$$|vwx|\leq N$$
$$|vx|\geq 1$$
$$\sigma_i=uv^iwx^iy \in L \forall i\in\mathbb{N}_0$$

5) So the next step is to prove that the factorization does not exists. Your job if to check that all possible factorizations in the form $uvwxy$ don't complies with the 3 points of the pumping lemma. This generate a contradiction in your initial assumption then $L$ can't be CFL.

6) If you find a factorization of your particular word this mean nothing! Remember that the pumping lemma says:

If $L$ is CFL $\Rightarrow$ exist a factorization$\dots$

So you have two options at this point. The first is suspect that maybe your language is CFL and try to write a context-free grammar or draw a push-down automaton that denotes $L$. In second option you can assume that the word $\sigma$ was bad pick and try with another word to find a contradiction.

This is the general mechanics of the pumping lemma. I recommend you to try to understand the theory behind it or you will probably make mistakes in your test.

You can't use the pumping lemma to show that a language $L$ is context-free.. If you want to prove that $L$ is CFL the standard way is to write a CFG or draw a PDA like I said before.


Check grammar for LL(1)? If I have to check a Left Recursive grammer for LL(1)  then should I check it after removing left recursion?

For example:-
S-> (L)|a
L->L.S|S

If I check after removing Left Recursion then the above grammer is LL(1).
But if I do not remove left recursion then above grammer is not LL(1).
which one is the right answer?

If the question is, "Is this grammar LL(1)?", then the answer is "No".

If the question is, "Can this grammar be made LL(1)", then by all means remove the left-recursion.

The distinction is important because removing left-recursion does not preserve derivation order, so the left-recursion-eliminated grammar produces different parse trees. If it is being used to parse, it is not the same grammar.


What is parallel virtual machine (pvm) and how it's different from mpi (message passing interface) I am learning beowulf cluster. And I want to know what is pvm and how it's work and there is any difference between mpi and pvm

In fact, MPI and PVM are very different. However, they have the same objective, that is achieving data/message exchange between processors, thus enabling distributed/parallel computation.

MPI is the acronym for Message Passing Interface. It is a well-known message-passing standard, which defines the syntax and semantics of a core of library routines to exchange data between processors. Therefore, MPI is not a technology itself, but just the definitions of how to exchange data. However, MPI implementations exist in several programming languages (e.g., C, C++, FORTRAN, Python, and R), and those implementations are usually refereed simple as MPI. This fact may cause confusion since both the technology and the standards definition have the same name.

On the other hand, PVM is a free software (released under both the BSD License and the GNU General Public License) which enables data exchange between processors, in the same way as the MPI implementations. PVM consists of a run-time environment and library for message-passing, task and resource management, and fault notification.

You may have a look at some studies that compare both MPI and PVM. Please, see the links below.

http://wwwmayr.informatik.tu-muenchen.de/konferenzen/Jass04/courses/2/Papers/Comparison.pdf

https://www.researchgate.net/profile/James_Kohl2/publication/2612922_PVM_and_MPI_A_comparison_of_features/links/0c960528b9401cec40000000/PVM-and-MPI-A-comparison-of-features.pdf

http://wwwmayr.informatik.tu-muenchen.de/konferenzen/Jass04/courses/2/Talks/Elts.ppt


Maximun distance that can be reached A stone is located at the point (0,0) of an infinite grid. The stone has exactly $n$ possible moves, not necessarily unique, each described by a $vector$ of integer coordinates. The stone can make  each move at most once , and the moves it makes may be arranged in any order.The goal is to reach a point as far (in the Euclidean distance) from the initial position as possible. How far can the stone be reached ? $($ Given that output is square of max distance $)$

Example :
 consider $ n$ $=$ $4$ and vectrs are

$[$2,-2 $]$ ,[-2,-2],[0,2],[3,1],[-3,1]

Ans is $26$
Optimal way is to use  vectors [0,2], [3,1], and [2,−2].or also [0,2], [−3,1], and [−2,−2].

link for vector clarity is https://ibb.co/mJByc99

Addition of vectors is commutative, so the order of moves is irrelevant. For example:

$(0,2) + (3,1) + (2,-2) = (0,2) + (2,-2) + (3,1) = (3,1) + (0,2) + (2,-2) = (5,1)$

So a simple brute force method is to calculate the distance traveled for all subsets of the set of $n$ possible moves. There are $2^n$ such subsets, but you don't need to consider the empty set. So the size of your search space is actually $2^n-1$.


Can finding a witness be NP-hard even if we already know there is one? The common examples of NP-hard problems (clique, 3-SAT, vertex cover, etc.) are of the type where we don't know whether the answer is "yes" or "no" beforehand.

Suppose that we have a problem in which the we know the answer is yes, furthermore we can verify a witness in polynomial time.

Can we then always find a witness in polynomial time?  Or can this "search problem" be NP-hard?

TFNP is the class of multivalued functions with values that are polynomially verified and guaranteed to exist.

There exists a problem in TFNP that is FNP-complete if and only if NP = co-NP, see Theorem 2.1 in:

Nimrod Megiddo and Christos H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 2 (April 1991), 317-324. DOI: 10.1016/0304-3975(91)90200-L

and the references [6] and [11] within. PDF available here.


Partial order, total order, and version order in transaction histories In Section 3.1.2 "Transaction Histories" of the PhD thesis by Atul Adya [1]:

  A history $H$ over a set of transactions consists of two parts: (1) a partial order of events $E$ that reflects the operations (e.g., read, write, abort, commit) of those transactions, and (2) a version order, $\ll$, that is a total order on committed object versions.

The author gives a comment on "the partial order of events" (Page 36):

"For convenience, we will present history events in our examples as a total order that is consistent with the partial order. Furthermore, wherever possible in our examples, we make this total order be consistent with the real-time ordering of events in a database system."

  Question 1: Why can we present the partial order of events as a total order of them? Because a partial order may imply multiple total orders consistent with it, which one to choose? Does the choice matter for later definitions and theorems?

Some comments on "the total version order" (Page 36) are as follows:

[Added (01-10-2015)] "The version order in a history $H$ can be different from the order of write or commit events in $H$. This flexibility is needed to allow certain optimistic and multi-version implementations where it is possible that a version $x_i$ is placed before version $x_j$ in the version order even though $x_i$ is installed in the committed state after $x_j$ is installed."

And,

"The system chooses the version order for each object."

  Question 2: What does it mean for the database system to choose the version order? And how? Is this implementation-dependent?

[1] Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions by Atul Adya, 1999

for what it concerns Question 1:

there is a theoretical result from 1930 [1] that states that

any partial order $S$ can be extended to a total order $S'$ which contains $S$.

This result is known as the "Order Extension Principle"; the proof of this result
uses the Axiom of Choice (I am not aware whether there is an alternative proof that does not use it). The paper is written in French, but you can find a proof at
https://www.proofwiki.org/wiki/Order-Extension_Principle.

When Adya states that he chooses the real-time order of events, the best guess
is that he assumes an implementation of the database; in this case, every history $H$
corresponds to an execution of the database, where events are totally ordered; such an order is the real-time order.
More specifically, by requiring that the partial order $<$ in a history $H$ is extended by the real-time (total) order, Adya imposes that whenever $e_1  < e_2$ in $H$, then the instant of time $t_1$ at which the event $e_1$ takes place (in the execution of the database that leads to $H$) is less than the instant of time $t_2$ at which $e_2$ takes place.
Choosing the real-time order of events to extend the partial order of a history $H$ is needed if one wants to prove the correctness of an abstract specification (i.e. set of properties that a history has to satisfy) with respect to a given specification.

Let's turn to Question 2:

in this case it seems to me that Adya wants to stress the fact that he allows the implementation of a database to access a version of an object which precedes (in the version order) the latest version installed. In practice, choosing an earlier version of an object could be either the result of the database not being able to access such a version (e.g. the lost update anomaly in causal consistency), or the user explicitly requesting to access an older version of an object (e.g. accessing an older version of a revision in a SVN repository).

Hope this helps,
Andrea Cerone.

[1] Edward Szpilrajn - sur l'extension de l'ordre partiel


Distance Vector Routing Example Consider a network with five nodes, N1 to N5, as shown as below.

The network uses a Distance Vector Routing protocol. Once the routes have been stabilized, the distance vectors at different nodes are as follows.

N1: (0,1,7,8,4)

N2: (1,0,6,7,3)

N3: (7,6,0,2,6)

N4: (8,7,2,0,4)

N5: (4,3,6,4,0)

Each distance vector is the distance of the best known path at that instance to nodes, N1toN5, where the distance to itself is 0. Also, all links are symmetric and the cost is identical in both directions. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors.

It's a GATE-2011 question.

I have a doubt here.

Suppose when the cost of the link N2-N3 changes to 2, this will be immediately known to N2 and N3 and they will update their routing table entry to reflect this change. Now, this would cause triggered update.

Suppose After receiving the vector from N2, N3 finally changes it's vector to (3,2,0,2,5).

Now my query is whether this vector (3,2,0,2,5) would be communicated to N4 or the old vector of N3(7,6,0,2,6) would be communicated to N4?

Let us review the specification of the algorithm.

  In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors.

Right after the cost of link N2-N3 changes to 2, the distance vectors at different nodes are as follows. The only difference from before is the distance from N2 to N3 and the distance from N3 to N2 has been updated from 6 to 2.

N1: (0,1,7,8,4)
N2: (1,0,2,7,3)
N3: (7,2,0,2,6)
N4: (8,7,2,0,4)
N5: (4,3,6,4,0)

In the next round of exchange, all nodes exchange their distance vectors with their respective neighbors. In particular, N3 sends (7,2,0,2,6) to its neighbor N2 and N4. Right after this round of exchange, the knowledge of each node are as follows besides their knowledge of respective distances to their neighbors.

N1 knows (1,0,2,7,3) from N2.
N2 knows (0,1,7,8,4) from N1 and (7,2,0,2,6) from N3 and (4,3,6,4,0) from N5.
N3 knows (1,0,2,7,3) from N2 and (8,7,2,0,4) from N4.
N4 knows (7,2,0,2,6) from N3 and (4,3,6,4,0) from N5.
N5 knows (1,0,2,7,3) from N2 and (8,7,2,0,4) from N4.

Discarding current distance vectors, all nodes regenerate their distance vectors at the same time. So after, for example, a fraction of a second, the distance vectors at different nodes becomes the following.

N1: (0,1,3,8,4)
N2: (1,0,2,4,3)
N3: (3,2,0,2,5)
N4: (8,4,2,0,4)
N5: (4,3,5,4,0)

If no change of the network happens before the next round of exchange, then in the next round of exchange, each node will send above distance vectors to its neighbors. In particular, N3 will send (3,2,0,2,5) to its neighbor N2 and N4 in the next round.

However, if before the next round of exchange, it happens that the link between N1 and N2 goes down. Then N1 and N2 will update their distance vector immediately, but only with the distance between N1 and N2. Now the distance vectors at each node are as follows.

N1: (0,infinity,3,8,4)
N2: (infinity,0,2,4,3)
N3: (3,2,0,2,5)
N4: (8,4,2,0,4)
N5: (4,3,5,4,0)

After the next round of exchange, N3 knows the distance vector (infinity,0,2,4,3) from N2 and (8,4,2,0,4) from N4. So N3 will update its distance vector to (10,2,0,2,5).


What precisely/concisely is the "head" of a singly linked list? I ask bc of ambiguity online So I have a pic which I think illustrates my confusion:

the read surrounds what I wonder is the head? Does head refer to a node with both a data and next, or only a node with next? In other words, which marked box does it refer to in my pic?

You're right, there are many different definitions of a List/Linked List. No one definition is correct nor incorrect. This answer is a bit long-winded, but having a backstory on the logic behind lists is worthwhile.

History of Lists

Let's start with the definition of a List, in Computer Science, as described by the developers of the structure (Newell, Shaw, and Simon [1]) for their Information Processing Language [1] in 1957. It was initially developed as a method for flexible memory assignment in the Logic Theory Machine.

Definition of Lists (1957)

  $Lists$ : Lists are the general units of information in the memory. A list consists of an ordered set of items of information. Any item on a list may be either a list or an element, and these are fundamentally different types of unit. [1]

Formation of Lists

  To form a list, we use a set of location words, each containing two addresses. One address locates an item on the list, the other address locates the next location word. [1]

Location words are JOHHNIAC [2][3] words that contain two addresses.

  The left address is the address of the next location word, the right address is the address of the item on the list. [1]

Here is an example of a List containing three elements:

[1]

You can see in this example, the items link to nothing. This is why items are "on the list", they are attached to the list but not a direct piece of the list. Saying the first element is the "head" of a list makes no sense in this context. They are not part of the list at all.

The Head of a List

Newell and Shaw describe the head of a list as the first location word in the list [1]. Thus, in a strict sense, the head has an address to the first element on the list, while itself is the first location word in the list.

This representation of a list was traditionally followed. This can even be seen in the LISP [4] programming language invented by John McCarthy. Also check the LISP 1.5 Programmer's Manual [5].

Definition of Lists (1964)

Soon came along the idea of putting "symbols" in the list, rather than attaching them on the list. Wilkes [6] describes the registers (nodes) of a list as having two parts (similar to Newell, Shall, and McCarthy) in his paper Lists and why they are useful [6]:

The CAR, left free, and may be used to hold a symbol. Alternatively, can store an address memory.
[6]
The CDR (pronounced "cudder") contains an address pointing to the next register in the list.
[6]

Here is a simple example of a list under Wilkes' definition, with symbols in the list:

[6]

Head of a List

  A list must start somewhere, and the address of its first register is stored in a sequence of fixed memory registers known as base registers. [6] Normally, it is not necessary to show the base registers in diagrams of lists. [6]

With Base registers [6]:

Typical representation without base registers [6]:

In this definition, the head of a list is more in line with your first picture, it is an external register, not part of the list itself that merely contains the address to the first register in the list.

You may be wondering why I chose these examples instead of giving you the simple wiki definition [7]:

  The head of a list is its first node.

This definition is left ambiguous most likely intentionally because there are many different implementations. We can now discuss the head in regards to the two examples I presented.

The Sentinel Node (wiki [8])

Of these two examples, the latter is a list using a sentinel node (the base registers), the former does not. When using a sentinel, the head is the sentinel, the first node in the list, even though the sentinel contains no elements or addresses to elements. Clearly without a sentinel, the head is simply the first node in the list.

Internal vs External Storage (wiki [9])

Of these two examples, the latter is an example of internal storage, the former is an example if external storage. With internal storage you could attempt to think of the head as the first element in the list (though I wouldn't recommend it, because it contains also the address of the next node), because the element is in the node. With external storage, the head contains a pointer (memory address) to the first element of the list and a pointer to the next node in the list.

Nodes vs Elements

Much of the confusion about lists comes from the fact that many people mix up an element of a list with a node of a list. To prevent any confusion, whether you're using internal/external storage or a sentinel node or not, in my opinion, it's best not to refer to the elements (data stored in the list) as nodes of the list. Conceptually they are distinct.

The node of a list should thus contain two parts (as previously mentioned), the element or address, and an address to the next node. In programming, even if the two are not separated in code, conceptually they should be. Therefore when Wikipedia refers to the head of a list, it refers to the first node in the list. That node, then contains element data and an address to the next node.

Programming the logic theory machine by A. Newell and J. C. Shaw (1957, pp. 233)
The History of the JOHNNIAC by F. J. Gruenberger (1968) (available here for free, no sign-in required)
Johniac by E. Thelen (accessed Oct 29, 2017, last updated Aug 6, 2015)
LISP I Programmer's Manual by J. McCarthy et al. (1960)
LISP 1.5 Programmer's Manual by J. McCarthy et al. (1962, 2nd ed)
Lists and why they are useful by M. V. Wilkes (1964, pp. 1-5)
https://en.wikipedia.org/wiki/Linked_list#Basic_concepts_and_nomenclature (accessed Oct 29, 2017)
https://en.wikipedia.org/wiki/Linked_list#Using_sentinel_nodes (accessed Oct 29, 2017)
https://en.wikipedia.org/wiki/Linked_list#Internal_and_external_storage (accessed Oct 29, 2017)


Context-free grammar for $ \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, l \geq \min(n,m)\}$ I know that $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, (l ≥ n) ∨ (l ≥ m)\}$ is a context-free language, because I know the context-free grammar, i.e.
$$
S \rightarrow AbZ \mid XBc \\
A \rightarrow aAb \mid X \\
B \rightarrow aBc \mid Y \\
X \rightarrow aX \mid a \\
Y \rightarrow bY \mid b \\
Z \rightarrow cZ \mid c
$$
I have a bit of difficulties understanding this construction. Can you explain step-by-step how it has been created? The rules?

Let us start by noticing that $X \to a^+$, $Y \to b^+$, $Z \to c^+$. Furthermore, $A \to a^n X b^n$ and $B \to a^m Y c^m$. Therefore $S$ generates words of the following two forms:
$$
a^na^+b^nbc^+ \\
a^+a^mb^+c^mc
$$
You take it from here.


clarification on multiple access in data link layer In physical layer, we already have methods to share a common link by dividing into channels using FDM etc.

Then why do we need to think about multiple access at data link layer? I.e why csma, csma/cd are needed? We shouldn't be seeing any collision at all when I'm using a different channel for communication right?
Do these protocols come into play only when i'm using a less bandwidth link due to which I can't share them by dividing into frequency bands  at all?

If each communication is on a separate channel, you need to figure out what channels are free before you start communicating. How do you propose to do that? If you try to ask somebody, that requires communication, so how do you find out which channels are free for that communication? If you try to just listen to what comes past and figure out which channels are free at the moment, how do you know that a channel that's quiet at the moment is really free, and it's not just that its users have paused for a moment. What do you do if somebody else also starts transmitting on that channel at the same time as you?

Alternatively, you need to preallocate $\tfrac12n(n-1)$ channels to your $n$ hosts, so that each pair of hosts has a specific channel to talk on. But that doesn't scale.


Solving T(n) = 2T(n/2) + log n with the recurrence tree method I was solving recurrence relations. The first recurrence relation was

  $T(n)=2T(n/2)+n$

The solution of this one can be found by Master Theorem or the recurrence tree method. The recurrence tree would be something like this:

The solution would be:

$T(n)=\underbrace{n+n+n+...+n}_{\log_2{n}=k \text{ times}}=\Theta(n \log{n})$

Next I faced following problem:

  $T(n)=2T(n/2)+\log{n}$

My book shows that by the master theorem or even by some substitution approach, this recurrence has the solution $\Theta(n)$. It has same structure as above tree with the only difference that at each call it performs $\log{n}$ work. However I am not able to use same above approach to this problem.

The non-recursive term of the recurrence relation is the work to merge solutions of subproblems. The level $k$ of your (binary) recurrence tree contains $2^k$ subproblems with size $\frac {n}{2^k}$, so you need at first to find the total work on the level $k$ and then to summarize this work over all the tree levels.

For example, if the work is constant $C$, then the total work on the level $k$ will be $2^k \cdot C$, and the total time $T(n)$ will be given by the following sum:

$$T(n) = \sum_{k=1}^{\log_2{n}}2^k C = C(2^{\log_2{n}+1}-2) = \Theta(n)$$

However, if the work logarithmically grows with the problem size you'll need to accurately compute the solution. The series would be like the following:

$$T(n)=\log_2{n}+\underbrace{2\log_2(\frac {n} {2})+4\log_2(\frac {n} {4})+8\log_2(\frac {n} {8}) + ....}_{\log_2{n} \text{ times}}$$

It'll be a quite complex sum:

$$T(n)=\log_2{n}+\sum_{k=1}^{\log_2{n}}2^k \log_2(\frac {n} {2^k})$$

I'll temporarily denote $m=\log_2{n}$ and simplify the summation above:

$$\sum_{k=1}^{m}2^k \log_2(\frac {n} {2^k})=\\=\sum_{k=1}^{m}2^k(\log_2{n}-k)=\\=\log_2{n}\sum_{k=1}^{m}2^k-\sum_{k=1}^{m}k2^k=\\=\log_2{n}(2^{m+1}-2)-(m2^{m+1}-2^{m+1}+2)$$

Here I used a formula for the $\sum_{k=1}^{m}k2^k$ sum from the Wolfram|Alpha online symbolic algebra calculator. Then we need to replace $m$ back by $\log_2{n}$:

$$T(n)=\log_2{n}+2n\log_2{n}-2\log_2{n}-2n\log_2{n}+2n-2$$
$$=2n-\log_2{n}-2=\Theta(n)$$

Q.E.D.


When are you supposed to eta-reduce? Wikipedia lists the following algorithm for normalizing a lambda calculus term $t$:

If $t$ is not in head normal form, beta reduce the beta redex in the head position to get $t'$. Then normalize $t'$ to get $t''$. $t''$ is the normal form of $t$.
If $t$ is in head normal form, normalize each of its subterms to get $t'$. $t'$ is the normal form of $t$.

The implied base case is if $t$ is in head normal form but has no subterms, in which case it is in normal form already. If $t$ has a normal form, the above algorithm is guaranteed to find it.

The problem I'm having is that it does not seem that the algorithm ever eta-reduces.

For example given the algorithm normalizes $\lambda y.\lambda x.y x$ to itself (since it is already in head normal form, and $x$ is also in head normal form). It should normalize to $\lambda y. y$ though.

It seems apparent that you need to add eta-reduction steps at some point. The problem is I'm not sure where to put them and preserve the property that the algorithm is guaranteed to find the normal form.

When and where do you eta-reduce to achieve this?

$\eta$ conversion is not a mean to reduce a term to $\beta$-normal form, but a tool to show equivalence regarding the (future) application; to express that 2 terms “are the same function”; that they will reduce to the same term when applied to arbitrary term(s).

If you want to also do $\eta$ conversions, you can do it anytime because you still have the same term (application-wise) after performing it. Having $\eta$ conversion in the theory will not enrich nor deplete the theory regarding existence of $\beta$($\eta$)-normal forms.


In Disjoint Sets, why do we make the smaller tree the subtree of the larger one? Currently I'm learning about the Disjoint Sets data structure. I understand that, when we create a union of two disjoint sets, we create a kind of "backwards" tree for fast lookup. As Skiena says in his book:

  To minimize the tree height, it is better to make the smaller tree the subtree of the bigger one. Why? The height of all the nodes in the root subtree stay the same, while the height of the nodes merged into this tree all increase by one. Thus, merging in the smaller tree leaves the height unchanged on the larger set of vertices.

I don't get this part, the description is not clear to me. Could someone clarify why we need to make this distinction?

Probably best explained with pictures. Say we have these two sets $A$ of height 2 and $B$ of height 3:

Now we have a choice when joining them:

Attach root of $B$ to root of $A$.
Attach root of $A$ to root of $B$.

Remember we are optimizing for look-up / $find()$. Let's see what happens in either case.

Attach root of $B$ to root of $A$.

We end up with this resulting set of height 4:

Attach root of $A$ to root of $B$.

We end up with this resulting set of height 3!

Wonderful! We've increased the size of the set without increasing the height. In this scenario our find will take at most 3 iterations, same as what we originally had because $B$ was of height 3 to begin with. In the other scenario we have at most 4 iterations because we've increased the height of the new set by 1. This is why it is always preferable to join the shorter tree to the taller one, because it will not increase the height of the taller tree (unless they are the same height). Thus, optimizing for look-up.


3-COL with a restriction on a number of vertices colored with a particular color If I modify a 3-COL problem (with colors A, B, C) in a way that I now demand that at most, say, 50 vertices may be colored with color A, does the problem still remain NP-complete?

I've been thinking of a reduction from a standard 3-COL, but there is no way that I can solve a standard 3-colorability using the problem described above; I'd have to cut the graph into smaller pieces. Other NP-complete problems I know of, like independence set, have a parameter and in my problem there is a fixed number instead of a parameter. So this got me thinking, that maybe such a problem could be solved in P-time, but this doesn't make sense as I could probably replace 50 with any other number.

So this is simpler than asking whether there is a 3-COL such that at most k vertices receive color A, but still quite hard in general I think.

Am I correct?

For a fixed parameter like 50, the problem can be solved in "polynomial time": guess which vertices to color A, then solving a 2-coloring problem for the remaining vertices.  The running time will be something like $O(|V|^{52})$, since there are $O(|V|^{50})$ ways to choose a set of at most 50 vertices; and 2-coloring can be solved in $O(|V|+|E|)=O(|V|^2)$ time.

Of course, this solution is solely of theoretical interest.  An algorithm whose running time is $O(|V|^{52})$ is technically polynomial-time, but it's completely and totally infeasible in practice for any interesting graph.

In contrast, if the parameter 50 is part of the input, then the problem remains NP-hard (consider what happens when you pass in $|V|$ as the value of this input; then you have the standard 3-COL problem).  This highlights the difference between a value that is fixed vs is an input to the problem.

Perhaps a simpler example to illustrate that difference is vertex cover: vertex cover is NP-complete, but if I ask you whether there exists a vertex cover of size $\le 50$, that can be done in polynomial time, for similar reasons -- the running time will be $O(|V|^{50})$ or so.  In particular, if you want to know whether there exists a vertex cover of size $\le k$, that can be done in $O(|V|^k)$ time.  When $k$ is a fixed constant, this is polynomial time; but when $k$ is part of the input, then this is exponential time (it is $\ge 2^k$).


Is there a formal CS definition of VCS and file versions? I don't know whether it was a joke, but once I read what was referred to as a formal definition of a file in a versioning system such as git, hg or svn. It was something like a mathematical object like a homeomorphism. Was that a joke or is there really computer science theory about versioning systems and the mathematics of VCS?

You're thinking of a tweet by Isaac Wolkerstorfer (@agnoster):

git gets easier once you get the basic idea that branches are homeomorphic endofunctors mapping submanifolds of a Hilbert space.

Unfortunately, it's a joke. As the author wrote on Quora:

It was intended as firmly tongue-in-cheek. I actually love git, and I think its complexity is greatly overblown. At the same time, I'm sympathetic to the fact that advice from git gurus to novices can end up sounding like inscrutable gibberish.
It's not intended to have any deeper meaning. Attempts to analyze it in this fashion should be futile, but due to a bug in reality, you can actually make any sufficiently hand-wavy statement fit if you try hard enough.

This has been discussed on Programmers Stack Exchange and on Mathematics Stack Exchange.

Joke aside, there has been work of formalizing version control. One effort that allies theory and practice is the work on patch theory by David Roundy on Darcs. The main objective of the theory is to model merging and, in particular, conflict resolution. The Darcs wiki has an introduction to the theory and a few pointers as well as a bibliography (unmaintained so outdated if you want a recent view on the subject, but it does list a 2009 survey paper by Petr Baudiš) and a list of talks (which includes more recent material). There's also a wikibook. One seminal paper is A Principled Approach to Version Control by Andres Löh, Wouter Swierstra and Daan Leijen3.
Patch theory does lead to a categorical model, which has been more recently explored in A Categorical Theory of Patches by Samuel Mimram and Cinzia Di Giusto and Homotopical Patch Theory by Carlo Angiuli, Ed Morehouse, Daniel R. Licata and Robert Harper. In Mimram and Di Giusto's work, the model has files as objects and patches as morphisms. I think that makes merging a branch a functor — an endofunctor if you're working in a single repository. “Homeomorphic endofunctor” doesn't make sense to me. With homotopy theory involved, submanifolds of a Hilbert space might not be so far out...


How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem? Can somebody help me with this recurrence please?
$T(n)=4T(\sqrt{n}/3)+(\log n)^2$

The division by 3 makes the task a little non-trivial, but you can still figure out how to proceed in the manner proposed by the answer suggested by Nathaniel in the comments.
Let $n = 3^{2^k-2}$ and you can modify the recurrence equation as
$$T(n) = 4T\left(\frac{\sqrt{n}}{3}\right) + (\log_3{2})^2.(\log_3n)^2$$
However, this modification will only bring a change of constant in your final solution. So we can safely assume that the original equation had the base of the logarithm as 3.
You have that $k = \log_2(\log_3n+2)$, and you can substitute this at the end to find your answer.


Method to change value in a key for a min heap How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with value oldKey, and no existing entry with key newKey, it will change it to newKey, keeping the the heap properties and returning true. If there is no key in the heap with value oldKey, or an existing entry has value newKey, then it will take no action and return false. Also an auxiliary  map is used to store the locations of the keys in an array. I know how to write methods for insertion but haven't seen any implementations of this.

Find the key's node
Change the node's key to the new key
Heapify the node

This will work in $O(log(n))$ worst case.

If the old key is the new key the node wont move. You can also explicitly check it before searching for the node, if you prefer.


Question about Morris' algorithm I am reading the lecture notes. I am trying to understand Morris' algorithm on page 2. The Morris' algorithm is as follows.

Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$.

Initial: $X=0$
For each item in the stream, increment $X$ with probability $\frac{1}{2^X}$.
Output: $2^X-1$.

It is said that $\mathbb{E}[2^X-1]=m$, where $X_m$ is the value of $X$ after seeing $m$ items.

How to show that $\mathbb{E}[2^X-1]=m$? Any help would be greatly appreciated.

Let us denote by $X_n$ the value of $X$ after reading $n$ elements, and let $Y_n = 2^{X_n}$. We have $Y_0 = 1$ and $Y_{n+1}$ equals $2Y_n$ with probability $1/Y_n$, and $Y_n$ otherwise. Therefore
$$
\mathbb{E}[Y_{n+1}|Y_n] = Y_n + \frac{Y_n}{Y_n} = Y_n + 1,
$$
which together with $Y_0 = 1$ implies that $\mathbb{E}[Y_n] = n + 1$.

More generally, we can estimate all moments of $Y_n$ in this way. We have
$$
\mathbb{E}[Y_{n+1}^k|Y_n^k] = Y_n^k + \frac{(2^k-1)Y_n^k}{Y_n} = Y_n^k + (2^k-1) Y_n^{k-1},
$$
and so $Y_0^k = 1$ implies that
$$
\mathbb{E}[Y_n^k] = 1 + (2^k-1) \sum_{m=0}^{n-1} \mathbb{E}[Y_n^{k-1}].
$$
As an example,
$$
\mathbb{E}[Y_n^2] = 1 + 3 \sum_{m=0}^{n-1} (m+1) = 1 + 3 \frac{n(n+1)}{2}.
$$
Therefore the variance of the estimator $Y_n-1$ is
$$
\mathbb{V}[Y_n-1] = \mathbb{V}[Y_n] = \mathbb{E}[Y_n^2] - \mathbb{E}[Y_n]^2 = 1 + 3 \frac{n(n+1)}{2} - (n+1)^2 = \frac{n(n-1)}{2}.
$$
More generally, induction shows that $\mathbb{E}[Y_n^k] = \Theta(n^k)$, and with some effort we can even calculate the leading constant:
$$
\mathbb{E}[Y_n^k] = \prod_{\ell=1}^k \frac{2^\ell-1}{\ell} n^k + O(n^{k-1}).
$$
In particular, if we denote $Z_n = (Y_n-1)/n$ then $Z_n \to Z$, where
$$
\mathbb{E}[Z^k] = \prod_{\ell=1}^k \frac{2^\ell-1}{\ell}.
$$
For more on $Z$, see Theorem 7 in Ph. Robert, On the asymptotic behavior of some algorithms.


Running time correct with Omega? I have the following statement. I would say it's correct as it's either equal or higher than $\Omega(\log^{10}(n))$.

Because:
I know $\log(2^n) = n$.
By that I would guess the same goes for $\log(n^{10})$ unimportant if the number is higher or not. By that it should be n. With this knowledge we already know it's higher than our $\Omega(\log^{10}(n))$.

We also know $\log(n)^2 = \log(n)$ again it will be higher or equal to our omega.

Is this correct?

$$(3 \log^2 n + 55 \log(n^{10}) + 8 \log n) \cdot \log n = \Omega(\log^{10} n)$$

Don't guess, but look at the definition which tells you that in order for $f(n) = \Omega(g(n))$ to hold, it must be the case that $\lim_{n \to \infty} f(n)/g(n) > 0$.

If I plug in $f(n)$ and $g(n)$ according to your description, I think I will get $\lim_{n \to \infty} f(n)/g(n) = 0$. You should check whether I made a mistake and draw the appropriate conclusions.


Is it true that P is not equal to deterministic linear space complexity class? I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class?

Is there some proof? Or should I find some algorithm which is not in P but it is in polynomial time complexity class or opposite way?

Do you know about some?

We do know that $\mathsf{P} \neq \mathsf{DSPACE}(n)$. This is proved in answers to a question on Mathoverflow. The idea is that $\mathsf{P}$ is closed under polynomial blowup while $\mathsf{DSPACE}(n)$ isn't (due to the space hierarchy theorem); consult the link on Mathoverflow for the details.


How does the computer know whether an address contains an instruction to be executed, or data to be used in an instruction? The question is already stated in the title.

A full answer to this question depends on the underlying computer architecture, as well as on layers of protection that the operating system may add on top of the basic architecture.

In the Harvard architecture instructions and read/write data are held in physically separate memory stores accessed by separate data pathways (buses). It is physically impossible to load a value from the data memory into the instruction register and it is physically impossible for a program to modify its own instructions. Values in the instruction memory may be copied into data registers and then treated as data, but the processor will know this from context e.g. when it sees an opcode "load the next word into Register A", the processor will assume the value in the next address in the instruction memory is a data value to be copied into Register A.

In the more flexible von Neumann architecture (which is adopted by most modern computers) instructions and data are held in the same memory and the processor does not see any difference between them. The processor assumes that whatever memory address its program counter points to at the start of an instruction cycle holds an instruction, and it will load that value into its instruction register and will try to execute it as if it were an instruction.

The danger with the von Neumann architecture is that the processor may treat data that was not intended to be executed as instructions, with unpredictable results. Or it may treat its own instructions as data and change them - this is known as self-modifying code, and is usually avoided because it is difficult to understand, test and maintain.

The solution to this danger is to re-introduce a distinction between data and instructions into the von Neumann architecture by using a no-execute bit, which can be implemented at a hardware level or in the operating system software.


Embedding a general planar graph into a grid I have here a little problem with my homework, and would appreciate some direction.

I am attempting for some time now to show that every planar graph is embeddable into a grid (As large as needs be).

I tried to make this argument inductively in many ways, but I am afraid that I don't see any good way to do that so far. My main problem is that while the subgraph may be embeddable in a grid, it might not still be possible to connect the relevant nodes to the nodes added in the inductive stage after the reorganization.

While writing this down, I thought of another possible solution which might solve it - observing the embedding to the plain as an embedding in the Cartesian plane, and moving every node to a "very close" point whose both coordinates are rational. Taking the greatest common denominator of all the coordinates, I believe that I'll find myself in a (huge) grid as required.

There is a really neat result which answer's this question: Schnyder's Theorem. Another nice result is that of de Fraysseix, Pach and Pollack.

Here is a reference for both algorithms. The "Realizer Method" corresponds to Schnyder's Theorem and "Canonical Orderings" corresponds to de Fraysseix et al.'s approach.

These algorithms can embed any planar triangulation in an $O(n)\times O(n)$ grid. You can embed a planar graph $G$ by adding edges until you obtain a maximal planar graph $T$. Then you run any of these algorithms with input $T$. The output will be a drawing of $T$ in an $O(n)\times O(n)$ grid, which is also a drawing of $G$ in that same grid.


Perturbation of a vector Given a vector $x=(x_1,\cdots,x_n)$ such that $0\leq x_i \leq1$ and $\sum_{i=1}^n x_i=1$. I would like to find a vector $x^*$ such that ($l_1$ norm ) $||x-x^*||_1\leq \delta$, where $\delta >0$.

How can we generate the $x_i^*$ so that still $\sum_{i=1}^n x^*_i=1$?

Set $\delta' = \frac{\delta}{2(n-1)}$.
You can nudge each $x_i$ except for the last one by a random value in $\left[-\delta', +\delta'\right]$, and then adjust the last value to get the sum to be $1$.

Pseudocode:

  $x \leftarrow (x_1,...,x_n)$
  $\delta' \leftarrow \frac{\delta}{2(n-1)}$
  $y  \leftarrow  (y_1, \ldots, y_n)$
  for each $i$ until $n$ do
  $\quad y_i \ \leftarrow \ (\,x_i + \mathsf{randomBetween(-\delta',+\delta')}\,)$
  endfor
  $y_{n+1} \leftarrow (1-\sum y_i)$

Using $y$ instead of $x^*$, the last line guarantees tha $\sum y_i = 1$.

We need to check that $|| x - y || < \delta$:

For $i=1,2,\ldots, n-1$ we have $|x_i - y_i| = \delta_i'$. Since the original $x$ vector sums to $1$, we also have $$|x_n-y_n| = \left|x_n - 1+\sum_{i=1}^{n-1} (x_i + \delta_i')\right| = \left|\sum_{i=1}^{n-1}\delta_i'\right|$$.

So $$|| x- y|| = \sum_{i=1}^{n-1} | \delta_i'| + \left| \sum_{i=1}^{n-1} \delta_i'\right| \le 2\sum_{i=1}^{n-1} | \delta_i'| \le \delta$$ using the triangle inequality.


Which is better wording: x grows with $N^2$ or x grows with $O(N^2)$ Which of the following sounds better (or more rigorously):

x grows with $N^2$ or
x grows with $O(N^2)$ or
x grows quadratically with $N$.

The three options have different meanings in mathematics:

The first option means that $x$ increases as $N^2$ increases.
The second doesn't really make sense.
The third has the meaning you are presumably after (perhaps "with" is better replaced by "in").

You can rephrase the first two options as follows:

$x$ grows as $N^2$ - this is informal, and doesn't differentiate between $x \sim N^2$ and $x = \Theta(N^2)$.
$x$ grows as $O(N^2)$ - this is an awkward phrasing, and it is better to use symbols: $x = O(N^2)$. Note, however, that this is not the same as your third option - it corresponds to $x$ growing at most quadratically in $N$. To get the same meaning, you have to use big Theta: $x = \Theta(N^2)$.

You mention rigor. Rigor is a property of proofs, whereas here there are no proofs. Your descriptions might be informal, but could help explain rigorous proofs.

The best two options are "$x$ grows quadratically in $N$" and $x = \Theta(N^2)$". Both are acceptable.


Language of Turing machines that never visit some given state Can someone help me to determine and prove if the following language is decidable or not?

I tried to think on some reductions but I can't figure it out...

$$A=\{\langle M\rangle|\text{$M$ is $TM$ and there is a state $q$ in $M$ that $M$ never visits}\}$$

my try:

I built mapping reduce $E_{TM}\le_{m} B$:

$<M>\rightarrow <M>$

so I need to prove:
$$<M>\in E_{TM}\iff <M>\in B$$

First direction:

$<M>\in E_{TM}\rightarrow L(M)=\emptyset \rightarrow M \text{  never visits  }  q_{accept} \rightarrow  <M>\in B $

The problem is in the second direction. How can I promiss that if the language is empty $M$ visits all the states?

Thanks!

I will assume that you're using $E_{TM}$ to mean the language $HALT=\{\langle M\rangle|\text{$M$ does not halt}\}$ and $B=A=\{\langle M\rangle|\text{$M$ is $TM$ and there is a state $q$ in $M$ that $M$ never visits}\}$. Also, you should state what your mapping is because if it is just the identity (which it seems to be here) then this won't work. This is because we can have a turing machine that halts right away but also happens to have an extra state that it never reaches, so it is not the case that $B\subset E_{TM}$.

Instead, it may help to think about this more informally. If have the ability to tell whether or not a turing machine visits all of its states, how might we use this superpower to decide the halting problem? The simplest, most direct approach is to see if we can answer the question of whether $M$ visits a specific state $q\in Q$ using knowledge of $B$. Then we can reduce to the halting problem by simply asking if a given TM $M$ visits any of its accepting states.

To do this, let's see what "subsets" of $M$ are still in $B$. By this I mean that we will choose a subset $P\subset Q$ and then on any transition that goes from a state in $P$ to one in $Q\setminus P$ we will instead reroute it to a halting state. Let's call the new machine with the new accepting state along with $P$ as its states as $N_P$.

Now, we start off by looking asking if $N_P\in B$ for $P$ being the set containing just the starting state. If this TM is in $B$ then we know $M$ never visits any state other than its initial state. If it is not in $B$ then we continue by adding a new state to $P$ and asking if the new TM is in $B$, continuing until we get to a TM which is in $B$. The $P$ we end on will have to be the set of states the TM visits, and all other states are unvisited. Thus, we can tell whether a $M$ visits a certain state $Q$ by simply checking if $q$ is in the final version of $P$.


Lambda calculus : what about the bound variables in substituting expression? I found the following set of lemma in my lambda calculus textbook :

  Lemma 1.16 Let $x, y, v$ be distinct (the usual notation convention), and let no variable bound in $M$ be free in $vPQ$. Then

  (a) $[P/v][v/x]M \equiv [P/x]M$ if $v \notin \mathrm{FV}(M)$;

  (b) $[x/v][v/x]M \equiv M$ if $v \notin \mathrm{FV}(M)$;

  (c) $[P/x][Q/y]M \equiv [([P/x]Q)/y][P/x]M$ if $y \notin \mathrm{FV}(P)$;

  (d) $[P/x][Q/y]M \equiv [Q/y][P/x]M$ if $y \notin \mathrm{FV}(P), x \notin \mathrm{FV}(Q)$;

  (e) $[P/x][Q/x]M \equiv [([P/x]Q)/x]M$.

In the first lemma , the first stage of substitution can be done because $x$ is a free variable in $M$ and and no variable bound in $M$ is free in $V$. But what about variables which are free in $M$ but bound in $V$? In that case, the substitution would carry the risk of changing the semantics, like if there were a free variable in $V$, let's say $K$, and there were a term in $M$ like $\lambda.k$ then it would definitely make $K$ a bound variable in $M$ if the $X$ being replaced is at a position right to the  $ \lambda .k$ and the substitution will be wrong.

How is this resolved? I am unable to see through this clearly.

$x$, $y$, and $v$ are variables not (arbitrary) terms. To the extent that it makes sense to say so, the only variable free in $v$ is $v$. There could still be an issue with, say, $M = \lambda v.x$, i.e. $[v/x]\lambda v.x$, but, by assumption, $v$ is not bound in $M$, so this is not a valid case; $v$ is clearly free in $vPQ$.


Is the language of strings with an integer ratio of the number of a's to the number of b's context-free? Consider the language $L \subseteq \{a,b,c\}^*$, where $w \in L$ if and only if the ratio of the number of $a$'s in $w$ to the number of $b$'s in $w$ is an integer. I've been unable to find a counterexample string in $L$ which I can use to disprove (via a contradiction proof using the pumping lemma for CFLs) that $L$ is a CFL. This suggests that $L$ may be recognized by a nondeterministic PDA.

Now, if $\#_a(w) = i\cdot \#_b(w)$ for some $i \geq 0$, then I can perfectly match every single $b$ with $i$ $a's$. The problem is that since $i$ can be any nonnegative integer, there are strings in $L$ for which I'd need to match every one $b$ with one $a$, strings for which I'd need to match every two $a$'s with one $b$, and so on. I don't see how a nondeterministic PDA has the capacity to cover all such (i.e., infinitely many) matchings.

The language is not a CFL. The string $w$ that is the counter example to the pumping lemma is $a^{(N+1)^2}b^{(N+1)}$ where $N\geq 1$ is the pumping length. The idea is to take the number of $a$'s comparably larger by an order of $N$ to the number of $b$'s. Then if you pump you get strings with $\#_a={(N+1)^2+ik_1}$ and $\#_b ={N+1+ik_2}$ for $i\geq -1$. You would be able to prove that his string does not belong to $L$ for some $i$ and for any $k_1+k_2\leq N$.

Or if we take some crazy long string like $w = a^{(2N)!}b^{N+1}$, noting that the pumped string will have $\#_a={(2N)!+ik_1}$ and $\#_b={N+1+ik_2}$ for $i\geq -1$. If $k_1 = 0$ then we can take $i > \frac{(2N)! - N -1}{k_2}$. If $k_1 > 0$ then for $i=1$,
$\frac{(2N)!+k_1}{N+1+k_2}$ is a proper fraction, since $0\leq k_2 \leq N-1$, $1 \leq k_1 \leq N$ and therefore $N+1 \leq N+1+k_2 \leq 2N$ which implies $0<\frac{k_1}{N+1+k_2}<1$ is a fraction.


How many virtual machines run inside MS Windows? In my Computer Systems (first year) module as part of my EE degree I'm studying virtual machines, memory management, hardware abstraction etc. I have come across the information that the OS creates and uses a few virtual machines to provide hardware and I/O abstraction.

I assume that there are multiple VMs doing different tasks, but how are they organised?

Are they one VM per task, e.g. one for disk I/O and the filesystem, one for human interface devices, etc; or are they all general purpose and are one VM per process?

Many thanks,
Ben Adamson

The NT kernel does have sub-systems or did for DOS, Win32, POSIX, and OS/2. You might consider them to be a VM layer in that they are instantiated per process and provides a compatible binary API to the process so that it may run. Each of these sub-systems only maps the binary API for the process to the API of the kernel and as such they don't do much other than that. State pertaining to a sub-system is kept in the process's context.

See chapter 5 in Inside Windows NT (Helen Custer, 1993) for more.


What are some problems which are easily solved by human brain but which would take more time computers? Are there any problems which can be solved by human brain in a very less time but a computer may take a lot of time or a computer could never solve it ?

Language processing.

Every kid learns how to use language within his first 1-3 years. Computers still don't understand simple language structures, not to mention ambiguity, sarcasm, subtleties, etc.


Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$ I'm reading my textbook and it claims that the regular expression $c^*(b \cup (ac)^*)^*$ defines the language $L$ over $\{a,b,c\}$ which consists of all strings that do not contain the substring $bc$.

However, I'm failing to see how that language would contain strings such as $bbbaaa$ or $aaabbb$. Am I missing something or is that regular expression incorrect? The expression I come up with was $ \left( \left( \left( a \cup b \right) ^*a \right) ^* \left( c \cup a \right) ^* \right) ^*b^* $

I checked an older edition of Sudkamp, and it had the same example. Actually the expression is $c^*(b\cup ac^*)^*$, which has a different bracketing.
Your $(ac)^*$ specifies strings of the form $acac\dots ac$, whereas Sudkamp has $ac^*$ which means strings like $acc\dots c$.

It follows the arguments of the answer by Raphael, but backwards. Any sequence of $c$'s is either at the beginning of the string, or else it cannot be preceeded by $b$ because there is an explicit $a$ in the expressing.


Finding Triples that satisfy modulo equation in $O(n\log n)$ time Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that satisfy the equation

$$a^2 + b^3 = c^4 \mod n\,,$$

where $a,b,c \in\{0,1,....,n-1\}$ and $n$ is any natural number.

Does anybody have any idea how to do this? Obviously checking all values yields $O(n^2)$ time.

I am able to compute the triples for a given value of $c$ within the desired bound since you can build a BST in $O(n\log n)$ time where the keys are the particular modulo values in $b^3$ and the values are the number of instances they appear. Then by calculating $((c^4 \!\!\mod n) + n - (a^2 \!\!\mod n)) \!\!\mod n$ for every value of $a$ and doing a search for that key in $b$ we achieve the desired runtime.

How can I achieve the same result for every value of $c$ rather than a specific one though?

I presume the $O(n\log n)$ run-time comes from some form of binary search, sorting or binary search tree but I am not sure exactly how to achieve this for all the values of $c$ rather than a specific one. Any help is appreciated. Thank you.

Hint: Use FFT to multiply the polynomials
$$ \sum_a x^{a^2 \pmod{n}}, \qquad \sum_b x^{b^3 \pmod{n}}. $$


Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n) I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time Hierarchy Theorem.

After the assumption, I want to prove that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$.

The first case $\mathsf{NP} \subset \mathsf{DTIME}(2^{n})$, is trivial.

For the second case, let $L \in \mathsf{DTIME}(2^{n})$ and $M$ be a deterministic TM that can decide it, let $$L_{\mathrm{pad}} = \left\{\left\langle x,1^{2^{\sqrt{|x|}}} \right\rangle : x \in L\right\}.$$ I am not sure how, using $L_{\mathrm{pad}}$, I can reach a conclusion that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$, I feel like I am missing something and that my method is not in the right direction, or it is lacking an extra detail.

It is enough to pad a special delimiter (say a comma) and $(|x|^2-|x|-1)$ 1's. Suppose $L_\mathrm{pad}= \left\{\left\langle x,1^{|x|^2-|x|-1} \right\rangle : x \in L\right\}$. Since $L\in\mathsf{DTIME}(2^n)$, there is a TM that can determine whether $x\in L$ in $O(2^{|x|})$ time. We then construct a new TM: given a string $y$, it first checks whether $y$ has the form $\left\langle x,1^{|x|^2-|x|-1} \right\rangle$, then simulates $M$ on $x$. This new TM determines whether $y\in L_\mathrm{pad}$ in $O(2^{|x|})=O\left(2^{\sqrt{|y|}}\right)$ time, so we have $L_{\mathrm{pad}}\in \mathsf{DTIME}\left(2^{\sqrt{n}}\right)$, thus $L_{\mathrm{pad}}\in\mathsf{NP}$ by your assumption. This means there exists a non-deterministic TM $M'$ that decides $L_{\mathrm{pad}}$ in polynomial time. Hence, we can construct a new non-deterministic polynomial-time TM that decides $L$ by first padding a comma and $(|x|^2-|x|-1)$ 1's to the input then simulating $M'$, which means $L\in\mathsf{NP}$.


Hoare logic - total correctness of loops Consider a while loop of the form :

$\texttt{while (C) {S}}$

with $\texttt{C}$ the condition and $\texttt{S}$ the body of the loop.

Let $\texttt{I}$ and $\texttt{V}$ respectively be an invariant and a variant of this loop. The rule for total correctness of while loops is given in my textbook by:

  If $\texttt{I} \Rightarrow \texttt{V} \geq 0$

  And $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

  Then $[\texttt{I}] \, \texttt{while (C) {S}} \, [\texttt{I} \land \neg
\texttt{C}]$

From what I think I understand, in order for the loop to terminate, the variant $\texttt{V}$ must stricly decrease and that it must also be bounded by zero. However, when I translate that mathematically, I obtain a different proposition from that of my textbook :

$$[\texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{V} \geq 0 \land \texttt{V} < v_0]$$

My question : Are this last proposition and my textbook's rule saying the same thing about what needs to be proven in order for the loop to terminate? In other words : is

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

the same as

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ together with $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Why or why not?

They are equivalent, in the sense that every time you can apply the textbook rule you can also apply your own rule, and vice versa. The invariant for the two rules is similar, but not the same.

Converting a textbook rule instance into an instance of your rule

Suppose we have an application or your textbook rule. I.e., we have found some $\texttt{I}$ for which:

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ together with $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Then, thanks to the implication above, we also have $\texttt{I} \iff  \texttt{I} \land \texttt{V} \geq 0$. Using rule PrePost, we can rewrite the invariant into its equivalent, and we get an application of your rule:

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

Here, we use the same invariant as in the textbook rule.

Converting an instance of your rule into a textbook rule instance

Now, for the converse direction. Suppose we have found $\texttt{I}$ for your rule:

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

Now, we can't assume $\texttt{I} \Rightarrow \texttt{V} \geq 0$, so we can't use $\texttt{I}$ for the textbook rule. However, we can use as a new invariant $\texttt{I}' := \texttt{I} \land \texttt{V} \geq 0$. We trivially have $\texttt{I}' \Rightarrow \texttt{V} \geq 0$ by construction (*). Further, from the hypothesis

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

we can obtain (by PrePost)

$[\texttt{I}' \land \texttt{C} \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I}' \land \texttt{V} < v_0]$ (**)

Properties (*) and (**) are exactly what we need to apply the textbook rule.


Decidability of a set containing first symbols of elements of a decidable set Let's say we have an alphabet $\Sigma = \{a,b, \dots , z\}$

Set $A$ consists of words $x_i$ containing symbols from $\Sigma$ alphabet, which have this structure

$x_i := \alpha_i \beta_i$, where $\alpha_i$ is just 1 symbol from $\Sigma$ and $\beta_i \in \Sigma^{*}$ (can also be empty)

So the set A should look like this
$A = \{ \alpha_1 \beta_1, \alpha_2 \beta_2, \dots , \alpha_n \beta_n, \dots\}$

The question is:

If the set $A$ is decidable, then should also the set $B = \{ \alpha_1, \alpha_2, \dots , \alpha_n, \dots\}$ be decidable?

My thoughts..

For the set $A$, we have a total computable function $f(x_i)$ which gives an answer, whether a given input element contains in $A$ or not.
Now, when we shrink $x_i$-s and only leave $\alpha_i$ parts, we cannot use $f$ anymore. The only idea which came to my mind, is using this naive algorithm.

get input $\alpha_j$
for each $x_i \in A$
   if $\alpha_j$ is prefix of $x_i$
      return YES
return NO

And here, I guess, the problem is in for each statement. Here we enumerate all elements of the set $A$. For being able to do this, I guess we need to use some kind of mapping $\phi : \mathbb{N} \to \Sigma^{*}$ and then apply $f$ on the output to get all possible $x_i$-s. This algorithm may give a correct answer, but it also may give no answer (we will never reach to return NO). So my conclusion was B is not decidable (B is semi-decidable). But there might also be a 'better' algorithm?

..end of my thoughts.

I apologize if my thoughts are 100% wrong. That's how far I could reach.

Any help is much appreciated.

You probably have to twist your head a couple of times but $B$ is decidable and it does not depend on the decidability of $A$. Note that $B \subseteq \Sigma$, i.e. a subset of your finite alphabet. Thus, $B$ is finite and hence, it is decidable.

However, this reasoning is not constructive: It is just enumerating all functions $\Sigma \to \{0, 1\}$ (that are $2^{|\Sigma|}$, i.e. finitely many), which are all computable, and one of them is the correct function although you do not know which one.


Is there a formal term for functions that have static state across executions? Two examples, one in PHP:

function adder($i){
  static $a = 0;
  $a += $i;
  return $a;
}

A similar effect can be achieved with closures in javascript:

var adder = (function(){
  var a = 0;
  return function(i){
    a += i;
    return a;
  }
})();

In javascript I've really just created an object. Implementation details not withstanding, does stateful-functions have a formal name?

Not that I know of, but "stateful function" is reasonably descriptive.  In informal conversation, that's what I'd use, as long as I suspect the audience will understand what I mean.  In formal writing, I might still use the same phrase but also provide a careful definition of what I meant by that phrase.  Really, that's a large part of what "formal" writing is about: it's about being precise about what you mean.


Find out if a path exists avoiding circular obstacles Given

a rectangle defined by its corners $(0, 0)$ and $(w,h)$,
$n$ circles $\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ with the
same radius $r$,

I need to determine the smallest possible radius r so that there is no
way to get from $(0,0)$ to $(w, h)$ without touching those circles.
What I have tried is

Use binary search to determine r
But the issue is that since there is no limitations for the
coordinates of the points (e.g. for them to be integers) I can't get
any idea how to construct a graph and use some path finding algorithm
such as DFS.

Any help would be appreciated.

Examples
Example 1, $w = 15, h = 20$; circles with coordinates $(2,7)$ and $(7,3)$; the result is $d \sim 3.2016$

Example 2 (without the right radius, but just to show what the issue is)

Your assumption using binary search is a good assumption, that means
that we can assume we know the radius, and focus only on the subproblem:

Given a rectangle and a set of circles, is it possible to navigate in
the rectangle from the top left corner to the bottom right corner
without touching a circle.

If a circle is covering either the starting point or the end point, we
can abort immediately, so we'll assume they don't.
We will create a graph consisting one vertex for each circle, and one vertex for the south east edges of the rectangle, and one vertex for the north west edges of the rectangle, in other words:
$$V = \{ v_c \mid \text{$c$ is a circle} \} \cup \{v_{\text{se}}, v_{\text{nw}} \}$$
Then we create the edges as follows:
$$E = \{ e = v_{c_1} v_{c_2} \mid \text{$c_1$ and $c_2$ overlap}\} \cup \{ e = v_{c} v_{s} \mid \text{$c$ touches side $s$}\}$$
In other words an edge between two objects if they overlap
geometrically.
If the south east sides are connected to the north west sides, then
it means that you cannot travel from the lower left part of the
rectangle to the upper right part of the rectangle.
In other words, you only need to see whether $v_{\text{se}}$ is
connected to $v_{\text{nw}}$ in your constructed graph, which would
isolate the starting point from the end point.

Yes instance

No instance (south is connected to west)


Is the Kleene star of an intersection contained in the intersection of Kleene stars? I need to find if given two formal languages $L_1$ and $L_2$ $$(L_1 \cap L_2)^*\subseteq (L_1^* \cap L_2^*) $$
I think that it's true since this can be rewritten as $$ \bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq (\bigcup^\infty_{i=0}L_1^i \cap \bigcup^\infty_{i=0}L_2^i)$$ and in general, $$(A \cap B) \cup (C \cap D) \subseteq (A \cup C) \cap (B \cup D)$$
I may be wrong since it has been a long time since i have done anything with set theory, and this is taken as given.
Thanks

Yes, it is true. But  the argument to support the conjecture is incorrect.

The correct proof is as follows: $L_1 \cap L_2 \subseteq L_1 $ and therefore $(L_1 \cap L_2)^* \subseteq L_1^*$. (argument: if $A \subseteq B$ then $A^* \subseteq B^*$).
Similarly $(L_1 \cap L_2)^* \subseteq L_2^*$.

Therefore $(L_1 \cap L_2)^* \subseteq (L_1^* \cap L_2^*)$ (argument: if $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$).

Anyway you can not write $(A \cap B)^i \cup (C \cap D)^j = (A^i \cup C^j) \cap (B^i \cup D^j)$.

Correct relation is: $(A \cap B) \cup (C \cap D) = (A \cup C) \cap (B \cup D) \cap (A \cup D) \cap (B \cup C) $

However $\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq (\bigcup^\infty_{i=0}L_1^i \cap \bigcup^\infty_{i=0}L_2^i)$ is correct because
$\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq \bigcup^\infty_{i=0}L_1^i $  and $\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq \bigcup^\infty_{i=0}L_2^i $.


Why doesn't the binary fraction representation match the decimal fraction representation? The Problem: What value does the hexadecimal number x55544552 represent in data type IEEE floating point?

My Work:
     I first wrote out that hexadecimal number in binary and got

0101 0101 0101 0100 0100 0101 0101 0010

   Now I have my three different sections, the sign, 0, the exponent 10101010 - 127, or 170 - 127, 43, and the fraction portion  101 0100 0100 0101 0101 0010, or 5522770.

    Now I can write out my IEEE floating representation as
        1.552270 $*$ 2 $^{43}$
   To simplify that expression, I decided to move the decimal point 23 slots to the right(the whole exponent proportion) and got
   (1 101 0100 0100 0101 0101 0010) * 2 $^{20}$) or 13911378 * 2$^{20}$.

To me, all my math made sense. When I checked
my answer on  Hex to IEEE Float, everything matched up but I couldn't figure out this part on the web application.
The web application has a specified section called fraction which represents the fraction of the floating point representation. In binary, the fraction is 1 .10101000100010101010010 but in decimal, the web application says the fraction is 1.6583655. When I converted 10101000100010101010010 to decimal, I got 5522770. Shouldn't the fraction decimal representation be 1.5522770 or am I missing something?

No, that's not how binary fractions work.
A decimal such as $0.13$ represents
$$0.13_{\mathrm{dec}} = 1\times 10^{-1} + 3\times10^{-2} = \frac{13}{100}\,.$$

Similarly, a binary fraction such as $0.1101$ represents
$$0.1101_{\mathrm{bin}} = 1\times 2^{-1} + 1\times 2^{-2} + 0\times 2^{-3} + 1\times2^{-4} = \frac{13}{16}\,.$$
$1101_{\mathrm{bin}} = 13_{\mathrm{dec}}$ but
$$0.1101_{\mathrm{bin}} = \frac{13}{16}\neq\frac{13}{100}=0.13_{\mathrm{dec}}\,.$$

Another way to see that you can't convert fractions into binary by forgetting that they're fractions is to note that $0.3=0.30$, but $3\neq 30$. So it can't possibly be that you convert $0.3$ in decimal to binary by saying "$3$ in binary is $11$, so $0.3$ in binary is $0.11$", since $0.3=0.30$ in decimal, so they should be equal in binary, too. But $30$ in binary is $11110$.


Is safety-critical software a subset of real-time software? I would like to refute my hypothesis that all safety-critical software (that is, software where errors can have catastrophical consequences, either in terms of human lives or high material costs) is a real-time software (where tasks have timing constraints) by finding interesting counterexamples: systems without timing constraints which are safety-critical.

I tried thinking of several examples, but they always seem somehow related to some physical system (e.g. flight control, radiation therapy, nuclear power) and therefore have some implicit timing constraints/deadlines. Even somewhat contrived "safety-critical" systems such as high-frequency trading are still real-time.

Note: I am not interested in a very specific subset of the code which is timing independent, but on something more complete, consisting of a substantial part of a complete application.

I would like to refute my hypothesis that all safety-critical software (that is, software where errors can have catastrophical consequences, either in terms of human lives or high material costs) is a real-time software (where tasks have timing constraints) by finding interesting counterexamples: systems without timing constraints which are safety-critical.

A good example of a safety critical program which does not itself have to meet real time constraints is a compiler.

If a compiler has code generation bugs, then even if the programmer wrote a safe program, the emitted machine code may still fail to meet some necessary guarantees. As a result, the standard practice at many development teams developing safety-critical software is to generate code with compiler optimizations turned off, and then to manually review the generated machine code.

The Compcert C compiler has a machine-checked formal proof showing that it never  generates incorrect assembly programs for any input program. As a result, it is possible to (a) limit code review to the C source code, and (b) permit the compiler to do optimization passes, without compromising the safety of the overall system. (See for example Towards Formally Verified Optimizing Compilation in Flight Control Software...)

Obviously, if you are trusting the compiler to generate code for flight control software, it is safety-critical. Equally obviously, a compiler is not real time software.