# Question
Title: How to find simple polygons in a complex polygon created by two lines
Given the image attached, I am looking for a way/strategy/pseudocode to iteratively find each polygon created either by two blue-dotted line segments, a blue-dotted line segment and an intersection, or two intersections.

I have an ordered list of line segments for each line, an ordered list of blue-dotted line segments, and an ordered list of intersections. Segments are stored as a list of two (x,y) tuples, intersections are stored as one (x,y) tuple. By ordered in this case I mean the shape has been processed from left to right, so everything is stored as if you were to follow the paths in an S shape from the bottom left to the top right.

At the moment I am processing each section of the polygon based on what is contained within two blue line segments, although I don't think this is a good way of going about it. I feel as though any attempt at an algorithm so far has overfit to this specific example. I'm fairly new to computational geometry so any help is appreciated.

edit 1: I am looking for a way to identify simple polygons (shapes with no holes and no self-intersections). For example beginning in the bottom left, there is a triangle created by the blue\_line\_seg\[0\], blue\_line\_seg\[1\] and part of the first line segment (since in this case we are following the green and red paths from left to right). This polygon could be stored (for the moment) as any arrangement of the points associated with those two blue line segments and the endpoint of the first green line segment ((3,6), (5.3,5.7), (5,3)). following that there is a 4-sided polygon created using blue\_line\_seg\[1\], blue\_line\_seg\[2\], part of the first line segment on the red path, and the entire first segment of the green path. However, between blue\_line\_seg\[2\] and blue\_line\_seg\[3\] we encounter an intersection point at (13.5,5.5), which would close off the third polygon. That polygon would also contain the last endpoint of the first red line segment. This is where it gets confusing: i'm trying to find a way to process each simple polygon without using too many heuristics / overfitting to this specific example.

# Answer
Please take a look at the DCEL data structure, which is normally used for representation and processing of polygonal subdivisions of the plane. This data structure usually stores three kinds of geometric objects - *vertices*, *edges* and *faces*. Relationships between these objects are also stored in the DCEL - for example, for each vertex you can find all the edges, incident to this vertex. Simple polygons you are looking for will be represented by finite DCEL **faces**.

You'll need to convert your ordered lists of segments and intersections to the DCEL. In order to do that you need to **split** all your red and green segments into edges by endpoints of blue segments and intersection points. All edges endpoints will become vertices - and you'll need to store relationships between edges and vertices. Each edge is represented by a pair of directed half-edges, and for each half-edge you'll be able to find the *next* half-edge with the same face on its left side. So, each face will be bounded by a loop of directed half-edges.

This structure has been implemented many times already, and one of best implementations is the CGAL 2D Arrangements \- it covers degenerate cases as well, which is important in Computational Geometry.
> 1 votes

# Answer
It is an easy matter to generate a single (crossed) polygon from the red polyline and the blue segments. Now for a relatively simple solution, you can

* detect all edge/edge intersection points; this can be done by brute-force or more efficiently (Bentley-Ottman algorithm);
* label the intersections with the index of the initial point of the edge plus the relative distance to the intersection (a fraction in $\[0,1)$); every intersection has in fact two labels;
* sort the intersections by increasing label, but keep a link between the two labels relating to the same intersection;
* you now have a list of "polygonal arcs" with known endpoints - and a way to enumerate the intermediate vertices; and the endpoints have links that form closed loops.

The labeling with a fraction is required when there are several intersections along the same edge; alternatively, you can sort the intersections along the edge and number accordingly.

This description assumes the points in general position (i.e. no vertex on an edge, no overlapping edges).

In the picture, the initial arcs are 5.2, 0, 1, 2, 2.4; 2.4, 2.6; 2.6, 3, 4, 4.8; 4.8, 5, 2.4. Then after forming the loops, 5.2/2.4, 0, 1, 2, 2.4/5.2; 2.6/4.8, 5, 2.4/5.2, 4.8/2.6; 2.6/4.8, 3, 4, 2.6/4.8.
> 0 votes

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


# Question
Title: Are all $\mathbf{P}$ languages $\mathbf{P}$-complete with respect to polynomial-time reduction?
Question: Is language $L \in \mathbf{P}$ also $\mathbf{P}$-complete with respect to polynomial-time reduction?

My thoughts: Given a language $L \in \mathbf{P}$, we want to show that for any other language $L' \in \mathbf{P}: L' \leq\_p L$. To do this, given any input $w' \in \Sigma^\*$, we can check in polynomial time if $w' \in L'$. If:

* $w' \in L'$: construct a word $w \in L$.
* $w' \notin L'$: construct a word $w \notin L$.

This construction would satisfy the existence of $f\colon \Sigma^\* \to \Sigma^\*, w' \in L' \iff f(w') \in L$.

This is where I stuck: Given a language $L$, how can we find a word $w \in L$ or a word $w \notin L$.

Addendum: I think I understood the problem. Since $L' \leq\_p L$ only requires existence of $f\colon \Sigma^\* \to \Sigma^\*$, I don't need construct $f$.

# Answer
I think you almost got it right, here is what you are missing: if $L$ is not trivial (i.e, not empty and not $\Sigma^\*$) then there are words $w\_1\in L,w\_2\notin L$. You can use them to construct $f$.
> 1 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Why is the Java HashMap load factor 0.75?
I can't understand why the Java HashMap load factor is 0.75. If I understand well, the formula for the load factor is n/m, where n is the number of key and m is the number of position in the hash table.

Since HashMap utilize bucket (i.e., a linked list) to store the value it is possible to have a load factor \> 1 without problem, so it's not clear for me why the load factor is set to 0.75.

# Answer
I don't know the answer, but I can walk you through what might be going through the mind of someone designing such a data structure.

Assuming a "good" hash function, and that $n$ is large enough, then for a given load factor $\lambda$, the probability that a bucket contains exactly $k$ elements in it is given by the Poisson distribution:

$$P(k,\lambda) = \frac{e^{-\lambda} \lambda^k}{k!}$$

So, for example, if $\lambda=1$, then the proportion of buckets containing exactly one element (i.e. those for which no chaining is needed; I'm not sure exactly how Java's HashMap actually implements it) is:

$$P(1,1) = \frac{1}{e} \approx 36.8\\%$$

For $\lambda = 0.75$, it is:

$$P(1,0.75) \approx 35.4\\%$$

Not much difference. However, this is measured per bucket, not per item. The proportion of successful queries that do not require traversing a chain (and is therefore loop-free) is $P(1,\lambda)/\lambda$. For $\lambda=1$, that is $36.8\\%$, but for $\lambda=0.75$, that is $47.2\\%$.

So by reducing $\lambda$ from $1$ to $0.75$, the proportion of successful queries that do not need to traverse a chain increases from a little over a third to a little under a half.

But it might use more memory. How much more?

I am going to assume some kind of optimised representation where the hash table is an array of $n$ words, an empty bucket is represented as a null pointer, a bucket with a single element is represented as a pointer to the object, and a bucket with more than one element is represented as a pointer to a linked list. I will assume that a linked list node is 3 words in size: the object header (which Java semantics requires), a pointer to the item, and a "next" pointer.

So you can think of the overhead cost of an empty bucket as being $1$ word, a bucket with one item in it being $1$ word, and a bucket with $k\>1$ items in it being $1+3k$ words.

I'll let you work out the details for yourself, by if $\lambda=1$, I calculate the overhead to be about $2.896$ words per stored item, and for $\lambda=0.75$, it's about $2.916$ words per stored item. That's less than $0.7\\%$ difference in memory overhead.

(Exercise: Under these assumptions, for what value of $\lambda$ is the memory overhead minimised? I will say that it's greater than $\frac{1}{2}$ and less than $1$. It's not $0.75$; if it was, that would be part of my answer!)

So it does seem that under these assumptions, you would get significantly more efficient lookup and only pay a tiny increase in memory overhead. And that's just one of many tradeoffs that you could look at.

My guess is that the Java library implementers performed some back-of-the-envelope calculations similar to this, and some experiments to be certain, and found that this was acceptable.
> 18 votes

# Answer
Using linked-list buckets is not the only way to resolve collisions. There is another technique: *rehashing*. Basically, when a collision occurs, an attempt is made to find a different, unoccupied slot. One way is *linear probing* \- basically, the index of the slot is incremented by a fixed constant (modulo the table size) until an open slot is found. A better way is *quadratic probing* \- basically, a counter 'i' is incremented, and the i-squared'th slot (modulo the table size) is checked, until an open slot is found. These tactics are very effective, at least until the table fills up. The load factor determines when the table has to be enlarged so that rehashing will continue to be effective. Possibly some Java hash class uses this technique.
> 1 votes

---
Tags: data-structures, hash-tables, java
---


title: Evaluating $T(n)=2^n+4T(\frac{n}{2})$

text:
# Question
Title: Evaluating $T(n)=2^n+4T(\frac{n}{2})$
$$T(n)=2^n+4T(\frac{n}{2})$$

I have started substitution for:

$$T(\frac{n}{2})=2^{\frac{n}{2}}+4T(\frac{n}{4})$$

$$T(\frac{n}{4})=2^{\frac{n}{4}}+4T(\frac{n}{8})$$

$$...$$

$$T(\frac{n}{4})=2^n+4\[2^{\frac{n}{2}}+4(2^{\frac{n}{4}}+4T(\frac{n}{8}))\]=2^n+4\cdot 2^{\frac{n}{2}}+4^2\cdot 2^{\frac{n}{4}}+4^3T(\frac{n}{8})$$

So in general:

$$T(\frac{n}{2^k})=2^n+4\cdot 2^{\frac{n}{2}}+...+4^k\cdot 2^{\frac{n}{2^k}}+4^{k+1}T(\frac{n}{2^{k+1}})$$

How should I proceed from here?

# Answer
> 1 votes
Sometimes it's more easy to take $n=2^k$ and write substitution in following way: $$\begin{array}{l}T(n)=2^2 T\left(\frac{n}{2} \right)+2^n=2^2\left\[2^2T\left(\dfrac{n}{2^2} \right) +2^{\frac{n}{2}}\right\]+2^n=\\ =2^{2 \cdot 2}T\left(\dfrac{n}{2^2} \right)+2^{2+\frac{n}{2}}+2^n=2^{2 \cdot 2}\left\[2^2T\left(\dfrac{n}{2^{3}} \right) +2^{\frac{n}{4}}\right\]+2^{2+\frac{n}{2}}+2^n=\\ =2^{2 \cdot 3}T\left(\dfrac{n}{2^{3}} \right) + 2^{4+\frac{n}{4}}+2^{2+\frac{n}{2}}+2^n=\\ =\cdots =\\ =2^{2 \cdot k}T\left(\dfrac{n}{2^{k}} \right) + 2^{2(k-1)+\frac{n}{2^{k-1}}}+\cdots+2^{2+\frac{n}{2}}+2^n = \\ =n^2T(1)+ 2^{2(k-1)+\frac{n}{2^{k-1}}}+\cdots+2^{2+\frac{n}{2}}+2^n \end{array} $$ rough estimation of $T(n)$ is $O(2^n)$.

# Answer
> 1 votes
Let $T(n)=T(2^m)=:P(m)$. The recurrence becomes

$$P(m)=2^{2^m}+4P(m-1).$$

Now we try to solve by the method of variation of the constant, noticing that a solution of the homogeneous equation is $P(m)=4^m$.

$$C(m)4^m=2^{2^m}+C(m-1)4^m$$ or

$$C(m)=C(m-1)+2^{2^m-2m}.$$

Then

$$C(m)=C(0)+\sum\_{k=1}^m2^{2^k-2m},$$ $$P(m)=C(0)4^m+\sum\_{k=1}^m2^{2^k},$$ and $$T(n)=C(0)n^2+\sum\_{k=1}^{\lg n}2^{2^k}=C(0)n^2+4+16+256+\cdots 2^n.$$

For sufficiently large $n$, the sum is very close to its last term, and

$$T(n)\approx 2^n.$$

---
Tags: recurrence-relation
---


# Question
Title: Solve the recurrence equation $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$
I tried to solve the recurrence $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$ using the Master Theorem. I tried the following way:

---

$n = 2^k$

$2^{\frac{2}{k}}\cdot T\left(2^k\right)+\log2^k$

$2^{\frac{2}{k}}\cdot T\left(2^k\right)+k$

At that point i'm stuck and not sure how to handle the $2^{\frac{2}{k}}$ before the $T\left(2^k\right)$. I would also like which more tools are open to use at this problem.

# Answer
> 1 votes
For $n \> 0$ we have

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

calling $R(n) = \frac{T(n)}{n}$ we follow with

$$ R(n) = R(\sqrt{n})+c\frac{\ln n}{n} $$

but now

$$ R\left(2^{\log\_2 n}\right) = R\left(2^{\log\_2 \sqrt{n}}\right)+c\frac{\ln n}{n} $$

Calling now $\mathcal{R}(\cdot) = R\left(2^{(\cdot)}\right)$ and $z = \log\_2 n$ we follow with

$$ \mathcal{R}(z) = \mathcal{R}\left(\frac z2\right)+c\_1 z 2^{-z} $$

now using again a transformation with $\mathbb{R}(\cdot) = \mathcal{R}\left(2^{(\cdot)}\right)$ and $\mu = \log\_2 z$ we follow with the recurrence

$$ \mathbb{R}(\mu) = \mathbb{R}(\mu-1) + c\_1 2^{\mu}2^{-2^{\mu}} $$

with solution

$$ \mathbb{R}(\mu) = c\_0 + 2c\_1\sum\_{k=0}^{u-1}2^{-2^{k+1}+k} $$

now going backwards with $\mu = \log\_2 z$ and $z = \log\_2 n$ we arrive at

$$ T(n) = n\left(c\_0+2c\_1\sum\_{k=0}^{\log\_2(\log\_2 n)-1}2^{-2^{k+1}+k}\right) $$

and certainly

$$ T(n) \ge n c\_0 + c\_1\log\_2 n $$

# Answer
> 1 votes
Using the nice trick of @Cesareo, and setting $n=2^{2^m}$,

$$\frac{T(2^{2^m})}{2^{2^m}}=\frac{T\left(\sqrt{2^{2^m}}\right)}{\sqrt{2^{2^m}}}+\frac{c\log2^{2^m}}{2^{2^m}}$$ is of the form

$$S(m)=S(m-1)+c'2^{m-2^m}.$$

Then by induction,

$$S(m)=S\_0+c'\sum\_{k=1}^m2^{k-2^k},$$

which is

$$\frac{T(n)}{n}=S\_0+c'\sum\_{k=1}^{\lg\lg n}2^{k-2^k}.$$

The terms of the sum are

$$2^{-1},2^{-2},2^{-5},2^{-14},2^{-20},\cdots$$ so the sum converges very quickly and is bounded above by $0.7815$.

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


# Question
Title: How did the following derivation of the final weight of a weight-balanced search tree node after rotation to make it balanced occur?
I was reading section 3.2 of *Advanced Data Structures* by Peter Brass (which is about weight-balanced search trees) for self-study. I got stuck on a proof about rebalancing properties.

$\alpha$ and $\epsilon$ are parameters, where $$\epsilon \le \alpha^2 - 2\alpha + \frac{1}{2}$$

The weight of a node is recursively defined:

If node `n` is a leaf (`n.left == NULL` and `n.right == NULL`), then `n->weight = 1`. Otherwise, `n.weight` is the sum of the weight of the left and right subtree.

The node `n` is $\alpha$-weight-balanced if $$n.left.weight \ge \alpha n.weight$$ and $$n.right.weight \ge \alpha n.weight$$

In one case, they start with $n^{old}.left.left.weight \> (\alpha + \epsilon)w$ and perform a right ration around $n^{old}$. By this:
$n^{old}.left.left$ becomes $n^{new}.left$
$n^{old}.left.right$ becomes $n^{new}.right.left$.
$n^{old}.right$ becomes $n^{new}.right.right$
Because $n^{old}.left$ was balanced, with $n^{old}.left.weight = (1 - \alpha)w + \delta$, we have $$n^{new}.right.left.weight \in \[\alpha(1 - \alpha) w + \alpha\ \delta), (1 - 2 \alpha - \epsilon) w + \delta \]$$

and $$n^{new}.right.right.weight = \alpha w - \delta$$.

I understand why they performed the rotations they did, and I more or less see where the original weights came from (I think), but I'm thoroughly confused as to how the final weights follow from the original weights and the operations they perform. Can someone explain this to me?

# Answer
> 1 votes
Here we are checking the case $2.1$,

The assumptions are

* $n^{old}.weight=w$,
* $n^{old}.right.weight \< \alpha\\,w,$
* $n^{old}.left.left.weight \> (\alpha + \epsilon)w$, and
* $n^{old}.left$ is balanced.

Let $n^{orig}$ be original node $n$, i.e., before the insertion or deletion of a node. Since $n^{orig}$ is weight-balanced, $n^{orig}.right.weight \> \alpha\\, n^{orig}.weight$. The insertion or deletion of a node can only change the weight of $n$ by $1$, i.e.,

* either $n^{old}.right.weight=n^{orig}.right.weight+1$ and $n^{old}.weight=n^{orig}.weight+1$
* or $n^{old}.right.weight=n^{orig}.right.weight-1$ and $n^{old}.weight=n^{orig}.weight-1$.

The above together with $n^{old}.right.weight \< \alpha\\,n^{old}.weight$ implies that $n^{old}.weight=n^{orig}.weight-1$ and $$n^{old}.right.weight = \alpha\\,n^{old}.right - \delta=\alpha w-\delta$$ for some $\delta\in \]0,1\]$.

We have $$n^{old}.left.weight=n^{old}.weight - n^{old}.right.weight =(1 - \alpha)w + \delta.$$ Because $n^{old}.left$ is balanced, $$n^{old}.left.right.weight \> \alpha\\,n^{old}.left.weight=\alpha((1 - \alpha)w + \delta)=\alpha(1 - \alpha)w + \alpha\delta.$$ On the other hand, we have $$\begin{aligned} n^{old}.left.right.weight &= n^{old}.left.weight - n^{old}.left.left.weight\\ &\< (1 - \alpha)w + \delta - ((\alpha + \epsilon)w)\\ &=(1 - 2 \alpha - \epsilon) w + \delta \end{aligned}$$ Hence, $$n^{old}.left.right.weight\in \[\alpha(1 - \alpha)w + \alpha\delta, (1 - 2 \alpha - \epsilon) w + \delta\].$$

---
Tags: data-structures, correctness-proof, search-trees, balanced-search-trees
---


title: What is conditional probability?

text:
# Question
Title: What is conditional probability?
I've been looking online and through a couple youtube videos but I cannot understand how exactly conditional entropy is being applied here. From what I'm understanding is that p(Y=1 | X=1) is 0 because of (1,1) on this table being 0 at that point, but then p(y=2 | X=1) = 1, which is where I'm getting lost because I thought that would equal 3/4? Basically I'm lost on what p(x|y) means exactly, could I get an explanation using this particular example?

# Answer
Here is one definition of conditional probability:

> $\Pr\[A|B\]$ is the probability that $A$ happens given that $B$ happens.

Another definition just gives a formula:

> $$ \Pr\[A|B\] = \frac{\Pr\[A \cap B\]}{\Pr\[B\]}. $$

Let's see why $\Pr\[Y = 2|X = 1\] = 1$. If $X = 1$ then it is always the case that $Y = 2$, and so conditioned on $X = 1$, the probability that $Y = 2$ is $1$.

We can also see this via the formula: $$ \Pr\[Y = 2|X = 1\] = \frac{\Pr\[Y = 2, X = 1\]}{\Pr\[X = 1\]} = \frac{3/4}{0 + 3/4} = 1. $$ Here $\Pr\[A,B\]$ is a commonly used notation for $\Pr\[A \cap B\]$, which is the probability that both $A$ and $B$ happen at the same time.
> 1 votes

---
Tags: probability-theory
---


# Question
Title: Will Big Theta not apply when $f(n)$ and $g(n)$ are of different order?
I'm currently taking my algorithms class, and I learnt that Big theta is defined as follows:

> $f(n) = \Theta(g(n))$ if there exist constants $c\_1, c\_2, n\_0 \> 0$ such that $0 ≤ c\_1g(n) ≤ f(n) ≤ c\_2g(n)$ for all $n ≥ n\_0$.

So if our $f(n)$ and $g(n)$ are of the same order, say $n$ and $2n$, we can easily find a constant $c$ and an $n\_0$, such that $n$ lies between $c\_1(2n)$ and $c\_2(2n)$ for all $n ≥ n\_0$.

Suppose in contrast that our $f(n)$ and $g(n)$ are of different order, say $f(n)$ is $O(g(n))$ where $f(n) = n$ and $g(n) = n^2$. So technically, there will exist constants $c\_1$ and $c\_2$ such that $c\_1(n^2)$ is less than $n$, and $c\_2(n^2)$ is more than $n$. However, because $n^2$ is of a higher order than $n$, as $n$ increases, $n^2$ will surpass n eventually regardless of its constant, and thus the definition of $\Theta(n)$ where for all $n \ge n\_0$ will never hold if our $g(n)$ and $f(n)$ eventually intersect each other (which will happen if they have different orders?).

Is this always the case? Or am I being too narrow-minded in thinking like this.

# Answer
> 1 votes
Because it's very important to use correct conditions for variables, let me firstly (for non-negative case) formally write definition for $\Theta$:

$$\Theta(g)=\Big\\{f\colon \exists C\_1\>0,\exists C\_2\>0, \exists N\in\mathbb{N}, \forall n \gt N, C\_1 g(n)\leqslant f(n) \leqslant C\_2 g(n)\Big\\}$$

Now to obtain $f\notin \Theta(g)$ we need formal negation of definition i.e. $$\forall C\_1\>0,\forall C\_2\>0, \forall N\in\mathbb{N}, \exists n \gt N,f(n)\lt C\_1 g(n) \lor f(n) \gt C\_2 g(n)$$

As you see in negation we **shouldn't find constants** $C\_1, C\_2$, but we work with them as with **arbitrary variables**. Now we are searching for $n$.

In example with $n^2 \notin \Theta(n)$ we can use, that for $\forall C\gt 0, \exists n\in\mathbb{N}$ for which we can write $n^2 \gt Cn$ i.e. $n \gt C$. As such, for example, we can take $n=\lfloor C \rfloor+1$. And, as last detail, if we want to fulfill also condition for $N$, then we can choose, for example, $n=\max(\lfloor C \rfloor+1, N+1)$. As answer to your question in title, we can see, that there is no problem with using Theta notation for different orders: additionally to written we have also $n \notin \Theta(n^2)$.

As to your intuitive considerations, then, at one glance, they seems correct, but it is difficult to mathematically agree or contradict them precisely, since these are not formal statements. Therefore, I prefer such proofs as I have given above.

# Answer
> 1 votes
$f(n)=O(g(n))$ alone does not imply $f(n)=\Theta(g(n))$. \[$3n-2\ne\Theta(n^2)$\]

$f(n)=\Omega(g(n))$ alone does not imply $f(n)=\Theta(g(n))$. \[$3n-2\ne\Theta(\sqrt n)$\]

$f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$ together imply $f(n)=\Theta(g(n))$. \[$3n-2=\Theta(n)$\]

# Answer
> 0 votes
Big Theta is one possible formalization of the concept of two functions being of the same order.

> There will exist constants $c\_1$ and $c\_2$ such that $c\_1(n^2)$ is less than $n$, and $c\_2(n^2)$ is more than $n$.

In fact, such a constant $c\_1 \> 0$ does not exist: if $n \ge 1/c\_1$ then $c\_1 n^2 \ge n$.

This shows that $n^2$ is not $O(n)$, and in particular, $n^2$ and $n$ don't have the same order.

In contrast, the other inequality does exist, showing that $n^2 = \Omega(n)$.

You can even show a stronger inequality: $n^2 = \omega(n)$ (look it up). This is the same as $$ \lim\_{n\to\infty} \frac{n^2}{n} = \infty. $$ Hence we can say that $n^2$ has a large order than $n$.

You can show that $f(n)$ has a larger order than $g(n)$, in the sense that $f(n) = \omega(g(n))$, then the two functions don't have the same order, that is, it is *not* the case that $f(n) = \Theta(g(n))$.

---
Tags: asymptotics
---


# Question
Title: Regular expression of binary strings not containing $1011$ or $1101$ as substring
I tried to solve by explicitly writing strings of length $2$, $3$ and $4$ (other than $1011$ and $1101$), but it creates a lengthy regular expression. Can someone suggests underlying pattern that helps in writing concise regular expression ?

# Answer
> 1 votes
Denote your language by $L$. The words $w$ in the list below satisfy the following property: $x \in L$ iff $wx \in L$: $$ 0,(10)^+0, 11^+00 $$ If a word doesn't start with any of these, then it must be of one of the following forms, where $z$ is some arbitrary word: $$ \epsilon, (10)^\*1,(10)^+,(10)^+11z,11^+,11^+0,11^+01z $$ The two cases involving $z$ are not in $L$. We conclude that an unambiguous regular expression for $L$ is $$ (0+(10)^+0+11^+00)^\*(\epsilon + (10)^\*1 + (10)^+ + 11^+ + 11^+0) $$ or $$ ((10)^\*0+11^+00)^\*((10)^\*(\epsilon+1)+ 11^+(\epsilon+0)) $$

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


# Question
Title: Algorithm for Getting Largest Connected Component From List of Touching Pairs
I have a program which finds the touching pairs of a given value in a binary image. For example, consider the below image:

```
[
  [1, 0, 0, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 1, 1, 0, 1],
  [1, 1, 0, 0, 0]
]

```

When the algorithm is run with a value of 0, it finds the following pairs:

```
[(1, 2), (22, 23), (23, 24), (18, 23)]

```

Is there an algorithm to find the largest connected components from these values? So for this example, it should return 4.

I know of some solutions which treat the matrix as a graph and run a DFS on it, but I'm looking for a solution using the already calculated connected pairs.

# Answer
> 0 votes
*I will elaborate the answer of @Stef from the comment.*

From what is given in the problem, it appears that you already have an existing algorithm to find the edges of the connected components. All you have to do now is build the components and determine the largest. As noted in the comment you can use union-find for this.

In union-find, each element in your pair will be treated as a set. We assume here that in addition to the 3 union-find operations, we can also perform a `size()` operation to determine the size of each set. Now, for each element of each pair, perform `make-set()` and then perform a `union()`. A union of a pair is interpreted as combing the elements into the same component. Following a union, update the set that currently has the largest size if necessary. After performing all unions, you will now have the largest set, which is also the largest component.

# Answer
> 1 votes
Create a graph only from nodes that appear in the output, and add an edge for each tuple in the output.

Then find the connected components in this graph using DFS + union find (or your other favorite method)

---
Tags: haskell, connected-components
---


# Question
Title: Array vs Linked List Implementation of Stacks (in JS)
Let's say I want to make a Stack class in JavaScript. The class will have a `push()` and a `pop()` method. I have two options for the underlying data structure I can use: Linked Lists or Arrays.

Using a Linked List I will have O(1) average and worst time complexities.

Using an Array I will have O(1) average and O(n) worst time complexities, since `Array.push()` and `Array.pop()` have O(1) amortized time complexities.

While the Array implementation will occasionally encounter an O(n) operation, it will likely be much faster than the Linked List implementation for every other operation as Arrays are far more optimized than Linked Lists.

Is there any other argument to using a Linked List-based implementation of a Stack other than what I have covered?

I can see why Linked Lists are better for Queues (since `Array.shift()` and `Array.unshift()` are O(n) operations), but not for Stacks.

Thanks!

# Answer
> -1 votes
If you are only considering the implementations, then yes what you have mentioned is correct. However when you consider the use cases, then you might want to think further. For example if your use case has very less push/pop operations then arrays are well suited else you can use linked list. If your use case requires frequent reading and using of indexes then array is the one to go. These might not seem the operations of a stack but sometimes you may need to implement such a data structure which could behave like a stack while providing other operations too.

What you are comparing is actually a data structure vs a concept. A linked list can be implemented using an array too and you can have the best of both. Then you can extend the idea to implement a stack.

This is just some food for thought since you asked for some insights. You can try out different implementations to see what works out best.

---
Tags: time-complexity, arrays, stacks, linked-lists
---


# Question
Title: Intersection of Infinite Regular Language with CFL
Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be finite or not ?

# Answer
It can be both. Infinite regular language intersection with $Σ^\*$ will be infinite and intersection with $Φ$ will be a finite set. Both $Σ^\*$ & $Φ$ are regular languages, and therefore are context free as well.
> 0 votes

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


title: Recurrence relation with O(loglogn)

text:
# Question
Title: Recurrence relation with O(loglogn)
I am trying to solve a recurrence relationship as follows:

T(n)=T(n^1/2)+O(loglogn)

I can solve the T(n^1/2) part quite easily, but I am completely lost as to what to do with an O(loglogn). I cant use the masters theorem since loglogn cannot be expressed in the form of n^x and using trees, I don't believe I can just drop the O. Any guidance would be very helpful!

Thank you!

Edit: I did some more digging and found an advanced Master's Theorem and ended up getting T(n)=O(log^2(logn)). I am not sure how to derive the advanced Master's theorem from the standard one or how to solve the problem using trees/standard Master's theorem.

# Answer
If $m:=\lg\lg n$, then $\lg\lg\sqrt n=m-1$. With $T(n)=T(2^{2^m})=:S(m)$, your recurrence becomes

$$S(m)=S(m-1)+O(m),$$ which has an $O(m^2)$ solution, and $$T(n)=O(\lg^2\lg n).$$

The result holds with logarithms in any base.
> 1 votes

# Answer
Hint: Let $U(k) = T(2^k)$. Find a recurrence relation for $U(n)$, solve it, and then infer a solution for $T(n)$.
> 0 votes

# Answer
Taking $\mathcal{T}\left(\cdot\right)=T\left(2^{(\cdot)}\right)$ and $z=\log\_2 n$ we follow with

$$ \mathcal{T}\left(z\right)=\mathcal{T}\left(\frac z2\right)+O\left(\log\_2 z\right) $$

and taking again $\mathbb{T}\left(\cdot\right)=\mathcal{T}\left(2^{(\cdot)}\right)$ and $u = \log\_2 z$ we follow now with

$$ \mathbb{T}\left(u\right)=\mathbb{T}\left(u-1\right)+ O\left(u\right) $$

let $O\left(u\right) = k u$ then

$$ \mathbb{T}\left(u\right)=\mathbb{T}\left(u-1\right)+ k u $$

has the solution

$$ \mathbb{T}\left(u\right)=c\_0 + \frac k2u(u+1) $$

and now going backwards with $u=\log\_2 z$ and $z = \log\_2 n$ we get

$$ T(n) = \frac k2\log\_2(\log\_2 n)\log\_2(\log\_2 n^2) $$

or

$$ T(n) = O\left(\log\_2^2(\log\_2 n)\right) $$
> 0 votes

---
Tags: recurrence-relation
---


# Question
Title: Amortized analysis (accounting/banker's method) for tree operations
Suppose we have a tree data structure with root $r$ with two operations:

Add($x, y$) - adds the node $y$ as a child to the node $x$

Zip($x$)- this makes the node $x$ and all of $x$'s ancenstors direct children of the root. So if we had a tree like $r \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ then Zip($3$) would make a new tree with root $r$ and children $1, 2, 3$ and $4$ as a child of $3$.

Say Add has cost $1$ and Zip($x$) has cost = length of path from root to $x$

We want to see that the amortized cost of a sequence of Adds and Zips is $\leq 2$ per operation. We want to use the banker's/accountant method to do this.

I'm a bit lost here and would appreciate the help.

# Answer
A new node $x$ can be inserted as a child of some non-root node. From how you describe it, this operation takes constant time. Now when $x$ is touched during a `zip` for the first time, you need to pay for the cost of making it a child of the root. But observe that when $x$ becomes a child of the root it will remain like that hereafter. Node $x$ can still be involved in a zip later when one if its descendant is zipped, but there is no need to transfer $x$, hence it will not incur any cost. Thus, you will only need to pay for transfering node $x$ once.

From this, hopefully you can see how much coin you will assign to `add` so you can save and have enough payment later when a newly inserted node is involved in a zip for the first time.
> 1 votes

---
Tags: algorithms, data-structures, amortized-analysis, average-case
---


title: Intersection between CSL and CFL?

text:
# Question
Title: Intersection between CSL and CFL?
I am trying to find a proof of A ∩ B where A is a **CSL** and B is a **CFL**. Also I know that CFL is a strict subset of CSL. Does that mean that their intersection will give CFL. I am stuck

# Answer
In the general case, the intersection between a context-sensitive language and a context-free language is context-sensitive.

See this post for details.
> 1 votes

---
Tags: regular-languages, automata, context-free, context-sensitive
---


# Question
Title: Is there a formula for this summation $\sum\limits_{k=i}^\mathbb{N}{i}$?
Is there a formulae for this summation? I wonder this could be not a constant or to say that i * i?

$\sum\limits\_{k=i}^\mathbb{N}{i}$

# Answer
$$\sum\limits\_{k=i}^N i = i \sum\limits\_{k=i}^N 1 = i(N - i + 1)$$

Maybe you meant: $$\sum\limits\_{k=i}^N k = \sum\limits\_{k=1}^N k - \sum\limits\_{k=1}^{i-1}k = \frac{N(N+1)}2 - \frac{i(i-1)}2$$
> 2 votes

---
Tags: summation
---


# Question
Title: Proof that Balanced Partition is NP-complete
In the Balanced Partition problem, there are $2m$ nonnegative integers with sum $2s$. The goal is to decide whether they can be partitioned into two subsets of $m$ integers and sum $s$.

The problem is obviously in NP. I am trying to prove that it is NP-complete.

So far, I have found the following reduction from the standard Partition problem (which is the same problem but without the restriction on the number of integers). Given an instance $I$ of Partition with some $n$ integers, do for $k$ in $0,1,\ldots,n-1$:

* Add $k$ zeros to $I$ ;
* If $n+k$ is even, then try to find a balanced partition.

+ If a balanced partition is found, remove the zeros and return it.

If no partition is found for any $k$, return "No partition".

The algorithm is correct since, if a solution to the original instance $I$ exists, then we can add some $k$ zeros to one of the parts to get a balanced partition, so for this $k$, a balanced partition will be found.

This shows that Balanced Partition cannot be solved in polynomial-time unless P=NP. However, it does not show that the problem is NP-complete; according to this Wikipedia page, "a problem is NP-complete if it belongs to NP and all problems in NP have **polynomial-time many-one reductions** to it", while the reduction I just described is not a many-one reduction - it is a Cook reduction.

EDIT: this paper shows that completeness under Cook reduction is (under some assumptions) distinct than completeness under many-one (Karp-Levin) reductions (see also this cstheory.SE question).

Question: How can I prove that Balanced-Partition is NP-complete under a many-one reduction?

# Answer
> 2 votes
Instead of adding $k$ zeros for $k$ in $0,1,\ldots,n-1$, just adding $n$ zeros is enough. It is somewhat funny the reduction in the question is just one-off the right reduction.

---

Here is the detail. It is quite easy.

Let us reduce the partition problem, which is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets with equal sum, to this "balanced partition problem".

Suppose $I=\text{multset}\\{a\_1, a\_2, \cdots, a\_n\\}$, $a\_i\>0$ is (the input of) an instance of the partition problem.

Let $I'=\text{multset}\\{a\_1, a\_2, \cdots, a\_n, a\_{n+1}=0, a\_{n+2}=0, \cdots, a\_{2n}=0\\}$, i.e., $I$ with $n$ zeros added. $I'$ is an instance of the balanced partition problem.

* Suppose $I$ is a yes instance, i.e., there exists $I\subseteq\\{1,2,\cdots, n\\}$ such that $$\sum\_{i\in I}a\_i=\sum\_{1\le i\le n,\\,i\notin I}a\_i.$$ Then $$\sum\_{i\in J}a\_i=\sum\_{1\le i\le 2n,\\,i\notin J}a\_i,$$ where $J=I\cup\\{i\mid n+1\le i\le 2n-|I|\\}$. Since $|J|=2n/2$, we know $I'$ is a yes instance.
* Suppose $I'$ is a yes instance, i.e., there exists $J\subseteq\\{1,2,\cdots, 2n\\}$ such that $|J|=n$ and $$\sum\_{i\in J}a\_i=\sum\_{1\le i\le 2n,\\,i\notin J}a\_i.$$ Removing all items that are $0$ from both sides, we obtain an equality that says $I$ is a yes instance.

The mapping from $I$ to $I'$ is a polynomial-time many-one reduction (a.k.a Karp reduction) from the partition problem to the balanced partition problem. (In fact, it is one-to-one reduction; however, "many-one" is good enough.) Since the former is $\mathsf{NP}$-complete and the latter is in $\mathsf{P}$, the latter is $\mathsf{NP}$-complete as well.

# Answer
> -1 votes
It sounds like you may already know the answer to your first question - the definition of NP-completeness requires you to find a many-one reduction, so no, you have not proven it to be NP-complete, but you have proven that if P!=NP then there is no polynomial-time algorithm for it. See also https://en.wikipedia.org/wiki/NP-completeness#Completeness\_under\_different\_types\_of\_reduction.

---
Tags: np-complete, partitions
---


title: sum of Boolean characters larger degree

text:
# Question
Title: sum of Boolean characters larger degree
I was curious if someone knew the answer/reference for the following. So it is well-known that if $S\in \\{0,1\\}^n$, then $$ \frac{1}{2^n}\sum\_{x\in \\{0,1\\}^n} (-1)^{\langle S, x\rangle}=1 $$ if and only if $S=0^n$ and is $0$ otherwise. Suppose I replace the exponent from a degree-1 term to a degree-2 or degree-k term, do we know how these character sums behave? For example, do we know bounds on the quantity $$ \frac{1}{2^n}\sum\_{x\in \\{0,1\\}^n} (-1)^{x^t A x} $$ (where $A\in \mathbb{F}\_2^{n\times n}$ upper triangular matrix) or in more generality we have $\frac{1}{2^n}\sum\_{x\in \\{0,1\\}^n} (-1)^{f\_k(x)}$ where $f\_k$ is a degree-k multilinear polynomial in $x\_1,\ldots,x\_n$? Any reference would be appreciated if such bounds/exact expressions are known

# Answer
> 2 votes
This is related to higher-order Fourier analysis.

A classical result of Dickson ("Dickson's lemma") states that up to a change of basis, any quadratic form over $\mathit{GF}(2)$ is of the form $$ x\_1 x\_2 + \cdots + x\_{2r-1} x\_{2r} + a x\_{2r+1} + b, $$ for some $a,b \in \mathit{GF}(2)$, where $r$ is known as the *rank*. In your case, $r$ is half the rank of $A + A^T$, and $b = 0$. The quantity you are interested in is known as the *bias*, and can be easily computed at this point: $$ \mathbb{E}\[(-1)^{x\_1 x\_2 + \cdots + x\_{2r-1} x\_{2r} + a x\_{2r+1} + b}\] = \prod\_{i=1}^r \mathbb{E}\[(-1)^{x\_{2i-1} x\_{2i}}\] \mathbb{E}\[(-1)^{ax\_{2r+1}}\] \mathbb{E}\[(-1)^b\]. $$ Now $\mathbb{E}\[(-1)^{x\_{2i-1} x\_{2i}}\] = \frac{1}{4} \cdot (-1) + \frac{3}{4} \cdot (1) = \frac{1}{2}$ and $\mathbb{E}\[(-1)^{x\_{2r+1}}\] = 0$.

Therefore:

* If $a = 1$ then the bias is $0$.
* If $a = 0$ and $b = 0$ then the bias is $2^{-r}$.
* If $a = 0$ and $b = 1$ then the bias is $-2^{-r}$.

---
Tags: boolean-algebra, mathematical-analysis, summation, boolean-complexity
---


# Question
Title: How to tell if I know algorithms & I learned it right?
# Notes

1. I apologize if the question is not formed well, I tried my best.
2. "**Only**" means anything else is discarded.
3. A stupid man’s report of what a clever man says can never be accurate, because he unconsciously translates what he hears into something he can understand. (You are the clever man here, so please try to be simple with me)
4. Please Answer an atomic question; If your advice contains a lot of difference advice, please list them.
5. Please make your answer practical (i.e., in terms of "Do" & "Don't")

# Question

## Briefly

What is the (Point of reference) or (Milestone) or (factor) that I **only** should use when I decide **"I understand algorithms"**?

### Example for "Milestone" Indicator

If you watched a video on how to do derive x2; if you finished the video and failed to obtain the derivative, you will ask yourself intuitively "did I really understand the video?". (The end of the video) is the (Milestone) in case of Mathematics.

And this is my question, what is the milestone in case of Algorithms?

## Precisely

1. Am I required to **only** learn popular algorithms & their solution patterns?
2. Or is it like Mathematics? (I should learn **"how to derive an algorithm and its complexities"** (even if I will not be able to derive the optimal solution) but at least, I can identify, understand & build an algorithm even if I never encountered it.

## All Understanding-Factors that I know

1. I can **only** solve the homework provided by the instructor.
2. I can **only** implement the algorithm in any programming language? or implement & identify **also** the written algorithm and its complexity? ("write" or "read & write")
3. Should I be able to identify an implemented code's algorithm **even if I did not study it before**? if yes, then how?

# Question's Reasons & Explanation

## Reasons

Algorithms courses (explicitly MIT 2011 & 2020, Stanford, San Diego, Princeton) teach only "The Algorithms only written in the book", thus, you cannot identify/understand anything beyond what they taught in the course.

## Reasons Explanation

This is similar to learning the test instead of the subject, you **only can answer questions**, already taught to you, and get good grades **without actually learning** the subject or how to use it in the real world.

# Resulting Problem

Unfortunately, I could not decide how to study Algorithms till now because:

1. I do not know how to identify if I am actually learning or just deceiving myself, which will be used to choose the course that I will learn from.
2. I am certain that you can get the delusion of knowing algorithms very well just because "you got a good grade" or "applied it once before".

# Answers

These are the answers that I reached so far, but I cannot verify because I lack the experience:

1. Learn by practice, specifically, **problem solving**.
Reason: because you do not need to learn everything at once, just learn what you need and let the calculation & invention for scientists and researchers.
2. Understanding-Factor is the ability to **identifying** the class of **problems** & their **solutions** when you encounter a problem. If you failed, search for new theorems that solve that problem. But you always need to know how to **calculate the space & time complexity** of the theorem. (I still do not know how to calculate the complexity of the algorithm).
Reasons: (same as the above reason)
3. **Only** study the test (provided algorithms).
Reasons: Because 90% of the Business problems require only already implemented & tested algorithms; Thus, your only role is to choose "what" & "when" to use an algorithm. The other 10% is left for researchers (via enhancement or even creation). Even if you are in the Algorithms development, you need tools that include a big number of Algorithms Design Techniques & A lot of Applications on it to be able to enhance & test it.
**Issue**: I found some questions/answers in the community that contradicts that "90% & 10%" which are: What do I need to know about algorithms?, How do I know if my algorithm is right (without coding)?, How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect.
4. Learn Algorithms & Data Structures **and also** Design & analysis of Algorithms & Data Structures.
Reason: Because it is not enough to know some Algorithms patterns but to also understand & analyse it (the person gave examples that I will translate in case somebody cares).
5. Algorithms are not a simple thing that can be covered within a single course. It can be broken down into the following:
a. Algorithm Design (which explains the general algorithm concept).
b. Algorithm Proof.
c. Algorithm Analysis.
d. Algorithm Standard Application.
e. Algorithm Enhancement & Addition.
f. Practical Application of Algorithm.
Each & every point is a course/topic in itself, and there can't be a course that covers all topics at once; Not even the most popular books (CLRS).
Therefore, the 3 questions of understanding an algorithm is composed of three main aspects (design, analysis, application). So as a conclusion, you do not need a single course to cover algorithms but rather multiple courses until you get it.
So to rephrase your question, "Is algorithms branch a (principle & skills type science branch) or (pattern science branch whereby you only apply patterns)?" and the answer is: I think it is both, you apply patterns but also whenever you need to dig deep, you really need to have the principle & skills that enable you to find a pattern.
Another aspect is, how to study algorithms?
a. Solve it on paper in a mathematical form.
b. Draw flowcharts.
c. watch other people's answers (solution and analysis).

# Answer
The premise of the question is faulty. There is no point at which "I understand algorithms" -- it is not a black-and-white matter, where one day we are required to say "I don't understand algorithms" and then I learn one more fact and the next day I am allowed to say "I understand algorithms". Instead, it is a matter of shades of grey.

My advice: don't get caught up in trying to answer a global question like "can I say I understand algorithms?". Instead, learn whatever topics you find interesting or useful. There is always more to learn.
> 2 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Do modern RAFT implementations assume that nodes trust each other?
I'm starting to dig into the RAFT consensus algorithm and I wanted to clarify something pretty basic: it seems like RAFT operates on the assumptions that 1) each node trusts all the other nodes and that 2) nodes would not have a failure mode where they would incorrectly identify themselves as a leader from a higher term.

My understanding is that 2 is prevented if 1 is true and if RAFT is correctly implemented, because no node would identify itself as a leader without a quorum. In a partition scenario, the worst case is that there are two partitions of unequal size, and so only nodes in one of the partitions should ever be able to be elected leader.

So I think my question is really just to get some clarity on whether RAFT algorithms rely on trusting the messages received from other cluster members.

# Answer
> 1 votes
A common assumption is "Messages are delivered without corruption" - which means nodes trust each other. So you are right!

---
Tags: consensus
---


title: SAT and #SAT in Quantum

text:
# Question
Title: SAT and #SAT in Quantum
Let us look at the two questions that are NP-complete for a classical computer:

1. Given an arbitrary Boolean expression, find an assignment of variables that evaluates the expression to $0$ (SAT).
2. Given an arbitrary Boolean expression, count the number of assignments that evaluates the expression to $0$ (#SAT).

We know that the Simon's algorithm or the Grover's search can effectively solve the first problem with square-root complexity with high probability. Is it the case for the second problem too, or a quantum computer still needs to perform the same number of queries as a classical computer does?

# Answer
It depends on how many satisfying assignments there are. If there are $t$ satisfying assignments, then it takes approximately $O(\sqrt{Nt})$ time for a quantum algorithm to identify all of them, if we are given an oracle to recognize which assignments are satisfying. This can be compared to $O(N)$ time for a classical algorithm to do the same task. So if $t$ is small, a quantum algorithm is significantly better.

See Quantum Counting, Gilles Brassard, Peter Hoyer, Alain Tapp, ICALP 1998.
> 2 votes

---
Tags: satisfiability, quantum-computing
---


# Question
Title: Time complexity of merging two lists while preserving order
I have two lists `l1` and `l2` of possibly unequal sizes (say, `m` and `n`). I wrote an algorithm to find out all ways `l1` and `l2` can be merged while preserving their order.

```
l1 = ["NYC", "LA"]
l2 = ["A", "B"]

output:
[['NYC', 'LA', 'A', 'B'],
 ['NYC', 'A', 'LA', 'B'],
 ['NYC', 'A', 'B', 'LA'],
 ['A', 'NYC', 'LA', 'B'],
 ['A', 'NYC', 'B', 'LA'],
 ['A', 'B', 'NYC', 'LA']]

```

`NYC` always comes before `LA`. `A` always comes before `B`.

Basic idea of algorithm: Append one item from `l1` to `temp`, recurse on remaining part of the lists. Do the same for `l2`.

Code (python3):

```
def merge(l1, l2):
    temp = [] # temporary buffer
    res = [] # final result
    mergeHelper(l1, 0, l2, 0, temp, res)
    return res

def mergeHelper(l1, start1, l2, start2, temp, res):
    if start1 >= len(l1) and start2 >= len(l2):
        res.append(temp.copy())
        return

    if start1 < len(l1):
        temp.append(l1[start1])
        mergeHelper(l1, start1+1, l2, start2, temp, res)
        temp.pop()

    if start2 < len(l2):
        temp.append(l2[start2])
        mergeHelper(l1, start1, l2, start2+1, temp, res)
        temp.pop()

```

**Question**: What's the time/space complexity? I suspect it might be $O(2^{n+m})$ as we have two choices for every iteration.

I figured out the recurrence relation is: `T(m,n) = 1 + T(n-1, m) + 1 + T(n, m-1)` but unable to reduce it further.

# Answer
The number of ways to combine an ordered list of size $n$ and an ordered list of size $m$ into one ordered list of size $n+m$ in a way which keeps the order of both lists is given by the binomial coefficient $$\binom{n+m}{n}$$ The time complexity of your procedure depends on various implementation details.
> 1 votes

---
Tags: algorithms, time-complexity, runtime-analysis, recurrence-relation, recursion
---


# Question
Title: How does this context-free grammar generate even length strings on either side?
I came across this context-free grammar for the language L = {xy||x|=|y|, x≠y}, but I can't seem to see how it can generate all lengths for x and y. Could someone illustrate this? For example, how would you derive the string "abba" or "aaabbaaa"?

# Answer
Suppose that $|x| = |y| = n$ and $x\_i \neq y\_i$, say $x\_i = a$ and $y\_i = b$. We can therefore write $x = r a s$ and $y = ubv$, where $|r| = |u| = i-1$ and $|s| = |v| = n-i$. Therefore $$xy = rasubv, $$ where $|r| = i$, $|su| = (n-i) + (i-1)$, $|v| = n-i$. Now let $p$ be the first $i-1$ letters of $su$, and let $q$ be the final $n-i$ letters of $su$, so that $su = pq$. Then $$ xy = rapqbv. $$ Now $A$ generates $rap$ (since $|r| = |p| = i-1$) and $B$ generates $qbv$ (since $|q| = |v| = n-i$), and so the grammar generates $xy$.

Now let's consider your two examples, starting with $abba$. In this case, $x = ab$ and $y = ba$, and so there are two choices for $i$: $i = 1$ and $i = 2$.

If we choose $i = 1$ then $x = ras$ for $r = \epsilon$ and $s = b$, and $y = ubv$ for $u = \epsilon$ and $v = a$. We have $su = b = pq$, and so $p = \epsilon$ and $q = b$. We now generate $xy$ as follows. First, $A \Rightarrow^\* rap = a$. Second, $B \Rightarrow^\* qbv = bba$. Finally, $S \Rightarrow AB \Rightarrow^\* (a)(bba)$.

If we choose $i = 2$ then $x = rbs$ for $r = a$ and $s = \epsilon$, and $y = uav$ for $u = b$ and $v = \epsilon$. We have $su = b = pq$ and so $p = b$ and $q = \epsilon$. We can generate $rbp = abb$ using $B$ and $qav = a$ using $A$, and put them together via $S \Rightarrow BA$ to generate $(abb)(a)$.

In your second example $aaabbaaa$ we similarly have two options for $i$: $i = 1$ and $i = 4$. If we choose $i = 1$ then $x=ras$ for $r = \epsilon$ and $s = aab$, and $y = ubv$ for $u = \epsilon$ and $v = aaa$. Then $su = aab = pq$, and so $p = \epsilon$ and $q = aab$. We generate $rap = a$ using $A$ and $qbv = (aab)b(aaa)$ using $B$, and put them together via $S \Rightarrow AB$ to generate $(a)(aabbaaa)$.

Finally, if $i = 4$ then $x = rbs$ for $r = aaa$ and $s = \epsilon$, and $y = uav$ for $u = baa$ and $v = \epsilon$. Then $su = baa = pq$, and so $p = baa$ and $q = \epsilon$. We generate $rbp = (aaa)b(baa)$ using $B$ and $qav = a$ using $A$, and put them together via $S \Rightarrow BA$ to generate $(aaabbaa)(a)$.
> 0 votes

---
Tags: context-free
---


# Question
Title: Big O vs. Big Theta for AVL tree operations
On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big Theta in general but am having trouble understanding why they are used in such a way here. A source is linked but it does not seem to make any reference to Big Theta, only Big O.

For example, why is the space complexity for the tree $\Theta(n)$ in the average case but $\mathrm{O}(n)$ in the worst case? My thought process is that since you *always* have to store all $n$ nodes in the tree, the space complexity is both $\Omega(n)$ and $\mathrm{O}(n)$, hence it should be $\Theta(n)$ in all cases. I don't see how there can be a "worst case" in terms of space when you're always storing the same amount of data.

Similarly, for searching, why is the time complexity $\Theta(\log n)$ for the average case but $\mathrm{O}(\log n)$ in the worst case? To me this seems to imply you need to check at least some multiple of $\log n$ nodes in the average case, but not in the worst case? If the worst case is not bounded below by some multiple of $\log n$ (so could be lower in some cases), is this not a better scenario than what is given for the average case? Should it not be the other way round? It's a similar situation for insertion.

I'm not sure what I'm misunderstanding about the operation of AVL trees, average vs. worst cases, or perhaps asymptotic notation in general, that's causing this misunderstanding. Is it just always convention to state worst case in terms of Big O?

# Answer
This is a pedantic point which I suggest ignoring.

The intended interpretation of the "worst case" column seems not to be the worst-case complexity, but rather bounds on the complexity which are true *always*. For example, Search *always* takes time $O(\log n)$; it doesn't always take time $\Theta(\log n)$.

It's true that the worst-case complexity is $\Theta(\log n)$, but usually we think of it a bit differently: $O(\log n)$ is a tight upper bound on the running time of Search. This means that $O(\log n)$ is a valid bound on the running time of Search, and that we can't improve it to $O(f(n))$ for any $f(n) = o(\log n)$.
> 5 votes

---
Tags: asymptotics, big-o-notation, binary-search-trees, avl-trees
---


title: Algorithm for Wrapping Problem

text:
# Question
Title: Algorithm for Wrapping Problem
Assume we have n items with each having a different length and m wrappers each has a different length. The cost of every wrapper is proportional to its length. An item can be covered with one or more wrappers but the wrappers can not be divided. What is the algorithm to wrap the item in the cheapest possible way (least cost of the wrappers)? I know this problem is a NP-hard or NP-complete problem. But can not find exactly which problem it can be mapped into.

What should be the approximation scheme for this problem?

# Answer
I'll consider the case in which items and wrappers are allowed to have the same length. What follows extends to your case by dealing with small enough perturbations of the lengths.

It is strongly NP-hard to even decide whether the problem admits a feasible solution. Indeed, you can reduce from an instance of 3-partition in which you have $3n$ positive integers $x\_1, x\_2, \dots$ strictly between $\frac{1}{4n}\sum\_{i=1}^{3n} x\_i$ and $\frac{1}{2n}\sum\_{i=1}^{3n} x\_i$. In order to do that, you can consider an instance with $m=3n$ wrappers of lengths $x\_1, x\_2, \dots$ and $n$ items of length $\frac{1}{n}\sum\_{i=1}^{3n} x\_i$.

This means that the approximation ratio is unbounded. Indeed, the cost of a yes-instance is upper bounded by $\sum\_{i=1}^{3n} x\_i$, while a costly solution can be forced to exist by adding $n$ additional wrappers of length $L \sum\_{i=1}^{3n} x\_i$ for some large enough $L$.

Then, assuming $\mathsf{P} \neq \mathsf{NP}$, any polynomial-time algorithm that provides an approximation ratio smaller than $\frac{L \sum\_{i=1}^{3n} x\_i}{\sum\_{i=1}^{3n} x\_i} = L$ could be used to solve the decision version of your problem (and hence 3-partition) in polynomial time.
> 2 votes

---
Tags: np-complete, np-hard
---


title: How to create tensors at runtime?

text:
# Question
Title: How to create tensors at runtime?
I have a small personal CAS project around linear algebra which involves, among other things, manipulating tensors. When I talk about tensors, I mean them according to the **physical / mathematical** definition, so this is of little importance for the rest of the question, but I would like to make it clear that what I want to manipulate is not simply arrays of any dimensions (a tensor is not a multidimensional matrix, even if I will later contradict myself, but for good reasons).

Since I am trying to create a CAS, I have a DSL in which the user can enter expressions and define objects, such as tensors. The user can define a tensor quite symbolically, without specifying values for components, in which case the problem I am encountering does not arise.

In a very general way, a user who wishes to specify the components of a tensor will do so *component by component*, so the component of a tensor of order $N$ will be of the form $C\_{i, j, ..., N}$ (if for the sake of simplicity we consider here only covariant components). For example, if I define a 3 times covariant tensor $T\_{ijk}$ and I want to define its component $T\_{3,2,1}$ with any expression $x$, I would write $T\_{3, 2, 1} = x$. In practice, one will often use matrices to do this (or a new tensor will arise from another operation, as a tensor product), but I want to be as general and abstract as possible, if possible.

So that's where my problem lies. If a user, for whatever reason, decides to create (or generate by a particular operation) a tensor of order N, the DSL must be able to represent internally the different components that constitute it in an adequate way. Even if it is not mathematically correct to define a tensor as a multi-dimensional array, at a given time, it must be manipulated numerically and at runtime, so that it is possible for my implementation to access each component from a given position $i, j, ..., N$ where N is not known at compile-time.

I am therefore looking for a way to define a kind of multi-dimensional array *at runtime*, i.e., for example, do something like (C#) `int[, ,] arr3d; int[, , ,] arr4d;` but dynamically. I've been programming long enough to know that this is not possible (at least not in a clean way).

My idea is then to use a geometric approach and to consider only one list of elements representing all the components. The position, in the geometrical approach, of each of the terms of this list individually would then be defined by another list `[i, j, ..., N]` whose general form would be fixed (at runtime) at the creation of the tensor. To clarify my thinking, here is a little pseudo-code that defines the useful types:

```
/// The position of a component represented by a list i, j, ..., N
type Position = int list

/// The type for a single component
type 'K Component = { position: Position; value: 'K }

/// The numerical components of a tensor
type 'K Components = 'K Component list

```

For example, a simple scalar would then have the components $(i)$ where $i$ can only be 0 (otherwise it is a vector), so I would make

```
let myScalar (x: int) =
    let pos : Position = [0]
    let components : Component<int> = { position=pos; value=x }
    let result : Components<int> = [ components ]

    result

```

Another example, a vector:

```
let myVector (len: int) (values: int list) =
    assert (values.Length = len)

    // "a vector of size len", so "len" is a "border"
    let pos = [len]

    let result : Components<int> = []

    for i=0 to len do
        let c = { position=[i]; value=value[i] }
        result += c

    result

```

Another example, a matrix:

```
let myMatrix (n: int) (m: int) (values: int list) =
    assert (n * m = values.Length)

    // like a square, the borders are "n" and "m"
    let pos = [n; m]

    let result : Components<int> = []

    for i=0 to n do:
        for j=0 to m do:
            let c = { position=[i; j]; value=... }

    .....

```

This is obviously pseudo code (F#), but I really hope you get the idea... The problem with this approach is

1. it becomes difficult to determine "edges" at N-dimensions.
2. it is not possible to define new `for` loops at runtime.

Since then, I have been thinking about this problem, but I have not found any way to meet my expectations, so I summarise them:

* I want to be able to represent the components of a tensor for non-fixed positions at compile-time.
* I want to be able to access the $(i, j, ..., N)$-th component by mentioning it by means of a list (if it had been fixed at compile-time, I would have remapped the list by a tuple of course).

My question is then "simply" how to do what I have just explained, by completing my geometrical approach for example, or by pointing me to a completely different one.

PS: in fact I talk about tensors in my question to give a real context of my problem, if I had simply asked for an array with indeterminate dimensions at compile-time, I would have been advised to review my algorithms. By the way, if you have a better idea to represent such an object, I'm interested! I did a lot of research on the Internet, but I didn't find anything...

PSS: I wasn't very formal in the explanations I gave about tensors, but who cares, I don't do math here, I only implement them like I can on a computer that even no know about the existance of the number 3.

# Answer
If you have an $N\_1 \times \cdots \times N\_d$ tensor, you can index the (zero-based) $(i\_1,\ldots,i\_d)$'th position using the formula $$ \sum\_{j=1}^d i\_j \prod\_{k=j+1}^d N\_k, $$ which you can compute in $O(d)$ if you're careful.

If you want to go over all positions, you can go over $I \in \\{0, \ldots, \prod\_{i=1}^d N\_i - 1\\}$, and extract the individual indices as follows: $$ i\_j = \left\lfloor I\middle/\prod\_{k=j+1}^d N\_k \right \rfloor \bmod N\_j. $$ Once again, you can compute this in $O(d)$ if you're careful.

The two operations are inverses of one another, and they are known as *ranking* and *unranking*.

There are other ways to over all positions. For example, you could start at the position $(0,\ldots,0)$, which you then increment as follows: start at $j = d$; increment $i\_j$ modulo $N\_j$; if there was an overflow, decrease $j$. If $j$ ever gets to zero, you have finished going over all entries.

---

In your case, you might also consider to write specialized code for tensors of small dimension, since these are the ones most likely to be encountered in practice. If you know the dimension, there is no problem with writing the nested loops as usual.
> 2 votes

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


# Question
Title: Maximum sum of values in a square grid (one in each row/ column)
this is my first post here so bare with me :).

What i'm looking for is an algorithm that can find the maximum sum of values in a square grid under the restriction, that you can only pick 1 value from each column and row.

so for example:

$$ \begin{matrix} 3 & 2 & 5 \\ 4 & 1 & 4 \\ 3 & 1 & 2 \\ \end{matrix} $$

in the first row, you pick 5, in the second you pick 4 and in the third you pick 1, for a total of 5+4+1 = 10.

The algorithm I came up with is similar to using Laplace expansion to find the determinant of a matrix.

(I'm using matrix and square grid interchangebly)

For every value in the first row, you recursively find the max sum of the matrix without that values' column/row and then add that result with the value. The maximum of these is our result (recursion end: 1x1 matrices return the value).

This algorithm runs in O(n!) (T(n) = n\*T(n-1) for n x n square grids) and I was wondering if anyone of you can come up with a faster algorithm.

I know that there are faster algorithms for finding the determinant, such as LU decomposition O(n^3) and Bareiss' algorithm O(n^3) or fast matrix multiplication O(n^2.373), but the ones I have looked at were to confusing for me to change into a fitting algorithm for this problem.

# Answer
Your problem is known as the assignment problem, and can be solved efficiently.
> 3 votes

---
Tags: algorithms, matrices, summation
---


# Question
Title: Is this language regular or non-regular : {ww | w ∈ {a,b}* } ∩ {a}*
I think it's a regular language but I can't find a DFA or a regular expression. Would anyone know how to help me?

# Answer
Hint: words in $\\{ww\mid w\in\\{a,b\\}^\*\\}$ have even length.
> 2 votes

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


# Question
Title: Why is there the regularity condition in the master theorem?
I have been reading *Introduction to Algorithms* by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be satisfied to use the theorem:

> ... 3. If
>
> $\qquad \displaystyle f(n) = \Omega(n^{\log\_b a + \varepsilon})$
>
> for some constant $\varepsilon \> 0$ and if
>
> $\qquad \displaystyle af(n/b) \leq cf(n)$ \[**this is the regularity condition**\]
>
> for some constant $c \< 1$ and for all sufficiently large $n$, then ..

Can someone tell me why the regularity condition is needed? How does the theorem fail if the condition is not satisfied?

# Answer
> 13 votes
Not a rigorous proof, but a "from the top of my head" explanation.

Imagine the recurrence $aT(n/b)+f(n)$ as a tree. The third case covers the scenario when the root node dominates the running time asymptotically, i.e. most of the work is being done in measly node on top of the recurrence tree. Then the running time is $\Theta(f(n))$.

To make sure the root actually does more work you need the

> $a f(n/b) \leq cf(n)$.

This says that $f(n)$ (the amount of work done in the root) needs to be at least as big as the sum of the work done in the lower levels. (The recurrence is called $a$ times on $n/b$ of the input.)

E.g. for the recurrence $T(n)=2T(n/4)+n$ the work on the level below the root is one fourth as big and only done twice $(n/4+n/4)$ versus $n$ so the root dominates.

But what if the function didn't fulfill the regularity condition? E.g. $\cos(n)$ instead of $n$? Then the work done on the lower levels might be bigger than the work done in the root so you are not certain that the root dominates.

# Answer
> 9 votes
Let $a = 1$ and $b = 2$, so that $$ T(2^n) = \sum\_{k=0}^n f(2^k). $$ For case 3 to apply, we need $f(n) = \Omega(n^\epsilon)$ (for some $\epsilon \> 0$) and the regularity condition, $f(n/2) \leq (1-\delta) f(n)$ (for some $\delta \> 0$). You get the regularity condition from the proof, i.e. it's a proof-generated concept. While the regularity condition isn't necessary (consider the example given on Wikipedia, $f(n) = n(2-\cos n)$), you can't drop it completely, as the following example demonstrates. Consider $$f(2^n) = 2^{2^{\lfloor \log\_2 n \rfloor}} \> 2^{2^{\log\_2n-1}} = 2^{n/2}.$$ Let $n = 2^{m+1}-1$. Then $$T(2^n) = \sum\_{k=0}^m \sum\_{t=2^k}^{2^{k+1}-1} 2^{2^k} = \sum\_{k=0}^m 2^{2^k+k} = \Theta(2^{2^m+m}), \quad f(2^n) = 2^{2^m}. $$ So it's not true that $T(2^n) = \Theta(f(2^n))$.

There is a more general theorem, Akra-Bazzi, in which the regularity condition is replaced by an explicit quantity that comes into the result.

# Answer
> -1 votes
We check regularity condition to check whether the work done by parents node is more than the work done by children. If the regularity condition fail we use another method in recurrences.

---
Tags: algorithms, asymptotics, mathematical-analysis, landau-notation, master-theorem
---


# Question
Title: Help with Linear recurrence relation with balanced partition
In my slides for my algorithms class, I have a method of finding the complexity of recursive functions called **Recurrence Relation with "partizione bilanciata" which means "balanced partition"**.

My course is in Italian and looking online in English I could not find any trace of this method, I know of the **recursive tree**, **induction**, and **master theorem**.

Has anyone any idea of how this is called in English? I don't like studying in Italian and I do not understand those pdfs.

I'm attaching some images of the formulas.

What exactly "balanced partition" mean, does it have something to do with for example Quick Sort, when you choose a middle pivot and the partitions are equal in size, which means it's balanced?

Is it the same as master theorem written maybe in a different way? I can see the form of the recurrence relation is different than the master theorem:

The master theorem has $f(n)$ instead of $cn^\beta$.

# Answer
Looks like I learned it by myself in a different way than my teacher teaches it, and that is why I never heard of "balanced partition".

Apparently it means that a problem is divided in more sub problems (kind of like quick sort as I said), and when we have this condition where T(n/b) and b\>=2, we use the "balanced partition" method.

I learned it in a different way, by getting Theta as f(n) and looking for p and k, where Theta(n^k * log^p(n)) , after that I have different cases, like in the following picture, my teacher teaches in a different way and that is why i got confused, because in English there is no "balanced partition" therm.
> 0 votes

# Answer
$aT\left(\dfrac nb\right)$ clearly indicates that $a$ subsets of equal size $\dfrac nb$ are processed. For instance in dichotomic search, $a=1$ and $b=2$. In MergeSort, $a=b=2$.

Partitions are indeed called balanced when the subsets are of equal size. The same term is used with trees and subtrees.

\[More generally, it suffices that the ratio of the sizes does not get smaller than a known positive constant. This is the case for instance in the "Median of medians" algorithm for linear-time median search. This works because the size of the subproblems tends to one geometrically, hence in a logarithmic number of steps.

In QuickSort, such a lower bound of the ratio cannot be guaranteed, hence its possible $O(n^2)$ degeneracy.\]
> 0 votes

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


# Question
Title: What is a witness string? I unable to understand the concept
From the text

> A language $L$ is in the class $NP$ iff there exists a polynomial-time Turing machine, denoted $V$, that gets an input string $x$ as well as a read-only string called the witness $w$, such that for any input string $x$,
>
> * if $x \in L$, then there exits a witness string $w$ such that $V^{w}(x)$ = "yes".
> * if $x \notin L$, then for any witness string $w$, $V^{w}(x)$ = "no".
>
> The Turing machine $V$ is also called a verifier.

First of all, I am unable to understand the notation $V^{w}(x)$ \- is $w$ also an input to the verifier - i.e. is it the same as $V(w,x)$?

Also, what is the nature of this witness string? Can someone give an example witness for a simple problem (the problem need not be an NP hard problem) and how the witness string is used by the verifier?

# Answer
> 9 votes
To give a concrete example, imagine you have a box of 4-digit combination padlocks. All those padlocks are closed, but some of them have a defect and no code can open them.

Given a padlock, you want to know if it can be opened or if it has a defect. The naive way to do it is to try all codes until it opens, or until you have tried all codes, so it may take up to 10000 tries to know the answer, for just one padlock.

However, suppose Superman is in the room. With his X-ray vision, he can guess immediately what the opening code of a padlock is. When you pick a padlock, Superman may say "the opening code is 2587". No matter if he is lying or not, and you just have to roll the four wheels until the padlock is in position 2587 to try if it opens it. If it is the right code, then the padlock will open. However, if the padlock has a defect, no matter the code Superman tells, the padlock will never open.

In this context, the language $L$ is the set of padlocks that can be opened, a word $x$ is a padlock, the witness string $w$ is the 4-digit code given by Superman and the verifier is you rolling the wheels in the right position.

# Answer
> 3 votes
Example: Let L be the language of all binary strings representing composite numbers. The input x for the verifier is a binary string; x is in L iff x represents a composite number (i.e x factors into two or more smaller numbers both different from 1). A witness w for L would be a binary string, different from both 1 and x, representing a factor; the verifier uses the witness by confirming that x is exactly divisible by w. If x is in L (i.e. x is indeed composite), there is some w between 1 and x which divides it, so there is a witness; if x is NOT in L (i.e. x is 1 or prime), then it is divisible only by 1 and x, so there is no witness.

That is just one example. Exactly how the verifier uses the witness depends on the nature of L and how the verifier checks for membership in L. Another case would be of a language checked by a probabilistic verifier - i.e, the verifier is allowed to 'flip coins' during the checking, and x is in L iff it is possible for the verifier to reach an accepting state. In this situation the witness would be a recording of the required coin flips leading to acceptance - i.e whenever the verifier needs to flip a coin it actually gets the 'next' bit from the verifier.

---
Tags: complexity-theory, np-hard, decision-problem
---


title: Right Reset Turing Machine

text:
# Question
Title: Right Reset Turing Machine
How do you simulate an ordinary turing machine using a right reset turing machine ? *(*A right reset machine is in which you can move left and reset to right end position*. Moreover the tape is unbounded on left but it is bounded on right)*

# Answer
> 2 votes
A complete description of the simulation would be tedious. In the following I will only be sketching a strategy that allows you to simulate a movement to the right, which seems to be where the difficulty lies.

If the head is in some tape cell and you want to move it to the right you can do the following:

1. Add a "mark", which we will call $\alpha$, to the symbol in the current cell (formally this introduces a new symbol $x\_\alpha$ for each symbol $x$ in the tape alphabet).
2. Reset the head to the rightmost tape cell.
3. Place a $\beta$ mark on the current tape cell.
4. Scan the tape from right to left, while remembering whether the previous symbol had a $\beta$ mark. Stop as soon as you reach the symbol with the $\alpha$-mark.
5. If the previous symbol had a $\beta$ mark, then:

5.1. Remove the $\alpha$ mark from the current symbol.

5.2. Reset the head position.

5.3. Scan the tape from right to left until you find the symbol with the $\beta$ mark.

5.4. Remove the $\beta$ mark. The head is now one location to the left w.r.t. its position at the beginning of this procedure.
6. Otherwise (the previous symbol did not have a $\beta$ mark):

6.1. Reset the head position.

6.2. Scan the tape from right to left until you find the symbol with the $\beta$ mark.

6.3. Remove the $\beta$ mark from the current symbol.

6.4. Move left.

6.5. Add the $\beta$ mark to the current symbol.

6.6. Reset the head position and repeat from instruction 4.

# Answer
> 1 votes
The right reset TM (RRTM) based on your setup lacks the ability to move one position to the right. To simulate this, when the RRTM is at cell $c$ and needs to move to $c\_r$, the cell to the right, it marks the content of cell $c$ i.e. put a dot on top of the symbol on $c$, move to a special state $q\_{search}$, then do a right reset. Now, it finds $c\_r$. To do this, it marks the current cell $c\_i$ using two dots and move left to $c\_j$. If $c\_j$ has a dot then the TM is on $c$ and the previously marked cell, $c\_i$, is $c\_r$. The TM enters state $q\_{found}$ and reset right. It continuously moves left until it find $c\_i$ again (by looking for the cell with two dots). It changes the two dots to a single dot then move left and remove the dot from this current cell (this is cell $c$). It then right reset again and move left continuously until the cell with a dot is found, which is $c\_r$. The TM can now proceed normaly.

If in case $c\_j$ has no dot then it is not $c$ and the the cell marked with two dots is not $c\_r$. The TM right resets and move left until it get to $c\_i$ (the cell with two dots) . It removes the two dots in $c\_i$, move left and let this next cell be the new $c\_i$ and repeat the process above to check if $c\_i$ is $c\_r$.

---
Tags: turing-machines, automata
---


# Question
Title: What is the language that this DFA accepts?
I've faced this question in my homework, I tried to solve it but I couldn't.

We're given a DFA:

---

---

Every time I tried to define the language, I found a word that the DFA accepts but the language I defined doesn't. I'll be thankful if anyone can at least tell the language the DFA defines without giving any explanation or proof of why it does.

---

One more question that isn't related to the topic: How could I put a text/image in the center of the page? like the image above, how could I put it in the center? I tried using \< center \> but it couldn't work.

# Answer
It accepts the language $\\{w \in \\{0,1\\}^\* \\; : \\; |w|\_0 - |w|\_1 \equiv 1 \pmod{3} \\}$, where $|w|\_x$ denotes the number of occurrences of character $x \in \\{0,1\\}$ in the word $w$.

To see that this is indeed the case, notice that state $q\_i$ encodes the situation in which that the number of $0$s minus the number of $1$s read so far is $i \pmod{3}$.
> 0 votes

---
Tags: automata, finite-automata
---


# Question
Title: Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)
Given a undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=2022n$ and some weight function $w\colon E\to \mathbb{R}$, and $0≤ w(e) ≤n$ for all $e∈E$,

> Describe an algorithm that determines if the MST of $G$ only uses edges with an integer weight.

i got this question in exam 2 weeks ago and my solution didn't get any point (wrong solution). But i didn't really understand what wrong with it i will just write the main point of it here, and hope someone can point out/explain where is the problem in it.

**My original solution :**

1. run "improved" DFS that save for each $v$ with his $π$ the "heaviest" non integer edge we found , the "heaviest" integer edge and the amount of non integer edge we found,
2. i proved the MST cycle property same idea like this answer here and used property of uniqueness set of weight in any MST
3. then i claim that while running DFS for each back discover =\> we close cycle =\> if we found integer heaviest $e$ edge and other non integer edge $e\*$ between $v$ and $π\[v\]$ such as $w(e\*)\<w(e)$ =\> so $e\*$ must appear in some MST =\> the algorism will stop and return that $G$ don't have MST with only integer value.

so it's total runtime will be $O(V+E)$ = \> $O(n)$

the official solution run time is $O(E α(V))$ =\> $O(n α(n))$, where α is the inverse of the single-valued Ackermann function.

# Answer
**The** MST of $G$ is not well-defined since there might be multiple MSTs of a graph. However, it can be shown that:

**Claim 1:** either all MSTs use only edges with integer weights or none of them does.

**Proof:** Suppose towards a contradiction that there are two MSTs $T\_1, T\_2$ of $G$ such that $T\_1$ only uses edges with integer weights while $T\_2$ contains at least one edge $e$ with a weight in $\mathbb{R} \setminus \mathbb{Z}$.

Consider the fundamental cycle $C$ obtained by adding $e$ to $T\_1$. Let $f$ be an arbitrary edge chosen from those having maximum weight in $C$. We cannot have $f=e$, since otherwise the edge of maximum weight in $C$ would be unique and hence $f$ would not belong to any MST. Moreover, we cannot have $f \neq e$ since otherwise the weight of $f$ must be larger than the weight of $e$ and hence $T\_1-f+e$ is a spanning tree of $G$ that is lighter than $T\_1$. $\square$

Let $I$ be the set of edges in $G$ having integer weights. The above claim tells us that, in order to solve your problem, it suffices to compute an arbitrary MST of $G$ and check whether it only uses edges in $I$. Consider a new graph $G'=(V, E')$ obtained from $G$ by reweighing each edge $e$ as follows: if the weight $w(e)$ of $e$ is an integer, let the new weight $w'(e)$ of $e$ be $2w(e)$. Otherwise, let the new weight $w'(e)$ be $2 \lfloor w(e) \rfloor + 1$. We can construct $G'$ in time $O(n)$ since $|E|=O(n)$ and we can take floors of real numbers in constant time, as per your clarification in the comments.

I claim the following:

**Claim 2:** there exists an MST of $G'$ that uses only edges with even weights if and only if there exists an MST of $G$ that uses only edges in $I$.

**Proof:** Let $T$ be an an MST of $G'$ that only uses edges with an even weight. Consider an edge $f = (u,v) \not\in I$ and notice that, since $w'(f)$ is odd, $f$ does not belong to $T$. Let $P$ be the unique path between $u$ and $v$ in $T$. From the cycle property and the fact that $w'(e) \neq w'(f)$, it follows that all edges $e \in P$ satisfy $w'(e) \< w'(f)$. As a consequence $w(e) = \frac{w'(e)}{2} \< \frac{w'(f)}{2} = \lfloor w(f) \rfloor + \frac{1}{2} \< \lceil w(f) \rceil$ which implies $w(f) \> w(e)$. As a consequence $f$ cannot belong to any MST of $G$.

Let $T$ be a MST of $G$ that only uses edges in $I$. Consider an edge $f=(u,v)$ such that $w'(f)$ is odd and notice that $f$ does not belong to $T$. Let $P$ be the unique path between $u$ and $v$ in $T$. From the cycle property and the fact that $w(e) \neq w(f)$ it follow that all edges $e \in P$ satisfy $w(e) \< w(f)$. Then: $w'(e) = 2w(e) \< 2w(f) \< 2\lfloor w(f) \rfloor + 2 = w'(f) + 1$, which implies $w'(f) \> w(e)-1$. Since $w'(e)$ is even and $w'(f)$ is odd, we must have $w'(f) \> w(e)$, and hence $f$ cannot belong to any MST of $G'$. $\square$

To check whether there is an MST of $G'$ that only uses edges of even length, compare the weight of a MST of $G'$ (with weight function $w'$) with the weight of a MST of the subgraph of $G'$ containing only the edges in $I$ (and weight function $w'$).

Since both these graphs contain $O(n)$ edges with weights between $0$ and $2n+1 = O(n)$, their MSTs can be computed in time $O(n)$.
> 5 votes

# Answer
### A simple algorithm

Here is the simplest and fastest algorithm to determine the MST of $G$ only uses edges with an integer weight. It runs in $O(E\\,\alpha(V))=O(n\\,\alpha(n))$ time.

1. Define weight function $w'\colon E\to \mathbb{N}$.
    * If $w(e)$ is an integer, $w'(e) =2w(e)$.
    * Otherwise, $w'(e) =2\lfloor w(e)\rfloor + 1$.

2. Sort all edges by their weights given by $w'$, which can be done in $O(n)$ time by a counting sort since weights are integers between $0$ and $2n+1$ and $|E|=2022n$.
3. Run Kruskal's algorithm on $(G, w')$ with the following tweak. When edge $e$ is about to be added, if $w(e)$ is not an integer (or, what is equivalent, $w'(e)$ is odd), return "No".
4. Return "Yes".

**Proof** of correctness. Since the set of weights in any MST is uniquely determined by the weighted graph,

* there exists one MST of $(G,w)$ that contains integer-weighted edges only $\iff$ every MST of $(G,w)$ contains integer-weighted edges only, and
* there exists one MST of $(G,w')$ that contains even-weighted edges only $\iff$ every MST of $(G,w')$ contains even-weighted edges only.

Suppose we have $\sigma$, a run of Kruskal's algorithm on $(G, w)$. We can make $\sigma'$, a run of Kruskal's algorithm on $(G,w')$ exactly like $\sigma$ except that step of sorting edges. Whichever edge is considered by $\sigma$ at some step, the same edge will be considered by $\sigma'$ at the corresponding step. In particular, $\sigma$ selects an integer-weighted edge $\iff$ $\sigma'$ selects an even-weighted edge. This is possible since Kruskal's algorithm only concerns about "the relative largeness" of weights and $w'$ is consistent with $w$, i.e., $w(e\_1)\le w(e\_2)$ $\iff$ $w'(e\_1)\le w'(e\_2)$.

The correspondence from $\sigma$ to $\sigma'$ means that every MST of $(G, w)$ contains integer-weighted edges only $\iff$ every MST of $(G,w')$ contains even-weighted edges only. $\quad\checkmark$

### What is wrong with your solution?

The step 2 of your solution is, I believe, the correct observation that
every MST only uses integer-weighted edges $\iff$ every non-integer-weighted edge is the unique heaviest edge of some cycle that contains it (the cycle property).

However, step 3 of your solution may classify whether a non-integer-weighted edge has the cycle property the wrong way, since the "heaviest" non-integer-weighted edge and the "heaviest" integer-weighted edge saved so far at step 1 might not be applicable to the cycle found at step 3. Even it is, that non-integer-weighted edge might be the unique heaviest edge on another cycle. As mentioned by AspiringMat, you will not be able to prove the classification of edges by your algorithm is correct.

I cannot see how we can improve a DFS so as to rectify the problem above.

One correct way is to use the simple algorithm above, which finds the lightest edge among all non-integer-weighted edges that do not have that cycle property ("lightest" and "cycle property" are with respect to $w'$, and "non-integer-weighted" is with respect to $w$) if there are such edges.
> 4 votes

# Answer
Here is one way to do it. First get all the integer edges $E\_{\mathbb{Z}}=\\{e\_1, ..., e\_k\\}$ in $O(m)=O(n)$ time. Since their weights are integers and bounded by $O(n)$, you can use bucket sort/radix sort to sort them in $O(n)$ time.

Now run Kruskal's algorithm on the sorted $E\_{\mathbb{Z}}$. This takes $O(n\alpha(n))$. So now you have a MST $T$ that only uses the integral edges.

To verify that $T$ is indeed an MST for $E$, loop over the remaining edges $e=(u,v)$ in $E-E\_{\mathbb{Z}}$ and verify that $w(u,v)$ is the maximum weight edge in the cycle in $T+\\{e\\}$ (since otherwise $T$ wouldn't be an MST). This step can be done in $O(n)$ by preprocessing $T$ and answering each query in $O(1)$ time.

So in total you get $O(n\alpha (n))$

More details on the Preprocessing step:

Here is how it works, for a given tree $T$, a line tree $L\_T$ satisfies the following rules:

1. $L\_T$ has the same vertices as $T$.
2. The maximum weight on the path between vertices $v$ and $u$ is the same for trees $T$ and $L\_T$
3. $L\_T$ is just a line (so we can choose the order of the vertices on the line and the weights of edges between neighbouring vertices, but nothing else).

If you have a Line tree, answering the query can be done in $O(n)$ time and $O(1)$ preprocessing using range maximum/minimum queries.

To construct a line tree, pick the maximum edge $e$ in $T$ and remove it. This breaks $T$ into two trees. Now recursively calculate the line tree for both subtrees, and join them to the endpoints of $e$. This can be done in $O(n)$ time if you return the line trees recursively as a linked list. You can prove by induction that the line tree generated satisfies all $3$ rules.
> 2 votes

---
Tags: algorithms, graphs, weighted-graphs, minimum-spanning-tree, depth-first-search
---


# Question
Title: Does this greedy algorithm minimize the sum of the diameters of two clusters?
Suppose given $2n$ points in the plane and we want to partition points into two clusters $C\_1$ , $C\_2$ such that each cluster contains exactly $n$ points and we want to minimize the sum of the diameters of two clusters. The diameter of a cluster is the maximum distance between any two points in that cluster.

I have a greedy algorithm for this problem:

Find diametral pair $(a,b)$ of $2n$ points, and then consider $a$ as the center of $C\_1$ and $b$ as the center of $C\_2$. Now, we make two lists $L\_a$ and $L\_b$ such that $L\_a$ contains all points sorted by increasing distance from $a$ and the other by increasing distance from $b$. I keep the first $n$ points in $L\_a$ that are closer to $a$ and remove others and then set $C\_1=L\_a$. I do the same for list $L\_b$ and then set $C\_2=L\_b$.

My question is, the above idea is optimal or not?

I think above idea return optimal solution because I can use Exchange argument as follows:

Suppose in the optimal partitions $C'\_{1}$ and $C'\_2$ isn't the same as $C\_1$ and $C\_2$ so there exists two points $c,d$ such that $c\in C\_1, d\in C\_2$ and $c\in C'\_2, d\in C'\_1$ but according to the algorithm if we exchange $c ,d$ we get $d\in C'\_2, c\in C'\_1$ so we achieve a new optimal solution that it's no worse than the optimal solution. So we get contradiction.

# Answer
> 2 votes
No, the algorithm does not return the optimal sets.

Consider the case of the $4$ points $P=\\{(0,0), (1,0), (0.5, 0.5), (0.5, 0.5)\\}$. The diametrical points are $(0,0)$ and $(1,0)$ with distance one. So your algorithm puts them in their own clusters. The closest other-point to $(0,0)$ is $(0.5, 0.5)$ so your algorithm returns the set $\\{(0,0), (0.5, 0.5)\\}$ and $\\{(1,0), (0.5, 0.5)\\}$ with cost $\sqrt{0.5^2+0.5^2} + \sqrt{0.5^2+0.5^2}=\sqrt{2}$.

However, the optimal sets are $\\{(0,0),(1,0)\\}$ and $\\{(0.5,0.5),(0.5,0.5)\\}$ with cost $1+0=1 \< \sqrt{2}$.

---
Tags: algorithms, computational-geometry, greedy-algorithms
---


# Question
Title: Space-efficient way to prove that a data has been processed before
Suppose that I have a stream of data packets in the form of unsigned 64 bit integers.

And I want to make sure that I am not processing the same packet content more than once.

A way of doing this would be using a hash map or dictionary, with the packets content as the key. And before processing a packet, I would need to check if the packet content already exists in the map. However doing this way would require at least `n * 8` bytes in memory where `n` is the number of unique integers in the stream.

Is there a more space-efficient way to do this?

# Answer
> 1 votes
If you aren't willing to tolerate any chance of error, then there is no more space-efficient way. You need enough space to store all of the data seen so far, so you need at least about $8n$ bytes (a little bit less, but not much less, for typical values of $n$).

If you're willing to tolerate a small chance of error, you could consider a Bloom filter. However, I suspect it will make errors in the "wrong direction" for your needs, as there is a small chance that a new packet could be wrongly treated as a duplicate.

# Answer
> 1 votes
As @pcpthm indicated in a comment, you can do much better than storing $64n$ bits when you get beyond a small number of entries. The bad news is that many traditional data structures for this (e.g. inverted lists) are not well-suited for dynamic update.

Since you only need to test membership, your best bet may be to use a *succinct* hash table. The key idea is to use an *invertible* hash function.

Depending on the particulars of the data, it may be appropriate to use the hash function $h(x) = x$, which is trivially invertible. But if it's not, you can easily construct invertible hash functions by using a Feistel network.

Suppose the value to be hashed is interpreted as two 32-bit integers $(l\_0, r\_0)$, and suppose you have a collection of (probably non-invertible; could be as simple as multiplication by a large prime) hash functions $h\_i$ which map 32-bit integers to 32-bit integers. Then define:

$$\begin{eqnarray\*} l\_{i+1} & = & r\_i \\ r\_{i+1} & = & l\_i \oplus h\_i(r\_i) \end{eqnarray\*}$$

(Note that $\oplus$ is bitwise exclusive or.)

Perform this for $k$ stages, and $(l\_k,r\_k)$ is your 64-bit hash value.

You can see why this hash function is invertible:

$$\begin{eqnarray\*} l\_i & = & r\_{i+1} \oplus h\_{i}(l\_{i+1}) \\ r\_i & = & l\_{i+1} \end{eqnarray\*}$$

So given all this, we now have an invertible hash function $h$. So now let's look at the actual hash table.

Imagine, for a moment, an idealised table where you store exactly $2^m$ entries in a table with $2^m$ buckets, and by pure luck, each bucket contains exactly one entry.

Traditionally, to test if $x$ is in this hash table, you would compute $h(x)$, obtain the bucket number as $b = h(x) \wedge (2^m-1)$ (where $\wedge$ is bitwise logical and), consult the $b$th bucket to see if it contains $x$.

If $h$ is invertible, you don't need to store $x$ in the bucket; it is sufficient to store $h(x)$ since if $h(x\_i) = h(x\_j)$, $x\_i = x\_j$.

However if you do that (and this is the *really* clever part), you don't need to store the $m$ lowest-order bits of $h(x)$ either, because that is implied by the fact that you are already looking in the right bucket. So you only need to store $h(x) \gg m$, which is $64-m$ bits per entry. So the total storage used by this data structure is $2^m(64-m)$ bits.

The theoretical minimum storage of any exact data structure is $\log { 2^{64} \choose 2^m }$ bits. Using Stirling's approximation

$$\log n! \approx n \log n - n \log e$$

we find that, if $2^m$ is much smaller than $2^{64}$, in the sense that $\log (2^{64} - 2^m) \approx 64$, then

$$\begin{eqnarray\*} \log { 2^{64} \choose 2^m } & \approx & \left(2^{64} \times 64 - 2^{64} \log e\right) - \left(2^m \times m - 2^m \log e\right) \\ & & - \left((2^{64} - 2^m) \log (2^{64} - 2^m) - (2^{64} - 2^m) \log e\right) \\ & = & 2^{64} \left(64 - \log (2^{64} - 2^m)\right) + 2^m \left(\log (2^{64} - 2^m) - m\right) \\ & \approx & 2^m \left(64 - m\right) \end{eqnarray\*}$$

So this representation is close to optimal.

Except, of course, that ideal hash tables where there is exactly one entry per bucket don't exist.

But there are variants where you can get quite close to full occupancy, such as cuckoo hashing. Note that hash table schemes based on probing (e.g. linear or quadratic probing) will *not* work here, because an entry must live in the bucket that corresponds to its hash value.

---
Tags: algorithms, data-structures, optimization, trees, space-complexity
---


# Question
Title: Number of products required to multiply polynomial coefficients
I am wondering about the claim from the book "Probability and computing" that the number of products required to multiply monomial coefficients is $\Theta(d^2)$, where $d$ is the number of monomials that forms the polynomial $$P(x) = (x-a\_1)(x-a\_2)\cdots(x-a\_d).$$ I think this answer is wrong and it takes $\Theta(2^d)$ instead.

Could someone explain this, please?

# Answer
> 11 votes
Consider the following algorithm:

* Start with $P = 1$.
* For $i=1,\ldots,d$: replace $P$ with $P \cdot (x - a\_i)$.

At step $i$, the polynomial $P$ has degree $i-1$, and so we need to compute $$ \sum\_{j=0}^{i-1} p\_j x^j (x - a\_i) = \sum\_{j=1}^i p\_{j-1} x^j - \sum\_{j=0}^{i-1} a\_i p\_j x^j = -a\_i p\_0 + \sum\_{j=1}^{i-1} (p\_{j-1} - a\_i p\_j) x^j + p\_{i-1} x^i. $$ As you can see, this requires $i-1$ products. Summing over all $i$, we obtain $\frac{d(d-1)}{2} = \Theta(d^2)$ products.

In fact, using FFT we can improve on this. FFT multiplies two degree $m$ polynomial using only $\Theta(m\log m)$ products. A straightforward divide and conquer approach results in the following recurrence for the number of products: $$ T(d) = 2T(d/2) + \Theta(d\log d). $$ The solution is $T(d) = \Theta(d\log^2 d)$.

# Answer
> 5 votes
Two polynomials of degree n, giving by their coefficients, can be multiplied in O(n^2) using the trivial algorithm and in O (n log n) using FFT.

Now you need more than one multiplication. You start with n first degree polynomials, you get n/2 2nd degree polynomials, then n/4 4th degree polynomials, etc. All those multiplications will be O(n^2) using the primitive algorithm and O(n log^2 n) using FFT.

I think a bigger problem may be that the coefficients get very large very fast, so a multiplication is not a primitive operation

Also the FFT method isn’t very efficient for small degrees so you would multiply small degree polynomials in pairs using the naive algorithm then switch to FFT when it becomes more efficient.

---
Tags: complexity-theory
---


title: Can element occur in a CNF formula?

text:
# Question
Title: Can element occur in a CNF formula?
For example, is $(X \vee 1)$ a valid formula in conjunctive normal form (CNF)?

If yes, then I would have to consider such formulas when trying to prove a statement about all CNF formulas.

# Answer
> 1 votes
$X \vee 1$ is not a CNF formula because $1$ is neither a variable nor the negation of a variable. Both $X$ and $\neg X$ are valid CNF formulas, however.

---
Tags: boolean-algebra
---


# Question
Title: Hints for efficient computation of the maximum length of a binary sequence
Given a positive integer $n$ I would like to compute $f(n)$, the maximum possible length of a binary sequence such that any substring of it (subsequence with consecutive elements), of length $n$, never repeats.

For example, with $n = 1$, I have a maximum length of $2$, obtained with $(0, 1)$ or $(1, 0)$.

For $n=2$ I think the maximum should be $5$, which I can obtain with the sequence $(0,0,1,1,0)$.

Similarly, I can get a length of at least $9$ for $n=3$ and $15$ for $n=4$ with the sequences $(0,0,0,1,0,1,1,0,1)$ and $(0,0,0,0,1,0,0,1,1,0,1,1,1,0,1)$ respectively.

Obviously I can write an exhaustive search with a number of operations proportional to $2^{f(n)}$, but this starts to be impractical already for $n=6$.

Any hint for reducing the time complexity? Is it possible in the first place?

# Answer
I think that $f(n) = 2^n + n - 1$. To construct a word of length $f(n)$ with no repeated substring of length $n$, pick $\beta\_n$ the $n$-th de Bruijn sequence over the alphabet $\\{0, 1\\}$ (of length $2^n$), and add the first $n-1$ letters of $\beta\_n$ at the end.

Here's some examples:

* for $n = 2$, pick $(0, 0, 1, 1, 0)$;
* for $n = 3$, $(0,0,0,1,0,1,1,1,0,0)$ of length $10$ (and not $9$ as you suggested);
* for $n = 4$, $(0,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1,0,0,0)$ of length $19$ (and not $15$ as you suggested).

The construction of $\beta\_{n+1}$ is obtnained by constructing a directed graph $G\_n = (V\_n, E\_n)$ such that:

* $V\_n = \\{0,1\\}^n$ (vertices are words of length $n$);
* for $u=u\_1u\_2…u\_n, v=v\_1v\_2…v\_n\in V\_n$, there is an edge labelled by $v\_n$ from $u$ to $v$ if and only if $u\_2…u\_n = v\_1…v\_{n-1}$.

A candidate (there are multiple possibilities) for the word $\beta\_{n+1}$ is then the word obtained by reading edge's labels in an eulerian cycle.

To prove that $f(n)$ is indeed equal to $2^n+n-1$:

* $f(n) \geqslant 2^n+n-1$ since the word constructed above has no repeated substring of length $n$ (because $\beta\_n$ has no repeated circular substring of length $n$);
* $f(n) \leqslant 2^n+n-1$ since there are $2^n$ different substring of length $n$, so there cannot be more than $2^n$ positions in the word that can be the beginning of a substring of length $n$.
> 1 votes

---
Tags: algorithms, time-complexity, combinatorics, substrings, subsequences
---