# Question
Title: Help in understanding the implementation/application of scope trees
I’m learning (self-taught) about language implementation and compiler design, and I’m implementing a toy language to cement the concepts in my mind. However, I’m having trouble understanding how scope trees are meant to be used.

In my toy language, I’m using the Visitor pattern to traverse the syntax tree as a simple interpreter. I assign a pointer to a given symbol table to a member of the syntax node to make the various symbols available at “run time”. The symbol tables are hash tables on a stack, and I resolve symbols defined in a parent scope by inspecting the stack.

But the literature I’ve read (specifically Language Implementation Patterns by Terence Parr) talks about a scope tree as a distinct tree structure, like the syntax tree, and traversing the scope tree. Does a scope tree stand separately and alongside the syntax tree, and if so how does one track the current position in the scope tree while traversing the syntax tree? Is it simply a global pointer to a scope node/symbol table that’s adjusted whenever a scope-affecting node is encountered in the syntax tree? Or, Is it okay for the scope tree’s tree structure to be implicitly defined by piggy-backing the syntax tree as I have done? I feel I am polluting the syntax nodes definitions by adding a symbol table member.

# Answer
My opinion on this is that the scope tree is a derived entity from the syntax tree, therefore as you perform your semantic analysis by walking the syntax tree you create a temporary scope tree on the fly and by doing that, the current position is automatically tracked.

The point is that both the scope tree and the syntax tree have to be married together somehow. As this would allow you to track the position of the symbols in unison. So as you traverse a method called a() on the syntax tree you statically know where to start in the symbol tree.

Note: you do not require a scope tree, you could use a stack but the advantage of the tree is that the storage of the scope is persistent. Therefore for simple validations a stack could be used to determine whether or not a variable is out of scope but for mode advanced analysis problems a scope-tree which behaves like a multidimensional stack would be required.

i.e.:

```
int a()
{
    int b;
    int c;
    {
       int b;
       int c;
    }
}

int b()
{
     int a;
}

```

So whenever you go into a function such as **a** you can create a function node and every time you see a declaration you can create a symbol and add it to the function's scope (push) and when you see a declaration you can resolve it by traversing up the tree.

Language implementation patterns by Terence Parr has a complete example of this and a very useful book.
> 2 votes

---
Tags: data-structures, programming-languages, compilers
---


# Question
Title: Set of Turing machines that halt after exactly 14 steps
Let $M\_i$ be the Turing machine with Gödel number $i$. Let $$A = \\{i \mid M\_i \text{ with input \\(x\\) halts after exactly 14 steps}\\}$$ Is the set $A$ recursive?

# Answer
I assume you mean $M\_i$ is a TM which is determined by Gödel Number $i$ such that from $i$ one can always construct $M\_i$ in finite time and that $A = \\{i \mid M\_i \text{ halts after exactly 14 steps on \\(x\\) as input, where $i$ is a G}\ddot{o}\text{del Number}\\}$ where $x$ is constant.

$A$ is recursive if there exists a TM for $A$ that always halts.

Such a TM can can be constructed as follows:

1. If $i$ is a Gödel Number construct $M\_i$, else $i \notin A$, halt.
2. Run $M\_i$ on the constant $x$ for 14 steps, if it halts after exactly 14 steps then $i \in A$, else $i \notin A$, halt.

Both 1 & 2 always halt which means that the TM always halts. So $A$ is recursive.
> 3 votes

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


# Question
Title: How to simulate this randomized "finite" sum?
Consider the the Geometric Brownian motion

$\qquad dX\_t=\mu X\_t dt+\sigma X\_t dW\_t$, with $X\_0=1$, $\mu=0.2$, and $\sigma=0.30$.

for each $n=1,2,3,..$ let $h\_n=1/n$, and let $X^n\_n$ be the final value of the discrete process obtained from Euler scheme wrt $h\_n$, i.e.

$\qquad X^n\_{k+1}=X^n\_{k} +\mu X^n\_k h\_n +X^n\_k \sigma \sqrt{h\_n} \text{randn}(0,1),$

for $k=0,1,2,\ldots n-1$. Here $\text{randn}(0,1)$ means the standard normal random variable with mean 0, standard deviation 1.

That is, after using Euler scheme ,for each $n=1,2,3, \ldots$ you have a sequence (which depends on $n$)

$\qquad \\{1,X\_1^2, X\_2^n,\ldots, X\_n^n \\}$.

For simplicity assume that $F\_n\equiv X\_n^n$.

I do know how to find $F\_n$ for $n=1,2,\ldots$.

Assume that $N\sim \text{Geometric}(p)$, i.e, $P(N=k)=(1-p)^{k-1}(p)$ ( let assume $p=0.5$ here for simplicity), for $k=1,2,3,\ldots$.

My question here is:

1. How to simulate this sum

$\qquad Y=\sum\_{k=1}^{N}\frac{(F\_{k+1}-F\_{k})}{2^k} N^2 $?

Using geornd(p) provided by matlab, I do know how to generate $N$.
2. How to approximate $E(Y)$?

My confusion comes from here. There are random variables floating around here: $N$ and $F\_{k+1}-F\_{k}$. Assume that $N$ and $F\_k$ are independent, so we have

$\qquad E(Y)=\sum\_{k=1}^{\infty}\frac{E\[(F\_{k+1}-F\_{k})\]E\[N^2 I\_{k\leq N}\]}{2^k} $.

# Answer
> 1 votes
Let me give you some basic principles that seem helpful for your problem:

* **How to estimate an expected value.** You want to estimate $\mathbb{E}\[Y\]$. Here's a standard fact: if you can sample from the distribution of $Y$, then you can estimate $\mathbb{E}\[Y\]$. Concisely, what you do is sample $n$ values according to the distribution of $Y$, then take their average; the result is a pretty good estimate for $\mathbb{E}\[Y\]$. The larger the value of $n$, the more accurate your estimate will be.

With more mathematical precision: let $y\_1,\dots,y\_n$ be the result of sampling $n$ times from the distribution of $Y$. This means that they come from i.i.d. r.v.'s with the same distribution as $Y$. Now let $\hat{y} = (y\_1+\dots + y\_n)/n$ be the average of these values. Then it follows that $\hat{y}$ is a good estimate for $\mathbb{E}\[Y\]$ (with high probability). In particular, $\mathbb{E}\[\hat{y}\] = (\mathbb{E}\[y\_1\]+\dots + \mathbb{E}\[y\_n\])/n = (\mathbb{E}\[Y\]+\dots + \mathbb{E}\[Y\])/n = \mathbb{E}\[Y\]$, so $\hat{y}$ is an unbiased estimator for $\mathbb{E}\[Y\]$. Also, by a similar calculation, $\text{Var}\[\hat{y}\] = \text{Var}\[Y\]/n$; the interpretation of this is that the error in your estimate of $\mathbb{E}\[Y\]$ will typically be roughly on the order of $\sigma/\sqrt{n}$, where $\sigma = \sqrt{\text{Var}\[Y\]}$ is the standard deviation of $Y$. Thus, if $Y$ has variance that is not too large, then this approach gives a reasonably accurate estimate of $\mathbb{E}\[Y\]$.

In your case, this shows how to answer your second question: if you can sample from $Y$, this gives you one candidate way to estimate $\mathbb{E}\[Y\]$. There are other ways to get an estimate, but this is a simple method that applies whenever you know how to sample from the underlying distribution.
* **How to sample from a sum of random length.** The next question is, how to sample from $Y$? The challenge you seem to be struggling with is how to deal with the fact that the definition of $Y$ is as a sum containing $N$ terms, but where here $N$ is a random variable.

It turns out there is a simple way to deal with this. In particular, you can sample from $N$ by using the following process:

1. Sample from $N$, i.e., pick a random value for $N$ by sampling from a geometric distribution (since that's the distribution of $N$).
    2. Now you have a fixed, constant value for $N$, so it becomes easy to sample from $Y$. In particular, for this fixed value of $N$, sample a random value for $F\_1,F\_2,\dots,F\_{N+1}$ (according to the distribution of these random variables). Then, plug those values into the definition of $Y$; the result will be a random value for $Y$, picked according to the correct definition for $Y$.

In general, if you have a random variable that is defined by some stochastic process, then you can sample from it by simulating the process, sampling from random values whenever the process does.

So, let me spell out the implications for you. This means that if you can figure out how to sample from the distribution of $F\_i$, then you can use the above two techniques to sample from the distribution of $Y$ and thereby estimate the value of $\mathbb{E}\[Y\]$. This reduces your problem to a smaller/simpler one: figuring out how to sample random values, distributed according to the distribution of $F\_i$.

---
Tags: algorithms, randomized-algorithms, sampling, monte-carlo
---


# Question
Title: pda: transformation between acceptance by empty stack and final states
I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state with a new start stack symbol, and another state after the original final states for emptying the stack. I understand the new state for emptying the stack, but why do we need a new start state and a new start stack symbol? Assume the the old pda has start state q0, start stack symbol Z0, when it goes to a final state qf, you may/may not expose Z0 on the stack. To make it into a pda accepting empty stack, can't we just create another state qe with an edge from qf-\>qe, at qe you can pop off any stack symbol until it becomes empty. What's wrong with my thoughts?

# Answer
> 4 votes
If I am understanding this correctly, you want to transform a PDA with final state acceptance into one that accepts by empty stack.

First point is, like you mention, when entering an "old" final state to go into a special state where the stack is emptied.

Second point is that we do not want to reach an empty stack at another moment during the computation. Note in that case the old automaton does not accept, but the new one accidentally does! The solution is (indeed) to add a new bottom symbol that can not be removed except at the special state. In that way accidental accepts are avoided. (And this what I understand is the extra part of the construction.)

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


# Question
Title: Expressing that a function converges to 1 with linear rate using Landau notation
I am working on an algorithm which approximates a certain optimal quantity. The approximation becomes better when the size of the problem ($n$) becomes larger: the difference from the optimum is approximately $1/n$.

Initially, I wrote that the algorithm achieves an approximation of:

$$\Omega(1-1/n)$$

But, now I am not sure this notation is correct: it is just like writing $\Omega(1)$ (the smaller element is swallowed in the larger element, which is 1).

Should I write:

$$1-O(1/n)$$

Or maybe:

$$1-1/\Omega(n)$$

Which of these is the correct notation?

# Answer
Both of the options you listed are acceptable. They have the same meaning; $f\in O(1/n)$ if and only if $1/f \in \Omega(n)$.

Let $f\in O(1/n)$. Then there exist $n\_0,M\>0$ such that for all $n\>n\_0$, $f\leq M/n$. Then $1/f\geq n/M$ for all $n\>n\_0$, thus $1/f\in \Omega(n)$, since for $n\>n\_0$, $1/f \geq 1/M \cdot n$.

The other direction is similar.
> 5 votes

# Answer
What you want to write, I think, is $1 - \Theta(1/n)$, unless you want to be more detailed and fill in the particular value $c$ so that you can write $1 - c/n + O(1/n^2)$.

While $1 - O(1/n)$ is accurate, it's kinda weird because $1 \in 1 - O(1/n)$, and even $1 + 1/n \in 1 - O(1/n)$, but I think it's still saying what you want. Maybe $1 - |O(1/n)|$ would be clearly understood if the sign bothers you like it does me.

$1 - 1/\Omega(n)$ doesn't have the sign problem that $1 - O(1/n)$ does, but it looks weird (and awkward to do calculation with), so I would avoid writing something like that.
> 1 votes

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


title: Extra space of MergeSort

text:
# Question
Title: Extra space of MergeSort
Here is my implementation of mergeSort. I need `n` extra space for the helper array. But what about recursive calls? I call sort `log n` times. mergeRoutine is a tail call, and it doesn't add to the call stack.

The extra space I need equals to `n + log n`. How can the extra space be `O(n)`?

I think we just consider `log n` negligible.

```
public class MergeSort {

    private int[] array;
    private int[] helper;

    public MergeSort() {
        this.array = array;
        this.helper = new int[array.length];
    }

    public void sort() {
        sort(0, array.length - 1);
    }

    private void sort(int start, int end) {
        if (end > start) {
            int middle = (start + end) / 2;
            sort(start, middle);
            sort(middle + 1, end);
            mergeRoutine(start, middle, end);
        }
    }

    private void mergeRoutine(int start, int middle, int end) {
        for (int i = start; i <= end; i++) {
            helper[i] = array[i];
        }
        int k = start;
        int i = start;
        int j = middle + 1;
        while (i <= middle && j <= end) {
            if (helper[i] <= helper[j]) {
                array[k] = helper[i];
                i++;
            } else {
                array[k] = helper[j];
                j++;
            }
            k++;
        }

        // Copy the rest. Either of the while loops works, not both.
        while (i <= middle) {
            array[k] = helper[i];
            i++;
            k++;
        }
    }
}

```

# Answer
$O(n)$ denotes the set of all functions $f(n)$ that are, for sufficiently large $n$, at most a constant factor larger than $n$. The notation $f(n) = O(n)$ is confusing because it really means $f(n) \in O(n)$.

E.g. $2n+5 \in O(n)$, $n/2 \in O(n)$, $\sqrt{n} \in O(n)$, $n + log\ n \in O(n)$ (the latter, because indeed $log\ n$ is negligible compared to $n$, e.g. $n + log\ n \< 2n$ and $2n \in O(n)$).

However, $n^2 \notin O(n)$ because there's no constant $k$ that can make $n^2 \< k n$ for all sufficiently large $n$.
> 2 votes

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


# Question
Title: Checking acceptance of a word vs finding an accepted word
We know that checking whether some word w is accepted by a turing machine TM is undecidable. But what about the problem of finding one accepting word of a TM?

Are these two problems related in some way, i.e. undecidability of one implies the undecidability of other (in any structure, like FA, LBA, PDA etc)?

My hunch is that they are not related but I am not able to argue why?

# Answer
## The two problems are Turing equivalent: one is undecidable for Turing machines iff the other is.

Deciding whether a Turing machine (TM) $M$ halts on a specific input $x$ is the Halting problem for Turing machines.

Given a TM $M$, we want to know whether it halts on some word. From $M$ we build a TM $M^\*$ that, independently of its input, dovetails the computation of $M$ over all inputs (i.e. it mimics the computation of $M$ on all possible inputs in parallel), and halts iff one of these computations halts. If we had an oracle $H$ that decided the halting problem, it could decide whether $M\*$ halts or not, hence whether the TM $M$ halts on some input. This is only for the decision on the existence of that input, but the same dovetailing construction could then be used to compute the halting input when it is known to exist. Hence we could build a TM that always halts, either with a word on which $M$ halts if there is one, or with failure when there is none.

Hence, if the halting problem were decidable, the problem of deciding whether a TM halts on some input, and determining that input wold be decidable too.

Conversely, let us assume that it is decidable whether a TM halt on some input. Then given a Turing machine $M$ and and input $x$ we want to decide whether $M(x)$ halts (the halting problem for $M$ on input $x$). For this we build a machine $M'$ that, independently of its input, will simply mimic the machine $M$ running on input $x$. Hence the machine $M'$ halts on some input (thus on any input) iff $M$ halts on input $x$. Hence we have a decision procedure for the halting problem if we have a decision procedure for halting on some input.

Both problems are Turing reducible to each other. Hence they are Turing equivalent. If one were to be decidable, the other would be too. Or, to take the contrapositive, the undecidability of one implies the undecidability of the other.
> 2 votes

---
Tags: computability, turing-machines, reductions
---


# Question
Title: Depth perception - detect how far into a scene a user is looking
I would like to know about how we can detect how 'deep' into a scene a user is looking. If looking into a 3D environment, with an object close to the user and one further away, how can we detect when the user is looking at the object further away? Or, rather, how can we detect which object a user is looking at in a 3D environment?

I am asking here because I'm not sure what this technology is called, or even if it exists, and so am hoping for some pointers into what I should be reading/looking at.

If anyone has some resources for me (links, algorithm names, books, articles, etc.), it would help a lot, but if you are able to explain a little, I'd really appreciate that, too.

Many thanks.

# Answer
> 3 votes
If you know the gaze direction angles of each eye (as well as head position and orientation), then the corresponding rays intersect roughly at the fixation point in 3D. This straightforward approach should work in theory, but in practice it is still quite challenging due to both technical and physiological factors.

Pfeiffer, Latoschik and Wachsmuth summarize quite accessibly the state of the art in 3D eye-fixation tracking as in 2008. Here, the intuitive approach I just described was still outperformed by another algorithm.

As the following link suggests, however, the problems with geometrical approaches may have been resolved since 2008. This commercial application appears to use the intersection-point method, though I doubt that the applied algorithms are published.

---
Tags: algorithms, terminology
---


# Question
Title: How to compare SURF points in two images
I know how to find SURF feature points and have code to find them, but I have no idea how to find the same point in 2 different images, I have laplacian, scale, orientation, descriptor, response and x, y. If i give it a very simple image, a triangle with no bottom and place it in two different places in two different images none of the info about the points are the same, Any help appreciated on how to compare points.

# Answer
> 3 votes
You compare the descriptors. The simplest approach is for every descriptor in image 1, you find its nearest neighbor in image 2. There are various strategies for discarding ambiguous matches, ensuring uniqueness of matches, using kd-trees for speed, etc. See the documentation for the matchFeatures function in MATLAB.

---
Tags: computer-vision
---


# Question
Title: Are there any non-naive parallel sparse matrix multiplication algorithms?
I was wondering about a problem in analyzing a social network (counting friends-in-common between all pairs of members) that requires squaring its adjacency matrix, and started reading up on algorithms for multiplying sparse matrices.

However, all I found so far were different ways of arranging the more or less naive "outer product" algorithm between processors - the same total number of multiplications/additions with different amounts of communication and additional algorithmic overhead (which, though, is undoubtedly important).

The most non-trivial algorithm I found was the Yuster-Zwick algorithm described in Fast sparse matrix multiplication, which is basically a combination of the same old naive algorithm and using a fast dense method for the dense part of the problem.

I looked at how sparse matrix multiplication is implemented in MLLib and it, too, appears to use the simple block-based algorithm.

Are there any parallel algorithms for multiplying sparse matrices that are substantially different from the naive one - as different as Strassen's or Coppersmith-Winograd's algorithms are from the naive algorithm for multiplying dense matrices?

For concreteness, let us assume that the matrices are sparse enough that number of non-zeros in the arguments and in the result are both $O(N)$.

# Answer
This recent paper proposes a different approach, based on hypergraph partitioning.

Grey Ballard, Alex Druinsky, Nicholas Knight, and Oded Schwartz. 2015. Brief Announcement: Hypergraph Partitioning for Parallel Sparse Matrix-Matrix Multiplication. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA '15). ACM, New York, NY, USA, 86-88. DOI=10.1145/2755573.2755613 http://doi.acm.org/10.1145/2755573.2755613
> 4 votes

---
Tags: complexity-theory, parallel-computing, matrices, linear-algebra, mapreduce
---


# Question
Title: Graph theory, $n$ people sitting around table
$n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice.

1. How big can $k$ be in terms of $n$?
2. Does everybody get to sit next to everybody else?
3. How many seating arrangements are there?

# Answer
*Point 3.* If the seats are unlabelled, the number of arrangements is $\frac{(n-1)!}{2}$.

*Explanation*: put a hat on one of the person and take it as the leader. Then you have $n-1$ choices for the person to his right and so on. But each arrangement is counted twice if you consider that circular arrangement $(a,b,c,d)$ is the same as the circular arrangement $(a,d,c,b)$.

*Point 2.* Answer is no. Take four people. They can only share one meal in your conditions. The people facing each-other will never eat side by side :-(

*Point 1.* You basically want to partition the edges of the complete graph on $n$ vertices into $k$ hamiltonian cycles. An obvious upper bound is then that $nk \leq {n \choose 2}$ so that $k \leq \left\lfloor \frac{n-1}{2} \right\rfloor$. This upper bound is met when $n$ is a prime number (take a first cycle then people at distance 2 then people at distance 3...)
> 3 votes

---
Tags: graphs, combinatorics
---


# Question
Title: Flow in a network: Conservation of flow definition
This might be too easy... But I just don't get it.

I've been reading about flow in networks and I stumbled upon this definition in wikipedia: https://en.wikipedia.org/wiki/Flow\_network

$\sum\limits\_{w\in V} f(u,w) = 0 $ $(\forall u \in V-\\{s, t\\})$

That implies $\sum\limits\_{(u,v)\in E} f(u,v) = \sum\limits\_{(v, z)\in E} f(v,z)$

It sounds trivial, but how does that implication work? The flow is 0 when there is no edge. So I think I can rewrite the first sum to:

$\sum\limits\_{w\in V} f(u,w) = 0 \iff \sum\limits\_{(u,v)\in E} f(u,v) = 0 $ for a node $u$

That would result in every flow being zero, wouldn't it? What am I doing wrong?

Thanks in advance :)

# Answer
> 2 votes
The short answer is $f(u,v)=-f(v,u)$. Note that the first sum includes both vertices $w$ such that $(u,w) \in E$, as well as vertices $w$ such that $(u,w) \notin E$ but $(w,u) \in E$. Now unpack the implications of the first sum, separating by these two cases, and I think you'll see what happens.

For a more lengthy explanation, this is covered in standard textbooks. Make a trip to a library to check out a few textbooks to find a detailed derivation; or, there are even online algorithm texts.

---
Tags: network-flow, ford-fulkerson, max-flow
---


# Question
Title: How to test image segmentation algorithms?
What would be an ideal environment/manner to judge the effectiveness of multiple segmentation algorithms? The goal is to determine which algorithms provide the best results for pre-clinical imaging. Our group has considered a GUI in MATLAB, and have different modules for different algorithms. Various papers have conducted such algorithm analyses in clinical scenarios, but none give an indication to their environment.

# Answer
> 0 votes
Google "image segmentation benchmark". You will find various data sets with ground truth, such as this one.

---
Tags: algorithms, algorithm-analysis, image-processing, computer-vision
---


# Question
Title: Can someone clarify landau symbols definition please?
I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know that technically the correct notation is to say $f(n)$ is an element of $O(f(n))$, not $f(n) = O(f(n))$.

Loosely, my understanding is this, given$ f(n) = n^2 + 2n +log(n)$ Big O represents the upper magnitude, so it would be correct (according to a past CS tutor), but not very accurate, to say $O(f(n)) = n^3$, but incorrect to say $O(n) = log(n)$, whereas the $Ω(f(n)) $represents the lower bound, so it would be correct, but inaccurate to say $Ω(f(n)) = log(n)$ or (not sure about this one), $Ω(f(n)) = 1$.

I know that $Θ(f(n))$ is defined as the intersection of $O(f(n))$ and $Ω(f(n))$, but is it valid to drop off lower orders of magnitude in the case of $Θ(f(n))$? ie. is $Θ(f(n)) = n^2$ correct? If not, what is the correct equality?

What I am entirely unsure about is $o(f(n))$ and $ω(f(n))$. I've seen the mathematical definitions and I know that the only difference between them and $O(f(n))$ and $Ω(f(n)) $respectively is that rather than "there exists C", it is "for all C", but my understanding of mathematical symbols is (at this stage) embarrassing. If anyone could shed some light on all of the above it'd be appreciated, thanks.

# Answer
> 6 votes
In the case of $O(f(n))$ and $\Omega(f(n))$ you are correct in that they can be wildly inaccurate and still be correct, for instance, $n$ is $O(2^n)$ - this just does not provide good information.

For $\Theta$ yes you can drop the lower orders of magnitude. What "$f(n)$ is $\Theta(g(n))$" means is that there are two constants, $C\_1$ and $C\_2$, and two values $n\_1$, $n\_2$ such that $C\_1g(n)\>f(n)$ for all $n$ greater then $n\_1$, and likewise $C\_2g(n)Nf(n)$ for all $n$ greater then $n\_2$. In your case we can see that multiplying $n^2$ even by 2 will dwarf the remaining values of $f(n)$ for sufficiently large $n$, likewise multiplying by 1 will make it always smaller.

Little $o$ and $\omega$ notation is used to describe a function as being orders of magnitude less then another. When we were in big $o$ notation, as long as one constant $C$ existed such that $Cg(n)\>f(n)$ then $f(n)$ is $O(g(n))$, with little $o$, every possible $c$ must cause this to happen. The easiest way to find this is to take the limit of $\lim\_{x \to \infty} \frac{f(n)}{g(n)}$: if it is zero then $f(n)$ is $o(g(n))$; if it is $\infty$ then $f(n)$ is $\omega(g(n))$

# Answer
> 6 votes
You cannot write $O(f(n)) = n^3$ or $O(f(n)) = \log n$ since this is a "syntax error". Big O notation is not symmetric, and can only be used on the right-hand side, or in a chain of inequalities $f(n) = O(g(n)) = O(h(n))$ (formally, this means $f(n) \in O(g(n)) \subseteq O(h(n))$).

Your function $f(n)$ satisfies $f(n) = \Theta(n^2)$, as well as $f(n) = \Theta(n^2 + 2n + \log n)$, $f(n) = \Theta(n^2 + n)$, $f(n) = \Theta(17n^2 + n/\log n + 5\log\log n)$, and many more. Regarding big O and big Omega, there are even more options, for example $f(n) = O(n!^2)$ and $f(n) = \Omega(1/n)$.

That said, when stating big Theta estimates, we are usually aiming for the simplest possible expression on the right, so in your case we are most satisfied with $f(n) = \Theta(n^2)$. With big O and big Omega, we are looking for both simplicity and tightness, which is why we would be most satisfied with $f(n) = O(n^2)$ and $f(n) = \Omega(n^2)$ ($f(n) = \Omega(\log n)$, for example, is simple but not tight).

---

The notation $f(n) = \Theta(g(n))$ means that for some constants $c,C\>0$, $$ c \leq \frac{f(n)}{g(n)} \leq C. $$ In other words, $f(n),g(n)$ are the same up to a (multiplicative) constant. The notation $f(n) = O(g(n))$ corresponds to just the upper bound $f(n) \leq Cg(n)$, and $f(n) = \Omega(g(n))$ corresponds to just the lower bound $f(n) \geq cg(n)$.

If you think of $f(n) = \Theta(g(n))$ as $f(n) = g(n)$ (up to constants), then $f(n) = O(g(n))$ is like $f(n) \leq g(n)$, and $f(n) = \Omega(g(n))$ is like $f(n) \geq g(n)$.

The notation $f(n) = o(g(n))$ just means that $f(n)/g(n) \to 0$, and $f(n) = \omega(g(n))$ just means that $f(n)/g(n) \to \infty$, so that $f(n) = o(g(n))$ is the same as $g(n) = \omega(f(n))$.

(Caveat: the discussion above assumes all functions are positive.)

# Answer
> 0 votes
With $\mathcal{O}$ you always want to have a function that is more or equal to your function asymptotically. So you can pretty much calculate with it.

Have in mind we are using $n \in \mathbb{N} = \\{1, 2, 3,...\\}$. That's relevant for the first inequality.

$f(n) = n^2+2n+5 \leq n^2+2n^2+5 = 3n^2+5 \stackrel{n \geq 3}{\leq} 3n^2+n^2 = 4n^2$

You can then use that $4$ as the constant factor $c$ so you'll get: $f(n) \in \mathcal{O}(n^2)$

And that is pretty accurate. You can however still size up the $4n^2$ and still be valid. The more margin you introduce, the more accuracy you lose.

---

The idea behind dropping off lower orders of magnitude for $\Theta$ is similar.

By now we know $f(n) \in \mathcal{O}(n^2)$ with $c=4$

For $\Omega$ you just drop of summands, so it gets smaller. $f(n) = n^2+2n+5 \geq n^2 + 5 \geq n^2 \implies f(n) \in \Omega(n^2)$

Now you now $f(n) \in \mathcal{O}(n^2)$ and $f(n) \in \Omega(n^2)$

This directly implies $f(n) \in \Theta(n^2)$

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


# Question
Title: Problem of finding pairs of elements that co-occur in some number of sets
I have a fairly general problem and I wonder if it has a name. The problem statement, as best I can put it, is the following:

> Let $I=\\{i\_1,i\_2,...,i\_n\\}$ be a set of items. Let $C=\\{C\_1,C\_2,...,C\_m\\}$ be a set of containers. Each container is unique and contains a set of items from $I$. Let $C\_{a,b} \subseteq C$ be the set of containers that contain both $i\_a$ and $i\_b$. Find all $(i\_a, i\_b)$ pairs where $\left\vert{C\_{a,b}}\right\vert \geq k$ for a given $k \in \mathbb{N}$.

If the items are people and the containers are times and places, then we are asking which people met at least $k$ times. If the items are groceries and the containers are shopping carts, then the problem is a variation of association rule learning. If the items are words and the containers are documents, then we are looking for a co-occurrence network.

# Answer
> 1 votes
You can look into bipartite graphs; the item-set relationships form this type of graph, and the process of clustering highly-connected nodes (loosely speaking) is called community detection (it's similar to frequent itemset mining).

# Answer
> 0 votes
I don't know if it has a special name. It looks like one algorithmic approach to solve it is by using matrix multiplication: let $M\_{i,j}=1$ if item $i$ is in container $j$, otherwise $M\_{i,j}=0$; then compute $N = M \cdot M^t$ and search for all cells of $N$ such that $N\_{a,b}\ge k$. In addition to the problems you mention, it's also similar to Computing the "at least k friends in common" graph.

---
Tags: reference-request
---


# Question
Title: Difference between $F(n)=O(n)$ and $F(n)\le O(n)$?
In a research paper I read $F(n) \leq O(g(n))$ and $F(n) \geq \Omega(h(n))$.

Isn't this the same as $F(n) = O(g(n))$ and $F(n) = \Omega(h(n))$?

Is there a difference?

# Answer
The notations $f(n) = O(n)$ and $f(n) \leq O(n)$ mean the same thing. Sometimes want to emphasize that the asymptotic estimate is coarse, and then you can use $\leq$, for example $\log n \leq O(n)$. This is not too common if all you're doing is just stating a single estimate, but is more common in a long calculation in which some steps are equations and some steps are inequalities, for example $$ H\_n + 5n = \log n + O(1) + O(n) \leq O(n). $$ In this particular example a simple equality would be more common, but in more complicated situations you could see an inequality. It is up to the authors' personal style. As a reader, you can just ignore this distinction.
> 3 votes

# Answer
I often see `F(n) = O(g(n))`, but also `F(n) ∈ O(g(n))`. `F(n) ≤ O(g(n))` is a little bit rarer.

All versions mean the same: `F(n)` does not grow faster (asymptotically) than `g(n)`.

The same holds for the other symbols `ω` (`>`), `Ω` (), `Θ` (`=`), `o` (`<`).

What notation is more correct, depends on the definition of the big O Symbol. In most cases `O(g(n))` is defined as a set of all functions that grow not faster than `g(n)` (asymptotically), so the the correct way to write it down would be `F(n) ∈ O(g(n))`.

But one could define `O` also as something like a function (`O: g → f`) that turns `g(n)` into the function `f(n)` with the property that f(n) grows not faster than `g(n)` (asymptotically). Then would the notation `F(n) = O(g(n))` be the right. This is sometimes useful, if you want to do something like `F(n)/G(n) = f(n) + o(1)`, which would make no sense if `o(1)` is a set.

I would say `F(n) ≤ O(g(n))` is something we call in Germany "doppelt gemoppelt", which means something like "done twice". The big O means that it grows not faster than, so it includes the "≤" already. But maybe one want it to make it more clear and visible by the first look or something. But you should also check, if the author wants to say something special with this. I saw a lot people that were struggling with something like `2ⁿ ∈ O(n!)` or `log n ∈ O(n⁵)`. Both is correct, but the bounds are not tight. maybe the author wants to underline that the bound is not tight.
> 2 votes

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


# Question
Title: The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?
My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

I understand the argument of the answer above. Also the answer is given in this book ''The Desing of Approximation Algorithms'' that I am reading. In \[pp. 67, §2\], the authors said:

> Algorithm 3.1 takes $O(n\cdot \min(B, V))$ time. This is not a polynomial-time algorithm, since we assume that all input numbers are encoded in binary; thus, the size of the input number $B$ is essentially $\lg B$, and so the running time $O(n\cdot B)$ is exponential in the size of the input number $B$, not polynomial. $\cdots$

I understand that $O(n\cdot B)$ is exponential in the size of the input number $B$, but also, in my point of view (which is wrong), $O(n\cdot B)$ is exponetial in the size of the input number $n$, i.e., the size of the input $n$ is $\lg n$. Why not? (If I were to represent $n$ in binary I would take $\lg n$ size, no?)

# Answer
$n$ is not part of the input, $n$ denotes the number of objects in the input.

The input consists of the capacity of the knapsack, a list of objects, each with a value and weight. If there are $n$ objects in the instance then the size of the instance is at least $n$ since each object needs to be represented (with at least one bit). Therefore $n$ is polynomial in the size of the input.

In general, the size of the input (if all weights and values are at most $B$) will be $O(n \log B)$, since there are $n$ objects to represent and representing an object (which is two numbers at most $B$) will take around $2\log B$ bits.
> 6 votes

---
Tags: polynomial-time, knapsack-problems
---


title: Tolerated use of the term topology

text:
# Question
Title: Tolerated use of the term topology
In the field of data structures (and maybe in graph theory), can we use the term topology to speak about the shape of a tree? For instance, consider the two following trees :

1) The first one: Node $a$ is parent of $b$ and $c$. Node $e$ is parent of $a$ and $d$

2) the second one: Node $a$ is parent of nodes $b$, $c$ and $d$.

Can we say that their topology are different, in the sense that the set of relations parents/children are different?

# Answer
Yes, I suppose you could, though it might be viewed as a somewhat informal usage of the term "topology". "Shape" would probably be a better word, as @Raphael suggests.

A more precise way would be to say that these two trees are not isomorphic.

Background: Two graphs $G,G'$ are considered isomorphic if there exists a map $f:V \to V'$ that is a graph isomorphism. Since any tree can be viewed as a graph, you can consider two trees to be isomorphic if they are isomorphic as graphs. One can also define a natural notion of a tree isomorphism directly; this happens to be equivalent to the notion of a graph isomorphism for unrooted trees, but is slightly different (and more appropriate to use) for rooted trees. You can read more about isomorphisms in standard sources.
> 1 votes

---
Tags: graphs, terminology, data-structures, trees
---


# Question
Title: Traversing a graph with respect to some partial order
Recently I was faced with the following Graph traversal problem: "Given an arrangement of buildings in form of a DAG. All the buildings have to be colored, but there is an order for that represented by edges in the DAG. If there is an edge from A-\>B, this would mean building B can only be colored after building 'A' has been colored. Also given is an array which provides the initial cost of coloring each building (vertex) in the graph. The actual cost of coloring a building 'v' is I(v) * C(v), where 'I(v)' is the number of buildings colored before 'v' plus '1' and C(v) is its initial cost of coloring provided in the array. Find the minimum actual cost of coloring all the buildings in the graph."

If there an is an edge from A-\>B, building B can be colored only after building A has been colored. Of course, there can be multiple routes to B in the graph, for instance from A-\>B and C-\>B. In this case if the provided array is (2,1,3) for coloring (A, B, C), and we choose to color building in the order of (A, B, c) then total cost = 1\*C(A) + 2\*C(B) + 3\*C(C) = 1\*2 + 2\*1 + 3\*3 = 13. However we cannot have an ordering where B is colored first.

I came up with a brute force solution to this problem. Topological sorting might help, but I couldn't really figure out how. Any suggestions?

# Answer
This can be formulated as an instance of integer linear programming, and then handed to an ILP solver. You could try that to see if it leads to any speedups.

The formulation: introduce zero-or-one variables $x\_{v,t}$, where $x\_{v,t}=1$ means that vertex $v$ was colored at time $t$. (Here $v$ ranges over vertices of the graph, and $t$ ranges over $1,2,\dots,n$, where $n$ is the number of vertices.) The precedence constraints mean that for every edge $v\to w$, we introduce an inequality

$$x\_{w,t} \le x\_{v,1}+x\_{v,2}+\dots + x\_{v,t-1}.$$

Also we require that every vertex be colored exactly once: $x\_{v,1}+\dots+x\_{v,n}=1$ for each $v \in V$, and you can only color one vertex at each time instant: $\sum\_{v \in V} x\_{v,t}=1$, for each $t=1,\dots,n$. Now the goal is to minimize the objective function

$$\Phi = \sum\_{v,t} t C(v) x\_{v,t},$$

which is a linear function of the variables. So, this is an ILP instance and can be fed to an off-the-shelf ILP solver.

ILP solvers incorporate a number of clever heuristics. If you're lucky, it's possible that one of them might help solve the problem faster than brute-force enumerating all valid topological sorts of the graph.
> 1 votes

# Answer
This is a job-shop scheduling problem, known as $1|\textrm{prec},p\_i=1|\Sigma w\_i C\_i$. It is $NP$-complete.

Lenstra, J.K. and Rinnooy Kan, A.H.G.: Complexity of Scheduling under Precedence Constraints. In Operations Research, vol. 26, pp. 22-35 (1978)

Sadly the paper is not open-access. They show $NP$-hardness by reduction from Linear Arrangement (also known as Graph Bandwidth)
> 1 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Proving correctness of a recursive algorithm using induction
For the program

```
mean(A,n)

    if n = 1 then

       return A[n]

    else

       return A[n]/n+mean(A,n-1)*(n-1)/n

    end

```

Show that if the recursive call to mean (A, n-1) returns the mean of A\[1,...n-1\] then the call mean (A,n) returns the mean of A\[1,...n\].

I know that the program always terminates with mean (A,1) as per the basis step where with inductive hypothesis we are proving n \>=1 and we are in the else case, but I'm not sure how to show the last part using the n-1 inductive step.

# Answer
Your inductive hypothesis is ´mean(A, n-1)\` is the mean of $A\[1:n-1\]$, i.e. the first $n-1$ elements of $A$.

Formally this can be written as ´mean(A,n-1)\`$= \frac{\sum\_{i=1}^{n-1}{A\[i\]}}{n-1}$

Then we conpute `mean(A,n)` with that hypothesis.

When $n=1$, the result is $A\[n\]$, i.e., $A\[1\]$ which is the mean of $A\[1:1\]$.

Otherwise the result is `A[n]/n+mean(A,n-1)*(n-1)/n`,
i.e. $A\[n\]/n + \frac{\sum\_{i=1}^{n-1}{A\[i\]}}{n-1}\times \frac{n-1}n$ becaus of the induction hypothsis.

You only have to simplify this expression to reach the desired result.

The conclusion of all this is that the proof is very simple, but you have to write formally your hypothesis and computation. The best way to answer a question is to first express it clearly and completely.
> 0 votes

---
Tags: recursion, correctness-proof, induction
---


# Question
Title: Is L closed under linear-time reductions?
L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace.

> Is L closed under linear-time reductions?

It is possible that for some pair of languages Q and R, every linear-time reduction from Q to R requires more than logarithmic space. Up to linear space could be used while still remaining within linear time. So it isn't immediately obvious to me that L must be closed under linear-time reductions.

On the other hand, it is not clear what a counterexample would look like. One wants a language Q that can be linear-time many-one reduced to a language in L (for instance, to undirected graph st-connectivity), yet so that Q is not in L.

# Answer
L is closed under linear-time reductions if and only if L = P.

**Proof:**

If L is closed under linear-time many-one reductions then:

Since L has non-trivial problems, all problems that are solvable linear time are in L.

Let (x) be the modification of the most basic P-complete problem to ask about "the first sqrt(T) steps" rather than "the first T steps". Since unary-to-binary conversion can be done in linear time and \[square-roots can be computed and TMs can be simulated in quasi-linear time\], (x) can be solved in linear time. Since L has non-trivial problems, there is a linear-time many-one reduction from (x) to a problem in L. By this paragraph's assumption, that means (x) is in L. Since L can square unary inputs, there is a logspace reduction from the most basic P-complete problem to (x). Thus (x) is P-complete. Since (x) is in L, that means  P ⊆ L .

If L is closed under linear-time many-one reductions then then P ⊆ L. With no assumptions, L ⊆ P.  Therefore, if L is closed under linear-time many-one reductions then then L = P. Since P can perform linear-time Turing reductions, P is closed under linear-time Turing reductions. Therefore, if L = P then L is closed under linear-time Turing reductions.  QED
> 2 votes

---
Tags: complexity-theory, reductions, complexity-classes, space-complexity
---


# Question
Title: Who coined the term "artificial intelligence"?
The most obvious (and commonly given) answer to this question is John McCarthy, but I have traced the first usage of this term to a 1955 paper, which McCarthy co-authored with Marvin Minsky, Nathaniel Rochester, and Claude Shannon. Although McCarthy was the lead author and probably the main organizer of the 1956 Dartmouth Summer Research Project on Artificial Intelligence, it could just as easily have been that one of these co-authors actually proposed the term "artificial intelligence". Does anyone know of any other evidence to suggest whose idea the actual term was? All of these individuals are now dead, but maybe some of their close associates or former students might be able to also shed light on the question.

# Answer
Based on my research, there is no conclusive answer as to who coined the term, although McCarthy can be credited with helping the term to find widespread acceptance within the computer science community. See "AI: The Tumultuous History of the Search for Artificial Intelligence" by Daniel Crevier (Published in 1993 by BasicBooks):

"Overcoming the resistance of some participants (Samuel felt that "artificial" sounded phony, and Newell and Simon persisted in calling their work "complex information processing" for years afterward), McCarthy persuaded the majority to go for "artificial intelligence." He lays no claim to having coined the phrase, and admits it may have been used casually beforehand. Yet nobody denies him the achievement of getting it widely accepted."

-- Daniel Crevier, p.50
> 1 votes

---
Tags: terminology, reference-request, artificial-intelligence, history
---


# Question
Title: Simple example: 2-approximation for vertex cover
I am having trouble finding an example for the following algorithm to prove that it calculates a 2-approximation:

> Repeatedly select a vertex $v$ of highest degree, add one of its edges $(v,w)$ to the cover, and remove all edges incident to $v$ or $w$.

Please give me insights on how to pick an example.

# Answer
> 1 votes
Hint:

1. Prove the stronger claim that if $M$ is *any* matching, then any vertex cover must contain at least $|M|$ vertices.
2. Conversely, if $M$ is any *maximal* matching (a matching which cannot be extended), then the $2|M|$ vertices in $M$ form a vertex cover.
3. Show that the greedy algorithm that you describe constructs a maximal matching.
4. Conclude that your algorithm (modified so that it outputs a set of vertices rather than a set of edges) is a 2-approximation for minimum vertex cover.
5. Consider the complete bipartite graph $K\_{n,n}$. What is its minimum vertex cover? What vertex cover does your algorithm produce?

---
Tags: approximation
---


# Question
Title: Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible?
could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to give a group of talented high schoolers who haven't seen matrices before a sketch/cursory proof of the result, but I couldn't think of a good way to explain it.

# Answer
> 6 votes
The algebraic proof goes like this. Fix a number of vertices $n$, and consider the "formal Laplacian" $n \times n$ matrix defined by $$ \begin{align\*} L(i,i) &= \sum\_{j \neq i} X(i,j) \\ L(i,j) &= - X(i,j). \end{align\*} $$ Here the $X(i,j)$ are commuting indeterminates. For every spanning tree $T$ of the complete graph $K\_n$ we can associate a degree $n-1$ monomial $X(T)$ as follows. Root the tree at the vertex $n$. For every non-root vertex $i$ with parent $j$, we include the variable $X(i,j)$ in the monomial. In total $X(T)$ is a product of $n-1$ monomials, one for every edge in the tree.

Let $M$ be the $(n,n)$ minor of $L$. We will show that $\det M = \sum\_T X(T)$. You can derive the matrix-tree theorem from this statement by substituting the actual graph for the indeterminates $X(i,j)$. If you wish, you can run the entire proof after doing the substitution, and then you don't have to talk about indeterminates.

Recall that $$\det M = \sum\_{\pi \in S\_{n-1}} (-1)^\pi \prod\_{i=1}^{n-1} M\_{i\pi(i)}.$$ We can write every permutation $\pi$ as a product of cycles $\pi\_1,\ldots,\pi\_{\ell(\pi)}$ and of fixed points $F(\pi)$, and then we get $$ \begin{align\*} \det M &= \sum\_\pi (-1)^\pi \prod\_{t=1}^{\ell(\pi)} \prod\_{i \in \pi\_t} (-X(i,\pi(i))) \prod\_{i \in F(\pi)} \left(\sum\_{j \neq i} X(i,j)\right) \\ &= \sum\_\pi (-1)^{\ell(\pi)} \prod\_{t=1}^{\ell(\pi)} \prod\_{i \in \pi\_t} X(i,\pi(i)) \prod\_{i \in F(\pi)} \left(\sum\_{j \neq i} X(i,j)\right), \end{align\*} $$ using the formula $(-1)^\pi = \prod\_{t=1}^{\ell(\pi)} (-1)^{|\pi\_t|+1}$. We can rewrite this as $$ \det M = \sum\_\pi D(\pi), $$ where $D(\pi)$ is the expression appearing above.

If we open up all the sums, we find that $\det M$ is a (weighted) sum of monomials of the form $X(\alpha) = \prod\_{i=1}^{n-1} X(i,\alpha(i))$. For each $\alpha$, we can look at the directed graph in which $i$ points at $\alpha(i)$. It's not hard to see that each such graph consists of a (possibly empty) collection of cycles $\alpha\_1,\ldots,\alpha\_{\ell(\alpha)}$ and a tree $T(\alpha)$ rooted at $n$. We will show that the coefficient of $X(\alpha)$ equals $1$ if $\ell(\alpha) = 0$, and vanishes otherwise. This will complete the proof.

Consider first the case that $\ell(\alpha) = 0$. In this case the only permutation $\pi$ for which $X(\alpha)$ appears in $D(\pi)$ is the identity permutation (since every $X(\beta)$ appearing in any other $D(\pi)$ contains some cycle), ans so the coefficient of $X(\alpha)$ in $\det M$ is indeed $1$.

Next, consider the case in which $\ell = \ell(\alpha) \neq 0$. In this case, for every subset $S$ of the cycles of $T(\alpha)$, $X(\alpha)$ appears in $D(\pi)$ for $\pi = \pi(S)$ which consists of the cycles in $S$, and it only appears in these $D(\pi)$. For every $S$, the coefficient of $X(\alpha)$ in $D(\pi(S))$ is $(-1)^{|S|}$. Therefore the total coefficient of $X(\alpha)$ in $\det M$ is $$ \sum\_{S \subseteq \\{\alpha\_1,\ldots,\alpha\_\ell\\}} (-1)^{|S|} = \sum\_{S\_1 \subseteq \\{\alpha\_1\\}} \cdots \sum\_{S\_\ell \subseteq \\{\alpha\_\ell\\}} (-1)^{|S\_1| + \cdots + |S\_\ell|} = \\ \sum\_{S\_1 \subseteq \\{\alpha\_1\\}} (-1)^{|S\_1|} \cdots \sum\_{S\_\ell \subseteq \\{\alpha\_\ell\\}} (-1)^{|S\_\ell|} = (1-1)^\ell = 0. $$ (This is just inclusion-exclusion. The previous case is the case $\ell=0$.) This completes the proof.

This proof is taken from lecture notes by Jacques Verstraete. See also Mark Muldoon's lecture notes, which presents this argument as a version of inclusion-exclusion.

---
Tags: graphs, linear-algebra
---


# Question
Title: About the definition of "differential privacy" in communication complexity
In the context of communication complexity I see a definition of differential privacy which isn't totally clear to me as to why it makes sense.

So the two parties $A$ and $B$ draw two strings $X$ and $Y$ from the set $S^n$ where $S$ is some finite set. Let $P$ be the protocol. Now if $z\_1 = (X\_1,Y\_1)$ and $z\_2 = (X\_2,Y\_2)$ are two instances drawn with a probability distribution $\mu$ over the set $S^n \times S^n$ then the protocol $P$ is called "$\epsilon$-differentially private" if the following holds:

$$e^{-2 \epsilon n} \leq \Pr\[P(z\_1) = p\] / \Pr\[P(z\_2) = p\] \leq e^{2 \epsilon n}$$

* Now why does this make sense? What's the intuition?
* How is this related to the bounded derivative definition?

# Answer
> 2 votes
Your definition is wrong. The correct definition is as follows. A protocol $P$ is *$\epsilon$-differentially private* (for $\epsilon \> 0$) if for any two inputs $Z\_1,Z\_2$ differing in a single coordinates and any $p$, $$ e^{-\epsilon} \leq \frac{\Pr\[P(Z\_1) = p\]}{\Pr\[P(Z\_2) = p\]} \leq e^\epsilon. $$ For small $\epsilon\>0$, $e^\epsilon \approx 1 + \epsilon$, and $e^{-\epsilon} \approx 1 - \epsilon$; the quantity $e^\epsilon$ is easier to work with compared to $1+\epsilon$, since $e^{\epsilon\_1} e^{\epsilon\_2} = e^{\epsilon\_1+\epsilon\_2}$, whereas $(1+\epsilon\_1)(1+\epsilon\_2) \approx 1 + \epsilon\_1 + \epsilon\_2$ holds only approximately.

Another small note: the upper bound implies the lower bound and vice versa.

The definition implies that for any two inputs $Z\_1,Z\_2$ that differ in at most $d$ places, $$ e^{-\epsilon d} \leq \frac{\Pr\[P(Z\_1) = p\]}{\Pr\[P(Z\_2) = p\]} \leq e^{\epsilon d}. $$ In particular, if the inputs have length $m$, then for *any* $Z\_1,Z\_2$ we have $$ e^{-\epsilon m} \leq \frac{\Pr\[P(Z\_1) = p\]}{\Pr\[P(Z\_2) = p\]} \leq e^{\epsilon m}. $$ In your case $m = 2n$.

---
Tags: complexity-theory, terminology, cryptography, communication-complexity, differential-privacy
---


# Question
Title: How is a communication protocol a mechanism?
Given a finite set $\Sigma$ and a positive integer $n$, a mechanism is a set $\\{ \mu\_x \vert x \in \Sigma^n \\}$ such that $\mu\_x$ is a probability measure on some $\sigma-$algebra for each $x$.

Now given a communication protocol $P$ between two privately coin-flipping parties $A$ and $B$ who start with the inputs $x$ and $y$ respectively one defines this quantity called the $VIEW^A\_P(x,y)$ : \`\`a joint probability distribution over $x$, the transcript of the protocol $P$, private randomness of the party $A$, where the probability space is private randomness of both parties"

* What does the stuff in the quotes mean?
* Can someone help understand how is this $VIEW^A\_P(x,y)$ a \`\`mechanism" as defined earlier? (For this to be a mechanism, $VIEW^A\_P(x,y)$ for a fixed $x$, has to assign a probability to some set of outcomes and I am unable to see as to which set of outcomes is it assigning a probability and how)

---

A transcript of a protocol will be a sequence of private coin tosses and bits exchanged in every step. So if one fixes both $x$ and $y$ then I can imagine that a probability can be assigned to a protocol - which would be the probability for that sequences of coin tosses to have happened. But still whaht is an "event" here is not clear since I can't see a natural way to group together these "outcomes" (each of which is now a possible transcript when started with a $x$ and $y$).

But if one fixes only $x$ then nothing is clear to me..

---

Reference : http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/diffprivacy.pdf

# Answer
> 2 votes
The view of Alice is what Alice gets to see; it is a probability distribution that depends on the inputs of both players $x,y$. It is a distribution over triples $(x,\tau,r\_A)$, where $x$ is Alice's input, $\tau$ is the transcript of the protocol, and $r\_A$ is Alice's private randomness. This probability distribution depends both on $x$ and on Bob's input $y$.

Here is how to generate this probability distribution, given a protocol $P$ and the inputs $x,y$ of both players. Generate the shared randomness $r$ according to its distribution, and Alice's private randomness $r\_A$ according to its distribution. Run $P$, obtaining a transcript $\tau$. Output $(x,\tau,r\_A)$.

---
Tags: complexity-theory, communication-protocols, communication-complexity
---


# Question
Title: Hardness of problem related to number of subsets that satisfy a particular property
I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example:

```
A: has properties p1, p2, p4
B: has properties p2, p4
C: has properties p2, p1

```

The task is to find the number of subsets of elements, where the union of the properties of the elements in the subset are equal to some predefined set.

For example if the predefined set is:

* `{p2}`, then the answer is `0`, because there are no subsets with a union of `{p2}`
* `{p1, p2, p4}`, then the answer is `5`, because we can take `{A}, {A, B}, {A, C}, {B, C}, {A, B, C}`

This problem seems like it might be hard (e.g., NP-hard), but I can not find anything similar in this list of NP-complete problems. I do realize that this is only small subset of NP complete problems.

Is there an efficient algorithm for this problem? Or, is it NP-hard, and if so, how can we prove that?

# Answer
The problem is NP-hard: in fact, it is #P-complete. Therefore, it is unlikely you'll be able to find an efficient solution for this problem. The proof is by reduction from #Monotone-SAT.

As Ricky Demer explains, without loss of generality we can take the "predefined set" to be equal to the union of all properties. (If the predefined set is larger than that, the answer to your problem is 0. If the predefined set is smaller than that, then we can remove all elements that mention a property not found in the predefined set, and we get a new problem instance with the desired property.) So let's focus only on this case.

Here is the reduction from #Monotone-SAT. Suppose we have a CNF formula $\varphi$ over $n$ variables and with $m$ clauses, where all of the literals in each clause are positive (i.e., no variable is negated). Then we can define an instance of your problem that corresponds to $\varphi$. The problem instance has $n$ elements, one element for each variable, and $m$ properties, one property for each clause. The set of properties of a variable is just the set of clauses that mention that variable. Then the number of solutions to this problem instance is exactly the number of satisfying assignments to $\varphi$.

It follows that your problem is exactly as hard as #Monotone-SAT: any algorithm for your problem gives a solution to #Monotone-SAT. However, it is known that #Monotone-SAT is #P-complete. (In fact, we can make a stronger statement: #Monotone-2SAT is also #P-complete.) It is widely believed that #P-complete problems cannot be solved in polynomial time. Thus, there is unlikely to be any polynomial-time algorithm for #Monotone-SAT -- or for your problem.

That's the bad news. Now one slight bit of hope. There are off-the-shelf #SAT solvers out there that you could try applying to your problem. See, e.g., https://cstheory.stackexchange.com/q/1295/5038 for some pointers. Now you shouldn't expect them to be efficient -- they are subject to the same hardness result, and so they might be very slow for all but small problem instances. However, if you absolutely *must* solve your problem in practice, this is something you could try. There are also tools for approximate model counting, which could be used to compute an approximation/estimate for the number of solutions to your problem -- however, again, this is a hard problem and you shouldn't expect algorithms with a good worst-case running time.

My thanks to Ricky Demer for the key insight that enabled me to recognize the relationship to #Monotone-SAT.
> 2 votes

---
Tags: complexity-theory, combinatorics, np-hard, boolean-algebra, counting
---


# Question
Title: Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace
Exercise 4.29 from Quantum Computation and Quantum Information by Nielsen and Chuang has me stumped.

> Find a circuit containing $O(n^2)$ Toffoli, CNOT and single qubit gates which implements a $C^n(X)$ gate (for $n \> 3$), using no work qubits.

I've figured out that this can't be done classically.

I've figured out how to do it with $O(2^n)$ exponentially precise gates (nest the double-control-from-single-controls-and-square-root-of-operation construction inside itself $n-2$ times).

I've tried generalizing the above construction into accumulating a linear combination of controlled operations. For example, if I have 3 controls called A and B and C and make a vector of the various cases \[0, A, B, C, AB, BC, AC, ABC\] then:

* Applying an operation unconditionally adds \[1, 1, 1, 1, 1, 1, 1, 1\]
* Controlling an operation on A adds \[0, 1, 0, 0, 1, 1, 0, 1\]
* Xoring A into C then controlling an operation on C (then undoing the xor) would add \[0, 1, 0, 1, 1, 1, 0, 0\]
* Xoring (A and B) into C via a toffoli gate then controlling an operation on C would add \[0, 0, 0, 1, 1, 1, 1, 0\]

Then I would try to add (apply a root of X) and subtract (apply inverse square root) the various vectors I can make until the result comes out as \[0, 0, 0, 0, 0, 0, 0, N\].

But I keep hitting various walls, such as solutions ending up with large multiples (i.e. the gates I'm using become exponentially precise, which I think is a no-no) or just not being able to solve the system due to the interplay between generating elements with AND/XOR then solving with +/\* being non-standard or creating exponential numbers of gates.

What are some other approaches to try?

# Answer
> 5 votes
Eventually I ended up solving this for $O(n)$ gates. I wrote up a trilogy of blog posts on it.

1. Constructing Large Controlled Nots (classically, with an ancilla)
2. Constructing Large Increments (classically, with an ancilla)
3. Using Quantum Gates instead of Ancilla Bits

Of course it would suck if you found this twenty years from now and my website was long gone, so the basic steps follow in quickly-described image form.

# 1. Bootstrap a Borrowable Ancilla Bit

Use a square root and its inverse to reduce the maximum number of controls by one, creating an uninvolved wire for each operation. Then iteratively move controls off of non-Not operations, and re-arrange the cruft that results into large increment gates and single-qubit phase gates.

# 2. Use Single Ancilla Bit to Cut Operations in Half

For each large operation, use the uninvolved wire as a borrowed ancilla bit. Use it to transform the huge increment and controlled-not gates into smaller operations that each have approximately half of the wires uninvolved. Repeat twice, if required for the next step to have enough working space.

# 3. Use Many Ancilla Bits to Finish

For each still-too-large operation, borrow the many uninvolved wires as ancilla bits. Use them to get all the way down to Toffoli-or-smaller gates.

Those three steps will get you all the way from a fully-controlled-not to linearly many Toffoli, CNOT, and single-qubit gates. There's a few implied pieces, like how to merge a control into an increment gate, but they're pretty simple.

(Sorry for the inconsistent style of the diagrams.)

---
Tags: quantum-computing, circuits
---


# Question
Title: Combining these two results into one asymptotic notation
Assume you have two parameters, $N \gg 1$ and $\epsilon \< 1$.

I have an algorithm (and matching lower bounds) that runs in $\Theta(\epsilon^{-1}+\log N)$ for $\epsilon \> N^{-1}$, and $\Theta\big(N\log\big(\frac{2}{N\epsilon}\big)\big)$ otherwise.

I would like to write it using one notation (possibly with $\max$ or $\min$ operands), but can't get it right.

The problem is that $\log\big(\frac{2}{N\epsilon}\big)$ is negative for large values of $\epsilon$, so it doesn't seem to fit.

Any help will be appreciated :D.

# Answer
Not that I encourage you to do so, but here's one way: $$\Theta \left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) $$

For $\epsilon = \omega(N^{-1})$, the $\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor$ expression is $0$, and the left expression is $$\frac{1}{\epsilon+N^{-1}}+\log N = \Theta(\epsilon^{-1} + \log N)$$

For $\epsilon = \Theta(N^{-1})$, the whole expression translates into $\Theta(N)$.

For $\epsilon = o(N^{-1})$ you get: $$\Theta \left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$
> 1 votes

# Answer
Which asymptote do you want?

If you fix $\epsilon$ to be constant and let $N\to\infty,$ then asymptotically $\epsilon \> N^{-1},$ and so the behavior is $\Theta(\epsilon^{-1} + \log N) = \Theta(\log N).$
> 0 votes

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


# Question
Title: Why is a negative number a pseudo-positive number in ones' complement?
I'm studying ones' complement representation and I read in a book that a negative number in ones' complement is a pseudo-positive of value $R^n - 1 - |x|$.

However there is no demostration and I can't find it anywhere. If someone could tell me the reason I will be very thankful.

# Answer
One's complement stores negative numbers as their bitwise negation.

Suppose we're working in $b$ bits. A positive integer $x$ is represented in binary by writing it as $x = \sum\_{i=0}^b a\_i2^i$, where each $a\_i\in\\{0,1\\}$. The bitwise negation of $x$, then, is $$\overline{x} = \sum\_{i=0}^b (1-a\_i)2^i = \sum\_{i=0}^b 2^i - \sum\_{i=0}^b a\_i2^i = 2^b - 1 - x\\,.$$
> 1 votes

# Answer
You are asking two questions:

1. How can I prove that negative numbers are stored as pseudopositive?
2. Why are negative numbers stored as pseudopositive?

The answer to the first question is that no proof is needed, since one's complement is a way of representing signed numbers as unsigned numbers, and it specifies that negative numbers are stored in this specific way. There is nothing to prove here, just read the definition of one's complement. In other words, this is true by definition.

Regarding the second question, storing numbers in this way facilitates arithmetic. For example, to add two numbers, you just add them as unsigned numbers, with an extra little fiddling depending on the sign bits; in two's complement you don't even need the extra fiddling.
> 1 votes

---
Tags: number-formats, numeral-representations
---


# Question
Title: Understanding Logical to Physical Addressing
I am trying to understand the concept of logical to physical addressing.
I am given 72 physical addresses (0-71) with values

A virtual address = 2^(p+w) p = page bits w = word bits

I know the page table is of size 6 indexed 0-5

If a page size is 16 words does that mean that the offset(w)=4, giving me 2^(p+4).

If thats the case how do I determine what the page number (p) if given a logical address of 12? I was thinking it would be 3 because I would need 3 bits to find the index of the page table 0-5, giving me 000 1100, index 0, offset 12. I feel like I might be missing something.

# Answer
> 0 votes
I think you are confused in how logical address is get converted into physical address of main memory. Let's take a walk from basics: logical and physical memory are divided into fixed size pages and frames respectively to remove external fragmentation.

As size of logical memory is generally bigger than physical memory so we can't bring all pages from logical memory into physical memory that's why we require a page table that contains the entry of pair(page no. , frame no.).

Now as always CPU generates a logical address of say 15 bits with 10bits for page size and 5bits for identifying frame no. from page table(5bits means that there can be maximum 2^5 pages), now using those 5 bits cpu index page table and find the frame no. in which the required page is residing say that's of 4 bits(that mean a maximum of 2^4 frames ) then the physical address will be made by replacing 5bits by those 4bits + 10bits in logical address.

Your interpretation in question is correct.

---
Tags: operating-systems, virtual-memory
---


# Question
Title: How to Prove NP-Completeness of Minimum Crossing Problem?
> In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. (from wikipedia)

I know that the problem of counting the Crossing Number of a graph to be less than or equal to `K` is proven to be NP-Complete by Garey and Johnson in 1983. I couldn't find the actual proof papers though.

So, what is the proof idea?

One way would be to reduce (in polynomial time) from some known NPC problem but to which one?

# Answer
Here is a short summary of the original paper. More modern treatments can be found in a paper of Cabello proving a hardness of approximation result. We are concerned with three different problems:

**CROSSING NUMBER**: Given a graph $G$ and a number $K$, can it be drawn with at most $K$ crossings?

**BIPARTITE CROSSING NUMBER**: Given a connected bipartite graph $G$ and a number $K$, can it be drawn in the unit square so that vertices of one part are on the top side, vertices of the other part are on the bottom side, all edges are within the square, and there are at most $K$ crossings?

**OPTIMAL LINEAR ARRANGEMENT**: Given a graph $G$ and a number $K$, can we arrange the vertices of $G$ in a line so that the total length of all edges is at most $K$.

The latter is known to be NP-complete. The reduction is from OPTIMAL LINEAR ARRANGEMENT to BIPARTITE CROSSING NUMBER, and then from BIPARTITE CROSSING NUMBER to CROSSING NUMBER.

There are several variants of the concept of *crossing number*, and the one meant here can be gleaned from the proof that crossing number is in NP: given a graph $G$ and a number $K$, to show that the crossing number is at most $K$, identify up to $K$ pairs of crossing edges, for each one introduce a new vertex, and add the appropriate edges so that the resulting graph becomes planar; planarity can be tested in polynomial (indeed, linear) time.

**OPTIMAL LINEAR ARRANGEMENT to BIPARTITE CROSSING NUMBER**: Given an instance $G=(V,E),K$ of OPTIMAL LINEAR ARRANGEMENT, we construct an instance of BIPARTITE CROSSING NUMBER as follows:

* For each $v \in G$, we include two vertices $v\_1,v\_2$ on opposite bipartitions, and $|E|^2$ copies of the edge $(v\_1,v\_2)$.
* Fix some ordering of $V$. For each $(x,y) \in E$ such that $x \< y$, include the edge $(x\_1,y\_2)$.
* Set the new $K$ to be $|E|^2(K-|E|) + |E|^2 - 1$.

Given a good arrangement $A$ of the vertices in $V$, the intended drawing of the new graph has both copies of $V$ equally spaced and ordered according to $A$, with edges $(v\_1,v\_2)$ being vertical (but slightly fanned so that they don't cross each other) and the "real" edges being straight. A "real" edge spanning a stretch of $\ell$ crosses $(\ell-1)|E|^2$ vertical edges, for a total of $(K-|E|)|E|^2$ crossings. There are also at most $\binom{|E|}{2} \leq \< |E|^2$ crossings between "real" edges.

Conversely, any drawing of the new graph with fewer than $|E|^4$ crossings must be of the form above (due to the vertical edges), and so we can read off a good arrangement of the original graph.

**BIPARTITE CROSSING NUMBER to CROSSING NUMBER**: Given an instance $G=(V\_1,V\_2,E),K$ of BIPARTITE CROSSING NUMBER, we construct an instance of CROSSING NUMBER as follows:

* We take all vertices in $V\_1,V\_2$ along with two special vertices $o\_1,o\_2$.
* We include all original edges.
* We connect $o\_i$ to each vertex in $V\_i$ using $3K+1$ edges (for $i=1,2$).
* We connect $o\_1$ and $o\_2$ using $3K+1$ edges.
* We use the same $K$.

Given a good drawing of the original graph, we draw the new graph by putting $o\_1$ above $V\_1$, $o\_2$ below $V\_2$, the edges from $o\_i$ to $V\_i$ are (almost) straight, and the edges connecting $o\_1$ and $o\_2$ go around the entire construction. This adds no new crossings.

In the other direction, we show that every good embedding of the new graph must be of this form, in a step by step fashion, completing the proof. I'm leaving this part to the reader.
> 4 votes

---
Tags: complexity-theory, graphs, np-complete, reductions, crossing-number
---


# Question
Title: How many inputs does the Hadamard gate have?
Look at the diagram in the middle of page 6-3 here, http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf

I am confused as to how should one think of the Hadamard gate.

As per the mathematics shown below it seems that the Hadamard gate, $H$ acts on tensor products of states as follows,

$$H( \otimes ^n | 0 \rangle) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum\_{x \in \\{ 0,1\\}^n} |x\rangle $$

But then the above interpretation and the diagram and the text have a few apparent discrepancies between them,

* In the diagram there is no step which looks like $\otimes ^n ( H | 0 \rangle ) $. It seem that all the wires carrying $H|0\rangle$ are straight away sent to the $f$ oracle without this tensoring between them.
* In terms of circuit complexity is this to be thought of as a "single" Hadamard gate or as $n$ Hadamard gates?
* Lastly how does the gate $H$ know about the state $|1\rangle$ ? It only sees the $|0\rangle$ states.
* And the last step is totally unclear: on which state is the $i$th Hadamard gate acting to get $ |s\_i\rangle$? It doesn't seem to be there in the equations below.

Can someone help clarify this?

# Answer
> 3 votes
The $n$-ary Hadamard gate acts on $n$ qubits. The state of the $n$ qubits is a unit norm vector of dimension $2^n$. You can take as basis the vectors $|x\rangle$ for $x \in \\{0,1\\}^n$.

As it happens, the $n$-ary Hadamard gate can be simulated by $n$ unary Hadamard gates acting on the individual qubits, which is what you see on page 6-3. The reason is that the $n$-dimensional Hadamard transform is the tensor product of $n$ one-dimensional Hadamard transforms.

The usual convention in circuit complexity is that gates have bounded fan-in. Otherwise you can compute any function using a large gate!

Consider the case $n=1$: $$ \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix} \\, . $$ This is where $|1\rangle$ comes from.

The entire circuit involves initializing $n$ qubits at the state $|0\rangle$, applying $n$ unary Hadamard gates on the $n$ qubits, applying the black box function $f$, and then applying the Hadamard gates again on the $n$ qubits. The final state of the $i$th qubit turns out to be $|s\_i\rangle$.

---
Tags: complexity-theory, quantum-computing, circuits, hamiltonian-circuit
---


# Question
Title: Official Name for the “First” Programming Language Developed by Turing?
As is widely known, Alan Turing discovered/invented the Turing Machine in his classic 1936 paper. Here he also gave how these machines are specified in terms of their machine states and instructions on how they operate. Is there any official or widely accepted name for this "first" mathematically defined programming language$^\*$ $L$ that consists of a specification of a Turing Machine together with its transition function? Clearly by definition this language is Turing complete and hence can simulate any other algorithmic programming language. For instance here would be how program of $L$:

//Some specification of the machine $M$'s states, initial state, final state, allowable tape symbols, blank tape symbol, etc.

\<0, 0, 1, R, 2\> // If $M$ is in state 0 and sees a 0, then write 1, move right, and enter state 2

\<2, 0, 0, R, 3\> // If $M$ is in state 2, sees a 0, then write 0, move right, and enter state 3

\<2, 1, 0, L, 3\> // etc

\*By first mathematically defined programming language, I'm ignoring for the moment innovations like automated loom printing or natural programming languages like DNA/RNA which are definitely algorithmic, and instead focusing on a particular strand of algorithmic specification that most closely matches what is commonly thought of as a programming language today. There are also other mathematically defined systems that were shown to be Turing equivalent around the same time as Turing, but none of these really caught on in terms of influence as Turing machines and their programming language did.

# Answer
Turing machines are not programmable. Each Turing machine computes only one function. Hence they do not use any programming language. What you see as a language is the description of the machine itself, not of a program in some programming language. Thus the name "*Turing machine*" is the only appropriate terminology.

Now it turns out that there are devices that can emulate Turing machines, such as a computer programmed to do such an emulation. They can use the description of a Turing machine to simulate its computation. This is very similar to a hardware emulator that can mimic the hardware of a computer from a formal description of the circuits.

The abstract theoretical model of such an emulation, as then performed by a Turing machine is called a Universal Turing machine. But universal Turing machines are in no way specialized for that kind of description. It is a much more general concept. The most general name for the input to a universal Turing machine could possibly be "Natural numbers".

However, in his 1936 paper *On Computable Numbers, with an Application to the Entscheidungsproblem*, Turing uses the kind of encoding you have in mind as input to be properly encoded for his *universal computing machine*. He calls it "*standard description*", abbreviated as "*S.D.*".

But it is not the first Turing complete language, even ignoring earlier theoretical work such as done by people like Church and Gödel.

You view of history is missing an earlier invention, which is Charles Babbage's Analytical Engine. Lady Augusta Ada King, Countess of Lovelace, is considered the first programmer in history, though her computer, Babbage's engine, never worked in her lifetime. I do not know that the "assembly language" for the engine received a name. According to Wikipedia it would have been Turing complete.
> 8 votes

---
Tags: turing-machines, programming-languages, history
---


# Question
Title: show that language $L'$ is regular (given $L$ regular)
I am working on the following question:

> $L$ is regular. Show that $L'=\\{x|\exists y,z,\ xyz\in L\wedge |x|=|y|=|z|\\} $ is also regular.

Firstly I show my idea. When you accept it I will try to formalize it. Every automata can has an equivalent automata with exactly one accept state. So let the automata for language $L$ have exactly one accept state $q\_{accept}$.

And now we start in two places - in the normal start state $q\_0$ and $q\_{accept}$. From $q\_{accept}$ we guess symbol. For one symbol we do two steps. From $q\_0$ we go according to symbol - one step. A state is accepting is when two "starts" meet in one state.

Am I on the right track with this idea?

# Answer
> 1 votes
For language $L-$ $M=(Q,\Sigma,\delta, q\_0, F) $
For language $L'-$ $M'=(Q',\Sigma,\delta, q\_{start}, F')$
$Q'=(Q\times Q)\cup q\_{start}$
**Transistions**
$\delta'(q\_{start}, \epsilon)=\\{(q,q\_{acc})|q\_{acc}\in F\\}$
Transition from $(q\_1, q\_2)$ to $(q\_3,q\_4)$
$\delta'((q\_1,q\_2),a\in\Sigma) = \\{(q\_3,q\_4)\\}\text{ iff }\delta(q\_1,a )=q\_3 \text{ and } \delta(\delta(q\_4,b),c)=q\_2 $ for some $b,c\in\Sigma$
**Accepting states** $F'=\\{(q,q)|q\in Q\\}$

# Answer
> 0 votes
start with $D$: a DFA for $L$. Construct an NFA $N$ for $L'$ in the following way:

1. $N$ has the same set of states $Q$ as $D$ with the same starting state.
2. for every $q\in Q$, let $i(q)$ be the length(s) of path(s) from the starting state to $q$ in $D$. Only paths of length at most $Q$ should be considered, then $i(q) \subseteq \\{0,1,\ldots, |Q|-1\\}$.
3. for any $l\in i(q)$: make $q$ accepting in $N$ if

3.1. $q$ is accepting in $D$, or

3.2. there is a path of length $2l$ from $q$ to an accepting state in $D$.

Now **prove** that this is what you need.

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


# Question
Title: Closed form for the recurrence T(n) = T(n-1) + n²
Given the following recurrence:

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

How can I prove it to be $O(n^3)$ with the substitution method? The $O(n^3)$ guess derives from the fact that at every step of the recursion we pay $n^2$ and we have $n$ steps of recursion therefore having: $n \times n^2 = n^3$.

I would even expect this to be $\Theta(n^3)$, but I can't even prove $O(n^3)$.

I tried with the guess:

$$ T(n) \leq n^3 + n^2 \cdot c\_1 + n \cdot c\_2 + c\_3 $$

but that yields:

$$ T(n) \leq n^3 + n^2 \cdot (3 + c\_1) + n \cdot (c\_2 - 2c\_1 -1) + (c\_1 - 1 - c\_2 + c\_3) $$

which yields:

1. $c\_1 = c\_1 + 3$
2. $c\_2 = c\_2 - 2c\_1 - 1$
3. $c\_3 = c\_1 - 1 - c\_2 + c\_3$

But even from the very first ($c\_1 = c\_1 + 3$) we find that no $c\_1$, $c\_2$ or $c\_3$ satisfy the equations.

What did I do wrong?

# Answer
> 3 votes
If $T(n)$ is $O(n^3)$, then with a coefficient to $n^3$:

$$ T(n) \leq n^3 c\_3 + n^2 c\_2 + n c\_1 + c\_0 $$ So, expanding $T(n+1)$: $$\begin{align\*} T(n + 1) &\leq (n + 1)^3 c\_3 + (n + 1)^2 c\_2 + (n + 1) c\_1 + c\_0 \\ T(n) + (n + 1)^2 &\leq n^3 c\_3 + 3n^2 c\_3 + 3n c\_3 + c\_3 + n^2 c\_2 + 2n c\_2 + c\_2 + n c\_1 + c\_1 + c\_0\end{align\*} $$

Leading us to:

$$ T(n) \leq n^3 c\_3 + n^2 (3c\_3 + c\_2 - 1) + n (3c\_3 + 2c\_2 + c\_1 - 2) + c\_3 + c\_2 + c\_1 + c\_0 - 1 $$

Therefore:

1. $ c\_3 = c\_3 $
2. $ c\_2 = 3c\_3 + c\_2 - 1 $
3. $ c\_1 = 3c\_3 + 2c\_2 + c\_1 - 2 $
4. $ c\_0 = c\_3 + c\_2 + c\_1 + c\_0 - 1$

Solving:

$$\begin{align} c\_3 &= 1/3 \\ c\_2 &= 1/2 \\ c\_1 &= 1/6 \end{align} \\ T(n) \leq n^3/3 + n^2/2 + n/6 + c\_0 = \frac{n(n + 1)(2n + 1)}{6} + c\_0 $$

# Answer
> 0 votes
Hint: Expanding the recurrence, we get that $$ T(n) = n^2 + (n-1)^2 + \cdots + 1^2 + T(0). $$ It is known that $$\sum\_{m=1}^n m^2 = \frac{n(n+1)(2n+1)}{6} = \Theta(n^3).$$

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


title: RAID: dedicated and distributed parity

text:
# Question
Title: RAID: dedicated and distributed parity
I understand what parity is (Sort of): A data recovery mechanism where missing data is calculated based on the data that exists. However i have encountered terminology which i can't define or put into perspective of the RAID system.

This terminology is 'dedicated' and 'distributed' Parity. Now i imagine that it is somehow related to the distribution of data among separate disks, but **can anyone give a more detailed definition and explanation of 'Dedicated' and 'Distributed' parity?**

Thanks in advance.

# Answer
The answer to your question can be infered from the wWikipedia page on "Standard RAID levels".

Parity is just one simple case of techniques for error detection, and the name seems to be used here to stand for various techniques of error detection and correction.

The idea of dedicated vs distributed parity, is related to whether the redundancy of information is on a special dedicated disk or whether it is distributed over all disks of the RAID system.

This does not apply to RAID 1 where redundancy is achieved by simple duplication of Data.

In the case of RAID 3 (and apparently RAID 2), data is striped (read "spread" for faster access) over several disk why the redundancy data (parity bytes or bits) is in a separate **dedicated** disk.

In the case of RAID 5, the redundancy is spread over all the disks and mixed into the original base data (**distributed parity**) so that the original data can be retrieved from any set of n-1 disks, when any one of the n disks fails. The content of the failed disk can be recomputed from the n-1 others.

Distributed parity seems to be preferred to dedicated parity, though the wikipedia page is not really clear as to why. My own suspicion is that it allows for more effective error correction than dedicated parity, which keeps the original data and the redundancy (parity) data separate. But this should be checked.
> 4 votes

---
Tags: data-structures
---


# Question
Title: Are combinatory logic terms always larger?
So there is an algorithm to convert lambda calculus terms to combinatory logic using SK combinators. It produces things that *explode* in size. I would like to know more about this explosion in size. I can't seem to think of a better algorithm however. I have heard of functional languages being practically compiled to combinators so it seems that a better algorithm must exist. I looked up David Turner's paper on the topic and he basically just says to apply a few optimizations and that they cause a "considerable improvement".

Does "considerable improvement" mean that the size drops to only a polynomial increase? Is there a known way to convert lambda terms to combinatory logic with only a polynomial (or less?) increase in size? If such an algorithm exists is it practical?

# Answer
not an expert on this but here are two historical papers that seem to be closely relevant to the question and it is possibly a semi active area of research. Turner proposed a set of combinators that can be reduced to SK combinators. this next paper argues that Turner combinators even not reduced to SK combinators leads to exponential blowup (and that presumably the reduction would to SK terms be even larger). but then the 2nd paper says there is an efficient O(n log n) space algorithm based on Turner combinators. (it appears maybe that claims have been made about polynomial efficiency that are regarded as not fully demonstrated/ unproved & are therefore regarded as conjectures...?) anyway apparently real functional evaluation in applied languages typically does not use combinator method so implementors are not too concerned with issues of theoretical efficiency of evaluation of functional expressions by combinator translation.

* What is an Efficient Implementation of the λ-calculus? / Frandsen, Sturtivant (1991) (see p.18)

> Furthermore, we show that implementations based upon Turner Combinators or Hughes Super-combinators have complexities $2^{Ω(ν)}$, i.e. an exponential lower bound. It is open whether any implementation of polynomial complexity, $ν^{O(1)}$, exists, although some implementations have been implicitly claimed to have this complexity.
* Translation of Turner Combinators in O(n log n) space / Noshita (1985)

> A practical method for representing Turner Combinators is presented, which needs only O(n log n) space in the worst case for translating lambda expressions of length n.
> 4 votes

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


# Question
Title: In complexity, why do we find upper bounds, not lower bounds?
In algorithms we use to find Big-O (upper bound), Big-omega (lower bound) and Big-Theta but why we are always interested in finding upper bounds instead of lower bounds?

# Answer
Lower bounds are of great interest and an active topic of research. However, we tend to be interested in lower bounds for *problems* and upper bounds for *algorithms*.

An upper bound for an algorithm is a performance guarantee: the algorithm will not use more than such-and-such an amount of memory or processing steps when run on an input of a particular size. On the other hand, lower bounds for algorithms aren't especially interesting, since most algorithms can be modified to be fast on certain instances and knowing that an algorithm might terminate very quickly isn't often a useful guarantee.

Conversely, any algorithm is an upper bound for the problem it solves. Lower bounds for problems, on the other hand, tell you whether it's worthwhile looking for a faster algorithm than the one you already have. Examples of lower bounds you'll probably be familiar with are completeness results (especially **NP**-completeness) and the fact that comparison-based sorting takes time $\Omega(n\log n)$.
> 11 votes

# Answer
It isn't true that we are are more interested in upper bounds than lower bounds.

Knowing the upper bound allows you to estimate whether your algorithm is feasible for a particular application. This is very important in practice which is why you might see upper bounds more often.

However, lower bounds are of great interest as well. Lower bounds tell you whether you can improve your algorithm: when you find a lower bound equal to the upper bound you know your algorithm is optimal. A lower bound might also tell you that a particular problem isn't feasible to solve and you need to make simplifications.

There are many theories dedicated to finding lower bounds in a variety of situations: the $\Omega(n\log n)$ lower bound for sorting (which is used to give lower bounds for other problems like Convex Hull), $NP$-completeness (and other complexity classes), $3$-SUM, Halting Problem, Fischer-Lynch-Paterson,...
> 5 votes

# Answer
upper bounds are much easier to determine than lower bounds. lower bounds are one of the great open questions in computer science subject to massive active research. so upper bounds can be regarded as "the path of least resistance" or "low hanging fruit". so far we cannot prove even simple lower bounds on many seemingly basic problems. the problem of *(nontrivial/ nonweak/ "strong")* lower bounds is so difficult that many scientists refer to the challenge in terms of disappointment and frustration at lack of progress over many decades despite intense research effort by top experts. eg in the standard textbook by Arora/ Barak lower bounds are referred to as "Complexity Theory's Waterloo".

another emerging pov is that upper and lower bounds are often interrelated by many subtle theorems. in many cases by proving one, one can prove the other. this seems a deep recurring principle that hasnt yet been fully understood/ uncovered & may be a key to future progress/ success in the area. some think that some basic principle/ concept in computer science (regarded by many as still "young") is yet to be uncovered that might unlock progress in the area.

another case study is P vs NP which is essentially/ nearly the foremost problem of the field, oriented around difficulty of lower bounds. the concept of "barriers" is relevant; a significant/ deep principle called "natural proofs" for example is regarded as a very difficult, so far insurmountable barrier to overcome to prove nontrivial lower bounds.
> 1 votes

---
Tags: algorithms, runtime-analysis, lower-bounds
---