# Question
Title: Finding all zero sums of length m and checking for zero subsums on an abelian group (generalization of the sub sum problem?)
Let $G$ be an abelian group. We say that $G$ has property $V\_n$ if for every $m \> n$ and a list $L\subset G$ of $m$ elements s.t. $\sum\_{g\in L}g=0$ there is a proper subset $\emptyset\neq L'\subsetneq L$ s.t. $\sum\_{g\in L'}g=0$. We define $V(G)=\min\\{n \mid G \text{ has property }V\_n\\}$. This is part of the problem of finding an arithmetic characterization of number fields.

My current code utilizes memoization (probably badly) and takes around 6 seconds to verify $V(C\_2^6)=7$. It takes more than a minute to calculate $V(G)$ for most $G$'s with $V(G)\>7$.

I'm really not sure what the complexity of my code is, will share it at the bottom. I would appreciate suggestions for better algorithms, improvements of my code, new code etc. I would like to be able to calculate cases up to at least $V(G)=100$ and $|G|=1000$.

Here are some values for some abelian groups. With the notation $AB((a\_1,a\_2,...,a\_n))$ meaning there are $n$ generators $g\_1$ through $g\_n$ with the relations $a\_i\cdot g\_i = 0$. so $AB((2, 2))$ will just be $C\_2\oplus C\_2$:

```
{AB((2, )): 2,
 AB((3, )): 3,   AB((2, 2)): 3,
 AB((4, )): 4,   AB((2, 2, 2)): 4,
 AB((5, )): 5,   AB((3, 3)): 5,     AB((2, 4)): 5,     AB((2, 2, 2, 2)): 5,
 AB((6, )): 6,   AB((2, 2, 4)): 6,  AB(tuple([2] * 5)): 6,
 AB((7, )): 7,   AB((4, 4)): 7,     AB((2, 6)): 7,     AB((3, 3, 3)): 7, AB((2, 2, 2, 4)): 7, AB(tuple([2] * 6)): 7,
 AB((8, )): 8,   AB((3, 6)): 8,     AB((2, 4, 4)): 8,  AB((2, 2, 6)): 8, AB(tuple([2] * 4 + [4])): 8, AB(tuple([2] * 7)): 8,
 AB((9, )): 9,   AB((2, 8)): 9,     AB((5, 5)): 9,     AB((2, 2, 4, 4)): 9, AB(tuple([3] * 4)): 9, AB((2, 2, 2, 6)): 9, AB(tuple([2] * 5 + [4])): 9, AB(tuple([2] * 8)): 9,
 AB((10, )): 10, AB((2, 2, 8)): 10, AB((4, 4, 4)): 10, AB((3, 3, 6)): 10, AB((2, 2, 2, 4, 4)): 10, AB(tuple([2] * 6 + [4])): 10, AB(tuple([2] * 9)): 10}

```

Here is my code - not adding the code for an abelian group since the implementation is kinda trivial and doesn't take any significant runtime.

```
from itertools import combinations
from multiset import Multiset
from abeliangroup import AbelianGroup, group_values
from multiset import FrozenMultiset as fms

def relevant_powerset(iterable: tuple):
    for r in range(2, len(iterable) // 2 + 1):
        for combination in combinations(iterable, r):
            yield combination

def get_similar_sums(summands: tuple, zero_sum: tuple) -> set:
    diff_tuple = tuple(Multiset(summands).difference(Multiset(zero_sum)))
    return {fms(zero_sum), fms(diff_tuple)}

def has_zero_subsum(summands: tuple, g: AbelianGroup, memo: set) -> bool:
    for s in relevant_powerset(summands):
        if sum(s, start=g.zero) == g.zero:
            memo.update(get_similar_sums(summands, s))
            return True
    return False

def memoized_group_check(g: AbelianGroup, m: int, memo: set = None, summands: tuple = None) -> bool:
    assert m > 1 and g.maximal_element_order() <= m
    if memo is None:
        memo = set()
    if summands is None:
        summands = tuple()
    if fms(summands) in memo:
        return True
    if len(summands) > 0 and sum(summands, start=g.zero) == g.zero:  # this removes about a 1/4rth of the runtime.
        memo.add(fms(summands))
        return True

    if len(summands) == m - 1:
        summands = (*summands, -sum(summands, start=g.zero))
        if summands[-1] == g.zero or g.order_map[summands[-1]] < g.order_map[summands[-2]]:
            return True
        return has_zero_subsum(summands, g, memo)

    start = 0 if len(summands) == 0 else g.order_map[summands[-1]]
    for i in range(start, len(g.non_zero_elements)):
        new_summands = (*summands, g.non_zero_elements[i], )
        if has_zero_subsum(new_summands, g, memo):
            memo.add(fms(new_summands))
            continue
        if not memoized_group_check(g, m, memo, new_summands):
            return False
    return True

def memoized_calculate_v(g: AbelianGroup, max_tries: int = 10) -> int:
    meo = g.maximal_element_order()
    memo = set()
    for m in range(meo + 1, meo + max_tries + 1):
        result = memoized_group_check(g, m, memo)
        if result:
            return m - 1

def main():
    for g in group_values.keys():
        print(f"Calculated: V({g})={memoized_calculate_v(g)}\nExpected: V({g})={group_values[g]}\n")

```

# Answer
> 0 votes
I can propose an algorithm that will work for an arbitrary group. If $Z \subseteq G$ is a multiset of elements, let $\mathcal{S}(Z)$ denote the set of sums of non-trivial submultisets of $Z$, i.e., $$\mathcal{S}(Z) = \left\\{\sum\_{y \in Y} y \mid \emptyset \ne Y \subsetneq Z \right\\}.$$ Say that $Z$ is *annoying* if $0 \notin \mathcal{S}(Z)$.

I suggest that you enumerate first all annoying multisets of size 1, then all annoying multisets of size 2, then all annoying multisets of size 3, etc. Also, for each annoying set $Z$, keep track of $\mathcal{S}(Z)$.

Note that every annoying multiset $Z'$ of size $n+1$ can be expressed in the form $Z'=Z \cup \\{x\\}$ where $Z$ is an annoying multiset of size $n$ and $x \in G$, for some $Z,x$. Therefore, we can enumerate all annoying multisets of size $n+1$, as follows:

* For each annoying multiset $Z$ of size $n$:

+ For each $x \in G \setminus Z$:

    1. Set $Z' := Z \cup \\{x\\}$.
        2. Compute $\mathcal{S}(Z')$.
        3. If $0 \notin \mathcal{S}(Z')$, add $Z'$ to the list of annoying multisets of size $n+1$.

Notice that given $\mathcal{S}(Z)$, you can efficiently compute $\mathcal{S}(Z')$ in line 2, via the relationship

$$\mathcal{S}(Z') = \mathcal{S}(Z) \cup (x + \mathcal{S}(Z)) \cup \left\\{x, \sum\_{z \in Z} z\right\\}.$$

So, I suggest that you store $\mathcal{S}(Z)$ and $\sum\_{z \in Z} z$ alongside $Z$, in the list of annoying multisets.

Also, note that without loss of generality, we can pick any arbitrary total order $\<$ on $G$, and replace the inner loop with "For each $x \in G$ such that $x\>\max(Z)$:". This will speed up the algorithm a bit further.

As an optional optimization, if $n$ is much smaller than $|G|$, you could first check that all $n$-size submultisets of $Z'$ are annoying before computing $\mathcal{S}(Z')$: if any is not annoying, then $Z'$ is surely not annoying either, so you can continue on to the next $Z'$ without computing $\mathcal{S}(Z')$.

The search terminates once you reach a size that has no annoying multisets.

Finally, once the algorithm finishes, look for the largest $n$, such that there is no annoying multiset of size $\>n$ that sums to zero, and conclude that $G$ satisfies property $V\_n$. (You can of course keep track of this on the fly.)

You might be able to obtain significant constant-factor speedups by implementing in C and using optimized datastructures.

In the worst case, the running time to verify $V\_n$ could be $O(\left(\\!\\!{|G| \choose n}\\!\\!\right) \cdot |G|)$. In practice the running time will hopefully be less: we can hope that as $n$ gets larger, the number of annoying multisets will be far less than $\left(\\!\\!{|G| \choose n}\\!\\!\right)$.

---

For the specific case of $G=C\_2^k$, the answer is easy to derive without needing an algorithm: we are guaranteed that $C\_2^k$ satisfies property $V\_{k+1}$. Property $V\_{n-1}$ amounts to asking for $n$ so that, for every $n \times k$ boolean matrix $M$, if $(1,1,\dots,1) \in \text{Ker}\\, M$, then there exists another non-zero element in $\text{Ker}\\, M$. In this case, if you take $n \ge k+2$, then every $n \times k$ matrix has a kernel of dimension 2 or higher, hence has at least two different non-zero vectors. Therefore $V\_{k+1}$ is satisfied. It is easy to show that $V\_k$ is not satisfied, by an explicit construction (take the identity matrix together with the all-ones row).

I don't know whether there is some similar linear-algebraic methods that can be used to specialize for the case of $G=C\_{a\_1} \times \cdots \times C\_{a\_k}$.

---
Tags: algorithms, discrete-mathematics, python, subset-sum, group-theory
---


# Question
Title: Why does showing that a NP problem is not NP-complete implies P$\neq$NP?
I found in this answer that if a problem is shown to be NP but not NP-complete then P$\neq$NP. What is the argument to prove this statement?

# Answer
> 4 votes
This statement is false.

It is already known that the empty problem and the universal problem are in $\mathsf{NP}$ and are not $\mathsf{NP}$-complete (not even $\mathsf{P}$-complete).

However, what is true is that if $A\in \mathsf{NP}$ is not one of the two problems above, then $A$ is $\mathsf{P}$-hard. To prove this result, consider $a\in A$ and $b \notin A$ (those exist because $A$ is neither the empty nor the universal language). Then for any $B\in\mathsf{P}$, you can create the following function: $$f : x\mapsto \left\\{ \begin{array}{ll} a& \text{if }x\in B\\b&\text{otherwise}\end{array}\right. $$ Since $B\in \mathsf{P}$, $f$ is computable in polynomial time. Given the definition of $f$, $a$ and $b$, it is clear that: $$x\in B \Leftrightarrow f(x)\in A$$ That means that there is a polynomial time many-one reduction from $B$ to $A$.

Now if such a language $A$ is not $\mathsf{NP}$-complete, then $\mathsf{P}\neq \mathsf{NP}$ (because $A$ is $\mathsf{P}$-hard and not $\mathsf{NP}$-hard).

# Answer
> 1 votes
If a problem X is NP-complete that means by definition that I can take any problem Y in NP, and for every instance of Y I can construct an instance of X so that solving X allows me to solve Y in polynomial time.

Now assume P = NP. Then Y is in P, so I can solve it in polynomial time anyway - without having to construct an instance of X at all, or by constructing one and ignoring it completely when I solve the instance of Y. That means any problem in P is in NP and is NP-complete. NP complete just doesn't mean much; if P = NP then P = NP-complete.

Now we reverse the logic: If P = NP then every problem in NP is NP-complete, so if there is a problem in NP that is not NP-complete then P ≠ NP.

(And there is a problem: There are two problems (the empty problem and the complete problem) where all instances have the same answer, either all instances have the answer NO or all instances have the answer YES, so you cannot find two instances with different answers and things break down).

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


title: 'Someone' in first order logic

text:
# Question
Title: 'Someone' in first order logic
I have in the lectures a sentence in English, which I have to translate to First Order Logic.

> Someone who loves all animals loves all humans.

Textbook solution:

> ∀x.(is\_human(x) ⇒ is\_animal (x))
>
> ∀y.(is\_human(y) ∧ ∀z.(is\_animal(z) ⇒ loves(y, z)) ⇒ ∀z.(is\_human(z) ⇒ loves(y, z))))

My solution: I would have interpreted the someone as an existential quantifier.

> ∀x.(is\_human(x) ⇒ is\_animal (x))
>
> ∃y.(is\_human(y) ∧ ∀z.(is\_animal(z) ⇒ loves(y, z)) ⇒ ∀z.(is\_human(z) ⇒ loves(y, z))))

Why would this be wrong and why assuming that keywords like someone just comes with Existential quantifier is not always correct. Since I have learned that some word just introduce either existential or universal quantifier. But here in this example this is not the case anymore.

# Answer
The main issue here is that *someone* is ambiguous. You are correct in that usually, it translates to an existential quantifier. But it doesn't always.

To find an example, I Googled for "someone who * will also", which produced this page, with the sentence:

> Someone who really respects you will also respect your boundaries about sex \[...\]

We can read this in the existential way, as meaning

> There exists a person who really respects you, and who will also respect your boundaries about sex.

But clearly, that is not what is being meant here. The intended meaning is:

> Anyone who really respects you will also respect your boundaries about sex.

or in other words:

> Everyone who really respects you will also respect your boundaries about sex.

So in this case, *someone* translates to a universal quantifier.

Natural language is full of subtleties like this, which is the reason first order logic and other forms of logic were developed in the first place.

Now let's get back to the example you were given:

> Someone who loves all animals loves all humans.

This is ambiguous in the same way: it may be used to mean

> Someone exists who loves all animals and who also loves all humans.

but it is more likely to be used to mean

> Everyone who loves all animals also loves all humans.

Incidentally:

* both of your first order logic examples are missing an opening bracket, which makes them ambiguous, too;
* regardless of where you put those brackets, neither of them will mean either of these two things.

So there is some more work left for you to do.
> 1 votes

# Answer
Consider the following sentence:

> The green men live on Mars.

How would you translate this into first order logic?

Be sure to note that the sentence does not claim that any green men actually exist.
> 0 votes

---
Tags: first-order-logic
---


# Question
Title: Improper binary tree: maximum number of external nodes
The term *external* node is used as a synonym for a *leaf* node in the following. A binary tree shall be called proper if each node has either zero or two children. If it is not proper, it shall be called improper.

I need to determine the maximum number of external nodes in an *improper* binary tree. Here is my current attempt to solve this problem:

My intuition is that, in general, a binary tree has a maximum number of external nodes when it has at most one node with a single child. Consequently, my first step is to prove that assumption by induction.

**Proposition**: A binary tree $T$ of $n$ nodes achieves a maximum number of external nodes when it has at most one node that a single child.

**Base case** ($n=1$): A tree with just a root node has no nodes with just a single child and with one external node it also has the maximum number of external nodes for a tree with one node.

**Induction step**: Let $T$ be a tree with $n+1$ nodes which has at most one node with a single child.

If $T$ has a node with a single child, we remove that child to get a tree with $n$ nodes that has a maximum $m$ of external nodes. Adding the removed child node back to the tree, we still have a total number of $m$ external nodes, which also is the maximum for a tree with $n+1$ nodes (I think, for this reasoning to be fully valid, I would have needed to show that any tree with $n$ nodes that does not fullfill above requirement cannot have the same number of external nodes and have its external node count incremented when adding a node, but the tree we're looking at has not). Otherwise, removing an arbitrary external node gives us a tree with $n$ nodes which has exactly one node with just a single child. This tree has a maximum $m'$ of external nodes. Now, adding the removed node back to the tree, its external node count becomes $m'+1$ which has to be the maximum for a tree with $n+1$ nodes, as adding a node can only increase the number of external nodes by at most one.

As the next step, we can observe that an improper binary tree that satisfies the above-mentioned requirement becomes a proper binary tree when removing its only non-root node without a sibling (there has to be exactly one). We know that in a proper binary tree with $i$ internal nodes there are $e=i+1$ external nodes. When putting the removed node back into its place we get a tree with $i'=i+1$ internal nodes and still $e$ external nodes. Thus, we have a tree with a total of $n=i'+e=(i+1)+(i+1)=2\*i+2$ nodes. The number of internal nodes is $i'=(n-2)/2+1=n/2$ and the number of external nodes is $e=n/2$. Therefore, the maximum number of external nodes in an *improper* binary tree with n nodes is $n/2$.

Edit: I'm particularly unsure about the necessity of proving, by induction, the general structure of a binary tree that has a maximum of external nodes. I need help in writing a proof that is more formal and straight to the point.

# Answer
Your reasoning looks on the right track. However, somewhere along the way, it loses track of the correct parity of numbers and the exact number of nodes that have $1$ child. More case-by-case analysis may be in need.

---

Here is a simpler and clearer way with combinatorics flavor, i.e., using double counting to obtain relations between variables.

Suppose we have an improper tree with $n$ nodes.

* Let $n\_0$ be the number of nodes without children, i.e., external nodes.
* Let $n\_1$ be the number of nodes with $1$ children. $n\_1\ge1$ since the tree is improper.
* Let $n\_2$ be the number of nodes with $2$ children.

Then $n= n\_0+n\_1+n\_2$, since both sides are the total number of nodes in the tree.

The number of all child nodes, i.e., nodes in the tree that are children of another node is $n-1$ since every node except the root is a child node. On the other hand, the parent of a child node has either $1$ or $2$ children.

* the number of child nodes that have a parent with 1 children is $n\_1$,
* the number of child nodes that have a parent with 2 children is $2n\_2$.

Hence $n-1=n\_1+2n\_2$. Replacing $n\_2$ with $n-n\_0-n\_1$, we get $n-1=n\_1+2(n-n\_0-n\_1)$. So, $$2n\_0=n-n\_1+1.$$

* If $n$ is even, then the least possible value of $n\_1$ is $1$, which can be attained. The maximum number of external nodes $n\_0=\frac n2$.
* If $n$ is odd, then the least possible value of $n\_1$ is $2$, which can be attained. The maximum number of external nodes $n\_0=\frac{n-1}2$.
> 1 votes

---
Tags: data-structures, binary-trees
---


# Question
Title: Should I lookahead in the lexer or parser?
So I have this Recursive Descent Parser which outputs a Syntax Tree for arithmetic expressions.

While doing some reading, I learned that LL(1) grammars have a lookahead of 1 - I remembered using a lookahead so I grepped for it. But instead of finding it in my parser, I found it in the lexer.

```
case "*":
    if self._peek() == "*":
        self._next(2)
        return Token(SyntaxKind.TWO_STAR, self.position - 2, "*")
    self._next(1)
    return Token(SyntaxKind.STAR, self.position - 1, "*")

```

I use this to differentiate between the power(`**`) and multiplication operator(`*`).

So is this the right way to do things? Or should this code be in my parser? And is my grammar still LL(1) if I don't actually lookahead in the parser?

# Answer
"The right way to do things" depends on the specifics of the language.

The lexical syntax of most modern programming languages uses what is known as the maximal munch rule, which states that given more than one possibility as to what the next lexeme could be, choose the one that consumes more of the input. This inevitably means that a lexical analyser must backtrack (or look ahead) in general. An example is in in C++, where `0x0` is an integer constant expressed in hexadecimal, but `0x` is an integer literal followed by a suffix. To determine the next token, the lexical analyser must look past the `x` to see what follows it.

This is a design decision by programming language designers to make programming languages easier to implement. It's not the only option.

To answer your last question, any LL(0) grammar is also LL(1) even though it never *needs* the lookahead symbol. Either way, LL(k)-ness is a property of the grammar, and the grammar doesn't care where the terminal symbols came from.
> 1 votes

---
Tags: compilers, parsers, lexical-analysis
---


# Question
Title: (Directed) Graphs: Minimal Vertices Subset With No Outgoing Edges
I've been trying to study some graph algorithms and, as part of it, prove a bunch of graph theorems in order to practice my ability to do theoretical work with graphs.
Specifically, I've been trying to prove that given a directed graph $G$, the minimal (in terms of vertex count) non-empty subset of vertices with no outgoing edges (i.e, the minimal non-empty set $M$ that holds the property that for all $v\in M$ and $u\in G$, if there is an edge $(v,u)$ then $u\in M$) is one of the two:

1. The minimal (again: in terms of vertex count) strongly connected component with no outgoing edges, or
2. If there is no such SCC with an out-degree of zero: that set is the entire graph (or its set of vertices, rather).

Whichever direction I try taking, I end up feeling stuck very fast. For one example of a failed attempt: I've been trying to show #2; that is to say, analyze the case in which there are no SCC with an out-deg of 0 in graph $G$. For this case I assumed (intending to prove by contradiction) that there exists an $M$ which is a strict subset of $G$'s set of vertices and it holds the property described above. If $M$ is strongly connected then it is an SCC with no outgoing edges due to having the property, which is a contradiction to the assumption of this case, so $M$ is not strongly connected. Hence, there exist vertices $v,u\in M$ such that there is no path from $v$ to $u$. And... that's about as far as I could get. I'm not sure how to even begin proceeding from here. I want to show that $M$ has an outgoing edge somehow, but there appear to be so many end cases that I struggle with finding something common to bind them all together.

Would greatly appreciate a hint or outlines for how to proceed (or corrections if I've made any false claims) to help me get a grasp of the process here.

# Answer
There is no wonder you end up feeling stuck. Assume $G$ has at least one vertex. The second case, "there is no such SCC with an out-degree of zero" does not exist.

Recall if each strongly connected component (SCC) of $G$ is contracted to a single vertex, the resulting graph $\mathcal C(G)$, **the condensation of G is a directed** ***acyclic*** **graph**. Any leaf vertex (i.e., has no outgoing edge) in $\mathcal C(G)$ comes from an SCC of $G$ that has no outgoing edges, i.e., with an out-degree of zero.

---

Let us prove the desired theorem.

Suppose $G$ is a non-empty digraph and $S$ is a non-empty subset of vertices in $G$ that has no outgoing edges. For any vertex $v$ in $S$, let $\text{SCC}\_v$ be the strongly connected component of $G$ that contains $v$. ($\text{SCC}\_v$ is only defined for $v\in S$)

Since $S$ has no outgoing edges, if vertex $v$ is in $S$ and $(v,u)$ is an edge, $u$ must also be in $S$. Iterating this process, we see that any vertex that is reachable from $v$ by a (directed) path must also in $S$. Well, **any vertex is reachable from any vertex in an SCC**. Hence, all vertices in $\text{SCC}\_v$ must be in $S$. $$S=\cup\_{v\in S}\text{SCC}\_v$$

There must be an $\text{SCC}\_v$ that has no outgoing edges. That is because $\mathcal C(G)$ is acyclic. In particular, the subgraph of $\mathcal C(G)$ consisting of $\text{SCC}\_v$'s is acyclic. That subgraph has a leaf vertex, say $\text{SCC}\_w$, which means vertices in $\text{SCC}\_w$ do not have outgoing edges to vertices in any other $\text{SCC}\_v$. Since there is no outgoing edges from vertices in $S$ to vertices outside $S$, vertices in $\text{SCC}\_w$ do not have outgoing edges in $G$.

If $S$ is minimal among all no-outgoing-edges subsets of vertices, then $S$ should be the only $\text{SCC}\_v$ in it that has no outgoing edges. Then $S$ should be the minimal SCC that has no outgoing edges.
> 2 votes

---
Tags: graphs, proof-techniques, directed-graphs, connected-components
---


# Question
Title: Showing NP-completeness of a graph problem with vertex capacities
The problem: Given an undirected graph G = {V, E}, a source-vertex s, and each vertex having a "capacity" between 0 and |V|, is there a tree which covers all vertices and does not extend from a vertex more times than its capacity allows, while also not covering every edge? Demonstrate that it is NP-complete.

An example graph with a source can be seen below, and an example solution, with each vertex not having more edges extend from it than its capacity would allow.

While showing it is in NP is trivial, performing a reduction from a known NP-complete problem to show this problem is NP-hard is where I am having some difficulty. I am having some suspicions that reducing a problem like vertex cover might prove easiest, but I am quite stuck here.

# Answer
You can transform each instance of the hamiltonian cycle problem (finding a cycle that visits each vertex exactly once) into an instance of your problem.
Given a hamiltonian cycle problem with a graph $G=(V,E)$, you can apply the reduction described here to turn the graph $G$ into a graph $f(G)$ for the hamiltonian path problem, which is the same as your problem if you restrict the capacity of each vertex to 1. This reduction also gives you a source.
You can map the set of instances of the hamiltonian cycle problem to a subset of the instances of your problem, solving these in polynomial time would solve the hamiltonian cycle problem. This proves your problem is $\mathsf{NP}$-hard.
> 0 votes

---
Tags: graphs, np-complete, reductions, np
---


# Question
Title: Word ladder problem for words with different length
Is there some one who know any algorithm for ***word ladder problem*** with words of ***different length***?

Actually we have some strings with same length and some strings with one length longer but not from any size(any size means: one string with size 10 and one string with size 1000).

any link or advise is acceptable.

my solution is this: build a graph with strings in the nodes and nodes are connected if their strings can be converted to each other just by changing one letter, then using BFS.

word ladder problem

# Answer
> 1 votes
Your algorithm that runs breadth-first search (BFS) on the graph built with words as nodes and pairs of words that differ by one letter as edges is the natural algorithm to solve the problem, whether the words are different lengths or not.

I would just call call your algorithm as a BFS algorithm. It is classic application of BFS to search for the shortest paths between two nodes of a graph where the length of a path is simply the number of its edges.

If we let the BFS algorithm run until all nodes has been visited, then it will be able to find all shortest paths between a source node and all other nodes.

You can find some detailed comparison between BFS and Dijkstra algorithm for shortest path in a graph here.

# Answer
> 0 votes
The BFS algorithm still works with some changes. You'd basically have to pad an extra character in all the places. For instance, if there's no word of the same length to move from the word "hot", you check for words of length 4 characters. For this, you'd have to check all 26 characters in 4 positions. `[x]hot`, `h[x]ot`, `ho[x]t`, `hot[x]`

Check for the presence of the words from these transformations and add them to your queue. You'd basically have to do this for all lengths between `beginWord.length` and `endWord.length`

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


# Question
Title: How to handle epsilon production in CLR(1) parsing?
Given the following grammar:

1. S -\> A
2. A -\> AB
3. A -\> ϵ
4. B -\> aB
5. B -\> b

Check whether it is CLR(1) or not.

I have drawn the canonical itemsets as well as the parse table. But I'm not sure whether it is actually correct or not. I have tried searching for some similar examples that have epsilon productions but could not find any. Could someone please help me out?

# Answer
$\varepsilon $ is a representation of an empty string. Since it derives literally nothing, it is as good as having scanned the complete production, with the corresponding item set $A\rightarrow \cdot$ and would trigger a $reduce$ action on respective lookahead.
> 2 votes

---
Tags: compilers
---


# Question
Title: Construct a DFA with reduced states equivalent to 10 + (0 + 11)0*1
I have found this question in a book. I could convert it into its equivalent DFA. But the problem is with the "reduced state" part. I think the answer given in the book is wrong. What would be the DFA with its reduced states? I am giving the converting steps for reference:

The reduced DFA as given in the book:

So, what should the DFA with reduced states look like?

# Answer
Hope this helps! The answer in your picture is wrong because it has two transactions for symbol ' 1'. Which violates the property of DFA.
> 1 votes

# Answer
I think in your book results, first of all they reduce to FA and then they convert to DFA, just like NDFA to DFA. So that in the second picture actual result comes like this, but they forget to mention some input state in $q\_f$ and $q\_3$.
> 0 votes

---
Tags: finite-automata, regular-expressions
---


# Question
Title: what is the difference between triple sat and 3Sat?
I am trying to grasp the concept of triple sat compared to 3Sat. I understand that 3Sat has 3 literals for each for each clause. ${Triple-Sat} = \\{ \phi | \phi $ has at least three satisfying assignments $\\}$. Im just not exactly sure what the difference is between them.

# Answer
I don't see a connection between the two problems.

3SAT restricts the form or the formulas. A 3SAT formula can have any number of satisfying assignments. 3SAT asks for satisfiability (does there exist a satisfying assignment?)

Triple Sat is independent of the form of the formula, and simply asks a different question (do there exist three different satisfying assignments?)
> 1 votes

---
Tags: complexity-theory, computation-models
---


# Question
Title: Does T(n) = 2 · T(2n) + n apply to Master method?
I'm trying to apply the master method to the following recurrence:

$$T(n) = 2 \cdot T(2n)+n.$$

We have $a=2$ and $b=1/2$.

Also, $f(n)=n$ and $n^{\log\_b a} = n^{\log\_{1/2} 2} = n^{-1}$ since $\log\_{1/2} 2 = -1$.

So, case 3 applies since $f(n) = \Omega(n^{\log\_b a+\epsilon })$ , i.e., $n = \Omega(n^{-1+2})$ for some constant $\epsilon = 2$.

Now we have to check the regularity condition:

For some constant $c\<1$, it must hold that $af(n/b) \leq cf(n)$.

That is (substitute $a$ and $b$ in the above regularity condition):

* $2 \cdot 2n \leq c \cdot n$
* $4n \leq c \cdot n$

Which cannot hold for any $c \< 1$

Hence, we cannot apply case 3.

**Is the above a correct application of Master theorem for this recurrence? And what would be the solution?**

# Answer
From wikipedia

"Here $n$ is the size of an input problem, $a$ is the number of subproblems in the recursion, and $b$ is the factor by which the subproblem size is reduced in each recursive call $(b\>1)$"

---

So no. Master theorem can not be used to solve the given recurrence.
> 1 votes

# Answer
The Master Theorem is not deemed to be used with $b\<1$. But you can recast the recurrence as

$$T(2n)=\frac12T(n)-\frac n2$$

or

$$T(n)=\frac12T\left(\frac n2\right)-\frac n4.$$

So yes, the Master Theorem can be used.
> 13 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, recurrence-relation, master-theorem
---


# Question
Title: What happens when an internet connection is faster than the storage write speed?
If one attempted to download a file at a speed of 800 Mb/s (100 MB/s) onto a hard drive with a write speed of 500 Mb/s (62.5 MB/s), what would happen? Would the system cap the download speed?

# Answer
Many protocols, including TCP which is most widely used protocol on the Internet, use something called flow control. Flow control simply means that TCP will ensure that a sender is not overwhelming a receiver by sending packets faster than it can empty its buffer. The idea is that a node receiving data will send some kind of feedback to the node sending the data to let it know about its current condition. So, two way feedback allows both machine to optimally use their resources and prevent any problems due to mismatch in their hardware.

https://en.wikipedia.org/wiki/Flow\_control\_(data)
> 47 votes

# Answer
> what would happen?

* The bytes that cannot be written to the HDD in time would be buffered temporarily somewhere; very likely some of them would be buffered in the application that "converts" the network traffic into HDD traffic (i.e., your browser), and in cases of longer congestion, the lower level parts of the stack (i.e., the networking subsystem of your PC) would have buffers at lower levels as well, which would fill up until full.
* The information that the data is coming too fast would then propagate back to the sender in some fashion. In the case of TCP/IP, this would mean that there is a part of the TCP protocol which tells the sender that it should stop sending. The Wikipedia page on TCP/IP says it best when it says:
> Its \[TCP\] responsibility includes end-to-end message transfer independent of the underlying network, along with error control, segmentation, flow control, congestion control, and...
* At the end of the day, the "system" (not necessarily the computer of the receipient, but the total system consisting of sender, network and receipient) would indirectly "cap" the download speed. At no point is a "speed" variable in existance, though. Both network traffic and HDD traffic is block-based, that is, the delays between those blocks would get long enough (on the faster network side) until the net "speed" (throughput) is on average the same as the slower speed of your HDD.

> Would the system cap the download speed?

Not literally. A few dozen years ago, computers indeed communicated with synchronous speeds (i.e., modems with fixed speed settings). This is, at some relatively low level, also happening today; i.e., your DSL or cable modem will probably have some set speed at which it communicates with its direct physical uplink component. But in 2017, all of this is sufficiently complicated that almost all components are quite dynamic. In the good old days, modems were often physically only able to speak a certain speed, and that even had to be established before dialing in. There are (were) some network protocols like ATM which tried to get a synchronous wide-area network, but they didn't turn out so well, compared to TCP/IP.

Today, the effective speed is usually always implicitely reached by buffering, flow control, and such.

Also note that in your example there can even be more participiants. The network interface could have more work to do (other connections to your PC). Some part of the network along the way could be busy (a family member surfing or watching videos). The HDD might be doing 3 large file writes at the same time. So it would make no sense to specifically set a "speed" which could be capped.
> 13 votes

# Answer
File downloads (usually) happen over a protocol called TCP. In TCP, the sender doesn't send any data until the receiver is ready to receive it.

What will happen is that your computer will reserve some amount of RAM to hold the received data temporarily before writing it to your hard drive (this is called a buffer). Then it will ask the sender for just enough data to fill the buffer. As it receives data, it will start writing data from the buffer to the hard drive - however, it won't ask for more data while the buffer is nearly full.

The overall effect is the sender simply waits for the receiver to catch up before it continues sending.
> 2 votes

# Answer
Try to copy from SSD disk to HDD disk. What will happen? The connection will follow the slowest part. However, I have perceived network bottleneck. Get 10000 torrents to download "1kb/s". What happens? "Error on the disk".... Cause disk head on plate cannot go in so many different places per second. So, I think that HDDs have shown the age of their speed and people with fast internet speed may perceive occasional silent network bottlenecks due to that.

Note that internet network clients may cache files on memory. When Full (doing other things will make mem to get full quicker), both the net clients and other process of machine will be cached in Disk.If only one HDD disk is in place, and network traffic is going on this disk, and temporary cache on the same disk, then it will be further slowed down. A disastrous result.

Net cache on ram --\> Ram full -\> Cache on Disk -\> same disk that net traffic goes also make temp cache of ram -\> Further slowed down --\> Disastrous result --\> the whole system will be slowed down.

(It almost out of question to copy/move files on the same disk that receiving a lot of internet traffic).

SSds is a solution if safety protocols of data loss are in place. But they are sadly, very expensive yet.

So, i believe we live in an epoch that people with fast internet connection silently have Network speed data transfer loss due to plate-HDDs.

I have noticed my mobile phone can download much faster than my computer (SD cards are essentially SSD type).
> 0 votes

---
Tags: computer-networks
---


# Question
Title: Determining a faster/better approach for finding the pairs with minimum difference in an array
Wondering which approach is faster in terms of time complexity. In short, is having a single loop that clears out the vector every time there's a difference lesser than the minimum so far faster than having two separate loops: first determines the minimum difference, second appends the corresponding elements with minimum difference to the vector.

**First approach: (one loop)**

```
    std::vector<std::vector<int>> minDiffElements(std::vector<int>& arr)
    {
        std::vector<std::vector<int>> ans;
        sort(arr.begin(), arr.end());

        int minDiff = INT_MAX;

        for (int i=1; i<arr.size(); i++)
        {
            int diff = arr[i] - arr[i-1];

            if (diff < minDiff)
            {
                ans = {{arr[i-1], arr[i]}}; // reinitialize the array
                minDiff = diff;
            }
            else if (diff == minDiff)
            {
                ans.push_back( {arr[i-1], arr[i]} );
            }
        }
        return ans;
    }

```

**Second approach: (two loops)**

```
    std::vector<std::vector<int>> minDiffElements(std::vector<int>& arr)
    {
        std::vector<std::vector<int>> ans;
        sort(arr.begin(), arr.end());

        int minDiff = INT_MAX;

        for (int i=1; i<arr.size(); i++)
        {
            int diff = arr[i] - arr[i-1];
            if (diff < minDiff)
            {
                minDiff = diff;
            }
        }

        for (int i=1; i<arr.size(); i++)
        {
            int diff = arr[i] - arr[i-1];
            if (diff == minDiff)
            {
                ans.push_back({arr[i-1], arr[i]});
            }
        }
        return ans;
    }

```

Sample:

```
input:  [-1000000, 1000000]
output: [[-1000000,1000000]]

input:  [1,9,10,15,16]
output: [[9,10],[15,16]]

```

# Answer
> 0 votes
Assume an array of $n$ elements, containing $k$ groups with equidistant pairs, of decreasing difference, each including $m\_k$ pairs.

The first version performs $n-1$ comparisons and $k$ array initializations and $\displaystyle\sum\_{i=1}^k m\_i$ `push_back`. The worst case is $n-1$ comparisons and $k$ initializations plus $n-1$ `push_back`.

The second version performs $n-1$ comparisons, then $n$ comparisons and $m\_k$ `push_back`. The worst case is $2n-1$ comparisons, $1$ initialization and $n-1$ `push_back`.

The best cases involve both a single initialization and a single `push_back`. Without more information, the expected cases are unknown. That's about all that can be said.

---
Tags: time-complexity, c++
---


# Question
Title: relation based on a given partial order - does it have a name?
Let $P$ be a partial order on $X.$ Does the relation $E(P)=$ { $(x,y)\in (X\times X)\setminus P:P$ $\cup$ { $(x,y)$ } is a partial order on $X$ } have a name? If not, what's a good thing to call it?

# Answer
I searched online. Also checked several articles/papers on poset topological sorting and linear extension of poset. No name has been found for that relation.

$E(P)$ can be described as the set of ordered pairs compatible to $P$ or the set of ordered pairs extending $P$ minus $P$.

As the asker noted, if an ordered pair belong to an extension of $P$, it does not belong to $E(P)$ necessarily. For example, let $P$ on $X=\\{a,b,c\\}$ be defined by $a\prec b$. Then $P$ can be extended by letting $b\prec c$ and $a\prec c$. However, only letting $b\prec c$ does not extend $P$ to a bigger poset since $a\prec c$ would be missing. Hence we cannot describe $E(P)$ as the union of all extensions of $P$ minus $P$.

Some names that might be good for $E(P)$ are "the $P$-extending relation", "the extending relation of $P$", or "the $P$-compatible relation".

Once defined at the start of your post/article, the notation $E(P)$ could be the best name for that set, where $E$ is, as you intended probably, shorthand for **e**xtension or **e**xtending. For the sake of clarity in references, $\text{Ext}(P)$ might be better ($\text{Extension}(P)$ looks a bit long).
> 2 votes

---
Tags: terminology, partial-order
---


# Question
Title: Relationships between path width and clique size of interval graphs
I faced the following claim on wikiepdia about interval graphs (https://en.wikipedia.org/wiki/Interval\_graph):

> The pathwidth of an interval graph is one less than the size of its maximum clique.

I have thought a while about it, but don't come up with any argument/proof why the pathwidth is bounded by the size of the maximum clique-1. Is there a "simple" proof why that is so? Or is it just the fact, that any clique must be contained in some bag of a tree/path decomposition?

# Answer
> 0 votes
> Or is it just the fact, that any clique must be contained in some bag of a tree/path decomposition?

To prove the claim one should prove, both, that the pathwidth is at most the maximum clique size - 1 (e.g., by construction), and that there does not exists a clique not contained in a bag as you observed. For interval graphs, a construction proving the first part is pretty much given by their definition.

The second, and perhaps a less obvious part, can be proved, for example, by induction on the max. clique size `k`, and can be also found in many text books, for example, as Lemma 12.3.5 of the 3rd edition of Diestel's book.

A proof of the lemma for path decomposition goes by induction goes as follows.

Base Step: The claim holds for cliques of size `1` and `2`, which are just vertices and edges, respectively, by the definition. That concludes the base case.

Inductive step: Take a clique `K` of size `k>2`, and consider two cliques `Ku` and `Kv` of size `k-1` obtained by removing vertices `u` and `v`, respectively, from `K`. By the induction hypothesis both `Ku` and `Kv` as well as the edge `uv` are contained in their bags. Now, there are three cases to consider.

If any of these bags are the same then we are done, since then there exists a bag that contains the whole `K`.

If the bag `B` containing `uv` is between the bags containing `Ku` and `Kv`, by the definition of the path decomposition, `B` also contains all the vertices in the intersection of `Ku` and `Kv`. Therefore `B` contains the whole `K`.

If the bag `B` containing `uv` is NOT between the bags containing `Ku` and `Kv`. Then either the bag containing `Ku` is between `B` and the bag containing `Kv`, or the bag containing `Kv` is between `B` and the bag containing `Ku`. In the former, by the definition of the path decomposition, the bag containing `Ku` also contains `v` and therefore the whole `K`. In the latter, by the definition of the path decomposition, the bag containing `Kv` also contains `u` and therefore the whole `K`.

---
Tags: algorithms, graphs, decomposition, treewidth
---


# Question
Title: Shortest path algorithm on graphs with non-numerical weights
*TL;DR: Floyd-Warshall algorithm seems to also accept "is-a" and "has-a" relationships as edge weights. I want to know exactly why this is fine, and how to generalize this notion of other unusual weights.*

I also considered to ask this question on Mathematics Stack Exchange since it also contains significant portion of abstract algebraic aspect, but I decided to just post it here.

I've once tried solving a programming problem where, given a list of *is-a* and *has-a* relationships in an object-oriented program, one should determine what relationships given pairs of classes are in. According to the problem statement, for every triplet of classes A, B, and C:

* ***Is-a* is transitive**: A *is-a* C if A *is-a* B and B *is-a* C.
* ***Has-a* is transitive**: A *has-a* C if A *has-a* B and B *has-a* C.
* ***Is-a* is reflexive**: A *is-a* A always holds.
* A *has-a* C if A *is-a* B and B *has-a* C, or A *has-a* B and B *is-a* C.
* No cycles of *is-a* relationship exist. We'll ignore this restriction for the purpose of this question.

My solution involved a modified Floyd-Warshall algorithm where:

* There are four possible edge weights: *only is-a*, *only has-a*, *both is-a and has-a*, and *neither is-a nor has-a* (written as $i$, $h$, $ih$, $0$, respectively, from now on).
    + These "weights" are partially ordered: $0$ is greater than both $i$ and $h$, which are in turn greater than $ih$; $i$ is not comparable to $h$.
* `dist[i][j]` is initialized with $0$ (instead of infinity) if `i != j`, or $i$ (instead of zero) otherwise.
* The "inherit" and order-theoretic "meet" operator replaces addition and minimum, respectively.

The "inherit" operator can be thought to encapsulate the preceding transitivity properties, and is defined by the following table:

|  | $0$ | $i$ | $h$ | $ih$ |
| --- | --- | --- | --- | --- |
| $0$ | $0$ | $0$ | $0$ | $0$ |
| $i$ | $0$ | $i$ | $h$ | $ih$ |
| $h$ | $0$ | $h$ | $h$ | $h$ |
| $ih$ | $0$ | $ih$ | $h$ | $ih$ |

As you can see, this algorithm handles weights that are non-numerical, and not even totally ordered; yet it seems like it runs just fine, and it got my submission accepted! Since then, I always wondered why these unusual weights didn't invalidate the algorithm, and moreover, what kind of weight sets are acceptable.

More specifically, when it comes to regular integers and real numbers, Floyd-Warshall algorithm is known to handle all graphs with nonnegative weights, and even some graphs that contains negative weight, but not those with negative *cycles*. This is what I am interested in: **which sets of mathematical objects and operators disallow something that correspond to "negative cycles"**, thus compatible with the algorithm?

Currently I assume that they should be at least meet-semilattices, which generalizes the notion and minimum operator and shortest paths, and also monoids, which generalizes the notion of adding multiple segments of paths together.

I've thought of a number of additional hypotheses, but I couldn't verify any of them correct:

* No elements compare less than additional identity.
    + Counterexample: In the above example, $i$ is the "inheritancial identity", with $ih$ less than it. We've already seen that this one works nevertheless.
* No "infinite descent" sequence $A$ exists, where $A\_1 \> A\_1 + A\_2 \> A\_1 + A\_2 + A\_3 \> \cdots$.
* For every pair of elements $a$ and $b$, $a + b \ge min(a, b)$.
* There exists a greatest lower bound for every set of elements.

Partial order especially makes the analysis harder, because the result of minimum operator is no longer necessarily equal to any of its operands, thus "splitting" the path. Again with the above example, if A *is-a* B, A *has-a* C, B *is-a* D, and C *is-a* D, then according to the properties of these relationships, both A *is-a* D and A *has-a* D holds; the paths A-B-D and A-C-D *both* contribute to this shortest path length $ih$, and if we were to cut *any* of these, the "length" between A and D would be farther.

# Answer
I'm not an expert on this, so I recommend you double-check my conclusions, but I believe you can compute all-pairs shortest paths using a generalization of the Floyd Warshall algorithm, for any objects and operators that form a closed semiring (also known as a star semiring). See, e.g., the following papers:

Semiring Frameworks and Algorithms for Shortest-Distance Problems. Mehryar Mohri. Journal of Automata, Languages and Combinatorics, 7(3):321-350, 2002.

A Systolic Array Algorithm for the Algebraic Path Problem (Shortest Paths; Matrix Inversion). Computing 34 (1985), pp. 191-219.

Path Problems in Graphs, Günter Rote. Computing Supplementum 7 (1990), pp. 155-189.

Transitive closure and related semiring properties via eliminants. S. Kamal Abdali, B. David Saunders. Theoretical Computer Science 40 (1985): 257-274.

Algebraic Structures for Transitive Closure. Daniel J. Lehmann. Theoretical Computer Science, 4 (1977), pp. 59–76.

It's possible you might find more references under the names "algebraic path problem" or "algebraic shortest paths".
> 0 votes

# Answer
Self-answer: after a follow-up research on my own, I discovered that, while my *is-a* & *has-a* weights do form a star semiring with idempotent meet operator, Floyd-Warshall algorithm does not work because it does not take cycles into account.

If I understood it correctly, Floyd-Warshall algorithm is only valid if paths with cycles are never shorter than ones without them: in other words, $x \le x^\*$. In my case, there was a counterexample to this, namely $h \nleq h^\* = ih$.

I've currently requested an additional test case to the original problem page; if the request is accepted, my submissions will be rejected as expected.
> 0 votes

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


# Question
Title: Terminology for number of topological sorts
Is there a standard terminology for the topological sort count over a partial order? I went with magnitude of a poset rather than dimension as this is too close to linear algebra terminology. I wonder if there is a generally accepted choice.

# Answer
> 1 votes
"Number of linear extensions" is probably the most popular one.

Google scholar returned 1000+ matches for `"number of linear extensions"` while `"number of topological order"` or `"number of topological sort"` return less than 10 matches. `"magnitude of a poset"` has only one match with seemingly different meaning.

---
Tags: partial-order
---


# Question
Title: How to generate spatial scale-free nwtworks?
I want to generate spatial scale-free networks for my project. Are there any python libraries that enable it?

I read about the BA model (https://www.science.org/doi/pdf/10.1126/science.286.5439.509) which seems like the pioneer of scale-free networks but I am not sure it takes the spatial aspect into the account.

Can anyone explain:

1. What is the difference between a spatial and non-spatial scale-free network?
2. Python libraries to generate a spatial scale-free network.

# Answer
> 0 votes
In each iteration, with probability $p$ you create an edge, and otherwise a new vertex.

When creating edges, you consider the degree of the two vertices, and scale by $1/f(\text{dist}(v,u))$, where dist is typically the Euclidean distance.

When adding a new vertex, you put it randomly in $n$-dimensional space and connect it to some predefined number of vertices, subject to degree and scaled down similarly as above.

---
Tags: algorithms, graphs, sampling, network-topology
---


# Question
Title: Convert lower-left matrix triangle 1D index to row, column
How can I convert a 1D index in the lower-left triangle of a grid into a row and column?

For example, consider this table of 1D indices, indexed by row and column

```
        //       0  1  2  3 4
        //    +--------------- ...
        // 0  |  0
        // 1  |  1  2
        // 2  |  3  4  5
        // 3  |  6  7  8  9
        // 4  | 10 11 12 13 14
        // ...

```

Computing the 1D index from row and column is easy.

Computing the column from the row and 1D index would also be easy. The triangle above a row has -- with 0-based indices -- (row^2 + row)/2 indices.

**How can I compute the row from the 1D index quickly, ideally in constant time, without any pre-computed mapping?**

# Answer
The $r$ first rows include $T\_r=\dfrac{r(r+1)}2$ elements and the linear index corresponding to $(r,c)$, with $0\le c\le r$, is $i:=T\_r+c$.

The $T\_r$ are called the *triangular numbers*.

---

Retrieving the row and column from the linear index is a little more tricky.

For given $i$, we have

$$\frac{r(r+1)}2\le i\le\frac{r(r+1)}2+r$$

or, multiplying by 2 then adding 1/4:

$$\left(r+\frac12\right)^2\le 2i+\frac14\le \left(r+\frac32\right)^2-2$$ and this is solved by

$$r=\left\lfloor\sqrt{2i+\frac14}-\frac12\right\rfloor.$$ $c$ follows.
> 2 votes

# Answer
I think this is a solution. Works better with 1-based indices.

```
        //       1  2  3  4  5
        //    +--------------- ...
        // 1  |  1
        // 2  |  2  3
        // 3  |  4  5  6
        // 4  |  7  8  9 10
        // 5  | 11 12 13 14 15
        // ...

```

Let `i` be the 1D index. Then we have `i < (row^2 + row / 2)`. And for the rightmost value in a row, we have `i = (row^2 + row / 2)`.

That gives the quadratic equation 0 = row^2 + row - 2i. Given i, we can solve for `row`, using:

```
q = -1/2 * (b + sgn(b) * sqrt( b^2 - 4ac ))
x1 = q/a
x2 = c/q

```

Then:

```
row = ceil( x2 ) = ceil( c / q )

```

For example, consider i=10, in the fourth row above. Then:

```
c = -2 * 10 = -20

q = -1/2 * (1 + 1*sqrt(1 - 4 * 1 * (-2*10)))
  = -1/2 * (1 + sqrt( 1 + 80 ))
  = -1/2 * (1 + 9)
  = -5

row = ceil( c / q ) = -20 / -5 = 4

```

Doing the same for `i=15` results in `row = -30/-6 = 5`.

The *ceiling* of the results for anything between `10 < i <= 15` is also 5.
> 1 votes

---
Tags: data-structures, arrays, matrices
---


# Question
Title: Matrix-vector multiplication using only lower triangular of matrix
Suppose one has a large **sparse symmetric positive definite** matrix $A$ and wants to multiply it by a vector $x$. Only the lower triangular part of matrix A is stored/known. The multiplication $Ax$ should be as efficient as possible, as it has to be performed many times and $A$ is large (millions of rows and columns). Is there any known algorithm that achieves this?

# Answer
Answer by Clayton Gotberg \[1\], modified:

> If $\textbf{A}$ is a symmetric matrix and $\textbf{A}\_{LT}$ is the lower triangular part of the matrix and $\textbf{A}\_{UT}$ is the upper triangular part of the matrix:
>
> $\textbf{A}\_x = \textbf{A}\_{LT}x + \textbf{A}\_{UT}x - diag(\textbf{A}) \cdot x$
>
> where the diagonal function only finds the diagonal elements of $\textbf{A}$. This is because of a few relations:
>
> $\textbf{A} = \textbf{A}\_{LT} + \textbf{A}\_{UT} - \textbf{IA}$ $(\textbf{B} + \textbf{C})x = \textbf{B}x + \textbf{C}x$
>
> To save time and space \[...\], take advantage of the relations:
>
> $\textbf{A}\_{UT} = \textbf{A}\_{LT}$ $(\textbf{A}x)^T = x^T\textbf{A}^T$
>
> To get:
>
> $\textbf{A}x = \textbf{A}\_{LT}x + (x^T\textbf{A}\_{LT})^T - diag(\textbf{A}\_{LT}) \cdot x$

Additionally, there are efficient GPU implementations \[2\] for efficient triangular matrix vector multiplication - this paper includes several references for relevant papers and algorithms.

# References

\[1\]: Symmetric Matrix-Vector Multiplication with only lower triangular stored, https://au.mathworks.com/matlabcentral/answers/812175-symmetric-matrix-vector-multiplication-with-only-lower-triangular-stored/?s\_tid=ans\_lp\_feed\_leaf

\[2\]: Efficient Triangular Matrix Vector Multiplication on the GPU, https://link.springer.com/chapter/10.1007%2F978-3-030-43229-4\_42
> 1 votes

# Answer
As far as I know, there is no better way than the standard matrix-vector accumulation, taking $O(n^2)$ operations. Anyway, you need to take into account the packed storage of the matrix, and you need to process the matrix elements following an L shape.
> 0 votes

---
Tags: matrices, sparse-matrices, matrix-multiplication
---


title: How to prove that this is NP complete

text:
# Question
Title: How to prove that this is NP complete
I have the following problem: Given an undirected graph with n vertices v1,…,vn, a positive integer weight on each edge, and a n×n symmetric matrix Rij. The objective is to find a subset S of the edges such that the total cost of the edges in S is minimized and for every pair of vertices vi and vj there exist at least Rij disjoint paths from vi to vj such that all paths use only edges in S.

I tried showing a reduction from Undirected Hamiltonian Cycle as follows, but I'm not quite sure where to go from there. Any help is appreciated!

# Answer
The problem cannot be NP complete since it is not a decision problem, and hence it does not belong to NP. The decision version of your problem (given an edge-weighted graph $G$, the matrix $R$, and an integer $k$, is there a set of edges that satisfies the constraints in your question and has a total cost at most $k$?) is clearly in NP.

To show that the problem is NP-hard you can reduce from the (decision version of the) minimum Steiner tree problem (to the decision version of your problem). The graph and the weights are the same. Build $R$ as follows: for each pair $v\_i, v\_j$ of terminals set $R\_{i,j}=1$, then set all other entries of $R$ to $0$.

The set of edges of any Steiner tree is clearly also a solution to your problem (and the costs coincide). Moreover, any set of edges that is a solution to your problem must induce a graph having a connected component that contains all the terminals. This implies the existence of a Steiner tree that costs at most as much as the sum of the weights of the selected edges.
> 1 votes

---
Tags: graphs, np-complete, np-hard, np, correctness-proof
---


# Question
Title: To where is the mouse sending signals of a computer?
When we move the mouse, we can see the cursor moving on the monitor. I know that mouse can send signals according to its movements. Which component of a computer is receiving those signals in the first place? Is this whole process happening only between device controllers and device drivers? Is there any involvement of the OS in this?

# Answer
Your mouse is plugged into a USB port, yes? And you're using a pretty normal PC?

First off, USB devices never send signals by themselves. They're only allowed to respond to questions they get from the computer (formally, the "host"). The computer is asking the mouse, typically 125 times per second, whether it's moved. Some expensive mice get polled 1000 times per second, but it uses more bandwidth on the USB bus. So let's answer the opposite question first: how do these requests get from the operating system to the mouse? and then the answers go back the opposite way to that.

---

If you were to trace the wire (don't bother, it's tiny and probably goes underneath other wires) you'll find it goes - past some circuits to defend against static electricity zaps - back to a component called a *USB host controller*. The host controller can be a separate chip, or it can be inside the CPU chip or the Platform Controller Hub. You can (and probably do) have more than one. To keep things simple let's assume it's a separate chip.

The USB host controller's job is to control the USB bus. The host controller is fully in charge of the USB bus (at least the one it's connected to - you have several), but is itself a slave to the rest of the system. It sends out these polling requests 125 times per second, all by itself, because it was told to.

Who told it? Well, the host controller, being a kind of adapter, has two sides. One side is the USB bus where you plug in your mouse. The other side points towards the CPU. There are many different host controllers that connect to CPUs in different ways, but since you have a PC, your one is probably connected to a PCI Express bus. The PCIe bus passes through a chip called the *Platform Controller Hub* (whose job isn't important here) and then on to the CPU. Actually, since the CPU is in charge of everything, I should say it goes from the CPU, through the PCH and on to the USB host controller.

The CPU can send PCIe transactions or "packets" to the USB host controller, more-or-less directly. The CPU redirects certain memory addresses to the PCIe bus, and PCIe packets are sent using the memory read and write instructions.

That covers the hardware side. How does the software look?

On the software side, you have a driver for the USB host controller, which knows what PCIe packets to send it to make it send these polling requests 125 times per second. That driver acts on behalf of the mouse driver, which knows **that** it has to send polling requests 125 times per second. And when it gets a response back (saying the mouse was moved) it passes that response to the mouse driver to interpret the mouse movement.

A USB bus can have several things plugged into it (via hubs) so the one host controller can interface with several USB devices at the same time, and therefore the one host controller driver can interface with several USB device drivers at the same time.

The USB mouse protocol is standardized, so you don't need to install a special driver for *your* mouse - the built-in one for "any USB mouse" will do.

---

It's quite typical that the software looks like the opposite of the hardware. You have a mouse driver that wants to talk to the mouse. But it can't talk directly, so it enlists the USB host controller driver to send the needed USB packets to the mouse. Some CPU designs (not yours) don't speak PCIe directly, so they might even need a PCIe driver to send the PCIe packets to the host controller. And we can go upwards, too: if you plug in a hard drive with a USB-to-SATA adapter, the SATA hard drive driver has to call on the USB-to-SATA chip driver to send SATA commands, which calls on the USB controller driver to send the USB commands telling the adapter chip to send the SATA commands.

The involvement of the operating system is that it's the framework within which all the drivers sit. You'd expect the operating system to mostly stay out of the way, apart from loading the necessary drivers depending on which hardware is plugged in.

The OS will scan the PCIe bus to see what devices are attached. It will see the USB host controller, and load the USB host controller driver, which will scan the USB bus to see what devices are attached. It will see the SATA adapter and the mouse, and get the OS to load the SATA adapter driver and the mouse driver... you get the idea.
> 2 votes

---
Tags: computer-architecture, operating-systems
---


title: How does symlink work?

text:
# Question
Title: How does symlink work?
I am recently studying The Operation System, I am confused about how symlink work even after watching some YouTube videos, hope there's someone can help me out with some questions. According to wiki, symlink is pointing to the name of the file but not the inode, if the computer wants to access /opt/be which is a symlink points to /usr/vscode/test.txt, should the procedure be

1. Access root inode
2. Access the index block pointed by root inode
3. Access the inode of /opt
4. Access the index block pointed by /opt inode
5. Access the inode of /opt/be
6. Access the index block pointed by /opt/be inode (the processor gets the filename i.e./usr/vscode/test.txt)
7. Access root inode again
8. Access index block pointed by root inode ...

I am wondering at step 7, should the process access the root inode again or should access the inode of the file directly?

# Answer
> 1 votes
A *symbolic link* is simply a *special file* which contains a *path*. There is nothing special or magic about this path. The path has to be looked up in exactly the same way as any other path.

For example, if the symbolic link contains the path `foo/bar/../../../baz/./quux`, then the OS has to look up that path.

> should the process access the root inode again or should access the inode of the file directly?

How would it know the inode? How would it even know that the inode exists at all?

For example, the Gatling webserver uses symbolic links for a neat trick: in Gatling, you configure an HTTP Redirect by creating a symbolic link whose path is the URI you want to redirect to:

```
ln -s https://www.google.com/ search.html

```

There is absolutely no expectation that `https://www.google.com/` is a resolvable path in your system – in fact, it is quite likely that it isn't. So, in this case, *there is no inode* for the linked path.

---
Tags: operating-systems, filesystems
---


# Question
Title: What characteristics would a PDA $A$ where $L(A)=\Sigma^*$ have?
I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's entire input, have an empty stack, and be in an accept state in order to accept. I am also working with the convention that a PDA always pushes a *\\$* onto the stack in the first transition and pops it off on the last transition to an accept state to ensure stack-emptiness (this comes from Sipser's Intro to Theory of Computation textbook). Given a PDA $A$ where $L(A)=\Sigma^\*$, what properties would $A$ have that we would be able to determine by just looking at its definition? Currently these are my potential guesses for said properties:

* Every single state has a transition for every symbol $s \in \Sigma$
* Nothing is ever pushed onto the stack (i.e. symbols are only read)
* Every state is an accept state (less sure about this one)

I would appreciate any insight, corrections, or additions to what I have already. Thanks!

# Answer
None of the above, I am afraid. There is nothing that distinguishes a PDA for $\Sigma^\*$, except that it has an accepting computation for every string.

Of course a PDA may have all those properties, just build a deterministic finite state automaton and convert it to a PDA by ignoring the stack. But we can avoid all these properties and still accept $\Sigma^\*$.

The stack *can* be used. Otherwise the PDA turns into a mere finite state automaton. For FSA we know that accepting $\Sigma^\*$ is decidable.

PDA are allowed to be non-deterministic, meaning that in the same configuration two different computational steps are possible. We do not necessarily handle every input symbol at every state. On the other hand handling every input symbol is not a restriction. One may just add non-accepting computations for missing symbols. Again, for deterministic DPDA accepting $\Sigma^\*$ is decidable, so non-determinism is one feature for undecidability.
> 1 votes

---
Tags: formal-languages, finite-automata, undecidability, pushdown-automata
---


title: Finding All Anagrams in a String

text:
# Question
Title: Finding All Anagrams in a String
**Problem**: find all anagrams in a string such that one substring can be formed from another substring by rearranging its letters. Given a string $s$, find the number of pairs of substrings of the string that are anagrams of each other.

Below is the traditional solution to this problem that uses $O(n^2\times n\log{n})=O(n^3\log{n})$.

Below at line 15, the formula is used to find all anagrams of same length:

$$\frac{count(count-1)}{2}$$

For example, if $s=KKKK$, then all anagrams of length 1 are 6 are $$ \underset{s\_1,s\_2,s\_3,s\_4}{\underbrace{KKKK}} = \\{s\_1, s\_2\\}, \\{s\_1, s\_3\\}, \\{s\_1, s\_4\\}, \\{s\_2, s\_3\\},\\{s\_2, s\_4\\},\\{s\_3, s\_4\\} = {4 \choose 2} $$

All anagrams of length 2, then all anagrams of length 2 are 3: $$ \underset{s\_1,s\_2,s\_3,s\_4}{\underbrace{KKKK}} = \\{s\_1s\_2, s\_2s\_3\\}, \\{s\_1s\_2, s\_3s\_4\\}, \\{s\_2s\_3, s\_3s\_4\\} = {3 \choose 1} $$

**Question**: All anagrams of length 3, then all anagrams of length 3 are 1 though the combination formula gives 2. Why, please?: $$ \underset{s\_1,s\_2,s\_3,s\_4}{\underbrace{KKKK}} = \\{s\_1s\_2s\_3, s\_2s\_3s\_4\\}, \\{s\_1s\_2, s\_3s\_4\\}, \\{s\_2s\_3, s\_3s\_4\\} = {2 \choose 1} = 2 $$

Also, I am not sure how we get the formula below to find the total number of all anagrams in a string, and why it's justified to be used in this problem?

$$ \sum\_i{\frac{count\_{anagram\_i}\left( count\_{anagram\_i}-1 \right)}{2}} $$

# Answer
> 1 votes
Lines $1-12$ are pretty straightforward, finding all substrings, sorting them and updating the counter for each occurrence of a substring and its permutation accordingly.

Now, $3$ substrings $BAC$, $ACB$ and $CBA$ . Sorting them lexicographically gives $ABC$. And in the hashmap $anagrams$ count of $ABC$ would be $3$. The question is asking to find *anagrams in a string such that one substring can be formed from another substring by rearranging its letters*, so essentially **pairs of substrings**. If you choose any $2$ from $BAC$, $ACB$ and $CBA$, you would get such a pair. The total number of such pairs would be $$\frac{3\ast (3-1)}{2} = \binom{3}{2} = 3$$. Similarly the idea can be extended to find the number of pairs for an arbitrary count as $$\frac{count\ast (count-1)}{2} = \binom{count}{2}$$

All that is left now is to sum them up.

---

P.S.

The algorithm is returning the count, while the question is asking to return substrings, so instead of incrementing the count you can save the substrings instead.

---
Tags: algorithms, time-complexity
---


# Question
Title: Distinct edge weight assumption in MST algorithms
My lecture notes for minimum spanning trees say that:

> A graph can have several minimum spanning trees but if the edge weights are distinct then the minimum spanning tree is unique. Without loss of generality, we can assume that the edge weights are distinct

I'm trying to convince myself that the distinct edge weights assumption in MST algorithms is a valid one but haven't made much progress. I thought about maybe considering the smallest absolute difference between two adjacent edge weights (call this $\delta$) and then let $\alpha = \delta / m$ where $m$ is the number of edges. If there's $k$ edges of the same weight $w$, order them arbitrarily and replace the edge weight by $w + i\times\alpha$ for $0\le i\<k$. Then all edge weights are unique and any MST algorithm applied for these new weights should give a valid MST for the original weights. I'm not convinced that this works though.

# Answer
You are on the right track. A bit more work is needed.

---

Suppose we have developed a comparison-based MST algorithm $\mathcal A$ for graphs of distinct edge-weights. (You will probably not see an MST algorithm that is not comparison-based.)

Let $G=(E,V,w)$ be a weighted graph where edge-weights might have duplicates. How can we obtain an MST of $G$ using $\mathcal A$?

We can run $\mathcal A$ on $G$, breaking ties among the same edge-weights arbitrarily and consistently, to obtain a spanning tree $T$. However, is $T$ an MST of $G$ still? That is your question.

Let we sort all edge-weights (with duplicates) according to the same tie breaking rules when we ran $\mathcal A$ to obtain $T$. Suppose we get $e\_1, \cdots, e\_m$. Let $\delta\_E$ be the smallest nonzero absolute difference between two edge-weights. Let $\delta\_G$ be the smallest nonzero absolute difference between the weights of two spanning trees of $G$. If all edge-weights are the same or all weights of spanning trees are the same, $T$ is trivially an MST. Assume otherwise, so both $\delta\_E$ and $\delta\_G$ are well-defined. Let $G^+=(V, E, w^+)$, where $$w^+(e\_i)=w(e\_i)+\frac{i\min(\delta\_E, \delta\_G)}{n^2}.$$ Then $$i\<j\iff w^+(e\_i)\<w^+(e\_j).$$ In particular, all edge-weights of $G^+$ are distinct.

Now we run $\mathcal A$ on $G^+$. Since the comparison order of all edges for $G$ is the same as that of $G^+$, the same spanning tree $T$ will be obtained. Since $\mathcal A$ is an MST algorithm, $w^+(T)\le w^+(T')$ for any spanning tree $T'$ of $G^+$ (or of $G$, since the spanning trees of $G$ are the same as the spanning trees of $G^+$).

$$w(T)\<w^+(T)\le w^+(T')\le w(T')+(n-1)\frac{n\delta\_G}{n^2}\<w(T')+ \delta\_G$$

By the definition of $\delta\_G$, this means $w(T)\<w(T')$.
> 2 votes

# Answer
The real question is: if we assign arbitrary priorities to edges of equal weights, can that break an MST algorithm ? Though this can lead to different MST's, neither the tree-ness property, nor the spanning property nor the minimum weight will be invalidated.

Assigning priorities can be done

* a priori, for instance by numbering the nodes and using the lexicographocal ordering based on (weight, number);
* a posteriori, by declaring that the edges effectively chosen during the resolution had a higher priority.
> 1 votes

---
Tags: algorithms, graphs, minimum-spanning-tree
---


title: Stack Program Counter

text:
# Question
Title: Stack Program Counter
I am trying to understand stacks a little better.

I don't understand why the content of the program counter is saved on the stack for the function call (call), but not for a jump (jmp)?

can someone please explain it to me?

thanks in advance!

# Answer
Under normal circumstances, the program counter is just incremented i.e. the next instruction is executed. When you call a function, instead of the next instruction, some other instruction needs to be executed, and after completing the function you need to go back and execute the next instruction after the function call, hence it needs to be remembered. This is not the case with jump, where you are skipping some instructions, so no need to store program counter in this case.
> 0 votes

# Answer
When you perform a `call`, you jump into a proceduce that can `ret`, effectively doing similar work to how a usual function call works. You run a function, and after it completes - you continue in the line after the `call`.

In contrast, `jmp` should not be called into procedures that use `ret`, which means that it will effectively act like a `goto` in C.

Both can be useful at times - `call` to call procedures / functions, and `jmp` (with its variations) to perform control flow operations, such as "if" conditions, "for" loops, etc.
> 0 votes

---
Tags: stacks, assembly
---


# Question
Title: Problems Solvable in Poly time but not verifiable in Poly time
I was just wondering if there exists problems that are solvable in polynomial time (a correct solution can be found in polynomial time) but not verifiable in polynomial time. My professor says no, but doesn't rlly give a clear explanation besides saying you can just use the solution to verify, but I fail to see how this can be if there are more than just one solution.

Are we allowed to make the argument that any problem with a poly algorithm can be modified in polynomial time so that it produces the particular polynomial solution we are trying to verify?

Edit: Sorry if the problem was confusing as I threw in P and NP, the title has been changed to reflect this.

# Answer
It appears you're asking about problems for which there may be more than one correct answer for a given input (not decision problems).

In that case, there may exist a polynomial-time algorithm that finds a solution, but no algorithm that can verify arbitrary solutions. For example, given any string, it's easy to find a program that prints that string and then halts, but impossible in general to determine whether a program prints that string and then halts.
> 3 votes

# Answer
The verification algorithm will just use the solving algorithm and will ignore the verification "proof" it gets.

I.e, a verifier is a TM $V(x,w)$, such that $x\in L\iff \exists w, |w|\text{ is polynomial and } V(x,w)=true$.

Therefore, if $V$ completely ignores $w$ and uses the solving procedure to check if $x\in L$, it is a polynomial verifier. The algorithm of $V$ is as follows:

define $V(x,w)$:

1. Compute $S(x)$
2. Return "true" $\iff$ $S$ returned "true"

So basically, $w$ has no meaning here. Its pretty "hacky" and sounds weird, but it is allowed since there is a polynomial solver $S$ \- and polynomial solvers are (in some sense) stronger than polynomial verifiers.
> 2 votes

# Answer
You have a problem in P. This means you have an algorithm X that will tell you whether the answer for an instance is yes or no, in polynomial time.

Now I create a verifier. A verifier takes an instance and some information that is supposed to help it, and will return in polynomial time an answer “yes” if the correct answer is “yes” and the information is useful.

My verifier throws the extra information away, uses algorithm X to determine the correct answer in polynomial time, and returns that answer. Since it gives the correct answer whenever the correct answer is yes, your problem is in NP - it exactly meets the definition for NP problems. Since it also gives the correct answer when the answer is no, P is also in co-NP.
> 0 votes

---
Tags: algorithms, np, p-vs-np
---


title: automatic memory allocation

text:
# Question
Title: automatic memory allocation
Global variables are given fixed addresses in main memory by the C compiler, called static memory allocation. Function local variables are created on the stack, this is called automatic memory allocation.

Why is it done this way?

# Answer
There are three types of memory in C: static (global variables), automatic (stack) and dynamic (heap). All three are needed to express programs conveniently and efficiently.

### Why static memory is necessary

Why you can't have just automatic and dynamic memory: It's mostly possible — after all, a local variable in `main` is almost as good as a global variable. (The heap is no good for global variables because there's no way to get a name for a part of the heap, only a name for a *pointer* to a part of the heap.) However, there are a few reasons why this would be inconvenient:

* Language design: sometimes it's convenient to access the same data from multiple places in a program without having to pass a variable via function arguments. Global variables allow this. With a variable in `main`, you'd have to pass its address through all function calls.
* Language design: global variables are available in `atexit`-registered functions which perform cleanup after `main` returns.
* Language design, with multiple threads: static variables are shared between threads. If they're on the stack of a particular thread, you'd have to keep that stack in memory even if the thread exits.
* Memory optimization: the initial values of variables have to be stored somewhere when the program starts. You might as well use the same memory if the variables are modified.
* Safety of memory management: the size of the stack is typically limited for several reasons, including keeping the memory usage reasonable when there are many threads. By making global variables a separate thing, you don't need to take them into account when calculating the stack size of the initial thread.

### Why automatic memory is necessary

Why you can't have just static and dynamic memory: where do you put the local variables of a function? Some very early programming languages reserved an area in memory for every function. This had a lot of limitations, so most languages adopted the concept of stack for a function's local variables. If each function has a dedicated memory area:

* If there are a lot of functions in the program, then at any given time, most of the functions are not being called, so their memory is not used. This wastes a lot of memory. The compiler might be able to optimize, e.g. if it sees that `f1` never calls (directly or indirectly) `f2` and vice versa then `f1` and `f2` can use the same memory area. But it's rarely possible to guarantee this kind of exclusion.
* A function may never call itself directly or indirectly, i.e. no recursion is possible. Recursive function calls are not that common in C programs, but they are possible, and some algorithms are essentially impossible to implement without using or faking recursion (it's of course possible to avoid recursion by managing your own stack when you need one, but it's inconvenient).

Using dynamic memory for the local variables of a function wouldn't be possible because you can't give a name to a part of the heap: you'd have to access everything through pointers — which themselves couldn't have names, so the only possible names would be global variables. That includes a function's arguments: functions could not have arguments, so you'd need to pass data through global variables, which has the same problems as using static memory to implement local storage for functions that I explained just above.

### Why heap memory is necessary

With automatic memory, you have to declare how much memory a piece of code is going to use before calling that code. In particular, a memory allocation can never travel upwards: you can't have a function allocating memory that its caller can then use. This is extremely restrictive. It turns the language into a Turing tarpit: it's technically possible to implement algorithms that require an amount of storage that can't be calculated at the beginning, but you have to basically try, and if you run out of memory, try again from scratch with more memory.
> 16 votes

# Answer
Because **functions can be recursive**.
Since a function may call itself (in)directly, the compiler needs to ensure that the nested invocation gets its own variables. And the stack is the most simple solution for that.

As a matter of fact, early FORTRAN did not allow for recursive functions. And guess what, that allowed the compiler to statically allocate memory for all functions. You don't see this requirement in modern languages because not having recursive functions is a price most programmers are not prepared to pay.
> 4 votes

# Answer
Global variables exist as unique instances, which are known at program compilation and can be preallocated some space.

Local variables are only needed if the functions are called. So

* they are not allocated in advance,
* if there are recursive calls or mutually recursive calls (A calls B and B calls A), there can be several instances of the same variables existing at the same time. The stack implements a convenient mechanism to allocate these instances. This *must* be done dynamically, as it is not possible to predict program execution.

You will soon learn that there is another form of dynamic allocation, which is managed explicitly by the programmer, in a memory zone called the heap. It provides maximum flexibility to allocate space of a size and layout not known in advance.
> 3 votes

---
Tags: memory-management, c, language-design
---


# Question
Title: Prove that if a language is in co-RE it doesn't mean that it's mapping reducible to another language
Prove/disprove: if $L\in \text{coRE}$ then $L$ is mapping-reducible to $\text{PAL}\_{\text{TM}}$, where
$\text{PAL}\_{\text{TM}} = \\{~\langle M,w\rangle ~|~ M ~\text{is a TM and}~w~\text{is a palindrome}~\\}$

It feels like there's not necessarily a mapping reduction from every language to a harder language, but I couldn't find a counter example or disprove the claim (How do I prove that a mapping doesn't exist?)

I tried playing with languages that I know that are in $\text{coRE}$, and also tried to assume towards contradiction that such a mapping exists, but it didn't really lead me anywhere.

# Answer
It is very easy to disprove the claim that if L is in co-RE, then L must be mapping reducible to $PAL\_{TM}$.

Consider a simple language such as the empty language, denoted as $∅$. This language contains no strings, so it is not a palindrome language, and therefore cannot be mapped reducible to $PAL\_{TM}$.

However, the empty language is in co-RE because it is the complement of the language {ε}, which is RE (since it contains a single string, the empty string ε). Therefore, we have found a counterexample to the claim that if L is in co-RE, then L must be mapping reducible to $PAL\_{TM}$.
> 1 votes

# Answer
One way to prove that a reduction doesn't exist is to prove that if a reduction *did* exist, it would lead to some result that is incompatible with the premise. So, suppose such a reduction did exist. What could you say about the complexity class of $L$, using that reduction?
> 0 votes

---
Tags: complexity-theory, turing-machines, computability
---


# Question
Title: How to remove ambiguity from the grammar?
I want to remove ambiguity from the grammar below:

S → ABC

A → abA | ab

B → b | BC

C → c | cC

I have removed left recursion and left factoring and obtained the grammar as follows:

S → ABC

A → abA'

A' → A | ε

B → bB'

B' → CB' | ε

C → cC'

C' → ε | C

Now, how can I remove ambiguity from the grammar? Is removing left recursion and left factoring necessary?

# Answer
"The grammar is ambiguous. But the language is regular. So if you figure out what the language is, you can easily write an unambiguous grammar", says rici.

Denote the language generated by the given grammar by $L$. Let us see what is $L$ in plain English. Or how we can describe the strings in $L$. Or how we can generate the strings in $L$.

A good way to start is, as you have done wonderfully, to generate and list some strings in $L$. You got $$a b b c, a b b c c, a b b c c c, a b a b b c, a b b c c c c, a b a b b c c, a b a b b c c c, a b b c c c c c, a b a b a b b c, a b a b b c c c c, a b a b a b b c c, a b a b a b a b b c, a b a b a b b c c c$$

We can observe that each string starts with one or more $ab$'s, continues with one $b$, and ends with one or more $c$s. (This observation could have been guided by studying the given grammar.)

It turns out the description above characterizes $L$. That is, a string is in $L$ if and only if it starts with one or more $ab$'s, etc. It is not hard to prove that fact.

Instead of transforming the given grammar, we can write an unambiguous grammar from scratch, since we "know" $L$.

In fact, the description above is "unambiguous" in the sense that there is unique way to split a string into one or more $ab$'s, one $b$'s and one or more $c$'s.

$S\to ABC$.
$A\to abA\mid ab$
$B\to b$
$C\to cC\mid c$

---

The grammar can be simplifed to

$S\to AC$
$A\to abA\mid abb$
$C\to cC\mid c$
> 1 votes

---
Tags: formal-grammars, compilers, ambiguity
---


# Question
Title: Check whether a regular expression is correct
I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct?

I know that there can be multiple regular expressions that are correct.

This is intended as a reference we can point others to. Please explain your method in a form that someone new can understand it.

# Answer
Yes. It depends how the regular language $L$ is specified. I describe below an algorithm for this problem, i.e., a systematic procedure that you can follow to check correctness. You can simulate running such an algorithm by hand, with pencil-and-paper, if necessary: it might be tedious, but it works. Even better yet, you can implement it on a computer and let the computer run the algorithm.

# As a finite automaton

If the language $L$ is provided in the form of a finite automaton (e.g., DFA or NFA), then there are standard algorithms to check whether the NFA/DFA is equivalent to $L$, i.e., whether they generate the same language.

1. If you have a NFA for $L$, first convert it to a DFA for $L$ (e.g., using the subset construction). If it is already a DFA, you can skip this step.
2. Then, convert the regular expression $R$ to a NFA (e.g., using Thompson's algorithm, or using Brzozowski derivatives) and convert the NFA to a DFA. Or, you can see https://cs.stackexchange.com/a/13606/755 for details on how to convert a regular expression to a DFA.
3. Minimize both DFA (see https://en.wikipedia.org/wiki/DFA\_minimization).
4. Finally, check whether the two minimal DFA are isomorphic, i.e., are the same, after relabelling of states. If they are the same, then the regular expression $R$ is correct. If they are not the same, then the regular expression is incorrect -- and moreover, you can identify a specific word that is accepted by one DFA and not by the other, and thus which demonstrates that $R$ is not a correct regular expression.

See also How do I verify that a DFA is equivalent to a NFA?, as well as Is there a way to test if two NFAs accept the same language? if you are implementing this in practice.

# As a regular expression

If $L$ is described by providing a regular expression, then test whether the two regular expressions are equivalent. See Algorithm to determine whether two regexes are equivalent for a detailed description of how to do that. (Related: https://cs.stackexchange.com/a/52860/755.)

# Provided in some other way

If the language $L$ is specified in some other way, you can first find a finite automaton for it (see How to prove a language is regular?) or find a regular expression for it (see How do I find a regular expression for a particular language?), then apply the above methods.

# Other approaches

There are other methods as well. See, e.g., Proving Equivalence of Two Regular Expressions for description of other methods that might be easier in some circumstances.
> 1 votes

---
Tags: regular-languages, finite-automata, regular-expressions
---


title: Java optimization and minimization

text:
# Question
Title: Java optimization and minimization
I'm new to optimization and I have a little problem that I want to resolve with my job. Here we go!

I need a certain number of drivers per day and each driver has 2 consecutive days off during the week. My optimization problem is that I want to have as few employees as possible with the number of driver per week. I need guidance please

For example, I need 6 drivers Monday, 5 drivers Tuesday, 8 drivers Wednesday, 5 drivers Thursday and 6 drivers Friday

The final result should look like this:

sSo the optimization function has to return 4 drivers with Monday and Tuesday off, 1 driver with Wednesday and Thursday, 1 driver with WT and 4 drivers with TF. That's a small sample, but I have more days to cover than that

I tried randomly, I tried with a method that I thought was good but wasn't. So the main problem is, with different number of drivers required per day (Monday to Friday) I want to have the least number of drivers required per week. An other example: I need 7 drivers on monday, 3 drivers on tuesday, 3 drivers on wednesday, 6 drivers on thursday and 8 drivers on friday

The result should be : I need 2 driver with monday tuesday off, 4 drivers with tuesday wednesday off, 2 drivers with wednesday and thursday off and 1 driver with thursday friday off. You can see with the tab below:

I don't need code, I just need to know how to start

Thank you

# Answer
You can solve this with linear programming.

Let's start with the variables. Let $x\_d$ denote the number of drivers whose work week starts on day $d$, e.g., $x\_\text{Monday}$ denotes the number of drivers who work Monday, Tuesday, Wednesday, Thursday, Friday, and have Saturday and Sunday off.

Next the inequalities. Each requirement gives you a linear inequality on the above variables. For instance, if you want at least 6 drivers on Monday, then you need to have

$$x\_\text{Mon} + x\_\text{Thu} + x\_\text{Fri} + x\_\text{Sat} + x\_\text{Sun} \ge 6.$$

Also, the number of drivers on each day must be at least zero, so we have $x\_\text{Mon} \ge 0$, $x\_\text{Tue} \ge 0$, etc.

Finally, the objective function. You say you want to minimize the number of employees, so you should minimize

$$\Phi = x\_\text{Mon} + x\_\text{Tue} + x\_\text{Wed} + x\_\text{Thu} + x\_\text{Fri} + x\_\text{Sat} + x\_\text{Sun}.$$

Your goal is to minimize $\Phi$, subject to the above linear inequalities. This is an instance of linear programming, so you can provide it as input to an off-the-shelf LP solver, and it will give you an optimal solution.

You might need to adjust this if you want to allow drivers who take more than two days off during the week, and/or if you want to have a secondary goal of minimizing the number of days per week worked by the drivers.

In general your problem might be considered to fall within the area of operations research, so you can learn more about methods used in operations research (which includes linear programming, integer linear programming, and other methods).
> 1 votes

---
Tags: optimization, java
---


title: How to reduce 3SAT to TwoOrMoreSAT?

text:
# Question
Title: How to reduce 3SAT to TwoOrMoreSAT?
I want to prove, that 2OrMoreSAT is NP-complete. It's defined as follows:

A formula is considered strongly satisfiable if there exists a model such that two or more different literals in every clause evaluate to true.

$\textit{2OrMoreSAT} = \\{\langle \phi' \rangle \mid \phi' \text{ is a boolean formula in CNF which is strongly satisfiable} \\}$

I want to solve this by reducing 3SAT to 2OrMoreSAT. My first thought was to duplicate all of the literals in a clause, which would ensure 2 or more literals being true - but I don't really know how to limit the literals after. Say ${\phi}$ ∈ 3SAT and ${\phi = X ∨ Y ∨ Z}$, then ${\phi'}$ could look something like this ${\phi' = (X\_1 ∨ X\_2 ∨ Y\_1 ∨ Y\_2 ∨ Z\_1 ∨ Z\_2) ∧ (...)}$

# Answer
> 1 votes
As pointed out by Yuval Filmus in the comments, I assumed there that the formula had to be in 3CNF, which is not necessarily the case. However, I will let my answer, maybe it can still help.

I may be wrong, but I think this problem is in $\mathsf{P}$, there is a reduction to $\texttt{2SAT}$.

Consider a clause $C = (x\lor y \lor z)$. From this clause, define:

$$\phi\_C = (x\lor a) \land (y \lor b) \land (z\lor c) \land (x\lor \overline{b}) \land(x\lor \overline{c}) \land(y\lor \overline{a})\land (y\lor \overline{c})\land (z\lor \overline{a}) \land(z\lor \overline{b})$$

Then I claim that $C$ is satisfiable with at least two true litterals if and only if $\phi\_C$ is satisfiable, and moreover, the truth values of $x$, $y$ and $z$ are the same in both truth assignments.

The idea is that $a\equiv y\land z$, $b\equiv x\land z$ and $c\equiv x\land y$.

Now if $\varphi = \bigwedge\limits\_{i=1}^n C\_i$ is a formula in 3CNF, then $\psi = \bigwedge\limits\_{i=1}^n\phi\_{C\_i}$ is a formula in 2CNF, and $\varphi$ is satisfiable with at least two true litterals per clause if and only if $\psi$ is satisfiable (this is due to the fact that in the previous claim, the truth values of $x$, $y$ and $z$ are the same, so a satisfying truth assignment does not change values between clauses).

Since this construction is done in polynomial time, $\texttt{2orMore3SAT}\leqslant\_m^p\texttt{2SAT}$, which is known to be in $\mathsf{P}$.

What would be a $\mathsf{NP}$-complete problem, though, is the following problem:

> Input: a boolean formula $\varphi$ in 3CNF.
>
> Question: is $\varphi$ satisfiable with **exactly** two true litterals per clause?

The reduction from $\texttt{3SAT}$ transforms a clause $C = (x\lor y \lor z)$ into: $$\phi\_C = (x \lor a \lor b) \land (y \lor c \lor d) \land (z\lor e \lor f) \land (a \lor c\lor e)$$

* if $C$ is satisfied, distinguish depending on the number of true litterals:

+ if exactly one litteral is true, say $x$ WLOG, then assign $b, c, d, e$ and $f$ to *true* and $a$ to *false*;
    + if two litterals are true, say $x$ and $y$ WLOG, assign $a, d, e, f$ to *true* and $b, c$ to *false*;
    + if all three litterals are true, assign $a, c, f$ to *true* and $b, d, e$ to *false*.

In all cases, $\phi\_C$ is satisfied with exactly two true litterals per clause, and the truth values of $x$, $y$ and $z$ are unchanged.
* Conversely, if $\phi\_C$ is satisfied with exactly two true litterals per clause, then exactly two among $a$, $c$ and $e$ are true, say $a$ and $c$. That means that $z$ and $f$ are true, so $C$ is satisfiable. Other cases are similar.

The rest of the reduction is similar to the problem above.

---
Tags: complexity-theory, np-complete, satisfiability, 3-sat
---


# Question
Title: Direct reduction from Near-Clique to Clique
An undirected graph is a Near-Clique if adding one more edge would make it a clique. Formally, a graph $G=(V,E)$ contains a near-clique of size $k$ if there exists $S\subseteq V$ and $u,v\in S$ where $|S|=k$, $(u,v)\notin E$, and $S$ forms a clique in $(V,E\cup\\{(u,v)\\})$. How can I show a direct reduction from Near-Clique to Clique?

# Answer
> 4 votes
Let $(G,k)$ be an instance of Near-Clique, construct an instance $(G',k')$ of Clique as follows.

For each $uv \notin E(G)$, add to $G'$ a subgraph corresponding to $(N(u)\cap N(v))$, i.e.,

1. for each $x \in N(u)\cap N(v)$ add the vertex $x'$ to $V(G')$, and
2. for each edge pair of vertices $x,y \in (N(u)\cap N(v))$ if $xy \in E(G)$ add the edge $x'y'$ to $E(G')$.

Set $k' = k-2$

As $uv \notin E(G)$, $u \notin N(v)$ and $v \notin N(u)$. Note that each of these corresponding subgraphs is disjoint, so a vertex in $G$ may have several corresponding vertices in $G'$.

Now we claim that $(G,k)$ has a $k$-near-clique iff $(G',k'=k-2)$ has a $k'$-clique.

$(\Rightarrow)$ Let $D$ be the vertices of the near clique, then there are two vertices $u,v \in D$ such that

1. $uv \notin E(G)$,
2. $D\setminus\\{u,v\\}$ forms a clique of size $k-2$, and
3. $D \subseteq N(u)\cap N(v)$ (by definition).

Then $G\[D\setminus\\{u,v\\}\]$ (the subgraph induced by $D$) is a subgraph of $G'$ (via the construct and property 3). Therefore by property 2, $G'$ has a clique of size $k-2=k'$.

$(\Leftarrow)$ Let $C'$ be a $k'=k-2$ size clique in $G'$ and let $C$ be the corresponding vertices in $G$ (with induce a $k-2$-clique in $G$ as well). By the construction, there must exist $u,v\in V(G)$ such that $C\subset N(u)\cap N(v)$ (i.e. $u$ and $v$ are adjacent to all the vertices of $C$), moreover $uv \notin E(G)$. Therefore $C\cup\\{u,v\\}$ forms a $k$-sized near-clique in $G$.

The last step is to just assure ourselves that this is polynomial-time computable. In constructing $G'$, we examine at most each pair of vertices, and compute the intersection of their neighbourhoods. Just so we don't have to think too hard about details, that is at most $n^{2}$ neighbourhoods, and for each we take $O(n^{2})$ time to compute the intersection. So the total construction can be enacted in polynomial-time.

# Answer
> 1 votes
Hint: Given an instance of clique, add two new vertices $u,v$, and connect each of them to all of the original vertices.

# Answer
> 0 votes
A much simpler and cruder reduction based on the same idea of the accepted answer:

On an instance of NEAR-CLIQUE $\langle G,k\rangle$, duplicate $G$ by at most $|V|^2$ times. Do not add any edges between the copies. Then, for each missing edge in $G$, choose one copy that has not been chosen and add that edge to the copy (each copy should only has one edge added). Return $\langle G',k\rangle$, where $G'$ is our modified graph, and $k$ is the same $k$ from the input.

This process takes polynomial time, because copying the graph takes linear time and we are doing it for at most $|V|^2$ times.

Suppose $\langle G,k\rangle \in$ NEAR-CLIQUE, then one of the copies of $G$ in $G'$ should contain a k-clique by the definition of NEAR-CLIQUE. Hence $\langle G',k\rangle \in$ CLIQUE.

Suppose $\langle G',k\rangle\in$ CLIQUE, then, if $G$ itself already contains a k-clique in the first place, $\langle G,k\rangle\in$ NEAR-CLIQUE by definition; if not, then this k-clique must be the result of us adding one extra edge to one of the copies of $G$. This, by construction, means that adding one edge *somewhere* in $G$ would give us a k-clique. Therefore $\langle G,k\rangle\in$ NEAR-CLIQUE.

---
Tags: complexity-theory, graphs, reductions, np
---