# Question
Title: Decision Tree Learning Deviation - Russell and Norvig
I am working through the Russell and Norvig AI book and came across the following on the top of page 706.

The section concerns Decision Tree pruning and testing a given attribute against the null hypothesis. The example at hand deals with a binary decision tree and $p\_k$ denotes the number of positive ("yes") responses in the training data and $n\_k$ the number of negative ("no") responses in the training data with respect to the training examples that are in the subset of values that took on the value $v\_k$ associated with the $k$th attribute of a vector $\vec{x}$ of length $n \times 1$. Furthermore $p$ and $n$ simply denote the number of positive and negative outputs of the training data.

The authors state the following:

> We can measure the deviation by comparing the actual numbers of positive and negative examples in each subset $p\_k$ and $n\_k$ with the expected numbers $\hat{p}\_k$ and $\hat{n}\_k$, assuming true irrelevance:
>
> \begin{align\*} \hat{p}\_k&=p\times \frac{p\_k+n\_k}{p+n}\\ \hat{n}\_k&=n\times \frac{p\_k+n\_k}{p+n}\\,. \end{align\*}
>
> A convenient measure of the total deviation is given by
>
> $$\Delta = \sum\_{k=1}^d \frac{(p\_k-\hat{p}\_k)^2}{\hat{p}\_k} + \frac{(n\_k-\hat{n}\_k)^2}{\hat{n}\_k}\\,.$$

**My questions:**

I think I understand the use of the estimators. We are basically assuming a uniform distribution on $p$ and $n$ and so within each subset of training examples that have the attribute value $A\_k$ equal to $v\_k$ we simply scale the overall $p$ and $n$ by the total proportion of samples in that set. In essence, we are assuming that, for instance, if $p=10$ and $n=5$, then those proportions hold in our subsets, and so the expected value of $\hat{p}\_k$ is simply scaled by the size of the subset.

This leads me to also understanding the numerator of the measure of deviation $\Delta$. We use the squared deviation of the expectation from the observed value. My question then is why do the estimators appear in the denominator? This seems very close to an equation for variance, and I assume that the estimators are somehow scaling $\Delta$, but how can we justify that?

# Answer
> 2 votes
TL;DR: They are basically doing a chi-squared test to compare the distributions.

In more detail: Let's break this down into two parts, $\Delta = \Delta\_1 + \Delta\_2$ where

$$\begin{align\*} \Delta\_1 &= \sum\_{k=1}^d \frac{(p\_k-\hat{p}\_k)^2}{\hat{p}\_k}\\ \Delta\_2 &= \sum\_{k=1}^d \frac{(n\_k-\hat{n}\_k)^2}{\hat{n}\_k}. \end{align\*}$$

Then $\Delta\_1$ is the test statistic for a chi-squared test of the goodness of fit between the two distributions $p\_k$ and $\hat{p}^k$. Similarly, $\Delta\_2$ is the test statistic for the goodness of fit between $n\_k$ and $\hat{n}\_k$.

If the distribution $p\_k$ is similar to $\hat{p}\_k$, and $n\_k$ is similar to $\hat{n}\_k$, then $\Delta$ will be small (the former means that $\Delta\_1$ will be small, and the latter means that $\Delta\_2$ will be small). Conversely, if $p\_k$ is not similar to $\hat{p}\_k$, or $n\_k$ is not similar to $\hat{n}\_k$, then $\Delta$ will be large (in the former case, $\Delta\_1$ will be large; in the latter case, $\Delta\_2$ will be large).

So this is a convenient measure of the total deviation between these distributions: a convenient way to get a single number to help us measure the extent to which both $p\_k$ is similar to $\hat{p}\_k$ and $n\_k$ is similar to $\hat{n}\_k$.

The chi-squared test is a standard test for goodness of fit, so its test statistic is a reasonable choice here. As for why the chi-squared test is a good test for measuring goodness of fit, you can read the standard literature on the chi-squared test.

---
Tags: machine-learning, artificial-intelligence, decision-tree
---


# Question
Title: Relation between size of hashtable and number of values to keep expected number of collisions below/equal to 1
This is an exam question from my algorithms and data structures course.

You imagine an hash function with h: U-\>{0,..m} (this is from the original question, but i think m-1 would be correct) and n values to hash. You want to keep the expected number of collisions below or equal to 1. How do you determine m in dependence to n.

My initial idea was following formula to determine the number of collisions: $n- E(\text{occupied locations}) = n-m+E(\text{empty locations}) \\\$
$= n-m+m(1-\frac{1}{m})^n$

For our question this would give: $ 1 \geq n-m+m(1-\frac{1}{m})^n$

I know that following solution would have been correct (and i know why now):

$E\[x\]=\frac{n(n-1)}{2} \cdot \frac{1}{m} = m \geq \frac{n(n-1)}{2}$

Well i know i did not solve the first Equation for m (i do not know how), but my question is if both solutions would be correct and if not why?

I got the first Equation from Darthmouth (\[Link\]:https://math.dartmouth.edu/archive/m19w03/public\_html/Section6-5.pdf)

# Answer
> 1 votes
No, your solution is wrong. The expected number of collisions is not $n- E(\text{occupied locations})$, so you went wrong in the first step of your approach. Try working through a small example or two and hopefully you will see why.

It's possible that your confusion has to do with how we count the number of collisions. If items A,B,C all go into the same hash bucket, we consider that as 3 collisions: A,B are a collision, B,C are a collision, and A,C are a collision.

---
Tags: data-structures, probability-theory, hashing
---


# Question
Title: Is there any bitwise multiplication algorithm that is sub O(n^2)?
The following program implements a simple algorithm for binary multiplication:

```
-- Numbers as infinite streams of bits, least significant bits first
data Bits
  = O Bits
  | I Bits

-- Increments a number
suc :: Bits -> Bits
suc (O xs) = I xs
suc (I xs) = O (suc xs)

-- Adds two numbers
add :: Bits -> Bits -> Bits
add (O xs) (O ys) =      (O (add xs ys))
add (O xs) (I ys) =      (I (add xs ys))
add (I xs) (O ys) =      (I (add xs ys))
add (I xs) (I ys) = (suc (I (add xs ys)))

-- Multiplies two numbers
mul :: Bits -> Bits -> Bits
mul (O xs) ys =        (O (mul xs ys))
mul (I xs) ys = add ys (O (mul xs ys))

```

(The complete program can be seen here.)

This algorithm, although simple, has `O(N^2)` complexity. Are there similarly simple algorithms with lower complexities?

# Answer
> 3 votes
Is Karatsuba algorithm simple enough? It's complexity is $O(n^{1.59})$.

---
Tags: algorithms, number-theory, multiplication
---


title: Minimizing $\max | x_i - \mu |$

text:
# Question
Title: Minimizing $\max | x_i - \mu |$
How can we construct an algorithm which finds $\mu$ that minimizes $\max | x\_i - \mu |$ in a linear time for an array of numbers $\[x\_1, x\_2, \ldots, x\_n\]$?

I take $g = \max\_{i\in \\{1,\ldots,n \\} } x\_i$ and $l = \min\_{i\in \\{1,\ldots,n \\} } x\_i$, and $\mu = l + \frac{(g - l)}{2}$

Is it true and why it minimizes the function?

# Answer
Since $|x| = \max (x, -x)$ for any $x \in \mathbb{R}$, we have $|x\_i - \mu| = \max(x\_i - \mu, \\, \mu - x\_i)$. Therefore, $$ \max\_i |x\_i - \mu| = \max \left(\max\_i (x\_i - \mu), \\, \max\_i (\mu - x\_i) \right) = \max (g - \mu, \\, \mu - l), $$ where $g = \max\_i x\_i$ and $l = \min\_i x\_i$. Finally, the function $\max(g - \mu, \mu - l)$ has minimum at $\mu = \frac{l + g}{2}$.
> 3 votes

---
Tags: algorithms, optimization
---


# Question
Title: Finding the Entropy of a random experiment with probability of $\frac{1}{3}$
Entropy is the randomness collected by an operating system or application for use in Cryptography or other uses that require random data. The formula for Entropy is $$H(p\_1, ..., p\_k)=-\sum\_{i=1}^{k} p\_i\log\_2(p\_i)\[bit\]$$

So if I were to calculate the Entropy of a coin toss. it would be $$H(\frac{1}{2}, \frac{1}{2})=-(\log\_2(\frac{1}{2})+\frac{1}{2}\log\_2(\frac{1}{2}))=-(0-1)=1 Bit$$

But why is there a $\frac{1}{2}$ before the $\log$? Also if I were doing an experiment where the probability of an outcome is $\frac{1}{3}$ and there are $3$ outcomes, so would the entropy be

$$H(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})=(\log\_2(\frac{1}{3})+\frac{1}{3}\log\_2(\frac{1}{3})+\frac{1}{3}\log\_2(\frac{1}{3}))$$

# Answer
> 1 votes
Your formula is totally inapplicable in computer randomness harvesting. I think that people use it because it's easy to write down. Even then, it's not really usable - what's *i* exactly? For any non trivial application, there are correlations. Try using this formula for the English language. No you can't say there are just 26 letters as they are hugely correlated. There are two, three, four letter combinations, and then there are words and sentences that have lexological and grammatical structure. I don't know what you do with full stops. The entropy rate will very much depend on who wrote the words and about what. If you try the Shannon formula in it's most simplistic typical use case, "1111111111...0000000000..." has exactly 1 bit/bit of entropy. Clearly it doesn't.

Entropy harvesting by a computer kernel consists of sucking up hardware device interrupts including keyboard presses. Non of this is uncorrelated. The official cryptographic term is non IID (non independent and identically distributed). And for measurement of such non IID entropy, there is no set standard. The best we have currently is either direct compression, or the NIST SP800-90B\_Entropy Assessment tools (which also include compression as one of the tests). They may have been written by a chap using up his spare time.

Is von Neumann's randomness in sin quote no longer applicable? is a currently open question featuring such entropy measurements. So essentially coin toss randomness is completely different to operating system randomness.

---
Tags: randomness, information-theory, cryptography, entropy
---


# Question
Title: How to derive dependently typed eliminators?
In dependently-typed programming, there are two main ways of decomposing data and performing recursion:

* **Dependent pattern matching**: function definitions are given as multiple clauses. Unification ensures that all omitted cases are impossible, and an external solver ensures that recursion is well-founded.
* **Eliminators**: Each inductive datatype $D$ has an associated constant $E\_D$, which acts as an induction principle, and as recursive function that decomposes values of type $D$. These are more verbose, but have the advantage of being total (all cases are covered by $E\_D$) and terminating by construction.

I've seen eliminators for common datatypes, like $Nat$, where the eliminator is basically mathematical induction, or $List$, where the eliminator is basically a fold.

I've been reading several papers on dependent pattern matching, and many refer to type theories in which datatypes can be defined, and eliminators are provided by the theory. For example, Eliminating Dependent Pattern Matching describes how UTT is based on eliminators, and how pattern matching can be converted to elimination in the presence of axiom $K$. My understanding is that, once a datatype is defined, the theory provides the eliminator.

What I haven't found (or at least, haven't recognized if I've seen it) is a good description of how one can derive the eliminators, both their types and their semantics.

Can someone point me to a reference that describes how one can obtain an eliminator from the definition of a datatype?

# Answer
The canonical reference for this is Peter Dybjer, *Inductive Families*, which gives a pretty comprehensive treatment of inductive families based on eliminators.
> 8 votes

# Answer
You might find some of our recent papers on this useful, as we derive eliminators for lambda-encoded datatypes. For example, see this one for generic derivation of eliminators, and this one for the basic technique applied just to the Nat type.
> 6 votes

---
Tags: reference-request, recursion, type-theory, dependent-types, inductive-datatypes
---


# Question
Title: The importance of the membership problem
Given a word $w$ and a language $L$, we want to check if $w\in L$. This is called the *membership problem*. Why is the membership problem important?

# Answer
The importance is that *any* computational problem where the answer is yes or no can be phrased as a membership problem in a language. The language is the set of strings for which the answer is yes.
> 8 votes

# Answer
Suppose we show that a language $L$ belongs to some class $C$ of languages (say $L$ is regular). So what? Why would we bother showing that?

One reason is because we want to answer membership queries – given a word $x$, is it in $L$? For example, $L$ might be the context-free fragment of the syntax of a programming language, and we would like to be able to parse source code.

For an arbitrary language $L$, it is hopeless to answer the membership problem efficiently (or even at all). However, for some classes of languages, such as regular languages and context-free languages, efficient algorithms do exist. This is why these classes are important in the first place.
> 4 votes

# Answer
What computation means to us today is that we write programs on the computer and finally run them.Now,the program is basically an algorithm that is implemented through a language,and there are a great many class of problems that do not allow algorithms to compute them or solve them.Now the set membership problem that we consider is carried upon sets of finite strings.when we write a program,the input is in the form of strings and output is also in the form of strings.So,if the set membership problem on the set of inputs and outputs allow algorithms to compute them then we say the program is capable to carry out its job else not.Hence the study of set membership problem on finite strings is a central problem in computer science.
> -1 votes

---
Tags: automata, decision-problem
---


# Question
Title: How to prove that a problem can't be solved in time $\mathcal O(n^{1/2 - \epsilon})$?
I have seen many problems in graph theory and in other related fields which admit a sublinear (in input size) running time $\mathcal O(n^{1/2})$ algorithm, where $n$ is the input size. I am not sure but to me it seems that fine grained complexity may be one possibility to prove that there is no algorithm with running time $\mathcal O(n^{1/2 - \epsilon})$, where $\epsilon$ is greater than 0. The model of computation is RAM.

**Question :** How to prove that a problem can't be solved in running time $\mathcal O(n^{1/2 - \epsilon})$?

# Answer
> 2 votes
One possibility to get *conditional hardness* is to give a (fine-grained) reduction from a problem that is known to be hard in some sense. The result will then something along the lines of "if problem X admits an algorithm running in time $O(n^{1/2-\epsilon})$, then problem Y can be solved within some specific time bound". The "specific time bound" should be something we don't know how or believe that can be achieved.

The survey of Williams \[1\] you refer to contains several examples. As you can see in Figure 1, there are several problems in computational geometry, graph theory, and logic that could be or have been reduced from. Now, for some problems, there is theoretical evidence and belief in the community that the conjectures indeed hold (like ETH). Other ones are less often believed like SETH.

It is an open problem to draw more connections between these problems (see Section 2.6 in \[1\]), i.e., to find more evidence for hardness other than "here's an isolated problem nobody has been able to find a faster algorithm for decades". For more in this direction, see e.g., this question on CSTheory.

---

\[1\] Virginia V. Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis. IPEC 2015 invited talk.

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


title: Testing if a given DAG is a lattice

text:
# Question
Title: Testing if a given DAG is a lattice
I am given a directed acyclic graph (DAG) with a unique source and sink. Is there an efficient way to test whether the partial order represented by this graph is a lattice?

In other words, I need to test whether any two vertices have a *unique* least upper bound and greatest lower bound.

From brief browsing, I found an $O(n^3)$ algorithm that explicitly computes the least upper bound of every pair of elements. Is there a better test?

# Answer
The DAG represents the *covering relation* $\lessdot$ of a partial order $\<$, also known as its Hasse diagram. An element $y$ covers an element $x$, in symbols $x \lessdot y$, if $x \< y$ and no $z$ satisfies $x \< z \< y$.

Suppose that $Y$ is a non-empty set of elements in the partial order which is upwards closed (if $z \in Y$ and $u \> z$ then $u \in Y$), and in which any two elements have a join. Let $y \notin Y$ be such that $Y \cup \\{y\\}$ is also upwards closed. Then for all $z \in Y$, $$ z \lor y = \min\_{y \lessdot u} z \lor u, $$ if the minimum exists. (This is Lemma 1 in Fast recognition of rings and lattices by Goralcik, Goralcikova, Koubek, and Rodl.)

This suggests the following algorithm for finding whether any two elements have a join (we can similarly determine whether any two elements have a meet):

* Arrange the elements in decreasing topological order $x\_1,\ldots,x\_n$.
* For $i=1,\ldots,n$, attempt to compute $x\_j \lor x\_i$ for all $j \< i$.
* Return TRUE if all attempts were successful.

In order to compute $x\_j \lor x\_i$, we use the following algorithm:

* Let $u\_1,\ldots,u\_m$ be the elements covering $x\_i$.
* Set $a \gets x\_j \lor u\_1$.
* For $i=2,\ldots,m$, check whether $x\_j \lor u\_i \leq a$ (i.e., if $(x\_j \lor u\_i) \lor a = a$), and if so, set $a \gets x\_j \lor u\_i$.
* Verify that $a \leq x\_j \lor u\_i$ (i.e., that $a \lor (x\_j \lor u\_i) = x\_j \lor u\_i$) for all $i=1,\ldots,m$.
* If verification was successful, return $a$.

Finding a topological ordering takes time $O(n+|E|)$. If we denote by $C(x)$ the number of elements covering $x$, then the rest of the algorithm runs in time proportional to $\sum\_{i=1}^n iC(x\_i) \leq n|E|$, since $\sum\_i C(x\_i) = |E|$. In total, we get a running time of $O(n|E|)$.

It is known that the covering relation of a semilattice contains $O(n^{3/2})$ edges (see Statement 3 in the paper mentioned above). Hence we can abort the algorithm if $|E|$ is larger, and otherwise we can assume that $|E| = O(n^{3/2})$, and so the algorithm above runs in time $O(n^{5/2})$. This is Theorem 2 in the paper mentioned above.

Concluding, we can determine whether a DAG is the covering relation of a lattice in time $O(n^{5/2})$. A recent survey by Freese, Algorithms for finite, finitely presented and free lattices mentions obtaining faster algorithms as an open problem (Problem 1 in the survey).
> 3 votes

# Answer
Although my experience involves DAGs where only *one* of the directions has a unique source/sink (called 'top'), perhaps my info will be relevant nonetheless.

For a DAG with a single source, we're mostly concerned with ensuring every vertex pairing has a unique GLB. Our production NLP analysis tools must quickly compute and produce the BCPO lattice from the initial, human-authored DAG which typically doesn't meet that condition. Fortunately, such a transform is guaranteed to exist. The canonical method used for computing it is given in the following famous paper:

Efficient Implementation of Lattice Operations (.pdf)

I use the method described there to prepare the type-inheritance DAG into a lattice so that its nodes--including the added GLBs--(e.g., each a so-called 'type') can be used as node values in a further, disjoint set of DAGs called *feature structures* which represent the actual linguistic entities subject to graph-unification parsing. Without the step of ensuring that every 'type'-pairing has a unique result (or 'bottom', meaning incompatible types), type unification--and thus the follow-on graph unification--become non-deterministic.

Perhaps the algorithm described in the paper will give you an insight into how to detect the condition more efficiently?
> 0 votes

---
Tags: graphs, lattices, order-theory
---


# Question
Title: What is a graceful algorithm to generate this number sequence
```
0                   0
1                   1
1 0                 2
1 0 0               4
1 0  1              5
1 0 0 0             8
1 0 0 1             9
1 0 1 1             11
1 0 0 0 0           16
1 0 0 0 1           17
1 0 0 1 1           19
1 0 1 0 1           21
1 0 1 1 1           23
1 0 0 0 0 0         32
1 0 0 0 0 1         33
1 0 0 0 1 1         35
1 0 0 1 0 1         37
1 0 0 1 1 1         39
1 0 1 0 0 0         40
1 0 1 1 1 0         46

```

So the idea of this sequence is based on patterns in the binary. Namely we don't ever repeat patterns. So if you have 1 0, you will never include 1 0 1 0 or 1 0 1 0 1 0 And you also throw out all rotations of a binary sequence within a given digit length. If you have 1 1 0 0 you will never have 1 0 0 1

What is a minimalistic algorithm for generating this sequence and does this sequence have a name? My interest in this sequence is musical as this is a concise list of rhythms in order of complexity.

# Answer
I think the below algorithm should be workable. It doubles/triples/quadruples/quintuples/... what we've generated so far to find disallowed sequences. Then it generates all possible sequences by attaching a 0 and a 1 to every sequence found in the previous iteration and removes the disallowed sequences. Then it checks for rotations and removes those too.

First round, generate 1 and 0.

Second round, double these to 11 and 00. These are the strings that are not allowed in this round.
Find possible permutations. (1-\>{10,11} 0-\>{00,01}). Remove the disallowed ones we just figured out.
We now have 1, 0, 10, and 01. Find rotations: 10 and 01 are rotations, so remove them but leave one. Which? Let's say 01, as in the example.

Third round, we have 1, 0, 10. We're aiming for a three-digit sequence, and doubling the two-digit sequences would get us a four-digit sequence. Tripling 1 and 0 gets us 111 and 000, which we disallow.
Find possible permutations. (10-\>{100,101}). Nothing to remove.
We now have 1, 0, 10, 100, 101. Find rotations: no rotations.

Fourth round, we have 1, 0, 10, 100, 101. Aiming for four digits. We do doubling and quadrupling to get the disallowed four-digits sequences: 1111, 0000, 1010.
Find possible permutations. (100-\>{1000, 1001}, 101-\>{1010, 1011}). Remove disallowed 1010.
We have 1, 0, 10, 100, 101, 1000, 1001, 1011. Find rotations: no rotations.

One note about when you have to decide which rotations to keep: In the above example we had to decide between "10" and "01". Let's see how these sequences would develop:

10-\>*100*, 101
01-\>*010*, 011

100-\>*1000*, **1001**
101-\>1010, \_1011\_

011-\>**0110**, \_0111\_
010-\>*0100*, 0101

Iterating "rotated sequences" produces rotations of what the other "rotated sequence" would have produced, so I believe it doesn't matter which rotation you keep.

---

**Update:** This seems to have something to do with Lyndon words (https://en.wikipedia.org/wiki/Lyndon\_word). As I couldn't find a decent list of binary Lyndon words on the internet, I used the Python code I found here: https://gist.github.com/dvberkel/1950267 to generate some more.

I've modified it a bit to make it easier to use (removed one import and changed `main` function to immediately start generating binary Lyndon words). I've also added a small Perl script to check whether your words are Lyndon words: https://gist.github.com/qiqitori/31175ab58d099ac4ff7573f34e7344d5

Call the Python script using e.g. `python lyndon_generator.py | head -n 1010`
Call the Perl script using e.g. `perl lyndon.pl`

Here's what the Perl script outputs:

```
Found rotation 1 of 1 (1) at index 1
Found rotation 01 of 2 (10) at index 2
Found rotation 001 of 4 (100) at index 3
Found rotation 011 of 5 (101) at index 4
Found rotation 0001 of 8 (1000) at index 5
Found rotation 0011 of 9 (1001) at index 6
Found rotation 0111 of 11 (1011) at index 7
Found rotation 00001 of 16 (10000) at index 8
Found rotation 00011 of 17 (10001) at index 9
Found rotation 00111 of 19 (10011) at index 11
Found rotation 01011 of 21 (10101) at index 12
Found rotation 01111 of 23 (10111) at index 13
Found rotation 000001 of 32 (100000) at index 14
Found rotation 000011 of 33 (100001) at index 15
Found rotation 000111 of 35 (100011) at index 17
Found rotation 001011 of 37 (100101) at index 18
Found rotation 001111 of 39 (100111) at index 20
Found rotation 000101 of 40 (101000) at index 16
Found rotation 010111 of 46 (101110) at index 21

```

As we can see, index 10 and 19 are missing, but I would bet that the next two numbers in your sequence would be equivalent to index 10 and 19.
> 1 votes

# Answer
(This is not meant as a separate answer, but rather as a long comment on the discovery of colleague sneep.)

The sequence described in the question are indeed basically the Lyndon words, but rotated by one character: instead of `00111` you have `10011`, moving the final `1` to the first position of the string, and in general Lyndon $x{\tt 1}$ appears in your list as ${\tt 1}x$. The reason is of course that in this way the string unambiguously represents a number.

Lyndon words are the strings that are smaller than all their rotations (and hence are non-periodic). Let us check that this gives the same words, in the sense that the minimal word that starts with a `1` (your definition) is the minimal (Lyndon) word that has its final `1`moved to front. Using $\<$ for lexicographic order, we have ${\tt 1}x\<{\tt 1}y$ iff $x\<y$ iff $x{\tt 1}\<y{\tt 1}$, as we wanted.

Of course we use here that Lyndon words end with `1`. Indeed, if a word ends with a `0` it has say $n$ leading zero's, and it is of the form ${\tt 0}^n{\tt 1} y {\tt 0}$ which is not lexicographically less than its rotation ${\tt 0}^{n+1}{\tt 1} y$.

As sneep noted your list is missing some elements like `10010` and `100110`.

The online encyclopedia of integer sequences has several items related to Lyndon words, most importantly the list of Lyndon words and the number of Lyndon words of certain length.
> 1 votes

---
Tags: algorithms, binary
---


title: $T(n) = 2T(n-1)$ Recurrences

text:
# Question
Title: $T(n) = 2T(n-1)$ Recurrences
What would be the complexity of the following recurrence?

$$T(n) = 2T(n-1)$$

# Answer
> 1 votes
*Note: The original version of the post included the initial values $T(0) = 0$ and $T(1) = 1$.*

If $T(n) = 2T(n-1)$ for all $n \> C$ then, as you can prove by induction, $$ T(n) = 2^{n-C} T(C). $$ In particular, in your case $T(n) = 2^{n-1}$. Note that given your initial values, the recurrence $T(n) = 2T(n-1)$ cannot hold for $n=1$; presumably it holds for all larger $n$.

You are asking for the *complexity* of the recurrence. *Recurrences have no such thing as complexity.* A recurrence might describe the running time of an algorithm, and then its solution is the time complexity of the algorithm. But a recurrence can describe any number of things, or even be completely abstract.

# Answer
> 0 votes
i don't know what do you mean about complexity of reccurence but if you want to find the closed form you can use the backward substitution method:
$T(n) = 2T(n-1)$
and then expand the $T(n-1)$:
$T(n) = 2(2T(n-2))$
and after that expand $T(n-2)$:
$T(n) = 2(2(2T(n-3)))$
...
$T(n) = 2^nT(0) $
and if you have $T(0) = C$ as a base case, your closed form would be: $T(n) = C2^n$

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


# Question
Title: Problem with forming a context-free grammar describing a language
I've been trying for hours to figure out, how to form a CFG describing this language $L$: $$L=\\{ w\in\\{a,b\\}^\* \mid w\text{ is of the form }a^nxb^{n+2}\text{, where }x\text{ is a string of length }3\text{ in }\\{a,b\\}^\* \\}.$$

The problem I'm having is related to the first $n$ of $a$'s. I can't wrap my head around how can this be described properly, since the $x$ can also contain 3 $a$'s.

This is my current solution. It does not work because it doesn't take the $n$ $a$'s to the front.

```
A -> aB | bB
B -> aC | bC
C -> aD | bD
D -> bE
E -> bF
F -> bF | _

```

# Answer
$S \to aSb \mid Abb, A \to aaa \mid aab \mid \ldots \mid bbb.$ That's it. First create an equal number of $a$s and $b$s with $S$. Eventually go to the $Abb$ rule creating two extra $b$s and then terminate with $A$ to any string of length $3$.
> 2 votes

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


# Question
Title: Knapsack Greedy Approximation: Worst Case
I am currently studying approximation algorithms and I have run into an issue with a study problem.

The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, where it sorts by the value/weight ratio, and picks the first item in this list that pushes the weight over the limit, and then picks either all the previous items or this particular item, whichever has a greater value.

The claim is that there is at least one case where this algorithm provides a value half that of the optimal value, but after many fruitless attempts I don't see a way to do this.

I have tried many value/weight pairs of 1/1 with a last pair of 5/6, resulting in a ratio of 5/9. Close, but even if I continue this process I am only going to approach a ratio of 1/2, but never achieve it.

Any hints as to how to proceed?

# Answer
> 7 votes
The approximation ratio is always *strictly* larger than $1/2$. Let $p\_1,\ldots,p\_{k-1}$ be the values of the items picked by algorithm, and let $p\_k$ be the value of the next item which would have been picked had it fit. Let $\alpha$ be the fraction of $p\_k$ that does fit – so $\alpha \< 1$. These lecture notes (Claim 2) show that $$ p\_1 + \cdots + p\_{k-1} + \alpha p\_k \geq OPT, $$ where $OPT$ is the optimal solution. In particular, $$ p\_1 + \cdots + p\_{k-1} + p\_k \> OPT. $$ The algorithm picks either items $1,\ldots,k-1$ or only item $k$, and there is some choice that results in strictly more than $OPT/2$.

# Answer
> 1 votes
Let's say the knapsack capacity is $2w$. For some small $e\>0$, let's say we have three items:

* value $w+4e$, weight $w+2e$
* value $w+2e$, weight $w+e$
* value $w-e$, weight $w-e$

The greedy algorithm has value $w+4e$. But, the maximum attainable value is $2 w + e$. When $e\to 0$, the approximation ratio approaches 2.

---
Tags: algorithm-analysis, approximation, greedy-algorithms, knapsack-problems
---


# Question
Title: Leftist Tree initialization in O(n) time
In the book *Handbook of Data Structures and Applications*, section 5.2.5, (copy of the relevant section available here) about leftist queues, the author(s) state the following:

> For the complexity analysis of of the initialization operation, assume, for simplicity, that n is a power of 2. The first n/2 melds involve max HBLTs with one element each, the next n/4 melds involve max HBLTs with two elements each; the next n/8 melds are with trees that have four elements each; and so on. The time needed to meld two leftist trees with 2 i elements each is $\mathcal{O}$(i + 1), and so the total time for the initialization is $$\mathcal{O}(n/2 + 2 (n/4) + 3(n/8) + \ldots) = \mathcal{O}(n\sum \frac{i}{2^i}) = \mathcal{O}(n)$$

However, it seems to me that the summation iterates from i = 0 to $\log(n)$: $\sum\_{i=0}^{\log(n)}$. This means it varies based on n, which in turn means the algorithm doesn't achieve $\mathcal{O}$(n) time as claimed but instead $\mathcal{O}(n \sum\_{i=0}^{\log(n)} \frac{i}{2^i})$ time.

Am I misunderstanding something? I've found other explanations online stating $\mathcal{O}$(n) time for this sort of mass initialization is possible, but this is the only proof I've found so far.

# Answer
The succession $a\_i = 2^{-i}i$ is absolutely convergent.

In more elementary terms:

$$ \frac{n}{2} \le \sum\_{i=1}^{\log n} \frac{ni}{2^i} \le n\sum\_{i=1}^{\infty} \frac{i}{2^i} = n\sum\_{j=1}^{\infty} \left( \frac{1}{2^j}\sum\_{i=1}^{\infty} \frac{1}{2^i} \right) = 2n $$
> 2 votes

---
Tags: data-structures, time-complexity, priority-queues
---


# Question
Title: Can an operating system without api still work?
In theory operating system is a special program run by itself without help so that also mean normal program can still run by itself mean that the need for api is not must have so finally can we have an os without api ?

# Answer
No, the other programs sit on top of the operating system(OS) and the OS runs on top of the hardware. The OS provides these programs with basic resources the programs will need to run like CPU, memory and input/output from for e.g. mouse and keyboard. The API is the only way they can get these resources, so normal programs will not be able to work on an OS without API. The new browser analogy is wrong since using IE is just a way to download the new browser files(can do it from command line, without IE). New browser still needs the OS to run.
> 2 votes

---
Tags: operating-systems, api-design
---


# Question
Title: Why does A* fail to find the fastest path when it reaches the goal?
I'm trying to understand how A\* works on some simple examples, and something struck me as odd. I could fairly easily come up with situations in which A\* "failed". Here is an example:

Take a 2x2 grid, in which you can only move in one of 4 (orthogonal) directions (no diagonal movement). Denote the node at (0, 0) by A, the node at (1, 0) by B, the node at (0, 1) by C, and the node at (1, 1) by D (so that it looks like `C D
A B` The weight going from A to B is 3, the weight going from A to C is 2, the weight from B to D is 1, and the weight from C to D is 3. Let the start node be A and the goal be D. Let our heuristic simply be Euclidean distance (or Manhattan distance, both produce the same result in this instance).

So, if my understanding of A\* is correct, we start with an open set containing only A, so we pop A. It's neighbours are B and C, which have g values g(B) = 3, g(C) = 2, and h values h(B) = 1, h(C) = 1. So the f-values are f(B) = 3 + 1 = 4, f(C) = 2 + 1 = 3. Add these to the open set.

Now the open set is {B, C}. Since C has the lowest f-value, we pop it. C's only neighbour is D, which is the goal. So we stop, having found "the best path" from A to D.

This is clearly wrong. The algorithm *should* output the path A-\>B-\>D, which has total weight 4, but instead it stopped prematurely.

Now, if we were to have a larger graph, then after exploring the path A-\>C-\>D we would go back to B (which is still in the open set), notice that the path A-\>B-\>D to D gives D a lower f-value than A-\>C-\>D, so we update D's f-value, giving the correct fastest path. Alternatively, we could simply continue running A\* until the open set is empty, rather than ending prematurely as soon as we've found the goal (however, this doesn't agree with Wikipedia's pseudocode implementation of A\*).

Are my ideas correct, or am I missing something about how A\* is typically implemented?

# Answer
> 4 votes
Your misunderstanding is that A\* doesn't return success until it pops a goal node, in your terminology.

So, in your example, when it pops $C$, it puts $D$ in the open list, with quite a high value. It then pops $B$ and puts $D$ in the open list again, with a lower value. So the first time that $D$ is popped will be from the route $A\to B\to D$, as it should be.

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


# Question
Title: Is this lower bound proof for the comparison-based sorting problem correct?
Here is a lower bound proof for the comparison-based sorting problem:

* Any comparison-based sorting algorithm can be considered to work by putting elements into their final positions one by one (Take the last time one element is put into its final position.).
* To put the element $e$ which is the $i$-th one being put into its final position, the algorithms should know the relative ordering between $e$ and the first $n-1$ elements that are already put into their final positions. This costs at least $\Omega(\lg i)$ comparisons.
* Therefore, the total number of comparisons is at least $$\sum\_{i=1}^{n-1} \lg i = \Omega(n \lg n).$$

Is this a reasonable proof? (I am quite confused about the second step.) If so, how to formalize it more rigorously?

# Answer
> 1 votes
No, I don't think it's a reasonable proof. This makes claims without justification. For instance, the second bullet says that the only way to put an element into its final position is (the algorithm must know something..). How do you know that is correct? How would you prove that? What does it even mean for an algorithm to know something? Why does knowing that cost at least $\Omega(\lg i)$ comparisons? All of that seems a bit unclear to me, so I don't find it a persuasive proof.

---
Tags: algorithms, sorting, lower-bounds
---


# Question
Title: Intuitive way to understand "Run-Length Encoding"
Run-Length Encoding is the simple form of lossless data compression in which compression in which *runs* (execution) of data are stored as a single data value and count rather than as the original *run* (execution).

Now the definition is there but what's an intuitive way of thinking about this?

# Answer
"Run" doesn't mean "execution". It means "sequence of identical things", as in "the football team had a run of wins."

So the intuition is simply that it's more efficient to say "ten $a$'s" than "$aaaaaaaaaa$".
> 3 votes

---
Tags: complexity-theory, optimization, runtime-analysis, data-compression, signal-processing
---


# Question
Title: Relationship between depth and the vertical displacement of the object between two frames
I am trying to find the relation between the vertical displacement of an object to the depth of the object.

Say, there is an object in an image and as the center of gravity of this object moves vertically upwards, we know that it is moving away from the camera.

We know at the same time, that the dimension of the image would reduce because the object is moving away from the camera.

So, two things are happenning - 1 . the objects center of gravity is moving up vertically and 2. the object dimension is decreasing because the object is moving away from the camera.

Is it possible to find a relationship between "the vertical displacement of the object from one frame to another frame" and "the distance of the object from the camera from one frame to another frame" ?

# Answer
Yes. This all comes down to some simple trigonometry. An object that is at horizontal distance $x$ and vertical distance $y$ from the camera's viewing direction will be at angle $\tan^{-1} (y/x)$ from the viewing direction, and the distance to the object will be the length of the hypotenuse, i.e., $\sqrt{x^2+y^2}$ (draw a picture).

So, if the object starts at height $y\_1$ and then moves upward to height $y\_2$, the distance to the object will increase from $\sqrt{x^2+y\_1^2}$ to $\sqrt{x^2+y\_2^2}$. Now you can compute the absolute or relative change in the distance to the object, if you know $x,y\_1,y\_2$. For instance, if you know the distance to the object originally and the original angle $\theta\_1$ from the camera's viewing direction, you can compute $x,y\_1$; if you know how much it moved upward, you can compute $y\_2$; and that will let you compute the new distance.
> 1 votes

---
Tags: computer-vision
---


# Question
Title: Is this passage from the textbook Artificial Intelligence: A Modern Approach incorrect?
On page 383, section 10.2. of the *Algorithms for Planning as State Space Search* chapter of the textbook *Artificial Intelligence: A Modern Approach*, the following passage appears:

In this passage, the authors write that in the air cargo example they use there are $50^{10} \times 200^{50+10} \approx 10^{155}$ states.

Is this incorrect? Shouldn't there be $10^{50} \times 60^{200}$ states?

As far as my understanding of probability goes, there is a different state for all the different arrangements of the 50 planes, which can each be at one of 10 airports, which would give the result $10 \times 10 \times ... = 10^{50}$, and then the same reasoning applied to the placement of the packages on an airplane or at an airport gives $60 \times 60 \times ... = 60^{200}$, which together give $10^{50} \times 60^{200}$.

Is the textbook incorrect or is my reasoning incorrect?

# Answer
Yes. You are right. That looks like an error in the textbook. Check their errata, or send the authors a note to let them know.
> 1 votes

---
Tags: artificial-intelligence, planning
---


# Question
Title: What is the name for a function's "return arity"?
The *number of parameters a function has* (and thus the number of arguments it can take) is known as *arity*. What is the name for *the number of values a function returns*? I'm not asking for the "size" of a function's return values. A function returning a tuple returns a single, composite, value.

# Answer
The term "arity" would have been introduced to programming via formal logic and related fields (e.g. universal algebra). In the context of formal logic, there is little reason to allow function symbols to return multiple values even in the form of a tuple, and good reasons to disallow it. Mathematically, a function $X\to Y\times Z$ is equivalent to a pair of functions $X\to Y$ and $X\to Z$. So we don't lose anything by disallowing functions into cartesian products. What we gain, though, is a uniform syntax, especially in the context of single-sorted logic which is the typical one in formal logic.

In a single-sorted logic, there is only one sort (base type), call it $S$, so all functions are of the form $S\times\cdots\times S\to S$, or more compactly $S^n\to S$. By disallowing functions into products, if we have a term $f(x,y)$ and a function symobl $g$ of arity 2, say, then $g(f(x, y), z)$ is always a valid term. If we allowed functions into products, we'd need to at least introduce the projections $\pi\_i : X\_1\times X\_2 \to X\_i$. This would require us to assume the products were associated in some particular way or we would need to allow a whole family of projections or we would need some syntax to "spread" the results into multiple parameters. Basically, the syntax of terms would become significantly more complicated for no real gain. These syntactic complexities are reflected in programming languages that have real multi-valued returns (as opposed to just a single-valued return of a tuple).

Single-sortedness is what allows us to reduce the arity to a number. Combined with the restriction that function symbols can only return into the single sort, everything you need to know about a function symbol for the purposes of syntax can be reduced to a single number. In multi-sorted logics, it makes more sense to view the arity as a list of sorts, but since the return type is no longer fixed something more like a type annotation, e.g. $(X, Y)\to Z$, makes more sense. These type annotations are more relevant than arity. They are what you need to tell if a term is well-formed.

Most programming languages don't support a true notion of multi-valued return, and many don't even have a good notion of tuple. Occasionally in more theoretical work, the term "coarity" is used for a return sort. In a single-sorted context, the coarity could be represented by a number, but in a multi-sorted, i.e. statically typed, context it would be more natural for it to be a list of sorts. Really, computational models where operations can produce multiple outputs are usually thought of with a circuit metaphor. In such cases, we'd talk about things like fan-in and fan-out, or in-degree and out-degree.
> 9 votes

---
Tags: terminology
---


title: Find smallest enclosing circle

text:
# Question
Title: Find smallest enclosing circle
On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R\_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known radii and positions with respect to the origin. (It is possible that some smaller sub-circles are partially or entirely inside some larger sub-circles.)

The entire plane is gridded uniformly into pixels with sides being horizontal and vertical (along coordinate axes). The size of the pixels is fixed and known a priori but otherwise much smaller than the size of parent circle; there are on the order of few $\times 10^{5}$ pixels all over the parent circle.

$\sim 1\\%$ of the area of the parent circle is colored in the form of a few clumps across the parent circle covering $\sim 10^{3}$ pixels. These colored pixels are mostly inside sub-circles; all are entirely inside the parent circle. We are given the 2D Cartesian coordinates for (the centers of) all colored grids.

Each colored grid is associated with the smallest sub-circle that contains it. If the pixel falls within multiple sub-circles, only the smallest of the circles should be chosen.

Finally, I would like to calculate the total number of colored grids associated with each sub-circle. Is there an efficient algorithm for this?

# Answer
> 1 votes
Yes, there are efficient algorithms for this problem, using standard data structures for storing two-dimensional data.

Here is a simple approach. Store all of the colored pixels in a quadtree. Next, for each sub-circle, compute it bounding box, so now you have a square instead of a circle. Query the quadtree data structure to find all points contained within that square. For each such point, test whether it falls within the sub-circle. If it does, mark that point as associated with that sub-circle, unless it is already associated with a smaller sub-circle.

I expect the running time of this approach will be approximately $O(n+m)$ where $n$ is the number of colored points and $m$ is the number of sub-circles (assuming there is not too much overlap among the sub-circles, which seems likely to be the case for the parameter settings you listed). Thus, it should be very efficient.

You can alternatively replace the quadtree with any other data structure for 2D data, such as a k-d tree, though for the parameter sizes you mention, I expect that anything will already be quite fast and so it probably won't be necessary to worry too much about optimizing this as much as possible.

---
Tags: algorithms, computational-geometry, counting, square-grid
---


# Question
Title: what does one million word represent in the question below?
An Associated cache and one million word main memory are divided into 256 word blocks. How many blocks are there?

# Answer
Assuming ONE MILLION WORD = 2^20 words, we have, size of main memory = 2^20 words

Now, block size = 256 = 2^8 words

Number of blocks in Main Memory = 2^20/(2^8) = 2^12
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: LTL to automaton translation that can only read disjunctions of labels per transition
Is there any automaton (or automaton translation) as expressive as LTL that can only read disjunctions of atomic propositions per each transition? Standard LTL-to-automaton algorithms allow the automaton to read conjunction as well as disjunction of atomic propositions.

# Answer
The models of an LTL formula $\varphi$, with atomic propositions $P$, are infinite words $w = \sigma\_0\sigma\_1\ldots$, where each $\sigma\_i$ is a subset of $P$. To recognize such words, the edges of an automaton recognizing the language of $\varphi$ generally have to be labeled by symbols in $2^P$ (i.e. subsets of $P$).

Often multiple transitions are grouped by labeling edges in the automaton with boolean formulas over $P \cup \tilde{P}$, where $\tilde{P}$ is the set of negated atomic propositions. The edge label $f$ then stands for all models of $f$. In nondeterministic Büchi automata we can restrict $f$ to be a conjunction, as disjunction in the label can be modeled by introducing another transition.

Universal automata are the dual of nondeterministic automata, so to accept a word $aw, a \in \Sigma, w \in \Sigma^{\omega}$ from a state $q$, $w$ has to be accepted from *all* $a$-successors of $q$. Combining universal and nondeterministic branching one gets alternating automata. In universal automata for LTL formulas you can restrict the edge label to be a disjunction over $P \cup \tilde{P}$, as you can model conjunction in the label by introducing another transition.

With the right acceptance universal automata are as expressive as LTL, for example co-Büchi universal automata can recognize all $\omega$-regular languages.

**Edit**: I don't think this is a good answer after second thought. The reason is that grouping transitions in this way makes no sense for universal automata, unless the formulas on the labels have disjoint models. Example: Splitting $x \xrightarrow{a \land b} y$ into $x \xrightarrow{a} y$ and $x \xrightarrow{b} y$ adds the possibility to move to $y$ when only satisfying $a$, which was not possible before. I don't see any natural way of having an automata with only disjunctive boolean formulas as edge labels, however you can get rid of the formulas entirely on the edge labels by just using symbols in $2^P$.
> 6 votes

---
Tags: automata, logic, linear-temporal-logic
---


# Question
Title: Understanding tables in Dynamic programming
I came across this problem that asks you to implement a regular expression matcher with support for '.' and '\*', where

'.' Matches any single character.

'\*' Matches zero or more of the preceding element.

```
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

```

While I was able to solve this in a linear fashion, I came across lots of solutions that used DP, like the one below,

```
class Solution {
    public boolean isMatch(String text, String pattern) {
        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
        dp[text.length()][pattern.length()] = true;

        for (int i = text.length(); i >= 0; i--){
            for (int j = pattern.length() - 1; j >= 0; j--){
                boolean first_match = (i < text.length() &&
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));
                if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                } else {
                    dp[i][j] = first_match && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

```

I'm having a hard time understanding this. I've solved a few DP problems that involved grids (shortest path in 2d grid, largest square in binary 2d grid), using a DP table there made perfect sense to me. However here I'm completely lost, I'm unable to understand how traversing a 2d table helps in solving this problem. Further more it appears we know when the characters don't match in the loop, so I don't understand why we don't terminate the search there (this is also probably due to my lack of understanding of how a table traversal leads to a solution). Is there a clear intuitive explanation for problems like these?

# Answer
`dp[i][j]` represents whether `text[i..]` matches `pattern[j..]`.

If `pattern[j..]` is starting with `x*` for some symbol `x` (including `.`), then `text[i..]` matches `pattern[j..]`, or `x*pattern[(j+2)..]`, if and only if

* `text[i..]` matches `pattern[(j+2)..]` (i.e. `x*` matches an empty string), or
* `text[i]` is `x` and `text[(i+1)..]` matches `x*pattern[(j+2)..]` (i.e. `x*` matches a non-empty string).

This is implemented by this part of code:

```
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
}

```

On the other hand, if `pattern[j..]` is not starting with `x*`, `text[i..]` matches `pattern[j..]` if and only if `text[i]` matches `pattern[j]` and `text[(i+1)..]` matches `pattern[(j+1)..]`. This is implemented by this part of code:

```
else {
    dp[i][j] = first_match && dp[i+1][j+1];
}

```
> 3 votes

---
Tags: algorithms, finite-automata, dynamic-programming
---


# Question
Title: Difficulty in updating the balance factor of nodes in AVL tree
In this figure x,y,z are the nodes on which rotation is performed and T1, T2, T3, T4 are the subtrees. I have understood how the rotation is working and have no trouble with that. The problem I am having is determining the final balance factor of nodes in the tree. In the first case before rotation, the balance of factor of x will be +2 or -2(that's why we are performing the rotation). But what about the balance factor of y? Why is it always taken as +1 or -1 before rotation? Why it can't be 0(the height of T3 can be equal to the height of z)? What will we the balance factor of z before rotation? It can be anything right? In short, what will be the balance factor of nodes with the question mark before and after the rotation?

This is the code I am trying to write:

```
Node insert(Node node, int key)
{
    if(node == NULL)
        node = new Node(key);

    else if (key <= node->key)
    {
        node->balance++;
        node->left = insert(node->left, key);
    }

    else if (key > node->key)
    {
        node->balance--;
        node->right = insert(node->right, key);
    }

    // Right Tree Heavy
    if (node->balance == -2)
    {
        /*Do the required rotation and update the balance factor*/
    }

    // Left Tree Heavy
    if (node->balance == 2)
    {
         /*Do the required rotation and update the balance factor*/
    }

    return node;
}

```

Edit: Initially the tree was satisfying all the properties of avl tree. Then a new node was added to either T1 or T2 which made the tree unbalanced at node x. Can anyone explain all the cases of balance factor of nodes before and after the rotation.

# Answer
> 4 votes
The reason that the number of possible values for the balance factors at $y$ and $z$ is limited is not only the fact that the tree has been AVL before insertion, but also the precise location where the rotation is performed in an ex-AVL tree.

Rebalancing is **only needed** at the lowest position where the balance becomes $\pm 2$ where below had balance factors $0$. All those $0$ balance factors have been changed into $\pm 1$ depending on the side where the key has been entered. The short reason for this is that when a node has originally balance factor $0$ and one of its subtrees becomes taller after insertion, not only the balance factor becomes $\pm 1$ but also the total length of the tree at that node becomes one taller, so we have to consider its father.

* If that father has balance $0$ it will become $\pm 1$, the tree is taller, and we *proceed up again* \[diagram **b)**\].
* If the father has balance $\pm 1$ we may happen to improve the balance to $0$, and *we stop*, no rotation needed \[diagram **a)**\].
* If the balance becomes $\pm 2$ we *rebalance at that point* using the proper rotation. After rotation the tree at that point has the same height as originally, so we do not have to consider balance factors higher up in the tree. \[diagram **c)**\]

So the issue here is to determine the context where the rotation takes place. This is determined by following the insertion process bottom-up, from the leaf where the key was added.

The precise type of rotation (single/double, left/right) is determined by the insertion path that was followed below the node where we rotate.

In the *single rotation* case we have left-left insertion from $x$ so $y=-1$ (longer to the left, my balance factors are opposite to yours). The value at $z$ is not important, its complete subtree is copied during the single rotation at $x$. In the *double rotation* case we have left-right insertion from $x$ so again $y=-1$. At $z$ we might have any value: $\pm 1$ depending on whether the key went left/right at $z$, but even $0$ in the special case $z$ itself was inserted!

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


# Question
Title: How to decompose a unit cube into tetrahedra?
I was presented with the problem of breaking the unit cube $\[0,1\] \times \[0,1\] \times \[0,1\] $ into tetrahedron shapes. The first two pieces are easy, but it's not so easy to visualize after that. I found:

* $\\{ (0,0,0), (1,0,0), (0,1,0), (0,0,1) \\}$
* $\\{ (1,1,1), (1,1,0), (1,0,1), (0,1,1) \\}$

What remains is a triangular prism. Then maybe I think it readily splits into 2 or 3 pieces. In any case, they are difficult to draw and keep track of all the data.

---

Also I think I could have started differently with this other tetrahedron:

* $\\{ (0,0,0), (1,1,0), (0,1,1), (1,0,1) \\}$

There should be lots of solutions, but I neither have the date to store into a computer nor do I have picture of even a single one.

# Answer
> 4 votes
The simplest way is a partition into $3! = 6$ tetrahedra:

1. $\\{x,y,z : 0 \leq x \leq y \leq z \leq 1\\}$.
2. $\\{x,y,z : 0 \leq x \leq z \leq y \leq 1\\}$.
3. $\\{x,y,z : 0 \leq y \leq x \leq z \leq 1\\}$.
4. $\\{x,y,z : 0 \leq y \leq z \leq x \leq 1\\}$.
5. $\\{x,y,z : 0 \leq z \leq x \leq y \leq 1\\}$.
6. $\\{x,y,z : 0 \leq z \leq y \leq x \leq 1\\}$.

The corresponding tetrahedra have the following vertices:

1. $(0,0,0),(0,0,1),(0,1,1),(1,1,1)$.
2. $(0,0,0),(0,1,0),(0,1,1),(1,1,1)$.
3. $(0,0,0),(0,0,1),(1,0,1),(1,1,1)$.
4. $(0,0,0),(1,0,0),(1,0,1),(1,1,1)$.
5. $(0,0,0),(0,1,0),(1,1,0),(1,1,1)$.
6. $(0,0,0),(1,0,0),(1,1,0),(1,1,1)$.

# Answer
> 0 votes
John your second and third pictures are perfect, you have your 5 tetrahedrons there. You just can't see the fifth one behind the shaded area in the third picture but you can see it in the second picture following the dotted lines. So you've got it right.

---
Tags: computational-geometry, discrete-mathematics
---


# Question
Title: Minimum capacity cut reduction from digraph with two edge weight sets
Given a digraph $G$ and $f, g : E(G) \mapsto \mathbb{R}$, how would you find a cut $(X,\bar{X})$ with $s \in X$ and $t \in \bar{X}$ such that $\sum\_{e \in \delta^+(X)}{f(e)} - \sum\_{e \in \delta^-(X)}{g(e)}$ is minimized?

$\delta^+(X)$ is the set of edges going out of $X$ and $\delta^-(X)$ is the set of edges going into $X$.

I can solve for the case where $f = g$, simply by constructing a network flow graph with all edges adjacent to either $s$ or $t$. Since $\sum\_{e \in \delta^+(X)}{f(e)} - \sum\_{e \in \delta^-(X)}{f(e)}$ can be rewritten as $\sum\_{e \in \delta^+(X)}{f(e)} + \sum\_{e \notin \delta^-(X)}{f(e)} + constant$ then a graph can be constructed with an edge between $s$ and all $v \notin \\{s,t\\}$ with capacity equal to $\sum\_{e \in \delta^-(v)}{f(e)}$ and an edge between all $v \notin \\{s,t\\}$ and $t$ with capacity equal to $\sum\_{e \in \delta^+(v)}{f(e)}$. Then dealing with negative $f$ is simply a matter of adding the capacity to the $(v,t)$ edge instead of the $(s,v)$ edge and vice versa.

However this solution does not work when $f \neq g$ and I can't come up with an answer for this case.

The solution works for the case that $f=g$ because if we have an edge $(a,b)$, in the case that $a \in X, b \in \bar{X}$ then the edge is going out of X and not going into X, the contribution to the cut capacity is $2f((a,b))$ as per the formula containing the constant above. Then if you add $b$ to $X$, $a$ no longer contributes to the sum over edges going out of $X$ and so $f((a,b))$ is removed and you are left with $f((a,b))$. If $f \neq g$, then you are instead left with $f((a,b)) − g((a,b))$ which is incorrect.

In terms of what I have tried so far for the general case, the case that $g(x) \< 0$ is trivial and the edge can simply be reversed and the capacity multiplied by $-1$ so that it is positive.

In the case that both $f,g \> 0$ then I consider this local portion of the graph:

Let $f = f(a,b)$ and $g = g(a,b)$ in the above graph. I can then transform it to this network graph:

Where the capacities are given by

* $(s,b) = f$
* $(b,a) = f - g$
* $(a,t) = f$

Clearly this is only applicable in the case where $f \> g$. Then in the case that $a$ but not $b$ is added to $X$ we have a net increase of $f$. When $b$ but not $a$ is added to $X$ we have a net decrease of $g$. When both $a$ and $b$ are added to $X$ there is no net change.

However I cannot reconcile this with the case where $f \< g$ or $f \< 0$.

# Answer
This problem is NP-hard.

Consider the $f=0$ case, then you are trying to minimize $-\Sigma\_{e\in\delta^-(X)}g(e)$, i.e. maximize $\Sigma\_{e\in\delta^-(X)}g(e)$. This is exactly the maximum cut problem, which is NP-hard.
> 0 votes

---
Tags: graphs, optimization, combinatorics, network-flow
---


# Question
Title: Is it possible to tell if two sequences of assembly instructions are semantically equivalent?
In a modern instruction set like x86-64 there are many many *many* ways to accomplish the same task using a series of old simple instructions all the way up to the complex SIMD instructions. If one wanted to determine the semantic equivalence of a series of instructions, could this be done rationally or must it only be done experimentally?

For the sake of simplicity I am restricting the number of instructions in a series to something like ten.

The naive way to solve the problem would be to generate all of the potential inputs and experimentally check the results.

A slightly smarter way might be to determine the edges of the input states and only test those.

But I'm wondering if there's a way to represent each of the assembly instructions (and series of instructions) as a data structure that could be compared. Is this a tractable problem? Or is this clearly something like the halting problem?

Intuitively this feels like something similar to what happens inside a compiler.

# Answer
If you restrict to programs of some fixed, finite length then yes, this is decidable. There are only a finite number of possible programs so there is a finite list of which ones are equivalent to one another. A program that is hard-coded with that list can answer the question just by looking up the two programs.

However, if you don't restrict the length of the programs, the problem becomes undecidable: if it were decidable, you could solve the halting problem ("Does program $P$ halt with input $I$?") by rephrasing it as "Is the program that simulates $P$ running on input $I$ equivalent to this trivial program that always halts?"

As an aside, why do you feel that a compiler would need to do this? Compilers just take a program represented in one form (source code) and translate it into another form (the executable image). The translation process guarantees that the two are semantically equivalent, so there's no need to check.
> 4 votes

# Answer
In the real world you can't.

Sure, you could simply run both sequences on a simulator, and compare the final states to see if they are identical.

Complications are; you can't tell in advance that either of the sequences will ever finish (halting problem). Hidden state in the processor (caches, interrupts, etc. see meltdown and spectre) can alter the outcome. Real programs have inputs and produce different outputs depending; it's tough to test all possible inputs.
> 0 votes

---
Tags: compilers
---


# Question
Title: How to represent a map data structure mathematically
Wondering how to represent a map object such as the following mathematically:

```
var foo = {
  a: 10,
  b: 'bar',
  c: true
}

```

You could say that it was a function like this:

```
foo(x, y, z)

```

where $x$ is an integer, $y$ is a string, and $z$ is a boolean. But the question then is how to say the names of the keys `a, b, c`. Something like:

```
foo(label(x, a), label(y, b), label(z, c))

```

But then wondering about how type theory deals with this, so I' a bit confused. Wondering how computer science would model this data structure using mathematical notation. Maybe:

$$ \begin{align\*} foo = \left\\{ \begin{array}{r@{}l} & a = x \\ & b = y \\ & c = z \end{array} \right\\} \end{align\*} $$

# Answer
There are multiple ways to represent it.

The simplest way is probably as a mathematical function $f:S \to T$ where $S$ is the type of the keys and $T$ is the type of the values. In other words, you can represent it as a function/map. Here we have $f(\mathtt{a}) = 10$, etc. (so this is different from the idea you mentioned in the question).

Here are some more sophisticated ways to encode this in a type system:

If the keys `a`, `b`, `c`, are statically known and never dynamic, and that set is fixed in advance and never changes, this could be represented as simply a tuple or a record type.

If the keys are static but you want to extend them, you could represent this as an extensible row type. See also In type systems, is there a name for SQL's way of cutting and combining record types into new types? and Is there any difference between extensible records and dependent maps and Encoding row types.

If the keys are fully dynamic (their possible values aren't known at compile time), it needs to be represented as a function (i.e., map type).
> 2 votes

---
Tags: type-theory, notation, mathematical-foundations
---


# Question
Title: Proving that no finite automaton can recognize a Dyck language
I was reading up on finite automata and I came across an interesting fact near the end of the Wikipedia page.

> The classic example of a simply described language that no DFA can recognize is bracket or Dyck language, i.e., the language that consists of properly paired brackets such as word "(()())". Intuitively, no DFA can recognize the Dyck language because DFAs are not capable of counting: \[...\]

Although it is very intuitive the argument they gave, I was wondering if there were a formal proof I could read for this, or if simple enough, reconstruct.

I tried Googling around for a proof, but I think I am missing some sort of a keyword in my search because nothing useful is coming up, it this proof trivial or intuitive enough that no papers have been published on it?

# Answer
> 3 votes
Consider a Dyck language $L$ with $k$ types of parentheses, one of them $()$. If $L$ were regular then $L \cap (^\*)^\*$ would be regular, but this is just the well-known non-regular language $a^nb^n$ (with $a,b$ replaced by $(,)$).

There are many ways to prove that $L' = \\{a^nb^n : n \geq 0\\}$ isn't regular. Here is one. Suppose that $A$ is a DFA recognizing $L'$, with states $Q$, initial state $q\_0$, accepting states $F$, and transition function $\delta$. Let $q(i) = \delta(q\_0,a^i)$. If $i \< j$ then $q(i) \neq q(j)$, since otherwise $\delta(q\_0,a^ib^i) = \delta(q\_0,a^jb\_i)$ although the former is in $F$ while the latter isn't. This implies the absurd conclusion that $Q$ must be infinite.

---
Tags: formal-languages, finite-automata
---


# Question
Title: Problem with determining the shape and direction of the Huffman Diagram
I have the phrase **"abracadabra"** and I want to encode it through the Huffman method. I first took the frequencies of each letters; $$a=5$$ $$b=3$$ $$c=1$$ $$d=2$$ $$r=2$$ But I'm not sure as to how the diagram should look like. I made a few and some of them are correct. Also what determines the direction the branches take? Is there any fixed criteria for it?

# Answer
> 1 votes
Huffman's algorithm is non-deterministic — at several junctures you have more than one admissible choice. For example, at the first step, you can merge either $c$ and $d$ or $c$ and $r$. As another example, you can choose which child is left and which is right arbitrarily. Any particular implementation of Huffman's algorithm has some tie-breaking rule which makes it deterministic, but any choice would lead to a minimum redundancy code, and the generic Huffman algorithm doesn't specify any specific tie-breaking rule.

Huffman's algorithm is guaranteed to produce a minimum redundancy code, but not every minimum redundancy code can be produced by an admissible run of Huffman's algorithm. See Gallager's classic paper Variations on a theme by Huffman.

---
Tags: algorithms, information-theory, data-compression, huffman-coding
---


# Question
Title: how to mapping reduce any r.e. language to the diagonal language K?
We know that the halting problem $A\_{TM}$ and the diagonal language K are mapping reducible to each other. Furthermore both are complete with respect to the mapping reduce relation.

I would like to prove that any r.e. language is mapping reducible to K directly without reducing to $A\_{TM}$. How can this be done?

# Answer
> 2 votes
Let $A=L(M)$ be any r.e. language. We reduce $A$ to $K$ using the following reduction function $f(x)$.

Given any word $x$, construct a TM $N\_x$ such that, when run on input string $y$, it ignores it, and simulates $M$ on $x$. If $M$ accepts, we make $N\_x$ accept, otherwise we make $N\_x$ diverge. We let $f(x) = \langle N\_x \rangle$.

$f$ is clearly a total computable function. It is also simple to check that $x\in A \iff f(x)\in K$.

Note that $f(x)\in K$ means that the TM encoded by $f(x)$ halts on input $f(x)$. This means that $N\_x$ halts on input $y = \langle N\_x \rangle$. The value of $y$ is actually irrelevant, since $N\_x$ will ignore it, and halt only when $M$ accepts $x$, i.e. when $x\in A$.

---

In a sense, the "trick" here was to ignore the diagonal property which is used in the definition of $K$, and just make $N\_x$ halt on all inputs $y$ or diverge on all inputs $y$. In such way, we surely include the diagonal, and we simplify the reduction function $f$.

If we really wanted, it is possible to define a function $f(x)$ which produces the encoding of $N\_x$, which always halts (or always diverges, if we prefer that) on any $y\neq f(x)$, and instead halts on the the diagonal $y=f(x)$ if and only if $x\in A$. Defining such $f$, however, is harder, and requires the second recursion theorem. Ignoring $y$ makes $f$ much simpler to construct.

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


# Question
Title: What is the consensus algorithm that requires an odd number of nodes?
Last week I stood up and gave a talk on the Raft Consensus Algorithm.

The first question I got was:

> Doesn't it need an odd number of nodes?

I answered "During leader election, the first node to become a candidate, all the other nodes have to vote for. (Provided for that node the lack of heartbeat, timeout conditions have been triggered, and for the client nodes the candidate has an update to date term log). If two candidates arise at the same time, and neither gets a majority, each will fall back to a different random timeout, and the first to become a candidate (provided all the other criterion are met) will win. So you don't need an odd number of nodes to reach a majority, you just need to be the first candidate. Split votes are handled."

Immediately after this answer - I got the same question from a different person all over again.

> So how does it reach consensus if it doesn't have an odd number of nodes?

My question is: **What is the consensus algorithm that requires an odd number of nodes?**

EDIT:

Here is an online publication that claims distributed systems need an odd number of nodes. (Spurious claim).

> Partition tolerant consensus algorithms use an odd number of nodes (e.g. 3, 5 or 7). With just two nodes, it is not possible to have a clear majority after a failure. For example, if the number of nodes is three, then the system is resilient to one node failure; with five nodes the system is resilient to two node failures.

# Answer
> 7 votes
To my knowledge there is no quorum-based consensus algorithm that requires an odd number of nodes (processes). That's because such algorithms don't require a majority in the sense that a higher number of processes accept a value. A majority in these algorithms means that *at least* $N / 2 + 1$ processes accept a value, where $N$ is the total number of processes.

The reason for this is that a quorum-based algorithm requires that every decision made is known by at least one member of each one of the possible quorums in the system. One simple way (but not the only one) to achieve this is to require that every quorum is composed by $N/2 + 1$ processes and that the vote is *unanimous* inside a quorum.

For example, in a system with two processes two votes are required and the system is not fault tolerant. For three processes two votes are required. For four, three votes. For five, three votes.

# Answer
> 4 votes
"Always have an odd number of replica set members" is a common simplification of the MongoDB replica set election process and best practices for deployment, but certainly not a strict requirement.

The main requirement to elect (and sustain) a primary in a MongoDB replica set is a healthy majority of configured *voting* members able to communicate with each other. As at MongoDB 3.6, there is a maximum of 7 voting members per replica set with up to 50 members in total. All members are voting by default; non-voting members can be configured but are not eligible to be candidates for the role of primary.

An even number of voting replica set members does not improve fault tolerance over a similar replica set with one less voting member. The majority of a replica set (`n/2 + 1`) with 4 voting members is 3 while the majority with 3 voting members is 2. Both of these configurations can only tolerate unavailability of a single voting member in order to elect (and sustain) a primary.

An odd number of voting members can reduce the chance of tied elections where half the members vote for a different (but equally eligible) candidate to become primary, or where a network split creates several partitions without a majority of voting members. The maximum of 7 voting members puts a reasonable limit on the number of potential participants in a distributed election.

Elections will still be successful given an even number of voting members, but may require more voting rounds to confirm a majority win in some circumstances. With MongoDB's original `v0` replica set protocol, election rounds were consecutive so failed elections could add notable delay. MongoDB 3.2 introduced a new `v1` replica set protocol inspired by Raft, which allows concurrent elections and significantly reduces election time. MongoDB's `v1` protocol extends Raft with some practical deployment considerations such as member priority, replication chaining, and primary catch-up (to avoid unnecessary rollback of committed data). For more background details, see: Replication Election and Consensus Algorithm Refinements for MongoDB 3.2 and Raft Consensus in MongoDB.

# Answer
> 0 votes
This clicked for me this week in a MongoDB Product Forum. Mongo requires an odd number of nodes to establish a majority.

---
Tags: distributed-systems, consensus
---


title: Knapsack progblem with two conditions

text:
# Question
Title: Knapsack progblem with two conditions
I want to create an algorighm (with dynamic programing) similar to 1/0 knapsack problem but, I have one extra condition isVegetable or isFruit.

Assume we have N food items where we know `number, weight, value, 0 || 1` where 0 means isFruit and 1 meas isVegetable. We have two conditions, one is max knapsack weight and second is max number of vegetable items

Two condition means ... we cant exceed max knapsack capacity (weight) and there cant bee more than T number of vegetables in knapsack, so yes max value can bee lower than in basic 1/0 knapsack:

```
    4 // number of fruit items
    6 // max knapsack weight
    2 // max number of vegetable
// item_number, item_value, item_weight, isFruit || isVegetable
    1 8 4 0
    2 5 8 1
    3 6 1 1
    3 6 1 0

```

Here is an code example for basic 1/0 knapsack. I need to adjust this solution for `isVegetable` limitation. Any ideas?

```
int knapSack(int W, int wt[], int val[], int n){
    int i, w;
    int K[][] = new int[n+1][W+1];

 // Build table K[][] in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            if (i==0 || w==0)
                 K[i][w] = 0;
            else if (wt[i-1] <= w)
                  K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
            else
                  K[i][w] = K[i-1][w];
        }
     }

     return K[n][W];
}

```

# Answer
> 1 votes
You have to add one more dimension (condition) to K. The 3rd dimension is your flag. Don't look at the 3rd dimension as boolean, but as a value. So vegetables have the 3rd dimension as value 1, fruits as 0.
In the 2nd dimension you always add weight. (+5, +8 ..and so on)
In the 3rd dimension you will always add +1, or 0.
It looks like a HW, so I will only hint the answer here:

* when building the K table, iterate over the 3rd dimension too
* fill the first values with 0 as in rows and columns
* there are now 2 conditions. the weight of an item has to be \<= as actual weight w, the vegetables "size" has to be \<= as actual vegetables count of knapsack
* In the MAX function you have to look to 3rd dimension exactly the same as you are looking to the 2nd

When you have your final answer, you can look backward in your K table which items you have used. Tushar Roy (at the end of the video) explains it how to do it in 2d knapsack problem, but it is the same as in 3d. https://www.youtube.com/watch?v=8LusJS5-AGo

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


# Question
Title: What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges?
I have a directed graph, which can be cyclic, where each node contains a value.

Nodes are not labeled, and different nodes can contain the same value.

The outgoing edges of a node are ordered, or labeled, (1, 2, 3, ... N), where N is the number of outgoing edges from the node. (That is, it's a k-ary tree, if such a term can be used for a cyclic structure).

For each node in the graph, I produce a description of that node using the algorithm below. Nodes are considered the "same" (equivalent) if they end up having the same description.

My motivation is that I'd like to produce a hash value from the description which will be the same for nodes where their value and the subgraph reachable from the node are (recursively) the same... however, if the descriptions are the same, the hash will be the same, so we don't need to worry about the hash.

I describe the data structure reachable from the node in this simple way:

1. Number the nodes in the subgraph reachable from the node, which I can do in a specific order (such as breadth-first, ignoring nodes already numbered) because the outgoing edges of a node are labeled.
2. Describe the subgraph reachable from the node by listing the nodes in the subgraph in order by the assigned number, and for each node in the list include in the hash the node's value and for each outgoing edge for the node (in label order), include the number assigned to the tail node of the edge.

For example, for a tree with nodes containing values A, B, C, and D:

I calculate describe A by assigning 0, 1, 2, 3 to the nodes containing A, B, C, D, and describe the values and edges this way:

```
0: A [1 2 3]
1: B []
2: C [0]
3: D []

```

Note in particular the outgoing edges from the node containing "A" are ordered (B, C, D), which makes this a unique description of the subgraph (which it wouldn't be if edges were unordered).

And similarly, to calculate the description for C:

```
0: C [1]
1: A [2 0 3]
2: B []
3: D []

```

As another example:

both nodes get the same description, because the algorithm produces the same description when run for each node.

Now, I'm *assuming* I haven't just solved the isomorphism problem for labeled graphs ;-)

Thus I'm guessing this algorithm describes some special case of graph isomorphism easier to solve than the general problem... or, it's not a solution to graph isomorphism because we're comparing nodes not graphs... or the algorithm is flawed doesn't produce the result I think it does! :-)

But I don't know enough computer science to be able to tell which nodes exactly *would* be characterized as the "same" or "different" by this algorithm.

It might be that different nodes (different in the usual way that you'd typically characterize the isomorphism of labeled graphs) are nonetheless "close enough" for my purposes that I don't mind that they get the same description.

And, if this simple algorithm does produce the result I want, I'd be eager to know if a more efficient algorithm exists. But I can't ask that question without being able to specify what the simple algorithm does do.

Or, if I *did* understand what equivalence relation the algorithm produced, I might see that the algorithm was indeed flawed for my purposes.

Can you help?

# Answer
I think the equivalence relation can be defined this way:

Two nodes are equal if they contain the same value, they have the same number of outgoing edges, and, recursively, the subgraphs reachable from the two nodes following the outgoing edges in order are equal.
> 0 votes

# Answer
For graph isomorphism, there are many heuristics that work in well in practice on most graphs. You could try adapting any of them to your setting.

Here's one example of a simple heuristic that might often work well in practice (but with no guarantees on worst-case performance). Let $f\_0:V \to \mathbb{N}$ be the original values of the graph, so $f\_0(v)$ is the value on vertex $v$. Now construct a new set of values $f\_1:V \to \mathbb{N}$ from $f\_0$, as follows. For each vertex $v$, apply your two-step algorithm to get a description for $f$ using breadth-first search---but crucially, stop the breadth-first search after depth 1. Take the resulting description, hash it with any hash function, and use the resulting hash as $f\_1(v)$. You can do this again, and construct $f\_2$ from $f\_1$ (note that we are now ignoring the original values on the nodes, and using the values from $f\_1$, when computing $f\_2$), and then construct $f\_3$ from $f\_2$, and so on. Do this for a few steps, say 100 steps. Each iteration can be done in $O(n)$ time, so the total running time will be $O(n)$ to compute all of the values $f\_{100}$.

Now we have a nice property: if $f\_i(v\_1) \ne f\_i(v\_2)$, then $v\_1$ is not equivalent to $v\_2$. Thus, if $f\_{100}(v)$ is a singleton ($v$ is the only vertex with that value; i.e., there does not exist $w$ such that $f\_{100}(v)=f\_{100}(w)$), then there is no need to compute a full description for your $v$. We can apply your full algorithm to compute a full description for only the vertices $v$ whose value appears multiple times in $f\_{100}$. Heuristically, for most graphs, there probably won't be many of them. Thus, you won't have to compute the full description for many vertices, and you might avoid quadratic running time.

There are degenerate graphs where this might fall apart, and where the running time becomes quadratic, but for "most" graphs, hopefully this won't happen.
> 1 votes

---
Tags: graphs, time-complexity
---


title: Prove foldl fusion law

text:
# Question
Title: Prove foldl fusion law
I have proven the `foldr` Fusion Law as follows:

Given `f` is strict, `f a = b` and `f (g x y) = h x (f y)` for all `x` and `y`, than

```
f.foldr g a = foldr h b

```

**Case `[]`**:

```
(f . foldr g a) [] = foldr h b [] -- Remove . notation
f (foldr g a [])   = foldr h b [] -- definition foldr
f (foldr g a [])   = b            -- definition foldr
f a                = b            -- This is a given, so stop

```

**Case `(x:xs)`**:

```
(f . foldr g a) (x:xs) = foldr h b (x:xs)       -- remove . notation
f (foldr g a (x:xs))   = foldr h b (x:xs)       -- definition foldr
f (g x (foldr g a xs)) = h x (foldr h b xs)     -- inductive hypothesis
f (g x (foldr g a xs)) = h x (f (foldr g a xs)) -- introduce y
                 say y = foldr g a xs
f (g x y)              = h x (f y)              -- This is a given, so stop

```

Now, I would also like to prove the Fusion Law for `foldl`. This goes like this:

Given `f` is strict, `f a = b` and `f (g x y) = h (f x) y` for all `x` and `y`, than

```
f.foldl g a = foldl h b

```

However, I don't seem to be able to use the same trick as in the proof for `foldr`. How can I prove the `foldl` Fusion Law?

# Answer
> 7 votes
Let me try to answer your question, I may be mistaken, so check it out first:

Let's first state the definition of foldl:

```
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl h b x = case x of
                []     -> b
                (x:xs) -> foldl h (h b x) xs

```

Now, we aim to prove that, given `f:: A -> B, g:: A -> C -> A, h:: B -> C -> B, a:: A b:: B`, such that:

```
f a = b
f (g x y) = h (f x) y, for all x, y
f is strict

```

Then:

```
f . foldl g a = foldl h b :: [C] -> B

```

We are going to prove it by induction on the length of the list:

**Case 0:**

```
f.foldl g a []   = foldl h b []
f (foldl g a []) = foldl h b []   -- Definition of .
f a              = b              -- Definition of foldl
True                              -- given

```

**Case n =\> n+1:**

let `x:xs` be a list of length n+1, then xs has length n, the property holds for xs. Let's check it's true for `x:xs`:

```
f (foldl g a (x:xs))   = foldl h b (x:xs)
f (foldl g (g a x) xs) = foldl h (h b x) xs  -- Definition of foldl

```

Now, let's take `f' = f, g' = g, a' = g a x, h' = h, b' = h b x`

Clearly, `f'` is strict, also, `f' a' = b'`:

```
f' a'     = b'
f (g a x) = h b x  -- Opening the '
h (f a) x = h b x  -- Hypothesis
h b x     = h b x  -- Hypothesis

```

Now, let's check that `f' (g' z y) = h' (f' z) y` works for any y, z (I changed the x for a z, because we have a fixed x, the head of the list):

```
f' (g' z y) = h' (f' z) y
f (g z y)   = h (f z) y   -- Opening the '
                          -- OK: hypothesis

```

Now, since the predicate works for lists of length n, and xs has that length, and also `f', g', h', a', b'` make the premises true, we have that, for any list of size n, in particular xs:

```
f' . foldl g' a' xs      = foldl h' b' xs
f  . foldl g  (g a x) xs = foldl h (h b x) xs  -- Opening the '
f (foldl g (g a x) xs)   = foldl h (h b x) xs  -- What we were trying to reach

```

---
Tags: proof-techniques, functional-programming, haskell
---


# Question
Title: How do I visit all edges incident to a vertex in a DCEL data structure?
In a doubly-connected edge list (DCEL) data structure, each vertex `v` stores a pointer to one arbitrary half-edge, `v.inc`, which has `v` as its origin, that is, `v.inc.origin == v`. However, there may be multiple half-edges which have `v` as its origin.

How do I access or iterate all half-edges which have `v` has their origin?

# Answer
We can do that by exploiting the structure of the DCEL.

Recall first that each half-edge `h` has a pointer to its twin half-edge, `h.twin`. Each half-edge `h` also has a pointer to its successor, `h.next`, and predecessor, `h.prev`, half-edges, which lie on the boundary of its incident face (that is, on the boundary of `h.face`), assuming that the incident face of `h` lies to its left (if we walk, in a counter-clockwise matter, along the edges incident to `h.face` by following the "next" pointers).

So, how do we visit all half-edges which have a vertex `v` as their origin?

The solution consists in exploiting the pointers `h.twin` and `h.next`.

Let `h` be the half-edge such that a vertex `v` stores `h` as its own incident half-edge (that is, `h == v.inc`), where `v` is the vertex that we want to know all half-edges which have `v` as its origin, where `h` is one of those half-edges. We can then access `h.twin`, which has `v` as its destination. Hence, `h.twin.next` is a half-edge which also leaves `v`. Unless `v` is adjacent only to one vertex `u`, which implies that `v.inc == h` is the only half-edge leaving `v` (and we are done), then `h.twin.next` is different from `h`. In that case, let `w = h.twin.next`. Then `w.twin` is a half-edge which has `v` as its destination (i.e. like `h.twin`). Hence, `w.twin.next` is also a half-edge which leaves `v`. We can proceed in this matter until `w.twin.next` is equal to `h`.

In a more formal way, the algorithm may look as follows.

```
function all_half_edges_leaving(v):
    h = v.inc
    list = [h]
    w = h.twin.next
    while w != h:
        list.append(w)
        w = w.twin.next
   return list

```

Clearly, once we have the half-edges leaving `v`, we can access in constant time also its twins (given that each half-edge stores a pointer to its twin). Alternatively, we may also store the twins in a list during the procedure above.
> 2 votes

---
Tags: algorithms, data-structures, computational-geometry, doubly-connected-edge-list
---


# Question
Title: time complexity when power is involved in iteration
How do I calculate the time complexity of the following method? Would you please provide explanation? I know it's going to involve `sqrt(n) * <something>`. I Just don't know what that `<something>` is.

```
public void timeComplexity(int[] arr){
    int n = arr.length;
    int sqrt = (int) Math.sqrt(n+1);
    for(int i=2; i<sqrt; i++){
        for(int k= (int) Math.pow(i,2); k < n; k+=i){
            //do some constant time work
        }
    }
}

```

Also consider the following two variations:

1. k starts at i (`k=i` or `k=3`) instead of `k= (int) Math.pow(i,2)`.
2. k is incremented by some constant `k++` instead of the variable i `k+=i`

# Answer
> 2 votes
You are interested in several different variants. I'll show you how to estimate the running time in the first one, you do the rest. In fact, I will only estimate the number of times that the inner loop is run, which is $$ \sum\_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil. $$ To obtain this, you need to figure out the number of iterations in loops of the form `for (x = a; x < b; x += c)` (assuming $a \leq b$ and $c \geq 1$), which is a nice exercise.

Using $x \leq \lceil x \rceil \< x+1$, we see that the sum above can be bounded by $$ \sum\_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i} \leq \sum\_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil \< \lfloor \sqrt{n+1} \rfloor-2 + \sum\_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i} . $$ Using $m = \lfloor \sqrt{n+1} \rfloor - 1$, we can evaluate the left sum as follows: $$ \sum\_{i=2}^m \frac{n-i^2}{i} = n \sum\_{i=2}^m \frac{1}{i} - \sum\_{i=2}^m i = n (H\_m-1) - \frac{m(m+1)}{2} + 1, $$ where $H\_m$ is the $m$th harmonic number. It is well-known that $H\_m = \log m + O(1)$, and so we can estimate the sum by $\frac{1}{2}n \log n - \Theta(n)$, skipping a few steps. A similar bound holds for the right sum, since the additional term is only $\Theta(\sqrt{n})$. Altogether, we deduce that the inner loop runs $\frac{1}{2}n\log n - \Theta(n)$ many times.

---
Tags: algorithm-analysis, time-complexity, loops
---


title: prove A is co-re

text:
# Question
Title: prove A is co-re
Working on some cs theory and solving a problem on computationally \[=recursively\] enumerable languages:

> A language $A\subseteq \\{0,1\\}^\*$ is co-c.e. if and only if there is a decidable language $B\subseteq \\{0,1\\}^\*$ such that, for all $x\in\\{0,1\\}^\*$,
>
> $x\in A \Leftrightarrow (\forall w\in \\{0,1\\}^\*) \langle x,w\rangle\in B $

This is a two sided proof since it is "iff"

=\> Since $B$ is decidable therefore there exists a TM call $M1$ s.t. it decides $B$ so we build a new machine as follows. $M2$ couples $M1$ s.t. it uses $M1$ as a witness to verify whether the given input tuple for some $w$ element of $\\{0,1\\}^\ast$: $\langle x,w\rangle$ is rejected if so accept else reject.

Now this side of the proof is trivial, but I feel like for the other side we are essentially trying to prove the halting problem?

\<= There exists a TM $M1$ s.t. it computes comp($A$), now if we are enumerating **for all** $w$ in the tuple $\langle x,w\rangle$; since it is an infinite set there is no possible way to guarantee the constructed machine will halt or not. (Halting problem)?

# Answer
Before I actually start answering your question, I will prove the following (see my comment):

> A language $A \subseteq \\{0, 1\\}^\ast$ is recursively enumerable iff there exists a recursive language $B \subseteq \\{0, 1\\}^\ast$ sucht that for all $x \in \\{0, 1\\}^\ast$: $$ x \in A \iff \exists w \in \\{0, 1\\}^\ast. \langle x , w \rangle \in B.$$

For *recursively enumerable* (r.e / c.e.) I think the following definition is common:

> A language $A \subseteq \\{0,1 \\}^\ast$ is recursively enumerable if there exists a Turing machine $M$ such that for all $x \in \\{0, 1\\}^\ast$: $$M( x) = \begin{cases}1, & x \in A\\ \bot, & \text{otherwise.}\end{cases}$$

*only if*: Let $M\_A$ be this machine. Let $B = \\{\langle x, w \rangle \mid M\_A(x) = 1 \text{ after } |w| \text{ steps}\\}$. $B$ is recursive as we only need to simulate $M\_A$ for a finite number of steps to get an answer. $B$ has obviously the desired property.
*if*: Let $B \subseteq \\{0, 1\\}^\ast$ recursive such that $x \in A \iff \exists w \in \\{0, 1\\}^\ast. \langle x, w \rangle \in B$. Let $M\_B$ the machine that decides $B$. We define $M\_A$ as follows: For input $x \in \\{0, 1\\}^\ast$ simulate $M\_B$ multiple (maybe infinite) times: In the $i$-th simulationon we use $\langle x, w\_i \rangle$ as input, where $w\_i$ is the $i$-th word in the canonical orderng of $\\{0, 1\\}^\ast$. If $M\_B$ outputs $1$ in some round $i$, $M\_A$ terminates with output $1$. Otherwise, $M\_A$ will never stop simulating $M\_B$ with new $w\_i$s. Thus, $$M\_A(x) = \begin{cases}1, & \exists w \in \\{0, 1\\}^\ast. \langle x, w \rangle \in B\\ \bot, & \text{otherwise}\end{cases} = \begin{cases}1, & x \in A\\ \bot, & \text{otherwise.}\end{cases}$$ Hence, $A$ is recursively enumerable.

---

Now to your question: It is simply negation the conditions: $A$ is co-recursively enumerable iff there exists $B'$ (which is the complement of the $B$ I used above) such that for all $x \in A$: $$x \in A \iff \forall w \in \\{0, 1\\}^\ast. \langle x, w \rangle \in B'.$$ You can probably find a more direct argument but following the same idea as me. This proof was just what I had in my head the whole time.
> 2 votes

# Answer
For $\Leftarrow$, we are given a TM $M$ which decides $B$. To prove that $A$ is co-ce we need to construct a TM $N$ which accepts the complement of $A$. Concretely, we can craft $N$ so that it diverges on each word of $A$, and accepts each word on its complement $\overline A$.

We make $N$ take its input $x$, and then try all the words $w$, checking whether $\langle x,w \rangle\in B$. We can do this $M$ decides $B$. As soon as we find some $w$ such that $\langle x,w \rangle\notin B$, we stop and accept. If we don't find any such $w$, we diverge.

So, $N$ indeed accepts the complement of $A$ ($L(N)=\overline A$), which is what we wanted.
> 1 votes

---
Tags: turing-machines, computability, church-turing-thesis
---


# Question
Title: Is there a method to compress all data without loss (lossless compression)?
I know that the answer is no but I'm not sure why. Here's where I started. We know that all data with length $n$ Bits and minimum $1$ Bit can be compressed, either lossless or lossy. But how do I continue? Why is it impossible to compress all the data without loss?

# Answer
There are $2^n$ bitstrings of length $n$, but only $2^n-1$ bitstrings of length smaller than $n$. Hence there is no one-to-one mapping which maps every bitstring of length $n$ to a bitstring of strictly smaller length. In other words, for any (lossless) compression scheme there will always be a string which it doesn't compress.
> 4 votes

# Answer
Each string of bits can also be a number.

Then we add pigeonholes. For each possible original message create a pigeon. For a message up to $n$ bits that is $\sum^n\_{i=1} {2^i}=2^{n+1}-2$ pigeons.

Now create a pigeonhole for each possible compressed message. If you *have* to compress (compressed message always has less bits then uncompressed) you only have $2^{n}-2$ pigeonholes.

because $2^{n+1}-2 \> 2^{n}-2$ there will be pigeons sharing a hole. With lossless compression this is not allowed.

The reason compression works most of the time is that most messages that we want to compress are self redundant in some way. Compression algorithms look for those patterns and exploit them. However doing this forces other messages (that we don't generate) to become larger when using the same compressor.
> 3 votes

# Answer
`We know that all data with length n Bits and minimum 1 Bit can be compressed...`

How do we know this? This isn't true for lossless compression. In fact for strings of length n, **most** of them are not compressible.
> 0 votes

---
Tags: algorithms, complexity-theory, nondeterminism, information-theory, data-compression
---


# Question
Title: Optimizing Fleury's algorithm to work in O(|V|+|E|)
The time complexity of Fleury's algorithm is $O(|E|^2)$ because for each edge I have to check whether it is a bridge or not and that takes $O(|V|+|E|)$ time. But, instead of that if I store my bridges in a hash table by a traversal at the beginning and then print the Eulerian tour (checking for each bridge in $O(1)$ using the hash table), the overall time complexity would be $O(|V|+|E|)$. So, will this optimization be useful? If yes, why is it not included in Fleury's algorithm?

In addition, which algorithm is used in practice to print an Eulerian path (not Eulerian cycle, I know that can be done in $O(|V|+|E|)$ using Hierholzer's algorithm)?

I am more interested in theoretical analysis (whether this optimization would be useful) rather than actual implementation.

# Answer
Because a bridge in current graph may not be a bridge in the primary graph. Note Fleury's Algorithm deletes an edge after you pass it.

Consider the following graph:

You start at $A$, then move to $B$ and delete the edge $AB$.

Now $BE$ becomes a bridge so the algorithm then chooses $BC$. However, $BE$ is not a bridge in the primary graph, so you cannot detect it in advance.

According to Wikipedia

> If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other.

So finding an Eulerian trail is essentially the same as finding a cycle (if there are exactly two vertices of odd degree, add an edge connecting them and find an Eulerian cycle in the new graph).
> 1 votes

---
Tags: algorithms, graphs, eulerian-paths
---