# Question
Title: If P is a property of turing machines, does P $\leq_T$ COUNT_P imply that P $\in$ RE $\cup$ coRE?
Fix an input and tape alphabet $\Sigma$ and $\Gamma$. Let P be a property of turing machines over these alphabets, i.e., a subset of $\\{\langle M \rangle \mid M \text{ is a TM over the alphabets } \Sigma \text{ and } \Gamma\\}$. Define COUNT\_P to be the function $\mathbb{N} \to \mathbb{N}$ describing the number of $n$-state turing machines over these alphabets which satisfy property $P$ (here, we also fix the states to be $\\{1, 2, \dots, n\\}$, so that we can't have two turing machines which are the same but with differently named states. Basically, we want the set of $n$-state turing machines to be finite).

One can show that if P is a recognizable (or co-recognizable) property, then P $\leq\_T$ COUNT\_P (here $\leq\_T$ denotes Turing-reducibility). What can be said about the converse of this statement? Indeed, if P $\leq\_T$ COUNT\_P, is P either recognizable or co-recognizable? I don't have any real reason to believe that this is true or false, but just would like to know an answer in either direction (seems difficult to find a counter-example or to prove it to be true).

# Answer
> 4 votes
Let $L \subseteq \mathbb{N}$ be a set of your choice, let $N(M)$ be the number of states in a Turing machine $M$, and let $P = \\{ \langle M \rangle : N(M) \in L \\}$. Then $P$ reduces to $\mathsf{COUNT}\_P$, but $P$ can be arbitrarily hard.

---
Tags: turing-machines
---


# Question
Title: difference between predictive modeling and clustering?
What are the fundamental differences between predictive modeling and clustering? according to literature, predictive modeling is a supervised learning with aim to construct models to predict the value of target attribute. On the other hand, clustering is a unsupervised method to split a data set to a couple of groups. In my idea, both of them are the same. when you are finding out the target attribute, you are actually trying to categorize it which is similar to clustering. I know that in clustering, we make subgroups of available data while in predictive modeling we try to find a model to predict value of attribute of unseen data based on current available data. Could anyone explain the differences between these two concept clearly? Thanks

# Answer
**Predictive models** are sometimes called learning with a teacher, whereas in **clustering** you're left completely alone.

**Predictive models** split data into training and testing subsample which is used for verifying computed model. Predictive (or regression) model typically assign weights to each attribute. From **clustering** you can compute some internal evaluation metric, but that doesn't necessarily correlate with (desired) human judgment. Unsupervised learning (clustering) mostly treats all attributes as equal as without external information, as one can't say which attribute is more important than the other.
> 1 votes

---
Tags: machine-learning
---


title: Represent a 5 card poker hand

text:
# Question
Title: Represent a 5 card poker hand
A deck of cards is 52. A hand is 5 cards from the 52 (cannot have a duplicate).

What is the least amount of bits to represent a 5 card hand and how?
A hand is NOT order dependent (KQ = QK). 64329 = 96432

Yes, can use 52 bits. That can represent a hand of any number of cards.

Given a hand is exactly 5 cards is there a way to represent it with less than 52 bits.

A single card can be represented with 6 bits = 64. So could just use 6 bits * 5 cards = 30 bits. But that would be order dependent. I could just sort and this should work. If that would not work please let me know.

Is there a way to get the key to 32 bits or under and not have to sort the 5 card tuple.

This is for poker simulations and sorting would be a lot of overhead compared to just generating the hand. If I have a dictionary with the relative value of each hand it is two simple lookups and a comparison to compare the value of two hands. If I have to sort the hands first that is large compared to two lookups and a comparison. In a simulation will compare millions. I will not get sorted hands from the simulation. The sort is not simple like 52 51 50 49 48 before 52 51 50 49 47. You can have straight flush quads ....

There are 2598960 possible 5 card hands. That is the number of rows. The key is the 5 cards. I would like to get a key that is 32 bits or under where the the cards do not need to be sorted first.

Cannot just order the list as many hands tie. Suit are spade, club, diamond, and heart. 7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h. There is a large number of ties.

The next step is 64 bits and will take the hit of the sort rather than double the size of the key.

I tested and `SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n };` doubles the time of the operation but I still may do it.

It gets more complex. I need to be able to represent a boat as twos over fives (22255). So sorting them breaks that. I know you are going to say but that is fast. Yes it is fast and trivial but I need as fast as possible.

C# for the accepted answer:

```
private int[] DeckXOR = new int[] {0x00000001,0x00000002,0x00000004,0x00000008,0x00000010,0x00000020,0x00000040,
                                    0x00000080,0x00000100,0x00000200,0x00000400,0x00000800,0x00001000,0x00002000,
                                    0x00004000,0x00008000,0x00010000,0x00020000,0x00040000,0x00080000,0x00100000,
                                    0x00200000,0x00400000,0x00800000,0x01000000,0x02000000,0x04000000,0x07fe0000,
                                    0x07c1f000,0x0639cc00,0x01b5aa00,0x056b5600,0x04ed6900,0x039ad500,0x0717c280,
                                    0x049b9240,0x00dd0cc0,0x06c823c0,0x07a3ef20,0x002a72e0,0x01191f10,0x02c55870,
                                    0x007bbe88,0x05f1b668,0x07a23418,0x0569d998,0x032ade38,0x03cde534,0x060c076a,
                                    0x04878b06,0x069b3c05,0x054089a3};
public void PokerProB()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    HashSet<int> cardsXOR = new HashSet<int>();
    int cardXOR;
    int counter = 0;
    for (int i = 51; i >= 4; i--)
    {
        for (int j = i - 1; j >= 3; j--)
        {
            for (int k = j - 1; k >= 2; k--)
            {
                for (int m = k - 1; m >= 1; m--)
                {
                    for (int n = m - 1; n >= 0; n--)
                    {
                        counter++;
                        cardXOR = DeckXOR[i] ^ DeckXOR[j] ^ DeckXOR[k] ^ DeckXOR[m] ^ DeckXOR[n];
                        if (!cardsXOR.Add(cardXOR))
                            Debug.WriteLine("problem");
                    }
                }
            }
        }
    }
    sw.Stop();
    Debug.WriteLine("Count {0} millisec {1} ", counter.ToString("N0"), sw.ElapsedMilliseconds.ToString("N0"));
    Debug.WriteLine("");
}

```

# Answer
> 10 votes
Let $C$ be a $\[52,25,11\]$ code. The parity check matrix of $C$ is a $27 \times 52$ bit matrix such that the minimal number of columns whose XOR vanishes is $11$. Denote the $52$ columns by $A\_1,\ldots,A\_{52}$. We can identify each $A\_i$ as a binary number of length $27$ bits. The promise is that the XOR of any $1$ to $10$ of these numbers is never $0$. Using this, you can encode your hand $a,b,c,d,e$ as $A\_a \oplus A\_b \oplus A\_c \oplus A\_d \oplus A\_e$, where $\oplus$ is XOR. Indeed, clearly this doesn't depend on the order, and if two hands $H\_1,H\_2$ collide, then XORing the two hash values gives $10-2|H\_1 \cap H\_2|\leq 10$ numbers whose XOR is zero.

Bob Jenkins describes such a code in his site, and from that we can extract the array

```
0x00000001,0x00000002,0x00000004,0x00000008,0x00000010,0x00000020,0x00000040,
0x00000080,0x00000100,0x00000200,0x00000400,0x00000800,0x00001000,0x00002000,
0x00004000,0x00008000,0x00010000,0x00020000,0x00040000,0x00080000,0x00100000,
0x00200000,0x00400000,0x00800000,0x01000000,0x02000000,0x04000000,0x07fe0000,
0x07c1f000,0x0639cc00,0x01b5aa00,0x056b5600,0x04ed6900,0x039ad500,0x0717c280,
0x049b9240,0x00dd0cc0,0x06c823c0,0x07a3ef20,0x002a72e0,0x01191f10,0x02c55870,
0x007bbe88,0x05f1b668,0x07a23418,0x0569d998,0x032ade38,0x03cde534,0x060c076a,
0x04878b06,0x069b3c05,0x054089a3

```

Since the first 27 vectors are just the 27 numbers of Hamming weight 1, in order to check that this construction is correct it suffices to consider all $2^{52-27}-1 = 2^{25}-1$ possible non-trivial combinations of the last 25 numbers, checking that their XORs always have Hamming weight at least 10. For example, the very first number 0x07fe0000 has Hamming weight exactly 10.

# Answer
> 13 votes
If we have a set of size $n$, you can represent an element of the set using $\lceil \lg n \rceil$ bits. You say that there are 2598960 possible 5-card hands. That means that a 5-card hand can be represented using just $\lceil \lg 2598960 \rceil = 22$ bits. 22 bits is significantly shorter than 30 bits.

How does the representation work? There are various options, with different tradeoffs. I list two below.

## Hard-coded dictionary

In this case, the number of possible 5-card hands is small enough that you could just have a hard-coded dictionary that lists all 2598960 hands, and you represent a hand by its index in the dictionary (represented in binary).

In other words, the dictionary can be a sorted list of hands. Each hand is the 5-tuple of the cards in the hand, in sorted order. You can look up a hand in the dictionary using binary search and find its corresponding index; and given an index, you can find the correspond hand. Or, you could store the dictionary as a hashmap that maps from the hand to its index. The index is an integer between 0 and 2598959, so it can be represented using 23 bits.

This approach will work and be very simple to program, but it is wasteful in space (size of the program executable).

## Ranking/unranking

Alternatively, if you care, there are better methods. See, e.g., any of the following references:

The general topic is known as "ranking (and unranking) of combinations". These are a little more complex to implement and understand, but avoid the need to include a hard-coded dictionary in the program.

# Answer
> 3 votes
You can sort the five items and simultaneously check for duplicates without any comparisons on some processors: Assume a processor has a fast instruction which determines the position of the highest bit set, and a fast instruction calculating a number with only the n-th bit set.

Let bit (n) be the number with exactly the n-th bit set. Let highest\_bit (x) be the number of the highest bit that is set in the number x, with an unspecified value if x = 0. Let x ^ y be the exclusive-or of x and y.

Given are five numbers a, b, c, d and e, each from 0 to 51, representing the five cards in the hand.

Let x = bit (a) ^ bit (b) ^ bit (c) ^ bit (d) ^ bit (e).

Let A = highest\_bit (x), change x to x ^ bit (A).

Let B = highest\_bit (x), change x to x ^ bit (B).

Let C = highest\_bit (x), change x to x ^ bit (C).

Let D = highest\_bit (x), change x to x ^ bit (D).

Let E = highest\_bit (x).

If x = 0 then there were duplicates in the numbes a, b, c, d, and e. Otherwise, use A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E as the encoding of the hand, where A, B, C, D and E are defined as above. This encodes a hand as a 30-bit string, while doing the sorting in a very efficient way.

---
Tags: combinatorics
---


# Question
Title: An encoding algorithm with an expensive encoder and a cheap decoder
I am looking for an encoding algorithm that would have an encoding function with highly expensive computational costs (ideally like scrypt). At the same time its decoding function must be a lot easier to calculate.

Computational costs should not depend on the size of the encoded data. The size of the encoded data can be up to 10 KB. The encoding part of the algorithm should also be small in the sense of not containing a huge constant data set used for calculations. The decoder can be large but not ridiculously (\< 10 MB). Some sorts of encryption are not forbidden.

Under computational costs I understand both calculation and memory costs, however one of them would also suffice

Pseudocode:

```
var encoded = encode("Hello world"); // Takes 10 seconds
var decoded = decode(encoded); // Takes 0.01 second

```

Encoding by brute-forcing the decode operation should be slower than encoding operation itself unless decode operation can be kept secret.

I was looking at asymmetric cryptography, I may be wrong, but those algorithms usually have equally expensive encryption and decryption functions. And their keys have length of the same order.

Maybe some of NP-complete problems could be a solution, but I don't know how to reuse them.

Thanks!

# Answer
There is a public-key scheme that achieves this, based on timelock cryptography. It is parameterized by a parameter $t$, which controls how slow encoding is. The time to encode (without knowledge of the private key) will be about $O(t)$; the time to decode (with knowledge of the private key) will be about $O(1)$; and the time to generate a private-public keypair (which should probably be counted as part of the running time spent by the decoder) is approximately $O(\lg t)$. Consequently, by making $t$ sufficiently large, you can have an arbitrarily large ratio between the time to encode and the time to decode.

The specific construction is based on timelock cryptography and the Rabin cryptosystem. Generate a RSA modulus $n=pq$ that has the following special form: $p=4u-1$, $q=4v-1$, $u \equiv v \pmod 2$, and $\gcd(p-1,q-1)=2$, where $u,v$ are integers. Let $\alpha$ be the integer such that $\alpha \equiv u \pmod{p-1}$ and $\alpha \equiv v \pmod{q-1}$. Pick a positive integer $t$, and compute the exponents $e=2^t \bmod \varphi(n)$ and $d = \alpha^t \bmod \varphi(n)$, where $\varphi(n)=(p-1)(q-1)$. Make $n,t$ public. The private key is $d$.

To encode a message $x$, you represent your message as a number $x$ that is a perfect square modulo $n$, a la Rabin's cryptosystem. Then compute $E(x) = x^{2^t} \bmod n$. This can be computed by repeatedly squaring $x$ (do it $t$ times).

To decode a codeword $y$, you compute $D(y) = y^d \bmod n$. Given knowledge of the private key, this can be computed efficiently, regardless of the value of $t$.

The person who creates the keypair can compute $d$ efficiently, using $O(\lg t)$ modular squaring operations (compute $\alpha$ using the Chinese remainder theorem, then compute $d$ using fast modular exponentiation, using knowledge of the factorization of $n$).

The parameter $t$ controls the time to encode. By choosing $t$ sufficiently large, you can make encoding 10 seconds. In contrast, decoding takes constant time (you can choose RSA parameters so that you can decode in 0.01 seconds). Or, to put it another way, creating the keypair takes $O(\lg t)$ time; encoding takes $O(t)$ time; and decoding takes $O(1)$ time. Therefore, the designer of the scheme can choose how long it takes to encode and how big the gap between encoding vs decoding will be.

This is basically the reverse of a timelock puzzle / timed-release cryptography. See https://crypto.stackexchange.com/q/606/351, Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify?, and Is it possible to create a "Time Capsule" using encryption?.

Why does this scheme work? In other words, why does decoding undo the encoding operation? It works for basically the same reason the Rabin cryptosystem works. In particular, raising to the $\alpha$th power computes a square root modulo $n$: raising to the $(p+1)/4=u$th power modulo $p$ computes a square root modulo $p$; raising to the $v$th power computes a square root modulo $q$; and by the Chinese remainder theorem, raising to the $\alpha$th power does both simultaneously, thus computes a square root modulo $n$. Thus $f(x)=x^2 \bmod n$ is a one-way permutation on the set of squares (quadratic residues) modulo $n$, and its inverse is $g(y)=y^\alpha \bmod n$. The crucial thing is that, without knowledge of the factorization of $n$, there is no known way to speed up repeated application of the function $f$; but with knowledge of $n$, you can dramatically speed up repeated application of the function $g$. So, encoding involves iteratively applying $f$; decoding uses the trick to apply $g$ many times, but faster than the naive method.
> 1 votes

---
Tags: algorithms, np-complete, cryptography
---


# Question
Title: What's the complexity of running an algorithm that searches over all cuts on a network and returns the minimum?
It's a question of a problem set. If I search for all possible cuts on a network graph and return the minimum, (so it will be equal to max flow), what will be the complexity of running this?

# Answer
According to CLRS (3rd, Section 26.2), the definition of *cut* is rather loose:

> A ***cut*** $(S, T)$ of flow network $G = (V, E)$ is a partition of $V$ into $S$ and $T = V - S$ such that $s \in S$ and $t \in T$.

Therefore, there are $2^{n-2}$ cuts of a flow network $G$ with $|V| = n$, no matter what the underlying graph is.

Obviously, however, not all the possible cuts are interesting (or meaningful) for the network flow problem.
> 1 votes

---
Tags: discrete-mathematics, network-flow
---


# Question
Title: Is there a greedy algorithm to solve the assignment problem?
The assignment problem is defined as:

**There are n people who need to be assigned to n jobs, one person per job. The cost that would accrue if the ith person is assigned to the jth job is a known quantity C\[i,j\] for each pair i, j = 1, 2, ..., n. The problem is to find an assignment with the minimum total cost.**

There is a question asking to design a greedy algorithm to solve the problem. It also asks if the greedy algorithm always yields an optimal solution and for the performance class of the algorithm. Here is my attempt at designing an algorithm:

Am I correct in saying that my algorithm is of O(n^2)? Am I also correct in saying that a greedy algorithm does not always yield an optimal solution? I used my algorithm on the following cost matrix and it is clearly not the optimal solution. Did I Do something wrong?

# Answer
The answer of your post question (already given in Yuval comment) is that there is no greedy techniques providing you the optimal answer to an assignment problem.

The commonly used solution is the Hungarian algorithm, see

Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955

for the original paper.

Otherwise your solution seems correct to me, and as usually with greedy algorithms, it will provide you a feasible solution which you may hope to not be "too far" from the global optimal solution.
> 2 votes

---
Tags: algorithms, greedy-algorithms, assignment-problem
---


title: Unary encoded language set

text:
# Question
Title: Unary encoded language set
While reading the book theory of computation by Michael Sipser, I did not understand the language given below. I will explain the problem first

> $$L = \\{1^n :n \in \mathbb{Z}\\}$$

Where $\mathbb{Z}$ is a set of integers.

**Question** :I am not able to understand the string that belong to the given set will look like.

I know if input alphabet is $\\{0,1\\}^\*$ then string 0101 (5 in decimal).

# Answer
> 2 votes
Forget about strings meaning anything. For any symbol $a$ and natural number $n$, $a^n$ is the string made from $n$ copies of $a$. So $a^1=a$, $a^2=aa$, $a^5=aaaaa$ and $a^0$ is the empty string, usually written as $\varepsilon$ or $\lambda$.

The set $\\{1^n\mid n\in\mathbb{Z}\\}$ isn't well-defined (did Sipser *really* write that?), since $-1\in\mathbb{Z}$ but $1^{-1}$ doesn't make sense: what would $-1$ copies of the symbol $1$ look like?

However, the set $\\{1^n\mid n\in\mathbb{N}\\}$ is just $\\{1^0, 1^1, 1^2, 1^3, \dots\\}$, i.e., $\\{\varepsilon, 1, 11, 111, \dots\\}$ (I'm considering zero to be a natural number; delete $\varepsilon$ if you think that one is the first natural number). Now, strings such as $111$ can be *interpreted* as numbers written out in some base (unary, binary, decimal, whatever). But the definition is just giving you a set of strings.

# Answer
> 0 votes
I think you need to understand the unary encoding. The set $$L =\\{1^n:n \in \mathbb{Z}\\}$$

contain strings like 1,11,111,1111 so on . Where 1,11,111,1111 represent 1,2,3,4 respectively in unary encoding.

---
Tags: automata, encoding-scheme
---


# Question
Title: Best way to merge 2 max heaps into a min heap
Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this?

The easiest way is to consider 2 max heaps an array with $2n$ elements and build a min heap with $O(n)$ complexity. Is there an algorithm with a complexity better than $O(n)$ ?

# Answer
> 1 votes
I guess you're thinking that there may be a faster way because if you want to merge two min heaps into a third min heap, is can be done in $O(\log n)$ by creating a $-\infty$ node in $O(1)$, making the roots of both heaps be children of that new node in $O(1)$, and extracting the min of the heap in $O(\log n)$.

But in your case, it can't be done. Clearly, building a min heap is harder than finding the minimum. But the minimum could be any of the leaves of the max heaps, so you have $O(n)$ elements of which you want to find the minimum. Clearly, you have to at least read all those elements and so you take at least $O(n)$ time. So it's $\Theta(n)$.

(Note that when merging two min heaps into a min heap, the minimum has to be one of the two roots, so it can be found in $O(1)$. But in the second case, there are too many nodes that could potentially be (i.e. are for some values of the heap) the minimum)

---
Tags: algorithms, data-structures, time-complexity, trees, heaps
---


# Question
Title: How to find ${O(T(n)=4T(\frac{n-2}{2}) +n^2)}$
In given:
$${T(n)=4T(\frac{n-2}{2}) +n^2 }$$ How can i find ${O(T(n))}$ ?

# Answer
> 4 votes
Let $S(n) = T(4n-2)$. Then $$ S(n) = T(4n-2) = 4T\left(\frac{4n-4}{2}\right) + \Theta(n^2) = 4T(2n-2) + \Theta(n^2) = 4S(n/2) + \Theta(n^2). $$ The master theorem tells us that $S(n) = \Theta(n^2\log n)$, and so $T(n) = \Theta(n^2\log n)$.

More generally, the statement of the Akra–Bazzi theorem (specifically, the $h\_i$ functions) makes it clear that the small perturbation in this recurrence ($\frac{n-2}{2}$ instead of $\frac{n}{2}$) doesn't change the asymptotics of the solution. From this theorem you can derive the solution directly without guessing the substitution $S(n) = T(4n-2)$.

---
Tags: recurrence-relation
---


# Question
Title: What is the name of this type of function composition?
If standard function composition is defined as:

```
 (define compose
   { (B → C) → (A → B)
             → (A → C) }

   F G -> (λ X (F (G X))))

```

What type of composition does the below function describe? Is there a particular name for it in category theory?

```
 (define compose-2
   { (A → (X → C)) → (B → X)
                   → (A → B → C) }

   F G -> (λ Y (compose (F Y) G)))

```

# Answer
You composition is of type $\operatorname{comp}:(A \to X \to C)\to (B \to X) \to (A\to B \to C)$. Up to Currying, it can be seen as being of type $(A \times X \to C)\to (B \to X) \to (A\times B \to C)$. So it's just a composition of a two arguments functions with a one argument function. You take $f$ and $g$ and return $(a,b)\mapsto f(a,g(b))$.

From a general abstract nonsense point of view, you can define the functor $$A\times -:\begin{array}{lll} O & \mapsto &A\times O\\ g : B \to X&\mapsto &\<\operatorname{id}\_A;g\>:A\times B \to A\times X \end{array}$$ and then your composition is just $\operatorname{comp}=f\mapsto g \mapsto f\circ (A\times g)$.
> 2 votes

---
Tags: functional-programming, mathematical-foundations, category-theory
---


# Question
Title: Sorting post numbers in a graph in $O(n)$ time
After running dfs on a graph, we get a list of n post and pre numbers. How do we sort this list in $O(n)$ time instead of $O(n\log n)$ time?

# Answer
You cheat. At the moment where you assign the post number, you know that it's the greatest post number so far. So you just keep a list vertices and whenever a vertex gets assigned a post number, you push it at the head of the list. At the end, the list will contain all vertices in decreasing post order. If you want them in increasing post order, you just have to reverse it which is $O(n)$. The same thing works for pre numbers.
> 2 votes

---
Tags: graph-traversal
---


# Question
Title: Is it possible that the diameter of a graph be shorter than the longest shortest path?
I used networkx to find the diameter of a graph that I have. It gave a diameter of 4. However, I found that between two particular nodes, using networkx's shortest path function, the path length is 5. I also coded dijkstra's algorithm and BFS from scratch and both returned a shortest path length of 5 too.

Is anything wrong with this? Isn't the diameter of a graph the longest shortest path?

This is what I'm using: http://vlado.fmf.uni-lj.si/pub/networks/data/Erdos/Erdos02.net

# Answer
> 3 votes
The diameter of a graph is, by definition, the length of the longest shortest path, i.e.,

$$\mathrm{diam}(G) = \max\_{x,y\in V(G)} \min\\, \\{\mathrm{len}(P)\mid P\text{ is a path from }x\text{ to }y\\}\\,.$$

But remember that the length of a path is the number of edges it contains, not the number of vertices. (That is, a single edge is a path of length 1, not 2.)

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


# Question
Title: Collection of real world non computable programming tasks
I'm quite new to computability theory and would be interested in some examples of realistic programming tasks you could encounter when working as a C++ programmer that are not computable.

# Answer
> 10 votes
* Are there some inputs that make my program crash?
* Can this object be freed (from memory) or can it be needed later?
* I'm building an editor and want to detect the programming language automatically. Given two languages described by CFGs, is there some input code for which I won't be able to guess the language (because it's valid in both languages)?
* Do these two programs do the same thing?

---

Suppose that you have a property of programs so that:

* It only depends on what the program does, not how it's written. So for example "It computes the factorial" or "It loops forever" work, but neither"It's written using a for loop" nor "It uses 5 variables" do.
* There is some program that has the property
* There is some program that doesn't have the property

Then Rice's theorem tells you that you can't have a (meta-)program that looks at source code and tells you if the program it describes has the property.

(My first and last examples are instances of that theorem)

# Answer
> 1 votes
Another uncomputable function that would be useful is one that compresses any data into a shortest possible description of it.

---
Tags: computability
---


# Question
Title: Getting O-bounds by applying regression methods to execution time measurements
Does anyone of you know how to associate an algorithm execution time (of experimental execution) to a well known complexity time? For example, say a divide and conquer algorithm lasts theoretically O(n·logn·n^2) or Ω(n·logn), in a theoretical way, doing reccurence ecuations and all that stuff. But when you plot the data from a CSV, you can't say just by looking at it 'oh yea this is O(n^2).

The data from the CSV is like:

```
n, execution_time_for_that_n...

```

How can I use a regression method to derive O-classes from such data?

# Answer
> 3 votes
It's impossible. No finite set of measurements can prove asymptotic bounds.

Proof sketch: Assume you had such a method. Apply it to any algorithm $A$. If your largest measurement is for input size $n\_0$, construct a new algorithm $B$ that branches into $A$ for all $n \leq n\_0$, and one with a different $\Theta$-runtime class for $n \> n\_0$. The method fails for $B$.

That said, there *are* ways to perform reasonable experiments (for average-case performance). I recommend the book "A Guide to Experimental Algorithmics" by C. McGeoch.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, experimental-analysis
---


# Question
Title: Why splitted text files is bigger than a large one with the same content?
I have this large text file that when unzipped has about 2GB. I split this one into multiple(more than 5 million) files and now I have a folder of about 20GB, how is this possible?

# Answer
Filesystem overhead.

Every time you create a file, the filesystem reserves space on disk to store the file name, and other metadata like its permissions, creation date, etc. It also has to maintain a sort of index of all the (possibly sparse) blocks occupied by each file. The index might be a simple list or a tree, depending on the filesystem.

Finally, note that most filesystems can not allocate only a portion of a block for a file, so the allocated space needs to be rounded up to the block size. This rounding affects both the file blocks, and the index blocks.
> 8 votes

---
Tags: filesystems, big-data
---


# Question
Title: Proof Review: Integer Factorization is in NP
I want to prove that integer factorization is in NP I have a general idea of how to prove this, and was wondering if I could get a sanity check: I'll show it's in NP by using a non-deterministic TM whose longest computational branch runs in polynomial time. The TM will do the following: Given an input (binary) word w of length n on the tape: Non deterministically guess i factors, 1\<=i\<=n, such that each of the factors is a binary string no longer than n. Multiply all of the factors together (I think this should take O(n^3)) and accept if the final number on the tape is equal to w. Otherwise, reject.

Am I missing anything?

# Answer
You are missing something.

If you are given what is supposed to be a factorisation of a number x, it's not enough to show that the product of those numbers is x. You also have to prove that all the numbers in the purported factorisation are primes.

Fortunately there is theorem that for every prime number, there is a polynomial time proof that it is a prime.
> 3 votes

---
Tags: turing-machines, factoring, check-my-answer
---


# Question
Title: Unique number to represent a combination of 5 numbers 1-39
This is a related question poker hand representation and I got a great accepted answer. The problem can be reduced to a virtual 39 card deck that from what I can tell is 16 bits.

I have 5 numbers 1-39 with none repeating. I need to uniquely identity those 5 numbers with the smallest possible number and not order dependent on the 5. I am pretty sure the number is 2^16. From the accepted answer to the link you go 01, 10, 100, ... and then start folding back. Then use an XOR on that matrix. I tried but I cannot figure out when / how to start folding back.

What is the matrix / array?

# Answer
> 3 votes
This can't be encoded into 16 bits. The number of such hands is ${39 \choose 5} = 575757$ (is that a pretty number or what?), and $\lg(575757) \approx 19.1$, so a 5-card hand be encoded into 20 bits, but it can't be encoded in 16 bits.

You can use the methods shown there (, ) to construct an encoding into 20 bits. Alternatively, if you want a coding-theory-based answer, analogous to Yuval's answer there (the accepted answer), you'll need to find a linear code of appropriate parameters. 16 bits isn't enough. Even 20 bits won't be enough; you'll need a slightly longer encoding, as the coding-theory-based solutions are fast to compute but yield an encoding that is slightly-longer-than-optimal.

---
Tags: combinatorics
---


# Question
Title: How to find the median of 5 elements by rote and its time complexity is O(n)
In the first step, I agree that divide n elements into groups take one pass so the time complexity is $$O(n)$$.

But if we need to find the median of each 5 elements, we may have to sort them. I know the time complexity of sorting is $$O(nlogn)$$.

How to find the median of 5 elements by rote and its time complexity is O(n). I cannot understand "**by rote**"

# Answer
"By rote" means "by a stupid/naive method". Here, the simples possible method is to check for each element if it's the median (by checking how many of the others are smaller or larger).

You could use any $\Theta(n^2)$ sorting method and pick the middle element. Or enumerate all permutations of the five elements and search for the sorted permutation.

Whatever you do, the running-time for each 5-element block will be constant, and so the total effort of that step will be linear.

---

You seem to be stuck at some basics of algorithm analysis; please refer to our reference questions to clear the waters.
> 0 votes

# Answer
Becuase $5$ is a constant, you can use (almost) any naive method to find the median of $5$ elements in constant time.

However, it is known that $6$ comparisons are sufficient (and necessary) to find the median of $5$ elements (try yourself). There are $\lfloor n / 5 \rfloor$ groups of $5$ elements. Hence, the second step can be done in time $\Theta(n)$.
> 0 votes

---
Tags: algorithms, selection-problem
---


# Question
Title: Expressing the condition as a set of linear constraints
Express the condition "$x = 0$ if and only if $y = 0$" as a set of linear constraints, where $x,y$ are integers such that $ - 5 \le x \le 8$ and $0 \le y \le 1$

# Answer
> 1 votes
I have managed to solve this problem:

So we must apply integer programming to satisfy logical condition: $$(x \ne 0 \vee y = 0) \wedge (y \ne 0 \vee x = 0)$$

The encoding i got $${M\_1}y \le x \le {M\_2}y \cup {M\_3}y \le x \le {M\_4}y{\text{ }}$$

Now set $${M\_1} = - 5,\\,{M\_2} = - 1,\\,{M\_3} = 1,\\,{M\_4} = 8$$

The encoding becomes $$-5y \le x \le -y \cup y \le x \le 8y{\text{ }}$$

The logical condition implies when $y = 0$, the value of $x = 0$. When $y = 1$, the value of $x \in \[ - 5, - 1\] \cup \[1,8\]$. If fact, when $y = 1$, integer variable $x$ can take on any value from $( - \infty , - 1\] \cup \[1,\infty )$. Hence we must provide an encoding that will force $x$ to take all values from its domain excluding $0$.

**Case** $y = 0$:

The encoding results in $0 \le x \le 0$, which forces $x = 0$

**Case** $y = 1$:

The encoding results in $$ - 5 \le x \le - 1 \cup 1 \le x \le 8$$

Thus, depending on $y = \\{ 0,1\\} $ a program can assign $x$ any value from its domain.

# Answer
> 1 votes
Let us instead translate $x=0 \leftrightarrow y=0$ into disjunctive normal form. We would get

$$ (x=0 \wedge y=0 ) \vee (x\>0 \wedge y=1) \vee (x\<0 \wedge y=1) $$

Each conjunction is a linear constraint.

In your solution you assumed that the constraint $y=1 \vee x=0$ is always true. In fact $y=1 \vee y=0$ is always true, since this is the domain of $y$.

If you kept this constraint, you would have eliminated solutions where $y=0$ and $x \not= 0$.

Another issue is with your interpretation of the constraints. The pair $$ \begin{array}{c} -M \< x \< 0\\ y=0 \end{array} $$ is a set of two constraints not a single constraint, therefore it is satisfied by the following 19 pairs $(-5,0),...,(8,0),(-5,1),...,(-1,1)$. The first 14 pairs clearly violate the condition $x=0 \leftrightarrow y=0$.

---
Tags: logic, linear-programming, integer-programming
---


# Question
Title: Why exactly are Regular Languages decidable?
I am trying to revise for my exams and going through my lecture slides and recordings, my lecturer didn't really give a clear example of why Regular languages are decidable.

She mentioned that it was because Regular Languages can be represented in Finite Automata, and can be classified as a subset of regular languages. As finite automata are special kinds of Turing Machines with bounded tapes in which you don't write anything, and just gave the definition of what decidable is, which in her words are "a Language L is Turing-decidable if there exists a TM that can decides it".

I sort of what she is getting at, but it seems extremely vague and over generalised that I don't fully understand what she is saying.

# Answer
I will try to explain it without a formal proof,

Imagine a turing machine where you have input written over a tape you can only but read only the input and not modify it. In addition you can only visit the length of the tape where the input is written. This gives you a finite number of configurations to traverse. Thus after a finite number of moves you can $Decide$ whether or not the word word belongs to the input language ; making regular languages decidable.
> 1 votes

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


# Question
Title: What is wrong with this conditional proof of P=NP?
I have recently thought up the following proof that L=P implies P=NP.

> Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified in logarithmic space. Thus NP=NL. But then NL is contained in P, which means that NP is contained in P and therefore P=NP.

By the efficient market hypothesis, I suspect this proof is flawed. I am however unable to determine the exact nature of the error. Can someone point it out?

# Answer
> Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified in logarithmic space. Thus NP=NL.

You haven't shown that **NP$\\,=\\,$NL**. The only method you've derived to show that $x\in A$, is to nondeterministically "guess" a witness $y$ and use the deterministic logspace algorithm to verify it. However, $y$ itself may be polynomially long, whereas your **NL** machine can only guess logarithmically many bits: your **NL** machine doesn't have enough space to store the witness, so you don't have an **NL** algorithm.

Also, note that we already know that witnesses to **NP**-complete problems can be verified in a complexity class smaller than **L**. Fagin's theorem says that **NP** is exactly the set of problems that can be defined in the existential fragment of second-order logic. This is equivalent to saying that you can verify a polynomial-length witness using first-order logic. **FO** is strictly weaker than **L**, since first-order logic can't solve simple logspace problems like telling you if your witness string contains an even number of $1$s.
> 11 votes

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


# Question
Title: Unique representation of 5-number sets with values 1-13
From a simulation I get 5 numbers 1-13. The nature of the simulation is that I do not get the numbers ordered. The value/rank of the the tuple is not order dependent 5 5 5 2 2 = 2 5 2 5 5. Values can repeat but they can repeat at most 4 times (it is a deck of cards). As it turn out there are 6175 combinations. Calculate the value of the tuple is expensive but it is pretty cheap to just generate the tuples in value order - save that and do a dictionary lookup. Without sorting the numbers what is the smallest number to uniquely represent the 5 number combination and how to generate that number?

Right now I just raise 5 to the 0-12 power and add the 5 as a proof of concept and it works. But that is fairly expensive and uses 32 bits. I want to get the bits and compute down. How might I do that?

Yes I have had few questions on this subject but I promise to make this my last.

In a related question got an answer for 5 numbers 1-52 in 27 bits using some magic numbers and XOR. I cannot figure out how to create those magic numbers for 1-13.

# Answer
> 3 votes
Here is a solution with 20 bits. Consider the following array:

```
0x000f2616, 0x000dbcce, 0x000533cf, 0x0007d943, 0x000a180c,
0x000f69f2, 0x0005e214, 0x0009da04, 0x000e101a, 0x000c495c,
0x0009cfaa, 0x000ff60d, 0x0000103d

```

Each of these numbers $x\_1,\ldots,x\_{13}$ is 20 bits long. Given a hand $a,b,c,d,e$, compute the 20 least significant bits of $x\_a+x\_b+x\_c+x\_d+x\_e$. You can easily check that this results in a value that identifies a hand uniquely.

I found these values by randomly generating arrays until one of them worked, so it's possible that a better construction exists (such as one using codes over $\mathbb{F}\_5$).

---

Here is another solution, which results in keys in the range \[0,441100\]. Let $p = 441101 \approx 2^{18.75}$, which is prime. The key corresponding to a hand $a,b,c,d,e$ is $5^a+5^b+5^c+5^d+5^e \bmod{p}$. This is the minimal prime that works. I calculated it by factoring all differences of $5^a+5^b+5^c+5^d+5^e$ for all pairs of hands.

You can also implement this using the array

```
1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 188721, 61403, 307015, 211772

```

Add the corresponding numbers, and (optionally) reduce modulo 441101.

# Answer
> 2 votes
Sorting five numbers is *so* fast that I don't see why you won't do it (implicitly or explicitly). For instance, you can just use insertion sort while creating the tuples. Or use counting sort, or radix sort (since you know the range of values and it's small).

Once the tuples are sorted, you can just number them by the lexicographic order, which is a nice exercise to do.

Note that whatever you do, you'll need at least $\log\_2\bigl(\binom{17}{5} - 13\bigr) \approx 13$ bits, which means in most real settings that you'll just use which ever `Int` datatype is available (maybe downgrading to `Int16` or `UInt16` if you manage to get that low, and such types are available).

Be mindful of premature optimization. First, do *something*. Then investigate if what you've got is fast enough. If not, find out where the bottleneck is. My gut says is *probably* not here.

---

I *think* sorting is a lower bound on this problem. If you have a unique numbering of tuples, looking up the sorted version in a table is an $O(1)$ operation, so in terms of complexity theory, computing this number can't be $\Theta$-faster than sorting (extending to arbitrarily large tuples). That does not say much about practical implementations (of constant-sized tuples), but it should give you some ideas about where natural boundaries may be.

---

For the fun of it, here is an idea to compute unique numbers without sorting. Assign each possible value $i$ the $i$-th prime $p\_i$. If $i$ appears $c\_i$ times in the tuples, its number is

$\qquad\displaystyle \prod\_{i=1}^{13} p\_i^{c\_i}$,

which is unique because prime factorizations uniquely map to numbers. You can compute this while iterating through the tuple once:

```
numberOf(t: (Int, Int, Int, Int, Int)) -> Int {
  c  = [Int](13)
  nr = 1

  for i = 1 .. 5 {
    c[t.i] += 1
    nr *= p[t.i]
  }

  return nr
}

```

The largest number you can get is the one of $(13, 13, 13, 13, 12)$ which turns out to have 70 bits -- not practical at all!

---
Tags: data-structures, sets, encoding-scheme
---


# Question
Title: How to describe a Turing Machine that accepts zeros in power of 3?
I need to describe by a graph a turing machine that can accept the language:
A = {0^(3^n ) |n≥0} = { 0 , 000 , 0^9 , 0^27 , ... }. **zeros in powers of 3**

This here is a turing machine that can accept the language:
A = {0^(2^n ) |n≥0} If that helps somehow..

# Answer
I wanted to post this as a tip cause this catches pow 3 but also (pow 3)\*2 :: 9 and 18 I sadly can't solve it perfectly right now but I'm certain you don't need more than 9 states, hope it helps you solve and I'm interested to see a real solution

Ps for you just a --\> 0
> 0 votes

---
Tags: graphs, turing-machines
---


title: Distributing resources for maximum gain

text:
# Question
Title: Distributing resources for maximum gain
This feels like it would be a well researched (or solved) problem, but I can't find the right words to search for it.

Suppose there is a collection of shared resources, and a collection of possible processes. Each process consumes fixed quantities of each resource and provides a fixed benefit. Each process can be applied zero or more times (but no fractional amounts), and resources can be left unused.

How can a distribution which maximises the total benefit be found? Brute-forcing each possible allocation will always find an answer, but is there a more optimal way?

An attempt to formalise the question:

$$ \text{Given resources } R \in \mathbb{R}\_{\ge0}^n \\ \text{and process requirements } P \in \mathbb{R}\_{\ge0}^{m,n} \\ \text{and process outputs } O \in \mathbb{R}\_{\ge0}^m \\ \text{find } N \in \mathbb{Z}\_{\ge0}^m \\ \text{such that no resource is over-spent: } \sum\_{i=0}^m{N\_i P\_{i,j}} \le R\_j \ \forall \ j \\ \text{and } N \cdot O \text{ is maximised} $$

# Answer
This is a knapsack problem. In the most basic version, you have a single resource (e.g., space in your knapsack) and you're trying to choose which items to put in it so you can carry the greatest value. People have also studied multi-constraint knapsack problems, which is the variant you're directly asking about.

The bad news is that knapsack problems are, in general, **NP**-complete. The good news is that they can be solved in pseudopolynomial1 time using dynamic programming, which is often practical. They can also be approximated fairly well: for any fixed $\varepsilon$, there is a polynomial time algorithm that will give you the answer to within a factor of $1\pm\varepsilon$. However, the dependence on the running time is superpolynomial, unless **P$\\,=\\,$NP**.

---

1 Pseudopolynomial time means that the running time is a polynomial function of the numbers represented in the input, whereas polynomial time means the running time is a polynomial function of the size of the input in bits. For example, the algorithm `read n; for i=1 to n do print "hello"; end` is pseudopolynomial: if its input is $n$, it performs $n$ iterations but, if the input is written as a $b$-bit binary number, then $n$ could be as big as $2^b$, so the algorithm isn't truly polynomial.
> 5 votes

---
Tags: optimization, resource-allocation
---


# Question
Title: Expressing a logical constraint in integer programming
Let $x$ be an integer such that $x \in \[ - 10,10\]$ and $b$ a binary variable. Apply **integer programming** to express $b = 1 \leftrightarrow x \ge3$

**My work:**

\begin{equation} \begin{cases} \text{if}\\,\\,\\,\\,\ b = 1, & \text{then}\\,\\,\\,\\,\\,\\,\ x \ge3 \\ \text{if}\\,\\,\\,\\,\ x \ge3, & \text{then}\\,\\,\\,\\,\\,\\,\ b = 1 \end{cases} \end{equation}

I got the following encoding $$3 + {M\_1}(1 - b) \le x \le 2 + {M\_2}b$$where $${M\_1} \le- 13{\text{ and }}{M\_2} \ge8$$

**Checking:**

Case: $b = 0$ $$3 + {M\_1} \le x \le 2$$For ${M\_1} \le - 13$, we have $x = - 10, - 9, \ldots ,2$

Case: $b = 1$ $$3 \le x \le 2 + {M\_2}$$ For ${M\_2} \ge 8$, we have $x = 3, 4, \ldots ,10$

Thus, by choosing $b = \\{ 0,1\\} $ we can force $x$ to take any value from its domain.

# Answer
Let $x \in \[-10,10\] \cap \mathbb Z$ and $y \in \\{0,1\\}$. Suppose that

$$y = \begin{cases} 1 & \text{if } x \geq 3\\ 0 & \text{if } x \leq 2\end{cases}$$

To ensure that $y \neq 0$ when $x \geq 3$, use

$$y \geq \frac{x-2}{8}$$

To ensure that $y \neq 1$ when $x \leq 2$, use

$$y \leq \frac{x+10}{13}$$

Pictorially,

The trivial inequality constraints are $-10 \leq x \leq 10$ and $0 \leq y \leq 1$. Lastly, the integrality constraints $x, y \in \mathbb Z$ should not be forgotten.
> 2 votes

---
Tags: logic, integer-programming, modelling
---


# Question
Title: Which class of neural network problem is this?
I have managed to describe a problem in quantum computing as the optimization of a function `f(graph,vector)`, over graphs and real vectors. For a given graph, I can optimize the vector with standard methods (say, gradient descent), but the search over graphs has to be a brute force random search, because I don't know what makes a graph 'good' for this application.

In any case, computing the value of `f` for a given graph and a given vector takes a time of the order of seconds, so even if I already knew good graphs the optimization of the vector would be feasible yet time consuming.

What I would love to try is to train a NN to find good pairs of graphs and vectors. Where do I start from? What kind of NN problem is this?

# Answer
> 1 votes
If I understand the question correctly, you want to find the optimum of the function $F(G) := \min\_{v\in V} f(G,v)$\*, where $V$ is your vector space, over all valid graphs $G$. Additionally, you can compute $F(G)$ for any given graph.

First of all, I doubt only neural networks are going to be very helpful. The main strength of neural networks is to classify given training data. Judging from your question, I doubt training data is abundant.

The general problem of *heuristically*\** optimizing an arbitrary function (here: $F$) over a **discrete** *solution space* (here: all valid graphs $G$) is usually solved by applying *metaheuristics*, such as local search methods (e.g. Hill climbing, simulated annealing, tabu search) or evolutionary algorithms.

These methods require you specify some structure of your solution space.

For local search, you need to define a *neighbour* relation between solutions to provide structure, such that

* The neighbour relation is symmetric
* Any two solutions are 'reachable' from another by
* The difference in $F$ between neighbours is usually (hopefully?) low.

For this problem, we could consider two graphs neigbours if we can reach the other by removing or adding an edge. This is clearly symmetric and all solutions are reachable if we assume all graphs have the same vertices. Then, all that's left is to hope that the network performance $F(G)$ *usually* doesn't change much if we remove/swap two edges.

Most likely, this neighbour relation does not suffice, as this is very problem-specific. If you have such a neighbour relation, you can apply some local search method and get a hopefully good answer.

\*: (You may want the maximum instead, but that doesn't really change anything, of course)

\**: In other words, we 'attempt' to find a good answer without any optimality guarantees. Note that this is even 'weaker' than approximation. These methods are often justified, as many optimisation problems over discrete domains cannot even be approximated efficiently. I think this is acceptable, as neural networks usually cannot guarantee any optimality either.

---
Tags: optimization, machine-learning, neural-networks
---


# Question
Title: Recurrence which cannot be analyzed by master theorem
Given the following recursion,
$$T(n)=T(\frac{n}{2})+ aT(\frac{n}{4})+n^2, $$ How can I find the minimal value for $a$ such that ${T(n)=ω(n^2)}$?

I tried to do it by *tree recursion* but I did not succeed to prove it by this method.

# Answer
> 5 votes
Suppose for simplicity that $n$ is a power of 2. Construct the tree corresponding to the recursion – each vertex is labelled by the current value of $n$, has three children, one of which is a leaf. We assume for now that the tree continues forever. Associate with each edge a weight, which is $1$, $a$, or $1$, depending on which term it corresponds to. The weight of a vertex is the product of all weights in the path from the root to the vertex.

Consider the generating series $$P(x) = \frac{1}{1-x-ax^2} = \sum\_{m=0}^\infty (x+ax^2)^m.$$ The coefficient of $x^k$ in $P(x)$ is the total weight of vertices whose label is $n/2^k$. Therefore $\tilde T(n) = n^2 P(1/4)$, where the tilde denotes that there is no base case and the recursion continues forever (we will discuss this later on). Thus $\tilde T(n) = \omega(n^2)$ iff the power series $P(x)$ diverges at $x = 1/4$. This happens if $1/4 + a/4^2 \geq 1$, that is, if $a \geq 12$.

There is a slight problem with this argument, namely the tree doesn't continue forever. However, it is easy to see that all leaves are at depth $\Theta(\log n)$, or more accurately, at depths between $\log\_4 n$ and $\log\_2 n$ (assuming a base case $T(1) = 1$). This shows that $$ \sum\_{m=0}^{\log\_4 n} \left(\frac{1}{4}+\frac{a}{16}\right)^m \leq T(n) \leq \sum\_{m=0}^{\log\_2 n} \left(\frac{1}{4}+\frac{a}{16}\right)^m. $$ When $a \< 12$, the preceding argument already shows that $T(n) = \Theta(n^2)$. When $a = 12$, these bounds show that $T(n) = \Theta(n^2 \log n)$. When $a \> 12$ these bounds are not enough to determine the asymptotics, though definitely $T(n) = \omega(n^2)$.

The Akra–Bazzi method is a general form of this argument. To solve your recursion, you first have to find the value of $p$ such that $(1/2)^p + a(1/4)^p = 1$. Given that, the Akra–Bazzi theorem tells you that $$ T(n) = \Theta(n^p) \cdot \left(1 + \int\_1^n \frac{u^2 \\, du}{u^{p+1}}\right) = \begin{cases} \Theta(n^2) & p \< 2, \\ \Theta(n^2\log n) & p = 2, \\ \Theta(n^p) & p \> 2. \end{cases} $$ (I leave the case analysis needed to prove the formula on the right-hand side to you. It is very instructive.) The critical point is when $p = 2$, and this happens when $1/4 + a/16 = 1$, that is, when $a = 12$, and so in this case $T(n) = \Theta(n^2 \log n)$. When $a \< 12$ we have $p \< 2$, and so in this case $T(n) = \Theta(n^2)$. These results agree with the calculations above. Finally, when $a \> 12$ we have $p \> 2$, and so in this case $T(n) = \Theta(n^p)$, the estimate which was too difficult for our crude method above.

# Answer
> 1 votes
Let's make a guess that $T (n) = k·n^2$ for some k \> 0. The recursion formula tells us that $T (n) = (k/4 + ak/16 + 1)·n^2$, so this works if $k = k/4 + ak/16 + 1$ or $(12 - a)·k = 16$. If a \< 12 then we get the easy solution $k = 16 / (12 - a)$. If a ≥ 12 then there is no solution k \> 0, so T (n) does *not* have the form $T (n) = k·n^2$.

You could then try to find $T (n)$ for $n = 2^m$, given a ≥ 12.

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


# Question
Title: Difference of Big-Oh terms -- what is the result?
I'd like to double-check my understanding of Big-Oh.

The definition is that $f(n) = O(g(n))$ if $|f(x)| ≤ M\\,|g(x)|$ for a natural number $M$ and for sufficiently large values of $x$.

Now, if $g(n) = O(n^2) - O(n^2)$, may we conclude that $g(n) = 0$? If not, what can we say about $g(n)$?

# Answer
We have $g(x) = f(x) - h(x)$ for some functions $f,h\in O(x^2)$. Since the functions are measuring the running time of some algorithm, I'll assume explicitly that $f(x)\geq 0$ and $h(x)\geq 0$, for all $x$. So there are constants $c\_1$ and $c\_2$ such that, for all large enough $x$, $f(x)\leq c\_1x^2$ and $h(x)\leq c\_2x^2$.

We have $g(x) = f(x) - h(x)$. Since $h(x)\geq 0$ for all $x$, we certainly know that $g(x)\leq f(x)$, since $g(x)$ is "$f(x)$ minus something non-negative." So, in particular, we have $g(x)\leq c\_1x^2$ for all large enough $x$, i.e., $g(x) = O(x^2)$.

However, we cannot conclude anything stronger in the general case. It is possible, for example, that $f(x) = x^2$ and $h(x) = 0$ for all $x$. Then $g(x) = x^2$. So, without more information about $f$ and $h$, we can't conclude that $g$ is any smaller than $x^2$.
> 3 votes

# Answer
Let's say we are talking about runtimes of algorithms, not functions. Then we can use the definition of $O (f (n))$ the way it is given here. But where would we encounter something like $O (f (n)) - O (g (n))$?

Here's a practical situation: I have a complex algorithm. One step in that algorithm has a runtime of $O (f (n))$. I could modify that step in a way that it now takes $O (g (n))$. How much faster will my algorithm be?

We can say naively that the improvement is $O (f (n)) - O (g (n))$. If $f (n), g (n) = O (n^2)$ then we can say equally naively that the improvement is $O (n^2) - O (n^2)$. But what is the actual improvement?

The fact is that with the information given, we have no idea. f (n) could always be 100 times larger than g (n), or always 100 times smaller, or sometimes larger and sometimes smaller; that's absolutely allowed by the definition of O (). All we can say is that the runtime of the algorithm will not improve by more than $O (n^2)$, and will not get worse by more than $O (n^2)$. We can't say whether it will improve or get worse, and it might be different depending on n.

But if we talk about functions, and not algorithms, then we must use a definition of O (f (n)) that takes into account negative values and somehow works in a meaningful way for negative values.
> 1 votes

# Answer
It is OK to say $$O(n^2) - O(n^2) = O(n^2)$$ which means that subtracting a function in $O(n^2)$ from another one in $O(n^2)$ gives a function in $O(n^2)$. Note that in algorithm analysis, we often assume that the functions considered take on positive values.

Be careful, because we don't have $$\Theta(n^2) - \Theta(n^2) = \Theta(n^2).$$ In contrast, we do have $$\Theta(n^2) + \Theta(n^2) = \Theta(n^2).$$

---

We don't have $g(n) = O(n^2) - O(n^2) \implies g(n) = 0$. For example, $$f\_1(n) = n^2 + n = O(n^2), \\;f\_2(n) = n = O(n^2),$$ $$f\_1(n) - f\_2(n) = n^2 = \Theta(n^2) \neq 0.$$
> 0 votes

# Answer
My (proposed) solution is:

$g(n) = O(n^2) - O(n^2) = M\*n^2 - M'\*n^2 = (M-M')\*n^2 = M''\*n^2 = O(n^2)$

that is:

$g(n) = O(n^2)$
> -1 votes

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


# Question
Title: Why is the inner product of -1,+1 binary variables at most $n-2$ and not at most $n-1$?
In short, if $x \neq u\_i \in \\{\pm1 \\}^n$ then why is:

$$ \langle x, u\_i \rangle \leq n-2 $$

but not:

$$ \langle x, u\_i \rangle \leq n-1 $$

?

---

To add context:

I was reading understanding machine learning from theory to algorithms and it had claim 20.1 section 20.3 on the section of the expressive power of Neural Networks. In the proof it said to consider "binary" vectors $\\{ \pm 1 \\}^n$ (which I will call Rademacher vectors). Let $f$ be a Boolean function and consider the Rademacher vectors that make $f$ output 1. If we consider some $x \in \\{ \pm 1\\}^n$ such that $u\_i \neq x$ then they claim that:

$$ \langle x, u\_i \rangle \leq n-2 $$

Which I think is false. Isn't the correct statement:

$$ \langle x, u\_i \rangle \leq n-1 $$

The reason I think this is if $x \neq u\_i$ then there exists at least **one** entry in the vector that are difference. Call it entry/index $j$. Thus $x\[j\] \neq u\_i\[j\] \implies x\[j\]u\_i\[j\] -1 $ since they must have opposite sign and both are entries in Rademacher vectors. Thus since we only need 1 entry for this to be true we get $-1$ instead of $-2$. In more detail an inner product is:

$$ \langle x, u\_i \rangle = \sum^n\_{j=1} x\[j\] u\_i\[j\]$$

since there are n terms we are adding, if we have n agreements then we have a sum of n, but if we have a single disagreement then we have only a decrease of 1, right? Is that correct or am I missing something super dum?

# Answer
> 2 votes
I just noticed that if we have one disagreement then we change one single entry from +1 to -1. Thus, the summation decrease by 1 because we are missing one of the +1's in the summation but on top of that because they are Rademacher vectors instead of simple binary 0,1 then it means that the +1 actually changes to -1, meaning the inner product decreases by an additional 1.

So it decreases by 2 cuz:

1. we lose a +1 in the summation
2. but we also replace the +1 with a -1

so total decrease is by two leading to $ \leq n-2$

---
Tags: machine-learning, neural-networks, boolean-algebra
---


title: universality of quantum gates

text:
# Question
Title: universality of quantum gates
Is there a difference between the set of quantum gates that are:

1. "universal" in the sense that you could calculate anything in BQP with a polynomial number of gates,
2. "universal" in the sense that you could approximate any arbitrary "gate" (unitary transformation) on a set of qubits?

And if so, what is the proper terminology to distinguish between these? (Or maybe it is exclusively used in only one of the above meanings?)

I believe these are at least different (but maybe the second implies the first). For example, it is my understanding that both of these sets:

* Toffoli and Hadamard gates
* CNOT gates plus all single qubit gates

are universal in the first sense, yet the first set cannot make phase shifts gates from the later. So Toffoli and Hadamard gates cannot be universal in the second sense.

Does any set meeting the second sense of universality automatically satisfy the first as well (or can some sets so inefficiently approximate calculations that they are not useful for modelling BQP)?

# Answer
Yes, approximate-any-quantum-gate implies can-solve-BQP-efficiently.

Even if the cost of approximating gates is very high, you only need to approximate Hadamard, CNOT, and $Z^{1/4}$ operations to some *constant* fidelity before error correction starts to work. So although you may pay a large constant overhead to get "good enough", once you get there the extra overhead to achieve better and better precision becomes reasonable.
> 3 votes

---
Tags: complexity-theory, quantum-computing
---


# Question
Title: Why do we prefer DFS to find connected components?
In finding the connected components in a graph, why do we use DFS, instead of BFS?

# Answer
> 5 votes
Two components $G\_1(V\_1, E\_1)$ and $G\_2(V\_2, E\_2)$ are connected if and only if there is a path between any vertex $v\_1\in V\_1$ and any other vertex $v\_2\in V\_2$. Here I'm assuming that both components are known to be connected, i.e., there is a path between any pair of vertices $v\_i, v\_j$ in any component (so that finding a path between any pair of vertices between both components fully connects them).

Hence, in finding connected components the procedure consists of starting in any vertex of $G\_1$ and collecting all nodes that are reachable from it. Clearly, this can be done either with *depth-first search* or *breadth-first search*:

1. *Breadth-first search* visits nodes in order of their depth from the start state, $s$. This way, it finds all paths of length 1, then length 2 and so on. Its main advantages are: it guarantees it will eventually find a solution (given sufficient memory, see below) and that the solution found is optimal; also, it can avoid *transposition* by maintaining a *CLOSED* list that stores all nodes previously expanded. Its main disadvantage is that it takes an exponential amount of memory (unless the graph being traversed is known to be *polynomial* but this is a rare case indeed).
2. *Detph-first search* generates paths of arbitrary length until a goal is found or a threshold is reached. Its main advantage is that it takes memory which is linear in the depth of the search tree developed. Its main disadvantage is that it cannot guarantee that it will ever find a solution and, if it does, that the solution is optimal.

Now, considering the problem stated above it becomes clear that the goal is not to reach a specific goal but to collect nodes reachable from the goal state. For this, there is no specific need to be optimal so that the question reduces to whether the available memory might be enough or not: whereas *Breadth-First search* does not provide any guarantee, *Depth-First search* does.

That is why we use *Depth-First Search* Mostly because: one, there is no need to find an *optimal* solution; second, memory matters!

Cheers,

---
Tags: algorithms, search-algorithms
---


title: On Plus of empty string

text:
# Question
Title: On Plus of empty string
We know $L^+=L^\star\backslash\\{\epsilon\\}$. How do we interpret that $\\{\epsilon\\}^+=\\{\epsilon\\}$?

# Answer
Your first definition only holds if $\epsilon \notin L$.

The Kleene star and plus are defined using recursive sets $V\_i$. We have:

$$V\_0 = \\{\epsilon\\}$$ $$V\_1 = L$$ $$V\_{i+1} = \\{ vw : v \in V\_i \wedge w \in L\\}$$

Then:

$$L^\* = \bigcup\limits\_{i=0}^{\infty} V\_i$$ $$L^+ = \bigcup\limits\_{i=1}^{\infty} V\_i$$

Note that $L^+$ *omits* $V\_0 = \\{\epsilon\\}$, but does not subtract $\epsilon$ from $L$.
> 4 votes

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


# Question
Title: Is this a valid proof of uncomputability of a function that doesn't use diagonalization?
Let's take the function $f = \\{(0,\pi)\\}$.

If I want to prove that such function is uncomputable I can simply say that calculating $\pi$ from $0$ would necessarily require infinitely many steps, since a Turing Machine can only write a single digit to its tape in each step.

Is this argument well constructed enough to be considered a legit proof? I think that this argument doesn't use diagonalization. Am I right?

Also: If I am right, can I apply that same argument to a similar function that has a periodic number in its codomain instead of $\pi$?

# Answer
> 5 votes
You're correct that you've not used diagonalization.

If you want to prove that something is or is not computable, you need a definition of computability. The standard definition is that a function $f$ from finite strings to finite strings is computable if there is a Turing machine $M$ such that, for every input $x$, $M$ halts with the value $f(x)$ written on its tape.

We already have a problem because the thing you're trying to prove uncomputable is of the wrong kind: it's not a function from finite strings to finite strings. As such, asking whether it's computable or not according to that definition just doesn't make sense – it's like asking if a cat is computable. In a sense, that completes your proof: you've shown that the object you're asking about doesn't meet one of the conditions for being computable, so it's uncomputable.

But it seems more likely that you have in mind some other definition of computability. What is that definition? Probably, if you try to write down that definition, you'll find that it doesn't make a lot of sense. Writing out $\pi$ requires writing an infinite amount of data, as you've observed. To produce a definition, you're going to have to be careful because the very essence of "computable" is that a Turing machine does something *and then halts* and it's impossible to produce infinite output and halt.

The standard definition of computability of real numbers is, essentially, that a number is computable if there's a Turing machine that will output arbitrarily good approximations. For example, a Turing machine that computes the function mapping an integer $n$ to the string containing the first $n$ decimal digits of the number. $\pi$ is computable in this sense: one way would be to use the fact that $\pi = 4(1-\tfrac13 + \tfrac15 - \tfrac17 + \tfrac19 - \cdots)$.

Numbers with periodic decimal expansions (i.e., rational numbers) are also computable in this sense. However, it would probably be better to consider rational numbers in the ordinary finite-string-to-finite-string model of computability, by representing a rational number as e.g. `1/7` rather than some infinite decimal expansion.

# Answer
> 5 votes
Decidable (language) and computable (number/function) have a very precise meaning, review the definitions to see why your argument is false.

I'll just point out a few problems to get you started. First, if your talking about a function $f:\mathbb{N}\rightarrow\mathbb{N}$, then you should specify how it behaves on all inputs, not just zero. Since there's nothing special about your $f$, your'e basically asking whether $\pi$ is computable (again, a well defined term, which means it can be approximated up to any required precision).

Obviously, a Turing machine cant write $\pi$ on its tape in a finite number of steps. Requiring to actually write the entire number as output would result in a not very interesting definition of "computable", since as you said, any non rational number (or even periodic rational) would be "uncomputable". However, given $n$, you could write a program that would output (in finite time) a number $\tilde{\pi}$ such that $\left|\tilde{\pi}-\pi\right|\le\frac{1}{n}$, so $\pi$ is in fact computable.

---
Tags: computability, undecidability, proof-techniques
---


# Question
Title: Maximizing the boolean combination of given real numbers
Let $x\_1, x\_2, \dots, x\_n \in \mathbb R$ and $b\_1, b\_2, \dots, b\_n \in \\{0,1\\}$. I want to know which of all the possible boolean combinations is maximal. For example, if $x\_1 = 2$ and $x\_2 = -2$,

$$\max \sum\_i b\_i x\_i = 2 \implies b\_1 = 1, b\_2 = 0$$

I can see that a brute force algorithm will have a running time complexity of $O(2^n)$. My question is whether there is an efficient algorithm for this or, at least, an approximation algorithm.

# Answer
> 4 votes
Maybe there is something I do not understand in your question, but the way it is formulated it seems that the set of solutions is:

* set $b\_i=1$ if $x\_i \> 0$
* set $b\_i=0$ if $x\_i \< 0$
* all others $b\_i$ can either be zero or one

It is clear that any other assignment will give you a lower value (either by adding a positive value or not adding a positive one). If $|\\{i:x\_i=0\\}|=K$, then you have $2^K$ solutions. This can be settled in $O(n)$ by a simple linear scanning of $x\_i$ values (even less if they are ordered).

---
Tags: optimization, approximation, integer-programming
---


# Question
Title: Algorithm to find path with max sum of degrees in a tree structure
Is there an efficient way to **find a path from root to a leaf such that it has the maximum sum of degrees of nodes** from all the paths possible in the tree.

For example if a tree is defined as the one in which each node is an integer and it has **as many child nodes as the perfect divisors of the integer**. And the root node is 16 then the sum of degrees of the required path would be **4+4+3+2+1 = 14**. The path being : **16-\>8-\>4-\>2-\>1**.

# Answer
In a tree, there is exactly one path from the root to any vertex. So just do depth- or breadth-first search on the tree and label each vertex with the sum of the degrees on the path from the root to there. Then pick the leaf with the smallest value.

An optimization could be to use greedy best-first search, where you maintain a queue of vertices in increasing order of their weight (sum of degrees on the path from the root). The first leaf you find would then be guaranteed to be the one of minimal weight. This would reduce the number of vertices that you look at but it's possible that the additional overhead of maintaining the priority queue would negate that benefit.
> 1 votes

# Answer
In a tree, there is only one path between the root and any leaf so you can just do a Depth-First Search and get the desired result.
> 0 votes

---
Tags: graphs, trees
---


# Question
Title: Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?
I know that given a system of multivariate quadratic equations (i.e, of the form $x^T Ax+b^T x=c$), deciding if there's a solution is NP-hard.

Is deciding if there's a solution to a single multivariate quadratic equation NP-hard too?

I am intersted in the NP-hardness of deciding if there's a solution to a single quadratic equation over any field; not only over $\mathbb R$.

I am currently trying to reduce from the problem of deciding whether there's a solution to the equation $x^T Ax=\lambda$ subject to $x\in\[0,1\]^n$ (which is NP-complete) to our problem using Lagrange multipliers.

# Answer
For $\mathbb{R}$ (the real numbers), you can decide whether a single multivariate quadratic equation has any real roots or not, in polynomial time. See https://cstheory.stackexchange.com/a/19858/5038. There are some other answers to that question that partly address the case of other fields.

For $\mathbb{F}\_2$ (the integers modulo two), you can decide whether there is a root in polynomial time. See https://cstheory.stackexchange.com/q/37687/5038.

I don't know what the situation is for $\mathbb{Q}$ or $\mathbb{F}\_{p^n}$.
> 3 votes

# Answer
It doesn't look like. The intuition that for example when $A$ is positive definite you can find a minimum and check if it is less than $c$.

Here is the approach to solve these equations.

Firstly, diagonalize $A = Q \Lambda Q^T$, where $Q$ is unitary. Then you have

$$ x^T Q \Lambda Q^T x + b^Tx = c $$

Substitute $y = Q^T x$ (then $x = Qy$).

You have $$ y^T\Lambda y + b^TQy = c $$

Here, denote $d^T = b^TQ$, and you have very simple equation $$ y^T \Lambda y + d^Ty = c $$ where $\Lambda$ is a diagonal matrix of eigenvalues.

You can do even more and get rid of a linear part by taking the square like $ax^2+bx = a(x^2 + \frac{b}{a}x) = a(x+\frac{b}{2a})^2-\frac{b^2}{4a}$ for every coordinate. Here several cases follows:

1. if all eigenvalues $\>0$ you have paraboloid so simply finding minimum and checking if it is less than $c$ will answer your question.
2. if all eigenvalues $\<0$ you have paraboloid and checking it maximum and checking if it is greater than $c$ will answer the question.
3. if there is an eigenvalue 0 and corresponding linear coefficient is not 0 than solution exists (for some $i$ you have $d\_iy\_i = c$, then $y\_i = \frac{c}{d\_i}$).
4. You have a saddle i.e. there is a eigenvalue \> 0 and eigenvalue \< 0. Then tending those coordinates to plus/minus infinity you see that your functions image is the whole $\mathbb{R}$ so there must be a solution.
5. if all eigenvalues and linear coefficients are 0 then there is a solution iff $c=0$.

The $\mathcal{NP}$-hard part comes into a play when you have restrictions on the domain for example a unit box.
> 1 votes

---
Tags: complexity-theory, np-complete, np-hard, decision-problem
---


# Question
Title: How are the 1s and 0s derived by the minimax algorithm for the game called "nim"?
I'm having trouble figuring out why the 1s and 0s are where they are in this game tree for the game Nim:

There is a statement in the book that explains the numbers but it's still not clear to me,

In implementing minimax, we label each level in the search space according to whose move it is at that point in the game, MIN or MAX.

In the example, MIN is allowed to move first. Each leaf node is given a value of 1 or 0, depending on whether it is a win for MAX or for MIN. Minimax propagates these values up the graph through successive parent nodes according to the rule:

If the parent state is a MAX node, give it the maximum value among its children. If the parent is a MIN node, give it the minimum value of its children.

If I was to draw the tree by hand how would I know where to put the 1s and 0s?

# Answer
The graph contains all positions reachable from the initial position. The values are determined as follows:

* A leaf (a node with no children) is labeled 0 if it is MAX's turn to play, and 1 if it is MIN's turn to play.
* A non-leaf belonging to MAX gets the maximum of the labels of its children.
* A non-leaf belonging to MIN gets the minimum of the labels of its children.

Hopefully you can now read the book and understand *why* we're doing the computation in this way.
> 1 votes

---
Tags: artificial-intelligence, heuristics, game-theory
---


# Question
Title: differences between theoretical research and applied research
What would be the differences between these two branches of research? For what I know the theoretical research is the one that will not necessarily end up with an application part, but the applied research deals with experimentation.

So it would be safe to say that applied research = experimental research?

Could anybody can bring up some examples to show the difference between these two types of research in the field of Computer Science?

I have been searching for some information about these topics, but I was not able to get a definitive answer.

Thanks

# Answer
Rule of thumb:

* Theoretical research concerns itself with *models*: defining models, determining their properties and theorems that hold given a set of models.
* Applied research concerns itself with the *real world*: solving problems given a real context governed by physical (or social) laws.

Obviously, the two are intertwined and not always clearly separated. For instance, TCSists sometimes call a piece of work "applied" if the model of choice somewhat resembles reality, in contrast to being completely academic.
> 3 votes

---
Tags: research
---


title: How can i find $Ω(f(n))$ and $O(f(n))$?

text:
# Question
Title: How can i find $Ω(f(n))$ and $O(f(n))$?
Given the following function,
$$f(n)=\prod\_2^n \log i. $$ How can I find $f(n)=\Omega (?)$ and $f(n)=O(?)$ ?

I tried to do it, but I have no idea how to do it ..

# Answer
> 4 votes
It will be easier to analyze $S(n) = \log f(n)$, which is given by the formula $$ S(n) = \sum\_{i=2}^n \log\log i. $$ According to the Euler–Maclaurin formula, $$ S(n) = \int\_2^n \log\log x \\, dx + \frac{\log\log 2 + \log\log n}{2} + \sum\_{k=1}^s \frac{B\_{2k}}{(2k)!} \[(\log \log)^{(2k-1)}(n) - (\log\log)^{(2k-1)}(2)\] + R, $$ where the remainder satisfies $$ |R| = O\_s \left(\int\_2^n (\log\log)^{(2s+1)}(x) \\, dx\right). $$ Here $(\log\log)^{(r)}$ is the $r$th derivative of $\log\log$ and $B\_{2k}$ are Bernoulli numbers.

In order to get big O asymptotics, it suffices for the error to be of order 1. The first few derivatives of $\log\log x$ are $$ \log \log x, \frac{1}{x\log x}, -\frac{\log x + 1}{x^2\log^2 x}, \frac{2\log^2 x + 3\log x + 2}{x^3\log^3 x}. $$ The third derivative has constant sign (for $x$ larger than some constant), and so when $s=1$, the growth rate of the remainder term can be bounded by the second derivative evaluated at $n$, which is $o(1)$. So it suffices to choose $s=1$. We obtain $$ \begin{align\*} S(n) &= \int\_2^n \log\log x \\, dx + \frac{\log\log 2 + \log\log n}{2} + \frac{\frac{1}{n\log n} - \frac{1}{2\log 2}}{12} + o(1) \\ &= x\log\log x - Ei(\log x) \bigr|\_2^n + \frac{\log \log n}{2} + O(1) \\ &= n\log\log n - Ei(\log n) + \frac{\log \log n}{2} + O(1), \end{align\*} $$ where $Ei(x)$ is the exponential integral. The exponential integral doesn't really reduce to any known function, but it is known that $E\_i(x) = (e^x/x)(1 + O(1/x))$. Therefore $$ S(n) = n\log\log n - \frac{n}{\log n} + O\left(\frac{n}{\log^2 n}\right). $$ This gives the value of $f(n)$ up to a factor of $e^{O(n/\log^2 n)}$. In the same way, we can get an explicit expression with error $e^{O(n/\log^k n)}$ for any constant $k$, using the divergent series for $Ei(x)$. If we want an expression with $O(1)$ multiplicative error, then the best we can get is $$ f(n) = \Theta(e^{n\log\log n - Ei(\log n)}\sqrt{\log n}). $$ With a bit of effort we can also find the hidden constant.

# Answer
> 4 votes
I won't even try to compete with Yuval's answer, but what are you going to do with a problem like this if you have no idea, and you are not a genius, and you want to get *some* result?

We can first observe that unlike other problems, in this case asking for $O (f (n))$ or $\Theta (f (n))$ means you need a very precise solution: The ratio between f (n) and f (n+1) is log (n+1) which goes towards infinity as n gets large. So if you manage to give an *exact* expression for f (n+1), then f (n+1) is *not* in $O (f (n))$!

Assuming that log(n) is the base 2 logarithm, log i ≥ 2 whenever i ≥ 4, which makes the product greater than $2^{n-3}$. log i ≥ 3 whenever i ≥ 8, so the product is greater than $3^{n-7}$ and so on. log i ≥ log n - 3 if i ≥ n / 8, so the product is also greater than $(\log n - 3)^{7n / 8}$, but less than $(\log n)^n$. So at least we can get a rough idea of how fast the product is growing, good enough to say that $\log f(n) = \Theta (n \log \log n)$, but nowhere near good enough for f (n) itself.

---
Tags: asymptotics
---


# Question
Title: How to model this constraint using integer linear programming?
Suppose we have $S=\\{1,2,\ldots,n\\}$, a binary variable $x$ and an integer $p$. I would like to model the following constraint using integer linear programming:

> If $x = 1$, then there must exists a unique $i\in S$ such that: $x\_j=1$ for all $j\in\\{i,i+1,\ldots,i+p-1\\}$.

How can I do this?

# Answer
> 3 votes
Assuming $x\_j$ are binary.

The additional *binary* variable $y\_i$ equals one if and only if when all $j$ are 1.

$$ \sum\limits\_{j=i}^{i+p-1}x\_j - p+1 \leq y\_i \leq \frac{1}{p}\sum\limits\_{j=i}^{i+p-1}x\_j $$

Then to have a unique $y\_i$ equals one you add $$ x \leq \sum\_{i=1}^n y\_i \leq (n-1)(1-x)+1 $$

---
Tags: integer-programming
---


title: Expected Number of Trials

text:
# Question
Title: Expected Number of Trials
I have an algorithm problem that I want to share with you and I want to get some idea how can I solve it.

Problem statement: You have to reach th Nth floor of a building by using a particular elevator: there is only one button that will take you from floor i to floor i+1 with probability p(i) or to floor 1 with probability 1-p(i). you are given the number of floor. next you are given N-1 number that represent the probability p(1)...p(n-1) you should output the expected number of turns needed to reach the Nth floor.

INPUT:

3

0.5 0.25

OUTPUT

13

What I know: if you have an event that can happen with a probability p the expected number of turns until this event occur is 1/p.

Now for the questions: Is the probability of getting to the last floor the product of all probabilities? I think this is wrong because we cannot apply it to the example 1/(p1\*p2) != 13

What kind of subjects (articles) should I read to solve this problem and problems similar to this.

If you have an idea feel free to share it but, please, don't give me the solution.

Thank you very much

# Answer
> 0 votes
Denote by $E\_i$ the expected number of turns it takes get to the $N$th floor from the $i$th floor. You are interested in $E\_1$. The numbers $E\_i$ satisfy the recurrence $$ E\_i = 1 + p\_i E\_{i+1} + (1-p\_i)E\_1, $$ valid for $i \< N$, with a base case $E\_N = 0$.

In order to solve this system of equations, multiply the $i$th equation by $p\_1 \cdots p\_{i-1}$ to get $$ p\_1 \cdots p\_{i-1} E\_i = p\_1 \cdots p\_{i-1} + p\_1 \cdots p\_i E\_{i+1} + \[p\_1 \cdots p\_{i-1} - p\_1 \cdots p\_i\] E\_1. $$ Summing this for $1 \leq i \leq n-1$, we get $$ E\_1 = 1 + p\_1 + p\_1p\_2 + \cdots + p\_1 \cdots p\_{n-2} + (1 - p\_1 \cdots p\_{n-1}) E\_1, $$ and so $$ \begin{align} E\_1 &= \frac{1+p\_1+p\_1p\_2\cdots+p\_1\cdots p\_{n-2}}{p\_1 \cdots p\_{n-1}} \\ &= \frac{1}{p\_1 \cdots p\_{n-1}} + \frac{1}{p\_2 \cdots p\_{n-1}} + \cdots + \frac{1}{p\_{n-1}}. \end{align} $$

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


# Question
Title: Comparing asymptotics of various functions
Is the first function big oh, theta or omega of the second function in the following examples.

$(\log n)^{\log n} $ and $ \frac{n}{\log n}$
I am not sure how fast the first function grows.

$n2^n$ and $3^n$
I think the second function grows faster but not sure how to prove it.

$(\log n)^{\log n} $ and $2^{(\log\_2n)^2}$
This is just puzzling.

$\sum\_{i=1 }^n i^k$ and $n^{k+1}$.
And so is this.

Any help is much appreciated.

# Answer
For the first and the third, taking the logarithm of both sides will really help. For the second, try to use the fact that if $\lim\_{n\to\infty} \frac{f(n)}{g(n)} = 0$ then $f(n) = o(g(n))$. For the fourth, try approximating the sum using an integral.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Cost of solving a matrix equation using the FFT
I am trying to calculate

$$V = (H^TH+I)^{-1} U$$

where $H\in\mathbb{R}^{m\times m}$ is a circulant convolution matrix corresponding to a convolution kernel $h$, and $U\in\mathbb{R}^{m\times n}$. The computation of $V$ can be done using the FFT algorithm.

I am confused about the computational complexity of using the FFT for this kind of problem. I will be most grateful if you could provide some suggestions or ideas for solving this problem. Thank you.

# Answer
> 3 votes
If $m \times m$ symmetric matrix $\rm H^{\top} H$ is circulant, then its spectral decomposition is

$$\rm H^{\top} H = Q \Lambda Q^\*$$

where the eigenvalues of $\rm H^{\top} H$ are given by the Discrete Fourier Transform (DFT) of the first row of $\rm H^{\top} H$, and where the eigenvalue matrix is

$$\rm Q = \frac{1}{\sqrt m} \\, F\_m$$

where $\rm F\_m$ is the $m \times m$ Fourier matrix. Hence,

$$\rm H^{\top} H + I\_m = Q \Lambda Q^\* + I\_m = Q \Lambda Q^\* + Q Q^\* = Q \\, (\Lambda + I\_m) \\, Q^\*$$

and

$$\rm \left( H^{\top} H + I\_m \right)^{-1} U = Q \\, (\Lambda + I\_m)^{-1} \\, Q^\* U = \frac 1m \\, F\_m \\, (\Lambda + I\_m)^{-1} \\, F\_m^\* U$$

The Fast Fourier Transform (FFT) algorithm can now be used to factor the Fourier matrix $\rm F\_m$ and its Hermitian transpose. What is the cost?

* Computing $\Lambda$ requires one DFT of length $m$. Using the FFT, that costs $O (m \log (m))$.
* Computing $\rm F\_m^\* U$ requires $n$ DFTs of length $m$. Using the FFT, that costs $O (n \\, m \log (m))$.
* Multiplying $\rm (\Lambda + I\_m)^{-1}$ and $\rm F\_m^\* U$ costs $m$ additions and $m \\, n$ divisions.
* Computing $\rm F\_m \\, (\Lambda + I\_m)^{-1} \\, F\_m^\* U$ requires $n$ DFTs of length $m$. Using the FFT, that costs $O (n \\, m \log (m))$.
* Dividing $\rm F\_m \\, (\Lambda + I\_m)^{-1} \\, F\_m^\* U$ by $m$ costs $m \\, n$ divisions.

Thus, the total cost is $O (n \\, m \log (m))$.

---

### References

---
Tags: algorithm-analysis, runtime-analysis, matrices, numerical-algorithms, fourier-transform
---


# Question
Title: Generating a Context Free Grammar from a Language
I am wondering how to go from a language such as this:

L = {a^n b^m c^k | n = m or m != k}

To a Context Free Grammar. I know that I would have to turn it into two separate languages but I don't know how to create the production rules for each of those languages.

# Answer
Given $L=\\{a^nb^mc^k | \ n=m \ \vee m \neq k \\}$ you can see it as $L=L\_1 \cup L\_2$ where:

* $L\_1=\\{a^nb^mc^k | \ n=m\\}$
* $L\_2=\\{a^nb^mc^k | \ m \neq k\\}$

Then you define 2 Context free grammars $G\_1$ and $G\_2$ for the 2 languages and in order to express the OR condition your add the production rule

$S \rightarrow S\_1\ | \ S\_2$

where $S$ is the starting symbol for $G$, $S\_1$ for $G\_1$ and $S\_2$ for $G\_2$.

As suggested in the comments, $L\_1$ and $L\_2$ can be splitted in order to make it easier the design of the grammars.

* $L\_1=L\_{1,1} \cdot L\_{1,2}$ where:

+ $L\_{1,1}=\\{ a^nb^n | \ n \geq 0 \ \\}$
    + $L\_{1,2}=\\{ c^k | \ k \geq 0\ \\}$
* $L\_2=L\_{2,1} \cdot (L\_{2,2} \vee L\_{2,3})$ where:

+ $L\_{2,1}=\\{a^n \ | \ n \geq 0\\}$
    + $L\_{2,2}=\\{b^mc^k | \ m \< k\\}$
    + $L\_{2,3}=\\{b^mc^k | \ m \> k\\}$
> 1 votes

---
Tags: context-free
---


# Question
Title: Shortest Path Variant (constrained max hop)
INPUT: directed non negative weighted graph, s, t, k

OUTPUT: SSSP from s to t where the path has $\leq k$ vertices

MY PROGRESS:

```
heap.add(s,0) where s is vertex and 0 is weight and heap is minheap
depth[s] = 1;
do
  c = heap.poll();
  SSSP[c] = c.weight
  if(depth[c] >= k) continue loop;
  for v in c's adjacent vertices
    if SSSP[v] is infinite
      heap.add(v, SSSP[c] + weight c to v)
      depth[v] = depth[c] + 1;
    else if getHeapNode(v).weight > SSSP[c] + weight c to v
      getHeapNode(v).weight = SSSP[c] + weight c to v
      heapify/shiftup
      depth[v] = depth[c] + 1;
while(!heap.isEmpty())

ans = SSSP[t];

```

Here is my approach and it doesn't work because I think there can be a case where a vertex that has been polled from the heap that exceeds $k$ when later is revisted by a longer (greater weight) path BUT at depth $\leq k-2$. This means that the neighbour of the polled vertex is reachable by the slower path but is not computable as the vertex has already been polled. I don't think this is the only criteria for max-k hops constrained shortest path. How should i go about doing this?

# Answer
The "best" way to solve your problem is by dynamic programming. This will give you a running time of O(k*n*MaxDegree).

The program is almost identical to the one for the knapsack. The basic idea is that you create a space (node, remaining hops), start at the destination (s,k) and then visit the neighbours of s, and so on.

For a deeper explanation, this problem is known as Constrained Shortest Path.
> 1 votes

# Answer
As indicated by Alberto, I don't think you have any option besides a standard search algorithm. The problem, like you suggest, is that, unlike in a standard Dijkstra algorithm, in this case you cannot dismiss a route just because it has worse added weight than another one to the same node. The algorithm could look like this:

```
function constrained_shortest_path(g : Graph, s : Node, t : Node, k : Int) : Path
    // queue contains tuples (<weight>, <nodes>, <depth>) and sorts by <weight>
    queue : MinHeap<(Int, List<Node>, Int)>
    queue.add((0, [s], 0))
    while queue is not empty do
        (weight : Int, nodes : List<Node>, depth : Int) := queue.poll()
        last_node = nodes.last()
        if last_node = t
            return nodes
        if depth >= k
            continue
        for adj : Node in g.adjacent_nodes(node)
            adj_weight := g.edge_weight(node, adj)
            queue.add((weight + adj_weight, nodes + [a], depth + 1))
    return []

```
> 0 votes

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


# Question
Title: PAC learnability given information about the expectation of the training/true error
Let $ \mathcal{X} $ be a domain set, $ \mathcal{Y}=\\{0,1\\} $ and $ \mathcal{H}$ an arbitary hypothesis class.

Assuming that there's an algorithm $ \mathcal{A} $ such that for every distribution $ \mathcal{D} $ realizable by $ \mathcal{H}$, it holds that $ \mathbb{E}\_{S \sim \mathcal{D} ^M}\[L^{0-1}\_{\mathcal{D}}(\mathcal{A}(S))\] \leq \mathbb{E}\_{S \sim \mathcal{D} ^M}\[L^{0-1}\_S(\mathcal{A}(S))\]+\epsilon\_m$ where $ \epsilon\_m \rightarrow0 $.

Does that mean that $ \mathcal{H} $ is PAC-learnable?

($L\_\mathcal{D}(h) $ is the true error of hypothesis $h$ with respect to the 0-1 loss function)

---

Well, I think that it's not, but I lack the knowledge to put a finger on the exact reason why.

My intuition is that even though $ \epsilon\_m \rightarrow 0 $, there still may be an arbitrary gap between $ \mathbb{E}\_{S \sim \mathcal{D} ^M}\[L^{0-1}\_{\mathcal{D}}(\mathcal{A}(S))\] $ and $ \mathbb{E}\_{S \sim \mathcal{D} ^M}\[L^{0-1}\_{\mathcal{S}}(\mathcal{A}(S))\] $. Thus, we still don't know how approximately good $ \mathcal{A}(S) $ is.

Can I deduce any promises whether $ \mathcal{A}(S) $ "probably" good (something about $\delta$)?

There's no need for formal proof. Rather, intuition will be appriciated.

# Answer
> 2 votes
$\mathcal{H}$ is not necessarily pac learnable.

Lets break down your statement, you have an algorithm $\mathcal{A}$, which given a set of labeled samples $S\subseteq \mathcal{X}\times \mathcal{Y}$, generates a hypothesis in $\mathcal{H}$. You also know that $\mathcal{A}(S)$ achieves a generalization error which is close to its sample error (the closeness is determined by $\epsilon\_m$).

If $\mathcal{A}$ was guaranteeing low sample error, then we were safe. However, this is not necessarily the case, take for example the rather stupid learning algorithm which always outputs some constant $h\in \mathcal{H}$ (and ignores the samples). This algorithm has equal sample/generalization error (so the condition is satisfied), but this obviously does not mean $\mathcal{H}$ is pac learnable (you can implement this algorithm even for $\mathcal{H}$ with infinite VC dimension).

---
Tags: machine-learning
---


# Question
Title: Parallel or efficient computation of value with momentum
I have a matrix $A$ with dimensions $M \times N$ and I want to compute $A'$ such that:

$$ A'\_{i,j} = \alpha A'\_{i,j-1} + (1 - \alpha) A\_{i,j} \\ 1 \leq i \leq M, 1 \leq j \leq N, \alpha \in \[0, 1\] $$

Where $A'\_{i,0}$ is some given constant.

I want to perform this computation as part of a machine learning training process on the GPU (I am using TensorFlow), but the only way to do it I can think of is with a loop over $j$, which makes the training tremendously slower (even if it's a TensorFlow loop, not a regular Python loop).

I know that being each value dependant on the previous one this is not a parallel-friendly computation, but I was wondering if there is some trick or reformulation that I am missing to make this in a smarter way.

# Answer
> 1 votes
I have noted that the above expression can be rewritten as:

$$ A'\_{i,j} = \alpha^j A'\_{i,0} + \sum\_{1 \leq k \leq N} (1 - \alpha) \alpha^{j-k}A\_{i,k} $$

Which makes me think I can define a $M \times N$ matrix $P$ as:

$$ P\_{i,j} = \alpha^j A'\_{i,0} $$

And a $N \times N$ matrix $R$ as:

$$ R\_{i,j} = \begin{cases} \alpha^{j-i} & \text{if}~i \leq j \\ 0 & \text{otherwise} \end{cases} $$

And so I *think* that I would have:

$$ A' = P + (1 - \alpha) A R $$

Which would be a more parallelizable computation. The only challenges would be to efficiently construct $P$ and $R$ (which is probably not that hard) and, more importantly, the memory usage if $N$ is big (which unfortunately in my case it kinda is).

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


# Question
Title: What is the name of the other vertex of an undirected edge?
Let's say I have an **undirected** graph with an edge $e = \\{a,b\\}$ connecting vertices $a$ and $b$.

Taking vertex $a$, what is the name of the other vertex? Is it the "co-vertex"? Or simply the "other vertex"? Or the "neighbouring vertex"?

# Answer
There's no set phrase; any clear description will do. "The other vertex in $e$", "the other endpoint of $e$", "$b$".

I've never heard of "co-vertex" and "neighbouring vertex" is vague, since $a$ might have multiple neighbours.
> 3 votes

# Answer
In graph theory, b would then be called an **adjacent vertex**.

Adjacent vertices are defined as follows.
Two vertices m and n are adjacent, if they are the end vertices of the same edge e.
> 0 votes

---
Tags: graphs, terminology
---


# Question
Title: Detemine if two DFA's are non-disjoint in polynomial time?
Given two DFA's , $M\_1$ and $M\_2$, I want to create an algorithm that determines if their languages are disjoint or not. The algorithm will run in polynomial time.

My idea is this: Let's say WLOG that $M\_1$ has 1 accepting state. We run DFS from that state and look at paths from the state to a starting state. Ideally, a path will be of the form $abb (a\cup b)abbb(ba)^\*$ The "or" operator will be used in places where the "path" from the root to the leaf node splits and then merges, and the "\*" operator will be used in case of cycles. We can then do the same thing for $M\_2$ and then do an intersection of their paths to find if they have any common paths.

This is basically just an idea that I had; I'm not too sure about the fine details, like how cycle detection will work, and if I need to modify DFS a bit for this to actually work.

Am I totally wrong? Are there any issues with this algorithm? Any help would be appreciated.

# Answer
> 0 votes
You want to know if there is any string accepted by both automata. There are standard techniques for producing an automaton that accepts exactly these strings, and there are standard techniques for seeing if the resulting automaton accepts any strings.

---
Tags: algorithms, automata, polynomial-time
---


# Question
Title: Matrix for modular exponentiation in Shor's algorithm
I'm trying to simulate Shor's algorithm with a model using vectors for quantum registers and matrices for quantum gates, however I'm stuck at the modular exponentiation bit of Shor's algorithm, having no idea how to build the corresponding matrix (unlike Hadamard and QFT). How can I build said matrix?

# Answer
> 0 votes
Note that Shor's algorithm doesn't require modular exponentiation. All you need is (controlled) modular *multiplication*.

There are two steps to getting the matrix for modular multiplication:

1. Write a function to turn any permutation into a matrix.
2. Apply it to the permutation $a \rightarrow a \cdot k \pmod{r}$.
3. *(Optional) Instead of making that matrix and multiplying by it, save massive execution time by just applying the permutation directly.*

For step 1, just have a function like this:

```
import numpy as np

def make_permutation_matrix(n, permutation):
    r = np.zeros((n, n))
    for i in range(n):
        r[permutation(i), i] = 1
    return r

```

Then for step 2, use it:

```
import math
k = pow(base, exponent, modulus)
n = math.ceil(math.log(modulus, 2))
mul_matrix = make_permutation_matrix(
    2**n,
    permutation=lambda x: x*k % modulus)

```

---
Tags: quantum-computing
---


# Question
Title: Complexity of / best algorithm for finding the dichotomy that maximizes information gain?
Suppose that $X$ is a finite set with a probability measure $P$. I want to find the subset $A \subset X$ so that the information gain of conditioning on ${A, A^c}$ is maximal. That is, I want to find $A$ that maximizes

$$H(X) -H(X|\\{A,A^c\\}) = H(X) - (P(A)H(A) + P(A^c) H(A^c)),$$

where $H(A)$ refers to the entropy of the conditional probability distribution so $\mu(B) = P(B \cap A) / P(A)$. (If $P(A) = 0$, then set $P(A) H(A) = 0$. In any case, it won't be a maximizer.)

Since this splits $X$ into two sets, I am calling this a dichotomy, and the question is of finding the dichotomy that produces the largest information gain.

Question: What is the complexity of this problem? (As D.W. points out below, a reasonable corresponding decision problem is - for $t \geq 0$, is there an $A$ so that information gain is $\geq t$? This decision problem is in NP, and we can ask if it is NP-hard, etc.) Is there a good heuristic algorithm for making this choice? What if I ask for an approximately, probably correct algorithm?

I am asking this question since I'm studying decision trees in machine learning and also coding theory, and this seems like a basic question in both settings.

# Answer
The information gain in that case depends only on the mass of $A$, and is maximized when $P(A)=\frac{1}{2}$. This probably shows why this definition of information gain is not very interesting.

Suppose $X=\left\\{x\_1,...,x\_n\right\\}$ and $P=\left(p\_1,...,p\_n\right)$.

The information gain is defined as

$IG(A)=H(X)-\left(P(A)H(A)+\left(1-P(A)\right)H\left(X\setminus A\right)\right)$

Where $H(A)$ is the entropy of the random variable which takes values in $A$ with probabilities $q\_x = \mathbb{1}\_{x\in A}\frac{p\_x}{p(A)}$.

Now lets write explicitly what is $IG(A)$:

$$\begin{align\*} IG(A)&= H(X)+P(A)\sum\limits\_{x\in A} \frac{p\_x}{P(A)}\log \frac{p\_x}{P(A)}+ \left(1-P(A)\right)\sum\limits\_{x\in X\setminus A} \frac{p\_x}{1-P(A)}\log\frac{p\_x}{1-P(A)} \\ &= H(x)+\sum\limits\_{x\in A} p\_x\log \frac{p\_x}{P(A)}+ \sum\limits\_{x\in X\setminus A} p\_x\log\frac{p\_x}{1-P(A)} \\ &= H(A)+\sum\limits\_{x\in A} p\_x\log p\_x -\sum\limits\_{x\in A} p\_x \log P(A) + \sum\limits\_{x\in X\setminus A}p\_x\log p\_x - \sum\limits\_{x\in X\setminus A}p\_x\log \left(1-P(A)\right) \\ &= -P(A)\log P(A) - \left(1- P(A)\right)\log(1-P(A)). \end{align\*}$$

So setting $y=P(A)$, you seek to maximize $f(y)=-y\log y-(1-y)\log(1-y)$ in $y\in\[0,1\]$. Maximum is achieved at $y=\frac{1}{2}$.

The optimization problem (or corresponding decision problem) is NP-hard, meaning that unless $P=NP$, you can't find a subset $A$ which minimizes $\left| P(A)-\frac{1}{2}\right|$ in polynomial time. This problem is called the partition problem (special case of subset sum), only that now you have the constraint that the elements sum to 1. See this question for some information about the hardness of partition problem.
> 4 votes

---
Tags: complexity-theory, optimization, machine-learning, coding-theory, entropy
---