# Question
Title: Number of non-XOR gates needed to implement an n-bit boolean function
There are $2^{2^n}$ possible functions that have $n$ boolean inputs and a single boolean output. Some of these functions have very short boolean logic circuits. Some have longer circuits.

A classic result in circuit complexity is that, if you count the total number of gates needed to implement $f$, most $f$s take $\Theta(2^n/n)$ 2-to-1 boolean gates. I'm interested in a slightly different metric, where **you can use as many XOR gates as you want but you don't count them** (ditto for NOT gates, which are just a XOR with one input constant). So your circuit could have $n$ AND gates plus $2^n$ XOR gates, and I'd call that a circuit of non-XOR-size $n$.

I've figured out that it's possible to implement any $n$-input function $f$ using at most $2^{n/2+1}$ gates that aren't XOR or NOT. The strategy works by using $2^{n/2}$ AND gates (with XOR gates interspersed) to prepare a set of $2^{n/2}$ indicator bits that can be XOR'd together to make any function of $n/2$ bits. I then pretend the top $n/2$ bits of the input index register are "choosing" the sub-function to apply with the bottom $n/2$ bits, and use my indicator bits to prepare the $2^{n/2}$ possible sub-function outputs. I then use $2^{n/2}$ AND gates to mux out the desired sub-function output (selected by the top $n/2$ bits of the input index register).

I'm interested in knowing **is it possible to do better than $2^{n/2+1}$ AND gates**, or is that asymptotically optimal.

# Answer
> 3 votes
By counting circuits, $2^{n/2 + 1}$ appears to be close to asymptotically optimal.

Let $C\_{n,k}$ be the number of distinct circuits with $n$ bits and $k$ AND gates.

We lower bound $C\_{n,k}$ by noting that we need to choose $k$ such that there is at least as many possible circuits as possible functions, i.e. $2^{2^n} \leq C\_{n,k}$.

We upper bound $C\_{n,k}$ by noting that every AND gate takes as input a bit which may have had each initial input and each output of a previous AND gate and possibly the constant 1 XOR'd into it. For the first AND gate there are $n + 1$ bits that may or may not be xored into each input of rht AND gate. For the second AND gate there are $n + 2$ bits, for the third $n+3$, and so forth. Then there's $n+k+1$ choices for what to xor into our output bit. Thus $C\_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$.

Now we know $2^{2^n} \leq C\_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$. By omitting the $C\_{n,k}$ in the center we get an inequality in terms of $k$ and $n$ that we can use to bound $k$ in terms of $n$ as follows:

$$\begin{align} 2^{2^n} &\leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1} \\ &= 2^{n+k+1} \prod\_{i=1}^k 4^{n+i} \\ &= 2^{n+k+1} 4^{\sum\_{i=1}^k n+i} \\ &= 2^{n+k+1} 4^{kn + k(k+1)/2} \\ &= 2^{2kn + k^2 + 2k + n + 1} \end{align}$$

Now we start manipulating both sides:

$$\begin{align} 2^{2^n} &\leq 2^{2kn + k^2 + 2k + n + 1} \\ 2^n &\leq 2kn + k^2 + 2k + n + 1 \\ 0 &\leq k^2 + k(2n + 2) + (n + 1 - 2^n) \end{align}$$

Finally, find the quadratic roots where the inequality switches, and focus down to the asymptotically dominant term of the positive root:

$$\begin{align} k &= \frac{-2n -2 \pm \sqrt{(2n+2)^2 + 4 \cdot (2^n - n - 1)}}{2} \\ &= -n - 1 \pm \sqrt{n^2 + 2n + 1 + 2^n - n - 1} \\ &= -n - 1 \pm \sqrt{n^2 + n + 2^n} \\ &\in \Omega \left(-n -\frac{1}{2} + \sqrt{n^2 + n + 2^n} \right) \\ &= \Omega \left(\sqrt{2^n} \right) \\ \end{align}$$

So it appears that $k$ must be asymptotically at least $\Omega(\sqrt{2^n})$ in order for there to be enough circuits to cover all of the possible functions.

---
Tags: asymptotics, circuits
---


# Question
Title: Prove that the depth of every vertex in a cycle is $\le \lfloor \frac{n}{2} \rfloor$ in a breadth first search?
Suppose I have an undirected graph that consists only of a cycle. Each vertex has a depth value that must be $1$ greater than its predecessor (i.e. if we reach vertex $F$ from vertex $C$ which has a depth of $2$, then $F$ has a depth of $3$). The beginning vertex has a depth of $0$. I need to show that every vertex must have a depth $\le \lfloor \frac{n}{2} \rfloor$.

I know that because the graph is only a cycle, every vertex must have a degree of $2$. And when performing a breadth first search, each vertex (except for the beginning vertex) will only have one vertex to choose, as the other connected vertex would be its parent. This would create a kind of "tree" shape where every node except the root has one child, and would mean that the maximum depth is $\le \lfloor \frac{n}{2} \rfloor$. I'm not sure how to phrase this as a proof, though.

# Answer
There may be other ways to prove your claim, the simplest seems to me is by induction on $n$.

**Base case :** $n=3$, that means input graph is a triangle and it is easy to see that in this case maximum depth is $\le \lfloor \frac{n}{2}\rfloor$

**Inductive case:** Suppose that depth of every vertex is $\le \lfloor \frac{k}{2}\rfloor$ in $k$ cycle graph want to prove that depth of every vertex is $\le \lfloor \frac{k+1}{2}\rfloor$ for $k+1$ cycle graph.

Hint for Inductive case: Going from $k$ cycle to $k+1$ cycle means we have added one vertex to any one of the edge ( as we know its both endpoints have depth $\le \lfloor \frac{k}{2}\rfloor$ (due to induction ) ) of the $k$ cycle graph it means depth of both endpoints in $k+1$ cycle will be $\le \lfloor \frac{k+1}{2}\rfloor$.
> 0 votes

---
Tags: graph-traversal
---


# Question
Title: Why creating an if condition after an if-else condition?
I try to understand and apply nested Monte Carlo Research. Yet, after reading its designer's paper I didn't understood why he added an if after an if-else condition. Shouldn't the last if be always skipped ?

Indeed, in `nested(position, level)` we can find at line 3 and 5 if and else conditions. When would the second if condition on line 7 would be read then ?

# Answer
> 1 votes
From what I understand, the `if-else` and `if` are not correlated. They are executed independently.

This structure would perhaps explain better:

```
if
 -- statement 1
else
 -- statement 2
end

# END OF IF ELSE BLOCK

if
 -- statement 3
end

```

# Answer
> 0 votes
At line 4 and 6 you have an affectation with $move$ at left side, so an execution of that if else can modify $move$. At line 7, you have a test implying $score \ of \ move$, i don't know this notation but i guess that we get the score of the calculated move.

Thus, line 7 is here to test the new value of move provided by lines 4-6.

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


# Question
Title: CURE algorithm: what does moving the representative points towards the centroid do?
The CURE algorithm is a method of clustering data. An outline of it can be found here on slide 5: https://www.slideshare.net/ellepiu/cure-clustering-algorithm. I personally learnt it from this video: https://www.youtube.com/watch?v=JrOJspZ1CUw, where the algorithm is explained at 7 minutes.

This is my understanding of the process of CURE. Let's assume that the data set is large enough such that we have to store a portion of the data on disk.

1. Take an amount of the data set that fits onto the computer, and cluster (perhaps hierarchically) to initialise clusters.
2. For each cluster: pick k representative points, and move each a fixed distance, $\alpha$, towards the cluster centroid.
3. For each data point on disk, assign it to the cluster with the representative point it is closest to.

To me, this selection of representative points seems like a really arbitrary thing to do, and I don't really see the logical process behind choosing to do this.

For any two data sets representing the same thing, it could be possible (even likely) that one set of clusters pre-representative-point-moving for one data set would be the same as the set of clusters post-representative-point-moving for the other.

Could someone please help explain in more detail the reasoning behind doing this? (Beyond just the basic pseudo-algorithm I have seen.)

**My thoughts**

I think that when moving the representative points towards the centroid of each cluster, this is equivalent to shrinking the boundary of the cluster. Once this is done, the data points that remain outside of the boundary are eliminated as clusters. But I'm not sure if this is correct.

# Answer
If I'm understanding your question correctly, you are interested in why the representative points are chosen as such, why they are merged and why this works. I'll first go over some background for CURE, then I focus on this particular question.

## Background: why CURE?

I think we should start with the *intention* of CURE. To see that, we look at slide 14:

Here, CURE is compared with BIRCH and MST. We see that BIRCH succeeds in identifying the top ellipsoid pair as different, but fails to detect the large disk as a single cluster. BIRCH seems to only support same-sized clusters, So BIRCH doesn't make some clusters big enough and others too big. MST successfully classifies the disk as a single cluster, but fails to separate the ellipsoids on top. MST makes the clusters too big.

So, BIRCH is an attempt at trying to 'hit' the sweet spot between BIRCH and MST, in the hope of creating better clusters. In this example, it seems to be working pretty well.

Alright, back to the main question, why are the representative points handled as such? Suppose CURE would output the BIRCH result as an intermediate step. It then looks at the representative points of the light-blue and black half-disks. As the representative points are close, CURE would decide to merge these two half-disks into a full disk, which is good.

Okay, that's nice and all, but what prevents CURE from merging the two ellipsoids above, as BIRCH does? CURE doesn't do this (or is at least unlikely to do so), as the representation points are *well scattered*. This means that it is only likely that two clusters that are touching each-other on a location with high density get merged (as otherwise many representatives being close has low probability). As the two ellipsoids only touch each-other at points with low density, CURE (with carefully chosen parameters, no doubt) detects them as different.

## How to merge?

We've seen that CURE sometimes has to merge two smaller clusters into a bigger one. The question is how to handle the representative points. The simplest way to do this is to simply add them to the new cluster. But this isn't a good idea. For their original clusters, the representation points were well scattered. But if we simply use the same points for our merged cluster, this is no longer the case.

To see this, consider the example of the two half-disks in the clustering provided by BIRCH. Suppose that the representation points form the outline of a half-disk slightly smaller than the ones given. Now, if we merge the clusters, the representation points lie a bit far away from the center. They are no longer well scattered.

This is a problem, because if there were another disk-like cluster nearby ('connected by a chain of outliers', as the authors would say), the fact that the representation points are too far to the edge of our newly merged disk means we're likely to put the two disks in a single cluster. Note that this process can occur many times at different hierarchical levels, so if we don't solve this, we won't get nice results.

So, the solution is to move the representation points a bit closer to the center, as this makes them more well-scattered and therefore decreases the probability that we make a bad merge.
> 2 votes

---
Tags: algorithms, machine-learning, clustering
---


title: Complexity of while loop using series

text:
# Question
Title: Complexity of while loop using series
For the following code fragment:

```
i = 1;
s = 1;

while(s <= n) {
    i++;
    s = s+i;
    printf("x");
}

```

How can we go about proving the time complexity of this code is $\Theta(\sqrt{n}))$?

Usually, I use sigma series analysis to figure the time complexity but I am having trouble turning this code into series notation and then using the series to find out the time complexity.

# Answer
> 1 votes
As you see, in each iteration `i` is increased by `1`. Hence, value of `s` would be $1 + 2 = 3, 1 + 2 + 3 = 6, 1 + 2 + 3 + 4 = 10, \ldots, \sum\_{i=1}^{k}= n$

Hence, $k$ is the time complexity of this code. As we know that $\sum\_{i=1}^{k} = \frac{k(k+1)}{2} = \Theta(k^2)$, and $\Theta(k^2) = n$, we can conclude that $k = \Theta(\sqrt{n})$.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


title: Decision problem for a Regular Langauge

text:
# Question
Title: Decision problem for a Regular Langauge
I'm not sure if my logic is correct when it comes to the algorithm for decision problems. The concept is confusing me when I fail to distinguish its answer from that of a proof.

For example:

Given two finite automata $M\_1, M\_2$ that operate on a common alphabet, find an algorithm to show that:

$$L(M\_1) \subseteq L(M\_2)$$

And how I viewed it was:

1. Find a string $w$ from the alphabet $\Sigma$
2. Feed $w$ to $M\_2$; if accepted then $w$ is part of $L(M\_2)$
3. Feed $w$ to $M\_1$; if accepted then $w$ is part of $L(M\_1)$
4. If $w$ was accepted by $M\_2$ and $M\_1$, then $L(M\_1) \subseteq L(M\_2)$
5. Otherwise reject

Unlike proofs which require mathematical arguments, algorithms for decision problems seem more like a logical flow or sequence description. If it were a proof I would have to perhaps design a language or expression using properties and lemmas where as here I just describe the process of determining if the statement can be answered (via "yes" or "no").

# Answer
> 3 votes
Your algorithm is not really specified completely, since you don't explain how you choose the word $w$. However, even once you do specify how $w$ is chosen, your algorithm will be incorrect. The reason is that it is completely symmetric in $M\_1$ and $M\_2$. In other words, if the algorithm accepts on the pair $(M\_1,M\_2)$, then it will also accept on the pair $(M\_2,M\_1)$. This means that it will necessarily fail for machines satisfying $L(M\_1) \subseteq L(M\_2)$ but $L(M\_2) \nsubseteq L(M\_1)$.

Presumably in class you were shown other decision algorithms for regular languages. I suggest you try to emulate them. As an example, here is an algorithm that determines whether $L(M) \neq \emptyset$, for a DFA $M$.

> Input: A DFA $M = \langle \Sigma, Q, q\_0, F, \delta \rangle$.
>
> Accept if some state in $F$ is reachable from $q\_0$, and reject otherwise.

(In class you will probably need to be more verbose.)

To show that this algorithm is valid, we need to show two things:

1. If $L(M) \neq \emptyset$, then the algorithm accepts.
2. If $L(M) = \emptyset$, then the algorithm rejects.

To prove the first part, suppose that $w \in L(M)$. By definition, the state $\delta(q\_0,w) \in F$ is reachable from $q\_0$, so the algorithm accepts.

To prove the second part, we will prove the contrapositive: if the algorithm accepts, then $L(M) \neq \emptyset$. Suppose that some state $q \in F$ is reachable from $q\_0$. This means that there is some path from $q\_0$ to $q$. If $w$ is the concatenation of all symbols on this path, then $\delta(q\_0,w) = q \in F$, and so $w \in L(M)$, showing that $L(M)$ is non-empty.

(Once again, in class you will probably need to be more verbose.)

# Answer
> 1 votes
This algorithm isn't correct. There could be some $w \in \Sigma ^\* : w \in L(M\_1) \wedge w \in L(M\_2) $ although $L(M\_1) \nsubseteq L(M\_2)$ Assuming in your first step the algorithm finds such a $w$, the algorithm would output the wrong answer.

To my mind your exercise is formulated in a very strange way, but i think you should find an algorithm $A$ with $\forall finite automata M\_1,M\_2: A(\<M\_1,M\_2\>) = 1 \Leftrightarrow L(M\_1) \subseteq L(M\_2)$

---
Tags: algorithms, regular-languages, decision-problem
---


# Question
Title: What happens to a file after too many copy-pasting?
Let's say we're talking about a 1 GB video file. It's copy-pasted from hard disk D1 to the hard disk D2, then from D2 to D3, and so on, all using Windows. If we continue this process for like 1 million times, what would the resultant file look like? Do error bits accumulate and finally corrupt the file?

# Answer
Once a single-bit error is introduced into a file, the file is corrupt. File systems, disk drivers, and hardware on the disk itself have checksums, error correction codes, and facilities to detect bad sectors to limit the probability of write (or read) errors, but it's not 100% (but it better be close to 100%, otherwise my disk isn't reliable).

In general, the way to compute the probability of corruption:

Let's say the probability of a single bit error occurring during a file copy is **P**. (P should be really, really low, otherwise, the disk or media wouldn't be reliable).

And let's assume that a file has a size **N** measured in bits (e.g. a 1 GB file would be 8 billion bits or so).

So the probability of the first bit in the file not getting corrupted is: **(1-P)**. And so it follows that the probability of all bits not getting corrupted during a transfer is **(1-P)N**

Now let's say you copy the file **X** times. Therefore the probability of the file not getting corrupted after X transfers is **(1-P)NX**. Or rather, the probability of corruption after X transfers is **1 - (1-P)NX**
> 3 votes

---
Tags: error-estimation
---


# Question
Title: Transforming an array into one with descending order
# Problem Description

Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) *descending order*: we require that $\hat{a}\_i \geq \hat{a}\_j$ for all $1\leq i\<j\leq n$. Here an operation means either increasing or decreasing an element by $1$.

For example, it requires at least $4$ operations to turn the array $\[1,2,3,4\]$ into descending order. One solution is increasing the first element by $2$, increasing the second element by $1$, and decreasing the last element by $1$ (then the new array is $\[3,3,3,3\]$, which is in decending order).

My questions:

* Is the problem NP-hard?
* If not, what algorithm solves this problem with the best time complexity?

# My efforts

We can write this problem as an integer linear programming. Say the elements in the array are $a\_1,a\_2,\ldots,a\_n$, and those in the new array are $\hat{a}\_1,\ldots,\hat{a}\_n$ then the problem is essentially an interger programming:

$$ \begin{align\*} \text{minimize}\quad &\left|\hat{a}\_1-a\_1\right|+\cdots+\left|\hat{a}\_n-a\_n\right| \\ \text{subject to}\quad &\hat{a}\_1\ge\cdots\ge\hat{a}\_n \end{align\*} $$

or equivalentlly

$$ \begin{align\*} \text{minimize}\quad &t\_1+\cdots+t\_n \\ \text{subject to}\quad &\hat{a}\_i-a\_i\le t\_i, &i=1,\ldots,n\\ &-\left(\hat{a}\_i-a\_i\right)\le t\_i, &i=1,\ldots,n\\ &\hat{a}\_1\ge\cdots\ge\hat{a}\_n \end{align\*} $$

But it seems not to help because the coefficient matrix is not totally unimodular, thus we cannot relax it to linear programming.

I also find a property of optimum solutions:

> If some consecutive elements are originally in non-descending order, then they must be the same in an optimum solution.

I don't know whether this property helps.

# Answer
> 2 votes
The LP you gave always admits a integral optimal solution.

Suppose there is a fractional optimal solution $\hat{a}\_1,\ldots,\hat{a}\_n$. For every $i$, fix the other elements $\hat{a}\_j$ with $j\neq i$ and consider the optimization on $\hat{a}\_i$, that is, minimizing $|\hat{a}\_i-a\_i|$ subject to $\hat{a}\_{i-1}\geq\hat{a}\_i\geq\hat{a}\_{i+1}$. It's easy to see that the optimal $\hat{a}\_i$ is either $a\_i$ itself, or equal to one of its neighbors $\hat{a}\_{i-1}$ or $\hat{a}\_{i+1}$.

This observation could be generalized. Suppose in an optimal solution we have $$\hat{a}\_i=\hat{a}\_{i+1}=\cdots=\hat{a}\_j=\lambda.$$ Now we fix $\hat{a}\_1,\ldots,\hat{a}\_{i-1},\hat{a}\_{j+1},\ldots,\hat{a}\_n$, and consider the optimization on $\lambda$. This is the simplest facility location problem, with the (convex and unimodal) objective $\sum\_{k=i}^j|\lambda-a\_k|$ subject to $\hat{a}\_{i-1}\geq\lambda\geq\hat{a}\_{j+1}$. It is optimized when $\lambda$ equals $\hat{a}\_{i-1}$ or $\hat{a}\_{j+1}$, or $\lambda$ coincides with some of the $a\_k$'s (actually the median of $a\_i,a\_{i+1},\ldots,a\_j$).

Upon the above observations, we could conclude that in a general problem where we want to minimize the $L\_1$ distance from a real number sequence $\langle a\_i\rangle$ to descending sequences:

> There is always a optimal solution such that each $\hat{a}\_i$ coincide with some $a\_k$.

To be formal, this conclusion could be deduced from examining the potential function $\Phi(\langle\hat{a}\_i\rangle)=|\\{\hat{a}\_i\\}\setminus\\{a\_i\\}|$.

Therefore, you can solve the linear program which gives directly the minimum number of operations. An alternative polynomial-time algorithm by the dynamic programming you suggested, but first sort $A=\\{a\_i\\}$ and compute $$C\_i(v)=\min\\{C\_i(v'),|a\_i-v|+C\_{i+1}(v)\\}$$ where $v\in A$ and $v'$ is the largest number smaller than $v$ in $A$.

# Answer
> 3 votes
There is an efficient dynamic programming solution if the input domain is small.

Let $C\_i(v)$ be the cost of increasing/reducing elements such that $\hat a\_i = v \wedge (\forall j \>i)\[\hat a\_{j} \leq v\]$.

It should be obvious that $C\_n(v)$ is simply $|a\_n - v|$, and thus computing $C\_n$ completely is easy.

Then $C\_{i}(v)$ is $|a\_i - v| + \min(C\_{i+1}(0), C\_{i+1}(1),\dots,C\_{i+1}(v))$. Using this we can compute $C$ as a table, using $C\_{i+1}$ to fill $C\_i$, working backwards all the way to $C\_1$. Then choosing the minimal element of $C\_1$ and working forwards again you have found the solution.

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


# Question
Title: Looking for a good algorithm to divide the nodes of a complete graph into groups
I have a set of locations, around 100, I want to divide into groups.

I say these locations are in a graph because the geometric proximity (straight line distance) doesn't matter to me, and I have a matrix of the distance (non straight line distance) and time, that would take to travel from any location to another. Either one, time or distance, can be used as edge weights for this complete graph.

The idea is to assign a group of locations to a person that will visit the locations in it, (there is no obligation to do a traveling salesmen or visit them in a specific order or to avoid passing on a repeated node).

Ideally these groups have a minimum of 8 locations, and a maximum of 11 locations. (For simplicity maybe a set amount of 10 per group would suffice). And I want to minimize the sum of weights needed to visit all the nodes in a group at least once.

All locations must belong to one group, and only one group.

Where do i go from here? I'm kind of rusty on graph theory. Is there a good algorithm for this already? It doesn't need to be optimal and I do understand that this will probably be an NP hard problem and not very efficient. Because i'm treating it as a graph i keep finding graph algorithms but most i find are not suited for weighted graphs or complete graphs.

# Answer
One possible approach would be to use local search. This probably won't find the optimal solution, and there are no guarantees, but if you're lucky, it might find a solution that is decent.

In local search, given a candidate solution, you need a way to randomly pick a neighboring solution. In the context of your problem, one way to do that might be to pick a pair of groups and a vertex $v$ in the first group, and remove $v$ from the first group and add it to the second group. (This will only be legal if the first group is not already at the minimum size, and the second group is not already at the maximum size.)

You could then apply a technique like simulated annealing. You'll probably need to experiment with the tuning parameters, and experiment with the method, to see whether it produces useful solutions or not.

This will require you to be able to quickly compute the effort associated with a single group, given the list of vertices in the group. You might want to ask separately about that problem. It sounds related to the Traveling Salesman Problem, which is NP-hard, but there are off-the-shelf solvers that implement sophisticated algorithms for finding a solution, and for the group sizes you are talking about (8-11 vertices), this might be relatively fast. The twist in your situation is that the TSP doesn't allow visiting a vertex more than once, but it sounds like you are willing to allow repeated visits, so we need to make adjustments to make to allow that. The following method should suffice: use an all-pairs shortest paths algorithm to compute the distance $d(u,v)$ between each pair of vertices, then replace the edge weight on the edge $u \to v$ with $d(u,v)$, then find the TSP solution; after this adjustment, no repeated visits will be needed any longer.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: If $h(s)$ is an admissible heuristic, is $\sqrt{h(s)}$ admissible?
I was thinking yes because $0 \leq \sqrt{h(s)} \< h(s)$ but I'm not entirely sure.

# Answer
> 1 votes
Yes, the basic condition for a heuristic being admissible is that it is always less than the actual cost, and the rest follows by the transitivity of the less-than-or-equal-to relation.

See the all-knowing wiki for the background. I'll steal the notation from there for some measure of consistency.

Or, in a rather unnecessary mathematical formulation, if $\forall s, h(s) \leq h^{\ast}(s)$, where $h^{\*}(s)$ is the actual cost then $h$ is admissible.

Assuming $x \in \mathbb{R}^{\geq 0}$ and (thanks Yuval) $x\geq 1$ (i.e. we don't have some weird situation where $\leq$ breaks, etc.), $\sqrt{x} \leq x$.

So $$\forall s, h(s) \leq h^{\ast}(s) \Rightarrow \forall s, \sqrt{h(s)} \leq h(s) \leq h^{\ast}(s) \Rightarrow \forall s, \sqrt{h(s)} \leq h^{\ast}(s)$$ therefore $\sqrt{h(s)}$ is admissible.

If $0\leq h(s) \< 1$, then $\sqrt{h(s)} \geq h(s)$, and is not necessarily admissible (it may still happen to be, but there's no guarantee).

---
Tags: search-algorithms, heuristics
---


# Question
Title: Equisatisfiability in the reduction from 4-SAT to 3-SAT
So If I understood correctly, the conversion from 4-SAT statement to 3-SAT statement follows the following approach:

(a or b or c or d) -\> (a or b or z) and (-z or c or d)

Where the z is a new literal. However, with 4 literals there exists 4^2 different permutations (a or b or c or d) and (-a or b or c or d) and (a or -b or...) and ...

If I convert each of the clauses with the approach above (add always new literal z\_n and it's negation) like:

(a or b or z) and (c or d or -z) and (-a or b or z\_2) and (c or d or -z\_2) and ...

, then the resulting 3-SAT statement is indeed satisfiable. Even if the 4-SAT statement with the all permutations for 4 literals is not. They should be equisatisfiable?

# Answer
You're right in saying that they should be equisatisfiable. *And they are.*

I'm not sure why you think converting your unsatisfiable $4-\text{SAT}$ instance into a $3-\text{SAT}$ instance would make it satisfiable. Because it doesn't.

If a $4-\text{SAT}$ instance is unsatisfiable, then no matter how you choose to assign truth values to your variables, there will be some clause that is not satisfied. Without loss of generality, let that clause be $(a \vee b\vee c\vee d)$. Since this clause is not satisfied by your assignment, it follows that all of $a, b, c$ and $d$ are false.

Now converting this into a $3-\text{SAT}$ instance gives you these pair of clauses: $(a \vee b \vee z)(\neg z \vee c\vee d)$. Note that since $a, b, c$ and $d$ are all false, in order for both of these clauses to be satisfied, both $z$ and $\neg z$ need to be true, which is impossible.

In other words, the resulting $3-\text{SAT}$ instance is also unsatisfiable.
> 10 votes

# Answer
So if I get it correctly, you started with the $2^4$ many clauses

* $a \vee b \vee c \vee d$
* $\neg a \vee b \vee c \vee d$
* $a \vee \neg b \vee c \vee d$
* $\ldots$
* $\neg a \vee \neg b \vee \neg c \vee \neg d$

There does not exist a valuation to the variables in $\\{a,b,c,d\\}$ that satisfies all of them, so these 16 clauses are together unsatisfiable.

Now we translate these clauses into 3CNF. This yields 32 clauses:

* $a \vee b \vee z\_0$, $\neg z\_0 \vee c \vee d$
* $\neg a \vee b \vee z\_1$, $\neg z\_1 \vee c \vee d$
* $a \vee \neg b \vee z\_2$, $\neg z\_2 \vee c \vee d$
* $\ldots$
* $\neg a \vee \neg b \vee z\_{15}$, $\neg z\_{15} \vee \neg c \vee \neg d$

This set of clauses should be equisatisfiable to the set of clauses given above as the translation to 3CNF yields an equisatisfiable formula.

And it actually *is* equisatisfiable. To see this, assume that we have a model $m$ for the 3CNF formulation. This assigns values to all variables in $\\{a,b,c,d,z\_0,z\_1, \ldots, z\_{15}\\}$. We know that $m$ (restricted to $\\{a,b,c,d\\}$ is also a model for the original CNF), as for every $i \in \\{0, \ldots, 15\\}$, we know that the if $z\_i$ has a false $\mathbf{false}$, then one of the first two literals of the original $i$th clause have to hold, and if $z\_i$ has a $\mathbf{true}$ value, then one of the latter two literals of the original $i$th clause have to hold.

Since the original 4CNF instance is unsatisfiable, and we know that from every model for the 3CNF SAT instance we can obtain a model for the 4CNF instance, we now know that the assumption that there exists a satisfying model for the 3CNF SAT instance exists must be wrong.
> 5 votes

---
Tags: logic, satisfiability
---


title: Comparison between MA and $P^{NP}$

text:
# Question
Title: Comparison between MA and $P^{NP}$
I am aware that $MA \subseteq ZPP^{NP} \subseteq \Sigma\_2^{P}\cap \Pi\_{2}^{P}$ and also $NP^{BPP} \subseteq MA \subseteq AM \subseteq \Pi\_{2}^{P}$.

My question is: In this whole thing, where does $P^{NP}$ lie? (Obviously, $P^{NP} \subseteq ZPP^{NP}$) But, what about the relationship between $MA$ and $P^{NP}$? Which is contained in which one?

Intuitively, It is known that $MA\_{EXP} \not\subset P/poly$, but for $EXP^{NP}$, no polynomial size circuit lower bound is known. Does that mean $P^{NP}$ is contained in $MA$?

# Answer
Apparently, no relationship is known between $MA$ and $P^{NP}$. Even $BPP$ ($\subseteq MA$) vs $P^{NP}$ problem is still open. It is conjectured though that $MA = NP$ (Under standard hardness assumptions). So, it is likely that $MA \subseteq P^{NP}$.
> 1 votes

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Segmentation technique for handwritten text (cursive and unconstrained)
Although I am new to the computer vision domain, I am tasked with automating handwritten text recognition from bank cheques. I first did some preprocessing(blurring and binarization) and then dilated it so that I could segment the words. But since the words are handwritten (cursive and unconstrained), the segmentation is failing most of the time. I read up on some research papers and it seems you can use neural networks for segmentation.Is that the correct approach? Are there other alternatives? Can someone shed some more light?

# Answer
> 1 votes
As mentioned in comments there is no one right way to recognize handwriting. That said, Here are two techniques you could explore.

Watershed segmentation works by creating a topological map of the image to determine which objects distinct and with or without connection to other objects. I recommend it to you because watershed excels at naturally or man-made round objects. It has been documented for use in handwriting recognition. This is an easy one to get started with too. You can simply call watershed in matlab, OpenCV, or scikit

Machine Learning / Deep Learning (ML) is a daunting term to some but we usually get the chance to stand on the shoulders of giants such that ML on images is about as difficult as editing an large collection of vacation photos. Bag of words is a particular technique which works well on finite object sets. Note that like most ML BoW requires pre-classified training materials so be prepared to provide at least 100 different samples of a cursive uppercase 'Q' along with all the other characters you wish to recognize. Nonetheless, if you've got the time and resources to train it, a ML solution can be incredibly powerful in handwriting recognition.

---
Tags: image-processing, computer-vision
---


# Question
Title: For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time?
For some given $n$, how can we check whether there exists $a,b \in \mathbb{N}$ ($b \> 0$) such that $a^b = n$ in polynomial time with respect to the number of digits in $n$?

# Answer
> 8 votes
Note that $b$ is upper bounded by $\log n$, so you can go over all possible integers $x\in\left\[1,\lceil\log n\rceil\right\]$, and for each $x$ check whether the equation $a^x=n$ has an integer solution, i.e. whether or not $n^{\frac{1}{x}}$ is an integer. You might be interested in root finding algorithms.

# Answer
> 2 votes
Take Ariel's answer first.

If the exponents get so large that say $a ≤ 10^{12}$, checking that a is an integer is usually very fast - calculate log n *once*, and usually $2^{log n / b}$ is nowhere near an integer.

If the exponents get even larger and a gets smaller, instead of iterating over b and calculating a, we can iterate over values of a from some value down to 2, calculate b = $log n / log a$ and check if that is close to an integer. , For example if n has 1 million digits, then for b ≥ 80,000 we have a ≤ $10^{13}$ and ordinary floating point operations can usually find that a is not an integer. If b ≥ 200,000 then a ≤ 100,000 so instead of iterating for b from 200,000 upwards we iterate for a from 100,000 down to 2 and check if b is an integer.

Doing all the checking in polynomial time in log n is easy, keeping the degree low is harder. There are much less than log n large values b or a to check, usually each in constant time. For smaller b, you obviously only need to check primes b.

You can also check for small prime factors of n. Say n has a factor $2^{57}$, then we only need to check b = 3 and b = 19. If n has any small prime factors, this will be quite helpful.

---
Tags: complexity-theory, polynomial-time
---


title: Graph families with high $k$-community

text:
# Question
Title: Graph families with high $k$-community
Just a quick question here, is there a known description of a graph family where for every graph $G=(V,E)$ it holds that for every $(u,v) \in E$ you have $|N(u) \cap N(v)| \geq k$? There was a definition for such graph as $k$-community. Even non-trivial examples (e.g., cliques) might be interesting.

Also, how to construct a graph which is a $k$-community, but does not have a $k+2$ clique? Is it possible at all?

Note that non-trivial cases also exclude not connected graphs and 1-vertex graphs.

# Answer
Strongly regular graphs fit the bill, i.e., one property is that adjacent vertices have (exactly) $\lambda$ common neighbors. Paley graphs should give you an infinite family and an explicit construction.
> 1 votes

---
Tags: graphs, clustering
---


# Question
Title: How to write decoder for compressed stringified objects
**Aim**: schema aware transformation.

I've written a code(in js) which can transform data `{projectDetails: [ {detail : {}, id : "gwl" }], name: "amit"}` into string `@gwl|amit`. But I'm not able to complete the decoder to transform it back.

**Problem**: logic to transform string back to object

**In detail**

Consider that following schema is given to transform data into string and back to object.

```
var schema = {
    type: "object",
    properties: {
        "projectDetails" : {
            type: "array",
            properties: {
                "detail" : {
                    type: "object",
                    properties: {
                        "first" : { type: "string"},
                        "last" : { type: "string"}
                    }
                },
                "id" : { type: "string"}
            }
        },
        "name" : { type: "string"}
    }
}

```

Consider following chars to understand the transformation;

* | : boundary indicator. To separate consecutive dynamic data fields.
* ^ : next field(set of fields) is/are repeated array item
* $ : empty value
* \# : missing, null, undefined field
* @ : empty object or array
* ! : missing, null, undefined object or array
* Y : True
* N : False

Example: Transform

```
{projectDetails: [ {detail : {}, id : "gwl" }], name: "amit"}
> @gwl|amit

{projectDetails: [ {detail : {} }], name: "amit"}
> @$amit

```

**Problem**: transform string back to object

**Implementation**

I iterated the schema to updated every data field with possible next char may occur in transformed string to identify the boundary of current field. It can help to reduce number of comparisons while decoding.

E.g. for the field `id` in above schema next possible chars in transformed string can be : `[$^|#]`.

Since this way complicate the solution, following regular expression can be used `(.*?)([|^#@!YN])` to read next field always. (it returns 2 matches every time, if first match is empty just ignore it and read further.)

**Challenge**

```
> @$

```

For above string, my decoder fails. Why? Because this is how I transform the string back.

* I read the schema.
* Since `projectDetails` is an array type, I loop
* Since array's item is of type object, I use recursion
* `detail` is object type and since the first field value in string is `@`. I mark it empty
* I read next field and mark it with `$`
* I come out from the recursion.
* Since there is no array separator, I read next field of the root object.
* I find nothing in transformed string to read.

*Note* I don't want to convert transformed string into array of fields. It'll cause issue in case of big objects.(I've faced it with other project)

# Answer
Found the answer.

As described in question about encoding schema, there can be multiple objects falling to same encoded string. Hence I was facing the difficulty to write the decoder.

To solve the above problem, I've added 2 more chars to know the start of the object/array;

```
| : boundary indicator. To separate consecutive dynamic data fields.
^ : next field(set of fields) is/are repeated array item
$ : empty value
# : missing, null, undefined field
@ : empty object or array
! : missing, null, undefined object or array
Y : True
N : False
{ : object start
[ : array start

```
> 0 votes

---
Tags: algorithms
---


# Question
Title: The Potential function for Fibonacci heaps
I am trying to get a better understanding of Fibonacci Heaps. I noticed the following definition for the potential function. $$ \Phi(F)=|W| +2\cdot \text{# marks}. $$ I do not understand why it is defined that way, or what its significant is. I am hoping somebody can explain it to me.

# Answer
> 3 votes
Because it works.

In amortized analysis, *you* pick the potential function. While it's usually related to some insight about the data structure or algorithm work, is it per se completely arbitrary. The only important thing is that if you write down the telescoping sum -- which is always set up in the same way! -- you can derive a good estimate.

---
Tags: algorithm-analysis, data-structures, amortized-analysis
---


title: lw and sw hazards example MIPS

text:
# Question
Title: lw and sw hazards example MIPS
The below example confused me:

```
lw $r0, 4($r0)
sw $r0, 4($r0)
add $r0, $r0, $r0

```

Using MIPS 5 stage execution what are the hazards we have 1) without forwarding 2) with forwarding only in the stage of execution (exe or alu) 3) with forwarding. Add nops to eliminate hazards.

# Answer
The hazard stems from the fact that the `lw` instruction updates register \\$r0 at the 5th stage of the pipe (write-back) while the `sw` and the `add` instructions require the updated data at the 2nd stage of the pipe (decode/read).

Putting everything on a single time line (assuming the `lw` execution begins at time $t=1$), the correct value of \\$r0 will be available not before $t=4$ and the other instructions must be stalled (at the decoding phase) until this data is available. After $t=4$ a forwarding unit can be used to forward the data to the correct place, e.g., to the execution stage for the `sw` or to the decoding stage for the `add` (if needed).
> 1 votes

# Answer
Look at data dependecies:

```
lw $r0, 4($r0)
sw $r0, 4($r0)
add $r0, $r0, $r0

```

At line 1, `$r0` is being written to. At line 2, `$r0` is being read. Therefore we have a RAW hazard, read after write.

There is also a WAR hazard between line 2 and 3 because the register is being written after reading it.
> 1 votes

---
Tags: computer-architecture, cpu-pipelines, mips
---


# Question
Title: Can I assume that a percentage of the time can be parallelized?
I study computer science and hardware. Some problem are about parallel computing and applied Amdahl's law. For instance, some calculation is that the sequential part of a program takes x seconds and the parallel part takes y-x seconds. Can I then safely assume that it is the same percentage of the time that is parallel for different number of CPU:s or will that vary with different number of CPU:s?

# Answer
> 4 votes
You can never assume anything.

There are plenty of cases where your work, or a percentage of your work, can be split up into k independent tasks. If you have k processors, then each one can handle one task. If you have k+1 processors, then one will be unused. So it's not just a matter of "percentage of work that can be parallelised", it's also a a matter of "how many parallel tasks can be performed".

There are plenty of cases where work can be parallelised, but work needs to be done to prepare for this. Let's say it takes time t to prepare for one parallel execution, independent of the amount of work. So with two processors, that preparation takes 2t. With 100 processors, it takes 100t. If the amount of work is fixed, there will be a point where more processors add more preparation time than the savings you get.

There are plenty of cases where there is a simple sequential solution, and a more complex and slower parallel solution. The total time using one processor and the sequential solution may be x. To use k processors may save y of the sequential time, but add f (k) sequential time for preparation, and use g (k, y) in total parallel time where g (k, y) \>\> y.

---
Tags: algorithm-analysis, runtime-analysis, parallel-computing
---


title: PAC learning of axis-aligned rectangles

text:
# Question
Title: PAC learning of axis-aligned rectangles
I've been reading the proof that axis-aligned rectangles are PAC learnable from the book Foundations of Machine Learning by Mohri (Proof pt. 1, Proof pt. 2), and a small technical detail stuck out to me.

The proof goes through dividing the target rectangle $R$ to four rectangular regions $r\_i$ (Fig 2.3), each having probability at least $\frac{\epsilon}{4}$. It is then claimed that:

* If the tightest sample-consistent rectangle $R\_S$ (Fig 2.2) meets any of these regions, then the mass of the possible erroneous region $R\setminus R\_S$ is bounded by epsilon, which in turn bounds the error probability.
* If $R\_S$ misses at least one of those rectangles, then we reduce to upper bounding the probability that the number of trials in a geometric random variable with probability $\ge\frac{\epsilon}{4}$ exceeds $m$.

It seems that for the first point, we need to pick $r\_i$ such that $\Pr\[r\_i\]\le\frac{\epsilon}{4}$, which means that we must pick the $r\_i$'s such that $\Pr\[R\_i\]$ equals exactly $\frac{\epsilon}{4}$. Is this reasoning correct? If so, how can you ensure that $\Pr\[r\_i\] = \epsilon/4$, without assuming something like absolute continuity of our distribution on $\mathbb{R}^2$?

# Answer
> 2 votes
Good question! The proof given in Mohri's book indeed assumes continuity of the distribution, but this can be avoided with a finer definition of the $r\_i$'s. Such a correction appears in these lecture notes who cite this paper.

Recall that you want the rectangles to be small enough, such that if $R\_S$ intersects all of them, then $R\setminus R\_s$ is small enough. Simultaneously, you want the rectangles to have large enough mass such that with high probability you do not miss a rectangle (here you use a simple bound on a geometric random variable as stated in the second point).

Suppose $R=\[a,b\]\times \[c,d\]$, and let us focus on $r\_1$, the subrectangle having $\[a,b\]$ as an edge (if we are able to satisfy the above constraints for $r\_1$, you can apply a similar construction for the rest of the rectangles). Define $r\_1=\[a,b\]\times\[c,c+h\]$, where:

$h=\inf\big\\{h'\big|\Pr\left\[\[a,b\]\times\[c,c+h'\]\right\]\ge \frac{\epsilon}{4}\big\\}$.

Note that $\Pr\[r\_1\]\ge\frac{\epsilon}{4}$. To see why, let us assume that $\Pr\[R\]\ge\epsilon$ (otherwise we are done) and let $\[a,b\]\times\[c,c+h'\]$ be some rectangle with mass $\ge \epsilon/4$. Now define the sequence of events $x\_i=\[a,b\]\times\[c,c+h+2^{-i}\Delta\]$, where $\Delta=h'-h$, and identify the rectangle $x\_i$ with the event that a point drawn from our distribution lies inside the rectangle. Now we have:

$\Pr\left\[r\_1\right\]=\Pr\left\[\bigcap\limits\_{n=1}^\infty x\_n\right\]=\Pr\left\[\lim\limits\_{n\rightarrow\infty}x\_n\right\]=\lim\limits\_{n\rightarrow\infty}\Pr\[x\_n\]\ge \frac{\epsilon}{4}$.

To see why the last inequality holds note that the series converges, since it is decreasing and lower bounded by $\frac{\epsilon}{4}$ (by our choice of $h$). See this question for a discussion on the probability of limit events. This shows that you are covered on the second point, and can upper bound the probability that at least one of the rectangles is missed.

It remains to show what we should do in the case that $r\_i\cap R\_s\neq\emptyset$ for all $i$. We can no longer immediately claim that $\Pr\left\[\bigcup\limits\_{i}r\_i\right\]\le\epsilon$, but a more sensitive approach would do the trick. Let us define $r\_i'$ to be the interior of the rectangle $r\_i$ along with its corresponding edge from $R$. Note that if $R\_S\cap r\_i\neq\emptyset$ then $R\setminus R\_S\subseteq\bigcup\limits\_{i}r\_i'$ (geometric argument). We can now conclude the proof by showing that $\Pr\[r\_i'\]\le\epsilon/4$. You can prove this by a similar approach, define a sequence of events converging to $r\_1'$, and use the fact the the probability for each event in the sequence is upper bounded by $\epsilon/4$.

---
Tags: machine-learning
---


# Question
Title: Are Kernel Codes (which are written in C) compiled during boot time?
I have a confusion regarding how the Kernel is loaded during the boot time. The intuition I have is like following:

During installation of an OS, the compiled Code of the Kernel (depending on the architecture of the system) is written to the part of the Primary Memory that is restricted to the OS. When the PC is turned on, during boot time, initial some of the Assembly Instructions are executed to start-up (like creating the process `init` and starting other services).

But how the other processes, services are created ? Are all codes are compiled to Assembly codes during installation or Kernel codes (written in C) are compiled during boot time? If the latter happens, then is GCC pre-installed to the OS address space?

# Answer
Usually, everything is compiled in advance: the kernel and userland applications.

Roughly, the kernel is written in a special place on the disk (or other permanent memory), which the hardware will access at boot time, copy in RAM, and execute.

The kernel includes the disk driver and the filesystem driver, and will look for specific files on the disk, using them to load the first OS process (e.g. `/bin/init`, in unix-like OSs). This will in turn ask the OS to spawn new OS services/daemons, load new drivers, and finally start the user interface.

There is no need to have a compiler around during this. All the code which is loaded is machine code (already compiled).

The compiler is also not needed at installation time, since whoever produced the installation media (or network repository) wrote binary packages in it, containing compiled code.
> 2 votes

# Answer
MacOS does a very, very small portion of this: During boot time, it determines which exact processor model is used by your computer, and then for a very small number of important functions, processor dependent code is written to a reserved memory location.

This is code for the memcpy and memset functions (where you *really* want the fastest possible implementation, and that is processor dependent), for atomic operations, and very few others. Hopefully the standard library that you are using uses this code when needed.

Installing code depending on the processor used is risky - I would want to be able to remove the hard drive from one computer, put it into a different computer, and have it working. But if you install processor dependent code, then code for processor A might not work on processor B.
> 2 votes

---
Tags: operating-systems, os-kernel, c
---


title: Multi-type max-flow

text:
# Question
Title: Multi-type max-flow
Suppose you have $m $ sources $s\_i$ and $n $ sinks $t\_j$, but every source produces a certain type of flow, out of $k $ types, and every sink demands a certain type as well. We would like to know if it is possible to satisfy all demands given the constraints in the network. Assume different flows types all have a certain weight, which is used to compare against edge capacities, and also to check for satisfying the demands.

Is there a formulation of this to a regular max-flow algorithm?

# Answer
This is an instance of multi-commodity network flow. If you insist on integer flows, the problem is NP-hard, but if you allow flows to take fractional values, the problem can be solved in polynomial time using linear programming.
> 4 votes

---
Tags: optimization, network-flow
---


# Question
Title: Can we implement every algorithm using only immutable variables?
Can we implement every algorithm using only immutable variables such that their space and time complexity is the same as using mutable variables?

# Answer
> 5 votes
Probably not, but I don't know if this has been definitely proven, and it depends on what you'll allow as "using only immutable variables".

In 1997 Pippenger published Pure versus Impure Lisp (Technical Report). This paper gives a negative answer when the programming language is Lisp with and without mutation (`RPLACA` and `RPLACD`) under some restrictions, namely the program consumes and produces sequences of atoms, and the program must be on-line meaning given potentially unbounded sequences as input, the program must output the $n$th output before consuming the $(n+1)$-th input. One thing to note, is that there is an unlimited supply of atoms, so each individual atom can contain an arbitrary amount of information. That said, it is difficult to get information out of an atom as it only supports equality. Part of the motivation for the first restriction is, as discussed in the papers introduction, "pure Lisp" can't make cyclic structures. If we allowed arbitrary structures as output, then there would be some (representations of) outputs that "pure Lisp" would simply be unable to make.

Now this is all well and good but also published the same year by Bird, Jones, and de Moor we have the paper More Haste, Less Speed: Lazy versus Eager Evaluation (PDF). This implements Pippenger's counter-example in the lazy language Haskell (but a lazy version of Lisp could also easily have been used) with the desired performance guarantees. (Not mentioned, but laziness also allows us to make cyclic structures.) That said, lazy evaluation, i.e. call-by-need *not* call-by-name, is usually internally implemented via mutation, but this internal mutation is unobservable from the language. I don't believe either paper discusses space usage.

More practically speaking, array algorithms are often the bread-and-butter of imperative programming, while in (pure) functional programming mutable arrays are awkward. (Graph algorithms are another area where pure functional programming struggles.) I'm pretty sure no one has demonstrated how to implement a persistent array with $O(1)$ lookups and updates to all versions. We can make persistent arrays with $O(1)$ lookups and updates to the *latest* version (and slower lookups/updates for older versions). Haskell's DiffArray implements this, though again the implementation utilizes mutation, but again this is not observable to the program. Since imperative programs are forced to use (mutable) data structures in a single-threaded manner anyway, this should allow any imperative array algorithm to be implemented in Haskell with no asymptotic slow-down (from the array at least).

The question gets murkier as we allow more features in the language. For example, the Clean programming language, another pure, lazy functional language introduced around the same time as Haskell, never had any trouble with arrays. Clean supports uniqueness typing which can guarantee that the reference you have to a data structure is the only reference. This allows operations to be implemented with in-place updates. The interface, though, is the same as the immutable interface except for an extra typing discipline. In particular, the updates could be implemented in an immutable fashion without the program being able to tell the difference.

Theoretically, I believe the question is still open, but it depends on what you consider the machine model. In some machine models it is answered. Practically, it's pretty clear that mutation is sometimes the only reasonable approach, but purely functional interfaces to mutation and mutable structures blur things a bit.

---
Tags: time-complexity, programming-languages, functional-programming
---


title: Methods of finding a PDA

text:
# Question
Title: Methods of finding a PDA
I am working on finding a PDA that accepts the following language:

```
L = {0^i 1^j 0^k 1^l | i < j and k < l}

```

I am having trouble figuring out how to break this down/ where to start. I am able to form simpler PDA's such as when there are twice as many 0's as 1's but am drawing a blank on what approach to take to begin to solve.

Are there any methods or algorithmic approaches to forming a PDA for a given language?

edit: this is NOT a duplicate of the question that was flagged, that question asks how to determine if a grammar is context-free, this is completely different.

So far I have developed this PDA but for some reason it accepts 0101 which should fail, I haven't figured out how it manages to pass through the first portion from the first accepting state:

# Answer
> 1 votes
If you can find a PDA for the language $L\_0 = \\{ 0^i 1^j : i \< j \\}$, then you can probably find a PDA for your language as well, which is just $L\_0^2$. Hence I suggest the following plan:

* Figure out a PDA for $L\_0$.
* Figure out a general construction that, given PDAs for languages $L\_1,L\_2$, outputs a PDA for their concatenation $L\_1 L\_2$.
* Apply the construction to the PDA you found in the first step.

---
Tags: automata, pushdown-automata
---


# Question
Title: Reducing the infinite language problem to halting problem
Let: $INF = \\{ w \in \Sigma^\* | \quad |L(M\_w)| = \infty \\} $.

It is easy to show with Rices theorem that $INF$ is not decidable. ($INF$ is non-trivial because of $\emptyset$ and $\Sigma^\*$).

How can you show this with a reduction onto the halting problem (for example)?

---

**Here are my thoughts:**

I had an idea of running the decider of $INF$ in its own input, but couldnt get very far.

Another idea that I just had was:

Construct a Turing machine TM M' that halts if the language is finite, and loops endlessly if it is infinite:

```
M'(w):
for i=0,1,...
    simulate M_w on w_i

```

Knowing the halting problem we cannot know if that turing machine will halt or not. We have supposedly reduced $HALT$ on $INF$. Is this correct ? (Since we take an instance of $HALT$

Can I get some feedback on my solutions ?

# Answer
> 3 votes
Your language is actually $\Pi\_2^0$-complete, and in particular even harder than the halting problem.

We can show that $\mathrm{INF}$ is $\Pi\_2^0$-hard by reduction from $\mathrm{TOT} = \\{ w : L(M\_w) = \Sigma^\* \\}$. Indeed, given a Turing machine $M$, we can construct a Turing machine $M'$ which on input $x$, simulates $M$ sequentially on all inputs $y \leq x$ (using lexicographic order). It is not hard to check that $M'$ halts on infinitely many inputs iff $M$ halts on *all* inputs.

To show that $\mathrm{INF}$ is in $\Pi\_2^0$, notice that a machine $M$ halts on infinitely many inputs if and only if for all inputs $x$ there exists an input $y \geq x$ and a number $n$ such that $M$ halts on $y$ within $n$ steps. Since the last condition is decidable, it follows that $\mathrm{INF}$ is in $\Pi\_2^0$.

To answer the question you are interested in, all you need to do is to find a reduction from the halting problem to $\mathrm{TOT}$.

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


# Question
Title: Maximum flow in a graph, and conservation of flow
The requirement for the conservation of flow in a flow network is, as I see it in the MIT lectures on Algorithms, that $\sum\_{v\in V}f(u,v)=0$ for every $u\not\in \\{s,t\\}$ where $s,t$ are the source and sink respectively. I think I get the intuitive idea expressed here, that there should be no accumulation or net loss in any vertex. However, it seems to me this expression actually says "The follow out of u is always 0". Am I confused or is the correct expression, $\forall u\not\in \\{s,t\\}$

$$\sum\_{v\in V}f(u,v)=\sum\_{w\in V}f(w,u) $$

Or is it there something about the requirement that $f(u,v)=-f(v,u)$ that takes care of this automatically? And maybe somehow in the summation we don't pay too much attention to the placement of the $u$ in the formula?

# Answer
> 1 votes
The definition given in the lectures you've seen is the usual, which can be seen as the conservation of flow through a node, as it follows that flow exiting the node is equal to the flow entering the node. The expression doesn't only consider outgoing flow, as the equation $f(u,v) = -f(v,u)$ means that incoming flow can be described as 'negative' outgoing flow.

Your expression currently just says 'the flow through $u$ is the flow through $u$', which doesn't restrict the flow at all.

A better version of the expression you try to pose is the following:

$\begin{equation} \sum\_{v\in V\_{in}(u)} f(v,u) = \sum\_{v\in V\_{out}(u)} f(u,v), \end{equation}$

where $V\_{in}(u)$ is the set of nodes $v$ that such that $v\rightarrow u$ is an edge and $V\_{out}(u)$ the set of nodes $v$ such that $u\rightarrow v$ is an edge.

It can be easily shown that this equation is equivalent to $\sum\_{v\in V} f(u,v) = 0$ when $f(u,v)= -f(v,u)$ for all $u,v\in V$.

---
Tags: network-flow, weighted-graphs
---


title: What is rightmost sentential forms?

text:
# Question
Title: What is rightmost sentential forms?
I'm solving some past job interview problems. I met an embarrassing question about compilers.

The question is :

> Consider the following grammar, with start symbol $E$:
>
> \begin{align\*} E &\rightarrow E \ast E\\ &\quad \mid E ~/~ E\\ &\quad \mid E + E\\ &\quad \mid E - E\\ &\quad \mid (E)\\ &\quad \mid a \mid b \mid c \mid \ldots \mid x \mid y \mid z \end{align\*}
>
> The following strings are legal derivations from this grammar:
>
> 1. $a \ast b + c$
> 2. $( a - b ) \ast c$
> 3. $a ~/~ ( b – c)$
>
> Which of the above are rightmost sentential forms?

When I was an undergraduate student, I learned that rightmost(leftmost) sentential form is result of rightmost(leftmost) derivation. so, I think if $1,2,3$ are legal derivations form above grammar then absolutely all of $1,2,3$ are rightmost sentential form. If I'm correct, above question is very worthless.

Is there any counter example that is not rightmost sentential form of the grammar $G$ although it is a legal derivation from $G$?

OR

Is there another definition about rightmost sentential form corresponding to above question? I have googled "rightmost sentential form" but there are few results and most of them is the definition that I already know.

# Answer
> 7 votes
I found other answers here confusing, so let me explain it clearly here-

Definitions:

> **A sentential form** is any string derivable from the start symbol. Note that this includes the forms with non-terminals at intermediate steps as well.
>
> **A right-sentential form** is a sentential form that occurs in a step of rightmost derivation (RMD).
>
> **A sentence** is a sentential form consisting only of terminals

The examples in your question are all sentences. And since any way of derivation (including RMD) ultimately leads to a sentence, technically **all sentences are right-sentential as well as left-sentential forms**. So there isn't any counter example which you asked for.

Clarifying Examples : Page 2 of this link

# Answer
> 3 votes
The grammar can be parsed both left-most and right-most.

`a∗b+c` can be derived left-most:

```
E
E * E
E * E + E
a * E + E
a * b + E
a * b + e

```

and also right-most (correct precedence:)

```
        E
    E + E
E * E + E
E * E + c
E * b + c
a * b + c

```

Only in the following form the grammar is both unambiguously left-recursive and arithmetically correct

```
S → E

E → T | E + T | E - T

T → F | T * F | T / F | (E)

F → a | b | c | ... | 1 | 2 | 3 | ...

```

# Answer
> 1 votes
I agree, that all the above examples given are rightmost sentential forms. I am not quite sure, how much this is correct, but I thought of a slight modification to definition of right sentential form. Here it goes,

> The **right sentential form** is the sentential form in which the input string when parsed from right-to-left and reduced whenever possible would give final output as the start symbol

Here reduction operation means to replace the symbol or set of symbols by the non-terminal symbol such that the symbol(s) satisfies some rule corresponding to that non-terminal symbol.

I thought of this definition because when I made the parse tree for the example strings given, I found that **first example** produced two parse trees, but both of them when parsed from right to left and reduced accordingly will ultimately lead to the start symbol.

# Answer
> 1 votes
Right derivation: when you select right most non terminal everytime to derive the string from G then it will result in the right sentetntial form If there is a legal derivation for G it must have atmost one right or left derivation, which results in right sentential form or left sentential form.

this can be proved for example consider a grammar G which derives the strings not by left or right derivations but by mixed , so now i can rearrange the productions to produce only the right and then the left, it is a simple arrangement as we do not have any conditions when to apply the the production rules.So i think there will be no grammar G for which there will be a derivation but not a right most derivation tree

# Answer
> 0 votes
The answer is (iii).

Considering precedence rules, * operator has more precedence than + operator, but bracket () has more precedence than \*.

So in (i), you start from the left where you have \*, as there is no bracket in the string.

In (ii), you still start from the left due to the use of bracket for the + operator which make it to have higher precedence than \*.

But in (iii), you must start from the right because of the use of bracket on the operator with the lesser precedence (+).

---
Tags: formal-grammars, compilers
---


# Question
Title: How did they cancel out O-terms in this fraction?
While reading a book about algorithms, I came across this derivation:

$$ \frac{2a\_0(2N) \ln(2N) + O(2N)}{2a\_0N\ln N+O(N)} = \frac{2\ln(2N) + O(1)}{\ln N+O(1)} = 2 + O\left(\frac{1}{\log N}\right). $$

Could somebody please explain to me how we went from the left to the right?

# Answer
First, let me mention that judging from the final result, in this context $O(f(N))$ means a function $g(N)$ such that $|g(N)| \leq Cf(N)$ for some $C\>0$ and all $N$.

The first step is simple: we divide both numerator and denominator by $2a\_0 N$. This gives us $$ \frac{2\ln(2N) + O(2N)/2a\_0N}{\ln N + O(N)/2a\_0N}. $$ Now if $f(N) = O(N)$ then $f(N)/2a\_0N = O(1)$, since $2a\_0$ is a constant. This is how we get to the second fraction.

Getting to the final expression takes more work. First, notice that $$ \frac{2\ln(2N) + O(1)}{\ln N + O(1)} = \frac{2\ln N + O(1)}{\ln N + O(1)}, $$ since $2\ln 2$ is a constant. Denote now by $B(N)$ the $O(1)$ function in the numerator, and by $C(N)$ the $O(1)$ function in the denominator. Then $$ \frac{2\ln N + B(N)}{\ln N + C(N)} = 2 + \frac{B(N) - 2C(N)}{\ln N + C(N)} = \\ 2 + \[B(N) - 2C(N)\] \frac{\ln N}{\ln N + C(N)} \frac{1}{\ln N} = \\ 2 + \[B(N) - 2C(N)\] \left(1 - \frac{C(N)}{\ln N + C(N)}\right) \frac{1}{\ln N}. $$ We need to show that the second term is $O(1/\log N)$. By definition, $|B(N)-2C(N)|$ is bounded by some constant. The same can be said about the second factor, since it tends to 1 as $N \to \infty$. Hence the entire second term is bounded in absolute value by a constant times $1/\ln N$, i.e., it is $O(1/\log N)$.
> 11 votes

# Answer
The real power of $O$ notation is in formulas like this. By systematically applying valid rules of manipulation, we can harness our intuition in a fully rigorous way, without much effort (such as that of dealing with explicit inequalities). (Of course, if we were allergic to $O$ notation, or not sufficiently confident about what manipulations are valid, we could immediately “translate” any $O$-containing expression we encounter into some other notation involving of sets of functions with appropriate quantifiers, but then we'd lose much of the power of $O$ notation.)

Let's look at this example in detail. In this case, we start with the expression $$\frac{2a\_0(2N) \ln(2N) + O(2N)}{2a\_0N\ln N+O(N)}.$$ (Presumably it has been specified earlier that in this context when we use $O()$ we are thinking of $N \to \infty$, not say $N \to 0$.)

First, to get an intuitive sense, we “THINK BIG”: for large $N$, both the numerator and denominator are dominated by their first terms, i.e. they grow as $2a\_0(2N)\ln(2N)$ and $2a\_0N\ln N$ respectively. As we see a common $2a\_0N$ factor, we can first divide both numerator and denominator by it. Our original expression thus becomes: $$\frac{2a\_0(2N) \ln(2N) + O(2N)}{2a\_0N\ln N+O(N)} \stackrel{(1)}{=} \frac{2\ln(2N) + O(2N)/(2a\_0N)}{\ln N + O(N)/(2a\_0N)}$$ Here, the manipulation $(1)$ is simply algebra, treating the $O()$ expressions as black-boxes.

Now, in the numerator we have the term $O(2N)/(2a\_0N)$. It may be obvious that this is $O(1)$, and you could indeed prove it easily, but you can also use standard manipulation rules that have been proved previously. In this case, for example, we can use a combination of:

which together give $f(n)O(g(n)) = O(f(n)g(n))$. (Recall that with equations containing $O$, all uses of the “$=$” sign are one-way: so we could not directly use $O(f(n)g(n)) = f(n)O(g(n))$ which is $(9.27)$ in the book.) So we can write $$O(2N)/(2a\_0N) = \frac{1}{2a\_0N} O(2N) = O\left(\frac{1}{2a\_0N}2N\right) = O\left(\frac1{a\_0}\right) = O(O(1)) = O(1).$$ (See $(9.25)$ in the book for $O(O(f(n))) = O(f(n))$.) Similarly, for the second term in the denominator, we get $O(N)/(2a\_0N) = O(1)$. So our expression becomes: $$\frac{2\ln(2N) + O(2N)/(2a\_0N)}{\ln N + O(N)/(2a\_0N)} \stackrel{(2)}{=} \frac{2\ln(2N) + O(1)}{\ln N + O(1)}$$ using the manipulations above. This is the first equality in the question.

---

Immediately, we can write the numerator $2\ln(2N) + O(1)$ as $2\ln N + 2\ln 2 + O(1) = 2\ln N + O(1)$, again using manipulations like $c = O(1)$ and $O(1) + O(1) = O(1)$ so $c + O(1) = O(1)$. So our expression is actually: $$\frac{2\ln(2N) + O(1)}{\ln N + O(1)} \stackrel{(3)}{=} \frac{2\ln N + O(1)}{\ln N + O(1)}$$

Now, faced with a division, it may be tempting to give up $O$-manipulation and reason with inequalities. But let's have a bit more faith in mindless manipulation. :-)

We can repeat the trick of “dividing”, this time by $\ln n$, to rewrite as $$\frac{2\ln N + O(1)}{\ln N + O(1)} \stackrel{(4)}{=} \frac{2 + O(1)/\ln N}{1 + O(1)/\ln N} \stackrel{(5)}{=} \frac{2 + O\left(\frac{1}{\ln N}\right)}{1 + O\left(\frac{1}{\ln N}\right)} $$ just as before.

Finally, we can use the rule $$\frac{1}{1 + O(f(n))} = 1 + O(f(n)) \quad \text{if $f(n) = o(1)$}$$ (I can't find this one in a book right now, but it's obviously useful to have in your toolkit and you can prove it yourself using $\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots$), to rewrite the expression as $$ \begin{align} \frac{2 + O\left(\frac{1}{\ln N}\right)}{1 + O\left(\frac{1}{\ln N}\right)} &\stackrel{(6)}{=} \left(2 + O\left(\frac{1}{\ln N}\right)\right)\left(1 + O\left(\frac{1}{\ln N}\right)\right) \\ &\stackrel{(7)}{=} 2 + 2O\left(\frac{1}{\ln N}\right) + O\left(\frac{1}{\ln N}\right) + O\left(\frac{1}{\ln N}\right)O\left(\frac{1}{\ln N}\right) \\ &\stackrel{(8)}{=} 2 + O\left(\frac{1}{\ln N}\right) \end{align} $$ where I skipped a few steps in the last equation because surely you get the point by now.

---

Above, I just wrote everything out in detail for illustration, but in reality, after a bit of practice with valid $O$-manipulations (of course you have to be careful not to do anything that's not justified, but this is similar to when you learned during middle-school algebra not to write $(x+y)^2 = x^2 + y^2$ say), you can become comfortable and don't have to work things out so laboriously: you'll be able to write directly, say, $$ \frac{2a\_0(2N) \ln(2N) + O(2N)}{2a\_0N\ln N+O(N)} = \frac{2\ln N + O(1)}{\ln N+O(1)} = \frac{2 + O\left(1/\ln N\right)}{1 + O\left(1/\ln N\right)} = 2 + O\left(\frac{1}{\log N}\right) $$ pretty much as in the question. There is nothing sloppy or non-rigorous here; you're applying valid rules that have been proved.

Being able to quickly do such calculations for asymptotics is the main benefit of using $O$ notation.
> 8 votes

# Answer
In order to make sense of this abuse of notation, replace the original Landau terms following the *placeholder semantics*:

$\qquad\displaystyle f(N) = \frac{2a\_0(2N) \ln(2N) + f\_1(N)}{2a\_0N\ln N+ f\_2(N)}$

with $f\_1, f\_2 \in O(N)$.

Clearly (assuming that $f\_2$ is non-negative),

$\begin{align\*} f(n) &\leq \frac{2a\_0(2N) \ln(2N) + f\_1(N)}{2a\_0N\ln N} \\ &= \frac{2a\_0(2N) \ln(2) \+ 2a\_0(2N) \ln(N) \+ f\_1(N)}{2a\_0N\ln N} \\ &= \frac{2 \ln(2)}{\ln(N)} + 2 + \frac{f\_1(N)}{2a\_0N\ln N} \\ &\leq 2 + \frac{2 \ln(2)}{\ln(N)} + \frac{c\_1 N}{2a\_0N\ln N} \qquad(\star)\\ &= 2 + \frac{4 a\_0 \ln(2) + c\_1}{2 a\_0} \cdot \frac{1}{\ln N} \end{align\*}$

with some $c\_1 \> 0$ and for all $N \geq N\_1$; $c\_1$ and $N\_1$ come from applying the definition of $O$ at $(\star)$.

Applying the definition of $O$ again yields the claim.
> 5 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?
Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?Does it have to do with pumping lemma?

Additionally,is there an algorithm which finds if a regular language of a regular expression is the empty set?

Thank you

# Answer
Yes, there is such an algorithm, and (if I am not mistaken) you can actually use a recursive evaluation of regular expressions.

Recall that regular expressions are composed from $\varnothing$, $\varepsilon$ and $a$ (for $a$ in some alphabet) using the operations $\cdot$, $+$ and $\*$ (concatenation, union and iteration).

Observe that a language can only be infinite if it is based on the iteration of any language that contains a string that is not empty ($\varepsilon$). Then such an iteration can be repeatedly concatenated and unioned with other languages. The result will be infinite again, except in the case we concatenate with the empty set.

Now introduce language 'classes' NUL, ONE, FIN, and INF for the empty set, the empty string, any (finite) language that contains a string other than $\varepsilon$, and any infinite set.

Start by replacing in your regular expression any occurrence of $\varnothing$, $\varepsilon$ and $a$ by NUL, ONE and FIN respectively.

Now use a set of reductions (equalities) on the new expression, and repeat those:

* NUL\* = ONE\* = ONE
* NUL + FIN = ONE + FIN = FIN + FIN = FIN
* NUL NUL = NUL ONE = NUL FIN = NUL INF = NUL
* ONE FIN = FIN FIN = FIN
* ONE INF = FIN INF = INF INF = INF
* FIN\* = INF\* = INF

And many more, try to find what is needed.

And it seems to solve the empty set problem at the same time?
> 5 votes

# Answer
Yes, there are algorithms for both of the things you described. In fact, you can take the algorithm for the second problem and use that to produce an algorithm for the first problem. So, let's take on the second problem first.

The first thing we're going to do is convert the regular expression into an equivalent DFA. Since regular expressions and finite automata are equivalent in their descriptive power, we can always do that.

Now, consider the state diagram of the DFA we have. This is just a directed graph. Note that this DFA accepts the empty language if and only if *there is no path from its start state to one of its accept states*. Checking whether or not there exists a path between two vertices of a graph is very simple. Just use breadth-first search from the start state and see if some accept state is reachable.

For the first problem, we make the following observation: *if the language of a DFA is finite, it can't accept any string whose length is not strictly smaller than the number of states it has*. Why is this true? Well, a string with length greater than or equal to the number of states has a length greater than or equal to the pumping length of the language. So, if such a string is accepted, pumping a certain substring of that string arbitrarily many times gives us arbitrarily many strings, all of which is in our language.

Now that we have that cleared up, we can give an algorithm for the first problem. Again convert your regular expression into an equivalent DFA $M$. Let that DFA have $n$ states.

Now, construct another DFA $N$ that accepts all strings with length greater than or equal to $n$.

After that construct a DFA $P$ such that $L(P)=L(M)\cap L(N)$.

We've already established that $M$ doesn't accept any string with length greater or equal to $n$ if and only if $L(M)$ is finite. So, the only time $L(M)$ and $L(N)$ have strings in common is when $L(M)$ is infinite.

Now, use the algorithm we developed for the first problem to see if $L(P)$ is empty or not. If it is, $L(M)$ is finite. If it's not, $M$ accepts infinitely many strings and as a result, so does your regular expression.
> 4 votes

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


# Question
Title: examples for: A is mapping reducible to B but B is not mapping reducible to A
I find it hard to find reductions that only work on one side: A is mapping reducible to B, but B is not mapping reducible to A. what could be an easy way to find such two languages A,B ? I tried Atm,Htm,EQtm,Etm,RegTm, and many others, and whenever I found that A is reducable to B, I also found that B is reducable to A.

thanks.

# Answer
> 1 votes
I now understand that there is a mapping reduction from the empty language to any other language except Sigma\*, and there cannot be a reduction from a language to the empty language except for a reduction from the empty language to the empty language.

---
Tags: reductions
---


# Question
Title: Proving NP hardness about graph creation
I have graph creation problem.

Given a set of nodes of graph, and node constraints such as given every node's number of neighbors and number of neighbors of neighbors and so on. I want to create a graph that can satisfy all these constraints (# of constraints is polynomial in n).

I have formulated the problem as an integer programming wherein I am trying to create possible edges by assigning them random variables $z\_{i,j} \in $ $\\{0, 1\\}$ and then trying to satisfy the constraints of # neighbors, # neighbors of neighbors and so on (k steps). However I am not sure if this is a NP complete problem because the constraints are non-linear.

# Answer
> 5 votes
If you are given just the degree sequence (the number of neighbors of each vertex), then the Havel–Hakimi algorithm is an efficient algorithm that constructs a graph conforming to the degree sequence, if possible, and alerts you otherwise. If you are given the second-order degree sequence (the number of vertices at distance 1 and at distance 2 from each vertex), then the problem of determining whether such a graph exists becomes NP-complete, as shown by Erdős and Miklós in their paper Not all simple looking degree sequence problems are easy.

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


# Question
Title: Can two equal classes be separated wrt an oracle?
Is it known if there are two classes of languages $A$ and $B$ such that:

1. $A$ and $B$ are defined wrt the exact same type of machine (e.g. 1-tape Deterministic Turing Machines, 2-tape Deterministic Turing Machines, 1-tape Nondeterministic Turing Machines, etc);
2. neither $A$ or $B$ are defined wrt a restriction on space usage;
3. $A = B$;
4. there is an oracle $O$ for which $A^O \neq B^O$?

# Answer
> 3 votes
While the other answer answers the question as posed (at least, given your definition of 'type of machine'), I still think the question is rather ill-posed and that resolving this is a solution as well.

## Problems with the current definition

First of all, as @D.W. mentioned in the comments, the claim 'Language class $X$ is defined w.r.t. machine $M$' is ill-posed. There is no need to define a class of languages with a machine at all. Even if we have a language which is commonly described w.r.t. some machine, such as $P$, there is nothing preventing us to give an equivalent definition that uses no machine at all! (Not sure if this is doable or has been done. Perhaps you can do something based on $\lambda$-calculus?)

The second problem is that oracle access is not a modifier/property of a language class! This follows immediately from the previous point: if I define a language without using a machine, how on earth am I able to use this oracle if I don't even have a machine?

The crucial mistake that leads to your problem is that a 'language' under oracle access actually depends on the definition of the language and a 'language' with oracle access is **not** invariant under the method you use to define the language. In fact, the often posed statement $P^O = NP^O$ is an example of *really bad notation*, as $P$ and $NP$ aren't actually languages here, but methods to define languages!

Let's make this precise: Let $\mathcal{X}$ be a 'definition method' for languages that can access oracles (for example, a set of machines and some acceptance rules) Let $L(\mathcal{X})$ be the language class that is defined by $\mathcal{X}$. Let $\mathcal{X}^O$ be the extension of $\mathcal{X}$ with access to the oracle $O$.

## Rephrasing the question

Your question can now be rephrased as follows, let language classes $A$, $B$ such that:

> 1. There exists an $\mathcal{X},\mathcal{Y}$ such that $A= L(\mathcal{X})$, $B = L(\mathcal{Y})$ and $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type'.
> 2. $\mathcal{X}$ and $\mathcal{Y}$ are able to use unbounded space.
> 3. $A=B$
> 4. There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$

By combining 3 and 1, we can do without $A$, $B$ and focus on the machines:

> 1. $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type' and are able to use unbounded space.
> 2. There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$

Now, the question crucially depends on what 'the same type' means. If $\mathcal{X} = \mathcal{Y}$, then satisfying both 1 and 2 becomes impossible, as we now do have $\mathcal{X}^O = \mathcal{Y}^O$, so $L(\mathcal{X}^O) = L(\mathcal{Y}^O)$.

So, a necessary condition for statements 1 and 2 is the claim:

> There exists an oracle $O$ such that $\mathcal{X}^O \neq \mathcal{Y}^O$.

You can define 'type' however you wish, but if two machines don't behave the same when I give them the same oracle, I don't consider those machines to be of the same type.

So, in conclusion, after rephrasing your question more formally and giving a property which I believe 'type' should adhere to, the answer to your question is actually no.

---
Tags: complexity-theory, relativization
---


# Question
Title: What does the "big O complexity" of a function mean?
What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?

# Answer
First of all, when people talk about big O *complexity*, they refer to the complexity of an algorithm, usually its running time. A somewhat better term is big O *asymptotics*. Big O makes sense to functions beyond the running time of an algorithm, indeed beyond any kind of complexity measure of an algorithm. Big O notation actually first appeared in the context of number theory, where it is used to simplify many statements.

Now back to your question. There really isn't any such thing as *the* big O complexity of a function. Let us take as an example your function. It has many big O estimates, such as:

* $9n^2 + 10n = O(9n^2 + 10n)$.
* $9n^2 + 10n = O(n^2)$.
* $9n^2 + 10n = O(n^3)$.

The first two estimates are better than the third one, since they are *tight*: not only do we have $9n^2 + 10n = O(9n^2 + 10n)$, but in fact $9n^2 + 10n = \Omega(9n^2 + 10n)$, whereas it is not true that $9n^2 + 10n = \Omega(n^3)$. Comparing the first two estimates, the second one is better since it is *simpler*.

What does *simple* mean? Although this is an informal notion, everybody will agree that functions of the form $a^n n^k \log^\ell n$ are simple. If we fix this class of simple functions, then the unique simple function $f(n)$ such that $9n^2 + 10n = O(f(n))$ and moreover this is a tight bound is $f(n) = n^2$ (i.e., $a=1$, $k=2$, $\ell=0$). This could be termed "the" big O asymptotics of $9n^2 + 10n$, but a much better term would be the *big $\Theta$* asymptotics of $9n^2 + 10n$, since the statement $9n^2 + 10n = \Theta(n^2)$ encompasses the property that this a tight upper bound.

This discussion suggests that when you are given an explicit function, you shouldn't be looking for big O and big $\Omega$ estimates – instead, you should aim higher, at a simple big $\Theta$ estimate.

The true role of big O and big $\Omega$ is in other situations. One situation is when analyzing the running time of an algorithm. The exact running time could depend on the input in a complicated way. For example, when running binary search on an array of length $n$, the algorithm could terminate after one step, two steps, or more – but always within $O(\log n)$ steps. We cannot describe the running time using big $\Theta$, since the best lower bound $\Omega(1)$ and the best upper bound $O(\log n)$ do not match. The same cannot be said about your example.

Another situation in which it makes sense to use big O and big Omega is when it is hard to find the exact asymptotics of a function. Take as an example the central binomial coefficient $\binom{2n}{n}$. Since $\sum\_{m=0}^{2n} \binom{2n}{m} = 4^n$ and since $$\binom{2n}{0} \< \binom{2n}{1} \< \cdots \< \binom{2n}{n-1} \< \binom{2n}{n} \> \binom{2n}{n+1} \> \cdots \> \binom{2n}{2n-1} \> \binom{2n}{2n}, $$ we can obtain the following upper and lower bounds: $$ \frac{4^n}{2n+1} \leq \binom{2n}{n} \leq 4^n. $$ This shows that $\binom{2n}{n} = O(4^n)$ and $\binom{2n}{n} = \Omega(4^n/n)$, where in both cases we are using simple functions as our estimators. The true rate of growth is $\binom{2n}{n} = \Theta(4^n/\sqrt{n})$, but this is harder to establish. In more complicated cases, it could be hard to find the exact rate of growth, or perhaps we are content with only an upper bound or only a lower bound, and then it makes sense to use big O or big $\Omega$.

One could also come up with contrived examples, which rarely happen in practice, in which there is no simple big $\Theta$ estimate for a given function. For example, consider the function $$ f(n) = \begin{cases} n & \text{ if $n$ is even}, \\ n^2 & \text{ if $n$ is odd}. \end{cases} $$ The best simple lower bound one could give is $f(n) = \Omega(n)$, and the best simple upper bound is $f(n) = O(n^2)$, but the two don't match.

Finally, while in analyzing algorithms we usually don't care about multiplicative constants, since they depend on details which our analysis abstracts away on purpose, in other situations it makes sense to ask for information beyond big Theta. For example, we can get an asymptotic estimate of the form $$ \binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}. $$ Or we could ask for an asymptotic series, such as $$ \binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} - \frac{4^n}{8\sqrt{\pi} n^{3/2}} + O\left(\frac{4^n}{n^{5/2}}\right). $$

At this point in your training, however, it's probably better to concentrate at the more elementary stuff, which is of more widespread use in computer science.
> 10 votes

---
Tags: terminology, asymptotics, landau-notation, reference-question
---


# Question
Title: Function to generate longer bit-sequence from shorter sequence with certain properties
im not familiar with the terminology of computer-science which makes it pretty difficult to search for the problem I have.

I'm looking for a function that generates a sequence of bits (**B**) of a given length (i.e. 1024 bit) from a chosen bit-sequence (**A**) (i.e. 32 bit).

This function needs to have the following properties:

1. The relation **A**-\>**B** has to be unique
2. A slight change of **A** (i.e. 1 bit) results in a slight change of **B** (~1024bit/32bit = ~32)

While searching I came across hash-algorithms but they achive kind of the oppisite I want to do. They shorten a sequence and a small change of the first one results in a big change of the other one.

Do you know of such a function or do I have to come up with something myself?

---

**Example** (with fewer bits):

Let bit-sequence **A** be given as 0b0101 (integer-representation: 5). Let function **F** map **A** to **B** so that **B** = 0b1001 0010 0101 0111 (example). Here, **B** can be split into 4 4-bit integers (9, 2, 5, 7).

Changing 1 bit of **A** from 0b0101 (5) to 0b0100 (4) results in 4 changed bits of **B** so that the resulting bits are 0b1011 0000 0101 0110 (integer: 11, 0, 5, 6).

The 4 integers contained in **B** will be used in further computations and I'm looking for function **F**.

# Answer
Let $\pi$ be a random permutation on $\\{1,\ldots,1024\\}$, and let $K$ be a random bit string of length 1024 bits. The following mapping seems to satisfy your needs (with probability close to 1): $$ A \mapsto \pi(A^{32} \oplus K). $$ In particular, changing $b$ bits of $A$ will result in changing $32b$ bits of the result.

If you are OK with changing more than 32 bits, then you can take a random sparse affine function, that is the function whose $i$th bit is an XOR of a small number of bits of $A$ chosen at random, XORed with a random bit.
> 1 votes

---
Tags: hash
---


# Question
Title: Remove duplicated in array with best performance
I am trying to remove duplicates from an array using the following two algorithms

```
   void PrintDuplicates(int[] arr)
   {
       if (arr == null)
           throw new ArgumentException("arr can't be null.");

       Hashtable table = new Hashtable();

       for (int i = 0; i < arr.Length; i++)
       {
           if (table.ContainsKey(arr[i]) == true)
           {
               // Console.WriteLine(i);
           }
           else
           {
               table.Add(arr[i], "");
           }
        }
    }

    void PrintDuplicatesWithSort(int[] arr)
    {
        if (arr == null)
            throw new ArgumentException("arr can't be null.");

        arr.ToList().Sort();

        for (int i = 0; i < arr.Length - 1; i++)
        {
            if (arr[i] == arr[i + 1])
            {
                // Console.WriteLine(i);
            }
        }
    }

```

Time complexity of the first algorithm to my understanding is O(n), while time complexity of the second is O(n) for sorting plus O(n-1) for the loop meaning total of O(2n-1).

However when I benchmark the code on this array `int[] arr = { 4, 2, 5, 4, 1 };` the one with the higher complexity performs two times better. This implementation is using .net which uses insertion sort and implementation of hashtable that searches in O(1) according to their documentation. What am I missing here?

# Answer
> 1 votes
Sorting is $O(n\log n)$, not $O(n)$.

Also these are asymptotic bounds. Even if one algorithm is $O(n)$ and another is $O(n^2)$, it is possible that, for small-ish values of $n$ the second algorithm is faster.

More concretely, $f(n) = 1000 n$ is $O(n)$ and $g(n)=n^2/1000$ is $O(n^2)$, and both bounds are tight. Still, it will take a while for the first function to become smaller than the second one: for $n\<1000000$ the second one is smaller.

---
Tags: complexity-theory
---


# Question
Title: On the analysis of Christofides's algorithm
Suppose you have even number of vertices, they form as a complete graph denote the graph by $G$. Now, suppose we compute the minimum weight perfect matching denoted by $P$ (so $P$ has alternating edges, i.e. one is a perfect matching and one is not along all the path $P$ through all vertices of $G$). Now, suppose $T^\*$ is TSP tour of $G$.

> Show that the inequality is true: $$ \operatorname{cost}(P) \le \min \\{ \operatorname{cost}(N\_1), \operatorname{cost}(N\_2) \\},$$
>
> where $N\_1$ and $N\_2$ are any two perfect matchings on $T^\*$.

Note that this inequality from the analysis of Christofides's algorithm, see this nice paper.

# Answer
Since $P$ is a minimum weight perfect matching, by definition $$ \operatorname{cost}(P) = \min\_N \operatorname{cost}(N), $$ where $N$ goes overl all perfect matchings. In particular, $\operatorname{cost}(P) \leq \operatorname{cost}(N)$ for any particular perfect matching $N$.
> 1 votes

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


# Question
Title: How is this lamda function beeing executed in an example for the Y combinator
I have spent a few hours now trying to understand how the Y Combinator is working and how it allows us to construct recursive functions with higher order functions.

I have been going through this derivation http://mvanier.livejournal.com/2897.html which is using the factorial function for explanation which I find quite helpful but at some point I am always getting lost.

I still understand this part

```
  (define (part-factorial self)
    ((lambda (f)
       (lambda (n)
         (if (= n 0)
             1
             (* n (f (- n 1))))))
     (self self)))

  (define factorial (part-factorial part-factorial))
  (factorial 5) ==> 120

```

We have a function `part-factorial` which takes as a formal parameter `self` and applies it as argument `(self self)` to the first lambda function. So inside the first lambda `f` will evaluate to `(self self)` which in case of the `factorial` function will evaluate to (part-factorial, part-factorial). So in the second lambda then if we take 5 as our n the call to the function f will evaluate to `part-factorial part-factorial 4` which will start the recursion.

After a few syntax changes we now define the functions as

```
  (define almost-factorial
    (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))

  (define factorial
    ((lambda (x) (x x))
     (lambda (self)
       (almost-factorial (self self)))))

  (factorial 5) ==> 120

```

And at this point I am confused. I understand the almost-factorial function as it is pretty much unchanged compared to `part-factorial` however the new factorial function is unclear to me, from a syntax perspective. I don't understand anymore which lamda will be executed with which parameters and in which order.

Could anybody explain to me the execution of this function?

# Answer
I am just going to write `h` for `almost-factorial` because long names can sometimes obscure math.

We consider:

```
((lambda (x) (x x))
 (lambda (self)
   (h (self self))))

```

Write `foo` for `((lambda (x) (x x))` and write `bar` for `(lambda (self) (h (self self))))`. Then our expression is just

```
(foo bar)

```

Using the definition of `foo` we see that this is equal to

```
(bar bar)

```

Then we use the definition of `bar` on the first occurrence of `bar` to see that this is equal to

```
((lambda (self) (h (self self)))) bar)

```

which in turn is just

```
(h (bar bar))

```

We discovered that `(bar bar)` is equal to `(h (bar bar))`. Let us write `g` for `(bar bar)`, so `g` is equal to `(h g)`. Taking into account the definition of `h` (which is jsut `almost-factorial` from your question) we see that `(h g)`, and therefore `g`, is equal to

```
(lambda (n)
  (if (= n 0)
      1
      (* n (g (- n 1)))))

```

In other words, `g` is the usual factorial function. I hope I got all the silly lisp parentheses where they are supposed to be.
> 6 votes

---
Tags: lambda-calculus, functional-programming
---


# Question
Title: Specify an upper bound of the size m of R with the big O notation
I am trying to learn the Big O notation through the example below, can you help?

Let S be a set of n vertexes of a graph G and R be a set that the set of edges of G. Specify an upper bound of the size m of R with the big O notation. The bound shall be as tight as possible.

Are upper bound of the size m and runtime two different concept?

How to proof that the m is O(n^2) if that is the case or else?

Thank you for your attention!

# Answer
you can prove it by taking some set of vertices say four (v1,v2,v3,v4). Now you are asking of Big Oh(greatest upper bound ...tightest most precisely )

note:this prove is for simple graph(see wiki)

now place the vertices like:

## v1 v2

## v4 v3

{in shape like rectangle}

just think what will be maximum number of edges possible? hmmm answer is :

if we draw an edge between every pair of vertices.

> for v1 : edges can be v(1-\>2) ,v(1-\>3),v(1-\>4)
>
> for v2: edges can be v(2-\>1){already included therefore don't write it} ,v(2-\>3),v(2-\>4)
>
> for v3:edges can be v(3-\>4)
>
> for v4: all are already included

what u see? total no of edges are coming in form:3+2+1=6

for n vertices(v1,v2......,vn) same could be done:

> for v1: (n-1) choices of vertices are available.{excluding v1 therefore n-1}
>
> for v2:(n-2)

. . . .

> for vn-1:1
>
> for vn:zero

total edges:n+(n-1)+(n-2)+...+1+0={n(n+1)}/2=0.5{n^2+n}

since we are talking of Big Oh only term with max degree will make difference Hence, it is O(n^2) where n is no. of vertices
> 0 votes

# Answer
> Are upper bound of the size m and runtime two different concept?

The concept is just upper bounding. It doesn't matter whether you're bounding the number of vertices in a graph, the number of steps a program takes to execute, or the number of elephants in India – it's just an upper bound.

Probably the first time most CS students see big-O notation is in the context of runtimes and it's a common mistake to assume that big-O somehow means runtime. But it doesn't. This is the same mistake as, "The first time I saw numbers, they referred to somebody's height. Therefore, numbers mean height."
> 3 votes

---
Tags: asymptotics
---


# Question
Title: Best Approach To Parse Human Readable Text To Machine Readable (CSV)
I am attempting to parse a large amount of text that cannot be readily used by other software due to the human readable design. However, each "section" of the text has the same format. By "section", I mean lines 1-10 (section 1) will have the same format as lines 11-20 (section 2). My plan is to loop through this text and gather all sections into a list. Then convert that list into a CSV.

Example:

```
####################################
123456789   first-name last-name   2/25/2018
------------------------------------
more-user-info1               12345
other-info1
123                   user-name1
------------------------------------
even-more-data1
####################################
112233445   first-name last-name   1/1/2018
------------------------------------
more-user-info2               78900
other-info2
555                   user-name2
------------------------------------
even-more-data2
####################################
<piece 3 here> ...

```

So to give you an idea `###...` means new section.

My question is what is the best approach to parsing this data? This is just an example, a real section has a lot more data and a lot of edge cases/optional data. This is also coming from a super old program so I am not aware of any blueprint or business rules around the data.

I am currently using regex to find the data I need to store. Are there any options besides regex to parsing non-strictly structured text?

# Answer
My approach is to check that my assumptions about the format of the data are correct while reading. Example, I ensure that as expected, I get the series of # characters, that the next line starts with a number and ends with a date as mm/dd/yyyy. Upon any failure, I would throw an exception with a message such as "expected so and so at line xxx but found yyy". In case things go south, I will not be left with some cryptic error message related to regex.
> 3 votes

---
Tags: parsers
---