# Question
Title: Analyzing space complexity of passing data to function by reference
I have some difficulties with understanding the space complexity of the following algorithm. I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^N), where N - the length of the initial vector. In all those cases all the subsets (vectors) are passed by value, so we contain every subset in the recursion stack. But i passed everything by reference. This is my code:

```
class Solution {
public:
vector<vector<int>> result;
void rec(vector<int>& nums, int &position, vector<int> &currentSubset) {
    if (position == nums.size()) {
        result.push_back(currentSubset);
        return;
    }

    currentSubset.push_back(nums[position]);
    position++;
    rec(nums, position, currentSubset);
    currentSubset.pop_back();
    rec(nums, position, currentSubset);
    position--;
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector <int> currentSubset;
    int position = 0;
    rec(nums, position, currentSubset);
    return result;
}
};

```

Would the space complexity be O(N)? As far as i know, passing by reference doesn't allocate new memory, so every possible subset would be contained in the same vector, which was created before the recursion calls.

I would also appreciate, if you told me how to estimate the space complexity, when working with references in general. Those are the only cases, where i hesitate about the correctness of my reasonings.

Thank you.

# Answer
All the computations of complexity depend on your model of computation, in other words on what *you* would like to count.

You may, as you say, only count memory that your code itself allocates. You should be aware that this way of counting space used can become useless easily. You can modify any algorithm to delegate all allocation to the caller. It is not very informative to say that you can solve any problem in constant space.

Another possibility is to count all memory space that gets accessed. If an algorithm accesses all the memory to store the input, do we count it? Some people do.

A more common way to define memory complexity is to measure the memory that the program modifies. Whether the program allocates it or the caller does, it doesn't matter in this case.

Relevant to the computation is also the units in which the memory is measured. You could count bits. This assumption leads to the claim that storing an integer $n$ will require $O(\log(n))$ of space. But this is not the only model used. You could assume that your model of a computer stores integers. In this model storing an integer requires just one unit of space. This is common when the size of the integers involved at not going to be large compared to other sizes of the inputs. These assumptions are relevant to the discussion in the comments. You both are right, but are using different units to quantify memory. These are not even the only options. Some models assume that a unit of memory can store an infinite precision real number, for example.

There are other aspects that sometimes are also taken into account. For example, in real world computers not all memory is the same. In some models memory is separated in a hierarchy. For example, according to response time. Registers and cache are faster than hard drive or magnetic tape. The space complexity can take into account how much of the different types of memory is used.

It is very common to just mention an $O$ class to which the amount of space used, as a function of some size of the input, belongs. To not be wrong it is better to clarify what is being counted and in what units.
> 1 votes

# Answer
I dont really know c++, but I can tell you what counts as space complexity:

1. Everything that creates new data does, and anything that does not create additional data has $O(1)$ space complexity: passing by reference is $O(1)$, passing by value is $O(n)$ (for $n$ being input size).
2. Looping over an array requires an index, which costs $O(log(n))$ space complexity.
3. Recursive calls in a function: the program has to remember where it was when calling a function, so when you have a recursive function - each recursion depth adds more to the space complexity.

Also, a really rough estimate to the space complexity is that it's bounded by the time complexity.
> 0 votes

---
Tags: algorithm-analysis, recursion, space-complexity, c++
---


title: Double Hashing with Strings as key

text:
# Question
Title: Double Hashing with Strings as key
How would you choose the second hash function with for double hashing with string as key? My first hash function is the scalar product of a random int array with the 16 bit number of each character. Is that a good first hash function? And what should I do for the second function now?

# Answer
There are many hash functions for hashing a string; a web search should turn up a bunch. You can use any one you like. The fact that you are using double hashing doesn't impose any additional requirements on the hash function. Yes, that would be a reasonable hash (and you could use two different int arrays for the two different hash functions); there are many other choices that would be reasonable as well.
> 0 votes

# Answer
Today, I would choose a second hash function that has the same form as the first hash function, but uses different constants.

The reason why is that modern CPUs have SIMD instructions, so you can compute both hash functions at the same time.
> 0 votes

---
Tags: hash, hash-tables, hashing
---


title: Smallest subarray problem

text:
# Question
Title: Smallest subarray problem
Say you have an array of integers like \[1, 2, 3, 4, 5, 6\], the problem is to find the smallest way to break up the array into sub-arrays where each sub-array satisfies the following requirement:

* sub-array.first\_integer and sub-array.last\_integer must have a common divisor that is not 1.

So for \[7, 2, 3, 4, 5, 6\] the answer would be 2, because you can break it up like \[7\] and \[2, 3, 4, 5, 6\], where 2 and 6 have a common divisor of 2 (which is \> 1 so it meets the requirement).

You can assume the array can be huge but the numbers are not too big. Is there a way to do this in n or n\*log(n) time? I think with dp and caching n^2 is possible but not sure how to do it faster.

Here is my current attempt with a BFS, but it's still N^2:

https://onlinegdb.com/ryZwkYnA8

Edit: OK I think I found an improvement which is a polynomial times the square root of a pseudo-polynomial: n * sqrt(magnitude of the values). Seems much faster, it basically builds an adjacency list; and can be done BFS, DP, and caching all the same. Although I wonder if anything better is available?

https://onlinegdb.com/SJpl4930L

# Answer
In my answer I will assume that all numbers are at most $M$ big, i.e. $A\[i\] \le M$.

First some comments about your both approaches.

Computing the GCD takes $O(\log M)$ time. So your first approach is actually $O(N^2 \log M)$. I also don't think that your second approach is actually better than $O(N^2)$. For instance assume if all the numbers of the first half of the array are equal. Then for each of those numbers you have at least $\Theta(N)$ effort for each divisor of $N$. Which means that the complexity for such a test case is something like $O(N^2 \sqrt M)$.

---

Let's first discuss a very trivial (but slower) dynamic programming solution, on which I will later base a better one.

Let's define the function $f$ as $f(i)$ is the smallest number of subarrays in which you can split the prefix of size $i$ of the array (the first $i$ numbers). Also let $f(i) := \infty$ if it is not possible to split the array, and $f(0) := 0$.

It's easy to see, that you can compute $f(i)$ using the recursion:

$$f(i) = \min\_{\substack{1 \le j \le i\\ \gcd(A\[i\], A\[j\]) \> 1}} f(j-1) + 1$$

This formula is very trivially to implement together with dynamic programming, and will have the complexity $O(N^2 \log M)$.

```
f(0) = 0
for i = 1 to N:
    f(i) = infinity
    for j = 1 to i:
        if gcd(A[i], A[j]) > 1:
            f(i) = min(f(i), f(j-1)) + 1
print f(N)

```

---

Now to a better approach. We need two mathematical facts that will help us:

* If two numbers have a common divisor greater than one, then they have a common prime factor.
* A number $\le M$ has at most $\log M$ prime factors.

Let the set of prime factors of $x$ be $P(x)$.

Then we can also rewrite the recursion for $f$ as:

$$f(i) = \min\_{p \in P(A\[i\])} \left( \min\_{\substack{1 \le j \le i\\ p ~|~ A\[j\]}} f(j-1) \right) + 1$$ In other word, if $A\[i\] = 20 = 2^2 \cdot 5$, then we look for all previous numbers who are divisible by 2, and take the minimum of $f(j-1)$, and for all previous numbers who are divisible by $5$ and take the minimum of $f(j-1)$. The actual optimal value $f(i)$ will one more than the minimum of both.

If we define $g(p, i)$ as the minimum of $f(j-1)$ with $p ~|~ A\[j\]$ and $1 \le j \le i$, then the formula simplifies to:

$$f(i) = \min\_{p \in P(A\[i\])} g(p, i) + 1$$

We can actually apply some sort of dynamic programming also to the function $g$. We store the values in a hash table. First we initialize the function for every possible prime factor with $g(p) = \infty$, and whenever a $f(j-1)$ changes, we update $g(p)$ for every $p \in P(A\[j\])$.

This means, after we update $f(i)$, we only need to update $O(\log M)$ different values of $g$.

This gives us the following algorithm:

```
# initialize g
for all p:
    g(p) = infinity

# set the first value f(0)
f(0) = 0
# update g
for p in P(A[1]):
    g(p) = min(g(p), f(0))

for i = 1 to N:
    # first compute f(i)
    f(i) = infinity
    for p in P(A[i]):
        f(i) = min(f(i), g(p)) + 1

    # and then update g
    if i < N:
        for p in P(A[i+1]):
            g(p) = min(g(p), f(i))
print f(N)

```

It's easy to see that this algorithm runs in $O(N \log M)$ time.

A shorter variation, but with the exact same approach and complexity, would also be:

```
for all p:
    g(p) = infinity
f(0) = 0
for i = 1 to N:
    f(i) = infinity
    for p in P(A[i]):
        g(p) = min(g(p), f(i-1))
        f(i) = min(f(i), g(p)) + 1
print f(N)

```

The only thing to discuss is, how we get the prime factorization of each number. There are loads of different approaches. For instance if $M$ is not too big, you can compute the Sieve of Eratosthenes in $O(M \log M)$ and during the computation store a prime factor for each number $\le M$. This allows to compute the prime factorization of each number in $O(\log M)$. Another option would be just to compute the prime factors on the fly, which would give take additionally $O(N \sqrt{M}$) time if you use the typical trial division until square root algorithm.
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Linear Programming Problem - what is feasible size for solution on a PC
I need to get feeling for the feasible size of a LPP, that can be solved on a PC. Say, its a good one (8 cores @ 3+GHz, 64GB RAM). We also assume that number of variables is close to the number of additional conditions.

I know it depends on the solver, but what size is feasible for solution in several hours/few days? 1000 of variables? A million? Order of magnitude would be enough.

Update. Let's consider a general form: matrix is not sparce/diagonal/blotchy or whatever. Let's say matrix's rows are filled with many hundreds of values (@ thousands of variables).

# Answer
There is no simple answer. The running time depends not only on the number of variables, but also on the "difficulty" of the system of inequalities. The best you can do is to try to benchmark on representative problem instances.
> 1 votes

# Answer
For continuous LP, problems with millions of nonzeros are solved routinely. I'd expect problems with 10 millions nonzeros to be solvable, barring numerical issues. You can find some benchmarks here, but they do not include the best commercial solvers, which I remember solve all problems.

This is my guess from experience, and I think common knowledge in the field, but can vary a lot:

* This could be a lot more for particular problem structures that you can exploit with a specialized algorithm
* Some kinds of problems may of course be harder to solve
* Solvers improve. Maybe my knowledge is already outdated and it's closer to 100 millions :D

The example you cite (a dense matrix) is very uncommon in practice, for example. This is why I use the number of nonzeros as a metric rather than the number of rows/columns.
> 4 votes

# Answer
I would assume a few times n^3 operations for n variables. How many operations per second can you perform? Using vector operations is not too difficult. Using 8 cores *for one problem* is hard. Depending on your programming effort you will be able to do between 1 and 100 billion operations per second, or 100 to 10,000 trillion operations per day, or very roughly n = 20,000 to 100,000. Buy a lot of RAM as well.
> 2 votes

---
Tags: time-complexity, linear-programming
---


# Question
Title: What is Pumping length for Union of Regular languages?
This is an exam question.

For E = {a,b}. let us consider the regular language $L= \\{x|x = a^{2+3k} or x=b^{10+12k}, k \>= 0\\}$

Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

A)3

B)9

C)5

D)24

Ans is 24.

As per me pumping length is the length which gets actually repeated. So, basically it's the length of y as per pumping lemma statement.

Now, for the first regular language, $a^{2+3k}$ How I visualized?

There would be sure 2 states which accept min 2 'a' ( since k\>=0).

Now, then I have $a^{3k}$ Means, which should definitely have a loop of length 3.

So, I choose x=2 (first 2 states) y=3 (the repeating part) and z=0.

So this first language must have atleast 3 as the pumping length.

And in similar lines the other must have. Atleast 12 as pumping length. (X=10, y=12, z=0)

And that's why as per me 24 is right. (Still sketchy at concluding)

Plz tell me if my understanding of Pumping length is right? If no plz try suggesting some links/references. If yes then have I applied the Concept right?

# Answer
A pumping length is a positive integer $p$ such that any string of $L$ of length at least $p$ can be decomposed in the form $xyz$ with $|xy|\leq p$, $|y|\>0$ and for all $n\geq0$ the words $xy^nz$ are in $L$.

Assume that $p\<12$. Then the word $b^{10+12}$ should be able to be decomposed as above. We cannot take $y$ with $1\leq|y|\leq p \<12$. Otherwise $xz=xy^0z$ wouldn't be in $L$.

We can take $p=12$ or larger.

If $10+12k=|b^{10+12k}|\geq p\geq 12$ then $k\geq1$ and we can decompose $b^{10+12k}$ as $xyz$, with $x=\epsilon$, $y=b^{12}$ and $z=b^{10+12(k-1)}$. Then $|xy|=12\leq p$ and for all $n\geq0$ we have $xy^nz=b^0b^{12n}b^{10+12(k-1)}=b^{10+12(n+k-1)}$ in $L$, since $n+k-1\geq k-1\geq0$

If $2+3k=|a^{2+3k}|\geq p\geq 12$, then $k\geq4$. We can decompose $a^{2+3k}$ as $xyz$ with $x=\epsilon$, $y=a^3$ and $z=a^{2+3(k-1)}$. We have that $|xy|=3\leq p=12$, $|y|=3\geq1$ and for all $n\geq0$ we have $xy^nz=a^0a^{3n}a^{2+3(k-1)}=a^{2+3(n+k-1)}$ in $L$, since $n+k-1\geq k-1\geq0$.

So, the minimum pumping length of $L$ seems to be $12$. Any larger value would also work in this case.
> 1 votes

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


title: Graph coloring variation

text:
# Question
Title: Graph coloring variation
Are there variations of the classic graph coloring problem that the number of neighbors in the same color is limited but not zero (in the original problem the limit is zero)?

Problem: Given a graph $G$ and two integers $c$ and $p$, is it possible to color the vertices of $G$ with $c$ colors such that for every vertex $v$ with color $\text{color}(v)$,

$$| \\{ w \in N\_G(v) \mid \text{color}(v) = \text{color}(w) \\} | \leq p?$$

# Answer
The definition you are looking for is "defective coloring":

> A $(k, d)$-coloring of a graph G is a coloring of its vertices with k colours such that each vertex v has at most d neighbours having the same colour as the vertex v. We consider k to be a positive integer (it is inconsequential to consider the case when k = 0) and d to be a non-negative integer. Hence, $(k, 0)$-coloring is equivalent to proper vertex coloring.
>
> The minimum number of colours k required for which G is $(k, d)$-colourable is called the $d$-defective chromatic number, $\chi \_{d}(G)$.
> 7 votes

# Answer
I'm not familiar with this variant, but it is still NP-complete for any fixed $p$.

Given a graph $G$ and an integer $c$, connect to each vertex $v$ a clique $C\_v$ on $(p+1)c-1$ vertices.

If the original graph $G$ has a valid coloring $\chi$, then we can color the clique $C\_v$ as follows: the color $\chi(v)$ appears $p$ times, and all other colors appear $p+1$ times. You can check that every vertex has exactly $p$ neighbors of the same color.

Conversely, suppose that the new graph has a coloring $\chi$ in which each vertex has at most $p$ neighbors of the same color. This is only possible if each color in $C\_v$ appears at most $p+1$ times, and so some color $\chi'(v)$ appears $p$ times, and the rest appear $p+1$ times. This implies that $\chi'(v) = \chi(v)$ (since otherwise $v$ would have $p+1$ neighbors with the same colors), and furthermore that $\chi$ restricted to the original vertices is a valid coloring (in the usual sense).
> 6 votes

---
Tags: graphs, np-complete, terminology, colorings
---


# Question
Title: How do you find all integers in a sorted array of size n that appear n/k times?
I try to find the solution to this problem: How do you find all integers in a sorted array of size n that appear n/k times in **less** than O(klogn) time?

I could only find this question, where O(klogn) solution was provided.

# Answer
> 3 votes
Let's start with the case $k = 2$, and assume that the algorithm is comparison-based.

I claim that any algorithm that finds even a single element appearing $n/2$ times must know an index $i$ such that $A\[i+1\] = A\[i+n/2\]$. Indeed, suppose that this is not the case, and let us assume for simplicity that the entries of $A$ are real numbers. Let us say that the algorithm known the following values: $$ A\[i\_1\] = \cdots = A\[j\_1\] \< A\[i\_2\] =\cdots = A\[j\_2\] \< \cdots $$ It is consistent with the algorithm's knowledge that $A\[i\_1-1\] \< A\[i\_1\] \< A\[j\_1+1\]$ and so on, and with a little effort we can arrange that there is no element appearing $n/2$ times.

Consider now the $n/2+1$ arrays of the following form: there is a run of $n/2$ many $0$s starting at some position $j \in \\{1,\ldots,n/2+1\\}$, and the rest of the elements are unique. In each such array, there is a unique choice for the index $i$ mentioned above. Thus the decision tree representing the algorithm has at least $n/2+1$ leaves, and so it must have depth $\Omega(\log n)$.

---

In the general case, the algorithm should know an index $i$ such that $A\[i+1\] = A\[i+n/k\]$ for each element which is output. We can partition the array into $k/2$ parts of size $2n/k$, and consider $(n/k+1)^k$ examples as before, where the $r$th element appearing $n/k$ times is in the $r$th part. This gives a lower bound of $\Omega(k\log(n/k))$, matching your upper bound for nearly all values of $k$.

(The algorithms can probably be slighly improved to give a matching upper bound.)

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


# Question
Title: Returning random integer from interval based on last result and a seed
Suppose we have an interval of integers \[a, b\]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are explored, the function would start to return the same first random sequence again, in the same order.

Example: a=1, b=5

```
3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

```

This would be easy to achieve by shuffling an array of all elements between a and b, and repeating it once the array is finished. However, this would take too much memory space, and this is not suitable for my case (I might have millions of elements).

Instead, the function I'd like to have would be more or less like this:

```
f(a, b, n, seed) -> n+1

```

Where:

```
a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

```

The trick is knowing some way to get a non-repeated number from the interval based only on the element returned before and the seed. In the end, it would behave like a circular list randomized at its initialization, but without using memory space.

# Answer
I suggest you pick a random permutation on the range $\[a,b\]$, i.e., a bijective function $\pi:\[a,b\]\to \[a,b\]$. Then, maintain a counter $i$ that starts at $i=a$; at each step, output $\pi(i)$ and then increment $i$ (wrapping around so that $b+1$ becomes $a$).

There are standard methods for generating such a random permutation in the cryptography literature: look up format-preserving encryption. The seed is the cryptographic key. You will be able to compute $\pi(i)$ in $O(1)$ time and $O(1)$ space, so this should be very efficient and avoid the need for a lot of storage.

If you insist that the next output should be a function of the previous output, you can let $g(i)=i+1$ (except that $g(b)=a$), then let $f(i)=\pi^{-1}(g(\pi(i))$, where $\pi$ is a random permutation chosen as above. This will then give you a random cycle that iterates through the elements of $\[a,b\]$ in a random order. The outputs are the sequence $f(a),f(f(a)),f(f(f(a))),\dots$.
> 6 votes

---
Tags: arrays, randomized-algorithms, memory-management, subsequences, intervals
---


# Question
Title: Is my reasoning wrong that $PSPACE$ should not equal $EXPTIME$?
It's impossible for a problem to require exponential space without being exponential-time.

1. Consider that if an $EXPSPACE~~complete$ problem can be solved in $2^n$ time. **It will now fall into the class $EXPTIME$.**
2. Then $EXPSPACE~~complete$ problems are in $EXP$ **if they can be solved in $2^n$ time**. This means they can reduce into $EXP~~complete$ problems and vice versa.

To me, this should be easy to write a proof that $EXPTIME$ = $EXPSPACE$.

My intuition tells me that if $Exptime$ = $Expspace$; then $PSPACE$ != $EXPTIME$,

**Because $PSPACE$ already is not equal to $EXPSPACE$.**

## Question

As an amateur, what would make this reasoning be wrong or right?

# Answer
> 2 votes
I did not understand the first part of the question, but just so you know, its unknown whether $EXPTIME=EXPSPACE$ or not. What is known is that $EXPSPACE\subseteq \bigcup \_cDTIME(2^{2^{n^c}})$ from the relations shown here.

The second part of the question: ***If*** $EXPTIME=EXPSPACE$ then $PSPACE\neq EXPTIME$, is absolutely correct: by the space hierarchy theorem, $PSPACE\subsetneq EXPSPACE$ and therefore $PSPACE\subsetneq EXPTIME$ as $EXPSPACE=EXPTIME$ (by our assumption).

---
Tags: complexity-theory
---


# Question
Title: Checking equality of integers: O(1) in C but O(log n) in Python 3?
Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$.

```
def is_equal(a: int, b: int) -> bool:
  return a == b

```

```
int is_equal(int a, int b) {
  return a == b;
}

```

But consider what is happening under the surface. Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. In either case this scan is $O(b)$ where $b$ is the number of bits. Since integers have a constant size in bits in C, this is simply $O(1)$.

*EDIT: C doesn't compare bit-by-bit see this answer*

In Python 3 however, integers do *not* have fixed size and the scan remains $O(b)$ for the number of bits in the input, or $O(\log a)$ where $a$ is the value of the input in base 10.

So if you're analyzing code in Python, any time you compare two integers, you are embarking on a surprisingly complex journey of $O(\log n)$ with respect to the base 10 value of either number.

For me this raises several questions:

1. Is this correct? I haven't seen anyone else claim that Python compares ints in log time.
2. In the context of conducting an interview, should you notice or care if a candidate calls this $O(1)$?
3. Should you notice or care about this distinction in the real world?

*EDIT: It is easily verified (and intuitive) that Python cannot compare arbitrarily large ints in constant time. So a better way to ask question 1 above might be "What (if any) is the justification for calling this operation $O(1)$? Because it's pragmatic? Conventional? Implied by the RAM model?*

# Answer
> 0 votes
TL;DR: There is a CS convention of describing this type of operation as $O(1)$ which happens to break down in extreme cases for Python. These cases are *extremely* rare, so to break with the convention of $O(1)$ has negative utility. This kind of pragmatism is normal in big $O$.

There are a lot of very good responses to this question and I encourage you to read them. But I don't think any one of them fully answer my questions. So here's a synthesis.

> Is this correct? I haven't seen anyone else claim that Python compares ints in log time.

This is surprisingly nuanced. It is **true** that Python compares very large ints in $O(\log n)$ runtime. But is it *correct* to describe this operation as $O(\log n)$?

Ultimately I'm most persuaded by this take from @TomvanderZanden:

> If you said the C or Python version was $O(1)$ any interviewer should be perfectly happy. If you said it (the Python version) was $O(\log n)$ they would probably still be happy, but think you are a rather pedantic person who doesn't follow normal conventions.

and

> If I was an interviewer, I would care whether you know the real-world limitations of what you are doing and know what theoretical concerns matter when and that you bring them up if and only if appropriate.

However I'm not accepting that as the answer because I think the first paragraph is currently misleading (happy to change).

Ultimately this argument is pragmatic. By the strict definition of big $O$ Python int comparison is still verifiably $O(\log n)$. But it is not useful to treat it that way, so you shouldn't. I would add that to be strict about big $O$ is to miss the point of big $O$ analysis.

# Answer
> 25 votes
> Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit.

Not quite. C `int`s are machine-word-sized and compared with a single machine instruction; Python `int`s are represented in base $2^{30}$ (see e.g. https://rushter.com/blog/python-integer-implementation/) and compared digit-by-digit in that base. So the relevant base of the logarithm is $2^{30}$.

If *at least one* of numbers can be bounded by $2^{30d}$ for *any* fixed $d$, the comparison is $O(1)$ (because the number of digits is compared first), and if they can't, other operations are likely of much more concern than equality comparison. So in practice I'd say it's very unlikely to matter and if it does you'll know (and would be using not `int`s but something like the GNU Multiple Precision Arithmetic Library in C as well).

# Answer
> 16 votes
Complexity is defined relative to a computation model. P and NP, for example, are defined in terms of Turing machines.

For comparison, consider the word RAM model. In this model, memory is divided into words, words can be accessed in constant time, and the size of the problem can be represented using $O(1)$ words.

So, for example, when analysing a comparison-based sort operation, we assume that the number of elements $n$ can be stored in $O(1)$ words, so it takes constant time to read or write a number between $1$ and $n$.

# Answer
> 9 votes
> Is this correct? I haven't seen anyone else claim that Python compares ints in log time.

No (and a little yes). Consider the following thought-provoking (but not really true) claim: A computer can only have a finite amount of memory (bounded by the number of atoms in the universe), so the Python version is also $O(1)$.

The problem is that we are trying to make a statement about asymptotics (pertaining to what happens at infinity) about a finite state machine (a computer). When we are analyzing the complexity of code, we don't actually analyze the code itself as it would run on a computer, we are analyzing some idealized model of the code.

Suppose I asked you to analyze a sorting algorithm written in C. You might state it uses ints to index the array, so it could only ever sort an array of size up to $2^{31}-1$. Yet, when we analyze such a piece of code, we pretend that it could handle arbitrarily large arrays. Clearly, we are not saying C integer comparison is $O(1)$ *because* it can only handle 32-bit numbers.

> In the context of conducting an interview, should you notice or care if a candidate calls this O(1)?

Usually, not. Suppose I am conducting an interview and ask you to write a C or python computer program that counts the number of female employees appearing in the employee database.

It would be *incredibly* pedantic if I complained your C program was incorrect because it could only count up to $2^{31}-1$.

We generally assume that numbers are small enough that they can fit within one word/integer. We assume addition (or any other number operation) can be done in $O(1)$, because it would be very annoying to have to write $O(\log n)$ everywhere and it would just make everything unreadable even though $\log n$ is so small it doesn't really matter anyways.

If you said the C or Python version was $O(1)$ any interviewer should be perfectly happy. If you said it (the Python version) was $O(\log n)$ they would probably still be happy, but think you are a rather pedantic person who doesn't follow normal conventions.

> Should you notice or care about this distinction in the real world?

Yes! It starts to matter when numbers get so large the assumption they are small is violated. Let's say you are interviewing for Google and they asked you to compute the number of search queries done by female users in the past year. The interviewer would be quite justified to complain if you wrote a C program using ints.

You could switch to using longs and still be justified in calling it $O(1)$, and similarly, calling the Python version $O(1)$ is also justified. The $O(1)$ v.s. $O(\log n)$ thing only starts to matter when the numbers get very long. For instance, if your task is to write a program that computes digits of $\pi$ or some similar task. If you wrote a Python program for this task and didn't mention the peculiarities of complexity when asked, the interviewer would care.

If I was an interviewer, I would care whether you know the real-world limitations of what you are doing and know what theoretical concerns matter when and that you bring them up if and only if appropriate.

**When should you care?**

So far, I've been a bit vague about "large" and "small" numbers. In the commonly used RAM model, you're allowed to assume that integer operations can be done in $O(1)$ on numbers that have at most $O(\log n)$ bits (where $n$ is the length of the input). The justification for this assumption is that if we have an input of length $n$, the pointers/indices in our programming language should be long enough to be able to address the entire input space. So, in the RAM model, if the input is binary number of $n$ (binary) digits, the complexity of checking equality is $O(\frac{n}{\log n})$ since we can check the equality of one group of $O(\log n)$ bits in one $O(1)$ operation.

# Answer
> 6 votes
Although this may seem like a trivial point, your first sentence is incorrect. *The functions are not equivalent*. To make them equivalent, the C function should use GMP (or similar) to implement arbitary-precision arithmetic. Now, the reason this observation is not trivial, is that the extent to which it's reasonable to say that the two are equivalent, is precisely the extent to which it's reasonable to say that the Python code is constant-time! That is, if we're going to ignore that Python's integers are bignums, we can (and should) consistently treat them as fixed size.

Analogously, consider the C function `int is_equal(char a, char b) { return a == b; }` and the Python function `def is_equal(a: str, b: str) -> bool: return a == b`. It is more obvious now that the functions are not equivalent, but the reason for that is exactly the same as the reason yours aren't. We just expect to see massive strings in Python all the time, but don't really expect massive ints even though of course we know they are possible. So, most of the time we ignore the fact that Python's integers are big, and we analyse as if they are fixed-size. In the rare cases where we care about the timings of bignum operations, you can use the "real" complexities. And, of course, also use GMP in your C code.

All this is to say: although you didn't realise it, you already know the answer to your restated version of your question at the end, and the answer is, "the same justification by which you described those functions as equivalent". Python is unusual in not having a fixed-size integer type (well, not one that people commonly use: it's possible to write one of course, and there's one in `numpy`). But as a matter of pragmatism, we don't want this to prevent us doing the "usual" complexity analysis of algorithms that crunch integers, and getting the "usual" answers. It is rarely necessary to provide the caveat that if we pass it a couple of 10GB integers that are nearly equal, it might take a little while to compare them.

In some cases you could formalise this (if you really need to) by saying that you're restricting your analysis to small integers. Then, you might consider complexity of some algorithm in terms of the size of some array of integers, treating all arithmetic operations as O(1). If you're considering algorithms which really are linear or worse in the magnitude of the integer, then you could formalise it by saying you're going to ignore the log-factor, since all you really care about is whether the complexity is closer to linear or quadratic, because O(n log n) is as good as linear for your purposes. Almost all the time, though, you don't need to formalise the complexity of algorithms *in Python*. If you've reached the point of specifying a programming language, you're not really doing abstract computer science any more ;-)

> In the context of conducting an interview, should you notice or care if a candidate calls this $O(1)$?

Depends on interview for what, I suppose, but as a software professional, working primarily in Python for the last 10 years, I would not ask that in an interview. If I asked a question which had the complexity of integer comparison hidden inside it (like, I dunno, "what's the complexity of this sort algorithm?"), then I'd accept an answer which ignored the whole issue. I'd also accept one which addressed it. I do think it is worth understanding and computing complexity as part of practical programming, I just don't consider it that important *for programming* to be very careful about formally stating that you're talking about reasonable-sized integers.

I would also never ask a question in which I want the candidate to offer the information that Python integers are arbitrary-precision, when it's not obviously relevant to the the question for some reason to do with the data involved. If the question implies that the numbers involved can go higher than 264 then in a C interview I'd want the candidate to notice that this is a problem they need to deal with, and in a Python interview I'd want the candidate to know that it isn't, but I wouldn't expect them to go out of their way to state it. There isn't time in an interview to state every little fact that makes something a non-problem.

If I wanted to check understanding of complexity in an interview, then mostly likely I'd start by asking for some code for some problem where there's a really straightforward "naive" solution with poor complexity, and at least one less straightforward solution with decent complexity using well-known techniques. If the candidate offers the naive solution, then you can ask what the complexity is and how they'd modify the code to improve it. If the candidate offers a better solution then you can describe the naive solution, point out how few lines of code it is, and ask what's wrong with it (perhaps by asking, "if you were reviewing someone's code and they gave you this, what would you say about it"?). For most practical purposes all you care about is whether they can tell the difference between linear, quadratic, and worse-than-quadratic. O(n log n) also appears, but mainly because of sorting or data structures where you're talking about complexity in terms of the number of comparisons. The cost of each comparison is usually considered irrelevant, because the algorithm designer usually has no control over it (it's provided by the user of the algorithm or data structure).

In the astonishingly unlikely event that I was the interviewer for a position as a CS academic covering arbitrary-precision arithmetic, then certainly I would want candidates to know the complexities of various algorithms for various operations, and indeed to know the state of the art for the non-trivial ones.

# Answer
> 0 votes
*EDIT*: Based on the comments, I've decided to preface my answer with a correction. I used big-O notation to talk about an operation. However, this notation is really applied to a complexity class, which gets defined by a *metric* on that operation. For example, it may be "the number of additions required in the worst case." or it might be "the number of seconds required in the average case." Both can use big-Oh notation to describe a *bound* on the series (big-O can be used on any sequence, not just runtime metrics).

Technically the meaning of O(1) or O(log n) has no meaning unless you specify the metric. However, colloquially speaking, when computer scientists talk about a sorting algorithm being O(n log n) without specifying the metric, they are implicitly talking about the worst case behavior in "number of instructions". This is the meaning I used in my answer below. Many commenters pointed out that this was not formally correct. However, from your question's wording, it appears you are using this implied metric, and I used it below. Purists are free to substitute in the above clarification in any sentences which use big-O notation without reference to a metric.

---

> Is this correct? I haven't seen anyone else claim that Python compares ints in log time. Python does indeed have an arbitrary precision integer format. However, we have to make a fair comparison here. If we consider the subset of integers on the bound of $\[0,2^{64}\]$, we find that the Python operation is constant time.

What you are seeing is one of the limits as to measuring computational complexity using big-oh notation. It describes what happens as n approaches infinity, but does not necessarily do a good job of comparing the behavior for smaller numbers. We see this famously in matrix multiplication algorithms. There are some algorithms which are more efficient in a big-oh sense, but are actually slower in practice until you get to gargantuan matrices.

> In the context of conducting an interview, should you notice or care if a candidate calls this O(1)?

Depends on what you are hiring them for. For the vast majority of jobs, calling it O(1) should be fine. Indeed, it is how we tend to teach it in school. If you wanted to turn it into a useful opportunity to learn about your candidate, you might ask them why they think addition is constant time (to which the answer is that the model they used to determine big-oh assumed it... which is a valid answer)

If you are hiring someone to look for things like exploits in your code, you may want to push futher. A bignum produced by your own code is one thing, but is the user allowed to input the number of their own choosing? If so, they may be able to create timing attacks and DOSs using the fact that this addition can be terribly slow. Detecting this risk might be part of their job.

> Should you notice or care about this distinction in the real world?

Practically speaking: no. Not until you acutally run into it, and fix the issue in debug. Python does a *lot* of things that are "generally safe" and are very efficient. This is why it has taken over as one of the most popular languages in the world.

For an equivalent situation: how fast is `x.y` in Python? We think of it as O(1), but there's actually a hash lookup there. That hash lookup uses a known probing mechanism, and the resulting lookup is actually O(n). You'll never see this in normal code. But in code where an adversary gets to fill your dictionary with their own content, they can intentionally craft keys that collide in this way.

# Answer
> 0 votes
I have never encountered a text that treated "regular" integer operations as anything besides constant time, with the implicit assumption that the size had some reasonable finite upper bound (for example 64 bits). Perhaps it would be more accurate to state the assumption, but to a CS audience, I think it is implicit.

Doing so would introduce a lot of complexity into discussions of essentially unrelated topics. Bigint implementations typically are not implemented bit by bit, but in base-(machine word size), so that O(b) \> O(1) problem only kicks in for fabulously large numbers.

Personally while interviewing someone, I might appreciate the rigor and breadth of knowledge associated with knowing Python integers were arbitrary length, but anything beyond stating the assumption that all math is O(1) would feel extremely pedantic. If the analysis started getting too far off-topic with arithmetic, and wasted time, I would consider this a bad candidate.

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


# Question
Title: Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $
I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language:

$$ \\{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \\} $$

I quickly made a CFG that represents that language (or so I believe):

$$ S \to 0S1 \hspace{0.2cm} | \hspace{0.2cm} A \\ A \to 1A0 \hspace{0.2cm} | \hspace{0.2cm} \epsilon $$

The problem is that I began to think if the Pumping Lemma would hold (it should since I have a CFG for the Language, so it must be a CFL).

(Having the Pumping Lemma in mind) I chose a word, w = $ 0^{n}1^{n}0^{n}1^{n} $. I immediately stopped because this word will not pass the Pumping Lemma (it can be used to demonstrate that $ \\{ ww \hspace{0.2cm}| \hspace{0.2cm} w \in \\{0,1\\}^{\*}\\}$, the language of duplicated words, is not a CFL, I have done it before)

Now I'm stuck with a Pumping Lemma that fails, and a CFG that produces the language and don't now what to do. I tried to come up with a word that the grammar couldn't produce and failed, I tried to invalidate the PL but failed (there are no restrictions that tells that the word cannot have all segments of the same size, so $w$ is in the language).

As far as I know If the PL holds, the language doesn't have to be a CFL, but if it fails is absolutely unquestionable that the Language is not a CFL.

What I'm I missing?

# Answer
> 2 votes
$\\{ww\mid w\in\\{0,1\\}^\*\\}$ not being context-free does not imply every subset is also not context-free. In this case, $0^n1^n0^n1^n$ passes the pumping lemma, since it can be written as follows $0^p1^p0^p1^p=0^p1^{p-1}1^n0^n0^{p-1}1^p$.

---
Tags: context-free, proof-techniques, pumping-lemma, correctness-proof
---


# Question
Title: Proof of Co-Problem being in NP if Problem is in NP using negated output
Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof?

Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is at least in $NP$ because the following algorithm can always be given:

```
Co-P(J):
    bool res = P(J)
    return !res

```

Where $Co-P(J)$ is the algorithm solving $Co-P$ and $P(J)$ is the nondeterministic polynomial algorithm solving P.

Why is this not correct?

# Answer
> 1 votes
A problem is in NP if for all instances where the answer is “Yes” you can guess a hint and verify it in polynomial time. Nothing at all is said for instances where the answer is “No”. That distinction between “Yes” and “No” answers is essential.

What your proof attempt shows is that if a problem X is in NP, then the co-problem “Does X have the answer ‘No’” is in co-NP, as we would expect, and says nothing about NP.

# Answer
> 0 votes
The problem with your proof is the fact that a TM for $NP$ would be non-deterministic.

The non-determinism allows the machine to split up into branches of computation, and your machine will accept iff **there is a branch** in which the computation accepted.

In order to know whether on an input the machine did not accept, you would have to know whether **for every branch** it did not accept.

Switching the result from a non-deterministic TM is pretty much like swapping between $\exists$ and $\forall$ and checking $\forall$ is a totally different problem than checking $\exists$.

I hope this made sense to you! If not, try to think of $NP$ as polynomial verifiable languages, i.e languages with a machine $M(x,w)$ where $w$ is a "witness" describing the $\exists$, and then calling a routine for an NP problem means calling $M$ with the correct "witness" - but to know that the input $x$ is not in the language means to know that every "witness" is not a correct one

---
Tags: np-complete, np, decision-problem
---


# Question
Title: Enumerate all non-isomorphic graphs of a certain size
I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ vertices. How can I do this?

More precisely, I want an algorithm that will generate a sequence of undirected graphs $G\_1,G\_2,\dots,G\_k$, with the following property: for every undirected graph $G$ on $n$ vertices, there exists an index $i$ such that $G$ is isomorphic to $G\_i$. I would like the algorithm to be as efficient as possible; in other words, the metric I care about is the running time to generate and iterate through this list of graphs. A secondary goal is that it would be nice if the algorithm is not too complex to implement.

Notice that I need to have at least one graph from each isomorphism class, but it's OK if the algorithm produces more than one instance. In particular, it's OK if the output sequence includes two isomorphic graphs, if this helps make it easier to find such an algorithm or enables more efficient algorithms, as long as it covers all possible graphs.

My application is as follows: I have a program that I want to test on all graphs of size $n$. I know that if two graphs are isomorphic, my program will behave the same on both (it will either be correct on both, or incorrect on both), so it suffices to enumerate at least one representative from each isomorphism class, and then test the program on those inputs. In my application, $n$ is fairly small.

Some candidate algorithms I have considered:

* I could enumerate all possible adjacency matrices, i.e., all symmetric $n\times n$ 0-or-1 matrices that have all 0's on the diagonals. However, this requires enumerating $2^{n(n-1)/2}$ matrices. Many of those matrices will represent isomorphic graphs, so this seems like it is wasting a lot of effort.
* I could enumerate all possible adjacency matrices, and for each, test whether it is isomorphic to any of the graphs I've previously output; if it is not isomorphic to anything output before, output it. This would greatly shorten the output list, but it still requires at least $2^{n(n-1)/2}$ steps of computation (even if we assume the graph isomorphism check is super-fast), so it's not much better by my metric.
* It's possible to enumerate a subset of adjacency matrices. In particular, if $G$ is a graph on $n$ vertices $V=\\{v\_1,\dots,v\_n\\}$, without loss of generality I can assume that the vertices are arranged so that $\deg v\_1 \le \deg v\_2 \le \cdots \le \deg v\_n$. In other words, every graph is isomorphic to one where the vertices are arranged in order of non-decreasing degree. So, it suffices to enumerate only the adjacency matrices that have this property. I don't know exactly how many such adjacency matrices there are, but it is many fewer than $2^{n(n-1)/2}$, and they can be enumerated with much fewer than $2^{n(n-1)/2}$ steps of computation. However, this still leaves a lot of redundancy: many isomorphism classes will still be covered many times, so I doubt this is optimal.

Can we do better? If I understand correctly, there are approximately $2^{n(n-1)/2}/n!$ equivalence classes of non-isomorphic graphs. Can we find an algorithm whose running time is better than the above algorithms? How close can we get to the $\sim 2^{n(n-1)/2}/n!$ lower bound? I care primarily about tractability for small $n$ (say, $n=5$ or $n=8$ or so; small enough that one could plausibly run such an algorithm to completion), not so much about the asymptotics for large $n$.

Related: Constructing inequivalent binary matrices (though unfortunately that one does not seem to have received a valid answer).

# Answer
> 25 votes
Probably the easiest way to enumerate all non-isomorphic graphs for small vertex counts is to download them from Brendan McKay's collection. The enumeration algorithm is described in paper of McKay's \[1\] and works by extending non-isomorphs of size n-1 in all possible ways and checking to see if the new vertex was canonical. It's implemented as `geng` in McKay's graph isomorphism checker `nauty`.

\[1\]: B. D. McKay, Applications of a technique for labelled enumeration, Congressus Numerantium, 40 (1983) 207-221.

# Answer
> 5 votes
These papers might be of interest.

"On the succinct representation of graphs", Gyorgy Turan, Discrete Applied Mathematics, Volume 8, Issue 3, July 1984, pp. 289-294 http://www.sciencedirect.com/science/article/pii/0166218X84901264

"Succinct representation of general unlabelled graphs", Moni Naor, Discrete Applied Mathematics, Volume 28, Issue 3, September 1990, pp. 303-307 http://www.sciencedirect.com/science/article/pii/0166218X9090011Z

They present encoding and decoding functions for encoding a vertex-labelled graph so that two such graphs map to the same codeword if and only if one results from permuting the vertex labels of the other.

Moreover it is proved that the encoding and decoding functions are efficient.

The first paper deals with planar graphs. In the second paper, the planarity restriction is removed.

EDIT: This paper might also be relevant:

Graph Isomorphism in Quasi-Polynomial Time, Laszlo Babai, University of Chicago, Preprint on arXiv, Dec. 9th 2015 http://arxiv.org/pdf/1512.03547v1.pdf

Babai's announcement of his result made the news: https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem

But perhaps I am mistaken to conflate the OPs question with these three papers ? The OP wishes to enumerate non-isomorphic graphs, but it may still be helpful to have efficient methods for determining when two graphs ARE isomorphic ?

# Answer
> 4 votes
I propose an improvement on your third idea: Fill the adjacency matrix row by row, keeping track of vertices that are equivalent regarding their degree and adjacency to previously filled vertices. So initially the equivalence classes will consist of all nodes with the same degree.
When a newly filled vertex is adjacent to only some of the equivalent nodes, any choice leads to representants from the same isomrphism classes. So we only consider the assignment, where the currently filled vertex is adjacent to the equivalent vertices with the highest number (and split the equivalence class into two for the remaining process).

I think (but have not tried to prove) that this approach covers all isomorphisms for $n\<6$.
For larger graphs, we may get isomorphisms based on the fact that in a subgraph with edges $(1,2)$ and $(3,4)$ (and no others), we have two equivalent groups of vertices, but that isn't tracked by the approach. (It could of course be extended, but I doubt that it is worth the effort, if you're only aiming for $n=6$.)

A naive implementation of this algorithm will run into dead ends, where it turns out that the adjacency matrix can't be filled according to the given set of degrees and previous assignments. It may be worth some effort to detect/filter these early. Some ideas:

* If the sum of degrees is odd, they will never form a graph
* Fill entries for vertices that need to be connected to all/none of the remaing vertices immediately.

# Answer
> 4 votes
There is a paper from the early nineties dealing with exactly this question:

Efficient algorithms for listing unlabeled graphs by Leslie Goldberg.

The approach guarantees that exactly one representant of each isomorphism class is enumerated and that there is only polynomial delay between the generation of two subsequent graphs.

The methods proposed here do not allow such delay guarantees: There might be exponentially many (in $n$) adjacency matrices that are enumerated and found to be isomorphic to some previously enumerated graph before a novel isomorphism class is discovered.

# Answer
> 1 votes
You also may see the paper

A new formula for the generating function of the numbers of simple graphs, Comptes rendus de l’Acade'mie bulgare des Sciences, Vol 69, No3, pp.259-268

http://www.proceedings.bas.bg/cgi-bin/mitko/0DOC\_abs.pl?2016\_3\_02

---
Tags: algorithms, graphs, data-compression, graph-isomorphism
---


# Question
Title: How to leverage the fact that I'm solving 1000's of very similar SMT instances?
I have a core SMT solver problem consisting of 100,000 bit-vector array clauses, and one 10000-dimensional bit-vector array. Then, my program takes as input k \<\< 100,000 new clauses, and adds them to the core SMT problem. My goal is, for any input of k clauses, to solve the entire problem.

Is there any static optimization or learning I could do on the core problem in order to find a better way to solve each of its siblings? For instance, is there some property of the graph of bit-vector variables being constrained in each clause that I could use as a heuristic for solving the specific instances?

Thanks!

# Answer
Some SAT solvers and SMT solvers offer an interface that lets you push clauses, and then later pop/retract them and push some new ones. You could explore to see whether this offers a speedup in your situation. There are no guarantees, and the only way to tell is to try it.
> 3 votes

---
Tags: optimization, sat-solvers, smt-solvers, static-analysis
---


# Question
Title: How to find the size of gaps between entries in an array so that the first and last element of the array is filled and the gaps are all of equal size?
I have an array a of n entries. I need to place a token on the first and last position of that array, so `a[0] = 1` and `a[n-1] = 1`.

I now want to place additional tokens into that array with a distance inbetween each index i where `a[i] = 1` that is greater than 2 (so placing a token on every index is invalid as well as alternating using and not using an entry is invalid). Phrazed differently: I want that `sum(a) < n/2` . The gap inbetween each token should be the same, so say with an array of size 16,

`a[0] = 1, a[3] = 1, a[6] = 1, a[9] = 1, a[12] = 1, a[15] = 1`

would be a solution with a gap size of 2 (distance of 3).

How do I find all gap sizes that are possible to fill said array with the given constraints?

Imagine a street inbetween two crossroads where a lamppost should be placed on each crossroad and then additional lampposts should be placed equidistant to each other and for some reason only natural number distances are allowed.

(The actual problem I want to solve is where to place Sea Lanterns in my Minecraft Project so do not disregard this problem as an assignment question I want a solution for.)

# Answer
> 2 votes
If I understand your problem correctly, the tokens (lanterns) can be placed every $x$ blocks (starting from $0$) if and only if $x\>2$ is a divisor of $n-1$.

For example, if the array has $n=31$ elements the valid values of $x$ are $3,5,6,10,15,$ and $30$.

---
Tags: arrays
---


# Question
Title: How to conceive a Turing machine that is the intersection of the languages of two Turing machines?
We have $ M = (Q,Σ,Γ,δ,q\_0,q\_a,q\_r) $ and $ M′= (Q′, Σ , Γ′, δ′,q\_0′,q\_a′,q\_r′)$.

We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don't have much more information than this. Anything to get started would be appreciated.

# Answer
What you ask might not be possible in general. If $L(T)$ denotes the set of words $x$ for which $T(x)$ accepts, and you do not have the additional assumption that $M$ and $M'$ recognize $L(M)$ and $L(M')$, respectively, then you could choose:

* $M$ as a Turing machine that takes another Turing machine $T$ as input and accepts if and only if $T$ halts on empty input. (Notice that such a Turing Machine $M$ exists).
* $M'$ as a Turing Machines that recognizes $\Sigma^\*$.

Then, there is no Turing Machine $T$ that recognizes $L(M) \cap L(M') = L(M)$ since $T$ would solve the halting problem.

On the other hand, if you are fine with a Turing machine that accepts $L(M) \cap L(M')$ **or** if you have the additional assumption that $M$ and $M'$ recognize $L(M)$ and $L(M')$, respectively, your problem is solved by a Turing machine that, on input $x$, operates as follows:

* Simulate $M(x)$ until it halts (possibly never).
* If $M(x)$ rejects, reject.
* Simulate $M'(x)$ until it halts (possibly never).
* If $M'(x)$ rejects, reject.
* Accept.
> 2 votes

---
Tags: turing-machines
---


title: removing indirect left recursion

text:
# Question
Title: removing indirect left recursion
I want to remove indirect left recursion from these rules:

```
    S-->TU,
    T-->US|b,
    U-->ST|a

```

I don't know if I can implement the algorithm correctly. My assumption is to make it like this:

```
S-->TU, T-->U'b, U'b-->U'a

```

Is this correct?

# Answer
> 0 votes
It's tedious... I hope I didn't make a mistake...

```
S->TU
T->US|b
U->ST|a

1.
S->TU
T->U(TU)|b
U->(TU)T|a

2.
S->TU
T->aTU|(TUT)TU|b
U->bUT|(UTU)UT|a

3. * is regex for "repeated 0 or more times"
S->TU
T->aTU|T(UTTU)*|b
U->bUT|U(TUUT)*|a

4.
S->TU
T->aTU|aTUX|bX|b
U->bUT|bUTY|aY|a

X->UTTUX|UTTU
Y->TUUTY|TUUT

```

By substitution of all possibilities of T and U you can remove the non-Terminals at the front of the expressions for X, Y and S.

# Answer
> 0 votes
No. The first language is non empty (e.g., it contains the word "ba"), while the second language is empty.

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


title: Is x86-64 is just an alias of EM64T?

text:
# Question
Title: Is x86-64 is just an alias of EM64T?
I was reading a book which describes a historical perspective:

> Pentium 4E (2004, 125 M transistors). Added hyperthreading, a method to run two programs simultaneously on a single processor, as well as EM64T, Intel’s implementation of a 64-bit extension to IA32 developed by Advanced Micro Devices (AMD), which we refer to as x86-64

I'm a little bit confused here, here are my two questions:

1. Does it mean that 'x86-64' is just an alias of 'EM64T'?
2. Is IA32 developed by AMD? Isn't IA32 designed by Intel and first implemented in the 80386 microprocessor in 1985? See Wikipedia.

# Answer
> 1 votes
> Q1-does it mean that x86-64 is just an alias name of EM64T?

The *original* name for the architecture is *AMD64*.

That is also the *marketing name* that AMD uses for that architecture.

When Intel licensed it from AMD, they first called the feature *CT*, then *IA-32e*, then *EM64T*, and most recently *Intel 64*. Those are Intel's *marketing names*. Note that Intel 64 contains extensions on top of AMD64 as well.

*x64* is *not* an official name. It is a *marketing name* created by Microsoft in order to refer to both Intel's and AMD's (as well as other vendors') implementations without using the name of one of the two main competitors.

*x86-64* is *not* an official name. It is a *marketing name* used by many vendors in order to refer to both Intel's and AMD's (as well as other vendors') implementations without using the name of one of the two main competitors.

`x86_64` is the GNU Autotools architecture designation used in tools such as Autoconf, Automake, and GCC.

IA-32 is, I believe, a term that Intel only introduced after they started working on IA-64. Until then, the architecture was colloquially known as *x86*, but did not actually have a name.

The bottom line is that you can *mostly* use the terms AMD64, IA-32e, x86-64, and x64 interchangeably, and people will probably understand what you are talking about. But, the official name for the architecture is AMD64, but that can also refer to AMD's specific implementation of that architecture (which may have AMD-specific extensions). Whereas IA-32e is Intel's specific implementation of the AMD64 architecture, which may have Intel-specific extensions.

> Q2- And is IA32 developed by AMD?

No, it isn't.

> isn't IA32 designed by Intel and first implemented in the 80386 microprocessor in 1985?

Yes, it is, although the name IA-32 came later.

---
Tags: cpu
---


title: Complexity analysis of m!/n!(m-n)!

text:
# Question
Title: Complexity analysis of m!/n!(m-n)!
Given the runtime of an algorithm to be m!/(n!\*(m-n)!) That is mCn, where both m and n are variables, is the complexity factorial or polynomial? Or is it something else?

Please elaborate.

Thanks

# Answer
The growths could be linear or constant depending on the relationship between $m$ and $n$ as they grow large. For example, if $n$ grows with $m$ as in $m=n+1$, then $\binom{m}{n}=\binom{n+1}{n}=n+1$.

Now, if you are interested in the maximum growth, then the binomial coefficients $\binom{m}{n}$ are largest when $n$ is half of $m$. Put $m=2n$ and use Stirling's approximation for the factorial. You get

$$\binom{2n}{n}=\frac{(2n)!}{(n!)^2}\sim \frac{(2n)^{2n}e^{-2n}\sqrt{4n\pi}}{n^{2n}e^{-2n}2n\pi}=\pi^{-1/2}2^{2n}n^{-1/2}$$
> 1 votes

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


# Question
Title: Building Suffix Array from Suffix Tree. Inorder visit when node has more than two children
From the notes:

> It is not difficult to observe that the suffix array $\texttt{SA}$ of the text $\texttt{T}$ can be obtained from its suffix tree $\texttt{ST}$ by performing an in-order visit: each time a leaf is encountered, the suffix-index stored in this leaf is written into the suffix array $\texttt{SA}$; each time an internal node u is encountered, its associated value is written into the array $\texttt{lcp}$.

**How do you do the inorder visit when a node has more than two children?**

Let's say you visit the leftmost child, then the node, then the other leftmost child. Then do you visit again the node?

*SA* in an array of pointer to suffixes, ordered lexicographically.

*lcp* contains the longest common prefix between two consecutive suffixes $\text{suff}\_{SA\[i\]} \text{ and } \text{suff}\_{SA\[i+1\]}$.

The \\$ represents a char that's smaller than every other char.

The value associated to each node is the length of the prefix spelled so far.

The leaves represents indices of suffixes. If T = banana\\$, the leaf 3 represents nana\\$ (T\[3,7\])

In the image there's what is supposed to be a suffix tree, but I think there's an error since the edges should be sorted according to their label and the leaf 7 with the edge labeled "\\$" should be the leftmost leaf and edge.

When simulating the algorithm, first you visit the node 7 ( using the fixed version of the tree ), then the root, so you have

```
SA = [7, ...]
lcp = [0, ...]

```

Then let's say you keep going on with an inorder visit of u. **When you go back to the root, do you insert the value 0 again in the lcp**? Or do you do it just the first time you visited the root?

# Answer
> 0 votes
If a node has $l$ children, with $l \geq 2$ during the inorder visit you have to treat the first $l-1$ children as left nodes, and you have to visit the parent multiple ($l-1$) times, writing multiple times the length of the prefix spelled inside the lcp array.

This, applied to the tree in the image, would yield the correct:

```
SA = [7, 6, 4, 2, 1, 5, 3]
lcp = [0, 1, 3, 0, 0, 2]

```

keeping in mind that the edge labeled "$" with the leaf 7 should be the leftmost.

---
Tags: algorithms, search-trees, suffix-trees, suffix-array
---


# Question
Title: Every decidable language $L$ has an infinite decidable subset $S \subset L$ such that $L \setminus S$ is infinite
Given an infinite decidable language $L$, then if $S \subset L$ such that $L \setminus S$ is finite, then $S$ must be decidable. This is true since given a decider of $L$ we contruct a decider for $S$:

Simulate the decider of $L$ on the input, if it accepts, go over $L \setminus S$ and check if it is there, if it is, reject. If it isn't accept. If the decider of $L$ rejects - reject.

Another point is if $S \subset L$ is finite then $S$ also must be decidable, this is immediate that every finite language is decidable.

Now we have the last case where $S$ is infinite and $L \setminus S$ is infinite. We know that there must be some subsets $S$ corresponding to this case that are undecidable. This is since there are $\aleph$ such $S$ but only $\aleph\_0$ deciders. Denote $D(L) = \\{ S \subset L : |S|= |L \setminus S|=\infty \wedge S \text{ is decidable} \\}$

Is it true that for all infinite decidable languages $L$ we have $D(L) \neq \phi$?

If this is true then as a conclusion we will have for all infinite decidable languages $L$ a sequence of decidable languages $L\_n$ such that $L\_0=L$ and $L\_{n+1} \subset L\_n$ and $|L\_n \setminus L\_{n+1}| = \infty$

We will also have a limit-set $L\_\infty = \\{ e \in L : \forall n \in \mathbb{N} \text{ } e \in L\_n \\}$ and can dicuss if it is empty/finite/infinite and decicable or not.

This seems like a nice way to study decidable languages, and curious to know if this direction is indeed interesting and whether there are articles published regarding these questions

Thanks for any help

# Answer
> 1 votes
If $L$ has a finite alphabet, then $L$ is recursively enumerable.

Then, from such an enumeration $w\_0,w\_1,w\_2,...$ of the words of $L$ you can take $S=\\{w\_0,w\_2,w\_4,...\\}$, which will also be decidable. To check if a word $w$ is in $S$ check if it is in $L$. If it is then use the enumeration of $L$ to check if its position is even or not.

---
Tags: turing-machines, decision-problem, computation-models
---


# Question
Title: In a single cycle datapath, do 'decode' and 'operand fetch' occur simultaneously?
After instruction has been fetched, does it go to control unit and register file at the same time or one after the other? For example if the control unit and register read both have 80ps delay, and we're calculating the total delay for a cycle, would we take their delay as 80ps(if they occur simultaneously) or if they happen one after the other so in that case delay of decode and operand fetch would be 160ps. Which one is correct?

# Answer
Figured it out. The control unit and register file are accessed one after the other. So the total delay would be 160ps.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Why is Savage's Vertex Cover algorithm a 2-approximation?
Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem.

> Given graph $G$, start at arbitrary node and traverse $G$ depth-first
>
> Obtain DFS tree $T$
>
> return $V\_C =$ internal nodes of $T$.

Now I read everywhere that this algorithm is supposed to yield a 2-approximation, but the only proof I found was here, and frankly, I don't get it and it's rather longish. Unfortunately also, the original paper is nowhere to be found. At other places where this was given as an exercise, I find the hint that one should first show that the tree $T$ admits a matching $|M| \ge \frac{1}{2} |V\_C|$. But if I had proved that (which I have no clue how to do), I have no idea how to use that knowledge. I don't see how I can put bounds on the output of the algorithm without an estimate for the number of internal nodes of an arbitrary tree. And the way I see it, such a tree can have between $1$ and $n-1$ leaves (consider the graphs which are a chain, or a star, respectively).

So I am puzzled. How could one show that this is a 2-approximation?

# Answer
First of all, you have to show that $V\_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node.

Next, we show that the DFS tree has a matching of size at least $|V\_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), this shows that the minimum vertex cover has size at least $|V\_C|/2$, so we get a 2-approximation algorithm.

It remains to show that any tree $T$ has a matching of size at least $I(T)/2$, where $I(T)$ is the number of internal node. The proof is by induction on $|T|$. If $T$ contains one vertex then $I(T)=0$ and so there is nothing to prove. Now suppose that the tree contains a root $r$ and subtrees $T\_1,\ldots,T\_n$. Let $r\_1$ be the root of $T\_1$, and let $S\_1,\ldots,S\_m$ be the subtrees of $T\_1$. The matching we are going to construct consists of matchings in $S\_1,\ldots,S\_m,T\_2,\ldots,T\_n$ together with the edge $(r,r\_1)$ (you can check that this is indeed a matching). This matching contains at least $1+(I(S\_1)+\cdots+I(S\_m)+I(T\_2)+\cdots+I(T\_n))/2$ many edges. We obtained the forest $S\_1,\ldots,S\_m,T\_2,\ldots,T\_n$ by removing two vertices $r,r\_1$, so $I(S\_1)+\cdots+I(S\_m)+I(T\_2)+\cdots+I(T\_n) = I(T)-2$. This completes the proof since $1+(I(S\_1)+\cdots+I(S\_m)+I(T\_2)+\cdots+I(T\_n))/2 = 1+(I(T)-2)/2 = I(T)/2$.
> 10 votes

# Answer
Another way to show that a vertex cover of a tree has to have at least $|V\_C|/2$ nodes is the following: The tree consists of $k$ leaves and $|V\_C|$ inner vertices, which have degree $\geq 2$. The degrees of the tree sum up to $2 (|V\_C| + k - 1)$. Therefore we can conclude that there are $k-2$ "free" degrees we can distribute to the inner vertices (in addition to the degree of 2 that every inner vertex has to have).

So let $M$ be a set of vertices with $|M| \< |V\_C|/2$. Then we can get at most $2 |M| + k - 2 \< |V\_C| + k - 2$ degrees (summed up). But we need to have at least $|V\_C| + k - 1$ to be able to cover all $|V\_C| + k - 1$ edges. Therefore M is no vertex cover.
> 1 votes

---
Tags: algorithms, graphs, approximation, matching
---


# Question
Title: Semi-decidability of the language $\overline{L_{\epsilon}}$
Firstly consider the problem: given $L\_H = \\{R(M)w : M \in TM\_0, w\in L(M)\\}$ where $R(M)$ are encoded transitions of $M \in TM\_0$. Assume for contradiction $\overline{L\_{H}}$ is semi-decidable, then there is $Q \in TM\_0$ with $L(Q) = \overline{L\_{H}}$ therefore for every $M \in TM\_0$ we have the following $$Q \ accepts \ input \ R(M)w \iff M \ does \ not \ accept \ input \ w \ \ \ \ (1)$$ Then we construct machine $Z$ s.t. doubles the input and runs machine $Q$. Observe the following for arbitrary $M \in TM\_0$: \begin{alignat\*}{2} Z \ accepts \ input \ R(M) &\iff Q\ accepts \ input \ R(M)R(M)\\ &\iff M \ does \ not \ accept \ input \ R(M) \end{alignat\*} Taking $M = Z$ will yield us a contradiction. Hence, $\overline{L\_{H}}$ is not semi-decidable.

The same technique I am trying to apply for the case $L\_{\epsilon} = \\{R(M) : M \in TM\_0 \ \text{s.t. $M$ accepts $\epsilon$}\\}$ where $R(M)$ are encoded transitions of $M \in TM\_0$. But I am facing some troubles. Assume for contradiction $\overline{L\_{\epsilon}}$ is semi-decidable, then there is $Q \in TM\_0$ with $L(Q) = \overline{L\_{\epsilon}}$ therefore for every $M \in TM\_0$ we have the following $$Q \ accepts \ input \ R(M) \iff M \ does \ not \ accept \ input \ \epsilon$$ Then I cannot really find appropriate $Z$ for this case, as doubling the input simply won't work. Any suggestions are appreciated.

# Answer
Assume for contradiction $\overline{L\_{\epsilon}}$ is semi-decidable. It's easily proven that $L\_{\epsilon}$ is semi-decidable by reduction to the HALTING problem, i.e. $L\_{H}$ is semi-decidable. If $L\_{\epsilon}$ and $\overline{L\_{\epsilon}}$ are semi-decidable, hence $L\_{\epsilon}$ is decidable. This is a contradiction, as $L\_{\epsilon}$ as well as $L\_{H}$ are semi-decidable.

In this proof the following claim was used:

> $\textbf{Claim:} \text{ If $L$ and $\overline{L}$ are semi-decidable, then $L$ is decidable}$
> 0 votes

---
Tags: turing-machines, proof-techniques, halting-problem, semi-decidability
---


# Question
Title: Check for common element in two arrays using FFT
My task asks me to check whether there is a common element in two sets $\\{x\_1,x\_2,...,x\_n\\}$, $\\{y\_1,y\_2,...,y\_n\\}$ with $x\_i,y\_i\in\mathbb{N}$ using the Fast Fourier Transform (FFT). (I'm aware that there is a simple $O(n\log(n))$ algorithm to solve this problem using sorting and binary search.) The tasks hints that we should consider the following product to solve the problem: $$ \prod\_{1\leq i,j \leq n} (x\_i-y\_j) $$ The product is obviously zero if there is a common element, but I am still not sure how I could compute it faster via FFT.
I know how to use FFT to multiply polynomials efficiently, but somehow I seem to overlook something.

# Answer
This one is a bit esoteric, but:

$$ \prod\_{1\leq i,j \leq n} (x\_i-y\_j) $$

Could be decomposed to (as noted by @NotDijkstra)

$$ \prod\_{i=1}^{n} p(x\_i) $$ where $$ p (x) = \prod\_{j=1}^{n} (x - y\_j) $$

reduces to a polynomial with roots $y\_i$. Coefficients of this polynomial could be computed with FFT, see https://arxiv.org/pdf/1608.01357.pdf. It could be done even faster using divide and conquer strategy - recursively split the formula into two polynomials and multiply them with FFT (see answers).

Polynomial representation in its turn would allow fast exponentiation of x, or even multi-point evaluation

Although, I don't see any advantages over traditional approach in terms of speed or complexity except if it's implemented on specialised ASICs/FPGAs/GPUs.
> 1 votes

# Answer
*It seems you want to use Vandermand's matrix.*

> Let's say the arrays have unique values in each of them(remember we need distinct values of \begin{equation} (x\_k) 's \end{equation} for k=1,...len(array1)+len(array2) to work for the property of "**Uniqueness of interpolating polynomial**") and we know the fact that at least one of them is common in the two arrays.
>
> > Now combine the arrays and calculate ***Determinant of Vandermand's Matrix*** which had to be nonsingular if all the x's and y's combined were distinct. Since we know there is a common element, the determinant of Vandermand's matrix must be 0, i.e, \begin{equation} \\\prod\_{0\<=j\<k\<=2n-1}(x\_k-x\_j)=0\\ \end{equation}

> > I wouldn't call it an efficient algorithm because solving the eqn using LU decomposition algorithms provides us with time complexity of O($n^3$) while even a faster algorithm like Lagrange's Formula would only get us to O($n^2$).
> 0 votes

---
Tags: algorithms, discrete-mathematics, fourier-transform
---


# Question
Title: Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma
I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying to prove?

# Answer
> 1 votes
By the pumping lemma $a^n b^n$ can be written as $xyz$ with $|xy| \le n$ and $|y| \ge 1$ in a way that ensures that $xy^kz \in L$ for any $k \ge 0$. Picking $k=0$, this implies that $xz \in L$.

Since this is not the case for your language $L$, you know that $L$ cannot be regular.

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


# Question
Title: Any reason why Turing Machine would prevail on recursion theory?
Nowadays, most introduction books, videos, and comments about theoretical computer science talk about Turing machines but don't discuss recursion theory anymore. These approaches are known to be equivalent.

What is the reason behind this? Has recursion theory simply gone out of fashion or is there a fundamental/mathematical reason explaining this?

# Answer
> 5 votes
With Turing machines you can talk about computer concepts such as running time and space usage. This is harder with $\mu$-recursive functions.

---
Tags: turing-machines, recursion
---


# Question
Title: Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$
Given an array $a$, we have to find product of $a\_{j}$-$a\_{i}$ modulo $998244353$ over all $i$ and $j$ given $j\>i$.
For eg. Let the array be $1,2,3$ then my answer will be calculated as-
$(2-1)$.$(3-1)$.$(3-2)$=$2$
As number of elements in the array could be large (upto $10^5$) I am looking for solution of order $nlogn$.
I have tried representing array as a polynomial but could get anything out of it. Please help.

# Answer
> 2 votes
The product $$V=\prod\_{i\<j}(a\_j-a\_i)$$ is the determinant of the Vandermonde matrix of the numbers $a\_1,a\_2,...,a\_n$.

The square of this number is the discriminant $D$ of the polynomial $$p(x)=\prod\_i(x-a\_i)$$

This in turn is equal to $$V^2=D=(-1)^{n(n-1)/2}\prod\_ip'(a\_i)$$

You can quickly compute the coefficients of $p(x)$ and thus $p'(x)$, evaluate it at the $n$ points $a\_1,a\_2,...,a\_n$ and their product. Then compute square root. The sign of $V$ you determine by sorting and counting the parity of the number of switches.

You can do all this in $O(n\log^2(n))$.

See the relevant algorithms here.

For the modular square root, you can use Tonelli-Shanks for efficiency. Although the theoretic order of this step is constant since the prime $998244353$ is fixed.

---
Tags: polynomials, fast-fourier-transform
---


title: Why is the following grammar not LL(1)

text:
# Question
Title: Why is the following grammar not LL(1)
Consider the following grammar:

```
S → bAb
  | bBa
A → aS
  | CB
B → b
  | Bc
C → c
  | cC

```

I have to provide the reasons as to why this grammar is not LL(1). So far all I can think of is that the grammar is not left factored given the productions:

```
S → bAb
  | bBa

```

But I am also wondering if the grammar is left recursive due to the productions:

```
B → b
  | Bc

```

Options provided are:

* This grammar has left recursion. (Unsure)
* This grammar has right recursion. (Would not make grammar not LL(1))
* This grammar is ambiguous. (Unsure)
* This grammar is not left factored. (Correct)
* This grammar can produce infinitely many distinct strings. (This shouldn't affect a grammar right?)

As far as I can tell, the grammar is not ambiguous, I have tried 3 different inputs and all have resulted in a single parse tree. So is this grammar not LL(1) just because of the lack of left factoring? or also because the grammar is left recursive?

# Answer
> 0 votes
LL(1) grammars must be unambiguous, have no left recursion, and no conflicts.

The grammar you provide is unambiguous in terms of the syntax tree, however there are conflicts when parsing (which stops it from being an LL(1) grammar). The conflicts reside in the first set of `S` and `C`. That is to say, `FIRST(S) = { b }`, but its ambiguous in which production rule to apply: `S -> bAb` or `S -> bBa`. This can be eliminated by factoring out the `b` as such:

```
S  -> b S'
S' -> A b | B a

```

Similarly for `C`:

```
C  -> c C'
C' -> c C' | eps

```

The grammar also has left recursion in the rule `B -> Bc`; this is the definition of left recursion. This can be removed as such:

```
B   -> b B'
B'  -> c B' | B''
B'' -> c

```

Check the following for more information:

---
Tags: context-free, compilers, parsers
---


# Question
Title: Is there a way to store an arbitrarily big BigInt in a bit sequence, only later to convert it into a standard BigInt structure?
I am trying to imagine a way of encoding a BigInt into a bit stream, so that it is literally just a sequence of bits. Then upon decoding this bit stream, you would generate the standard BigInt sort of data structure (array of small integers with a sign). How could you encode the BigInt as a sequence of bits, and how would you decode it? I don't see how to properly perform the bitwise manipulations or how to encode an arbitrary number in bits larger than 32 or 64. If a language is required then I would be doing this in JavaScript.

For instance, this takes bytes and converts it into a single bit stream:

```
function arrayOfBytesTo32Int(map) {
  return map[0] << 24
    | map[1] << 16
    | map[2] << 8
    | map[3]
}

```

How would you do that same sort of thing for arbitrarily long bit sequences?

# Answer
Look at Elias delta or gamma coding as an example.
> 2 votes

# Answer
There are many common encodings for arbitrary-length integers. I would say that the most-used representations are:

* Length-data representations, where the number of bytes/words is written first, followed by the data.
* A "continuation bit" representation. If the word size is *b* bits, then an integer is split into groups of *b-1* bits, with the high order bit denoting whether there is another byte following or not.

You can mix and match these. The ASN.1 Basic Encoding Rules are a case in point, where in the general case, the length field is encoded in base 128 using the continutation bit. ASN.1 BER is used in many network protocols, such as VoIP, SNMP, and LDAP, as well as in cryptography, where representing large integers is a common thing.
> 2 votes

---
Tags: encoding-scheme, bit-manipulation
---


# Question
Title: validation of a pumping lemma proof for regular languages
I have the following regular expression:

Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT I was just wondering, because $L$ is made up of a union of two expressions, is it valid to split $L$ into

$ L\_1=\\{a^ib^jc^{2j-1} | i\<=j \land i,j\>0\\}$

$L\_2=\\{a^ib^jc^{2j-1}| i\>=2j-1 \land i,j\>0\\}$

and show for each $L\_1$ and $L\_2$ that the pumping lemma does not work on them (so for $L\_1$ I just show that for each $k$, $i$ is not smaller or equal to $j$, and similarly for $L\_2$.

By that I show that $L\_1$ and $L\_2$ are not regular which means that the union of the two will also be not regular. Is this correct?

thank you.

# Answer
> 2 votes
the union of 2 non-regular languages can be regular.

The trivial example is any non-regular language L and its complement. The union of those two is the set of all strings, which is a regular language.

There for the conclusion $L1, L2 \notin Regular \implies L1\cup L2 \notin Regular$ does not follow.

---
Tags: automata, regular-languages, regular-expressions, pumping-lemma
---


# Question
Title: How can follow this this guide to construct a graph with matrix/reachability
Let's we have k matrices. For example we have 3 now, where first one is 8x5 ($a\_1$ x $b\_1$), second one is 5 x 6 ($a\_2$ x $b\_2$) and last one is 6 x 8 ($a\_3$ x $b\_3$). And our goal is to figure out if possible to multiply within any given matrices and reach a matrix of dimension **x** and **y**, when **x** and **y** is given ahead of time. In this example, (8x5) x (5x6) x (6x8), end up a 8x8 matrix. The hints is given, but I cannot visualize. Any more help is appreciated. can understand the first step, but have not idea about the second one.

> First, we can define nodes in the graph as the values of each $a\_i$ and each $b\_i$, and put an edge from $a\_i$ to $b\_i$.
>
> Second, Whenever there is a chain of matrices $M\_{i1},...M\_{ik}$, we can multiply, then **x**=$a\_{i1}$ has an edge to $b\_{i1} =a\_{i2}$, and $a\_{i2}$ has an edge to $b\_{i2}$ =$a\_{i3}$, and so on, up until $b\_{ik}$ =**y**. So there could be a path from **x** to **y** in this graph.
>
> Third, Inversely, for any path from x to y, the edges form a chain of matrices that we can multiply, which create a **x** x **y** matrix. therefore, **x** is reachable from **y** in the graph iff there is a chain of matrices which from the **x** x **y** matrix.

The first step create something like this ?

```
>  x-->
> n8-->n5
> n5-->n6
> n6-->n8
>   -->y

```

What is $M\_{i1}$, $a\_{i1}$ and $b\_{i1}$? How does that differ to $a\_{1}$ ?

# Answer
Okay let's say you got $n$ matrices $M\_1,M\_2,...,M\_n$ with dimensions $a\_1\times b\_1,...,a\_n\times b\_n$. Now we look at what happens to the dimension when we multiply two matrices $M\_i, M\_j, i\neq j$: $$(a\_i\times b\_i)(a\_j\times b\_j) = a\_i \times b\_j$$ Notice that you can only multiply the two matrices iff $b\_i = a\_j = p$: $$(a\_i\times p)(p\times b\_j) = a\_i \times b\_j$$ You might spot the pattern here: only the first dimension of the first matrix and the last dimension of the last matrix matter. Thus in order to get a matrix with dimensions $(x\ times y)$ you need a chain of matrices looking like that: $$(x \times e\_1)(e\_1 \times e\_2)(e\_2 \times e\_3)...(e\_n\times y) = (x\times y)$$ where $e\_i$ are just arbitrary numbers. This looks similar to a path in a graph, where you are walking from the node labeled with x to a node labeled with y. Notice that for every node in the graph if it represents the first component of the dimension ($a\_i$) of a matrix $M\_i$ it's connected to the second component of the dimension ($b\_i$). Meaning $a\_i$ and $b\_i$ are connected. Secondly the second component of a dimension $b\_i$ of a matrix $M\_i$ is connected to all first components $a\_j, i\neq j$ that have the same value ($b\_i = a\_j$). Now if there is a path from $x$ to $y$ in a graph you can build an equation as shown above.

The graph in your particular example looks like this:

```
8(a1) -> 5(b1)
5(b1) -> 5(a2)
5(a2) -> 6(b2)
6(b2) -> 6(a3)
6(a3) -> 8(b3)

```

Now $8 = a\_1 = x$ is your starting point and $8 = b\_3 = y$ is your end point.

EDIT: Construction algorithm:

```
Input: arrays a,b with n elements
Output: adjacency list A of size 2*n
A = new array of 2*n lists
for i = 1 to n: A[i].add(i+n)
for i = 1 to n:
   for j = 1 to n:
      if b[i] == a[j]:
          A[i+n].add(j)

```

Notice that $A\[i\leq n\]$ corresponds to the node for $a\_i$ and $A\[n+i\leq 2n\]$ corresponds to the node for $b\_{i}$. Now if you want to check if you can build a matrix with a certain dimension $(x,y)$ you search through $a$ to find $i$ such that $a\[i\] = x$ and start a dfs or bfs from node $i$ which has the neighbors $A\[i\]$ and you stop your search when you arrive at node $n+j$ such that $b\[j\] == y$.
> 0 votes

---
Tags: graphs, graph-traversal, dag, matrix, matrix-multiplication
---


# Question
Title: Is this benchmark sufficient to consider my algorithm as an efficient matrix multiplication algorithm?
I built a matrix multiplication algorithm and now I need some thoughts about following benchmark.

C++ chrono:: high resolution clock Time(micro second)

1. (Dim)256--\> (Naive algo ) 296807, (My algo) 187479
2. (Dim)512--\> (Naive algo) 2249495, (My algo) 1359046
3. (Dim)1024--\>(Naive algo) 27930970, (My algo) 12309645

FYI, I have no knowledge about strassen matrix multiplication algorithm and how to utilize a github project.Therefore,I stole some benchmark from a github account for sake of some comparisons with strassen matrix mulplication algorithm.Those are as below.

C++ chrono:: high resolution clock Time(micro second)

1. (Dim)256--\>(Naive algo) 260281,(Strassen algo) 216970
2. (Dim)512--\> (Naive algo) 2122299, (Strassen algo) 1580466
3. (Dim)1024--\>(Naive algo) 2algorithm?Strassen algo) 14696774

I don't know specs of github user's computer.I assume it's better than mine after observing both execution times of naive matrix multiplication algorithm.(quoted from https://github.com/rangelak/Strassen-Matrix-Multiplication)

Specs of my computer

Processor core i7 6th gen(2.60 GHz)

Ram 8gb

What do you think about my algorithm after observing above mentioned band what can I expect after comparing my algorithm with strassen matrix multiplication algorithm?

# Answer
> 0 votes
one thing I want to mention is that the strassen's matrix multiplication algorithm isn't often used in the real world and your algo is probably faster if the $n$ stays below a few thousands (explained here: https://stackoverflow.com/questions/13559928/why-is-my-strassens-matrix-multiplication-slow). Now if you still want to compare your algorithm to the strassens algorithm I would recommend you to copy past a function from somewhere and run it on your computer. The algorithm would get the same input as your algo and would run on the same hardware.

Here are some implementation of strassens algo:

vectors: https://github.com/dmonaldo/strassen-matrix-multiplication/blob/master/main.cpp

arrays: https://www.geeksforgeeks.org/strassens-matrix-multiplication-algorithm-implementation/

When I benchmark an algorithm I always want to plot the results to visualize the complexity. I think more is better; so you should probably use more n not only 256, 512, 1024. Also it would be good to know if your algo is made for a special case like sparse matrices etc. if that's the case you need to pay close attention to the input data, otherwise one algo might have a disadvantage.

---
Tags: algorithms, matrix-multiplication
---


title: Bipartite graphs with min weights

text:
# Question
Title: Bipartite graphs with min weights
I have a full bipartite graph with node sets $A=\\{a\_1,a\_2,\ldots,a\_n\\}$ and $B=\\{b\_1,b\_2,\ldots,b\_n\\}$. Each node has a weight, $v\_i$ for $a\_i$ and $w\_i$ for $b\_i$. Each node $a\_i$ is connected to exactly one node of $B$, say $b\_j$, via an edge $e\_i$, whose weight is $\min(v\_i,w\_j)$. Now I want to find a one-to-one mapping from $A$ to $B$, whose sum of edge weights is as small as possible.

My idea is to sort $v\_i$s increasingly and $w\_i$s decreasingly and then find the sum of all $\min(v\_i,w\_i)$ after sorting. Is it correct? Can you give a proof/disproof?

I have run computer simulations for $n=5,6,\ldots,10$ with random vertex weights and found no counterexample.

# Answer
> 2 votes
It is nice that you have checked your idea on some random samples.

---

To see why your idea work, let us find the simplest but non-trivial case and then take a look at it. For simplicity and WLOG, the weight of a node will be used to denote that node. For example, if $A$ contains a node with weight $42$, that node will be referred to as node 42.

The case of $n=1$ is trivial.

Let $n=2$. If we happens to look at to $A=\\{1, 2\\}$ and $B=\\{3,4\\}$, then however we choose the mapping, the sum will be $1+2=3$. This sample is apparently not enlightening.

How about $A=\\{1, 3\\}$ and $B=\\{2,4\\}$?

* If we connect 1 with 2 and 3 with 4, the sum is $\min(1,2) + \min(3,4)=1+3=4$.
* If we connect 1 with 4 and 3 with 2, the sum is $\min(1,4) + \min(3,2)=1+2=3$.

So this is a non-trivial example. Now we should ask the basic question, **why** does the second choice produce a smaller sum?

To answer the question, we should observe how those two sums come up. Note that 1 appears in both sums. Is that coincidence? Think for a moment and you will know it is not. 1 is the minimum number of all numbers. So whatever it is connected to, it will be selected as the weight of the connection.

That means, whatever number 1 is connected to, which is 3 in this case, that number will be missing from later computations, i.e., it will be "wasted". The bigger the "waste" is, the less the remaining numbers will be and hence the less weight the remaining connection will produce, since function $\min(\cdot, \cdot)$ is decreasing with respect to both variables. So 1 should be connected to a number as big as possible. That is **why** 1 is connected to 4 instead of 3 so as to produce the minimum total sum.

In the case of $n=2$, there are only two choices of the mapping. Either the smaller number in $A$ is mapped to the smaller number in $B$, dubbed "forward mapping", or to the bigger number in $B$, dubbed "reverse mapping". To make the mapping produce smaller total weight, we should always choose the "reverse mapping", so that a large number will be wasted (or, what is the same, a smaller number will be kept to be used.)

---

To prove your idea is correct, we first show that for any mapping from $A$ to $B$, there is a mapping that maps $\min(A)$ to $\max(B)$ with no greater total weight. Suppose map $f$ maps $\min(A)$ to some $b\_j$ and some number $a\_i$ to $\max(B)$. Then we can make another map $f'$, which is the same as $f$ except for these 4 number, $f'$ maps $\min(A)$ to $\max(B)$ and $a\_i$ to $b\_j$. Since, as we have shown above, for four numbers $\min(A), a\_i$ and $b\_j$, $\max(B)$, we have $$ \min(\min(A), \max(B)) + \min(a\_i, b\_j)\le \min(\min(A), b\_j) + \min(a\_i, \max(B)),$$ the total weight of $f'$ is not greater than that of $f$.

So we know,

* the minimum total weight comes from a mappings that maps $\min(A)$ to $\max(B)$.
* For all mappings that map $\min(A)$ to $\max(B)$, the minimum total weight comes from, by the same argument, a mapping that maps the minimum of the remaining numbers in $A$ (i.e. the second minimum number in $A$) to the maximum of the remaining numbers in $B$ (i.e., the second minimum number in $B$).
* For all mappings that map $\min(A)$ to $\max(B)$ and the second minimum number in $A$ to the second maximum number in $B$, the minimum total weight comes from a mapping that maps the third minimum number in $A$ to the third maximum number in $B$.
* And so on, until the last minimum number in $A$ is mapped to the last maximum number in $B$, i.e., the maximum number in $A$ is mapped to the minimum number in $B$. $\checkmark$

An even more formal proof could be given. However, the above reasoning might be easier to understand. It should, I believe, convince an ordinary human.

---

Here is another straightforward way to prove your idea.

First assume all numbers are distinct. Let us prove by reductio ad absurdum. Suppose the minimum total weight can be reached by a mapping $g$ other than the mapping described in your idea. Then $g$ must contain a sub-mapping that is a "forward mapping", i.e., there must be two numbers $\alpha\_1\lt \alpha\_2$ in $A$ and two numbers $\beta\_1\lt \beta\_2$ in $B$ such that $g(\alpha\_1)=\beta\_1$ and $g(\alpha\_2)=\beta\_2$.

Now we can make another mapping $g'$ which is the same as $g$ everywhere else except that the sub-mapping of $g'$ on $\alpha\_1$ and $\alpha\_2$ is a "reverse mapping", i.e., $g'(\alpha\_1)=\beta\_2$ and $g'(\alpha\_2)=\beta\_1$. Now we can, as before, verify that the total weight of $g'$ is smaller than that of $g$, which contradicts our assumption.

If all numbers are not distinct, we will use the technique of approaching by limit. Perturb all numbers slightly so that they become distinct. Now all weights will be slightly off their original weights. That means the total weight obtained from your idea should not be far from the optimal solution. Let the perturbation go to zero, we see that it is, in fact, the optimal solution.

---

You might be interested in a similar problem, how to prove the greedy algorithm that minimize the maximum sum of a pairing.

# Answer
> 0 votes
I think the best solution in here is using the min-cost max-flow algorithm on this graph. If you don't know about it, go and read about it. This algorithm is the most classic solution for this sort of problem.

---
Tags: weighted-graphs, bipartite-matching, bipartite-graph
---


# Question
Title: What is the difference between python list and c++ vector?
I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both implemented?

# Answer
Both python list and c++ vector are implemented as dynamic arrays (https://en.wikipedia.org/wiki/Dynamic\_array). (Essentially arrays that get reallocated when they are too small.) Now the important difference between the python and c++ version don't come from the data structures themselves, but rather from the language. In c++ you can store structs, primitive data types pointers etc. in a vector. But in python everything is a pointer in the sense that an e.g. an integer is stored in the heap and it has an annotation attached to it that says "i am an integer". That's required because python has a dynamic type system. And the elements stored in the list are only pointers to the actual elements. This mechanism also allows python to store different data types in the same list. This is another reason why python is kinda slow.
> 3 votes

---
Tags: data-structures, python, lists, c++
---