# Question
Title: Is Q-Learning ever better than Brute Force?
I am currently learning about the Q-learning algorithm, so I therefore assume that it has some use or purpose. However I currently cannot see how it is in any way useful. In terms of complexity class, it appears to perform equal to or worse than brute force, which as far as I am aware, is the lowest you ever need to go to compute something computable.

What, if anything, have I missed?

# Answer
Reinforcement Learning (RL) algorithms are useful in a setting when the structure of the environment is unknown and/or stochastic. The environment is normally formalized as a Markov Decision Process (MDP) or Partially Observable Markov Decision Process (POMDP) and the goal of an RL agent is then to maximize its cumulative reward (or minimize its regret with respect to the best alternate policy) while behaving in the environment.

As such it isn't clear how a brute force algorithm would efficiently deal with the stochastic nature of the environment or the fact that this procedure is almost universally assumed to be done online. For more information and a modern overview of RL I recommend this excellent reference by Csaba Szepesvari.
> 6 votes

---
Tags: machine-learning, artificial-intelligence
---


title: Undecidability and Countability

text:
# Question
Title: Undecidability and Countability
This question is prompted by Undecidable unary languages (also known as Tally languages)

How does the countability of a language imply (un)decidability?

# Answer
> 6 votes
Countability doesn't imply (un)decidability: the set of even numbers and the set of codings of Turing machines that halt on input zero are both countable but the first is decidable and the second isn't.

Conversely, for any finite alphabet $\Sigma$, the set $\Sigma^\*$ of all finite strings over $\Sigma$ is countable, since each string can be seen as a natural number written in base $|\Sigma|$. Therefore, any language (i.e., any subset of $\Sigma^\*$) is also countable.

The only place that uncountability comes in is that there are uncountably many different languages over any finite $\Sigma$. This gives an immediate proof of the existence of undecidable languages: there are uncountably many languages but only countably many Turing machines.

---
Tags: undecidability, uncountability
---


# Question
Title: Finding largest subset that matches moments
I would like to find a algorithm that will do the following:

> Given two sets $A, B \subseteq \mathbb{R}$, where $|B| \> |A|$, find the largest subset $C \subseteq B$, such that:
>
> $\qquad |\operatorname{mean}(A) - \operatorname{mean}(C) |\< \delta$ and
>
> $\qquad |\operatorname{std}(A) - \operatorname{std}(C) | \< \epsilon$

I think this problem is NP-hard, but I would like a good approximation that does reasonably well. An even harder version of this is to find the larget subset $C$ that matches not just the moments, but the histogram of $A$ to some quality metric. If you have a solution, or can point to same papers that would great!

I am a neuroscientist, and this is for my research.

# Answer
> 1 votes
I tried formulating this as an integer linear program, but ran into problems, because the variance is not a linear function: it is quadratic.

---

Here was my attempt.

Introduce variables $x\_b$ (one for each $b \in B$), such that $x\_b=1$ if $b \in C$ and $x\_b=0$ if $b \notin C$. Thus, we have $|B|$ new zero-or-one variables. We can force them to be zero or one by adding the constraints $0 \le x\_b \le 1$ for each $b \in B$.

Next, we'll force the mean of $C$ to be in the accepted range. Introduce a new unknown $\mu$ and add the constraint

$$\mu = (\sum\_{b \in B} x\_b b)/|B|.$$

This forces $\mu$ to be the mean of $C$. Also, it is expressible in a linear equation, since everything except for $\mu$ and the $x$'s are constants. Finally, add the two linear inequalities

$$\text{mean}(A)-\delta \le \mu \le \text{mean}(A)+\delta.$$

But it's not clear how to force the standard deviation of $C$ to be in the accepted range. Let $\sigma = \text{std}(C)$, i.e., $\sigma$ denotes the standard deviation of $C$. We could try to use the fact that

$$\sigma^2 = \frac{1}{N} \sum\_{c \in C} c^2 - \frac{1}{N^2} \left( \sum\_{c \in C} c \right)^2,$$

but now when we substitute in with our definitions of $x\_b$, we get something ugly:

$$\sigma^2 = \frac{1}{N} \sum\_{b \in B} b^2 x\_b - \frac{1}{N^2} \left( \sum\_{b \in B} b x\_b \right)^2,$$

where the right-hand term has something quadratic. Worse still, $N$ also depends upon the $x$'s, which takes this even further away from something linear:

$$S = \sum\_{b \in B} x\_b.$$

Alternatively, we could try to use the fact that

$$\sigma^2 = \frac{1}{N} \sum\_{c \in C} (c - \mu)^2,$$

but when we substitute in, again we get something that's not linear:

$$\sigma^2 = \frac{1}{N} \sum\_{b \in B} x\_b (b - \mu)^2,$$

where the non-linearity comes from the fact that $N$ is itself a function of the $b$'s, as well as the fact that the right-hand side involves a product of two linear variables ($x\_b$ and $\mu$).

We want

$$\text{std}(A) - \epsilon \le \sigma^2 \le \text{std}(A) + \epsilon.$$

Plugging in, we find that we need

$$(\text{std}(A) - \epsilon)N \le \sum\_{b \in B} x\_b (b - \mu)^2 \le (\text{std}(A) + \epsilon)N.$$

This is not linear, because $x\_b (b - \mu)^2$ is not a linear function of $x\_b,\mu$.

We could deal with the fact that $N$ is not a constant by enumerating all candidate values of $N$ and solving an ILP for each. However, that still doesn't deal with the problem that $x\_b (b - \mu)^2$ is non-linear.

So, I'm stuck. I wasn't able to formulate this cleanly as an ILP.

---
Tags: algorithms, reference-request, optimization
---


# Question
Title: Why can't we flip the answer of a NDTM efficiently?
I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) states that it is unclear how another NDTM $T$ can determine in $O(n^{100})$ time how to flip $M$’s answer.

My Problem is as follows: A NDTM outputs $1$ iff there exists a sequence of non-deterministic choices that leads to the accepting state. Furthermore, there exists a universal NDTM $NU$ that can simulate every NDTM with only a small (logarithmic) overhead. So why can’t we construct T as follows: First, simulate M with the universal NDTM which should be possible in time $O(n\log n)$. Then output 1 – M’s answer. This would mean that we can flip the answer of any linear NDTM in time $O(n\log n)$.

# Answer
> 16 votes
A nondeterministic Turing machine accepts if at least one path accepts; it only rejects if all paths reject. This asymmetry makes it hard to "flip answers".

For example, suppose you have a nondeterministic Turing machine $M$ that has two paths for input $w$: one accepts, the other rejects. $M$ has at least one accepting path for $w$, so it accepts. Suppose we want to produce a machine that accepts exactly the inputs that $M$ rejects. The obvious first attempt is to take $M$ and make its accepting states reject, and its rejecting states accept. $M$ has one accepting path for $w$ and one rejecting path; this new machine $M'$ has one rejecting path and one accepting path. So it still accepts $w$, which it was supposed to reject!

A nondeterministic machine can't look at all its paths simultaneously and take action based on what all of those paths do. If you like, you can think of it as a form of parallelism where the threads are forbidden to communicate with each other. When all of the threads have finished the program must ask itself the following question: "Did at least one of my threads accept?" If the answer is yes, it is legally obliged to accept; if the answer is no, it is legally obliged to reject. *It cannot do anything else.*

When you simulate a nondeterministic machine $M$ using another one, $M'$, each path of $M'$ simulates one path of $M$ and sees only that path. It can't say, "If all those other paths rejected, I'll accept" because it can't see the other paths; it can only see itself. So all it could possibly say is things like, "If the path I simulated accepted, I'll reject" or "If the path I simulated accepted, I'll accept too". Then, at the end of the computation, the machine has to say, "If any of my paths accepted, I'll accept too", leading to the problem I described above. To invert the behaviour of $M$, each path of $M'$ needs to say, "If the path I simulated accepted, I reject; else, I accept" and, at the end of the computation, the machine needs to say, "If all of my paths accepted, I accept; else, I reject." This is because, if all of the simulator's paths accepted, that means all of $M$'s paths rejected, so $M$ rejected, so the simulator needs to accept. But the simulator isn't a valid nondeterministic Turing machine because it isn't using the legally mandated acceptance criterion. It can't do that.

The only way we know to figure out if a nondeterministic machine rejects its input is to try every possible path and verify that they all reject. After all, if even one of them accepted, the machine would accept the input. But trying every possible path is exponentially slower than trying just one.

# Answer
> 2 votes
The problem is that NDTM are inherently non-symmetric: the time $O(n)$ means that they have $O(n)$ steps to guess an accepting path if exists, and will reject otherwise (if no accepting path exists).

The problem is that if your machine $NU$ is really in $O(n log( n))$, it means that it guesses in $n log (n)$ steps a witness that $M$ rejects the input. This might not be possible to do, because there are no witnesses of rejection of $M$, just witnesses of acceptance. Rejection is the absence of witness, so it is not easy to prove rejection in a short time.

# Answer
> -3 votes
actually technically you are asking the P$\stackrel{?}{=}$coNP($\stackrel{?}{=}$NP) question which is open. it is widely conjectured but not proven that they are not equal. the other answers are intuitive sketches/circumstantial evidence why they are not equal.

---
Tags: complexity-theory, turing-machines
---


# Question
Title: Why does making a seemingly insignificant edit to an executable's machine code return errors?
First of all, I would like to apologize if this question is in the wrong section. For all I know, it could be placed in Super User, Reverse Engineering, or Stack Overflow.

Now lets get back the experiment I tried:

What I did was took an executable file and changed its file type to a text document type. Then I opened this file in a text editor and changed a single character. This character was just part of some descriptive copyright information. After this I changed the file type back to an executable file type and tried running it. Why does the Windows operating system return the error, "The version of this file is not compatible with the version of Windows you're running...", when attempting to run the executable?

What is happening underneath the hood when an executable runs?

# Answer
> 5 votes
When you open an executable in a text editor then the editor reads the contents in some lossy way - even if you haven't changed anything then the file would be different. Binary files contain non-printable characters (those with ASCII codes from 0 to 31), and these could be deleted by the text editor (other than CR/LF), especially the 0 character. Also, Windows text editors would convert CR (the UNIX new line convention; 0D) to CR/LF (the Windows convention; 0D 0A).

If you're curious what went wrong in your case, try to compare the files byte by byte and see where the differ. You could use a "hex editor", which is what you should have used to modify your file in the first place. These editors don't mishandle your files.

---
Tags: operating-systems
---


# Question
Title: Context-free language and regular expressions
I have the following context-free language:

```
S -> ASa | b
A -> aA | a

```

I don't understand why this is not regular. I first said that it's generated by the regular expression `a+ba+`. The following is regular however

```
S -> ASa | b
A -> aA | e

```

e stands for the empty string. I don't understand their differences.

# Answer
> 7 votes
The subtlety is that in the first case, the number of $a$'s before the unique $b$ must be at least the number of $a$ after, i.e. your language is $\\{a^nba^m|n\geq m\\}$, so it is not regular. This is because each $A$ produces at least one $a$.

In the second case however, this constraint disappears, and your language becomes indeed $b+a^\*ba^+$ which is regular.

# Answer
> -3 votes
See, in the CFG grammar you need to store the value of n and m in order to compare the condition i.e. n\>= m.So memory is required,preferably a stack.Whereas, in the regular grammar its either b or any string ending with ba. You don't need anything to remember to satisfy the grammar,as there is no such condition where you need to store the value.

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


# Question
Title: lexicographic depth-first search complexity class
It seems to me to be incorrect to say that lexicographic DFS is P-complete, since it isn't a decision problem. There is a corresponding decision problem, first DFS ordering, which is known to be P-complete. However, I want to talk about complexity of DFS, not it's decision problem. What complexity class should I say DFS belongs to?

# Answer
The formal name for a problem where you want to actually produce the solution as the output (not just say yes or no to whether one exists) is a Function Problem if every input has an associated output, or a Search Problem if some inputs might not have any solution (of course a function problem is just a special case of a search problem).

In this case, every graph has a lexicographic depth first ordering, so for any graph there is some output that can be produced, and you have a function problem. The class of function problems that can be computed in deterministic polynomial time is (cunningly) called FP.

Going out on a limb (with regards to my knowledge, someone else might be able to confirm this), I suspect that the obvious relationship1 between P and FP holds for complete problems too, so your problem should also be FP-complete.

1. Note that this relationship normally relies on Turing reductions, but seeing as P=co-P there shouldn't be too much of a problem here.
> 3 votes

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


title: Issue with Multithreading spin locks

text:
# Question
Title: Issue with Multithreading spin locks
a spin lock solution to the critical path problem is shown below . my question is will this or will this not result in starvation ?

```
    Thread A                Thread B
leave note A;           leave note B;
while (note B) {\\X     if (noNote A) {\\Y
    do nothing;             if (noMilk) {
}                               buy milk;

if (noMilk) {                  }
    buy milk;           }
}                       remove note B;
remove note A;

```

let me illustrate my point ,if thread A and B are scheduled as shown wont that result in starvation ?

note : those arrows are meant to indicate a cycle .

note: I'm following the online operating system course from Berkeley (http://www.youtube.com/playlist?list=PL-XXv-cvA\_iCrnl0625nXp4GimjT-cv\_1) .

In lecture 4 ,they talk about this as a correct solution to the critical path problem

# Answer
> 1 votes
Process B isn't looping; it runs and then quits. In other words, there won't be a second "leave note B" in your picture. There is a loop in process A (a *busy wait*, as it's called) and when process B removes its note, then execution will return to A's loop: A will check and see that there is milk so will remove its note and quit.

---
Tags: operating-systems, synchronization
---


# Question
Title: Is the language of Roman numerals ambiguous?
An ambiguous Language is a formal language for which there exists a string that can have more than one meaning (several possible meanings or interpretations). Multiple synthesis structures for a string.

**\[Question\]**
Are Roman numbers an example of an ambiguous language?

Because there can be more then one representation for some number such as 1999, which can be written as `MDCCCCLXXXXVIIII`, `MCMXCIX`, or `MIM`.

I am confused. Sometimes I feel not, some time yes!

**EDIT**
\[ANSWER\]

Although there can be more than one representation of same magnitude in Roman Number System. That is basically Non-Positional Number System. But its possible to write **Unambiguous Grammar for that can generate all possible/valid pattern in Roman Number System**.

**Here is again a beautiful link** that describe `symbol table`, `rule` , `Grammar` for Roman number.

I am not sure about this but some authors says that: "*Roman numbers can be recognized by a regular expression, so you don't really need a context-free grammar.*" and a regular language can't be ambiguous.

# Answer
A grammar (not a language!) is ambiguous if there is a word with two "essentially different" parses. Roman numerals are unambiguous - given a roman numeral, it has an unambiguous numerical value. The fact that this correspondence is not one-to-one is beside the point.
> 19 votes

# Answer
You fell into the trap of thinking that formal language theory deals with meaning. It doesn't.

In formal language theory, a context-free language is ambiguous if some context-free grammar generates exactly that language, but no such grammar does so in such a way that each string in the language only has a single parse tree.

The language of Roman numerals isn't completely standard, but I believe all versions have the property of being *finite*: I don't think 5000 can be represented, let alone a million. Every finite language is unambiguous: it can be generated by a grammar that directly produces each member string from the start symbol.

(UPDATE: Peter Shor's comments make it clear that this wasn't the case: apparently it was quite common to surround numbers with `C Ͻ` or `| |` to multiply them by 1000. When this can be applied arbitrarily often, the language is no longer finite; when it can be done in arbitrary ways, it still doesn't become ambiguous when only `C Ͻ` is used; when `| |` is used, the interpretation may become ambiguous, but I still don't think the language becomes ambiguous in the formal, syntactic sense.)
> 6 votes

# Answer
Its not ambiguous.

Note that if you are writing a smaller digit before a larger one, obviously that means you are subtracting. But notice that those digits must be comparable. `I` would come before `V` and `X` only. `X` would come before `L` and `C` only. `C` before `D` and `M`.

Break the number and then combine their roman correspondents.

`49` is `40+9`. We dont write it as `IL`. We first convert `40`, then `9` so its `XLIX`.

`99` is not `IC`. Its `90 (XC)` \+ `9 (IX)` ie `XCIX`.

`499` is not `ID`. Its `400 (CD)` \+ `90 (XC)` \+ `9 (IX)` ie `CDXCIX`.

`999` is not `IM`. Its `900 (CM)` \+ `90 (XC)` \+ `9 (IX)` ie `CMXCIX`.

So, according to this

`1999` should be `MCMXCIX`. `1000 (M)` \+ `900 (CM)` \+ `90 (XC)` \+ `9 (IX)`.

And also `MDCCCCLXXXXVIIII` is an invalid representation. You can't have 4 consecutive same letters. Instead you convert it.

M\*DCCCC\*LXXXXVIIII $\rightarrow$ M\*CM\*LXXXXVIIII

MCM\*LXXXX\*VIIII $\rightarrow$ MCM\*X\*VIIII

MCMXC\*VIIII\* $\rightarrow$ MCMXC\*IX\*

This online conversion tool might be helpful.
> 4 votes

# Answer
You are confusing several concepts of ambiguity, and using your own definition backward.

There is the concept of **semantic ambiguity**: is it possible to have different meanings for the same string. In your case: is it possible that 2 different numbers are written in the same way in Roman numerals. The answer is clearly no, because there is a simple deterministic algorithm to compute the value represented by a Roman numeral.

However, when you talk of formal language, you are considering only syntactic structures (usually tree structure) associated to string in accordance with the way these strings can be generated by a grammar. Identifying a tree associated with a string is called parsing.

Then there is the concept of **syntactic ambiguity**. Are there two different ways to parse some numerals into a structure. I cannot answer that since you do not give a formal definition of the structure of roman numerals.

But let us assume that you are only considering structure defined by a context-free (CF) grammar. Then you may wonder whether the Roman numerals can be generated by an **unambiguous CF grammar** (they can, though I did not check the grammar on the site you discovered). But there are CF languages that will not have an unambigous grammar. Such CF languages are said to be **inherently ambiguous**.

**Does syntactic ambiguity really matter?** Not necessarily if you are only interested in the meaning of sentences, here in the integer values represented by Roman numerals. Syntactic structure is normaly used to define semantic, that is, meaning. If the same sentence has two structure because of grammatical ambiguity, that could be a problem. But it could also be that the way meaning is associated with the structure of a sentence (the parse tree) is such that it produces the same meaning for all strucures corresponding to a same sentence. **Syntactic ambiguity does not necessarily result in semantic ambiguity.**

The Romans numerals can be defined as a formal language, for example with a CF grammar. But you are also associating a meaning with each string, which means that you are considering more than a formal language. Hence you should be clear whether you talk of syntactic ambiguity, or of semantic ambiguity.

Now, you may have two distinct Roman numerals that represent the same number, as you show in your question, and which is confirmed by wikipedia. For example VIIII and IX. That is not ambiguity. It is a very common situation when a given meaning can be expressed syntactically by different strings. While you stated correctly that (semantic) ambiguity is when a string can have more than one meaning.

To take it with natural language, the sentence "John sees a man with a telescope" is ambiguous because you cannot determine whether John is using a telescope, or whether the man is carrying one.

But the fact that both sentences "the dog eats the bone" and "the bone is eaten by the dog" mean the same thing is not a problem for anyone.

From what I read in wikipedia, there is a finite number of Roman numerals. Hence they can be trivially represented by a regular grammar. And a regular grammar is an unambiguous CF grammar. But that is a trivial argument that provides no insight.

What you want is a CF grammar that will identify as a tree the organization of a Roman numeral so that it will be easier to compute its meaning: the associated integer. This is possible in various ways.
> 3 votes

# Answer
The translation from Arabic numbers to Roman numbers is very straight forward and absolute not 'unambiguous'.

You can translate each Arabic digit to exact one Roman representation.

```
Arabic:    1    2    3    4    5    6    7    8    9
Roman:     I   II  III   IV    V   VI  VII VIII   IX

Arabic:   10   20   30   40   50   60   70   80   90
Roman:     X   XX  XXX   XL    L   LX  LXX LXXX   XC

Arabic:  100  200  300  400  500  600  700  800  900
Roman:     C   CC  CCC   CD    D   DC  DCC DCCC   CM

Arabic: 1000 2000 3000
Roman:     M   MM  MMM

```

Combine a number from the highest to the lowest digit.

E.g.
1999 is (with space) `M CM XC IX` and together `MCMXCIX`.
> 1 votes

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


title: Code to get java code complexity

text:
# Question
Title: Code to get java code complexity
I have Java function as input and want to get it's order for example O( n ) I search in the internet very hard but didn't find any thing can help me, is there any algorithms or package may help me.

# Answer
> 5 votes
No. There's no algorithm to analyze the asymptotic complexity of a piece of code given as input. Being able to do that would tell you whether the code halted and that's undecidable.

---
Tags: algorithms, java
---


# Question
Title: How to find two functions that are not big-oh of each other?
I am asked to find two functions that are not big-oh of each other. Is it correct if I pick say $f(n)=2\sin (n)$ and $g(n)=1$? That way, $f$ will never always be greater than $g$.

# Answer
$\sin n \in O(1)$. Note the arbitrary constant in the definition of $O$.
> 2 votes

# Answer
Some people are picky about negative-valued functions. Here's one that will satisfy even picky people: $$ f(n) = n,\qquad g(n)=\begin{cases} n^2 &\text{if $n$ is even}\\ 1 & \text{if $n$ is odd} \end{cases} $$ There clearly isn't a constant $k$ for which $f(n)\le k\cdot g(n)$ eventually so $f$ isn't big-O of $g$ and in the same way we can see that $g$ isn't big-O of $f$.
> 1 votes

# Answer
The sine function oscillates between 1 and -1 up to a constant factor. So it would be correct to say that the function is $O(1)$ if the function is used to describe the runtime complexity of an algorithm, i.e. a complexity which oscillates as input size goes from $1,2,3$ to ... You could use $AbsoluteValue(sin(x))$ for the negative... Or $Sin(x)+1$...
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Why is this function computable in $O(n^{1.5})$ time?
My textbook says: "We define the function $f\colon \mathbb{N}\to\mathbb{N}$ as follows: $f(1)=2$ and $f(i+1)=2^{f(i)^{1.2}}$. Note that given $n$, we can easily find in $O(n^{1.5})$ time the number $i$ such that $n$ is sandwiched between $f(i)$ and $f(i+1)$."

How can I convince myself that we can in fact easily find $i$ in $O(n^{1.5})$ time? As $f$ is defined recursively, I think we have to compute $f(1),f(2),f(3)\dots f(j)$ until $f(j)\geq n$. In order to find out the time that these computations take, I think we have to find a suitable upper bound for $i$ dependent on $n$ and we have to find an upper bound on the execution time of the function $x\to2^{x^{1.2}}$. In the end, we can hopefully show the quoted proposition. Unfortunately, I don't see neither one thing nor the other.

I forgot to mention: Please note that we are in a nondeterministic context. So $f$ is claimed to be computable in $O(n^{1.5})$ by a nondeterministic Turing machine.

---

As quite a few people have already read this question, with some of them finding it useful and interesting too, but nobody answered so far, I want to provide some more information on the context: The quoted claim is an integral part of the proof of the nondeterministic time hierarchy theorem. The proof (with the claim) can be found e. g. in the book by Arora and Barak, but I have found quite a few other resources on the Web too which present the same proof. Each of those calls the claim easy or trivial and does not elaborate on how to find $i$ in $O(n^{1.5})$ time. So either all these resources just copied from Arora and Barak or the claim is in fact not so difficult.

# Answer
> 5 votes
Denote by $|x|$ the length of a number $x$, i.e. $\lfloor \log\_2 x \rfloor + 1$ (for $x \> 0$). Calculating $2^x$ requires time $O(x)$ in the RAM model, and so calculating $f(i+1)$ from $f(i)$ takes time $O(f(i)^{1.2}) = O(|f(i+1)|)$. Since $f(i)$ is growing faster than geometrically, the overall time to calculate $f(i+1)$ is $O(|f(i+1)|)$. As you point out, you need to do so until $f(i+1) \geq n$, which means that $f(i) \< n$. Therefore the total running time is $O(|f(i+1)|) = O(f(i)^{1.2}) = O(n^{1.2})$.

In the Turing machine model with a single tape, calculating $2^x$ takes time $O(x\log x)$, and so the total running time is $O(n^{1.2} \log n) = O(n^{1.5})$. The algorithm for computing $2^x$ replaces $\[x\]$ by $1\[\[x\]\]$ (here $\[x\]$ is the binary representation of $x$, and $\[\[x\]\]$ is the binary representation using different digits $0',1'$), and then repeatedly runs the transformation $\[\[x\]\] \longrightarrow 0\[\[x-1\]\]$, which takes time $O(|x|) = O(\log x)$.

---
Tags: complexity-theory, algorithm-analysis, nondeterminism
---


# Question
Title: Applying dynamic programming to a simple two-person game of perfect information
A natural number n represents the initial position in the game. When it is a players turn he/she is allowed to

```
I)  Subtract 2 from n
II) Subtract 3 from n
III)    Subtract 5 from n

```

We call the player who begin the game Adam and the other player Berta. The players alternate by applying on of the three rules to the number 0 or a negative number his/her opponent. If a player manages to produce the number 0 or a negative number he/she wins the game.

Here is an example of a game played by Adam and Berta (for n=15)

```
15 is given to Adam. He decides to subtract 5 leaving 15-5 = 10 to Berta
10 is given to Berta. She decides to subtract 3 leaving 11-3=8 to Beta
8 is given to Adam. He decides to subtract 2 leaving 8-2=6 to Berta
6 is given to Berta. She decides to subtract 2 leaving 6-2=4 to Adam
4 is given to Adam. He decides to subtract 5 producing -1 a negative number, Adam wins!

```

b) we define a one dimensional array X(1), X(2),X(3),..,X(n)

```
i)  X(j) =1 if Adam has a method to win when given the number j
ii) X(j)=0 if Adam has no method that guarantees that he wins when the given the number k

```

Calculate X(1),X(2),X(3)….,X(23),X(25)

What is X(8), X(13) and X(24)? Answer should be of the form boolean boolean boolean so if X(8)=0 , X(13)=1 and X(24)=1 the correct answer is 011 Thus the correct answer is one of the following 000 001 010 011 100 101 110 111

My attempt is

```
n=8
Adam: 8-5=3
Berta: 3-3 =0
Berta wins  0

n=13
Adam=13-5=8
Berta: 8-3=5
Adam 5- 5
Adam wins 1

I get really stuck with 24, so far I have 01

```

Is there a method for this type of problem, i have been stuck on it for ages now. Thanks in advance

# Answer
Since you want to calculate $X(1), X(2), X(3)$,... and not just some $X(i)$, you can start from $X(1)$. Let's denote the case where there is a winning strategy for first player by $1$ and the other case by $0$.

Clearly, value of $X(i)$ for $i \in \\{1,2,3,4,5\\}$ is $1$. Let's store the values of $X(i)$ that we computed in an array. For $i\>5$, if at least one of the values of $X(i-2), X(i-3), X(i-5)$ is $0$, then the value of $X(i)$ will be $1$. If none of them is $0$, then the value of $X(i)$ will be $0$.
> 2 votes

# Answer
Hint: A position with $n \leq 5$ is a win for the first player (the player to go); let's call such a position P1. If any move from a given position leads to a P1 position, then the position is a win for the second player (the player not to go); let's call such a position P2. If there is a move from a given position to a P2 position, then it's a P1 position. Use dynamic programming to determine who wins for given $n$.

More generally, you can compute the Sprague-Grundy function. That will tell you who wins in the simultaneous game when there are several positions $n\_1,\ldots,n\_k$, and each turn each player selects a position and makes a move there; a player who can't make a move (all $n\_i$ are negative or zero) loses.
> 0 votes

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


title: 2 cases for P = NP

text:
# Question
Title: 2 cases for P = NP
As we all know the million dollar question in Computer Science P=NP or not. I was trying to understand it and got some doubts please tell me whether I'm right or wrong

N=NP in two cases

> Case 1: We have found an algorithm which can solve a NP-Complete problem in P-Time. This implies that P=NP=NP-Complete. But still we can not say anything about the NP-HARD Problems.
>
> Case 2: We have found an algorithm which can solve a NP-Hard problem in P-Time. This implies that P=NP=NP-Complete=NP-Hard.

Am I right or I'm missing some point.

# Answer
> 6 votes
Case 1 is almost correct: if you could solve a single **NP**-complete problem in polynomial time, then every other **NP** problem can be solved by first reducing to the solved problem and then using the polytime algorithm for that. However, even if **P** **NP**, the trivial languages $\emptyset$ and $\Sigma^\*$ are not **NP**-complete under many-one reductions, so **NP** $\neq$ **NP**-complete.

Case 2 is incorrect. **NP**-hard is not a complexity class, as such, and **NP**-hard problems can have arbitrarily high complexity. To take an extreme case, the halting problem in **NP**-hard but you wouldn't be able to solve that by proving **P** = **NP**. Also, any **EXP**-complete problem is **NP**-hard, since **NP** $\subseteq$ **EXP**, so any problem in **NP** is reducible to any **EXP**-complete problem. However, by the time hierarchy theorem, **P** $\neq$ **EXP** so there cannot, in fact, be any polytime solution to this **NP**-hard problem, even if **P** = **NP**.

# Answer
> 2 votes
No, your case 2 is wrong.

NP-hard is *definitely* not equal to P. NP-hard includes problems that are not even decidable/computable.

The following diagram might help: it shows that there is no upper bound on how hard NP-hard problems can be.

If we solve some problem in polynomial time, then all problems below that in the diagram will be solvable in polynomial time but there are still NP-hard problems above it which are not.

---
Tags: complexity-theory
---


# Question
Title: How to build/recognise a deadlock-free order of resources
I have been faced with a problem where three concurrent processes **X**, **Y** ,**Z** execute three different code segments that access and update certain shared variables. Before entering the respective code segments :

* Process X executes the P operation on semaphores a,b and c;
* Process Y executes the P operation on semaphores b,c and d;
* Process Z executes the P operation on semaphores c,d and a.

After completing the execution of its code segment, each process invokes the V operation (i.e, signal) on its three semaphores. All semaphores are binary semaphores initialized to one.

How do I recognise a deadlock-free order of invoking the P operations by the processes ? For illustration, the given examples are the following

1. X: P(a)P(b)P(c) Y:P(b)P(c)P(d) Z:P(c)P(d)P(a)
2. X: P(b)P(a)P(c) Y:P(b)P(c)P(d) Z:P(a)P(c)P(d)
3. X: P(b)P(a)P(c) Y:P(c)P(b)P(d) Z:P(a)P(c)P(d)
4. X: P(a)P(b)P(c) Y:P(c)P(b)P(d) Z:P(c)P(d)P(a)

# Answer
Preventing deadlocks can be achieve by removing one of the Coffman condition, one being the circular wait condition.

For this we need to build a partial ordering of the resources.

From Wikipedia a partial ordered (poset) set is :

> A (non-strict) partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., which satisfies for all a, b, and c in P:
>
> * a ≤ a (reflexivity);
> * if a ≤ b and b ≤ a then a = b (antisymmetry);
> * if a ≤ b and b ≤ c then a ≤ c (transitivity).

For the processes, there is no interest in the first two clauses, resources are distinct and unique. All we care about is the transitivity. Assuming a given order of resources, we then must ensure that each process never claims a lower resource before a higher one.

Building a deadlock free order is as simple as ordering the resources. This choice is arbitrary.

To solve your examples, we need to find what order has been chosen, if one exists, and verify it is a poset.

1. is not a poset since $a \> c$ (from X) and $c \> a$ (from Z) contradicts the transitivity.
2. is a poset since $b \> a \> c \> d$ in all groups.
3. is not a poset since $b \> c$ (from X) and $c \> b$ (from Y) contradicts the transitivity.
4. is not a poset since $a \> c$ (from X) and $c \> a$ (from Y) contradicts the transitivity.

Conclusion, only 2 is a deadlock free order as the circular wait condition is removed.
> 4 votes

---
Tags: process-scheduling, deadlocks
---


# Question
Title: Correct nomenclature: Hamilton path, Hamilton's path or Hamiltonian path?
What is the correct way? Hamilton path, Hamilton's path or Hamiltonian path? To be clear, I am referring to the correct way to name a graph such that there exists a single path (without repeated vertices) through all the vertices.

In Wikipedia it says "Hamiltonian path", whereas in an article I found "Hamilton path".

# Answer
I have seen both Hamilton path (or Hamilton cycle) and Hamiltonian path (or Hamiltonian cycle). A graph, however, is always Hamiltonian (if it contains a Hamilton/Hamiltonian cycle). Consider for example the titles of two papers: *Hamiltonian cycles in random regular graphs* (Fenner & Frieze) and *Generating and counting Hamilton cycles in random regular graphs* (Frieze, Jerrum, Molloy, Robinson & Wormald). Alan Frieze apparently doesn't care too strongly about the issue.

However, I've never seen Hamilton's path or cycle.
> 2 votes

---
Tags: hamiltonian-path
---


# Question
Title: Find all non-decreasing sequences given lenght and size
I'm trying to find a solution for this exercise:

> Give the pseudocode of an algorithm which takes two positive integers n and k and prints all the non-decreasing sequences of length k (1,2,...,n).
>
> For example n=4, k=3:
>
> 111 112 113 114 122 123 124 133 134 144 222 223 224 233 234 244 333 334 344 444
>
> the complexity must be O(n S(n,k)) with S(n,k) the number of the sequences to print for n and k.

i think from the complexity required that a backtracking algorithm it's needed but i could'nt solve it.

i tried something like this:

```
P(n,k,h: prefix length, S: sequence)

      if h == k then
           OUTPUT S
      else
         for i=1 to n do
             if(i>=S[h])
                   S[h+1]=i;
                   P(n,k,h+1,S);

```

# Answer
**Hint.** Given the available time complexity, a simple recursive algorithm should work. If you need a sequence of length $k$ from the set $\\{m, \dots, n\\}$ you either include $m$ or you don't.
> 1 votes

---
Tags: algorithms, backtracking
---


# Question
Title: How do I compute this non terminal positions evaluation, for tic-tac-toe?
Looking at this solution on page 3 but having trouble understanding the evaluation function specifically.

> For non terminal positions, we use a linear evaluation function defined as
>
> Eval (s) = 3\[X2(s)\]+X1(s)−(3\[O2(s)\]+O1(s))
>
> We define X n ( s ) as the number of rows, columns, and diagonals in state s with exactly n X’s and no O’s, and similarly define O n ( s )

Looking at this state 's' for example (these problems accounts for symmetry):

```
|X| | |
| |O| |
| | | |

```

It shows an evaluation of `-1`

However, got 0:

X2(s) = 0 because there are no rows or columns with 2 X's.
X1(s) = 2 because the top row and left column both have 1 X (but the diagonal has an O)

O2(s) = 0 because there are no rows or columns with 2 O's.
O1(s) = 2 because the middle row and middle column both have 1 O (but the diagonal has an X)

Plugging in:

```
0+2 - (0+2) = 0

```

So, I thought I am missing symmetry but I just get a bigger scale that still = 0's.

I must be overlooking something simple but not sure.

Any help is appreciated.

# Answer
> 3 votes
O1(s) = 3. You missed another diagonal.

---
Tags: heuristics, game-theory, board-games
---


# Question
Title: Big O relation between $2^n$ and $2^{2n}$
I know that:

If $f(n) = O(g(n))$ , then there are constants $M$ and $x\_0$ , such that

$f(n) \<= M\*g(n), \forall n \> n\_0$

The other, plain English way of defining it is,

If $f(n)=O(g(n))$ then for large $n$ , $f(n)$ would *grow* as fast as $g(n)$.

I got confused when comparing $2^n$ with $2^{2n}$. Here , $f(n) = 2^n$ and $g(n) = 2^{2n}$. Clearly , $f(n)$ is smaller than $g(n)$ by a factor of $2^n$. So there will be constants $A$ and $x\_0$ such that the first definition above is met.

However, for large $n$ , $2^{2n}$ would grow much faster than $2^n$, leaving $2^n$ far behind. That is $2^{2n}$ won't be an asymptotic/tight bound for $2^n$ .

So, is $2^n = O(2^{2n})$ or not? (or did I just create a confusing situation out of nothing)

# Answer
The more strong estimate is correct:

$2^n = o(2^{2n})$

Just look at definition of the little-o. For *any* constant $c \gt 0$ you need to find a constant $n\_0$, such that for all $n \ge n\_0$ you get $2^n \le c \cdot 2^{2n}$. Apparently, the following inequality will give you this $n\_0$:

$n\_0 \ge ln(1 / c)$
> 4 votes

# Answer
Remember that $O$ is an upper bound.

$2^n = O(2^{2n})$, but $4^n = 2^{2n} \ne O(2^n)$. I.e., $2^{2n}$ is not within a constant factor of $2^n$.
> 3 votes

# Answer
The statement:

> If $f(n)=O(g(n))$ then for large $n$ , $f(n)$ would grow as fast as $g(n)$.

is incorrect, and that's probably where your confusion is. Taking from Raphael's answer in How does one know which notation of time complexity analysis to use? :

> $f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$...

Note "at most as fast," not "as fast." If you want "as fast," you're probably looking for $\Theta$; taking from Raphael's answer again:

> $f \in \Theta(g)$ means that $f$ grows about as fast as $g$...

but as you've already probably guessed, $2^n \notin \Theta(2^{2n})$. For $2^n \in \Theta(2^{2n})$ to be true, $2^{2n}$ would itself have to be $\cal{O}$$(2^n)$, which I think you can see is clearly not the case.
> 3 votes

---
Tags: complexity-theory, algorithm-analysis, asymptotics, landau-notation
---


# Question
Title: Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG
I am somewhat confused with the running time analysis of a program here which has recursive calls which depend on a RNG. (Randomly Generated Number)

Let's begin with the pseudo-code, and then I will go into what I have thought about so far related to this one.

```
    Func1(A, i, j)
    /* A is an array of at least j integers */

 1  if (i ≥ j) then return (0);
 2  n ← j − i + 1 ; /* n = number of elements from i to j */
 3  k ← Random(n);
 4  s ← 0; //Takes time of Arbitrary C

 5  for r ← i to j do
 6      A[r] ← A[r] − A[i] − A[j]; //Arbitrary C
 7      s ← s + A[r]; //Arbitrary C
 8  end

 9  s ← s + Func1(A, i, i+k-1); //Recursive Call 1
10  s ← s + Func1(A, i+k, j); //Recursive Call 2
11  return (s);

```

Okay, now let's get into the math I have tried so far. I'll try not to be too pedantic here as it is just a rough, estimated analysis of expected run time.

First, let's consider the worst case. Note that the K = Random(n) must be at least 1, and at most n. Therefore, the worst case is the K = 1 is picked. This causes the total running time to be equal to T(n) = cn + T(1) + T(n-1). Which means that overall it takes somewhere around cn^2 time total (you can use Wolfram to solve recurrence relations if you are stuck or rusty on recurrence relations, although this one is a fairly simple one).

Now, here is where I get somewhat confused. For the expected running time, we have to base our assumption off of the probability of the random number K. Therefore, we have to sum all the possible running times for different values of k, plus their individual probability. By lemma/hopefully intuitive logic: the probability of any one Randomly Generated k, with k between 1 to n, is equal 1/n.

**Therefore, (in my opinion/analysis) the expected run time is:**

**ET(n) = cn + (1/n)\*Summation(from k=1 to n-1) of (ET(k-1) + ET(n-k))**

Let me explain a bit. The cn is simply for the loop which runs i to j. This is estimated by cn. The summation represents all of the possible values for k. The (1/n) multiplied by this summation is there because the probability of any one k is (1/n). **The terms inside the summation represent the running times of the recursive calls of Func1.** The first term on the left takes ET(k-1) because this recursive call is going to do a loop from i to k-1 (which is roughly ck), and then possibly call Func1 again. The second is a representation of the second recursive call, which would loop from i+k to j, which is also represented by n-k.

**Upon expansion of the summation, we see that the overall function ET(n) is of the order n^2.** *However*, as a test case, plugging in k=(n/2) gives a total running time for Func 1 of roughly nlog(n). *This* is why I am confused. How can this be, if the estimated running time is of the order n^2? Am I considering a "good" case by plugging in n/2 for k? Or am I thinking about k in the wrong sense in some way?

# Answer
How does the recursive formula for $E\[T(n)\]$ compare between this algorithm and randomized quicksort? They are very similar, which might lead one to believe that the running time of your algorithm is $\Theta(n \log n)$. In fact, the recursive formula for the run-time is so similar to the one for quicksort, that you could use that fact in itself as a proof. There are more elegant ways to prove it, but you can also prove it by induction.

$$ T(n) \leq bn + \frac{1}{n}\sum\_{k = 1}^n T(k) + T(n-k) $$

$$ = bn + \frac{2}{n}\sum\_{k = 1}^{n-1} T(k). $$

Suppose (induction hypothesis) that $T(i) \leq ci \ln i$ for $i \le n - 1$.

Then use the standard trick of bounding a sum by an integral: $\sum\_{i=1}^{n-1}f(i) \leq \int\_1^n f(x) dx$.

The rest of the proof works like a standard proof by induction with just a little algebra.

Here's a nice source for this and other proofs of the running time of quicksort, and the techniques apply to this problem as well.

Notes on randomized quicksort analysis
> 1 votes

---
Tags: algorithms, algorithm-analysis, randomized-algorithms, average-case
---


# Question
Title: what is a good source for learning how to design a programming language?
I am trying to find a good resource for learning on how to design and create a new programming language. It seems like a search for books in amazon raises some difficulties, because the vast majority of results are about programming languages, not on how to design them.

# Answer
This was a bit too long for a comment. And in a way it is an answer.

I fear that if you have to ask that question, you are not yet mature enough in the field to actually do the job. Furthermore, the kind of things you need to learn and do depends very much on what the language is for. If it is for general programming, you have to understand the various kinds of structural choices that have to be made. The best source is a general course on programming, not just programming in one specific language. To understand what is scope (it varies), what are variables (they come in different brands), what is environment and binding, to distinguish between functional, imperative or logical paradigms, and so on.

Designing a language is highly dependent on what you want to say (program) and how you want to do it. Look for "programming paradigms."

Learn several advanced programming languages (Haskell, CAML or others), not just what is commonly used by programmers. When you know enough languages, you will naturally know how you would want to design one, if you still do.

And of course, you have to learn all the implementation techniques for theses structures and features. But that you will largely find in books on compiler and interpreter writing. Maybe you can start with that.

You do not have to do that. But cemeteries are full of programming languages that no one ever looked at.

Creating a language is a long, long work, with slim chances of success. Make sure it is worth spending a significant part of your life doing it.
> 4 votes

# Answer
You would have to pull together resources from several places:

1. Books that deal with principles of programming languages: what are the building blocks of a language, what sorts of languages are there, how do we define a language, how do we define its operational semantics, etc. Here I would recommend Benjamin Pierce's "Types and programming languages" and Bob Harper's "Practical Foundations of Programming Languages" (also PDF draft is available).
2. Books that deal with actual low-level implementation: how to implement a parser, how to generate assembly code, garbage collection, code optimization, etc. A classic is the Dragon book.
3. Actual implementations of languages. You may be better off starting with simple things, such as my PL Zoo, and then look at actual implementations of real programming languages.
> 4 votes

---
Tags: programming-languages
---


# Question
Title: Is this a well founded inductive type? Can I express this in Coq?
the standard List type in Coq can be expressed as:

```
Inductive List (A:Set) : Set :=
  nil : List A
| cons : A -> List A -> List A.

```

as I understand, W-type express a well-founded tree of elements of this type. so, what if `nil` is not qualified by `A`? i.e. we have:

> for all `A: Set` `nil : List A`

instead of

> for all `A: Set` `nil A: List A`

is this a correct W-type? can I express this in Coq?

# Answer
You have misunderstood why `A` stands there in the definition of list.

Let us first look at how we might define lists of booleans:

```
Inductive ListBool : Set :=
  | nilBool : ListBool
  | consBool : bool -> ListBool -> ListBool.

```

And here is how we might define lists of natural numbers:

```
Inductive ListNat : Set :=
  | nilNat : ListNat
  | consNat : nat -> ListNat -> ListNat.

```

As you can see the `nilBool` and `nilNat` are constants that do *not* depend on any parameters. It is boring to define lists of booleans, lists of natural numbers, lists of lists of booleans, etc. Coq allows a *parametrized* definition of lists in which the `List` type itself takes a parameter `A` as input, to give lists of elements of type `A`. This is defined as you wrote:

```
Inductive List (A : Set) : Set :=
  | nil : List A
  | cons : A -> List A -> List A.

```

In the `nil` clause we have `List A`. Here `A` is the argument to `List`, it is not an argument to `nil`. If we wrote just `List` then Coq would ask "list of *what*"? For a similar reason the `cons` constructor has two occurences of `List A`.

Let me put it another way. The type of `ListNat` is `Set`. The type of `List` is `Set -> Set`. So we have to apply `List` to a set before we get a list.
> 3 votes

---
Tags: type-theory, dependent-types, coq, inductive-datatypes
---


# Question
Title: Determining the optimal threshold value for a one-dimensional decision stump classifier
I'm currently trying to find an efficient algorithm to solve a discrete optimization problem that arises when constructing decision trees. The problem is as follows:

Say we are given $N$ ordered data points on the real line: $x\_1,\ldots,x\_N \in \mathbb{R}$ such that $x\_1 \< x\_2 \< \ldots \< x\_N$.

Each of the points $x\_i$ has a label $y\_i \in \\{0,1\\}$. We are asked to predict this label using a *decision stump classifier*, $h(x;t) = \mathbb{1}\[x\>t\]$. The decision stump classifier predicts $\hat{y}\_i = 1$ if $x\_i \> t$. Thus, the accuracy of this classifier depends on the threshold parameter $t$.

I am looking for an efficient algorithm to determine the value of $t$ that maximizes the number of correctly classified points. That is, solve the problem:

$$\max\_{t\in\mathbb{R}} A(t)=\sum\_{i=1}^N \mathbb{1}\[y\_i=0\]\mathbb{1}\[x\_i\leq t\] + \mathbb{1}\[y\_i=1\]\mathbb{1}\[x\_i\>t\]$$ Some insights:

* Since there are $N$ data points, we only need to consider $N+1$ values of $t$. These are values that lie in the $N+1$ intervals $(-\infty,x\_1), \[x\_1,x\_2),\ldots, \[x\_{N-1},x\_N), \[x\_N,\infty\]$.
* When $t \< \min\_{i}x\_i$, the decision stump predicts $\hat{y}\_i=1$ for all $i=1,\ldots,N$. Here $A(t) = \sum\_{i=1}^N{\mathbb{1}\[y\_i=1\]}=N^+$.
* When $t \geq \max\_{i}x\_i$, the decision stump predicts $\hat{y}\_i=0$ for all $i=1,\ldots,N$. Here $A(t) = \sum\_{i=1}^N{\mathbb{1}\[y\_i=0\]}=N^-$.
* The number of correctly classified points $A(t)$ can be decomposed as $B(t)+C(t)$, where $$B(t) = \sum\_{i=1}^N{\mathbb{1}\[y\_i=0\]\mathbb{1}\[x\_i\leq t\]}$$ is the number of correctly classified points with negative labels and $$C(t) = \sum\_{i=1}^N{\mathbb{1}\[y\_i=1\]\mathbb{1}\[x\_i\>t\]}$$ and the number of correctly classified points with positive labels. Note that $B(t)$ is monotonically increasing in $t$ while $C(t)$ is monotonically decreasing in $t$.

# Answer
There is a straightforward algorithm that runs in $O(N)$ time, by scanning from left-to-right and right-to-left. Basically, it takes advantage of a simple recurrence relation for $B(\cdot)$ and $C(\cdot)$.

Let $t\_0,t\_1,\dots,t\_N$ denote a sequence of $N+1$ candidates for the threshold (i.e., $t\_i \in \[x\_i,x\_{i+1})$, etc.), as you articulated in the question. Our job is to find the value of $i$ that maximizes $B(t\_i)+C(t\_i)$.

I claim we can compute the $N+1$ values $B(t\_0),B(t\_1),\dots,B(t\_N)$ in $O(N)$ time, using a left-to-right scan. This is because, given $B(t\_{i-1})$, it is easy to compute $B(t\_i)$. In particular, notice that $B(t\_i)$ can be written as the summation

$$B(t\_i) = \sum\_{j=1}^i 1\[y\_j=0\].$$

In other words $B(t\_i)$ is the count of how many of the first $y$'s are equal to zero. Thus we get the recurrence relation

$$B(t\_i) = B(t\_{i-1}) + 1\[y\_i=0\]$$

with the base case $B(t\_0)=0$. This allows us to compute all of the $B(t\_i)$'s in $O(N)$ time.

We can similarly compute the $N+1$ values $C(t\_0),C(t\_1),\dots,C(t\_N)$ in $O(N)$ time, by scanning from right-to-left. Here we take advantage of a recurrence relation that computes $C(t\_i)$ given $C(t\_{i+1})$. The details are similar to that for $B(\cdot)$.

The result is that we can compute the sequence of $N+1$ values $B(t\_0)+C(t\_0),B(t\_1)+C(t\_1),\dots,B(t\_N)+C(t\_N)$ in $O(N)$ time. Then it is easy to find the largest value in that list. The running time in total is $O(N)$ time.

I don't think you can do any better than $\Theta(N)$ worst-case running time, since you may need to examine every item (in the worst case). Therefore,the method I have outlined above appears to be asymptotically optimal (up to constant factors).
> 1 votes

---
Tags: algorithms, machine-learning, discrete-mathematics
---


# Question
Title: Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays
A homework problem in my current CS class asks us to produce a *comparison-based* procedure for taking (essentially—there are some poorly-specified rules about duplicates) the set intersection of $k$ unsorted arrays of at most $n$ elements each. For full credit, we are supposed to do this in $O((k-1)n)$ comparisons. (Specifically, we are given a Java array of arrays of Comparable elements.)

I'm pretty thoroughly convinced that this is impossible, and that the best worst-case comparison bound for such a procedure is $\Theta(N\log n\_0)$, where $N$ is the sum of the lengths of the arrays and $n\_0$ is the length of the shortest array. I don't, however, know how to *prove* this is the best.

Since producing such an algorithm is current homework, please adhere to the following restriction in your answers/comments: if I am *wrong*, and it *is* possible to do better, do not reveal the algorithm unless it is very difficult (in which case a link to a relevant paper would be appreciated).

### What I've tried so far

The shortest array has $2^{n\_0}$ subsets. This gives an immediate information-theoretic lower bound of $\Omega(\log\_2(2^{n\_0}))$. Unfortunately, this is just $\Omega(n\_0)$, and $O(n\_0)$ obviously can't be obtained.

### Edit

I missed a line in the (rather long) assignment. It looks like what he's looking for is actually a lot less interesting than what I thought he wanted. However, I'm still curious about how to prove a lower bound of $\Omega(N \log n\_0)$, if that is the lower bound.

# Answer
I think we can prove that $O(n)$ time is not attainable for the special case $k=2$, using an adversary argument.

Fix a constant $c\>0$. Let's take two lists of $n$ items, where the resulting $2n$ items are all different. Consider an algorithm that has done $cn$ comparisons between the $2n$ items in the two lists. This defines a partial order $\preceq$ on the $2n$ items, where if the algorithm has compared $x,y$, we have either $x \prec y$ or $y \prec x$, and where we let $\preceq$ be the reflexive, antisymmetric, transitive closure of $\prec$.

I'm pretty sure that, with high probability over the choice of the lists, there exists some item $x$ in the first list and some item $y$ in the second list such that $x,y$ are incomparable under $\preceq$. (This needs proof; I'll let you fill this part in.)

Now we can consider a parallel universe where everything is exactly the same as before, except that in the alternate universe, $y=x$. This alternate universe is also compatible with all of the comparisons that have been made by the algorithm. Thus, the algorithm cannot distinguish these two universes, so it must produce the same output in both cases.

However, the correct output for the two universes differs. The correct output in the first universe is the empty set, while the correct output in the second universe is the element $\\{x\\}$. Consequently, the algorithm must be incorrect in at least one of these two universes. In other words, for at least one of these two inputs, the algorithm produces the wrong output.

It follows that, when $k=2$, any $O(n)$-time algorithm must produce an incorrect answer on at least one input. In other words, any correct algorithm must take $\omega(n)$ time.
> 1 votes

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


# Question
Title: Where is the recursion, in the minimax-decision algorithm?
The below is from an article titled:

> **Minimax: Recursive Implementation**

To be a recursive function, you need to call yourself.

* What part of this pseudo code is calling itself?
* How does depth-first effect the recursion process?
* There seems to be a return in every line of `minimax-value`, shouldn't the return be only on a terminal case?
* Will `value[op]` contain the moves in order from the root node?
* What does `Apply(op,game)` do the very first time through?

Any pointers are greatly appreciated.

# Answer
> 3 votes
Inside the function Minimax-Value, see the line where it says "the highest Minimax-Value of..."? That is implicitly a recursive call to the Minimax-Value function, i.e., a call to yourself.

---
Tags: heuristics, game-theory, board-games
---


title: An algorithm for making 2 carts meet

text:
# Question
Title: An algorithm for making 2 carts meet
Say I have 2 carts on an infinite railroad, each cart is initially under a lamp. There are only 2 lamps, and they are at a fixed location, hence they don't change their location. The distance between them is D, but its not known. Each cart has a processing unit, both will execute a copy of the same program once the whole system is "initiated".

The task: to write a code in pseudo-code, which will make the 2 carts collide.

Restrictions: The following commands can be used:

> 1. move left/right \*insert\_number\_here\* steps //each movement takes 1 clock cycle, meaning that "move left C steps takes C clock cycles
> 2. if underlamp \*put\_instruction\_here\* //if the cart is under a lamp
> 3. goto \*number\_of\_line\_here\*
> 4. stop

Variables, loops and not (!) are usable.

the given solution is:

> for i=1 to infinity:
>
> 1. go left i steps.
> 2. if underlamp stop.
> 3. go right i steps.

Now, I need a hint to help me make a simple improvement to the algorithm that is given in the trivial solution, so when the distance between the lamps is D, the total number of steps of both carts will be a first order polynomial function of D.

My lecturer gave the following solution, and told me to improve the given code using a different idea. This is his solution:

> 1. go right.
> 2. go right.
> 3. go left.
> 4. if underlamp goto 6.
> 5. goto 1.
> 6. go right.
> 7. goto 6.

My improvement of the given code, but I'm not sure that in this one, the total number of steps is a first order polynomial function of D.

> for i=1 to infinity:
>
> 1. go right i steps.
> 2. if underlamp goto 4.
> 3. go left.
>
> 4.for j=1 to infinity:
>
> 1. go right j steps.

# Answer
You asked for a hint. OK, here goes:

Obviously, we don't know $D$ (otherwise the problem is too easy). But suppose we do know an upper bound $U$ on $D$. In other words, suppose we know an integer $U$ and are promised that $D \le U$. Then it is possible to build a solution whose running time is a low-order polynomial of $U$. In fact, it is possible to build a solution whose running time is $O(U^2)$. Take a close look at your professor's algorithm (the one labelled "the given algorithm"), and think for a bit, and maybe you'll see how to accomplish this.

But what about the fact that we don't know the value of $U$? Well, you might ponder the sequence $1,2,4,8,16,32,\dots$. I'm being deliberately terse here since you asked for a hint, but if you ponder on this, I think you'll be able to find an algorithm that it meets all your criteria.
> 1 votes

---
Tags: algorithms, computer-algebra, pseudo-polynomial
---


# Question
Title: Time complexity of proximity search in distance matrix
I am a high school student computationally studying the 3-dimensional structure of chromosomes by 40 kilobase loci. In a nutshell, loci that are close in space tend to express their genes at the same time ― loci are different stops on a 3D-winding DNA chain.

The best way to understand the 3D structure is by gathering what are basically distances between loci.

Now I have an $n\times n$ ($n$ = number of loci studied) matrix where the $(i,j)$ entry is the distance between locus $i$ and locus $j$. I also have a (somewhat miraculous) 3-dimensional of the same chromosome that maps each locus to a certain point in a 3D $(x,y,z)$ coordinate system.

My task is to find all of the loci within a certain radius of locus $L$. With the matrix, I would have to go to $L$ and traverse many nearby locus-distance chains, possibly for a long time, before being any bit certain that I had everything I wanted (i.e. brute force). With the spatial model, I would only have to conduct a simple search within that radius.

Here is my question. What is the complexity of finding nearby loci in the 3D model and the 2D matrix with respect to loci count and radius size (whichever you think is more complex)? (Compare the two complexities and give both.)

I am not very studied in CS, but here is what I guess:

$$C\_\text{2D search best-case} = O(n^2)$$ $$C\_\text{2D search worst-case} = O(2^n)$$

Best-case is what you'd expect, and worst-case would be going through every permutation of the distance.

$$ C\_\text{3D search any case} = O(n) $$

This is just my rather fallible intuition.

# Answer
There are a number of candidate techniques you could use.

The simplest is just naive search. Given a locus $L$, just scan over all $n$ loci and see how close each one is to $L$. You might measure "close" as Euclidean distance in the 3D coordinate system. Naive search takes $O(n)$ time, since you have to examine each locus and you do $O(1)$ work for each locus you examine. In your example, it appears that $n=40,000$, so this might be perfectly efficient, given your miraculous mapping to 3D space.

If you want to do this task many times, you can preprocess the data you have to make subsequent queries faster. For instance, one candidate is to use the techniques described in the following question: Find all neighbors at a certain distance, in 3 dimensions Basically, you have the 3D coordinates for each locus, so you store those 3D points in a k-d tree or octree. Now given the 3D coordinates of a locus $L$, you can quickly scan the tree to find all neighbors that are near $L$ in 3D space. The asymptotic running time of these algorithms is hard to analyze, but it might be something like $O(\lg n)$ times the number of loci that are close to $L$.

---

If you didn't have the miraculous map to 3D coordinates, there are alternative approaches that use just the $n \times n$ matrix of edit distances, but they will be slower. For instance, if you have precomputed the $n\times n$ matrix, then you can use naive search: given a locus $L$, scan over all $n$ loci and see how close each one is to $L$ using the edit distance matrix. This will take $O(n)$ time, since you have to consider all $n$ loci and it takes $O(1)$ work for each look-up in the matrix.

Unfortunately, precomputing the $n \times n$ matrix of edit distances will probably take $O(n^2)$ time, or maybe even slower. (Therefore, unless you're going to do many queries, it is not clear that precomputing the matrix of edit distances is worthwhile.)

Anyway, even if you have the precomputed distance matrix, I don't know of any way to use nearest-neighbor search techniques to get the running time below $O(n)$ time. This is a significant difference from the case where you have the miraculous 3D map: if you have the miraculous map to 3D coordinates, it looks like you can make search much faster.
> 3 votes

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


title: Left Linear Grammar: How to construct?

text:
# Question
Title: Left Linear Grammar: How to construct?
I need help constructing a Left Linear grammar for the language

$L = \\{ a^n b^m c^p \mid n\geq 2, m\geq 3, p\geq 4 \\}$

Here is what I have so far, I know :

$N = \\{S\\}$

$T = \\{ a, b, c \\}$

$P = \\{$

$S \rightarrow Pcccc$

$P \rightarrow Pc$

$P \rightarrow M$

$M \rightarrow Mbbb$

$M \rightarrow Mb$

$M \rightarrow N$

$N \rightarrow Naa$

$N\rightarrow a$

$\\}$

I need help figuring out the productions. I am not sure if I am doing it right.

# Answer
In the strictest sense, productions of the form $X \rightarrow Y\alpha\beta\gamma\ldots$ (i.e. where there's more than one terminal) are not allowed, so if you want to be particularly formal, you would need to change the productions like $S\rightarrow Pcccc$ to a series of productions that do things step by step, e.g.

$S\rightarrow P\_{1}c$,
$P\_{1}\rightarrow P\_{2}c$,
$P\_{2} \rightarrow P\_{3}c\ldots$.

This is may not appear to be a serious problem, however there are mistakes in your grammar, for example it generates the string $acccc$ via the derivation $S\Rightarrow Pcccc \Rightarrow Mcccc \Rightarrow Ncccc \Rightarrow acccc$. Interestingly by fixing the transitions with multiple terminals, you fix this problem.

So for example, a small part of the change could (there are many possible correct grammars) be:

$S\rightarrow Pcccc$
$P\rightarrow Pc \mid Mbbb$

Importantly the $P\rightarrow M$ transition should be removed, it's what is allowing the jump past the $b$s, the key part of the change is forcing the first group of characters when you move from one nonterminal to the next.

There's also a small error where the grammar only allows 3 $a$s, but that's most likely a typo or close enough to one that it should be obvious how to fix it.

On a more general note, if you are comfortable with DFAs, you can treat both right and left linear grammars (but not unqualified linear grammars, has to be either right or left) in much the same way as a DFA, just thing of the nonterminals as the states, and the productions as the transitions - the terminal is the label on the transition and the nonterminal is the new state. The significant difference is that you don't need a production that deals with every terminal - grammars only deal with strings that are in the language, whereas automata have to deal with input that isn't in the language (and reject it).
> 3 votes

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


# Question
Title: Language where every prefix has almost equal a's and b's
Is the following language regular?

> $$L = \\{x \in \\{a, b\\}^\* \mid \text{in every prefix \\(w\\) of \\(x\\), } 0 \le |w|\_a − |w|\_b \le 2\\}$$
>
> If so, give a DFA for it with as few states as possible. If you claim that it is not regular give a pumping lemma proof that it is not regular.

I'm doing exam prep and have tried pumping this to no avail. I think I created a DFA that works but I'm not entirely sure because pumping similar examples (i.e. if the number of a's is strictly greater than b's) yielded results that are not regular. Is my DFA correct? Or is there something I can pump that will fail the lemma?

# Answer
Hint: as you read each letter of the input, imagine trying to keep track of the difference between the number of $a$'s and the number of $b$'s. What is the set of possible values that this could possibly take on, if the input is in $L$? What's the largest this difference could be? What's the smallest it could be?
> 4 votes

# Answer
Since your automaton is non-deterministic, it is hard to tell whether it is doing what it is supposed to. When trying to construct an automaton in order to prove a given language to be regular, I remind myself that these machines have a very limited memory, so I try to find out what is the variable to keep in track when reading the input string, and what are its possible "states". This is the reason why this language is regular, whereas the other one you mention (number of a's is strictly greater than b's) is not : there is something small to keep in track (with constant possible states) when recognizing its strings. It is not very different from the language of strings in $\\{0,1\\}^\*$ with an even number of 1s, or the language of strings with an equal number of '01's and '10's substrings.
> 3 votes

# Answer
Building an automaton for a language is usually not enough to convince a professor. Worse, your comments show it is not enough to convince yourself it works.

So, your task is now to assign a *meaning* to each of the states: what do they represent?

I think your automaton still needs some attention besides that. For instance, it is not deterministic.
> 2 votes

# Answer
This language is regular. A minimal DFA will have one state corresponding to each of the following possibilities:

1. The prefix has $\\#\_a = \\#\_b + 0$. This is the start state for the DFA. This is an accepting state.
2. The prefix has $\\#\_a = \\#\_b + 1$. This is an accepting state.
3. The prefix has $\\#\_a = \\#\_b - 1$. This is an accepting state.
4. The prefix has $\\#\_a = \\#\_b + 2$. This is an accepting state.
5. The prefix has $\\#\_a = \\#\_b - 2$. This is an accepting state.
6. The prefix satisfies none of the conditions given above. This is not an accepting state.

Transitions will be as follows: while in the state corresponding to $\\#\_a = \\#\_b + i$, where $-2 \le i \le 2$, transition to the state corresponding to $\\#\_a = \\#\_b + i + 1$ on seeing $a$ and the state corresponding to $\\#\_a = \\#\_b + i - 1$ on seeing $b$. If the target state is not one of the ones given in items 1-5 above, then transition instead to the dead state described in item 6; when in the dead state, all transitions are onto the dead state itself.
> 1 votes

---
Tags: regular-languages
---


title: Qubits Related to RAM?

text:
# Question
Title: Qubits Related to RAM?
I read in this article that the amount of bits that can be emulated by a certain number of qubits is 2^(number of qubits). This is because each qubit can be in one of 2 states after it collapses, and so before all the quantum... whatevers collapse, that is the function that gets that result. At least, that was generally what it was saying, but I probably mangled the explanation myself; sorry.

Anyway, this relation (2^n) happens to be the same as the relation between memory registers and RAM in classical computers (i.e. if the computer has n bits in the register, it can have up to 2^n bytes in RAM). Is this important? Does it mean qubits will become like the memory registers and their states like the RAM when we switch to quantum computers? Or is it just something that seems important but is actually meaningless in practice?

By the way, there don't seem to be any tags for some things I referenced, like RAM & memory registers. Is that because the site is so new, or am I just not looking hard enough?

# Answer
> 3 votes
This coincidence just shows that the function $n \mapsto 2^n$ shows up in many places. For example, an $n$ bit register can store up to $2^n$ different values. If wireless frequency is parametrized using $n$ bits, then there are up to $2^n$ possible frequencies (in fact, there are probably a bit less). If an IP address is $n$ bits, then there are at most $2^n$ possible IP addresses (in fact, there are fewer). If a cryptographic key is $n$ bits long, then there are $2^n$ possible keys. And so on.

---
Tags: memory-management, quantum-computing
---


title: What is the no free lunch theorem?

text:
# Question
Title: What is the no free lunch theorem?
I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser exists". On the other hand, the Wikipedia article talks about 'candidate solutions" that are "evaluated one by one" - if we only consider algorithms of a particular form, then that is a much more limited claim.

Can anyone explain what this theorem actually claims?

# Answer
The No Free Lunch theorem (NFL) was established to debunk claims of the form:

> My optimisation strategy X is always best.

In particular, such claims arose in the area of genetic/evolutionary algorithms.

The statement is, roughly: every optimisation strategy performs *badly* on *many* problems. Therefore, there can be no always-best strategy and your claim about X is wrong.
> 10 votes

# Answer
As far as I understand it, this theory is aimed at global optimization methods like Genetic Algorithms, Neural Networks, Simulated Annealing and so on...

The main claim is that if we consider all possible problem instances of a certain problem, these methods are just as good as any other optimizer that consider the same amount of candidate solutions, even Random Walk for example.

The general purpose optimizers will probably work well on many popular/real life problem instances, but these do not represent well the entire space of possible problem instances.
> 3 votes

---
Tags: algorithms, terminology, optimization, heuristics
---


title: What type of recursion is this?

text:
# Question
Title: What type of recursion is this?
I was trying to rule out whether this was LL(1) by checking for left-recursion in the following grammar:

$\qquad A \to 0 A 1 \mid 0 1$

Which produces:

$\qquad 0 A 1 \Rightarrow 0 0 A 1 1 \Rightarrow \dots$

But I am unsure what type of recursion this is called, since it sorta stays in the middle.

If this is not left-recursive, would you agree that this is not LL(1) because non-terminal A has 0 appear twice in FIRST(A)?

# Answer
**What is a name for ?**

There may be a name for that recursion, but then I would have forgotten it. It does not really matter. Call it *central recursion* or *middle recursion* if you will. And you can even define it simply :

> A recursive rule (or non-terminal) is said to be *middle recursive* iff it is recursive, but neither left recursive nor right recursive.

If I have to write a paper, and cannot find the accepted name for something, and there may be none, then I make one up and give a proper definition for it so that people can read my paper.

The point is that not everything needs to have a specific name. You give names only to entities and concepts that play a specific role in the kind of work you are doing. You example seems to be just a general case of recursion, which happens to be neither left nor right.

Left recursion is important as it plays a significant role when you study left-to-right recursive descent parsers. Hence it was given a name.

Regarding your second question, I would agree. This may even happen in the absence of recursion, with a grammar generating a finite language. $\qquad A \to 0 0 \mid 0 1$
But there are other grammars for that language. This grammar is not LL(1), but the language is.
> 2 votes

# Answer
For a given production of the form $A \rightarrow \alpha\_{1} \mid \alpha\_{2}$, to uniquely determine if $A$ should be expanded to $\alpha\_1$ or $\alpha\_2$, we need $FIRST(\alpha\_1) \cap FIRST(\alpha\_2) = \emptyset$.

According to Compilers- Principle, Techniques and Tools by Aho, Lam et. al.

"In general, if $A \rightarrow aP\_1 \mid aP\_2$ are two $A$-productions, and the input begins with a nonempty string derived from $a$, we do not know whether to expand $A$ to $aP\_1$ or $aP\_2$. However, we may defer the decision by expanding $A$ to $aA'$. Then, after seeing the input derived from $a$, we expand $A'$ to $P\_1$ or to $P\_2$."

This process is called left factoring of grammar.
> 0 votes

---
Tags: formal-grammars, parsers, left-recursion
---


# Question
Title: Prove that languages which contain words whose lengths are multiples of a constant are regular
This is a problem involving the theory of regular languages. I am stuck on this problem and do not know how to solve this type of problem.

> Prove that the language $B\_n = \\{ a^k \mid k \text{ is a multiple of } n \\}$ is a regular language for any $n \ge 1$.

Let me describe my thoughts thus far: It is easy to show that for $n=1$, we have $B\_1 = \\{a\\}$.

In other words, a regular expression can easily be built for the value of $n=1$, and thus for any $k$.

# Answer
> 5 votes
Since the multiples of $n$ are $0, n, 2n, 3n, \dots$, it's clear that $B\_n=\\{\epsilon, \mathtt{a}^n, \mathtt{a}^{2n}, \mathtt{a}^{3n}, \dots\\}$, in other words the set of all strings that can be made by concatenating arbitrarily many copies of $\mathtt{a}^n$. I'll bet you can find a regular expression denoting that language, for any given value of $n$.

# Answer
> 3 votes
Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs to L. Define a relation R on strings by the rule that x R y if there is no distinguishing extension for x and y. It is easy to show that R is an equivalence relation on strings, and thus it divides the set of all strings into equivalence classes.

The Myhill–Nerode theorem states that L is regular if and only if R has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing L is equal to the number of equivalence classes in R. In particular, this implies that there is a unique minimal DFA with minimum number of states.

For the above problem, try using congruence relation and partition the set of all strings into k equivalence classes.

References : http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode\_theorem

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


# Question
Title: Kleene star of an infinite unary language always yields a regular language
Let $L = \\{a^n \mid n \ge 0\\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$.

Thus $L$ consists of sequences of $a$ of all lengths, including a sequence of length $0$. Let $L\_2$ be any infinite subset of $L$. I need to show there always exists a DFA to recognize $L\_2^\*$.

If $L\_2$ is a finite subset it is very obvious as $L\_2$ would be a DFA and hence by Kleene closure $L\_2^\*$ would be recognized by a DFA. But I am unable to get it for infinite subset as $L\_2$ may not be expressed as DFA when, e.g., string lengths are prime.

# Answer
> 9 votes
Suppose there are two words in the language whose lengths are relatively prime. Let these lengths be $x$ and $y$. We know (see this) that by adding these numbers to each other repeatedly, we can get any number greater than $(x - 1)(y - 1) - 1$. So if $x$ and $y$ are $13$ and $7$, we can write any number greater than $72$ as a linear combination of $7$ and $13$. What this means for us: $L\_2^\*$ consists of some arbitrary finite language (regular, as all finite languages), in union with the language $\\{w \in a^\* \mid |a| \> (x-1)(y-1)-1\\}$. This language is regular since it is the language of all words with a finite set of words removed. Since $L\_2^\*$ is a union of regular languages, it must also be regular.

If all words in $L\_2^\*$ have lengths which share a greatest common factor (call this common factor $m$), then repeat the above argument, but instead of using string lengths, use string lengths divided by $m$. In this case, $L\_2^\*$ will be the concatenation of an arbitrary finite language (regular) and the language $\\{w \in (a^m)^\* \mid |w| \> m^2\[(x/m - 1)(y/m - 1) - 1\]\\}$, also regular (since $(a^m)^\* is regular and we are removing finitely many words from it).

For example, suppose all words in $L$ have a GCF of 2, and the language contains the words $a^4$ and $a^{10}$. We have $m = 2$, $x/m = 4/2 = 2$, and $y/m = 10/2 = 5$, which are relatively prime. Therefore, we know that we can get any word whose length is multiple of $m$ if the length is greater than $m^2\[(x/m - 1)(y/m - 1) - 1\] = 2^2\[(2 - 1)(5 - 1) - 1\] = (4)(3) = 12$ by concatenating $a^4$ and $a^{10}$.

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


# Question
Title: How to find whether a point is in a line or not
Suppose in a given plain there are fixed number of lines. A point P lies on one of the line. How to find which line intersects the point P ? I am giving an example

In the above graph point P is on the line CE. We can determine it visually.But my problem is how to make the computer understand it. Is there any algorithm available to make it so ?

# Answer
Any finite line is described by two points. assuming we are talking 2D here, then your graph can be described as a set of points, having X and Y coordinations, and a set of edges $E$, which describe which pair of points are connected with a line. Elementary geometry tell us the function expressing the points on these lines is $Y=(X-X\_0)\frac{Y\_1-Y\_0}{X\_1-X\_0}+Y\_0$ ($(X\_0,Y\_0), (X\_1,Y\_1)$ denote the two point's coordinations)

To check whether a point belongs to this line, insert the point's coordinates to the equation and see if the equation holds. since the line is not infinite, we should also check if the point is between the two points defining the line. If the equation holds, it is sufficient to check if one of the point's coordinates (say $X$) is between the two point's defining the line ($X\_0$ and $X\_1$).

So, for any line in the graph, perform the check explained above, if the above criteria holds, the line contains P.

Checking if P is on a specific line takes constant amount of computational effort, so the running time of this procedure is $O(E)$.
> 5 votes

# Answer
Using homogeneous coordinates, $P$ lies on the line $EC$ if, and only if, $P^{\mathrm{T}}(E \times C) = 0$, where $\times$ is the cross-product and ${}^{\mathrm{T}}$ denotes transpose.
> 2 votes

# Answer
As an alternative to Ron Teller's excellent answer, there is a formula that gives the distance separating a point and a line. Using this formula may prove a more natural way to determine whether the point falls on the line if using floating-point representations.

Of course, you must then check that the X and/or Y coordinate of your point fall between the coordinates of the points defining your line segment, as Ron points out.
> 1 votes

---
Tags: algorithms, computational-geometry
---


title: Genetic algorithm fitness function

text:
# Question
Title: Genetic algorithm fitness function
I'm trying to write some little code (POC for the selection/mutation operators) that uses a genetic algorithm to solve a global maximum for a function.

```
f(x_1...x_n) = M - (x_1 - a_1)^2 - (x_2 - a_2)^2 - ... - (x_n - a_n)^2

```

M a\_i are constants. I have to find x\_i such that f(x\_i) = max(f) = M

My selection method is truncation (I select the top 100 fittest of a population of 500). My crossover method is average. there is a 80% chance for crossover, other wise one of the parents is passed on. My elite count is 5 (1% of the population) There is a 3% chance for a mutation for an individual, the range of the mutation is \[-0.3, 0.3\]

My fitness function is f it self and my stopping condition is ABS(previous best fitness - current best fitness) \<= 10^(-21)

You can find the code I wrote here.

The problem is that it converges before it reaches even an approximate solution.

What can I change in the solution approach so that the algorithm would converge on the maximum(f)? (This is not my algorithm, it's a reduction of a problem I have at work.)

# Answer
I haven't looked at your code, but a few observations.

* Your selection method is very strong. If you generate 500 individuals at random and choose the best 100, within just a few generations you're going to have a population dominated by descendants of that initial 100 winners. In effect, you're very quickly focusing your search on the best 20% of a random sample. You probably need something like tournament or rank-biased selection instead -- something *dramatically* weaker than what you have.
* The elite count is maybe a tad high as well. 5 might be OK, but certainly combined with your selection method, you have an algorithm that's basically designed to converge too quickly.
* Averaging in crossover may or may not be harmful. It depends on where the optimal values of your parameters lie. Take a problem like "minimize f(x)=x^2 for x in \[0, 100\]". The optimal value of x in that problem is at 0, and averaging two parents will in this case *always* result in worse offspring than one of the parents you started with. For other problems, this may be helpful instead though. If you want to try something else, Simulated Binary Crossover (SBX) is often used for real-valued optimization problems. Alternately, one approach is to reduce the crossover rate and increase the mutation rate to provide a wider search of the parameter space.
> 2 votes

---
Tags: algorithms, optimization, heuristics, genetic-algorithms
---


# Question
Title: How to determine letter boundaries in Huffman encoded strings?
I'm trying to understand the Huffman compression algorithm.

Lets assume the word : **YESSSS**

According to Huffman tree we will get :

* S : 4 times -\> Code : 0
* Y : once -\> Code : 01
* E : once -\> Code : 00

at the end YESSSS will become : **01 00 0 0 0 0**

So far everything is clear.

Now my problem is in the space between the binary words. How this can be stored in memory ?

In another words ?

How to computer will know that that :

* the first character has two bits
* the second character has two bits
* the fourth other characters has only one bit

Because **01 00 0 0 0 0** doesn't have the same meaning than **01 00 00 00**

* **01 00 0 0 0 0** means : YESSSS
* **01 00 00 00** means : YEEE

Any ideas please ?

# Answer
Huffman codes are prefix-free codes (no codeword is a prefix of another), and so they are uniquely decodable. That means that if you encode a message using a Huffman code, then there is no other message that results in the same encoding.

Here is why. Suppose that $w$ is some binary string. We will show that $w$ encodes at most one message, in the Huffman code $\\{c\_1,\ldots,c\_n\\}$. Let's try to factor $w$ as $w = c\_i w'$. I claim that this can be done in at most one way. Otherwise, we would have $w = c\_i w' = c\_j w''$, and so either $c\_i$ is a prefix of $c\_j$ or the other way around. If there is no such factorization, then $w$ encodes no message. Otherwise, suppose $w = c\_i w'$. Then the first character of the message (if there is any) is $i$, and the rest is encoded by $w'$.

Prefix-free codes can be decoded very efficiently: to find the prefix $c\_i$ alluded to in the preceding paragraph, just follow the Huffman tree until you get to a leaf. There is no look-ahead. There is a more general class of codes, *uniquely decodable codes*, which are codes satisfying what we proved in the last paragraph: every string is the encoding of at most one message. Such codes could require arbitrary large look ahead: consider for example $\\{00,10,1\\}$ and a word $1 w^n$. If $n$ is even then this is broken up $1(00)^{n/2}$, if $n$ is odd then $10(00)^{(n-1)/2}$. In order to tell which is which, we need to look ahead to the end of the string.

Given that prefix-free codes are easier to decode, but uniquely decodable codes are more general, you could ask: do we gain something by allowing uniquely decodable codes which are not prefix-free? This is answered by the Kraft–McMillan inequality: every uniquely decodable code $\\{c\_1,\ldots,c\_n\\}$ satisfies $$ \sum\_{i=1}^n 2^{-|c\_i|} \leq 1, $$ and conversely every set of codeword lengths satisfying this inequality correspond to some prefix-free code. So prefix-free codes are as general as it gets.

---

The proof is not too difficult. Suppose $c\_1,\ldots,c\_n$ is uniquely decodable, with maximum codeword length $M$. Consider the encodings of all words of length $\ell$. Weight each encoding $x$ by $2^{-|x|}$, and sum. You get $$ \left(\sum\_{i=1}^n 2^{-c\_i}\right)^\ell. $$ On the other hand, since the code is uniquely decodable, for each possible length, $2^{-|x|}$ must sum to at most $1$. Since words of length $\ell$ are encoded by strings of length at most $M\ell$, we conclude $$ \left(\sum\_{i=1}^n 2^{-c\_i}\right)^\ell \leq M\ell. $$ Taking $\ell$th roots and letting $\ell \to \infty$, we recover the inequality.

For the other direction, suppose that the integers $\ell\_1,\ldots,\ell\_n$ satisfy $\sum\_{i=1}^n 2^{-\ell\_i} \leq 1$. Without loss of generality, we can assume that the sum is exactly $1$: otherwise, suppose that the sum is $A/2^B$ (for integer $A$), and add $2^B-A$ new integers equal to $B$.

I claim that either $n = 1$ or there must be a subset of these summing to exactly $1/2$. Indeed, suppose $n \> 1$, and arrange all weights in non-decreasing order $\ell\_1 \leq \dots \leq \ell\_n$, and look at the running sums $2^{-\ell\_1} + \dots + 2^{-\ell\_i}$. There must be a first index at which they cross $1/2$, say $2^{-\ell\_1} + \dots + 2^{-\ell\_i} \geq 1/2$ but $2^{-\ell\_1} + \dots + 2^{-\ell\_{i-1}} \< 1/2$. Write the latter sum as $S = A/2^B$, where $B \leq \ell\_{i-1} \leq \ell\_i$ and $A \< 2^{B-1}$. Then $S + 2^{-\ell\_i} = (A + 2^{B-\ell\_i})/2^B \geq 1/2$, so $A + 2^{B-\ell\_i} \geq 2^{B-1}$. Since $2^{B-\ell\_i} \leq 1$, we must have $2^{B-\ell\_i} = 1$ and $A + 2^{B-\ell\_i} = 2^{B-1}$, so $S + 2^{-\ell\_i} = 1/2$.

When $n = 1$, the code $\\{\epsilon\\}$ is a prefix-free code with codeword lengths $0$. For $n \> 1$, divide the weights into two sets $L\_0,L\_1$ such that $\sum\_{i \in L\_0} 2^{-\ell\_i} = \sum\_{i \in L\_1} 2^{-\ell\_i}$. Construct two prefix-free codes $C\_0,C\_1$ from the lengths obtained by subtracting $1$ from all weights in $L\_0,L\_1$, respectively. Now glue these codes together by prefixing $C\_0$ by $0$ and $C\_1$ by $1$.
> 2 votes

# Answer
In short: your codes are wrong, and should be S:1, Y:01, E:00 (or equivalent; your code is not a prefix code); the key must be stored with the message to be decoded (and you must have some way of knowing that the (key, coded message) pair represents a message coded according to the associated key). For instance, a real program that's doing Huffman encoding might spit out a file that looks like this:

```
01. This is encoded using Huffman's algorithm.
02. 1:S, 01:Y, 00:E
03. 01001111

```
> 1 votes

---
Tags: coding-theory
---


# Question
Title: How to generate the LR(0) finite state machine for a grammar
Here is a context-free grammar with a single nonterminal symbol S and three terminal symbols +, \*, and s:

S -\> + S S | * S S| s

My purpose is to build the LR state machine for this grammar. My attempt:

```
[State 0]      ->     [State 1]       ->       [State 2]
S -> . + S S   (+)    S -> + . S S    (*)      S -> * . S S
S -> . * S S          S -> . * S S             S -> . + S S //leads to loop
S -> .s               S -> .s

```

When I get to state 2, I see that an infinite loop begins to form. I think I am missing/misunderstanding part of the algorithm to form the machine. Can you ignore a production if it already exists somewhere else?

# Answer
There is no loop, an item like $S\to \bullet{+}SS$ in your example might occur in several item sets of the LR automaton. Let us continue the construction of state 2:

```
[State 2]
S -> * . S S
S -> . + S S
S -> . * S S
S -> . s

```

It has transitions to itself on "$\*$", to state 1 on "$+$", to some state 3 with item set $\\{S\to s\bullet\\}$ on "$s$", and to yet another state on "$S$":

```
[State 4]                 [State 5]
S -> * S . S   --(S)-->   S -> * S S .
S -> . + S S
S -> . * S S
S -> . s

```

State 4 has again a transition to state 1 on "$+$", state 2 on "$\*$", and state 3 on "$s$". The construction is not complete yet, since you are missing some outgoing transitions from states 1 and 0, but hopefully you can finish it yourself.
> 1 votes

---
Tags: automata, formal-grammars
---


title: Reducing 3SAT to Triangle Cover Graph

text:
# Question
Title: Reducing 3SAT to Triangle Cover Graph
The Triangle Cover Graph problem is this:

> Given a graph $G = (V,E)$ and an integer $k$, does there exist a set of at most $k$ vertices of $G$ such that every triangle contained in $G$ also contains a vertex of the set?

This problem is obviously in $NP$ as its verifier is just the set which you can easily check. However, what's the reduction to be able to show that this is NP Complete?

I recognize the fact that a good reduction for this problem would be for 3-SAT as you could easily take a 3-sat instance and make a 3-vertex triangle in the graph corresponding to the variables which are in each clause. However, I wasn't able to come up with a way to connect the different triangles together to ensure that the assignment of vertices would be a satisfiable truth assignment.

# Answer
> 2 votes
Hint: The obvious thing to do would be to have two vertices $v^+,v\_-$ per variable and one triangle per constraint. You might have to tweak this construction a little to avoid the possibility that both truth values are selected for some variable. You can do this using a "gadget", one per variable, that forces the selection of at least one truth value per variable.

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


# Question
Title: Deleting vertices so that largest connected component has at most $n/2$ vertices
I have a question regarding a graph algorithm which is as follows:

Given a graph $G = (V,E)$ whose vertices are uniquely labeled $\\{1, 2,\dots ,n\\}$ we want to determine the smallest integer $k$ such that deleting vertices $1$ through $k$ results in a graph whose largest connected component has at most $n/2$ vertices (when we delete a vertex we also delete all edges incident to that vertex). Give an $O(m \log^\* n)$ algorithm that determines $k$.

The graph at the beginning could be disconnected, nor at the end need it be connected. Since $O(m \log^\*n)$ is almost linear, $\log^\*n$ grows very very slowly like in union-find data structure so this algorithm is almost linear time like union-find. I am trying to solve it through union find but it seems I am doing something wrong. Now I think that I should use union-find as a black box, but I ca'nt figure it out.

This is a practice problem, not homework.

# Answer
Hint: Try working backwards, adding vertices to the graph in reverse order $n,\dots,1$.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Degree conditions sufficient for Hall's theorem
Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the graph).

Konig's theorem proves that every $k$-regular bipratite graph has exactly $k$ edge disjoint perfect matchings, so the answer is obviously yes for any $k$-regular bipartite graph with $k\>0$ (it's not hard to see why hall's condition is satisfied in this case).

Is there a wider rule?

For example: Let $|L|=|R|=n$, What is the minimal degree as a function of $n$ of every vertex in the graph such that the graph must admit a perfect matching?

I'm also wondering if these conditions will hold in general graphs (satisfying Tutte's theorem), and if not, then are there similar conditions for general graphs.

# Answer
> 2 votes
Are you by any chance looking for Hall's theorem ? It gives a complete characterization of when a bipartite graph admits a perfect matching. Specifically:

G admits a perfect matching if and only if for all subsets $S \subset L$, we have $$ |\Gamma(S)| \ge |S|$$ where $\Gamma(S) \subset R$ is the set of neighbors of vertices in $S$.

---
Tags: graphs, matching
---


# Question
Title: Worst case running time to search for an element in a balanced BST with $n2^n$ elements
What is the worst case running time to search for an element in a balanced binary search tree with $n 2^n$ elements?

The answer is $\Theta(n)$.

My answer:

To search an element in BST is $\log (n)$ so $$ \begin{align\*} \log(n 2^n ) &= \log(n) + \log(2^n) \\ &= \log(n) + n\log 2 & \text{(base is 2)} \\ &= \log(n) + n \end{align\*} $$

> Why have they used $\Theta$ in the answer?
> And why only $n$?

# Answer
> 4 votes
You state that searching an element in a BST takes time $\log n$, but this is wrong on two counts. First, this is (roughly) the *worst-case* number of comparisons. Second, the running time itself isn't exactly $n$ but is roughly $C\log n$ for some constant $C$ that depends on the exact machine model (assuming that comparisons take constant time). For this reason, it is better to use $\Theta$ notation (look it up!) and state that the worst-case running time of element lookup in a BST is $\Theta(\log n)$, where $n$ is the number of elements in the BST.

In our case, the number of elements is $n2^n$, and so the running time is $\Theta(\log(n2^n)) = \Theta(\log n + n) = \Theta(n)$. Asymptotically, $n + \log n = \Theta(n)$, and so there is no need to explicitly mention $\log n$.

# Answer
> -1 votes
In question, they are asking only the worst case time,so, they comparing log n(log base 2) time with n time. So, the worst case time is n becasue n is larger than the log n time..

---
Tags: asymptotics
---