# Question
Title: Keeping a String Secret in (Open) Source Code
I have finished developing an app for Android and intend to publish it with GPL -- I want it to be open source. However, the nature of the application (a game) is that it asks riddles and has the answers coded into the string resource. I can't publish the answers! I was told to look into storing passwords securely -- but I haven't found anything appropriate.

Is it possible to publish my source code with a string array hidden, encrypted, or otherwise obscured? Maybe by reading the answers from an online database?

Update

Yuval Filmus's solution below worked. When I first read it I was still not sure how to do it. I found some solutions, for the second option: storing the hashed solution in the source and calculating the hash everytime the user guesses. To do this in javascript there is the crypto-js library at http://code.google.com/p/crypto-js/. For Android, use the MessageDigest function. There is an application (on fdroid/github) called HashPass which does this.

# Answer
> 87 votes
You have at least two options, depending on what problem you want to solve.

If you want innocent readers of your code to not get the answers inadvertently, or you at least want to make it a bit difficult so that users are not tempted, you can encrypt the solutions and store the key as part of your code, perhaps a result of some computation (to make it even more difficult).

If you want to *prevent* users from retrieving the answer, you can use a one-way function, or in computer jargon, a *hash function*. Store a hash of the answer, and they you can test whether the answer is correct without it being possible to deduce the answer *at all* without finding it first. This has the disadvantage that it is harder to check for an answer that is *close* to the correct answer, though there are some solutions even to this problem.

# Answer
> 29 votes
You have two three options:

**Keep the answers separate from the rest of the source code**

If you want your code to be open source, however don't want the answers to be open source, then you open source the code for the application *without* the questions & answers, with the questions & answers being a separate closed source "plugin" or data file. Your Android app would bundle both of these together into a single app.

**Put the answers in your source code**

Alternatively, if you consider the questions and answers to be a core part of what you want open sourced then you should put the answers into the source code, *preferably un-obfuscated so that others can read and modify them*. Obfuscating source code so that it can't be understood and modified isn't really in keeping with the principles of open source code.

**Put the answers on a server on the internet**

With both of the above solutions it's possible for someone who has downloaded your app to find out the answers without playing your program in either case - no matter how you obfuscate / encrypt your answers, if your program can identify the answer without additional information, so can a human examining your compiled app.

If you *really* want to make sure that nobody can find out the answers then the only real option is **not to give them the answers** and have the app call a web service etc... whenever they want to know the answer. The app should send the answer that the user has entered and the web service should tell the app whether or not the answer is correct, that way the user has no way of telling what the answer is until after they already have the correct answer (short of brute-forcing the web service, which you can detect and protect against).

If you are looking for ways to obfuscate your answers the that suggests to me that you don't really want to open source your answers in the first place, so you should consider the first options.

If it's *critical* that the user not be able to find the answer in advance then the third option is your only real choice, however I'm struggling to think of a scenario where this would be worth the effort, not least because it prevents your users from using your app without an Internet connection.

# Answer
> 4 votes
If the object is to obscure strings from casual reading of the source code but keep them open so other people can easily make their own changes - for example if you were publishing the source to a text adventure and didn't want any descriptive text to appear which would constitute a spoiler, then use something reversible like rot13.

In fact, you could rot13 all your translation files and flip them back on the fly.

That's keeping the open spirit. Random "magic" hashes isn't really programmer-friendly.

# Answer
> 4 votes
Open source requires the source code to be made public and available, not the game data. So you could easily put the data in another file and not publish that one. Add some crypto if you want to prevent casual reading of the file. I doubt a strong crypto is necessary for your application.

# Answer
> 4 votes
Why would you store your answers in your GPL source code if you don't want your users to know them? Even if they're not known or easily crackable now, they can (and likely will) be in the future.

Instead of storing them in your app, use an external database. Make a small web service that compares the answers to what's in your database. Then let your application make a call to that webservice whenever it has to verify. The main problem is that, because it requires internet access, you will lose some speed and potential userbase. your app license should only apply for the app itself, not the webservice.

You could also just put your answers in a small database and put that in your program. As far as I know, GPL only applies to source code, not any data that your app stores. I might be wrong on that, though.

# Answer
> 1 votes
Remember that even if you store a database in a remote web server, the database can still be duplicated by simply writing down all correct key/value pairs that have been seen. And generally speaking, mobile apps should try to not give errors or cease to function because the network is down (use queued messaging, and "update when you can").

So if you want a local database, but don't like the idea of it getting blatantly decrypted, you can use a bloom filter (to avoid talking to a network or having a big decrypted database locally). This is how spell checkers used to work when memory space was really tight.

So, if you add question/answer pairs into the filter like:

> Hash(NormalizeString(Question\[n\]))+Hash(NormalizeString(Answer\[n\]))

If you ask if "Capitol of Virginia?Richmond" is in the set, it will either answer "definitely no", or "almost certainly yes". If you get too many false positives, then make the database larger.

You could have an immense database in a tiny space, assuming that the user will spell the Question and Answer exactly as you expect. Keeping the database small helps with updates, because they probably have to be transferred over wireless networks.

---
Tags: arrays, security
---


# Question
Title: Algorithm: ordering non-overlapping intervals
Assume we have a (multi)set of nontrivial intervals $\mathcal{I} = \\{I\_1,...,I\_n\\}$ and for any two $I\_i, I\_j \in \mathcal{I}$, we have that $I\_i \cap I\_j$ is trivial (that is: contains at most one point), or one of them contains the other. Just to clarify, an example would be $\mathcal{I} = \\{\[0,10\], \[2,6\],\[6,8\], \[2,4\],\[2,3\],\[5,6\],\[6,7\]\\}$. For the sake of simplicity, assume there is a longest interval that contains all other intervals, call that the root.

We can arrange such (multi)sets as a tree where $I\_i$ is a descendant of $I\_j$ iff $I\_i \subseteq I\_j$ (if an interval has multiplicity $\> 1$, then its multiple occurrences can form a path in the tree). What I want to do is find such a tree. It's clearly possible in $\mathcal{O}(n^2)$ time: sort the intervals by length in descending order and process them in that order. Whenever we insert the next interval $I\_i$ into the tree, find the shortest interval already in the tree $I\_j$ such that $I\_i \subseteq I\_j$; such an $I\_j$ must exist since the root contains all other intervals.

I would like to do this in $\mathcal{O}(n \log n)$ time and it seems to me that should be possible. Rough ideas include using interval trees and trying to construct the tree from the bottom up starting from its leaves, or figuring out how to annotate search trees to do something like this for me, but nothing successful so far.

# Answer
You can solve it in $O(n \lg n)$ time using a divide-and-conquer algorithm.

## Explaining the main idea: a cleaner variant

To help me explain the main idea, I'm going to change the problem slightly. I'll assume we're given a set of intervals, with no interval appearing more than once in the set, and where for any pair of overlapping intervals $I,I'$, one of them contains the other (i.e., either $I \subset I'$ or $I' \subset I$). The goal is to output a forest (a collection of trees).

This variant of the problem is slightly more general, in that we're not assuming we have a single root interval that all others are contained in. It's also slightly more specific in that I'm assuming we don't have the case of a trivial overlap containing a single point.

I'll show later in my answer how to remove these extra assumptions, but for now, let's go with this variant of the problem, as it makes explaining the main ideas easier.

## Main idea: an algorithm for the cleaner variant

We'll use divide-and-conquer. Let $x$ denote the median of the $2n$ endpoints of the intervals. This can be computed in $O(n)$ time.

Use $x$ to partition the intervals into three collections:

* The intervals that are wholly to the left of $x$ (i.e., their right endpoint is strictly less than $x$).
* The intervals that are wholly to the right of $x$ (i.e., their left endpoint is strictly greater than $x$).
* The intervals that contain $x$.

We'll first compute three forests, one forest for each of these three collections. Call these forests $\mathcal{L}$ (the forest of the intervals on the left), $\mathcal{R}$ (for the intervals on the right), and $\mathcal{M}$ (for the intervals that contain $x$). You can compute $\mathcal{L}$ and $\mathcal{R}$ by invoking the algorithm recursively. You can compute $\mathcal{M}$ directly by sorting the intervals that contain $x$ by decreasing width and building a path of the intervals by descending size (each node in $\mathcal{M}$ has exactly one child; it is the next-smallest interval).

Now we need to join together the forests $\mathcal{L},\mathcal{R},\mathcal{M}$. Since $\mathcal{M}$ is a path, given an interval $I$, you can find the smallest interval $I' \in \mathcal{M}$ such that $I \subset I'$ by using binary search. Therefore, to join the forests, take the roots of $\mathcal{L}$ and $\mathcal{R}$ and use binary search in $\mathcal{M}$ to find the smallest interval containing it, and add a corresponding child relationship. This is all you need to do to join them into a single forest, as there can be no other child relationships between $\mathcal{L},\mathcal{R},\mathcal{M}$. Output the resulting forest.

What's the running time of this procedure? Well, it takes $O(n)$ time to partition the intervals into these three collections. You can compute $\mathcal{M}$ in $O(n)$ time (if you've done a single up-front precomputation to sort the intervals by decreasing width). It will take at most $O(n \lg n)$ time to join $\mathcal{L}, \mathcal{R}, \mathcal{M}$ into a single forest, since each binary search operation can be done in $O(\lg n)$ time. With a little more cleverness, you can speed up the merging to run in $O(n)$ time (pre-sort the intervals by their left endpoint once, and by the right endpoint; now you can join $\mathcal{L}$ and $\mathcal{M}$ by doing a merge on the sorted list of intervals of $\mathcal{L}$ and the sorted list of intervals of $\mathcal{M}$, both sorted by their left endpoint; join $\mathcal{R}$ and $\mathcal{M}$ similarly). Therefore, the running time is $O(n)$ plus the time for the two recursive calls. Finally, note that each recursive call is on at most $n/2$ intervals, due to the way we chose $x$ (there can be at most $n/2$ intervals wholly to the left of $x$, as each such interval contributes 2 endpoints to the $2n$ endpoints, and at most $n/2$ intervals wholly to the right of $x$).

Therefore, we get the recurrence relation

$$T(n) = 2 T(n/2) + O(n),$$

whose solution is $T(n) = O(n \lg n)$.

## Solving your original problem

Your original problem allows a pair of intervals to overlap in a single point, without either one containing the other. This doesn't fundamentally change the problem. You need to generalize the method for computing $\mathcal{M}$ slightly, as it is no longer guaranteed to be a simple path, but this is not hard to do. Also, now $\mathcal{M}$ might have two leaves. If so, for each root of $\mathcal{L},\mathcal{R}$, you need to compare it to both leaves to see whether it is contained in either one. This doesn't change the overall running time.

Also, your original problem allows some intervals to appear in the input twice. This is easy to accommodate: remove duplicates, count how many times each interval appears in the input, run the algorithm above, and then adjust the tree to account for multiplicities (e.g., by duplicating nodes, or however you would like them to appear in the final output).
> 5 votes

# Answer
What about another sorting order, which seems to be compatible with pre-order in your proposed trees?

Define $I \le I'$ with $I=\[a,b\]$ and $I'=\[c,d\]$ iff $I$ is before $I'$, i.e., $b\le c$, of $I$ contains $I'$, i.e., $a\le c$ and $d\le b$.
> 3 votes

---
Tags: algorithms, data-structures, trees, intervals, ordering
---


# Question
Title: Combinational Logic - Need help with proof by rewrite
In my Computer Logic class we were assigned the following problem:

> Complete a **truth table** that has $3$ inputs $(A, B,C)$ and one output $(F)$. $F$ is asserted whenever $B$ or $C$ are asserted, but deasserted if both $B$ and $C$ are asserted. $F$ is asserted whenever $A$ is asserted and $C$ is deasserted. $F$ is deasserted in all other cases.

After which we are supposed to

> Determine the sum-of-products equation for $F$. Show the terms instead of the minterm abbreviations (show $ABC$ instead of m7).

Finally, we are supposed to:

> Prove that $F$ from question $2$ is equivalent to $F = BC' + B'C + AC'$ using proof by rewrite. HINT: remember the uniting law is the key to minimization.

Here is what I have:

1)

```
A    B    C    F
0    0    0    0
0    0    1    1
0    1    0    1
0    1    1    0
1    0    0    1
1    0    1    1
1    1    0    1
1    1    1    1

```

2) $F = A'B'C + A'BC' + AB'C' + AB'C + ABC'$

Number three is what is throwing me. I am using the axioms of boolean algebra, such as the Uniting Law, but so far all I have been able to do is the following:

3) A’B’C + A’BC’ + AB’C’ + AB’C + ABC’ = BC’ + B’C + AC’

```
A’B’C + A’BC’ + AB’C’ + AB’C + ABC’

A’B’C + AB’C + A’BC’ + AB’C’  + ABC’            Commutative Law

B’C + A’BC’ + AB’C’ + ABC’                      Uniting Law

A’BC’ + ABC’ + B’C + AB’C’                      Commutative Law

BC’ + B’C + AB’C’                               Uniting Law

```

That's as far as I am able to get. Did I screw up the truth table, resulting in incorrect minterms, or did I miss something?

Appreciate the help!

# Answer
The last line is wrong : 1 1 1 1 Should be : 1 1 1 0

But the equations following are correct.

For the simplification : BC’ + B’C + AB’C’ = BC' + B'.(C+AC') = BC'+B'.(C+A)=BC'+B'C+B'A

(I don't know the name of the rules used, there is some associativity, "X+X'Y = X+Y", etc...)

--- edit ---

Let's prove that X+X'Y = X+Y

Using :

* A = A.B + A.B'
* A = A+A
* A + AB = A.(1+B) = A
* A + A' = 1

X+X'Y = XY+XY'+X'Y = Y(X+X') + XY' = Y + XY'

Repeating (A=A+A) :

X+X'Y = X+X'Y + X+X'Y = X+X'Y + Y+XY'

= X + Y + X'Y + XY'

= X+XY' + Y+X'Y

= X + Y
> 1 votes

# Answer
If you're in CDA 3103, I just got done with this. What I did when I got to where you were is take the C' out via the distributive law, then use the absorption law on the inside of the parentheses. Good luck!
> 0 votes

# Answer
Rewriting TEMLIB's answer, since it should be C and not B:

BC’ + B’C + AB’C’

= BC' + C'(B+AB') --\> Associativity Law

= BC'+ C'(B+A) --\> Absorption Law

= BC' + B'C + AC' --\> Distributive Law

And that should be your answer
> 0 votes

---
Tags: logic
---


# Question
Title: How to pick a good structural induction hypothesis
(Full disclosure: homework question)

Let $M = (Q, \Sigma, q\_0, A, \delta)$ be a finite automaton. The extended transition function $\delta^\*$ is defined as follows:

1. $\forall q \in Q$

$\delta^\*(q, \Lambda) = q$
2. $\forall q \in Q, y \in \Sigma^\*, \sigma \in \Sigma$

$\delta^\*(q, y \sigma) = \delta(\delta^\*(q, y), \sigma)$

I am attempting to prove the following statement $\forall x,y \in \Sigma^\*$:

$\delta^\*(q, xy) = \delta^\*(\delta^\*(q, x), y)$

It seems pretty obvious from an intuitive standpoint. Since the definition of $\delta^\*$ states that for all $y \in \Sigma^\*, \sigma \in \Sigma$

$\delta^\*(q, y\sigma) = \delta(\delta^\*(q, y), \sigma)$

And since the base case of $\delta^\*$ is (using $\Lambda$ as the empty string)

$\delta^\*(q, \Lambda) = q$

That means $\delta^\*(q, y)$ is just a bunch of nested $\delta^\*$ applications with the first symbol of $y$ on the innermost application, and the last symbol of $y$ on the outermost application. E.g. if $y = y\_1y\_2y\_3$, then

$\delta^\*(q, y) = \delta^\*(\delta^\*(\delta^\*(y\_1), y\_2), y\_3)$

I'm not very experienced at writing proofs, so I'm not sure how to go about setting up the basis case, induction hypothesis, etc. I can prove the first equation for $xy = \Lambda$ as the basis, but I don't know what to do beyond that.

# Answer
> 2 votes
This is a (moderately sketchy) outline of the induction. As it's a structural induction (a generalisation of the familiar, standard induction), we need the object we're inducting over to have a recursive definition. In this case we'll induct over the string $y$, and we can define a string (over an alphabet $\Sigma$ as:

1. $\lambda$ is a string.
2. If $s$ is a string and $\sigma \in \Sigma$, then $s\sigma$ is a string.

We'll steal the normal notation and say that a string constructed in this way is in $\Sigma^{\ast}$ of course. (This level of formalism can be left implicit, it's just nice to see it a few times to help with the understanding of what the proof structure is). Normal mathematical induction can be done in a similar way, where the recursive structure is the Peano version of the naturals, so we're actually on familiar ground here.

Then the proposition you want to prove is

$$ \forall q \in Q, x,y \in \Sigma^{\ast},\\,\\, \delta^{\ast}(q,xy) = \delta^{\ast}(\delta^{\ast}(q,x),y) $$

We will "prove" this by structural induction over $y$.

So then we have a base case for every base case of the recursive definition. In this case there's only one, $y = \lambda$.

**Base Case**

$$\Sigma^{\ast},\\,\\, \delta^{\ast}(q,x\lambda) = \delta^{\ast}(\delta^{\ast}(q,x),\lambda)$$

(You get to fill in the gaps of course, but this one should be reasonable clear.)

Then we have an induction hypothesis and step for every recursive case in the recursive definition, again just like induction over the naturals, we only have one case, so things are nice and simple.

**Inductive Case**

$$ \forall q \in Q, x,y \in \Sigma^{\ast}, \sigma \in \Sigma ,\\,\\, \delta^{\ast}(q,xy) = \delta^{\ast}(\delta^{\ast}(q,x),y) \rightarrow \delta^{\ast}(q,x(y\sigma)) = \delta^{\ast}(\delta^{\ast}(q,x),(y\sigma)) $$

That is, if you know that it's true for $y$, prove that it's true for $y$ plus one more character $\sigma$ (again, we're lucky that the structure is very similar to the natural numbers).

# Answer
> 2 votes
Hint: Prove the identity $\delta^\*(q,xy) = \delta^\*(\delta^\*(q,x),y)$ by induction on $|y|$ (the length of $y$).

---
Tags: finite-automata, proof-techniques, induction
---


# Question
Title: Let A,B be languages. If A is decidable and B undecidable, then A reducible to B
So I'm learning for an upcoming exam and there's a specific problem which I can't show:

> Let A be decidable and B undecidable, then $A \le B$

Can someone give me a hint how to solve that? Furthermore, does that mean, that every decidable language is reducible to an undecidable language?

# Answer
The hint is that your reduction can compute any computable function of its input. Whether an instance of $A$ is a "yes" or a "no" instance is computable by construction.

And, yes, that means that every decidable language is reducible to every undecidable language. It means that because you've assumed nothing about $A$ and $B$ except decidability of $A$ and undecidability of $B$.
> 0 votes

---
Tags: computability, reductions, undecidability
---


# Question
Title: Proof via induction for small-step semantics
I'm doing a course in Computer Programming Languages and I'm trying to prove the following (roughly following Pierce's Types and Programming Languages book):

if $t \rightarrow^\* t'$ then $if\\; t\\; then \\; t2 \\; else \\; t3 \rightarrow^\* if\\; t'\\; then \\; t2 \\; else \\; t3$

I'm a little confused about where to start; as far as I know, I'm supposed to define a base case, then prove it via induction.

I've started my proof by assuming these base cases:

$P(\frac{}{true \rightarrow^\* true})$ and $P(\frac{}{false \rightarrow^\* false})$.

I'm stuck at this point, and I don't really how know to proceed.

edit: I've added the syntax in an effort to clear things up.

# Answer
The induction should be on the derivation of $t \to^\* t'$:

* If $t \to t'$ in one step, then we get the desired result by the E-IF rule.
* Suppose $t \to^\* t'$ because $t \to t'' \to^\* t'$. By the E-IF rule we have $$(\mathtt{if}\\;t\\;\mathtt{then}\\;t\_2\\;\mathtt{else}\\;t\_3) \to (\mathtt{if}\\;t''\\;\mathtt{then}\\;t\_2\\;\mathtt{else}\\;t\_3)$$ and by the induction hypothesis $$(\mathtt{if}\\;t''\\;\mathtt{then}\\;t\_2\\;\mathtt{else}\\;t\_3) \to^\* (\mathtt{if}\\;t'\\;\mathtt{then}\\;t\_2\\;\mathtt{else}\\;t\_3).$$ These two together give us the desired $$(\mathtt{if}\\;t\\;\mathtt{then}\\;t\_2\\;\mathtt{else}\\;t\_3) \to^\* (\mathtt{if}\\;t'\\;\mathtt{then}\\;t\_2\\;\mathtt{else}\\;t\_3).$$
> 4 votes

---
Tags: programming-languages, proof-techniques, semantics, operational-semantics, types-and-programming-languages
---


title: Math in computer science is hard?

text:
# Question
Title: Math in computer science is hard?
I am in High School (P.R.) and I am a regular person in math. Should I try computer science?

# Answer
> 5 votes
This is a very subjective question, but generally speaking, a computer science degree is (arguably) a mix of the "mathematical" and "engineering" aspects of computer science (there are also "scientific" aspects, but they are hardly usually encountered in undergraduate studies). **The shared aspects** include basic mathematics such as calculus and linear algebra. **"Mathematical" computer science** is discrete mathematics, automata theory, computability, computational complexity, algorithms, data structures and so on. **"Engineering" aspects** include programming computer organization, operating systems, databases, and so on. **Advanced topics** such as machine learning and computer graphics are (in my view) engineering topics which are relatively mathematical, though usually require continuous mathematics rather than discrete mathematics.

If you agree to this picture, then the conclusion is that computer science is less mathematical than mathematics. Computer programmers typically need to know a very small amount of mathematics. Indeed, even an understanding of mathematical induction is probably beyond what is needed. Most of your fellow classmates will probably have modest mathematical skills, so unless you have mathophobia, I think computer science is within your means.

# Answer
> 2 votes
I am currently doing a undergraduate degree in Computer Science, Computational and Applied Mathematics and Information Systems. I also have worked for a small time in business based software engineering. What Yuval said is true, Computer Science does require less mathematics than a pure-maths degree or even electrical engineering but some of the maths you may encounter will be a bit harder and theoretical.

Depending on your university, the requirements for computer science may also be different. Some universities require a high maths component like multi-variable calculus, statistics and Linear algebra while other may only require some functional concepts such as single variable calculus and some basic algebra. Depending on where you want to go with the degree at the end of your studies having a mathematics background may or may not be useful.

In research, R&D jobs and more physics and optimisation based jobs mathematics is a must but in the business realm unless you are doing specialised work, a background in theoretical mathematics is not really required.

---
Tags: education
---


title: CPU Performance

text:
# Question
Title: CPU Performance
Please, help me to understand the mathematics behind the following formula of CPI. Why do we calculate CPI the way it's done on the pic?

# Answer
> 3 votes
CPI is the average number of cycles per instruction. The CPI is the expected value of $C(R)$, where $R$ is a random instruction, and for an instruction $r$, $C(r)$ is the number of clock cycles that $r$ takes. The table gives you the distribution of $R$ and the function $C$, from which you can calculate the expectation according to its definition (which matches the intuitive concept of average number of cycles per instruction), namely $$ \mathbb{E}\[C(R)\] = \sum\_r C(r) \Pr\[R = r\]. $$ That's the computation detailed in the answer.

# Answer
> 0 votes
CPI is a statistical calculation used to determine how many cycles some algorithm (series of instructions) will take. It is not really CPU performance by itself. If you take the identical algorithm and calculate it's CPI on multiple CPUs then those values can be used to compare CPUs although it will not be a strong indication of a CPUs performance due to built in optimisations in CPUs which may skew the results and not really show the highest performing CPU.

CPI is better for comparing different algorithms used to work out similar values on the same CPU. Rather than looking directly at an algorithm's complexity one could calculate its CPI which can be useful when only a rough estimate is needed and the algorithms in question are very complex in nature and therefore their complexities and the amount of computational time they take to complete is very difficult to work out.

CPI is however a statistical result on experimental data which within computer science, is quite unreliable. An analytical approach would be much better in determining a much more reliable result although this may be too complex to figure out or take too much time. A way to make CPI more accurate would be to take multiple CPI values for the same algorithm and use different statistical calculations like the mean to work out a more accurate result.

---
Tags: performance
---


# Question
Title: Simple question: Pushdown automata transition
I am currently constructing pushdown automata. can I push/pop alphabet more than two in a transition??

For example, $\delta$(a, a/aaa) means, in the state of input alphabet 'a' and stack point 'a' (there is only one item 'a') then it can push two more item 'a' on the stack so that there is three a's in the stack.

# Answer
> 1 votes
This depends on the formalism you are using.

As a "abstract data structure" you would have simple instructions like push(symbol), pop, top, isempty that you then can program as an add-on to a finite state automaton.

In standard formal language theory one uses a single instruction of the form you describe $(p,a,A,q,\gamma) \in \delta$ means: in state $p$ with $A$ on top of the stack we can pop $A$ and push the symbols $\gamma$ and move to state $q$. Thus we can indeed push several symbols at once, and we always pop one. With this single instruction we can also pop a symbol (by not pushing anything back) or keep the stack unchanged (by pushing back what has been popped).

In the Sipser book the formalism is different for instance.

---
Tags: pushdown-automata
---


# Question
Title: What happens when there is a branch mispredict and an interrupt occurs?
There is a branch mispredict and while executing the false code, an interrupt occurs (for example a keyboard interrupt). The EPC (register that holds the return address) now holds the wrong return address (after the interrupt handler has finished, it would return in code that wasn't even meant to be executed). How do CPUs deal with this problem?

# Answer
> 5 votes
All instructions in the processor are executed speculatively and *every* instruction that is fetched after a mispredict needs to be cancelled without allowing any of its effects to become externally visible. This is done with register renaming and a reorder buffer that commits instruction effects in-order. Instructions from asynchronous interrupt handlers are handled the same way, the main difference (and complexity) being how you refetch them after the mispredict causes them to get cancelled.

Example: you fetch the branch at the address $B$, mispredict its target as $M\_0$, and start fetching $M\_0, M\_1, \cdots, M\_n$. At this point the fetch unit realizes that an asynchronous interrupt, starting at address $I\_0$, needs to be handled and proceeds to set $M\_{n+1}$ as the *predicted* `EPC`, and fetch $I\_0, I\_1, \cdots, I\_m$. (Note that we've only set the *predicted* `EPC` to $M\_{n+1}$, not the "real" (externally visible) `EPC`.) Now the execution unit finally realizes that the branch at $B$ was mispredicted and that the correct branch target was $T\_0$.

At this point we must mark *all* the instructions $M\_0, M\_1, \cdots, M\_n, I\_0, I\_1, \cdots, I\_m$ as "cancelled." Luckily none of them have been committed because they are all behind $B$ in the reorder buffer. Then the execution unit sends a signal to the fetch unit that the correct instruction after $B$ should have been $T\_0$, rather than $M\_0$.

At this point the fetch unit must realize that there was an asynchronous interrupt handler that had been fetched but not committed. It could do this, for example, by keeping a counter that is incremented the first time the first instruction of an asynchronous interrupt handler is fetched, and decremented when that instruction retires (is committed). So the fetch unit sets $T\_0$ as the *predicted* `EPC`, starts fetching from $I\_0$ again (a new copy of the instruction at $I\_0$, let's call it $I\_0'$), and proceeds with $I\_1', I\_2', \cdots, I\_m'$. At some point the branch $B$ reaches the head of the reorder buffer and commits. That means that it records $T\_0$ as the correct (externally visible) "next instruction pc".

$B$ is followed in the reorder buffer by a bunch of cancelled instructions, $M\_0, M\_1, \cdots, M\_n, I\_0, I\_1, \cdots, I\_m$, these are not committed, but any resources (e.g., physcial registers) allocated to them need to be returned to the free-register queue. Finally $I\_0'$ reaches the head of the reorder buffer. It commits. As part of committing the externally visible "next instruction pc" is copied into the real (externally visible) `EPC` register.

TL;DR

Register renaming and the reorder buffer make handling mispredicted branches much easier.

---
Tags: computer-architecture
---


# Question
Title: Construction of an NFA knowing only the equivalence classes and some examples of L
> For a certain language $L \subseteq \\{a, b\\}^∗$, IL has exactly four equivalence classes. They are $\[\lambda\]$, $\[a\]$, $\[ab\]$, and $\[b\]$. It is also true that the three strings $a$, $aa$, and $abb$ are all equivalent, and that the two strings $b$ and $aba$ are equivalent. Finally, $ab \in L$, but $\lambda$ and $a$ are not in $L$, and $b$ is not even a prefix of any element of $L$. Draw an FA accepting $L$

How would I draw a finite automaton for this I know there four states a, ab, b, and empty set.

# Answer
> 1 votes
From any class $\[x\]$ move to $\[xa\]$ using letter $a$, and similarly to $\[xb\]$ with letter $b$.

So, from $\[\lambda\]$ we move to $\[a\]$ with letter $a$, and from there to $\[aa\]$ with another $a$. As $a$ and $aa$ are equivalent, in fact state $\[a\]$ equals state $\[aa\]$.

As $a$ is not in $L$, $\[a\]$ can not be a final/accepting state.

Etcetera.

---
Tags: automata, finite-automata
---


title: Verifying a solution vs. finding one

text:
# Question
Title: Verifying a solution vs. finding one
There is an algorithmic problem $A(n)$, where $n$ is the size of the problem.

It is known that, for every candidate solution S, the time it takes to verify whether it is a correct solution to $A(n)$ is $T(n)$.

1. Does this imply a lower bound on the time it takes to find a correct solution to $A(n)$ (e.g. that it takes at least time $T(n)$)? This seems obvious to me, but obvious and true do not always coincide. Since $P \subseteq NP$, the implication probably holds if $T(n)$ means "polynomial time". But does it hold in general, for arbitrary complexity classes?
2. Does this imply any upper bound on the time it takes to the time it takes to find a correct solution to $A(n)$ (e.g. that it can be done in time $2^{T(n)}$)?

# Answer
> 1 votes
You should define carefully what it means to "find a correct solution". In trivial problems, this may be different than verifying. For example, consider the problem of deciding whether a graph is colorable in *some* number of colors. This problem is trivial, since every graph is colorable in $|V|$ colors. Moreover, it is easy to define such a coloring - give a distinct color for each vertex.

However, verifying that a coloring is correct takes quadratic time.

As for an upper bound - if verifying a solution takes time $T(n)$, than going over all solutions will take time $2^{O(T(n))}$, so not exactly $2^{T(n)}$, but close.

---
Tags: complexity-theory, runtime-analysis
---


# Question
Title: Average Time Complexity of Searching An Array
Why is the average time complexity of searching an array $O(n)$? Is it because if the element does not exist, then $n$ searches must be done. If the element is at the end of the array then $n$ must also be done, so $\frac{2n}{2} = n$?

# Answer
> 2 votes
It sounds like you're talking about a linear search. If we assume that the key is equally likely to be in any of the $n$ locations in the array, then the expected location is $\frac{n+1}{2}$. A linear search for this element would then require $O(\frac{n+1}{2}) = O(n)$ time.

---
Tags: algorithm-analysis, runtime-analysis, average-case
---


title: Naive Bayes MapReduce

text:
# Question
Title: Naive Bayes MapReduce
I have the following question to answer in a MapReduce assignment sheet

> The **Naive Bayes classifier** is a widely-used tool for analyzing data. Consider a data set that has $n$ data items, each of which has the same $m+1$ attributes. Each data item is stored as a tuple $$(i,(X\_0,i, X\_1,i, . . . X\_m,i))$$

where $i$ is the key (index) of the item, and the associated value is a tuple with the $m + 1$ attributes of the item. For simplicity, assume that all the attributes are binary, i.e. each $Xj,i$ is either $0$ or $1$.

> To build the Naive Bayes classifier, we need to compute the set of conditional probabilities $$Pr\[X\_j = x|X0\]$$

These probabilities can be computed from **counts**.

$$Pr\[X\_j = x|X\_0 = b\] = \frac{C\[X\_j = x \text{ AND } X\_0 = b\]}{C\[X\_0 = b\]}$$

> where $C\[\text{cond}\]$ counts the number of tuples from the input that satisfy the condition $\text{cond}$.
>
> Describe how the probabilities needed for a Naive Bayes classifier could be computed using the **MapReduce** model. Assume that $n$ is large (say, $n = 10^9$), while $m$ is small(say, $m = 10$).
>
> How many rounds does your solution require?

My approach -

> I assume that $X\_j$ here means the sum of $X\_j$ attribute column fields across all rows. So using the **MapReduce model**, we can take subsets of tuples and split them over different machines for the **Map stage**. For each tuple, **if** $X\_0$ is $1$ then we can emit the key-value pair $(0,1)$, **if** $X\_j$ is $1$ we can emit $\mathrm{KVP} (j, 1)$ and **if** *either* $X\_0$ or $X\_j$ are $1$ **then** we can emit $(0j, 1)$. As $m$ is small this production of key-value pairs for each tuple should take constant time.

After this once similar keys are shuffled together, in the Reduce stage we can simply count up the totals for each key and use the following formula -

> $\mathsf{COUNT}(A \text{ AND } B) = \mathsf{COUNT}(A) + \mathsf{COUNT}(B) - \mathsf{COUNT}(A \text{ OR } B)$

and then get the corresponding probabilities. This solution thus requires one round of **MapReduce**.

Does this seem like a reasonable solution or am I interpreting the question wrong?

**EDIT - More specifically, I have the following doubts**

> 1. In the context of the Naive Bayes classifier, is my assumption that $X\_j$ is the sum of the values of entries in the $X\_j$ column across all rows correct?
> 2. In the Map stage is it possible to generate multiple key-value pairs of different types like I did in my answer above? And would it still be counted as one 'round' of **MapReduce**?

# Answer
> 0 votes
Your approach is fine. The idea essentially is the same that gets used in Word Count example in Hadoop \[1\].

\[1\] http://hadoop.apache.org/docs/r1.2.1/mapred\_tutorial.html#Example%3A+WordCount+v1.0

---
Tags: probability-theory, database-theory
---


# Question
Title: How does a regular language satisfies the second condition of the pumping lemma
I'm a little bit confused about the second condition of the pumping lemma which are:

> 1. $|y|\geq1$
> 2. $|xy|\leq p$
> 3. $\forall i \geq 0 : x y^i z \in L$

I don't understand why the length of substrings $xy$ has to be less than the pumping length? Considering the example below:

> Suppose we have a language $L = \\{ w | w ∈ 1^\*0+1^\*\\}$ and a string $s \in L$ which $L$ is a **regular language**.
>
> Let the string $s = 101$ and $S$ can be split into three substring $xyz$ where $y$ can be pumped.

Therefore:

> $x = \text{'1'}$ $y=\text{'0'}$ and $z=\text{'1'}$. It seems that substring $|xy|$ is somehow larger than the pumping length $p$ itself (in this case: $p=1$ since there's only one $0$), Therefore $|xy| \> p$, a contradiction ! Does this mean that the language $L$ in this case is **not regular** ?

Or did I misunderstood something.

# Answer
> 7 votes
The pumping lemma states that if a language $L$ is regular then there exists $p$ such that every word $w \in L$ that is long enough ($\lvert w \rvert \ge p$) can be split as $w = xyz$ such that

1. $|y| \geq 1$.
2. $|xy| \leq p$.
3. For all $i \geq 0$, $xy^iz \in L$.

You give an example of a language $L$ and a string $s \in L$ which can be split as $s = xyz$ such that

1. $|y| \geq 1$.
2. $|xy| = 2$.
3. For all $i \geq 0$, $xy^iz \in L$.

This is a property which is similar to the one guaranteed by the pumping lemma, but perhaps different. The property expressed by the pumping lemma need not be the only property satisfied by a regular language. All the pumping lemma states is that **if** a language is regular **then** it satisfies the pumping property. It does not state that **if** a language is regular **then** the only property it satisfies is the pumping property.

To give an analog, consider the following statement: if $x$ is a multiple of $4$ then it is a multiple of $2$. Here is a "counterexample": $12$ is a multiple of $4$, but it is a multiple of $3$ (rather than $2$). Your counterexample is similar.

Another issue is the pumping length $p$. If you look at the proof, then $p$ is the size of a DFA accepting $L$. In particular, $p$ doesn't depend on $w$. In your case, it's not clear why you assume that $p=1$; in fact, when applying the pumping lemma, you cannot assume anything about $p$. You're just guaranteed that some $p$ exists. In fact, for your language $p \geq 5$, since the minimal DFA has $5$ states.

The condition $|xy| \leq p$ is supposed to help you apply the pumping lemma. For example, if you look at the language with strings $0^n1^n2^m$ for $m, n \ge 0$, without this condition you wouldn't be able to prove that the language is not regular, since the pumped part could always be in the $2^m$ area. The condition $|xy| \leq p$ allows you to locate the pumped part.

This condition isn't always general enough, for example it doesn't work for showing that $2^m0^n1^n$ is not regular. There is a more general version of the pumping lemma which can handle this called Ogden's lemma.

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


title: Random Forest closed loop

text:
# Question
Title: Random Forest closed loop
I'm using the Random Forest algorithm for classification. I have some variable to use as features in input, but I was wondering if I can use the output of the classification itself as input.

Suppose, for example, that I want to classify people in two categories : "criminal" or "honest". In order to do that, I have a vector of three features: the name of the city where the person is born, the number of people that committed crimes in the city where the person is born, and the number of people that live in that city. When I run the algorithm, I will get the classification results $y\_1,y\_2,...,y\_n$ for each input vector $x\_1,x\_2,...,x\_n$.

Now, it would be wrong to add to the input vector a new feature "number of people from the same city who have been classified by the algorithm as criminal"?

My purpose is to run several instances of the algorithm on different datasets and then share the informations gathered in each subset between the different instances. Does it can make sense?

# Answer
This is a cascade classifier. Of course you can do that, but the main disadvantage (that you have to keep in mind) is that your error propagates along your cascade classifiers. So even if you have a very good classifier somewhere towards the end of your cascade, if you feed it with weak features (i.e., the output of the previous layer which was not so good) you should not expect to get a reasonable answer. There is generally another common problem with this method and that's the well-known overfitting effect. However, since you are using different subsets of data to train each classifier it shouldn't be a problem in your case I guess.
> 3 votes

---
Tags: machine-learning, classification
---


# Question
Title: Advantages of adaboost over gentleboost in applications, or vice versa?
I've been researching on AdaBoost and GentleBoost classifiers, but can't seem to find a clear answer to the question:

* What is Adaboost better at classifying in computer vision?
* What is GentleBoost better at classifying?

I've been told that AdaBoost is good for things with soft edges, like facial recognition, while GentleBoost is good for things with harder and more symmetrical features and edges, like vehicles. Is this true? Is there any proof for this or any evidence to back up this claim?

# Answer
Genetellboost is developed to cope with labeling noise, i.e., when some samples are wrongly labeled. Though, it wasn't so successful in that respect, from my experience it is quite good in handling noisy features which are kind of outliers in dataset. That being said, there is no proof for neither of the things that you asked (nor the things that you mentioned are true). In fact, we know that these algorithms are so similar that it is practically impossible to predict which one works better on which dataset. You have to test it and that's it.
> 4 votes

---
Tags: algorithms, reference-request, machine-learning, classification, computer-vision
---


title: I/O in Theory of Computation

text:
# Question
Title: I/O in Theory of Computation
I posted a question "Arbitrary Programs that halt" some days ago and now i think my doubt is a lot more clear.

I concluded that in any arbitrary program that halts, control flow operations, calculation operations ( 2+3 , "1 && 0", etc ) and memory assignment ( x:= "Hello" ) can be easily represented by Models of Computation such as Turing , RAM Machines, Lambda Calculus, etc.

But I/O operations such as reading input from keyboard/mouse/etc, writing output to monitor/speaker/network\_device, don't really seem to have any relation to those models of computation, that is, i can't think of a way to simulate/emulate them there ( the only I/O operation that those models of computation could simulate is writing and reading from memory ) . This reflects the fact that the programming languages were meant to access not only the CPU and the memory but the entire desktop PC ( including its additional I/O devices ).

At the same time, i've some people suggest that those I/O operations correspond to computations, in the Theory of Computation sense, and i'm thinking this is a problem because Turing-complete models of computation were mean't to possibly express ANY computation.

So, there are two possibilities :
1 - Those I/O operations are not really computation and hence Turing-Complete models of computation are not required to express them, and also programming languages ( and our Desktops in general ) are modelling MORE than mere computation, they are modelling Computation + I/O.

2 - Those I/O operations are really "computation" and i simply don't know how to think of simulating them with Turing-Complete models of computation, that is, i can't seem a way to simulate the entire composition of a desktop PC ( CPU + memory + all external devices ) in those models of computation.

The first option seems more plausible to me, but i don't know.

What do you guys think about the relation between those I/O Operations and Computation ?

# Answer
For Turing machines I/O corresponds to using the tapes:

* a disk is a tape which has been rolled up
* keyboard is the input tape
* display is the output tape

A more interesting question is how to model *interaction* between machines using communications channels (that's a form of I/O), especially asynchronous communication. You can look up communicating sequential processes and $\pi$-calculus to learn about computational models that account for communication (and these are not the only ones).

The $\lambda$-calculus is a bit different because it does not have a direct notion of I/O. However, in any programming language we may simulate an input or an output stream by passing around extra lists of chacarters (or bits) which represent input and output streams. Here is an example in Haskell (but using only purely functional part if Haskell without any real I/O):

```
    -- Simulated IO in a purely functional way in Haskell

    -- A dataype of programs which perform simulated IO and return
    -- results of type a
    data SimulatedIO a =
        Result a
      | Output String (SimulatedIO a)
      | Input (String -> SimulatedIO a)

    -- Run a simulated IO calculation on the given input stream.
    -- Return the result, the remaining (unused) input, and output.
    run :: [String] -> SimulatedIO a -> (a, [String], [String])
    run input (Result a) = (a, input, [])
    run input (Output s c) =
      let (x, input', output) = run input c
      in (x, input', s : output)
    run (s:input') (Input c) = run input' (c s)

    -- Example
    greeter :: SimulatedIO Int
    greeter =
      Output "What is your name?" -- ask the user for his name
             (Input (\name -> -- read the name
                Output ("Hello " ++ name) -- greet the user
                       (Result (length name)))) -- return the length of user's name

    -- Execute the example with simulated input ["John", "Banana", "Orange"]
    example = run ["John", "Banana", "Orange"] greeter

    -- the result is
    --
    --    (4, ["Banana","Orange"], ["What is your name?","Hello John"])
    --
    -- 4 because "John" has four characters
    -- ["Banana","Orange"] is the unused input
    -- ["What is your name?","Hello John"] is the output

```
> 7 votes

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


# Question
Title: How to calculate probability of packet loss and drop rate?
In a queuing system (M/M/1) with a finite packet capacity $z$, how do you determine the probability of packet loss if we assume that packets are dropped when the system is full? Packets arrive with a rate $\lambda$ and are served at rate $\mu$ (using the Poisson distribution).

**My attempt at a solution:**

Probability of packet loss = Probability that the system has exactly $n$ packets (i.e., it is at its capacity)?

I also have a formula from my notes where probability of packet loss is approximated at $(1 - \frac{\lambda}{\mu})(\frac{\lambda}{\mu})^z$ (so this is most likely correct but can someone please explain why?).

I'm not sure how to calculate the rate at which packets are dropped. I already know the probabilities $P(n)$ that there are $n$ packets in the system where $n = 0, 1, ..., z$ packets.

# Answer
> 1 votes
If you study **M/M/1** queuing systems you'll probably know that such a queuing system can be seen as a markovian chain with birth rate λ and death rate $\mu$; that is to say that you change your state (and in an **M/M/1** the state is the number of clients in the system) by unitary steps: $-1$ with rate $\mu$ and $+1$ with rate $\lambda$.

It is quite hard and long to explain in a thread like this and for this reason I suggest you to take a look at the markovian chains theory to understand why it works like this. Anyway, I'll try to give you an idea: you can set a basic **fluxus equation** to describe the system:

$$P\[x(t)=k\] \mu = P\[x(t)=k-1\] \lambda$$

and analyzing the transition probabilities you will find: $$ P\[x(t+h)=k+1 | x(t)=k\] = \lambda h + o(h) \\ P\[x(t+h)=k-1 | x(t)=k\] = \mu h + o(h)\\ P\[x(t+h)=k | x(t)=k\] = 1-\lambda h-\mu h + o(h)\\ P\[x(t+h)=k+j | x(t)=k\] = h + o(h)$$

with $h$ defined as very little piece of time.

So, defined $ρ=\frac{\lambda}{\mu}$ as the **load factor** of the system, you will find that (recalling the **total probability theorem**):

$$ P\[x(t)=k\] = (1-ρ) ρ^k $$

If you take a look at this result, you will recognize the answer to your question: if the system is a blocking system with blocking capacity $z$, the probability of packet loss is the following:

$$P\[z\\,\text{clients in the system}\] = P\[k\\,\text{clients in the system}\] = P\[x(t)=k\] = (1-ρ) ρ^k$$

Is it ok? :)

# Answer
> 0 votes
Ok! Now if you have the "packet loss probability" (or in other words "the packet blocking probability", that from now I will call $P\_\mathrm{blk}$) you can simply calculate the **packet loss rate** as: $$\lambda P\_\mathrm{blk}$$

Otherwise, if you want to calculate the average rate of **admitted packets** you can simply do: $$\lambda (1 - P\_\mathrm{blk})$$

I think it should be clear why I can do this simple calculation. Knowing the $P(n)$ probabilities you can calculate $P\_\mathrm{blk}$ as: $$P\[x(t)=k\]=(1−\rho)\rho k$$

as I said before. Of course the rate is proportional to the load factor because this parameter gives how much the system is "load" in terms of occupation and traffic during the time, in stationary conditions. If you have a load factor very close to 1 you are much more likely to be in an unstable condition and go to the blocking condition. For M/M/1 systems it is good to have very low load factor :)

I hope you can now solve your problem!

---
Tags: probability-theory, computer-networks, priority-queues
---


# Question
Title: Why system calls via interrupts are slow and thus we have SYSENTER/SYSEXIT instructions?
As far as I understand we got SYSENTER/SYSEXIT instructions because system calls via interrupts were slow (right? I might be wrong though). Therefore my question is why system calls via interrupts are slow? And how do we optimize them via SYSENTER/SYSEXIT instructions? Thank you

# Answer
> 4 votes
There is the general rule about interrupts being slow, and the particular case of x86 CPUs.

* x86 have had several ways to enter kernel mode : Call gates, interrupts. They are complex, microcoded instructions, requiring many register save operation and protection checks. SYSENTER/SYSEXIT are just optimised methods : For example, since the 80286, 4 protection levels were available, but rarely used (except, IIRC, by OS/2 ?) : SYSENTER/SYSEXIT support only ring 0 (user) to ring 3 (kernel)
* On many instruction set architectures, software interrupts are used to enter kernel mode from user code. These instructions can be optimised, but, in the simplest implementation, they are handled like external hardware interrupts or MMU faults. They are slow because the pipeline must be flushed, prefetched instructions must be discarded, before jumping to the interrupt vector.

# Answer
> 3 votes
A software interrupt (or call gate, for that matter) requires pushing a bunch of stuff onto the stack, and popping when the OS returns. SYSENTER/SYSEXIT does not.

---
Tags: operating-systems
---


# Question
Title: Integer Programming Traveling Salesman - Checking if Tour is Complete
I'm reading a Wikipedia article on the Traveling Salesman problem as an Integer Programming formulation (http://en.wikipedia.org/wiki/Travelling\_salesman\_problem). The authors have all their constraints and I don't understand the final one. The following statement is in there.

> To prove that every feasible solution contains only one closed sequence of cities, it suffices to show that every subtour in a feasible solution passes through city 0 (noting that the equalities ensure there can only be one such tour). For if we sum all the inequalities corresponding to x\[ij\]=1 for any subtour of k steps not passing through city 0, we obtain: n * k \<= (n-1) * k

I specifically don't understand the "For if we sum all the inequalities..." part. Sum which inequalites?

A little further the author states the following.

> Without loss of generality, define the tour as originating (and ending) at city 0. Choose u\[i\]=t if city i is visited in step t (i, t = 1, 2, ..., n). Then u\[i\]-u\[j\] \<= n-1, since u\_i can be no greater than n and u\_j can be no less than 1; hence the constraints are satisfied whenever x\_{ij}=0. For x\_{ij}=1, we have:
>
> u\[i\] - u\[j\] + nx\[ij\] = (t) - (t+1) + n = n-1,
>
> satisfying the constraint.

I guess I don't understand how this detects that we pass through all the nodes.

---

Okay, looking at this some more, I think I've discovered a bit more. This equation is the MTZ formulation (Miller-Tucker-Zemlin) and it's geared at finding subtours.

Having digested some snippets from papers like Gabor Pataki's *Teaching Integer Programming Formulations using the Traveling Salesman Problem*, there's a statement in there that if a subtour did not contain node 1, then along this subtour the u\[i\] value would have to increase to infinity. I'm not 100% sure, but what I think this means is that if you had nodes 3 and 4 linked together (edge from 3 to 4 and another from 4 to 3), you would have the following constraints...

$u\_3 - u\_4 + 1 \le (n-1)\*(1-x\_{34}) \le 0$

$u\_4 - u\_3 + 1 \le (n-1)\*(1-x\_{43}) \le 0$

The contradiction here is that $u\_4$ is one step greater than $u\_3$ which is one step greater than $u\_4$.

# Answer
First, an overview is as follows:

> The last constraints enforce that there is only a single tour covering all cities, and not two or more disjointed tours that only collectively cover all cities.
> To prove this, it is shown below (1) that every feasible solution contains only one closed sequence of cities, and (2) that for every single tour covering all cities, there are values for the dummy variables $u\_i$ that satisfy the constraints.

Interpreting the last constraints as a theorem: $$u\_i - u\_j + n x\_{ij} \le n - 1 \quad 1 \le i \neq j \le n \Leftrightarrow \text{there is only a single tour covering all cities.}$$ then part (1) is the *necessary* condition ("$\Rightarrow$"): every *feasible* solution in ILP implies a unique tour; and part (2) is the *sufficient* condition ("$\Leftarrow$"): every single tour corresponds to (at least) one feasible solution.

---

For your questions:

> I specifically don't understand the "For if we sum all the inequalities..." part. Sum which inequalities?

We aim to prove the part (1): every feasible solution contains only one closed sequence of cities. To this end, we should exclude the case that two or more disjointed subtours that only collectively cover all cities: For instance, subtours $0 \to 1 \to 2 \to 0 \bigcup 3 \to 4 \to 3 \bigcup 5 \to 6 \to 5$ covering all cities $0, \cdots, 6$ is not a legal tour, but it does *satisfy* the first and the second set of *equalities*.

Consider any subtour which does not pass through the city $0$ and sum the inequalities of $u\_i - u\_j + n x\_{ij} \le n - 1 \quad 1 \le i \neq j \le n$ *for the subtour* (taking $3 \to 4 \to 3$ as an example):

Summing up $$(u\_3 - u\_4 + n \cdot 1 \[x\_{34} = 1\] \le n-1) \text{ and } (u\_4 - u\_3 + n \cdot 1 \[x\_{43} = 1\] \le n-1),$$ we have $$2n \le 2 (n-1).$$

Generally, for a subtour (which does not pass through the city $0$) with length $k$, we will get $nk \le (n-1) k$. Contradiction.

Therefore, every subtour must pass through the city $0$. Further, the first and the second equalities enforce that all subtours must be disjoint. As a consequence, there can only be a single tour covering all cities.

> I guess I don't understand how this detects that we pass through all the nodes.

As I mentioned in the "overview", part (2) is the *sufficient* condition: We are *given* a single tour covering all cities, we aim to show that this tour corresponds to some feasible solution in this ILP. Because such a given tour trivially satisfies other constraints which do not involve these $u\_i$ variables, it suffices to show that there are values for $u\_i$ that satisfy the last constraints. This is proved by construction: Choose $u\_{i}=t$ if city $i$ is visited in step $t$.
> 2 votes

---
Tags: traveling-salesman, integer-programming
---


# Question
Title: Whats is the meaning of polynomial run-time in input size ?
If an algorithm runs in exponential time with exponential input then we say it runs in polynomial time ? Why ? Doesn't the algorithm run in exponential time anyway ? How the input size affects ? Thanks.

# Answer
I think I understand the question enough to answer it. Yes polynomial time is the time the algorithm takes *relative* to the size of the input. So if your input has size $n$, PTIME means the running time is a polynomial in $n$. Sure if you replace $n$ with some exponential $n=e^p$ you get an exponential time relative to $p$ (assuming the algorithm was not running in constant time). But that does not invalidate the concept of polynomial time anymore than saying that $f(x)=2x$ is a linear function but you can substitute $x$ with $y^{y^y}$ *on both sides*, i.e $f(y^{y^y})=2y^{y^y}$; it is an intrinsic property of $f$ of being linear *in its argument*.

This is further discussed on an example at https://cstheory.stackexchange.com/questions/18756/whats-the-meaning-of-input-size-for-3-sat

This issue of having to express the input size as a function of another "quantity" does occur (implicitly) in the context of reducing one problem to another in order to feed it to an existing algorithm. In that context, in order to avoid the obvious gotcha that would "prove" an EXPTIME problem is a PTIME one by using an exponential-size encoding, only polynomial-time reductions are allowed. So, if $p$ is the size of a problem, you can encode it in PTIME as another problem of size polynomial in $p$. But you can't encode it (taking only PTIME) as problem of exponential size in $p$.
> 2 votes

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


title: FP^NP-complete problems

text:
# Question
Title: FP^NP-complete problems
Is there any other standard FP^NP-complete problem other than the Traveling Salesman Problem? For instance, in the canonical propositional logic?

# Answer
TSP is actually OptP-complete and so are many other optimization problems, including Knapsack, MAX-SAT, 0-1 Integer Linear Programming. This class and proof technique is largely the work of Mark Krentel; orig paper STC'86. The journal version of the paper has more details, including the fact that OptP is subclass of FPNP.

LEX-MIN-SAT, finding the lexicographically smallest satisfying assignment, is OptP-complete under metric reductions. There's also an analogue of Schaefer's dichotomy theorem for LEX-MIN-SAT proved by Reith and Vollmer http://arxiv.org/pdf/cs/9809116.pdf

I think is almost a research-level, or at least graduate-level question, by the way.
> 5 votes

---
Tags: complexity-theory, complexity-classes, propositional-logic
---


title: Introduction to number theory

text:
# Question
Title: Introduction to number theory
What is the best book for a beginner in Introduction to number theory?

I am new to this field and getting deeper into cryptography, so I think reading some intro books about number theory can be of help.

# Answer
> 1 votes
If you want to go deeper into cryptography and number theory, then of course you start here: Neal Koblitz, A Course in Number Theory and Cryptography.

---
Tags: number-theory, computer-algebra
---


# Question
Title: How to implement mutex on single processor (single core) system other than using spinlock
How does one implement mutex on a single processor system without using spinlock mechanism. Mutex is to be implemented in user space (for any user level library like pthread lib for example).

# Answer
> 3 votes
It is impossible to implement a mutex completely in userspace unless you have special CPU instruction that could simulate a semaphore or a lock (some "test and increment if true" instruction). pthread in Linux goes through the kernel to implement the mutex.

# Answer
> 2 votes
On a single processor system a spin lock won't work at all. There's only one processor so if that one processor tries to acquire a locked mutex, it will start spinning, and there will be no other processor available to unlock the mutex. The processor will be stuck spinning forever.

Rather on a single processor system one needs to use two other techniques. First, if the mutex is supposed to protect some data structure during interrupt handlers, then you achieve mutual exclusion simply by turning off interrupts during the critical section.

For mutexes used for "normal" threads when a thread (let's call it "A") tries to acquire a mutex and finds it locked, it calls into the scheduler which selects some other thread(s) to run for a while before retrying to run thread A. This can actually be viewed as a form of spinning (test the lock, find it busy, call the scheduler to run some other thread, eventually come back to me, test the lock again, and so on ...). So a slightly more sophisticated approach is to associate a queue with each mutex. When thread A tries to acquire the mutex and finds it locked, it places itself on the queue associated with the mutex, then calls the scheduler, which selects some other thread(s) to run for a while. Eventually one of those other threads unlocks the mutex. At that point the thread that unlocked the mutex removes thread A from the queue and places thread A in the schedulers "ready-to-run" list. Eventually the scheduler will decide to run thread A again, thread A will again try to acquire the mutex, and (unless someone else has locked the mutex in the meantime) will find it unlocked this time.

---
Tags: operating-systems, threads
---


# Question
Title: What is determinism in computer science?
I was asked if my computer program (in Java) was deterministic. I'm wondering how could it be not? There is no such thing as a non-deterministic Java program right? Even if I use a random number generator to make branching unpredictable, it is still really non-deterministic (but harder to prove so).

# Answer
> 6 votes
I'd like to expand on @jmite's mention of non-determinism due to threading. "Is your program deterministic?" is a question that might well be asked in a parallel programming class, and the answer with many multi-threaded programs is often "no."

In most multi-threaded programs the exact interleaving of instructions from different threads is *indeterminate*. We can't *determine* the order in which instructions are interleaved just by using the program and its input. To actually figure out what order the instructions would interleave would require us to know the exact state of the caches and branch predictors and tlbs on every core, when all the external interrupts occur to the picosecond (mouse movements, external network traffic, timer interrupts) the exact position of the disk drive heads with respect to the spinning platter, the temperatures of every transistor (at least the transistors that drive the asynchronous busses) and the small fluctuations in voltage coming from the wall socket or battery.

Given that every time you run your multithreaded program the exact instruction interleaving is different, we are really interested in:

> can the multi-threaded program's *output* be exactly determined knowing only the input and the code?

For example, the following multithreaded program is non-deterministic:

```
thread A                    thread B
acquire mutex m             acquire mutex m
x = 0                       x = 1
release mutex m             release mutex m
print x

```

This program will sometimes print "0" and sometimes print "1".

The following multithreaded program is determinisitic

```
thread A
x = 0
fork thread B               thread B
acquire mutex m             acquire mutex m
x = x + 1                   x = x + 2
release mutex m             release mutex m
join with thread B          finished
print x

```

This program would usually be considered deterministic. It always prints "3", although we don't know if the sequence of values of `x` was 0, 1, 3 or 0, 2, 3.

Things get even more interesting when we are talking about data structures like binary trees. In a binary tree the exact shape of the tree usually depends on the exact order in which nodes were added. But often you are using the binary tree to represent some abstract data type (like an ordered sequence) in which many different tree shapes represent the same abstract value.

For example, the binary trees

```
  0          1          2
   \        / \        /
    1      0   2      1
     \               /
      2             0

```

all represent the same ordered sequence "0, 1, 2". So most people would still call this ordered-sequence type *deterministic* although if you have to debug the program (and thus deal with different runs having different actual representations of the data structure) you might also call it *annoying*.

# Answer
> 3 votes
You can create true randomness in a computer by measuring the decay of a radioactive source and using that as the basis for a random number generator. So yes, there is such a thing as a non-deterministic computational automaton.

Even if there weren't, you can still *simulate the appearance of actual randomness* in a computer. That's what makes things like Monte Carlo simulations possible. The quality of such randomness can be measured with statistical techniques.

A **deterministic program** would behave the same way each time it is executed, or would behave in a manner consistent with its logical design. That is, given the same input over multiple executions, the same output will always occur. This is also true of programs that employ pseudo-random number generators; given the same seed and the same user input, the program will behave the same way each time.

Note that there are ways to randomize a pseudo-random number generator so that you cannot predict its output. One common way is to take the six or so least significant digits of a high-resolution clock when the user presses a key, and use that as the seed to the pseudo-random number generator.

# Answer
> 3 votes
So, here's the problem. There are two different and competing meanings for deterministic in Computer Science.

* Deterministic = uniquely defined. This is the definition used mostly in automata theory, complexity theory, theory of computation. A deterministic computer/Turing Machine/automaton is one for which, given the current input and state, there is only one action that can be taken.

This is defined in contrast to non-deterministic machines, where, in a given state, the machine has multiple possible actions/transitions that can be taken. A machine accepts some input if there is exists some accepting computation. Alternately, you can view non-deterministic machines as having some magic decision procedure which tells them which action to choose, or as a machine that has infinite parallelism and tries multiple options simultaneously.

Real computers are deterministic in this sense, but can simulate non-determinism, usually through some sort of backtracking search.

Note that there is NOT any randomness occurring in this situation. Either we assume some magic choose which path to take, or we assume we're trying them all in parallel.

* Determinism = Non-random. This is the case that Robert Harvey describes. This definition of determinism is usually what's used in math, statistics, or physics (i.e. quantum physics is non-deterministic).

In computing science, something which is non-deterministic in this sense is usually referred to as stochastic, or randomized. However, the term deterministic/non-deterministic is often used in systems programming to describe threaded programs.

A program that uses random numbers is inherently non-deterministic in this sense, since its output might change for a given input. However, if you view the random seed as input, or view the RNG as input as an infinite stream of numbers, then you could argue that your program is deterministic, since its output is fixed given its input.

Things become complicated when you add threading. Poorly-written multi-threaded programs can be non-deterministic, if their output changes depending on how threads are scheduled. Mutexes, semaphores, etc. all have the goal of making multithreaded programs deterministic, i.e. they give the same result, regardless of how threads are scheduled.

* Conclusion:

Which definition is being used where depends on the context. If you're talking $P =? NP$, then $NP$ is the class of problems solved by a non-deterministic Turing Machine, in the first sense of non-deterministic (infinite parallelism). Likewise, non-deterministic finite automata (NFAs) are non-deterministic in the first sense.

# Answer
> 2 votes
A philosophical (but perhaps less useful answer than those given) is that non-determinism occurs only when your accuracy of measurement falls below the threshold required to be able to be sure of the outcome.

The 'non deterministic' program listed above i.e.

```
thread A                    thread B
acquire mutex m             acquire mutex m
x = 0                       x = 1
release mutex m             release mutex m
print x

```

is only non-deterministic in that there are things happening at a low enough level in the computer stack that you can't measure them (or, in this example, you *could* measure them if you had the right tools but you would normally not expect to do so as part of your code development). There's nothing actually 'random' here, the events leading to one thread/process gaining the mutex over another aren't random but you just don't measure the things affecting which one wins out.

---
Tags: algorithms, terminology, nondeterminism
---


title: MIPS rating formula

text:
# Question
Title: MIPS rating formula
Could you please help me to understand the mathematics behind MIPS (million instructions per second) rating formula?

The formula for MIPS is:

$$ \text{MIPS} = \frac{ \text{Instruction count}}{\text{Execution time} \ \times \ 10^6}$$

For example, there are 12 instructions and they are executed in 4 seconds. So the CPU's performance is $\frac{12 \ \text{instructions} }{4 \ \text{sec}} = 3 \ \text{instr}/\text{sec}$. MIPS would be $3\times10^{-6}$.

> **Question**: How do we go from $3$ instructions per second to millions instructions per second? What is the logic/mathematics behind dividing by $10^6 = 1 \text{ million}$?

# Answer
> 2 votes
Perhaps the unit conversion confuses you?

$$ \frac{i\\,\text{instr}}{t\\,\text{sec}} = \frac{i\\,\text{instr}}{t\\,\text{sec}} \times 1 = \frac{i\\,\text{instr}}{t\\,\text{sec}} \times \frac{\text{millions}}{10^6} = \frac{i}{t \times 10^6} \times \frac{\text{millions}\\,\text{instr}}{\text{sec}} $$

---
Tags: cpu-cache, performance
---


# Question
Title: Fast solution for a combinatorial maximizaton problem
You are given a natural number n (n\<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 (consisted of not necessarily consecutive bits). Now we have to find the maximum number from the numbers in S so that every pair of numbers is "compatible" and I want an example numbers from S with that maximum. Here is an example of the task:

n = 6; S = { 000000, 000001, 000010, 000011, ..., 111110, 111111 }; The maximum number from the numbers in S with that property is 10. Here is an example: 000000, 000011, 110000, 001100, 010010, 001111, 111100, 110011, 101101, 111111

I tried making some greedy solutions but they aren't working on greater n (and I think they can't be made accurate). When I thought of some graph solutions I reached an NP problem (let each binary number is vertex and we have an edge connecting them if they aren't "compatible"; now we have to find the maximum in vertices independent set). The other way I tried is making a bipartite graph with one set of vertices with the binary numbers of length n and the other with the binary numbers of length n-1. We have an edge from the first to the second set if the number from the second could be a substring of length n-1 of the number in the first. Now we have to find the maximum number of vertices from the first set so that their edges do not have any common endpoint vertex but I couldn't think out the solution of this problem and couldn't find it in the Internet.

# Answer
> 3 votes
You seem to be looking for the optimal single-deletion-correcting code of length n. As far as I know, it's an open problem.

This paper states that

1. The Varshamov-Tenengolts code (specifically $VT\_0$) is a good candidate, but there has been no proof of this as of yet. It is the set of all words for which $\sum\_{i=0}^{n} i\cdot x\_i \equiv 0 \mod n+1$ where $x\_i$ is the $i$-th digit in $x$'s binary representation. Its size can be computed as $$\frac{1}{2(n+1)}\sum\_{d\mid n+1 \land 2\not \mid d} \phi(d)2^\frac{n+1}{d}$$. The first few values of the above formula can be found at A000016.
2. The above code has been proven to be optimal for small values of $n$, and to be asymptotically optimal for large $n$.
3. No efficient algorithm has been found to generate/check the optimal code. The largest value of $n$ for which an optimal code is known (and confirmed to be the above) is $9$ (actually $10$).

---
Tags: algorithms, optimization, combinatorics
---


# Question
Title: Need clear explanation to Range updates and Range queries in Binary Indexed trees?
I have gone through few tutorials about how to perform range updates and range queries using Binary indexed tree. I have even gone through Range update + range query with binary indexed trees . I'm unable to understand the need of second tree. In the tutorial http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree :

It says as:

> Consider a range update query – Add $\mathrm{val}$ to $\[i,\dots,j\]$. We will design a sum function, where we consider a summation function for all possible $x$ as following:
>
> $0$ for $0 \leq x \< i$
> $\mathrm{val} * (x - (i - 1))$ for $i \leq x \leq j$
> $\mathrm{val} * (j - (i - 1))$ for $j \< x \< n$

I just want to know the following things:

If $i\leq x\leq j$, why is the sum $\mathrm{val}\*(x-(i-1))$ ?

I'm not able to appreciate the entire algorithm.

Could someone explain me using examples?

# Answer
Consider an array $A\[0, \cdots, n-1\]$ and its cumulative sum array $A'$. Suppose we want to make a range update of $v$ to $A\[i, \cdots, j\]$. Then $A'$ is changed in the following way:

* For $0 \le x \< i$: $A'\[x\]$ does not change;
* For $i \le x \le j$: $A'\[x\]$ is added by $v \ast \left( x-(i-1) \right)$;
* For $j \< x \< n$: $A'\[x\]$ is added by $v \ast \left( j-(i-1) \right)$.

---

**For your question**, why is $v \ast \left( x-(i-1) \right)$?

First, the specification of range update of BIT `Range-Update(v,i,j)` means adding value $v$ to each element of $A\[i, \cdots, j\]$.

Secondly, $A'$ stores the cumulative sums of $A$. For $A'\[x\], i \le x \le j$, its increment consists of the cumulatively added values preceding it, which is, along with $v$ of itself, $v \ast \left( x-(i-1) \right)$. The increment of $A'\[x\], j \< x \< n$ is the same as that of $A'\[j\]$, which is $v \ast \left( j-(i-1) \right)$.

---

An example from the post you mentioned is as follows (thanks @JS1; the indices starts from 1 for consistency):

Suppose you had an empty array:

```
0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

```

And you wanted to make a range update of +5 to \[4..8\]:

```
0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)

```
> 1 votes

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


# Question
Title: Language described by inverting accepting states of NFA
Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean that rejecting states become accepting states and accepting states become rejecting states.

Is there a nice expression for such a language reference to the original NFA language?

# Answer
> 4 votes
The answer is basically in the question you link, but to make it explicit: no, there is no "nice expression" since anything can happen.

For an example, let $L$ be any regular language; let's say it's accepted by NFA $A\_L$:

\[source\]

Now consider this automaton $A'\_L$:

\[source\]

Clearly, $A\_L$ and $A'\_L$ accept the same language $L$. However, the automaton obtained from flipping $A'\_L$ accepts $\Sigma^\*$ (since $s$ is accepting in this one).

So we see that we need further assumptions on the automata if flipping is to yield anything meaningful. For instance, if we require that for every input, either all computations are accepting or all are rejecting -- a property $A'\_L$ above does not have -- then flipping yields the complement of the original language.

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


# Question
Title: Complexity of 4-coloring a map with constraints
The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color.

In fact, there exists a quadratic algorithm for 4-coloring planar graphs.

Suppose you are given a map (e.g. the world's map) and a list of $k$ constraints, e.g. Greece is colored blue, and Spain, Italy and Uruguay are red.

> **Can this problem be solved in poly time if $k$ is part of the input?**
>
> **Can this be solved in poly time if $k$ is fixed (i.e. is the problem fixed parameter tractable with respect to $k$)?**

# Answer
> 3 votes
It is $NP$-complete. Consider a graph $G$ which is modified by duplicating every vertex, and connecting every duplicate vertex to its original. Then if we constrain all the duplicate vertices to a fixed color, then the thus obtained graph is 4-colorable (with constraints) if and only if the original graph is 3-colorable.

# Answer
> 2 votes
To add to the other answer, the name of the problem you are interested in is *precoloring extension*: given a graph $G$ with some precolored vertices and a color bound $\ell$, can the precoloring of $G$ be extended to a proper coloring of all vertices of $G$ using not more than $\ell$ colors? This problem is NP-complete for planar bipartite graphs with fixed $\ell = 3$ as shown by Kratochvíl \[1\].

The problem has also been investigated in a parameterized setting, for instance, when either the number of precolored vertices or the number of colors used in the precoloring is restricted to be at most $k$. Both cases are W\[1\]-hard, see e.g. \[2\].

---

\[1\] Kratochvíl, Jan. "Precoloring extension with fixed color bound." Acta Math. Univ. Comen 62 (1993): 139-153.

\[2\] Marx, Dániel. "Parameterized coloring problems on chordal graphs." Theoretical Computer Science 351.3 (2006): 407-424.

---
Tags: complexity-theory, graphs, colorings, parameterized-complexity, planar-graphs
---


title: Omega-Language to Büchi automaton

text:
# Question
Title: Omega-Language to Büchi automaton
I'm currently preparing a presentation about LTL and a book says that the language $L = (a(a \cup b))^\omega$ cannot be described by any LTL (or FO) formula which is understandable but how does the corresponding Büchi automaton $\mathcal{A}$ look like with $L(\mathcal{A}) = L$?

# Answer
Intuitively, the language is exactly the set of words that have $a$ in all the odd places. Thus, the corresponding NBW (in fact, $DBW$) has three states, $q,s,r$, where $q$ is initial, $s$ is accepting, and $r$ is a rejecting sink. The transitions are $\delta(q,a)=s, \delta(q,b)=r$, and $\delta(s,a)=\delta(s,b)=q$.
> 2 votes

---
Tags: automata, buchi-automata
---


# Question
Title: Turing Machines: Arbitrary alphabet equivalence with binary alphabet
Think of an $n$-ary alphabet as $\\{0, 1, ..., n-1, n\\}$. For example, a binary alphabet is $\\{0, 1\\}$.

> Do **Turing Machines** with binary alphabets decide the same set of languages as Turing Machines with $3$+ symbol alphabets?

I am unsure of how to show equivalence. Clearly, any $3$+ symbol **TM** can simulate a **TM** with $2$ symbols, but I don't know how to show the other direction (if one exists).

# Answer
> 1 votes
I am answering the question "Can Turing Machines with binary alphabet decide the same languages as Turing Machines with 3 or more alphabet symbols?"

Now, on the one hand, it's not well-defined what happens if you take a string with three different alphabet symbols and give it to a TM that only is designed to see a binary alphabet on the tape. So in that sense, a three-symbol Turing Machine can decide languages with these strings, while the two-symbol machine isn't allowed to read them. (For instance, if the language has "a", "b", and "c" in it, then there is no TM with a binary alphabet that reads these strings.)

But you might ask this question instead. Let's consider only languages whose strings have two symbols, in order to give a fair comparison between the two-symbol TM and the three-symbol TM. Now, can the three-symbol TM decide more of these languages, simply because it can write more types of symbols on the tape while it is computing?

The answer here is "no". The idea is that we have to take any three-symbol Turing Machine and show that there is a two-symbol TM that essentially takes the same "steps" and accepts whenever the original one accepts, etc. Just as a hint, the idea here is to make a TM with a modified transition table so that it can "act like" it's writing the third symbol down, even though it's only using two symbols.

# Answer
> 0 votes
We need to emulate an n-symbol Turing machine with a binary TM (the other direction is trivial). So you need to convert the input string to binary (e.g. usual binary encoding) and convert the transition function to work with the binary alphabet. E.g. you have a transition (F,T,R,M,W) - F = from state, T = to state, R = read symbol, M - move left/right, W = write symbol. You need to convert this to a sequence of transitions: first read the binary representation - use n states for that. Then you can move the head - log2(n) operations, then write the output, again use n states, then transition to T'.

---
Tags: turing-machines
---


# Question
Title: Example of exponential algorithm performing better than a polynomial one?
I have a weird question.

I was just wondering if there were some problem with two solutions; one (A) being exponential time, the other one (B) being polynomial time. However the constants involved are such that, in "practice", the algorithm (A) performs better.

For instance, we could have something like $(1 + 10^{-100})^n$ versus $n^{10^{100}}$.

(I said exponential vs. polynomial, but any other distinction would do.)

# Answer
> 5 votes
I think the classic example of this is in Linear Programming.

The Simplex Algorithm is exponential time, but fast in practice. There is a polynomial time algorithm, but it's generally slower.

See the relevant Wikipedia entry.

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


# Question
Title: Using a binary heap to solve an equation
I have to find a solution for this equation:

I have to find the set of solutions a, b, c, d for all possible combinations of values 1 \<= x \<= n.

$a^5 + b^5 = c^5 + d ^ 5$

I first thought about using a heap, because it is what I am learning, but I can't seem to come up with a pattern.

I was told that my algorithm should run in $O(n^2\log(n))$ so I know I would have to use a heap of size n, with n\*2 inserts into its structure.

That's as far as I got, can someone hint me?

# Answer
You can generate all possible triples $(x^5 + y^5, x, y): x, y \in \\{1, \dots, n\\}$. There are $n^2$ of them. Next you can sort them by first component using heap sort or any other sorting algorithm(it will take $\mathcal{O}(n^2\cdot\log\_2(n))$). Now we have $k$ subsequences in sorted sequence where all triples have equal first component. Let's denote $i$th subsequence as $S\_i$ and their first component as $c\_i$. Each $S\_i$ gives $\frac{|S\_i| \cdot (|S\_i|-1)}{2}$ solutions such that $a^5 + b^5 = c\_i = c^5 + d^5$. Number of solutions is $\mathcal{O}(|S\_1|^2) + \cdots + \mathcal{O}(|S\_k|^2) = \mathcal{O}(n^2)$ since $|S\_1| + \cdots + |S\_k| = n$.

You also can just build heap on the sequence of all triples. And consequentially extract triples with minimum first component from it. While triples have equal first component they are part of some subsequence $S\_i$.

To build heap of size $n^2$ we need $\mathcal{O}(n^2)$ and to extract $n^2$ times minimum from it we need $\mathcal{O}(n^2\cdot\log\_2(n))$.
> 2 votes

---
Tags: algorithms, combinatorics, heaps
---


# Question
Title: Approximate probabilities of passing a NIST statistical test
I am working with random number generation and testing, so I'm using NIST statistical tests to examine my random numbers. Now I want to compare my solution with other RNGs, but i can't find any probabilities of passing a NIST statistical test for them. So does anyone have that info? Info about both PRNGs and TRNGs would be appreciated.

# Answer
Have a look at TestU01. It's another testing suite that has NIST built in. It also has implementations of most of the well-known RNGs, so you can compare. The documentation may have some results listed in it.
> 1 votes

---
Tags: reference-request, random-number-generator
---


# Question
Title: When was the terminology *tracing collector* introduced to denote both mark-and-sweep and copy collectors
Automatic storage reclamation, aka garbage collection, comes in two main families, sometimes cooperating: the reference count collectors and the tracing collectors. I may develop specifics of each family if there is demand for it but my question is about tracing collectors.

Tracing collectors, in their simpler form can be divided into mark-and-sweep (possibly with compaction) and copy collectors (that compact naturally). Historically, they seem to have been considered distinct families in the first 10 or 20 years of the development of garbage collection technology.

I am wondering when they started to become known as *tracing collectors* forming a single family. When was the expression *tracing collectors* first used to denote both mark-and-sweep and copy collection, and possibly collectors mixing both technologies (as is often the case with generational collectors).

Ideally, a reference to a paper introducing the terminology would be the best form for an answer. Reference to a book is good too, if you can give the printing where it first appears, as books often evolve with successive printings. Specifying the page or giving a quote would be nice too.

## Added after accepting the answer.

I am accepting the answer given by Pseudonym, as it is a very clear answer, that seems to be as good as it will ever get (but who knows?). What I mean is that it seems unlikely that an earlier date will be found, sinve the Paul Wilson's 1992 survey is pretty thorough. As I recall, the previous survey by Cohen in 1981 does not allude to *tracing* or unification of copy and mark-and-sweep.

An interesting trivia is that the introduction of this concept is exactly half-way between the first garbage collection paper in 1960 (as far as I know) and now (early 2015), which give a kind of time measure of conceptual evolution.

This first GC papers, to my knowledge, used reference counting and were published in 1960. According to wikipedia, which cites Jones, Richard; Lins, Rafael (1996), *Garbage collection: algorithms for automatic dynamic memory management*, Wiley, p. 40, ISBN 9780471941484:

> The first, though cumbersome and error-prone, reference counting technique was described by J. Gelertner, J.R. Hansen, and C.L. Gerberich \[Gelernter et al, 1960\] but the standard reference counting algorithm is due to George Collins \[Collins, 1960\].

To my knowledge, the first tracing GC is a mark-and-sweep implementation for LISP published in 1964 in, *Notes on implementing LISP for the M-460 Computer*, Timothy P. Hart and Thomas G. Evans, pp. 191-203 in The Programming Language LISP, its Operation and Applications, March 1964, published by Information International, and reprinted by MIT press (though they seemed to have lost all memory of it when I asked, a long time ago). It does use the name "garbage collector", but I do not know whether that is the first occurrence in the computer literature.

# Answer
The terminology was introduced in Lang and Dupont, *Incremental Incrementally Compacting Garbage Collection*, SIGPLAN 87. This is the paper which consolidated several lines of enquiry into one common language.

The way I found this out was by consulting Paul Wilson's 1992 survey, *Uniprocessor Garbage Collection Techniques*, which is required reading if you need to know stuff like this.
> 5 votes

---
Tags: terminology, programming-languages, memory-management, garbage-collection
---


title: What is 'halting'?

text:
# Question
Title: What is 'halting'?
I've read a definition that says that "co-semi-decideable' means that a TM is halting on all inputs NOT in the language. I've heard the word come up a lot, and I've so far assumed that halting just means to stop and asess an input.

But just to be clear, would somebody be so kind as to give me an easy to understand of what halting is in turing machines?

# Answer
Look at the definition of a Turing Machine (e.g., the one here). The machine has *states*. Each state can be *final* or non-final. If the machine's state is non-final, in the next step the machine "does" something, namely, it can write something on the tape, move its head, and/or change its state to a different state. This is how the machine makes a progress.

However, if the state is *final*, the machine just stops and continues no more. This will be its final setting, the head will not move anymore and the tape remains the same forever. This event is non-reversible and is what we call *halting*.

Machines can halt on all inputs, on some inputs, or no input(s). An example for a non-halting machine (on any input) is one that has only one state $q\_0$ (which must be non-final), on which the head always moves to the right. Formally, this can be denoted as having the transition function $\delta(q\_0,a) \to (q\_0,R,a)$ for any symbol of the tape's alphabet $a\in \Gamma$.

A Final state can be either *accepting* or *rejecting*. It makes sense to have only two final states: $q\_{accept}$ and $q\_{reject}$. The first is equivalent to the output "yes" and the second to the output "no".

Machines that stop on *every* input are called deciders: their language is decidable. But it's better to look at it from the other side: some languages can be decided: there exists a machine that halts and accepts (e.g., ends in $q\_{accept}$) for every input which is a word in the language; and halts and rejects (ends in $q\_{reject}$) for every input which is not a word in the language. Some languages cannot be decided: any machine that accepts all the words in that language, has some inputs on which it doesn't halt. These are semi-decidable languages. The co-semi-decidable languages have machines that only halt (and reject) on all the words not in the language, but will not halt on some other inputs, which are words in the language.
> 13 votes

# Answer
It just means stopping. It's not actually a piece of jargon (in the sense of jargon being "special words or expressions used by a profession or group that are difficult for others to understand"), it has the normal English meaning.

Note that there's no connotation of assessing the input either, it's just stopping. Whether the Turing Machine accepts or rejects is a second, separate consideration (apart from the inaccuracy of thinking of this as "assessing the input" - the work that the Turing Machine does is the assessment part).
> 4 votes

---
Tags: terminology, computability, turing-machines
---


# Question
Title: How do you prove two languages are equivalent using the definition of acceptance?
I need to prove that $L(f(M)) = L(M)\cup \\{\varepsilon\\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \\{q\_f\\}, \Sigma, \delta', q\_f, F\cup\\{q\_f\\})$ and $q\_f$ is a new state not in $Q$ and

$\delta'(q,a) = \begin{cases} \delta (q,a) & \text{if }q\in Q\\ \delta (q\_0,a) & \text{if }q= q\_f. \end{cases}$

I'm assuming I need to use induction but I'm not sure how to go about it

# Answer
> 1 votes
I don't think you need to use induction, a simpler case analysis will suffice, along with a couple of central observations about the new DFA $f(M)$:

1. $q\_{f}$ is the new start state,
2. $q\_{f}$ is also an accepting state,
3. $\delta'$ is *almost* exactly the same as $\delta$ (in a very specific way of course), and
4. there's no transitions *into* $q\_{f}$.

From this you can argue what happens on input $x$ in two cases:

1. $x = \varepsilon$, and
2. $x$ is anything else.

---
Tags: formal-languages, regular-languages, finite-automata, proof-techniques, induction
---