# Question
Title: Is this exponential-sized vertex cover problem in P?
> Suppose P $\neq$ NP. Prove or disprove if language is in P using a reduction or an algorithm:
>
> $$ \left\\{ \left(G = (V,E), k, 0^{2^{|V|}} \right) \mid (G,k) \in VC \right\\} $$

Suppose I have the this input $00000000$ I can construct a TM which calculates the number of vertices by applying log operation. So for this example $\log\_28 = 3$ I have a graph with 3 vertices.
For this case I need to check if $k$ applies to these vertices.
This can be done in $v\choose k$ operations. I think because it can be done in polynomial time the language is in P.

# Answer
> 1 votes
More generally, if $L \in \mathsf{TIME}(f(n))$ and $f(n)$ is a reasonable function then the following language is in $\mathsf{P}$: $$ L' = \\{ (x,0^{f(|x|)}) : x \in L \\}. $$ Indeed, given an input $(x,0^m)$, we first check that $m = 0^{f(|x|)}$ (that's why we need $f$ to be *reasonable*, an informal notion which can be formalized if need be), and then we run the algorithm for $L$ witnessing that it is in $\mathsf{TIME}(f(n))$. Since the input has length larger than $f(n)$, the latter part actually runs in linear time.

In your case, $L$ is *vertex cover*, which can be solved in time $2^n$, where $n$ is the number of vertices in the graph (in this regard, your example doesn't quite correspond to the general case above, but the idea is the same). So your $L'$ is in $\mathsf{P}$.

Note that the assumption $\mathsf{P}\neq\mathsf{NP}$ makes no difference here – you can prove that your language is in $\mathsf{P}$ unconditionally.

---

In the comments, you are worried that since vertex cover is NP-complete, you have just shown that P=NP. But your language is not vertex cover, and (assuming P≠NP), it is not NP-hard. You can reduce vertex cover to your language by sending an instance $(G,k)$ of vertex cover to an instance $(G,k,0^{2^{|V|}})$ of your problem, but this reduction doesn't run in polynomial time, since the output is exponentially long.

---
Tags: np-complete, vertex-cover
---


title: Time complexity of the immanant

text:
# Question
Title: Time complexity of the immanant
Let $A$ be an $n \times n$ matrix over some field $\mathbb{F}$. The determinant

$$ \det(A) = \sum\_{\sigma \in S\_n} \operatorname{sgn}(\sigma) A\_{1 \sigma(1)} \cdots A\_{n \sigma(n)}$$

can be evaluated in $O(n^3)$ field operations (via Gaussian elimination, say). Note that this is *much* better than naive evaluation of the polynomial above, which has $n!$ terms. On the other hand, the similar-looking permanent

$$ \operatorname{perm}(A) = \sum\_{\sigma \in S\_n} A\_{1 \sigma(1)} \cdots A\_{n \sigma(n)} $$

has no known polynomial-time evaluation algorithm: it is $\\#P$-complete even for matrices containing only zeros and ones over $\mathbb{F} = \mathbb{Q}$. The other significant difference is that the determinant is invariant under an arbitrary change of basis ($A \mapsto P A P^{-1}$ for any invertible $P$), whereas the immanant is only invariant under a permutation of basis elements ($A \mapsto P A P^{-1}$ for $P$ a permutation matrix).

There are a finite number of functions which interpolate between the determinant and the permanent. For any irreducible character $\chi \colon S\_n \to \mathbb{Z}$, we can define the *immanant* of the matrix $A$ to be $$ \operatorname{Imm}\_\chi(A) = \sum\_{\sigma \in S\_n} \chi(\sigma) A\_{1 \sigma(1)} \cdots A\_{n \sigma(n)}. $$ Then the permanent corresponds to the trivial character $\chi(\sigma) = 1$, and the determinant corresponds to the sign character $\chi(\sigma) = (-1)^k$ where $k$ is the number of inversions in $\sigma$.

> **Question:** What is known about the complexity of computing immanants? At what point do they switch over from being polynomial time to being NP-hard?

In order for this question to make sense, we need to know about what kinds of immanants arise for a given $n$, or in other words what the irreducible characters of $S\_n$ are. It turns out that the irreducible characters of $S\_n$ are in bijection with integer partitions of $n$, or in other words decreasing lists of positive integers adding to $n$. These are often also represented by their Young diagrams, for example the integer partitions of $n = 5$ are shown below:

In the standard way of associating partitions to characters, the one-row partition $(n)$ corresponds to the trivial representation (and to the permanent), while the one-column partition $(1, \ldots, 1)$ corresponds to the sign representation (and to the determinant).

There are some natural partial orders that can be put on the set of partitions of $n$, which place the one-row partition at one end of the order and the one-column partition at the other, such as the dominance order. We could perhaps fantasise that as you move up this order from the "easy" determinant to the "hard" permanent, you come across some kind of barrier where computation starts getting harder and harder.

# Answer
> 5 votes
The state of affairs as of 2013 is described in Mertens and Moore, The Complexity of the Ferminonants and Immanants of Constant Width. Let $\lambda$ be the partition corresponding to $\chi$.

* Immanants are easy if the leftmost column of $\lambda$ contains $n - O(1)$ boxes (Barvinok; Bürgisser).
* Immanants are hard if $\lambda\_i - \lambda\_{i+1} = \Omega(n^\delta)$ (Brylinsky and Brylinsky, improving on results of Hartmann and Bürgisser which applied only to hooks and rectangles).
* The problem of computing the $\lambda$-immanant given $\lambda$ is hard even if $\lambda$ is restricted to have width 2, and promised to have at least $n^\delta$ boxes in the second column (Mertens and Moore; de Rugy-Altherre).

The paper of de Rugy-Altherre is subsequent to Mertens–Moore.

# Answer
> 2 votes
Shameless self-promotion: Under standard complexity assumptions, A full complexity dichotomy for immanant families shows that immanant families (satisfying minimal computability and density requirements) are polynomial-time computable iff the involved partitions have only finitely many boxes outside of the first column.

---
Tags: complexity-theory
---


# Question
Title: Why can't we compute the lexicographically-least word of a given length on which a given TM halts?
I had this question in my exam. but my answer is wrong(I didn't receive explanations why...) $$f(\langle M\rangle,1^n)=\left \\{ \texttt{the lexicographically smallest } x\in\left \\{ 0,1 \right \\}^n \cap L(M) \texttt{ if } n\>100\texttt{ and }L(M)\cap \left \\{ 0,1 \right \\}^n \neq\varnothing \texttt{, otherwise undefined}\right \\}$$

I answered it is computable.
for input $(\langle M\rangle,1^{n})$ when $n \geq101$
I run the machine on all possible inputs in $\Sigma^{n}$ and output the first result when conditions are
met.

I was wrong and apparently the language is not computable. what did I miss?

# Answer
> 2 votes
Since for a given $n$, there are only finitely many strings in $\Sigma^n$, saying "run $M$ on all words from $\Sigma^n$" does make sense. But we need to be somewhat careful about the details here.

1. We could run $M$ on all $w \in \Sigma^\*$ in parallel. If we do that, then (assuming that $M$ halts on at least one of them, which we may do here), there is a first word for which we learn that $M$ halts on it. But "first" here refers to our particular simulation, and to how long $M$ takes on the various words. This will generally not be the lexicographically first word; so this is not doing the job.
2. We could run $M$ on the words $w \in \Sigma^\*$ in lexicographic order. But now, if $M$ doesn't halt on $0^n$, we never proceed beyond this particular simulation.

To prove that the function is indeed non-computable, mirror the proof of Rice' theorem.

# Answer
> 2 votes
Consider this version of the halting problem: given $T$, decide whether $T(\varepsilon)$ halts (where $\varepsilon$ denotes the empty string).

Let $\overline{0}$ (resp. $\overline{1}$) be the string containing $101$ zeros (resp. ones) and suppose towards a contradiction that your function is computable. Then, given $T$ you can construct a Turing machine $M\_T$ that behaves as follows on input $x$:

* If $x\neq \overline{0}$ then $M\_T(x)$ accepts;
* Otherwise $M\_T(x)$ simulates $T(\varepsilon)$, and when (if) $T(\epsilon)$ halts $M\_T(x)$ accepts.

It is easy to see that $f(\langle M\_T \rangle, \overline{1}) = \overline{0}$ if $T(\varepsilon)$ halts and $f(\langle M\_T \rangle, \overline{1}) = \underbrace{00\dots0}\_{100 \mbox{ times}}1$ if $T(\varepsilon)$ does not halt.

Since $f$ is computable by hypothesis, we can decide the halting problem by computing $f(\langle M\_T \rangle, \overline{1})$ and accepting iff $f(\langle M\_T \rangle, \overline{1}) = \overline{0}$. This is a contradiction.

---
Tags: formal-languages, turing-machines, computability
---


# Question
Title: An error on Introduction to Algorithms 3rd edition about closest pair of points
In the book Introduction to Algorithms of Cormen 3rd edition page 1041 about of Closest Pair of Point divide and conquer algorithm, Is there an error? It's said: "...Create an array Y', which is the array Y with all point **not** in the 2$\delta$-wide vertical strip removed...", it should be: "...Create an array Y', which is the array Y with all point **in** the 2$\delta$-wide vertical strip removed..."?

# Answer
> 1 votes
Just the two lines before, (or last two lines of page 1040 if you want) say the following:

> Observe that if a pair of points has distance less than $\delta$, both points of the pair must be within $\delta$ units of line $\lambda$. Thus, as Figure 33.11(a) shows, they both must reside in the 2$\delta$-wide

Meaning that if you want to be able to **combine** them after divide and conquer phases, you specifically are going to look within the 2-$\delta$ range. And this is why the first step is to remove all the points that exceed that limitation, therefore that they do not satisfy such constraint.

You want to keep only the points within that window-range.

---
Tags: algorithms
---


# Question
Title: What happens to the running time of an $O(n \ln n)$ algorithm if you double $n$?
Problem:

Suppose the running time of a certain algorithm is $O(n \ln n)$. We happens to the running time of the algorithm if $n$ doubles.

Answer:

Let $R\_1$ be the running time of the algorithm when the input is of size $n$. Let $R\_2$ be the running time of the algorithm when the input is of size $2n$. Let $R = R\_2 / R\_1$. \begin{align\*} R &= \frac{ 2n \ln (2n)}{ n \ln n } = \frac{ 2 \ln (2n)}{ \ln n } \\ R &= \frac{ 2 ( \ln(2) + \ln(n))}{ \ln n } = \frac{ 2 ( \ln(2) )}{ \ln n } + \frac{ 2 ( \ln(n))}{ \ln n }\\ R &= \frac{2 \ln(2)}{ \ln n } + 2 \\ \end{align\*} This does not seem right to me. Is it? If it is wrong, where did I go wrong?

# Answer
> 0 votes
I suggest following property: if for functions $g,f \gt 0$ we have $f \sim kg$, for some constant $k\gt 0$ i.e. $\lim\limits\_{n \to \infty}\frac{f(n)}{g(n)}=k$ and both, $g$ and $f$, have not zero as limit point, then $O(f)=O(g)$.

**Proof:**

Let's consider $\phi \in O(f)$, then we have $\phi \leqslant C f \leqslant C (k+\varepsilon)g$ for appropriate $C, \varepsilon$ and $n \gt N.$ So $O(f) \subset O(g)$. Using, that we have also $\lim\limits\_{n \to \infty}\frac{g(n)}{f(n)}=\frac{1}{k} \gt 0$, we obtain reverse including.

Based on brought property we can say, that running time $O(n \ln n)$ does not change if we double $n$: $$O(n \ln n) = O(2n \ln 2n)$$

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


# Question
Title: Minimum absolute value of subset sums of integer values
$f(x\_1,...,x\_m)=\min\_{\emptyset\subset I\subseteq\[m\] }\left|\sum\_{i\in I}x\_i\right|, x\_i\in \mathbb{Z}\setminus\\{0\\}$

How to prove $f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$?

When $\mathbf{POLY}\overset{\Delta}{=}\\{ f:\\{0,1\\}^\*\rightarrow \\{0,1, \\}^\* |$ exists polynomial TM which competes $f \\}$

# Answer
We give a Turing reduction from the $\mathrm{SubsetSum}$ problem. Suppose we are given a $\mathrm{SubsetSum}$ instance $(A, k)$ where w.l.o.g. $A$ only contains positive integers, i.e. we want to find a set $X \subseteq A$ such that $\sum\_{x \in X} x = k$ and define the set $A' = A \cup \\{- k\\}$.

We want to show that $f(A') = 0$ if and only if $(A, k) \in \mathrm{SubsetSum}$:

* Suppose that $(A, k) \in \mathrm{SubsetSum}$. Then there exists a set $X \subseteq A$ such that $\sum\_{x \in X} x = k$, i.e. the sum over the elements of $X \cup \\{-k\\} \subseteq A'$ is $0$, implying $f(A') = 0$.
* Otherwise, we have $(A, k) \notin \mathrm{SubsetSum}$. As $A$ only contains positive integers but no subset of $A$ sums to $k$ we infer that any subset of $A'$ sums to some nonzero value.

It follows that if $f$ is computable by some polynomial time DTM then $\mathrm{SubsetSum}$ can in turn be decided in polynomial time, showing that $\mathsf P = \mathsf{NP}$.
> 3 votes

---
Tags: complexity-theory, computability, np-complete, polynomial-time, subset-sum
---


# Question
Title: Create Shortest Path tree for every node after Floyd Warshall in O(nm)
Right now I am stuck with the problem, how all shortest path trees can be created in O(n\*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after execution of Floyd Warshall. We were asked to think about why this is not $O(n(n+m))$ and for which graphs we really would have to do $O(n^2)$ work and if it really is $O(n^2)$ for these graphs.

The Output should be all shortest paths trees $T\_v$ for any $v \in V$

I can clearly see running DFS on every node as start node and checking if an edge is part of the shortest path or not results in O(n(n+m)) which doesnt give the desired result.

I came up with the following ideas:

* I thought about if I can state that n \>= m/2 if we exclude all isolated nodes in $O(n)$ first, so $O(n^2) = O(nm)$ what would result in $O(nm)$ over all.
* Another possibility regarding DFS would be adding edges for other trees which hold the same edge. I came up to use a $nxm$ Matrix wheter a node was added or not and keep track of visited nodes to add edges for every node. But since I have to go through all nodes every time and check for matrix entry, which does not improve that much over all.
* I also thought about path construction using a next matrix, which can be created during floyd warshall though I have to do it for every combination of two nodes in two for loops and every one recursive call is worst case $O(n)$ which results in $O(n^3)$. It would get better only if a can skip loops and edges though I can´t see an efficient way to achieve this.

Do you see any flaws within in my statements above and might any of these possibilites leed to the disired outcome? How can it be solved?

# Answer
> 1 votes
Compute all pair to pair distances $D\[u,v\]$ for $u,v \in V$ using Floyd-Warshall.

For each vertex $s \in V$ construct a graph $H\_s$ as follows:

* For each edge $e = (u,v)$ check whether $D\[s,u\] + D\[u,v\] = D\[s,v\]$. If the answer is yes the (directed) edge $(u,v)$ belongs to at least one SPT from $s$, and you add $e$ to $H\_s$.

This requires time $O(n \cdot m)$ and each graph $H\_s$ is encoding all SPTs from $s$. To get a single SPT from $T\_s$ each $s$ compute any spanning arborescence of $H\_s$ rooted in $s$. This can be done, e.g., via a BFS.

---
Tags: algorithms, graphs, shortest-path, graph-traversal, depth-first-search
---


# Question
Title: How to analyse the time complexity of an algorithm based on the input values in addition to input size
I saw a joke on twitter today that got me thinking on how to perform a time complexity analysis of this algorithm such as you can express that the worst case is dependent on the input **value** in addition to the input size.

The joke algorithm was this *sleep sort* algorithm in javascript

```
const arr = [20, 5, 100, 1, 90, 200, 40, 29]

for(let item of input) {
   setTimeout(() => console.log(item), item)
}

```

```
// Console Output
1
5
20
29
40
90
100
200

```

If we were to describe its Time Complexity and only took into consideration the size of the input, it would be `O(n)`. But from a practical standpoint that wouldn't be really accurate as the Worst Case Time of the implementation is heavily dependent on the actual value of each array element, so is it possible to convey this in a Time Complexity Analysis notation? Is there such a thing as `O(max(n) + n)`, for example?

# Answer
Worse-case complexity gives an upper bound on the complexity of an algorithm in terms of some parameters. Often the parameter is the length of the input, either in bits or in words, but sometimes several parameters are pertinent. The standard example is graph algorithms, where complexity is often expressed in terms of both the number of vertices and the number of edges.

In your case, you can define $n$ to be the length of the input and $m$ to be the maximum value in the input, and then the worst-case complexity could be $O(n+m)$, for example.
> 0 votes

# Answer
If we analyze a Time Complexity dependent also on the values of a given input, then as you say a more defined notation would be `O(max(n))`.

Though, saying `O(max(n) + n)` in O notation means `O(max(n))`

So it will still be **accurate**, since in both outcomes the Complexity is linear in the given input.
> 0 votes

---
Tags: complexity-theory, time-complexity, algorithm-analysis
---


# Question
Title: Proving big-theta complexity with constants in $f(n)$
I am working through a problem in which I have to prove that a particular $f(n) = \Theta(g(n))$. I know that for this to be true there need to exist positive constants $c\_1$, $c\_2$, and $n\_0$ such that for all $n \geq n\_0$, $c\_1g(n)\leq f(n) \leq c\_2g(n)$. Simply put, the goal is to pick values for the constants such that the above inequality holds. As a side note, $n$ must be a positive integer, and $c\_1$ and $c\_2$ can be any positive real number, correct? I haven't been able to find clarity over that.

Now, suppose the $f(n)$ has some undefined constants $a$ and $b$, such as $f(n) = n^a + n^b$. Note that this is a throwaway example. My question is this: do we need to define $c\_1$ and $c\_2$ in terms of the constants $a$ and $b$, or do we need to pick an actual numerical value for $c\_1$ and $c\_2$, and by extension, values for $a$ and $b$? The former is much more difficult to do.

I apologize in advance for the poor formatting (I simply placed any math in italics, which I know is not correct). This is my first ever post on CS stack exchange. Also, I would like to state that there was a serious attempt at researching into the above, but I couldn't find examples of how to prove $f(n) = \Theta(g(n))$ when $f(n)$ has other constants. If anyone has resources related to this, I would be very grateful.

I would appreciate any and all help. Looking forward to potential responses.

# Answer
You can find the definitions of big O notations on Wikipedia. They agree with your definition of big $\Theta$.

As for your actual question, the answer is actually quite subtle. Sometimes it is possible to find constants $c\_1,c\_2,n\_0$ which work for all values of the parameters. For example, in your case, all $n \geq 1$ satisfy $$ 1 \cdot n^{\max(a,b)} \leq n^a + n^b \leq 2 \cdot n^{\max(a,b)}, $$ and so you can say that $n^a + n^b = \Theta(n^{\max(a,b)})$.

(As a side note, you can also say that $n^a + n^b = \Theta(n^a + n^b)$, or that $n^a + n^b = \Theta(n^a + 2n^b)$; but usually we aim at the simplest possible expression, or an expression of a particular form, say $n^\alpha \log^\beta n$.)

In other cases we are not so lucky. For example, $\log^k n = O(n)$ for all $k$, but the relevant constants depend on $k$. Sometimes this makes no difference, but in other cases it is important to know that the constants depend on $k$. When it does matter, we sometimes use the notation $O\_k(n)$ to stress that the hidden constants depend on $k$. This is not completely standard, but pretty common. When the hidden constants are independent of some parameter, we can explicitly say so – $n^a + n^b = \Theta(n^{\max(a,b)})$, where the hidden constants are independent of $a,b$.

In your case, since you are only interested in an isolated estimate, you don't care about the dependence of the hidden constants on the parameters. So for you, $\log^k n = O(n)$ holds, even though the hidden constants depend on $k$, since for any *particular* $k$ this statement holds. This is the usage in the master theorem, for example – the constants there depend on the parameters, but usually it makes no difference, because the parameters are fixed in any given application, in the vast majority of circumstances.
> 0 votes

---
Tags: algorithms, time-complexity, asymptotics, proof-techniques
---


title: pruning branch and bound

text:
# Question
Title: pruning branch and bound
I am working on a branch and bound problem and I was wondering if it is correct to prune the node with z = 21.667 and if so, how do we know that we will not get a better solution if we branch on this node?

# Answer
In branch and bound, you prune a branch if you have an upper bound on the best solution that this branch can provide, and this upper bound is smaller than your current best solution. In your case, you have no current best solution (since you haven't considered any integer solutions), and in particular, you cannot prune any branch.
> 0 votes

---
Tags: branch-and-bound
---


title: Explain the proof of allocation problem

text:
# Question
Title: Explain the proof of allocation problem
**The problem**:

> There are $N$ houses for sale. The $i$-th house costs $A\_i$ dollars to buy. You have a budget of $B$ dollars to spend.
>
> What is the maximum number of houses you can buy?

There is an intuitive way to solve this problem in a greedy way: we must at first sort the house costs and then buy houses until we are out of money and it works.

and the proof is:

> Let's prove the correctness of this greedy algorithm. Let the solution produced by the greedy algorithm be $A = \\{a\_1, a\_2, \ldots, a\_k\\}$ and an optimal solution be $O = \\{o\_1, o\_2, \ldots, o\_m\\}$.
>
> If $O$ and $A$ are the same, we are done with the proof. Let's assume that there is at least one element $o\_j$ in $O$ that is not present in $A$. Because we always take the smallest element from the original set, we know that any element that is not in $A$ is greater than or equal to any $a\_i$ in $A$. We could replace $o\_j$ with the absent element in $A$ without worsening the solution, because there will always be element in $A$ that is not in $O$. We then increased number of elements in common between $A$ and $O$, hence we can repeat this operation only finite number of times. We could repeat this process until all the elements in $O$ are elements in $A$. Therefore, $A$ is as good as any optimal solution.

I don't understand the proof and I have couple of questions:

1. What does it mean to replace $o\_j$ with an absent element in $A$?
2. Why do we need to do it?

Could you explain this proof in a simpler way with examples?

You can see this problem here.

# Answer
> 1 votes
I don't like this proof so much. Here is a different one.

We can assume without loss of generality that $A\_1 \leq \cdots \leq A\_N$. Consider an optimal solution $\\{i\_1,\ldots,i\_\ell\\}$, where $i\_1 \< \cdots \< i\_\ell$. In particular, $$ A\_{i\_1} + \cdots + A\_{i\_\ell} \leq B. $$ Intuitively, it is clear that $A\_1 + \cdots + A\_\ell \leq B$ (we will prove this formally in a moment), and so the greedy algorithm will also choose at least $\ell$ houses.

Now let us prove that $A\_1 + \cdots + A\_\ell \leq A\_{i\_1} + \cdots + A\_{i\_\ell}$.

I claim that $i\_j \geq j$. Indeed, $$ i\_j \geq 1 + i\_{j-1} \geq 2 + i\_{j-2} \geq \cdots \geq j-1 + i\_1 \geq j. $$ This implies that $A\_{i\_j} \geq A\_j$, and so $A\_{i\_1} + \cdots + A\_{i\_\ell} \geq A\_1 + \cdots + A\_\ell$.

---
Tags: correctness-proof
---


# Question
Title: Find cycles with specific weights in complete graph
(this is a cross-post from mathoverflow)

Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique identifier.
Let's say I then have an input, $c$ of three edges (e.g $c=\[4,7,6\]$). Does an algorithm exist that lets me search $G$ for instances of $c$, and returns the identifiers of the matching nodes?
The cycles it returns must be closed loops, such as $\[A, D, B, \text{(then back to A)}\]$, rather than $\[D, A, B, A\]$

Here is a poorly-drawn example: .

# Answer
> 1 votes
Welcome to CS.SE.

I propose to list all paths that correspond to the given weight sequence, and keep only the one which are cycles it needed, which is then easy.

A recursive algorithm that appends an edge with weight equal to the first one in the sequence to paths that correspond to the rest of the sequence then makes the job, right?

This leads to the following python 2.7 code, that does not make the assumption that the graph is complete. Its core is the `find` function, everything else is for playing and testing.

```
import random
random.seed()

min_weight,max_weight=1,20
c_length=30

# build the graph (complete in this case)
V = ['A','B','C','D','E']
N = {u:[v for v in V if v!=u] for u in V}
weight = {}
for (u,v) in [(u,v) for u in V for v in N[u] if u<v]:
        weight[(u,v)] = weight[(v,u)] = random.randint(min_weight,max_weight)
for (u,v) in sorted(weight):
        print u+'--'+str(weight[(u,v)])+"--"+v

# build a correct sequence of weights
c = []
u = random.choice(V)
while len(c)<c_length:
        v = random.choice(N[u])
        c.append(weight[(u,v)])
        u = v
print c

# search all paths corresponding to the weight sequence in the graph
def find(c,S):
        if len(c)==0:
                return(S)
        return set([u+r for u in S for r in find(c[1:],[v for v in N[u] if weight[(u,v)]==c[0]])])

result = find(c,V)
print result

# check results
def check(x):
        if len(x) != len(c)+1:
                return(False)
        for i in xrange(len(x)-1):
                if weight[(x[i],x[i+1])] != c[i]:
                        return(False)
        return(True)
for x in result:
        assert(check(x))

```

Is it correct? It is far from optimal, of course.

# Answer
> 1 votes
**This answers a different question: a cycle is not necessarily simple.**

You can use the following dynamic programming solution:

```
fun dfs(v, start_v, c_pos, visited_vertices):
    if c_pos = c.length then
        // Used all edges
        if v = start_v then
            // Returned to the starting vertex
            visited_vertices is the answer for the problem
    else
        if was[v, start_v, c_pos] then
            // We've already been in this state and didn't find an answer
            return
        was[v, start_v, c_pos] <- true
        for each vertex u such that d(v,u) = c[c_pos] do
            // u is a possible next vertex on the path
            dfs(u, start_v, c_pos + 1, visited_vertices + [u])

set all was[u, v, pos] to false

for each vertex v do
    dfs(v, v, 0, [v])

```

The core is the `dfs` function: we've started a path at vertex `start_v`, visited vertices `visited_vertices` and currently stay at vertex `v`. During this, we've used weights `c[0]`, ..., `c[c_pos - 1]` from the list `c`. (Note that `v`, `start_v` and `c_pos` are actually redundant since they can be recovered from `visited_vertices`, but I left them for clarity).

If `c_pos = c.length`, then we've used the entire list `c`. If we've returned to the original vertex (i.e. `v = start_v`), then we've found the required cycle.

Otherwise, the function tries to find the next edge in the path. It simply tries all next vertices `u` (such that `d(u,v)` matches the next expected length) and runs `dfs` from them. The main optimization is dynamic programming. If we've already been in some state and didn't find an answer, then we abandon the current path. Note that `visited_vertices` doesn't matter for the state (since visited vertices don't affect whether we can find the rest of the path): we only care about starting vertex, current vertex, and the number of used edges.

Therefore, the total running time is $O(n^3 \cdot c.length)$: there are $O(n^2 \cdot c.length)$ states, and for each state we need $O(n)$ time.

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


title: Proof of algorithm correctness

text:
# Question
Title: Proof of algorithm correctness
I am studying about algorithm correctness and have enctountered this problem.

```
function add(y,z)
comment Return y + z, where y,z are natural numbers
x :=0; c:=0; d:=1;
while(y>0)v(z>0)v(c>0) do
    a := y mod 2;
    b := z mod 2;
    if a XOR b XOR c then x := x+d;
    c:= (a AND b) v (b AND c) v (a AND c);
    d :=2d; y:= floor(y/2);
    z := floor(z/2);

```

The book that I'm reading says that loop invariant is $(y\_j + z\_j + c\_j)d\_j + x\_j = y\_0 + z\_0$ and I honestly can't understand the conclusion. How do you come up with this? Why is this true?

# Answer
In order to prove an algorithm correctness a loop invariant should include:

1. Initialization:It is true prior to the first iteration of the loop.
2. Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
3. Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Let's look at your invariant:

**Initialization** then is before entering the loop, so choose any number for $y$ or $z$ such that $y,z \in N$ (I'll use $n\_1$ and $n\_2$ respectively) then you will have that your property is satisfied since at this point: $d=1$, $c=0$ and $x=0$. So your invariant will be: $(n\_1 + n\_2 + 0)\*1 + 0 = n\_1 + n\_2$.

**Maintenance**: This one you can prove it with induction. Here a complete example with induction. Is slightly more complicated, but you can see in your case that it holds, since at every iteration you "divide" $y$ and $z$ by 2, but $d$ duplicates every time, therefore balancing the division. The $c$ is there in case of odd numbers.

**Loop termination**: at this point according to the while, nor $y$ nor $z$ nor $c$ can be higher than $0$, but at the same time they are all natural numbers, therefore they are all $0$. Now we have that $x = y+z$ and if you plug it into the invariant you have: $(0 + 0 + 0)\*d + x = y\_0 +z\_0 \Rightarrow y + z = y\_0 + z\_0$
> 2 votes

---
Tags: algorithms, correctness-proof, loop-invariants
---


# Question
Title: How does a transition function behave in a FSM when an input is not recognized (i.e. the input is not contained in the alphabet)?
In Sipser's *Introduction to the Theory of Computation*, the provided proof for the union operation being closed for regular languages has a step for the transition function that I find a bit lacking.

Assuming that $M\_1=(Q\_1, \Sigma, \delta\_1, q\_1, F\_1)$ and $M\_2=(Q\_2, \Sigma, \delta\_2, q\_2, F\_2)$ are two different FSMs for languages $L\_1$ and $L\_2$. With $M=(Q, \Sigma, \delta, q\_0, F)$ being the FSM for $L = L\_1 \cup L\_2$ (the regular languages for the FSMs). The step for the constructed transition function, $\delta$, states that for each $(r\_1,r\_2) \in Q$ and each $a \in \Sigma$, let $\delta((r\_1,r\_2),a)=(\delta\_1(r\_1,a),\delta\_2(r\_2,a))$. This is working with the assumption that the input alphabet, $\Sigma$, is the same for $M\_1$ and $M\_2$.

I am confused on how $\delta((r\_1,r\_2),a)=(\delta\_1(r\_1,a),\delta\_2(r\_2,a))$ behaves for a combined alphabet $\Sigma = \Sigma\_1 \cup \Sigma\_2$, specifically if $a \in \Sigma\_1$ and $a \notin \Sigma\_2$? What would the output of $\delta\_2(r\_2,a)$ be and how would this transition work in the FSMs $M\_2$ and $M$?

# Answer
In my copy of the book, third edition, this is Theorem 1.25. From its proof, I quote:

> The theorem remains true if they have different alphabets, $\Sigma\_1$ and $\Sigma\_2$. We would then modify the proof to let $\Sigma = \Sigma\_1\cup \Sigma\_2$.

What is suggested here is that in advance we assume the two alphabets to be equal, i.e., before we start the product construction. So we have to transform the original automaton $M\_1$ with alphabet $\Sigma\_1$ into an equivalent automaton $M\_1'$ with alphabet $\Sigma\_1\cup \Sigma\_2$ accepting the same language. As you observe automata here are deterministic, i.e., have a transition function $\delta:Q\times \Sigma\to Q$.

The easiest way for the construction of $M\_1'$ is extending the transition function for letters outside $\Sigma\_1$. Any such letter should lead to not accepted computations. This can be done by adding a new garbage (or failure state) where all letters from $\Sigma\_2\setminus \Sigma\_1$ are mapped to.
> 2 votes

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


# Question
Title: Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$
Prove by induction that $T(n)=\Theta(n^2 \log\_{3}n)$ where $$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$

The base case for $n=1$ seems to work, but I am unable to do the induction step.

# Answer
W.l.o.g. suppose $n = 3^k$: The expand the second part of the function:

$$ T(n) = 9 T(\frac{n}{3}) + n^2 = 9 (9T(\frac{n}{3^2}) + (\frac{n}{3})^2) + n^2 = 9^2 T(\frac{n}{3^2}) + 9(\frac{n}{3})^2 + n^2 = $$ $$ 9^3 T(\frac{n}{3^3}) + 9^2 (\frac{n}{3^2})^2 + 9(\frac{n}{3})^2 + n^2 $$

You can continue it by induction to obtain the following:

$$ T(n) = 9^k T(\frac{n}{3^k}) + 9^{k-1}(\frac{n}{3^{k-1}})^2 + \cdots + 9(\frac{n}{3})^2 + n^2 $$

As $n = 3^k$, $T(\frac{n}{3^k}) = T(1) = 1$. Hence,

$$ T(n) = \sum\_{i=0}^k9^i(\frac{n}{3^i})^2 = \sum\_{i=0}^k9^i\frac{n^2}{9^i} = \sum\_{i=0}^kn^2 = n^2 \times k $$

We know that $k = \log\_3(n)$. Therefore:

$$ T(n) = n^2 \log\_3(n). $$ and we can say $T(n) = \Theta(n^2 \log(n))$ asymptotically.
> 1 votes

# Answer
Let $n = 3^{k}$ to obtain $T(3^{k}) = 9T(3^{k-1}) + 9^{k}$. This can be written $t\_{k} - 9t\_{k-1} = 9^{k}$. The characteristic equation is $(x-9)^{2} = 0$. Hence $t\_{k} = c\_{1}9^{k} + c\_{2}k9^{k}$. Putting $n$ back instead of $k$, we find $T(n) = c\_{1}n^{2} + c\_{2}n^{2}\log\_{3}n$. $T(n)$ is therefore $\Theta(n^{2}\log\_{3}n)$.
> 1 votes

---
Tags: time-complexity, runtime-analysis, recurrence-relation, recursion, induction
---


# Question
Title: Partitioning list into two parts of almost equal sum
I was given this problem in class, and I have no idea how to solve it. The problem is:

> "Given a list of positive integers, divide the numbers into 2 groups such that the difference between the sum of each group is minimal, print that difference. The algorithm must be efficient."

I guess by efficient they mean do not just brute force every option, any ideas?

I tried summing all the numbers and dividing by 2, then the problem is equivalent to finding a group that is the closest to that number, also now you can go over all the options but once you get to a point where you can only add numbers but your above that number you can stop.

# Answer
> 3 votes
As Yuval Filmus points out, this is an optimization version of the PARTITION problem. The problem is weakly NP-complete, so any polynomial time solution to your problem would immediately solve partition (simply check if the minimum difference between the sums of the two sets is $0$).

You can solve the problem in pseudo-polynomial time $O(nS)$, where $S$ the sum of the input integers, using dynamic programming, or in time $O(n \cdot 2^{n/2})$ using the split-and-list technique. Pick the best of the two algorithms depending on the value of $S$.

The dynamic programming algorithm is as follows. Let $A = \\{a\_1, \dots, a\_n\\}$ be the input (multi-)set of numbers, and let $S=\sum\_{a \in A} a$. Consider a partition of $A$ into two sets $B$ and $C$, and assume w.l.o.g. that $\sum\_{b \in B} b \le \sum\_{c \in C} c$ (since otherwise you can swap $B$ and $C$). The cost (to minimize) of this partition is: $$ \sum\_{c \in C} c - \sum\_{b \in B} b = \left(S- \sum\_{b \in B} b\right) - \sum\_{b \in B} b = S - 2 \sum\_{b \in B} b. $$

Showing that the problem is equivalent to finding a subset $B$ of $A$ whose sum of elements is at most $\lfloor S/2 \rfloor$ and, subject to this constraint, it is maximized.

For $i=0, \dots, n$, and $x=1,\dots,\lfloor S/2 \rfloor$, let $OPT\[i,x\]$ be true if and only if there exists a subset $B$ of $\\{a\_1, \dots, a\_i\\}$ with $\sum\_{b \in B} b = x$.

Then $OPT\[0,0\]=\top$ and, for $x\>0$, $OPT\[0,x\]=\bot$.

If $i\>0$: $$ OPT\[i,x\] = \begin{cases} OPT\[i-1,x\] \vee OPT\[i-1,x-a\_i\] & \mbox{if $a\_i \le x$} \\ OPT\[i-1,x\] & \mbox{otherwise} \end{cases}. $$

There are $O(nS)$ values $OPT\[i,x\]$ and each of them can be computed in constant time (in increasing order of $i$). The maximum value of $\sum\_{b \in B} b$ is $\max \left\\{ x \in \\{0, \dots, \lfloor S/2 \rfloor \\} \mid OPT\[n, x\] = \top \right\\}$.

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


# Question
Title: Constant terms at each level of a recursion tree
In CLRS, exercise 4.4-5 the following question is asked:

> Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$

In my recursion tree, the sum of level 0 is $$n$$ level 1 is $$(3/2)n - 2/2^1$$ level 2 $$(3/2)^2n-14/2^2$$ level 3 is $$(3/2)^3n - 74/2^3$$ and so on. My issues is that the rule governing the constants 2, 14, 74 etc. is difficult to express as a function of the level so that I can create a sum for all levels of the tree.

Would it be correct to say that the cost at each level of the tree is $$(3/2)^in - O(1)$$ and thus avoid the problem of having to sum all of the constant terms via big O notation, or is this approach incorrect? If so, why and what should I do instead?

# Answer
> 0 votes
For each specific level $i$, it is true that the cost is $(3/2)^i n - O(1)$. However it would be misleading to state this in general. Suppose for example that the cost at level $i$ were $(3/2)^i n + 2^{2^i}$, and that there were $\log n$ levels. The dominant factor in the total cost would be the "constant" term.

However, in your case, you can say that the cost at level $i$ is *at most* $(3/2)^i$, which gives you the required upper bound.

# Answer
> 0 votes
Regarding the recurrence itself. First, for concreteness, let us define $T(0) = 0$ and for $n \> 0$, $$ T(n) = T(n-1) + T(\lfloor n/2 \rfloor) + n. $$ Let $S(n) = T(n) + 2n$. Then $$ S(n) = T(n) + 2n = T(n-1) + T(\lfloor n/2 \rfloor) + 3n = S(n-1) + S(\lfloor n/2 \rfloor) + n+1 - 2\lfloor n/2 \rfloor,$$ and $S(0) = 0$. Note that $n+1-2\lfloor n/2 \rfloor \in \\{1,2\\}$. Therefore if we define a $R(0) = 0$ and $$ R(n) = R(n-1) + R(\lfloor n/2 \rfloor) + 1 $$ then $S(n) = \Theta(R(n))$ and so $T(n) = \Theta(R(n)) - 2n$.

Now let $U(n) = R(n) + 1$. Then $U(0) = 1$ and $$U(n) = U(n-1) + U(\lfloor n/2 \rfloor).$$ Thus $U(n)$ is the number of ways to reach $0$ using two operations: subtract $1$ and right shift by $1$. Also, $R(n) = U(n) - 1$, and so $T(n) = \Theta(U(n)) - 2n$, which is going to equal $\Theta(U(n))$.

The sequence $U$ is also known as A000123, where other interpretations are given. The asymptotics of the sequence are known to be $n^{\Theta(\log n)}$. More accurate answers can be found on the OEIS references.

---
Tags: asymptotics, proof-techniques, recurrence-relation, recursion
---


title: Explanation of roofline model

text:
# Question
Title: Explanation of roofline model
I am currently studying the roofline model. Wikipedia \[2\] shows the following example graph:

The diagonal line shows $\beta * I$. But I do not understand why this line does not go through the zero point. If $I = 0$ so should $\beta * I = 0$. What am I misunderstanding here?

\[2\] https://en.wikipedia.org/wiki/Roofline\_model

# Answer
> 1 votes
The axes are in logarithmic scale, and so don't really have a zero point. What you are seeing is $$ \log P = \min(\log I + \log \beta, \log \pi). $$ The striking part is that the *slope* of the line is always the same.

---
Tags: computation-models, modelling, high-performance-computing
---


# Question
Title: How to minimize this DFA using given algorithm?
I am trying to use Myhill-Nerode theorem to minimize the DFA appearing below.

The algorithm repeatedly runs the following step:

> If there is an unmarked pair $(Q\_i, Q\_j)$, mark it if the pair $\\{δ (Q\_i, A), δ (Q\_j, A)\\}$ is marked for some input letter.

Initially only $\\{0,3\\},\\{1,3\\},\\{2,3\\}$ are marked. However, $\\{0,1\\}$ or $\\{0,2\\}$ won't be marked since the don't have common edges, $\\{1,3\\},\\{1,2\\}$ or $\\{2,3\\}$ only goes to state 3 with edge 3, but there is no such pair $\\{3,3\\}$. Then it seems no minimization can be done.

The minimized DFA, however, should merge states 1 and 2.

# Answer
> 2 votes
The difficulty with the problem is, as Dean Gurvitz hinted and as you have experienced, not all transitions are specified explicitly. For example, given input 3 at state 0, what is the transition? According to the definition of DFA, every transition for any input symbol at any state must be specified.

You will ask then, why do I see such a graph for a DFA? What you see is a DFA specified as **an incomplete DFA**.

> some authors use deterministic finite automaton for a slightly different notion: an automaton that defines at most one transition for each state and each input symbol; the transition function is allowed to be partial. When no transition is defined, such an automaton halts.

To apply your procedure to minimize a DFA, you have to convert an incomplete DFA to a (complete) DFA. **Add another state $R$, the rejected state. Whenever a transition from some state given some symbol is not specified, add a transition from that state given that symbol that goes to $R$.** In particular, all transitions that start from $R$ go to $R$. Now that a (complete) DFA if formed, you can compute merrily with your procedure, treating $R$ just as any other non-final state. Once you are done with your procedure, you will have a (complete) DFA with minimal states. If preferred or necessary, you can convert the minimal (complete) DFA to an incomplete DFA by removing the (new) rejected state, i.e., the state that comes from $R$, and all transitions from or to that state.

# Answer
> 1 votes
This is a late answer, but I will put a practical twist on the issue.

John L. provides the accepted and formal way of dealing with it. However, from my experience in the industry, instead of halting the machine, it can be treated as self loop.

If it is not mentioned explicitly how to deal with it, go with the accepted answer.

Otherwise, as long as you clearly indicate how unspecified transitions are handled, you can imply things like a reset to initial state, halt state, self loops, some other state...

That will give you different end result, but it will basically completely specify your model.

---
Tags: finite-automata
---


# Question
Title: Is the chalk really needed in the "chalk and string labyrinth" analogy for depth-first search?
I came across the chalk-and-string labyrinth analogy for depth-first search in *Algorithms* by Dasgupta et al. I have seen the code for the depth first search.

> Everybody knows that all you need to explore a labyrinth is a ball of string and a piece of chalk. The chalk prevents looping, by marking the junctions you have already visited. The string always takes you back to the starting place, enabling you to return to passages that you previously saw but did not yet investigate.

How a computer does it in code makes sense, but as a human, I think that the string is sufficient. why would I need the chalk, wouldn't see the string indicate that I have already passed a junction?

# Answer
First of all keep in mind that this is just an analogy meant to convey the intuition behind the DFS algorithm on graphs.

Now graphs can be directed, which would correspond to having a labyrinth with junctions/rooms and one-way pathways between them. Then it is possible for you to be in some room $r\_0$ and to travel to some other room $r\_1 \neq r\_0$ as a part of your labyrinth exploration. Maybe all paths from $r\_1$ lead to a dead end, so you backtrack to $r\_0$. From there you continue to explore until you reach a third room $r\_2 \not\in \\{r\_0, r\_1\\}$. The problem arises if $r\_2$ has a pathway to $r\_1$: without any record that you already visited $r\_1$, you'd visit it again.

To stick with your analogy, you don't need strings if the floor plan of your labyrinth can be represented as a tree (rather than a general graph). Indeed, if you have a tree and some (arbitrary) order among the edges from a vertex to their children (as it is usually the case in actual implementations), you can implement a DFS without keeping any information other than the current and previous vertices of the search (i.e., an edge of the tree).
> 2 votes

---
Tags: depth-first-search
---


# Question
Title: Algorithm to check that one sum is less than another
Suppose that we have two sums: a1+a2+...+an, b1+b2+...+bm

We can perform only two binary operations on operands of these sums:

* lt (less than)
* eq (equal)

These operations can return 3 possible results: true, false, unknown. Other operations like summation, subtraction and etc. are not allowed.

The question is how to implement algorithm for function lt(a1+a2+...+an, b1+b2+...+bm), that also returns true, false or unknown? But unknown can be returned only if there is no enough information to return true or false.

For example if we know that (n=m=3 && a1 \< b3 && a2 = b2 && a3 \< b1) the algorithm have to return true. Or if we know that (n=3 && m=2 && a1 \< b1 && a2 \< b1 && a3 \< b2 && b1 \< b2) the algorithm have to return unknown.

# Answer
> 0 votes
I will assume your variables can take on arbitrarily real numbers. Build a weighted directed graph that represents all known inequalities, with one vertex per element (i.e., $n+m$ vertices in total). In particular, apply 'eq' and 'lt' to all ${n+m \choose 2}$ pairs of elements. Then:

* If $x \< y$ (i.e., $\textsf{lt}(x,y)$ returns true), where $x,y$ are two elements, add a directed edge $x \to y$ with length $-1$.
* If $x \le y$ (i.e., $\textsf{lt}(y,x)$ returns false), add a directed edge $x \to y$ with length 0.
* If $x=y$ (i.e., $\textsf{eq}(x,y)$ returns true), then add directed edges $x \to y$ and $y \to x$ with length 0.
* If $x\ne y$ (i.e., $\textsf{eq}(x,y)$ returns false), do nothing and add no edges.

Let $d(x,y)$ be the length of the shortest path from $x$ to $y$ in this graph. If $d(x,y)=c$, then we will be guaranteed that $x \le y + c$, and this is the optimal $c$ for which this is true (i.e., it is the smallest $c$ for which this is true).

Compute a new bipartite graph $G$ with an edge $a\_i\to b\_j$ of length $d(a\_i,b\_j)$ for each $a\_i,b\_j$. This can be computed with the Floyd-Warshall algorithm, for example.

Find the minimum-weight perfect matching in this bipartite graph. This is an instance of the assignment problem, and hence can be solved in polynomial time with standard algorithms. If the total weight of the matching is $w$, then we can conclude that

$$a\_1+\dots+a\_n \le b\_1+\dots+b\_m + w.$$

Consequently, if $w \le 0$, then we can conclude that $a\_1+\dots+a\_n \le b\_1+\dots+b\_m$ and we can return "true" to the original question.

Solve another assignment problem for the bipartite graph with edges $b\_j \to a\_i$ of length $d(a\_i,b\_j)$ for each $a\_i,b\_j$. In this way, we obtain $w'$ such that

$$b\_1+\dots+b\_m \le a\_1+\dots+a\_n + w'.$$

If $w' \le 0$, return "false" to the original question.

Otherwise, return "unknown".

This takes $O(nm)$ calls to the binary operations and $O((nm)^{2.5} \log n)$ running time.

This works for this very specific problem. A more general approach is to use linear programming: if you want to check whether $(I\_1 \land \cdots \land I\_k) \implies J$, where the $I$'s and $J$ are linear inequalities, then check whether the system of inequalities $I\_1 \land \cdots \land I\_k \land \neg J$ is satisfiable using linear programming. This will let you support more general mathematical expressions and more general relationships between the variables, as long as they are all linear functions/inequalities of the variables. In your problem, after you call 'lt' and 'eq' on all pairs of elements, each operation that returns something other than "unknown" gives you an inequality or equality $I\_i$ on two variables. Here $J$ is the inequality $a\_1+\dots+a\_n \le b\_1+\dots+b\_m$. So, you could apply linear programming directly to your problem. This approach also supports more general operations, as long as they are all linear.

My answer above essentially solved the linear programming problem for the special case where $I\_1,\dots,I\_k$ are all inequalities with a difference of two variables, and $J$ has the form $a\_1+\dots+a\_n \le b\_1+\dots+b\_m$. I used a standard data structure for representing differences of two variables (the graph), and then combined it with an algorithm for the assignment problem to capture the one additional inequality with multiple variables.

---
Tags: algorithms
---


# Question
Title: Are there 3-colorable maps that can never be colored?
I just watched this explanation of zero-knowledge proofs with Avi Wigderson: https://www.youtube.com/watch?v=5ovdoxnfFV

Key claims from the video:

* Every formal statement can be translated into a map in a way that preserves truth. If a statement is true, its map will be 3-colorable. If not, it isn't 3-colorable https://youtu.be/5ovdoxnfFVc?t=1721

If every formal statement can be translated to a map, and suppose there's a true statement that can't be proven true by Gödel's incompleteness theorems, then doesn't that mean that no algorithm whether P, NP, or worse can exist to color it? Does that mean that there are some 3-colorable maps that can never be colored?

This seems wildly counterintuitive (which maybe is just the nature of Gödels' incompleteness theorems, which I haven't tried to understand the proof of). Or maybe I don't understand Gödel's incompleteness theorems (also likely). If I'm misunderstanding something though, it'd be helpful to know what to look into more.

# Answer
> Every formal statement can be translated into a map in a way that preserves truth. If a statement is true, its map will be 3-colorable. If not, it isn't 3-colorable https://youtu.be/5ovdoxnfFVc?t=1721

Every formal statement **in propositional logic** can be translated to a map 3-coloring instance. The video is being very sloppy with calling this 'every mathematical statement', as there's many mathematical statements that aren't captured in propositional logic.

Propositional logic is decidable (it's equivalent to the SAT problem).
> 4 votes

# Answer
That's an informal description of what has been proven. To make it precise, you need to understand what is meant by 'statement'. Once you dive into it, you'll discover that 'statement' refers to one thing in the video and another thing in Godel's theorems. So I recommend understanding the details of that claim and its proof.
> 1 votes

---
Tags: undecidability
---


# Question
Title: Turing machine that checks whether a given string is an output of a given machine and input
Is there a Turing machine such that, given a description $\langle M \rangle$ of a Turing machine $M$, an input $x$ and a string $y$, computes whether or not $y$ is the output of $M$ input $x$?

My guess is that the answer is no because this might imply that the set of strings with Kolmogorov complexity greater than or equal to their length is decidable.

# Answer
No. Any such machine $T^\*$ would allow you to immediately solve the halting problem. Given a description of $M$, construct a Turing machine $T\_M$ that simulates $M$ and then outputs some fixed string, e.g., "0". Notice that, given $M$, $T\_M$ is computable.

Then $T^\*$ with input $T\_M$ and "0" accepts if $M$ halts and rejects if $M$ does not halt.
> 3 votes

# Answer
No, in fact any non-trivial semantic property of Turing machines is undecidable. This result is Rice's theorem.
> 4 votes

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


# Question
Title: What mathematical guarantees gives alpha-beta pruning?
In the alpha-beta pruning version of the minimax algorithm, when one evaluates a state `p` with $\alpha$ and $\beta$ cutoff and gets a `v` value, i.e.,

*v = alphabeta(p, $\alpha$, $\beta$)*

are these properties true?

1. *alphabeta(p, -$\infty$, $\beta$) = v* when *$\alpha$ \< v*
2. *alphabeta(p, $\alpha$, $\infty$) = v* when *v \< $\beta$*
3. *alphabeta(p, $\alpha$', $\beta$') = v* when *$\alpha$ $\le$ $\alpha$' $\le$ $\beta$' $\le$ $\beta$*
4. if *v \> $\beta$*, then *alphabeta(p, $\beta$, $\infty$) = alphabeta(p, $\alpha$, $\infty$)*
5. if *v \< $\alpha$*, then *alphabeta(p, -$\infty$, $\alpha$) = alphabeta(p, -$\infty$, $\beta$)*

I've reached to this results studying the algorithm itself after reading a couple of papers. After applying it to a real case I've got an improvement of ~30% (in number of states visited, and this gives about a 30% of time execution improvement also), but I want to know if there is a mathematical background that supports these changes to the algorithm.

# Answer
For a complete reference you can check An Analysis of Alpha-Beta Priming If I am not misunderstanding eq 15 and 16 apply to your case.
> 0 votes

# Answer
My understanding is that these inequalities are just required to make alpha/beta pruning correct, that is to guarantee that you get the minimax result.

You say you get an improvement of 30%. You might add if that is 30% fewer numbers checked, or 30% faster execution time (you might be checking say 65% fewer numbers, but might take twice as long on average per number checked).

But alpha/beta works best if you have a reasonably good heuristic to find and check “good” values i first, and for each value i find bad values ij first. The reason: If you examine an i first where the minimum of $a\_{ij}$ is large, then it will be easier to reject i’ which is not as good as i, and if you were able to guess a j first that makes $a\_{ij}$ small then i’ is again easier to reject.

In chess alpha-beta pruning will be substantially better than just 30%.

PS. I thought about it, and your savings should be a lot more than 30%, even if your values are random. Say you have 100x100 values which are a just random. If you examined i and now examine i’ and i’ has a higher maximum, then you examine on average 50% of the values to find the maximum at which point the search for i’ is pruned (or likely even earlier). If the maximum is lower, you examine 100 values. For the k-th value I that you examine the chance that it has the lowest maximum so far is 1/k so it’s much more likely that you examine around 50 numbers, not 100.

But after a while the smallest maximum will get smaller, and you’ll find a bigger element in a row much faster than after 50 attempts. Someone with more patience can probably give you a good approximation but I’m sure you need to examine much fewer than 70% of all numbers.
> 0 votes

---
Tags: algorithms, discrete-mathematics, minimax
---


# Question
Title: Understanding 2's complement multiplication using Booth's algorithm
I was referring Booth's algorithm for 2's complement multiplication from William Stallings book. It was explained as follows (please ignore two starting words "As before", it still makes complete sense):

>

The author then gives following example for $7\times 3$, which I am able to understand:

>

Next author gives examples for all combinations of +ve and -ve combination of multiplication:

**Doubt**

I am not able to get how example in figure 9.13 maps to same example but more compact approach illustrated in figure 9.14(a). I mean how those entries are made in fig 9.14 (a)

**PS**: Wanted to add tags "booths-algorithm" and "2s-complement-multiplication", but wasnt able to create those due to low reputations.

# Answer
So, it goes like this, we have **Q = 0011** and **Q-1 = 0** in the beginning.

At the start, we have

> **count = 4**
> **(Q0 Q-1) = (1 0)**

so we perform the **A←(A-M)** operation, according to the figure each time when we perform any operation in **register A**, we assume that its value is **00000000** for **+M** and **11111111** for **−M**. Performing **A←(A-M)** yields the first partial product

> **A = 11111111+00001001 = 11111001**

Now, we have

> **count = 3**
> **(Q0 Q−1) = (1 1)**

note here, when we have **(Q0 Q−1)** as **(1 1)** or **(0 0)**, we'll just skip and put *all 0s* in the partial product by shifting it by 1 bit to the left (as we do in multiplication) as it's done in the book, which is the 2nd partial product

> **A = 00000000+00000000 = 00000000**
> shifting it left by 1 bit, **00000000**

Now, we have

> **count = 2**
> **(Q0 Q−1) = (0 1)**

so we perform the **(A←A+M)** operation, which gives us the 3rd partial product

> **A = 00000000+00000111 = 00000111**
> shifting it left by 2 bits, **00011100**

Now, we have

> **count = 1**
> **(Q0 Q−1) = (0 0)**

as mentioned above, we'll just skip and put all 0s as the 4th partial product

> **A = 00000000+00000000 = 00000000**
> shifting it left by 3 bits, **00000000**
> `(this isn't illustrated in the figure 9.14(a))`

after this operation **count = 0** and then we'll sum up all the partial products as

```
   11111001 (1st partial product)
   00000000 (2nd partial product)
   00011100 (3rd partial product)
 + 00000000 (4th partial product)
-------------------
   00010101 (final product)

```

As we all know (00010101)2 = (21)10. That's what done in the **figure 9.14(a)**, but shown in a different (**or COMPACT**) way as

```
   11111001
   0000000
 + 000111
-------------------
   00010101

```

Well, you can make it more compact like this:-

```
   11111001
 + 000111
-------------------
   00010101

```

But all of 'em will give you the binary representation of 21.
> 1 votes

---
Tags: multiplication
---


# Question
Title: Reduction for the proof that COMBI $:= \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$ is NP complete
Given the Language $COMBI := \\{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\\}$. Proof that Combi is NP-complete.

I tried to reduce Clique \<=p Combi. I had two different ideas:

* Let $f(\langle G,k\rangle) = \langle G,k\rangle$ so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow f(\langle G,k\rangle)$ is trivial. Though I am puzzled with the case $f(\langle G,k\rangle) \in$ COMBI $\Rightarrow \langle G,k\rangle $. What is when I have only an Independent set $\geq k$ within $\langle G,k\rangle$ and no Clique $\geq k$. Then it would be in COMBI but not within CLIQUE.
* Let $f(\langle G,k\rangle) = \langle G´,k\rangle$ where $G´= \overline{G} \cup G$ as disjunctive union (two different components) and $\overline{G}$ is the complement graph so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow f(\langle G,k\rangle) \in$ COMBI is trivial again, but the other case seems to be flawed due to the same reason as in the first try.

Where am I going wrong or do I have to make a completely different reduction $f$?

# Answer
Let $\langle G=(V,E), k \rangle$ be an instance of CLIQUE with $k \ge 1$, and let $n=|V|$.

Let $S$ be a new set of $n$ additional vertices. Construct a new graph $G'=(V', E')$ with $V' = V \cup S$ and $E=E' \cup (S \times (E \cup S))$. Now consider an instance $\langle G', n+k \rangle$ of your problem.

If $G$ has a clique of size $k$ containing the vertices in $C \subseteq V$ then $G'$ has at least one clique of size at least $n+k$. Pick, e.g., the clique induced by $C \cup S$.

If $G'$ has a clique or an independent set of size $n+k$ then let $C$ be the set of vertices that induce such a clique or independent set set. Since $C \cap S \neq \emptyset$ and $|C| \ge 2$, $C$ cannot be an independent set and therefore it is a clique. Then $C' = C \setminus S$ is a clique of size at least $n+k-n=k$ that is also a subgraph of $G$.
> 2 votes

---
Tags: np-complete, clique, polynomial-time-reductions
---


# Question
Title: Are there search problems that cannot be written as decision problems?
I'm not sure whether the distinction between decision and search problems has a deeper significance or if it is just concerns the immediate answer to the problem.

Of course, if you have a finite solution space then you can easily turn a search problem into a decision problem by assigning a 'yes' to whichever output satisfies your conditions. Even if you are searching for the object which maximises some function on the solution space, you can pairwise compare the evaluations of the function to assign 'no' values and be left with the 'yes' solutions.

Perhaps there are search problems cannot be turned into decision problems if we are unable to enumerate the solution space and assign a 'yes' or 'no' to every value?

# Answer
In terms of **decidability**, they are equivalent. Indeed, in order to turn a decision problem into a search problem we do the following:

1. Run the decision algorithm
2. If it outputted "no", return "no solution exists"
3. Else, create a list called $Active$, and a counter $w\in\Sigma^\*$.
4. Until you find a solution, repeat the following 5-6 steps:
5. Create a new instance of an algorithm that checks whether $w$ is a valid solution, and add this instance to $Active$.
6. For every instance in $Active$, run the algorithm one more step. If any one of them returned "true", return the $w$ associated with it. Otherwise, increase the counter $w$ by one.

Intuitively, the word $w$ enumerates over all $\Sigma^\*$, and for each one we check wether it is a valid solution. Since the decision algorithm must have returned "true", there is a valid solution, say $w^\*$. Since $w$ enumerates over **all** $\Sigma^\*$, then it will also go through $w^\*$ and thus will find the valid solution.

---

In terms of **computation time**, the two might differ. It depends on the language itself, and on the granularity of the time complexity you are trying to achieve. For example, $SAT$ has a known search to decision reduction that runs in polynomial time. This means that you can solve the search problem by a polynomial factor of the decision problem. But it wont help you if you are looking for a sub-polynomial factor instead.
> 2 votes

---
Tags: decision-problem, search-problem
---


# Question
Title: Question about pointer in PCB structure and meaning of job queue
PCB structure exists inside kernel area. And in ready queue, which is Linked List, each Node of the queue is PCB. And this mean PCB Node has the next address of PCB in the queue, right?? Then My question is this..

1. Does PCB structure has pointer field that has address of next PCB structure??
2. According to Wikipedia, Job Queue consists of process waiting to be allocated to Memory. But, in terms of 'process', process means the program loaded on the Memory waiting to be executed or being executed. And how can Job Queue consists of process, that is not loaded onto the memory(I think we can't say it is process because it is not on the Memory)

# Answer
> PCB structure exists inside kernel area. And in ready queue, which is Linked List, each Node of the queue is PCB.

This is correct, however in most operating systems, ready tasks are sorted by priority to ensure that the most important task will run next. So the design of the ready queue may be more sophisticated than this in practice.

> Does PCB structure has pointer field that has address of next PCB structure??

This is the way that it's usually done. Of course, if it is implemented as a doubly-linked list, it will have a "previous" pointer too.

> According to Wikipedia, Job Queue \[...\]

I can see why this may be confusing. The Wikipedia page that you're talking about is about batch processing systems. This is a related idea, and there are batch processing systems without user interaction, but it's not relevant to what you're trying to understand.
> 0 votes

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


# Question
Title: Is a system of equations derived from mutually recursive ADTs always uniquely solvable?
After looking at Can a computer determine whether a mathematical statement is true or not? for a while, I worry we may be into incompleteness/halting problem territory with this question, so an answer on that front, while disappointing, would also be acceptable

I've been interested by ADT equations since I read the linked post, and I've started thinking about them in the context of Coq's inductive types (which essentially permit the usual sum, product, and unitary type constructors).

In particular, I've been considering the correspondence between type definitions and the number of elements inhabiting the type. In particular, solving the type's equation yields the number of elements inhabiting the type, and it seems reasonable to me that, for any so-definded type, this number is at most $\aleph\_0$. That is, for any ADT or inductively defined type, the number of inhabitants is at most countably infinite. I'm thinking about how to formulate or prove such a statement in Coq, and in the meantime had some questions. (It seems further natural that such types and numbers are in one-to-one correspondence up to isomorphism between types of the same cardinality, but that might be a step too far).

It seems easy enough to show a type definition containing exactly $n$ elements for any natural $n$, so that gives one direction of a theorem connecting the two. Going the other way, though, seems more difficult, and in either case it woudl be natural to me to rely on a function $C$ from types $\tau$ to numbers (what class of numbers?) $n$ where $C(\tau) = n$ means there are $n$ elements inhabiting the type.

The trouble is, this function doesn't seem computable. If we take the naturals as

```
Inductive nat: Type :=
  | O
  | S: nat -> nat.

```

such a function would be required to produce an infinity (namely $\aleph\_0$), and thus I don't think Coq could accept such a definition. (Worse, how would the definition know when to return 0?)

So I've come back around to equations. I wondered if I could formulate this idea by constructing for each type $\tau$ (possibly parameterized on other types $\alpha, \beta, \dots$) a polynomial (is this the right term, since it may really be a recurrence?) in the same class of numbers $\tau(\alpha, \beta, \dots) = P(\tau, \alpha, \beta, \dots)$ and proving that all such equations have a unique solution (and herein lies my concern above: would this even be provable?).

This brings me to my main question: I believe that the above statement is true in the absence of mutually recursive types. But mutually recursive types suggest systems of equations, rather than a single equation, and it is well-known that systems do not always have a solution.

But these systems would have some (possibly unique) properties:

* they would be polynomial in this class of numbers
* each would have the form $\tau\_i = P(\tau\_1, \dots, \tau\_n)$
* there would be exactly $n$ equations for $n$ mutually recursive types

Is it possible to prove (or already proven) that such systems are always uniquely solvable in the naturals? I suspect it might be easier to formulate in Linear algebra, but I'm a bit rusty on what it takes to do that here.

# Answer
The initial assumption about such types having at most countably many elements is false. We can use inductive types to define a non-countable type, namely the countably branching trees:

```
(* Countably branching trees. *)
Inductive Tree : Type :=
  | Leaf : Tree
  | Node : (nat -> Tree) -> Tree.

Lemma nocycle (t : Tree) : forall (f : nat -> Tree), t = Node f -> forall a, f a <> t.
Proof.
  induction t as [? | f H].
  - easy.
  - intros g E n.
    injection E.
    intro E'; destruct E'.
    intro gN.
    now elim (H n f gN n).
Qed.

Corollary uncountable_Tree :
  ~ exists (f : nat -> Tree), forall t : Tree, exists n, f n = t.
Proof.
  intros [f H].
  destruct (H (Node f)) as [n ?].
  now pose (nocycle (Node f) f eq_refl n).
Qed.

```

In any case, counting elements of types is a tricky business. Consider the following inductive type:

```
Inductive cow (P : Prop) : Type :=
  | moo : P -> cow P.

```

Consider any propostion `Q : Prop`. If `cow Q` has zero elements then `Q` is false, and if it has an element then `Q` is true. So if we could count the elements of `cow`, we could also tell whether it has zero elements, and would be able to decide an arbitrary proposition, which would give us excluded middle.

You need to restrict the inductive types quite severaly to obtain a small enough family of them whose sizes can actually be counted.
> 3 votes

---
Tags: type-theory, linear-algebra, formal-methods, abstract-data-types
---


title: Algorithm for evaluating polynomials

text:
# Question
Title: Algorithm for evaluating polynomials
I'm reading *The Algorithm Design Manual* and I stumbled upon this problem. I can't really get my head around this, I don't even know how the number of multiplications could differ, what I mean is that there is no polynomial that would make this algorithm perform poorly. I also have no idea how this could get improved, every operation seems necessary to me.

Any help would be much appreciated.

# Answer
> 0 votes
The number of multiplications in the algorithm is $2n - 1$, but the number of multiplications in the Horner's method is $n$, which means this algorithm is not optimal.

As mentioned in the Wiki page, Horner's method in evaluating a polynomial is optimal, therefore we can change this algorithm so that it uses the Horner's method.

```
p = a[n]

for i = n-1 to 0:
   p = p.x + a[i]

```

---
Tags: time-complexity, algorithm-analysis
---


# Question
Title: What can be said about the Fourier expansion of compositions of Boolean functions, if anything?
Let $\chi\_S: \mathbb{F}\_2^n \to \\{\pm 1\\}, x \mapsto (-1)^{\sum\_{i \in S}x\_i}$ for every $S \subseteq \[n\]$ denote the parity functions from $\mathbb{F}\_2^n$ to $\\{\pm 1\\}$. Then, of course, every $f: \mathbb{F}\_2^n \to \\{\pm 1\\}$ can be written as a linear combination (over $\mathbb{R}$) of the parity functions. I have tried (without much ease or success), to produce the Fourier expansions of compositions of even simple Boolean functions, in particular of conjunctions of parity functions, like $\chi\_S \wedge \chi\_T$ (where under the encoding of $1\_{\mathbb{F}\_2^n} \mapsto -1,0\_{\mathbb{F}\_2^n} \mapsto +1$, $\wedge$ is just $\max\_2$).

So, my questions are:

1. Are there good techniques/tools in general for computing/estimating the Fourier expansion of $f \circ g$ when we know both of the expansions for both $f,g$?
2. Is there something we can say about the particular case of conjunctions/disjunctions over parity functions?

# Answer
If $f,g$ are two $\pm1$-valued functions and $f \lor g$ is their maximum (this is the standard notation for maximum; $\land$ stands for minimum), then $$ f \lor g = \frac{1 + f + g - fg}{2}. $$ Since $\chi\_S \chi\_T = \chi\_{S \Delta T}$, this shows that $$ \chi\_S \lor \chi\_T = \frac{1}{2} + \frac{\chi\_S}{2} + \frac{\chi\_T}{2} - \frac{\chi\_{S\Delta T}}{2}. $$ You can read the Fourier expansion from this (unless $S = T$, in which case $\chi\_S \lor \chi\_S = \chi\_S$).
> 1 votes

---
Tags: boolean-algebra
---


title: Circuits and Closure Under Reductions

text:
# Question
Title: Circuits and Closure Under Reductions
Suppose that $A$ and $B$ are languages such that $A\leq\_P B$ (many-to-one Karp reduction), and $B\in \mathbf{P/poly}$. How do we prove that $A\in\mathbf{P/poly}$?

Using similar ideas like Cook-Levin (or $P\subseteq \mathbf{P/poly}$), I can show that given $x\in\\{0,1\\}^n$, there exists a (easily computable) poly-sized circuit that can compute each bit of the reduction, say $R(x)$. The issue for me is that the size of $R(x)$ may depend on $x$ and not only $n$ (since we only require it to be bounded by $\mathrm{poly}(n)$). In such a case, it is not clear how to what input length circuit for the language $B$ to use.

# Answer
> 0 votes
If $A \leq\_P B$ then since $P \subseteq P/\mathit{poly}$, also $A \leq\_{P/\mathit{poly}} B$. This means that there is a function $f \in P/\mathit{poly}$ such that $x \in A \leftrightarrow f(x) \in B$. Since $f \in P/\mathit{poly}$, for every $n$ there is a polynomial size circuit $C$ that computes $f(x)$ for $x$ of length $n$. The circuit needs to have some mechanism for indicating the output length, which might depend on $x$.

Since $C$ has polynomial size, in particular, there are only polynomially many options for the output length, and so if $B \in P/\mathit{poly}$, these circuits can be connected to the outputs of $C$ in order to compute $A$.

---
Tags: complexity-theory, reductions, circuits
---


# Question
Title: Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$
Given a grid graph $G=(V,E)$ which has only two different integer costs/weights of 1 and 2. Find Minimum Spanning Tree in $O(|V|+|E|)$.

I tried the following:

* Changing Kruskal using a counting Sort in $O(|E|)$. But can I say that this results in O(|E|+|V|)? Since Kruskal would normally be ${\displaystyle O(T\_{sort}(|E|)+|E|\cdot \alpha (|V|))} =O(|E|)$ when $\alpha (|V|) \in O(1)$ Can this be stated for this case? I lack detailed understanding of inverse ackerman behaviour.
* Other possibility changing Prim so that I use a priority queue which support del\_min, decreaseKey and insert in $O(1)$. I thought about using two simple stacks or queues and only del\_min from the one, which holds the 1 integers, but descreaseKey seems not efficient since I have to loop through the lists to find the elements. So maybe combine this with some kind so hash mapping to directly access each element in $O(1)$ for decreaseKey?

Both seem really close to the actual result, though I am struggling to see the right solution for this case.

# Answer
Let $n=|V|$ and $m=|E|$.

Intuitively you want the to return the union of the edges in 1) a maximal spanning forest $F$ of the graph induced by the edges of weight $1$, with 2) a maximal spanning forest $F'$ of the graph obtained by identifying the edges of each tree in $F$ into a single vertex (where each edge in $F'$ actually represents an edge of $G$).

Some care is required to attain a running time of $O(n)$. The details are as follows.

---

Let $G\_1$ be subgraph of $G$ induced by the edges of weight $1$. Let $C\_1, \dots, C\_k$ be the connected components of $G\_1$. For each $C\_i$, compute any a spanning tree $T\_i = (V\_i, E\_i)$ of $C\_i$. This requires $O(m)=O(n)$ time in total.

For each edge $e=(u,v)$ of weight $2$ in $G$ let $i$ and $j$ be such that $u \in C\_i$ and $v \in C\_j$. Let $k(e) = (\min\\{i,j\\}, \max\\{i,j\\})$. Sort the edges of $G$ in nondecresing order of $k(\cdot)$, keep at most one edge for each value of $k(\cdot)$. Let $S$ the resulting ordered set of edges. Notice that $S$ can be found in time $O(m)=O(n)$ using radix-sort.

Create a graph $G\_2$ with vertex set $\\{1, \dots, k\\}$ and edge set $\\{ k(e) : e \in S \\}$. For an edge $(i,j)$ in $G\_2$ let $\ell(i,j)$ be and edge $e$ in $G$ such that $k(e) = (i,j)$. This *label* $\ell(i,j)$ can be stored along with the edge $(i,j)$ itself, so that given $(i,j)$ we can find $\ell(i,j)$ in $O(1)$ time. This step also requires $O(n)$ time.

Finally, compute any spanning tree $T' = (V', E')$ of $G\_2$. An MST of $G$ is the tree induced by the edges in $\left( \bigcup\_{i=1}^k E\_i \right) \cup \\{ \ell(i,j) \mid (i,j) \in E'\\}$.

Overall, the whole algorithm takes $O(n)$ time. The same algorithm extends naturally to any constant number of distinct edge weights.

Here is a visualization of the algorithm on the graph you proposed in the comments. Blue edges has weight $1$, red edges have weight $2$. The connected components of $G\_1$ are highlighted in gray (and each connected component will be represented by a vertex in $G\_2$). In this particular example $S$ contains all red edges of $G$ since each red edge connects a different (unordered) pair of connected components in $G\_1$.
> 2 votes

---
Tags: weighted-graphs, minimum-spanning-tree, prims-algorithm
---


# Question
Title: Code and time complexity of multiplication à la française
This references the multiplication algorithm in Chapter 1 of *Algorithms* by Dasgupta et al.

I am trying to understand how the code for multiplication à la française works from the multiplication by hand. This is the example given.

This is the code given for it.

I went ahead and did multiplication of $13 \times 11$ (odd) case and $13 \times 10$ (even) in a spreadsheet and this is what I got.

It seems to me that in the code the rows of the columns are flipped with respect to handwritten example, that is, in $13 \times 11$, the 1 shows up where 13 is and not where 104 is as in the handwritten example. I still get the correct answer. Where did I make a mistake? In the evaluation or understanding the conversion from handwritten algorithm to algorithm in code.

I also have trouble seeing how to get $O(n^2)$ for the time complexity. I understand that there is bit shifting and addition and so at some point, assuming both $x$ and $y$ are n bits, we end up adding $1 + 2 + 3 + \dots + n = \frac{n}{2}(n+1) = O(n^2)$ but aren't we shifting the bits $n$ times and therefore need to multiply by another factor of $n$ to get $O(n^3)$?

This is what I get when I think of the equation for master theorem: $T(n) = T(\frac{n}{2}) + O(n)$ because there is 1 recursive call and the problem is halved and it takes $O(n)$ time to add n bits. However, this equation would give me $\Theta(n)$ which is wrong. What step did I miss in the recurrence equation?

# Answer
In the function $T(n)$, the parameter $n$ represents the length of the input in bits. The recursive call reduces $y$ to $\lfloor y/2 \rfloor$, which reduces the length of the input by a single bit. Hence the recurrence is really $T(n) = T(n-1) + O(n)$, whose solution is indeed $T(n) = O(n^2)$.
> 1 votes

---
Tags: recursion, multiplication
---


# Question
Title: Concrete example of an admissible A* heuristic compared to Djisktra
As I understand it, A\* is a general form of Djikstra where the selection of the next node to visit can be based on something other than the actual distance. For example, with Djikstra, you'd use a priority queue ordered ascending by distance and shift off the head of the queue to decide where to visit next. But with A\*, the order of the priority queue can be based off of the actual distance and/or another factor (the heuristic). The heuristic is considered admissible if the value it returns is guaranteed to be equal to or less than the actual distance. In other words, Djikstra is a form of A\* where the heuristic always returns the actual distance.

So, what is a concrete example of an admissible A\* heuristic?

It seems like writing a heuristic function that always returns an equal to or lesser value than the actual distance would require some magical insight about the graph obtained if I already knew the shortest distances.

# Answer
> 1 votes
> In other words, Djikstra is a form of A\* where the heuristic always returns the actual distance.

This is wrong. Dijkstra's is a form of A\* where the heuristic *is always 0*.

Dijkstra's algorithm is essentially the weighted-graph version of a breadth-first search. It simply spreads out from the start node in all directions until it researches the end node. It could spend a lot of time searching paths that are going in the complete opposite direction of the end, because it doesn't know anything about the global properties of the graph.

That's where the heuristic comes in. Since we know the approximate direction of the end, we can prioritize searches that move in that direction. In a 2D graph, for example, this would mean prioritizing searches that are closer to the end from a bird's-eye view.

The heuristic is *added* to the total distance so far to determine which nodes to consider next. If the heuristic is 0, then we're only using the distances known so far, meaning we don't prioritize any direction and we get Dijkstra's algorithm again. However, if it's non-zero, we do prioritize certain directions, which hopefully leads to us reaching the end sooner.

Note that the heuristic is just an estimate, *not* the actual distance to the end. In fact, it's more than an estimate - it's a lower-bound to the actual distance *(that's what "admissible" means)*. In our 2D example, our heuristic is the bird's-eye view straight-line, which is the shortest possible path between two points. Adding obstacles will never decrease this path length, only increase it.

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


# Question
Title: Compilers: How to see "the number of grammars where there exists a string that has at least two different left-most derivations"?
Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?

# Answer
Although the problem of detecting whether a grammar is ambiguous is, in general, undecidable, for toy grammars like this it is usually pretty easy to find ambiguities by simply enumerating the possible (left-most) derivations until you derive the same sentence in two ways.

For example, $G\_1$ has just three productions $S\to a S b \mid S b \mid c$, and none of them has more than one non-terminal on the right hand side. So there are only four derivations of three steps, and it's easy to see that two produce the same sentence.

$$\begin{align}S&\to a S b \to a a S b b \to a a c b b \\; (P\_1, P\_1, P\_3)\\ S&\to a S b \to a S b b \to a c b b\\; (P\_1, P\_2, P\_3) \\ S&\to S b \to a S b b \to a c b b\\; (P\_2, P\_1, P\_3) \\ S&\to S b \to S b b \to c b b\\; (P\_2, P\_2, P\_3)\\ \end{align} $$

$G\_3$ does have a production which produces two non-terminals, so there are a lot more short derivations. Even so, it shouldn't take you very long to find two derivations for the same sentence.

Proving that a grammar is *not* ambiguous is not so easy. One possibility is to create a conflict-free parsing table, using any standard algorithm. Not all unambiguous grammars are deterministic (and fewer are deterministic with a single lookahead) but if you do manage to find a conflict-free parser, then the grammar was definitely unambiguous.
> 2 votes

---
Tags: formal-grammars, compilers, parsers
---


# Question
Title: Loop invariance insertion sort algorithm
I have the following pseudo code for a insertion sort algorithm

```
INSERTION-SORT

1 for j = 2 to A.length
2    key = A[j]
3    // Insert A[j] into the sorted sequence A[1..j-1]
4    i = j -1
5    while i > 0 and A[i] > key
6        A[i+1] = A[i]
7         i = i -1
8    A[i+1] = key

```

I am trying to convert it into executable code written in Python

```
def main():
    A = [5,2,4,6,1,3]
    for j in range(1,len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key
        print A[0:j+1]
    return A

main()

```

is this a correct translation? I'm not sure if I messed something up with the indexes because it seems as though I'm not getting the end index with range. Furthermore I'm going to be testing correctness with initialization, maintenance and termination.

I added the line `print A[0:j]` to show initialization and maintenance but I'm not sure if it should be `print A[0:j-1]`.

Any help is greatly appreciated!

# Answer
Python arrays have 0-based indexing, like in C, and unlike Fortran, which uses 1-based indexing. You can check Wikipedia for information about other languages.

A python array $A$ of length $n$ consists of the elements $A\[0\],\ldots,A\[n-1\]$. The python function `range(n)` goes over the indices $0,\ldots,n-1$, and your `range(1,n)` goes over the indices $1,\ldots,n-1$.

In insertion sort, we go over all prefixes of the array inductively, and make sure that they are sorted. If $A\[0\],\ldots,A\[j-1\]$ is already sorted, in order to make $A\[0\],\ldots,A\[j\]$ sorted, we just need to more the current $A\[j\]$ into its proper location. Since $A\[0\]$ is automatically sorted, we only need to go over $j=1,j=2,\ldots,j=n-1$, at which point the entire array $A\[0\],\ldots,A\[n-1\]$ is sorted. This is why the loop goes over `range(1,n)`.

Is your implementation correct? Practically speaking, the best way to find out is to test it on many inputs. While such a test cannot verify that the algorithm is correct, and could miss some corner cases, it is also likely to catch off-by-one errors, especially in a language like python with bounds checking. Since insertion sort is such a simple algorithm, you are likely to catch any implementation errors by sorting small random arrays.
> 1 votes

---
Tags: algorithms, algorithm-analysis, sorting, correctness-proof, python
---


title: Prove that $(uv)^R = v^Ru^R$

text:
# Question
Title: Prove that $(uv)^R = v^Ru^R$
> The reverse of a string, introduced informally above, can be defined more precisely by the recursive rules $$a^R=a,$$ $$(wa)^R=aw^R,$$ for all $a \in \Sigma$, $w \in \Sigma^\*$. Use this to prove that $$(uv)^R = v^Ru^R,$$ for all $u, v \in \Sigma^+$.

This is exercise 3 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. I am not used to this type of exercise, so I would like some help to get the hang of it.

My attempt: Suppose $u = u\_1...u\_n$ and $v = v\_1...v\_n$. So, $$(uv)^R = (u\_1...u\_nv\_1...v\_{n-1}v\_n)^R = v\_n(u\_1...u\_nv\_1...v\_{n-1})^R \implies (uv)^R = v^Ru^R.$$

Is it correct? If not, any hint? Thanks in advance.

# Answer
> 5 votes
The answer depends on your standard of proof. Let's try to be very strict.

First of all, let us define words. In contrast to Peter Linz, we will not be afraid of the empty string. The set of words $\Sigma^\*$ satisfies the following:

* If $w \in \Sigma^\*$ then either $w = \epsilon$ or $w = x\sigma$, where $x \in \Sigma^\*$ and $\sigma \in \Sigma$.
* $\epsilon \neq x\sigma$ for every $x \in \Sigma^\*$ and $\sigma \in \Sigma$.
* $x\sigma = y\tau$ iff $x=y$ and $\sigma=\tau$.
* Define an *inductive subset* of $\Sigma^\*$ to be a subset $S \subseteq \Sigma^\*$ such that (i) $\epsilon \in S$ and (ii) if $x \in S$ then $x\sigma \in S$ for all $\sigma \in \Sigma$.
    + $\Sigma^\*$ is an inductive subset.
    + If $S$ is an inductive subset then $S = \Sigma^\*$.

Now we can define concatenation of words inductively:

* $w.\epsilon = w$.
* $w.(x\sigma) = (w.x)\sigma$.

Finally, we define reversal:

* $\epsilon^R = \epsilon$.
* $(x\sigma)^R = \sigma.x^R$, where $\sigma$ is syntactic sugar for $\epsilon \sigma$ (which we know to be in $\Sigma^\*$ since it is an inductive subset).

We need several lemmas.

**Lemma 1.** For all $x \in \Sigma^\*$, we have $\epsilon.x = x$.

**Proof.** Let $S = \\{ x \in \Sigma^\* : \epsilon.x = x \\}$. We will show that $S$ is an inductive subset, and so $S = \Sigma^\*$, that is, $\epsilon.x = x$ for all $x \in \Sigma^\*$.

If $x = \epsilon$ then $\epsilon.\epsilon = \epsilon$. If $x = y\sigma$, where $y \in S$, then $\epsilon.x = \epsilon.y\sigma = (\epsilon.y)\sigma = y\sigma = x$, using $y \in S$. $\square$

**Lemma 2.** For all $x,y,z \in \Sigma^\*$, $x.(y.z) = (x.y).z$.

**Proof.** Fix $x,y \in \Sigma^\*$, and let $S = \\{ z \in \Sigma^\* : x.(y.z) = (x.y).z \\}$. We will show that $S$ is an inductive subset, and so $S = \Sigma^\*$.

If $z = \epsilon$ then $x.(y.z) = x.y = (x.y).z$.

Now suppose that $z = w\sigma$, where $w \in S$. Then $$ x.(y.z) = x.(y.w\sigma) = x.((y.w)\sigma) = (x.(y.w))\sigma = ((x.y).w)\sigma = (x.y).(w\sigma) = (x.y).z, $$ using $z \in S$. $\square$

Now we are ready to prove your claim. Fix $x \in \Sigma^\*$, and let $S = \\{ y \in \Sigma^\* : (x.y)^R = y^R.x^R \\}$. We will show that $S$ is an inductive subset, and so $S = \Sigma^\*$, that is, $(x.y)^R = y^R.x^R$ for all $y \in \Sigma^\*$.

If $y = \epsilon$ then $$ (x.y)^R = x^R = \epsilon.x^R = \epsilon^R.x^R, $$ using Lemma 1.

If $y = z\sigma$, where $z \in S$, then $$ (x.y)^R = (x.(z\sigma))^R = ((x.z)\sigma)^R = (\epsilon\sigma)^R. (x.z)^R. $$ Let us notice that $(\epsilon\sigma)^R = \epsilon\sigma.\epsilon^R = \epsilon\sigma.\epsilon = \epsilon\sigma$. Also, since $z \in S$, $(x.z)^R = z^R.x^R$. Therefore $$ (x.y)^R = (\epsilon\sigma).(z^R.x^R) = ((\epsilon\sigma).z^R).x^R = (z\sigma)^R .x^R = y^R.x^R.$$ using Lemma 2. $\square$

---

While I tried to be rather strict, a completely formal proof will be even stricter: it will justify every single step, referring to a definition, a lemma, or a logical axiom. However, the proof above should be easy to convert to something that proof assistants can grok.

---

In practice, you can prove your claim as follows. Let $x = \sigma\_1 \ldots \sigma\_n$ and $y = \tau\_1 \ldots \tau\_m$. Then $$ (xy)^R = (\sigma\_1 \ldots \sigma\_n \tau\_1 \ldots \tau\_m)^R = \tau\_m \ldots \tau\_1 \sigma\_n \ldots \sigma\_1 = (\tau\_m \ldots \tau\_1) (\sigma\_n \ldots \sigma\_1) = y^R x^R. $$ At a more advanced stage, this proof can be summarized by "obvious".

---
Tags: formal-languages, strings
---


# Question
Title: Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time
I am looking for a solution for the following problem:

> Find the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time.

Consider the following sequence: $$ 3, 1, 6, 1, 5 $$ The answer here is $3$, with $6, 5, 3$ being in the set found. The value of $N$ is not a given - we're looking for the largest $N$.

So far, I came up with three solutions:

1. Sort the sequence and go from the top.
2. Use a modified version of quickselect.
3. Use a modified version of BST where elements bigger than the current $n$ are inserted, and elements smaller than the new $N$ are removed.

1 and 3 are more or less $n\log n$ (though I'd expect 3 to be faster), 2 is best case $n$, worst case $n^2$.

Our teacher told us it's possible to do it in a reliable $n$ time. What is the algorithm for the linear solution, if there's one?

# Answer
> 3 votes
Let $n$ denote the length of the array. We will find the largest $N$ such that there are at least $N$ elements whose value is at least $N$.

Make a pass through the array, counting the number of elements of value $1,2,\ldots,n$; if any element has value larger than $n$, count it as $n$.

Using this, determine, for each value $m \in \\{1,2,\ldots,n\\}$, the number of elements whose value is at least $m$.

Now you can easily determine the solution.

# Answer
> 2 votes
Let $S$ and $\ell$ be a set of input elements (integers) and let $\ell$ be an integer. Consider the problem of finding the maximum cardinality of a subset $S^\*$ of $S$ that contains the largest elements of $S$ and suck that $\min S^\* \ge |S^\*| + \ell$. Your problem is captured by the special case $\ell=0$ (standard techniques allow you to find the subset $S^\*$ itself, rather than just $|S^\*|$).

Partition $S$ in two sets $S\_1$ and $S\_2$ such that $S\_2 = \lfloor |S|/ 2\rfloor$ and $\forall x\in S\_1, y \in S\_2$, $y \ge x$. Let $m$ be the minimum element of $S\_2$. $S\_1$, $S\_2$ and $m$ can be found in $O(|S|)$ time by finding the median $m$ of $S$, partitioning $S$ a-la-quicksort, and using some care when $S$ contains multiple copies of $x$.

If $m \< |S\_2| + \ell$ then the set $S\_2$ contains too many elements, and you can recurse on $S\_2$ and $\ell$.

If $m \ge |S\_2| + \ell$ then $S\_2$ is a feasible solution but is not necessarily the best one. Recurse on $S\_1$ and $\ell+|S\_2|$. If the value returned by the recursive call is $r$ this implies the existence of a set $S^\*$ containing $r$ values from $S\_1$, and all the elements in $S\_2$.

The first call of the algorithm will be on $S$ and $\ell=0$.

---
Tags: sorting, selection-problem
---


# Question
Title: NP Complete Proof - Polynomial Reduction
We know that the INDEPENDENT-SET problem is NP Complete i.e $\langle G',k'\rangle$ means graph $G'$ has an Independent set of size $k'$. I am preparing for the finals an a sample question is to prove TRIANGLE-FREE-SET to be NP Complete. $$TRIANGLE-FREE-SET:=\\{\langle G,k\rangle| \text{$G$ has a subset of vertices of size $k$ whose induced subgraph is triangle free}\\}$$

To give a polynomial reduction of IS instance $\langle G',k'\rangle$ to TFS, I thought of adding an extra vertex and connecting this extra vertex to all the original vertex of the IS problem instance and then have $k=k'+1$. However, I am stuck trying to prove that if $\langle G,k\rangle \in TFS$ then $\langle G',k'\rangle \in IS$. Any leads appreciated.

# Answer
Probably you can get your answer from here: Reducing independent set to triangle-free subgraph

Basically in order to prove that $TFS$ is NP-complete you can just check the first proof in the link's answer. Given a graph $G$ with an independent set $k$, there exists a $G'$ with a $TFS$ of size $|V|+k+1$.
> 1 votes

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


# Question
Title: How to simulate online matching algorithms (implementation)
I was reading about online algorithms and bipartite matching.

I found an implementation that works fine on several websites (like geeksforgeeks). For the online version, I found this paper https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf

But there's one part that I don't understand.

In this paper, they refer to U (boys) as "on-line" which means data arrive sequentially (in real-time?) not all at once

While I can see how such case if frequent in real life, I fail to understand what kind of implementation could be used to demonstrate this...

I thought of the following

* Create a graph with girls
* add boys and define manually the girls they like via some sort of user input (input py/cin c++)
* solve(match) for the newly added boy according to rank(priority) and return to user input till no more girls are left or till user decides to stop?

In the online version do we assume a predefined limited number for both U and V(boys and girls)? or just for girls?

Is my suggestion correct? or did I misunderstand something?

Thanks in advance

# Answer
Just to clarify your doubt. An **online** algorithm is an algorithm that does not have the whole input (otherwise it would be **offline**), but it gets the input in a sequential manner. Looking at your paper, for example, they define an online algorithm as (1 Introduction):

> An on-line algorithm receives a sequence of requests and must respond to each request as soon as it is received

I would use a simpler example than a graph of boys and girls. Think about a list of numbers that you want to sort.

Then an offline algorithm would take the whole input and sort it: quicksort.

An online algorithm sorts after every single number, or better, it ensures that a certain property is maintained over a sequential input. An clear example of it is Insertion Sort, since it ensures that the output list is always sorted.

Now looking at your questions:

1. *In this paper, they refer to U (boys) as "on-line" which means data arrive sequentially (in real-time?) not all at once.* ~\> Exactly. The girls in the example arrive one by one. You might know how many they are in total, (since |V| seems to be given), but you do not know which one is the next one until you "matched" the current one. As in the "insertion sort" example, you do not know the next number until you sorted the current one.
2. *In the online version do we assume a predefined limited number for both U and V(boys and girls)? or just for girls?* ~\> The paper says "Let G(U,V,E) be a bipartite graph", therefore my take on it is that you know how many boys (|U|) and how many girls you have (|V|).
> 1 votes

---
Tags: graphs, probabilistic-algorithms, bipartite-matching, online-algorithms
---


# Question
Title: Solving the recurrence formula $T(n) = 3T(n/2)+n^2$
What is the solution of the following recurrence? $$ T(n) = 3T(n/2) + n^2, \quad T(1) = 0. $$ I cannot use the master theorem since I need to know the exact final expression, not just it's big O, which I know is $O(n^2)$.

I'm stuck at the following, after 4 steps: $$3^4T(n/2^4)+((3^6)n^2)/((2^6)2^6)+(3^3n^2)/((2^2)2^4)+(3n^2)/(2^2)+(n^2).$$

# Answer
First of all, your recurrence is defined only when $n$ is a power of 2, so let us assume that $n = 2^m$. Expanding the recurrence, we get \begin{align} T(n) &= n^2 + 3T(n/2) \\ &= n^2 + 3(n/2)^2 + 9T(n/4) \\ &= n^2 + 3(n/2)^2 + 9(n/4)^2 + 27T(n/8) \\ &= \cdots \\ &= n^2 + 3(n/2)^2 + 9(n/4)^2 + \cdots + 3^{m-1} (n/2^{m-1})^2 + 3^m T(n/2^m) \\ &= n^2 + 3(n/2)^2 + 9(n/4)^2 + \cdots + 3^{m-1} (n/2^{m-1})^2 \\ &= n^2 \left\[1 + \frac{3}{4} + \left(\frac{3}{4}\right)^2 + \cdots + \left(\frac{3}{4}\right)^{m-1} \right\] \\ &= \frac{1-(3/4)^m}{1-(3/4)} n^2 \\ &= 4n^2 - 4 \cdot 3^m \\ &= 4n^2 - 4n^{\log\_2 3}. \end{align}
> 1 votes

---
Tags: algorithms, recurrence-relation
---