title: guillotine cuts versus general cuts

text:
# Question
Title: guillotine cuts versus general cuts
Cutting problems are problems where a certain large object should be cut to several small objects. For example, imagine you have a factory that works with large sheets of raw glass, of width $W$ and length $L$. There are several buyers, each of which wants an unbounded number of small glass sheets. Buyer $i$ wants sheets of length $l\_i$ and width $w\_i$. Your goal is to cut small sheets from the large one, such that the total used is maximized and the waste is minimized (there are also other types of cutting and packing problems).

One common restriction in cutting problems is that the cuts must be **guillotine cuts**, i.e., each existing rectangle can be cut only to two smaller rectangles; it is impossible to make L-shapes etc. Obviously, the maximum used area with guillotine cuts might be smaller than the maximum used area without restriction.

My question is: **Are there upper and lower bounds on the ratio between the optimal guillotine cut and the optimal general cut?**

Related work: Song et al. (2009) describe an algorithm that uses a restricted type of guillotine cuts – *twice-guillotine cuts*. They prove, using geometric constraints, that the ratio between the maximum twice-guillotine cut to the maximum guillotine cut is bounded by $\frac{6}{7}$. I am looking for a comparable result about the ratio between the maximum guillotine cut to the maximum general cut.

# Answer
> 9 votes
Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts.

Let us start with the upper bound and assume we are given a square piece of glass with a side length of $2$. Furthermore, we have exactly one buyer who is interested in rectangular glass sheets of width $1-\varepsilon$ and length $1+\varepsilon$. Using general cuts, the optimal solution looks something like the following picture, with four of the desired rectangles placed around a little square of side length $\varepsilon$ in the middle.

It is easy to see that this cutting pattern can not be achieved via guillotine cuts. In fact, any cutting pattern using guillotine cuts can fit at most 3 of the desired rectangles into the original square. As a result, the worst ratio between guillotine cuts and general cuts is at least $3/4$.

Next, we have a look at the lower bound. Let $W$ and $L$ be the side lengths of the original sheet of glass. Without loss of generality, we can assume that there exists a buyer $i$ such that $w\_i \leq W$ and $l\_i \leq L$. Otherwise, the original sheet would be unusable, no matter if we use guillotine cuts or general cuts. However, using guillotine cuts, we can always cut out at least one quarter of the original sheet by simply aligning the rectangles desired by buyer $i$, as shown in the following picture.

Notice that the red rectangle corresponds to one quarter of the whole sheet and is completely covered by the gray rectangles buyer $i$ desires. On the other hand, even if we use general cuts, we cannot use more than the whole sheet, which gives us a lower bound of $1/4$.

I am aware that the lower bound is quite weak and it can probably be improved with a bit more work. But it is a start.

---
Tags: reference-request, computational-geometry, lower-bounds, packing
---


title: Bin packing with twin items

text:
# Question
Title: Bin packing with twin items
Assume we are given $k$ bins of capacity $b$ and $n$ items with integral sizes $x\_1,\dots,x\_n$. The bin packing problem is to decide whether there exists an assignment of items to bins such that no bin exceeds its capacity. In this standard from, the bin packing problem is well known to be NP-hard. However, consider a version of the problem where every items has a twin of equal size. More formally, if $i$ and $j$ are twins, it holds that $x\_i = x\_j$.

For two bins, the problem is easy since there exists a feasible solution if and only if a packing where no twins share the same bin is feasible. However, what happens if we have more than two bins? I suspect that the problem becomes NP-hard. Unfortunately, I have not been able to prove this so far.

Does anyone have an idea for a reduction or know if the problem has been studied before? Also, if the problem is hard for twins, does the hardness carry over to triplets, quadruplets etc.?

# Answer
As it turns out by a rather complicated chain of reductions starting from three dimensional matching, which is too involved to be discussed here, bin packing remains NP-hard for twin items. It even remains hard for triplets, quadruplets or any fixed number of similar items.
> 0 votes

---
Tags: reductions, np-hard, packing
---


title: NP-hardness of a scheduling problem

text:
# Question
Title: NP-hardness of a scheduling problem
***Problem:*** Given an undirected, weighted, complete graph $G = (V, E, w, c)$. $w$ is the *time weight* function on edges, $w:E \to \mathbb{N}^{+}$; $w(e)$ represents the time it takes to travel along edge $e$. $c$ is the *time deadline* function on vertices, $c:V \to \mathbb{N}^{+}$.
Given a source vertex $s$, the question is whether there exists a tour $p: v\_{0} = s \to^{e\_{0}} v\_{1} \to^{e^{1}} v\_{2} \to \cdots \to v\_{i} \to^{e\_{i}} \to \cdots$ such that

* $\\{ v\_{i} \\}$ is a multi-set. That is, $p$ is not necessarily a simple path.
* $\\{ v\_{i} \\}$ contains all vertices, i.e., $V \subseteq \\{ v\_{i} \\}$.
* For each vertex $v \in V$, suppose that it ***first*** appears in $p$ as $v\_{i}$, then we require that $$\sum\_{n=0}^{n=i-1} w(e\_{n}) \le c(v).$$

***Background:*** A courier needs to deliver goods to the places represented by $V$. Each consignee has specified a deadline. The question is whether there is a tour satisfying all these deadlines.

I guess that this problem is NP-hard, and it reminds me of the scheduling problems with deadlines. However, I cannot find a suitable one for the reduction. Any ideas? (Other reductions for NP-hardness or algorithms are also appreciated.)

# Answer
This sounds very much like a Hamilton path problem. If you set the edge weights all to $1$ and the deadline of the vertices all to $|V| - 1$, then each vertex can only be visited once, since there is not enough time to visit one twice before the deadline runs out. Finding a Hamilton path on the other hand is NP-hard. Thus, your problem is NP-hard as well.
> 4 votes

---
Tags: algorithms, complexity-theory, reference-request, np-complete, scheduling
---


# Question
Title: Computing probability of sentence using N-grams
I have implemented N-grams by constructing a tree (or a trie, technically) that stores frequencies of each N-gram. Each path in the tree represents an N-gram and its frequency: the path consists of N nodes (each node containing a word), followed by a leaf node containing the frequency. So, each path in the tree is of length N + 1.

I'm now trying to compute the probability of observing a given sentence, and am having some trouble, particularly when N \> 2.

For the sentence `<s> Hello world </s>` using N = 1, the probability is `P(<s>) * P(Hello) * P(world) * P(</s>)`.

Using N = 2, the probability is `P(Hello | <s>) * P(world | Hello) * P(</s> | world)`.

But for N = 3, I'm not sure what to do. If I compute `P(Hello | <s>) * P(world | <s> Hello)`, then my tree will give an error since `<s> Hello` is a bigram and the tree is only defined for trigrams.

I considered maybe wrapping each sentence an additional time, e.g. `<s> <s> Hello world </s> </s>` then computing `P(Hello | <s> <s>) * P(world | <s> Hello) * P(</s> | Hello world) * P(</s> | world </s>)`, but this seems non-intuitive and involves mutating the corpus in an ugly way.

What is the proper way to compute this probability?

# Answer
The $N$-gram model assumes a generative model in which the next word generated depends only on the preceding $N-1$ words. Using Bayes' law, we get that the probability of a sentence $w\_1,\ldots,w\_n$ is $$ P(w\_1\cdots w\_n) = P(w\_1) P(w\_2|w\_1) P(w\_3|w\_1w\_2) \cdots P(w\_N|w\_1\ldots w\_{N-1}) P(w\_{N+1}|w\_2\ldots w\_N) \cdots P(w\_n | w\_{n-N+1}\ldots w\_{n-1}). $$ In the particular cases $N=1,2,3$, this gives $$ P(w\_1\cdots w\_n) = P(w\_1) P(w\_2) \cdots P(w\_n), \\ P(w\_1\cdots w\_n) = P(w\_1) P(w\_2|w\_1) P(w\_3|w\_2) \cdots P(w\_n|w\_{n-1}), \\ P(w\_1\cdots w\_n) = P(w\_1) P(w\_2|w\_1) P(w\_3|w\_1w\_2) P(w\_4|w\_2w\_3) \cdots P(w\_n|w\_{n-2}w\_{n-1}). $$ This means that your expression for $N=2$ is wrong.

In practice, we don't want to store special tables for the first $N-1$ characters. There are two ways around this. First, we can ignore entirely the first $N-1$ words. This makes sense when the text is very long, and we don't expect the first few words to make a big difference in the resulting probability. Second, we can include a special "blank" symbol and add it to our tables, so that (for example) $P(w\_1)$ is stored as $P(w\_1|\not{b}\ldots \not{b})$.

Usually one stores not the actual probabilities but rather their *logarithm*. The reason is that adding numbers is faster than multiplying them. As an added benefit, you don't have to worry about the dynamic range of the floating point data type you use (the actual probability could be rather close to 0 and could cause underflow, but this is unlikely for its logarithm).

Another thing to keep in mind is that the results are more meaningful as the text becomes longer. Your example is very short and doesn't serve as a good test case.
> 3 votes

# Answer
You seem to be having trouble figuring out how to compute `P(world | <s> Hello)`. If so, here's how to compute that probability, from the trigram frequencies.

Let `f(W X Y)` denote the frequency of the trigram `W X Y`. Now find all words `Y` that can appear after `<s> Hello`, and compute the sum of `f(<s> Hello Y)` over all such `Y`. This sum is the frequency of the bigram `<s> Hello`, so call it `f(<s> Hello)`.

Now a reasonable estimate for `P(world | <s> Hello)` is simply `f(<s> Hello World) / f(<s> Hello)`.

In practice, I recommend you use Laplace smoothing or some other kind of smoothing, to handle zero counts better.
> 1 votes

---
Tags: natural-language-processing
---


# Question
Title: What is the complexity of an in-place merge algorithm for forward iterators
I have written an in-place merge algorithm for forward iterators. My goal was to write an in-place merge algorithm to merge two sorted parts of a singly linked list without allocating extra memory to perform the merge. However, I have no clue how to determine its complexity.

Here is the corresponding pseudocode algorithm; I tried to represent the concept of iterators in pseudo-code, but that's not really pretty. Basically, an iterator is an object that points to a value in a sequence of elements. The only operations usable with a forward iterator are the following:

* Check whether two iterators point to the *same* value (`=` and ); just remember that two values can be equal without being the same.
* Copy the iterator (`let it = other_it`), basically create another iterator that points to the same value.
* Advance the iterator so that it points to the next value in the sequence (`advance`).
* Access the value it points to, generally to read or write that value (`value_of`), `<-` is used to assign the values.
* Get the iterator pointing to the next value in the sequence (`next_iterator`).

The following function uses the set of operations defined above to implement an in-place merge algorithm.

```
function inplace_merge(first: ForwardIterator, middle: ForwardIterator, last: ForwardIterator)

    while first ≠ middle
        if value_of(middle) < value_of(first)

            # first should be in the right partition
            let tmp = value_of(first)

            # Put right in place
            value_of(first) <- value_of(middle)

            # Look for the place where to insert tmp
            let current = middle
            let next = next_iterator(current)

            # Move everything smaller than tmp to the left
            while next ≠ last and value_of(next) < tmp
                value_of(current) <- value_of(next)
                advance current
                advance next
            end while

            # Insert tmp in the right place
            value_of(current) <- tmp
        end if

        advance first
    end while

```

This algorithm takes two sorted ranges `[first, middle)` and `[middle, last)` and reorders them to produce a sorted range `[first, last)`. The function `compare` is used to compare the elements. The algorithm more or less works like this: whenever an element in the left range is greater than the first element of the right range, we replace the first element of the right range in the left range, then we move every element to the left until we find the place where to insert the element that was originally in the left range (I know, plain-text descriptions sound a bit cryptic).

What is the complexity of this algorithm, considering that the complexity is determined by the number of comparisons performed between value with `<`?

# Answer
Your algorithm is very similar to insertion sort or selection sort. Here is some pseudocode which hopefully captures your algorithm:

```
inplace_merge(A[1,...,n], B[1,...,m])

C[1,...,n] = A[1,...,n]
C[n+1,...n+m] = B[1,...,m]
for i from 1 to n:
   if C[i] > C[n+1]:
     find position j in {1,...,m} such that C[n+j] < C[i] <= C[n+j+1] (where C[n+m+1]=∞)
     C[i], C[n+1,...,n+j-1], C[n+j] = C[n+1], C[n+2,...,n+j], C[i]
return C

```

The invariant is that at the end of each iteration, `C[1,...,i;n+1,...,n+m]` and `C[i+1,...,n]` are both sorted, and that the multiset of elements never changes.

Consider what happens when all elements in the array `A` are larger than all elements in the array `B`. In this case, `j` always equals `m`, and so the running time of each iteration is $O(m)$, and the total running time is $O(nm)$.

In contrast, the mergesort merging algorithm merges the two arrays in time $O(n+m)$, and should be preferred over your algorithm.
> 4 votes

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Pi Calculus: Restriction necessary for molecular (atomic) action?
In "A Calculus of Mobile Processes, Part 1" \[1\], Milner et al. give an example for transmitting a pair of values $(u,v)$ from the process $P$ to either $R$ or $Q$ (see page 13). All three processes are assumed to run in parallel.

They present following solution:

$$ \begin{align} P &= (w) (\bar{x}(w).P' | \bar{w}u.\bar{w}v.0) \\ Q &= x(w).w(y).w(z).Q' \\ R &= x(w).w(y).w(z).R' \end{align} $$

They claim that "it is vital to this idea that w (...) is indeed a private name". Why is this a necessity?

Wouldn't following solution without restriction work?

$$ \begin{align\*} P &= \bar{x}(w).P' | \bar{w}u.\bar{w}v.0 \\ Q &= x(\alpha).\alpha(y).\alpha(z).Q' \\ R &= x(\beta).\beta(y).\beta(z).R' \end{align\*} $$

\[1\] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.363&rep=rep1&type=pdf

# Answer
Your solution would work only if you consider $P$, $Q$ and $R$ in parallel as a "closed system", i.e. a system which is not supposed to be composed and interact with an external environment but just to perform internal reactions.

In the context of your quotation, the translation of a polyadic action into a monadic one is supposed to be compositional and to yield a bisimilar labelled semantics. The role of the restriction is to avoid exposing the actions on $w$ to the environment: what happens if the environment performs actions on the public channel in your solution? For instance, consider the process $S$ $$ S = w(y).S' $$ If put in parallel with your version of $P$, $Q$ and $R$ it can "steal" the first/second component of the couple from $Q$ or $R$. This is because you do not need to receive $w$ on $x$ to be able to use it if $w$ is a public name, while that is the only way to acquire it when it is restricted.
> 4 votes

---
Tags: algorithms, computation-models, pi-calculus
---


# Question
Title: Why does $2^{O(\log n)} = n^{O(1)}$ hold?
I was recently looking at the article on the P complexity class on Wikipedia. In the section on relationships to other classes, it mentions that P is known to be at least as large as L, giving this explanation:

> A decider using $O(\log n)$ space cannot use more than $2^{O(\log n)} = n^{O(1)}$ time.

The article sadly fails to explain how that last equality holds. How exactly does one go about showing that $2^{O(\log n)} = n^{O(1)}$?

# Answer
This is simple math. An expression of the type $O(\log n)$ is at most $C\log n$ for some $C \> 0$ and large enough $n$. So for large enough $n$, the entire expression $2^{O(\log n)}$ is at most $$ 2^{C\log n} = n^C = n^{O(1)}. $$ The first equation follows from the definition of the logarithm $2^{\log n} = n$, which in this case I conveniently assumed is taken to the base 2 (though it makes no difference in this case – can you see why?).
> 7 votes

# Answer
This follows from a little bit of algebraic manipulation of these expressions:

$$2^{c \log n} = (2^{\log n})^c = n^c = n^{O(1)}.$$

Alternatively, if you prefer:

$$2^{c \log n} = 2^{\log(n^c)} = n^c = n^{O(1)}.$$
> 6 votes

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


# Question
Title: If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$?
If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$? I am asking this question because, for other non-deterministic classes, it seems $\mathbf{P} = \mathbf{NP}$ always establishes that they are equal to their deterministic counterparts.

# Answer
This is an open research question. At our current state of knowledge, knowing $\mathbf{P}=\mathbf{NP}$ would neither imply $\mathbf{L}=\mathbf{NL}$ nor $\mathbf{L}\neq\mathbf{NL}$. And, conversely, knowing $\mathbf{L}=\mathbf{NL}$ or $\mathbf{L}\neq\mathbf{NL}$ wouldn't imply anything about the $\mathbf{P}$ vs $\mathbf{NP}$ question. (But it's possible that the *proof* of $\mathbf{L}$ vs $\mathbf{NL}$ would tell us something about $\mathbf{P}$ vs $\mathbf{NP}$ or vice-versa.)

We know $\mathbf{L}\subseteq \mathbf{NL} \subseteq \mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE} = \mathbf{NPSPACE}$, where the equality follows from Savitch's theorem. The nondeterministic version of the space hierarchy theorem says that $\mathbf{NL}\neq \mathbf{NPSPACE}$ so we know that at least one of the set inclusions must be strict. We kinda think they're all strict but our current knowledge doesn't rule out any subset of them, as long as it includes at least one between $\mathbf{NL}$ and $\mathbf{PSPACE}$.
> 16 votes

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Are there well-specified formal languages that are not regular?
> Given a finite alphabet, there are well-specified formal languages that can not be recognized by regular expressions, FSAs or regular grammars **True/False**

I am studying for my exam and I am unsure about this question. From my understanding, you generate formal languages from regex, FSA. For i.e. for `a*` our formal language will be

`empty,a,aa,aaa etc.`

So I can identify if a formal language can be described by a regex, but not sure if that is always the case. Could somebody please help me with this?

# Answer
> 6 votes
There are indeed well-specified formal languages that cannot be represented by regular expressions, even on a one-letter alphabet. Examples include $\\{a^{n^2} \mid n \> 0\\}$ and $\\{a^p \mid p \text{ is a prime number}\\}$.

# Answer
> 3 votes
If "well-specified" does not have a very special meaning in your course, than the answer is "yes"; it follows directly from e.g.

$\qquad\displaystyle \mathrm{REG} \subsetneq \mathrm{CFL} \subsetneq 2^{\Sigma^\*}$,

a result that was probably presented in the course.

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


# Question
Title: How to prove for that a given non-regular language its given super-set is also non-regular?
Consider the non-regular language $L\_1$ = {$a^n$b$a^n$: $n \geq 0$} and its super-set language

L = Language of strings with equal number of trailing and leading a's,

or in other words,

$$L = \\{a^n b w b a^n : n \ge 0, w \in \\{a,b\\}^\*\\} \cup \\{a^n b a^n : n \ge 0\\}.$$

How would we prove that L is also non-regular?

I have the idea that I should use the help of $L\_2 = L - L\_1$, but I'm stuck at the following step:

$L\_1 \cap L\_2 = \phi $ , thus $L\_1 \cap L\_2$ is a regular language.

I was trying to prove it using contradiction.

Let, L to be regular which is $L\_1 \cup L\_2 $ is regular.

And tried to prove, $L\_1$ or $L\_2$ is equal to a set union or intersection or complement operation over the regular sets $L\_1 \cap L\_2 $ and $L\_1 \cup L\_2$

But stuck at

$L\_1 = \[(L\_1 \cup L\_2) \cap (L\_2)^c\] \cup (L\_1 \cap L\_2)$

With Myhill-Nerode theorem: I might be incorrect please fix me if I am wrong.

Take S =$a^\*(b+b.(a+b)^\*.b)$
Pick x and y from S such that $x \neq y$.

x = $a^n b$
y = $a^m b$
Take, z = $a^n$

$x.z \in L$ but $y.z \notin L$. Thus, by Myhill\_Nerode one can conclude it to be non-regular.

# Answer
> 5 votes
Since you already know that $L\_1$ is nonregular, here is a simple proof. Suppose that $L$ is regular. Then since $a^\*ba^\*$ is regular, the language $L \cap a^\*ba^\*$ should be regular. But $L \cap a^\*ba^\* = L\_1$, which is not regular. Hence $L$ is nonregular.

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


# Question
Title: If a Ptime function loses x bits of data at every call, is it a one way function?
If we have a computational function $f(x)=g(f(x-1)^2)$, where $g(y)$ is a floating point operation, mapped onto a given number of bits say 32 bits (thus leading to loss of a given number of precision bits every time), is the function a one-way function?

# Answer
> 4 votes
A one-way function is a function which is easy to compute but hard to invert. More accurate, it is a polytime function $f$ such that given a random $y$, it is hard to find a preimage $x$ satisfying $f(x) = y$. The exact sense of hardness isn't important here.

Your function is not one-way since it fails the first requirement: it is not easy to compute. If you use your recursive definition, computing $f(x)$ takes $x$ applications of the function $g$, which is exponential time.

It also fails the second requirement, since its range is finite. You can hardcode one preimage for each possible value in the image, and so invert the function efficiently.

---
Tags: cryptography, one-way-functions
---


# Question
Title: For practical computing purposes, every algorithm is O(1)?
I am taking a course in algorithm analysis and the professor is arguing that using the negation of the definition for Big O, it can be argued that, for practical computing purposes, both the running time and the memory usage of every algorithm is O(1). How is this possible? How can it be proven?

# Answer
> 6 votes
Sure. Time and memory are both finite, thus $O(1)$. But that isn't a very interesting (useful) result. Complexity is studied precisely because we do care how much time (or memory, or whatever other measure is of interest) algorithms take as a function of the input (size), even if we aren't willing to wait "finite, but very large" time nor to equip the machine with "finite, but very large" memory. We'd want to have an idea of how long we have to wait, or how much memory is enough.

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


# Question
Title: Can this question be solved without knowing the Page Table Entry?
I'm preparing for the exams and this question came up -

> Consider a machine with $64MB$ physical memory and a $32$-bit virtual address space. If the page size is $4KB$, what is the approximate size of the page table?
> (A) 16MB
> (B) 8MB
> (C) 2MB
> (D) 24MB

The way I've solved it -
**Physical Address Space** = $64MB = 2^{26}B$
**Virtual Address** = $32$-bits, $\therefore$ **Virtual Address Space** = $2^{32}B$
**Page Size** = $4KB=2^{12}B$
**Number of pages** =$\\,\Large\frac{2^{32}}{2^{12}}$$=2^{20}$ pages.
**Number of frames** =$\\,\Large\frac{2^{26}}{2^{12}}$$=2^{14}$ frames.
$\therefore$ **Page Table Size** = $2^{20}\times 14\\,bits \approx 2^{20}\times 16\\,bits\approx 2^{20}\times 2B= 2MB.$
Some books claim the answer to be $8MB$ and I don't see why, but that confuses me.
Is this the correct way to solve it? Is the answer correct?

# Answer
Your answer and calculation is correct, if we used a one-level page table.

However, a one-level page table is probably not a very likely implementation strategy, so it's more interesting to analyze the space consumption for a more plausible implementation strategy and work out what this would look like.

A two-level page table is probably a more likely implementation strategy. The first 9 bits of the virtual address will be used as an index into the first-level table; they yield the entry in the second level. The next 11 bits of the virtual address will be used as an index into the second-level table.

With this strategy, the size of the entire page table is $1+k$ pages, or $(1+k) \times 2^{12}$ bytes, where $k$ is the number of second-level table entries. The worst case is $k=2^9$, in which case the entire page table takes up approximately $2^9 \times 2^{12} = 2^{21}$ bytes, i.e., 2 MB. In other words, the worst case for a two-level page table is approximately the same as the size of a one-level page table. However, the best case is much less.

I don't know how the books got 8 KB, but that seems clearly wrong, absent further assumptions; that would only allow 4096 entries in the entire page table, which clearly isn't enough to maintain a virtual-to-physical mapping for all of virtual memory.
> 3 votes

# Answer
obvious it can be solved. u can calculate the size of page table entry easily.

size of page table entry = No. of bits used for frame number(convert it into byte), here bits in frame no. is 14 bits so it is approximately equal to 2 byte. so size of each entry of page table be 2B.
> -3 votes

---
Tags: operating-systems, memory-management, paging
---


# Question
Title: Machine with an oracle for a language that cannot decide another language in polynomial time
We usually see examples of languages contained in $P^A$ for some language $A$, or cases where $P^A=P^B$ (or $P^A\subseteq P^B$) for two languages $P^A$ and $P^B$.

However, there is any explicit example of two languages $A$ and $B$ such that $P^A\not\subseteq P^B$ and $P^A\not\supseteq P^B$?

I was thinking in something like $\mbox{HALT}$ and $\mbox{EMPTY}$ but Yuval Filmus made me see that in fact $P^{\mbox{HALT}} \subseteq P^{\mbox{EMPTY}}$, because $\mbox{EMPTY}$ is stronger than $\mbox{HALT}$. Nevertheless is possible to find an explicit language satisfying the desired property? What about $\mbox{FINITE}=\\{\<M\>: L(M) \mbox{ is finite}\\}$, it can be compared with $\mbox{HALT}$ in the same way as $\mbox{EMPTY}$?

# Answer
Let $A,B$ be two incomparable Turing degrees (these can be constructed by diagonalization, known in this context as *forcing*). If $P^A \subseteq P^B$ then in particular $A \in P^B$, and so $A$ reduces to $B$; since we know this is impossible, we can conclude that $P^A \nsubseteq P^B$. Similarly $P^A \nsupseteq P^B$.
> 3 votes

---
Tags: reductions, polynomial-time, oracle-machines
---


# Question
Title: Arden's rule expressed as matrix algebra
> The following theorem is (in the context of languages) known as Arden's Lemma: Given a linear system $X = B+AX$ and the matrix A is quasiregular, then we have a solution which is unique and which preserves rationality. In the next lemma we show the converse: For every rational series we can find a linear system such that the first component of its solution vector is exactly the given series. With these two results we have already done most of the work for proving the Theorem of Schutzenberger, which teaches us that the families of rational and recognizable series coincide.
>
> # Theorem 2.2.1
>
> Let $B \in \mathbb{K}\langle\langle\Sigma^\*\rangle\rangle^{n,1}$ and $A \in \mathbb{K}\langle\langle\Sigma^\*\rangle\rangle^{n,n}$ a quasiregular matrix. The linear system
>
> $$ X = B + AX $$
>
> has the unique solution $X = A^∗B$. Moreover, if $A$ and $B$ are $\mathbb{K}-rational$ then the solution $X$ is $\mathbb{K}-rational$.
>
> ## Proof:
>
> First we show that $X = A^∗B$ is a solution:
>
> $$ B + AX = B + AA^∗ B = (I + AA^∗)B = A^∗B = X. $$

My question is as follows: what does asterisk mean in this context (when it is used with matrices)? I know what Arden's Lemma is, but I don't understand the proof given here.

To credit the author of this paper: Regular Languages And Their Generating Functions: The Inverse Problem by Christoph Koutschan.

# Answer
> 3 votes
The notation is probably defined in the paper or in some standard reference, but one can guess that $$ A^\* = (I - A)^{-1}. $$ This definition satisfies the identity $A^\* = I+AA^\*$, since $$ I+AA^\* = I-((I-A)-I)A^\* = I-(I-A)A^\*+A^\* = I-I+A^\* = A^\*. $$ Presumably a quasiregular matrix $A$ is one for which $I-A$ is invertible, perhaps with some additional assumptions.

# Answer
> 3 votes
This is the Kleene star. The Kleene star is defined for any monoid. It is sometimes defined as

$$A^\* = 1 + A + A^2 + A^3 + \cdots$$

(given a suitable notion of convergence, and assuming the sum converges). Here $1$ is the identity -- in this case, the identity matrix. In monoids that have division, we can refer to our intuition that $1 + A + A^2 + A^3 + \cdots = 1/(1-A)$, and equivalently define

$$A^\* = (1-A)^{-1},$$

when the inverse exists. In your case, the inverse is simply the matrix inverse, and as before, $1$ is the identity matrix.

---

Alternatively, the Kleene star of $A$ can be defined as the element $A^\*$ satisfying

$$A^\* = 1 + A A^\* = 1 + A^\* A.$$

In other words, if there is an element $Z$ such that

$$Z = 1 + A Z = 1 + ZA,$$

then we say that $Z$ is the Kleene star of $A$, written $A^\* = Z$. Again, $1$ represents the identity in the underlying monoid/semiring -- in this case, the identity matrix.

---

See also the notion of a star semiring. For instance, matrices form a star semiring.

---
Tags: regular-languages, combinatorics, matrices
---


# Question
Title: Can every state in a DFA be an accepting state?
I know that we can have 0 accepting states in a DFA, it would just recognize the empty language. What about the case of all states being accepting? Would that mean it would recognize all of the strings in the DFA's particular alphabet?

Thanks

# Answer
Yes, every state can be accepting. Assuming the transition function is total (complete), so every state has a transition out on every possible letter in the alphabet, then yes, this would recognize all strings in the DFA's alphabet: the DFA would recognize $\Sigma^\*$.

If the transition function is not complete -- in other words, if there is some state $q$ and some letter $a$ where there is no transition out of $q$ on letter $a$ -- then the DFA doesn't necessarily recognize all of $\Sigma^\*$.

See In a DFA, does every state have a transition on every symbol of the alphabet? for more on that distinction. To avoid confusion, I generally recommend sticking to DFAs whose transition function is complete (total), at least until you understand the concepts well.
> 3 votes

---
Tags: finite-automata
---


# Question
Title: Given a set of irregular polygons finding a set of vertices (one on each polygon) such that distance between points is maximized
Given a set of irregular polygons with the same number of points, where $polygon\_i$ is completely contained within the boundary of $polygon\_{(i+1)} $.

I need to find a set of vertices (one vertex from each polygon) such that the pairwise distances between all of the points selected are maximized.

What kind of algorithm should I be looking at to solve this problem? The practical use case of this would be a case with 4-8 polygons with roughly 1000-3000 vertices each, I am looking for an approach that could work under these parameters, but am also interested in the classification of this problem from a theoretical perspective.

It seems like this is case of treating each point as the center of circle that is a member of an independent set in a geometric intersection graph, and then moving the points along the polygon boundary that they lie on such that the radius is maximized while keeping the set independant.

Potential Simplifications here are:

* Each polygon has the same number of vertices.
* All vertices of $polygon\_i$ are contained entirely within the area of $polygon\_{(i+1)} $
* All polygons lie on the same 2D plane.

# Answer
> 0 votes
I don't know whether this problem is in P. Given the similarity to facility location problems, it smells like it might be NP-hard. However, I can suggest some candidate algorithms. They break down into two categories: algorithms to get the exact optimal solution, and heuristics to get a pretty-good solution that hopefully will be an approximation to the optimal (but no guarantees).

## Exact algorithms

One approach is to convert to a decision problem, and then an algorithm for independent set. The decision problem is:

Given sets $S\_1,\dots,S\_k$ of points and a distance $d$, is there a way to choose one point from each set so that no two points are at distance $\le d$ from each other?

(Each $S\_i$ represents the set of points in a single polygon.) Binary search over $d$ lets you convert any algorithm for the decision problem into an algorithm for your optimization problem.

Now form a graph $G=(V,E)$ where $V=S\_1 \cup \dots \cup S\_k$, and where you have an edge between every pair of points that are at distance $\le d$ from each other. You are looking for an independent set $v\_1,\dots,v\_k$ such that $v\_i \in S\_i$ for all $i$. There are many approaches for solving such a problem.

For instance, you can express it as a SAT instance, and feed the result into a SAT solver. You'll have one boolean variable $v$ for each $v \in V$; if $v$ is set to true, then that means you've included $v$ in your set. Now you have a bunch of clauses of the form $(\neg v \lor \neg w)$ for each pair $(v,w) \in E$, asserting that you don't pick any pair of vertices at distance $\le d$, as well as a clause for each set $S\_i$ asserting that you pick exactly one element of $S\_i$.

Or, you could express it as an integer linear programming instance, and feed the result into an ILP solver. You'll have one zero-one variable $v$ for each $v \in V$; add an inequality $v+w \le 1$ for each pair $(v,w) \in E$, along with an equality $x\_1+x\_2+\dots + x\_j = 1$ where $S\_1=\\{x\_1,\dots,x\_j\\}$ (and similarly for each $S\_i$).

Or you could apply an approximation algorithm for independent set, such as the greedy algorithm based on selecting the minimum degree vertex at each step.

The graph $G$ is a geometric intersection graph, so you might be able to use algorithmic ideas customized for that kind of graph. You'd have to investigate them for yourself and see if they can be applied to your problem.

## Heuristics

One heuristic is to use the Farthest Point First heuristic from clustering. You pick a point arbitrarily, then pick the point that is furthest from it, then pick a third point that is furthest from these two (maximizes the minimum-pairwise-distance), and repeat.

You'll need to adjust it to your setting, to make sure you don't pick two points from the same polygon. There are multiple ways to do that, but one simple one is: if you've already picked some subset of points, then discard any remaining ones that are from the same polygon as one of those, and only consider what's left as a candidate for your next point.

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


# Question
Title: Hamming code -- identical parity bits for different errors
(7,4) Hamming Code (HC) detects all 2-bit errors and corrects all 1-bit errors.

However, there can be 2-, 3- or 4-bit errors that come with the same parity bits as that of 1-bit errors.

Eg.: Let the data be $1011$. So - the parity bits are

$P\_1=0$

$P\_2=1$

$P\_4=0$

, the message transmitted is $0110011$ and the message received is $1000011$.

HC, assuming a 1-bit error, $1000011$ can accurately correct this to the transmitted data, which is $1011$.

But then, suppose the receiver received $1010101$. This has the same parity bits as
$1000011$, and HC, assuming a 1-bit error, would "correct" this as $0101$ which is wrong.

A particular set of parity bits can also hold for 2-, 3- or 4- bit errors.

How does the algorithm handle this?

The possibilities I can think of are:

a.) Takes this as a 1-bit error and just corrects it: in this case, a corrupt bit sequence is transmitted.

b.) corrects it as a 1-bit error, as it does in (a) above, and runs another detection algorithm, say checksum, to make sure.

How does Hamming code work this?

TIA.

# Answer
When we say that a Hamming code detects (up to) 2 errors and can correct 1, we mean just that:

1. There is an error-detection algorithm that returns NO if there are no errors and returns YES if there are one or two errors. There is absolutely no guarantee when there are more errors.
2. There is an error-correction algorithm that gets a possibly corrupted word and outputs the original codeword, **assuming that there was at most one error**. There is absolutely no guarantee when there are more errors.

In real life we cannot always guarantee that there are at most X errors in every block, and this is handled by an "outer code", for example the checksum that you mention.
> 3 votes

# Answer
> there can be 2-, 3- or 4-bit errors that come with the same parity bits as that of 1-bit errors.

When detecting or correcting an error, the entire 7 bit code word is used, not just the 3 parity bits, so it doesn't matter if different error patterns produce the same 3 parity bits, because the other 4 bits will be different.

> the message transmitted is 0110011 and the message received is 1000011.

That's a 3 bit error (the first 3 bits are toggled), and in this case, Hamming code will fail to detect an error, and assume the data is 0011 (instead of 1011).

> How does the algorithm handle this?

It doesn't. If using (7,4) Hamming code for error detection, it's only guaranteed to detect a 1 or 2 bit error, and it will detect most but not all 3 or more bit errors. If using Hamming code for error correction, it can only correct a 1 bit error.

A single bit error correction will always produce a code word that appears to have zero errors, but if there was more than 1 bit in error and a single bit correction is done, the single bit correction results in at least 3 bits in error. For example assume 0000011 is received, and it's a 2 bit error that should have been 0000000. A single bit error correction will produce 1000011, resulting in a 3 bit error that appears to have zero errors.

Wiki article:

http://en.wikipedia.org/wiki/Hamming(7,4)

There are 128 possible 7 bit code words. 16 of these are valid code words that appear to have zero errors. The remaining 112 code words have at least 1 bit in error, and as mentioned in the wiki article, (7,4) Hamming code cannot distinguish between single-bit errors and two-bit errors, and fails to detect some patterns with 3 or more bits in error when they map into a valid code word.

The 16 valid code words that appear to have zero errors, in code word order:

```
data    codeword

0000    0000000
0111    0001111
1110    0010110
1001    0011001
0101    0100101
0010    0101010
1011    0110011
1100    0111100
0011    1000011
0100    1001100
1101    1010101
1010    1011010
0110    1100110
0001    1101001
1000    1110000
1111    1111111

```

In this set of 16 valid code words, 1 has zero bits set, 1 has all seven bits set, 7 have three bits set and 7 have four bits set. In the set of 112 invalid code words, 7 have one bit set, 7 have 6 bits set, 21 have 2 bits set, 21 have 5 bits set, 28 have three bits set, and 28 have four bits set. Note that at least 3 bits have to be toggled to convert from one of the 16 valid code words to another valid code word, this is referred to as the minimum distance which in this case is 3. This is why (7,4) Hamming code can detect 2 bit errors, because no 2 bit error can result in a valid code word.
> 1 votes

---
Tags: computer-networks, coding-theory, error-correcting-codes, hamming-code
---


# Question
Title: Is it possible to shorten this Finite Automata Transition Graph?
I designed this transition graph, seen below. The alphabet contains {a, b, c}, and the goal of this machine is to accept any strings (no limitations on length of string) that ends with a letter that is already in that string.

Example: abba, aaa, bb, ababababacc, cabc are accepted. Example: abc, bccba, a, b, c, cccab, are a rejected.

Is there a shorter/simpler way to design this finite automata than this transition graph?

# Answer
Each string that is input to an automaton takes you to some state. So you can see each state an encoding some kind of information about the inputs the machine has seen if it's in that state. For example, an automaton might have a state that corresponds to "all words with an even number of $b$s."

Why am I telling you this? Because, when you're designing an automaton, it's often helpful to think about what information you need to store about the input to accept the language you want. In this case, you want to accept all words whose last letter has already appeared in the string. So, the information you need to decide the language is "What letters have I seen so far?" If you encode that information in some states of the automaton, it should be easy to add the right transitions to accept the language you want.
> 3 votes

# Answer
When faced with tasks as building an automata it may be sometimes useful to think about decomposing the automata into smaller parts, and then using union or concatenation or repetition to build the whole thing.

For your task, think about a regular expression $(a+b)^\*c(a+b+c)^\*c$ as corresponding to only one of the possible cases, viz. the case which only finds the words having $c$ repeated at least twice. You may use the same idea to construct automata for $a$ and $b$, and then take the union of the three. The resulting graph will be roughly the half of what you have now.
> 1 votes

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


# Question
Title: What does Djikstra mean by "formal techniques" in this essay?
In this essay (and others) by Djikstra, he refers to "formal techniques" a number of times.

> ... for the computing scientist, formal techniques would play a much more important rôle than they had done so far for the mathematician.
>
> ... The practical reason was that formal techniques are indispensable for dealing in a sufficiently trustworthy manner with the type of complexities a program designer has to control.
>
> In our history, the computing scientist seems to be the first to be asked to apply formal logic on a grandiose scale and to make formal techniques an integral part of his daily reasoning; in a way, circumstances have forced him to become more mathematical than the Pope is Roman Catholic.
>
> ... what else can you expect in a world that has never seriously tried to apply formal techniques on a sizeable scale with elegant effectiveness?

I have only a vague idea of what he means by this term (which I'm sure has to do with the context he was writing in in 1985).

Does he mean something like "formal methods" -- proving mathematically that a program you've written is correct? If so, his assertions don't seem very accurate -- we're not doing that on a "sizable scale."

From other essays, I have the idea that perhaps he means "programming in a language with a specified syntax." To my understanding, this would make the third quote make more sense -- his argument is that mathematicians have no syntax their formulas must follow -- but I don't know why this would be called a "technique" or why it would be called "indispensable", as though it's some new technological advance for writing programs. How would programs be written, if not in terms of some strict syntax?

So I'm not sure I get what he's saying.

# Answer
It seems quite clear that Dijkstra did mean what is known today as *formal methods*. He also had the idea that calculations should replace mathematical proof in prose, which you can find in some of the EWDs. It seems that so far his dream hasn't been realized, and while formal methods are used in some extreme circumstances, the average programmer has no use for them.
> 6 votes

---
Tags: history
---


# Question
Title: What does a square mean in a Boolean formula
I am reading the paper *Measuring the hardness of SAT instances* by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF) and I would like to know what the square symbol in the following means

> **Lemma 3** The space satisfies the following three properties:
>
> 1. $s(\Gamma \cup \\{\Box\\})$ = 0
> 2. For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
> 3. For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\\{x\\}\to\\{0,1\\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.
>
> The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3
>
> $$s(\Gamma) = \min\_{x, \overline{x}\in\Gamma, b\in\\{0,1\\}} \big\\{ \max\\{s(\[x\mapsto b\](\Gamma))+1, s(\[x\mapsto\overline{b}\](\Gamma))\\}\\;\big\\}$$ when $\Box\notin\Gamma$, and $s(\Gamma\cup\\{\Box\\}) = 0$.
>
> ---
>
> 3 Note that, since $\Gamma$ is unsatisfiable, it either contains $\Box$ or it contains a variable with both signs.

# Answer
> 5 votes
Ran's comment is correct. This isn't standard notation in proof complexity (the relevant area of TCS), though it might be standard in SAT solving (the relevant applied area). It stands for the *empty disjunction*.

Semantically, the empty disjunction is the same as contradiction, but the former is a *clause* whereas the latter is a *formula* (or sometimes a constant). The usual symbol for contradiction is $\bot$, read *bottom*.

---
Tags: satisfiability
---


# Question
Title: Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity
Problem Statement: Suppose we have a thousands of words and we need to maintain these words in a data structure in such a way that we should be able to find all anagrams for a given string. I tried to achieve this with O(1) complexity.

I am looking for a algorithm to implement above scenario. I implemented this problem with below algo, but I feel that we can improve its complexity. Any suggestion will be helpful.

Algorithm:

Here is trick to utilise hash code, we can also use character histogram.

Step 1:Create an array of prime numbers.

```
   int primes[] = {2, 3, 5, 7, ...};

   We are using prime number to avoid false collisions.

```

Step 2:Create a method to calculate hash code of a word\string.

```
   int getHashCode(String str){
     int hash = 31;
     for(i =0 to length of str){
        hash = hash*primes['a' - str.charAt[i]];
     }
     return hash;
   }

```

Step 3: Now store all words in a HashMap.

```
void loadDictionary(String[] words){

  for( word from words for i = 0 to length of words)   {
     int hash  = getHashCode(word);
     List<String> anagrams = dictionary.get(hash);
     if(anagrams ! = null){
         anagrams.add(word);
     } else
        List<String> newAnagrams = new ArrayList<String>();
        newAnagrams.add(word);
        dictionary.put(hash, newAnagrams);
     }
  }
}

```

Step 4: Now here is the approach to find anagrams:

```
   int findNumberOfAnagrams(String str){
      List<String> anagrams = dictionary.get(getHashCode(str));
      return anagrams.size();
   }

```

# Answer
> 3 votes
You may get some inspiration from the articles The world's fastest scrabble program by Andrew W. Appel and A Faster Scrabble Move Generation Algorithm by Steven A. Gordon. Both algorithms rely on a clever use of finite automata.

See also this question on Stackoverflow.

# Answer
> 2 votes
Use a hash table (python dictionary or equivalent) in which the key is the sorted multiset of letters and the contents is all words composed of these letters.

---
Tags: algorithms, complexity-theory, time-complexity, strings
---


# Question
Title: DFA for at most two $b$'s and at least one $a$
I'm totally new to DFA's and automata in general – this is the first week or two of class that I've actually seen this – and I'm curious as to a pattern to match the following:

"Match the set of all strings on the alphabet $\\{a, b\\}$ that have at most two $b$'s and 1 or more $a$'s."

# Answer
Close your eyes. Tell yourself: I am an automaton.

What is my task? Check whether the number of $a$'s is at most $1$ and the number of $b$'s is at least $2$. So I will count $a$'s and $b$'s. My memory holds two numbers, the respective counts. I start with two zero's. When I see $a$ I add one to the first number, when I read $b$ I add one to the second number.

Ah. When the number of $a$'s reaches $2$ I can stop counting them: my test be be always false. When the number of $b$'s equals $2$ I can stop counting them, I have seen enough of them.

Now open your eyes and write down your state diagram: all possible states (= memory contents) and actions upon reading a letter to another state. Mark the "good" states.

Done.
> 3 votes

# Answer
A standard idiom in situations like this is to use the states to "remember" the number of $a$s and $b$s seen so far, so we can list the states as $s\_{p,q}$, with the interpretation that if you're in state $s\_{p,q}$, then you have seen $p$ $a$s and $q$ $b$s.

Now the $p$ that are of interest to us are $p=0$ and $p\ge 1$. The $p\ge 1$ values are the ones we'll accept. Similarly, the $q$ that are of interest to us are $q=0, 1, 2$ and $q\>2$ and we'll accept $q=0,1, 2$. Combining these, we'll have eight states corresponding to the pairs $$ (0, 0)\quad(0,1)\quad(0, 2)\quad (0, 3^+)\quad(1^+, 0)\quad(1^+,1)\quad(1^+, 2)\quad (1^+, 3^+) $$ where the notation $n^+$ means the relevant variable is greater than or equal to $n$

Since you want to accept strings where the number of $a$s to be greater than or equal to 1 AND the number of $b$s is $0,1,2$ the final states of this FA will be $$ s\_{1^+,0}\quad s\_{1^+,1}\quad s\_{1^+,2} $$ Filling the transitions is easy. For example, in state $s\_{0,2}$ seeing an $a$ the machine will change to $s\_{1,2}$ and seeing a $b$ will change to $s\_{0,3^+}$. Do this for all eight states and you'll have completed the FA.

---

1. This is known as the **Cartesian product** of two finite automata. I didn't come across a good online source for this, but it's in many theory texts.
2. This construction will work for other conditions as well. For instance if you had wanted a machine to accept strings with 1 or more $a$s OR 2 or less $b$s, you'd construct exactly the same FA but the final states would be $$ s\_{0,0}\quad s\_{0,1}\quad s\_{0,2}\quad s\_{1^+,0}\quad s\_{1^+,1}\quad s\_{1^+,2} \quad s\_{1^+,3^+} $$
> 2 votes

# Answer
**Hint**. Try first to find the set $S\_0$ of strings that have no $b$'s and $1$ or more $a$'s, then the set $S\_1$ of strings that have exactly one $b$ and $1$ or more $a$'s and finally the set $S\_2$ of strings that have exactly two $b$'s and $1$ or more $a$'s.

You should be able to find a regular expression for $S\_0$ and $S\_1$ by yourself and this should help you to find one for $S\_2$. The language you are looking for is the union of $S\_0$, $S\_1$ and $S\_2$.
> 1 votes

---
Tags: regular-languages, automata
---


# Question
Title: Continuous Mutual Correction from Multiple Sensors
I'm stumped on what exactly to search for; so here is a non-scientists description of the topic.

I've got multiple sensors of different types that are measuring the same physical value in different ways. The sensors are all subject to significant error or temporary unavailability, but in greatly different ways. I want to develop code that can use all available sensor data by maintaining slowly changing corrections for each sensor based on the other.

I would love guidance on what exactly to look for to begin a literature search on the topic. Thanks.

---

Notes based on comments:

* A silly example would be collection sampled data on an instrumented automobile's scalar velocity from:
    + wheel rotation frequency sensor
    + pitot type anemometer
    + tri-cup anemometer
    + MEMS accelerometer
    + GPS
* The physical value being measured, the signal, is not periodic or in any way predictable. It ranges from 0.0 to Max, where max is greater than zero and noninfinite. It is relatively easy to define reasonable limits for max\_value, max\_delta\_value and so on be observation and calculation from simplified Newtonian models.
* At least one sensor is subject to calibration/bias drift continuously. This should be at least 4 orders of magnitude below reported value, but in nonnegligible.
* At least one sensor is unbiased, calibrated and provides confidence range data along with sample data. Per sample error can be as much as 2 orders of magnitude greater than sample value.
* All sensors use wireless communications of data, so all samples are not reported. No error in measurement is introduced in transmission.

# Answer
The broad area that studies these kinds of topics is called estimation theory. This is more a matter of statistics than of computer science, so you might want to take a look in some statistics textbooks and check out the Statistics.SE.

For instance, you might be interested in the Kalman filter.

That said, before one can devise a solution to your specific solution, we'd need a lot more information about what you know. Do you know anything about the joint distribution of their sensing? Do you know anything about the accuracy of each sensor (e.g., its variance)? Are all sensors calibrated and unbiased? Do you know anything about how the underlying physical value changes over time or the distribution it comes from? Do some self-study of the literature, and make sure you know the answers to those before asking on Stats.SE.
> 2 votes

# Answer
The Extended Kalman filter is probably exactly what you are looking for.

Basically, the Extended Kalman filter *leverages* the mathematical model of your system to come up with a **very** computationally efficient method of sensor data fusion.

For example, EKF can be used to quite accurately estimate a vehicle's position, orientation, and speed, from a single noisy GPS sensor! (But adding more sensors improves accuracy.) The trick is, by doing a bit of calculus on the equations of motion, and incorporating the standard deviation of your sensors, you come up with a few simple matrix calculatons that update all the estimated variables accordingly.

You can certainly have the offset/bias of a sensor as one of the estimated variables, and in this way the bias will be estimated and corrected.

Basically, this is how to implement the EKF:

1. Choose your state variables (what is to be estimated)
2. Mathematically formulate your state update (given current state, what is the predicted state in *t* seconds)
3. Mathematically formulate your observations (given current state, what is the predicted data given by a sensor)
4. Evaluate the uncertainty (standard deviation) for your state update and observation
5. Do calculus and crunch numbers according to the method of EKF
6. Use the results of step 5 to implement a software algorithm

Hopefully this will help put some of the literature into context. EKF is a fantastic piece of mathematics, and not that difficult to put into practice, but much of the literature is very dense. However, more accessible introductions to it are appearing, for instance this one.
> 2 votes

---
Tags: algorithms, signal-processing
---


# Question
Title: Connected Graph: Select the minimum number of nodes such that the node and neighbor covers everything
The problem is to select the minimum number of nodes from a graph such that, the selected nodes and their neighbors consists of all the nodes of the graph.

Any straight forward algorithm for this? Repeatedly selecting the node with highest degree centrality doesn't work.

Thank you.

# Answer
This depends on what you mean by "straight forward". There's a very straight forward brute force algorithm - it just doesn't have very good performance.

As to which problem this is, I would say it is Dominating Set. A vertex cover is also a dominating set, but not every dominating set is a vertex cover (i.e. a vertex cover might be significantly larger than a dominating set).

As for straight forward algorithms with good performance, you're not in a good spot.

* It is NP-complete, so no polynomial-time algorithm unless $P = NP$.
* It is $W\[2\]$-complete, so no $FPT$-algorithm unless $W\[2\] = FPT$.
* It has no $n^{o(k)}$ algorithm unless the Exponential Time Hypothesis fails.
* It is also $Log$-$APX$-complete, so no $o(\log n)$ approximation algorithm unless $P = NP$.

The best algorithm I know of at the moment is a $O(1.4969^{n})$ exact algorithm, but I don't think that would satisfy the "straight forward" criterion.

Even on restricted classes of graphs, you're unlikely to get good running times.

If you graphs happen to have very small treewidth, local treewidth, or are planar, then there are FPT algorithms, but again, they're not exactly "straight forward".

If you do want to solve Vertex Cover however, then it's still hard, but you have a few more possibilities:

* Vertex Cover has a 2-approximation (find any maximal matching, and take all the vertices in the matching).
* Vertex Cover is FPT, and has a number of kernelization algorithms of varying complexity (the more complex ones give significantly better running times). This paper contains details on a relatively simple one and this one the current best.
* It is also amenable to a number of optimization approaches, and if you have access too something like CPLEX, then the ILP is easy to formulate, and relatively fast to solve.
> 5 votes

---
Tags: graphs
---


title: Fast comparison with a tolerance

text:
# Question
Title: Fast comparison with a tolerance
I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$.

I want to do this by replacing the numbers by a discrete key computed on them in such a way that when two keys differ, they map two significantly distant numbers.

$$K(r)\ne K(s)\implies |r-s|\ge 1.$$

The converse,

$$K(r)=K(s)\implies |r-s|\<1.$$

may only partially hold, but should be false in a minority of the cases. ($K(r):=0$ is indeed a trivial solution to the first requirement, but is of no use because of the second.)

In my context (database search), the key being *discrete* and a *single* comparison for *equality* being sufficient are essential properties.

The first idea that come to mind is simple rounding, or equivalently, flooring, i.e.

$$K(r):=\lfloor r\rfloor.$$

Anyway this doesn't work as all values in range $\[r,r+1)$ map to $K(r)$; the values $1$ unit away from these span $(r-1,r+2)$, which maps to one of $r-1,r,r+1$. So you would need a triple equality test

$$|r-s|\<1\implies \lfloor r\rfloor=\lfloor s\rfloor-1\lor \lfloor r\rfloor=\lfloor s\rfloor\lor \lfloor r\rfloor=\lfloor s\rfloor+1.$$

If I am right, the reasoning can be extended to any function $K$: the numbers that map to $K(r)$ are in the set $K^{-1}(K(r))$; the numbers one unit away are in the Minkowski sum $K^{-1}(K(r)) + (0,1)$, which cannot be covered by a single $K^{-1}(K(s))$.

I can also accept a scheme where the key function is computed differently for $s$, but the single comparison principle must remain

$$K(r)\ne L(s)\implies |r-s|\ge 1.$$

Is this a known problem ? Is there a solution or a workaround ?

**Update**: the problem statement was reformulated in the original text.

# Answer
> 4 votes
If for all $|r - s| \< 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise).

What you are asking is impossible.

One thing which is possible is to compare keys with three rather than two possible outcomes:

1. If $K(r)$ is close to $K(s)$ then $|r - s| \< 1$.
2. If $K(r)$ is far from $K(s)$ then $|r - s| \geq 1$.
3. Otherwise, we don't know.

Of course, the aim is that the third case happens as rarely as possible. One simple way to achieve this is to choose a random $x$ and some small (non-random) $\epsilon \> 0$, and to use $$ K(r) = \lfloor r/\epsilon + x \rfloor. $$ Under this definition, the only uncertainty is for $r,s$ at distance $(1-\epsilon,1+\epsilon)$. The random component mitigates even this uncertainty, albeit only by a little.

# Answer
> 2 votes
The second variant isn't much better: $\forall s,r: |r-s| \< 1 \Rightarrow K(r) = L(s)$ implies that $\forall r: K(r) = L(r)$, as $r = s$ is only a special case. On the other hand, you are down to two comparisons:

$K(x) := \lfloor 0.5\cdot r + 0.5 \rfloor \\ L(s) := \lfloor 0.5\cdot s \rfloor \\ \forall r,s: |r-s|\<1 \Rightarrow K(r) = L(s) \lor K(r) = L(s) + 1$

If you are trying to build an index by hashing these keys, two lookups or double the space might be good enough.

# Answer
> 2 votes
As others have said, what you want is impossible.

But you might want to look at locality-sensitive hashing. It achieves something vaguely similar: if two elements are similar, then with significant probability they will have the same hash.

It is possible to amplify the probability by hashing with multiple independent hash functions. With high probability, at least one of the hashes will have the property that the two elements have the same hash.

This may or may not be adequate for your application, but it's worth knowing about.

---
Tags: algorithms, comparison, search, hashing
---


# Question
Title: Does a do-while loop suffice for Turing-completeness?
I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need unbounded memory and certain operators...). The gist of my question is: does a do-while loop have the same computational power as a while-do loop? In other words, can a language be Turing-complete if it's impossible to skip instructions entirely.

I realise that some of the semantics here could be a bit ambiguous, so let me phrase the actual question with a specific example:

Brainfuck (BF) is a Turing tarpit where the only control flow is a while-do loop, denoted as `[...]` (there is a complete language spec at the bottom of the question, in case you're not familiar with Brainfuck). Let's define a new language BF\*, where `,.+-<>` have the same semantics as in BF, but instead of `[]` we have `{}` which denotes a do-while loop. That is, the only difference to BF is that every loop is executed at least once before further iterations can be skipped.

**Is BF\* Turing-complete?** If it is, I'd be interested in how I could translate BF to BF\*. If it isn't, how do I prove that?

Some observations of my own:

* Not every BF program can be translated into BF\*. For instance, it's impossible to write a program in BF\* which may or may not read or print a value - if the program potentially prints one or more values, it will always print at least one. However, there might be a Turing-complete subset of BF which can be translated to BF\*.
* We cannot simply translate `[f]` (where `f` is some arbitrary, Brainfuck program consisting only of `+-[]<>`) to `f<sup>-1</sup>{f}` (in an attempt to cancel the effect of the first iteration), because a) not every computable function has a computable inverse and b) even if it did, `f<sup>-1</sup>` wouldn't necessarily have fewer loops than `f` so applying this step recursively isn't guaranteed to terminate in the first place.

---

Here is a quick overview over the Brainfuck language. Brainfuck operates on an infinite tape where each cell contains a byte values, initially zero. Overflows wrap around, so incrementing 255 gives 0 and vice versa. The language consists of 8 instructions:

```
+   Increment the current cell.
-   Decrement the current cell.
>   Move tape head to the right.
<   Move tape head to the left.
,   Input a character from STDIN into the current cell.
.   Output the current cell as a character to STDOUT.
[   If the current cell is zero, jump past the matching ].
]   If the current cell is non-zero, jump back to just behind the matching [.

```

# Answer
> 10 votes
I don't know Brainfuck so you'll have to do some translation from my pseudocode. But, assuming that Brainfuck behaves sensibly (ha!), everything below should apply.

do-while is equivalent to while-do. `do X while Y` is equivalent to `X; while Y do X` and, assuming you have conditionals, `while Y do X` is equivalent to `if Y then (do X while Y)`.

Life is a bit harder if you don't have conditionals. If you have while-do, you can simulate `if Y then X` using something like this:

```
B := true
while (Y and B) do
    X
    B := false
endwhile

```

But what if you only have do-while? I claim that the following simulates `if Y then X`, assuming that `X` terminates given the current value of the variables. (This isn't guaranteed: the program `if y=0 then loopforever` terminates if `y != 0`, even though `X` loops for any value of the variables). Let `V1`, ..., `Vn` be the variables modified by `X` and let `X'` be `X` modified so that it uses `Vi'` instead of `Vi` for each of those variables. `swap(A,B)` denotes the obvious code that swaps the variables `A` and `B`.

```
V1' := V1; ...; Vn' := Vn
V1'' := V1; ...; Vn'' := Vn
C := 0
do
    X'
    swap (V1',V1''); ...; swap (Vn',Vn'')
    C := C+1
while Y and C<2
V1 := V1'; ...; Vn := Vn'

```

The idea is the following. First, suppose that `Y` is false. We simulate doing `X` once, and store the results in `V1''`, ..., `Vn''`; `V1'`, ..., `Vn'` hold the original values of `V1`, ..., `Vn`. Then, we assign `V1 := V1'; ...; Vn := Vn'`, which does nothing. So, if `Y` is false, we've done nothing. Now, suppose that `Y` is true. We'll now simulate `X` *twice*, storing the results in both the "primed" and "double-primed" variables. So, now, the assignments at the end of the loop have the effect that `X` was computed once. Note that `Y` only depends on the "unprimed" variables, so its value is not affected by running the loop repeatedly.

OK, so what if `X` might not terminate for the current value of the variables? (Thanks to Martin Ender for pointing out this possibility.) In that case, we need to simulate `X` instruction-by-instruction, using similar ideas to those above. Each instruction definitely terminates so we can use the `if` simulation above to do instruction decoding, along the lines of "If the opcode is foo, do this; if it's bar, do that; ...". So, now, we use a loop to iterate through the instructions of `X`, using an instruction pointer and so on so that we know which instruction to execute next. At the end of each iteration of the loop, check `Y` and check whether `X` has halted yet. If `Y` is false, the swapping technique allows us to undo the effects of `X`'s first instruction.

---
Tags: programming-languages, turing-completeness, loops, imperative-programming
---


# Question
Title: Is this algorithm actually a graph-traversal algorithm?
I was given in a lecture the following algorithm that wwas said to be a graph-traversal algorithm.

# The algorithm given during the lecture

## The algorithm

```
EXPLORE (s:sommet, D:list of the following vertices of the vertices ahead,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    Else LIST←LIST-{i}

PARCOURS(D: list of the out-going vertices or ahead vertices)
for all vertex x in X
     {visited [x]<-false}
for all x in X
    if not visited [x]
    EXPLORE(x,D,M or visited)

```

## the example I tried

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline X1 & X2,X4 \\ X2 & X1,X3\\ X3 & X4,X5 \\ X4 & X6,X7 \\ X5 & X2,X6 \\ X6 & X4,X7 \\ X7 & \emptyset \\ \end{array}

I assume that this is the list (tell me if you think this is not the case).

Select 1 $\in$ LIST

LIST(1)=X2,X4 $\not= \emptyset$

X2 $\in$ LISTE(1) is not visited, so we change visited to true X4 $\in$ LISTE(1) is not visited, so we change visited\[4\] to true no more elements are not visited, we do LISTE \<-LISTE-(1)

the array-list thus becomes:

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline X2 & \not X1,X3\\ X3 & X4,X5 \\ X4 & X6,X7 \\ X5 & X2,X6 \\ X6 & X4,X7 \\ X7 & \emptyset \\ \end{array}

And I can plot $X1$

Then I do the algorithm again

Select 1 $\in$ LIST

LIST(2)=X3 $\not= \emptyset$

X3 $\in$ LISTE(2) is not visited, so we change visited$\[3\]$ to true no more elements are not visited, we do LISTE \<-LISTE-(2)

the array-list thus becomes:

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline X3 & X4,X5 \\ X4 & X6,X7 \\ X5 & \not X2,X6 \\ X6 & X4,X7 \\ X7 & \emptyset \\ \end{array}

I can plot anew:

**Then I'm not sure wether to SELECT X4 or X3**. It seems that it is the whole difference between *Depth-first search* algorithm and *Breadth-first search* ones.

I think this the way the first part of this algorithm run, yet I'm not sure on how does the second partt works. It seems that it allows to explores every paths in my mere opinion...

# The algorithm given by a friend of mine

Yet, a friend of mine just wrote the following one rather shorter to do the same thing:

```
EXPLORE (s:sommet, D:list of the following vertices of the vertices ahead,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    LIST←LIST+{j};
    Else LIST←LIST-{i}

```

I don't understand how the first one is a graph traversal algorithm and I wonder if it is the best one as far as it seems that the second one is shorter, (but unclearly to me actually).

# Answer
> 1 votes
There seems to be a bug in the first algorithm which is fixed in the second algorithm, namely the first EXPLORE explores only the starting vertex and its neighbors, but nothing beyond that. However, the first algorithm at least explores the entire graph; the second one only explores the connected component of $s$. The second one also doesn't bother to initialize the array `visited`.

I strongly suggest that you try and understand what these algorithms are doing. It could help running them manually on a few examples. You could also program them and have the programs print out the actions performed by the algorithms.

---
Tags: algorithms, graphs, runtime-analysis
---


# Question
Title: Measuring the hardness of SAT instances Lemma
I am reading the paper *Measuring the hardness of SAT instances* by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF).I have two questions the first one is I would like to undersatnd the demonstration for the last claim. Specifically I need an example of the proof tree of $\[x\rightarrow b\](\Gamma)\vdash \\{\Box\\}$. And the second one is I would like an example of the last part of the Lemma 3, that is an example of the definition $s(\Gamma)$.

> **Lemma 3** The space satisfies the following three properties:
>
> 1. $s(\Gamma \cup \\{\Box\\})$ = 0
> 2. For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
> 3. For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\\{x\\}\to\\{0,1\\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.
>
> The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3
>
> **$$s(\Gamma) = \min\_{x, \overline{x}\in\Gamma, b\in\\{0,1\\}} \big\\{ \max\\{s(\[x\mapsto b\](\Gamma))+1, s(\[x\mapsto\overline{b}\](\Gamma))\\}\\;\big\\}$$** when $\Box\notin\Gamma$, and $s(\Gamma\cup\\{\Box\\}) = 0$.
>
> ---
>
> 3 Note that, since $\Gamma$ is unsatisfiable, it either contains $\Box$ or it contains a variable with both signs.

I trying to understand the proof of that Lemma using this UNSAT formula: $\Gamma = (a+b)(a+b')(a'+c)(a'+c')$. Specifically, in this point: "From the proof tree of $\[x \rightarrow b\](\Gamma) \vdash\\{\Box\\}$ , adding the literal $x'$ in the clauses where $\[x \rightarrow b\]$ has removed it, but preserving the structure of the proof tree, we get a proof of $\Gamma \vdash x'$". I consider $x=a=1$ then replacing $a'$ in the formula $\[a\rightarrow 1\](\Gamma)$ I get $(a'+b)(a'+b')(a+c)(a+c')$ that also by resolution is $\\{\Box\\}$. What is wrong in my example How Do I get $\Gamma \vdash x'$?

\*$\\{\Box\\}$ means the empty clause

# Answer
First, $\[a\to 1\]\Gamma = (1)(1)(c)(c')$. A refutation of this consists of resolving $c$ and $c'$. Following the proof, we reinstate $a'$ to get the CNF $(1)(1)(a'+c)(a'+c')$, and then resolve $a'+c$ and $a'+c'$ to get $a'$.

Similarly, $\[a\to 0\]\Gamma = (b)(b')(1)(1)$, which can be refuted by resolving $b$ and $b'$. Reinstating $a$, we get $(a+b)(a+b')(1)(1)$, and resolving $a+b$ and $a+b'$ we get $a$.

Note that your notation, which is different from the paper's, is confusing you. For example, $x'$ is not the negation of $x$ but rather a new variable symbol.
> 2 votes

---
Tags: satisfiability
---


# Question
Title: Understanding multi-variable big O (time complexity)
I have something of this kind:

$$(n-1) d m + m + 2m\*v+2v^2 + v$$

Where all n,d,m,v are variables.

My little knowledge of computational complexity leads to do this kind of approximation:

$$ O( (n-1) d m + mv + v^2 )$$

However I feel I could further simplify into

$$ O( n d m + mv + v^2 )$$

and

$$ O( n d m + v^2 )$$

hence

$$ O(v^2)$$

Are my assumptions correct?

* can I remove the $-1$ from $(n-1)$?
* can I remove $mv$ since $v$ will grow $v^2$ any way?

# Answer
> 6 votes
You can remove the $-1$ from $(n-1)$, since $(n-1)dm=ndm-dm\leq ndm$. On the other hand, you can not simplify beyond $O(ndm+mv+v^2)$ unless you know more about the relations between the variables. $mv$ and $v^2$ are incomparable, depending on the ratio between $m$ and $v$ one may grow faster than the other. Similarly, your last step (removing $ndm$ in favor of $v^2$) is also incorrect.

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


title: Recursive function problem

text:
# Question
Title: Recursive function problem
This might seem very simple but it's been giving me lots of headaches.

For example if I run f(12345) the result is 5310135.

I understand why it would return 5310, the rest of 135 is what is giving me troubles. Sorry if the question sounds dumb, I am a newbie seeking for help:).

```
function f (integer n)
{
    print n%10;
    if (n!=0)
    {
        f(n/100);
        print n%10;
    }
}

```

# Answer
> 3 votes
You missed the second print instruction.

We can rephrase the algorithm as follows:

```
function f (integer n) {
  if n equals 0 {
    print 0
  } else {
    print n % 10
    f(n/100)
    print n % 10
  }

```

Now we can do "recursion unrolling":

```
function f (integer n) {
  if n equals 0 {
    print 0
  } else {
    print n % 10
    if n/100 equals 0 {
      print 0
    } else {
      print (n/100) % 10
      f(n/10000)
      print (n/100) % 10
    }
    print n % 10
  }

```

One more level:

```
function f (integer n) {
  if n equals 0 {
    print 0
  } else {
    print n % 10
    if n/100 equals 0 {
      print 0
    } else {
      print (n/100) % 10
      if n/10000 equals 0 {
        print 0
      } else {
        print (n/10000) % 10
        f(n/1000000)
        print (n/10000) % 10
      }
      print (n/100) % 10
    }
    print n % 10
  }

```

Suppose for the moment that all of `n`, `n/100`, `n/10000` differ from zero. The executed code is then

```
print n % 10
print (n/100) % 10
print (n/10000) % 10
f(n/1000000)
print (n/10000) % 10
print (n/100) % 10
print n % 10

```

Hopefully you can see the pattern.

The printed string is always an odd-length palindrome with a `0` in the middle, a property which you can prove by induction.

# Answer
> 2 votes
Don't think in terms of "stack levels" or such for recursive functions. Say you have:

```
f(n)
{
   /* do something */
   g(n - 1);
   /* more stuff */
}

```

if you call `f(n)` you expect `something` done, then `g(n - 1)` is completely worked through, and finally comes `more stuff`. If `f` and `g` happen to be different or the same function is irrelevant, it is done the exact same way. And the only sane way to understand recursive functions is as above: When hitting a recursive call, just assume (for now) that `f` does it's work correctly in the recursive call, and that under that condition the body of the function does it's job correctly. You have to reason separately that there are conditions under which there are no further recursive calls (and the results in those cases are right), and that recursive calls get you somehow "closer" to those base cases. Exactly the same way you reason if `f` and `g` are different, you analyse the called function separately.

# Answer
> 2 votes
The following gets executed:

```
f(12345)
│   print 12345 % 10
│   f(123)
│   │   print 123 % 10
│   │   f(1)
│   │   │   print 1 % 10
│   │   │   f(0)
│   │   │   └   print 0 % 10
│   │   └   print 1 % 10
│   └   print 123 % 10
└   print 12345 % 10

```

The function prints every other digit (units included) in reverse order, then `0`, then these digits in direct order: `12345 -> 1 3 5 -> 531 0 135`.

---
Tags: algorithms, recursion
---


title: Read After Write(RAW) hazard

text:
# Question
Title: Read After Write(RAW) hazard
I am confused in finding RAW dependencies whether we have to find only in adjacent instructions or non-adjacent also.

consider the following assembly code

I1: ADD R1 , R2, R2;

I2: ADD R3, R2, R1;

I3: SUB R4, R1 , R5;

I4: ADD R3, R3, R4;

FIND THE NUMBER OF READ AFTER WRITE(RAW) DEPENDENCIES IN THE Above Code.

I am getting 2 dependency I2-I1 and I4-I3.

# Answer
> 1 votes
Adjacency is not relevant for determining Read-After-Write dependences. You simply list *all* the instructions where one of the source registers reads the value produced by some previous instruction.

So (assuming that your assembly language is `OPERATOR DEST SRC1 SRC2`) you are missing, for example, that the first source operand of `I3` dependends on the value written by `I1`. (You are missing several others as well.)

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: How can can I find out if the two disks intersect in the plane?
. Imagine two disks on the xy plane. Each disk is represented by three numbers (the radius, the x coordinate of the center and the y coordinate of the center). All values for this problem are real numbers. Your task is to determine if the two disks intersect.

# Answer
> 4 votes
I am not sure if I should answer such a question, but here we go:

Let the first disk be $D\_1 = \langle R\_1, (x\_1, y\_1)\rangle$ and the second disk be $D\_2 = \langle R\_2, (x\_2, y\_2)\rangle$, where $R\_1$ and $R\_2$ is the radius of the first and second disk respectively, as well as $(x\_1, y\_1)$ and $(x\_2, y\_2)$ is the center of the first and second disk respectively. Further, let $d$ be the distance of the two centers; that is, $$d = \sqrt{(x\_2 - x\_1)^2 + (y\_2 - y\_1)^2}.$$ Then, the two disks intersect if $$d \leq R\_1 + R\_2$$ and do not intersect otherwise.

Note that if $d = R\_1 + R\_2$, then the two disks have only one point in common.

---
Tags: algorithms
---


# Question
Title: Does this Turing Machine M decide the language of polynomials?
Does this Turing Machine decide language of polynomials with integer coefficients which have integer roots: The input represents a polynomial over variables x1, . . . , xn with integer coefficients.
1. Examine all possible integer values of x1, . . . , xn.
2. Evaluate the polynomial on all of them.
3. If any of them evaluates to 0, accept; else reject

From what I know I would say No, since: "M decides a language L iff M accepts all strings in L and reject all strings not in L ". Where L is the language of polynomials. Is this correct?
Any help is appreciated!

# Answer
> 1 votes
The problem with this algorithm is that it never terminates when the polynomial has no integer roots. Its semantics are:

* If the input polynomial is in $L$, the machine halts and answers YES.
* If the input polynomial is not in $L$, the machine never halts.

The semantics we are after are a bit different:

* If the input polynomial is in $L$, the machine halts and answers YES.
* If the input polynomial is not in $L$, the machine halts and answers NO.

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


# Question
Title: How to categorize an undirected triangular graph with top, bottom, and intertwining paths
**Background**:
I worked on finding the maximum path from the top to the bottom of a tree-like graph. During the process I found that the algorithm for finding the maximum path from the top to bottom of a binary tree also worked for my graph. My problem arose when trying to name the program, because the graph it works on is clearly not a binary tree.

**The problem**:
My graph looks like this:
·······a······
······/··\·····
·····b···c····
····/··\··/··\···
···d···e····f··
··/··\·/··\··/··\·
g····h····i····j
Due to that all the inner nodes at lower levels have multiple "parents" from the level above, it cannot be classified as a binary tree. From the perspective of finding the maximum path from the top to the bottom, it could be classified as a DAG, but because there strictly are no directed edges in the input graph, this also seems wrong. If presented in the following way:
a - c - f - j
|····|····|·
b - e - i
|····|·
d - h
|··
g
It could be argued that it is a lattice graph. But that would conceal that it has a defined "top" and "bottom", and that I have worked with a root and leaves. One could always fall back to calling it a general graph I guess, but that would conceal that it follows a very rigid structure.

**My question**:
What should I call this bastard that can be processed by many of the algorithms applied to binary trees but violates some of the properties of trees, for the sake of my problem can be considered a DAG but has no directed edges, and somehow resembles a lattice?

# Answer
Your algorithm relies on some properties of the input graph for its correctness. You should isolate these properties, and then you will know how to name your program.

The most likely answer is that your algorithms works on DAGs oriented source-to-sink, as you and David mention. However, there are many possible variants:

1. Your algorithm might rely on the DAG having a single source.
2. Your algorithm might rely on the outdegree being at most 2 or perhaps exactly 0 or 2.
3. Your algorithm might work on every (possibly connected) graph, implicitly considering say the BFS tree (or forest) of the graph, from a given starting node.

Only you can tell which of these is correct for your algorithm.
> 1 votes

---
Tags: graphs
---


# Question
Title: What happens if we expand the alphabet of a given Turing Machine?
If we expanded the alphabet Sigma = { 0, 1, u, \> } to Sigma' = { 0, 1, 2, u, \> }. How would the table change? We're just learning about Turing Machines in class and I'm a bit confused. Is the table in the picture calculated in some way?

# Answer
That’s a table of transitions, and it determines what the program does when it encounters a given symbol on its tape while in a given state. This program, if I’m reading it right, accepts strings containing two consecutive 1 symbols before the first space.

If there were another symbol, it would be necessary to define what the program would do on encountering them. For example, to ignore them, there would be a pair of transitions saying that, if the program is in state s1 and reads a 2, it should stay in state s1 and move to the right, and that if it is in state s2 and reads a 2, it should stay in state s2 and move to the right.
> 4 votes

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


# Question
Title: Subgraph of an interprocedural control flow graph
Say I have the interprocedural control flow graph (ICFG) of a program.

Now I am only interested in the control flow between two functions f1 and f2.

* What is the most straight-forward way to remove the non-relevant part of the ICFG?
* Is there a standard performance-optimized algorithm for this task?
* Does the result, that is, the interprocedural control flow "subgraph", have a special name?

I guess it would not be appropriate to call this a "slice" because its creation is based on the control flow graph reachability but not on data dependency relations. But I am not 100% sure.

**EDIT:**

I have to clarify: I am interested in the control flow starting at function f1, optionally passing via other functions, but eventually ending at function f2. In other words, the subgraph that contains all paths in the ICFG whose start node is f1 and whose end node is f2. This also includes paths with other nodes in between f1 and f2. Sorry in case my first explanation was not clear enough.

# Answer
> 2 votes
You are asking several questions. Here are answers to some of them. Your process is obtained by contracting all vertices not belonging to $f\_1,f\_2$, a process which is similar to the process of contracting edges in the definition of graph minors (though your graph is directed). Semantically, you can produce the graph by repeatedly performing the following contracting procedure for each vertex $v$ which is not $f\_1,f\_2$:

> Let $(x\_i,v)$ be all the incoming edges, and $(v,y\_j)$ all the outgoing edges. Delete $v$ and replaces the edges adjacent to $v$ by the edges $(x\_i,y\_j)$ for all $i,j$.

I don't know what is the most efficient implementation of this process, though I suspect you could find it in the literature once you determine what this operation is known as.

---
Tags: terminology, graphs, programming-languages, compilers
---


# Question
Title: Why does an admissible heuristic mean A* is optimal?
An admissible heuristic never overestimates the cost to reach the goal. **However**, isn't that only the relative difference between heuristics for two different paths matter?

Say we have optimal path A (cost 100 to reach goal) and sub-optimal path Z (cost 120 to reach goal). Even if the heuristic is admissible, say it gives A a heuristic of cost 99 while it gives Z a heuristic of cost 10.

In both cases, the heuristic is admissible since it's lower than the actual cost it'll take to reach the goal, but still under this, **Z is optimal** since the heuristic gives a cost of 10 to Z and a cost of 99 to A.

It seems to me then it doesn't even matter that the heuristic is admissible. You still get the suboptimal solution.

What am I missing?

# Answer
## With an admissible heuristic

The heuristic defines which nodes will be explored first, but does not change the final path found.

In your example, the heuristic will cause the path to Z to be explored first. The algorithm will discover the true (expensive) cost of 120. Then it will decide to explore the A path and discover the optimal route.

A better heuristic would guess A was the way to go immediately, find the cost of 100, and never bother exploring Z at all (e.g. if the heuristic said the cost was greater than 100).

So the heuristic changes the execution time, but not the final answer.

## With an unadmissable heuristic

If the heuristic marked A as costing 130 (when the true cost is 100), it may find the route to Z (true cost 120), and instantly stop (because it "knows" the cost to A is at least 130), so return the wrong answer.
> 6 votes

# Answer
A\* does not guarantee to find optimal path to nodes with `h(v) > 0`. It only guarantees to find the optimal route to the target node, with `h(v) = 0`. In the process of doing so, it will find optimal path to many nodes along the way, but not all of them.
> 1 votes

---
Tags: search, artificial-intelligence
---


# Question
Title: How to prove universality in complex systems?
I'm working on my graduation project for CS, which is about cellular automata. Recently, i was able to build a system where the input is transferred to multiple different structures at once. The input consists of numbers, a sequence of numbers ranges from (-infnite to infinite), like ('5','65443'or'9921075').

From the sequence of numbers {input}, i can see each number's behavior and how it interacts with other numbers by analysing the different structures it outputs, it is like a Cellular Automaton structure simulates another Cellular Automaton structure.

How can i relate these properties to universality, What should i look for or analyze in these structures to show universality?

# Answer
In order to show that your computation model is universal, you have to show that you can implement every computable function in your model. You do this by picking some other computation model $M$ and showing how to simulate $M$ in your model. For somewhat more formal definitions, see this answer.

As stated, this sounds difficult, and the first step is to look at various proofs of universality to get some ideas of what is involved. Some examples are listed in the Wikipedia article. It's possible that your model can easily simulate one of the simpler computation models such as counter machines, and this is perhaps the first thing to check.

It is also possible that your model is not Turing-complete but is still quite strong, say PSPACE-complete or EXPTIME-complete.
> 6 votes

# Answer
Proving arbitrary CAs are universal in some sense is one of the hardest problems in CS/mathematics, and is probably about as hard as the Busy Beaver problem or nearly equivalent to the halting problem. Depending on scope this may be outside the range of an undergraduate research project.

Some sense of this can be understood by looking at Mathew Cooks very ingenious 40 page proof of the universality of rule 110. The rule was conjectured to be universal for many years before the proof was discovered. The proof uses tag systems which are used in other CA-TM equivalence constructions.

Eric Weisstein has a basic survey/collection of references on this Mathworld. Note, that study of this problem goes back decades, eg to Von Neumann. Another famous proof is with the Game of Life by Conway.

Another case study is the Wolfram $25K prize for 2,3 machine universality.
> 2 votes

---
Tags: computability, computation-models, cellular-automata
---


# Question
Title: What is the point of an active shape model in facial recognition?
From what I understood, the Active Shape Model (ASM) is used in facial recognition. I figured out how the ASM works but I don't get why we use it.

How this shape is suppose to be interpreted for facial recognition? Should it be compared directly to the database?

I have read many research papers about ASM and facial recognition but none of them explains the point of it.

# Answer
The active shape model algorithm is used to locate precisely the eyes, eyebrows, nose and mouth of a person. It is also used to align faces that are tilted. It is not used directly for face matching and it has nothing to do with databases. It is a preprocessing step. You (I) will need another algorithm to match its result with a database. (ICA for example)
> 4 votes

---
Tags: algorithms, computer-vision
---


title: Average-case analysis help

text:
# Question
Title: Average-case analysis help
I am stuck on trying to understand how to solve the following question. Could someone please explain for a beginner to average-case analysis?

Considering the following algorithm A which takes as input a bit string b = b\_1, b\_2, ... , b\_n (each b\_i is either 0 or 1) and does the following:

```
A(b,n)
k = 0
FOR i = 1 TO n DO
    IF b_i = 1 THEN
        k = k + 1
j = k mod 2
IF j = 1 THEN
    FOR i = 1 TO k DO
        PRINT("Hello World")

```

Assuming each string is bit string b is equally likely, what is the average number of "Hello Worlds" that A will print?

The hint I have so far is I need to express the sum directly on the sample space, where $X$ below represents the number of times "Hello World" is printed, and depends on individual inputs. $$ E(X) = \sum\_{L \in S\_n} X(L) \cdot Pr(L) $$

# Answer
You haven't stated what the distribution of the initial vector is. I'm assuming that each $b\_i$ is independently set to $0$ or $1$ with equal probability.

The first step is to find a formula for the expectation $E$. Let $k$ be the value of $k$, that is, the number of 1s in the vector. We know that $k$ has binomial distribution $\mathrm{Bin}(n,1/2)$. Then $$ E = \sum\_{\ell\text{ odd}} \Pr\[k=\ell\] \ell = \sum\_{\ell\text{ odd}} 2^{-n} \binom{n}{\ell} \ell. $$ A good idea now is to use the binomial identity $\binom{n}{\ell}\ell = \binom{n-1}{\ell-1}n$: $$ E = \frac{n}{2^n} \sum\_{\ell\text{ odd}} \binom{n-1}{\ell-1} = \frac{n}{2^n} \sum\_{r\text{ even}} \binom{n-1}{r}. $$ When $n$ is even, the binomial identity $\binom{n-1}{r} = \binom{n-1}{n-1-r}$ implies that $$ \sum\_{r\text{ even}} \binom{n-1}{r} = \frac{1}{2} \sum\_{r\text{ even}} \left\[\binom{n-1}{r} + \binom{n-1}{n-1-r}\right\] = \frac{1}{2} \sum\_r \binom{n-1}{r} = \frac{1}{2} \cdot 2^{n-1}, $$ and so $$ E = \frac{n}{2^n} \cdot 2^{n-2} = \frac{n}{4}. $$ I'll leave you the case of $n$ odd (you get the same answer, but a different trick has to be used).

The answer $n/4$ is what we expect. Here's why. If the `if` wasn't there, then $E$ would equal the expected value of $k$, which is $n/2$. As it is, we are only printing "with probability $1/2$", so we would expect the answer to be roughly half of $n/2$, that is, $n/4$. Since the printing condition depends on $k$, this heuristic calculation is wrong, though it turns out to predict exactly the correct value. Still, it lends credence to our calculation.
> 1 votes

# Answer
The first loop counts $k$, the number of $1$'s, an integer in range $\[0,n\]$, with a binomial distribution. When $k$ is odd, $k$ PRINTs are performed.

So the answer is the weighted average of the odd integers in range $\[0,n\]$.

By the symmetry of Pascal's triangle, for odd $n$, the sum of odd $k$'s equals the sum of even $k$'s, while the total sum is $(n+1)\dfrac n2$ (using the mean formula).

Hence the requested expectation, $\dfrac n4$.
> 0 votes

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


title: floating point rounding (1/x)*x

text:
# Question
Title: floating point rounding (1/x)*x
I'm trying to figure out what the smallest positive integer x such that the floating point expression round(round(1/x)\*x) is not equal to 1 in single precision.

I have that the answer is 41, but when I let the number 3 for example be x, isn't 1/3 = 0.333, and when rounded = 0, 0 * 3 = 0? So why is the answer 41?

# Answer
That's probably not what was meant by "round". I suspect "round" probably meant to round to the nearest single-precision float. In particular, you can easily verify that 41 is the smallest number with this property:

```
>>> from numpy import *
>>> float32(float32(1.0/3.0)*3.0)
1.0
>>> float32(float32(1.0/40.0)*40.0)
1.0
>>> float32(float32(1.0/41.0)*41.0)
0.99999994

```

But you should double-check the definition of the function round() with whoever told you this problem. We can't read their mind.
> 1 votes

---
Tags: floating-point, rounding
---


# Question
Title: DFA for the language L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }
I need to find a DFA for this language: L = { $ \omega = xy \in (a,b)^\*\mid |x|\_a = |y|\_b $ }

# Answer
> 4 votes
Let $w=w\_1\dots w\_n$ be any word in $\\{a,b\\}^\*$. For $i=0,\dots,n$ consider the values $d\_i(w):=|w\_1\dots w\_i|\_a - |w\_{i+1}\dots w\_n|\_b$. We can prove

* $d\_0(w) = - |w|\_b \le 0$,
* $d\_n(w) = |w|\_a \ge 0$,
* $d\_{i+1}(w) = d\_i(w) + 1$ for $i=0,\dots,n-1$.

This implies that there must be some $i$ with $d\_i(w) = 0$, and therefore $w\in L$. So $L=\\{a,b\\}^\*$.

---
Tags: regular-languages, automata, finite-automata
---


title: What is a naive method?

text:
# Question
Title: What is a naive method?
I was researching dynamic programming and read the following:

> Often when using a more naive method, many of the subproblems are generated and solved many times.

What is a naive method?

# Answer
It's not a technical term with a precise meaning, it is just the English word "naive". In a computer science context, the word usually means something like "one of the things you would think of first, but without realizing a less obvious but important fact".

For instance, if one knows the definition of Fibonacci numbers is $\mathrm{Fib}(n) = \mathrm{Fib}(n-1) + \mathrm{Fib}(n-2)$, then a "naive" implementation would be

```
def Fib(n):
  if n <= 1:
    return 1
  else:
    return Fib(n-1) + Fib(n-2)

```

What's the problem? That if we call, say, `Fib(7)`, then we end up making many of the same calls over and over, such as `Fib(4)` (because `Fib(7)` calls `Fib(6)` and `Fib(5)`, and `Fib(6)` calls `Fib(5)` and `Fib(4)`, and both times we call `Fib(5)` it calls `Fib(4)` and `Fib(3)`, and so on).

So here a more a more "sophisticated", as opposed to naive, solution would be like dynamic programming and avoid all the extras computations.
> 21 votes

# Answer
Naive implementation is the solution where it looks straightforward and less tricky as possible.

In some cases, it may be not have good space or time behavior, like the naive implementation of the Fibonacci function (exponential rather than linear).

But in many cases, it can work well most of the time. So nothing is wrong with the naive approach, you can do it as 3 steps:

"Make it work" (as requested) -\> "Make it elegant/beautiful" (refactoring, more readable) -\> "Make it fast" (performance optimization)

For programming languages with traditions of "over-engineering" like Java, I would recommend "simplest solution" any day.
> 3 votes

# Answer
In general, we can solve every problem in **NP** in time $2^{\text{poly}(n)}$ by *brute force*, meaning we explicitly enumerate all candidates for an NP-witness, which has length polynomial in the input size $n$. In this context, the method of "check every possible solution" can be considered naive.
> 1 votes

---
Tags: terminology, dynamic-programming
---