# Question
Title: Proving that $a^{2^kp}$ isn't context-free (where $p$ goes over all primes)
I have this language and have to prove that its not context free:

$$L = \\{a^{2^kp } \mid k \in \mathbb{N}, p \text{ is prime number}\\}.$$

Because it's unary, a context free language is also regular, so it should be enough to prove that this language isn't regular.

Proving $a^p$ and $a^{2^k}$ aren't regular is simple. But how do I prove it with the "product" of these two?

My thought was, because $a^{2^k}$ isn't regular and also not context free, if $a^{2^k}$ were regular/context free, concatenating this language $p$ times, we would deduce that the above language would also be regular/contextfree, because regular and CFL are closed under concatenation. But because $a^{2^k}$ isn't regular/context free, the $p$-times concatenation of this also isn't regular/context free.

Is my attempt correct?

# Answer
> 1 votes
Your attempt is wrong for several reasons:

1. If $L$ isn't regular then it doesn't mean that $L^p$ isn't regular. For example, let $L = \\{ a^{n^2} : n \geq 0 \\}$. Then $L$ isn't regular but $L^4$ is regular.
2. The language $L^p$ (the concatenation of $p$ copies of $L$) is not the same as the language $\\{ w^p : w \in L \\}$. For example, $\\{a,aa\\}^2 = \\{a,aa,aaa,aaa\\}$ whereas $\\{ w^2 : w \in \\{a,aa\\} \\} = \\{aa,aaaa\\}$.
3. To obtain your language from $L' = \\{ a^{2^n} : n \geq 0 \\}$ you will need to take the union of infinitely many powers of $L'$. There is usually very little you can say about infinite unions, since every language can be written as an infinite union of words.

One way to show that your language isn't regular is using the following criterion:

> Suppose that $L = \\{ a^i : i \in S \\}$ is an infinite regular language. Then $|S \cap \\{1,\ldots,n\\}|/n$ tends to a positive rational limit.

This criterion follows from the fact that $L$ is regular iff $S$ is eventually periodic.

The Erdős–Kac theorem implies that the fraction of numbers in $\\{1,\ldots,n\\}$ with at most two distinct prime factors tends to 0. In particular, if $S = \\{ 2^k p : k \geq 0, p \text{ prime} \\}$ then $|S \cap \\{1,\ldots,n\\}|/n \longrightarrow 0$. Since $L$ is infinite, the criterion shows that it is not regular.

# Answer
> 0 votes
Since every context-free language over a one-symbol alphabet is regular (see this question), it suffices to show that your language isn't regular. Assume it is and denote by $n$ the integer of the pumping lemma for regular languages and pump the string $s=2^kp$ where $k$ is chosen to be less than $\log\_2n$. From here, the proof runs exactly as the standard proof for the language $\\{a^{2^k}\mid k\>0\\}$.

---
Tags: formal-languages
---


# Question
Title: Are the sets of all finite automata and pushdown automata countable?
So considering that set of all turing machines is countably infinite, can we also say that set of all FA machines(DFA/NFA) or set of all PDA machines(DPDA/NPDA) are countably infinite, Considering that we can build all of them with Turing machine?

# Answer
> 2 votes
The answer to your first question is yes, the sets of FAs and PDAs are countable. It's easy to see that since each such machine can be completely described by a finite encoding of its relevant information, like its states and its transition function.

For the second question, there are lots of languages (uncountably many, as the video shows), and almost all of them simply cannot be recognized by any FA. Any non-regular language will suffice as an example, like $\\{0^n1^n\mid n\ge 0\\}$. The same result holds for the languages recognized by PDAs: there are languages that aren't context-free, like $\\{0^n1^n0^n\mid n\ge 0\\}$.

# Answer
> 2 votes
The set of all finite automata is indeed countable, but that has nothing to do with the set of all TMs being countable. The two models are only related by the set of languages they accept, but both have infinitely many machines per language so we can't immediately conclude anything about the sets of machines.

You can prove countability with the usual means: working from the formal definition of FAs (something like $A = (Q, \Sigma, \delta, Q\_F)$), construct an injection into $\mathbb{N}$. That's tedious, but elementary. For PDAs, it works just in the same way.

# Answer
> 1 votes
If you define finite automata as Turing machines with a single working tape that could be just read from left to right, and similar PDAs as Turing machines with an additional working tape that could be just used as a stack, then the countability of Turing machines gives you the countability of FAs and PDAs as they form subsets. But in general if you define these models independently, then you have to explicitly construct for each FA or PDA a corresponding TM, and this construction must be unique (i.e. an injection from the FAs or PDAs to TMs) to employ the fact that TMs are countable.

Let me add that the Turing definable languages are countable, but are not **effectively** countable, i.e. there is no Turing machine itself that enumerates them. This is a classic result related to the Halting problem. But in the case of finite automata (or PDAs) we can indeed **effectively** enumerate them. For the regular languages, just built a TM that enumerates finite automata for increasing size of states and alphabet (removing duplicates if you want to, as finite automata equivalence is decidable). Similar for PDAs, but in this effective enumeration their might be machines that describe the same language, and as context-free language equivalence is undecidable I do not see any way to get rid of them.

Hence in some sense we have a "stronger" notion of countability for regular or context-free languages then for general Turing definable languages.

---
Tags: automata, finite-automata, pushdown-automata, uncountability
---


# Question
Title: What are the (efficient) algorithms to cluster squares into groups using a threshold such that the closest squares form groups?
I have a set of rectangles that needed to be grouped based on their locations. (All the rectangles follow the same orientation.) Two rectangles would be in the same group if the distance between them is less than a certain (constant) threshold.

The obvious algorithm will find all groups in ${O(n^2)}$ time. What I am looking for is an efficient algorithm that can perform better.

# Answer
Store the centers of the rectangles in a data structure that supports efficient nearest-neighbor queries, such as a quadtree. Now for each rectangle $R$, you can determine whether there exist any other rectangles within the prescribed distance, and if so, list them all. Then you can merge all such rectangles into the same group by using a union-find data structure to keep track of which rectangles are in which group. Each rectangle starts out in its own group, and when you find two rectangles that are close to each other (within the prescribed distance), you use the Union operation to merge their two groups.

A number of optimizations are possible. Here is one simple optimization. For each internal node in the quadtree, keep track of a single bit that indicates whether all points (rectangles) in the subtree under that node are known to be in the same group. When enumerating neighbors to $R$, if that bit is set, then you don't need to enumerate all points under that node; it's enough to find any one point (rectangle) under that node, and merge it into the same group as $R$.
> 4 votes

---
Tags: algorithms, computational-geometry, clustering
---


title: Bilinear Interpolation

text:
# Question
Title: Bilinear Interpolation
I am trying to implement bilinear interpolation as described in the paper **Spatial Tranformer Networks** by *Jaderberg et. al* (see link to paper). They describe bilinear interpolation in Equation 5 as:

$$ V\_i^c = \sum\_{n}^{H}\sum\_{m}^{W} U\_{nm}^c \max(0,1-|x\_i^s - m|)\cdot\max(0,1-|y\_i^s - n|), $$ where:

* $V\_i^c$ is the resulting pixel value in the new image
* $H$ and $W$ are the height and width of the original image (or feature map) in pixels
* $c$ refers to the channel (e.g. RGB)
* $(x\_i^s, y\_i^s)$ are the coordinates where the original image is sampled (where the image is normalized such that $-1 \le x\_i^s, y\_i^s\le 1$)
* $U\_{nm}^c$ is defined as the pixel value at location $(n,m)$ in channel $c$.

I am having trouble interpreting the variables $n$ and $m$. Are these

* coordinates in the normalized image (i.e. $-1 \le n, m\le 1$, where you would sum $n$ from $n=-1$ to $H=1$ in steps of the normalized resolution, e.g. steps of $1/100$ for an image that is 100 px in height)
* or are these row and column values (e.g. you sum $n$ from $n=0$ to $n=100$ for an image that is 100px in height)?

I have tried out both to do downsampling of an image, but don't get consistent results.

If someone can help me out interpreting this, I would appreciate it very much.

Below I have included what I understand of bilinear interpolation. Maybe that someone can help me out based on this.

---

In the below figure, a single channel feature map (or image) with one channel is displayed that consists of four pixels with values $ U\_{nm} $, where $ n $ and $ m $ are the coordinates of the center of the pixels, i.e. $ m,n \in \\{-0.5, 0.5\\} $. If we index $ m $ and $ n $ as $ m\_k, n\_k $, with $ k \in \[1,4\] $, we can also index the pixel values as $ U\_{n\_km\_k} $. The values of all four pixels can be reduced to a single value $ V $ at position $ (x\_i^s, y\_i^s) $ by applying bilinear interpolation.

The procedure can be divided into three linear interpolations. First the value $ U\_1' $ at position $ (x\_{U\_1'}, y\_{U\_1'}) $ can be computed by interpolating the values $ U\_{n\_1m\_1} $ and $ U\_{n\_2m\_2} $: \begin{equation} U\_1' = \Delta x\_2\ U\_{n\_1m\_1} + \Delta x\_1\ U\_{n\_2m\_2}. \end{equation} As the sum of $ \Delta x\_1 $ and $ \Delta x\_2 $ is equal to one, due to normalization of the axes, the above equation can be rewritten as: \begin{equation} U\_1' = (1-\Delta x\_1) U\_{n\_1m\_1} + (1-\Delta x\_2) U\_{n\_2m\_2}. \end{equation} The terms $ \Delta x\_1 $ and $ \Delta x\_2 $ can be expressed as: \begin{align} \Delta x\_1 = |x\_i^s - {m\_1}|\\ \Delta x\_2 = |x\_i^s - {m\_2}|, \end{align} which, substituted into the equation for $U\_1'$ yields: \begin{equation} U\_1' = U\_{n\_1m\_1}(1-|x\_i^s - {m\_1}|) + U\_{n\_2m\_2}(1-|x\_i^s - {m\_2}|). \end{equation}

Similarly the value for $ U\_2' $ can be computed: \begin{equation} U\_2' = U\_{n\_3m\_3}(1-|x\_i^s - {m\_3}|) + U\_{n\_4m\_4}(1-|x\_i^s - {m\_4}|). \end{equation}

Once $ U\_1' $ and $ U\_2' $ have been computed, $ V $ can be determined by linearly interpolating $ U\_1' $ and $ U\_2' $: \begin{equation} V = U\_1'(1-\Delta y\_1) + U\_2'(1-\Delta y\_2) . \end{equation} The values for $ \Delta y\_1 $ and $ \Delta y\_2 $ can be expressed as follows: \begin{align} \Delta y\_1 = |y\_i^s - y\_{U\_1'}| = |y\_i^s - {n\_1}| = |y\_i^s - {n\_2}|\\ \Delta y\_2 = |y\_i^s - y\_{U\_2'}| = |y\_i^s - {n\_3}| = |y\_i^s - {n\_4}| . \end{align}

Substituting the above equations and those of $\Delta x\_1$ and $\Delta x\_2$ into the equation for $V$ yields: \begin{equation} \begin{split} V &= U\_{n\_1m\_1}\cdot (1-|x\_i^s - {m\_1}|) \cdot (1-|y\_i^s - {n\_1}|) \\ &+ U\_{n\_2m\_2}\cdot (1-|x\_i^s - {m\_2}|) \cdot (1-|y\_i^s - {n\_2}|) \\ &+ U\_{n\_3m\_3}\cdot (1-|x\_i^s - {m\_3}|) \cdot (1-|y\_i^s - {n\_3}|) \\ &+ U\_{n\_4m\_4}\cdot (1-|x\_i^s - {m\_4}|) \cdot (1-|y\_i^s - {n\_4}|), \end{split} \end{equation} which can be written more compactly as: \begin{equation} \begin{split} V &= \sum\_{k=1}^{4} U\_{n\_km\_k} \cdot (1-|x\_i^s - {m\_k}|) \cdot (1-|y\_i^s - {n\_k}|)\\ &=\sum\_{n}^{H}\sum\_{m}^{W} U\_{nm} \cdot (1-|x\_i^s - {m}|) \cdot (1-|y\_i^s - {n}|). \end{split} \end{equation}

---

**Edit to clarify my comment to @D.W.**

Initially I also thought that $n$ and $m$ are row and column indices as you normally do a summation over integer values. Also the summation is up to $H$ and $W$, respectively, which are the # of rows and # of columns. So it seems logical to think that $\sum\_{n=1}^{H = \\#rows}\sum\_{m=1}^{W = \\#columns}$, with $n=1,2,3,...,H $ and $m=1,2,3,...,W$.

However, when you apply it in this way, the terms within the summation will always be zero. This is because of the condition $-1 \le x\_i^s, y\_i^s \le 1$. Taking the example in the figure where $(x\_i^s, y\_i^s) = (-0,25, 0,25)$, we have: \begin{equation} \begin{split} V &= \sum\_{n}^{H}\sum\_{m}^{W} U\_{nm}\cdot \max(0, 1-|x\_i^s-m|)\cdot \max(0, 1-|y\_i^s-n|) \\ &= U\_{11}\cdot \max(0, 1-|-0.25-1|)\cdot \max(0, 1-|0.25-1|)\\ &+ U\_{12}\cdot \max(0, 1-|-0.25-2|)\cdot \max(0, 1-|0.25-1|)\\ &+ U\_{21}\cdot \max(0, 1-|-0.25-1|)\cdot \max(0, 1-|0.25-2|)\\ &+ U\_{22}\cdot \max(0, 1-|-0.25-2|)\cdot \max(0, 1-|0.25-2|)\\ &= U\_{11}\cdot 0 + U\_{12}\cdot 0 + U\_{21}\cdot 0 + U\_{22}\cdot 0= 0 \end{split} \end{equation} When you have $n$ go from $n=0$ to $H-1$ (and similarly for $m$), it does work in this (simple) example, which would lead to concluding that $n$ and $m$ should start from zero.

However, when you try to apply this to an image which is larger than 2x2 pixels, you get a similar problem than the one for $n=1, ..., H$, i.e. all elements within the summation will be zero when $n\>0$ and $m\>0$.

To clarify this, look at the below image. Here the original image is an 8x8 image with pixels depicted by black squares. We wish to downsample the image to a 6x6 image, depicted by the dashed red squares. If we want to compute the value of the pixel marked by the pink star with coordinates $(x\_1^s, y\_1^s) = (-0.833, 0.833)$, we would have: \begin{equation} \begin{split} V\_{1} &= \sum\_{n}^{H}\sum\_{m}^{W} U\_{nm}\cdot \max(0, 1-|x\_1^s-m|)\cdot \max(0, 1-|y\_1^s-n|) \\ &= U\_{00}\cdot \max(0, 1-|-0.833-0|)\cdot \max(0, 1-|0.833-0|)\\ &+ U\_{01}\cdot \max(0, 1-|-0.833-1|)\cdot \max(0, 1-|0.833-0|)\\ &+ U\_{02}\cdot \max(0, 1-|-0.833-2|)\cdot \max(0, 1-|0.833-0|)\\ &+ ...\\ &+ U\_{10}\cdot \max(0, 1-|-0.833-0|)\cdot \max(0, 1-|0.833-1|)\\ &+ U\_{11}\cdot \max(0, 1-|-0.833-1|)\cdot \max(0, 1-|0.833-1|)\\ &+ ...\\ &+ U\_{77}\cdot \max(0, 1-|-0.833-7|)\cdot \max(0, 1-|0.833-7|)\\ &= U\_{00}\cdot 0.167^2 + U\_{10}\cdot 0.167\cdot 0.833, \end{split} \end{equation} which is only a function of $U\_{00}$ and $U\_{10}$ and not of $U\_{00}$, $U\_{01}$, $U\_{10}$ and $U\_{11}$ as one would reason.

If we look at the blue star with coordinates $(x\_{49}^s, y\_{49}^s) = (0.833, -0.833)$ and apply the same equation, we have: \begin{equation} \begin{split} V\_{49} &= \sum\_{n}^{H}\sum\_{m}^{W} U\_{nm}\cdot \max(0, 1-|x\_{49}^s-m|)\cdot \max(0, 1-|y\_{49}^s-n|) \\ &= U\_{00}\cdot \max(0, 1-|0.833-0|)\cdot \max(0, 1-|-0.833-0|)\\ &+ U\_{01}\cdot \max(0, 1-|0.833-1|)\cdot \max(0, 1-|-0.833-0|)\\ &+ U\_{02}\cdot \max(0, 1-|0.833-2|)\cdot \max(0, 1-|-0.833-0|)\\ &+ ...\\ &+ U\_{10}\cdot \max(0, 1-|0.833-0|)\cdot \max(0, 1-|-0.833-1|)\\ &+ U\_{11}\cdot \max(0, 1-|0.833-1|)\cdot \max(0, 1-|-0.833-1|)\\ &+ ...\\ &+ U\_{77}\cdot \max(0, 1-|0.833-7|)\cdot \max(0, 1-|-0.833-7|)\\ &= U\_{00}\cdot 0.167^2 + U\_{01}\cdot 0.833\cdot 0.167, \end{split} \end{equation} which again is only function of $U\_{00}$ and $U\_{01}$ and not of $U\_{66}$, $U\_{67}$, $U\_{76}$ and $U\_{77}$ as one would expect.

I have also tried normalizing $n$ and $m$, such that $n =-1, -1+ 2/8, -1 +4/8, ..., 1$ (and similarly for $m$, but I end up with similar problems.

# Answer
Yeah, the notation there does seem pretty hard to understand. I suspect they mean row/column indices.

When they write $\sum\_n^H$, I would guess that they mean $\sum\_{n=1}^H$, i.e., a sum where $n$ ranges over the values $1,2,3,\dots,H-1,H$.

Why do I guess this? They say in Section 3.1 that the image has width $W$ and height $H$ and can be viewed as an element of $\mathbb{R}^{H \times W \times C}$, which means that $H$ is the number of rows of the image (its height in pixels). Thus, I can't see any other interpretation of their notation that makes sense to me.

It looks like they might be being inconsistent about when they are using row/column indices vs normalized coordinates. For instance, in (4) and (5) it seems like they are using row/column indices. (As a consequence, the sampling methods choose the interpolated/sampled value for a pixel based only on neighboring pixels... not based on the entire image. That makes sense given how we'd expect bilinear sampling to work.) In contrast, Section 3.2 seems to be written using normalized coordinates. Perhaps they are assuming you'll be able to figure out what they mean from context and then convert between the two representations as necessary. However, for (5), it appears that everything is done using row/column indices.

These are just my guesses.
> 1 votes

---
Tags: image-processing, sampling
---


# Question
Title: Given a sufficiently powerful computer and model, can dice rolls be predicted?
I guess that this is a chaos, randomness and modelling question. Can it be conceived that a sufficiently powerful (perhaps quantum) computer might be able to accurately predict the scores on a physical die tossed from a cup?

I understand that dice land the way they do because of highly complex and chaotic interactions between the die and whatever it hits. There is a concept of total physical modelling (that I don't know the technical term for) that aims to model a real item on an atomic level. This would require great computational power and storage.

Is such modelling possible, or are there fundamental (perhaps quantum) nuances that will always prevent this? They say the weather is chaotic and unpredictable, yet the Met Office now says that today's three day forecasts are as accurate as yesteryear's daily forecasts. Advances seem to be possible...

# Answer
I believe it could be predicted assuming technological limits of sensors and computation were overcome. A die is too large for quantum effects and a simple enough system.

Related paper
> 1 votes

# Answer
You wouldn't need a quantum computer to solve this problem; you'd need a complete set of inputs and assumptions, and a reasonable expectation. I think the question may be under-specified.

*Why quantum computing?*

If you are trying to solve this in real time while watching someone toss the die, e.g. to make money at a casino, there are likely too many variables to ever accurately predict before the die actually falls.

*What do you mean by "tossed from a cup"?*

Is this a controlled experiment? Will the cup, force used to move cup, the die shape, the surface material be consistent? If you'd like to predict for all situations, then there is likely only 1 computer, i.e. the universe, capable of determining the outcome. Otherwise, that is an interesting problem!

*What do you mean by "accurately"?*

If you are looking for the correct prediction for 1000 tosses by 1000 different people , then we could likely say, "nope, can't be done." If accurately means "80% of the time the model predicts the outcome of a toss," then that is an interesting question!

*Next up ... FEA?*

The physics of rolling a die are well understood. The complete set of inputs and assumptions make a good model, and could be used to predict a single die's rolled value with some confidence. The model would likely be limited to a very fine set of criteria, material of the cup, force used to move cup, curvature of the corners of the die, the material of the ground, etc.

Here's an example of some documentation for a detailed Finite Element Analysis of explosives. I didn't have time myself to go through it, but it looks good enough. The best thing about FEAs are the movies.
> 1 votes

# Answer
"Sufficiently powerful" means just that - if you can't predict the dice roll, it would not be because of lack of computing power.

You need to measure the initial conditions, and model how the initial conditions lead to the outcome. That measurement will have some margins of error. If you measured initial conditions C, the real initial conditions will be C + eps for some unknown eps. The question is then: Given different initial values C' that are consistent with your measurements, are different outcomes possible? If yes, then your "sufficiently powerful" computer cannot help.

Instead of dice, take planet movements. The last calculation that I read about showed that planet movements are not predictable for the next 25 million years, because of measurement errors in the initial conditions, not because of any lack of computational power.
> 1 votes

---
Tags: computation-models, randomness
---


title: Cuckoo filters for non powers-of-2

text:
# Question
Title: Cuckoo filters for non powers-of-2
The Cuckoo filters paper (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) claims a 95% load factor, however it seems to make an implicit assumption that the table size is a power of 2, and their implementation also enforces that (https://github.com/efficient/cuckoofilter/blob/master/src/cuckoofilter.h#L90). This means that the load factor can be as bad as ~50%, depending on the number of keys.

The reason seems to be intrinsic to the alternate index algorithm: it is $$ h\_2(x) = h\_1(x) \oplus hash(signature) $$ The XOR makes the algorithm an involution (so the same formula holds to find $h\_1$ from $h\_2$), but the result is smaller than the table size only if the size is a power of 2.

Is there an alternative formula that works with non-powers of two? Basically something that pseudo-randomly maps signatures to involutions of `[0, n)`.

# Answer
> 1 votes
Yes, it is possible. Use

$$h\_2(x) = \text{hash}(\text{signature}) - h\_1(x) \bmod n.$$

The theory behind this: if $c$ is a constant, the function

$$f(t) = c - t \bmod n$$

is an involution for any $c$ and any $n$, since

$$f(f(t) = c - (c-t) = t \pmod n.$$

Therefore, we can use the hash of the signature as the constant $c$. This gives you a scheme that works for any $n$, without requiring that $n$ be a power of two.

# Answer
> 0 votes
If you don't mind doing a test, check whether the current position is in $\[0\\,\mathpunct{\ldotp\ldotp}n/2)$ or $\[n/2\\,\mathpunct{\ldotp\ldotp}n)$, and depending on that add or subtract a random number in $\[0\\,\mathpunct{\ldotp\ldotp}n/2)$ derived from the signature. It's not completely random, but I guess it should work.

You can do the same with other tests, e.g., even/odd. You just add a random odd number based on the signature (even case) or subtract it (odd case).

---
Tags: combinatorics, hash-tables, probabilistic-algorithms, bloom-filters
---


# Question
Title: How to build a PDA that accepts strings which have odd numbers of a and even numbers of b and has only 2 states?
How can i draw a PDA which has **only 2** states and accepts strings which have odd number of a and even number of b?

the alphabet is {a,b}, and the PDA has to be only 2 states?

# Answer
I like to remind you that in fact for *every* context-free grammar there exists an equivalent PDA that has only a *single* state using acceptance by *empty stack*. If we need to use PDA acceptance by *final state* then *two states* are required as we need a working state and a separate accepting state.

The single state construction is given on wikipedia's page for PDA and is called the expand-match construction for "parsing" context-free languages. The state here is called $1$.

1. $(1,\varepsilon ,A,1,\alpha )$ for each rule $\displaystyle A\to \alpha $ (expand)
2. $\displaystyle (1,a,a,1,\varepsilon )$ for each terminal symbol $a$ (match)

Note this uses the classical definition of PDA where the automaton starts with a fixed single element on its stack. A certain textbook has decided to change this basic definition and starts with the empty stack, where an extra state is needed to push the initial stack symbol. (horrible, this textbook is actually quite common and continues to spoil young kids).

when restricted to FSA the construction is actually quite simple. The PDA keeps the state on the stack as its only element. Accepting states of the FSA may be popped from the PDA so the PDA can accept (by empty stack) whenever the FSA can accept.
> 1 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Bucket Priority Queues with large integers for $O(1)$ insert and extract~min?
I recently got into a discussion about Priority Queues when the requirements allow for "best effort" removal (i.e. the removed key may not always be THE very highest priority, but it is relatively close).

After thinking about it a bit I stated "I could probably make it $O(1)$ by using buckets" and approximating the minimum (to bucket size precision). I was politely told that I was wrong. Not taking no for an answer, I later went to Google and found the ample literature on the subject, which seemed to confirm I was wrong :-|

Note that the closely related question, Unique integer priority queue with both $O(1)$ insert and extract-min?, does not allow for approximation, so the answers don't apply to my question.

I was told the standard solution to this problem is to use a queue where keys are appended to the end in $O(1)$ and read from the head in $O(1)$ and which is then periodically sorted in $O(\log N)$ or whatever sorting algorithm you can find.

Assuming 64-bit integers as keys, and a precision of $ \pm 127$ (a 56-bit bucket)... Can't you just hold the buckets in a sparse array (so as not to require $2^{56}$ words of memory)... problem solved?

# Answer
> 1 votes
Your proposed data structure is simply a hash table with some rounding to reduce the number of buckets. Effectively, all this does is divide the problem complexity by some constant factor (128 in your example).

You have no hierarchy in your design, so there is no way to have O(1) access to the smallest/largest non-empty bucket. To achieve this feature efficiently, you're already pretty much bound to some type of priority queue. This class of data structures is well studied, and has various implementations with typically very low bounds on complexity.

---
Tags: data-structures, efficiency, priority-queues
---


title: Fitness model for scale free networks

text:
# Question
Title: Fitness model for scale free networks
In order to generate scale-free networks, we can use this algorithm, derived from Barabási–Albert model:

1) we assign every node a "weight" $\theta\_i$ (or two in the direct case).

2) we place $m$ edges between nodes by choosing the ends of the edges with probabilities proportional to the weights.

With the right choice of the coefficients $\\{\theta\\}$ we can generate a graph with the desired power-law distribution. A very popular method is the so-called Chung-Lu Model and it's, for example, used in the power.law.game function in the igraph library. This model prescribes to number the nodes from 1 to N and then assign to each node a $\theta\_i = i^{-\alpha}$, with $\alpha \in \[0,1)$, then select nodes as the ends of an edge with probability $p\_{ij} \propto \theta\_i \theta\_j$, and repeating for all the edges to put in. The resulting graph will have a degree distribution $p(k) \propto k^{-\gamma}$, with $\gamma = \frac{\alpha}{\alpha +1}$.

My question is: why can't we simply consider a power-law distribution with a finite extent $p(x) = \frac{1-\gamma}{x\_{max}^{1-\gamma} - x\_{min}^{1-\gamma}} x^{-\gamma}$, then sample our $\theta\_i$ from this distribution? This is more intuitive from my perspective, because if my expected degrees follow a power-law distribution, I expect that the graph degree distribution follows the same power-law.

# Answer
I don't know if my solution is correct, but after some searching, I eventually came up to this conclusion:

The algorithm that is used to build the graph is not compatible with a different choice other than $\theta\_i = i^{-\alpha}$.

This is because the algo is derived from the Barabási–Albert with some modifies. We start with N nodes, and we add a link between a couple of nodes every time step until we have added $mN$ edges. First we normalized the weights so they will be the probability that we choose the node $i, \\;$ $\sum\_{i=1}^{N} i^{-\alpha} \sim \frac{1-\alpha}{N^{1-\alpha}}$. We can easily compute the rate at which the node acquires links, since it will be proportional to its degree: \begin{equation} \frac{d\\,k\_i}{dt} = \frac{k\_i}{2mN} = \frac{1-\alpha}{N^{1-\alpha} i^\alpha}, \end{equation} this means that we will select the node $i$ with probability $p(i) = k\_i ^{-\frac{1}{\alpha}}$. This is equal to the probability that a node has a degree $k\>k\_i$, so it is related to the cumulative probability distribution: \begin{equation} P(k\>\bar{k}) \sim k^{-\frac{1}{\alpha}} \rightarrow p(k) \sim k^{-\frac{1}{\alpha} -1} \equiv k^{-\gamma}, \end{equation} where $\gamma = \frac{1+\alpha}{\alpha}$. Is this a good answer?
> 1 votes

---
Tags: algorithms, graphs, randomness, enumeration, random-graphs
---


# Question
Title: How to access the bit at a particular index?
How do I access the bit at a particular index in a number using shift operator. Say the number is $n$.
Let the index be $i (i: 0 \le i \< n).$
Rightmost bit is $0$.

The only thing I can think of is:
$def \\, bitAt(n, i)$
$\\,\\,\\,\\,\\,\\,\\,\\,m = n \>\> i+1$
$\\,\\,\\,\\,\\,\\,\\,\\,v = n \>\> i$
$\\,\\,\\,\\,\\,\\,\\,\\,m = m \<\< 1$
$\\,\\,\\,\\,\\,\\,\\,\\,if(m == v)$
$\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,return \\, 0$
$\\,\\,\\,\\,\\,\\,\\,\\,else$
$\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,return \\, 1$
$\\,\\,\\,\\,\\,\\,\\,\\,end$
$end$

Is there a more efficient way to do this?

# Answer
This can be done by running an `AND` between `n` and a number with it's `i`th bit set to 1, which can be obtained by `1 << i`. The result of this operation will be zero if the `i`th bit in `n` is zero, or `1 << i` otherwise.

Case of zero:

```
n     = 10111
m     = 01000 (1 << 3)
n & m = 00000

```

Case of one:

```
n     = 10111
m     = 00100 (1 << 2)
n & m = 00100 (1 << 2)

```

So:

$m = 1 \<\< i$

$\text{if}\\; (n \\;\\&\\; m == 0)$

$\\;\\;\\;\\;\text{return} \\;0$

$\text{else}$

$\\;\\;\\;\\;\text{return} \\;1$
> 2 votes

---
Tags: algorithms, bit-manipulation
---


# Question
Title: How to compare algorithms having the same complexity
I am new to programming and want to learn how to compare algorithms having the same complexity and pick the best one. Certain problems can be sloved using several algorithms which have the same complexity. How do i compare such algorithms

# Answer
> 3 votes
By "*having the same complexity*" I assume you mean having the same *time* complexity.

If you have done fine analysis of time complexity of these algorithms then there may be hidden constants or factors of lower degree polynomials which are ignored when you compare using big-O notation but have effect in practice. For example, if one algorithm always takes $n^2 + 100n + 10000$ steps and the second one takes $0.3n^2$ then the second one would be a better choice, though both run in $O(n^2)$.

You could also consider their space complexity and choose one which consumes less memory if the memory consumption matters and more important than the time complexity.

If you aim to implement these algorithms yourself and use it in your commercial application (or something like that) then you could think about how easy they are implemented and how easy these algorithms scale.

# Answer
> 1 votes
If you develop software, it doesn't matter how fast an algorithm is, what matters is that it meets your requirements. Once you have an algorithm that works, and meets the requirements, the cost of making a second algorithm work, and comparing it with the first algorithm, can be very high. And you have only a 50% chance that the second algorithm is better, and a possibly much lower chance that it is better in a meaningful way.

---
Tags: algorithms, complexity-theory, time-complexity, space-complexity
---


# Question
Title: Minimum number of givens for General Sudoku of size $n^2 \times n^2$
Here, it is well known that the minimal number of givens for a size $9 \times 9$ board of Sudoku requires 17 "givens" in order to be solved (i.e., no puzzle can be solved with $\le 16$ givens).

What is the minimal number of givens for a size $n^2 \times n^2$ board? Is there a table of "best-known" minimal values?

I'm speculating that there is only an asymptotic/approximate bound as the $n=3$ case was not known, let alone higher values of $n$. For $n=4$, the best-known is 55, and $n=5$ is 151.

# Answer
The minimum number of clues for a puzzle of $n^2$ x $n^2$ is known for $n = 2$ (4 x 4 Sudoku), of which the **minimum clues is 4** (25% of cells filled). There are 13 such non-equivalent puzzles. (based on info at "enjoysudoku.com").

The minimum number of clues for a puzzle of $n^2$ x $n^2$ is also known for $n = 3$ (9 x 9 Sudoku), of which the **minimum clues is 17** (about 21.0% of cells filled). About 49,000 such non-equivalent Sudokus have been discovered.

For $n = 4$ (16 x 16), the fewest clues known in any puzzle is 55 (about 21.5% of cells filled), but it is not known if this is the fewest possible. (based on info at "enjoysudoku.com").

For $n = 5$ (25 x 25), little work has also been done to find the fewest clues possible, and comparatively few Sudokus of this size have been constructed. One 25 x 25 Sudoku is known to have 328 clues. So from a cursory study, the fewest clues for (n=5) is 328 or fewer (about 52% or fewer cells filled). Note: this Sudoku was not an attempt to be an example with few clues. I listed it only to provide an initial upper bound.
> 2 votes

---
Tags: reference-request, board-games, sudoku
---


# Question
Title: Machine Learning: if test, validation errors are same, the model with lower train loss is better at generalization?
I tuned some hyperparameters and got 2 best models.

These two models are almost the same "test(not train)" and "validation" errors. But `model A` has lower "train" error than `model B`.

In this case, the model with lower "train" error (`model A`), would show good performance on new data? (good generalization)

Or `model A` is more overfitting to the dataset so it would work worse in new data?

Thanks

# Answer
> 1 votes
Though usually the test error is your primary goal, I can imagine some specific cases when the train error also matters. One possible example: training set has much more 'hard' inputs than the test set.

If you ever visually examined MNIST, you've probably seen that some images are puzzling even for a human, while others are much easier to tell. If one would split the training/test set differently, it's possible to see that training error would be higher than the validation or test error.

However, it's important to say that a situation like that indicates that data is probably poorly collected or split. So in this case it's better not to choose model A vs model B, but to check the data.

# Answer
> 0 votes
I don't think there is any reason to expect either one to perform better on new data. Assuming you haven't used the test set for anything other than evaluating these two models, the performance on the test set is the best estimate you have of how well it will perform on new data. Thus if they get the same performance on the test set, I don't think there's any basis for expecting one or the other to be better on new data.

---
Tags: machine-learning
---


# Question
Title: Minimum number of processes for the deadlock?
> A system has 6 identical resources and $N$ processes competing for them. Each process can request at most two requests. Which one of the following values of $N$ could lead to a deadlock?
>
> 1. 1
> 2. 2
> 3. 3
> 4. 4

---

My attempt:

Deadlock free condition is:

$R \geq P(N-1)+1 ,$

Where R is total number of resources,

P is the number of processes, and

N is the max need of resources by each process.

$6 \geq P(2-1) + 1$

$6 \geq P + 1$

$5 \geq P$

So, the number of processes should be less than $5$ for the deadlock free condition.

Hence, all options can not be deadlocked.

---

In this exercise problem the answer given option (4).

> Can you explain it in a formal way, please?

# Answer
> 10 votes
I agree that no deadlock is possible here. If there are three or fewer processes, there clearly cannot be a deadlock because there are enough resources for every process to just hold two resources the whole time.

So any deadlock must have at least four participating processes. To participate in a deadlock, a process must hold at least one resource. Further, a process cannot hold more than two resources so a process that currently has two resources can definitely run until it frees at least one of those resources. Therefore, if there is a deadlock, it must involve four processes, each holding exactly one resource. This means that there are two resources free so any process that requests a resource will be granted it and will then run until it releases one or both of the resources it holds. Out of our set of four supposedly deadlocked processes, at least one is always runnable, so there is no deadlock. (In fact, at least two are runnable at all times.)

Perhaps the question-setter had the following situation in mind. Suppose processes 1 and 2 are using two resources each and processes 3 and 4 are using one resource each. Now, if 3 and 4 each request one more resource, they will block. But this is not deadlock because the situation can be resolved by either one of the two runnable processes (1 and 2) giving up one of their resources. Deadlock is the situation where every one of a set of processes is blocked and the only way to resolve the situation is for one of those blocked processes to give up resources, which it can't do because it's blocked.

# Answer
> 1 votes
I would think that even with 5 processes, deadlock isn't possible. If 5 processes each need up to 2 of six identical resources, we could assume that each acquires one resources, and then we have 5 processes with a single resource left. Sure, four processes may have to wait when one process acquired the last resource, but eventually that process will free a resource, and things progress. No deadlock. (The OP's formula tells the exact same story, just for a more general case).

---
Tags: operating-systems, synchronization, deadlocks, resource-allocation
---


# Question
Title: Longest path in directed graph cyclic graph where each node has one children
Consider given directed unweighted cyclic graph with $N$ nodes, and $N$ edges, and each node has at most one out-going children. Find the longest path.

**Example**

Consider the following graph, the path $2, 3, 1$ is the longest covering all 3 nodes.

**What I think for the solution**

Because every node has at most one children we form some type of equation that for node $a$, and it's children $b$, the path starting from node $a$ = path to start from $b + 1$, but I think because there are cycles this wont work.

# Answer
> 1 votes
As *rus9384* & you seemed to have figured out in the comments, there exists an $O(N)$ solution to the problem.

First, apply the well known algorithm to find Strongly Connected Components in the graph in $O(N)$. Then, after collapsing all such components into single nodes, you can slightly modify the algorithm to find the Longest Path in a DAG to get your answer in $O(N)$ time.

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


# Question
Title: Understanding definition of epsilon closure and finite automata states
I am going through the book , introduction to compiler design , by Torben Ægidius Mogensen.

It provides the following definition of an epsilon closure :

Given a set M of NFA states, we deﬁne $\ \epsilon $-closure($\ M $) to be the least (in terms of the subset relation) solution to the set equation $\ \epsilon $-closure($\ M $) =$\ M $ $\ \cup $ {$\ t $|$\ s $ ∈ $\ \epsilon $-closure($\ M $) and $\ s^\epsilon t$∈T}, where T is the set of transitions in the NFA.

Initially , it defined the notion $\ a^b c $ to mean that a transition from state $\ a $ to $\ b$ takes place when a symbol $\ c $ is encountered .

But in the above definition $\ s^\epsilon t $ , $\ t$ is an element of the set of transitions , not the set of states .

This has resulted in a bit of confusion as to what exactly does an epsilon closure mean .

One more terminology word-play that wanted to be clear about is , the exact meaning of a sentence of the following sort :

"We extend the set of NFA states with those you can reach from these by using only epsilon transitions ."

But in a set of NFA states , the epsilon transition would direct one state to another which would be already included in the set of NFA states. So , how is it possible to extend the same set with the elements already contained in it ?

# Answer
Your textbook is being very formal, probably since it aims at using set equations later on. However, $\epsilon$-closure is a very simple concept. The $\epsilon$-closure of a set $M$ of states is the collection of states that can be reached from a state in $M$ by taking any number of $\epsilon$-transitions (possibly zero).

The textbook uses a different (but equivalent) definition: it defines the $\epsilon$-closure of $M$ to be the smallest set of states that contains $M$ and that for every state $s$ that it contains, contains all states reachable from $s$ by a single $\epsilon$-transition.

Regarding the second quote, there is some context missing. Here is one possible context which would make sense. For an NFA without $\epsilon$-transitions, we define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$. When we have $\epsilon$-transitions, there are several different possible definitions of the transition function. One possibility is to define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$ and then an arbitrary number of transitions labeled $\epsilon$ (possibly none).
> 9 votes

---
Tags: finite-automata
---


# Question
Title: Finding the largest linear combination that is not possible
Regarding the problem:

What is the largest bet that cannot be made with chips worth $\\$7.00 $ and $\\$9.00$? Verify that your answer is correct with both forms of induction.

I need to find an algorithmic approach, but till now my approach is to try all possible combinations with 0,1,2,3,4,5,6,7,8 (9) as the column headings and then the next row having the values as 9,10,... and so on, till able to get all values that can be generated. All this requires an iterative approach that progressively increases the data set size, till at least 9 consecutive values can be generated. I have found that 47 is the largest value that cannot be generated.

But, first of all this is no programmable algorithm. Second, due to first reason, I cannot prove it by induction of any type.

I feel that the algorithmic approach should consider the values that are originating from the initial set of those values that cannot be generated by any linear combination of values; i.e. 1,2,3,4,5,6,8; and then checking out which value will be the last one that can be generated from them and is not a linear combination of $9x + 7y$ (with $x,y \> 0$).

If there were an approach that takes all further points that are not reachable by all the initial set of non-reachable (not having a value given by the linear combination of 9x + 7y, (x,y \>0)) points (1, 2, 3, 4, 5, 6, 8); then I would be very happy to get any hint for the same.

# Answer
> 6 votes
First of all, there is a known formula that gives the correct answer in this case: if $a,b$ are relatively prime, then the maximal element which cannot be written as a non-negative combination of $a,b$ is $(a-1)(b-1)-1$. (Extending this to the case where $a,b$ are not relatively prime is a nice exercise.)

Second, suppose you don't know this formula, and want to prove that 47 is the largest value that cannot be generated. You have to prove two things:

1. 47 cannot be generated.
2. Any larger number can be generated.

To show that 47 cannot be generated, note that if $47 = 9x + 7y$ with $x,y \geq 0$ then $x \< 7$ and $y \< 9$. This means that it suffices checking all $x \in \\{0,\ldots,6\\}$ and $y \in \\{0,\ldots,8\\}$.

To show that any larger number can be generated, you first show that $48,49,50,51,52,53,54$ can be generated, by giving the appropriate values of $x,y$ (for example, $48 = 3 \cdot 9 + 3 \cdot 7$). You then complete the proof by induction (how?).

---
Tags: algorithms, iteration
---


# Question
Title: Can't figure out how to make a grammar LL(1)
Let's say I start with:

$A \rightarrow Ba$

$B \rightarrow dab | cBb | Acb$

Now I want to make this grammar LL(1), so I need to get rid of the left recursion. I'll work with $B \rightarrow Acb$.

I'll replace where $A$ occurs with its production:

$B \rightarrow dab|cBb|Bacb$

And that gives me a direct left recursion, which I rewrite as:

$B \rightarrow dabB' | cBbB'$

$B' \rightarrow acbB' | \epsilon$

At this point this seems like this should be LL(1), so I'm checking: $FIRST$ sets: For $A: \\{d,c\\}$, $B: \\{d,c\\}$ and $B': \\{\epsilon, a\\}$.

$FOLLOW$ sets: $A: \\{eof\\}$, $B: \\{a,b\\}$ and $B': \\{a,b\\}$.

Now I'd like to check $FIRST^+$, but if I do $FIRST^+(B' \rightarrow acbB') = \\{a\\}$ and then $FIRST^+(B' \rightarrow \epsilon) = \\{\epsilon, a, b\\}$ which does NOT have a non-empty intersection.

Does it make sense to look at $FIRST^+$ in terms of each production that has the same left hand side? Or, have I made a mistake in calculating $FIRST$ or $FOLLOW$ sets to begin with? Is there an issue with the rule $B \rightarrow cBb$ (not left recursive exactly but does have the $B$ nestled inside).

# Answer
For context-free grammar to be LL(1), these two requirements have to be met for its every rule $ A \rightarrow \alpha | \beta$:

1. $ FIRST(\alpha) \cap FIRST(\beta) = \emptyset$
2. $ \epsilon \in FIRST(\alpha) \implies FOLLOW(A) \cap FIRST(\beta) = \emptyset$

> Does it make sense to look at FIRST+ in terms of each production that has the same left hand side?

No, as you can see, to decide if grammar fits those rules above, we have to calculate $FIRST$ function for the right-hand sides of the grammar's rules, not for the left sides.

For your grammar, we get these results:

$A: FIRST(Ba) = \\{c,d\\},\space FOLLOW(A) = \\{\epsilon\\}$

$B: FIRST(dabB') = \\{d\\},\space FIRST(cBbB') = \\{c\\}, \space FOLLOW(B)=\\{a,b\\}$

$B': FIRST(acbB') = \\{a\\},\space FIRST(\epsilon) = \\{\epsilon\\},\space FOLLOW(B')=\\{a\\}$

As you can see, there is a $FIRST/FOLOW$ conflict (violated second requirement from above) in $B'$. You can read here about how to solve this.
> 1 votes

---
Tags: context-free, formal-grammars
---


title: Valid, unsatisfied or neither?

text:
# Question
Title: Valid, unsatisfied or neither?
How should I create the truth table to solve each of these questions? Maybe can give me an example?

1. $Smoke \implies Smoke$
2. $Smoke \implies Fire$
3. $(Smoke \implies Fire) \implies (\neg Smoke \implies \neg Fire)$
4. $Smoke \lor Fire \lor \neg Fire$
5. $((Smoke \land Heat) \implies ((Smoke \implies Fire) \lor (Heat \implies Fire)) $
6. $(Smoke \implies Fire) \implies ((Smoke \land Heat) \implies Fire))$
7. $Big \lor Dumb \lor (Big \implies Dumb)$
8. $(Big \land Dumb) \lor \neg Dumb$

# Answer
You would first set up a table with all variables being assigned each possible combination of truth values. You then propagate those truth values to the literals and next smallest subformulae, then continue propagation until you conclude the entire formula.

Example:

$$F: (P \land Q) \implies \neg (P \land \neg Q)$$

$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline P & Q & \neg Q & P \land Q & P \land \neg Q & \neg(P \land \neg Q) & F \\ \hline F & F & T & F & F & T & T \\ \hline F & T & F & F & F & T & T \\ \hline T & F & T & F & T & F & T \\ \hline T & T & F & T & F & T & T \\ \hline \end{array}$$
> 3 votes

---
Tags: logic, propositional-logic
---


# Question
Title: Can a DFA have an empty string as input?
Given string w such that every odd position in w is a 1

My solution is

The book's solution is

from my understanding $\epsilon$ should not be an accepted state, however in the book's solution it is. How is it handling this case?

# Answer
> 5 votes
Yes, an empty string is a valid input to a DFA. If this were not the case, DFAs would not be closed under all of the Kleene algebra operations.

In this case, the argument is correct. Think of the problem statement as an implication. If $i$ is an odd position, then $S\_i$ is 1.

---
Tags: finite-automata
---


title: PTAS definition vs. FPTAS

text:
# Question
Title: PTAS definition vs. FPTAS
From what I read in the `preliminary version of a chapter of the book “Lectures on Scheduling”
edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D.`

This is the *PTAS* Definition:

> A polynomial time approximation scheme (*PTAS*) for problem $X$ is an approximation scheme whose time complexity is polynomial in the input size.

and FPTAS definition

> A fully polynomial time approximation scheme (*FPTAS*) for problem $X$ is an approximation scheme whose time complexity is polynomial in the input size and also polynomial in 1/$\epsilon$.

Then the writer says:

*Hence, for a PTAS it would be acceptable to have a time complexity proportional to $|I|^{1/\epsilon}$ where $|I|$ is the input size;although this time complexity is exponential in $1/\epsilon$. An FPTAS cannot have a time complexity that grows exponentially in $1/\epsilon$ but a time complexity proportional to $|I|^8/\epsilon^3$ would be fine. With respect to worst case approximation, an FPTAS is the strongest possible result that we can derive for an NP-hard problem.*

Then he suggested the following figure to illustrates the relationships between the classes of problems:

Here is my questions:

1. From the *PTAS* and the *FPTAS* definition, how does the writer conclude that the *FPTAS* cannot have a time complexity that grows exponentially in $1/\epsilon$? and what difference does it make if it can have such time complexity?
2. A time complexity like $(n+1/\epsilon)^3$ is acceptable for *FPTAS* but it is not for *PTAS*, then why *FPTAS* is considered to be a subset of *PTAS*?
3. What does he mean by: *an FPTAS is the strongest possible result that we can derive for an NP-hard problem.*
4. In the aggregate I would like to know what exactly these to concepts mean and, what are their distinct properties.

***Thanks in advance.***

# Answer
Let me answer your questions in order:

1. By definition, a problem has an FPTAS if there is an algorithm which on instances of length $n$ gives an $1+\epsilon$-approximation and runs in time polynomial in $n$ and $1/\epsilon$, that is $O((n/\epsilon)^C)$ for some constant $C \geq 0$. A running time of $2^{1/\epsilon}$ doesn't belong to $O((n/\epsilon)^C)$ for any $C$.
An algorithm whose running time is $O((n/\epsilon)^C)$ is better than an algorithm whose running time is only guaranteed to be $O(n^C e^{D/\epsilon})$, since the dependency on $\epsilon$ is better for the first algorithm. Furthermore, for any $E$, we can find an $1+1/n^E$-approximation in polynomial time using the first algorithm but not using the second (at least not with the given guarantee).
2. A problem in which an $1+\epsilon$-approximation can be found in time $(n+1/\epsilon)^3$ is definitely in PTAS, since for every $\epsilon$ this is $O(n^3)$ (exercise) and so polynomial in $n$.
3. What the authors meant here is that since an NP-hard optimization problem can't be solved exactly in polynomial time, the best we can hope for is for it to be $\epsilon$-approximable in polynomial time, and furthermore with a good dependence on $\epsilon$. Among the common complexity classes, FPTAS gives the strongest guarantee on the dependence on $\epsilon$. But in practice we sometimes get an even better guarantee: the running time is polynomial in $n$ and in $\log(1/\epsilon)$. So it's not strictly true that FPTAS is the strongest possible result; it's only the strongest possible result among the options PTAS,FPTAS,P. If we made up a new class LPTAS (corresponding to time polynomial in $n$ and in $\log(1/\epsilon)$), then that would be a stronger guarantee.
4. Given an NP-hard optimization problem, it can't be solved exactly in polynomial time; the best one can hope for is to approximate it efficiently. Some problems are NP-hard to approximate to some constant $C\>1$. For others, it is possible to approximate the problem arbitrarily well in polynomial time, and these problems have a PTAS and so belong to the class PTAS. It might be that a $1+\epsilon$-approximation takes time proportional to $e^{1/\epsilon}$, and so we can only apply this efficiently for constant $\epsilon$. If the problem has an FPTAS (and so belongs to the class FPTAS), then we know that the dependency on $\epsilon$ is only polynomial, and so we can approximate efficiently to within $1+1/n^C$ for any $C$.
> 18 votes

# Answer
Let the instance size be $|I|=n$. The difference between a PTAS and an FPTAS is that, in the former $\epsilon$ is a fixed constant, so that it can be treated as a constant. That is why a running time such as $n^{1/\epsilon}$ is still polynomial in instance size $n$ (also in input size as $\epsilon$ is a fixed constant anyway). In an FPTAS, $\epsilon$ is not fixed. The approximation scheme must be polynomial in $1/\epsilon$ as well as $n$ (ie, $\mathrm{poly}(n,1/\epsilon)$ as in $n^4 (1/\epsilon)^3 + (1/\epsilon)^8$). A running time such as $n^{1/\epsilon}$ is clearly not polynomial in $n$ and $1/\epsilon$. Hence such an approximation scheme is a PTAS but not an FPTAS.
> 1 votes

---
Tags: algorithms, complexity-theory, terminology, complexity-classes, approximation
---


# Question
Title: What algorithm to use for this subset sum problem
I have a typical subset sum problem and I'm looking to choose the proper algorithm to solve it, the set contains (around) 1000 elements, and elements are constrained to max 22 bits for now.

I have been looking around and looks like the well known O(2^(n/2)) is not an option, and looking into the Dynamic Programming version memory becomes a big concern, because the elements values are pretty balanced

n=1000 s=962,425,151 (Avg=964,452)

Array required: \[1000,964452152\] = 964,452,152,000 bytes

Even using a bit array, (given I'm estimating the algorithm requirements properly), it will require 112 GB of memory... (964,452,152,000/8 = 120,556,519,000 bytes)

Is there other known subset sum algorithm I could evaluate?

**Edit 1: (after Tom reply)**

I didn't clarify this in the question:

* It must be an exact algorithm (not approximate solutions)
* Should be able to output the subset solving s

# Answer
> 2 votes
You can implement the dynamic programming algorithm using a much smaller amount of memory. You don't need the entire table in memory all the time.

The point is that to answer the question "Is there a set of items $1,\ldots,i$ that sums to $s$?", you only need the answers for $i-1$ (the previous "row" in the DP table), but you don't care about the (previously computed) answers for $i-2,i-3,\ldots$. Thus, at any given time, you'd only need an two arrays of around 120MB each in memory (and in fact, you can do it using only one array!).

However, reconstructing the solution becomes more difficult, since traditionally you'd reconstruct the solution by backtracking through all of the stored values. There's a nice workaround: with each (feasible) subproblem, store how much of the weight is taken up by the first $n/2$ elements.

We can do this computation in time $O(ns)$ (where $s$ is the sum of all elements). From the final row of the dynamic programming table, we can now find not only whether the problem has a solution at all, but also (if a solution exists), what portion of the target sum is achieved by the first $n/2$ elements (and consequently, we also know what portion of the sum the remaining elements make up). We can now solve the two subproblems recursively, each of half size. The total time taken is only $O(ns \log n)$, i.e., we only take a factor $O(\log n)$ hit in the running time for a linear reduction in memory usage.

You should also consider the possibility that perhaps not all possible values can be attained as sum of items in your set. So, depending on the input, perhaps not using a contiguous array of bits, but using instead for example a hash table will use less memory.

Finally (as an alternative solution), if you only need an approximation, consider rounding the values (e.g. to the nearest thousand) to reduce the size of the tables further.

---
Tags: algorithms, time-complexity, np-complete, space-complexity
---


# Question
Title: Are there any algorithms or data structures that need to find the median value of a set?
I have been reading this book for my class, Randomized Algorithms. In this particular book, there is a whole section dedicated to finding the median of an array using random selection, that leads to a more efficient algorithm. Now, I wanted to know if there are any practical applications of this algorithm, in the domain of computer science, besides a theoretical improvement. Are there any algorithms or data structures that need to find the median of an array?

# Answer
> 17 votes
> if there are any practical applications of this algorithm in the domain of computer science besides being a theoretical improvement

The application of this algorithm is trivial - you use it whenever you want to compute a median of a set of data (array in other words). This data may come from different domains: astronomical observations, social science, biological data, etc.

However, it is worth mentioning when to prefer median to mean (or mode). Basically, in descriptive statistics, when our data is perfectly normal distributed then mean, mode, and median are equal, i.e. they coincide. On the other hand, when our data is skewed, i.e. the frequency distribution for our data is (left/right) skewed, the mean fails to provide the best central location because the skewness is dragging it away from the typical value to left or right, while the median is not as strongly influenced by the skewed data, and thus best retains this position pointing to a typical value. Thus computing a median might be preferable when you deal with skewed data.

Also, machine learning is where statistical methods are heavily used, for example $k$-medians clustering.

# Answer
> 13 votes
**Median filtering** is common in reduction of certain types of noise in image processing. Especially salt and pepper noise. It works by picking out the median value in each color channel in each local neighbourhood of the image and replacing it with it. How large these neighbourhoods are can vary. Popular filter sizes (neighbourhoods) are for example 3x3 and 5x5 pixels.

# Answer
> 10 votes
Computing medians is particularly important in randomized algorithms.

Quite often, we have an approximation algorithm that, with probability at least $\tfrac34$, gives an answer within a factor of $1\pm\epsilon$ of the true answer $A$. Of course, in reality, we want to get an almost-correct answer with much higher probability than $\tfrac34$. So we repeat the algorithm $k$ times and then take the median. The median will be within $A(1\pm\epsilon)$ unless at least half of the $k$ samples were less than $A(1-\epsilon)$ or at least half were bigger than $A(1+\epsilon)$, and this has probability exponentially small in $k$.

Computing medians takes our crappy "It's wrong one time in four" algorithm and turns it into an "It's wrong once in $2^n$ runs" algorithm while only adding a factor of something like $n$ to the running time.

# Answer
> 5 votes
The median of medians has some applications:

* Finding a pivot for quicksort, which brings its worst-time complexity to $ O(n \log n)$.
* Finding a pivot for quickselect, bringing it's worst-time complexity to $O(n)$, from $O(n^2)$.

---
Tags: runtime-analysis, randomized-algorithms
---


# Question
Title: What is an example of set $A$, that is decidable if $AA$, but which is not decidable if it is $A$ alone
I encountered a question to give an example of a set $A$ that is not decidable as $A$, but which becomes decidable if it is concatenated with itself, i.e. $AA$.

In case a set $A$ is decidable, then it is easy to see that $AA$ is also decidable, since a $TM$ that decides $A$ can be modified to also recognize $AA$... But I am having a hard time to look for examples given its converse.

# Answer
You can pick your favourite undecidable language $L$ and build $A$ in this way:

$A = \\{ 1 \\} \cup \\{ 2n \\} \cup \\{ 2n + 1 \mid n \in L \\}$

$A$ contains $1$ and all even numbers, but it also contains ... (I let you try to complete the proof)

Note that I assume that $AA = \\{ xy \mid x, y \in A\\}$; because if you define $AA=\\{ xx\mid x \in A\\}$ then it doesn't exist an undecidable language $A$ such that $AA$ is decidable (again I let you try to prove it :-).
> 3 votes

---
Tags: complexity-theory, turing-machines, undecidability
---


# Question
Title: Recursion Theorem : why does $SELF$ need $A$ and $B$ parts?
I read in Sipser's book that a machine can make copies of itself using a special function $q(w)$ which takes a string $w$ as input and prints out the string $w$.

A $TM$ $SELF$ can print out its own description $AB$ using two parts. For the first part $A$ prints out $\<B\>$ since it has the description for $B$ inside its finite control. For the second part, $B$ looks at the tape for its own description $\<B\>$, and uses $q$ to come up with $\<A\>$. Both descriptions are then concatenated to come up with $\<AB\>$.

I understand the proof above, but I couldn't get it yet why $SELF$ should have two parts. If its own description is writtten in its finite control, couldn't it just use $q$ to print out its own descrition?

# Answer
> 3 votes
No, it can't.

Intuitively, $A$ can be described by `print "B"`. Whatever $B$ is, there is such an $A$. Note that, by construction, $A$ is a program "longer" (roughly speaking) than $B$.

If we try to write $A$ as `print "A"`, we incur in a problem, since $A$ should be "longer" than itself. Hence, such a definition is ill-posed.

For the same reason, you can't write a description of a TM inside its own finite control: you would need an infinite amount of states for that.

---

You can search the web for "quines": programs printing their own source code. Virtually all of them have to workaround the fact that they can't include their own source code in themselves, and have finite length. Hence, they must exploit something analogous to the $q()$ function you mention.

A typical quine can be designed as follows. Start from a clumsy attempt:

```
myself=""
print myself

```

Obvious partial fix: copy its source code within `myself`

```
myself="myself=\"\" \n print myself "
print myself

```

Not yet there: we should replicate the source code inside the innermost quotes, and so on, infinitely many times. Not good.

Instead, we use a placeholder for that "infinite" replication, which we replace *at runtime* with the whole code.

```
myself="myself=\"PH\" \n print myself "
print replace(myself, "PH", myself)

```

Obvious fix

```
myself="myself=\"PH\" \n print replace(myself, \"PH\", myself)"
print replace(myself, "PH", myself)

```

Assuming that `replace` only replaces the first occurrence of the placeholder `PH`, and that we fix the whitespace precisely in `myself`, this is now a program printing itself -- a quine.

Note how the replacement of `PH` must be done at runtime. Similarly, in the Sipser proof, we must compute `q()` at runtime -- we can't encode that in the finite control.

---
Tags: complexity-theory, computability, turing-machines
---


# Question
Title: Getting output of dynamic programming, (contiguous sub array, box stacking)
I am attempting to output the largest stack of boxes given an input of a set of boxes. Currently I have an array called maxWeight that has the values of the boxes sorted from largest to smallest, this is the array being operated and changed, I then have another array that also has the values of the boxes going from largest to smallest.

```
 for(int i = 1; i < array.length; i++) {
     for(int k = 0; k < i; k++) {
          if(array[i].canStackOn(array[k])
             && maxWeight[i] < maxWeight[k] + temp[i].weight()) {
              maxWeight[i] = maxWeight[k] + array[i].weight();
              }
          }

  }

```

I am absolutely beating my brains out trying to find a way to keep track of each of the items added to the location of the largest sum on the array. Could anyone be so kind as giving pointers to a solution?

# Answer
You are computing inductively an array maxWeight. The value of maxWeight at a certain point $i$ is the maximum over several possibilities. Currently you are remembering only the maximum itself. If you also store which possibility was maximum, then you will be able to use this additional information in order to construct an optimal solution.
> 1 votes

---
Tags: dynamic-programming, knapsack-problems
---


# Question
Title: Is there a universal identity or zero value for folding?
I'm using Haskell notation for illustration, hopefully it is known widely enough for this to make sense.

In the following fold function the second argument is what I'm calling the identity:

```
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

```

It is trivial to fold/reduce over a list of values with certain operations such as addition or multiplication. e.g.

```
mySum :: (Num a, Foldable t) => t a -> a
mySum = foldr (+) 0   --NB. Works because 0 is the additive identity

myProduct :: (Num a, Foldable t) => t a -> a
myProduct = foldr (*) 1  --NB. Works because 1 is the multiplicative identity

```

But not all operations have an obvious identity value.

My question is whether there is such thing as a universal identity value, or a function whereby you can find the identity value, or if you can contrive a scheme so that there now is one.

i.e. can you somehow define a z value such that:

```
foldrUniversal :: Foldable t => (a -> b -> b) -> t a -> b
foldrUniversal f = foldr f z

```

or could you have a function that determines it:

```
findIdentity :: (a -> b -> b) -> z  --is this possible?

foldrUniversal f = foldr f (findIdentity f)

```

or can you use some trick so that you always have an identity value even if you don't know what it should be?

(Note that I'm not stuck on a programming problem. I already know about foldr1 in Haskell, or using the head of the list as the identity and then the tail of the list as the list argument. I posted in cs.stackexchange instead of StackOverflow because I'm interested in the theoretical possibilities.)

# Answer
There's no universal identity for folding. It it in fact visible from your examples with `+` and `*`: how could you infer that `+` needs `0` but `*` needs `1`? In order to find this out, it is necessary to analyze `+` and `*` sufficiently to find how they differ. If the compiler has some knowledge of `+` and `*`, this might be doable. But if you generalize the example to any primitive function, or any function defined in Haskell but which the compiler isn't able to analyze, then the compiler won't be able to tell the difference between `+` and `*`, so there's no way it could come to different conclusions regarding the identity.

Another way to see that there's no universal identity is that sometimes, there is no identity. For example, if you had a type of positive integers (integers $\gt 0$) and the operation `+`, then there would be no identity. Another example that's perhaps more intuitive for a programmer: for string concatenation, the identity is the empty string `""`. But if you define an operation that concatenates with an explicit separator (e.g. `cat x y = x + "," ++ y`), that one has no identity.

It is possible however to *force* a universal identity, i.e. to pull an object out of thin air and declare that it will be an identity. (This use of the word *force* comes from mathematics.) The way to do this is to add a level of indirection — as every programmer knows, you can solve¹ any problem by adding a level of indirection. Instead of folding over values of the original type, you fold over a value that is either a value of the original type, or the identity. In other words, an option.

```
fold_with_identity :: Foldable t => (a -> b -> b) -> t a -> Maybe b
fold_with_identity f xf = fold_list (toList xf) where
                            fold_list [] = Nothing
                            fold_list x0:xs = Just (foldr f x0 xs)

```

There's no such thing as a free lunch, so obviously this doesn't actually solve the problem — it just moves it to the next level. You may get `Nothing` out of this and you have to know which value to convert it, if there's a value to convert it to.

¹ <sub> almost. Offer void where prohibited by law or by the type system. One per customer if using linear logic. Consult a PhD if the symptoms persist. </sub>
> 3 votes

# Answer
Assume we can define

```
foldrUniversal :: Foldable t => (a -> b -> b) -> t a -> b

```

Then,

```
foo :: b
foo = foldrUniversal (\x y -> y) []

```

Is a way to form a value for **any** type `b`. If the type system is sane, this implies that `foo` does not terminate, as if we recursively defined `foo = foo`. Otherwise, all the types would be inhabited, making the logic associated to the type system to be inconsistent. A type system that allows this would be regarded as essentially "broken".

In real world languages, we do (grudgingly) allow some unwanted inhabitants. Non-terminating values ("bottom") are common ones, since they are mandatory in language with unconstrained recursion. `null` values are also used in many OOP based languages -- this is a so-called "billion dollar mistake", and should be avoided. Having a way to craft a "real" value of type `b` (say non-null, non-bottom) from nothing is too much.
> 5 votes

---
Tags: functional-programming
---


# Question
Title: Does a bitonic sorter compare a pair of elements more than once?
I've got two questions about bitonic sorting:

1. Does a bitonic sorter compare a pair of elements more than once?
2. How many comparisons does a bitonic sorter perform in the case where the size of the array not a power of two.

# Answer
> 1 votes
1) yes, the exact same comparison is made, interleaved with other operations. The butterfly network creates tones and checks local and far pairs, after far pairs it still has to apply local ones.

2) The original bitonic sort by Batcher requires the sequence that is a power of two. It makes tones in bitonic sort phase and then bitonic merge phase. The given algorithm introduced dummy nodes (infinite value or maximum that can be stored) for inputs $2^k - c$ and after sorting strips them from result. So the original network uses the number of comparisons equal to the net sorting the next power of two input size. The modifications that use less comparisons are not successful because of environment they run in. While it is possible to avoid not needed comparisons, it introduces branching at higher level (or special blocks, since it is no longer symmetric), to choose what comparator should be used and (in my opinion) is not any more bitonic sort.

You might be interested in more general sorting networks, where the exact number of compares is the subject of creating the sorting net for given $n$. The structure and algorithm depends on number of comparators available. The net is created for exactly given size, and it is not required to be power of two or be even. The optimal networks are found for $n \le 10$.

I recommend Optimal sorting networks by *Daniel Bundala and Jakub Závodný* about pursuit of better networks (these are general, not bitonic) with algorithmic approach.

---
Tags: sorting
---


# Question
Title: Comparing A* search to Simulated Annealing
Good Afternoon,

I am comparing A\* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my answer, and was wondering if someone could give me some input.

A\*: Optimal, finds path of shortest distance to goal state based on heuristic.

SA: Complete, stochastic, randomly selects next state and either rejects/accepts based on change in energy state. If it is a bad move (less energy than previous state) then it either accepts/rejects based on probability.

Now, I understand that A\* requires bookkeeping in order to track the path from goal state to start state. This is why I think that the memory requirements would be linear, where there are n nodes in the path from start to finish.

On the other hand SA doesn't require bookkeeping, since it's trying to find the state with the maximum "energy". Could someone explain exactly what "energy" would mean? Also, I am confused about comparing the functions of these two algorithms. A\* is good at finding the path to a goal state (which is already known) with the lowest cost, whereas SA only finds a state that is most desirable. what is the point of comparing A\* to SA when they seem to have two different purposes?

# Answer
"Energy" is just the output of your cost function that you define for the SA problem. You are right that the two algorithms seem to have two different purposes, and in most cases, I would say that is true. However, you could pose a pathfinding problem as a simulated annealing problem, depending on how you define your cost (energy) function.

Let's say you have a cost function that equals the total cost to get from point A to point B. Your SA algorithm would try to find the minimum in this cost function, but imagine how difficult that may be. Your cost surface could potentially by many-dimensional. Plus, there is no guarantee that your cost surface is smooth, so finding that minimum on this enormous cost surface may be computationally intractable.

I think you've stated well many of the differences, but the next step is to try to understand the benefits/drawbacks of each algorithm solving the problem they are best suited for.
> 2 votes

---
Tags: algorithms, randomized-algorithms, heuristics, searching
---


# Question
Title: Relation between Hoare Type Theory and pointers
My understanding is that in Hoare Type Theory every imperative statement has a type of the form `{Pre}res:T{Post}` where `T` is the type of the result of the computation and `Pre` and `Post` are propositions representing respectively the pre and postconditions of the statement and `res` is the result of type `T` which can appear in the postcondition.

Given the following program in pseudo-C:

```
int i=0;
int*p=&i;
*p=1
return i;

```

How can Hoare type theory represent the the fact that `i` must be 1?After all,it's not clear `i` is modified in the above snippet,and it can be hidden even from the programmer if we begin to add lambdas and partial application

# Answer
> 8 votes
A pointer to a variable creates an alias. When the alias is modified, the corresponding variable is modified as well. Therefore, the rule for an assignment in Hoare's logic is not just *update the value*, but *update the value for all associated aliases*. Let's apply it to the example:

```
{True}        int i=0;  {i = 0}
{i = 0}       int*p=&i; {i = 0; [*p, i]}  /* *p and i are now aliases */
                                          /* The postcondition can be written as: */
                        {[*p, i] = 0}     /* In particular, *p = 0 */
{[*p, i] = 0} *p=1;     {[*p, i] = 1}     /* In particular, i = 1 */
{[*p, i] = 1} return i; {i = 1}

```

The general rules to reason about programs with pointers are given by *Separation logic*. The information whether two expressions reference the same memory location is obtained by *pointer analysis* and *alias analysis*.

---
Tags: type-theory, dependent-types, hoare-logic
---


# Question
Title: How many possible policies in a Markov Decision Process?
If a policy yields an action for a state, how come a 3-state MDP with 2 possible actions, i.e. $S = \\{Hot, Mild, Cold\\}$, $A = \\{East, West\\}$, has **8** possible policies? Isn't it 6 if there are 2 possible action for every state?

# Answer
Looks like you are a bit confused by the notion of *MDP policy*. There's a detailed discussion with lots of examples in this question.

A policy is any possible strategy in a given environment. Example: "go $East$ in any state" is a valid strategy in your MDP (though maybe not optimal), as well as "go $West$ in any state".

So there are 3 states and 2 possible actions per each, hence $|A|^{|S|} = 2^3 = 8$ possible strategies: $EEE$, $EEW$, ..., $WWW$.
> 4 votes

---
Tags: machine-learning, artificial-intelligence, decision-problem, markov-chains
---


# Question
Title: Non-deterministic TM and problems in class P
Definition: $\text{P}$ is the set of languages that can be decided by a deterministic Turing Machine in polynomial time.

I wonder if $\text{P}$ equals to the set of languages that can be decided by a non-deterministic Turing Machine in polynomial time?

I think this has to be true because a non-deterministic Turing Machine can also decide all problems which can be decided by a deterministic Turing Machine. Because of the fact that we have here a language in P this NTM also decides it in P.

Am I right or am I wrong?

# Answer
> 2 votes
> I wonder if $\text{P}$ is the set of languages that can be decided by a non-deterministic Turing machine in polynomial time?

This is the same as asking whether $ \text{P} = \text{NP}$, where $\text{NP}$ is the set of languages that can be decided by nondeterminsitic Turing machines in polynomial time. The question of whether $\text{P} =\text{NP}$ is an open problem. So we don't know the answer yet.

> I think this has to be true because a non-deterministic Turing Machine can also decide all problems which can be decided by a deterministic Turing Machine.

The fact that nondeterministic Turing machines can simulate deterministic Turing machines without any time blowup (simply by not using nondeterminisim) is straight-forward and only shows that $\text{P} \subseteq \text{NP}$, the mysterious open containment is the other one: we don't know yet whether deterministic Turing machines can simulate nondeterministic Turing machines with at most polynomial blow-up.

# Answer
> 1 votes
The class $P$ is a subset of $NP$. For an $NP$ algorithm to simulate $P$ in polynomial time, it does not even need to use nondeterminism, since a single branch can solve the $P$ problem.

It could be a bit confusing though when textbooks say that an $NP$ algorithm works in 'polynomial time'. But this refers to the amount of time it takes for a single branch to compute. But taken as a whole, $NP= \cup NTIME(n^k)$, while $P= \cup DTIME(n^k)$.

# Answer
> 0 votes
Every problem of class `P` is also of class `NP`. `NP` means we can verify a solution to a problem in polynomial time. If a problem is in the `P` class, one method of verifying the solution would be to find the solution in polynomial time. Thus, the `P` problem is `NP` class.

---
Tags: complexity-theory, turing-machines, polynomial-time, nondeterminism
---


# Question
Title: Checking whether at least n/2 + 1 elements of a set/vector are equal
We have a set of elements, say a vector of $n$ elements (actually, the data structure really doesn't matter in this case). It is NOT sorted. We want to check whether at least $n/2 + 1$ elements are equal.

I have been thinking about an efficient algorithm to do so but I don't know, the fact that it is not sorted makes it quite difficult for me.

If it was sorted, we could do it with an $O(n)$ algorithm, I'd say: just iterate over the vector, saving the most common element. If the counter arrives to $n/2 + 1$, we are done.

Could you give me some advice? Thank you very much.

# Answer
I think there is an even better approach to your problem:

1. The element you are looking for will also be the median of the list. Find the median of the list using the Median of Medians algorithm. **$O(n)$ complexity**
2. Check if the median appears at least $n/2 + 1$ times on the list **$O(n)$ complexity**

So, the algorithm you're looking for runs in linear time.
> 1 votes

---
Tags: algorithms, data-structures
---


# Question
Title: The origin and the meaning of "Abstract Syntax Tree"
This question is closely related to *Does an abstract syntax tree have to be a tree?* and is partially answered there, but I would like to be more precise and to have more concise answers.

1. What is the origin of the term?
2. Are there any formal definitions of AST?
3. If I understand correctly the spirit of the use of "AST" term, it is a misnomer: an AST is any combinatorial object or datum that one tries to represent by strings of characters using more or less simple syntax that should ideally reflect the internal structure of the object/datum. For example, in first-order logic and in lambda calculus, expressions like $(\forall x)(x = x)$ or $(\lambda x.x)$ do not really represent trees because bound variables introduce loops. Do I understand correctly?

Basically, I broke up here in simpler pieces a single question: *What is AST?* Without answering parts (1) and (2) the answer will probably be incomplete or hard to verify, and if (1) and (2) are answered, an answer to (3) probably should follow.

---

*Update*

I have realized that it is not the "syntax tree" that is abstract, but the syntax. This clarifies the terminology to me and makes this question less relevant. Basically, I parsed "abstract syntax tree" incorrectly.

I also provided an answer to the related question.

# Answer
> 1 votes
You are asking three questions. I will answer one.

I don't think "abstract syntax tree" is a misnomer. It aims to represent the *syntax* of the expression. It is not claimed to represent all of the meaning (semantics) of the expression. The issue with bound variables that you mention relates to semantics rather than syntax.

Also, remember that names are merely that: references to some concept, to serve as an aid to communication. Sometimes the concept is subtle or nuanced enough that no name is going to fully represent all the complexities of the concept, so we choose the best name we can (while keeping it fairly short). And a name is just an aid to communication, so not all concepts have a fully precise, rigorous definition -- if it is used in a way that aids understanding and facilitates communication, that is often OK.

---
Tags: terminology, reference-request, compilers, history, syntax-trees
---


# Question
Title: Operations under which the class of undecidable languages isn't closed
Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable languages are not closed under these operations?

What can we say about the kleene closure? Do we have examples for it too? I.e. can the closure of an undecidable language be decidable?

Also, can we generalize such undecidable classes?

# Answer
Yes, let $H$ be binary encoding of the halting problem and $A=0H\cup 1\\{0,1\\}^{\ast}\cup\\{\epsilon\\}$, $B=1H\cup0\\{0,1\\}^{\ast}\cup \\{\epsilon\\}$, then $AB=\\{0,1\\}^{\ast}$ (why?)
> 21 votes

# Answer
We know that the halting language is undecidable. Let H be its binary encoding. We can also state that complement of H is undecidable. Therefore, union/intersection of H and HComp are $\Sigma^\*$ and $\phi$, which are decidable.
> 9 votes

# Answer
Same holds for the Kleene star (Kleene closure):

set $\text{HP}' = \text{HP} \cup \\{0,1\\}$ with $HP$ being the halting problem. $\text{HP}'$ is clearly undecidable, and $(\text{HP}')^\* = \Sigma^\*$, which is regular (thus decidable).
> 9 votes

# Answer
Ran showed that undecidable languages are not closed under the Kleen star operation; but they aren't closed under a simple "self" concatenation ($L \cdot L = L^2 = \\{ xy \mid x,y\in L \\}$) either; for example:

$L = \\{1\\} \cup \\{2n\\} \cup \\{ 2n+1 \mid n \in Halt \\}$

$L$ is undecidable, but $L^2$ is decidable.
> 1 votes

---
Tags: formal-languages, undecidability, closure-properties
---


# Question
Title: What is the time complexity of finding the residual network in this case?
Here are the details:

**(1)** We are given a number $f$ of units of flow that we wish to transmit from the source node to the sink node. For example, $f=5$ units of flow (data or goods) should be transmitted from the source node to the sink node.

**(2)** We are not given any plan or policy to transmit the flow. However, we know that $f$ is less than the maximum flow of the network. So, it is possible to transmit such an amount of flow through the network.

**(3)** We are given the arcs' capacities.

$\bullet$ Now, it is required to determine the residual network after sending these $f$ units of flow.

Very simple:

**Input:** A network with the given arcs' capacities and an amount of flow $f$. Also, two nodes are specified as source and sink nodes.

**Output:** A plan to transmit $f$ units of flow from the source node to the sink node, and the corresponding residual network.

It is clear that there may be more than one plan to send $f$ units of flow through the network, and so the residual network may change. It is not important to reach a special residual network. My main concern is only to find the time complexity of such a job (finding a way to transmit $f$ units of flow through the network, and then determining the residual network).

It is easy to see that if I have the plan to send $f$ units of flow, the residual network can be determined with time complexity of $O(m)$, where $m$ is the number of edges in the network.

**$\bullet$** I highly appreciate any help in advance.

# Answer
> 0 votes
The time complexity of this problem is (at most) the time complexity of the network flow problem. You are given a graph and you want to find a flow of size $f$. You can use any network flow algorithm for this. Different algorithms have different running time. Wikipedia has a list of algorithms, with their running times. There is not a single optimal algorithm; different algorithms work better in different situations.

You mentioned you want to find a flow of size at least $f$, rather than a max flow. Many of the algorithms for max flow can be adjusted to stop early when you've found a flow that is large enough. Or, you can adjust the graph to ensure that a flow of size $f$ *is* a max flow -- if the original source vertex is $s$, add a new vertex $s\_0$ and an edge $s\_0 \to s$ of capacity $f$, then treat $s\_0$ as the new source vertex and solve the max flow problem.

Once you find the flow itself, you can compute the residual network in $O(m)$ time. For each edge, you compute how much remaining capacity it has (the capacity of that edge minus the amount sent by the flow); and you add a reverse edge if necessary (the amount of the flow). This is $O(1)$ work per edge. All known network flow algorithms take $\Omega(m)$ time. Therefore, the time to compute the residual network once you find the flow is negligible; the bottleneck is finding the flow itself.

---
Tags: time-complexity, network-flow
---


# Question
Title: Are divide and conquer searches applicable to unimodal decision problems?
Given a sorted list of booleans with consecutive 0s followed by consecutive 1s such as \[0,0,0,0,1,1,1\], binary search is able to find the first 1 after all the 0s in log(n) time.

Is this technique generalizable to find the index to the maximum of a unimodal *boolean* list with a single 1 sandwiched between 0s such as \[0,0,0,0,0,1,0,0\]?

It seems like any search algorithm would have trouble narrowing down the search range with all the duplicate 0s surrounding a single 1, however binary search copes well with duplicates, so I'm having trouble explaining why this is impossible.

In addition, the unimodal property required by ternary / Fibonacci search is met, where an array A with indices i \< j satisfies A\[i\] \<= A\[i+1\] until maximum at A\[j\] then A\[j\] \>= A\[j+1\].

From what I've read this is possible with a list of integers, so it can't be impossible due to just discrete versus continuous functions.

What am I missing here?

# Answer
> 1 votes
No. Any algorithm for this problem requires at least $n-2$ time in the worst case. Thus, the problem requires $\Omega(n)$ time. You can't use binary search.

There's a simple adversary argument: each time the algorithm reads some index in the array, the adversary just answers 0. After the algorithm has read $n-2$ different positions in the array, there are still two possibilities for where the 1 could be, so whatever the algorithm outputs at that point is wrong for at least one input (there exists an input array that makes the algorithm wrong).

---
Tags: algorithms, binary-search, searching
---


title: Maximum depth of a B+ tree

text:
# Question
Title: Maximum depth of a B+ tree
Given $K$...`# key values`, $n$...`# pointers in a node`.

I read somewhere, that the **maximum** depth is defined as $\lceil\log\_{\lceil\frac{n}{2}\rceil}(K)\rceil$. However, it is not correct, as I can come up with a counterexample. When the tree is minimum filled, it won't work. E.g.:

This is a valid $B^+$-tree, the root has at least two childs, each inner node has at least $\lceil n/2 \rceil$ childs and each leaf has at least $\lceil \frac{n-1}{2}\rceil$ record. So, $n=3$ and $K=4$, then $\log\_2(4) = 2$. Now, when you fill up the leafs: \[1,1,2,2,3,3,4,4\], then it is again a valid tree and $K=8$, hence $\log\_2(8) = 3$, but same depth.

**Notice:** I am looking for a formula or explanation but for a $B^+$-tree **not** a $B$-tree. A source would be nice.

# Answer
> 2 votes
Since you're not sure where you read it, is it possible you are misremembering slightly what the result was?

In a B+ tree, we require that every node has between $n/2$ and $n$ children. In other words, every node is required to have at least $\lceil n/2 \rceil$ children. This means that any tree of depth $d$ where all leaves are at depth $d$ must have at least $\lceil n/2 \rceil^d$ leaf nodes. Thus, any such tree must have depth at most $\lceil \log\_{\lceil n/2 \rceil} L \rceil$, where $L$ is the number of leaf nodes. Perhaps this is what you read.

Note that the number of key value is related to the number of leaf nodes: $\lceil b/2 \rceil -1 \le L/K \le b-1$. This would let you get a similar result in terms of $K$, for a full tree with all leaves at the same level.

Detail: Here I have ignored that the root is usually allowed to have as few as 2 children. This has only a small effect on the answer.

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


# Question
Title: What kind of growth is $O(0.24\cdot K\cdot 2^w)$
I've calculated the running time of an algorithm I'm interested in to be

$$O(0.24\cdot K\cdot 2^{w})\\,,$$

where $K$ and $w$ are both variables. ($K$ is the number of elements in some set, and $w$ is the log of the largest element, so both are variables.)

What kind of growth does this function have? I'll say it is exponential, however I don't know what the 0.24 implies.

# Answer
> 2 votes
If $K$ is constant and $w$ is variable then $0.24\times K\times 2^w$ and the function is exponential in $w$, therefore it is $O(2^w)$.

If $K$ is variable and $w$ is constant then $0.24\times K\times 2^w$ is $O(K)$ - linear in $K$.

If both $K$ and $w$ are variables then $0.24\times K\times 2^w$ is $O(K2^w)$.

If both $K$ and $w$ are constant then $0.24\times K\times 2^w$ is $O(1)$.

The constant $0.24$ is ignored since it becomes irrelevant when we compare the rate of growth of a function. For more details please see Big-O notation.

We also use $O^\*(f(n))$ notation, in particular in analysis of parametrized algorithms, which means that the algorithm runs in $O(f(n)p(k))$ for some polynomial $p(k)$. So you could also write it is $O^\*(2^w)$ in case $w$ is variable.

# Answer
> 2 votes
The function $f(K,w) = K\cdot 2^w$ has polynomial (in fact, linear) dependence on $K$ and exponential dependence on $w$.

You're interested in the function $g(K,w) = 0.24\cdot f(K,w)$ but the constant multiplier doesn't change anything. Linear growth in $K$ means that, if $K$ doubles, then $f(K,w)$ doubles, too. But doubling $K$ also doubles $g(K,w)$. Exponential growth (with base $2$) means that adding $1$ to $w$ doubles $f(K,w)$, and the same applies to $g$.

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


title: Pseudo-random role assignment

text:
# Question
Title: Pseudo-random role assignment
I have a number of players, ranging from `[0..N]`. Each round every player is assigned a specific role, either 1, 2 or 3. `floor(N / 8)` role 3's are assigned, `floor(N / 4)` role 2's are assigned and the rest are assigned role 1's.

At the moment, I pick people completely at random for roles 3 and 2, however, this has the issue that some people can go many, many rounds without getting a specific round. Although the algorithm is "random", people may still get annoyed at how it seemingly isn't.

I was wondering if anyone knew of a better algorithm which still assigns roles semi-randomly but tries to reduce the chance of someone not getting a role for too long (or, the converse, where it tries to ensure a role is not chosen too often)?

# Answer
> 1 votes
I suspect the biggest problem is going to be the gap between role 3's. So, one possible approach would be to schedule 8 rounds at a time, and for each block of 8 rounds, make sure that every player gets assigned role 3 exactly once.

This can be done as follows. For the first round, randomly pick N/8 people to be role 3 in the first round. Then, randomly pick N/8 people who haven't been picked yet to be role 3 in the second round. Continue until you have scheduled all of the role 3's for all 8 rounds. This will ensure that each player is role 3 exactly once in those 8 rounds; and that in each round, exactly N/8 people have role 3.

You could then complete the schedule by randomly scheduling role 2's and role 1's among the remaining people (with the right probabilities). This would be pretty simple to implement and might be good enough.

---

What if people start complaining about the role 2's? Well, you could schedule them nearly-equally, too, with a modest modification. As before, schedule 8 rounds at a time. We'll try to ensure each player is assigned role 3 exactly once in those 8 rounds; and that most players are assigned role 2 twice, once in the first 4 rounds and once in the last 4 rounds (but we won't be completely perfect about that). We'll start by assigning the role 3's as described above and fix their assignment.

Next, we'll assign role 2's to the first 4 rounds. In the first round, randomly pick a subset of N/4 people who don't have any assignment in that round, and assign them role 2. In the second round, out of the people who don't have any assignment in that round and who haven't been assigned role 2 yet, randomly pick a subset of N/8 of them and assign them role 2. Continue. In each round, we find the set of people who don't have a role assigned to them in that round yet and who haven't been assigned role 2 yet, and randomly pick a subset of size N/4 from that set; everyone in that subset is assigned role 2. In rounds 1-3, it is nearly guaranteed that this set is larger than N/4, so we can pick a subset of the appropriate size. In round 4, this set might be smaller than N/4; if so, assign everyone in that set role 2, and then randomly pick other people who don't have an assignment in that round to be role 2 until you have N/4 role 2a's in that round. In this way, most people are assigned role 2 exactly once in the 4 rounds, with a few people who get assigned role 2 zero or two times (due to round 4 being imperfect).

Then, do the same for role 2 in rounds 5-8.

---
Tags: algorithms, randomized-algorithms
---


# Question
Title: What language can be created from a regular expression with nulls?
The usual regular expressions I have seen are those with non-null inputs (e.g. $a$, $b$). A few days ago, I saw, for the first time, a regular expression that has a null ($∅$) in it.

$$ r\_{1}= (cε + d∅)^{\*}, Σ = \\{c,d\\} $$

This confused me since I do not know how a language would be created from $r\_{1}$.

What would a language created from a regular expression be like if that regular expression has a null (like $r\_{1}$ above)?

Additionally, what would a language be like if the regular expression from which the language is created from contains $ε$ (for example, like $r\_{2}=(aε)(bε)ε, Σ = \\{a, b\\}$, and again, like $r\_{1}$ above)?

# Answer
The regular expression $\emptyset$ matches nothing at all: not the empty string, not any non-empty string.

Any concatenation with $\emptyset$ also matches nothing: a string would only match $d\emptyset$ if it could be divided into some part that matches $d$ and some part that matches $\emptyset$, but no such part exists. So $d\emptyset$ is the same thing as $\emptyset$: it matches nothing at all.

An alternation ("or") of something with $\emptyset$ has no effect: $c\epsilon+\emptyset$ means "anything that matches $c\epsilon$ or matches $\emptyset$" and that's just "anything that matches $c\epsilon$."

So $c\epsilon+d\emptyset$ is the same thing as $c\epsilon$ which, in turn, is the same thing as $c$. The regular expression you quote is equivalent to the simple $c^\*$.

---

Conceptually, $\emptyset$ plays a similar role to zero in addition and multiplication. Adding zero to anything doesn't change it, just as alternation of a regular expression with $\emptyset$ doesn't change it. Multiplying anything by zero makes it equal to zero, just as concatenation of any regular expression with $\emptyset$ turns it into $\emptyset$.

$\emptyset$ might seem rather pointless as a regular expression. It's needed because, without it, the empty language (the one with no strings at all in it, i.e., the set $\emptyset$) wouldn't be regular. To see this, it's not hard to prove by induction that every regular expression that doesn't contain the character $\emptyset$ must match at least one string. However, we want the empty language to be regular, because it's accepted by an automaton – in fact, by any automaton with no accepting states.
> 4 votes

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


# Question
Title: Name for tree where each node has the aggregate of its children
Is there a general name for a tree in which the leaves have some arbitrary values and the value of every other node is some "aggregate" function of its children?

An example where the aggregate function is the sum:

```
  14
 /  \
4   10
   / | \
  7  1  2

```

The function could also be the min, max, or any other function of the form $f:S^n\to S$.

# Answer
Such tree is called *Sum Tree* or *SumTree*, where the property is maintained in bottom up fashion. In general if the value is additional value (node property) for some existing one like AVL it is *Sum augmented AVL Tree*.

If the property is inherent, like maintaining the prefix sum, it would be *Fenwick Tree*.

As far as I know there is no established name, but for other functions it is *partial statistics tree*. preferable name would be *Tree augmented with $f$*, to make it explicit.
> 2 votes

---
Tags: data-structures, terminology, trees
---