# Question
Title: Does White never lose in Chess if Chess is solved?
If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?

# Answer
> 3 votes
This is unknown at the time of writing. Further, according to solving chess on Wikipedia, no resolution is expected in the near future.

# Answer
> 4 votes
Let's take alternative chess. The rules are identical to chess, except that White can pass in it's very first move (but Black can't, even if White passed).

Now it's obvious that White has a strategy to never lose. Because if every move except a pass leads to a loss, then White can pass, and we know that whatever move Black does will lead to a loss for black.

In real chess, nobody knows. And nobody knows if there is a forced win for either white or black either. It is also reasonably likely that there is a time and space limited algorithm that can force a draw.

White starts with an advantage - 1/2 tempo. (Why one half tempo? After e3-e5 e4 White has lost one tempo, and White and Black have effectively swapped sides). We may suspect that with perfect game any advantage would tend to increase. But you need a considerably better position than your opponent in order to win and might not be able to ever get that.

# Answer
> 2 votes
Maybe it is worth mentioning why some kind of reasoning like

> White has a winning strategy because everything black does, white could have done before.

does not work. You might already be familiar with *Zugzwang*, i.e. a position where the one who has to move loses (the game or just material) or at least weakens his position. The Trébuchet position shows an example, with reciprocal Zugzwang; here, the player who does not have to move next has a forced win.

It is not known whether the initial position is such a position with Zugzwang for white and a forced mate for black.

---
Tags: space-complexity, search-problem, board-games, search
---


# Question
Title: Is it standard for VMs to run *= computationallyHeavyFunction() if the left hand side is 0?
What is the standard way for VMs to deal with 0 \*= computationallyHeavyFunction()? Given that once the VM sees that left hand factor is 0, it would know that the result of `computationallyHeavyFunction()` would not matter, is it standard for VMs to still compute `computationallyHeavyFunction()` or do they tend to omit that computation and just evaluate as 0?

**Edit:** After answer, I think I misphrased the question. I'll rephrase a bit and replace `computationallyHeavyFunction()` that has unknown factors. If VMs see `0 * (1-1/veryLargeNumber)^anotherVeryLargeNumber`, do they tend to not compute right factor? Assuming they rely on squaring algorithm, quite computation heavy with O(log2(anotherVeryLargeNumber)).

# Answer
> 5 votes
Optimizing `0 * f(…)` is correct only if `f` has no side effect and its result is known to be finite. If `f` has side effects, they must be executed even if the result does not matter. If `f` might return a result such as NaN or infinity then the result of the calculation might be NaN and not 0.

A VM that is optimized for numerical or symbolic calculations and that has access to enough type information to know that `f` has no side effects and has a finite result would presumably optimize the call away. Any other type of VM would not do this optimization.

# Answer
> 1 votes
Let's ignore the issues of side effects and peculiarities of floating point such as NaN and signed zeros and assume that it is meaningful to avoid the computation.

Let's also ignore the question of why the front end who generated the VM instruction stream did not do that optimization if the `0` is a literal or the result of a constant expression. That's an important assumption, as that optimization is relatively easy to do there.

My first point is that VM implementations varies a lot. I'll simplify that implementation space by considering two cases: interpreter VMs which executes the instruction one by one and compiling VMs which compile the VM instructions to another representation (potentially machine language) before execution. However note that it is common to have both approach in one VM executor, the interpreter used in a first place to collect profiling information to guide the compilation process of hot paths.

In the case of interpreter VMs, you have to look at the language interpreted. Those are usually byte code for a stack or a register machine. That's not a representation suitable for such kind of optimization as the facts first that the complex expression is suitable to be ignored is difficult to extract, then that there is a multiplication and that the value by which the multiplication is a special one and is probably after the description of your complex computation. In summary, I'd be surprised if interpreter VM paid that cost as I doubt the benefits warrant the price and if you are that performance sensitive, you'll have the setup to switch to a compiling VM for hot paths.

In the case of compiling VMs, you can have in practice quite a lot optimizations and they can afford to put back the instruction stream in a representation suitable for optimizations. The optimizations done are in fact the same kind of optimizations done in an optimizing compilers, with a tighter constraint on compilation time and the advantage of easier profiling information to guide the compilation. Reduction of multiplication by a constant (either a true constant or a constant value detected with the help of profile information) is far from being the most complex optimization they do and I'd expect it do be done. The case where the `0` is not a constant but the value of a variable is more complex. You can imagine it to generate code which check for `0` and then completely avoid the costly function, just as it is done for short-circuit boolean operators, but I'd be surprised if it is commonly done.

---
Tags: computer-algebra
---


title: Quick Sort Equal to or Less Than

text:
# Question
Title: Quick Sort Equal to or Less Than
For my course I have to memorise a number of algorithms and to know how to perform them by hand. The steps of the quick sort are given as the following in the text book I am using:

1. Choose the item at the midpoint of the list to be the first pivot
2. Write down all the items that are less than the pivot, keeping them in order, in a sub-list
3. Write down the pivot
4. Write down the remaining items (those greater than the pivot) in a sub-list
5. Apply steps 1 to 4 to each sub-list
6. When all items have been chosen as pivots, stop

The problem is that these instructions are ambiguous as to what to do if there is an item which is equal to the pivot. Does it fall into the first sub-list (written before the pivot) or the second (written after the pivot)? I assume that there is some sort of agreed upon standard for this.

# Answer
> 2 votes
It doesn't really matter which way you decide to break the tightness. You could put all the elements less than or equal to the pivot in the first list and the ones larger than the pivot in the second list, or you could put only the elements smaller than the pivot in the fist list and the ones larger than or equal to the pivot in the second list.

You could even arbitrarily pick the list that will contain an element equal to the pivot (except the pivot itself), on an element-to-element basis. No matter how you will assign these elements to the lists, the algorithm will still work.

Another solution that slightly breaks the algorithm's description you gave is to put all elements smaller than the pivot in the first list $L\_1$, all those larger than the pivot in the second list $L\_2$, and insert as many copies of the pivot $x$ as there are elements equal to $x$ (including the pivot itself) between the sorted versions of $L\_1$ and $L\_2$.

As a final note: the pseudocode reported in your textbook seems wrong. You are supposed to recursively repeat the whole procedure on $L\_1$ and $L\_2$, not just steps $1$ to $4$ (otherwise you will never reach a recursion depth larger than $1$).

# Answer
> 2 votes
It seems the author assumed there were no two equal items, which isn't usually an assumption you should make. (those greater than the pivot) seems to be not an instruction, but just an explanation, so I would leave that out. Follow exactly what the instructions say: All items less than the pivot, then the pivot, then the remaining items (which may all be equal to the pivot, but the instructions don't care about that).

PS. Comparing using "\<" vs "\<=" can make a huge difference, for example if you sort a huge array where all items are equal. For that situation, you want an algorithm that handles it efficiently and not as the worst case.

PPS. It is often a very good idea to ask "what if ..." when you suspect it is something that can happen but that the algorithm designer didn't think about. Like in this case. If you write code that *you* designed, it is a good idea in that situation to add a comment that explains "Yes, I did think about this, and it works just fine in this case".

PPPS. This isn't at all how Quicksort is usually implemented, since it uses lots of additional space. Quicksort isn't supposed to use space except the original space of the data and a tiny bit of stack space. And you don't continue until every element has been chosen as the pivot, but until the sublists have length 0 or 1 (and lists of length 2 are likely sorted using a single comparison).

---
Tags: algorithms, quicksort
---


# Question
Title: Which Grows Faster: Factorial or Double Exponentiation
Which of the functions among $2^{3^n}$ or $n!$ grows faster?

I know that $n^n$ grows faster than $n!$ and $n!$ grows faster than $c^n$ where $c$ is a constant, but what is it in my case?

# Answer
You can find the result by taking a $\log$. Hence:

$$\log(2^{3^n}) = 3^n$$ $$\log(n!) \leqslant \log(n^n) = n\log n$$

(In the latter equation, we have used the fact that $n! \leqslant n^n$, as you note in the question.)

Of course $3^n$ grows faster than $n \log n$. As $\log$ is an increasing function, we can say $2^{3^{n}}$ grows faster than $n^n$, and also $n!$.
> 46 votes

# Answer
Another way to directly compare the two expressions is to take the ratio of consecutive terms:

$$\frac{2^{3^{n+1}}}{2^{3^n}}=2^{2\cdot 3^n}\gg 3^n\gg n+1=\frac{(n+1)!}{n!}$$

(for positive integers $n$), and clearly also $2^{3^1}=8\>1!$, so $2^{3^n}$ indeed grows more rapidly than $n!$.
> 26 votes

# Answer
You noted in your question that $n^n$ grows faster than $n!$, and that’s a great starting point for comparing the growth of $2^{3^n}$ and $n!$. Specifically, let’s ask - of $n^n$ and $2^{3^n}$, which grows faster?

To answer that, let’s try rewriting $n^n$ so that it has the same exponential base as $2^{3^n}$. Since $n = 2^{\log\_2 n}$, we have that

$$n^n = (2^{\log\_2 n})^n = 2^{n \log\_2 n}.$$

Now, is it easier to see how $n^n$ and $2^{3^n}$ relate?

As a note, this approach is similar to taking the base-2 logs of both expressions. I thought it would be good to include this here because it gives a slightly different perspective on how to arrive at the answer given your initial observation.
> 12 votes

# Answer
Induction.

Base case: $n=1$ gives $2^{3^1}=8$ and $1!=1$ which clearly holds.

Hypothesis: suppose that $2^{3^k}\>k!$ for some $k\in\Bbb N$.

Consider $n=k+1$. Then $$2^{3^{k+1}}=2^{3^k\cdot3}\>(k!)^3=(k+1)!\cdot\frac{k!(k-1)!}{1+\frac1k}\>(k+1)!$$ which is true $\forall k\>1$ and thus the result follows.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: Why increasing the beam width does not necessarily improve the beam search solution?
Normally increasing the beam width is a better solution, but I have read that this is not necessarily true, is there any proof of this?

# Answer
Imagine your tree looks as follows:

You are looking for the leaf with minimum label and the label of each internal nodes represents the heuristic value associated with the subtree routed at that node.

If the width of your beam is just $1$, you start at the root and then go $\rightarrow 5\rightarrow7\rightarrow0$.

If the width of your beam is $2$, you first take $\[5,6\]$ as potential candidates. Look at $5's$ children, so your best candidates at that point for the next level are $\[7,8\]$. Look at $6's$ children, both better candidates, so your potential candidates become $\[3,4\]$. Then you'll find only $9$'s going down, which is worse than the solution found with a beam width of $1$.

But if your heuristic is well behaved enough, you might be able to guarantee that increasing the beam width can not degrade the quality of the solution that is found.
> 1 votes

---
Tags: search-algorithms
---


title: Is SEMIPRIME in P?

text:
# Question
Title: Is SEMIPRIME in P?
The title says it all: is there a deterministic polynomial time algorithm that tests for semiprimality? (A number $N$ is a semiprime if it is the product of two primes.) I don't understand the ''PRIMES is in P'' paper, so I can't judge if it adapts, and I haven't had any luck searching this topic online.

If it is, is there a good (preferably concise) place to read about it?

# Answer
> 1 votes
I only know that before “Primes in P” was shown, there were excellent non-deterministic algorithms to show whether a number is prime or composite (if the algorithm says “it’s prime” for a composite number, it’s 1000 times more likely due to a hardware problem than due to a problem with the algorithm).

I know of no efficient non-deterministic algorithm to check if p is semi prime.

---
Tags: complexity-theory, reference-request, primes
---


title: What algorithm to use for this problem?

text:
# Question
Title: What algorithm to use for this problem?
I was recently faced with a hackerrank interview test where I couldn't solve the following problem correctly. I would not want to name the exact problem for privacy purposes, but I can tell that it was nowhere in Google with this name.

**Problem**

We want to organize an event with as much performers as possible. We are given a list of possible performer arrival times and performance durations. Our function should return the maximum number of performers that can be selected without conflicts.

**Example**

N = 5
arrivals = \[1, 3, 3, 5, 7\] (performers arrive in these times)
durations = \[2, 2, 1, 2, 1\] (the time needed to finish their performances)
solution = 4

So at time 1 we can accept the performer and will finish at time 3. At time 3 we have two conflicting choices, and doesn't matter which we chose. Time 5 and 7 are not conflicted either.

**My solution**

1. Made tuples of the arrivals and durations by zipping. Sorted the tuples first on arrival, then on duration.
2. Outer for cycle for i from start to finish. Initialize new set in each iter.
3. Inner for cycle for j from i to finish. Check if j can be added to the set without conflict. If set is longer than max I save.

Python source

**Questions**

1. Are there better ways, standard algorithms to solve this problem?
2. I know that there are some edge cases, for which my algorithm doesn't work. Hackerrank evaluated my algo, and it only passed 7/13 test cases. What could be some edge cases I am missing?
3. Is this a search problem or an optimization problem?

# Answer
> 1 votes
This is a simple Interval Scheduling Maximization problem, which can be solved in *O(n log(n))* time via a simple greedy algorithm. The trick is to sort performances according to *end time* and not *start time*.

Here is the description of the solution found on the Wikipedia page I linked:

---

Several algorithms, that may look promising at first sight, actually do not find the optimal solution:

* Selecting the intervals that start earliest is not an optimal solution, because if the earliest interval happens to be very long, accepting it would make us reject many other shorter requests.
* Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal.

**Greedy polynomial solution**

The following greedy algorithm does find the optimal solution:

```
Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

```

Whenever we select an interval at step 1, we may have to remove many intervals in step 2. However, all these intervals necessarily cross the finishing time of x, and thus they all cross each other. Hence, at most 1 of these intervals can be in the optimal solution. Hence, for every interval in the optimal solution, there is an interval in the greedy solution. This proves that the greedy algorithm indeed finds an optimal solution.

A more formal explanation is given by a Charging argument.

The greedy algorithm can be executed in time *O(n log n)*, where *n* is the number of tasks, using a preprocessing step in which the tasks are sorted by their finishing times.

---

# Answer
> 1 votes
Look at maximum interval scheduling.

Assign an interval $(s\_i, t\_i)$ to each performer, for $i=1,\dots,N$, meaning that the performance starts at time $s\_i$ and has a duration of $t\_i - s\_i$.

Assume for now that all the intervals are sorted by their end time. Just for simplicity assume also that all times are distinct (this assumption is unnecessary). Your problem can then be solved in $O(N)$ time.

Consider $(s\_1, t\_1)$ and let $I$ be the set of intervals that intersect it (excluding $(s\_1, t\_1)$ itself).

Is easy to see that all the intervals in $I$ must start before $t\_1$ (as otherwise they wouldn't intersect $(s\_1, t\_1)$) and end after $t\_1$ (otherwise $t\_1$ wouldn't be the minimum end time). This means that all intervals in $I \cup \\{ (s\_1, t\_1) \\}$ intersect with each other and hence any solution can contain at most one of them.

Let $S$ be a solution (i.e., a subset of pairwise non-intersecting intervals). It is always possible to convert $S$ into a new solution $S'$ that contains $(s\_1, t\_1)$ and such that $|S'| \ge |S|$.

If $S \cap I = \emptyset$ then we are trivially done since we can pick $S' = S \cup \\{ (s\_1, t\_1) \\}$ (notice that this also includes the case in which $(s\_1, t\_1) \in S$).

If $S \cap I \neq \emptyset$, let $(s\_i, t\_i)$ be the unique interval in $S \cap I$. Any interval $(s\_j, t\_j) \in S \setminus \\{ (s\_i, t\_i) \\}$ must satisfy either $s\_j \> t\_i \> t\_1$ or $s\_i \> t\_j \> t\_1$. The latter case is actually impossible since it would contradict the fact that $(s\_i, t\_i) \in S$. In other words, if we replace $(s\_i, t\_i)$ with $(s\_1, t\_1)$ we still obtain a feasible solution. Therefore we pick $S' = S \cup \\{(s\_1, t\_1)\\} \setminus \\{ (s\_i, t\_i) \\}$.

The bottom line is that there is always an optimal solution that contains $(s\_1, t\_1)$. Therefore you can always add $(s\_1, t\_1)$ to your solution, delete all intervals in $S \cup \\{ (s\_1, t\_1) \\}$, and look for the optimal solution among the remaining intervals. This amounts to running the greedy algorithm that considers the intervals in order and adds any interval that fits.

From your instance it seems that the starting times are already sorted. In this case you can do the trick of "reversing the time", i.e., swapping the starting and ending times, for example by changing $(s\_i, t\_i)$ into $(-t\_i, -s\_i)$, which allows you to obtain a $O(N)$-time algorithm by skiping the initial sorting step which would already require $\Omega(N \log N)$ time.

---
Tags: algorithms, optimization, search-algorithms
---


title: Non planarity of K3,3

text:
# Question
Title: Non planarity of K3,3
I am reading about planar graphs from this site.

It says:

> The complete bipartite graph K3,3 is not planar, since every drawing of K3,3contains at least one crossing. why? because K3,3 has a cycle which must appear in any plane drawing.

I am not able to get what *cycle which must appear in any plane drawing* has to do with *edge crossing*. Can't a cycle appear in plane drawing without crossing edges and thus letting the graph be planar? I must be missing something stupid.

# Answer
This explanation is wrong. In principle you could prove that $K\_{3,3}$ is not planar by enumerating all types of planar embeddings, and show that some paths must cross. If I remember correctly this is the path chosen in some lecture notes, so if you look around you might be able to find this argument. Another route, taken by your lecture notes, is to use Euler's formula.

When your notes say that $K\_{3,3}$ isn't planar since it "has a cycle", they were trying to provide you some intuition, not too successfully I reckon. The claim requires a proof which is indeed given later in the notes.
> 8 votes

# Answer
In a comment @MithleshUpadhyay links to a document which is part of the book

```
Graphs
An Introductory Approach
by Robin J. Wilson and John J. Watkins
John Wiley & Sons, Inc. 1990

```

It seems that the site you are referencing to does cite this book incompletely. Here is the complete text from the book:

> On the other hand, the complete bipartite graph $K\_{3,3}$ is not planar, since every drawing of it contains at least one crossing. To see why this is, note that $K\_{3,3}$ has a cycle of length $6$ (namely, $uavbwcu$) which must appear in any plane drawing as a hexagon (not necessarily regular).
> We must now insert the edges $ub$, $vc$, and $wa$. Only one of them can be drawn inside the hexagon, since two or more would cross. Similarly, only one of them can be drawn outside, since two or more would cross.

The paragraph following the picture is missing in the text you read. I think the proof from the original text is completely clear.
> 4 votes

# Answer
If a,b,c,1,2,3 are the vertices of $K\_{3,3}$, then in any planar drawing of $K\_{3,3}$ the cycle \[1a2b3c1\] must appear as a cycle.

For example, if it is drawn in the form of a hexagon, then the edge \[1,b\] will lie either completely inside the hexagon or completely outside it. Assume that the edge \[1,b\] lies completely inside the hexagon. The edge \[2,c\] has to be drawn outside the hexagon or else it will intersect the edge \[1,b\]. Now \[3,a\] cannot be drawn without intersecting either edge \[1,b\] or \[2,c\].

The same argument is valid if edge \[1,b\] is drawn outside the hexaon.
> 3 votes

# Answer
Maybe this is useful, even if is not the same kind of proof you want.

Every planar graph without cycles of 3 vertices (triangles) should follow this rule (that derives from Euler's rule):

$m \leq 2n - 4$

But $K\_{3,3}$ has:

$m = 9$

$n = 6$

$9 \leq 8$

That's absurd, so $K\_{3,3}$ is not planar.
> 0 votes

---
Tags: graphs
---


title: Maximum value of arbitrage

text:
# Question
Title: Maximum value of arbitrage
I'm trying to solve this from The Algorithm Design Manual:

> 6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time during which 1 U.S. dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars. At such a time, a smart trader can trade one U.S. dollar and end up with 0.75×2×0.7=1.05 U.S. dollars---a profit of 5%. Suppose that there are n currencies c1,...,cn and an n×n table R of exchange rates, such that one unit of currency ci buys R\[i,j\] units of currency cj. Devise and analyze an algorithm to determine the maximum value of R\[c1,ci1\]⋅R\[ci1,ci2\]⋯R\[cik−1,cik\]⋅R\[cik,c1\] Hint: think all-pairs shortest path.

My understanding is this is asking to find the longest simple cycle (LSC) on a directed weighted (complete?) graph. There is a reduction from longest simple path to LSC, so this would be NP-hard. It seems strange that the problem gives a hint, so maybe it's asking something else?.

# Answer
The question is at least poorly worded, since it does not specify $k \leq n$ or require a simple cycle. So any positive-value arbitrage cycle can be "pumped" to generate a cycle with unbounded positive value.

If we add the requirement that the cycle is simple, then finding the simple cycle with the maximum product of the weights is equivalent to finding the simple cycle with the maximum sum of the logarithms of the weights, which is indeed the NP-hard Longest Simple Cycle problem.

Usually, these arbitrage questions ask to find *a* cycle with positive return, if one exists. This can be done by negating the logarithms of the weights and checking for negative cycles. This question asks for the *best* cycle, though.
> 2 votes

---
Tags: algorithms, graphs, shortest-path, weighted-graphs
---


# Question
Title: is AVL tree is better than heap for sorting purpose?
for sorting n elements what is better to use AVL tree or heap data structure and why? Can someone explain in brief?

# Answer
Both of them will work, and both of them support insertions${}^1$ and deletion${}^2$ of the minimum element in $O(\log n)$ worst-case time (where $n$ is the number of elements currently in the data structure).

It really depends what you mean by "better". An AVL tree will have the additional binary-search-tree property that the heaps do not have, and this allows to quickly support other operations (in addition to returning the ones above). For example you can quickly search for any element in the tree (both for its value and its rank). Indeed, the typical use of AVL trees is to implement a dictionary.

Since there isn't really any reason to use an AVL tree for sorting (they are a bit more complex to implement than an heap), you could stick with an heap. See also: heapsort.

---

${}^1$ Notice that constructing an AVL tree of $n$ elements by repeated insertions takes $O(n \log n)$ time. You can also construct an heap by repeated insertions in $O(n \log n)$ time but, since the arrangement of the elements in an heap is more relaxed than a BST, this can actually be improved to $O(n)$. For the purpose of sorting this doesn't really matter since its complexity will be subsumed by the one of the subsequent $n$ deletions.

${}^2$ Deletions are not really necessary if an AVL tree is used. Since an AVL tree is a BST, it suffices to return the elements in the same order as they are considered by a symmetric traversal of the tree.
> 3 votes

# Answer
No it is not. They both have the same running time but the heap is way lighter for a couple of reasons. For the asymptotic running time, note that a heap can be built in linear time meanwhile applying $n$ operations of extract min takes a total of $O(n \log n)$. On the other hand, constructing an AVL tree requires $O(n\log n)$ operations meanwhile traversing it to construct a sorted array takes only linear time. Hence, both have a total running time of $O(n \log n)$.

However, a heap has a way smaller constant factor compared to all the rotations happening in the construction of an AVL-tree. Even though the depth of an AVL-tree is $O(\log n)$, it comes with a huge constant factor compared to the depth of a heap which is at most $\left\lfloor \log n \right\rfloor + 1$.

More importantly, a heap is very cache-friendly and can be very easily implemented in an array. On the other hand, I can imagine building an AVL-tree in an array is quite cumbersome.
> 1 votes

---
Tags: data-structures, sorting, heap-sort, avl-trees
---


# Question
Title: How to prove Exact cover problem is NP Complete using Vertex Cover problem?
Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from Vertex Cover.

# Answer
You can reduce from vertex cover in cubic graphs since it is known to be $\textrm{NP}$-hard. Let $G=(V,E)$ be the graph in the instance of vertex cover and, for $v \in V$, call $E\_v = \\{ (v,u) \mid (v,u) \in E \\}$ the set of edges incident to $v$ in $G$.

Fix $1 \le k \le |V|$ and construct an instance of the exact cover problem as follows:

* The elements to be covered are those in $E$ plus $k$ additional elements $x\_1, \dots, x\_k$.
* There are $7k$ sets for each vertex $v \in V$, namely all sets $X \cup \\{x\_i\\}$ for $X \in 2^{E\_v} \setminus \\{ \emptyset \\}$ and $i=1,\dots,k$. Let $S\_v$ be the collection of such sets for $v$.
* Finally, there are $k$ sets $\\{x\_1\\}, \\{x\_2\\}, \dots, \\{x\_k\\}$.

If there is an exact cover $C$ for this instance, then we must have $|C| \le k$ (since each set contains one of $x\_1, \dots, x\_k$) and hence there is a vertex cover of $G$ of size at most $k$. Namely: $\\{ v \in V \mid S\_v \cap C \neq \emptyset\\}$.

Suppose now that there is a vertex cover $C$ of $G$ with at most $k$ vertices. Let $C=\\{v\_1, \dots, v\_\ell \\}$. We now show that the above exact cover instance admits an exact cover. Arbitrarily assign each edge $(u,v)$ of $G$ to one of the vertices in $\\{u,v\\} \cap C$. For a vertex $v\_i \in C$, let $A\_i$ be the set of edges assigned to $v\_i$. For $i\>\ell$ let $A\_i = \emptyset$. The sought exact cover contains all sets $A\_i \cup \\{x\_i\\}$ for $i=1,\dots, k$. Notice that if $A\_i \neq \emptyset$ then $A\_i \cup \\{x\_i\\} \in S\_v$.

To conclude the proof you just need to observe that exact cover belongs to $\textrm{NP}$ since the cover itself is a certificate that can be checked in polynomial-time.
> 1 votes

---
Tags: algorithms, complexity-theory, np-complete, nondeterminism, p-vs-np
---


# Question
Title: How to convert the left recursive grammar into right recursive grammar
I have a grammar: $A\rightarrow Aa|bB|c$

The above is the left recursive grammar. I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to avoid left recursive.

Some body please guide me how to do that.

# Answer
Consider where "a" terminals can appear in a string produced by this grammar. Based on that, you should be able to split the "A" nonterminal up to make a right-recursive grammar that matches the same strings.

(Also, your "B" nonterminal appears to be missing...? Or just has no productions?)
> 1 votes

---
Tags: formal-grammars, left-recursion
---


title: Computing hash of a compound key

text:
# Question
Title: Computing hash of a compound key
Why is the initial value of `hash` 17 and not 0?

```
/**
 * Returns an integer hash code for this date.
 *
 * @return an integer hash code for this date
 */
@Override
public int hashCode() {
    int hash = 17;
    hash = 31*hash + month;
    hash = 31*hash + day;
    hash = 31*hash + year;
    return hash;
}

```

https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Date.java.html

# Answer
There is no compelling reason that I'm aware of. The hash algorithm would also work about as well with an initial value of 0, as far as I can see.
> 1 votes

---
Tags: hash
---


title: Worst case runtime for binary search

text:
# Question
Title: Worst case runtime for binary search
The run time of binary search is O(log(n)).
log(8) = 3
It takes 3 comparisons to decide if an array of 8 elements contains a given element. It takes 4 comparisons in the example below.

python2.7

```
def binary_search(a_list, item, comparisons_inner=0):
    low = 0
    high = len(a_list) - 1

    while low <= high:
        mid = (low + high) / 2
        guess = a_list[mid]
        comparisons_inner += 1
        if guess == item:
            return mid, comparisons_inner
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None, comparisons_inner

my_list = [5, 8, 11, 15, 21, 23, 100, 223]
index, comparisons = binary_search(my_list, 223)
print(index, comparisons)

```

log(8) \< 4
Why is the run time of binary search O(log(n)) despite the 4 comparisons it takes in the example above?

# Answer
Your algorithm makes $\lfloor \log n \rfloor+ 1$ comparisons for an array of length $n$, which is at most $2 \log n$, which is $O(\log n)$. Hence, $\lfloor \log n \rfloor+ 1 = O(\log n)$.

In more detail, recall that the big-O notation subsumes constant factors. A function $f(n)$ is said to be $O(\log n)$ if there exist positive constants $c$ and $n\_0$ such that $f(n) \le c \log n$ for all $n \ge n\_0$. In our case, we want to prove $\lfloor \log n \rfloor +1 = O(\log n)$. To prove the existence of positive constants $c$ and $n\_0$ satisfying the desired condition, observe that $\lfloor \log n \rfloor+ 1 \le \log n + \log n = 2 \log n$, for all $n \ge 2$. So we can take $c = 2$ and $n\_0 = 2$.
> 1 votes

---
Tags: runtime-analysis, binary-search
---


# Question
Title: Min-plus matrix multiplication implementation
I had a look at topological sorting where they mention a possible parallel algorithm that relies on matrix multiplication, but using min-plus matrix multiplication:

> One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, **using min-plus matrix multiplication** with maximization in place of minimization. The resulting matrix describes the longest path distances in the graph.

I had a look at min-plus matrix multiplication, but can't quite understand what $min$ is doing in the description of the algorithm:

> Given two $n \times n$ matrices $A = (a\_{ij})$ and $B = (b\_{ij})$, their distance product $C = (c\_{ij}) = A \star B$ is defined as an $n \times n$ matrix such that $c\_{ij} = \min\_{k=1}^n \\{a\_{ik} + b\_{kj}\\}$. This is standard matrix multiplication for the semi-ring of tropical numbers in the min convention.

What is the $min$ function here? When I think of $min$, I think of it like $min(1, 2) = 1$. But how does that make sense if we are doing a sum?

So, in my implementation of *regular* matrix multiplication, finding the value for $c\_{ij}$ looks like this:

```
    for j := 0; j < p; j++ {
        sum := 0

        for k := 0; k < m; k++ {
            sum += A[i][k] * B[k][j]
        }

        C[i][j] = sum
    }

```

But if I add a $min$ (or a $max$) function here, like so:

```
...
sum += min(A[i][k] * B[k][j])
...

```

That doesn't make sense at all.

So how would one describe an implementation of the $min$ function described in the article for min-plus matrix multiplication? It is the $min$ of what?

# Answer
In the tropical semiring, the "addition" operation is the minimum, and the "multiplication" operation is addition.

If you want to adapt matrix multiplication to the tropical semiring, you literally need to replace every occurrence of $+$ with $\min$, and $\*$ with $+$.

To this effect, look at the line:

> sum+= A\[i\]\[k\]\*B\[k\]\[j\]

Let's rewrite it "properly", as:

> sum= sum+A\[i\]\[k\]\*B\[k\]\[j\]

Then, in the tropical semiring, this becomes:

> sum= min(sum, A\[i\]\[k\]+B\[k\]\[j\])

And you're done.
> 4 votes

---
Tags: algorithms, mathematical-programming, matrix
---


# Question
Title: How to prove that this language is not regular?
Given a language $L$ over the alphabet { `0`, `1`, `[`, `,`, `]` } where if $x \in L$ then $x$ is of the form $\[x\_0, \dots, x\_n\]$, in which each of the $x\_i$ represents unique binary strings (so $x\_i = x\_j$ only when $i=j$). Prove that this is not a regular language.

Here is what I have. I have used the pumping lemma.

Suppose $L$ is a regular language. Let $M$ be the DFA that accepts $L$. Let $p$ be the pumping length of $L$. Given $x = \[x\_0,\dots,x\_p\] \in L$ we see that $|x| \> p$ so pumping lemma applies, so $x = UVW$ where $|UV| \< p$, $|v| \> 0$, and $UV^iW \in L$.

Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x\_i$. Therefore we have reached a contradiction, which shows that $L$ is not a regular language.

Is this a correct proof? If not, what can I do to improve it?

# Answer
> Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x\_i$. Therefore we have reached a contradiction, which shows that $L$ is not a regular language.

This is not necessarily true. Suppose $x=\[0^p, 0^{p-1}, \dots, 00, 0\]$. If $V$ is of length $k\<p$ and entirely in $0^p$, we get $UVVW = \[0^{p+k}, 0^{p-1}, \dots, 00, 0\]$ which is still in $L$.

Normally when doing a proof using pumping lemma, we try to use a more specific $x$ such that the pumping lemma fails. Like this:

Suppose $L$ is regular and let $p$ be its pumping length. We choose $x=\[0^p, 0^{p-1}, \dots, 00, 0\]\in L$. By the pumping lemma, we can split it into 3 parts $UVW$. Noticed that $V$ cannot include the symbol `[` otherwise $UVVW$ contains two `[` which is not in $L$. Then, the choices for $V$ is either $0, 00, \dots, 0^{p-1}$. Note that it cannot be $0^p$ because it is subject to the constraint $|UV|\leq p$. No matter what we choose for $V=0^k$, the string $UW=\[0^{p-k}, 0^{p-1}, \dots, 0\]$ is not in $L$ because $0^{p-k}$ must be one of $0, 00, \dots, 0^{p-1}$. Hence $L$ is not regular.
> 2 votes

# Answer
Your proof doesn't quite work because of the last step: "Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x\_i$."

The problem with this is that the substring being pumped is not necessarily an entire $x\_i$. It could be the middle of an $x\_i$, which would not necessarily invalidate the string's membership in $L$.

Using the pumping lemma makes this problem more complicated than it needs to be, in my opinion. Using the Myhill-Nerode theorem instead gives a proof that the language is not regular in about two sentences, and does a better job of intuitively explaining why the language can't be regular (namely, that DFAs have finite memory, so it can't remember all the $x\_i$ to ensure that they are unique).

Here's the tweet-length proof if you want it. Don't write this on your homework, though, or you'll get points off for not showing your work.

> Suppose that $L$ is regular; by Myhill-Nerode, there exist two distinct prefixes "$\[x\_1,$" and "$\[x\_2,$" in the same equivalence class. But "$\[x\_1, x\_2\]$" is in $L$ and "$\[x\_2, x\_2\]$" is not in $L$, contradicting them being in the same equivalence class.
> 1 votes

# Answer
Your proof is incorrect because it is possible in some cases for $UVVW$ to belong to $L$. For example, take $x = \[000,001,010\]$ and $V =,00$. Then $UVVW = \[000,00,001,010\]$ whose binary strings are unique.

Here is proof that $L$ is not regular. By way of contradiction, suppose there exists a DFA $M$ with $p$ states that recognizes $L$. Consider the $p+1$ inputs $s\_1 = \[0^1, s\_2 = \[0^2, \ldots, s\_{p+1} = \[0^{p+1}$, where $s\_i$ consists of the open bracket followed by $i$ $0$'s.

Observe that the DFA $M$ reaches different states for these different inputs. For if the DFA $M$ reached the same state for input $s\_i$ and also input $s\_j$ for some $i \ne j$, then it must make the same decision (of accepting versus nonaccepting) after concatenation of the same suffix $,0^i\]$, i.e. both $\[0^i, 0^i\]$ and $\[0^j, 0^i\]$ must be accepted or both must be rejected by the machine. However, the first string is rejected by the machine and the second string is accepted by the machine.

This implies the DFA must have at least $p+1$ states, a contradiction. Since $p$ was arbitrary, we have proved that there is no DFA (with a finite number of states) recognizing $L$.

The proof above is self-contained and from scratch, but if you want to learn about this proof method look up the Myhill-Nerode theorem and how one can show a language to be nonregular by giving an infinite set of pairwise distinguishable prefixes (the $s\_i$'s above).
> 1 votes

---
Tags: formal-languages, regular-languages
---


title: Is $n^{1/\log \log n} = O(1)$?

text:
# Question
Title: Is $n^{1/\log \log n} = O(1)$?
> Is $n^{1/\log \log n} = O(1)$ ?

Suppose that $n^{1/\log \log n} = c$ where $c$ is constant.

Taking logs of both sides,

$$\frac{1}{\log \log n}\log n = \log c.$$

I am not able to spot an error. Please help

# Answer
> 7 votes
The function $n^{1/\log \log n}$ tends to infinity, since $$ n^{1/\log\log n} = e^{\log n/\log\log n}, $$ and $\log n/\log \log n \longrightarrow \infty$.

# Answer
> 2 votes
In your last step, a contradiction is reached since (by L'Hopital) $$\lim\_{n\to\infty}\frac{\log n}{\log\log n}=\lim\_{n\to\infty}\frac{1/n}{1/(n\log n)}=\lim\_{n\to\infty}\log n$$ and $\log$ is unbounded.

# Answer
> 1 votes
There isn't an error. You supposed that $n^{1/\log\log n}$ is constant and you derived the contradiction that $\log n/\log\log n$ is constant. Therefore, your supposition must be false.

It would have been better to have written that $n^{1/\log\log n}\leq c$ for all $n$, since you're really trying to show that the function is bounded above by a constant, not that *is* constant.

# Answer
> 0 votes
By way of contradiction, suppose $n^{1/ \log \log n} = O(1)$. Then, by definition of the big-O notation, there exist positive constants $c$ and $n\_0$ such that $n^{1/\log \log n} \le c$ for all $n \ge n\_0$. Taking log of both sides, we obtain that $\frac{\log n}{ \log \log n}$ is at most some constant $c' = \log c$ for all sufficiently large $n$. But this is impossible because it can be shown (for eg by L'Hopital's rule) that $\lim\_{n \rightarrow \infty} \frac{\log n}{\log \log n} = \infty$.

---
Tags: asymptotics
---


# Question
Title: Time complexity to sort 100 elements by using selection sort?
What will be time complexity for sorting 100 elements using selection sort answer given is O(1), but selection sort time complexity is O(n^2) in every case so how O(1)?

# Answer
> 1 votes
That's because you only have a constant number of elements, in this case 100. In other words, $100^2 = O(1)$, i.e., you do a constant amount of work. Usually it is more interesting to analyze the scalability of an algorithm with a growing input size $n$.

# Answer
> 0 votes
Let the constant $c\_i$ denote the cost of the $i$th statement of your selection sort algorithm. If $n$ is the number of elements in the input array, it is possible to show that the running time of the selection sort algorithm is a quadratic function $T(n) = an^2+bn+c$ for some constants $a, b, c$. Hence, selection sort is $O(n^2)$. Now if you fix $n=100$, then $T(100)$ is some constant independent of $n$ and hence is $O(1)$.

Recall that $f(n) = O(1)$ if there exists a constant $c \> 0 $ such that $f(n) \le c$ for all sufficiently large $n$. Every constant function is $O(1)$. For example, $5000 = O(1)$ because $5000 \le 5000 \cdot 1$ and so we can take $c = 5000$.

---
Tags: data-structures, time-complexity, sorting
---


# Question
Title: Difference between $a^{2n} b^n$ and $n_a(w) = 2n_b(w)$
I have encountered two questions related to npda:

1. Construct an npda for $L\_1 = \\{a^{2n} b^n \mid n \geq 0\\}$ as a language over $\Sigma = \\{a,b,c\\}$.
2. Construct an npda for $L\_2 = \\{w \in \\{a, b, c\\}^\* \mid n\_a(w) = 2n\_b(w)\\}$.

What is the difference between the above two languages?

# Answer
> 1 votes
The usual definition is that $n\_a(w)$ refers to the number of $a$s in $w$.

Based on this definition, $L\_1$ consists exactly of words that begin with an even number of $a$s followed by half as many $b$s (no $c$s are permitted). Therefore, you have $\varepsilon, aab, aaaabb, aaaaaabbb,... \in L\_1$.

Whereas $L\_2$ consists of words containing an even number of $a$s and half as many $b$s (in *any order* and with an arbitrary number of $c$ in between).

Thus every word in $L\_1$ is also in $L\_2$ (formally $L\_1 \subseteq L\_2$), but there are words in $L\_2$ that are not in $L\_1$:

* For some $n \geq 0$, consider words of the form $b^n a^{2n}$. They are in $L\_2$, because they contain an even number of $a$s and half as many $b$s, but if $n \> 0$, then it does not match $a^{2n} b^n$, because the $a$s come after the $b$s. You have $\varepsilon, baa,bbaaa,bbbaaaaaa,... \in L\_2$, but $baa,bbaaa,bbbaaaaaa \notin L\_1$.
* The same argument applies for $w = (aab)^n$. You have $\varepsilon, aab,aabaab,aabaabaab \in L\_2$, but $aabaab,aabaabaab \notin L\_1$.
* A word can have an even number of $a$s and half as many $b$s and also contain $c$s. For example, $a^{2n} b^n c \in L\_2$. But the words in $L\_1$ by definition only contain $a$s and $b$s.

# Answer
> 1 votes
In both languages, each string must have twice as many $a$'s as $b$'s. For a string to be in the first language, it must satisfy the additional condition that all the $a$'s occur before any of the $b$'s. So $aba$ does not belong to the first language and does belong to the second language.

---
Tags: formal-languages, context-free
---


# Question
Title: What are the basics of CS i should know,before I start my journey into machine learning
I am myself a `non-cs graduate` and would love to be a `machine learning engineer`.

I have learned to code and know the basics of `Machine learning` as well. Now I would like to know what "`basics of CS`" I should learn to be completely job ready.

I sometimes have difficulties reading CS documentations and don't know how programs and computers work in background, I am also naiver on topics like *memory management, operating systems, networking, electronics stuff like microprocessor, compiler design etc*. Are these all necessary for my transition to AI? If they are, would you please recommend me a `short learning path or books or videos`. I hope I wouldn't need to go deep in these areas. Thanks

# Answer
> 2 votes
Computer science is a very broad subject area, and many of its sub-disciplines have little or no overlap with others. For example, knowing the basics of operating systems design, compiler design or microprocessor design are unlikely to help you make progress in machine learning (although each one is an interesting topic in its own right).

Machine learning is a sub-topic of artificial intelligence, so the most closely related disciplines are other sub-topics of artificial intelligence such as pattern recognition, data mining, knowledge representation and natural language processing. Some knowledge of the theory of data structures and algorithms would also be useful. Outside of computer science itself, you will also need some knowledge of mathematical topics such as probability, statistics and mathematical optimisation.

---
Tags: machine-learning, reinforcement-learning, books, learning-theory
---


# Question
Title: Simplify the asymptotic expressions $O(n^2 + n) + \Omega (n^2 + n \log n)$
How can it be shown that the expression $O(n^2 + n) + \Omega (n^2 + n \log n)$ simplifies to $\Omega (n^2)$? Why is it not $\Theta(n^2)$?

# Answer
> 0 votes
The expression that you write means what can we say about $f(n) + g(n)$ such that $f(n) \in O(n^2 + n)$ and $g(n) \in \Omega(n^2 + n \log n)$. First, we can rewrite the inputs to $f(n) \in O(n^2)$ and $g(n) \in \Omega(n^2)$. Hence, the we can say $f(n) + g(n) \in \Omega(n^2)$.

However, we cannot say $f(n) + g(n) \in \Theta(n^2)$. As a counterexample, $f(n) = n$ and $g(n) = n^3$.

Anyhow, if you want to say there is a function $f(n)$ such that it is in $O(n^2 + n)$ and also in $\Omega(n^2 + n \log n)$, you're right. Although if $f(n) \in \Theta(n^2)$, it is in $\Omega(n^2)$ as well.

# Answer
> 0 votes
Remember that $f(n) = O(g(n))$ when $\lim\sup\limits\_{n\rightarrow\infty}$ $\frac{f(n)}{g(n)}$ $ \< \infty \space \space$ and that $f(n) = \Omega(g(n))$ when $\lim\inf\limits\_{n\rightarrow\infty}$ $\frac{f(n)}{g(n)}$ $ \> 0 $.

From the above expression we can eliminate both $n$ and $nlogn$ because $n^2 \> n \> nlogn $. We are left with $O(n^2) +\Omega(n^2)$. Since the first is a superior limit and the last an inferior limits, we know that the expression reduce to his inferior limits.

---
Tags: asymptotics
---


title: $2d+1$ threshold for error detection

text:
# Question
Title: $2d+1$ threshold for error detection
Why is the threshold for detecting errors $2d+1$? I am aware that the question has been asked before, for example here, but the answers provided didn't really justify why the formula contains $+1$.

So why is there $+1$ in the equation?

# Answer
Let's look at a simple, concrete example where $d=4$. Suppose the codebook is $C = \\{0000,1111\\}$. This means the sender transmits either the codeword $0000$ or the codeword $1111$ during each block of communication, and no other binary strings are transmitted. For example, to transmit a $0$ bit, the string $0000$ is transmitted, and to transmit the $1$ bit, the string $1111$ is transmitted. The hamming distance of this code is $4$.

Suppose the sender transmits one of the above two codewords, and suppose the receiver gets $0010$. Then the receiver knows that the transmitted codeword has been corrupted by the noisy channel because the received vector is not either of the two transmitted codewords (only $0000$ or $1111$ could have been transmitted). Thus, the receiver is able to "detect" that an error has occurred (i.e. that the transmitted codeword has been corrupted by the noisy channel). If the noisy channel flips up to any $3$ bits, the receiver will detect an error, but if the channel flips all $4$ bits - say $0000$ was transmitted and $1111$ was received - then the receiver will wrongly conclude that the received codeword $1111$ was the transmitted codeword. Thus, we say this code can detect up to $3$ bit errors because the minimum distance between any two codewords in this codebook is at least $4$. If only up to $3$ bits are flipped, then such an error can't convert one codeword into another because any two codewords differ in at least $4$ positions. More generally, if the hamming distance is $d$, then up to $d-1$ errors can be detected.

Suppose again that the received vector is $0010$. Then, the receiver will detect that an error has occurred. But can it correct the error and figure out which codeword was transmitted? The receiver can use the nearest-neighbor decoding rule, which says if the received vector is not one of the codewords (in the codebook), then make the decision that the transmitted codeword is the one closest (in hamming distance) to the received vector. This is a good rule when the probability of a bit getting flipped is small. Because $0000$ is closer to $0010$, the receiver concludes that $0000$ was transmitted. But what if the received vector is $0011$? Then, both $0000$ and $1111$ are equally distant from the received vector. The receiver will not be able to correct $2$ errors (it can only detect that an error has occurred, but not correct it).

Ideally, we would like any two codewords to differ in a large number of positions. Define the sphere of radius $d$ centered around a codeword $x$ to be the set of all codewords which differ from $x$ in at most $d$ positions. For example, the sphere of radius $1$ centered at $0000$ is the subset of vectors $\\{0000,1000, 0100, 0010, 0001\\}$. Because the sphere of radius $1$ centered at $0000$ and the sphere of radius $1$ centered at $1111$ are disjoint, the nearest-neighbor decoding rule will decode correctly if the number of bit flips is at most $1$. The above code of hamming distance $4$ can correct up to $\lfloor (4-1)/2 \rfloor = 1$ error. Because of the possibility that the received vector can be $0011$ or $0101$, etc, the code can't correct $2$ errors.

More generally, if the spheres of radius $d$ centered at any two codewords in the codebook are disjoint, then the nearest-neighbor decoding rule will correct up to $d$ errors. For any two such spheres to be disjoint, any two codewords must differ in at least $2d+1$ positions. If there exist some two codewords differing in $2d$ or fewer positions, then these two codewords could both be the nearest-neighbors of some received vector. Visualize in your mind the picture in $3$ dimensions of two spheres of radius $d$, which end up being disjoint because the distance between their centers is $2d+1$.

Thus, if the hamming distance is $2d+1$, the code can correct up to $d$ errors. Or, if the hamming distance is $d$, the code can correct up to $\lfloor (d-1)/2 \rfloor$ errors.
> 2 votes

# Answer
A code $C$ can detect up to $d$ errors if the minimal distance between two codewords of $C$ is at least $d+1$. Suppose that the sent codeword was $x$, and the received one was $x'$, which differs from $x$ by at least 1 and at most $d$ symbols. Since the minimal distance is at least $d+1$, $x'$ is not a codeword, and so the error is detected.

A code $C$ can correct up to $d$ errors if the minimal distance between two codewords of $C$ is at least $2d+1$. Suppose that the sent codeword was $x$, and the received one was $x'$, which differs from $x$ by at most $d$ symbols. I claim that $x$ is the only codeword which differs from $x'$ by at most $d$ symbols, and so $x'$ can be corrected to $x$. Otherwise, there would be another codeword $y$ which differs from $x'$ by at most $d$ symbols, but then $x,y$ would differ by at most $2d$ symbols.
> 0 votes

---
Tags: error-correcting-codes
---


title: Useless production

text:
# Question
Title: Useless production
Kindly consider the following productions. How can I identify a useless production?

```
S->aS|A|C

A->a

B->aa

C->aCb

```

Somebody please guide me. Zulfi.

# Answer
Starting from $S$ it is impossible to generate a sentential form that contains the nonterminal $B$.

This is easy to see since:

* $S$ only has productions whose body contain $S$ itself, $A$ or $C$.
* $A$ has no nonterminals in the body of its productions.
* $C$ has only $C$ itself in the body of its productions.

This means that the production $B \to aa$ is useless.
> 1 votes

# Answer
*Useless symbols* are those that do not appear in any derivation from the start variable of some terminal string. If you similarly define *useless productions* to be those productions that are not used in any derivation from the start variable of a terminal string, then observe that the production $B \rightarrow aa$ is useless because $B$ is not reachable from the start variable, and the production $C \rightarrow aCb$ is also useless because it does not derive any terminal string - once we use this production, the nonterminal symbol $C$ will be contained in every further sentential form, and so we can't obtain a string containing only terminal symbols.
> 1 votes

---
Tags: formal-grammars
---


title: Context-free grammar for binary words

text:
# Question
Title: Context-free grammar for binary words
I am supposed to create CFG for this languague:

$L= \\{w : w \in \\{a, b\\}^\*, |w\_b| = 3k, k \geq 0 \\}$

where $|w\_b|$ is count of terminals $b$ in $w$.

**For example:**

aa - OK, no 'b'

abb - wrong, only 2 'b'

aaabbb - OK, 3 times 'b'

aababbb - wrong, 4 times 'b'

abbbbbaaa - wrong, 5 times 'b'

abababbbaaab - OK, 6 times 'b'

and so on...

I can't come up with any solution. Any advice?

---

My goal is to design context-free grammar, **not automaton or regular expression** (i don't know how to design automatons or RE yet).

What about CFG

```
G = {{S,A}, {a,b}, R, S}

```

where R rules are:

```
1] S -> S A b A b A b A S
2] S -> A
3] S -> ε
4] A -> a A
5] A -> ε

```

Explanation:

rule 2\] is for cases when there are no 'b' symbols in w

rule 3\] is for case of empty string

rule 4\] is for adding 'a' symbols between 'b', e.g. baaaabab, babaab

rule 5\] is for cases, when there are multiple 'b' next to each other, e.g. abbbaaa

---

Is this CFG ok?

# Answer
> 1 votes
**Hint**: A string with exactly one $a$ would look like this: $$ (\text{any number of } b's)\\,a\\,(\text{any number of } b's) $$ and a grammar to generate the language of these strings is $S\rightarrow AaA,\ \ A\rightarrow bA\mid \epsilon$.

Generalize.

# Answer
> 1 votes
Your language is regular. You can create a DFA or NFA for your language, and then convert it mechanically into a regular grammar. As an example, here is a grammar for the language of all even-length words over $\Sigma = \\{a\\}$, which was generated this way from a DFA with two states:

$$ \begin{align\*} &S \to aT \mid \epsilon \\ &T \to aS \end{align\*} $$

The two nonterminals $S,T$ correspond to the two states; the starting symbol corresponds to the initial state; the productions $S \to aT$ and $T \to aS$ correspond to the transition function; and the production $S \to \epsilon$ corresponds to $S$ being an accepting state.

# Answer
> 0 votes
Your CFG looks correct, but it can be made simpler. The production $S \rightarrow SAbAbAbAS$ can be replaced by $S \rightarrow SbAbAbA$ (i.e. remove the first $A$ and last $S$) . Given any string containing $3k$ $b$'s $(k \ge 1)$, the suffix of the string starting with the third $b$ from the right can be generated by the $bAbAbA$ part. For example, if the string is $aababababbab$, then the rightmost $bbab$ can be generated from $bAbAbA$.

---
Tags: context-free, formal-grammars
---


# Question
Title: Enumerate all paths of length 3 in a given tree T
Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.

# Answer
Let $T$ be a tree on $n$ vertices. Root $T$ in an arbitrary vertex $r$ and let $p(v)$ denote the parent of vertex $v \neq r$ in $T$. For $v \in V$, let $C(v)$ denote the children of $v$ in $T$.

A path $\langle v\_1, v\_2, v\_3, v\_4 \rangle$ of length $3$ in $T$ is of exactly one of the following two forms (when the path's traversal direction is ignored):

* **Type A:** $p(v\_1) = v\_2$, $p(v\_2) = v\_3$, $p(v\_3) = v\_4$, or
* **Type B:** $p(v\_1)=p(v\_3)=v\_2$ and $p(v\_4)=p(v\_3)$.

To enumerate all paths of type $A$ it suffices to perform a DFS visit of $T$. When a vertex $v$ at depth at least $3$ is encountered, return the path $\langle v, p(v), p(p(v)), p(p(p(v))) \rangle$. This takes $O(n)$ time overall.

To enumerate all paths of type $B$, perform a DFS visit of $T$ and when a vertex $v$ at depth at least $2$ is encountered, return all the paths of the form $\langle v, p(v), p(p(v)), u \rangle$ where $u \in C(p(p(v))) \setminus \\{ p(v) \\}$. This requires time $O(n + P)$, where $P$ is the number of paths of type $B$ in $T$.

Overall you can enumerate all the paths of length $3$ in $T$ in time $O(n + P)$.

Notice that $\Omega(n)$ is a lower bound on the time needed by any algorithm since you need to read the input tree. A bad case in which $P=0$ but you still spend $\Theta(n)$ time is a star.
> 1 votes

---
Tags: algorithms, graphs, trees
---


# Question
Title: Implementing reliable pairwise average in distributed systems
Consider an asynchronous and unreliable distributed system. Each node has a value. Suppose that p and q are two neighbor nodes of the system (p\_val and q\_val are the values of p and q respectively). p and q want to compute the average of their values and change their values to the average. If one node changes its value to the average, the other node should change as well. This problem is called distributed reliable pairwise average.

> Question: Is it possible to implement distributed reliable pairwise average? or it is impossible?

---

I think that it is impossible. Please consider the following simple protocol:

1. Each node sends its value to the other node.
2. Each node after receiving the value of the other node changes its value to the average.

Suppose that p receives q\_val but q doesn't receive p\_val due to occurring a link-failure, so if p changes its value to the average, it is not correct. It seems that they need to send acknowledgments. If they start to send acknowledgments, they enter an endless loop.

# Answer
Full reliability is simply not possible in (distributed) systems; at some point of fractional system failure you reach a level where system state and/or data is no longer recoverable. You should consider that this is dependent not only on node failure, but also on data distortion (bits might flip as they travel across the network, etc.). As a result, you can reach very high levels of certainty about correctness but it's very difficult if not impossible to guarantee it.

One of the most well known examples of this is the Byzantine Generals/Byzantine Fault problem, which deals with consensus in networks (https://en.wikipedia.org/wiki/Byzantine\_fault).
> 1 votes

---
Tags: distributed-systems
---


# Question
Title: 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:

1. Let the loop variant be the "iteration" relation, i.e. the reflexive transitive closure of the transition relation.
2. Since the loop always terminates, the loop variant has no infinite descending chains.
3. 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:

1. Is there a model of ZF where a program always terminates but has no loop variant?
2. If the answer to 1 is *yes*, then what is the weakest choice principle that, when added to ZF, changes the answer to *no*?
3. 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?

# Answer
> 4 votes
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).

---
Tags: computability, logic, loop-invariants, termination
---


# Question
Title: Can timestamp be used in synchronization of processes having Race Condition?
I am wondering whether **timestamp** can be used to solve process synchronization problem, when race condition occurs?
Below is an algorithm for **entry** as well as **exit sections** for every process who wants to enter in critical section. Entry section uses FCFS (First Come First Serve) technique to give access to critical section.

```
    interested[N] is shared array of N integers where N is number of processes.

    // This section executed when process enters critical section.
    entry_section (int processNumber) {
        interested [processNumber] = getCurrentTimeStamp ();  // Gets the current timestamp.
        index = findOldestProcessNumber (interested);         // Find the process number with least timestamp.
        while (index != processNumber);
    }

    // This section executed when process leaves critical section.
    exit_section (int processNumber) {
        interested [processNumber] = NULL;
    }

```

According to me, this algorithm satisfies all conditions for synchronization, i.e., Mutual Exclusion, Progress, Bounded waiting and Portability. So, Am I correct?

Thanks for giving your time.

# Answer
> 1 votes
The short answer is yes, since what you're essentially doing with the timestamps is making all potentially conflicting processes sequential. Of course, in sequential systems there are no race conditions (a bit of a simplification, but nevertheless). In what way does timestamping processes differ from creating locks on resources, which is the current standard in parallel computation? You may want to reflect on what the real issues with race conditions are. Maybe this definition from Wikipedia might help:

> "A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events."

So the primary issue to consider is what happens when you don't have control over the process(es) that cause(s) the race condition.

---
Tags: operating-systems, synchronization
---


# Question
Title: Why can't we prove decidability of $L= \{ \langle M \rangle : M$ accepts $ \epsilon \}$ with a configurations graph?
Since every deterministic Turing Machine can be translated to a graph of configurations such that $M$ accepts a word $w$ iff there is a path from the initial configuration that matches $w$ to an accept configuration, we can define a decider $D$ for $L$ such that:

$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

Though this seems simple and valid (to me), there is a well-known result showing that $L$ is undecidable. I can't figure out what is the flaw in the proof and will be happy for any help to figure it out

# Answer
> 2 votes
> $D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

The problem here is that, even if you define the TM so that there are only finitely many accepting configurations (e.g. by requiring that the final tape be empty), *the configuration graph itself may have infinitely many vertices*. This is because the configuration includes the contents of the tape, and the tape contains however many cells the TM has written to, which is in general unbounded.

Every vertex can be identified by a finite string (the configuration description), and each vertex is connected to only a finite number of other vertices (determined by the transition relation), so the graph is *locally finite*. But the whole graph may still have an infinite number of vertices that are reachable.

# Answer
> 0 votes
> then builds the configurations graph and checks if the initial configuration of ϵ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

The above is just another way of saying: run $M$ on $\epsilon$ and wait to see if the machine halts or not. This, hovewer, is not deciding the language $L$.

---
Tags: turing-machines, computability, undecidability
---


# Question
Title: Number of automorphism for clique of 6 vertices minus two non adjacent edges
How many automorphism does a clique with 6 vertices have, when we take two edges from it (two edges that don't have the same vertex)?

I thought the answer is 6\*(n-2)! Number of automorphism for a full graph Kn is n!. Clique can be seen as a full graph since all of the vertices must be connected to each other. Since we take away two edges I think it should be (n-2)!. And it has to be multiplied by 6 because there are 6 vertices all together so was still permutate them.

Is this correct? How to find this correctly? What if there are N vertices?

# Answer
> 1 votes
It's not hard to check that $(1\\; 2)$, $(1\\;3)(2\\;4)$, and $(5\\;6)$ are all automorphisms of the graph. Considering the degrees of vertices, this shows that the orbits of the automorphism group $G$ are $\\{1,2,3,4\\}$ and $\\{5,6\\}$. According to the orbit stabilizer theorem, $|G| = 4|G\_1|$. Once again, it's not hard to check that $(3\\;4)$ and $(5\\;6)$ are automorphisms in $G\_1$, and consider degrees and the property of being connected to $1$ shows that the orbits of $G\_1$ are $\\{3,4\\}$ and $\\{5,6\\}$. It is not hard to check that all 4 permutations respecting these orbits are in $G\_1$, and so $|G\_1| = 4$. We conclude that $|G| = 16$.

Informally, $1$ can get mapped to any of $1,2,3,4$. Assuming that $1$ gets mapped to itself (without loss of generality), we see that $2$ has to get mapped to itself, $3$ to one of $3,4$, and $5$ to one of $5,6$. These are the only constraints, so in total there are $4\cdot 2\cdot 2 = 16$ automorphisms.

# Answer
> 0 votes
The automorphism group of a graph and of its complement are isomorphic. Hence, the problem is to find the automorphism group of the complement graph, which consists of $2$ disjoint edges and two isolated vertices. The two isolated vertices can be permuted among themselves (in $2$ ways). The two edges can be permuted among themselves (in $2$ ways) and the endpoints of each edge can further be permuted (in $2^2=4$ ways). Thus, the total number of automorphisms is $2 \times 2 \times 2^2 = 16$.

The structure of the automorphism group can also be obtained. The group of the two isolated vertices is $S\_2$. The group of the two independent edges is the wreath product of $S\_2$ with $S\_2$. Hence, the automorphism group of the graph is $S\_2 \times (S\_2~wr~S\_2)$.

More generally, it is shown in \[Frucht, On the groups of repeated graphs. Bull. Amer. Math. Soc, 55 (1949), 418-420.\] that if a graph $G$ consists of $k$ connected copies of some graph $H$, then the automorphism group of $G$, denoted $Aut(G)$, is the wreath product of $S\_k$ with $Aut(H)$, which contains automorphisms of the individual copies as well as automorphisms that permute the copies among themselves.

---
Tags: algorithms, graphs
---


title: Print to video permutations

text:
# Question
Title: Print to video permutations
You want to print vectors with n elements, where:

* the first element can have the values: e1.1, e1.2, e1.2;
* the second element can assume the values: e2.1, e2.2, e2.3;
* ...;
* ...;
* the nth element can assume the values: en.1, en.2, en.3.

I should print all possible vectors; eg:

{e1.1, e2.1, en.1 ...};

{e1.2, e2.1, en.1 ...};

etc. etc.

Someone could indicate an algorithm making use of while/for loop to print these vectors?

Thanks so much!

# Answer
The idea is to think of your output as representing a number in a mixed base. The $i$th digit has base $b\_i$, where $b\_i$ is the number of options for the $i$th element. You can then print all possible vectors essentially by implementing a counter. I'll let you work out the details.
> 1 votes

# Answer
Here's a python program that does this for $n=4$. In the $i$th iteration, each vector of length $i$ is appended with one of three possible strings to create vectors of length $i+1$.

```
n = 4
res = [["e1.1"], ["e1.2"], ["e1.3"]]
for i in range(2, n+1):
    temp = res[:]   #make a copy of current list
    res = []
    for x in temp:
        res.append(x + ["e" + str(i) + ".1"])
        res.append(x + ["e" + str(i) + ".2"])
        res.append(x + ["e" + str(i) + ".3"])

print(res)

```
> 0 votes

---
Tags: algorithms, permutations, loops
---


# Question
Title: Can maximal number in poset be more than one?
In poset maximal number is defined as: An element 'a' belongs to 'A 'is called a maximal number if there is no element 'c' in 'A' such that a is less than c.

but it again says that there can be more than one maximal number. How can it be possible?

# Answer
> 3 votes
Yes, it is possible for a poset to have more than one maximal element.

For example, let $R$ be the divides relation on the set $A = \\{1,2,3,5\\}$. Then $2$ is a maximal element of the poset $(A, R)$ because none of the other elements is a multiple of $2$. If you draw the Hasse diagram of this poset, you'll find that there are no elements "above" $2$ in this diagram, and so $2$ is a maximal element. Similarly,$3$ and $5$ are also maximal elements. These three elements are pairwise incomparable (similar to how apples and oranges are incomparable).

The terminology partially-ordered set is justified because the elements can't be totally ordered by being placed on a straight line, whereas the set of all integers or the set of all real numbers are totally ordered under the $\le$ relation.

# Answer
> 1 votes
Consider for example the poset of all subsets of $\\{1,2,3\\}$ of size at most $2$ ordered according to inclusion. The maximal elements in this poset are $\\{1,2\\},\\{1,3\\},\\{2,3\\}$.

For an even more striking example, every antichain (set in which no two elements are comparable) is a poset in which all elements are maximal and minimal. For example, consider the poset of all subsets of $\\{1,2,3\\}$ of size *exactly* $2$ ordered according to inclusion. There are three elements $\\{1,2\\},\\{1,3\\},\\{2,3\\}$, and all are maximal and minimal.

It is always possible to add a maximal element to a poset so that it contains a unique maximal element. See if you can figure out how.

---
Tags: discrete-mathematics
---


# Question
Title: Alternative to Hamming distance for permutations
I have two strings, where one is a permutation of the other. I was wondering if there is an alternative to Hamming distance where instead of finding the minimum number of substitutions required, it would find the minimum number of translocations required to go from string a to string b.

My strings are always of the same size and I know there are no errors/substitutions.

Example:

```
1 2 3 4 5
3 2 5 4 1

```

This would give me two:

```
3 2 5 4 1 (start)
-> 3 2 1 4 5
-> -> 1 2 3 4 5

```

If this is already implemented in R that would be even better.

# Answer
> 4 votes
Finding the minimal distance is called the "Sorting By Translocation" problem. Part of an abstract from a paper:

"Given two signed multi-chromosomal genomes Pi and Gamma with the same gene set, the problem of sorting by translocations (SBT) is to find a shortest sequence of translocations transforming Pi to Gamma, where the length of the sequence is called the translocation distance between Pi and Gamma. In 1996, Hannenhalli gave the formula of the translocation distance for the first time, based on which an $O(n^3)$ algorithm for SBT was given. In 2005, Anne Bergeron et al. revisited this problem and gave an elementary proof for the formula of the translocation distance which leads to a new $O(n^3)$ algorithm for SBT."

What's called "translocation" here is called a transposition, i.e., a permutation of exactly two elements in a list, in traditional combinatorial language.

# Answer
> 0 votes
We need to find the minimum number of transpositions that take one string $a$ to another string $b$, where $a, b$ are permutations. It looks like you are looking for the minimum distance between two given vertices $a, b \in S\_n$ in the complete transposition graph, which is the Cayley graph of $S\_n$ generated by the set of all transpositions.

---
Tags: terminology, string-metrics, permutations, edit-distance
---


# Question
Title: Mixed integer non convex optimization problem
If an optimization problem is mixed integer non-convex problem. The optimal solution by applying brute exhaustive search is infeasible to be applied in practice due to high complexity i.e. $O(N^K)$. Can we say that it's NP hard problem? If yes, can someone explain with more details.

# Answer
> 0 votes
No, you can't infer NP-hardness from such an algorithm. Indeed, why should the existence of a slow algorithm mean that there can't be a fast algorithm?

For example, consider the problem of sorting $n$ integers. Suppose the first algorithm I give you is a one that tries all $n!$ permutations. Can we now safely conclude that this problem is somehow hard? Of course not and we know that there are many much faster polynomial-time algorithms for the problem.

---
Tags: optimization
---


# Question
Title: Algorithm for real time Coordinate smoothing
So I get new Coordinates every 10ms even with RTK fixed precision, they jump between 1-3cm. The Coordinates are the current Position of my Vehicle

I have a Vehicle using these Coordinates to follow a drawn Path.

Now as the Coordinates Jump, the Vehicle tries to follow them and is driving in curves instead of a straight line sometimes more sometimes less depending on how sensitive the steering is.

My question now is, what Algorithm is capable of "smoothing" incoming Coordinates in real-time to avoid the jumping around?

Kalman-Filter / Douglas-Peucker or something else?

Does a prediction of the next current position help? -- Maybe with the help of an IMU?

# Answer
> 1 votes
A Kalman filter is a reasonable choice for this. It is useful for tracking the movement of an object, as it can be used with a model for the physics of the movement of an object.

---
Tags: algorithms, robotics
---


# Question
Title: Classification accuracy based on top 3 most likely classifications
My goal is to recommend jobs to job seekers based on their skill set.

Currently I'm using an SVM for this, which is outputting one prediction, e.g. "software engineer at Microsoft". However, consider this: how significantly different are the skill sets of a software engineer at Microsoft and a software engineer at IBM? Probably not significantly different. Indeed, by inspection of my data set I can confirm this. Hence, the SVM struggles to discriminate in situations like this, of which there are many in my data set, and my classification accuracy is about 50%.

So I had an idea.

In SK Learn, once you've trained some model, you can compute the probability a particular input X belongs to each class.

So for each input X in my test set, I took the the top 3 most likely classifications. Then I tested whether or not the correct label was in the top 3 predictions. If it was, then I considered the prediction to be correct. In doing so, the classification accuracy increased to over 80%.

So my question is: is this a valid approach to measuring classification accuracy? If it is, then does it have a name?

In my mind, it is valid given my intended application, which is to recommend a selection of jobs to a job seeker, which are relevant to their skill set.

# Answer
This is called top-3 accuracy. See https://stats.stackexchange.com/q/95391/2921, https://stackoverflow.com/q/37668902/781723, https://stats.stackexchange.com/q/156471/2921. Sure, you can use it. Whether top-1 accuracy or top-3 accuracy is better correlated with user satisfaction will depend on your particular application and on your users.
> 0 votes

---
Tags: machine-learning, classification, performance, svm
---


# Question
Title: Assignment Problem -- finding the $k$ agents with the best assignment
I have a question that I have been thinking about. Suppose we have $n$ agents, $m$ tasks, a cost matrix with $M\_{ij}$ being the cost of agent $i$ performing task $j$, and are given a value $k \leq n$. How can we find the $k$ unique agents, who when each optimally allocated a unique task, result in a minimum total cost? Can this be related to the assignment problem? Thank you very much for any guidance or assistance.

# Answer
The assignment problem can be extended to solve this problem. The regular problem without the $k$ restriction can be solved by building a Minimum Cost Maximum Flow network is as follow:

We have a source $S$ a sink $T$ and the corresponding bipartite graph in the middle. Note that each edge has two values $f/c$ which denote maximum flow allowed through this edge and cost of each flow unit. Now, the problem is that we want to allow at most $k$ units of flow from $S$ to $T$. To do this, just duplicate node $S$ into $S\_1$ and $S\_2$ and put an edge among them such that cost of each unit is 0 (no penalty) and maximum flow allowed is $k$. The new graph will look like this:

The minimum cost maximum flow from $S\_1$ to $T$ is the solution to the original problem for a fixed $k$.
> 3 votes

---
Tags: bipartite-matching, assignment-problem, bipartite-graph
---


title: Formal languages: What is $2n_c$?

text:
# Question
Title: Formal languages: What is $2n_c$?
I have got following question:

Determine whether the following language is context free or not: $$L = \\{ w \in \\{a,b,c\\}^\*: n\_a (w) = n\_b (w) = 2n\_c (w)\\}. $$

What is the meaning of $2n\_c$ in the above question?

# Answer
This language is not CFL.

Consider the language $L \cap a^\*b^\*c^\*$ . Assume that $L$ is CFL, now, as $ a^\*b^\*c^\*$ is regular and CFL are closed under intersection with regular languages, $L \cap a^\*b^\*c^\*$ would be CFL. But $L \cap a^\*b^\*c^\* = a^nb^nc^{2n}$, which is not context free (The proof is similar to this). Hence the contradiction!

Thus the given language is not CFL.
> 1 votes

---
Tags: formal-languages, context-free
---


# Question
Title: Are these two sensible and related or unrelated ways of regarding a logic system as a programming language?
When I am trying to understand logic programming languages e.g. Prolog, I am immediately confused by the following two ways of relating logic systems and programming languages or type systems.

1. In *Types and Programming Languages* by Pierce, Section 9.4 *Curry–Howard correspondence* on p109 has a table

Does it mean that a logic system is a programming language, where

* types are propositions and
    * values of a type are proofs of the proposition?
2. On the other hand, a logic system is described in a formal language that defines what a logic expression is. Can we view a logic system (e.g. the first order predicate logic system) as a programming language, where

* it has two types: Boolean type and function type, and
    * Each logic expression without a variable has Boolean type, so can be evaluated to a truth value. Each logic expression with any variable has Boolean function type, so its application to truth values for its variables can be evaluated to a truth value?

Are the above two views of a logic system as a programming language completely unrelated/orthogonal, or are they the same or can they be unified?

Thanks.

# Answer
> 1 votes
> Does it mean that a logic system is a programming language, where types are propositions and values of a type are proofs of the proposition?

Not necessarily, being both (logic systems and programming language) formal languages, there certainly is a certain degree of isomorphism between the two concepts, this translates into the fact that we can encode a logical system through a programming language and develop algorithms to identify proofs of the theorems of our logical system.

If you are interested in the similarities between logical propositions and types, I strongly suggest you take a look at Homotopy type theory.

# Answer
> 1 votes
The relationship between the two is related to intuistionistic logic vs. classical logic. When you add sufficiently powerful versions of the excluded middle law to Curry-Howard-style type systems, you can translate between propositions (types of sort `Prop`, which are inhabited if and only if they are provable) and Boolean values at will. Check out the list of excluded middle/proof irrelevance laws available in Coq for a jumping-off point.

---
Tags: programming-languages, logic, types-and-programming-languages
---


# Question
Title: LTL Logic Finally, Globally and Until to irreflexive Version
my professor said that we can transform the reflexive Finally, Globally and Until into irreflexive Finally, Globally, Until.

Can someone explain me this?

For irreflexive Finally we have $w \models F^+ \varphi$ if $\exists i \>= 1: w^{(i)} \models \varphi$ For irreflexive Globally we have $w \models G^+ \varphi$ if $\forall i \>= 1: w^{(i)} \models \varphi$ For irreflexive Finally we have $w \models \varphi\_1 U^+ \varphi\_2$ if $\exists i \>= 1: w^{(i)} \models \varphi\_2$ and $\forall j, 1 \leq j \< i w^{(i)} \models \varphi\_1$

# Answer
Sorry, I misread your question at first as wanting to express the irreflexive variant using the reflexive variant (which could be done with the next operator). You don't actually need the next for the other direction.

I'm making the following assumption: By $w^{(i)}$ you mean the suffix of $w$ starting at the $i$ symbol, so for $w = w\_0 w\_1 w\_2 \dots$, you have $w^{(i)} = w\_i w\_{i+1} w\_{i+2} ...$

Then for all $w \in L$, you have:

1. $w \models F\varphi \Leftrightarrow w \models \varphi \lor F^+ \varphi$.
2. $w \models G \varphi \Leftrightarrow w \models \varphi \land G^+ \varphi$.
3. $w \models \varphi\_1 U \varphi\_2 \Leftrightarrow w \models \varphi\_2 \lor (\varphi\_1 \land (\varphi\_1 U^+ \varphi\_2))$.

If you want to show this formally, it follows directly from the definitions:

For 1. you have:

$\begin{align\*}w \models F \varphi &\Leftrightarrow \exists i \geq 0: w^{(i)} \models \varphi \\ &\Leftrightarrow \exists i \> 0: w^{(i)} \models \varphi \quad \text{ or } \quad w^{(0)} \models \varphi \\ &\Leftrightarrow w \models F^+\varphi \text{ or } w \models \varphi \\ &\Leftrightarrow w \models \varphi \lor F^+\varphi \end{align\*}$

The argument for 2. is symmetric to 1.

For 3. you have (pay attention to $\leq$ vs $\<$):

$\begin{align\*}w \models \varphi\_1 U \varphi\_2 \Leftrightarrow & \exists i \geq 0 \forall 0 \leq j \< i: w^{(j)} \models \varphi\_1, w^{(i)} \models \varphi\_2 \\ \Leftrightarrow & \exists i \> 0 \forall0 \leq j \< i: w^{(j)} \models \varphi\_1 , w^{(i)} \models \varphi\_2 \quad \text{ or } \quad w^{(0)} \models \varphi\_2\\ \Leftrightarrow (& \exists i \> 0 \forall0 \< j \< i: w^{(j)} \models \varphi\_1 , w^{(i)} \models \varphi\_2 \quad \text{ and } \quad w^{(0)} \models \varphi\_1) \quad \text{ or } \quad w^{(0)} \models \varphi\_2 \\ \Leftrightarrow (&w \models \varphi\_1 U^+ \varphi\_2 \quad \text{ and } \quad w \models \varphi\_1 )\quad \text{ or } \quad w \models \varphi\_2 \\ \Leftrightarrow & w \models \varphi\_2 \lor (\varphi\_1 \land (\varphi\_1 U^+ \varphi\_2))\end{align\*}$

If you would have wanted to do the other direction, as I thought initially:

1. $w \models F^+ \varphi \Leftrightarrow w \models XF \varphi$
2. $w \models G^+ \varphi \Leftrightarrow w \models XG \varphi$
3. $w \models \varphi\_1 U^+ \varphi\_2 \Leftrightarrow w \models X(\varphi\_1 U \varphi\_2)$.

To show this formally, the argument would be similar to before.

When you combine both directions, this transformation is sometimes referred to as "unrolling", i.e. expanding $F \varphi \equiv \varphi \lor X F\varphi \equiv \varphi \lor X \varphi \lor XXF \varphi \equiv ...$ and $G \varphi \equiv \varphi \land XG \varphi \equiv \varphi \land X \varphi \land XXG \varphi \equiv ...$ etc.

Regarding your comment (not 100% sure if you were joking): $\lnot X$ is not $-1$ or "going backwards". You have $w \models \lnot X \varphi \Leftrightarrow w^{(1)} \not \models \varphi$. In other words, if you think in terms of Kripke structures and of $w$ as the vertex-label sequence of a path in this transition system, then $\lnot X \varphi$ means "in the next state, $\varphi$ does not hold".
> 1 votes

---
Tags: linear-temporal-logic, temporal-logic
---


# Question
Title: Find the closest string to a fixed set of strings
I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the fixed size). For this problem you can assume the strings only contain the characters 0-9, and if needed, the length will never be longer than 32 characters.

I measure closest by hamming distance, the distance between two strings is the number of places the two strings differ. I don't care about how ties are resolved, any string with the minimum distance is acceptable.

For example, with s1 = "123" and s2 = "321", the distance between them is 2. (All the pseudo code is in Python)

```
def distance(s1, s2):
    return sum(a != b for a, b in zip(s1, s2))

```

I can complete a query in $O(n)$ time where $n$ is the number of strings in the set. The idea would be to loop over each string in the set and compute the distance between it and the target. The answer is the (first, with this implementation) string with the smallest distance.

```
def query(table, target):
    return min(table, key=lambda t: distance(target, t))

```

Is there a way to do this in less than linear time? Can the set of strings be pre-processed to allow for a faster search?

---

Here is a testcase/example

```
target = '91814154'
table = [
    '91812315',
    '77403499',
    '57579618',
    '92354796',
    '23425335',
    '97722442',
    '01824154']

distances = [4, 8, 8, 6, 8, 7, 2]

```

So the answer is the string '01824154'.

# Answer
This is a nearest-neighbor problem, and there are a variety of algorithms for the problem. The simplest is a k-d tree, and there are more sophisticated data structures as well. Another approach is to use locality-sensitive hashing.

However, the effectiveness of these methods depends heavily on the dimension (i.e., on the length of the strings). Practical experience is that for dimension $\le 10$, these are better than the naive linear-time search, but for very high dimension, usually they perform no better than the naive algorithm. This occurs due to the curse of dimensionality. In your context, that means that if the strings are short and $n$ is large, these data structures will probably be effective, but if the strings are long, I would not expect too much hope.

In the special case where strings are long and you expect the nearest neighbor to have very low Hamming distance, whereas the distance to most other strings will be very large, then there are techniques you can use. For instance, you might look into shingling the strings into $n$-grams, storing the $n$-grams in a hashtable, and doing a lookup on each $n$-gram from the query string. You can view this as a form of locality-sensitive hashing for the Hamming distance. Another approach is to use bit sampling as a locality-sensitive hash; this should be easy to implement.

I also recommend taking a look at our questions in the topic, especially Why Is KD-Tree-based Nearest Neighbor Exponential in K?, Best data structure for high dimensional nearest neighbor search, Why is exact nearest neighbor search hard in high dimensional spaces?, What is the state of the art for k nearest neighbour search?.

We also have questions here about the harder problem of finding the nearest string, where nearest is measured by Levenshtein edit distance (e.g., Find all pairs of strings in a set with Levenshtein distance \< d, How to speed up process of finding duplicates/similar items in a large amount of strings?, How fast can we identifiy almost-duplicates in a list of strings?, Matching strings in one set to strings in another based on Levenshtein distance).
> 3 votes

---
Tags: algorithms, strings, string-metrics, nearest-neighbour
---


# Question
Title: How can I represent a set of graphs for learning purposes?
I have a network of labelled digraphs and a I need to perform a unsupervised learning algorithm on this data.

I am interested in embedding a network of description logic documents in a vector space using the ideas in the paper Co-embedding Attributed Networks (which is a variational auto-encoder). look at the picture:

The first step is to represent each digraph as a feature vector in a vector space.

I have googled a lot but I haven't found good explanations (I also search for supervised algorithms like support vector machine working on a set of labelled digraphs but google doesn't retrieve good results).

My question is: How can I represent a set of labelled digraphs into a vector for learning purposes? (this representation algorithm must have linear complexity)

# Answer
I don't think that paper is suitable for what you want to do. That paper generates an embedding of *nodes*: given a graph $G$ and a node $v$ in $G$, it outputs an embedding of $v$ (a representation of some properties of $v$). You want an embedding of the *entire graph*: given a graph $G$, you want to compute an embedding of $G$ (a representation of the entire graph $G$).

So, I suspect you'll need to consider a different approach. A usual starting point would be to do exactly what @Juho recommended: brainstorm some features that might be relevant (e.g., number of nodes, average degree), then map the graph to a feature vector (a list of the values of these features), and use the feature vector as your representation of the graph. More sophisticated methods are possible as well, but I'd recommend you start with the simple approach before diving into more complex methods, especially if you are not very experienced in this field.
> 1 votes

---
Tags: machine-learning
---