# Question
Title: Density of uniform distribution over two disjoint squares
A probability distribution $P$ over $X \times \\{0, 1\\}$. $P$ can be defined in term of its marginal distribution over $X$ , which we will denote by $P\_X$ and the conditional labeling distribution, which is defined by the regression function $$ \mu(x) = P\_{ (x,y) \sim P} \[y = 1 \mid x\] $$ Consider a 2-dimensional Euclidean domain, that is $X = \mathbb R^2$, and the following process of data generation: The marginal distribution over $X$ is uniform over two square areas $\[1, 2\] \times \[1, 2\] \cup \[3, 4\] \times \[1.5, 2.5\]$. Points in the first square $Q\_1 = \[1, 2\] \times \[1, 2\]$ are labeled 0 (blue) and points in the second square $Q\_2 = \[3, 4\] \times \[1.5, 2.5\]$ are labeled 1 (red).

Describe the density function of $P\_X$, and the regression function, Bayes predictor and Bayes risk of $P$.

In the image, I have defined the Probability density function. I am having trouble in figuring out the pdf of this function in 2 dimensional space.

# Answer
The density $p\_R$ of the uniform distribution over a rectangle $R$ is given by $p\_R(x) = 0$ if $x \notin R$, and $p\_R(x) = 1/\mathit{area}(R)$ otherwise. Indeed, up to scaling the distribution must have this form, and the choice $1/\mathit{area}(R)$ ensures that $p\_R$ is a distribution.

In your case, you have a mixture of two such distributions: with probability $1/2$ you take a uniform point in $\[1,2\] \times \[1,2\]$, and with probability $1/2$ you take a uniform point in $\[3,4\] \times \[1.5,2.5\]$. The density function of the mixture is the average of the density functions of the individual distributions.
> 1 votes

---
Tags: machine-learning, learning-theory, bayesian-statistics
---


# Question
Title: In the beginning, computable functions were always total, but when where the partial functions included
The modern definition of computable functions $f\colon \mathbb N \to \mathbb N$ as given on Wikipedia quite naturally describes partial functions, and not just total functions. Now I am reading some historical references, and before and around the 1930's people just seemed to be concerned with total computable function, so that when they talk about computable functions they always mean total functions.

As an example let me cite An unsolvable problem of elementary number theory by A. Church, here he just considers total functions right from the start, and when he introduces $\lambda$-definable, or recursive functions, he also just considers total function.

So at what point, and why, people dropped the assumption that computable functions always have to be total?

# Answer
> 3 votes
The Stanford Encyclopaedia of Philosophy has a summary of the history of recursive functions. In particular, in Section 1.8 we can read that Stephen Kleene explicitly defined the partial recursive functions, and showed them to be equivalent to several other notions of computable functions, in a series of papers between 1936 and 1954. For example, already his 1936 paper General recursive functions and natural numbers introduces the unbounded search operator which leads to partial functions (when the search does not find anything).

# Answer
> 0 votes
My guess is 1965-1971, due to the introduction of analysis of algorithm runtimes. See below for reasoning.

I'm not great with the history here, but as I understand it what happened is that people switched from considering

* functions $\mathbb N \rightarrow \mathbb N$ (find the nth number in the increasing sequence). In this definition, the natural question to ask is, "can we enumerate this sequence", and how many steps does it take it output each digit?
* To considering functions $\mathbb N \rightarrow \\{YES, NO\\}$. In this definition, the natural question is "how hard is it to calculate the answer"? **Note that it's now much easier to consider partial functions.**

When this switch happened, I'm less sure. Turing was using sequences in 1936 to calculate digits. Stearns and Hartmanis in 1965 still were, in their paper that introduced asymptotic analysis of algorithms. Steven Cook in 1971 was not. I assume these were typical of the time (that everyone publishing that year used the same convention). Given the (very!) short gap to a switch after a long stability, I can only assume that decision problems are more natural to think about for complexity analysis, and this caused the change.

---
Tags: formal-languages, computability
---


# Question
Title: Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$
Does there exist a Deterministic pushdown automata for the language $L=\\{ a^ib^j| i \neq 2j+1, i,j\>0\\}$ where $\Sigma = \\{a,b\\}$

I have tried to find a pushdown automata and it turned out to be a non-deterministic one.

# Answer
> 1 votes
Yes, here the idea of one with three states. I don't know stuff formally enough to write tuples.

* Keep track of the parity of 'a's you read in two states.
* If you read 'aa', push A on the stack
* When you hit b, you better be on odd parity
* Pop 'A' for every 'b' you read
* At the end of the input, succeed if the stack is exactly empty.

This accepts only when i == 2j+1. Then, invert the last step, while keeping the requirement to keep it in the format $\\{a^ib^j\\}$ to get the version below. This requires adding one more state.

This might be a valid formal version, or it might not:

```
state,      input (z=end-of-string),
               top of stack (E=empty, *=anything),
                  action
q_a_even,   a, *, do nothing and transition to q_a_odd
q_a_even,   b, *, transition to q_b_ok
q_a_even,   z, *, succeed
q_a_odd,    a, *, push 'A' and transition to q_a_even
q_a_odd,    b, E, transition to q_b_ok
q_a_odd,    b, A, pop and transition to q_b_danger
q_a_odd,    z, *, succeed
q_b_danger, a, *, fail
q_b_danger, b, E, succeed
q_b_danger, b, A, pop and transition to q_b_danger
q_b_danger, z, A, succeed
q_b_danger, z, E, fail
q_b_ok,     a, *, fail
q_b_ok,     b, *, transition to q_b_ok
q_b_ok,     z, *, succeed

```

---
Tags: formal-languages, automata, pushdown-automata
---


# Question
Title: Finding the area of a rectangle in python
Q: Standard input consists of exactly four integers, first x1 and y1, the coordinates of the bottom-left corner of a rectangle, then x2 and y2, the coordinates of the top-right corner. Write a Python script named area-of-rectangle.py which outputs the rectangle’s area.

I'm SO stuck and have no clue what I'm doing. I wrote this

x1 = int(input()) y1 = int(input()) x2 = int(input()) y2 = int(input()) bottom\_left = (x1 + y1) top\_right = (x2 + y2) area = bottom\_left * top\_right print(area)

IT'S ALWAYS WRONG. Please help :(

# Answer
To calculate the area of a rectangle on a coordinate system, you need the length between x1 and x2, and the length between y1 and y2.

```
x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())

xDiff = abs(x1 - x2) # Using absolute value to ignore negatives
yDiff = abs(y1 - y2)

area = xDiff * yDiff

```

Edit: Forgot to mention, if x2 is always greater than x1, and y2 is always greater than y1, instead you can just use `xDiff = x2 - x1` and `yDiff = y2 - y1`
> 1 votes

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


title: Forest characterization

text:
# Question
Title: Forest characterization
> Prove that each property below characterizes forests...

> a. every induced subgraph has a vertex of degree at most one.

When proving a characterization, do we have to prove both directions, like an if and only if, or does it suffice to prove only one direction?

# Answer
"Characterizes" means you must prove "if and only if".
> 8 votes

# Answer
"Characterize" means you must prove both directions.

However, you can be more efficient with multiple characterizations: proving A implies B implies C implies A shows all three are equivalent, because implication is transitive. Examples in practice:

Equivalence of induction, strong induction, and well-ordering

Equivalence of 6 different characterizations of the exponential function
> 2 votes

# Answer
Welcome to CS.SE :)

Suppose $G$ is a forest. Then so is every subgraph $G\[X\]$ induced by some $X \subseteq V(G)$, and clearly every forest has a node of degree at most one (either an isolated vertex or some leaf).

Now suppose that $G$ is a graph such that every subgraph $G\[X\]$ induced by some $X \subseteq V(G)$ has a vertex of degree at most one. Then $G$ cannot contain a cycle, otherwise the vertices of said cycle would induce a subgraph where every vertex has degree at least $2$ (in a cycle, every vertex is adjacent to its two neighbors). As $G$ is acyclical, it must be a forest.

Putting the two pieces together, we get your desired result.
> 1 votes

---
Tags: graphs, theory
---


# Question
Title: Why does the BFR (Bradley, Fayyad and Reina) algorithm assume clusters to be normally distributed around its centroid?
I'm following a course on data mining based on the lectures from Stanford University and the book *Mining of massive datasets*.

On the topic of clustering, the **BFR** algorithm is explained with this video.
I understand how the algorithm works, but I am unclear on the reason why the algorithm makes the *strong* assumption that each cluster is normally distributed around a centroid in Euclidian space.

The video explains that the assumption implies that clusters look like axis-aligned ellipses, which is understandable as the dimensions must be independent.
I've watched the video a few times, and read the section in the book (freely downloadable using the first link) on pages 257-259, but I'm unable to grasp why that assumption is made, and why it has to be made.

Could someone explain this for me?

# Answer
Roughly, the algorithm needs to estimate the probability to assign a point the correct cluster.

So the algorithm add *P* to a cluster if it is very unlikely that, after all the points have been processed, some other cluster centroid will be found to be nearer to *P*.

So the algorithm measure the probability that, if *P* belongs to a cluster, it would be found as far as it is from the centroid of that cluster. To do that, it assumes that the clusters contain normally distributed points aligned with the axes of the used space.
> 3 votes

---
Tags: data-mining, clustering
---


# Question
Title: Is C++ considered a language with high or low orthogonality?
I'm looking to make a comparison of regularity in languages - specifically orthogonality.

If I were to say Java is weak in terms of orthogonality and Haskell stronger, where would C++ sit and why?

# Answer
By many standards, Java would not be considered weak in this respect. Java was not one of the first-generation languages. By the time it was developed, quite a few things were known about language design, and the lessons learned do show. For instance, it's pretty easy to parse.

C++ is quite a bit older, as it shares a history with C. As a result, C++ has the a preprocessor language that is quite distinct from the rest of the language. But unlike C, C++ has effectively added a third language. The C++ template system is Turing-complete, and effectively a language of its own. (Although recent C++ versions have reduced this gap).

The result? This bit of valid C++ code:

```
#define A 0
enum { b = 1};
const int c = 2;
constexpr int d = 3;

```

But note that this process is a result of the success. The most orthogonal languages are those defined as a theoretical exercise, never used, and therefore never adapted to be useful for a wide range of tasks.
> 2 votes

---
Tags: c++
---


# Question
Title: Can Edge Belong to a cycle if it is part of multiple BFS products
Given a simple connected undirected graph. with V vertices and E edges.
Let e be some edge from E.

If I perform |V| **different** BFS runs - meaning started each time from a different vertex - and in every run e is part of the Spanning tree produced from the run.
Can it be belonging to some cycle?

The multiple answers I have to choose from are:

1. it does not belong to any cycle
2. e might belong to a cycle but if it belongs to an odd-length cycle, then it must belong to an even-length cycle.
3. e might belong to a cycle but if it belongs to an even-length cycle, then it must belong to an odd-length cycle.
4. None of the above.

My claim is, because BFS is deterministic and because we performed |V| BFS on the graph, each time from a different vertex. if e was on some cycle, and it doesn't matter even-length or odd length, one of the vertices on the cycle would have caught up with it and remove it.

The only way that it belongs to every Spanning tree, is if it's un replaceable, meaning it's the only thing connecting two vertices.

Am I right? is there any formal proof th

# Answer
Let's show first that such an edge might belong to a cycle, by considering the case of a square $ab,bc,cd,da$. We will show that $ab$ could belong to BFS trees starting at arbitrary vertices. This is clear if BFS is started from $a$ or from $b$. If BFS is started from $c$, it could enqueue $a,d$ in this order; dequeue $a$; then enqueue $b$. Similarly, if BFS is started from $d$, it could enqueue $b,c$ in this order; dequeue $b$; then enqueue $a$.

In contrast, if an edge $e=(x,y)$ only belongs to odd cycles, then it cannot belong to all BFS trees. Indeed, take a shortest cycle containing $e$, and let $z$ be the vertex opposite $e$. If we start BFS from $z$, then $x,y$ are both enqueued before any of them is dequeued, since $d(z,x) = d(z,y)$ (try it on a triangle).
> 3 votes

# Answer
As Yuval pointed out, there is some ambiguity of the original exercise as the enqueueing order of the neighbors of a node is not stipulated by the definition of a breadth-first-search (BFS).

**Proposition 1**: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. If $e$ is a part of a cycle, then there is a BFS of $G$ that produces a BFS tree that does not contain $e$. (If $e$ is not part of any cycle, then it is a bridge of $G$ and, hence, appears on every spanning tree.)

Since this proposition is, apparently, clear to the OP, no formal proof will be given here.

If we stick to this (indeterministic) version of BFS, the answer to the exercise should be choice 1, "it does not belong to any cycle".

---

Let us add some context so that that exercise becomes more interesting.

Suppose that for every node, the order of its children to be enqueued in a BFS is fixed beforehand. Now, it can happen that an edge that is part of a cycle can be part of the spanning tree produced from each of $n$ BFS runs. For example, graph $G\_1$ with $C\_0=\[1,3\]$, $C\_1=\[0,2\]$, $C\_2=\[1,3\]$, $C\_3=\[2,0\]$, where $C\_i$ is the list of neighbors of node $i$ in the enqueueing order. The following lists shows the edge $\overline{1,2}$ is always part of the BFS tree produced.

* The BFS starting from node 0 produces the tree with edges $\overline{0, 1}$, $\overline{0,3}$, $\overline{1,2}$.
* The BFS starting from node 1 produces the tree with edges $\overline{1, 0}$, $\overline{1,2}$, $\overline{0,3}$.
* The BFS starting from node 2 produces the tree with edges $\overline{2, 1}$, $\overline{2,3}$, $\overline{1,0}$.
* The BFS starting from node 3 produces the tree with edges $\overline{3, 2}$, $\overline{3,0}$, $\overline{2,1}$.

We have the following proposition.

**Proposition 2**: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. Suppose we have selected an enqueueing order for the neighbors of each node. If a BFS of $G$ will always include $e$, then $e$ is either not part of any cycle or $e$ is a part of cycle of even length.

**Proof**. For the sake of contradiction, suppose that there is a cycle of odd length that contains $e$ and every cycle that contains $e$ is of odd length.

Consider $\mathcal C$, one of the shortest cycles that contains $e$. Since the length of $\mathcal C$ is odd, we can select $v\_0$, a node of $\mathcal C$ that is "opposite" to $e$, i.e, the cycle is $v\_0, v\_1, \cdots, v\_k, v\_{k+1},\cdots, v\_{2k-1}, v\_{2k}, v\_0$ for some $k$ and $v\_i$'s, where $\overline{v\_k,v\_{k+1}}$ is edge $e$. Since any cycle containing $e$ must be longer than $\mathcal C$, we have, $$\text{distance}(v\_0, v\_{k}) = \text{distance}(v\_0, v\_{k+1}) = k.$$

Let us run BFS from node $v\_0$. Let tree $T$ be the BFS tree produced. We claim $T$ does not contain $e$. Otherwise, suppose $T$ does contain $e$. WLOG, suppose $v\_k$ is nearer to $v\_0$ than $v\_{k+1}$. Since $T$ is a shortest-path tree from $v\_0$, we have

$$\text{distance}(v\_0, v\_{k+1}) = \text{distance}(v\_0, v\_{k}) + \text{distance}(v\_k, v\_{k+1})=\text{distance}(v\_0, v\_{k}) + 1,$$

which contradicts previous equality. This contradiction shows that $T$ does not contain $e$. That, however, contradicts the given condition that every BFS tree contains $e$. $\ \checkmark$

---

With respect to proposition 2, the answer to the exercise should be choice 3, "$e$ might belong to a cycle but if it belongs to an odd-length cycle, then it must belong to an even-length cycle.", if the context, i.e. the way in which BFS is supposed to run, implies that the enqueueing order of neighbors of a node is fixed before all runs.
> 5 votes

---
Tags: trees, minimum-spanning-tree, breadth-first-search
---


# Question
Title: Efficient way to calculate the maximum curvature of a cubic spline
I've got a 2D **cubic spline** (Bézier) and I have the polygon-line that's a discretization of that spline.

Is there an efficient and simple to implement a way to calculate the **maximum curvature** of the spline either by using its smooth representation or the discrete poly-line? It doesn't have to be exact since it's for a game, an error around 10% would be totally acceptable.

Different wording: I would like to know: if I'd drive a car driving at constant speed along the spline, what would be the maximum degree I had to turn the steering wheel to stay on it?

# Answer
> 2 votes
Step 1: Express the points on the spline parametrically, so the spline is the set of points of the form $(x(t),y(t))$, where $t$ is a parameter. Here $x(t)$ represents the $x$-coordinate (as a function of the parameter $t$) and $y(t)$ represents the $y$-coordinate. Since this is a cubic spline, you can find functions $x(t),y(t)$ that are cubic polynomials with known coefficients that provide this parametric expression.

Step 2: Use the formula on Wikipedia for computing the curvature, given a parametric representation of the curve. This gives you a formula for the curvature as a function of $t$, namely, $\kappa(t)$. Note that since $x(t)$ and $y(t)$ are cubic polynomials, you can explicitly compute their first and second derivatives, so you can analytically compute an explicit expression for $\kappa(t)$, i.e., for the curvature as a function of $t$.

Step 3: Find the value of $t$ that maximizes $\kappa(t)$. Note that we are now dealing with a function $\kappa : \mathbb{R} \to \mathbb{R}$, i.e., we are in the one-dimensional case. Thus, we can find the maximum numerically using any of a number of methods: gradient descent, Newton's method, or a number of other methods.

Alternatively, you can analytically compute the derivative of $\kappa(t)$, and then solve the equation $\kappa'(t)=0$ for $t$. This might allow an analytic solution that identifies a list of candidate maxima of $\kappa(t)$. Make sure to also check the endpoints (the lower and upper bounds for $t$). Evaluate $\kappa$ at each candidate and pick the one that makes the value of $\kappa(t)$ as large as possible.

# Answer
> 2 votes
I followed D.W.'s approach and found a solution as follows:

In order to use an online derivative calculator, I expressed the cubic spline with points `P0`, `P1`, `P2` and `P3` using variables `a` through `h`:

```
P0 = (a, e)
P1 = (b, f)
P2 = (c, g)
P3 = (d, h)

```

The x-y-coordinates and their derivatives are as follows:

```
x(t)   = a*(1-t)^3+3*b*(1-t)^2*t+3*c*(1-t)*t^2+d*t^3
x'(t)  = 3*((d-3*c+3*b-a)*t^2+2*(c-2*b+a)*t+(b-a))
x''(t) = 6*((d-3*c+3*b-a)*t+(c-2*b+a))

y(t)   = e*(1-t)^3+3*f*(1-t)^2*t+3*g*(1-t)*t^2+h*t^3
y'(t)  = 3*((h-3*g+3*f-e)*t^2+2*(g-2*f+e)*t+(f-e))
y''(t) = 6*((h-3*g+3*f-e)*t+(g-2*f+e))

```

In order to keep the equations in a more compact form, I introduced the following substitutions:

```
m = d-3*c+3*b-a
n = c-2*b+a
o = b-a
p = h-3*g+3*f-e
q = g-2*f+e
r = f-e

```

This leads to the following simplified derivatives:

```
x'(t)  = 3*(m*t^2+2*n*t+o)
x''(t) = 6*(m*t+n)
y'(t)  = 3*(p*t^2+2*q*t+r)
y''(t) = 6*(p*t+q)

```

Using the mentioned curvature equation and the online derivative calculator I obtained the following expression with its derivative:

```
k(t)   = (x' * y'' - y' * x'') / (x'^2 + y'^2)^(3/2)
       = ((3*(m*t^2+2*n*t+o)) * (6*(p*t+q)) - (3*(p*t^2+2*q*t+r)) * (6*(m*t+n))) / ((3*(m*t^2+2*n*t+o))^2 + (3*(p*t^2+2*q*t+r))^2)^(3/2)
k'(t)  = (-18*m*(p*t^2+2*q*t+r)+18*p*(m*t^2+2*n*t+o)-18*(m*t+n)*(2*p*t+2*q)+18*(2*m*t+2*n)*(p*t+q))/(9*(p*t^2+2*q*t+r)^2+9*(m*t^2+2*n*t+o)^2)^(3/2)-(3*(18*(p*t+q)*(m*t^2+2*n*t+o)-18*(m*t+n)*(p*t^2+2*q*t+r))*(18*(2*p*t+2*q)*(p*t^2+2*q*t+r)+18*(2*m*t+2*n)*(m*t^2+2*n*t+o)))/(2*(9*(p*t^2+2*q*t+r)^2+9*(m*t^2+2*n*t+o)^2)^(5/2))

```

Unfortunately, the online tool is not able to yield roots for this expression. But if you look closely (preferably at some rendered representation), you'll find a difference with almost identical denominators `(...)^(3/2)` and `2*(...)^(5/2)`. Multiplying the left-hand side with `2*(...)` yields a common denominator and the following nominator, which should be set to zero:

```
2*(-18*m*(p*t^2+2*q*t+r)+18*p*(m*t^2+2*n*t+o)-18*(m*t+n)*(2*p*t+2*q)+18*(2*m*t+2*n)*(p*t+q))*(9*(p*t^2+2*q*t+r)^2+9*(m*t^2+2*n*t+o)^2) - (3*(18*(p*t+q)*(m*t^2+2*n*t+o)-18*(m*t+n)*(p*t^2+2*q*t+r))*(18*(2*p*t+2*q)*(p*t^2+2*q*t+r)+18*(2*m*t+2*n)*(m*t^2+2*n*t+o)))

```

This tool can simplify this expression and yields the following polynomial in text form:

```
  ((1296*m*p^2+1296*m^3)*q-1296*n*p^3-1296*m^2*n*p)*t^5
+ ((1620*m*p^2+1620*m^3)*r+3240*m*p*q^2+(3240*m^2*n-3240*n*p^2)*q-1620*o*p^3+((-1620*m^2*o)-3240*m*n^2)*p)*t^4
+ ((5184*m*p*q+1296*n*p^2+6480*m^2*n)*r+1296*m*q^3-1296*n*p*q^2+((-6480*o*p^2)-1296*m^2*o+1296*m*n^2)*q+((-5184*m*n*o)-1296*n^3)*p)*t^3
+ (1296*m*p*r^2+(1944*m*q^2+6480*n*p*q-1296*o*p^2+1296*m^2*o+8424*m*n^2)*r-8424*o*p*q^2-6480*m*n*o*q+((-1296*m*o^2)-1944*n^2*o)*p)*t^2
+ (2592*n*p*r^2+(3888*n*q^2-2592*o*p*q+2592*m*n*o+3888*n^3)*r-3888*o*q^3+((-2592*m*o^2)-3888*n^2*o)*q)*t
+ (-324*m*r^3+(1944*n*q+324*o*p)*r^2+((-1944*o*q^2)-324*m*o^2+1944*n^2*o)*r-1944*n*o^2*q+324*o^3*p)

```

Now you can choose any solver for 5th-degree polynomials. In my case, I could easily use the `roots` function from Python's NumPy:

```
poly = [
    (1296*m*p**2+1296*m**3)*q-1296*n*p**3-1296*m**2*n*p,
    (1620*m*p**2+1620*m**3)*r+3240*m*p*q**2+(3240*m**2*n-3240*n*p**2)*q-1620*o*p**3+((-1620*m**2*o)-3240*m*n**2)*p,
    (5184*m*p*q+1296*n*p**2+6480*m**2*n)*r+1296*m*q**3-1296*n*p*q**2+((-6480*o*p**2)-1296*m**2*o+1296*m*n**2)*q+((-5184*m*n*o)-1296*n**3)*p,
    1296*m*p*r**2+(1944*m*q**2+6480*n*p*q-1296*o*p**2+1296*m**2*o+8424*m*n**2)*r-8424*o*p*q**2-6480*m*n*o*q+((-1296*m*o**2)-1944*n**2*o)*p,
    2592*n*p*r**2+(3888*n*q**2-2592*o*p*q+2592*m*n*o+3888*n**3)*r-3888*o*q**3+((-2592*m*o**2)-3888*n**2*o)*q,
    -324*m*r**3+(1944*n*q+324*o*p)*r**2+((-1944*o*q**2)-324*m*o**2+1944*n**2*o)*r-1944*n*o**2*q+324*o**3*p,
]
roots = np.roots(poly)

```

The resulting list contains all values `t`, where the curvature `k(t)` is at a local minimum or maximum. There could, however, be imaginary solutions that should be ignored.

Example:

Regarding D.W.'s hint about endpoints: I'm not sure if the curvature *could* be extrem at these points. But if in doubt, make sure to check the endpoints explicitly.

---
Tags: algorithms, numerical-algorithms
---


# Question
Title: Is it possible to make data structure that will find MEX and support modification queries
Let's say we have given array of $n$ elements, now we want to create data structure that will allow us to get the MEX of its elements, MEX (**M**inimum **EX**cluded) meaning the smallest positive integer that is not present in the set. More info from wikipedia. The data structure should also support insert and remove elements from itself.

In other words, we have given a multiset with $n$ elements, we want to find its MEX, but we should support removing and adding elements.

What I was thinking was that we should first process the elements on some way, and then when adding new element in the set we should check if it is equal to the MEX, but there are many cases to worry about, so I couldn't come to complete solution.

The data structure should support both the queries/updates in $O(\log N)$ or similar time-complexity classes.

# Answer
> 3 votes
**Method 1**
You can also use a bit trie — this is a trie made of bits of your numbers, thus it is represented as a binary tree (since there are only two types of bits — 0 and 1), and its depth is $\mathcal{O}{(log(n))}$.

When you add a number, you mark the vertex that representing this particular number as a full binary tree, and then you recursively go over its parents marking them as full binary trees if their left and right children are both full binary trees as well.

When you remove a number, you unset the "full binary tree" mark and do so for all its parents.

When you want to get MEX, you should do the DFS towards $x$, avoiding visiting subtrees which are marked as full (because there are no free values in such subtrees) and attempt to visit a left subtree first if you are allowed to by the x restriction.

```
class MEX {
  struct MEXNode {
    MEXNode *children[2];
    bool is_full = false;
    int cnt = 0;

  public:
    MEXNode() {
      children[0] = nullptr;
      children[1] = nullptr;
    }
  };
private:

  inline MEXNode *nonnull(MEXNode *& n) {
    if (!n) n = new MEXNode();
    return n;
  }

  void insert(int val, int level, MEXNode *n) {
    if (level == -1) {
      n->cnt++;
      n->is_full = true;
      return;
    }

    int cur_bit = (val & (1 << level)) >> level;
    insert(val, level - 1, nonnull(n->children[cur_bit]));

    n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
    n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
  }

  // Remove an integer from the set
  void remove(int val, int level, MEXNode *n) {
    if (level == -1) {
      n->cnt--;
      n->is_full = n->cnt > 0;
      return;
    }

    int cur_bit = (val & (1 << level)) >> level;
    remove(val, level - 1, nonnull(n->children[cur_bit]));

    n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
    n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
  }

  // Find the minimum element >=x that isn't present in the set
  int get(int val, int level, MEXNode *n) {
    if (n->is_full) {
      return -1;
    } else if (n->cnt == 0) {
      return val;
    }

    int cur_bit = (val & (1 << level)) >> level;
    int ans = get(val, level - 1, nonnull(n->children[cur_bit]));
    if (cur_bit == 0 && ans == -1) {
      ans = get((val >> level << level) | (1 << level), level - 1, nonnull(n->children[1]));
    }

    return ans;
  }

  MEXNode root_node;
public:

  void insert(int x) {
    insert(x, 31, &root_node);
  }
  void remove(int x) {
    remove(x, 31, &root_node);
  }
  int get(int x) {
    return get(x, 31, &root_node);
  }
};

```

**Method 2**
Create a set of intervals $S$. If the interval $\[l, r\]$ is present in $S$, that means that the elements $l, l + 1, l + 2, \dots , r$ are in $S$.

Adding an element $x$ is handled like this: If $\[whatever, x - 1\]$ is present in the set, remove it and add $\[whatever, x\]$. Likewise, if $\[x + 1, whatever\]$ is in the set, remove it and add $\[x, whatever\]$.

Removals are handled in this way: Find the interval containing x. Split it into two intervals $\[start, x - 1\]$, and $\[x + 1, end\]$.

MEX queries are handled similarly: Find the interval containing $x$ and output $end + 1$. This can be implemented using 2 `std::set<std::pair<int, int>>` in C++.
The first set indexes pairs by the first element (i.e. left end), and the second one by their second element (i.e. right end)

```
class MEX {
  typedef std::pair<int, int> interval;
  std::set<interval> s[2];
  std::multiset<int> values;
  void insert_pair(interval p) {
    auto[x, y] = p;
    if (x > y) std::swap(x, y);
    s[0].insert({x, y});
    s[1].insert({y, x});
  }
  void remove_pair(interval p) {
    auto[x, y] = p;
    if (x > y) std::swap(x, y);
    s[0].erase({x, y});
    s[1].erase({y, x});
  }

  std::optional<interval> is_end(int x, bool left) {
    int idx = left;
    auto it = s[idx].lower_bound({x, 0});
    if (it != s[idx].end() && it->first == x)
      return *it;
    else
      return std::nullopt;
  }

 public:
  void insert(int x) {
    bool ok = values.find(x) == values.end();
    values.insert(x);
    if (!ok) return;
    auto p1 = is_end(x - 1, true);
    auto p2 = is_end(x + 1, false);
    if (p1 && p2) {
      interval i = {p1->second, p2->second};
      remove_pair(*p1);
      remove_pair(*p2);
      insert_pair(i);
    } else if (p1 && !p2) {
      interval i = {p1->second, x};
      remove_pair(*p1);
      insert_pair(i);
    } else if (!p1 && p2) {
      interval i = {x, p2->second};
      remove_pair(*p2);
      insert_pair(i);
    } else if (!p1 && !p2) {
      interval i = {x, x};
      insert_pair(i);
    }
  }
  void remove(int x) {
    values.erase(values.find(x));
    if (values.find(x) != values.end()) return;
    auto it = s[1].lower_bound({x, 0});
    if (it->first != x && it->second != x) {
      interval p1 = {it->second, x - 1};
      interval p2 = {x + 1, it->first};
      remove_pair(*it);
      insert_pair(p1);
      insert_pair(p2);
    } else if (it->first != x && it->second == x) {
      interval p = {x + 1, it->first};
      remove_pair(*it);
      insert_pair(p);
    } else if (it->first == x && it->second == x) {
      remove_pair(*it);
    } else if (it->first == x && it->second != x) {
      interval p = {it->second, x - 1};
      remove_pair(*it);
      insert_pair(p);
    }
  }
  int get(int x) {
    if (values.find(x) == values.end()) return x;
    auto it = s[1].lower_bound({x, 0});
    return it->first + 1;
  }
};

```
* Usage

```
MEX mex;
mex.insert(int);
mex.remove(int);
mex.get(int); // Find the minimum element >=x that isn't present in the set

```

---
Tags: data-structures, optimization
---


# Question
Title: Generating topological sequence from DAG with additional "not appearing before" constraints
DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG?

Is there an algorithm for generating topological sequence from DAG with such constraint? Or maybe I can transform the DAG with this constraint?

# Answer
Let's say the 2 nodes in question are node x and node y. If you want node x to not appear before node y, then, as Yuval Filmus mentioned in the comments, you want it to appear after y.

What does this mean?

If x is a predecessor of y, then the graph would not be valid, because by definition, a topological sort puts all predecessors before their childrens.

If x is not a predecessor of y, you could **add an auxiliary edge from x to y**. This ensures that x will definitely appear before y, again by definition of a topological sort.

Followup:

Adding an auxiliary edge may cause some problems, here are some possible solutions to resolve them

Shortest/longest path in weighted DAG: Just set the edge weight as 0

Shortest/longest path(number of edges used): Give all non-auxiliary edges value of 0, treat as SP/LP in weighted DAG
> -1 votes

---
Tags: algorithms, graphs, constraint-satisfaction, dag
---


# Question
Title: In a set of sentences, how could I determine the fewest sentences that contains all characters?
So, for the sake of simplicity, I am going to use English characters for this example. Let's say I have a set of strings of characters in English ranked by difficulty: Easy, Intermediate, Advanced.

So it would look like:

## Easy

```
1. APQ
2. DL
3. RTE

```

## Intermediate

```
1. FSMG
2. NDA
3. LOXCW

```

## Advanced

```
1. GEW
2. ZAY
3. IVK

```

My question is: How could I go about finding the smallest set of strings that contain all the characters?

In this example, I would not need **Easy 2** or **Advanced 1** because their characters appear elsewhere in the set and they don't offer any characters not found elsewhere. Is there a type of algorithm best suited for this?

I can't just do a map lookup to see if I have come across a character before because I am looking for the smallest set. Also, I want to make sure, for instance, if I skip **Easy 2** that I don't skip **Intermediate 2** and **Intermediate 3** since that's where I found the **D** and **L** that allowed me to skip **Easy 2**.

As for my real-world application, I have 4135 strings (about 100-200 characters long) split into 6 levels of difficulty, and these strings are sentences in Chinese. These strings have about 4000 unique characters combined. I'm basically looking for which sentences are worth learning and discard the ones that don't offer much/any new characters. Difficulty is mostly irrelevant, but I may run the algorithm within difficulties, then across the board.

Any help would be greatly appreciated.

# Answer
This is an instance of set cover. It is NP-hard, so there is no efficient algorithm to find the absolute optimal solution. The problem has been studied and there are many techniques out there, which you can find by searching on set cover.

One approach is to use a heuristic to select a subset of strings that might be a little larger than absolutely necessary, but which can be found efficiently. See, e.g., the greedy heuristic and others derived from it.

Another approach is to use a SAT solver or ILP solver to find the optimal solution. This is not guaranteed to terminate within your lifetime; it might, or it might not. Some solvers will let you run for a fixed amount of time and output the best solution found so far.
> 2 votes

---
Tags: algorithms, optimization, shortest-path, strings, data-mining
---


title: Is computer science pointless

text:
# Question
Title: Is computer science pointless
For example, in real life, you're working with real time data that is constantly appended to. Computer science assumes a static problem, like traveling salesman. In reality you would start with a set of cities and add and remove them over time, so the solution at the individual step is trivial, and it's easier to store the result in memory than to run a fancy algorithm every time.

Likewise if you want to traverse a data structure in a certain way, isnt it easier to create a system of pointers and just store it in memory (x is the last branch etc) than having to find the last branch at runtime with an algorithm?

Is computer science actually excessively computational to the point it ignores easy in-memory or pointer solutions to most data structure problems?

# Answer
Your question takes a very narrow and untrue view of what computer science is. Computer science doesn't "assume a static problem" -- there is an entire subfield studying Online Algorithms, which take input problems piece-by-piece, as just one example.

Computer science is the system of methods for analyzing computing problems (i.e., making efficient use of computing time and computing memory). If you have (correctly) worked out a better way to solve a problem, then you are doing Computer Science. In general, it makes no such "static assumptions" or "ignores in-memory pointer solutions". You'll find that nearly any problem has been studied from nearly any angle, by someone in computer science.

When you describe "a system of pointers and how to store them in memory", what are you doing but describing an algorithm? An algorithm is a description of executable steps -- if you have devices a system of pointer-bookkeeping that solves the problem, you have devised an algorithm. If that algorithm doesn't find the "optimal" solution, it's still an algorithm that may be analyzeable by standard methods in Computer Science (e.g., "average"/worst-case runtime; or approximation bounds)

It's true that many problems faced in the "real world" are not addressable *solely* by the algorithms and data-structures taught in the first few years of a computer science education, and also that many real word problems do not require *optimal* solutions (not that computer science *only* studies optimal solutions -- it doesn't, optimizations and approximations are very intently studied).

However, the point of teaching the "standard" algorithms and data-structures isn't only to give a *complete* toolkit, but to provide a breadth of examples that introduce many different techniques:

* Algorithms for solving NP-complete problems like the Traveling Salesman Problem can introduce the concept of heuristics (which may or may not be "complete") and approximations
* Data-structures like doubling-arrays can introduce the concept of amortized analysis
* Data-structures like balanced trees prove out the concept of *worst case* analysis, showing that naive implementations can lead to pathological runtimes, and showing that there are *bounds* to how much you can improve in general (e.g., you can do insertion & lookup better than $\Theta(n)$ and no better than $\Theta(\log(n))$)
> 10 votes

# Answer
Even though computer science can be understood as a science of problem solving, *as a science*, it is above all interested in framing (answerable) questions. Questions about problem solving methods, whose answers can then be applied to the "real world" (whatever that is), sometimes by scientists themselves, most of the time by people in other walks of life.

Although it's true that very often solutions to practical problems are not a direct application of scientific research, it is also true that many times the presence of scientific results is hidden in plain sight, as the answers they bring are converted in common knowledge.

Your question relies on notions that you take for granted $\unicode{x2013}$ they seem *real* $\unicode{x2013}$, but weren't always so approachable. They were once purposefully conceived by scientists, who were deeply aware of the complexity of the choices they were making, and their implications, so that you can now navigate these notions in oblivion, as if they have grown on trees.

That said, I don't think your question should be disqualified. I think it can be useful to others, in its naiveté.
> 2 votes

---
Tags: software-engineering
---


# Question
Title: Simplifying $r_n = \max(p_n,r_i+r_{n-i})$ to $r_n = \max(p_i + r_{n-i})$
In CLRS (Intro to algorithms) on page 362, it says equation (1):

$$ r\_n = \max(p\_n, r\_1+r\_{n-1},r\_2+r\_{n-2},\dots,r\_{n-1}+r\_1) $$

can be simplified to this equation (2):

$$ r\_n = \max\_{1 \leq i \leq n} (p\_i + r\_{n-i}) $$

I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal proof but one that makes logical and intuitive sense. General arguments or assumptions that lead to this simplification are also welcome. Any effort is much appreciated.

**Update**

I want to know how the second equation is valid if we are not considering the optimal revenues on both sides but only the optimal revenue of the right-hand piece as suggested by the second equation.

I.e. in the second equation, we use the price of the left piece and then add it to the optimal revenue of the right-hand piece.

# Answer
> 1 votes
I feel like this is basically paraphrasing the explantion in CLRS but maybe it will help.

Let $j$ be the length of the leftmost rod piece in an optimal solution. This piece has a cost of $p\_j$ and so it contributes exactly that much to the total revenue. It is easy to see that the remaining part of the rod (of length $n-j$) must be divided up in an optimal manner as well for the whole thing to be optimal (and thus leads to a revenue of $r\_{n-j}$).

Thus, we have $r\_n = p\_j +r\_{n-j} $. Because $r\_n$ is the optimal revenue, $r\_n \geq \max\_{1\leq i \leq n}\\{p\_i+r\_{n-i}\\}$. But we also have $r\_n = p\_j +r\_{n-j} \leq \max\_{1\leq i\leq n}\\{p\_i+r\_{n-i}\\}$.

Putting both ineqalities together gives $r\_n = \max\_{1\leq i \leq n}\\{p\_i+r\_{n-i}\\}$.

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


# Question
Title: Confused between the terms Process and Process Control Block
I was reading about the Long term scheduler, when I read that when memory is not enough and load on the CPU due to multiprogramming is too high, a process might be moved to secondary storage space (namely swap space). I am slightly confused as too what exactly happens when a process is moved out of memory. Is its "PCB(Process Control Block)" moved out and store in Hard disk or something else like "process state".

I believe that this confusion is due to lack of clarity between "process in memory" and "process control block". Are the two things different or the same?

The above two diagrams have been picked from the 3rd chapter of Operating Systems Concepts 9th edition.

# Answer
The point of swapping is to make room in RAM. What is moved to disk is what the book calls “process in memory”, not the process control block. The PCB block is a small amount of memory, so moving it to disk wouldn't help much. Additionally, some of the PCB is necessary even if the process is never scheduled, for example to know whether a file is open or not (which matters if the file is deleted or when taking a lock on the file), to know what events (such as I/O becoming available) might cause the process to become runnable (this information would be in the “process state”), and the knowledge of where the process data is in the swap space (that would be the process's “memory limits” while it's swapped out). In contrast, none of the process's own memory is necessary while the process is not scheduled.

Note that most operating systems don't swap out a whole process, but parts of its memory. Some books make a distinction between “swapping” a whole process and “paging” parts of memory, but in modern usage, the words “swapping” and “paging” are usually synonymous and refer to any mechanism that temporarily moves process memory to swap, whether it moves a whole process at a time (uncommon) or parts of process memory (common).
> 1 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Sorting $n^2$ numbers which consist of numbers from 1 to $n$
I wish to sort $n^2$ numbers which all come from the set $\\{1,2,3,...,n\\}$, i.e duplications are allowed. I know I can just use merge sort which has complexity $\mathcal{O}(n^2\log (n))$, but I was wondering if it was possible to do better since I know all the numbers will be coming out of $\\{1,2,3,...,n\\}$.

If there is a special name for this type of problem please let me know. Any references or answers are greatly appreciated.

# Answer
> 4 votes
Given your contraints, I think Counting sort or Radix sort will do the job.

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


# Question
Title: Is there difference between a function in mathematics to a function in computer science?
I never learned a lot of mathematics (generally only arithmetic) and never learned computer science in a formal frame.

I emphasize that I don't mean to ask about a "function" in programming ("procedure"/"method"), rather only about the difference between the formal definition of function in mathematics to the formal definition of function in (theoretical) computer science, if at all there is any such difference (unless computer science don't share the exact definition common in mathematics).

**Is there difference between a function in mathematics to a function in computer science?**

# Answer
A function in mathematics is just a special case for a binary relation, where for every x there is exactly one y such that xRy is in the binary relation.

Computer science uses that term with the same meaning, as it uses lots of mathematical terms. It also uses the term "function" (or "subroutine", "procedure", "method") with a totally different meaning of one component of a program in the area of computer programming.

Just like the word "function" would be used with a completely different meaning in patent law (functional vs. decorative components) architecture (a functional design), medicine or psychology (like a "functional alcoholic").
> 4 votes

# Answer
As others have noted, the answer is "yes", but it's often a qualified "yes". Sometimes we talk about sets and functions, but sometimes we talk about *computable* sets and *computable* functions.

There is a temptation to think of programming language types as sets of values (e.g. $\hbox{Bool}$ is the set of values $\left\\{ \hbox{False}, \hbox{True} \right\\}$), and programming language functions as functions between those sets, but this isn't correct.

Consider a function with this type:

$$f : X \rightarrow 2^X$$

In set theory, this function cannot be bijective, because Cantor's theorem states that there is no bijection between a set and its power set.

But with computable sets and computable functions, there's no such problem. In a programming language like Haskell, for example, I can write:

```
newtype X = X (X -> Bool)

```

And in doing so, I have constructed a type $X$ such that $X$ and $2^X$ are isomorphic.
> 3 votes

# Answer
I would be a lot more confident if you were asking about a specific usage, rather than in generaly--would you like to give an example?

That said no, they are the same. Further, theoretical computer science is arguably a field of mathematics, and certainly inherits a lot of culture and terminology from it. You can expect most terms to be the same.

However, do keep in mind:

1. As you mention, sometimes when computer scientists say "function", they mean a function call or subprocedure. This should generally be clear in context.
2. (Rare) If you are reading about computability, for example early in a class when the halting problem is introduced, "function" may be used as a (sloppy) abbreviation for "partial function". A "partial function" is like an ordinary (or "total") function, except that it is allowed to be undefined for some inputs. This corresponds to a deterministic computational process like a Turing machine--it either outputs something, or it may run forever.
> 1 votes

# Answer
Function in computer science in simple words represents by braces( ) like in c++ we use predefine functions like main() etc but sometimes in ( java) we call this function as method also we have many predefined functions in java like substring(),indexOf() and many more but also you will remeber one think these languages also provides controls to declares your own function

Thanks bro for more reply me i have better command in java ,python and javascript to let me know in which language you want to know the concept of function i will try my best
> -2 votes

---
Tags: functional-programming
---


# Question
Title: Can a computer science graduate find an unknown spyware,malware?
If a computer science graduate is presented with a device that has a spyware which anti spywares cannot yet detect, can he find it?

2. Or presented with website that is possibly malicious, can he prove whether it is safe or not?

If not then people of what computer field can do the the tasks mentioned above?

I am asking to get a better understanding of what computer science is about.

# Answer
> 0 votes
Well it depends. The task of identifying spyware/malware and analyzing it requires a lot of knowledge about the operating system you are working on, being able to deal with code in general (be it assembly, reverse engineering, etc.) and of course knowing protocols (be it https, http, and any other protocol) including how they work on the mathematical level.

Computer science students often know a lot about the os they are working with, coding in general etc., because they work with them every day and are nerdy in general, but not because of the content of computer science lectures. Computer science is more concerned with the **science of computing**. Meaning you learn e.g. how to compute things with algorithms on abstract models of machines (you actually don't care about the specifics like OS/ hardware etc.) and how to develop those algos and how to classify their performance. Of course the basics of programming and OS architecture are taught, but the focus is on abstract concepts. E.g. instead of learning HTTPS protocol you might learn about the math of cryptography which again would allow you to understand most secure protocols by reading their spec. *You learn the theoretical basis for to understand real world stuff on your own*.
Common topics in compsci would be: programming, analysis, linear algebra, algorithms and data structures, graph theory, ...

You can study IT-Security at some universities, which is probably a bit closer to praxis.

---
Tags: education
---


title: Java programming object terminology

text:
# Question
Title: Java programming object terminology
Say there is a class called `Person`. Then in the following expression :

`Person human = new Person()`

Which is the "reference" and which is the "object"?

`human` should be the reference since it's not an actual object, it simply points to an object. On the other side, `new Person()` truly is the actual object. I've seen these terms used vice versa and I was wondering what's the actual naming?

# Answer
> -2 votes
Person is a class and human is an object the most important key point about object is it points towards feilds and methods but here you will see in braces you have passed nothing means class Person have no parametrized constructor but have a default one

Thanks bro if you will find any difficulty while doing java i am here for your help so free to ask

---
Tags: programming-languages, java, object-oriented
---


# Question
Title: A problem about master theorem and recursion
Prove or disprove the following statement:
If $f(n)\in \Omega(n^2)$ and $T(n) = 2T(n/2) + f(n)$ then $T(n) \in O(f(n))$.

I think that the statement is false. Do you know any counterexamples?

# Answer
> 0 votes
Taking $n=2^k$, we have $$T(n)=2T\left(\frac{n}{2}\right)+f(n)=\\\=2\left\[2T\left(\frac{n}{2^2}\right) +f(n)\right\]+f(n)=2^2T\left(\frac{n}{2^2}\right)+2f(n)+f(n)=\\\=2^3T\left(\frac{n}{2^3}\right)+2^2f(n)+2f(n)+f(n)=\cdots=2^kT(1)+f(n)\[2^{k-1}+\cdots+1\]=\\\=2^kT(1)+f(n)(2^k-1) = nT(1)+f(n)(n-1)$$ Now we have 2 cases: 1. $T,f$ are defined only for $2$s powers and 2. $T,f$ are defined on $\mathbb{N}$.

1. Considering non negative functions, condition $T \in O(f)$ gives $$ f(n)(n-1) \leqslant T(n) \leqslant C f(n)$$ which is impossible for any below boundedness for $f$.
2. If we demand $T$ defined on $\mathbb{N}$, then we come to necessity to define $T\left(\frac{n}{2}\right)$ which can be filled by OP.

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


# Question
Title: On Tarjan's paper "Finding a Maximum Clique"
In his paper, "Finding a Maximum Clique" from 1972 Robert Tarjan introduced an algorithm that finds maximum cliques in $O(1.286^n)$. You can find a link to his paper here.

In the second page of the introduction he states the following lemma.

Let $G = (V,E)$ be a graph and $S \subseteq V.$ Then $$ ||G|| = \max\_{\text{clique } C \text{ in } G\_S} \\{|C| + ||G\_{A(C)\setminus S}||\\} $$

where $||G||$ is the size of the maximum clique in $G$ and $A(C)$ is the set of adjacent vertices to one or more elements in $C$.

This does not make sense to me, for example if we let $S$ be the set containing just one isolated vertex, then $\max\_{\text{clique } C \text{ in } G\_S} \\{|C| + ||G\_{A(C)\setminus S}||\\} = 1$, since $A(C) \setminus S = \emptyset \setminus S = \emptyset$.

Even worse, we can take $S = \emptyset$ and then the lemma falls apart.

What am I missing?

# Answer
You definition of $A(C)$ is wrong. It is the set of vertices adjacent to *all* vertices in $C$: $$ A(C) = \\{ v \in V : \forall u \in C, (u,v) \in E \\}. $$ In particular, if $C = \emptyset$ then $A(C) = V$.

In your example, suppose that $S = \\{v\\}$. Let's see what $|C| + \\|G\_{A(C) \setminus S}\\|$ amounts two for all choices of $C$:

1. If $C = \emptyset$, then $A(C) \setminus S = V \setminus \\{v\\}$, and so $|C| + \\|G\_{A(C)\setminus S}\\|$ is the maximum size of a clique in $G$ that doesn't contain $v$.
2. If $C = \\{v\\}$, then $A(C) \setminus S = N(v)$, the set of neighbors of $v$. Therefore $|C| + \\|G\_{A(C) \setminus S}\\|$ is the maximum size of a clique in $G$ that contains $v$.

So in this case, the formula is correct.

When $S = \emptyset$, the formula just states that $\\|G\\| = \\|G\\|$.
> 2 votes

---
Tags: clique
---


# Question
Title: Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n
Here is a question from Computational Complexity by Arora and Barak:

> Show that representing OR of $n$ variables $x\_1,x\_2,\dots,x\_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$. (This is Exercise 6 in the chapter on circuit lower bounds.)

How do I approach this problem?

# Answer
> 1 votes
Let $AND:\\{0,1\\}^n\mapsto\\{0,1\\}$ be a polynomial in $GF(q), q\geq 2$. Notice that the polynomial can't have a constant term (the constant term is zero), because $AND(0,...,0) = 0$. Meaning we can write the polynomial as: $$AND(x\_1,...,x\_n) = \sum\_{S\subseteq\[1,n\], S\neq \emptyset}a\_S\prod\_{j\in S}x\_j$$ We now claim that every non-zero summand in $AND$ contains $x\_i$. Suppose that there are a set of summands not containing $x\_i$. Choose the smallest (by amount of different parameters contained) of them. Notice that this term is uniquely identified by a set $U \subset \[1,n\]\backslash\\{i\\}$. Now set $x\_u = 1, u\in U$ and $x\_v = 0, v\notin U$ and that there is no proper subsets of $U$ whose associated term is non-zero, because $|U|$ was chosen to be minimal. $$AND(x\_1,...,x\_n) = a\_U$$ This implies $a\_U = 0$, because $i\notin U \land x\_i = 0$. Repeat for all other summands (in increasing order by size). Thus all non-zero terms contain $x\_i$. This applies to all $i\in\[1,n\]$, hence the degree of $AND$ is $n$.

We can denote $OR$ as $OR(x\_1,...,x\_n) = 1-AND(1-x\_1,...,1-x\_n)$ and likewise $AND(x\_1,...,x\_n) = 1-OR(1-x\_1,...,1-x\_n)$ by De Morgan's Law. Thus $AND$ and $OR$ must have the same degree.

# Answer
> 1 votes
Let $f\colon \\{0,1\\}^n \to \mathit{GF}(q)$. Then $$ f(x) = \sum\_{y \in \\{0,1\\}^n} f(y) \prod\_{i\colon y\_i=0} (1-x\_i) \prod\_{i\colon y\_i=1} x\_i. $$ This shows that any function from $\\{0,1\\}^n$ to $\mathit{GF}(q)$ can be represented as a multilinear polynomial.

Now let us show that the representation is unique. This follows from dimension considerations (the space of all such functions has dimension $2^n$, which coincides with the dimension of the space of multilinear polynomials), but we can also prove it directly. If some function has two different representations $P,Q$, then $P-Q$ is a non-zero multilinear polynomial that vanishes on $\\{0,1\\}^n$. Let $m$ be a monomial in $P-Q$ of minimal degree, appearing with coefficient $c \neq 0$, and let $y \in \\{0,1\\}^n$ be the point defined as follows: $y\_i = 1$ if $x\_i$ appears in $m$, and $y\_i = 0$ otherwise. Then $(P-Q)(y) = cm(y) = c \neq 0$, contradiction.

Suppose that $P$ is a polynomial representing the OR function. If $P$ is not multilinear, we can replace every occurrence of $x\_i^d$ for $d \geq 1$ with $x\_i$, obtaining another representation $Q$ of OR whose degree is at most the degree of $P$. According to the above, this representation is unique, and so it must be the following: $$ Q(x) = 1-\prod\_{i=1}^n (1-x\_i). $$ Thus $\deg(P) \geq \deg(Q) = n$.

---
Tags: complexity-theory, circuits, polynomials
---


# Question
Title: Solve recurrence relation $T(n)=n^{1/5}T(n^{4/5})+5n/4$
I am trying to solve this recurrence relation - $T(n)=n^{1/5}T(n^{4/5})+5n/4$. I can't use the master's method and the recursion tree method because of that $n^{1/5}$ term.

We can write $$\frac{T(n)}n=\frac{T(n^{4/5})}{n^{4/5}}+\frac54$$

Now we can change variable $S(n)=\frac{T(n)}{n}$. So, we get $$S(n)=S(n^{4/5})+\frac{5}{4}$$

Then I used the recurrence tree method by taking $n=2^{(\frac{5}{4})^k}$. I got $S(n)=O((log\_{5/4}(log\_2 n))^2)$. So, $$T(n)=O(n(log\_{5/4}(log\_2 n))^2)$$

I don't know, the answer doesn't look right. Can anyone please help me out? If anyone knows the final answer please let me know, so that I can check.

Thanks!

# Answer
**Derivation**
Lets consider $n = 2^{(5/4)^k}$. Now we can evaluate step by step: $$ S(n) = S(2^{(5/4)^{k-1}}) + 5/4 = S(2^{(5/4)^{k-2}}) + 5/4 + 5/4$$ Notice that every time $k$ is reduced by one since: $$\left(2^{(5/4)^{k}}\right)^{4/5} = 2^{(5/4)^{k}\cdot(4/5)} = 2^{(5/4)^{k-1}}$$ Thus we can denote $S(n)$ as (assuming $S(2) = 0$ as base case): $$\sum\_{i=1}^k 5/4 = (5/4)k $$ Now lets solve $n = 2^{(5/4)^k}$ for $n$. Apply $\log\_2$ and then $\log\_{5/4}$ on both sides: $k = \log\_{5/4}(\log\_2(n))$ and thus $S(n) = (5/4)\log\_{5/4}(\log\_2(n))$.

---

**Test by plugging it in**
You can simply plug your solution in to test it. For $S(n) = S(n^{4/5}) + 5/4$ you can obtain $S(n) = (5/4)\log\_{5/4}(\log\_2(n))$ by the recursion tree method (as described above). Lets plug this into our recurrence: $$S(n) = (5/4)\log\_{5/4}(\log\_2(n^{4/5}))+5/4 = (5/4)\log\_{5/4}((4/5)\log\_2(n))+5/4$$ And by the rules of logaritm: $$S(n) = (5/4)\log\_{5/4}(\log\_2(n))+(5/4)\log\_{5/4}(4/5)+5/4$$ Notice $\log\_{5/4}(4/5) = -1$ and things cancel out: $$S(n) = (5/4)\log\_{5/4}(\log\_2(n))-(5/4)+5/4 = (5/4)\log\_{5/4}(\log\_2(n))$$ Our expression for $S(n)$ fulfills the recurrence. Hence $$T(n)/n = S(n) \Rightarrow T(n) = (5/4)n\log\_{5/4}\log\_2(n)$$ A double logarithm looks scary but if often occurs when recurrences have the form $T(n) = aT(n^\alpha) +b$.
> 2 votes

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Polynomial-time algorithm to solve the maximum vertex bipartite subgraph problem
I'm trying to find an algorithm that solves the maximum vertex biclique problem. I know that that algorithm can be solved in polynomial time (in contrast with the maximum edge biclique problem, which is NP-hard), and it's related somehow to transform the problem to a network flow problem, but I'm having a hard time finding it because most of the results from google are about NP-hard problems with similar wordings like maximum edge biclique problem, maximum vertex coverage and such.

Could anyone provide a link, explanation or even a pseudocode algorithm about how to solve the maximum vertex biclique problem in polynomial time?

# Answer
> 1 votes
The problem is equivalent to the Maximum Independent Set problem on the "bipartite complement graph" (take the complement graph and delete edges with both endpoints on the same side of the bipartition). Such an MIS is the complement of a Minimum Vertex Cover, which can itself be deduced from a Maximum Matching.

You can probably take it from here (with maybe a bit of googling for how to find a Minimum Vertex Cover in a bipartite graph).

---
Tags: graphs, optimization
---


# Question
Title: Find subgraphs that can only be reached by two nodes
I want to find subgraphs in a graph that are only connected to the rest of the graph by two nodes; for example, node A is connected to the rest of the graph, as well as node F, but nodes B-E are only connected to each other and A and F (don't have to be fully connected). Is there a name for this? And is there an algorithm for finding such subgraphs? The distance of A and F is defined by their shortest path: for example, if d=4, I would want to find all subgraphs where the shortest path between A-like and F-like nodes is at most 4.

# Answer
I don't know if there's a name for such subgraphs, but here's something to get you started.

**If you require the subgraphs to be connected**

A polytime algorithm for $G=(V,E)$ would be: for every possible unordered pair $(A,F)\in \binom{V}{2}$ consider the connected components of the graph induced by $V\smallsetminus\\{A,F\\}$. Then consider the classes which contain at least a neighbour of $A$ and one of $F$ (this step is required if the original graph was not connected). Then for each subgraph you found you can "add $A$ and $F$ back in" and look for their distance in the graph.

Let's sketch correctness (only the step about the subgraphs we are looking for being the connected components needs to be verified).

* All components are solutions: by construction they only share links with themselves and A and F, and are connected.
* All solutions are components: they are connected and only connect to the rest of the graph through A and F.

I am guessing you can do much better in runtime, but your problem seems to be in $P$ at least.

**If you don't**

You need to also consider combinations of the subgraphs found above, but in terms of the minimum distance it doesn't change much.
> 1 votes

---
Tags: graphs, terminology, subgraphs
---


# Question
Title: What is the fastest and most elegant way to change a matrix dimension?
I have been writing code for a paper and I'm reading an image in RGB space in OpenCV which means that its read as a 3D matrix (HEIGHT x WIDTH x 3 (RGB) ).

I'm reshaping the image into a 2D matrix ( NB\_PIXELS x 3 (RGB) ) using this code :

```
image = image.reshape(len(image) * len(image[0]), len(image[0][0]))

```

This reshaping process is an important step in the method that I'm going over in the paper.

Since I can't have the paper depend on a library like NumPy I would like a more elegant way to explain the reshaping. Are there any papers that I can reference or any equations, methods ..etc that I can use as a replacement to the code that I shared ?

Thank you!

# Answer
I would consider a sentence such as this to be unambiguous:

> We flattened the $h \times w \times 3$ input data down to a two-dimensional $hw \times 3$ shape.

I don't believe a reference explaining this would be necessary.
> 3 votes

---
Tags: matrices
---


# Question
Title: Why add S0 -> S while converting CFG to Chomsky Normal Form
While converting CFG to CNF sometimes it is suggested to add extra step. Add new start symbol **S0** and add new derivation **S0 -\> S**. Book Hopcroft Ullman does not suggest this step but many other articles suggest to add this step. What is purpose of adding this extra derivation?

# Answer
This has to do with the fact that grammars in Chomsky normal form cannot generate the empty word. Indeed, if we only allow rules of the form $A \to BC$ and $A \to a$, then it is impossible to generate the empty word.

In order to accommodate languages containing the empty word, we allow the transition $S \to \epsilon$, where $S$ is the starting symbol. For various reasons (for example, the proof of the pumping lemma), we still don't want any other symbol to generate the empty word, so we disallow $S$ on the right-hand side.

The transition $S\_0 \to S$ allows us to treat $S$ as a normal symbol, that is, to allow it to appear on the right-hand side, even if the grammar generates the empty word.
> 2 votes

---
Tags: normal-forms
---


# Question
Title: Depth of binary tree with few single children
The node of a binary tree is called a *single child* if it has a parent but does not have a sibling. The root is by definition not considered a single child.

> Let $T$ be a binary tree of size $n$, and let $k$ be the number of vertices in $T$ that are single children. Is it true that if $\frac{k}{n}\leq \frac{1}{2}$ then the height of $T$ is $O(\log n)$?

# Answer
> 2 votes
You can construct a tree with *no* single children which has height $(n-1)/2$: .

---
Tags: binary-trees
---


# Question
Title: Finding the rectangle with maximum perimeter weight in a 2D array
\[Problem Description\]:

Given an array of size $N \times N$, the task is to find the rectangle with maximum perimeter weight in the array. The perimeter is defined as the number of cells on the sides. The perimeter weight of a rectangle is defined as the sum of all the values lying on the sides of the rectangle.

For example, the above image shows an array of size 5\*5. Each cell has a value. The pink cells form the perimeter of the rectangle with upper left cell (0,0) and lower right cell (2,3). The perimeter is 10. The perimeter weight is (1-1+0+4+2+1+0+2-5-1) = 3

I am asked to give:

(1): an $O(N^3)$ algorithm to find a rectangle with the maximum weight.

(2): an $O(N^3)$ algorithm to find a rectangle with the maximum weight with perimeter no greater than a given constant L.

I really have no idea about how to do. Could anyone give me some idea about these 2 problems?

Thanks a lot in advance!

# Answer
Let us denote the entries of the array by $A(i,j)$.

Fix the first and last rows of the rectangle $i\_1,i\_2$. For $j\_1\<j\_2$, the perimeter of the corresponding rectangle is $$ \sum\_{i=i\_1}^{i\_2} \[A(i,j\_1) + A(i,j\_2)\] + \sum\_{j=j\_1}^{j\_2} \[A(i\_1,j) + A(i\_2,j)\] = \\ \left\[\sum\_{i=i\_1}^{i\_2} A(i,j\_1) - \sum\_{j\<j\_1} \[A(i\_1,j) + A(i\_2,j)\]\right\] + \left\[\sum\_{i=i\_1}^{i\_2} A(i,j\_2) + \sum\_{j \leq j\_2} \[A(i\_1,j) + A(i\_2,j)\]\right\]. $$ Let us denote the first term by $x\_{j\_1}$ and the second by $y\_{j\_2}$. Using appropriate precomputation, it is possible to compute the arrays $x\_j,y\_j$ in $O(n)$. We can also compute $\max\_{j\_1\<j\_2} (x\_{j\_1}+y\_{j\_2})$ in $O(n)$. In total, for each $i\_1\<i\_2$ we can compute the maximum perimeter in $O(n)$. Since there are $O(n^2)$ choices for $i\_1,i\_2$, the entire algorithm runs in $O(n^3)$.

This answers your first question. I'll let you check whether these methods can help with the second question.
> 3 votes

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


# Question
Title: Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem
I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following:

* There exists a believed-today NP-hard problem called $X$, where its whole input space can be divided into a finite set of groups such that there exists a corresponding "single-threaded" polynomial-time algorithm for each group (that only runs polynomically for the inputs corresponding to its designated group, without any complexity guarantees regarding inputs for other groups).

Since we don't neccesarily have a criteria to know, polynomically, to which group a certain input belongs to, a possible approach to solve such problem $X$ polynomically is to run all algorithms in parallel and wait for the first that finishes, aborting the execution of everyone else.

Since we have at least one polynomial-time algorithm for every possible input of $X$ (because of the conditions given above), and we are executing all algorithms at once, such problem will be solved in polynomial time for every input, and so every believed-today NP-hard problem can be solved polynomically previous transformation to an instance of $X$.

Is there any research in this direction?

# Answer
$X$ doesn't exist (unless $P = NP$ in general) because your description is self-contradictory. You claim it is NP-hard, yet its input domain can be split in a finite number of disjoint poly-time solvable problems. This makes it $P$.

The idea of executing these algorithms in parallel adds nothing. Even on a single machine you can run N programs 'simultaneously' by distributing computational time in a round-robin fashion, leading to an overhead factor of N to any single program. Set N to be equal to your number of algorithms (which was, by your description, a finite constant), and you end up with a poly-time algorithm.
> 3 votes

# Answer
No, I'm not aware of any research in this direction, probably because it is not very promising. This does not seem to me like a promising approach to solve NP-hard problems efficiently, or other hard problems efficiently. The hard part would be how you would find that decomposition; I don't know of any reason to think that's particularly easier than solving the entire problem.

If the problem had the structure you described, with only polynomially many groups, then the problem could be solved in polynomial time. Anything you can do in parallel, you can do with a single thread by interleaving execution. After all, many CPUs are single-threaded, yet can execute many processes (seemingly in parallel, though actually interleaved).

You talk about "believed to be NP-hard", but most of the NP-hard problems we encountered are not just "believed" to be NP-hard; they are known to be NP-hard, and we can prove it.

My answer does not change appreciably if you replace "believed to be NP-hard" with "believed to be hard".
> 1 votes

---
Tags: complexity-theory, graphs, optimization
---


# Question
Title: Given a list of integer rectangle areas, find all integer rectangles that they can tile
> Is there an efficient algorithm that takes in a list (multiset) of integer rectangle areas and finds all possible integer rectangle tilings?
>
> Every integer rectangle area in the list (multiset) must be used exactly once (corresponds to exactly one rectangle).

For example, if we were given $$(2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1, 1, 18, 1, 1, 20, 1)$$ then one possible integer rectangle tiling is:

which uses the given list to tile a $11\times 12$ rectangle.

So far, I've found What rectangles can a set of rectangles tile? on MO, and am trying to track down and adapt the references to my problem.

A similar but different problem is Filling rectangles with integer-sided squares.

# Answer
> 3 votes
**This answer assumes that you only allow the tiles to have integer sides.**

There are always some trivial tilings, in which the rectangle being tiled has either a single row or a single column. Counting the number of these is simple combinatorics. Let us show that deciding whether there are any other tilings is NP-complete (under randomized reductions, or assuming some number-theoretic conjectures). It is clearly in NP. To show that it is NP-hard, we reduce from PARTITION. An instance of PARTITION is a multiset of positive integers, and the problem is to determine whether it can be partitioned into two multisets with equal sum.

---

We start by showing that PARTITION is NP-hard even if all parts are odd and the total sum is divisible by 4. Let us first ignore the latter requirement. Given an instance $S = \\{x\_1,\ldots,x\_n\\}$ of PARTITION, construct an instance of the new problem with $S' = \\{2nx\_1+1,\ldots,2nx\_n+1\\} \cup \\{1^n\\}$ (here $1^n$ mean $n$ many $1$s).

If the original instance can be partitioned into two equal parts, say $\\{x\_1,\ldots,x\_m\\}$ and $\\{x\_{m+1},\ldots,x\_n\\}$, then so can the new instance. Indeed, consider the multiset $\\{2nx\_1+1,\ldots,2nx\_m+1\\}$, together with $n-m$ many $1$s. This multiset sums to $2n(x\_1 + \cdots + x\_m) + m + (n-m) = 2n(x\_1 + \cdots + x\_m) + n$. Similarly, the remaining numbers sum to $2n(x\_{m+1} + \cdots + x\_n) + (n-m) + m = 2n(x\_{m+1} + \cdots + x\_n) = n$, which is identical.

Conversely, suppose that $S'$ can be partitioned into two equal parts, say one of them consisting of $2nx\_1+1,\ldots,2nx\_m+1$ together with $r$ many $1$s. It follows that $$ 2n(x\_1 + \cdots + x\_m) + m + r = 2n(x\_{m+1} + \cdots + x\_n) + (n-m) + (n-r), $$ and so $$ 2n(x\_1 + \cdots + x\_m - x\_{m+1} - \cdots - x\_n) = (n-2m) + (n-2r). $$ Since $1 \leq m \leq n-1$ and $0 \leq r \leq n$, the right-hand side is in the range $\[-(2n-2),(2n-2)\]$. Since the left-hand side is a multiple of $2n$, we conclude that the right-hand size is zero, and so $x\_1 + \cdots + x\_m = x\_{m+1} + \cdots + x\_n$.

Let us now attend to the sum of $S'$. If $S$ sums to $2R$ then $S'$ sums to $$ 2n \cdot 2R + 2n = 2n(2R+1). $$ Therefore if $n$ is even, then we are done. Otherwise, we can replace $n$ with $n+1$ throughout (equivalently, add a zero to $S$).

---

We now reduce the PARTITION variant to the tiling problem. Let $S$ be an instance of PARTITION in which all numbers are odd and the sum is $2T$, where $T$ is even. Let $p$ be a prime in $(2T,3T)$. Notice that $S \cup \\{p-T,p-T\\}$ can be partitioned into two equal halves iff $S$ can (this is since $2(p-T)$ is larger than half the total sum, which is $\[2T+2(p-T)\]/2 = p$). Moreover, since $p$ is odd and $T$ is even, $p-T$ is odd.

Let $q \in (2p,3p)$ be a prime, and consider the instance $S \cup \\{p-T,p-T,pq\\}$. If $S$ can be partitioned into two equal halves, then we can tile a rectangle of dimensions $p \times (q+2)$ by taking a rectangle of dimensions $p \times q$ and adding two more columns corresponding to the two equal halves of $S \cup \\{p-T,p-T\\}$.

Conversely, suppose that $S \cup \\{p-T,p-T,pq\\}$ can tile some rectangle. Since $p,q$ are prime, the rectangle of area $pq$ must have dimensions $1 \times pq$ or $p \times q$ (up to switching the axes). In the former case, since all remaining numbers add up to $2p \< pq$, we end up with a trivial tiling. In the latter case, since $2p \< q$, the remaining numbers are not enough to fill any rows, and so we conclude that the tiled rectangle must have exactly $p$ rows. Since the remaining numbers add up to $2p$, they must tile a $p \times 2$ rectangle (or two $p \times 1$ rectangles, which is a stronger requirement). The remaining numbers are all odd, and so must correspond to rectangles with a single column. This is only possible if they can be partitioned into two equal parts.

---
Tags: algorithms, reference-request
---


title: Finding a maximum element in min heap

text:
# Question
Title: Finding a maximum element in min heap
i need to say : Where can be a maximum element in a min heap when all the elements are different?

# Answer
The maximum is one of the heap’s leaves. You can’t know which one. You for optimizing your algorithm, you can scan only the leaves, which in case the heap is implemented with an array, requires scan of maximum of (n+1)/2 nodes (which is still O(n))
> 2 votes

# Answer
The best way to do this would be to iterate over all the items at the bottom of the heap.
> 0 votes

---
Tags: heaps
---


# Question
Title: Undecidability of "is this CFG prefix-free?"
I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition).

Another thread has the very different question "is this *regular language* prefix-free". One of the answers in that thread claims to prove undecidability for CFLs (even though that did not explicitly ask for a proof of undecidability for CFLs) using the usual Post Correspondence Problem (PCP) method.

The proof in the other thread claimed (as of Oct 11, 2020) that a certain CFL with an endmarker $\\#$ is prefix free if and only if there's no PCP solution. However, it seems to be possible to have prefixes in the CFL even without any PCP solutions, which would mean the proof is wrong.

I also tried using the fact that "non-emptiness of intersection of two CFGs" is undecidable. However, we are only able to use undecidability of CFGs being prefix-free to prove undecidability of intersection non-emptiness, *not* the other way around.

# Answer
One endmarker is insufficient to prove this. Instead, we must use multiple endmarkers. Here's the full proof, with the same basic idea taken from the other answer.

Using the notation from Sipser 3rd edition problem 5.21, let the string pairs $(t\_i, b\_i)$ for $i \in \\{1, 2 \ldots k\\}$ be an instance of the PCP problem. Define grammar rules $T \rightarrow t\_i T \texttt{a}\_i$ and $T \rightarrow t\_i \texttt{a}\_i$ (where $\texttt{a}\_i$ are new symbols) along with $B \rightarrow b\_i B \texttt{a}\_i$ and $B \rightarrow b\_i \texttt{a}\_i$. This instance of PCP has a solution if and only if $T \cap B$ is non-empty. (This construction can be used to prove many other undecidability properties of CFGs; for more, see Sipser 3rd edition chapter 5 or Hopcroft and Ullman 3rd edition chapter 9).

Define more rules $W \rightarrow T\\#$ and $W \rightarrow B\\#\\#$, where $\\#$ is another new symbol. Clearly, $W$ is prefix free if and only if $T \cap B$ is non-empty. Hence, a decider for prefix-free CFGs would also decide any PCP problem. Since PCP is undecidable, we have a contradiction, and thus the language of prefix free CFGs is also undecidable.
> 5 votes

---
Tags: formal-languages, turing-machines, context-free, undecidability
---


# Question
Title: How to pass comma separated values from yacc to cpp file node
I am writing a compiler in CPP using Flex and Bison and having trouble understanding passing values up the syntax tree in bison. I have grammar like this below, 'exp' would evaluate to any number.

```
args_list: exp | args_list comma exp;
array_list: datatype identifier '[' number']' equal '{' args_list'}'{$$ = new array_node($1, $2, $4, $8);}

```

I wanted to pass args\_list to the array\_node but not getting how to pass? As you can see user can initialize array with any length but how to pass this list to CPP node? for example - int a\[4\] = {1,2,3,4} ; I want to pass something like

```
new array_node(datatype, a, number, args_list)

```

in which I am not getting how to pass args\_list so that I can have array type. Or please suggest me another way to pass the array list to the cpp file. or how to pass whole array to cpp file from yacc?

# Answer
> 0 votes
args\_list’s type can be vector. Then, instead of calling to new array\_node you can have a factory method (array\_node::factory) which parses the type, casts the args and returns the array\_node object

---
Tags: compilers
---


# Question
Title: Is this concatenation ({a} · {b})^2 ≠ a^2 · b^2?
I presumed they were equal, such that both resulted in `aabb`. However, I'm told they are false and I don't know why.

Is it because in the **second** one, we would concatenate `a · b` before raising to the power of 2, thus resulting in `abababab`? Or because in the **first** one you concatenate first, thus resulting in `abab`?

Thanks in advance.

# Answer
They are different, because:

$(a \cdot b)^2 = abab$, since you need to concatenate $a$ and $b$ first, them reapeat the concatenation two times.

$a^2 \cdot b^2 = aabb$, since you need to concatenate the repetition of two $a$ with the repetition of two $b$.
> 1 votes

---
Tags: formal-languages
---


# Question
Title: Given a bitonic sequence $a_1, a_2, \ldots, a_n$ , calculate the median in $O(\log n)$
This is a question in my textbook, it requires me to write an algorithm to find the median of a bitonic sequence in $O(\log n)$, where $n$ is the number of elements (a bitonic sequence is a sequence that is non-increasing first, and then it's non-decreasing after some point). How do I approach this? I feel like it has something to do with the medians of the 2 parts (the non-increasing and non-decreasing parts of the sequence), but I couldn't find a way to solve it from there.

Any help would be much appreciated. Thank you.

# Answer
> 2 votes
First you use an algorithm to find the bitonic point, that is the point where the sequence swaps from being non-increasing to non-decreasing. This is possible with this algorithm in $O(\log(n))$. Now you split the sequence apart at this point (virtually, you don't really make any copies since that would cost $O(n)$). You can now use this algorithm to find the median of two sorted sequences in $O(\log(\min(u,v)))$. $u+v = n$ in our case since we split the original sequence.

Beware that you need to adjust the given algorithms since the first one uses the opposite definition of bitonic (first increasing the decreasing) and the second one assumes that both arrays are sorted in the same direction (in our case one is in reverse).

---
Tags: algorithms
---


# Question
Title: How would it be possible that primality testing is in P, but not factorization?
Suppose that P != NP. Then there exists 3SAT formulas such that their satisfiability is computationally "evil" (i.e, the satisfiability can be exponentially hard to determine in the size of the formula).

Primality testing can be reduced to the satisfiability of a multiplication circuit, which can be reduced to the satisfiability of a 3SAT formula. But "Primes is in P". The satisfiability of this formula cannot be "evil", since it can be reduced to AKS primality test for example.

Integer factorization can be achieved by finding a satisfying assignment to the same formula. This can be achieved by choosing a variable, and then testing the satisfiability again. Choosing a variable, simplifies the formula through unit propagation. The new formula is a subset of the previous one. Now suddenly "we don't know" whether this formula can be solved in polynomial time.

Isn't this a contradiction? Is it possible that the subset of a formula is harder to solve than the formula itself?

# Answer
First of all, it doesn't make sense to talk about solving any particular formula in polynomial time--every specific formula can be solved in constant time (the answer is either yes or no, we just don't know which). So talking about whether any particular formula is "evil", probably does not make sense.

Also, just because we can solve problem A, by reducing to the problem B, doesn't mean we can solve everything near problem B. In fact, we may not even be able to solve problem B, in some cases!

Can you remove some clauses and make a family of SAT problems harder? Definitely. Take any family, and add the clause $A \\& \bar{A} $. Now the answer is definitely "no". Remove that clause, and the problem is hard.

This makes sense--removing constraints often feels like intuitively makes things harder. Think about sudoku--less filled in boxes, doesn't always make the problem easier.
> 2 votes

# Answer
"Primality testing can be reduced to the satisfiability of a multiplication circuit" - that's right, or close enough, because it can be reduced to the non-satisfiabilty of a multiplication circuit.

However, factoring cannot be reduced to the satisfiability of a multiplication circuit. It can be reduced to actually *satisfying* the circuit. Proving or disproving satisfiability, and finding an actual way to satisfy the formula are totally different in difficulty.

"How can this be" - for an example, go back to high school maths. Every continuous function of real numbers on a closed interval has a maximum and a minimum. And if f(a) \< 0 and f(b) \> 0 then the function has a root on the interval \[a, b\]. But *finding* the maximum, minimum, and root, that's a totally different matter.
> 1 votes

---
Tags: p-vs-np, integers, factoring
---


# Question
Title: Assuming P = NP, how would one solve the graph coloring problem in polynomial time?
Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time?

Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \\{1,2,\cdots,k\\}$ for some $k$ satisfying the property that $(u,v) \in E$ implies $\chi(u)\ne\chi(v)$ so as to minimize the fewest number $k$ of “colors”.

# Answer
> 42 votes
There are two cases:

1. $P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded middle. In this case, we have *no idea* what an algorithm to solve graph coloring in polynomial time looks like, or any other problem. We know one exists, because we know that if it doesn't exist, we can derive a contradiction. So a proof of this form is pretty useless for solving problems quickly.
2. $P = NP$ constructively. In this case, we have a polynomial time algorithm for some $NP$-hard problem, let's say $L$. If $L$ is NP-hard, then it must solve some other NP-hard problem in polynomial time (i.e. it reduces from that problem). That problem, in turn, either reduces from another problem, or has a direct reduction from every problem in $NP$. We keep following the trail of reductions until we get to one with a direct proof (probably 3SAT).

By composing these reductions, we get an algorithm that solves 3SAT in polynomial time (because each reduction only makes a polynomial number of calls to the previous algorithm, and our starting algorithm for $L$ runs in polynomial time.

We then plug that algorithm into the reduction from Cook-Levin theorem, which gives us a way to simulate *any algorithm running in Polynomial time* with a polynomial number of calls to a 3SAT solver. Again, a polynomial number of calls to a polynomial-time algorithm runs in polynomial time.

Finally, there is a simple non-deterministic algorithm that solves Graph-coloring in polynomial time: just guess a coloring and check if it's valid. So we use Cook-Levin to simulate this algorithm in polynomial time.

As you can imagine, each time we have to compose a reduction, the degree of our polynomial is going to get higher and higher. So it's entirely possible that $P = NP$ but graph colouring can only be solved in, say, $O(n^{100000000000000})$ time. This is still polynomial time, but it really doesn't buy us much in terms of practically solving problems.

# Answer
> 11 votes
If P=NP, that means there is for any given problem in NP, for example, the problem "Is $G$ $k$-colourable?", where $G$ is a finite graph and $k$ an integer, there is an algorithm to solve it in polynomial time.

Unfortunately, our problem is not in NP. We want to find a $k$-colouring for the minimum possible $k$. Now we can find the minimum possible $k$ in polynomial time just by repeatedly solving the problem above for $k=1,2,\ldots$, until it returns the answer "yes". (Note this happens by the time $k$ reaches the number of vertices, if not earlier, so only a polynomial number of instances are needed.)

But now that we know $k$, how do we find a $k$-colouring? Well, if $k$ equals the number of vertices, that's easy: every vertex must have a different colour. If $k$ is less than the number of vertices, then in any colouring (and we know one exists), there are two vertices $x$ and $y$ of the same colour (which must be non-adjacent). That means that we can combine $x$ and $y$ (remove them and replace them with a new vertex which is adjacent to every neighbour of $x$ or $y$), and the same colouring works for this new graph. So this new graph is also $k$-colourable, and has one fewer vertex.

So what we can do is run over all pairs of non-adjacent vertices $x,y$ and check whether the new graph formed by combining $x$ and $y$ is $k$-colourable, until we get an answer "yes" (this must eventually happen). We then repeat this process, keeping track of which original vertices were combined to form each current vertex, until the graph only has $k$ vertices. This divides the vertices of the original graph into $k$ sets, and we can just give each set its own colour to obtain a $k$-colouring of $G$.

# Answer
> 5 votes
The following roughly sketched algorithm, assuming P=NP, finds a 3 coloring of the input graph if one exists, in polynomial time. If there's no such 3 coloring, though, it never terminates.

First, learn to enumerate all possible algorithms (Turing machines), and to simulate computation of any such Turing machine on arbitrary input.

Second, learn to enumerate all possible algorithms with an attached poly-time alarm clock. (That means that we will be enumerating a special case of Turing machines that conceptually do two things in parallel; on one set of tapes, they compute the "primary problem", and on a separate tape they just count down to zero from a fixed one of functions n, 2\*n^2, 3\*n^3, ..., where n is the length of the input to the primary problem, halting the computation (perhaps prematurely from the perspective of the primary problem) once this countdown on the separate tape (called alarm clock) reaches zero before the primary problem is solved. So sometimes the computation is terminated because an output has been provided for the primary problem, and sometimes the computation is terminated by the alarm clock, with the output tape containing whatever it happens to.)

The exact order in which the Turing machines with an attached polynomial alarm clock are enumerated should be exhaustive: it should be such that we'll encounter every combination of a Turing machine and of an alarm clock function among the ones suggested above sooner or later.

Now, learn to simulate all these Turing machines with an attached polynomial alarm clock in parallel, starting them well spaced in time one by one. In particular, make sure that almost one half of the total running time is devoted to the first Turing machine with an attached polynomial alarm clock in the enumeration, almost one quarter of total running time to the second machine, almost one eighth of it to the third machine and so on. (We are making sure that each Turing machine in the enumeration gets a known constant fraction range of total run time, assuming we keep running at least till its first transition.)

How can we do that? Example: Simulate one transition of the first machine. Then the same again - one more transition of the first machine. Then one transition of the second machine. Than all this again: two more transitions of the first machine and one more of the second machine. Only then do the first transition of the third machine, followed by all that again (seven more transitions in total) before ever simulating the first transition of the fourth machine.

From time to time, a machine terminates, be it due to its alarm clock or to its having solved its primary problem (which will rarely consist of a production of 3 colorings of the input graph, but who cares). If a machine terminated, we check whether it has produced a valid 3 coloring of the input graph on its output tape, and if so, we terminate the entire simulation of all the Turing machines with attached alarm clocks, returning the same 3 coloring as the output.

To be honest, I haven't closely checked that I can amortize the overhead of switching attention from a machine to a machine, the overhead of iterating across the machines (i.e., generating the initial state of a new machine in the enumeration), and the overhead of checking the terminal states (whether a terminating machine stumbled upon a valid 3 coloring or not); but I can certainly make sure to spend more time on the simulated transitions of individual Turing machines than on all these kinds of overhead, i.e. the total overhead ends up less than 100%, again a constant factor.

Now, it is well known that the function version of the 3 coloring problem is self reducible to its decision version. There's a simple polynomial time algorithm for the decision problem (by P=NP) and therefore the self-reducing algorithm which actually reliably identifies an example 3 coloring in polynomial time whenever one exists, occurs **somewhere** in our enumeration of all Turing machines - and it occurs somewhere even with a liberal enough polynomial time alarm clock which allows it to complete in whatever time it needs. Good news is that we gave a fixed fraction of attention (of the time resource) to this particular machine in our multitasking simulation, therefore we have slowed it down just by a (huge) constant factor - by the other simultaneously simulated machines, and by the remaining up to 100% overhead. So even this specific "universal" simulation is capable of providing examples of 3 coloring in polynomial time. Quod erat promissum.

===

(I'd love to say that this simulation comes close to preserving even the optimum exponent of finding the 3 coloring, but that just wouldn't be true. The biggest problem in this respect is that the "universal" simulator may have fewer tapes and fewer states than the machine being simulated, and simulating even a single transition is a costly exercise; the simulation preserves polynomial time, but not the specific exponent.)

Unfortunately, any such simulation only becomes a polynomial time algorithm for finding 3-colorings if we now equip it with its own polynomial time alarm clock (thus slowing it down twice, and also guaranteeing that it terminates on any input within the specified time limit); and this last step is con-constructive. Unlike any part of the construction until now, we don't know which polynomial among n, 2\*n^2, 3\*n^3, ... should be chosen for the alarm clock. We just know that a sufficiently liberal alarm clock exists, such that if we attach it to our (otherwise specific) "universal" machine, we will obtain a polynomial time algorithm doing 3 colorings wherever they exist and rejecting (only) graphs that are not 3 colorable, or inputs that do not encode graphs.

The method of universal simulation can be extended even to your graph coloring problem with the help of the additional technique described in this answer. What gets messier is that we are then no longer able to filter out "wrong answers" that easily; if a machine offers us a 5-coloring, how do we know whether a 4-coloring exists? The sufficient solution is to just wait it out, either a 4-coloring will appear in the output of a better behaved child machine or not, before the master alarm clock runs out. Again, the last step will be non-constructive: we know that with a sufficiently liberal polynomial time alarm clock we'd get a polynomial algorithm giving us optimal colorings, but it's hard to tell which specific polynomial to choose if all we know is that P=NP. If we choose a too aggressive (insufficient) polynomial time alarm clock, not only we will sometimes fail to find the optimal coloring, but we will sometimes output a suboptimal coloring which we tried to wait out, but not patiently enough.

# Answer
> 2 votes
Having P=NP means there *is* a polynomial time algorithm. It doesn’t mean we *know* one, or we will *ever* know one, or we will ever be able to *prove* it runs in polynomial time.

And we might find there is an algorithm running in O(n^10000), which means we can actually solve *no instances of size \> 1*.

# Answer
> 1 votes
If P=NP, you can use Levin's Universal Search algorithm.

Here is a sketch:

Since the problem is in NP, you have a polynomial time verifier for it. Let's call it $V$.

Let $\\{M\_i\\}\_{i\in N}$ be an enumeration of all polynomial-time machines (e.g. take the enumeration of all Turing machines, add to them clocks to bound the running time to $n^k+k$).

Think of a matrix where on one side we put these machines and on the other side the number of steps from the machine that we run. So cell (i,j) will be the output of the i-th machine in the enumeration after j-steps of execution, using a universal Turing machine U that for simplicity say have at most quadratic overhead.

Here is your polynomial-time algorithm for finding the solution:

```
FindSolution(x)
for i := 0; ; i++ {
  for j := 0; j < i; j++ {
    y := U(i,j,x)
    if V(x,y) {
      return y
    }
  }
}

```

This will find a witness when there is an answer. If there is not an answer, it will continue indefinitely. If you have a polynomial verfier for the complement problem or if you have an upperbound on the run time, you can use it to also output NO answer.

How long would it take to find an answer? If the optimal algorithm is the i-th algorithm, and its running time is $n^k$, then we will find an answer when run the i-th algorithm for $n^k$ steps. By that point we would have run $i\*n^k$ for other algorithms. So overall it would be something like $O((i\*n^k)^2) = O(n^{2k})$.

In practice, this is likely useless though because even though $i$ is a constant, it will be very large, like the number of programs that you can write which has the same length as your polynomial algorithm, say if that has size 10KB, the constant would be something like $2^{160,000}$ (8 for a byte, 2 from above simulation overhead).

---
Tags: graphs, np, colorings
---