# Question
Title: Computing a partial density matrix from an amplitude vector
Suppose you're given the list of $2^{2n}$ complex coefficients defining the state of a $2n$ qubit register. You want to compute the $2^n \times 2^n$ density matrix of the first $n$ qubits.

Is it possible to compute the result in $O(4^n)$ time? That would be optimal, since the output has size $\Theta(4^n)$.

It's easy to hit $O(8^n)$. The naive algorithm that simply computes the density matrix for each possible value of the unrelated qubits and then adds those together achieves that:

```
def density_matrix_of_first_half(amplitude_vector):
  v = amplitude_vector
  M = new complex[2^n, 2^n]
  for r < 2^n:
    offset = r * 2^n
    for i < 2^n:
      for j < 2^n:
        M[i, j] += (v[i + offset] * v[j + offset]).conjugate()
  return M

```

But I was hoping it was possible to do better. Are there any papers about this problem?

(*The reason I care so much more about $4^n$ vs $8^n$ is because I'm actually computing things with a GPU. My textures can have $2^{2n} = 4^{n}$ pixels, so I get the $4^n$ inner-loop in the application of a single shader. But $8^n$ is far over the max texture size, so the $8^n$ algorithm would require a pipeline of $2^n$ shaders. Or at least might force me to drop the qubit limit another 30%.*)

# Answer
> 1 votes
It's a matrix multiplication. Not sure how I didn't notice it right away, but the problem is exactly computing $U \cdot U^\dagger$ for a $U$ whose rows are made up of the chunks of amplitude vector.

```
def density_matrix_of_first_half(amplitude_vector):
  U = new ComplexMatrix(2^n, 2^n)
  for i < 2^n:
    for j < 2^n:
      U[i, j] = amplitude_vector[i + (j << n)]
  P = U * U.adjoint()  // <-- expensive
  return P

```

**Fancy matrix multiplication does asymptotically better than the naive algorithm**

Matrix multiplication can be done in time $O(n^\omega)$, where $n$ is the dimension of the matrix and $\omega$ is known to be below $2.375$. It's conjectured that there may be algorithms where $\omega = 2 + \epsilon$, but no one's managed to find any yet.

In the context of the question with $2^n \times 2^n$ matrices, the complexity is $O(2^{n \omega})$. However, because the asymptotically faster algorithms tend to have large constant factors hidden by the Big-O notation, in practice it's often better to stick with naive multiplication or Strassen multiplication. Also there are probably GPU-optimized matrix multiplication algorithms that would be more relevant given the note at the end of the question.

**$U \cdot U^\dagger$ is not easier than $U \cdot V$**

General matrix multiplication combines two totally independent matrices $U \cdot V$. Given that our density matrix problem only computes $U \cdot U^\dagger$, where the two inputs are totally *dependent*, one wonders if this "adjoint-squaring" is easier than general multiplication. Turns out it's not.

---
Tags: algorithms, quantum-computing
---


# Question
Title: Is matrix "adjoint-squaring" faster than general matrix multiplication?
The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are related to each other in some known way, it's sometimes possible to get a speedup. For example, computing $U \cdot V$ is quite easy if you're promised that $V = U^{-1}$.

I was wondering if knowing $V = U^\dagger$, i.e. that $V$ is the conjugate transpose of $U$, allowed for asymptotically faster matrix multiplication.

**Can the special case $U \cdot U^\dagger$ be computed asymptotically more quickly than the general case $U \cdot V$?**

# Answer
> 6 votes
**It's not faster** (asymptotically). You can reduce general matrix multiplication down to three "adjoint-squarings".

Suppose we're given an adjoint-squaring function $\mathfrak{F}$ where $\mathfrak{F}(M) = M \cdot M^\dagger$. Consider that:

$\mathfrak{F}(A + B) = (A+B) \cdot (A+B)^\dagger = AA^\dagger + BB^\dagger + A B^\dagger + B A^\dagger$

$\mathfrak{F}(A - B) = AA^\dagger + BB^\dagger - A B^\dagger - B A^\dagger$

$\mathfrak{F}(A + i B) = AA^\dagger + BB^\dagger - i A B^\dagger + i B A^\dagger$

Thinking in terms of the basis $\[x, y, z, t\] \rightarrow x AA^\dagger + y BB^\dagger + z A B^\dagger + t B A^\dagger$, those three adjoint-squarings give us $p=\[1, 1, 1, 1\]$ and $q=\[1,1,-1,-1\]$ and $r=\[1,1,-i,i\]$ respectively. From that we want to recover the product $\[0,0,1,0\] \rightarrow AB^\dagger$. A bit of work will show that the linear combination $\frac{1-i}{4}p - \frac{1+i}{4}q + \frac{i}{2} r$ is exactly what we need.

Therefore **we can compute the product $U \cdot V$ via $\mathfrak{F}$ by evaluating:**

$$U \cdot V = \frac{1-i}{4} \mathfrak{F}(U + V^\dagger) - \frac{1+i}{4} \mathfrak{F}(U - V^\dagger) + \frac{i}{2} \mathfrak{F}(U + i V^\dagger)$$

Since the most expensive step of this reduction is the adjoint-squaring (it's certainly not the adding, conjugating, transposing, subtracting, or scaling), and the adjoint-squaring function $\mathfrak{F}$ is only used a constant number of times (3 times), general multiplication is no more asymptotically expensive than adjoint-squaring.

(Related: Is matrix squaring asymptotically faster? Nope. With a much simpler proof.)

---
Tags: complexity-theory, time-complexity, matrices, multiplication
---


# Question
Title: Longest path with at most $k$ edges in a tree
How to find the longest (in terms of sum of weights) simple path with at most $k$ edges in a tree? Weights of edges are integers, so they can be negative. I thought about using Bellman-Ford, but it would take too much time. Is there any faster algorithm than $O(V \cdot E)$?

# Answer
> 0 votes
Have you tried looking at the Shortest Path Faster Algorithm (SPFA)? Even though its worst case time is the same as for Bellman-Ford, the average time complexity on a random graph is $O(|E|)$ and it also works for graphs with non-negative edges.

---
Tags: algorithms, graphs
---


# Question
Title: Find a maximum sum in matrix, subject to special constraint
I have a matrix of size $N \cdot M$ filled with integer values $A\[i\]\[j\]$. I want to choose some numbers so that their sum is maximal. But there is one very important constraint. If I choose numbers in the $i$-th row from interval $\[a, b\]$, then I have to also take the interval $\[\max(1, a - 1), \min(b + 1, M)\]$ in the $i + 1$-th row. In other words, if I use all of $A\[i\]\[a\], \dots, A\[i\]\[b\]$, then I also have to use the elements $A\[i+1\]\[\max (1, a-1)\],\dots ,A\[i+1\]\[\min (b+1, M)\]$.

I can't think of any algorithm for this. I don't even have any idea how to brute-force it. Could someone please help me solve that? I think the optimal solution should have $O(N \cdot M)$ complexity or something like that.

Example input: $N=4$, $M=7$, and $$A = \left(\begin{matrix} &-1 &4 &-6 &-1 &-2 &-5 &10 \\ &5 &-7 &2 &1 &-9 &-13 &2 \\ &2 &4 &-10 &3 &1 &2 &6 \\ &3 &2 &7 &1 &-7 &4 &5 \end{matrix}\right). $$

For this problem instance, the maximal sum is $40$. This can be achieved by taking the 5 in the first column, the 3 in the fourth column, the 1 in the fifth column and the 2 in the last column as the summits of the triangles.

# Answer
This can be solved in $O(NM)$ time using dynamic programming.

Given any solution, let $s$ denote the smallest index $s$ such that $a\[s\]\[1\]$ is selected. (It follows that $a\[1\]\[1\],\dots,a\[s-1\]\[1\]$ are not selected and that $a\[s\]\[1\],\dots,a\[N\]\[1\]$ are selected.) This partitions solutions based on the value of $s$, i.e., based on which entries from the first column are selected in that solution. There are only $N$ possible values for $s$.

Now define $f(s,t)$ to be the largest sum that is possible by selecting some entries from the submatrix $a\[1..N\]\[t..M\]$, subject to the restriction that you choose all of $a\[s..N\]\[t\]$ and don't choose any of $a\[1..s-1\]\[t\]$. You can easily find a recurrence relation that expresses $f(s,t)$ in terms of a few values of the form $f(s',t+1)$. This immediately yields a simple dynamic programming algorithm with running time $O(NM)$.
> 1 votes

---
Tags: algorithms, optimization, dynamic-programming
---


# Question
Title: Is the maximum matching problem trivial when the graph is complete?
I have a quick question.

The maximum matching problem is an easy problem but not a trivial one. I was wondering that if the bipartite graph was complete, is it a trivial problem?

I think we can just select an arbitrary edge $\\{u,v\\}$ and remove the vertices $u$ and $v$ from the graph and continue until there is no vertices.

# Answer
Yes, that would work. Instead of continuing until you have no vertices, though, you should continue until you have no edges. You may have vertices left over, if the two sets have different sizes.
> 2 votes

---
Tags: matching
---


title: Number of levels in the recursion tree

text:
# Question
Title: Number of levels in the recursion tree
While solving Recurrences of type $T\left ( n \right ) = a\cdot T(\frac{n}{b})+c$ using the recursion tree method, number of levels in the recursion tree is equal to $\log\_{b}n$ when $b$ is a constant.
But when $b$ is dependent on $n$, can we say that number of levels are still $\log\_{b}n$?
For example, in
$T\left ( n \right ) = a\cdot T\left ( \frac{n}{\sqrt{n}} \right )+c$

Can we say that number of levels in the recursion tree are equal to $\log\_{\sqrt{n}}n = 2$?
I guess this is wrong but I am unable to reason it properly, please explain me the reason "why this is wrong?"(If it really is).

# Answer
> 1 votes
If $b$ is not a constant, then no, you can't say the number of levels is still $\log\_b n$.

In your example, we have $T(n) = a T(\sqrt{n}) + c$ (since $n/\sqrt{n} = \sqrt{n}$). There are more than 2 levels in the recursion tree. In fact, there are $\lg \lg n$ levels in the recursion tree. So, no, you can't just compute $\lg\_{\sqrt{n}} n = 2$ and conclude that there are 2 levels in the recursion tree -- that gives the wrong answer.

(Why $\lg n$? Suppose $n=2^k$. Then each level halves $k$, so we do a total of $\lg k$ levels we get down to a constant. Since $k = \lg n$, we get a total of $\lg k = \lg \lg n$ levels.)

The Master theorem gives a formula for solving this kind of recurrence, but it's only valid when $b$ is a constant.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Algorithmic Composition: generative vs transformative algorith
What's the difference between **generative** and **transformative** algorithms in relation to algorithmic composition of music?

As I understand the basic idea of the algorithms themselves, generative uses past candidate values (output becomes input) as progenitors (parents) for the next output, i.e. by combining them under certain conditions.

Transformative algorithms use environmental factors only to determine how to change the existing input.

However I've read that generative music as created by Brian Eno can use environmental factors and a single candidate input value, transforming it based on stored environmental factors.

I am struggling to understand what the difference is since there seems to be no universal agreement on what constitutes generative.

# Answer
A *generative* algorithm tries to generate a new song out of nothing.

A *transformative* algorithm takes one song $s$ as input, and tries to produce a new song $s'$ by making some changes to $s$.
> 1 votes

---
Tags: algorithms, terminology
---


# Question
Title: Average Cost Threshold Protocol with Minimum Thresholds: How to find the price?
The protocol is defined here, but I'll give a summary here.

Okay, so a number of agents want a certain public good to be constructed (a public good is something like a book, a program, or a statue, something that can optionally benefit everyone once constructed.) It costs $P$ to construct this good. The agents each give an interval that they are willing to pay. Agent $i$'s interval is $\[m\_i,M\_i\]$. (In the case of a rational agent, $m\_i=0$, but if the agent is somewhat altruistic, $m\_i\>0$. It has been proven that $M\_i$ will always be how much value a rational agent $i$ expects to extract from the public good.)

Now, in this protocol, each person pays the same price $p$, or $m\_i$, whichever is greater, or pays nothing at all if $p \> M\_i$. (Those who pay get access to the good, those who don't are excluded from the good.) What I am trying to do is find the minimum $p$, such that the total amount paid (let's call it $F(p)$) is equal to or greater than $P$, efficiently.

If all $m\_i$ are $0$ and there are $n$ agents, I can do it $\mathcal O(n \log n)$. I first sort the agents by $M\_i$. Then starting with the agent with least $M\_i$, I figure out how much funds will be available with $p=M\_i$. If $F(M\_i) \gt P$, than $M\_i$ is the minimum $p$. Otherwise, we go to the next agent, and so on. $F(M\_i)$ can be calculated in $\mathcal O (n)$, by multiplying $M\_i$ by how many agents come after (or are) agent $i$ (for each agent $j$ that comes after $i$, $M\_j \ge M\_i$. Since $p=M\_i$, not $p\>M\_j$, and agent $j$ pays $p=M\_i$.) (Note, I've left out the analysis for when $p$ is between the $M\_i$'s; it doesn't change the it too much.)

My question is, how does one solve this problem efficiently in general, when the $m\_i$ may not be $0$?

Note: Sorry if I didn't phrase this clearly. Feel free to ask for clarification in the comments.

# Answer
> 2 votes
There are two standard kinds of approaches to this sort of problem.

1. Check out segment trees and interval trees, and see if either of them are useful here (e.g., by augmenting the data structure).
2. Explore a sweep line algorithm. In this sort of algorithm, we envision $p$ increasing from 0 upward as time progresses, and at each point in time, we keep track of the set of all intervals that contain $p$. Thus, when $p$ hits the left endpoint of an interval, we add it to the set; when it reaches the right endpoint, we remove it from the set. You can store the set as a balanced binary tree data structure, and then make it persistent using standard path copying techniques. Now that you have this persistent data structure that captures all points in time, often you can find a way to solve your problem fairly rapidly. Crucially, the tree will be of size $O(n \lg n)$ and depth $O(\lg n)$, so accesses are fast.

I haven't explored either of those approaches in the context of your particular problem, but these are two general techniques that are often useful for problems of this sort.

# Answer
> 0 votes
Okay, so this is how far I got. Adding each agent is $\mathcal O(n)$, for a total of $\mathcal O(n^2)$, but spread out (the application I had in mind would involve agents coming one at a time).

If you have no agents, start with an empty linked list. If you have $n$ agents, you will already have a solution of $p\_{old}$ for $n-1$ agents, as well as an old linked list, as well as our new agent, agent $i$.

The linked list has elements of the form $(\Delta P\_j,m\_j,M\_j)$, where $\Delta P\_j = P - F(M\_j)$, a.k.a., how much more money is needed if $p=M\_j$. It is sorted by $M\_j$, smallest first.

So we traverse our linked list, starting with $(\Delta P\_j,m\_j,M\_j)$. If $M\_i \ge M\_j$, decrease $\Delta P\_j$ accordingly. If $\Delta P\_j = 0$, $p=M\_j$, then the rest of the linked list is discarded (including agent $j$'s node), and we end. If $\Delta P\_j \gt 0$, continue traversing. If $M\_i \< M\_j$, keep a reference to $j$'s node. Now traverse the rest of the list to determine $\Delta P\_i$. If $\Delta P\_i = 0$, then $p=M\_i$, and throw out all nodes after and including agent $j$. If $\Delta P\_i \gt 0$, then before $j$ insert a node $(\Delta P\_i,m\_i,M\_i)$, and $p=p\_{old}$.

---
Tags: algorithms, optimization, efficiency
---


# Question
Title: Brandes' betweenness algorithm for weighted undirected graph
I am studying Brandes' betweenness algorithm for *weighted* undirected graph. I am not sure that, in Algorithm 1 (which is based on Dijkstra's shortest path algorithm),

* If a node is first encountered, then we have to check `d[neighbor_node] < 0`. But if not, do we have to check `d[neighbor_node] > d[current] + length(current,neighbor_node)`?
* If greater, then do I have to delete previous updates like `Queue, Pre[]` and others?

# Answer
Note: I assume that the OP is talking about Algorithm 1 in the paper "A Faster Algorithm for Betweenness Centrality" By Ulrik Brandes.

You probably have noticed that Algorithm 1 in the paper is for *unweighted* graphs. In this case, Dijkstra's algorithm@wiki amounts to BFS and a shortest path for a vertex $v$ is found immediately when $v$ is first encountered (in the pseudo-code, it is represented by `if d[w] < 0 then`). This property is due to the layer-by-layer search feature of BFS.

> $Q\_1:$ If a node is the first occurrence , then we have to check `d[neighbor_node] < 0`. However, if not, do we have to check `d[neighbor_node] > d[current] + length(current,neighbor_node)`?

For *weighted* graphs, the property mentioned above does not necessarily hold. So you need to ***replace*** (meaning the following is not needed any more) the `if d[w] < 0 then` predicate by a slightly involved one suitable for *weighted* graphs:

```
          [foreach] neighbor w of v [do] [if] d[v] + length(w,v) < d[w] [then]

```

Note that for *weighted* graph, you should use a priority queue.

> $Q\_2:$ If greater, then do I have to delete previous updates like `Queue, Pre[]` and others?

No. You set `d[], P[], sigma[]` only when a shortest path is found. It is valid all the time once it is set. No need to update them later.
> 1 votes

---
Tags: algorithms, shortest-path, graph-algorithms
---


# Question
Title: What are Predictive Clustering Trees in machine learning?
Anybody could let me know what exactly the PDT is and where does it come from? it comes from predictive modeling or decision tress?

I read some articles and websites like: this and this but both of them are about predictive modeling. I think PDT comes from decision tree rather than predictive modeling.

# Answer
Clus might get you started. It uses predictive clustering trees and is described in this article, although you'll probably need a student account to get access to that article.

They have a list of publications that you should also find instructive.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Proving that the reversal of a language reversal is that language
I am trying to prove that with language L, (L^R) ^R =L So that the reversal of the reversal of the language is the original language L.

I have proved that before with a **string not language** (let's call it a string 's').

```
(s^R)^R = s.
Proof by induction on the length of s.

Base: |s|=0. s=ε. (s^R)^R =(ε^R)^R =(ε)^R =ε=w.
Induction hypothesis: if 0 ≤ |x| ≤ n, then (x^R)^R = x.
Induction step: Suppose |s| = n + 1. Then we can write s = xa, where a is a symbol and 0≤|x|≤n. Then
(s^R)^R
= ((xa)^R)^R since s = xa
= (ax^R)^R since (xy)^R = y^R*x^R (think of a as a string of length 1) = (x^R)^R*a^R same as previous line but using outer R
= (x^R)^R*a using the second part of the definition of reverse with u=ε.
= xa by the induction hypothesis
= s since s = xa

```

**How can this reasoning the expanded to Languages?** In essence I am proving the same operation, but I am dealing with languages instead of strings. Languages are made up of strings. Thoughts?

# Answer
> 4 votes
Well, we don't really need induction here.

We want to prove that for any language $L$ holds the statement

$$\left( L^R \right)^R = L.$$

(1) Let $s \in \left( L^R \right)^R$. Then there exists a (unique) string $t \in L^R$, such that $s = t^R$. The situation is analogous with $t$: there exists a (unique) string $u \in L$ such that $t = u^R$. From that we get $s = t^R = \left( u^R \right)^R = u$, so $s \in L$.

(2) Let $s \in L$. Observe that $s^R \in L^R$ and $\left( s^R \right)^R \in \left( L^R \right)^R$, again using the fact that $s = \left( s^R \right)^R$ we get that $s \in \left( L^R \right)^R$.

From (1) and (2) follows the statement of the theorem.

# Answer
> 1 votes
Given that it's true for strings (as you've shown), there isn't much to prove: $$\begin{align} (L^R)^R &= \\{s^R\mid s\in L^R\\} \\ &= \\{s^R\mid s\in \\{t^R\mid t\in L\\}\\} \\ &= \\{(t^R)^R\mid t\in L\\} \\ &= \\{t\mid t\in L\\} \\ &= L. \end{align}$$

---
Tags: strings, induction
---


# Question
Title: Which formula corresponds to this K-Map?
I have a K-Map and I need to figure out which expression isn't equivalent to the provided K-Map.

$f(w,x,y,z) = \sum(3,7,9,11,13,15) + \Phi(4,5,6)$

We know that both options (a) and (b) are equivalent, and both represent the K-Map's function.

Option (c) however, turns to $(x)(x+w)$ if we make a subcube of size 8 using the first and last row, and a subcube of 00-01 on both axes (size = 4).

If however we take the first row and last row as different subcubes, and the subcube of 00-01, we get the function = $(x'+y)(x+y)(x+w)$.

Which of the above two methods gives the right answer (i.e., is the correct method)?

To complicate matters further, the answer key lists the answer to the question as (d)None, but I find the answer to be (c). Is the book's answer wrong? Or am I wrong?

# Answer
First, you need to describe all three of your options using a minimum amount of literals. To achieve this you will need to do the following (use basic boolean algebra laws):
Using the **Distributive Law** ($ A(B+C) = AB + AC$):

(a) $(w + x)y = wy + xy$
Option $b$ is already shown in its minimal form, so we can leave it like that:

(b) $xy + yw$
To minimize the form of option $c$, we will use a few laws:

Using the **Distributive Law** ($A+(BC)=(A+B)(A+C)$):

(c) $(w+x)$\**(w'+y)(x'+y)\** $=(w+x)$\**(y+w'x')\**

Next, we can see that $w+x$ is $(w'x')'$, by **De Morgan's Theorem**.
This allows us to use the law $A(A'+B)=AB$ (in our case, $w+x$ will be $A$ and $y$ will be $B$):

$(w+x)(y+w'x')=(w+x)y$
We see that (c) is the same expression as (a), and they both are the same as (b).
All 3 options are the same.
Now let us check if they are OK (they are OK if they implement the K-map).

For this we can minimize the given k-map. If it results in the same minimal expression - all 3 options are OK. If not, then all 3 are not OK.
xy \wz|00|01|11|10
00\____| 0 | X | 0 | 0
01\____| 0 | X | **1 | 1**
11\____| *1 | 1 | **1 | 1***
10\____| 0 | X | 0 | 0
The 4 **BOLD** cells are one group $=wy$
The 4 *ITALIC* cells (line 3) are another group $=xy$

Together: $wy+xy$

After minimizing the map we see that the expression that we got is the same expression as (a), (b) and (c) (since they are all the same).

This means that options a-c all implement the k-map.

So the correct answer must be d.

> **EDIT**
>
> When trying to group the cells, the groups need to be of the size 2 in the power of n (can be 1, 2, 4, 8...). You must always look for the biggest possible groups. (so the second option that you suggested would be wrong anyway - it is better to group 8 cells and not 4 and 4).
>
> Next, you tried to group '0's. You can only group '0's if you want the Maxterms. Only when you are looking for the POS (product of sums), aka CNF form. You are looking for the minterms (SOP). You need to choose cells that have the value '1' in them.
>
> About the 'x (called 'don't care'): If you have an 'x' placed in a cell next to cells that are '1', and that 'x' will help you make a bigger group - you use it.
> If the 'x' doesn't help you - you pretend that it is a '0'.
>
> So, if you have the row: 0 x 1 1 and all of the other cells are '0' - you only group the '1' and '1' (because the size of the group with 'x' is 3 - and it is not a power of 2 !).

Hope this helps :)
> 1 votes

# Answer
Let $$S = (w + x) (w' + y) (x' + y).$$

* if $y = 1$, then $S = (w + x)$;
* if $y = 0$, then $S = (w + x) w' x' = 0$.

Therefore, $S$ is equivalent to $(w+x) y$.
> 0 votes

---
Tags: logic, boolean-algebra, propositional-logic, karnaugh-map
---


title: Karnaugh map simplification

text:
# Question
Title: Karnaugh map simplification
I'm working through an example that looks like a fairly simple Karnaugh map and simplification, but I feel stupid that I can't seem to understand the correct answer.

**This is the map:**

**My groupings:**

This is the equation:

But I don't know how it simplifies to the correct answer here:

I understand why the NOT A goes outside of the bracket, but I don't see how the C OR NOT C just becomes a C inside the bracket?

# Answer
Check for solution. Grouping should be done using 2 quads
> 3 votes

# Answer
First, when you are trying to group, you must use the biggest possible group. A group's size has to be a power of 2 (1, 2, 4, 8...).

In this case you need to make 2 groups:

cells 4, 5, 12, 13: $A'D$
cells 8, 9, 12, 13: $A'C$

Represented as SOP: $A'D+A'C$

Using the Distributive Law:

$A'D+A'C=A'(C+D)$

---

About the way that you tried:

You grouped:

cells 4, 5: $A'C'D$
cells 8, 9, 12, 13: $A'C$

Assuming that you didn't notice the bigger grouping option, the expression that you have can still be simplified using Boolean Laws:

$A'C'D+A'C=A'(C'D+C)$ **Distributive Law**
According to one of the laws: $A+A'B=A+B$
So: $A'(C'D+C)=A'(C+D)$
> 1 votes

---
Tags: logic, boolean-algebra, karnaugh-map
---


# Question
Title: programs compatible with different processors
Ok, I've been told for years that during the old days, a program written on a certain machine would run only on that machine but now, programs run on multiple types of computers.

What does this really mean? I mean, does it mean that programs were written for certain instruction sets of the processor and would not run in different instruction sets? If so how did they overcome this problem?

Is it due to the standard x86, AMD64 or ARM architectures that most programs are written for these types of processors and they are abundant in the world?

Please enlighten this lost kid.

# Answer
> 3 votes
The intel line of processors (8086, x86) have backwards compatible instruction sets (i.e., unless you tell an x86 otherwise, it will behave like a 8086, and the 8086 instructions (and registers, etc) are just a subset of the x86 ones. Ditto for AMD64 (i.e., x86\_64), they are able to run x86 software as is. This for pragmatic compatibility reasons: buying the shiny, new machine with the latest processor, and having it run your extant software in a slow emulator is *not* a way to make new buyers. So the 80286 could run 8086 software (operating system and all), and so on up. You can install an 32 bit (x86) operating system on x86\_64 (64 bits) too.

ARM is a completely different kettle of fish, but also compatible (to an extent) along the line.

Besides, running software on some sort of virtual machine (Java Virtual Machine, .NET, ...) has advantages as the same "binary" runs on more platforms (simplifying the logistics of getting "the right version" to the user), today's processors are so ridiculously overpowered it doesn't make much of a difference for interactive applications. Besides, the Just In Time compilation technology has become the tool of choice, even rivaling native compiled binaries for some uses.

---
Tags: computer-architecture, software-engineering
---


# Question
Title: Does Heapsort work in time o(n log n) in the best case?
Is it possible for Heapsort to work in time $o(n\log n)$ on certain inputs?

For example in case of Insertion sort it is possible, however when it comes to Quickssort it is not possible. What about Heapsort? I tried to find an input array such that Heapsort will be working in $o(n\log n)$.

I ask you is it possible? Some permutation? The same elements?

# Answer
The paper: The Analysis of Heapsort by Schaffer and Sedgewick shows that

> Theorem 1: Heapsort requires that at least $\frac{1}{2} n \lg n - O(n)$ data moves for any heap composed of distinct keys.

and that

> Theorem 3: The *average* number of data moves required to Heapsort a random permutation of $n$ distinct keys is $\sim n \lg n$.

---

It also mentions that

> If equal keys are allowed, the best case is clearly linear \[3\]: consider the case of a heap with all keys equal.

The citation to \[3\] here is TechReport: On Heapsort and its Dependence on Input Data.
> 4 votes

---
Tags: algorithms, runtime-analysis, sorting, lower-bounds, heap-sort
---


# Question
Title: What are the advantages of cuckoo hashing over dynamic perfect hashing?
Dynamic perfect hash tables and cuckoo hash tables are two different data structures that support worst-case O(1) lookups and expected O(1)-time insertions and deletions. Both require O(n) auxiliary space and access to families of hash functions for their operations.

I think that both of these data structures are beautiful and brilliant in their own right, but I'm not sure I see how and when one of these would be preferable over the other.

Are there specific contexts in which one of these data structures has a clear advantage over the other? Or are they mostly interchangeable?

# Answer
In cuckoo hashing, lookups can be performed in parallel, while in Dietzfelbinger et al.'s original dynamic perfect hashing scheme, lookups require two chained memory accesses, in which the second access uses information retrieved from the first.
> 4 votes

# Answer
Dynamic perfect hashing in the sense of Dietzfelbinger et al. only needs 2-independent hashing. While there are some results on simple hashing for cuckoo hash tables, such as twisted tabulation hashing and "Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash", the original dynamic perfect hashing is more robust in some sense.
> 3 votes

# Answer
It is relatively easy to increase the space efficiency of cuckoo hashing by allowing each slot to hold more than one item. For slots of size 4, the space efficiency is something like 95%. That is to say, items can be inserted until 95% of the space in the table is used to hold items, not just places where items might go.

On the other hand, the bounds in the Dietzfelbinger et al. paper on dynamic perfect hashing only prove that insert operations can proceed as long as the table is no more than 3% full.
> 2 votes

# Answer
Cuckoo hashing uses $O(1)$ memory blocks at any one time and needs to free or reallocate memory rarely. Dynamic perfect hashing in the sense of Dietzfelbinger uses $O(n)$ memory blocks and will use more space in both internal and external fragmentation. There are ways to avoid this, but they add complexity to the algorithm.
> 1 votes

---
Tags: data-structures, hash-tables
---


title: DFAs as Categories

text:
# Question
Title: DFAs as Categories
I've been recently investigating metacategories (arrows and objects) alongside Automata theory and noticed that a category is a sort of parent container for DFAs, which are just a specific type of function over sets.

If the relationship between automata and categories is significant, does that mean an automata could encode type information in addition to its accepting duties?

# Answer
As David Richerby stated, you can make a category out of just about anything, so of course automata in their various forms are included. Googling "category of automata" will return results and Joseph Goguen used a category of automata as an example in his Categorical Manifesto. (He also did research on such categories.) That such categories exist makes no suggestion that there is any special relationship between automata and categories.

However... (one type of) a deterministic automaton is just a monoid action. You have your state space $S$ and a monoid of inputs $M$ (often the free monoid on some finite set, i.e. strings) and your transition function $t : M \times S \to S$. We want our $t$ to be equivariant, i.e. it respects the monoid structure on $M$. Formally, $t(1, s) = s$ and $t(mn, s) = t(n, t(m, s))$.

There's a particularly nice and fairly important categorical reformulation of this. We can view a monoid as a one object category, call it $C\_M$. The object isn't too important so let's just call it $\star$. The only hom set is $Hom(\star, \star) = M$ and composition is just the multiplication of the monoid. A monoid action is then just a functor $F : C\_M^{op} \to Set$. $F(\star) = S$ and $F(m)(s) = t(m, s)$. The functor laws guarantee equivariance.

Once we have this perspective, there are many directions we can go with it. We can change $Set$ to $Poset$ and talk about state machines with monotonically increasing states. (Or, you know, if we want *finite* state machines, use $FinSet$.) We can generalize $C\_M$ from a one object category to an arbitrary (small) category and have different state spaces as we transition which I think may be similar to what you were thinking about "types". We can recognize that we immediately have an entire category of state machines over $M$, namely the functor category $\[C\_M^{op}, Set\]$. We can further recognize that this is a presheaf category, a type of category of foundational importance in category theory. Presheaf categories also have a lot of structure for free; in particular, they're toposes so you can interpret a dependently type lambda calculus into them. This example is also an example of a Lawvere theory.

So, it turns out there are pretty profound connections between state machines and category theory. Of course, there are also profound connections between category theory and topology or order theory or metric spaces. This is part of what makes category theory so enticing.
> 6 votes

---
Tags: formal-languages, automata, category-theory
---


# Question
Title: two languages reducible to each other can belong to RE and recursive?
If two languages L1 and L2 both are reducible to each other in polynomial time then which of the following is false?

**A** L1 is decidable and L2 is undecidable.

**B** L1 is recursive and l2 is RE

**C** both

**D** none of these

I know that both need to belong to NP or NP hard if they are reducible to each other. simply solving one solves other.

If L1 is recursive then L2 also needs to be recursive. in context of P-NP if L1 is decidable and by doing extra polynomial work i can get Turing machine for L2 as well ans vice versa . why one is decidable and other is semi-decidable a true statement?

# Answer
Reductions are translations between computational problems. Reductions are used to define the concept of NP-hardness but that doesn't mean that every use of reductions has something to do with NP – analogously, you can translate between English and French but that doesn't mean that every piece of translation has something to do with French. In this case, there's no reason to assume that we're in the context of P vs NP: the question is in the context of computability theory (what functions can we compute?) not complexity theory (how much resources are required?).

For your question at the end, remember that every decidable language is semi-decidable.

I've no idea what the answer to the multi-choice question is, since it's so badly worded. Choosing "C", for example, would mean asserting that the statement "both" is false but "both" isn't a statement with a truth value.
> 3 votes

---
Tags: computability, undecidability
---


# Question
Title: If f(n) = Ω(n) and g(n) = O(f(n)), what do we know about g?
Let f(n) = Ω(n), and g(n) = O(f(n)).Then g(n) = \_______.

I thought of it this way, since f(n) is Ω(n),then f(n) belongs to the set of functions defined by Ω(n), ie,{n,$n^2$,$n^3$ ....}. So g(n) will change accordingly , ie , g(n) will be of complexity O(n),O($n^2$),O($n^3$) ...etc. Is it correct to directly substitute functional values into O(f(n)) to get a sense of the complexity?

# Answer
Knowing that $f(n)=\Omega(n)$ and $g(n)=O(f(n))$ doesn't tell you anything about $g(n)$. For all we know, $f(n)$ could be $2^{(2^{(2^n)})}$ and then $g(n)$ could be almost any function. All we know is it is upper bounded by some function, which might grow arbitrarily fast. It's akin to saying "up to 50% off or more".
> 7 votes

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


title: distributed alpha beta pruning

text:
# Question
Title: distributed alpha beta pruning
I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see below) are all quite old (1990 being the latest). I assume there have been many substantial advancements since then. What is the current standard in this field?

Also please point me to an idiot's explanation of DTS as I can't understand it from the research papers that I have read.

The algorithms mentioned above:

* PVS: Principle Variation Splitting
* YBWC: Young Brothers Wait Concept
* DTS: Dynamic Tree Splitting

are all are discussed here.

# Answer
yes the theory has advanced significantly and somewhat due to both the chess analysis literature and general parallel programming techniques. here are some newer refs on (chess) alpha beta pruning over distributed clusters/ parallelism. also some of the early distributed computing chess literature predates a lot of basic parallel design patterns and can be conceptualized within that framework.

the basic idea behind DTS is that search trees are distributed among computational nodes based on move/ layout complexity. unused processors that "finish early" can do additional work beyond an initial allocation which can be distributed as evenly as possible initially but will turn out to be uneven. hence its basically a kind of "load balancing" and "producer/ consumer" queue, or also similar to job scheduling.

> This idle processor broadcasts (using shared memory) that it is idle, and is available to "help" any other processor finish searching its tree. The busy processors collect the "state of the tree" data, and store it in shared memory for the idle processor to examine. This idle processor analyzes this data, and decides which (if any) of the busy processors seems to have a tree that is complicated enough that it would be efficient to help with the search. If such a position is found, the idle processor informs the processor which owns that node of this and they "join" forces.
> 3 votes

---
Tags: algorithms, distributed-systems, board-games
---


# Question
Title: Algorithm for storing polygon edges into grid
Is there any algorithm which takes edges (given by its two end points), and determines in which cell (or cells) of grid it is?

Grid has fixed dimensions and number of cells. Grid is represented by its cells with matrix. And every cell has list of edges that intersect that cell.

Input is set of pair points, but I can also transform it in just set of points, or any other needed representation. Output should be the mentioned grid with cells who contain list of edges that intersect that cell.

Algorithm should be fast and robust, and by that I mean it covers special (degenerated) cases and that its time complexity is good.

What I want to be able is to use that grid later for search, for example to answer me question like "Which cells does given edge AB(with end points A and B) intersect?" or "Give me all edges that intersect cell 12"(First row, second column).

# Answer
Bresenham's method is one possibility, however do be aware that as originally presented, it produces the best discrete approximation to the line, which isn't exactly what you want. You want the grid cells which *include* the polygon, which means that (say) left-edges should be rounded down and right-edges should be rounded up. Wu's algorithm effectively enumerates all of the cells which a line passes through, so it would probably be easier to modify that.

Do bear in mind that on a lot of modern CPUs, floating point arithmetic is extremely efficient compared with integer arithmetic, especially now that we have SIMD execution units. It can actually be more efficient in some cases since the register file and execution units for floating point are typically independent of those used for integer computations. Bresenham is still important, of course, but it's probably worth considering other methods.

Another algorithm that may be worth considering is Pineda's method, which is used by many (if not most) GPUs to scan-convert triangles into fragments. The question asked about polygon edges specifically, not the interior of polygons, but you might find some useful ideas there.

If raw speed is important, one advantage of Pineda's method is that you can enumerate which 4x4 cells the polygon touches, and then calculate individual grid entries in parallel using SIMD arithmetic. This should be very fast on modern hardware.
> 1 votes

# Answer
You can use line drawing algorithm like Bresenham.
The second question is just Bresenham in the loop, or simply discrete version of point on segment using discrete grid.
Bresenham algorithm presents very fast rasterization as it operates on integers - for sure faster than DDA and also works for vertical segments.
> 0 votes

---
Tags: reference-request, computational-geometry, search-algorithms
---


# Question
Title: How the website owner keep track of your times of access?
To be specific, I am using the online website of Strait Times News. It limits users to 30 articles to read per month. I just do not understand how do they know you are accessing? We use different IP each time we go online, don't we? Is there anyway to hack this?

# Answer
> 1 votes
I am not sure how this website keeps track but I can tell you the general flow how usual websites keep track of user's data.

If the you are registered user on the site it doesn't matter which ip you use it can be tracked easily. To be more specific when you read the complete article a tracker can be anywhere from page-end scroll to read-more button.

Edit1: Looks Like the website you are talking tracks user based on (article click+ip+ cookie) so it is easy just to choose new ip + incognito browsing to get 30 article limit each time.

---
Tags: computability, network-flow
---


# Question
Title: If a machine recognizes language L, can it also recognize L*?
This is a homework question. Suppose the only accept state is the start state. My rationale for this is that L\* is just the concatenations of L, so if all strings in L are accepted, then all strings in L\* will be accepted as well. One problem I see with this is that a machine can only accept one language, so it might be problematic...

# Answer
> 4 votes
> One problem I see with this is that a machine can only accept one language, so it might be problematic.

You are answering your own question: by definition¹, any given automaton accepts $L$ *and* $L^\*$ if and only if $L = L^\*$. This can happen -- examples include $L = \\{ \varepsilon \\}$ and $L = \Sigma^\*$, for instance, but not as a rule.

It is not clear from your question if you understand the acceptance criterion of finite automata. The automaton has to be in a final state *after reading the whole input*, not in the beginning or at any time.

---

1. The language accepted by automaton $A$ is uniquely defined to be the set of words $w$ for which $A(w)$ is (an) accepting (computation).

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


title: How do I find my wife in a supermarket?

text:
# Question
Title: How do I find my wife in a supermarket?
If two people are lost in a maze, is there an algorithm that they can both use to find each other *without* having previously agreed what algorithm they will be using?

I think there are some characteristics that this algorithm will have:

* Each person must be able to derive it using logic that makes no *assumptions* about what the other person is deciding, but as each person knows the other is in the same position they may make *deductions* about what the other *must* be deciding.
* An identical algorithm must be derived by both people as there is total symmetry in their situations (neither has any knowledge about the starting position of the other, and the maze is a fixed size, and fully mapped by both). Note that the algorithm is not required to be deterministic: it is allowed to be randomized.

# Answer
This is called *rendezvous problem*.

As the paper: Mobile Agent Rendezvous: A Survey mentioned, this problem is original proposed by Alpern: The Rendezvous Search Problem:

> Two astronauts land on a spherical body that is much larger than the detection radius (within which they can see each other). The body does not have fixed orientation in space, nor does it have an axis of rotation, so that no common notion of position or direction is available to the astronauts for coordination. Given unit walking speeds for both astronauts, how should they move about so as to minimize the expected meeting time T (before they come within the detection radius)?

In the survey paper above,

> ***Abstract:*** Recent results on the problem of mobile agent rendezvous on distributed networks are surveyed with an emphasis on outlining the various approaches taken by researchers in the theoretical computer science community.

It covers both "Asymmetric Rendezvous" (in Section 4) and "Symmetric Rendezvous" (in Section 5).

---

For symmetric rendezvous, the paper by Alpern shows:

> It is shown how symmetries in the search region may hinder the process by preventing coordination based on concepts such as north or clockwise.
> 19 votes

# Answer
Actually any consistent pre-arranged scheme will do.

For example:

1. Turn always left
2. If on a dead-end backtrack to previous turn and turn right
3. One will have to walk double the (pre-arranged) speed of the other (or in more number-theoretic terms, the speeds of the two agents should be relatively prime, or more generaly be linearly-independent).

Or even simpler

1. One agent stays in the same place
2. While the other uses a consistent scheme to explore the maze (e.g using an Ariadne's thread approach).
3. Eventualy, in finite time, they will meet.

This scheme will guarantee that the people will meet eventualy (but it might take some time)

Why? Because the scheme is consistent for both and does not lead either to a dead-end. So since the maze is finite and is connected, after a finite time they will meet.

If the scheme is not consistent, there is no guarantee they will meet since they can result in closed loops.

If they have the same speed then depending on the architecture of the maze, e.g a cyclic maze, then it is possible they can always be at anti-diametrical points of the maze, hence never meet, even though the scheme is consistent.

It is clear from the above that the scheme needs to be pre-arranged, but any consistent pre-arranged scheme will do.

Else one can rely on probabilistic analysis and infer that with a large probability they will meet, but this probability is not one (i.e under all cases).

One can also consider the converse of the *rendezvous problem*, the *avoidance problem* where the objective is for the agents to always *avoid each other*.

The solution to the avoidance problem is for the agents to reflect each other exactly. Meaning that what one agent does the other should do the reflection of that. Since the **avoidance problem also has a solution**, it is clear that strategies for the rendezvous problem that may lead to *reflection behaviour* of the agents, cannot guarantee solution.

One can say that the strategy for the avoidance problem is *parallelization* (ie maximum divergent point) whereas the strategy for the rendezvous problem is *orthogonality* (i.e least convergent point)

The above analysis can be turned into an randomised algorithm which does not assume pre-arranged roles for the agents, like the following:

1. Each agent throws a coin on which role to choose (e.g either staying in place or exploring the maze)
2. Then they proceed as described above.

This on average will lead to people eventually meeting, but is not guaranteed under all cases.

If we assume that the agents can *leave traces*, e.g labels of their (current) direction and speed. Then, the other agent, can use these traces as information to adjust both its own direction and speed (see below).

This kind of problem is an example of **global optimisation using only local information**. Or, in other words, a way to **map global constraints to local constraints**. This, more general, problem (which subsumes the rendezvous problem) is tackled in this math.se post (and references therein) "Methods to translate global constraints to local constraints"
> -1 votes

---
Tags: algorithms, search-algorithms, agent-based-computing
---


title: Shortest path in divisors graph

text:
# Question
Title: Shortest path in divisors graph
There is a graph with N vertices numbered from 1 to N. Edge between a and b exists if and only if a|b or b|a. If a|b then the weight of the edge is b/a. If b|a then the weight of the edge is a/b. Given two vertices u and v, I want to find the length of the shortest path between them. I think that the shortest path should pass through gcd(u, v) or lcm(u, v) (lowest common multiple), but I can't prove it. Can someone tell if my theorem is correct? If it is not correct, then how to solve this? It is not my homework.

# Answer
> 1 votes
> Given two vertices $u$ and $v$, I want to find the length of the shortest path between them. I think that the shortest path should pass through $\gcd(u, v)$ or $lcm(u, v)$ (lowest common multiple), but I can't prove it. Can someone tell if my theorem is correct?

I think the claim is not strictly true as written, and I will provide a counter-example.

---

First a claim: For any two vertices in this graph, there is a shortest path between them which uses only edges whose weight is a prime.

Pf: If the weight is not a prime, it can be factored, and this yields a different path between the same two vertices. The sum of any sequence of positive numbers all at least 2 is less than or equal to their product (trivial, by induction), so that is a shorter path, which can be substituted into the original in place of the non-prime edge.

(Note that a slightly stronger thing we could say is "shortest paths can only contain edges whose weight is a prime or is 4", proof left to reader.)

---

Now take two arbitrary non-prime coprime numbers, say, 6 = 2 * 3, and 35 = 5 * 7.

Clearly, a shortest path using only prime edges has at least 4 steps.

Also, we can ignore the possibility of a shortest path using edges corresponding to primes which are not {2, 3, 5, 7} -- by commutativity of multiplication, any such edges can be reordered until the end, without changing the weights of any of the edges, and the total effect of any such edges for primes which were not originally involved must be a loop, so in fact they could be skipped.

It follows (from this argument) that the shortest paths from 6 to 35 are in bijection with orderings of {2, 3, 5, 7}. They all have the same cost, which is 2 + 3 + 5 + 7.

Some of them pass through the lcm or gcd, but some do not. For instance, 6 -\> 2 -\> 10 -\> 70 -\> 35.

---

I think you can prove that there *is* a shortest path passing through the gcd? And there *is* a shortest path passing through the lcm?

---

I think the idea to prove that would be, look at the edges in the path, and look at which ones make the number larger, and which ones make the number smaller. Then rearrange the edges using commutativity of multiplication as before. If you sort it so that those that make the number larger come first, and then are followed by those that make the number smaller, then in the middle I think you pass through the lcm. If you sort it so that those that make the number smaller come first, then I think you pass through the gcd.

# Answer
> 0 votes
Let's assume u\<=v (otherwise interchange u and v).
1. u|v trivial u=gcd(u,v), v=lcm(u,v) (special case u=v)
2. gcd(u,v)=1 =\> path must go either via 1 or via u\*v=lcm(u,v)
3. gcd(u,v)=x =\> path analog to path from u/x to v/x (which is solved by 2.)

There always exists at least one shortest path going through gcd(u,v).
There exists at least one shortest path going through lcm(u,v) if lcm(u,v)\<=N.
There can exist shortest paths passing neither gcd nor lcm, e.g. u=2\*3,v=5\*7:

```
2*3->2->2*5->5->5*7
2*3->2->2*7->7->5*7
2*3->3->3*5->5->5*7
2*3->3->3*7->7->5*7

```

or u=4,v=9: `4->2->6->3->9`

---
Tags: graphs, combinatorics, number-theory
---


# Question
Title: Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular?
I was taught that if you can create a DFA to accept a language, then the grammar that is generating the language is regular.

**AND**

A DFA is a finite automata that accepts a language and also ***rejects*** the strings that aren't a part of the language.

It says if we replace $x$ with $c$ where $c \in \\{0,1\\}^+$, then $L$ is regular.

But the DFA should reject the string $abbaaaba$ since it doesn't fit the $wxw^R$ criteria and that isn't happening, so how is it regular?

# Answer
> 3 votes
In $\\{wxw^R|w,x\in\\{0,1\\}^+\\}$, we're free to choose $x$ to be any non-empty sequence, including all but the first and last characters of $wxw^R$. So we might as well limit $w$ to be a single symbol; it won't change anything.

So $L$ is exactly the same as $L' = \\{axa|a\in\\{0,1\\}\land x\in\\{0,1\\}^+\\}$ which is evidently regular.

---

Here's a more formal proof, in case the above was too telegraphic. Suppose we have

$$L = \\{wxw^R|w,x\in\\{0,1\\}^+\\}$$

Now:

$$\\{0,1\\}^+ \equiv \\{0,1\\} \cup \\{aw | a \in \\{0,1\\} \land w \in \\{0,1\\}^+$$

which just says that $w^+$ is either exactly one symbol or one symbol concatenated with $w^+$. Also observe that if $a$ is a symbol and $w$ is a sequence of symbols, then $a^R\equiv a$ and $(aw)^R\equiv w^Ra$. So we can rewrite $L$ as a union:

$$L = \\{axa|a\in\\{0,1\\}\land x\in\\{0,1\\}^+\\} \cup \\{awxw^Ra|a\in\\{0,1\\}\land w,x\in\\{0,1\\}^+\\}$$

Now, looking at the two sets in that union, we can see that

$$\\{awxw^Ra|a\in\\{0,1\\}\land w,x\in\\{0,1\\}^+\\} \subset \\{axa|a\in\\{0,1\\}\land x\in\\{0,1\\}^+\\}$$

because

$$\\{wxw^R|w,x\in\\{0,1\\}^+\\} \subset \\{0,1\\}^+$$

and since for any sets $A$ and $B$

$$B \subset A \implies A = A \cup B$$

We can simplify the definition of $L$ to

$$L = \\{axa|a\in\\{0,1\\}\land x\in\\{0,1\\}^+\\}$$

which is clearly a regular language.

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


# Question
Title: What is the running time of this recursive algorithm?
I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037.

This is my proposed solution to compute the $n$th value:

```
a n | n<1        = 0
    | n<3        = 1
    | otherwise  = head (goods n)

goods n = [x | x <- [1..], isGood x n]

isGood x n = and [ x - a(n-k) /= a(n-k) - a(n-k-k) || a(n-k-k) == 0 | k <- [1..n] ]

```

Note that Haskell does not automatically cache or memoize these values.

The OEIS page for the sequence gives the fact that $a(n) \leq (n+1)/2$, so the `[1..]` could be replaced by `[1..(n+1)/2]`, as the algorithm will never reach an $x$ greater than $\frac{n+1}{2}$.

Attempting to count function calls, I derived the following upper bound $T(n)$, the number of function calls that the algorithm takes for an input $n$:

$$ \begin{align} T(n) &= \sum\_{x=1}^{(n+1)/{2}} \sum\_{k=1}^{n} 2~T(n-k) + 2~T(n-2 k) \\ &\leq \sum\_{x=1}^{(n+1)/{2}} \sum\_{k=1}^{n} ~T(n-k)\\ &\leq \sum\_{x=1}^{(n+1)/{2}} \sum\_{k=1}^{n} 4~T(n-1)\\ &\leq \sum\_{x=1}^{(n+1)/{2}} 4~n~T(n-1)\\ &\leq 4~n~T(n-1)~\frac{n+1}{2}\\ &\leq 2~n~(n+1)~T(n-1) ) \end{align}$$

I plugged the final formula into Mathematica:

```
RSolve[{T[n] == 2*T[n - 1]*n*(n + 1), T[1] == 1}, T[n], n]

```

And got, after a little simplification: $T(n) \leq ~2^n~n!~(n + 1)!$

The average ratio between this and the Haskell program execution time, for $n \in \[12,20\]$ is $2.0 \cdot 10^{39}$ and the standard deviation of the ratios is around $6.0 \cdot 10^{39}$. (Curiously enough, the log plot of the ratios appears to be a straight line).

The ratios with the first line, defining $T(n)$, have a mean and standard deviation of $4.8 \cdot 10^6$ and $1.8 \cdot 10^6$, respectively, but its plot jumps around a lot.

**How can I get a better bound on the time complexity of this algorithm?**

Here is the algorithm in valid C (minus forward declarations), which I believe is roughly equivalent to the Haskell code:

```
int a(int n){
    if (n < 1) {
        return 0;
    } else if (n < 3) {
        return 1;
    } else {
        return lowestValid(n);
    }
}

int lowestValid(int n){
    int possible = 1; // Without checking, we know that this will not exceed (n+1)/2

    while (notGood(possible, n)) {
        possible++;
    }
    return possible;
}

int notGood(int possible, int n){
    int k = 1;

    while (k <= n) {
        if ( ((possible - a(n-k)) == (a(n-k) - a(n-2*k))) && (a(n-2*k) != 0) ) {
            return 1;
        } else {
            k++;
        }
    }
    return 0;
}

```

The C version takes about 5 minutes to compute $a(17)$ and the Haskell version takes about the same for $a(19)$.

The first times of the versions:

```
Haskell: [0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0e-2,3.0e-2,9.0e-2,0.34,1.42,11.77,71.68,184.37,1815.91]
C:       [2.0e-6, 1.0e-6, 1.0e-6, 2.0e-6, 1.0e-6, 6.0e-6, 0.00003,0.00027, 0.002209, 0.005127, 0.016665, 0.080549, 0.243611, 0.821537, 4.56265, 24.2044, 272.212]

```

# Answer
You can write your recurrence as $$ T(n) = (n+1)(T(n-1) + 2T(n-2) + T(n-3) + 2T(n-4) + \cdots). $$ In particular, $T(n) \geq (n+1) T(n-1)$. This means that the sequence $T(n)$ grows very rapidly, and in particular $$ T(n-1) + 2T(n-2) + \cdots \leq T(n-1) \left\[ 1 + \frac{2}{n} + \frac{1}{n(n-1)} + \frac{2}{n(n-1)(n-2)} + \cdots \right\] = (1+O(1/n)) T(n-1). $$ Therefore $$ T(n) \leq (n+O(1)) T(n-1). $$ This means that $$ T(n) = O((n+O(1))!), $$ and so $$ T(n) = O\left(n^{O(1)} (n/e)^n\right). $$ This improves on your bound by a square root.
> 3 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation, recursion
---


# Question
Title: What is this question asking for?-->Test this code, find an error in the program and "construct an instance to demonstrate the error" (in C)
I am learning the basics of the language C, and so far we have covered up to loops. This question is related to my assignment. The problem is I do not understand what the question is asking.

I know the error in the code, but I don't understand what this question is asking me to do? What is an instance? Am I supposed to make a different piece of code? Because I am pretty sure the error is a semantic one(knowledge based rather than syntax). Here is the code anyways just for context:

# Answer
> 2 votes
As noted by Tom van der Zanden in a comment, and given you already know what's wrong with the code, think of an input that will cause the program to fail, just run the program with that input and you have your instance. Does it make more sense if you think of the phrase, "for instance"?

You may be overthinking it (a good sign actually), if this is just a very basic C language course, they are probably being rather obvious in what they are asking for.

KISS -- Keep It Simple, Sailor

---
Tags: c
---


title: Determining states in a DFA

text:
# Question
Title: Determining states in a DFA
In computational theory for deterministic finite automata, there is a 5-tuple representation containing $Q$, $\Sigma$, $\Delta$, $Q\_0$ and $F$. I am wondering how one understands thinking about the number of states to construct such a DFA.

Example:

$$\\{w \in\\{0,1\\}^\*\mid w\text{ contains at least two $0$s but does not contain }000\\}\\,.$$

In the solution, there are 7 states required, $(q\_0, q\_1, ..., q\_7)$.

How should one typically begin understanding the sequence in which they write their states to then cross $\Sigma$ and $Q$ to find the transitions?

# Answer
Here is one way of thinking about it. You are receiving a sequence of zeros and ones. At each moment the sequence might stop and you need to decide to accept or reject the resulting word. At each point in time, think about what properties of the sequence you need to remember to decide whether to accept a word or reject it. The number of these properties is a proxy for the number of states. The properties also suggest descriptive names of states.

For this problem, you need to know if you have seen exactly one zero, at least two zeros, and if you have seen three consecutive zeros. In case you have seen exactly one zero, you need to know if it is the last character (this gives 2 states). In case you have seen at least two zeros you need to remember the last two characters of the string (this gives 4 states, in principle, but in this case two can be combined for a total of 3). You need to remember if you have seen 3 consecutive zeros (1 more state). You also need a start state for a total of 1 (start) + 2 + 3 + 1 = 7 states.

So you can describe a state by a tuple (a,b), where a is 1 if you've seen exactly one zero so far, and 2 if you have seen at least two zeros, and b indicates the last bits you've seen. You can have the following states:

(0,\*) - haven't seen any zeros yet, aka start state

(1,0) - have seen one zero and it is the last character of the string

(1,1) - have seen one zero, but it was some time before, it is no longer the last character

(2,00) - have seen at least 2 zeros, and the last two characters are zeros - DANGER - one more zero and I need to reject

(2,10) - have seen at least 2 zeros, and the last two characters are 10 - we are relatively safe, because we need to see 2 zeros before we decide to reject

(2,\*1) - have seen at least 2 zeros, and the very last character is 1 - we are quite safe, we'll have to see 3 zeros before we decide to reject.

All the above states are assuming you have not seen three consecutive zeros. Of course, once you decide to reject due to three consecutive zeros, you always reject - this gives one more state.
> 4 votes

# Answer
The simplest way to solve this, perhaps with more than the minimum number of states, is to use the product construction:

1. Come up with an automaton that accepts all words containing at least two 0s. You can do this with 3 states.
2. Come up with an automaton that accepts all words not containing the substring 000. You can do this with 4 states. (If you find this difficult, first construct an automaton that accepts all words containing the substring 000.)

(All automata are deterministic.)

Applying the product construction, we get an automaton with 12 states. Some of its states will be unreachable, however, and some of them will be clearly equivalent. This way you can reduce the number of states, perhaps all the way to the 7 states in the solution.
> 2 votes

---
Tags: automata, proof-techniques, dfa
---


# Question
Title: Efficient algorithm to generate undirected graph edges from 3D distribution of nodes based on distance
I have a set of nodes where each node $n\_i$ is associated with a cartesian coordinate $\vec r\_i$ and a radius $\sigma\_i$. I want to generate a graph data structure where nodes $n\_i$ and $n\_j$ are connected by an undirected edge if $|r\_{ij}| \< \sigma\_i + \sigma\_j$. This is not my field and I am interested in efficient algorithm/workflow/software suggestions. I am working in C++.

# Answer
> 0 votes
This is the intersection graph of a set of spheres. The case of 2D disks, all of the same size, is well-studied; its intersection graph is known as a unit disk graph, and it has been studied in some depth in the literature. I don't know if your case has been studied in the literature, but those are some search terms you could use to try to find related work.

---
Tags: graphs
---


title: Proof that this problem is in NP

text:
# Question
Title: Proof that this problem is in NP
I have to prove the following problem is in NP (and define verifier as well as the certificate/witness):

The input is a set of $n$ boxes with weights $w\_{1},\ldots,w\_{n}$ and two numbers $s$ and $t$ (all natural numbers). Can the boxes be loaded onto $s$ trucks if each truck can only carry a total weight of $t$?

Apparently this is supposed to be easy, but I'm stuck.

# Answer
> 3 votes
Once you get the hang of these, they are quite easy, so the first thing is not to over think things.

To prove containment in NP (in this manner) you need (as you mention):

1. A *witness*. This is just a "string" that proves an instance is a Yes-instance. So it can just be the solution. When we say "string", typically we don't define how the string is encoded, or even really that the witness is a string. What we give is a format for a solution.
2. A *verifier*. This is a Turing Machine that takes a witness (hence why the witness is a string, formally) and the original input, and checks that the witness is correct. So really the verifier is a set of steps to perform this check, given a witness in the correct format. For NP, we have the additional restriction that the verifier has to run in *deterministic* polynomial time.

So for this problem we can represent a solution as a collection of sets of boxes. We can assume that the boxes have a unique ID. This is the witness. You should, to cement this, try to write done a more precise format for this.

The verifier then should take such a string and check the following:

1. There are at most $s$ sets (or exactly, depending on the exact problem specification).
2. That each box appears exactly once, somewhere.
3. That the total weight of each set is at most $t$.

It should, hopefully, be clear that this verifiers that the solution is correct. The only thing that remains to do, is show that the verifier runs in deterministic polynomial time. Again this should hopefully be fairly clear. Even if we do each step separately, it's three passes over the list (we can, for convenience, assume that the verifier is a multitape machine, so we can more easily represent data structures), and this is certainly polynomial.

---
Tags: complexity-theory, np
---


title: Finding a certain prefix of a string

text:
# Question
Title: Finding a certain prefix of a string
Let $\Sigma = \\{ \sigma\_1 , ..., \sigma\_t \\}$ and let $S$ be a string from $\Sigma^\*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the **shortest** prefix $T$ of $S$ such that $S$ is a prefix of $T^n$ ($T^n= T \cdot .... \cdot T$, $n$ times).

I tried to build the suffix tree for $S$, and then checking each node, by their levels - from lowest level to top level, because then the corresponding prefix will be shortest at the lowest level of the suffix tree and will get longer - and then for each node checking if this property applies for the prefix of the current suffix node I'm looking at, but that would not necessarily give me the shortest prefix, because the suffix tree may have on the same level different lengths suffices.

I'm not sure as to how I'll be able to find the shortest prefix $T$? Perhaps there is a different way of using a suffix tree?

Or maybe there is a way to solve this efficiently without using suffix trees at all?

# Answer
> *Repetitions and periods in strings constitute one of the most fundamental areas of string combinatorics.*1

The shortest prefix T of S where,

$S = T^k.Q , s.t: k\>= 1, Q =$ some prefix of T, then |T| is called the period of string.

> *We say that string w has period p if w\[i\] = w\[i + p\]* 1

Conventionally, finding T can be done by the Knuth–Morris–Pratt algorithm as well as Boyer–Moore string search algorithm.

Proving the correctness is beyond the scope of this answer.(More precisely, beyond my scope). See 1 for a better idea.

---

Before I came to know this, I attempted to solve this using KMP. And later, luckily, others have confirmed it. This could be helpful if one is wondering how could one possibly get an idea that KMP would work. I first tried to figure out the pattern and thought KMP could do the job.

Wondering how ? Our aim is to make $S$ a prefix of $T^n$ i.e. $TT \cdot .... \cdot T$, $n$ times. You can see that T is repeating itself, so, should some prefix of $S$ too.

E.g. take $S = abc$, the only way you can have $TTT$ and $S$ as a prefix of $TTT$ ($T^3$) is if $T = abc$, then $abc$ is a prefix of $abcabcabc$. The minimum part which is repeating is the complete string $abc$. Hence, $T = abc$.

But, if $S = aba$, then $T$ can be $ab$, and $aba$ is a prefix of $TTT$ i.e. $ababab$. The minimum part which is repeating is just the string $ab$. Hence, $T = ab$.

You're roughly getting the idea that finding that part of prefix of $S$, where it is repeating itself in the rest of $S$ and ending with some part of it.

Final e.g. would be $S = abababa$, then again $T$ would remain $ab$, i.e, the prefix which is getting repeated and ending with some part of it. We could form $S$ as $T^k.Q: s.t. k \>= 1, Q =$ some prefix of $T$, here $a$.

Now your job is pretty easy. For every prefix in $S$, check if it is present in the rest of $S$ as described above. The shortest one you find would be the answer.

KMP has an essential part called "Prefix Function". Below is the code for the Prefix function in C / C++. When I ran it over a couple of strings S, I found good results.

```
void make_prefix_fun(char pat[], int a[], int m){
    // i is moving forward, and j is staying behind.
    a[0] = 0 ;
    for ( int i = 1, j = 0 ; i < m ; i++ ){
        while ( pat[j] != pat[i] && j > 0 )
            j = a[j-1];
        if ( pat[j] == pat[i] )
            j++;
        a[i] = j;
    }
}

Sample Cases:
aba
a b a
0 0 1
//  ^ T = S[1..(|S| - 1)]

adbashdbhabsjd
a d b a s h d b h a b s j d
0 0 0 1 0 0 0 0 0 1 0 0 0 0
// T is the complete S    ^

abcdabcda
a b c d a b c d a
0 0 0 0 1 2 3 4 5
//              ^. T = S[1..(|S| - 5)]
// Cool. Found something here.

abababababababababa
a b a b a b a b a b a b a b a b a b a
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// Cool. Found something here.              ^. T = S[1..(|S| - 17)]

abababababababababaaaa
a b a b a b a b a b a b a b a b a b a a a a
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 1 1
// Working exactly as expected.                   ^

```

Found a pattern? Yes, we do.

If you **observe the array**, after the first couple of consecutive 0s,

* **if** we get the series, 1,2,3...x strictly upto the end, we can have our T = S\[1..(|S| - x)\] and the length of your required T is N - a\[N\] where N = |S|.
* **else** T = entire string S.

**The required T is the longest prefix of S, which is repeating itself in S, and S ends with some prefix of T or in other words T = S\[1...|T|\], where |T| is called the period of the string.**

---

References:

1 - *Repetitions in strings: algorithms and combinatorics*, Crochemore et al.

Credits:

devnum, Mihai Calancea, Hendrik Jan.
> 1 votes

---
Tags: algorithms, optimization, strings, substrings, suffix-trees
---


# Question
Title: In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity?
It is well-known that there is an asymptotic lower bound of $nlogn$ for comparison sorting. However, I am wondering what is the fastest known algorithm for comparison sorting, in terms of the multiplicative constant?

# Answer
> 1 votes
The "multiplicative constant" is quite a bit more complex, the real average time for e.g. quicksort is $a n \log n + b \log n + c n + d$ for some constants that depend on the exact cost of comparisons (and thus the layout of the elements), memory access (again, data layout related), machine architecture, how smart the compiler is, ...

To get real average time, you need to know the distribution of possible inputs. Most analysis is done assuming all possible inputs are equally likely, but some experiments have shown that sorted (or almost sorted) data is very likely. In that case, it turns out lowly insertion sort beats all, at $O(n)$.

Do you worry about worst time? Sorry, you can't grab the on average fastest quicksort, and have to fall back on much, much slower heapsort or mergesort variants.

If you want a complete answer to your question, go check Knuth's "The Art of Computer Programming", volume 3 (Sorting and Searching). Some 800 pages of heavy going math for your enjoyment.

---
Tags: algorithms, reference-request, sorting, efficiency
---


title: Random sampling of tuples

text:
# Question
Title: Random sampling of tuples
When I talked with students about pseudo-random number generation, I mentioned that you should not blindly use subsequent outputs of a pseudo-random number generator (PRNG) to form tuples as they may not be uniformly random then; a famous example is RANDU.

The natural follow-up question is: what *do* you do? I can imagine several strategies.

1. Choose a PRNG that you know works well for $k$-tuples and sample $(\leq k)$-tuples by using subsequent numbers as components.

I assume that $k \leq 5$ is probably covered, but are there any for arbitrary $k$?
2. Use $k$ different PRNGs (different algorithms and/or different seeds) and draw the $i$th component from the $i$th one.

I seem to remember that mixing PRNGs is not a good idea.
3. If the domain of your PRNG is big enough, use bits $i,k+i,2k+i, \dots$ for the $i$th component.

Seems sound and is probably the method of choice assumign real $U(0,1)$-numbers, but does not scale given finite resolution/domains in practice.
4. Use a bijection from the domain of your PRNG to the $k$-dimensional space you want to sample from, e.g. a generalized version of Cantor's pairing function.

The sizes of the resp. domains can become a problem here a well.

None of the approaches seems entirely reasonable. So what is the state of the art? What advice would you give a person who needs to sample uniformly random tuples?

# Answer
Using consecutive outputs from the PRNG to form a tuple is fine if you use a good enough PRNG. So, one reasonable approach is to simply use a good PRNG, and then not waste brain power worrying about issues like this.

One way to get a "good enough" PRNG is to use a cryptographic-quality PRNG.

RANDU is a truly lousy PRNG (for instance, the least significant bit of its output is not random at all), so no surprise that all sorts of bad things happen when you use its output. But the root cause there is not using tuples from RANDU; the root cause is using RANDU.
> 3 votes

# Answer
The *spectral test* can be used to check if a given linear-congruential PRNG is suitable for sampling $T$-tuples \[1, sec. 3.3.4\].

> The most important randomness criteria seem to rely on properties of the joint distribution of $T$ consecutive elements of the sequence, and the spectral test deals directly with this distribution.

Algorithm S \[1, pp101\] is too long to reasonably reproduce here, let alone the theory behind it. According to Knuth, it is not quite feasible for $T \geq 9$ (the constant may be different today) because an exhaustive search causes a running time in $\Omega(3^T)$.

So if the distributional properties of a PRNG w.r.t. tuples are *really* important to you, there are ways to check for them. Knuth later references the work of H. Niederreiter, which seems to contain tests for other kinds of generators.

---

1. Seminumerical Algorithms by D.E. Knuth (TAoCP vol. 2; 3rd ed; 1998)
> 0 votes

---
Tags: reference-request, randomness, sampling, pseudo-random-generators
---


# Question
Title: Randomized and Deterministic Communication Complexity of a function
I have a problem I'm trying to answer for my homework. The question is:

Let $p$ be a prime number and let $GF(p)$ denote the finite field of size $p$. Suppose that A has input $x∈GF(p)$ encoded with $⌈log2p⌉$ bits and B has input $y∈GF(p)$ encoded with $⌈log2p⌉$ bits. Let $f:GF(p)×GF(p)→\\{0,1\\}$ be the function defined as $$ f(x,y)= \begin{cases} 0& \text{if}& x+y+xy=0\\ 1& \text{if}& x+y+xy≠0 \end{cases} $$ for all $x,y∈GF(p)$. Show that the randomized communication complexity of $f$ is $O(log\text{ } log\text{ } p)$ bits. Can you prove a lower bound on the deterministic communication complexity of $f$?

I've been thinking about using a random element $r∈GF(p)$ and make A calculate $f$ using $x$ and $r$ and sending the answer $r$ to B, but this doesn't seem to work as there are no general trend using such an protocol. For example that when A and B get the same answer, the function is $0$ or if they get different answers, the function is $1$.

Anyone have any idea how this protocol can look like? For example what kind of random input should be used?

# Answer
> 2 votes
Hint: The condition $x + y + xy = 0$ is equivalent to the condition $1 + x + y + xy = 1$, i.e. $(1 + x)(1 + y) = 1$, or in other words, $$ (1+x)^{-1} = 1+y. $$

---
Tags: complexity-classes, communication-complexity, protocols
---


# Question
Title: Efficient algorithm for 'unsumming' a set of sums
Given a multiset of natural numbers X, consider the set of all possible sums:

$$\textrm{sums}(X)= \left\\{ \sum\_{i \in A} i \\,|\\, A \subseteq X \right\\}$$

For example, $\textrm{sums}(\left\\{1,5\right\\}) = \left\\{0, 1, 5, 6\right\\}$ while $\textrm{sums}(\left\\{1,1\right\\}) = \left\\{0, 1, 2\right\\}$.

**What is the most efficient algorithm for calculating the inverse operation** (measured in terms of the size of the input set of sums)? Specifically is it possible to efficiently calculate any of the following:

1. Whether a given set is a valid set of sums. (For example, $\left\\{0,1,2\right\\}$ is valid but $\left\\{0,1,3\right\\}$ is not.)
2. A multiset that sums to the given set.
3. The *smallest* multiset that sums to the given set. (For example, $\left\\{1,2\right\\}$ and $\left\\{1,1,1\right\\}$ both sum to $\left\\{0,1,2,3\right\\}$ but the former is smaller.)

# Answer
# Solution

Solution has two parts. First we discover minimal set, then we prove that it can represent the power sum set. The solution is adjusted for programming implementation.

## Minimal set algorithm

1. Find maximal element $a\_{m}$ from the sum (multi)set. $P$, the potential minimal (multi)set is initially empty.
2. Unless there is only one group, represent $a\_{m}$ in all possible ways as a pair of sums that add up to $a\_{m}$, $S\_{ij}=\\{(a\_{i},a\_{j})|a\_{i}+a\_{j}=a\_{m}\\}$
3. Check that all elements from the set of sums are included.
4. Find maximal element $a\_{s}$ from all $S\_{ij}$ (meaning together) with the following property: for each $S\_{ij}$, $a\_{s}$ is either in $S\_{ij}$, or we can find $a\_{p}$ from the set of sums so that $a\_{p}+a\_{s}$ is in $S\_{ij}$.
5. If it is the case that $S\_{ij}$ does not contain $a\_{s}$, just the sum $a\_{s}+a\_{p}$, remove $a\_{p}+a\_{s}$ from $S\_{ij}$ (or just set a mark to ignore it) and insert $a\_{p}$ and $a\_{s}$ in $S\_{ij}$ instead.
6. If an element is present in every $S\_{ij}$ remove it from all $S\_{ij}$ once (or just set a mark to ignore it and not to touch it any longer) and add it to the list of elements of potential minimal set $P$.
7. Repeat until all $S\_{ij}$ are empty
8. If some of $S\_{ij}$ remains non-empty and we cannot continue, try again with the maximum value from all $S\_{ij}$.
9. Recreate the recursive steps without removals and continue with power set coverage algorithm over $P$. (Before this, you can make a safe-check that $P$ includes all elements that cannot be represented as a sum of two elements so they must be in underlying set for sure. For example, the minimal element must be in $P$.)

(10. Observe that a minimal set solution which is the goal of the algorithm cannot contain more than one repetition of the same number.)

Example:

$$\\{2,3,5,7,8,10,12,13,15\\}$$

Represent 15 in all possible ways as a sum of two numbers from the set of sums.

$$(13,2),(12,3),(10,5),(8,7)$$

Try to find maximal number that is in all groups or that can be represented as a sum. Obviously we can start searching for it from 8, there is no point going above it.

13 from the first group is 13=8+5 so 13 is fine, but 12 from the second group is not fine since there is no 4 to make 12=8+4 in the set of sums. Next we try with 7. But immediately 13 cannot be covered, there is no 6.

Next we try 5. 13=5+8, 12=5+7, 10=5+5, and for the last either 8=5+3 or 7=5+2 but not both. The groups are now:

$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$

5 is repeating in all groups so we extract it $P=\\{5\\}$. We extract 5 only once from each group.

$$(8,2),(7,3),(5,5),(3,7)$$

Obviously there is no point going higher than 5 so we try 5 again. 8=5+3, 7=5+2, so all is fine

$$((5,3),2),((5,2),3),(5,5),(3,(5,2))$$

Extract one 5 again from all groups since it is repeating. (This is not common but our case is deliberately created to display what to do in case we have repetitions.) $P=\\{5,5\\}$

$$(3,2),(2,3),(5),(3,2)$$

Now we try with 3 and have 5=3+2. Add it to the group.

$$(3,2),(2,3),(3,2),(3,2)$$

Now extract 3 and 2 since they are repeating everywhere and we are fine $P=\\{5,5,3,2\\}$ and the groups are empty.

$$(),(),(),()$$

Now, we need to recreate recursive steps without removals, this simply means doing the above without really removing the elements from $S\_{ij}$ just placing them in $P$ and marking not to alter it any longer.

$$(13,2),(12,3),(10,5),(8,7)$$ $$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$ $$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

## Power set coverage

The purpose of this part is to check if the found minimal set is able to cover the power sum set. It is possible that a found solution can cover all given sums, but that they are not power set sums. (Technically, you could simply create a power sum set from the found minimal set and check if each sum, as power set dictates, is in the initial sum set. This is all that just merged with what we already have, so nothing is wasted. You can do this part while rewinding the recursion.)

1. Encode all elements from the minimal set using successive powers of 2. The order is not important. Encode the same element with a new value as many times as it is repeating. Start from C=1, every next element has C=2C.

$$(2=\[1\],3=\[2\],5=\[4\],5=\[8\])$$

2. Replace the elements in the restored recursion list,

$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

with the encoding: 2 with 1, 3 with 2, 5 with 4, and another 5 with 8. Observe that each element has different encoding even though they are repeated.

$$((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))$$

3. Collect all intermediate sums, at the moment we have (1,2,4,8)

$$((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))$$

Intermediate sums $(1,2,3,4,5,8,9,10)$

$$((14),1),((13),2),((7),8),(15)$$

Intermediate sums $(1,2,3,4,5,8,9,10,13,14,15)$

$$\\{(15),(15),(15),(15)\\}$$

4. Check that the result is $2^m-1$, where $m$ is the number of elements in the solution, in the example $m=4$
5. Collect missing numbers from $1$ to $2^m-1$ in the intermediate sum list

$(6,7,11,12)$

6. Justify their absence in the following manner: represent each number in binary form

$(6=0110\_2)$ $(7=0111\_2)$ $(11=1011\_2)$ $(12=1010\_2)$

$6$ represents the sum of 3+5 since $0110\_2$ is covering second and third element from $(2=\[1\],3=\[2\],5=\[4\],5=\[8\])$. The sum of these elements, 8, is listed in the initial sum list $\\{2,3,5,7,8,10,12,13,15\\}$, so all is fine.

$7$ represents the sum of 2+3+5 since $0111\_2$ is covering first three elements from $(2=\[1\],3=\[2\],5=\[4\],5=\[8\])$. The sum of these elements, 10, is listed in the initial sum list so all is fine.

$11$ is 2+3+5, and 10 is in the list. $12$ is 3+5, and 8 is in the list.

If any binary representation corresponds to the sum that cannot be found, report that there is no solution.

So all is fine and $(2,3,5,5)$ is the solution. It is the minimal solution as well.

# Discussion

It was necessary to provide the algorithm that is going to check if the sums cover the power set completion, which is what is hidden in the binary expansion. For example if we exclude 8 and 7 from the initial example, the first part would still provide the solution, only the second part would report missing combinations of sums.

First part of discovering the possible minimal set is $mnlog(m)$ which comes to $m\log^2(m)$: we are looking around $m$ elements $n$ times having one $\log(m)$ binary search.

The last part is done in recursion return and it does not require any special effort, we are searching over less than $m$ elements, we need binary form which is $\log{m}$ and we have one addition and search if the sum is in the list, so together it is again about $m\log^2(m)$.

If we assume that the number of elements in the power sum set corresponds to the number of partitions of the largest element in the underlying set then the complexity is around $m\log^3(m)$. Any of the two justifies the initial sorting in order to find the largest element.

Parts of the algorithm assume that we can find the pair of sums in linear time and this requires sorting.

### Incorrect start

First part of the algorithm may fail, if we have started it on the wrong foot. For example $2,3,4,5,6,7,8,9,10,11,12,13,15$ has the basic solution $2,3,4,6$ which you get if you start algorithm from 6. However we can start our algorithm from 7, since there is nothing in step 4. that would say not to, and lock ourselves in, the algorithm cannot end properly. The reason is that 7 is 7=4+3 and 4 and 3 are in the solution. So locked algorithm does not always mean that there is no solution, just to try again with lower initial value. In that case, some ideas about the possible values are hidden within remaining $S\_{ij}$. That is why we suggested starting from there in case of failure.

Another example, if you miss and start algorithm from 5, you would get $5,4,3,3$ but this one does not include 2.

Notice that this algorithm is not going to give a derived solutions like $2,2,3,4,4$, which we got simply by turning 6 into 4 and 2 in the solution $2,3,4,6$. There are special rules that cover these versions.

The purpose of this algorithm is to provide a solution once we have started it all correctly.

### Improvements

Step 4. is the one that could be upgraded in this manner: instead of maximal we could try out every element in descending order that satisfies the given condition. We create a separate branch for each. If some branch does not give a solution, cancel it.

For example for $2,3,4,5,6,7,8,9,10,11,12,13,15$ we could try in the first round $7,6,5,4$ in separate ways since all of them are passing the first test. (There is no reason to use 2 or 3 since we know they have to be in the underlying set.) and simply continue that way all around until we collect all versions that can reach the end. This would create a full-coverage solution which would discover more than one underlying set.

Another thing, since we know that we cannot have more than one repetition if the case is minimal, we can incorporate this in our algorithm.

Overall, the condition in step 4. that a number must repeat in every group or have ability to create a sum is strong enough to get us out of direct exponential waters, which would be an algorithm of simply trying out every combination and creating the power set over each until we find a match.
> 9 votes

# Answer
NOTE: This does not quite work in general, see Uri's counterexample below.

One way of achieving at least 1. and 2. for a given set $Y$ (minimality requires a bit of tweaking) is (sorting $Y$ first, if necessary):

* Check whether $0\in Y$. If not, there is no solution.
* Let $y$ be the smallest positive number in $Y$. Then $y$ must also be in $X$, if it exists (otherwise it would be the sum of smaller positive numbers, which would also occur in $Y$).
* Let $z\_1\<\dots\<z\_n$ be the remaining members of $Y$. We will try to find a set $Y'$ such that $Y = Y' + \\{0,y\\}$. Obviously $0$ must be in $Y'$. For $i=1,\dots,n$: if $z\_i+y\in Y$, add $z\_i$ to $Y'$; otherwise, if $z\_i-y\notin Y$, there is no solution; otherwise (i.e. if $z\_i+y\notin Y$, but $z\_i+y\in Y$), we don't need $z\_i$ in $Y'$.
* Repeat recursively with $Y'$, collecting the minimal elements $y,y',\dots$ into a multiset. This is your solution iff you end up with an empty set.}

In each recursive step, the size of the set decreases by at least $1$ (since we exclude the least element $y$), so the number of steps is in $O(n)$. Each step contains a single iteration over the current set, for an $O(n^2)$ total complexity (assuming unit costs for arithmetic operations).

Finding a minimal solution (note that this is not necessarily unique; for example, for $Y=\\{0,1,3,4,5,6,7\\}$ we have $\\{0,1,3,4,6\\}$ and $\\{0,1,3,5,6\\}$) is slightly more involved: after finding the minimum $y\in Y$, you would analyze the arithmetic progressions $\\{a+k\cdot y\\}$ in $Y$, reject if one of them is a singleton, and otherwise pick alternating members for $Y'$; if a progression has odd length, you need to pick some pair of successive members, hence the non-uniqueness.
> 1 votes

---
Tags: algorithms, optimization, combinatorics, integers
---


# Question
Title: Determining if an undirected connected graph is minimally connected
I'm trying to solve a practice problem in Elements of Programming Interviews (19.4) and I am a bit confused. The question is to determine if an undirected connected graph is minimally connected.

The authors define minimally connected as "it is connected and there is no edge that can be removed while still leaving the graph connected."

This question is equivalent to asking if there are any cycles in the graph.

They authors' solution runs the white-gray-black variant of recursive DFS, and return false if a grey node is visited twice.

It seems to me though, that since you know the graph is connected you can just count the number of edges. Any minimally connected graph, like a binary tree, will have (V - 1) edges.

```
return num_edges/2 == num_vertices - 1;

```

So, long story short, is this solution correct for the case of an undirected, connected graph? I checked the books errata and it doesn't mention it.

# Answer
> 5 votes
If $G$ is an undirected graph, it's a standard lemma that the following are equivalent:

* $G$ is a tree.
* $G$ is connected and has no cycles.
* $G$ is connected and the number of edges is one less than the number of vertices.

Therefore, yes, your solution is also correct.

(The authors' solution does have the benefit of giving you a relatively simple setting where you can think through the properties of depth-first search in a deep way. There are other problems that aren't solved so easily, and where the best solution involves some other sort of modification to depth-first search.)

---
Tags: algorithms, graphs, spanning-trees
---


# Question
Title: DPDA for $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ according to empty stack criterion
I'm having some trouble with the following language:

$L\_1 = \\{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\\}$

with alphabet $A=\\{0,1,2,3\\}$

I'd like to find a deterministic pushdown automata to recognise it according to the empty stack criterion.

I built the deterministic pushdown automata according to the final states criterion and as the language has the prefix property there should be an automata according to the empty stack criterion.

Is there an algorithm to do this? The one I use to translate from one criterion to the other doesn't not seem to work for deterministic automata.

# Answer
DPDA for $\mathcal L=\\{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\\}$

let's try to understand wich words the automata should accept:

$\\{\varepsilon,03,13,23,0033,1133,2233,0133,0233,1233,000333,111333,\dots \\}\in \mathcal L$

So we can see the "two parts" of the automata, the first part will contain the $0,1,2$ digits and the second part of the automata will contain the $3$ digits, so for the first part we will do a "push" for some $X$ and for the second part we will do a "pop" for $X$, we will accept the word if the stack is empty so in the end we will do a "pop" for some $Z$ that have been in the stack alaready

Try this one, if it is not $100\\%$ at least it will lead you to bulid it by yourself

SPOILER:

>
> 1 votes

---
Tags: context-free, pushdown-automata
---


title: From NFA to DFA (basics)

text:
# Question
Title: From NFA to DFA (basics)
I am trying to learn NFA to DFA.

This is the original image

To begin the process of converting to DFA, I started off with the start state and noticed that if the input is a 1, this means it goes to qb, which would be represented as {qa qb}. I also think it would loop onto itself because if you have a 0 and are in that state, it goes back to qa (does this make sense)?

Now, for the accept state, do I label {qa qb} as an accept state? Needless to say I'm getting myself a little confused... Pardon also the awful handwriting.

# Answer
Yes.

`{qa,qb}` will be an accepting state.

Because you are still learning it, you might find these useful

https://www.youtube.com/watch?v=IE4LcyIfGOk

https://www.youtube.com/watch?v=MMfLTfoJUAI

(P.S - I don't think you should be asking this kind of elementary questions here, as you are supposed to learn these things from your respective course teacher(s) (Unless you are not studying CS / related subjects, or it is not possible for you to be in touch with someone enough knowledgeable on these subjects). Moreover, you should practice these things a lot to have a clear conception on the conversion process. You should be able to find the basic instructions and procedures for these problems in the internet easily.)
> 0 votes

---
Tags: finite-automata
---


# Question
Title: checking if string is generated by regular grammar
How do I check wether a string is generated by given regular grammar? I know you can check for it in O(N), what is the algorithm called?

# Answer
> 2 votes
A regular grammar corresponds quite closely to a non-deterministic finite automaton, reading the word in the usual way (right regular grammar) or backwards (left regular grammar). You can run $m$-state NFAs on inputs of length $n$ in complexity $O(2^m n)$, which is linear if you fix the NFA.

---
Tags: regular-languages
---