# Question
Title: Are there undecidable properties of non-turing-complete automata?
Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability).

I would like to get an example (if possible) of an undecidable problem that is defined *without using Turing machines* explicitly.

Is Turing completeness of a model necessary to support uncomputable problems?

# Answer
> 15 votes
Undecidable problems about context free grammars, and hence, pushdown acceptors as well, which are restricted TMs from Wikipedia...

1. Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?
2. Given two CFGs, do they generate the same language?
3. Given two CFGs, can the first generate all strings that the second can generate?

There are many others about CFGs/PDAs as well as CSGs/LBAs and many other "simpler than TM" models.

# Answer
> 7 votes
It is not clear what you are asking in the later part of the question mainly because "a problem about a machine model" is not defined.

> I would like to get an example(if possible) of undecidable problem without needing Turing Machine

Let be $\\{M\_i\\}$ be a class of machines and lets use $i$ as the code of $M\_i$. We can interpret $i$ also as the code of $i$th TM and then ask that given $M\_i$ does the $i$th TM halt? And this problem about $M\_i$s is undecidable.

A language is just a set of strings, what interpretation you assign to the strings has no effect on the decidability of the language. Unless you formally define what you mean by *a machine model* and *a problem about those machines* your later questions cannot be answered.

> Is Turing complete the minimal machinery to support an undecidable problem?

Again, the point I mentioned above applies. A more reasonable question would be: are all undecidability proofs go through something similar to the undecidability of halting problem for TMs? (The answer is: there are other ways).

Another possible question is: what is the smallest subset of TMs where the halting problem for them is undecidable. Obviously such a class should contain problems which do not halt (otherwise the problem is trivially decidable). We can easily create artificial subsets of TMs where the halting problem is not decidable without being able to compute anything useful. A more interesting question is about large decidable sets of TMs where the halting is decidable for them.

Here is another point: as soon as you have very small ability to manipulate bits (e.g. a polynomial size $\mathsf{CNF}$) you can create a machine $N$ with three inputs: $e$, $x$, and $c$ such that it output 1 iff $c$ is a halting accepting computation of TM $M\_e$ on input $x$. Then you can ask the problems like: is there a $c$ s.t. $N(e,x,c)$ is 1? which is an undecidable problem.

# Answer
> 6 votes
There is a very simple undecidable problem for finite state automata. Break the alphabet into two halves $\Sigma \cup \bar\Sigma$, where the letters in $\bar\Sigma$ are "barred" copies. Now, given a finite state automaton $A$ over $\Sigma\cup\bar\Sigma$ decide whether it accepts a string such that the unbarred part equals the barred part (if we ignore the bars). E.g., string $a a \bar a \bar a b\bar b \bar aa$ would be ok (both parts spell $aaba$).

Yes, this is Post Correspondence Problem hidden in a finite state automaton. The Turing completeness is far from obvious in the question. It is there, in the background, as the two copies (unbarred and barred) together code a queue, which itself is of Turing power.

# Answer
> 3 votes
> "Is it possible to build an undecidable problem for an automaton less powerful than a Turing Machine?"\`

Yes. An automaton is a consistent axiomatic formulation of number theory (e.g. see (1)) and therefore by Gödel's 1st incompleteness theorem it must include undecidable propositions.

**Example:**

Any problem that is undecidable for a TM is also undecidable for any automaton that a TM can simulate. Why? Because if an automaton that is less powerful than a TM could decide a language that a TM cannot decide, a TM should be able to decide it by simulating the automaton with yields a contradiction.

# Answer
> 1 votes
Emil Post wanted to find the answer to exactly this question: Is there a non-recursive (non-computable) set which does not solve the halting problem. He succeeded only in part, but what he did, was create what is called **simple sets**.

From Wikipedia:

> A subset of the naturals is called simple if it is co-infinite and recursively enumerable, but every infinite subset of its complement fails to be enumerated recursively. Simple sets are examples of recursively enumerable sets, that are not recursive. Have a look at the Wikipedia article for more information and references, simple set.

---
Tags: computability, automata, undecidability
---


# Question
Title: Assumption on weights in threshold circuits
A threshold gate implementing a linear threshold function on $n$ boolean inputs $x\_1, x\_2 \ldots, x\_n$ is given by the equation: $w\_1 x\_1 + w\_2 x\_2 + \ldots, w\_n x\_n \ge t$ where $w\_1, \ldots, w\_n, t \in \mathbb{R}$. The $w\_i$'s are called the weights of the threshold function and $t$ is called the threshold, and naturally, the gate fires a $1$ on an input $x$ if the weighted sum given by the equation above exceeds $t$.

Now, almost everywhere in the literature on threshold circuits, I encounter this fact (which I am guessing, is folklore since I couldn't find a proof anywhere): The $w\_i$'s in the linear equation above can be made integers (on $n \log{n}$ bits), and a threshold circuit made up of these gates will still compute whatever was possible with real weights. I have given this some thought, and I think it must be a simple trick, but I have failed to obtain a proof of this fact. Can somebody help or provide me with a reference? (the only reference I could find was a text by Muroga, which I couldn't procure)

# Answer
Given $w\_1,\ldots,w\_n,t$, let $X$ be the set of assignments such that $\sum\_i w\_i x\_i \geq t$, and consider the linear program with variables $z\_1,\ldots,z\_n$ and the $2^n$ constraints $$ \begin{align\*} \sum\_i z\_i x\_i \geq +1 & (x\_1,\ldots,x\_n) \in X \\ \sum\_i z\_i x\_i \leq -1 & (x\_1,\ldots,x\_n) \notin X \end{align\*} $$ This linear program (with a constant objective function) is feasible (since $z\_i = w\_i/t$ is a solution), and so has a solution $z\_1,\ldots,z\_n$ which is a vertex. As such, it is the solution of a system of $n$ equations of the form $$ \sum\_i z\_i x\_i = \pm 1. $$ Cramer's rule gives each $z\_i$ as a ratio of two $n \times n$ determinants of matrices of $0,\pm 1$ entries; in fact the denominator is the same. Each numerator $N\_i$ and the common denominator $D$ is at most $n!$ in magnitude, so multiplying everything by $D$, we get an integral solution $N\_1,\ldots,N\_n,D$, where all the quantities are at most $n! \leq n^n = 2^{n\log n}$ in magnitude.
> 6 votes

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


# Question
Title: If a predicate is not computable, what can be said about its negation?
Doing the following exercise:

> Let $\overline{HALT(x,y)}$ be defined as
>
> $\overline {HALT(x,y)} \iff \text{program number y never halts on input x}$
>
> Show that it is not computable.

Just want to make sure I have understood the concept correctly. We had in a theorem that HALT(x,y) is not computable which means that we cannot determine whether program number y eventually halts on input x. I realized that $\overline {HALT(x,y)}$ is the negation of HALT(x,y). Is it true (I cannot find it in my book or on the internet) that if a function is (not) computable, its negation is also (not) computable? A function being computable means there is a program p which computes it, we cannot say there is a program Q that computes its negation. Or can we draw such conclusion?

# Answer
> 5 votes
To answer the literal question that you asked, $\mathsf{HALT}$ is a boolean function, i.e. a function whose values are in the set $\\{\mathsf{false}, \mathsf{true}\\}$. The negation of $\mathsf{HALT}$ is the composition of this function with the negation operator $\mathsf{not}$. Since $\mathsf{not}$ is bijective, any algorithm that computes $\mathsf{HALT}(x,y)$ terminates if and only if $\mathsf{not}(\mathsf{HALT}(x,y))$ terminates (because if $\mathsf{not}(\mathsf{HALT}(x,y))$ terminates then $\mathsf{not}(\mathsf{not}(\mathsf{HALT}(x,y))) = \mathsf{HALT}(x,y)$ terminates).

Framing the question in a more intuitive manner, $\mathsf{HALT}$ is a predicate: it is the characteristic function of a set. The predicate is computable if and only if the set is decidable, i.e. recursive. The complement of a recursive set is a recursive set (the reasoning above is one way to prove it), which amounts to saying that the negation of the corresponding predicate is computable iff the predicate is.

A related property that is not conserved by negation is semi-decidability, as in recursively enumerable sets. The complement of a recursively enumerable set is not r.e. in general (in fact, an r.e. set has an r.e. complement iff it is recursive). Whereas a recursive set's characteristic function uses two values to distinguish between the elements that are in the set and the ones that aren't, a recursively enumerable set can be given as the domain of a partial recursive function: the r.e. set is the domain on which the function has a value. If the function is given as an algorithm, the domain is the part where the computation of the function halts and returns a value; the complement of the domain is the part where the computation does not halt.

# Answer
> 6 votes
If a function F is computable, so is !F, as you can simply compute F and return the negated result.

For the same reason, if a function isn't computable, neither is its negation.

---
Tags: computability, proof-techniques
---


# Question
Title: Regarding the height of a recursion tree on dynamic programming
I am trying to understand dynamic programming and I am watching this mit video. If you guys could take some time out , can you refer to the slide on 41:36 . Why is the height m+n. I just don't get it why is the heigh of this recurrence tree m+n.

http://videolectures.net/mit6046jf05\_leiserson\_lec15/

Thank you.

# Answer
Each level you subtract $1$ from the left *or* the right in the worst case (when $x \ne y$). So intuitively if you go down the left over and over again (along the leftmost part of the tree), it will reach $(1,n)$, at level $m$, and you will only be able to go right from there. Then you will go down $n$ more levels to the bottom.
> 1 votes

---
Tags: recurrence-relation, dynamic-programming
---


title: How can I improve my Algorithm?

text:
# Question
Title: How can I improve my Algorithm?
> This is a problem from Interview Street in Dynamic Programming section. https://www.interviewstreet.com/challenges/dashboard/#problem/4f2c2e3780aeb
>
> Billboards(20 points)
>
> ADZEN is a very popular advertising firm in your city. In every road you can see their advertising billboards. Recently they are facing a serious challenge , MG Road the most used and beautiful road in your city has been almost filled by the billboards and this is having a negative effect on the natural view.
>
> On people's demand ADZEN has decided to remove some of the billboards in such a way that there are no more than K billboards standing together in any part of the road.
>
> You may assume the MG Road to be a straight line with N billboards.Initially there is no gap between any two adjecent billboards.
>
> ADZEN's primary income comes from these billboards so the billboard removing process has to be done in such a way that the billboards remaining at end should give maximum possible profit among all possible final configurations.Total profit of a configuration is the sum of the profit values of all billboards present in that configuration.
>
> Given N,K and the profit value of each of the N billboards, output the maximum profit that can be obtained from the remaining billboards under the conditions given.

```
Constraints
1 <= N <= 1,00,000(10^5)
1 <= K <= N
0 <= profit value of any billboard <= 2,000,000,000(2*10^9)

```

> My Solution (Psuedocode):

```
Let Profit[i] denote the Profit from ith billboard.
(i, j) denotes the range of billboards
MaxProfit(i, j) for all (i, j) such that i<=j and i-j+1 <= K is:
    MaxProfit(i, j) = Profit[i] + Profit[i+1] + ... + Profit[j];

For other (i,j) MaxProfit equals,

MaxProfit(i, j)
{
        if(MaxProfit(i, j) is already calculated)
            then return its value;
    max = 0;
    for all k such that i<=k<=j // k denotes that, that position has no   billboard
    {
        temp = MaxProfit(i, k-1) + MaxProfit(k+1, j);
        if(temp > max)
        max = temp;
    }
return max;
}

```

My solution is of order $$N^2$$. So I get TLE and Segmentation fault for larger N. I have already passed 6/10 test cases. I need to pass remaining 4. Help needed.

# Answer
> 8 votes
You can do it in $O(N \log N)$ time and $O(N)$ space.

Instead of finding the billboards that you want to keep, find the billboards that you want to get rid of. You need to find the minimum cost set of billboards such that there is no gap of more than $K$ between two billboards. Do this by constructing a table where the $i$th entry is the minimum cost to remove the $i$th billboard and enough previous billboards to make this legal. Now, to add an entry to the table, you need to find the minimum of the previous $K$ entries to the table. You can do this in $O(\log N)$ time using a priority queue.

If $K \ll N$, you might want to use a fancier priority queue that takes $O(\log K)$ time instead; but I'd guess that for large $K$, the simpler priority queues such as heaps that don't admit deletion of a non-MIN item are quicker for this problem. I don't know how tight time limits Interview Street has set for this problem.

---
Tags: algorithms, data-structures, dynamic-programming
---


title: Instruction Translation

text:
# Question
Title: Instruction Translation
Imagine two machines of different architecture which produce output of a standard format.

If you have a program for one machine and can observe it's operation and output, what techniques exist to automatically produce an equivalent program for the alternate architecture?

By equivalent I mean produces equal output (by some equality relation) for equivalent input.

# Answer
> 4 votes
A "simple" way of solving this problem is to write an emulator for the first machine's instruction set on the second machine. Then set the first program as input to this emulator. One could also apply partial evaluation techniques to optimise things a little, which would result in an emulator that runs only the first program (and nothing else).

---
Tags: programming-languages, compilers
---


# Question
Title: Help need to learn Quantum Computation and Information
I want to learn quantum computation and information. I am studying from Nielsen & Chuang book for this. Is there any online vedio (lecture series) starts from basics of quantum computation and information up to factorization, discrete log, search etc?

# Answer
> 5 votes
I haven't watched them myself, but you could probably do worse than Michael Nielsen's videos, Quantum Computing for the Determined.

I'd recommend also that you look online for written lecture notes; there is a very strong culture in the field of having students scribe notes which then have a habit of finding their way online. These can sometimes vary substantially in quality, but often the lecturer will take them and edit them, resulting in quite a good set of notes. Just as an example that I grabbed off the top of Google, Ronald de Wolf's lecture notes seem fairly comprehensive; but others surely exist, and if you find the going hard with those notes, you will probably find one set of notes which better suits your learning style.

---
Tags: reference-request, education, quantum-computing
---


# Question
Title: Who conceived the concept of Discrete Event Simulation, and when?
I'm trying to trace back the origin of the general concept of Discrete Event Simulation and found a 1968 article by Fishman and Kiviat mentioning the term. It is titled *The statistics of discrete-event simulation*.

However, I'm unable to verify this as the origin of the term.

Is there further historical information on this?

# Answer
> 6 votes
Cornell's Conway, Johnson and Maxwell's paper Some Problems in Digital Systems Simulation, was published in 1959 in Management Science. It discusses many of the key points of a discrete event simulation, including managing the event list (they call it an element-clock) and refer to "more efficient but more complicated methods" for locating the next event, but don't discuss the heap data structure. This paper refers to earlier publications, but they don't seem to discuss the specifics of a discrete-event simulation like this paper does.

---
Tags: reference-request, simulation, history
---


# Question
Title: Adjacent house , dynamic programming problem
I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it can be either positive or negative value. But the aim is to maximize the profit by buying a subset of these houses. So infact, you should buy houses which are \>0 value. However, you cannot buy houses that adjacent to the house you are buying, e.g i-1 and i+1 should not be bought. I am not quite sure where to start to look at this problem, I mean what exactly will be the difference of looking it from the greedy or dynamic programing way. Thanks for any suggestion.

# Answer
I'll just leave a broad hint. Suppose $H(1:n)=\[h\_1,h\_2\ldots,h\_n\]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h\_{n-1}$ in its optimal list, or it doesn't. If it does include $h\_{n-1}$, then we can't add $h\_n$ to the list and we are done. If it doesn't include $h\_{n-1}$, then we can check if the profit rises or drops with the inclusion of $h\_{n}$.

Can you now write down a recurrence? And solve the recurrence efficiently? What happens when we have one or two houses in all?

*Update*:@user: Sorry, I forgot that there are negative values! You do need a 2D array and split the problem into to the small pieces $\[h\_i \ldots h\_j\]$ for $1\leq i \< j\leq n$,
> 5 votes

---
Tags: dynamic-programming, knapsack-problems
---


title: Analyzing Twitter Relationships

text:
# Question
Title: Analyzing Twitter Relationships
I'm not even sure if this is the right StackExchange to post this, but it seems like sentiment analysis would go here.

What would be the best approach to determine if two people on Twitter are actually friends?

I think that the first criteria would be that they are following each other. This would eliminate all of the celebrities, companies, etc. that a person follows.

The second criteria could be physical proximity to one another. If two people tweet from the same general areas, then there's probably a higher chance that they actually know each other.

After that, I'm not sure what criteria I should look for. Would sentiment analysis of their tweets to each other be a viable option? With that friendly sentiment could indicate that they actually know each other.

# Answer
> 3 votes
My metric of choice would be the communication by **direct message**. However, this metric is hard to come by since measuring it requires the user's consent.

I do not think that using similar hashtags or terms has any say over friendship. People tend to adjust to the language they read and do not require personal bonding to do so.

I think **mentions** are a good way to identify friends and foes alike. A good way would probably be to see whether mentions beget a reply. Users tend to 'reward' pleasant and useful mentions with replies. However, the semantics of these messages are very important and only quantified analysis may not be enough.

Since I cannot comment yet, I would like to reply to the suggestion of using machine learning. I do not think that machine learning can effectively identify friends, even if one manages to get 'sufficient' data. Using Twitter is a rather creative process and generally not uniform across social circles.

# Answer
> 1 votes
What you want to do is make some form of graph. Your nodes could be users on Twitter, or posts, actions, etc. I would recommend a weighted digraph with multiple edges allowed (though you could just represent this by summing the weights of multiple edges). You want your edges to be something which indicates a link between these two people, such as mentioning them in a post, or using common hash-tags.

What you put in this graph and how you score it has much more to do with psychology than computer science, so I won't comment to much on that. My recommendation would be to start with a group of people on twitter you know to be friends, and look at what their graphs look like to start, then use that to determine the weight you will give to each type of interaction.

Then, to find an overall score, you can use some sort of metric on your graph. You could use the overall weight of the edges connecting the two users, or sum the weights of the paths between them, weighting longer paths lower.

---
Tags: algorithms, machine-learning, computer-networks, social-networks
---


title: Are randomized algorithms constructive?

text:
# Question
Title: Are randomized algorithms constructive?
From , the proofs by the probabilistic method are often said to be non-constructive.

However, a proof by probabilistic method indeed designs a randomized algorithm and uses it for proving existence. Quoted from p103 of Randomized Algorithms By Rajeev Motwani, Prabhakar Raghavan:

> We could view the proof by the probabilistic method as a randomized algorithm. This would then require a further analysis bounding the probability that the algorithm fails to find a good partition on a given execution. The main difference between a thought experiment in the probabilistic method and a randomized algorithm is the end that each yields. When we use the probabilistic method, we are only concerned with showing that a combinatorial object exists; thus, we are content with showing that a favorable event occurs with non-zero probability. With a randomized algorithm, on the other hand, efficiency is an important consideration - we cannot tolerate a miniscule success probability.

So I wonder if randomized algorithms are viewed as not constructive, although they do output a solution at the end of each run, which may or may not be an ideal solution.

How is an algorithm or proof being "constructive" defined?

Thanks!

# Answer
The probabilistic method is typically used to show that the probability of *some* random object having a certain property is non-zero, but doesn't exhibit any examples. It does guarantee that a "repeat-until-success" algorithm will eventually terminate, but does not give an upper bound on the runtime. So unless the probability of a property holding is substantial, an existence proof by the probabilistic method makes a very poor algorithm.

In point of fact, probabilistic algorithms aren't actually constructive existence proofs, so much as they are algorithms to *produce* constructive existence proofs. The output is an object of the sort which it was meant to prove the existence of; but the fact that it will *eventually* yield one ("there will exist an iteration in which it yields an example — except with probability zero...") is not enough to be constructive; it will only be satisfactory to someone who already accepts that non-zero-probability-without-construction suffices for existence. Conversely, if you do have a good bound on the run-time, then there's in principle no excuse not to run it in order to actually produce an example. A good probabilistic algorithm still isn't a constructive proof, but a good **plan** to obtain a constructive proof.

Note that this idea, that a randomized algorithm is a *proof strategy* (as opposed to a proof in itself) to demonstrate an existential quantification, is not unlike the idea that induction is a good proof strategy to show a universal quantification (over the natural numbers). This analogy may seem compelling, as induction is essentially the heart of recursion as a computational technique. (For any positive integer $n$, if you want to decide whether $n^2$ is a sum of the consecutive odd numbers preceding $2n+1$, you can reduce this to investigating whether $(n-1)^2$ is a sum of the consecutive odd numbers preceding $2n-1$, and so forth.) Induction is essentially an algorithmic proof-strategy which we have elevated to a theorem, allowing us to have the knowledge without explicitly computing it each time. However, induction is accepted constructively because it is already an axiom(-scheme) of Peano arithmetic, and one which is independent of the other axioms. By contrast, there is no rule of inference or axiom which allows the probabilistic method to prove existence constructively, or to constructively prove that probabilistic algorithms produce existence proofs, or anything along these lines. You simply cannot prove that there are examples of a class of object from the fact that there is a probabilistic algorithm to construct it, unless you already accept that proposition, either as an axiom, or from other premises.

Of course, one might adopt a philosophical position intermediate to constructivism and the classical approach to existence, and say that what one wants is not constructions per se but construction-schema which are allowed to fail with any probability less than one; that would make any probabilistic construction "schematic", if not completely constructive. Where one wishes to draw the line, to say that they find an existence proof "satisfactory", ultimately depends on how much intuition (in a non-philosophical sense) they wish to gain from proofs.
> 8 votes

# Answer
Uniform proof complexity is a field devoted (among else) to the study of constructive notions of proofs, and their relation to complexity classes. For each of the popular (uniform) circuit complexity classes, one can define a theory in which everything which is provable has a "backing" in an algorithm in this complexity class. Randomized algorithms are accommodated through versions of the pigeonhole principle (oddly enough).

Unfortunately I'm not an expert so I can't say much more, other than point you to the book by Cook and Nguyen (same Cook as in Cook's theorem) and to the work of Emil Jeřábek, especially his thesis on randomized computation.
> 5 votes

---
Tags: algorithms, terminology, randomized-algorithms
---


title: Polynomial time reducibility

text:
# Question
Title: Polynomial time reducibility
> $L\_1$ and $L\_2$ are two languages defined on the alphabet $\sum$. $L\_1$ is reducible to $L\_2$ in polynomial time. Which of the following cannot be true?
>
> * $L\_1 \in P$ and $L\_2$ is finite
> * $L\_1 \in NP$ and $L\_2 \in P$
> * $L\_1$ is undecidable and $L\_2$ is decidable
> * $L\_1$ is recursively enumerable and $L\_2$ is recursive

My reasoning is as follow,

If $A \le\_p B$, and $B \in P$, then $A$ can be reduced to $B$ in polynomial time and solved in polynomial time making $A \in P$. Thus I initially figured the 2nd choice as false and thus the right answer.

However using the same argument on mapping reducibility, the 3rd choice seems to be false as well. The fourth choice is the same as the third one.

I was unsuccessful in reasoning anything about the 1st choice.

To put my above arguments in context, I am learning about theory of computation and have just about skimmed the surface of computability and complexity theory. Helo me out.

# Answer
Three of the options use the same trick: if $C1,C2$ are two classes of languages and $C1 \subseteq C2$; then $L1 \in C2$ doesn't imply that $L1 \notin C1$.

The only choice that cannot be made true is 3: if there is a polynomial time reduction from an undecidable language $L\_1$ to a decidable language $L\_2$ then $L\_1$ becomes decidable, too (just build a Turing Machine that computes the reduction and then solve the problem using the decider for $L\_2$) and this is a contraddiction.
> 3 votes

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


# Question
Title: What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$?
Given an adjacency matrix $A\_G$ of an undirected graph $G$, it is easy and straightforward to compute the characteristic polynomial $\chi\_G(\lambda)$. What about the other way around? The problem can be formulated as follows.

> **Problem** Given a polynomial $P$, decide whether there is a graph $G$ with the corresponding adjacency matrix $A\_G$ such that its characteristic polynomial $\chi\_G(\lambda)$ equals the given $P$.

For an arbitrary $P$, it is not always the case that there is a corresponding $A\_G$. The naive exhaustive algorithm for the problem uses a basic theorem in algebraic graph theory:

> **Theorem** Let $G=(V,E)$ be a graph with adjacency matrix $A\_G$ and $\chi\_G(\lambda) = \lambda^n+c\_1\lambda^{n-1}+c\_2\lambda^{n-2}+\cdots+c\_{n-1}\lambda+c\_n$, then
>
> **(1)** $c\_1=0$,
>
> **(2)** $-c\_2 = |E|$, and
>
> **(3)** $-c\_3 = \text{twice the # of triangles in G}$.

Now, given $P$, the algorithm goes through every candidate $A\_G$ of a corresponding $G$ with $|E|=-c\_2$ and number of triangles ($K\_3$) equal to $-c\_3$. For each $A\_G$, compute $\text{det}(A\_G - \lambda I)$ and see if it equals the given $P$. If none match, return false. Otherwise, return the $A\_G$.

This works, but is clearly not fast. The exhaustive algorithm would work even without the above theorem. Its use makes the search space smaller. What's a fast and more clever algorithm?

# Answer
The short answer is **no**. No quick algorithm for this problem is known.

A big open problem (for at least 50 years) in algebraic graph theory asks about the existence a regular graph of degree 57 order 3250 girth 5 and diameter 2. This is known as a Moore graph.

However, it is known that if such a graph exists its characteristic polynomial has to be $p(x) = (x-57)(x+8)^{1520}(x-7)^{1729}$ \[1, Proposition 1\].

So if there would be a quick solution to your problem, this big open problem would be solved already.

In fact, the theorem that you stated can be further generalized. The $i$'th coefficient of the characteristic polynomial of $G$ is given by $$(-1)^{i}c\_i = \sum (-1)^{r(H)} 2^{s(H)}$$ where the summation is taken over all subgraphs $H$ of $G$ that have order $i$ and whose connected components are $K\_2$ and cycles. The function $s(H)$ counts the number of components of $H$ that are cycles while $r(H)$ denotes the rank of $H.$

---

\[1\] M. Macaj, J. Siran. Search for properties of the missing Moore graph, Linear Algebra Appl., 432 (2010), 2381–2398.
> 7 votes

---
Tags: algorithms, graphs, discrete-mathematics, matrices
---


# Question
Title: Prove correctness of recursive multiplication algorithm
I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together:

```
function multiply($n, $r) {
    if($n == 1)
 return $r;
    else if($r == 1)
 return $n;
    else
        return $r + multiply($n - 1, $r);
}

```

How do I prove my algorithm is correct?

A quick google search tells me I have to prove that it works for $n + 1$ and I have to prove that it terminates. Unfortunately I'm still incredibly new to this and haven't the faintest clue as to where to start for proving my algorithm correct, so I would really appreciate some help here. I think maybe I have to do some sort of proof by induction but as this is an algorithm, I wouldn't know where to start.

# Answer
> 7 votes
You need to do a proof by induction on $n + r$. Let $P(m)$ be the statement "for any $n,r \geq 1$ satisfying $n+r = m$, $\mathrm{multiply}(n,r) = nr$. The proof by induction goes along the following lines.

Base case: $m=2$, so $n=r=1$. By inspection, $\mathrm{multiply}(1,1)=1$.

Induction step: suppose $P(m)$ is true for some $m \geq 2$, and let $n,r\geq 1$ satisfy $n+r = m+1$. If $n=1$ or $r=1$ then $\mathrm{multiply}(n,r)=nr$ by inspection. Otherwise, by $P(m)$, $\mathrm{multiply}(n-1,r)=(n-1)r$ (since $n-1+r = m$), so $\mathrm{multiply}(n,r) = r+\mathrm{multiply}(n-1,r) = r+(n-1)r = nr$.

By the principle of mathematical induction, $P(m)$ is true for all $m$, and so for any $n,r\geq 1$, $\mathrm{multiply}(n,r)=nr$.

---
Tags: algorithms, algorithm-analysis, correctness-proof, induction
---


title: Language member explanation

text:
# Question
Title: Language member explanation
Given the following formal language $L$:

$$ L=\\{ww \mid w\in\\{a,b\\}^\*\\}$$

Why is $a$ not a member of this language?

So what is $\\{a,b\\}^\*$ exactly? I thought it means $(a+b)^\*$?

# Answer
The notation $\\{a,b\\}^\*$ stands for all strings over the alphabet $\\{a,b\\}$. A word is in the language $L$ if it is of the form $ww$, where $w$ is an arbitrary word over the alphabet $\\{a,b\\}$. For example, taking $w = aba$, we see that $abaaba \in L$. If $w$ has length $n$ then $ww$ has length $2n$, and in particular every word in $L$ has even length. So $a \notin L$. But this idea isn't enough to prove that $ab \notin L$.

If $x$ is a word of odd language, then $x \notin L$. If $x$ has length $2n$, then write $x=yz$, where $y$ consists of the first $n$ characters, and $z$ consists of the last $n$ characters. Then $x \in L$ if and only if $y=z$. If $x=ab$ then $y=a$ and $z=b$ and so $y \neq z$, implying $ab \notin L$.
> 3 votes

# Answer
The language states that each word of the language consists of two parts `w`, which a condition on the `w`.

As a result you always need a even number of characters in each word of this language. In consequence `a` is not a member of L!

The words `w` created by `{a,b}*` are like you stated: A arbitrary sequence of `a` or `b` characters (a sequence of zero characters as well). For a member-word of the language, however, these words are "doubled" or concatenated to each other.
> 1 votes

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


# Question
Title: Practical applications of disjoint set datastructure
I know that the disjoint set datastructure is used to keep track of the connected components of an undirected graph when the edges are added to the graph dynamically . I also know that is is used in Kruskal's algorithm for minimum spanning trees . What are the other possible applications of this datastructure ?

# Answer

> 7 votes

---
Tags: algorithms, graphs, data-structures
---


# Question
Title: Shifting subset sum solution by constant positive integer
While reading the Wikipedia article about the subset sum problem I came across this example: "is there a non-empty subset whose sum is zero? For example, given the set $\\{ −7, −3, −2, 5, 8 \\}$, the answer is yes because the subset $\\{ −3, −2, 5 \\}$ sums to zero".

I have noticed that if we shift all the values of the set by adding a 8 to all elements we get $\\{ 1, 5, 6, 13, 16 \\}$ and then add the constant to the desired solution $0 + 8$, so now the question becomes is there a subset that adds up to $8$, which is not possible. My question is why does shifting the set and the solution by a positive integer "break" the solution, isn't the mathematics sound from the previous operations?

# Answer
Your error is that you add your constant to the left-hand side of the equality multiple times, and only once to the right side. For example, $1+1=2$ clearly holds. If you add $8$ to both sides of it, you get $1+1+8=10$ which also holds. Erroneously you might add it twice to the left hand side and get $9+9=10$, which does not hold.

In your case, $0$ should not become $8$, but instead $8 \cdot 5 = 40$. Now a solution exists again.
> 5 votes

---
Tags: integers, decision-problem
---


# Question
Title: What are the mathematical prerequisites for adaptive machine learning algorithms?
I am a PhD student in Computer Science who switched his PhD a little bit towards ML algorithms combined with something else... I am an expert in that something else, say image processing, but not an expert in Machine Learning. What should I read/learn to get the ML mathematics right? Especially for adaptive learning algorithms.

# Answer
The precise mathematical skills that you'll need for your studies will vary depending on exactly which area of ML you'll be working in. In general though Bayes theorem, probability theory and statistics will be your constant companion. Getting a good grasp of these is extremely helpful when it comes to fully understanding how learning algorithms work, and how they can be modified.

Partial differential equations, linear algebra, and mathematical induction are also very important. However beyond these it is difficult to say exactly which areas you should brush up on. In my opinion it depends on what problem you are trying to solve.

For instance is it a regression problem? Is it a classification problem? Are you clustering data? You mention adaptive algorithms, but many ML algorithms could be considered adaptive. As you become familiar with the ML field you'll find that people use different terms to describe exactly the same thing :) a little frustrating to be honest! But the second link you provided is from a non - computer science journal, so just be aware the definition of adaptive in this paper may mean something different in ML. For instance I don't work in adaptive algorithms, but my work has to adapt to high throughput data streams so is most certainly adaptive. But it falls under the category of Semi-supervised learning.

I would recommend taking a look at the following books for more information:

**Machine Learning by Tom M. Mitchell, 1997** \- This is a great and relatively easy going introduction to machine learning. Despite being over ten years old, this book covers the key topic areas, and introduces you to important concepts. Indirectly this will introduce you to the mathematics of Machine Learning. You'll be able to tell from this book what type of mathematics skills your particular problem may require.

**Artificial Intelligence: A Modern Approach by Stuart Russell & Peter Norvig, 3rd Edition, 2009** \- All encompassing text (1000+ pages) covers machine learning in great detail. Authoritative text.

**Pattern Recognition and Machine Learning (Information Science and Statistics), Christopher M. Bishop, 2006** \- Excellent authoritative text that goes in to ML in great depth. This includes introductory chapters that get you up to speed with the mathematics required to understand learning algorithms (including probability). Can be hard going if you have no mathematics experience.

To support any reading you do I suggest you take a look at the Andrew Ng machine learning course on Coursera. I watched some of these before starting my own study, so too did many of my friends.
> 6 votes

---
Tags: reference-request, machine-learning, education, learning-theory
---


# Question
Title: What are some applications of binary finite fields in CS?
I was looking at details on finite fields. Finite binary fields, e.g. $\mathbb{F\_2}$, are used in CS in some places such as circuit theory \[1\].

> What are some key applications of finite fields in CS?

I am also looking for uses of $\mathbb{F\_{2}^n}$ which Mathworld shows can be represented as binary vectors.

---

\[1\] Noga Alon and Gil Cohen. On Rigid Matrices and Subspace Polynomials. Electronic Colloquium on Computational Complexity, Report No. 133 (2012).

# Answer
Finite fields come up in many places. Here are just a few examples:

1. The Razborov-Smolensky polynomial method.
2. Fourier analysis, as used for example in the proof of the PCP theorem, or fast integer multiplication.
3. List decoding - codes like Reed-Muller are algebraic codes.
4. Algebraization, the method used to prove IP=PSPACE.
5. Elliptic curves over finite fields are used in cryptography.
> 7 votes

# Answer
For one example, it shows up in the analysis of approximation algorithms for Feedback Vertex Set.

The *characteristic vector* of a simple cycle $C$ in a graph $G = (V, E)$ is a vector in $\mathbb{GF}\[2\]^m, m = |E|$. A vector over this field has 1s in components correspond to edges of $C$ and 0s in the other components.

We can use this to describe the *cycle space* of $G$. That is, a subspace of $\mathbb{GF}\[2\]^m$ that is spanned by the characteristic vector of all simple cycles of $G$. The *cyclomatic number* of $G$, $\text{cyc}(G)$, is the dimension of this space. Using $\text{comps}(G)$ to denote the number of connected components in a graph we have $$\text{cyc}(G) = |E| - |V| + \text{comps}(G).$$

The vectors of $\mathbb{GF}\[2\]^m$ correspond to *cut vectors* of $G$ where a 1 corresponds to a component that has an edge in the cut, and 0 otherwise.

Using this fact, you can derive results giving an upper bound of $2 \text{OPT}$ for an approximation algorithm using a local-ratio scheme.
> 4 votes

---
Tags: algorithms, reference-request, discrete-mathematics, applied-theory
---


# Question
Title: How do the following Hash Functions compare?
Consider the two hash functions used to map IP addresses. $x\_i$ represents a octave (or "bit field") of the address.

Hash Function 1: $$h\_a(x\_1, x\_2, x\_3, x\_4) = \sum^{4}\_{i=1} a\_ix\_i \bmod n$$

Where $n$ is a prime number closest to the total number of IP addresses being mapped. The probability of two IP addresses being mapped to the same bucket is $\frac{1}{n}$ using this hash function.

Hash Function 2:

$$h\_a(x\_1, x\_2, x\_3, x\_4) = \sum^{4}\_{i=1} x\_i \bmod n$$

What would the probability to two IP addresses being mapped to the same bucket be using the second hashing function?

# Answer
Your question is a bit confusing. These two "hashes" are incomparable.

The reason is that your second function is a **specific hash function**, while the first formulation is a **family of hash functions** (indexed by $a$).

How can you compare the two? Choose $a$ in random and compare the two instances? Compare for the best/worst $a$, maybe? Compare on average (for a uniform $a$)?

**Remark**: *Just to complete the details: Usually (at least, within the crypto-community), when people say "hash function" they actually mean a family of hash function, out of which you pick one instance uniformly. The properties of the hash function is (also) over the probability of selecting the specific function out of the family*

---

As for your other question, the answer is no, in the second hash, the probability is not equal $1/n$ to be in each bucket. Assume that each $x\_i$ is uniform in \[0..255\], then $x\_1+x\_2$ is **not** uniform in \[0..510\]. For instance $P(0)=1/256^2$ (both are 0) while $P(4) = P(0,4) + P(1,3) + P(2,2) + P(3,1) + P(4,0) = 5/256^2$. There's no reason that the sum will be uniform $\mod n$.

Last comment: As explained above, for the first hash, a probability of $1/n$ is over the choice of $a$.
> 2 votes

---
Tags: hash-tables, hash
---


title: Tensor Product in Quantum Computation

text:
# Question
Title: Tensor Product in Quantum Computation
I can not understand the following equality $$\langle ij|(|0\rangle \langle 0|\otimes I)kl \rangle= \langle i|0\rangle \langle 0|k \rangle \langle j|I|l \rangle?$$

Also to estimate phase $\phi$ in Nielsen & Chuang book, I can not understand why $(|0 \rangle + e^{2\pi i 2^{t-1}\phi} |1 \rangle)(|0 \rangle + e^{2\pi i2^{t-2}\phi }|1 \rangle)\cdots (|0 \rangle + e^{2\pi i 2^{0}\phi} |1 \rangle)= \displaystyle\sum\_{k=0}^{2^t-1}e^{2\pi i \phi^k} |k\rangle$.

Will you kindly help me?

# Answer
> 10 votes
A tensor product of operations, $I\otimes J$ say, acts on each subsystem separately: if $\phi$ and $\psi$ are states and $I$ and $J$ are operators then $$(I\otimes J)(\phi\otimes \psi) = (I\phi) \otimes (J\psi)$$ In bra-ket notation the state $\phi\otimes \psi$ can be denoted $|\phi\rangle|\psi\rangle$. In your first equation, the $\langle i|0\rangle\langle 0|k\rangle$ factor and $\langle j|I|l\rangle$ factor just separate in this way.

The algebra behind the second equation is basically: $$(1+x^{2^0})\dots(1+x^{2^{t-1}})=1+x+x^2+x^2+\dots+x^{2^t-1}$$ except that the "1" is replaced by $| 0\rangle$, and the $x$ is replaced by $\exp(2\pi i \phi |1\rangle)$ (clash of my notation: $\phi$ is now a number). The only difference is that the multiplication is really a tensor product, and with bosons $|1\rangle\otimes |1\rangle=|2\rangle$.

---
Tags: quantum-computing
---


# Question
Title: Algorithmic consequences of algebraic formula for partition function?
Bruinier and Ono have found an algebraic formula for the partition function, which was widely reported to be a breakthrough. I am unable to understand the paper, but does it have any algorithmic consequences for fast computation of the partition function?

# Answer
> 5 votes
It is my uninformed belief that Rademacher's formula is faster in practice (and perhaps in theory also) than the Bruinier and Ono formula. While Rademacher's asymptotic expansion is an infinite sum, we know that $p(n)$ is an integer, so if we have bounds on the tails of the expansion, we can use the formula to compute $p(n)$. According to Calkin et al., "the exact formula of Rademacher yields a very fast algorithm".

Bruinier and Ono describe what would take to implement their algorithm in Section 5 of their paper. The first step is to determine representatives for $\mathcal{Q}\_n$, of which there are $h(-24n+1)$. According to Soundararajan, we should expect $h(-24n+1) = \Theta(n)$, so the formula would involve $\Theta(n)$ summands. That makes it worse than Euler's formula for $p(n)$ (computationally speaking), though the latter admittedly requires $\Omega(n)$ memory.

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


# Question
Title: Computing the rank of a multiset after inserting another element
What is the procedure for computing the rank of a multiset after inserting an element?

For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements.

The multiset $M = (1,1)$ has rank $5$ because there are $4$ multisets less than it based on lexicographic ordering: $(0), (1), (0,0), (0,1)$.

If we insert $0$, we get $(0,1,1)$ which has rank $8$. If $1$ were inserted instead we'd have $(1,1,1)$ with rank $9$.

Is there a function $f(r,x,n)$ which takes a rank $r$, an element $x$, and $n$, and returns the new rank after inserting $x$?

# Answer
I'll consider the easy $|S|=2$ case. There are $n+1$ multisets of size $n$, and so the rank of the multiset $0^{n-k} 1^k$ is $$ r(n,k) = \sum\_{m=0}^{n-1} (m+1) + k = \frac{n(n+1)}{2} + k. $$ What happens when adding an element? Adding $0$ and $1$, respectively, correspond to $r(n+1,k)$ and $r(n+1,k+1)$. We have $$ \begin{align\*} r(n+1,k) &= \frac{(n+1)(n+2)}{2} + k = n + 1 + \frac{n(n+1)}{2} + k = n+1 + r(n,k), \\ r(n+1,k+1) &= r(n+1,k)+1 = n+1 + r(n,k) + 1. \end{align\*} $$ Therefore the function you want is $$ f(r,x,n) = r + n+1 + x. $$ Here $n$ is the size of the old multiset, rather than the number of elements. For example, the rank of $(1,1)$ is $5$, and $f(5,0,2) = 5 + 3 + 0 = 8$, $f(5,1,2) = 5 + 3 + 1 = 9$.
> 4 votes

---
Tags: algorithms, combinatorics, sets, binary-arithmetic
---


# Question
Title: Line smoothing algorithm that perserve data uniformity
Intro:

I'm working with huge data set that i need to plot in browser, and since there may be up to 1M points my idea was to create different representations for different zoom levels

lets say i have 100k points, i would average two-by-two until i get 50k, then i would repeat that until i get below 500 points (my arbitrary threshold)

so on the most zoomed-out level i would draw all 500 points, or part of it, depending of the chart size, and as i zoom in, i would switch to next zoom level (and stream data if user drags selection l/r), and ultimately if user wants to see fine grain details he can zoom to 0 zoom level and see all the fine details.

I actually created this prototype, and its working quite well, except for one thing: side-effect of this is, as you can imagine, that peaks are lost in those iterations of averaging.

I did some research and find about Douglas-Peucker algorithm, and how it can perserve peaks, i did some tests, and it works quite well, but the problem with that is that if it encounters a series of data (y values) \[1,1,1,1,5,6,1,1,1,1,1,1\] it will smooth that to something like \[1,6,1,1\] which doesn't work for me since i need to keep ratio of zoom levels like this

n (length of original data) \> n/2 \> n/4 \> n/8 \> .....

I read quite few papers on line smoothing, but all algorithms that i found are accepting distance threshold, that they use for smoothing as a parameter, and none of those can accept number of desired output elements, and also, since their goal is to smooth the line, they will transform sequence like this (y values) \[1,1,1,1,1,1,1,1,1,1,1\] into \[1,1\]

So, finally, my question:

Is there an algoritm that:

* instead of usual distance threshold accepts the desired number of output elements
* tries to perserve peaks (as Douglas-Peucker does)
* will smooth data uniformly, so even if it gets (y values) \[1,1,1,1,1,1\] and i say i want 3 outputs, event if it IS in theory correct to smooth as \[1,1\] i would need to get \[1,1,1\] instead

Also, please don't be confused by lack of X axis information because it is irrelevant since all data are measured from 1 to n in steps of 1, so there are no N/A values, or blank spots, or values like \[1.3,1.4,3\]

x is always \[1,2,3....n\]

# Answer
Here are two suggestions for you to try.

*Suggestion 1:* Use a linear filter. Instead of computing the average $x\_{2n},x\_{2n+1} \mapsto (x\_{2n}+x\_{2n+1})/2$, try averaging over a larger sequence, e.g. $y\_n = (x\_{2n-1}+2x\_{2n}+2x\_{2n+1}+x\_{2n+2})/6$.

*Suggestion 2:* Use a conditional filter: if $x\_{2n} \< x\_{2n+1} \> x\_{2n+2}$ or $x\_{2n-1} \< x\_{2n} \> x\_{2n+1}$, then let $y = x\_{2n+1}$ or $y = x\_{2n}$, respectively, and similarly for local minima; otherwise use the average (or a linear filter) as before.
> 1 votes

---
Tags: computational-geometry, approximation, graphics
---


# Question
Title: Can you have three consecutive black nodes in red-black search tree?
Suppose I am making a red-black search tree, and in my right subtree, I have a black node, then a red node, and it has two black children, the black children further black childrens. As such a lemma has been made that red-black trees with $n$ internal nodes have height at most $2\log(n+1)$, would this proof still hold for such a black tree?

# Answer
> 6 votes
In fact, a red-black tree can have all black nodes. In that case the tree is completely balanced and has the required bound.

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


# Question
Title: How does this recurrence relation fit the algorithm?
I have the following pseudo code:

```
Multiply(y,z)
1. if (z==0) return 0
2. else if (z is odd)
3.    then return (Multiply(2y, floor(z/2)) + y )
4. else return (Multiply(2y, floor(z/2)))

```

Towards analysing this procedure's runtime, this recurrence relation is given as answer:

$\qquad \displaystyle T(z) = \begin{cases} 0 & z=0 \\ T(z/2)+1 & z\>0\end{cases}$

Why is $T(z)=0$ when $z=0$? Shouldn't it be $1$ for this case?

And, the $+1$ in $T(z/2)\mathbf{+1}$ is because the worst case is `(multiply(2y, floor(z/2)) + y` (note the `+ y`). Am I correct?

# Answer
You should be careful about what is being counted. If you want to count "runtime" (as in, number of statements) the given recurrence is clearly wrong.

Reverse-engineering from the recurrence, it is probably supposed to count *additions*. In particular, note how the computation the parameters for recursive calls is ignored. I hope it is clear that the recurrence is correct for the worst-case then; your reasoning for $+1$ is spot-on.

Why does restricting your self to additions make sense here? Additions are one of the statements that are executed *most often* (in the worst case, that is ignoring line 4.). That means that the true runtime (in a theoretic model) is *proportional* to the number of additions. Since you are (most likely) after *asymptotics* in terms of $O$, counting additions is sufficient: the proportion-constant is lost in $O$, anyway.

You can, for the fun of it, set up a recurrence counting all statements. You'll see that the result has the same asymptotic growth as the one you were given.
> 4 votes

# Answer
There's a bit of ambiguity in what you're looking for here. I am going to assume it's the running time of the function.

I agree that it should be 1 when $z=0$ because it generally is considered to take $O(1)$ operations to return a function value. However, this will only affect your final answer by an additive constant of 1.

The $+1$ factor in the recurrence $T(z) = T(z/2) + 1$ is caused by the overhead of calling the subfunction.

In other words, what happens at a given value of $z$ is:

The function is called (generally $O(1)$ work just to set up the stack, etc.)

The program tests whether $z$ is odd ($O(1)$ work)

The function calls itself with a smaller instance ($T(z/2)$ work), and then does an addition before returning ($O(1)$ work).

Add these up, and you get $T(z) = T(z/2) + O(1)$. You can substitute $1$ instead of $O(1)$ in this case and you'll get the same answer so long as you're only worried about asymptotics.
> 2 votes

---
Tags: time-complexity, algorithm-analysis, asymptotics, recurrence-relation
---


# Question
Title: Proof that a randomly built binary search tree has logarithmic height
How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS *Introduction to Algorithms* (chapter 12.4), but I don't understand it.

# Answer
> 27 votes
Let's first think about this intuitively. In the best-case scenario, the tree is perfectly balanced; in the worst-case scenario, the tree is entirely unbalanced:

Starting from the root node $p$, this left tree has twice as many nodes at each succeeding depth, such that the tree has $n=\sum\_{i=0}^{h}2^i =2^{h+1}-1$ nodes and a height $h$ (which is in this case 3). With a little math, $n\le2^{h+1}-1\rightarrow h\le\lceil\log\_2(n+1)-1\rceil\le\lfloor log\_2 n\rfloor$, which is to say it has $O(\log n)$ height. For the entirely unbalanced tree, the height of tree is simply $n-1\rightarrow O(n)$. So we have our bounds.

If we were constructing a balanced tree from an ordered list $\\{ 1,2,\dots,n\\}$, we'd choose the middle element to be our root node. If we are instead randomly constructing a tree, any of the $n$ nodes are equally likely to be picked and the height of our tree is: $$height\_{tree}=1+\max (height\_{left\space subtree}, height\_{right\space subtree})$$ We know that in a binary search tree, the left subtree must only contain keys less than the root node. Thus, if we randomly choose the $i^{th}$ element, the left subtree has $i-1$ elements and the right subtree has $n-i$ elements, so more compactly: $h\_n=1+\max (h\_{i-1},h\_{n-i})$. From there, it makes sense that if each element is equally likely to be picked, the expected value is just the average of all cases (rather than a weighted average). Hence: $\operatorname{E}\[h\_n\]=\frac{1}{n}\sum\_{i=1}^{n}\[1+\max (h\_{i-1},h\_{n-i})\]$

As I'm sure you've noticed, I've deviated slightly from how CLRS proves this, because CLRS uses two relatively common proof techniques that are disconcerting for the uninitiated. The first is to use exponents (or logarithms) of what we want to find (in this case height), which makes the math work out a little more cleanly; the second is to use indicator functions (which I'm just going to ignore here). CLRS defines the *exponential height* as $Y\_n=2^{h\_n}$, so the analogous recurrence is $Y\_n=2\times\max (Y\_{i-1},Y\_{n-i})$.

Assuming independence (that each draw of an element (out of the available elements) to be the root of a subtree is irrespective of all previous draws), we still have the relation: $$\operatorname{E}\[Y\_n\]=\sum\_{i=1}^{n}\frac{1}{n}\operatorname{E}\[2\times\max (Y\_{i-1},Y\_{n-i})\]=\frac{2}{n}\sum\_{i=1}^{n}\operatorname{E}\[\max (Y\_{i-1},Y\_{n-i})\]$$ for which I did two steps: (1) moving the $\frac{1}{n}$ outside because it is a constant and one of the properties of summations is that $\sum\_i ci=c\sum\_i i$, and (2) moving the 2 outside because it is also a constant and one of the properties of expected values is $\operatorname{E}\[ax\]=a\operatorname{E}\[x\]$. Now we're going to replace the $\max$ function with something larger because otherwise simplifying is difficult. If we argue for nonnegative $X$, $Y$: $\operatorname{E}\[\max(X,Y)\]\le\operatorname{E}\[\max(X,Y)+\min(X,Y)\]=\operatorname{E}\[X\]+\operatorname{E}\[Y\]$, then: $$\operatorname{E}\[Y\_n\]\le\frac{2}{n}\sum\_{i=1}^{n}(\operatorname{E}\[Y\_{i-1}\]+\operatorname{E}\[Y\_{n-i}\])=\frac{2}{n}\sum\_{i=0}^{n-1}2\operatorname{E}\[Y\_{i}\]$$ such that the last step follows from the observation that for $i=1$, $Y\_{i-1}=Y\_{0}$ and $Y\_{n-i}=Y\_{n-1}$ and going all the way to $i=n$, $Y\_{i-1}=Y\_{n-1}$ and $Y\_{n-i}=Y\_{0}$, so every term $Y\_0$ to $Y\_{n-1}$ appears twice, so we can replace the entire summation with an analogous one. The good news is that we have a recurrence $\operatorname{E}\[Y\_n\]\le\frac{4}{n}\sum\_{i=0}^{n-1}\operatorname{E}\[Y\_{i}\]$; the bad news, is that we're not much further than where we started.

At this point, CLRS pulls an induction proof $\operatorname{E}\[Y\_n\]\le\frac{1}{4}\binom{n+3}{3}$ out of their ... repertoire of mathematical experience, one that includes an identity $\sum\_{i=0}^{n-1}\binom{i+3}{3}=\binom{n+3}{4}$ they leave to the user to prove. What's important about their choice is that its largest term is $n^3$, and recall that we are using exponential height $Y\_n=2^{h\_n}$ such that $h\_n=\log\_2n^3=3\log\_2n\rightarrow O(\log n)$. Perhaps someone will comment why this particular binomial was chosen. The general idea though is to bound from above our recurrence with an expression $n^k$ for some constant $k$.

To conclude with a one liner: $$2^{\operatorname{E}\[X\_n\]}\le \operatorname{E}\[Y\_n\]\le \frac{4}{n}\sum\_{i=0}^{n-1}\operatorname{E}\[Y\_i\]\le\frac{1}{4}\binom{n+3}{3}=\frac{(n+3)(n+2)(n+1)}{24}\rightarrow \operatorname{E}\[h\_n\]=O(\log n) $$

---
Tags: data-structures, algorithm-analysis, binary-trees, search-trees, average-case
---


# Question
Title: Are there grammar classes between Chomsky level 1 and 2?
Are there any grammar classes which are true subsets of Chomsky level 2 but not equal to level 1?

# Answer
> 4 votes
I know I'm pretty late, but oh well.

There's a class of grammars known as indexed grammars (describing indexed languages, which are a proper subset of CS languages and a superset of CF languages). The rules look very much like the ones in a CF grammar, but every LHS nonterminal has an associated stack of *index symbols*, and when rewriting that nonterminal, the stack can be manipulated by other nonterminals in the RHS. For example:

$A\[\sigma\] \rightarrow B\[\sigma x\] C\[\sigma y\]$

which means "rewrite nonterminal A to nonterminals B and C, copy the stack and push x to B's stack and y to C's stack" or

$A\[\sigma x\] \rightarrow B\[\sigma\]$

meaning "if there's an A with x on top of its stack, rewrite it to B and pop that x off the B's stack".

Some examples of indexed languages are $\left\\{ a^n b^n c^n d^n | n \geq 1 \right\\}$ or $\left\\{ www | w \in \left\\{ a, b \right\\}^+ \right\\}$.

As for the automaton, indexed languages are exactly the class of formal languages recognizable by a nondeterministic nested-stack automaton, which is basically a NPDA in which some elements of the stack may be other stacks.

Concerning practical use, wikipedia says that indexed grammars sometimes find use as affordably processable descriptors of natural languages.

**Edit**: As Raphael mentioned, indexed languages | grammars are closely related to mildly context-sensitive languages.

There's a class of grammars similar to indexed grammars called *linear indexed grammars*. While in an IG, *every* nonterminal in the RHS recieves a copy of the LHS's stack, LIGs require that *at most one* nonterminal in the RHS recieves the stack. Given that any LIG can be transformed into an equivalent IG, they're strictly less powerful and it has been shown that the set of languages they generate is equivalent to the set of mildly context-sensitive languages.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Will this algorithm terminate on any input?
One can compress data with straight-line grammars. An algorithm that employs this technique is called *Sequitur*. If I understood correctly, Sequitur basically starts with one rule representing the input and then does these three steps till the grammar does not change anymore:

1. For each rule, try to find any sequences of symbols in any other rule that match the rule's right hand side and replace these sequences by the rules left hand side.
2. For each pair of adjacent symbols in any right hand side, find all non-overlapping other pairs of adjacent symbols that are equal to the original pair. If there are any other pairs, add a new nonterminal, replace all occurrences of these pairs by the new nonterminal and add a new rule that defines the nonterminal.
3. For each nonterminal that appears exactly once on all right-hand sides of all rules, replace its occurrence by its definition, remove the nonterminal and the rule that defines it.

For each (non-empty) input, can one guarantee that the above algorithm terminates?

# Answer
This is my idea for a proof although I am not quite sure whether it works:

Consider $r$, the number of symbols on all right-hand sides and $n$, the number of distinct nonterminals. Each grammar has a specific tuple $(r-n,n)$. Let's define an order on grammars. We first sort by $r-n$ and in case the values are equal by $n$.

Whenever step one fires, $r$ decreases as each rule has at least two symbols on its right hand side. Whenever step two fires, $n$ increases by one and $r$ stays the same (in case only two pairs are found) or decreases (if two or more pairs are found). If the third step fires, $r$ decreases by one and $n$ also decreases by one as one nonterminal is replaced by the whole right hand side of its definition which is removed. Let $G'$ be the tuple of the grammar (whose tuple is $G$) after the application of any of those steps, then:

* step 1 always reduces $r-n$ by at least one, $G' \< G$
* step 2 always reduces $r-n$ by at least one, $G' \< G$
* step 3 does not change $r-n$ but reduces $n$ by one, $G' \< G$

The application of each step reduces the tuple of $G$ to a lower tuple. What is left is to show, that both $r-n$ and $n$ have a lower bound. Per definition $n\ge1$. Since each nonterminal is defined in terms of exactly one rule, $n$ is also the number of rules. Since each rule has at least two symbols on it's right-hand side, $r\ge2n\to r\>n\to r-n\>0$. The tuples have a lower bound that is eventually reached. Thus the algorithm must eventually terminate.
> 2 votes

---
Tags: algorithms, algorithm-analysis, formal-grammars, data-compression, correctness-proof
---


title: Lower bound for Convex hull

text:
# Question
Title: Lower bound for Convex hull
By making use of the fact that sorting $n$ numbers requires $\Omega(n \log n)$ steps for any optimal algorithm (which uses 'comparison' for sorting), how can I prove that finding the convex-hull of $n$ points is bounded by $\Omega (n \log n)$ steps?

# Answer
If you could create the convex-hull in $o(n \log n)$ time, this would imply, that you can sort $n$ numbers in $o(n\log n)$ time.

You do this with contradiction. You have $n$ numbers $(x\_1, x\_2, \ldots, x\_n)$, which you would like to sort. From these numbers, you create points $P$ in 2D space in some fashion. For example $p\_i=(x\_i,x\_i^2)$.

On these newly constructed points $P$ you call the algorithm for convex hull, which returns you the actual convex hull.

After that, you simultaneously traverse upper and lower hull, from the lower left-most point in (which you find in $O(n)$ time), to the upper right-most point. With this traversal you actually sort the numbers. Let $p\_i$ and $p\_j$ be the next points on lower and upper hull, then if $x\_i\<x\_j$, you move one step ahead on the lower hull and add $x\_i$ to the end of the sorted array (else you take one step ahead on the upper hull and add $x\_j$ to the array). You then finish when the traversals meet in the upper right-most point of the convex hull.

The algorithm that I described is run in $O(n)$ time. So if the convex-hull algorithm would be $o(n\log n)$, the sorting of $n$ numbers could be also done in $o(n\log n)$ time, which is a contradiction since we know that sorting $n$ numbers takes at least $\Omega(n \log n)$ time.
> 6 votes

---
Tags: complexity-theory, computational-geometry, lower-bounds
---


title: Proving DOUBLE-SAT is NP-complete

text:
# Question
Title: Proving DOUBLE-SAT is NP-complete
The well known SAT problem is defined here for reference sake.

The DOUBLE-SAT problem is defined as

$\qquad \mathsf{DOUBLE\text{-}SAT} = \\{\langle\phi\rangle \mid \phi \text{ has at least two satisfying assignments}\\}$

How do we prove it to be NP-complete?

More than one way to prove will be appreciated.

# Answer
Here is one solution:

Clearly Double-SAT belongs to ${\sf NP}$, since a NTM can decide Double-SAT as follows: On a Boolean input formula $\phi(x\_1,\ldots,x\_n)$, nondeterministically guess 2 assignments and verify whether both satisfy $\phi$.

To show that Double-SAT is ${\sf NP}$-Complete, we give a reduction from SAT to Double-SAT, as follows:

On input $\phi(x\_1,\ldots,x\_n)$:

1. Introduce a new variable $y$.
2. Output formula $\phi'(x\_1,\ldots,x\_n, y) = \phi(x\_1,\ldots,x\_n) \wedge (y \vee \bar y)$.

If $\phi (x\_1,\ldots,x\_n)$ belongs to SAT, then $\phi$ has at least 1 satisfying assignment, and therefore $\phi'(x\_1,\ldots,x\_n, y)$ has at least 2 satisfying assignments as we can satisfy the new clause ($y \vee \bar y$) by assigning either $y = 1$ or $y = 0$ to the new variable $y$, so $\phi'$($x\_1$, ... ,$x\_n$, $y$) $\in$ Double-SAT.

On the other hand, if $\phi(x\_1,\ldots,x\_n)\notin \text{SAT}$, then clearly $\phi' (x\_1,\ldots,x\_n, y) = \phi (x\_1,\ldots,x\_n) \wedge (y \vee \bar y)$ has no satisfying assignment either, so $\phi'(x\_1,\ldots,x\_n,y) \notin \text{Double-SAT}$.

Therefore, $\text{SAT} \leq\_p \text{Double-SAT}$, and hence Double-SAT is ${\sf NP}$-Complete.
> 34 votes

# Answer
You know that $\mathsf{SAT}$ is NP-complete. Can you find a reduction from $\mathsf{SAT}$ to $\mathsf{DOUBLE\text{-}SAT}$? That is, can you manipulate a satisfiable formula so that the result has at least two satisfying assignments? Note that the same manipulation can not render unsatisiable formulae satisfiable.

> For any formula $\varphi$, the formula $\varphi \lor f(\varphi)$ has at least twice the number of satisfying assingments as $\varphi$, with $f$ a homomorphism that renames all variables to new names.
> 12 votes

---
Tags: complexity-theory, np-complete, satisfiability
---


# Question
Title: Is the clique problem NP-complete also on bipartite or planar graphs?
We know that the clique problem is NP-complete. Is the restriction of the problem to bipartite graphs or planar graphs still NP-complete?

# Answer
In a bipartite graph there can be no clique of size three. Not much of a problem that is left I guess?

(edit) Sorry, that was too fast, I realize thanks to comment by Nicholas below. To make up for it I googled a reference.

The maximum edge biclique problem is NP-complete by Ren\*e Peeters. Discrete Applied Mathematics 131 (2003) 651 – 654

(ps) So I understand that *my* answer relates to a question that changes the types of graphs we are looking for, kind of bipartite cliques, whereas the other answer restricts the set of graphs we are looking in to planar. In planar graphs cliques can have size at most four, thanks to Kuratowski.
> 6 votes

# Answer
For planar graphs, the problem is in $\mathsf{P}$. This follows already from Kuratowski's theorem: a clique is at most of size 4. The naive algorithm can just check every combination.

For a more clever algorithm, see Norishige Chiba and Takao Nishizeki, Arboricity and Subgraph Listing Algorithms, SIAM Journal on Computing 14(1): 210–223, 1985.
> 4 votes

---
Tags: complexity-theory, graphs, np-complete
---


# Question
Title: References on comparison between quantum computers and Turing machines
I was told that quantum computers are not computationally more powerful than Turing machines. Could someone kindly help in giving some literature references explaining that fact?

# Answer
What is actually the case is that anything a quantum computer can compute, a Turing machine can also compute. (This is without commenting at all on how *long* it takes the Turing machine to compute the function compared to a quantum computer.)

This is actually not difficult to see, provided you understand quantum computation. For a quantum circuit over a typical gate set, for example, the outcome is governed by a probability distribution, which is determined by the coefficients of a unitary matrix. That unitary matrix is just a matrix product of those of the gates, and can be computed — if you're patient enough — by a classical computer. So for sheer computability (as opposed to efficiency), there is no advantage to using quantum computers.

The whole challenge arising from quantum mechanics is to determine whether such coefficients can be computed *efficiently*, which is a more demanding problem than whether they can be computed *at all*.
> 10 votes

# Answer
Consider a quantum gate. Smoothing out all the technical details, it can be represented as a matrix $G$. An input to the gate, say $\vert \phi \rangle$ is just a vector $v$, and the output of the gate is the vector $Gv$.

Now, consider a circuit. A circuit is just a bunch of gates $\\{G\_1, G\_2, ... \\}$, and the circuit itself can be seen as a "generalized gate" $C=G\_n \cdots G\_2 G\_1$, which operates on the input state (the vector $v$).
*\[Again, this is a very coarse abstraction.\]*

So basically, computing a circuit on an input $\vert \phi \rangle$, is merely computing the vector $Cv$ or $ G\_n \cdots G\_2 G\_1 v$. It's clear that such a task (matrix multiplication and multiplication of matrix by vector) can be done by a classical TM, therefore, TM is at least as strong as a quantum-TM (QTM)
*\[ok, classical circuits are as strong as quantum circuits. nevermind that.\]*

On the other hand QTM is trivially as strong as TM, and therefore, both models are equivalent.

---

**EDIT due to comments**
In order to ask which "computer" is more powerful, we need to first clarify what it means to be more "computationally powerful". And this semi-philosophical discussion begins with the question

> **What is computation**?

Is "playing MP3" files a computation? Is outputting random numbers a computation?

The standard definition says that a computation is "computing a function". That is, for every input $x$ (which can be any string of any finite length), output $y=f(x)$, where again $y$ can be a string of arbitrary (finite) length. If your computer can output $y$ for any $x$, we say that *it can compute $f$*.

Now, to say that computer "A" is more powerful than "B" just means that A computes more functions $f$ than $B$. Similarly,

> Two models, $A$ and $B$ are considered **equivalent** if, for any function $f$, $A$ computes $f$ if and only if $B$ computes $f$.

OK, you say, but wait a second, there is randomization.. A quantum computer does not just output $y$. It outputs $y\_1$ with probability $p\_1$, or $y\_2$ with probability $p\_2$, or ....$^0$

Indeed.. And this extends the standard definition of computing a function. We can resolve it, and generalize our definitions in several ways. (1) one option is to say that the answer of $f(x)$ is that specific $y\_i$ that has probability $p\_i\>0.75$ (and there is at most one such value)$^1$. If we Assume that $f$ outputs only a single bit, then "the output of $f(x)$ is always well defined$^2$. Otherwise, if no such value exists, and all the outputs have small probability we can say $f$ is not defined on that input; (2) A second option is to say that the output of $f(x)$ is the list $(y\_1,p\_1), (y\_2,p\_2),...$. For this to be well defined, we must have a finite list, since we required the output string to be finite.

With the above, it should be clear that having probabilities doesn't change the power of the model, and a classical TM can just output the list of possible outputs along with the probability for each output. *this is exactly what happens* when a TM multiplies matrices and outputs a vector — the vector represents the probability of each and every possible measurement output.

<sup> $^0$This issue is not unique to quantum computing. Classical probabilistic computing "suffers" from the same issue.
$^1$Why $p=0.75$? No reason. Any constant larger than $1/2$ would work.
$^2$Why assuming $f$ outputs one bit? because it is enough.. We can reduce any more complex function to one or more functions with a single-bit output. But this doesn't matter to our discussion. </sup>
> 10 votes

# Answer
other answers are valid, just want to add one that emphasizes this is really a very deep (largely still open/unresolved) question at the heart of much modern research into complexity class separations and quantum vs classical computing. they are *functionally* equivalent as far as TMs and QM computers are both proven Turing complete; there are several ways to prove this.

but equivalence in complexity theory very much hinges on time and space subtleties/efficiencies ie resources to compute particular algorithms. and theres also a huge amount of research looking at "noise" in QM computing that considers that theoretical noiseless models may not be "real" or achievable in practice and real models may/will have significant noise. there are complex schemes to mitigate this noise, etc.; there is some excellent commentary on this in various posts in RJ Liptons blog eg flying machines of the 21st century

for example it has been proven that factoring is in BQP, the class of quantum algorithms that run in P time, by Shor in a famous proof that at the time also launched a large amount of serious study/reseach into QM computing because of the dramatic result.

however even with "noiseless" QM models its an open question whether P $\stackrel{?}{=}$ BQP where the former denotes a classical complexity class of efficient Poly-time algorithms and BQP is the class of efficient/Poly-time QM algorithms. and there are various similar open questions.

Scott Aaronson is an excellent writer/researcher on the subj and has written some papers accessable to the layman. see eg The limits of QM computers, SciAm or QM computing promises new insights, NYT.
> 1 votes

---
Tags: computability, reference-request, turing-machines, quantum-computing
---


# Question
Title: Can you have a binary search tree with O(logn + M) property for the following case
Let $n$ be the number of strings which are sorted in lexicographical order and stored in a balanced binary search tree. You are provided with a prefix $x$ of which $M$ strings have the prefix $x$. I have devised the following algorithm, where I search until I find the first occurence of the prefix $x$ in one of the nodes. After that I run an inorder traversal on it, such that I print only the ones, that have prefix $x$ and are in order.

For example of sorted strings: $\[ACT,BAT,CAT,CAB\]$ and the prefix $x = CA$, I would print $CAT$ and $CAB$.

# Answer
> 1 votes
The data structure you are looking for is called a range tree. Range trees are usually used for geometric data, but they can be used here as well. In 1d, a range tree is simply a balanced binary search tree with the data stored at the leaves and the internal nodes augmented with the min and max element stored in the subtree. They have running time $O(\log n+ k) $ where $n$ is the total number of objects in the tree and $k$ is the number of objects reported. You will have to structure your queries slightly differently to use a range instead if a prefix. So add a special min and max character to your alphabet, call them 0 and 1 for convenience. Now to find all strings with prefix "CA", " you would search for all strings in the range (CA0, CA1).

As noted in the comments above, a trie is the structure one would normally use for this type or query. But the computational model used is slightly different, so it's hard to compare. The running time would be the length of your longest output string + k.

---
Tags: binary-trees, search-trees
---


# Question
Title: What is the time complexity of calling successor $n$ times during tree traversal?
According to some sources, the time complexity of finding the successor of a node in a tree is $O(h)$. So, if the tree is well balanced, the height $h=\log n$, and the successor function takes time $O(\log n)$. Yet, according to this stackoverflow post on the time complexity of an inorder traversal of a binary search tree, if you call the successor function $n$ times, the time complexity is $O(n)$.

What resolves the apparent contradiction between:

> If I call the sucessor function once, the time complexity is $O(h)$, which could be $O(n)$ or $O(\log n)$, depending on the kind of tree.

AND

> If I call the successor $n$ times, the time complexity is $O(n)$ in a balanced tree.

Shouldn't tree traversal take $O(n^2)$ or $O(n\log n)$ time?

# Answer
Gist: **The time complexity of calling the sucessor function multiple times is not merely the product of the number of calls and the worst-case bound**, though that product does encompass the worst case. Rather, if the function going to be called from every node, a more sophisticated analysis can establish a tighter worst-case bound for specific trees and implementations of the successor function.

At best, tree traversal takes at $O(n)$ time: $n-1$ calls are made to the successor function, which takes constant time. One simple example of this is the traversal of a linked list, which has a successor function that immediately returns a pointer to the next node with no additional computation.

The worst "reasonable" tree traversal would take $O(n^2)$ time: $n-1$ calls are made to the successor function, which searches all $n$ nodes before determining the successor. For example, if we have an unsorted tree and the successor is defined to be the next largest element (rather than based on its position in the tree). Of course, we could sort the tree first in time $O(n\log n)$ and in general, if we expect to call the successor function $n$ times, it would be wise to preprocess the tree so that it can be traversed in one of the three canonical ways: inorder, preorder, or postorder.

Ok, time to clear a misconception! Let's ask what's the best-case and worst-case scenarios for the successor function are when we have an inorder traversal of a binary search tree:

Remember that in inorder traversal, the left subtree is visited, then the parent node, then the right subtree. So an inorder traversal on the above tree gives us $\[A,B,C,D,E,F,G,H,I\]$. (For contrast, preorder traversal would have given us $\[F,B,A,D,C,E,G,I,H\]$). We start at the beginning of the tree at $A$. From $A$, the successor function checks to see that it has no right subtree (it doesn't) before finding its closest ancestor for which it is the descendant of the left child. But wait! I didn't tell you that each node had knowledge of its ancestors, so we potentially have to search the entire tree just to determine where $A$ is! So now we split into two cases:

* *Worst-case*: Assuming that our node has no right subtree, if the tree was a binary search tree, we could find the node in $O(\log n)$ time. But worst-case, it's not a binary search tree; in fact, it has no structure, so every call takes $O(n)$ time, but if we're consistent about how we search, the total number of steps to find the node's successor is at least $\sum\_{x=1}^{n}x=\frac{(n)(n+1)}{2}=O(n^2)$.
* *Best-case*: Each node has a link to its ancestor, so from $A$ to $B$ takes two steps (check for right subtree; back up to ancestor for which it is the left child). The successor function that takes the most steps is from $E$ to $F$, for which $E$ first checks that it has no right subtree, then checks to see if it is the left child of $D$ (it isn't), or the descendent of the left child of $B$ (it isn't), and finally if it is the descendent of the left child of $F$ (it is). That took $O(h)=O(\log n)$ steps, but most calls to the function won't take that many steps. Quoting the SO post, "observe that each edge in the tree gets visited at most twice (once from parent to child and once from child to the parent)" so the total number of nodes visited is $2n$ and hence $O(n)$ worst-case bound.

Another way to appreciate that the average call to successor is $\<\log(n)$ is to consider a balanced tree with $n$ nodes and roughly $n/2$ leaves. Half of all successor function calls will be to an ancestor, half of which are from the left child ($\frac{1}{4}n$) and thus takes only one generation/step, $\frac{1}{8}n$ go back two generations, $\frac{1}{16}n$ go back three. Hopefully you see the pattern: $\sum\_{i=1}\frac{i}{2^{i+1}}$ converges to $1$. And the other half does the step-analogous $\min$ function (searching it's right subtree for the leftest child), so it also converges to $1$. The expected time is thus $2$ (if I've done my math carefully). So that's $n-1$ calls to a successor function that on average takes ~$2$ steps $\rightarrow O(n)$ time.
> 5 votes

---
Tags: binary-trees, search-trees
---


# Question
Title: Graph Closeness - Different result with gephi and NodeXL
I'm writing a JavaScript library for calculating graph measurements such as degree centrality, eccentrality, closeness and betweenness.

In order to validate my library I use two exist applications Gephi and NodeXL to run calculation with them. The problem is I got what looks like different results.

I build simple graph:

```
  (A) ----- (B)
   |         |
   |         |
  (C) ----- (D)

```

Gephi gave those results:

```
A ecc=2 close=1.333 bet=0.5
B ecc=2 close=1.333 bet=0.5
C ecc=2 close=1.333 bet=0.5
D ecc=2 close=1.333 bet=0.5

```

NodeXL gave those results:

```
A close=0.25 bet=0.5
B close=0.25 bet=0.5
C close=0.25 bet=0.5
D close=0.25 bet=0.5

```

Note that NodeXL does not calculate eccentrality.

Which one is right?
Are the results really different?

I didn't normalize (or at least not intend to normalize) any results.

# Answer
The **closeness** of a node in a graph is defined as the reciprocal of the sum of all distances to other nodes.

Since your example is completely symmetric, we only calculate the closeness centrality of $A$.

* distance $A\to B$ is 1
* distance $A\to C$ is 1
* distance $A\to D$ is 2

Therefore the sum of the distances is 4, and the closeness of $A$ is $1/4$. This shows that the NodeXL results are correct. I would advise you to have a look at the manual of Gephi to check how the closeness is computed here. It should be definitely be smaller than 1.
> 3 votes

---
Tags: graphs, terminology
---


# Question
Title: Multitape Turing machines against single tape Turing machines
*Introduction*: I recently learned that a multi-tape Turing Machine $\text{TM}\_k$ is no more "powerful" than a single tape Turing machine $\text{TM}$. The proof that $\text{TM}\_k \equiv \text{TM}$ is based on the idea that a $\text{TM}$ can simulate a $\text{TM}\_k$ by using a unique character to separate the respective areas of each of the $k$ tapes.

Given this idea, how would we prove that a process taking $t(n)$ time on a $\text{TM}\_k$ can be simulated by a 2-tape Turing machine $\text{TM}\_2$ with $ O(t(n))\log(t(n))$ time?

# Answer
Look at the original paper by Hennie and Stearns:

F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", Journal of the ACM (JACM), Volume 13 Issue 4, Oct. 1966, pp. 533-546

The construction is a little bit elaborate, but not extremely difficult to understand. The basic idea is to store and keep the current symbol of each tape in the same fixed column (*home column*) and simulate a shift of the $k$ tapes using a series of partially filled "buffers" of increasing length placed on the two tapes on the left and right side of the home column in order to avoid a full shift (that would require $O(t(n)^2)$ steps). If you need further help, modify the question and ask about the points in the paper that are not clear.
> 10 votes

---
Tags: time-complexity, turing-machines, simulation, tape-complexity
---


# Question
Title: When are 2 decision/optimization problems equivalent?
Does anybody know a good definition of 2 decision / optimization problems being equivalent?

I am asking since for example allowing polynomial time computations any 2 problems in NP could be considered equivalent.

# Answer
> 6 votes
Suppose $L\_1$ and $L\_2$ are two decision problems, and $\mathcal{A}$ is a class of algorithms (like $P$). Say that $L\_1$ is $\mathcal{A}$-reducible to $L\_2$ if there is an $f \in \mathcal{A}$ such that $x \in L\_1$ iff $f(x) \in L\_2$. Say that $L\_1$ and $L\_2$ are $\mathcal{A}$-equivalent if each is $\mathcal{A}$-reducible to the other. For example, all NP-complete problems are $P$-equivalent. If you want a finer notion, you can consider more restricted classes, such as log-space or even AC0. Such notions of reducibility actually come up in refinements of Schaefer's dichotomy theorem.

As for optimization problems, let's consider maximization problems. With each maximization problem $L$ (which is a function mapping instances to optimal values), you can associate the decision problem $L'$ consisting of pairs $(x,v)$ such that $L(x) \geq v$. Now you can define reducibility and equivalence as before.

---
Tags: complexity-theory, terminology, undecidability
---


# Question
Title: Separate all leaves of a weighted tree with minimum weight cuts
This is part of a larger problem, which I believe I have reduced to this. Given a tree $T$ having positive edge weights, and $k$ leaves (nodes which have exactly one connected node), I need to delete some edges in the tree so that no two leaves in the original tree are connected (by a path) in the newly formed forest (of trees). The total sum of the weights of the deleted edges needs to be minimized.

My understanding is that atleast $k-1$ edges need to be deleted to separate out all the $k$ leaves. Any more deletions will unnecessarily increase the total cost. Thus, we need to perform exactly $k-1$ deletions.

My hypothesis: For every pair of leaf nodes $l\_i$ and $l\_j$, find the edge with the minimum weight in the (unique) path from $l\_i$ to $l\_j$. The $k-1$ least weight edges from this set of edges need to be deleted. This will minimize the sum of weights of the edges to be deleted in order to disconnect all leaves from each other.

I am unable to prove or disprove this hypothesis. Can someone please prove the correctness of this hypothesis, or give a counter-example along with the correct algorithm to solve this problem? If this is indeed correct, is there a faster way (asymptotic complexity wise) to solve this problem? This approach will take $\Theta({k^2})$ time. Thanks in advance!

# Answer
For each node $v$ with height 1 (all its children are leaves): If $v$ has degree $d$ and $d - 1$ children, then the $d-2$ smallest edges are added to the cut. These cuts are required to separate the children of $v$ from each other. Now, all but one child (leaf) of $v$ has been separated from the rest of the tree.

Now consider all the nodes $v$ with height 2. Each of these nodes with degree $d$ has a single parent edge (assuming that $v$ is not the root), and $d - 1$ paths of length at most two connecting it to the leaves in its subtree. We must remove the minimum edge from exactly $d - 2$ of these paths in order to disconnect these leaves from each other. Add these edges to the cut. Now all but one leaf in $v$'s subtree has been separated from the rest of the tree. This leaf is connected to the parent of $v$ and the rest of the tree by a path of length at most $3$. Later on, we will be required to remove at most one edge on this path, so we don't need to track all edges, just the one of minimum weight.

Now consider all nodes $v$ with height $h$. Each of these nodes with $d - 1$ children has exactly $d - 1$ leaves connected in its subtree. Each of these leaves are connected to $v$ by a path of length at most $h$, but have also stored the minimum weight edge on this path. We must cut the smallest $d - 2$ edges in order to separate these leaves from each other. The remaining leaf is connected to the rest of the tree via a path of length at most $h + 1$, and in constant time we store its new minimum weight edge by comparing the old minimum with the weight of the edge `(v, v.parent)`.

By working through the nodes in height order, we maintain the invariants that:

1. In each subtree, we have selected the minimum cut to separate the leaves in that subtree.
2. Each subtree has exactly 1 leaf connected to the root of the subtree.
3. Each subtree maintains the minimum weight edge on the path to that leaf.
4. Each subtree with $k$ leaves has selected exactly $k-1$ edges for its cut.
5. Each subtree is processed in $O(d)$ time, where $d$ is the degree of the root of the subtree.

Correctness and a running time of $O(n)$ follow from these invariants.
> 7 votes

# Answer
Consider this graph with $2k$ nodes:

<sup>\[source\]</sup>

From how you describe how you choose the edges to be removed, it is not clear what should happen. If for all pairs $(1,k), (2,k), \ldots, (k-1,k)$ the same node is chosen, you are lucky. But you might also end up removing all the edges with weight $1$, which would leave $k-1$ of the leaves connected. You see that you have to proceed iteratively, choosing the next edge to be removed knowing which are already gone.

Note that the removal of *any* edge causes a new connected component to arise; thus, removing any $k-1$ edges creates $k$ connected components. So we can just sort edges by weight and remove the $k-1$ smallest -- all we have to take care of is to not remove an edge that creates a new component without any of the original leaves.

To this end, collect in a preprocessing step for each edge all leaves reachable from one and all leaves reachable from the other incident node (without using the considered edge). This takes time $O(m^2)$ and $\Theta(mk)$ extra space, if $m$ is the number of edges (and $n$ the number of nodes), we find reachable leaves by depth-first search and we store the set of reachable leaves per edge in a bit vector.

Now sort the set of edges in time $\Theta(m\log m)$ and perform the greedy algorithm. After removing an edge $(u,v)$, update the bit vectors of all edges in the separated components accordingly: all edges in component $U \ni u$ can no longer reach those leaves reachable from $v$ and vice versa. This update takes time $O(mk)$. The greedy algorithm can not remove $(u,v)$ if $u$ or $v$ can not reach a leaf (without using $(u,v)$).

This algorithm runs in time $O(m^2k)$ (at most $m$ phases of the greedy algorithm each of time $O(mk)$, which dominates everything else). A more precise analysis might make use of the fact that components shrink quickly (on average). Also, the preprocessing step can be sped up by using message passing: the sets of reachable leaves can be propagated among inner edges/nodes.

It is clear that the algorithm separates the $k$ leaves by removing $k-1$ edges. Assume that it did not find an optimal selection of edges. Then, there is an edge $e^\*$ separating two sets of leaves $L\_1, L\_2$ which has smaller weight than one of the edges $e$ on the paths between leaves from $L\_1$ and $L\_2$ chosen by the algorithm. This is a contradiction to how the algorithm works: it would have considered $e^\*$ before $e$ because of its smaller weight, and since it separates a superset of the same leaves, could and would have removed it. Thus, the algorithm is correct.
> 3 votes

---
Tags: algorithms, graphs, trees
---


title: How to prove $L \cdot L^{*} = L^{+}$

text:
# Question
Title: How to prove $L \cdot L^{*} = L^{+}$
How can one formally prove

$L \cdot L^{\*} = L^{+}$

It looks obvious to me since with the concatenation you get rid of $\varepsilon$, but I cannot think of a formal proof through induction or something.

# Answer
To summarize the comments.

A. Sometimes $L^+$ is **defined** to be $L\circ L^\*$, where '$\circ$' is the concatenations operator.

B. Assume the following definitions,

> $L^\* \equiv \\{\varepsilon\\} \cup L \cup L^2 \cup \cdots$
>
> $L^+\equiv L \cup L^2 \cup \cdots$

Then, by the properties of the concatenation operator, $L\circ L^i = L^{i+1}$. Explicitly for the case of $i=0$, it also holds that $L\circ\\{\epsilon\\} = L$.

Then, $$\begin{align} L\circ L^\* &= L \circ \left( \\{\varepsilon\\} \cup L \cup L^2 \cup \cdots \right ) \\ &= (L\circ \\{\varepsilon\\}) \cup (L\circ L) \cup (L \circ L^2) \cup \cdots \\ &= L \cup L^2 \cup \cdots \\ &\equiv L^+ \end{align}$$

The only missing part is to explain the second transition--The distributivity of the concatenation operator over unions.
> 4 votes

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


# Question
Title: Difference between HSI and YCbCr for pattern recognition by color
I am doing a project on face detection in C#. I want to find the skin area by using skin color segmentation. For that purpose, I have to extract the skin area.

I know I can use HSI or YCbCr, but what is the exact difference between these?

# Answer
I'm not an expert, but judging from the Wikipedia articles, YCbCr is used for image compression (JPEG and television \[YPbPr\]), while HSI is used in computer vision. Since you're doing computer vision, if we believe Wikipedia then you should use HSI. Of course, you could always experiment with both representations and all six dimensions. See what works best. If you're fitting a linear model, then it doesn't really matter, and you can even use RGB.
> 2 votes

# Answer
Ycbcr just has one component (y) for luminance and two for chrominance and it is less light variation sensitive than HSI, and for face detection Ycbcr comes to better result
> 2 votes

---
Tags: pattern-recognition, image-processing
---


# Question
Title: Maximum Schedulable Set Zero-Lateness Deadline Scheduling
This is a homework problem for my introduction to algorithms course.

> Recall the scheduling problem from Section 4.2 in which we sought to minimize the maximum lateness. There are $n$ jobs, each with a deadline $d\_i$ and a required processing time $t\_i$, and all jobs are available to be scheduled starting at time $s$. For a job $i$ to be done, it needs to be assigned a period from $s\_i \geq s$ to $f\_i$ = $s\_i + t\_i$, and different jobs should be assigned nonoverlapping intervals. As usual, such an assignment of times will be called a schedule.
>
> In this problem, we consider the same setup, but want to optimize a different objective. In particular, we consider the case in which each job must either be done by its deadline or not at all. We’ll say that a subset $J$ of the jobs is schedulable if there is a schedule for the jobs in $J$ so that each of them finishes by its deadline. Your problem is to select a schedulable subset of maximum possible size and give a schedule for this subset that allows each job to finish by its deadline.
>
> (a) Prove that there is an optimal solution $J$ (i.e., a schedulable set of maximum size) in which the jobs in $J$ are scheduled in increasing order of their deadlines.
>
> (b) Assume that all deadlines $d\_i$ and required times $t\_i$ are integers. Give an algorithm to find an optimal solution. Your algorithm should run in time polynomial in the number of jobs $n$, and the maximum deadline $D = \max\_i d\_i$.

I've solved the problem as worded with the recurrence

$Opt(i, d) = \max\left \\{ \begin{array} \\ Opt(i-1, d-t\_i) + 1 \hspace{20 mm} d\leq d\_i \\ Opt(i-1, d) \end{array} \right \\}$

but our instructor added a new requirement that our algorithm must not be dependent on D. This recurrence seems like it would produce an $O(nD)$ running time if implemented with dynamic programming.

I can't figure out how to reduce its running time from $O(nD)$ to $O(n^k)$. To me it seems like it's a variation on the knapsack problem with all values equal to 1. In which case it seems like this is the best that can be done.

If I'm doing something wrong could someone point me in the right direction, or if I've done everything right so far, could someone at least give me a hint as to how I can make an $O(n^k)$ recurrence or algorithm.

# Answer
Use a dynamic programming algorithm to compute an $n \times n$ table $T$, where the entry $T(j,k)$ answers the question: suppose you wish to schedule $j$ out of the first $k$ jobs. What is the earliest time you can complete processing these?

How do we compute $T(j,k+1)$? Either the job $k+1$ is included in the best set of $j$ out of $k+1$ jobs, so $$T(j,k+1) = T(j-1,k) + t\_{k+1},$$ or job $k$ is not included in this set, so $$T(j,k+1) = T(j,k).$$ We also have to worry about the deadline. We can do this by making the entries of $T$ where the task is impossible equal to $\infty$, and checking whether we have exceeded the deadline at every step. So the pseudocode for computing the $T(j,k+1)$ entry of the table is

```
if T[j-1,k] + t[k+1] > d[k+1]
    then T[j,k+1] = T[j,k]
    else T[j,k+1] = min ( T[j,k-1]+t[k+1], T[j,k] )

```

We initialize by setting $T(j,k) = \infty$ if $j \> k$, and $T(1,1) = \infty$ if $t\_1 \> d\_1$, and $T(1,1) = t\_1$ otherwise.
> 3 votes

---
Tags: algorithms, time-complexity, dynamic-programming, efficiency, scheduling
---