title: prove/disprove regularity of languages

text:
# Question
Title: prove/disprove regularity of languages
Let $L\_1 \in REG$ and $L\_2 \notin REG$ prove or disprove:

$\forall L\_1 ,L\_2 \text{ } $ $\text{ }L\_1^C \cup L\_2\in REG \lor L\_2\setminus L\_1\in REG$

I think that it may be disproved, but I found it very hard to disprove, because:

if $L\_2 \subseteq L\_1$ then $L\_2\setminus L\_1 = \emptyset$

and if $L\_1 \subseteq L\_2$ then $ L\_1^C \cup L\_2 = (L\_1 \cap L\_2^C)^C = (L\_1 \setminus L2)^C = \Sigma ^\* $

and if $L\_1 \cap L\_2 = \emptyset$ then $ L\_1^C \cup L\_2 = L\_1^C$

and in any other scenario, any counter-example that I tried to construct was too complicated to disprove the regularity of both languages.

I know that at least one of the languages must be not regular, and I proved it.

# Answer
Let $\Sigma=\\{0,1\\}$ and denote by $|w|\_1$ the number of occurrences of $1$ in $w \in \Sigma^\*$. Pick $L\_1 = \\{w \in \Sigma^\* \mid |w|\_1 \equiv 1 \pmod 2\\}$ and $L\_2 = \\{0^n1^n \mid n \ge 0\\}$.

Suppose that $L' = L\_1^C \cup L\_2$ was regular. Then a necessary condition for $L'$ to be regular is for $L^{(1)} = L' \setminus L\_1^C = L\_2 \setminus L\_1^C = \\{ 0^{2k+1}1^{2k+1} \mid k \ge 0 \\}$ to be regular.

Moreover, let $L^{(0)} = L\_2 \setminus L\_1 = \\{ 0^{2k}1^{2k} \mid k \ge 0 \\}$.

Both $L^{(1)}$ and $L^{(0)}$ are not regular. Suppose towards a contradiction that at least one of them, say $L^{(i)}$, was regular and let $p$ be any even integer that is not smaller than the the pumping length of $L^{(i)}$. Consider the word $0^{p+i}1^{p+i} \in L^{(i)}$. By the pumping lemma we know that there is some choice of $1 \le k \le p$ such that $0^{p+i-k} 0^{kh} 1^{p+i} \in L^{(i)}$ for every integer $h \ge 0$. Picking $h=0$ yields $0^{p+i-k} 1^{p+i} \in L^{(i)}$ but this is a contradiction.
> 2 votes

# Answer
First note that the statement is somewhat artificially made complex, probably to muddle the solution.

The languages considered are $L\_1^C \cup L\_2$ and $L\_2 \setminus L\_1 = L\_2 \cap L\_1^C$. Now replace $L\_1$ by its complement, and we obtain $L\_1 \cup L\_2$ and $L\_1 \cap L\_2$.

In order to find a counter example it suffices to find a regular $L\_1$ and a nonregular $L\_2$ such that both their union and intersection are nonregular.

Assume the alphabet is $\Sigma= \\{0,1\\}$. Choose any non-regular language $L\subseteq \Sigma^\*$. Then let $L\_2 = \Sigma \cdot L$, which means that both $0{\cdot}\Sigma^\* \cap L\_2$ and $1{\cdot}\Sigma^\* \cap L\_2$ are irregular, as they are basically two disjoint copies of $L$ within $L\_2$.

Now consider $L\_1 = 0{\cdot} \Sigma^\*$.
> 2 votes

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


# Question
Title: Calculating path for most efficient use of consumable items?
What concepts or technologies can help me with the following problem?

You have a finite inventory of resources and a list of recipes to convert a set of resources into another resource (IE "crafting" in a video game). Given that data I would like to compute an optimal path to a goal of a set of resources. For example, you have 30 items which at the end of crafting you want to end up with 5 highly complex items which may take multiple "hops" to achieve. What is the optimal recipe order to get there?

The closest concepts I can think to this are a dependency graph or scheduling algorithm but my research hasn't been helpful to deal with the consumable aspect of the resources. I imagine this is a solved problem as it is at the root of most construction jobs.

Any terms that I can Google to help me on my way. I'll be using Python or JavaScript for my project so any libraries that come to mind would be helpful too!

# Answer
> 1 votes
This should be solvable with integer linear programming.

Let me assume that you can borrow resources from someone if you need to, as long as you pay them back fully. Then it can be expressed in a particularly clean way as integer linear programming.

Suppose there are $d$ resources; then the current state of your inventory can be represented as a vector $v \in \mathbb{Z}^d$ that counts how many of each resource you have (negative means you owe that many). Also, each recipe can be represented as a vector $r \in \mathbb{Z}^d$ as follows: $r\_i \> 0$ means that this recipe creates $r\_i$ many copies of resource $i$; $r\_i \< 0$ means that this recipe consumes $-r\_i$ many copies of resource $i$.

Let $v\_0$ denote your original inventory. Your goal is to find a sequence of recipes so that the inventory becomes $v$, satisfying some constraint (such as that $v\_7 \ge 1$ and $v\_9 \ge 1$, if you want to end up with at least one of resource 7 and 9). If $r\_1,\dots,r\_k$ are the available resources, it turns out this problem is equivalent to trying to find integers $x\_1,\dots,x\_k \in \mathbb{Z}$ such that $x\_i \ge 0$ and

$$v = v\_0 + \sum\_{i=1}^k x\_i r\_i$$

satisfies the constraint. Notice that $v\_0$ and $r\_1,\dots,r\_k$ are known, so the final inventory $v$ can be expressed as a linear function of $x\_1,\dots,x\_k$. Now if the constraint on $x$ can be expressed as linear inequalities (as it can in your situation), then this is an instance of integer linear programming: we want to find $x\_1,\dots,x\_k$ that satisfy the linear inequalities.

So, you could create this linear programming instance, then use an off-the-shelf ILP solver to solve it. The solution will tell you how many times to apply each recipe.

There is one potentially undesirable aspect of this approach: the sequence of recipes may temporarily leave with an inventory $v$ where you have a negative number of some resource. If you're allowed to borrow resources, you can think of this as representing a borrowed resource, and it's no problem; you can add the constraint $x\_i \ge 0 \forall i$ on the final inventory, and that ensures that you'll be able to return all borrowed resources.

However, if you have no way to borrow resources, then the problem is trickier. You can solve it by introducing $k$ variables per time step, indicating which one of the recipes you apply in that time step. However, this blows up the size of the integer linear program by a factor of the number of steps needed, which might make the ILP solver significantly slower. You'd have to try it to see if it achieves acceptable performance in your setting. I don't know if there is a better solution -- it seems like there ought to be one, but I don't know.

---
Tags: graphs, scheduling
---


# Question
Title: Can databases use data structures/algorithms to respond to arbitrary queries?
Let's say that I am interested in discovering the smallest 5 numbers in a set of numbers.

In SQL, this would work:

```
select number
from (
    select number,
        row_number() over(order by number asc) as order_
    from my_table
) ranking
where order_ <= 5;

```

Alternatively, I could use the Quickselect algorithm (in my language of choice), to solve this problem, returning data in O(N) time.

Is the SQL engine using a similar optimum/near-optimum algorithm to solve this problem? Here is an execution plan in a SQL Server 2017 DB:

My interpretation is that it's taking a brute-force approach (read data, sort, compute `order_`, filter). With a non-clustered index on `number`, the table scan switches to an index scan, but otherwise, it's still the same operation.

Are there examples of databases (SQL or otherwise) where

1. The database is aware of specific patterns of queries and tries to use a data structure/algorithm to respond to the query (similar to how a human would handle it)?
2. The database provides options for humans to nudge the engine towards specific types of algorithms/data structures?

What prevents us from being able to describe queries and have a database engine figure out a near-optimal approach to solve the query?

I have a feeling that I am glossing over practical challenges that an RDBMS actually robustly handles. For instance, ACID compliance, handling data that won't fit in memory, etc make it indispensable. Implementing a binary-tree data structure + traversal on data that doesn't fit in RAM might be too niche and too complex to be useful in a general setting?

# Answer
Full disclosure: I've written the sort subsystem for a commercial database server, albeit not a SQL one.

Database servers will use every trick you can think of, and a lot you haven't thought of, to speed up operations such as sorting. But it can only do so much if you give it an overly complex query.

Query optimisers are not magic, any more than compilers are. A compiler could, in theory, optimise `sin(x)*sin(x) + cos(x)*cos(x)` to `1.0`, but most would agree that detecting cases like this is not a good use of a compiler developer's time. Similarly, you should think very hard about how you sort XML documents by title; you don't want to have to parse the XML on every SELECT query.

You could have expressed the query like this (apologies for the capital letters; I'm in the habit for SQL):

```
SELECT number
FROM my_table
ORDER BY number asc
LIMIT 5;

```

This is *much* simpler, and it gives the query optimiser more to work with. I'd be very interested in seeing what plan you got.

Query optimisers never work in a vacuum. They always take into account whatever context they can. So, for example, if `my_table` is a small table, then the optimiser will often reason, quite correctly, that it should just do a dumb thing with low constant factors.

Assuming that isn't the case, then with the simplified query, a modern DBMS will probably take an approach like this:

* If there is an index on the `number` field, it will try very hard to use an index scan. The query will then take *sublinear* time in the size of the table. I encourage you to try it. This is probably the number one thing you can do if you need high performance on a query of this kind.
* Otherwise, it will likely implement it with a single pass over the table, using a 5-element min-heap to form the result set. Like quickselect, this is still linear in the size of the table, but it's "quickheap" instead.
> 6 votes

# Answer
No, your database will not detect the semantics of your query.

What they *do* do, and in excruciating depth, is do their darndest to execute your query as fast (or as efficient, depending on settings) as possible. Also, these kinds of operations are the bread and butter of the DB - everything from the hardware level up will be optimized fully to perform these operations as quickly as possible within the RDBMS.

In your particular case, there is no conceivable way for the RDBMS to do it differently. There is no generic syntax for specifying a "quickselect"-like operation in SQL. In other cases, sub-queries can and routinely are optimized together with their parents, but due to your construction with the analytic function (which you presumably picked like this for the purpose of this question, it is a little more complex than needed), I would not expect the RDBMS to figure it out.

Still. The big carrot for doing it in SQL instead of in your code is that this saves you from transferring an arbitrarily large amount of data over a possibly slow network - and not only the network, but the full stack ending behind the DB library of your application, in your actual code, including coding and recoding, validation etc.. This alone is, in my experience, almost always worth it for significant amounts of data (and for insignificant amounts it usually doesn't matter either way).

While the operation is $O(n\log n)$ in the DB, the constants may still make it faster or even *much* faster than $O(n)$ in your application, if it takes long to transfer all the data to it. Especially if you start scaling - imagine not only having to transfer lots of data to one application, but to many - you can easily hit a network bottleneck which is out of your control to remove; while bottlenecks on your RDBMS server are usually much more under your control (or you can throw indexes, materialized views etc. at the problem, restructure your SQL, optimize RAM usage and so on).

On your concrete questions:

> The database is aware of specific patterns of queries and tries to use a data structure/algorithm to respond to the query (similar to how a human would handle it)?

No, it cannot usually sense complex patterns. But what they do have are the so-called "statistics" - i.e., histograms about the contents of their tables and indexes. Each time the RDBMS needs to process a SQL statement, it creates an "execution plan" which takes all these statistics, and of course also all available algorithms, data structures and such into account.

In the distant past, RDBMS would instead use rule-based plans which were pretty stupid. But with the statistics-based approach, if all goes well (and for regular statements on a well-tuned system, that's mostly a given in a modern RDBMS) then at the end of the day it comes up with a solution equal or better to what a human can do, simply because it usually has more information.

Exceptions to that rule are where good DBAs or DB-centric devs shine and make their money.

> The database provides options for humans to nudge the engine towards specific types of algorithms/data-structures?

Sure. At least the RDBMSses I know (foremost Oracle) give the human a plethora of options; both through creating specialized indexes and other structures, and through setting different options on all the data structurs; through tuning system settings (relative sizes of RAM buffers for different things; different weights on preferring certain algorithms or solutions); and finally through so-called "hints" in individual SQL queries with a non-SQL meta-language.

> What prevents us from being able to describe queries and have a database engine figure out a near-optimal approach to solve the query?

Nothing is preventing us, and that is the way it should work. That's what SQL is all about - while one may naively assume that SQL is an instruction of how to work, it is most definitely not. A RDBMS is free to interpret it and plan the actuall work in whichever way it sees fit, and the art is to formulate the SQL in a way which is letting the execution planner do its job (i.e., to avoid something like in your example which pretty much shoe-horns it into a specific, non-optimal solution), but then to get out of its way.
> 2 votes

---
Tags: algorithms, database-theory
---


# Question
Title: what are meta variables in this static analysis book's explanation about types?
At page 21 of this book: https://cs.au.dk/~amoeller/spa/spa.pdf I found this:

I started reading everything and understanding it pretty well, until this.

It's defining the possible types of a language. I'm very confused about what theta and alpha mean. What are those meta-variables? What is `ua.t` and `t[ua.t/a]`?

Could someone give me some context? I'm not into computer science, this may be something specific that I have never seen before. I'm from a math background.

# Answer
> 4 votes
A metavariable is a variable that denotes some hypothetical chunk of a program. This distinction is important in the theory of programming languages, where we need to distinguish variables representing program fragments from the variables contained in those programs.

The terminology, I think, comes from logic: if you're defining a logic, you need to define it in some language that's distinct from the thing you're defining. This is the "meta-language", and the variables it uses are metavariables. The history of formal logic and programming languages are deeply intertwined via the Curry-Howard correspondence, so the terminology carried over.

# Answer
> 1 votes
## Meta-variable explanation by example

Consider the simply typed lambda calculus (STLC) with base types `Int` for integers and `Bool` for booleans. In this calculus, we can have an identity function for integers $(\lambda x:\mathrm{Int}.x)$ and another one for booleans $(\lambda x:\mathrm{Bool}.x)$. More generally,

> For every type $A$ of STLC, there is an identity function $(\lambda x:A.x)$.

The above sentence does not belong to the STLC language. It belongs to a meta-language: the language that I used (english) to express a property about STLC. The $A$ in the above sentence is a meta-variable that ranges over the set of types of STLC.

The distinction here is perhaps clearer, because we know that STLC has no type variables. But if you want to express properties about a language that has type variables, you may need to explicitly clarify what are variables of the object language (the calculus/language you talk about) and what are meta-variables (variables that belong in the language you use to express properties about the object language).

---

## Notation

The notation $\mu a.\tau$ is a type that is similar to System F's polymorphic type $\forall a.\tau$. They both bind the type variable $\alpha$ in $\tau$. The difference is in the semantics. As the text states,

> A type of the form $\mu a.\tau$ is considered identical to the type $\tau\[\mu a.\tau / \alpha\]$.

and this allows us to introduce recursive types in our object-language (which is not the case about $\forall a.\tau$).

Generally, for types $\sigma$ and $\sigma'$ (btw, these are again meta-variables) the notation $\sigma\[\sigma' / \alpha\]$ denotes substitution of the type variable $\alpha$ with $\sigma'$ in $\sigma$. In the text, they set $\sigma = \tau$ and $\sigma' = \mu a.\tau$.

---

... and now I realized this is a bit of an old question. :P

---
Tags: type-theory, type-checking, static-analysis
---


# Question
Title: Need help understanding tightest lower bound ( BigOmega ) of n!
I am currently learning complexity theory and wasn't able to find a tightest lower bound to **BigOmega(n!)**, I am quite certain it isn't **n^n** and so wasn't able to reach to a tightest lower bound, can **log(n)^n** be the one, of course lose lower bounds are possible, but can you please help me understand the tightest lower bound of **n!**?

# Answer
> 3 votes
You are indeed correct that it isn't $n^n$ (though this is good enough for most purposes). As OmG mentioned in the comments, there is a standard approximation formula called "Stirling's approximation formula" which gives the following asymptotic bound:

$$n!=\Theta\Big(\sqrt{n}\frac{n^n}{e^n}\Big)$$

---
Tags: complexity-theory, algorithm-analysis, asymptotics, complexity-classes
---


# Question
Title: Unit conversion - Better to divide by an integer or multiply by a double?
I currently have a `long` timestamp measured in units of 100ns elapsed since January 1st, 1900. I need to convert it to milliseconds.

I have the choice of either multiplying by `0.0001` or dividing by `10_000`. Although at first glance they sound the same, the former would actually cause an implicit cast to a `double` \- the latter would of course result in another `long` with the remainder truncated.

Which would yield a better result? Obviously `double` is an imprecise type that introduces errors due to the use of a mantissa, floating radix, and exponent, but would that error be less or more than the error from performing the simple integer division? Or would the error be demonstrably negligible?

To give an example of one of my values, here is one of the timestamps: `38348440316924872` .

I'm specifically referring to C#, but this question should be general to computer science.

# Answer
I think the answer to your question really depends on what you want to achieve, namely:

* Do you need the measure to be more precise than milliseconds?

If the answer to the first question is yes:

* I think double is a reasonable choice. In the range of the number you gave the worse error I got is with `38348440316924876` where if multiplied with `0.0001` gave me `3834844031692.4883`.
* A even better solution might be to use a fixed point number where in the underling data structure stores the 100ns steps and abstracts in a way that it feels like working with milliseconds.

If the answer to the question is no:

* I would just divide by `10000`, if you want the value to be rounded and not truncated I would just apply this formula $\frac{x + 5000}{10000}$ to get a rounded value.

Edit: I did not really answer your question, but as you can see the error with `double` is much smaller than the one you would be getting with `long`
> 3 votes

---
Tags: floating-point
---


# Question
Title: Minimum absolute difference in a BST is always between
Given a Binary Search Tree(BST) I would like to understand can absolute minimum difference between any two nodes of a BST is always between adjacent nodes. If Yes or No can we generalize it ? Assume there are atleast two nodes.

Here is my approach

Case 1 : Assume only positive real numbers

Assume the absolute difference (dMIN) between two adjacent nodes is not the Minimum This means there exists an absolute minimum difference which is smaller than dMIN by d. Say dMIN - d. In a BST, as we traverse left the value of the Node always decreases atleast by a smallest non zero value. Similiarly if we traverse to the right of a given node value of a node always increases atleast by smallest non-zero value This means the absolute min difference is always greater dMIN atleast by smallest non-zero value Which contradicts there exists a smaller absolute dMIN - d. Thus the absolute minimum difference is always absolute difference of two adjacent nodes

Case 2 - Assume the nodes of the BST comprises entire set of real numbers. There exists atleast one negative real number.

Assume there exists a min absolute difference(dMIN) two adjacent nodes. Since the value of the nodes comprises entire set of real numbers As we traverse to the left side of node the value of the node decreases atleast by the largest negative number. This can be continued until we reach leaf nodes from the root node. Thus the absolute min difference increases as we traverse from the root node to the left most leaf node. Thus absolute min difference of a pair of nodes is always between root node and leaf node.

# Answer
Your proof for case 1 seems like good intuition (it is **not** a formal proof). However, instead of the proof in case 2, you can directly reduce case 2 to case 1:

Lets say that the minimal value in the tree is $v\_{min}\in\mathbb{R}$. Then, we can artificially "add" $v\_{min}$ to the value of every node in the BST. Now, the BST will contain only non-negative numbers. This BST will follow case 1.

I claim, that for any two nodes with values $v'\_1$, $v'\_2$ in this updated BST, their absolute difference is the same as their absolute difference from the original BST, that had values $v\_1,v\_2$ in them:

$$|v'\_2-v'\_1|=|v\_2+v\_{min}-(v\_1+v\_{min})|=|v\_2-v\_1+v\_{min}-v\_{min}|=|v\_2-v\_1|$$

And hence the proof for case 1 works here as well.
> 1 votes

---
Tags: binary-search-trees
---


# Question
Title: What is the formal definition of precedence and associativity in programming language?
The concept of precedence and associativity seems straightforward.

> The operator precedence is a collection of rules that reflect conventions about which procedures to perform first in order to evaluate a given mathematical expression.

> The associativity of an operator is a property that determines how operators of the same precedence are grouped in the absence of parentheses.

However, from the perspective of programming language theory, I wonder if there's a formal definition for precedence and associativity. With that formal definition, for example, we could argue that if a formal grammar defines the precedence of two operators, or that if a grammar has some property, then the operators in the grammar will have some kind of precedence.

Maybe it is possible to give a formal definition in each programming language case by case, but there's no general one?

# Answer
> 2 votes
Look at the Swift language where the available operators are not defined in the language, but in the standard library. There are rules that let the compiler distinguish between binary and unary operators. An expression is operands, possibly preceded or followed by unary operators, and separated by binary operators.

That’s decided by the grammar, without any knowledge of the operands. Then we examine the unary operators from inside to outside. An operator on the left/right must be allowed on the left/right. If there is an operator on each side then we apply the one with higher priority. Operators of equal priority are an error.

Next the binary operators. We find the first sequence of operators of highest priority. If these operators have different associativity then we have an error, otherwise the operators are evaluated left to right or right to left. Repeat until all operators are gone.

So precedence and associativity are not part of the grammar, they are attributes of each operator.

And this isn’t about “mathematical expressions”. It’s any expression.

---
Tags: formal-languages, formal-grammars, programming-languages
---


title: how to optimise this

text:
# Question
Title: how to optimise this
Say you are given a matrix $M (A \cdot B)$ when $A$ is the number of rows and $B$ is the number of columns. Now we are free to pick one element from each column. Lets say these elements are $E = \\{ e\_1,e\_2,e\_3,\dots,e\_b \\}$ and $f(E) = \max(E) - \min(E)$. Find the minimum value of $f(E)$.

I tried multiple but I can't think of any way to answer. Please help.

# Answer
> 0 votes
Label each element $m\_{i,j}$ of $M$ with $(m\_{i,j}, j)$ and sort all such pairs in non-decreasing order of the first element (the order on the second element can be arbitrary).

We will use a data structure that maintains a dynamic collection $D$ of $n$ elements and is able to insert elements, delete elements, report the maximum element in $D$, report the minimum element in $D$, and report $|D|$ in $O(\log n)$ time per operation. For example you could use an AVL tree. In our application, this data structure will contain at most one pair $(m, j)$ per column $j$. If $|D|=B$ the elements associated with these pairs will represent a tentative solution $E$.

Moreover, maintain an array $A\[1, \dots, B\]$. The generic $j$-th entry $A\[j\]$ of $A$ will contain the pair $(m,j)$ currently in $D$, if any. Initially all entries of $A$ are "empty".

As said before, the following algorithm will maintain a tentative solution $E$. Let $m^\*$ be the minimum value of $f(E)$ encountered so far. Initially $m^\* = +\infty$.

Proceed as follows:

* For each pair $(m, j)$ in non-decreasing order of $m$:
    + If $A\[j\]$ not is empty, delete $A\[j\]$ from $D$.
    + Insert $(m,j)$ into $D$.
    + Set $A\[j\] = (m,j)$.
    + If $|D|=B$ then let $(m^-, \cdot)$ and $(m^+, \cdot)$ be the minimum and maximum values in $D$, respectively, and update $m^\* = \min\\{m^\*, m^+ - m^-\\}$.
* Return $m^\*$.

Clearly this algorithm takes $AB \log (AB)$ time. We now argue about its correctness.

Let $E = \\{ m^\*\_1, m^\*\_2, \dots, m^\*\_B \\}$ be an optimal solution, where $m^\*\_i$ is selected from the $i$-th column of $M$. Consider the instant $t$ at which the last element $m^+$ from $E$ is added to $D$ by the algorithm (notice that, by construction, we have $m^+ = \max E$) and let $(m\_1, 1), (m\_2, 2), \dots, (m\_B, B)$ be the keys in $D$.

It suffices to prove that, for each $j = 1, \dots, B$ we have $m^\*\_j \le m\_j \le m^+$. The inequality $m\_j \le m^+$ is trivial, so we can focus on $m^\*\_j \le m\_j$. By our choice of $t$, we know that all $m^\*\_j$ must already have been processed by the algorithm at some time $t'$ that comes not later than $t$. Then, at time $t'$, $(m^\*\_j, j)$ was in $D$. The claim follows since the pairs $(\cdot, j)$ inserted in $D$ are monotonically non-decreasing w.r.t. the value of their first element.

---
Tags: algorithms, data-structures, arrays, matrices
---


# Question
Title: Codeword length of a character with frequency more than $\frac{2}{5}$ in huffman coding
I read the following post. Now i encountered this question, what is codeword length of a character with frequency more than $\frac{2}{5}$ huffman coding? I think it can 2bit or 1bit, but i can't prove it. Any help for proving that appreciated.

# Answer
Consider the classical algorithm that constructs the Huffman code and focus on the moment in which the singleton vertex $v$ corresponding to the character with frequency larger than $\frac{2}{5}$ was first merged with another tree $T$. At this point in time, either the frequency of $T$ was at least $\frac{2}{5}$ (which means that all trees had frequency at least $\frac{2}{5}$), or $T$ was the only tree with frequency smaller than $\frac{2}{5}$ (otherwise $T$ would have been merged with some other tree).

This means that there can be at most one additional tree in the forest other than $v$ and $T$.

The maximum depth of $v$ that can be obtained by combining (up to) $3$ trees is $2$.

Clearly both $1$ and $2$ are possible lengths of a codeword, as shown by symbol $a$ in the following two examples (frequencies are in blue).
> 1 votes

---
Tags: algorithms
---


# Question
Title: Faster algorithm for a specific inversion
There is a permutation (more precisely a derangement) $\sigma$ of the set $\\{0,1,\dots,n-1\\}$ with cardinality $n$.

I want to compute the following counts (a kind of inversion):

$$K(\sigma )\_{i}=\\#\\{j\>i:\sigma \_{j}\>i\\}$$

for each $0 \le i \lt n$.

Obviously a $O(n^2)$ straight-forward algorithm computes these counts. But can it be done faster (eg in $O(n \log n)$)?

I can't seem to wrap my head around such an algorithm, based on other divide-and-conquer algorihms for usual inversions, at least so far.

**Background:** The counts above are used in a custom algorithm to rank and unrank derangements in lexicographic order and their computation is the main bottleneck of the algorithm.

# Answer
Each element $j$ contributes $1$ to the cardinality of all sets $\\{j \> i \mid \sigma\_j \> i\\}$ for which $i \< \min\\{\sigma\_j, j\\}$, and $0$ to the other sets.

You can compute all $n$ values $K(\sigma)\_i$ in $O(n)$ time as follows. Maintain an array $A\[0, \dots, n-1\]$ where each entry $A\[i\]$ is initialized to $0$. Then, for each $j$, increment $A\[\min\\{\sigma\_j, j\\}\]$ by $1$.

Compute the sums of the elements in all suffixes of $A$, i.e., construct a new array $K\[1, \dots, n-1\]$ such $K\[i\] = \sum\_{i' \> i} A\[i'\]$. This can be done in $O(n)$ time by setting $K\[n-1\]=0$ and, for all $i=n-2, \dots, 0$ (in this order), $K\[i\] = K\[i+1\] + A\[i+1\]$.

Clearly, the above can also be done in-place without the need of the additional array $K$.
> 7 votes

---
Tags: algorithms, time-complexity, combinatorics, permutations
---


# Question
Title: Stuck on Converting to Chomsky Normal Form,
I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form.

Here is the language:

S → AA|SBBa|b

A → ABa|BS|a

B → BBb|a|λ

I know the first step is to make a new start symbol and thats easy enough

SO → S

S → AA|SBBa|b

A → ABa|BS|a

B → BBb|a|λ

Here is where I mess up, I know that you have to get rid of the lambda after this so it should be

SO → S

S → AA|SBBa|b|Sa

A → ABa|BS|a|Aa|S

B → BBb|a|

I know that now you have to get rid of the unit rules, but I have no idea how to start getting rid of them. A to S and So to S seem, like the only ones.

Any help would be appreciated

# Answer
here the first grammar given is :

S → AA|SBBa|b

A → ABa|BS|a

B → BBb|a|λ

first, remove epsilon productions:(B → λ):

S → AA|SBBa|SBa|Sa|b

A → ABa|BS|a|Aa|S

B → BBb|a|Bb|b

second, remove Unit productions and some unreachables may create:

S → AA|SBBa|SBa|Sa|b

A → ABa|BS|Aa|AA|SBBa|SBa|Sa|a|b

B → BBb|Bb|a|b

Then we are ready for CNF in two step furtuere:

1)

S → AA|SBBP|SBP|SP|b

A → ABP|BS|AP|AA|SBBP|SBP|SP|a|b

B → BBW|BW|a|b

W → b

P → a

2)

S → AA|FG|FP|SP|b

F → SB

G → BP

A → QP|BS|AP|AA|FG|FP|SP|a|b

Q → AB

B → HW|BW|a|b

H → BB

W → b

P → a

I guess the final result in CNF is part 2.
> 1 votes

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


# Question
Title: Faster algorithm for specific inversion count (part 2)
Following the issue from Faster algorithm for a specific inversion:

We have a permutation (a derangement actually) $\sigma$ of the set $\\{0,1,\dots,n-1\\}$ with cardinality $n$.

I want to compute certain counts (a kind of inversion):

$$K'(\sigma )\_{i}=\\#\\{j\<i:\sigma \_{j}\>i\\}$$

for each $0 \le i \lt n$.

With the restriction that the computation should depend **strictly on previously computed entries** (as this is for unranking, the future entries of the permutation are not yet known).

For computing the complementary counts during ranking (the linked question), there is a linear algorithm rather than the straight-forward $O(n^2)$ algorithm.

Can a faster algorithm (than the straight-forward $O(n^2)$ computation) be applied also in this case (maybe linear or $O(n \log n)$)?

**Background:** The counts above are used in a custom algorithm to rank and unrank derangements in lexicographic order and their computation is the main bottleneck of the algorithm.

# Answer
Each $j$ contributes $1$ to all $K'(\sigma)\_i$ with $j \< i \< \sigma\_j$.

Ideally you want a data structure that maintains a collection of $n$ counters $C\_0, \dots, C\_{n-1}$ under the following operations:

* Offset($j$, $\delta$): Given $j$ and $\delta$, add $\delta$ to each $C\_i$ with $i \le j$.
* Evaluate($i$): Return the value of $C\_i$

When $\sigma\_j$ is revealed, you can add $1$ to all $C\_i$ with $j \< i \< \sigma\_j$ (assuming the interval is non-empty) by performing the following two operations: (i) Offset($\sigma\_j-1$, $1$), (ii) Offset($j$, $-1$). Then, you can recover the value of $K'(\sigma)\_i$ by performing a Evaluate($i$) operation.

The rest of the answers describes how to implement a data structure supporting each of the above operations in $O(\log n)$ time, so that the overall time complexity will be $O(n \log n)$.

Suppose for simplicity that $n$ is a power of $2$, so that $k = \log n$. Instead of keeping a single set of counters $C\_0, \dots, C\_{n-1}$ (i.e., one for each $i$) keep multiple counters per element $i$.

The counters associated with $i$ will be $C^{(h)}\_i$ for some suitably chosen values of $h$. In particular, if the binary expansion of $i$ has $\ell\_i$ zeros in its least significant bit, then we will keep $\ell\_i$ counters $C^{(0)}\_i, C^{(1)}\_i, \dots, C^{(\ell\_i-1)}\_i$. (If $\ell\_i=0$, we keep no counters). The intuition is that adding $1$ to $C\_i^{(h)}$ corresponds to adding $1$ to each of the $2^h$ "original counters" $C\_i, C\_{i+1}, \dots, C\_{i+2^{h}-1}$. In particular we say that $C\_i^{(h)}$ *covers* $C\_i, C\_{i+1}, \dots, C\_{i+2^{h}-1}$.

See the figure for a graphical example with $n=16$.

To implement Offset($j$, $\delta$): write $j+1$ as a sum of (at most $\log n$) decreasing distinct powers of $2$ so that $j+1 = 2^{h\_1} + 2^{h\_2} + 2^{h\_3} + \dots + 2^{h\_m}$. Do the following:

* Set $x = 0$.
* For each $\ell = 1, \dots, m$:
    + Increment $C^{(h\_\ell)}\_x$ by $\delta$.
    + Increment $x$ by $2^{h\_\ell}$.

For example when $j = 12$, we can write $j+1 = 13$ as $8 + 4 + 1 = 2^3 + 2^2 + 2^0$. To perform Offset($12$, $1$), we would add $1$ to $C\_{0}^{(3)}$, $C\_{8}^{(2)}$, $C\_{12}^{(0)}$. These are exactly the counters corresponding to the intervals highlighted in red.

To recover the value of the "original counter" $C\_i$, it suffices to sum the values of all counters $C\_{i'}^{(h)}$ that cover $C\_i$.
> 2 votes

---
Tags: algorithms, time-complexity, combinatorics, permutations
---


# Question
Title: Calculate the number of "count inversions" of sub arrays
Recently, I encountered the following problem:

> Given an array $A$ of length $n$ $(0\le n\le 2^{17})$. Let $f(l, r, x)$ denotes the number of occurrences of $x$ in the subarray $a\[l\ldots r\]$. Find the number of pairs $(i, j)$ such that $i\<j$ and $f(1, i, a\[i\]) \> f(j, n, a\[j\])$.

My idea is to mimic the divide and conquer algorithm used to count the number of inversions:

* Split the array in to two equal halves.
* Recursively calculate the number of count inversions in each half.
* Somehow calculate the number of count inversions in with $i$ in the first half and $j$ in the second half (this is the merge step in the ordinary count inversion algorithm).

However, I'm stuck with the merge step. Anyone have any idea on how to overcome this step?

# Answer
I have an algorithm idea, however it relies on data structures.

First we pre-compute $L\[i\] = f(1,i,a\[i\])$ using a Hashmap.

```
H := Map()
for i = 1, ..., n:
    key := a[i]
    if key in H:
        H[key] = 1
    else:
        H[key] += 1
    L[i] = H[key]

```

In the same manner we pre-comupte $R\[i\] = f(i,n,a\[i\])$ (backwards ofc). Now we have to find the number of pairs $i\<j$ such that $L\[i\]\<R\[j\]$ This is possible with a modified sorted balanced binary search tree. This tree should support insert/remove but also the operation:

$rank(x)$ \- find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree

Such a tree is called Ordered Statistics Tree(OST). (All of the above operations in $O(\log n)$ )

```
for i = 1, ..., n:
    tree.insert(R[i])

total = 0
for i = 1,...,n:
    total += n - tree.rank(L[i])
    tree.remove(R[i])

```

$total$ is the final result. Note that OST is implemented in the standard library of gcc, making it available in most CP scenarios. If you want to implement rank yourself without needing BBSTs, that is also possible using a combination of toggle-sum segment tree and binary search. Using a Fenwick-tree and binary search is for competitive programming purposes easiest to implement.

The runtime of the first part is $O(n)$ and for the second part $O(n\log n)$ (since we make $3n$ tree queries).
> 2 votes

---
Tags: recursion, divide-and-conquer
---


# Question
Title: How to approximate big composite number factors?
There is a big 1024-bits number A that was obtained by multiplying two numbers B and C.Are there any ways to get first numerical digits of these numbers?

How example:

```
A(4.65467...e+1024) = B(2.25351...e+512) x C(2.62568...e+256)

```

I want to receive `2.25` and `2.62` accordingly.

# Answer
Nope. The factoring problem is believed to be hard. Without knowing the full factorization, for any guess at the top digits of B you can reconstruct a set of top digits of C that would be consistent with that.
> 3 votes

---
Tags: primes, factoring
---


# Question
Title: Factorial algorithm more efficient than naive multiplication
I know how to code for factorials using both iterative and recursive (e.g. `n * factorial(n-1)` for e.g.). I read in a textbook (without been given any further explanations) that there is an even more efficient way of coding for factorials by dividing them in half recursively.

I understand why that may be the case. However I wanted to try coding it on my own, and I don't think I know where to start though. A friend suggested I write base cases first. and I was thinking of using arrays so that I can keep track of the numbers... but I really can't see any way out to designing such a code.

What kind of techniques should I be researching?

# Answer
The best algorithm that is known is to express the factorial as a product of prime powers. One can quickly determine the primes as well as the right power for each prime using a sieve approach. Computing each power can be done efficiently using repeated squaring, and then the factors are multiplied together. This was described by Peter B. Borwein, *On the Complexity of Calculating Factorials*, Journal of Algorithms **6** 376–380, 1985. (PDF) In short, $n!$ can be computed in $O(n(\log n)^3\log \log n)$ time, compared to the $\Omega(n^2 \log n)$ time required when using the definition.

What the textbook perhaps meant was the divide-and-conquer method. One can reduce the $n-1$ multiplications by using the regular pattern of the product.

Let $n?$ denote $1 \cdot 3 \cdot 5 \dotsm (2n-1)$ as a convenient notation. Rearrange the factors of $(2n)! = 1 \cdot 2 \cdot 3 \dotsm (2n)$ as $$(2n)! = n! \cdot 2^n \cdot 3 \cdot 5 \cdot 7 \dotsm (2n-1).$$ Now suppose $n = 2^k$ for some integer $k\>0$. (This is a useful assumption to avoid complications in the following discussion, and the idea can be extended to general $n$.) Then $(2^k)! = (2^{k-1})!2^{2^{k-1}}(2^{k-1})?$ and by expanding this recurrence, $$(2^k)! = \left(2^{2^{k-1}+2^{k-2}+\dots+2^0}\right) \prod\_{i=0}^{k-1} (2^i)? = \left(2^{2^k - 1}\right) \prod\_{i=1}^{k-1} (2^i)?.$$ Computing $(2^{k-1})?$ and multiplying the partial products at each stage takes $(k-2) + 2^{k-1} - 2$ multiplications. This is an improvement of a factor of nearly $2$ from $2^k-2$ multiplications just using the definition. Some additional operations are required to compute the power of $2$, but in binary arithmetic this can be done cheaply (depending on what precisely is required, it may just require adding a suffix of $2^k-1$ zeroes).

The following Ruby code implements a simplified version of this. This does not avoid recomputing $n?$ even where it could do so:

```
def oddprod(l,h)
  p = 1
  ml = (l%2>0) ? l : (l+1)
  mh = (h%2>0) ? h : (h-1)
  while ml <= mh do
    p = p * ml
    ml = ml + 2
  end
  p
end

def fact(k)
  f = 1
  for i in 1..k-1
    f *= oddprod(3, 2 ** (i + 1) - 1)
  end
  2 ** (2 ** k - 1) * f
end

print fact(15)

```

Even this first-pass code improves on the trivial

```
f = 1; (1..32768).map{ |i| f *= i }; print f

```

by about 20% in my testing.

With a bit of work, this can be improved further, also removing the requirement that $n$ be a power of $2$ (see the extensive discussion).
> 61 votes

# Answer
Keep in mind that the factorial function grows so fast that you'll need arbitrary-sized integers to get any benefit of more efficient techniques than the naive approach. The factorial of 21 is already too big to fit in a 64-bit `unsigned long long int`.

As far as I know, there is no algorithm to compute $n!$ (factorial of $n$) which is faster than doing the multiplications.¹

However, the order in which you do the multiplications matter. Multiplication on a machine integer is a basic operation that takes the same time no matter what the value of the integer is. But for arbitrary-sized integers, the time it takes to multiply *a* and *b* depends on the size of *a* and *b*: a naive algorithm operates in time $\Theta(|a| \cdot |b|)$ (where $|x|$ is the number of digits of $x$ — in whatever base you like, as the result is the same up to a multiplicative constant). There are faster multiplication algorithms, but there is an obvious lower bound of $\Omega(|a| + |b|)$ since multiplication has to at least read all the digits. All known multiplication algorithms grow faster than linearly in $\max(|a|,|b|)$.

Armed with this background, the Wikipedia article should make sense.

Since the complexity of multiplications depend on the size of the integers that are being multiplied, you can save time by arranging multiplications in an order that keeps the numbers being multiplied small. It works out better if you arrange for the numbers to be of roughly the same size. The “division in half” that your textbook refers to consists of the following divide-and-conquer approach to multiply a (multi)set of integers:

1. Arrange the numbers to be multiplied (initially, all the integers from $1$ to $n$) in two sets whose product is roughly the same size. This is a lot less expensive than doing the multiplication: $|a \cdot b| \approx |a| + |b|$ (one machine addition).
2. Apply the algorithm recursively on each of the two subsets.
3. Multiply the two intermediate results.

See the GMP manual for more specifics.

There are even faster methods that not only rearrange the factors $1$ to $n$ but split the numbers by decomposing them into their prime factorization and rearranging the resulting very long product of mostly-small integers. I'll just cite the references from the Wikipedia article: “On the Complexity of Calculating Factorials” by Peter Borwein and implementations by Peter Luschny.

¹ <sub> There are faster ways of computing *approximations* of $n!$, but that's not computing the factorial any more, it's computing an approximation of it. </sub>
> 22 votes

# Answer
Since the factorial function grows so fast, your computer can only store $n!$ for relatively small $n$. For example, a *double* can store values up to $171!$. So if you want a really fast algorithm for computing $n!$, just use a table of size $171$.

The question becomes more interesting if you're interested in $\log(n!)$ or in the $\Gamma$ function (or in $\log \Gamma$). In all these cases (including $n!$), I don't really understand the comment in your textbook.

As an aside, your iterative and recursive algorithms are equivalent (up to floating point errors), since you are using tail recursion.
> 11 votes

# Answer
I assume this is about finding the exact integer $n!$, not any floating-point approximation, for example. Very roughly $n! ≈ (n/e)^n$, so $\log n! ≈ n (\log n - \log e)$. In practice we can assume that $n \<\< 2^{64}$, otherwise we would need at least $2^{64} \cdot (64 - \log e)$ bits, which is about $2^{67}$ bytes or about 130 million terabytes.

We can multiply a k-bit number by a 64 bit number in O (k). The naive multiplication multiplies n k-bit numbers from 0 to $k(\log k - \log e)$ with a 64 bit numbers, so it takes about $n^2 \log n$ operations. If we can't multiply to m-bit numbers faster than in $O(m^2)$ then this beats any clever divide-and-conquer technique, which will at least multiply two $(n/2) (\log n - 1 - \log e)$ numbers as the last step, taking $O(n^2 \log^2 n)$ operations.

But if we can multiply two m-bit numbers in M(m) operations where M(m) is much smaller than $m^2$, then we can split the n numbers that we need to multiply into 2 groups with similar sized product, for example taking the 1st and 4th, 5th and 8th, 9th and 12th number vs the 2nd and 3rd, 6th an 7th, 10th and 11th number, and do this recursively. The Karatsuba algorithm works in $O(m^{1.58})$ and is quite accessible, but there are faster methods not much above O(m \log m). Using the Karatsuba algorithm, you should be able to calculate $(2^{32})!$ on a not very expensive computer in reasonable time. You'll need about 16 GB for the result alone.
> 1 votes

# Answer
Is the text book written Fundamentals of Algorithms, or Art of Programming by Knuth?

The following method is very effective:

1. Compute binomial coefficient (n, r), using the formula, by repeated multiplication,

(1+b)^n = 1 + (n,1)b + (n, 2)b^2 + ..... + (n, r)b^r + .... If you choose b large enough, for example, b = 2^n, there is no carry generated between the coefficients, so, you can select (n, r)

2. Suppose you want to compute m!.

Select N, much larger than m, for example, say N = m^m, and compute

K = integer(N^m/(N, m)),. Then K = m!

Here both exponent is computed by repeated multiplication.

Example : 8! = 40320 = integer( N^8/(N, 8)) for any N ≥ 1128977
> 0 votes

---
Tags: algorithms, efficiency, arithmetic
---


# Question
Title: How can we count the number of pairs of coprime integers in an array of integers? (CSES)
For reference, I am trying to solve this CSES Problem.

The problem basically states that given up to $10^5$ positive integers in the range $\[1, 10^6\]$, find the number of pairs of those positive integers that are coprime.

After some thought, I've come up with the following 3 ideas that I think may be on the right track, but are each missing something.

Brute-Force Idea: Simply iterate through all $O(N^2)$ pairs of integers in the array, and increment our answer every time the pair of integers has a Greatest Common Divisor of 1. Using the Euclidean Algorithm to find GCDs, we obtain a time complexity of $O(N^2logN)$, but this is too slow since $N \<= 10^5$.

Idea #2 (Sieve of Erathosthenes): I thought that there had to be some significance to all the numbers being bounded by the rather low $10^6$ and not something like $10^9$ or $10^{18}$. Specifically, the bound allows us to create an Extended Sieve of Eratosthenes (basically just a normal sieve except we keep, for each number, the smallest prime number that is a factor of it). However, only comparing the smallest prime factors of 2 numbers is not enough to determine if they're actually coprime (consider $14$ and $21$), and besides, this still involves testing all pairs of numbers, which is too slow.

Idea #3 (Principle of Inclusion and Exclusion): My most recent idea is that perhaps we can construct, for each prime number in the range $\[1, 10^6\]$, whichever given numbers are divisible by it. Then, the number of coprime pairs = the total number of pairs ($\frac{N(N-1)}{2}$) - the number of pairs of prime numbers such that both numbers appear in at least 1 same set, and the last term can be calculated with the PIE's formula. The problem with this is that the Principle involves the intersections of sets, and I have no idea how to calculate these intersections without re-iterating through all integers, not to mention that calculating the various terms in the formula of PIE requires iterating through all subsets of the integers ($O(2^N)$) - again, this approach seems too inefficient.

Overall, I'm pretty sure that at least *one* of these ideas is somehow on the right track, but I have been unable to find the missing link to the final solution. Can someone point me in the right direction? Thanks a lot!

# Answer
> 6 votes
The solution is a combination of Ideas 2 and 3:

* By Idea 2, you can find a full prime factorization of each number (by dividing by the smallest prime, then dividing by the smallest prime of the result, etc.). W.l.o.g. we can assume that each prime number in the factorization has power $1$.
* Since each number is $\le 10^6$, it can have at most $7$ distinct prime divisors, since for the product of $8$ smallest primes: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \> 10^6$. Therefore, each number has at most $2^7$ distinct divisors.
* Now, for each divisor of each number, we record in how many numbers it appears. Since each divisor is $\le 10^6$, you can simply maintain a counter for all possible divisors. For each number, you process its divisors and increment their counter.
* Finally, using Idea 3 (PIE), for each number we can find how many numbers are not co-prime with it. For example, if the current number is $14$, then this amount is (# of numbers divisible by 7) + (# of numbers divisible by 2) - (# of numbers divisible by 14). Since the current number itself is included in this count, subtract $1$ from it.

Overall time is $2^7 \cdot 10^5 \approx 10^7$ and memory is $10^6$.

# Answer
> 0 votes
The second idea seems to guide you on the right track. You can use the fact that all multiplies of each prime cannot be co-prime. So, for 14, as an example, you can remove all multiples of 2 and seven from the list. Hence, you can remove all multiplies of 2 ($\frac{10^6}{2}$), plus all odd multiplies of 7 ($\frac{10^6}{7\times 2}$). Hence, you need to check the co-prime with $10^6 \times (1 - \frac{1}{2} - \frac{1}{14}) \sim428571$.

Although you cannot decrease the asymptotic complexity, as you are working on a specific range, any reasonable decreasing factor can boost the performance of your algorithm significantly.

---
Tags: algorithms, number-theory, counting, mathematical-analysis, primes
---


# Question
Title: I am working on project euler 52 to practice my Python but I think I have misunderstood what the problem is
> It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

> Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

I took this to mean find the smallest x for which 2x, 3x, 4x, 5x, and 6x are all doubles, that is, the smallest x for which they all have the same digits at the same frequency.

This can't be right as for whatever x, 2x will always have one extra 2 than 3x which has one extra 3 than 4x, etc.

# Answer
> 1 votes
Given a positive integer $x$ let $n\_x = \lfloor \log\_{10} x \rfloor$ and let $x\_0, x\_1, \dots, x\_{n\_x} \in \\{0, 1, 2, 3, 4, 5, 6, 7 ,8 ,9\\}$ such that $x = \sum\_{i=0}^{n\_x} 10^i x\_i$. Define the multiset $S(x) = \\{x\_0, x\_1, \dots, x\_{n\_x} \\}$.

The problem is asking for: $$ \min x \quad\mbox{ s.t.}\\ S(x)=S(ix) \quad \forall i \in \\{2,3,4,5,6\\}; \\ x \in \mathbb{Z}; \\ x \> 0. $$

---
Tags: python
---


# Question
Title: Betweenness Problem for Binary Comparisons is NP-Complete
I have a very simple question and wanted to check whether my answer is correct.

Suppose we are given a list of comparisons $x\_1\>x\_2,..,x\_k\>x\_i$ then consider the decision problem asks whether the ordering $\>$ can be made transitive and complete over all the X.

My impression is that such a decision problem is NP-complete. Here is my proposed solution.

1. Any solution can be checked in polynomial time, suffice to verify each comparison from the solution ordering.
2. To show it is NP-complete, I show that the *Betweenness Problem* with triple type (https://en.wikipedia.org/wiki/Betweenness) is reducible to ours.

Proof of 2): The Betweenness problem asks exactly our question but has ordering of type $x\_1\>x\_2\>x\_3$. But of course each such statement can be translated to $x\_1\>x\_2$, $x\_2\>x\_3$ this is done in at most (?) than polynomial time.

I just wanted to check whether this solution is correct and complete? Any help is greatly appreciated, thanks a lot!

# Answer
Your problem can be solved in linear time. Construct a directed graph on the vertex set $\\{1,\ldots,n\\}$, with an edge $i \to j$ for every comparison $x\_i \< x\_j$. There is a linear order compatible with the given comparisons iff the digraph is acyclic. (See topological ordering.)
> 5 votes

# Answer
Your solution is wrong. In particular the Betweenness problem is not what you claim it to be. In the Betweenness problem you are given a collection of triples $(x\_i, x\_j, x\_h)$ and you want to place $x\_j$ between the occurrences of $x\_i$ and $x\_h$. Notice that there is no requirement saying that $x\_i$ must precede $x\_j$. I.e., both $\langle x\_i, \dots, x\_j, \dots, x\_h \rangle$ and $\langle x\_h, \dots, x\_j, \dots, x\_i \rangle$ are valid orders.

Your problem is easily solvable in polynomial time. Let $X = \\{x\_1, \dots, x\_n\\}$ be the set of input elements and let $m$ be the number of comparisons you are given in input, where the $i$-th comparison is $c\_i \> c'\_i$ (with $c\_i, c'\_i \in X)$. Create the directed graph $G=(X, E)$ where $E = \\{ (c'\_i, c'i) : i =1,\dots,m \\}$.

Your problem admits a solution if and only if $G$ is acyclic. If it is, a solution can be found by computing a topological order of $G$.
> 4 votes

---
Tags: time-complexity
---


# Question
Title: kdtree or balltree supporting insertion/deletion
I'm looking for a data structure to perform nearest-neighbor searches in 3D Euclidean space. I have used kd- and balltrees for this purpose before, but my problem is more sophisticated this time. I'd like to be able to insert and delete points from my dataset dynamically. I don't see any reason why either of these two data structures wouldn't support this. Based on my understanding of both algorithms, I would think they offer the same complexities for each operation as a 1D binary search tree, including logarithmic-time insertion and deletion. Yet I can't find an implementation of either type of tree that supports these operations.

Why do none of the kdtree and balltree implementations I can find online (in particular from sklearn and alglib) support insertion/deletion? Is there a different freely available implementation which does?

# Answer
> 2 votes
My experience comes mainly from kd-trees.
I think this answers part of your question and the attached image really visualizes the problem.
When you construct the kd-tree initially the tree is constructed in a way that is balanced.
If you add vertices to the tree, especially if you are adding points in a trajectory (e.g. the points that an airplane traversed) then you end up with an unbalanced tree where query time are not as good as balanced trees.

# Answer
> 2 votes
I am not sure about BallTrees, but kd-trees definitely support deletion (see my Java implementation here). I think the reason why it is often not implemented is that it is a lot more complex and may be a lot slower than a typical insertion. For example, you first need to find a proper replacement point.

As @Andrea Nardi pointed out, in kd-trees insertion and deletion usually cause imbalances in the tree making it slower (I would add that the initial tree is also usually imbalanced).

If you are looking for spatial index that support nearest neighbor search and fast insertion/deletion, also have a look at my own PH-Tree. It works a bit like a quadtree but can guarantee a maximum depth and is much more memory efficient. It also guarantees that every insertion/deletion will only affect one node (and possible add/remove an empty second node). Note that the standard implementation is a *map*, so every coordinate can have only one entity, you would need to store lists at each coordinate.

In my experience quadtrees and the PH-Tree are the fastest for insertion/deletion. The PH-Tree scales well with large datasets (millions of points). For 3D nearest neighbor search, the best often seem to be R-Trees (e.g. R-star-tree), and again quadtrees and the PH-Tree (quadtree being the fastest but not scaling well with entry count). I found kd-trees usually lacking in performance, but as always, *this depends a lot on the characteristics of your data*, so please make your own tests. I have some performance graphs here (you may need to download it, GitHub takes ages to display it).

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


# Question
Title: Yao's min-max theorem: how can the set of deterministic algorithms be finite?
I'm read *Randomized Algorithms* book by Motwani, the part about Yao's min-max technique:

> Consider a problem where the number of distinct inputs of a fixed size is finite, as is the number of distinct (deterministic, terminating, and always correct) algorithms for solving that problem.

> Let $\Pi$ be a problem with a finite set $\mathcal{I}$ of input instances(of a fixed size), and a finite set of deterministic algorithms $\mathcal{A}$, then

> Proposition $2.5$ (Yao's Minimax Principle): For all distributions p over $\mathcal{I}$ and $\boldsymbol{q}$ over $\mathcal{A}$, $$ \min \_{A \in \mathcal{A}} \mathbf{E}\left\[C\left(I\_{p}, A\right)\right\] \leq \max \_{l \in \mathcal{I}} \mathbf{E}\left\[C\left(I, A\_{q}\right)\right\] $$ In other words, the expected running time of the optimal deterministic algorithm for an arbitrarily chosen input distribution $\boldsymbol{p}$ is a lower bound on the expected running time of the optimal (Las Vegas) randomized algorithm.

It's reasonable that the number of distinct inputs of fixed size is finite, say the number of graphs with $100$ vertices is finite. But how come the number of distinct deterministic algorithms is also finite? That is to say, the number of determinist algorithms to find the min-cut for graph of $100$ vertices is finite. I'm confused here:

* What exactly does it mean here by being finite?
* Why these two sets has to be finite?

# Answer
> 4 votes
The set of all algorithms *isn't* finite. Motwani isn't claiming that the set of all algorithms is finite.

Rather, Motwani is proposing we examine a situation where we have some finite set of algorithms. In other words, suppose we have a set $\mathcal{A}$ of algorithms. If $\mathcal{A}$ is finite, then Motwani says there are some facts we can prove, and the exposition explains some of those facts.

Nowhere does Motwani claim or assume that $\mathcal{A}$ is the set of all algorithms. You can consider any set of algorithms you want. If your set is finite, then the facts shown there will hold. If your set is infinite, they might not.

---

To put it another way, "Consider a problem where X" is not a claim that X holds; it is a statement that *if* X holds, then some other things will follow.

---
Tags: randomized-algorithms
---


# Question
Title: What is known about $S$ if $\{\langle M\rangle : L(M)\in S \}$ is recursive or recursively enumerable
For $L\_S=\\{\langle M\rangle : L(M)\in S \\}$ what is known about $S$ in case of:

1. $L\_S\in RE$
2. $L\_S\in R$

# Answer
> 1 votes
Rice's theorem states that if $L\_S$ is not trivial (i.e., is not $\varnothing$ nor all languages) then $L\_S$ can't be decided (it might be computably enumerable, though).

An extension to Rice's theorem states that $L\_S$ is computably enumerable if and only if after replacing $S$ with $S\cap RE$, all the following hold.

1. For all $L\_1, L\_2$ computably enumerable, if $L\_1 \in S$ and $L\_1 \subseteq L\_2$, then $L\_2 \in S$.
2. If $L \in S$, there is a finite subset $L' \subseteq L$ so that $L' \in S$.
3. The set of finite languages in $S$ is computably enumerable.

Proofs are given at here.

# Answer
> -1 votes
Take a look at Rice's theorem and its extensions.

Basically, Rice's theorem and its extension state:

1. If $\emptyset\neq S\subset RE$ then $L\_S\notin R$
2. If $\emptyset \neq S\subset RE$ and $\Sigma^\*\notin S$ (please fix me if this is wrong, this is what I remember) then $L\_S\notin RE$

---
Tags: formal-languages, turing-machines, computability, recursively-enumerable
---


# Question
Title: Precise algorithm for finding higher order derivatives
I'm trying to make an algorithm that finds the first 10 or so terms of a function's Taylor series, which requires finding the nth derivative of the function for the nth term. It's easy to implement derivatives by following the definition of the derivative: $$f'(x) = \lim\_{h\to0}\dfrac{f(x+h)-f(x)}{h}$$ implemented here in Python:

```
dx = 0.001
def derivative(f, x):
    return (f(x + dx) - f(x)) / dx

```

The value seems to be even closer to the actual value of the derivative if we define it like this:

```
dx = 0.001
def derivative(f, x):
    return (f(x + dx) - f(x - dx)) / (2 * dx)

```

which just returns the average of `(f(x + dx) - f(x)) / dx` and `(f(x) - f(x - dx)) / dx`.

---

For higher order derivatives, I implemented a simple recursive function:

```
dx = 0.001
def nthDerivative(f, n, x):
    if n == 0:
        return f(x)
    return (derivative(f, n - 1, x + dx) - derivative(f, n - 1, x - dx)) / (2 * dx)

```

I tested the higher order derivatives of $f$ at $1$, where $f(x)=x^9$, and as can be proved by induction, $$\dfrac{d^n}{dx^n}(x^k)=\dfrac{k!}{(k - n)!}x^{k-n}$$

Therefore, the nth derivative of $f$ at $1$ is $\dfrac{9!}{(9 - n)!}$. Here are the values returned by the function for n ranging from 0 to 9:

```
n             Value  Intended value
-----------------------------------
0             1.000               1
1             9.000               9
2            72.001              72
3           504.008             504
4          3024.040            3024
5         15120.252           15120
6         60437.602           60480
7         82298.612          181440
8      32278187.177          362880
9   95496943657.736          362880

```

As you can see, the values are waaaay off for $n$ greater than $5$.

---

What can I do to get closer to the actual values? And is there an algorithm for this that doesn't have $O(2^n)$ performance like mine?

# Answer
The first thing you should understand is why central differencing gives you a more precise solution.

Consider the Taylor expansion of $f$ around $x$:

$$f(x + h) = f(x) + h f'(x) + \frac{1}{2} h^2 f''(x) + \frac{1}{3!} h^3 f'''(x) \cdots$$

Then:

$$\frac{f(x+h) - f(x)}{h} = f'(x) + \frac{1}{2} h f''(x) + \frac{1}{3!} h^2 f'''(x)\cdots$$

That is:

$$f'(x) = \frac{f(x+h) - f(x)}{h} + O(h)$$

However:

$$f(x - h) = f(x) - h f'(x) + \frac{1}{2} h^2 f''(x) - \frac{1}{3!} h^3 f'''(x) \cdots$$

Therefore:

$$f(x + h) - f(x-h) = 2 h f'(x) + \frac{2}{3!} h^3 f'''(x) \cdots$$

And so:

$$\frac{f(x + h) - f(x-h)}{2h} = f'(x) + O(h^2)$$

With central differencing, the even terms of the Taylor series cancel, and you get a second-order approximation instead of a first-order approximation.

(Note that in real-world problems, central differencing is not always possible for many reasons. In fluid dynamics, for example, you do not want to do a central differencing approximation across a shock, so you generally only approximate derivatives using values that are "upwind" of the point of interest. I digress.)

You can think of approximating high-order derivatives as solving for the coefficients of the Taylor expansion. To find the first derivative, you solve for the first two coefficients. Since there are two unknowns, you need two equations. To calculate the second derivative as well, you need a third equation at least.

This doesn't seem like a game that you can win. If you obtain more points by using smaller values of $h$, then numerical evaluation becomes more unstable; if $f(x)$ and $f(x+h)$ are close in value, then $f(x+h) - f(x)$ can easily suffer from catastrophic cancellation. If you use larger values of $h$, then the $O(h)$ or $O(h^2)$ error term is larger. For a given $h$, there are only two points at distance $h$ from $x$ on the real line.

However, there are as many points (at a distance $h$ from $x$) as you want in the complex plane. So if $f$ is holomorphic, and $f(x) = x^9$ is holomorphic, you can obtain some extremely high-precision derivative estimates by picking points on a circle around $x$.

Back to central differencing for a moment, this works by eliminating the even terms of the Taylor approximation. You may wonder if it's possible to extend this to eliminate higher-order terms.

Suppose that $A\_k(h)$ is a $k$th-order approximation to some desired value $L$. That is, there are some constants $c\_i$ such that:

$$A\_k(h) = L + c\_k h^k + c\_{k+1} h^{k+1} + c\_{k+2} h^{k+2} + \cdots$$

Let's look at what happens if you halved $h$:

$$A\_k(\frac{h}{2}) = L + \frac{1}{2^k} c\_k h^k + \frac{1}{2^{k+1}} c\_{k+1} h^{k+1} + \frac{1}{2^{k+2}} c\_{k+2} h^{k+2} + \cdots$$

Then:

$$2^k A\_k(\frac{h}{2}) - A(h) = \left(2^k - 1\right) L + O(h^{k+1})$$

And so this:

$$A\_{k+1}(h) = \frac{2^k A\_k(\frac{h}{2}) - A\_k(h)}{2^k - 1}$$

is a $k+1$th-order approximation. And, of course, you can iterate to find higher order approximations.

Even though this technique uses smaller and smaller step sizes, you can control the numeric issues by using a factor $t$ other than 2:

$$R(h,t) = \frac{t^k A(\frac{h}{t}) - A(h)}{t^k - 1}$$

This is known as Richardson extrapolation, and it turns out to be extremely useful in estimating derivatives.
> 3 votes

# Answer
If you use memoization, your algorithm will have $O(n^2)$ running time, instead of $O(2^n)$ running time. See also https://en.wikipedia.org/wiki/Numerical\_differentiation#Higher\_derivatives.

You might check the value of $dx$ you are using (see https://en.wikipedia.org/wiki/Numerical\_differentiation#Step\_size); and check whether you are experiencing numerical roundoff/precision issues.

One other possible approach is to evaluate the function at 10-20 randomly chosen points near $x$, and then fit a 10th order polynomial to those points using least-squares polynomial regression.
> 1 votes

---
Tags: algorithms, mathematical-programming, numerical-algorithms, mathematical-analysis, numerical-analysis
---


# Question
Title: Bellman-Ford algorithm and nodes that not appear on negative cycle
Given directed graph $G=(V,E,\omega,s,t)$ that $\omega:E\to \mathbb{R}$ is the weight function on $E$, and we want to find shortest path from $s$ to $t$. First, we run the Bellman-Ford algorithm to finding the shortest path from $s$ to $t$, but after the termination of the algorithm, I know that if the distance of a node $v$ changed, then the graph contains a negative cycle that reachable from the source, so, can we conclude that $v$ necessarily appear in a negative cycle or not?

My attempt: I think not necessarily $v$ appears in a negative cycle. Consider the below example that $t$ not on any negative cycle, but after the termination of the algorithm, if we update the distance, its distance changed. **Can we conclude that $v$ sometimes appears in a negative cycle or sometimes not appear on any cycle?**

# Answer
You are right. It doesn't mean that it will appear in a negative cycle. Rather, it means that there exists some negative cycle $C$ that is reachable from the source node $s$ and $v$ can be reached from $C$.

Since the distance for any node inside a negative cycle is practically negative infinity (for any negative value, after a certain number of iterations the distance will be smaller than that), then the distance for any node that can be reached from it is also negative infinity. Meaning that this is not a good way to detect *which* edges are in the negative cycle.

If you want to find the negative cycle, you can actually do something easy:

1. Run bellman ford
2. Do an extra iteration of bellman ford. If nothibg changed, there is no negative cycle. Otherwise, there is.
3. If there is a negative cycle, let $w$ be a node that changed in step 2
4. Do $w\leftarrow parent(w)$ at least $|V|$ times.
5. This resulting $w$ (after you did step 4), and all other nodes that you get by doing $w\leftarrow parent(w)$ (again, only after step 4. In step 4 the nodes you see don't count), have to be the negative cycle.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Does Nondeterministic TM is a counterexample of Extended Church-Turing Thesis?
We know that Extended Church-Turing Thesis (or Cobham's thesis) states that any 'reasonable' model of computation can be equivalent to Turing Machine model in at most polynomial time overhead.

People always believe that this ECTT is not true and a candidate counterexample is quantum computation. But, why they don't see Nondeterministic Turing machine as a counterexample? Is it because it didn't correspond to any real-world computing device?

Note: I don't know what is good tag for this question, so if you know one, please let me know.

# Answer
> 4 votes
No, because nondeterministic Turing machines are not "reasonable" in the sense used here. In this context, the ECT talks about realistic models of computation, i.e., models that can be implemented on physical devices. Nondeterminism cannot be implemented directly given our current understanding of physics (we can simulate it on a deterministic machine, but that incurs an exponential slowdown).

---
Tags: complexity-theory, church-turing-thesis
---


# Question
Title: Reduction from 2 finite languages when one doesn't include epsilon and the other does
Just did a test about the subject that had the following question:

I know it seems trivial and my first reaction was "well of course its true" but the epslilon kinda threw me off.

$L\_2$={ab,$\epsilon$} $L\_1$={a} , is there a computable reduction from $L\_1\leq L\_2$ ,: True Or False

I assumed by contradiction that its true and did the following :

My idea was that if we always reject epsilon , then the starting state would always reject on the empty string , therefor no reduction would exists.

, if $\epsilon\notin L\_1$ then the computable function f must uphold: $f(\epsilon)\notin L\_2\iff \epsilon\notin L\_1$ Therefor the turning machine will always stop on the empty string , so she'll also stop on $\epsilon\cdot a=a$ therefor $f(\epsilon a)=f(a)\notin L\_1$ in contradiction to the assumption

Now the answer was true apparently but I can't really understand why , I'm also not 100% sold on my solution , but since I managed to prove it I just went with it , so I assume that I have some mistake in the part of $f(\epsilon a)=f(a)$.

Thanks,

# Answer
> 0 votes
Here a possible function $f$ that provides the reduction from $L\_1$ to $L\_2$.

$$ f(x) = \begin{cases} \varepsilon & \mbox{if $x=a$} \\ b & \mbox{otherwise} \end{cases}. $$

---
Tags: complexity-theory, computability, reductions, undecidability
---


# Question
Title: find a path to visit every node in graph not necessarily once
I meet a problem but when I google, there are all Hamiltonian Path Problem: How to find a path to visit every node in directed graph(not necessarily once)?

This problem is different from Hamiltonian Path.

For example:

```
1 --> 2 -->  3 ↔ 4
             ↕
             5

```

I have a path $1\rightarrow 2\rightarrow3\rightarrow4\rightarrow3\rightarrow5$ to visit all nodes in this graph, however this graph has no hamiltonian path.

My questions:

> 1. What's the terminology of this problem?
> 2. Is there algorithm or theorem to determine whether a general graph has such path? If a graph has such graph, how to find the detailed path?

Thanks

# Answer
You probably haven't found anything in your searches because this problem is fairly easy to solve, without needing any fancy methods.

If the graph is strongly connected, then it is easy. Let $s$ be the starting node. Pick any vertex $v$ you haven't visited yet, and append a path $s \leadsto v$ followed by some path $v \leadsto s$ (both must exist, since the graph is strongly connected). Repeat, appending to the end of the path, until every vertex has been visited.

If the graph isn't strongly connected, decompose it into a dag of scc's. Then you can reduce the problem to finding a path through this dag (within a scc, use the algorithm of the first paragraph). You can find a path to visit every node in a dag iff the dag is itself a path, i.e., it has the structure $v\_1 \to v\_2 \to \dots \to v\_k$, and then it is trivial to write down this path.

This is not a Hamiltonian path, since it may visit the same vertex multiple times.
> 3 votes

# Answer
If you are allowed to visit vertices more than once, many graph theorists use the term *walk* instead of path, i.e., a *path* is a *walk* where each vertex is visited only once (others use the pair *path* and *simple path* for *walk* and *path*).

The **shortest** walk visiting every vertex may be called a Hamiltonian walk (see MathWorld), although this notion is not nearly as widely known as Hamilton paths. As a consequence a graph is Hamiltonian if and only if it has a Hamilton walk and this walk has length $n$ (number of vertices) and thus finding a Hamiltonian walk is also hard (as apposed to a walk of arbitrary length).
> 2 votes

# Answer
I think what you're looking for, like I was, is the Minimum Spanning Tree. Here is an article about it.
> 2 votes

---
Tags: graphs, graph-traversal, hamiltonian-path
---


# Question
Title: How can I optimize the runtime of an algorithm that ranks binned columns cumulatively by average of another column?
I have a dense set of data that looks like this

| Y | X1\_BIN1 | X1\_BIN2 | X2\_BIN1 | X2\_BIN2 | X2\_BIN3 | ... |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 1 | 0 | 0 | 1 | 0 | ... |
| 1 | 1 | 0 | 1 | 0 | 0 | ... |
| 0 | 0 | 1 | 0 | 0 | 1 | ... |
| 1 | 0 | 0 | 0 | 1 | 0 | ... |
| 0 | 1 | 1 | 0 | 0 | 0 | ... |

but for millions of rows and about 400 columns, corresponding to bins of about 20 different XN variables. The average of Y is about 0.01.

What I want to do, is select the bin (e.g., X1\_BIN1, X2\_BIN3) that has the highest average Y value (always 1 or 0), then remove those rows, and then repeat the process until all rows have been selected or all remaining Y values are 0.

In the above example, X2\_BIN1 would be chosen first, the second row would be removed, then X2\_BIN2 would be chosen second, and all the remaining rows would be 0.

The problem with my current method is that it searches through all columns of data after each iteration, and then selects the one with the highest average. This has an O(N^2) runtime, which is bad when I have about 400 columns to go through.

Unfortunately, I can't think of any surefire way that would effectively reduce the runtime of this process.

For very small bins, I can subtract the count of the bin from all the other bins, and see if there are any others/groups of any others, with that subtracted count, that would still have a higher rate than the remaining bins with their original count. I think that this would save maybe one or two iterations out of hundreds, though, and

If I only calculate bins that would still have enough rows after removing K rows in a previous iteration, the average rate is so low that I could only assume the average Y value for bins that are mutually exclusive from the previous bin (e.g., if I remove X1\_BIN1, then the average of X1\_BIN2 is the same for the entire set). And then I would need to recalculate those bins if rows corresponding to a bin of another X variable were removed.

Additionally, the bins are constructed in a way that they are all likely to have distinct average values within a given X variable, making the above more effort than it's worth.

I'm not sure if this is better suited towards a more statistics-oriented forum, since there are underlying distributions that would make certain approaches better, but at this point, I feel like I've mostly used statistics just to rule solutions out.

# Answer
Let $n$ and $m$+1 be the number of rows and columns, respectively (so that there are $m$ bins). Your problem can solved in $O(nm + m^2)$ time. This is asymptotically optimal unless $m = \Omega(n)$, i.e., you have asymptotically more bins than rows.

Maintain the following:

* A collection of lists $L\_1, \dots, L\_m$ where $L\_j$ stores all rows contained in the $j$-th bin.
* An array of Booleans $R\[1, \dots, n\]$ where $R\[i\]$ is true if and only if the $i$-th row has already been selected. Initially all $R\[i\]$s are false.
* An array $A\[1, \dots, m\]$ where $A\[j\]$ contains the number of unselected rows that belong to the $j$-th bin and have $Y$ set to $1$. (Initially no row is selected).
* An array $B\[j\]$ that contains the number of unselected rows that belong to the $j$-th bin. Initially $B\[j\] = |L\_j|$.

Repeat the following:

* Find the index $j$ of a bin such that $A\[j\]\>0$ and $A\[j\]/B\[j\]$ is maximized. If no such index exists we are done.
* For each row $i$ in $L\_j$ such that $R\[i\]$ is false:
    + Set $R\[i\]$ to true
    + For each bin $h = 1, \dots, m$:
        - If row $i$ belongs to bin $h$:
            * Decrement $B\[h\]$ by $1$
            * If the $Y$ value of row $i$ is $1$:
                + Decrement $A\[h\]$

Let's bound the time complexity of this algorithm. Finding the next bin $j$ to process takes $O(m)$ time and happens at most $m$ times, therefore the overall time spent during this step is $O(m^2)$. For a fixed bin $j$, the time spent iterating over $L\_j$ to find the rows $i$ to process is $O(n)$, therefore the overall time spent across all bins is $O(nm)$ . Moreover, each row is processed only once, in time $O(m)$. The overall time is hence $O(nm)$.
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Is this variation of Max-Coverage NP-hard?
**Setup**

An instance of Max-Coverage is typically defined by a collection of $n$ sets $S = \\{s\_1, s\_2, \dots, s\_n\\}$, and a budget $k$, where the objective is to select a subset $U\subset S$ such that $$\big|U\big| \leq k,~\text{ and }~\big|\cup\_{s\in U}s\big|~\text{ is maximized}.$$

The variation I am interested in is as follows. Instead of being given a collection of sets, we are given a collection of $n$ **pairs** of sets, $S = \big\\{p\_1 =\\{s\_{1, 0}, s\_{1, 1}\\}, p\_2=\\{s\_{2, 0}, s\_{2, 1}\\}, \dots, p\_n=\\{s\_{n, 0}, s\_{n, 1}\\}\big\\}$. Further, instead of selecting $k$ sets, we now have to select one set from each pair of sets say $U = \\{ s\_{1, i\_1}, s\_{2, i\_2}, \dots s\_{n, i\_n}\\}$ s.t. $i\_j\in\\{0, 1\\}$ and $$\big|\cup\_{s\in U}s\big|~\text{ is maximized}.$$

**Questions**

1.) Is it NP-hard to optimally select one set from each pair such their union is maximized?

2.) Let $A$ be the universe of possible set elements and for each $i \leq n$, we have $s\_{i, 0} \cup s\_{i, 1} = A$ and $s\_{i, 0} \cap s\_{i, 1} = \emptyset$.

# Answer
**Regarding 1.** Consider a CNF-SAT formula $\phi$ with $n$ variables $x\_1, \dots, x\_n$ and $m$ clauses $C\_1, \dots, C\_m$. For $i=1,\dots,n$ define $s\_{i,0} = \\{ C\_j \mid \overline{x}\_i \in C\_j\\}$ and $s\_{i,1} = \\{ C\_j \mid x\_i \in C\_j\\}$.

The formula $\phi$ is satisfiable if and only if it is possible to select one $s^\*\_i \in \\{s\_{i,0}, s\_{i,1}\\}$ for each $i$ such that $\cup\_{i=1}^n s^\*\_i = \\{C\_1, \dots, C\_m\\}$, i.e., $\left| \cup\_{i=1}^n s^\*\_i \right|=m$. This shows that your variant of the problem is $\mathsf{NP}$-hard.

**Regarding 2.** The problem is equivalent to satisfying the maximum number of clauses in the CNF-SAT formula $\phi$ constructed as follows: create a variable $x\_i$ for each pair $p\_i = \\{s\_{i,0}, s\_{i,1}\\}$ and a clause $C\_j$ for each element $a\_j \in A$, where $C\_j = \bigg( \bigvee\limits\_{i : a\_j \in s\_{i,0}} \overline{x}\_i \bigg) \vee \bigg( \bigvee\limits\_{i : a\_j \in s\_{i,1}} x\_i \bigg)$. Let $m = |A|$ be the number of clauses of $\phi$.

We say that two clauses are equivalent if they contain exactly the same literals and we look at the equivalence classes $\mathcal{C}\_1, \mathcal{C}\_2, \dots, \mathcal{C}\_{\ell}$ of the set of clauses w.r.t. the relation "being equivalent".

Since each clause $C\_j$ contains all variables, $C\_j$ is false only in $1$ out of the $2^n$ possible truth assignments, and so are all clauses that are equivalent to $C\_j$. This means that, if $\ell \< 2^n$, there is always a truth assignment that satisfies all clauses.

We now consider the complementary case, namely $\ell \ge 2^n$. In this case it is impossible to satisfy all clauses simultaneously, i.e., in any truth assignment there is at least one clause equivalence class $\mathcal{C}$ such that all clauses in $\mathcal{C}$ are false.

Among all these classes we pick a class $\mathcal{C}^\*$ that minimizes $|\mathcal{C}^\*|$. From the above discussion we know that the formula $\phi^\*$ obtained from $\phi$ by deleting the clauses in $\mathcal{C}^\*$ is satisfiable and, by our choice of $\mathcal{C}^\*$, we know that $m - |\mathcal{C}^\*|$ is exactly the maximum number of satisfiable clauses of $\phi$.

All of the above can be done in polynomial-time and shows that this version of your problem is not $\mathsf{NP}$-hard, unless $\mathsf{P}=\mathsf{NP}$.
> 1 votes

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


title: Merkle tree sorting leaves and pairs

text:
# Question
Title: Merkle tree sorting leaves and pairs
I am implementing a Merkle tree and am considering using either of the two options.

The first one is sorting only by leaves. This one makes sense to me since you would like to have the same input every time you are constructing a tree from the data, that might not arrive sorted by default.

```
       CAB
      /    \
     CA     \
   /    \    \
  C     A     B
/  \  /  \  /  \
1  2  3  4  5  6

```

The second one is sorting by leaves and pairs, which means that after sorting the leaves, you also sort all the pairs after hashing them, however I'm not entirely sure about the benefits of this implementation (if any).

```
       ACB
      /    \
     AC     \
   /    \    \
  C     A     B
/  \  /  \  /  \
1  2  3  4  5  6

```

I have seen these implementations of Merkle trees in the past but am not sure about their benefits. So why choose one over the other?

# Answer
Further expanding on @Paul Etscheit, sorting the hash pairs simplifies the verification of merkle proofs.

Example: The open zeppelin merkle proof verification smart contract, requires the hash pairs to be sorted. This is made even clearer when you look at their tests.

Merkle inclusion proofs can be verified through a function `function verify(bytes[] proof, bytes root, bytes leaf)`. The function will return true if `root` is equal to the root computed from the leaf and proof nodes.

Using sorted hash pairs means your merkle proof does not needs to contain information about the order in which the child hashes should be combined in. i.e. Your proof can simply be an array of hashes.

For example:

Using merkletreejs and the following merkle tree:

```
└─ 7075152d03a5cd92104887b476862778ec0c87be5c2fa1c0a90f87c49fad6eff
   ├─ e5a01fee14e0ed5c48714f22180f25ad8365b53f9779f79dc4a3d7e93963f94a
   │  ├─ ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb
   │  └─ 3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d
   └─ 2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6
      └─ 2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6

```

Without sorting the hashpairs you need to use `.getProof(<node>)`, which returns a proof of the form:

```
[
  {
    position: 'right',
    data: <Buffer 3e 23 e8 16 00 39 59 4a 33 89 4f 65 64 e1 b1 34 8b bd 7a 00 88 d4 2c 4a cb 73 ee ae d5 9c 00 9d>
  },
  {
    position: 'right',
    data: <Buffer 2e 7d 2c 03 a9 50 7a e2 65 ec f5 b5 35 68 85 a5 33 93 a2 02 9d 24 13 94 99 72 65 a1 a2 5a ef c6>
  }
]

```

When you sort the hashpairs, you can use `.getHexProof(<node>)`, which returns a proof of the form:

```
[
  '0x3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d',
  '0x2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6'
]

```
> 3 votes

# Answer
A bit late to the party, but the second approach can be useful to simplify the merkle-path. When hashing a pair, it's required to know if the leaf is on the left or right side of the pair. This can become quite complex, for example, when implementing multi-leaf inclusion proofs. By sorting the pairs before hashing, it doesn't matter which side the leaf actually has in the pair, as you're applying the same rule every time. Pretty neat solution in my opinion.
> 2 votes

# Answer
The first method is the standard one that I've seen.

I'm not clear on what the purpose of the second method would be, or even exactly how it works. It's not something I've seen before.

I'd suggest you use the first method by default, and if you encounter a situation where it is insufficient or has some problems, post a question asking about the specific requirements you have in that situation.
> 1 votes

---
Tags: algorithms, trees, hash
---


# Question
Title: Why is the probability of a false positive not 0 for Freivald's Algorithm?
Freivald's algorithm (see the wiki) is a randomized algorithm for verifying whether the product of two $n \times n$-matrices $A$ and $B$ yields a given matrix $C$ (i.e. $AB = C$). The way this task is accomplished is to introduce a random vector $\vec{v} \in \mathbb{R}^{n}$ and evaluate whether $$A(Bv) = Cv$$ The claim is that if $AB \neq C$, then $AB v = Cv$ with probability at most $1/2$, and they provide a justification. Their argument for why 1/2 works makes some sense to me. What I don't understand is why this bound can't be improved further by the following argument:

**Claim:** Suppose that $AB \neq C$. Then for almost all choices of $v$ (i.e. with probability $1$), $AB v \neq Cv$.

**Proof of Claim:** Note that $AB v = Cv$ if and only if $(AB-C)v =0$. Let $D = AB-C$. Then $ABv = Cv$ if and only if $v \in \ker(D)$. Since $AB \neq C$, $D$ is not the $0$-matrix meaning that $\dim(\ker(D)) \< n$. Hence, $\ker(D)$ is a proper linear subspace of $\mathbb{R}^{n}$ and therefore has measure $0$. Thus, for almost all choices of $v$, $D v \neq 0$ meaning that $ABv \neq Cv$ with probability $1$.

Q.E.D.

Hence, if $AB v = Cv$, then $AB = C$ with probability $1$. Shouldn't this mean that the probability of failure in Freivald's algorithm is $0$ instead of $2^{-k}$?

Thanks.

# Answer
Algorithms can't work over $\mathbb{R}^n$, as you can't represent real numbers in finite space. Also, you can't pick a number uniformly at random from $\mathbb{R}$. Instead, usually we work over a finite field.

Then we can't do any better. Suppose we are working in the finite field with two elements, $GF(2)$. Suppose that

$$AB - C = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}.$$

Then it is easy to verify that Frievald's algorithm is wrong with probability $1/2$, as $(AB-C)v = 0$ holds with probability $1/2$ when we select $v$ uniformly at random. You can generalize this to a $n\times n$ matrix that is all zeros except for a single entry, and then the probability of false positive is $1/2$.

If you are working over $\mathbb{Q}$, then the same matrix $AB-C$ also provides a similar counterexample. As Greg Martin explains, Freivald's algorithm by definition chooses vectors uniformly at random from $\\{0,1\\}^n$, and then when $v$ is selected from this distribution, $(AB-C)v=0$ holds with probability $1/2$. (And if you are wondering whether it is possible to do better by choosing $v$ differently, there is no way to choose a number uniformly at random from $\mathbb{Q}$, so it's not clear what distribution you would use.)
> 12 votes

---
Tags: algorithms, linear-algebra, randomized
---


# Question
Title: Calculate transfers to equalize balances?
I'm playing a MMORPG where we party hunt, the problem is that at the end of the hunt each person may have different balances depending on what items they wasted and the stuff each one looted.

The game tell us what are our balances in the party, but nothing more... so for example, having something like this as an input:

**Balances:**

* Person A: +132
* Person B: -50
* Person C: +70

I want to obtain the transfers to be made so that we all end up with the same balance, using the example from above:

**Transfers:**

* Person A should transfer 81 to B
* Person C should transfer 20 to B

So A ends up with 51, B ends up with 51 and C ends up with 50.

Is there a known algorithm for this? I would like to make a web app with this calculator.

# Answer
Here is an algorithm that isn't necessarily guaranteed to give the optimal solution but might be effective for small numbers.

Let $\delta\_i$ be the amount that player $i$ is supposed to give: if $\delta\_i\>0$, they are giving away goods; if $\delta\_i$, they are receiving goods. I will assume $\sum\_i \delta\_i = 0$.

In each step, find the smallest set $S$ of players you can find such that $\sum\_{s \in S} \delta\_s = 0$, i.e., the smallest subset that can given goods amongst themselves. Then transfer among the players in $S$. This can be done with $|S|-1$ transfers. (Everyone with a surplus gives to one designated player who has a shortfall; then that designated player gives to everyone else who has a shortfall.)

Now repeat.

If there are $n$ players and you've partitioned the player into $k$ sets $S\_1,\dots,S\_k$, then in total you'll use $n-k$ transfers, so it is in your interest to partition into as many sets as possible, i.e., intuitively to make each set as possible. That's the intuition for why this might be a reasonable strategy.

It won't necessarily find the optimal set of transfers, though. I suspect that finding the optimal set of transfers is (weakly) NP-hard, by reduction from the partition problem, but I haven't tried to check this carefully, so this statement might be incorrect. It might even be strongly NP-hard, by reduction from 3-partition.
> 0 votes

---
Tags: equality
---


title: Give a context-free grammar

text:
# Question
Title: Give a context-free grammar
We know that $L$ = { $w$ $\in$ {a, b}\* $|$ $|w|\_{a}$ \> $|w|\_{b}$ }

This is my answer: $G$ = ({$S$,$A$,$B$},{$a$,$b$},$R$,$S$)

$R$ = S $\to$ $AB$

$A$ $\to$ $aA | Aa |B$

$A$ $\to$ $a | abB | Bab | Bba |aBb|bBa $

But after testing, it seems that writing like this is wrong.

So how should it be written?

https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/

This link can be used to simulate.

# Answer
> 0 votes
Your problem is finding a CFG grammar $G$ for the language $L$ that contains equal number of $a's$ and $b's$ with extra number of $a's$ . $$L=\\{\omega\in \Sigma^\*\mid n\_a(\omega)\>n\_b(\omega)\\}$$

Let $A$ is a variable that derive only $a's$.

Let $E$ is a variable that derive equal number of $a's$ and $b's$.

Let $S$ be start symbol.

As a result we have the following grammar $G$:

$$S\to EAE\mid SS$$ $$E\to EE\mid aEb\mid bEa\mid \lambda$$ $$A\to aA\mid a$$

---
Tags: context-free
---


# Question
Title: Construct a DFA which accepts all strings containing both 11 and 010 as substrings
I have drawn the DFA for language L1 containing 11 as substring and language L2 containing 010 as substring. But I don't know how to concatenate these two to get the final answer. Please help!

# Answer
There are two ways to go about this. Firstly, you could try constructing the product automaton M(Q, Σ, δ, q, F), where Q is the cartesian product of the sets A(Q) and B(Q) where, A is an automaton which accepts all strings having 11 as a substring and B accepts all strings having 010 as a substring. A state S(p, q) in M is final if p ∈ A(F) and q ∈ B(F). Secondly, it's not hard to convinced yourself that for a string to be accepted by M, the string could either have 11 followed by some substring and then a 010, or the other way around. This intuition might help you make a DFA, without having to construct the product automaton. Here's the DFA.
> 2 votes

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


# Question
Title: Trouble to understand the proof of greedy algorithm for set cover
**Problem definition:** Given a universe $U$ of $n$ elements, a collection of subsets of $U$, $S = \\{S\_1,..., S\_k\\}$, and a cost function $c: S \to Q^{+}$. Find a minimum cost subcollection of $S$ that covers all elements of $U$.

**The provided algorithm (Approximation algorithms - Vijay V. Vazirani)**

**Part of the proof where I have trouble to understand**

**My question**

I have a difficult time to understand the last in equality, if $|\bar{C}| \leq n - k + 1$, why does $\cfrac{OPT}{|\bar{C}|} \leq \cfrac{OPT}{n - k + 1}$ hold?

# Answer
You have that $|\bar{C}| \ge n-k +1$, not $|\bar{C}| \le n-k+1$. The quantity $\frac{OPT}{|\bar{C}|}$ can only increase when we replace $\bar{C}$ with something that is at most as large. In our case we replace it with $n-k+1$.

Then: $$ \frac{OPT}{|\bar{C}|} \le \frac{OPT}{n-k+1}, $$ as desired.
> 2 votes

---
Tags: approximation, set-cover
---


# Question
Title: How do you justify making algorithm subroutines more efficient when Big-O notation only includes the dominant term?
I don't really understand time complexity, and wanted some clarification in this hypothetical situation.

If I were being given items one by one, and I wanted a list of them all in the reverse order I got them in, I could add each item to an ArrayList, then reverse it. Both of these operations are $O(n)$ in time complexity, and therefore my total is $O(2n)$, which is just $O(n)$.

However, I could also add each item as I got it to a Stack, and since Stacks are LIFO, it's already reversed once I have all of the items. This skips the $O(n)$ ArrayList reversing, but is still $O(n)$ overall since getting the n items was $O(n)$.

I think the second option would be better, since I'm avoiding an $O(n)$ subroutine, but how can I say that I have made my algorithm more efficient?

In the context of explaining how my second algorithm is more efficient, is it appropriate to just say I have made it more efficient by removing an $O(n)$ subroutine?

# Answer
Asymptotic notation is not fine-grained enough capture the difference between $n$ and $2n$ operations, and there are good theoretical reasons not to care about multiplicative constants unless we want to specify the nitty-gritty details of the model of computation at hand and of our algorithms.

That said, you could say that both algorithms require $\Theta(n)$ time but the second version has a "smaller hidden multiplicative constant"\*.

---

\*Be careful on how the stack and the array lists actually implemented when you estimate the number of operations down to multiplicative constants. There might be more going on under the surface than what meets the eye. For example a common implementation of a list/stack that is backed by a dynamic array might have a final capacity of $2n$, and the overall number of elements written to it might be about $4n$.
> 3 votes

# Answer
You might measure that a particular implementation of an algorithm on a particular computer takes say $315 n^2$ nanoseconds, plus/minus 10%. And an implementation of a different algorithm on the same computer is measured to take $409 n^2$ nanoseconds, plus/minus 6%. I guess you will prefer the first algorithm.

Big-O notation and asymptotic complexity ignores what particular computer you are using, what programming language and compiler / interpreter etc. In this case it would be just interested in the $n^2$ term. So both algorithms would be judged to be equivalent in execution time.

This is quite reasonable because otherwise you'd find it hard to judge an algorithm independent of the hardware that is used. Actually, the difference in speed in my example is so little, it is absolutely possible that on a different computer the second algorithm would be faster.

Note that if you want to make an algorithm just twice as fast, you often have the choice to write code that runs faster (which may cost you because it can be hard work to make code faster), or instead pay for a faster computer that runs twice as fast. If an algorithm is asymptotically slower, buying a faster computer isn't going to help.
> 2 votes

---
Tags: algorithm-analysis, semantics
---


# Question
Title: Complexity of binary search on contiguous, nonoverlapping segments of an array
Suppose that we have an $n$ sized array that it broken into $m$ contiguous, non-overlapping chunks such that when the chunks are concatenated, they form the original array.

Say we perform a binary search individually on `chunks[0]`, `chunks[1]`, `chunks[2]`..., `chunks[m-1]`. What is the complexity here? We perform binary search $m$ times. So it seem the cost is

$$ \sum\_{i = 0}^{m - 1} \log (L\_i) \\ \sum\_{i = 0}^{m - 1} L\_i = n $$

where $L\_i$ is the length of `chunks[i]`

But how do we write big O in terms of $n$ here?

# Answer
By Jensen's inequality you have: $$ \frac{1}{m} \sum \log L\_i \le \log \left( \frac{1}{m} \sum L\_i \right) =\log\left(\frac{n}{m}\right). $$ Therefore $\sum \log L\_i \le m \log \frac{n}{m}$ and the overall time complexity is $O(m \log \frac{n}{m})$.

Notice that this upper bound is tight (for example when all $L\_i$s are roughly equal).
> 2 votes

---
Tags: time-complexity
---