# Question
Title: When binary search algorithm will be $O(1)$
I had an exam today, and there was a question that said:

> Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $O(\log(n))$.

I'm not sure about my answer, but I answered randomly saying that, it can be $O(1)$ when the element I am searching for is at the middle of the array, and it will be $O(\log(n))$ when the element is at the end of the array.

I know my answer might be trivial, but how can I answer a question like this?

# Answer
> Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $(\log n)$.

This is a nice open-ended question to test how well students understand the referred concepts. Here is how I could show my understanding about the conventional binary search.

First, the algorithm time is always $O(\log n)$ in its usually implementation, i.e, an (indexed) sorted array (SA) or a binary search tree (BST) in the RAM model + comparison model (the computation model that is usually used when we talk about binary search). Even if the algorithm happens to find the wanted element in the very first iteration, i.e., comparing the wanted element against the element in the middle of the SA or the root of the BST, it takes $O(\log n)$ time still. Even in the worst time, it takes $O(\log n)$ time still.

Second, the algorithm time will be $O(1)$ when its runs on some particular subsets of the searching problems in some particular ways as illustrated below.

* The number of elements, i.e., the length of the array or the number of elements in BST is bounded by a constant. In this case, even a linear search algorithm will run in $O(1)$ time. Note that the wanted element may or may not be in the given elements.

Note this situation is different from the situation when the number of different values of the element (as used in the comparison) is bounded. We may need $\Theta(\log n)$ steps to find the index of a $2$ in an sorted sequence of $n$ numbers all of which are 1, 2, or 3.
* The wanted element is in the middle of the SA, or in the one-quarter or three-quarter position of the SA, and so on but within a bounded times of iterations. The exact indices of these positions depend on the exact implementation of the binary search. An implementation might check the element at index $(n-1)/2$ first in an array with indices $0,1,\cdots, n$ and odd $n$ or check the element at index $(n+1)/2$ first. The former implementation might need $\Theta(\log n)$ to find the element at index $(n+1)/2$.
* The wanted element is within a bounded depth away from the root of the BST.
* We could construct various special set of searching situations where the time for a particular implementation of the algorithm will be $O(1)$ by reverse engineering. Specifying a constant $c$. Searching an array by binary search algorithm. If it ends with $c$ steps, we include that problem instance. All together we will find a set of problem instances where the binary search algorithm will run within $c=O(1)$ steps.

Here is a shorter version that could be used as a reference answer to the question for grading. Again, only the conventional binary search algorithms are considered.

> The binary search algorithm always runs in $O(\log n)$ time in the usual computation model.
>
> If the wanted element is among the elements that could be possibly compared within $c$ comparisons for some constant $c$, then the algorithm time is $O(1)$. It happens when the number of total elements is bounded by a constant, when the wanted element is the element in the middle of a sorted array of odd length and when the depth of the wanted element is less than a constant where a binary search tree is used.
> 4 votes

# Answer
I thought for a while and come up with the following. Your question is not completely clear but I am answering on the basis of what I have understood.

Assume that the input array $A$ is given of size $n$. Make a binary tree $\mathcal{T}$ out of the input array $A$. The root(say $r$) of the tree will be the element at index $A\[n/2\]$. Note that vertex set of the $\mathcal{T}$ will be the elements of the array $A$. Then break the array into two halves and make left half as the left subtree $A\[1...n/2-1\]$ and the right half $A\[n/2+1...n\]$ as the right subtree of $\mathcal{T}$ by recursively as defined in the second line. At the end you will have a tree $\mathcal{T}$. Let $x$ be the element which we want to search in an array $A$.

Let $\mathcal{D}(x,r)$ denotes the depth of the element $x$ from the root $r$ of the tree $\mathcal{T}$

**Claim:** If $\mathcal{D}(x,r) \le \mathcal{O}(1)$ then binary search will stop within $\mathcal{O}(1)$ time.
> 0 votes

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


# Question
Title: Minimal paths as solution of a linear program of a special network flow
Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$.
We're looking for the shortest s-t-path.

By regarding this problem as a special flow network, we can express this using linear programming as follows :

Minimize the function: $$ \sum\_{e\in E} c\_e\cdot x\_e $$

Under the constraints: $$ \forall v\in V-\\{s,t\\}: \sum\_{e\in in(v)}x\_e -\sum\_{e\in out(v)} x\_e = 0 \\ \sum\_{e\in out(s)} x\_e = 1 \\ \sum\_{e\in in(t)} x\_e = 1 \\ \sum\_{e\in in(s)} x\_e = 0 \\ \sum\_{e\in out(t)} x\_e = 0 \\ \forall e\in E: x\_e \ge 0 $$

Here $c\_e$ are the weights of the edges, $in(v)$ are all edges going into $v$, and $out(v)$ are all edges starting in $v$.

About the correctness:

Let $S$ be a solution to above linear program. As the constraints are the same as for network flows (if we see each edge as having infinite capacity), $S$ is a flow on $G$.

Given that every $s-t$-path fulfills the constraints, we can conclude that if $S$ is an $s-t$-path, then it is an $s-t$-path with minimal costs.

Further, $S$ can't contain any cycle with positive weight, as we could simply remove this cycle from $S$ and end up with a lower-cost solution that fulfills the constraints.

Finally, $S$ has to be an $s-t$-path. Let's assume $S$ wasn't. Given that $S$ is a flow, we know that it has to contain some $s-t$-path. So let $M$ be the set of all $s-t$-paths that $S$ contains.
Then there is a path with minimal costs in $M$ (as $S$ is cycle-free, and therefore there can only be finitely many elements in $M$). Let this $s-t$-path be $p\_{min}$.

If we let $c: M\to \mathbb R $ now be the map that assigns each $s-t$-path in $M$ its cost, we obtian the following inequality: $$1\cdot p\_{min} \le \sum\_{p\in M} \lambda\_p \cdot p \qquad\text{ given that } \forall p\in M: \lambda\_p \ge 0 , \sum\_{p\in M} \lambda\_p = 1$$

Therefore, if $S$ would contain multiple $s-t$-paths, it wouldn't be minimal.

Thus we can conclude, that $S$ is a minimal $s-t$-path.

My question now is: Did I miss something in the proof?

---

Addendum:

It turns out that the above proof needs that each $s-t$-path has a unique cost. Otherwise, there might be no single $s-t$-path with minimal costs. In this case, it can't be shown that the solution $S$ only contains a single of those paths with minimal costs.
However, in this case, by the reasoning above, it still is true that every path in $S$ is optimal. So in this case, we can just pick any path in $S$ as solution (which we can find using e.g. DFS)

Some final (off-topic) remarks:
This whole procedure seems like a lot for a less efficient method to obtain a shortest path. What caught my eye were the following two properties of this algorithm:
$(i)$ Besides the non-negativity constraint, all constraints are actually equalities.
$(ii)$ The algorithm should be easily adaptable to also allow for negative cycles (by putting some linear restriction on the solution, e.g. that the path mustn't be too long, etc.)

# Answer
There is a major flaw in your question: You presented a shortest path formulation and not a special case of a network flow problem.
Your objective function minimizes the cost of the path. The next 5 constraints are the classic flow constraints, which ensure a path between $s$ and $t$. The last constraint is just the bound of variable $x$.

Now, we can start answering your questions:

---

> Given that every s−t-path fulfills the constraints, we can conclude that if S is an s−t-path, then it is an s−t-path with minimal costs.

Correct. It is the shortest path on the defined graph.

---

> Further, S can't contain any cycle with positive weight, as we could simply remove this cycle from S and end up with a lower-cost solution that fulfills the constraints.

The solution of a shortest path problem does not contain a cycle, for obvious reasons.

---

> Did I miss something in the proof?

Sorry, but your proof does not show anything. You are showing that the shortest path is the shortest path.

---

> This whole procedure seems like a lot for a less efficient method to obtain a shortest path

Because you are solving the shortest path problem :)
However, I still recommend you to stick with Dijkstra's algorithm, which is faster than linear programming.

---

> Besides the non-negativity constraint, all constraints are actually equalities.

Yes, good observation. You just have the classic flow constraints (which are all equalities). I recommend you to read the Ahuja's book on network flows (is the best I know, by the way).

---

> The algorithm should be easily adaptable to also allow for negative cycles (by putting some linear restriction on the solution, e.g. that the path mustn't be too long, etc.)

You can do that. However, this constraint lies in enumerating all the cycles of your graph, which cannot be fastly solved.
> 2 votes

---
Tags: shortest-path, linear-programming, check-my-answer
---


# Question
Title: Is it possible to define a DFA for the language of words having exactly one double letter?
Consider the language $\\{ w \in \Sigma^\*~|~ w~\text{contains exactly one double letter}~\\}$. For example, $baaba$ has exactly one double letter, but $baaaba$ has two double letters.

Suggested answer for the case where $\Sigma = \\{a,b\\}$ (even if it's an RE not a DFA): $(\epsilon \cup b)(ab)^\*aa(ba)^\*(\epsilon \cup b) \cup (\epsilon \cup a)(ba)^\*bb(ab)^\*(\epsilon \cup a)$.

# Answer
> 1 votes
In general, if you claim to have found a regular expression for the language, you can follow Thompson's algorithm to convert that expression into an NFA and then using subset construction to convert that NFA into a DFA.

# Answer
> 0 votes
Start by drawing out individually, the DFAs separated by the union and combine both machines together to get a DFA that the language accepts.

# Answer
> 0 votes
The idea of a DFA is that each state of it stands for two kinds of attributes of the strings,

* historical attributes as the string is scanned letter by letter from left to right
* current attributes about the last several letters.

If you want to identify words that contains exactly one double letter by scanning, here are the states and the corresponding attributes.

* $q\_0$, empty word
* $q\_{a}$, no double letter, ending with $a$.
* $q\_{b}$, no double letter, ending with $b$.
* $q\_{da}$, has a double letter, ending with $a$.
* $q\_{da}$, has a double letter, ending with $b$.
* $q\_{dd}$, has two double letters.

Now it should be easy enough to find the transitions between the states given another input letter. Because both history attributes and the last letter are known.

By the way, I recommend strongly that meaningful subscripts be used to tell the attributes associated to the states. Upon seeing $q\_{a}$, I know immediately the strings that reaches this state have no double letter and end with $a$. If it is extended with letter $a$, it goes to the state $q\_{da}$.

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


# Question
Title: How does a predictive coding aid in lossless compression?
I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).

From the example seen below, it's pretty clear that by pre-processing the image with predictive coding, we've modified its histogram and concentrated all of its grey levels around 0. But why exactly does this aid compression?

Is there maybe a formula to determine the compression rate of Huffman, knowing the standard deviation and entropy of the original image? Otherwise, why would the compression ratio be any different; it's not like the range of values has changed between the original image and pre-processed image.

Thank you in advance,

Liam.

# Answer
Huffman coding, as usually applied, only considers the distribution of *singletons*. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per singleton, where $H(\cdot)$ is the (log 2) entropy function.

In contrast, predictive coding can take into account correlations across data points. As a simple example, consider the following sequence: $$ 0,1,2,\ldots,255,0,1,2,\ldots,255,\ldots $$ Huffman coding would use 8 bits per unit of data, whereas with predictive coding we could get potentially to $O(\log n)$ bits for the entire sequence.
> 7 votes

---
Tags: image-processing, data-compression, huffman-coding
---


title: Language decidable or not?

text:
# Question
Title: Language decidable or not?
I have just began with my course of complexity and computability and I need your experience to help me progress !!

Something is not clear for me:

It is asked to determine if L1 is decidable or not, below the language is an answer given by a student. And I'm not agree with it...

The Rice theorem is given as follow :

I don't get why L1 is decidable since, for me, it looks like the Rice theorem could be immediately applied.

Did I understood very badly or am I right ? In the first case, why ?

Thanks in advance for your help !

Elia

# Answer
> 3 votes
Rice's theorem only applies for nontrivial properties, which are properties which are not always true or not always false. Your property is trivial, since it's always true.

---
Tags: complexity-theory, computability
---


# Question
Title: If A is polynomial time reducible to B does that imply not(A) is polynomial reducible to not(B)
$A\leq\_p B \iff \bar{A}\leq\_p \bar{B}$ (if A is polynomial time reducible to B does that imply that complement of A is polynomial reducible to complement of B)

I was told that this is the case based on the definition of $\leq\_p$ but I am having trouble proving this.

# Answer
In case you were wondering, the answer is yes.

Here is the reasoning.

**Lemma**: Let $f$ be a reduction from $A$ to $B$. Then $f$ is also a reduction from $\overline A$ to $\overline B$.
**Proof**: By the definition of a reduction, $f$ maps $A$ to $B$ and $f$ maps the complement of $A$ to the complement of $B$. So $f$ maps the complement of the complement of $A$, which is $A$ itself, to $B$, which is the complement of the complement of $B$. By the definition of a reduction again, $f$ is a reduction from the complement of $A$ to the complement of $B$. QED.

Suppose $A$ is polynomial-time reducible to $B$. Let $f$ be a polynomial reduction from $A$ to $B$. The lemmas shows that $f$ is also a reduction from the complement of $A$ to the complement of $B$. Since $f$ is polynomial-time, $\overline A$ is polynomial-time reduced to $\overline B$ by $f$.

With $A$ replaced by $\overline A$ and $B$ by $\overline B$, the above paragraph also shows $\overline A$ is polynomial-time reducible to $\overline B$ implies $A$ is polynomial-time reduced to $B$.

The above two paragraphs shows the equivalence of $A\leq\_p B$ and $\overline{A}\leq\_p \overline{B}$.
> 3 votes

---
Tags: complexity-theory, np-complete, np-hard, np
---


title: expected length of linked list

text:
# Question
Title: expected length of linked list
Consider a datatype whose objects will be sequences of elements that has the following two methods

prepend($x, T$) which will insert an element to x to the beginning of the sequence T

search($T, i$) which returns the ith element in the given sequence

T is a linked list. prepend takes $1$ step. Search takes $i$ steps

Suppose T has exactly one element and a sequence of n operations are performed. You are given that prepend has probability $p$ and search has probability $1-p$ for each operation. The value of $i$ is chosen uniformly from $\[1, \dots, T\]$

Q) Derive the expected length for the linked list just before the k'th operation is performed

---

so we need the weighted average of all possible values of some random variable. for each $X\_i$ let it be the number of steps for given events. If theres a prepend we add a node whereas if theres an access we do nothing to the length. How do we come up with an equation for expectd length?

$E(X) = something \cdot (k-1)$ since just before $k$ but not sure how to derive the probability yet

Any help appreciated

# Answer
> $E(X) = something \cdot (k-1)$

That $something$ is $p$. The full formula should be $E(Y)=1+p(k-1)$, where $Y$ is the random variable that is the length for the linked list just before the $k$-th operation is performed.

To convince yourself that $p$ is the right answer, try a few cases. When $p=1$, every operation adds one element to $T$. When $p=0$, no prepend operation will happen. When $p=1/2$, an element is added about half of the times. Make sense?

Here is the simple reason why. Let $Y\_i$ be the increase of length in step $i$. Then

* $Y\_1, Y\_2, \cdots, Y\_n$ are independent random variables,
* $E(Y\_i)=p$ for all $i$ since the probability of prepending is $p$ for each operation.

Since the expectation of the sum is the sum of the expectations for independent variables, we have $$\begin{align} E(Y) &=E(1+ Y\_1+ Y\_2+ \cdots+ Y\_{k-1})\\ &=1+ E(Y\_1)+E(Y\_2)+\cdots+E(Y\_{k-1})\\ &=1+ p(k-1) \end{align}$$ where 1 comes from the initial one element in $T$.
> 1 votes

# Answer
You can break this down into basics. Recall that the expected value of the length will be the sum of all possible lengths multiplied by their probability: $$\mathbb{E}\[L\] = \sum\_{i = 0}^{k-1} i \cdot P(L = i)$$

The probability $P(L = i)$ is the probability of length being equal to $i$ after $k-1$ operations. This means exactly $i$ of the $k-1$ operations would've been `prepend` and $k - 1 - i$ operations would've been `search`. The probability of this will be:

$$P(L = i) = p^{i} \cdot (1 - p)^{k - 1 - i} \cdot N(i, k - 1)$$

Where $N(i, k - 1)$ is the number of ways we can do $i$ `prepends` out of the `k-1` total operations. Consider that there are multiple orders to those operations (e.g. {`prepend`, `prepend`, `search`} and {`prepend`, `search`, `prepend`} both reach length 2). We can "choose" $i$ of the $k - 1$ operations to be `prepend` then the rest will be `search`, thus we have:

$$N(i, k - 1) = \binom{k - 1}{i}$$

Now we can plug this back in:

$$\begin{align\*} \mathbb{E}\[L\] & = \sum\_{i = 0}^{k-1} i \cdot p^{i} \cdot (1 - p)^{k - 1 - i} \cdot \binom{k - 1}{i} \end{align\*}$$

You can see this is clearly the expected value of a binomial distribution and we get:

$$\mathbb{E}\[L\] = p \cdot (k-1)$$

(See here if you want to work through these last two steps precisely).
> 1 votes

---
Tags: probability-theory
---


# Question
Title: Deriving the expected number of steps that is taken to perform the k'th operation
Consider a datatype whose objects will be sequences of elements that has the following two methods

prepend($x, T$) which will insert an element to x to the beginning of the sequence T

search($T, i$) which returns the ith element in the given sequence

T is a linked list. prepend takes $1$ step. Search takes $i$ steps

Suppose T has exactly one element and a sequence of n operations are performed. You are given that prepend has probability $p$ and search has probability $1-p$ for each operation. The value of $i$ is chosen uniformly from $\[1, \dots, T\]$

Q) Deriving the expected number of steps that is taken to perform the k'th operation

---

This would be the average of all possible events so number of search and prepends to the expected length. Expected length is given to be p (k-1). Derived from below

expected length of linked list

search takes i steps (probability 1-p). Prepend takes 1 step (probability is p ).

$E(X) = search(1) + search(2) + \cdots + search((p(k-1)))$

Not sure how to get an exact value for it

# Answer
> 1 votes
Let $N\_i$ be the random variable denoting the length of $T$ prior to the $i$th operation. You should be able to calculate $\mathbb{E}\[N\_i\]$.

The expected running time $T\_i$ of the $i$th operation is $$ p \cdot 1 + (1-p) \cdot \frac{1+\cdots+N\_i}{N\_i} = p + (1-p) \frac{N\_i+1}{2}. $$ Given $\mathbb{E}\[N\_i\]$, you should be able to calculate $\mathbb{E}\[T\_i\]$ using this formula.

I leave you to figure out all remaining details.

---
Tags: probability-theory
---


# Question
Title: A problem to maximize the number of edges in a cycle while minimizing the total weight
I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this?

Consider a graph $G$ that consists of an undirected bipartite graph and another vertex $O$ that is connected to all the other vertices. Assume the weight of the edges are positive and the weights obey the triangle inequality. Find a cycle in $G$ that involves $O$ s.t. the total weight is $\leq$ some given value $t$ and maximize the total number of vertices it passes through.

# Answer
> 2 votes
This is NP-complete, since an instance $(V,E)$ of the NP-complete problem Hamiltonian Path can be reduced to it: Turn each vertex in the original HP instance into a pair of vertices $a\_i, b\_i$ connected by a low-weight edge, with one vertex in each part of the bipartite graph, and add a high-weight edge $a\_ib\_j$ for each edge $v\_iv\_j$ in the original graph. Finally add $O$. Solve your instance and delete $O$: the original graph has a HP iff $2|V|−1$ edges remain.

All this is to say there is almost certainly no polynomial-time algorithm to solve your problem (since if there was, Hamiltonian Path, and every other NP-complete problem could also be solved in polynomial time). Adapting an algorithm for solving TSP sounds reasonable to me.

---
Tags: algorithms, graphs, graph-traversal, traveling-salesman, branch-and-bound
---


# Question
Title: Non-existence of PSPACE-hard unary language
I'm trying to prove that unless $\mathsf{P}=\mathsf{PSPACE}$, there is no unary language which is $\mathsf{PSPACE}$-hard.

Assuming there is an unary language $A$ which is $\mathsf{PSPACE}$-hard, it doesn't seem reasonable to solve $A$ in polynomial time. How can this be proved then?

# Answer
> 5 votes
Suppose that $A$ is a unary PSPACE-hard language. We will show how to solve TQBF, a PSPACE-complete language, in polynomial time.

Recall that an instance of TQBF is a quantified formula of the form $\psi = \exists x\_1 \forall x\_2 \exists x\_3 \forall x\_4 \ldots \phi(x\_1,\ldots,x\_n)$, where $\phi$ is an arbitrary propositional formula. The instance is a Yes instance if the formula is valid.

We construct a binary tree which will represent the truth value of $\psi$. We do it level by level. Each vertex in the tree corresponds to a partial assignment of $x\_1,\ldots,x\_n$. At the root, we just write the empty assignment.

Suppose that we have constructed the $i$‘th level, where $0 \leq i \< n$. We construct the $(i+1)$’th level as follows. For each vertex $\alpha$ on the $i$’th level, we add two children, $\alpha \cup \\{x\_{i+1} = 0\\}$ and $\alpha \cup \\{x\_{i+1} = 1\\}$. For each new vertex $\beta$, we consider the formula $\psi\_\beta = Q x\_{i+2} \ldots \phi(\beta,x\_{i+2},\ldots,x\_n)$. We apply the polytime reduction from TQBF to $A$ on $\psi\_\beta$, obtaining a “truth value” $t\_\beta$; note that there are only polynomial many possible values for $t\_\beta$. These truth values may repeat; for each truth value $t$, we pick one vertex of that truth value (“live vertex”), and point all other vertices (“shadow vertices”) having the same truth value to that vertex; we won’t add new children to the shadow vertices in the next step.

After $n$ such steps, all the (polynomially many) leaves are labeled by complete truth assignments $\gamma$ to $x\_1,\ldots,x\_n$. We can evaluate $\psi\_\gamma$ directly, and so obtain the real truth values of all live vertices on the $n$’th level, and deduce the real truth values of all shadow vertices on the $n$’th levels. From these we can deduce the real truth values of all live vertices on the $(n-1)$’th levels, and hence of all shadow vertices on that level; and so on. Eventually, we will find the truth value of $\psi$.

Since each level contains only polynomially many vertices, this algorithm runs in polynomial time. It follows that $\mathsf{P}=\mathsf{PSPACE}$.

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Maximal Minimum Spanning Tree by Removing $k$ Edges
The problem is as follows:

> Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0 \< k \< |E| - |V| + 1$. Describe and analyze and efficient algorithm to remove *at most* $k$ edges from $E$ such that the resulting graph $G' = (V, E' \subseteq E, w)$ has a maximal weight minimum spanning tree over all possible $G'$.

I initially thought a greedy algorithm would work with "just remove the $k$ smallest edges as long as the graph remains connected." However, this does not work, consider the following graph and $k = 1$:

The MST of $G$ has weight 9. If we remove the minimal edge $(B, C)$, the MST of the resulting graph has weight 12. However, if we remove the edge $(A, B)$, the MST of the resulting graph has weight 13. So this greedy strategy does not work.

---

Other strategies, we can first note that it only helps to remove edges that are in the MST of $G$ initially. So we can first determine $T = MST(G)$. The next (inefficient) thing we could do is consider each edge in $e \in T$ and do:

1. Remove $e$ from $T$, cutting $T$ into $T\_1$ and $T\_2$.
2. Determine the next smallest edge $e'$ spanning $T\_1$ and $T\_2$ in $G$.
3. Keep track of $e$ such that it maximizes $w(e') - w(e)$.

Repeat this $k$ times. This doesn't seem very efficient though. This would be something like $O(k \cdot n \cdot (n + m))$ I think. We could optimize this a bit by keeping track of an ordered set of edges on the cuts.

I am wondering if there exists an algorithm that is $O(km \log n)$ or better. Any approaches / advice would be appreciated.

# Answer
> 3 votes
This is known as the $k$ most vital edges for the minimum spanning tree problem. It has been proved as NP-hard \[1\].

For fixed $k$, Weifa Liang proposed an $O\left(n^k\alpha((k+1)(n-1),n)\right)$ algorithm where $\alpha$ is a functional inverse of Ackermann’s function \[2\], and can be improved to $O\left(n^k\log\alpha((k+1)(n-1),n)\right)$ using Seth Pettie's sensitivity analysis \[3\].

---

\[1\] Frederickson, G. N., & Solis-Oba, R. (1999). Increasing the weight of minimum spanning trees. *Journal of Algorithms, 33*(2), 244-266.

\[2\] Liang, W. (2001). Finding the k most vital edges with respect to minimum spanning trees for fixed k. *Discrete Applied Mathematics, 113*(2-3), 319-327.

\[3\] Pettie, S. (2005, December). Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In *International Symposium on Algorithms and Computation* (pp. 964-973). Springer, Berlin, Heidelberg.

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


# Question
Title: Empirical evidence for the Church-Turing thesis in other disciplines
I am aware of the fact that, since the concept of "effectively calculable function" is not rigorous or formally definable, the Church-Turing thesis may not be proven by symbolic or formal reasoning alone.

My impression, though, is that under the domain of physics, philosophy, cognitive science or other disciplines, we may find empirical evidence that gives us a strong reason for accepting it, for instance in the field of numerical cognition. Even if those disciplines are not directly related to computer science, the importance of this thesis in CS make this, in my opinion, an important issue to consider for us; that's why I'm asking this question here. (If you feel like there are better SE suited for this questions, let me know please.)

So, what is the current state of the research for evidence to support the Church-Turing thesis? Are there any recent developments?

A good answer would also provide a list of all the major efforts to this day to empirically validate or refute the CT-Thesis, and the main problems posed by this issue. Investigations on the notion of "effectively calculable" in cognitive science, or what does it mean to "compute" in physics are also welcome.

# Answer
Proof is an inherently mathematical concept. "Effectively calculable function" has no definition in mathematics and you can't prove something that doesn't have a definition.
> 1 votes

---
Tags: church-turing-thesis
---


# Question
Title: Are two CCS processes equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas?
I was skimming this recent paper and I was struck by the following statement:

> two processes are equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas

I have trouble believing it.

I reason that:

1. weak bisimilarity does not account for tau-transitions and therefore is oblivious to the possibility of livelocks.
2. I believe the possibility of a livelock *can* be represented in HML,

and, therefore, a counterexample can be constructed.

Consider these processes:

```
One = lol.One;
A = lol.omg.A + zomg.A;
B = 'omg.B + 'zomg.B;
Two = (A | B) \ {omg, zomg};

```

Consider, furthermore, the HML formula

```
Livelock = max(X. <tau>X);

```

I believe that this formula is satisfied only by Two, which nevertheless is weakly bisimiliar to One.

I have tried to use the Edinburgh Concurrency Workbench to confirm my reasoning:

```
agent One = lol.One;
agent A = lol.omg.A + zomg.A;
agent B = 'omg.B + 'zomg.B;
agent Two = (A | B) \ {omg, zomg};
prop Livelock = max(X. <tau>X);
******
echo "Is One strongly bisimilar to Two?";
strongeq(One, Two); ********************* outputs "false"
echo "Is One weakly bisimilar to Two?";
eq(One, Two);       ********************* outputs "true"
echo "Is it the case that One |= Livelock?";
checkprop(One,Livelock);  *************** outputs "false"
echo "Is it the case Two |= Livelock?";
checkprop(Two,Livelock);  *************** outputs "true"

```

So, is it the case that *two processes are equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas*?

* If so, why is this true, and what's the flaw in the counterexample, above?
* If not, what did the authors mean or what sort of context am I missing? (Or was it a typo?)

# Answer
(This probably does not fully answer, but I think it can still help)

According to their Def. 4, there is no modality $\langle \tau \rangle$ in their HML logic. Their syntax only allows $\langle\\!\langle u \rangle\\!\rangle$ where $u \in A \cup\\{\epsilon\\}$, and $\tau$ is assumed not to be in $A$ (Def. 1), hence $u\neq\tau$.

Also, there seems to be no recursion allowed in their logic.

Further, as far as I can see, in the Concurrency Workbench `<a>` indicates a strong possibility, while `<<a>>` indicates a weak possibility.

I can't recall which variant of the HML logic precisely corresponds to weak bisimilarity, but I think that it can't involve a strong `<tau>` modality since otherwise we would distinguish `lol` and `tau.lol`.
> 1 votes

---
Tags: concurrency, model-checking, pi-calculus, ccs
---


# Question
Title: Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity
I was instructed to create a pushdown automaton described in the title. Basically, the pushdown automaton accepts strings of the form $x\\#y$ where $x$ and $y$ are strings of 1s and 0s such that there must be at least one difference and at least one similarity between $x$ and $y$. Here is the meaning of one similarity. Let $x=x\_1x\_2\cdots x\_m$ and $y=y\_1y\_2\cdots y\_n$, where $x\_1,x\_2 \cdots, x\_m, y\_1,y\_2, \cdots, y\_n\in\\{0,1\\}$, then there exists an index $i$ such that $x\_i=y\_i$.

I understand that I must have two separate cases, with one case assuming that $|x| = |y|$ and one case where $|x| \not= |y|$. Right now I am only working on the case where $|x| = |y|$. So far, I am using nondeterminism to find the $i$-th value of $x$, matching it against the $i$-th value of $y$. However, this only determines if there is at least one difference between $x$ and $y$. I am failing to see a solution where I can also determine that there is at least one similarity. If anybody can point me in the right direction, it would be much appreciated.

# Answer
Here is the critical observation. We can combine the two conditions, there must be at least one difference and there must be at least one similarity between $x$ and $y$ into the following one condition.

---

Let $x=x\_1x\_2\cdots x\_m$ and $y=y\_1y\_2\cdots y\_n$, where $x\_1, x\_2,\cdots, x\_m,y\_1, y\_2,\cdots, y\_n\in \Sigma$. Then $x\\#y$ is a word in the language if and only if there exists an index $i$ such that

* $x\_i\not=y\_i$ and $x\_{i+1} =y\_{i+1}$ or,
* $x\_i=y\_i$ and we do not have $x\_{i+1} =y\_{i+1}$.

The precise meaning of "we do not have $x\_{i+1} =y\_{i+1}$" is either exactly one of $x\_{i+1}$ and $y\_{i+1}$ is defined or $x\_{i+1}\not= y\_{i+1}$.

---

The basic motivation of the idea above is that an PDA can only keep track of one unbounded counter. So we should compress two unbounded counters, the index of the similarity and the index of the difference into one unbounded counter.
> 1 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Distinct elements count of huge multiset
I know that *HyperLogLog* can approximate the distinct elements count of a huge multiset but I was wondering if it was possible, using a method I saw mentioned on an IRC channel, to get an exact answer while still using significantly less space than a traditional approach.

Would the following work to compute the exact (not approximate) distinct elements count of a huge multiset?

The idea is to use a *Bloom filter* twice, first processing the data one way, and then in reverse and additionally using a map (whose size is much smaller than the huge multiset -- this property is provided by the Bloom filter).

```
1st pass
create an empty bloom filter
create an empty map
for each element from the multiset
    if already in the bloom add to the map with key element / value 0
    else add to the bloom

```

Second pass is nearly identical but elements from the huge multiset are processed in reverse (multiset doesn't need to be an ordered set: it simply needs to have its elements iterated from the end to its beginning).

```
2nd pass
    empty the bloom filter (but not the set)
    for each element from the multiset (but processed this time in reverse order)
        if already in the bloom add to the map with key element / value 0
        else add to the bloom

```

At this point the map contains a list of potentially, but not necessarily, clashing entries in the multiset. So the entries are all set to zero.

```
3rd pass
   cnt = 0
   for each element in the multiset
       if present in the map, increment value in that map for that key
       else increment cnt

```

Exact cardinality is now equal to `"cnt + nb entries in the map whose value is 1 or greater"`.

This requires three passes but uses space identical to a *Bloom filter* plus a map to count the x% of entries the *Bloom filter* couldn't answer if they were present or not.

I hacked a quick proof of concept and did some generative testing and it seemed to give the correct answer but I'm really not sure.

Is it possible to compute the exact distinct element count of a huge multiset this way?

# Answer
> 3 votes
Let me simplify your third step: count the number of elements in your multiset which are not in the map, and add to it the number of elements in the map.

Suppose that your elements are $x\_1,\ldots,x\_n$. For a given hash $h$, let $x\_{i\_1},\ldots,x\_{i\_\ell}$ be the elements hashing to $h$ (in order). If $\ell = 1$, then the elements won't be added to the map in the first or second step. Otherwise, elements $x\_{i\_2},\ldots,x\_{i\_\ell}$ will be added to the map in the first step, and elements $x\_{i\_{\ell-1}},\ldots,x\_{i\_1}$ will be added to the map in the second step.

In total, this shows that after the first two steps, the map will contain all elements whose hash appears more than once.

After the third step, *cnt* will contain the number of elements whose hash appears exactly once. All of these elements are distinct, and also distinct from the elements in the map. You then add to *cnt* the number of elements present in the map, and so obtain the number of distinct elements.

---
Tags: algorithms, sets, bloom-filters
---


# Question
Title: Interactions between predictive analytics, ML, and case-based and rules-based reasoning
For my studies on economy, I work on prediction of judicial decisions. I don't really understand the interactions between several concepts:

* predictive analytics
* machine learning
* case-based reasoning
* rules-based reasoning

At the moment, I understand that predictive analytics is an area of statistics that deals with extracting information from data and using it to predict a outcome, like a judicial decision. In predictive analytics there are 2 kinds of tools: econometric tools like MCO regression and machine learning tools like neural networks.

Among ML tools, we can distinguish between 2 approaches: rules-based reasoning and case-based reasoning. Given a given legal problem, with the rules approach, the algorithm learns the rules that led to these data, deduce a linear model and then we can confront the problem to the model to deduce the solution given by a court. With cases approach, the algorithm brings the given problem closer to similar cases found in the data, and deduces a solution given by a court.

Is it correct?

Are different kind of ML tools like K-NN or neural network only used for one type of reasoning? or they can be used for both?

# Answer
Personally, I'm not enamored of the "rules-based reasoning vs case-based reasoning" categorization; I'm not sure it is a particularly useful mindset for modern machine learning. For instance, deep learning is one of the most effective ML methods used today in several domains, yet it doesn't seem to fall into either of those categories. That's just my opinion.

Rather than trying to find this kind of high-level generalization about how ML works, I think it might be more useful to study some specific ML techniques: linear regression, k-nearest neighbors, SVM, random forest, deep learning, etc.
> 0 votes

---
Tags: machine-learning, case-based-reasoning
---


# Question
Title: Context Sensitive Grammar for the language $\{a^n b^n c^{2+k}\mid n \ge 1, 0 \le k\le 1\}$
I'm studying for my final exam and come up with this exercise with no idea how to find the production rule of this grammar.

I need help. Thanks all of you! :)

# Answer
Here is the hint.

### The grammar of a union is the union of the grammars.

That is, the grammar for $L\_1$ and $L\_2$ is the "union" of $G\_1$ and $G\_2$, where $G\_1, G\_2$ is the grammar for $L\_1$ and $L\_2$ respectively. Instead of a formal definition, let me use an example to illustrate the meaning of the strategy.

Suppose the grammar for language $L\_1$ is:
$\quad S\to aSbS \mid ST \mid \epsilon$
$\quad T\to Tab \mid \epsilon$
Suppose the grammar for language $L\_2$ is:
$\quad S\to bSaS \mid T $
$\quad T\to aT \mid \epsilon$
Then the grammar for $L\_1\cup L\_2$ is:
$\quad S\to S\_1 \mid S\_2$
$\quad S\_1\to aS\_1bS\_1 \mid S\_1T\_1 \mid \epsilon$
$\quad T\_1\to T\_1ab \mid \epsilon$
$\quad S\_2\to bS\_2aS\_2 \mid T\_2 $
$\quad T\_2\to T\_2a \mid \epsilon$
where all nonterminals for $L\_1$ are added subscript ${}\_1$ and all nonterminals for $L\_2$ are added subscript ${}\_2$ and, finally, a new rule $S\to S\_1\mid S\_2$ is added.

Can you see how to decompose the language given in the title into smaller pieces so as to apply this strategy?
> 1 votes

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


# Question
Title: Modelling of minimal NOR-circuit problem with CP
I'm currently working on a Constraint Programming problem which I find difficult to model.

Here 's the definition of the problem :

" Given a specification of a Boolean function f(x1, ..., xn) in the form of a truth table, to find a NOR-circuit (meaning only NOR gates) satisfying the specification that minimizes depth (and, in case of a tie in depth, with minimum size). In order to simplify the problem, several assumptions are made:

• Only NOR gates with 2 inputs and 1 output can be used: more general NOR gates with more inputs are not allowed (i.e., the fan-in of NOR gates is always 2).

• The output of a NOR gate can only be the input of a single gate: outputs cannot be reused as inputs of more than one gate (i.e., the fan-out of NOR gates is always 1).

• In addition to the input signals of the Boolean function to be implemented, constant 0 signals can also be used as inputs of NOR gates. Constant 0 signals as well as input signals can be used as many times as needed as inputs of NOR gates. On the other hand, the circuit does not need to use all input signals. Similarly, the constant 0 signal does not have to be used if it is not needed."

Source : https://www.cs.upc.edu/~erodri/webpage/cps/projects/Q2-16-17/proj.pdf

Since this is the first time that I'm confronted to this kind of problem, I'm having difficulties finding "good" decision variables. Maybe I'm missing something trivial ...

Do you have any idea/hint on how to model this problem ?

# Answer
> 0 votes
This is a logic synthesis problem. Specifically, without the "fan-out of 1" limitation, this looks like the circuit minimization problem. Circuit minimization is $\Sigma\_2^P$-complete, so you should not expect any efficient algorithm for it. There are many algorithms in the literature that you can explore, including Karnaugh Maps, Quine-McCluskey, Espresso, and others. I wouldn't consider constraint programming the obvious first way to approach this problem.

If you have a requirement to use constraint programming for some homework exercise, well, you should do your own exercise, but here is a hint: you should be able to tell whether there exists a circuit of depth $d$ and width $w$ by building a $d \times w$ grid of NOR gates, then using decision variables to represent which edges are used to connect these gates. How could you use that to solve the original problem?

Limiting fan-out to 1 seems unrealistic, as gnasher729 explains.

---
Tags: optimization, integer-programming, constraint-programming
---


# Question
Title: Sanity check about a linear programming problem
given the linear program:

minimize $x+y$

subject to,

$ax+by \leq 1$

$x,y \geq 0$

I need to find real numbers $a,b \in \mathbb{R}$ such that the program (a) is infeasible, (b) is unbounded, and (c) has a unique optimal solution.

Since we are asked to minimize the sum of two non-negative numbers the solution for all $a,b \in \mathbb{R}$ is $(x,y)=(0,0)$, right?

I cannot see any potential values of $a,b$ which would make the program infeasible or unbounded, because we are always looking to minimize the sum of non-negative numbers.

# Answer
> 1 votes
I’d say the program is always feasible because x = y = 0 is a solution.

Most pairs a, b give a unique solution. Only certain pairs don’t.

Now it depends on the definition of “unbounded”. If we talk about the goal function, the minimum is always bounded by 0. If we talk about the points (x, y), they are unbounded if a \<= 0 or b \<= 0.

---
Tags: linear-programming
---


# Question
Title: If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)?
Just as I asked in the title: if my algorithm has complexity $O(n!\times n)$, can I just write $O(n!)$, or I have to keep it like $O(n!\times n)$?

# Answer
The function $n! \cdot n$ grows faster than $n!$, so it is not the case that $n! \cdot n$ is $O(n!)$. Therefore if all you know about an algorithm is that it runs in time $O(n! \cdot n)$, you cannot conclude that it runs in time $O(n!)$.

What you can do is "O tilde" notation, and write $\tilde{O}(n!)$. The meaning of "O tilde" is not completely standard, so you will have to explain that for you, $\tilde{O}$ suppresses factors which are polynomial in $n$.
> 1 votes

# Answer
No. You can't. As $\lim\_{n\to\infty} \frac{n!}{n! \times n} = 0 $. Hence, $n! \times n = \omega(n!)$ or $n! = o(n\times n!)$ (little-oh).
> 2 votes

# Answer
If you care about the actual sizes, you need to keep the $n$. You could switch to $O((n+1)!)$ if that is easier for you.

But maybe you only actually care about how fast the logarithm grows, and $\log(n!) = O(\log (n \cdot n!))$.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Finding the Range of Solutions for KSum Variation
# Preface

I asked a question before where I was looking to understand the complexity class of the following problem:

> Given a range of integers $\\{a,a+1,...,b-1,b\\}$, find a subset of size $k$ such that the sum is equal to $s$.

I had found a $O(k)$ algorithm as hinted at by the accepted answer. After playing around with the results of this algorithm, I found that it was not 100% what I was looking for.

# Problem

Given a range of integers $\\{a,a+1,...,b-1,b\\}$, find the range of the $i^{th}$ element of all subsets of size $k$, sorted in increasing order, that sum to $s$:

For example, given $k = 3$, $a = 1$, $b = 8$, and $s = 11$ we get the following list of all possible solutions sorted in increasing order:

```
{ 1 | 2 | 8 }
{ 1 | 3 | 7 }
{ 1 | 4 | 6 }
{ 2 | 3 | 6 }
{ 2 | 4 | 5 }

```

By grouping each column, we can see the ranges of values for each of the $i^{th}$ elements in the set:

1. $\\{1,2\\}$
2. $\\{2,3,4\\}$
3. $\\{5,6,7,8\\}$

# Question

I would like an algorithm that in constant time could generate the range of values for a $i^{th}$ element for all subsets summing to $s$ for a given $a$ and $b$.

```
 get_ith_range(int k, int a, int b, int s, int i)
    int lower_bound, upper_bound
    // Some cool O(1) algorithm...
    return (lower_bound, upper_bound)

```

I do not mind if it is not $O(1)$, but I feel as though there should be a way to get there at least in $O(k)$.

### Attempts

Currently, I have a way to generate the smallest for the $1^{st}$ range and the largest for the $k^{th}$ range (not in constant time though). But, I have not been able to even get to where I could generate the full $i^{th}$ range in any case.

Using my solution from my previous question, I can in $O(k)$ time produce the smallest possible value and the largest:

```
while k:
    k -= 1
    temp = int((k)*(2*a+k-1)/2)
    if s > b+temp:
        yield b
        b -= 1
        s -= b
    else:
        yield s-temp
        while k:
            k -= 1
            yield a+k

```

The last value generated by the above algorithm will be the smallest possible value. Also, the first value generated is the largest possible value.

Although, the largest can be done trivially (which is how I came up with the above *greedy* algorithm):

```
# (number of values)*(smallest + largest)/2 => sum {smallest,...,largest}
temp = int((k-1)*(2*a + k - 2)/2)
if s < b+temp:
    max = b-temp
else:
    max = b

```

# Answer
Suppose that the value at location $i$ is $j$. According to the continuity of $k$-sums (mentioned in an answer to the linked question), the range of possible sums of values at locations $1,\ldots,i-1$ is $$(i-1)a + \binom{i-1}{2},\ldots,(i-1)(j-1) - \binom{i-1}{2}.$$ Similarly, the range of possible sums of values at locations $i+1,\ldots,k$ is $$ (k-i)(j+1) + \binom{k-i}{2}, \ldots, (k-i)b - \binom{k-i}{2}. $$ Therefore the range of possible sums of all $k$ values is precisely $$ (i-1)a + \binom{i-1}{2} + j + (k-i)(j+1) + \binom{k-i}{2}, \ldots, \\ (i-1)(j-1) - \binom{i-1}{2} + j + (k-i)b - \binom{k-i}{2}. $$ We want to find for which values of $j$, the value $s$ is in this range. We get the following inequalities: $$ (i-1)a + \binom{i-1}{2} + \binom{k-i+1}{2} + (k-i+1)j \leq s, \\ (k-i)b - \binom{i}{2} - \binom{k-i}{2} + ij \geq s. $$ Therefore the range of $j$ is $$ \max\left(\left\lceil \frac{s-(k-i)b + \binom{i}{2} + \binom{k-i}{2}}{i} \right \rceil,a+i-1\right) \leq j \leq \\ \min\left(\left\lfloor \frac{s - (i-1)a - \binom{i-1}{2} - \binom{k-i+1}{2}}{k-i+1} \right \rfloor,b-k+i\right). $$
> 2 votes

---
Tags: algorithms, subset-sum, constant-time
---


# Question
Title: How to prove SPACE-TMSAT is PSPACE-hard?
I understand that the language:

$\operatorname{SPACE-TMSAT} = \\{⟨M, w, 1^n⟩ : \text{DTM $M$ accepts $w$ in space $n$}\\}$

is in PSPACE since it doesn't use more than $n$ space. But to prove that it is PSPACE-complete, we need to do the reduction from any other PSPACE language to it. If we assume the language to run on a DTM using $O(n^k)$ space, how could we reduce it to SPACE-TMSAT?

# Answer
Suppose $L$ is accepted by some machine $M$ using up to $p(n)$ space, for some polynomial $p(n)$. We map $w$ to $\langle M, w, 1^{p(|w|)} \rangle$.
> 3 votes

---
Tags: complexity-theory, reductions, space-complexity
---


# Question
Title: Can a greedy algorithm have more than one subproblems to solve after making greedy choice?
For example: `s = <s1 s2 s3>` is my problem,

I make greedy choice `s2` and solve `s1` and `s3` in a greedy way.

In CLRS, it was mentioned regarding "designing greedy algorithms"

> Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve

So why is it that we are left with only one subproblem in greedy method after making greedy choice?

# Answer
I think what you are talking about is Divide and Conquer (and Combine) techniques:

> **Divide** the problem into a number of subproblems that are smaller instances of the same problem.
>
> **Conquer** the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
>
> **Combine** the solutions to the subproblems into the solution for the original problem.
>
> *CLRS 3rd Ed Ch 4, pp. 65*

If not D&C, then at least a variant. It seems you are making an *greedy* choice, then this divides the problem into multiple, and you solve these subproblems the same way. Consider the following problem which I think can be solved as you mentioned:

> Given a directed binary tree $T$ (meaning edges are directed from parent to child) with positive integer values on the nodes, determine the directed path with maximal sum of node values.

Here is how we can solve this:

1. We make a "greedy" choice to include the root node. Since the values are positive, we know that the root node can only increase the sum of node values.
2. We now can either go left or right (not both since it is directed towards leaves).
3. Solve the left case, what is it's maximal path? Let's say it's of weight $L$.
4. Solve the right case, what is it's maximal path? Let's say it's of of weight $R$.
5. Now we combine these results, if $L \> R$ then we prepend the root node to the path returned from the left case, else we prepend the root node to the path returned from the right case.
6. If we get down to a leaf node, simply return it because it will be it's own maximal path since values are positive.

So this is a kind of "greedy" algorithm in the sense that we make a greedy choice (include the root node always). However, it is much more of a divide and conquer algorithm based on the definition of D&C. This is why greedy must only be left with one subproblem. If we have multiple subproblems then we are either in the case of Divide and Conquer or Dynamic Programming most likely.
> 0 votes

---
Tags: algorithms, greedy-algorithms, algorithm-design
---


# Question
Title: Complete the following table by specifying the scope of each declaration
I'm having a hard time understanding this question. Can each declaration have more than one scope or can a declaration have more than one scope?

If it's the later it would be:

```
Declaration              Scope
int a = 1;               B1
int b = 1;               B1
int b = 2;               B2
int a = 3;               B3
int b = 4;               B4

```

Or can it have more than one scope:

```
Declaration              Scope
int a = 1;               B1, B2, B4
int b = 1;               B1
int b = 2;               B2, B3
int a = 3;               B3
int b = 4;               B4

```

I'm sorry if this is a simple question. I just want to make sure what I'm doing is correct.

Thanks.

# Answer
Your first answer is good (assuming the scope to assign is in order as declarations go).
Each declaration is in the scope, where it is declared. In inner scope (say B2) variable $b$ is declared shadowing previous declaration. Now you cannot use outer scope variable (read, write) as is by name without scope resolution operator.

Your second table suggests that variables are available in given scopes (say B1, B2, B4), and you have taken into account shadowing, so it still looks good, but technically it is accessible and not shadowed in that scope, not declared in that scope.
> 3 votes

---
Tags: c, c++
---


title: Consensus/ranked ordering algorithm

text:
# Question
Title: Consensus/ranked ordering algorithm
Say I have a set of numbers, for example `{1, 2, 3, 4, 5}`. Is there an algorithm that allows these numbers to be put into a consensus ordering based on a ranked vote? For example, if 3 people vote and their votes are `[1, 2, 3, 4, 5]`, `[2, 1, 3, 4, 5]`, and `[1, 2, 3, 5, 4]`, then the consensus ordering would be `[1, 2, 3, 4, 5]`. Ideally the algorithm would support votes of partial orderings as well, such as `[2, 5, 4]`.

I'm pretty sure I can extend the ranked voting system to produce a complete ordering of the "candidates," but I'm wondering if there's already an algorithm to do this.

# Answer
I have both good news, and bad news. Not only is there a way to do it; there are many candidate ways to do it. For instance, you could use IRV, Condorcet voting, Borda count, or many other schemes. See https://en.wikipedia.org/wiki/Ranked\_voting and https://en.wikipedia.org/wiki/Social\_choice\_theory.

Unfortunately, there are also negative results showing that no scheme provides all of the properties that we might desire. See Arrow's theorem: https://en.wikipedia.org/wiki/Arrow%27s\_impossibility\_theorem and https://en.wikipedia.org/wiki/Condorcet\_paradox.
> 2 votes

---
Tags: algorithms, sorting, consensus
---


# Question
Title: Find the longest possible path in full binary tree
Given the depth of the tree, I need to calculate the longest possible path in the full binary tree (also known as the diameter).

When attempting this problem, I experimented with what the depth has to do with the path length. However, the solutions I came up with depended on going through the root, while the longest path could obviously exist outside of the root.

What's an equation I can use to find the diameter of the full binary tree using the depth?

# Answer
If it is a *full binary tree*, that is defined as:

> Full binary tree is a tree in which every node other than the leaves has two children.

Then you know the depth $D$ will be half of the total possible diameter. This is because we can take a maximum possible path of length $D$ from root to any leaf in the subtree rooted at the left-child of the root, and we can also take a maximum possible path of length $D$ from root to any leaf in the subtree rooted at the right-child of the root. Thus, adding these up would be a path of length $2D$.

Thus, we get that the maximum possible diameter would be equal to twice the depth (i.e. $\mathrm{diameter} = 2\cdot \mathrm{depth}$).
> 5 votes

---
Tags: binary-trees
---


# Question
Title: Response time of scheduling a DAG where each vertex is a task
Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v\_i$ has to execute before task $v\_j$ if there exists an edge $(v\_i,v\_j)$ between those two tasks. I have $x$ threads that can execute those tasks.

Is there a (simple) formula to determine the response time (or at least an upper bound) for the given setup using any work-conserving scheduler?

# Answer
Found it! This problem is NP-complete when the goal is to minimize total execution time.

> The scheduling problem (P1) is the following. We are given
>
> (1) a set $S = \\{J\_1 , \ldots , J\_n\\}$ of jobs,
>
> (2) a partial order $\prec$ on $S$,
>
> (3) a weighting function $W$ from $S$ to the positive integers, giving the number of time units required by each job, and
>
> (4) a number of processors, $k$.

Please see the following paper, which immediately discusses it from the introduction onward:

J.D. Ullman. Np-complete scheduling problems. *Journal of Computer andSystem Sciences*, 10(3):384 – 393, 1975.

There are a few other cases that may be of interest that are discussed in the paper:

* When $\prec$ is empty (no edges in the DAG)
* (P2) When $W(J\_i) = 1$ for all $i$.
* (P3) When $k = 2$ and $W(J\_i) \in \\{1, 2\\}$ for all $i$.

You can show 3-SAT reduces to (P2) through and intermediate problem (P4) that Ullman discusses. Then it is clear that (P2) reduces to (P1).
> 4 votes

# Answer
A simple upper bound on the response time, for any work-conserving scheduler, is $$\frac{\mathit{vol} - L}{x} + L,$$ where $\mathit{vol}$ is the sum of all the execution times and $L$ is the sum of the execution times along a critical path in the DAG.
> 2 votes

---
Tags: graphs, parallel-computing, scheduling
---


# Question
Title: Are fully connected layers required for convnets?
I have a reinforcement learning model I'm trying to create for a grid based game. One of the features of the game is that the game board can get bigger mid game, although I know this is a problem that machine learning isn't very good at. However, one idea that I had was to train a convolutional neural net model that doesn't have a fully connected layer at the end, so that the input and output size of the net can vary together, and the model will still work because it won't need any additional weights to produce an output. In addition, adding a fully connected layer or two at the end would be a very large amount of extra weights to train, since the action space of the problem is very large (15232 discrete actions if I remove the expanding grid portion of the game). If my calculations are correct, a single fully connected layer would become 464 million more weights. Which seems like a lot compared to my existing 223,350 trainable parameters.

Here is one iteration of this network type I've tested:  For this model, the observation space is 92 layers deep, and 28 wide by 16 tall. And the action space is 34 layers deep, and 28 wide by 16 tall. I'm not getting amazing results from this network (although better than random choice), which could be due to a multitude of reasons. However, I don't know if this is bad idea as I'm having trouble reasoning about this design generally.

Is a fully connected layer at the end necessary for the network to learn global ideas about the observation space?

# Answer
There are no rules. You can do whatever you like. The ultimate test is how well it works; you'll have to try it and see.

But the short answer is: no, fully connected layers are not required. You can build a network that is purely convolutional, with no fully connected layers. It's hard to know how well it will work, without trying it.
> 1 votes

# Answer
What you are thinking of is a Fully Convolutional Network (FCN). It's already discussed for a couple of years, and you might want to check out this famous piece of paper.

So the architecture you are designing conceptually has no problem. With less parameters, you may achieve faster learning and better performance (or not, maybe). Is a FCN better than a traditional ConvNet with fully connected layers? I don't know, I think there's no solid answer to that.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Linear Path Optimization with Two Dependent Variables
Alright, so this is a fairly interesting problem I have but also slightly difficult to explain so I will try my best.

There are two runners on a line that goes from $x=0$ to $x=100$. The two runners start at $x=50$. The runners are then given an array of coordinate pairs that they must visit. The catch is, the coordinate pair contains the $x$ value for locations runner 1 and runner 2 must be at the same time. So for example, if they are given a coordinate pair $(40, 70)$, to successfully "complete" that coordinate, runner 1 must go to $x=40$, and runner 2 must go to $x=70$. They can't move on to the next coordinate pair until both have reached their destination.

So given a large array of coordinate pairs, the runners have to visit each coordinate pair in any order they chose. The runners can move at the same time and have the same speed. The trick is how to optimize the order in which they visit the coordinates. For example, if runner 1 is at $x=10$, and runner 2 is at $x=90$, it would be inefficient to chose a coordinate pair like $(80,80)$, because runner 2 would only travel $10$ units, and spend a long time waiting while runner 1 is moving $70$ units. This is sort of like the travelling salesman problem, except there are two people involved dependent on each other, and they can visit any point from any other given point in any order.

Does anyone have any ideas how to create an algorithm that would return the best (or at least good) optimized order in which they would visit these coordinate pairs?

# Answer
> 4 votes
You can consider the 1D-position of the 2 runners as one 2D-position. X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100).

Then all the goal points coordiantes can have a 2D-position in the same way, for instance (40, 70). Now the Travelling salesman problem has to be solved using the Tchebychev distance (infinite norm). I am pretty sure this is NP-complete.

A simple heuristic approach may be to always run to the next closest point (greedy nearest neighboor). Or you can either look for a more sophisticated one...

# Answer
> 3 votes
As Vince observes, your problem is TSPP (traveling salesman path problem) on the plane with respect to the $L\_\infty$ metric. On the plane, the $L\_\infty$ and $L\_1$ metrics are equivalent (the unit balls differ by a rotation of $45^\circ$), so your problem is equivalent to TSPP on the plane with respect to the $L\_1$ metric. This problem has been addressed on this question.

---
Tags: algorithms, optimization, traveling-salesman
---


# Question
Title: NP completeness proof of a spanning tree problem
I am looking for some hints in a question asked by my instructor.

So I just figured out this decision problem is $\sf{NP\text{-}complete}$:

In a graph $G$, is there a spanning tree in $G$ that contain an exact set of $S=\\{x\_1, x\_2,\ldots, x\_n\\}$ as leafs. I figured out we can prove that it is $\sf{NP\text{-}complete}$ by reducing Hamiltonian path to this decisions problem.

But my instructor also asked us in class:

> would it also be $\sf{NP\text{-}complete}$ if instead of "exact set of $S$", we do
>
> "include the whole set of $S$ and possibly other leafs" or "subset of $S$"

I think "subset of S" would be $\sf{NP\text{-}complete}$, but I just can't prove it, I don't know what problem I can reduce it to this. As for "include the set of $S$..." I think it can be solved in polynomial time.

# Answer
> 15 votes
In short, your guesses are correct. For the purpose of this answer, let’s call the three problems in question as follows:

* Equality version: Given a graph $G = (V, E)$ and a set $S \subseteq V$, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is equal to $S$. As you stated, this is NP-complete by a reduction from the Hamiltonian path problem.
* Subset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a subset of $S$.
* Superset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a superset of $S$.

To prove that the subset version is NP-complete, you can still reduce the Hamitonian path problem to it. Try to modify the proof of the NP-completeness of the equality version.

To prove that the superset version can be solved in polynomial time, try to find a necessary and sufficient condition for such a tree $T$ to exist.

Both versions (as well as some other problems about spanning trees) are studied in \[SK05\]. But I guess that it is better if you try to solve the problems by yourself before looking at the proofs in the paper, because looking at the paper can be a big spoiler. Unfortunately I had looked at the paper before trying to find a polynomial-time algorithm for the superset version!

---

\[SK05\] Mohammad Sohel Rahman and Mohammad Kaykobad. Complexities of some interesting problems on spanning trees. *Information Processing Letters*, 94(2):93–97, April 2005. \[doi\] \[author copy\]

# Answer
> 0 votes
These hints weren't enough to get me to a solution for the superset of S problem - though the hints are helpful and correct. This is my train of thought that got me to a solution.

What happens if you remove all the vertices in S from G, (V-S), and then find a spanning tree T with DFS? If there are any yet unconnected vertices in G, say v1; what does that say about the role of at least one of the vertices in S that was removed? That it lies in the path to v1 from some vertex that is presently in the spanning tree. Thus, it can't be a leaf (since leaves have no children). If there are no unconnected nodes, that means every vertex in S can be a leaf provided it has an edge leading to the spanning tree. Vertices in S that only connect to other vertices in S of course won't have a connection to the spanning tree and would violate the condition. So, there are two cases to check for:

1. If all nodes not in S are connected after removing S from G and finding a spanning tree
2. If each node in S can be connected directly to the spanning tree.

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


# Question
Title: Finding a negative cycle in a bipartite graph
The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where the edges in one direction (from X to Y) are all positive and the edges in the other direction (from Y to X) are all negative?

---

One idea that I considered is to solve two instances of the minimum-weight assignment problem: one with only the edges from X to Y, and one with only the edges from Y to X. Combining the two assignments gives a directed cycle in the original graph. However there are two problems with this idea:

* The computational problem of finding a minimum-weight assignment is not necessarily smaller than Bellman-Ford, for example the Hungarian algorithm requires time $O(|V|^3)$.
* The directed cycle found in this way is not necessarily minimum-weight in the original graph; it is possible that the original graph has a negative cycle while this algorithm will yield only a positive cycle. For example, consider a graph with four vertices in each side, with the following weights: \begin{align\*} w(x\_1\to y\_1) = w(x\_2\to y\_2) &= 1 \\ w(y\_2\to x\_1) = w(y\_1\to x\_2) &= -2 \\ w(x\_3\to y\_3) = w(x\_4\to y\_4) &= 5 \\ w(y\_4\to x\_3) = w(y\_3\to x\_4) &= -3 \end{align\*} and all other weights are $+\infty$.

There is a negative cycle $x\_1\to y\_1\to x\_2\to y\_2$ (total weight -2). However, the minimum-weight assignment from X to Y has weight 12 and the minimum-weight assignment from Y to X has weight -10 so the total is positive.

# Answer
> 4 votes
Given a directed graph, turn each edge $(u,v)$ into two edges $(u, x)$ and $(x,v)$ with the same weight where $x$ is a newly added vertex. Now the graph becomes a bipartite graph, and there is a negative cycle in the original graph if and only if there is a negative cycle in the new bipartite graph.

Suppose the two parts of the bipartite graph are $X$ and $Y$. We increase the weights of all edges from $X$ to $Y$ by $r$ and decrease the weights of all edges from $Y$ to $X$ by $r$, where $r$ is a large enough positive integer. Now we get a new bipartite graph where all edges from $X$ to $Y$ have positive weights and all edges from $Y$ to $X$ have negative weights. In addition, there is a negative cycle in the original bipartite graph if and only if there is a negative cycle in the new bipartite graph.

So if there is an $O(f(|V|,|E|))$ algorithm to solve your problem, we can solve the problem on general directed graphs in $O(|E|+f(|V|,|E|))=O(f(|V|,|E|))$ (since $f(|V|,|E|)\in \Omega(|E|)$) time by applying the algorithm on the bipartite graph obtained from the conversion above. This means your problem is asymptotically no easier than the problem on general directed graphs.

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


# Question
Title: Reduction of Hamiltonian cycle to Hamiltonian cycle & clique
I've been given a homework problem to prove that determining whether a graph G has both a Hamilton cycle and a clique of size k is NP-complete.

Based on this question, I know an "easy" reduction exists from Hamiltonian path to Hamiltonian path & clique (or someone has said it exists), and I assume that the same is true for reducing Hamiltonian cycle to Hamiltonian cycle & clique.

My thought is to somehow insert a clique of size k into G such that it's in the original cycle. (If I can make it lie in the path of the original cycle, it shouldn't disrupt the cycle, as all cliques have a Hamiltonian path through them.) But there are two problems with this approach:

1. I'm not sure how to insert a clique in such a way it can't create or destroy a cycle. I've tried:

* Inserting the clique on an arbitrary edge of the graph (can result in a G' without a Hamiltonian cycle)
    * Adding k-2 vertices and creating a clique between them and two adjacent vertices in G (can result in G' without a Hamiltonian cycle)
    * Inserting the clique between input & output nodes connected to two different vertices on the original graph (can result in G' with a Hamiltonian cycle where G did not have one, if the points are arbitrary, or G' without a Hamiltonian cycle if inserted across adjacent vertices)
2. More generally--if I can find a way to insert a clique while preserving G's original Hamiltonian cycle--does this actually satisfy the iff requirement of the reduction? I don't feel like it does, because the existence of the clique in G' is in no way contingent on the existence of the Hamiltonian cycle in G.

Could someone give me a push in the right direction on this? I'm totally stumped on another way to approach it.

# Answer
> 2 votes
For NP completeness, two things must be demonstrated.

1. That a solution to the problem can be verified in polynomial time (usually easy).
2. That the input to another NP Complete problem can be formatted as an input to the potentially NP complete problem (also that a solution from the potential NP Complete problem can be turned into a solution to the NP complete problem) all in polynomial time.

It looks like you are trying to go the wrong direction with your question. You are asking about inserting a Clique into a graph, but you only need to concern yourself with a graph that would be sent to a HP solver and modify the inputs so they are appropriate for a HP+Clique solver. The HP part of the candidate problem doesn't require any modification - it just takes an undirected graph G(V,E). A clique takes an undirected graph G(V,E) and a goal, k. So you need to define a k that is in $G\_{HP}$. what if you set k=1?. This way, the only graphs that your solver will fail to find a solution for are those that don't have a HP since every node is a clique with itself. This takes O(1) to define k=1.

Now, you just need to modify the output of the HP+Clique so it is the same as the output for the HP problem. e.g. If the candidate problem produces a solution, you would only return the path part and drop the clique part. If a solution is not found, you return NO.

---
Tags: complexity-theory
---


title: Alternate reduction from 3SAT to 4SAT?

text:
# Question
Title: Alternate reduction from 3SAT to 4SAT?
It seems that the standard reduction method you see online from 3SAT to 4SAT is that we let $\phi = (a \lor b \lor c)$ be a 3SAT clause, and so there is an assignment that satisfies $\phi$ iff $\phi' = (a \lor b \lor c \lor z) \land (a \lor b \lor c \lor \neg z)$ is also satisfiable.

Is it just as valid to say that $(a \lor b \lor c)$ is satisfiable iff $(a \lor b \lor c \lor c)$ is satisfiable? This seems like a much simple solution..

# Answer
It depends on the exact definition of $k$-SAT that's being used. If $k$-SAT is defined to have clauses of length *at most* $k$, your reduction is perfect; if it's defined to have clauses with *exactly* four *distinct* literals, then you're out of luck.
> 1 votes

# Answer
The SAT order of operations would reduce the variables in a clause to unique literals before evaluating the formula. However, I couldn't find a reference to support this claim.
> 0 votes

---
Tags: reductions, satisfiability
---


title: Why is Max SAT in P if SAT in P?

text:
# Question
Title: Why is Max SAT in P if SAT in P?
It holds that if SAT could be solved in poly time, one can also find in poly time the assignment that satisfies most clauses of the original formula. Does anyone have any idea how to show this? Let's assume we have algorithm A to decide in poly time if a given formula could be satisfied or not. How one can use this to find in poly time the assignment that satisfies most clauses. I know that using this assumption leads to also being able to find satisfying assignment in poly time (if the formula is in SAT), but if the formula is not in SAT how can we find what is the sub-formula with maximum clauses that belongs to SAT without iterating over the powerset of the clauses which will lead to exp time algorithm?

# Answer
> 3 votes
Suppose that you have a CNF formula $x$ with input size $n$, and that you can solve $\text{SAT}$ in $O(n^c)$ time for some constant $c$.

We construct a new formula $y$. For each clause $l\_i$ in $x$, with terms $v\_{i,k}$, add a new variable $t\_i$ and the CNF clauses $\bigwedge\_i(\neg t\_i \vee l\_i)$ and $ \bigwedge\_{i,k} (t\_i \vee \neg v\_{i,k})$.

Now this formula is only satisfiable if $t\_i$ is assigned a truth value equal to $l\_i$, and our input size is bounded by linear function of the original size. We then add a "at least $k$ out of $n$" constraint to this formula on the $t$ variables. This also adds a polynomial number of clauses. Now the formula is only satisfiable if at least $k$ clauses of the original formula are satisfiable.

Now we can simply solve $\log\_2(n)$ instances of the above formula, doing a binary search with $k$ to find the maximal number of clauses that are satisfiable simultaneously.

# Answer
> 0 votes
This is the reduction from SAT to MaxSAT given we have a polynomial time algorithm for MaxSAT. Take some instance of a SAT problem $f$. Since SAT requires all clauses in $f$ be satisfied or return that none exists, we can set $k=m$ and run Max\_SAT($f=(CNF),k=m$). If exactly $k$ clauses in $f$ are satisfied, it returns the solution. If less than $k$ clauses are satisfied, MaxSAT returns No which would also match the output of a SAT solver.

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Computability - Can a Turing Machine calculate the input's length?
I have looked for an answer for this question which seems trivial, but I didn't find any.

> Can a Turing machine, given a word $w$, calculate the length of the word?

# Answer
> 1 votes
Yes, of course it can. As a simple intuition, replace "Turing machine" with "computer program" and the answer shouldn't change, assuming that the Church–Turing thesis is true.

Just use a portion of the tape after the input as a binary counter and shuttle back and forth increasing that counter by one for every character in the input, marking the characters that you've already counted.

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


title: Concatenated pseudorandom generators

text:
# Question
Title: Concatenated pseudorandom generators
I have two pseudorandom generators $G\_1$ and $G\_2$ from $k$ bit to $2k$ bit. I have another PRG $G\_3$ from $k$ to $2k$ bits. Now I buildup a new function from $k$ to $4k$ as follows:

Let $x$ be $k$ bit then apply $G\_3$ on it on $x$. Then let output by $y$. Apply $G\_1$ on first $k$ bits and $G\_2$ on last $k$ and join the resulting output. Then resulting function is a PRG. How do you prove this?

# Answer
> 3 votes
The idea is to use a hybrid argument. Let us first write a formula for the new PRG: $$ G(x) = G\_1(G\_{3,1}(x)) G\_2(G\_{3,2}(x)), $$ where $G\_3(x) = G\_{3,1}(x) G\_{3,2}(x)$.

Suppose that we could distinguish between $G(U\_k)$ and $U\_{4k}$, where $U\_n$ denotes $n$ random bits. Consider the following sequence: $$ G(U\_k); G\_1(U\_k) G\_2(U\_k); U\_{2k} G\_2(U\_k); U\_{4k}. $$ By assumption, we can distinguish between the first distribution and the last distribution. Hence we can distinguish an adjacent pair of distributions.

* If we can distinguish $G(U\_k)$ and $G\_1(U\_k) G\_2(U\_k)$, then this gives a distinguisher for $G\_3$.
* If we can distinguish $G\_1(U\_k) G\_2(U\_k)$ and $U\_{2k} G\_2(U\_k)$, then this gives a distinguisher for $G\_1$.
* If we can distinguish $U\_{2k} G\_2(U\_k)$ and $U\_{4k}$, then this gives a distinguisher for $G\_2$.

By assumption, $G\_1,G\_2,G\_3$ are all secure, so we obtain a contradiction.

# Answer
> 2 votes
This is the Goldreich-Goldwasser-Micali construction, and its security is proved in good textbooks on the foundations of cryptography (e.g., Oded Goldreich's book).

---
Tags: pseudo-random-generators
---


title: Reversible Merge of Integer Hash Values

text:
# Question
Title: Reversible Merge of Integer Hash Values
Context:

I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's children. Additionally, I'd like to be able to replace one of the node's children in constant time (i.e., not doing a full recombination of hash values) as the branching factor for the tree could be quite large.

Question:

I am looking for a set of functions ($combine$, $separate$) that operate on fixed width integers and have the following properties.

Let $X$ be some set of integers with fixed width $b$.

(1) $combine(X)$ outputs an integer with width $b$

(2) $combine(X)$ operates in $O(|X|)$ time complexity

(3) $$combine\Bigl(\left\\{t, separate\bigl(combine(X), x\bigr)\right\\}\Bigr) = combine\Bigl(\bigl(X \setminus \\{x\\}\bigr) \cup \\{t\\}\Bigr)$$ where $x \in X$ and $t$ is some integer of width $b$.

(4) $separate(X, x)$ operates in $O(1)$ time complexity

(5) The outputs of $combine$ are going to be used as hash values so an algorithm with a "good" distribution of output values to avoid collisions is ideal. That said, I'd define good as anything better than trivial addition and subtraction (see below).

Initial thoughts:

A trivial implementation would have $combine$ and $separate$ be addition and subtraction (with some modulo logic); however, this obviously won't have a good distribution for tightly bunched input values.

# Answer
> 2 votes
A simple approach is to use the sum of hashes, e.g.,

$$\begin{align\*} \text{combine}(X) &= \sum\_{x \in X} H(x)\\ \text{separate}(y,x) &= s - H(x) \end{align\*}$$

where $H(\cdot)$ is some good hash function. To make the result suitable as a hash, I recommend that you hash the output of combine one more time before using it as a hash value.

More generally, you can use any commutative hash function. See, e.g., https://crypto.stackexchange.com/q/6497/351 and https://crypto.stackexchange.com/q/11420/351 and https://crypto.stackexchange.com/q/54544/351 and Which fingerprinting/hashing algorithms support compounding?.

Another approach is to use a Merkle hash tree. Store the list of children in a Merkle hash tree, one mini Merkle hash tree per node of your tree (i.e., a binary tree whose leaves are the children of the node, and where each internal node is augmented with the hash of the values in its two children, and the value in the root of hte Merkle tree is the hash of that node of your tree). This allows $O(\lg n)$ updates rather than $O(1)$ updates, but that might be good enough.

---
Tags: algorithms, trees, hash, integers
---


title: Which algorithm is this?

text:
# Question
Title: Which algorithm is this?
I'm looking for someone who can tell me which algorithm this is and help me to clearify what the variable mean.

* $g\_j$ : the shortest path length from $1$ to $j$
* $t\_{i,j}$: the length from $i$ to $j$
* $\mathrm{SCS}$: successive set
* $S$: Start node, $G$: Goal node

\begin{align} &f\_G = 0 \\ &f\_i = \infty, \forall i ≠ G \\ &t\_{i,j} = \infty, \forall (i, j) \notin T \\ &t\_{i,j} \> 0 , \forall (i, j) \in T\\ &T = \\{1, 2, . . . , N − 1, N\\}, \quad Ť = \\{\emptyset\\} \\ &\text{Do while $T$ is not empty} \\ &\qquad j^\* = \arg\min\_{j\in T} f\_j \\ &\qquad \text{for }i \in \mathrm{SCS}(j^\*)\\ &\qquad\qquad f\_i = \min \\{f\_i , t\_{i,j}^\* + f\_j^\*\\}\\ &\qquad \text{Remove $ j^\*$ from T, add $j^\* $ to Ť} \\ &\text{Stop while }j^\*= S \end{align}

# Answer
It looks like a Dijkstra algorithm to me.

I see the algorithm begins at the "do while" line and everything before are the input for the algorithm. With your clue that G is the goal node, and $t\_{i,j}$ are *lengths*, it is easy to see $f\_i$ is the distance from $i$ to G as we know so far within the loop.

So the algorithm means the following:

* Every iteration, we find the node $j^\*$ within T that has min distance to G
* Then we scan each of its neighbor $i$, update their distance to G
    + update rule: they reach G with traversing $j^\*$ or without (i.e., the old $f\_i$), so min of these two will be the new known min distance to G
* After this scan, all nodes that can possibly reach G via $j^\*$ are updated. And we remove $j^\*$ from T, meaning that in the future, any other node (not neighbor to $j^\*$) to reach G via $j^\*$ should only be via one of its neighbor $i$

Here the $t\_{i,j}$ are positive, so that adding to $f\_{j^\*}$ can only increase the distance. And hence all $f\_i$ will only be decreasing in each iteration. In this case, this algorithm is a dynamic programming by iteratively reducing the problem to a smaller set of nodes until a solution is found.
> 2 votes

---
Tags: algorithms, graphs, algorithm-analysis
---


# Question
Title: How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method?
The recurrence I have is

$T(n) = 2T(\sqrt{n-1} + 2) + 1$

I don't know how to solve it. I didn't find much on the internet with square roots in recurrences especially with constants inside of it. I'm supposed to find the height of the tree but I have no idea how.

I need to solve this recurrence only using trees. And I can't find anything about solving recurrences with trees and square roots as parameters.

# Answer
You could try upper and lower bounding the work done in your recurrence tree by two other simpler recurrences.

For instance, this is the function/rate by which your recurrence input decreases at each level: $$f(n) = \sqrt{n-1} + 2$$

We can find a function the decreases faster, for example

$$f\_1(n) = \sqrt{n} \leq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$

We can also find a function that decreases slower, for example

$$f\_2(n) = 2\sqrt{n} \geq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$

Thus with $f\_1(n) \leq f(n) \leq f\_2(n)$ we can construct two other recurrences based on these new functions:

$$\begin{align\*} T\_1(n) & = 2T\_1(\sqrt{n}) + 1\\ T\_2(n) & = 2T\_2(2\sqrt{n}) + 1\\ \end{align\*}$$

We can then bound our original recurrence by these:

$$T\_1(n) \leq T(n) \leq T\_2(n)$$

So if you can solve these recurrences, then you can bound $T(n)$ appropriately, because these will lower bound and upper bound the depth of the recursion tree respectively.

---

I wanted to work through this a bit further for my own satisfaction. Not quite a recursion tree analysis, but I think this function is interesting so I worked through it.

The first $T\_1$ we can solve relatively easily with a domain transform:

$$\begin{align\*} T\_1(n) & = 2T\_1(\sqrt{n}) + 1\\ T\_1(2^{2^k}) & = 2T\_1(2^{2^{k-1}}) + 1\\ S(k) & = 2S(k-1) + 1\\ & = \Theta(2^k)\\ T\_1(n) & = \Theta(2^{\log \log n})\\ & = \Theta(\log n) \end{align\*}$$

The second $T\_2$ is a little trickier, but not much. Let's unwrap this a bit:

$$\begin{align\*} T\_2(n) &= 2T\_2(2\sqrt{n}) + 1\\ &= 2\left(2T\_2(2\sqrt{2\sqrt{n}}) + 1\right) + 1\\ &= 4T\_2(2^{3/2} \cdot n^{1/4}) + 3\\ &= 4\left(2T\_2(2 \cdot (2^{3/2} \cdot n^{1/4})^{1/2}) + 1\right) + 3\\ &= 8T\_2(2^{7/4} \cdot n^{1/8}) + 7\\ &= \vdots \end{align\*}$$ The pattern starts to emerge and we can perform another domain transform (obviously, to be formal you should prove that the pattern holds by induction, but I'm omitting that).

Let $n = 4^{2^k + 1}$ and when we apply $2 \sqrt{n}$ we get:

$$\begin{align\*} 2 \sqrt{4^{2^k + 1}} & = 2 \sqrt{4} \sqrt{4^{2^k}}\\ & = 4 \cdot 4^{2^{k-1}}\\ & = 4^{2^{k-1} + 1} \end{align\*}$$

Now with this we do the domain transform: $$\begin{align\*} T\_2(n) & = 2 T\_2(2 \sqrt{n}) + 1 \\ T\_2(4^{2^k + 1}) & = 2 T\_2( 2 \sqrt{4^{2^k + 1}}) + 1\\ S(k) & = 2 S(k-1) + 1\\ & = \Theta(2^k)\\ T\_2(n) & = \Theta(2^{\log\_2(\log\_4(n) - 1)})\\ & = \Theta(\log n) \end{align\*}$$

With this we see:

$$\begin{align\*} T\_1(n) &\leq T(n) \leq T\_2(n) & \forall n \geq 4\\ c\_1 \log n &\leq T(n) \leq c\_2 \log n & \forall n \geq 4\\ \implies T(n) & = \Theta(\log n) \end{align\*}$$
> 4 votes

# Answer
This is not a full solution, but should get you going with what dkaeae commented above (link here).

First thing that is reasonable to try is setting $n = 2^{2^k} + 1$. However, after applying the $f(n) = \sqrt{n - 1} + 2$ in the recurrence, we get $2^{2^{k-1}} + 2$ which is not going to work for our function $g(k)$ as seen in the domain transform scheme.

Next thing that I did, was determine the base case. You can see 1, 2, and 3 will not work. Thus, we have 4 is the first value where the first application of $f^{-1}$ is increasing. We can get the following sequence after repeatedly applying $f^{-1}$:

$$\\{4,\ 5,\ 10,\ 65,\ 3970,\ 15745025,\ 247905749270530,\ \ldots\\}$$

What we want is a function $g(k)$ equivalent to the $k$th term in this sequence. However, plugging this sequence into OEIS or wolframalpha.com presents no results. From there I tried to see what repeated application of the function $f(n)$ actually did:

$$\begin{align\*} f(n) & = \sqrt{n - 1} + 2\\ f(f(n)) & = \sqrt{\sqrt{n - 1} + 1} + 2\\ f^{(3)}(n) & = \sqrt{\sqrt{\sqrt{n - 1} + 1} + 1} + 2\\ f^{(4)}(n) & = \sqrt{\sqrt{\sqrt{\sqrt{n - 1} + 1} + 1} + 1} + 2\\ \vdots & = \vdots \end{align\*}$$

The thing to notice here is that each term we have has 2 added on to the end of it. If we can find a function $h(k)$ that fits $f^{(k)}(n) - 2$, then we know $g(k) = h(k) + 2$. Thus, we are now searching for the sequence above, minus 2!

$$\\{2,\ 3,\ 8,\ 63,\ 3968,\ 15745023,\ 247905749270528,\ \ldots\\}$$

Now when you search this sequence, something does actually turn up. See sequence A003096 from OEIS. Fortunately, there is a closed form (albeit disgusting) for this sequence.

$$h(k) = \lceil c^{2^k}\rceil \quad \text{where } c=1.2955535361865325413981559700593353\ldots $$

Disclaimer: I have no idea how this constant is derived, but this closed form will work for you.

We now know a $g(k) = h(k) + 2 = \lceil c^{2^k}\rceil + 2$. Now try this $g(k)$ with Domain Transform and you should be good to go to apply recursion tree analysis on the transformed domain.

This method will work, but I think the easier way would probably be to upper bound and lower bound the depth of the recursion tree with an easier function.
> 1 votes

---
Tags: trees, recurrence-relation
---


# Question
Title: Is the language of words with equal number of 010s and 101s as substrings regular?
Is the language of words containing same number of 101s and 010s regular? If yes, how can I design a DFA for it?

In general, is the language of words containing equal number of strings which one is "one's complement" of the other one is regular (like the language of words containing equal number of 01s and 10s which is regular)? Is there any counterexample?

# Answer
> 5 votes
No, the language of words containing same number of 010s and 101s is not regular.

Consider $x\_n=(0100)^n$ and $y\_n=(1011)^n$. Then $x\_iy\_j$ contains $i$ number of 010s and $j$ number of $101s$. That is, $x\_iy\_j$ is in the language if and only if $i=j$.

So $x\_i$ represents a distinct Nerode-Myhill equivalence classes for all $i$. Since there are infinitely many such $x\_i$, there are infinitely many Myhill-Nerode equivalence classes. By Myhill–Nerode theorem, the language is not regular.

---

Here are several related exercises. Exercise 2 answers the more general situation in the question. Exercise 3 is a further generalization.

Let $\Sigma=\\{0,1\\}$.

**Exercise 1.** The language of words over alphabet $\Sigma$ containing the same number of 01s and 10s is regular. The language of words over alphabet $\\{0,1, 2\\}$ containing the same number of 01s and 10s is not regular.

**Exercise 2.** Let nonempty $w\in \Sigma^\*$. Let $\overline w$ be the one's complement of $w$. For example, $\overline{010010111}=101101000$. Let $E\_w$ be the language of words over $\Sigma$ containing the same number of $w$s and $\overline w$s. Show that $$ E\_w\text{ is regular} \iff w=01\text{ or }w=10$$ (It may take a while to do this exercise.)

**Exercise 3.** Let $u$ and $v$ be two different non-empty words in $\Sigma^\*$. Let $E\_{u,v}$ be the language of words over $\Sigma$ containing the same number of $u$s and $v$s. Let $N\_{u,v}$ be the language of words over $\Sigma$ containing no $u$ nor $v$ as a subword. Show that $$ L\_{u,v}\text{ is regular } \iff \\{u,v\\}=\\{01,10\\}\text{ or } E\_{u,v} = N\_{u,v}.$$ (It may take a while to do this exercise.)

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


# Question
Title: Expected number of iterations for bozo sort opt algorithm
I'm trying to figure out the upper bound for the number of iterations of the bozo sort opt algorithm, described in this paper on section 3.2: http://www.hermann-gruber.com/pdf/fun07-final.html

I know the maximum number of inversions in this case is *nC2*, what i'm struguling with is the probability of two numbers in an iteration being an inversion.

Here is the relevant piece of the paper I'm focusing on, I know the answer to the number of iterations is there, I just can't seem to get to it.

> ## 3.2 Comments on optimized variants of bogo-sort
>
> Though optimizing the running time seems somewhat out of place in the field of *pessimal* algorithm design, it can be quite revealing for beginners in both fields of optimal *and* pessimal algorithm design to see how a single optimization step can yield a dramatic speed-up. The very first obvious optimization step in all aforementioned algorithms is to swap two elements only if this makes sense. That is, before swapping a pair, we check if it is an inversion: A pair of positions $(i, j)$ in the array $a\[1, \dots, n\]$ is an inversion if $i \< j$ and $a\[i\] \> a\[j\]$. This leads to optimized variants of bogo-sort and its variations, which we refer to as bogo-sort$\_{opt}$, bozo-sort$\_{opt}$, and bozo-sort$^+\_{opt}$, resp. As there can be at most $\binom{n}{2}$ inversions, this number gives an immediate upper bound on the number of swaps for these variants—compare, e.g., to $\mathcal \Omega(n\*n!)$ swaps carried out by bogo-sort. It is not much harder to give a similar upper bound on the expected number of iterations. As the number of comparisons during a single iteration is in $\mathcal O(n)$, we also obtain an upper bound on the expected total number of comparisons:
>
> **Lemma 14.** The expected number of iterations (resp. comparisons) carried out by the algorithms bogo-sort$\_{opt}$, bozo-sort$\_{opt}$, and bozo-sort$^+\_{opt}$ on a worst-case input $\overline x$ of length $n$ is at most $\mathcal O(n^2\log n)$ (resp. $\mathcal O(n^3\log n)$).

# Answer
The bounds in that paper can be tightened. The tighter bounds in lemma 14 are "..." at most $O(n\log n)$ (resp. $O(n^2\log n))$.

---

As in the question and the papers, we will fix a set of $n$ elements that are totally ordered. The array $a=(a\_1, a\_2, \cdots, a\_n)$ will be a permutation of the $n$ elements. A pair of element $\\{a\_i, a\_j\\}$ is a good pair if $i\lt j$ and $a\[i\]\lt a\[j\]$. It is a bad pair if $i\lt j$ and $a\[i\]\gt a\[j\]$. A bad pair is also call an inversion.

**Fact on inversion**. Swapping a bad pair strictly decreases the number of all inversions. An array is sorted if and only if the number of all inversions is 0. The maximum number of all inversions is the same as the numbers of all pairs, $\binom n2$.

Now we will use the fact above to show the tightened version of lemma 14 for one case.

### The expected number of comparisons carried out by bozo-sort$\_{\text{opt}}$ on a worst-case input $x$ of length $n$ is at most $4n^2\log n + (n-1)$, where $\log$ is the natural logarithm.

Proof: Suppose there are $m$ bad pairs in the array. A run of `procedure rand. transpose` hit one with probability $p = m/n^2$, so the expected number of runs of that procedure until we hit a bad pair is $1/p=n^2/m$. Since the number of bad pairs decreases each time we swap a bad pair, the expected number of runs of that procedure until the array is sorted is bounded by $$\sum\_{m=1}^{\binom n2}\frac{n^2}m=n^2\sum\_{m=1}^{\binom n2}\frac1m\le 2n^2\log n$$

Note that each `procedure rand. transpose` makes one comparison. The effect of running `procedure sorted` before every $n-1$ `procedure rand. transpose` will at most double number of comparisons besides the initial $n-1$ comparisons. Q.E.D.

<sub>The above proof is adapted from *Fun sort or the chaos of unordered binary search* by T. Biedl, T. Chan, E. D. Demaine, R. Fleischer, M. Golin, J.A. King, and J. I. Munro. Discrete Applied Mathematics, 144(3):231–236, 2004. </sub>

### Exercises

**Exercise 1.** Show that $\sum\_{m=1}^{\binom n2}\frac1m\le 2\log n.$ (Hint, here is the rate of divergence of harmonic series).

**Exercise 2.** (One minute or less.) Show that ${m}/\binom n2$ is the probability of `procedure rand. transpose` in bozo-sort$^+\_{\text{opt}}$ hitting one bad pair when there are $m$ bad pairs.

**Exercise 3.** Show that the expected number of bad pairs found (and, swapped) by a call to `procedure randomly permute` in bogo-sort$\_{\text{opt}}$ when there are $m$ bad pairs is $\Theta(m(n-1)/n^2)$. Show the expected number of total comparisons until the array is sorted is at most by $\Theta(n^2\log n)$.
> 0 votes

---
Tags: algorithms, algorithm-analysis, sorting
---