# Question
Title: Finding prime factors of non-random key generator
I have been working on a challenge i found on the internet. It is as follows:

> You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the random number generator it uses frequently produces the same primes when it is generating keys.
>
> Exploit this knowledge to factor the (hexadecimal) keys below, and enter your answer as the last six digits of the largest factor you find (in decimal).
>
> Key 1: 1c7bb1ae67670f7e6769b515c174414278e16c27e95b43a789099a1c7d55c717b2f0a0442a7d49503ee09552588ed9bb6eda4af738a02fb31576d78ff72b2499b347e49fef1028182f158182a0ba504902996ea161311fe62b86e6ccb02a9307d932f7fa94cde410619927677f94c571ea39c7f4105fae00415dd7d
>
> Key 2: 2710e45014ed7d2550aac9887cc18b6858b978c2409e86f80bad4b59ebcbd90ed18790fc56f53ffabc0e4a021da2e906072404a8b3c5555f64f279a21ebb60655e4d61f4a18be9ad389d8ff05b994bb4c194d8803537ac6cd9f708e0dd12d1857554e41c9cbef98f61c5751b796e5b37d338f5d9b3ec3202b37a32f

These seem to be common RSA 1024-bit keys.

My approach to the problem was to implement Pollard's rho algorithm to find factors, then once a factor is found, try dividing the decimal form of the keys by that factor until it is not divisible anymore. Iterate.

Now, i used Pollard's rho and tried to divide until the key is not divided anymore because of the information the problem gave: the keys are not completely random.

But here comes the question: assuming the algorithm generates two primes and multiplies them to get a co-prime, which is the key, the low randomness doesn't help much, does it? I mean, even if both keys share a common factor, finding it the first time would take the regular-impractical-exponential time.

That seems to be the case, as my Python algorithm is running for about 5 hours now and has not found any factor to the second key, which i decided to start with.

As it is a challenge, i assume there is a practical way of finding the answer. So what im i doing wrong? Is just the algorithm choice wrong, as Pollard's rho is intended mainly for integer with small factors? Is my assumption that i can only use the lack of randomness after i find the first of the four factor, to then try to break the other key with the same factor, wrong?

I would like if someone could just point me in right direction, instead of just giving the answer. Thank you.

# Answer
> 6 votes
So you have two numbers that:

1. both have two prime factors, and
2. you strongly suspect that they share a factor.

So one is $n\_{1}=pq\_{1}$ the other $n\_{2}=pq\_{2}$. What is their GCD?

> What happens when you apply Euclid' algorithm?

---
Tags: algorithms, cryptography, randomness, primes
---


# Question
Title: Finite representations and programming languages Countably inifite
I'm going over some of the pre-requisite math regarding Automata theory, and finite representations.

I read the following:

* If ∑ is a finite alphabet the set of all strings over the alphabet (∑\*) is **countably infinite**.
* The set of all possible languages over an alphabet ∑ is **uncountably infinite**.

How can the set of languages possible from ∑ be **uncountably infinite**, yet the possible application of that alphabet to a language be **countably infinite**?

Can I ask those replying to not use too much complex notation, as I'm not a mathematics wizz.

# Answer
> 5 votes
Here is a simpler situation highlighting the difference. The set of finite binary strings is countable. The set of *infinite* binary strings is uncountable.

Another example: the set of numbers with finite decimal expansion is countable. The set of numbers with infinite decimal expansion is uncountable.

The reason that the number of languages is uncountable is that you have infinitely many choices: for each word, you can decide whether it's in the language or not. That's why it's like that infinite binary string considered above.

# Answer
> 4 votes
Questions of the form "how can" are always hard to answer as they ask for intuition. The intuition here is: uncountable means "too many" in way. Why are there "much more" objects of one kind than of the other kind? Well, they just are.

Make sure you understand the facts.

1. Given a finite set $\Sigma$, construct the bijection to $\mathbb{N}$ for the set of all (finite) strings over $\Sigma^\*$.

Hint: $\Sigma^n$ is finite, so combining a generalised numbering of $\Sigma^n$ with $n$ should work.\
2. Show that the set of all tuples of naturals, i.e. $\mathbb{N}^+ = \bigcup\_{i \geq 1} \mathbb{N}^i$, is countable.

Hint: Construct the bijection for $\mathbb{N}^i$ first (cf. Cantor) and combine those, again using $i$.
3. Show that the power set of $\mathbb{N}$, i.e. $2^{\mathbb{N}}$, is uncountable.

Hint: Use diagonalisation.

If you have done this, you have all the tools to show for instance that

* all algorithmic (or, more generally, finitely represented) concepts are countable but
* the set of all functions over naturals or reals or ... is uncountable.

---
Tags: discrete-mathematics
---


title: parallelizing $k$-means

text:
# Question
Title: parallelizing $k$-means
I'm having trouble thinking about the following. If we have two machines 1 and 2 that evenly split a set of data points, does $k$-means separately, then averages the result, does this agree with just $k$-means on one machine?

To be more specific, consider the following routine:

> 1. Split an input dataset evenly between 1 and 2.
> 2. Initialize $k$ centroids that are the same on both 1 and 2.
> 3. Use $k$-means algorithm to find updated centroids.
> 4. Find a new set of $k$ centroids by averaging the corresponding centroid from 1 and 2.
> 5. Loop over 2.

Will this agree with just running $k$-means? I think that it is the averaging part that might work, but then I'm not sure if this routine finishes running.

# Answer
Short answer is yes, you can parallelize $k$-means, essentially as you described.

First, on each processor, you assign points to the centroids closest to them. This part is trivial as long as each processor knows the locations of the centroids.

Next, you compute the new location of the centroids on each processor, and then combine them. But as Raphael pointed out in his comment, you have to weight the centroids from machine 1 and machine 2.

Let's consider a simple example, and only look at 5 points assigned to one of the centroids $C$. Suppose that machine 1 has points $x\_1$ and $x\_2$ and machine 2 has points $x\_3, x\_4$ and $x\_5$. If we were dealing with the standard (single processor) version of $k$-means, then the new location of $C$ would be $$ C' = \frac{1}{5} \sum\_{i=1}^5 x\_i $$

The contribution from machine 1 is $$C\_1 = \frac{1}{2} \sum\_{i=1}^2 x\_i$$

and the contribution from machine 2 is $$ C\_2 = \frac{1}{3} \sum\_{i=3}^5 x\_i $$

In order to properly combine the results from the two machines, you just do the algebra: $$ C' = \frac{1}{5}(2C\_1 + 3C\_2) $$

Your stopping condition should be the same as in the standard version of $k$-means.
> 4 votes

---
Tags: algorithms, machine-learning, parallel-computing
---


# Question
Title: Language Recognition Devices and Language Generators
I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses just like the text books I have.

My question is about language recognizers verses generators.

I get the overriding principle of a recognizer. That it analyses a language and is able to determine nay or yay if a String belongs to a language. This is at least what I have picked up from the books and notes. However, it's much more complex than that is it not? A tokeniser and syntax analyzer (which I assume to be recognizers) do not just say yes or no, they also say where and somtimes what don't they...?

However, regarding language generators,I cannot find a very clear explination about what they are. The typical description I get is, for example in Sebasta's Concepts of programming languages says *'A language generator is a device that can be used to generate the sentences of a language. We can think of a generator as a push button that produces a sentence of a language every time it is pressed.'* Seriously? That's it?? Your kidding right....

I read that Regex is an example of a Generator, then why when people talk of generators to they not talk of the inputs. For example Regex has a target String, and the Regex with defines both the accepted alphabet and it's grammar rules.

Can someone provide for me a clearer distinction of what a recogniser is?

# Answer
I assume that, by definition, a language is a set of *finite* strings.

The first distinction to be made is between **operational** and **denotational** concepts.

**Denotational definition of a language** is a precise specification of the language through various (a priori) non computational mathematical devices such as, for example:

* a specification with a property of strings that characterise the strings of the language. $\\{ x^n \mid n$ is a prime integer$\\}$
* an algebraic characterisation from other languages and strings: $L= (L\_1 \cup L\_2).abac$ where $L\_1$ and $L\_2$ are languages already defined. Note that $abac$ may also be viewed as a language with a single string. **Regular expressions** are an example of such a definition, when they are interpreted as defining regular languages. (Discussion of their pragmatic use for string matching in programming languages, under the name of Regex or Regexp, would require a specific presentation).
* a system of language equations, of which the relevant language is a solution with specific properties, for example the smallest solution, if that is well defined. An example of such an equation is $A = A B a$ where $a$ is a symbol, and $A, B$ are variables ranging on languages over an alphabet containing $a$. A pair of languages $(\hat A,\hat B)$ is a solution if $\hat A$ is equal to the concatenation of itself with $\hat B$ and a final symbol $a$
* any mix of the above

Then **operational concepts** give you ways of **answering algorithmic questions about the language** or **performing algorithmic tasks** related to the language.

Among these operational concepts, two are classical ones:

* if you are given a string, can you decide whether it is in the language or not. Such an algorithm providing a decision procedure is a **recognizer**.
* can you enumerate all the strings in the language. If such an algorithm exists, the language is said to be recursively enumerable. There are many other names. Such an enumeration algorithm is a **generator** of the language.

A generator provides a semi-decision procedure that can tell you whether a string is in the language, but may not terminate if it is not in the language.

A recogniser can always be used to have a generator (assuming your alphabet is denumerable, which is a general assumption in operational definitions). You just enumerate all the strings on the alphabet, and use the recognizer to determine whether it is in the language.

Both **a generator or a recognizer may be used to define a language**, operationally.

It is often the case that several "views" or "definitions" of the same language have to be used. It is then essential to **prove consistency** of the different views, to establish that they do define the same language. Very often, general theorems will provide that. For example, there are theorems that establish that some Context-Free recognizer building techniques (e.g., LR(k)) are consistent with the generator view of the CF grammars.

The same formalism may sometimes be read as fitting any of the above concepts.

For example, a context-free grammar define the language as a the smallest solution to a system of language equations.

It may also be read as a string rewriting system that can generate the language.

And it can be used in a fairly direct way to decide whether a string belongs to the language (without building any specific pushdown machine).

Note that there are many other thing one may want to do with a language, such as associating a structure with strings (e.g., parse-tree, or derivation tree, which need not be the same, depending on the kind of grammar considered). One may also want to associate semantics with the strings. But that is yet another type of problems, which may be very dependent of the kind of language considered.

---

Note following a remark by user @Vor. It seems that the concept of recognition, and probably of recognizer, is not the same in various sub-communities of the field.

Two articles of Wikipedia seem to have differing views on this:

* **Formal grammar**

> a grammar is usually thought of as a language generator. However, it can also sometimes be used as the basis for a "**recognizer**"—a function in computing that **determines whether a given string belongs to the language or is grammatically incorrect**.
* **Recursively enumerable language**

> In mathematics, logic and computer science, a formal language is called recursively enumerable (also **recognizable**, partially decidable, semidecidable or Turing-acceptable) **if it is a recursively enumerable subset** in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.

It is not exactly the same use of the concept of recognition, applied in one case to a string and in the other to the language. Nevertheless, it seems that the terminology is somewhat inconsistent.
> 4 votes

# Answer
For a language $L$, a *recognizer* of $L$ is an algorithm that computes

$\qquad \chi\_L(w) = \begin{cases} 1, & w \in L \\ 0 , &w \not\in L\end{cases}$.

Note that in computability and complexity theory, these are sometimes called *deciders* and algorithms that compute

$\qquad \tilde\chi\_L(w) = \begin{cases} 1, & w \in L \\ \uparrow , &w \not\in L\end{cases}$

are called *acceptors*.

A *generator* or *enumerator* can be modelled as an algorithm computing

$\qquad e\_L(i) = w\_i$

where $L = \\{ w\_i \mid i \in \mathbb{N} \\}$. As it turns out, $e\_L$ and $\tilde\chi\_L$ are equal in power (cf. the set of recursively enumerable languages) but $\chi\_L$ is stronger (cf. the set of recursive/decidable languages).

You typically want compilers to be deciders; interpreters are arguably recognisers.

A regular expression (or, for that matter, a grammar) does not fit in this terminology per se. I'd say they give a *descriptive* representation of their languages while above notions are algorithms representatios. Grammars have a slighly more enumerative feel (since translating them into a top-down generator of words is intuitive) while regular expressions feel more like deciders (via their NFA), but it's also easy to build acceptors from grammars.
> 7 votes

# Answer
The default example for a generator is a (formal) grammar. Such a grammar, combined with a source of random numburs to determine which rule to apply at each step of the derivation, will fit the description you cite.

Typical examples for recognisers are automata or parsing algorithms. As you noted, such a device will be able to determine, if a given word belongs to a language. They can be able to determine additional properties of words in the language, e.g. derive an annotated syntax tree.

In the case of regex, I would argue that they are neither a generator nor a recogniser but simply a description of the formal language, just like the set $\\{ww \mid w \in \Sigma^\*\\}$.
> 3 votes

---
Tags: formal-languages, terminology, automata
---


title: Why choose D* over Dijkstra?

text:
# Question
Title: Why choose D* over Dijkstra?
I understand the basis of A\* as being a derivative of Dijkstra, however, I recently found out about D\*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D\* over Dijkstra. To my understanding, Dijkstra gives a best path and D\* works backwards from the end goal, but unlike A\* it seems to do many calculations, so it doesn't seem as efficient.

# Answer
> 9 votes
The main reason for choosing D\* is that it is *incremental*. Basically, when your initial route gets blocked, an incremental search algorithm is able to take advantage of the previous calculations. Dijkstra doesn't do this; it needs to recompute everything from scratch. Such an incremental approach is often used in robotics, navigation, and planning.

This is the short answer. For much more, I think you would be interested in How do the state-of-the-art pathfinding algorithms for changing graphs (D\*, D\*-Lite, LPA\*, etc) differ?

---
Tags: algorithms, graphs, search-algorithms, efficiency
---


# Question
Title: Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$
Having large matrices, $W$ (the unknown) and $M$ (known), is it possible to solve for $W$ in this equation $$W \cdot W^{T} = M,$$ where $M$ can have negative entries.

# Answer
> 3 votes
You might be looking for the Cholesky decomposition. The referenced article also contains an example for $M$ having negative entries. Note the constraints on $M$ for this decomposition to exist.

---
Tags: linear-algebra, matrices, mathematical-programming
---


# Question
Title: Construct two functions $f$ and $g$ satisfying $f \ne O(g), g \ne O(f)$
Construct two functions $ f,g: R^+ → R^+ $ satisfying:

1. $f, g$ are continuous;
2. $f, g$ are monotonically increasing;
3. $f \ne O(g)$ and $g \ne O(f)$.

# Answer
There are many examples for such functions. Perhaps the easiest way to understand how to get such an example, is by manually constructing it.

Let's start with function over the natural numbers, as they can be continuously completed to the reals.

A good way to ensure that $f\neq O(g)$ and $g\neq O(f)$ is to *alternate* between their orders of magnitude. For example, we could define

$f(n)=\begin{cases} n & n \text{ is odd}\\ n^2 & n \text{ is even}\\ \end{cases}$

Then, we could have $g$ behave the opposite on the odds and evens. However, this **doesn't work** for you, because these functions are not monotonically increasing.

However, the choice of $n,n^2$ was somewhat arbitrary, and we could simply increase the magnitudes so as to have monotonicity. This way, we may come up with:

$f(n)=\begin{cases} n^{2n} & n \text{ is odd}\\ n^{2n-1} & n \text{ is even}\\ \end{cases}$, and $g(n)=\begin{cases} n^{2n-1} & n \text{ is odd}\\ n^{2n} & n \text{ is even}\\ \end{cases}$

Clearly these are monotone functions. Also, $f(n)\neq O(g(n))$, since on the odd integers, $f$ behaves like $n^{2n}$ while $g$ behaves like $n^{2n-1}=n^{2n}/n=o(n^{2n})$, and vice-versa on the evens.

Now all you need is to complete them to the reals (e.g. by adding linear parts between the integers, but this is really beside the point).

Also, now that you have this idea, you could use the trigonometric functions in order to construct \`\`closed formulas'' for such functions, since $\sin$ and $\cos$ are oscillating, and peak on alternating points.
> 17 votes

# Answer
Good illustration for me is: http://www.wolframalpha.com/input/?i=sin%28x%29%2B2x%2C+cos%28x%29%2B2x

$$ f(n) =2x+sin(x) $$ $$ g(n) =2x+cos(x) $$ $$ f\neq O(g) $$ $$ g\neq O(f) $$
> -3 votes

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


title: Concatenation of regular languages

text:
# Question
Title: Concatenation of regular languages
Suppose we have two language

```
L = {0^n|n>=0}
M = {1^n|n>=0}

```

We know both of these are regular languages.

Will L.M (concatenation) be a regular language? Please explain your answer and if yes then what will be its expression?

Thanks for any help in advance.

Adding to it, we know that language {o^n1^n|n\>=0} isn't a regular language

# Answer
The two languages can be written in a slightly different way as :

* $L = \\{ 0^i | i\geq0\\}$
* $M = \\{ 1^j | j\geq0\\}$

When you concatenate, what you get is :

* $L\circ M = \\{ 0^i 1^j | i\geq0 , j\geq0\\}$, which is, no doubt, a regular language.

What important thing you are overlooking is, **you are adding the constraint $i=j$** mistakenly which takes it to the category of CFG.
> 6 votes

# Answer
Regular languages are precisely those languages that are recognized by some nfa. Therefore the concatenation $LM$ must be regular since their nfa recognizers can simply be concatenated (i.e. linking each accepting state of $L$'s nfa to the start state of $M$'s nfa with a $\epsilon$-transition).

This does not contradict $\\{0^n1^n|n \geq 0 \\}$ being context-free, since the variable $n$ in the definitions of $L$ and $M$ are bound and thus their instantiations are Independent from each other.
> 4 votes

# Answer
Just use the equivalence with regular expressions. Your first language is $0^\*$ and the second is $1^\*$. Their product is $0^\*1^\*$, which is also regular. More generally, the product of two regular languages is regular.
> 2 votes

# Answer
L1.L2 is regular, it represents a language having any number of 0's followed by any number of 1's. We can easily construct a DFA for this(Also RL's are closed under concatenation). But, L1.L2 is $\\{0^n 1^m\mid m\ge 0, n\ge 0\\}$. Here we have treat that two $n$'s differently (they are not related to each other).
> 0 votes

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


# Question
Title: Does splitting a process across 4 terminal windows decrease the time it takes?
Basically, I using an algorithm called 'miranda' to look at miRNA targets and it only runs on a single thread. It compares everything in one file against everything in another file, produces a file as an output and runs off of the command line in terminal. The process took roughly 20 hours to create the output file.

I was advised by my supervisor that if i split one of the files up into say 4 equally sized parts, and ran them in four separate terminal windows this would decrease the overall time it took for the process to be completed.

I found that when I was using a single terminal window, the process would take up about 100-120% of the CPU. However, when running four terminal windows, each individual process only takes between 30-40% of the CPU.

How much effect does splitting the file up like this have in the overall time it takes to run the process? Although I split it across four threads, will the effect only be an increase in speed of about 1.5 times?

# Answer
> 2 votes
What you describe (split job into parts, total CPU usage stays the same) indicates that your task is (or gets) I/O (or perhaps RAM) bound. Try splitting among several machines, not just several processes on the same machine. If the program you are using comes from somewhere else, see if there are newer versions, bug reports on performance, or perhaps tricks and suggestions, on its webpage or user sites.

Use the tools on your operating system to see what the bottleneck really is. As you don't say what operating system this is, I can't give concrete suggestions. Perhaps look into uxix.stackexchange.com, superuser.com, or serverfault.com (all part of the stackexhange network).

# Answer
> 0 votes
It sounds like your data set is very large. However, you might be able to significantly speed up the program if you read everything into memory before working on it. File I/O is very slow. Rather then running four terminal windows, still split the file up, but run multiple threads from the same program. You'll see decreased overhead.

If you're using C++, a good library to check out is OpenMP for threading. As vonbrand mentioned above, you could also split the program across multiple machines. If you have a cluster available, the best way to do this would still to run a single program but parallelize it. In C++, the library OpenMPI is useful for this.

---
Tags: algorithms, cpu-pipelines, threads
---


# Question
Title: How to represent a 0-valid boolean formula?
I read in these two papers http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf and http://people.csail.mit.edu/madhu/papers/noneed/fullbook.ps that if we have a boolean formula that is $0-valid$ then (of course) SAT problem is in $\mathcal{P}$ but finding a solution with maximum true literals is $\mathcal{NP}-$hard.

N.B. As defined in the previous papers, a $0-valid$ boolean formula $f$ is a boolean formula $f: \\{0, 1\\}^n\rightarrow\\{0, 1\\}$ that satisfies $f(0, \dotsc, 0)=1$.

My question is:

Can I represent a general $0-valid$ boolean formula on the variables $x=\left(x\_1, \dotsc, x\_n\right)$ by the following one:

$f(x)=\bigwedge\limits\_{i=1}^{L}\bigvee\limits\_{i\in\mathcal{S}\_l}\neg\\;x\_i$?

Where $L$ is the number of clauses and $\mathcal{S}\_l\\;\forall\\;l\in\\{1,\dotsc, L\\}$ is a subset of $\\{1, \dotsc, n\\}$.

# Answer
The constraints of a $0$-valid formula can be more general. All we know about them is that they are satisfied if all variables are $0$. For example, a constraint could be $x = y$ (i.e. $(x \land y) \lor (\lnot x \land \lnot y)$). Your form is not general enough, since it only considers constraints of the form $\lnot x\_1 \lor \dots \lor \lnot x\_\ell$.

While your formulation doesn't capture the problem of determining the most positive solution for a $0$-valid CSP, it is equivalent to an even more classical problem, *set cover*. In particular, your problem is NP-complete.
> 3 votes

# Answer
No. A formula in the form you propose has the property that it is never satisfied by the all-ones assignment (i.e., an assignment where all variables take the value True), assuming $L\>0$. However, there exist non-trivial 0-valid formulas that don't have this property.

For instance, consider the xor $x \oplus y \oplus 1$; this is 0-valid, but is also satisfied by the all-ones assignment, and it is not equivalent to True, thus it cannot be expressed in the form you propose.
> 3 votes

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


# Question
Title: Suboptimal Solution for a combinatorial problem
I have a cost function $f(X)=\\|\hat{X}-X\\|\_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\\|X\\|\_2=\big(\sum\_{i,j}x\_{ij}^2\big)^{1/2} $. This matrix $X$ is generated by selecting only $s$ different rows from a matrix $B$ of dimension $n\times s$. At the end, we are going to choose one matrix $X$ that generates the least cost $f(X)$ within all possible $n\choose s$ submatrices of B. And so, this is a combinatorial problem that becomes complicated mostly when $n$ is big.

So my question is can we find a suboptimal solution without going through all possible $n\choose s$ submatrices and what kind of algorithm that I can apply to find such solution.

My second question is can we apply a feature selection algorithm to find a suboptimal solution for a combinatorial problem.

# Answer
## Mixed-integer quadratic programming

Given your updated question, this can be formulated as a mixed-integer quadratic programming problem.

Let $y\_1,\dots,y\_n$ be $n$ zero-or-one integer variables, subject to the constraint $y\_1+\dots+y\_n=s$, with the intent that if $y\_i=1$ then we are selecting the $i$th row from $B$. Then for each $i,j$, the entry $(\hat{X}-X)\_{i,j}$ can be expressed as a linear function of $y\_1,\dots,y\_n$. We are asking to minimize the objective function $\sum\_i,j (\hat{X}-X)\_{i,j}^2$, which is a quadratic objective function. Therefore, this can be expressed as a mixed-integer quadratic programming problem.

So, you could try throwing an off-the-shelf solver for mixed-integer quadratic programming at this and see how it does.

## Closest vector problem

If everything in sight is an integer, I think this problem could also be approached as the problem of finding the closest point in a lattice to a given vector, the closest vector problem (CVP).

Consider the following lattice over a $n+s^2$-dimensional space. For each $i$, we have a basis vector of the form

$$(0,\dots,0,K,0,\dots,0,B\_i,0,\dots,0),$$

where $K$ is a large constant (to be chosen later) and in the above, $K$ appears in the $i$th column, and $B\_i$ is the $i$th row of $B$ and it appears starting in the $n+(i-1)s+1$th column. This gives us $n$ basis vectors, which form a basis for the lattice. Now we want to find the lattice point that is closest to the vector

$$(0,\dots,0,\hat{X}\_1,\hat{X}\_2,\dots,\hat{X}\_s),$$

where the first $n$ columns of this vector are zero and $\hat{X}\_i$ is the $i$th row of $\hat{X}$. If we choose $K$ appropriately, the closest lattice point has a good chance of being a sum of just $s$ of the basis vectors and thus forming a solution to this problem.

Now you could try to see if you can find any off-the-shelf CVP solvers, and see if they are effective at this problem. This is only going to work if everything is an integer: if you've got real numbers, I don't think this will work.
> 5 votes

# Answer
If you are willing to replace the induced $2$-norm with the Frobenius norm, then you can solve the problem column-by-column instead of all at once.

In a lot of practical situations I would expect the frobenius minimizer will be exactly the 2-norm minimizer, and is a common choice of norm to minimize in matrix completion problems.

---

**edit:** In a recent edit the original poster made it clear that what they are looking for *is* the frobenius norm, even though the notation $||\cdot||\_2$ is traditionally used for the induced 2-norm. (the edit makes the problem much less interesting). Since the rest of this post is about justifying the Frobenius norm as an approximation to the induced 2-norm, it's basically irrelevant to the edited version of the question.

A little bit more on why the Frobenius norm could be a good approximation.

Since all norms are equivalent on a finite dimensional space, immediately we have $$c(s)||\hat{X} - X||\_{Fro} \le ||\hat{X} - X||\_2 \le C(s) ||\hat{X} - X||\_{Fro},$$

so the Frobenius minimizer will be within a constant of the $2$-norm minimizer when the dimensions of the matrix are fixed. The issue, as usual, is that the constants $c(s), C(s)$ depend on the number of entries in the matrix and go to zero/blow up as $s$ becomes larger and larger.

However, there is a situation where the constants do not blow up and that is, roughly, when

1. you are dealing with a sequence of matrices $\hat{X}\_s, B\_s$ that are stably larger and larger approximations of some extremely high dimensional (or infinite dimensional) true matrices (operators) $\hat{X},B$, and
2. the very large or infinite "true" problem has a solution in the sense that there exists $X\_{optimal}$ such that $\hat{X} - X\_{optimal}$ is compact.

A little bit more on these conditions: 1) is the case if, for example

* your matrices are generated by incomplete sampling of data (eg., measurements from a scientific experiment where you could get better results by taking more data, or shopping data from a small subset of amazon's customers that are supposed to represent the customerbase as a whole), and you could get similar but bigger problems from the same distribution just taking more samples, or
* the size $s$ of your matrices comes from the level of discretication of a continuum problem like a partial differential equation.

Furthermore, 2) must always be the case if you reasonably expect a solution, since if there is no approximation that makes $\hat{X} - X$ compact, then by definition it has no finite rank approximation, so you can never come up with a good result to the real problem by solving limited data versions with $\hat{X}\_s, B\_s$ nomatter how big $s$ is.

Now, assuming that the compactness condition holds, the singular values $\sigma\_1, \sigma\_2, \dots$ of $\hat{X} - X\_{optimal}$ are summable (and thus square summable), and so we have the explicit equivalence, $$||\hat{X} - X\_{opt}||^2\_{Fro} = \sum\_{i=1}^{\infty} \sigma\_i^2 = \left(1 + \frac{\sum\_{i=2}^{\infty} \sigma\_i^2}{\sigma\_1^2}\right)\sigma\_1^2 = \left(1 + \frac{\sum\_{i=2}^{\infty} \sigma\_i^2}{\sigma\_1^2}\right)||\hat{X} - X\_{opt}||\_2^2.$$

These constants are independent of $s$, and moreover the more compact the error, the faster the singular values decay, so the closer to 1 the equivalence constant is. Thus assuming that the matrices $\hat{X}\_s, B\_s$ come from stable sampling schemes or stable discretizations of $\hat{X},B$, we have the equivalence $$||\hat{X}\_s - X\_{s,opt}||^2\_{Fro} \le \gamma\_1\left(1 + \frac{\sum\_{i=2}^{\infty} \sigma\_i^2}{\sigma\_1^2}\right)||\hat{X}\_s - X\_{s,opt}||\_2^2 \le \gamma\_2 ||\hat{X}\_s - X\_{s,opt}||^2\_{Fro},$$ where $\gamma\_1$, $\gamma\_2$ come from the stability and coercivity constants of the sampling/discretization process.

So, since the assumptions above apply to a wide range of circumstances, replacing $2$-norm minimization with Frobenius norm minimization often makes sense in practical contexts.
> 5 votes

---
Tags: optimization, combinatorics, parallel-computing
---


# Question
Title: Do real world computers use the Turing Machine mechanism?
I am a high school student in the twelfth grade. I study high-level programming, and a little bit of basic computer science.

I have recently started to understand what a Turing Machine is. I wanted to ask:

I understand that a Turing Machine is a hypothetical device used to *explain* the mechanisms of computing.

But is a Turing Machine conceptually the actual very basis of computers? (In the most basic level). Or do real world computing mechanisms and the Turing Machine mechanism (way of calculating things) have very little in common?

# Answer
> 11 votes
Turing machines were invented by Turing in his 1936 paper on computable numbers and the halting problem. It was one of a few models floating around at that time (like Church's $\lambda$ calculus, which had been defined earlier). All these models have later been shown equivalent, so if you're only interested in *computability*, then the Turing machine model is as good as any other model.

Modern computers are not based on the Turing machine model. Turing machines are very slow, and don't represent the capabilities of hardware. From the software side, a modern computer is similar to the RAM machine, which allows indirect addressing and has an unlimited "alphabet" (its registers hold arbitrarily large integers), though actual machines have limited registers, and this sometimes makes a big difference (for example, when doing arithmetic on large numbers). I don't know of a good model for the hardware side; Boolean circuits, popular in theoretical computer science, model neither memory nor iterative computation.

Turing machines are polynomially equivalent to RAM machines with polynomially bounded registers. That means that both machines provide the same notion of *efficient* computation (polynomial time computation), a theoretical notion whose usefulness in practice is doubtful. In contrast, (bounded) RAM machines form a reasonable model for actual computation, and so complexity results for RAM machines have practical relevance. However, even this model ignores some important complexities of modern computers, such as the speed of access to different kinds of memory (disk, main memory, different caches).

# Answer
> 1 votes
all modern computers are basically built on the Von Neumann architecture which is essentially central processing unit CPU plus memory, and a stored program where CPU also includes arithmetic/logic unit ALU.

notice that the Turing machine basically has the same "architecture," esp the universal computer, which can run programs stored on the tape. the state table and tape head functions somewhat like the CPU (in this analogy the ALU would be a subset of all TM states that control arithmetic logic) and the tape as memory. of course many early real computers even used "tapes" to store data (and this continues in some contexts eg mass storage systems). the analogy can be further strengthened with a binary "symbol alphabet" on the tape. there are also multihead TMs studied just like with real computers.

TCS complexity theory studies physical entities operated on by the abstract TM namely space and time both which have "continuum/divisibility" like properties as in the real physical case. the TM is said to do "work" as it calculates/ *moves*, also a physical concept. many deep TCS theorems show deep interrelationships between space and time just as there are strong physical concepts eg "velocity". ie overall there are deep connections between TCS and physics. (never forget the TM is *literally a machine!*)

in short there are various strong *conceptual/metaphorical* similarities between a TM and the modern computer although depending on the context this may be either emphasized or downplayed (not surprisingly leading to some perplexity by students). a key difference is that the TM has infinite memory on the tape, in computers this is only "approximated" (so to speak) by large memories.

---
Tags: turing-machines
---


title: Power method to calculate eigenvectors

text:
# Question
Title: Power method to calculate eigenvectors
I've implemented a program for computing eigenvectors of some random, symmetric, $N$x$N$ matrix using the power method. I have found difficulty in calculating all $N$ eigenvectors consistently, almost every time the algorithm fails to converge for all $N$. The Wikipedia page on the power method tells me this algorithm is not guaranteed to converge for all $N$ eigenvectors, can someone suggest a way for me to encourage convergence, at least in a majority of the cases? Is this possible? If not, can someone suggest a better algorithm for computing eigenvectors?

# Answer
> 2 votes
Whole books and fields of research are devoted to methods for computing eigenvalues and eigenvectors. Properties of the matrix matter, a lot. The ideal method will depend on whether

* the matrices are symmetric or nonsymmetric,
* positive definite or indefinite,
* sparse or not sparse,
* you need all the eigenvalues/vectors or just a few,
* you have $O(1)$ access to the elements of the matrix or just the ability to apply it to vectors via a function call
* etc...

That said, at the core of most modern methods for finding all the eigenvalues of a generic matrix is the The QR algorithm (the eigenvalue algorithm, not the related orthogonalization algorithm). The methods most used in practice such as the Arnoldi iteration (or Lanczos for symmetric problems) are basically a 2 step process in which the matrix is converted into a nicer form, and then the QR algorithm is used.

Understanding the power method is a good place to start from because it's intuition informs most of the other methods in some way or another.

---
Tags: algorithms, linear-algebra, matrices
---


title: Binary Palindrome

text:
# Question
Title: Binary Palindrome
Let an integer n be given. Write the integers from 1 to n in binary notation successively from left to right. In the resulting string consisting of zeros and ones, choose a palindrome substring of maximal length. It is required to find the length of this substring. For example, if n=5, we can get a string which is 1 10 11 100 101. And we can get the longest substring that is palindromic: 11011 or 01110. So the answer to the question is 5. The n can be very big. Are there any good algorithm to solve this problem? Thanks in advance!

# Answer
You could use a regular palindrome substring search algorithm, such as as Manache's Algorithm. It would still be optimal, i guess, even considering that your string is binary. Take a look at that algorithm.
> 2 votes

---
Tags: algorithms
---


title: Understanding decidability

text:
# Question
Title: Understanding decidability
Sorry this is a basic question to understand decidability. It is the first time I see it in my undergrad course.

**1)** I am reading why the language `AFDA` is decidable and why `ATM` (halting problem) is not. The explanation says that the emulated `TM` in `ATM` might loop forever. I agree, because a specific input string might make the `TM` going forever, always able to apply rules and never halting.

However, why is `AFDA` decidable? What if the automaton never reaches any of its final states and keeps looping? There might be a specific input that makes the `FDA` never reach such states. I understand that once the input string finishes, it will be either accepted or rejected, but what if it does not finish? I'm assuming the input string in the `TM` can be infinite.

**2)** The same problem I have here:

```
A = { 0^k 1^k | k >= 0}

```

This language is decidable, and it will halt in strings like `10`, `010101`, etc but what if the input string is infinite `01010101......` it will never end.

What am I missing?

# Answer
> 2 votes
1) The automaton "halts" after it reads the input, whether or not it reaches a final state. It *accepts* the input if, when it halts, it's in a final state.

2) Inputs are always finite strings. There are generalizations of finite automata ($\omega$-automata of various kinds \[Buchi, Rabin, Muller\]) that accept $\omega$-words (countably infinite strings) as inputs.

# Answer
> 0 votes
1) I haven’t heard of the “AFDA” acronym before, but I assume you mean the acceptance-problem for Deterministic Finite Automatons. In that case, the answer is that the input strings in this machine model are *always finite*. Because the DFA always halts, a Turing machine can decide whether a given DFA accepts the input or not.

2) Again, in all common machine models input strings are *always finite*, especially in undergrad courses where you typically adress finite-state machines, Turing machines, pushdown automata,… (Unless, of course, infinite input strings are explicitly allowed in your specific machine model.)

---
Tags: turing-machines
---


# Question
Title: Pumping lemma on {a^n | n=3^k} — help finishing the proof
I am working on a pumping lemma question and trying to prove that the following is not regular, but I can't finish the proof, if someone can help me it will be great.

So I am given this language: $L = \\{ a^n | n = 3^k , k≥0 \\}$ . Ok. I choose $w = a^{3^m}$. I know for sure that $y = a^t$ ($y$ must be any number or $a$'s), where $t≥1$. $x = a^{(3^m)-t}$ and $y = a^t$. I pump twice, so $i =2$ and $xy = a^{(3^m)+t}$.

Now, is this enough to finish the proof? What is my $xyz$? and how do I prove that my $w$ is not in the language? Thank you so much for whoever decide to help me out!

# Answer
> 1 votes
It is not enough. Also note that you didn't define $x$ correctly, and forgot $z$. I would define: $$x = a^s$$ $$y = a^t$$ $$z = a^{3^m - s -t}$$ such that $s + t \<= m$ and $t \>= 1$ (hence $1 \<= t \<= m$)

You need to show that for $i=2$, you get something that is not in L (meaning, there is no $k$ such that $x(y^2)z = a^{3^k}$ ).

Let's look at $x(y^2)z = a^{3^m+t}$. Its length is $3^m + t$.

Using the fact that for every $i, i \< 3^i$, We get: $3^m \< 3^m + 1 \le |x(y^2)z| = 3^m + t \le 3^m + m \< 3^m + 3^m = 3^{m+1}$

We see that the length of $xy^2z$ isn't in the form of $3^n$ (it's something between $3^m$ to $3^{m+1}$, hence it is not in L. Contradiction to the pumping lemma.

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


# Question
Title: How to reformulate my problem as a mixed-integer quadratic problem
I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the $s$-dimensional vector $a$ is to be computed to find $x$.

The only assumption that we have is $x=0$ when we project $x$ onto the space spanned by $s$ different rows (that we don’t know their indices) of the matrix $B$ which has $n$ rows. To do this projection we can use $P\_s\in \mathbb{R}^{n\times n}$ which is $1$ on the diagonal entries that correspond to the $s$ selected rows of $B$ and $0$ elsewhere. Hence, $P\_s x= P\_s z + P\_s Ba=0 \implies a=-(P\_sB)^{-1}P\_sz$.

The main issue is that we don’t know the positions of these $s$ rows, so the problem is combinatorial and we need to go through all possible $n\choose s$ projections to find the exact $x$ which corresponds to the least cost $f(x)=\\|y-Ax\\|\_2$ where $\\|v\\|\_2=\big(\sum\_iv\_i^2\big)^{1/2}$, $y\in \mathbb{R}^{m\times 1}$ and the matrix $A\in \mathbb{R}^{m\times n}$ are given.

So my question is how I can reformulate my problem as a mixed-integer quadratic programming to go through all possible $n\choose s$ submatrices of $B$ formed by the $s$ selected rows and finally find the set of rows which corresponds to the least $f(x)$.

# Answer
> 1 votes
So it sounds like the problem is the following:

> Given $A,B,y,z$, I want to find the vector $a \in \mathbb{R}^n$ that minimizes $||y-Az-ABa||\_2$, subject to the constraint that there must exist some matrix $P\_s$ with exactly $s$ 1's on its diagonal and 0's everywhere else, satisfying $P\_s (z+Ba)=0$.

## Mixed-integer QCQP

This can be formulated as a mixed-integer quadratically constrained quadratic programming problem, as follows.

We have $n$ unknowns $a\_1,\dots,a\_n$, so $a=(a\_1,\dots,a\_n)$. Also introduce $n$ integer zero-or-one unknowns $p\_1,\dots,p\_n$, with the intention that $P\_s$ will be the diagonal matrix whose diagonal is $p\_1,\dots,p\_n$. Add the cosntraint that $p\_1+\dots + p\_n=s$, to ensure that exactly $s$ of the entries on the diagonal are $1$. Note that each entry of $z+Ba$ is a linear expression in the unknowns, so the constraint $P\_s (z+Ba)=0$ can be expressed as $n$ quadratic constraints, each of the form $p\_i \cdot e\_i=0$ where $e\_i$ is linear in $a\_1,\dots,a\_n$.

Now note that each entry of $y-Az-ABa$ is a linear expression of the $n$ unknowns $a\_1,\dots,a\_n$, so the objective function is a quadratic function of the unknowns.

Unfortunately, mixed-integer QCQP is a pretty challenging form of non-linear programming, so I don't know how well this will work in practice. You might have to try it out with some solvers.

This is a pretty brain-dead approach. There may be smarter approaches that are more effective than this, by taking advantage of the structure of your problem.

---
Tags: optimization, combinatorics, parallel-computing, integer-programming
---


# Question
Title: Good beginner source to learn about how computers work
I am a senior year high school student. I love programming and my chosen language is Java. I'm very much into high-level programming and Object Oriented design.

Recently, I started to show first interest in the low-level side of things. Especially the most basic level of how computers work (the more theoretical level, not the hardware side).

For example, how computers make basic calculations has always been a mystery to me. How is it that a computer can even come up with the result for `5 + 2`? (As a kid I used to think that every computer stores the answers for all of the possible calculations.. lol)

I am also interested in the most basic level of how computers, well, generally do things internally. Again, at the most basic and fundamental level.

As you can see it's hard for me to phrase what I'm interested in learning, probably because I know almost nothing in computer science. But I hope you get the idea.

Could you direct me to a good source that I can learn from - at the most beginner level - this kind of knowledge? (A website or a book \[preferably a website\]).

Thanks

# Answer
What I have got for you is :

These books should help you understand how computer works. A bit knowledge of computer hardware is a must and it will surely speed up your learning process.
> 3 votes

# Answer
> Recently, I started to show first interest in the low-level side of things. Especially the most basic level of how computers work (the more theoretical level, not the hardware side).

Well, actually it is the opposite: the more theoretical, the more high-level, since you deal with abstract notions.

To understand the theory behind computers, the best book I have read is Introduction to the Theory of Computation by M. Sipser. You have everything: Turing machine, automata, grammars and languages, complexity, etc. It is very well written and fairly accessible, considering the topic.

> I am also interested in the most basic level of how computers, well, generally do things internally. Again, at the most basic and fundamental level.

The reference remains for me A. Tanenbaum's books: Structured Computer Organization for hardware and Operating Systems: Design and Implementation for OS. Old books but still standing. Caution however: these are reference books, and not always very "undergrad-friendly" (since you are soon an undergrad, right? :) ).
> 1 votes

# Answer
You could start off with Java at http://www.learnjavaonline.org/. And once you are clear with syntax of Java, you could try http://codingbat.com/java. Its got some really good programming exercises.
> -2 votes

---
Tags: books
---


# Question
Title: In reference to the Chomsky hierarchy (and automatas), Which is the linear feedback shift register Languages/automaton?
The Chomsky hierarchy is a guideline on language expressive power. The linear feedback shift register is a very interesting "element" to structure a language and there is a large theoretical literature.

In reference to the Chomsky hierarchy (and automata), which is the linear feedback shift register languages/automaton ?

# Answer
It has a *finite* memory, so it's just a DFA (or some of the output-producing variants). If you allow a growing/shrinking feedback register, it is probably equivalent to a Turing machine.
> 1 votes

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


# Question
Title: Using the pumping lemma for a proof by contradiction
I'm trying to prove that the set of even-length strings with the two middle symbols being equal cannot be accepted by finite automata. I can explain why it cannot be accepted intuitively, but I'm having trouble with the proof. Our symbols are {a, b}.

I allowed L = $\\{(ab)^{\*{\frac{n}{2} - 1}} aa (ab)^{\*{\frac{n}{2} - 1}}\\}$. I know the format of the language is wonky, and will be talking to my professor about it tomorrow. For the proof, I allowed $\frac{n}{2} - 1$ to be the combination of symbols before and after the two elements. So, using the Pumping Lemma's condition that |uv|≤ n, I allowed $u = \frac{n}{2} -1$ and $v = n^2$ (for aa); this is obviously greater than n, but I'm having trouble understanding how to choose $u$ and $v$. Is my assignment for these parameters correct?

# Answer
> 0 votes
$u$ and $v$ are supposed to be strings such that $uv$ is a prefix of a string in the language longer than $p$ symbols, $p$ being the pumping length. Furthermore, you do not get to choose them. All you know is that their total length does not exceed $p$ and they are prefix of a word $x$ in the regular language, of length $n$.

You do not get to choose them because they are existentially quantified in the statement of the pumping lemma ... you could choose them if they were universally quantified. If you do not understand this last remark, just ignore it.

What you can choose is the value of $n$ and the string $x=uvw$ of size $n$ that will be used for pumping. You choose $n$ in relation to the pumping length $p$ which depends only on the regular language.

I would suggest to choose $n$ quite big, so that you make sure $uv$ is in the first half of the string $x$, since $| uv| ≤ p$.

I would also choose my string $x$ with an appropriate pattern of a and b ... and then check what happens when I pump. It may seem odd, but you have to get even with that problem.

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


# Question
Title: Proving that Max Weighted Independent Set is in NP
What I'm trying to do is to show a problem in NP can be reduced to the min weight vertex cover problem

I've chosen the max independent weight problem = input: A graph G with weights on each vertex, output: An independent set with the max total weight

Before reducing, I've tried to show that the max indep. weight problem is in NP (which is usually the first step in these reductions). I'm trying to construct a verification algorithm for this problem; but I'm stuck on trying to show that the verification algorithm can check if a certificate is the max indep. set in polynomial time.

Any guidance or comments would be greatly appreciated. Thanks

# Answer
> 1 votes
Max weighted independent set is the decision problem whose instances are pairs $(G,B)$ such that $G = (V,E,w)$ is a vertex-weighted graph that has an independent set of weight *at least* $B$. Nowhere is it claimed that $B$ is the maximum weight of an independent set. The problem (like many others) is defined in this way precisely so that it be in NP.

Also, in order to show that your problem is NP-hard, it might be easier to reduce from max independent set.

# Answer
> 3 votes
The issue is with the version of the problem you are using. Note that as you define it, the output is required to be the maximum weight independent set, i.e. the optimum answer. $NP$ however is a class of *decision* problems, so the only valid outputs are Yes and No.

So if you want to show the problem is in $NP$ you first need to convert it to a decision problem:

> **$k$-Weight Independent Set**
> Input: A vertex weighted graph $G=(V,E,w)$ and an integer $k$.
> Question: Is the a set $V'\subset V$ such that $V'$ is an independent set and $\sum\_{v\in V'} w(v) \geq k$?

It should be easier to see that this version is in $NP$. There is an optimization class - $NPO$ - that corresponds to $NP$, but the normal definition is that a problem is in $NPO$ if its decision variant is in $NP$ - so you're still in the position where you want to deal with the decision variant.

---
Tags: reductions, np
---


# Question
Title: Impact on the order of elements on the cost of searching in a linked list
I have the following homework question that I am struggling with. I have read the corresponding chapter from the book, but no guidance there.

Consider a linked list $X: X\_1 \to X\_2 \to X\_3 \ldots$. Assume that the cost of examining a particular element $X\_i$ is $C\_i$. Note that to examine $X\_i$, one needs to scan through all elements in front of $X\_i$. Let $P\_i$ be the probability of searching for element $X\_i$, so the total cost for all searches is $$ \sum\_{j=1}^{n} \left( P\_j \cdot \sum\_{i=1}^{j} C\_i \right) $$

1. Show that storing elements in non-increasing order of $P\_i/C\_i$ does not necessarily minimize the total cost.
2. Show that storing elements in non-decreasing order of $P\_i$ does not necessarily minimize the total cost.

Any help and direction how to approach the problem will be highly appreciated.

# Answer
I'm assuming costs are strictly positive. Otherwise it doesn't make much sense to consider the quantity $P\_i/C\_i$.

Regarding 1: Consider any order, and suppose that for some $i$, $P\_i/C\_i \< P\_{i+1}/C\_{i+1}$. Suppose that we switch the elements $i$ and $i+1$. Say that we switched between $\ldots,A,B,\ldots$ and $\ldots,B,A\ldots$. Let $\Delta$ be the difference in average search cost (new cost minus old cost). When looking for $A$, which happens with probability $P\_i$, we have to pay $C\_{i+1}$ more. When looking for $B$, which happens with probability $P\_{i+1}$, we have to pay $C\_i$ less. So $$ \Delta = P\_i C\_{i+1} - P\_{i+1} C\_i = (P\_i/C\_i - P\_{i+1}/C\_{i+1}) C\_i C\_{i+1} \< 0. $$ In other words, the switch was beneficial. We conclude that the optimal arrangement is to store the elements in non-increasing order.

*How I found this proof:* I tried to construct a counterexample by trying a few examples on two elements, but I didn't work. So I decided to write the inequalities enjoyed by such a counterexample, and solve them in order to find one. The solution showed that in fact no counterexample is possible.

Regarding 2: This is quite easy to construct, especially in view of part 1, which gives a condition for optimality in case there are only two elements. I'm sure you can handle this part yourself.
> 1 votes

---
Tags: algorithm-analysis, data-structures, linked-lists
---


# Question
Title: Are statecharts with parallel states NFA, DFA, or none of the above?
I'm looking for formal statements and proofs that I can make when using SCXML statecharts. As such, I'm trying to categorize it properly.

SCXML supports hierarchical states. I believe that any hierarchical state machine can be converted into an equivalent non-hierarchical state machine. And I believe that a "simple" non-hierarchical state machine can be considered a DFA (deterministic finite automata).

SCXML is not a "simple" state machine, however:

* Transitions between states may be guarded by arbitrary code conditions. Only one transition from an active state will be taken as a result of a single event, but which transition is taken may vary. Given this, I believe that SCXML should be considered (for certain configurations) an NFA (non-deterministic finite automata).
* Certain transitions may be taken not in response to an event, but as soon as a condition is valid. Given this, I believe that SCXML may at times be considered an NFA with ε-moves.
* SCXML supports not just hierarchical states, but also "parallel" (orthogonal) states. These allow the runtime to be in more than one atomic ("leaf") state simultaneously.

This last detail gives me pause, as I have not found any formal statements classifying parallel state machines. **Does the introduction of concurrent parallel states break any NFA definition?**

I *think* that it doesn't. I *think* that you can convert any parallel state machine into an equivalent non-parallel machine via combinatorial explosion. But I'd like to know it for sure.

# Answer
The paper *Parallel Finite Automata for Modeling Concurrent Software Systems* contains a proof and examples showing that a (non-hierarchical) parallel state machine can be converted into a non-parallel version. The technique is somewhat obvious: simply create the cartesian product of all concurrent sections and you have a DFA.

Combine with a proof that any hierarchical section of a state machine can be flattened into an equivalent non-hierarchal version, and there exists an obvious—but hard for me to formally notate—conversion process that involves flattening hierarchies and expanding parallel sections from the leaves on upwards.

The result is that any SCXML state machine can be converted into an equivalent version that contains neither hierarchy nor parallel states. At this point the state machine may be DFA, NFA, or NFA with ε-moves (depending on the transitions used), but all of these are similarly equivalent.

In summary, I believe that any SCXML state machine can be converted into an equivalent DFA, and as such the formalisms of DFA apply.
> 2 votes

---
Tags: automata
---


# Question
Title: Every language that is reducible to a language in $\Sigma_i^p$ is also in $\Sigma_i^p$ . How?
The complexity class $\Sigma\_{k}^{p}$ is recursively defined as follows: \begin{align} \Sigma\_{0}^{p} & := P, \\ \Sigma\_{k+1}^{p} & := P^{\Sigma\_{k}^{p}}. \end{align}

Why is every language that is reducible to a language in $\Sigma\_i^p$ also in $\Sigma\_i^p$?

This comes in the proof of the theorem: If there is a PH-complete problem, then PH (the polynomial hierarchy) collapses.

# Answer
First of all, there are many reduction concepts, but I assume you mean the polynomial reduction ($\le\_p$).

The complexity class $\Sigma\_{k}^{p}$ is recursively defined as follows: \begin{align} \Sigma\_{0}^{p} & := P \\ \Sigma\_{k+1}^{p} & := P^{\Sigma\_{k}^{p}} \end{align}

Let $A$ and $B$ be two languages over alphabets $\Sigma\_A$ and $\Sigma\_B$, respectively. Let $k \in \mathbb{N}\_0$, $B \in \Sigma\_{k}^{p}$ and $A \le\_p B$. Since $A$ is polynomially reducible to $B$, there exists a function $f: \Sigma\_A^\star \rightarrow \Sigma\_B^\star$ (computable in polynomial time), such that $x \in A \Leftrightarrow f(x) \in B$. So we have an algorithm that decides $A$, which first transforms the input for $A$ to an input for $B$ using $f$, and then uses the algorithm for $B$ on the transformed instance. Therefore, $A$ is in $max\left\lbrace P, \Sigma\_k^p \right\rbrace$.

If $k = 0$, $\Sigma\_k^p = \Sigma\_0^p = P$, then $A$ is also in $P = \Sigma\_0^p$, since the transformation requires at most polynomial time and $B$ is in $P$.

If $k \> 0$, the transformation is negligible and $A \in \Sigma\_k^p$.
> 3 votes

# Answer
Let's take $\Sigma\_3^p$ as an example. It is defined as the set of all languages of the form $$ x \in L \Leftrightarrow \exists |y| \< |x|^{c\_1} \forall |z| \< |x|^{c\_2} \exists |w| \< |x|^{c\_3} \varphi(x,y,z,w), $$ where $\varphi$ is a polytime predicate. Here $\exists |y| \< |x|^{c\_1}$ means that there exists a string $y$ of length less than $|x|^{c\_1}$ such that the bound formula holds.

Now suppose that a language $M$ is p-reducible to such a language $L$, say for some polytime $\psi$, $x \in M \Leftrightarrow \psi(x) \in L$. Suppose that $|\psi(x)| \< |x|^d$. Then $$ x \in M \Leftrightarrow \exists |y| \< |x|^{dc\_1} |y| \< |\psi(x)|^{c\_1} \land \forall |z| \< |x|^{dc\_2} |z| \< |\psi(x)|^{c\_2} \Rightarrow \exists |w| \< |x|^{dc\_3} |w| \< |\psi(x)|^{c\_3} \land \varphi(\psi(x),y,z,w). $$ Equivalently, $$ x \in M \Leftrightarrow \exists |y| \< |x|^{dc\_1} \forall |z| \< |x|^{dc\_2} \exists |w| \< |x|^{dc\_3} |y| \< |\psi(x)|^{c\_1} \land ( |z| \< |\psi(x)|^{c\_2} \Rightarrow (|w| \< |\psi(x)|^{c\_3} \land \varphi(\psi(x),y,z,w))). $$ It's not hard to check that the new predicate is also polytime, and so $M \in \Sigma\_3^p$.
> 1 votes

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


# Question
Title: What is the evidence that that types are more basic specifications, and specifications are more detailed types?
In the book **Type Theory and Functional Programming** \[Thompson, S 1999\] the author explains the relationship between specifications, types and proofs of functions:

> The equivalent specifications can be thought of as suggesting different program development methods: using the ∃∀ form, we develop the function and its proof as separate entities, either separately or together, whilst in the ∀∃ form we extract a function from a proof, post hoc.
>
> This analysis of specifications makes it clear that when we seek a program to meet a specification, we look for the first component of a member of an existential type; the second proves that the program meets the constraint part of the specification.

On this same topic, the commenter writes:

> Specifications are in a way "more detailed" types. Or, state the other way, types are more basic specifications. Martin-Lof type theory is precisely about fusing the two ideas into one.

My question is: **What is the evidence that that types are more basic specifications, and specifications are more detailed types?**

# Answer
As Gilles points out, it depends on what you count as types. If you mean by types something like types in Java or Scala or Haskell, then this is clearly true.

One easy way to see this is (simplifying a bit) to use a general framework of specifications to express the behavioural content of types as a specific case of specification. The best framework to do this at the moment is $\pi$-calculus as a programming language and Hennessy-Milner logic as a specification language. I suggest to choose $\pi$-calculus because it's expressive, and well studied. In particular, most sequential programming languages are easily seen to be (behaviourally equivalent to) specific sub-calculi of $\pi$-calculus. Hennessy-Milner logic is an expressive modal logic that can be used to nail down processes up to behavioural equivalence. Now we take an arbitarty type, say the function space constructor $ int \rightarrow bool $ and express the constraints this type imposes on programs as a specification in Hennessy-Milner logic.

Conversely, we need to show that specifications are strictly more expressive than types but that's fairly obvious, for we cannot specify e.g. that a method is sorting its input array.
> 1 votes

---
Tags: functional-programming
---


title: Algorithm to Group Vertices of Graph

text:
# Question
Title: Algorithm to Group Vertices of Graph
Given is the following graph which is logically divided into layers (with Dijkstra's shortest paths algorithm):

```
 Vertices   Layer

    Root      0
   /   \
  A     B     1
 / \    |
C   D   E     2
 \  |  /
  \ | /
    F         3

```

Now I'm looking for an algorithm which groups vertices when they have a (single) common ancestor in the previous layer, e.g. for the graph in the example the groups would be:

```
0: A, B
1: C, D
2: E
3: F

```

I know that this is doable by visiting vertices and comparing ancestors but I was wondering whether there is a well known algorithm for it.

**Update:** My question is really only related to find groups. I'm aware of the fact, that I can traverse vertices and test for incoming edges and group those vertices. Furthermore, the graph is fully constructed.

One (now deleted) answer mentioned DFS, which creates a search forest (as BFS creates a search tree which I basically used for levels, though I mentioned Dijkstra). So, I assume that combining BFS and DFS could give me the desired result.

# Answer
this seems to be known as the "Lowest Common Ancestor" problem of graphs. see eg
> 1 votes

# Answer
Maybe you can use A\* algorithm as a better alternative to dijkstra and use the metric function ( heuristic ) of a\* to group or flag your vertices in an appropriate way.

Change due to assessment.

I think there is no appropriate algorithm doin that. Because you need to span the whole graph before knowing which connections are established. With the metric or heuristic approach you can predict some kind of grouping during the evolvement of the graph by defining rules for grouping within your metric function.

Best regards.
> 0 votes

# Answer
I think Breath First Search would work, (by searching for a node not in the graph so, I guess check for a NIL node) and just print out the adjacent edges, when marking them as searched. It will search all the nodes until there are no nodes left to search and NIL is found.
> 0 votes

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


# Question
Title: What is the name two mutually idempotent functions?
To clarify, in haskell, there is an `ord` function that gives the byte integer of a character (i.e. `ord 'a'` yields `97`); and there is a `char` function that takes the byte integer of a character and returns the character (i.e. `char 97` yelds `'a'`.

What is the name of a collection of such functions? I'm not very mathematically literate (I'm working on it), but I found semirings on wikipedia. Do semirings provide an appropriate description?

# Answer
> 2 votes
These are known as *inverse functions*. For example, the mappings $x \mapsto 2x$ and $x \mapsto x/2$ are inverses of each other, as are $\exp$ and $\log$ (restricted to positive numbers), or $\sin$ (restricted to the interval $\[-\pi/2,\pi/2\]$) and $\arcsin$.

---
Tags: sets
---


# Question
Title: Context-free grammar for $L = \{a^n : n\leq2^{20}\}$
I want to find a context-free grammar for $L = \\{a^n : n\leq2^{20}\\}$. There's one for sure. I approached it by two ways and both seemed dead end. One was to set a limit during the production of the new strings. But I don't think there's such a thing in CFGs. Second approach was to produce the strings of the language top-down. Starting from the last string $a^{2^{20}}$ and removing an $a$ each time till epsilon but I don't think that's achievable either. Any ideas?

# Answer
> 6 votes
As Karolis mentions, one solution is $$ S \to \epsilon | a | a^2 | a^3 | \cdots | a^{2^{20}}. $$ However, we can do better: $$ \begin{align\*} &A\_{20} \to A\_{19} A\_{19} \\ &A\_{19} \to A\_{18} A\_{18} \\ &A\_{18} \to A\_{17} A\_{17} \\ &A\_{17} \to A\_{16} A\_{16} \\ &A\_{16} \to A\_{15} A\_{15} \\ &A\_{15} \to A\_{14} A\_{14} \\ &A\_{14} \to A\_{13} A\_{13} \\ &A\_{13} \to A\_{12} A\_{12} \\ &A\_{12} \to A\_{11} A\_{11} \\ &A\_{11} \to A\_{10} A\_{10} \\ &A\_{10} \to A\_9 A\_9 \\ &A\_9 \to A\_8 A\_8 \\ &A\_8 \to A\_7 A\_7 \\ &A\_7 \to A\_6 A\_6 \\ &A\_6 \to A\_5 A\_5 \\ &A\_5 \to A\_4 A\_4 \\ &A\_4 \to A\_3 A\_3 \\ &A\_3 \to A\_2 A\_2 \\ &A\_2 \to A\_1 A\_1 \\ &A\_1 \to A\_0 A\_0 \\ &A\_0 \to a | \epsilon \end{align\*} $$ The start symbol is $A\_{20}$. You can prove by induction that $A\_k$ generates $\\{ a^n : n \leq 2^k \\}$. If you want an even shorter solution, you can try $$ \begin{align\*} &A\_{20} \to A\_{18} A\_{18} A\_{18} A\_{18} \\ &A\_{18} \to A\_{16} A\_{16} A\_{16} A\_{16} \\ &A\_{16} \to A\_{14} A\_{14} A\_{14} A\_{14} \\ &A\_{14} \to A\_{12} A\_{12} A\_{12} A\_{12} \\ &A\_{12} \to A\_{10} A\_{10} A\_{10} A\_{10} \\ &A\_{10} \to A\_8 A\_8 A\_8 A\_8 \\ &A\_8 \to A\_6 A\_6 A\_6 A\_6 \\ &A\_6 \to A\_4 A\_4 A\_4 A\_4 \\ &A\_4 \to A\_2 A\_2 A\_2 A\_2 \\ &A\_2 \to \epsilon|a|aa|aaa|aaaa \end{align\*} $$ Many more options are possible, see which one you like most.

Comments:

1. In terms of number of symbols, a grammar based on powers of 2 is the most efficient.
2. This approach seems (at first) to work only for powers of 2, but in fact you can use the binary representation to handle any upper bound (exercise).

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


# Question
Title: A NPDA for the language $L = \{w \mid w \in \{a,b,c\}^*, n_c(w) = n_a(w) + n_b(w)\}$
Consider the language $L = \\{w, w \in \\{a,b,c\\}^\*, n\_c(w) = n\_a(w) + n\_b(w)\\}$, where $n\_q(\omega)$ is defined to be "the number of $p \in \omega$.

I have tried a couple of PDA's that follow this whole idea of a stack-replacement kind of algorithm, but the reasoning behind it is incorrect. I know it is not the right structure; furthermore, those examples of my previous attempts don't really fit in the context of the question that I'm asking.

There I have a gut feeling that I need to exploit the fact that $0=n\_a(w)+n\_b(w)-n\_c(w)$ but I have absolutely the faintest idea how to do so. When building this kind of "counting machine," what are some design patterns that I can exploit?

# Answer
You don't need the "N" in your "NPDA", you can do this with a deterministic counter machine. Every time you see an $a$ or a $b$ increment the counter by $1$, every time you see a $c$ decrement the counter by $1$. When you get to the end of the string, if the counter is at $0$ then accept, else reject.

This is very easy to convert to a standard PDA instead of a counter. As a hint, you will need only one symbol for you stack, and will have to use your finite state to remember if your counter is positive or negative (while the stack remembers the actual magnitude of the count), and you will accept by empty stack.

I am not going to write down the answer more explicitly than this since it is a homework excercise, and you will not learn anything from just copying my answer.
> 2 votes

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


title: How does binary addition work?

text:
# Question
Title: How does binary addition work?
I find **binary** confusing. I have watched minecraft redstone videos on binary adders, real binary adders, diagrams, etc and yet I have not learned much at all. *How does electrons flowing through wires made of gold "add/subtract" to make numbers through some logic gates?!*

# Answer
## It's like magic, isn't it?

Here's a visual depiction for you, and hopefully it will make it easier for you to understand. This circuit is something called a half-adder; a half-adder is a special kind of adder -- the most base level kind of adder -- that takes two values, A and B which are the addend and auged respectively, and outputs them into the sum. If the addend and augend overflow, then the overflow is placed into a special output called $C\_{out}$, which means "carry out."

Well, to chain these together, we need to take two half adders and put them together in order to construct something called a full-adder. What makes a full-adder special is that it takes another input, $C\_{in}$ as well as the addend and augend, and performs an addition on all three of those bits. Here, the half adder I described above has been put into a "black box" kind of configuration, where the visible details of the circuit are hidden, and the inputs and outputs are provided instead. Notice, just like the half-adder, we have a sum and a $C\_{out}$ too.

Well, to construct bigger adders, such as four bit adders, we need to chain those full-adders together, and this is when the pattern becomes even more obvious:

And to construct an 8 bit adder, you put two four bit adders together. To construct a 16 bit adder, you put two eight bit adders together. To construct a ... well, you get the point.

---

## So, what's all the 1 and 0 nonsense that I'm hearing about? (Read: how in the heck did someone come up with all of this).

Easy. We have things called "logic gates" which are represented by a couple of symbols to start with, but the simplest way to explain it is in the form of something called a truth table, but what these "True" and "False" values really represent is 1 for true and 0 for false -- but don't worry about that, yet. The first two columns: p|q are a set of truth values that are then evaluated for the other columns. Where $p\wedge q$ represent $p$ and $q$, $p\vee q$ represent $p$ or $q$, and the last column represents $p$ xor $q$

The last operator, `xor` is a special operator. It is the english equivalent of "I either \__ or \__" and the implication is that both cannot happen at the same time.

So when we're connecting these in relation to the individual circuit symbols, you can check those out here.

Putting these all together, with the special truth tables that I've shown you, you can clearly see that in the case of the half adder, walking through a set of logic values you can determine what these propositions mean in terms of those two binary truth values.

So, what's all this mean in terms of our base? Our system of counting? Well, as you may know, it is possible to convert a number of an arbitrary base (ours is 10) to another arbitrary base (in the case of the circuit, it is base two). There are many ways to do that, one of which is by using wolfram alpha; however, the manual way is fun too, if you want to learn how.

Let's count:

0 0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

8 1000

9 1001

10 1010

11 1011

12 1100

13 1101

14 1110

15 1111

16 10000 \<-- Rollover

The set of numbers on the right are binary numbers. The numbers on the left are numbers in our base, base 10. If you'll notice, the far right column, ex. 000\[0\], is the 'ones' column. This represents one one. The second column, ex. 00\[0\]0, is the 'twos' column. The third column, ex. 0\[0\]00, is the fours column. The fourth column \[0\]000 is the 'eights' column. Notice how the power values are, increasing in powers of two. Make more sense now?

So what makes these circuits work? Consider the half-adder. Those inputs a and b represent some arbitrary value coming from the outside. The first portion of the half adder is a `xor` gate. Look in the table for what happens when two true values are applied (1's), the output is 0. Therefore the sum is zero. Now consider the `and` gate, what happens when two true values are applied to the and gate? the output is one. So, we derive the sum from the output of the xor gate (which is 0), and we derive the $C\_{out}$ from the `and` gate which is (1) if A and B are both (1).

---

## Edit: More Circuits

I've added these and I've also made YouTube video of them working, just as I promised.

---

---

## Videos:

If I get another request, I'll make another video and upload it, showing the internals of what it REALLY looks like as the circuit is going through its cycles.

Here are some adders

Here is a demonstration of the gates

---

Make more sense now?
> 18 votes

---
Tags: logic, binary-arithmetic
---


# Question
Title: What is the difference between RAM and TM?
In algorithm analysis, we assume a generic one processor Random Access Machine (RAM). As far as I know, the RAM machine is no more efficient than the Turing machine. All algorithms can be implemented in the Turing machine. So my questions are:

* If the Turing machine is as efficient as the RAM machine, then why are we not assuming Turing machine for algorithm analysis?
* What is the difference between RAM and TM?

# Answer
> 16 votes
Turing machines are not as efficient as RAM machines. A RAM machine can access an arbitrary tape location in $O(1)$. A Turing machine can't. A RAM machine can do arithmetic in $O(1)$ (under certain restrictions). A Turing machine can't.

Turing machines polynomially simulate RAM machines, that is, for some constant $c$, any RAM machine running in time $O(n^k)$ can be simulated by a Turing machine running in time $O(n^{ck})$. (The constant is pretty reasonable, about $2$, depending on the Turing machine model.)

---
Tags: turing-machines, computation-models
---


# Question
Title: Regarding Turing Machine Halting Problem
All problems solved by standard today's general purpose computer can be solved by standard Turing machine.As general purpose computer can't do more than Turing machine so The Turing machine halting problem must also be unsolved by today's general purpose computer.How can I realize the fact that halting problem can't be solved by todays general purpose computers.

# Answer
The halting problem is the question of whether a program $B$ halts on and some given input $x$. It is impossible to create a program that decides the halting problem, so the effect is that, whatever program $A$ you create, there will exist some program $B$ and input $x$ such that $A$ will not tell correctly whether $B$ halts on input $x$.
> 2 votes

---
Tags: computability, turing-machines, halting-problem
---


title: Lamport's Byzantine Generals Algorithm

text:
# Question
Title: Lamport's Byzantine Generals Algorithm
I've stumbled at the first OralMessage algorithm in Lamport, et al's paper.

I've searched the web and there are dozens of sites, restating in exactly the same terms and examples, which isn't helping me.

Lamport claims the algorithm can handle (n-1)/3 traitors, and works when the commander is a traitor.

My restatement of the algorithm:

1. The commander sends a value to each of the lieutenants.(round 0)
2. Each lieutenant: forwards each message he receives to the other lieutenants:
don't forward messages that already have your name (eg you are b and receive 'cb1')
don't forward messages if they already have (N - 1)/3 names. (eg N=10 and you receive 'gcd0')
add your name to front of message before forwarding (eg you are b and receive 'c0', send 'bc0')
3. after all messages have been sent, each lieutenant:
examines the received messages and makes their decision.
if its a tie, then decide 0.

I'm not sure how to do 3, the paper says the algorithm "assumes a sequence of \[majority\] functions" (nested?)
In the example, I'm assuming to take the majority in each vector of round 2 (ie left to right), and then take the majority of these.

EXAMPLE

Commander is a traitor, N=7, M=(7-1)/3=2, so 6 lieutenants one of whom is a traitor. I have assigned the lieutenants letters b-g.

Here are the messages **received** at each node in rounds 1 & 2, assuming a node can send to itself. (the messages in brackets are redundant from B's point of view. I don't know if this is important.):

```
<(b1) ,c0   ,d0   ,eX   ,f1   ,g1   >

<     ,(cb1),(db1),(ebX),(fb1),(gb1)>
<(bc0),     ,dc0  ,ecX  ,fc0  ,gc0  >
<(bd0),cd0  ,     ,edX  ,fd0  ,gd0  >
<(beX),ceX  ,deX  ,     ,feX  ,geX  >
<(bf1),cf1  ,df1  ,efX  ,     ,gf1  >
<(bg1),cg1  ,dg1  ,egX  ,fg1  ,     >

```

Note:
'dc0' is sent to everyone by 'd' (because 'd' was the last to prepend their name)
'X' indicates an unreliable message. 'e' is a traitor and always sends unreliable messages

BUT 'step 3' gives 1,0,0,X,1,1 which is no better than round 1.
AND the majority of these is 1 if X is 1, and 0 if X is 0. So the traitor can confound us.

What am I doing wrong?

# Answer
----I'm not sure if this should be my answer. Many thanks to hengxin. It does explain my confusion, and may be helpful to others seeing the question----

I failed to realise that there are 2 types of unreliable messages,
\- some are different for each lieutenant, (eg 'eX' in round 1)
\- others are the same for all lieutenants (I will denote these as 'S')

the amended example is,

```
<(b1) ,c0   ,d0   ,eX   ,f1   ,g1   >

<     ,(cb1),(db1),(ebX),(fb1),(gb1)>   1
<(bc0),     ,dc0  ,ecX  ,fc0  ,gc0  >   0
<(bd0),cd0  ,     ,edX  ,fd0  ,gd0  >   0
<(beS),ceS  ,deS  ,     ,feS  ,geS  >   S
<(bf1),cf1  ,df1  ,efX  ,     ,gf1  >   1
<(bg1),cg1  ,dg1  ,egX  ,fg1  ,     >   1

```

now the result from 'round 2' is different to 'round 1', and allows agreement.
however, we could have acheived the same result with:

```
<(b1) ,c0   ,d0   ,eX   >

<     ,(cb1),(db1),(ebX)>   1
<(bc0),     ,dc0  ,ecX  >   0
<(bd0),cd0  ,     ,edX  >   0
<(beS),ceS  ,deS  ,     >   S

```

Remember we have a traitor commander, but it seems more than coincidence that there is 1 traitor lieutenant out of 4 lieutenants (3t+1)?
> 2 votes

---
Tags: distributed-systems, fault-tolerance
---


title: Edge traversals of trees

text:
# Question
Title: Edge traversals of trees
I want to find a minimal vertex in a tree from which we can traverse some edges exactly twice then come back to that vertex then do it with the rest of edges. By minimal, I mean that the difference of numbers of two subsets of edges have to be minimum.

# Answer
For each vertex label each incident edge $e$ with the number of edges reachable through $e$ (including $e$).
The vertex you are looking for satisfies that the maximum of its labels is at most $\left\lceil\frac{n-1}2\right\rceil$. It is easily verified that there is exactly one such vertex in each tree. ($n$ denoes the number of vertices of the tree, thus $n-1$ is the number of edges.)

In order to find that vertex efficiently, we can modify depth first search.

We start at an arbitrary vertex and in each vertex we do the following:

1. Initialize a flag `candidate = true` and an integer `sum = 0`.
2. For each edge $e$ leading to a child $v$:
    1. Call the procedure on $v$. Denote the return value by $s$.
    2. Label the incident end of $e$ with $s$.
    3. `sum = sum + s`.
    4. If $s \> \left\lceil\frac{n-1}2\right\rceil$ set `candidate = false`.
3. Set $r = n - 1 - sum$.
4. Label the incident end of the edge leading to the parent with $r$.
5. If $r \> \left\lceil\frac{n-1}2\right\rceil$ set `candidate = false`.
6. If `candidate == true` the current vertex is the one we are looking for. Abort.
7. return $r+1$.

The correctness should be straightforward. Since the additional effort is ${\cal O}(1)$ per vertex resp. per outgoing edge, the runtime stays in ${\cal O}(|V| + |E|) = {\cal O}(n)$.
> 1 votes

# Answer
*Note: This is a rewriting of the previous version of my answer. It is hopefully easier to understand. The previous version had a bug in the vertex labeling formulae where it used $L\_v(e)$ instead of $L^v(e)$.*

Since the question was not clear, and changed over time, I present below a general method that can handle several different definition of a vertex to be identified by some property. I use it to compute both the **Jordan center(s)** and the **"gravity" center(s)**.

From the initial statement of the question, and an erased comment made by the OP, it seemed that the problem was to find the Jordan Center(s) \[there may be two\], of the tree. The definition of the Jordan Center(s) states that it has minimal excentricity, the excentricity of a vertex being its longest distance to any other vertex. There may be one or two such vertices in a tree.

The current statement of the question, as clarified by David Richerby, seems to rather ask how to find what I am calling here the gravity center of the tree, i.e., a vertex where it can be divided into two subtrees such that the difference between their number of edges is minimal.

To simplify the presentation, here are some of the definitions and notations I am using.

* a tree is a pair composed of a finite non-empty set of vertices (or nodes) and a set of unordered pairs of vertices, called edges, such that there is exactly one path between any two vertices. Our reference tree here is noted $T$.
* an edge is said to be incident on each of its two vertices, and a vertex is said incident on all edges it belongs to. A vertex with a single incident edge is called a **leaf**.
* a **rooted-tree** is a tree with a distinguished vertex $r$ called the root. To specify the root, it may be called a $r$-rooted-tree.
* a **rooted subtree** of a tree $T$ is a rooted-tree such that all edges are edges in $T$, and all vertices except possibly the root have the same number of incident edges as in $T$. This means that the missing parts of $T$ must have been cut off at the root.
* a rooted-tree is **prime** iff there is only one incident edge on the root.
* a $u$-rooted subtree $s$ of a $v$-rooted tree $t$ is a **daughter** of $t$ iff (v,u) is an edge of $t$. Then, by adding the edge to the subtree $s$ you obtain a prime $v$-rooted subtree of $t$.
* $D(t)$ is the set of daughters of a $v$-rooted tree $t$
* $D(v)$ is the set of daughters of the full tree $T$ rooted in vertex $v$.
* $E(t)$ is the set of edges in a (sub)tree $t$. For a vertex $v$, $E(v)$ is the set of incident vertices on $v$.
* for a (sub)tree $t$, we call **weight** of $t$ its number of edges.
* an **attribute** (characteristic value) of a rooted tree $t$ is said to be **synthesized** if it can be computed from the values of the same attribute for the daughters of $t$. The formula to be used to do this computation is called the **synthesis formula**. An **initial attribute** must be provided for all daughter subtrees that are only a single leaf vertex with no edge.
* a **vertex labeling formula** for a tree $T$ is a formula that computes a label for each vertex $v$ from attributes computed for each daughter of the $v$-rooted tree $T\_v$.

Note that the root of a daughter tree always has on less incident edge in the daughter than in the full tree. The missing edge is precisely the edge connecting it to the root of its parent tree.

Synthesized attributes can be computed for a $v$-rooted tree $t$ by a recursive function calling itself recursively on each of the daughters of $t$.

Alternatively, it can be computed for all daughters of all rooted subtrees of $T$. There are exactly two such daughters for each edge of $T$, one at each end of the edge. One proceeds by initializing all the leaf vertex attributes, and then using the synthesis formula to compute the attribute for all daughter trees, when their own daughter have had their attribute computed. It is easy to show that, as long as there is a daughter without its attribute, there is one where the attribute can be computed because it has been done for all its daughters. Hence the algorithm terminates, with every daughter having its attribute computed.

Various optimizations are possible, depending on what is being computed.

## Case of the Jordan center.

The attribute needed is the depth $\phi$ of each daughter tree, i.e., the length of longest path starting from its root.

We initialize the attribute $\phi(l)$ of each leaf daughter $l$ to 0, since there is no path starting from it.

The **synthesis formula** to compute the attribute for a daughter $d$ is $\phi(d)= 1+{Max}\_{t\in D(d)} \phi(t)$

The vertex labelling formula is then: $L(v)=\max\_{t\in D(v)} \phi(t)$

The Jordan centers are the vertices with the smallest label.

## Case of the gravity center

We want to find a vertex $g$ such that the tree can be split at that vertex (keeping a copy of the vertex in each of the two parts) so that the weight difference between the two parts is minimal, the weigth of a tree being the number of edges. I am calling such a vertex a **gravity center** of the tree (**there may be 2 gravity centers**).

This amounts to finding a vertex $g$ minimizing the weight difference between the two partitions of a bipartioning of $D(g)$.

For this purpose we choose as attribute the weight $\omega(d)$ of each daughter tree.

We initialise the attribute $\omega(l)$ of each leaf daughter $l$ to 0, since it contains no edge.

The **synthesis formula** to compute the attribute for a daughter $d$ is $\omega(d)=\Sigma\_{t\in D(v)} 1+\omega(t)$

Note that, as soon as there is an edge (u,v) such that the two daughter corresponding to that edge have their weight computed, their sum is the weight $p=|E(T)|$ of the whole tree $T$. This can then be used to simplify computation and speed up the algorithm.

The vertex labeling formula label each vertex $v$ with the smallest weight difference $\delta\_v$ between two subtrees partitioned on that vertex. The vertex with the smallest such value $\delta\_v$ is the answer to the question. The vertex labelling formula is then: $L(v)=\min\_{I\subseteq D(v)}\left|\sum\_{t\in I}\omega(t) - \sum\_{t\in D(v)\setminus I}\omega(t)\\,\right|$.

Then the gravity center is the vertex with the smallest label.

However, this vertex labeling function is NP complete in the number of incident edges on the vertex, as it is a Partition problem. We need a better way to identifies the center of gravity, without actually computing the partition into 2 subtrees.

Instead, we identify the gravity center with another property: a vertex $g$ is a gravity center iff no prime $g$-rooted subtree has more than $(p+1)/2$ edges, where $p=|E(T)|$ is the total number of edges. Hence it is a vertex $g$ with the smallest maximum value for the weight of a prime $g$-rooted subtrees. Since the weight of a prime $g$-rooted subtree, is just 1 more than the weight of the corresponding daughter, we can use instead the weight of daughters.

Thus we use the following vertex labelling formula: $L(v)=\max\_{t\in D(v)} \omega(t)$
Any vertex $g$ with the smallest label $L(g)$ is a gravity center.

**Sketch of a Proof**

First we note there may be one or two gravity centers. For example, if you connect two trees having the same weight (number of edges) with an additional edge, then the vertices joined by that edge are the two gravity center of the larger tree thus created. They both have a minimum weight difference equal to 1 (corresponding to the connecting edge). So they both have a prime rooted subtree with $(p+1)/2$ edges. It is the rooted subtree that start with the connecting edge.

We note $\delta\_v$ the minimum weight difference between subtrees of a bipartition rooted at the vertex $v$.

Then, we prove that if a prime $v$-rooted subtree $\tau$ has more than $(p+1)/2$ edges, there is another vertex $u$ such that $\delta\_u\<\delta\_v$, so that $v$ cannot be a gravity center. The vertex $u$ is the vertex at the other end of the root vertex of $\tau$. The proof uses the fact that the total weight of all prime $v$-rooted subtree is constant, equal to $p=|E(T)|$.

We then prove that if a vertex $g$ has a prime $g$-rooted subtree with exactly $(p+1)/2$ edges, then there is another such vertex, but all other vertices have a prime $g$-rooted subtree with more edges.

Similarly we prove that if a vertex $g$ has all prime $g$-rooted subtree with less $(p+1)/2$ edges, all other vertices have a prime $g$-rooted subtree with more than $(p+1)/2$ edges.

The last 2 proofs are by finite induction on the distance between the gravity center and the vertex considered. One can show that on a path from a gravity center (that does not include the other, if any), the difference $\delta\_v$ associated with a vertex $v$ increases strictly with the distance of $v$ from the gravity center. One can also prove that the maximum weight of a prime $v$-rooted subtree increases strictly too in the same way. This can be used to find quickly the gravity center.
> 1 votes

---
Tags: graphs, trees, graph-traversal
---


# Question
Title: Is Math a MUST in computer science specificly in Software Development for Web servers
I know math is necessary for application development in simulation software and else.

But I'm learning Python and trying to go deep in PHP, and like to develop applications and extends web servers' capability.

I'm before a big dilemma that whether to learn math professionally or not. I have tried my best to avoid being general on my question.

I have asked this question here because I want to learn it from roots and deal with its scientific aspects.

# Answer
> 4 votes
Your question seems to be based on the misunderstanding that *software development = computer science*. They are not the same thing. Your questions starts out asking about software development, but then ends by asking about the roots and scientific aspects thereof, which brings you to computer science, so it is not entirely clear what you want.

If you want to focus on software development, then math is not required (though it will often come in handy).

If you want to focus on computer science, then it is absolutely essential.

---
Tags: software-engineering
---


title: Difference between BTSP and TSP

text:
# Question
Title: Difference between BTSP and TSP
I am wondering what is the difference between Bottleneck Travelling Salesman Problem and normal Travelling Salesman Problem?

Thank you

# Answer
> 2 votes
BTSP asks to find a Hamiltonian cycle in a weighted graph, which minimizes the weight of its most weighty edge.

TSP asks to find a Hamiltonian cycle in a weighted graph, which minimizes the sum of weights of its edges.

---
Tags: algorithms, traveling-salesman
---


# Question
Title: Proving a binary heap has $\lceil n/2 \rceil$ leaves
I'm trying to prove that a binary heap with $n$ nodes has exactly $\left\lceil \frac{n}{2} \right\rceil$ leaves, given that the heap is built in the following way:

Each new node is inserted via percolate up. This means that each new node must be created at the next available child. What I mean by this is that children are filled level-down, and left to right. For example, the following heap:

```
    0
   / \
  1   2

```

would **have** to have been built in this order: 0, 1, 2. (The numbers are just indexes, they give no indication of the actual data held in that node.)

This has two important implications:

1. There can exist no node on level $k+1$ without level $k$ being completely filled
2. Because children are built left to right, there can be no "empty spaces" between the nodes on level $k+1$, or situations like the following:

```
    0
   / \
  1   2
 / \   \
3  4    6

```

(This would be an illegal heap by my definition.) Thus, a good way to think of this heap is an array implementation of a heap, where there can't be any "jumps" in indeces of the array.

So, I was thinking induction would probably be a good way to do this... Perhaps something having to deal with even an odd cases for n. For example, some induction using the fact that even heaps built in this fashion must have an internal node with one child for an even n, and no such nodes for an odd n. Ideas?

# Answer
If I get your question correctly, the obtained heap is just an ordered binary-tree, where in ordered I mean that the $k$th level can only be occupied after the $k-1$ level has been completely filled, and each level is occupied from left to right, without skipping.

Then the proof goes like this.

1. A perfect tree of depth $k$ has exactly $2^{k+1}-1$ nodes.
2. Assume that the heap reaches depth $k$. Thus
    1. up to level $k-1$ the tree is perfect (and has $2^k-1$ nodes there)
    2. on the last level, there are exactly $n-2^k+1$ nodes, which are all leaves.
3. Each leaf on the $k$th level has a parent. Moreover, each two consecutive leaves have the same father (maybe except for the last node, whose father has only one child)
4. Thus, out of the $2^{k-1}$ nodes at level $k-1$, $\left\lceil \frac{n-2^{k}+1}{2} \right\rceil$ are parents, and the rest $2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$ are leaves.
5. The total amount of leaves is $$n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$$ Which gives you what you need.
> 10 votes

# Answer
Here's a simpler logical proof.

Last leaf is $n^{th}$ index. Its parent is at index $\lfloor{n/2}\rfloor$ and similarly, there is no element such that its parent is ($\lfloor n/2 +1\rfloor)^{th}$ element. Thus leaves are indexed from $\lfloor{n/2}\rfloor$ +1 to n.

Hence, total number of leaves = n- $\lfloor(n/2)\rfloor$ = $\lceil(n/2)\rceil$.
> 18 votes

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


title: Reduce Vertex cover to SAT

text:
# Question
Title: Reduce Vertex cover to SAT
I need to reduce the vertex cover problem to a SAT problem, or rather tell whether a vertex cover of size k exists for a given graph, after solving with a SAT solver. I know how to reduce a 3-SAT problem to vertex cover problem, by constructing the subgraphs for each variable (x, !x) and for each clause (a triable). But I am not getting,how to do other way round?

I was thinking of first forming a DNF ,with electing k vertices at first and then convert it to a CNF, by enumerating all clauses. Is there any other method?

# Answer
> 8 votes
Let's introduce a variable $x\_i$ for every node $i$, representing the condition that the node is part of the vertex cover. Then for every edge $\\{v,w\\}$ we introduce the clause $x\_v \lor x\_w$.

We have the additional condition $x\_1 + x\_2 + \ldots \ +\ x\_n \leq k$. We can combine an addition circuit to compute the bits of the sum with a comparator circuit to enforce the inequality. The CNF of the resulting circuit has only polynomially many clauses.

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