# Question
Title: What does it mean to be Turing reducible?
I'm confused about what it means to be Turing reducible. I thought I understood what it meant, but apparently not.

$A \leq B $ Means that A is Turing reducible to B. This means that given an oracle for Machine B, A can be solved.

I'm confused in the case of SUPERHALT which decides whether a Turing machine with access to the HALT oracle halts or not. I feel like SUPERHALT is reducible to HALT because I can just put any Turing machine into a HALT oracle and then put that result into another HALT oracle.

So in summary I believe:

Given a Turing machine M and input x $\epsilon \\{1,0\\}^\*$ and oracle $HALT$, $$SUPERHALT(M(x)) \<\_T HALT(M(x))$$ because $$SUPERHALT(M(x)) = HALT(HALT(\<M(x)\>)$$ Which is wrong, but I just want to know what I'm misunderstanding.

# Answer
From wikipedia article Turing Reduction, in computability theory, a Turing reduction from a problem $A$ to a problem $B$, is a reduction which solves $A$, assuming the solution to $B$ is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve $A$ if it had available to it a subroutine for solving $B$. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for $B$. Turing reductions can be applied to both decision problems and function problems.

This potentially allows us, along with a few other things, to solve problem $A$ using a deterministic Turing machine if $B$ is solvable using deterministic Turing machine.

I assume $SUPERHALT = \\{ \langle M,x \rangle \ | \ M^{HALT}$ halts on input $x \\}$. If so, then your reduction is incorrect.

First of all, a Turing machine $M$, that uses $HALT$ as an oracle, cannot be used as a non-oracle machine and given as an input of $HALT$. So using something like $HALT(\langle M, x \rangle)$ leads nowhere.

We can use relativizing proof to prove that $SUPERHALT$ is unsolvable even with availability of $HALT$ as an oracle. We simply take Turing's original proof (with the machine given as self-input) that the halting problem is unsolvable, and give all the machines an oracle for the halting problem. Everything in the proof goes through as before.

From the fact that $SUPERHALT$ is unsolvable (even with the availability of $HALT$ as an oracle) we can prove $SUPERHALT \not\leq\_T HALT$. Suppose there is a turing reduction $M'$ for $SUPERHALT$, which uses $HALT$ as a subroutine. Then this $M'$ which uses $HALT$ as an oracle is able to decide $\langle M^{HALT},x\rangle \in SUPERHALT$. This is a contradiction. Hence $SUPERHALT \not\leq\_T HALT$.
> 6 votes

# Answer
> $A\leq B$ means that $A$ is Turing reducible to $B$. This means that given an oracle for Machine $B$, $A$ can be solved.

This is very close to correct, yes. Being picky, $A$ and $B$ here are languages, not machines, but that's not super-important. The key intuition here is that, if $A\leq B$ then, if you were given a subroutine for $B$ (which is, essentially, what an oracle is), you could solve $A$. This measn that, in a sense, $A$ is no harder than $B$.

Your intuition that what you're calling $\text{SUPERHALT}$ reduces to the ordinary halting problem, however, is incorrect. It's very easy to write down things like "$\text{SUPERHALT}(M(x)) = \text{HALT}(\text{HALT}(M(x)))$" but I'm not sure that statement actually means anything. For example, the argument of $\text{SUPERHALT}$ is a Turing machine with an oracle for the halting problem. So it doesn't make sense to write $\text{HALT}(M(x))$ because the argument to $\text{HALT}$ is supposed to be an ordinary Turing machine, not an oracle machine. So, when you write an equation, stop and check that it actually makes sense.

In fact, it can be shown that $\text{SUPERHALT}\not\leq\text{HALT}$. The proof of this uses essentially the same diagonalization as the proof that $\text{HALT}$ is not decidable. Intuitively, we expect $\text{SUPERHALT}$ to be strictly harder than $\text{HALT}$ because $\text{SUPERHALT}$ asks the halting question about more powerful machines (oracle machines) than $\text{HALT}$ does (ordinary machines).
> 5 votes

---
Tags: computability, reductions, halting-problem
---


# Question
Title: Given two vertices s,t in a directed graph, is there a vertex x such that xs and xt are paths?
I am curious of knowing of an efficient algorithm for the problem:

Given two vertices s,t in a directed graph, is there a vertex x such that `xs` and `xt`are paths?

I can of course do a BFS from each node of the graph resulting in a quadratic time algorithm.

Or I can reverse all the edges of the graph, do a BFS from `s` store all reachable vertices in a hashtable, do a BFS from `t` and check for each reachable vertex if it is in the table, ifso, I found `x`. While the running time is linear, the extra space requirement is ugly.

Is there any elegant O(E + V) time algorithm for this problem?

# Answer
**tl;dr** I wrote some solution but realized it is not perfect. Since I didn't want all this typing to go waste I figured I might post my observations here rather than splitting them in the comments.

I think that the problem can be solved for any arbitrary $s,t$ and $x$ in $\mathcal{O}(V+ E)$. In fact we can extend the problem to answer $Q$ queries of the form $(s,t,x)$ with $\mathcal{O}(V+E)$ pre processing and $\mathcal{O}(1)$ per query. I am having trouble completing step 6, but I am pretty sure that it can be done. Someone in the comments may know.

1. Find all strongly connected components (scc) of the graph using Kosarjau's or Tarjans algorithm. This step will take $\mathcal{O}(V+E)$ time.
2. Using a hash table, you can check if two nodes belong to the same stongly connected component in $\mathcal{O}(1)$ time.
3. If two nodes $u$ and $v$ belong to the same strongly connected component, then there exists paths both from $u$ to $v$ and $v$ to $u$.
4. Now what remains to be checked is if two nodes $u$ and $v$ do not belong to the same strongly connected component, does there still exist a path from $u$ to $v$.
5. We will modify the given graph $G$ to a new graph $G'$ which we shall call the strongly connected component graph or scc graph for short. In the scc graph, each node corresponds to one strongly connected component in the original graph i.e. we compress all nodes belonging to the same scc to a single node. It can be proven that the scc graph is a Directed Acyclic Graph (DAG for short).
6. Now our task reduces to check if there exists a directed path between $u$ and $v$ in the DAG. Topological sort can give an ordering such that for any path from $u$ to $v$, $u$ will appear before $v$ in the ordering. Thus we can check if index of $u$ in the topologically sorted sequence of vertices is less than that of $v$ in $\mathcal{O}(1)$ but this method also gives false positives and this is where I am stuck.
7. I feel that we can augment step 6 with some additional data to complete the algo. One method I was thinking of was to maintain some constant $K$ number of random topological sorts and if the inequality $index(u) \< index(v)$ is true for all $K$ sequences then we can conclude with high probability that there is a path from $u$ to $v$.
> 1 votes

---
Tags: graph-traversal
---


# Question
Title: Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string?
I'm trying to design a pushdown automata where there are two symbols in the alphabet and the accept state is when there is \>= 60% of symbol A.

I'm trying to think in terms of what to save on the stack. The problem of telling when there are 50% or more is trivial. You can just pop and push As and Bs on the stack to track which one has the majority. If an A is on the stack at the end, you're solid. however, in this problem we see that an A can be on the stack in the end and still not meet the criteria because it could be a ratio of 6 As to 5 Bs, which is under 60%.

# Answer
> 1 votes
Assume you have to check whether $\\#A \ge \frac 43\\#B$, then this is equivalent to $3\\#A \ge 4\\#B$. This can be solved: just push 3 symbols for every $A$ and pop four of them for every $B$ (changing this a little when the number gets negative).

Adapt this to your fraction.

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


# Question
Title: How to pick w for the Pumping lemma if the language has no clear pattern?
I'm trying to understanding using the pumping lemma to prove that a language is not regular. I sort of understand how it works when the language describes strings with a particular form, like in this example, but what do you set w to if there isn't a particular form.

The particular problem I'm trying to prove isn't regular: The language is the set of strings that is composed of 60% or more As and Bs with the alphabet {A, B, C, D}

Because the form of the strings is indeterminate (i.e. it doesn't follow a pattern like a^i b^i, I'm not sure how to divide the strings into a w and x, y, z.

# Answer
> 2 votes
I think your confusion lies in the fact that the language is not given in more "structured" form. Even if the language is not given as such, you are free to choose any string from the language which is more "structured" and allows you to disprove that language is regular.

Take $w=C^{2N}A^{3N}$ (or $A^{3N}C^{2N}$) where $N$ is the pumping length and $w$ is a string in your language, and then follow the proof in similar lines as in How to prove that a language is not regular?.

You should prove by yourself that above string $w$ can not be pumped.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Is a degree-$d$ pseudo distribution always a relaxation?
The optimization problem we are generally concerned with looks like the following,
\begin{eqnarray\*} &\inf \\{ p(x) \vert x \in K\\} \\ &K = \\{ x \in \mathbb{R}^n \vert q\_i(x) \geq 0, i = 1,..,m \\} \end{eqnarray\*}

where $p(x)$ is some polynomial objective function and $q\_i(x)$ are polynomial constraints.

One can look at this corresponding question,

\begin{eqnarray\*} &\inf\_D \\{ \tilde{\mathbb{E}\_D} \[p\] \\} \\ &s.t \\ &D : \\{ 0,1\\} ^n \rightarrow \mathbb{R} \\ &\sum\_{x \in \\{0,1\\}^n} D(x) = 1 \\ & \forall u \in SOS\_d \\ &\tilde{\mathbb{E}}\_D \[u\] \geq 0 \\ &\tilde{\mathbb{E}}\_D\[q\_i\] \geq 0 \end{eqnarray\*}

Here we use the \`\`pseudo-expectation" notation" whereby we have for any function $f$, $\tilde{\mathbb{E}}\_D\[f\] = \sum\_{x \in \\{ 0,1\\}^n } D(x)f(x)$ And $SOS\_d$ is the cone of all real polynomials in $n-$variables which can be written as a sum of squares of polynomials of degree at most $\frac{d}{2}$

* Is it clear that *for all* $d$ the later is a relaxation of the former?

If we restrict the polynomials to be valued on the hypercube $\\{0,1\\}^n$ then I can think of an argument which shows that the latter is a relaxation of the former by going through an intermediate Lassere relaxation. But if the polynomials are valued on the whole of $\mathbb{R}^n$ (as written above) then my above argument works only if $n^d \< 2^n$.
* Is there a proof that if one keeps increasing the $d$ then at $d=n$ the later will exactly hit the infimum being searched for in the first?

# Answer
To see that this is a relaxation, all you have to check is that each feasible solution to the first problem gives rise to a feasible solution to the second problem. All you have to do is, given $x \in K$, take an actual distribution $D$ concentrated on $x$. (This only works if in the definition of $K$ you replace $\mathbb{R}^n$ with $\\{0,1\\}^n$; your formulation doesn't make too much sense.)

When $d = n$, the conditions guarantee that $D$ is an actual distribution. If the objective function $p$ is concave then the optimal distributions are singletons, and so both programs have the same value. Otherwise it could be that for some distribution $D$ supported on $K$ it holds that $\mathbb{E}\_{X\sim D}\[p(X)\] \< \min\_x p(x)$.
> 1 votes

---
Tags: np-complete, optimization, np-hard, np
---


title: Complexity of sorting a 1-sorted array

text:
# Question
Title: Complexity of sorting a 1-sorted array
A $k$-sorted array is one in which every element is at most distance $k$ from its position when the array is sorted. The complexity of sorting such array is $O(n\log k)$. But if $k=1$, then $\log k=0$ so what happens? What is the complexity of sorting an array where each element is at most one place away from its sorted position?

# Answer
When we say an algorithm runs in $O(\lg k)$ time, that is an *asymptotic* statement. It means that there exists a constant $c$ such that when $k$ is sufficiently large, the running time is $\le c \lg k$. It says nothing about what happens when $k$ is small.

In particular, if we say an algorithm runs in $O(\lg k)$ time, that doesn't necessarily mean that when $k=1$ the running time is 0.

The same kind of comment applies to your question as well. No, it doesn't mean that the running time to sort an array where each element is at most one place away from its sorted position is $O(0)$. Rather, the complexity of that task is $O(n)$.
> 21 votes

# Answer
There is hidden linear time to perform merge part of sorting algorithm.
Linear is less than loglinear, so it was not visible. $\log1=0$, but it means that you will not e.g. heapify, just merge in $O(n)$ (heap structure in case of *1-sorted* array degrades to swapping consecutive elements to perform sort).

Inserting element to empty heap (which might be used in such sorting) costs $O(1)$, while putting element to min-heap containing $k$ elements is $O(\log k)$, which is in fact $O(\log k + c)$, so the first looks like it could be substituted with $k=1$ to have cost 0, but the second reveals constant factor in asymptotic notation.
> 6 votes

# Answer
There are some studies of tight bounds on sorting, such as Gagie and Nekrich, Tight bounds for online stable sorting, which looks at cost as a function of multiset entropy. These estimates include lower-order terms, so if you look at Table 1 you'll see that both upper bounds include an O(n) term in addition to Hn, so you can't just set H=0 and get zero cost. The O(n) is typically required to verify that all the elements are identical in the H=0 case (n-1 comparisons to be exact).

Unfortunately this makes sorting low-entropy sets disproportionately costly; for instance in radix sort when one radix is single-valued.

I think the entropy is also small for K-sorting; I don't know the exact expression offhand. If all the elements are already ordered that's similar to them being identical; n-1 comparisons are needed.
> 3 votes

---
Tags: complexity-theory, sorting
---


# Question
Title: Sieving to compute first values of totient function
What i want to do is to compute the first $n$ values of Euler's totient function effectively. As far as i know the best way to do it is to run a sieving algorithm and for each prime encountered to update current totient-value for all its multiples. My realization in Python is given below. I use two facts about totient function:

a) if $~p~$ is prime than $~\phi(n) = n-1$

b) for any prime $~p~$ and positive integers $~a,n~$ $~\phi(p^a n) = p^a n (1 - \frac{1}{p})$

My problem is termination of main loop. My code loops till $n / 2$ though i would like to stop at $\sqrt{n}$. The problem is that some numbers above $\sqrt{n}$ may have prime divisors above $\sqrt{n}$ which won't be processed with current version of algorithm if main loop is terminated before $n / 2$. I don't understand how to handle totient function values for such numbers since calculation for them wasn't finished in fact. Any ideas on these problem will be highly appreciated. Thanks in advance!

```
# n >= 2
def sieve(P, n):
    end = n // 2 + 1
    for k in range(2, end):
        if (P[k] == k):
            for j in range(2*k, end, k):
                P[j] -= P[j] // k

def phi(P, n):
    if (n == 1):
        return 1
    if (P[n] == n):
        return n-1
    return P[n]

n = int(input())
P = [i for i in range(0,n+1)]
sieve(P, n)
for k in range(1, n+1):
    print(repr(k) + "  " + repr(phi(P,k)))

```

# Answer
> 2 votes
The complete formula for Euler's totient function is $$ \varphi(n) = n\prod\_{p|n} \left(1-\frac{1}{p}\right), $$ where the product goes over all prime factors of $n$. Hence you essentially need to factor $n$ in order to compute $\varphi(n)$. You can do it in any way you wish.

Computing $\varphi(n)$ is believed to be as hard as factoring $n$ (and is indeed as hard in some special cases, for example when $n$ is a product of two primes).

You can use a sieve to factor all numbers up to $n$. The idea is to go from $2$ to $n$; whenever encountering an uncircled number $p$ (the initial state), this number must be prime, and we can circle all its multiples. Moreover, we can divide these numbers by $p$, the appropriate numbers by $p^2$, and so on. At the end, the uncircled numbers are all primes, and all other numbers have been factored.

You can easily adapt this algorithm to compute the totient function directly. Every time you encounter a new prime $p$, you divide all its multiples by $(p-1)/p$. After going through all numbers up to $n$, all uncircled numbers are prime, and so their totient function is easy to compute.

---
Tags: number-theory
---


# Question
Title: What determines the number of arcs and tokens in a Petri Nets Model?
I study Petri Nets to model some cases related to my job. Currently, I study the basics of Petri Nets and am confused. (For the time being I couldn't get a textbook yet, I will.)

**my questions**

**q1)** What determines the required number of tokens required for the model to be constructed properly? What is a bulletproof thinking way to determine the number of tokens required? It may be not needed the correct procedural way of thinking to construct but complex cases will need I think. (*Is it only enough to know the conditions, so number of conditions will equal to number of tokens **OR** number of conditions actually gives me the number of arcs between places-transitions, and then I should assign the number of tokens to places depending on the number of arcs?)*

**q2)** Am I thinking in the correct way below?

**q3)** Can you please provide the model required for my icing case below?

---

case: icing ocuurs or no icing. (2 states)

*Place 1* : Icing occurs

*Place 2* : No Icing

2 conditions (2 arcs so 2 tokens required for enabling & firing) required for icing on air:

1. water molecules **AND**
2. negative celcius temperature

. If these conditions exists simultaneously, then icing will occur.

So enabler from Place 2 to Place 1 needs 2 conditions. From Place 1 to Place 2, enabler needs "absence of at least 1 condition". After this point I stuck and can not draw the model.

My real world cases are too complicated.

# Answer
> 1 votes
One of the resources I used to teach myself about Petri Nets was the chapters on Petri Nets in the textbook “Petri Nets and Grafcet: Tools for Modeling Discrete-Event Systems” (David and Alla, 1992).

An example process and a Petri Net model of the process may help you answer your first two questions (Chenier, 2016). Thus I am including the following, a Petri Net model to illustrate the icing process at a logical level. Furthermore control is included for recognizing the presence or absence of water and for identifying the freezing point (below 0 Celsius) and melting point of water (above 0 Celsius). The change of phase from liquid to solid and the change of phase from solid to liquid are reactions to the recognition of water and identification of temperature. Assume when water changes phase, every single molecule undergoes the phase change at the same instant.

Given these assumptions the icing process behaves like an AND-Gate plus controls for the inputs of the AND-Gate. The controls toggle the input values.

Table 1 Input-Output Relations of Water-Temperature versus Ice

Figure 1 is a Petri Net model of the icing process and Table 2 is a summary of places and transitions in the model. \[For the PDF version Figure 1 is a dynamic, interactive diagram.\] Every (enabled) transition can be triggered by clicking on a green square. To click on an enabled transition is equivalent to an occurrence of the corresponding event. The demonstration mode triggers a transition (T\_0,T\_1,T\_2 or T\_3) automatically when any of the other transitions are triggered. Please see Notes for more information about Figure 1.

Figure 1 A Dynamic, Interactive Petri Net Model of an Icing Process with Input Controls

Table 2 A Summary of Places and Transitions

## Notes

1. The Petri Net model in Figure 1 is a Place/Transition Net.
2. The graphics used to represent an inhibitor arc in Figure 1 is an arrow with a small circle near the corresponding place. The small circle stands for the weight (which is 0). As you probably know, an inhibitor arc is an input with an annotation for testing if the input can fire but does not have an annotation for firing the input.
3. Every edge with two arrowheads has one and only one (logic) annotation for testing the condition of the input.
4. A subtle assumption made for the model in Figure 1 is the possibility of transitions (T4,T5,T6,T7) to occur several times while phase changes (T0,T1,T2,T3) may not be fast enough to occur.

## Scenarios

To assist in the interpretation of the model, the following six scenarios are included.

Scenario 1 No water found, normal temperature detected, and no ice.

Scenario 2 From Scenario 1, water was detected (T5 fires). In this scenario: water found, normal temperature detected, no ice.

Scenario 3 From Scenario 2, temperature drops below freezing point (T7 fires) but the ice has not formed yet. In this scenario: water found, freezing temperature detected, no ice.

Scenario 4 From Scenario 3, the system has reacted to the freezing temperature (T3 fires). In this scenario, water found, freezing temperature detected, and ice.

Scenario 5 From Scenario 4, the temperature goes above freezing (T6 fires) but the system has not reacted yet. In this scenario: water found, normal temperature detected, and ice.

Scenario 6 From Scenario 5, the system has reacted to freezing temperature (T2 fires). In this scenario: water found, normal temperature detected, and no ice.

## References

Chionglo, J. F. (2016). A Reply to "How to determine / what determines the number of arcs and tokens in a Petri Net model" at Computer Science Stack Exchange. Available at http://www.aespen.ca/AEnswers/1458112273.pdf.

Chenier, A. (2016). How to Determine / What Determines the Number of Arc and Tokens in a Petri Nets Model. Computer Science Stack Exchange. Retrieved on Mar. 14, 2016 at What determines the number of arcs and tokens in a Petri Nets Model?.

David, R. and H. Alla. (1992). Petri Nets and Grafcet: Tools for Modeling Discrete-Event Systems. Upper-Saddle, NJ: Prentice Hall.

---
Tags: petri-nets
---


title: A Graph's Density and Sparsity

text:
# Question
Title: A Graph's Density and Sparsity
1. A graph is dense when |E| (edges) is closest to $|V|^2$.
2. A graph is sparse when |E| is closer to $|V|$.

What does it mean to take the magnitude of the vertices? Secondly, I am having a hard time conceptualizing why the above two rules are true.

Also can someone elaborate on why if a graph is sparse, it should be represented with an adj list and why if it is dense, it is best to use an adjacency matrix instead?

# Answer
> 3 votes
The notation $|V|$ here means the number of vertices in your graph. Likewise, $|E|$ is used to denote the number of edges. We typically say that a graph is sparse whenever $|E| \in O(|V|)$ - i.e there are few enough edges. Similarly, we say that a graph is dense whenever $|E| \in \Theta(|V|^2)$ - i.e there are many edges in your graph. These are not really rules, but rather just the terminology one often uses in textbooks.

An adjacency matrix requires $\Theta(|V|^2)$ space to store, while an adjacency list requires $\Theta(|V| + |E|)$ space to store. So when the graph is sparse, using an adjacency matrix is wasteful in terms of space usage, even though answering queries may be faster. On the other hand, is the graph is dense, then both representations require a quadratic amount of space to store, and so you are better off using the adjacency matrix for $O(1)$ edge queries. There are other trade-offs that one can consider as well depending on the queries you anticipate using often, such as vertex insertion/deletion, neighborhood queries, among others... but this is the general rule of thumb.

It may also make a difference when implementing certain algorithms, like Dijkstra's. Using an adjacency matrix, the algorithm takes $O(|V|^2)$ time, but using an adjacency list, it can be implemented in $O(|V| + |E| \log |E|)$ time. This type of trade-off is common when implementing different graph algorithms.

# Answer
> 2 votes
An adjancency matrix takes up more space, the size is not flexible with repect the the number of element. Given that you have 20 vertices with only few just being connect, when represented with an adjacency list, its still take up the same (approximately the same space).

So its only resonable to use the matrix when you are sure you will be using a reasonable size of the already allocated space. For Adjacency List, its dyanamic and space increase as number of the vertex grows, So, its best to just use adjacency list for small sparse graph.

---
Tags: graphs
---


# Question
Title: Linear Search Algorithm - Why allow a user to input a start and end index to LS?
Here is the linear search algorithm provided in class:

```
bool LinearSearch(int [] a, int l, int u, int e) {
      for(int i:=l; i ≤ u ; i := i + 1) {
          if (a[i] = e) return true;
      }
      return false;
}

```

If the intention of this function was to linear search through the function why allow a parameter of l and u? A user could test this function in ways to breach the intention of linear search. For example let l and u be numbers such that it only searches through a subsequence of the list and not the entire list. I asked my professor if the intention of this code was to have the possibility of it being used in ways that do not search the entire list. She didn't quite understand me, because she replied "No, it should be possible to search through the entire list." Well I know it's possible but why have the l and u if you can just write the code better and remove l and u. Now I know in other languages you might need to know the bounds, but this isn't a programming class whatsoever.

# Answer
Surely, it is not about correctness. It is only a slightly general version of linear search. This technique is not uncommon. Obviously the more general the procedure is, the more applicable it is.

Linear search is a little bit simple for an illustration. Let's look at quicksort@wiki that is declared as `quicksort(A, lo, hi)`. This is because `quicksort` is a *recursive* procedure that needs to call itself over a sub-range of the array. Notice that `quicksort` also needs a `partition` procedure, which is declared as `partition(A, lo, hi)` instead of `partition(A)`.

Another kind of examples is dynamic programming. Suppose that you want to compute the edit distance@wiki between two strings of $a$ and $b$, with lengths $m$ and $n$ respectively. What you are actually computing is $\text{Dist}(i,j)$ for $0 \le i \le m, 0 \le j \le n$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Showing the the language represented by a set is regular
Is the language $L = \\{ w \mid w $ is $ 3^n - 1 $ in some given representation $, n \> 0 \\}$ regular? I know that it is regular. If each element in $L$ is represented as decimal numbers, $L = \\{ 2, 8, 26, 80, 242, \ldots \\}$. If in binary, $L = \\{ 10, 1000, 11010, 1010000, 11110010, \ldots \\}$. However, if in ternary, $L = \\{ 2, 22, 222, 2222, 22222, \ldots \\}$. From there, it is clear that a DFA can be designed to show that $L$ is regular. But what if it wasn't ternary that it became clear, but instead base 59 or base 1009?

My question is that for other sets, does there exist a clear method to determine if the language based on that set is regular or not? Or does it just depend on the cleverness of the solver?

# Answer
> 4 votes
See DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$.

The proof for $L'=\\{w \mid w \in \\{0,1\\}^\*, w $ is $3^n$ in binary for some $ n \> 0 \\}$ is not regular can be easily modified to prove that $L'=\\{w \mid w \in \\{0,1\\}^\*, w $ is $3^n - 1$ in binary for some $ n \> 0\\}$ is not regular.

However in ternary the same language is regular. It is similar to case of $2^n$ and $2^n-1$. So for some bases you might be able to prove these kind of languages regular but for others you may not.

---
Tags: formal-languages, regular-languages
---


title: Enumeration of winning coalitions

text:
# Question
Title: Enumeration of winning coalitions
Taken from Wikipedeia:

> A simple voting game, taken from Game Theory and Strategy by Phillip D. Straffin:
>
> \[6; 4, 3, 2, 1\]
>
> The numbers in the brackets mean a measure requires 6 votes to pass, and voter A can cast four votes, B three votes, C two, and D one. The winning groups, with bolded swing voters, are as follows:
>
> **AB**, **AC**, **A**BC, **AB**D, **AC**D, **BCD**, ABCD

Using a non-trivial structure, we know that `ABCD` will always be a member of the set of winning groups. Also, we know that if `AB` is a winning group, then `ABC` and `ABD` are also winning groups. In other words, the set of winning groups `AB, ABCD` is invalid. ~~Thus, any member of the set, besides ABCD, can be constructed by removing a single element from another set in the group.~~ *(Edit: While this is true, it gives the wrong impression.)*

In the beginning, the goal was to generate the set of possible winning groups for a given number of players. Using three players as an example, the set of winning groups is:

```
{1, 2, 3}

{1, 2, 3}, {1, 2}
{1, 2, 3}, {1, 2}, {1}
{1, 2, 3}, {1, 2}, {2}
{1, 2, 3}, {1, 2}, {1}, {2}

{1, 2, 3}, {1, 3}
{1, 2, 3}, {1, 3}, {1}
{1, 2, 3}, {1, 3}, {3}
{1, 2, 3}, {1, 3}, {1}, {3}

{1, 2, 3}, {2, 3}
{1, 2, 3}, {2, 3}, {2}
{1, 2, 3}, {2, 3}, {3}
{1, 2, 3}, {2, 3}, {2}, {3}

{1, 2, 3}, {1, 2}, {1, 3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}
{1, 2, 3}, {1, 2}, {1, 3}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {2}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}, {3}

# and so on...

```

~~This is doable through a relatively simple algorithm as thankfully offered here.~~ *(Edit: That algorithm does what was requested, but, per my oversight, generates false positives, e.g. {{1, 2}, {1, 3}, {1, 2, 3}, {1, 2, 3, 4}}.)*

However, I want to only generate one set per "isomorphic group." For example, the sets `{1, 2, 3}, {1, 2}` and `{1, 2, 3}, {1, 3}` are the same if we swap the labels of 2 and 3. This is the primary goal.

The secondary goal is to only generate the sets of winning groups that could be realized through a voting structure. ~~Using a four player system and a maximum of 20 votes per person, I found sets of winning groups that satisfied the above criteria, but could not be realized.~~ *(Edit: See previously mentioned false positives and the answer below.)*

# Answer
> 4 votes
You are asking two questions:

1. How to count "winning groups" up to isomorphism?
2. Which winning groups are realizable as winning coalitions?

From the point of view of winning groups, we can assume that each voter always casts all her votes, and the resulting games is known as a *weighted voting game*.

## Counting winning groups

Your concept of "winning group" is a same as a *monotone Boolean function* or an *upset*. The number of monotone Boolean functions up to permutation is enumerated in the sequence A003182, and grows pretty quickly. For $n=7$ the number is already pretty large: 490,013,148. It's probably not too helpful to list all of them. It is even non-trivial just to calculate the number, see this paper.

You can find all the 16351 non-constant monotone Boolean functions for $n=6$ listed here as sets of *minterms*, which are (in your parlance) minimal winning coalitions. The minterms form what is known as an *antichain*, a collection of sets none of which is a subset of another.

## Which winning groups are achievable?

Let $S\_1,S\_2$ be two sets of voters. A *swap* consists of taking some $x \in S\_1 \setminus S\_2$ and some $y \in S\_2 \setminus S\_1$, and forming the new sets $S\_1 - x + y, S\_2 - y + x$ (that is, we exchange two voters, taking care not to have the same voter twice in any of the sets). Given several sets $S\_1,\ldots,S\_k$ of voters, a *trade* is the result of applying arbitrarily many swaps, resulting in a new $k$-tuple $T\_1,\ldots,T\_k$.

(Alternatively, $T\_1,\ldots,T\_k$ is a trade of $S\_1,\ldots,S\_k$ if the multisets $S\_1 \cup \cdots \cup S\_k$ and $T\_1 \cup \cdots \cup T\_k$ are the same.)

Let $W$ be a set of "winning coalitions". We say that $W$ is *trade robust* if whenever $S\_1,\ldots,S\_k \in W$, in any trade $T\_1,\ldots,T\_k$ obtained from $S\_1,\ldots,S\_k$ at least one of the $T\_i$ is in $W$. It is easy to see that every set of winning coalitions arising from weighted voting games is trade robust (exercise). Amazingly, Taylor and Zwicker showed that the converse holds as well.

---
Tags: algorithms, enumeration, voting
---


# Question
Title: Runtime of algorithem when the internal for depend on the external for
I'm trying to find the running time of this pseodocose:

```
int x=0,i,j
for (i=1;i<=n;i++)
    for(j=1;j<=n+r;j=j+i)
       x=x+j;

```

What I did: First I checked what happened on the first iteration of the external `for`:

* $i=1:$ the internal `for` will run $n+r$ times, so $j\in\\{1,2,3,4,\dots,n+r\\}$ so $\color{blue}{a\_n=n}$
* $i=2: $ the internal `for` will run from $j=1$ to some $k\leqslant n+r$ such that $j\in\\{1,3,5,7,\dots,k\\}$ so $\color{blue}{a\_n=2n-1}$
* $i=3$: the internal `for` will run from $j=1$ to some $k\leqslant n+r$ such that $j\in\\{1,4,7,10,\dots,k\\}$ so $\color{blue}{a\_n=3n-2}$

So the runnig time should be $\color{blue}{\underbrace{n+(2n-1)+(3n-2)+(4n-3)+\dots}\_{ n+r \text{ times}}}$

But what should I to now? I should find the running time in $\Theta$ terms, I am trynig to find the runnig time without using any calculator

# Answer
For $i=1$ the internal loop runs for $n+r$ times, for $i=2$ the internal loop runs for $\lceil (n+r-1)/2 \rceil+1$ times, for $i=3$ the internal loop runs for $\lceil (n+r-1)/3 \rceil+1$ times, and so on till $i=n$ when the internal loop runs for $\lceil (n+r-1)/n \rceil+1$ times.

You now need to sum these numbers. I suggest you read about harmonic series.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Complexity of $n \times \log n$ tiling problem
Is there a polynomial time algorithm for an $n \times \log n$ tiling problem?

For instance: Suppose $A$ is a finite alphabet. A tile is a $2 \times 2$ matrix of elements from $A$. A tiling is a matrix of tiles in which any adjacent symbols (including diagonally) in neighboring tiles are equal.

The Tiling Problem is as follows. Given a set of tiles $T$ and a sequence $C\_1$ of $\log n$ tiles from $T$, is there an $n \times \log n$ tiling of $T$ whose first row is $C\_1$?

# Answer
> 1 votes
Hint: Use dynamic programming, going row by row. Use the fact that there are only $\log n$ many columns, and so only $|A|^{\log n} = n^{\log |A|}$ many different configurations of each column.

(The resulting algorithm will be polynomial in $n$ but not in the input size, which is only $O(\log n)$.)

---
Tags: np-complete, cellular-automata
---


# Question
Title: Objective function and Neighborhood function
I have a problem which has several solution but one is the optimal . my questions are:

1- It is required to write an objective function. I don't know what "Objective Function" mean . I need the definition of this function regard my problem.

2-Another requirement is writing a Neighborhood function of a local search algorithm, also i need the definition for this function.

Thank you

# Answer
An *objective function* is some function that returns a value indicating how 'close' a given solution is to the optimal solution. This might be an exact value, or an estimate.

A *neighbourhood function* is a function that returns a list, set, etc. of the states that are considered 'adjacent' to the current state: that is, states that can be obtained by making a single modification to the current state according to whatever rules are appropriate to your problem.

To illustrate: suppose you are trying to navigate from one city to another. Your 'states' are the individual cities that you can travel through, and they are connected in such a way as to represent which cities are adjacent to each other. Your objective function could be a measure of how far a given city is from your target city; the lower the value the closer to optimal it is. Your neighbourhood function would then return the list of all cities connected to your current city (i.e. cities reachable in one step).
> 2 votes

---
Tags: algorithms
---


# Question
Title: Quantum computer simulators with proper measurements
I have been looking for quantum computer simulators and came across QCAD (http://qcad.osdn.jp/). It is stated on their website that "Measurement gates on QCAD are different from real measurements."

I wonder if other simulators, like those listed on Quantiki (https://quantiki.org/wiki/list-qc-simulators), might have the same problem of incorrectly mapping the design with the experimental values.

# Answer
> 4 votes
Based on QCAD's help file, their measurement gates are more like measure-later-suggestions:

> The measurement gates on QCAD only set "measurement flags". After the calculation, the measurement is performed.

I'm very surprised they would return a wrong answer instead of throwing an error. **Most simlators *won't* do this**, and if they do it should be reported as a bug.

For example, I use the same cheat in my own simulator (which you can play with in your browser), but I prevent any later operations that would cause the result to differ compared to deferring the measurement. So it lets you hit a measured qubit with a NOT gate, but a Hadamard gate or a controlled-by-unmeasured-qubit NOT gate will be forcibly disabled. Which is frustrating, but at least not misleading.

# But Why?

The reason this limitation exists is *efficiency*. It's the difference between $\Theta(4^n)$ operations and $\Theta(2^n)$ operations needed to simulate a gate applied to an $n$-qubit system. Operations on mixed states are much more expensive to simulate than operations on pure states, and deferring measurement allows the simulation to only use pure states.

# Workaround

A simple workaround for this limitation is to **include an extra qubit, CNOT the value you wanted to measure onto the extra qubit, then measure the extra qubit**. This is mathematically equivalent to measuring the original qubit, but will sidestep the limitation in the simulator that prevents you from then doing more things with the original qubit and still getting the correct result.

# Easy Alternatives w/o By-Design Silent Mistakes

Microsoft's LiQui|\>

Google's in-browser "Quantum computing playground"

Davy Wybiral's toy in-browser simulator

"Quirk", my own toy in-browser simulator

---
Tags: quantum-computing, simulation
---


# Question
Title: Linear Bounded Automaton that accepts all strings
I'm currently reading Sipser's Introduction to the Theory of Computation, and I'm reading up about linear bounded automata, now we know from Rice's Theorem that whether a TM can accept all strings in a given alphabet is undecidable, I was wondering if the same could apply to linear bounded automata, if not, how would one go about proving the undecidability of such a problem (or its decidabilty?). Thanks in advance.

# Answer
For Turing machines another problem is also undecidable: whether it accepts any string at all. This is already undecidable for LBA. Basically the proof is by oberving that we can replace a TM accepting string $w$ by a LBA accepting the \`trace of the computation' by the TM on $w$. The verification of the trace of the computation does not need more space than the computation itself, and thus can be verified by a LBA.

The question whether a device accepts *all* strings is already undecidable on a lower level of the Chomsky hierarchy, the context-free languages (CF grammars,or pushdown automata).
> 3 votes

---
Tags: turing-machines, automata, undecidability
---


# Question
Title: Kolmogorov complexity vs purposefully inefficient Turing machines
It's a theorem that, although the Kolmogorov complexity of a string is relative to the Turing machine you're working with, it differs by at most a constant (basically the amount of space it takes to write an interpreter for Turing machine A inside of Turing machine B).

My question is: how does this theorem deal with the issue of Turing machines with purposefully inefficient encodings?

For example, suppose we have a universal Turing machine $M\_{terrible}$ that requires its input to be repeated five times. It starts by verifying that the input is in fact of the form `x ++ x ++ x ++ x ++ x`, then executes the universal Turing machine $N$ on just `x`. Shouldn't this force the Kolmogorov complexity of strings relative to $M\_{terrible}$ to be 5 times larger than they are relative to $N$? Why doesn't this violate the theorem?

# Answer
You are stating the theorem incorrectly. The theorem states that the Kolmogorov complexity is the same up to a constant for *essentially optimal* description languages, which are those in which you can describe running a Turing machine on an input $x$ using $|x| + O(1)$ bits. Given this definition, it is a simple matter of playing with definitions to see that all such description languages result in the same notion of Kolmogorov complexity, up to an additive constant.
> 5 votes

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


# Question
Title: How many languages exist over a finite alphabet?
I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams. Link

In "Exercises for ACS 1, Fall 2004, sheet 1", exercise 1 item C, the question is,

> How many languages exist over the symbol sets from (a)?

Question (a) describes the alphabets $S=\\{a,b\\}$ and $S=\\{1\\}$. The answer to the question as provided in the same link is

> In both cases, $|Σ^\*| = \mathbb N$, that is, there are $2^{\mathbb N}$ many languages over these alphabets – indeed, over any finite alphabet there are $2^{\mathbb{N}}$ languages.

Here $\mathbb{N}$ is the set of all natural numbers. I am confused as to how the author came to this conclusion.

Update: In my understanding, since {a,b} is a set of strings of {a,b}, it follows that it is a subset of {a,b}\* or the set of all strings over {a,b}. So, as per set theory, the cardinality of a set containing the subsets of all strings over {a,b} = powerSet({a,b}\*) whose cardinality is equal to $2^{\mathbb{N}}$. Is my understanding correct?

# Answer
> 3 votes
The number of possible words is countably infinite, since we can list them in increasing order of length: $$ \epsilon,a,b,aa,ab,ba,bb,\ldots \\ \epsilon,1,11,111,1111,11111,\ldots $$ This is why $|\Sigma^\*| = \aleph\_0$ (to use a more common notation). The set of all possible languages is the set of all subsets of $\Sigma^\*$ (known also as the *power set* of $\Sigma^\*$), which *by definition* has cardinality $2^{\aleph\_0} = \aleph$.

If you are unfamiliar with these terms, you need to do some reading on elementary set theory.

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


# Question
Title: It is possible to implement a *greater than* function using only addition, substractions and multiplications?
All values are from a finite field $Z\_t$. I want to write a function *greater than* like this

$GT(x,y) = \begin{cases} 1, & \text{if } x \> y, \\ 0, & \text{otherwise}. \end{cases}$

using only additions, multiplications, subtractions and preferably not divisions.

The equality function

$EQU(x,y) = \begin{cases} 1, & \text{if } x == y, \\ 0, & \text{otherwise}. \end{cases}$

can be computed like this

$EQU(x,y) = 1 - (x-y)^p$, where p is the Euler totient function $p=phi(t)=t-1$ because $t$ is prime.

Can a greater than function be written in a similar way ?

The greater than function would be used for a homomorphic encryption application to find the maximum integer value from a vector of encrypted integers.

# Answer
> 13 votes
Every function on a finite field $GF(q)$ can be represented unique as a polynomial of individual degree at most $q-1$.

Indeed, as you mention, $1-x^{q-1} = \[\\!\[x=0\]\\!\]$ is a polynomial that equals $1$ if and only if $x=0$. Therefore we can represent any function $f\colon GF(q)^n \to GF(q)$ in the variables $x\_1,\ldots,x\_n$ in the following form: $$ \sum\_{t\_1,\ldots,t\_n \in GF(q)} f(t\_1,\ldots,t\_n) \prod\_{i=1}^n \left(1-(x\_i-t\_i)^{q-1}\right). $$ Since the dimension of the space of $n$-variate functions is $q^n$ and the number of monomials of individual degree at most $q-1$ is also $q^n$, we conclude that this representation is unique.

---
Tags: algorithms, linear-algebra
---


# Question
Title: Should planar Euclidean graphs be planar straight-line graphs?
An Euclidean graph, by definition is

> A weighted graph in which the weights are equal to the Euclidean lengths of the edges in a specified embedding

and a graph is called planar if

> it can be drawn in a plane without graph edges crossing

lastly, a planar straight-line graph (PSLG) is

> embedding of a planar graph in the plane such that its edges are mapped into straight line segments.

By these three definitions, I cannot conclude that if an Euclidean planar graph should be a PSLG or not. For instance, given an Euclidean non-planar graph:

I can convert this graph into an Euclidean planar graph

by sticking with the definitions. Given the definitions above, the former one is a non planar straght-line graph whereas the latter one is a planar graph. Assume that the length of each edge is preserved. Then is the latter one still an Euclidean graph?

# Answer
Fáry's theorem states that every planar graph can be drawn in such a way that its edges are (non-crossing) straight lines. Hence every planar graph is a planar straight-line graph.

However, this doesn't really have any bearing on the definition of Euclidean graph. According to the definition you link too, the edges need not be straight. A Euclidean graph is a planar graph in which the edge weights are their lengths in some specific (planar) embedding. In particular, a non-weighted graph isn't Euclidean any more than a cucumber.

Finally, the first graph in your question is planar – it's just that your specific embedding isn't a planar embedding.
> 4 votes

---
Tags: graphs, euclidean-distance
---


# Question
Title: Sorting array with at most two inversions
I have created an algorithm to sort an array of size $n$ with at most 2 inversions with exactly $n$ comparisons in the worst case.

I have no idea how to prove that it is optimal in terms of the number of comparisons. The only argument which came up to my mind is that we of course have to read the whole array, but I don't think it is a proper argument. I tried to use argument similar to minimal number of comparisons to find minimum (with graph), but it doesn't seem to be good in that case.

How can I prove that $n$ comparisons is optimal in the worst case?

# Answer
> 2 votes
To show that the optimal number of comparisons is $m$, you have to prove that any algorithm that uses $m-1$ comparisons must make a mistake on some arrays. The usual way to accomplish that is through an *adversary argument* – you "react" to the queries of the algorithm in a specific way, and ensure that after $m-1$ steps, there are two different linear orders that are consistent with your answers to the queries (as well as comply with the constraints – in this case at most two inversions).

---
Tags: time-complexity, sorting, arrays
---


title: Mano base computer and the FGO flag

text:
# Question
Title: Mano base computer and the FGO flag
I have a question about the Mano base computer. The state diagram, shown below, implies that the output device will set the FGO flag to "1" after the job is done to continue the output activity from the PC (and to zero when device is busy).

But in most cases we don't have anything to do with the output and the flag stays at "1" and the cycle enters the interrupt routine every time. It seems like this leads to the computer running the interrupt routine most of the time.

Is this a bug in this system or am I missing something?

# Answer
> 1 votes
You may have a misunderstanding of OUTR. **OUTR is not the R in the flowchart you posted**. Here is what is exactly done in the Mano system:

OUTR is not flag! It's a register for sending AC's value to the output device. FGO is a flag in system that shows whether the CPU is ready to send data to output device or not. So it is "1" by default. The CPU checks the flag:

1. If FGO="1" : The device is ready to send output in an interrupt cycle! so R\<--1 and the interrupt process will start: AC's content will be moved to OUTR in parallel and FGO="0" (means OUTR is full and you cannot send anything to output device!).
2. If FGO="0": means that the device is busy reading data from OUTR so no more data can be send out.

At the end of the I/O process the R\<--0 *means get out of Interrupt cycle!*

---
Tags: computer-architecture
---


# Question
Title: On certificates in BPP (avoiding majority vote)
Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output.

However if the problem $\Pi$ is also in $NP$ instead of running $A$ so many times why cant we after every run verify the certificate that $A$ produces is correct? If correct after a particular run and the answer is $Yes$ and the certificate is accepted then declare answer as $Yes$ else if the answer is $Yes$ and the certificate is not accepted then declare answer as $No$.

This should be much faster than taking majority vote.

# Answer
> 3 votes
A randomized algorithm $A$ does not produce any sort of "certificate" in any useful sense. Even if $A$ is a correct BPP algorithm, all that you know by running $A$ once is that it gives this particular outcome on this particular set of coin tosses. How would you use this fact as a witness that the input is or is not in the language? A correct BPP algorithm may give the right or wrong answer on this particular run.

In contrast, a correct deterministic algorithm does give a certificate from only running it once because it will give the same (correct) answer every time. Whereas you would need to run $A$ on all possible coin tosses and concatenate these answers to get any sort of "proof" about the input.

Another approach to your question: you could also start from the fact that a problem is in NP and try to design a randomized algorithm that both solves it and produces witnesses when it does. Here, however, as Yuval says, the issue is that witnesses may be very unlikely to guess so we do not know how to do this in general. If we could show that a randomized polynomial-time algorithm can reliably guess witnesses when they exist, we will essentially have shown $NP \subseteq BPP$.

# Answer
> 1 votes
The algorithms witnessing that $\Pi \in \mathsf{BPP}$ and that $\Pi \in \mathsf{NP}$ could be different. You cannot interpret random coin tosses used by $\mathsf{BPP}$ algorithms as witnesses for $\mathsf{NP}$ algorithms.

---
Tags: complexity-theory, np, randomized-algorithms, polynomial-time, randomness
---


title: Existence of Hamming code

text:
# Question
Title: Existence of Hamming code
We are given a number $n \geq 3$ and we know that the Hamming bound is satisfied. Does this imply that there is a Hamming code with length $\frac{q^r-1}{q-1}$, dimension $\frac{q^r-1}{q-1}-r$ and Hamming-distance $3$ or do we have to construct such a code, given that the bound is satisfied?

# Answer
> 4 votes
The Hamming bound is an upper bound on the size of codes. It's not a tight bound in general, though in some specific cases it is achievable. Codes achieving the Hamming bound are called perfect codes.

When the alphabet size is a prime power, all perfect codes are known: apart from some trivial cases (repetition codes, codes with one codeword, and codes containing all possible codewords), they share the same parameters as a Hamming code or a Golay code.

What this means is that if your alphabet size is a prime power and you have parameters satisfying the Hamming bound, then a code with these parameters actually exists only in the cases listed above. In any other case, the bound isn't tight.

---
Tags: coding-theory
---


title: A clarification on $PP$

text:
# Question
Title: A clarification on $PP$
Wiki in https://en.wikipedia.org/wiki/PP\_(complexity) says "a PP algorithm is permitted to do something like the following:

On a YES instance, output YES with probability $1/2 + 1/2^n$, where n is the length of the input. On a NO instance, output YES with probability $1/2 - 1/2^n$."

Can we replace $2^n$ by something larger like $2^{n^{1+\epsilon}}$ or $2^{2^n}$? It seems that this case should be already known to be distinct from $BPP$.

# Answer
> 3 votes
First, let me change your definition of PP a little bit:

On a YES instance, output YES with probability $\geq 1/2 + \epsilon(n)$

On a NO instance, output YES with probability $\leq 1/2 − \epsilon(n)$

Here, I replaced the error term with $\epsilon(n)$ and added $\geq$ and $\leq$. If we don't include $\leq$ and $\geq$, then problems in $BPP$ would not fall under our definition of $PP$.

You can replace the error with any small $\epsilon(n)\>0$ you want, but you are not accomplishing anything by going past $\epsilon(n)^{-1} = \Omega(2^{poly(n)})$.

Realistically, we do not need an error term smaller than $\epsilon(n)^{-1} = 2^n$ because you can amplify the error by a polynomial amount to get $2^{poly(n)}$ (since we are a polynomial time machine).

We unfortunately can't amplify beyond this, but that turns out not to matter. There does not exist a probabilistic polynomial time Turing machine that can accept or reject with error probability $\epsilon(n)^{-1} = \Omega(2^{poly(n)})$. A probabilistic polynomial time Turing machine does not have a large enough number of configurations to accept or reject with such a fine grained/detailed error.

To see what I mean, think about how you would design a PPTM that outputs YES with probability just $1/2^{2^n}$. The best you could do is use almost all of your runtime to generate $poly(n)$ random bits and accept if they are all $0$'s. The probability of this happening is bounded by $1/O(2^{poly(n)})$.

---
Tags: complexity-theory, complexity-classes, randomized-algorithms, probabilistic-algorithms
---


# Question
Title: Calculating product of totient functions
Suppose that i need to compute product $~\phi(1) \dots \phi(n)~$ modulo prime $500009$ as fast as possible. Memory limitations are rather tough: $64$ mb so i can't just keep all the values of totient function. $n$ can be as large as $10^9$ and time given is $2$ s.

My main idea is to somehow estimate the prime factors and their exponents in factorization of this product. And then apply fast modular exponentiation. But i don't understand yet how to do such estimation.

Any ideas are highly appreciated. Thanks in advance.

P.S. This is not a hometask or a problem from a current contest. I'm just surfing number theory problem bank and solving them for fun.

# Answer
Let $p=500009$ and $m=12p+1$. One possibility is to use the fact that $\phi(m) \equiv 0 \pmod{p}$, and hence it's enough to pre-calculate all values up to $m$. Storing each answer in a 32-bit integer, this is a table of size 24MB.

If you don't like pre-calculating everything, you can use in some other way the fact that only numbers below $m$ need to be considered. Be creative.
> 0 votes

---
Tags: number-theory
---


title: Maths Co-Processors

text:
# Question
Title: Maths Co-Processors
I want to know how Maths Co-Processors are made and how they work. I do understand that these are based upon electrical (yet chemical) switches, but how do they calculate things ?

I don't understand how switching something on and off not only make something tick but also make it do much more. I get it that it can turn on and off but how does it consider a certain given number and adds that with another number and give the result ?! That is just mind blowing to me.

I tried to look for answers but I couldn't find any. I also want to know about other (Main CPU) processor(s) but I am keeping that for another question.

Thank You !

# Answer
> 3 votes
Both the CPU and that math coprocessor (now a part of the CPU) work in the same way --- using logic gates to implement the actual logic, using flip flops for registers, and using RAM for cache.

Mathematical operations are implemented as a combination of circuits (collections of logic gates) and tables (a type of memory). Their exact implementation depends on the processor, and can be quite complicated and hard to get right (see for example the Pentium FDIV debacle).

To know more, consult a textbook like The Elements of Computing Systems.

# Answer
> 2 votes
I could have done this in comments, but I want to keep it more neat and so, I am doing this as an answer.

So here are some books that can be helpful and in fact are; very informative.

***1***. **The Elements of Computing Systems** By ***Noam Nisan, Shimon Schocken*** \- (Suggested by *Mr. Yuval*)

> **http://www.amazon.com/The-Elements-Computing-Systems-Principles/dp/0262640686**

***2.*** **Code** By ***Charles Petzold***

> http://www.amazon.com/Code-Language-Computer-Hardware-Software/dp/0735611319

***3.*** **How Computers Work** By ***Roger Young***

> http://www.amazon.com/How-Computers-Work-Processor-Edition/dp/1442113987/

***4.*** **Digital Design And Computer Architecture** By ***David Harris*** \-

> http://www.amazon.com/Digital-Design-Computer-Architecture-Edition/dp/0123944244

***5.*** **Inside The Machine** By ***Jon Stokes*** \-

> http://www.amazon.com/Inside-Machine-Introduction-Microprocessors-Architecture/dp/1593276680

***6***. **How Computers Work** By ***Ron White*** \-

> http://www.amazon.com/How-Computers-Work-Evolution-Technology/dp/078974984X/

There are many other books you can look for. These were suggestions on the Amazon page for '*The Elements Of Computing System*' but 'Code' is a very famous and nice book. And so are the others but neither have I read all of them.

Other Helpful Books Are :-

*And again, there are many other books one can find and if you do so, which is not mentioned in the list but you find it to be good, please do post the name of the book and the author at least.*

*Thank You !*

---
Tags: cpu
---


# Question
Title: How to give an approximation algorithm for this unusual bin packing problem?
The usual bin packing problem can be formulated as: \begin{align} & \underset{x,y}{\min} & & B = \sum\_{i=1}^n y\_i\\ & \text{subject to} & & B \geq 1,\\ & & & \sum\_{j=1}^n a\_j x\_{ij} \leq V y\_i,\forall i \in \\{1,\ldots,n\\}\\ & & & \sum\_{i=1}^n x\_{ij} = 1,\forall j \in \\{1,\ldots,n\\}\\ & & & y\_i \in \\{0,1\\},\forall i \in \\{1,\ldots,n\\},\\ & & & x\_{ij} \in \\{0,1\\}, \forall i \in \\{1,\ldots,n\\}, \\, \forall j \in \\{1,\ldots,n\\},\\ \end{align}

where $y\_i = 1$ if bin $i$ is used and $x\_{ij} = 1$ if item $j$ is put into bin $i$

I have a similar problem that is formulated as:

\begin{align} & \underset{x,y}{\min} & & B = \sum\_{i=1}^n y\_i\\ & \text{subject to} & & B \geq 1,\\ & & & \sum\_{j=1}^n a\_{kj} x\_{ij} \leq V y\_i,\forall i \in \\{1,\ldots,n\\}, \\, \forall k \in \\{1,\ldots,n\\}\\ & & & \sum\_{i=1}^n x\_{ij} = 1,\forall j \in \\{1,\ldots,n\\}\\ & & & y\_i \in \\{0,1\\},\forall i \in \\{1,\ldots,n\\},\\ & & & x\_{ij} \in \\{0,1\\}, \forall i \in \\{1,\ldots,n\\}, \\, \forall j \in \\{1,\ldots,n\\},\\ \end{align}

where $y\_i = 1$ if bin $i$ is used and $x\_{ij} = 1$ if item $j$ is put into bin $i$.

You can see that constraint 2 is no longer the same as in the usual formulation. Now, it must be satisfied for each item $k$.

In my problem the items influence each others (by constraint 2). Each item should be packed into a bin (by constraint 3). The objective is to minimize the number of bins used (by the objective function).

How can I solve this problem? Or how can I design an approximation algorithm for it?

I tired to apply the known approximation algorithm for bin packing such as (Next Fit, First Fit, etc.) but I failed because of constraint 2. (For example, I failed to give a proof of the approximation ratio 2 of Next Fit.)

Could you give me some directions where I should go (e.g., is this problem known) and how to solve this problem?

# Answer
> 5 votes
Your problem is known as Multi-Capacity Bin Packing. One of the foundational papers in the area is by Leinberger, Karypis and Kumar, who state a result of Garey, Graham, Johnson and Yao that in the case of $d$ constraints (in your case, $d = n$) many natural algorithms give a $d+1$-approximation.

---
Tags: approximation, algorithm-design
---


# Question
Title: Efficiently split a point cloud into two parts by a hyperplane to maximize the total sum of values associated with one part
I have the following problem in mind. Suppose we have an $n$-dimensional point cloud with $m$ points. Each point in the cloud is associated with a value $X\_i,1\leq i\leq m$. I would like to use a hyperplane to partition this point cloud into two parts, $S$ and $S^c$, in order to maximize $\sum\_{i\in S} X\_i$. Are there any efficient ways to do it?

Any advice would be greatly appreciated. If this cannot be solved efficiently, do there exist a good approximation algorithm?

# Answer
The special case of your problem in which the points are in $\\{-1,1\\}^n$ and the values are $\pm 1$ is known as *Maximum Agreement for Halfspaces*. When talking about approximation, we want a positive objective function, and in this case it is convenient to ask for the number of correctly classified points. A point is correctly classified if either its value is $+1$ and it belongs to $S$, or its value is $-1$ and it belongs to $S^c$.

A trivial $1/2$-approximation algorithm just picks any halfspace and chooses either the halfspace or its complement. One of these satisfies at least half the constraints. Guruswami and Raghavendra showed that no better polynomial time approximation algorithm exists unless $\mathsf{P}=\mathsf{NP}$.

In practice you might be able to use some heuristics, but these of course don't provide any guarantees in the worst case.
> 0 votes

---
Tags: algorithms, optimization, computational-geometry, approximation, discrete-mathematics
---


# Question
Title: How many segmentations are possible for a string length N?
I have a string with length N. I would like to know how many segmentations are possible to it. Consider the example `abcdc` the number of N = 5 All possible segmentations are

```
['abcdc']
['abcd', 'c']
['abc', 'dc']
['abc', 'd', 'c']
['ab', 'cdc']
['ab', 'cd', 'c']
['ab', 'c', 'dc']
['ab', 'c', 'd', 'c']
['a', 'bcdc']
['a', 'bcd', 'c']
['a', 'bc', 'dc']
['a', 'bc', 'd', 'c']
['a', 'b', 'cdc']
['a', 'b', 'cd', 'c']
['a', 'b', 'c', 'dc']
['a', 'b', 'c', 'd', 'c']

```

Then what will happen when `my N tends to infinity` . Any closed form equations?

# Answer
> 3 votes
There are n-1 points where you can break the string. Each is independent of the others. Therefore there are $2^{n-1}$ possibilities to break the string.

---
Tags: combinatorics, strings
---


# Question
Title: How to compute Jacobi symbol efficiently?
How do I compute the Jacobi symbol $(N|A)$ efficiently?

In particular, for every odd $N, A$, define the Jacobi symbol $(A|N)$ as $\prod\_i Q\_{p\_i}(A)$ where $p\_1, \dots , p\_k$ are all the (not necessarily distinct) prime factors of $N$ (i.e., $N =\prod\_i p\_i$), and where $Q\_p(A)$ is defined as below (i.e., $Q\_p(A)$ is the Legendre symbol $(A|p)$).

Arora and Barak claim that the Jacobi symbol is computable in time $O(\log A \cdot \log N)$. How do I see this? What algorithm can be used to compute the Jacobi symbol like this?

---

Motivation:

Sanjeev Arora and Barak sketch a proof that $PRIMES$ is in $BPP$. First they define a function $Q\_N(A)$

$$Q\_N(A) = \begin{cases} 0, & \text{if } \gcd(N,A) \ne 1, \\ 1, & \text{if } A \text{ is a quadratic residue modulo $N$} \\ -1, & \text{otherwise}. \end{cases}$$

Then they state the following properties:

1. For every odd prime $N$ and $A ∈ \[N − 1\]$, $QR\_N (A) = A^{\frac{(N−1)}{2}} \pmod N$.
2. The Jacobi symbol is computable in time $O(\log A \cdot \log N)$.
3. For every odd composite $N$, $|\\{A ∈ \[N − 1\] : gcd(N, A) = 1 \text{ and } (A|N) = A^{\frac{(N−1)}{2}}\\}| \le \frac{1}{2}|\\{A ∈\[N − 1\] : gcd(N, A) = 1\\}|$

Then they give the corresponding algorithm :
Choose a random $1 \le A \le N$, if $gcd(N, A) \> 1$ or $(A|N) = A^{\frac{(N−1)}{2}} \pmod N$ then output “composite”, otherwise output “prime”.

If all the above 3 properties hold then I can see that $PRIMES$ is in $BPP$, but I am unable to prove property 2, regarding the Jacobi symbol.

# Answer
> 4 votes
The Wikipedia article on the Jacobi symbol describes an efficient algorithm for calculating it which uses quadratic reciprocity and operates similarly to the GCD algorithm.

---
Tags: time-complexity, complexity-classes, randomized-algorithms, number-theory, primes
---


# Question
Title: Language that system calls are implemented in
Lately, I have been reading about operating systems design. The idea that all user space programs utilize Kernel services via a "System Call Interface" have got me thinking further into this.

Is system call implemented in specific language like C/C++ on each operating system or it is some sort of assembly language or machine code?

# Answer
System calls are usually implemented in C (or at least that used to be the case) mixed with assembly language. That said, everything gets translated eventually to machine code.
> 1 votes

# Answer
Looking at the linux source code here it would appear that they implement the bulk of it in C with some macros to call some some small amount of assembly code needed to set interrupts and a few other things. I'm not sure exactly how they are setting the interrupts but it would appear that a minimal of the work is done in assembly. Even much of the architecture specific stuff is done in C as seen here. I can't imagine working at that level of complexity outside of a higher level language frankly either.

Not that my experience means anything but this is also how we did things when I took my operating systems class but frankly that's not telling of how a state of the art OS does things. Linux is a much better source of information.

So it looks like things are mostly done in C with a bare minimum done in assembly.
> 1 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: Unary notation representation in Turing Machine
What can be a good convention to represent positive and negative integers in unary notation on a Turing machine? I want to design a Turing machine which acts as a subtractor.So should I partition the integer range to represent positive and negative integers in unary notation or is there some other way?

# Answer
> 1 votes
A reasonable convention would be to take any enumeration of the integers and use it. For example, this enumeration $$ 0,1,-1,2,-2,3,-3,\ldots $$ corresponds to this encoding: $$ \begin{align\*} 0 &\to \epsilon \\ 1 &\to 1 \\ -1 &\to 11 \\ 2 &\to 111 \\ -2 &\to 1111 \\ 3 &\to 11111 \\ -3 &\to 111111 \end{align\*} $$

---
Tags: turing-machines, automata
---


# Question
Title: Why does the recurrence equation for QuickSort consider all the elements in the array?
I have been taught that `QuickSort` has the following recurrence equation in the best case:

$T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c \cdot n & \text{if } n\>1 \end{cases}$

where $c \in \Theta(1)$ and $c \cdot n \in \Theta(n)$. As well for the general case:

$T(n) = \begin{cases} c & \text{if } n=1 \\ T(q) + T(n-q) + c \cdot n & \text{if } n\>1 \end{cases}$

Moreover, the algorithm used in the lecture was the following:

```
Procedure QuickSort(A[p,...,r])
    if p < r
        q = Partition(A, p, r)
        QuickSort(A, p, q-1)
        QuickSort(A, q+1, r)

```

As you can see, the recursive calls don't take care of the pivot element $q$. I understand this occurs as `Partition` moves elements around until the pivot is where it should be is the array ordered. The following is the `Partition` algorithm:

```
Function Partition(A[p,...,r], p, r)
    x = A[r]
    i = p-1
    for j = p to j = r-1 do
        if A[j] <= x
            i = i+1
            Exchange(A[i], A[j])
    Exchange(A[i+1], A[r])
    return i+1

```

My question is: *Why do the recurrence equations assume the algorithm takes all the elements of the array (let it be $n$) if the actual algorithm only takes $n-1$ elements?*

Why can't it be the following?

$T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n-1}{2}) + c \cdot n & \text{if } n\>1 \end{cases}$

Or, more generally, this one?

$T(n) = \begin{cases} c & \text{if } n=1 \\ T(q) + T(n-q-1) + c \cdot n & \text{if } n\>1 \end{cases}$

# Answer
> 4 votes
When you're looking at the behaviour of the algorithm as $n\to\infty$, the difference between $n$ and $n-1$ becomes negligible. The simpler form is easier to deal with and it gives the same answer.

# Answer
> 4 votes
> As well for the general case: \[recurrence with $q$\]

Note how $q$ remains a free variable here; that's bad. It's not the same $q$ for every recursive call, and either way you can not really solve the recurrence. You need to let $q$

* be $0$ or $n - 1$ for the worst case,
* be $n/2 \pm 1$ for the best case, or
* sum over $\sum\_{q=0}^{n-1}$ and take the average by multiplying with $\frac{1}{n}$ for the average case (under the random permutation model).

Note that more involved arguments are needed to see that this last one is actually correct, in particular that the recursion maintains the random model.

As such, the form with $q$ is an intermediate step only.

> Why can't it be the following \[with $n-1$ instead of $n$\]?

It can, and it should. However, the recurrence may be easier to solve if you use $n$ instead of $n-1$. The simplification can be justified if you

* are only interested in asymptotics and
* establish that

$\qquad\displaystyle \frac{T(n)}{T(n-1)} \in O(1)$

as $n \to \infty$. This is the case if $T$ is "smooth" and does not grow too fast.

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


# Question
Title: How to write a closed term with this type?
`X→Y →(X+Y)×Y`

I'm confused about how to get the type `(X + Y)`. If I assume `m: (X + Y), n: X, k: Y` then I can get $${m:X+Y \vdash \lambda n:X.\lambda k:Y.\<m, k\>}$$ which get the right type. But I can't reduce the context `m: X + Y`. So, could anyone tell me how to make it? Thanks a lot.

# Answer
> 4 votes
Whenever a new type constructor is defined, it comes with *introduction* and *elimination* terms. These are *part of the definition*.

In the case of sums, the following are **part of the definition** of what it means to have $X + Y$:

* given types $X$ and $Y$ there is a type $X + Y$
* given a term $e : X$ there is a term $\mathsf{inl}(e) : X + Y$
* given a term $e' : Y$ there is a term $\mathsf{inr}(e') : X + Y$
* (there is also an eliminator and equations which I am not writing down here)

So I think this is the point you missed: we do not just say "there is a type $X + Y$" without anything else, as that would be completely useless. We also provide ways of *constructing* (introducing) and *deconstructing* (eliminating) terms of the new type.

Now that we know that $\mathsf{inl}$ and $\mathsf{inr}$ are there by definition of sum types, it is easy: $$\lambda x : X . \lambda y : Y . \langle \mathsf{inr}(y), y\rangle.$$ By the way, Haskell's djinn package can help you with this (I'd show a demo but OSX El Capitan broke cabal).

# Answer
> 2 votes
However you've formulated sums, you ultimately have two constructors, i.e. functions with type $X\to X+Y$ and $Y \to X+Y$. Often these are called `inl`/`inr`. In Haskell they are `Left` and `Right`. If you're using a Church-encoding, you should work out the right lambda terms.

So, since you have both an $X$ and a $Y$, you have two separate ways of filling in the first component of the result tuple.

---
Tags: lambda-calculus
---


title: Persistent random-access queue

text:
# Question
Title: Persistent random-access queue
I need a queue $\[x\_0, ..., x\_n\]$ that supports the following operations:

* $\operatorname{enqueue}(\[x\_0, ..., x\_n\], x) = \[x\_0, ..., x\_n, x\]$
* $\operatorname{dequeue}(\[x\_0, ..., x\_n\]) = \[x\_1, ..., x\_n\]$
* $\operatorname{lookup}(\[x\_0, ..., x\_n\], i) = x\_i$
* $\operatorname{update}(\[x\_0, ..., x\_n\], i, y) = \[x\_0, ..., x\_{i - 1}, y, x\_{i + 1}, ... x\_n\]$
* $\operatorname{insert}(\[x\_0, ..., x\_n\], i, y) = \[x\_0, ..., x\_i, y, x\_{i + 1}, ..., x\_n\]$
* $\operatorname{delete}(\[x\_0, ..., x\_n\], i) = \[x\_0, ..., x\_{i - 1}, x\_{i + 1}, ... x\_n\]$
* $\operatorname{length}(\[x\_0, ..., x\_n\]) = n + 1$

All operations should be in $O(\log n)$. The data structure should be atomic and persistent, i.e. it is written to a random-access data storage device, such a hard disk or flash memory. Therefore the data structure should minimize the number of seeks. I thought about using Counted B-Trees without keys and with a rollback journal. I also looked at several purely real-time functional data structures that use multiple lists (lists can be efficiently implemented with a file system with a truncate operation) but they seemed to be too complicated or not randomly accessible.

Assume that the filesystem has the following operations:

* write(file, offset, x)
* read(file, offset, length)
* append(file, x)
* truncate(file, length)

Is there any other data structure that I is more efficient or easier to implement while being as efficient?

# Answer
> 2 votes
Yes there is a data structure which name is Treap You can also do other things too (ex. range sum, range min-max, etc.) using this or you can also use BBST (Balanced binary search tree like AVL).

Okay i will explain some terms i am assuming you have some Knowledge about Trees and BST(Binary search Tree)
Q. What Treap is?
A. Treap = Tree + Heap (in easy way)

Q. Use of Treap?
A. its randomized balanced tree basically its contain 2 values first one is data and second is rank (data, rank) and it has two property using data we keep BST(Binary search Tree) property it mean smaller than data will go on left side and bigger will be on right side and rank keep heap property its your choice that you want min heap aur max heap property. trick here is that rank is given uniformly random. So when we heapify using rank height of tree will not exceed O(LogN). so in easy implementation we can get a self balanced binary search tree.

Q. How to implement above requirements?
A. Insert and Delete methods are easy and equal to BST's methods

```
struct Node *insert(struct Node *root, int pos, int data) {
  if(root == dummy) {
    ptr ->left = ptr ->rig = dummy;
    ptr ->size = 1;
    ptr ->pri = rand();
    ptr ->data = data;
    return ptr++;
  } else if(root ->left ->size >= pos) {
    root ->left = insert(root ->left, pos, data);
    if(root ->left ->pri > root ->pri) root = rot(root, root ->left);
  } else {
    root ->rig = insert(root ->rig, pos - root ->left ->size - 1, data);
    if(root ->rig ->pri > root ->pri) root = rot(root, root ->rig);
  }
  update(root);
  return root;
}

```

here you can see 2 methods which are unknown to you actually one it **rot** which is rotation when our tree violate heap property and **update** where you can update your tree's attribute here we keeping size so you can updated this information here

Delete method is homework for you it will be same as insert in above code pos define that you want to insert an element in between pos-1 pos.

okay now lets come on your requirements :

```
enqueue -> call insert and pos will be root ->size
denqueue -> call delete
lookup -> search method same as binary search tree's search method
update , insert -> call insert
length -> root ->size

```

---
Tags: algorithms, data-structures, trees, search-trees, balanced-search-trees
---


title: Segment trees with insertion/deletion

text:
# Question
Title: Segment trees with insertion/deletion
I have a range-query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in the order that they appear in the input. The operations can be one of the following: update a position of the array with a new value, insert a new element at some index of the array, remove an element at some index of the array and query information about a range of the array.

I tried an implementation of Segment Tree where the nodes are stored in an array. Left child of node at index p is at index 2p, right child is at index 2p + 1. This implementation is not enough, because the tree is static. All I can do are range queries and update positions of the original array. Inserting or deleting elements in the original array requires the tree to be rebuilt, so the running time is O(n) (too slow for the test cases). My program is correct, but too slow.

I Googled about Segment Trees with insertion/deletion and I read that is possible to do that with self-balancing binary search trees, like AVL or Red-Black trees. But I'm having trouble to understand how insertion or deletion would work in this dynamic Segment Tree that I need.

Does anybody know something about that?

# Answer
Similar to what you asked, this Problem on the maximum height of solders involves range queries and insertions of elements.

I solved that problem using treap, which can be used to solve your problem as well.

Here is a very brief introduction to treap.

A Cartesian tree is just a binary tree on a sequence of pairs that is

* a heap if we look at only one element of each pair, and
* a binary search tree if we look at the other element of each pair.

In a Cartesian tree, if we assign random values to each heap-ordered element, then the expected height of the resulting tree is $O(\log n)$. This is the idea behind treaps.
> 0 votes

---
Tags: data-structures, search-trees, range-query, segment-trees
---


# Question
Title: Find a graph for which Kruskal's algorithm achieves worst-case running time
I am working on a problem in which I must find a graph with edge weights on n vertices, for which Kruskal's algorithm achieves worst-case running time. I am using a UNION-FIND data structure, but with no optimisations (path compression or weight/height union rules).

The version of Kruskal's which I am using is as follows:

```
Kruskal(G)
  for each vertex  ∈  do MAKE−SET()
  sort all edges in non-decreasing order
  for edge ,  ∈  (in the non-decreasing order) do
    if FIND  ≠ FIND() then
      colour (, ) blue
      UNION(, )
  od
  return the tree formed by blue edges

```

Also, MAKE-SET(x), UNION(x, y) and FIND(x) are defined as follows:

```
MAKE-SET()
  Create a new tree rooted at
  PARENT()=x

UNION(, )
  PARENT FIND() ≔ ()

FIND()
   ≔
  while  ≠ PARENT() do
     ≔ PARENT()
  return y

```

After having looked at this post, my idea was to construct a graph on n vertices, such that there are as many redundant edges as possible and at least one necessary edge which is checked last (this edge must have the greatest weight).

I've looked at the specific cases n = 4 and n = 5 and have tried to construct such graphs in these cases. However, I am struggling to generalise to arbitrary n.

I would appreciate any hints for progressing with this problem. Thank you.

# Answer
> 3 votes
Let the answer be a complete graph $G = (V,E)$ with $|V| = n$ and a weight function $W : E \to \mathbb{R}$

Let the vertices be denoted by $1,2,\dots n$ and edges between $i$ and $j$ as $(i,j)$.

Now define the weights of all the edges as follows: $$W(i,j) = j-1, \forall \ 1 \le i \< j$$

(Assuming you break ties for the edges on the basis of the value of the nodes $i,j$)

If you add a break statement once all $n$ nodes have been merged, then the algorithm will iterate on all the $\binom{n}{2}$ edges (except the last $n-1$) before finishing execution. This is because it will iterate all the edges in non decreasing order and it will find that except for the edge $(1,j)$ all other edges connect nodes belonging to the same disjoint set.

The running time will thus be $\mathcal{O}(\alpha(n + \binom{n}{2}))$

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


# Question
Title: The difference between theoretical complexity and practical efficiency
If I have this pseudocode:

```
for i=0 to n/2 do
   for j=0 to n/2 do
       ... do anything ....

```

The number of iterations is $n^2/4$.

What is the complexity of this program? Is it $O(n^2)$?

What is the intuition formal/informal for which is that complexity?

Next, if i have this other pseudocode :

```
for i=0 to n do
   for j=0 to n do
       ... do anything ....

```

The complexity is again $O(n^2)$ -- is that correct?

Is there any difference between efficiency in practice and theoretical complexity in this case? Is one of these faster than the other?

# Answer
## Big O Formally

$O(f(n)) = \\{g(n) | \exists c \> 0, \exists n\_0 \> 0, \forall n \> n\_0 : 0 \leq g(n) \leq c\*f(n)\\}$

## Big O Informally

$O(f(n))$ is the set of functions that grow slower (or equally fast) than $f(n)$. This means that whatever function you pick from $O(f(n))$, let's name her $g(n)$, and you pick a sufficiently large $n$, $f(n)$ *will* be larger than $g(n)$. Or, in even other words, $f(n)$ will eventually surpass any function in $O(f(n))$ when $n$ grows bigger. $n$ is the input size of your algorithm.

---

As an example. Let's pick $f(n) = n^2$.

We can say that $f(n) \in O(n^3)$. Note that, over time, we allowed notation abuse so almost everyone writes $f(n) = O(n^3)$ now.

Normally when we evaluate algorithms, we look at their order. This way, we can predict **how** the running time of the algorithm will increase when the input size ($n$) increases.

In your example, both algorithms are of **order** $O(n^2)$. So, their running time will increase the same way (quadratically) as $n$ increases. Your second algorithm will be four times slower than the first one, but that is something we're usually not interested in \**theoretically\*. Algorithms with the same order can have different factors ($c$ in the formal definition) or different lower order terms in the function that evaluates the number of steps. But usually that's because of implementation details and we're not interested in that.

If you have a algorithm that runs in $O(log(n))$ time we can safely say it will be faster than $O(n)$ \[1\] because $log(n) = O(n)$. No matter how bad the $O(log(n))$ algorithm is implemented, no matter how much overhead you put in the algorithm, it will always \[1\] be faster than the $O(n)$ algorithm. Even if the number of steps in the algorithms are $9999\*log(n) = O(log(n))$ and $0.0001\*n = O(n)$, the $O(log(n))$ algorithm will eventually be faster \[1\].

But, maybe, in your application, $n$ is always low and will never be sufficiently large enough so that the $O(log(n))$ algorithm will be faster **in practice**. So using the $O(n)$ algorithm will result in faster running times, despite $n = O(log(n))$

\[1\] if $n$ is sufficiently large.
> 7 votes

# Answer
Auberon provided a very good explanation of the **Big O**. I will try to explain what that means for you.

First of you are right. The first code example has $\frac{n^2}{4}$ iterations, but is still in the complexity class `O(n^2)`.

## Why?

The thing about complexity classes is, that we assume that doing something several times is not *that* bad for runtime.

Imagine a Algorithm with complexity `O(2^n)` running for `n=3` and taking 1 second.

We could run this 10 times, and still expect an answer after about 10 seconds.

Now Imagine increasing `n` by 10. The Programm will take `2^10=1024` seconds.

So the computer scientists basically said: "*Man, leading factors are annoying. Let's just assume n grows to infinity and compare functions there*"

Which lead to the **Big O**.

## In Practice

In Practice it is very well possible that a solution with much worse complexity runs much faster (for "small" inputs). It is easy to imagina a Programm that runs in `O(n)` but needs `10^10*n` iterations.

*It is O(n)* but even an `O(2^n)` solution could be faster for small n.

## In summary:

The **Big O** is a useful tool. But you still have to think about how fast your algorithm is in practice, since it only describes how much more time it will need if the input grows.
> 6 votes

# Answer
> If I have this pseudocode:

```
for i=0 to n/2 do
   for j=0 to n/2 do
       ... do anything ....

```

> The number of iteration is $n^2/4$.

Actually, it's $(1+n/2)^2 = n^2/4 + n + 1$.

> What is the complexity of this program? Is correct $O(n^2)$?

That depends entirely on what "do anything" is. For example, if "do anything" is replaced by the line

```
for k=0 to 2^n do {}

```

then the running time is $\Theta(n^22^n)$.
> 3 votes

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


# Question
Title: How do RNN's handle providing output with different dimension than input
It seems like an RNN has to have the ht-1 needs to be the same size as the input vector since they're being added to one another, but if you're doing something like modeling to another language or classification, how would you handle this? I'd imagine you'd just have a fully connected layer that would predict the output, but I was wondering if there is a standard convention?

# Answer
So Basically what happens is the input x is multiplied by a hidden layer U to yield a state vector s, which transforms it to a new dimensionality. Then The recurrent layer W is always a square matrix to maintain the dimensions of s. Lastly, the output matrix V is multiplied to update the matrix to the output dimensionality.

So if you had a vector that was 5 dimensions, and you wanted to multiply it into a state vector of 20 dimensions and an output vector of 2 dimensions, your dimensions would be:

```
x is 5x1
s is 20x1
y is 2x1

U is 20x5
W is 20x20
V is 2x20

```

and your formula is:

```
s = Ux + W*s_(t-1)
y = Vs

```
> 2 votes

---
Tags: neural-networks
---


# Question
Title: Resending old frame when a damaged frame has been received in one bit sliding window protocol
I'm reading Tanenbaum's and Wheterall's book on Computer Networks. I'm trying out some examples of situations that can occur in the **one bit sliding window protocol** for a datalink layer.

The code for the protocol can be found here on page 214.

The situation I was investigating was the following: Let's say client A successfully sends a frame to client B. Client B then sends his frame containing data along with the acknowledgement (ACK) that he received client A's frame correctly (piggybacking). Now somewhere along the way this frame gets damaged. Therefore, in the code, a chksum\_err event occurs. Then the exact same frame client A sent before is sent again. Why? Shouldn't it be the case that client A now sends a frame with the sequence number inverted, new data but the acknowledgement is not inverted? This way, assuming nothing special happens along the way, client B correctly receives a new frame (instead of a duplicate) and client B knows that the frame he sent was damaged so he needs to send it again.

Isn't this the *beauty* of the protocol? Is the code wrong or what am I missing?

# Answer
> 2 votes
> Shouldn't it be the case that client A now sends a frame with the sequence number inverted, new data but the acknowledgement is not inverted?

This could indeed be done when the error occured in the data. i.e. you're sure that it wasn't the acknowledgement or sequence number that was damaged. In that case, sender A could indeed send a new frame as described and avoid sending unnecessary duplicates.

However, although an error can be detected, it can not be detected **where** the error occured (in the data, acknowledgement or sequence number). If the error occured in the aknowledgement number then the client may unrightfully think that his previously sent frame was received correctly while it actually wasn't received correctly and so, if he sents a new frame with new data as proposed in the question, a client will miss a frame!

---
Tags: computer-networks, communication-protocols
---


# Question
Title: What is the difference between "deadlock prevention" and "deadlock avoidance"
I have studied about both of these on many places like this, this and this, but still it is not that much clear that what the actual difference is between these two.

The Wikipedia links (first and second links mentioned above) say about deadlock prevention that:

> The *hold and wait* or *resource holding* conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations)...

and the deadlock avoidance section of the same page says:

> Deadlock can be avoided if certain information about processes are available to the operating system before allocation of resources, such as which resources a process will consume in its lifetime...

so almost in both of these situations we require the processes to provide information about resources in advance.

So can anyone kindly explain in easy-to-understand words that *what the actual difference is in between both of these*.

# Answer
It seems that *deadlock prevention* and *deadlock avoidance* are two names for the same concept. Indeed, the Wikipedia section on deadlock avoidance has been marked as redundant. While the distinction might be taken from the literature, some people at least are arguing that this distinction is superfluous. See the paper The classification of deadlock prevention and avoidance is erroneous by Neumann Levine, which is mentioned in the Talk part of the Wikipedia article.
> 4 votes

---
Tags: operating-systems, deadlocks
---


# Question
Title: Are qubits written in a big-endian or little-endian order when grouped?
Say for instance you layout a quantum simulator like follows:

`amps = [0] * 8 # 3 qubits`

Therefore you are left with the following in binary: `000, 001, 010, 011, 100, 101, 110, 111`

Does the third digit in binary represent the third qubit or the first?

One would assume it would be the third but I'm not certain and I don't want to get the model wrong.

# Answer
> 1 votes
There's no convention. Usually the endian-ness doesn't matter, or else it's clear from the context which endian-ness is being used.

(I'm also not aware of a convention for whether the wires in circuit diagrams are top-endian or bottom-endian. I just always infer from context.)

---
Tags: quantum-computing
---


# Question
Title: How to find a perfect matching with this constraint?
I have a positive integer $n$ and two disjoint sets of nodes $V=\\{v\_1,\ldots,v\_n\\}$ and $W=\\{w\_1,\ldots,w\_n\\}$. I also have a weight function $f:V\times W\to\mathbb{R}\_{\>0}$ and a positive number $\alpha$. The function $f$ is represented by the matrix $\mathbf{F}=\left\[f\_{vw}\right\]$ as:

$$\mathbf{F}=\begin{bmatrix} f\_{11} & \cdots & f\_{1n} \\ \vdots & \ddots & \vdots \\ f\_{n1} & \cdots & f\_{nn} \\ \end{bmatrix}.$$

I would like to create a perfect matching between $V$ and $W$ (that is associate one node from $V$ to exactly one node from $W$) such that some constraint is satisfied (it is given explicitly next). Or, I am looking for a function $a:V\to W$ that is bijective between $V$ and $W$.

The constraint is specified by a matrix $\mathbf{G}=\left\[g\_{vw}\right\]$ defined by: $g\_{vw}=f\_{va(v)},\forall v,w$. For example, if I have $n=3$, $v=\\{1,2,3\\}$ and $W=\\{1,2,3\\}$ and $\mathbf{F}$ is given by: $$\mathbf{F}=\begin{bmatrix} 1 & 3 & 2 \\ 4 & 7 & 1 \\ 7 & 9 & 5 \\ \end{bmatrix},$$ and the bijection is $a(1)=2,a(2)=3,a(3)=1$. The matrix $\mathbf{G}$ will be: $$\mathbf{G}=\begin{bmatrix} 3 & 2 & 1 \\ 7 & 1 & 4 \\ 9 & 5 & 7 \\ \end{bmatrix}.$$

Now, the constraint says that $\alpha\min\limits\_{v}g\_{vv}\geqslant\max\limits\_{v\neq w}g\_{vw}$. With the same example, if $\alpha=1$, the bijection $a$ does not satisfy the constraint since $\alpha\min\limits\_{v}g\_{vv}=1$ and there exists some $w\neq v$ such that $g\_{vw}\>1$.

In summary, I would like to find a bijection between $V$ and $W$, $a:V\to W$, such that $$\alpha\min\limits\_{v}g\_{vv}\geqslant\max\limits\_{v\neq w}g\_{vw},$$ where $g\_{vw}$ is defined previously.

# Answer
> 3 votes
We consider three different cases: $\alpha \< 1$, $\alpha = 1$, and $\alpha \> 1$.

Suppose first that $\alpha \< 1$. Arrange the $n^2$ elements in the matrix in non-increasing order: $x\_1,x\_2,\ldots$. Note that $x\_1,\ldots,x\_n$ must belong to the diagonal, and moreover $\alpha x\_n \geq x\_{n+1}$. Hence the instance is solvable iff $\alpha x\_n \geq x\_{n+1}$ and $x\_1,\ldots,x\_n$ belong to different rows and columns.

The case $\alpha = 1$ is very similar. Let $x\_1 = x\_2 = \cdots = x\_m \> x\_{m+1}$. If $m = n$ then we are back to the previous case. If $m \< n$, then $x\_1,\ldots,x\_m$ must belong to the diagonal. We find out whether it is possible, fix this part of the permutation, and iterate (details left to you). The most interesting case is when $m \> n$. In that case, we use a bipartite perfect matching algorithm to find out whether $n$ of these $m$ elements can be put on the diagonal.

The case $\alpha \> 1$ is slightly more complicated. Let $A$ be the list of elements larger than $\alpha x\_n$. All of these elements (if any) must belong to the diagonal in any solution, since the diagonal always contains an element at least as small as $x\_n$. If $A \neq \emptyset$, we first check that they can be put in the diagonal, fix this part of the permutation, and iterate. If $A = \emptyset$, then we check whether the first $n$ elements can be put on the diagonal. If so, we have found a solution. Otherwise, we know that the solution must contain an element at least as small as $x\_{n+1}$ on the diagonal, and we let $A$ be the list of these elements. If $A \neq \emptyset$, we do what we did before. Otherwise, we use a bipartite perfect matching algorithm to try and fit $x\_1,\ldots,x\_{n+1}$ on the diagonal (deleting first elements conflicting with the current partial permutation). If so, we have found a solution. Otherwise, we continue with $x\_{n+2}$. Eventually we will have made a conclusion, since when reaching $x\_{n^2}$ the answer is positive.

---
Tags: algorithms, np
---