# Question
Title: Prove that { ⟨M⟩ ∣ ⟨M⟩ ∉ L(M) } is undecidable
Prove that $L = \\{\langle M \rangle \mid \langle M \rangle \notin L(M)\\}$ is undecidable. Hint: If there were a decider TM DL for L, what would happen if we gave DL its own description as input?

Here's what I've got so far:

$\mathrm{ATM} ≤\_M M$ (with $\leq\_M$ being mapping reducible)

Find a map : $f: \langle M \rangle \to \langle DL \rangle$ such that DL doesn't recognize w if and only of x is M's own description.

```
DL(w):
 if w != description:
    run on M(w)
    if M(w) accepts:
       return accept

```

I couldn't figure out how to relate DL to ATM to prove that L is unrecognizable. My answer might be partially wrong, but I tried my best. Any help is appreciated.

# Answer
> 1 votes
You do not need to reduce $ATM$ to $L$. As it hints, Let $L$ is recognized by a TM $M\_L$, and note that $L = L(M\_L)$ ($L(M\_L)$ denotes the language recognized by $M\_L$). Then you have the following contradictions $$\langle M\_L \rangle \in L \implies \langle M\_L \rangle \notin L(M\_L) \implies \langle M\_L \rangle \notin L$$ and $$\langle M\_L \rangle \notin L \implies \langle M\_L \rangle \in L(M\_L) \implies \langle M\_L \rangle \in L$$ This completes the proof.

---
Tags: computability, turing-machines, undecidability
---


# Question
Title: Is there any standard for comparing runtimes experimentally?
### My situation

I am writing a paper presenting a software module I developed and I want to compare its runtime to other modules for the same task. I am aware of the drawbacks of runtime experiments, but please assume as given that there is no way around it in my case. (I can and do deduce some properties theoretically, but it doesn’t suffice for everything.)

The specific scenarios I want to use for benchmarking have two parameters: the complexity $n$ of the problem and a random seed $r$ which determines the detailed problem. Mainly I want to show the dependence on $n$. Going by preliminary investigations and theory, the influence of $r$ on the runtime is minor or negligible. A single task takes at most ten minutes to complete.

### Actual question

I am looking for some commonly accepted or published procedure on performing such experiments or at least a list of common pitfalls (ideally published).

### What I found so far

Nothing. Internet searches turn up all sorts of unrelated results, but then I may not be using the right terminology. Including the keyword *minimum,* which I know to be a good standard (see below), didn’t help either.

### How I would do it

* Run all experiments on the same machine with potentially interfering software such as a GUI disabled as far as possible.
* Subject all modules to the same selection of scenarios, i.e., the same $n$ and $r$.
* For each scenario, test the different modules directly after each other in random order. With other words, the loop over the different modules is the innermost one. This should avoid bias on the different modules due to slow fluctuations of the machine’s performance (e.g., due to temperature changes). The random order should avoid bias through such effects as caching or one module always being tested after the same one.
* For each $n$, take the minimum runtime over several scenarios with different seeds as the benchmark. This should avoid bias on the different modules due to short-time fluctuations of the machine’s performance that make individual runs exceptionally bad.

# Answer
> 2 votes
C.C. McGeoch's "A Guide to Experimental Algorithmics" is a good reference for

* how to set up experiments on algorithms,
* how to interpret and use results, and
* how to iterate towards more meaningful results if necessary.

# Answer
> 2 votes
In addition to elapsed time for each run, report seconds of user & system mode, and total IP packets, and total disk I/Os, if only to verify that some numbers are consistently "low" and have negligible impact on elapsed time.

On https://wiki.freebsd.org/BenchmarkAdvice PHK and others offer good advice, including

> Use ministat to see if your numbers are significant. Consider buying "Cartoon guide to statistics"

---
Tags: algorithm-analysis, reference-request, runtime-analysis, experimental-analysis
---


title: How to convert between bases partially?

text:
# Question
Title: How to convert between bases partially?
I have some large number $n$ in base $b\_1$ and I want to convert it to base $b\_2$. $n$ is about a million decimal digits long, therefore it's impractical to convert it as a whole. However I don't need the entire $n$, just **some arbitrary slice** of it when it's converted to $b\_2$

For example converting from base 10 to base 3, with a slice from digits 5-10:

```
n(10) = 2347892347
n(3) = 2000[11212]22021210211
m(3) = 11212 <-- the number I need

```

*note: it doesn't matter if the slice starts from the left or the right of the number*

Is there a fast method to get that slice $m$? Any help is very much appreciated.

# Answer
> 1 votes
Partial answer:

It works for some pairs $b\_1$ $b\_2$, but may not work for every pair.

Partial solution:

for pairs $b\_1$ $b\_2$ where there is an $x, p\_1, p\_2 \in \mathbb{Z}$ such that

$\begin{alignat\*}{4} x^{p\_1} & {}={} & b\_1\\ x^{p\_2} & {}={} & b\_2 \end{alignat\*}$

you can divide $n$ of $b\_1$ into sections of $p\_2 $ digit sections, which you can then convert into $b\_2$.

If you want to query a slice in the result $b\_2$, you need to calculate the section number by dividing by $p\_1 $

3 -\> 10 doesn't work with this, but I will give you an example

8 -\> 16:

$x = 2, p\_1 = 3, p\_2 = 4$

```
8  [....][1][2][3][4][..p2 * x blocks..]
2        001010011100
16 [....][ 2][ 9][ C][..p1 * x blocks..]

```

3 -\> 9:

$x = 3, p\_1 = 1, p\_2 = 2$

```
3  [....][1][0][2][1][..p2 * x blocks..]
3          1  0  2  1
9  [....][   3][   7][..p1 * x blocks..]

```

---
Tags: algorithms, optimization, base-conversion
---


# Question
Title: Reverse the input and output of a Mealy machine
Given a Mealy machine $M$, is it possible to construct another Mealy machine $M'$ that generates the reverse outputs from the reverse inputs, and if so, how?

That is, for each string $s$, $M(s) = t$ iff $M'(s') = t'$, where $s'$ is $s$ reversed and $t'$ is $t$ reversed.

For example, if $M(\`\`abcd")$ is $\`\`efgh"$ then $M'(\`\`dcba")$ should be $\`\`hgfe"$.

# Answer
> 2 votes
That's not possible in general. The classical Mealy machine definition requires the Mealy machine to accept infinite-length input strings and produce infinite-length output strings while reading the input. You can't reverse an infinite-length input string and can't reverse an infinite-length output stream, since there is no last letter in the unreversed string that you could put as first letter in the reversed string.

So for your question to make sense, you would first need to change the definition to allow the Mealy machine to have missing successors for some state/input combination, so that an input word ends at a well-defined position. Then, you would need to assume that the automaton eventually has a missing transition for every possible input word. This excludes all cycles in the automaton.

If we have this, then there is only a finite number of different input strings. If $M'$ is actually well-defined, then it is possible to build such a Mealy machine. But $M'$ may not be well-defined. For example if $M(\textit{abcd}) = \textit{efgh}$ and $M(\textit{cd}) = \textit{he}$, then we have $M'(\textit{dcba})=\textit{hgfe}$ and $M'(\textit{dc}) = \textit{eh}$. By the definition of Mealy machine, this also means however that $M'(\textit{d})=\textit{h}$ and $M'(\textit{d}) = \textit{e}$, which is a contradiction.

---
Tags: automata, finite-automata, closure-properties
---


# Question
Title: Greedy algorithm: Minimizing the maximum of a list
> Given a list $L$ of positive integers, assuming you can only modify the list by "splitting" its numbers a finite number $n$ of times. Write an algorithm which minimize the maximum of the last generated list.

By "splitting" a number $x$ I mean deleting $x$ from $L$ and adding to $L$ two positive numbers $\alpha,\beta$ verifying $\alpha+\beta=x$. We can only do this $n$ times.

My try was taking the two greatest elements of $L$, $\alpha$ (the maximum) and $\beta$ (the other), then I split $\alpha$ into $c=\min(\alpha/\beta+1,n+1)$ equal parts (the last part will be $\frac{\alpha}{(\alpha/\beta+1)}+\alpha\text{mod}(\alpha/\beta+1)$). So I spend $c$ of the hability.

Then I repeat the process until I run out of the hability or $\beta=1$, so then y take $c=\min(\alpha/\beta+1,n+1)-1$.

I know my try is not correct, as the list $(10, 4, 9)$ for $n=4$ is a counterexample. Any idea?

I'm not looking for efficiency details (it can be achieved working with heaps), only for correctness.

# Answer
If we use $k$ splits on a single element $x$ of the list, the lowest value we can reach is $\dfrac{x}{k+1}$. In turn, we need $\displaystyle k = \left \lceil\frac{x}{v}\right\rceil - 1$ splits for $x$ to reach a certain value $v$.

Elements do not affect each other, after all to reach some maximum $v$ after splitting each element must reach it individually.

So you simply want to find the smallest possible $v$ such that $$\sum\_{x \in L}\left\lceil\frac{x}{v}\right\rceil \leq n + |L|$$

You can find $v$ to arbitrary precision by using a binary search using the above check, starting with range $\[0, \max L\]$. Finding an exact answer is somewhat trickier though.
> 3 votes

---
Tags: algorithms, optimization, greedy-algorithms
---


# Question
Title: How to retrieve reset bit in constant time in a bit array
In a game application there is a session id assigned to each player every time they start a new session. Session id's are always unique and there can be billion users of this game. Whenever a user logs-in, get() function is called which basically assigns a bit to the user by setting a bit from a bitarray and when user logs out, set() function is called which resets that bit.

So,it may happen that at some point the bit array looks like below: 101010101000011111

For uint\_32 bitarray\[100000\], 100000 integers needs to be searched for finding out reset bit in worst case if linear search is used. Is it possible to make this search constant time?

For a 32/64 integer and not using bit array this would be pretty much constant using bit operation (x&-x) but for a bit array getting constant time it would be not that easy.

Is there any data structure which I can use for this purpose? I think we can use skip list for this but need some information as to the right approach to insert and delete element from this skip list?

# Answer
> 3 votes
Access into a bit array is constant time. In particular, if you have an array that is stored contiguously in memory, indexing into the array takes constant time: reading $A\[i\]$ takes constant time, regardless of how large $i$ is. That's all that you need to do to access a bit array. In particular, if you have an array of bytes, then you can read the $i$th bit of the bit-array by reading $A\[i/8\]$ and doing a bit-masking operation to get the $(i \bmod 8)$th bit of that byte, and so on.

If you want to find a new session id that is not in use, that can be done in (expected) constant time as long as at least 1/2 of the session ids are not in use. You simply pick a random session id, check whether it is in use, and repeat until you find one that is not in use. If at least 1/2 of the session ids are not in use, the expected number of times you need to repeat this until you find one that is not in use is 2 (as it's expected the number of coin tosses until you get a heads, which is a geometric series), i.e., a constant. Each iteration takes constant time, so the whole thing can be done in $O(1)$ time.

So, a bit array already meets all of your requirements. Just make sure that at least 1/2 of the session ids are not in use.

(What do you do if more than 1/2 of the session ids are in use? Double the size of the array, copying over the old array if needed. The doubling will happen rarely enough that the amortized time for each operation remains constant, i.e., $O(1)$.)

---
Tags: algorithms, balanced-search-trees, bit-manipulation
---


# Question
Title: Checking for intersection of $d$-dimensional spheres
Is there a simple algorithm to check whether $n$ different balls (of the same radius) in $\mathbb{R}^d$ intersect? That is, coordinates of their centers $x\_i$ are given, radius $R$ is given and we need to determine if there exists a point $p$ such that $$\\| p - x\_i \\| \leq R \quad \forall i.$$ In other words, check whether there is a point $p$ that is contained in all $n$ balls.

# Answer
This is an instance of the smallest enclosing ball problem.

An equivalent statement of your problem is: Given points $x\_1,\dots,x\_n$, we want to determine whether there exists a point $p$ such that every point $x\_i$ is at distance at most $R$ from $p$, i.e., we want to find a sphere of radius $R$ that encloses all of the points $x\_1,\dots,x\_n$.

So, find the smallest enclosing ball that contains all of $x\_1,\dots,x\_n$; then check whether the radius of that ball is at most $R$ or not. The smallest enclosing ball problem is well-studied and you can find references and algorithms in the Wikipedia page I linked to.
> 4 votes

---
Tags: computational-geometry
---


# Question
Title: Are there noncomputable functions with a finite search space?
The top rated answer to Why, really, is the Halting Problem so important? lists a few examples for a noncomputable problem. However, these mostly involve an infinite search space. Are there noncomputable problems with a finite search space? If not, why not?

# Answer
Depends on what exactly you have in mind.

If the problem is to find an element with decidable (!) properties among a recursively enumerable set $A$ (of finitely represented elements), then yes: if $A$ is finite, the problem is trivially computable. Just check every element.

If $A$ is finite *but unknown*, it's more interesting but still: the problem is computable, since *there is* an algorithm that checks the every element in $A$, even though we can't point it out. See this for an example.

If the identifying property is undecidable, then the problem may be¹ uncomputable. For instance, the search space for the question "Does TM M halt on input x?" is finite -- just two possible answers -- but the problem is (in)famously undecidable.

---

1. It's possible that the property as written down is not needed to identify the correct element.
> 1 votes

---
Tags: computability
---


# Question
Title: How to find longest possible identical sequence in Array A and B?
You have to arrays of single digit numbers. (0 - 9).

```
A = [....1 billion elements....];
B = [3,5,8,1,2,5,8,3,4,9,1,0,2];

```

I want to find combo of as few as possible subsets that of array B in A.

So whole Array B could be in Array A by coincidence since it's very large and that would be the largest match as whole sequence is there. Or you could have subset of array B, `[8,3,4,9]`, at index ex: `i = 3800443`...

Now my goal is to convert Array B to references based on Array A.

So If I give you object like this:

```
{
  block1: {i: 48938, len: 388},
  block2: {i: 2828, len: 3},
  ...
}

```

you'd be able to reconstruct array B if you had array A.

One mistake would be to go and find biggest subset only. Then the solution would have biggest subset, but not minimum amount of subsets possible.

Example:

```
a = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |^||^||^||^||^||      ^     ||^|

```

Although this has longest subset, but It ended up with 6 blocks. Whereas,

```
b = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |    ^    ||     ^    ||    ^   |

```

here each subset might not be the longest but there are fewer subsets to cover whole array.

# Answer
> 4 votes
Assuming all characters of $B$ are wholly contained in $A$, then this method should give you an optimal results.

### Algorithm

1. Compute the longest substring $P\_i$ in $A$ that is a prefix of the suffix of $B$ from $B\_{i \ldots n}$. This is essentially equivalent to finding the longest common substrings between $A$ and $B$ starting at index $i$ of $B$. There are many methods of doing this, some listed below:
    1. Compute a suffix tree $T$ for the array $B$. Making sure to leave in the suffix links (these are important for back tracking and essentially make the tree like an Aho-Corasick state machine). Traverse $A$ using $T$ as a state machine. Keep track of deepest non-root node reached in $T$ for each path from root to leaf. This will take $\Theta(|B|) + \Theta(|B| + |A|) = \Theta(|B| + |A|)$.
    2. Solve this by inserting both strings $A$ and $B$ into a generalized suffix tree. Keep track of deepest common ancestor between a suffix leaf of $B$ with any other suffix leaf in $A$. This will take $\Theta(|B| + |A|)$.
    3. Least optimal, use dynamic programming, but reverse the formula so you compute longest prefix for a suffix, rather than longest suffix for a given prefix. This will take $\Theta(|B|\cdot |A|)$. (Would not recommend)
2. Sort $P$ by the index of the starting character of the prefix (i.e. in the original suffix order).
3. Let $i = 0$
4. While $i \< |B|$:
    1. Let $j$ be the last index of substring $P\_i$.
    2. Add substring $P\_i$ to a set $S$.
    3. Let $i = j+1$
5. Return $S$ as it is the set of sequences in $A$ that minimally but completely cover $B$.

### Running Time

Let $n = |B|$ and $m = |A|$:

1. Will take $O(n + m)$ because branching factor is constant (only 10 values) and if you keep it compressed and refer to indices instead of values.
2. Will take $O(n \log n)$ or $O(1)$ depending on how you structure $T$.
3. Will take $O(n)$.

Total time will be $O(m + n)$ which will be $O(m)$ for $m \gg n$.

### Example

Let $$B = \[0, 1, 3, 1, 2, 0\]$$ $$A = \[2, 1, 3, 0, 5, 1, 2, 4, 0, 1, 3, 0, 3, 1\]$$

Step 1 would compute the following tree:

Step 2 should generate the following longest prefixes $P$ for suffix $S$:

$$\begin{array}{|c||r|r|} \hline B \text{ indices} & S & P \\ \hline \[0\ldots 5\] & 0,1,3,1,2,0 & 0,1,3 \\ \hline \[1\ldots 5\] & 1,3,1,2,0 & 1,3 \\ \hline \[2\ldots 5\] & 3,1,2,0 & 3,1 \\ \hline \[3\ldots 5\] & 1,2,0 & 1,2 \\ \hline \[4\ldots 5\] & 2,0 & 2 \\ \hline \[5\ldots 5\] & 0 & 0 \\ \hline \end{array}$$

We then follow steps 5, 6, and 7 to get that our set to be returned is contained of: $$P\_0 = \[0, 1, 3\], P\_3 = \[1, 2\], \text{ and } P\_5 = \[0\]$$

It's also easy to think of this as the maximum number of disjoint subsequences of $B$ contained in $A$. The maximum here is 3 because there are at most 3 subsequences that have no overlapping pieces:

Maybe this visualization will help. Then we should keep track of indices along the way in $A$ (this is relatively trivial with proper manipulation), but we see $B$ can be represented by:

$$A\[6 \ldots 8\] \\; A\[4 \ldots 5\] \\; A\[3 \ldots 3\]$$ $$0,1,3 : 1,2 : 0$$

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


# Question
Title: Minimum amount of swaps needed to sort a stack
Given a stack, what is the minimum amount of swaps needed to sort it? Since the bottom of it stays intact and we slowly move to the upper part of it, if the stack contains n elements, the amount of swaps f(n) would be

> f(n) \< n

for n = 1, 2, 3, 4, is that correct? I cannot find a more accurate way to express it. Also, how do we calculate the f(n) for n \> 4?

# Answer
> 4 votes
Your problem is known as Pancake sorting and it is not true that $f(n) \< n$. The minimum number of swaps is between $\frac{15n}{14}$ and $\frac{18n}{11}$.

Currently we know empirically that $P\_{17} = 19$, which is the Pancake number, giving lower bound of 19 flips in the stack of 17 elements.

The sequence is known as AA058986.

---
Tags: sorting, stacks
---


# Question
Title: Show that function is not turing-computable?
We have two functions:

$f\_1: \mathbb{N}\rightarrow \mathbb{N} \quad $ $f\_2: \mathbb{N}\rightarrow \mathbb{N}$

By definition $f\_1$ is turing-computable while $f\_2$ is not.

Then we define a third funtion $g(n) = f\_1(n) + f\_2(n)$.

I want to show that $g(n)$ is not turing-computable:

So first assume that $g(n)$ is computable.

That means I can write it like this:

$f\_2(n) = g(n)-f\_1(n)$

Which (is where I'm not sure) means that $f\_2$ can be computed which is a contradiction to the definition, which results that $f\_2$ is not turing-computable.

# Answer
This proof is correct as written, well done :) Remember this pattern, because an identical proof can be used in a wide variety of similar problems such as rational/irrational numbers and polynomials/non-polynomials
> 2 votes

---
Tags: computability, check-my-answer
---


# Question
Title: Modeling an inequality problem to a graph
Given $n$ variables : $a\_1,a\_2...,a\_n$ and $m$ inequalities of the form $a\_i\<a\_j$, we want to know if there's a positioning that satisfies all the inequalities.

> a. We want to modelize the problem to a directed graph $G=(V,E)$. $V=?,E=?$

$V=\\{a\_i|i\in\[n\]\\}$ $E=\\{a\_ia\_j|a\_i\<a\_j\\}$

> b. Complete the sentence: There exists a valid positioning iff...

$G=(V,E)$ doesn't contain directed cicles and parallel edges (i.e. to prevent $a\_1\<a\_2$ $a\_2\<a\_3\space$ $a\_3\<a\_1\space$ and $a\_1\<a\_2\space$ $a\_2\<a\_1$)

> c. How do we determine if there exists a valid positioning? What would be the complexity of such action?

I guess check for directed cycles (which i don't know how) and parallel edges?

> d. If there's a valid positioning, how do we find it?

By giving the vertex with maximum $d\_{out}$ the lowest number and so on?

I'd appreciate help with c and d.

# Answer
You’re on the right track with your response to $c$. There’s a bunch of algorithms that solve $c$ and $d$ simultaneously. If you’re familiar with depth-first search, you can use that to solve the problem.

Another approach is what’s called “topological sort.” The key idea here is that if a directed graph has no cycles, then you can put the vertices in a line such that there are only edges that go from start vertex to an end vertex such that the end vertex is to the right of the start vertex. This is actually really easy to write an algorithm to do, give it some thought and see if you can’t come up with a clever trick.

The best case time for solving this problem is $O(|V|+|E|)$, and off the top of my head I can think of four algorithms that achieve that timing.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: semaphore implementation with test and set
I'm trying to understand the algorithm for implementing semaphores on SMP system using test and set instruction described here: https://people.mpi-sws.org/~druschel/courses/os/lectures/proc4.pdf

(and a bunch of similar implementations on the web).

Locking semaphore looks like this:

```
void P(Semaphore s)
{
  Disable interrupts;
  while (ldl(s->lock) != 0 k !stc(s->lock, 1));
  if (s->count > 0) {
    s->count -= 1;
    s->lock = 0;
    Enable interrupts;
    return;
  }
  Add(s->q, current thread);
  s->lock = 0;
  sleep(); /* re-dispatch */
  Enable interrupts;
}

```

I have a number of questions about this. One is -- what is enabling and disabling of interrupts for? It seems that the whole reason we are using test and set is that interrupt disasbling is not feasible on SMP systems.
Then, what does the sleep() followed by enable interrupts mean? Does it mean that we do whole sleep with interrupts disabled? That can't be right as it defeats the purpose of sleeping. And if we first enable interrupts and then sleep, doesn't it mean that we have a possibility of missing a wakeup after lock is set to 0 but before we sleep?

# Answer
> 1 votes
The purpose of the spinlock is to prevent *other* cores from entering the critical section. The purpose of disabling interrupts is to prevent *this* core from re-entering the critical section.

The only way this core could try to re-acquire the semaphore is if an interrupt occurs and the interrupt handler needs the semaphore for some reason. Disabling interrupts prevents this from occurring.

As for the reason why `sleep()` is called after releasing the spinlock but before interrupts are enabled... well, that depends too much on the specifics of the operating system design to give a general answer.

The whole of the "waiting on the semaphore" operation should be atomic. That includes waiting on its queue *and* transitioning the thread from its "running" state to its "waiting" state. Presumably, that's what the call to `sleep()` is supposed to do.

You wonder if there's a possible race condition where this CPU releases the spinlock on the semaphore, then some other CPU signals the semaphore, then this cpu calls `sleep()`. That isn't necessarily a problem. If `sleep()` is written such that if it finds that the current thread is runnable it handles that case correctly, it won't cause a problem.

So why are interrupts disabled when you call `sleep()`? Some kernels are just designed that way, in that interrupts need to be disabled when you call into the scheduler. The call to `sleep()` may not actually "sleep"; it might just be whatever the scheduler has to do to make a thread sleep.

Alternatively, if there is a thread context switch hidden deep inside that call to `sleep()`, that may be where interrupts are re-enabled.

Ultimately, this code is designed to get the general idea across. How you would implement it in a real kernel would be like this, but this isn't necessarily drop-in code.

(Consider that load-linked/store-conditional instructions are spelled out in the example but there's no memory barrier operation on the spinlock release. That's a very specific ISA!)

---
Tags: concurrency, synchronization
---


# Question
Title: Is the balanced parentheses language inherently ambiguous?
I have this grammar:

$S\rightarrow SS |S \rightarrow(S)|S\rightarrow\epsilon $

Now this grammar generates the set of balanced parentheses. But this grammar is ambiguous. I am trying to find an unambiguous grammar for this language but all in vain. This has led me to believe that the language is inherently ambiguous. Am I true? If not please provide an unambiguous grammar for this language.

# Answer
> 4 votes
$$S \rightarrow (S)S$$ $$S \rightarrow \epsilon$$

Generalising this to other Dyck languages is left as an exercise.

---
Tags: formal-grammars
---


# Question
Title: Is the Choice operator implementable on $\pi$-calculus?
I was reading about $\pi$-calculus, and some authors include in the basic operations a Choice operator $P \oplus Q$ which means that either $P$ or $Q$ will be executed, but not both.

On page 8 of "Applied $\pi$ - an introduction" (available on http://www.cl.cam.ac.uk/~pes20/apppi.ps ), the author says that the coice operator is not necessary because it can be implemented as:

$$ P \oplus Q \triangleq \textbf{new} \ x \ \textbf{in} \ ( \bar{x}z.0 | xz.P | xz.Q ) $$

But it did not convince me. For example, taking $P=ab.0$ and $Q=cd.0$:

$$ \bar{a}y.0 | (ab.0 \oplus cd.0) \rightarrow 0 | 0 \rightarrow 0 $$

but

$$ \bar{a}y.0 |(\textbf{new} \ x \ \textbf{in} \ ( \bar{x}z.0 | xz.ab.0 | xz.cd.0 )) \rightarrow $$ may reduce to $$ \bar{a}y.0 |0|ab.0|(\textbf{new} \ x \ \textbf{in} \ xz.cd.0 ) \rightarrow 0 | (\textbf{new} \ x \ \textbf{in} \ xz.cd.0 ) $$ but it may also reduce to $$ \bar{a}y.0 |0|cd.0|(\textbf{new} \ x \ \textbf{in} \ xz.ab.0 ) $$

which will deadlock without ever sending $y$ through $a$. My question is: where are the mistakes? Is my reasoning wrong? Is this implementation of the choice operator wrong? Is the $\pi$-calculus required to backtrack and find the path with the most reductions?

I'm really sorry if my question makes no sense, I have very little formal training on this subject it is mostly curiosity so that I can implement a $\pi$-calculus simulator.

# Answer
The issue is that you are manipulating $\oplus$ but you don't have any rules (besides its definition) telling you what reductions you can do. The whole point of the paragraph that presents this definition is that there are multiple notions of choice and some but not all are encodable.

> Many process calculi have explicit choice or summation operators for nondeterminism, allowing for example $P+Q$ which can behave either as $P$ or as $Q$ (this is imprecise – in fact several different operators are possible). \[...\] In some cases a form of choice is encodable in a choice-free calculus – for example a purely internal choice can be encoded in the π-calculus given in Section 1.1 above by \[expression from question\] but in other cases non-encodability results can be proved \[...\].
> 1 votes

---
Tags: pi-calculus
---


# Question
Title: Best complexity to find solutions to $x^2+y^2=z^2$
What is the algorithm with the best complexity that finds solutions in a given range to the equation $x^2+y^2=z^2$ ?

The best i could do is to iterate through all $x$ and all $y$ and store $x^2+y^2$ in a hash and then iterate through all possible $z$ and check if $z^2$ is in the hash.

# Answer
I think you are asking about **Pythagorean Triples** (the form $x^2+y^2=z^2$ where $x$,$y$ and $z$ are integers).

**Euclids Formula** is generally thought to be efficient for finding primitive Pythagorean Triples.You can multiply these primitive triples with a constant to get non primitive Pythagorean Triples.

**Here** are some other methods of finding Pythagorean Triples
> 2 votes

---
Tags: algorithms, time-complexity, discrete-mathematics, searching
---


title: Counting Colorings of a Grid

text:
# Question
Title: Counting Colorings of a Grid
Given a $n \times m$ grid, define a *valid coloring* as mapping from the grid cells to a set of $k$ available colors such that no two adjacent cells have the same color. Cells are considered as adjacent if they share a side. **How many valid colorings are there?** Let $f(n, m, k)$ be the answer.

I search for a way to compute $f(n, m, k)$ fast, primarily in terms of time complexity. However, a polynomial-time solution is not required.

This problem was proposed in Codesprint 5 at HackerRank with constraints $1 \le n,m \le 8$ and $k \le 10^9$. However, I am not asking for this particular case, so it does not matter so much. It is worth mentioning there is a discussion on TopCoder, but I do not get it after several readings.

**Approaches.** I present my thoughts as following. First, we may explicitly enumerate all colorings. This works only on very small instances, because the number of colorings is growing exponentially. In order to see this, consider an $1 \times m$ grid and $k = 3$ colors. The first cell may be colored in $3$ ways and each following cell in $2$ ways, which yields $f(1, m, 3) = 3 \cdot 2^{m - 1}$.

Let's consider $n = 2$. If $m = 1$, we simply get $f(2, 1, 3) = 6$. Assume, we know $f(2, m, 3)$ for some $m \in \mathbb{N}$. Let $X$ and $Y$ be the colors in the rightmost / last column for an abritrary valid coloring of $2 \times m$ grid. In $(m + 1)^{th}$ column, there are $2$ colors for the top cell $(Y$ and the third color, say $Z$). Distinguish between two cases.

Case #1: Top cell has color $Y$. Then, our bottom cell can get color $X$ or color $Z$. There are two possible choices.

Case #2: Top cell has color $Z$. Then, our bottom cell must have color $X$.

Altogether, there are $3$ possibilities for the next step, i.e. $f(2, m + 1, 3) = 3 \cdot f(2, m, 3)$. Using our base case and solving the recurrence, the result comes out to be $f(2, m, 3) = 2 \cdot 3^m$.

These counting arguments get more complicated for larger values of $n$, even for $n = 3$ I do not find an explicit formula. In the original problem, there are significantly more colors than cells. It should be sufficient to consider colorings with exactly $1, 2, \dots, mn$ colors (let $a\_{i}$ be the respective answers) and compute $\displaystyle \sum\_{i = 1}^{mn} \binom{k}{i} a\_{i}$. Therefore, don't worry too much about this step.

Hints and approaches are appreciated as well as solutions and references.

# Answer
> 2 votes
For every graph $G$ on $n$ vertices there is a degree $n$ polynomial $\chi\_G$ such that $\chi\_G(k)$ is the number of valid $k$-colorings of the graph. This polynomial is known as the chromatic polynomial, and can be found in exponential time. The easiest solution to the programming challenge is to precompute the chromatic polynomials. For example, denoting the $n \times m$ grid by $G(n,m)$, we have $$ \begin{align\*} \chi\_{G(1,1)} &= x \\ \chi\_{G(1,2)} &= x^2 - x \\ \chi\_{G(2,2)} &= x^4 - 4x^3 + 6x^2 - 3x \\ \chi\_{G(1,3)} &= x^3 - 2x^2 + x \\ \chi\_{G(2,3)} &= x^6 - 7x^5 + 21x^4 - 33x^3 + 27x^2 - 9x \\ \chi\_{G(3,3)} &= x^9 - 12x^8 + 66x^7 - 216x^6 + 459x^5 - 648x^4 + 594x^3 - 323x^2 + 79x \end{align\*} $$

---
Tags: algorithms, combinatorics, enumeration
---


title: Call by value-return with void function

text:
# Question
Title: Call by value-return with void function
If I'm passing parameters as call by value-return and call a void function, will the local values within the function still be copied to the corresponding values in the caller function even though the called function doesn't return? For example:

```
int x = 4;

void foo(int a) {
    a = 8 + 8;
}

int main() {
    foo(x);
    print x;
}

```

Will the value printed be 4 or 16? My hunch is that because foo never returns, the local value for a within the stack frame of foo never gets copied back to the value for x in the stack frame for main, but I wanted to double check.

# Answer
> 0 votes
It will print 4 because sending by value will change the copy not the original variable which is x in your example.

---
Tags: evaluation-strategies
---


# Question
Title: Exact Value of Denormalised number related to floating point numbers
I faced with the following issue: if the value of a floating point format number is in the range of underflow, it must be 0 or a **denormal number**.If the value is not 0 than what is the exact value of it?Is it conventional constant value or depend on different architectures? I am sorry but could not understand through wiki's article

# Answer
> 1 votes
Some -- not all but the most common one are -- binary floating point representations are using a trick to get one more bit of precision. First, let's define the *normal representation* for non-null floating point values as the representation where the exponent is chosen so that the most significant bit of the value is the most significant bit of the value is the most significant bit of the significand (also known as mantissa). The trick is to notice that when the normal representation is used, the most significant bit of the significand is always set for non null values, and thus those format mandate the representation to be normalized so that they can avoid to represent it in the format.

This has two undesirable characteristics.

* Some values which would have been representable if normalization was not mandated are now no more representable as normalization would implies a non representable exponent.
* The difference between 0 and the first representable value is bigger than the difference between the next representable value and the first.

Some formats (again not all but the most common one are) are trying to avoid those properties by allowing non-normalized values if normalization is not possible. Those are called denormal or subnormal.

So when a computation result in a number which is smaller (in absolute value) to the smallest normal representation -- also known as underflow --, the main choices are:

* use as result a denormal if the representation allow it and the number is not smaller than the smallest denormal
* use zero as result

Note that some other possibilities exist:

* use as result a NaN marking the result as underflow
* generate an exception or an interrupt of some sort
* set a sticky bit somewhere meaning that an underflow has been met in addition to returning one value of some kind.

Underflow are usually considered as too common for those other possibilities, excepted the last one, to be considered as useful for most code.

---
Tags: floating-point
---


# Question
Title: Show that Knapsack-like problem on directed graph is NP-hard
Let $G=(V,A)$ represent a directed acyclic graph, where a value $v\_i \ge 0$ is assigned to every vertex $u\_i$. Let $T$ represent a threshold and $N = |V|$. Problem statement:

maximize: $\sum\_{i=1}^{N}v\_i x\_i$

subject to: $\sum\_{i=1}^{N} x\_i \leq T$ and $x\_i \in \lbrace 0,1 \rbrace$

and $x\_i(x\_j-1) = 0 \quad \forall a\in A: u\_i \to u\_j$

In other words, we want to choose up to $T$ vertices that maximize the sum of their values, with the restriction that if a vertex $u\_i$ is chosen, any reachable vertices $u\_j$ must also be chosen. Therefore, $x\_i(x\_j-1) = 0$ for a given arc $u\_i \to u\_j$ represents that if $u\_i$ is chosen ($x\_i = 1$) then $u\_j$ must be chosen as well ($x\_j = 1$).

I want to prove that this is a **NP-hard** problem. To do that, I have taken the 0-1 knapsack problem, which is NP-hard:

maximize: $\sum\_{i=1}^{M}v\_i x\_i$

subject to: $\sum\_{i=1}^{M} w\_i x\_i \leq T$ and $x\_i \in \lbrace 0,1 \rbrace$

The 0-1 knapsack may be reduced to an *instance* of the original problem. Assume an instance of the original problem, with the following properties of $G$:

* $v\_i = 0$ for every vertex $u\_i$ with incoming arcs.
* All vertices have at most 1 incoming arc.

The 0-1 knapsack may be reduced to this instance by the following polynomial transformation:

* There are $M$ items, where $M$ is the number of vertices $u\_i \in G: v\_i \> 0$.
* The value $v\_i$ of each item the value $v\_i$ of vertex $u\_i$.
* The weight $w\_i$ of each item is $1+$ the number of reachable vertices from $u\_i$.

Explanation:

* Since vertices with a non-zero value have no incoming arcs, they may be chosen independently, as there is no possibility for such a vertice to be chosen twice, as a "dependency" of another one. Thus, individual items in the knapsack problem may be mapped to these vertices.
* As no vertice has more than 1 incoming arc, no vertice may be reached by multiple vertices. This guarantees that the weights of each knapsack item are independent of each other.

**Questions**

1. Have I formulated the original problem correctly, using the mathematical notations? It's been quite some time since I have formally formulated a graph theory problem.
2. Is this reduction enough to prove that the original problem is NP-hard? I only have reduced the 0-1 knapsack only to an **instance** of the original problem, not the original problem itself. Does this imply that the original problem is "at least as hard, if not harder" than the 0-1 knapsack?
3. Assuming that question (2) stands, is my reduction correct?
4. Alternatively, could I demonstrate my case via another reduction?

# Answer
$x\_i \leq x\_j \forall (i,j) \in A$ is a linear constraint that represents your requirement (if $x\_i=1$ it would push $x\_j$ to take value $1$ as well). You get a constrained knapsack problem. You can easily reduce a knapsack to it by considering a graph that simply has no arrows.
> -1 votes

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


# Question
Title: What is the type system (or class of type systems) that that ensures all your tree Branches end in Leaves?
I've come across this situation numerous times in the past few years where I have some classes like (pseudo-Java):

```
interface Node<T> { ... }

final class BranchNode<T> implements Node<T> {
    List<Node<T>> children;
}

final class LeafNode<T> implements Node<T> {
    List<T> elements;
}

```

If you know the height of a balanced tree in advance, you can make classes for each height of node instead of a single BranchNode class. I think Daniel Spiewak did this in his Scala PersistentVector implementation:

```
final class Height2Node<T> implements Node<T> {
    List<Height1Node<T>> children;
}
final class Height1Node<T> implements Node<T> {
    List<LeafNode<T>> children;
}

```

But if you don't know the height of the tree or need to support an arbitrary height, or only care whether a node is a Branch or a Leaf, is there a type system that can ensure that all your Branches end in Leaves?

I mean, you could walk the tree and use `instanceof` to find some leaf nodes and calculate the height of a given node from that and write code to ensure a balanced tree. But I'm wondering if a type system exists that can model this in such a way that it allows building a valid tree and prevents building an invalid one? If so, what is that type system, or class of type systems that can help solve this problem?

I've heard the words, "dependent types" and "higher kinded types" before. I could maybe even recognize simple examples of one or the other, but would have trouble explaining what they mean. So go easy on me, or provide links. Thanks in advance!

# Answer
> 1 votes
To be honest, I'm unsure about whether this is a CS question or a programming question. There is a strong programming part to it, yet encoding requirements in types requires reasoning on types which is more on the CS side. Anyway, here is an answer.

---

There are several options to encode that requirement into types.

Basically, we need to encode that each `BranchNode` has at least one child. This means that a leaf can only be a `LeafNode`.

A naive approach would be

```
final class BranchNode<T> implements Node<T> {
    Node<T> firstChild;
    List<Node<T>> otherChildren;
}

```

We can even keep only a (private) children list, and enforce that using a constructor.

```
// Make these private
private Node<T> firstChild;
private List<Node<T>> otherChildren;

// Make this to be the only public constructor of the class
BranchNode(Node<T> firstChild, List<Node<T>> otherChildren) {
    children = otherChildren.clone();
    children.add(firstChild);
}

```

Note the usual caveats, though. One can break this invariant using `null`s, non termination, or by creating circular references, e.g. a `BranchNode` which is its own child (this is easy to achieve if the tree is mutable, for instance). Unwanted subclasses also can break the invariant.

---

Another option is to exploit the usual Church encoding of algebraic data types into polymorphic types. In theory, this is related to initial algebras and catamorphisms. In OOP practice, this is known as the "visitor pattern".

I'll pretend leaves contain a single `int`. One can generalize this using generics, as usual.

```
interface Visitor<R> {
   R visitNode(int data);
   R visitBranch(R firstChild, List<R> otherChildren);
}

interface Node {
   <R> R visit(Visitor<R> v);
}

```

Pseudo code follows, since Java is too heavy for writing this in a readable way, and I'm not completely familiar with its functional libraries.

```
class LeafNode implements Node {
  int data;
  visit(v) = v.visitNode(data);
}

class BranchNode implements Node {
  Node firstChild;
  List<Node> otherChildren;
  visit(v) = v.visitNode(firstChild.visit(v),
                         otherChildren.map(_.visit(v)));
}

```

The advantage of this approach is that the invariant can not really be broken by adding subclasses. One can create a new `Leaf2Node` subclass, but if that has the same `visit(v)`, it will behave as `LeafNode`. The implementation of `visit(v)` in general will be limited by types, and running `visit(v)` will always (if terminating) end with calling `v.visitNode(data)` when a leaf is encountered.

---
Tags: programming-languages, trees, type-theory, type-checking, types
---


# Question
Title: Enumerate probabilistic and other kinds of Turing machines together
When we talk about the enumeration of TM's, do we mean the "regular" deterministic ones? So if we want to enumerate nondeterministic or probabilistic TM's, do we need a separate enumeration?

I can see how we could describe probabilistic TM's as strings, just as we describe the deterministic TM's only now we have two transition functions. Then it also follows that checking whether some string enumerates a probabilistic TM is decidable. Perhaps one could think of a way to create some universal coding of TM's to strings that works for all different kinds of TM's? Perhaps the first ... digits of the enumeration describe what kind of TM (probabilistic, determinstic etc) it is and then follows the description of the TM in the standard fashion. So then we can enumerate all the TM's?

A related question, does a TM know it's own description? Or can we give it that information without loss of generality?

# Answer
> When we talk about the enumeration of TM's, do we mean the "regular" deterministic ones?

We mean an enumeration of whatever kind of Turing machines we're talking about at the moment. Unless stated otherwise, "Turing machine" is normally taken to mean deterministic Turing machine.

> Perhaps one could think of a way to create some universal coding of TM's to strings that works for all different kinds of TM's?

There's no fixed list of "all different kinds of TM's", so I don't see how this would be possible.

> A related question, does a TM know it's own description?

It's not clear to me what it means for a TM to "know" anything. A Turing machine is just its state set, transition function and so on.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: LL1 parsing algorithm for strings generated by a given grammar
> How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar?

I have to design a parser for a specific grammar. Let $G$ be the grammar described as:

$$S \rightarrow aBC $$ $$B \rightarrow bB \mid cC $$ $$C \rightarrow c \mid S $$

### My approach

**1. Test if the grammar is $\operatorname{LL(1)}$**

First I have to determine if the grammar is $\operatorname{LL(1)}$ or not. It seems that G is $\operatorname{LL(1)}$ because:

$\operatorname{FIRST}(aBC) \cap \operatorname{FIRST}(bB \mid cC) \cap \operatorname{FIRST}(c \mid S) = \\{a\\} \cap \\{b,c\\} \cap \\{c,a\\} = \emptyset $

**2. Write a string generated by G**

$s = abccaccc$

**3. Design the algorithm for parsing strings**

*I'm getting stuck here*

**4. Test the algorithm for a given string**

Lets test the algorithm for a given string $s = abccaccc$

# Answer
> 0 votes
Here's a possibly useful quote from Aho, Lam et al ("the Dragon Book"). (Emphasis added.)

> A grammar $G$ is $LL(1)$ if and only if **whenever $a \to \alpha | \beta$ are two distinct productions of $G$**, the following conditions hold:
>
> 1. For no terminal $a$ do both $\alpha$ and $\beta$ derive strings beginning with $a$.

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


# Question
Title: Algorithm for computing partitions of a set of n elements into subsets of size m
I need an algorithm that can compute all the different partitions of a set of n elements into subsets of size m.

For example for $n=4$ for the set $\\{a,b,c,d\\}$ and $m=2$ the output should be

$\\{\\{\\{a,b\\},\\{c,d\\}\\},\\{\\{a,c\\},\\{b,d\\}\\},\\{\\{b,c\\},\\{a,d\\}\\}\\}$

# Answer
Two possible possible solutions.

Given a set $S$ of size $n$ and a positive integer $m \< n$. First generate all $m$-size subsets of $S$, for example, in lexicographic order and store them. Let $C$ be the set of all $m$-size subsets of $S$. The size of $C$ is $\binom{n}{m}$. The following algorithm generates all partitions

```
Generate(S, Partition)
  if S is empty
    print Partition
    return

  for each T in C such as T is a subset of S
    add T to Partition
    Generate(S-T, Partition)
    remove T from Partition
end

```

This algorithm repeats partitions but you can check if a Partition repeats. If it does then do not print it. One possible solution is checking its lexicographic order.

The second approach, which I think is simpler, is to systematically generate all $(n/m)$-size subsets of $C$. If for some $(n/m)$-size subset $T$ all sets in $T$ are mutually exclusive, then $T$ is a partition and so print it.

**Example**: $S=\\{a,b,c,d\\}$ and so $C = \\{\\{a,b\\},\\{a,c\\}, \\{a,d\\}, \\{b,c\\}, \\{b,d\\}, \\{c,d\\}\\}$. Then using the second approach we systematically generate all $4/2=2$-size subsets of $C$. Thus while generating if we have $\\{\\{a,b\\},\\{a,d\\}\\}$ then we just skip it since it's not a partition. But if we have $\\{\\{a,b\\},\\{c,d\\}\\}$ then we print it since it is a partition. Furthermore, there is no chance of generating duplicate of a subset of $C$ since we generate all (distinct!) combinations of $4/2=2$ elements from $\binom{4}{2}=6$.

For generating combinations of $k$ elements from $n$ you could look, for example, here.
> 2 votes

---
Tags: algorithms, enumeration, partitions
---


title: How to adapt DPLL to solve HORNSAT?

text:
# Question
Title: How to adapt DPLL to solve HORNSAT?
*This question wask asked in a homework of Computer Theory in Rome, Italy.*

> How to simplify the DPLL algorithm in order to solve HORNSAT?

**My Approach:**

I know that an *Horn clause* is an OR of literals where it contains at most one pure literal and any number of negative literals.

I would start with the following algorithm:

FUNCTION $Dpll(S)$:

1. *IF* $S = \emptyset $ **RET SAT**
2. *WHILE* $\exists$ one unit clause $(p)$ or $\exists$ one literal $p$ that appears pure in $S$
3. *IF* ( $p \in S \wedge \neg p \in S) $ **RET UNSAT**
4. *ELSE* $S = Unit-propagate(S,p)$
5. *ENDIF* *ENDWHILE*
6. IF $S = \emptyset $ **RET SAT**
7. choose one literal $p$ in one clause in $S$
8. *IF* $(DPLL(Unit-propagate(S,p) == SAT)$ **RET SAT**
9. *ELSE* **RET** $DPLL(Unit-propagate(S,\neg p)$

FUNCTION $Unit-propagate(S,p)$

10. Delete every clause in $s$ that contains $p$
11. Delete every occurence of $\neg p$
12. **RET** $S$

# Answer
Horn formulas are always satisfiable unless there is at least one unit clause that contains a positive literal. (Otherwise assigning false to all the variables guarantees the formula would be satisfied.) The procedure in that case is to unit propagate all unit clauses that contain a positive literal and unit propagate any such new clauses as they occur. Once this task is completed, if the remaining formula contains no empty clauses then the Horn formula is satisfiable.
> 2 votes

---
Tags: algorithms, satisfiability, propositional-logic
---


# Question
Title: I have n boys and n girls. I need to pair as much of them as possible for a dance in O(nlogn). Reduce this to a standard problem?
There are n girls and n boys. Each girl i has an objective attractiveness constant Pi (a natural number). The bigger the number, the more attractive. Each boy has a range in which he is comfortable asking the girl out \[Ai, Bi\] (inclusive). A boy will not ask someone out who is below Ai or above Bi.

I need to pair as many of them as I can for a single dance in O(n\*logn) time.

I tried building some kind of a tree in O(n) and then using that three in O(logn) repeatedly against the whole list. I've spent some solid 3 hours on this problem and I'm really not getting anywhere. I've tried to build a dependency tree, I've treed weighted priority queues. I considered some constraint satisfaction algorithms, but as far as I recall they are all nowhere near O(n\*logn).

Nothing seems to work. But I do clearly see that this has to be reduced to some other standard computer science problem.

However I've had no luck looking up "load balancing" or "pair assignment". I've no idea what are the right keywords.

This seems the be the kind of problem data centers have when assigning load to virtual machines. Or web requests over the world for large web sites. For example a server can sustain a load in \[Ai, Bi\] range (let's say RAM in GB's 4-8GB) and our target application needs 5GB. Now let's say we have n of both of these (target applications and servers). How to pair them so as much get paired? Thanks.

# Answer
Algorithm: Pick girl #i where $P\_i$ is as high as possible. Eligible boys are those with $A\_j ≥ P\_i ≥ B\_j$. If there is no eligible boy then she is not matched, otherwise match her with eligible boy #j, where $B\_j$ is as large as possible. Then match the remaining boys and girls in an optimal way.

If instead you match her with boy #k or with nobody, then you can just swap boy #j and boy #k, and you get a result either as good as promised.
> 1 votes

---
Tags: algorithms, optimization, bipartite-matching, constraint-satisfaction
---


title: Converting CFG to CNF

text:
# Question
Title: Converting CFG to CNF
need some help with the following question:

I've watched a few youtube tutorials but I'm struggling to convert this specific CFG

# Answer
> 0 votes
What you want is to have each production be of one of the forms $A \rightarrow BC$, $A \rightarrow x$ (for a terminal $x$), and $S \rightarrow \epsilon$ (where $S$ is the start symbol). The only productions in that grammar which are not of one of these forms are:

* $\text{S} \rightarrow I \text{ VP PP}$
* $\text{VP} \rightarrow ate \text{ NP}$
* $\text{VP} \rightarrow \text{V}$

**Hints**: try replacing the second production with an equivalent one of the form $A \rightarrow BC$, and try replacing the third production with one of the form $A \rightarrow x$. For the first one, I suggest creating a non-terminal $\text{X}$ such that $\text{X} \rightarrow I \text{ VP}$, and then rewriting the production as $\text{S} \rightarrow \text{X} \text{ VP}$. This production is in the correct form, but now the one for $\text{X}$ isn't; however, it isn't too much work to fix that one as well.

---
Tags: formal-languages, natural-language-processing
---


title: Determining Ambiguity of grammar

text:
# Question
Title: Determining Ambiguity of grammar
I read that no LL(1) grammar can be ambiguous.

Can we just make a LL(1) predictive parser table for a grammar to determine whether it's ambiguous? If the grammar is not LL(1), can we say that grammar is ambiguous?

# Answer
> If the grammar is not LL(1), can we say that grammar is ambiguous?

Euh, no. A grammar is unambiguous if for every word in its language there exists exactly one derivation-tree for it in the grammar.

Parsing is a way to find that derivation, given the string, preferably in some efficient way. Several classes of grammars were defined that have efficient parsing methods, for example LL(1) grammars.

A grammar can be non-LL(1), and still be unambiguous. For instance when we reverse an LL(1) grammar (that is, take the mirror image of the RHS of every production) the result still is unambiguous: mirroring the original unique derivation trees. But it cannot be parsed in an LL fashion, rather its reverse...
> 2 votes

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


# Question
Title: What is the transitive and reflective closure of the derivation relationship?
*This question is asked during a class of Computer Science.*

> What is the transitive and reflective closure of the derivation relationship?

I know that if $R$ is a relationship on $A^2$, a transitivive and reflective relation on $R$ is the following $R^\*$

$$R^\* = R^+ \cup \\{\<x,x\> \mid x \in A\\}$$

but I don't now how to apply it to the concept of derivation

# Answer
If $R\subseteq A\times A$ is a binary relation, it can be imagined as a directed graph: the elements in $R$ are the edges. The graph however might be infinite. The elements in $R^\*$ represent (finite) paths, following zero, one or more of the consecutive edges. Zero edges because of reflexivity, two or more because of transitivity.

In case of a grammatical derivations the relation $\Rightarrow$ considered is a binary relation in $\Sigma^\*\times\Sigma^\*$ for some alphabet $\Sigma$, defining a single step as defined by the grammar. Then $\Rightarrow^\*$ consists of all pairs of strings the first one of which can be rewritten into the second, using zero, one or more steps.

In other words, $x \Rightarrow^\* y$ iff there exist steps $x= w\_0 \Rightarrow w\_1 \Rightarrow \dots \Rightarrow w\_n=y$.
Again, this includes the case of zero steps $x= w\_0 = w\_n=y$.

This notation can then be used to define the *language* of the grammar. Usually \[but not always\] this looks like $L(G) = \\{ x\in\Delta^\* \mid S \Rightarrow^\* x \\}$; the set consisting of all terminal words ($x\in\Delta^\*$) that can be derived from the axiom ($S \Rightarrow^\* x$).
> 2 votes

---
Tags: formal-languages, logic
---


# Question
Title: Undecidability: writing a symbol on Turing Machine's tape
I wonder to know if given a Machine $M$, a string $x$ and a symbol $\phi$, would $M$ ever write $\phi$ ?

**My approach**

Maybe i can show if the problem is undecidable by contradiction using $M$ to prove $\operatorname{HALTING PROBLEM}$, but i'm stuck here. Any hints ?

# Answer
> 2 votes
First take a Arbitrary Turing Machine M and modify it so that on stopping state it will first write a new symbol $\phi$ that it won't write at any other time.

If you can decide that Machine M' will write that symbol then you can decide whether machine M halted.

# Answer
> 1 votes
HINT: Modify $M$ so it writes $\phi$ if and only if it halts.

> Choose $\phi$ so it's not in the original $M$'s alphabet.

---
Tags: turing-machines, reductions, undecidability
---


# Question
Title: How to select a binary tree node uniformly at random
The exercise I'm trying to solve is

> You are implementing a binary search tree class from scratch, which, in addition, to insert, find and delete, has a method `getRandomNode()` which returns a random node from the tree. All nodes should be equally likely to be chosen. Design and implement an algorithm for `getRandomNode()`, and explain how you would implement the rest of the methods.

The answer from the book is:

```
 1  class TreeNode {
 2    private int data;
 3    public TreeNode left;
 4    public TreeNode right;
 5    private int size = 0;
 ...
12    public TreeNode getRandomNode() {
13      int leftSize = left == null ? 0 : left.size();
14      Random random = new Random();
15      int index = random.nextInt(size);
16      if (index < leftSize) {
17        return left.getRandomNode();
18      } else if (index == leftSize) {
19        return this;
20      } else {
21        return right.getRandomNode();
22      }
23    }
...
55  }

```

But here is the problem. With this algorithm, I don't see how nodes are equally likely to be chosen. In line 16, it says if `leftsize > index,` where `index` is a number from 0 to `size`, then the algorithm will continue with the left node, otherwise the right node. It only works when the tree has a depth of 2. When the tree is taller, the probability of each node being chosen will not be equal.

Am I wrong? Does this algorithm work?

# Answer
> 7 votes
The algorithm works just fine.

Note that each node's `size` field tells you the total number of nodes in the subtree rooted at that node. Throughout this answer, I'm just going to assume that a child's `size` is zero if the child is `null`. Thus, for any node in the tree, we have

```
this.size == left.size + 1 + right.size

```

Consider the root of the tree. If we choose a node of the tree uniformly at random, then it should be in the left subtree with probability `left.size/size`, it should be the root node with probability `1/size` and it should be in the right subtree with probability `right.size/size`. By the equation above, these three probabilities add up to 1. If you look at lines 15–22, the algorithm implements exactly this probability distribution. It generates a uniform random integer in the range `0 .. size-1`. If this number is in the range `0 .. left.size-1`, the algorithm picks a random node from the left subtree; if it's equal to `left.size`, it picks the root and, otherwise, it picks a random node from the right subtree.

And the argument I gave doesn't depend on the node you consider being the root, so the recursive calls behave as they should. The algorithm doesn't care about the depth of the nodes: it just recurses down the subtree and chooses subtrees with the correct probability.

# Answer
> 1 votes
I want to show that this algorithm indeed randomly chooses a node according to the uniform distribution.

Consider the root node. We have two subtrees: the left subtree with the size $s\_l$ and the right subtree with the size $s\_r$. The total number of nodes in the tree is $size = 1 + s\_r + s\_l$. Now, I want to prove that distribution is uniform, i.e. for any node $e$, $P(e)=\frac{1}{size}$ (probability that the algorithm chooses $e$).

There are three possibilities, either $e$ is the root, or $e$ is in the left subtree, or $e$ is the right subtree.

If $e$ is the root node, then `index = random.nextInt(size)`uniformly selects an integer between $0$ and $size-1$, and the statement `if (index == leftSize)` is true with the probability $\frac{1}{size}$.

If the node $e$ is in the left subtree then the probability that the statement `if (index < leftSize)` is true, $P(InLeft)$, is equal to $\frac{s\_l}{size}$ and the conditional probability that the node $e$ is chosen given it is in the left subtree is $P(e \mid InLeft)=\frac{1}{s\_l}$. Thus the probability \[$e$ is in the left subtree\] AND \[$e$ is chosen\] is equal to $$P(InLeft \cap e \text{ is chosen }) = P(InLeft)P(e \mid InLeft) = \frac{s\_l}{size}\frac{1}{s\_l} = \frac{1}{size}$$

If the node $e$ is in the right subtree then using the same argument as in the previous case we have $P(InRight)P(e\mid InRight) = \frac{s\_r}{size}\frac{1}{s\_r} = \frac{1}{size}$.

Thus the distribution is uniform.

# Answer
> 1 votes
Consider an arbitrary node $n\_k$ which is reached from the root $n\_0$ along path $(n\_0, n\_1, \dots, n\_k)$. We will explicitly compute the probability of $n\_k$ being chosen.

Observe that when visiting $n\_{i-1}$ with $i\>0$, that node itself is selected with probability

$\qquad\displaystyle \frac{1}{\operatorname{size}(n\_i)}$, and

child $n\_i$ is recursed to with probability

$\qquad\displaystyle \frac{\operatorname{size}(n\_i)}{\operatorname{size}(n\_{i-1})}$.

Hence, because all the choices are stochastically independent, the probability to select $n\_k$ is

$\qquad\displaystyle \frac{\operatorname{size}(n\_1)}{\operatorname{size}(n\_0)} \cdot \frac{\operatorname{size}(n\_2)}{\operatorname{size}(n\_1)} \cdot \dots \cdot \frac{\operatorname{size}(n\_k)}{\operatorname{size}(n\_{k-1})} \cdot \frac{1}{\operatorname{size}(n\_k)} \quad=\quad \frac{1}{\operatorname{size}(n\_0)}$,

what was to show.

Fill in the details for a formal proof.

---
Tags: algorithms, trees, correctness-proof, randomness, sampling
---


# Question
Title: Shortest path in NL algorithm, need help to understand
https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/sol8.pdf

I'm checking those solution and i'm having trouble understanding the proof that shortest path belong to NL (2.a).

So being Shortest path = {(G=(V,E), k, s, t) | shortest path from s to t in G has length k} and rk-1 being the number of vertices reachable in k-1 steps, the proposed algorithm is

```
d ← 0
flag ← FALSE
for all w ∈ V do
    p ← s
    for i ← 1 to k − 1 do
        non-deterministically pick a neighbor q of p
    if p = w then
        d ← d + 1
    if w = t reject
    if w is a neighbor of t then
    flag ← TRUE
if d < rk−1 reject
if flag then accept else reject

```

In a line it does "non-deterministically pick a neighbor q of p" but q it's never used. Where and how it's q used?

# Answer
What is probably meant is that the chosen vertex is substituted back into $p$. This way when the for loop is done, $p$ contains some vertex of distance at most $k-1$ from $s$. Note that comparing the counter $d$ to $r\_{k-1}$ makes sure that you went over all the vertices of distance at most $k-1$ from $s$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How to create an algorithm when given the invariant
I am given the following invariant:

`Invariant` The greatest $i$ keys of an Array are always in sorted order on the last $i$ indices of the Array.

I am supposed to create a sorting Algortihm using this invariant. But I seem to have understood the concept of an Invariant differently, because with the information I find online, I can't find an idea for starting this problem. Do I have to create an algorithm that sorts the first $n-1$ elements in the array? Thanks for your help

# Answer
> 1 votes
Observations:

1. For $i=0$, you don't know anything about the array.
2. For $i=n$, the array is sorted.

So the idea is to go from $i=0$ to $n$ while maintaining the invariant. This is similar to an inductive proof; in fact, you'll get an inductive algorithm.

* Start with the input array and $i=0$; clearly, the invariant is maintained.
* For some $i \geq 0$, assume that the invariant holds. What do you do to ensure the invariant holds for $i+1$?

I'll let you take it from here.

---
Tags: algorithms, algorithm-design, loop-invariants
---


# Question
Title: Does space complexity analysis usually include output space?
Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this out just by reading examples.

If a function returns a new list, should the space complexity analysis of the function include the space required for the output? There seem to be clear reasons to want to exclude the input from the analysis, but it's less clear if the output should be excluded. Does the architecture of the system matter (e.g. multi-tape turing machine vs modern RAM-based computer)?

Consider the example functions below. They all use O(1) auxiliary space but different output space (relative to the input space), so the overall space complexity changes based on whether or not you include the output space.

**generate a new list from a single int input:**

```
int[] random1(int count) {
    Random rand = new Random();
    int[] output = new int[count];
    for (int i = 0; i < count; i++) {
        output[i] = rand.Next();
    }
    return output;
}

```

Output space: O(2^n)

**generate a new list from a list input:**

```
int[] random2(int[] input) {
    Random rand = new Random();
    int[] output = new int[input.Length];
    for (int i = 0; i < input.Length; i++) {
        output[i] = input[i] + rand.Next();
    }
    return output;
}

```

Size of output: O(n)

**modify the input list in place**

```
int[] random3(int[] input) {
    Random rand = new Random();
    for (int i = 0; i < input.Length; i++) {
        input[i] = input[i] + rand.Next();
    }
    return input;
}

```

Size of output: O(1)

# Answer
> 25 votes
Typically, we consider space complexity in terms of Turing machines with:

* one read-only input tape
* one write-only output tape
* however many read-write working tapes you want.

The space usage is the number of cells used on the working tapes, so input and output space typically *aren't* counted. (See, e.g., Section 2.5 of Papadimitriou.)

Obviously, we don't want to count input space since, then, every algorithm would have to use linear space. Likewise, we don't want to count output space as that stops us from distinguishing between problems that are hard simply because the output is big (e.g., given an integer $n$, write the list $1, 2, \dots, n$) and problems that are hard because even computing a single output is hard (e.g., output a list of all $3$-colourings of the input graph).

On the other hand, not all authors do this. Sipser defines space usage as just the number of tape cells read by an ordinary Turing machine (Section 8) and the says, more or less, "Oops but that doesn't let us consider any kind of sublinear space, so we'd better redefine it not to include the input" (Section 8.4; he's only considering decision problems, so there's no output to worry about).

I'm not a fan of the redefinition approach but, either way, we need to exclude the input and output if we want to talk about any kind of sublinear space bound.

**References**
C.H. Papadimitriou, *Computational Complexity*. Addison–Wesley, 1992.
M. Sipser, *Introduction to the Theory of Computation* (3rd edition). Cengage Learning, 2013.

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


# Question
Title: What kind of languages can be recognized by a restricted one-tape deterministic Turing Machine?
During a lesson, our TA asked:

> What kind of languages can be recognized by a *deterministic* Turing Machine such that we can use only a tape *portion* that contains the input?

**My thoughts:** my Theory of Computation book says that there is a special TM called *linear bounded automaton* (LBA) that corresponds to a *non-deterministic* Turing Machine that has a limited tape. Such machine recognize Context Sensitive languages.

So if i simulate the LBA behavior starting from a *deterministc* TM, may I recognize "deterministic"-Context Sensitive Languages?

# Answer
> 2 votes
It's famously unknown whether deterministic and non-deterministic LBA accept the same set of languages.

---
Tags: formal-languages, automata, context-sensitive, linear-bounded-automata
---


title: Number of words in $L$ of length $n$?

text:
# Question
Title: Number of words in $L$ of length $n$?
Be $L$ a formal language over the alphabet $\Sigma$. $L$ can be defined by induction:
$L^0 = \\{\epsilon\\}$ and for $i\>0: L^i = \Sigma\*L^{i-1}$.
Means that $|L^n|$ is the number of words in $L$ of length $n \in \mathbb{N}$ letters from $\Sigma$.
Find $|L^n|$.

For $\Sigma = \\{a,b\\}$, $|L^n| = 2^n$ scince $|\Sigma| = 2$ and $|K\*\Sigma| = |K|\*2$ (with $K$ being an arbitrary set). Right?
But what happens if $\Sigma = \\{a,b,aa,ab,ba,bb\\}$ ?
For some $n$ some elements can be created in multiple ways (e.g. $a$ and $ba$ result in $aba$ and $ab$ and $a$ result in $aba$). Therefore $|L^n| \neq 6^n$.
The problem clearly is, that some letters of $\Sigma$ (e.g. $aa$) consist of other letters of $\Sigma$ (e.g. $a$).
So far i looked at some results (no guaranty for correctness):

$|L^1| = 6$
$|L^2| = 28$
$|L^3| = 120$
$|L^4| = 496$
$|L^5| = 2016$
$|L^6| = 8128$

And found a formula for these values: $|L^n| = 2^n\*(2^{n+1}-1)$
However, i can't explain or prove it. What is the correct way to approach this? Which words can be created in multiple ways?

# Answer
> Means that $|L^n|$ is the number of words in $L$ of length $n\in \mathbb{N}$ letters from $\Sigma$.

Actually, $L^n$ consists of the words that are composed of $n$ *copies* of words from $L$. The precise lengths of these words differ.

This exercise starts however with a very specific set $L$, it consists of *all* words of length 1 or 2. That means that $L^2$ consists of all words of length 2,3 or 4. (No need to verify in how many ways that can be done.) And this are 4+8+16 = 28 strings, exactly like you claimed.

This can be generalized for $L^n$.
> 3 votes

---
Tags: formal-languages, proof-assistants
---


# Question
Title: Show that kleene plus language is a regular language by describing how you build a DFA or NFA for it
> L ⊆ ∑\* is a regular language. Show that L^+ (aka kleene plus) is a regular language by describing how you can build a DFA or NFA for the language.

I would build a NFA. That NFA must have exactly one starting state and one end state, where the starting state is never the end state.

The amount of characters of the given language equals the amount of states of the NFA +1.

Every state except for the end state has an (outgoing) arrow to the next state where every single character of the language occurs exactly once (ordered aka one after the other).

If the language is made up of just one character, do: The end state has an outgoing arrow to itself with that one character of the language.

Else do: The end state has an outgoing arrow to the second state (I mean that state where the starting state points at) with the first character of the language.

Here is an example:

Given is language (aba)^+ where ^+ means exponent +

The NFA for this language would look like this ("Beispiel" means example):

Do you agree with my idea and do you have any improvements?

For the case the language is made up of several pairs, for example (aba, ab, bb)^+ I would just do the entire procedure for every single. In the end you will have a NFA for language (aba)^+ another NFA for (ab)^+ and NFA for (bb)^+. Then concatenate all NFA to one entire NFA.

# Answer
You can use Thompson's construction. It constructs NFA with $\epsilon$ moves. But remove the forward $\epsilon$-transition from the new start state into the new final state since you are interested in $L^+$ and not in $L^\*$.

NFA with $\epsilon$ moves is a generalization of NFA and DFA. But you can systematically transform any NFA with $\epsilon$ moves into equivalent NFA without $\epsilon$ moves and DFA. Look here for more.
> 2 votes

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


# Question
Title: TSP decision problem vs TSP optimization problem
Let's check together whether the TSP-decision problem is NP-complete. Maybe it will help me to understand things better.

Question for TSP-decision problem: Given n cities and a tour from length $k$. The traveller starts at an arbitrary city, visits every other city just once and returns to the starting point. Does a tour from length $\leq{} k$ exist?

Let's first check whether the TSP is in NP:

A proof is given. Proof in this case is a tour. For it to be in NP, we must be able to verify this proof with a deterministic algorithm in polynomial time. So first we have to check, whether every city is only visited once. This can be done at most in $O(n^2)$. Next we need to calculate the distances and sum them up. This can be done as well at most in $O(n^2)$. The last step is to check whether the calculated length is $\leq{} k$. The hole process would require a polynomial time $\rightarrow 2 n^2 = O(n^2)$.

So the TSP-decision problem is in NP. What about the NP-hardness? We don't need to prove that, because Richard M. Karp proved that the Hamiltonian Circuit is NP-complete. The TSP is a special case of the Hamiltonian Circuit, therefore we know TSP must be NP-complete as well. NP-complete means = NP-hard and NP.

Is this possible with TSP-optimization problem?

Question for TSP-optimization: Given n cities and a tour from length $k$. A traveller starts at an arbitrary city and visits every other city just once and returns to the starting point. Is tour from length k the shortest tour? We can check in polynomial time, that every city is visited once. However we can't check whether $k$ is really the shortest tour, because we would have to check every other possible tour as well. That would mean $(n-1)!$ possible tours. And this would make the hole process above exponential.

So TSP-optimization problem is not in NP? Therefore it is not NP-complete, but NP-hard?

Anything wrong about my thoughts?

# Answer
> 1 votes
Only decision problems can be NP-hard or NP-complete; these are problems for which the answer is either Yes or No.

Optimization problems have an *optimal solution* as an answer. The associated decision problem is, given an instance and a value, whether the the value of an optimal solution is as good or better than the given value.

When we say that an optimization problem is NP-hard, we mean that its associated decision problem is NP-hard; it is an abuse of terms. We could also say that an optimization problem is NP-complete if its associated decision problem is NP-complete.

The TSP optimization problem is, given a graph, find a TSP tour of shortest length. The associated decision problem is, given a graph and a value $k$, decide whether the shortest TSP tour has length at most $k$. These are different than the problems that you describe.

Sometimes we are interested in a weaker version of the optimization problem, namely, given an instance, find the value of an optimal solution. This is the perspective usually considered in the field of hardness of approximation, in which the goal is to show that it is NP-hard to even *approximate* the optimal value.

# Answer
> -2 votes
I would like to point out that the TSP optimization problem returns a **Minimum length Hamiltonian-Cycle** for the graph. Now, our job to prove this problem is in NP class invloves

> Checking whether the Minimum length falls within a range.

Now this range is calculated by adding the weight of **n-1** number of edges in increasingly sorted order for the minimum bound and decreasingly sorted order for the maximum bound *(This maximum or minimum values are not necessarily cycle-lengths)*. This whole checking process can be done in polynomial time. Hence, TSP optimization problem also lies in NP class.

If anyone thinks that the way of proving this problem to be NP class isn't correct, I would also point out what Raphael originally posted :

> However we can't check whether k is really the shortest tour, because we would have to check every other possible tour as well. That would mean (n-1)! possible tours. And this would make the hole process above exponential.

This problem itself is similar to the TSP problem and thus is not what we want to look for.

P.S. Please correct me if I'm wrong anywhere !

---
Tags: complexity-theory, np-complete, np-hard, np, traveling-salesman
---


# Question
Title: $U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP complete
I'm trying to prove $U = \\{ \langle M, x, \\#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\\}$ is NP-complete. Showing it is NP is trivial. NP-hardness is the hard part. One way to do it would be to reduce a known NP-complete problem to $U$. Another way would be to find a general way to reduce any NP problem to $U$ in polynomial time.

I've found some online proofs for doing this. They all seem to reduce some arbitrary NP problem, say $A$, to $U$ by using the polynomial bound for the nondeterministic polynomial-time decider for $A$. So let $A$ be some NP problem, and let $N$ be its non-deterministic decider which runs in $n^{k}$ time for some $k$. Then output $\langle N, x, \\#^{k} \rangle $. The issue I have with this solution is, how do you know what $k$ is? You know that $A$ is NP, so there is a non-deterministic polynomial time decider for it, but how do you know the actual degree of that polynomial? It seems false to assume it is already known, surely one should have to compute it manually to obtain a reduction. How could you compute the degree of this polynomial in polynomial time? The existing proofs seem to gloss over this critical fact.

# Answer
> 2 votes
Finding the running time of a given Turing machine is undecidable. Luckily, you don't need to find the actual degree. You only need to show the existence of a reduction from $A$ to your language, not to construct a procedure that given a description of $A\in\mathsf{NP}$ (say, as the encoding of its verifier), will output a reduction from $A$ to your language.

Think of it this way, let $\\{f\_n\\}\_{n\in\mathbb{N}}$ be a sequence of functions, where $f\_i(x)=\left(M\_A,x,\\#^{|x|^i}\right)$. One of the functions in this sequence is the reduction you're looking for, and I don't need to point out which one (note that I can specify it in terms of the degree of the polynomial in the running time of $M\_A$).

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


# Question
Title: Can I use Θ if tightest lower and upper bound are not the same?
When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation? If an algorithm has a running time of $\Theta(n)$, is it safe to assume that the upper and lower bound are the same?

# Answer
> When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation?

Do you mean to say that we can only prove an $\Omega(f\_1)$ and an $O(f\_2)$ bound, respectively, on *the same cost function* (such as "worst-case running time)? Then yes: you can only use $\Theta(f\_1) = \Theta(f\_2)$ to combine the bounds if, well, $f\_1 \in \Theta(f\_2)$.

If you mean to say that best case and worst case have different growth rates, then that's a different issue: "lower bound" and "best case" as well as "upper bound" and "worst case" are *not* the same concepts! You can have $\Theta$-bounds for either case, but they still don't combine in a meaningful way since they are talking about different cost functions.

> Also, if an algorithm has a running time of theta(n), is it safe to assume that the upper and lower bound are the same?

That's not a "safe assumption", that's *the definition* of $\Theta$.

I suggest you revisit the definitions of the different Landau symbols and the basics on how to use them in algorithm analysis. Maybe start reading at our reference question.
> 3 votes

# Answer
Often when describing running times of algorithms we leave out information that can usually be inferred. Typically you should include: Time Complexity (Landau Notation), Input Type (worst case, best case, average, etc.) and Machine Model (e.g. RAM). The last two are often inferred, but you should describe them in your case.

I suspect when you say "the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same", what you really mean is "the asymptotic running time **in the best case** is not the same as the asymptotic running time **in the worst case**".

Imagine a simple function like this:

$$f(n) = c + n\cdot (n \bmod 2)$$

We can say the following:

* $f(n) = O(n)$
* $f(n) = \Omega(1)$

However, we could not concretely give a $\Theta(?)$ bound without more context. It would be more proper to say:

* $f(n) = \Theta(n)$ in the worst case (or $f(n) = O(n)$ in the worst case)
* $f(n) = \Theta(1)$ in the best case (or $f(n) = \Omega(n)$ in the best case)

The former of each statement is more precise and doesn't leave much room for error. The latter would also work but isn't as strict of an argument. I think this answer gives a good distinction on why a descriptive $\Theta(\cdot)$ should be preferred to an ambiguous $O(\cdot)$ or $\Omega(\cdot)$.
> 1 votes

# Answer
**f(n) = ϴ(g(n))**, if and only if:

* **f(n) = O(g(n))** (at the worst case f(n) performs an asymptotically equivalent of g(n) operations); and
* **f(n) = Ω(g(n))** (at the best case f(n) performs an asymptotically equivalent of g(n) operations)

So the answer to your second question is straightforward - yes, as it is the actual definition of the theta notation.

Regarding your first question, it would be **inaccurate** to denote the running time of such an algorithm in theta notation. In some cases, though, an algorithm may approximately perform as if it was bounded by a theta notation (meaning that only in extreme situations it performs otherwise). Still, you can't use the theta notation, unless your algorithm satisfies both conditions mentioned above.
> 0 votes

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


title: Best heuristic for A*?

text:
# Question
Title: Best heuristic for A*?
I'm trying to build a maze solver using A\* algorithm. The maze is a grid with movement allowed in 4 directions (up, down, left, right). If there's a starting cell (x1, y1) and a destination (x2, y2), which of these should I make my heuristic?

1. Euclidean Distance
2. abs(x2-x1)
3. (x2-x1)^2 + (y2-y1)^2
4. abs(x2-x1) + abs(y2-y1)

I'm leaning towards the euclidean distance because it seems intuitive but am unsure.

# Answer
> 2 votes
The best possible heuristic for A\* is the actual length of the shortest path to the target that way A\* can always select the next node in the optimal path. This is usually not possible to get so a approximation is needed.

The simplest heuristic is constant 0. This makes A\* revert into dijkstra.

The closer the heuristic gets to the shortest path the better it is.

But if a heuristic overestimates then the node with the optimal path may get pushed down the queue and a less optimal path will get selected.

For a grid with only the 4 cardinal directions (and no obstacles) the optimal heuristic is the manhattan distance (option 4).

Option 3 is not a good heuristic because it will overestimate the distance which can lead to a non-optimal path being chosen.

---
Tags: algorithms, shortest-path, heuristics
---


# Question
Title: Is closed form of summation less costly?
I imagine finding the closed form of an algorithm should yield fewer steps than the original. But in the case of a summation from 1 to n, I'm not sure if it actually does.

Here's the original sum

```
Sum(N)
   total = 0
   for x = 1 to N
       total = total + x
   ret total

```

Here's the closed form

```
Sum(N)
    ret N*(N-1)/2

```

I think the argument is that '\*' is only a single operation vs many '+' operations, but I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition.

Please correct me if my above claims are incorrect. My questions are: Does the closed form in this particular case yield fewer steps? Is closed form intended to reduce number of operations on the machine itself, and does it ever do that?

# Answer
> 7 votes
> I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition.

Try being more imaginative. I'm pretty sure that you were taught at school how to calculate, say, $38\times 144$ without adding $144$ thirty-seven times.

# Answer
> 1 votes
The complexity of the loop is roughly $\mathcal{O}(N n)$ where $n$ is the number of bits in N. The complexity of multiplication using the school book method is $\mathcal{O}(n^2)$ and there are better algorithms with complexity $\mathcal{O}(n^q)$ where $q\<2$. Since $n \< N$ it's clear that the multiplication is faster assymptotically.

---
Tags: algorithms, efficiency
---


# Question
Title: Are there unary languages that are in RE but not R?
Suppose that we have an alphabet Σ = {a}. My question is, is it possible to create a language with this alphabet, which is recursively enumerable, but not recursive?

My assumption is a no, i think we can construct a deterministic finite machine, which accepts every language, constructed with a single element in its alphabet.

# Answer
There are undecidable unary languages.

You can consider the set of words in $\\{0,1\\}^\*$ as essentially encoding natural numbers in binary.* Similarly, the set of words in $\\{1\\}^\*$ encodes natural numbers in unary. Intuitively, if a set of natural numbers is undecidable, that doesn't depend on the base in which the numbers are represented, since we can easily write algorithms to convert between bases.

Another way to see this is to observe that any decidable language (over *any* alphabet) is, by definition, decided by some Turing machine. There are only countably many Turing machines, but there are uncountably many unary languages. Therefore some (almost all!) unary languages must be undecidable.

---

* This isn't quite true because of the empty string and because, e.g., the strings $1$ and $01$ are clearly different but both encode the number one in binary. To get around this, say that the string $w$ encodes the number whose binary representation is $1w$.
> 3 votes

# Answer
It's easy to encode the Halting problem as unary language:

$\qquad\displaystyle L\_H = \\{ a^{\langle M \rangle} \mid M \text{ is a TM}, M(\langle M \rangle) \text{ halts}\\}$

is decidable if and only if the (special) Halting problem is decidable (proof is a pair of trivial reductions).

What you may have had in mind is that all context-free unary languages are also regular. That is an interesting fact, but does not carry up the Chomsky hierarchy. There are many ways to see that, including

* Myhill-Nerode's theorem and
* Parikh's theorem.
> 2 votes

# Answer
Sure we can. The set of all words $\Sigma^\*$ is isomorphic to $\mathbb N$, since only the length of each word matters. That is, given a word we can take its length, and given the length we can reconstruct the original word. Hence the bijection, which is trivially computable.

Hence, we can just take any r.e., non recursive subset of naturals $A$ (e.g. the Kleene's set $K$) and consider the language of all words of the form $a^n$ with $n\in A$.
> 1 votes

---
Tags: computability
---


# Question
Title: Search string excluding longer string containing substring that contains string, not exclusively longer string
How you define a search of text to find a string A, but exclude results that contains B only (which contains A), but not the both string A and string B?

For example:

* String A : "**Great Wall**"
* String B : "***Great Wall*** *of China*"
* Text 1: "The **Great Wall**"
* Text 2: "The ***Great Wall*** *of China*"
* Text 3: "The ***Great Wall*** *of China* is a **Great Wall**"
* Text 4: "Lorem Ipsum"

I've used Bold to indicate when String A is present and Italics when String B is present.

We would like to search for Texts that contains A, and A + B, but not B only.

So the results should be the Texts 1 and 3.

What approach would enable us to find these results?

Also, we are using a search that can provide us only a list of items that contains a string.

# Answer
> 1 votes
Finite automata to the rescue!

Let

* $\mathcal{A} = \Sigma^\* \cdot \\{A\\} \cdot \Sigma^\*$ and
* $\mathcal{B} = \Sigma^\* \cdot \\{B\\} \cdot \Sigma^\*$

be the regular languages that contain all strings with substring $A$ resp. $B$.

Note then that

$\qquad\displaystyle L = \overline{\mathcal{B}} \cdot \\{A\\} \cdot \overline{\mathcal{B}} \ \cup\ \mathcal{A} \cdot \mathcal{B} \ \cup\ \mathcal{B} \cdot \mathcal{A}$

is the set of all strings you are looking for, and from basic closure properties of REG we know that it is regular as well.

Constructing a (minimal) DFA from the above description using standard constructions yields an effective method that may or may not be efficient.

---
Tags: algorithms, strings, searching
---


# Question
Title: Is the complement of the Turing machine equality language not recursively enumerable as well?
The language that determines if two Turing machines are equivalent is not recursively enumerable because you can reduce it to the emptiness problem (does a Turing machine take no input).

Then for the complement of this language (ie. if two Turing machines are not equivalent) would you be able to reduce that to the non-emptiness problem (a Turing machine takes some input)?

And thus this language would be recursively enumerable.

However, I thought the Turing machine equality language is an example where both a language and its complement are not recursively enumerable.

# Answer
> The language that determines if two Turing machines are equivalent is not recursively enumerable because you can reduce it to the emptiness problem (does a Turing machine take no input).

You have the reduction the wrong way around. You're saying "Telling if two Turing machines are equivalent is impossible because, if I could solve some impossible problem, I could solve this one." Well, that's like saying, "Lifting a can of beans is impossible because lifting a truck is impossible and, if I could lift a truck, I could lift a can of beans."

Rather, you want to reduce the known-hard problem to TM equivalence: "If I could solve this problem, I'd be able to solve this impossible problem." Specifically, if you could solve the TM equivalence problem, you could solve the TM emptiness problem by asking, "Is the machine I'm interested in equivalent to this machine that immediately rejects every input?"

> Then for the complement of this language (ie. if two Turing machines are not equivalent) would you be able to reduce that to the non-emptiness problem (a Turing machine takes some input)?

Again, you mean the reduction to be the other way around. So, we need to show that the non-equivalence problem being RE would make the non-emptiness problem RE. But the non-emptiness problem *is* RE: just dovetail simulations of the machine on all inputs and accept if it accepts one of them. So there's no contradiction available, here.

> However, I thought the Turing machine equality language is an example where both a language and its complement are not recursively enumerable.

Correct. Intuitively, you can't enumerate the language of inequivalent TMs because to do that would require you to definitively say "This machine loops on some input that this other machine accepts." And, indeed, we can turn this intuition into a formal proof.

First, observe that the Turing machine non-halting problem (given a description of a Turing machine $M$ and an input $x$, does $M(x)$ loop?) is not RE. This is the complement of the halting problem so, if it were RE, then both the halting problem and its complement would be RE. But if a language and its complement are both RE, they're both recursive, and we know that the halting problem isn't recursive.

Now, observe that, if we could solve the TM inequivalence problem, we could solve the non-halting problem. To determine if $M$ loops on input $x$, just ask if it is inequivalent to the machine "If the input is $x$, halt; otherwise, do the same as $M$."
> 4 votes

---
Tags: computability, turing-machines, undecidability
---


# Question
Title: How is a compiler related to the runtime system?
A quick search on the role of compiler brings up the following:

> A compiler is a special program that processes statements written in a particular programming language and turns them into machine language or "code" that a computer's processor uses.

However, I also read that every language needs to have a target runtime system and programs written in that language execute in the context of the runtime system.

Adding up the two, it appears that a compiler converts programs into bits understandable by the runtime system and the runtime system acts as the agent interpreting the bits, translating them to the processor intructions. Is this correct? If not, how else are compiler and runtime system related?

And if the above is correct, it would imply the following:

1. two executables compiled from programs with identical logic written in different languages would not be identical
2. with people typically installing several programs from disparate sources, an average machine would have to have dozens of runtimes which doesn't seem to be the case.

What am I missing here?

# Answer
I just looked on my machine (which is running macOS Sierra), and I found four runtime systems for C and C++ alone:

```
/usr/lib/crt1.10.5.o
/usr/lib/crt1.10.6.o
/usr/lib/crt1.o
/usr/lib/gcrt1.o

```

They're not huge; only about 10kB each. Small enough that if you statically linked them to a typical program they would barely register. Still, there they are.

I'm certain that I have a bunch of others for different languages, too: Python and Java are fairly standard. Emacs seems to come pre-installed so there's a Lisp-like language. There's probably a Swift runtime if I look hard enough. And, of course, that's not including all the languages I installed myself because I like collecting programming languages.

Many modern operating systems are designed with C in mind (in that their system call APIs are C calls), and many languages with a "foreign function" interface support C natively because so many third-party libraries support a C API. So runtimes for many languages are often built on top of the C runtime.

It's useful to think of a runtime system as some kind of virtual machine. However, many programming languages do compile to machine code, so the job that the runtime system has to do can be as simple as initialisation and shutdown only, with nothing further needed while the program is running.

For example, a typical runtime for C and C++ (they are often shared these days) has to perform the following initialisation before any C code is run:

* Set up the C stack.
* Initialise any standard library data structures that need to be initialised (e.g. `atexit` or `stdin`/`stdout`/`stderr`).
* Invoke static constructors (e.g. for C++).
* Process command-line arguments and environment variables to pass to `main()`.
* Call `main()`.

There's nothing here that really corresponds to interpreting the output of the compiler, with the possible exception of information that the compiler generates about static constructors.

Even for compiled languages, however, the runtime may provide subroutines to support source-level operations for which it would be wasteful or inconvenient for the compiler to generate code.

Exceptions in C++ are one example. Another is where some particular platform doesn't have a suitable instruction; many 32-bit platforms don't have a native 64-bit division instruction, but the compiler may still want to support 64-bit integers.
> 3 votes

---
Tags: compilers
---


title: Longest path in a DAG: source to sink?

text:
# Question
Title: Longest path in a DAG: source to sink?
Is the longest path in a (weighted) DAG always from a source to a sink? This seems correct to me by intuition, but I'm not 100% confident. Like, for example, if I had an array in which each index represented a node in topological order, and stored the length of the longest path with that node as its endpoint in the graph at that index, would the longest path in the graph always be stored in the last index?

# Answer
First, notice that your topological sort comment isn't quite right, because other nodes can be sinks than the last node in a topological sort.

To your original question: Consider some path in a DAG that is *not* from a source to a sink. Can you show that this path can be made longer? (This implies that the longest path must be from a source to a sink.)

For example, if the path does not start at a source, then it has at least one incoming edge... (make sure you use the fact that the graph is a DAG).
> 2 votes

---
Tags: graphs, weighted-graphs, dag
---