# Question
Title: Prove $H2 = \{\langle M\rangle : M$ accepts all inputs in $\{0, 1\}^∗$ whose length is at most $2\}$ is undecidable but recognizable
Yet another question from an exe. in the Computability class taught by Z. Luria -

I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable?

I mean we can build a machine $M$ that checks all the possibilities (In this case ${0, 1, 00, 01, 10, 11}$), That was my approach for proving the recognizable property.

Is there a mistake in the exe. or I'm not understanding the topic at all?

I think that the fact the language is made of $TM$ confuses me.

# Answer
> 1 votes
#### Undecidability can be confusing. Recognizability can be confusing.

The setups and arguments for propositions on undecidability or recognizability can be quite confusing, indeed. The languages we want to prove undecidable/recognizable usually involve encodings of Turing machines, while at the same time, the programs that we build to prove them undecidable/recognizable are also Turing machines.

For example, the halting problem is to decide, given the encoding of a Turing machine and a word, whether that Turing machine will halt upon that word (as input). The usual proof that the halting problem is undecidable involves:

* a hypothetical Turing machine $A$ that decides the halting problem,
* the construction of a new Turing machine $B$ that will, given an encoding of a Turing machine $p$ as input, run forever iff $p$ halts upon the encoding of $p$ itself, and
* the analysis of running $B$ upon its own encoding as input.

It happens often when people talk about a Turing machine, they mean the string that encodes it instead. For example, the language of all Turing machines that accept empty input. In case of confusion, make it clear what is referred to is the machine, or the string instead.

#### Let us clear some confusions

While "a finite language always decidable", this problem is about the decidability of the language of the encodings of some Turing machines. That is, whether there is an algorithm that will always tell (in finitely many steps), given an encoding of a Turing machine $T$, whether $T$ accepts every string among $\epsilon,0,1,00,01,10,11$. There are, of course, infinitely many Turing machines that accepts all those strings. For example, Turing machine $T\_i$ that always moves to the right $i$ times and then accepts, ignoring input completely. You can also add an arbitrary number of useless states to a Turing machine.

"The language is made of TMs confuses me". Language $H2$ is made of the encodings of Turing machines. $\langle .\rangle$ maps a Turing machine to the string that encodes it, i.e., given Turing machine $M$, $\langle M\rangle$ is a string.

#### Prove $H2$ is recognizable but not decidable.

$H2$ is not decidable is a straightforward application of Rice's theorem. All we need to do is to verify that it is valid to apply Rice's theorem.

Let Turing machine $R$ runs as follows upon input string $w$.

1. If $w$ does not encode a Turing machine, reject.
2. Otherwise, $w$ encodes a Turing machine $T$.
    1. Simulate $T$ upon the empty input.
    2. If the simulated $T$ above accepts, simulate $T$ again upon input string 0.
    3. If the simulated $T$ above accepts, simulate $T$ again upon input string 1.
    4. If the simulated $T$ above accepts, simulate $T$ again upon input string 00.
    5. If the simulated $T$ above accepts, simulate $T$ again upon input string 01.
    6. If the simulated $T$ above accepts, simulate $T$ again upon input string 10.
    7. If the simulated $T$ above accepts, simulate $T$ again upon input string 11.
    8. If the simulated $T$ above accepts, accepts.

It is clear that $R$ recognizes $H2$.

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


title: Possible Error in TAOCP

text:
# Question
Title: Possible Error in TAOCP
In section 1.2.11.2 of Donald Knuth's first volume of TAOCP, he gives an exercise at the end to prove that $g(n) = \Omega (f(n)) \iff f(n) = O(g(n))$ (exercise 13). His solution is simply: "we may take $L = \frac{1}{M}$ in the definitions of $O$ and $\Omega$." However, earlier in the book he states, "Every appearance of $O(f(n))$ means precisely this: There are positive constants $M$ and $n\_0$ such that the number $x\_n$ represented by $O(f(n))$ satisfies the condition $|x\_n|\leq M|f(n)|$ for all integers $n\geq n\_0$." Similarly, he says, "The statement $$g(n) = \Omega (f(n))$$ means that there are positive constants $L$ and $n\_0$ such that $$|g(n)| \geq L |f(n)| \text{ for all }n\geq n\_0."$$

However, if $L$ and $M$ have to be positive constants, then we can't say that $L=\frac{1}{M}$ because the reciprocal of a positive constant is not a positive constant. You can adjust the proof to make it work when $L$ and $M$ have to be positive constants, but I'm wondering if Knuth made an oversight by stating that $L$ and $M$ have to be positive constants because that makes his proof for exercise 13 not work. Additionally, I see no reason that these must be positive constants (and Wikipedia agrees with me, calling the constants positive and real).

If this is in fact an error, how should I report it to claim a hexadecimal dollar in a fictional bank?

# Answer
> 3 votes
The reciprocal of a positive constant is indeed a positive constant.

Just like $2\>0$ and the reciprocal of $2$ is $\frac{1}{2}\>0$.

So Knuth didn't make a mistake

---
Tags: big-o-notation
---


title: Vector of 1s and sum of elements

text:
# Question
Title: Vector of 1s and sum of elements
I stumbled on the following computing issue and would like some help to solve it. Given a vector of size n and filled with 1's, give all the elements obtained by the sum of them. Ignore combinatorial options like \[m, n\] and \[n, m\]

Example: n = 5, v = \[1,1,1,1,1\]: The possibilities are below:

```
[2, 1, 1, 1], [2, 2, 1]
[3, 1, 1], [3, 2]
[4, 1]
[5]

```

Take note: the elements are in front of one another only when 1s are summed together. Otherwise, they are placed on the next row.

# Answer
> 1 votes
This task can be done conveniently by a recursive algorithm.

Fix the total sum `n`. A partition of `n` can be viewed as a decreasing sequence of positive integers that sum up to `n`. If the initial segment of decreasing sequence has been selected, the remaining sequence is naturally a partition of `s` into numbers that are at most the least of the selected numbers, where `s` is `n` subtracted by the sum of the selected numbers. Thus we can construct partitions recursively.

---

Here is an implementation in Python.

The function `partitions_recursive` puts partitions of number `s` with decreasing parts, each part at most `m`, in the array `buffer` starting at index `start`.

```
def partitions(n):
    all_partitions = []
    buffer = [0] * n

    def partitions_recursive(start, s, m):
        """sum(buffer[index:]) will be s. Each entry will be at most m"""
        if s == 0:
            all_partitions.append(buffer[:start].copy())

        for part in range(1, min(s, m) + 1):
            buffer[start] = part
            partitions_recursive(start + 1, s - part, min(m, part))

    partitions_recursive(0, n, n)
    return all_partitions

print(partitions(5))
# [[1, 1, 1, 1, 1], [2, 1, 1, 1], [2, 2, 1], [3, 1, 1], [3, 2], [4, 1], [5]]

```

---
Tags: algorithms
---


# Question
Title: Find non CFL $L$ such that Pref($L$) is CFL
While studying I've encountered this question written above. I am familiar to the closure properties of CFL, and even know that $$L=\\{a^{j^2}|j\geqslant 0\\}$$ ($a$ to the power of ($j$ to the power of $2$))
is one that answers the question, but I don't know how to prove that.

If anyone could explain it to me, it would be excellent!
Thank you.

# Answer
> 1 votes
I think proving that $\text{Pref}(L)$ is CFL is the easiest part (it is even regular): ask yourself what are all prefixes of a word $a^{j^2}$.

Proving that $L$ is not CFL is done here.

You can use the pumping lemma for CFL or, even better, the pumping lemma for regular languages (using the fact that a CFL over a one-letter alphabet is a regular language).

---
Tags: context-free
---


# Question
Title: How to use the step count method correctly for binary search?
I've tried to use the step counting method to get the worst-case time complexity for binary search. But I seem to mess it up, as my final result would be `O(n)` and not `O(log(n))`.

My implementation:

```
fn binarySearch(array:[i32;20],target:i32) -> isize{
    let mut min = 0; //c
    let mut max = array.len(); //c
    let mut guess:usize; ///c
    while max > min{ //n
        guess = (max+min)/2; //c
        println!("Guess: {}",array[guess]);//c
        if array[guess] == target{//c
            return guess as isize;
        }else if array[guess]<target{//c
            min = guess + 1; //c
        }else{//c
            max = guess - 1; //c
        }
    }
    return -1 as isize; //c
}

```

I've written the time it takes in the comments `c` for constant `n` for linear. But based on this I get something like this: `T(n) = c+c+c+n*(c+c+c+c+c+c+c+c)` which should boil down to `T(n) = 3c+n*8c` which would be `O(n)` and not `O(log(n))`.

# Answer
> 2 votes
The mistake in your analysis is counting the number of iteration of the while loop as $n$. The key observation with binary search is that you cut the range at about half in every iteration. So if initially your array has $n$ items, in the worst-case you will divide the array in half $k$ times until only one element is left (after this the subarray will be empty and the loop will end). You will get $n/2^k = 1$, which then is equal to $n=2^k$. Here $k$ is also the worst-case number of iterations. Taking the logarithm both sides will give you $k =\log\_2 n$.

# Answer
> 1 votes
**Hint:**

On the first iteration, guess = n/2 and either the search ends there or continues in \[0, n/2-1\] or \[n/2+1, n\].

On the second iteration, guess = n/4-1/2 or 3n/4+1/2, and either the search stops there or continues in \[0, n/4-3/2\] or \[n/3+1/2, n\] or \[n/2+1, 3n/4-1/2\] or \[3n/4+3/2, n\].

And so on. The details of the bounds do not matter so much. What matters is that the interval size is halved every time.

---
Tags: algorithms, time-complexity, runtime-analysis, binary-search
---


# Question
Title: How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?
I have been given the following problem and was wondering if my solution is correct: Say that a variable $A$ in CFG $G$ is necessary if it appears in every derivation of some string $w$ where $w$ is in $G$. Let $$\text{NECESSARY}\_{\text{CFG}} =\\{\langle G,A\rangle \mid G\text{ is a CFG and }A\text{ is a necessary variable in }G\\}$$

1. Show that $\text{NECESSARY}\_{\text{CFG}}$ is Turing-recognizable.
2. Show that $\text{NECESSARY}\_{\text{CFG}}$ is undecidable.

This problem is a textbook exercise in the book *Introduction to the Theory of Computation* by Martin Sipser.

---

This is my solution to part 1.

$D$ = On input $\langle G,A\rangle$:

1. Create a CFG $H$ by eliminating the $A$ variable from the derivations of $G$.
2. Create list of strings $w$ generated by grammar $G$.
3. Create a decider for $\text{A}\_{\text{CFG}}$ and check if each string of $w$ can also be generated by $H$.
4. If $w$ strings cannot be generated by $H$ then accept.
5. If some string cannot be generated by $H$ then reject.

---

For part 2, I don't have a solution. My thoughts would be to somehow reduce this to $\text{ALL}\_{\text{CFG}}$ which is known to be undecidable.

# Answer
> 7 votes
#### An approach for the undecidability

Let $G$ be a context-free grammar. We can add to $G$ new context-free generation rules that employs new variables without using any variables in $G$ (except the initial variable of $G$) so that we end up with a grammar $H$ such that $H\in\text{ALL}\_{\text{CFG}}$ and

$\quad$ $G\in\text{ALL}\_{\text{CFG}}$ $\iff$ every new variable is not necessary in $H$.

Were $\text{NECESSARY}\_{\text{CFG}}$ decidable, we could decide the right-hand side, and hence the left-hand side as well.

#### Some minor issues of your solutions

Your solution to part 1 is basically correct.

There are, apparently, some typos in step 4 and step 5. Step 5 , "... then reject" might be wrong since this procedural cannot end with rejecting when $L(G)$ contains infinitely many strings. It is unnecessary any way.

Here is a better way to write your solution.

Turing machine $D :=$ On input $\langle G,A\rangle$:

1. Create a CFG $H$ by eliminating variable $A$ from the generation rules of $G$.
2. Create a decider for $\text{A}\_{\text{CFG}}$.
3. For each string $w$ in $\Sigma^\*$:
    1. Use the decider to check whether $\langle G,w\rangle\in\text{A}\_{\text{CFG}}$ and whether $\langle H,w\rangle\in\text{A}\_{\text{CFG}}$. If the former is yes and the latter is no, accepts.

It is easy to see that $D$ recognizes $\text{NECESSARY}\_{\text{CFG}}$. Note that there is no need to specify when or whether $D$ rejects.

---

You are on the right track on the undecidability.

Note that the right way is "to reduce $\text{ALL}\_{\text{CFG}}$ to this" instead of "to reduce this to $\text{ALL}\_{\text{CFG}}$".

The mental model is to view "$\text{ALL}\_{\text{CFG}}$" as such a "huge and difficult" problem that it cannot be "reduced" to another small and easy problem. If we do find a reduction, the other problem must also be "huge and difficult", which is what we want.

# Answer
> 6 votes
Let $G$ be a context-free grammar over an alphabet $\Sigma$ with initial variable $S$. Create a new grammar $G'$ with a new initial variable $S'$, a new variable $A$, and transitions $S' \to S \mid A$, $A \to \sigma A$ for every $\sigma \in \Sigma$, and $A \to \epsilon$. You take it from here.

---
Tags: turing-machines, computability, context-free, undecidability, semi-decidability
---


# Question
Title: Explaining why FFT is faster than DFT for the general public?
How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?

# Answer
> 9 votes
FFT is an algorithm for computing the DFT. It is faster than the more obvious way of computing the DFT according to the formula.

Trying to explain DFT to the general public is already a stretch. Also, they probably don't know what an algorithm is. Perhaps you could say that there's a fast way of computing the DFT, and that's one more reason why it's so useful.

# Answer
> 3 votes
FFT algorithms are faster ways of doing DFT. It is a family of algorithms and not a single algorithm. How it becomes faster can be explained based on the heart of the algorithm: **Divide And Conquer**. So rather than working with big size Signals, we divide our signal into smaller ones, and perform DFT of these smaller signals. At the end we add all the smaller DFT to get actual DFT of the big signal. This gives great benefit asymptotically. So for large values of N, we save a lot!! We shall see how much in a while.

Let us try to understand it more with little bit of high school maths:

DFT computation for N point signal takes: N^2 multiplications (this is clear from the basic defintion, you have N points, and for each of the points you have to multiply N complex sinusoids).

Now if we dvivide our N-point signal into two signals S1 and S2 of length N/2, and then perform DFT of these smaller signals, we will be doing (N/2)^2 multiplication for each of the S1 and S2. So total no. of mulitplications performed in calculating DFT of S1 and S2 will be 2 * (N/2)^2. Then to get actual DFT of N point signal we need to add these componets. So we can see that we actually need approximately (see Note below) 2 * (N/2)^2= (n^2)/2 which is *half* that in case of N point signal.

This reduction of half is a result of dividing the siganls once. But if we continue deviding the signals again and again, we will end up in reducing the amount of computations in each step by an amount which is much lesser than N^2. In fact the over all no. of compuations using this method comes of the order of N\*logN.

To get an idea of how fast this is as compared to direct DFT, consider a computer which can execute 1 mulitiplication operation in 1 nano-seconds. Assume that we have a signal having total of N= 10^9 points.

Total number of nanoseconds spent for evaluating DFT by direct method (i.e not using FFT)on the given Computer= N^2= 10 ^ 18 Nano seconds, which is approximately 31 years. While using FFT we shall spent N\*logN = (10^9)\*log (10^9)= (10^9)\*9\*log10 = (10^9) * 9 * 3.32 which is approximately equal to 30 * (10^9) or approximately 30secs!!

**So using direct DFT you will spend 31 years while using the devide and conquer approach as in FFT you will get the same output only in 3o seconds!! Now its up to you which method will you prefer :-).**

The bottom line is that a lot of problem in nature can be solved much easily if they are small in size. The total effort in solving many small sized problems, is often much smaller than in case of solving one big problem; especially, if the size of the problem is very big such as the above example explained.
This is the basic idea on which FFT algorithms are based upon.

**Note:** I said 'approximately' because it turns out that we cannot add them directly, and indeed we need a mulitplication factor, actually a phase factor, before combining them. But this is still much lesser that no. of multiplicatiosns we need to do in calculating DFT of S1 and S2, so we can neglect this additional multiplication for large values of N.

**Dvide and Conquer: an analogy in military**

The concept has been used historically in military. For example Sun Tzu (c. 6th century BCE) a Chinese general, military strategist, and author of The Art of War, writes:

It is the rule in war,

1- if ten times the enemy's strength, surround them;

2- if five times, attack them;

3- if double, be able to divide them;

4- if equal,engage them;

5- if fewer, be able to evade them;

6- if weaker, be able to avoid them.

**Sun Tzu**

FFT works on rule no. 3. Rule 1 and 2 tells that if your computer is very powerful enough, then probably you will not be interested in adopting any 'Dvide and Conquer' approach, becasue the gain in doing so will be very less. Also rule no 4 to 6 tells that when your computer is too weak, forget about conquering the problem, by dividing the problem size. You will have to search some other ways. One such way could be Randomization

# Answer
> 2 votes
What does a Fourier transformation do? It takes a sequence of values, like the sound volume recorded on a CD with 44,100 values per second, and transforms it into frequencies. That is very useful for example for compression, because frequencies change much less than volumes. Or it can be used to remove noise, because when you look at frequencies, noise is much easier to detect. So the Fourier transformation is quite useful. And (surprisingly? Caused by deep mathematics) very luckily Fourier transformation can also be used to transform frequencies back to volumes.

There is a formula for calculating the Fourier transformation. Unfortunately that formula combines every single point with every other point. Just for 1,024 points that’s 1,024 x 1,024 values that need to be combining, which takes over a million operations.

FFT (Fast Fourier transformation) uses some clever tricks to combine 1,000 points with 1,000 points much faster.

First, it combines the first and second point producing two new values, the third and fourth point producing two new points, and so on. Next we split the data into groups of four. It combines the first and third point, and the second and fourth point. Since each of these points already combined two original points, each of the four results combines data from 4 points.

Then the data is split into groups of eight, and FFT combines the 1st and 5th, 2nd and 6th, 3rd and 7th, and 4th and 8th values, and we get 8 results combining 8 values each. We repeat with groups of 16, 32, 64, 128, 256, 512 and 1,024 numbers.

We do a total of 10 rounds, and each round combines 1,024 points with one of 1,024 other points, for a total of 1,024 calculations per round, or 10,240 operations in total, instead of over a million. How all these values are combined has to be done in a really clever way, but once that way was found, FFT is massively more efficient than just following the formula.

# Answer
> 1 votes
For a non maths audience this will be hard, I suggest you keep it as short as possible or omit it entirely but here's my attempt

A DFT is a large matrix that you multiply your input vector by, the naive implementation involves doing n^2 multiplications for an n point DFT (there are a whole bunch of additions too, but at least in hardware the cost of the multiplications will dominate)

An FFT can be seen as transforming the DFT matrix into multiple matrices which when multiplied together give you the same result, crucially some of the terms in the FFT matricies are 0 so all multiplications with these terms can be omitted meaning you end up with fewer multiplications overall.

# Answer
> 1 votes
Calculating one value of X(k) in the frequency domain costs N complex multiplications, so calculating all N of them one by one, "starting over" every time, costs N times N is N^2 complex multiplications.

However, if you first calculate the DFT of all even entries ((N/2)^2 multiplications) and all odd entries (another (N/2)^2 multiplications), for a total of N^2 / 2 multiplications, you can calculate the full DFT from those with just another N/2 multiplications and N additions. For large N that last step can be ignored, and thus you gained a factor of two. If N is a power of two N=2^q, then you can repeat this trick q times by doing it also for the smaller DFTs of the even and odd entries, winning q times a factor 2, thus it becomes N^2 / (2^q) = N^2 / N = N multiplications, but you have to do that q = log2(N) times, so in the asymptotical case you end up with something of the order N log(N).

To see why you can combine the DFTs of even and odd entries in such an easy way, you must realize that you're just summing entries multiplied with evenly spaced complex numbers on the unit circle in the complex plane (Nth roots of 1, which all lay on a circle). So, if you treat the odd entries as the only input for some DFT then you you're only a single rotation away from what you need for the full DFT: the rotation to bring the entries back to where they should be. A rotation means a multiplication, hence N/2 extra multiplications before you can combine the two smaller DFTs with just additions.

Note that the same trick can be applied when N doesn't factor into just 2^q, but when it can be factored into many small prime numbers. For example, if N=p^q you can repeat q times a stage where you calculate p DFT's each of N/p points and then combine those with (p-1)N/p multiplications (rotating p-1 of the DFT's of the previous stage) and (p-1)N additions, for each of the q stages.

# Answer
> 1 votes
Here is an attempt.

The Fourier transform decomposes a signal into superimposed sine waves of various frequencies (this can be demonstrated visually).

It turns out that we can find out the strength of a specific wave in a specific signal by multiplying the signal with the wave and summing the resulting signal (again, this can be demonstrated visually).

---

The fast Fourier transform speeds up this process.

The insight is that if we divide the signal into two equal halves and compute the decomposition of each, then we can use these decompositions to obtain the decomposition of the entire signal (we don't explain how).

Since the two signal involved are smaller, the process is faster (we don't explain why, but we say it in a convincing tone).

We can speed things up further by *iterating* this process: dividing the original signal into quarters, computing their decomposition, deducing the decomposition of the two halves, and then of the entire signal.

The best performance is obtained by repeating this all the way down: starting with signals containing a single sample, then repeatedly doubling the signal length until we reach the original signal. This is the fast Fourier transform, and it is indeed significantly faster (e.g., xM for signals of length N).

# Answer
> 0 votes
EDIT: Indeed my previous answer was misleading, since I stated that recursive summation like in merge sort saves calculations and that is of course not true.

What does happen here however is that instead of doing 2N operations on each of the N vectors members (multiplication and summation), we do 2\*lg(N) operations, which are caused thanks to recycling of 2 of the previous operations each time from our current and from another, different vector member. If you look at the butterfly diagram, you’ll see that we recycle each time: we reuse 2 of the previous calculations. Instead of doing N of them each time. That yields in 2lgN calculations EACH time instead of N.

# Answer
> 0 votes
The FFT exploits a property of the DFT: the DFT of a sequence can be obtained by interleaving the DFTs of the first and second halves of the sequence.

As a DFT on $N$ points takes the evaluation of $N$ sums of $N$ terms ($N^2$ operations), interleaving twice $\dfrac N2$ sums of $\dfrac N2$ terms is less expensive ($\dfrac{N^2}2+N$ operations).

The same trick can of course be reused on the half sequences to further reduce the cost, and so on.

# Answer
> -5 votes
the easiest way to understand why its faster is because FFT uses both cos+sin on the other hand DFT only uses cos, DFT is more common because it requires less space in compression in general for image, sound,... the other comments are do a deep dive, mine is just a taste of the stuff.

---
Tags: algorithms, efficiency, education, didactics, fourier-transform
---


# Question
Title: Context Switching in Round Robin CPU scheduling algorithm
If we have only one submitted process and we are using RR CPU scheduling algorithm. Assume that the CPU burst time for this process is 10 ms and the time quantum is 2 , then there will be multiple context switches ? OR the process will continue running on the CPU ? The book "Operating system concepts" 9th edition , page 273 , states that :

> Assume, for example, that we have only one process of 10 time units. If the quantum is 12 time units, the process finishes in less than 1 time quantum, with no overhead. If the quantum is 6 time units, however, the process requires 2 quanta, resulting in a context switch. If the time quantum is 1 time unit, then nine context switches will occur, slowing the execution of the process accordingly (Figure 6.4).

Which means that there will be context switch for one process only . However , this doesn't make any sense for me , since we have only one process , so why the OS performs context switch ?

# Answer
A round robin scheduling algorithm schedules a fixed time slice/quantum for every process. Every process arrives in the **ready queue** and the short term scheduler decides which process to dispatch next based on the scheduling algorithm.

I think you are assuming context switch to be the process of interrupting one process and running another one, which is alright most of the times but isn't exact. **A context switch means saving the current state of the process so that it can resume execution later.**

As you see, **the short term scheduler and scheduling algorithms operate on the ready queue**, where the processes are in ready state. So in running state assuming a uniprocessor system, the OS simply keeps the process in running state as per the scheduling algorithm. **So in this case even if there is just 1 process, after using up its time slice, it would save the current execution state, go back to the ready queue and be scheduled to run again**. Hence the context switch. Hope this clears your doubt.

The lines in the text are based on a lot of assumptions, primarily assuming that only 1 process is to be run on the cpu, which isn't how modern OSes work in practice. There are much more processes and even the OS itself(the core of the OS called kernel) which need to run in a multitasking fashion to ensure the OS delivers the performance and functionality it's supposed to.
> 1 votes

---
Tags: process-scheduling
---


# Question
Title: How to prove that if Eternal Vertex Cover is Polynomial it's possible to detect its vertices and edges
EVG is defined as EVC = { \<G,m,k\>| G is an undirected graph and there is as et of m edges in G that are covered by at most k nodes}

If EVG was decidable in polynomial time how could we find the list of m vertices and k nodes that satisfy it in polynomial time?

Here's the best solution I found: Run EVC repeatedly with k=k-1 until it's not longer accepted. That would be our min boundary for (call it k') Same thing with increasingly higher m until we find for k' the max number of m (call it m')

Then add an external node and connect it each time with a different node in G and run EVC. If it's rejected it means that the node that we connected to is part of the EVG otherwise it isn't. This was we can detect a minimum k' nodes and maximum m' edges and output them.

Problem is that if there are more than 1 EVG the might fail.

# Answer
#### The simple idea

Keep removing nodes from $G$, maintaining $\langle G, m, k\rangle\in \text{EVC}$ without ever changing $m$ and $k$.

#### A simple algorithm

Suppose $\langle G=(V,E), m, k\rangle\in\text{EVC}$.

1. Let $D$ be an algorithm (or an oracle) that decides $\text{EVC}$ in polynomial time.
2. While $|V|\gt |k|$:
    * for each node $v$ in $V$:
        1. check whether $\langle G\text{ without }v, m, k\rangle\in \text{EVC}$ using $D$.
        2. If yes, remove $v$ from $G$, updating $V$ and $E$ accordingly and then breaking this "for each" loop.
3. Now $|V|\le k$. Let $U$ be any set of $m$ edges in $E$. Return $(U,V)$.

---

Note that it is always true that $\langle G, m, k\rangle\in \text{EVC}$ during the algorithm. Whenever the algorithm runs the "for each" loop, it will remove a node from $G$ since $\langle G, m, k\rangle\in \text{EVC}$ and $|V|\gt k$ before the loop. So the "while" loop will executes the "for each" loop at most $n-k$ times, where $n$ is the number of nodes in $V$ initially.

Each execution of the "for each" loop calls $D$ at most $n$ times since $|V|$ can only becomes smaller. Since $D$ runs in polynomial time and $G$ can only become smaller, the whole algorithm runs in polynomial time as well.
> 1 votes

---
Tags: algorithms, complexity-theory, time-complexity, polynomial-time, vertex-cover
---


# Question
Title: What are the applications of Rose trees?
I recently found out about the Rose tree data structure, but just going off of a Haskell `data` definition and the tiny Wikipedia description of it, I've got some trouble understanding what applications a Rose tree might have.

For reference, the Haskell `data` definition:

```
data RoseTree a = RoseTree a [RoseTree a]

```

For those unfamiliar with Haskell -- it's a recursive data type definition with an arbitrary type `a`, where the type constructor is provided with a literal of type `a` followed by an optionally empty list of type `RoseTree` on the same type `a`.

The way I see it:

* This data structure is unordered by default (although I assume most practical applications do implement some form of ordering for searching)
* The data structure doesn't enforce a fixed number of nodes per layer at any point, except the global root, which must have a single node

Given that minimal amount of information, I'm having trouble figuring out when one might use this type of tree.

In addition to the question in the title, if search is indeed implemented in most applications of a Rose tree, how is this done?

# Answer
> 18 votes
You seem to have an overly "data structures and algorithms" mindset. Not every tree is some kind of search tree. Data structures are often designed to correspond to or capture aspects of a domain model.

S-expressions are almost exactly rose trees. (Or rather, I would say how they are typically thought of is as rose trees. Wikipedia is correct in saying they are more like binary trees, but what you might call "proper" S-expressions are only slightly different from rose trees.) At any rate, you can use them as a generic representation for an abstract syntax tree. The benefit of doing this is that you can easily write generic operations, e.g. "find all variables" or "swap parameters" or "rename this symbol". It's also extensible in that adding a new type of node to your abstract syntax often doesn't require really changing anything. The downsides are there aren't really any constraints, so it doesn't a priori prevent you from writing nonsense. This can be mitigated for users by standard abstract data type techniques, but the implementer of transforms and such must deal with the unstructured representation even though they "know" that the input is structured via a data type invariant. Of course, when that certainty is misplaced (possibly because things have changed), the errors tend to be unpredictable and hard to debug.

In practice, while the `Data.Tree` module in the standard libraries provides a rose tree, almost no one uses it in the Haskell community. Defining custom data types that explicitly capture the constraints is so easy that there is little reason to use a generic library type. Further, there has been an enormous amount of research and practice around performing generic operations over custom types which eliminates many of the benefits of using a generic representation. Finally, Haskellers tend to be very much in favor of explicit, enforced constraints and are willing to pay to get it.

To answer your last question, oftentimes searching an AST is unimportant and/or the ASTs are generally assumed to be small enough that just walking the whole thing is acceptable. Admittedly, it's not uncommon to collect definitions in a separate data structure with references into the AST which could be viewed as a sort of index. Similarly, some optimization passes will (usually locally and temporarily) build up indexes to simplify and speed up their operation. The structure of the AST corresponds to the input and so it can't be "rebalanced" or anything like that. As such, it's uncommon for the AST itself to contain indexing information or information to help "searching".

# Answer
> 1 votes
Here's an extremely specific case: shrinking test cases in property based testing (PBT).

One interesting characteristic of PBT is that test cases are random. One unfortunate side effect is that when you find one that falsifies a test, it tends to be massive, messy, and very hard to use for a human being.

In order to solve this, PBT frameworks include the notion of "shrinking" a test case: make it smaller until you can't find a smaller one that still fails. For example, integers can be shrunk in halves until they reach 0, list gravitate towards the empty list, floats towards ints...

This process can be thought of as exploring a rose tree: given a failing test case `a` (root of the tree), you test each smaller version of it (direct children of `a`). This is recursive: as soon as you find `a'` that also fails your test, you start over using `a'` as your new root.

Not only can this be thought of as exploring a rose tree, it's actually implemented that way in some libraries, including (but probably not limited to) Hedgehog. Each randomly generated test case is the root of a rose tree of smaller test cases.

The beauty of this approach is that you can compose random test case generators, and in turn compose their corresponding rose trees: you get correct shrinking of complex test cases for free.

# Answer
> -1 votes
Rose trees could be used in genetic programming to represent the program that the genetic programming system evolves.

Example 1 — `(2.2 - (X / 11)) + (7 * cos(Y))`:

Example 2 — `(5 * 6) + sqrt(3)`:

This kind of tree can be easily represented using S-expressions that Lisps have. The first tree could be represented using the list `'(+ (- 2.2 (/ X 11)) (* 7 (cos Y)))`, while the second tree could be represented using the list `'(+ (* 5 6) (sqrt 3))`.

---
Tags: trees
---


# Question
Title: Find the spanning tree minimizing the backtracking in an unweighted graph
I am working with undirected unweighted graphs, and I am searching for an algorithm that gives me a spanning tree minimizing the number of moves to visit every nodes.

For example, given this graph :

one spanning tree may be :

but, starting at `a`, 11 moves are necessary to go through every nodes : `ab`, `ba`, `ah`, `hg`, `gh`, `hi`, `ic`, `cd`, `dc`, `cf`, `fe` (note that getting back to the start is not required). But with another tree such as this one :

only 8 moves are necessary (which is incidentally the lowest possible for a graph with 9 nodes, but this is not attainable in every graph e.g. if there are multiple "dead-ends").

I am looking for an algorithm which could output such a tree (or path), or at least a good approximation. The graphs I am working with may have up to 100 nodes.

One of my ideas was to generate every spanning tree and then find the best one, but I don't know how to do it, and the number of trees may grow too fast for this to be practical.

# Answer
> 0 votes
Thanks to this post, I found a solution :

1. Use the Floyd-Warshall algorithm on my graph to get the matrix of the shortest distance between every nodes
2. Apply a TSP solver on this to get the shortest path.

Unfortunately, this means the complexity is $O(n^22^n+n^3)$ at best (when using a dynamic programming approach).

# Answer
> 2 votes
The problem is NP-hard since the graph admits a spanning tree with no backtracking if and only if it contains a Hamiltonian path. This shows that, if the measure to optimize is the number of times you backtrack, then there can be no polynomial-time approximation algorithm unless $P \neq NP$.

If the measure is the number of moves needed to visit all the vertices while moving along the edges of the tree, then an arbitrary spanning tree already provides a $2$-approximation. Indeed, any solution must involve at least $n-1$ moves, while an Eulerian tour of a spanning tree traverses each of the $n-1$ edges twice.

---
Tags: graphs, trees, minimum-spanning-tree, python
---


# Question
Title: Newbie needs some explanation on the following code and O-expressed time complexity
I am learning data structures and algorithms currently, and want to understand how the following codes received their `O`-notations.

**Code example #1:**

```
for (int i = N; i > 1; i--) {
  for (int j = 0; j < i; j++) {
    for (int k = 1; k < N; k = k*2) {
        doSomething(i, j, k);
    }
  }
}

```

The `O`-notation for how many times `doSomething(i, j, k);` is executed is: $$\theta(N^2logN)$$

**Code example #2:**

```
for (int i = N; i > 1; i = i/2) {
  for (int j = 0; j < i; j++) {
    for (int k = N; k < N+N; k++) {
        doSomething(i, j, k);
    }
  }
}

```

The `O`-notation for how many times `doSomething(i, j, k);` is executed is: $$\theta(N^2)$$

**Code example #3:**

```
for (int i = N; i > 1; i = i/2) {
  for (int j = 0; j < i; j++) {
    for (int k = N; k < N+N; k = k + N/10 + 1) {
        doSomething(i, j, k);
    }
  }
}

```

The `O`-notation for how many times `doSomething(i, j, k);` is executed is: $$\theta(N)$$

**My question(s):**

*How do you really derive to these O expressions or time complexities*, I am looking at various of mathematical methods but I won't get smarter as a result of that. I looked at few YouTube videos, but even those don't explain the basic tools and fundamentals that give you the edge in doing these calculations and steps manually on any type of code.

*Why do these algorithms or for-loops for how many times the method `doSomething(i, j, k);` is executed derive to these `O`-expressions?*

# Answer
You must proceed from inner to outer.

Evaluate the number of calls to `doSomething` in the innermost loop.

* #1: $\log N$, because you can double $k$ a number of times $\log\_2(N)$ before you reach $N$.
* #2: $N$ times, obviously.
* #3: at most $10$ times, as this will add more than $N$ to $k$.

Using this information, you can evaluate for the intermediate loop.

* For all three cases, this is just $i$ times the count for the inner loop.

Now for the external loop.

* #1: sum of $i\log N$ for $i$ decreasing by unit steps; in total $(N+(N-1)+(N-2)+\cdots1)\log N=\dfrac{N(N+1)}2\log N$.
* #2: sum of $N$ for $i$ following a decreasing geometric progression; in total $N\left(N+\frac N2+\frac N4+\cdots1\right)\approx 2N^2$.
* #3: same as #2 with 10 instead of the first $N$.
> 3 votes

---
Tags: time-complexity, asymptotics, big-o-notation
---


# Question
Title: Construct a regular expression for a specified language
Let $\Sigma = \\{a, b\\}$ I need to find a regular expression for this language:

* The language where the number of $a$'s and $b$'s is equal and for every prefix of a word the absolute value of the difference between the number of $a$'s and $b$'s isn't greater than 2

But I can't seem to find an expression for this language. From what I understand for each $w\in L\_2$, $\\#\_a(w)= \\#\_b(w)$ and for every prefix $p$ such that $w=pu$, $|\\#\_a(p)- \\#\_b(p)| \leq 2$, so I need to somehow enforce that for every $a$ there will be a $b$ and that the difference between them will never exceed $2$, yet I don't think I know how. Can I make the expression include conditions? i.e if $|\\#\_a(p)- \\#\_b(p)| = 1$ can I only accept substrings such that $|\\#\_a(p)- \\#\_b(p)| \leq 2$ would be kept?

# Answer
> 2 votes
I think the regular expression is easier to find using a DFA, but an explaination may be possible without (although the reasonning is the same).

First, note that a word of this language (let's note it $L$) is necessarily of even length. We will then consider pairs of consecutive letters in a word $w\in L$:

* if the word $w = uv$ with $u = ab$ or $u = ba$, then it is clear that $v\in L$;
* if $u = aa$, then necessarily the first letter of $v$ is a $b$. Consider $v = b\alpha v'$, with $\alpha\in \\{a, b\\}$:
    + if $\alpha = b$, then $v' \in L$ and we are back to square one;
    + else, $\alpha = a$, and we can apply the reasonning we did for $v$ to $v'$;
* it is the same thing for $u = bb$.

A corresponding regular expression could then be:

> $$(ab + ba + aa(ba)^\*bb + bb(ab)^\*aa)^\*$$

# Answer
> 0 votes
So I might've come up with the answer looking at Brian M. Scott answer to a similar question

if I build the regular expression $$ (aabb + bbaa)^\* $$ The parity between $a$'s and $b$'s is always kept, easily proven using induction (using the same outline as in the cited answer above), and for every substring, $p$, $|\\#\_a(p) - \\#\_b(p)| \le 2$, because for every substring, $x \in \\{aabbaabb, aabbbbaa, bbaaaabb, bbaabbaa\\}$, $|\\#\_a(x) - \\#\_b(x)| \le 2$

---
Tags: regular-expressions
---


# Question
Title: Finding an algorithm that decides given 2 regular expressions $E_1$ and $E_2$ and a non-negative integer $k$, whether $|L(E_1) \backslash L(E_2)| = k$
Find an algorithm that decides, given 2 regular expressions $E\_1$ and $E\_2$ and a non-negative integer $k$, whether $|L(E\_1) \backslash L(E\_2)| = k$.

I know that regular expressions are closed under set difference so I can find a regular expression equivalent to the one above, and then convert it to a DFA and then break it up into a graph of strongly connected components following which it's possible to solve it using dynamic programming. But is there a way to solve this without converting it to a DFA? (I'm trying to find a solution that's not difficult to implement)

# Answer
Converting to a DFA is pretty easy to implement, especially if you use a library with support for manipulating regular expressions and automata. I doubt you're going to find something simpler to implement.
> 2 votes

---
Tags: automata, regular-expressions
---


# Question
Title: Showing that for every NFA with n states, there is a regular expression of length $O(2^n)$
Consider the idea of an extended non-deterministic automation, where transitions can be labelled by regular expressions and not simply by symbols of the input alphabet or $\epsilon$. Such an automaton would work in the obvious way: if there is a transition from state $q$ to state $q′$ labelled with a regular expression $E$, then the automaton can move from $q$ to $q′$ by reading a prefix of the input word that is a string in $L(E)$.

$(a)$ Explain how every non-deterministic automaton with n states can be converted into an equivalent, extended non-deterministic automaton with $n + 2$ states such that

• The initial state has no incoming transitions.

• There is a single accepting state with no outgoing transitions.

• There is at most one transition between any pair of states.

$(b)$ Now show how to obtain a single regular expression denoting the original language by iteratively removing states from the extended non-deterministic automaton obtained in part $(a)$ while maintaining equivalence. As you remove each state, you should maintain the three properties in part $(a)$. At the end, only the initial state and the single accepting state will remain, and there will be one edge labelled with the regular expression to be found. Explain why the size of this expression is $O(2^n)$

For part $(a)$ we can just add 2 new states, make the first 1 a new starting state and add an edge from it to the old starting state, and make the second one a new final state and add an edge from all old final states to it(and then remove the old final states from the set of final states).

If the NFA happens to have more than one transitions between any pair of states, let the the labels be $E$ and $F$ on the edges. Replace it with a single edge with the label $(E+F)$.

I'm unsure about part $(b)$. My idea was that if we're removing node $u$, then for all nodes $(v,u)$ such that there's an edge from $(v,u)$ with label $E$ and for all nodes $(u,x)$ with label $F$, add a label between $(v,x)$ with label $E.F$. If there already exists some label between these 2 nodes, add the old label, $G$ to $E.F$ (making the label $E.F + G$).

Keep doing this till we only have the start and the final node left - but this doesn't seem to work as we end up with self loops at times which i don't know how to deal with?

# Answer
> 3 votes
What you are looking for, the solution to part (b) is the last step of the **State Elimination Method** that converts a DFA/NFA/$\epsilon$-NFA into regular expression. Here is a short article that explains the method.

---

"If we're removing node $u$, then for all nodes $(v,u)$ such that there's an edge from $(v,u)$ with label $E$ and for all nodes $(u,x)$ with label $F$, add a label between $(v,x)$ with label $E\cdot F$. If there already exists some label between these 2 nodes, add the old label, $G$ to $E.F$ (making the label $E\cdot F + G$)."

The above idea of yours is pretty good. However, it misses the self loop from $u$ to itself, as you have pointed out.

Suppose the label between $(u,u)$ is $H$. Instead of label $E\cdot F$, use $E\cdot H^\*\cdot F$ instead. That is all you need to do.

Since $E$, $H$ and $F$ might be the sum of regular expressions, it should be safer to write $(E)(H)^\*(F)$ instead of $E\cdot H^\*\cdot G$, so that the order of operator precedence is maintained properly. Also, write $(E)(H)^\*(F) + G$ instead of $E\cdot F + G$.

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


# Question
Title: Are there any differences between the various editions of The Art of Computer Programming?
I'm trying to get my hands on a set of these books, and it seems the most recent printing was in 2011. It's currently out of print, and going for *crazy* money. Meanwhile older editions from the 70s are available on eBay for much cheaper.

Is there any reason to hold out for an affordable copy of the newer edition? Or are they exactly the same?

# Answer
They are not the same. The 1985 edition that I have includes RSA for example which wasn’t there earlier. Not sure about newer version.
> 3 votes

---
Tags: books
---


# Question
Title: how two phase commit ensure serializability
Two phase commit is used in distributed transaction. For example, a client sends a transaction to two databases with a coordinator.

* step1: client get a global transaction id from coordinator
* step2: client send the transaction to two databases respectively
* step3: client send the commit flag to coordinator
* step4: coordinator send prepare flag to two databases, and two databases response prepare ack
* step5: coordinator send commit flag to two databases, and two databases response commit ack
* step6: coordinator response commit ack to client

My questions are

* What is the global transaction id in step1 used for?
* And two phase commit is used to ensure the atomic in ACID, but how does it ensure the serializability? For examples, if client A sends transaction A and client B sends transaction B to databases simutaniously, then two databases may execute two transactions in different orders. Then two databases may end with non consistent states.

# Answer
Let me try to explain this using an example. Suppose there is `coordinator` and two participants named `P1` & `P2`. Now suppose both `P1` & `P2` creates a transaction to modify a variable `A` and no other transaction is raised in between, in this case coordinator know that both participants are doing same this coordinator will raise a commit message indicating that both participants can commit and changes will be saved.

Now let's take other example Suppose variable `A` depends on variable `B`, now participant `P1` raises message to modify variable `A` and at the same time participant `P2` raises message to modify both `B` & `A`, in this case coordinator know that participants are going out of sync by executing these commands so master will decline this transaction since it will not serialize.

An assumption about the outcome of transactions, either commit, or abort, can save both messages and logging operations by the participants during the 2PC protocol's execution. For example, when presumed abort, if during system recovery from failure no logged evidence for commit of some transaction is found by the recovery procedure, then it assumes that the transaction has been aborted, and acts accordingly. \[Wikipedia\]
> 1 votes

# Answer
1. For how to ensure serializable.

The atomic commit protocol like 2PC only ensures the "atomicity" property, i.e. a cross-shard transaction either commits or aborts on all participants. The "consistency" (in the sense of ACID) is ensured by the concurrency control protocols like 2PL.
For instance, if you use two-phase locking (2PL) with 2PC, suppose there is a pending transaction T1 that has come to the decision phase of 2PC, then a coming transaction T2 will be blocked at the pre-write phase by the 2PL. In this way, serializability is ensured.
2. For why the transaction ID is needed.

* For implementation, transaction ID serves as an identifier to look up the information (like transaction status, committed, aborted) for a transaction.
* For CC (concurrency control), the transaction ID is sometimes used as a timestamp for the Timestamp-order method to ensure a consistent order of transactions across different shards, or avoid deadlock in techniques like 2PL-wait die.
> 1 votes

---
Tags: database-theory, databases, database-concurrency
---


# Question
Title: Realistic model of memory allocation/deallocation cost
When doing complexity analysis, they never account for the costs of memory allocation/deallocation on the heap. In particular, this is the case for the announced complexities of the operations on containers.

But allocation/deallocation does not come for free and unfortunately is implementation-dependent. Furthermore, one may suspect that the costs are dependent on the whole allocation/deallocation history, via fragmentation. To me, this seems a grey area of the characterization of algorithms, and I believe that in some cases this hidden cost could invalidate low complexity claims such as O(1) or amortized O(1).

So I wonder if there are reasonable models of the complexity of real heap management systems that reflect the behavior of those commonly implemented with compilers. Is there a better answer than "this is implementation dependent" ?

Or another way to ask the question: is it justified to ignore these costs ?

---

Note that I am aware of the post What is the time complexity of memory allocation assumed to be?, but I expect a more concrete answer.

# Answer
> 1 votes
I do believe it is justified to ignore these costs. If we care about actual running time in practice, I expect that there are other factors that are ignored in asymptotic running time that often have a bigger influence -- memory hierarchy and caching particularly comes to mind. In theoretical runtime analysis we treat a random lookup into memory as the same cost as a single arithmetic operation, but in practice it can be 100x slower. I think it'd be rare to find situations where memory allocation overhead causes an 100x increase in runtime.

There are ways to achieve at most a $O(\log n)$ time slowdown, where $n$ is the total amount of memory available. For instance, you can emulate "page tables" in software. Build a mapping from (object id, offset) to an address, and store this mapping in a binary tree. Now accessing the $j$th byte of object with id $i$ can be done by looking up $(i,j)$ in the mapping, and then accessing memory there. Allocating a $k$-byte object can be done by picking a new object id, then finding any $k$ free bytes in memory, and adding $k$ mappings to the binary tree. You can keep track of which bytes are free using a bitmap. Deallocation is also simple; you remove $k$ mappings from the binary tree. In practice, you probably want to use page granularity rather than byte granularity, and round up object allocations to be a multiple of the page size.

I would be surprised to find any problem where taking memory management into account in the running time analysis changes the ultimate time complexity to solve the problem.

Most of the common algorithms use fixed-size objects. For those algorithms, it is straightforward to build a memory allocator where allocation and deallocation can be done in $O(1)$ time. For instance, you can have a doubly linked list of empty objects; allocation removes one from the list, and deallocation inserts it back onto the list.

# Answer
> 1 votes
This question feels more like benchmarking than algorithm analysis to me. That's not to say that there aren't algorithmic considerations.

Consider a multiprocessing environment with different threads all allocating, sharing, and deallocating objects. Each CPU could allocate from its own arena, or there could be a pool of arenas and each allocation could be taken from one that no other CPUs are using. However, an object must be returned to the arena from which it came. This means that deallocation is more likely to suffer from contention and cache locality issues than allocation.

Unmapping a segment of memory from the address space of a process is a $O(\log n)$ operation where $n$ is the number of blocks mapped, since every operating system that I'm aware of uses balanced binary trees for the segment map. (There was an old version of Solaris which used a linked list until system programmers complained about the performance!)

However, mapping a segment, where the programmer doesn't care where it's mapped to, on a 64-bit OS, is probably an $O(1)$ operation, since the kernel probably appends to the tree. Once again, deallocation is likely to be more expensive than allocation.

---
Tags: time-complexity, memory-allocation
---


# Question
Title: How to known which algorithm is the best for what situation, when sorting numbers?
**Is there some kind of "universal list" of performance of different algorithms in different situations?**

I have different databases that save user input (numbers). However some of these sets of numbers are small and some of them are really big (such as the common one). There are negative numbers included.

I remember from when I took algorithms as a course that there are things such as "big-oh notation" and "theta notation", etc. What I am looking for is some way of looking up which algorithm I should use for different un-ordered lists of numbers.

I know that merge sort has the best over all performance with a worst-case time of $n \log n$ however I also know that both insertion sort and quick sort (worst-case $n^2$) sorts better with fewer elements in the given list. There are a few cases of lists being in reverse sort, where can I look up what is the most effective then?

**How do I know which of insertion sort or quick sort I should use then?**

**What is "a small list of numbers that is quicker to sort with quick sort/insertion sort"?**

# Answer
> 1 votes
There is a comparison of sorting algorithms on wikipedia which provides most of the information you're looking for, including separate tables for non-comparison based sorts (distribution, radix, etc).

The short answer this question usually gets is "use whatever built-in library you have". This is obviously frustrating because that's a practical answer to an abstract question. It's often phrased as "you shouldn't be worrying about this" yet this is something taught in every introduction to programming and tutorial site, with drastically fewer explanations of what standard library sorting algorithms do. So it shouldn't be surprising that the question is so common. In short, the built-in sorts usually are adaptive, so they use different algorithms depending on the data structure that way you're usually getting the best of all options.

There are lots of websites, animations and videos that visualize sorting algorithms. This tool has 75 different sorts built in as well as different input data like almost-sorted, reversed, duplicates. It's used to make lots of videos. Those can answer a lot of questions quickly just by visualizing the abstract concept of big O.

To answer one of your specific questions, negative numbers should generally be handled with no issue by any sorting algorithm unless its extremely specialized. Most sorts you read about are comparison based so they don't care if you're comparing `(-∞ <= 2)` or `(red <= blue)` as long as it can get a valid result out of the comparison.

For the more specific questions you mentioned, I've also wondered about those cases and considered making a big table just as an exercise to cement what I've learned and maybe satisfy someone else's curiosity. However once you start seriously considering publishing something like that you realize it's very difficult to choose a good "reference frame" (what test cases on what hardware) that won't give beginners the wrong idea or get a million corrections from people. It's a somewhat lose/lose scenario so I understand a bit more why people don't do it. (And I'm even more grateful to the people on Wikipedia and elsewhere who do).

The last thing I'll say is that another reason you'll be told to just use the built in sort is that it's very common to pre-optimize code, which can lead to more problems down the line. It's rare that you'll need to write your own sorting algorithm, but it can happen.

# Answer
> 0 votes
In practice you call a method or function provided by your computer’s operating system or your languages standard library.

The algorithm used is likely a mixture of different algorithms and designed to minimise average runtime - with “average” meaning the average over arrays that users actually try to sort. Methods that help us looking for a sorted sequence at the start and end of the array which can let you combine two sorted arrays and sort the result in O(n), checking for an array that is sorted with few changes (if you start with an array of n items and change k of them, you can sort the result in O(n + k log k)), possibly checking for small arrays.

Usually sorting will be comparison based, because that allows for a consistent interface.

Plus there is the possibility of partially sorting: You may want to *display* an array in sorted order, but then you only need to sort the part that is being displayed; quicksort can do that nicely.

---
Tags: algorithms, sorting, quicksort, mergesort
---


# Question
Title: Why DFS transversal without the duplicates is a valid cycle?
So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get. Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path. The well-known 2-approximate algorithm computes the MST , transverses it with DFS while noting down the vertices .
**I don't get how from there, we get a valid (Hamiltonian) path** .
In dfs transversal we find duplicates exactly because some vertices are not connected but do have common ancestors. By deleting the duplicates how can we 'jump' from one another?

For example here in 7.46 we get an explanation for the path from MST https://www.youtube.com/watch?v=zM5MW5NKZJg

# Answer
> 3 votes
The 2-approx algorithm you are referring to works on a special kind of TSP called the Metric TSP . In this version of TSP the graph must be complete and edge weights must satisfy the triangle inequality.

Since the graph is complete, if you delete a repeating edge after the modified DFS, you will replace it with an edge that directly connects the vertices.

---
Tags: algorithms, graphs, algorithm-analysis, approximation, traveling-salesman
---


# Question
Title: Is the intersection of any context free language and the set of all palindromes context free?
Let $L$ be any context-free language. Is the set of all palindromes that are elements of $L$ also context-free?

I know that the intersection of context free languages isn't guaranteed to be context free, so I can't apply that here.

I also thought of maybe using the fact that $\\{0^{n}1^{n}0^{n}|n ≥ 0\\}$ is not context free as all elements in the set are palindromes, but I don't know what context free language to intersect it with.

# Answer
Nice question, and your intuition almost gave you an answer. Simply check the intersection of language $\\{0^n 1^n 0^+\\,|\\,n\>0\\}$ with the palindrome language :)
> 3 votes

---
Tags: context-free
---


# Question
Title: A language of natural numbers is decidable iff it is either finite or the image of some strictly increasing computable function
Suppose $L \subseteq \mathbb N$ such that, for the purpose of Turing machine computation, numbers in $L$ are represented by strings over the alphabet $\\{0, 1\\}$ in the standard binary notation. Prove that $L$ is decidable if and only if $L$ is finite or $L$ is the image of some strictly increasing computable function $f : \mathbb N \to \mathbb N$. Such a function $f$ is strictly increasing if for all $n\_1$, $n\_2$ $∈$ $\mathbb N$, $n\_2$ $\>$ $n\_1$ implies $f(n\_2) \> f(n\_1)$.

My attempt for the backward direction:

* $L$ decidable $\impliedby$ $L$ finite.

If $L$ is finite we can simply check whether an input is in the set of finite words in $L$.
* $L$ decidable $\impliedby$ $L$ is the image of $f$.

If $L$ is the image of some strictly increasing computable function there's a 1-1 correspondence between the natural numbers and the words in $L$. Therefore consider a Turing machine where on input $x$, we start incrementing a counter $y$, which is initially at $0$ while $f(y)\<x$.

Once $y$ has finished incrementing, if $f(y)$ equals $x$ we accept else we reject. Since the number $y$ must be finite, the Turing machine always terminates. Therefore $L$ is decidable.

How can I proceed with the forward direction?

# Answer
"If $L$ is the image of some strictly increasing computable function there's a 1-1 correspondence between the natural numbers and the words in $L$". This is a key observation. You might have realized that given $L$, if $L$ is the image of some strictly increasing function $f:\mathbb N\to\mathbb N$, then $f$ is unique, since $f(n)$ must be the $n$-th smallest number in $L$.

---

Let us try constructing $f$ step by step.

What is $f(0)$? It is the smallest number in $L$.

1. Is $0$ in $L$? If yes, $f(0)=0$.
2. Otherwise, is $1$ in $L$? If yes, $f(0)=1$.
3. Otherwise, is $2$ in $L$? If yes, $f(0)=2$.
4. And so on.
5. At last, after finitely many checks, we must get a "yes" since $f(0)$ is a natural number. Set $f(0)$ accordingly.

What is $f(1)$? $f(1)$ is the smallest number in $L$ that is greater than $f(0)$.

1. Is $f(0) + 1$ in $L$? If yes, $f(1)=f(0)+1$.
2. Otherwise, is $f(0)+2$ in $L$? If yes, $f(1)=f(0)+2$.
3. Otherwise, is $f(0)+3$ in $L$? If yes, $f(1)=f(0)+3$.
4. And so on.
5. At last, after finitely many checks, we must get a "yes" since $f(1)$ is a natural number. Set $f(1)$ accordingly.

What is $f(2)$? You should be able to see the drill now.
And so on.

---

In summary, here is how $f(n)$ can be computed, assuming $L$ is infinite and decidable. Let $D$ be a decider for $L$.

1. Let $result=0$
2. Repeat:
    1. Apply $D$ to check whether $r\in L$.
    2. If $r\in L$:
        * If $n=0$, return $result$.
        * Decrease $n$ by one.
    3. Increase $result$ by 1.

The case when $L$ is finite is trivial.
> 2 votes

---
Tags: turing-machines, decidability
---


# Question
Title: Why are reachability trees meaningful for Petri Nets
To construct a reachability tree we start with the initial marking and then consider all enabled transitions and fire them **one by one**. That is, we find the marking corresponding to firing each.

I can't see why is this meaningful because if we were simulating the petri net then starting with the initial state we would fire all possible transitions that can fire together to reach the next marking and not just one of them.

So I don't understand what's the purpose of constructing a reachability tree if the markings (configurations) it will give consider firing only one transitition at a time which isn't how a petri net works.

# Answer
> 2 votes
Most Petri nets *do* work by having their transitions fired one by one. See, for instance, these course notes. In any marking, one or more transitions may be enabled. One of these may then fire, producing a new marking. The reachability graph is the labeled directed graph with as its vertices all reachable markings, and as its arcs transitions, such that an arc labeled $t$ from $M\_1$ to $M\_2$ exists if and only if firing transition $t$ in marking $M\_1$ will produce marking $M\_2$.

Of course this may be extended by allowing multiple transitions, or even bags of transitions, to fire all at once. But in standard Place/Transition nets, this isn't very interesting. Firing a bag of transitions has the exact same net effect as firing each of its member transitions in some arbitrary sequence - you don't gain additional behaviour by firing them all at once.

This is no longer true for different kinds of Petri nets, such as

* nets in which transitions may take time, or
* nets with inhibitor arcs.

So, for a proper answer to your question, you'll need to tell us what kind of Petri net you're dealing with.

---
Tags: computation-models, petri-nets
---


# Question
Title: Which approach of mine for an algorithm upper bound is correct?
Say we have this algorithm in Python.

```
def secret(S: list):
   n = len(S)
   while n > 0:
      n = n // 2
      for j in range(n):
         if j in S:
            S.append(j)
   return S

```

I need to find the strictest upper bound (Big-$O$).
I have two approaches to solve this, which give me different solutions and I would appreciate your help deciding which one is correct!

**The first approach:**

According to the python documentations, the `x in s` operator is $O(n)$ where $n$ is the length of the list. (Provided here: https://wiki.python.org/moin/TimeComplexity)

So, at the worst case, in each of the for loop, we search the element $|S|$ times. Say that $|S| = N$, then in each iteration the length of $S$ at the worst case gets bigger by $1$ \- because it does contain $j$ each time, and it adds this $j$.

The first iteration of the `while loop`: $\text{range}(N/2)$

$$ N + (N+1) + (N+2) + \dots + N + \frac{N}{2} = \frac{N^2}{2} + 1 + 2 + \dots + \frac{N}{2} = \frac{N^2}{2} + \frac{\frac{N}{2}(\frac{N}{2} + 1)}{2}$$

At the second iteration of the `while loop`: $\text{range}(N/4)$

$$N + \frac{N}{2} + (N + \frac{N}{2} + 1) + (N + \frac{N}{2} + 2) + \dots + (N + \frac{N}{2} + \frac{N}{4}) = \frac{N^2}{4} + \frac{N^2}{8} + 1 + 2 + 3 + \dots + \frac{N}{4} = \frac{N^2}{4} + \frac{N^2}{8} + \frac{\frac{N}{4}(\frac{N}{4} + 1)}{2}$$

The $k$-th iteration is by:

$$I\_k = \frac{N^2}{2^k} + \frac{N}{2^{k-1}} \cdot \frac{N}{2^k} + \sum\_{i=1}^{N/2^k} i$$

and over and over... exactly $\lg(N)$ times.

$$ \sum\_{k=1}^{\lg(N)} I\_k$$

Which is (if I am not wrong here): $$O(N^2 \lg (N))$$

**The second approach:**

The second approach is like the first, but I noticed that while it's true that the `x in S` operator is $O(|S|)$, it is not $|S|$ (the **current** size) in this case specifically, as we insert these numbers if they are already in the array! so each iteration will be at most $O(N)$ and not $O(|S|)$

And so the math gets easier and we do on the first iteration:

$$\overset{N/2 \text{ times}}{N + N + N + \dots + N} = N^2 / 2$$

On the second iteration it would be:

$$\overset{N/4 \text{ times}}{N + N + N + \dots + N} = N^2 / 4$$

and this keeps going of course, $\lg(N)$ times, so we have this sum:

$$ \sum\_{k=1}^{\lg(N)} N^2 / 2^k$$

Which at the end goes to be:

$$O(N^2)$$

---

Which one is correct?

When we recognize the 'live' updating size of $N$ (starting at $N$, then $N+1$, then all the way to $N+N/2$, then $N+N/2+1$ all the way to $N+N/2+N/4$, ...)

Or not recognize the live updating size, as the `in` operator would surely find the number **at most** $N$ iterations? ($N$ is the starting size of $S$.)

# Answer
> 2 votes
#### A simple proof of $\Theta(N^2)$ time-complexity

Each iteration of the `while loop` will cut $n$ in half and, at worst, increases the size of $S$ by $n$. In the $i$-th iteration of the `while loop`, $n\le\frac{N}{2^i}$.

Hence the line `S.append(j)` can be executed at most $N/2 + N/4 + N/8+\cdots = N$ times. So, $|S|$ is at most $N + N= 2N$ at any time.

Each appendment takes $O(1)$ time except possibly when the capacity of $S$ is doubled, at which time the appendment takes $O(N)$ time, assuming the usual implementation of Python. So, the total time that is spent on that line is at most $O(N)$.

Now consider the total time spent on `if j in S`. Each execution will take at most $|S|$ time. So the total time is no more than $$ \frac{N}2 (2N) + \frac{N}{2^2}(2N) + \frac{N}{2^3}(2N) + \cdots = 2N^2$$

Hence, $O(N^2)$ is an upper bound.

---

Consider the first iteration of the while loop, which is basically

```
      for j in range(N//2):
         if j in S:
           #

```

If `j` is not in $S$, `if j in S` will take $\Theta(|S|)$ time. In order to execute `if j in S` faster, we can assume all `j`s are in $S$. Since it takes different number of lookups to find different `j`s, the least total number of lookups needed to execute `if j in S` `for j in range(N//2)` is $$1 + 2 + \cdots + (N//2-1)=\Theta(N^2).$$

Hence, $\Omega(N^2)$ is a lower bound.

---

So, the time-complexity is $\Theta(N^2)$.

In particular, the strictest upper bound in big $O$-notation is $O(N^2)$.

#### "You can improve the bound in your first approach"

Let us do the math more carefully.

> The $k$-th iteration is by: $$I\_k = \frac{N^2}{2^k} + \frac{N}{2^{k-1}} \cdot \frac{N}{2^k} + \sum\_{i=1}^{N/2^k} i$$

So, $$I\_k = \frac{N^2}{2^k} + \frac{N^2}{2^{k}}\frac1{2^{k-1}} + \frac N{2^k}(\frac N{2^k}+1)/2= \frac{N^2}{2^k}(1 + \frac1{2^{k-1}}+\frac1{2^k}+\frac1N)\lt\frac{N^2}{2^k}(1+1+1+1)=\frac{4N^2}{2^k}$$

So, $$ \sum\_{k=1}^{\lg(N)} I\_k\le 4N^2\sum\_{k=1}^{\infty}\frac1{2^k}=4N^2.$$

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


# Question
Title: What is a sorting algorithm that is robust to a faulty comparison?
I want to sort a list of `n` items with a comparison sort. However, one of the comparisons made by the algorithm will be flipped from what it's supposed to be. Specifically, there is one pair of items for which the comparator function consistently gives the wrong result.

What is a efficient `n*log(n)` sorting algorithm that will be robust to this faulty comparison? By robust, I mean that every item is off by at most `k` spots from its true position, for some reasonably small `k`.

If possible, I'd like it to be robust in the worst case (faulty comparison chosen adversarially), but I'll settle for robust in the average case.

An example robust algorithm (that's not efficient), would be to make all `n*(n-1)/2` pairwise comparisons, and place each item by how many of the comparisons they won. Then, no matter what comparison the adversary makes, each items index will be off by no more than `k=1`.

An example of a NON-robust algorithm is quicksort, because the adversary could just choose the largest item to be on the wrong side of the first pivot, making it on average `n/2` spots off from its correct index.

# Answer
> 2 votes
I think I've thought up a solution.

First, do a first pass with any decent sorting algorithm you want (like quicksort), which should, at worst, result in only one item that's significantly far from where it should be.

Then, choose a width `h` that's at least 5.

`for i from 0 to n-h`, we look at the group of `h` items at `i, i+1, ..., i+h-1`. We make all `h*(h-1)/2` pairwise comparisons in that group, and rearrange them by who won the most comparisons. We then increment `i` and move onto the next group.

Afterwards, we do the same thing, but going backwards from `i=n-h` to `i=0`.

These two extra passes will bubble up/bubble down the displaced item to be in the correct area, and uses the extra comparisons in a group of `h` to override the faulty single comparison.

The final number of comparisons will be `O(n*log(n)) + n*h*(h-1)/2`. Not sure how much better you can do.

This method also works (I think) for more than one faulty comparison. All you need to do is make sure that `h` is large enough to override those faulty comparisons.

# Answer
> 1 votes
It seems that this tends to be referred to as "noisy" comparison / information rather than faulty.

This paper specifically analyzes various sorting algorithms "robustness" in the context of faulty comparisons and shows both how it affects time/comparisons and the accuracy of the final result. According to their results, merge and quick sorts are the best traditional sorting algorithms. A swiss tournament gives better results, which makes sense since tournament systems are generally designed around the idea of imperfect comparisons. They get the best results from their own algorithm, which appears to be essentially tournament sort.

Sorting from Noisy Information may also be of interest.

# Answer
> 0 votes
If I give you an additional hint, that the two items that are consistently compared incorrectly are adjacent in the correctly sorted array, and I’ve sorted the array for you already so that only these two items are not correctly sorted, then there is no way for you to find out which pair is ordered incorrectly.

Another observation: If the array looks correctly sorted, that is $a\_1 \< a\_2 \< ... \< a\_n$, and A, B are the two values that are consistently compared incorrectly, then either A, B are adjacent (but in the wrong order) in the sorted array and it is impossible to find out which array elements are A and B, or the array is correctly sorted.

If you sort the array using Quicksort with O (n log n) comparisons, and only one of the n^2 / 2 comparisons gives the wrong result, then it is highly likely (some constant times log n / n) that all comparisons gave the correct result, and therefore the array is correctly sorted. In every partitioning, unless you took A or B as the pivot then the partition step is done correctly, the sub-partitions are created correctly.

If say A is the pivot, and B is within the partition, then B will be moved into the wrong sub-partition. Say A \< B. B should go into the right sub-partition but goes into the left one instead. If we are very unlucky, then A is also (correctly) in the left sub-partition, later B is picked as a pivot, and A is moved (incorrectly) to the right sub-partition of the left partition. So there is a small chance of B ending up in the wrong place, and an even smaller chance of both A and B ending up in the wrong place.

PS. How you can go wrong...

Assume we have $a\_1 \< a\_2 \< a\_3 \< ... \< a\_n$, and A and B are the two numbers that are compared incorrectly. Clearly each comparison is correct and the array sorted unless A and B are adjacent in the array. If we have say $a\_k \< A \< B \< a\_{k+3}$, when in reality A \> B, then it is possible that $A \> a\_{k+3}$ and $B \< a\_k$, so having an array that looks sorted doesn't mean much at all.

However, if we also have $B \> a\_k$ and $A \< a\_{k+3}$ then we have indeed A and B between $a\_k$ and $a\_{k+3}$ and the array cannot be distinguished from a correctly sorted array.

---
Tags: algorithms, sorting, average-case, comparison, adversary
---


# Question
Title: What Good Is Kolmogorov Complexity Since It Is Relative?
Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a constant that depends on the choice of that pair. They can't disagree too much because one can always switch over to emulating the other. However, this amount of maximum disagreement can be arbitrarily large.

Given that, of what use is Kolmogorov complexity? I suppose if you have a sequence of bitstrings, then you can talk about the asymptotic growth of the complexity of these bitstrings, and you will know that this is independent of choice of UTM.

But I thought that Kolmogorov was supposed to be meaningful for individual finite strings. But every bitstring can be produced by an arbitrarily small program: imagine a language that functions just like Java but where an empty file produces the bitstring under consideration.

Doesn't this relativity make Kolmogorov complexity basically pointless? I must be mistaken, right?

# Answer
> 3 votes
The relativity is up to an additive constant. Suppose that you express Kolmogorov complexity relative to your favourite universal Turing machine $U$, but I do it relative to my favourite UTM $V$. If the shortest program for $V$ that outputs a string $x$ is $M$, then the shortest program for your machine $U$ can't be any longer than the one that simulates $V$ running $M$, and that has length $|M|+k$, where $k$ is the size of the simulator.

So, yes, you could pick a UTM that has a very efficient coding for some finite set of strings. However, that would increase the length of the coding of at least that the same number of other strings, and we're typically interested in the asymptotic behaviour of infinite families of strings, rather than individual strings.

# Answer
> 1 votes
You're not wrong. All that Kolmogorov complexity theory can say is that most strings are incompressible, which is known by simple counting arguments, and is a purely informational, not computational property.

As to which strings are compressible and which ones aren't, this is entirely up to how your particular machine represents the small subset of compressible ones, where the constant matters a lot. What goes into the constant are all the things needed to extract this small special subset and so it ends up being everything about the choice of machine and nothing about the actual string. After all, you do not get something for free (compression) by playing programming games, even with a UTM; you merely move information around, e.g. into the machine's construction.

Since practically we care about compressible strings, not incompressible ones, Kolmogorov complexity theory in the original version is useless.

However, the interpretation of complexity in equivalent computational terms is insightful and has led to other variants of Kolmogorov complexity on constrained machines (not UTM's) that are more practically useful.

# Answer
> 0 votes
I think the key point that is missing is that task for infinite families of bitstrings is not that different from fixed bitstrings.

The Kolmogorov Complexity measures the length of your Java code or any other language, it may also measure the compiled program length, which is still *relative* to architecture and OS. When you imagine a program taking input then you are probably thinking about conditional Kolmogorov Complexity.
The standard KC states that it is the length of a program in predetermined description, it is true that various languages, hardware and software will yield various result, but we are interested in particular configuration to find the minimal description. Taking it to any level, the minimal amount of information needed is the same. The constant that occurs due to invariance theorem is irrelevant for many theoretical aspects, and takes into account the UTM choice, which allows to concentrate on the main problem: how compressible is given bitstring and move on.

For finite amount of bitstrings we are interested in the sum of one programs length and inputs lengths that will recover the original representation, but such program will not be able to produce anything else. Good, it was not the point!

---
Tags: computability, information-theory, randomness, kolmogorov-complexity
---


# Question
Title: K-Modes Clustering with Partially-Overlapping, Variable-Length Data?
I'm working on a project that's attempting to cluster books using machine learning. I'm using the K-Prototypes algorithm for clustering data that has both numerical and class-based data. Under the hood it uses the K-Modes algorithm for class-based book fields (such as genre), and K-Means for numerical data (such as year published).

I'm running into an issue with the genre data on a book. A book can have a variable length of assigned genres, and those genres are not all overlapping. For example:

Book A genres: `["Sci-Fi", "Fantasy", "Futuristic"]`

Book B genres: `["Sci-Fi", "Horror"]`

Book C genres: `["Historical", "Fantasy", "Romance", "Love", "Fiction"]`

Most of the literature online discusses class-based data for a single potential class, that's shared across multiple instances. For example: car color could be one of the following: `["Red", "Green", "Blue"]` and every car item is assigned one of those three values for 'color'. What's the proper way of using K-Prototypes (and K-Modes really) with dynamically fetched, variable length, non-overlapping classes like the genre example above?

Thanks for the help!

# Answer
> 3 votes
I don't know how if there's a "proper" way to do this, but defining a similarity measure between two bags of "words" is a well-trodden path in information retrieval.

Let $B$ be the set of all books, and $G$ be the set of all genres. For some $b \in B$ and some $g \in G$, denote the *term count* $f\_{g,b}$ to be:

$$f\_{g,b} = \begin{cases}1,\\,\hbox{if book }b\hbox{ has genre }g\\0,\\,\hbox{otherwise}\end{cases}$$

(Note that you can easily generalise this to "books" where the number of times a "genre" appears is important. This is how it's used in information retrieval, where a document that uses a word like "football" a lot is probably more relevant to the topic of football than one that uses the word only once.)

Then one simple measure of similarity between two books $b\_1$ and $b\_2$ could just be the inner product of these two vectors. This is called the *cosine measure*, because the dot product of two vectors in Euclidean space is proportional to the cosine between the two vectors:

$$\mathrm{cosine}\_{\mathrm{simple}}(b\_1,b\_2) = \sum\_{g \in G} f\_{g,b\_1} f\_{g,b\_2}$$

This measure, however, would artificially weight books which have a lot of genres listed higher. More common is to use the relative frequency of a genre within a book, called the *term frequency*:

$$\mathrm{tf}(g,b) = \frac{f\_{g,b}}{\sum\_{g' \in G} f\_{g',b}}$$

And then:

$$\mathrm{cosine}\_{\mathrm{weighted}}(b\_1,b\_2) = \sum\_{g \in G} \mathrm{tf}(g,b\_1) \cdot \mathrm{tf}(g,b\_2)$$

Next step up in complexity is *tf-idf*, short for "term frequency, inverse document frequency". The theory behind this one is that some genres (e.g. "fiction") probably shouldn't weigh as highly as others (e.g. "historical").

To weight each genre, we use a little information theory. The probability that a randomly picked book will have the genre $g$ is:

$$P(g) = \frac{\left| \left\\{ b \in B : f\_{g,b} \> 0 \right\\}\right|}{\left|B\right|}$$

So the information content of the message "a randomly-chosen book has genre $g$" is $-\log P(g)$. We call this the *inverse document frequency*:

$$\mathrm{idf}(g) = -\log P(g) = \log \frac{\left|B\right|}{\left| \left\\{ b \in B : f\_{g,b} \> 0 \right\\}\right|}$$

Then the similarity measure is simply these two functions multiplied together:

$$\mathrm{ifidf}(g,b) = \mathrm{tf}(g,b) \cdot \mathrm{idf}(g)$$

And then the similarity of two books is simply the weighted sum over all genres:

$$\mathrm{similarity}(b\_1,b\_2) = \sum\_{g \in G} \mathrm{tfidf}(b\_1,g) \cdot \mathrm{tfidf}(b\_2,g)$$

These are just two possibilities. BM25 is a popular similarity measure used in information retrieval.

But there are other options. Once you are thinking of each book as a frequency histogram of genres, a whole world of similarity measures opens up. Some method based on the Kullback-Leibler divergence might work, for example.

All of these methods are principled, but perhaps there's more art than science here...

---
Tags: algorithms, machine-learning, clustering
---


# Question
Title: Automata Regular Language - if $L_1$ and $L_1-L_2$ is regular, than $L_1\cap L_2$ is...?
Given $L\_1,L\_2$ which can be any regular / non-regular languages.

Let $L\_1$ and $L\_1-L\_2$ be regular languages.

I want to know if $L\_1\cap L\_2$ must be regular or not.

So, I wrote $L\_1-L\_2=L\_1\cap L\_2^c$ which is regular.

From here I don't really know what to do, because $L\_2^c$ can be wither regular or non-regular.

I think that I struggle to understand what the difference operations actually means.

Any hints?

Thanks!

# Answer
> 0 votes
Your first try is to express $L\_1\setminus L\_2$ using the intersection operation. However, we know nothing about regularity of $L\_2$ in advance. In fact, $L\_2$ can be irregular, say, if $L\_1 = a^\*$ and $L\_2=\\{b^{n^2}|n\>0\\}$ (the language $L\_1\setminus L\_2$ is clearly regular, since it is empty). Instead, you can try to do an inverse: express $L\_1\cap L\_2$ using $L\_1$ and $L\_1\setminus L\_2$. Both these languages are regular, thus any boolean operation over them results in a regular language.

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


# Question
Title: T(1)=1 is a boundary condition of the recurrence $T(n)=2T(\lfloor{n/2}\rfloor)+n$. Does there exist any other boundary condition of the recurrence?
Section 4.3 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" uses the following recurrence as an example to illustrate the substitution method.

$T(n) = 2T(\lfloor{n/2}\rfloor)+n \tag{4.19}$

That section says

> Let us assume, for the sake of argument, that T(1) = 1 is the sole boundary condition of the recurrence.

In reality, does there exist any other boundary condition of the recurrence (4.19)?

# Answer
> 2 votes
Once you specify $T(1)$, the recurrence determines $T(n)$ for all $n \geq 2$. The value of $T(1)$ itself is arbitrary.

Given $n \geq 1$, construct a sequence of integers as follows. The starting point is $n\_0 = n$. If $n\_i \geq 2$, then $n\_{i+1} = \lfloor n\_i/2 \rfloor$. The sequence stops once $n\_\ell = 1$. You can check that $\ell = \lfloor \log\_2 n \rfloor$. Unrolling the recurrence, we have $$ T(n) = n\_0 + 2n\_1 + 4n\_2 + \cdots + 2^{\ell-1}n\_{\ell-1} + 2^\ell T(1). $$ Therefore if we define $T\_C(n)$ to be the solution to the recurrence with initial condition $T\_C(1) = C$, then $$ T(n) = T\_0(n) + 2^\ell T(1). $$ Also, $n/2 \< 2^\ell \leq n$. Therefore the choice of $T(1)$ only affects the solution by an additive factor of $\Theta(n)$.

---
Tags: algorithms
---


# Question
Title: When proving a set is not regular is it enough to prove a subset of it regular?
E.g. when proving $L = \\{w \in \\{a,b\\}^\*:$ the first, the middle, and the last characters of w are identical$\\}$, can i just prove $ab^{p}ab^{p}a$ is not regular? Where $p$ is the pumping length?

# Answer
I think you mixed up a few things here. Say, L is indeed regular. Then the pumping lemma guarantees us **a** pumping length.

If we want to show that $L$ is **not** regular, we can go on by assuming its regular and for every pumping length we **find a word that cant be pumped.**

This means, we need to search for a word (for example $ab^pab^pa$ as you have suggested) and show that no matter how you divide this word into the 3 pieces $x,y,z$ ($w=xyz$) of the pumping lemma, you can find an integer $n$ with $xy^nz\notin L$. This would contradict the pumping lemma and therefore the regularity of $L$.

As a side note, showing that a **subset** of $L$ is not regular doesnt imply that also $L$ is not regular (for example, $\Sigma^\*$ is regular, but there are non-regular languages which are obviously subsets of it).
> 1 votes

# Answer
I think L is irregular. Let's assume it is. Then $\\{ab\\}^\*$ has an irregular subset, but is clearly regular. On the other hand, L has an irregular subset (L itself) but is irregular. So you can't conclude anything from the irregularity of a subset.

And both the empty language and any language with a single element are regular, so any language, regular or irregular, has a regular subset. Again, it proves nothing.
> 1 votes

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


title: Product of sparse polynomials with FFT

text:
# Question
Title: Product of sparse polynomials with FFT
I need to compute the product of two polynomials $f(X)$ and $g(X)$ over a finite field. The degrees of these polynomials are $n^2$ for some integer $n$. However, we also know that the polynomials are sparse in the sense that most coefficients are zero and furthermore, only $O(n)$ of the coefficients are non-zero.

Can we compute the product $f(X)\cdot g(X)$ in runtime $O(n\cdot \log^2(n))$ via FFT? If not, could we at least do it in subquadratic runtime?

# Answer
> 2 votes
Let $n\>0$.
Let $f(X)=X^{n^2} + X^{n(n-1)} + X^{n(n-2)}+\cdots + X^n + 1$.
Let $g(X) =X^{n^2} + X^{n-1} + X^{n-2} + \cdots + 1$.

$$\begin{aligned} f(X)g(X)&=f(X)X^{n^2} + f(X)(X^{n-1} + X^{n-2} + \cdots + 1)\\ &=X^{2n^2}+X^{2n^2-n} + \cdots + X^{n^2+n} + X^{n^2} + {}\\ &\quad\quad X^{n^2+n-1}+X^{n^2+n-2} +\cdots+ X^2 + X + 1\\ &=\sum\_{2n\ge i\ge n+1}X^{ni} + \sum\_{n^2+n-1\ge i\ge n^2+1}X^i \ \ + 2X^{n^2} + \sum\_{n^2-1\ge i\ge0}X^i \end{aligned}$$

The number of non-zero coefficients of $f(X)$ is $n+1$.
The number of non-zero coefficients of $g(X)$ is $n+1$.
The number of non-zero coefficients of $f(X)g(X)$ is $(n+1)^2-1=n^2+2n$.

It is impossible to list all nonzero coefficients of $f(X)g(X)$ in subquadratic runtime of $n$ in the worst time. So, it is impossible to compute all nonzero coefficients of $f(X)g(X)$ in subquadratic runtime of $n$.

---
Tags: runtime-analysis, sparse-matrices, fast-fourier-transform
---