# Question
Title: Divide sequence of numbers from 1 to n into 2 groups with minimum difference
Let's say for some $n$ we have the sequence $1, 2, 3, \dots , n$, what we want with this sequence is to divide it in two sets such that each element of the sequence will be in only one set, and the difference in sums of the two sets will be minimum possible.

**Example**

Let $n = 4$, and $A$ and $B$ are our sets, we can divide the numbers in this set such that the difference in sum between them will be $0$, $A = \\{1, 4\\}$ and $B = \\{2,3\\}$

**My thinking**

I noticed we can divide like this $1$ and $n$ in set $A$, then $2$ and $n-1$ in set $B$, then $3$ and $n-2$ in $A$, etc..

My algorithm gives correct result if $n$ is divisible $4$, but when it is not divisible by $4$ it will return that the difference between the sets is bigger than it actually is, how can we divide the numbers optimally.

# Answer
It turns out that the strategy depends on $n$ mod $4$.

To see why, one computes the total sum of all these numbers, which is $n(n+1)/2$. The parity of this sum depends on $n$ mod $4$: if $n$ is congruent to $0$ or $3$ mod $4$, the total sum is even; otherwise the total sum is odd.

When the total sum is odd, it is not possible to divide the set into two parts with equal sums. The minimum difference you can expect is therefore $1$.

---

If $n = 0$ mod $4$: you already figured out how to do that.

If $n = 1$ mod $4$: divide $2, \cdots, n$ using your strategy, and add the extra $1$ to any side. This achieves the minimum difference $1$.

If $n = 2$ mod $4$: divide $3, \cdots, n$ using your strategy, and add the extra $1$ and $2$ to each side to get the minimum difference $1$.

If $n = 3$ mod $4$: divide $4, \cdots, n$ using your strategy, and add $1$ and $2$ to one side, and $3$ to the other side to get the minimum difference $0$.
> 2 votes

---
Tags: discrete-mathematics
---


# Question
Title: Maximum value of LOOP-Program turing-computable
Lets consider the class of "simple" LOOP-Programs.

A LOOP-Program P is inducively defined as:

$P\_1: x\_i = x\_j$ and $P\_2:x\_i = x\_i +1$ are LOOP-Programs. We also define a length property $l(P)$ where $l(P\_1) = l(P\_2) = 1$

P: $P\_1;P\_2$ is also LOOP. (sequential execution of statements). The length of these programs is $l(P) = l(P\_1)+l(P\_2)$

P: $LOOP\ \ x\_I \ \ DO \ \ P\_1 \ \ END $ (execute P a fixed amount of times, this program will execute P exactly $x\_i$ times.) The length of this program is $l(P) = l(P\_1)+1 $

The input of a LOOP-Program is passed as as $f(n\_1 \cdots n\_k) \rightarrow x\_1 \cdots x\_k$ and the output is alsways stored in $x\_0$

Lets further consider $S(n)$ the function which computes the maximum value of a simple LOOP-Program of maximum length $n$ with input $n$.

It is known that $S(n)$ is not LOOP-computable. ( can write proof if needed)

The question stands wether $S(n)$ is Turing-computable.

First we can note down the following theorems:

* a LOOP-Program always halts after a finite amount of steps.
* a function is turing-computable if a Turingmachine $M$ exists which computes $S(n)$ given the input $n$ after a finite amout of steps.

My solution to the question wether $S(n)$ is turing-computable is:

We construct a TM $M$ which enumerates all LOOP-Programs of length $n$ onto the tape.:

We know this is possible because there is only a finite amount of LOOP-Programs of length $n$ using the variables $x\_1 \cdots x\_{2n}$. We will use a suitable encoding method which encodes a LOOP-Program syntactically onto the tape.

This step of the algorithm will halt after a finite amount of steps.

Then we simulate the LOOP-Programs on the tape and write the results onto the tape. This step also terminates after a finite amount of steps.

We then have the output of every single LOOP-program of length $n$ with input $n$ on the tape and we know we can find the largest value in a finite amount of steps.

Thus $S(n)$ is computable.

---

My question is: does my answer hold up and can one poke any holes in this logic ?

# Answer
My answer in the question is correct.
> 0 votes

---
Tags: computability, loops, check-my-answer
---


# Question
Title: When it is said an algorithm runs in exponential time, is it meant it has complexity $O(2^n)$, or $2^{O(n)}$?
Also, are they equivalent or are they different?

Examples of algorithms/Turing Machines that run in complexity of one but not the other would be much appreciated.

# Answer
> 4 votes
Beware the abuse of notation; I can not recommend using "$2^{O(n)}$".

That said, a common interpretation is using the placeholder semantic. That is, we read

$\qquad\displaystyle f \in 2^{O(n)} \quad"\iff"\quad \exists\\, g \in O(n).\ f \in O(2^{g(n)})$

Compare that to the definition of $O(2^n)$ and you'll quickly see that the two are not the same.

> Because $2^{cn} = (2^c)^n$, the term "$2^{O(n)}$" covers all exponentially bounded functions, i.e. the union of all $O(a^n)$; use $c = \log\_2 a$.

Your titular question should answer itself now.

> Since $3^n \not\in O(2^n)$, this Landau class does not cover all exponential function. This is easy to show independently of above discussion, by the way.

---

Note how the "definition" makes two $O$ out of one; that's why I think that notation is bad. See also this related question where is becomes clear that even experts don't agree on what the notation should mean here, exactly. Here's another related question.

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


# Question
Title: What happens when all reference bits set to 1 in Second Chance Page Replacement Algorithm?
I have a sequence like 5577334... and there are 3 frames available.

After the 6th clock, all pages (5, 7 and 3) will have their reference bits set to 1. Now, when 4 comes in, 5 will go even though its reference bit is 1 because of the FIFO rule but what happens 7 and 3' referance bits? Do they stay as 1? or Is 7's reference bit set to 0 since there is FIFO rule? or Are both 7 and 3' referance bits set to 0?

# Answer
> 1 votes
Well, I found the answer in a textbook which is saying since there is a pointer looking for a page whose reference bit is 0, it will traverse the circular queue **setting all reference bits to 0** and replacing the page who came first like FIFO.

---
Tags: algorithms, paging
---


title: Subset Sum for {1,...,n}

text:
# Question
Title: Subset Sum for {1,...,n}
In general, the subset sum problem is NP-Complete. However, what if we say that our set is $\\{1,...,n\\}$? Is there a formula/combinatorial calculation that says how many subsets of $\\{1,...,n\\}$ have their sum equal to $k$?

# Answer
This is A053632. The prefixes of this sequence convergence to the more well-known A000009, the number of partitions into distinct (or odd) parts. You shouldn't expect a clean formula, though it's of course easy to calculate small terms using dynamic programming.
> 1 votes

---
Tags: complexity-theory, time-complexity, subset-sum
---


title: RNG: removing bias by counting bits

text:
# Question
Title: RNG: removing bias by counting bits
I have a hardware RNG that sends me some random bits. Due to nature of that RNG, the source is biased. Then, the bitstream is processed in a following way to remove the bias:
two counters are used, which count amounts of 1's and 0's in the stream and when the difference is above the threshold, the next bit out ot the rng is forced to either 0 or 1.
I have concerns about this. This just means that we have directly introduced some dependency of future bits on past bits, which totally destroys randomness, right? Is this a valid concern? If yes, what are proper ways to deal with bias in RNG?

# Answer
> This just means that we have directly introduced some dependency of future bits on past bits, which totally destroys randomness, right?

Yes.

Let $T$ be the threshold of the process you describe. In a uniform (i.e. non-biased) distribution, the sequence $\mathtt{0}^{T+1}$ would have the probability $2^{-(T+1)}$, like any other sequence of length $T+1$. But the process you describe will flip the last bit, since the threshold of excess $\mathtt{0}$ bits was exceeded, and thus this sequence has the probability $0$. That's a bias. Note that this bias exists regardless of the distribution of the original generator, i.e. the process always makes the generator somewhat worse.

It's pretty apparent if you take this to an extreme. With $T=1$, the output of the process would be an alternating sequence, either $\mathtt{01010101\ldots}$ or $\mathtt{10101010\ldots}$, which is obviously hardly random at all.

This process looks like it was devised by someone who doesn't understand probability. They have a vague intuition that (9,9,9,9,9,9) doesn't look random and so they go out of their way to avoid too many repetitions. But (9,9,9,9,9,9) is not impossible, so any random generator will generate this sequence of length 6 one day, and again, and again… And it will generate (9,9,9,9,9,9,9) if you wait long enough, and (9,9,9,9,9,9,9,9), etc.

The proportion of $\mathtt{1}$ bits in the first $n$ bits should tend towards a bell curve as $n$ tends to infinity. A biased initial source deforms the curve towards one side. The process moves the summit towards the center, but cuts off the sides.

> Is this a valid concern?

Yes. Bad random generators sink ships (or save them, as the case may be). One of the ways the Allies broke messages encrypted with the German Enigma during WWII was to rely on lack of randomness because the operators' intuition of randomness led them to introducing biases.

> If yes, what are proper ways to deal with bias in RNG?

If you have a random source where each bit has a probability $p$ of being $\mathtt{0}$ and $1-p$ of being $\mathtt{1}$, then there's a rather well-known trick to turn it into a uniform source, which is due to Von Neumann. Read two bits; if they're different then output the first bit and discard the second one; if they're the same then discard both bits and try again. This works well enough with a biased coin because the bias is overwhelmingly due to the design of the coin which doesn't change between tosses. But it assumes that the bits are all independent from one another. This is not a safe assumption for a physical random generator. Even if the underlying physical process is “perfectly” random, imperfections in the construction of the apparatus often have more complex biases, e.g. due to resonance phenomena. The general name for this sort of process is whitening. Von Neumann whitening is typical good enough for physical simulations, but other usage such as cryptography needs more reliable methods.

In computer security, the practical way to construct a random generator is to use a hybrid design.

1. A random source (ultimately derived from some physical process) provides entropy. It doesn't matter that this source is biased. All that matters is that it has some minimal level of unpredictability, i.e. there is some threshold $p \gt 0$ such that the probability of any given bit being $\mathtt{0}$ is between $p$ and $1-p$.
2. The entropy is used as a seed to a cryptographically secure pseudorandom number generator (CSPRNG). A CSPRNG is deterministic, but it is infeasible for an adversary to guess any part of its output unless they know the seed. (“Infeasible” means that the adversary trying to guess an output bit gains a negligible advantage from any knowledge that doesn't imply knowledge of the key.)

The resulting distribution is not uniform (since the CSPRNG is deterministic, it can only output a finite subset of all possible sequences, limited by its state size), but it is indistinguishable from a uniform distribution by an adversary with finite processing power.
> 3 votes

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


# Question
Title: Is it possible to solve 3SUM in $O(n^2)$ time?
**Problem:** **3SUM**

**Input:** Three lists A, B and C of integers and an integer k. Each list contain $n$ numbers. **Task:** Decide whether there exists a tuple (a, b, c) ∈ A × B × C such that a + b + c = k.

**Question :** Is it possible to solve **3SUM** in $O(n^2)$ time using constant space ? Prove or disprove it

# Answer
A $O(n^2)$ algorithm (with $O(1)$ space) is as follows:

* Sort $A$, $B$, and $C$ individually in $O(n \log n)$.
* For each $a \in A$:
    + Search a pair of $b \in B$ and $c \in C$ such that $b + c = k - a$. This can be done in $O(n)$ by traversing $B$ from the smallest to the largest and $C$ from the largest to the smallest. (Tip: Comparing $b + c$ with $k-a$ each time.)
> 5 votes

# Answer
~~This question is not a 3sum problem.~~ The question can be solved with hash tables. For each element in **C** traverse **A** and see if the corresponding element exists in **B**. Time complexity would be $O(|C|\*|A|\*1) = O(|C||A|)$

Edit:
Answer to the updated question:

This problem can be treated as **2SUM** problem for each element in **C** (or any other list as they are symmetrical). That is for each $c \in C$ we find solutions for the sum $k - c$ using elements from **A** and **B**.

For a $O(1)$ auxiliary space algorithm one can first sort **A** and **B**. Then use 2-pointer algorithm (Tutorial) to solve the 2SUM problem in $O(n)$.

Comment if you have doubts on implementation. You can also see https://cs.stackexchange.com/a/13586/81272
> 2 votes

---
Tags: complexity-theory, lower-bounds
---


# Question
Title: Using closure properties to show that $L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)$ is regular or not
i'm trying to figure out whether this Union $\left \[ L\_1=\\{a^lb^mc^m|l,m\ge 0\\} \cup L(b^\*c^\*)\right\]=K$ is regular or not, now since regular languages are closed under intersection, so i assume $K$ is regular then its intersection with $L(a^\*b^\*)$ should be regular which is $K\cap L(a^\*b^\*)=L(a^\*)\cup L(b^\*)$ right ?

1 - Does this implies that the Union is also regular ?

2 - i know that $L=\\{a^lb^mc^m|l,m\ge1\\}$ is CFL, but is $L\_1$ also CFL ?, which is basically $L\_1=L\cup \\{\epsilon ,a,bc\\}$

3 - is $K$ regular or not and how to prove it ?

Any Hints would be appreciated.

# Answer
You are not starting with the right proof idea. It's this:

1. I want to show $L$ is not regular.
2. Assume towards a contradiction that $L$ *is* regular.
3. Since REG is closed against $f$, I conclude that $L' = f(L)$ is also regular.
4. But I already know that $L'$ is not regular (from elsewhere). Contradiction; $L$ can't be regular.

See here for complete examples.
> 0 votes

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


# Question
Title: An algorithm to generate all connectible pair combinations
In this thread I am seeking for an advice or a starting point on how to solve the following riddle. I need to come up with an algorithm which will generate all possible combinations, but I don't know where to start. In this example let's assume that we have 3 value pairs

```
1 2

2 3

3 1

```

The aim of a riddle is to make as much UNIQUE pair connections as possible. So the first KeyValuePair can connect on value 2 of second KeyValuePair, whereas second KeyValuePair can connect on number 3 of third KeyValuePair. Start and End key can not be the same. Here is a graphical representation of the expected result:

```
Valid combinations:

1 2  (1 - 2 connection)

2 3  (2 - 3 connection)

3 1  (3 - 1 connection)

1 2, 2 3 (1 - 3 connection)

1 2, 3 1 (2 - 3 connection)

2 3, 3 1 (2 - 1 connection)

Invalid combinations:

3 1, 1 2 (3 - 2 connection, duplicate)

2 3, 1 2 (3 - 1 connection, duplicate)

3 1, 2 3 (1 - 2 connection, duplicate)

1 2, 2 3, 3 1 (connection: 1 - 1, not unique, 'Start' and 'End' key can not be the same)

```

I hope I did not miss anything :). A graphical representation of joining would be:

Pair 4 1 was added for the sake of demonstration. In a real world application I expect there to be 100+ pairs. Therefore an algorithm must be efficient. Also (sorry if this is too much) I will need to make sure that there are no more than 3 pairs in a chain (therefore above image is not entirely correct)! But this requirement can be ignored right now, for the sake of simplicity. How to design an algorithm like this?

**EDIT:** Based on comment replies I think I need to provide additional explanation of the real use-case for this algorithm. In reality there will be currencies instead of numbers. So `EUR/USD` is 1 - 2, `USD/RUR` is 2 - 3, `RUR/EUR` 3 - 1, in that case (`EUR/USD - USD/RUR`) is also 3 - 1, but fundamentally it is different kind of conversion! What we are searching here is basically how every currency can be converted to any other currency. For that same reason `EUR/USD` \- `USD-RUR` \- `RUR/EUR` (`= EUR/EUR`) is not a valid case. Hope that explains it a bit better.

# Answer
Model the whole thing as a directed graph.

* Currences are nodes.
* Conversions are edges.
* Conversion factors are edge weights.

So, in your example, you'd have nodes `EUR` and `USD`, and edges from `EUR` to `USD` with weight 2 resp. from `USD` to `EUR` with weight 1/2.

Now, every (directed) path from one currency to another represents a potential series of conversions, and the total conversion factor is the product of all traversed edge weights.

Note that, in general, there are super-exponentially many such paths so you probably do not want to list them all. Furthermore, finding the "longest" path may be NP-hard.
> 0 votes

---
Tags: algorithms, enumeration
---


# Question
Title: What is meant by the term 'state' in a finite-state machine?
What is meant by the term 'state' in a finite-state machine?

I have not seen a proper definition on the web and am looking for a university-level answer.

Thank you in advance.

# Answer
> 1 votes
A state is simply an assignment of all possible variables of a system to values. A state transition then means a transition from one possible set of values of variables to another set of values.

To see how this might be useful, imagine a set of two switches $S$ and a light bulb $B$ that are connected to emulate some unknown logical gate. If you want to find out what that gate is, you can use a state machine model:

Say $I = \\{S,B\\} $

Initial State: $I = \\{\\{0,0\\},0\\}$

State transitions:

$\\{\\{0,0\\},0\\} \rightarrow \\{\\{1,0\\},1\\} \rightarrow \\{\\{0,1\\},1\\} \rightarrow \\{\\{1,1\\},0\\} $

It is evident that every state is just a set of different possible values of $I.$

By looking at the values of $B$ for a set of values of $S$, You can easily deduce that the system emulates a XOR gate.

# Answer
> -1 votes
If you have done some programming in some language , then the current executing instruction can be considered as the state in automata,

Like if you consider this python code :

```
print('Hello') - (A)
print('World') - (B)

```

then it simply going from A-\>B which will be giving you the output of `"Hello World"` on your console.

So you are going from one state to another on some input or terminating the automation if nothing is left to consume.

---
Tags: automata, finite-automata, finite-model-theory
---


# Question
Title: What is the time complexity of the following loop?
```
function (n)
    i = 1
    s = 1
    while (s <= n)
        i = i+1
        s = s*i
        print "*"
end

```

# Answer
Assuming all operations are done in constant time, this loop runs in $\Theta(n!^{-1})$ where $!^{-1}$ is the inverse factorial. Intuitively, the program will enter the loop $i$ times, $i$ being the smallest integer so that $i!\geq n$.
> 0 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Definition of "idempotence" of a function?
Currently there are two things that may change between invocations of a function: the return value, and the external states. I understand that if the external states changes, the function is not idempotent. However, it seems controversial whether the return value is required to stay the same. For example, is the below function idempotent?

```
int foo = 1; // global
int bar() {
    int ret_val = foo;
    foo = 5;
    return ret_val; // 1, 5, 5, 5...
}

```

Or is there consensus over this?

# Answer
> 2 votes
There are two related concepts called "idempotence" in programming. One is the mathematical one that quicksort and Raphael talk about. Namely, given a mathematical function $f$, $f$ is idempotent if $f(f(x))=f(x)$. Or more algebraically, $f\circ f = f$.

The other notion that's common in practice and particularly for distributed computations is if an identical "request" is made multiple times, the system will behave as if it was made once. For example, an HTTP PUT is supposed to be an idempotent request so that it can be transparently repeated in case it's suspected that an earlier request was lost. This sense of idempotence is important in distributed computing because it turns at-least-once semantics into effectively exactly-once semantics.

The second notion cast into the context of an imperative language would correspond to the property of a procedure or method that calling it once is the same as calling it arbitrarily many times with the same arguments (assuming no intervening related procedures/methods are called).

The second notion can be related to the mathematical notion by viewing the request/procedure/method as performing a function on the state of the system (taken broadly). An idempotent request/procedure/method, corresponds to an idempotent function on the system state.

Arguably, the response to an idempotent request should be the same on every request. In practice, the responses tend to be informational and so potentially non-deterministic (often due to the concurrency inherent in distributed computing), that you have no real guarantee of any response. For example, the MDN page I linked discusses the case of HTTP DELETE. A HTTP DELETE may return a 200 status code after successfully deleting a resource and then a 404 for future HTTP DELETE requests. But the non-determinism of networking means that making two identical DELETE requests could produce any of two 200 responses, two 404 response, a 200 response followed by a 404, or a 404 followed by a 200 response. (And, of course, many other possibilities such as a 503 response or no response.) The upshot is that your DELETE request could get a 404 response even when you expected a 200 response for a variety of reasons and thus, since the 404 response means the resource wasn't there at the time the request was processed*, you should treat that as just as good as having gotten a 200 response.

If the semantics of your procedure/method are: "on these arguments, do this, then non-deterministically return one of this set of responses", then the procedure/method is free to return different responses (from that set of responses) even when called multiple times with the same arguments. I would consider such a procedure idempotent assuming the "do this" part was idempotent. On the other hand, if the semantics of your procedure/method are: "on these arguments, do this, then if it is the first time this procedure was called return X else return Y", then I would not consider the procedure/method idempotent.

* Of course, someone could have added it back between the time the 404 was generated and the time you received it.

# Answer
> 1 votes
Idempotence is a concept that applies to mathematical functions. Since functions in imperative programming languages can have side effects, the concept is not well defined.

In programming languages that allow to define functions without side effects (such as purely functional languages), the definition is exactly the same as the mathematical one, i.e. $f$ is idempotent if and only if $f(f(x)) = f(x)$.

---
Tags: terminology, imperative-programming
---


# Question
Title: Intersection of languages using closure properties
1. $L\_1 \in \mathrm{CFL} \cap L\_2\in \mathrm{CSL}$ is $\mathrm{CSL}$ because every $\mathrm{CFL}$ is $\mathrm{CSL}$ and by applying closure property of $\mathrm{CSL}$ under intersection, it's $\mathrm{CSL}$.
2. $L\_1 \in \mathrm{ RL} \cap L\_2 \in \mathrm{CFL}$ is same as $\mathrm{CFL} \cap \mathrm{CFL}$ . As $\mathrm{CFL}$ is not closed under intersection, we promote $\mathrm{CFL}$ to $\mathrm{CSL}$. So $\mathrm{CSL} \cap\mathrm{CSL}$ is $\mathrm{CSL}$.

But, we know that 2nd is guaranteed to be $\mathrm{CFL}$ (also $\mathrm{CSL}$).

Why I am not able to arrive at the answer ($\mathrm{CFL}$) using closure properties for 2nd case ? Can't we apply closure properties when considering regular languages?

# Answer
One of the closure properties of CFL is that they are closed onder intersection with regular languages. This can be directly applied, rather than first promoting the regular language to context-free language.

In general, if we want to know the family in which the intersection (or whatever operation $\oplus$) of two languages belongs, then we look for the smallest families $\mathrm{X}$ and $\mathrm{Y}$ that contain the two languages and for which we know an applicable closure property.

In your terminology, we "promote" as little as possible, but enough to find a family/families for which the closure property is known.
> 3 votes

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


# Question
Title: What should I do if I think I wrote an algorithm that is _generally_ faster than Atkin Sieve?
I've been having some fun with prime numbers. A few months ago I sat down to see if I could write something that could compete with Atkin Sieve and ended up with an algorithm that, on my local tests on my RAM-restricted computer provide results where my algorithm is either close to Atkin or it can be way faster (depending on the number of prime numbers that are being discovered).

I set up a repo with the "basic" algorithm and then another version that uses BigIntegers with an expanding array so that memory could expand as much as necessary (trying not to go on RAM-hungry implementations using Collections of BigInteger and such).

This is waaaay out of my area of expertise... let's say, I'm just having fun while learning so I think I need people that have more experience on the field of performance testing and also guidance from people with research background to guide my steps if it's worthy.

So.... how about you take a look at the code and run some local tests? Perhaps offer ideas to improve performance? Or how to know if I should turn this into a *serious* research project?

Branches

* Master has a basic implementation that works on boolean arrays.
* bigint has basically the same implementation using BigInteger (and Collections)
* bigint-selfgrowing: bigint implementation using an enormous boolean array (grows as needed)
* bigint-selfgrowing-lessmemory: because of the nature of the data that my algorithm handles, for every 6 numbers, only 2 of them have to be kept so I modified the arrays to not care for the other 4 numbers (which allows for a **theoretical** 66% memory reduction but with a noticeable performance hit... plus Atkin is still using the original Enormous Boolean Array so it's not comparing oranges to oranges anymore... still, worth a look)

All branches have 3 classes that can be used to easily run tests of the pattern sieve (my sieve) against atkin. They can get 1, 2 or 3 parameters:

* Single parameter: run single test with so many numbers
* Two parameters: run tests starting from first parameter up to second parameter increasing number of primes by the first parameter each run
* Three parameters: Run tests from first parameter up to second parameter increasing primes by the the third parameter each run.

For each test, it will report how many ms/ns/us it took to run (depending on the java class that was called) in csv format (and will also provide a little human-readable output on stderr, just in case).

https://github.com/eantoranz/patternsieve

Thanks in advance.

PS I used an implementation of Atkin that I found on internet (credits provided on commit, code and on stderr when running) so it might not be the best out there... if you know of a better implementation, let me know.

# Answer
> 1 votes
Your PatternSieve is what is called a wheel sieve, or the wheel optimization for the SoE and is mentioned at the SoE Wikipedia page. It's well known and used in all fast SoE implementations. See Wheel factorization at Wikipedia for example. Pritchard wrote some articles about it in the early 1980s (e.g. A sublinear additive sieve for finding prime numbers and Explaining the wheel sieve). Sorenson has also written a number of good summary papers over the last 30 years (a recent paper that includes a number of references: Two compact imcremental prime sieves). I found Quesada and van Pelt's 1996 paper A Note on the Extensions of Erathosthenes' Sieve to be useful, though I believe Sorenson's are better as a whole.

The very basic skip-evens is the first form of this, and is almost always used. Doing mod-6 (skipping 2 and 3) is oft-used because it's simple, as seen in Robert William Hank's Python examples. Mod-30 (skipping 2, 3, and 5) is especially popular in high performance implementations because the 8 candidates fit perfectly in one byte. Going further is less common because of decreasing gains for quite a bit more complexity but mod-210 isn't too bad and primesieve uses that in some cases. The modulo is the small primorial (e.g. $5\\# = 30 \rm{\ and\ } 7\\# = 210$), while the number of remaining numbers is $\phi(n)$ (Euler's totient), e.g. $\phi(30) = 8 \rm{\ and\ } \phi(210) = 48$.

You are looking at empirical performance. This is certainly interesting, but Java is definitely not the best language here, and you would be best served by using properly fast comparisons. It's fairly well known that properly optimized segmented SoE implementations are faster than the segmented SoA. E.g. GordonBGood's long analysis. The SoA you're using is certainly simple and easy to follow, but it's straight from the Wikipedia pseudocode which indicates it skips lots of optimizations. Even Bernstein's convoluted but fast C implementation is slower than the fastest SoE implementations (though it is optimized enough to beat the simple ones).

---
Tags: algorithms, primes
---


# Question
Title: FLP Impossiblity Result assumption of $C_1 = e'(C_0)$
FLP86's famous proof regarding impossibility of async distributed processes with a single fault assumes in the proof of the third lemma the existence of an event $e'$ such that the neighbor configurations $C\_0$ and $C\_1$ can be related as

$C\_1 = e'(C\_0)$.

I don't get how this is possible, as it seems to me like $e'$ carries out a state transition from a 0-valent configuration to a 1-valent configuration. In addition to this being counter intuitive the proof of case 1 of lemma 3 clearly states that any successor of a 0-valent configuration has to be a 0-valent configuration. What am I missing here?

# Answer
At least in this part of the article, the character C is used for **bivalent** configurations. The index $0$ for the bivalent $C\_0$ was chosen simply because $e(C\_0)$ is 0-valent and the index $1$ in $C\_1$ was chosen because $e(C\_1)$ is 1-valent, even though $C\_0$ and $C\_1$ are bivalent neighbors (when applying $e'$).
> 2 votes

---
Tags: distributed-systems, concurrency, synchronization, consensus
---


# Question
Title: Operating Systems - SJN/Round Robin - turn around time + waiting time
2.(10 pts) a) You are given 4 processes in a batch system that all arrive at time 0 with the following CPU burst times:
P1 : 35, P2: 25, P3: 13, P4: 22. Assuming there is no context switch overhead, draw a time line chart (Gantt chart) showing when each process executes under each of the following scheduling algorithms:

SJN (Shortest Job Next).

Round Robin with a quantum of 10.

Answer - https://i.stack.imgur.com/tgMuZ.jpg

I don't fully understand how to get the turning or waiting time.

Waiting time I'm assuming is (95+90+88+63)/4

Turn around time is P1 = 95 - 0 = 95 or 95 - 25 or 95 - 10? same goes for P2, P3, P4

# Answer
> 1 votes
Turn Around time= Completion time - Arrival Time

and

Waiting time= Turn Around time - Burst time

---
Tags: operating-systems, cpu, process-scheduling
---


# Question
Title: Paths in a graph with two kinds of costs
A weighted graph $G= (V, E, W\_1, W\_2)$ has two cost functions $W\_1, W\_2 : E \rightarrow \mathbb{R}$. Each edge $e$ has two costs $W\_1(e)$ and $W\_2(e)$. We may think the costs as representing different resources, such as time and fuel. Similarly, a path $p =e\_1, e\_2, \dots e\_n$ has two costs,

$$W\_1(p) = \sum\_i W\_1(e\_i) \qquad \text{and} \qquad W\_2(p) = \sum\_i W\_2(e\_i) \qquad$$

Consider the following decision problem: given two nodes $u, v \in V$ and two constants $c\_1, c\_2$, does there exist a path $p$ from $u$ to $v$ such that $W\_1(p) \le c\_1$ and $W\_2(p) \le c\_2$?

Is it NP complete or is a polynomial algorithm known to exist?

# Answer
This is NP-hard by reduction from Partition.

Given an instance of the Partition problem consisting of $n$ nonnegative integer values $x\_1, \dots, x\_n$, we can generate an instance of your problem as follows:

* Make $n+1$ vertices $s\_0, \dots, s\_n$. Let $u = s\_0$ and $v = s\_n$.
* Make $n$ vertices $a\_1, \dots, a\_n$, and edges $s\_{i-1}a\_i$ for every $1 \le i \le n$ having weights $W\_1(s\_{i-1}a\_i) = x\_i$ and $W\_2(s\_{i-1}a\_i) = 0$.
* Make another $n$ vertices $b\_1, \dots, b\_n$, and edges $s\_{i-1}b\_i$ for every $1 \le i \le n$ having weights $W\_1(s\_{i-1}b\_i) = 0$ and $W\_2(s\_{i-1}b\_i) = x\_i$.
* Also add edges $a\_is\_i$ and $b\_is\_i$ having both weights 0 for every $1 \le i \le n$.
* Set $c\_1 = c\_2 = \frac{1}{2}\sum\_{i=1}^n x\_i$.

The original Partition instance has a solution if and only if the above-constructed instance of your problem has a solution. Basically, for each number $x\_i$, we must visit exactly one of the vertices $a\_i$ or $b\_i$, incurring a cost of $x\_i$ for one of the two weights (and zero cost for the other weight).
> 1 votes

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


# Question
Title: Effective AI for one player-one ghost pacman
I am thinking of a modified version of pacman. In this version, it will be a two-player game. Each player will have one pacman and one ghost. So there are 2 pacmans and 2 ghosts in the board at a time. No additional ghost is there. A player will control both his pacman and ghost separately- there is no predefined or random move of ghosts. Ghost of a player will try to catch the opponent's pacman. Pacman of a player will try to avoid the ghost of the opponent. Collision of ghost and pacman of the same player won't affect anything. So the pacman and the ghost of the same player need to cooperate with each other. "Moving Target Search" seems promising for the ghost, but what about the pacman? Will minimax (with alpha beta pruning) work in this multi-agent cooperative environment? I am saying this cooperative because my ghost will try to catch the opponent's pacman and my pacman will use this opportunity to eat more food. I have separate functions for the pacman move and the ghost move to simplify the gameplay. So returning a single tuple (including the moves of both pacman and ghost) from a function is not possible here.

# Answer
This is an adversarial game problem where you need to find the optimal behavior from each position. There are several approaches to attack such problem.

You can do Minimax with alpha beta pruning to find the best move. It will provide you an optimal move after exploring the `entire` tree up to some level (not too deep if the branching factor is too high, here your branching factor is $4\*players$) using a `handcrafted heuristic` by you. So the quality of the results heavily depends on the quality of the `heuristic`. If you improve the pruning you can achieve better results, as you can explore more.

Another approach is Montecarlo Tree Search. This algorithms performs really good in several games, and doesn't depend on any previously knowledge of the game. Roughly speaking, it seeks the best option by expanding the tree from the state you are in and calculates the quality of a state by performing a random simulation of the game.

There is a `novel` approach, Reinforcement learning, that you can use to find the answer. The idea behind it is approximate the optimal policy that gives you the maximal reward. Here you can understand by policy the action you will make at any position an the rewards are the points you get after each action. You can read more about it here.
> 1 votes

---
Tags: artificial-intelligence
---


# Question
Title: What is the difference between Boolean Algebra and Boolean Lattice?
What is the difference between Boolean Algebra and Boolean Lattice? I have already searched on Google but could not find a reasonable answer?

# Answer
> 3 votes
According to Wikipedia, these are two names for the same concept. You can differentiate them by stating that Boolean algebra is an algebraic structure having operations $\land,\lor,\lnot$ satisfying certain axioms, and in contrast a Boolean lattice is a lattice having certain properties; but the two definitions are equivalent. Sometimes Boolean algebra and Boolean lattice refer to specific constructions (subsets of a set), but according to Stone's representation theorem these two definitions are also equivalent.

---
Tags: algebra
---


title: Subnets in computer network

text:
# Question
Title: Subnets in computer network
***Question:*** Given: Class B IP address 169.202.0.0.

Network when divided into 4 sub networks, each one requires 16,000 IP addresses. They need to be assigned sequentially without gaps.

Find the sub networks.

***Here is my solution:***

Total IP addresses in 1 subnet are 16000 = 2^14 – 384 Bits required for subnet: 4 = 2^2 = 2 bits

Bits Required for Host id: 16000 = 214 =14 bits

Subnet mask: 255.255.192.0

**Subnet 1:** 169.202.0.0 To 169.202.62.127 = (62x256) +128=16000

**Subnet 2:** 169.202.62.128 To 169.202.125.255

**Subnet 3:** 169.202.126.0 To 169.202.188.127

***However in the solution booklet something else was mentioned( solution given below) which confused me. Please help/guide me.***

What do them mean by wasting few IP addresses and how are those particular ones selected. Moreover how did we get the solution given in the image below.

Subnet 4: 169.202.10 111100.1000000 = 169.202.188.128 To 169.202.11 111011.1111111 = 169.202.251.255

# Answer
After subnetting the the network Id for any subnet will consists of two parts:

1. First part consisting of 1st 16 bits(from left side)
2. Subnet identifier which will be of 2 bits.

All addresses within a particular subnet must have the same network Id part.

Now consider subnet 2(created by u)and consider the 3rd octet from left.

1st address - 00111110

last address - 01111101

You can see in the 1st address subnet Id is 00 but in the last address subnet id is 01. This cannot be accepted.

So to remove this problem we will give each subnet all the addresses that can be made with the remaining 14 bits. This is the right way.

The advantage of this scheme is that it allows u to expand ur network since there are always some unused addresses.
> 0 votes

---
Tags: computer-networks
---


title: Order of a leaf node in B+ Tree

text:
# Question
Title: Order of a leaf node in B+ Tree
Going with the definition, that order of a B+ tree is the maximum number of children a node can have.

What is exactly meant by the order of a leaf node? As per my understanding order of a leaf node is the number of pairs it can hold.

But in general when order of a B+ tree is defined in a question like, order is 5. Example:https://www.tutorialcup.com/dbms/b-tree.htm . Then we assume the leaf nodes to have keys in \[n/2\] to n-1(3 to 4).

If we assume the leaf can contain 5 pairs, then the upper limit on keys should be 5 and not 4. Could someone explain why its taken to be n-1 in every B+ tree insertion tutorial.

# Answer
> 1 votes
For a B+ tree the order of a node is the maximum number of keys that it can contain. This satisfies the definition of maximum number of children because for a leaf node number of record pointers(children) is same as number of keys. The last pointer present in a leaf node is not considered a children since it links one leaf to another(is not a record pointer).

# Answer
> 0 votes
As you state, the order is the maximal number of children. That is one more than the number of items the node can store.

---
Tags: data-structures, trees, databases
---


# Question
Title: Relationship between MIPS (Million Instructions per second) and operating frequency of a processor
Let's say there is an algorithm that runs on a processor at ***x MIPS***, operating at a clock frequency of ***y MHz***. If I double the operating frequency to ***2y***, what happens to the MIPS? It seems to me that doubling the operating frequency should double the instructions executed per second, i.e, MIPS = ***2x***, is this correct?

# Answer
Only if you double the speed of everything. Which you can’t in practice.
> 1 votes

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


# Question
Title: Can we use recursion for large pool of input data?
While studying recursion, I came to know that for every function call it has to store intermediate data on stack for later use. If so, then for large amount of data, recursion can be inefficient. Storing large intermediate data can cause memory overflow. Can you please explain, then why recursion is used at all? If possible, can you please provide one practical application of recursion.

Thanks!

# Answer
> Can anyone explain me why we don't see programmers using recursion on daily basis?

We do.

On StackOverflow, questions with the *recursion* tag happen just about every day.

P.S., with a little more sql-foo than what I know, you could figure out how many days in the past year or two have not had a question asked with the *recursion* tag. I scanned the past few months and didn't see any.
> 2 votes

---
Tags: algorithms, recursion
---


# Question
Title: How are lamport timestamps useful in practice?
I am reading Lamport's paper titled Time, clocks, and the ordering of events in a distributed system

I understand what's in there more or less, but I am confused whether Lamport timestamps on their own are useful in practice since just by looking at the logical timestamps, we can't say anything about which happened before what. It seems to me that Lamport timestamps on their own aren't useful, and we need to extend them to something like vector clocks to be useful in practice. Am I missing any details?

# Answer
> 2 votes
As Wikipedia explains:

> The algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and conceptually provide a starting point for the more advanced vector clock method.
>
> Conceptually, this logical clock can be thought of as a clock that only has meaning in relation to messages moving between processes. When a process receives a message, it resynchronizes its logical clock with that sender. The above mentioned vector clock is a generalization of the idea into the context of an arbitrary number of parallel, independent processes.

In distributed systems, it is often necessary for (almost) all the nodes to reach agreement on things such as the order of events. That agreed upon order need not be the God's Eye knowledge of the order of events. There are various other distributed agreements needed.

---
Tags: distributed-systems, clocks
---


# Question
Title: Are there problem instances which we know to be unsolvable?
As it says in the title:

> Are there problem **instances** which we know to be unsolvable?

Or equivalently

> Are there any promise problems with a finite number of possible inputs which are undecidable?

**Please note:** I realize that many computational problems are known to be unsolvable, but to the best of my knowledge (limited it may be) all must take an infinite number of inputs. Therefore, their existence does not imply that there cannot be an infinite number of algorithms each solving a subset of these problems.

**Remark:** I only wish to consider well-defined problems, i.e. every input has a correct output.

On a related note, is there a complexity hierarchy for promise problems with only a finite number of possible inputs?

# Answer
Every problem with a finite number of inputs is computable.

Proof: Suppose that the inputs are $i\_1,\ldots,i\_n$ and that the desired outputs are $o\_1,\ldots,o\_n$. Then the following program solves the problem:

* If the input is $i\_1$, output $o\_1$.
* If the input is $i\_2$, output $o\_2$.
* ...
* If the input is $i\_{n-1}$, output $o\_{n-1}$.
* Output $o\_n$.
> 6 votes

---
Tags: undecidability
---


# Question
Title: Analysis of brute force decoder in a $q$-ary erasure channel
Consider the $q$-ary erasure channel with erasure probability $\alpha$, i.e. given $x\in\mathbb{F}\_q$ with probability $\alpha$ it outputs $?$ and with probability $1-\alpha$ outputs $x$.

For a linear code $\mathcal{C}$ generated by an $n\times k$ matrix $G$ over $\mathbb{F}\_q$, we take a decoder $D:(\mathbb{F}\_q\cup\\{?\\})^n\to\mathcal{C}\cup\\{\text{fail}\\}$ such that:

$$D(y) = \begin{cases} c & \text{if}\ \exists!\ c\in\mathcal{C}:y\ \text{agrees with}\ c\ \text{on the unerased entries in}\ \mathbb{F}\_q \\ \text{fail} & \text{otherwise} \\ \end{cases}$$

For a set $J\subseteq \[n\]$ let $p\_G(J)$ be the probability that $D$ outputs “fail” conditioned on the erasures being indexed by $J$.

Prove that $\mathop{\mathbb{E}}\limits\_{G\in \mathbb{F}\_q^{n\times k}}\[p\_G(J)\]\leq q^{k-n+|J|}$.

Let $p\_G$ be the probability that $D$ outputs “fail”. Show that when $k = Rn$ for $R\<1-\alpha$, $\mathop{\mathbb{E}}\limits\_{G\in \mathbb{F}\_q^{n\times k}}\[p\_G\]$ is exponentially small in $n$.

For the first part I think that if the errors occurred are indexed by $J$, we are left with $n-|J|$ correct entries, so $D$ fails when the corresponding $n-|J|$ rows of $G$ does not imply a unique solution to the set of linear equations. But I don't know how to compute the probability of such an event.

For the second part I took random variables $\forall\ J\subseteq \[n\]:\mathbf{1}\_J$ which indicates whether the errors occurred are indexed by $J$. It is clear that $\mathbb{E}\[\mathbf{1}\_J\]=\alpha^{|J|}(1-\alpha)^{n-|J|}$ and I tried to use the above bound for all the $J$'s with $|J|\leq n-k$ and a bound of $1$ with the other $J$'s, but it doesn't seem to be sub-exponential at the end. Moreover I ended up with partial binomial theorem sums and I failed to estimate them.

# Answer
> 2 votes
To upper bound the first probability, we can assume without loss of generality that the sent codeword is the zero codeword. After deleting $|J|$ rows, we are left with a random $(n-|J|)\times k$ matrix $A$, and we want to bound the probability that its (right) kernel is non-trivial, that is, that there is a non-zero vector $x$ such that $Ax=0$. For any non-zero vector $x$, $Ax$ is a uniformly random vector (why?), and so the probability that $Ax=0$ is $q^{-(n-|J|)}$. Since there are $q^k-1$ many non-zero vectors $x$, the union bound shows that the probability that one of them satisfies $Ax=0$ is at most $q^k \cdot q^{-(n-|J|)}$. We can slightly improve on this by considering vectors up to scalar products, which reduces the probability by a factor of $q-1$.

The second half involves applying Chernoff's bound (also known as Hoeffding's bound) to show that it is unlikely that there are many erasures, and then applying the bound in the first half. Choose the threshold so that $q^{k-n+|J|} \leq q^{-\epsilon n}$.

---
Tags: information-theory, error-correcting-codes
---


# Question
Title: Enumerating pairs of disconnected cliques in a graph
Given an unweighted graph $G = (V,E)$. I am interested in enumerating all pairs of disconnected cliques, i.e. there should not exist any edge between two cliques. (For example, there would not exist any such pair in a complete graph). A clique could be of any size $\geq 1$.

Are there any standard approaches to solve this problem? If so, could someone please highlight the sources or suggest some approaches?

# Answer
I figured out this solution while discussing with a Professor.

The above problem could be formulated into a clique search problem. Let the input graph be $G\_1 = (V\_1,E\_1)$. Create a duplicate $G\_2 = (V\_2,E\_2)$ of $G\_1$. Let vertices in $V\_1$ be denoted by $\\{v\_{11},v\_{12},...,v\_{1k}\\}$ and their duplicates in $V\_2$ be represented by $\\{v\_{21},v\_{22},...,v\_{2k}\\}$. Now, for each pair of vertices $(v\_{1i},v\_{1j})$ in $G\_1$ without an edge with $(i\<j)$, connect $(v\_{1i},v\_{2j})$. Then, all the desired pairs of disconnected cliques of $G\_1$ can be obtained as cliques of $G\_1 \cup G\_2$ that have vertices in both $G\_1$ and $G\_2$.
> 1 votes

---
Tags: graphs
---


# Question
Title: How do we define a tree in a directed graph?
I am trying to solve the exercise 3.3 in *Approximation Algorithms* by Vazirani, pg 34. It states

> **3.3** Give an approximation factor preserving reduction from the set cover problem to the following problem, thereby showing that it is unlikely to have a better approximation guarantee than $O(\log{n})$.
>
> **Problem 3.14** (Directed Steiner tree) $G = (V,E)$ is a directed graph with nonnegative edge costs. The vertex set $V$ is partitioned into two sets, required and Steiner. One of the required vertices, $r$, is special. The problem is to find a minimum cost tree in $G$ rooted into $r$ that contains all the required vertices and any subset of the Steiner vertices.

My (related) questions

1. How do we define a tree in a directed graph? I searched on the Internet and found that a tree is defined for only undirected tree, in particular on Wikipedia.
2. What does it mean "*rooted into* $r$"? Does it mean out-degree of $r$ is zero?

# Answer
Sometime there isn't a completely agreed upon meaning of terms, it is more useful to look at the context to see which definition is appropriate.

In this case, instead of searching for definition of general *directed tree*, it is better to look for *directed steiner tree*.

A quick search pulled up this paper which has this diagram showing an example of directed steiner tree:

While not explicitly defined, it coincides with my intuition of what a *default* directed tree should look like --- A directed graph with **exactly** one directed path from a distinguished root vertex to any other vertex in the graph (tree).
> 8 votes

# Answer
A tree is defined as an acyclic graph. Meaning there exists only one path between any two vertices.

In a steiner graph tree problem, the required vertices are the root, and terminals. The optimal tree will be the lowest cost tree which contains exactly one path between the root vertex, and each terminal vertex.

Tree(graph theory)

Steiner Tree Problem
> 3 votes

---
Tags: graphs, terminology
---


# Question
Title: Is it beneficial to convert recursion to tail recursion?
If it is beneficial, then how Big-O (time complexity) is affected? Embedded link provided by members does not answer original question.

# Answer
> 2 votes
Any recursion can be converted into tail recursion by transforming the function into continuation-passing style.

The continuations being built can be defunctionalized (a-la John C. Reinolds) into a list of custom data expressing the same intent.

In other words you gradually build a TODO list while going along, then you DO it. And while doing the topmost recorded task, you may add some more TODO tasks there.

But you never recurse, all you do is build and interpret the TODO data. The accumulator transform is a specific case of this.

The answer on the linked (as duplicate) question talks about the CPS. Here's the example from there, in Scheme/Lisp, with a little twist:

```
(lambda (a b c d)          ; a normal function of 4 arguments
  (+ (- a b) (* c d)))

```

This could be transformed into continuation-passing style as follows:

```
(lambda (k a b c d)        ; the same, as a CPS-function,
  (k- (lambda (v1)            ; expecting one additional function,
         (k* (lambda (v2)       ; the "continuation" to be called
                  (k+ k v1 v2))
             c d))
      a b))

```

The twist is simply the naming of the CPS built-in functions, to remove possible confusion: while `-` is the regular subtraction function, `k-` is its CPS equivalent.

Every CPS-function accepts an additional parameter: a "continuation" function of one argument describing "what-to-do-next" with that argument.

So if `-` expects two arguments, to subtract one from the other, `k-` expects three arguments: in addition to the two values it expects a function of one argument that it will feed the result of the subtraction *to*.

As you can see, there's no recursion - the function itself is even unnamed. We construct big nested anonymous function instead, describing the future computation step by step in the typically inside-out linearized fashion.

---
Tags: algorithms, recursion
---


# Question
Title: Algorithm to sort n size input with k distinct elements
We need an optimal algorithm in pseudo-code for sorting a sequence of $n$ which has only $k$ distinct numbers ($k$ is not known a Priori).

Can we use Counting Sort to solve this problem in $O(n+k)$ time? I don't think so. Though the time complexity of Counting Sort is $O(n+k)$ but $k$ is the largest element in the input but not the number of distinct elements.

> Is there any chance that we can get a linear time algorithm to solve this problem?

# Answer
It is not possible. As if $k = \Theta(n)$, Hence you can not find a linear algorithm. Anyhow, you can find an algorithm in $O(n + k\log(k))$.

Find maximum in $O(n)$. Then create a hash table to find the $k$ distinct values is $O(n)$. Then sort the $k$ values in $O(k\log(k))$. Notice that the space complexity in this algorithm is $O(\text{largest value})$. However, the time complexity would be $O(n + k\log(k))$.
> 2 votes

---
Tags: algorithms, sorting
---


title: Is there a name for this class?

text:
# Question
Title: Is there a name for this class?
The class $C\_{1,\epsilon }$ of decision problems solvable by an NP machine such that

1. If the answer is 'yes,' at least 1/2 and at most $1-\epsilon$ of computation paths reject.
2. If the answer is 'no,' all computation paths reject.

Is there a name for this class that looks like $RP$?

Is this in $RP$ or $coRP$?

The class $C\_{2,\epsilon }$ of decision problems solvable by an NP machine such that

1. If the answer is 'no,' at least 1/2 and at most $1-\epsilon$ of computation paths accept.
2. If the answer is 'yes,' all computation paths accept.

Is there a name for this class that looks like $coRP$?

Is this in $RP$ or $coRP$?

What is $C\_{1,\epsilon }\cap C\_{2,\epsilon}$?

Is it in $ZPP$?

# Answer
Your class $C\_{1,\epsilon}$ is the same as RP. It is clear that everything in $C\_{1,\epsilon}$ is in RP. In the other direction, take an RP algorithm for a problem, and amplify its success probability to be $1-\delta$. Now modify it to toss coins and reject with probability $\epsilon$ (or some constant $c \> \epsilon$) and only then run. If $\delta$ is small enough, then the overall success probability in the Yes case will be arbitrarily close to $1-\epsilon$.

The same argument shows that $C\_{2,\epsilon}=coRP$, and so $C\_{1\epsilon} \cap C\_{2\epsilon} = ZPP$.
> 3 votes

---
Tags: complexity-theory, complexity-classes
---


title: Minimum number of states in the DFA

text:
# Question
Title: Minimum number of states in the DFA
I am trying to solve following problem but unable to solve this. Can anyone tell me how to approach this kind of problems where it is not easy to make DFA.

> The minimum number of states required to construct a DFA that recognizes the language of strings over the alphabet ${a,b}$ whose tenth symbol from the right end is $a$?

I tried converting R.E of the language which is $(a+b)^\*a(a+b)^9$ into DFA but couldn't convert. Can anyone convert this into DFA or provide a $generalized$ solution when it is $n^{th}$ symbol from the right hand of the string?

# Answer
Let $L\_n$ consist of all words over $\\{a,b\\}$ such that the $n$th symbol from the right is $a$. The minimum number of states in a DFA accepting $L\_n$ is $2^n$.

First, let us construct a DFA with so many states. The states of the DFA correspond to strings of length $n$ over $\\{a,b\\}$. The starting state is $b^n$. When in state $\sigma\_1\ldots \sigma\_n$ and reading $\sigma$, we move to state $\sigma\_2 \ldots \sigma\_n \sigma$. A state is accepting if the first symbol is $a$.

Second, we use the Myhill–Nerode theorem to show that $2^n$ states are necessary. We claim that all words of length $n$ are pairwise inequivalent. Indeed, let $x \neq y$ be words of length $n$. Then $x\_i \neq y\_i$ for some $i$, say $x\_i = a$ and $y\_i = b$. This implies that $x b^{i-1} \in L\_n$ whereas $y b^{i-1} \notin L\_n$, showing that $x,y$ are inequivalent modulo $L\_n$.
> 4 votes

---
Tags: finite-automata
---


title: what are the roles of Turing Machine?

text:
# Question
Title: what are the roles of Turing Machine?
I am having trouble in writing the specific role of Turing machine? can it solve all the algorithm a digital computer can solve(i.e. today's PC's)?

# Answer
The Turing machine is a theoretical computational model which is studied in undergraduate courses due to its simplicity and for historical reasons.

Historically, the Turing machine was the first widely accepted definition of computation, and for many years, it was arguably the simplest definition to explain. Nowadays, however, we can define computation equivalently using our favorite programming language – one of the wonders of computability theory is that there are many models of computation which are completely equivalent in power, as long as we don't care too much about time and space usage. Turing machines are also polynomially equivalent to RAM machines, and so to imperative languages, and this means that you can define the classes P and NP using either Turing machines or (say) C programs, and obtain completely equivalent definitions.

Turing machines have the advantage that their semantics are very simple to state and analyze. While it is still a big mess to construct a universal Turing machine (in this sense Turing machines are not better than C programs), other basic theorems lend themselves to an easy proof using the Turing machine model. The most obvious example is the Cook–Levin theorem, which states that SAT is NP-complete. Complexity classes with limited resources also have relatively simple definitions using Turing machines (for example, logspace), whereas a definition using C programs would have to be somewhat subtler.

Modern computers are based not on the Turing machine but instead on ideas of von Neumann. In this sense the Turing machine is not a realistic model, and generally speaking the RAM model should be prefered. However, the RAM model has several different variants which are *not* equivalent, whereas Turing machines are more standardized, with different variants being mostly essentially equivalent (even when time and space usage are measured).
> 1 votes

# Answer
Well there's no existing algorithm on a computer that can execute a program with the ability of a Turing machine yet, as a Turing machine can solve problems like NP-complete exactly, whereas existing algorithms are mostly approximations and not a perfect algorithm.
> -1 votes

---
Tags: turing-machines
---


# Question
Title: How does the Monte Carlo Tree Search Algorithm Decide When to Expand?
I understand that the MCTS algorithm *expands* its tree after it has *selected* the best route to take. However, how does it decide when to end selection and then expand the tree? It cannot just traverse down the whole graph... then it would always produce child nodes at the same place (right?) So, how does the MCTS decide when to produce a child node when traversing down the search tree?

# Answer
With each rollout the algorithm goes through steps of selection, expansion, simulation, and backpropagation. It does this incrementally one move at a time. 1 selection, 1 expansion, 1 simulation of random playouts them back propagated the values back to root. Next rollout and henceforth depending on ucb weights between exploration and exploitation.
> 1 votes

---
Tags: algorithms, search-algorithms, monte-carlo
---


# Question
Title: Adversarial Monte Carlo Tree Search Asymmetry
Monte Carlo Tree Search with UCT is praised for it's asymmetric tree growth, growing promising subtrees more than non-promising ones.

But in a 2-player adversarial game, when a win at one node is a loss at the node below it, wouldn't the tree growth be extremely favourable for the current player at each node, and result in a not so asymmetric tree growth?

# Answer
The most explored path will be the Nash Equilibrium, because at each step we choose the best move for each player.
The asymmetry happens at each level towards the best move for the current player, thus overall the tree will not grow asymmetrically.
> 1 votes

# Answer
With each new rollout, considering games with many traps like chess, the random playouts converge super slowly if at all. Usually based on very high rollouts and on nodes with greater exploration.. Good game play for me happens around +100000 rollouts but dependant on the game. For one rollout you are correct, but with each rollout things get incrementally better. Backpropagation over many rollouts solve this in the UCB.
> 0 votes

---
Tags: artificial-intelligence, game-theory, monte-carlo
---


# Question
Title: Monte Carlo Tree Search in connect 5 tree design
I'm trying to create a mcts ai for connect 5 algorithm. However, I'm confused on designing the tree. Here is a quick description of the algorithm:

The initial state, *S0* is the board state where the AI **places the stone**, or in other words, the AI's turn. Is it correct that each node should be the AI's turn, not the humans?

In the expansion phase, you need to "create child nodes". In my game, the child nodes would each be a place where an AI can make a move. However, if I want to select the *next avaliable AI move*, I need to know where the enemy, or the human places the stone before the next avaliable AI move. I improvised by making it 2-layered: for every avaliable human moves, add every avaliable AI moves after the human plays. Is this the correct way to do it?

This is my current tree structure in an Example: Each state has info of where black and white "stones"are placed. the AI plays white, and Human plays black. Black plays first. state S0 would be the first move of the game.

```
                S0(black stones:[(2,2)],white stones:[])
                        /                            \
                       /                              \
                      /                                \
S1(black stones:[(2,2)],white stones:[(1,1)])        S2(black stones:[(2,2)],white stones:[(1,2)]
    |                                                       |
S3(black stones:[(2,2),(2,1)],white stones:[(1,1)])  S4(black stones:[(2,2),(2,3)],white stones:[(1,2)]

```

# Answer
> 1 votes
In you implementation you need to separate the game rules from the mcts search algorithm. Mcts does not need an evaluation like minimax. When calling random playouts all you need to do is keep making legal moves till the game ends and mark the playout with an outcome of win/loss.

your game rules need functions like legal\_moves, make\_move, undo\_move, is\_game\_over, winnerIs and maintain a states that represent the position

your mcts needs mcts, ucb\_sample, expand, random\_playout, backpropogation

for states you need position {visits, value or total/count}

---
Tags: trees, artificial-intelligence, board-games, monte-carlo
---


# Question
Title: What is partial expansion in Monte Carlo Tree Search?
I'm trying to understand the modification to the MCTS algorithm called Partial Expansion.

From what I've been reading it enables one to not require all child nodes to have been expanded before expanding grandchild nodes.

However, I'm having a hard time conceptually understanding this process and its potential benefits. Can anybody please help me out?

# Answer
> 1 votes
Partial expansion is a pruning/reduction strategy. Instead of requiring all children to be explored in selection you could set a threshold like done in "Move Count Pruning" (MCP) based on only expanding the first 10 children only. Usually you call ucb\_sample if all children are explored depending on your weights.

Another example could be based on the rollout. Even rollouts need full expansion and odd rollouts need only MCP. This way the tree gets explored in a different way.

Benefits usually come in reducing time and favouring early moves. Early moves get more time and those nodes get better statistics. With backpropogation grandchildren help update their parents because statistics exist.

---
Tags: monte-carlo
---


# Question
Title: UCT1 Algorithm: What does "total number of simulations" mean?
When reading up on the UCT1 algorithm (I'm writing a Monte Carlo tree search), I'm having trouble with the formula. $$\frac{w\_i}{n\_i} + \sqrt{\frac{\ln t}{n\_i}}$$ Wikipedia, this guy, and this guy all say that $t$, or whatever else they use for that variable, equals the "total number of simulations". What does this mean, exactly? The total number of simulations in the entire tree? The child nodes of that particular node? The "sibling" nodes? So, what is the $t$ is this equation? Thanks!

# Answer
The UCT1 algorithm is actually an algorithm for a multi-armed bandit. There is a machine with several arms. At each round you pull one of the arms and get some reward. Your goal is to maximize your total reward. In this algorithm, $t$ is the round number: $t = 1$ in the first round, $t = 2$ in the second round, and so on.

When using UCT1 to perform Monte Carlo tree search, you treat each explored node as a multi-armed bandit. Monte Carlo tree search consists of several rounds of *simulations*: in each round a complete game is played out. The value of $t$ for a particular node is the number of rounds at which you passed through the node.

$n\_i$ is the number of simulations through the $i$th child, i.e. how many simulations encountered that state in their simulations. A simulation consists of an entire game played out. Once it exits the node it invariably goes through one of its children. So $t$ is the sum of the $n\_i$.

You ask:

> I made some images. Is it like this or like this?

It's more like the latter.
> 5 votes

# Answer
$t$ = total number of visits for the node in question.
$n\_i$ = total number of visits for its child.
$w\_i$ = value of its child

You need to normalize each output over the total value and then select the maximum for best move.
> 0 votes

---
Tags: algorithms, trees, search-trees, monte-carlo
---


# Question
Title: Check if there is only one simple path in graph between nodes x and y`
Let's say we have given simple undirected graph $G$ having $N$ nodes and $M$ bidirectional edges. For given $x$ and $y$ we want to check if in the graph there is only one simple path between them.

What I was thinking for, is that we should find all the cycles in the graph and run bfs from $x$ to $y$, if the path doesn't move through the vertices that are in some cycle, there is only one path, and otherwise there are more.

Is there some other way to check this?

# Answer
Raphael's suggestion to use 2-shortest path is correct but more complex than necessary.

Your approach is unfeasible, the number of cycles is factorial in the size of input.

Here's a sketch of a solution in time $O(|V|+|E|)$.

Find a path $p\_1, \dots p\_n$ from $x$ to $y$ in $O(|V|+|E|)$. If no such path exists, answer $\textsf{NO}$. Otherwise, mark all the nodes in the path. That path is indeed unique if and only if no node in that path reaches a node that comes after it. Starting from the first node of the path $p\_1$, pick a random edge going out from $p\_1$ other than the one that connects it to $p\_2$ and start a DFS from there. If you reach a marked node, answer $\textsf{NO}$, if you never reach a marked node, cut that branch from the graph and pick another random outgoing edge. Continue in a similar fashion until all outgoing edges are exhausted, then start again with the following node until you reach $p\_n$. If you finish the procedure without ever answering $\textsf{NO}$, answer $\textsf{YES}$. The entire procedure has the cost of a DFS, $O(|V|+|E|)$, therefore the overall time is $O(|V|+|E|)$.
> 5 votes

# Answer
Run a k-shortest path algorithm with $k=2$ and observe whether it fails.
> 2 votes

# Answer
If there exist a path from source $x$ to some cycle it doesn't always contradict the existence of a single simple path. Take a look at the following example:

Here there is a cycle that can be reached from $x$ and $y$. This problem can be solved in $O(|V| + |E|)$.

You can run BFS to find shortest distance from $x$ to every vertex on the graph and the same from $y$. One node belong to the shortest path from $x$ to $y$ if and only if $$distance(x,u) + distance(u,y) = distance(x,y)$$ Now, to check if there is a single path, check that valid nodes in shortest path at every distance occurs at most once. This is, if there are at least two nodes that belong to a shortest path from $x$ to $y$ with the same distance to $x$ then, there are at least two shortest path, otherwise it is unique. You can do all post-processing in $O(|V|)$.
> 2 votes

# Answer
Perform a depth-first search starting in $x$ and annotate edges according to whether they are tree, back, or cross edges (cf. e.g. here).

There is more than one simple path from $x$ to $y$ if and only if there is (at least) one node on the path from $x$ to $y$ using only tree edges (i.e. the path found by DFS) that is incident to a back or cross edge.
> 0 votes

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


# Question
Title: Using visible line segments to compute a visibility polygon
Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the region in $P$ consisting of all points $q$ visible from point $p$. A point $q$ is visible from point $p$, if the line segment $\overline{qp}$ is completely in the polygon $P$.

As for now, let's ignore the case where a line segment lies completely on the ray.

Now I have a collection of line segments (edges of the polygon) which are visible from point $p$. The problem is that not every line segment in the collection is fully visible which is why I can't simply connect them into a polygon. I first need to compute which part of each line segment is visible and connect those. This last step is what I struggle with.

Here are two examples:

In the left example edge $\overline{AD}$ is partially seen from $p$, in the right example it's $\overline{GH}$ (rest of the edges are completely visible).

For the left example, how can I use the fact that $\overline{EB}, \overline{BC}, \overline{AD}$ and $\overline{DE}$ are visible from point $p$ in order to compute the visibility polygon?

I struggle with finding an algorithm to do this which doesn't fail for every second case I apply it to. Any suggestions?

# Answer
> 1 votes
First, assume we already have a list $L$ with all segments in $P$ that are at least partially visible from $p$, ordered by the smallest angle $\theta$ such that a segment is visible from $p$ at angle $\theta$. (This can be done with a (angular) sweep line algorithm in $O(n\log n)$)

Now, observe that if a line from $p$ to some point on the segment $s\_i$ in $L$ intersects some segment of $P$, it must intersect either $s\_{i-1}$ or $s\_{i+1}$ (be careful to wrap around the ends of the list), i.e. one of the neighbours of $s\_i$.

Therefore, we can construct the visibility polygon as follows: iterate over all segments $s\_i$ in $L$ and compute the visible sub-segment of $s\_i$ using the segments $s\_{i-1},s\_{i+1}$. (call it $s\_i^\*$) Add it to your visibility polygon and then add the lines connecting the endpoints of $s\_i^\*$ with $s\_{i-1}^\*$ and $s\_{i+1}^\*$ to the visibility polygon (if they aren't already connected directly).

# Answer
> 0 votes
If visibility polygon means a polygon $P'$ where point $p$ needs to able to see all the points on the line segments in $P$ without any other point blocking it then here is what I think:

You are given polygon $P$ so you are also given the vertices $V$ and edges $E$ (line segments) within $P$. So if $p$ is visible in $P$ then point $p$ and all points $x$ on the edges $E$ can form a line segment $\overline{px}$ where no other point on $\overline{px}$ can contain another point $x'$ from another edge $E'$.

This means that $\overline{px}$ does not intersect any other point $x'$ of any other $E'$ in $P$. This also means that you would be able to check from one vertex on $E$ to the other.

Therefore, if at given time your algorithm finds a segment that's only partially visible you will also know where the last point that allows it to be visible to $p$ and so you would use that point as the new vertex.

For example, in the your left polygon above, you can find the point from $\overline{AD}$ where any further towards $A$ would render the line partially not visible. Let's say that this new point is $A'$. Then by removing $\overline{AD}$ and $\overline{AC}$ and add $\overline{A'D}$ and $\overline{A'C}$ to the given polygon (or simply replace $A$ with $A'$ for the line segments involving $A$) then you would be able to compute the visibility polygon.

The one problem that I can think of currently is that there are infinitely many points on a given line so this algorithm can essentially run infinitely. So there has to be a length difference, $\delta$, between two points on the line segment that's small enough to be able to check all critical points but big enough that it won't let the algorithm run infinitely so that your algorithm would just increment by $\delta$.

---
Tags: algorithms, computational-geometry, polygons
---


# Question
Title: find the missing number in a block of 3 numbers
Given a contiguous sequence of numbers in which each number repeats thrice, there is exactly one missing number. Find the missing number.

```
eg: 11122333 : Missing number 2
11122233344455666 Missing number 5

```

I think we can't do better than just going from beginning to the end and checking the count if a specific number count is less than 3.

```
s = "11122233344455666"
count = 1
flag = 0
for i in range(0, len(s), 3):
    if i+2 < len(s) and s[i] != s[i + 2]:
        print s[i]
        break
    elif i+2 >= len(s):
        print s[i]
        break

```

# Answer
Your current algorithm is linear in the size of your array $A$, which I'll call $n$. We can do a bit better, by observing the following: If some index $3i-1$ comes before the missing number, then $A\[3i-1\]=i$. Otherwise, $A\[3i-1\]=i+1$. (I start indexing at $0$)

So, we can do a binary search on $i$, as we always can see whether the index of the missing number is larger or smaller than $3i-1$. This gives an $O(\log n)$ algorithm, which is an improvement on your linear time algorithm.
> 3 votes

---
Tags: algorithms
---


title: On $UP$, $NP$, $\oplus P$ and $PP$?

text:
# Question
Title: On $UP$, $NP$, $\oplus P$ and $PP$?
We know $UP\subseteq NP\subseteq PP$.

> Is $UP^{\oplus P}\subseteq NP^{\oplus P}\subseteq PP^{\oplus P}$?

I think the first $UP^{\oplus P}\subseteq NP^{\oplus P}$ is straightforward since whatever queries an $UP$ machine can do we know an $NP$ machine can do.

> How to show second $NP^{\oplus P}\subseteq PP^{\oplus P}$?

# Answer
Consider the oracle machine $N$ that decides $L \in NP^{\oplus P}$. For each computational branch of $N$, if it ends with $\textsf{YES}$, do nothing. If it ends with $\textsf{NO}$, branch and output once $\textsf{YES}$ and once $\textsf{NO}$. Therefore, $L\in PP^{\oplus P}$.
> 1 votes

---
Tags: complexity-theory, reference-request, complexity-classes, nondeterminism, oracle-machines
---


# Question
Title: Is the implementation relation between an interface and a class an instantiation or inheritance relation, or neither?
In Python, we have `metaclass` and `abstract class`.

In Java and C#, we have `interface` and `abstract class`.

The relation between a metaclass and a class is instantiation, so it extends the instantiation relation between a class and an object.

The relation between an abstract class and a class is inheritance, so it extends the inheritance relation between concrete classes.

The relation between an interface and a class is implementation.

* Is this implementation relation an instantiation relation, an inheritance relation, or neither?
* If neither, can this relation be viewed as some extension of some relation between some classes or objects?
* is an interface more like a metaclass or an abstract class?

Thanks.

# Answer
From notes I have from university, here is an explanation I found useful that may help

> An interface, or protocol as it is sometimes called, is a device that is used to allow unrelated objects to interact with one another, by implementing an agreed upon system of behavior. When a class implements an interface, the class agrees to implement all of the methods defined in the interface. Interfaces are useful since they capture similiarity between unrelated objects without forcing a class relationship.

The important line is the bottom, there is no class relationship between classes that impliment an interface. You cant view it in the same way you would with instances of classes and abstract classes. These give a direct relation in terms of object type and subtype. It is not a guarantee of relation between objects but instead a guarantee of functionality.

To your bullets I would say; Neither, not really, and it is not really like either metaclass or abstract class at all.
> 2 votes

# Answer
> Is this implementation relation an instantiation relation, an inheritance relation, or neither?

I would say interfaces are very close to abstract classes. They provide the functionality of multiple inheritance in single-inheritance languages.

A class X implementing an interface Y, or inheriting from another class Y, both allow me to treat objects of class X as Ys in my code. I rarely create an abstract class, but when I do, I always wonder whether to make it an interface instead.

In Java and C#, classes can be marked as `abstract` to indicate they cannot be instantiated. It would have made perfect sense to specify interfaces as `bodiless` classes to indicate they cannot have method bodies or other executable code.

So an implementation relation is effectively a (multiple) inheritance relation, except that the language designers happened to choose different terminology.

Instantiation is the relationship between classes and their objects. in statically typed, compiled, strictly class-based languages such as Java or C#, instantiation is very different from inheritance and implementation: the latter are compile-time relationships defining which code will be associated with which objects at runtime, while instantiation is something that happens at run time, defining a relationship between an entity existing only at run time (an object) and something defined at compile time, namely the code associated with it, specified in the class(es) it belongs to.

This distinction is blurred by reflection, which can create all of these things at run time. It is also much blurrier in dynamic languages such as Python, in which none of these things are defined at compile time in the first place. Another way to blur it is to allow method implementations and inheritance to happen not only on classes, but also on individual objects, such as in a Lisp dialect I've used. If an object can define its own methods, it becomes more like a class, so instantiation becomes more like inheritance.

> Is an interface more like a metaclass or an abstract class?

Metaclasses don't really have a pendant in statically classed languages such as Java or C#. They allow code to be defined that is executed at class initialization time. Java and C# also allow this, but they don't offer a construct that allows such code to be bundled together like that. Abstract classes can be used for this purpose, so I would say they're the closest match.
> 1 votes

---
Tags: programming-languages, object-oriented
---


title: Is the empty string a terminal symbol?

text:
# Question
Title: Is the empty string a terminal symbol?
I ask this question with regards to a grammar in Chosmky Normal Form. The definition states that the rules must be of the following forms:

1. A $\rightarrow$ BC
2. A $\rightarrow$ a
3. S $\rightarrow$ $\epsilon$

And A,B and C are non-terminal symbols, B and C are different from S and a is a terminal symbol. The definition also states that the last rule can only be present if the language of the grammar accepts the empty string (source). Now if $\epsilon$ is a terminal symbol, than this is a contradiction as the second rule can be transformed to S $\rightarrow$ $\epsilon$, seeing as A must not be different from S. This leads me to conclude that $\epsilon$ is not a terminal symbol, is this correct?

# Answer
It's true that, in general, definitions don't include the empty string in the set of "terminals", as there's no need for that (e.g. the production rules for a context-free grammar are defined as a relation $V \rightarrow (V \cup \Sigma)^\*$ - the star covers all productions of the form $A \rightarrow \epsilon$; in all other contexts, it can be omitted because it has no effect on concatenation).

Note, however, that in the case of a CNF grammar, you couldn't just make a simple convention for "terminals" to include the empty string and cut down to just the first two rules, because rules of the form $A \rightarrow \epsilon$ are not allowed for all non-terminal $A$, just for $S$.
> 7 votes

# Answer
The empty string is *not* a terminal symbol. A terminal symbol is an element of the alphabet, but the empty string is not an element of the alphabet.

In fact, this is an issue that we have to address when defining the formal syntax of context-free grammars. Either we ask that $\epsilon \notin \Sigma$, or we encode $\epsilon$-rules as $A \to$ rather than as $A \to \epsilon$. There is a similar choice regarding the symbol $\to$: either we ask that $\to \notin \Sigma$, or we encode rules as pairs $(A,\alpha)$. There are of course other choices, such as allowing the "user" to choose the symbols standing for $\to$ and $\epsilon$.
> 5 votes

---
Tags: normal-forms, chomsky-hierarchy
---


# Question
Title: Get a fixed-size family of k-element subsets
I have an n-element set, and I want to consider families of its k-element subsets of fixed size s. For example, if n = 3, k = 1, s = 2, we have these families:

```
{{1}, {2}}, {{1}, {3}}, {{2}, {3}}

```

In my problem n, k, s are not so small, e.g. s = n = 50, k = 20.

Let us say all such families are ordered lexicographically (or really in any clearly stated order). I want to have an efficient way to get a family by its number.

I have only a following idea: enumerate all k-element subsets of n-element set (there is an efficient algorithm to get i-th element by i). Then enumerate all s-element subsets of comb(n, k)-element set, using the same operation. Now we need to generate a number in range (0, comb(comb(n, k), s)) and turn it firstly to the number of s-element subset and then to a family of k-elements sets.

However, I want to know, if there is a more beautiful approach than just generating first combination and then second combination by its numbers.

# Answer
> 2 votes
In general, what you are looking for is a combinatorial number system (of degree $t$) , i.e., a correspondece between $\mathbb{N}$ and all $t$-combinations.

There is a large number of algorithms for $t$-combination generation from the last (at least) 50 years. In particular, the operations you are interested in are typically called *rank* and *unrank*.

For much more than what the Wikipedia article contains at the time of writing, you can have a look at say the book of Knuth \[1\] or the one by Kreher and Stinson \[2\]. Knuth's book contains pseudocode that is straightforward to write in your favorite language, and the nook of Kreher and Stinson is accompanied by source code (in C) that can be found online as well.

---

\[1\] Knuth, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Pearson Education India, 2011.

\[2\] Kreher, Donald L., and Douglas R. Stinson. Combinatorial algorithms: generation, enumeration, and search. Vol. 7. CRC press, 1998.

---
Tags: algorithms, combinatorics
---


# Question
Title: Quantum computing - Difference between a binary bit and a Q-bit
I have recently watched this introductory video on quantum computing where the speaker talks about $n$ Q-bits and the representation of $2^n$ states.

What I didn't get is the word state.How is it different from a classical computer working with $1$'s and $0$s in which each bit can represent 2 states ($0$ or $1$) so that the $n$ bits can generate $2^n$ states.

# Answer
I think something worth pointing out early on is the ambiguity of the word state. In quantum information most things have very strong (shall I say natural?) physical interpretations / origins. In classical information we represent information as bits. A bit might correspond to the state of some classical system, such as an electric sign in a circuit, etc. Evolution of classical bit vectors is arbitrary in the sense that its enforced by us humans.

In quantum computing information is represented using states of a quantum system (for example polarization of a photon). The states of a quantum system can be identified with vectors of a Hilbert space. Qubits $|0\rangle, |1\rangle$ are just an arbitrary choice bases of a two dimensional space. A two-qubit state represents a quantum system which is a composite of two two-dimensional subsystems. Evolution of quantum state vectors are governed by the laws of physics.

For a classical two-bit vector, the permissible values are $00,01,10,11$, whereas for a two-qubit system you can have any $a|00\rangle+b|01\rangle+c|10\rangle+d|11\rangle$ for $a,b,c,d\in\mathbb{C}$ provided that $|a|^2+|b|^2+|c|^2+|d|^2=1$. This, together with the postulates of quantum mechanics, permits a completely different range of behaviors of quantum systems (and qubit vectors), behaviors that are unseen in classical systems. This gives the above representation of information a lot more power compared to classical information representation. A number of physical phenomena allow various interesting information theoretic operations (such as teleportation, superdense coding, etc), which are not admissible using classical systems.

The emphasis here really is on the fact that in quantum computing you can exploit a range of physical phenomena that is not typical in classical information theory.
> 2 votes

# Answer
The point is you can have a linear combination of qubits which is not possible for classical bits. $$\alpha |0\rangle + \beta |1\rangle$$

where $\alpha$ and $\beta$ are probability amplitudes and can in general both be complex numbers. See more details here.
> 0 votes

# Answer
The state of an $n$-bit quantum system is described by $2^n$ complex numbers $c\_x$ – indexed by vectors in $\\{0,1\\}^n$ – such that $\sum\_x |c\_x|^2 = 1$. (Some people consider these numbers only up to "rotation", that is, up to multiplication by a complex number of unit modulus.) Compare this to an $n$-bit classical system, whose state is a single vector in $\\{0,1\\}^n$, and to an $n$-bit classical system with randomness, whose state is a probability distribution over $\\{0,1\\}^n$, that is, it is described by $2^n$ non-negative real numbers $r\_x$ summing to 1, $\sum\_x r\_x = 1$.

The state of a system is what you need to know in order to follow the evolution of the system, and eventually determine the output. The evolution of a quantum system is described by (local) unitary operations, which you can think of as $2^n \times 2^n$ complex unitary matrices which operate on the state by multiplying it. At the very end, the state of the system is measured, and then it collapses to the deterministic state $x$ with probability $|c\_x|^2$ (you can also measure just some of the qubits during the computation, but let's ignore that). Notice how you need to know all $c\_x$ in order to understand how the system evolves and what is its output. In contrast, to understand the evolution and output of a classical system, you just need to know the contents of all the bits, which is described by a vector in $\\{0,1\\}^n$.
> 0 votes

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


# Question
Title: Time complexity of dequeue function (queues)
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

```
MultiDequeue(Q){
     m = k
     while ((Q is not empty) and (m > 0))
     { Dequeue(Q)
       m = m – 1
      }
}

```

What is the worst case time complexity of a sequence of **n queue** operations on an initially **full** queue having n elements.?

(A) $\Theta(n) $

(B) $\Theta(n+k)$

(C) $\Theta(nk)$

(D) $\Theta(n^2)$

---

Here suppose we do one dequeue operation, then the loop will run for min(n,k) times. Now remaining 1 operation can be 1 enqueue operation which will take O(1) time so total complexity in this case will be O(min(n,k)).

Suppose we have k=1 and do (n-1) dequeue operations then it will take k\*(n-1) time for multideqeue function and remaining one enqueue operation will take O(1) time . So in total we are getting O(kn) time in this case.

I am confused on how to handle 'k' parameter when we are calculating complexity.

**NOTE :- n queue operations can be any combination of enqueue/dequeue/multi-dequeue(as defined) operation.**

Any help would be appreciated.

# Answer
> 2 votes
It's $\Theta(n)$. Observe that if you are limited by $n$ operations, the total number of elements that ever enter the queue is less than or equal to $n$. Furthermore, every element is processed at most twice: once when it enters the queue, and once when it leaves the queue, therefore the total time is at most a constant times $n$.

---
Tags: algorithms, time-complexity
---


# Question
Title: Fast and space efficient data structure for nearest neighbors in 3 dimensions?
I am looking for data structures to answer nearest neighbor queries in 3D which are reasonably space efficient (ie use at most $O(n^{1+\epsilon})$ space) and fast ($O(n^{\epsilon})$ or $O(log^k(n))$ query time in the worst case).

As a summary of what I already know:

* 1D is trivial (just sort the points and use binary search).
* 2D is a bit trickier, but with a point location data structure + voronoi diagram you can do it in $O(n)$ space and $O(log(n))$ query time.
* In 3D and above, that solution breaks down since the Voronoi diagram of a set of points is $O(n^{floor(d/2)})$.

I am aware of approximate techniques based on kd-trees or grid based methods, though these are dependent on assuming either a uniform distribution of points or something about the distance to the nearest neighbor, and don't perform so well in all cases. I am not interested in these randomized or approximate solutions - I want something that works for any data set in the worst case. Is there anything out there that does this, or is there some lower bound which blows this idea out of the water?

# Answer
I like Drost's hierarchical voxel hashing. It has an average time complexity of $O(log(log(|D|)))$, where $|D|$ is the number of points in data cloud. While the construction is a bit more tedious, searching gets much faster.

The method is also extended to a journal version, found under this link.
> 1 votes

# Answer
Exact nearest neighbour queries in kd trees are perfectly feasible. Bentley's original paper gave an algorithm, but the better algorithm was in the follow-up paper. This is the tech report version:

Friedman, Bentley, and Finkel, *An Algorithm for Finding Best Matches in Logarithmic Expected Time*, SLAC-PUB-1549, July 1976.
> 0 votes

---
Tags: data-structures, computational-geometry, nearest-neighbour
---


# Question
Title: Minimum number of states in dfa accepting binary number with decimal equivalent divisible by $n$
I was aware of the fact that, if DFA needs to accept binary string with its decimal equivalent divisible by $n$, then it can have minimum $n$ states.

However recently came across following text:

> * **If $n$ is power of $2$**
> Let $n=2^m$, so number of minimum states $=m+1$. For $n=8=2^3$, we need $3+1=4$ states.
> * **Else If $n$ is odd**
> Number of states $=n$. For $n=5$, we need $5$ states.
> * **Else if $n$ is even**
> Keep dividing it with $2$ until you get odd quotient. The result is final odd quotient plus number of divisions done. For $n=20,20/2=10,10/2=5→5+2=7$ states

I was guessing:
**Q1.** From where all these facts came. (I know this must have come from general pattern that such DFAs follow, but then I have below doubts)
**Q2.** Are these points indeed correct?
**Q3.** If yes (for Q2), then what can be the reason for each point?
**Q4.** Do these three bullet points cover all cases? (I guess yes, since there is even and odd, but I am new to this, and I was guessing if any such more point is left unmentioned in my textbook, especially since I did not find any reference book (by Peter Linz and Hopcroft-Ullman) talking about this topic)

# Answer
> 4 votes
## Case 1: $n$ is a power of 2

If you wanted to check whether a decimal number is divisible by some power of 10, you can just look at the number of trailing zeros. For example, all numbers that are divisible by $100 = 10^2$ end with 2 zeros (this is of course including numbers ending with more than 2 zeros). The same idea can be applied here for binary numbers and powers of 2. Specifically to check for multiples of $n = 2^m$, you can simply check if the string ends in $m$ zeros. For example, if $n = 16 = 2^4$, all multiples of $n$ will end in 0000 (4 zeros). Thus we can create the following DFA for $n = 16$:

This construction can be extended to all multiples of 2, where you have $m+1$ states to ensure that your input ends in at least $m$ zeros (reading a 0 takes you one state forward, reading a 1 takes you back to the start). As suggested in the comments on your question, you can show that you can't do any better than this using a Myhill–Nerode argument.

## Case 2: $n$ is odd

The general idea here is that when a number is divided by $n$, the possible remainders are $0, 1, \ldots, n-2$ or $n-1$. We can give our DFA one state for each of these possible remainders so as we process a string, we're keeping track of the remainder of what we've read so far and transitioning to the appropriate remainder based on what character we read. Then, we accept if we finish in the remainder 0 state.

Design DFA accepting binary strings divisible by a number 'n' walks through a detailed method for constructing such a DFA, and you can find out more about this by searching for "DFA based division". This gives a total of $n$ states, which is optimal by Myhill-Nerode because these remainders are exactly the equivalence classes given by the relation $\equiv\_L$ for the language $L = \\{\text{binary strings divisible by }n\\}$.

## Case 3: $n$ is even (and not a power of 2)

The technique in case 2 also works here but it isn't optimal. Every $n$ in this case can be expressed as $2^km$ where $m$ is odd (this is the division procedure described in your question). Thus, to check whether a binary string is divisible by $n$, we check whether it is divisible by both $2^k$ and $m$.

We know that it takes $k$ states to check divisibility by $2^k$ (case 1) and $m+1$ states to check divisibility by $m$ (case 2). We can take a DFA for divisibility by $m$, unmark the accepting state and make it the start state for a DFA for divisibility by $2^k$, giving our final DFA $k+m$ states.

As an example, here's the DFA for $n = 6$:

The top three states ensure that the number is a multiple of 3, and the final accept state ensures that it is a multiple of 2.

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


# Question
Title: Number of nodes of a parse tree when the Grammar is in CNF?
There happened to be a following question -

> In any Chomsky Normal Form grammar $G$, how many nodes will all parse trees for terminal strings of length $n\>0$ generated by G have?

I tried for some examples & arrived at the answer $2^{n}+1$ but it is incorrect & obviously trying examples is not a sophisticated way. The correct answer given is $3^{n}-1.$ Can anyone explain how this answer comes?

# Answer
> 5 votes
Both of the answers are wrong. To find the correct answer, let us consider the grammar $$ S \to SA \mid a \\ A \to a $$

You can check that the tree corresponding to $S \to a$ has 2 nodes, the one corresponding to $S \to SA \to aA \to aa$ has 5 nodes, and the one corresponding to $S \to SA \to SAA \to aAA \to aaA \to aaa$ has 8 nodes. This corresponds to the formula $3n-1$ (rather than $3^n-1$, the formula you quoted).

Let us now prove that this formula is correct. The proof is by induction, where we allow varying the starting nonterminal. When $n = 1$, the derivation must be of the form $A \to \sigma$, which includes 2 nodes. When $n \> 1$, the first step must be $A \to BC$, where $B$ gives rise to a word of length $k$, and $C$ gives rise to a word of length $n-k$. The entire tree is formed from the trees corresponding to $B,C$ by adding the root, and so the total number of nodes is $$1 + (3k-1) + (3(n-k)-1) = 3n-1.$$

---
Tags: formal-grammars, parsers
---


# Question
Title: Turing Machine vs Universal Turing Machine
I am a computer science student and at the moment I am starting a new subject called models of computing.

I am trying to understand what is the difference between a Turing Machine and an Universal Turing Machine.

For what I understand a Turing Machine can be compared to a program that runs on our computer and an universal Turing machine can be compared to a computer, that can run any program.

So, a universal Turing machine can handle various Turing machines?

Thanks,

# Answer
> 2 votes
A UTM is a TM that get code of a TM and its input and return the output of the TM on the input as its output. See details here:

> a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape

# Answer
> 1 votes
By the Church Turing Thesis, a TM can represent any computable algorithm in the world, including your own Python program. So if a Python program can take as input an encoding of a 'TM' and run it, then there exists a TM (in fact a UTM) that can do exactly this. You can try to write your own UTM in Python to simulate an TM, with a lot of string parsing functions.

---
Tags: turing-machines
---