# Question
Title: Constructing the matrix of a controlled quantum operation
How do we construct a matrix that takes into account whether the first qubit is set?

I am trying to construct the controlled-V matrix, but there is no quantum computational paper that describes it so I am looking at CNOT and wondering how the matrix for CNOT determines whether the first bit is set (to apply the NOT part)

Could somebody help?

# Answer
For any gate $U\_n$ on $n$-qubits, you can create a controlled version by taking

$$\text{c-}U\_n = \left (\begin{matrix} I\_n & 0 \\ 0 & U\_n \end{matrix}\right)$$

where $I\_n$ is the identity matrix (of the same dimension as $U\_n$). Note that this gate works on $n+1$ qubits, where the first serves as the control bit.

This should work because the controlled gate is required to satisfy

* $\text{c-}U\_n |0\rangle|x\rangle = |0\rangle|x\rangle $, and
* $\text{c-}U\_n |1\rangle|x\rangle = |1\rangle(U\_n|x\rangle) $

where $|x\rangle$ is an $n$-qubit state. You should be able to check that the above matrix satisfies exactly this.
> 3 votes

# Answer
If you're ever not sure how to turn an operation into a matrix, just do it case by case.

Based on the paper you linked from another question, I'm guessing that your $V$ gate is a square-root-of-NOT gate. That is to say, $V = \sqrt{X} = \sqrt{\begin{bmatrix} 0&1\\1&0 \end{bmatrix}} \ni \frac{1}{2} \begin{bmatrix} 1+i & 1-i \\ 1-i & 1+i \end{bmatrix}$

We need to know what our operation does in every case. Suppose we have a state $\left| AB \right\rangle$ and we're controlling based on $A$ and applying our controlled $V$ gate to $B$. Then we find that:

* If $\left| AB \right\rangle = \left| 00 \right\rangle$ then the output should be $\left| 00 \right\rangle$
* If $\left| AB \right\rangle = \left| 01 \right\rangle$ then the output should be $\left| 01 \right\rangle$
* If $\left| AB \right\rangle = \left| 10 \right\rangle$ then the output should be $\frac{1+i}{2} \left| 10 \right\rangle + \frac{1-i}{2} \left| 11 \right\rangle$
* If $\left| AB \right\rangle = \left| 11 \right\rangle$ then the output should be $\frac{1-i}{2} \left| 10 \right\rangle + \frac{1+i}{2} \left| 11 \right\rangle$

Now we need to decide on a mapping between our kets and a vector. Let's say that $x \left| 00 \right\rangle + y \left| 01 \right\rangle + z \left| 10 \right\rangle + t \left| 11 \right\rangle$ maps to $\begin{bmatrix}x\\y\\z\\t\end{bmatrix}$. That is to say, we go in big-endian order.

We have all the elements we need to make the matrix now. Progress by:

* Arranging the inputs in the order we decided on (i.e. 00 then 01 then 10 then 11)
* Mapping each input's output to a column vector
* Row-wise concatenating the output columns into a matrix

Our outputs are $\left|00\right\rangle = \begin{bmatrix} 1\\0\\0\\0 \end{bmatrix}$, $\left|01\right\rangle = \begin{bmatrix} 0\\1\\0\\0 \end{bmatrix}$, $\left|10\right\rangle = \begin{bmatrix} 0\\0\\\frac{1+i}{2}\\\frac{1-i}{2} \end{bmatrix}$, and $\left|10\right\rangle = \begin{bmatrix} 0\\0\\\frac{1-i}{2}\\\frac{1+i}{2} \end{bmatrix}$ so our matrix for a controlled-$V$ is:

$\begin{bmatrix} 1&0&0&0\\0&1&0&0\\0&0&\frac{1+i}{2}&\frac{1-i}{2}\\0&0&\frac{1-i}{2}&\frac{1+i}{2} \end{bmatrix}$

As you can see, it's basically just a matter of replacing a sub-section of an identity matrix with our target operation. Things get a bit more complicated when there's more qubits, because the interior matrix values get spread out and rearranged and repeated depending on where the controls are and how many uninvolved qubits there are, but you can always fall back on brute force if you're not sure.

(My personal method for computing the matrices of controlled operations is a mathematical hack of the tensor product that special-cases a sentinel value representing "controlled".)
> 3 votes

---
Tags: quantum-computing
---


title: Data transfer at certain frequencies

text:
# Question
Title: Data transfer at certain frequencies
I am curious as to what the maximum data transmission rates are to a given frequency.

Say you have a com channel with a frequency of 10 khz. How many bits/s would you be able to send?

Thanks!

# Answer
Channel Capacity or maximum data rate is the maximum rate at which data can be transmitted over a given communication link, or channel.

In general, information is conveyed by change in values of the signal in time. So more the frequency of a signal, more is the achievable data rate.

For a communication channel,

Δf⋅Δt≈1

To transmit one signal, a pulse of length Δt (in time) is required. If one signal represents one bit, then the data rate is about 1/Δt. So the maximum data rate in bit/second is about the same as the band width Δf in Hertz.

But this is an incredible underestimate of the information capacity of a transmission system. It assumes that you are sending rectangular shaped pulses. Using different encoding schemes, more than one bit can be represented by one cycle of signal.

The channel capacity of a channel increases proportionally with the bandwidth. But in practice, we cannot keep increasing the signal bandwidth infinitely. Apart from this, there are other standard transmission constraints in the form of different channel noise sources that strictly limit the signal bandwidth to be used. According to Shannon Hartley equation, the only limit to data rate in a given bandwidth is, the Signal to Noise Ratio.

Using Shannon formula we can obtain an absolute limit of the maximum data transmission rate.

$C = B + log\_2(1 + S/N)$

C - Channel capacity B - Bandwidth S - Average received signal power over the bandwidth N - Average noise over the bandwidth
> 3 votes

---
Tags: information-theory
---


# Question
Title: How to formulate Traveling Salesman Problem (TSP) as Integer Linear Program (ILP)?
Consider this distance matrix of an asymmetric TSP instance: $$ \begin{matrix} & c\_0 & c\_1 & c\_2\\ c\_0 & 0 & 1 & 2\\ c\_1 & 2 & 0 & 1\\ c\_2 & 1 & 2 & 0 \end{matrix} $$

One optimal tour (with a total distance of 3) is clearly: $$ c\_0 \rightarrow c\_1 \rightarrow c\_2 \rightarrow c\_0$$

Now we can reformulate this as an ILP. Let $e\_{i,j}\in\\{0,1\\}$ denote the presence or absence of the directed edge from $c\_i$ to $c\_j$ in the tour (0 - edge is not in the tour, 1 - edge is in the tour). Then we obtain the ILP by:

1. setting the objective $$\text{minimize}\\;\\;\\; 1\cdot e\_{0,1} + 2\cdot e\_{0,2} + 2\cdot e\_{1,0} + 1\cdot e\_{1,2} + 1\cdot e\_{2,0} + 2\cdot e\_{2,1}$$
2. ensure that we arrive at city $c\_i$ from exactly one other city and depart from $c\_i$ to exactly one other city $$\begin{align\*} e\_{0,1} + e\_{0,2} = 1\\ e\_{1,0} + e\_{1,2} = 1\\ e\_{2,0} + e\_{2,1} = 1\\ e\_{1,0} + e\_{2,0} = 1\\ e\_{0,1} + e\_{2,1} = 1\\ e\_{0,2} + e\_{1,2} = 1 \end{align\*}$$
3. ensure we do not find a set of minor tours (we want a complete tour through all 3 cities) by enforcing the following constraints for the artificial variables $u\_i$ (Miller-Tucker-Zemlin subtour elimination constraints): $$\begin{align\*} u\_1 - u\_2 + 2\cdot e\_{1,2} \leq 1\\ u\_2 - u\_1 + 2\cdot e\_{2,1} \leq 1\\ \end{align\*}$$

Is this transformation correct? Its probably not because when I try to use a Solver it says that the ILP is infeasible.

I tried to follow the steps on Wikipedia: https://en.wikipedia.org/wiki/Travelling\_salesman\_problem#Integer\_linear\_programming\_formulation

**Edit 1**

We can verify that there must be a solution to the ILP by the following considerations:

There are exactly 2 solutions to the equation system under 2. $$\begin{align\*} \text{(1)}\\;\\;\\;e\_{0,1} = e\_{1,2} = e\_{2,0} = 1 \land e\_{1,0} = e\_{2,1} = e\_{0,2} = 0\\ \text{(2)}\\;\\;\\;e\_{0,1} = e\_{1,2} = e\_{2,0} = 0 \land e\_{1,0} = e\_{2,1} = e\_{0,2} = 1\\ \end{align\*}$$

Since there are 6 variables and each variable can have only 2 values, we can easily verify this by testing all $2^6$ variable assignments.

Now we can observe that either $e\_{1,2} = 0 \land e\_{2,1} = 1$ or $e\_{1,2} = 1 \land e\_{2,1} = 0$ holds for the solutions.

In the first case we can satisfy the inequations under 3. by $u\_1 = 2 \land u\_2 = 1$ in the latter case by $u\_1 = 1 \land u\_2 = 2$.

**Edit 2**

This is annoying. I used another tool (LPSolve) to solve the exact same ILP and got the solution instantly. Seems that my transformation was correct and the tool is buggy.

# Answer
> 1 votes
You must have entered your ILP program into the ILP solver wrong. It's easy to verify that the ILP program is feasible, using the procedure I outlined in the comments. In particular, from the tour $c\_0 \to c\_1 \to c\_2 \to c\_0$ we get the assignment $e\_{0,1}=e\_{1,2}=e\_{2,0}=1$ and $e\_{1,0}=e\_{2,1}=e\_{0,2}=0$. Setting $u\_1=0$ and $u\_2=1$, we find a feasible solution: you can easily check by hand that every one of your equations is satisfied. So, you've done something wrong in entering it into the tool.

In the future, you should do that kind of sanity check on your own before asking here.

---
Tags: algorithms, traveling-salesman, integer-programming
---


# Question
Title: Finding a (minimal?) program that maps $M$ items to indices $[0,M)$
Let's say there are $M$ strings that we are trying to create a perfect hash for such that we get as output of the hash $\[0,M)$ with no collisions, when hashing those $M$ items.

I know that there are algorithms that can help you achieve this by finding salt values to use with a given hash function that will cause this to happen (like this one http://blog.demofox.org/2015/12/14/o1-data-lookups-with-minimal-perfect-hashing/).

However, all of the algorithms I've seen are randomized/probabilistic: e.g., there is a probability $p$ for any particular salt value to yield a perfect hash, so keep trying until you find one.

Is there any deterministic algorithm for constructing a perfect hash?

Second, is there a deterministic algorithm to construct a perfect hash that is minimal in size (the smallest program that is a valid perfect hash on these $M$ items)?

Security isn't a concern, and while efficiency of the algorithm to find the mapping is nice, it isn't a requirement. Evaluating whatever mapping program was found should be as efficient as possible though.

# Answer
There is a deterministic algorithm for constructing a perfect hash, if you don't care about efficiency. For instance, you can enumerate all programs (in order of increasing size) and test each one to see which is the first that produces a valid perfect hash. This is a valid deterministic algorithm that is guaranteed to always find a valid perfect hash (and even to find the minimal such program). However, this will be extremely slow for all but the smallest values of $M$, so it's not likely to be useful in practice.

I expect that finding the smallest such program will be NP-hard, and probably $\Pi\_2$-hard (loosely, "even harder than NP-hard"). I don't have a proof of this -- just a suspicion. For example, the problem of circuit minimization is known to be $\Pi\_2$-hard. In other words, given a circuit $C$, it's $\Pi\_2$-hard to find the smallest circuit $C'$ that computes the same function as $C$. Your probably isn't quite the same, but it has a "similar feel", so I would expect your problem (finding the smallest deterministic program that yields a valid hash for the $M$ items) will also be hard.

If you are willing to make unproven assumptions, it is possible to come up with a deterministic algorithm that is also efficient: about as efficient as the randomized/probabilistic algorithms you know of it and want to avoid. In particular, you can take a randomized algorithm and derandomize it as follows: fix a cryptographic-strength pseudorandom number generator (e.g., AES-CTR mode); fix a seed for it (e.g., the all-zeros AES key; or pick a random 128-bit value, and fix it as the AES key); feed this seed the prng algorithm and use it to generate an unending stream of pseudorandom numbers; now run the randomized algorithm, except that whenever it calls for a random number, give it the next pseudorandom number from the output of the crypto prng. Note that this is a completely deterministic algorithm: the seed is hardcoded into the code of the algorithm and fixed for all time. Here's what we know: if the pseudorandom number generation algorithm is cryptographically secure, and if the randomized algorithm outputs the correct answer, then (with high probability over the choice of seed) the deterministic algorithm also outputs the correct answer.

This means that if you know how to build a cryptographically-secure pseudorandom number generator, you can convert any randomized algorithm into a deterministic algorithm. It may be surprising that cryptography has anything to do with this subject, since we don't require kind of security properties from the hash, but it turns out that this construction gives a generic way to derandomize any randomized algorithm. Here's how to see the connection: the definition of what it means for a prng to be cryptographically-security is that no polynomial-time algorithm should be able to tell that it is receiving pseudorandomness rather than real randomness; thus, we can run the randomized algorithm, and swapping out the true-random bits for pseudorandom bits won't mess up the algorithm.

Thus, this will let you build a deterministic algorithm that is correct and efficient, if AES is secure (or one that works if factoring is hard, or based on any other cryptographic assumption). It's widely believed that AES is secure (and factoring is hard, etc.), even though we have no proof, so this provides a reasonable practical solution to your problem, even though we have no proof that it works.
> 4 votes

---
Tags: data-structures, hashing
---


# Question
Title: Machines whose languages are their own encoding
Is the language $S = \\{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \\{\langle M \rangle\\}\\,\\}$ decidable, recognizable and/or co-recognizable?

I tried diagonalization but can only prove that $R = \\{\langle M \rangle \mid M \text{ is a Turing Machine and } \langle M \rangle \notin L(M)\\}$ is not recognizable, which does not seem to help in this case...

# Answer
> 4 votes
Using the recursion theorem, for any Turing machine $T$ you can construct a Turing machine $M$ such that on input $\langle M \rangle$, $M$ executes $T$ (on the empty tape), and otherwise $M$ immediately rejects. You can use this to show that $S$ is not decidable. Using the same ideas you can explore its recognizability and co-recognizability.

---
Tags: computability, reductions, undecidability
---


title: How to simplify boolean expression?

text:
# Question
Title: How to simplify boolean expression?
I am having trouble simplifying logical expressions to a much simpler form, can someone provide me some insight on how to approach the problem?

Let's assume i have the following expression: $ABCD + A\bar{B}CD$.

I am aware of the De Morgan's law, but not sure how to apply them in this case.

Thank you!

# Answer
> 0 votes
What kind of simplification are you looking for ?

In the case you've given, $ABCD+A\bar{B}CD= ACD(B+\bar{B}) = ACD $.

In any case, this is a set of laws of Boolean algebra that might be helpful.

# Answer
> 0 votes
Starting with an expression in canonical normal form, you can simplify it by applying normal algebraic methods `ABCD + ABbarCD = ABCD(1 + bar) = ABCD` or in less obvious cases using a Karnaugh map.

---
Tags: logic, proof-techniques, boolean-algebra
---


# Question
Title: VC dimension of monotone disjunctions of length k over n variables?
There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log\_2 {n \choose k}$. I'm wondering if this is bound at $k \log\_2 n$? (Possibly follows from combinatorial identities).

More generally I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection: "Further, it is NP-hard to learn a disjunction of $k$ variables as a disjunction of few than $k \log n$ variable." The author states this without proof; I'm assuming it's well-known or obvious but am trying to figure out why or where it is proved.

# Answer
> 1 votes
Yes. This bound follows by a little bit of straightforward manipulation:

$${n \choose k} = {n \times (n-1) \times \dots \times (n-k+1) \over k!} \le {n \times n \times \dots \times n \over 1} = n^k.$$

Now taking the logarithm of both sides, we see that

$$ \lg {n \choose k} \le \lg(n^k) = k \lg n.$$

The bound can also be derived from bounds listed in Wikipedia: it follows from the fact that ${n \choose k} \le n^k/k!$. Check out Wikipedia in the future -- it's often helpful!

---
Tags: learning-theory, vc-dimension
---


# Question
Title: Do polynomial reduction functions work both ways?
For example to prove 3-Sat ≤p Independent Set do I just have to prove this theorem:

Theorem- Formula F is satisfiable IFF graph has an independent set.

If I have to prove it this way does this also mean that Independent Set ≤p 3-Sat as well since the theorem goes both ways?

# Answer
The statement

> Formula $F$ is satisfiable $\iff$ graph has an independent set

is imprecise, since it does not specify which graph we are taling about. Correcting this, we get:

> There is a polynomial-time function $\mathcal{G}$ from formulas to graphs such that, for all formulas $F$, $F$ is satisfiable $\iff$ $\mathcal{G}(F)$ has an independent set

Note that, once properly written like this, the statement is no longer symmetric: the reduction function goes in one way (formulas to graphs), and not the other way around. So, proving the above does not also prove the converse reduction.

The converse reduction (from independent set to 3-SAT) holds, but to prove that we need another reduction function $\mathcal{F}(G)$ mapping graphs into formulas.
> 6 votes

---
Tags: complexity-theory, reductions, proof-techniques, 3-sat
---


# Question
Title: Is shuffling a set of items after popping an item meaningfully more random than doing it once, before starting?
I'm working on a thing to randomly assign people into a shift. There's mostly 2 sets of people, "free" and "assigned".

Is shuffling the "free" set after assigning an employee meaningfully more random than just doing it before I start putting people into the "assigned" set? How can I come up with proof of this?

# Answer
> 5 votes
Say we have $n$ people. After shuffling the whole list (once), every person occupies every position with probability $1/n$.

Shuffling before each draw means every choice is uniformly random; that is, because the choices are now stochastically independent, being drawn as $i$th person has probability

$\qquad\displaystyle \frac{1}{n-i+1} \cdot \prod\_{k=1}^{i-1} \Bigl(1-\frac{1}{n-k+1}\Bigr) \quad=\quad \frac{1}{n}$.

So no, shuffling repeatedly does not "add" any randomness -- whatever that would mean. It's uniform, i.e. "fair", to begin with, so what would "more random" mean?

The correct statement is: repeated shuffling does not change the distribution. Which means it is unnecessary, but also not harmful if it eases the mind of laymen participants.

# Answer
> 3 votes
Here is a proof by converse. If the second is not random then you have no proof the first is random.

A shuffle is only valid if every position is random. If every position is not random then the first position is not random.

Once you pop, the free person has been removed. The remaining is exactly the set of free.

---
Tags: algorithms, probability-theory, randomized-algorithms
---


# Question
Title: Find the longest contiguous subsequence such that its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$
You are given $N$ $(1 \le N \le 10^6)$ positive integers $a\_1, a\_2, \ldots, a\_N (1 \le a\_i \le 10^6)$ and two positive integers $D$ $(1 \le D \le 10^6)$ and $M$ $(1 \le M \le 10^6)$

Find the longest contiguous subsequence such that

1. its sum $(a\_i + a\_{i+1} + \cdots + a\_j)$ is divisible by $D$, and
2. $(a\_i + a\_{i+1} + \cdots + a\_j) \le D\cdot M$.

I can find the longest contiguous subsequence such that its sum is divisible by $D$, but I don't know how to include the second condition. Can anyone help me to solve this problem? I think it should work in something like $O(N)$ or $O(N \cdot \log N)$.

To find the longest contiguous subsequence such that its sum is divisible by $D$, I use the fact that $(a\_i + a\_{i+1} + \cdots + a\_j)$ is divisible by $D$ if and only if $(a\_1 + a\_2 + \cdots + a\_{i-1}) \mod D = (a\_1 + a\_2 + \cdots + a\_j) \mod D$. So, I calculate prefix sum and for every possible remainder I remember when it first occured.

# Answer
> 2 votes
There exists a linear time algorithm.

1. Compute partial sum $s\_j = \sum\_{i=1}^j a\_i$ and their remainders $r\_j = s\_j \mod D$.
2. Consider the sequence $\\{(j,s\_j,r\_j)\\}\_{j=0}^N$. For each $0\leq r \< D$, compute the subsequence consisting of all tuple $(j,s\_j,r\_j)$ such that $r\_j = r$. An easy approach is to sort the tuples in the sequence by their third component, using an stable sorting algorithm ($O(N \log N)$ time). In this problem, $D \approx N$, so we could use bucket sort, improving the running time to linear; otherwise, using hash could also improve the running time to linear.
3. For each subsequence, apply the following algorithm on it.

1. Pick two pointer $i,j$, both initialized as the first element in the subsequence.
    2. If $s\_j - s\_i \> DM$, point $j$ to the successor of $(j,s\_j,r\_j)$ in the subsequence, otherwise point $i$ to the successor of $(i,s\_i,r\_i)$ in the subsequence.
    3. Repeat step 2 until $j$ points to the last element in the sequence.

Among all temporary values of $(i,j)$, find one that maximize $j-i$ under constraint $s\_j-s\_i \leq DM$.

---
Tags: algorithms, optimization, combinatorics, number-theory
---


# Question
Title: What is M referring to when talking about memory size( 4M x 8)
In the following paragraph its talking about memory and it throws M into the L X W of memory notation and i'm confused on how 4M = 2^22. Thanks in advance

PARAGRAPH:

Memory is built from random access memory (RAM) chips. (We cover memory in detail in Chapter 6.) Memory is often referred to using the notation length X width (L X W). For example, 4M X 8 means the memory is 4M long (it has 4M = 2^2 X 2^20 = 2^22 items) and each item is 8 bits wide (which means that each item is a byte). To address this memory (assuming byte addressing), we need to be able to uniquely identify 2 ^ 22 different items.

# Answer
M in this context is just defined to be $2^{20}$, so if you have M items (bits, bytes, whatever), you'll have $2^{20}$ of them. The letter was chosen since it's the first letter in the term mega, meaning a million. Since $2^{10}=1024$ is close to $1000$, we'll have $2^{20}=(2^{10})^2≈(1000)^2=1000000$. M is sometimes called a "binary million".
> 2 votes

---
Tags: memory-access
---


# Question
Title: Creating an O(n log n) time and O(n) space algorithm for counting pairs in an array
Given an integer array $a$, create a function, $\text{int} \\; \text{pairs}( \text{int} \\;a\[\\;\])$ that returns the number of equal element pairs in the array. For example, given the array $a=\[2,5,1,2,5,1,1,6\]$ the pairs are $(2,2), (1,1), (1,1), (1,1)$ and $(5,5)$, so the function should return $5$. The solution needs to run in $O(n \log n)$ time and $O(n)$ space.

My algorithm first sorts the array using quick sort in $O(n \log n)$ time, then go through the sorted array and for each chunk of equal elements, keep track of the size of the group(which resets to $1$ when a distinct element is next), runs in $O(n)$ time.

If the next element equal the previous element, then increase the group size variable.

Otherwise, if the group size variable is bigger than $1$, add $n \choose 2$, where $n$ is the group size, to the overall sum of pairs variable(initially $0$), then reset the group size variable to $1$.

The problem I have is that, although the algorithm is correct, the algorithm runs in $O(n^2)$, which I think is because of the $n \choose k$ method.

The pseudo-code for my $n \choose k$ method is:

```
int binomial(n,k)
    if(k>(n-k)) k=n-k

    int b=1
    for(int i=0, m=n; i<=k; i++, m--)
        b=b*m/i

    return b

```

If the method does run in $O(n^2)$, then can I modify it to make it $O(n \log n)$. If its not possible to make a binomial coefficient method to run faster than $O(n^2)$, then does anyone have another algorithm for achieving the number of pairs from the array.

# Answer
Just evaluate $\binom k2$ with $\frac{k(k-1)}2$, this takes $O(1)$.

---

Note that if the pairs are to be counted "without replacement", the formula is $\lfloor\frac k2\rfloor$.
> 3 votes

---
Tags: algorithms, combinatorics, arrays
---


# Question
Title: Shuffling a file on disk using $O(\log n)$ memory
How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place?

~~If the file had size $2^m$, then we can first split the file into 2-byte chunks, shuffle them individually, then shuffle each set of neighboring 2 chunks and merge, doing this recursively. Merging can be done using constant memory by reading the start of a chunk and swapping them with another.~~

~~But if the file size is not $2^m$ then the above doesn't really work, as for a 3-byte file the last byte cannot be in the middle position. (the chunks here are `[1, 2]` and `[3]`).~~

\[EDIT\] This doesn't generate all permutations as Yuval Filmus points out.

\[EDIT 2\] The paper "Random permutations on distributed, external and hierarchical memory" seems like a close match. Other refs/ideas welcome.

# Answer
The algorithm you suggest doesn't result in a uniform permutation. An in-place algorithm which works for every file size is the Fisher–Yates shuffle.
> 5 votes

# Answer
Raw idea:

1. Divide your file in blocks sized with the available memory. Use Fisher-Yates to shuffle the blocks.
2. Shuffle merge the blocks by group of 2 (when it remains $N\_A$ bytes in block A and $N\_B$ bytes in block B, take the byte of block A with probability $N\_A/(N\_A+N\_B)$), for now consider that we are not trying to do that in place and put the result in another file.
3. Repeat, at each step the size of the block is doubled, until there is only one block. You have your shuffling.
4. To make it in replace, remark that this is in fact a merge sort using random choice instead of comparison. Thus adapt a in-place merge sort algorithm, using shuffling merge instead of sorting merge for the merge step (IIRC, you'll need $O(\log N)$ file positions for that, but I doubt it will dominate the three disks sectors buffers needed somewhere in the system to make it works)
> 2 votes

---
Tags: algorithms, randomized-algorithms, permutations, randomness, in-place
---


# Question
Title: How is the Delta Rule derived in neural networks and what is the explanation for the algebra?
I am currently trying to learn how the Delta Rule works in a neural network. So far I completely understand the concept of the Delta Rule, but the derivation doesn't make sense. My question is how is the Delta Rule derived and what is the explanation for the algebra. Currently I am writing equations to try to understand, they are as follows:

*Desired* = (*Input* * *Weight*D)

*Actual* = (*Input* * *Weight*A)

*Error* = (*Input* * *Weight*D) - (*Input* * *Weight*A)

*Error* = *Input* (*Weight*D \- *Weight*A)

However, as stated Here, the *ΔWeight* is understood to be *Error* * *Input*, where as I derive it to be *Error* / *Input*. I fully understand the concept of correcting the weights in a neural network, however, I do not understand how the algebra and derivation of the Dela Rule work to re-adjust the weights to correctly represent the output. I will explain my current understanding to help you understand why I may be confused. Because the *Input* is constant whilst you attempt to find a correct weight, you can factor it out. This leads me to the equation that the *Error* is equal to the *Input* times the difference between the correct and incorrect weights. This is also very clear. However I do not understand where they go from here to get the equation to correct the weights. How is the required net change derived from this? How does the algebra behind simply *Input* * *Error* work? Thank you.

# Answer
> 1 votes
Your equations are wrong on several counts. First of all, the weights and the inputs are both *vectors*. Second, the value of actual is given by $\operatorname{sgn}(\langle \mathit{Input}, \mathit{Weights} \rangle)$, in words, the *sign* of the inner product of the input and the current weights. Similarly, the desired output is either $+1$ or $-1$. Therefore the error is either $+2$ (if the desired was $+1$ but the actual was $-1$) or $-2$ (in the opposite case). Third, we don't want to "solve" for the weights, since this would erase everything that we have learned so far.

The idea of the learning process is to give negative feedback. Suppose that we got $-1$ but we expected $+1$. We want to change the weights so that on the same input, $\langle \mathit{Input}, \mathit{Weights} \rangle$ will be larger. The most economical way (in some sense) is to update the weights with a new vector proportional to the input, since the input is the vector most correlated with itself (that is, the unit vector $w$ maximizing $\langle \mathit{Input},w \rangle$ is proportional to $\mathit{Input}$). Thus we increase the weights with some multiple of the input. If the error were in the other direction, we would decrease instead of increase — which is why we multiply the input by the error.

---
Tags: algorithms, neural-networks
---


# Question
Title: Rice's Theorem: implication of having an undecidable property
I understand the assumptions that have to be true about a property or set of properties in a Turing machine description for Rice's Theorem to apply.

But then what? If a set of Turing machines have an undecidable property, is the language itself necessarily undecidable? Or only if you can find a reduction from a known-undecidable machine is the language undecidable?

What does it really say about a language if it has an undecidable property? Are machines that recognize that language undecidable?

# Answer
An undecidable property $\pi$ of Turing machines is the same as an undecidable language consisting of all encodings of Turing machines satisfying $\pi$. We identify the property with the language of encodings of Turing machines satisfying the property.

The fact that a language is undecidable just means that no Turing machine decides the language — this is the definition of undecidability. In particular, no machines recognize the language, assuming *recognize* means *decide*; a machine $T$ decides a language $L$ if $T$ terminates on all inputs, on inputs $x \in L$ returns $1$, and on inputs $x \notin L$ returns $0$. A *machine* cannot be undecidable, only a *language* can be undecidable.
> 5 votes

# Answer
You are talking about two things here. Consider a non-trivial property $P$ of languages. $P$ can be anything, for instance, does the language contain a string of prime length or not.

Now there are a set of *Turing Machines* whose languages have this property $P$. Let,

$$S = \\{\langle M\rangle \mid\text{ Language of M satisfies }P\\}\\,.$$

Now, Rice's Theorem says that $S$ is undecidable. This means that you cannot build a decider that takes the description of a Turing Machine and tells whether the language of the input machine has a particular non trivial property. It does **NOT** say that for any $L$, ($L \in P $) $L$ is undecidable.

Consider the language $L = \\{10\\}$. This language $L$ is in $S$ (note that I am saying $L \in S$). Clearly, the language is decidable even though $S$ is not.

Hope that clears your doubt.
> 0 votes

---
Tags: computability, undecidability, rice-theorem
---


title: Algorithms on random geometric graphs

text:
# Question
Title: Algorithms on random geometric graphs
A random geometric graph (https://en.wikipedia.org/wiki/Random\_geometric\_graph) is constructed by choosing $n$ points in $\mathbb{R}^d$ at random according to some distribution, and setting $p\_i \sim p\_j$ if $\\|p\_i - p\_j\\|\<r$, for some parameter $r$. Geometric graphs are of use in modelling real world networks.

For example, we can model a transportation map using the uniform distribution on $\[0,1\]^2$.

I am interested in whether there are good graph theoretic algorithms for dealing with these graphs. For example, is there an algorithm for finding the shortest path between two vertices that is better (in expectation) for these graphs than BFS? Obviously such an algorithm would be useful for GPS manufacturers.

Does research like this exist?

# Answer
> 4 votes
The graphs that you get are known as unit disk graphs. There is a vast literature about algorithms on unit disk graphs. Since you are asking about shortest paths, check out this article by Cabello and Jejcic. Of course all of this will not take into account that the graphs are generated by some random process.

For further references consult the wikipedia page or the Cabello and Jejcic paper.

---
Tags: algorithms, graphs
---


# Question
Title: LTL properties in bounded model checking via assertions
Is there a way to check LTL properties in a bounded model checker?

As an example, consider a liveness property ($G F p$ - always eventually $p$)? Suppose we have the following trivial program

```
#include <pthread.h>
int a = 0;
void * f(void * x)
{
  a = 1;
  return x;
}
int main()
{
  pthread_t t;
  pthread_create(&t, 0, f, 0);
  while (a == 0);
  return 1;
}

```

Is "always eventually main terminates" expressible in a bounded model checker using only assertions?

In principle, you can construct a Büchi automaton from an LTL formula, express it in the modeling language (e.g. as C code) and run it in parallel to the model/program. However, unbounded loops pose a problem to the bounded model checker. Hence, I wonder how such properties can be expressed using assertions, e.g. in CBMC.

# Answer
The property "always eventually main terminates" should be expressible and verifiable in a bounded model checker. For such properties, the model checker would either verify the property or find a "acceptance cycle" that shows that there exists a loop in an execution trace that does not satisfy the property (by considering execution traces of bounded lengths).

For example, the given property can be expressed in the SPIN model checker with:

```
int a;
bool end;

proctype thread1() {
  a = 1;
}

init {
  a = 0;
  end = false;
  run thread1();
  do
  :: (a == 0) -> skip;
  od;
  end = true;
}

ltl prop { always (eventually end) }

```

The code follows the given C code, where `do` simulates checking the condition with `while` loop. When checking if `prop` holds, SPIN will find an "acceptance cycle" that shows that main might get constantly scheduled for execution and starve thread1, thus refuting the formula. If a "fair" scheduler is assumed (e.g. with enforcing "weak fairness" SPIN reference), the property will be proven correct.

Note that although such (liveness) properties should be supported, by expressing them in LTL (or other logics like CTL), it is not clear how could they be expressible only with assertions (since assertions state something about the state at particular program point).
> 2 votes

---
Tags: formal-methods, model-checking, linear-temporal-logic, software-verification
---


# Question
Title: Synchronisation and ordering in distributed systems
I have been wondering, what are some ways to handle synchronisation and/or sequencing issues in distributed systems. For example, assume multiple homogeneous nodes listening on a stream of messages and updating a data store based on those messages. Let's say 2 updates for a particular record enter the queue, one at t1 and the other at t2 (t2 \> t1). Further, the t1 packet is consumed by a node n1 and the other one by n2. Now, what would happen if due to computational or network latencies, n2 processes the packet earlier than n1 and updates the data store. Since n1 has an older update, it should not update the data store.

One way I can think of, is to maintain a per attribute versioning of the record and generate a sequence number for each message based on which updates should be made. We could also use timestamps but we would run into issues if the clocks across the nodes drift.

Is there a standard universal way of tackling these sequencing issues? Is this what ZooKeeper does? Are there any interesting reading materials on this topic?

# Answer
At a high level, you are considering consistency models (@wiki) in distributed systems, like a distributed replicated data store in your example. Consistency models specify what values may be returned by a *read* given that memory operations may only be partially ordered. Note that this has imposed restrictions on the order in which all the operations are performed.

There are lots of different consistency models, as indicated in the wiki article. Informally each of them defines a partial order over the operations. One of the common implementation methods is to utilize ***broadcast service***. Not surprisingly, there are various broadcast service with different *ordering* (what you are probably interested in) and *reliability* (concerning fault tolerance) requirements. The following description is quoted from Chapter 8 "Broadcast and Multicast" of the book "Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2nd Edition) By Hagit Attiya and Jennifer Welch. 2004.":

> Ordering: Do processes see all messages in the same order or just see the messages from a single process in the order they were sent? Does the order in which messages are received by the broadcast service preserve the happens-before relation?
>
> Reliability: Do all processes see the same set of messages even if failures occur in the underlying system? Do all processes see all the messages broadcast by a nonfaulty process?

---

This Technical Report: A Modular Approach to Fault-Tolerant Broadcasts and Related Problems; 1994 gives a more comprehensive formal framework of broadcast service. It has also related the consensus problem with atomic broadcast. Consensus is also popular in distributed data storage systems, by implementing a replicated state machine.

---

As for your comment:

> I would also be interested in any implementations of these which are in production or used by large scale companies?

Most distributed storage systems have considered such *consistency models* issues and their implementations. Again, different storage systems are targeted for different application scenarios, and thus adopt different consistency models and implement different ordering strategies.

I will name a few keywords and it is not difficult for you to find papers or articles about them: Amazon's Dynamo, Yahoo!'s PNUTS, Google's Bigtable, ZooKeeper, COPS@SOSP'11, Cassandra, HBase, ...
> 1 votes

---
Tags: distributed-systems, concurrency, consensus
---


# Question
Title: Context-free grammar for "member of"/set membership?
I wonder whether context-free grammar (or what else?) can be used to implement "member of" structures, which describe that **something is a member of something**.

For example, I want to be able to infer the statement:

> **John Lennon** is in **Beatles**.

The inferring process should return True since in the grammar John Lennon has been defined to be a member of the Beatles. If John Lennon weren't defined to be found in Beatles, I'd want to return False.

It does not look like a typical CFG product. Or could it be?

Or what kind of parsing and/or formal language technique is usable for this?

# Answer
> 1 votes
So you want to model expressions of the form

```
(function A B1 B2 B3 ... BN)

```

with a context-free grammar.

That's clearly possible; note that the term itself almost directly corresponds to a regular expression, i.e. you do not even need the full power of context-free grammars.

Consider this, for example (written in something like EBNF):

```
fct_appl = "(" fct_name set_name atom_name+ ")"

```

Here, `X_name` are tokens or other rules. If you separate parser and lexer, they would be lexer rules. If there are no syntactic differences between identifiers, you can use this

```
fct_appl = "(" ident ident ident+ ")"

```

This applies only to functions with one atomic and one list-type parameter, of course. You could also generalize to this:

```
fct_appl = "(" ident+ ")"

```

In any case, the *semantics* have to be defined elsewhere.

---

It does not really matter if you use programming-language style syntax like above, or natural-language style syntax like this:

```
my_membership = ident "is a" ident

```

This is all you need. Whether it's pre-, post- or infix, whether you use `is a` or , these are all design decisions that mostly go away after parsing¹ the syntax. Translate your parse tree into an AST and the information you get is the same: A is a B.

---

1. Some nasty corner cases regarding ambiguity and left-/right-recursion may happen and depend on your choice of syntax.

---
Tags: context-free, formal-grammars, natural-language-processing
---


# Question
Title: AVL tree such that each insert causes rotation (single or double)
Could you give me an example of an AVL tree for which inserting an element at an *arbitrary* (i.e. every) position causes a rotation (double or single)?

I have tried to come up with an example, but I didn't manage to.

# Answer
> 4 votes
### Short answer: it depends.

The answer depends on what is the set of the possible elements of the AVL tree.

### Natural numbers, no duplicates allowed.

**Yes**, there is an AVL tree requiring a rotation on the next insertion, whatever that is:

```
      1
     / \
    0   3
       / \
      2   4

```

The next insertion has to be a natural $\geq 5$ and cause a rotation.

Similarly,

```
      0
       \
        1

```

will rotate as soon as any natural (which has to be $\geq 2$) is inserted.

### Integer numbers, no duplicates allowed.

**Yes**, there is an AVL tree requiring a rotation on the next insertion:

```
      0
     / \
   -1   1
   /     \
 -2       2

```

The next insertion has to be $\leq -3$ or $\geq 3$.

### Rational numbers, real numbers, strings.

***No***, there is no AVL tree requiring a rotation on the next insertion. We now prove this claim.

These sets satisfy the following property, which we now assume.

**Assumption.** Let $V$ be the set of the possible elements of the AVL tree. Given any two $x,y \in V$, with $x \< y$, there exists $z \in V$ satisfying $x \< z \< y$.

**Proposition.** For every $n$, any AVL tree having height $n$ admits at least one insertion requiring no rotations (a *simple* insertion).

**Proof.** We proceed by induction on $n$.

For $n \leq 1$, it is trivial.

By the induction hypothesis, assume every AVL tree with height $\< n$ admits a simple insertion. Take $T$ to be any tree with height $n$, and name $S,U$ its immediate subtrees. W.l.o.g., assume $height(S) \leq height(U) = n - 1 \< n$ (otherwise, swap $S,U$). Hence, $S$ admits a simple insertion $p$.

Modify $p$ so to ensure that, once inserted into $T$, it is inserted into the $S$ side. This is trivial if $p$ falls "inside" the elements of $S$. If instead it is the new minimum/maximum of $S$, make sure it is larger/smaller than the root of $T$, exploiting our assumption above.

Hence, performing an insertion of $p$ into $T$ can not cause any rotation inside the $S$ subtree. Further, it can not cause a rotation around the root of $T$, since this insertion can increase $height(S)$ at most by one, so the AVL invariant $|height(S) - height(T)|\leq 1$ still holds. Hence, there is a simple insertion in $T$.

**QED.**

### Duplicates allowed.

The above proof also holds when duplicates are allowed. In that case, one can insert a duplicate of the root of $T$ in either side.

# Answer
> 1 votes
"Every insert causes rotation" - it cannot happen.

Example:

If you add 5, there is rotation, but if you add 0, there is no rotation. Balance in AVL tree is {-1; 0; 1} and then if it gets bigger (-2 or 2) it rotates.
This implies that only addition of node on one side will cause rotation.

If I understood your question - you wold like such instance of AVL tree that no matter what you add it will rotate (probably without duplicates) - this is not possible.

I do understand that more formal way would be preffered, and I would love to state formal inductiin for all trees, ommiting instances with less than tree nodes, but there is no instance of such tree that would work for initial inductive step.

In very standard implementation AVL does not support duplicates - for example you use it as backend to associative array, then overwriting is desired effect.
Additional field like $count$ will allow multiplicity, or list to preserve values, but still rotation will not occur, which initially was not the point.

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


# Question
Title: Proving that language, with $|\Sigma|=1$, is irregular by Myhill–Nerode theorem
We have $\Sigma =\\{0\\}$ and $$L=\\{0^{2^n} \mid n\ge 0\\}$$ How to prove that $L$ is irregular by using Myhill–Nerode theorem?

At other languages with $\Sigma \>1$ we can usually separate the word or something like this with combination and this how we can show that two words are not at the same equivalent class....
But what we can do at this case?

Here what I tried:
Assuming that $i\ne j$, then $0^{2^i+1}$ is not at the same equivalent class with $0^{2^j+1}$, why?
Let mark: $p$ - the amount of $0$'s that we need to add to $0^{2^i+1}$ to be $0^{2^{i+1}}$, $q$ - same thing but with $j$ instead of $i$.
Of course $p\ne q$, hence:
$0^p\in 0^{2^i+1}$ but $0^p\notin 0^{2^j+1}$.

I'd like to know if I'm right at my and I should continue or try a different way...

Thank you!

# Answer
Your idea is basically correct, but your argument could be written in a clearer way. You want to say that if $i \neq j$ then $0^{2^i+1},0^{2^j+1}$ are inequivalent. You propose to consider adding the word $0^{2^i-1}$ to both, obtaining $0^{2^{i+1}},0^{2^i+2^j}$. The first word is clearly in $L$, whereas the second isn't, though an argument is required (left to you). This shows that the infinite set $\\{0^{2^i+1} : i \geq 0\\}$ consists of pairwise inequivalent words (modulo $L$), so $L$ is not regular.

In fact, *all* words $0^n$ are pairwise inequivalent modulo $L$ – see if you can prove that. (The argument is very similar.)

For languages over a unary alphabet there is a simpler characterization. Let $L = \\{0^n : n \in I\\}$. Then $L$ is regular if and only if $I$ is eventually periodic, which means that for some $m \geq 1$, $n + m \in I$ iff $n + 2m \in I$. The set of powers of two is not eventually periodic since it has arbitrarily large "gaps". (A formal argument is similar to your proof.)
> 2 votes

---
Tags: regular-languages
---


title: Variations of Depth First Travesal

text:
# Question
Title: Variations of Depth First Travesal
While learning depth first traversal, I realise there are two approaches that are followed.

**Method 1**. The first one is as given in the Forouzan's book is as follows:

1. Push the initial node onto the stack
2. Pop the stack
3. Process the popped out node
4. Push all its adjacent nodes onto the vertex
5. Go to step 2.

**Method 2**. Then there is a version of depth first traversal as given in CLRS:

1. Push the node onto the stack
2. Process the pushed node
3. Push one of its adjacent node onto the stack.
4. If there is no adjacent node to the stack top node, then pop it.
5. Go to step 2.

CLRS does not explain it in terms of push and pop operation on stack. However I made this push pop version equivalent to CLRS Depth First traversal explanation. This approach is also explained in this video.

I observe the following points:

1. The two versions yields different stack contents and processing sequence.
2. Method 1 pops out the node before pushing its neighbor. Method 2 pops out the node after all its descendants are processed.
3. Method 1 pushes all adjacent nodes and processes the stack top node while method 2 pushed one adjacent node, processes it, pushes its adjacent node. This results in different processing sequence, as can be seen below:

So which one is correct/preferable ?

# Answer
> 1 votes
Every DFS algorithm should also construct a *DFS tree* (or, in general, forest), which records how the search progresses. For the CLRS algorithm, the adjacent node in step 3 is made the child of the node in step 2. For the other algorithm you have to be more careful (I'll let you figure out the correct way). If the DFS tree is constructed properly, then it will satisfy the following property:

> If $(x,y)$ is an edge not belonging to the tree, then either $x$ is an ancestor of $y$ or $y$ is an ancestor of $x$.

This is the property of DFS used in actual algorithms. The actual sequence in which the nodes are traversed could also be important, but this is less common.

Corneil and Krueger suggest a generic "non-deterministic" version of DFS, and give a characterization in terms of the resulting DFS traversal order. They also suggest a canonical way of forming the DFS tree given the DFS order – each node is the child of its earliest neighbor, and show that the resulting DFS tree always satisfies the crucial property stated above.

If Method 1 satisfies the criterion of Corneil and Krueger, then it is worthy of the name DFS. If you are curious, you can read the paper and check whether the criterion listed there holds for that algorithm. Even if it doesn't, you can check whether there is a simple way to construct a DFS tree (not necessarily using the construction suggested by Corneil and Krueger) that satisfies the property above – that suffices in most cases.

You can use any algorithm which satisfies your needs (in some cases, you don't care about *any* property, only about traversing the entire connected component). A "correct" form of DFS, together with a method of constructing the DFS tree, should satisfy the DFS tree property, and preferably also the ordering characterization of Corneil and Krueger. Which one is preferable depends on many factors – usually the one using the least resources (time and memory).

---
Tags: algorithms, graphs, data-structures, graph-traversal
---


# Question
Title: What if p and q are not distinct in RSA Crypto System? What could go wrong?
In RSA Crypto System we choose p and q such that they are distinct primes. Calculate n=pq and phi=(p-1)(q-1). Then e is chosen for public key (n,e) s.t. gcd(e,phi)=1

# Answer
> 13 votes
The security of RSA relies on the fact that the best known way to compute $\phi(n)$ is to prime factorize $n$. For $n=pq$, where $p$ and $q$ are large, distinct primes, this is very hard. If instead $n=p^2$, then one could quickly find $p$ by calculating a square root. Then one could calculate $\phi(p^2)=p^2-p$ and break the encryption completely.

# Answer
> 11 votes
In addition to SBareS's answer, let me mention that the formula $\varphi(pq) = (p-1)(q-1)$ only works if $p \neq q$: $\varphi(p^2) = p(p-1)$. Therefore if $p = q$ then decryption wouldn't be the inverse of encryption (unless you use the correct formula for $\varphi(n)$.

---
Tags: algorithms, cryptography, encryption
---


title: Is Ω(f+g) = Ω(min(f,g))?

text:
# Question
Title: Is Ω(f+g) = Ω(min(f,g))?
We know that $O(f(n)+g(n))=O(max(f(n),g(n)))$.

So can we say that $\Omega(f(n)+g(n)) = \Omega(min(f(n),g(n))$?
Then what is $\Theta(f(n)+g(n))$ equal to?

# Answer
Assuming $f,g \> 0$, we have $$\max(f(x),g(x)) \< f(x) + g(x) \leq 2\max(f(x),g(x)).$$ Therefore $\Theta(f(x) + g(x)) = \Theta(\max(f(x),g(x)))$, in the sense that both sets of functions are equal.

Still assuming that $f,g \> 0$, it is also true that $\Omega(f(x)+g(x)) = \Omega(\min(f(x),g(x)))$, in the sense that if $h(x) \in \Omega(f(x)+g(x))$ then also $h(x) \in \Omega(\min(f(x),g(x))$. The stronger bound $\Omega(f(x)+g(x)) = \Omega(\max(f(x),g(x)))$ also holds.

I have mentioned two interpretations of equality. In fact the second one (which really corresponds to $\subseteq$ in this case) is actually the standard one – equality is not symmetric! However, in the case of big $\Theta$ both notions fortunately coincide.
> 9 votes

# Answer
"So can we say that $\Omega(f(n)+g(n)) = \Omega(\min(f(n),g(n))$?"

No. (Consider 1 and n.)

"Then what is $\Theta(f(n)+g(n))$ equal to?"

If $f$ and $g$ can have opposite signs then $O(\max(f(n),g(n)))$, else $\Theta(\max(f(n),g(n)))$.
> 2 votes

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


# Question
Title: Mathematical optimization with thresholded optimization function
Gradient descent can be used to minimize an objective function $\Phi:\mathbb{R}^d \to \mathbb{R}$, if we know how to evaluate $\Phi$ on any input of our choice.

However, my situation is a little different. I have an objective function $\Phi$ of the form

$$\Phi(x) = \Phi\_1(x) + \Phi\_2(x),$$

where I can evaluate $\Phi\_1$ on any input of my choice, but I don't have the ability to do that for $\Phi\_2$. Instead, for $\Phi\_2$, I have only a thresholded (quantized) version of $\Phi\_2$: I can evaluate $f\_2:\mathbb{R}^d \to \\{0,1\\}$ on any input of my choice, where $f\_2$ is defined by

$$f\_2(x) = \begin{cases} 0 &\text{if } \Phi\_2(x)\le t\\ 1 &\text{if } \Phi\_2(x) \> t\\ \end{cases}$$

and $t$ is fixed. You can assume that $\Phi\_2$ is smooth and has all the nice properties you might like, but I can only evaluate $f\_2$, not $\Phi\_2$. How can I search for an $x$ that's likely to make $\Phi(x)$ as small as possible, in this situation? Is there any way to adapt gradient descent or other mathematical optimization method to this setting?

---

Why I think there might be some hope: if we find $x',\delta \in \mathbb{R}^d$ such that $f(x')=0$ and $f(x'+\delta)=1$, where $x' \approx x$ and $\delta \approx 0$, then we've learned some information about $\Phi\_2$, e.g., that the partial derivative of $\Phi\_2$ is likely to be large in the $\delta$ direction. It seems like it might be possible to build an algorithm to exploit this kind of information. Are there any techniques to handle this kind of situation?

# Answer
I guess $f\_2(x)$ is some sort of oracle that tells you if $\Phi\_2(x)$ is greater than $t$? If the set $\\{\mathbf{x} : \Phi\_2(x) \le t\\}$ is convex, then I think projected gradient algorithm might be helpful. Could you provide more information on $\Phi\_2(x)$? The question is kinda confusing with the information provided.
> 2 votes

---
Tags: algorithms, optimization, numerical-algorithms, gradient-descent
---


# Question
Title: How can I calculate optimal batch sizes for calls to an external server?
So I have a large number of commands, say 500,000, that I want to send and run on a server somewhere else, and get the answers back. All of these commands together takes a long time to execute - roughly 30 seconds. I could group all those commands together and send them off, have the server execute them all, and then get my results. But that's significantly slower than grouping those commands into *batches*, which I send off all at the same time, and can then execute on that server in parallel.

However, I can't make the batches too small, because I'm doing this from a browser, and most modern browsers can only keep ~6 concurrent open connections with the same server. So you get a trade off - for large batch sizes, I'm not sending enough concurrent commands to the server. For small batch sizes, I'm sending so many that the browser gets backed up.

I've tried this experimentally, and I wind up with data that looks something like this (pardon the terrible drawing):

On the x axis is the number of batches I use, and on the y axis is the time the whole resulting calculation takes. I haven't succeeded in finding a model that really works for this data, only a basic crude approximation.

All I really want to know is, is there research on this kind of thing I can look up? Some way that, given code execution times on the server, and delay times for getting there, I can calculate the optimal batch size? I can't be the only person who's wanted to solve this problem. If there isn't, then what do you think?

# Answer
Here's the simplest model I can think of. Assume that each command takes $\beta$ seconds to complete, and it takes $\alpha$ seconds to create a connection. Then I would expect that it would take $\alpha+\beta k$ seconds to complete a batch of size $k$. If there are $N$ commands in total, then we'll need $N/k$ batches. With 6 concurrent TCP connections to the server at a time, this means it'll take $N/(6k) \times (\alpha + \beta k)$ seconds to complete all of the batches. As a function of the batch size, this is

$$f(k) = {\alpha + \beta k \over 6k} N.$$

You can find the optimal batch size by finding $k$ that minimizes $f(k)$, which can in turn be done using calculus by taking the derivative and setting it to zero: $f'(k)=0$. Note that

$$f'(k) = {6\beta k - 6(\alpha + \beta k) \over 36k^2} N = {\alpha \over 6k^2} N.$$

Setting this to zero, we find that $f(k)$ is minimized by taking $k$ as large as possible; in the limit we have $\lim\_{k \to \infty} f(k) = \beta/6 N$.

Obviously, this is not what you observe empirically, which suggests that this model is not accurate. I suggest as a next step you start to brainstorm why the model might be inaccurate or what factors it might be overlooking. You might also want to measure and plot some additional metrics, e.g., the average time it takes for each batch to complete (as a function of batch size, i.e., the time between starting execution of command 0 from batch $i$ to starting execution of command 0 from batch $i+1$).
> 1 votes

---
Tags: algorithm-analysis, reference-request, optimization, computer-networks
---


title: Algorithms for logical synthesis

text:
# Question
Title: Algorithms for logical synthesis
Let's say that I want to map some string of binary digits to a single binary digit of output, like the below:

$ \begin{array}{l|l} \text{Input}&\text{Output}\\ \hline 0001&0\\ 0011&1\\ 0111&0\\ 1111&1 \end{array} $

If inputs besides those listed are given, I don't care what the output is. I only care about the inputs listed.

I can eyeball the truth table and come up with the below:

$Output = \lnot (Input\_0 \oplus Input\_1 \oplus Input\_2 \oplus Input\_3)$

However, that isn't the only solution, and might not be the solution using the fewest number of operations.

Are there any algorithms to figure this out for arbitrary length inputs mapping to a single binary digit of output?

Ultimately I'm trying to solve for mapping $M$ bits of input to $N$ bits of output. I figure an ok way to do this might be to break it into $N$ problems of mapping $M$ bits of input to a single bit of output so am starting with that.

I'm actually going to be implementing something using a standard modern computer (aka desktop CPU), so I know that there is some extra complexity if I want better efficiency, due to the fact that operations happen not on single binary digits, but on eg. words. Not only will efficiency depend on minimizing the number of operations done on each bit, there will also be efficiency to be gained by letting "bit programs" share operations where they can, if that makes sense.

One step at a time, but I bring this up in case there is an answer which encompasses my future needs as well.

Edit: I've found these pages which talk about minterms and karnaugh maps and understand what they are talking about, however I also know that they aren't guaranteed to be the minimal circuit, and they also mention that some other algorithms are used in more complex circuit design (but they don't say what they are)
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic2.html
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html

# Answer
This is an instance of logic synthesis. A standard approach is to use Karnaugh maps or the Quine-McCluskey algorithm. Finding the minimal circuit is hard (see circuit minimization), but there are tools and techniques that often work reasonably well in practice. For instance, you can use the Espresso tool to help with this; there are other tools for this task as well.

See also Creating a logical circuit and Working out the connectives (And, Or, Not) in a Truth Table that has the outputs.
> 3 votes

---
Tags: algorithms, logic, circuits
---


# Question
Title: Is the following intuition valid for understanding $k$-wise independent hash functions?
I really enjoy reading up on algorithms and data structures and in the course of doing so often come across ones that rely on $k$-wise independent families of hash functions. I'm perfectly comfortable working with these families of hash functions as black boxes (that is, I understand the relevant definitions and how the algorithms and data structures rely on those definitions), but when I look at specific examples of families of $k$-wise independent families of hash functions, I often have a really hard time understanding why they work. I assume that a lot of this is due to the fact that I don't have a super solid grasp of number theory or finite fields.

One trend I've noticed is that to form a $k$-wise independent family of hash functions whose domain and codomain is a set $\\{0, 1, 2, 3, \dots, p-1 \\}$, where $p$ is a prime, you can choose a random $(k+1)$-degree polynomial by choosing $k+1$ random elements out of $\\{0, 1, 2, \dots, p-1\\}$, then to have the hash function be "evaluate the polynomial on the given input value." (I assume that this is equivalent to choosing a random $(k+1)$-degree polynomial over $\mathbb{F}\_p$, though I may be mistaken about this.)

My intuition behind why this approach works is that, just like a degree-$(k+1)$ polynomial over the reals cannot be determined by $k$ or fewer points, a degree-$(k+1)$ polynomial over $\mathbb{F}\_p$ cannot be determined by $k$ or fewer points. As a result, these polynomials work well as hash functions because, with random coefficients, if you see $k-1$ outputs of the hash function, it's impossible to predict any $k$th output of the hash function better than a random guess because you can't determine what the polynomial is.

My questions are the following:

1. Is this a correct intuition for why these families of hash functions work correctly?
2. I teach undergraduate courses on algorithms and data structures that do not have number theory or abstract algebra as prerequisites. If this intuition is correct, would it be inappropriate / misleading to use this intuition to explain these families of hash functions?

Thanks!

# Answer
> 6 votes
Your intuition is exactly right. Yes, that's equivalent to choosing a random polynomial over $\mathbb{F}\_p$. The reason why it works is exactly the interpolation theorem for finite fields.

$k$-wise independent basically means "it behaves like a perfect hash function, if you only feed it $k$ inputs" or "it behaves like a perfect hash function, as far as correlations between up to $k$ different hash values appear"; and the interpolation theorem then ensures that this level of perfection is achieved for the construction you outline.

It can be a bit tricky to explain this intuition to students who aren't familiar with anything from number theory, group theory, or finite fields. One approach is to explain the intuition of the interpolation theorem over the real numbers, and then just give a statement that "something similar happens when you work modulo $p$ a prime", without trying to prove it. That's not perfect, though.

Another approach is to not try to teach this topic, at this point in their education. While I was taught universal hashing in my undergraduate algorithms course, I've gradually come to the opinion that the topic is better to omit from the course: it's not important enough, and it relies too much on mathematical background and intuition that students don't have. Why isn't it important? Well, most students won't become theorists. For students who will eventually become practitioners, they probably won't ever need universal hash functions. Instead, ordinary hash functions are often so good that as a first approximation you can just model them as if they were universal (as a heuristic), without making a big deal about it, and do your probability calculations from there. This is enough to let you analyze uses of hash functions in a way that's accurate enough for practical/engineering purposes. And, given that, it's not clear that we need to show them constructions that provably achieve something that ordinary hash functions already heuristically achieve pretty well. That's just a personal opinion, though.

# Answer
> 1 votes
You can explicitly teach this for small $k$. For example, when $k=1$ you can take the random hash function $h(x) = c\_0$, where $c\_0 \in \mathbb{Z}\_p$ is chosen randomly; for each individual $x$, this is uniformly random.

When $k = 2$, you take the random hash function $h(x) = c\_0 + c\_1 x$, where $c\_0,c\_1 \in \mathbb{Z}\_p$. To show that this is uniformly random, we show that for any inputs $x \neq y \in \mathbb{Z}\_p$ and outputs $a,b \in \mathbb{Z}\_p$ there is a *unique* choice of $c\_0,c\_1$ such that $h(x) = a$ and $h(y) = b$. Indeed, if $c\_0 + c\_1 x = a$ and $c\_0 + c\_1 y = b$ then $c\_1(x-y)=a-b$ and so $c\_1 = \frac{a-b}{x-y}$, and then $c\_0 = a - c\_1x$.

The general case is very similar, and uses the fact that Vandermonde matrices are invertible – but this may be too advanced for your students (perhaps you could work out the case $k = 2$). Note that to get $k$-wise independence you only need polynomials of degree $k-1$.

---
Tags: hash, number-theory, intuition
---


# Question
Title: counterexample for this graph isomorphism algorithm
I'm trying to learn about graph isomorphism and I stumbled upon coloring. When given 2 graphs, you give each vertex a color according to properties of their neighbors and any vertex on graph 1 can only map to any vertex on graph 2 with the same color. This way you cannot have false negatives (if the algorithm says there's no mapping, it is so) but you may have false positives. So now I'm looking for a false positive of my particular graph isomorphism coloring algorithm.

We're going to assign each vertex a "breadth" and a "color", which are both strings. Assume both graphs have n vertices.

```
Step 1: we assign depth=0. We pick a starting vertex and assign it
(breadth, color) = ("0;","0;").
We assign a set S={that vertex}.

    Step 2: depth++;
    set T=[all neighbors that don't have a color yet of all vertices in S].

        Step 2.A: for each vertex in T, name it t and set t.breadth = depth + ";"

        Step 2.B: for each t in T:
        t.breadth += '[' + (concatenate all colors of all
        neighbours of t that are in S, in lexicographically sorted order) + '];'

        Step 2.C: for each t in T:
        t.color = t.breadth + '{'+(all breadths of all neighbours
        of t that are in T, concatenated in lexicographically sorted order)+'}'

    Step 2.D: S=T; goto step 2 unless T is empty.

Step 3: Save the resulting coloring, clear S and T and the coloring and
repeat from step 1 for *each possible starting vertex for both graphs*.

Step 4: We now have n colorings for both graphs. Deduce if this leads to a
negative. If not, for now assume that the graphs are isomorphic.

```

A bit of explanation on step 4: Suppose I pick a starting vertex for graph 1, we need to look at each starting vertex for graph 2. If a starting vertex for graph 2 then leads the exact same number of colors for each color of graph 1, we have possible vertex mappings from graph 1 to graph 2. If this is also the case for another starting vertex of graph 2, we have extra mapping possibilities. with 1 starting vertex for graph 1, we look at all starting vertices from graph 2 and *union* the results together.

When looking at another starting vertex for graph 1, we get another set of mappings. Each starting vertex of graph 1 leads to a set of mappings, and we're looking at the *interesection* of those sets. If that intersection is empty, the graphs are not isomorphic.

Now, I'm looking for two graphs for which this algorithm says they're isomorphic, while they're not.

I'm assuming that the graphs are connected.

Note that the colors might grow exponentially large this way, but we can avoid that by replacing parts with placeholders.

# Answer
> 7 votes
I've not looked closely at your algorithm so I'm not sure exactly what it does. However, it sounds quite a lot like colour refinement (also known as the 1-dimensional Weisfeiler-Lehman method). I suggest you look at the following paper, which will both explain that method and show a class of graphs whose isomorphism problem it cannot solve, even though graph isomorphism on those specific graphs is in **P**. Even if your algorithm turns out to be different from colour refinement, a similar construction might give some graphs it doesn't work on.

* J.-Y. Cai, M. Fürer and N. Immerman, *An Optimal Lower Bound on the Number of Variables for Graph Identification*. *Combinatorica*, 12(4):389–410, 1992. (Free PDF)

By the way, one thing you can (probably) do to avoid the labels your algorithm assigns from becoming exponentially long is to just replace them with 1, 2, ... at each round. You (probably) don't need to know exactly *what* label each vertex has; rather, you (probably) just need to know whether two vertices have the same label or not.

# Answer
> 3 votes
Although the question is somewhat different, the following answer by Yuval Filmus also answers my question:

> There are two non-isomorphic graphs with 16 vertices in which each vertex has 6 neighbors and 9 vertices at distance 2: the Shrikhande graph and the $4\times 4$ rook's graph.

---
Tags: graphs, graph-isomorphism
---


# Question
Title: Best random permutation employing only one random number
The ideal random permutation algorithm of Fisher and Yates (Algorithm P in Knuth vol.2) for a sequence of $n$ objects requires $n-1$ random numbers.

In some card games one first does a "cut" and then a riffle shuffle. The cutting point is a random value, the subsequent shuffling could be considered as deterministic. That is, only one random number is being used to generate the permutation, which understandably can't be ideal. On the other hand, theoretical perfection isn't always necessary in practice. I like hence to know whether, if one keeps the constraint of using one random number in a run, the quality of randomness of the permutation obtained couldn't eventually be improved through certain appropriate modifications of the procedure commonly employed in card games, if one is willing to take the trade-off of more work/time, inconvenience, etc. Such trade-offs may not be acceptable for real games, but I suppose there may be other practical applications that could advantageously exploit the same idea, thus without being required to acquire, e.g. via a chosen PRNG, the larger number of random numbers needed for executing the algorithm of Fisher and Yates.

# Answer
> 8 votes
Regardless of the algorithm you use, if you have $i$ bits of random data, you can generate a maximum of $2^i$ possible permutations. If $i$ is smaller than $log\_2(n!)$, then there will be some permutations which cannot be produced, and you will have, in effect, decided which permutations those are when you encode your algorithm. (You may not be able to predict which permutations they are, but you have nonetheless determined that fact.) \[1\]

$log\_2{52!}$ is about 225.6, so with a single 64-bit random number, you can only generate one out of every 4372488437452686306097090522819848184377442426979 permutations. With four 64-bit random numbers, you'd have no trouble generating all of them. $log\_2{64!}$ is just under 296, so it would require five 64-bit numbers.

Since your permutation-generator is deterministic, you cannot invent more possibilities by manipulating the algorithm. The best you can do is to ensure that it is a homomorphism; that every random number is mapped onto a different permutation. Beyond that, you could investigate whether the one-in-4372488437452686306097090522819848184377442426979 sample of the universe of permutations exhibits any biases. For example, is each individual permutation position in the same evenly distributed? Is there a correlation between two (or more) positions? I sincerely doubt that trying to emulate a physical shuffle will improve these statistics more than the simple mathematical approach outlined below.

As xkcd reminds us, there is no such thing as an intrinsically random value. The only meaningful question we can answer is whether a sequence of pseudorandomly generated values is "random-like".

So let's first figure out how to transform the $i$ bits of randomness into $2^i$ *distinct* permutations. The following generic procedure should work:

1. Predefine some function $f$ which maps $\[0, 2^i)$ onto $\[0, n!)$.
2. For each permutation, given a random number $x$, compute ${q\_0,...,q\_{n-1}}$ and ${r\_0,...,r\_{n-1}}$ as follows:

* $q\_0 = f(x)$
    * $r\_i = q\_i \mod (n-i)$
    * $q\_{i+1} = {{q\_i - r\_i}\over{n - i}}$
3. Perform a Fisher-Yates shuffle using ${r\_0,...,r\_{n-1}}$ as the "random numbers".

(Aside from expanding the initial seed into the range $\[0,n!)$, this is precisely the solution proposed by Yuval, just written out in more detail.)

Then you could start to measure the "randomness" of a proposed function $f$ by measuring the distribution of the values of each $r\_i$ over the range of $f$. The next step might be to look at the distribution of $\<r\_i, r\_j\>$ for each pair $0 \<= i \< j \< n$

One really simple definition of $f$ is:

$$f(x)=\lfloor x * {n!\over2^i} \rfloor$$

Assuming you calculate this with precise rational arithmetic, this gives a surprisingly reasonable set of individual $r\_i$ distributions for a 52-shuffle given a 64-bit random number. \[2\] You'll have to decide whether that's good enough for you. If it turns out to not be, there are other possible transformations which might do better. Another simple one would be replacing the above with:

$$f(x)=\lfloor x * {n!\over2^i} \rfloor + p \mod n!$$

where $p$ is some large prime.

---

\[1\] This information-theoretic argument is based on the permutation-generation algorithm being stateless. If each random number is in some way combined with all previously generated random numbers without losing (too much) information, then the universe of possible permutations could be much larger. (This condition is not satisfied by simply combining the two random numbers with some arithmetic or bitwise operation whose value has the same number of bits as each of the arguments.) I think that's a reasonable assumption because the original question was cast in the context of a client-server architecture; in such systems maintaining co-ordinated state between the disconnect components is generally more complicated than exchanging a few more bits in each transaction.

\[2\] I didn't do much more than look at some histograms and a couple of correlations and a chi-square or two, but it was all really simple python, so I'm sure you could reproduce my limited research in a few minutes.

# Answer
> 4 votes
If you can get a random number in the range $\\{0,\ldots,n!-1\\}$, you can generate a permutation on $n$ elements using the Fisher-Yates algorithm. The idea is to think of this number as encoding the numbers used in the Fisher-Yates algorithm, using "mixed-base" notation.

# Answer
> 2 votes
There is a method by Ivan Stojmenovic, which uses only a single (pseudo-)random number in $\[0,1\]$ to uniformly (unbiasedly) generate any random permutation needed.

> **1.13 UNRANKING WITHOUT LARGE INTEGERS**
>
> Following the work by Stojmenovic 38, "ON RANDOM AND ADAPTIVE PARALLEL GENERATION OF COMBINATORIAL OBJECTS", this section describes functions mapping the interval \[0...1) into the set of combinatorial objects of certain kind, for example, permutations, combinations, binary and t-ary trees, subsets, variations, combinations with repetitions, permutations of combinations, and compositions of integers. These mappings can be used for generating these objects at random, with equal probability of each object to be chosen. The novelty of the technique is that it avoids the use of very large integers and applies the random number generator only once. The advantage of the method is that it can be applied for both random object generation and dividing all objects into desirable sized groups.

The method works similarly to picking a random index from $\[0,n!-1\]$ and unranking the corresponding permutation (or other combinatorial object of interest), but with a twist. With appropriate manipulation of combinatorial relations one can use simply a random number (essentialy a probability that a specific permutation has been selected, uniformly) and do all computations using float-point arithmetic **without ever using big integer arithmetic**. This also leads to using one single random number, so it leads to a kind of *fisher-yates-knuth shuffle algorithm with minimum number of PRNGs used*, one.

generate random permutation algorithm (from above reference)

*($n$ is the size of the permutation and $g$ is the random number in $\[0,1\]$)*

The drawbacks of this approach are related to floating-point calculations and their accuracy, although the performance cited is decent and in accord with other approaches (that have similar issues, e.g using multiple PRNG's which after a while do not meet uniformity criteria depending on number of items $n$ in permutation, and so on..).

> \[..\]The method gives theoretically correct result. However, in practice the random number $g$ and intermediate values of $p$ are all truncated. This may result in computational imprecision for larger values of $m$ or $n$. The instance of a combinatorial object obtained by a computer implementation of above procedure may differ from the theoretically expected one. However, the same problem is present with other known methods (as noted in the previous section) and thus this method is comparable with others in that sense. Next, in applications, randomness is practically preserved despite computational errors.

(ps similar fast and efficient methods are extensively researched and used for my custom combinatorial library for node/JS Abacus, in progress)

---
Tags: randomness, sampling, permutations
---


# Question
Title: How many operations to produce this superposition of 3 qubits?
Suppose I have three qubits that of course represent $2^3=8$ states. I want to put these qubits so that they are in the particular superposition say...

$$a|000\rangle + b|001\rangle + c|010\rangle + d|011\rangle + e|100\rangle + f|101\rangle + g|110\rangle + h|111\rangle\\,.$$

Here's the question: do I perform a 2d rotation on each qubit (each having its own $2\times2$ rotation matrix) for a total of three operations, or do I perform a single 8d rotation using an $8\times8$ rotation matrix?

Follow up question: if the answer is 'make an $8\times8$ matrix', doesn't this at some point boil down to just applying a rotation to each qubit?

# Answer
You don't need a full 8x8 three-qubit operation, but you will need a two-qubit operation of some kind. If you only rotate each qubit independently, you'll find you can only make un-entangled states like:

$(a\_1 \left| 0 \right\rangle + b\_1 \left| 1 \right\rangle) \otimes (a\_2 \left| 0 \right\rangle + b\_2 \left| 1 \right\rangle) \otimes (a\_3 \left| 0 \right\rangle + b\_3 \left| 1 \right\rangle)$

$= a\_1 a\_2 a\_3 |000\rangle + a\_1 a\_2 b\_3 |001\rangle + a\_1 b\_2 a\_3 |010\rangle + a\_1 b\_2 b\_3 |011\rangle + b\_1 a\_2 a\_3 |100\rangle + b\_1 a\_2 b\_3 |101\rangle + b\_1 b\_2 a\_3 |110\rangle + b\_1 b\_2 b\_3 |111\rangle$

But as soon as you have a non-trivial two-qubit operation, like a controlled-NOT, to go with your single qubit gates, you can approximate any larger operation or state arbitrarily well. (This is different from classical reversible computing, where you need a doubly-controlled-not before you get universality.)

The basic idea of how it's done is:

* Break a large operation into lots of single-qubit operations, but allowing each to have lots of controls.
* Use the fact that all single-qubit operations have a square root to knock controls off of multi-controlled operations until you're left with singly-controlled operations.
* Replace controlled-whatevers with controlled-NOTs by finding $A$, $B$, $C$, $\theta$ such that $ABC = I$ but $AXBXC e^{i \theta} = U$ for each single-qubit operation $U$.

The details of these kinds of constructions are covered in textbooks.
> 2 votes

---
Tags: quantum-computing
---


# Question
Title: Algorithm to find a minimal regular language containing given context-free language
I am not sure that the problem is in general solvable, but here's an example of what I mean:

1. Any context-free language has a trivial regular language that contains it: $\Sigma^\*$.
2. The language $L\_1=\\{a^nb^n\\;|\\;n\geq 0\\}$ is contained in $L\_2=\\{a^nb^m\\;|\\;n,m\geq 0\\}$, which is obviously a subset of $\Sigma^\*$.

# Questions

1. Is there a way to prove $L\_2$ is the "smallest"\* language which contains $L\_1$?
2. Is there an algorithm for finding such language pairs given the context-free one?

---

* "smallest" means that there is no other language which also satisfies the requirement and is its proper subset.

# PS

Sorry, I now realized that I cannot actually find the minimal language with the requirement given above, for example: $L\_3=\\{ab, aabb\\} \cup \\{a^nb^m\\;|\\; n,m \geq 2\\}$ would be smaller than $L\_2$, and one could continue constructing languages like that ad infinitum. So, maybe an alternative definition for "smaller" could be "having least states"?

I'm sorry for indecisiveness. Please feel free to put this on hold until I figure out the good requirement. Or suggest one yourself, if you feel like there may be an interesting one.

# Answer
There is no "smallest" regular language containing any non-regular langauge.

First, note that every finite language is regular, so any non-regular language $L$ must be infinite. Consider some regular language $R\supset L$. $R\setminus L$ must also be infinite since, if it were finite, then $L = R\setminus (R\setminus L)$ would be regular, because regular languages are closed under difference. So, in particular, we can take any finite $S\subset R\setminus L$ and the langauge $R\setminus S$ is regular, is a strict subset of $R$ and a strict superset of $L$.

In other words, whenever you have a non-regular $L$ and a regular $R$ such that $L\subset R$, there is another regular $R'$ such that $L\subset R'\subset R$ (and, in fact, infinitely many of them).
> 3 votes

---
Tags: regular-languages, context-free
---


# Question
Title: Partition a bipartite graph to a complete matching and an independent set
I am looking for a reference for the following theorem:

Let $G$ be a bipartite graph with partitions $X$ and $Y$, each with the same number of vertices ($n$).

There is a nonempty subset $Y\_1 \subseteq Y$, and a partition of $X$ to disjoint subsets $X\_1$ and $X\_2$, such that:

* There is a complete matching between $X\_1$ and a subset of $Y\_1$;
* There are no edges between $X\_2$ and $Y\_1$.

Intuitively, $X$ can be seen as a set of men and $Y$ can be seen as a set of women. An edge between $x \in X$ and $y \in Y$ means that "$x$ and $y$ like each other" ("like" is considered a symmetric relation).

The goal is to find a subset of the women ($Y\_1$) and a subset of the men ($X\_1$), such that each man can marry a woman he likes without upsetting any of the other men ($X\_2$), because no unmarried man likes any married woman.

This sounds similar to Hall's marriage theorem, but the premise is simpler. And, I am mainly looking for a reference that I can cite.

Some special cases:

* If the graph is full (i.e. any man likes any woman), then we can take $Y\_1=Y$, $X\_1=X$, $X\_2=\phi$.
* If the graph is empty (i.e. no man likes no woman), then we can take $Y\_1=Y$, $X\_1=\phi$, $X\_2=X$.
* If there is $y \in Y$ with no neighbours (i.e. a woman that doesn't like any man), then we can take $Y\_1={y}$, $X\_1=\phi$, $X\_2=X$.
* If there is $y \in Y$ with a single neighbour $x \in X$ (i.e. a woman that likes a single man), then we can take $Y\_1={y}$, $X\_1={x}$, $X\_2=X-{x}$.

The question becomes more problematic when all $y \in Y$ have at least two neighbours.

# Answer
This question was subsequently posted on Math.SE. It received a complete answer by Zur Luria which I am quoting here.

> I think I can prove your conjecture using Hall's theorem.
>
> First of all, any perfect matching is also an envy-free matching, so if $G$ satisfies Hall's condition then there is an envy-free matching.
>
> Otherwise let $S \subseteq X$ be a maximal subset such that $|N(S)|\<|S|$. If $S=X$ then any $y$ that isn't in $N(S)$ isn't wanted by any $x$. If $|S|\<n$ then the subgraph of $G$ on the vertices$X\smallsetminus S,Y \smallsetminus N(S)$ satisfies Hall's condition (otherwise we can make $S$ larger), and so it has a matching that matches all of the vertices in $X\smallsetminus S$. This matching is envy-free.

I also co-authored a paper on this problem, some related generalizations and optimization problems, and some applications to fair division.
> 2 votes

---
Tags: graphs, reference-request
---


# Question
Title: 1-to-1 cryptographically secure bit shuffling
Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes). The function should have the following qualities:

* It should be 1-to-1 so that all inputs map to some output and so that no two inputs map to the same output.
* Given an output element it should be difficult to guess the input that lead to that output, even when the mapping is completely known.

Does such a function exist? Where can I learn more?

# Answer
> 10 votes
This is known as a *one-way permutation*. The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements. There are various candidate constructions for one-way permutations, e.g., based on raising to the third power modulo an RSA modulus or other schemes.

# Answer
> -1 votes
You may want to have a look on DES or AES, they are doing exactly what you want. these to methods depending on having a key that encrypt/decrepit the plain text. another method the use dual keys (public&private keys) this is a very commonly used method nowadays and the most popular one is RSA, it is mainly deepening on having a public key the is known to every one and a privet key it is just you who should know it. and if you some one want to send you something he will encrypt it with your public key (notice that he cannot decrepit it anymore as it is only decrepited by your private key). and if you want to make authentication you can send something encrypted by your private key and the receiver will decrepit it by your public key that way he will be sure that it is sent by you.

more information could be found here:

https://en.wikipedia.org/wiki/RSA\_(cryptosystem)

# Answer
> -2 votes
You could try this:

First, take the SHA-256 or other hash of your input value. Then use a basic cypher, something like the classic A=C, B=D, C=E...

The difference is that you use the SHA-256 of the entire input string to determine how much it is shifted by(is it A=B, A=C, A=D, etc.)

Note: I am not a cryptography expert and am not sure how secure this would be.

---
Tags: discrete-mathematics, cryptography, hash
---


# Question
Title: Prim's algorithm: difference between brute force and PQ approaches
I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues.

Given a graph $G=(V,E)$, the former can be stated as in Dasgupta et al.:

```
X = {}
while(|X| < |V-1|)
  pick a subset S of V for which X has no edges between S and V-S
  let 'e' be the minimum weight edge in E between S and V-S
  X = X union {e}

```

It uses blue rule and builds the tree edge by edge: at the end you have the MST of the whole graph, until then $X$ is just incomplete. If we use a brute force approach, running time is $O(|V|\cdot |E|)$.

As we know, better running time is obtained mantaining a priority queue that we use to find the cheaper edge incident to the tree that we build on a step by step basis. Anyway i think that this more than just optimization, since solution with this last approach is built incrementally.

Infact, if with brute force you have a tree built edge by edge considering from the beginning the whole graph, with priority queues you instead discover nodes incrementally: at each step you have a valid MST of a subproblem. As long as the algorithm proceeds, every node is discovered and priority queue becomes empty. At this point the MST has grown to be the solution of the whole graph. I can summarize with the following simple example:

You start from node $A$, and edges to $B$ and $C$ are immediately discovered. They become part of the tree. Anyway tree changes as long as new nodes are discovered (see UPDATE label in the picture). With brute force you don't have anything similar.

Please, let me know if i'm mistaken or if my reasoning is not complete.

# Answer
First, the psuedo-code given is *not* intended for brute force Prim's algorithm. It is a ***meta***-algorithm for MST. Quoted from the beginning of Section 5.1.5 of "Algorithms":

> What the cut property tells us in most general terms is that any algorithm conforming to the following greedy schema is guaranteed to work.

Both Kruskal's algorithm based on disjoint sets and Prim's algorithm based on priority queues are instances of the meta-algorithm.

---

As for your other questions:

> "If we use a brute force approach, running time is O(|V|⋅|E|)."

It does not make much sense to discuss about the time complexity of a meta-algorithm.

> "Anyway I think that this more than just optimization, since solution with this last approach is built incrementally."

The greedy meta-algorithm for MST is incremental. And both Kruskal's algorithm and Prim's algorithm are incremental.
> 1 votes

---
Tags: graphs, greedy-algorithms, check-my-answer, minimum-spanning-tree
---


# Question
Title: What is the trick used in skip lists to minimize $k + \frac{n}{k}$?
I was reviewing skip lists and the first step is to have two lists, the bottom one ($L\_0$) of length n and the top one ($L\_1$) of size k.

Usually one traverses the "express line" (i.e. the top lane with least elements) first until you need to use lower lanes. This leads in the simple case of 2 linked-lists to a run time of:

$$ L\_1 + \frac{L\_0}{L\_1} = k + \frac{n}{k}$$

in computer science courses it is common to optimize this equation **without using calculus**. The equation that it leads to solve is:

$$ k = \frac{n}{k} \implies k = \sqrt{n}$$

I was wondering if anyone remembered the alternative argument for optimizing the above equation?

If I recall correctly, it goes something like this:

we wish to choose a length of $L\_1$ (i.e. k) that is as small as possible. But we also don't want it to be too small or $\frac{1}{k}$ will grow too much. So since the expression is sort of an "average" we just intuitively guess that its minimized that the "average" value. i.e. when $k = \frac{n}{k}$. I am not sure if this is completely correct or explained well but if someone remembers how to minimize this without using calc (as its usually taught in CS courses it would awesome!)

# Answer
The method you mention is based on the following theorem:

> If $f \geq 0$ is non-decreasing, $g \geq 0$ is non-increasing, and $f(t) = g(t) = y$, then $$ y \leq \min\_x \[f(x) + g(x)\] \leq 2y. $$

Note that there is (at most) a unique point $t$ such that $f(t) = g(t)$.

In your case, $f(k) = k$ is increasing and $g(k) = n/k$ is decreasing, and $f(\sqrt{n}) = g(\sqrt{n}) = \sqrt{n}$, so $\sqrt{n} \leq \min\_k \[k + n/k\] \leq 2\sqrt{n}$. In fact, calculus shows that the minimum is indeed $2\sqrt{n}$.

The proof of the theorem is very simple: if $x \geq t$ then $f(x) + g(x) \geq f(t) = y$, whereas if $x \leq t$ then $f(x) + g(x) \geq g(t) = y$.
> 2 votes

# Answer
To make it more clear what is the constant and what is the variable I will use $x$ for the variable name instead of $k$ in the following. We will assume that $x\>0$ and $n\gt 0$ and that the root $\sqrt{t}$ is the positive root of the positive number $t$.

We have $$x+\frac{n}{x}=\left(\sqrt{x}-\frac{\sqrt{n}}{\sqrt{x}}\right)^2+2\sqrt{n}$$ But $$\left(\sqrt{x}-\frac{\sqrt{n}}{\sqrt{x}}\right)^2 \ge 0$$ And its minimum 0 will be at $x=\sqrt{n}$
> 2 votes

---
Tags: algorithm-analysis, data-structures, randomized-algorithms, linked-lists
---


title: Dynamic Learning (Machine Learning)

text:
# Question
Title: Dynamic Learning (Machine Learning)
I have been given a task to dynamically learn the optimum value of a parameter in a Heuristics Filtering Algorithm used in a tool.

The accuracy of the tool increase as the value of ***K*** in the heuristics filtering algorithm increases. How ever a lower ***K*** leads the tool towards a low resource consumption (memory, time and temporary storage).

How can I dynamically learning the optimum value of ***K*** using Machine Learning techniques so that the tool can dynamically generate an optimal value of ***K***.

I have been looking into Reinforcement Learning and learning from online resources. First, the problem has to be modeled as a Markov Decision Process (s, a, r, s'). I got stuck at what my State Space s should be. My set of actions a (they represent the value that k should be) are {10,20,30...,100}. Is Reinforcement Learning the way to go in the first place? If not, what other machine learning techniques do you suggest? I'm not into AI but I enjoy solving problems

# Answer
First some questions:

* Can $k$ only take on 10 possible values?
* From what you've said above, the measure of the 'quality' of a given value for $k$ would be an n-tuple e.g. $(accuracy,memory, time, storage)$, right?

So 'dynamically learning a value for $k$' involves learning a good choice based on $L$, the list of n-tuples for previous values of $k$.

Here are two very simple schemes:

If your problem is genuinely multi-objective, then you can always just pick the associated $k$ at random from the Pareto-front of $L$.

If your multiple objectives can be combined into a single quality value, then fit a differentiable curve (e.g. a polynomial) to these values, then symbolically determine the optimum of that curve and the associated value of $k$. Most computer algebra packages support the functionality for this, as does the Apache Commons Math library for Java.
> 1 votes

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Is there a name for the problem of spatially organizing a graph as to minimize total edge length?
The problem is that of spatially (with or without a fixed spatial dimension) organizing a graph so that each node becomes a cell in a grid, and each edge becomes a line, such that the total combined length of all lines (edges) is the minimal.

I want to know if that problem has a name, and how complex it is. I also would like to know if this problem is easier if done incrementally (i.e., starting with an empty graph and adding/removing nodes as to maintain that property).

# Answer
This is a version of graph drawing, restricted to vertices being on a grid, but allowing more than two dimensions. The one-dimensional case is an example of a graph layout problem, known as Minimum Linear Arrangement. In all of these problems, one is interested in minimizing some metric of the resulting diagram, which could be the number of edge crossings or, in your case, the total length of the edges.

These kinds of problem are very often **NP**-hard, even in the one-dimensional case: in particular Minimum Linear Arrangement, the 1D version of your problem, is **NP**-hard. There's a survey of graph layout problems by Díaz, Petit and Serna (*ACM Surveys*, 34:313–356, 2002; .ps.gz).
> 3 votes

---
Tags: complexity-theory, graphs
---


title: SVM Maximizing Margin

text:
# Question
Title: SVM Maximizing Margin
I am trying to make sense of the following:

Taken from the MIT website.

So I understand that we want to maximize the distance between the planes H0 and H1, where H0 is defined as `wx+b=0` and H1 is defined as `wx+b=1`. I am following with the definition that the distance betweena point `(x0,y0)` and a line `Ax+By+c=0` is `|Ax0+By0+c|/sqrt(A^2+B^2)`.

What I don't understand is... What is `wx+b`? So I understand `w` is the weight vector, `x` is an input and `b` is the offset, so `wx+b` gives an indication's of x's class as predicted using the model with weight vector `w`. But, when we are looking at the distances between H0 and H1, which are both lines, what 'line' and what 'point' are we referring to?

# Answer
> 1 votes
First of all, the formula given for the distance between a point and a line is not a *definition*, it is a *calculation*. The distance between a point $p$ and a line $\ell$ is the minimum distance between $p$ and a point on $\ell$.

Similarly, if $\ell,\ell'$ are two lines then the distance between them is the minimum distance between a point on $\ell$ to a point on $\ell'$. This is zero unless the lines are parallel, and if they are, say given by $x \bullet w + b = 0$ and $x \bullet w' + b' = 0$, then the distance is (I believe) $|b/\\|w\\| - b'/\\|w'\\||$. Again, this is not a formula but rather a calculation.

---
Tags: svm
---


title: How to prove P ⊆ Co-NP

text:
# Question
Title: How to prove P ⊆ Co-NP
My approach

> Let L ∈ P
>
> $\exists$ Turing Machine $M\_1$ which decides L.
>
> We can easily construct $M\_2$ which decides $\bar{L}$
>
> $\bar{L}$ ∈ CO-NP $\implies$ P ⊆ Co-NP

I'm not sure whether its a correct way to prove this or not. I found this method here Link

# Answer
> 6 votes
It's because P = Co-P: if we can find a solution for a problem in Polynomial time, we can also decide in Polynomial time that it does NOT have a solution. Now, since P ⊆ NP we have that the complement of this problem is in Co-NP. But the complement of any problem in P is in Co-P and therefore any complement of any P problem is in Co-NP. And since the complement of any P problem is Co-P = P, we have P ⊆ Co-NP

# Answer
> 1 votes
A deterministic polynomial time machine for a language $L$ can easily be converted to a non-deterministic polynomial time machine which has the same operational semantics (that is, it operates deterministically), and so it both non-deterministically and co-non-deterministically accept $L$ – just check the definitions.

---
Tags: complexity-theory, complexity-classes, np, p-vs-np
---