title: Proving FPT is strictly contained in XP

text:
# Question
Title: Proving FPT is strictly contained in XP
In their book *Fundamentals of Parameterized Complexity*, Downey and Fellows claim (in chapter 27.1) that $\mathrm{FPT}\subsetneq \mathrm{XP}$, and that this is a "basic result" that follows by "standard diagonalization", without any further reference.

I have neither been able to find a proof of this "basic result" in the literature (although many state it as a basic fact without reference), nor am I familiar enough with the "standard diagonalization" technique to easily produce a proof on my own.

Is there a full proof or more detailed sketch available in the literature? Alternatively, can you provide such a proof or sketch here? I suppose this diagonalization technique would be a basic tool in complexity theory, so looking near that field might be useful.

# Answer
By the time hierarchy theorem, there is a family of languages $(L\_k)\_{k \in \mathbb{N}}$ such that $L\_k$ is decidable in time $O(n^{2^{k+1}})$, but not in time $O(n^{2^k})$. We define $\mathcal{L} = \\{\langle k, w\rangle \mid w \in L\_k\\}$, and use $k$ as the parameter.

Then $(\mathcal{L}, k)$ is in $\mathrm{XP}$, as every fixed slice of $\mathcal{L}$ is just some language $L\_k$, which by our choice belongs to $\mathrm{P}$. However, if $(\mathcal{L},k)$ were fixed-parameter tractable, it would have some $O(f(k)\cdot n^\ell)$-decision process. But by fixing the parameter $k$ to be $\ell$, we'd get a $O(n^k)$ algorithm for $L\_k$, in contradiction to our choice of $L\_k$.
> 4 votes

---
Tags: complexity-theory, reference-request, parameterized-complexity, diagonalization
---


title: Name for scheme and host of URL

text:
# Question
Title: Name for scheme and host of URL
Is there a specific name when we refer to just the scheme and host of URL, for example `http://localhost` of the URL `http://localhost:8080/help` ?

# Answer
According to the URL spec from the WHATWG, the combination of scheme and host is a special case of what is called an **absolute-URL string**. Such a string is (in your case) a **URL-scheme string** matching a **special scheme** (e.g. `http`), followed by `://` and a **valid host string** (e.g. `localhost`), *optionally* followed by a `:` with a **URL-port string** (e.g. `8080`), which is again *optionally* followed by **path-absolute-URL string** (e.g. `/help`).

As you can see, your second string is also called an absolute-URL string by the WHATWG spec. So there seems to be no official name for the combination of only the scheme and a host. In some sense, the scheme+host does not use any of the options available, so you could perhaps call it a *minimal absolute-URL string*.
> 2 votes

---
Tags: computer-networks
---


# Question
Title: Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?
This is my first post on CS Stack Exchange. For some time, I have been studying basic graph algorithms, mainly BFS, DFS, minimum spanning trees and their basic algorithms (Kruskal and Prim). One thing I have noticed, as I have used both Skiena's Algorithm Design Manual and CLRS is that, at least in the pseuducode in CLRS, several of them have a similar structure: do something with all the vertices of the graph, do something special to the root or the first vertex (for example, set its cost to 0, as in Prim), then create a queue or a priority queue, insert all the vertices and in a loop extract one by one, check some condition and do something to their adjacency list. Why do they follow such a structure? Some of the algorithms in CLRS are similar:

PS: as I mentioned, this is my first post, not only in CS, but in all the Stackoverflow network. Any suggestion or improvement on question posting is greatly appreciated.

# Answer
When we want to design an algorithm, we mainly consider how our data is organized. When we model a problem with graph for example, the things we could do are restricted to this specified model. For example we visit a vertex for the first time, we visit it’s neighboors, we may want to mark a vertex with specific color and so on.

But this is not necessary, we may solve problems in very strange ways. Take this example when we want to check if there does not exist a path from $u$ to $v$ in the input graph with $n$ number of vertices which path lengths has a size of $O(n)$ and we are limited to logarithmic space, the algorithm which introduced by Immerman-Szelepcśenyi is not trivial at all.

What i mean is for trivial algorithms, combination of basic operations seems similar but this is not necessary for non-trivial algorithms. we may combine basic operations in very strange way to solve a problem.
> 2 votes

# Answer
One way to see the similarities between BFS and DFS is to consider them as the same algorithm (or perhaps some sort of "meta algorithm"), but using a different underlying data-structure: BFS uses a queue, while DFS uses a stack. A nice illustration of that is this figure from "IDEA Instructions":
> 1 votes

---
Tags: algorithms, graphs, graph-traversal, breadth-first-search, prims-algorithm
---


# Question
Title: What does FTP and XP stand for in "$FTP \subsetneq XP$?
What do FPT and XP stand for in this question? Proving FPT is strictly contained in XP

I don't have enough reputation to comment on that post and ask and I couldn't find the meanings of these acryonyms through Google

# Answer
FPT stands for *fixed-parameter tractable*, and is the class of *parameterized* problems solvable in time $$f(k) \cdot n^{O(1)},$$ for any function $f$. A parameterized problem is a problem that comes with a specific *parameter* that you may use exponential time in, or that we are particularly interested in. Examples of parameterized problems are Vertex Cover parameterized by solution size, Independent Set parameterized by solution size, coloring parameterized by number of colors, etc. Only the first of these belong to FPT, where as the second belong to a class W\[1\] (if you're going to ask, W is short for *weft*, don't ask).

There are few problems that make sense to cite as being in XP, (the third problem is, as Juho correctly points out para-NP-hard and not in XP). XP is "short" for slice-wise polynomial, and is the class of problems solvable in time $O(n^{f(k)})$. Note that coloring cannot be in XP (unless P = NP) since then 3-coloring (which is NP-complete) would be solvable in $O(n^{f(3)}) = O(n^c)$ time, thus rendering it polynomially solvable.
> 3 votes

# Answer
From a quick google search, I found out this Wikipedia page on FPT and this site on XP.

If you want to know what I searched: I literally googled "FPT complexity class" and it was the first result :)

---

And no, I'm not familiar with those complexity classes as well
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: What does the complexity class $\mathsf{XP}$ stand for?
$\mathsf{XP}$ is the class of problems with input length $n$ and parameter $k$ than can be solved in $O(n^{f(k)})$ time, where $f$ is a computable function. It's described on the complexity zoo page as "Fixed-parameter Tractable for Each Parameter", but I fail to see how adding "for each parameter" to the description causes such a significant change to the definition compared to $\mathsf{FPT}$, which contains problems solvable in $O(f(k)\cdot n^{O(1)})$ time.

The complexity zoo page mentions the book it was defined in, Parameterized Complexity, but I don't have access to it right now.

# Answer
There is a slightly different description for XP which I personally find less misleading: "Polynomial time for each parameter". I believe the zoo page uses FPT instead of P for some formal reasons (parameterized problems are sometimes defined as subsets of $\Sigma^\*\times\Pi^\*$, classical problems as subsets of $\Sigma^\*$). It can be noted that both formulations describe non-uniform XP, while the time bound $O(n^{f(k)})$ refers to uniform XP. In any case, the important difference is that for XP, the exponent of $n$ may depend on the parameter, for FPT it mustn't.

The practical importance of XP is as a door to parameterized complexity analysis. Once a problem is recognized as belonging to XP it makes sense to investigate its exact parameterized complexity. If it does not even belong to XP, parameterized analysis doesn't make much sense. It can also be argued that in that case the parameterization is not meaningful.
> 6 votes

# Answer
FPT stands for *fixed-parameter tractable*, and is the class of *parameterized* problems solvable in time $$f(k) \cdot n^{O(1)},$$ for any function $f$. A parameterized problem is a problem that comes with a specific *parameter* that you may use exponential time in, or that we are particularly interested in. Examples of parameterized problems are Vertex Cover parameterized by solution size, Independent Set parameterized by solution size, coloring parameterized by number of colors, etc. Only the first of these belong to FPT, where as the second belong to a class W\[1\] (if you're going to ask, W is short for *weft*, don't ask).

There are few problems that make sense to cite as being in XP. XP is "short" for slice-wise polynomial, and is the class of problems solvable in time $O(n^{f(k)})$. Note that coloring cannot be in XP (unless P = NP) since then 3-coloring (which is NP-complete) would be solvable in $O(n^{f(3)}) = O(n^c)$ time, thus rendering it polynomially solvable.

(Cross-posted from *What does FTP and XP stand for*.)
> 3 votes

---
Tags: complexity-theory, complexity-classes, parameterized-complexity
---


# Question
Title: Given two languages $A,B \subseteq \Sigma^*$, prove that $A/B$ is semi-decidable if both the languages are semi-decidable
I have found two interesting questions regarding the quotient of languages, described as:

$A/B=\\{w \mid \exists z\in B\land wz\in A\\}$

The first one is:

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

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

The second one is:

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

# Answer
Let us keep this in mind: $w\in A/B \iff \exists z\in B: wz\in A$

Since we are working with semi-decidable machines, then we have no problem iterating over all $z$'s until we find a good one!

Therefore, the idea to solve it will be the following: Let $M\_A$ be the TM for $A$, and let $M\_B$ be the TM for $B$.

We want to create a new TM for $A/B$ like so:(when given $w$ as input)

* Iterate through all $z\in \Sigma^\*$
* For each such $z$, if both $M\_B(z)$ and $M\_A(wz)$ accepted, then accept.

Notice, that there is still an important detail left! What happens if $M\_B(z)$ never stops? We will never continue to search the other $z$'s!

To solve that, we will modify the TM as follows:

* Let $T=\\{\\}$ be an empty set representing the set of all running "threads" we have created
* For $z\in \Sigma^\*$:
    + Create two new threads that will compute $M\_B(z)$ and $M\_A(wz)$ respectively. Add those two threads into $T$.
    + Do one step in every thread in $T$.
* If at any point, there is some $z$ such that both threads $M\_B(z)$ and $M\_A(wz)$ have finished executing and both accepted, then accept as well.

This solution effectively runs the machine $M\_B(z\_0)$ (for a specific $z\_0$) only one step for each new $z$ that we discover - instead of trying to run the machine until it halts. This allows us to continue to discover more new $z$'s even if the execution of those machines never ends!

I will leave it to you to verify that this machine really accepts $A/B$ :)
> 2 votes

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


# Question
Title: Is ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$?
I'd like to know if ${\Sigma\_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$ or not.
I know ${\Sigma\_2^\textsf{P}}^\textsf{NP}=\Sigma\_3^\textsf{P}\subseteq\textsf{PH}$, and I wish to know if this holds for ${\Sigma\_2^\textsf{P}}^\textsf{coNP}={\textsf{NP}^\textsf{NP}}^\textsf{coNP}$.
In other words, can we switch $\textsf{NP}$ and $\textsf{coNP}$ in the exponent and why?

# Answer
> 2 votes
For any language $L$, and for any oracle $O$, we have that $L^O=L^\overline{O}$. Substitute $NP$ instead of $O$, and $\Sigma^P\_2$ instead of $L$ and you get that ${\Sigma^P\_2}^{coNP}={\Sigma^P\_2}^{NP}$.

The statement is easy to see: Assume we have a TM $M$ for $L^O$, we want to build a TM $M'$ for $L^\overline{O}$.

The machine $M'$ will work just like $M$, except for when it asks for an oracle query $q\in \Sigma^\*$ and gets result $r\in\\{0,1\\}$, we will treat it as if we got the result $1-r$ (the binary negation of $r$). We can do this since oracles are guaranteed to always return an answer, even if the query is not in the language.

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Show that for a singly-connected graph the number of edges $E$ must be equal to the number of vertices minus $1$, $E=V-1$
I am reading "Bayesian Reasoning and Machine Learning By David Barber". I am not completely sure how to do question 19 on page 23:

Show that for a connected graph that is **singly-connected**, the number of edges $E$ must be equal to the number of vertices minus $1$, $E=V-1$. Give an example graph with $E=V-1$ that is not singly connected.

> Definition (Singly-Connected Graph). A graph is singly-connected if there is only one path from a vertex a to another vertex b. Otherwise the graph is multiply-connected. This definition applies regardless of whether or not the edges in the graph are directed. An alternative name for a singly-connected graph is a tree. A multiply-connected graph is also called loopy.

My approach to proving that $E=V-1$:

Proof by induction:

Let $P(n)$ be the statement that a singly-connected graph with $n$ vertices has $n-1$ edges.

We prove the base case, $P(1)$:

For a graph $G$ with $1$ vertex, it is clear that there are $0$ edges. (\**Question 1:\**Is this correct though, why can't there be $1$ or even $2$ edges such that this one vertex connects to itself with $1$ or $2$ paths respectively?)

We now prove the case for $P(n+1)$:

Suppose for the sake of induction that $P(n)$ is true. Let $G$ be a singly-connected graph with $n$ vertices and hence $n-1$ edges. Then if we add a vertex to $G$ with one edge connecting it to any of the vertices of $G$, then we have a new graph $G'$ which has $n+1$ vertices and $n$ edges.

Hence we have shown that $P(n)\implies P(n+1)$ and hence it it true for all $n\in \mathbb{N}$

**Question 2:** Would this proof be correct?

**Question 3:** I can't think of a graph which is not singly connected but has $E=V-1$ edges. What would be some examples?

# Answer
> 1 votes
For your question 1, as already noted by rici, you cannot have loops (edges connected a vertex to itself) in singly-connected graphs (which are often also called trees). In most graph textbook definitions in my experience as well, loops are not allowed.

For your question 2, also as noted by rici, your approach constructs a specific instance of P(n+1) so you do not prove that the the claim works for all instances of P(n+1).

In order to prove that this holds for any instance, you are right that you can work by induction but you must work in reverse: consider a tree with n+1 vertices. You must extract a tree with n vertices from it. The property holds for it because you have proven that it holds for all trees with n vertices. Then you must use the relationship between the two to show that the wanted property holds for the larger object.

In this case I would go like this: consider a tree with n+1 vertices. It's easy to show that it has at least one vertex with degree 1. Remove this vertex. You now have a tree with n node, and therefore with n-1 edges (by induction hypothesis). Your original n+1 vertex tree has one more vertex and one more edge, so it must have n+1 vertices and n edges, so the property holds for trees with n+1 vertices (notice that I did not make any assumption on the original tree with n+1 vertices I used so the proof is valid for any such tree).

# Answer
> 1 votes
$\underline{Answer1}$: Proof by induction

$Proof$: Let n be the number of vertices in a tree (T).

$~~~~~~~Base~cases$:

```
   If n=1, then the number of edges=0.

   If n=2 then the number of edges=1.

   If n=3 then the number of edges=2.

```

Hence, the statement (or result) is true for n=1, 2, 3.

Let the statement be true for n=m. Now we want to prove that it is true for n=m+1.

Let $E$ be the edge connecting vertices say $V\_i$ and $V\_j$. Since $G$ is a tree, then there exists only one path between vertices $V\_i$ and $V\_j$. Hence if we delete edge $E$ it will be disconnected graph into two components $G1$ and $G2$ say. These components have less than $m+1$ vertices and there is no circuit and hence each component $G1$ and $G2$ have $m1$ and $m2$ vertices.

```
     Now, the total no. of edges = (m1-1) + (m2-1) +1
                                 = (m1+m2)-1
                                 = m+1-1
                                 = m.

```

Hence for n=m+1 vertices there are m edges in a tree (T). By the mathematical induction the graph exactly has n-1 edges.

$\underline {Answer2}:$

The one you have done is other technic (also correct) but uses the same induction idea.

$\underline {Answer3}:$

A singly connected graph $G(V, ~E)$ is a directed graph which has at most 1 path from $u$ to $v$, $\forall$ $u,~v \in V$. So, a Non-singly graph would imply that the graph has atleast 2 paths from $u$ to $v$ (which could be formed by adding edges between the vertices to singly connected graph), hence number of vertices remain the same but not the edges (number of edged increases compared to singly connected), so $|E|\>|V|-1$ for non-singly connected graph.

Hence you cannot come up with such graph.

---
Tags: graphs, induction
---


title: How does Sipser's 0n1n PDA reject 0101?

text:
# Question
Title: How does Sipser's 0n1n PDA reject 0101?
In Sipser's Theory of Comp in 2.2 the following PDA is provided for ${\\{0^n1^n|n\ge0}\\}$.

I follow how to process `""`, `"01"`, `"0011"`. I want to reject `"0101"`, however it seems one of the nondeterministic paths makes it to accept. I'm probably misunderstanding a detail of PDA -- my logic is as follows:

1. Start in `q1`
2. Take $\varepsilon$ transition, push `$` on stack, state is now `q2`
3. Take `0` loop transition, push `0` on stack, state stays `q2`
4. Take `1` transition, pop the `0`, update state to `q3`
5. Take $\varepsilon$ transition, pop `$` off, enter accept state `q4`
6. The other path is ignored out of `q3`
7. But we've still got another `01` on the input string with no exits out of `q4`, so accept... or assume dead state somehow?

# Answer
> 2 votes
Being in state $q\_4$ and still having $01$ to read means that the word cannot be accepted (at least with this reading path).

Using this formal definition, there is no path leading from the configuration $(q\_0, 0101, Z)$ to a configuration $(q, \varepsilon, \gamma)$, so $0101$ is not accepted by the automaton.

---
Tags: pushdown-automata
---


# Question
Title: Prove that a hamiltonian DAG has a single topological sort
I've been straggling a little proving the argument "a hamiltonian directed acyclic graph has a single topological sort".

This is pretty much the idea of what I've come along:

* lets prove by contradiction. so lets assume a hamiltonian DAG has at least 2 topological sorts.
* If there're few topological sorts - it means one of the following options:
* either there're at least 2 vertices that aren't dependent. meaning both of these vertices could be with 0 in-degree. but it contradicts the fact that the graph is hamiltonian (there's a hamilton path in G)
* either there exists a vertex that splits to 2 branches. such that the neighboring vertices could appear in different order in the topological sort. but it contradicts that the graph is hamiltonian because in such a case - after choosing a branch, we won't be able to visit the vertices of the second branch. however if we do have this possibility, we have come to a cycle that ends in the vertex that split to 2 branches. (contradiction to the graph being a DAG)
* Finally we get contradiction to our assume - thus the original statement is correct.

Would appreciate your thoughts and suggestions about the idea of proof.

# Answer
> 1 votes
Let $G=(V,E)$ be a Hamiltonian DAG.

Since $G$ is Hamiltonian, there exists a path $p = \[v\_1, \ldots, v\_n\]$ where $\\{v\_1,\ldots, v\_n\\}=V$. By definition, $p$ is a topological ordering.

Note that $v\_i$ must come after each of $v\_1, \ldots, v\_{i-1}$ in *every* topological ordering, since we have path $\[v\_j, \cdots, v\_i\]$ for each $j$ smaller than $i$. Likewise, $v\_{i+1}, \ldots, v\_n$ must come after $v\_i$ in every topological ordering since $v\_i$ has a path to each of those.

Hence $v\_i$ occurs in position $i$ in every topological ordering, i.e. every topological ordering is equal to $p$.

---
Tags: algorithms, graphs, search-algorithms, hamiltonian-path
---


# Question
Title: PRNG for generating numbers with n set bits exactly
I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 \< n \< 64$ and return a pseudo-random 64-bit number with exactly $n$ bits set to $1$, and the rest set to 0.

My current approach involves something like this:

1. Generate a pseudorandom 64-bit number $k$.
2. Count the bits in $k$, storing the result in $b$.
3. If $b = n$, output $k$; otherwise go to 1.

This works, but it seems inelegant. Is there some kind of PRNG algorithm which can generate numbers with $n$ set bits more elegantly than this?

# Answer
> 12 votes
What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern.

This is known as enumerative coding, and it's one of the oldest deployed compression algorithms. Probably the simplest algorithm is from Thomas Cover. It's based on the simple observation that if you have a word that is $n$ bits long, where the set bits are $x\_k \ldots x\_1$ in most-significant bit order, then the position of this word in the lexicographic ordering of all words with this property is:

$$\sum\_{1 \le i \le k} { x\_i \choose i}$$

So, for example, for a 7-bit word:

$$i(0000111) = { 2 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 0$$ $$i(0001011) = { 3 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 1$$ $$i(0001101) = { 3 \choose 3 } + {2 \choose 2 } + {0 \choose 1} = 2$$

...and so on.

To get the bit pattern from the ordinal, you just decode each bit in turn. Something like this, in a C-like language:

```
uint64_t decode(uint64_t ones, uint64_t ordinal)
{
    uint64_t bits = 0;
    for (uint64_t bit = 63; ones > 0; --bit)
    {
        uint64_t nCk = choose(bit, ones);
        if (ordinal >= nCk)
        {
            ordinal -= nCk;
            bits |= 1 << bit;
            --ones;
        }
    }
    return bits;
}

```

Note that since you only need binomial coefficients up to 64, you can precompute them.

---

* Cover, T., *Enumerative Source Encoding*. IEEE Transactions on Information Theory, Vol IT-19, No 1, Jan 1973.

# Answer
> 3 votes
Very similar to Pseudonym's answer, obtained by other means.

The total number of available combinations is approachable by the stars and bars method, so it will have to be $c=\binom{64}{n}$. The total number of 64-bit numbers from which you would be trying to sample your number would be obviously much higher than that.

What you need then is a function that can lead you from a pseudorandom number $k$, ranging from $1$ to $c$, to the corresponding 64-bit combination.

Pascal's triangle can help you with that, because every node's value represents exactly the number of paths from that node to the root of the triangle, and every path can be made to represent one of the strings you are looking for, if all left turns are labeled with a $1$, and every right turn with a $0$.

So let $x$ be the number of bits left to determine, and $y$ be the number of ones left to use.

We know that $\binom{x}{y}=\binom{x-1}{y}+\binom{x-1}{y-1}$, and we can use it to properly determine the next bit of the number at each step:

$\mathtt{while}\\;\\;\\; x\>0$

$\quad \mathtt{if}\\;\\;\\; x\>y$

$\qquad \mathtt{if}\\;\\;\\;k\>\binom{x-1}{y}: \\;\\;\\;s \leftarrow s\\; + \mathtt{"1"}, \\;k\leftarrow k-\binom{x-1}{y}, \\;y \leftarrow y-1$

$\qquad \mathtt{else}:\\; \\;s \leftarrow s\\; + \mathtt{"0"}$

$\quad \mathtt{else}: \\;\\;s \leftarrow s\\; + \mathtt{"1"}, \\;y \leftarrow y-1$

$\quad x \leftarrow x-1$

# Answer
> 2 votes
Another quite elegant method is to use bisection as described in this stackoverflow answer. The idea is to keep two words, one known to have at most k bits set and one known to have at least k bits set, and use randomness to move one of these towards having exactly k bits. Here is some source code to illustrate it:

```
word randomKBits(int k) {
    word min = 0;
    word max = word(~word(0)); // all 1s
    int n = 0;
    while (n != k) {
        word x = randomWord();
        x = min | (x & max);
        n = popcount(x);
        if (n > k)
            max = x;
        else
            min = x;
    }
    return min;
}

```

I made a performance comparison of various methods and this one is typically the fastest unless k is known to be very small.

# Answer
> 1 votes
You can do the following :

1) Generate random number,$k$ between $1$ and $64$.

2) Set $k$ th $0$ to $1$.

3)Repeat steps 1 and 2 $n$ times

$A\[\]$ is $64$ bit array with all $0$s

```
for(i=1 to n)
{
    k=ran(1,65-i) % random number between 1 and 65-i
    for(x=1;x<65;x++)
    {
        if(A[x]==0)k--;
        if(k==0)break;
    }
    A[x]=1;
}

```

# Answer
> 0 votes
How about setting a random bit, if it is not already set, until k bits are set?

---
Tags: algorithms, information-theory, coding-theory, pseudo-random-generators
---


title: Minimum Cost Arrangement

text:
# Question
Title: Minimum Cost Arrangement
I want to find an arrangement to evenly place 12 items ($a\_1, a\_2, ..., a\_{12}$) into 4 boxes ($b\_1, b\_2, b\_3, b\_4$) such that the cost is minimal.

Let $b(x)$ be the index of the box that contains item $x$. The cost of an arrangement is

$$\sum\_{i=1}^{12} \sum\_{j=1}^{12} |b(a\_i) - b(a\_j)| M\_{i,j}$$

where $M$ is a $12\times 12$ constant matrix where all values are non-negatives.

---

For this instance I could use brute force with $\frac{12!}{3!3!3!3!}$ iterations, but I hope to get a generalised solution that can solve for $N$ items and $K$ boxes in a faster way.

Is there a solution faster than brute force? I have tried some operations research library (such as Google OR tools, CVXPY) but am unable to reduce the problem into a readily acceptable representation.

My intuition tells me there is no faster solution than brute force. In that case, is there an approximation algorithm that can provide good enough solution?

# Answer
> 1 votes
You could try expressing this as an integer linear expression: let $v\_{x,b}$ be 1 if item $x$ is placed in box $b$, and let $w\_{x,x',b,b'}$ be 1 if $v\_{x,b}=1$ and $v\_{x',b'}=1$; then your objective function is a linear function of these zero-or-one variables. You can also enforce the relationship between the $v$'s and $w$'s, and ensure that the $v$'s represent a valid placement into boxes, using the techniques in Express boolean logic operations in zero-one integer linear programming (ILP). Then, feed the resulting ILP to an off-the-shelf ILP solver. I don't know whether this would be faster than brute force, but it is something you could try.

---
Tags: optimization
---


# Question
Title: Are programs just "words" of a formal language?
Every formal language is a subset of E\*.

Let's say this formal language is python. If a program is syntactically correct, then the Python Automata accepts the "word", which is the program. If that is true, what are the atomic elements like "print" called?

Is this correct? Please correct my thought on this.

# Answer
I think that your intuition is correct but the exact details of its explanation are fuzzy. Every syntactically correct program is a "word" or a "sentence" (depends on what you prefer) of some language $\mathcal{L}$.

In the context of lexer-full parsing, the "automaton" (intended as the program that prints "syntax error" in case of error) that accepts the language is composed of 2 distinct automata that cooperate to decide whether $\mathcal{p}\in\mathcal{L}$. They are the lexer and the parser.

The former is responsible for accepting the sequence of keywords and basic constructs of the language (int, for, while, print, +, -, numbers,...).

The latter is responsible for checking that sequences of non-terminal and terminal symbols (keywords and their sequences) form correct sentences.

Namely, the lexer is able to tell that "for" is a word of the language, but is unable to tell that "for while () }}}" makes no sense. That's the purpose of the parser.

Since both automata (lexer and parser) are accepting a language, all the sequences of characters or symbols accepted are words of their languages.

In general, informally, the lexer accepts words, while the parser accepts sentences. This is simply a handy way to distinguish sequences of characters from sequences of symbols read by the lexer. Still, there's no strict nomenclature.
> 2 votes

---
Tags: formal-languages
---


# Question
Title: Definition of static property of object in OOP
Grady Booch in Object-Oriented Analysis and Design with Applications says:

> The state of an object encompasses all of the (usually static) properties of the object plus the current (usually dynamic) values of each of these properties ...

Then:

> Another property of a vending machine is that it can accept money. This is a static (i.e., fixed) property, meaning that it is an essential characteristic of a vending machine.

Then:

> All properties have some value. This value might be a simple quantity, or it might denote another object.

I am in doubt in about "`the ability of accepting money`" is a real property. Instead it seems it describes a behavior. Also Grady Booch says "All properties have some value."; but what is the value of "`the ability of accepting money`"?

# Answer
He apparently means to say that the existence of a particular property is usually common to every instance of a class (*static*, in that sense), while its value is not.

For example, *time\_of\_birth* is a property common to all *Person*s, while its value is not.
> 0 votes

---
Tags: terminology, reference-request, object-oriented
---


title: Building a game tree from a board game

text:
# Question
Title: Building a game tree from a board game
Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge. The goal of this game is being able to survive a certain number of turns (25) without running out of gas or food (starting with 100 gas and 50 food), the score depends on how filled this two gauges are (from 1 to 100, 0 is game over). Every turn these gauges loss a set amount (-10 for gas, -5 for food), but across the board there are nodes where these gauges can be replenished by a set amount (+100 for gas, +40 for food), after using a node, it will become unavailable for a set amount of turns (10 turns), using a node also counts as a turn, so the gauges are reduced.

I've been reading about game trees to represent two-player games and how they're used for Go, Chess and others, but aside not being able to find information about single player games, one big question popped in my mind. **"How can I build a tree from a board game like this?"**

I would be really grateful if you could point me towards books or papers that could teach me how to build a tree for this purpose, my only clue is the max depth can be 25 at most, was also thinking about graphs, but in all honestly, I'm completely lost on how can I generate a tree from any random board this game can have.

Thank you.

# Answer
I think a search tree can be used to solve this problem, but I'm not sure that is the right way to go.

I think it makes more sense to model the game as a finite state machine. Properties of your board would be part of the "state", such as your current food and gas and position on the game board. What happens after each valid move would be a transition in this state machine. Extending the state machine with some "dynamic" transitions could be useful, such as "advance a turn unless food or gas is $\leq0$" (this allows you to build the state machine purely with the knowledge of the locations.)

After building the state machine, you need to simulate it to find if the winning state is reachable. If so, the path that reaches that state is the solution to your game. Since the total "depth" of your state machine is small, running any reasonable path-finding algorithm would do.
> 2 votes

---
Tags: algorithms, graphs, trees, board-games
---


title: Invariant vs Assertion vs lemma

text:
# Question
Title: Invariant vs Assertion vs lemma
I am reading Distributed Algorithms by Nancy Lynch. I have come across lemmas, assertions and invariants, but I do not understand the difference between them. I think lemma means an intermediate result. Can someone please dexplain the definitions for each?

# Answer
> 4 votes
All terms describe formal claims that are true. The main difference is in how they are used.

A *lemma* is mathematical claim that is (generally) true. In textbooks, Lemma's are usually either proven, left as an exercise, or assumed to be prior knowledge. A lemma is distinguished from a *theorem* in that the lemma is usually a less important or intermediate result.

An *assertion* is a claim, again supposed to be true. An assertion can be made in a proof, but also by a computer program or algorithm. In the latter case, the assertion is often tested, i.e. a computer program checks if the claim is true.

An *invariant* is a property of some (mathematical) process that remains true over time. For example, a *loop invariant* is a property that remains true during the execution of a loop.

---
Tags: algorithms, proof-techniques, discrete-mathematics, distributed-systems, concurrency
---


# Question
Title: How to find an algorithm to calculate the best move for this graph based strategy game?
I'm prototyping a deterministic Risk like game. A player can move units from one node to a connected node if he has more than 1 unit the in origin node (must leave 1 unit behind). The player wins if he conquers the enemy's home node. Battles are settled by multiplying the node's defensive units by the defensive rate and then subtracting the attacking units; if the result is a number higher than 0 the attacking player conquers the node and the surviving units are moved to the conquered node. A node has a spawn rate that spawns units (belonging to the player controlling the node) every x turns.

I don't have much experience with graphs so I'm hoping I can get some help finding an algorithm that can calculate either the shortest possible winning move (if we are in a winning position) or the list of possible defensive moves that can be taken to avoid the other player win (if the other player has a shot at winning, but we can do something about it).

**Examples**

*\[EDIT\] On each node there are two numbers: the top number represents the number of units in that node, and the bottom number represents the spawn rate, which for this examples is always 0*

*Node indexes that I'll use bellow: \[First level\] 0,0 \[Second level\] 1,0; 1,1 \[Third level\] 2,0; 2,1, 2,2 ...*

*For this example the nodes are only connected from one level to the other; one diagonal away. This will not matter for the algorithm as every node will know which nodes it has connection with.*

*(1,0 is connected with: 0,0; 2,0; 2,1)*

*(2,1 is connected with: 1,0; 1,1; 3,1; 3,2), etc*

*Home node is 0,0*

*Red to move*

Red has two possible winning moves:

\[Shortest\] **3,0 -\> 2,0 -\> 1,0 -\> 0,0 + 2,2 -\> 1,1 -\> 0,0**

*\[Longest (should be ignored)\] **3,0 -\> 2,0 -\> 1,0 -\> 0,0 + 3,2 -\> 2,1 / 2,2 -\> 1,1 -\> 0,0***

*Green to move*

Green has four moves he must choose from to avoid certain defeat:

**3,1 -\> 2,0** | **3,1 -\> 2,1** | **3,2 -\> 2,1** | **2,2 -\> 1,1**

The algorithm doesn't need to take into account the defensive rate and the spawn rate. I can figure that part out.

Hopefully this will be not too difficult for someone with graph related algorithm experience.

\[EDIT\]

To clarify something asked in the comments: The players take turns doing moves, sequentially, and may only move units (from one node to another) once per turn. The algorithm must take into account possible counter play by the opponent, and discard solutions where the opponent was able to defend in time.

It is important to chose the shortest winning move so that in cases where the opponent also has a a winning move (on another graph, an inverted triangle from the one depicted in the image, but with the "home node" colored red, belonging to the opponent), we can then compare the winning move sequence length and see who gets there first.

I don't want an algorithm to solve the entire game, only the sub game depicted in the example. For the entire game I'm using MCTS where other moves are considered, like which nodes to update, etc. This algorithm will be used for selection / expand, and possibly rollout in the MCTS, if I get something very fast.

Currently I'm looking into backwards induction, it is straight forward to implement, but it is quite expensive, even with lots of optimizations (discussion in the comments). So a more performant alternative would be great!

# Answer
> 1 votes
Following Arno suggestion in the comments I've done a C# backwards induction implementation that includes dealing with state transposition. Here is the code for the runner class, the node class should be very straight forward to do. Hopefully it will help someone!

```
public class BackwardsInduction
{
    private Func<IGameState, Move[]> moveSelectionFunc;
    private Func<IGameState, double[]> scoresFunc;
    private readonly double defaultScore;
    private readonly int nodeStartLevel;
    private readonly int nodeEndLevel;
    private List<List<BINode>> nodesPerLevel;

    private List<IGameState> gameStates;

    private Dictionary<int, BINode> visitedGameStatesHash;

    public BackwardsInduction(Func<IGameState, Move[]> moveSelectionFunc, Func<IGameState, double[]> scoresFunc, double defaultScore, int nodeStartLevel, int nodeEndLevel)
    {
        this.moveSelectionFunc = moveSelectionFunc;
        this.scoresFunc = scoresFunc;
        this.defaultScore = defaultScore;
        this.nodeStartLevel = nodeStartLevel;
        this.nodeEndLevel = nodeEndLevel;
        nodesPerLevel = new List<List<BINode>>();
        gameStates = new List<IGameState>();
        visitedGameStatesHash = new Dictionary<int, BINode>();
    }

    public BINode RunGetRootNode(IGameState rootState, int? maxDepth)
    {
        var rootNode = new BINode(playerJustMoved: rootState.PlayerToMove, defaultScore: defaultScore);
        nodesPerLevel.Add(new List<BINode>() { rootNode });
        Run(rootState, rootNode, maxDepth);
        if (rootNode == null)
        {
            return null;
        }
        BackFillScores();

        return rootNode;
    }

    public void Run(IGameState currentState, BINode currentNode, int? maxDepth, int currentLevel = 0)
    {
        var availableMoves = moveSelectionFunc(currentState);
        if (availableMoves.Length == 0)
        {
            currentNode.Scores = scoresFunc(currentState);
        }
        if (nodesPerLevel.Count <= currentLevel)
        {
            nodesPerLevel.Add(new List<BINode>());
        }
        if (maxDepth == null || currentLevel < maxDepth.Value)
        {
            foreach (var move in availableMoves)
            {
                var newState = currentState.Clone() as IGameState;
                var thisNodePlayerJustMoved = newState.PlayerToMove;
                newState.DoMove(move);
                var gameStateHash = GetGameStateHashCode(newState);
                if (visitedGameStatesHash.TryGetValue(gameStateHash, out BINode transposedNode))
                {
                    currentNode.AddTransposedNode(transposedNode);
                    continue;
                }

                var newNode = currentNode.AddChildGetNode(move, thisNodePlayerJustMoved, newState);
                visitedGameStatesHash.Add(gameStateHash, newNode);

                nodesPerLevel[currentLevel].Add(newNode);

                Run(newState, newNode, maxDepth, currentLevel + 1);
            }
        }
    }

    public void BackFillScores()
    {
        for (int i = nodesPerLevel.Count - 2; i >= 0; i--)
        {
            foreach (var node in nodesPerLevel[i])
            {
                if (node.ChildNodes.Any())
                {
                    node.Scores = node.ChildNodes.MinObject(x => x.Scores[x.PlayerJustMoved.Id]).Scores;
                }
            }
        }
    }

    private int GetGameStateHashCode(IGameState gameState)
    {
        unchecked
        {
            int hash = 17;
            for (int level = nodeStartLevel; level <= nodeEndLevel; level++)
            {
                var levelNodes = gameState.Nodes[level];
                for (int index = 0; index < levelNodes.Length; index++)
                {
                    hash = hash * 23 + levelNodes[index].GetSimplifiedHash();
                }
            }
            hash = hash * 23 + gameState.PlayerToMove.Id;
            hash = hash * 23 + gameState.PlayerToMove.MoveCount;
            return hash;
        }
    }
}

```

This is not the optimal solution for my scenario because it has to process a huge state tree and is quite expensive. But it solves my problem for now and outputs the correct result.

---
Tags: algorithms, graphs, game-theory
---


# Question
Title: What is the computer science interpretation of a qubit?
I am a CS major trying to decipher quantum computing. I have done some elementary study on qubits and I always seem to get lost at the "infinitely many" states that the qubit can have. And I really want to understand what it actually means. My understanding is as follows and please correct me if I am wrong,

A classical bit has two states 0 and 1, which means *n* bits can represent *2^n* different states, though each state is individually expressed. A Qubit could have "infinitely many" states between 0 and 1. This means that *n* qubits can represent *m^n* states, Where 'm' is the base and m \> 2. This would mean we can represent larger numbers using fewer qubits when compared to the classical bit. If this is so, how does this lead to an increase in computation speeds?

If I am completely off track, what is the actual interpretation of a qubit?

# Answer
> 4 votes
A qubit is a vector in a 2-state complex space. Its vector form is something like Qubit = $ax + by$, which by convention in Dirac notation is $|Q\rangle = a|0\rangle + b|1\rangle$, where $|0\rangle$ and $|1\rangle$ represent linearly independent basis vectors and the coefficients $a,b$ are complex numbers. $a^2$ and $b^2$ represent the probability of measuring 0 or 1, and they can take on any complex value as long as $|a|^2 + |b|^2 = 1$ (which must be true because we only have one qubit).

In this framework, the qubit acts like a vector pointing from the origin which naturally evolves or rotates around the infinitely many surface points of a ‘Bloch Sphere’ except when it’s measured it only ever tells you 0 or 1 (which represent the north and south poles of the sphere).

In short, a qubit is a vector.

The ‘infinitely many’ language comes from the ability of $a,b$ to take on any complex value so long as their squares equal 1. Measuring a qubit (meaning when you read it, touch it, look at it, record its value etc) only gives you 0 or 1, not both and not a decimal in between.

If you also think of the qubit as a wave, then the goal of quantum computing is to take a superposition of all possible results of a qubit string (000, 001, 010, 011 etc), weight the components appropriately to constructively and destructively interfere with one another, so that at the very end you’re biased to get the right result... with a nonzero probability that you will get the wrong answer even if you do everything right.

Incidentally a string of three qubits, you’ll notice, is the tensor product of three qubit vectors. This creates a complex space with $2^3 = 8$ basis vectors which our 3-string qubit can happily explore.

# Answer
> 0 votes
A QuBit is an element of a quantum circuit.

Like regular bits, a QuBit has two states, 0 or 1. Unlike regular bits, a QuBit can be in a superposition of these states.

Point 1: This gives us a terminology problem: What should be meant by "state" when talking about quantum systems. This is a problem only if classical terminology is stretched too far. Accept that new understandings are needed for quantum systems, and don't get stuck in terminology issues.

Point 2: An understanding of "superposition" is needed. That would be a long topic to discuss by itself, and is not discussed here.

A single QuBit system isn't very useful. Using an operator to put a single QuBit into a state which assigns equal probability to either state then examining the state of the QuBit gives you the same result as a fair coin toss.

Point 3: "Operator" is another specific technical term. Loosely speaking, in a single bit system, operators might be "1" (set to the 1 state), "0" (set to the 0 state), "1/2" (set to the 1 state superimposed with the 0 state, with equal probabilities). Operators are more interesting when talking about more than one QuBit.

In a quantum circuit which has multiple QuBits, the states of QuBits can be entangled with each other. The circuit is programmed by applying quantum operators to pairs of QuBits. This puts the entire circuit in an entangled state. At this point, meaningful computation becomes possible.

Point 4: "Entangled" gives us the last technical term. This is another long topic which is not discussed here.

That's a start. To understand how computation is done using QuBits, all of the above should be understood. That will require understanding a number of computer science concepts as well as a number of concepts from quantum physics.

Point 5: Wait! What about complex numbers and probability amplitudes? Or 'ket notation?

All of that is important when talking concretely about superposition, entanglement, and operators. But one step at a time. This answer is to provide a brief description of what is a QuBit.

# Answer
> 0 votes
In the previous answer:

"weight the components appropriately to constructively and destructively interfere with one another, so that at the very end you’re biased to get the right result... with a nonzero probability that you will get the wrong answer even if you do everything right."

Let's translate this.

a. weight the components appropriately.. hmm b. to constructively and destructively interfere with one another... c. so that at the very end you’re biased to get the right result... d. with a nonzero probability that you will get the wrong answer... e. even if you do everything right.

Let's think about this for a little more than a moment as you place your bet at a Roulette Table.

I'm at the roulette table with 37 slots including TWO double-Zeros. The final answer, the winner, is decided by elements of a. The roughness of the track the ball runs in... b. the amount of oil on the spinners fingers... c. the flip of his/her hand and how many times the ball has been flipped... d. The nearly infinite ways the ball can bounce when it falls out of the track... e. and.. where the wheel started, and where it was when the ball left the track...

You may notice the infinite amount of possible variations but really, only 37 answers. How hard can this be? These five listed variable are just the most obvious one out of a million others and is a micro description of "Weight the components correctly." But... The 'Vectors within a Qubit cover all that so Let's let that be handled by ONE Qubit.

Once the ball leaves the track and begins to bounce around inside the wheel... there is an infinite number of ways "to constructively and destructively interfere with one another." Lets let that be handled by the ONE MORE Qubit. Omy, the power we have here!

"so that at the very end you’re biased to get the right result." meaning... we need to let some or all of our Qubits be biased in such a way as to always (most always) predict an outcome that matches the expected answer.. 1-37. Looks like we have to let Qubit one interact with Qubit two.

Of course the non-zero probability of producing the right answer is STILL 1 out of 37 as the game is being played in the Casino and our money may be long gone before we can possibly change all the input required to help us win even one spin of the wheel.

As admitted.. "even if you do everything right." Odds are against being right the first time... Wanna take a Moon ride based on the output of this computer?

The idea is that if you can bias up the input and provide the right entanglement and the right forces of constructive and destructive interaction... you might somehow resolve a 64 encryption code with a minimum number of 'readings' of the Qubits and more quickly produce the actual code out of 1.8446744e+19 possibilities. There you go. Enjoy.

Finally... (I do have a little experience with the pre-cursors of Quantum computing.) I knew of a person that tried to simulate the mentioned inputs of our quantum computer by biasing the two sides of two flip-flops to simulate the multiple inputs of a given neuron in the human nervous system. The idea was to bias the two sides of a binary flip-flop and then power it up and see if it became a Binary One or Zero. The constructive/destructive part was simulated with positive and negative voltages. The interaction of Two flipflops was simulated with capacitive or inductive coupling between the inputs of the two flipflops. At power up time, the answer would be 00 01 10 or 11 from the two bits, exactly like the answer produced by two Qubits. That answer was completely dependent on INPUT and an expected result.

Think about it. What kind of input is needed to resolve a 64bit encryption code. See the problem?? There is NO KNOWN input to do that. Is there anything about entanglement that will help get us to the right required input? Simply stated. No. Admittedly, the possibilities ARE limitless but so are the number of wrong answers.

By the way... neurons are tiny little frequency generators... Each one only goes up or down in frequency.. with zero F being the unstimulated state and High F resulting when multiple inputs... of varying input frequency produce any one of an infinite number of output frequencies by the neuron. I would more likely spend my money in that direction if we are talking about how quickly the brain can identify a face in a crowd. The RGB sensors in our eyes can produce an infinite number of colors by producing just three frequency generators per pixel of color sensing. Effectively three bits per pixel. How many Qubits will be needed to tell if a car is maroon or beet colored? *yikes!* My daughter could do that when she was four. Just a thought.

---
Tags: quantum-computing
---


# Question
Title: What is the reason for this contradiction about the size of the char type?
the size of one char in C is 4 bytes, however to define an 'A' character we use the sum of two values like this expression here:

or in other way i want to say that the char is 4 bytes size, but in the example it shows that the size is 8 bytes.

how it happens, what is wrong here ?

# Answer
Sizeof(char) = sizeof(unsigned char) = sizeof(signed char) = 1 by definition in C and C++. And char contains at least 8 bit (it can be more, but 8 is by far the most common).

So your assumption that the size of one char in C is 4 is wrong. However, in C a character literal like 'x' has type int, not type char, so sizeof('x') = sizeof(int) is usually larger than 1, and 4 is not unusual but in no way guaranteed.

Your calculation doesn’t show that sizeof(char) would be 8 in any way, because you confused “bit” and “byte”.
> 1 votes

---
Tags: programming-languages, virtual-memory, bit-manipulation
---


title: important separators

text:
# Question
Title: important separators
Given a graph G and an important (X,Y)-separator S, why is it true that for every edge e in S the set of S\e is an important (X,Y)-separator in G\e

Important (X,Y) cut is defined as follows: S is an important (X,Y)-cut if it is inclusion-wise minimal and there is no (X,Y)-cut S' with $|S'|\<=|S|$ such that R' dominates R where R,R' are the sets of vertices reachable from X in $G/S, G/S'$ respectively.

I understand that this is a basic claim in the proof of bounding important separators at $4^k$ and I somewhat understand the logic that every other edge disjoint path doesn't contain e but I'm stumbled here

I'm doing a presentation on important separators based on https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf book at chapter 8.

It's stated as Proposition 8.9 and given as exercise. (I'm just trying to get the logic behind this claim)

# Answer
Say that $S\setminus e$ is not an important separator in $G\setminus e$. In other words, there exists a cut $S'$ in $G\setminus e$ with $|S'|\<|S\setminus e|$ and $R'\supset R$. Now, observe that $S'\cup\\{e\\}$ must be a cut in $G$ with $|S'\cup\\{e\\}|\<|S|$ and $R'\supset R$. But that implies that $S$ is not an important separator in $G$.
> 0 votes

---
Tags: graphs, minimum-cuts
---


# Question
Title: Maximum number of distinct nodes that can be visited on a single walk
Given a directed graph which may contain cycles, how can I find the maximum number of *distinct* nodes that can be visited on a single walk?

I have done some research and the most similar-*sounding* problem I have found is the longest path problem, which is in fact rather different as far as I understand it: it is not concerned with walks, but simple paths.

The first solution that pops into my mind is to:

1. Label all nodes with 1.
2. Find a cycle and replace it with a *single* node labelled with the sum of the labels of the nodes in the cycle. This newly-created node should retain all incoming and outgoing edges of the cycle it replaces (considered as a whole).
3. Repeat step 2 until no cycles can be found.
4. Replace each node with a chain the length of which is determined by the node's label. Retain the incoming and outgoing edges of the original node by connecting them to the beginning and the end of the chain, respectively.
5. We should have a DAG at this point. A cursory Google search reveals linear time algorithms to solve the "longest path in a DAG" problem.

This sounds horribly complicated (even assuming it's correct to begin with) and I was wondering if I could leverage your expertise to improve this solution, or scrap it altogether and come up with something sensible, or even reframe the problem so that a solution is easier to find.

# Answer
> 3 votes
The problem you have is the following: You have a directed graph and you are allowed to visit the same vertices and edges many times over. You want to find a walk starting in a vertex $s$ that visits as many vertices as possible.

First observation is that in a strongly connected component (SCC), you can visit every vertex in that SCC as many times you want.

Second observation is that if you create the "meta-graph" where each SCC is a weighted node (the weight is the number of vertices in the SCC in the original graph), then you have a DAG (this is an exercise to prove).

Third observation, which the OP pointed out, is that the problem is polynomially solvable in a DAG (it is also polytime in weighted DAGs).

The algorithm then becomes:

1. Construct the SCC-DAG
2. Run the (weighted version) of the polytime algorithm for DAGs.

---
Tags: graphs, dag, directed-graphs
---


# Question
Title: What are the reasons for solution assumptions behind the longest subsequence problem?
All O(N^2) solutions that I have seen for the longest increasing subsequence problem, as their first step, state something like this "Let L\[i\] be the length of the LIS **ending** at index i...":

And, while this is a working assumption (the one that helps us solve the problem), I'm more curious on why one shall assume that and pick this approach? Or, in other words, how does one's thought process evolve and end up with an idea that an array must be introduced where each element is a length of a subsequence that **ends at i** -- here, I'm questioning exactly, why L\[i\] shall reflect a subsequence **ending** at *i* (i.e. why not **starting** at *i*)?

To better illustrate my question: when I was trying to solve the problem myself, without knowing the solution available on the Internet, I came to similar realizations: the first one is that a) I need an array L and the second one that b) L\[i\] will determine the length of **a subsequence starting at i** (!). I then proceeded with implementing the solution which turned out to be working (see below). The solution is equivalent to the most popular one, though this core assumption is directly opposite. When I read the popular solution, I began wondering, why didn't I think of this (i.e. L\[i\] -- length of a subsequence *ending at i*)? The answer might be just random -- i.e. "why not?", but maybe there's something else to it?

While backtracking my own thought process, I realized it was just a straightforward way to think for me when I was looking at an example sequence and tried to "mentally" solve the problem -- i.e. build subsequences as I go from 0 to N. Does it just mean that for someone (or the majority) the straightforward way was to think of how (or where) the subsequence ends?

```
    int lengthOfLIS(vector<int>& sequence) {
        if (sequence.size() == 1) return 1;
        if (sequence.size() == 0) return 0;

        int maxLen = 1;
        vector<int> LIS(sequence.size(), 1); // LIS[i] -- len of subseq starting at i

        for (int i = sequence.size()-2; i >= 0; --i)
            for (int j = i+1; j < sequence.size(); ++j)
                if (sequence[i] < sequence[j])
                {
                    LIS[i] = max(1+LIS[j], LIS[i]);
                    if (LIS[i] > maxLen) maxLen = LIS[i];
                }

        return maxLen;
    }

```

# Answer
Congratulation for solving a popular problem independently with a perspective that is rarely seen.

---

The choice between "ending at $i$" and "starting at $i$" can be dismissed as insignificant, coincidental, and random. They are symmetric to each other.

A similar question could be why we read, write and think from left to right, as shown on this web page and, much more often than not, in computer science and programming. Note, however, (most?) Arabians write from right to left.

---

On the other hand, there are, indeed, a few reasons why "ending at $i$" is seen overwhelmingly more often.

* Assume we read and write from left to right.
It is more natural to consider the sequences that start at the left side first, to be extended to the right. So, we would classify them according to where they end.
* A convention across most (if not all) popular programming languages is that a dynamic array grows at the side where the index is larger.
To be consistent with that direction, we would like to classify the subsequences according to their ending indices. In the case when we grow the given array (sequence), the code we have written and the computed (intermediate) result can be reused easier.
* In general, it is more natural and common to extend subsequences (or anything) at their closing ends. "Extending the start of something" is more likely to sound weird. For example, a university can decide to extend a semester if it is about to end or even if it has ended, at which time the start of the semester cannot be extended earlier.
Programming is hard. So people make every little effort to make it human-friendly. Or friendly to more people.
> 1 votes

---
Tags: algorithms, dynamic-programming, algorithm-design
---


# Question
Title: How can I estimate Bhattacharyya parameter for BSC channel, used for Polar codes
In polar codes, the frozen bits in each message are determined through the worst channel, where the relevant parameter is the Bhattacharyya .

How can I estimate Bhattacharyya parameter for BSC channel?

# Answer
I do not think you can use formula (14) on page 5 of 'How to construct polar codes'. I think you want to compute Bhattacharyya parameters after channel polarization. Hence, you need to compute transition probabilities of synthesized channels firstly, and then compute Bhattacharyya parameters using formula (14) on page 5 of 'How to construct polar codes'. The formula of transition probabilities of synthesized channels is give by Arikan in his TIT paper, but it is not easy to implement it.
> 1 votes

# Answer
read the paper "Designs of Bhattacharyya Parameter in the Construction of Polar Codes ". your answer is there.
> -1 votes

---
Tags: information-theory, coding-theory
---


title: Order of query execution in the SQL

text:
# Question
Title: Order of query execution in the SQL
When a user writes a SQL query it needs to be scanned, parsed and validated. The question is in which order these three operations occurs in the process?

Scanning, Parsing, Validation or any other order to execute the query

Scanning refers to identifying the keywords, token, attribute names and relation names

Parsing refers to checking of the syntax whether it follows the syntax rules or not

Validation refers process of validating the names of relations and attributes.

# Answer
> 1 votes
The process of scanning is the process of "reading" the text concretizing the SQL query. Parsing is instead the process of checking that it is syntactically correct (the elements of the language are in the correct order/occurrence). Since no check can be done on something that you do not see/perceive: scanning must precede parsing, or they must at least happen simultaneously in alternation (this is what happens in parsers design through flex & bison).

Most parsers carry out semantic correctness checks during the lexing phase while the input is read.

Since I do not know what you mean by "validation", I assume it is the process of checking that the query satisfies some correctness criterion. For instance, it does not access unexisting tables. This exact task can be carried out during the lexing phase but it is not compulsory to do so.

Hope this helps.

---
Tags: database-theory
---


# Question
Title: Recurrence relation and time complexity of recursive factorial
I'm trying to find out time complexity of a recursive factorial algorithm which can be written as:

```
fact(n)
{
 if(n == 1)
 return 1;
 else
 return n*fact(n-1)
 }

```

So I write the recurrence relation as

```
T(n) = n * T(n-1)

```

Which is correct according to this post: Recurrence relation of factorial And I calculate the time complexity using substitution method as follows:

```
T(n) = n * T(n-1)  // Original recurrence relation
= n * (n-1) * T(n-2)
...
= n * (n-1) * ... * 1
= n!

```

But according to this post, here, both recurrence relation and time complexity are incorrect. What am I doing wrong or not getting correctly?

# Answer
Your understanding of how recursive code maps to a recurrence is flawed, and hence the recurrence you've written is "the cost of T(n) is n lots of T(n-1)", which clearly isn't the case in the recursion. There's a single recursive call, and a multiplication of the result.

Assuming the numbers aren't large, the multiplication is constant time, and it's a single operation, not a multiplier on the number of recursive calls:

$$ T(n) = T(n-1) + c\_{1} $$

The base case is $T(1) = c\_{2}$

If we simplify things further, and assume $c\_{1} = c\_{2} = 1$ (it makes no difference to the final asymptotic analysis anyway), you get:

$$ T(n) = T(n-1) + 1 = T(n-2) + 1 + 1 = T(n-2) + 2 ... $$

And the same final result as the StackOverflow question of $T(n) = n$.
> 3 votes

# Answer
Note that $$T(n) = n * T(n-1)$$ compute $n!$ in recursive manner, is differ from running time of your algorithm, hence $T(n)$ is recursive formula for compute $n!$.

If $f(n)$ be the time complexity of your algorithm, so

$$f(n)=f(n-1)+O(1).$$

Note that, if we change your recursive code as follow:

```
 fact(n)
    {
     if(n == 1)
     return 1;
     else
     for i=0 to n
     x=x+n*fact(n-1);
     return x;
     }

```

then $f(n)$ will be

$$f(n)=nf(n-1)+O(1).$$
> 0 votes

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Prove that the following algorithm for division and remainders of natural numbers is correct
I am currently brand new to the correctness proof method, and have stumbled upon this algorithm which I find very tricky.

> Prove that the following algorithm for division and remainders of natural numbers is correct.
> **function** divide(y,z)
> **comment** Return $q,r \in \mathbb{N}$ such that $y=qz+r$ and $r\<z$, where $y,z \in \mathbb{N}$
> $r:=y; q:=0; w:=z;$
> **while** $w \leq y$ **do** $w:=2w$
> **while** $w\>z$ **do**
> $q:=2q; w:=\lfloor w/2\rfloor;$
> **if** $w \leq r$ **then**
> $r:=r-w; \space q=q+1;$
> **return**(q,r)

The loop loop which I got for the following algorithm is $q\_j w\_j + r\_j = y\_0$ and $r\_j \< w\_j$. And this is what I got so far.

In each iteration we calculate the following variables:

> $w\_{j+1} = \lfloor w\_j / 2 \rfloor$, $q\_{j+1}=2q\_j$
> $r\_{j+1}=r\_j-w\_{j+1}$, $q\_{j+1}=q\_{j+1}+1=2q\_{j}+1$ if $w\_{j+1} \leq r\_j$

To prove the loop invariant, I used mathematical induction.
Assume that it holds for some $j$, and let's prove that the loop invariant holds for $j+1$. First I tried proving that in $j+1$. iteration the if statement hold ($w\_{j+1} \leq r\_j$).

> $q\_{j+1}w\_{j+1}+r\_{j+1}=y\_0$ and $r\_{j+1} \< w\_{j+1}$
> $(2q\_j+1) \lfloor w\_j/2 \rfloor + r\_j-\lfloor w\_j/2 \rfloor =y\_0$ and $r\_j-\lfloor w\_j/2 \rfloor \< \lfloor w\_j/2 \rfloor$
> $2q\_j \lfloor w\_j/2 \rfloor + q\_j(w\_j\space mod\space 2)-q\_j(w\_j\space mod\space 2)+r\_j=y\_0$ and $r\_j \< 2 \lfloor w\_j/2 \rfloor$
> $q\_jw\_j-q\_j(w\_j\space mod\space 2)+r\_j=y\_0$ and $r\_j\<w\_j-(w\_j \space mod \space 2)$

And then I stated that $(w\_j\space mod\space 2) = 0$ in order for the inductive hypothesis to hold. And I got:

> $q\_jw\_j+r\_j=y\_0$ and $r\_j\<w\_j$

This is the first induction which I proved, the second would be if $w\_{j+1} \> r\_j$.
My question is any of this which I wrote correct, or is there another way to prove the loop invariant. Any type of advice is helpful.

# Answer
A very simple loop invariant: w = z \*2^k, and q and r are the correct result for division by w instead of division by z. k=0 proves the theorem.
> 0 votes

---
Tags: algorithms, algorithm-analysis, correctness-proof, program-correctness
---


# Question
Title: What is the meaning of this symbol that looks like an inverted uppercase A?
I found this symbol in a book I'm reading. Does anyone know what this symbol means? Does it mean for all js?

# Answer
It's universal quantifier that interpreted as "given any" or "for all". you can check definition of quantifiers.
> 5 votes

---
Tags: algorithms, discrete-mathematics, notation
---


# Question
Title: Is there one (or a few) canonical/ specific use cases for "functions returning functions" (beyond "decorators")?
1. Is there one (or a few) canonical/ specific use cases for "functions returning functions" (beyond "decorators")?
2. What can you do with "functions returning functions" that you cannot (easily or elegantly or expressively) do with functions as variables ("functions taking functions as their arguments") and/or composing functions, as in :`(f(g(x))`.

# Answer
A common reason to return a function is when programming with *iterators*. Specifically, when you have a data structure (such as a list or set) and you want to return an iterator over it.

In a pure functional style, an iterator is an initial state `init: S` together with a function

```
next: S -> Option<(A, S)>

```

where S is the state of the iterator and A is the output type of the iterator. It takes in a current state and returns either None or a value and a new state.

So, if you want to define an iterator over a list, you need to write a function

```
iterate_over_list: List A -> (S, S -> Option<(A, S)>)

```

where `S` is defined appropriately -- depending on your implementation it could either be `(List A, int)` (the list together with an index into it) or just `List A` if you consume the list while iterating over it.

There's no way to avoid returning a function here because an iterator is something that you call repeatedly (every time you want a new element, you ask the iterator to generate a new element).

---

To give an even simpler example along the same lines, sometimes you want an iterator over all integers starting at a given integer. Then you would write a function

```
iterate_starting_from: int -> (S, S -> Option<(int, S)>)

```

where `S` in this case would just be `int` (the state of the iterator is the current integer to be returned). The implementation of this is something like (in pseudocode):

```
iterate_starting_from(i):
    let init = i
    let next = lambda x: Some((x, x+1))
    return (init, next)

```
> 5 votes

# Answer
Here is my opinion on the matter:

Take for example, the derivative operator. For clarity, we will denote by $der(f)$ the derivative of $f$ (which is usually written as $f'$).

The derivative function $der$, takes as an input a deriviable function $f$, and returns a different function which is its derivative: $der(f)$.

In a similar way, an integral is a function of functions. Also function composition can be thought of as a function $compose(f,g)=f\circ g$.

Essentially, the main "basic" use of such functions allow us to create certain "traits" or "behaviours" of "regular" functions, that we can define to all functions simultaneously.

That being said, there are more complex and interesting examples, such as linear transfomations in the dual vector space, or other things similar to it - which are much more complex and are useful for other things as well.
> 1 votes

---
Tags: functional-programming, design-patterns
---


# Question
Title: Having a set of non unique Key-Value pairs, how can I optimally find a lowest sum subset if distinct keys?
I understand that the title might be confusing so I'll lead with an example.

I have the following set (actually a map):

```
{
  "ab": 2,
  "ac": 1,
  "ad": 3,
  "ae": 4,
  "abc": 6,
  "b": 2,
  "ba": 4,
  "bc": 4,
  "bd": 3,
  "bde": 4,
  "c": 2,
  "cb": 3,
  "cde": 5,
  "d": 4,
  "e": 4
}

```

I want to find a subset of entries whose keys *uniquely* cover $a,b,c,d,e$ **and** with the minimum sum of the values of the selected entries. *Uniquely* means that each letter in the key should appear in **only one selected entry**.

Some valid subsets:

```
["ab","cde"] -> 7
["ac","bde"] -> 5
["ad","cb","e"] -> 10
["ba","cde"] -> 9
["abc","d","e"] -> 14

```

Some invalid subsets:

```
["ab","ba","cde"]
["ad","bde"]
["abc","cde"]

```

Desired subset:

```
["ac","bde"] -> 5

```

I know I can iterate through the list in nested loops but the complexity becomes $O(n^c)$ where $n$ the total amount of entries and $c$ the amount of entries in the subset (e.g. 2 or 3). For my use case I might have $n=300, c=10$ which becomes prohibitive, even if polynomial (c is a predetermined constant).

Is this a type of problem that can be reduced to a known problem? Do optimizations exist? It is **not** mandatory to select the entries with the minimum value, low value combinations in general are acceptable to me. In the example above, I'd be ok with the entries with sum 5 or 7.

# Answer
> 2 votes
If $s$ is part of the input then it is NP-hard even to just decide whether a feasible solution exists since this is the Exact Cover problem.

You can design an algorithm having time complexity $O(n m 2^\frac{n}{2} )$ by using the split and list technique, where $m$ is the size of the universe.

The idea is as follows:

* Partiion the $n$ possible keys into two sets $A,B$ of roughly $n/2$ keys each.
* Generate all $O(2^{n/2})$ subsets of $B$ and, for each subset $X$ that covers each element at most once, compute a pair $(1\_X, w\_X)$ where $1\_X$ is the characteristic vector of the elements covered by $X$ (w.r.t. the universe) and $w\_B$ is the sum of the values of the keys in $X$.
* Collected the pairs generated from $B$ into an array $L$ and sort $L$ (in lexicographic order) in time $O(m |B| \log |B|) = O(n m 2^\frac{n}{2})$.
* Generate all $O(2^{n/2})$ subsets of $A$ and, for each subset $X$ that covers each element at most once, consider the complement $\overline{1}\_X$ of its characteristic vector $1\_X$ and its "cost" $w\_X$. Binary search $L$ for the pair $(\overline{1}\_X, w)$ minimizing $w$ (if any). This requires time $O(m \log |B|) = O(m n)$. If such a pair exists, the keys in $X$ and in the set that generated $(\overline{1}\_X, w)$ form a candidate solution of overall cost $w\_X + w$.
* Return the candidate solution of minimum cost.

# Answer
> 0 votes
Given your constraints it looks like a typical "bitmask" problem. We can model sets with small sizes such as 10 bits simply as int32. If the int32 $s$ represents a set we say:

* $s$ contains $i$ if the $i$-th bit of $s$ is $1$ (`s & (i << 1) > 0`)
* $s$ is empty if $s = 0$
* $a$ is a subset of $s$ if `a & s == a`
* union of $b$ and $s$ is `b | s`

Let $n,c$ be as defined in your task. Using this you could write the following algorithm:

```
dp := integer array of length 2^c initialized to -1
dp[0] = 0
for i = 0...n-1:
    key,val := the i-th key value pair
    s = 0
    for char in key:
        s = s | (1 << char2num(char))
    if dp[s] == -1: dp[s] = val
    dp[s] = min(dp[s], val)
    for j = 0...2^c-1:     #iterate through all bitsets
        union = s | j      #union of two bitsets through OR
        if dp[j] == -1:
            continue
        if dp[union] == -1:
            dp[union] = dp[j] + dp[s]
        dp[union] = min(dp[union], dp[j] + dp[s])
answer is dp[2^c-1]

```

`char2num` is just supposed to translate "a" to $0$ "b" to $1$ and so on. The whole "trick" is to use a dp-array over all sets and use the sets as indices. Furthermore since we use int32, union just becomes an OR operation.

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


# Question
Title: Query regarding Length of an Input and Time Complexity of algorithms
What is actually meant when we say 'size/length of an input'? As far as I have interpreted it in different books,it means the values of the parameters to be inputted in an algorithm. But I am actually confused of what it really is. And further they state that time complexity of algorithms is usually a function of the size of the input. For instance,if I take the problem of multiplication of square matrix of order $p$ by itself, then is $p$ the size of the input? If so then,the time complexity does depend on it. Is my interpretation correct?

# Answer
The input size, is roughly measured by "how many values do we store here?", and if you want to be more specific, you will also include "how much data (in terms of bits) do the values take?".

In the matrix case, if the matrix is of order $p\times p$, then it has $p^2$ elements in it. Hence, its "size" will be said to be $O(p^2)$.

When talking in formal terms for turing machines, the input is simply a string. This string can *encode* matrices, or anything else you want - but it still will always be a string. Think of how you write a vector: as a combination of letters, brackets and numbers - its a string! Strings are nice: the input size is defined to be the number of "letters" in the string. For example, the binary string "1101" will have size $4$, while the binary string "010101" will have size $6$.
> 1 votes

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


title: Sorting by tournament sort

text:
# Question
Title: Sorting by tournament sort
Is there somewhere a website/application/software/something where you can submit a list of string/image/audio/content/whatever and the appliance make a tournament sort by asking you question like "Do you prefer \[Element K\] or \[Element J\] or you don't know?". And depending on the replies he ask smartly for the other elements of the list and when he has enough replies, he return a sorted list of our string/image/audio/content/whatever preferences? (ex-aequo can be possible considering the "you don't know" choice)

It's not a software creation asking, it's a "simple thing" that I guess it exists over internet, but I don't know what terms to search for that

# Answer
> 1 votes
This might be helpful. There might be other websites too.

---
Tags: sorting
---


# Question
Title: Mechanically proving element non-membership
I'm facing a (possibly simple) problem while proving a theorem.

I need to show that under several (true) assumptions, some element is not in a set. Such assumptions are all met and there is are lemmata that can be employed to reach the conclusion. The problem comes from the fact that the lemma for doing so must be applied an arbitrary number of times.

Lemma 1: $\forall x:\big(x\in X \iff P(x) \big)$

Lemma 2: $\forall x,y : (P(x) \land Q(y) \land x\neq y) \Rightarrow qq \neq x $

Lemma 3: $\forall x : P(x) \Rightarrow Q(x)$

Assumption: $\vert X\vert=k \land k\ge 2 %\big(\forall x\in X.P(x)\big)$

Desired result: $qq\not\in X$

**What i tried so far:**

*Proof:* Intuitively, it is easy to see that $qq\not\in X$ because I can choose two elements $a$ and $b$ of $X$ (they are distinct by definition), plug them in lemma 2, and get that $qq\neq a$. If we apply this idea $k$ times we get that $qq$ is not an element of $X$, hence it is not in $X$. $\Box$

When $k=2$ or bounded, this reasoning works.

**The problem:** $k$ is not known in advance and I can not mechanically apply Lemma 2 arbitrarily many times.

How can I prove this intuitive fact in a mechanical fashion? I've been (vaguely) suggested to employ a bijection but i still don't see how to do so.

# Answer
I eventually proved the theorem in a mechanical fashion and I want to thank j\_random\_hacker for pointing out a proof sketch based on induction and correcting my wrong initial formal statement.

The actual (mechanical) solution did require the employment of an inductive predicate that allows the human prover to instantiate the inductive hypothesis to a set $X'$.

The employment of natural induction in a mechanized fashion seems to be insufficient for carrying out the proof. This specific problem is discussed further here: Induction examples in PVS, slide 23/61. A different solution suggested there is subtyping.
> 0 votes

---
Tags: correctness-proof, first-order-logic, proof-assistants
---


# Question
Title: Halting Problem - Arguments to Halting Checker Function
I'm trying to understand the Halting Problem. All the explanations I've seen state that the problem arises when passing a program to a halting check function along with itself as input. For example `if halts(program, program)` in the code below (please let me know if my code does not accurately represent the halting problem).

One thing that is confusing me is why we need to stipulate that the program is passed to the harting checker along with itself as input.

If, for example, we had `if halts(program, "foo")`, would the paradox no longer occur?

def halts(program, input_data):
    """
    Hypothetical function.
    Returns True if program would halt when run with input_data
    as its input, else False.
    """

    return program_halts

def will_i_halt(program):
    if halts(program, program):
        while True:
            print("INFINITE LOOP")
    else:
        print("HALT")

will_i_halt(will_i_halt)
```

# Answer
> 2 votes
I can write a program "halts" which will often return the correct result, will never return the wrong result, and will sometimes not halt.

For example, programs without loops and recursion always halt. So I can write a program "halts" that checks if another program has no loops and recursions and returns "halts" if that is the case, but if there is a loop then my program can't figure out the correct answer, so to avoid ever giving the wrong answer it just doesn't halt.

There is nothing deep or interesting in the answer so far, it is just all straightforward and obvious. I could improve the program, for example to see if the program runs into a loop from which it cannot exit and return "doesn't halt" in that case, so it might indeed work in a useful way for *many* cases.

Now the question is: Is there a program "halts" which will always return the correct result, and *never* halt? We can either write such a program and prove that is correct, or we can prove that such a program doesn't exist.

To prove that "halts" cannot exist, we could try to find inputs where a human can't figure out whether "program" halts with input "input\_data" or not. But that's problematic; the human might just not be clever enough, and a more clever human might figure out whether this program halts, or be able to write the program "halts", because they are more clever.

The other possibility is to prove "if 'halts" existed, then I could give it inputs where I can prove that it returned the wrong results".

At the moment I don't know if program "will\_i\_halt" will halt with input "will\_i\_halt". But *if* it halts, and the program "halts" is correct, then will\_i\_halt(will\_i\_halt) calls halts(will\_i\_halt, will\_i\_halt) which returns true, and then then will\_i\_halt goes into an infinite loop. So *if* it halts, "halts" cannot have returned the correct result.

If it doesn't halt, then will\_i\_halt(will\_i\_halt) calls halts(will\_i\_halt, will\_i\_halt) which returns "no" and will\_i\_halt halts. So if it doesn't halt, "halts" cannot have returned the correct result either. Since a program either halts or doesn't, we found an input where "halts" gives the wrong result. Contradiction therefore "halts" doesn't exist.

We need to call will\_i\_halt(will\_i\_halt) because doing this produces the identical call twice with different results. The results of calling will\_i\_halt(will\_i\_halt) directly and calling it indirectly by calling halts(will\_i\_halt, will\_i\_halt) are different.

If I called will\_i\_halt(foo) that would call halts(foo, foo) which would call foo(foo). Quite obvious that calling will\_i\_halt(foo) and foo(foo) should produce different results, so whatever halts(foo, foo) produces doesn't give any contradiction.

# Answer
> 1 votes
You are asking an interesting question.

For one, start by fully understanding the halting problem and the proof of its undecidability (from what it sounds you *do* understand it).

Now, you are asking what happens when we restrict ourselves to a specific input for the turing machines? The answer is quite interesting - even in this case the problem is undecidable!

The "trick" is to somehow encode *both* the turing machine *and* its input together, and pass it as the first "program" parameter. This is done as follows:

Given a TM $M$ and an input $w$, construct the new machine $M\_w$. The machine $M\_w$ will ignore its input, and will simply simulate $M$ when ran with $w$ as its input.

Now, notice that running this $M\_w$ with any input, for example even with "foo" as the input - will be equivalent to running $M$ with $w$ as its input. Hence, deciding if $M\_w$ halts when given input "foo" is equivalent to deciding whether $M$ halts on $w$ (which we know is an undecidable problem).

---
Tags: halting-problem
---


# Question
Title: Is every binary sequence the output of some meaningful-text-input algorithm?
Here is the problem: Let's say we have a random binary sequence, just an arbitrary sequence of zeroes and ones (of some arbitrary length of digits). Can we find an algorithm that would decode/decompress this sequence into a meaningful statement (say, in some natural human language)? I don't want to condition or bias on any particular human natural language, or really any other communication system (I suppose we could broaden to visual, audio, or other symbolic communication systems).

The idea is that we can take a natural language statement in text form, and then using lossless text compression, code it into a binary sequence that appears completely random. So one will see this sequence and think it is just meaningless and random, say, in the information theoretic sense. Then suppose one is presented with some other binary sequence that appears random. One might use this as an argument against the conclusion that this other binary sequence is stochastically random or lacks any meaningful information since we have an example of a sequence that appears random but in fact is actually compressed meaningful text. The idea comes from an intelligent design type argument against the idea of ever concluding something is stochastically random, i.e. that just because something appears random, one can never claim it is actually random (since some things that appear random are not). My perspective is that it is a bad argument (or even a purposefully misleading one).

Here is an attempt to put it symbolically. Suppose we have a binary sequence $\mathbf x$. Does there exist an text-to-binary algorithm $F$ and a meaningful text string $\mathbf s$ such that $\mathbf{x}=F(\mathbf{s})$.

For example, if I am presented with an arbitrary sequence such as:

$$0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 1 1$$

can I find an algorithm that this exact sequence is the result when the input string is

$$\text{''Apples grow on trees.'' } $$

or any other arbitrary but meaningful text statement?

Of course, maybe other algorithms decode the binary sequence to different text strings, but that is fine. My point is that even if we have a random binary sequence, generated by, say, coin flips or radioactive decays, then we can always find an algorithm that would encode meaningful text as that particular random sequence. I am hoping to avoid trivialities, e.g. a tailor-made algorithm that converts a pre-specified text string to the the specific sequence under question. I am hoping that the algorithm will be a general-purpose text compressing/encoding algorithm that can act on any text string from the given natural language.

I hope this question is understandable. I don't quite have a sophisticated enough understanding of information and computational theory to formulate it more clearly. Feel free to be as theoretical as desired in any comments, questions, or answers though.

# Answer
> 3 votes
The answer is Yes, such an algorithm exists. Suppose $x=00100100001111011110110110001011$ and $s=$"Apples grow on trees". There here is an algorithm $F$ that meets your requirement:

function $F(t)$:

* If $t=$"Apples grow on trees", then return $00100100001111011110110110001011$.
* Otherwise, do anything you want. (e.g., return the gzip compression of $t$)

If you additionally want $F$ to be bijective, that takes a little extra work, but that can also be arranged.

This is a rather trivial solution, so while this meets all your requirements, I suspect perhaps your requirements didn't accurately capture what you actually wanted to know.

# Answer
> 2 votes
We could actually speak of a compression algorithm.

Some compression schemes use prefix codes, which relies on how often a particular symbol appears, which is referred to as the frequency. The basic idea is that the symbols that appear most often are re-expressed as the smallest possible symbols. We call the output symbols code words.

For example, in your string "Apples grow on trees", the character "e" appears most often at 3 times, so we want to re-express this as small as possible. We will rewrite your entire string, and write the single bit "0" every time the character "e" appears in the string. Then, the four characters "p", "s", "r", and "o" each appear 2 times. So again, we will re-express them as new codes, and as small as possible. "0" has already been taken, so re-express them as "1000","1001","1010", and "1011". Then express the remaining characters as larger strings.

This is still pretty small for characters, and obeys the prefix code idea, which states that no code word, for example the bit "0", is a prefix of any other code word.

Using a system like this will ensure that basically any string will have a specific interpretation.

# Answer
> 0 votes
My 2 cents...

Can there be , Yes. But it kind depends on your depends definition of "meaningful-text-input"

Right now.. I would say not yet. A compression algorithm generates binary data, and each algorithm can generate different binary data.

but just given random pattern, not that I have found exactly. Well, until you explore writing the algorithm.

You have the trivial substitution, example from D.W. And a slight extension with a database to look up pattern replacements, a dictionary. This can get rather large quickly.

Off the top of my head... one method is using a Markov Chain. I can imagine using the binary input to walk a Windowed Markov Chain of words/letter/patterns to build the output text.

There are a few Markov chain programs out here that you could modify. a quick search you can find code to play with, even JavaScript.

This Markov Chain data can be built up by processing a set of text files into a database/dictionary

I assume you are receiving this pattern to be decoded, so long as both sides have the same built dictionary, any pattern can be decoded and output the same text for the same input. And many(not all) text can be encoded into a binary pattern, provided that all parts of the input text can be found in the Markov chain dictionary.

---
Tags: information-theory, randomness, data-compression
---


title: Fractional Knapsack in linear time

text:
# Question
Title: Fractional Knapsack in linear time
How to solve fractional knapsack in linear time? I found this on Google but don't really understand it.

1. Choose element $r$ at random from $R$ (set of profit/weight ratios)
2. Determine
    * $R\_1 = \\{ p\_i / w\_i | p\_i / w\_i \> r, for 1 \leq i \leq n \\}, W\_1 = \sum\_{i \in R\_1} w\_i$
    * $R\_2 = \\{ p\_i / w\_i | p\_i / w\_i = r, for 1 \leq i \leq n \\}, W\_2 = \sum\_{i \in R\_3} w\_i$
    * $R\_3 = \\{ p\_i / w\_i | p\_i / w\_i \< r, for 1 \leq i \leq n \\}, W\_3 = \sum\_{i \in R\_3} w\_i$
3. if $W\_1 \> W$
    * recurse $R\_1$ and return computed solution
4. else
    * while (there's space in knapsack and $R\_2$ is not empty)
        + add items from $R\_2$
    * if (knapsack gets full)
        + return items in $R\_1$ and items just added from $R\_2$
    * else
        + reduce knapsack capacity by $W\_1 + W\_2$
        + recurse on $R\_3$ and return items in $R\_1 \cup R\_2$
        + add items returned from recursive call

I don't get how it works, what $R$ and $W$ are supposed to represent ... can someone explain? Or maybe if you have another algorithm to propose?

# Answer
> 9 votes
It would be nice if you stated the problem. I assume that you have $n$ items $x\_i$, each having profit $p\_i$ and weight $w\_i$. You want to maximize your profit under the constraint that the total weight is at most $W$. For each item $x\_i$, you are allowed to put any fraction $\theta \in \[0,1\]$ of it, which will give you profit $\theta p\_i$ and weight $\theta w\_i$.

Here is an example. You have raw gold, with a profit of $1000$ and weight $1$. You also have bananas, with a profit of $1$ and weight $10$. Suppose you can carry a weight of $2$. What would you do? Naturally, you would first put as much gold as you can - namely, all of it, and then you would put it as many bananas as you can - namely, a tenth of it, for a total profit of $1000.1$.

The general algorithm is similar. Suppose you divide $W$ into a $1000$ "slots", which you want to fill with the most profitable item-parts of weight $W/1000$. For an item weighing $w\_i$, we have $w\_i/(W/1000)$ pieces (suppose for the moment that this is an integer), and each of them is worth $p\_i/(w\_i/(W/1000))$. When choosing what to put in a slot, we would like to maximize our profit, and so we choose the item with maximal $p\_i/w\_i$, and put it as many pieces as possible. If we run out, we choose the item with the next largest $p\_i/w\_i$, and so on.

You can implement this without dividing $W$ into a $1000$ pieces: Choose the item with maximal $p\_i/w\_i$, and put as much of it as possible. If you run out, choose the next one, and put as much of it as possible. And so on. Implementing this algorithm requires sorting the list $p\_i/w\_i$, which takes time $O(n\log n)$. The algorithm you describe uses the same trick use in quickselect to reduce the running time to $O(n)$, at the cost of making the algorithm randomized.

I suggest the following route to understand the algorithm:

1. Understand the classical greedy algorithm for fractional knapsack.
2. Understand quickselect.
3. See how the algorithm you quote combines the technique of quickselect with the greedy approach.

# Answer
> 2 votes
**R** is the *set of ratios of profit/ weight of every object*, where profit and weight of objects are given. And **W** is the  **Capacity of knapsack**.
Now Instead of choosing random element at 1-step we can apply *median finding algorithm* to find median in **O(n)** times.
And then we can do rest of all steps. So the time complexity analysis will be -
T(n) = T(n/2) + O(n).
And we will get  **O(n)**  as solution. Tell me if anything is not properly explained and you wanna know something more.

# Answer
> 2 votes
In linear time, you can find the median item in terms of value per unit weight. Then, also in linear time, you can figure out if you can fit all items that are at least that valuable in the knapsack or not. If you can, then do so, and recursively solve this problem for the **n/2** items of lower value given that you've already filled the knapsack. If you can't, then you can throw out the **n/2** items of lower value, and then try to solve the problem again with only the **n/2** items of highest value.

The recurrence here is **T(n)=T(n/2)+O(n)**, and we have that **T(n)=O(n)**, as desired.

***In the solution you have pasted:*** **R** is the set of ratios, profit/weight **W** is the summation of the entire weight of this set, used to compare with the capacity of your knapsack. Similarly, {pi/wi|pi/wi} represents the ith elements profit is to the ith weight value. We are comparing this value to the randomly selected **r** value and then segregating based on the comparison of the ratio. The **R1, R2, R3** are further subsets of the ratio set depending on the ratio being less, equal or greater than that of the median element.

similarly, the **W1, W2, W3** are the summation of the weights of these sets.

Now choose the suitable solution set depending on the ratio values as explained in starting.

# Answer
> -1 votes
I tried to implement the algorithm in c++. Here is the link Fractional knapsack in linear time

---
Tags: algorithms, algorithm-analysis, greedy-algorithms
---


# Question
Title: Does the A* algorithm visit every node in an undirected graph when no path to the goal node exists?
When no path to the goalnode exists, does the A\*-Algorithm a) visit and b) expand every node in an undirected graph? I have a monotone heuristic. Thanks

# Answer
No, for example it doesn't expand nor visit the goal node or, in general, any node that does not belong to the connected component containing the starting node.
> 0 votes

---
Tags: graphs, weighted-graphs
---


# Question
Title: Can you use Dijkstra's algorithm to find the maximum cost path?
Suppose you have a DAG and the edges are positively weighted, and you want to find the maximum cost path from any node with no in degree to any node with no out degree.

Is it possible to negate all the weights and then apply Dijkstra's algorithm on the negative weights? All the paths here will have a negative weight, but in this situation, I think Dijkstra's algorithm would still work?

Alternatively, could you apply Dijkstra's algorithm to the original positive weights, but instead of a min heap you use a max heap?

# Answer
> 3 votes
No, Dijkstra's algorithm will not work. Consider the following counter-example: $V = \\{s,u,t\\}$ and $E = \\{(s,u),(u,t)(s,t)\\}$. The weights on the edges is as follows: $w(s,u) = 1$, $w(u,t) = 3$, and $w(s,t) = 2$.

Here the Dijkstra's algorithm with negative weights would give the shortest path $(s,t)$. However, the shortest path is $s$-\>$u$-\>$t$, which is the longest path in the positively weighted graph.

# Answer
> 0 votes
Note that, Dijkstra can't compute optimal shortest path when there are negative weights. So when you negate weights, the longest path will be shortest path, but Dijkstra can't find that.

---
Tags: graphs, dag, dijkstras-algorithm
---


# Question
Title: Why are lw and sw byte addressable but jump and beq word addressable?
I am refering to MIPS (32 bits).

Is there any particular reason that when loading or storing a word, we address memory in bytes, but when we jump or branch using beq we address memory in words?

Thanks!

# Answer
On MIPS, each instruction is exactly one word long, and is byte-aligned to words. Hence it makes no sense to jump to a byte address in the middle of a word, because that can't be the legal start of an instruction. Because the lower two bits of a jump address must be zero, you can describe more higher-order bits in the instruction encoding.
> 1 votes

---
Tags: mips, assembly
---


# Question
Title: Does $P=NP$ require an algorithm that uses polynomial space?
if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?

# Answer
> 2 votes
You can think about this more informally: it takes time to access memory. For any algorithm, whether a Turing machine or using some other formalism, whenever it queries or modifies memory that takes a certain amount of time. Therefore, total space used by an algorithm (units of space accessed during execution) is always **less than or equal to** the time used by the algorithm: $$ \textsf{space} \le \text{time} $$

For this reason, as nir explains, the algorithm you envision cannot exist.

# Answer
> 1 votes
Any turing machine with running time $O(T(n))$ for some function $T$, will have to use at most $O(T(n))$ cells on the tape, and hence will use at most $O(T(n))$ space.

Therefore, the answer is that such an algorithm wouldn't even exist.

---
Tags: complexity-theory, time-complexity, space-complexity, big-o-notation, p-vs-np
---