# Question
Title: how does the shap algorithm work in polynomial time?
I'm trying to understand how the shap algorithm calculates in polynomial time an estimation to the feature attribution function that satisfies the shapely value attributes (specifically for tree based models!).

A simplified version of the feature attribution function for the feature $i$ of the model $f$ prediction for the input instance $x$ is: $\phi\_i(f, x)=\sum\_{S \in N /\\{i\\}}\[f\_x(S\bigcup{i})-f\_x(S)\]$ \- i.e. sum the change in the model prediction for every set of features $S$ that does not include the feature $i$ from the same set when $i$ is introduced.

The naive exponential estimation for a tree based model (Algorithm 1 in the paper), estimates $f\_x(S)$ by recursively following the decision path for $x$ if the split feature is in $S$, and taking the weighted average of both branches if the split feature is not in $S$ (weights are the coverage of train samples in that branch). We do that for every set $S$ in the powerset of features.

So far so good. But now the paper describes Algorithm 2 - a polynomial method for computing the same values, basically by "running simultaneously for all $2^N$ subsets"! I can't understand that, no matter how much I try (see my notebook).

Can someone enlighten me and explain how is that working? how are we tracking the number of sets and the coverage in every path?

Note that the real algorithm is much more complex than what I'm presenting here, as the real feature attribution function weights each set $S$ proportionally to the number of features in it $|S|$ \- but **I'm not interested in that complexity**, only in the basic simplified setup I've presented here.

Thanks for your efforts, this is something that's eluding me for years

# Answer
First, some notation.

A *decision tree* is a binary tree in which each internal node is labelled by one of $x\_1,\ldots,x\_n$, and has two outgoing edges labelled $0$ and $1$. Leaves are labelled with real numbers. To evaluate the decision tree on an input $(x\_1,\ldots,x\_n) \in \\{0,1\\}^n$, we just follow the tree from the root to a leaf, and output the value on the leaf. From now on, we fix a decision tree $T$, as well as a reference output $y$.

A decision tree is *irredundant* if no root-to-leaf path contains the same variable twice. We can easily make a tree irredundant in linear time, and so we assume that $T$ is irredundant. (For some reason, the paper doesn't make this assumption.)

Given a subset $S \subseteq \[n\]$, let $f(S)$ denote the expect output of $T$ when run on a random input $x$ subject to $x\_S = y\_S$ (i.e., $x\_i = y\_i$ for all $i \in S$). Alternatively, it is the expected value of the following process. Start at the root and proceed to a leaf. At any given node, if the node queries a variable $i \in S$, go to the branch labelled $y\_i$. Otherwise, take a random branch. Thus $f(\[n\])$ is the value of $T$ on $y$, and $f(\emptyset)$ is the value of $T$ on a random input.

For $i \in \[n\]$, we define the Shapley value $\phi(i)$ to be $$ \phi(i) = \sum\_{i \notin S} \frac{|S|!(n-|S|-1)!}{n!} (f(S \cup \\{i\\}) - f(S)). $$ For the actual algorithm, the coefficients won't matter much. Indeed, we will calculate directly $$ \alpha\_+(i,\ell) = \sum\_{\substack{i \in S \\ |S|=\ell}} f(S), \\ \alpha\_-(i,\ell) = \sum\_{\substack{i \notin S \\ |S|=\ell}} f(S), $$ from which we can determine $\phi(i)$ using the formula. In the same way, we can compute other power indices, such as the Banzhaf index.

Let $v$ be any node in $T$. Define $\alpha\_{\pm}(i,\ell,v,s\_0,s\_1)$ as the same value as above, when run on the decision tree rooted at $v$, given that we have already put $s\_1$ nodes inside $S$, and $s\_0$ nodes outside $S$. Thus we are interested in $\alpha\_-(i,\ell,r,1,0)$ and $\alpha\_+(i,\ell,r,0,1)$, where $r$ is the root of $T$.

If $v$ is a leaf then $\alpha\_{\pm}(i,\ell,v,s\_0,s\_1)$ is just the label of $v$ multiplied by the number of possible sets $S$, which is $\binom{n-s\_0-s\_1}{\ell-s\_1}$. Now suppose that $v$ is an internal node labelled with $x\_j$ and having children $v\_0,v\_1$. If $j = i$ then $$ \alpha\_+(i,\ell,v,s\_0,s\_1) = \alpha\_+(i,\ell,v\_{y\_i},s\_0,s\_1), \\ \alpha\_-(i,\ell,v,s\_0,s\_1) = \frac{\alpha\_-(i,\ell,v\_0,s\_0,s\_1) + \alpha\_-(i,\ell,v\_1,s\_0,s\_1)}{2}. $$ (In fact, it doesn't matter whether we choose $\alpha\_+$ or $\alpha\_-$ on the right-hand side.) If $j \neq i$ then $$ \alpha\_{\pm}(i,\ell,v,s\_0,s\_1) = \alpha\_{\pm}(i,\ell,v\_{y\_j},s\_0,s\_1+1) + \frac{\alpha\_{\pm}(i,\ell,v\_0,s\_0+1,s\_1) + \alpha\_{\pm}(i,\ell,v\_1,s\_0+1,s\_1)}{2}. $$

The actual algorithm in the paper is some sort of mild optimization of this idea.
> 3 votes

# Answer
slight optimization over @yuval-filmus excellent answer.

In his comment here: https://github.com/slundberg/shap/issues/24 @sh1ng suggests an improvement. Rephrasing a bit, he's saying that we can use the path depth $d$ instead of $n$, and we can also save ourselves the iteration over sets with $|S|=l$ and thus improve the time complexity.

Suppose we have a leaf node at depth $d$. The dynamic programming recursion ensures that we will handle every set $S$ with size $|S|=s\_1 \leq d$ by collecting $s\_1$ features along the path into our set and $s\_0$ features out of our set s.t $s\_0+s\_1=d$.

Since we covered any possible set of features along the path, the iteration over $l$ is used *only* to take into account features that are not along the path, and count sets with sizes $|S|=l \geq s\_1$, which are ${n-d} \choose {l-s\_1}$. Note that since our tree is irreducible (each feature appears at most once in any path), we know that $d \leq n$ so the expression makes sense and the factorial is never negative.

We will now show by induction over the number of features $n$ that we can:

1. Use $d$ instead of $n$ in the shapely weight
2. Don't need to iterate over $l$ and take into account features not along the path

If $n=d$ the claim is trivial. We will use the shapely weight $sw = \frac{s\_1!(n-s\_1-1)!}{n!} = \frac{s\_1!(d-s\_1-1)!}{d!}$. The count would also be trivial ${{n-d} \choose {l-s\_1}} =1$

Now suppose $n=d+1$. There would be

* ${{n-d} \choose {l-s\_1}}=1$ set with the same size $l=s\_1$, and it's shapely weight would be $\frac{s\_1!(n-s\_1-1)!}{n!} = \frac{s\_1!(d-s\_1)!}{(d+1)!}=sw\frac{d-s\_1}{d+1}$.
* There would also be ${{n-d} \choose {l-s\_1}}=1$ set with size $l=s\_1+1$, and it's shapely weight would be $\frac{(s\_1+1)!(n-s\_1+1-1)!}{n!} = \frac{(s\_1+1)!(d-s\_1-1)!}{(d+1)!}=sw\frac{s\_1+1}{d+1}$
* when we'll sum those 2 sets in the $l$ iteration, we'll get exactly the same contribution as $sw\frac{d-s\_1}{d+1}+sw\frac{s\_1+1}{d+1} = sw$
* these are the only 2 valid values of $l$ for our path

*Important* to notice that these 2 sets would have exactly the same contribution $f(S)$ as in the case where $n=d$, as they land in exactly the same node of the tree.

*Also important* to notice that the same claim holds true if $i$ is in our set ($\alpha\_+$ code branch) or outside ($\alpha\_-$ code branch).

Now if $n=d+2$, exactly the same argument would hold for these 2 sets, and we'll get 4 sets. 2 sets with weights summing to $sw\frac{d-s\_1}{d+1}$ and 2 sets with weights summing to $sw\frac{s\_1+1}{d+1}$, and the sum is again $sw$.

code is available in this notebook. credit goes to yuval and sh1ng
> 1 votes

# Answer
In this paper: https://arxiv.org/pdf/2007.14045.pdf, a polynomial-time algorithm is given to compute the SHAP score for deterministic and decomposable Boolean circuits. This algorithm can also be used for decision trees, since there is a simple polynomial-time algorithm for translating such trees into deterministic and decomposable Boolean circuits. For the same reason, the algorithm can also be used for ordered binary decision diagrams (OBDDs) and free binary decision diagrams (FBDDs).
> 1 votes

---
Tags: dynamic-programming, game-theory, decision-tree
---


# Question
Title: Intuition on O(number of leaves) for master theorem
I am trying to develop the intuition of the master theorem for the case where $a \> b^{d}$ \[Case 3\] in this video. In the video, they say that since most of the work is done at the leaves, we should expect $O(\text{number of leaves})$ but I don't see how that is similar to $O(n^{\log\_b a}$), which one would get from the proof.

I just need the connection to the intuition as in how to see $O(n^{\log\_b a}$) from $O(\text{number of leaves})$ even in the least rigorous way. I don't need the actual proof. The presenter gets on to the proof where $n$ is a power of $b$ later on, which is easier to follow but I would like to know so that I don't have to look up the material every time I need to check my work. Given the order of the presentation, I suspect that the intuition can be obtained without the proof for now but I could also be wrong and would appreciate being corrected if that's the case.

# Answer
The recurrence in question is $T(n) = aT(n/b) + f(n)$. Suppose that $n = b^k$, and the leaves are at $n = 1$. The root $b^k$ has $a$ children labelled $b^{k-1}$ (the label is the size of the subproblem). Each one of them has $a$ children labelled $b^{k-2}$, and in total there are $a^2$ children at depth $2$ labelled $b^{k-2}$. More generally, there are $a^\ell$ children at depth $\ell$ labelled $b^{k-\ell}$. In particular, taking $k = \ell$, we see that there are $a^k$ leaves. Since $n = b^k$, we get that the number of leaves is $$ a^k = (b^{\log\_b a})^k = (b^k)^{\log\_b a} = n^{\log\_b a}. $$
> 2 votes

---
Tags: time-complexity, master-theorem
---


# Question
Title: How to index a tree to allow efficient search for paths?
By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be indexed.

I feel this question must be pretty elementary, but as a CS noob I don't know how to search for the answer. I may not even be phrasing the question correctly.

So let me describe a hypothetical use case. Say my program stores a chess game (including variations) as a tree, with each node representing the state of the game after a move. Given any two nodes which are guaranteed to be in the tree, what is the most efficient way to find the path (a sequence of intervening nodes) from one to the other? I'm mostly concerned with time complexity, although I'd like to save space as well (not sure how to express myself more precisely).

**Edit: to clarify what I want, say I have a Python program like this:**

```
tree = Tree(game_record)  # there's a tree constructed from a game record

# this tree can be traversed by calling `advance` and `backtrack`
tree.advance(child=0)  # advance the game into the first child of the current node
tree.backtrack()  # backtrack to the parent of the current node

# and it can tell you which node it's currently at
current_node = tree.current_node()

# now this is my question: at first we're at one node
node1 = tree.current_node()
# after some advancing and backtracking, we arrive at another
node2 = tree.current_node()
# I want a method that returns the path from node1 to node2
tree.find_path(node1, node2)  # should return something like [node3, node4, ...]

# what would be a good way to implement this method?

```

Walking the whole tree is probably not it. I'm thinking that maybe each node can be assigned an informative `address`, perhaps an array. One scheme would be to let a child's `address` be one element longer than its parent's, where the extra element uniquely identifies the child. So if the first node has address `[0]`, its children would have `[0, 0]`, `[0, 1]`, ... and the children of `[0, 1]` would have addresses like `[0, 1, 0]`, `[0, 1, 1]`, and so on. With this scheme the nodes on the path between any two nodes can be directly read off from their addresses.

With a tall tree though, the addresses can get quite long. Not a real concern for a chess program, but this way of indexing a tree just feels inefficient and inelegant to me. Is there a better way to assign addresses? Or is there a completely different approach to this problem?

# Answer
> 3 votes
Root the tree in an arbitrary fashion. Given two nodes $x,y$, let $x\_0 = x, x\_1, \ldots$ and $y\_0 = y, y\_1, \ldots$ be the paths going up the tree all the way to the root. If $x\_i = y\_j$ then the unique path between $x$ and $y$ is $x\_0,\ldots,x\_i=y\_j,\ldots,y\_0$.

In order to find this path quickly (at the cost of a little bit of memory), generate the two paths in parallel, $x\_0,y\_0,x\_1,y\_1,x\_2,y\_2,\ldots$, storing the resulting vertices in a hash table, until they collide. This happens at time $\max(i,j)$, which is the same as the path length $i+j$ up to constant factors.

---

While the description above suggests that you have to store the entire tree ahead of time, this is not necessarily the case. In general, all you need to do is to have a consistent way of determining which of the neighbors of a given vertex is its parent. Whether this is possible without storing the entire tree depends on the problem. When it is possible, you can generate the tree "as you go", which prompts us to reduce the space complexity of the algorithm (perhaps you don't need to store the path from $x$ to $y$, but only to generate it vertex by vertex).

---

If space is at premium, you can save a factor of $k$ by storing only a $k$'th fraction of the vertices. Say that a vertex is *($k$-)special* if the hash of its index is divisible by $k$. Perform the search as above, but only store special vertices. On average, this will cut the number of vertices stored by a factor of $k$. However, it doesn't give you the exact intersection point. Suppose that your sequences contain the special points $x\_{i\_1},\ldots,x\_{i\_a}$ and $y\_{j\_1},\ldots,y\_{j\_b}$, where $x\_{i\_a} = x\_{j\_b}$. To find the exact intersection point, it suffices to consider the small parts $x\_{i\_{a-1}+1},\ldots,x\_{i\_a}$ and $y\_{j\_{b-1}+1},\ldots,y\_{j\_b}$.

If space is still at premium, you can use exponential search followed by binary search. We go over $k=1,2,4,8,\ldots$, and for each value of $k$, determine only the first $k$-special vertex after the initial vertices $x,y$. Suppose that for some $k$, these special vertices coincide. Now generate the sequence of $k/2$-special vertices, until they coincide. Let $x\_{i\_a}=y\_{j\_b}$ be the first time these sequences coincide. Then we can narrow the search down to $x\_{i\_{a-1}+1},\ldots,x\_{i\_a}$ and $y\_{j\_{b-1}+1},\ldots,y\_{j\_b}$. Now we generate the sequence of $k/4$-special vertices, starting at $x\_{i\_{a-1}+1},y\_{j\_{b-1}+1}$ (unless these vertices are the same, in which case we are done); and so on. The running time is still linear, but the space requirements is down nearly to a constant (in expectation).

We can get the space down to a deterministic constant by defining *special* in terms of the depth of a vertex rather than in terms of its index, but depth is not necessarily easy to compute.

# Answer
> 2 votes
Given a tree, you can preprocess it (attaching extra information to each node) so that you can answer least common ancestor queries. A least common ancestor query is this: given two nodes $u,v$, find the lowest node $w$ that is a parent of both of them. Finding the path between two nodes can be reduced to a least common ancestor query: if the least common ancestor of $u,v$ is $w$, then the path from $u$ to $v$ involves going up from $u$ to $w$, then down from $w$ to $v$.

Yuval Filmus's answer may be more useful in practice, but I thought I'd share this connection to a standard data structure in case it is helpful.

---
Tags: time-complexity, trees
---


# Question
Title: How to (Efficiently) Sort a List of Items with Parent/Child Relationship
I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an `_.isDescendentOf(other)` member function that returns `true` when a node is a descendant of another node (they have a list of immediate parents, and can sweep upwards to find grandparents). Some of the items may not have a relationship with one another. I need to sort these items such that **no item comes before an item it is a descendant of**.

Consider items of the format `(a, [b, c])` which indicates that `a` has descendants `b` and `c`. If we had the unsorted list (with an invalid ordering): `[(c, []), (a, [b, c]), (b, [c]), (d, [])]`

Valid orderings would be: `[(a, [b, c]), (b, [c]), (c, []), (d, [])]` or `[(d, []), (a, [b, c]), (b, [c]), (c, [])]`

(Note, `(d, [])` can technically be placed anywhere since it does not have a relationship with the others.)

(Note, `a`, `b`, etc. are randomly-assigned placeholder names and, though they are alphabetically ordered here, in reality they are random.)

I am quite unsure how to achieve this in an efficient way. My (current) solution involves maintaining a list of "placed" and "unplaced" items (the former is empty at the beginning, and the latter initialized with a copy of the unsorted list), and then greedily moving "unplaced" items to the "placed" list when they do not have any ancestors in the "unplaced" list (until the "unplaced" list is empty). That being said... I am curious whether there is a more efficient way to achieve these results. Thanks in advance!

# Answer
> 2 votes
I think you already have implemented some sort of adjacency list representation of a directed graph. You can use a topological sorting (https://en.m.wikipedia.org/wiki/Topological\_sorting) to order the items.

---
Tags: sorting, trees, greedy-algorithms
---


# Question
Title: Bin packing variant for maximizing value in a bin
I'm creating a tool where, given a list of `N` items that have a **volume** (`v`) and a **price** (`p`), it should produce a list `L` that optimally fits as much value as possible into a single bin with a fixed size `V`. `L` does not need to contain all `N`.

My current solution is a heuristic that simply sorts all the items by price-per-volume and iterates over all items, inserting it into the bin if it can. This produces mixed results, so I'm looking to a bin-packing variant to solve this. All of the examples of bin-packing I've seen only seem to optimize for reducing the number of bins.

Is there a specific name for the variant I've described here?

# Answer
This is the knapsack problem. It is NP-complete, so there are no algorithms that are both efficient on all problem instances and always optimal, but there are many different techniques that yield different points in the tradeoff between computation time and quality of the solution.
> 1 votes

---
Tags: packing
---


# Question
Title: why does relabel take O(VE) time total for unit capacity flow networks?
It is well known that for arbitrary flow networks, Goldberg's push-relabel algorithm takes $O(V^2E)$. Part of that comes from $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ relabelling operations per vertex, each taking $O(V)$ time, for a total of $O(V^3)$ for all relabelling operations.

I'm interested in what happens to these bounds when we restrict edge capacities to be 1. It is clear that there are no more non-saturating pushes, so only saturating pushes, of which there are always $O(VE)$, remain.

However, I found a 1995 phd thesis by a student of Goldberg that claims (on p 13) that when edge capacities are 1 (and thus all pushes are saturating), the relabelling portion takes $O(VE)$ time instead of the usual $O(V^3)$.

How does this $O(VE)$ result follow?

# Answer
The $O(VE)$ result actually holds *in general*, not just for unit edge capacity, hence it has nothing to do with edge capacity being 1.

This result is proven in Exercise 26.4-3 of CLRS, and thus the $O(V^3)$ quoted in the question is not tight.
> 1 votes

---
Tags: graphs, network-flow, bipartite-matching
---


# Question
Title: Graph partition that maximize the number of triangles within its parts
Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P\_1, P\_2, \ldots P\_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal?

This seems NP-complete. Was this problem studied before? (I couldn't find anything after searching clique graph partition). Furthermore, I would appreciate a heuristic approach to solve it.

# Answer
> 1 votes
I don't know whether there are any good heuristics, but I can suggest one approach: you could try to use an ILP solver on this task. Introduce zero-or-one variables $x\_{i,v}$, $y\_{i,u,v,w}$, where $x\_{i,v}=1$ means that vertex $v$ is contained in partition $P\_i$, and $y\_{i,u,v,w}=1$ means that $u,v,w$ are a 3-clique in $P\_i$. (Only introduce variables $y\_{i,u,v,w}$ for triples of vertices $u,v,w$ that are a 3-clique in the original graph $G$; all others are effectively hardcoded at 0.) You can add constraints $$y\_{i,u,v,w} \ge x\_{i,u} + x\_{i,v} + x\_{i,w} - 2,$$ $$y\_{i,u,v,w} \le x\_{i,u}, y\_{i,u,v,w} \le x\_{i,v}, y\_{i,u,v,w} \le x\_{i,w},$$ $$\sum\_v x\_{i,v} \le M, \sum\_i x\_{i,v}=1.$$ Then, maximize the objective function $\sum\_{i,u,v,w} y\_{i,u,v,w}$ subject to these constraints, using an off-the-shelf ILP solver.

---
Tags: graphs, optimization, np-complete, heuristics, clique
---


title: Conversion of $\epsilon$-NFA to a DFA

text:
# Question
Title: Conversion of $\epsilon$-NFA to a DFA
So, I was watching a video about the conversion of $\epsilon$-NFA to a DFA. In the resulted DFA, she didn't write the state 4 in any successor set of the sets containing the state 3, and her explanation was that this happens because the state 3 has no outgoing transitions that are labeled with letters from $\Sigma$ in the input NFA. See the following image.

So my question is, if the state 3 had an outgoing transition labeled with 0 in the input NFA (see the 2nd image below), then does the state 3 contribute the states 2,4,5, and 6 in the successor set upon reading the letter 0?

# Answer
> 1 votes
What she actually describing is the following construction. For an $\epsilon$-NFA $ A = \langle Q, \Sigma, \delta, Q\_0, F \rangle$, the intuitive idea is as follows. Consider a state $q$. If there is an $\epsilon$-transition from q to $s$, then whenever we reach q, we can also reach $s$. Yet, there may be $\epsilon$-transitions from $s$, so we also need to take them into account. For every state $q\in Q$, let $EC(q) \in 2^Q$ be the $\epsilon$-closure of $q$ which is formally defined as $EC(q) = \\{s \in Q: \text{ $s$ is reachable from $q$ using only $\epsilon$-transitions}\\}$. In particular, for every state $q\in Q$, $q\in EC(q)$ as a state is reachable from itself by a path of length 0.

Now Given the sets $EC(q)$ for every state $q \in Q$, we define the DFA B as follows. $B = \langle 2^Q, \Sigma, \kappa, \bigcup\limits\_{q\in Q\_0} EC(q), \\{S\in 2^Q: S\cap F \neq \emptyset\\}\rangle$, where $\kappa(T, \sigma) = \bigcup\limits\_{q\in T} \bigcup\limits\_{s\in \delta(q, \sigma)} EC(s)$, for every set of states $T\in 2^Q$, and letter $\sigma \in \Sigma$. That is, given a non-$\epsilon$ transition $\langle q, \sigma, s \rangle$, we move not only to $s$, but also to all the states that are reachable from $s$ via $\epsilon$-transitions.

So indeed, in the first attached image, the state $3$ has no outgoing transitions that are labeled with letters from $\Sigma$, and thus, for every set $T$ that contains state $3$, the state $3$ does not contribute any states in the set $\kappa(T, \sigma)$, for every letter $\sigma$. However, in the 2nd attached image, there is a 0-labeled transition going out from the state 3. So, in the DFA $B$, when you read the letter 0 from a set $T$ that contains the state $3$, then the state $3$ contributes the states $\kappa(\\{3\\}, 0)$ in $\kappa(T, 0)$. Now since $\delta(3, 0) = \\{4\\}$, we have that $\kappa(\\{3\\}, 0) = EC(4) = \\{2, 4, 5, 6\\}$, that is, you're right that the state $3$, upon reading the letter 0, contributes the states $2, 4, 5, $ and $6$.

Important note: she is doing $\epsilon$-transitions removal and the subset construction at the same time. I don't like that at all as it is confusing, also I don't see the formal construction itself in the video. I suggest that you try to do $\epsilon$-removal alone (without determinization). That may give you a better understanding as a start.

---
Tags: finite-automata, nondeterminism
---


# Question
Title: Combinatorial optimization algorithm with constraints and objective function
I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function.

.e.g Say each item in the set has integer-valued properties `A, B, C`. I need to select `n` items (say 2, can pick any item at most once) such that the sum of the property B among all selected items is at least 50 and the sum of all C's is at least 60 (two constraints), and I need to maximize for sum of A.

Where should I start looking? I was pointed towards LP but am unable to formulate it since I'm looking to pick exact items from a set.

# Answer
You can indeed formulate an Integer Linear Program. Let $x\_i \in \\{0,1\\}$ denote whether you select item $i$. For each item $i$ define $f\_a(i)$, $f\_b(i)$, and $f\_c(i)$ as the integer values for the properties $A$, $B$, and $C$.

Then we define the objective function as maximizing $\sum\_{i = 1}^{m} f\_a(i) \cdot x\_i$, given $m$ items in total.

Your constraints are very similar as well, namely $\sum\_{i = 1}^{m} f\_b(i) \cdot x\_i \geq 50$, and $\sum\_{i = 1}^{m} f\_c(i) \cdot x\_i \geq 60$.

Since you can select at most $n$ of those $m$ items, you need to following constraint: $\sum\_{i = 1}^{m} x\_i \leq n$.

You can then easily recover the solution from your variables. Simply check whether $x\_i = 1$, and if so, add item $i$ to your solution.
> 2 votes

---
Tags: combinatorics, linear-programming, knapsack-problems, integer-programming
---


# Question
Title: Minimum number of swaps to make two arrays strictly increasing
I'm trying to understand the solution of the following problem (LC 801):

> Given two arrays, A and B, of the same nonzero length, find the minimum number of swaps (A\[i\] \<--\> B\[i\]) to make A and B strictly increasing.
>
> The solution is guaranteed to exist for the given input data.
>
> Example:
>
> Input: A = \[1, 2, 9, 4, 5, 6\], B = \[7, 8, 3, 10, 12, 13\]
>
> Output: 1 (swap 9 and 3)

The solutions posted by others consider a `dp` array, of size \[2, A.size()\], which is filled as follows:

```
int N = static_cast<int>(A.size());
std::vector<std::vector<int>> dp(2, std::vector<int>(N, N));

for (int ii = 1; ii < N; ++ii) {
  if (A[ii - 1] > A[ii] && B[ii - 1] > B[ii]) {
    dp[0][ii] = std::min(dp[0][ii], dp[0][ii - 1]);
    dp[1][ii] = std::min(dp[1][ii], dp[1][ii - 1] + 1);
  }
  if (A[ii] > B[ii - 1] && B[ii] > A[ii - 1]) {
    dp[0][ii] = std::min(dp[0][ii], dp[1][ii - 1]);
    dp[1][ii] = std::min(dp[1][ii], dp[0][ii - 1] + 1);
  }
}

return std::min(dp[0][N - 1], dp[1][N - 1]);

```

How to think / develop the idea for the solution?

It is clear that in the case the monotony is broken, i.e. A\[ii\] \<= A\[ii - 1\] we need to swap, but, from trying a few test cases, this is not the optimal way to do the swaps.

# Answer
$dp\[b\]\[i\]$ denotes the minimum number of swaps needed to make the first $i$ elements of both arrays strictly increasing where $b$ is a boolean flag denoting whether we've swapped $A\[i\]$ and $B\[i\]$ (or $\infty$ if this minimum doesn't exist).

The key observation is that we only care about what $A\[i-1\]$ and $B\[i-1\]$ are when calculating $dp\[0/1\]\[i\]$. This means that we can calculate $dp\[0/1\]\[i\]$ using only $A\[i-1\]$, $B\[i-1\]$, $A\[i\]$, $B\[i\]$ and $dp\[0/1\]\[i-1\]$ in $\mathcal O(1)$ time. (The recurrences are shown in the code you posted).

The answer is clearly $\min(dp\[0/1\]\[N\])$, and this solution runs in $\mathcal O(N)$ time.
> 1 votes

---
Tags: dynamic-programming, arrays
---


# Question
Title: In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?
Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the symbol 0. Does this mean the computation dies, or does this mean that the string is accepted?

# Answer
A string is accepted by an NFA if there is a sequence of moves such that it can reach a final state at the **end of the string**.

As you said, assume that for $w=0110$ after reading $011$ we are in a final state (called $q$) and there is no transition like $\delta(q,0)$, this is when we encounter a situation called **dead configuration**. At this point we can't just say the machine stops, because it's not precise. What we can say here is that no final state can be reached by reading $w$ so the NFA doesn't accept the string.
> 1 votes

# Answer
Finite automatas (either) DFA or NFA, must be process the entire input string.

DFAs will keep track of a **single state** while processing a string. Think of it as a pointer to the *current* state. It will transition (i.e. move that pointer) according to its rules while processing a string. Remember that for a DFA, all states must have a transition for each symbol in the alphabet. Thus, the DFA will have a unique path to the final state after processing the entire input string. If final state is an accepting state after processing the entire input string, the string is accepted; otherwise, it is rejected.

NFAs on the other hand will keep track of a **set of states** while processing a string. Think of it as having a set of pointers to *all possible* states for which the NFA could have transitioned to after processing a certain number of symbols. This allows for the NFA to not have all transitions defined, the inclusion of $\epsilon$ on transitions, and having a symbol on more than one transition out of a state. If the set of states contains an accepting state after processing the entire input string, the string is accepted; otherwise, it is rejected.

Take the following example:

$L = \\{0,1\\}^\*00^+1 + \\{0,1\\}^\*01^+0$. The following NFA accepts this language.

We can make a chart that shows how the NFA will process an input string. The left column indicates the current set of states (when we start processing we start with `{A}`). The middle column is the set of states possible from the current set of states after processing a `0`, and similarly for the right column with `1`.

```
              0         1
_________ | ________ | _______
{A}       | {A,B,C}    {A}
{A,B,C}   | {A,B,C,D}  {A,C,D}
{A,B,C,D} | {A,B,C,D}  {A,C,D}
{A,C,D}   | {A,B,C,D}  {A,C}
{A,C}     | {A,B,C,D}  {A,C}

```

Suppose we have an input string `001`. The NFA will process the input:

```
0 from {A}       -> {A,B,C}
0 from {A,B,C}   -> {A,B,C,D}
1 from {A,B,C,D} -> {A,C,D}

```

We see that the final set of states is `{A,B,C,D}` which does contain an accepting state. Thus, $001 \in L$. Notices while processing the string, the NFA did not record the way it got to the accepting state; it just records that it is possible to get to one.

Suppose however we have an input string of `0011`. The NFA will process the input:

```
0 from {A}       -> {A,B,C}
0 from {A,B,C}   -> {A,B,C,D}
1 from {A,B,C,D} -> {A,C,D}
1 from {A,C,D}   -> {A,C}

```

We see then that the final set of states is `{A,C}` which does not contain an accepteing state. Thus, $0011 \notin L$.

TL;DR

FAs must process the entire input. For NFAs, if the final set of possible state the machine could end in contains a final state, then the input string is accepted; otherwise, it is rejected.
> 0 votes

---
Tags: complexity-theory, computability, automata, finite-automata, computation-models
---


# Question
Title: State complexity of difference of two languages
Given $A\_1$ \- **DFA** with $n$ states, $A\_2$ \- **NFA** with $m$ states (both over the same alphabet - $\Sigma$). What's the state complexity, i.e. an upper bound for the amount of states of the minimal **DFA**, recognizing the language $L(A\_1)\setminus L(A\_2)=L(A\_1) \cap(\Sigma^\*\setminus L(A\_2))$.

What I thought of: evaluate the state complexity of $\Sigma^\*\setminus L(A\_2)$ (hypothesis: $2^m$). Why? Because an upper bound of $2^m$ can be obtained for a **DFA** to accept the language of $A\_2$. It's also known that the state complexity of the completion $\Sigma^\*\setminus L(A\_{min})$ is $k$, where $A\_{min}$ is an arbitrary minimal $DFA$ with $k$ states. Therefore we can evaluate the upper bound of the minimal **DFA**, recognizing $L(A\_1) \cap(\Sigma^\*\setminus L(A\_2))$ as $n2^m$ (the state complexity of the intersection is simply the product of states).

# Answer
> 1 votes
This is correct, and moreover it is tight for $n = 1$, even for a binary alphabet (but not for a unary alphabet!). Indeed, it is well-known that there are language accepted by $m$-state NFAs which require $2^m$ states for a DFA. Since the DFA complexity of a language and its complement coincide, taking $A\_1 = \Sigma^\*$ we obtain a tight example with $n = 1$ and any $m$.

It is an interesting question whether the bound is tight for all $n$. This is likely the case if we take for $L(A\_1)$ the language $(\Sigma^n)^\*$.

---
Tags: complexity-theory, automata
---


# Question
Title: What is the actual scope of the Halting Problem impossibility result?
Consider the Halting problem : No TM H exists which given any TM and input, decides whether that TM will halt on that input. The usual proof (informally) is that if such an H existed, then a function D(X) = {if H(D,X) then loop; else Halt;} can be constructed, with D(D) leading to a contradiction =\> hence H can’t exist.

However, this proof relies on the fact that H decides Halting for any (TM,Input) pair as input - and so in particular, it can be given (D,D) to decide. But what if we suppose that H decides Halting for everything except D(D). Does the proof fall apart?

It seems that from “H can’t decide D(D)” we jump to the conclusion that “No TM exists that solves the Halting problem for any TM”. While that conclusion is technically valid, maybe there’s a TM that decides Halting for ‘virtually all’ Turing Machines, except a tiny subset - which includes D(D), or possibly D(any input), or even some slightly larger set. The above proof doesn’t preclude that.

Is there a more quantitative statement of the Halting Problem impossibility result - something that gives some measure of how many TMs (or a description/characterization of which ones), out of the set of all possible TMs, no single function can decide whether they halt or not?

To put it another way, maybe it's possible to construct a Halts() function that will be correct on 99.99999…% of its inputs? Or to be more precise, given a Halts() function candidate, we can state something quantitatively, along the lines of : Correctness = $ \lim \limits\_{n \to \infty} \sum\_{1}^{n} \frac {IsCorrect(Halts(n))}{n}$ (where the sum is over the indices of TMs in some fixed enumeration, and IsCorrect returns 1 if Halts(n) is correct). Now we can ask 1) Are there Halts() functions for which this limit exists? 2) Out of those, which ones maximize this limit?

The import of this is that if there's a Halts() function with a correctness close enough to 1, then the Halting undecidability theorem can be viewed as having little practical value and as being more of a curiosity applicable to a tiny subset of degenerate cases. Even though Rice's theorem shows a wide variety of questions that are undecidable because they can be reduced to the Halting problem, for each of those questions individually, the 'Correctness' limit above might still be close to 1, and so again, we'd be able to find algorithms that decide them for all practical purposes (save a few odd cases).

Note: This question is similar to what's asked in "Attempt #3" of this answer, but it doesn't look like that was ever addressed further (i.e. whether there's any research or literature that investigates such a limit).

# Answer
> 4 votes
Let us say that $H$ is a *partial Halting oracle* if it takes as input a pair $(M,x)$ where $M$ is the description of a Turing machine and an input $x$, and:

1. If $H$ terminates and outputs "yes" then $M(x)$ halts.
2. If $H$ terminates and outputs "no" then $M(x)$ does not halt.

In particular, $H$ is allowed to run forever and not give an answer.

Given two partial Halting oracles $H\_1$ and $H\_2$ we may combine their powers by running them in parallel, and if either one ever halts and gives an answer, we output that answer. Let us write $H\_1 \oplus H\_2$ for such a combined partial Halting oracle.

Consider the partial Halting oracle $L$ which works as follows on input $(M,x)$: it simulates the working of $M$ on input $x$, and if the simulation ever terminates, it terminates with output "yes". Then $L$ correctly predicts all cases that halt, and no others.

Given any partial Halting oracle $H$, we can always combine it with $L$ to get a partial Halting oracle $H \oplus L$ that correctly predicts all the halting cases. The only question then is, how good a predictor of non-halting can be implemented.

Define the *non-halting set* $$\overline{K} = \\{(M,x) \mid \text{$M(x)$ does not halt}\\}$$ and for any partial Hlating oracle the set $$S\_H = \\{(M,x) \mid H(M,x) = \text{"no"}\\}.$$ We then have $S\_H \subset \overline{K}$, $S\_H$ is computably enumerable, and $\overline{K}$ is productive. Computability theory teaches us that $\overline{K} \setminus S\_H$ is infinite, i.e., every partial Halting oracle fails infinitely often.

You may try to measure the ratio of $S\_H$ to $\overline{K}$ in some fashion, such as the measure you suggest in the question. However, the problem with all such measures is that they heavily rely on how machines are coded. By passing to a different coding we can maipulate the measure to be whatever number we like, so that is not very helpful. For instance, to get a 99% success rate, use the following coding: a number of the form $100 n$ encodes the machine encoded by $n$ in some standard encoding, while a number of the form $100 n + r$ with $0 \< r \< 100$ encodes a machine that obviously never halts (always the same machine).

---
Tags: turing-machines, undecidability, halting-problem
---


# Question
Title: What does it mean by saying "Asymptotically more efficient"?
What does it mean when we say that an algorithm $X$ is asymptotically more efficient than $Y$ ?

* $X$ will be a better choice for all inputs.
* $X$ will be a better choice for all inputs except small inputs.
* $X$ will be a better choice for all inputs except large inputs.
* $Y$ will be a better choice for small inputs.

---

The link for this question is here .

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/

---

I thought that an algorithm more asymptotically efficient should work for all inputs, but I am not getting the reason behind "It works for all inputs except small ones".

# Answer
First off, both algorithms "work" for all inputs. The question is about performance.

The answers to that question are kind of crappy. One way to say one algorithm is asymptotically more efficient than another is if there is some (problem-specific) input size such that for any larger input size the more efficient algorithm will take fewer "computational steps", usually by some abstract measure, e.g. number of comparisons.

The idea of the answers is that an asymptotically more efficient algorithm *may* still require more steps before that input size. It *can* be the case that the asymptotically more efficient algorithm requires fewer steps for all inputs, but it doesn't need to be the case and in practice usually isn't. So a better wording of the "correct" answer would be "$X$ will be a better choice for all inputs except **possibly** small inputs".

The wording still isn't that great though. First off, many more factors go into deciding what algorithm is a "better choice", but I'll give them that the intent is clear enough in this case. The real issue is "small" and "large". One of my favorite papers is The Fastest and Shortest Algorithm for All Well-Defined Problems. This paper describes an algorithm which given *any* specification of a function and a proof that it can be computed in polynomial time will compute that function in *optimal* time complexity within a factor of $5$ plus an additive term. For example, if I provided it an implementation of bubble sort as the function specification and the simple proof that it was $O(n^2)$, it would produce a sorting algorithm that was $O(n\lg n)$. In fact, it would produce an algorithm that was $5cn\lg n + o(n\lg n)$ where $c$ was the constant factor of the *asymptotically** optimal algorithm. This is amazing. There's just one problem: the ***constant*** *term* – hidden in the $o(n\lg n)$ in this example – renders the algorithm almost certainly completely infeasible for virtually any real problem. What do I mean by "completely infeasible"? I mean the heat death of the universe will happen many times over before that algorithm completes. Nevertheless, for suitably "large" inputs it will be faster than bubble sort. My point is it's almost certainly not physically possible to write down by any means a "suitably large" input, let alone compute on it.

At any rate, how I would word the correct answer would be: "$X$ requires fewer steps than $Y$ on sufficiently large inputs". This is still a bit vague as there are multiple notions of "step" that could apply and an algorithm could be asymptotically more efficient by one metric and less efficient by another. This wording avoids the value judgement of "better choice"; there are many reasons to choose asymptotically less efficient algorithms or even less efficient algorithms when constant factors/terms are specified such as cache-efficiency or implementation simplicity.

* There is a subtlety here. The asymptotically optimal algorithm may have a worse constant factor, $c$, than an asymptotically non-optimal algorithm. I think it will have the best value of $c$ for any asymptotically optimal algorithm, but it's conceivable that to squeeze out a slight gain in asymptotic efficiency, massive complexity is added that significantly increases the constant factor.
> 16 votes

# Answer
"Asymptotically more efficient" means "more efficient for all problems above a certain size". It doesn't say what the "certain size" is, and it doesn't say what happens before that "certain size".

So all the answers except the second one are clearly wrong, because "Asymptotically more efficient" says nothing about small input sizes at all. But the second one is also problematic.

There is currently no hardware that could store an array of $10^{30}$ integers, so clearly $10^{30}$ integers would count as "large input". But I can easily create a sorting algorithm that is asymptotically more efficient than Bubblesort, but only for inputs of $10^{40}$ or more integers. So take answer two, change "large" to "large enough", and it becomes correct.

In practice, it is often a good idea to check for which input size an asymptotically better algorithm is actually faster, and what the required time is for inputs where it is faster, and sometimes an algorithm will only be faster for problem sizes that cannot practically be solved anyway. If algorithm A beats algorithm B, but only for problems where each takes $10^{15}$ years or more, then A isn't very helpful.
> 4 votes

# Answer
What people usually mean when they say something like this is:

> If $T\_A$ and $T\_B$ are the two running-time cost functions of algorithms $A$ and $B$ in model X, respectively, then $T\_A \in o(T\_B)$.

Many caveats apply here: $X$ needs to be specified, and we have to define what "running-time cost" is to mean, exactly. *Time* is almost never the subject of investigation. There are many other cost measures. It is unclear if Landau notation makes any helpful statement about efficiency. And so on.

In particular, none of the statements you propose follow, even though people often suggest the second did.

Sadly, the wider community of people dealing with algorithms embraces terminology that borders on vacuous for the sake of simplicity. (Making precise *and* helpful statements about algorithms is hard!)

You may be interested in our reference questions.

---

> An algorithm X is said to be asymptotically better than Y if X takes smaller time than y for all input sizes n larger than a value n0 where n0 \> 0.

Note how this is *not* the usual definition! If $T\_A(n) = n+1$ and $T\_B(n) = n$, we would not say it's "asymptotically better". Given all the caveats of an analysis that boils down an algorithm's performance down to a single number, no claim that one was "better" than the other can be made.

I recommend you learn computer science from CS resources, not from programmers who have read about stuff on Wikipedia once. (Yes, that's harsh, but I've seen too many falsehoods propagated in programmer circles, even on SO.)
> 3 votes

# Answer
Reason: If two algorithms for the same problem are of the same order then they are approximately as efficient in terms of computation. Algorithm efficiency is useful for quantifying the implementation difficulties of certain problems. • B will be a better choice for all inputs. • B will be a better choice for all inputs except small inputs. • B will be a better choice for all inputs except large inputs. • A will be a better choice for small inputs.
> -1 votes

---
Tags: algorithms, algorithm-analysis, terminology, asymptotics
---


title: How to make a directed graph in python?

text:
# Question
Title: How to make a directed graph in python?
I am working on my own personal project. I took an intro to coding class last semester so I have been exposed to coding but I am still lost with it.

Basically, for my project, I want to build a web map (I'm not even sure if that's the right word for it) using python. Here is an example.

Basically, some numbers will have arrows leading to them and others will have arrows leading out of them. I was wondering if maybe someone knew of any libraries that generated something like this. If not, I was wondering if anyone had any advice on where to start. Or at least can tell me the actual name for this type of graph because I'm not sure if it's actually called a web graph.

Thank you all :)

# Answer
> 1 votes
This looks like a *directed graph*. For a Python graph library, you can have a look at networkx. There are other libraries too, like igraph and graph-tool.

# Answer
> 1 votes
There are many resources for creating Graphs.

If you're a visual thinker you can create the networks with visual online tools download the graph in .graphml format and import it to Python.

Here are some sources: CSacademy, GraphOnline

```
# import the modules
import networkx as nx
import matplotlib.pyplot as plt

# Create the graph
G = nx.read_graphml("filename.graphml", node_type=str)

# Visualize
nx.draw_networkx(G)
plt.show()

```

If you are confident with python you can start with these modules rightaway: Networkx, Igraph, graph-tool

I would recommend Networkx since there are tons of study materials available online!

Happy coding!

---
Tags: graphs, python
---


# Question
Title: What algorithm to use, least waste when sawing wood planks
Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 30cm 50cm and 20cm. Is there an algorithm for calculating the least waste? When using brute force it quickly escalates in time :(

Formally we have $N$ wooden planks each $L\_1, \dots, L\_N$ cm long. And we want to have $M$ pieces, $l\_1, l\_2, \dots, l\_M$ cm long. How to minimize the waste?

# Answer
> 3 votes
This problem can be reduced to the binpacking problem (which is a special instance of the cutting stock problem, see @fade2black's answer)

The bins can represent the fixed size wood pieces, which are 100cm long in your example.

The items to be binned can be the list of needed wood lengths.

Minimizing for the minimal number of bins equates minimizing waste;

* Let $L\_M$ be the size of a bin, $L\_{all} = \sum\_{i=1}^N L\_i$
* Suppose there is a distribution of $L\_i$ over $M\_{min}$ bins, but it is not the minimum amount of waste.
    + Then there is a distribution of $L\_i$ over $M\_{minwaste}$ bins where $M\_{min} \< M\_{minwaste} $
    + And then the waste can be expressed as $\[M\_{minwaste} * L\_M - L\_{all}\] \< \[M\_{min}\*L\_M - L\_{all}\] $
    + which simplifies to: $M\_{minwaste} \< M\_{min} $
    + This contradicts our premise and its derivative of $M\_{min} \< M\_{minwaste}$ .
* Hence, $M\_{minwaste}$ cannot be greater than $M\_{min}$ and have less waste.

---

Python example using the `binpacking` module, note that binpacking is indeed NP-hard, as such the `binpacking` module is most likely using heuristiscs which will most likely result in approximation answers.

```
import binpacking
needed = [60, 30, 50, 20]
print(binpacking.to_constant_volume(needed, 100))

```

Outputs the following:

```
[[60, 30], [50, 20]]

```

# Answer
> 2 votes
This problem seems to be NP-hard. Please check Cutting stock problem. Nevertheless, you could attack it using LP or other approximation methods.

# Answer
> 0 votes
If you find the subject interesting, there is a company that reduces waste by about 10% (according to their marketing material) by cutting trees not into rectangular shapes, but according to the shape of the tree. You order the floor boards for your room size, and you get non-rectangular floor boards that fit together exactly, and must be laid in exactly the right order.

And reducing waste by 10% means they need to process 10% less wood, which directly increases profits.

---
Tags: algorithms, optimization
---


title: How this language belong to R?

text:
# Question
Title: How this language belong to R?
Consider the following language $$L= \\{ \langle M\rangle | \text{ $M$ is a TM, and $L(M)\in coRE$} \\}$$

I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. Indeed, suppose we have a TM $M$, now for input $x$ such that $x\notin L(M)$, it seems that we cannot decide whether $x\notin L(M)$ as $M$ may not halt on $x$.

# Answer
> 1 votes
The language $L$ is not decidable, this is an immediate consequence of Rice's theorem (you can instead try and prove that $L$ is not decidable directly using reductions). To begin with, there are two machines $M\_1$ and $M\_2$ such that $L(M\_1)\in coRE$ and $L(M\_2)\notin coRE$. For example, $M\_1$ can be a machine that accepts all inputs, and $M\_2$ can be a machine that recognizes the language $Halt\_{TM} = \\{\langle M, w\rangle: \text{ $M$ halts on $w$ } \\}$ which is known to be in $RE\setminus coRE$. So the property $P = \\{ M: \text{$M$ is a TM, and $L(M)\in coRE$}\\}$ is a non-trivial property. Also, for every two machines $M\_1$ and $M\_2$ with $L(M\_1) = L(M\_2)$, it holds that $L(M\_1)\in coRE$ iff $L(M\_2)\in coRE$. Thus, either both $M\_1$ and $M\_2$ are in $P$, or both are not in $P$. Hence, the property $P$ is also semantic, and so by Rice's theorem $L$ is not decidable.

Maybe you saw the claim suggesting that $L' = \\{ \langle M\rangle: \text{ $M$ is a TM, and $L(M) \in RE$} \\}$ is decidable, and this follows simply from the fact that $L'$ is the language of all legal encodings of TMs.

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


title: Pumping lemma: why x in ∣xy∣ ≤ p?

text:
# Question
Title: Pumping lemma: why x in ∣xy∣ ≤ p?
Looking at the pumping lemma, I've noticed that in the string $xy^pz$, there seems to be no rule explicitly stated for $x$ and $z$. If I understand correctly, $x$ and $z$ are basically anything on the 2 sides of the string $y^p$ that we're pumping and thus can be anything in $L$.

Rule 2 & 3 of the pumping lemma are:

* $|y| \geq 1$
* $|xy| \leq p$

Since $|x| = 0$ and $|z| = 0$ seem to be allowed, as they only need to be of non-negative length, we shouldn't need $x$ in rule 2 and it can be rewritten as $1 \leq |y| \leq p$.

Are $x$ and $y$ not just a substitute for whatever are on the 2 sides of $y^p$ which we're pumping? Why is $x$ in rule 2 if it doesn't seem to make a difference? If $x$ is necessary, why is there no $|yz| \leq p$?

# Answer
> 3 votes
You said:

> If I understand correctly, $x$ and $z$ are basically anything on the 2 sides of the string $y^p$ that we're pumping and thus can be anything in .

This is not true. The pumping lemma suggests that for every long enough word $w$ such that $w\in L$, there is a partition of $w$ into three words $w = xyz$ such that the three conditions of the lemma hold. You only know that such $x, y$ and $z$ exist, you do not know whether this is true for all $x, y, $ and $z$ that partition $w$. Thus, you cannot force $x$ or $z$ to be empty. In fact, this is far from being true. For example, consider the language of the regex $a b^\*$. Here $y$ cannot contain the letter $a$, thus you cannot force $x$ to be the empty word.

You also said:

> If $x$ is necessary, why is there no $|yz|\leq p$?

This condition is too strong as, along with the condition on $|xy|$, it suggests that every long enough word $w$ in the language, has to be of length at most $2p$, which is not correct. Also, once you have the condition $|xy|\leq p$, there is no need to have a condition on $|yz|$. The pumping lemma conditions come up naturally from how a run of length at least $|Q|+1$ looks. In such long runs, two states have to repeat in the first $|Q|+1$ states of the run, and thus the condition on $|xy|$ arises. You can think about considering the last $|Q|+1$ states in a long run, and that might give you another variant of the pumping lemma (where $x$ and $z$ replace rules) but I don't see how this may be more useful or more appealing than the standard pumping lemma.

# Answer
> 1 votes
I think it might be useful to understand where the pumping lemma comes from and how it can be proven.

If a language $L$ is regular, there exists a DFA that recognizes it$^1%$.
Let $p$ be the number of states in the DFA.
As a word passes through it, the automaton goes through a *sequence of states*, as each symbol is consumed.
For a word $w$, if $|w| \ge p$, then this sequence comprises at least $p + 1$ states, so it *necessarily* contains at least a duplicate.
The sequence might contain multiple distinct states that are repeated an arbitrary number of times, but we choose to focus only on *the first state that gets repeated and its first repetition (i.e. second occurrence)*.

So for these long words, their state sequence looks like this:
$q\_1, q\_2, ... q\_n, q\_r, q\_{r+1}, ... q\_{r+m}, q\_r, ... q\_l\ ^2$
With the following properties:

* $q\_1$ is the initial state
* $\forall i, j \in \[1, n\], (i \neq j) \iff (q\_i \neq q\_j)$ (first n states are distinct)
* $\forall i \in \[1,n\], q\_i \neq q\_r$
* $\forall j \in \[1,m\], q\_{r+j} \neq q\_r$
* $q\_l$ is a final state

We choose to name three parts of the word:

* $x$ is the first part that is consumed through a sequence of states without repetition, i.e. whatever is consumed by going through $q\_1, q\_2, ..., q\_n, q\_r$
* $y$ is the part consumed between the first state that is ever repeated and its first repetition (or second occurrence), i.e. whatever is consumed by going through $q\_r, q\_{r+1}, ... q\_{r+m}, q\_r$
* $z$ is whatever's left, the part consumed after going through the second occurrence of $q\_r$

From here we can extract all the conditions of the lemma:

* $|y| \ge 1$ \- the smallest possible sequence for $y$ is $q\_r, q\_r$; a transition from $q\_r$ back to itself; in a DFA, each transition must consume a symbol
* $\forall k \in \mathbb{N}, xy^kz \in L$
    + for $k = 0$ simply delete everything from $q\_r$ to $q\_{r+m}$; you're left with a valid sequence of states ending in a final state; so whatever word is consumed by it is in the language
    + similarly, you can replace the second $q\_r$ with $q\_r, q\_{r+1}, ..., q\_{r+m}, q\_r$ as many times as you want
* $|xy| \le p$ \- we said we're only interested in the first state to be repeated and its first duplication; so in $q\_1, q\_2, ..., q\_n, q\_r, q\_{r+1}, ... q\_{r+m}, q\_r$ each state is unique except for $q\_r$, so the sequence has length at most $p + 1$, standing for the consumption of at most $p$ symbols.

This third condition is the one relevant to your question; it is true that $1 \le y \le p$ and that can be *inferred* from it. But $|xy| \le p$ is a *stronger* condition that we can prove, so why wouldn't we employ it?

As for what we can say about $|yz|$ \- pretty much nothing from the above. You *could* make a change in the proof and instead of focusing on "the first repeated state and its first duplication", you could instead pick "the last repeated state and its last duplication", which would give you $|yz| \le p$; but doing so, you would lose the part about $|xy|$ \- you can't have both$^3$. Why the pumping lemma is as it is, it's probably just cultural and somewhat arbitrary.

---

$^1$ there actually exists an infinitude of DFAs that recognize it, as you can always add unreachable dummy states. However, things get simpler if we choose to only be interested in the *minimal DFA* \- the one with the smallest number of states.

$^2$ The names $q\_1, q\_2$ etc. do not refer to the actual names of the states, it's just a way to refer to them in the context of this sequence; $n$ and $m$ are some natural numbers, with the only restriction that $n + m \le p - 1$

$^3$ There's a difference between the two pumping lemmas with conditions $|xy| \le p$ versus $|yz| \le p$ and a pumping lemma with a condition $|xy| \le p\ or\ |yz| \le p$ \- while the disjunction one would hold for the same languages, it would require more (unnecessary effort) in its employment

# Answer
> 0 votes
~~The condition $|xy|\leq p$ requires that the selected substring $y$ to be pumped is not too far from the start of the string.~~

~~Consider the language $L = \\{x |x \in \\{0,1\\}^\* x\ has\ equal\ number\ of\ 0's\ and\ 1's \\}$ which can be shown to be a non-regular language via the pumping lemma. To show that this is not regular the usual example string used is $0^p1^p$. With the 2nd condition, no matter how we divide this string, we only get 0's for $y$, so the lemma fails for this. If we just require $1 \leq|y|\leq p$ then we are free to select anywhere in the substring, say $y = 0^{p/2}1^{p/2}$ and pump the substring and pass the lemma.<br>~~

~~The requirement of selecting $y$ not to be far from the start of the string has something to do with the proof that the pumping lemma exists in the first place. So you might want to check it out from some book like Sipser or whatever you are using or here.~~

**Edit: I decided to give my own explanation in case you do not want to read the references**

In the proof of the pumping lemma, given some regular language $L$, $p$ is the number of states of the smallest DFA that recognizes $L$. Say that there exists $w\in L$ such that $|w| \geq p$. Remember that before we even begin consuming $w$, we are already at the start state so technically we have already entered 1 state and there are $p-1$ remaining states that we have not entered yet. But $w$ contains $\geq p$ symbols and reading a symbol will result to entering a state, so it must be that at least one state was entered more that once. This is where the pigeonhole principle is applied.

From above, it must be that the sequence of states entered to consume $w$, from the initial to the final state, contains a cycle. Now, string $w=xyz$ because $x$ represents the substring consumed before entering the cycle, $y$ is the substring consumed in the cycle, and $z$ is the consumed after the cycle.

Given a language $L$ and a string $w$ from it, you do not necessarily need to find the smallest DFA to get $p$. It is known to be there, assuming that $L$ is regular. What you are trying to do is to guess a correct partition of $w$. Finding the correct partition is equivalent to finding the state $q\_i$ where the cycle will begin. Of course, when you find $q\_i$ you cannot start the DFA there since you must begin at the start state (unless of course $q\_i$ is the start state which implies that $|x|=0$). So your simplified bound of $1 \leq y \leq p$ is not enough. Essentially, the substring $x$ is like your offset from the start state to $q\_i$. Since there are at most $p$ states, and you are initially at the start state, you can try to visit at most $p-1$ states until you find $q\_i$ which implies that the length of $x$ is at most $p-1$. Since $|y| \geq 1$, the length of $xy \leq p$

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Complex/Hybrid data structures- do people ever combine structures like graphs and hash tables together?
I just built a LRU cache that combines a hash table and a double linked list. To me it was a brilliant idea to combine those two structures and use the strengths of each together, so it got me thinking, can people or do people combine hash tables with other more complex data structures like trees and graphs? Are there use cases and what would they be called? I don't see much written about these on the usual sites like Wikipedia.

Obviously the hash table gives constant lookup time (or nearly so allowing for collision resolution), and the tree or graph gives you ways and means of doing traversals.

I know you can hang a new tree's parent node from every single hash entry but I mean having one tree main tree or graph overlayed and interconnected with one main hash table

# Answer
I am convinced that **in many practical cases such hybrid data structures are key to effectiveness**, so I like your question pretty much!

There are many examples, and I would like to detail one that makes a **true difference both in practice and in theory**.

First, a bit of context. There are two main data structures for representing graphs: adjacency lists, where we have the list of neighbors for each vertex; and adjacency matrices, where we have a double-entry array in which cell $i,j$ tells if there is an edge between vertices $i$ and $j$.

Let us consider a graph $G$ with $n$ vertices and $m$ edges. In practice, $m$ is generally much lower than its maximal value $\frac{n\cdot (n-1)}{2} \sim n^2$. This makes adjacency lists appealing, because they need only $O(m)$ space, whereas adjacency matrices need $O(n^2)$ space. However, one cannot query edge existence in constant time in an adjacency list representation, whereas one can do this in an adjacency matrix. This is why the two approaches coexist in the wide world of graph algorithms, with some relying on adjacency lists, and some on adjacency matrices.

In some cases, though, **it is possible to take advantage of the best of the two worlds**. This is particularly true when one considers large graphs with heterogeneous degrees. The *degree* of a vertex is its number of neighbors. Heterogeneous degrees mean that there are vertices with only few neighbors, as well as some with many many neighbors. In practice, there are often many nodes with low degree, as well as few nodes with very high degree (and some nodes with intermediate degrees). This leads to the following idea: represent low degree neighborhoods by adjacency lists, and then parsing them is fast (as they are small); and represent each high degree neighborhors by an array of size $n$. If one carefully chooses which degrees are considered small and which are considered large, then it is possible to have a compact graph representation that allows very fast edge existence queries.

I used this approach in triangle listing/counting algorithms (triangles are sets of three vertices all linked together): Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs

In this case, one may formally show that the algorithmic complexity depends on the way vertices are divided into low and high degrees. The practical benefit is huge too.
> 0 votes

---
Tags: graphs, data-structures
---


# Question
Title: Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$
I have found two interesting questions regarding the quotient of languages, described as:

$A/B = \\{ w \text{ | }\exists z \in B, wz \in A\\}$

The first one is:

* Let $A$ and $B$ be regular languages, prove that $A/B$ is decidable

By using the proof from this other question, it can be proved that $A/B$ is regular if $A$ is regular too.

Then, since any regular language is decidable, $A/B$ will be regular (and decidable) too.

The second one is:

* Let $A$ and $B$ be decidable languages, prove that $A/B$ is semi-decidable

I have no idea on how to prove this one, I assume that it's somehow related to $A$ and $B$ being able to stop for any string, whether it's accepted or rejected, but since I don't know whether $A$ is regular or not, I don't know what to do.

# Answer
Let $\Sigma$ be your alphabet. You want to design a Turing machine $T$ such that, given any word $w \in \Sigma^\*$, $T(w)$ accepts if and only if $w \in A / B$. Notice that since you only want to prove that $A/B$ is semi-decidable, $T(w)$ is not required to reject when $w \not\in A / B$.

Since $A$ and $B$ are decidable, you know that there are two Turing machines $T\_A$ and $T\_B$ such that that $T\_A(x)$ (resp. $T\_B(x)$) accepts if $x \in A$ (resp. $x \in B$) and rejects otherwise.

You can then design $T$ as follows:

* For each word $z \in \Sigma^\*$:
    + If $T\_B(z)$ accepts and $T\_A(wz)$ accepts:
        - Accept.
> 2 votes

---
Tags: formal-languages, regular-languages, semi-decidability
---


# Question
Title: Compute several histograms with multiple filter conditions
I have a numerical dataset of $N$ columns ($\approx 150$) and $K$ rows ($\approx 60000$).

On a user interface, you can apply a filter to one or more columns. We can call the number of filters = $Z$ (with $Z \le N$). Those filters are double sliders allowing to get a min/max for the column. For each filter, I would like to compute the histogram by applying all filters except this one.

The simplest method would be for each filter, to apply all other filters in the complete dataset and compute the histogram of this remaining column. That leads to a $O(Z^2)$ filtering on the dataset and poor performance with an important number of $Z$ and also $K$.

Is there a smarter way ? I have a "feeling" there is probably a way in $O(Z)$ but I am not able yet to clear it in my mind to write it :). It looks quite similar to the problem of *the product of an array except self* in term of thinking.

**Maybe a more concrete example may help**

On a e-commerce, you are selling RAMs and you have a filter by:

* *price*
* number of modules
* frequency
* memory size

If you filter the *price* between 100€-200€ and a *frequency* above 3000Mhz, you will mainly have a *memory size* of 16Gb. The benefit of the histogram is to see on the "price" slider, in which direction you may have more result with the smallest change. For example going below 100€ will not provide a lot more result as there is nearly no ram below 90€. However, if you increase to 250€ you may have a lot more choice for this range of frequency. Similarly, if you reduce the frequency, you will end up with more choice (lower frequency is cheaper so maybe 32gb will be available at 200€.

To see that:

* you need to compute the distribution of the price after applying the filter on frequency only
* then compute the distribution of the frequency after applying the filter on price to have the number of product available below 3000Mhz.

The objective is to be able to render something like :

The histogram is available on the complete range of even if there is a filter on this given range (blue section). This is quite simple if there is only 1 filter as you compute only once the histogram but on my case, depending on other filters, this histogram varies.

I hope this example makes it clear.

# Answer
> 2 votes
I'm going to assume that each filter is a predicate on rows that identifies whether that row should be kept or discarded. If so, then yes, this can be solved with many fewer than $O(Z^2)$ applications of the filters. I'll describe two algorithms with different tradeoffs between time vs space: the first applies $O(Z)$ filters but uses $O(ZK)$ memory; the second applies $O(Z \lg Z)$ filters and uses just $O(K \lg Z)$ memory. In both, let $F\_1,\dots,F\_Z$ denote the filters.

# Algorithm 1: minimizing computation time

Here is an algorithm that applies $O(Z)$ applications filters and uses $O(ZK)$ memory. (This corresponds to something like $O(ZK)$ time and $O(ZK)$ memory.) Roughly speaking the algorithm computes a "prefix sum" and a "suffix sum", using two linear scans. In more detail:

1. For each $i$, compute the subset $S\_i$ of rows that are retained if you apply filters $F\_1,\dots,F\_i$.
2. For each $j$, compute the subset $S'\_j$ of rows that are retained if you apply filters $F\_j,\dots,F\_Z$.
3. For each $i$, compute the intersection $S\_{i-1} \cap S'\_{i+1}$; this is the set of rows that are retained if you apply all the filters except for $F\_i$.

Note that step 1 can be done in a linear scan using a total of $Z$ applications of filters, as you can obtain $S\_{i+1}$ from $S\_i$ using a single application of $F\_{i+1}$. Similarly step 2 can be done using $Z$ applications of filters, for a total of $2Z=O(Z)$ applications of filters. Unfortunately you have to store all of $S\_1,\dots,S\_Z,S'\_1,\dots,S'\_Z$, which takes $O(ZK)$ memory.

# Algorithm 2: minimizing memory usage

A divide-and-conquer algorithm can solve the problem with $O(Z \lg Z)$ applications of filters and $O(K \lg Z)$ memory. (This corresponds to approximately $O(ZK \lg Z)$ time and $O(K \lg Z)$ memory.) The algorithm works like this:

1. If $Z=1$ or $Z=2$, the problem is trivial; this is the base case. Otherwise:
2. Compute the subset of rows that are retained if you apply filters $F\_1,\dots,F\_{Z/2}$. Then, recursively apply the algorithm to this reduced set of rows and to the filters $F\_{Z/2+1},\dots,F\_Z$.
3. Compute the subset of rows that are retained if you apply filters $F\_{Z/2+1},\dots,F\_Z$. Then, recursively apply the algorithm to this reduced set of rows and to the filters $F\_1,\dots,F\_{Z/2}$.

Notice that you can compute the subsets of rows in steps 2,3 with $O(Z)$ applications of filters. So, if we let $T(Z)$ denote the number of filter applications used by this algorithm when running on $Z$ filters, we have the recurrence relation

$$T(Z) = 2 T(Z/2) + O(Z),$$

which has the solution $T(Z) = O(Z \lg Z)$. The claimed running time follows; and it's not too hard to see that the amount of memory used is as claimed, too (as there are $O(\lg Z)$ levels to the recursion tree, and you store $O(K)$ records per level of the recursion tree at a time).

# Can we do better?

A natural question is to ask whether it is possible to find an algorithm that is optimal in both time and memory usage: e.g., $O(Z)$ applications of filters and $O(ZK)$ memory. I don't know whether that is possible or not.

---
Tags: algorithms, optimization, filtering-problem
---


# Question
Title: Are there any existing problems that wouldn't be solvable with a halting oracle?
I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible for a Turing machine also shows that it is impossible for a Turing+oracle to decide the Halting Problem for a Turing+oracle. Are there any actual, practical, examples of problems unsolvable by a halting oracle?

Note: by "oracle" I mean oracle for a standard Turing machine, *not* a TM with an oracle itself.

# Answer
Just take a problem whose Turing degree is above $0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above $\Sigma^0\_1$. Examples of such problems (where $\phi\_n$ is the $n$-th partial computable function and $W\_n = \\{k \in \mathbb{N} \mid \text{$\phi\_n(k)$ is defined}\\}$ is the $n$-th computably enumerable set):

* $\\{n \in \mathbb{N} \mid \text{$\varphi\_n$ terminates for finitely many inputs}\\}$ is $\Sigma^0\_2$-complete.
* $\\{n \in \mathbb{N} \mid \text{$\varphi\_n$ is a total function}\\}$ is $\Pi^0\_2$-complete.
* $\\{n \in \mathbb{N} \mid \text{$W\_n$ is a computable set}\\}$ is $\Sigma^0\_3$-complete.

None of these can be solved even if you have a Halting Oracle. For instance, consider the second example, "is $\varphi\_n$ total?" Given $n$ how would the Halting Oracle help us decide whether the Turing machine encoded by $n$ halts on *every* input?

---

**\[Added 2014-06-03\]** For a "practical" aspect of all of this, consider the problem: a programmer has written a function `void charge_credit_card(int card_number, int amount)` and we would like to know whether the function terminates on all inputs. It is *impossible* to write a compiler which can automatically check this in general. Moreover, even if we allow the compiler to ask us questions of the form "does `charge_credit_card` terminate when given input `(k,m)`?", it is still impossible.
> 17 votes

# Answer
Predicting a random oracle is not solvable using, possibly, any kind of hypercomputation.
> -1 votes

---
Tags: computability, undecidability, halting-problem, oracle-machines
---


# Question
Title: If a solution to Partition is known to exist, can it be found in polynomial time?
In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete.

Suppose we are given an instance and we know that it admits an equal-sum partition. Can this partition be found in polynomial time (assuming $P\neq NP$)?

Let's call this problem "GuaranteedPartition". On one hand, apparently one can prove that GuaranteedPartition is NP-hard, by reduction from Partition: if we could solve GuaranteedPartition with $n$ numbers in $T(n)$ steps, where $T(n)$ is a polynomial function, then we could give it as input any instance of Partition and stop it after $T(n)$ steps: if it returns an equal-sum partition the answer is "yes", otherwise the answer is "no".

On the other hand, the GuaranteedPartition is apparently in the class TFNP, whose relation to NP is currently not known.

Which of the above arguments (if any) is correct, and what is known about the GuaranteedPartition problem?

# Answer
> 3 votes
I think the whole misunderstanding comes from an incorrect definition of TFNP. TFNP is for problems like factoring, where there is always a solution. Every integer has a prime factorization, so you don't have to make any restrictions on what inputs are allowed - i.e., every input string of bits represents a number that has a factorization. This is different from a promise, which is more like what you're describing.

Unlike integers and factorizations, there are sets that do not have equal-sum partitions. And if you change the input format to be some strange representation of sets of integers such that every set represented always has a valid partition, then you change the problem entirely. A program that solves this new problem probably couldn't be used to solve the original NP-hard Partition problem.

(GuaranteedPartition is also not a decision problem, so it's not NP-hard either - although a machine that solved GuaranteedPartition could be used to solve anything in NP, as you point out.)

---
Tags: reductions, np-hard, partitions
---


# Question
Title: Computation equivalence of functional and procedural programming
I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural programming (any problem you can solve with one can be solved with another).

I'm curious as to how this conclusion was originally derived, and whether there is a conclusive proof as to this (preferably one that a bit of a newb to lambda calculus like me can understand)

Related: Why are functional languages Turing complete

# Answer
One standard way to prove that a language is Turing-complete is to implement a simulator for a Turing machine (or for any other Turing-complete language) in that language. That is typically straightforward but boring, for most general-purpose languages.

You can find more resources on Turing-completeness in ; see especially, e.g., Is there an algorithm for converting Turing machines into equivalent Lambda expressions?. You might also be interested in Which calculus is based on first-order functions and is Turing complete?, Are there minimum criteria for a programming language being Turing complete?, What does being Turing complete mean?, Are all turing complete languages interchangeable, Clear, complete, proof that a language is Turing Compete?.
> 1 votes

---
Tags: lambda-calculus, functional-programming, turing-completeness, combinatory-logic
---


# Question
Title: Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?
Pure Prolog (Prolog limited to Horn clauses only) is Turing-complete. In fact, a single Horn clause is enough for Turing-completeness.

However, pure Prolog is incapable of expressing list intersection. (Disequality, `dif/2`, would allow it to do it, but `dif/2` is not Horn, unlike equality).

This seems like a paradox, at first glance. Is there a simple explanation?

# Answer
Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means *exactly* that and *only* that.

A list is not a natural number, and list intersection is not a function on natural numbers.

Note: it is, of course, possible to *encode* lists as natural numbers, which would then make list intersection a function on natural numbers. And I have no doubt that, given you chose a suitable encoding of lists, Pure Prolog will be perfectly capable of expressing list intersection.

To put it another way: just because Pure Prolog is not capable of expressing list intersection *using the particular representation of lists* that was chosen for *General Prolog* does not mean that there does not exist a representation of lists more suitable for use with *Pure Prolog* such that Pure Prolog is capable of expressing intersection of *those particular lists*.
> 82 votes

# Answer
Expressiveness is not a criteria of being Turing complete. **Computability** is.

If Pure Prolog is Turing Complete then Pure Prolog can compute the intersection between two sequential sets.

You may not be able to **express** this computation. It may take you several lines of code or even several pages. You may not be able to use the data structure you **prefer**. You may need to resort to a different data structure to represent the list or even resort to files on disk. But it should be possible.

The definition of Turing completeness is strictly:

> Being able to write a program that implements a Universal Turing Machine.

In other words:

> If you can write a Universal Turing Machine emulator in it, it is Turing Complete!

Nothing more, nothing less.

The only reason this definition is considered useful is that for a given computable list of instructions (also called a "language" but most people these days would call it a "program"), there should be at least one Turing Machine capable of parsing it. And it is proven that you can write programs for a Universal Turing Machine that can emulate any Turing Machine. When combined, this means that a Universal Turing Machine can parse anything computable because even if it can't it can execute a Turing Machine eumlator that can parse that thing.

So the theoretical solution for any Turing Complete language incapable of performing a computation is to run a Universal Turing Machine emulator in that language and run a Turing Machine eumlator in that emulator to perform the given computation.

Of course, this is not practical. But Turing Completeness is not about practicality (nor is it about expressiveness), it is only about **possibility**. It is about **computability**.

---

> Side note: I would like to bring to your attention the fact that there is a lot of things in computing that are what I call **beyond Turing complete**.
>
> For example, modern OSes like Linux and Windows and iOS require a computing system that is beyond Turing complete - specifically they require interrupt support. It is possible to write a virtual CPU and run it on a CPU that cannot do interrupt and fake interrupts in software but doing so will fail to work real-time (note: there was a Unix workstation that did something like this but I forgot its name, the CPU did not have interrupts so the computer used two CPUs - one to run the programs and OS and another to monitor hardware and pause the main CPU to handle hardware events thus emulating hardware interrupts - but note that the system is essentially using a second full Turing Machine to implement the thing the main Turing Machine cannot do on its own).
>
> Another example is the Top-Down Operator Precedence algorithm for implementing compilers/parsers. While it can be implemented with any language it is considerably easier to implement it with a language that has first-class functions, a features common in functional languages but uncommon in procedural languages. Heck, even **functions** themselves are beyond Turing complete since they're not part of Universal Turing Machines (though they form the core of Lambda Calculus - the other computing system developed to define computability and computing)
> 4 votes

---
Tags: programming-languages, turing-completeness, prolog, logic-programming
---


# Question
Title: Efficiently finding the maximum pairwise GCD of a set of natural numbers
Consider the following problem:

Let $S = \\{ s\_1, s\_2, ... s\_n \\} $ be a finite subset of the natural numbers.

Let $G = \\{$ $\gcd(s\_i, s\_j) \mid s\_i, s\_j \in S,$ $ s\_i \neq s\_j \\}$ where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$

Find the maximum element of $G$.

This problem can be solved by taking the greatest common divisor of each pair using Euclid's algorithm and keeping track of the largest one.

Is there a more efficient way of solving this?

# Answer
## Solution 1

**Time Complexity:** $\mathcal{O}(n\sqrt{\max(s\_i)})$

Maintain an array, $\texttt{cnt}$, to store the count of divisors. For each $s\_i$, find its divisors and for each $u$ in those divisors, increment $\texttt{cnt}\[u\]$ by one. The greatest GCD shared by two elements in $S$ will be the greatest $u$ where $\texttt{cnt}\[u\] \> 2$.

For each $s\_i$, we only need to check up to $\sqrt{s\_i}$ for its divisors, so the complexity is $\mathcal{O}(n\sqrt{\max(s\_i)})$.

## Solution 2

**Time Complexity:** $\mathcal{O}(\max(s\_i)\log(\max(s\_i)))$

Given a value $x$, we can check whether there exists a pair with GCD equal to $x$ by counting all the multiples of $x$ in $S$ and checking whether that count is at least 2.

With that information, loop through all possible values of $x$ and keep the maximum one with at least two multiples in $S$. This works in $\mathcal{O}(\max(s\_i)\log(\max(s\_i)))$ time since

$$ \sum\_{x = 1}^{\max(s\_i)} \frac{\max(s\_i)}{x} \approx \max(s\_i)\log(\max(s\_i)). $$
> 1 votes

# Answer
For this problem, there exists a simple solution of just counting all divisors for each number, then checking if each divisor matches with a previously counted divisor.

Counting a number's divisors can be done in $\sqrt{x}$ where $x$ is the number. Specifically, all divisor in a given number x can be expressed as divisor pairs, where $z\cdot y = x$ and $z \< \sqrt{x} \< y$ except if $z = y = \sqrt{x}$. This means that by looping through the range $\[1,\sqrt{x}\]$, all divisors (both prime and non-prime) of $x$ can effectively be found.

Checking and storing a divisor could be done with a HashSet or some equivalent.

This algorithm yields an $\mathcal{O}(n\sqrt{\mathrm{max}})$ solution, where $\mathrm{max}$ is the max number in the array.

Comparing this to your $\mathcal{O}(n^2 \log(n))$ solution, this algorithm is more efficient if $n \sqrt{\mathrm{max}}$ \< $n^2 \log(\mathrm{max})$, which simplifies to if $\sqrt{\mathrm{max}}/\log(\mathrm{max}) \< N$.
> 0 votes

# Answer
Here is an efficient algorithm (in ***Python***). *Please find the explanation below.*

```
def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S

    s = set(S)
    m = max(S)

    res = 0
    i = m

    while(i > 0):
        a = i
        cnt = 0
        while (a<=m): # a maxed at max of the list
            if a in s:
               cnt += 1
            a += i

        if cnt >= 2:  # we have found the result
            res = i
            break

        i = i -1

    return res

```

### Explanation of the above code snippet :

We observe the following in this problem:

1. The result can not be more than `max(S)`
2. The result is a number, that has two or more multiples in this list `S`
3. In-fact the result is `max` of all such numbers with the property mentioned above.

With these observations, the program does the following:

1. Make a `set` of the list. As sets can be searched efficiently in `O(log(n))`
2. Find the max of the list and store it in the variable `m`.
3. Starting from `m` till `1`, find the first number that has two or more multiples in the set. The first such number found is the result.

I hope this is clear. Please let me know if you need a more detailed explanation.
> -2 votes

---
Tags: algorithms, number-theory
---


# Question
Title: Convoy effect in priority scheduling and SJF (Non preemptive)
In books, I have read that FCFS suffers from convoy effect. I think that even SJF and priority(both preemptive and non preemptive) can suffer from convoy effect.

In SJF, if a process with large burst time arrives first then no other process can preempt it causing convoy effect.

In preemptive and non preemptive priority, if all processes arrive at time 0 and if a high priority process has very large burst time, it can lead to convoy effect as no other process can preempt this process because they all have lesser priority.

Am I correct?

# Answer
Cant comment but here is some clarification. Using the preemptive sjf, a process with a smaller burst can remove a process with a bigger burst that is currently occupying the cpu, this eliminates the convoy effect but can create a starvation effect whereby shorter procesess keep cutting off long and old processes. A priority based sheduling is efficient if it keeps in account how long a process has been waiting in the wait-queue and also its cpu-burst, a good example is the HRRN method, where the priority of a process is calculated taking in account the afore mentioned criterias. So if the priority
> 0 votes

# Answer
Yes, in SJF and non-preemptive Priority algorithms, convoy effect can occur but only for a relatively small instant (i.e. the burst time of the first process). After that, there is no possibility of convoy effect. So, convoy effect doesn't affect the performance of these algorithms to a great extent. But, in FCFS, convoy effect can occur any number of times and hence, affects the performance greatly. That is why FCFS is said to be "suffering" from convoy effect whereas others are not. Also, in any preemptive algorithm (like SRTF or preemptive Priority algoritm), there is absolutely no chance of convoy effect.
> 0 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes
in my notes I have one fact:

in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at most $\frac{2n}{3}$.

1. Does it work for every binary tree or only when $n$ is divisible by three?
2. How can I quickly prove the fact in my note? A simple idea?

# Answer
> 5 votes
$\DeclareMathOperator\s{size}\def\f#1{\lfloor#1\rfloor}\def\c#1{\lceil#1\rceil}$As already pointed out by gnasher729, the statement is not literally true when $n\equiv1\pmod3$: if $n=3k+1$, there are binary trees of size $n$ whose all subtrees have size either $\le k\<n/3$ or $\ge2k+1\>2n/3$.

A version suitable for all $n$ can be proved as follows. Let $\s(u)$ denote the size of the subtree rooted at $u$.

> **Lemma 1:** If $1\le s\le n$, then every binary tree of size $n$ has a node $u$ such that $s\le\s(u)\le2s-1$.

**Proof:** Let $u$ be a node with $\s(u)\ge s$ such that $\s(u)$ is minimal possible. By minimality, the child subtrees of $u$ have size $\le s-1$ each, hence $\s(u)\le2(s-1)+1=2s-1$. QED

Balancing $\s(u)$ and its complement, we obtain the following.

> **Corollary 2:** In every binary tree of size $n\>1$,
>
> * there is a node $u$ such that $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$, and
> * there is a node $u$ such that $\c{n/3}\le\s(u)\le\f{(2n+1)/3}$.

**Proof:** Using Lemma 1 with $s=\f{(n+1)/3}$, we have $2s-1\le\f{(2n+2)/3}-1=\f{(2n-1)/3}$. Likewise, $2\c{n/3}-1=2\f{(n+2)/3}-1\le\f{(2n+4)/3}-1=\f{(2n+1)/3}$. QED

We can also reformulate it as follows:

> **Corollary 3:** Every binary tree of size $n\>1$ has a subtree such that both the subtree and its complement have sizes between $\f{(n+1)/3}$ and $\f{(2n+1)/3}$.

**Proof:** Taking $u$ with $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$ by Corollary 2, the complement of the subtree rooted at $u$ has size between $n-\f{(2n-1)/3}=\c{(n+1)/3}=\f{n/3}+1$ and $n-\f{(n+1)/3}=\c{(2n-1)/3}=\f{(2n+1)/3}$. QED

Using Corollary 2, the simple bound $n/3\le\s(u)\<2n/3$ works if $n\equiv0,2\pmod3$. It also works for all $n$ if the tree is *full*:

> **Corollary 4:** Every binary tree of size $n\>1$ such that all nodes have $0$ or $2$ children has a node $u$ such that $n/3\le\s(u)\<2n/3$.

**Proof:** In this case, the size of every subtree (including $n$ itself) is odd. By Corollary 2, there is $u$ with $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}\<2n/3$. If $\f{(n+1)/3}\ge n/3$, we are done. The remaining case is that $\f{(n+1)/3}=(n-1)/3$. But here $n-1$ is even, hence $(n-1)/3$ is also even, while $\s(u)$ is odd. Thus $\s(u)\ge1+(n-1)/3\>n/3$. QED

# Answer
> 3 votes
Let us prove that in a binary tree with $n\gt1$ nodes, there is a node $u$ such that $\frac{n}3\le size(u)\le\frac{2n}3$.

Proof: Run the following algorithm.

1. Let $u$ be the root node of the given binary tree.
2. Check the number of nodes in the left subtree and the right subtree of $u$.
    1. If the number of nodes in the left subtree is between $\frac n3$ and $\frac{2n}3$ inclusive, return the left child node of $u$.
    2. If the number of nodes in the right subtree is between $\frac n3$ and $\frac{2n}3$ inclusive, return the right child node of $u$.
    3. If there are more nodes in the left subtree of $u$, assign the left child node of $u$ to $u$. Otherwise, assign the right child node of $u$ to $u$. Go back to step 2.

We claim that whenever the algorithm is entering step 2, $size(u)\gt\frac{2n}3$.

* The first time when the algorithm is entering step 2, $size(u)=n\gt\frac{2n}3$.
* For the sake of induction, assume that $size(u)\gt \frac{2n}3$ when the algorithm is entering step 2 at some moment. We continue to run the algorithm. If it returns at step 2.1 or 2.2, there is nothing more to prove. Otherwise, the algorithm will be entering step 2.3. Then the number of nodes in each subtree of $u$ is not in $\[\frac{n}3, \frac{2n}3\]$. (Otherwise, the algorithm must have returned at step 2.1 or step 2.2.)

+ If there are more nodes in the left subtree of $u$, the number of nodes in the right subtree of $u$ must be $\le\frac{size(u)}2\le \frac{n}2$. So, the number of nodes in the right subtree of $u$ must be $\lt\frac{n}3$. So the number of nodes in the left subtree $u$ must be $\ge size(u)- \frac{n}3\>\frac{n}3.$ That means, the number of nodes in the left subtree $u$ must be $\gt\frac{2n}3$.
    + Otherwise, by similar reasoning, the number of nodes in the right subtree of $u$ must be $\gt\frac{2n}3$.

So, after $u$ is updated at step 2.3, $size(u)\>\frac{2n}3$. In other words, when the algorithm is re-entering step 2 the next time, $size(u)\>\frac{2n}3$.

The claim is proved.

Note that $size(u)$ decreases by at least 1 whenever $u$ is updated. So $u$ cannot be updated forever. That means the algorithm must stop at some time. The only places it stops is at step 2.1 or step 2.2, where node $u$ such that $\frac{n}3\le size(u)\le\frac{2n}3$ is returned.

---

Here are more directed answers to your questions.

1. The conclusion works for every binary tree has more than one node. It does not work for a binary tree with one node.
2. The simple idea is checking whether one of the child nodes satisfies the condition. If not, then recurse to the subtree that has no less nodes than the other subtree.

# Answer
> 1 votes
It’s not true for trees with 3k+1 nodes. There is supposed to be a subtree with k+1/3 to 2k+2/3 nodes, that is k+1 to 2k nodes. Take a tree starting with only left nodes until we have a subtree of 2n+1, and then both sub trees have size n. The theorem fails. So assume n = 3k or n = 3k+2.

n = 3k: We start with N = root of the tree. As long as N has a subtree with more than 2n/3 nodes, replace N with the root of that subtree. This will end eventually, and at that point the tree with root N has more than 2n/3 nodes, and both subtrees have at most 2n/3 nodes. The tree has at least 2k+1 nodes. If both subtrees had less than n/3 nodes, that’s at most k-1 nodes, subtrees plus node would have at most 2k-1 nodes, less than the 2k+1 required.

n = 3k+2: We start with N = root of the tree. As long as N has a subtree with more than 2n/3 nodes, replace N with the root of that subtree. This will end eventually, and at that point the tree with root N has more than 2n/3 nodes, and both subtrees have at most 2n/3 nodes. The tree has at least 2k+2 nodes. If both subtrees had less than n/3 nodes, that’s at most k nodes, subtrees plus node would have at most 2k+1 nodes, less than the 2k+2 required.

The two subtrees have at most 2n/3 nodes, and don’t both have less than n/3 nodes, so one has between n/3 and 2n/3 nodes.

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


# Question
Title: the number of arrangements of N players around a round table, where each player can sit on one of 3 contiguous chairs
Consider the fact that each player can either sit on their desired chair or on the neighbouring chair. Two configurations are distinct if at least one person is sitting in another chair. My attempt For example, if there are 4 players sitting around a circular table there can be 9 distinct arrangements.

1. F1,F2,F3,F4
2. F2,F1,F3,F4
3. F2,F1,F4,F3
4. F4,F2,F3,F1
5. F1,F3,F2,F4
6. F1,F2,F4,F3
7. F4,F1,F2,F3
8. F2,F3,F4,F1
9. F4,F3,F2,F1

Now, I am stuck here. How can calculate this and what about larger values of N such as 50?

I tried using vectors and pushing back every element and do the reverse operators and swap elements but I am not sure whether this is correct or not.

# Answer
> 1 votes
Consider the variant of the problem in which the people are arranged in a segment instead of circle and let $S(n)$ be the number feasible arrangements for $n$ people.

Now lets go back to your original problem, and let's name $C(n)$ the number of feasible arrangements of $n$ people.

Clearly $C(0)=C(1)=1$ and $C(2)=2$, so we will henceforth suppose that $n \ge 3$.

Let's name the people $p\_1, \dots, p\_n$ where the assigned position of $p\_i$ is $i$. If $p\_1$ is sitting in position 1 then the number of possible arrangements of $p\_2, \dots, p\_n$ is exactly $S(n-1)$. Otherwise, $p\_1$ is sitting either in position $2$ or in position $n \neq 2$. We will only consider the former case since the latter one is symmetric. Clearly $p\_2$ cannot sit in position $2$, so he/she must either sit in position $1$ or in position $3$. If $p\_2$ is sitting in position $1$, then the number of possible arrangements of $p\_3, \dots, p\_n$ is exactly $S(n-2)$. Otherwise, $p\_2$ must be sitting in position $3$, which means that $p\_3$ must be sitting in position $4$ (since position $2$ and $3$ are occupied) and, in general, $p\_i$ must be sitting in position $(i \bmod n) + 1$. Since this completely determines everyone's position, this case only contributes $1$ to the total number of configurations.

To summarize, we have that: $$ C(n) = S(n-1) + 2(S(n-2)+1) = S(n-1) + 2S(n-2) + 2. $$

We are left with figuring out what $S(n)$ is. Clearly $S(0) = S(1) = 1$, so we consider $n \ge 2$. In this case $p\_1$ can only sit in position $1$ or $2$. If $p\_1$ is sitting in position $1$ then there are $S(n-1)$ possible arrangements of $p\_2, \dots, p\_n$. If $p\_1$ is sitting in position $2$, then $p\_2$ must be sitting in position $1$ (as it is the only other person that can sit there) and there are $S(n-2)$ possible arrangements for $p\_3, \dots, p\_n$. We hence have: $$S(n) = \begin{cases} 1 & \mbox{if } n \in \\{0,1\\} \\ S(n-1) + S(n-2) & \mbox{otherwise} \end{cases} = \mathcal{F}\_{n+1},$$ where $\mathcal{F}\_{i}$ denotes the $i$-th Fibonacci number. Substituting back, we obtain:

$$ C(n) = \begin{cases} 1 & \mbox{if } n \in \\{0,1\\} \\ 2 & \mbox{if } n = 2 \\ \mathcal{F}\_n + 2 \mathcal{F}\_{n-1} + 2 & \mbox{otherwise} \end{cases}. $$

---
Tags: algorithms, data-structures, dynamic-programming
---