# Question
Title: Why is it best to use a prime number as a mod in a hashing function?
If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function

$$ H = k \bmod \ 11$$

Now all the values will be placed one after another in 9 rows. For example, in the first bucket there will be $0, 11, 22 \dots$. In the second, there will be $1, 12, 23 \dots$ etc.

Let's say I decided to be a bad boy and use a non-prime as my hashing function - take 12. Using the Hashing function

$$ H = k \bmod \ 12$$

would result in a hash table with values $0, 12, 24 \dots $ in the first bucket, $1, 13, 25 \dots$ etc. in the second and so on.

Essentially they are the same thing. I didn't reduce collisions and I didn't spread things out any better by using the prime number hash code and I can't see how it is ever beneficial.

# Answer
> 127 votes
Consider the set of keys $K=\\{0,1,...,100\\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that are multiples of $3$:

* Keys $\\{0,12,24,36,...\\}$ will be hashed to bucket $0$.
* Keys $\\{3,15,27,39,...\\}$ will be hashed to bucket $3$.
* Keys $\\{6,18,30,42,...\\}$ will be hashed to bucket $6$.
* Keys $\\{9,21,33,45,...\\}$ will be hashed to bucket $9$.

If $K$ is uniformly distributed (i.e., every key in $K$ is equally likely to occur), then the choice of $m$ is not so critical. But, what happens if $K$ is not uniformly distributed? Imagine that the keys that are most likely to occur are the multiples of $3$. In this case, all of the buckets that are not multiples of $3$ will be empty with high probability (which is really bad in terms of hash table performance).

This situation is more common that it may seem. Imagine, for instance, that you are keeping track of objects based on where they are stored in memory. If your computer's word size is four bytes, then you will be hashing keys that are multiples of $4$. Needless to say that choosing $m$ to be a multiple of $4$ would be a terrible choice: you would have $3m/4$ buckets completely empty, and all of your keys colliding in the remaining $m/4$ buckets.

In general:

> Every key in $K$ that shares a common factor with the number of buckets $m$ will be hashed to a bucket that is a multiple of this factor.

Therefore, to minimize collisions, it is important to reduce the number of common factors between $m$ and the elements of $K$. How can this be achieved? By choosing $m$ to be a number that has very few factors: a **prime number**.

# Answer
> 19 votes
Whether a collision is less likely using primes depends on the distribution of your keys.

If many of your keys have the form $a+k\cdot b$ and your hash function is $H(n)=n \bmod m$, then these keys go to a small subset of the buckets iff $b$ divides $n$. So you should minimize the number of such $b$, which can be achieved by choosing a prime.

If on the other hand you like to have $11$ to $12$ buckets and you know that differences which are multiples of $11$ are more likely than differences which are multiples of $2$ and $3$, you may choose $12$ for your very special application.

# Answer
> 11 votes
Whether this has an impact (also) depends on how you treat collisions. When using some variants of open hashing, using primes guarantees empty slots are found as long as the table is sufficiently empty.

Try to show the following, for instance:

> Assume we want to insert an element that hashes to address $a$ and resolve collisions by trying positions $a + i^2$ subsequently for $i=1,2,\dots$.
>
> Show that this procedure always yields an empty position if the hash table is of size $p$, $p$ a prime larger than $3$, and at least half of all positions are free.
>
> Hint: Use the fact that the residue class ring modulo $p$ is a field if $p$ is prime and therefore $i^2=c$ has at most $2$ solutions.

# Answer
> 5 votes
First of all, the question is phrased incorrectly. The following are equivalent and correct expressions of the intended question:

* why **must** we use a prime number as the modulo of the hash value (not "in the hashing function)

or equivalently and more succinctly:

* why must the size of a hash table be a prime number?

The proper answer to this question lies in the context, and that context is open addressing with double hashing collision resolution.

Where you compute:

```
hashval1 = hashfcn1(k) // for initial location
hashval2 = hashfcn2(k) // probing increment

```

hashval1 is used for the initial insertion probe. If that location is empty, then you insert the (k, v) and you’re done, never using hashval2. If that location is occupied, then you jump hashval2 addresses to (hashval1 + hashval2) % arraysize, and repeat to see if the location is empty. If that location is again not empty, then you jump another hashval2 addresses to (hashval1 + 2 * hashval2) % arraysize. And so on.

Here’s the key: HOW MANY TIMES DO YOU PROBE BEFORE GIVING UP?

If every element of the array is potentially a target, then the answer is: you probe n-times. This is easy to visualize with linear probing, you write a *for (i = 0; i \< n; ++i)* loop for probing which breaks early if a empty slot is found. It’s no different with double hashing, with the exception that the probe increment is hashval2 rather than 1. But this leads to a problem, you’re not guaranteed to probe every slot in the array when hashval2 \> 1. Simple example of this: array size = 10 and hashval2 = 2; in this example you only ever probe the even or odd slots, in fact, you end up probing each slot twice, which is pointless. Even if you make the array size an odd number like 15, if probe increment is 5 then the probe sequence will be (let’s use hashval1 = 0): 0, 5, 10, 0, 5, 10, 0 5, 10, 0, 5, 10, 0, 5, 10. You keep probing the same three occupied slots over and over.

What’s the problem here? The problem is that the hash table size and hashval2 share common factors, in this case 5. So we need the hash table size and hashval2 to share no factors. Since hashval2 is a function of k and post modulo lies in the range of 0 \< hashval2 \< array size, there’s nothing we can do about hashval2. That leaves the array size. The array size in double hashing must be guaranteed to have no factors in common with hashval2. Thus by simple math, the array size must be a prime number.

Example: Array size = 11 (a prime number). hashval1 = 1.

```
hashval2 = 1; // 1,2,3,4,5,6,7,8,9,10,0 <-- probing sequence
hashval2 = 2; // 1,3,5,7,9,0,2,4,6,8,10
hashval2 = 3; // 1,4,7,10,2,5,8,0,3,6,9
hashval2 = 4; // 1,5,9,2,6,10,3,7,0,4,8
hashval2 = 5; // 1,6,0,5,10,4,9,3,8,2,7
hashval2 = 6; // 1,7,2,8,3,9,4,10,5,0,6
hashval2 = 7; // 1,8,4,0,7,3,10,6,2,9,5
hashval2 = 8; // 1,9,6,3,0,8,5,2,10,7,4
hashval2 = 9; // 1,10,8,6,4,2,0,9,7,5,3
hashval2 = 10;// 1,0,10,9,8,7,6,5,4,3,2

```

You always probe a maximum of the number of slots in the hash table; i.e., every slot has an equal chance of hosting a value. But since the probe increment is itself a hash value, it is uniformly distributed over the size of the hash table which eliminates the clustering you get with other collision resolution algorithms.

TL;DR: a hash table size that is a prime number is the ONLY way to guarantee that you do not accidentally re-probe a previously probed location.

# Answer
> 2 votes
If your hash function is of the form $h(k)=a\times k \mod m$ where $m$ is prime and $a$ is chosen at random, then the probability that 2 distinct keys hash to the same bucket is $1\over m$. So for $m=1009$, $Pr\\{h(x)=h(y), x\neq y\\}=0.00099108027$ which is very small.

This scheme is known as: Universal Hashing.

# Answer
> 1 votes
Just to complement Mario Cervera's answer.

Let's consider a hash function given by `hash(k) = k mod 12`, so our hash table has 12 buckets.

First, we need to understand how collisions occurr in hash tables. Two numbers with keys $k\_1$ and $k\_2$ are said to collide when `hash(k_1)=hash(k_2)` which is $k\_1 \mod 12 = k\_2 \mod 12$.

Now imagine that we have a list of values to add to our hash table, with the following keys respectively: $ \[ 0, 1, 2, \dots, 100\]. $

The following plot shows the size of each bucket in the hash table, after adding the above values.

As can be seen, the bucket size is fairly even accross the hash table. In practice however, it is seldom the case that the data is so neatly distributed.

It is for example, more common that there are values that are more likely to occur than others. An example where this occurs is if the keys are strings, and the hash function is just adding the ascii code of each character, and then modding the result.

In any case, let's assume the extreme case where the set of keys consists of only numbers that are multiples of 3.

So we construct the list as follows:

```
[0, 3, 6, 9, 12, 15, 18, ...]

```

Now we try filling in the hash table again, using the same hash function as before:

As you can see, it is less balanced. In fact, the uneven buckets are 0, 3, 6, and 9.

To see why, suppose we only have multiples of 3 as keys, and observe how they are assigned to buckets:

```
Keys:     0  3  6  9  12 15 18 ...
          ↓  ↓  ↓  ↓  ↓  ↓  ↓
Bucket:   0  3  6  9  0  3  6  ...

```

Which explains the uneven buckets above.

Now let's try with a bucket size of 10, and the same unbalanced data.

It is again well balanced. And 10 is not a prime. So what's going on?

For the unbalanced data, the main difference between bucket size 10 and bucket size 12, is that the buckets that are multiples of 3 do not line up neatly inside the bucket size 10, as marked in bold:

```
Keys:     0  3  6  9  12 15 18 ...
          ↓  ↓  ↓  ↓  ↓  ↓  ↓
Bucket:   0  3  6  9  2  5  8  ...

```

Which explains the nicely balanced result above.

So the main issue is that 12 (the first bucket size) is a multiple of 3.

So the general rule is: since we know that the data might be biased, we want to decrease the chance that it is biased towards numbers **that divide the bucket size**. And which numbers are famous for having few divisors? The prime numbers!

# Answer
> -2 votes
I think we have a short answer by using probability. we use % (modulo) in hashing to calculate remainder of a division(our data % chosen number). **if our mod be a prime number which also is our divisor it is more likely that division has a remainder** and less numbers has same factor like our divisor So less collision happens.

---
Tags: data-structures, hash, hash-tables, primes
---


# Question
Title: Confusion when composing functions in Lambda expression
> $$(\lambda x. x \text{ } x ) ( \lambda x . x \text{ } x )= (\lambda x. x \text{ } x) ( \lambda x . x \text{ } x)$$
>
> Source

I am a bit confused on how this composition was done. When I do it, I get:

$$ \lambda x. (\lambda x. x \text{ } x) (\lambda x . x \text{ } x)$$

On what basis do I drop the exterior most $\lambda x.$?

# Answer
> 4 votes
You drop the $\lambda x$ because that's just how beta reduction is defined: $(\lambda v.M)(N) \triangleright\_\beta M\[v/N\]$. In your example, $v$ is $x$, $M$ is $xx$, and $N$ is $\lambda x. xx$.

The intuition is that once you applied the function to an argument, then the slot is filled and no longer open for substitution with yet another argument ad infinitum. The "$\lambda x.$" is like the "$f(x) = $" in something like "$f(x) = x^2$". Once you apply the function, $f(2)$, the result is equivalent to $4$ (the part behind the equivalence sign with $2$ substituted for $x$), and not a new function of the form $f(x)$.

---
Tags: lambda-calculus
---


# Question
Title: number of substrings in same position with same contents
`L1` and `L2` are two lists which only consist of `X`'s and `Y`'s. `L1` and `L2` have the same length.

How many sublists of `L1` contain the same number of `X`'s as the sublist of `L2` in the same position? The empty sublist is not counted.

For example:

1. `L1` = `X` `L2` = `Y` =\> return `0`
2. `L1` = `Y, Y` `L2` = `Y, Y` =\> return `3`
3. `L1` = `Y, X, Y` `L2` = `X, Y, X` =\> return `2`
4. `L1` = `Y, Y, X, X` `L2` = `X, X, Y, Y` =\> return `2`

A brute-force approach would have time complexity `O(n^2)`. I think (but I am not sure) there's an `O(n)` solution, but I can't put my finger on it.

# Answer
You are right, there is an $O(n)$ time algorithm for this.

Let $L(i,j)$ be the substring of the string $L$ from index $i$ to $j$, and let $|L|\_X$ be the number of $X$'s in $L$. Consider that the number of substrings ending on an index $j$ with the same number of $X$'s in both strings is equal to the number of indices $i$ (with $i\<j$) for which $$|L\_1(1,i)|\_X - |L\_2(1,i)|\_X = |L\_1(1,j)|\_X - |L\_2(1,j)|\_X$$ Hope this helps.
> 0 votes

---
Tags: algorithms, time-complexity, substrings, linear-complexity
---


# Question
Title: Can someone help me understand this Turing Machine?
I am using the book Elements of the Theory of Computation (2nd edition), which has been fine until now. However, I am stuck trying to grasp the Machine Turing conveyed in Example 4.1.8 (pages 189-190). I cannot make sense of the copying machine portrayed in Figure 4-8. Can someone help me understand with an input word as an example?

# Answer
The following is how I decode this program. The $R\_\sqcup$ is a macro for the machine that moves right until it reads a blank. I deduce that $R^2\_\sqcup$ repeats this process, locating the second blank to the right. Now the machine shutles right and left moving one non-blank $a$ to the right each cycle.
The position in the original string of the current copied character is temporarily marked with a blank.

```
move-Left until space

step-Right

while the current character a is not a space
do
    write space // overwriting a, but it is memorized,
    twice: move-Right until space,
    write a       //on the position of the second space
    twice: move-Left until space,
    write a       // restoring the a in the first copy
    step-Right
od

move-Right until space

```
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Why does a 32 bit address only contain 1 byte, when 32 bits = 4 bytes?
I am really confused about it. I think 32 bits = 4 bytes but 32 bit address is only 1 bit.

# Answer
The address indicates *where* in memory a piece of data is found. This piece of data can be of any size.

The page number in a book is made of two digits. That does not mean that the page only contains two digits, does it ?
> 4 votes

# Answer
The question is confusingly worded, but if the question is "why a pointer of 32 bits (4 bytes) points to only one byte of storage", that is just how a particular computer architecture (like x86) is designed.

It's designed with byte-addressable storage, even though the address space itself is larger than 8 bits, and therefore a pointer into that address space requires more than one byte for its storage.

There is no intrinsic link between the size of the pointer and the size of each addressable unit.

On a 64-bit architecture, it takes 8 bytes (64 bits) to store a pointer which points to one byte.

As for why an 8-bit byte tends to be the minimum addressable unit, the most obvious explanation on the x86 architecture is the need for 16, 32, and 64-bit processors in the x86 lineage (which are all considered to be successors of the 8080, which was an 8-bit processor) to be backward compatible with each previous iteration, going back ultimately to the 8080.

But if you were starting from a clean slate, the number of bits in a byte, and the size of an addressable unit, is somewhat a matter of convention, and there have been historically (and probably still are) different conventions than the 8-bit byte and byte-addressable memory.

Also, with 32-bit processors, although the pointer may address only one byte explicitly, the instruction set is such that a pointer can be treated as addressing a 32-bit value *starting* at the address referred to by the pointer, but continuing also into 3 subsequent addresses.

This way, a 32-bit pointer can *implicitly* be addressing a value of 32-bit size, even though it explicitly addresses a value of only 8-bit size. What implicit size a pointer is treated as addressing, depends on the instruction to which that pointer is supplied as an operand.
> 3 votes

# Answer
On top of what everyone else has said, computers tend to be byte-addressable because text is an important use case.

Of course, modern CPUs don't actually read a byte from RAM. They read a *cache line*, which might be 32-128 bytes in size, and then extract bytes or words from that.

Every so often, a new generation of hardware designers comes along and wonders why we don't just load and store words, and then use a second instruction to extract bytes if we need them. In the next revision of the hardware, without fail, the byte addressing instructions always gets added back. Increasing pressure on the instruction window is a bad idea.
> 2 votes

---
Tags: computer-architecture, memory-hardware, memory-allocation
---


# Question
Title: Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem
The unweighted maximum coverage problem is defined as follows:

Instance: A set $E = \\{e\_1,...,e\_n\\}$ and $m$ subsets of $E$, $S = \\{S\_1,...,S\_m\\}$.

Objective: find a subset $S' \subseteq S$ such that $|S'| = k $ and the number of covered elements is maximized.

The problem is NP-hard, but a simple greedy algorithm (at each stage, choose a set which contains the largest number of uncovered elements) achieves an approximation ratio of $1-\frac{1}{e}$.

In the following post, there is an example of when the greedy algorithm fails.

Tight instance for unweighted maximum coverage problem?

I wish to prove that the approximation ration for the greedy algorithm is tight. That is, the greedy algorithm is not an $\alpha-$approximation ratio for any $\alpha \> 1-\frac{1}{e}$.

I think that if I will find, for any $k$, (or for an ascending series of $k's$), an instance where the number of elements covered by greedy algorithm is $1-(1- \frac{1}{k})^k$ times the number of elements covered by the optimal solution, the tightness of the ratio will be proved.

Can someone give a clue for such instances?

I thought of an initial idea: let $E = \\{ a\_1 ,...a\_n,b\_1,...,b\_n,...,k\_1,...,k\_n\\}$, a set with $n\cdot k$ elements. Let $S$ include $k$ sets of $n$ elements each, $A = \\{ a\_1 ,...a\_n\\},...,K= \\{k\_1,...,k\_n\\}$. The optimal solution will select these $k$ sets and cover all the elements in $E$. Now I want to add $k$ sets to $S$, that will be the solution the greedy algorithm will find, and will cover $1-(1- \frac{1}{k})^k$ of the elements in $E$. The first such set, of size $n$: $S\_1 = \\{a\_1,...a\_\frac{n}{k},b\_1,...b\_\frac{n}{k},...,k\_1,...k\_\frac{n}{k} \\}$ ($\frac{n}{k}$ elements from each of the first $k$ sets). The second such set, of size $n - \frac{n}{k}$: $S\_2 = \\{a\_\frac{n}{k},...a\_{\frac{n}{k}+ (n - \frac{n}{k})\cdot\frac{1}{k}},b\_\frac{n}{k},...,b\_{\frac{n}{k}+ (n - \frac{n}{k})\cdot\frac{1}{k}},...,k\_\frac{n}{k},...,k\_{\frac{n}{k}+ (n - \frac{n}{k})\cdot\frac{1}{k}} \\}$ , (that is, $(n - \frac{n}{k})\cdot\frac{1}{k}$ elements from each of the first $k$ sets) and so on till we have $k$ additional such sets.

I don't think this idea works for every $k$ and $n$, and I'm not sure it's the right approach.

Thanks.

# Answer
Your approach is mostly correct. The coverage of $S\_i$ is $n ( 1 - 1 /k)^{i-1}$ and the sets $S\_1, \ldots, S\_k$ are disjoint, so the total coverage is $$ \sum\_{i=1}^{k} n (1 - 1 / k)^{i-1} = n \left( \frac{1 - (1 - 1/k)^k}{1 - (1-1/k)} \right) = kn \left( 1 - (1 - 1/k)^k \right) = \mathrm{OPT} \cdot \left( 1 - (1 - 1/k)^k \right) $$ as required, where OPT is the optimal value ($nk = |E|$ in this case). The above sum is a simple Geometric series.

There are two small problems. Firstly, the sizes of the $S\_i$s may not be integral. You can fix this by setting $n=k^{k-1}$ so that $$ |S\_i| = k^{k-1} \left( \frac{k - 1}{k} \right)^{i-1} = k^{k-i}(k-1). $$

The second problem is that the algorithm will not necessarily select set $S\_1$ over all of $A, B, \ldots, K$ as they are all provide $n$ additional coverage. You will have the same problem with all subsequent sets. You could reasonably just declare that the $S\_i$s appear before $A, \ldots, K$ in the collection of sets, and that this is how the greedy algorithm tie-breaks. To be more thorough, you could add $k$ new elements to $E$, and add a unique new element to each of $S\_1, \ldots, S\_k$. The greedy algorithm is now obliged to choose $S\_1, \ldots, S\_k$ and achieves a coverage of $$ kn \left(1 - (1 - 1/k)^k) \right) + k = kn \left( 1 - (1 - 1/k)^k + 1 / k^{k-1} \right). $$ The new term $1 / k^{k-1}$ obviously goes to zero and the $1-1/e$ upper bound on the approximation factor is still proved.
> 0 votes

---
Tags: np-hard, approximation, greedy-algorithms, set-cover
---


# Question
Title: What is the motivation behind (purpose of) "macros" in languages such as Rust, Nim, Crystal, etc.?
Most constructs / schemes in programming serve an essential purpose (sometimes more than one), for instance :

* Structs in essentially C's solution to the problem of providing user defined data types.
* Classes in C, Python, generalize the concept and allow for OO programming.
* Templates or type parameters or generics (C++, Java, etc.) allow for the type of a variable to be passed as a parameter, and thus makes it possible to write more generic code by abstracting the actual type of a variable away (in an algorithm, for instance).
* etc.

So I assume that "macros" also serve an essential purpose. I understand that it gravitates basically about "meta-programming", but what is the concrete advantage expected from it? What potential problem does it solve in main cases?

Based on the examples above, if you had to summarize the idea in one short sentence, how would you formulate it?

In particular, I am wondering what the point of being able to define dynamically the name of a function (for instance) could be?

Somehow, the abstract idea of macro seems to be at the top of the following hierarchy of abstractions (or generalizations):

* the concept of parameter of a function.
* The concept of the type of a parameter bieng itself a parameter (generics, templates, parametric types).
* The concept of a function being passed as a parameter to another function or a function returning a function.

Etc.

# Answer
> 2 votes
Macros indeed enable a powerful form of metaprogramming. In particular they allow

* to substitute any kind of piece of code,
* anywhere, not necessarily in identifiers.

They are quite useful to implement compile-time variants of the code, to ensure portability across platforms, as shorthands for repeating fragments, as compile-time search/replace for configuration...

---
Tags: meta-programming
---


# Question
Title: Are there applications in which random number generation quality is the bottleneck?
Random number generators commonly found in default libraries are actually pseudo-random number generators. Nevertheless, more sophisticated options exist to gather entropy from "truly"-random sources such as atmospheric noise, thermal noise, electromagnetic and quantum phenomena.

Speed of random number generation is important, as for instance Monte Carlo simulations need a large amount of random numbers. Since speed can be the bottleneck and Monte Carlo simulations are used in many fields, an improvement in random number generation speed translates into real-life value generated.

What about the quality of the randomness? Are there real-life applications in which the random number generation quality is the bottleneck? That is, are there situations in which an improvement in quality (or generation cost for a given quality) of random-number generation over the state of the art would result in real-life value generated?

# Answer
There have certainly been situations where the periodicity of some pseudo-random number generators along with simplifications during use and exceptional observers have caused issues -- the obvious one that comes to mind is the guy who could predict where the "randomized" Press Your Luck gameboard would land.

As far as more modern applications, I think one big concern is any time that you have two systems using similar pseudo-random number generators "against" each other. Whether these are simple game AIs or generative adversarial networks, you risk a chance of similarity in the number generation process, creating more false positive "successes" than would normally happen by chance.

Furthermore, because any pseudo-random generative process is inherently "predictable" given enough time and resources, how would you know if an AI was able to learn what algorithm you were using, or just abstracting it to outcomes from your number generator? This has applications from games to encryption to even just learning tasks -- you can't tell if an AI is answering your questions "intelligently" in a multiple choice test if it is just determining which answer slot will be the next one chosen randomly as the "correct" slot without reading the question.
> 1 votes

---
Tags: randomness, pseudo-random-generators, random-number-generator
---


title: MIPS limited dual issue

text:
# Question
Title: MIPS limited dual issue
Some of the MIPS processors like 5kc, 5kf have "limited dual issue". Searching online it seems that this means that the processor allows for a dual issue in only some selected cases, but it is not clear which ones these precisely are. Can someone elaborate on what "limited dual issue" exactly means ?

Further, came across another terminology around limited dual issue - asymmetric and symmetric. What does asymmetric limited dual issue mean ?

# Answer
Limited in this context means that the processor can only execute certain combinations of instructions in parallel. It may not even have more than one pipeline and may use some other mechanism for instruction-level parallelism. Asymmetric means that the two pipelines are not identical. For example, one pipeline could handle branches and arithmetic instructions while the other handles memory instructions.
> 0 votes

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


# Question
Title: Compute upper convex hull of a function surface
I have a sampled function sruface

$$ z = f(x, y) $$

represented as a grayscale raster image. How to find the upper convex hull of that surface. That is I am looking for the minimal

$$ g(x, y) $$

such that

$$ g(x, y) \geq f(x, y), \text{Eigenvalues}(\text{Hessian}(g)) \< 0 $$

It is possible to convert the image into a 3d mesh, and then use qhull or similar, but that would result in too much overhead.

# Answer
> 0 votes
I figured out that there is a problem with the convex hull of a raster image, namely the fact that it is essentially constructed of quads, which gives an ambiguity. For example, consider the example below:

```
0   1

1   0

```

This could be interprted like

```
0 -- 1
|  / |
| /  |
1 -- 0

```

```
0 -- 1
| \  |
|  \ |
1 -- 0

```

Which obviously results in a different upper convex hull. Thus, a general convex hull algorithm would be required.

---
Tags: convex-hull
---


# Question
Title: Confusion regarding FLEX(regular expressions)
I am building an analyzer that takes in text and numbers the lines; taking in

```
hello how are you
i'm fine thanks

```

as input and using the code:

```
%{
    int i=0;
%}
%option noyywrap
%%
.* {i++;printf("[%d] %s \n",i,yytext);}
%%
void main(){
    yylex();
}

```

this yields:

```
[1] hello how are you

[2] i'm fine thanks

```

there's an empty line there, why? using this code fixes the issues:

```
%{
    int i=0;
%}
%option noyywrap
%%
[ \t]*\n
.* {i++;printf("[%d] %s \n",i,yytext);}
%%
void main(){
    yylex();
}

```

this yields:

```
[1] hello how are you
[2] i'm fine thanks

```

I am confused about why there is an empty line using the first code, and why adding

```
[ \t]*\n

```

fixes the problem.

# Answer
> 2 votes
There are two things you need to know about Lex (and hence Flex, which follows the same semantics):

1. It buffers a line of input at a time.
2. The dot `.` symbol includes the new line/carriage return at the end of a line.

The first point is the important one. It means that Lex tokens cannot span a line break. If you need to handle multi-line tokens (e.g. a programming language with multi-line strings or multi-line comments), this is typically handled with start states.

Your input file (assuming Unix line endings; if you're using DOS line endings, mentally replace `\n` with `\r\n`), is essentially this string:

```
"hello how are you\ni'm fine thanks\n"

```

When Lex reads, this, it starts by buffering the first line:

```
"hello how are you\n"

```

The whole line matches the regular expression `.*`, and in particular, the `\n` character matches the `.` symbol.

So when you print the token text:

```
printf("[%d] %s \n",i,yytext);

```

what you are actually printing is:

```
"[1] hello how are you\n \n"

```

That is why you see a blank line in the output. Adding the other rule gives Lex a higher-priority token to consume the line ending.

(Note: Examples follow, but I have not actually tested any of these!)

This would also have worked:

```
[^\r\n]*  {i++;printf("[%d] %s \n",i,yytext);}
[\r\n]    ;

```

Here, the first line tells Lex that you want to match everything except line endings, and the second line gives Lex a rule to consume the line ending.

So would using the lookahead operator `/`:

```
.*/[\r\n]*  {i++;printf("[%d] %s \n",i,yytext);}
[\r\n]      ;

```

If you really want the whole line, not including the line ending, it's also good practice to include explicit start-line and end-line operators:

```
^[^\r\n]*$  {i++;printf("[%d] %s \n",i,yytext);}
[\r\n]      ;

```

(By the way, I put an explicit semicolon on rules for which I want Lex to do nothing. That's just my style, but I think it's a good habit to be in if you do a lot of Lex.)

Lex buffers input lines because it was designed in the 1970s when the memory and address space of computers was much smaller than it is today. It was also designed for early Unix, where everything is a small tool which takes text as input and output, to be connected together with pipes.

Modern thinking among compiler writers is that it makes more sense just to memory-map the whole input file and let the operating system do the buffering for you. This way, you don't have to worry about how line buffering interacts with your lexical analyser.

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


# Question
Title: Calculate all distances in an undirected and unweighted graph
Which algorithm do I use and how much does it cost if I have to:

Calculate all distances in an undirected and unweighted graph from two sources to all nodes.

I think the most appropriate algorithm is a BFS(G,s) with cost T(n)= O(V+E) where V= (number of nodes) and E=(number of arcs). The algorithm is the one in the figure. In this algorithm, however, only one source is considered. So it wouldn't answer the question. What would be the right answer and what the cost?

# Answer
> 0 votes
**Approach**:

1. Run $BFS(vertex\_{1})$.
2. Run $BFS($vertex\_{2})$.

**Complexity:**

$O(|V|+|E|) + O(|V|+|E|) = O(|V|+|E|)$

As long as you have a constant $c$, then $c\times f(n) = O(f(n)) $.

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


# Question
Title: Given a binary matrix, find the number of sub-matrices with all ones
Given a matrix A, let Aij denote the element of the i'th row and j'th column. $$ A\_{i,j}\in \\{0, 1\\}$$

Find the number of sub-matrices with all ones.

**1 \<= #rows, #columns \<= 150**

P.S. This apparently can be solved in O(#rows x #columns) using dynamic programming and stack. I just can't wrap my head around how this can be achieved.

# Answer
> 1 votes
Here is a solution in $O(n\cdot m)$, where $n, m$ are the number of rows and columns respectively.

Let us iterate over all columns of the matrix from left to right. For each column let us iterate over all cells in this column and for each cell $A\[i,j\]$ let us compute the number of submatrices of ones, having $A\[i,j\]$ as the bottom-right corner. Let $\mathcal{T}\[i,j\]$ be the set of all these submatrices, and $T\[i,j\] = |\mathcal{T}\[i,j\]|$ be the value we want to compute.

Let $Z\[i,j\]$ be the longest number of ones on the $i$th row ending at the $j$th column. Then it holds $$Z\[i,j\] = \begin{cases} 0 &\colon A\[i,j\] = 0\\ A\[i\]\[j-1\]+1 &\colon \text{otherwise} \end{cases}$$ Hense, we can compute this value in constant time for each cell.

Now for a cell $A\[i,j\]$ assume that $Z\[i-1,j\] = k$, then all matrices in $\mathcal{T}\[i\]\[j\]$ can that span at least two rows can have at most $k$ columns, independent of $Z\[r, j\]$ for $r \< i-1$. This monotonousity allows us to \`\`forget'' the values of $Z\[r, j\]$ where $r\<j$ adn $Z\[r,j\]\>Z\[i-1, j\]$.

Therefore, we define a stack $\mathcal{S}\_j$ for each column. We start with empty column, and when iterating over the cells of the column we update the stack as follows:

If $A\[i\]\[j\] = 0$, then empty the stack and set $T\[i\]\[j\] = 0$, otherwise do the following

```
while not stack.empty
 let r = stack.top
 if z[r,j] >= z[i,j]
  stack.pop
 else
  break
// now r is the last row having Z[r][j] < Z[i][j]
if not stack.empty
 T[i,j] = T[r,j]
T[i,j] += Z[i][j] * (i-r)
stack.push(i)

```

So the stack keeps sequence of rows of increasing `Z[i,j]`. The whole dynamic programming is in the line `T[i,j] = T[r,j]`, since we can extend each submatrix ending at $A\[r,j\]$ to one ending at $A\[i,j\]$ (since all the lines $i'$ between $r$ and $i$ have a greater value of $Z\[i',j\]$ than $Z\[r, j\]$. We als have all submatrices using rows $r+1$ to $i$ and the last $Z\[i,j\]$ columns.

Note that we push each cell exactly once to the stack, and hence can pop it at most once, since all other operations are done in constant time per cell, we achieve a total running time of $O(n\cdot m)$.

---
Tags: algorithms, matrices
---


# Question
Title: Which algorithm solves the single-pair shortest path in a weighted directed cyclic graph?
I need to find the shortest path between two nodes in a directed, positively weighted graph that migt contain cycles. All weights are either zero or one. If it was not weighted, I'd use breadth-first search. Dijkstra's algorithm should solve this, but is there a more appropriate algorithm?

# Answer
Since all distances are between $0$ and $n-1$, Dijkstra's algorithm with a suitable priority queue takes time $O(n+m)$, where $n$ and $m$ are the number of edges and vertices of the graph, respectively.

The priority queue is simply an array $A$ such that $A\[i\]$ contains a list of all elements with key $i$. The keys extracted during Dijkstra's algorithm correspond to distances in the graph and are always non-decreasing. Therefore to report the smallest element in the queue it suffices scan the array starting from the previous index $i$ (initially $i=0$) until an $A\[i\]$ that stores a non-empty list $L$ is found. Then remove any element element $x$ from $L$ and return it.
> 1 votes

---
Tags: algorithms, graphs, weighted-graphs, directed-graphs
---


title: Special arcs - graph traversal

text:
# Question
Title: Special arcs - graph traversal
question is: given an unwighted nondirected graph G=(V,E) portrayed as an adjacency list, a special arc is defined as an arc (u,v) where both u and v has the same distance from source vertex s.

i need to give an algorithm to find all of the special arcs for a given s node.

the teacher's solution is: run BFS from s and save distances from s in every node. then, go over all of the nodes and for every node, check if 1 of the neighbors has same distance.

they claim its complexity is O(|V|+|E|) .. i think it is not.. if all nodes are connected to all nodes then for every node we check we go through all of the nodes so isn't it O(|V|^2)?

# Answer
Run BFS from source vertex $s$ to find length of shortest path from $s$ to all other vertices in $O(V+E)$.

After than, traverse all edges $(u,v)$, let $d\[u\]$ be shortest distance of vertex $u$ from $s$, if $d\[u\]=d\[v\]$ then report that edge as a special arc. We traverse each edge one time and checking whether end points of edge $(u,v)$ have the same distance from source or not, it's obvious that can be done in $O(1)$.

So the total running time will be $O(V+E)$.
> 2 votes

# Answer
If you have a clique then the complexity is $O(|V|^2)$ as you claim, but $|E| \in \Theta(|V|^2)$ so $O(|V|^2) = O(|E|)$.
> 0 votes

---
Tags: graphs, breadth-first-search
---


# Question
Title: Longest prefix of string S that is also a sub-prefix of S in linear time
As the question suggest. I want an algorithm that runs in linear time which finds the longest prefix of a substring that is a sub-prefix of the same string.

**Formally:**

---

Given a string $S$ of length $n$, we define a function $\delta\_{S}:$ $\[n\]\rightarrow\[n\]$ as follows. For each integer $w$, $1\le w\le n$, $\delta$ is defined:

$\delta\_{S}\[w\] = \max\\{i\colon S\[1...i\] = S\[w...w+i-1\]\\}$.

The algorithm should find $\delta\_{S}\[w\]$ for each $1\le w \le n$.

---

Question should be solved using the $\pi$ function of KMP's preprocessing.

---

The question can be easily solved in $O(n^2)$. The $O(n^2)$ solution is simple and straightforward. For each $w$, manually find the longest prefix. Each iteration could take $O(n)$ time, thus for all $1 \le w \le n$ it would take $O(n^2)$. However, the question should be solved in a linear time. This question falls down under string matching, in particular, KMP. I know the question should be solved using the function $\pi$ from KMP's pre-processing. However, I can't solve the question.

---

**What I tried:**

Assume in this answer that all arrays starts from index 1 and ends at index n. Not from 0 until n-1.

Create a new array $\delta$. Initialize $\delta\[1\]$ = n, since this is always true, and initialize the rest of the array to be 0.

Create an array $\pi$ and compute $\pi(w)$ for $1\le w \le n$, and then for each index, subtract the index of the cell of the array from the content of the array. For instance, $i-\pi(i)$ and then check if this value is greater from $\delta\[i\]$. However, I seem to get stuck and can't solve the problem. I've tried to solve the problem for a couple of days before posting here, I can't seem to really fully understand the question and how to approach it.

# Answer
> 2 votes
The algorithm you mentioned is correct. Note as the comments pointed out, that you want to compute the so called $z$-function: $$ z\[i\] := \max\_{k\in\[n\]}\\{k\\,|\\, S\[1:k\] = S\[i:i+k\],\\,\\, 0\leq i+k \leq n\\} $$ using the $\pi$ function: $$ \pi\[i\] := \max\_{k\in\[n\]}\\{k\\,|\\, S\[1:k\] = S\[i-k:i\],\\,\\, 0\leq i-k \leq n\\} $$ We claim that $$ z\[i\] := \max\_{k\in\[n\]}\\{k\\,|\\, \pi\[i+k\] = k,\\,\\, 0\leq i+k\leq n\\} $$ Notice for each $i\in \[n\]$: $$ \pi\[i+k\] = k \iff S\[1:k\] = S\[i:i+k\] $$ By taking the maximum over $k\in \[n\]$ our proof is complete. This yields the algorithm:

```
z[1,...,n] = 0
for i in [n]:
    k = pi(i)
    z[i-k] = max(z[i-k],k)

```

as you already described.

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


title: Modified Quicksort*

text:
# Question
Title: Modified Quicksort*
given array of size n, and a function called FindPivot which returns the median with a time complexity of O(n^(1.1)). what is the worst case time complexity of quicksort using the given func to find pivot?

the answer given by the teacher is theta(n^(1.1)) I thought it should be theta(n^1.1logn) please explain

# Answer
> 0 votes
Since the function returns the median, the time complexity of (this version of) Quicksort is described by the recurrence equation: $$ T(n) = 2 T(n/2) + O(n^{1.1}). $$

By the Master theorem, this has solution $T(n) = O(n^{1.1})$.

It is not possible to conclude that $T(n) = \Theta(n^{1.1})$ from the given information since, e.g., FindPivot might run in time $\Theta(n)$ (recall that $\Theta(n) \subset O(n^{1.1})$), in which case the resulting complexity would be $\Theta(n \log n)$.

If we further assume that FindPivot runs in time $\Theta(n^{1.1}$) then the recurrence equation becomes $T(n) = 2 T(n/2) + \Theta(n^{1.1})$, which has solution $T(n) = \Theta(n^{1.1})$.

# Answer
> 0 votes
Intuitively, many small components of equal size in a recursion formula often result in a log n factor, which is smaller than any power.

In your case, your recursion has 2 * T(n/2) ≈ T(n) * 2 / 2^1.1 = T(n) / 2 ^1.1. Now the smaller components in your recursion shrink like a geometric series. You are not adding up items of equal size, so there is no factor log n.

Note that if we just compare n^1.1 and n ln n, the first one is larger from n = 5,000,000,000,000,000 and then quickly gets a lot faster.

---
Tags: time-complexity, quicksort
---


# Question
Title: Algorithm to determine the regularity of a language
According to the answer provided by Janoma, there are several methods to determine the regularity of a language.

## Theorem

Let **L ⊆ Σ∗**. The following conditions are equivalent:

* **L** is generated by a **regular expression** (i.e., the definition of regular language).
* **L** is recognized by a **nondeterministic finite automaton** (Kleene).
* **L** is recognized by a **nondeterministic finite automaton without ε-transitions**.
* **L** is recognized by a **deterministic finite automaton** (Scott and Rabin).
* **L** is generated by a grammar **(N, Σ, P, S)**, where **N** is a finite subset of **Σ∗** (Frazier and Page).
* **L** is generated by a **left (resp. right) regular context-free grammar**.
* The index of the **Nerode relation ≡L** is finite (Anil Nerode, Linear automaton transformations, 1958). This is widely (and incorrectly) known as the **Myhill-Nerode theorem**. ≡L is the relation used to build the minimal DFA of a regular language.
* The index of the **Myhill relation ∼L** is finite (John Myhill, Finite Automata and the Representation of Events, 1957). ∼L is the relation used to build the syntactic monoid of an arbitrary language.
* The **syntactic monoid of L** is finite (consequence of Myhill's result). We note here that the syntactic monoid, apart from being defined by using relation ∼L, can be defined as a minimal monoid (in size) that recognizes **L as a preimage of a homomorphism**.
* **L** can be recognized by a **read-only Turing Machine** (trivial).
* **L** can be defined by a formula in **Monadic second-order logic over strings** (Büchi).

However, in none of these methods is there a clear, step by step process that can be followed to conclusively prove that a language is regular.

Does such an algorithm exist? Please provide the necessary references as well.

# Answer
Of course one would first have to specify the language to apply the regularity algorithm. Even for a rather restricted class of language specifications such an algorithm would be impossible.

It is undecidable, for a given context-free grammar, to decide whether it accepts a regular language.

Theorem 6.3 (c) in: Bar-Hillel, Perles, Shamir, On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung 14 (1961) 143–172. doi 10.1524/stuf.1961.14.14.143
> 3 votes

---
Tags: algorithms, regular-languages, automata, finite-automata, regular-expressions
---


# Question
Title: Would using the mean as pivot speed up quicksort?
Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was: 'If we could consistently choose a pivot from the middle 50 percent, we would only have to split the list at most $\log\_{4/3} n$. The choice of the pivot seems to be one possible problem of quicksort that can lead to $O(n^2)$ behavior.

My idea was: **If in each step one would use the mean of the partition as pivot**, this could increase the speed significantly. Especially after a few steps, when outliers are in their own division of the list, the mean and median should be very close to each other (once again, looking at large lists). The additional time during each step to calculate the mean should be $n$. Therefore:

Quicksort estimated time: $nA\log\_{4/3} n$

Quicksort\_mean estimated time: $2nA\log\_{5/3} n$

(5/3 is most likely a conservative estimation by me, could as well be closer to 2, as subsets should quickly be without outliers). So, starting at around 10,000 entries Quicksort\_mean would be (on average) faster than Quicksort. Furthermore, it would never risk to be $O(n^2)$, as it is bound to not take the minimal or maximal element of the stack.

My main question is: Did I miss anything? I have to admit, I never implemented quicksort myself, so I might miss out on other parts of the whole thing (storage, etc.)

# Answer
Using the mean for your partition does not prevent the $\Omega(n^2)$ worst-case behavior. It occurs when the input list is exponentially increasing. Consider the input:

$1,n^2,n^3,\ldots,n^n$

The mean of this set is (asymptotically) $n^{n-1}$ so you obtain the worst partition possible. This is a bit of a cheat considering that storing the list takes $\Omega(n^2)$ space if the numbers are represented as integers. But if you are sorting floating-point numbers then this scenario is concievable.

However, it is possible to calculate the *median* of a set (or any other order statistic for that matter) in $O(n)$ time so if you really care about run time guarantees for quick sort you should use that rather than the mean.

However, in all practical scenarios the additional cost of computing the mean/median is so large that picking a random pivot almost always is faster.
> 10 votes

# Answer
There are two problems. One problem is that finding the mean is work as well, so you need a gain that more than pays for that.

The second problem is that often people look at the number of comparisons. But you have comparisons and data movement. If the pivot is not exactly in the middle, then you actually reduce the number of data movements. So minimising the number of comparisons might actually increase the total execution time. (If you take a sorted array and take the first array element as pivot, then you only have O(n) data movements. If each data item is an array of 1000 strings of 1000 characters on average, and you sort by comparing the first character of the first string, and n isn't extremely large, then the worst case number of comparisons might be fastest.

But in general, given the ratio of cost of data movement vs. cost of comparisons, there is an optimal pivot which often isn't the exact middle.
> 0 votes

# Answer
A serious reason that prevents us from using the mean is that in general it is not computable. For instance, you can't get the mean of two strings. This disqualifies the mean for general-purpose sorts.

For the cases that the keys are scalar numbers, the effectiveness will depend on their distribution.
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting, quicksort
---


# Question
Title: How a simple algorithm of adding two numbers can be written in lambda calculus?
It is claimed that "lambda calculus is a universal model of computation that can be used to simulate any Turing machine". How can I, using this universal model, simulate an algorithm of calculating an algebraic sum of two numbers? How will this algorithm look, according to the grammar of the calculus, which does NOT include the `+` operator?

There is also a follow up question: may I introduce my own $X$-calculus, which would also be called a "universal model of computation" and will consist of a single letter $X$?

# Answer
The lambda calculus not only has no `+` operator, but also lacks natural numbers. All it has are functions. The idea is to *represent* a natural as a specific function, and then define another addition-function to perform addition on said natural-functions (called numerals).

A natural number $n$ is represented as $\lambda sz. s(s(s(s \ldots z)))$ where there are exactly $n$ application of $s$ inside. Roughly, this representation makes $n$ to be written as a function operator that takes function $s$ and returns its $n$-th iterate $s^n = s \circ s \circ \ldots$.

After that, one can define a successor operation as $Succ = \lambda nsz. s(nsz)$. You can verify that reducing $Succ\ n$ when $n$ is a numeral will lead to the next numeral.

Similalrly, addition can be coded as repeated successor e.g. $Add = \lambda nm. n\ Succ\ m$. Again, one can verify that it operates as expected on numerals.

In this way we can walk a long run and slowly build all basic arithmetics and simulate natural numbers. We can also encode booleans, strings, and other standard data types using suitable functions. Eventually, we also define fixed point combinators that allow us to form recursive functions. After that we can write a lambda term that can simulate the execution of a Turing machine, so proving the Turing completeness of the language.

Regarding the question on the "X-calculus". Yes, you can definitely invent your model. You must define what are the "programs" in your model (e.g. the set of lambda terms, the set of Turing machines, the set of strings of the form $XXX\cdots$, etc.). Then you must associate them with a semantics. How do you run your programs? You need to define a semantic relation to formalize "this program computes this naturals-to-naturals function". After that, you have a model of computation and can check whether it's Turing powerful or not.
> 4 votes

---
Tags: lambda-calculus
---


title: What are non-isomorphic NFAs

text:
# Question
Title: What are non-isomorphic NFAs
I came across the following problem while doing my Formal Language class assignment and hope someone can give me some hints:

1. I have $\Sigma = \\{0,1\\}$ and $L=\\{x0a \mid x \in \Sigma^\*, a \in \Sigma\\}$, namely $L$ contains all strings whose second-to-last character must be a $0$.
2. I have found that there are four equivalence classes of $I\_L$, namely $\[\epsilon\], \[0\], \[00\], \[01\]$, and I'm able to construct a DFA using this four equivalence classes to accept the language $L$.
3. Then, I'm asked to show that there are at least three non-isomorphic NFAs of minimum size that all can accept $L$. I think the smallest NFA must have at least three states since if a NFA has only two states, this implies that there exists a single character that can be accepted by this NFA which is not true for the language we have.

Can someone provide some hints regarding how to approach this?

# Answer
Your argument that two states are not enough seems solid. The automaton needs a simple path of length two where only the last state is accepting.

Once we know this we can play with the automaton. Create three states: initial state $0$, seen letter $0$ as state $1$, and accept after $0a$ as state $2$. From this we can add extra edges to ensure that all and only strings ending in $0$ will reach the middle state $1$.
> 1 votes

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


title: Why is 3-co-SAT not in P?

text:
# Question
Title: Why is 3-co-SAT not in P?
The 3-co-SAT problem consists of deciding whether if a 3CNF formula, has an unsatisfiable assignment of variables, i.e., assignment of variables that evaluates to 0.

We know that 3-co-SAT is in coNP, however, I do not understand why it is also not in P? It seems to be very easy to check whether if there exists an unsatisfiable assignment of variables as follows:

1. Iteratively go through each clause.
2. For each clause try $2^3 = 8$ possible variable assignments. If there exists an assignment that makes the clause evaluate to False, accept.
3. If no clauses evaluated to False, reject.

This algorithm has runtime $8m$ where $m$ is the number of clauses, and it accepts a string if it is in coSAT no?

# Answer
> 4 votes
co-SAT is not asking whether there exists an unsatisfying assignment, it is asking if every assignment evaluates to false.

---
Tags: np, decision-problem, co-np
---


# Question
Title: Algorithm for finding a path in a directed graph that visits each node in a given subset
I was wondering about a solution for the following problem:

> Given a directed graph $G=(V,E)$ and a subset of vertices $U \subseteq V$ suggest an algorithm that finds if there is a directed path that visits every node in $U$. The path can revisit vertices/edges. The path can visit vertices not in $U$ repeatedly as well.

I was thinking about running DFS\BFS from each vertex but it feels inefficient, I'll be grateful for any insights.

Source: Open University of Israel - Algorithms course, written by Dr. Daniel Reichman, fall semester 2012-2013.

# Answer
> 1 votes
Instead of "path", Let us use "walk" for a sequence of edges which joins a sequence of vertices (that can revisit vertices and edges). We will reserve "path" for its usual meaning, a walk in which all vertices are distinct.

This answer describes a linear algorithm that given a directed graph $G=(V,E)$ and $U \subseteq V$, finds if there is a walk that visits every node in $U$. The main idea is to take advantage of the longest distances from the root in a directed acyclic graph (DAG) to speed up the search for a path.

### Reduce to a rooted DAG

Compute the condensation of $G$, a DAG that which is attained when each strongly-connected component of $G$ is contracted to a single vertex. This DAG is called "the meta-graph of strongly connected components" in D.W.'s answer. The computation can be done by any one of the linear-time algorithms.

Denote the condensation of $G$ by $G'=(V', E')$. Let $U'$ be the vertices in $V'$ that represent the strongly-connected components that contain at least one vertices in $U$. Since $G'$ is acyclic, any walk in $G'$ is a path.

Add a vertex $s$ to $G'$ and an edge from $s$ to every root of $G'$. (A vertex in a DAG is called root if there is no incoming edge to it). Now $G'$ is a connected DAG with a unique root, $s$.

The problem is transformed to finding if there is a (walk) path in $G'$ that visits every node in $U'$.

Replacing $(G, V, E, U)$ with $(G', V', E', U')$, we will assume henceforth that $G$ is is a connected DAG with the unique root $s$.

#### Longest distance from $s$ to each vertex

For each $v\in V$, let $dist\[v\]$ be the longest distance from $s$ to $v$, i.e., the biggest number of edges in a path from $s$ to $v$.

Here is a simple and useful property of $dist$. If there is an edge or a path from vertex $v\_1$ to $v\_2$, then $dist\[v\_1\]\<dist\[v\_2\]$.

Compute $dist$ using dynamic programming as follows.

1. Initialize a hash table/hash map $dist$ with $dist\[v\] = 0$ for all $v\in V$.
2. Create a topological order of all vertices. This can be done by some linear-time algorithm.
3. For every vertex $v\in V$ in topological order,
    * For every adjacent vertex $w$ of $v$:
        + if $dist\[w\] \< dist\[v\] + 1$: $\quad dist\[w\] = dist\[v\] + 1$.

#### Check if there is a path from $u\_i$ to $u\_{i+1}$

Sort all vertices in $U$ by $dist\[\cdot\]$. Since $dist\[v\]$ is an integer between $0$ and $|V|$ for every vertex $v$, this sorting can be done in linear time with counting sort. (We can also simply select all vertices in $U$ from the sequence obtained in the step 2 above.)

Let $U=\\{u\_1, u\_2, \cdots\\}$, $dist\[u\_i\]\le dist\[u\_{i+1}\]$.

For $i$ from $1$ up to $|U|$, do the following:

1. If $dist\[u\_i\]=dist\[u\_{i+1}\]$, there is no wanted path. The algorithm ends.
2. do a breadth-first search (or a depth-first search) starting with $u\_i$, in order to check if there is a path from $u\_i$ to $u\_{i+1}$. To speed up the search, whenever we see an edge that ends at a vertex $w\not=u\_{i+1}$ such that $dist\[w\]\ge dist\[u\_{i+1}\]$, we will remove that edge from $G$ and ignore $w$, since for all $j\ge i$, no path from $u\_j$ to $u\_{j+1}$ can include that edge. (Note that edge must start at a vertex with $dist$ smaller than $dist\[u\_{i+1}\]$.)
3. If $u\_{i+1}$ has not been reached, there is no wanted path. The algorithm ends.

When the algorithm have reached here, we know there is path from $u\_i$ to $u\_{i+1}$ for all $i$. Connecting all paths together, we obtain a path that passes all vertices in $U$.

Note the for-loop accesses each edge in $U$ at most once. Hence it takes linear time to complete the for-loop.

#### Linear-time complexity

It takes linear time to do each step of the three steps above. Hence this algorithm runs in linear time.

Some of the steps in the algorithm can be implemented faster. For example, when we compute the condensation of the original $G$ using Kosaraju's algorithm, we may obtain the topological order of $V'$ and $U'$ in parallel. We may also compute $dist\[\\,\]$ at the same time.

# Answer
> 1 votes
Hint:

> Work through a few small examples of graphs. Draw a few graphs with \<= 8 vertices on a piece of paper, mark a subset of vertices, and check whether there is a path. See what patterns can spot from trying to solve each one by hand, one small problem at a time.

If that's not enough, here's a bigger hint:

> Draw the meta-graph of strongly connected components. Do the same as above, with this additional information.

---
Tags: algorithms, graphs, directed-graphs, linear-complexity
---


# Question
Title: How can I prove rigorously that $\log x = o(\sqrt{x})$?
For my MSc thesis, I need to prove rigorously that $\log x = o(\sqrt{x}).$ How can I do it?

# Answer
> 2 votes
Using L'Hôpital's rule: $$ \lim\_{x \to \infty} \frac{\log x}{x^{1/2}} = \lim\_{x \to \infty} \frac{(1/x)}{(1/2) x^{-1/2}} = \lim\_{x \to \infty} \frac{2}{x^{1/2}} = 0. $$

Therefore, for any $c\>0$, there exists some $n\_0$ such that, for all $n \ge n\_0$, $\log x \le c \sqrt{x}$. This satisfies the definition of Little-o notation.

# Answer
> 2 votes
You will probably admit

$$z=o(e^z)$$ (which is obvious by Taylor).

Then with $z=\alpha\log(x)$,

$$\alpha\log(x)=o(x^\alpha)$$

and you can drop the factor $\alpha$ in the LHS.

---
Tags: upper-bound
---


# Question
Title: Partitioning a set based on a non-equivalence relation
I have a set of $n$ elements, and a binary relation between these elements. However, this is **not** guaranteed to be an equivalence relation. (Specifically, the elements are line segments in a plane, and the relation is intersection: if $A$ intersects $B$, and $B$ intersects $C$, $A$ may or may not intersect $C$.)

I would like to partition this set such that no two elements in the same subset intersect. This can be done trivially by putting every element in its own subset. But I would like the number of subsets to be as small as possible (meaning each subset is as large as possible).

Is this a standard problem, and/or is there a standard algorithm to achieve it? My current thought is to use something akin to a greedy algorithm. Start with a single bin, then iterate through the elements. Test each element against each bin; if it intersects with any element in that bin, move on to the next one. If it intersects something in *every* bin, make a new one. Off the top of my head, this would seem to run in $O(n^2)$ time, since at worst we're comparing every element against every other element. But I'm curious if there's a cleverer algorithm I'm missing—or if there's some pathological input that will make this algorithm use far more subsets than necessary.

# Answer
This problem is called **Interval Partitioning Problem**, and it can be solved in $O(n\log n)$ time by a greedy algorithm.

You can refer to this courseware for details.

Actually, this problem can be reduced to the Graph Coloring Problem: for each segment $E$ in your problem, there is a corresponding vertex $v\_E$ in the constructed graph, and if segment $A$ intersects segment $B$, then there is an edge $(v\_A,v\_B)$ in the graph.

When segments are in one dimension, the constructed graph is an interval graph, so it can be solved by a greedy algorithm.
> 1 votes

---
Tags: algorithms, partitions
---


# Question
Title: Add minimum numbers of edges to the graph for the existence of an eulerian path
Question is **add minimum number of edges so that this given graph consists an eulerian path (but not necessarily an eulerian circuit). Why do edges less than these given edges won't suffice?**

As I solved this question, it turns out that an eulerian path can exist by removing more than one edge. Does it work as a contradiction? Or is it possible to add more edges in the graph to get the result?

Here's my solution with series of vertex showing that an eulerian circuit can exist by removing edges.

# Answer
This problem is described by Borsch et al. (1977), who showed that adding edges to make an Eulerian graph is polytime solvable.

If you want to delete edges, the story changes, and the problem is NP-complete, see Cygan et al. (2014).

The proof? A cubic planar graph has a Hamiltonian path of and only if you can delete edges to make it Eulerian.

References

1. F. T. Boesch, C. L. Suffel, and R. Tindell. The spanning subgraphs of eulerian graphs. Journal of Graph Theory, 1(1):79–84, 1977.
2. M. Cygan, D. Marx, M. Pilipczuk, M. Pilipczuk, and I. Schlotter. Parameterized complexity of eulerian deletion problems. Algorithmica, 68(1):41–61, 2014.
> 2 votes

---
Tags: graphs, eulerian-paths
---


# Question
Title: Comparison between big-Ω and ω notations
Example of function f(x) such that it is true that `f(x) = Ω(g(x))` but that it is not true that `f(x) = ω(g(x))`

# Answer
> 1 votes
Pick $f(x) = g(x) = x$. Then $f(x) \in \Omega(g(x))$ and $f(x) \not \in \omega(g(x))$.

# Answer
> -2 votes
```
f(x) = Ω(g(x)) , f(x) = ω(g(x))
Ω(g(x)) = ω(g(x))
0 = (ω - Ω)(g(x))

```

We have a TRUE statement whenever the difference between small omega and big omega approaches zero.

Define indicator function: when big omega, then TRUE, else (small omega) -\> FALSE.

---
Tags: algorithms, asymptotics, big-o-notation
---


# Question
Title: How to determine if a set of edges is an edge cut of a graph?
An **edge cut** of a graph $G$ induced by **a partition** of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in $Y$.

An **edge separator** is a set of edges whose removal will increase the number of connected components in the graph.

Note that these are two distinct concepts and cannot be considered equivalent.

An edge separator is not necessarily an edge cut. For example,

For the complete bipartite geaph $K\_{3,3}$, a set of any seven edges of $K\_{3,3}$ is an edge separator, but a set of any seven edges of $K\_{3,3}$ is not an edge cut.

For another exmaple,

The brown edges highlighted in the above Figure represent an edge-separating set, but it is not an edge cut. The set of brown edges on the right is an edge cut.

It is easy to determine whether a set of edges is an edge separator. **But how do we determine if a set of edges is an edge cut of a graph?** I don't have a good idea yet, but I have a rough idea which is to color the set of vertex-ends of edges under consideration and then see if a partition as defined by the edge cut can be found.

# Answer
As you say, a *cut* in a graph $G=(V,E)$ is an edge set $C$ with the property that you may partition the vertices of $G$ (let's call the parts $A$ and $B$) in such a way that $C$ is exactly the set of edges with one end in $A$ and the other in $B$. This implies that the subgraph $H=(V,C)$ is bipartite with color classes $A$ and $B$. However, it is not enough to check that $H$ is bipartite, as this may disregard vertices that should be on the same side.

A good trick to use in a situation like this is *contraction*, i.e. we shrink every component of $\overline{H}=(V,E-C)$ down to a single vertex and let the edges in $C$ go between these instead. A simple way to achieve this is to find all the components of $\overline{H}$ (just run your favorite search algorithm on the graph until all vertices are seen), and build a new graph $\widetilde{H}$ where:

* Each vertex corresponds to a component of $\overline{H}$
* Each edge corresponds to an edge in $C$, with the endpoints corresponding to the components of endpoints of the original edge
* Multiple edges and loops are allowed

Now, $C$ is a cut in $G$ if and only if $\widetilde{H}$ is bipartite and has no loops.

I made the graphs $\widetilde{H}$ corresponding to the graphs in your figure to make it a bit more clear:

You should be able to do all of this in $O(|V|+|E|)$ time.
> 2 votes

---
Tags: graphs
---


# Question
Title: “Converting” networkx / osmnx graph to a planar graph
I am currently working on some analyses of the Berlin road network, and I am using OSMNX to get a relevant graph representation. I noticed that - if with drawbacks - many authors use planar representations when working with road networks. Geoff Boeing, the author of osmnx, has concerned himself with the issue, too (https://geoffboeing.com/publications/planarity-street-network-representation/, here for full text).

So suppose I have a non-planar graph, what would be the easiest way to make it planar? More specifically, I would like to make it planar by adding nodes at places where edges intersect, instead of removing edges until the graph is planar, as suggested elsewhere. Do you know of any algorithm in python that is able to do that?

I found that, in some instances, downloading the raw (non-simplified) data from OSM using OSMNX, one obtains a planar graph of a place, however, this is not the case for Berlin as a whole.

I would be very happy about any hints, suggestions, and help given. Thanks!

# Answer
> 3 votes
The Bentley-Ottmann algorithm can be used to find all intersections between edges, and then you can add a node at each such intersection.

# Answer
> 2 votes
The algorithm consists of converting a Voronoi diagram, which is a partitioning of a plane into regions based on the distance to points in a specific subset of the plane, into a weighted graph represented by a networkx object in Python.

The input to the algorithm is a list of points in two dimensions. The Voronoi diagram is computed using the scipy.spatial library, which returns a set of vertices and edges representing the diagram.

The algorithm then iterates through the edges of the Voronoi diagram and checks if each edge connects two points whose coordinates lie in the range \[0,1\]. If so, the edge is added as an edge in the networkx graph, with a weight equal to the Euclidean distance between the two endpoints of the edge.

Finally, the resulting networkx graph is returned as output. This graph represents the Voronoi diagram as a weighted graph, where the vertices correspond to the points in the input list and the edges represent the borders between the Voronoi regions. The weights on the edges represent the lengths of these borders.

The algorithm for converting a Voronoi diagram into a weighted networkx graph is useful for generating planar graphs in several ways.

Firstly, the Voronoi diagram itself can be thought of as a planar graph, where the vertices represent the input points and the edges represent the borders between the Voronoi regions. This graph can be used for various applications, such as geographic information systems, computer vision, and computational geometry.

```
import numpy as np
import networkx as nx
from scipy.spatial import Voronoi,voronoi_plot_2d
import matplotlib.pyplot as plt

#we create a function to generate a planar graph from a voronoi diagram

def voronoi_to_networkx(points):
# we get the voronoi diagram
  vor = Voronoi(points)

  G = nx.Graph()

# Add an edge for each ridge in the Voronoi diagram that connects two points in the range [0,1]
  for simplex in vor.ridge_vertices:
      if -1 not in simplex:
          i, j = simplex
          p = vor.vertices[i]
          q = vor.vertices[j]
          if 0 <= p[0] <= 1 and 0 <= p[1] <= 1 and 0 <= q[0] <= 1 and 0 <= q[1] <= 1:
              distance = np.linalg.norm(p - q) # Calculate the Euclidean distance between p and q
              G.add_edge(tuple(p), tuple(q),weight=distance)

  return G

#We create 20 points from which the voronoi diagram will be generated
points=np.random.rand(20,2)

#we plot the diagram
vor=Voronoi(points)
voronoi_plot_2d(vor)
plt.show()

#We convert diagram to networkx
graph=voronoi_to_networkx(points)
#We assign each node to its actual position in the plane
pos = dict(zip(graph.nodes(), graph.nodes()))
nx.draw(graph, pos,node_size=5)
#We check that the graph is planar.
print(nx.is_planar(graph))
plt.show()

```

---
Tags: algorithms, graphs, python
---


# Question
Title: Turning an undirected graph into a directed graph such that in-degree of all nodes is at most 1 or show it is not possible
I was thinking what if you just started with the node with lowest non-zero degree $u$ (only count undirected edges) and picked random edge that is connected to that and direct that inwards. EX: undirected edge $uv \to (v,u)$. Then repeat, ignoring nodes that have reached the at-most-one limit. At the end, you check to see if there are any undirected edges left. If yes then output impossible;if no then you have a valid solution.

I'm not sure if this works though.

# Answer
> 1 votes
Your algorithm works. The main concept here are tree and cycle.

#### it is possible iff no cycles or one cycle

**Claim**: Let $G$ be an undirected connected graph. $G$ can be turned into a directed graph with in-degree at most $1$ iff $G$ has no cycles or exactly one cycle.
**Proof**: "$\Leftarrow$":
If $G$ has no cycle, it is a tree. Pick any node as the root, it is easy to change an undirected tree into a directed rooted tree.

If $G$ has one cycle, change that cycle into a directed cycle. Contract this cycle into one vertex so that $G$ becomes an undirected tree. Using that vertex as the root, change $G$ into a directed rooted tree. We have, in fact, assigned a direction for each edge in the original $G$ so that it becomes a directed graph with in-degree at most $1$.

"$\Rightarrow$":
Suppose $G$ is turned into directed graph $G'$ with in-degree at most $1$.

Consider $G'$. Since different edges must have different tails, the number of edges is no more than the number of nodes.

Since $G$ and $G'$ have the same number of edges and the same number of nodes, the number of edges in $G$ is no more than the number of nodes in $G$. As a connected graph, $G$ has at least $|V|-1$ edges.

* $G$ has $|V|-1$ edges.
Then $G$ must be a tree, which has no cycles.
* Otherwise $G$ has $|V|$ edges.
Let $T$ be a spanning tree of $G$, which has $|V|-1$ edges. $G$ is $T$ plus one edge. So $G$ has exactly one cycle.

#### Your algorithm works

It is enough to show your algorithm works on each connected component.

Assume the given graph, $G$ is connected.

If $G$ has more than one cycle, then it is impossible to change $G$ as wanted. Your algorithm must return "impossible" as well.

If $G$ has no cycle, your algorithm will pick a leaf every time. In the end, your algorithm will produce a directed rooted tree.

If $G$ has one cycle, your algorithm will pick a leaf every time until every node that is incident to an undirected edge is incident to more than one undirected edge. Upon that time, all those nodes together with all undirected edges form the unique cycle in $G$. Your algorithm will assign a direction to one of the undirected edges. Then spread the direction either way along the cycle one edge at a time. In the end, every node will have in-degree $1$.

#### Another algorithm

Split the given graph $G$ into connected components.

For each connected component $C$, check the number of edges in it.

* If it is more than the number of nodes, return "impossible" (and end the entire algorithm).
* If it is less than the number of nodes, $C$ is a tree. Pick any node as the root. Make $C$ a directed rooted tree.
* Otherwise, there is a unique cycle in $C$. Find that cycle. Change that cycle into a directed cycle. Imagine the nodes in the cycle as one (super-)node. Picking that node as root, make $C$ a directed root tree.

This algorithm is not necessarily faster or easier to implement than your algorithm. It is, however, clearer what is going on with this algorithm.

---
Tags: algorithms, graphs, directed-graphs
---


# Question
Title: Why would we want to define new types in a functional programming language?
I am a total noob to programming, and one of the basic ideas in Haskell is how one can define new types using some things called constructors. I haven't quite understood it fully, but why would one want to make any types beyond the basic ones? What practical utility does it hold?

# Answer
If you write a banking system, you will have entities representing users, accounts, transactions, balances, money, … If you write a game, you will have entities representing players, levels, maps, enemies, NPCs, weapons, vehicles, … If you write a media player, you will have entities representing albums, tracks, artists, …

Without the ability to define your own types for all of those entities, the language would have to ship with every single type that every single programmer could possibly need for every single program that will ever be written … including types for concepts that don't even exist yet!

You can see how it is much more convenient to allow the programmer to define their own types than to try and predict the needs of every programmer who will ever be born.
> 2 votes

# Answer
Suppose you have to use a data type multiple times in multiple functions ,one way is to use the primitive data types again and again ,Other way is to use type synonyms to gove the desirred name to the primitive type.That's ehere the idea of custom type comes in to give a name to a data type composed of multiple primitive data types and to define operations on those types using structyural induction.Example-

```
type Sentence = String
wordList Sentence= spllitat ' ' Sentence
``

```
> -1 votes

---
Tags: type-theory
---


# Question
Title: Approximate euclidean graph from distance matrix?
In a personal project of mine, I have been faced with the following problem. I have an $n \times n$ matrix $T$ where an entry $t\_{ij} \geq 0$ denotes an arbitrary metric between two points $i$ and $j$ in the 2D Euclidean space.

What I would like to do is create a graph $G=(V,A)$ which can approximate matrix $T$ where $|V|=n$. The goal is to assign coordinates $(x\_i,y\_i)$ for each point $i \in V$. This should be done in such a way that the Euclidean distance $d\_{ij}$ between $i,j \in V$ defined as

$d\_{ij} = \sqrt{(x\_i-x\_j)^2 + (y\_i-y\_j)^2}$

should approximate $t\_{ij}$ as much as possible. Hence:

$d\_{ij} \approx t\_{ij}$

There is one additional constraint: the points need to be placed within a circle of radius $R$.

So far I have tried to approach this problem from a mathematical programming point-of-view. Unfortunately, my experience is mostly with linear programming but the problem I have at hand appears to be non-linear. Here is the model I have developed, where $x\_i$ and $y\_i$ are real-valued variables.

$\min \sum\_{i \in V}\sum\_{j \in V}|d\_{ij}-t\_{ij}|$

$\text{s.t. }$

$d\_{ij} = \sqrt{(x\_i-x\_j)^2 + (y\_i-y\_j)^2}$

$d\_{0j} \leq R,\ \forall\ j \in V,\ \text{0 refers to coordinate } (0,0)$

$x\_i,y\_i \in \[-R,R\],\ \forall\ i \in V$

This way we know that an optimal solution would exist when the objective function is exactly 0.

However, I still have open questions which I cannot seem to find the answer to:

1. Is this the best way to model such problem?
2. How can I solve this model? Are there algorithms or solvers (e.g., CPLEX) for such model?
3. Does this problem already exist with some name in the literature?

Can anyone shed some light on this problem?

# Answer
The exact version of your problem, where the distances are known exactly and the goal is to exactly match those distances, is known as the distance geometry problem. The approximate version, as you formulate it, seems similar to the multidimensional scaling problem.

The approach you sketch looks like a reasonable approach to the problem, and I imagine you could use any optimization method to try to minimize your objective function, including gradient descent or Newton's method. The initial placement of points might make a big difference to the quality of the solution so you might try making many runs with different random initializations, and keep the best solution you've found so far.

You could also try adapting force-directed graph drawing to your problem. You have a preferred distance $t\_{ij}$ between each pair of vertices $i,j$, so you can treat this as a spring that exerts a force if its length is larger than $t\_{ij}$ or smaller than $t\_{ij}$.

See also https://softwareengineering.stackexchange.com/q/243199/34181, https://mattermodeling.stackexchange.com/q/5088, https://scicomp.stackexchange.com/q/40855/4274, https://math.stackexchange.com/q/156161/14578, https://mathoverflow.net/q/97611/37212, https://mathoverflow.net/q/7794/37212, https://math.stackexchange.com/q/3047212/14578.
> 1 votes

---
Tags: algorithms, mathematical-programming
---


# Question
Title: PDA of the language where the number of a's are NOT equal to the number of b's
I have this NPDA for language `L = {w: num_a(w) == num_b(w)}`
all loops in q1 `a, $ -> 0$ b, $ -> 1$
a, 0 -> 00 b, 1 -> 11
a, 1 -> \lambda b, 0 -> \lambda` `------>q1-----------------\lambda, $ -> $------>q2` initial state: q1
final state: q2
What if I modified `L` such that the number of a's is not equal to number of b's.
That is `L' = {w: num_a(w) != num_b(w)}`. What would be the modification I have to make in the original NPDA.

# Answer
> 3 votes
Your PDA can act as follows. For each $a$ being read, it pushes $A$ into the stack. Then, for every $b$ being read, it attempts to pop $A$ off the stack. If there are no more $A$s, it moves to an accepting state, checking that the rest of the input consists of $b$s; this handles the case in which there are more $b$s than $a$s. Alternatively, it could decide at some point to move, via an $\epsilon$ transition that pops an $A$, to a different accepting state at which no more symbols can be read; this handles the case in which there are more $a$s than $b$s.

# Answer
> 0 votes
For the number of a's to be unequal to the number of b's, either they are more a's or b's.

---
Tags: regular-languages, context-free, pushdown-automata, nondeterminism
---


# Question
Title: How do we approach this variant of Gaussian Elimination problem
Consider a set of $N$ vectors (each of Length $L$) with positive integer as elements. Given a target vector $T$ of length $L$.

Objective: Using the given set of vectors (by addition or subtraction) reduce $T$ to the form $T'$ such that:

1. all entries in $T'$ are either 0 or 1.
2. the first entry of $T'$ is 0.

How do we approach this problem? I think it can be solved by something similar to Gaussian Elimination but I am not so sure. Can someone please comment.

# Answer
> 2 votes
Regardless of whether we can use each vector more than once, we can always restrict the solutions of an arbitrary instance to those that use each vector at most once and perform only subtractions.

Indeed, we can append $N$ additional entries $x\_1, \dots, x\_N$ to each vector. The generic $i$-th input vector has all these entries set to $0$ except for $x\_i$, which is set to $1$. The target vector has all these entries set to $1$.

Then it is possible to reduce the exact cover problem to this version of your problem: index the items in the exact cover instances with the integers from $1$ to $N$ and create a vector $v\_S$ for each set $S$. Set the $i$-th entry of $v\_S$ to $2$ if item $i$ is in $S$ and to $0$ otherwise. All entries in the target vector are set to $2$.

There is a solution to your problem if and only if there is an exact cover. This shows that your problem is NP-hard.

If repetitions are allowed it is easy to design a $O^\*(2^L)$-time algorithm: guess the final values of the entries of of $T'$ (i.e., either $0$ or $1$) and solve a system of linear Diophantine equations.

If repetitions are not allowed the trivial exhaustive algorithm runs in time $O^\*(2^{2N})$. However, if $L\<N$ you can design a $O^\*(2^{N+L})$ algorithm by guessing $T'$ and using the "split and list" technique.

---
Tags: algorithms
---


# Question
Title: Is it true that $R.L^* + L^* = R + L^*$?
I am trying to solve a problem to show equivalence between two regular expressions, and simplifying one of them I got $R.L^\* + L^\*$ in the end which I am not sure how to simplify further.

I want to equate it to $R + L^\*$. Is this equivalence correct or is there a way to derive it?

# Answer
That's false in general. Pick $R = a$ and $L=b$. The word $ab$ is in the language defined by $RL^\* + L$ but not in the language of $R+L^\*$.

It might be true for your specific choice of $R$ and $L$.
> 1 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Can a DFA have multiple of the same state?
I need to create a DFA for a *sequential* order of states e.g. A -\> B -\> C -\> B -\> A
and so on, where 'A' is the start and finish state, 1 is a transition to the next state and 0 just loops back to the current state. 1 and 0 are the only inputs

The only way I've found I can do it in this order is by having 2 B states, Is this ok or is there another way to do this?

# Answer
Ask yourself this: what do you mean by *the same state*? In particular, why do your two $B$ states need to be the *same* state and what value does that give you over treating them as two separate states?

For a more thorough answer: consider the formal definition of the DFA, which includes the transition function $\delta(Q \times \Sigma) \rightarrow Q$ ($Q$ being the set of states, $\Sigma$ being the set of input symbols). The notion of there being "duplicate" states is already invalidated by $Q$ being a *set* of states, but since the actual behavior of the automaton emerges from the state transition function, let's consider the implication of there being duplicate states regarding that.

Let's call the two states you've labeled $B$ by the names $b\_1$ and $b\_2$. Since you want them to be the same state, $b\_1 = b\_2$. Since $\delta$ is a function, for any $\sigma \in \Sigma$ it must therefore hold that $\delta(b\_1, \sigma) = \delta(b\_2, \sigma)$. In English: if $b\_1$ and $b\_2$ are the *same* state they cannot behave differently between each other wrt. the state transition function. Therefore your $B$ states must be separate states: if $\delta(B, 1) = C$ at one point, it will be that, always.

Naturally, this does not invalidate your automaton in other ways – what you want to define is probably possible, but the notion of there being multiples of the same state is incompatible with the definition of DFA, and I don't see any value in trying to fudge the formalism to make them possible either.
> 2 votes

# Answer
A DFA must have at most a single transition on a given input. In your example, being in state $B$ and reading a 1 you have two choices for the resulting state: go to $A$ or $C$. You could, though have a nondeterministic FA that would achieve this. The resulting language would consist of all strings of $1$s of even length.
> 0 votes

---
Tags: algorithms, complexity-theory, finite-automata
---


# Question
Title: Is pumping lemma not applicable for every 'long enough' string in the language?
I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So does a non-regular subset have strings only length $\<p$? But if they have length $\<p$, can't they be trivially pumped?

# Answer
Being a subset of a regular language does not have to be based on the length of the strings. It can be constructed based on other properties of the strings.

I assume that by now you already know that the language $L\_1$ containing strings with equal numbers of 1 and 0 is not regular. Notice that this is a subset of the language $L\_2$ that contains all binary strings, which is trivially regular. It is the property of having equal 0 and 1 that makes it impossible to have a DFA/NFA that will only accept strings from $L\_1$.

So if you treat all of $L\_1$ as being binary strings (as elements of $L\_2$), then all of them can be pumped with respect to this property. But if you consider them as having equal number of 0 and 1, then that is the time where pumping lemma fails.
> 4 votes

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


# Question
Title: Is this variant of #Positive 2-SAT #P-complete?
This variant of #Positive 2-SAT is defined as follows :

We are given a set of variables :

**(a,b,c,d,e)**

we can form our 2-literal clauses from these set of variables but we want the input in this variant such that for example if we are given a clause (a,e) then this input must contain every possible 2-literal clause from variables below variable ( e ) and every such combination must contain variable ( e ), Thus if we given (a,e) then the input must also contain (b,e) ,(c,e) ,(d,e) as well ,and if the input contain (a,c),(b,d) these clauses then the input must also contain (b,c) ,(a,d) ,(c,d).

Is this variant of #Positive-2SAT ,where we have this kind of restriction on the input ,still #P-complete?

I have no idea as to how to show its complexity and haven't been able to find any sort of text on this type of variant.

My motivation for this is know more about the how much restrictions we can put on the input without changing the complexity status of the problem.

# Answer
> 2 votes
It can be solved in polynomial time, and thus is unlikely to be #P-complete. Every such formula has the form

$$\varphi = \bigwedge\_{j=1}^{k} \bigwedge\_{i=1}^{a\_j-1} (x\_i \lor x\_{a\_j})$$

where $a\_1,\dots,a\_k$ is some sequence of variable indices and the variables are $x\_1,\dots,x\_n$. Let's assume (without loss of generality) that $a\_1 \< \cdots \< a\_k$.

Then every satisfying assignment to $\varphi$ has the form

$$\begin{align\*}&x\_1=x\_2=\cdots=x\_{a\_t-1}=\text{True},\\ &x\_{a\_t}=\text{False},\\ &x\_{a\_{t+1}}=x\_{a\_{t+2}}=\cdots=x\_{a\_k}=\text{True} \end{align\*}$$

for some $t$. The number of satisfying assignments of this form is $2^{n\_t}$ where

$$n\_t=|\\{a\_t+1,a\_t+2,\dots,n\\} \setminus \\{a\_{t+1},a\_{t+2},\dots,a\_k\\}|$$

which can be readily computed. Thus, the total number of satisfying assignments to $\varphi$ is

$$2^{n\_1} + 2^{n\_2} + \dots + 2^{n\_k},$$

which can be computed in polynomial time.

---
Tags: complexity-theory
---


# Question
Title: Regularity or non-regularity of union of two languages
Consider this language:

$K=\\{xy \mid x=\\{a,b\\}^\*, y=x^R \text{ or } y=x\\}$

I know that these languages are non-regular separately:

$K\_1=\\{xy \mid x=\\{a,b\\}^\*, y=x^R\\}$

$K\_2=\\{xy \mid x=\\{a,b\\}^\*, y=x\\}$

But what about their union?

# Answer
> 1 votes
Suppose towards a contradiction that $w$ is regular, let $p$ be its pumping length, and consider the word: $a^pba^pb \in w$.

By the pumping lemma, there is some $k \ge 1$ such that $a^{p + ik}b a^p b \in w$ for all choices of an integer $i \ge -1$. Choosing $i=-1$ we obtain $a^{p-k}b a^p b \in w$. This is a contradiction, therefore $w$ is not regular.

---
Tags: regular-languages
---


title: Pattern Matching Variant Problem

text:
# Question
Title: Pattern Matching Variant Problem
Given string P with length n, and a function A on P \[n\] --\> \[n\] that does the following: For every 1 \<= k \<= n A on P \[k\] = { the maximum index i such that P\[1...i\] = P\[k...k+i-1\] Write an algorithm that's optimal as possible that given string P calculates the value of A on P \[k\] for every 1\<= k \<= n

# Answer
There exist an **O**(n2) solution for the given problem. Let prefixlen be an n×n array and result be stored in an array res of length n. res\[k\]=0 implies that there is no longest prefix that matches the substring p\[k\]..p\[k+i-1\]. Here p is taken as zero indexed.

```
for k from 0 to n-1
  res[k]=0
 for i from 0 to min(k-1,n-1-k)
   if i==0 then
      if p[0]==p[k]
        arr[k][0]=1
      else
        arr[k][0]=0
   else if arr[k][i-1]!=0 then
      if p[arr[k][i-1]==p[k+i] then
        arr[k][i]=arr[k][i-1]+1
      else arr[k][i]=arr[k][i-1]
       end if
   else
      if p[k]==p[0]  then
         arr[k][i]=1
      else arr[k][i]=0
  res[k]=max(res[k],arr[k][i])
  end for
 end for

```
> 0 votes

---
Tags: matching
---


# Question
Title: Why do we shift by three in RISC-V loops?
In this youtube video, the instructor explained some basic code in RISC-V assembly, but i didn't understand why in the first line, he is shifting i by 3. Why do we have to multiply it by 8??

I feel like it has something to do with the fact that LOAD IMMEDIATE operations can load values up to 12 bits only, but I couldn't make the connection.

# Answer
> 1 votes
Since you haven't provided any context of the code, we can just make assumptions.

**Assumption:** *save* is an 8-byte(or 64-bit) integer array.

**address of save\[i\] in memory** is equivalent to writing **base\_address(save) + i * size\_of\_unit\_element\_of(save)**

Hence, to compute the effective address of save\[i\], we need to add i\*(8 bytes) to its base address (which happens to be x25).

So, essentially, we store **i\*8 in x10**, and **add base-address x25 to x10**, leading to **save\[i\]**.

Finally, we dereference it and store the value at save\[i\] to x09.

---
Tags: assembly
---


# Question
Title: PDA for equal number of as and b's where n>=1
How to design Push Down Automata for a language that has equal number of a's and b's where $n \ge 1$?

I got how to do it for $n \ge 0$, not able to get it for $n \ge 1$.

# Answer
The intersection of a context-free language and a regular language is also context-free, and this can be shown using the same Cartesian-product-machine construction used to show the intersection of two regular languages is also regular. This construction gives you a way of finding the PDA for the intersection of a context-free language and a regular language, if a PDA and DFA are known.

A DFA for the language of strings that are non-empty is easy: it has two states, q0 and q1, with q1 accepting and q0 not, and all transitions go to q1.

You say you already have a PDA for the language of strings where #a(w) = #b(w); call its states Q, its accepting states A, its initial state q\*, its alphabet S, its stack alphabet Z and its transitions f: Q x S x Z -\> Q x Z.

We can define a PDA that accepts the intersection of non-empty strings with the strings that have #a(w) = #b(w) as follows:

1. Q' = {q0, q1} x Q
2. A' = {(q1, q) | q in A}
3. S' = S
4. Z' = Z
5. f'(q, s, z) = ((q1, q'), z') where (q', z') = f(q, s, z)
6. initial state (q0, q\*)
> 0 votes

---
Tags: pushdown-automata
---


title: Is One Way TSP NP-Complete?

text:
# Question
Title: Is One Way TSP NP-Complete?
I know that finding the optimal solution to One Way TSP (TSP but the salesman does not have to return to his original city) is NP-Hard, but is it NP-Complete? I ask this because I recently found a solution to Open TSP but can't find a good resource to tell me whether or not One Way TSP is NP-Complete.

# Answer
The answer depends on how you define "One Way TSP".

If the One Way TSP problem asks to compute the tour itself, then it cannot possibly be NP-complete since it is not a decision problem, and hence it does not even belong to the class NP.

If the problem is that of *deciding* whether there is a tour having cost at most $x$, for some input parameter $x$, then the problem belongs to NP (a yes-certificate is the tour itself) and it is NP-complete.
> 2 votes

# Answer
Take your "one way" problem. Add another city X, make the distance from start to X = 0, make the distance from X to any other city d which is longer than the sum of all other distances, then solve the original TSP for this instance.

In the solution, X obviously must have two neighbours. One neighbour must be the start city, otherwise you would have a total distance \>= 2d, instead of a distance less than 2d. If you remove the city X from the solution, you have the optimal solution for the "one way" problem.
> 0 votes

---
Tags: np-complete, np-hard, np, p-vs-np, traveling-salesman
---


title: merging logn + 1 sorted subarrays

text:
# Question
Title: merging logn + 1 sorted subarrays
given array A of size $n$ which is made of $logn + 1$ sub arrays which are sorted, I need to sort ASAP.

example of array : $A\[500,501,3,8,100,1,2,9\]$ as you can see, sub arrays are :$\[1:2\]\[3:5\]\[6:\]$

my solution was: merge all logn + 1 arrays together, simultaneously.

so like I compare : $1:3:500$ \>\> append 1 to sorted array $2:3:500$ \>\> append 2 and so on until all is done.

i thought the complexity of my solution is expected to be $O(n)$ because each sub array on average has $\frac{n}{logn+1}$ values and there are $logn+1$ subarrays ..

chatgpt says its $O(nloglogn)$ ..

can you please explain the complexity analysis? does my solution even work?

# Answer
> 1 votes
I don't understand what "merge all $\log n + 1$ arrays together, simultaneously" means. The trivial algorithm that iteratively checks all the minima $m\_1, m\_2, \dots$ of the sub-arrays to find $j = \arg\_{i=1, \dots, \log n +1} \min m\_i$, adds $m\_j$ to the final sorted array, and deletes $m\_j$ from the $j$-th sub-array has complexity $\Theta(n \log n)$.

If instead you merge two arrays at a time, in a balanced binary-tree fashion, you have that each "level" of merging requires time $O(n)$ and that there are only $\log( \log n + 1) = O(\log \log n)$ levels. Hence the overall time-complexity is $O(n \log \log n)$.

Another solution is to just maintain a min-heap $H$ that stores the minima of the subarrays. Iteratively remove the minimum element $m$ from $H$ and add it to the final sorted array, then delete $m$ from its sub-array and insert the new minimum of that sub-array into $H$ (if any). Since $H$ can be built in linear-time (in its size), contains at most $\log n + 1$ elements throughout the execution of the algorithm, and each heap operation can be performed in time $O(\log |H|)$, where $|H|$ denotes the number of elements in $H$, it follows that the time complexity of this algorithm is also $O(n \log \log n)$.

# Answer
> 0 votes
Obviously you could pick the smallest number from the k arrays and remove it from its array, which is trivial to do in k steps, multiplied by the number of array elements.

Instead you split the array into pairs of two arrays, and find the smaller of each group, then you split the groups into pairs, each including 4 arrays, then 8, 16 arrays and so on. You find the smallest element instantly. Now in one of the groups of two one input has changed, so you find again which is smaller. Now the smallest of a group of 4 is changed, and the smallest of a group of 8 and so on, for a total of log k changes.

Total effort per element found is log k. Since you have k = log n, the total effort is n log log n.

---
Tags: time-complexity, sorting, mergesort
---


# Question
Title: Is there an optimisation algorithm that does not require a good initial solution?
I was reading this question on CS stack exchange called How important is initial state for local search optimisation?

I would like to extend it with the following example:

I have been reading about optimisation techniques and noticed that if a random initial state is provided to a genetic algorithm, it may still find a good enough solution. However, a simulated annealing algorithm may be stuck and never get out of really bad initial solution.

Does it mean these two are not comparable if a bad initial solution is provided? Are there any other algorithms that are not that sensitive to an initial solution?

# Answer
> 0 votes
The answer is 'it depends'. It depends on the particular problem you are optimizing. I doubt you are going to get a single answer that applies to everything. In general, reducing the dependence on the initial state is generally considered a good property of an optimization algorithm, but there is no clear way to evaluate this, and the dependence is likely to depend on the specific optimization task you are solving. It is very hard to make sweeping statements, because how well an optimization approach works depends heavily on the task.

---
Tags: optimization, heuristics
---