title: Achieving Randomness

text:
# Question
Title: Achieving Randomness
Can **True** *Randomness* be achieved by composing prngs in different states and with different algorithmsv(e.g. have $n$ different composition algorithms, use a prng to select any permutation of them. A lot $(\sum\_{i=1}^{n}{^nP\_i})$ of permutations exist. Compose the algorithms selected using the permutation. Whenever a new number is generated in a sequence of random numbers the entire algorithm selection process is repeated, and new seeds assigned to all algorithms.

The final result with/from the different prngs will be supplied as output.

For every new number, a fresh seed is taken to the random selection algorithm(to choose the composition of the PRNGs), this should be the most complex PRNG and have as much entropy as possible.

The sequence works something like this. Each PRNG takes two parameters; a seed, and some previous value.

For the first PRNG selected for composition, a seed $s$ is provided, and another randomly generated seed is used to generate another number $c$(This will be done by a randomly selected PRNG not in the sequence. So in actuality, we'll have $n+2$ PRNG algorithms). Each PRNG generates its own random number $k$. By choosing a permutation of some predefined composition algorithms (Whether the random number is to be floating or not, will define available composition algorithms, e.g final value $v \mod max$ will be used to arrive at the random integer) $c$ is used to modify $k$, to generate some $c\_i$ to pass to the next algorithm in the sequence. The final $c\_n$ will be adjusted to be within range as the random number.

I cannot conceive how such a system may be feasibly 'deterministic'.

Because of this, the algorithm shouldn't be philosophically deterministic. The next number is ***NOT*** based on previous numbers.

Arbitrarily designing a PRNG 'algorithm' isn't difficult (slightly modifying an existing algorithm, using different seeds to choose from, generating more than one result and choosing from it, etc). I read a post online about the security flaws of using prngs. How they are ultimately deterministic.

Will such a prng be deterministic?
Will it be able to achieve 'true' randomness?
Assuming all the prng algorithms have the same 'degree' of randomness What is the minimum $n$ I should choose to make it non-feasibly deterministic? $\tag{\*}$

My only worry now, is the computational expensiveness of such a model. It *should* have a worst case running time of $nf(n)$ where $f(n)$ is the worst case running time of the worst random algorithm. (Assuming PRNGS don't have their running time vary with their outputs) {Though the higher security, might be worth it}.

(\*) Feasible deterministic, means that if all computers in the world were connected to make a super computer (assume this is possible and performance scales accordingly) this super computer will be able to 'crack' (be able to determine the next $k$ number(s) in line given an arbitrary list of generated numbers (from the same *instance* of this algorithm $n$ and arbitrary time $m$ s.
$n,m\colon n \ge m \gt 10^{10^{100}}$
$k$'s value is irrelevant. If it can crack the next 10, then given enough time, it'll crack the next 100.

True randomness, is defined as being non feasibly deterministic.

# Answer
There are two types of answers:

* Practical: You are looking for good stream ciphers. Several exist, though we don't know for sure that they are secure.
* Theoretical: You are looking for cyptographically secure PRNGs. There are several suspected constructions, but such objects are not known to exist; if P=NP, then they don't exist.

In both cases, there is quite a wide literature on the subject.
> 6 votes

# Answer
No deterministic algorithm can produce non-deterministic output (by definition). PRNGs are deterministic algorithms, so mixing them any complicated way still produces a deterministic result.

If you want the output to be "truly random" (have entropy), you will have to get the entropy from somewhere (and a deterministic algorithm cannot create entropy) and thus have a non-deterministic algorithm/system.
> 4 votes

---
Tags: algorithms, randomness
---


# Question
Title: generation-compare-and-swap, or GCAS, in CTries
The data structure is used for example in Scala: https://github.com/scala/scala/blob/v2.12.0-M3/src/library/scala/collection/concurrent/TrieMap.scala

More details in this paper: http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf

The logic I'm confused about is on **line 139** in **Figure 11** on **page 6** of `ctries-snapshot.pdf`

The code checks if the generation of the root node is the same as the current node before proceeding. To quote the paper,

> The idea is to communicate the intent of replacing the value in the I-node and check the generation field in the root before committing to the new value

This is the last sentence of the second paragraph in section **4.1** on **page 6**. The root generation is changed for example when a snapshot is taken (**Figure 7** on **page 15**).

The question is, I don't see any synchronization mechanism that would prevent updates to the root right after the generation check. To use the papers own words, how is "the intent of replacing the value in the I-node" communicated to other threads attempting to update the root node through snapshots? From what I can tell, the root and the I-node in question can be two distinct nodes, and I'm not sure how the CAS's surrounding the generation check can prevent a race.

# Answer
> 4 votes
Nice observation.

To prevent the scenario that you are describing, the actual implementation in the Scala standard library uses a variant of the software RDCSS instruction when reading or modifying the root. Any modification of the root is only successful if the value below the main I-node did not change.

All reads of the root location are in the actual code calls to RDCSS\_READ\_ROOT:

https://github.com/scala/scala/blob/2.12.x/src/library/scala/collection/concurrent/TrieMap.scala#L694

And all CASes to the root are similarly replaced with an RDCSS. More details about this instruction in this paper:

https://timharris.uk/papers/2002-disc.pdf

I guess this important detail that you noticed (and in fact, you are maybe even the first person to notice so far, besides myself) was left out of the paper to keep the text clear.

---
Tags: synchronization
---


# Question
Title: Which part of Go(lang) is in Crystal(lang)?
Reading Crystal Programming Language They says it is inspired from many programming language and Go.

I would like too know which part of Golang, since it is not its syntax.

# Answer
> 3 votes
I simply asked @asterite, one of the developers of Crystal, at IRC #crystal-lang (the log is here).

He said the answer is CSP, the concurrency model. For example, both Go and Crystal use channels for communications.

---
Tags: programming-languages, syntax
---


# Question
Title: What is the time complexity of the piece of code given below
```
int IsPrime(n)
{
    int i, n;
    for (i=2; i<=sqrt(n);i++)
        if(n%i == 0)
            {printf("Not Prime \n"); return 0;}
    return 1;
}

```

Here the loop executes for $ \Theta (\sqrt{n}) $ time . But my teacher said that it is not because the lower bound is $ \omega (1) $ I was not able to understand why it so .

Q1\] Could some of you explain which one of us is right justifying reason ?

Q2\] What is the importance of " return 0 " ? What would have been the change if there had no " return 0 inside looping function ?

Q3\] In general What is the meaning of return 0, 1, -1 in C programming language ? I have read this from stackoverflow but that didn't solve . Need little bit explanation

# Answer
The loop executes at most $O(\sqrt n)$ times because `i` is incremented in every iteration of the loop. You claim that it is also executed at least $\Omega(\sqrt n)$ times. This is not true because it has an early exit (the `return` statement). For example for even numbers the function returns during the first iteration.

If you recall the definition of $\Omega$, we have $f(n) \in \Omega(g(n))$ if there is some constant $n\_0$ such that for all $n\>n\_0$ we have $c\*g(n) \< f(n)$ for some constant $c$. By this definition the runtime of your program can't be $\Omega(\sqrt n)$ because the loop makes only one iteration for infinitely many inputs (that is, you can't find a suitable $n\_0$).

You can of course restrict your analysis to the worst case ($n$ is a prime number). Then you are correct in saying that the runtime is $\Theta(\sqrt n)$. There is a question about the relation of $O$, $\Omega$, best and worst case in case you find this confusing.
> 4 votes

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Restrictions to counter machines capturing LBA
As you know in computation theory, there is a simple programming language equivalent in power to Turing machines. It is described as follows:

Values: natural numbers only, but of unlimited precision.

• Variables:

– Input variables X1, X2, X3, . . .

– An output variable Y

-Local variables Z1, Z2, Z3, . . .

• Instructions:

1 ) $V ← V + 1$ Increase by 1 the value of the variable V .

2 ) $V ← V − 1$ If the value of V is 0, leave it unchanged; otherwise decrease by 1 the value of V.

3 ) $ IF \\;V \neq 0\\; GOTO \\;L$ , If the value of V is nonzero, perform the instruction with label L next; otherwise proceed to the next instruction in the list.

• Labels: A1, B1, C1, D1, E1, A2, B2, C2, D2, E2, A3, . . .

• Exit label: E.

• All variables and labels are in the global scope .

for example the following program computes f(x) such that if x = 0 , f(x) = 1 otherwise f(x) = x \begin{align} \[A\] \quad &X ← X − 1 \\ &Y ← Y + 1 \\ &IF\\; X \neq 0\\; GOTO \\;A \\ \end{align} this language can use infinite number of variables.

> What restrictions should be added to this language so its power will be the same as Linear Bounded Automata? One of them is clear about the variables but I will appreciate if anybody helps me about any others, if they exist. I have searched a lot but I couldn't find any source that describes both topics. I would appreciate any relevant pointers.

# Answer
Programs with natural numbers as data and as instructions increment, decrement and zero test are know as register machines or counter automata. (Wikipedia cites several sources, usually I refer to Minsky).

Their power is that of the Turing machine, that is, they accept recursively enumerable sets (strings or numbers).

Thus they are more general than the LBA, which is more a complexity class (as mentioned in the comments). The length of the space used for computations is linear, otherwise the LBA are Turing Machines.

To translate that restriction to counter automata I would suggest to restrict the variables to at most exponential in the size (length) of the input. First, you can code such variable by markers on the tape. That would prove one inclusion. I expect that every LBA can be simulated by an exponentially bounded counter automaton, after all, the tape is just a number an writing on the tape is changing a digit. There is a standard construction that translates the two sides of the tape (right and left from the reading position) as two numbers, and moving the head is just a multiplication/division, deciding the element under the reading head is modulo counting. You need extra counters (variables) for these operations and in particular you need the zero test.
> 3 votes

---
Tags: computability, turing-machines, linear-bounded-automata
---


# Question
Title: How to Solve the following Recurrence Equation?
I wanted to Solve the following Recurrence Equation using Master Theorem and Back substitution but Im stuck at certain point . can u pls help me how to proceed further

$T(n)=T(\sqrt{n})+n+c$

**Using Master Theorem**,

put n = $2^{m}$

$ T(n)=T(2^{m})= S(m)$ ie $T(\sqrt{n}) = S(\frac{m}{2})$

Hence the Recurrence Relation will be $S(m)=S(\frac{m}{2})+ 2^{m}$

Here a =1 , b=2 $f(m)=2^{m}$

case 1 : $2^{m} \notin O(m^{\log\_b a - \epsilon })$

case 2 : $2^{m} \notin \Theta (m^{\log\_b a } \log^{k} n)$

case 3 : $2^{m} \in \Omega (m^{\log\_b a +\epsilon } )$

put $\epsilon = 1$ We get

$2^{m} \in \Omega (m^{\log\_2 1 +1 } ) \Rightarrow \Omega (m^{0+1})\Rightarrow \Omega (m)$ Which is True

Now checking Regularity

$af(\frac{m}{b})\leq \delta f(m) \Rightarrow f(\frac{m}{2})\leq \delta f(m)$

ie .$2^{\frac{m}{2}} \leq \delta \ 2^{m}$ taking log on both sides $\frac{m}{2}\leq \log\_2 \delta +m$

taking $\delta =\frac{1}{2}$

$\frac{m}{2}\leq -1 +m \Rightarrow 1 \leq \frac{m}{2} $

How to check this last condition is satisfied or not ? How to proceed from here... ?

**Using back Substitution** $T(n)=T(\sqrt{n})+n+c$

$T(n)= T(n^{\frac{1}{2}})+n+b \\ = T(n^{\frac{1}{4}})+n^{\frac{1}{2}}+n+2b \\ =T(n^{\frac{1}{8}})+n^{\frac{1}{4}}+n^{\frac{1}{2}}+n+3b \\ ... \\ .. \\ = T(n^{\frac{1}{2^{k}}})+\sum\_{i=1}^{k} n^{\frac{1}{2^{i}}} + kb$

How to Evaluate the summation ? How to proceed further... ?

please explain both the method.

# Answer
Regarding the master method, I don't quite understand why you got stuck. You had to show that the function $f(n) = 2^n$ satisfies $f(n/2) \leq (1-\epsilon) f(n)$ for some $\epsilon \> 0$ and large enough $n$. You showed this using some complicated calculation. So the condition is satisfied, and the method applies, giving the answer $T(2^m) = \Theta(f(m)) = \Theta(2^m)$. A more elementary way to check the condition is to notice that when $n \geq 2$, $$ 2^{n/2} \leq 2^{n-1} = \frac{1}{2} \cdot 2^n. $$

Regarding substitution, clearly $f(n) \geq n + c$. In the other direction, when $n \geq M$ we have $\sqrt{n} \leq n/\sqrt{n} \leq n/\sqrt{M}$, $\sqrt\[4\]{n} \leq \sqrt{n}/\sqrt{M} \leq n/M$, and so on. Therefore when $n^{1/2^{k+1}} \geq M$, $$ \begin{align\*} f(n) &= n + c + \sqrt{n} + c + \cdots + n^{1/2^k} + c + f(n^{1/2^{k+1}}) \\ &\leq n + \frac{n}{\sqrt{M}} + \cdots + \frac{n}{\sqrt{M}^k} + (k+1) c + f(n^{1/2^{k+1}}) \\ &\leq n \sum\_{t=0}^\infty \frac{1}{\sqrt{M}^t} + (k+1)c + f(n^{1/2^{k+1}}) \\ &= \frac{1}{1-1/\sqrt{M}} n + (k+1)c + f(n^{1/2^{k+1}}). \end{align\*} $$ Choosing $k$ so that $n^{1/2^{k+1}} \approx M$, we deduce that $$ f(n) \leq \frac{1}{1-1/\sqrt{M}} n + O(c\log\log n), $$ where the hidden constant depends on $M$. Choosing an arbitrary $M$, we get $f(n) = O(n)$. This implies that $$ f(n) = n + c + f(\sqrt{n}) = n + O(\sqrt{n}). $$ Combining this with the lower bound, we have $$ n + c \leq f(n) \leq n + O(\sqrt{n}). $$ This is a much better estimate than the one we got using the master theorem.
> 4 votes

---
Tags: algorithms, time-complexity, recurrence-relation
---


# Question
Title: What are the first computer science papers that used asymptotic time complexity?
When was big O first used in computer science and when did it become standard? The Wikipedia page on this cites Knuth, *Big Omicron and Big Omega And Big Theta*, SIGACT April-June 1976, but the beginning of that paper reads

> Most of us have gotten accustomed to the idea of using the notation $O(f(n))$ to stand for any function whose magnitude is upper-bounded by a constant times $f(n)$, for all large $n$.

This quote indicates that the idea and notation were already in common use.

The Wikipedia page also cites math papers from the late 1800s and early 1900s, but that doesn't quite answer the question. In particular, I've heard researchers who were around back then (in the 60s and 70s, not the late 1800s) say that when asymptotic analysis was first used, some people pushed back, saying that wall clock time was a better metric. However, no one I've talked to can cite the specific papers that got pushback like this and I'd like to find evidence that can confirm or deny these stories.

# Answer
with history questions there are typically subtle nuances and its not easy to determine a particular paper that introduced a particular concept because it tends to be spread over many contributors and is sometimes rediscovered independently when obscure early references dont necessarily disseminate (fundamental ideas are like that). but the history basically goes something like this: Landau notation is an old mathematical formalism (1894/ Bachman)\[1\] which was imported into CS as a "key concept" around the early 1970s. by the mid 1970s this was somewhat accepted as in your Knuth reference and Knuth himself was involved in spreading this concept.

interestingly its import into CS was probably closely related to the P vs NP vs Exptime distinctions uncovered in early 1970s which were highly influential/ heralded in the field. it was Cobham/ Edmonds who started to define the class P in early 1970s.\[3\] there were early proofs about Exptime and Expspace by Stockmeyer/ Meyer.\[2\] the Cook-Levin theorem\[4\] (1971) showed the core relevance of P vs NP time, immediately supported by Karp\[5\] (1972).

an early mathematician who worked in number theory but also on the edge of computer science was Pocklington. as in \[3\] it points out:

> However, H. C. Pocklington, in a 1910 paper,\[11\]\[12\] analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that did not.

another early pioneer in analyzing complexity of machine-based algorithms for number theory, ie factoring, was Derrick Lehmer, professor of mathematics at University of California, Berkeley, and built/ analyzed factoring "algorithms" (sieve based implementations) as early as the 1920s and its possible he may have described something like computational complexity wrt factoring in an informal way.\[6\]

yet another case is a "lost" 1956 letter by Godel to von Neumann talking about complexity measurements of steps *f(n)* of a machine to find proofs of size *n*.\[7\]

\[1\] Big O notation history / wikipedia

\[2\] Word problems requiring exponential time. / Stockmeyer, Meyer (1973)

\[3\] P time class history / wikipedia

\[4\] Cook-Levin theorem / wikipedia

\[5\] Karps 21 NP complete problems / wikipedia

\[6\] Lehmer factoring machine/ sieve / wikipedia

\[7\] Godels lost letter / RJLipton
> 3 votes

---
Tags: asymptotics, history
---


# Question
Title: Finding optimal set for a sum of a product function over a 2D lattice
Given a 2D lattice with coordinates $1 \leq x \leq c$ and $1 \leq y \leq d$, we define $f(x, y) = xy$.

We wish to find a boolean function $I(x,y)$ that determines in $O(1)$ time whether or not $(x,y)$ belongs to the set of points $S$ of size $k$ such that the sum $Z(S) = \sum\_{(x,y) \in S} f(x,y)$ is smaller or equal to any other set of size $k$. One may use $O(c+d+k)$ time and space to construct $I$.

Is this possible? Is this a known problem (my search turned up nothing)? Can https://en.wikipedia.org/wiki/Divisor\_summatory\_function and its approximation help us?

Motivation: I work in NLP and am trying to find an optimal way of storing part of a word-word cooccurrence matrix in memory and part on disk. This matrix is very sparse. I'm making the simplifying assumption that the probability of two works co-occurring is proportional to their unigram frequencies. By ranking words in terms of frequency, we get the $c$ and $d$ terms. So the smaller the ranks $c$ and $d$, the more likely they are to co-occur, so this value should be stored in memory. Since there will be billions of lookups, $I$ needs to be fast.

Thanks!

# Answer
The set $S$ must have the following form: there must exist a threshold $t$ such that:

* If $xy \< t$, then $(x,y)$ *is* in $S$.
* Some or all of the points $(x,y)$ with $xy=t$ are in $S$.
* If $xy \> t$, then $(x,y)$ is *not* in $S$.

Moreover, in the second bullet, it doesn't matter *which* points with $xy=t$ you put into $S$; all that matters is how many of them you put into $S$. Finally, notice that the locus of points $(x,y)$ such that $xy=t$ forms a hyperbola.

It follows that one way to parametrize the set is as

$$S = \\{(x,y) : xy \< t \text{ or } (xy=t \text{ and } x\<u)\\},$$

for some parameters $t,u$. It's clear that, given $t,u$, membership can tested in $O(1)$ time, i.e., your oracle will run in $O(1)$ time, as required.

So, we simply need to select suitable values of $t,u$ during the precomputation to construct $I$. How can we do that?

One easy way is to use binary search. Notice that it's easy to count the number of lattice points $(x,y)$ such that $xy \< t$ in $O(c)$ time: just iterate over $x=1,2,\dots,c$ and count the number of values $y$ such that $xy \< t$, i.e., such that $y \< t/x$; there are $\lfloor (t-1)/x \rfloor$ of them, so we sum that over $x=1,2,\dots,c$. Now use binary search on $t$ until you find the largest $t$ such that the number of such points is at most $k$. This gives you the value of $t$. It also gives you the number of points $(x,y)$ such that $xy\<t$; call that number $k\_0$.

Once you know the value of $t$, the next step is to choose a suitable value for $u$. We'll need to choose $u$ so that there are exactly $k-k\_0$ lattice points $(x,y)$ such that $xy=t$ and $x\<u$. Finding $u$ can be done by iterating over $x=1,2,\dots,c$; for each $x$, check whether $y=t/x$ is an integer, keep track of how many lattice points you've found, and stop once you've found $k-k\_0$ of them.

In the end, the precomputation requires something like $O(\min(c,d) \log k)$ time and the oracle can be computed in $O(1)$ time. The precomputation can probably be done even faster through implementation tricks and/or some number theory, but given your problem statement, I'm guessing this might already be good enough.
> 3 votes

---
Tags: lattices
---


# Question
Title: Optimality in multi-agent multi-target path finding
Suppose I have a regular rectangular weighted grid with multiple agents and obstacles. Agents cannot be in grid sites that contain obstacles, and for simplicity assume multiple agents can be in the same grid site.

If I select a single location on the grid and want to find the nearest agent to that location, a good solution is easy: I can simply do a breadth-first (BF) search.

However, suppose I have *n* target locations and *m*\>=*n* agents. I want to visit the target locations with *n* agents simultaneously. I do not care which agent goes to which location, but the total distance travelled must be minimal. Or, to rephrase, I'm attempting to find a distance-weighted maximum matching for two sets of nodes on a graph.

One solution would be to calculate the shortest path from all agents to all targets and then do a bipartite matching. Since the graph may be disconnected by obstacles, this could result in needless multiple sampling of the entire grid space of a connected region. This hardly seems optimal. (Solution 1)

I propose the following 'algorithm' (Solution 2):

1. from each target location start a BF search until there is one agent in every target's searched space
2. if the number of unique agents in the searched spaces is less than *n*, continue searching from all target locations
3. if a matching between targets and agents in their respective searched spaces is not possible with full target covering, continue searching from the ~~target locations where covering was not possible and all other target sites that share agents with the uncovered target sites~~ all target locations.
4. the first matching that fulfils step 3 is the solution

now I have two questions:

1. is solution 2 optimal, i.e. is it guaranteed that I will select precisely those agents with the least total distance to their assigned targets? I.e. am I not neglecting any agents by not continuing the search for long enough?
2. *if* solution 2 *is* optimal, are there any further ways of reducing the computational complexity?

# Answer
Read the following paper on the generalization of your problem with "makespan" as the objective. The proposed algorithm should work even if $m\neq n$.

H. Ma and S. Koenig. "Optimal Target Assignment and Path Finding for Teams of Agents." http://idm-lab.org/bib/abstracts/papers/aamas16a.pdf
> 2 votes

# Answer
No, your proposed algorithm is not correct: it might output a matching that is sub-optimal. Here is a counter example.

We have three agents, A, B, and C. We have three targets, T, U, and V. Here are the distances:

Distances to T: A: 1, B: 100, C: 101
Distances to U: A: 2, B: 1, C: 3
Distances to V: A: 101, B: 1, C: 100

In the first round of your algorithm, you'll discover the AT, BU, and BV distances, but no complete matching is possible, so you'll continue searching. In the second round, you'll discover the BT, AU, and CV distances. Now a complete matching is possible, and A-T B-U C-V is the minimal matching given the information so far, so your algorithm will output that assignment, for a total cost of 102. However, this isn't the optimal answer; the optimal answer is A-T C-U B-V, for a total cost of 5. So in this example, your algorithm outputs the wrong answer.

---

In general, if you have a candidate algorithm like this and you want to know whether it is correct, a good strategy is to test it with random testing. Implement your proposed algorithm, and implement a (slower) golden-reference algorithm that is known to be correct. Now generate a million random small test cases (i.e., random inputs), and run both implementations on each and check that both implementations give the same answer in all cases. If you find any mismatch, you know your algorithm is incorrect and it's back to the drawing board. If you don't find any mismatches, that doesn't prove your algorithm is correct -- but the procedure is still helpful for catching some buggy ideas.
> 0 votes

---
Tags: time-complexity, search-algorithms, shortest-path, graph-traversal, assignment-problem
---


title: A nim game variant with pass move

text:
# Question
Title: A nim game variant with pass move
This variant is almost similar to the normal nim game which states -

> Two players take turns to remove one or more items from a single, non-empty pile. The player who removes the last item from the last non-empty pile is declared as a winner.

The twist is an inclusion of a "pass" move for each non-empty pile. To make myself clear, a player can choose to pass his move on any non-empty pile on which there was no "pass" move made.

I looked up grundy numbers to solve this problem, but I do not how to add the rule of pass move.

For ex:

$G(0) = mex(empty-set) = 0$

$G(1) = mex(G(1),0) = ?$

Here`mex(g)` is a function which takes a set of non-negative integers and outputs smallest non-negative integer that is not present in the list.

For ex : `mex(0,1,2) = 3` and `mex(0,2,3) = 1`

I just don't know how to proceed. I'd appreciate some help. Also, I'd like to add that the number of piles is small say 10-15 but the number contained in each pile is quite huge. Hence those recursive backtracking type of solutions won't work.

**Update** : The pass move is not mandatory.

# Answer
> 1 votes
You have to augment each pile with an extra bit which states if it has been passed or not. Then you can compute the Grundy function as usual. For example, here are some values: $$ \DeclareMathOperator{\mex}{mex} \newcommand{\yes}{\text{Yes}} \newcommand{\no}{\text{No}} G() = \mex(\emptyset) = 0 \\ G(1,\yes) = \mex(G()) = \mex(0) = 1 \\ G(1,\no) = \mex(G(),G(1,\yes)) = \mex(0,1) = 2 \\ G(2,\yes) = \mex(G(),G(1,\yes)) = \mex(0,1) = 2 \\ G(2,\no) = \mex(G(),G(1,\yes),G(2,\yes)) = \mex(0,1,2) = 3 $$ Here *Yes* means that the pile has been passed, and *No* that it hasn't been passed.

You mention that a recursive solution won't be efficient enough. In that case, I suggest trying to find a formula for the Grundy function. Here is a hint:

> A pile which has been passed behaves like a normal pile. A pile which has not been passed behaves like a pile which is one item larger.

---
Tags: combinatorics, game-theory, board-games
---


# Question
Title: Approximation with imperfect dichotomy oracle
Given an unknown $x$ and an oracle $O(r)$ such that:

1. If $O(r)$ is true then $x \geq r$.
2. If $O(r)$ is false then $x \< 2r$.

Conversely, the oracle has a defined behaviour only outside the interval $(x/2, x\]$, and may output anything between.

We want to find a factor 2 approximation of $x$.

What is the strategy with a minimal number of calls to $O$?

# Answer
I found thanks to @YuvalFilmus 's advice! (if you want me to remove this answer and post it yourself, feel free to ask)

### 1. We find a factor 4 approximation

If we know a value r s.t. O(r/2) = True and O(r) = False, then we know that x is in \[r/2, 2\*r\[.

And for any starting point y, while O(y) = True we multiply y by 2 until we have O(y) = False, and conversely for O(y) = False to find such a value.

By the properties of the oracle, this terminates. We have a logarithmic complexity. But when evaluating $O(y \times 2^k)$ for an integer k, we know that there is an index that separates the True values from the False. Thus we can apply binary search on this logarithmic scale to have a $\log(\log(x))$ number of evaluations of the oracle.

### 2. We transform a $2^{1+\frac{1}{k}}$ approximation in a $2^{1+\frac{1}{2k}}$ approximation

Suppose you know $x\in\[a, b\[$ with $\frac{b}{a} = 2^{1+\frac{1}{k}}$.

Take $c = a * 2^\frac{1}{2k}$.

We know that if $x \in \[a, c\[$, then $O(c)$ is false, and that if $x \in \[2c, b\[$, then $O(c)$ is true.

Thus we can eliminate one interval of ratio $2^\frac{1}{2k}$, and the remaining interval is of ratio $2^{1+\frac{1}{k}-\frac{1}{2k}}$ = $2^{1+\frac{1}{2k}}$.

### 3. Complexity

We make $\log(\log(x))$ calls to the oracle in the first stage, and then $i$ to get a $2^{1+\frac{1}{2^i}}$ approximation factor.

For example, if you work with integers, the stop condition is $ x * (2^{1 + \frac{1}{2^i}} - 2) \< 1 $. A Taylor expansion gives us $i \> \log(x) + 1$ with the first term, so $i \> \log(x) + 2$ should be fine.

### 4. Other strategies

Like shown below, more evaluations per step could get us immediately better approximation factors than 2.

However, it requires too much evaluations, with no improvement in the worst case when the oracle is a threshold function.

Let $x\_1, x\_2 = \frac{r}{2}, x\_3, x\_4=b, x\_5, x\_6=2r$ be numbers in geometric progression of ratio $\sqrt2$ with $r$ found after the first stage.

We know $O(x\_2) = T, O(x\_4) = F, O(x\_6) = F$, and we know $x \in \[x\_2, x\_6\[$. We split this interval in 4 and look at the values of $O(x\_1), O(x\_3), O(x\_5)$. We note $?$ when a value can be True or False.

For $x\in\[x\_2,x\_3\[$, the possible values are $?, F, F$.

For $x\in\[x\_3,x\_4\[$, the possible values are $T, ?, F$.

For $x\in\[x\_4,x\_5\[$, the possible values are $T, ?, F$.

For $x\in\[x\_5,x\_6\[$, the possible values are $T, T, ?$.

If we get $O(x\_1) = F$ or $O(x\_5) = T$, we know a $\sqrt2$ factor approximation of x. Else, the value of $x\_3 = c$ allows us to eliminate either the leftmost or the rightmost interval, which is exactly the first step of the second stage of our general strategy to transform a $4 = 2^{1 + \frac{1}{1}}$ approximation into a $2\sqrt2 = 2^{1 + \frac{1}{2}}$ approximation.
> 3 votes

---
Tags: algorithms, search-algorithms, approximation, binary-search
---


# Question
Title: Difference between large-scale optimization and equation-based simulation
Large scale optimization (for example using AMPL) can be used to solve equilibrium systems which have components with fixed mathematical relationships. What is the difference between this and using an equation-based simulation system (like Modelica) to solve an equation-based system?

Of course, most simulations have a time variable, but you can just as well have a time variable in AMPL. Are AMPL models therefore fully analogous to equation-based simulation like MapleSim/Modelica, or is there some fundamental difference between the technologies?

# Answer
AMPL and Modelica are modelling languages, not a solver or optimization algorithm. So, you don't use AMPL or Modelica to solve some optimization problem: you express the problem in AMPL or Modelica, then you use some other solver to find the optimal solution.

AMPL tends to be used for problems that can be solved with optimization methods: e.g., linear programming, integer linear programming, quadratic programming, convex optimization, that sort of thing. Modelica seems to be used for problems that can be solved by solving differential equations or by using hybrid model-checking.

Modelica is for modelling how some continuous variables change over time. Contrary to what you wrote, there's no simple way to model in that in AMPL by "adding a time variable". To put it another way: Modelica lets us model, say, the position of a component as a function of time. This is a function $f(t)$. AMPL lets us model, say, the position, as a fixed continuous value. This is a value $x$. Adding a second variable $t$ still doesn't give you any way to model a *function* of $t$.

So, the two approaches are for modelling different kinds of problems; and typically they're used with different kinds of back-end solvers, which use different techniques. They're not interchangeable.

Disclaimer: This is all based on my (rather limited) understanding of these systems.
> 2 votes

---
Tags: optimization, simulation
---


title: Building cycle in rectangle

text:
# Question
Title: Building cycle in rectangle
I have to build a cycle with fixed length $n$ that includes exactly $k$ corners inside $w$ x $h$ rectangle.

For example:
$w = 5\\h=3$

$n = 12\\k = 6$

I have already found out that I need at least $4$ corners and number of corners and number of non-corner elements needs to be even number.

Then I write an recursive algorithm that runs in exponential time complexity, but I have a strong feeling that this thing can be done much faster.

Problem is that I do not know which square will definitely be in the cycle so I run my algorithm on first $\frac w2$ fields to cover all chances, but I am aware that I search some branches multiple time.

I have also discovered that if the cycle exist it will start with corner in (0, 0) or corner in (0, 1)

Does anybody have an idea on how to speed this thing up?

Have a nice day!

# Answer
> -1 votes
your problem looks inherently exponential to me to find all the solutions. a rough sketch to show that is to create a large # of similar-looking objects. the objects are the same under translation and rotation. they (apparently?) can also be scaled. so in a rough sense there is no way to "speed it up" if you already have an exponential time algorithm. you ask for a better algorithm but also ask for general ideas. here are some ideas/ suggestions.

* youve abstracted the problem but it might help to step back and describe the background that inspired it. is it from some field in particular? chances are there are papers that study the general area.
* it looks like its in NP because its easy to verify solutions. think of solving it in terms of NP. a canonical problem in this area is the satisfiability problem. many problems have been converted to it and SAT solvers are "state of the art" for solving NP problems. SAT solvers can discover and handle the intrinsic symmetries in the problem not technically "efficiently" (in the sense of guaranteed P time) but in the "most efficient way known" based on heuristics, "best practices", and decades of optimization research/ theory. so consider translating it to SAT and studying it that way.
* if you want a general idea of the algorithm behavior you can run it at different scales and graph the # of solutions to find basic scaling properties.
* if you just want *any* solution, you might try a probabilistic approach where you lay down a simple starting shape say square/ rectangle and then randomly alter it until it gets closer to your requirements. see eg heuristics. genetic algorithms are also good for this. you can encode the shape in terms of genetic coding.
* imagine a triangular shape that has 2 straight sides at right angles and then a 3rd that is diagonal and has any # of corners required. its not an "efficient" use of space because it has a large open area but it satisfies your criteria and can be created at any scale with arbitrary # of corners. you didnt specify any criteria about minimizing or maximizing space inside or outside. so maybe this is a bit underconstrained as stated.
* actually think this might need to be described better. are you touching squares only at the edges squares and the squares touching those edge squares? what do you mean by "corners"? corners on your object? corner squares on the rectangle? you give only one example so think your description is somewhat ambiguous or subject to misinterpretation on closer inspection.

---
Tags: algorithms, graphs, searching
---


title: Why theorem proving is hard?

text:
# Question
Title: Why theorem proving is hard?
Every time I ask why most people think that P ≠ NP, I get a response like "because theorem proving is harder than proof checking".

From this, I understand that proving theorems is hard. But why is this? In fact, it is known that a *theorem*, in mathematics, is a statement that *has been proved* on the basis of previously established statements. So *a not proven theorem* would not be called a theorem, would it? I mean, a theorem is easy to prove because it is defined to be so and people call it theorem because they know how to prove it, no? If we were talking about *conjectures*, I would have not asked this question.

When I was looking, I found this paper: Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. But this seems to confuse me furthermore.

I am sure I am missing something (maybe some obvious one). Would you please clarify this?

# Answer
> 7 votes
> So a not proven theorem would not be called a theorem

No, it's usually called a proposition, or a conjecture.

> I mean, a theorem is easy to prove because it is defined to be so and people call it theorem because they know how to prove it, no?

Just because you know a proof exists doesn't mean that you can efficiently find that proof.

> From this, I understand that proving theorems is hard

The thing is, there is no mathematical evidence that it's hard, other than the repeated failures of people to prove that it's easy. But of course, the failures of people to prove that it's hard acts as evidence that it's easy.

When people say that proving theorems is harder than checking them, they are speaking from intuition. From a complexity theory standpoint, there is no evidence that proving theorems is harder than verifying them. If there were, we would be able to resolve $P$ vs $NP$. Any guesses one way to the other are just that, guesses.

There is, however, an analogy, from computability theory.

When people are talking about proving versus checking for $P$ vs $NP$, they usually mean things like SAT or Constructive Propositional Logic, or other such systems with no quantifiers, or restricted quantifiers. But if we extend proofs to include predicate logic, with $\forall$ and $\exists$, then we have a firm result: checking proofs of these is decidable, and generating such proofs is undecidable. This is a basic consequence of the undecidability of the halting problem.

---
Tags: complexity-theory, terminology
---


# Question
Title: How to compare two circular sequences in linear time?
We have two circular sequences, which means there is no start or end in the sequences, how to test if two sequence are equal or not in linear time? I have two circular sequences of E. Coli bacteria with length (4,639,221). I thought about attaching two sample of the first sequence and find the other one in it in linear time, but I was looking for a better idea, using a suffix tree is a suggestion that I think works for this problem.

# Answer
> 4 votes
Start with computing the lexicographlcally least circular substrings$^1$ of the both circular sequences and then compare them directly.

Alternatively you can check for the substring $A$ (the first seqience) in the string $BB$ (a concatenation of $B$, the second sequence) circular sequence with itself) using for example the KMP$^2$

You might also be interested in the application of the Suffix Trees (also Suffix Arrays) and this thesis reviewing the applications to DNA sequences.

$^{\[1\]}$(described in *K. S. Booth. Lexicographically least circular substrings. Inf. Process. Lett., 10(4/5):240-242, 1980.*, and here
$^{\[2\]}$(Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt, SIAM J. Comput., 6(2), 323–350. *Fast Pattern Matching in Strings*

# Answer
> -2 votes
Start in first list with a ptr with 1X speed and the second list with 2X speed. They meet at a point after some time if they both are the same lists. From then on, you can check if each of their nodes are the same. This is linear in time.

If they dont meet, they are not the same circular lists.

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


# Question
Title: Running Time of naive implementation of Dijkstra's Algorithm
Here is the "naive" implementation of Dijkstra's algorithm that the professor uses:

> For a directed graph $G = (V,E)$ as input
>
> Initialize:
>
> * $X = \\{s\\}$ (the vertices processed so far)
> * $A\[s\] = 0$ (computed shortest path distance)
> * $B\[s\] = empty path$ (computed shortest path)
>
> Main Loop:
>
> While $X \neq V$:
>
> * Among all edges $(v,w) ∈ E$ with $v ∈ X$, $w \notin X$, pick the one that minimizes $A\[v\] + \ell\_{vw}$, where $\ell\_{vw}$ is the length of the edge between $v$ and $w$. Call this edge $(v^\*,w^\*)$ .
> * Add $w^\*$ to $X$.
> * Set $A\[w^\*\] = A\[v^\*\] + \ell\_{u^\*w^\*}$.
> * Set $B\[w^\*\] = B\[v^\*\] \cup \\{(v^\*w^\*)\\}$.

The running time for this is given as $O(nm)$, where $n = |V|$ and $m = |E|$. I don't fully understand why. He says $n$ is the number of loop iterations, which I understand, but that $m$ is the work per iteration (a linear scan through edges to compute the minimum). But if it's doing $m$ work per iteration, that would imply that it's looking *at every single edge in the graph*, when it should only be looking at edges that cross the "frontier" between $X$ and $V - X$. Can someone clear up my confusion?

# Answer
> 2 votes
In each iteration we need to go over all edges crossing the cut $(X,V\setminus X)$. The algorithm doesn't explain how we do that, so it is difficult to analyze the exact running time, though $O(m)$ per iteration is definitely an upper bound. A naive implementation will presumably go over *all* edges, checking which of them cross the cut, and for this implementation, the running time will indeed be $\Theta(m)$ per iteration.

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


title: Does deterministic imply algorithmic?

text:
# Question
Title: Does deterministic imply algorithmic?
I'm not exactly sure whether this question belongs to this SE or not, but it doesn't seem to fit elsewhere.

Say a process behaves in a deterministic fashion (that is, it gives the same output when an input is entered over and over again), then **can we build it as an algorithm?**; if not, can you think of a counter-example?, that is, a deterministic process which can't be modeled as an algorithm.

# Answer
> 6 votes
An algorithm must have a finite description, whereas a deterministic process according to your definition can use an infinite lookup table. For example there is a deterministic process that solves the halting problem for Turing machines, but there is no such algorithm.

# Answer
> 3 votes
No. Deterministic, to me, means that the state of a system at any given point in time is a function of its state at any previous point in time. So all one needs to show a difference is an example of a system that evolves according to a function that isn't computable. For instance encode programs as Godel numbers. The state of a system at any given point in time (where time is discrete) is 0 if the represented program halts and 1 if it loops. This is an example of a discreet deterministic system (all be it an abstract non-physical one). It's also easy to find examples of non-discreet deterministic systems that can't be computed.

I'm not sure if there is some example that can be pulled from physics or not. Quantum systems themselves can be simulated but there might be properties of them that can't be computed there from. I know of something called the "spectral gap problem" but I'm not sure how that plays into your answer *and* moreover you might not call a quantum system "deterministic" because of how measurements work in quantum systems.

Another possible, but more philosophical, definition of deterministic would be the lack of presence of free will which you might think a quantum system qualifies as. But I don't think that's what you were looking for.

---
Tags: algorithms
---


# Question
Title: Getting a tighter upper bound on the following function
We have the following function which determines the Nth fibonacci number:

```
int fib(int n){
    if(n<=0) return 0;
    else if (n==1) return 1;
    return fib(n-1)+ fib(n-2)

}

```

Find the time complexity

I am currently reading the book "Cracking the coding interview" and the answer it gave is quite disappointing. The book says that there are 2 branches per call, and we go as deep as N, therefore the runtime is $O(2^N)$ and it later explains that a tighter upper-bound is $O(1.6^N)$, but it doesn't go over it because the mathematics are "very complex. It doesn't even point out the place where we can find the approach to get the desired upper-bound. I don't want to defame "cracking the coding interview", but I think that more consistency must be shown. My question is, how do we get $O(1.6^N)$ for the algorithm?. It doesn't look like top notch math.

# Answer
Let's count how many times we have to make a call into `fib` for each value of `n`. Let's call that number $f(n)$.

Then:

$$ \begin{align} f(0) &= 1 \\ f(1) &= 1 \\ f(n) &= 1 + f(n-1) + f(n-2) \qquad \textrm{(for $n \> 1$)} \end{align} $$

The first several values for $f$ are then 1, 1, 3, 5, 9, 15, 25, 41, 67, etc.

It turns out that if you add one to $f$ and half the result,(\*) you get the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.

That is, $f(n) = 2\cdot\textrm{fib}(n+1) - 1$

Since it is well known that the Fibonacci function is $O\left((\frac{1+\sqrt{5}}{2})^n\right)$, so is $f(n)$.

Note that since $\frac{1+\sqrt{5}}{2} \approx 1.618 \> 1.6$, the book is actually technically incorrect when it says that $O(1.6^N)$ is an upper bound, and should be corrected to say $O(1.62^N)$ or something similar.

---

(\*) Okay, I kind of pull that out of a hat. As for how to mentally jump from a recursion that's almost like one you know but off by a constant (as in this case, the recursion formula for $f$ looked like the recursion for `fib` but had that annoying $1+$ at the beginning) one technique is to say:

"What if $g$ were something that obeyed `fib`'s recursion rule, and $f(n) = g(n) + C$ for some constant $C$. What happens when I substitute that into my recursion equation?"

You then end up with:

$$ g(n) + C = 1 + g(n-1) + C + g(n-2) + C $$

Using $g(n) = g(n-1) + g(n-2)$, you find that $C$ is $-1$. From that you see "Oh, $1+f(n)$ should look kind of like the Fibonacci series, but it starts with "2, 2", so..." (and then it's straightforward to write a formula for $f(n)$).
> 3 votes

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


title: Average runtime of naive primality test

text:
# Question
Title: Average runtime of naive primality test
The naive prime test goes something like this:

```
is_prime(n):
  for(i=2; i<=sqrt(n); ++i):
     if n mod i == 0 :
       return false
  return true

```

If $n$ is prime the loop runs for $\sqrt(n)$ iterations. I was wondering what the "average" runtime is. It is of course troublesome to define this properly, because there is no uniform distribution on the natural numbers, so I don't know whether this question actually makes sense or not. My intuition is that "most" numbers have relatively small divisor and prime numbers are relatively rare.

Maybe the following definition works: Let $f(n)$ be the number of loop iterations necessary for testing the first $n$ numbers using the above function. What is a good upper bound for $f(n)/n$?

# Answer
> 2 votes
Better suitable for math.stackexchange.com.

It is quite widely known that about n / ln (n) numbers are primes, so you get $n^{1/2}$ iterations in about n / ln (n) cases.

You can try to figure out how often you have more than $n^{1/3}$ iterations: That happens if there is no prime factor less than $n^{1/3}$, and therefore the number is either prime or the product of two primes. So you either have a prime, and there are about n / ln n of those, or you have a product of two primes, that is a product of one prime p from $n^{1/3}$ to $n^{1/2}$, and one prime from p to n/p, and there only about (n/p) / ln (n/p) of those.

All other numbers take less than $n^{1/3}$ iterations.

---
Tags: number-theory, primes
---


# Question
Title: Balance factor changes after local rotations in AVL tree
I try to understand balance factors change after local rotations in AVL trees. Given the `rotate_left` operation:

```
  x            y'
 / \          / \
a   y   =>   x'  c
   / \      / \
  b   c    a   b

```

and $b(x)$, $b(y)$ - balance factors for $x$ and $y$ nodes - I want to find $b(x')$ and $b(y')$.

In my reasoning I will use the Iverson bracket notation, that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise: $$ \[P\]=\begin{cases} 1, \text{ if } P \text{ is true}; \\ 0, \text{ otherwise}.\end{cases} $$

Balance factor for the node $x'$ can be calculated like this: $$b(x') = h(b) - h(a)$$

where $h(b)$ and $h(a)$ - the heights of sub-trees $a$ and $b$.

Let's substitute $h(b) = h(y) - b(y)\[b(y) \> 0\] - 1$ and $h(a) = h(x) - b(x)\[b(x) \> 0\] - 1$:

$$b(x') = (h(y) - b(y)\[b(y) \> 0\] - 1) - (h(x) - b(x)\[b(x) \> 0\] - 1)$$

Some simplification:

$$b(x') = h(y) - b(y)\[b(y) \> 0\] - h(x) + b(x)\[b(x) \> 0\]$$

Now substitute $h(y) = h(x) + b(x)\[b(x) \le 0\] - 1 $:

$$b(x') = h(x) + b(x)\[b(x) \le 0\] - 1 - b(y)\[b(y) \> 0\] - h(x) + b(x)\[b(x) \> 0\]$$

Obviously, $\[b(x) \le 0\] + \[b(x) \> 0\] = 1$:

$$b(x') = h(x) + b(x) - 1 - b(y)\[b(y) \> 0\] - h(x)$$

Simplify again:

$$b(x') = b(x) - b(y)\[b(y) \> 0\] - 1$$

In the same way I can find balance factor for $y'$. Skipping intermediate steps I get: $$ b(y') = h(c) - h(x') =\\ ...\\ = b(x) + b(y)\[b(y) \le 0\] - b(x')\[b(x') \> 0\] - 2$$

Somehow I have feeling that this is not the simplest formula for balance factors.

Is there any simpler approach to calculate balance factors, which would always work even if the tree becomes unbalanced?

**EDIT**:

The simplest formulas I managed to get look like this (see my own answer for details): $$b(y′)=b(y)+b(x')\[b(x')\le0\]−1$$ $$b(x′)=b(x)−b(y)\[b(y)\>0\]−1$$

# Answer
> 5 votes
**EDIT:**
@Maxym's answer is correct after all and is actually equivalent. I had simply misinterpreted the notation. Leaving this answer anyway as the cited link provides a useful explanation.

While @Maxym's answer is on the right track, his formula didn't quite work for me. After beating my head against the wall for quite some time, I found this link written by Brad Appleton that seems to be the right formula (at least my unit tests all work now and my tree stays coherent): http://oopweb.com/Algorithms/Documents/AvlTrees/Volume/AvlTrees.htm

Using Maxym's notation, it would be something like this for the left rotation (also I reversed the order -- since the formula for the new y depends on the new x, it makes sense to me to list x first):

$$b(x′) = b(x) − 1 - max(b(y), 0)$$ $$b(y′) = b(y) - 1 + min(b(x′), 0)$$

And for the right rotation:

$$b(x′) = b(x) + 1 - min(b(y), 0)$$ $$b(y′) = b(y) + 1 + max(b(x′), 0)$$

In case that page goes away, I'm including the relevant portion:

> **Calculating New Balances After a Rotation**
>
> To calculate the new balances after a single left rotation; assume we have the following case:
>
> ```
>          A                                     B
>         / \                                   / \
>        /   \                                 /   \
>       a     B           ==>                 A     c
>            / \                             / \
>           /   \                           /   \
>          b     c                         a     b
>
> ```
>
> The left is what the tree looked like BEFORE the rotation and the right is what the tree looks like after the rotation. Capital letters are used to denote single nodes and lowercase letters are used to denote subtrees.
>
> The "balance" of a tree is the height of its right subtree less the height of its left subtree. Therefore, we can calculate the new balances of "A" and "B" as follows (ht is the height function):
>
> `NewBal(A) = ht(b) - ht(a)`
>
> `OldBal(A) = ht(B) - ht(a) = ( 1 + max (ht(b), ht(c)) ) - ht(a)`
>
> subtracting the second equation from the first yields:
>
> `NewBal(A) - OldBal(A) = ht(b) - ( 1 + max (ht(b), ht(c)) )
>  + ht(a) - ht(a)`
>
> canceling out the ht(a) terms and adding OldBal(A) to both sides yields:
>
> `NewBal(A) = OldBal(A) - 1 - (max (ht(b), ht(c)) - ht(b) )`
>
> Noting that max(x, y) - z = max(x-z, y-z), we get:
>
> `NewBal(A) = OldBal(A) - 1 - (max (ht(b) - ht(b), ht(c) - ht(b)) )`
>
> But ht(c) - ht(b) is OldBal(B) so we get:
>
> `NewBal(A) = OldBal(A) - 1 - (max (0, OldBal(B)) )
>  = OldBal(A) - 1 - max (0, OldBal(B))`
>
> Thus, for A, we get the equation:
>
> `NewBal(A) = OldBal(A) - 1 - max (0, OldBal(B))`
>
> To calculate the Balance for B we perform a similar computation:
>
> `NewBal(B) = ht(c) - ht(A)
>  = ht(c) - (1 + max(ht(a), ht(b)) )`
>
> `OldBal(B) = ht(c) - ht(b)`
>
> subtracting the second equation from the first yields:
>
> `NewBal(B) - OldBal(B) = ht(c) - ht(c)
>  + ht(b) - (1 + max(ht(a), ht(b)) )`
>
> canceling, and adding OldBal(B) to both sides gives:
>
> `NewBal(B) = OldBal(B) - 1 - (max(ht(a), ht(b)) - ht(b))
>  = OldBal(B) - 1 - (max(ht(a) - ht(b), ht(b) - ht(b))`
>
> But ht(a) - ht(b) is - (ht(b) - ht(a)) = -NewBal(A), so ...
>
> `NewBal(B) = OldBal(B) - 1 - max( -NewBal(A), 0)`
>
> Using the fact that min(x,y) = -max(-x, -y) we get:
>
> `NewBal(B) = OldBal(B) - 1 + min( NewBal(A), 0)`
>
> So, for a single left rotation we have shown the the new balances for the nodes A and B are given by the following equations:
>
> `NewBal(A) = OldBal(A) - 1 - max(OldBal(B), 0)`
> `NewBal(B) = OldBal(B) - 1 + min(NewBal(A), 0)`
>
> Now let us look at the case of a single right rotation. The case we will use is the same one we used for the single left rotation only with all the left and right subtrees switched around so that we have the mirror image of the case we used for our left rotation.
>
> ```
>          A                                     B
>         / \                                   / \
>        /   \                                 /   \
>       B     a           ==>                 c     A
>      / \                                         / \
>     /   \                                       /   \
>    c     b                                     b     a
>
> ```
>
> If we perform the same calculations that we made for the left rotation, we will see that the new balances for a single right rotation are given by the following equations:
>
> `NewBal(A) = OldBal(A) + 1 - min(OldBal(B), 0)`
> `NewBal(B) = OldBal(B) + 1 + max(NewBal(A), 0)`

# Answer
> 4 votes
I found the answer myself. We know that $$b(x)=b(x')+b(y)\[b(y)\>0\]+1$$ $$b(y′)=b(x)+b(y)\[b(y)\le0\]−b(x′)\[b(x′)\>0\]−2$$ thus $$b(y′)=b(x')+b(y)\[b(y)\>0\]+1+b(y)\[b(y)\le0\]−b(x′)\[b(x′)\>0\]−2$$ where $$b(x')−b(x′)\[b(x′)\>0\]=b(x')\[b(x')\le0\].$$ So, the new balance factors will look like this: $$b(y′)=b(y)+b(x')\[b(x')\le0\]−1$$ $$b(x′)=b(x)−b(y)\[b(y)\>0\]−1$$

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


title: Who needs linearizability?

text:
# Question
Title: Who needs linearizability?
I've been reading about the differences between **serializability** and **linearizability**, which are both consistency criteria for replicated systems such as replicated databases. However, I don't know in which cases linearizability would be needed, even though it's stronger than serializability.

Could you come up with scenarios where such strong property would actually be necessary?

# Answer
> 6 votes
Consider the design of concurrent, wait-free (or lock-free, which is weaker) data structures. In this scenario, linearizability is generally required, even though in some cases, performance and scalability can be improved by satisfying a weaker correctness condition. Whether an implementation satisfying such a weak condition is useful is usually application-dependent. In contrast, a linearizable implementation is always usable, because designers can view it as atomic.

Moreover, linearizability is a non-blocking property: a total operation (defined for all object states) is never required to block. Instead, Serializability is not a non-blocking property. Therefore, in order to increase the degree of concurrency, designers of concurrent data structures always rely on linearizability.

# Answer
> 13 votes
I've reread Herlihy and Wing many times over the past 15 years. It is a very difficult read. And that is unfortunate, because while there are some subtleties around the edges the basic idea is actually quite reasonable.

In short: linearizability is like serializability, but with the additional requirement that the serialization respect additional ordering constraints between the transactions. The goal is to allow you to reason rigorously about an individual atomic data structure rather than having to reason about the entire system all at once.

Linearizability is also easy to achieve: just associate a mutex with the object you want to linearize. Every transaction on that object starts by locking the mutex and finishes by unlocking the mutex.

Here are the definitions I'll use:

> A system is *serializabile* if given a set of transactions over a set of data, any result of executing the transactions is the same as if the *transactions* were executed in some sequential order, and the operations within each transaction are contained within their transaction in the order specified by the transaction's code.

Serializability disallows the appearance of interleaving of operations between different transactions, and requires that the chosen ordering of transactions satisfies causality (if transaction A writes the value x, and transaction B reads the value x that A wrote, then transaction A must precede transaction B in the chosen serial order.) But it says nothing about any other constraints on the ordering of transactions (in particular, it says nothing about *processes* and the order in which processes perceive events.)

There is another related idea that does add in the constraints about the order in which processes executed operations (but doesn't talk about transactions only individual read/write operations):

> A system is *sequentially consistent* if the result of any execution is the same as if the operations of all the processes were executed in some sequential order, and the operations of each individual process appear in this sequence in the order specified by its program. (Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", *IEEE T Comp* 28:9(690-691), 1979).

Implicit in the definition of sequential consistency is that we only accept sequential orders where for each memory location (object) the induced sequential order of operations obeys the rule that *the value returned by each read operation to location `x` must be the same value that was written by the immediately preceding write operation to location `x` in the sequential order.*

Linearizability has the good intentions of (a) combining together the notion of transactions (from serialization) with the notion that processes expect the operations they issue to complete in order (from sequential consistency) and (b) narrowing the correctness criteria to talk about each object in isolation, rather than forcing you to reason about the system as a whole. (I would like to be able to say that my object's implementation is correct even in a system where there are other objects that are not linearizable.) I believe Herlihy and Wing may have been trying to rigorously define a *monitor*.

Part (a) is "easy": A sequential consistency-like requirement would be that the transactions on the object issued by each process appear in the resulting sequence in the order specified by the program. A serialization-like requirement would be that the transactions on the object are all mutually exclusive (can be serialized).

The complexity comes from objective (b) (being able to talk about each object independently of all the others).

In a system with multiple objects it is possible that operations on object B place constraints on the order in which we believe operations were invoked on object A. If we are looking at the entire system history then we will be constrained to certain sequential orders, and will need to reject others. But we wanted a correctness criteria that we could use in isolation (reasoning just about what happens to object A without appealing to the global system history).

For example: suppose I am trying to argue about the correctness of object A, which is a queue, suppose object B is a memory location, and suppose I have the following execution histories: Thread 1: A.enqueue(x), A.dequeue() (returns y). Thread 2: A.enqueue(y), A.dequeue() (returns x). Is there an interleaving of events that would allow this implementation of the queue to be correct? Yes:

```
Thread 1                           Thread 2
A.enqueue(x)                       ...
...                                A.enqueue(y)
...                                A.dequeue() (returns x)
A.dequeue(y) (returns y)           ...

```

But now what if the history (*including object B*) is: B starts with value 0. Thread 1: A.enqueue(x), A.dequeue() (returns y), B.write(1). Thread 2: B.read() (returns 1) A.enqueue(y), A.dequeue() (returns x).

```
Thread 1                           Thread 2
A.enqueue(x)                       ...
A.dequeue() (returns y)            ...                       (uh oh!)
B.write(1)                         ...
...                                B.read() (returns 1)
...                                A.enqueue(y)
...                                A.dequeue() (returns x)

```

Now we'd like our definition of "correctness" to say that this history indicates that either our implementation of A is buggy or our implementation of B is buggy, because there is no serialization that "makes sense" (either Thread 2 needs to read a value from B that hasn't been written yet, or Thread 1 needs to dequeue a value from A that hasn't been enqueued yet.) So while our original serialization of the transactions on A seemed like a reasonable one, if our implementation allows a history like the second one, then it is clearly incorrect.

So the constraints that linearization adds are quite reasonable (and necessary even for simple data structures like FIFO queues.) They are things like: "your implementation should disallow dequeue() a value that won't be enqueued() until some time in the future." Linearizability is quite easy (and natural) to achieve: just associate a mutex with your object, and each transaction starts by locking and ends by unlocking. Reasoning about linearizability starts to get tricky when you are trying to implement your atomicity with non-blocking or lock-free or wait-free techniques instead of simple mutexes.

If you are interested in some pointers to the literature, I found the following (although I think the discussion about "real-time" is one of the red-herrings that make linearizabilty more difficult than it needs to be.) https://stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability

# Answer
> 4 votes
First, linearizability and serializability are not directly comparable. As the table below shows, the main difference is that on the left hand side, all individual operations are atomic (like having a java `synchronized` around each op. On the right side, the unit of atomicity is a transaction; an individual operation is not atomic. Which is why Serializability has always been a part of the database literature, while the left-hand side has been the subject of processor-memory literature (read/write op is atomic). The original Key-Value stores (such as dbm and memcached) started off on the left hand side (get/put is atomic), but newer ones are increasingly supporting transactions (such as Google's spanner).

```
obj. operations are atomic      |  Transactions are atomic
--------------------------------+---------------------------------
Linearizability                 |
Sequential Consistency          |    Serializability
Causal Consistency              |
Cache Consistency               |

```

Linearizability requires that a system of objects in a concurrent setting must behave identical to a sequential system that handles one operation (a request/response pair) at a time -- in a parallel universe -- in such a way that (a) the clients in both universes see exactly the same responses (b) temporal order is preserved (more on this below).

The definition of Serializability, like Sequential Consistency, only requires the first criterion.

Temporal order preservation means this: if A:x.op1() (A is a client, x is an object, and op1 is an operation) finished before another operation B:y.op2() started, then in the sequential universe the requests are handled in the same order. This isn't required in Sequential Consistency (SC); the object is allowed to queue up a client's request, respond to the client, then evaluate it later. Further, the object may handle a later request from some other client out of turn, evaluating it before getting to the first one.

Non-preservation of temporal order is a problem. After A:x.op1(), suppose A picked up the phone and told B about it, then B called x.op2() call. There is no way for the system to know about this causal chain of events, since the second step involved a message not tracked by the system. In many real cases, it is not unreasonable for A to assume that once x had responded to it, B's invocation can rely on the updated state. If temporal order was not preserved, A and B are in for a surprise. This wouldn't happen in a linearizable system.

The second nice property of temporal order preservation is locality and compositionality, that a system built of linearizable objects is itself linearizable. So, instead of having one monolithic key-value store, you can shard it into many separate partitions each managed by its own KV-store server; if each of them is linearizable, the whole database functions as one linearizable monolithic KV store, with no extra effort.

---
Tags: concurrency, databases
---


title: Are DFAs unique?

text:
# Question
Title: Are DFAs unique?
For a given regular is expression, once we construct a deterministic finite automaton: is that automaton unique for that expression? In a sense, that no other DFA (different number of vertices or transitions) can be constructed from that same regular expression.

# Answer
For every regular language there are *infinitely many* DFAs accepting the language. You can always add dummy states not reachable from the initial state, for example.

However, there is a unique DFA which has the minimum number of states, called the *minimal automaton* (or some such name). This is part of Myhill–Nerode theory.
> 12 votes

---
Tags: finite-automata
---


# Question
Title: Is detecting easy instances of NP-hard problems easy?
My question is the following. Assume that $\Pi$ is an NP-hard problem. Given an arbitrary instance $I$ of $\Pi$ and assume that an adversary knows that this instance is easy to solve, is it possible to find a deterministic polynomial-time algorithm to solve this particular instance $I$?

For example: Suppose that $\Pi$ is GRAPH COLORING. The adversary gives you a graph $G$ with $n$ vertices.

1. The adversary knows that $G$ is complete but you don't. Can you find a polynomial-time algorithm that says "This graph is colorable with $\Delta +1$ colors"?
2. The adversary knows that $G$ has some property $P$ but you don't. Can you find a polynomial-time algorithm that says "This graph is colorable with $b$ colors"?
3. ...

# Answer
The problem isn't really well-posed. For any particular instance, there is a single solution, say $S$. Consequently, we can imagine an algorithm that has the answer $S$ hardcoded in: no matter what input you give it, all it does is just print $S$. This answer counts as a deterministic polynomial-time algorithm that solves this particular instance $I$.

Therefore, the answer to your question is "Yes", but for uninteresting reasons. It's possible you might need to think more about how to formulate your question to match what you really want to know.

---

The final part of your question is actually a bit different. It doesn't ask about a single instance $I$. Rather, it asks about a *special case* of the problem, i.e., an infinite family of instances that is a proper subset of all possible instances for $\Pi$. In that case, the answer is "it depends"; some special cases might remain NP-hard, and others might be in P.

Finally, I don't know what it means to say "The adversary knows X but you don't". I'm free to write an algorithm that assumes X is true and only works when X is true. "Knowledge" is a funny thing and not well modelled by the kinds of tools you seem to be talking about; complexity theory is more about "existence" than "knowledge".
> 17 votes

# Answer
In some sense, the answer to your question is affirmative, due to Levin's universal search algorithm. Consider for concreteness graph coloring, and a particular class of easy instances. As a witness that this class is easy, you have an algorithm which, given a graph in this class, produces (in polynomial time) a legal coloring together with a polynomial size proof that the coloring is optimal.

Levin's universal search algorithm runs all polynomial time algorithms on its instance (this is achieved by trying all possible polynomial time bounds for each algorithm), checking whether they provide a legal coloring together with an optimality proof. On any class of easy instances, this algorithm runs in polynomial time. Unfortunately the constants will be huge, so this algorithms isn't practical.
> 7 votes

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


# Question
Title: How the closure properties of the formal languages dictate decidability of their problem
Consider the following problem:

> Is $L\_1 * L\_2$ is of $LType$?
>
> where we know that both $L\_1$ and $L\_2$ are of type $LType$ and $LType$ is closed under $\*$ operation.

Above, by $LType$, I mean any type of language that is known to belong to any type of Chomsky hierarchy. So it may be regular (Chomsky Type 3), CFL or DCFL (Chomsky Type 2) etc. Also by operation $\*$, I mean any binary operation that results in another language, say intersection $\cap$, union $\cup$, difference $-$ etc.

Given all these pre-information of the type of languages and their closure under the specified operation, is the above problem decidable? For example

> Does the problem:
>
> > "Given that $R\_1$ and $R\_2$ are regular, is $R\_1 \cap R\_2$ too a regular language?"
>
> is decidable, especially when we know that regular languages are closed under intersection?

Also can we comment in the same manner about undecidability of operation when we know that the type of operand languages is not closed under that operation? That is

> Does the problem
>
> > Is $L\_1\*L\_2$ is of $LType$?
>
> is undecidable?, especially when we know that $LType$ is not closed under the operation $\*$ and that $L\_1$ and $L\_2$ are of type $LType$?

For example

> Does the problem
>
> > Is $CFL\_1\cap CFL\_2$ is CFL?
>
> is undecidable?, especially when we know that CFLs are not closed under intersection.

I feel both of above facts are correct/obvious/intuitive. But I am confused because no book on the theory of automata states it clearly.

# Answer
If a family $\mathcal F$ of languages is closed under some operation, say intersection, then you are right that it is decidable whether the intersection of any two particular languages from $\mathcal F$ also belongs to $\mathcal F$. The answer is always *Yes*.

The converse, however, isn't true. Consider the family $\mathcal F\_m$ of all regular languages which are accepted by some DFA having at most $m$ states, for some parameter $m$. When $m \> 1$, this language family isn't closed under intersection, but given any two languages from $\mathcal F\_m$ (in any reasonable encoding), it is decidable (depending on the encoding, efficiently) whether their intersection belongs to $\mathcal F\_m$.
> 1 votes

---
Tags: formal-languages, automata, undecidability, decision-problem, chomsky-hierarchy
---


# Question
Title: Calculate $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ maximizes
I have two datasets $A$ and $B$:

$A = \\{1, 5, -34, 34.34323, -23.5444, 9.43, ....\\}$ $B = \\{-0.5, 44, -0.243, -3455, 2.22221, -23.23, ....\\}$

Those datasets contain a big amount of "random" numbers (They are actually not random, but their source does not matter for this question). Both datasets always have the same size.

Now I need to calculate two numbers $(u,v) \in \mathbb{R}$ so that $\sum (a\_i + b\_i)$ with $ a\_i \geq u$ and $b\_i \geq v$ reaches the biggest possible value.

For clarification: Say $a\_3 \geq u$ but $b\_3 \< v$. Then $(a\_3 + b\_3)$ is **not** included in the sum. That is meant by $ a\_i \geq u$ and $b\_i \geq v$.

Does an algorithm for the solution to this problem already exist? If not, I am open for ideas.

# Answer
For each pair of elements, $(a\_{i},b\_{i})$, you can calculate the sum of all the $(a\_j+b\_j)$ where $a\_{j}$ and $b\_{j}$ are both greater than or equal to $a\_{i}$ and $b\_{i}$. So an algorithm could look like:

```
largest_pair = 0
largest_value = -∞
for each i:
    for each j:
        total = 0
        if(a[j] >= a[i] & b[j] >= b[i])
            total += a[j] + b[j]
    if(total>largest_value)
        largest_value = total
        largest_pair = i
u = a[largest_pair]
v = b[largest_pair]
output u,v

```

This algorithm is $O(n^2)$ but is easily adaptable to n-variables, and there should be some shortcuts that could speed it up
> 4 votes

# Answer
This algorithm can be solved in $O(n \log^2 n)$ time. The basic approach is to use Aidan Connelly's algorithm, except we'll speed up the inner loop so the inner loop takes only $O(\log n)$ time instead of $O(n)$ time. The solution involves a sweepline algorithm, persistent data structures, and other tricks.

---

**Prefix sums.** First, as a warmup, let's note that we can build a data structure that given a set $Y=\\{y\_1,\dots,y\_n\\}$ of points supports the following operations:

* PrefixSum($y$): given $y$, return $\sum\_{y\_i \ge y, y\_i \in Y} y\_i$.
* Insert($y$): given $y$, add it to the set $Y$ of points stored in the data structure.

I'll show how to perform both queries in $O(\log n)$ time.

In particular, we can store the points $Y$ in a balanced binary search tree with each point $y\_i$ in a leaf of the tree. We store numbers in the nodes of the tree. Initially, each leaf receives a number corresponding to the point stored in it, and each internal node is 0.

When we run Insert($y$), we insert a new leaf for the point $y$ (in the correct location, so the leaves are in sorted order), then we find a collection of disjoint subtrees whose union is the set of leaves $y\_i$ where $y\_i\<y$, and add $y\_i$ to the root of each of those subtrees. Notice that any such consecutive interval of leaves can be covered by $O(\log n)$ disjoint subtrees, so the Insert operation runs in $O(\log n)$ time.

To answer PrefixSum($y$), we sum all the numbers on the path from the root to the leaf for $y$ and return that sum. Since it's a balanced tree, this also runs in $O(\log n)$ time.

---

**Persistence.** Now we can turn this data structure into a (partially) persistent data structure, using standard path copying techniques.

Now, given a version number (timestamp) $t$ and a number $y$, we can compute the answer to PrefixSum($y$) for version $t$ of the data structure. This can be done in $O(\log n)$ time. Also, we can perform the operation Insert($y$) on the latest version ($t$), obtaining a new version ($t+1$), in $O(\log^2 n)$ time. After doing $n$ inserts, the final data structure will have size $O(n \log n)$.

---

**Sweepline.** Now, let's apply this infrastructure to your problem. Assume the points $(a\_i,b\_i)$ are sorted first by increasing $a\_i$ and then ties resolved by increasing $b\_i$. We'll sweep leftwards, from $(a\_n,b\_n)$ to $(a\_1,b\_1)$; when we visit $(a\_i,b\_i)$, we'll perform Insert($b\_i$) into the persistent data structure at that time. Let's think of $a\_i$ as the "version number" for the persistent data structure: given $a\_i$, we can find the version of the data structure right after $(a\_i,b\_i)$ was processed.

Notice that given any $a\_j$ and any $b\_k$, we can now look up the version corresponding to $a\_j$ and perform the PrefixSum($b\_k$) operation. This will return the value of $\sum\_{a\_i \ge a\_j, b\_i \ge b\_k} a\_i + b\_i$. This operation takes $O(\log n)$ time. So, we can just do this operation $n$ times, once for each pair $a\_j,b\_j$ that appears in the original list, similar to Aidan Connelly's algorithm.

How long does this take? Sorting the data can be done in $O(n \log n)$ time. Building the persistent data structure takes $O(n \log^2 n)$ time, as we perform the Insert operation $n$ times and each instance takes $O(\log^2 n)$ time. Finally, we perform $n$ PrefixSum lookups, each of which takes $O(\log n)$ time, so that stage takes $O(n \log n)$ time. The total running time is thus $O(n \log^2 n)$ time.

---

**General remarks.** This technique of combining persistent data structures and a sweepline method is a useful one in computational geometry problems, especially when working in 2D. See also Using persistence on a constant database and What classes of data structures can be made persistent?.
> 2 votes

---
Tags: algorithms
---


title: Dwarves color their houses

text:
# Question
Title: Dwarves color their houses
The dwarves of the Black Forest live in houses that are each painted either red or blue. Some dwarves are friends, and some aren’t. Every so often, a dwarf will think about repainting his house. To decide whether to repaint, he looks at the colors of his friends’ houses. If his house is red, but more of his friends live in blue houses than in red houses, then he will paint his own house blue. On the other hand, if his house is blue, but more of his friends live in red houses than in blue houses, then he will paint his own house red. Prove that after some point in time, no dwarf ever paints his house again.

Here is my attempt: This problem can be modeled by a graph. The vertices of the graph represent the houses and there is an edge between two vertices if the dwarves of the houses represented by the vertices are friend with each other. The problem then translate to coloring the vertices with two colors. If the graph has no cycle then it is a tree, then we can look at the leaves of the tree and color them and go one layer up and color the nodes according to how many children node has the majority of colors and so on. However, what happen when there is cycle in the graph?

# Answer
Your problem is known as *majority dynamics*. It is known that under rather general conditions, the behavior converges to a fixed point or to a cycle of length 2. Presumably in your case the rules are such that cycles of length 2 cannot happen. Try adapting the proof method in Goles and Olivos.
> 3 votes

# Answer
Since the problem is not well defined otherwise, I will assume the dwarves are a finite number.

If all dwarves repaint their houses at the same time, then as Evil pointed out, your thesis could be false (think of an isolated simple cycle of even length where the colors are alternated).

If on the other hand only a single dwarf repaints his house at any given time, your problem has an elementary solution.

Let $G=(V, E)$ be your graph. For each $u, v \in V$ let $\phi : V \times V\rightarrow \\{1, -1\\}$ be $1$ if $u, v$ are adjacent and have the same color, $-1$ if they are adjacent but differently colored, and $0$ if they are not adjacent.

We observe that a node $u$ may only change color if $$ \sum\_{v \in V} \phi(u, v) \lt 0 $$

Therefore, the quantity $$ \Phi = \sum\_{u,v \in V} \phi(u, v) $$

is strictly increasing. Since the graph is by hypothesis finite in size, there can only be finitely many changes of colors.
> 3 votes

---
Tags: graphs
---


# Question
Title: Finding longest chain in poset in subquadratic time
Let $(A,\leq)$ be some finite poset. For $a,a' \in A$ we can determine in constant time whether or not $a \leq a'$. The *height* of an $A$ is by definition the greatest $n$ such that there are elements $$ a\_0 \< a\_1 \< \cdots \< a\_n $$ of $A$. By treating $(A,\leq)$ as a directed acyclic graph, we can determine the height of $A$ as the length of the longest path in this graph, which we can compute in linear time in the size of the graph; that is, in $\mathcal O(|A|^2)$.

Can we do any better for this special case where $A$ is a poset?

Edit: if it matters, I am especially interested in the case where the length of the longest path is already known to be significantly shorter than the size of $A$.

# Answer
> 3 votes
Well, start by observing that

when A has no comparable pairs, the height will be 0
and
when A has one or two comparable pairs, the height will be 1

.
Thus, when  $\leq$  is given with one bit for each ordered-pair of distinct elements,
even promised-to-be-at-most-1 height will have
co-nondeterministic query complexity  $(|\hspace{.02 in}A|\hspace{-0.03 in}\cdot \hspace{-0.03 in}(|\hspace{.02 in}A|\hspace{-0.04 in}-\hspace{-0.05 in}1))\hspace{.02 in}/\hspace{.02 in}2$
and probabilistic query complexity  $\Theta$$\left(\hspace{-0.02 in}|\hspace{.02 in}A|^2\right)$ .
Accordingly, we can only hope for better when  $\leq$  is given in some other way,
like as a list of the pairs for which it's true or as

an $A$-indexed array of ordered-pairs of lists, such that for each element $a$ of $A$,
$a$'s left list is the $a'$ such that  $a' \< a$  and $a$'s right list is the $a'$ such that  $a \< a'$

.
(I currently have no clue regarding the complexity for such representations of  $\leq$ .)

For your case of interest:
See this question and its answer.
(That answer's universe size is your n and that answer's n is your  $|\hspace{.04 in}A|$ .)

However, that negative result does not necessarily apply to
"the case where the length of the longest path is already known to be" short.

---
Tags: algorithms, complexity-theory, partial-order
---


title: Game tournament program, NP complete?

text:
# Question
Title: Game tournament program, NP complete?
I have been trying to find a solution both theoretical and practical to my problem but I just can't. The question is you have **x** players that should play some rounds **y** of games in groups of **4**. Now if a player was in a game with somebody else, he is not allowed to be ever again with that player in the same group. Now the question is give **n** groups that satisfy this conditions. With **n** being maximal amount of possible groups.

My first approach was to just take a player put him into a group, now for the next player check the array already\_played\_with\_players of the first player for the second player if he's not in add him and add the players he played with to the already\_played\_with\_players array. Proceed so too for the next two players. Then mark these 4 players as in a group and take the next player out of the pool and so on.

This is not some educational question, but a real world problem. I would like to organize a game tournament, but so that people meet new people and don't play with the same people again. I already ask multiple people mathematicians, physicians, computer scientist, but the solution was not really evident to anybody. So I was wondering if the problem is NP-complete? I know I would need to find a reduction from another NP-complete problem to my problem to prove that, but I don't even know how to formalize my problem exactly.

# Answer
> 6 votes
Your problem has been solved by Brouwer in 1979 in his paper Optimal Packings of $K\_4$'s into a $K\_n$. Quoting from his paper, let $$ J(2,4,v) = \begin{cases} \lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor - 1 & \text{if } v \equiv 7 \text{ or } 10 \pmod{12}, \\ \lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor & \text{otherwise}. \end{cases} $$ The maximal number of groups when there are $v$ players, denoted $D(2,4,v)$, is equal to $J(2,4,v)$ unless $v \in \\{9,10,17\\}$, in which case $D(2,4,v) = J(2,4,v)-1$, and unless $v \in \\{8,11,19\\}$, in which case $D(2,4,v) = J(2,4,v)-2$.

The more general case in which every pair can appear at most $\lambda$ times has been solved by Assaf in his paper The packing of pairs by quadruples.

---
Tags: np-complete
---


# Question
Title: How would one prove the pigeonhole principle with a SAT solver?
Suppose I wanted to find a proof of the pigeonhole principle or show that no proof shorter than $L$ exists. I understand that proof-checking is in NP, so I could write a CNF formula that is satisfiable iff. such a proof exists. What I want to know is, how exactly would one do that? I understand I would assume a set of axioms about sets or something and also the axioms of first-order predicate calculus, and probably also modus ponens and stuff... but how exactly does one do something like this? Can anyone give a construction of such a CNF formula? References to papers or general explanations would be appreciated.

# Answer
> 6 votes
SAT solvers work in the *propositional calculus*, and usually accept as input a formula in *conjunctive normal form*. There are several different propositional variants of the pigeonhole principle; they are all contradictions, and the actual pigeonhole principle is their negation. One of them, which states that there is a one-to-one mapping from $\\{1,\ldots,n\\}$ to $\\{1,\ldots,n-1\\}$, is described in page 2 of this book extract (apparently Jukna's *Extremal Combinatorics*), where you can also find an exponential lower bound for refuting the pigeonhole principle in the resolution proof system.

(Reiterating, to prove that there is no one-to-one mapping from $\\{1,\ldots,n\\}$ to $\\{1,\ldots,n-1\\}$, we instead refute the formula stating that such a mapping does exist.)

SAT solvers are (almost) all based on the DPLL procedure (with some hacks such as clause learning), and so when they refute a statement, their transcript can be converted to a resolution refutation. Therefore the lower bound mentioned above shows that SAT solvers will have a hard time refuting the pigeonhole principle.

---
Tags: reference-request, logic, satisfiability, first-order-logic, proof-assistants
---


title: removing write protection

text:
# Question
Title: removing write protection
I tried to format my 32 GB SanDisk pendrive. But it showed me that " the disk is write protected" . I tried using CMD but it failed. I can't format it even using safe mode. Please help me to recover from this issue

# Answer
Making the supposition that you are using Windows and the drive doesn't have a physical switch, you can use diskpart to remove write-protection. Open a command prompt (cmd) as administrator and type in the following, pressing enter after every line.

```
cmd> diskpart
diskpart> list disk
diskpart> select disk x
diskpart> attributes disk clear readonly

```

Obviously, omit the cmd\> and diskpart\> before each command, and replace x on the third command with the disk number from the second one.

P.S. This isn't the correct section for this question and your problem could have been resolved by a simple Google search
Source
> -1 votes

---
Tags: computer-architecture
---


# Question
Title: Modifications to speed up the AKS primality proving
It is clear that AKS primality proving is the newest one, but as the results show it is not the fastest one.

When I try the 9 digits long prime number it consume about 6 minutes to give you the result.

Are there any modifications to make it faster for large random primes in size above 200 digits?

The problems in the AKS are:

1. Euler phi function
2. Binomial congruence

# Answer
There are a number of modifications, but none of the improvements I'm aware of will get it remotely close to the speed of ECPP or APR-CL. For random 100-digit primes, the times for the fastest codes I'm aware of are:

* 246 days (estimated) AKS v6 paper
* 45 hours (estimated) AKS Bernstein + Voloch + Bornemann
* 2.6 hours AKS Bernstein theorem 4.1
* 0.042 seconds APR-CL (WraithX 1.1)
* 0.04 seconds APR-CL (Pari/GP 2.7.0)
* 0.029 seconds ECPP (ecpp-dj 1.03)
* 0.20 seconds ECPP (Primo 4.1.0 single thread)

At 500 digits, ECPP and APR-CL are in the 9-15 second range. AKS would take years, albeit we could trivially parallelize or distribute it.

I haven't seen anything that gives better improvements than Bernstein's 2003 paper while not being a complete rework such as adding randomization. The growth rate in practice comes out to $O(\log^{6.03} n)$ (there's almost certainly more than 0.03 variance in measurements, but the point is that it's very close to the ideal exponent of 6). Ricky points out that Lenstra Jr. and Pomerance are still actively publishing theoretical improvements, tightening the proven exponent.

The time taken at more than very small input sizes is almost entirely in the congruence test. There really should be very little time spent selecting the 'r' and 's' parameters, though it's possible to see it be non-trivial. For the congruence tests, Bernstein has a paper describing some of the methods that can be used to speed this up, and the implementations shown above use binary segmentation in GMP, as he suggests. You can see the implementation I used for timing at https://github.com/danaj/Math-Prime-Util-GMP/blob/master/aks.c, with various algorithms available.

There isn't any reason to use AKS in practice at any input size, given open source implementations of more efficient algorithms, not to mention Primo for use on large inputs. ECPP gives certificates as well, which is a huge advantage.
> 1 votes

---
Tags: reference-request, number-theory, primes
---


title: Learning dynamics

text:
# Question
Title: Learning dynamics
I recently learned about Q-learning, a reinforcement learning technique that directly estimates the expected value of taking an action in a state.

I'm wondering if there exists techniques to do "dynamics learning", in order to estimate the dynamics of a system. A "dynamics learning" agent might choose actions which help it estimate the state transition function, or to estimate parameters of some known transition function.

For example, a "dynamics learning" agent in the cart-pole system would discover a function that approximates the equations of motion of the cart-pole. Or, the agent might know these equations, but not parameters of the system, like the inertial moment of the pendulum or the mass of the cart.

What techniques are there to do "dynamics learning"?

# Answer
> 4 votes
There are three issues. First, you must choose a class of models for the dynamics. Second, you must construct a training set, by taking the agent down different trajectories to explore the state space. Third, you need a way to learn/infer a particular dynamics model from this training set. There are different ways to instantiate each of these tasks.

In robotics, one common choice is to use a Markov decision process (MDP) for the dynamics model. This is a convenience choice, because there are relatively standard ways to learn a MDP from a training set, and because given a MDP dynamics model it is well-studied how to construct a controller for the system that takes the dynamics into account. Another option is to use a higher-order Markov decision process or a partially observable Markov decision process, but those can be much more unwieldy to work with.

There are many ways to explore the state space. Chapter 3.1 of Pieter Abbeel's PhD thesis has a nice overview as of 2008.

To infer/learn a MDP given a training set, you can use maximum likelihood estimation. More sophisticated techniques are also possible; see Abbeel's PhD thesis for an overview this as well (Chapters 3 and 4).

More generally, see the literature on system identification from the field of control theory.

---
Tags: machine-learning, physics
---


title: Equivalence of PDA and a counting PDA

text:
# Question
Title: Equivalence of PDA and a counting PDA
Lets define a counting PDA as equivalent to a PDA except that the transition relation can use the stack size.

Formally, let's define the transition relation as $\Delta:Q\times (\Sigma \cup \\{ \epsilon \\}) \times (\Gamma\cup\\{\epsilon\\})\times \mathbb{N} \to P(Q\times (\Gamma\cup \\{ \epsilon \\}) )$

Meaning that $(q,\beta) \in \Delta(r,\sigma, \alpha, n)$ means that when the automaton is in state r reading the symbol $\sigma$, the head of the stack contains $\alpha$ and we have n items in the stack, then we can remove $\alpha$ and insert $\beta$ and transition to q.

My question is whether the family of automata created by this definition of a counting PDA is equivalent to family of PDAs.

# Answer
Nope. A counting PDA is more powerful than a PDA... even more powerful than a Turing machine. It can recognize undecidable languages.

Proof: Let $L \subseteq \\{1\\}^\*$ be an undecidable *unary* language. It's easy to build a PDA that pushes one symbol on its stack per symbol on the input tape. Then the height of the stack fully encodes the input word. Thus its final transition can in one step decide whether the input word is in $L$, by "encoding" $L$ fully into the transition relation $\Delta$.

In retrospect, this is perhaps not too surprising. A counting PDA is not physically realizable. A PDA has a finite description. A Turing machine has a finite description. A counting PDA does not. Thus, it's not too surprising that it might be more powerful.

Or, to put it another way, because they have a finite description, there are only countably many PDA's and only countably many Turing machines; but there are uncountably many counting PDA's. As a result, it's not surprising that there exists a language accepted by a counting PDA that isn't accepted by any PDA (or any Turing machine) -- for this not to be the case, there would have to be some enormous equivalence among counting PDAs that map the uncountably many counting PDAs to only countably many languages.

---

How do we know there exists an undecidable unary language? Well, let $L\_2 \subset \\{0,1\\}^\*$ be any ordinary undecidable language in binary. Now map each word $x \in L\_2$ to its unary encoding; this gives you a unary language $L\_1$. Then $L\_1$ must be undecidable too (because the mapping is computable). For instance, the binary word $110$ maps to the unary word $1^6$, since $110$ is the binary representation of 6. (Strictly speaking, we must adjust the encoding slightly, to make sure that $110$ and $0110$ don't map to the same thing, but that's easy to fix up.)
> 4 votes

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


# Question
Title: What does pre-, post- and in-order walk mean for a n-ary tree?
The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and right child. If it can be used for n-ary trees, how?

An n-ary tree has 1 parent and n children at any given node. Where n can be any whole number for each node.

Please use the figure below to explain this, if you need one.

# Answer
No, it's not limited to binary trees. Yes, pre-order and post-order can be used for $n$-ary trees. You simply replace the steps "Traverse the left subtree.... Traverse the right subtree...." in the Wikipedia article by "For each child: traverse the subtree rooted at that child by recursively calling the traversal function". We assume that the for-loop will iterate through the children in the order they are found in the data-structure: typically, in left-to-right order, for a diagram such as you have shown.

In fact, this is already described in the Wikipedia article on tree traversals: see https://en.wikipedia.org/wiki/Tree\_traversal#Generic\_tree, which describes exactly how to generalize this to $n$-ary trees. Pre-order traversal is one where the pre-order operation is "Display the current node" and the post-order operation is "Do nothing". Post-order traversal is one where the pre-order operation is "Do nothing" and the post-order operation is "Display the current node".

In-order traversal is a special case. It probably only makes sense for binary trees. While there are several different possible ways that one could define in-order traversal for $n$-ary trees, each of those feels a bit odd and unnatural and probably not terribly useful in practice. So, it's probably best to think of in-order traversal as being specific to binary trees; if you want to do something akin in-order traversal for a $n$-ary tree, you'll need to decide exactly what you mean by that, as there's no standard meaning for that.
> 12 votes

# Answer
There are many exotic data structures used all over CS with many variants. There was some similar recent question (now deleted) about traversing n-ary trees in an ordered way by `overexchange`. It appears that most or many n-ary trees in the literature studied tend not to be ordered. However, as an alternative pov / exceptional / "edge" case on the other detailed answer, there are cases of ordered n-ary trees that are not "odd and unnatural and probably not terribly useful in practice". Here is one ref; there are likely many other cases, although it's possible they are not in widespread use.

\[1\] n-ary ordered trees / P Mateti 7140 course notes
> 0 votes

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