title: restricted sub-permutations check

text:
# Question
Title: restricted sub-permutations check
I am solving the following problem, motived by combinatorial optimization sampling proces.

I have restriction (0,1) matrix to restrict which item (column index) can be on current position (row index) at permutations. For example: 4x4 case (4 position permutations)

```
 1     1     1     0
 1     1     0     1
 1     0     1     1
 0     1     1     1

```

So, on position 4 (4th row at restriction matrix) is not allowed items 1, for example.

This restrictions produce the following list of possible permutations (earch row is one possible permutation):

```
 1     2     3     4
 1     2     4     3
 1     4     3     2
 2     1     3     4
 2     1     4     3
 2     4     1     3
 3     1     4     2
 3     2     1     4
 3     4     1     2

```

I am looking for algorithm to check if any sub-permutation, which is represented by first N \< 4 positions, may correspond to any of possible permutation or not, without need to avaluate all possible permutations.

For example sub-permutation \[1 2 3\] is OK, but sub-permutation \[3 4 2\] is not.

# Answer
> 2 votes
A sub-permutation (not necessarily initial) corresponds to the removal of rows and columns in your restriction matrix. So your problem can be reduced to the case $N = 0$ (you also have to check that your sub-permutation conforms to the restriction matrix). In order to determine whether a restriction matrix admits any permutation, treat it as an $n \times n$ bipartite graph, and check whether the graph has a perfect matching.

Here is an example. Consider your restriction matrix $$ \begin{matrix} 1&1&1&0 \\ 1&1&0&1 \\ 1&0&1&1 \\ 0&1&1&1 \end{matrix} $$ Choosing the first three elements to be $1,2,3$ is the same as deleting the first three rows and columns. We get $\begin{matrix} 1 \end{matrix}$, which has a perfect matching as a $1\times 1$ bipartite graph.

In contrast, choosing the first three elements to be $3,4,2$ is the same as deleting the first three rows (say) and columns $3,4,2$ (rows and columns might be switched depending on the representation). We get $\begin{matrix} 0 \end{matrix}$, which doesn't have a perfect matching.

---
Tags: algorithms, decision-problem, permutations
---


title: Complexity of multiplication

text:
# Question
Title: Complexity of multiplication
I've been reading around the area of complexity and arithmetic operations using logic gates; one thing that is confusing me is that \begin{equation} \Theta (n^{2}) \end{equation} is quoted as being the complexity for multiplication for iterative adition. But addition of a number requires \begin{equation} log\_2(n) \end{equation} operations, 1 for each bit or 8 times that for each nand gate involved in doing this. So it strikes me as obvious that adding that number n times will have a complexity of \begin{equation} n \log\_2(n) \end{equation} Which is definitely less than \begin{equation} \Theta (n^{2}) \end{equation} So where is this additional factor of \begin{equation} \frac{n}{\log\_2(n)} \end{equation} coming from?

# Answer
> 8 votes
Addition of a number of size $n$ takes time $O(n)$. Don't confuse a number and its encoding size, which is logarithmically smaller.

When multiplying an $n$-bit integer $a$ by an $n$-bit integer $b$ using the iterative addition algorithm, you are adding up to $n$ shifted copies of $a$. Each addition costs you $O(n)$ rather than $O(\log n)$. The numbers $a,b$ itself could be as large as $2^n$.

---
Tags: complexity-theory, arithmetic
---


title: L closed under logspace reduction

text:
# Question
Title: L closed under logspace reduction
Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$.

I read the proof that $L$ is closed under logspace reductions in Arora-Barak's textbook. The idea of the proof is, if I'm not getting wrong, to simulate the Turing Machine $M\_B$ that computes the solution to $B$, carefully recomputing the $i$-th output bit of $f$ whenever we need it (so to save space).

My (probably naive) question is: since we are only interested in remaining within $L$, why can't we just compute the output of $f$ and store it entirely on the work tape of $M\_B$ (this should require only logarithmic space), maybe separating it from the rest of the work tape with a special symbol, and use it as input to $M\_B$? Since $B \in L$ this should require just an additional logarithmic amount of space, so there shouldn't be any risk to exit from $L$…where am I getting wrong?

# Answer
> 4 votes
The output of $f$ doesn't have to be of logarithmic size. This is why there is something to show.

To give an example, the function $f(x) = x$ can be computed in constant space but its output length is linear.

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


# Question
Title: About showing algorithmic gap instance for the Goemans-Williamson SDP
Using usual notation we have,

$SDP(G) \geq OPT(G) \geq Alg\_{GW}(G) \geq \alpha\_{GW} SDP(G) \geq \alpha\_{GW} OPT(G)$

where we mean,

$SDP(G)$ = The maximum value that the SDP finds of the objective function $\sum\_{(u,v) \in E} w\_{uv}( 1-\vec{y\_u}.\vec{y\_v})/2$ (one unit vector $\vec{y\_v}$ in $\mathbb{R}^d$ for each vertex $v$ for some $d$) And $w\_{uv}$ are the given edge weights such that $\sum\_{(u,v) \in E} w\_{uv} =1$

$OPT(G)$ = The actual size of the max-cut for the graph

$Alg\_{GW}(G)$ = The value of the max-cut returned by the randomized rounding prescription of Goemans-Williamson

$\alpha\_{GW}$ = the famous constant of $\sim 0.878$

* If say someone shows that for every $\epsilon$ there is a graph $G(\epsilon)$ such that $(\alpha\_{GW}+\epsilon)OPT(G(\epsilon)) \geq Alg\_{GW}(G(\epsilon))$ then does this imply that this is a class of graphs on which the algorithm is performing as bad as it could?
* Why does showing the existence of such a family of graphs as above also necessarily imply that on this family $SDP(G(\epsilon)) = OPT(G(\epsilon))$ ?

# Answer
> 1 votes
A graph for which $Alg(G) = \beta OPT(G)$ is, by definition, a graph on which the algorithm has approximation ratio $\beta$. You can use this insight to answer the first question.

As to your second question, suppose that $Alg(G) \leq (\alpha\_{GW}+\epsilon) OPT(G)$. Since $Alg(G) \geq \alpha\_{GW} SDP(G)$, we deduce that $$ \alpha\_{GW} SDP(G) \leq Alg(G) \leq (\alpha\_{GW}+\epsilon) OPT(G). $$ Therefore $SDP(G) \leq (1+O(\epsilon)) OPT(G)$.

---
Tags: complexity-theory, time-complexity, approximation
---


title: A facility location problem

text:
# Question
Title: A facility location problem
Consider the following scenario. There are N localities in a town where population for locality $L\_i$ is denoted by $P\_i$, $i \in {1,\ldots,n}$. We need to place K hospitals around the town in a way that the cost of accessing the hospital is minimized.

We are basically trying to $$\min\_O(\sum\_{i=1}^N P\_i \times C(d(L\_i,O(L\_i))))$$ where, $$O(L\_i) = \textrm{Nearest hospital's location to }L\_i\\d=\textrm{Euclidean distance between 2 locations}\\C = \textrm{Cost function to travel distance }\`\`d"$$

It doesn't seem we can use gradient descent. Consider 3 localities $L\_1,L\_2$ and $L\_3$ and 2 hospitals $H\_1,H\_2$. If we initially put $H\_1,H\_2$ on $L\_1,L\_2$ e.g.

$$L\_1H\_1\ldots L\_2H\_2 \ldots L\_3$$

If the gradient descent starts moving projects to the right, then we may find ourselves in the following situation. The final location of nearest hospital to $L\_2$ would have changed from $H\_2$ to $H\_1$.

$$L\_1\ldots H\_1L\_2 \ldots H\_2L\_3$$

So could you please give me some pointers on how to solve this problem?

# Answer
This problem is known as Euclidean $k$-center problem and is known to be NP-complete. There are some approximation algorithms but we don't have any PTAS algorithm.

Of course for $K \geq N$, the solution is trivial, with optimal value 0.
> 2 votes

---
Tags: algorithms, optimization, probability-theory
---


# Question
Title: Match students and teachers based on ranking
I have a similar question to that of Stable Marriage Problem.

This is the criteria
1) 1 Student must have 1 Teacher only.
2) 1 Teacher ideally should have 3-4 Students.

The spreadsheet is done using Google Apps Script (Javascript). How do I go about with the system calculation and giving teachers the system-generated result (3-4 Students) ?

# Answer
Your problem differs from stable marriage problem in a minor way. A teacher can have 4 students maximum. You will have to fix the maximum students allotted to teacher (you may not have 3-4, if you also prescribe minimum number of students then you might have to dig deeper).

Now you can do two things, first, have four copies of each teacher and solve the stable marriage problem. Second solution is essentially like first but you keep a list of 4 "engagements" for each teacher.
> 1 votes

---
Tags: algorithms, bipartite-matching, assignment-problem
---


# Question
Title: Select a subset of the columns in $2\times n$ matrix, is it easy?
I want to know if this problem is polynomial-time solvable or not?

The problem is: Given a nonnegative integer-valued matrix of size $2\times n$ and two nonnegative integer numbers $b\<n$ and $c$.

The question is: Find a subset of the columns of cardinality at most $b$ such that the sum of each row over the subset of the columns is greater than $c$. Return no if no such subset exists.

I cannot show it is NP-hard.

EDIT:

*My attempt to prove hardness*: According to the suggestions by Filmus, I tried to reduce PARTITION (an instance is given by the set of non-negative integers $\\{a\_1,\ldots,a\_n\\}$) to my problem. I failed of course. The think that I did not understand is how partitioning a set of non-negative integers is related to this problem? I mean in my problem I want to choose a subset of $\\{1,\ldots,n\\}$ in order to maximize something. I cannot see how this is a partition. I tried many thinks but I cannot write them all here:

* I tried to create the matrix with only $a\_{2i}$ in the first row and $a\_{2i+1}$ in the second row.
* I tired to make the first row sorted in increasing order and the second row sorted in the decreasing order.
* I tried to divide the $a\_i$ into two values $\alpha\_i$ and $\beta\_i$ such that $a\_i=\alpha\_i+\beta\_i$ and then create the matrix with $\alpha\_i$ in the first row and $\beta\_i$ in the second row.

**Can someone explain to me, intuitively, how can I use PARTITION to show the NP-hardness of my problem?** You do not have to give the solution.

*My solution to solving the problem*:

I tried this solution. Suppose, without lose of generality that the first row of the matrix is sorted in increasing order. (The second row of the matrix does not have to be sorted otherwise the problem is trivial.)

Now, take the last $b$ columns of the matrix.

* If the sum over the first row is less than $c$ than we are done. No solution exists.
* Else, the sum of the first row over the last $b$ columns is greater than $c$, then see the sum of the second row.
    + If the sum of the second row over the last $b$ columns is greater than $c$ than we are done. Return the last $b$ columns.
    + Else, the sum of the first row over the $b$ columns is greater than $c$ but the sum of the second row over the $b$ columns is less than $c$. Well, here we have a problem.

# Answer
Hint: Show that it is NP-hard by reduction from EQUAL-PARTITION, the variant of PARTITION in which we require both parts to have equal sizes (see a question on math.se).

Given an instance $\\{x\_1,\ldots,x\_n\\}$ of EQUAL-PARTITION (with $x\_i \> 0$), consider an instance of your problem with $b = n/2$, $c = \sum\_i (M+x\_i)/2 - 1$ for large enough $M$ (I think that $M = \max\_i x\_i$ should suffice), and the matrix $$ \begin{bmatrix} M+x\_1 & \cdots & M+x\_n \\ M+\frac{\sum\_i x\_i}{n/2}-x\_1 & \cdots & M+\frac{\sum\_i x\_i}{n/2}-x\_n \end{bmatrix}. $$
> 6 votes

---
Tags: algorithms, complexity-classes
---


title: Language is decidable or not?

text:
# Question
Title: Language is decidable or not?
Prove each languages decidable or undecidable.

```
{ <M> | L(M) is not recognizable}

```

I am not able to understand how this works. And what is recognizable language? What are the angle brackets? And of course how is language undecidable?

# Answer
**Hint**: The language $\\{\langle\\,M\\,\rangle\mid L(M)\text{ is unrecognizable}\\}$ is empty (why?) and the empty language is decidable (why?).
> 4 votes

---
Tags: computability, undecidability
---


# Question
Title: Red-black tree amortized cost of the rebalancing
I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions).

How can it be proven?

# Answer
If you look at the rules for what happens in a red/black tree insertion, you can see that the fixup rules for maintaining the red/black invariants only propagate upward if the newly-inserted node becomes the child of a red node with a red sibling.

Let's call a "fissionable" group in the red/black tree a black node with two red children. If you do an insertion into a fissionable group, the fissionable group will be recolored and rotated in a way that ends up eliminating that fissionable group, but which propagates the insertion fixup to a higher level in the tree. If you set the potential function of a red/black tree to be the number of fissionable groups in the tree, then the true cost of doing an insertion is 1 + r, where r is the number of groups destroyed, and the number of new fissionable groups created is at most one (you should check this), so the amortized cost of a fixup is O(1) because the potential drop is r.

It's a lot easier to think about this by looking at the isometry between red/black trees and 2-3-4 trees. A fissionable group in a red/black tree corresponds to a 4-node in a 2-3-4 tree, and if you understand 2-3-4 tree insertions it's pretty easy to see why the amortized cost of an insertion into a red/black tree is O(1).
> 3 votes

---
Tags: algorithm-analysis, data-structures, search-trees, amortized-analysis, balanced-search-trees
---


# Question
Title: Proving correctness of a loop that calculates the sum of array
I am trying to mathematically prove that the following program is correct:

```
int ArraySumC(int[] a) {
    int i = 0;
    int j = 0;

    while (i <= n) {
        j = j + a[i];
        i = i + 1;
    }

    return j;
}

```

When the loop ends, we want the invariant, Q, and the condition for loop termination, B'.

```
Q ∧ B' = Q ∧ i > n

```

We also want the post condition

```
j = sum(a[1] ... a[n])

```

I'm not sure how to go from here, because I don't know what Q should be. I am used to B' being an equality and thus being able to substitute one side of B' into the post condition. Should I assume that B' is i = n + 1? Or is there another way to deal with the inequality?

# Answer
I think your postcondition is wrong. Since index i is initialized at 0, you're actually summing from 0 to n, not from 1 to n. The postcondition, lets call it $P$, should be:

$$ j = \sum\_{k=0}^{n} a\[k\] $$

Or:

```
j = sum(a[0] ... a[n])

```

Usually you would write $B$ as $i \neq n+1$ instead of $i \le n$, because it makes the proof easier. In that case, you would choose $Q$ as (assuming array indexing starts at 0):

$$ j = \sum\_{k=0}^{i-1} a\[k\] $$

Or in your notation:

```
j = sum(a[0] ... a[i-1])

```

Then $ Q \land \lnot B \implies P$ is true because you can substitute $i$ by $n+1$. Of course, you would have to prove that $Q$ is a valid invariant, but I'll leave that to you.

In your case,$\lnot B$ is $i\>n$ instead of $i = n + 1$, so you can't use substitution. You can deal with the inequality by adding information to the invariant and then proving $i = n +1$ using this new information. Our new invariant $Q'$ could be:

$$Q \land i \le n+1$$

This new condition holds before the loop starts because $i$ starts at 0 and $n+1$ must be at least $1$.To prove that $Q'$ is a valid invariant, we have to show that it also holds after every iteration. Each time the loop executes $i$ changes to $i+1$, so we must prove that $ i+1 \le n+1$, which is true because the loop condition states that $i \le n$ was true when the iteration started.

Now we know that $Q \land i \le n + 1 \land i \> n$ holds after the loop ends. And since $i \le n + 1 \land i \> n \implies i = n + 1$ and $Q \land i = n + 1 \implies P$, the program is correct.
> 3 votes

---
Tags: loops, loop-invariants, program-correctness
---


title: Interesting small SAT problems?

text:
# Question
Title: Interesting small SAT problems?
I'm noodling around with making a hardware SAT solver on an FPGA, and I'm wondering if there are any interesting SAT problems smaller than, say, 50 variables both to stay within the limits of the FPGA board (namely the number of LEDs) and so I can brute-force if needed to get all possible solutions. I looked into factorizing small integers, but it seems that even relatively small numbers quickly get in to the hundreds of variables. Is there anything else I can look at besides random-SAT?

# Answer
In general, you can look at hard combinatorial instances. If 50 variables is not a hard limit, try e.g., an instance arising from combinatorial block design having 105 variables described in \[1\]. The actual instance in DIMACS format is here provided by the authors. For the instance, the authors write in \[1\] that: "We issue a challenge for any solver to solve it in less than one day."

Something that will be not as hard, but still not entirely trivial is coloring Mycielski graphs. These are graphs with clique number 2, but the chromatic number can be arbitrarily large. Again, if 50 variables is really a hard limit, it seems the largest Mycielski graphs you can consider is the Grötzsch graph if you use the obvious encoding to CNF. The obvious encoding will have 33 variables if you test for 3-colorability (UNSAT), and 44 variables if you test for 4-colorability (SAT).

---

\[1\] Van Gelder, Allen, and Ivor Spence. "Zero-one designs produce small hard SAT instances." Theory and Applications of Satisfiability Testing–SAT 2010. Springer Berlin Heidelberg, 2010. 388-397.
> 5 votes

# Answer
See the international SAT solver competition. It's a competition that tests various solvers by running them on a library of hard SAT instances. You can download the instances they used to evaluate the SAT solvers. I would suggest you look at these competitions and see if any of the instances they've used would meet your needs.
> 3 votes

---
Tags: satisfiability, data-sets, benchmarking
---


# Question
Title: How do I find the max and min value of an array in 3n/2−2 comparisons?
So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers or a single number.

What I'm trying to do now is the same thing but I'm trying to come up with a method that will always use 3n/2−2 comparisons. The method above doesn't use 3n/2−2 comparisons each time. So I just want to visualize how this is done on an array before I start to programming the method.

# Answer
Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. The maximum value of the original array must be the max of the larger group and the minimum value of the original array must be the min of the smaller group. Initially, you do n/2 comparisons to make the split, and from there you need to find the max and min of two groups of n/2 elements each, which can be done with a total of n/2 - 1 comparisons per group. Overall, this is 3n / 2 - 2 compares.

... assuming, of course, you have an even total number of elements. Think about what happens if that isn't the case.
> 7 votes

# Answer
There is an algorithm for finding minimum and maximum simultaneously (in one pass over an array), requiring $O(1)$ additional memory.

The idea is to process the elements of the input array *in pairs* as in this answer by templatetypedef, but without explicit grouping, so (almost) no additional memory is needed.

A coarse sketch of the algorithm:

1. Compare the first pair of elements between *each other*.
2. Compare the smaller element with the current minimum and update the current minimum if needed.
3. Compare the larger element with the current maximum and update the current maximum if needed.
4. Repeat for the rest pairs.

The analysis of the number of comparisons is the same as given by @templatetypedef.

This algorithm is described in detail in "Introduction to Algorithms", 3ed by Cormen, Leiserson, Rivest, and Stein (sect. 9.1, p. 214).

The book also states (in the form of an exercise) that the lower bound for **any** simultaneous min/max algorithm is $\lceil 3n/2 \rceil - 2$ comparisons in the worst case, so we actually can't do much better than we already do.
> 2 votes

# Answer
Just scan the array, starting with provisional maximum and minimum as the first element, from the second element onwards. If the element is larger than your current maximum, record that; if not, see if it is smaller than your current minimum, and update. You don't need the whole paraphernalia of splitting and recursion.

Can't have a simpler program. Can't do with less work, need to compare with at least $n - 1$ elements to confirm the maximum. For any order in which you check, by ordering the elements to be checked in decreasing order, you can force $2 (n - 1)$ comparisons.
> 0 votes

---
Tags: algorithms, search-algorithms, arrays, comparison
---


# Question
Title: Complexity of dynamic card game algorithm
Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red card drawn, we get 1 dollar and lose 1 dollar for every black card drawn. The problem consists in finding an algorithm which returns the expected value of the game. If we denote by $b$ and $r$, respectively, the number of black and red cards left in the deck at any time, the expected value of the game $E(b,r)$ satisfies:

$$E(b,r)=\max\left\\{b-r,\frac{b}{b+r}\\,E(b-1,r)+\frac{r}{b+r}\\,E(b,r-1)\right\\}\\,,$$

with boundary conditions $E(0,r)=0$ and $E(b,0)=b$. The expected value of the game is therefore given by $E(26,26)$.

My question is, if we implement the recursive algorithm associated with the above formula, how can we determine its complexity? Using the trivial cases of $E(1,1)$ and $E(2,2)$, it would appear that we are dealing with exponential complexity, but is there a way to prove this properly, and if so, what is the number of necessary operations to compute $E(n,n)$ for an arbitrarily large integer $n$? Any ideas or references to literature would be greatly appreciated.

# Answer
> 3 votes
As pointed out in the comments, your recurrence is wrong (though equivalent for $b=r$; it's a recurrence for $E(b,r)+b-r$). Also, you can solve this efficiently using memoization or its more principled cousin, dynamic programming. The dynamic programming solution calculates iteratively $E(i,j)$ for $i+j=0,1,\ldots,52$.

Finally, to answer your question, if you implement you original solution, you get a running time satisfying the recurrence $$ T(b,r) = C + T(b-1,r) + T(b,r-1), $$ with initial conditions $T(b,0) = O(1)$, $T(0,r) = O(1)$. If $T'(b,r) = T(b,r)-C$ then $$ T'(b,r) = T'(b-1,r) + T'(b,r-1), $$ a recurrence solved by $\alpha \binom{b+r}{r}$. Taking the initial conditions into account, we get that $$ T(b,r) = \Theta\left(\binom{b+r}{r}\right). $$ In particular, $$ T(n,n) = \Theta\left(\binom{2n}{n}\right) = \Theta\left(\frac{4^n}{\sqrt{n}}\right). $$ (This assumes all arithmetic is $O(1)$. The running time is actually somewhat larger since the relevant numbers grow fast, but this is a (multiplicative) lower-order factor.)

---
Tags: algorithms, algorithm-analysis, runtime-analysis, probability-theory, recursion
---


# Question
Title: How can I draw a Moore diagram for a given circuit?
I have a circuit and I should draw a moore diagram (state diagram) for that.  The problem is that every state can have 5 inputs and this makes the question hard for me.  I tried about 20 times to draw that diagram and every time I failed.  Can anyone help?

# Answer
Don't try to draw the automata. Because there will be 32 states each having five transitions. Rather try to describe the transition function and output as hinted by DylanSp. i.e.

q01001 -\> 1 -\> q11001 (output 1), meaning if switches 2,5 are on and you put on switch 1, the lamp is lighted.

Another one. q11001-\>2-\>q10001 (output 0), meaning if switch 1,2 and 5 are on and you put off switch 2 than the lamp is unlighted.

I assume that input consists of a sequence of 1,2,3,4,5 indicating which switch is flipped. starting state is q00000. I assume, final state will be probably those transitions where lamp is lighted, if that is what you are trying to do.
> 2 votes

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


# Question
Title: Polynomial hierarchy: inclusion between spaces
Using the definition for the polynomial hierarchy:

$$ \Sigma\_{i+1}^P = NP^{\Sigma\_i^P} $$ $$ \Pi\_{i+1}^P = coNP^{\Sigma\_i^P} $$

I have been asked to to show that:

$$ P^{\Pi\_k^P } \subseteq \Pi\_{k+1}^P $$

I don't really have many ideas on how to go for it:

by definition $ P^{\Pi\_k^P } $ is the set of languages accepted by a $PTIME$ deterministic TM with an oracle answering queries in $\Pi\_k^P$, while $\Pi\_{k+1}^P$ is the set of languages accepted by a universal alternating TM, with an oracle answering queries in $\Sigma\_k^P$.
If I could use a universal ATM $M\_A$ to simulate a DTM (and I would say I can't) then I should be able to recognize a language $L \in P^{\Pi\_k^P}$ by noticing that $L$ is accepted by a DTM $M$ that uses the oracle $O$ (that answers about $\Pi\_k^P$), thus taking a universal ATM $M\_A$ to simulate $M$ and another universal ATM $M\_O$ (accepting queries in $\Pi\_{k+1}^P$) to simulate the oracle (since $\Pi\_k^P \subseteq \Pi\_{k+1}^P $).

But I really think this reasoning cannot be done, as actually I'm not using the oracle…how should I approach the problem?

# Answer
Using the definition of Papadimitrou for polynomial hierarchy, or for that matter from wiki, the proof is really simple. $\Delta^P\_{k+1} = P^{\Pi\_k^P} \subseteq CoNP^{\Pi\_k^P} = CoNP^{\Sigma\_k^P} = \Pi^P\_{k+1}$. Similarly $\Delta^P\_{k+1} \subseteq \Sigma^P\_{k+1}$.

But if the definition of polynomial hierarchy is done by alternating quantifiers than also we can prove it in the following way. The proof follows the book "Computational Complexity" by Arora and Barak, yet you have to flip a few $\exists$ and $\forall$, and do some negations. Assume equal fixed polynomial length certificates in the following proof.

We know that $P^{\Pi\_k^P} = P^{\Pi\_k^{SAT}} = P^{\Sigma\_k^{SAT}}$.

Suppose that $L$ is decidable by a polynomial-time DTM $M$ with oracle access to $\Sigma\_k^{SAT}$. Then, $x$ is in $L$ if and only if there exists a sequence of oracle answers that makes $M$ accept $x$. That is, if $a\_1 , . . . , a\_m \in \\{0, 1\\}$ is a sequence of (correct) answers to oracle queries on input $x$, that is, the machine $M$ receives $a\_i$ as the answer to its $i$ th query, then (1) $M$ reaches the accepting state $q\_{accept}$ and (2) all the answers are correct. $m$ is the maximum number of oracle queries.

We can modify DTM $M$ so that it will make exactly $m$ queries for the given input size $|x|=n$, i.e $m$ is not varying depending on the outcomes of the oracle. $m$ will be (less than) a polynomial in $n$. $m$ can also be made polynomial time computable by possibly taking a larger value. The proof is made further difficult because there are polynomial number of queries and each $i$-th query may be different depending on the answers of previous queries. Also we need to convert $\exists a\_1, a\_2,...$ to $\forall a\_1,a\_2,...$ is the proof by Arora and Barak.

Let $\phi\_{i,a\_1,a\_2,...,a\_{i-1}}$ denote the $i$-th query that $M$ makes to its oracle when executing on $x$ receiving answers $a\_1 , . . . , a\_{i-1}$ . $\phi\_{i,a\_1,a\_2,...,a\_{i-1}}$ can be generated by a turing machine (which is similar to $M$ in some ways) in polynomial time. Then, the condition (2) can be phrased as follows:

if $a\_i = 1$ then $ \exists u\_1 \forall u\_2 ... \phi\_{i,a\_1,a\_2,...,a\_{i-1}}(u\_1,u\_2,...,u\_k ) = 1$ and if $a\_i = 0$ then $ \forall v\_1 \exists v\_2 ... \phi\_{i,a\_1,a\_2,...,a\_{i-1}} (v\_1,v\_2,...,v\_k ) = 0$.

Now we have the following:

$x \in L$
iff $\forall a\_1 , . . . , a\_m \in \\{0,1\\}$
$\exists i \in \[1..m\]$ if $a\_i = 1$ then $\forall U\_i^1 \exists U\_i^2, \forall U\_i^3,...\phi\_{i,a\_1,a\_2,...,a\_{i-1}}(U\_i^1, U\_i^2,U\_i^3,...,U\_i^k) = 0$
OR $\exists i \in \[1..m\]$ if $a\_i = 0$ then $\exists V\_i^1\forall V\_i^2, \exists V\_i^3,...\phi\_{i,a\_1,a\_2,...,a\_{i-1}} (V\_i^1,V\_i^2,V\_i^3,...,V\_i^k) = 1$
OR $M$ accepts $x$ using answers $a\_1 , . . . , a\_k$

This implies that $L \in \Pi\_{k+1}^P$ since $\phi\_{i,a\_1,a\_2,...,a\_{i-1}} \in \Sigma\_k^{SAT}$. ( You can club all quantifiers as $\forall a\_1 , . . . , a\_k , U^1\_1 , U^1\_2 . . , U^1\_m \exists V^1\_1 , . . . , V^1\_m, U^2\_1, U^2\_2, ... U^2\_m \forall V^2\_2,..., V^2\_m, U^3\_1, ...U^3\_m \exists ...$ , the certificates are still polynomial).

We can actually prove $NP^{\Sigma^P\_k} = \Sigma^P\_{k+1}$ and $CoNP^{\Pi^P\_k} = \Pi^P\_{k+1}$ using similar methods if I remember correctly.

The inclusion graph is given pictorially below,
> 4 votes

---
Tags: complexity-theory, complexity-classes, polynomial-time, simulation, oracle-machines
---


# Question
Title: Where can I find an original reference for this integer square root algorithm
As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary.

I'm sure this is not original; can anyone provide a reference?

```
// All arithmetic is truncating unsigned integer arithmetic
// Actual implementation uses bit shifts
// Indention level defines statement scope

def sqrt(r)                         // r is an unsigned integer
    residue = r                     // residue will be the 'remainder'
    root = 0                        // root will be the integer square root (floor(r**0.5))
    onebit = 2**(bitlength(r)-2)    // onebit is a moving 'bitpicker'
    while onebit > r
        onebit = onebit / 4         // find highest bitpicker less than r
    while onebit > 0
        x = root + onebit           // Current root plus onebit
        if residue >= x             // Room to subtract?
            residue = residue - x   // Yes - deduct from residue
            root = x + onebit       // and step root
        root = root / 2             // Slide evolving root 1 bit down the residue
        onebit = onebit / 4         // Slide the bitpick 1 bit down the root
    assert(root**2 + residue == r)
    assert((root+1)**2 > r)
    return root, residue

```

# Answer
> 9 votes
The wikipedia article on Methods of computing square roots: base 2 presents a strikingly similar snippet of C-code *\[a\]*, but the link to the source is dead. Let's try to do better.

The snippets from both wikipedia and the question are very similar to Martin Guy's widely circulated C implementation *\[b\]*. which contains a comment: *From a book on programming abaci by Mr C. Woo*. Search engine use suggests this is \[1\] - one edition seems to be from 1930; it has been reprinted, e.g. \[2\].

The age of the method is bound to be on the order of two millenniums - *the* original reference might be difficult to obtain.

A purportedly\[z\] very similar Algorithm has been presented by TIJ Rolfe, who in turn refers to \[3\].

---

1. Woo, C.C. *The Fundamental Operations in Bead Arithmetic. How to Use the Chinese Abacus*, China Lace Co., Ltd., Hong Kong
2. Kwa Tak Ming, C. C. Woo, *The Fundamental Operations in Bead Arithmetic. How to Use the Chinese Abacus*, Literary Licensing, LLC, United States, 2012, 9781258466855
3. Hart, W.L. "College Algebra" 4th ed., Boston, 1955, p.424

---
Tags: algorithms, reference-request, integers, numerical-algorithms
---


# Question
Title: Why isn't there a universal separator character for data files?
I am not sure if this is the correct forum for this question, but... After so much time and usage of spreadsheets and data files in general, there is a need to cater for all types of files containing all sorts of characters used as a field separator. Why hasn't a universal separator character evolved so that no-one has to bother with tab vs. pipe vs. comma (with and without quoted fields) vs. whatever? You would think that there would be a dedicated key on the keyboard like the "Enter" button used for field separation that is non-printable and that would reduce the number of data file types to one (with the exception of proprietary formats).

# Answer
We could have a field separator, but we don't, because of historical reasons. Most of the characters are brought from the era of typewriters. So we have line-separator ^M and page-separator ^L, and we actually have record separator \037 and unit separator \038 which can be used as field separator. But in reality no one uses that. First if you have a text file like csv, you want to use separators which are visible like , : TAB or SPACE. If your file is binary you are free to do almost anything with it.

Now it is too late to have a universal field separator. You can have your own private field separator of your choice. Just don't use it in your fields too.
> 2 votes

---
Tags: databases, information-retrieval
---


# Question
Title: Proving that the language of satifiable CNF formulae with primes is NP-complete
> Given the following language:
>
> $$L=\left\\{\langle\phi, n\rangle \ \middle|\ \begin{array}{l}\phi\text{ is a satisfiable Boolean formula}\\ \text{written as POS (in CNF form)}\\ \text{and $n$ is a prime number}\end{array}\right\\},$$
>
> Prove that L is an NPC language.

This is the first time I'm trying to solve this kind of questions, and I am stuck.

This is what I have so far:

To prove that a language is NPC, I need to prove two things:

1) $L \in \mathrm{NP}$

2) For any $L'\in \mathrm{NP}$, there exists a poly-time reduction from $L'$ to $L$.

To prove (1), can I say that $\phi$ is NP (because we know that SAT is NP), and that $n$ is P (because Prime is P)?

If so, I think that I need to say that $\mathrm{P} \subseteq \mathrm{NP}$ to complete the proof of (1).

What's next?

# Answer
For 1): You have to prove that the language is solvable by a nondeterministic TM in polynomial time. The easiest way is indeed to use previously defined TMs, e.g. the TM to solve SAT. So your approach is correct.

For 2): You don't have to prove it for every $L'$ $\in$ $NP$ explicitly, it suffices to give a reduction from a language that is NP-complete. The idea is that you reduce every word $w' \in L'$ to a word $w \in L$, so if you find an efficient way to solve $L$, you also have an efficient way to solve $L'$. So you can choose any NP-complete language that should provide a simple reduction to $L$.

The next step therefore would be to choose such NP-complete language $L'$.

Next you have to find a reduction $f$ to reduce your previously chosen language $L'$ to your language $L$. Depending on your choice of $L'$, this can be a very simple process in your case. Note that $\\{$ $f(w') \mid w' \in L \\} \subseteq L$, not $\\{$ $f(w') \mid w' \in L \\} = L$
> 4 votes

# Answer
Below is not a general solution, but specific to the language given in the question. This technique is called restriction. Other widely used techniques are local replacement and component design. You can find these in the old text book of Garey and Johnson.

For 2) we know that $L' \leq SAT$ for all $L' \in NP$. So we only need to prove $SAT \leq L$, just reduce $\phi \rightarrow \langle\phi,2\rangle$. This will give us $\phi \in SAT$ iff $\langle\phi,2\rangle \in L$.

Then $\forall L' \in NP, L' \leq SAT \leq L$.
> 0 votes

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


title: client and server programs

text:
# Question
Title: client and server programs
I\’m a novice programmer that\’s learning how to program on his own currently. I\’m currently fiddling around with a server/client program that allows me to send a signal from one computer to another. I tested both on the same computer and they did rather well for the most part. however, I want to see if I can connect with computers on a different network.

-update- i'm currently programming in C# and have both my client and server programs all written out.

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.IO; using System.Net; using System.Net.Sockets;

namespace TCPServer { class Program { static void Main(string\[\] args) { TcpListener listener = new TcpListener(IPAddress.Parse("127.0.0.1"), 8000); Console.WriteLine("About to initialize port"); listener.Start(); Console.WriteLine("Listening for a connection"); try { using (TcpClient client = listener.AcceptTcpClient()) { Console.WriteLine("connection accepted."); NetworkStream stream = client.GetStream(); using (BinaryWriter w = new BinaryWriter(stream)) { using (BinaryReader r = new BinaryReader(stream)) { if (r.ReadString() == Sharedata.RequestConnect) { w.Write(Sharedata.AcknowledgeOK); Console.WriteLine("Connection complete.");

```
                            while ( r.ReadString() != Sharedata.Disconnect)
                            {
                            }
                            Console.WriteLine(Environment.NewLine);
                            Console.WriteLine("Disconnect request received.");
                        }
                        else
                        {
                            Console.WriteLine("Can't complete connection");
                        }
                    }
                }
            }
            Console.WriteLine("Connection Complete");
        }
        catch(Exception ex)
        {
            Console.WriteLine(ex.ToString());
        }
        finally
        {
            listener.Stop();
            Console.WriteLine("Listener stopped");
        }
        Console.WriteLine(Environment.NewLine);
        Console.WriteLine("Main method complete. Press Enter");
        Console.ReadLine();

    }
}
public class Sharedata
{
    public const string AcknowledgeOK = "OK";
    public const string AcknowledgeCancel = "Cancel";
    public const string Disconnect = "Bye";
    public const string RequestConnect = "Hello";
}

```

}

and here's the client code

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.IO; using System.Net; using System.Net.Sockets;

namespace TCPClient { class Program { static void Main(string\[\] args) { TcpClient client = new TcpClient();

```
        try
        {
            Console.WriteLine("Attempting to connect to the server on port 8000");
            client.Connect(IPAddress.Parse("127.0.0.1"), 8000);
            Console.WriteLine("Connection establish");
            NetworkStream stream = client.GetStream();
            using (BinaryWriter w = new BinaryWriter(stream))
            {
                using (BinaryReader r = new BinaryReader(stream))
                {
                    w.Write(Shareddata.RequestConnect);
                    if ( r.ReadString() == Shareddata.AcknowledgeOK)
                    {
                        Console.WriteLine("Connected.");
                        Console.WriteLine("Press Enter to disconnect.");
                        Console.ReadLine();
                        Console.WriteLine("Disconnecting...");
                        w.Write(Shareddata.Disconnect);
                    }
                    else
                    {
                        Console.WriteLine("Connection not completed.");
                    }
                }
            }
        }
        catch (Exception err)
        {
            Console.WriteLine(err.ToString());
        }
        finally
        {
            client.Close();
            Console.WriteLine("port closed.");
        }
        Console.WriteLine(Environment.NewLine);
        Console.WriteLine("Main method complete. Press Enter");
        Console.ReadLine();
    }
}
public class Shareddata
{
    public const string AcknowledgeOK = "OK";
    public const string AcknowledgeCancel = "Cancel";
    public const string Disconnect = "Bye";
    public const string RequestConnect = "hello";
}

```

}

so far I ran both programs together and so far it seems the client one is having issue when it's ran for extended periods of time.

# Answer
> 1 votes
I intend this to give you a general idea of what to do next, I have not reviewed your code 100% so as a student you have to figure out where to plug in the pieces I give you.

In your server code you don't need to specify an IP address, using a call like this will get it automatically:

```
TcpListener serverSocket = new TcpListener(8000);
            TcpClient clientSocket = default(TcpClient);

```

Then on your client, assuming you are running on the same subnet, you put in the servers IP address and (in this case) port 8000. Let's assume your server is on 192.168.1.10:

```
clientSocket.Connect("192.168.1.10", 8000);
            serverStream = clientSocket.GetStream();

```

Now that's just a simple answer designed to get you going in the right direction, perhaps someone else will provide a more complete answer.

In addition you are assuming the connection is established, you probably will want to study Exceptions at some point, a simple example on the client side is:

```
try
        {
            clientSocket.Connect("192.168.1.10", 8000);
            serverStream = clientSocket.GetStream();
            // do some processing here
        }
        catch (SocketException ex)
        {
            // oops something specific failed!
            Console.WriteLine(ex);
        }
        catch (Exception ex)
        {
            // oops an exception we didn't expect happened!
            Console.WriteLine(ex);
        }

```

Here's the information you can look up telling what exceptions clientSocket can throw

Take a look at this StackOverflow question and you'll see where I got the try-catch example.

Here are more examples: http://csharp.net-informations.com/communications/csharp-chat-server.htm http://csharp.net-informations.com/communications/csharp-chat-client.htm

---
Tags: computer-networks
---


# Question
Title: Can any algorithm efficiently be implemented as a SIMT problem?
Many algorithms can be implemented more efficiently using SIMT instructions (e.g. CUDA) than using sequential instructions.

Excluding overhead due to hardware limitations (specifically, memory copy times when using a GPU) - are there algorithms whose efficiency *can **only** be made worse* in a SIMT model? By "efficiency," I mean here the total number of elementary operations / # parallel processing elements.

(Assume that each individual compute element in the SIMT model is (made to be) exactly as fast as the single compute element in the sequential model. Therefore, computing time is the same as the number of elementary operations.)

Asked another way, can *any* algorithm be made *at least as efficient* using SIMT instructions than it could using sequential instructions? Again, I'm purely talking about computing "time" here - not set up / memory copies (which are the typical reason why you wouldn't use a SIMT processor for a highly sequential problem AFAIK).

# Answer
> 1 votes
No, efficiency cannot be strictly worse, for trivial reasons. For instance, you can have all $n$ threads independently compute the same thing -- each doing the same thing that the sequential computation would have done.

This is not very interesting or useful in practice, for a number of reasons: (1) in practice, in SIMT architectures each individual compute element is typically less powerful than the compute element in a sequential system; (2) we care not just about compute time but about energy usage, and wasting energy on pointless computation would be, well, pointless.

At the same time, it *is* true that there are computational tasks that are inherently sequential: they cannot be sped up on a parallel processor (including a SIMT machine). See, e.g., Which algorithms can not be parallelized?, https://crypto.stackexchange.com/q/606/351.

---
Tags: efficiency, parallel-computing
---


# Question
Title: Efficient formulation for binary integer linear programming
**Problem**:

There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either:

1. nothing, or
2. 1 S, or
3. 1 B, or
4. 2 S, or
5. 2 B, or
6. 1 B and 2 S

We are given the weight (float not integer) of each ball (in array $w$). There are some constraints on the weights of the boxes and balls:

1. The total weight of a box $ \leq T$
2. In configurations 4 and 6 above, the difference of S should be $ \leq D$
3. In configuration 6 above, the weight of 2 S should be $\geq$ weight of 1 B

Now I want to minimise the number of boxes used.

**My approach**

I have modelled this as a linear programming problem with binary variables.

Let there be $M$ boxes, $N\_S$ small balls and $N\_B$ big balls.

Decision variables:

1. $b1\_j$ is a binary variable which is $1$ if box $j$ is in configuration $1$, else $0$. Similarly for $b2\_j, b3\_j, b4\_j, b5\_j, b6\_j$ for each box $j$.
2. $x\_{ij}$ is a binary variable which is $1$ if ith big ball is in box $j$, else $0$.
3. $y\_{ij}$ is a binary variable which is $1$ if ith small ball is in box $j$, else $0$.

Constraints:

1. Total weight of any box $\leq T$ $$\sum\_{i}x\_{ij}w\_i + \sum\_{i}y\_{ij}w\_i \leq T \qquad \forall \\, j$$
2. Weight difference constraint: $$y\_{ij}w\_i-y\_{kj} w\_k \leq D \qquad \forall \\, i,j,k$$
3. Each ball used exactly once: $$\sum\_{j}x\_{ij}=1 \qquad \forall \\, i$$ $$\sum\_{j}y\_{ij}=1\qquad \forall \\, i$$
4. Each box is exactly one configuration: $$b1\_j+b2\_j+b3\_j+b4\_j+b5\_j+b6\_j=1$$ Similarly for other constraints. I hope you get the way I am trying to solve this.

Now the problem is this approach is taking a lot of time to solve using PuLP. For just 15 balls and 10 boxes it took minutes and time is increasing exponentially as the balls increase. I want to solve this for at least 100 balls.

Any help would be appreciated.

# Answer
# Integer linear programming

Let me suggest another way of formulating this with ILP that might be worth trying. Define *combination* to mean a list of all of the balls in a single box. For instance, the combination might be (7,15) meaning that the box contains ball 7 and ball 15. Of course, we can enumerate all legal values for the combination, i.e., for the contents of a single box. There will be at most $1+N\_S+N\_B+N\_S(N\_S-1)/2+N\_B(N\_B-1)/2+N\_B N\_S(N\_S-1)/2$ different combinations (fewer in practice due to the constraints on the difference of weights and the total weight of a box).

Now introduce a binary variable $x\_{ij}$ that is 1 if the $i$th box contains combination $j$. Here $j$ is an index that ranges over all possible legal choices for the combination, i.e., for the contents of a single box. (Don't include any illegal combinations.)

We get some linear inequalities from this:

* For each box, we must select one combination for it to contain: $\sum\_j x\_{ij} \le 1$.
* Each ball must be used exactly once: $\sum\_i \sum\_{j \in B\_k} x\_{ij}=1$, where $B\_k$ is the set of legal combinations that include ball $k$.

Now you can test feasibility, i.e., test whether it is possible to pack all of the balls into some given number of boxes.

For example, suppose we have 5 big balls and 10 little balls and 10 boxes. Then there will be at most about 300 legal combinations (probably fewer), so there will be about 3000 binary variables. I don't know whether PuLP will be effective, but you could give it a try.

# Exact cover

Even better yet, one can note that your problem is an instance of the exact cover problem. The universe is the set of balls; each combination is a subset of the universe; and we want to find a way to cover the universe by a disjoint union of the combinations.

There are dedicated algorithms for the exact cover problem that might be faster than expressing this as an integer linear program and applying an ILP solver.
> 2 votes

---
Tags: efficiency, linear-programming, integer-programming, modelling
---


# Question
Title: Finding a maximal set of nonintersecting line segments in a unit circle
Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning several lines can share points. I need to find the biggest subset of S of non intersecting lines. Lines that share an end point are treated as intersecting.

In the great piece of art above, n = 3 and m = 2, connecting all dots will form an equilateral triangle, and the two lines are intersecting.

What I tried doing is to apply dynamic programming, but I can't formulate a recursive relation. I tried enumerating the point P = {1,2,...,n} and claiming something like "Let C\[k\] be the largest subset using only point from 1 to k etc..." but couldn't relate it to k - 1, plus I didn't take advantage of the fact the the points divide the circle into equal pieces.

Any clues\help will be vastly appreciated. :)

# Answer
> 2 votes
For intervals we have got a similar problem.

In the case of interval two intervals $(x\_i,y\_i)$ and $(x\_j,y\_j)$ are intersecting if $x\_i \leq y\_i \leq x\_j \leq y\_j $ or $x\_j \leq y\_j \leq x\_i \leq y\_i$ is not true.
The problem for intervals is discussed in Maximum non-overlapping intervals in a interval tree.

In your case however lines are intersecting only if you have $x\_i \leq x\_j \leq y\_i \leq y\_j \leq x\_i$ in circular order. Here $x\_i$ and $y\_i$ are the circumference distance from a fixed point say the top point.

As suggested in the solution for intervals you can either apply dynamic programming or the greedy algorithm.

---
Tags: algorithms, computational-geometry, dynamic-programming
---


# Question
Title: What is the origin of using Q to denote a set of states in an automaton?
When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q\_0$, $q\_1$, etc.

Is there a particular reason why the letter $Q$ was chosen? As in, is $Q$ the first letter of a word historically related to automata? Or was it chosen totally arbitrarily?

# Answer
> 6 votes
The symbol $q$ to denote the state of a finite automaton appears (for the first time??) in Moore's 1956 paper Gedanken-Experiments on Sequential Machines and since the paper became very popular, I suppose that Moore's notation has been adopted since then. Apparently, Moore didn't use any special notation for the set of states, but it you adopt $q$ for a state, $Q$ seems to be an obvious choice for the set of states.

I don't think there is any special meaning for the letter $q$ (or $Q$).

\[1\] E.F. Moore, Gedanken experiments on sequential machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, 129–156. Princeton University Press, 1956.

---
Tags: automata, finite-automata, notation, history
---


# Question
Title: DFA to regular expression how to deal with 'sink state'
Didn't find a clear statement on this so I just want to make sure I'm right. If I have DFA with edges leading to a 'sink state' (non-accepting state we don't get out of) the edges leading to the sink state and the edge from the sink to itself won't get any representation in the regular expression right? We can just remove those edges and stated at the beginning.. Am I right?

# Answer
> 2 votes
Yes, if you have a DFA with a state $q\_{rej}$ acting as a sink state, then it is there only for the formal definition of the DFA, so that our DFA will "know" to reject any other inputs that loop in there. An NFA on the other hand, does have to have a sink state, and you can just erase it. A DFA must describe what to do on each input, whether it is an input that will be accepted or whether rejected. An NFA describes which words you will accept, it has no need to describe which you reject. A regular expression works on the same principal, it only describes which inputs you accept, it does not describe which are rejected.

Hope this clarified your question.

(note that you cannot remove those edges and the sink state in the DFA, because, as stated above, a DFA must decide an answer on **each** input, even if it loops in a sink state. Removing it will result in an NFA)

# Answer
> 1 votes
It depends on the definition you take for a DFA. If you insist that your DFA should be *complete*, that is, if the transition function is a total function from $Q \times A$ to $Q$, then you need to keep the sink state. But if you consider an *incomplete* DFA (that is, the transition function is only a partial function from $Q \times A$ to $Q$), then you can remove the sink state.

---
Tags: finite-automata, regular-expressions, simulation, dfa
---


title: Data interchange in two registers

text:
# Question
Title: Data interchange in two registers
This picture is from Computer System Architecture 3rd Edition by Morris Mano. Is it possible to interchange the data of any two registers in a single clock pulse? I know that the data of DR (data register) and AC (accumulator register) can be interchanged in a single clock pulse. But other than this I don't understand how data replacement between two registers can be accomplished. Thank you.

# Answer
Just count the busses. Most of the registers in this design only have an input from the single common bus. The only exception is the ACcumulator, which also has an input from the DR.
> 1 votes

---
Tags: computer-architecture, cpu
---


title: merge sort merge phase

text:
# Question
Title: merge sort merge phase
I'm watching a video, demonstrating merge sort, https://www.youtube.com/watch?v=EeQ8pwjQxTM

At 5:42, happens something I do not understand.

We are merging last 2 big arrays, `[4,15,50,108]` and `[8,16,23,42]`. My understanding is - we pick each pair, since they are already in sorted arrays, and swap them if one is larger than the other. So it goes well, until 23 is smaller than 50, and next element is 42 which is smaller than 108 and we end up with `[4,8,15,16,23,50,42,108]`.

Obviously, my understanding is faulty. But I heard no indication we go we compare each element in first array with all the elements of second one. Did I miss it? If so, how's the `n log n` complexity achieved, since we do `n^2` operations?

# Answer
## How does the merging work?

Imagine two pointers, starting at the first element of each array. In this example I will use the #-Symbol to indicate the pointers.

**This is your start configuration:**

`[#4,15,50,108]`

`[#8,16,23,42]`

`[ ]`

Now you always compare the elements, that the pointers are pointing at and move the smaller element to the merged list. Then you move the "winning" pointer to the next element. The "loser" pointer does not move. If a pointer reaches the end of the list, the other pointer always wins.

**This is your result after the first comparison:**

`[4,#15,50,108]`

`[#8,16,23,42]`

`[4]`

4 won the comparison and therefore is added to the merged list. The pointer is moved to the next position. Now we start over and compare 15 and 8 resulting in this configuration:

`[4,#15,50,108]`

`[8,#16,23,42]`

`[4, 8]`

This process continues until each element is in the merged list.

**After comparing 15 and 16:**

`[4,15,#50,108]`

`[8,#16,23,42]`

`[4, 8, 15]`

**After comparing 50 and 16:**

`[4,15,#50,108]`

`[8,16,#23,42]`

`[4, 8, 15, 16]`

**After comparing 23 and 50:**

`[4,15,#50,108]`

`[8,16,23,#42]`

`[4, 8, 15, 16, 23]`

And so on...

In code these pointers could be realised by using indexes for the lists (increasing them when the pointer has to move) or using queues (always taking the first element).

## How is it $O(n\*log(n))$ if we do $O(n^2)$ Operations?

Because we dont. During the merge process, every element is still only visited once (you never decrease a pointer). If your merge algorithm has two lists of length $n$ for arguments, then it needs $O(2\*n)$-Time but $O(2\*n) = O(n)$. And with merging in $O(n)$, merge sort is in $O(n * log(n))$.
> 2 votes

# Answer
We do not compare elements in both the arrays one to one. We only keep smaller element and recompare the larger element. For example

4 ? 8

4 is smaller 8 is larger so we keep 4 and our two arrays are now \[15, 50, 108\] and \[8, 16, 23, 42\].

15 ? 8

8 is smaller 15 is larger so we keep \[4, 8\] and our two arrays are now \[15, 50, 108\] and \[16, 23, 42\].

After this we compare and keep the elements as below

Compare 15 ? 16, keep \[4, 8, 15\]
Compare 50 ? 16, keep \[4, 8, 15, 16\]
Compare 50 ? 23, keep \[4, 8, 15, 16, 23\]
Compare 50 ? 42, keep \[4, 8, 15, 16, 23, 42\]
Second array is empty so keep \[50 108\] in th end.
Thus we have \[4, 8, 15, 16, 23, 42, 50, 108\] as merged array.

For analysis head over to the solution of Recurrence Relationship for Divide and Conquer or you can learn about Master Theorem, which is more general. $T(n) = 2T(n/2) + O(n)$ is solved in Case 2 of the wiki article.
> 2 votes

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


# Question
Title: String searching, where we allow characters to almost-match
Let $\Sigma= \\{1,...,n\\}$. Let $T$ and $Q$ be two strings with characters from the alphabet $\Sigma$ of lengths $n,k$, respectively. I am looking for an algorithm to test whether $Q$ appears as a substring of $T$, except that I have a more relaxed notion of when two characters match.

Two characters in these strings are *similar* if $|Q\[j\] - T\[l\]|\leq 1$. Call the indices $i,j$ a *good pair* if $|Q\[j\] - T\[j+i-1\]|\leq 1$, that is if the characters in the $j+i-1$'s cell in $T$ and the $j$'s cell in $Q$ are similar. An index $i$ is *good for all* if for all $1\leq j \leq k$, the pair $i,j$ is a good pair.

I'd like to find all the good-for-all indices. That is, I aim to find all the indices $1\leq i\leq n$ s.t. for all $1\leq j \leq k$, we have $|Q\[j\] - T\[j+(i-1)\]|\leq 1$.

I'm at a loss even where should I begin from. Obviously I can solve naively, but this is not interesting at all. I'm not even sure what should be the optimal time for this problem. Also, I don't see any lower bound on the running time (except $O(n)$ obviously).

How efficiently can we find all the good-for-all indices? What algorithm can I use for this?

# Answer
> 3 votes
You're looking for all instances of $Q$ as a substring of $T$, except that two symbols are still considered to match even if they differ by one, so this is basically a generalization of substring search (string matching).

This particular problem can be solved efficiently using convolution methods. The running time will be something like $O(n \lg n)$, times some small factors. Let me outline the algorithm, and then explain why it works.

# The algorithm

**Step 1**: We will construct binary strings $T' \in \\{0,1\\}^{6n}$, $Q' \in \\{0,1\\}^{6k}$, with a special property:

* If index $i$ is good-for-all, then there are $\ge k$ indices $j$ where both $T'\_j$ and $Q'\_{j+6i}$ are 1.
* If index $i$ is not good-for-all, then with probability at least $1/2$, there are $\< k$ indices $j$ where both $T'\_j$ and $Q'\_{j+6i}$ are 1.

Let me outline how to construct $T',Q'$. First, pick a random hash function $h:\Sigma \to \\{1,2,\dots,6\\}$. Next, define a code $C\_T:\Sigma \to \\{0,1\\}^6$ like this: $C\_T(x)$ is a 6-bit string that is 1 at index $h(x)$ and 0 at all other positions. Also, define a code $C\_Q:\Sigma \to \\{0,1\\}^6$ as follows: $C\_Q(x)$ is a 6-bit string that is 1 at indices $h(x)$, $h(x-1)$, and $h(x+1)$, and 0 at all other positions.

Finally, define the binary string $T'$ to be the concatenation of codewords

$$T' = C\_T(T\[0\]) C\_T(T\[1\]) \cdots C\_T(T\[n-1\]),$$

and similarly $Q'$ to be the concatenation of codewords

$$Q' = C\_Q(Q\[0\]) C\_Q(Q\[1\]) \cdots C\_Q(Q\[k-1\]).$$

You can check that these two strings satisfy the properties above.

**Step 2**: We will use convolution (polynomial multiplication) to find all indices that are good-for-all. Define polynomials $T(x),Q(x)$ from the binary strings $T',Q'$ as follows:

$$\begin{align\*} T(x) &= \sum\_j T'\_j x^j\\ Q(x) &= \sum\_j Q'\_j x^{6k-1-j} \end{align\*}$$

Multiply these two polynomials to get the polynomial $P(x) = T(x) Q(x)$. Let $p\_i$ be the coefficient of $x^i$ in $P(x)$, so that $P(x) = \sum\_i p\_i x^i$.

We have the following nifty property: $p\_{6k-1-6i}$ counts the number of indices $j$ where both $T'\_{j}$ and $Q'\_{j+6i}$ are 1. Thus, we can immediately read off a set of "suggested" indices that are "suggested good-for-all". Every index that is actually good-for-all will appear in that set, and every non-good-for-all index has at most a probability $1/2$ of appearing in the set of "suggested" indices.

**Step 3**: Repeat Steps 1 and 2 80 times, and keep only those indices that are suggested in every iteration. Output that list.

# Correctness

All of the good-for-all indices will remain and appear in the output. Also, there's at most a $n/2^{80}$ probability that any non-good-for-all index survives all 80 iterations. This probability is small enough as to be negligible.

# Running time

The running time of this algorithm is dominated by the time to multiply two polynomials of degree $6n,6k$. Assuming $n \ge k$, this running time is basically $O(n \lg n)$ (ignoring log-log factors) using standard techniques.

In practice there are a number of ways one could optimize this further. For instance, we can often stop early without doing all 80 iterations: once the set of surviving suggested indices is small enough, we can just check each one directly and output only the correct ones.

# Other approaches

Since your problem is a generalization of string matching, you could also look at other algorithms for string matching and see if any of those techniques can be generalized to your situation. For instance:

* It would be straightforward to adapt finite automaton based search methods: you can build an automaton based on $Q$ that accepts all strings that would match $Q$ as a substring (where "match" allows two similar characters to be treated as matching). Building such a DFA might be very slow, but once you have the DFA, testing whether $T$ is a match can be done very fast -- in linear time.
* It might be possible to adapt the Knuth-Morris-Pratt algorithm to your situation. It might take some thought to work out the details, but if it works out, you might get a linear-time algorithm, i.e., $O(n)$ running time.
* Also, take a look at Boyer-Moore.

I would especially suggest you take a look at KMP -- it looks plausible to me that this might yield a viable algorithm.

---
Tags: algorithms, strings, string-metrics, substrings
---


# Question
Title: Is the memory usage of total languages deterministic?
I'm interested in the memory usage of various programming languages when implemented on actual hardware.

I believe that a Turing-complete programming language has, in general, unknowable memory usage since object lifetimes are not statically analyzable \[1\]. It also seems like a regular expression language (in the deterministic finite automata) has statically known memory use.

What is the most complex programming language for which that is true? And where do total languages \[2\] fall in relation to that?

\[1\] Given the caveat that we're implementing that programming language on a physical computer with all its requisite limitations.

\[2\] A total language is, for the purposes of this question, a language where all programs written in it are guaranteed to terminate.

# Answer
> 2 votes
Because total programs cannot run forever they cannot use infinite memory. You can know maximum, and best case cost from looking at what algorithm is implemented. Checkout these wikipedia pages to see the relationship between different grammars, algorithms, and machines:

---
Tags: computability, programming-languages, memory-management, performance, space-analysis
---


title: Equivalence of regular grammars

text:
# Question
Title: Equivalence of regular grammars
I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving that two regular grammars recognize the same language decidable?

# Answer
> 5 votes
Yes, this is decidable. There's a rather direct conversion from a regular grammar to an NFA. From there, run the subset construction to turn the NFAs into DFAs. Run minimization algorithms to convert each DFA to a canonical minimum DFA, then decide whether the two DFAs are equivalent. Each transformation preserves the language represented, so this ultimately decides whether the two grammars have the same language.

---
Tags: computability, regular-languages, formal-grammars, decision-problem
---


# Question
Title: will breaking not used anymore RSA codes in the future affect privacy?
just read and watch some stuff on how RSA works. main idea seems to be if someone steals your communication he cannot decode it anyway.

but let's say someone steals it and keeps it along with current RSA-1024 used. if in 10 years he will be able to break this RSA can he decode our communication and passwords from 10 years ago?

# Answer
> 2 votes
Anybody who knows the cyphertext and the decryption key can decrypt the message. It doesn't matter how they obtained the cyphertext or the key, or how much time has elapsed since the message was encrypted; anyone who has both of those things can decrypt.

---
Tags: cryptography, security
---


# Question
Title: How do I find the number of inversions using a red black tree?
I'm trying to figure out a way to find the number of inversions in permutation time O(nlogn) using red black trees. Here's how I think it can be done. So if I have an algorithm that inserts a new node into a red black tree then by inserting the node if it inserts properly then it means the values are in the proper order and there's no inversions. If a value is inserted and the order property is not satisfied then we need to either rotate the tree or change the color of the branches to satisfy the order property. So I have an insert method that looks like this:

```
private Node put(Node h, Key key, Value val){
        if(h==null)
            return new Node(key, val, 1, RED);
        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, key, val);
        else if (cmp > 0) h.right = put(h.right, key, val);
        else h.val = val;

        if (isRed(h.right) && !isRed(h.left))
            h = rotateLeft(h);

        if (isRed(h.left) && isRed(h.left.left))
            h = rotateRight(h);

        if (isRed(h.left) && isRed(h.right))
            flipColors(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

```

Now if I declared a variable that kept count of all the inversions then at what points would I need to put it at and is there any code that is unnecessary when counting the inversions? What I'm thinking of doing is replacing all the rotations and color changes with inversion incrementing. Would doing that still give me the right number of inversions in O(nlogn) time?

# Answer
What you are trying to do is correct. However only number of rotations will not be able to tell you anything about the inversions. The whole procedure is as follows.

You start with an empty red-black tree. Then you insert the elements in the given sequence one by one, in the order that they occur in the sequence.

Whenever an element $x$ in the sequence is inserted, the elements larger than $x$ already existing in the red-black tree are inversions. You need to calculate this number.

You total up all the inversions for all elements and you get the total number of inversions.

You need to augment the red-black tree by keeping the size of sub-trees in the interior nodes. Then you can find the number of elements larger than $x$ either during insertion or after insertions by doing a search of element $x$.

Since you are confused about the strategy, I suggest you should use the second method. Don't count the larger elements during the insertion stage. Count them immediately after the insertion is done and before another insertion is to be done (in a separate function). This will take additional $O(\log n)$ on the augmented tree.

If all your numbers are distinct then this algorithm suffices. However, if some numbers are same, then you have to modify your insertion to insert only at the rightmost possible position and/or counting only the strictly larger elements depending on your algorithm. You will need to further augment the data structure to hold the min-value and max-value of the sub-tree in the node.
> 3 votes

---
Tags: algorithms, trees, counting, balanced-search-trees
---


# Question
Title: How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism?
I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem.

Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the Hamiltonian Cycle - Subgraph Isomorphic connection, @Luke Mathieson says that "Hamiltonian Cycle to Subgraph Isomorphism is really just rephrasing what it means for a graph to have a Hamiltonian cycle" - but I don't get it.

How does one transforms from Hamiltonian Cycle to Subgraph Isomorphism?

I read Reducing from Hamiltonian Cycle to Subgraph Isomorphism and https://en.wikipedia.org/wiki/Subgraph\_isomorphism\_problem and couldn't understand how should a proper reduction look like, how to build one that proves the subgraph problem?

Your help in simplifying the problem(s) will be very appreciated.

# Answer
> 2 votes
Reduction $HC \leq SubgraphIsomorphism$ is done as $G \rightarrow \langle G, C\_n \rangle$ where $n$ is the number of vertices in $G$, and $C\_n$ is the cycle graph with $n$ vertices. This effectively means that $G$ has a subgraph $C\_n$ if and only if $G$ has a Hamiltonian Circuit.

There are mainly three types of common reductions. $A \leq\_L B$, $A \leq\_P B$ and $A \leq\_M B$ i.e. log-space reduction, polynomial-time reduction and turing reduction. If we don't specify, it usually means polynomial-time reduction which is also known as Karp reduction.

Let us take $A \leq\_P B$. It means we can transform an input $x$ of problem $A$ to an input $f(x)$ of problem $B$ in polynomial-time such that *(and this is important)* $x$ is a yes-instance of $A$ if and only if $f(x)$ is a yes-instance of $B$. This effectively gives us a polynomial-time algorithm to check yes-instances of problem $A$ if there is a known polynomial-time algorithm to check yes-instances of problem $B$.

Now if $A$ is known to be a tough problem, like Hamiltonian Circuit problem, then $A \leq B$ will imply that $B$ is also a tough problem. That is, since $HC$ is NP-complete, SubgraphIsomorphism is also NP-complete (as we also know additionally that Subgraph Isomorphism is in NP, otherwise we would have only shown its NP-hardness).

---
Tags: complexity-theory, np-complete, reductions, hamiltonian-path, graph-isomorphism
---


# Question
Title: Relationship of algorithm complexity and automata class
I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm. For example is there a range of complexity push down automata can express? If the answer is yes to said question is there a resource depicting the relationship? Thanks!

# Answer
Yes, there are relationships in many cases!

For example, it is known that any language which is accepted by reversal-bounded counter machines are in $P$ (see here).

Similarly, we know that all regular languages are in $P$, since there's a polynomial time algorithm for determining if an NFA accepts a given word.

There are too many to enumerate here, but in general, more limited computation models are in easier complexity classes.
> 8 votes

# Answer
Here are some known results:

1. $\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, where $\mathsf{REG}$ is the set of regular languages. For proofs, see the Wikipedia page on $\mathsf{DSPACE}$.
2. $\mathsf{DCFL} \subseteq \mathsf{SC}$, where $\mathsf{DCFL}$ is the set of deterministic context-free languages, and $\mathsf{SC}$ is Steve's class. See the Wikipedia page on $\mathsf{DCFL}$.
3. $\mathsf{NL} \subseteq \mathsf{LOGCFL} \subseteq \mathsf{AC^1}$, where $\mathsf{LOGCFL}$ is the set of languages logspace-reducible to a context-free language. See the Wikipedia page on $\mathsf{LOGCFL}$, which also gives some languages complete for $\mathsf{LOGCFL}$ under logspace reductions.
4. $\mathsf{CSL} = \mathsf{NSPACE}(n)$, where $\mathsf{CSL}$ is the set of context-sensitive languages. See the Wikipedia page on $\mathsf{CSL}$.
5. The class of languages accepted by deterministic nonerasing PDAs is $\mathsf{DSPACE(n\log n)}$, and the class of languages accepted by non-deterministic nonerasing PDAs is $\mathsf{NSPACE}(n^2)$. See the Wikipedia page on PDAs.
6. Two-stack automata are equivalent in power to Turing machines, but restricting the automata results in weaker models. See a technical report of San Pietro.
> 11 votes

# Answer
> Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm.

The question which *class of automata* can implement a given *algorithm* like quick sort is tricky, because it is unclear what would count as an implementation of that algorithm. For quick sort, the performed comparisons should certainly be the same, but must the order in which the comparisons occur also be the same? What about the order of read accesses to specific elements of the input? The order of copy, move and swap operations for specific elements?

You would have to specify quite a number of *oracles* for those operations which matter to you, but then you are already in a very specific situation based on the algorithm, and quite far from the general classes of automata commonly studies. The way around this dilemma is to talk about problems instead of algorithms, and formalize problems by talking about languages.

> For example is there a range of complexity push down automata can express?

Not really, because a push down automata can read its input only once and only in forward direction. However, if you split the machine into a part which is allowed to read the input forward and backward as it wishes, and maintain a finite number of pointers to specific input positions (NL), and a part which is a push down automata that receives its input from the other part, then you get the complexity class LOGCFL, which is equal to SAC1 (a circuit class).

If you don't separate those two parts and just add a stack to NL, then you get the automata class AuxPDA, which is equal to the complexity class . But if you decide to limit the runtime of that automata (with stack and logarithmic auxiliary storage) to polynomial time, then you get NAuxPDAP, which is again equal to LOGCFL. (And if you insist on deterministic polynomial runtime, scrap the stack, but allow polylogarithmic auxiliary storage, then you get SC.)

On the other hand, if you keep the restriction that the automata can read its input only once and only in forward direction, and additionally require that it can use its stack only in a very deterministic way directly based on the input (i.e. the input symbol determines whether that automata pushes something on the stack, pops something from the stack, or leaves the stack untouched), then you end up with a visibly pushdown automata, which recognizes exactly the nested word languages, which can also be recognized in deterministic logarithmic space.
> 4 votes

---
Tags: complexity-theory, automata, reference-request, complexity-classes
---


# Question
Title: Why is the dynamic programming algorithm of the knapsack problem not polynomial?
The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack.

Why is this not a polynomial-time algorithm?

I have read that one needs $\lg W$ bits to represent $W$, so it is exponential time. But, I don't understand, one also needs $\lg n$ bits to represent $n$, doesn't one? So, for example, merge sort is not polynomial time, because its complexity is $O(n\lg n)$ and one needs $\lg n$ to represent $n$?

What am I missing here?

# Answer
When we say polynomial or exponential, we mean polynomial or exponential *in some variable*.

$nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a function of the *size of the input*.

This is where the argument about $\log W$ comes in. Ignoring the values of the items for the moment (and considering only their weights), the input of the knapsack problem is $n$ numbers $\leq W$. Each number is represented with $\log W$ bits, and there are $n$ numbers, so the size of the instance is $n\log W$.

This makes $nW$ not polynomial in the size of the instance, since $W$ is exponential in $\log W$.

However, (coming back to your example about sorting) an instance for sorting consists of $n$ elements to be sorted, and representing these takes at least $n$ bits (and probably a bit more, since the elements themselves are probably bigger than $1$ bit each). We can represent *the number* $n$ using $\log n$ bits, but we can't represent $n$ things using $\log n$ bits.

The main difference is that $W$ represents a number in the input, while $n$ represents "the number of things".

Note that if we were to "cheat", we could represent $W$ using $W$ bits if we used a unary encoding. This version of the problem is technically polynomial, but really only because we were deliberately being less efficient.

It turns out that there is a whole class of Strongly NP-Hard Problems, which are still NP-hard even when the input is represented in unary format. But Knapsack is not one of these problems.
> 16 votes

# Answer
> I have read that one needs $\lg W$ to represent $W$ so it is exponential-time. But, I don't understand, also one needs $\lg n$ to represent $n$, no?

This is a great question. You need to look at what the input actually is. The input consists of $n$ items, each of which has a weight $w\_i$ and value $v\_i$, plus the capacity $W$ of your knapsack.

Each of the $w\_i$w, the $v\_i$s and $W$ is a number, written in binary. In particular, each $w\_i$ and $v\_i$ must be at least one bit, so the length of the input is at least $n$ bits (well, even $2n$ bits). You're absolutely correct that it takes $\log n$ bits to write $n$ in binary and $\log W$ bits to write $W$. But the point is that $n$ isn't written out in binary as part of the input.
> 3 votes

---
Tags: algorithm-analysis, runtime-analysis, dynamic-programming, knapsack-problems, pseudo-polynomial
---


# Question
Title: Partitioning a set to the maximum number of subsets summing to zero
Given a multiset of numbers $X = \\{x\_1, \dots, x\_n\\}$, such that $\sum X = 0$, how can $X$ be partitioned to the *maximum number* of subsets so that each subset sums to zero?

I have searched around a lot, but none of the partition or packing problem variants seem to address this particular case.

# Answer
> 5 votes
3-Partition reduces to this problem, so it's strongly $NP$-hard. Moreover, 4-Partition also reduces to it (and the blowup is linear), so assuming the exponential time hypothesis there's no $2^{o(n)}$ algorithm.

Using dynamic programming there's a $O^\*(4^n)$ algorithm, it would be interesting if you could do $2^n$ or even $1.99^n$.

---
Tags: algorithms, sets
---


# Question
Title: Is it computationally possible to voice-recognize and word-tag-time-align audiobooks to their actual text?
I would like to know whether it is computationally possible for a computer to go through the words of an audiobook as input, output a file containing both the original audio and the text corresponding to each word (which could be reviewed by a human), and a silent software tag between each word marking each word boundary.

*How much of this process could be automated, and how much of it would have to be carried out by a human?*

This process would yield a file where instead of just being able to play, pause, and move forward and backwards by a given number of minutes, as could be done in the original audiofile, we could now also provide the following functionality:

* move back and forth a given number of words
* move back and forth a given number of sentences
* move back and forth a given number of chapters (or subsections)
* spell the current word
* look up the current word in a dictionary
* accurately repeat over and over, the text between any two markers, with a custom number of seconds between each repeat (which is good for learning / memorizing stuff)

Note that while audio books were primarily designed for blind people, has increased functionality would both give them more power as well as empower people with learning disabilities or both.

UPDATE: Since the audiobook is created from a text (either a text file or a textbook which can be read using OCR), I wish the case to be considered where the source words and punctuation are available. My problem is having the computer assign a time t\_(w\_i) to the beginning of each word w\_i and store these in the output sound+wordTimes file (which could be post-edited for inaccuracies by humans). I have not seen anything that does this so far.

This link seems to suggest that what I am trying to do is possible (via a technique called forced alignment).

# Answer
> 3 votes
The fact that humans can understand audio books shows that it is computationally possible. This does not make the problem easy for an AI. It also does not mean that you can write a formalism of the language in audio form for parsing. Anything involving audio / recordings is going to involve lots of fuzzy data. This is not generally what someone would call parsing, but instead speech recognition. If you can properly recognize words in the correct context then the rest of the stuff you mentioned like dictionary lookup, and moving around a book is basically trivial.

It is easier to do this if you already have the words though. I would recommend something like splitting the audio based on breaks, and then applying speech recognition on each section to make sure the word matches the audio that was split. This is to check if errors in splitting exist. If there is an error where the word does not match the audio a human could be prompted to manually split them.

---
Tags: speech-recognition
---


# Question
Title: Algorithm for finding a mouse hole in a wall in O(n) time
There is this question:

> As a result of the US Election, a wall is built along the entire Canadian border. You have been told there is a mouse hole in the wall, but it can only be seen when you are standing in front of it. Your task is to find the mouse hole by walking along the wall; however, you are standing in Minnesota and do not know whether the hole is East or West of your current location.
>
> Give an algorithm that will allow you to find the mouse hole in O(n) steps, where n is the (unknown to you) distance in steps from your initial location to the mouse hole.

I was thinking that to find the mouse hole in `O(n)` steps, I would have to go both East and West at the same time.

But seeing that I can't do this (or maybe I can?), I thought that regardless of direction I first take since I'm traveling around the US border and then around the Canadian border, I would have traveled a linear time. I'm also thinking that this problem might resemble a graph?

How can I go about writing an algorithm to describe this?

# Answer
Here is one strategy. Choose a direction (left or right) arbitrarily. Then go for some number of steps. If found the hole, you are done. Else turn around, and move backwards for a double number of steps. If found the hole you are done. Else return to start. Repeat. In each repetition of this loop, you need to increase the distance you walked. To specify the algorithm, now you need to say for how long you walk until turning back, and how much you increase the distance walked in each consecutive loop. In order for this to be efficient, you want exponential increase, i.e., in iteration $i$ you walk left for $2^i$ steps, then turn walk right for $2 * 2^i$ and return back to start for a total of $4\*2^i = 2^{i+2}$ steps in iteration $i$. Now, if a hole is located at position $n$ = $2^j$ for some $j$ then you will discover it in iteration $j$. By that time you would have walked $\sum\_{i=0}^j 2^{i+2} = 4(2^{j+1}-1) \le 8n = O(n)$ steps.
> 1 votes

# Answer
This problem goes by various names, including the linear search problem and the cow path problem. The solution indicated in Denis's answer is optimal for deterministic algorithms (though the competitive ratio is 9 rather than 8), but randomized algorithms can do almost twice as better; see Kao, Rife and Tate.
> 3 votes

---
Tags: algorithms, data-structures, asymptotics
---


title: Indirect Left recursion

text:
# Question
Title: Indirect Left recursion
I'm resolving indirect left recursion for these production rules:

```
S -> Aa / a   eq1
A -> Sb / b.  eq2

```

Where `S` is the starting symbol.

Now I can do this in two ways:

1. Putting `A` in eq1

So I'll get the solution (sol1):

```
S -> Sba /a /ba

```

and then

```
S -> aS' / baS'
S' -> baS' / epsilon

```
2. Replacing `S` in eq2:

So I'll get the solution (sol2):

```
S -> Aa / a
A -> abA' / bA'
A' -> abA' / epsilon

```

Both seem to be correct. Which is the correct answer?

# Answer
Yes, both your answers are correct. Note that the language under consideration is regular, see wikipedia.

The first grammar is equivalent to this regular expression: $$r\_1 = a(ba)^\* \mid (ba)^+.$$

The second grammar is equivalent to this regular expression: $$r\_2 = (ab)^+a \mid b(ab)^\*a \mid a.$$

It's easy to prove those regexes generate equal languages $L(r\_1) = L(r\_2)$.
> 3 votes

---
Tags: formal-grammars, parsers, left-recursion
---


title: Calculi for a computability class

text:
# Question
Title: Calculi for a computability class
Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the complete set of push down automata, with nothing more powerful.

First question: Can a language exist that expresses up to the power of finite state machines but nothing higher?

Next. Working at the power of Turing machines we have the lambda calculus which with a little bit of sugar is a nice programming language. In addition there are weaker forms of the lambda calculus that are not Turing complete such as the simply typed lambda calculus.

Second question: What calculi exist that cannot express problems above finite state machines, but a programming language could be built on top of. Kind of like the lambda calculus.

Grammars can be restricted to only allow regular languages. This of course does not change the fact that context free grammars can represent regular languages.

Third question: Even though context free grammars allow the expression regular languages, do the methods used to check if a grammar is regular allow the expression of all regular languages? Such as those talked about in "https://en.wikipedia.org/wiki/Regular\_grammar".

These questions are all directly related. Pardon how convoluted this is.

# Answer
You are asking several questions. Let me answer them one by one, though not in the same order.

*Even though context free grammars allow the expression regular languages, do the methods used to check if a grammar is regular allow the expression of all regular languages?* You are misunderstanding the article. One does not *check* that a grammar is regular. Rather, we *define* a grammar as regular if it satisfies the constraints described in the article. Regular grammars indeed generate all (and only) regular languages, and it's not too hard to show this by interpreting them as NFAs (exercise).

As an aside, the following is undecidable: given a context-free grammar, check whether the language it generates is regular.

*Can a language exist that expresses up to the power of finite state machines but nothing higher?* Yes, for example the language of regular expression, the language of DFAs, the language of NFAs, the language of regular grammars, and so on.

*What calculi exist that cannot express problems above finite state machines, but a programming language could be built on top of. Kind of like the lambda calculus.* This question is not really well defined, and it is very easy to cheat. A reasonably natural example is finite automata – if you add two stacks you get a model having the same power as a full-fledged Turing machine.
> 3 votes

---
Tags: computability, finite-automata, formal-grammars, programming-languages, pushdown-automata
---


# Question
Title: What is a limitation of using an array concerning capacity?
Is it that you need a separate method to expand the array whenever it goes over the capacity?

# Answer
Array is defined to have continous memory, so there is a need to extend it by finding continous block that fit it in.
Also the array size is given in advance.
The limit is the largest available continous block and possibility to index it.

For example C defines $malloc$ and $realloc$, which seeks such block (it may start in the same place as original array).
$realloc$ when finds larger region in different place rewrites the content of the array.

If there is no constraint about continous regions - there are lists of arrays used - smaller blocks connected in linked list, easier to grow, but a bit slower to operate on.

Some languages provides growing arrays, but internally it could be stack, list or anything else, so definition of "what is array" is crucial.
> 2 votes

---
Tags: data-structures, arrays
---


# Question
Title: Get the previous and next values of a string in lexicographic order
I'm working with a noSQL database and for certain reasons I can't use equality filtering in my queries

e.g

```
select all from database where id = 10

```

is NOT allowed

but inequality filtering is allowed

e.g

```
select all from database where id > 1

```

My ID's are UNIQUE strings (emails) and I need to use equality filtering so I thought to convert inequality statements to equality statements (e.g where id = 10 could be written as Where id \> 9 AND \< 11).

If my ids were numbers I would use code such as this to get my key:

```
function(id)
{

    //assuming no id can be 0 and no id can be larger than 2^53-1. This will return the row with id = 10
    var result = sendToDatabaseQuery('SELECT * FROM database where id > ' + (id-1) + ' AND ' id < ' (i+1)');

}

```

With numbers it would be very easy to do this, but with Strings I have found it to be more challenging. If I have an email such as mysuperfakeemail.gmail.com how could I get the previous and next lexicographic string (I am assuming they are mysuperfakeemail.gmail.co**l** and mysuperfakeemail.gmail.co**n** respectively)? Is there an established algorithm for this type of function already? I am writing this on a nodejs server with UTF-8 characters.

# Answer
Computing the previous and next lexicographic string is the same as subtracting and adding 1 to a number, only your number is encoded in some higher base corresponding to your alphabet. I presume you already know how to add and subtract 1, but if not, there are many online resources explaining that.

You mention UTF-8, which is not quite an ordered alphabet. Yet your SQL interpreter has some specific rules for ordering strings, and is should include an ordering of the actual alphabet (UTF-8 or smaller).
> 3 votes

---
Tags: algorithms, sorting
---


# Question
Title: Using FFT to solve pattern matching problem with don't cares
I've studied about $FFT$ and it's use in string matching, but there are several issues that bother me. First I'll describe the problem and the solution I've seen in class:
Suppose we have alphabet $\Sigma = (a, b, \phi)$ where $\phi$ is "*don't care*", meaning it matches with every letter, including itself. We have a text $T = t\_{\_0}t\_{\_1}t\_{\_2}...t\_{\_n}$, and a pattern $P = p\_{\_0}p\_{\_1}p\_{\_2}...p\_{\_m}$, assuming $n$ is much bigger than $m$. We say that we have match in index $i$ if for every $0 \leq k \leq m$:
$$P\[k\]=\phi \space or\space T\[i+k\]=\phi \space or\space P\[k\]=T\[i+k\]$$ Therefore we introduced new "multiplication" function over $\Sigma$:
$$ f(a,b) = \begin{cases} 0 & \text{if a = b;}\\ 1 & \text{else;}\\ \end{cases} $$ The idea was to translate every appearance of $a$ and $\phi$ to $0$, and $b$ to $1$, reverse $P \text{ (P$^R = p\_{\_m}p\_{\_m-1}p\_{\_m-2}...p\_{\_0})$}$, treat both strings as polynomial coefficient vectors and multiply them according to the regularity of $f$. Then in their product vector, $C$, indices that are 0's will tell us there's a match starting in that index in text. In order to do that efficiently we used $FFT$, however, $FFT$ works with standard multiplication, so in order to bypass that obstacle we calculated $T^c \cdot P^R +T \cdot (P^R)^c$, where $c$ superscript means to "not" the string, for example: $(100010)^c = 011101$, and $+$ means normal addition of vectors. Now I have 2 questions bugging my mind:
1) How that thing we did in "not"-ing the strings helps solving the problem about the multiplication. I mean I've tried several examples and it works, but why it works?
2) If I wanted to expand this method to bigger alphabet, how could I do it? There's something very binary-oriented in the core of "not"-ing the string, relying on the fact that I have only one pair of letters that create discrepancy.

# Answer
> 2 votes
The idea behind the NOT is that $T^c P^R + TP^{Rc}$ is measuring *disagreement* rather than *agreement*. Disagreement can come in two ways: text says $0$, pattern says $1$ ($T^c P^R$); and text says $1$, pattern says $0$ ($TP^{Rc}$). That's why you need two summands.

In more detail, $T^cP^R$ measures the number of indices at which the text was $0$ and the pattern was $1$; $TP^{Rc}$ measures the number of indices at which the text was $1$ and the pattern was $0$; and their sum measures the number of indices at which the text and the pattern didn't match.

When the alphabet has size $r$, you can use a similar approach with $r$ summands (an even simpler solution uses $r(r-1)$ summands). I'll let you figure out the details. (No hints will be given, and solutions won't be verified.) Extra points if you manage to do this with the (possibly) optimal $\lceil \log\_2 r \rceil$ summands.

---
Tags: algorithms
---


# Question
Title: Difference between the tilde and big-O notations
Robert Sedgewick, at his **Algorithms - Part 1** course in Coursera, states that people usually misunderstand the **big-O** notation when using it to show the order of growth of algorithms. Instead, he advocates for the **tilde** notation.

I understand the **big-O** is an upper bound for certain problem at certain condition.

What is the difference between the **tilde** and **big-O** notations?

# Answer
The $\sim$ notation is similar to the more conventional $\Theta$ notation. There are two main differences between $\sim$ and $O$:

1. $O$ only provides an *upper bounds*, while $\sim$ is simultaneously an upper bound and a lower bound. When we say that the running time of an algorithm is $O(n^2)$, this doesn't preclude the possibility that it is $O(n)$. In contrast, if the running time is $\sim n^2$ then it cannot be $\sim n$.
Another notation with these properties is $\Theta$.
2. $O$ only holds up to a constant: $f = O(g)$ if $f(n) \leq Cg(n)$ for some $C \> 0$ (and large enough $n$). In contrast, for $\sim$ the implied constant is always $1$: if $f \sim g$ then $f/g \to 1$. This contrasts with $\Theta$ in which the implied constant is arbitrary, and indeed there could be different constants for the lower and upper bounds.

Exact constants are impractical in general, for many reasons: they are machine dependent, hard to compute, and could fluctuate depending on $n$. The first problem can be mitigating by measuring some proxy for the actual time complexity, such as the number of comparisons in a sorting algorithm.

Sampling the course, it seems they are using $\Theta$, but call it *order of growth*.
> 13 votes

# Answer
The definitions are that $f(n) = O(g(n))$ if for some constant $c \> 0$ and $N\_0$, you have that $f(n) \le c g(n)$ whenever $n \ge N\_0$. I.e., $g$ gives an upper bound (within a not specified constant). Similar is $f(n) = \Omega(g(n))$, for other constants $c'\> 0, N\_0'$ you have $f(n) \ge c' g(n)$ whenever $n \ge N\_0'$. I.e., a lower bound (within a constant). It is said that $f(n) = \Theta(g(n))$ if both the above are satisfied.

Note that e.g. $n^2 = O(n^3)$, and $n^2 = \Omega(n)$, while $200 n^{1 + 1/n} = \Theta(n)$.

The definition of $f(n) \sim g(n)$ is more demanding: it is that:

$$\lim\_{n \to \infty} \frac{g(n)}{f(n)} = 1$$

No arbitrary constants, the functions grow together. In this sense, it is similar to $\Theta$, but sharper.
> 7 votes

---
Tags: asymptotics
---