# Question
Title: Regular language as finite union of periodic sets
Is it true that every regular language can be expressed as a finite union of periodic sets? In other words, if $L$ is regular, then do there exist finite sets $A\_1,\dots,A\_n,B\_1,\dots,B\_n$ such that

$$L = A\_1 \cdot B\_1^\* \cup \cdots \cup A\_n \cdot B\_n^\*.$$

I know this is true for regular languages over a unary alphabet, but I'm not sure about general alphabets.

# Answer
> 2 votes
Every language of this form can be represented as a regular expression without nested Kleene star. That is, its star height is $1$. The star height hierarchy is strict, and in particular, it is known that the language $(a^\*b^\*c)^\*$ cannot be represented in that form. An example over a binary alphabet would be $(aa(ab)^\*bb(ab)^\*)^\*$.

# Answer
> 6 votes
The answer by @YuvalFilmus is perfectly fine, and points you to the import notion of *star height*. But let me add a little bit more. We will show that languages of your form give a proper subset of the languages of star height one. But first, some musings what might come close to your form.

**General Regular Languages**

First, probably the closest form to yours for regular $L \subseteq \Sigma^\*$, accepted by a complete deterministic automaton $A = (\Sigma, Q, \delta, q\_0, F)$. For $q \in Q$ and $E \subseteq Q$, write $L\_{q, E}(A)$ for the language accepted by $(\Sigma, Q, \delta, q, E)$, i.e., changing the start state to $q$ and the set of final states to $E$. Then, we can write $$ L = \bigcup\_{ q \in F } L\_{q\_0, q}(A) L\_{q, \\{q\\}}(A)^\* $$ This result seems to be folklore and follows easily. A more refined variant of this decomposition appears in the book *Automata, Languages and Machines, Volume A* by S. Eilenberg, under the name *iterated up-decomposition*.

**Commutative and Bounded Regular Languages**

Others forms, more close to yours, and being proper generalizations of the unary language case you mentioned, could be given for the bounded and commutative regular languages. A language is *commutative*, if it is closed under permutation of letters. For example, $\\{ab,ba\\}$ is commutative, whereas $\\{ab\\}$ is not. A language $L \subseteq \Sigma^\*$ is *bounded*, if $L \subseteq w\_1^\* \cdots w\_n^\*$ for words $w\_i \in \Sigma^\*$. In what follows, let us denote by $\diamond$ the shuffle of two languages, and, for $L \subseteq \Sigma^\*$, by $L^{\diamond,\*} = \bigcup\_{n \ge 0} \underbrace{L \diamond \ldots \diamond L}\_{\mbox{$n$ times}}$ the *iterated shuffle*. Also, by $\operatorname{perm} : 2^{\Sigma^\*} \to 2^{\Sigma\*}$ denote the *permutational closure*, or *commutative closure*, i.e. adding all words that are permutations. For example, $\operatorname{perm}(\\{ab\\}) = \\{ab,ba\\}$.

Note that $L \subseteq w^\*$ is regular iff $L = w^n(w^p)^\*$ for some $n, p \ge 0$. This is implied by noting that $\\{ n : w^n \in L \\}$ is ultimately periodic (it could be viewed as a regular unary language).

By a result of Ginsburg/Spanier we have

> A language $L \subseteq w\_1^\* \cdots w\_r^\*$ is regular iff it is a finite union of languages of the form $L\_1 \cdots L\_r$, where each $L\_i \subseteq w\_i^\*$ is regular.

Also, if $\Sigma = \\{a\_1, \ldots, a\_k\\}$ and $L \subseteq \Sigma^\*$ is commutative and regular, it is possible to show that $$ L = \bigcup\_{i=1}^n \operatorname{perm}(u\_i) \diamond \operatorname{perm}(N\_i)^{\diamond,\*} $$ for finite sets $N\_i \subseteq a\_1^\* \cup \ldots \cup a\_k^\*$ with $|N\_i \cap a\_j^\*| \le 1$.

Also, as stated here and here, a regular language $L$ over $\Sigma = \\{a\_1, \ldots, a\_k\\}$ is commutative iff $$ L = \bigcup\_{i=1}^n U\_{i,1} \diamond \ldots \diamond U\_{i,k} $$ for unary regular languages $U\_{i,j} \subseteq a\_j^\*$ with $i \in \\{1,\ldots, n\\}$ and $j \in \\{1,\ldots,k\\}$.

All these results are closely related. Note that for unary languages, they all reduce to the form you have stated.

**A Necessary Condition for Languages of your Form**

The condition I will state involves topology and infinite words. It yields, for example, that $b^\*a$ and $(b^\*a)^\*$ could not be written in your form. The latter has star height two, note that star height could be characterized by *cycle rank*, see Eggan's Theorem. However, I do want to give a self-contained, and different, argument here, not based on star height. Let $\Sigma^{\omega}$ be the set of infinite words over $\Sigma$. Define an operator $W : 2^{\Sigma^\*} \to 2^{\Sigma^{\omega}}$ by, for $L \subseteq \Sigma^\*$, $$ W(L) = \\{ \xi \in \Sigma^{\omega} \mid \mbox{ $\xi$ has infinitely many prefixes in $L$ } \\}. $$ Then \begin{align\*} W(b^\*a) & = \emptyset \\ W((b^\*a)^\*) & = \\{ \xi \in \Sigma^{\omega} \mid \mbox{$\xi$ has infinitely many $a$'s. } \\}. \end{align\*} Observe that $$ W(U \cup V) = W(U) \cup V(V), $$ as, if $\xi \in W(U\cup V)$, then, by the pigenhole principle, at least one of $U$ or $V$, or both, must contain infinitely many prefixes of $\xi$. Also, in your form we could assume all the sets $A\_i$ are singletons, as concatenation distributes over union.

Let us inspect languages of the form $L = u(u\_1 + \ldots + u\_n)^\*$, which are the parts of your form. Set $\Gamma = \\{ b\_1, \ldots, b\_n \\}$, an auxiliary alphabet, and consider the homomorphism $h : \Gamma \to \Sigma^\*$ given by $h(b\_i) = u\_i$, i.e., substituting each letter by the corresponding word. This homomorphism could also be applied to infinite words in $\Gamma^{\omega}$. We have $$ W(u(u\_1 + \ldots + u\_n)^\*) = \\{ uh(\xi) \mid \xi \in \Gamma^{\omega} \\}. $$ In particular, if all the set $B\_i$ are singletons, $W(L)$ is finite, and $W(L) \ne \emptyset$ for every infinite language of your form.

By the last observation, $b^\*a$ could not be written in your form. So, this is a very simple example, even of star height one. But let us show that $L = (b^\*a)^\*$ could also not be written that way. Assume it could be, then the set of infinite words, which all have an infinite number of $a$'s in it, could be written in terms of a homomorphism $h : \Gamma^\* \to \Sigma^\*$ as outlined above, i.e., $$ \\{ \xi \in \Sigma^{\omega} \mid \mbox{$\xi$ has infinitely many $a$'s. } \\} = u h(\Gamma^{\omega}) $$ for some $u \in \Sigma^\*$. Let $m = \\{ |h(x)| : x \in \Gamma \\} + |u|$. Then $ub^maaaaa\cdots$ is in this language, and this implies $h(x) \in b^+$ for some $x \in \Gamma$. But then $ubbbbbbb\cdots \in uh(\Gamma^{\omega})$, which is a contradiction, as it only contains a finite number of $a$'s. Hence, $(b^\*a)^\*$ could not be written that way. $\square$

---
Tags: formal-languages, regular-languages, finite-sets
---


# Question
Title: How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?
An SUBSET-SUM *instance* is a list of $n$ integers $\\{ a\_1, a\_2,... a\_n\\}$. To *evaluate* a subset is to output the sum of a subset.

However, I want to know, is it possible to create a new instance $T$, the same size as the original set $S$, that any subset in $S$ that evaluates to $W$, the corresponding subset in $T$ (the numbers taken from the same positions) evaluates to $0$? All other subsets in $T$ should evaluate to $1$.

Bonus: Give a list of other NP-complete problems (other than 3SAT, where you evaluate a *formula* that either outputs $0$ or $1$ depending on the set of binary variables being passed into it), where evaluating an analogous instance outputs $0$ if it satisfies some objective related to the problem and $1$ otherwise.

# Answer
> However, I want to know, is it possible to create a new instance T, the same size as the original set S, that any subset in S that evaluates to W, the corresponding subset in T (the numbers taken from the same positions) evaluates to 0? All other subsets in T should evaluate to 1.

No, this is impossible. Consider $S=\\{1,2,3\\}$ and $W=3$. Our set $T$ should be $\\{a,b,c\\}$ such that $a+b=0, c=0$ and $a+b+c=1$.
> 3 votes

---
Tags: np-complete, subset-sum
---


title: Can this language be called regular?

text:
# Question
Title: Can this language be called regular?
Recently, I was facing some problems in effectively proving the following :

Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of digit such that when viewed as numbers, satisfy the mathematical equation x+y=z.

> For example, the string 123#45#168 is in this language because 123 + 45 = 168.

Is this language regular and why ?

I was trying to apply the Pumping Lemma, but am unsure of how to complete the proof. Could anyone please help ?

# Answer
> 1 votes
Hint:

> Consider the special case where $y=0$.

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


title: Universal Quantifiers in QBFs

text:
# Question
Title: Universal Quantifiers in QBFs
I've been looking into reductions to/from the TQBF language and have managed to get stuck on something that is almost certainly not true (or, if it is true I'm missing a significant computational cost associated with it) with respect to simplifying TQBF instances.

For the sake of simplicity, let's restrict attention to TQBF instances in prenex normal form and CNF with no free variables. My hypothesis (which I strongly suspect is wrong, but have been unable to find a counter-example) is that such a TQBF is satisfiable if and only if the TQBF that results from removing all instances of universally quantified variables from the sentence is satisfiable. For example, take the following instance:

$\exists a \forall b \exists c \forall d$ $\psi(a,b,c,d)$

$\psi(a,b,c,d) = (\neg a \vee b \vee c)\wedge (\neg b \vee \neg c \vee d)\wedge (a \vee c \vee \neg d)$

First, I contend that this instance is not satisfiable (easily verifiable by hand). If we apply the method I describe above, we get the following "core":

$\exists a \exists c$ $\phi(a,c)$,

$\phi (a,c) = (\neg a \vee c)\wedge (\neg c) \wedge (a \vee c)$

which is clearly not satisfiable. If instead of this example we look at this:

$\exists a \forall b \exists c \forall d$ $\psi(a,b,c,d)$

$\psi(a,b,c,d) = (\neg a \vee b \vee \neg c)\wedge (\neg b \vee c \vee d)\wedge (a \vee c \vee \neg d)$

which clearly is satisfiable (set c to true, a to false) and which has a "core" of

$\exists a \exists c$ $\phi(a,c)$,

$\phi (a,c) = (\neg a \vee \neg c)\wedge (c) \wedge (a \vee c)$

that is also satisfiable with the same variable settings.

If this method always works, that would seem to imply that there is a reduction from TQBF to SAT in time linear in the number of universal quantifiers and the number of occurrences of the universally quantified variables in the formula, showing that TQBF is NP-Complete (it is already known to be PSPACE-Complete and thus NP-Hard, so if it is in NP it is NP-Complete) and furthermore that NP=PSPACE. I would be utterly stunned if this is the case, but I have been unable to find a counterexample (or a missing computational cost in the reduction that makes it not polynomial time). What am I missing?

# Answer
Your intuition was right. It doesn't work. Here is a counterexample.

Consider $\forall a \exists b \varphi(a,b)$ where $\varphi(a,b) = (a \lor \neg b) \land (\neg a \lor b)$. This statement evaluates to true.

However, if we remove $a$ following your procedure, we get $\exists b \psi(b)$ where $\psi(b) = ((\neg b) \land (b))$; and that statement evaluates to false.

One way to understand why your method doesn't work is that $\forall a \exists b \varphi(a,b)$ isn't equivalent to $\exists b \forall a \varphi(a,b)$. At most your method might work if all of the $\forall$'s are on the inside, i.e., for a sentence of the form $\exists \cdots \exists \forall \cdots \forall$, but not for any other pattern of $\exists$ and $\forall$.
> 2 votes

---
Tags: logic, satisfiability
---


# Question
Title: Hardness of maximizing difference of functions
Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP\_HARD. What can be said about the problem of maximizing $f-g$, with $g$ being another function over $D$? Is it possible to characterize $g$ in relation to $f$ in a way that can be assured that maximizing $f-g$ is also NP-HARD?

# Answer
> 1 votes
I suspect there's not likely to be any characterization that is very useful. The optimization problems can be hard or easy depending on $g$.

To give an analogy: you could ask for a characterization of functions $f$ for which it is NP-hard to maximize $f$. Well, you're probably not going to find a useful one.

---
Tags: complexity-theory, np-hard, proof-techniques
---


# Question
Title: Policy dependent on initial state distribution in finite horizon MDPs
Consider an MDP defined as the tuple $\langle S,A,R,P,\mu,\lambda\rangle$ where $S$ is the state space, $A$ the action space, $R:S\times A\times S\to\mathbb{R}$ the reward function, $P$ the transition probabilities, $\mu$ the initial state distribution, and $\lambda$ is the discount factor.

Let the decision horizon be finite. The expected discounted return under a given policy $\pi = (\pi\_1,\ldots,\pi\_{T-1})$, where each $\pi\_t:S\to A$, is defined as \begin{align\*} F(\pi,\mu) = E\_{\pi,\mu}\big\[\sum\_{t=1}^{T-1}\lambda^tR(s\_t,a\_t,s\_{t+1}) + \lambda^TR(s\_{T-1},s\_T)\mid s\_1\sim \mu\big\] \end{align\*} where $a\_t = \pi\_t(s\_t)$ and the expectation is taken with respect to the probability distribution on the states induced by the initial state distribution $\mu$ and the policy $\pi$. An optimal policy is defined as $\pi^\*\in\arg \max\_\pi F(\pi,\mu)$.

It seems to me that the math says that since we are only maximizing over $\pi$, there is still a residual dependence of the optimal policy on $\mu$, i.e., mathematically it should be written: $\pi\_{\mu}^\*\in\arg \max\_\pi F(\pi,\mu)$.

**Question:** Are optimal policies in MDPs dependent upon the initial state distribution? If not, what conditions allow us to rule out this dependence?

# Answer
On an MDP the main assumption is that states are independent (**Markov** Decision Process). Any policy in such environments will decide an action on a given state independently of previous visited states, taken actions and received rewards.

This means that the optimal policy doesn't depend at all on the initial distribution. However the initial distribution might affect the expected reward but it won't affect the optimal policy.

To be clear on your second question, the condition that allow us to rule out this dependency is the markov property: The future is independent from the past given the current state. So the optimal policy will have a distribution of actions to take depending only in the state, without caring about the weight of such state in the initial distribution.
> 0 votes

---
Tags: dynamic-programming, reinforcement-learning, markov-chains
---


# Question
Title: Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP
I always considered Symmetric TSP to be inapproximable **in general**, and thus by extension Asymmetric TSP as well. Once you add the condition of the triangle inequality however, you obtain Metric TSP (which can be Symmetric or Asymmetric), which is approximable (*e.g.* Christofides algorithm).

However, I'm having doubts after finding the following paper :

An improved approximation algorithm for ATSP
Vera Traub, Jens Vygen (https://arxiv.org/pdf/1912.00670.pdf)

In their paper, there is no mention of Metric TSP, or the triangle inequality. Does this mean that I'm misunderstanding, *i.e.* Asymmetric TSP is in fact approximable, even without the triangle inequality?

EDIT : As Discrete Lizard pointed out, Metric TSP seems to not just imply (any) TSP respecting the triangle inequality, but rather Symmetric TSP respecting the triangle inequality. This does not change my last question though, and Yuval Filmus' answer is still correct.

# Answer
Here is an excerpt from the introduction to an earlier paper of Svensson, Tarnawski and Végh, which was the first to give a constant factor approximation algorithm for ATSP:

> Without any assumptions on the distances, a simple reduction from the problem of deciding whether a graph is Hamiltonian shows that it is NP-hard to approximate the shortest tour to within any factor. Therefore it is common to relax the problem by allowing the tour to visit cities more than once. This is equivalent to assuming that the distances satisfy the triangle inequality: the distance from city $i$ to $k$ is no larger than the distance from $i$ to $j$ plus the distance from $j$ to $k$. All results mentioned and proved in this paper refer to this setting.
> 4 votes

---
Tags: approximation, traveling-salesman
---


title: Game on the graph with matchings

text:
# Question
Title: Game on the graph with matchings
The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move the piece along any outgoing edge to the vertex, where the piece has never been. The one who cannot make a move loses. How to Prove that the former wins if and only if the starting vertex lies in all maximal matchings?

# Answer
First of all, let me correct *maximal matchings* (that is, matchings which cannot be extended) to *maximum matchings* (that is, matchings of maximal size).

Suppose first that the starting vertex $v$ doesn't lie on all maximum matchings. Pick a maximum matching $M$ which doesn't contain $v$. The second player will always play an edge from $M$ – we will show that this is always possible. Suppose that the game play so far has been $v,a\_1,b\_1,\ldots,a\_t$. We know that $M$ doesn't touch $v$. If it also doesn't touch $a\_t$, then this is an augmenting path (check!), which contradicts the maximality of $M$. Hence $M$ must contain an edge $(a\_t,b\_t)$, which the second player can play.

Suppose next that the starting vertex $v$ does lie on all maximum matchings. Pick some maximum matching $M$ which contains $v$. The first player will always play an edge from $M$. Suppose that the game play so far has been $v,a\_1,\ldots,b\_t$. If $M$ doesn't touch $b\_t$ then we could switch edges according to this "almost-augmenting" path to obtain another maximum matching which doesn't contain $v$. Hence $M$ must contain an edge $(b\_t,a\_{t+1})$, which the first player can play.
> 7 votes

---
Tags: algorithms, graphs, matching
---


title: Is every unambiguous grammar regular?

text:
# Question
Title: Is every unambiguous grammar regular?
While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language. But is there a regular language for every unambiguous grammar? How can I prove that this is/isn't true?

# Answer
> 13 votes
The following grammar is unambiguous yet generates a non-regular language: $$ S \to aSb \mid \epsilon $$

---
Tags: formal-languages, formal-grammars, proof-techniques, ambiguity
---


title: Lowest complexity - Number closest to 0

text:
# Question
Title: Lowest complexity - Number closest to 0
I'm currently trying to improve my algorithm skills and I was trying a simple algorithm :

Given a list of integers. We want to find the one that is the closest to 0. If we have a number and his opposite, we want to return the positive one.

My current complexity on this algorithm is O(n). Is it possible to get a lower one ?

My current solution looks at all the values. I was thinking about a binary search, but we're not looking for a specific number, and the list of integers is not sorted.

Thanks for the help !

# Answer
> 1 votes
If you want an algorithm that is always correct you can not do better, precisely because you *have to* look at all the values at least once (except if you find a $0$ somewhere, then you can immediately return that).

Otherwise, suppose your run your algorithm $A$ some input $I=\[a\_1,a\_2,\ldots,a\_n\]$, and it returns a value $v\neq 0$ without looking at all numbers in $I$. Say it didn't look at $a\_k$. Then we could just as well set $a\_k=0$ and $A$ wouldn't know about it (because it didn't look at $a\_k$). Thus $A$ will be wrong on this (modified) input.

That is of course assuming that setting $a\_k = 0$ doesn't contradict some assumption you have about the data (for example it being sorted).

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


# Question
Title: What is the difference between a fraction and a float?
I understand any fraction to be *a quotient of integers which isn't 0*, but after coming across the term "float" in various programming languages (such as JavaScript) I misunderstand why it is even needed and we don't say a fraction instead.

What is the difference between a fraction and a float?

# Answer
Computers usually deal with floating-point numbers rather than with fractions. The main difference is that floating-point numbers have limited accuracy, but are much faster to perform arithmetic with (and are the only type of non-integer numbers supported natively in hardware).

Floating-point numbers are stored in "scientific notation" with a fixed accuracy, which depends on the datatype. Roughly speaking, they are stored in the form $\alpha \cdot 2^\beta$, where $1 \leq \alpha \< 2$, $\beta$ is an integer, and both are stored in a fixed number of bits. This limits the accuracy of $\alpha$ and the range of $\beta$: if $\alpha$ is stored using $a$ bits (as $1.x\_1\ldots x\_a$) then it always expresses a fraction whose denominator is $2^a$, and if $\beta$ is stored using $b$ bits then it is always in the range $-2^{b-1},\ldots,2^{b-1}-1$.

Due to the limited accuracy of floating-point numbers, arithmetic on these numbers is only approximate, leading to numerical inaccuracies. When developing algorithms, you have to keep that in mind. There is actually an entire area in computer science, numerical analysis, devoted to such issues.
> 2 votes

---
Tags: mathematical-programming, mathematical-foundations
---


title: $fl(x)=x(1+\delta)$

text:
# Question
Title: $fl(x)=x(1+\delta)$
The floating point representation of a real number $x$ in a machine is given by $fl(x)=x(1+\delta),\\: |\delta| = \frac{|x^\*-x|}{|x|} \le \epsilon$.

But I do not find this equation very insightful. Insert $\delta = \frac{x^\*-x}{x}$ in the equation and you get $x^\*$. So $fl(x)$ is just $x^\*$. Why write $x^\*$ in this fancy way: $$fl(x)=x(1+\delta)$$

Does equation have a name by the way?

# Answer
The idea that this expression is trying to relay is that the nature of the error in floating-point arithmetic is *multiplicative* rather than *additive* (which is the case for fixed-point arithmetic). This is because of the way that floating-point numbers are stored: as a mantissa multiplied by an exponent. Since the error is incurred only when rounding the mantissa, it is multiplicative (ignoring overflow and underflow).

The kind of guarantee that numerical algorithms can make is: if the input is correct up to a multiplicative error of $1 \pm \delta$, then the output will be correct up to a multiplicative error of $1 \pm \epsilon$. So $\delta$ (in your case, the machine $\delta$) measures the relative error involved when expressing real numbers as floating-point numbers, which is the information required to deduce the accuracy of numerical algorithms.
> 1 votes

---
Tags: numerical-analysis
---


# Question
Title: 2-dimensional ranking of multiple arrays
Given a fixed dimension $d$, say $d=2$ we want the following:

Input: $A\_1\ldots A\_m$: $m$ arrays of length $n$ of integers

Each input array $A\_i$ must be a permutation of the numbers $1..n$, so in each array each number from $1$ to $n$ appears exactly once.

Output: For each tuple (pairs in the case $d=2$; triplets in the case of $d=3$ etc. In this example we'll use pairs) of numbers $(1,1),(1,2)\dots(n,n)$, we want a **count** for in how many input arrays the first number of the tuple is also the first to appear in the array (among the numbers of that tuple). The order in which the other numbers of the tuple appear in an array doesn't matter, as long as they come later than the first number of the tuple.

> Question: Can this be done quicker than $O(mn^d)$ in the worst case?

**Upper and lower bounds**

The output is represented as a $d$-dimensional array of length $n$. Therefore a lower bound for the runtime complexity is $O(n^d)$.

The naive approach is to create $m$ mappings from each number to its index for each input array. Then for all $n^d$ tuples, walk through the $m$ mappings, yielding a runtime complexity upper bound of $O(dmn^d)$ and since $d$ is a constant this is $O(mn^d)$.

**Examples**

```
A = (1,2,3,4),        Output =  1 2 3 4
    (1,2,3,4),                  -------
    (1,2,3,4),     =>       1 | 4 4 4 4
    (1,2,3,4)               2 | 0 4 4 4
                            3 | 0 0 4 4
    d=2, m=4, n=4           4 | 0 0 0 4

=======================================

A = (4,3,2,1),         Output = 1 2 3 4
    (1,2,3,4),                  -------
    (1,2,3,4)      =>       1 | 3 2 2 2
                            2 | 1 3 2 2
    d=2, m=3, n=4           3 | 1 1 3 2
                            4 | 1 1 1 3

```

**Application**

While writing poker analysis software, I'm particularly interested in the case $d=3, m\approx 1250, n\approx 1250$. I estimate that the naive $O(mn^d)$ solution takes multiple hours but less than a day when using native Java arrays (no hashmaps etc) on a single thread.

$d$ stands for the number of players that are still active during a poker hand. Normal poker software handles the case $d=2$. Some high-end software handles the case $d=3$.

I'm interested in the case $d=2$, but then the naive approach is already quick enough in most situations. I'm mainly interested in the case $d=3$. I'm less (but still) interested in the case $d=4$ which is probably unfeasible and even less interested in greater values. I'm not interested in $d\>10$. A poker table has 10 players max. The values of $m$ and $n$ do not increase/decrease with $d$.

# Answer
> 4 votes
Here is a solution quite simple to implement, that only improves the $d$ factor.

For the increasing series $\[1, 2, .., n\]$, get the tuple list of the coordinates to increase in your output array. For $d = 2$ and $n = 4$, this is $H=\[(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)\]$. Asymptotically (not exactly due to $(a, a)$ being always valid), there are $O(\frac{n^d}{d})$ terms in this list.

Initialize an output array $B$ of size $n^d$ to zeros.

Then, for each of the $m$ arrays $A$ and for each tuple $(a\_0, a\_1, ..., a\_d)\in H$, increase $B\[A\[a\_0\], A\[a\_1\], ..., A\[a\_d\]\]\]$ by 1.

It achieves $O(\frac{m n^d}{d})$.

***EDIT***

For $d=3$, basically, both tuples $(0, 1, 2)$ and $(0, 2, 1)$ are in the coordinates list to increase. But if you want to use the knowledge that $B\[a, b, c\] = B\[a, c, b\]$, you have to keep only tuples non-decreasing after the 2nd integer. So here you leave $(0, 2, 1)$. Be careful to still keep $(a, b, b)$ tuples like $(0, 2, 2)$.

Then you will divide the number of terms in the list by about a factor $2(d-1)!$ for the general case).

At the very end, you have to add a $O(n^d)$ step to gather counts on $B\[a, b, c\]$ and $B\[a, c, b\]$. For every tuple $(a, b, c)$ with $b \< c$,

* $S = B\[a, b, c\] + B\[a, c, b\]$
* $B\[a, b, c\] = S$
* $B\[a, c, b\] = S$

This runs in $O(\frac{m n^d}{d!})$.

---
Tags: algorithms
---


# Question
Title: How to convert $(0.11001100...)_2$ to a decimal number
I managed to find and understand algorithm for converting any $x \in \Bbb R$ from a decimal number to binary number.

But I have a hard time finding an algorithm for converting a binary number with infinite bits to a decimal number. I will like to convert $(0.11001100...)\_2$ to a decimal number.

# Answer
> 1 votes
Classical formula for proper fraction is $$(0.a\_{-1}a\_{-2}a\_{-3}\cdots)\_2 = \left(\sum\limits\_{k=1}^{\infty}\frac{a\_{-k}}{2^k}\right)\_{10}$$ Where for $a\_{-k}$ we have $k \in \mathbb{N}$ and $a\_{-k}\in \\{ 0,1\\}$. As you see for indexing is taken negative numbers.

In your example $$(0.11001100...)\_2 =\left( \frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^5}+\frac{1}{2^6}+ \cdots\right)\_{10}$$

# Answer
> 1 votes
Let $x=0.11001100...$. in base $2$. Then $16x=1100.\overline{1100}\implies 15x=12\implies x=4/5$.

---
Tags: arithmetic, boolean-algebra
---


title: Cache Miss and Processor Speed

text:
# Question
Title: Cache Miss and Processor Speed
today in my class my professor mentioned that

```
Cache misses becomes more expensive as the speed of the processor increases

```

But he didn't explain the reason. I searched this statement over the internet and found no answer whatsoever.

According to me, this statement is true because, when the speed of the processor increases it can execute more instructions at a given clock cycle, thus a miss leads to a stoppage of more instructions from executing. So cache misses becomes expensive as processor speed increases. Is my thinking correct or am I doing it all wrong?

# Answer
Yes, that's correct. Assuming the speed of the cache doesn't change, a cache miss takes a fixed amount of time, and if the number of instructions per time unit increases, then more instructions get delayed because of the cache miss.

Modern processors try different methods to counteract this. Obviously you can use bigger caches which may lead to fewer cache misses. The disadvantage is that with the same technology, a bigger cache will run slower. Another method is organising the cache in such a way that "normal" code doesn't produce unneeded cache misses.

Another method is "streaming", where the cache figures out that you are reading from consecutive memory addresses, and uses this to start loading data before it is needed, reducing the average cost of a cache miss. That is often automatically. There may be instructions that load data from memory without caching it - if you process a gigabyte of data in consecutive memory, then caching any of it is pointless.

Then comes out-of-order execution: You may have one instruction waiting because of a cache miss, but other instructions not affected by this can go on executing. And with hyperthreading the processor executes two or more threads interleaving instructions; if thread A has to wait, then thread B continues at full speed.
> 4 votes

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


# Question
Title: Longest common sub-sequences with a condition
A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length.
Now you are given two arrays $S$ and $T$ with integers. You need to find a sub-sequence which is common to both arrays, has maximum length, and is a good sub sequence.

This is a pure dynamic programming problem, in which states ( I am not sure,but is is my guess) are $dp\[i\]\[j\]$ is answer for $S\[1:i\]$ and $T\[1:j\]$ ($A\[1:i\]$ means subarray of $A$ from $1$ to $i$). But I could not find transition between states, could anyone help me.

P.S - Problem link

# Answer
> 1 votes
A two-dimensional $dp\[i\]\[j\]$ is not fine enough to enable a recurrence relation. We need to track more information to be able to find the solutions to larger problems from the solutions of smaller problems.

Instead of $dp\[i\]\[j\]$, try filling the following two tables simultaneously

* $dp\\\_good\[i\]\[j\]$, which means the length of longest common good subsequence of $S\[1:i\]$ and $T\[1:j\]$ that ends at $S\[i\]$ and $T\[j\]$. This number is $0$ is $S\[i\]\not=T\[j\]$.
* $dp\\\_bad\[i\]\[j\]$, which means the length of longest common bad subsequence of $S\[1:i\]$ and $T\[1:j\]$ that ends at $S\[i\]$ and $T\[j\]$. Here a bad subsequence just means it is not a good subsequence. Again, this number is $0$ is $S\[i\]\not=T\[j\]$.

The answer will be the maximum of all $dp\\\_good\[i\]\[j\]$.

The above approach should work when you are looking for a sequence that "contains at least one pair of numbers which are adjacent and equal."

For the original problem, Task: ZAJ Stutter, we should define a good string as a stutter, i.e., a string that consists of successive pairs of two equal elements. A bad string will be defined as "almost a stutter", that is, a strings which becomes a stutter if we delete its last element.

---
Tags: algorithms, dynamic-programming
---


# Question
Title: What is an algorithm for minimizing the standard deviation of m sums summed from n summands? [with attempt]
I have m bins (sums) and n summands. Each summand goes into a bin. In order to minimize the standard deviation, I have a greedy algorithm that appears to accomplish this. I am not sure of the name, but would like to know more. All m bins must have a sum greater than zero at the end of the algorithm.

It seems simple:

sort the summands from highest to lowest.

for each summand in the summands: find the first available bin with minimum sum and place it in the bin

I haven't proved anything about it, but I've come up with a few test data sets and it appears to work.

EDIT --- Here is my attempt at an analysis:

The algorithm seeks to minimize the standard deviation of m sums summed from n summands.

The mean is always the sum of n summands divided by m, that is given.

To minimize the standard deviation, the algorithm makes the greedy choice to minimize the standard deviation, or variance (either). I want to prove that the greedy choice is always the optimal choice.

Suppose there is a bin m1, not the minimum sum bin, that is a better choice than minimum sum bin m. Adding to this bin will minimize the standard deviation around u.

In other words, placing the next value n into this m will maximally decrease the variance, meaning that we have maximally decreased the sum of (m\_i - u)^2. NOTE: m1' = m1 + x, m' = m + x, where x is the next summand.

So: remaining\_sum\_var + (m1' - u)^2 + (m - u)^2 \< remaining\_sum\_var + (m' - u)^2 + (m1 - u^2) where m1 is greater than m.

Simplify and factor:

(m1' - u)^2 + (m - u)^2 \< (m' - u)^2 + (m1 - u^2)

m1'^2 - 2um1' + 2u^2 + m^2 - 2um \< m'^2 - 2um' + 2u^2 + m1^2 - 2um1

m1'^2 - 2um1' + m^2 - 2um \< m'^2 - 2um' + m1^2 - 2um1

Ignoring linear terms whose difference will be constant (linearity).

m1'^2 + m^2 \< m'^2 + m1^2

If we have added summand x to m1 this expands to:

(m1 + x)^2 + m^2 \< (m + x)^2 + m1^2

m1^2 + 2m1x + x^2 + m^2 \< m^2 + 2mx + x^2 + m1^2

2m1x \< 2mx

m1 \< m, this is a contradiction. So it cannot be the case that there is a better choice than minimum sum bin m.

# Answer
No, your algorithm does not always produce the optimal solution. When $m=2$, this is (at least as hard as) the Partition problem, which is NP-hard. Wikipedia discusses the greedy algorithm and lists a counterexample which shows that your algorithm does not work.
> 1 votes

# Answer
I have discovered that the algorithm is the LPT Algorithm. It is covered here along with other algorithms for an example task: scheduling on parallel machines with fixed jobs. The problem is NP hard and NP complete. The polynomial time algorithms are approximations.

https://depositonce.tu-berlin.de/bitstream/11303/11089/3/grigoriu\_liliana\_2019.pdf
> 0 votes

---
Tags: algorithms, greedy-algorithms
---


title: A regular language derived from another

text:
# Question
Title: A regular language derived from another
This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular: $$ \\{x|\exists y \\; |y| = 2^{|x|} and \\; xy \in A\\} $$

I'm aware of the notion of regularity preserving functions, and that it would suffice to show that $f(x) = 2^x$ satisfies the property that for an ultimately periodic set $U$, $f^{-1}(U) = \\{m|f(m) \in U\\}$ is ultimately periodic. I'm struggling to $f$ has this property, but the book from which this comes implies a solution not using this is possible. It appears to be looking for a construction.

I can see that by repeated application of the idea behind the Pumping Lemma, if $A$ has DFL with $k$ states, that for any $x$ with $|x| \geq k$ then $$ \exists y \\; |y| = 2^{|x|} and \\; xy \in A\ \implies \exists y \\; |y| \leq k \\; and \\; xy \in A\ $$

But this doesn't give anything going in the opposite direction, that shows that some suitably short $y$ guarantees the existence of a $y$ of the required length.

Any help in solving this, or hint at how to progress would be very helpful.

# Answer
> 1 votes
In order to show that $f$ is regularity preserving, it suffices to show that $f^{-1}(U)$ is eventually periodic for $U = \\{ n : n \equiv b \pmod{a} \\}$, where $a$ is a prime power (here we are using the Chinese remainder theorem and the fact that the eventually periodic sets are closed under intersection).

For $f(n) = 2^n$, we consider two cases:

* If $a = 2^k$ then $f(n) \equiv 0 \pmod{a}$ for large enough $n$.
* If $a = p^k$ for an odd prime $p$, then $(2,a) = 1$, and so we can think of $2$ as an element of the multiplicative group $\mathbb{Z}\_a^\times$. In particular, $2^n \bmod a$ is periodic, the period being the order of $2$ in the group.

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


title: Tapered Quantization

text:
# Question
Title: Tapered Quantization
In Gonzalez et al it is mentioned that Tapered Quantization is

I am unable to figure this thing out. I have searched the whole internet, but nothing of the same appears. I need a help in understanding this matter, and if you can provide a picture that will be really helpful.

# Answer
> 0 votes
Basically from what I understood, it would be something like this....

In the quantization graph, we usually see a wave and the corresponding amplitudes marked at the axes and all those amplitude values are equally spaced from each other.

But according to tapered quantization, the constantly repeating values of the amplitudes will follow a finely spaced pattern in the plotter but with the values that appear rarely, those amplitude points/ values would face an non-equal pattern in between them(they would be marked or placed far away from each other).

---
Tags: image-processing
---


title: How to detect "tree-able" set-families?

text:
# Question
Title: How to detect "tree-able" set-families?
A set-family (a set of sets of elements) is called *tree-able* if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family corresponds to a path from the root to a leaf. For example, the following family is treeable:

```
{ {1, 2, 6}, {1, 3, 4, 5, 6} }

```

A possible tree is:

```
1 -> 6 -> 2
     |
     + -> 3 -> 4 -> 5

```

However, the following family is not treeable:

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

```

Is it possible to decide in polynomial time whether a given set-family is treeable (and construct a tree)?

# Answer
> 1 votes
An idea is to use a tree of set instead of a tree of indexes. One can develop it arbitrarily to a valid tree of indexes at end. An advantage is that you obtain all the valid trees with this process.

Let's consider the set of sets $A$ as a list $A\[i\]$. The initial tree $G(V, E)$ of set contains only one vertex which is the first set $root = s\_0$. And you keep a set $D$ of all indexes you already encoutered.

Then, we loop on other sets to add their information to the set tree. We consider the vertices of the tree starting from the root and adding new vertices when necessary.

let s define a function ***compare($s$, $v$)*** with $s$ a set and $v$, the set associated to a vertex of $G$.

* if $s == v$ then return true
* $c = s \cap v$
* if $c == v$ then

+ for $v\_s$ in sons(v) if ***compare(s-c, $v\_s$)*** then return true
    + if $s-c \cap D$ is not empty then return false
    + create a new son to $v$, $v\_s$ associated to set $s-c$ and return True
* in $G$, develop vertex $v$ to $v\_1$ and $v\_2$ associated respectively to sets $c$ and $v-c$, return ***compare($s$, $v\_1$)***

Thus, the main loop is:

* $root = A\[0\]$
* $D = A\[0\]$
* for $s$ in $A\[1:\]$
    + if ***compare(s, root)*** then $D = D \cup s$
    + else return false
* return true

When reaching the $i^{th}$ set, $G$ contains at most $i-1$ vertices, and you will recursively call the ***compare*** function up to $i-1$ times. Thus for $N$ sets covering $L$ different indexes (thus the set operations are $O(L)$), this algorithm solves the problem in $O(L N^2)$

An exemple: $A = \[\\{1, 3, 5\\}, \\{1, 2, 3, 4\\}, \\{ 1, 2, 3, 6\\}, \\{1, 2, 3, 5, 7\\}\]$

the initial tree $T$ has one vertex associated to the set $A\[0\] = \\{1, 3, 5\\}$

```
{1, 3, 5}

```

then you treat $A\[1\] = \\{1, 2, 3, 4\\}$, the root vertex has to be developed in

```
{1, 3} - {5}

```

to finally add a $\\{2, 4\\}$ son vertex to the root:

```
{1, 3} - {5}
|
{2, 4}

```

then comes $A\[2\] = \\{ 1, 2, 3, 6\\}$, after root, it remains $s = \\{2, 6\\}$. On $\\{5\\}$ child, there is no possibility as 2 is already in $D$. But on $\\{2, 4\\}$ child, it works after developing it.

```
{1, 3} - {5}
|
{2} - {4}
|
{6}

```

Finally comes $A\[3\] = \\{1, 2, 3, 5, 7\\}$, that will not work as 2 and 5 are both in $D$ and in different branches of $T$.

---
Tags: algorithms, graphs, trees, sets, dag
---


# Question
Title: what are the weakest preconditions of these following statements
what is the meaning of postcondition and weakest postcondition in terms of programing and what are weakest postconditons of following statements.

```
1. a=2*(b-1)-1   {a>0}
2. b=(c+10)/3    {b>6}
3. a=(a+2*b-1)   {a>1}
4. a=2*b+1;b=a-3 {b<0}

```

# Answer
Let's do the first one. You want to find what condition on $b$ will imply $2(b-1)-1\>0$. All you have to do is solve this inequality.

The other ones are similar.
> 0 votes

---
Tags: automata, programming-languages
---


# Question
Title: Finding certain elements when only able to ask in chunks
I have a set of $n$ elements. Of these elements $b\ll n$ are blue and $r=n-b$ are red. I want to find all blue elements.

My only way to discriminate between red and blue objects is by asking a blackbox that takes a fixed number $k$ of elements (with $n \gt k \gg 1$) and returns an approximation of how many of those elements are blue. The approximation is such that the returned number $\hat N\_b = N\_b + u$ is the real number of blue elements $N\_b$ combined with a Gaussian noise $u$ that has a Variance of $\text{Var}(u)\approx 1$ and an expected value of $E(u)=0$. $k$ is big enough that in a random sample the expected number of blue elements $E(N\_b)$ greatly exceeds the variance of the noise.

Is there an efficient algorithm to determine (to a certain probability) which elements are blue?

# Answer
You can eliminate the noise. Any time you make a query, repeat it 1000 times, use the average of the 1000 responses, and round it to the nearest integer. The noise in the result before rounding will have variance $1/1000$, so the probability that rounding creates an error is $\operatorname{erfc}(\sqrt{125})$, which is less than $10^{-54}$... i.e., negligibly small (smaller than the probability that a cosmic ray strikes your computer and causes it to give an incorrect result). This will increase the number of queries by a factor of 1000, i.e., by a constant factor, so it will not affect the asymptotic complexity.

Now once there is no noise, it becomes much easier to solve it. For instance, you can first find a set of $k$ objects known to be red, then repeatedly randomly sample $n/b$ unknown objects, add $k-n/b$ known-red objects, and query the result; if the response is 1, then you know that one of those is blue, and you can use binary search to find it. This will require about $O(b \log b)$ queries. I expect it should be possible to reduce this to $O(b)$ with more cleverness, but I haven't figured that out yet. A good question is whether you can do substantially better than $O(b)$, if $k \gg b$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Has category theory had an impact on computer science?
I've only learned bit of category theory, but so far its relation to type systems seems mostly descriptive. For example, you really don't need to know about coproducts to come up with the idea of union types.

I'm looking for references to ideas in computer science that were arrived at due to results in category theory. I'd be especially interested in results in areas other than PL such as machine learning.

# Answer
> 2 votes
* Categories can be used to model databases, and have been used for data integration. See also this paper. There's a pretty gentle introduction in chapter 3 of Seven Sketches in Compositionality.
* Coalgebras are a generalization of automata, and have provided insight into notions of bisimulation. I saw a talk about this, but also found this paper
* Closed symmetric monoidal categories have been used to model linear logic, but also to model quantum computation (which is itself related to linear logic). There's a Rosetta Stone paper that discusses this.
* CRDTs are a cornerstone of distributed computing, and while I don't understand it myself, it looks like there is some connection to category theory
* Guarded recursion and the Topos of Trees generalize step-indexing, which has been used to model higher-order separation logic. This is a tool for verifying programs with heap memory and/or concurrency, and has been applied in Iris.

I think it's also worth mentioning that the Programming Language concepts are not exactly isolated or esoteric. Monads originated in Category theory: my understanding is that Moggi (a category theorist) first applied them, and they were brought into Haskell by Philip Wadler.

But, monadic interfaces are everywhere. Errors in Rust are monadic, as are basically any langage's `Option` type. Promises in Javascript are monads. Using monads gives a beautiful implementation of Software Transactional Memory, a lock-free approach to concurrency.

And, of course, category theory is basically at the heart of modern logic research, which underlies most CS theory.

# Answer
> 1 votes
Not what you are hoping for, but:

An early version of the OCaml language was based on the idea of a categorical abstract machine "represented by Cartesian closed category".

Haskell's monad classes "are based on the monad construct in category theory".

---
Tags: reference-request, category-theory
---


# Question
Title: Is there any neutral element for the cryptographic hash function SHA256? (or its variants)
My question is the following: Is it possible to compute a string given that after applying a SHA256 function the result is the same string?

Edit for clarification: If my string A is a neutral element of SHA256, then: A == SHA256(A) is true. Does A exists?

# Answer
No one knows. It is believed to be computationally infeasible to find such a string, if one exists. No one knows whether such a string exists.

By standard heuristics (modelling SHA256 as a random function), there is approximately a $1/e\approx 0.368$ chance that no such input exists, and approximately a $0.632$ chance that such an input exists, so if I were forced to bet, I would bet that it's more likely there exists such an input than that there doesn't, but no one knows. Don't interpret this chance too seriously: for the specific SHA256 function, either such an input exists or it doesn't. We don't know which is the case.

If such an input exists, it is believed that it would take about $2^{256}$ steps of computation to find it, which is completely infeasible.
> 3 votes

---
Tags: cryptography, exact-string-matching
---


# Question
Title: 3Sum Why this O(nlogn) solution doesn't work?
I have been doing LeetCode and tackled the problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is $O(n^2)$ or $O(n^2 \times \log n)$ and not only that but the problem is a highly researched topic so I don't think I found a better solution but can't see why my approach wouldn't work, can use help to figure it out.

The problem is the following
Find three numbers in an array such that $a + b + c = t$,
the LeetCode problem is slightly different in which you need to find the closest sum.

My code is the following:

1. Sort the array.
2. Start with two pointers `i=0` and `j= last element of array`
3. Use binary search between `i` and `j` to find `m` such that `arr[m] == target - arr[i] - arr[j]`, if such `m` doesn't exist return `m` such that `arr[m]` is the closest.
4. If `arr[i] + arr[m] + arr[j] == target` then your finished.
5. Otherwise if `arr[i] + arr[m] + arr[j] < target` then add 1 to `i` else subtract 1 form `j`.
6. Repeat 3 → 5 until `j - i == 2`
7. Return the best found `i,m,j`

The logic in step 5 is that if the solution found is less than the target then we should increase `i` such that our next guess is bigger.

Code:

```
def binSearch(arr, s, e, t):
    m = (s + e) // 2
    r = m
    d = 9999
    while s <= e:
        m = (s + e) // 2
        if arr[m] == t:
            return m
        elif arr[m] > t:
            e = m - 1
        else:
            s = m + 1

        if d > abs(t - arr[m]):
            d = abs(t - arr[m])
            r = m
    return r

class Solution:
    def threeSumClosest(self, nums, target: int) -> int:
        nums.sort()

        s = 0
        e = len(nums) - 1
        minn = 999999
        t = ()
        while e - s >= 2:
            left = nums[s]
            right = nums[e]
            remaining = target - (left + right)
            m = binSearch(nums, s + 1, e - 1, remaining)
            middle = nums[m]
            r = left + middle + right

            # print("i's: ", (s,m,e))
            # print("values: ", (nums[s], nums[m], nums[e]))
            # print("r", r)
            # print("**************")

            if r == target:
                return r
            elif r < target:
                s += 1
            else:
                e -= 1

            if abs(target - r) < minn:
                minn = abs(target - r)
                t = r
        return t

```

# Answer
This fails for, e.g., \[1, 9, 55, 55, 100\], t=111. The first iteration finds 110 and increases i to exclude 1 as a possibility, but the only solution, \[1, 55, 55\], needs 1.

The basic problem is that when you increase i or reduce j, you are assuming that the element you just advanced past is not needed -- that there exists some solution that does not include it. But this is not justified by anything, and it could well be that all solutions need that element.

A great way to test algorithm ideas like this is to write a small program that generates many small random inputs, and compare the result of your algorithm on each of them to the result of a known-correct brute-force approach.
> 2 votes

---
Tags: algorithms, algorithm-analysis, correctness-proof, search-problem
---


# Question
Title: Find maximal subset with interesting weight function
You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th column, then add up all the maximums.

For example, for $n = 4$, $k = 2$ and rows $(1, 4), (2, 3), (3, 2), (4, 1)$ the weight of subset $(1, 4), (2, 3), (3, 2)$ is $\max\\{1, 2, 3\\} + \max\\{4, 3, 2\\} = 3 + 4 = 7$.

The question is, having $m \leq n$, find the subset of size $m$ (from given $n$ rows) with maximal weight.

The problem looks trivial when $m \geq k$, but how can one solve it for $m \< k$? Looks like dynamic programming on subsets could work for small $k$, isn't it? Are there other ways to do it?

# Answer
Definitely NP-hard, since it can be used to encode a maximisation form of Vertex Cover in which we ask for the maximum number of edges that can be covered by any subset of $k$ vertices: The input matrix here is just the incidence matrix of the graph, with vertices in the rows and edges in the columns.
> 1 votes

---
Tags: optimization, dynamic-programming
---


# Question
Title: Sequencing or continuation-passing in pure lambda-calculus
I am trying to solve the following exercise given here.

Consider the following number representation. How to define the addition?

```
|0| = λx.x
|1| = λx.λx.x
 ...
|n + 1| = λx.|n|

```

The successor and predecessor operators are easy to define:

```
Succ n = λx.n
Pred n = n (λx.x)

```

An "obvious" solution for defining the addition is to use the successor operation plus the test for zero together with the fixed point combinator, something like **(Y F)** for **F** given below (the operator **if** and booleans are defined as usual):

```
F = λf.(λm n. if (Is0 m) n (Succ (f (Pred m) n))

```

But defining **Is0** seems non-trivial. The problem is that a numeral **|N|** consumes N+1 arguments, and N arguments are simply erased by it. Hence, if I apply such a function, it seems reasonable to stop its application when it becomes clear that the numeral, e.g. is not an identity. I guess it is some sort of continuation, but I cannot imagine how to model it in the pure lambda-calculus. Maybe someone knows any tips that may help?

A sequencing operator can also help to define the addition. If an application of a numeral **|m|** is delayed until a numeral **|n|** is applied to *all* its arguments, the result will be exactly a numeral **|n+m|**. Maybe there exists a variant of such a sequencing combinator in the pure lambda-calculus?

The answer which is provided by the author of the exercise uses a non-pure operation (namely, **IsProcedure** which checks whether its argument is a function).

**UPD:** It is not hard to do a CPS in lambda-calculus (details for CBV can be found here). Seems that is not enough for solving the problem.

**UPD**: If we have some version of **quote-eval** functions for the pure lambda-calculus, then there must be a function $eq$, which recognizes whether the quoted lambda-expressions are *syntactically* equal, and we can construct **Is0** using $eq$. But I doubt that $eq$ is definable. The reason is "genericity lemma" (Barendregt book, lemma 14.3.24). If we were able to test equality on the quoted lambda-terms then ($eq$ (**Quote** $\Omega$) (**Quote** $\lambda x.x$)) would return $False$, and the genericity implies that ($eq$ (**Quote** $\lambda x.x$) (**Quote** $\lambda x.x$)) would also return $False$. Does that contradict a possibility of constructing **Quote** in the pure lambda-calculus?

# Answer
I do not think you will find what you are looking for in the pure lambda calculus. The key is this statement you made:

> A sequencing operator can also help to define the addition. If an application of a numeral |m| is delayed until a numeral |n| is applied to all its arguments, ...

Well, models of the lambda calculus are supposed to be like:

$$U \cong U^U$$

And the point of *this* is that every semantic value $u \in U$ may be applied to something. So it makes no sense to talk about something being "applied to all its arguments." There is no value that cannot be applied to more arguments in the pure lambda calculus.

I don't know off hand of a model/argument that this representation of naturals makes it impossible to implement `IsZero`, although some thinking about it makes it seem unlikely. However, if it is to be possible in the pure lambda calculus, it will have to make sense semantically, and not be based on notions that are only syntactic.

Edit: here is a sketch of an argument. A definition of $\mathsf{IsZero}$ must eventually reduce like:

$$\mathsf{IsZero}\ n \rightsquigarrow^\* n \overrightarrow v$$

The reason is that applying to some number of values is the only mechanism in the lambda calculus to actually distinguish between numerals. It needs to be the case that: $$0 \overrightarrow v = \mathsf{true} \\ \mathsf{s}n \overrightarrow v = \mathsf{false}$$ However, for every $\overrightarrow v$ it is the case that: $$||\overrightarrow v| + k|\overrightarrow v = |k|$$ (where $|\overrightarrow v|$ is the length of $\overrightarrow v$). But only $|1| = \mathsf{false}$ (if that is the convention chosen). In English, there is no bound on the number of terms required to get a boolean by applying a numeral. So there cannot be a $\overrightarrow v$ that satisfies the equations for all numerals, and thus $\mathsf{IsZero}$ cannot be defined.
> 2 votes

# Answer
The most straightforward way to define addition in lambda-calculus is to treat the numbers as if they were linked lists, and catenate the lists. To do this right, it is necessary to use extra variables to replace the outer variables of each number, so the resulting expression for the second number can be substituted for the inner variable of the resulting expression for the first number. This yields the following expression for addition:

```
  λw.λx.λy.λz.w y (x y z)

```
> -2 votes

---
Tags: lambda-calculus
---


# Question
Title: What is the minimum required storage for a sparse, depth-first octree?
For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree on disk, given the following conditions:

* It is very sparse (i.e., not all nodes exist), but potentially deep (a depth of 20 or beyond)
* It is stored depth-first (pre-order)
* All parent nodes up to the root node must be stored (i.e., it is not sufficient to store just the leave nodes)
* The amount of data per node is a global constant

The best I can come up with is ~~6~~ 7 bits per node: 3 bits to indicate the position of a node with respect to its parent, and ~~3~~ 4 bits to store how many child nodes exist. However, intuition tells me there should be a more efficient way. Please note that algorithmic efficiency is not part of the question, as its representation in memory will be different anyways.

P.S.: Please let me know if CS is not the right SE venue for this kind of question.

**Update**

The resulting data structure will be stored in a file on disk, thus the need for an efficient encoding of the octree. There are additional data files that contain information associated with each existing node (e.g., solution data). To have a one-to-one relationship between nodes ("cells") in the octree file and the datasets, it is required to store all internal nodes (i.e., non-leaf nodes) in the octree file as well.

*Example*

An octree with 5 nodes: 0, 1, ..., 4. Their relationship is the following:

* 0 is the root
* 1 is child 0 of node 0
* 2 is child 1 of node 1
* 3 is child 5 of node 1
* 4 is child 1 of node 0

The resulting tree would look something like this (with missing nodes omitted)

`0
 / \
 1 4
 / \
2 3`

and the nodes need to be stored `0 1 2 3 4` (pre-order depth-first).

# Answer
> 2 votes
The number of octrees with $n$ nodes is OEIS sequence A007556:

$$T(n) = {8n \choose n}/(7n+1)$$

I worked this out, incidentally, by writing a short program to generate the first few values of $T(n)$ and then searching for it.

If you had no other information than $n$, then the minimum number of bits required to store an octree with $n$ nodes is $\log\\,T(n)$. (We're doing information theory here, so all logarithms are in base 2 unless otherwise specified.) Using Stirling's approximation to the logarithm of the factorial:

$$\log n! = n \log n - n \log e + O(\log n)$$

We find:

$$\log\\,T(n) = (24 - 7 \log 7) n + O(\log n)$$

Which works out to $24 - 7 \log 7 \approx 4.349$ bits per node. So to answer the first part of your question, this *is* the theoretical minimum. You cannot do better than this.

Now we just have to address the second part: How close can we get?

Consider a bit vector of size $8n$, $8$ bits per node, where you put a 1 if the node has a child in that slot, and a 0 if it doesn't. This obviously uses about twice the space theoretically needed.

However, 0's and 1's don't occur with the same frequency. Specifically, given an octree with $n$ nodes, exactly $n-1$ of the bits must be 1 (exercise: why?), leaving $7n+1$ of them 0. The entropy of a bit is, therefore, approximately:

$$H = -\frac{1}{7} \log \frac{1}{7} - \frac{6}{7} \log \frac{6}{7} \approx 0.59$$

So you should be able to compress the bit vector to $8nH \approx 4.733n$ bits.

The actual compression method that I will suggest, because it's easy to understand and doesn't use anything complicated to implement like arithmetic coding, is Elias-Fano coding with parameter $b=2$.

We'll use your octree as an example. The bit vector corresponding to your exanple is:

```
11000000 01000100 00000000 00000000 00000000

```

We know that because $n=5$, the number of bits that are set must be $n-1=4$. We work out the indexes of the bits that are set:

$$\left\\{0, 1, 9, 13\right\\}$$

Or in binary, using $\left\lceil \log(8n) \right\rceil = 6$ bits per entry:

```
0000 00
0000 01
0010 01
0011 01

```

I've separated the low order $b$ bits for a reason. The compressed representation has two parts, one for the high-order bits and one for the low-order bits.

For the low-order bits, we just store these in an array. That is:

```
00 01 01 01

```

For the high-order bits, we count the patterns. Since there are no indexes that are larger than $8n-1=39$, There are only 10 possible patterns for the high-order bits:

$$\\{0000,0001,0010,0011,0100,0101,0110,0111,1000,1001\\}$$

We count the number of indices with each of the high-order patterns, and then encode those counts using a unary code:

```
110 0 10 10 0 0 0 0 0 0

```

(In practice, you probably don't need to work out all the high-order bit patterns, just stop when you run out of indices. But I digress.)

On this example, the representation uses 8 bits for the first array, and 14 bits for the unary-encoded bit vector, for a total of 22 bits, or 4.4 bits per node.

Recall that the asymptotic theoretical minimum is 4.349 bits per node.

Working out the asymptotic size of this representation as $n \rightarrow \infty$ is left as an exercise. So is actual code to do the compression and decompression.

Finally, I know you didn't ask about algorithmic efficiency, but storing the bit vector in an SDArray with succinct rank/select indices (there are implementations all over the place; look them up), you should be able to make this data structure random access in close to constant time. That is, you should be able to query the octree in its compressed form. The details are, again, left as an exercise.

# Answer
> 1 votes
Assume simple setting, data is three chars, the coordinates are in fixed-point float

* 0) "tak"
* 1) "kot"
* 2) "mak" \[76, 102, 179\]
* 3) "las", \[51, 76, 153\]
* 4) "pas" \[179, 179, 153\]

The floating point values converted to 8 bit fixed point and z-order curve computed. For example take 3)

51 (110011b), 76 (1001100b), 153 (10011001b)

Interleaved

* `51 -> 000 000 001 001 000 000 001 001`
* `76 -> 000 001 000 000 001 001 000 000` shift by one to the left
* `153 -> 001 000 000 001 001 000 000 001` shift by two to the left
* `Orred 100 010 001 101 110 010 001 101`

Coordinates converted to codes:

2. 100 011 110 100 001 011 110 100
3. 100 010 001 101 110 010 001 101
4. 111 000 011 111 100 000 011 111

sort encoded indices

3. 100 011 110 100 001 011 110 100
4. 100 010 001 101 110 010 001 101
5. 111 000 011 111 100 000 011 111

The index of the child is encoded in the bit triplet at the current level of tree. While traversing the level counter should be kept.

Store to file, add 1 bit per node

* 0 - internal node
* 1 - leaf

Check the location code, while the parent code matches, we are in the same subtree, otherwise traverse up until the next code location matches or to root.

For simplicity I will split it into three files (but it may be one, since the widths are constant)

* type) `0111` (bits)
* data) `takkotlasmakpas` (3 letter string)
* indices) `100011110100001011110100100011110100001011110100111000011111100000011111` (bits)

How it would work?

Checking the location means to compare bits from the most significant one taking as many bit triplets as level counter shows, here root has level 0

1. Read data, create root
2. Read index, data and type
3. if type is 0, store internal node as n-th child from location index at current level, store data, go to this node, increase level counter read another data and type, repeat 3) until type is 1
4. if type is 1, store child, read next index, data and type. If location code mismatches then traverse up until full match or root encountered. At every step up decrease counter.
5. if not EOF goto 2

Here overhead is 1 bit per existing node only.

How would it work in the example?

`create root ("tak")`

`read first index (100 011 110 100 001 011 110 100), read type (0) and read data ("kot")`
`create node as the 4-th child (100), store data`

`read type and data (1, "las"),`
`store data in node, put the next node as 3-rd (011) child, ++level`

`read (1, "las"),`
`create 6-th node (110) and store "las", decode index into coordinates`
`(100 011 110 100 001 011 110 100 -> [76, 102, 179])`

`store current location code (100) as last one (triplets up to level)`

`read another one, (100 010 001 101 110 010 001 101), (mak, 1),`
`check whether location code matches up the last one (here it is 100 == 100)`

`put node as 2-nd (010) child, store data, decode index into coordinates
(100 010 001 101 110 010 001 101 -> [51, 76, 153])`

`read another one, (111 000 011 111 100 000 011 111),`
`the location code mismatches (111 != 100), while no match go up (or until root level)`

`store node as 7-th (111) child, decode index into coordinates`
`(111 000 011 111 100 000 011 111 -> [179, 179, 153])`

# Answer
> 0 votes
## fixed-size node

Pseudonym has almost convinced me that it's not possible to store such a tree with only 4 extra bits per node. Here's one way to store it with a fixed overhead of 5 extra bits per node:

* 3 bits to indicate this node's position relative to its parent
* 1 bit to indicate whether or not it is a leaf (i.e., whether or not it has any children)
* 1 bit to indicate whether this node is the *last* of its siblings.

Reading each node one fixed-size block at a time in depth-first pre-order, we have something like:

```
node_list = []
total_nodes = 0

read_branch( parent_index, current_index, file, node_list ):
    disk_node = read_node( file )
    node_list[current_index].data = disk_node.data
    node_list[current_index].parent = parent_index
    node_list[current_index].position_relative_to_parent = disk_node.relative_position
    global total_nodes += 1
    # read all children and their descendents first, if any
    if( disk_node.has_children ):
        total_children =
            read_branch( current_index, current_index + 1, file )
    else:
        total_children = 0
    # read next sibling, and all other siblings, and their descendents, if any
    if( disk_node.has_sibling ):
        total_siblings_and_their_descendents =
            read_branch( parent_index, current_index + 1 + total_children, file )
    else:
        total_siblings_and_their_descendents = 0
    return (1 + total_children + total_siblings_and_their_descendents)

read_entire_tree():
    file = open_file("the_octree")
    root_index = 1
    estimated_total_nodes = read_branch( null, root_index, file, node_list )
    assert( estimated_total_nodes == total_nodes )

```

## Other alternatives

Here are some ways of compressing it even more, but in ways that are significantly more complex and bug-prone.

The octree could be stored in even less space if it used some variable-sized encoding that used less than 5 bits per node most of the time (even if it required much more than 5 bits per node occasionally). (Huffman coding, arithmetic coding, gzip, LZJB, etc).

Whenever a node had more than 2 children, rather than always store the children in some fixed order, a little information could be encoded into the order the children were stored. For example, perhaps each node could have 2 bits that indicated whether it was a leaf (0 children), or had 1, 2, or "more" children. Then if it had "more" children -- i.e., at least 3 children -- then the first 3 children could be read, and the order of those children -- ABC, ACB, BAC, BCA, CAB, CBA -- could be decoded into a number 0..5 and interpreted as indicating 0 to 5 *more* children past the 3 already read.

I suspect that storing the tree in some other order -- perhaps breadth-first or leaf-first -- might allow the tree to be stored in less space.

---
Tags: data-structures, trees, encoding-scheme, storage
---


# Question
Title: Making an algorithm that picks a unique random number in fixed set more efficient
I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have designed an algorithm that can generate a unique number in a range then check if it isn't in the list of account numbers and then add it to the list.

My Issue is that as the number of available account numbers decreases the more times the algorithm will need to generate new numbers which will create exponential overhead. especially when generating 6+ digit long account numbers.

My solution to this problem was after x number of attempts I would run a second operation that would find all missing account numbers in the list and return one at random. This would work but leaves me with the same problem.

**Flowchart of my Algorithm**

Country Code is part of the user registration and each country has it's own selection of sortcodes

so the hierarchy is:

CountryCode \> Sortcode \> Account Number

The only other solution That I can think of that would remove the overhead issue and give me a unique random number in a set, would be to pre-generate the set of numbers in random order and then pick off the top number until the set is empty. However, I'm not sure where this list would be kept when the application isn't running and I feel generating the numbers at runtime would be more suitable.

If you need any further information I will provide.

# Answer
> 1 votes
If you want to generate a list of $n$ random codes, from a space of at least $2n$ possible codes, then simple rejection sampling is easy and efficient: choose a random code, if it is a repeat throw it away and repeat, otherwise output; and repeat. The running time will be $O(n)$. This is the method you have rejected in the question.

If you want to generate a list of $n$ random codes, from a space of not much more than $n$ random codes, then use a Fisher-Yates shuffle. Create a list of all random codes (0, 1, 2, 3, ...), then randomly permute it using a Fisher-Yates shuffle, then take the first $n$ codes in the resulting list. The running time will be $O(n \log n)$.

---
Tags: algorithms, time-complexity, efficiency, random-number-generator
---


# Question
Title: How does virtual memory work when it need to save data in physical memory into disk?
I'm reading a textbook which desribe VM as:

> a data structure stored in physical memory known as a page table that maps virtual pages to physical pages. The address translation hardware reads the page table each time it converts a virtual address to a physical address. The operating system is responsible for maintaining the contents of the page table and transferring pages back and forth between disk and DRAM.

A page table is an array of page table entries (PTEs). M. If the valid bit is set, the address field indicates the start of the corresponding physical page in DRAM where the virtual page is cached. If the valid bit is not set, then a null address indicates that the virtual page has not yet been allocated. Otherwise, the address points to the start of the virtual page on disk.

So my question is, let's the PP0(VP1) has been modified and need to be written back to disk to make the change permanent. But the the PTE1 only has address(PP0) pointed to main memory, it has lost disk address VP1, so how can the changes be made to disk in this scenario?

# Answer
> 3 votes
There are a few options:

1. if a page is in memory then it cannot be on disk as well, As such there is no duplication and the issue doesn't exist.
2. there is more than just the MMU's pagetable to hold paging information. This mean that the kernel has an auxiliary data structure that says where the page is on disk and the MMU page table only tracks what is in memory. This solution allows memory mapping of files whether they are on disk or over the network.

---
Tags: computer-architecture, memory-management, memory-hardware, virtual-memory
---


# Question
Title: Asymptotic analysis of $T(n) = T(n/5) + T(4n/5) + \Theta(n)$
If I have a recurrence relationship like this: $$T(n) = T(n/5) + T(4n/5) + \Theta(n),$$ how would I analyze its rate of growth?

I believe I can't use the master theorem. I tried to draw a tree but some of the branches terminate earlier. There's a way to calculate the big-O notation by assuming $T(n) \le 2 T(4n/5)$, but does this result in a tight estimate?

# Answer
> 3 votes
Your recurrence can be solved using the Akra–Bazzi theorem, a vast generalization of the master theorem. The result is $\Theta(n\log n)$.

You can also see this using a recursion tree. The root is labeled $n$. An internal vertex $m$ has children labeled $m/5$ and $4m/5$. Vertices are leaves if their labels is at most some arbitrary positive constant $C$, say $C=1$. The running time is proportional to the sum of all labels.

We can partition the vertices in the tree to levels according to their distance from the root. The first $\log\_5 n$ levels of so are "complete", that is, their labels sum to $n$, and there are $\log\_{5/4} n$ levels in total, so the sum of labels is between $n\log\_5 n$ and $n\log\_{5/4} n$ levels. In particular, the complexity is $\Theta(n\log n)$.

---
Tags: asymptotics, discrete-mathematics
---


# Question
Title: Proof that languages are Turing-recognizable iff computably-enumerable
A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes.

In the "only if" direction, we assume that a Turing machine $M$ recognizes some language $L$. We list all the strings in the input alphabet (in lexicographic order, say) as $s\_1,s\_2,s\_3,\dots$

We then construct an enumerator $E$ that for each $i=1,2,3,\dots$ simply runs $M$ **for $i$ steps** on each input $s\_1,s\_2,s\_3,\dots, s\_i$; then it prints any $s\_j$ which is accepted by $M$. $E$ is what we need.

Now, since I know that strings are finite, why should I run $M$ **for $i$ steps** on the first $i$ strings, when I could just run it on the $i$-th string? It feels like an unnecessary complication.

P.S. Another question was asked about this, but it addressed a different doubt: Question for "Only if" part for the theorem "A language is Turing-recognizable iff some enumerator enumerates it."

# Answer
If you run $M$ on the $i$-th string then it might never halt, so your algorithm will be stuck. The idea is that if $M$ does halt on the $i$-th string, say after $j$ steps, then we will see it once we get to the $\max(i,j)$-th string.
> 2 votes

---
Tags: formal-languages, turing-machines, computability, enumeration
---


# Question
Title: What do these Big-O notations mean in context of comparison
What do the following mean, in the context of `greater than`, or `smaller than`?

$$ O(n \log n) \> O(n) $$

$$ O(nlogn) \< O(n^2) $$

# Answer
In this context, this comparison means the `subset of`. Hence, $O(n\log n) \> O(n)$ means All members of $O(n)$ exist in $O(n \log n)$ as well or $O(n) \subset O(n \log n)$. For example, $f(n) = \sqrt{n} \in O(n)$ and $f(n) \in O(n\log n) $ and $g(n) = n \log n \not \in O(n)$ and $g(n) \ \in O(n \log n)$.
> 3 votes

---
Tags: big-o-notation
---


# Question
Title: Error correction code without error detection
Error detection and correction codes require many bits of redundancy for correcting even a modest number of erroneous bits. However, we often have out-of-band methods to determine when and where the errors occured, such as if we observe a voltage spike that exceeds the usual signal levels.

1. Are there any well-established error correction codes that use less redundancy, but require that the receiver explicitly declares some bits as unknown and corrects only those? In theory, we should be able to correct one erroneous bit for every bit of redundancy.
2. Are there any such codes which are also able to detect and correct a small number of unknown errors, in addition to the known ones?
3. Are there any such codes where the receiver augments each bit with some kind of non-binary confidence score, and the code then finds the most likely original sequence?

# Answer
> 2 votes
You might be interested in the binary erasure channel, in which each symbol is erased with probability $p$. The capacity of this channel is $1-p$, and there are practical erasure codes that achieve it.

In the second scenario you describe, some symbols are erased, and some are received with error. This is known as the binary symmetric error channel, and there is some work on it.

Finally, if each symbol is associated with a *confidence*, then the corresponding notion of decoding is soft decoding.

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


# Question
Title: Why does case 3 regularity condition of master theorem always hold when f(n)=$n^k$ and f(n)=$\Omega(n^{\log_b a+\epsilon})$
I know that the regularity condition for master theorem Case#3 stating that \[$af(\frac{n}{b}) ≤ cf(n)$ for some constant $c \< 1$ and all sufficiently large n\] always holds when the $f(n)=n^k$,$f(n)=\Omega(n^{\log\_b a+\epsilon})$. However, I have tried to prove this statement, and was unable to do so.

The question is how to prove that the regularity condition of master theorem case 3 always holds on the two above-mentioned functions.

# Answer
If $f(n) = n^k$, we know that $k \> \log\_ba$, since this is Case 3; this is the meaning of the second condition in your post. We have to find $c\<1$ such that for large $n$, $$ a(n/b)^k \< cn^k. $$ We can simply choose $c = a/b^k$. Since $k \> \log\_b a$, we get $c \< 1$.

---

If all you know about $f$ is that is satisfies $f(n) = \Omega(n^{\log\_ba+\epsilon})$ for some $\epsilon\>0$, then you cannot conclude that $f$ is regular. Indeed, given $a,b,\epsilon$, take $$ f(n) = a^{\tfrac{1}{2} \lfloor \log\_{b^2} n \rfloor(1+\epsilon/\log\_ba)} $$ Then $$ f(n) \> a^{\tfrac{1}{2}(\log\_{b^2} n - 1)(1+\epsilon/\log\_ba)} = \Omega(a^{\log\_b n(1 + \epsilon/\log\_b a)}) = \Omega(n^{\log\_b a(1+\epsilon/\log\_b a)}) = \Omega(n^{\log\_b a+\epsilon}). $$ On the other hand, if $n = b^{2m+1}$ for integer $m$ then $f(n/b) = f(n)$, and in particular, no $c\<1$ satisfies $af(n/b) \leq cf(n)$. Since $b^{2m+1}$ can be arbitrarily large, we conclude that $f$ is not regular.
> 2 votes

# Answer
In case of $f(n)=\Omega(n^{\log\_b^{a+\epsilon}})$, we need to find $c\<1$ such that for sufficiently large n

$a\*\Omega((\frac{n}{b})^{\log\_b^{a+\epsilon}})\leq c\*\Omega(n^{\log\_b^{a+\epsilon}})$

By slightly modifying the left part we obtain the following inequality

$\frac{a}{a+\epsilon}\*\Omega(n^{\log\_b^{a+\epsilon}})\leq c\*\Omega(n^{\log\_b^{a+\epsilon}})$

Thus we can take $c=\frac{a}{a+\epsilon}$ and here $c\<1$ as $\epsilon\>0$ according to case 3 of master theorem.

## Important Note

This hypothesis has been shown to be wrong in the answer by Yuval Filmus. Regardless, I am keeping it, for anyone not to make a similar mistake.
> 0 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: what will be space complexity for snippet for(i=1 to n) int x=10;?
The space complexity of the code snippet given below:

```
int *a = malloc(n * sizeof(int));
int sum=0;
for (i = 0; i < n; i++)
{
    scanf("%d", &a[i]);
    for (j = 0; j < n; j++)
    {
        int x = a[i];
        sum = sum + x;
    }
}
free(a);

```

This is question of a test. I answered it $O(n)$, considering space only for array and constant space for rest of the code. But in the answer they given $O(n^2)$ and there explanation is "The array is of size $n$ and the inner most loop we are declaring a variable $x$ every time the loop is executed, this loop is executed $O(n^2)$ time hence overall space complexity is $O(n^2)$." Now my doubt is what should be space complexity of

```
for (i = 1; i <= n; i++)
    int x = 10;

```

What i thought is that it should be $O(1)$ because in each iteration variable $x$ gets destroyed.

# Answer
You are right. Are they saying if we run that loop n times then n different variables having name x will be created? This doesn't happen. Moreover, it is good practice to avoid unnecessary global variables. To check this yourself, you can try printing the logical address of x using this:-

```
for(i=0;i<10;i++)
   {
       int x=1;
       printf("%d\n",&x);
   }

```

The same logical address gets printed every time. So yes, the total space used by this is not dependent on n. It is O(1).

By the way, You could have thought that x gets destroyed only once at the end of last iteration and meanwhile all the values a\[i\] would be getting overwritten on the same x in each iteration. Even this is not what happens. x gets destroyed after each iteration and the space is made available for use by other parts.
> 2 votes

---
Tags: algorithms, space-complexity, space-analysis
---


# Question
Title: Given a row sum vector and a column sum vector, determine if they can form a boolean matrix
For example, for a boolean matrix of size $3x4$, the column sum vector $C = (3, 3, 0, 0)$ and the row sum vector $R = (2, 2, 2)$ form a match because I can construct the boolean matrix:

$$ \begin{matrix} & \begin{bmatrix} 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 \end{bmatrix} & \begin{pmatrix} 2\\2\\2 \end{pmatrix} = R \\ C = &\begin{pmatrix} 3 & 3 & 0 & 0 \end{pmatrix} \end{matrix} $$

However, the row sum vector $R' = (4, 1, 1)$ doesn't form a match with $C$.

So given two vectors whose values are sorted in a non-increasing order $C\_w$ and $R\_h$, and whose accumulated sum is the same, $T = \sum\_jc\_j = \sum\_ir\_i$, how can I polynomically check if $C$ and $R$ form a matching because I can form a matrix $M\_{h,w}$ having $C$ and $R$ as colum and row sum vectors respectively?

More specifically, in case it can help to make the check algorithm faster, in my specific case, C and R has the following properties:

* $h \leq w$
* The number of positive values of $R$ and $C$ is $\> w$. For example, $C$, in the example, has two positive values and $R$ has three positive values, and it happens that $2 + 3 \> w = 4$.

# Answer
> 2 votes
Based on the, apparently famous paper on the field, Ryser 56, and the thesis recommended by @orlp, the test to know if a row and column sum vectors forms a match, e.g., a matrix $M\_{h,w}$ exists having these row and column sum vectors, is the following one:

* Let $R\_h$ be a vector of $h$ elements sorted in a non-increasing order ($r\_1\geq r\_2\geq\ldots\geq r\_h$).
* Let $C\_w$ be a vector of $w$ elements sorted in a non-increasing order ($c\_1\geq c\_2\geq\ldots \geq c\_w$).

Is there exists a matrix $M\_{h,w}$ with $h$ rows and $w$ columns having $R$ and $C$ as row sum and column sum vectors respectively? We say that $R$ and $C$ **form a match** if such $M$ exists (this definition of *matching* is mine because it helps me explaining).

\[*Note:* The restriction of $R$ and $C$ being sorted is to simplify the test. If $R$ and $C$ are not sorted, but their sorted versions forms a match because they can form a matrix $M$, then $R$ and $C$ form a match because you can always reorder the rows and columns of $M$ so their column and row sum vectors equals $R$ and $C$. *$-$ end note*\]

Given ($\\#$ means size of the set, in case you don't know, because I didn't):

$$ \tag{1} \begin{matrix} C^\* = \begin{bmatrix}c^\*\_1&\ldots&c^\*\_w\end{bmatrix}, & c\_j^\* = \\#\\{\ i\ |\ r\_i\geq j\\} & \forall j\in\[1, w\] \end{matrix} $$

The conditions for $M\_{h,w}$ to exists are:

$$ \tag{2} \sum\_{i=1}^hr\_i = \sum\_{j=1}^wc\_j $$

$$ \tag{3} \forall i\in \[1,h\], r\_i \leq w $$

$$ \tag{4} \forall j\in\[1, w\], c\_j \leq h $$

$$ \tag{5} C\prec C^\* $$

* Equation $(2)$ means that $R$ and $C$ must both count the number of $1$s in the to-be-determined matrix $M$, and so both sums must match. Otherwise $M$ doesn't exist.
* Equation $(3)$ and $(4)$ combined means that both $R$ and $C$ must reflect the fact that no row or column of $M$ can have more $1$s than the width or height of $M$ respectively. Otherwise $M$ doesn't exist.
* Equation $(5)$ is the core of the test. Let's me explain it step by step. In his paper, Ryser starts by creating a "maximal form of $M$", which is an intermediary matrix $M^\*\_{h,w}$ where each row $i$ has, starting from the beginning of the row, as many contiguous $1$s as indicated by $r\_i$. Once that has been done, $C^\*$ is just the column sum vector of $M^\*$. For example, for a $3\times 4$ matrix $M$ with $R = (3, 3, 1)$, the maximal form of $M$ would be:

$$ \begin{matrix} & M^\* = &\begin{bmatrix} 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 0 \end{bmatrix} & \begin{pmatrix} 3\\3\\1 \end{pmatrix} = R \\ &C^\* = &\begin{pmatrix} 3 & 2 & 2 & 0 \end{pmatrix} \end{matrix} $$

Afterwards, he proves that he can construct $M$ from $M^\*$ by moving $1$s around only within their own rows (to don't alter $R$) to make $C^\*$ become $C$, provided that $C^\*$ majorizes $C$, which is precisely the equation $(5)$. Otherwise $M$ doesn't exist. Notice that, if $R$ and $C$ forms a match, there could exist more than one matrix having $R$ and $C$ as sum vectors.

The equation $(1)$ seems to have been originally introduced by Arjen Stolk in the thesis given above, and it's just a direct way of getting $C^\*$ without having to construct $M^\*$.

Equation $(1)$ simply means, counting, per column $j$, how many rows of $M$ have same or more $1$s than the column index itself (how many $r\_i\geq j$). Notice that $C^\*$ is already sorted, otherwise majorization woudn't be defined (actually, before proving that $C\prec C^\*$ is all you need, Ryser first prove, because of the way $M^\*$ is defined, that $C^\*$ is already sorted in a non-decreasing fashion).

# Answer
> 6 votes
This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis *Discrete tomography for integer-valued functions* in Chapter 1. It gives a simple greedy algorithm for solving this problem:

> While the proof of theorem (1.1.13) is somewhat involved, the reconstruction algorithm that comes out of it is actually quite easy. It proceeds one column at a time, starting with a column whose sum is the highest and working in order down to the lowest column sum. In each column, we place the 1’s in those rows where with the largest number of 1-positions left, that is, such that the row sum minus the number of 1’s already filled in is the largest.

---
Tags: combinatorics, matrices
---


# Question
Title: Solve Recurrence for $T(n) = 7T(n/7) + n$
I'm trying to solve the recurrence for $T(n) = 7T(n/7) + n$. I know using Master Theorem it's $O(n\log\_7n)$, but I want to solve it by substitution method.

At level $i$, I get: $7^i T(n/7^i) + (n+7n+7^2n+ \cdots + 7^i n)$ By setting $i = \log\_7n$, the above becomes: $$7^{\log\_7n}\cdot T(1) + (n + 7n + 7^2n + \cdots + 7^{\log\_7n}n$$

Since $7^{\log\_7n} = n$, the above finally becomes $$n+ (n+7n+(7^2)n+ \cdots + n\cdot n)$$ This solves to $O(n^2)$ to me since $n\cdot n$ dominates, not $O(n\log\_7n)$, any idea what's wrong?

# Answer
Here is what I get: \begin{align} T(n) &= n + 7T(n/7) \\ &= n + 7(n/7) + 7^2 T(n/7^2) \\ &= n + 7(n/7) + 7^2(n/7^2) + 7^3 T(n/7^3) \end{align} and so on. Each of the summands equals $n$, and there are $O(\log n)$ of them.
> 1 votes

---
Tags: recurrence-relation, recursion, master-theorem
---


# Question
Title: Can you say anything interesting about a language knowing only that it is prefix-closed?
Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w \in L$, and $u$ is any prefix of $w$, then $u \in L$).

Knowing only this, can you give any positive or negative decidability or complexity results about $L$?

Thanks! :)

# Answer
If $P$ and $Q$ are languages closed under prefix, then $P\cup Q$, $P\cap Q$, $P \cdot Q$, $P/Q$ are also closed under prefix. Also you can think of such a language $L$ as a directed tree. Define the graph/tree $G = (V,E)$ where $V = L$ and $$E = \\{(\mathit{prefix}(w),w) \mid w\in L \\}$$ (the words are the nodes and the parent of every word is its prefix). Note that I assume that $\mathit{prefix}(x) = \varepsilon$ for all $x\in\Sigma$, meaning that the prefix of a single symbol is the empty word. Thus the root of the tree constructed above is the empty word. The constructed tree can be easily transformed to a DFA recognizing the language (I think you can see how).
> 1 votes

# Answer
Let $L$ be an arbitrary language. Since the set of all words is countable, we can think of $L$ as a subset of $\mathbb{N}$. Let $\ell\_i = 1$ if $i \in L$, and $\ell\_i = 0$ if $i \notin L$. Define the language $L'$ of all words of the form $\ell\_1 \ldots \ell\_n$. The language $L'$ inherits many properties of $L$, and is prefix-closed.
> 0 votes

---
Tags: complexity-theory, formal-languages, computability
---


# Question
Title: What is "rank" in a binary search tree and how can it be useful?
I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me.

**What I have looked into:**
From what I have read, a ranked binary search tree is a tree where each node has a variable "rank" attached to it.

In the question here, someone states that in order to determine the rank of a node in a binary search tree you can do the following:

> Start the rank at zero. As the binary search proceeds down from the root, sum up the sizes of all the left subtrees that the search skips by. Also include the nodes along the path less than the searched item. These are just the parents of right children on the search path.

**Questions:**
The rank seems like it is just a number that reflects how many nodes it takes (plus one for the root) to get to a particular node in a tree. Is that right? It didn't seem right to me only because that seems like that would just make the rank of a node the same as the depth of a node.

Also, what is the difference between "weight" and "rank"? If a node in a particular binary search tree has a weight attached to it, is that just a random value assigned to it by the user/developer?

Lastly, what is the point of having a rank? My first thought is that it can be used to indicate priorities. However, in that case, why wouldn't the developer just use weights?

**Other things:**
I also took a look at the site here. It explains how to calculate rank, but I'm still not convinced I understand the concept yet.

Thanks for any help.

# Answer
> 12 votes
According to this book (Chapter 3.2), a node in a BST has rank $k$ if precisely $k$ other keys in the BST are smaller. So, if you order all the BST nodes according to their keys, then each node with rank $k$ will take $k$-th place.

# Answer
> 2 votes
The Rank of node in tree tells us how many nodes in the tree have key values less than that node in the Tree. So a node of Rank 5 will have 4 other nodes in the tree with Key value less than that specific Node. This can be used in algorithms to find '$K$'th smallest item in a tree and will run in $\log(n)$ ($O(1)$ if you already maintain the sizes) running time.

The size of a node : is the sum of all nodes in Left subTree + sum of all nodes in right SubTree + 1 (for the given node) -- There will be slight complications if you the node is on the rightSubtree of its parent. In this case, choose rank as Rank of parent + size of leftSubTree.

So if I want to find the rank of a node, I will need to find the "size" of leftSubTree (as all of them will be smaller than current node) + 1.

```
int rank(int key, Node node) {
        if (node == null) return 0;
        if      (key < node.key) return rank(key, node.left);
        else if (key > node.key) return 1 + size(node.left) + rank(key, node.right);
        else              return size(node.left);
    }

```

It is not same as depth. Depth of a Node is the number of "levels" between the root of the tree and that node. This will be equal to height of root - height of Node.

For further reading, check Algorithms 4th Edition By Robert Sedgewick and Kevin Wayne.

# Answer
> 1 votes
I think it depends on if you are doing rank union by size or by height. The rank of a node using rank union by size may indicate how many nodes are in the subtree of that node. The rank of a node using rank union by height would indicate how many edges are in the path from that node to the furthest leaf in that node's subtree.

# Answer
> 1 votes
Adding to the answer by HEKTO above, to calculate the rank in a BST with unique elements,

the rank of a left child = rank of the parent - 1 - number of elements in its right subtree

and,

the rank of a right child = rank of the parent + 1 + number of elements in its left subtree.

It can be used to find any general $i^{th}$ order statistic in the BST in O(h) time, i.e. O(log n) time if the tree is balanced. So it is useful to find the median of the elements or ith largest/smallest element among the elements.

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


# Question
Title: Context-free grammar for language with unequal numbers of a and b
I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e.

$$\\{u \in \\{a, b\\}^\* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \\},$$

but it seems that I keep getting specific cases instead of the general case.

Here are some that I have tried:

(S being the start Variable)

```
S -> A | a | b
A -> aV | bT
V -> aV | bL
L -> aV
T -> bT | aM
M -> aT

```

This one's problem is that you can't create 2 of the same string if it's the lesser amount of alphabet.

So I've tried

```
S-> A | B
A -> aV | a
V -> aV | aVb | bVa
B -> bT | b
T -> bT | aTb | bTa

```

This one also has problem because if you have a you need to have b on the opposite end.

Additionally, I know this is one of the huge problem in my process is that you start with 'a' or 'b' and use that as a flag for if there is more 'a' or there is more 'b'...

I've been trying to think the way where you can input an alphabet (i.e `S -> aV | bV`) so that I can start with any variable and I use cases or condition to go to different variable, but I end up with infinite variable situation.

# Answer
> 9 votes
Here are some hints:

1. Break the language into two parts: $L\_a = \\{ w : \\#\_a(w) \> \\#\_b(w) \\}$ and $L\_b = \\{ w : \\#\_a(w) \< \\#\_b(w) \\}$. Below we concentrate on $L\_a$.
2. Figure out a grammar for the language $L\_= = \\{ w : \\#\_a(w) = \\#\_b(w) \\}$. Here the idea is that $L\_= = (aL\_=b + bL\_=a)^\*$.
3. Use the identity $L\_a = L\_=(aL\_=)^+$ to construct a grammar for $L\_a$.

# Answer
> 5 votes
The unequal number of $a$'s and $b$'s have {equal number of $a$'s and $b$'s} with {{extra $a$'s } or {extra $b$'s}}

Extra $a$'s or extra $b$'s can be

* at the beginning
* at the end
* in between (ANY WHERE) and any number of times

Let $P$ derive strings with extra $a$'s

Let $Q$ derive strings with extra $b$'s

Let $X$ derive equal number of $a$'s and $b$'s

Let $A$ derive only $a$'s

Let $B$ derive only $b$'s

And $S$ derives the final language

\begin{align} &S\rightarrow P\mid Q\\ &P\rightarrow XAX\mid PP\\ &Q\rightarrow XBX\mid QQ\\ &X\rightarrow aXb\mid bXa\mid XX\mid \varepsilon\\ &A\rightarrow aA\mid a\\ &B\rightarrow bB\mid b \end{align}

# Answer
> 4 votes
Remember that the following approach is also feasible:

1. Come up with a pushdown-automaton for the language.
2. Use the standard construction to get a grammar.

That's not a very insightful process (in terms of learning how to construct grammars) but it works.

# Answer
> -5 votes
I know this is like a very old post, (and way past your homework deadlines), but here's the solution:

$\qquad\begin{align\*} L &\to L\_a \mid L\_b \\ L\_a &\to L\_=aL\_a \mid L\_=aL\_= \\ L\_b &\to L\_=bL\_b \mid L\_=bL\_= \\ L\_= &\to aL\_=bL\_= \mid bL\_=aL\_= \mid \varepsilon \end{align\*}$

# Answer
> -5 votes
$$ \begin{align\*} &S → U \mid V \\ &U → TaU \mid TaT \\ &V → TbV \mid TbT \\ &T → aTbT \mid bTaT \mid \epsilon \end{align\*} $$

I hope it will predict a context-free grammar for the language consisting of all strings over $\\{a,b\\}$ containing an unequal number of a's and b's!

# Answer
> -6 votes
$$ \begin{align\*} &S\to aB \mid bA \\ &A\to b \mid bS \mid aBB \mid \epsilon \\ &B\to a \mid aS \mid bAA \mid \epsilon \end{align\*} $$

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