title: Measuring time complexity of algorithm

text:
# Question
Title: Measuring time complexity of algorithm
I was going through a past paper question but I don't have any answers to know if I'm working out the problems correctly or not.

I need to find the time complexity for:

```
i) repeat
      n:=n div 2;
   until n=1;

ii) for i:=1 to n do
       begin
          for j:=1 to n do
             begin
                for k:=1 to n do;
             end;
       end;

iii) repeat
        for i:=1 to n do
           begin
              for j:=1 to n do;
           end;
     n:=n div 2
     until n=1

```

In my opinion, the answer for (ii) is $O(\log n)$ and the answer for (ii) is $O(n^3)$ but I'm not sure about my answers. Regarding question (iii) I have no idea how to come up with a solution.

# Answer
For 1, suppose that $n = 2^{m+\delta}$, where $m$ is an integer and $\delta \in \[0,1)$, and compute how many iterations the loop has.

For 2, it's easy to see that it's $\Theta(n^3)$.

For 3, the "inner" loop is $\Theta(n^2)$. Now suppose that $n = 2^{m+\delta}$ and follow the same procedure as in 1. (For starters, you might want to assume that $\delta = 0$.) You will get $\Theta$ of $$ n^2 + \frac{n^2}{4} + \frac{n^2}{16} + \cdots = \Theta(n^2). $$
> 1 votes

# Answer
The standard answer is as given by *Yuval Filmus*.

Note that the questions are slightly flawed and can be interpreted in a different way, especially if you teacher is an adept of tricky/vicious exams.

For example, for (i) the program does not terminate if $n=0$, thus the complexity is unbounded.

On the contrary, since the inner loop of (ii) is empty, any reasonable compiler will produce a compiled code running in constant time.
> 1 votes

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


title: Sort algorithm input probabilities

text:
# Question
Title: Sort algorithm input probabilities
Suppose that there is an algorithm which sorts a sequence of $n$ elements

$$a\_1, a\_2, ..., a\_n$$

Each of the $a\_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers.

Is it true, given that $k \to \infty$, that:

1. The probability that any two of incoming sequence elements are equal, tends to $0$?
2. The probability that the incoming sequence is already sorted, tends to $\frac{1}{n!}$?

Why / why not?

# Answer
Here is why you would expect these properties to hold. Suppose that $a\_1,\ldots,a\_n$ are chosen independently from the uniform distribution on $\[0,1\]$. The event $a\_i = a\_j$ has probability zero, and so with probability $1$ all numbers are distinct. Moreover, given that, all sequence orderings are equally likely, and since there are $n!$ of them, the probability that the sequence is ordered is exactly $1/n!$.

To prove that these claims hold in the limit even when the $a\_i$ are sampled from a finite set requires some calculation, which I leave to you.
> 3 votes

---
Tags: probability-theory, sorting
---


# Question
Title: Complexity of finding a spanning tree that minimizes the maximum interference
Given $n$ nodes in the plane, connect the nodes by a spanning tree. For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning tree. The **interference** of a node $v$ is then deﬁned as the number of such disks that include the node $v$.

The problem I'm interested is to find a spanning tree that **minimizes the maximum interference**.

What is known about the problem in terms of computational complexity? Is it NP-hard? Can it be solved efficiently? What is its inapproximability threshold?

Apparently this problem is still not understood well. I do not know the complexity of the problem (solvable optimally in polynomial time, or NP-complete), and as far as I know it is unknown whether efficient approximation algorithms exist.

# Answer
> 1 votes
This problem already is known, and is NP-Hard, but if you like to know more about the interference related problems I'd offer you to read this book.

The Problem 1, in the Buchin work is as follow:

> **Problem 1** (Locher, von Rickenbach, Wattenhofer\[5\]). Given n nodes in the plane. Connect the nodes by a spanning tree. For each node v we construct a disk centering at v with radius equal to the distance to v's furthest neighbor in the spanning tree. The interference of a node v is then defined as the number of disks that include node v (not counting the disk of v itself ). Find a spanning tree that minimizes the maximum interference.

---
Tags: complexity-theory, graphs, computational-geometry
---


title: Theory of multi-label classification

text:
# Question
Title: Theory of multi-label classification
Multi-label classification is a machine-learning problem where each sample can have zero or more labels from a closed set of possible labels. This task has applications in several fields. For example, in dialog systems, each sentence that the human says may have several intents, and the classifier should detect all of them. For example, the sentence "I want a cake and a drink" contains the two intents "WANTCAKE" and "WANTDRINK".

Theoretically, I expect a classifier to classify multi-label samples, even if the training data contained only single-label samples. For example, consider the following training set (where each word is considered a feature):

* "I want a cake" -\> WANTCAKE
* "I want a drink" -\> WANTDRINK
* "I want a solution" -\> WANTSOLUTION

I would expect a classifier to realize, that the words "I want a" are not relevant for classification, and the words cake/drink/solution are indicative of the classes WANTCAKE/WANTDRINK/WANTSOLUTION respectively, and classify the sentence "I want a cake and a drink" correctly as {WANTCAKE,WANTDRINK}.

This seems trivial to humans. Therefore. I was very surprised to find out, that many state-of-the-art multi-label classifiers fail miserably on this simple task!

For example, consider a multi-label classifier in the "Binary Relevance" method. In this method, there is a single binary classifier for each label. For example, there is a binary classifier for the "WANTCAKE" label, trained with I want a cake" as a positive sample, and the other two sentences as negative samples. When this classifier sees the sentence "I want a cake and a drink and a solution", it sees a *single* feature "cake" that is a positive signal of WANTCAKE, and *two* features, "drink" and "solution", that are negative signals of WANTCAKE, because they appeared in the training set with sentences that did not have the WANTCAKE label. Therefore, this classifier returns 'negative'. The same happens for the other two binary classifiers, and thus the multi-label classifier returns an empty set!

I also tried other approaches to multi-label classification, such as RF-PCT (Random Forest Prediction Clustering Trees), with a slightly larger example (7 labels instead of 3) and got similar results.

I sent this problem to machine learning experts, and they told me that I need more training data. They said that a classifier cannot tag multi-label instances, if the training data contains only single-label instances. In practice, they are right - adding more training data usually improves the accuracy of the classifier.

But I am still bothered with the theoretical issue - how can it be, that there is no state-of-the-art classifier that can solve this trivial, 3-instance problem?

I am looking for a classifier that provably solves such problems. I.e., a classifier for which there is a proof, that if it is given correct single-label samples, it can correctly solve multi-label cases.

Is there such a classifier?

# Answer
You subsequently clarified that you are looking for a way to do multi-label classification in general, and the example in the question about wanting a cake was just an example.

OK, here is one standard way to do multi-label classification. For each candidate label, you build a boolean classifier that outputs true or false: true means that the label applies, false means it doesn't.

In your example, you'd have three classifiers: a "cake classifier" that outputs true if the sentence should be labelled "wants-cake" and false otherwise; a "drink classifier" that outputs true if the sentence should be labelled "wants-drink" and false otherwise; and a "solution classifier" that outputs true if the sentence should be labelled "wants-drink" and false otherwise. You now train each one separately. Given a sentence, you run all three classifiers on it and use that to select which labels should or should not be associated to the sentence. For instance, if the "cake classifier" outputs true, the "drink classifier outputs false, and the "solution classifier" outputs true, then you label the sentence as "wants-cake + wants-solution".

This allows you to use any boolean classifier as your underlying building block. For instance, you can use SVMs, decision trees, random forests, and many other schemes.
> 3 votes

---
Tags: machine-learning, correctness-proof, classification
---


title: Machines in P undecidable?

text:
# Question
Title: Machines in P undecidable?
Given a Turing machine $M$, we say that $L(M) \in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M \in P$ if the machine runs in polynomial time. Note that there can be machines that run needlessly long but still decide a language in $P$. By Rice's theorem, we know that

$\\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) \in P \mbox{ } \\}$ is undecidable. Is it known whether:

$\\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }M \in P \mbox{ } \\}$ is also undecidable?

# Answer
Here is a paraphrase of the proof in the cstheory answer. We reduce from the halting problem. Suppose that we are given a machine $M$, and we are to decide whether $M$ halts on the empty input. We construct a new machine $M'$ accepting a single input $x$, which operates as follows:

1. Let $n = |x|$.
2. $M'$ runs $M$ for $n$ steps.
3. If $M$ halted within $n$ steps then $M'$ runs a dummy loop taking exponential time $\Omega(2^n)$. Otherwise, $M'$ just halts.

Since Turing machines can be simulated with only polynomial overhead, if $M$ doesn't halt then $M'$ runs in polynomial time. If $M$ halts, then $M'$ takes exponential time. Hence $M$ halts iff $M'$ is not polynomial time.

---

More generally, this shows that even if we know that $M$ runs in time at most $f(n)$ for some superpolynomial time-constructible $f$, then we cannot decide whether $M$ runs in polynomial time.
> 7 votes

# Answer
The way your second language is written is not exactly well formed in regards to normal standards. $P$ is a set of languages and not a set of machines. Based on what you said in the rest of your question, I assume that you are trying to make the distinction between machines that run in at most polynomial time and those which happen solve a problem in $P$. Perhaps this would be a better way to write it as:

$A=\left \\{ \left \langle M \right \rangle | (\exists k \forall x) M(x) \text{ halts in } O \left ( |x|^{k}\right ) \text{ time} \right \\}$

$O$ can be replaced with $\Theta$ if you want to exclude weaker machines such as log-time TMs.

Note that: $A\subset\\{\langle M \rangle|L(M) \in P \\}$

As observed by sdcvvc, Rice's theorem does not immediately apply and suffice here since the "non-trivial" property used has to be a property of $L(M)$. A time bound on a machine is not a property of the language, but rather is a property of that machine.

An answer for a predetermined $k$ was discussed the cstheory question question referred to in the comments. The choice of that constant was the key to proving the undecidability. In our language, we include any $k\in\mathbb{N}$ and therefore do not have a maximal $k$ to work with.

I have not had time to spend to sufficiently investigate, but I imagine that it would not be unreasonable to extend their results to any $k\>2$ via straight forward induction.

A recent paper written by David Gajser, who was motivated by that the cstheory post, answers a more generalized version of this question:

Let $HALT\_{T(n)} = \\{ \langle M\rangle|\forall x M(x) \text{ halts in at most } T(n=|x|) \text{ time}\\}$

For single tape Turing Machines: $HALT\_{T(n)}$ is undecidable if $T(n)= \Omega(nlog(n))$

For multiple tape Turing Machines: $HALT\_{T(n)}$ is decidable iff $T(n) \leq k+1$ for some $k\in \mathbb{N}$

He extends these undecidability results to classes with arbitrarily large constants (such as $P$). According to him, the answer to your question is that the language ($A$) is undecidable.
> 2 votes

---
Tags: computability, time-complexity, turing-machines
---


# Question
Title: Probability that a uniformly random sequence is already sorted
Now I tried tackling this question from different perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I have no good ideas).

Let there be $k, n \in\mathbb{Z\_+}$. These are fixed.

Consider a set of $k$ integers $S=\\{0, 1, 2, ... k-1\\}$.

We form a sequence $a\_1, a\_2, ..., a\_n$ by picking numbers from $S$ at random with equal probability $1/k$.

The question is - what is the probability of that sequence to be sorted ascending, i.e. $a\_1 \leq a\_2 \leq ... \leq a\_n$?

Case $k \to \infty$:

This allows us to assume (with probability tending to $1$) that all elements $a\_1, ..., a\_n$ are different. It means that only one ordering out of $n!$ possible is sorted ascending.

And since all orderings are equally likely (not sure why though), the probability of the sequence to be sorted is

$$\frac{1}{n!}.$$

Case k = 2:

Now we have zeroes and ones which come to the resulting sequence with probability $0.5$ each. So the probability of any particular n-sequence is $\frac{1}{2^n}$.

Let us count the number of possible sorted sequences:

$$0, 0, 0, \ldots, 0, 0$$ $$0, 0, 0, \ldots, 0, 1$$ $$0, 0, 0, \ldots, 1, 1$$ $$\ldots$$ $$0, 0, 1, \ldots, 1, 1$$ $$0, 1, 1, \ldots, 1, 1$$ $$1, 1, 1, \ldots, 1, 1$$

These total to $(n+1)$ possible sequences. Now again, any sequence is equally likely, so the probability of the sequence to be sorted is

$$ \frac{n+1}{2^n}. $$

Question:

I have no idea how to generalize it well for arbitrary $k, n$. Maybe we can tackle it together since my mathematical skills aren't really that high.

# Answer
> 2 votes
You can have $k^n$ possibilities of generating a sequence.

Now, there are only $^{n+k-1}C\_{k-1}$ favorable outcomes .

So, the probability that your sequence is already sorted is: $$ \frac{^{n+k-1}C\_{k-1}}{k^n}$$

# Answer
> 0 votes
The key to this problem is to count the number of sequences $a\_1,\dots,a\_n$ of length $n$ that are in sorted order and where every element is from $S$.

Here's a key trick to do that. Given a sequence $a\_1,\dots,a\_n$, we can form a $k$-tuple $(c\_0,\dots,c\_{k-1})$ where $c\_i$ denotes the number of times that $i$ appears in the sequence $a\_1,\dots,a\_n$. This $k$-tuple will always satisfy $c\_0+\dots+c\_{k-1} = n$. Now notice that the each sorted sequence $a\_1,\dots,a\_n$ corresponds to a unique $k$-tuple $(c\_0,\dots,c\_{k-1})$.

In other words, there is a bijective correspondence between the following two sets:

$$A = \\{(a\_1,\dots,a\_n) : 0 \le a\_1 \le \dots \le a\_n \< k\\}$$ $$C = \\{(c\_0,\dots,c\_{k-1}) : c\_0 \ge 0, \dots, c\_{k-1} \ge 0, c\_0+\dots+c\_{k-1} = n\\}.$$

Do you see why this bijective correspondence exists? Given a sequence $a\_1,\dots,a\_n$, we can easily find the corresponding $k$-tuple $(c\_0,\dots,c\_{k-1})$. The reverse is also true: given a $k$-tuple $(c\_0,\dots,c\_{k-1})$, it is easy to recover the corresponding sequence $a\_1,\dots,a\_n$, and that sequence is unique (since the items have to appear in sorted order).

Since these two sets can be put into bijective correspondence, they have the same size: $|A|=|C|$. So, now all we need to do is count the number of such $k$-tuples, i.e., to compute $|C|$. And that's an easier task. It can be done using a standard "stars-and-bars" technique from combinatorics. (If you're not familiar with "stars-and-bars", look it up in a textbook, or ask a separate question about it.) Ultimately, we get the answer

$|A| = |C| = {n+k-1 \choose n}$.

The probability you want to compute is this number, divided by the number of sequences (i.e., divided by $n^k$). So the final answer is: the probability is

$${n+k-1 \choose n}/n^k.$$

---
Tags: combinatorics, probability-theory, sorting
---


title: Queries on Tree

text:
# Question
Title: Queries on Tree
We have a tree with $N$ nodes. $N \le 10^5.$ Each node has a value $V$ associated with it. Now we have $Q$ $(\le 10^5)$ queries. There are two types of queries:

1. Q X Y: in this type of query we have to decrement each node of the subtree rooted at $X$ by value $Y$.
2. C X: in this type of query we have to count the number of nodes in the subtree rooted at $X$ that are $\le 0$.

Here is my approach: I can perform the update query in $O(N)$ along with some sort of lazy propogation. The count query can be thus performed in constant time.

But I am more than sure that there will be a better approach to handle update queries. Possibly a $O(\log N)$ bound for both updates and counts. Is there a way I could map this tree into a segment tree or a bit.

Any approach would be appreciated.

# Answer
You can do a bit better, if you augment the data structure with some additional information at each node. You can make each query Q X Y run in $O(1)$ time (just update a single number at the node $X$). Also, you can make each C X query run in $O(D+n(X))$ time, where $n(X)$ is the number of nodes underneath $X$ (follow the path from the root down to $X$ to accumulate the effect of all previous Q-queries on any ancestor of $X$; then recursively explore all of $X$'s descendants, taking into account the effect of all $Q$-queries on descendants of $X$ as you go).

It feels like it ought to be possible to do better, but I don't immediately have a suggestion.
> 1 votes

---
Tags: data-structures, trees
---


# Question
Title: Set combination data structure (And storage complexity)
I have already posted this question on Stackoverflow, but I'm starting to think that this is the right place.

I have a problem where I am required to associate unique combinations from a set (unique subsets) to a given value. e.g.: Let `S={a, b, c, d}`, the required data structure should perform the following:

**Key -\> value**

```
{a,b} -> value1
{a,c} -> value2
{c,d} -> value3

```
* Property 1: The length of the set in the key is fixed (In this example it's fixed to 2).
* Property 2: The data structure does not hold all possible subsets of S.

**Question 1**: What is the storage complexity of a simple Map holding these values? O(N!)? (given that |S| = N and it's not fixed)

**Question 2**: Is there any efficient data structure that could store such elements? (The most important efficiency would be required in storage complexity)

# Answer
Question 1: The storage complexity of a map for holding these values is $\Theta(m)$, where $m$ is the number of entries in the map, assuming we don't count the space to store the sets themselves, and assuming we store them in a hash table (or similar data structure).

This doesn't include the space to store the sets in the keys, as those presumably already exist. If you want to include that space as well in your estimate of the space complexity, then we need at most $\Theta(m)$ space for the map, plus $\Theta(mk)$ space to hold the sets (assuming each set contains $k$ elements), for a total of $\Theta(mk)$ space. I am assuming that each element of $S$ can be stored in a single word ($\Theta(1)$ space), e.g., that $n \le 2^{64}$. If $n$ is huge, so that an element of $S$ cannot be stored in a single word, a better estimate of the total space usage is $\Theta(mk \lg n)$, since it takes $\Theta(\lg n)$ bits to store a single element of $S$, each subset of $k$ elements takes $\Theta(k \lg n)$ bits, and there are $m$ entries in the map, each of which requires $\Theta(k \lg n)$ bits to store it.

The number of unique subsets of size $k$, out of a universe of $n$ items, is ${n \choose k}$. Therefore, if you know that the keys are subsets of size $k$, you know that $m \le {n \choose k}$. But you mentioned in the question that the number of entries in the map is less than all possible subsets of size $k$, so this isn't helpful.

Question 2: Yes, a hash table would be an efficient data structure to store these elements. There's a straightforward way to define a hash function on subsets of $S$, so you can use that to build a hash table. A hash table achieves the space complexities listed above.
> 2 votes

---
Tags: data-structures, space-complexity, sets
---


# Question
Title: Number of 5-cycles and 6-cycles in a simple graph
Is there any formula for computing the number of 5-cycles and 6-cycles in a simple undirected graph?

# Answer
> 2 votes
I'll suppose that you looking for $k$ *-cycle*, and in the following $f(k)$ is a computable function which belongs to $O(k!)$.

One simple algorithm is considering all possible k+1 vertices, to check whether they are part of a some cycle or not, this algorithm is $O(|V|^{k+1})$ (If we consider corresponding edge, running time can be improved on sparse graphs). This idea can be improved by using matrix multiplication algorithm, we know that in the level $m$ of (adjacency) matrix multiplication we have the number of paths of length $m$ starting from each node. Then we can calculate $M^k$, this can be done in $O(f(k)\cdot M^{\omega+1})$ (where $M^\omega$ is the lower bound for running time of matrix multiplication for adjacency matrix $M$ of input graph). But converting this to a cycle is a little bit tricky task and you can find one algorithm here, running time of exponential part still is independent of size of graph and is depend to $f$, but sure in the cycle case $f$ is bigger ($k!$ in the first paper). There are faster but more complicated algorithms like what described in this, all of them are consequence of these simple ideas.

P.S: I hope to be clear that the bound that I mentioned is not tight, e.g in both Monien and Alan's papers, upper bounds are better than general thing that I wrote.

# Answer
> 0 votes
Yes. Let $M$ denote the adjacency matrix of the graph. You can compute $M' = M^5$ (the 5th power of $M$) efficiently. Now $M'\_{i,i}$ counts the number of paths of length 5 starting at $i$ and ending at $i$. Therefore, $\sum\_i M'\_{i,i}$ counts the number of 5-cycles, if you don't restrict these to be simple cycles.

If you want the number of simple cycles, you'll need to subtract off something to account for non-simple paths. This is trickier, but can still be done using inclusion-exclusion and a case analysis.

---
Tags: graphs
---


# Question
Title: Time Complexity for Creating a Graph from a File
Assume that I have a file that consists of pairs of numbers separated by a space. These numbers are the labels for vertices in my graph. For example:

```
0 5
0 7
2 3
4 5
1 5
.
.
.

```

I want to create a graph (adjacency list) by reading this file line-by-line. For each line, I will create an edge between the two vertices. Of course, if the vertex doesn't exist yet, then I will add it before creating the edge.

I read here of an algorithm that builds a graph with a time complexity of $O(|V| + |E|)$ where $V$ = set of vertices and $E$ = set of edges. That makes sense to me. However my algorithm doesn't insert the vertices in a loop first and then insert all of the edges in another loop second. My algorithm just adds the vertices as it's looping through the edges.

My question is if my algorithm is $O(|E|)$? It seems like that can't be right, but I read here that when calculating the time complexity you don't take into account if statements. That's exactly what my vertex creation would be -- an if statement that checks if the node exists in the middle of my looping through all the edges.

# Answer
> 3 votes
You forget that $O(|E|) \subset O(|E|+|V|)$ and $O(|E|+|V|) \subset O(|E|)$. Though It's actually $O(|E|\ln|V|)$, because checking if a vertex has been inserted is hardly $O(1)$.

---
Tags: algorithms, graphs, algorithm-analysis, runtime-analysis
---


title: Are there more easy SAT Problems?

text:
# Question
Title: Are there more easy SAT Problems?
1. Apart from $2SAT$, what versions of SAT problem is complete for the class NL?
2. Is there dynamic programming algorithm to solve the $2SAT$ Problem?

# Answer
(1) is hard to answer unless you clarify what you mean by "versions of SAT problem." If we limit ourselves to the classes listed in Schaefer's "The Complexity of Satisfiability Problems", the only nontrivial class known to be in NL is 2-SAT.

As for question (2), 2-SAT is amenable to dynamic programming, as is SAT in general. During the DPLL process each partial assignment produces a new subformula: the previous formula with false literals removed and all satisfied clauses deleted. As subformulas are determined to be unsatisfiable, they can be memoized in a canonical form. If a known unsatisfiable subformula is encountered again during the DPLL search, a table lookup can identify it and the search can immediately backtrack. For SAT instances derived from problems with many symmetries (and therefore many identical subformulas) the time savings can be substantial.
> 7 votes

---
Tags: complexity-theory, satisfiability
---


title: Fundamental Boolean Functions

text:
# Question
Title: Fundamental Boolean Functions
I can define any boolean function (I think) using **and** and **not**, or using **or** and **not** (plus a constant 0 or 1). And I can define **or** in terms of **xor**. And then there are **nor** and **nand**. So I am wondering:

1. Why are we traditionally taught boolean logic using **and**, **or** and **not**?
2. Is there a "simplest" set of boolean functions that can be used to define all the rest? Or are there "families" of functions that are equivalent in some way?
3. Do we always need 0, 1 and 2-argument functions (eg 0 or 1 constants, **not**, and **and**) to define a family? Or are there any boolean functions with more than 2 arguments that are fundamental (can appear in an answer to 2)? Or well-known? Or common? If not, what's so special about 0, 1 and 2 arguments?
4. Is there some underlying mathematical theory (perhaps based on symmetry?) that makes these kinds of questions easier to answer? For example, how do you rigorously derive all answers to questions 2 or 3?

(I know that a partial answer to 2 (equivalent families) is "yes" because I remember De Morgan's theorem from college, but that's about as far as I can get).

# Answer
> 3 votes
Your main observation is correct - in order to be able to express all Boolean functions, we need not stick to a certain set of connectives. All we need is a *complete* set of connectives, which is defined by just this property. There are infinitely many such sets of connectives. One such example is given by NOR (or NAND) and the constant $0$ (or $1$). You can probably do with just one ternary connective, but I'll let you figure that out.

Why are we taught AND, OR and NOT? Because these are familiar and useful. It is also common to define propositional logic using the connectives IMPLIES and NOT. It's just a matter of convenience. It is also a matter of convenience that all usual connectives are nullary, unary and binary - already ternary connectives are more awkward to write, functional notation being necessary.

In general, given a set of connectives, you can define the set of all Boolean functions definable from them. Then you can define the concept of equivalent sets of connectives. For example, XOR and NOT is equivalent to XNOR, and $0$ and NOT is equivalent to $1$ and NOT. You can easily prove that two sets $A,B$ of connectives are equivalent if each connective in $A$ can be expressed using connectives in $B$ and vice versa. You can even define an order relation expressing that one set of connectives is at least as expressive as another set of connectives.

One relevant mathematical area is *universal algebra*. For an application to computer science, you can have a look at Schaefer's theorem and its modern descendants, which form a very active research area. Another connection to computer science is Reckhow's theorem that shows that every formula written using one complete set of connectives can be rewritten using any other set of connectives *with only polynomial blowup*, and furthermore proofs in any complete propositional proof system can be converted to any other (with a different set of connectives), again with only polynomial blowup.

---
Tags: logic
---


title: Where are back edges in a DFS tree?

text:
# Question
Title: Where are back edges in a DFS tree?
As I understand it when doing a DFS run when every new node is discovered and edge is added to the DFS tree from the parent of the new node to the new node. If that's the case how are back edges are created?

# Answer
> 4 votes
The terms forward, back and cross edges classify edges in the original graph with respect to the depth-first search, so they don't appear in the DFS tree itself. Different DFS runs may yield different classifications. They are useful in some algorithmic contexts.

You can read more on Wikipedia.

---
Tags: terminology, graphs
---


# Question
Title: How do I prove that Context Free languages have more memory than FSM
This is very much clear to me that an FSM has limited memory (sufficient to store present state). How do I prove that (intutively or otherwise) that a CFL has more memory than a DFA or NFA (thus making a CFL more powerful than FA) ?

# Answer
> 1 votes
There's a small mistake in your question.

The FSM (DFA or NFA) are **machines** that accept regular languages.

the CFL is also a **language**.

They are accepted by a machine called PDA (PushDown Automata) which you can think of as a generalization of the a DFA/NFA.

A PDA is like a NFA but in addition, it also has a stack. So it can accept (context free) languages like $L = \\{0^p1^p | p \geq 0\\}$

Its fairly easy to show that the PDA is more powerful than DFA.. (see it accepts $L$ that the DFA cannot)

We will show something stronger, i.e. formally define the construction of the PDA that will show that any language accepted by some *DFA* is also accepted by some *PDA* .

a PDA is 6 tuple $(Q, \Sigma, \Gamma, \delta, q\_0, F )$, where,

* $Q$ is the set of states
* $\Sigma$ is the input alphabet,
* $\Gamma$ is the stack alphabet,
* $\delta$ is the transition func. $\delta:(Q \times \Sigma\_\epsilon \times \Gamma\_\epsilon) \rightarrow \mathcal{P}(Q\times \Gamma\_\epsilon)$ ,
* $q\_0 \in Q$,
* $F \subseteq Q$

now observe that a DFA/NFA is just the same thing where $\Gamma$ is always 'empty'.

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


title: Pattern bonding problem

text:
# Question
Title: Pattern bonding problem
> Let $\Sigma = {1,2,3,4}$ . We say that symbol $\sigma $ bonds with symbol $\tau$ if $\sigma = \tau$ of $\sigma = \tau +1$ for even $\sigma$ and $\sigma = \tau -1$ for odd $\sigma$ . In other words , 1 and 2 bond , and 3 and 4 bond (in addition to every number bonding with itself ) .
>
> The Pattern bonding problem is defined as follows:
>
> INPUT : Text $ T = t\_{1} , ..., t\_{n}$ and pattern $ P = p\_{1} , ..., p\_{m}$ over alphabet $\Sigma $ .
>
> OUTPUT : All locations $i$ in the text that bond with the pattern , i.e , where $t\_{i+j-1}$ bonds with $p\_{j}$ $j=1,...,m$ .

Can someone supply an algorithm for the pattern bonding problem (the faster the better complexity can) ? , I thought about "Less then matching" .

**Edit: (Answer)**

Map $ (1,2) \rightarrow \alpha , (3,4)\rightarrow \beta$ then the text and the pattern is on $\Sigma = {\alpha , \beta}$ and then we know to solve it in $O(n)$ using witness or KMP .

# Answer
Hint: map $1,2$ to $a$ and $3,4$ to $b$.
> 1 votes

---
Tags: algorithms, pattern-recognition
---


# Question
Title: Why is compression ratio using bzip2 for a sequence of "a"s so jumpy?
```
library(ggplot2)

compress <- function(str) {
  length(memCompress(paste(rep("a", str), collapse=""), type="bzip2"))
  / nchar(paste(rep("a", str), collapse=""))
}

cr <- data.frame(i = 1:10000, r = sapply(1:10000, compress))

ggplot(cr[cr$i>=5000 & cr$i<=10000,], aes(x=i, y=r)) + geom_line()

```

The compression ratio starts out at 37 for "a" and hits the break-even at 39 "a"s (compression ratio = 1). The chart starts out pretty smooth and gets edgy suddenly for 98 "a"s and from there at increasingly small intervals.

The local lows and smooth sections seem also quite erratic and random. Can somebody explain to me why bzip2 shows this behaviour in this example?

# Answer
> 14 votes
Suppose a simple compression algorithm that represents a run of `a` by storing $(\text{header}, \mathtt{\text{"a"}}, n)$, i.e. some fixed header, the string `a`, and the number of repetitions $n$. This is a run-length encoding. Then the length of the compressed text would be close to $a + \lg n$ bits for some constants $a$. The corresponding compression ratio would be $\dfrac{a + \lg(n)}{n}$. This is roughly the shape of the curve as seen from a distance, if you neglect the local ups and downs. Asymptotically, the compression ratio is $\Theta(\lg(n)^p/n)$ with $p \ge 1$ (I haven't worked it out but I suspect there are other factors at play which make the size of the output superlinear in the length of the input string).

$\lg n$ bits aren't an integer number of bits, let alone bytes: the size of $n$ has to be at a minimum rounded up to an integer number of bytes. This explains a first threshold effect: for this simple compression algorithm, you would observe that the length of the output is $a$ when $n$ is sufficiently small, then $a+1$, then $a+2$, etc. The compression ratio therefore isn't a smooth curve but jumps from $\dfrac{a}{n}$ to $\dfrac{a+1}{n}$, then $\dfrac{a+2}{n}$, etc. This effect is barely visible in the realignment after jumps (but there are other effects at play which make the jumps different).

Since the compression ratio is too close to the inverse ratio of the length for visual observation, here is the data for small length in my implementation (this may be dependent on the version of the bzip2 library, as there are multiple ways to compress some inputs). The first column indicates the number of `a`'s, the second column is the length of the compressed output.

```
1–3       37
4–99      39
100–115   37
116–258   39
259–354   45
355       43
356       40
357–370   41
371–498   43
499–513   41
514–609   45
610       43
611       41
613–625   42
626–753   44
754–764   42
765       40
766–767   41
768       42
769–864   45
…

```

Bzip2 is far more complex that a simple run-length encoding. It works in a series of steps, and the first step is a run-length encoding step, but with a fixed size limit. The first step works as follows: if a byte is repeated at least 4 times, then replace the bytes after the 4th by a byte indicating the repeat count of the erased bytes. For example, `aaaaaaa` is transformed to `aaaa\d{3}` (where `\d{003}` is the character with byte value 3); `aaaa` is transformed to `aaaa\d{0}`, and so on. Since there are only 256 distinct byte values, only sequences where the byte is repeated up to 259 times can be encoded this way; if there are more, a fresh sequence starts. Furthermore, the reference implementation stops at a repeat count of 252, which encodes a string of 256 bytes.

This step explains the first threshold and the threshold at 258: $\mathtt{a}^n$ compresses to 37 bytes for $1 \le n \le 3$ and to up to 39 bytes for $4 \le n \le 258$. The introduction of the repeat count results in 2 more bytes in the output of the subsequent steps, and that extra byte is able to represent all repeat counts up to 258. After 258 bytes, there is a second RLE string. There is a third one at 514 bytes, a fourth at 769 bytes, and so on. Extra RLE strings after the second one don't cost much if at all because that sequence `aaaa\d{252}` (assuming that `\d{252}` is the repeat count, I haven't checked) is itself repeated and therefore compressed by subsequent steps.

Why are the thresholds at 258, 516, 769, (none at 1024), 1279 rather than exact multiples of 256? I suspect it's because the Burrows-Wheeler transform followed by a move-to-front can transform something like `aaaa\374aa` (output of step 1 for $n=258$) by moving the `a`'s together so that they can be encoded together, but I haven't checked.

The reduction in length at $n=100$ is interesting. For the input $\mathtt{a}^{101}$, the first RLE step produces `aaaa\d{97}` — but the byte value of `a` is 97, so this is `aaaaa` which has better potential for compression by subsequent steps. I suspect that the shrinking effect not only for $n=101$ but also for surrounding values is due to the delta encoding step which makes it easier to store bytes with nearby values. If you change `a` to `A` (65), you'll notice that the shorter output happens for $68 \le n \le 83$.

My analysis of this example is far from exhaustive. To understand other effects, you would have to study the other steps of the transformation: I mostly stopped after step 1 of 9. I hope this gives you an idea of why compression ratios get a little choppy and don't vary monotonically. If you really want to figure out every detail, I recommend taking an existing implementation and observing it with a debugger.

For the most part, such minute variations aren't the main focus when designing a compression algorithm: in many common scenarios, such as general-purpose or media compression algorithms, a difference of a few bytes is irrelevant. Compression tries to squeeze out every bit at the local level, and tries to chain transformations in such a way as to gain often while rarely losing and then not by much. There are nonetheless situations such as special-purpose communication protocols designed for low-bandwidth communication where every bit matters. Another situation where exact output length matters is when the compressed text is encrypted: when an adversary can submit part of the text to be compressed and encrypted, variations on the length of the ciphertext can reveal the part of the compressed-and-encrypted text to the adversary; this was recently publicized in the CRIME exploit on HTTPS.

---
Tags: data-compression
---


# Question
Title: Why do you have to worry about cache coherence if you are using shared memory?
Wikipedia says that shared memory comes with lots of costs associated with cache coherence costs. But I thought the whole idea of shared memory is that all the CPUs access the same memory? So if one CPU changes that memory then other CPUs would access the same value? It would seem like this would require FEWER cache coherence costs? Is the idea that if one CPU changes its local cache before it writes to shared memory then other CPUs have to be notified?

# Answer
> 7 votes
If two different processors share one memory, each having individual cache, they can end up having two different values in the same address.

Imagine each of two processors has private caches L1 and L2. The cache L3 is shared between both processors. Assume the processor A reads data from address X in L3 to L1 and the processor B reads the same data from the same address (address X in L3) to it's private cache L1. Then, if the processor A modifies the value and does a write-back, the processor B can't figure it out without the support of coherence protocol and would still have an old value in it's own cache.

Basically, you are right. The cache coherence protocol is a mechanism to notify processors about shared memory modification caused by other processors.

The main advantage of the shared memory architecture for a programmer is that there is no need to explicitly describe communication and interaction between processors (like you would do using MPI, for instance). The coherence and consistency of the memory is fully the responsibility of the hardware.

# Answer
> 4 votes
You are correct: when one processor changes a memory location that is locally cached, then all other processors that are sharing that memory location need to be notified.

So why have local caches? If you didn't then *every* memory access would be as slow. You want most memory accesses to be fast, so each processor should have its own fast cache. This works extremely well for data that is used by only a single thread of computation (for example: each thread has a private stack, and no other thread will read or write that data.) Likewise it works extremely well for read-mostly data. For example, data structures that get initialized once and then read by many threads. The code of the program is also read only, so does well being cached.

For the few memory locations that really are shared, you need to keep the caches coherent. This involves detecting that a memory location is shared, and then notifying any of the other caches that are currently caching that memory location. You have to pay the cost of the book-keeping to detect which memory locations are shared even if you never actually use the shared memory.

---
Tags: computer-architecture, distributed-systems, parallel-computing
---


# Question
Title: Deriving the Sobel equations from derivatives
Many sites give the Sobel operators as the convolution mask for smoothing an image. However, I haven't found a single site that describes how you can derive the operators from partial first derivatives. If anyone can explain the derivation, I would highly appreciate it.

# Answer
The Sobel operator is an approximation of the derivative in the X dimension followed by a simple smoothing operator in the Y dimension. (Or derivative in the Y dimension and then smoothed in X).

Consider a one-dimensional signal $f(t)$. The derivative of $f(t)$, $d f(t) / dt$ can be written as:

$$ \lim\_{\Delta \rightarrow 0} \frac{f(t+\Delta) - f(t-\Delta)}{2\Delta} $$

This is called the *centered difference formula*.

But with a discrete signal the smallest $\Delta$ you have at your disposal is the distance between samples, so you use that as an approximation of the limit.

We can see just how bad (or good) an approximation it is by looking at what it does to a complex exponential signal $e^{\omega i t}$. The true derivative would give $\omega i e^{\omega i t}$. The approximation gives $$ \frac{e^{\omega i (t+1)} - e^{\omega i (t-1)}}{2} = \frac{e^{\omega i}e^{\omega i t}-e^{-\omega i}e^{\omega i t}}{2} = \frac{e^{\omega i} - e^{-\omega i}}{2}e^{\omega i t} = i \sin(\omega)e^{\omega i t} $$ so extremely accurate with low frequencies ($\omega$ near 0), but increasingly inaccurate as $\omega$ approaches the Nyquist frequency ($\omega \rightarrow \pi$). This is about the best you are going to do with three samples. It also has the advantage of over-attenuating the high frequency response rather than over-amplifying.

Now let's do some smoothing in the Y dimension. We want something that only uses 3 points, and about the best you are going to get is $\frac{1}{4}f(t-\Delta) + \frac{1}{2}f(t) + \frac{1}{4}f(t+\Delta)$. This filter has frequency response: $$ \frac{1}{4}e^{\omega i (t - \Delta)} + \frac{1}{2}e^{\omega i t} + \frac{1}{4}e^{\omega i (t + \Delta)} = \frac{1}{2}(1 + \frac{e^{-\omega i \Delta}+e^{\omega i \Delta}}{2})e^{\omega i t} = \frac{1}{2}(1 + \cos \omega)e^{\omega i t} $$ which smoothly transitions from passing low frequencies to completely attenuating high frequencies.

So convolve the derivative approximation in the X dimension with the smoother in the Y dimension and you get the kernel: $$ \frac{1}{8} \left\[ \begin{array}{ccc} 1 & 0 & -1 \\ 2 & 0 & -2 \\ 1 & 0 & -1 \end{array} \right\]. $$
> 4 votes

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


# Question
Title: Decide if L is regular or not and argue it. Trying to use Pumping Lemma
Part (a): Let $L = \\{x \in \\{0,1\\}^\* \mid \\#0(x) \neq 4\times\\#1(x)\\}$, where $\\#0(x)$ means the number of 0 in string $x$ and $\\#1(x)$ means the number of 1 in string $x$.

So I want to use the pumping lemma. But I'm having a hard time choosing a string so that I can show that it is not regular.

I've been thinking about how I could use something like the string, s, = $0^{3p}1^p$. But I do not see how you use that fact (I would like to show that xyyz would equal $0^{4p}1^p$). This route seems unfruitful. So any help would be nice.

Part (b): Let $L = \\{x \in \\{0,1\\}^\* \mid \exists k \in \mathbb{N}, \\#0(x) + \\#1(x) = 2k\\}$.

Again stuck on this problem. My original approach was to leverage the fact that the parity is the same on the 0s and 1s (if one is even, then so does the other and vice versa. Same for odd parity.)

Again, this does not seem to be working.

# Answer
> 4 votes
For part (a), if you are intent on using the pumping lemma, then you can either use Subhayan's suggestion and first complement the language, or just do it directly like so. Let $p$ be the constant promised by the pumping lemma, and consider the following word: $$ w = 1^p 0^{4(p!+p)} \in L. $$ According to the pumping lemma, you can write this as $w = xyz$ with $|xy| \leq p$ and $|y| \geq 1$, so that $y = 1^k$ for some $1 \leq k \leq p$. Furthermore, the pumping lemma guarantees that $xy^iz \in L$ for every $i \geq 0$. Now take $i = (p!/k)+1$. Then $$xy^iz = 1^{p-k}1^{k(p!/k)+1} 0^{4(p!+p)} = 1^{p!+p} 0^{4(p!+p)} \notin L.$$

Another option is to use the Myhill-Nerode criterion; it then makes no difference whether or not you complement $L$. For some reason this criterion isn't usually taught in introductory classes. The idea is to consider some DFA accepting $L$. If two words $x,y$ end up at the same state of the DFA, then for every word $z$, $xz \in L$ iff $yz \in L$. In particular, if two words $x,y$ don't satisfy this condition (we say that they *conflict*), then they must end up at different states of the DFA. Hence we find an infinite number of pairwise conflicting words, $L$ isn't regular.

Such an infinite sequence of pairwise conflicting words is $x\_n = 1^n$. Indeed, given $n \neq m$, consider $z\_n = 0^{4n}$. We have $x\_n z\_n \notin L$ but $x\_m z\_n \in L$, and so $x\_n$ and $x\_m$ conflict.

For part (b), $L$ is just the language of all words of even length. Hence we can improve on Subhayan's answer by designing a DFA for $L$ using only two states.

# Answer
> 5 votes
**(a)**: Recall that regular languages are closed under complement, i.e if $L$ is regular, so is $L'$. ($F\_{L'} = Q\_L- F\_L$)

Assume that $L$ is regular. This follows: if $L = \\{x \in \\{0,1\\}^\* \mid |x|\_0 \neq 4.|x|\_1 \\}$ is regular, then so is $L' = \\{x \in \\{0,1\\}^\* \mid |x|\_0 = 4.|x|\_1\\} $

Now you should show that $L'$ is not regular. And that gives you a contradiction.

**(b)** You can construct the following DFA for this.

# Answer
> 2 votes
For part (a), instead of doing everything and go back to pumping lemma, you can try to use a famous nonregular language, which is $K=\\{x: \\#0(x)=\\#1(x)\\}$. You probably saw this language already, and a proof of $K$ being nonregular is classic and easy to find.

Now you want to deduce from that that $L$ is nonregular, which is the same as showing that its complement $L'$ is nonregular. For this you can use the fact that regular languages are closed under inverse images of morphism.

We look at the morphism $\varphi:\\{0,1\\}^\*\to\\{0,1\\}^\*$ defined by $\varphi(0)=0000$ and $\varphi(1)=1$. Remark that $K=\varphi^{-1}(L')$. If $L'$ was regular, then $K$ would also be, which we know is not the case. Therefore $L'$ is nonregular, and its complement $L$ too.

For part (b), as Yuval Filmus said you are just accepting words of even length, so a 2-states automaton is a witness that your language is regular.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Runtime of various versions of binary search
I was given the following code and was told to find the best and worst case running times in big theta notation. (Below is in python)

```
def find(a, target):
    x = 0
    y = len(a)
    while x < y:
        m = (x+y)/2
        if a[m] < target:
            x = m+1
        elif a[m] > target:
            y = m
        else:
            return m
    return -1

```

I know that the running time of this code in the worst case is $O(\lg n)$. But the question I was given if the fifth line was changed from $m = \frac{x+y}{2}$ to $m=\frac{2x+y}{3}$, would the running time change?

My intuition is that the running time gets a little larger as it is no longer cutting the list in half like binary search should do which is less efficient, but I am not sure how to calculate what the asymptotic runtime would be at this point.

# Answer
Instead of cutting the interval in half, it's cut in to a piece 1/3 of the length and it's cut in to a piece 2/3 of the length. If you are lucky enough that the item you're searching for is in the left half, then you've done a better job than regular binary search. If you're unlucky and it ends up in the right half, then you do slightly worse than regular binary search.

What happens if the algorithm has "bad luck" twice in a row. The interval gets cut to 2/3rds and then to 2/3rds again, meaning it gets cut to 4/9ths which means it is now slightly shorter than 1/2. This means that in the worst case (bad luck every time) this version of binary search will take only 2x more steps than regular binary search.

On the other hand, if the algorithm is lucky the interval is cut to 1/3rd. If we look at regular binary search, after two steps the algorithm has been cut in half two times, meaning it has been cut to 1/4th - slightly shorter than a 1/3rd. So in the best case, the algorithm takes at least half as many steps as regular binary search.
> 2 votes

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


# Question
Title: Linear time labeling algorithm for a tree?
I have an undirected tree whose vertices I want to label. The leaf nodes should be labeled one. Then, assume the leaves were removed. In the tree that remains, the leaves should be labeled two. This process continues in the obvious way until all vertices have a label. The reason I do this is I want to store the vertices in a queue, and go through them "leaves first". Is there an easy way to do this $O(n+m)$ time?

I can solve the problem by doing a BFS on every step. But in the worst case, on every step I go through every vertex, remove exactly two leaves and enqueue them. I believe this takes quadratic time.

Another idea was to first find all the leaves, and then do a BFS from every leaf. This doesn't give me the desired solution. For example, consider a kind of "crown graph" as in the figure below. The desired solution is shown, but launching a BFS from each leaf would result in only two labels used.

Ideally, the linear time algorithm would also be easy to explain and implement.

# Answer
> 8 votes
## Unrooted Trees

You can use a priority queue to solve this in $O(E+V\log V)$:

* Put all vertices in a priority queue, with their priority being their degree.
* While the queue is non-empty:
    + Remove a vertex $v$ of minimal priority, which must be $1$ (or $0$ at the very end).
    + Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all *original* neighbors of $v$.
    + Subtract $1$ from the priority of the unique remaining neighbor of $u$ (if any).

In fact, we don't really need a priority queue, and this algorithm can be implemented using a simple queue in time $O(E+V)$:

* Initialize an array of length $V$ with the degrees of all vertices.
* Initialize another array of length $V$ with "alive".
* Go once through the first array, and push all vertices of degree $1$ to a queue.
* While the queue is non-empty:
    + Pop a vertex $v$.
    + Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
    + Mark $v$ as "dead".
    + If $v$ has some "alive" neighbor $u$, subtract $1$ from the degree of $u$.
    + If the new degree of $u$ is $1$, push $u$ to the queue.

## Rooted Trees

Use DFS instead. Here is a sketch of the algorithm.

* Given a node $v$, if $v$ is a leaf, set $d(v) = 1$.
* If $v$ is not a leaf, run the algorithm on all its children, and then let $d(v) = 1 + \max d(u)$, where $u$ goes over the set of all children.

You run this algorithm on the root.

# Answer
> 2 votes
A straightforward answer is as follows:

* Turn this into a directed graph, where we have an edge $(u,v)$ from each node $u$ to its parent $v$. Note that you get a dag (directed acyclic graph).
* Topologically sort the graph.
* Scan the vertices, in sorted order. Label each vertex with one more than the largest of the labels on its predecessors. Since we're scanning in topological order, all of the predecessors of $v$ will already have received a label before we try to label $v$.

Each of these steps can be done in $O(n+m)$ time, so the total running time is $O(n+m)$. I mention this alternative approach only in case you find it conceptually easier to understand than Yuval's answer.

---
Tags: algorithms, trees
---


title: Which problems are hard for P^NP?

text:
# Question
Title: Which problems are hard for P^NP?
Quantified Boolean formulae are the prime examples of problems that are hard for the polynomial hierarchy, i.e., for the $\Pi$ and $\Sigma$ versions of it. However, there is also the $\Delta$ version, defined as $\Delta\_{i+1}^{\rm P} := {\rm P}^{\Sigma\_i^{\rm P}}$. In particular, $\Delta\_2^{\rm P} = {\rm P}^{\rm NP}$.

What are typical hard problems for this part of the hierarchy?

I failed to search the Web for this; especially, you cannot use Google to find much about "P^NP".

# Answer
> 6 votes
Krentel gave two problems complete for $\Delta\_2^P$ (see Theorem 3.4):

> *Input:* Boolean formula $\phi(x\_1,\dots,x\_n)$.
> *Question:* Is $x\_n = 1$ in the lexicographically largest satisfying assignment of $\phi$?
>
> *Input:* Weighted graph $G$, integer $k$.
> *Question:* Is the length of the shortest TSP tour in $G$ divisible by $k$?

Krentel also states that the only previous example of a $\Delta\_2^P$-complete problem up to 1988 was Uniquely Optimal TSP, given by Papadimitriou in 1984.

As sdcvvc pointed out, see also the MO discussion at https://mathoverflow.net/questions/2218/characterize-pnp for a nice discussion by Ryan Williams of a machine model that captures $\Delta\_2^P$.

---
Tags: complexity-theory, oracle-machines
---


# Question
Title: Explanation of Heavy light decomposition
Can anyone explain heavy light decomposition of trees or give a resource to read it from? I have already gone through http://ipsc.ksp.sk/2009/real/solutions/l.html which is the best i could find but still could not understand its working completely.

# Answer
> 3 votes
I am taking this from http://wcipeg.com/wiki/Heavy-light\_decomposition

Essentially the decomposition tells you which, if any, subtrees at a node N take up more than half the weight of the tree rooted at N. Such a subtree gets an edge coloured with the word "Heavy" the rest get coloured "Light". Note that there can be at most one heavy subtree at any given node.

Here is an implementation in Haskell.

```
module HLDecom where

{- |
  This data type has data in the leaves and nodes
  that collect a list of subtrees each of which is
  paired with b-type data.  The b should be thought
  of as information on the edge connecting the node
  to the subtree.
-}
data Tree a b = Leaf a | Node [(b,Tree a b)]

data Color = Heavy | Light

size :: Tree a b -> Integer
size (Leaf x) = 1
size (Node ns) = 1 + sum (map (\(a,b) -> size b) ns)

{- |
  The Heavy-Light decomposition of a tree is a
  colouring of the tree's edges with
  either Heavy or Light.

  If the size of a subtree at a node is more
  than half the size of the tree at the node,
  then the edge connecting the node to that
  subtree is heavy otherwise it is light.

  It should be obvious that at any given node,
  there can only be one such heavy subtree
  (there can only be one subtree that
  has > 1/2 the weight), and further we can find
  this subtree by finding the maximum size subtree.
  If this size is more than half the size of
  the whole tree, then it is colored Heavy.

  The implementation below could certainly be
  improved for efficiency; however, the focus
  on being direct and clear.
-}
--hlDecomp :: Tree a b -> Tree a Color
hlDecomp (Leaf x) = (Leaf x)
hlDecomp (Node ns) =
  let
    sizeOfNode = size (Node ns)
    heavyLight = map (\(b,tree) ->
       if size tree >
          sizeOfNode `div` 2
          then (Heavy,tree)
          else (Light,tree)) ns
  in
    Node heavyLight

```

---
Tags: data-structures, trees
---


# Question
Title: Tight asymptotic bound for recursive algorithm
I have this algorithm where:

$$ T(n) = \begin{cases} 1 & \text{if}\\; n \le 1 \\ T(n/2) + 1 & \text{otherwise} \\ \end{cases} $$

So, evaluating for $T(0), T(1), T(2), T(3), \ldots, T(n)$, I'm getting values like: $$ 1, 1, 2, 2, 3, 3, \ldots, n, n $$

I assume this is twice the sum of $1$ to $n$, that would be the same as $n (n+1)$ or $n^2+2$.

Is my assumption ok?

# Answer
> 3 votes
Suppose that $n = 2^k$. Then $$ T(n) = T(2^k) = T(2^{k-1}) + 1 = T(2^{k-2}) + 2 = \cdots = T(2^0) + k = k + 1. $$ So $T(n) = \log\_2 n + 1$ in that case. In the general case you would get something similar, $T(n) = \lfloor \log\_2 n + 1\rfloor$.

---
Tags: algorithm-analysis, asymptotics, recursion
---


# Question
Title: Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ time
Suppose you are given an input set $S$ of $n$ numbers, and a black box that if given any sequence of real numbers and an integer $k$ instantly and correctly answers whether there is a subset of input sequence whose sum is exactly $k$. I want to show how to use the black box $O(n)$ times to find a subset of S that adds up to $k$.

This is what I've done: the first time we enter our set $S$. If it returns yes we can continue, otherwise it isn't possible to form the sequence which sums up to $k$. The next step is to test our set without the first element. If the black box returns yes we can delete it from our set otherwise we know that it is needed. We do this for each element and our $S$ shrinks to a set which sums up to $k$. Can I use induction to prove this?

# Answer
> 4 votes
Let $S = \\{a\_1,\ldots,a\_n\\}$, and denote $S^t$ the set after deciding the fate of $a\_t$. If you want to use induction, here is your induction hypothesis:

1. If there is a subset of $S$ that sums to $k$, then there is a subset of $S^t$ that sums to $k$.
2. Every subset of $S$ that sums to $k$ includes $S^t \cap \\{a\_1,\ldots,a\_t\\}$.

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


# Question
Title: What is a regular expression that matches all strings over the alphabet except a particular substring?
I've come across this problem in my studies, and I've abstracted it to the more general case here.

Given a finite alphabet, what is a regular expression that matches all strings over the alphabet, except one particular finite substring?

As an example:

Given $\Sigma = \\{a, b, c\\}$

What is a regular expression that matches all of $\Sigma$ except the substring $ ba$?

What I really want is simply $\Sigma^\* - ba$.

# Answer
Just draw the minimal complete DFA accepting your string, change the final states to get the complement and now convert this new DFA to a regular expression.

In your case, you will get $\mathcal{A} = (Q, A, \cdot, 1, F)$ with $Q = \\{0, 1, 2, 3\\}$, $A = \\{a, b, c \\}$, $F = \\{3\\}$ and $1 \cdot b = 2$, $2 \cdot a = 3$ and $q \cdot x = 0$ for all other transitions. Thus the automaton for the complement is $\mathcal{A}' = (Q, A, \cdot, 1, F')$ with $F' = \\{0, 1, 2\\}$.

Converting $\mathcal{A}'$ to a regular expression gives $$ 1 + b + (c + bc + baA)A^\* $$
> 4 votes

# Answer
One way of finding such a regular expression is $$ \epsilon+a+b+c+aa+ab+ac+bb+bc+ca+cb+cc+(a+b+c)(a+b+c)(a+b+c)(a+b+c)^\*. $$ There might be more succinct solutions, but this always works (for all finite languages).
> 1 votes

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Name for concept: each pair of sets is either nested or disjoint
Does this property have a name?

> Given a collection of sets $\mathcal{P}$, for all pairs $A, B\in\mathcal{P}$, either $A\cap B=\emptyset$ or $A\subseteq B$ or $B\subseteq A$.

This concept could equally apply to monoids, groups, partial orders or other mathematical structures, with some adjustments to the definitions. For instance, for monoids and groups we would replace $A\cap B=\emptyset$ by $A\cap B=\\{\epsilon\\}$, where $\epsilon$ is the unit of the monoid/group.

# Answer
I think that's called a *laminar family*.
> 8 votes

---
Tags: terminology, sets
---


# Question
Title: Learning juntas, with membership queries
The junta problem is the following: we have a boolean function $f:\\{0,1\\}^n \to \\{0,1\\}$ that actually happens to depend on only $k$ of its input variables. Given the value of $f(x)$ for many random values of $x$, we want to identify the $k$ input variables that $f$ actually depends upon. In other words, secretly $f(x\_1,\dots,x\_n) = g(x\_{i\_1},\dots,x\_{i\_k})$ for some indices $i\_1,\dots,i\_k$; given many pairs $(x,f(x))$ where each $x$ is random, we want to find the $i\_1,\dots,i\_k$.

I am interested in a variant of the junta problem, where we are allowed membership queries. In particular, at any point, we can choose a value $x$ and receive the value of $f(x)$. The goal remains the same: We want to learn the junta, i.e., learn the indices $i\_1,\dots,i\_k$.

How many membership queries are needed, and what is the running time to learn the junta?

There is a simple, straightforward algorithm that uses something like $O(n)$ membership queries (first find $x,y$ such that $f(x)\ne f(y)$, then move from $x$ to $y$ by changing one bit of the input at a time, to identify $x',y'$ such that $f(x')\ne f(y')$ and $x',y'$ differ in a single bit position). But can it be done with many fewer membership queries? For instance, can we learn the junta with, say, $O(\lg n)$ membership queries?

# Answer
Information theory shows that you need at least $\log\_2 \binom{n}{k}$ queries. When $k$ is small, this is $\Theta(k\log n)$, which is probably enough. Consider for example the case $k=1$, and suppose for simplicity that $n$ is a power of $2$. By feeding the inputs $x\_i = \text{bit $r$ of $i$}$ to $f$ you can recover the index $i\_1$. (To determine whether the function is $i\_1$ or $\lnot i\_1$, feed the all-zero vector to $f$.)
> 5 votes

# Answer
Lerning juntas from membership queries can be done in $O\_k(\log(n))$ queries indeed. According to Yuval's answer, this give a correct dependence of $n$. However, the dependence on $k$ is not tight (it will be something like $2^k$).

The answer to this question is actually written in the Learning juntas by Mossel, O'Donnell and R. Servedio, but I'll spell it out anyway.

Note first that it is enough to find in each step one influential coordinate, since we can then recurse to the $(k-1)$-junta problem, by fixing the bits in the coordinates found so far and considering the function restricted to different possible fixes of these coordinates.

In order to find one influential coordinate in $O(\log(n))$ queries let us simply sample our function $f$ on random inputs, until found $x,y \in \\{0,1\\}^n$ such that $f(x) \neq f(y)$. (If we find no such inputs, we may guess that the function is constant.) Now given such $x$ and $y$, let us pick at random a point $z$ between $x$ and $y$ at distance $0.5dist(x,y)$ from each of them, and read $f(z)$. If $f(x) \neq f(z)$ then we continue with the pair $x,z$, and otherwise we continue with the pair $y,z$. The process continues for at most $\log(n)$ iterations, until we find two neighboring vertices on which $f$ gives different values. This gives us one influential coordinate.
> 5 votes

---
Tags: algorithms, machine-learning, learning-theory
---


# Question
Title: $\mathsf{co\text{-}NP}$ and Cook reductions
Can someone help me understand the steps in this argument? There is a decision problem that is in $\mathsf{co\text{-}NP}$ (under standard Karp reductions) and is $\mathsf{NP}$-hard with respect to Cook reductions. Does this imply that if it is in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{co\text{-}NP}$ and if so, why?

# Answer
> 8 votes
Every NP-complete program $A$ is co-NP hard under Cook reductions: given a problem $B$ in co-NP, its complement $\overline{B}$ is in NP, so there is a polytime function $f$ such that $f(x) \in A$ iff $x \in \overline{B}$. Therefore the following is a Cook reduction from $B$ to $A$: given $x$, ask whether $f(x) \in A$, and return the opposite.

This shows that Cook reductions are not sensitive to the difference between NP and co-NP. Karp reductions are, and that's why we use them in the usual definition of NP-complete. (If we were only interested in P vs. NP, Cook reductions would be fine.)

---
Tags: complexity-theory, reductions, np-hard
---


title: Congestion Game with Varying Price

text:
# Question
Title: Congestion Game with Varying Price
I molded my problem as the following game (it is a congestion game with varying price):

$N$ players share resources $E$,

$S\_i$ is the strategy space of player $i$ which is in $2^E$ (where $2^E$ is the power set of resources).

$P\_e^i$ is the price of resource $e \in E$ considering player $i$. **The price of resource $e$ is different for different users.**

The goal of each player is to select a strategy $S\_i$ which minimize its price $\sum\_{e\in S\_i}P\_e^i$ .

My questions are:

1. Does this game have any Nash Equilibrium (NE)? If so under which conditions?
2. If it has any NE, what is a sample algorithm for achieving it?

I searched literature but could not find any appropriate information! Any solution is appreciated!

# Answer
> 1 votes
I think the answer is yes, there is a Nash equilibrium, and it can be attained just by letting each person in turn change his selection to the best possible alternative.

For more information, read this paper:

Weighted congestion games with separable preferences

by: Igal Milchtaich

http://www.citeulike.org/user/erelsegal-halevi/article/12205199

---
Tags: algorithms, optimization, game-theory
---


title: finger search on a red black tree

text:
# Question
Title: finger search on a red black tree
I'm having trouble finding materials on what 'finger search' is, in the context of a red black tree.

Even Wikipedia has a very short page about that, could you refer me or explain what kind of search is that.

# Answer
> 2 votes
One of the basic operations supported by trees is searching for elements. A balanced binary tree (for example, a red-black tree) supports search in $O(\log n)$ time, where $n$ is the number of elements. In some scenarios, the elements we are searching for are close to one another, and *finger search* allows taking advantage of that. After having just searched the $j$th largest element, searching the $i$th largest elements only takes time $O(\log |i-j|)$. So scanning through all the elements in order would only take $O(n)$ time rather than $O(n\log n)$.

Finger search can be implemented using several different data structures. In particular, it can be implemented using balanced binary trees such as red-black trees.

For more on finger search, check out a research proposal by Maverick Woo and a book chapter by Gerth Stølting Brodal.

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


# Question
Title: Approximate percentage of the memory's total operating time for refreshes while refreshing DRAM
A DRAM that must be given a refresh cycle 64 times per ms.Each refresh requires 150ns,a memory cycle requires 250 ns. What is the approximate percentage of the memory's total operating time must be given to refreshes?

Can someone explain how to find the solution?

# Answer
I don't quite understand the different between "refresh" and "memory cycle" (whatever that means), but here is the sort of calculation you have to do. There is a refresh cycle $64$ times every millisecond (so every $(1/64)\text{ms}$), which apparently takes $150\text{ns}$. So refreshes take $150\text{ns}/(1/64)\text{ms}$ of the time, which is $(150\times 64)/10^6 = 0.0096$ \[since $1\text{ms}=10^6\text{ns}$\], or about one percent \[multiplying by $100$\].

You can also consult Wikipedia here.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Confusion regarding several time complexities including the logarithm
I am new to Advanced Algorithms and I have studied various samples on Google and StackExchange. What I understand is:

1. We use $O(\log n)$ complexity when there is division of any $n$ number on each recursion (especially in divide and conquer).
2. I know that for binary search, we have time complexity $O(n \log n)$, I understood $\log n$ is because each time it halves the full $n$ size number list in a recursive manner until it finds the required element. But why is it multiplied with $n$ even we just traverse half of the $n$ size element for each execution so why we multiply $\log n$ with $n$?
3. Please give me any example explaining the complexity $O(n^2 \log n)$. I hope this will help me in understanding much better the above two questions.

# Answer
1. You are correct in thinking binary search is $O(\log n)$, it shouldn't be multiplied by $n$.
2. Popular (comparison-based) sorting algorithms are $O(n \log n)$.
3. 3SUM (i.e. find 3 elements in an array that sums to zero) using binary search is $O(n^2 \log n)$.

The pseudo-code:

```
For each element
  For each other element
    Do a binary search for the 3rd element that will result in a zero sum.

```

Although the problem can be solved in $O(n^2)$ in a different way, this should still serve as a decent example.

**Explanation of merge-sort complexity:**

Merge-sort, for example, splits the array into 2 parts repeatedly (similar to binary search), but there are some differences:

* Binary search throws away the other half, where merge-sort processes both
* Binary search consists of a simple $O(1)$ check at each point, where-as merge-sort needs to do an $O(n)$ merge. This should already make the $O(\log n)$ vs $O(n \log n)$ make sense.

For a quick check, ask how many work, on average, is done for each element.
Note that a single merge is linear time, thus $O(1)$ per element.
You recurse down $O(\log n)$ times and, at each step there's a merge, so each element is involved in $O(\log n)$ merges.
And there are $O(n)$ elements.
Thus we have a time complexity of $O(n \log n)$.

There is also the more mathematical analysis: (source)

> Let $T(n)$ the time used to sort n elements. As we can perform separation and merging in linear time, it takes $cn$ time to perform these two steps, for some constant $c$. So,
> $T(n) = 2T(n/2) + cn$.

From here you work your way down to $T(1)$, and the remaining terms gives you your $O(n \log n)$ running time. Or use the master theorem.

If both of these are unclear, it should be easy enough to find another resource explaining the complexity of merge-sort.
> 4 votes

---
Tags: algorithms, asymptotics, runtime-analysis, landau-notation
---


# Question
Title: Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?
In the last section of chapter 3 (page 54) in *Probability and Computing: Randomized Algorithms and Probabilistic Analysis* by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the median of a set $S$ of distinct elements in $O(n)$ time. As a substep the algorithm requires sorting a multiset $R$ of values sampled from $S$, where $|R| = \lceil n^{3/4} \rceil$. I'm sure this is a fairly simple, and straight forward question compared to the others on this site, but how is sorting a multiset of this size bounded by $O(n)$?

I assume the algorithm is using a typical comparison-based, deterministic sorting algorithm that runs in $O(n\log$ $n)$. So, If I have the expression $O(n^{3/4}\log(n^{3/4}))$, isn't this just equivalent to $O(\frac{3}{4}n^{3/4}\log(n)) = O(n^{3/4}\log(n))$? How does the reduction down to $O(n)$ proceed?

# Answer
> 6 votes
Your analysis is correct, and you can conclude that $O(n^{3/4} \log(n)) = O(n)$ immediately. By L'hopital's rule $\log(n) = o(n^c)$ for any fixed $c \> 0$, and in particular for $c = 1/4$. Therefore $O(n^{3/4} \log(n)) = O(n^{3/4} n^{1/4}) = O(n)$.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, search-algorithms, randomized-algorithms
---


title: Time Complexity of Algorithm

text:
# Question
Title: Time Complexity of Algorithm
I need help with finding out the time complexity of the following algorithm:

```
procedure VeryOdd(integer n):
for i from 1 to n do
  if i is odd then
    for j from i to n do
      x = x + 1
    for j from 1 to i do
      y = y + 1

```

This is my attempt:

$$ Loop1 = \Theta(n)$$ $$ Loop2 = \Theta(n)$$ $$ Loop2 = O(n)$$

And we also know that loop2 and loop3 will get executed every second time of the execution of the outer loop. So we know that:

$$T(n) = \Theta(n) * 1/2(\Theta(n) + O(n)) = \Theta(n^2)$$

Now to the thing I'm not so sure about, nameley, is Loop3 really $$O(N)$$ and if yes, then is $$\Theta(n) + O(n) = \Theta(n)$$

Thanks in advance

# Answer
$$ Loop 1 = \theta(n) $$ Since both loop in total will run n times so, $$ Loop 2 + Loop3 = \theta(n) $$ $$ T(n) = \theta(n) * 1/2 ( \theta(n)) = \theta(n^2) $$
> 1 votes

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


# Question
Title: Which of the common sorting algorithms can be parallelized?
I want to know that whether which of the following algorithm can be parallelized?

Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Quick Sort, Merge Sort, Radix Sort.

Those which can't be, please explain me briefly that how? Or please try to tell me in simple words that what is parallelism in sorting algorithms.

# Answer
Check this link. Parallelism can be achieved by using pipeline of processing units or using multiple processor link.

For comparison based sorting lets take an example of quick sort , in quick sort after we find the pivot then we can process two parts in parallel.

```
quicksort(A)
if |A| = 1 then return A
i := rand int(|A|)
p := A[i]
in parallel do
 L := quicksort({a : a ∈ A | a < p})
 E := {a : a ∈ A | a = p}
 G := quicksort({a : a ∈ A | a > p})
return L ++ E ++ G

```

Another example we can take is of Radix sort which does not directly compare keys to determine ordering.The basic radix sort algorithm (whether serial or parallel) examines the keys to be sorted one “digit” position at a time, starting with the least significant digit in each key.For implementation in parallel see this tutorial Parallel In-Place Radix Sort
> 0 votes

---
Tags: algorithms, sorting, parallel-computing
---


# Question
Title: Does this language have a context-free grammar?
Here is a question that I encountered in one of my exams:

> Find one context-free grammar that recognizes the language: $\qquad L = \\{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\\} $

Can you find such a grammar? I even doubt its existence, but I have not been able to prove that.

# Answer
No, this language is not context-free. This is because the language requires to iterate $b^mc^m$ with the same number $m$ each time. Even if we restrict to $n=0$ and $p=2$ then the resulting language $\\{b^mc^mb^mc^m \mid m\ge 0\\}$ is easily recognized as non-context-free. Formally this restriction is obtained by intersecting with a regular language, a known closure property of context-free languages. To prove a language formally non-context-free one might use the pumping lemma discussed elsewhere in this forum.

Perhaps that is a mistake in its specification. If for each iteration the number $m$ can be different, the resulting language is context-free. That language would be $L\_1 = \\{ a^n w d^n \mid n\ge 0, w\in \\{\\; b^mc^m \mid m\ge 0\\}^\* \\;\\}$. As an example, $bbbcccbc$ is an element of $L\_1$, but not of $L$.

*How* to find a grammar (for $L\_1$)? Observe the nesting structure. Context-free grammars are good in nesting, and iteration. For instance the part $\\{\\; b^mc^m \mid m\ge 0\\}^\*$ is generated by $T\to AT, T\to A, A\to bAc, A\to\lambda$, starting with $T$. Now add a matching number of $a$'s and $d$'s on both sides by nesting: $S \to aSd, S\to T$.
> 3 votes

# Answer
As @Hendrik mentioned, if m is not to be remembered ie it can be different than I think following grammar will work .. $$ A \rightarrow a A D | a B D | \lambda $$

$$ B \rightarrow b B c | b B c P|P $$ $$ P\rightarrow bPc|bPcB|\lambda $$ $$ D \rightarrow d $$
> 0 votes

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


# Question
Title: If someone was designing a computer language, why would they require static members to be defined outside the class?
I am new to C++ and just learned that "The declaration of a static data member in the member list of a class is not a definition. You must define the static member outside of the class declaration, in namespace scope."

I am curious about why this is. Are there particular design advantages to making the rules of the language in this way? I am not asking: "tell me what Stroustrup was thinking when he made C++" -- which I know is an unfair question on these forums. I am asking: if someone sat down to make a computer language, why might they require that static data members are defined outside of the class. What are the advantages of this? What are the disadvantages? What kinds of costs would this incur? Why would someone put this quirk in their language? (Also I'm curious, but I know it's not totally appropriate to ask here: how did this quirk end up in C++).

# Answer
Such language design solution makes sense, because class body is basically a declaration, which normally has to be in the header file. All definitions has to appear in cpp files, where class instances are actually used. If you allow static members to be defined inside class body, then you mix declarations with definitions. So I would require this to make separation between declarations and definitions clear.

In terms of this separation it is fine to initialise static const class members inside class body. Basically, you are defining some constant and it could be equivalently done with some `#define` directive.

It doesn't seem that this restriction is due to the limits of the language or a compiler. Java doesn't have this restriction and allows definitions inside the body of a class for any static data member (not const only).

Update: C++11 relaxes the restriction and supports non-static member in-class initialisation. Static members still have to be defined outside.
> 3 votes

# Answer
In C++ it is generally the case that you can access the variables that are declared inside whatever level of curly braces you are currently in. Curly braces and scope at least roughly correspond.

But a data definition includes an initializer, which is code. *The code that initializes the static data member is not allowed to access any of the non-static data members of the class.* (Because those are members of objects, and there is a one-to-many relationship between the static member and the objects and in any case the static member is initialized before any of the objects of the class are created.)

So example:

```
static int a=0;

class foo {
  int b;
  static int c = b+1;  // what does this mean????
};

int foo::c = a+2;  // This makes sense.  We are initializing using only other statics.

```

Let's look at another similar situation (from C) where the language designers made a different decision that has historically caused a lot of trouble. In C `static` usually means "has the lifetime from the time the compilation unit is loaded until the compilation unit is unloaded." Unfortunately there is one case where it means something different:

```
static int y = 0;
int foo(int x) {
  static int bar = x+y; // bar gets initialized when???  And what value does it get?
  bar += x;
  return bar;
}

```

When does `bar` get initialized? *At the time of the first call to `foo`!* So its initial value depends on `x` (which kind of makes sense) and whatever the value of `y` is at the moment (which is confusing at best.) This also has performance and correctness implications because of multithreading: `foo`'s initializer needs to be protected with a guard that guarantees the initializer gets executed only once, and the guard needs to be atomic with respect to multithreading! So the above code is equivalent to the following:

```
static int y = 0;
static int foo_initializer_has_been_called=false;
int foo(int x) {
  static int bar;
  if (foo_initializer_has_been_called) {     // actually this needs to be an atomic
    bar = x+y;                               // test-and-test-and-set to handle
    foo_initializer_has_been_called = true;  // multithreading
  }
  bar += x;
  return bar;
}

```

*Arguably* the designers of C had no choice because there was no other place to write the initializer for a variable with static lifetime but local scope. The designers of C++ couldn't fix the mistake that the C designers made, but they could avoid making it a second time, because they have the `class_name::member_name` syntax to use outside the class declaration. So a static declared inside a class has exactly the same lifetime as a static declared outside the class, and the initializer is written at the global scope to make it clear that the lifetime and scope of accessible variables during initialization is the same as it would be if the static was declared outside the class.
> 3 votes

---
Tags: programming-languages
---


# Question
Title: Find all intervals that overlap with a given interval
Note: I moved this question from stackoverflow.com

I have an algorithmic problem where I would like to see if it can be solved in better than $O(n)$:

I have given a table $T$ of $n$ elements where each element is a tuple $(s\_i, e\_i)$ with $s\_i, e\_i \in \mathbb{N}$ and $s\_i \< e\_i$, i.e. each tuple is some kind of an interval. I have to find all intervals that overlap with a given interval $\[t\_0, t\_1\]$ with $t\_0, t\_1 \in \mathbb{N}$ and $t\_0 \< t\_1$. Further, I have available two sorted lists $S$ and $E$, containing the $s$ values, or $e$ values respectively, together with the index $i$ pointing to the respective entry in $T$. The lists are sorted by $s$ values, or $e$ values respectively. (Let's assume both, $s$ and $e$ values, are unique.)

**Problem:**

We have to find each interval/tuple $(s\_i, e\_i) \in T$ where $s\_i \leqslant t\_1$ and $e\_i \geqslant t\_0$.

**My thoughts so far:**

We can exclude some elements by either applying one of the interval boundaries, i.e. searching $t\_1$ in $S$ or $t\_0$ in $E$. This gives us a list $L$ of remaining elements: $$ L \leftarrow \\{e \in E \mid e \geqslant t\_0\\} \text{ or } L \leftarrow \\{s \in S \mid s \leqslant t\_1\\} $$ However, there is no lower bound on the number of elements in $L$, no matter which search we perform. Further, we have to check every element in $L$ if $s \leqslant t\_1$, or $e \geqslant t\_0$ respectively depending on which search we performed before.

The complexity for this solution is $O(n)$.

However, let's say that $k$ is the maximum number of elements overlapping with interval $\[t\_0, t\_1\]$. If we assume $k \ll n$, then the complexity is $O(n/2)$ since we can exclude at least $n/2$ elements by choosing the appropriate search for $L$. Still $O(n/2)$ is in $O(n)$.

Can you think of a better approach to solve this problem?

**For record:**

The complexity for finding all intervals overlapping with a certain given interval using an interval tree is $O(\log n + k)$ where $k$ is the number of overlapping intervals. However, in my practical case I am using a MySQL database which provides index trees for each value, i.e. $s$ and $e$, separately. This way I can not find overlapping intervals in less than $O(n)$. I would need to create an interval tree which is a search tree that stores both interval boundaries, i.e. $s$ and $e$, in a single data structure. The complexity for constructing the interval tree is $O(n \log n)$. \[http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22intervals/\]

# Answer
I believe that interval trees offer a solution to your problem. Basically, you store your intervals in the interval tree data structure; then, to find all intervals that overlap with $\[t\_0,t\_1\]$, you do a query into the interval tree. This should solve your problem and run faster than $O(n)$ time.
> 7 votes

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


# Question
Title: Trouble understanding how to pick constants to prove big theta
So I'm reading Introductions to Algorithms and sometimes I wish it would be a little bit more friendly with how it explains topics. One of these topics is proving big-theta.

I understand that the definition of $\Theta$ is as follows:

> $\Theta(g(n)) = f(n)$ if there exists positive constants $c\_1$, $c\_2$, and $n\_0$ such that $0 \le c\_1 g(n) \le f(n) \le c\_2 g(n)$ for all $n \ge n\_0$.

In other words, for $f(n)$ and $g(n)$, $f(n)$ can be bounded by $c\_2 g(n)$ from above and bounded below by $c\_1 g(n)$.

So the example in the book goes:

> Show that $\frac{1}{2} n^2 - 3 n = \Theta(n^2)$.

From the definition of big theta:

$$ c\_1 n^2 \le \frac{1}{2} n^2 - 3 n \le c\_2 n^2$$

CLRS begins by dividing by the largest order term of $n$ which is $n^2$ to get

$$ c\_1 \le \frac{1}{2} - \frac{3}{n} \le c\_2 $$

From here we split the problem into two parts, the right-hand inequality and the left-hand inequality.

On the right hand side: CLRS chooses $c\_2 \ge \frac{1}{2}$ because for $n \gt 1$, $\frac{1}{2} - \frac{3}{n}$ can never be less than $\frac{1}{2}$ since $\frac{3}{n}$ goes to $0$ as $n$ goes to infinity. (I'm assuming they choose $n \gt 1$ here because if $n=0$ then we would be dividing by $0$.)

*Now this is where I start to get lost.*

On the left hand side: CLRS chooses $c\_1 = \frac{1}{14}$ (not sure why) and $n \ge 7$. I'm not sure what the significance of these choices is. At $n \le 6$, $\frac{1}{2}-\frac{3}{n}$ becomes negative. But why $\frac{1}{14}$ for $c\_2$? I'm just not sure how they arrived at solving the left hand side and the book doesn't really explain it well for me.

# Answer
> 5 votes
For $n \leq 6$, $$ 1/2 - 3/n \le0, $$ so if you are taking integer value of $n$, put $n = 7$ as it gives $1/14$. This is how he arrived in the conclusion i.e., for $n \geq 7$, $$ 1/2 - 3/n \ge1/14, $$ because $n$ is in the denominator it will only decrease the value of -ve term, so overall value will increase with $n$, which is the constant $c\_1$.

---
Tags: complexity-theory, asymptotics
---


title: Prove or disprove whether L is regular

text:
# Question
Title: Prove or disprove whether L is regular
Let $\Sigma = \\{0,1\\}$. For every word $w \in \Sigma^\*$, let $|w|\_0$ and $|w|\_1$ denote the count of 0's and 1's, respectively, in $w$. Let $L$ be the language $$L = \\{ w \in \Sigma^\* \mid |w|\_0 \gt |w|\_1 + 2 \text{ or } |w|\_1 \gt |w|\_0 + 2\\}$$ Prove or disprove whether $L$ is regular.

# Answer
> 3 votes
Recall that regular languages are closed under complementation. That is, if $L$ is regular, than so is $\overline{L}=\Sigma^\*\setminus L$.

Thus, if you manage to prove that $\overline{L}$ is not regular, then $L$ is not regular as well.

Observe that $$\begin{align} \overline{L} &= \\{w\in \\{0,1\\}^\*: |w|\_0\le |w|\_1+2 \wedge |w|\_1\le |w|\_0+2\\} \\ &=\\{w:|w|\_1-2\le |w|\_0\le |w|\_1+2\\} \\ \end{align} $$

Assume by way of contradiction that $\overline{L}$ is regular, then by the pumping lemma, there exists a pumping constant $p$. Consider the word $0^p1^p\in \overline{L}$, then (by standard pumping-lemma arguments) there exists some $i\le p$ such that $0^{p+ki}1^p\in \overline{L}$ for every natural $k$. Choose $k=5$ (any number greater than 2 will work), then $p+5i\>p+2$, and therefore $0^{p+ki}1^p\notin \overline{L}$, which is a contradiction.

# Answer
> 0 votes
@Shaull's solution is perfect.. here's a slightly different version of it...

try to see, that $L$ = $L\_1 \cup L\_2$

where

$L\_1 = \\{ w \in \\{0,1\\}^\* \mid |w|\_0 \gt |w|\_1 + 2\\}$

$L\_2 = \\{ w \in \\{0,1\\}^\* \mid |w|\_1 \gt |w|\_0 + 2\\}$

now we will go on to show that $L\_1$ is not regular using the pumping lemma.

> The pumping lemma states that if some $A$ is a regular language, $\exists$ number $p$ (think of it as the number of states of a DFA that recognizes $A$) such that if $s \in A, |s| \geq p$ then $s$ can be divided into $x,y,z$ such that $s=xyz$ and
>
> 1. $\forall i\geq0, xy^iz \in A$
> 2. $|y| \> 0$
> 3. $|xy| \leq p$

Now, we do a proof by contradiction, and assume that $L\_1$ is regular.

Now again, see that $L\_1 \supset L\_{1a} \cdot L\_{1b} $

where

$L\_{1a} = \\{ w = 0^n1^n \mid n\geq 0\\}$ (it has the same number of 0s and 1s)

$L\_{1b} = \\{ w \in \\{1\\}^n \mid n\geq 2\\}$

i.e. a regular language is closed under union.

Now we will just show that $L\_{1a}$ is not regular.

Proof by contradiction: Assume $L\_{1a}$ is regular, then there is a DFA, $M$ that accepts $L\_{1a}$. Let $p$ be the num of states.

Let $s$ be some word in $L\_{1a}$

Let $s = 0^{p+1}1^{p+1}$

$s= xyz$

$|xy| \leq p $ (from defn pumping lemma)

$|xy|$ has just $0$s

$y$ has atleast one $0$ (from defn pumping lemma)

but $xy^2z$ has more $0$s than $1$s $\rightarrow s = xy^2z \notin L\_{1a} $

Contradiction!!! this shows $L\_{1a}$ is not regular

Then this gives a contradiction that $L\_1$ is regular, and finally that shows that $L$ is also not regular.

---
Tags: formal-languages, regular-languages
---


title: High maths for game theory

text:
# Question
Title: High maths for game theory
I am a starting Ph.D. student in computer science, and I am trying to understand some classic game-theory papers, such as those by Nash, Kalai and Smorodinsky. But I find it hard to understand the mathematical parts. It seems that these papers were written by mathematicians, for mathematicians.

Can you recommend a book that explains the mathematical preliminaries of game theory, to people without extensive mathematical background?

# Answer
\[The reviews are based on *my* first hand experience with the materials.\]

Quick Read:

* Essentials of game theory (Leyton-Brown, Shoham) - This is a ~100 page book, which will give a strong intuition (and more) on Game theory, this mostly covers the basics, the math here is also pretty lightweight, and this is very much readable (even by a college junior). After this book the reader should be able to (atleast) sit through an advance GT Talk.
* An Algorithmic Game Theory Primer (Tim Roughgarden) - A really nice survey by Tim Roughgarden. It talks about various disciplines like Mechanism Design, Complexity of Equilibria, among many other things.This should motivate the reader to identify the other areas of research.

Books:

* Algorithmic Game Theory (Nisan et al) - This is perhaps the most popular book among Computational Game Theorists.. It covers a *lot* of ground, and the content is very rich. (IMHO) This is one of the books, that every researcher should read before diving into the subject.
* Lectures in Game Theory for Computer Scientists (eds. Apt and Grädel) This is yet another book that contains essays from several authors and is rich in application content. As the name suggests, this is for a great resource for computer scientists who want to *use* game theory for their research.

Also, if you are done with these, want more advanced material take a look at the LNCS Proceedings of SAGT.
> 7 votes

---
Tags: reference-request, game-theory, mathematical-analysis
---


title: Prove that X/Y/Z is context-free

text:
# Question
Title: Prove that X/Y/Z is context-free
Given languages X, Y and Z, each with alphabet, define X/Y/Z as:

```
     X/Y/Z = { w ∈ Σ* | ∃u ∈ Y and ∃v ∈ Z; such that wuv ∈ X }.

```

Prove that if X is context-free, and Y and Z are regular, then X/Y/Z is context-free.

# Answer
> 2 votes
Setting $T = YZ$, your language is the set $L$ of all $w \in \Sigma^\*$ for which there is a $t \in T$ such that $wt \in X$. In other words, $L$ is the right quotient of $X$ by $T$. Now, if $X$ is regular, so is $L$ (in all cases) and if $X$ is context-free and $Y$ and $Z$ are regular, then $T$ is regular and $L$ is context-free. One way to prove this latter statement is to consider the rational transduction $\tau$ defined by $\tau(u) = uT$ and observe that $L = \tau^{-1}(X)$. Now, the inverse of a rational transduction is also a rational transduction and context-free languages are preserved under rational transductions.

For an introduction to transductions see J. Berstel, Transductions and Context-Free Languages.

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


title: Is $\Theta$ symmetric?

text:
# Question
Title: Is $\Theta$ symmetric?
For example if $$ f(x)= \Theta (g(x)) $$

from the definition of the theta notation, there exist c1 and c2 constants such that

$$c\_1 g(x) \le f(x) \le c\_2 g(x)$$

then if only we took the constants $1/c\_1$ and $1/c\_2$ we could say from the definition that

$$ g(x)= \Theta (f(x)) $$

Right?

# Answer
> 8 votes
Right, except that the constants are actually $1/c\_2$ and $1/c\_1$. That is, $$c\_1 g(x) \leq f(x) \leq c\_2g(x) \Rightarrow \frac{1}{c\_2}f(x) \leq g(x) \leq \frac{1}{c\_1}f(x)\\,.$$ Also, remember that the inequalities only apply for large enough $x$.

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


# Question
Title: Asymptotic approximation of a recurrence relation (Akra-Bazzi doesn't seem to apply)
Suppose an algorithm has a runtime recurrence relation:

$ T(n) = \left\\{ \begin{array}{lr} g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n\_0\\ f(n) & : n \< n\_0 \end{array} \right. $

for some constant $0 \< \delta \< 1$. Assume that $g$ is polynomial in $n$, perhaps quadratic. Most likely, $f$ will be exponential in $n$.

How would one go about analyzing the runtime ($\Theta$ would be excellent)? The master theorem and the more general Akra-Bazzi method do not seem to apply.

# Answer
One possible approach might be by analogy to differential equations. Let $T'(n) = T(n)-T(n-1)$. Here $T'(n)$ is a discrete analog of the first derivative of $T(n)$. We get the following relationship: $$T'(n) = T(\lfloor \delta n \rfloor) + g(n).$$ The continuous analog of this is the differential equation $$t'(x) = t(\delta x) + g(x),$$ or, if you prefer to see it written differently: $${d \over dx} t(x) = t(\delta x) + g(x).$$ That's a differential equation.

Now you could try to solve the differential equation for the continuous function $t(x)$, then hypothesize that a similar function will be the solution to your original recurrence relation, and try to prove your hypothesis. At least, this is one general approach you could follow.

I've forgotten everything I once knew about differential equations, so I don't know the solution that differential equation, but maybe you will be able to solve it by reviewing all the techniques for solving differential equations.
> 5 votes

---
Tags: asymptotics, recurrence-relation
---


title: Big Theta Proof on polynomial function

text:
# Question
Title: Big Theta Proof on polynomial function
This is not homework. I have the solution but it's not what I'm getting. I know there are multiple solutions to the problem but I want to make sure that I'm not missing anything.

The question is as follows:

> Prove that 2$n^2$ \- 4n + 7 = Θ ($n^2$). give the values of the constants and show your work.

Here is how I approached the problem:

From the definition of Θ(g(n)):

0 ≤ C1$n^2$ ≤ 2$n^2$ - 4n + 7 ≤ C2$n^2$

Divide the inequality by the largest order n-term. (This is the only way I know how to solve these equations.)

> 0 ≤ C1 ≤ 2 - (4/n - 7/$n^2$) ≤ C2

Split the problem into two parts: LHS and RHS.

We start with the RHS:

Find constant C2 that will satisfy

> 0 ≤ 2 - (4/n - 7/$n^2$) ≤ C2

n=1, (2 - (4/1 - 7/$1^2$)) = 5

n=2, (2 - (4/2 - 7/$2^2$)) = 7/4

n=3, (2 - (4/3 - 7/9)) = 13/9

We choose C2 to be 2, n≥2 to satisfy the RHS.

LHS: we try to find a constant that will satisfy

> 0 ≤ C1 ≤ 2 - (4/n - 7/$n^2$)

From above, we know that after n=2, the equation approaches 2 as n grows larger, so if we pick a constant that is less than 2 then it should satisfy the LHS.

We choose C1 to be 1. For n, choosing 1 would satisfy the left hand side, but since the RHS needs n≥2, we stick with it.

So the constants that prove 2$n^2$ - 4n + 7 = Θ ($n^2$) are

> C1 = 1 , C2 = 2 , n≥2

The given solution to this problem chooses n≥4, but I'm not sure why. It seems that n≥2 would work fine. Am I wrong somewhere?

If I'm not wrong, if I would have picked C1 to also be 2, wouldn't that also satisfy the left hand side since the inequality allows it to be ≤?

# Answer
Your solution is fine. There are multiple ways to prove this fact, all of them valid/correct. So your approach is valid, and it's possible that the solution from your class is also valid: that's not a contradiction.

Let me give you one piece of advice for structuring your proof in the future, though. In the argument you sketched in the question, you are "working backwards": you start from the statement you wish were true (that $c\_1 n^2 \le 2 n^2 -4n + 7 \le c\_2 n^2$), and then you try to derive what needs to be true about $c\_1,c\_2$ for your wish to hold true. Experience has proven that that kind of reasoning is error-prone, though: it's easy for you to make a mistake along the way. It is also hard for others to check.

When you write up your proof, I suggest you do the reasoning in the opposite direction. Start from what you know is true, and then derive the implications of that, ending with the conclusion that $c\_1 n^2 \le 2 n^2 -4n + 7 \le c\_2 n^2$. This better matches how people think and makes it easier for the reader to understand what's going on. And the purpose of a proof is to communicate an idea to the reader, so the proof should be structured to make the reader's life easier: to make it as easy as possible for the reader to verify that the proof's reasoning is correct and valid. It's just like a good book; good writing is chosen to make life good for the reader. Proofs are the same way. And, ultimately, this will benefit you too: in my experience, if you follow this approach, then you're less likely to make a subtle mistake in your proof.

So, a better proof outline would be to show that $n^2 \le 2n^2 - 4n + 7$ holds for all $n\ge 2$ (because such-and-such), and show that $2n^2 - 4n + 7 \le 2n^2$ holds for all $n\ge 2$ (because blah-de-blah), and then conclude that $2n^2 - 4n + 7 \in \Theta(n^2)$. I realize this kind of proof is harder to write, because you need to know the value of $c\_1,c\_2$ to use before you can start writing down this style of proof. But you know what? That's OK. You can do a side calculation, on scratch paper, to figure out what value of $c\_1,c\_2$ to use. Don't show us that side calculation; just figure out what value of $c\_1,c\_2$ would be good ones to do, and then start the proof with you pulling $c\_1=1,c\_2=2$ magically out of thin air, and demonstrate that your choice is valid. This style of proof will be better for you, and better for the reader.
> 8 votes

---
Tags: asymptotics
---