# Question
Title: How to understand out of bound in the following theoretical context?
Consider the following initialization step of loop invariant for merge procedure

**Initialization**: Prior to the first iteration of the loop, **we have $k=p$, so that the subarray $A\[p .. k - 1\]$ is empty**. This empty subarray contains the k- p= 0 smallest elements of $L$ and $R$, and since $i = j = 1$, both $L\[i\]$ and $R\[j\]$ are the smallest elements of their arrays that have not been copied back into $A$.

I have doubt in the above statement that if $k=p$, then array $A\[p..p-1\]$ is impossible and hence the further argument cannot proceed, which didn't happen. Where am I going wrong?

# Answer
> 1 votes
It is often useful to allow arrays of zero length. These are just empty arrays. The length of the subarray $A\[i\ldots j\]$ is $j-i+1$, so when $j=i-1$, we just get an array of length 0.

Why is this useful? Here are some examples:

* An array $A\[1\ldots n\]$ can always be partitioned into two arrays $A\[1\ldots i\]$ and $A\[i+1 \ldots n\]$ of lengths $i,n-i$. This works even for $i \in \\{0,n\\}$.
* We can construct an array $A\[1\ldots n\]$ inductively using the formula $A\[1\ldots i\] = A\[1\ldots (i-1)\] \cdot A\[i\]$. The base case is the empty array $A\[1\ldots 0\]$.

Having arrays of *negative* length makes less sense, and could lead to confusion and errors, since there is no semantics under which the formula $|A\[i\ldots j\]| = j-i+1$ would hold for them, since array lengths are non-negative.

---
Tags: loop-invariants
---


# Question
Title: Why does packet delivery time only count transmission time once?
Why is packet delivery time equal to transmission time + propagation delay, and not equal to 2\*(transmission time) + propagation delay?

At the end of packet delivery time, doesn't that mean that those bits haven't been received?

# Answer
> 0 votes
After the transmission time has passed, the last bit of the packet has just been put on the wire. That bit (just like all the others) will take an amount of time equal to the propagation delay to reach the receiver. When the last bit reaches the receiver, all the earlier bits will have reached it. So the total time taken is the transmission time plus the propagation delay.

It might be easier to visualize what's going on if you think about a train instead of a data packet. Imagine that we're standing by the track, some distance apart. We want to know how long it is from when the front of the train passes me (the time at which "I start sending the train to you") until the whole train has passed you (the time at which "you finish receiving the train"). This is equal to the time it takes the whole train to pass me (transmission time), plus the time it takes the back of the train to reach you (propagation delay). Or, if you prefer, it's equal to the time it takes the front of the train to reach you (propagation delay) plus the time it takes the rest of the train to pass you (transmission time).

---
Tags: computer-networks
---


# Question
Title: lambda expressions, parenthesis, and order of application
I am building a lambda applicator in Java, and I have uncovered a bit of misunderstanding. Either my question at the bottom is what I am asking, or something in the build-up below is wrong. Either way, I'd appreciate any insight.

So, `NOT` can be defined as

`λb.b (λxy.y) (λuv.u)`

If we allow

```
A1 = λb.b
B1 = (λxy.y)
C1 = (λuv.u)

```

Now NOT is `(A1 B1 C1)`

By order of operations, `B1` will be applied before `C1` So let `Not1 = (A1 B1)`

`NOT` can now be rewritten as `(Not1 B1)` or `((A1 B1) C1)`.

When we apply the expression

`TRUE = (λdw.d)`

to `NOT`, we have

`((A1 B1) C1) TRUE`

Which, because `A1` is the identity function, is supposed to get us

`((TRUE B1) C1)`

... but why wouldn't we apply `B1` to `A1` first?

# Answer
I believe you are misunderstanding what $\lambda$-abstraction represents and are not considering its scope. First; your definition of $NOT$ is correct and $NOT$ is in normal form.

It is not true that $\lambda b. b\ (\lambda x y. y)\ (\lambda u v. u)$ is the same as $(A\_1\ B\_1\ C\_1)$ and I give here two reasons why:

1. The body of $\lambda$-abstraction goes as far right as possible (after ".", until its enclosing brackets, in our case none) and therefore $\lambda b. b\ (\lambda x y. y)\ (\lambda u v. u)$ is a $\lambda$-abstraction with variable $b$ and body $b\ (\lambda x y. y)\ (\lambda u v. u)$. The string "$\lambda b. b$" in this case is not representing an identity expression, but is a part of the definition of $\lambda$-abstraction. Its $\lambda$ "belongs" to the whole $NOT$ expression. Written fully parenthesised, your expression for $NOT$ would be $$\biggl(\lambda b. \Bigl(\bigl(b\ (\lambda x y. y)\bigr)\ (\lambda u v. u)\Bigr)\biggr)$$
2. If it were in fact the same as $(A\_1\ B\_1\ C\_1)$, this could reduce to $(B\_1\ C\_1)$ which could then reduce to $\lambda y. y$ which is identity (which is not $NOT$) and $\lambda$-expressions have at most one normal form.

The $NOT$ operator, when applied to some expression $X$ should reduce like this: $$\bigl(\lambda b. b\ (\lambda x y. y)\ (\lambda u v. u)\bigr)\ X \rightarrow\_\beta X\ (\lambda x y. y)\ (\lambda u v. u)$$

---

You can try your ideas and check existing examples with pLam to help you build a similar tool by yourself. Good luck!
> 4 votes

---
Tags: lambda-calculus
---


# Question
Title: Is this context-free grammar correct for this regular expression?
I have created a context-free grammar

$$ \begin{align\*} &S \to S\_1 \mid S\_2 \\ &S\_1 \to aS\_3bS\_4 \mid \epsilon \\ &S\_2 \to bS\_4 \\ &S\_3 \to aS\_3 \mid \epsilon \\ &S\_4 \to aS\_4 \mid bS\_4 \mid \epsilon \end{align\*} $$

for this regular expression

$ (aa^\*b(a \cup b)^\*) \cup (b(a \cup b)^\*) $

Is the grammar correct or am I missing a certain route?

# Answer
One way to check whether you have got correct grammar is to use plain English or regular expression to characterize each non-terminals, starting from the more basic blocks.

$$S\_4 \to aS\_4 \mid bS\_4 \mid \epsilon$$ This rule says $S\_4$ is the words any words made up by zero or more $a$'s and $b$'s or, what is equivalent, $(a\cup b)^\*$.

$$S\_3 \to aS\_3 \mid \epsilon$$ This rule says $S\_3$ is the words any words made up by zero or more $a$'s or what is equivalent, $a^\*$.

$$S\_2 \to bS\_4$$ This rule says $S\_2$ is all words that are $b$ followed by zero or more $a$'s or $b$'s or what is equivalent $a(a\cup b)^\*$.

$$S\_1 \to aS\_3bS\_4 \mid \epsilon$$ These two rules says $S\_1$ is $aa^\*b(a\cup b)^\*$ or the empty string.

$$S \to S\_1 \mid S\_2$$ This rule says $S$ is $aa^\*b(a\cup b)^\*$ or the empty string or $a(a\cup b)^\*$.

The given regular expression for $S$ is $$ (aa^\*b(a \cup b)^\*) \cup (b(a \cup b)^\*). $$ Can you see the difference between the given regular expression and the above description of $S$? Yes, the extra empty string. That is the single difference.

If the given regular expression is more complex, we might need to design some algorithm and implement it in some programming language. For the simple ones like this, the above step by step analysis should be enough. Be careful, of course.
> 0 votes

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


# Question
Title: Calculating Tag Bits in a Direct-Mapped Cache
The following comes from Patterson & Hennessy *Computer Org. and Design* (5th ed., p. 390):

> How many total bits are required for a direct-mapped cache with 16 KiB of data and 4-word blocks, assuming a 32-bit address?

My question is, how can we determine the tag bits based on the book's answer?

The answer shows the following:

> We know that 16 KiB is 4096 (212) words. With a block size of 4 words (22), there are 1024 (210) blocks. Each block has 4 $\times$ 32 or 128 bits of data plus a tag, *which is 32 $ - $ 10 $ - $ 2 $ - $ 2 bits*  \[emphasis added\].

I see that 32 is the assumed address size (in bits); 10 is the index (log2 of 1024); and 2 bits are the offset; however, what are the **other** 2 bits subtracted from 32?

# Answer
> 0 votes
Since Hennessy & Patterson uses MIPS architecture as the basis for all its examples, we can assume that this example is no exception. MIPS is byte addressable. Hence a byte offset of 2 bits (to address the four bytes in the 32-bit word size) need to be included in the 32 bit address.

These 2 bits occupy the least significant two bits of the 32 bit address's binary representation. Hope that helps!

---
Tags: cpu-cache, caching
---


# Question
Title: Terminology for reducing runtime of an algorithm by using a property of the problem?
It is a very standard situation that we have a class of problems $P$, and a subclass $\tilde P\subset P$ which has a certain restricted property.

For example, $P$ could be the problem of searching through an arbitrary list of people for someone with height $1.8$ meters, while $\tilde P$ could be the same problem, except that it is known that the list is ordered by height.

Searching through an ordered list is far more efficient than through an arbitrary list.

**My question is: what would be the term for an algorithm using/relying on a certain particular structure of the problem in order to run more efficiently than would be needed in the general case?**

**Or alternatively, what is the term for "omitting calculations" that are necessary to do in the general case but that can be omitted in the restricted problem case?**

# Answer
> 2 votes
I'd call it "special-casing".

There are variations. Variation 1 would be: You examine the input, and if the input has a special form, then you use an algorithm that cannot handle every input, but only input like the one you detected.

Variation 2: You run an algorithm that will run fast, but will not be successful for every possible input. You may detect while you run the algorithm or after you ran it that it failed, and use a more general algorithm.

Variation 3: You run a general algorithm, knowing that it will be fast in some cases, and hope your case is a fast one.

# Answer
> 1 votes
The common name is just *optimisation* which in this context may be elaborated as *restricted case* or like gnasher729 mentioned: *special case*.

The concept of cutting needless calculations is called *lazy evaluation* or *call-by-need*. When you have to handle general case, all computations are required, but if you hit *deegenerate case*, some calculations are simply ommited.

Another term is *specialization*, when function takes inherent structure of the problem, and is suited only to given case (but unlike lazy evaluation or special casing, it never checks if input is restricted, it is assumed from the start).

# Answer
> 0 votes
From what I've seen, there isn't a single technical term for this but people tend to use phrases involving the word "restricting" or "restriction", such as "restricting the input", "restricting to the case where..." and so on.

# Answer
> 0 votes
The concept you are looking for is very close to that of **promise problems**. Although promise problems are usually related to decision problems, you could easily generalize the concept to search problems.

The algorithm solving a promise problem is allowed to have an unspecified behavior on instances which do not fulfil the promise. Hence, you could set the promise to be the property you are relying on and then analyze the complexity of algorithms which must work correctly only for inputs that satisfy the promise.

---

(Adding an alternative answer in response to criticism to my other answer. This seems to better address the penultimate question in the OP (i.e, relying on properties of the input), while the other one (i.e., "reductions") better suits "omitting calculations", that is, the last question in the OP.)

# Answer
> -1 votes
The term you are looking for is **reduction**, which is a central aspect of complexity theory. In particular, what you want are so called *efficient* (or *poly-time*) *Turing reductions* (also called *Cook reductions*).

We say a problem $A$ is Turing reducible to a problem $B$ if there is a TM which solves $A$ if provided with an oracle for $B$. (An oracle is a device which answers a query in $B$ with runtime cost 1.) The reduction is efficient if the TM can perform it in polynomial time in the length of its input.

Note the above applies not only to decision but also to search problems (as you are probably more interested in the latter.)

For specific problems, you may want to set a stricter asymptotic bound (than simply polynomial) on the reduction depending on the asymptotic lower bound of problem $B$. For example, a reduction of a problem $A$ to sorting should take not only polynomial but actually $o(n \log n)$ time; otherwise, the reduction is meaningless since it is powerful enough to solve $B$ (i.e., sorting) directly.

---
Tags: algorithm-analysis, terminology
---


title: Chomsky Classification of Languages

text:
# Question
Title: Chomsky Classification of Languages
Given is a language $A = \\{ a^n\\:b\\:c^{2n}\\:b^m |\\; n ∈ N^{+} ;\\; m ∈ N \\}$ ; where $N^{+}$ are the natural numbers excluding 0.

I have found a type-1 grammar to describe it:

$S \to A\_1A\_2$

$A\_1 \to aA\_1cc \\;| \\; abcc$

$A2 \to bA\_2 \\; |\\; \epsilon$

However, this doesn't tell me much about the language's Chomsky type. How can I know if there exists a more restricted grammar and how can I find it?

# Answer
The language $A = \\{ a^n\\:b\\:c^{2n}\\:b^m |\\; n ∈ N^{+} ;\\; m ∈ N \\}$ is not obviously regular since finite automata do not have memory and hence it is not possible for them to determine the relation between $a$ and $c$.

Let us try to construct a Type-2 grammar for this language. Note that Type-2 grammars are of the form $V\to(V \cup T)^{\*}$ where $V$ represents non-terminals and $T$ represents terminals. So our example would lead to something like this:

$S \to a\\:A\_1\\:cc\\:A\_2 $

$A\_1 \to a\\:A\_1\\:cc\\;|\\;b$

$A\_2 \to b\\:A\_2\\;|\\;\epsilon$

Hence we see that this is a Type-2 grammar according to the Chomsky hierarchy.
> 1 votes

---
Tags: formal-languages, formal-grammars, chomsky-hierarchy
---


# Question
Title: Whether language of all turing machines is decidable or undecidable or semi-decidable?
I recently came across this language:

$L=\\{\<TM\>| \text{TM accepts recursively enumerable languages}\\}$

It was asked in the question to find out whether language L is decidable or undecidable.

As far as I could reason out, language L is the set of all recursive enumerable languages or set of all turing machines.

But I can't figure out whether this language is decidable or not.

Can anyone please help me out??

Thanks in advance!!

# Answer
> 2 votes
Let us express $L$ slightly more precisely. $$ L=\\{\<TM\>\\; \mid \text{The language accepted by } TM \\ \text{ is a recursively enumerable language}\\}$$

Since for any Turing machine $TM$, the language accepted by it is a recursively enumerable language by definition, that restriction clause for $TM$ does not have any effect at all. We have, as indicated by OP, $$L \text{ is the set of encodings of Turing machines.} $$

The question becomes "Whether the language of all Turing machines is decidable or undecidable or semi-decidable?" as in the title.

Now this question is really about how we encode all Turing machines (in some specified model). There are ways to encode them so that we could end up with undecidable or semi-decidable language. However, in most reasonable encodings of Turing machines of most common models such as the standard Turing machines described in Wikipedia, we can check whether a string encodes a Turing machine by an algorithm in finite time.

So the simplified answer is "$L$ is decidable". This is the generally accepted answer. It is especially suitable when the encoding of Turing machines is implied to be decidable such as in the book *Introduction to the theory of computation* by Michael Sipser. Or when a decidable encoding of Turing machines has been described explicitly and has been assumed to be the default such as in the book *Introduction to automata theory languages and computation* by John E. Hopcraft et. al.

(The complete answer would be "$L$ is decidable unless an unusual encoding of Turing machines is used", which sounds, however, pedantic and which is usually not a welcomed answer.)

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


# Question
Title: What is this data structure/concept where a plot of points defines a partition to a space
I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem.

Basically it's a plot of points, and the lines are drawn to be equidistant between two points. It forms a perfect partition where the lines around the point form the shape of area that is closest to that point. Does this ring a bell to anyone? I've had a tough time googling descriptions and getting results. And I don't know how else to describe it. Hopefully the picture helps.

# Answer
> 33 votes
What you described is Voronoi diagram.

Here is an excerpt from Wikipedia.

> In the simplest case, shown in the first picture, we are given a finite set of points ${p\_1, \cdots, p\_n}$ in the Euclidean plane. In this case each site $p\_k$ is simply a point, and its corresponding Voronoi cell $R\_k$ consists of every point in the Euclidean plane whose distance to $p\_k$ is less than or equal to its distance to any other points. Each such cell is obtained from the intersection of half-spaces, and hence it is a convex polygon. The line segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are the points equidistant to three (or more) sites.

# Answer
> 3 votes
You are looking for a Multi-Class Classification Algorithm. I suggest you have a look at:

---
Tags: algorithms, data-structures, terminology, computational-geometry
---


# Question
Title: What is the difference between a Top type and a Unit type
Wikipedia defines a Top type: (edited for readability)

> The **Top** type \[...\] is the universal supertype, as all other types in any given type system are subtypes of **Top**

However, the article goes on to say:

> In C++: The pointer to void type can accept any non-function pointer, even though the void type itself is not the universal type but the unit type.

I don't understand this. In particular, given these two functions:

```
void foo(T1, T2, T3);
SomeType bar(T1, T2, T3);

```

I'd expect `bar` to be accepted wherever `foo` is accepted (in function pointers, as virtual methods, etc); which makes me think `void` is being treated as a supertype of `SomeType`.

Leaving C++ aside, I'd expect the same semantics from any language: any logic that expects a void could logically accept any other type.

---

So, given its properties, **why is void usually called a Unit type, and how is it different from a Top type?**

# Answer
> 6 votes
Let me first give the mathematical counterparts of the unit and the top type:

* the *unit type* is the type $U$ such that for every type $X$ there is a unique map $X \to U$
* the *top type* is the type $T$ such that every type $X$ is a subtype of $T$, written $X \leq T$

Thus we cannot speak of the top type unless we have subtyping. Not all type systems have subtyping, and in those there is no top type to speak of.

The unit type $U$ must be very *small*: since there is only one map $U \to U$, if we have $a, b: U$ then the two maps $x \mapsto a$ and $x \mapsto b$ must be equal, whence $a = b$. We should be more precise about what "equal" means, and we should discuss non-terminating computations, but let's keep things simple. On the other hand, there must be at least one element of $U$, or else there can be no map $\mathtt{int} \to U$. (NB: We can only have a map $S \to \emptyset$ when $S$ itself is the empty set.)

The type called $\mathtt{void}$ isn C/C++ has the property of the unit type. It is a mistake to think that a function returning $\mathtt{void}$ "returns nothing". It actually returns precisely one thing, but because the unique thing that it returns is unique and does not carry any information beyond the fact that the function actually returned, we never make the thing explicit. Thus programmers never see it, and so they end up thinking it isn't there. There are programming languages in which the unique element of the unit type can be made explicit. Can there be a function that returns nothing? Yes, it's a function that does not return at all (if it did, it would have to return *something*) – it is a function which raises an exception! Raising an exception is *not* "returning".

The top type $T$ must be in some sense very *large* because every other type is a subtype of $T$. Note that $X \leq T$ does not necessarily mean that there is an injective map $X \to T$, nor does the fact that there is a map $X \to T$ imply $X \leq T$. There are many kinds of subtyping and it is really quite impossible to tell more precisely what "large" means without knowing what sort of subtyping we are talking about.

For example, in some languages there is subtyping between numerical types, so that for instance $\mathtt{byte} \leq \mathtt{int} \leq \mathtt{float}$. Here $\mathtt{float}$ could be the top type, and it is the "largest" numerical type.

On the other hand, structural record subtyping says that the record type $R = \\{\ell\_1 : X\_1, \ldots, \ell\_m : X\_m\\}$ is a subtype of $Q = \\{k\_1 : Y\_1, \ldots, k\_n : Y\_n\\}$ when every field $k\_j : Y\_i$ has a corresponding field $\ell\_i : X\_i$ such that $k\_j = \ell\_i$ and $X\_i \leq Y\_j$. In words, $R \leq Q$ means that an $R$-record may be seen as a $Q$-record because it has all the fields that a $Q$-record should have, and possibly more. Under this view the top type is the empty record $\\{\\}$, which is isomorphic to the unit type!

You asked concretely about subtyping of functions. The basic rule there is: if $X\_2 \leq X\_1$ and $Y\_1 \leq Y\_2$ then $(X\_1 \to Y\_1) \leq (X\_2 \to Y\_2)$ (notice the reversal of inequality for $X\_1$ and $X\_2$). In your particular case we have $X\_1 = X\_2 = T\_1 \times T\_2 \times T\_3$, $Y\_1 = \mathtt{SomeType}$ and $Y\_2 = \mathtt{unit}$ (I refuse to write "void" for something that is not the empty type and C/C++ can go sulk in the corner). So the question comes down to $\mathtt{SomeType} \leq \mathtt{unit}$, i.e., should the unit type be the top type? Well, this depends on what "subtype" means, as I tried to explain above. In C and C++ subtyping is expressed through a system of implicit coercions, so you'd have to open a book on C and find out whether there is supposed to be an implicit coercion from an arbitrary type to the unit type. It's a matter of language definition.

---
Tags: type-theory
---


# Question
Title: Are managed computer programming languages eco-friendly?
Managed code needs to be be interpreted or JIT-ed at runtime.

At first glance it seems to me that in general it is more energy consuming to interpret/compile the program on every user's computer than to compile it once and distribute binary code that can be run without any further processing...

So does that make compiled languages more environmentally friendly than managed languages?

Is the difference significant?

# Answer
> 2 votes
I think there might be a misconception. Managed code doesn't necessarily have to be interpreted or compiled on each user's computer.

Significance is in the eye of the beholder. The technical question would be, what is the percentage increase in energy consumption caused by language A vs language B? That will depend on the two languages in question, and the program you're considering, but you could measure it using standard benchmarking techniques. Then, whether that difference is significant or not will be a matter of opinion.

# Answer
> 0 votes
As a theoretical matter (this is CS, not Engineering) the run-time generation of executable code has a possible benefit of choosing more energy-efficient constructs that might not universally be available. Consider CPU variants with and without hardware support for encryption - a software implementation will be less efficient.

---
Tags: programming-languages
---


# Question
Title: Why does little endian apply to numbers and not to text strings?
The Portable Executable file format is the format that Windows EXE files use.

It is a binary format.

Numbers are in little endian form. Thus, the following hex represents the decimal number 256, not 1.

```
00 01

```

Some fields in the file format represent text strings. For example, the "Name" field contains a null-terminated string that has up to 8 characters. Here are the hex bytes for a name and in parentheses the corresponding string:

```
2E 64 61 74 61 00 00 00 (.data)

```

My question is this: The file's byte order is little endian and therefore the bytes in a number are interpreted from right-to-left. Why aren't the bytes in a string interpreted right-to-left? Why aren't the bytes for the above string this:

```
00 00 00 63 74 61 64 2E

```

Notice that I reversed the order of the bytes. That's not how it is in EXE files, but why not? Why does "little endian" apply only to numbers and not to text strings?

# Answer
> 6 votes
The premise is wrong. Unicode encodings include UTF-16BE, UTF-16LE, UTF-32BE and UTF32-LE. Only UTF-8 has no Litte-Endian or Big-Endian variants.

Fundamentally, Endian-ness is about the byte order of multi-byte words, and you're thinking of text encodings which use a single byte per character (i.e. ASCII). There's no order to a single byte.

# Answer
> 2 votes
You certainly could do it that way. It's an arbitrary decision. You could store characters in ascending order, or in descending order.

---
Tags: strings, number-formats, binary
---


# Question
Title: How to choose a word to apply the Pumping Lemma?
I have some questions about the PUMPING LEMMA. First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes. And sorry about my English :)

Now my questions.

What is the easiest way to find a word, to start the Pumping Lemma? Are there some tricks I have to know? For example I wanted to prove the following language is non-regular: $$A=\\{a^nb^mc^k\mid n,m,k \in N \wedge n\ mod\ 2=0=m\ mod\ 2\ \wedge m\<k\\}$$

My idea is to choose the word $w=c^n$. But it seems like a bad idea, because if I choose the decomposition $w=xyz$ with $y\not= \lambda$ than I can not pump it up, so that it isn't in A anymore. With the decomposition we get $x=c^i$,$y=c^j$ and ${c}^{n-i-j}$. Now I have to choose an $k$ to pump it up, but there is no $k$, were $w$ is not in $A$ anymore, or am I wrong?

For example let $k$ be $0$. Then we get $xy^0z = {c}^{n-j}. But $ m \< k $ \Longleftrightarrow 0\<n-j$ for $ j \> 0 $ is not wrong, so its not working.

My goal is to find a smart word, so that I do not need a case distinction.

I hope my problem is understandable. If not just ask.

# Answer
> 1 votes
You are on the right track. You just need to continue observing and trying. The trials and errors you have done might have been done by many experienced users more or less in different ways.

As you have found $w=c^n$ does not work. That word is too simple to be pumped outside of $A$, whether we will pump it down or pump it up.

Let us continue your preference/acumen to ignore the $a^n$ part. Let us choose word $b^mc^k$, where $m\<k$. If we can pump substring of $b^m$ enough time, the number of $b$'s in $w$ will become larger than $k$ eventually. To ensure what will be pumped is a substring of $b^m$, we can let $m\ge p$, where $p$ is the pumping length.

So let us try $b^{p}c^{p+1}$. I will let you check that this word, if pumped up, will be no longer in $A$.

However, the number of $b$'s in $w\in A$ must be even. If $p$ is odd, $b^pc^{p+1}$ is not in $A$ in the first place. Well, in that case, we can choose $b^{p+1}c^{p+2}$.

In general, how to choose the right word so that it could pump down or up out of the language might feel like a bit of black magic without much pattern initially. However, there is actually not much choices involved. You may learn from this answer and this answer.

---

**Exercise**. Prove the following language is not regular. $B=\\{a^nb^mc^k\mid n,m,k \in N \wedge n\operatorname{mod}2=1=m\operatorname{mod 2}\ \wedge m\<k\\}$

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


# Question
Title: Algorithm to find if there are N 1's in a matrix where no two 1's are in same row or column
I am trying to find an algorithm to determine whether a $N\times N$ matrix of ones and zeroes could have a sublist of ones, such that in that sublist we have only one $1$ from each row or column.

# Answer
> 3 votes
This is the perfect matching problem in a bipartite graph: construct a bipartite graph with nodes $1,...,N$ on one side and nodes $-1,...,-N$ on the other side, and with an edge from $i$ to $-j$ if your matrix has a 1 in row $i$, column $j$. Then a perfect matching in this graph corresponds to a subset of ones in the matrix having the property that no two of them are in the same row or column.

## Textbook algorithm

The Hopcroft-Karp algorithm solves the problem; it can determine if a perfect matching exists in time $O(\sqrt{N} M)$ where $M$ is the number of ones in your matrix (clearly, $M \le N^2$).

## A simpler randomized algorithm

If you are satisfied with a randomized algorithm (with a small probability of error), there is indeed a conceptually simpler algorithm due to László Lovász. Create a new matrix $X$ in which every 1 in the original matrix is replaced by a random integer between 1 and some bound $P\>100 \cdot N$; zeros in the original matrix remain zeros in $X$. Compute the determinant of $X$. If $det(X) \neq 0$, then for sure the original matrix has a perfect matching; if $det(X) = 0$, then with probability at least $1-1/100$, the original matrix does not have a perfect matching. (If you want to be sure that the value of the determinant does not overflow, you can do the computations modulo $P$ if you choose $P$ to be prime.) Computing the determinant will take time $O(N^3)$ with standard decomposition methods.

## An even simpler (and slower) method

The simplest polynomial-time algorithm I know for bipartite perfect matching is due to Linial, Samorodnitsky and Wigderson and runs in time $O(N^4 \log N)$. Let $c\_j$ denote the sum of the elements in column $j$. The algorithm is as follows:

> For $N^2 \log N$ iterations do:
> 1. Normalize each column so that it sums to 1
> 2. Normalize each row so that it sums to 1
> 3. Compute $c\_1,\ldots,c\_N$
> 4. If $\sum\_{j=1}^N (c\_j-1)^2 \< 1/N$ return YES
> Return NO

## If $N$ is tiny

If you want something even simpler (?) to implement (but **much, much** slower if $N$ is large), you could just enumerate all permutations over $N$ elements, and for each of these check if the corresponding set satisfies your property. That is, for each permutation $\pi: \\{1,\ldots,N\\} \to \\{1,\ldots,N\\}$, you check if cell $(i, \pi(i))$ of the matrix contains a 1, for each $i=1,\ldots,N$. The standard libraries of some programming languages have support for generating all permutations of a set; for example, *itertools.permutations* in Python or *next\_permutation* in C++. However, this approach based on enumeration will take time about $N \cdot N!$, which is more than exponential in $N$. It will probably only be acceptable if $N$ is at most around 10-12.

---
Tags: algorithms, matrices
---


title: Finding related-node clusters

text:
# Question
Title: Finding related-node clusters
I currently have an undirected weighted graph. I am trying to find a good algorithm for learning/finding a cluster of closely related nodes and/or loosely relationship within a cluster in a graph given a size of the cluster. For example, here the longer edges represent the farther relationship between 2 nodes. We identified 2 clusters where each cluster has a close relationship internally. I am new to computer science, could you please suggest an algorithm or a paper for this problem? Your help is really appreciated!

# Answer
> 1 votes
The problem you are trying to solve is called community detection or community structure, where several popular algorithms are listed, such as Girvan–Newman algorithm and Minimum-cut method.

You can find many related questions and answers on this site, on CrossValidate and on StackOverflow, such as the following:

A good introduction can be found at Community detection in graphs.

A recent survey can be found at Community detection in social networks.

---
Tags: graphs
---


# Question
Title: How to write recurrence relation for backtracking problem?
I am not able to understand how to write a recurrence relation for n queen problem. I searched on web and everywhere it was given directly without explaining how can we arrive to that. Recurrence relation is for n\*n board $T(n)=n\*T(n-1)+O(n^2)$ but think it should be $T(n)=T(n-1)+O(n^2)$ as if we put the queen anywhere in first row, we are left with $(n-1)\*(n-1)$ board and it is sub-problem for T(n-1). But how n gets multiplied is not understandable. Can anyone help in explaining such recurrence relation.

# Answer
> Recurrence relation is for n\*n board $T(n)=n\*T(n-1)+O(n^2)$ but think it should be $T(n)=T(n-1)+O(n^2)$ as if we put the queen **anywhere in first row**, we are left with $(n-1)\*(n-1)$ board and it is sub-problem for T(n-1). But how n gets multiplied is not understandable.

How many cells are there in the first row? $n$. That is where the factor $n$ come from.

* We put the Queen in the first cell of the first row. Removing the first row and first column, we then check the remaining $(n-1)\*(n-1)$ board.
* We put the Queen in the second cell of the first row. Removing the first row and second column, we then check the remaining $(n-1)\*(n-1)$ board.
* $\vdots$
* We put the Queen in the last cell of the first row. Removing the first row and last column, we then check the remaining $(n-1)\*(n-1)$ board.
> 2 votes

---
Tags: time-complexity, recurrence-relation, divide-and-conquer
---


# Question
Title: How to decide which bytes will form a packet ?(computer networks)
In wireless communication , I understand what it means to transmit a "bit" but I wanted to understand what exactly does it mean by a packet .

\*******POST EDIT/RECEIVING INITIAL ANSWERS\******* I got the following question , which is also there in my comment ,

1. How to decide which bytes should form one packet of data ?
2. What distinguishes one packet from another ?

for the following query

\*****EDIT CLOSES HERE \****

There will be a signal of certain frequency, $ \omega $ which is transmitted .If the amplitude crosses a threshold then it means then we say that a "bit" about the information which is interpreted or encoded by a signal of frequency $ \omega $ is detected or received . (Please correct me If I am wrong)

Similarly , I would like to understand what exactly a "packet of data" in networking means electronically(logically or physically maybe) . What is the definition of a packet ?

Still if the previous version of this question is required then its in the following link :

https://hastebin.com/tejapuvace.coffeescript

Looking forward to replies , thanks a lot .

# Answer
> 1 votes
As pointed out in the answer by gnasher, a packet is nothing more than a sequence of bits.

The actual transmission depends on the underlying physical medium. In case of wireless networks, we transmit using radio signals or microwave signals or infrared signals.

> **How do we send information via signals?**

We **modulate** the wave. We take the initial signal, which is just a wave (and contains no data/information) and then somehow ***combine*** our information signal with the base signal. This process is called modulation. The result is a signal that can be transmitted via airwaves.

Note that wireless communication is omni-directional. They are propagated in all directions. At the other end there is a receiver which listens for certain waves (say only listens to certain frequencies). The receiver knows which modulation technique was used to combine the carrier(base) signal with the information, and uses an appropriate technique to demodulate the signal to extract the information.

In case of digital signals (sending 0's and 1's), this is known as Discrete Modulation.

> **How do we distinguish a packet in a signal?**

Till now we have established how a stream of bits can be propagated wirelessly. Distinguishing Layer 2 frames / Layer 3 packets / Layer 4 segments is a job for the Router / Computer which uses the receiver.

> **A simple example.**

Say each link-layer frame starts and ends with one zero and six 1's. So the receiver which is constantly listening for airwaves with a certain characteristic (amplitude / frequency / phase / whatever) suddenly encounters a string of bits "**0111111**101101.....". This is immediately processed as the start of a frame and we keep on reading the signal until we encounter ""....10101**0111111**..."". This is how we know that the frame has ended.

Now note that in the above explanation we skipped over a huge amount of topics. There are multiple digital modulation and demodulation techniques, as well as dozens of protocols that a frame / packet has to follow to be correctly processed by the target even if it is received. The Wikipedia page for Modulation will be a good starting point for further reading.

# Answer
> 1 votes
A packet is a sequence of bytes. Nothing more, nothing less.

When transmitting packets, a signal is formed in such a way that boundaries between packets are easily identified, and that the bytes forming the packets can be transmitted and decoded by the receiver.

Electrical signals at high frequencies must be formed in such a way that they are not damaged during transmission. A digital signal (low signal = 0, high signal = 1) at high frequency has no chance to survive transmission because of higher frequencies added by sharp signal changes.

In addition, information for error detection and correction is added before transmitting and checked + removed after receiving the signal, so a package that is sent cannot only be received, but checked for correctness.

(The actual way the signal is formed will only be known by a handful of highly specialised engineers. It's no secret, just very difficult and not of any interest to most people. As I said in a comment, "applied magic").

---
Tags: computer-networks, communication-protocols, protocols
---


title: Threads and Operating System

text:
# Question
Title: Threads and Operating System
In a computer, the processor executes different threads and changes between them, the operating system is a program at the end that it´s being executed by the processor, there exists the posibility that the processor is not executing the code of the operating system, if there is, shouldn´t this cause problems with the programs being executed on the computer?

# Answer
For full detail, you should consult a textbook on operating systems.

The brief answer is that the operating system doesn't need to be executing all the time. It suffices for it to periodically regain control of the machine, and this happens through so-called "interrupts". Interrupts can happen for a number of reasons:

* a process that wants the operating system to do something for it (e.g., to perform I/O) can raise an interrupt (known as a "system call");
* a hardware device that needs attention (e.g., because some I/O that was requested has now completed) alerts the OS by raising an interrupt;
* the system clock will raise interrupts at some frequency (typically multiple times per second).
> 1 votes

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


# Question
Title: Is there an FPRAS for the number of min st cuts in general graphs?
Provan and Ball \[1\] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get a Fully Polynomial Randomized Approximation Scheme for it?

\[1\] Provan, J. Scott, and Michael O. Ball. "The complexity of counting cuts and of computing the probability that a graph is connected." SIAM Journal on Computing 12.4 (1983): 777-788.

# Answer
The Provan and Ball paper actually shows a 1-1 reduction from bipartite independent sets (BIS) to min st cuts. So an FPRAS for min cuts would imply an FPRAS for #BIS. However, #BIS is not known (and thought unlikely) to have an FPRAS \[1\]\[2\].

\[1\] Dyer, Martin, et al. "On the relative complexity of approximate counting problems." International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer, Berlin, Heidelberg, 2000.

\[2\] Dyer, Martin, Leslie Ann Goldberg, and Mark Jerrum. "An approximation trichotomy for Boolean# CSP." Journal of Computer and System Sciences 76.3-4 (2010): 267-277.
> 1 votes

---
Tags: complexity-theory, approximation, counting, minimum-cuts
---


# Question
Title: What is the motivation behind restore model of computation?
The memory that stores the input is called the input memory. The memory that an algorithm additionally occupies during the computation is called the working memory.

$\textit{Model of Computations}$

1. Word RAM **:** This a very well known model of computation.
2. Read-only word RAM: Where input memory is assumed to be read-only.
3. Permuted word RAM: Allow input memory to be permuted but not destroyed.
4. Restore model: This is a variant of permuted word RAM model, where the input memory is allowed to be modified during the process of answering a query, but it has to be restored to its original state afterward.

I know that why word RAM is the interesting model of computation in many cases but I don't have any idea what is the motivation behind studying problems in 3 and 4. Let us take the example of DFS(Depth-first Search). I know that the problem has been studied in word RAM and I also know about the space complexity of it in that model. I recently come across one paper in which DFS (see this) has been studied in 4th model of computation. The result is that DFS and BFS in place memory in linear time.

**Question:** What is the motivation behind restore model of computation?

# Answer
The restore model is semantically identical to the read-only model. Both models are natural since you expect operations on objects to not alter them. For example, imagine running a query on a database. You don't want the query to modify the database, but you might not mind if the database is temporarily changed while running the query, as long as it is restored to its original state in the end.

(In fact, in this particular you might care, for many reasons: perhaps several processes access the database in parallel; or perhaps you are worried that a failure will stop the process in the model, thus leaving the database in a modified state. These are reasons why you'd sometimes prefer the read-only model.)

The restore model is more powerful than the read-only model, in the sense that it potentially requires less auxiliary memory. In recent times, this model is known as *catalytic computation*. See for example Koucký's expository article, which provides further motivations for this model.
> 1 votes

---
Tags: algorithms, computation-models
---


# Question
Title: Finding optimal multiplication order and optimal binary tree
I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree.

Consider the following five matrices A, B, C, D and E along with their dimensions;
A=(6×5) B=(5×1) C=(1×7) D=(7×4) E=(4×2)

After two hours, I have calculated the final cost matrix as

```
0   30   72   82   85
    0    35   48   53
         0    28   43
              0    56
                   0

```

and the split k values that led to a minimum m\[i, j\] value

```
0   1   2   2   2
    0   2   2   2
        0   3   4
            0   4
                0

```

Now I don't know how to calculate optimal order for multiplication from the above table. And also don't know to draw optimal tree for that sequence. Kindly someone help me at this point.

# Answer
> 1 votes
This is the classic problem of matrix chain multiplication.

Here is the pseudocode in Java from Wikipedia, which computes, for each $2 \le k \le n$, the minimum costs of all subsequences of length k using the costs of smaller subsequences already computed. It runs in $O(n^3)$, where $n$ is is the number of matrices, assuming the number of rows and columns in all matrices are bounded by a constant.

```
// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
// The first index for dims is 0 and the first index for m and s is 1.
MatrixChainOrder(int dims[])
{
    // length[dims] = n + 1
    n = dims.length - 1;
    // m[i,j] = Minimum number of scalar multiplications (i.e., cost)
    // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
    // The cost is zero when multiplying one matrix
    for (i = 1; i <= n; i++)
        m[i, i] = 0;

    for (len = 2; len <= n; len++) { // Subsequence lengths
        for (i = 1; i <= n - len + 1; i++) {
            j = i + len - 1;
            m[i, j] = MAXINT;
            for (k = i; k <= j - 1; k++) {
                cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
                if (cost < m[i, j]) {
                    m[i, j] = cost;
                    s[i, j] = k; // Index of the subsequence split that achieved minimal cost
                }
            }
        }
    }
}

```

You can check that Wikipedia page for more information. In particular, there is a ready-make java implementation. There is also explanation to a much more complicated algorithm that runs in $O(n\log n)$ time.

---
Tags: optimization, dynamic-programming, binary-trees, matrices
---


title: Worst-case complexity in terms of n?

text:
# Question
Title: Worst-case complexity in terms of n?
I have this algorithm taken out from the Manual of Algorithms Analysis:

```
function pesky (n)
r:=0
for i:=1 to n do
  for j:=1 to i do
    for k:= j to i + j do
      r := r + 1
return (r)

```

I understand the time complexity of this algorithm for any given input size *n \> 0* will be *O(n^3)* since the 3 for loops will always be executed and the inner loop carries out the sum operation *n x n x n* times (this is of course not exact, but I say it in asymptotic terms taking out constants and lower degree terms of *n*); however, during a lecture we were asked to express the complexity of the worst-case in terms of *n* instead of in big oh notation (they left this exercise for next session).

The worst case I can think about for this algorithm would a really large integer as input *n* which in fact could be so large that it approaches infinity (since no restrictions for the input were stated). Even in this worst case we know time complexity would behave in *O(n^3)*, but how would I express this "in terms of *n*", the best thing I could come up with is this:

But I feel like I'm just making that up and that there might be another more correct way to express it. Does anyone know the correct way to express worst-case complexity in terms of *n*?

EDIT: I must make it clear that I found the equation that puts *n* in function to the *r* output by means of summation resolving, however I did not consider that function as the time complexity function (and hence not the answer for "worst-case in terms of *n*") since that function describes output on a given input and not the time it takes to run the algorithm itself.

Moreover I had the idea to try to calculate the complexity counting each operation and I got something like this.

I am not sure if thats correct, if it is I could use that expression to state the worst-case complexity in terms of *n*, and also I could make my initial statement about big oh notation for the worst case more precise since this would be *O(n)*.

# Answer
> 2 votes
Let us interpret `for i:=1 to n` inclusively. That is, `i` will take values $1, 2, \cdots, n$.

Let us check how many operations are done in `pesky(n)`.

`r:=0`: 1 assignment.

`for i:=1 to n do`: $n$ assignments of `i`.

`for j:=1 to i do`: $\sum\_{i=1}^ni=\dfrac{n(n+1)}2$ assignments of `j`.

`for k:= j to i + j do`: $\Sigma\_{i=1}^n\Sigma\_{j=1}^i(i+1)=\dfrac{n(n+1)(n+2)}3$ assignments of `k`.

`r := r + 1`: $\Sigma\_{i=1}^n\Sigma\_{j=1}^i(i+1)=\dfrac{n(n+1)(n+2)}3$ additions by 1. $\dfrac{n(n+1)(n+2)}3$ assignments of $r$.

There are $1+n+\dfrac{n(n+1)}2+\dfrac{n(n+1)(n+2)}3\cdot2=\dfrac{(n+1)(n+2)(4n+3)}6$ assignments in total.

There are $\dfrac{n(n+1)(n+2)}3$ additions in total.

If we treat the computation cost of one assignment as that of one addition, we have $\dfrac{(n+1)(n+2)(4n+3)}6+\dfrac{n(n+1)(n+2)}3=\dfrac{n(n+1)(2n+1)}2$ operations.

That is answer. Note that it is a fixed number given $n$. That is, there is no distinction of best-case, worse-case or average-case.

Or is it? If we ignore over many important details, yes. However, let us take a close look. Does `for i:=1 to n do` involve assignment only? Mostly like not. We have to produce 1, 2, 3, $\cdots$, n in the first place. If we produce them by addition by 1, we have $n-1$ more additions. How do we make sure we will stop when $i$ reach $n$? Probably we have to compare `i` with `n` for about $n$ times. Comparison takes time of course. We should include that cost. Wait, there is more. It is unreasonable to expect that $n$ is in the right position to be compared with $i$; We have to fetch $n$ from somewhere so that we can compare it with $i$. Now, we are not even sure how to describe that fetching and its computational cost. There are, in fact, many more important details that could be taken into consideration.

You might be wondering now. Do we have an answer or not? Yes and no.

* Yes, we have an answer, assuming some assumptions. I will not be surprised that your instructor might come up with a different number of operations under a different set of assumptions, though.
* No, the answer cannot stand up to scrutiny in many situations. That is one of the reasons why we use the big $O$-notations. We can say the computation cost is $\Theta(n^3)$ under a set of very general assumptions (a.k.a. model of computation).

By the way, if you check what I had written before, you will notice and understand that I have been rather careful, saying that I am only computing how many times the innermost iteration are executed. In general, the asymptotic time complexity of a nested loop is determined by the product of that number with the average cost of one innermost iteration.

---

Here is a similar exercise for you to practice.

**Exercise.** Express the best-time complexity of the following function in terms of $n$ instead of in big $O$-notation. Only the operation `r := r + 1` is counted.

```
function pesky2(n)
  r := 0
  for i := 1 to n do
    for j := 1 to i do
      for k := 1 to j do
        r := r + 1

  return r

```

---
Tags: algorithm-analysis, time-complexity
---


# Question
Title: Algorithm for blending/merging shapes together like liquid
This is a basic example of how 2 circles would come together:

A more complex example would be an arbitrarily shaped polygon like a country on earth, merging with another one or a circle. All of the edges would have to somehow attach to the circle as you move the circle around, so it feels like it's adhering together like liquid.

Wondering if there are standard equations for doing this, or how it is done.

# Answer
> 0 votes
The idea of metaball is to treat two circles as objects with mass centered in the middle, calculate at every discrete point (canvas) forces from every circle below threshokd radius (otherwise every point is taken to equation, which drastically increases complexity), and then use another threshold for blending, used per pixel. Optionally with blur afterwards. It works fine for non-isovolumetric computation. If you prefer splines over polygons, one way to do it is: https://pdfs.semanticscholar.org/54d2/61fd778f25cec19060c3fdbaea7a15d14834.pdf

If you require isovolumetric one, use navier-stokes, iterative finite element method.

As for specified polygons, there are two ways:
Use circle or ellipse to contain polygon, use standard metaball algorithm (with elliptic detransform to circle if needed) and then perform mapping from circle (ellipse) to new shape. It will look nice and involve standard tools, but may not be accurate.

Another way is to treat every vertex as separate circle that interacts only with second shape.

If you do not want to create mapping, you may use Bézier patch with "texture" like here: http://hpcg.purdue.edu/papers/Malkova10VisComp.pdf

For reference: Metaballs and marching squares, Metabals as SVG vectors and CSS

# Answer
> 0 votes
The Povray raytracer has an object like this, the blob. You find its code with some explanations at https://github.com/POV-Ray/povray/blob/master/source/core/shape/blob.cpp .

---
Tags: algorithms, graphics
---


title: proof of the rice's theorem

text:
# Question
Title: proof of the rice's theorem
Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given TM’s language has property $P$ is undecidable.

Proof:(This is from sipser's book).

Assume for the sake of contradiction that $P$ is a decidable language satisfying the properties and let $R\_P$ be the TM that decides $P$.

We show how to decide $A\_{TM}$ using $R\_P$ by constructing TM $S$.

First let $T\_∅$ be a TM that always rejects, so $L(T\_∅)$ = ∅.

You may assume that $\<T\_∅\> \notin P$ without loss of generality, because you could proceed with $\bar{p}$ instead of $P$ if $\<T\_∅\> \in P$.

Because $P$ is not trivial, there exists a TM $T$ with $\<T\> \in P$.

Design $S$ to decide $A\_{TM}$ using $R\_P$ ’s ability to distinguish between $T\_∅$ and $T$.

$S = $“On input $\<M, w\>:$

1. Use $M$ and $w$ to construct the following TM $M\_w$.

$M\_w$ = “On input $x:$

1. Simulate $M$ on $w$. If it halts and rejects, reject. If it accepts, proceed to stage $2$.
    2. Simulate $T$ on $x$. If it accepts, accept.”
2. Use TM $R\_P$ to determine whether $\<M\_w\> \in P$. If YES, accept. If NO, reject.”

TM $M\_w$ simulates $T$ if $M$ accepts $w$. Hence $L(M\_w)$ equals $L(T)$ if $M$ accepts $w$ and $∅$ otherwise.

Question: I'm having trouble understanding the last few lines of this proof. $R\_p$ is a decider that decides $p$. It tells us that a machine has the property $p$ or not. When we run $R\_p$ on the description of $M\_w$ and suppose $M\_w$ accepts $w$ then the language of $M\_w$ equals the language $T$ otherwise $\phi$. Now i don't understand how this proves that acceptance problem is also solvable if we have a decide for $P$. I'm stucked at his point , any help would be great.

# Answer
> 4 votes
Let us verify that $S$ is a decider for $A\_{\text{TM}} = \\{⟨M,w⟩\mid M \text{ is a TM and }M\text{ accepts } w\\}$.

Let $⟨M,w⟩\in A\_{\text{TM}}$ be the input to $S$. Let us see how $S$ runs according to its specification.

1. First, construc $M\_w$. Since $M$ accepts $w$, $M\_w$ simulate $T$.
2. Use TM $R\_P$ to determine whether $⟨M\_w⟩ \in P$. Since $M\_w$ simulate $T$, $⟨M\_w⟩\in P$. So, the answer is YES. So, accept.

Now let $⟨M,w⟩\not\in A\_{\text{TM}}$ be the input to $S$. Let us see how $S$ runs according to its specification.

1. First, construc $M\_w$. Since $M$ do not accept $w$, $M\_w$ simulate $T\_\emptyset$.
2. Use TM $R\_P$ to determine whether $⟨M\_w⟩ \in P$. Since $M\_w$ simulate $T\_\emptyset$, $⟨M\_w⟩\not\in P$. So, the answer is NO. So, reject.

The above analysis shows that $S$ is a decider for $A\_{\text{TM}}$.

Hope this helps.

---

**Exercise of a minute or less.** Verify that if $M$ do not accept $w$, $M\_w$ simulate $T\_\emptyset$.

---
Tags: complexity-theory, computability, regular-languages, rice-theorem
---


# Question
Title: What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute
If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?"

This strikes me of being a relative of the Halting Problem, but I just don't know the taxonomy here.

What is the name of this problem, or does it not have a name because it is solved/uninteresting?

# Answer
This is called the *reachability problem* -- is it possible for a given system to enter a given state?

Techniques that attempt to answer this problem fall under *reachability analysis*, which is one of the main goals of (finite / symbolic) model checking.

---

As the other answer suggests, this is one of the many instances covered by Rice's theorem. Answering questions about the runtime behavior of programs from only their source code is almost always undecidable. Nonetheless, there are many attempts to solve these problems that can be fairly effective in "real world" code (e.g., Microsoft's 2002 project SLAM), because human programmers tend to try to make their code easy to understand (for other humans; we hope incidentally also for mechanical analysis)
> 8 votes

# Answer
EDIT: This answer is more detailed than mine.

This is an example of a question covered by Rice's theorem. For example, the question of if a program outputs "Hello World" or not is covered by that theorem.

It also covers quantification over inputs (e.g. does program $P$ do $X$ on all input, does program $P$ do $X$ on some inputs, does program $P$ do $X$ on even inputs, etc...).

In particular, it states that in general, the problem is only semidecidable, just like the Halting problem.

EDIT: The theorem is only about what a program *does*, not its internals. So the question of "does a program ever get to line 7?" technically is not covered by the theorem. To get around this, just imagine that your interpreter/compiler prints out the line number it is currently on. Now the question is "does the program ever say it is on line 7?", which is a question about what it does, and therefore covered by Rice's theorem. You do not need to actually make the modification; just proving the possibility is enough.
> 5 votes

# Answer
Several others have pointed to Rice's Theorem as an answer proving that this is undecidable. As a trivial alternative to that line of reasoning, your problem statement can be shown to be isomorphic to a straight forward halting problem.

To do this, transform the program using the following rules:

* The statement X is replaced with a statement which halts.
* All other statement which halt are replaced with an infinite loop
* An infinite loop is appended to the end of the program (if the end is not already considered to be a statement which halts)

It's trivial to see that solving the halting problem for this transformed problem is identical to determining if X is reachable in the original program. Thus, said reachability is undecidable in general.
> 1 votes

---
Tags: computability, terminology, rice-theorem
---


# Question
Title: is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?
I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition):

> A directed graph $G = (V, E)$ is *singly connected* if the existence of a path from $u$ to $v$ implies that $G$ contains at most one simple path from $u$ to $v$ for all vertices $u, v\in G$. Give an efficient algorithm to determine whether or not a directed graph is singly connected.

Previous threads on this question are here and here. In that second thread, one of the answers links to a preprint by someone who corresponded with one of the authors of the book, and stated (in the abstract of the preprint) that the solution the authors intended was (if I'm understanding correctly) to call DFS-VISIT(G, u) (from p. 604 of CLRS) on each vertex $u$ of the graph, resetting all vertex colors back to white (to indicate unvisited) in between calls, and return false (for "not singly connected") whenever a forward edge or cross edge is found, and returning true otherwise. This would take O(VE) time.

There seems to be some confusion in the answers and comments section of those threads: the above scheme is referred to as "calling DFS on every vertex". In fact, this is different from the DFS algorithm presented on p. 604 of CLRS, which calls DFS-VISIT on all unvisited nodes in the graph, without resetting the colors in between calls, which takes $O(V + E)$ time.

My question is, instead of doing what is stated in the preprint, which takes O(VE) time, is it sufficient to simply perform the ordinary $O(V + E)$ DFS on the graph, and return false (for "not singly connected") whenever a forward edge or a cross edge that is located entirely within a single DF tree is found? (As correctly pointed out in one of the comments in the second thread linked above, a cross edge within a single DF tree means the graph is certainly not singly connected, but a cross edge between two vertices in different trees does not necessarily mean so).

In other words, is it possible to have a non-singly connected graph, such that for some ordering of the adjacency lists, performing the DFS algorithm from p. 604 of CLRS will not find any forward edges or cross edges *within* individual trees, but possibly only cross edges *between* trees, if any?

# Answer
I just realized, a single call to DFS is *not* sufficient, since the conjecture I asked about is *not* true. Here is a counterexample. Suppose DFS first visits all nodes in a tree rooted at $u$, and $v$ is a descendant of $u$. Then suppose an unvisited vertex $w$ has both $u$ and $v$ in its adjacency list. Then, $w$ would not be in the same tree as $u$ and $v$, but there would be cross-tree edges $(w, u)$ and $(w, v)$, and hence there would be more than two paths from $w$ to $v$, making the graph not singly connected.

However, we cannot modify the algorithm to also look for cross edges between trees, since if we removed the $(w,u)$ edge from the example above, then it's still possibly for it to be singly connected even though there's a $(w,v)$ cross edge.
> 2 votes

# Answer
You can check if there is already a path between u and v, using their finishing and discovery time (d\[u\] u is an ancestor of v). If their times are disjoint, then they are on different branches and not reachable from one another, so there shouldn't be more than one path between w and u or w and v.
> -1 votes

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


# Question
Title: What is the term for two file formats that describe the same amount of information?
I am working on file formats conversion. Some of them can be converted back and forth to others without losing any information (fields or precision of the numbers encoded), others file format do not take into account some data or meta-data or use approximated values. I was looking for a term to describe the first case, where two formats describe the same amount of information. I'm aware of the term isomorph that seems to describe the case quite well but I couldn't find any reference to any isomorph file format. Is there any other term used for describing the case?

# Answer
I think that many programmers would look at it in terms of the *conversions* between the two formats, and say that each format can be converted to the other *losslessly*, and that it's possible to make a *round-trip* without losing any data. It's not a standard usage, but if you said that the two formats were *round-trippable* wrt each other, you would probably be understood. That said, you should still explain what that means!
> 3 votes

# Answer
Isomorphic file formats implies semantically that the formats have analogous data structures but no necessarily the same fidelity.

Perhaps this what you want to say: two file formats that have the same (data) fidelity.
> 0 votes

---
Tags: data-structures, terminology, information-theory, filesystems
---


# Question
Title: Relation between semi decidable, undecidable and countable sets
I know that

* **decidable** problem: has both counting (bijection with $\mathbb N $) and membership algorithm (TM halts for both member and non member strings )
* **semidecidable** problem: has counting algorithm and TM halts for member strings
* **countable** problem: has only counting algorithm

Now I have come across **undecidable** language set which does not have membership algorithm (as semi decidable languages at least have TM which halts for member strings, which is not the case for undecidable problems), that is it does have TM that halt neither for member string nor for non member string.

I have doubt about the relationship between these language classes.

I know "decidable $\subset$ semi decidable $\subset$ countable".

Where does "undecidable" fit here?

Is it like this?:

(Match the color of text with that of the border. Region color is lighter shades of corresponding enclosed texts.)

**Q.** Is above diagram correct? Also I want to add "countable" to above. I feel, for finite alphabet languages, countable will be proper superset of "undecidable". Is it right?

**PS:** I feel, earlier I based my understanding of "undecidable" on incorrect definition given in this question. So I draw wrong diagram earlier. I believe its correct now.

# Answer
A language is defined as a set of strings over an alphabet. We will assume the usual situation where the alphabet is a finite set. Then the set of all strings are countably infinite. Why is it countable? Because we can list all strings of length 0, all strings of length 1, all strings of length 2, all strings of length 3 and so on.

The correct diagram should look like the following (where we assume P!= NP), where the enclosing unlabeled plane represents languages that are countable. Note all languages that sit outside of the region of "TM decidable" is "TM undecidable". Note that we usually say "decidable", "recognizable", "co-recognizable" and "undecidable" simply without the prefix "TM".

For completeness, we have the following diagram that includes chomsky hierarchy.
> 3 votes

# Answer
Undecidable is simply the complement of decidable, as the name suggests: anything that is not decidable is undecidable. So the whole pink area of your diagram consists of undecidable languages.

All languages over finite alphabets are countable. For example, every string over alphabet $\\{0,1\\}$ is a natural number written in binary.1 Everything in your diagram is countable. We only ever consider finite alphabets; infinite alphabets aren't physically realizable because we can't store infinitely many distinguishable possibilities in a finite space.

---

1. A small problem is that $0$, $00$, $000$, etc. are all the number zero written in binary. So, instead, associate the binary string $xyz$ with the natural number $1xyz$ and now, every binary string represents a different natural number.
> 3 votes

---
Tags: computability, terminology
---


title: Recursive factorial algorithm

text:
# Question
Title: Recursive factorial algorithm
I'm struggling to understand this factorial algorithm.

```
Falling(n, m):
    if m = 0
        return 1
    if m = 1
        return n
    return Falling(n, floor(m/2))*
           Falling(n - floor(m/2), ceil(m/2))

```

The algorithm should compute $n!/(n-m)!$

I'm analyzing it in the case of n = m, i.e it returns n! Now I'm getting the correct results from my implementation of it in Java, but the correctness of it has shaking my head.

How should I approach this?

# Answer
> 2 votes
If you plug in the result in what is returned by the recursion, you get: $$\frac{n!}{(n - \lfloor \frac{m}{2} \rfloor)!} \frac{(n - \lfloor \frac{m}{2} \rfloor)!}{(n - \lfloor \frac{m}{2} \rfloor - \lceil \frac{m}{2} \rceil)!} = \frac{n!}{(n - \lfloor \frac{m}{2} \rfloor - \lceil \frac{m}{2} \rceil)!}$$

You can see the right side is equal to $\frac{n!}{(n - m)!}$ because of the identity $m = \lfloor \frac{m}{2} \rfloor + \lceil \frac{m}{2} \rceil$ (if you are in doubt about this: check the cases $m$ even and $m$ odd separately).

For correctness, the only thing left to check then is the base cases $m=0$ and $m=1$ are correct (which is a trivial observation), that `Falling` is not invoked with incorrect parameters (this is the case if $m \le n$ holds) and that it terminates (also the case because the invoked instances have strictly smaller parameters).

---
Tags: algorithms, algorithm-analysis, recursion
---


# Question
Title: Algorithm for generating all unlabeled trees with n nodes?
How can one generate all unlabeled trees with $\le n$ nodes?

That is, generate and store the adjacency matrices of those graphs? (not just count them)

Visualization of all unlabeled trees with $\le6$ nodes:

# Answer
> 2 votes
Start by considering rooted trees parametrised by vertex count and depth. These have an obvious recursive construction: a rooted tree of one vertex has depth $0$; a rooted tree of $n \> 1$ vertices and depth $d \ge 1$ has a root and its children; at least one child has depth $d-1$, no child has depth $\ge d$, and the total number of vertices of the children is $n-1$.

Now, by a theorem of Jordan every tree either has a centre or bicentre. A tree with bicentre is formed by taking two rooted trees of equal depth and adding an edge between their roots. A tree with centre is a rooted tree where at least *two* children of the root have depth $d-1$.

# Answer
> 2 votes
Here is some python code https://gist.github.com/hagberg/7979081

I would start with all the trees size N-1 appending a new node to each of the nodes The tricky part is to identify whether each new tree is truly new and not isomorphic to previously generated trees. I'm guessing you need a system to code this topologies to detect symmetries. I'd try to find the longest path Longest path in an undirected tree with only one traversal and find a deterministic way to represent the graph

This now gone project to verify the graceful Tree conjecture contains some c++ code that might help you https://web.archive.org/web/20120729224449/http://www.eleves.ens.fr/home/wfang/gtv/index\_en.html

---
Tags: algorithms, graphs, trees
---


title: Halting problem without input?

text:
# Question
Title: Halting problem without input?
I'm only a layman therefore only discuss stuff naïvely.

I read some introductory articles about halting problems with a scenario that if there were such a decider accessible to us, we should be able to solve some unsolved mathematical problems. We could write some brute-force programs to check Goldbach conjecture, say, and then throw it into the decider to see what happens. Then he refers to halting problem to say that such kind of dream is not possible.

However I notice that there's difference between halting problem and his scenario. Such a brute-force checking program has nothing to do with input data, but for halting problem, we assume the decider to check for every input. So I wonder whether halting problem without input is also undecidable?

I googled and found this. Personally I think it's wrong and couldn't be corrected because of self-reference.

Thanks for your help!

# Answer
> 7 votes
Here is a different proof using Berry's paradox instead of the liar paradox. Suppose that the halting problem (for programs with no input) were decidable. For each $n$, let $f(n)$ be the smallest number which cannot be computed by a program of length at most $n$ (without inputs). Consider the following program for computing $f(n)$:

> Go over all programs of length at most $n$, and for each one that halts, store the number it computes. Output the smallest number not encountered in this way.

This is computable since we can solve the halting problem for the relevant programs, and so we can determine which programs halt. What is the length of this program? The code itself is fixed apart from the length $n$, which can be encoded using $2\log n$ bits. All in all, this program has length $2\log n + C$ for some constant $C$. For large enough $n$ we have $2\log n + C \leq n$, and so there is a program of length at most $n$ which computes $f(n)$! This cannot be, and we are forced to conclude that the halting program is not computable.

# Answer
> 4 votes
Any program and input pair can be converted to a program without input by just including the input in the program, so if the halting problem is decidable for programs without input, then it is decidable for all program and input pairs.

# Answer
> 0 votes
Actually, the halting problem is the problem where you're given an Turing machine description and an input, and you need to determine whether that Turing machine halts on that input. It doesn't matter that your "Goldbach checker" program doesn't take an input. Instead of calling it "a program that doesn't take an input", just call it "a program that ignores its input and checks Goldbach's conjecture regardless of what input it's give." It's perfectly valid to ask if the Goldbach checker halts when given input "Hello, Frank."

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: When estimating camera motion from the fundamental matrix, why can translation only be recovered up to scale using epipolar geometry?
I was wondering once you have recovered the fundamental matrix F such that xFx' = 0. If you try to recover translation and rotation from F, I am told that this is possible only up to scale? Why so?

# Answer
This can be seen intuitively as follows:

The fundamental matrix $\mathtt{F}$ can be written in terms of the epipolar matrix $\mathtt{E}$, in which case the epipolar constraint equation becomes: \begin{align} \mathbf{x}^{\prime\top} \mathtt{F} \mathbf{x} &= 0\\ \mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} \mathtt{E} \mathtt{K}^{-1} \mathbf{x} &= 0,\\ \end{align} where $\mathtt{K}, \mathtt{K'}$ are the intrinsic camera matrices of the two images corresponding to the points $\mathbf{x}, \mathbf{x'}$, respectively, and I have used $(\cdot)^{-\top} = (\cdot^\top)^{-1}$.

Now, we also know that the epipolar matrix has the form \begin{equation} \mathtt{E} = \mathbf{t}^\times \mathtt{R}, \end{equation} where $\mathbf{t}, \mathtt{R}$ are the relative translation vector and the relative rotation matrix, respectively, between the two images. The operator $(\cdot)^\times$ turns a $3-$vector into a $3\times 3$ skew-symmetric matrix. Since $\mathtt{E}$ is $3 \times 3$, $\mathbf{x}$ and $\mathbf{x'}$ are $3 \times 1$ vectors represented in what we call *homogenous coordinates*. These have an equivalence property of $\mathbf{x} = (x\_1, x\_2, x\_3)^\top = (\lambda x\_1, \lambda x\_2, \lambda x\_3)^\top = \lambda \mathbf{x}$ for any $\lambda \neq 0$. If you want to convert a homogeneous point into their more familiar 2D image plane representation, you simply take the first two components and divide them by the third one.

This means that, if we replace all of this in the epipolar constraint and multiply the translation $\mathbf{t}$ by an arbitrary scale factor, we get the following: \begin{align} \mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} (\lambda \mathbf{t})^\times \mathtt{R} \mathtt{K}^{-1} \mathbf{x} &= \mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} \mathbf{t}^\times \mathtt{R} \mathtt{K}^{-1} (\lambda \mathbf{x})\\ &= \mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} \mathbf{t}^\times \mathtt{R} \mathtt{K}^{-1} \mathbf{x}\\ &= \mathbf{x}^{\prime\top} \mathtt{F} \mathbf{x} = 0, \end{align} which leads to the original constraint. This shows there is an overall scale ambiguity. More precisely, the epipolar matrix (and the fundamental matrix) are homogeneous quantities too. This can be further verified by taking the SVD decomposition of $\mathtt{E}$: if it is a valid essential matrix, two of its singular values are equal, hence $\mathtt{E}$ has 5 degrees of freedom and not 6.
> 1 votes

---
Tags: computer-vision
---


# Question
Title: Why proving the solution of a problem is polynomial time is sufficient enough to say that it is a NP prolbem?
Why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem is nondeterministic polynomial time? Please note: this is not a question on how to prove a questions is NP, but instead asking why, we can just do so? If there is more step we need to do, what are missing here?

I am not sure why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem in NP because seem to me that we can also verify a solution of a problem is polynomial time while it is actually linear time, can't we?

Proving that a problem is in NP seem requires one additional step? it is really necessary ?

# Answer
I think that your doubt is legitimate. I assume that you know the difference between deterministic and non-deterministic (e.g. state machines), but maybe this is actually the root of your doubt.

First of all, note that a linear-time algorithm is a polynomial-time algorithm (by definition).

The class $P$ is a subset of the class $NP$, that is, problems that have a (deterministic) polynomial-time solution are also included in the $NP$ class, the class of problems which have a non-deterministic polynomial-time solution. In other words, if you can solve a problem in polynomial time *deterministically*, you can definitely solve it in polynomial time *non-deterministically*.

Therefore, if you are able to verify (*in polynomial time*) that a solution or algorithm $s$ for problem $t$ runs in polynomial time (that is, if you are able to verify that $t \in P$), then you automatically show that the problem $t$ is also in $NP$ (because $P \subset NP$).
> 0 votes

---
Tags: proof-techniques, np, proof-assistants
---


# Question
Title: Automated geometric theorem-proving using synthetic methods
This question is about geometric theorem proving and is inspired by this Math.SE post. Currently, Euclidean-geometric theorem provers, as referred to in the post, use coordinate geometry to convert a geometry problem into a set of algebraic equations.

> Why haven't people developed a theorem prover that uses *synthetic* reasoning ?

By 'synthetic' I mean reasoning from axioms. I feel that synthetic reasoning would be more insightful than solving a large number of equations; yet, am unsure about how well it yields to implementation. Can you offer more insight? What would be the benefits and drawbacks of such a prover?

Also,I felt that my question would be more appropriate here than on Math.SE.

# Answer
> 3 votes
*(Note: I don't know anything about geometric reasoning, so I'm shifting from my limited experience in automated theorem proving in another field. I think the fundamental issue is the same.)*

Synthetic reasoning tends to blow up exponentially. Typically, after $n$ steps of reasoning, there are about $a^k$ ways to choose a next step for some $a \gt 1$. There might be some overlap because there are multiple ways to prove the same theorem, but you still end up with a really fast combinatorial explosion in practice.

Reasoning from the goal is typically a lot tamer, because you tend to try to deduce the goal from simpler premises. It's still impractical in all but rather constrained settings (e.g. some arithmetic or geometric theories).

Putting a geometric problem into equations sets a boundary on the problem. You have $p$ equations and $q$ unknowns, now go and solve. Since the problem is bounded, the search for a solution will not go on forever. Furthermore, this form is convenient for many shortcut tricks that allow for faster solving, because solving algebraic equations is a well-known problem.

This choice of method is not less insightful than synthetic reasoning. An algebraic solver can keep track of the reasoning steps that it uses, and produce a proof trace that explains why the purported solution is really a solution. (Not all solvers bother to keep a proof trace.) This proof trace can be expressed in terms of geometric axioms. Thus you can get the same amount of insight no matter how the proof was obtained. (Insight, or lack thereof: in synthetic reasoning, “and then you apply this lemma” doesn't tell you why this lemma rather than any other lemma.)

# Answer
> 1 votes
There were some implementations in the 1950s and later, but the search space explosion is the main issue (as said above).

You can find more information in:

Shang-Ching Chou and Xiao-Shan Gao and Jing-Zhong Zhang. Machine Proofs in Geometry, World Scientific 1994.

Shang-Ching Chou and Xiao-Shan Gao. Automated reasoning in geometry, Handbook of Automated Reasoning, Elsevier 2001

Dongming Wang. Geometry machines: From AI to SMC. Artificial Intelligence and Symbolic Mathematical Computation, LNCS1138, Springer 1996.

---
Tags: artificial-intelligence, automated-theorem-proving
---


# Question
Title: Algorithm for units allotment to the customers based on preferences
I'm searching for a simple algorithm to allotment a real estate unit for the customer based on the customer preferences like the following table.

Each customer has a priorities and we should allocate a unit for each customer, what is the name of this algorithms type to cover all scenarios.

# Answer
> 1 votes
This is not an answer.

This post is used to show that the problem in the question is not the same as the stable marriage problem. There are three differences.

* The number of customers might not be the same as the number of units. However, there is an asymmetrical version of stable marriage problem as described here. So this is not a critical difference.
* Each customer may not have ranked all units. However, it can be understood each customer ranks all units not explicitly ranked lower than all units ranked. So this is not a critical difference.
* **None of the unit ranks the customers at all**. In stable marriage problem, each man ranks all women while each woman ranks all men. This is **an important difference** that makes every algorithm for stable marriage problem not applicable directly for the current situation.

+ We could assign a random (strict) ranking (and possibly different) of customers to each unit. Now we can apply any algorithm for stable marriage problem to our customers and units.
    + We could assume that all units rank all customers indifferently. We can then find super-stable or strongly-stable "marriage" between customers and units.

Although we could assign rankings of the customers to the units so as to apply the algorithms for stable marriage problem, it adds an extra dimension of condition as well as probably extra steps in the solution algorithms. It might/should be better that the problem and its solution is kept as it is, agnostic to any rankings of the customers by the units.

(This post could be changed to an answer should the question be updated with the addition of a priority table by units.)

# Answer
> 1 votes
This problem is sometimes called the room assignment problem or the hospital/university admissions problem. The standard approach here is to use the Random Serial Dictatorship algorithm (RSD). This algorithm is very simple, but has nice properties and even is the *only* algorithm (where I call algorithms that provide the same output the 'same algorithm') that has all these properties.

The RSD algorithm is as follows: pick a customer at random and assign to that customer the most preferred unit that is still available. Then, pick another customer that has not been picked yet and repeat this procedure until all customers are assigned.

---

This algorithm has the following nice properties:

1. **Pareto optimality**: We want the assignment to be 'efficient' somehow, in the sense that we as much as we can give the users what they want. One way to look at this is to call an assignment 'bad' if any number customers can redistribute their units such that at least one of them has a better unit and none of them have a worse unit. If an assignment is not 'bad', then it is Pareto optimal.

It is a straightforward exercise to verify that the RSD algorithm is indeed Pareto optimal.
2. **Strategy proofness**: We want that there is no way that customers can 'cheat the system' by lying about their preference. Formally, we say that a customer $c$ can successfully *manipulate* if there is a fake preference profile $P'\_c$ such that the algorithm gives a strictly better unit according to the true preference profile $P\_c$ than $c$ would get if $c$ would report their true preference $P\_c$. If there is no possible way for any customer to manipulate, the system is called strategy proof.

It is easy to see that RSD is strategy proof: we only look at the preference profile of $c$ when it is their turn to choose. But then, lying only means that they might pick something that has a lower preference than all available units! So, $c$ cannot manipulate.
3. **'Fairness'** We want also to be somewhat fair, in the sense that every customer should have 'equal opportunity' to get their preferred unit. But, there are limits here. We cannot demand that each user has equal probability to get their best result: Suppose we have 100 customers and all but one customer prefers unit 1 most, but the final customer prefers unit 2. Then whatever assignment mechanism we make, if we want Pareto optimality, the final customer has a higher probability to get their most preferred unit.

In RSD, the randomized portion is there to enforce some sort of equal treatment. We cannot treat everyone the same, but at least everyone has the same chance to be first to pick their favorite, as to be second, third, etc.

---
Tags: algorithms
---


title: Language of TM is Undecidable

text:
# Question
Title: Language of TM is Undecidable
why is this Problem$$L = \\{ \langle M\rangle \mid L(M) \text{ is undecidable}\\}$$ undecidable?

I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case decidable and $L=\emptyset$ especially finite and decidable.

I know we cannot find an algorithm but every TM has a language and we even if we don't it, we know it is decidable.

Can someone help me where I do have a misunderstanding?

# Answer
> 1 votes
You're very close!

The key is the difference between *recognizable* and *decidable*.

A language $R$ is recognizable if we can build a TM $T$ such that $L(T) = R$. In other words, there's a Turing machine that accepts exactly those strings in the language—and for strings *not* in the language, it might halt in a non-accepting state (i.e. it might reject), or it might run forever without halting (i.e. it might diverge).

A language $D$ is decidable if we can build a TM $T$ such that $L(T) = D$, ***and*** $T$ rejects (halts in a non-accepting state) on strings not in $D$.

It turns out that a whole lot of languages are recognizable but not decidable. The language $H\_0 = \\{ \langle M \rangle | M \textrm{ halts on empty input} \\}$ is undecidable (this is the Empty-Input Halting Problem), but $H\_0$ can be recognized by the following procedure (call it $RH$):

> Simulate $M$ on empty input. If it ever halts, accept.

Now we have a Turing machine whose language, $L(RH) = H\_0$, is undecidable! Which means the property in question is non-trivial, so by Rice's Theorem that property is undecidable.

---
Tags: turing-machines, undecidability, rice-theorem
---


# Question
Title: Reason programming language B was named "B"?
I’ve searched around for this already but ironically the results have been overshadowed by “Why C was named C” instead.

If C was named “C” because it came after B, why was B named "B", since the only languages preceding B were FORTRAN and Plankalkül?

Is it possible naming B - “B” was a play on “Assembly” abbreviated - “A” since B is higher level than Assembly and follows this same construct?

# Answer
B was designed by Dennis Ritchie and Ken Thompson, as a cut-down version of BCPL, the Basic Combined Programming Language. Ritchie \[1\] says,

> \[B's\] name most probably represents a contraction of BCPL, though an alternate theory holds that it derives from Bon, an unrelated language created by Thompson during the Multics days. Bon in turn was named either after his wife Bonnie, or (according to an encyclopedia quotation in its manual), after a religion whose rituals involve the murmuring of magic formulas.

---

\[1\] Dennis Ritchie, *The development of the C language*. ACM SIGPLAN Notices. 28 (3): 201–208, 1993.
> 3 votes

---
Tags: programming-languages, history
---


title: REC and RE under intersection

text:
# Question
Title: REC and RE under intersection
Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither?

Assume $L\_{3}$ is the intersection of some language $L\_{1}$ $\epsilon$ RE and some other language $L\_{2}$ $\epsilon$ REC .

Since $L\_{2}$ $\epsilon$ REC, there must be a Turing-Machine $M\_{2}$ that holds on every input, whethere or not the input x $\epsilon$ $L\_{2}$. If we now have a k-NTM $M\_{3}$ that on one band simulates $M\_{2}$ and upon acceptance of the input switches to another band where it then simulates $M\_{1}$ (for $L\_{1}$).

Since $M\_{1}$ is only ever simulated if $M\_{2}$ accepts the input, $M\_{1}$ only gets the chance to hold for every word x $\epsilon$ $L\_{1}$ $\bigcap $ $L\_{2}$.

That means we can already assume that we wont get stuck in a loop for words x $\notin $ $L\_{2}$.

However that is not the case for words that are in the intersection or only in $L\_{2}$ and not in $L\_{1}$, as the simulation of $M\_{1}$ wil also be recursively enumarable and may run forever, without us ever knowing whether the input is accepted or not.

If my thoughts so far were correct, that means that $L\_{3}$ $\epsilon$ RE.

What I am uncertain about is if there is any sort of algorithm or technique with which we could make the simulation of $M\_{1}$ decidable, or if maybe it is possible to make an entirely new TM, independent from $M\_{1}$ and $M\_{2}$ and make sure it is decidable?

# Answer
> 2 votes
You have been going well. Yes, $L\_3=L\_1\cap L\_2\in\text{ RE} $.

Could it be that $L\_3$ is recursive?

The answer is not necessarily. There are several cases here.

* If $L\_1$ is a recursive language as well, then $L\_3$ is also recursive.
* If $L\_1$ is not a recursive language, then $L\_3$ may or may not be recursive.

+ For example, let $L\_2$ be the languages of all words. Then $L\_3=L\_2$ is not recursive.
    + For example, let $L\_2$ be the language that does not contain any word. Then $L\_3$ is also the language that does not contain any word, which is recursive.

---

**Exercise 1**. Show that if both $L\_1$ and $L\_2$ are recursive, then $L\_1\cap L\_2$ is recursive.

**Exercise 2**. Construct two languages $L\_1$ and $L\_2$ that satisfy all following conditions.

* $L\_1$ is recursively enumerable.
* $L\_2$ is recursive and $L\_2$ is not the language of all words.
* $L\_1\cap L\_2\subsetneq L\_1$ is recursively enumerable but not recursive.

---
Tags: formal-languages, turing-machines, computability, undecidability, semi-decidability
---


# Question
Title: Why are finite automata defined as ordered $n-tuples$ and not as sets?
First off, I should mention that I am a new contributor on this site and as such, please bear with me if this has been asked and answered before. I searched to the best of my ability to find similar questions and didn't find any.

**The Question**

Consider the definition of a deterministic finite automaton given below:

> A deterministic finite automaton $M$ is an *ordered* $5$-tuple $ (Q,\Sigma, \delta, q\_0, F)$ where:
>
> * $Q$ is the set of input states;
> * $\Sigma$ is a finite set of input symbols;
> * $\delta\colon Q \times \Sigma \to Q$ is the transition function;
> * $q\_0$ is the initial state
> * $F$ is the set of final states

My main question is, would it be inaccurate to define $M$ as the set $ \\{Q,\Sigma, \delta, q\_0, F\\}$ of five elements? I arrived at this question when wondering if a DFA must necessarily be *ordered* since n-tuples are, by definition, ordered. In other words, the tuple $(Q,\Sigma, \delta, q\_0, F)$ is, by definition, different from $(Q,\Sigma, \delta, F,q\_0)$. But what if we define its elements the same way as given in the definition above? Will it be a DFA? If it will, then can a DFA be instead defined as a *set*?

# Answer
A DFA fundamentally has five components, and those components aren't interchangeable. You can't freely swap the set of final states and the set of input symbols, for example, without just making a mess of everything.

The standard representation just says "those five things make a DFA". In other words, a DFA is just those five things in sequence, nothing more or less. The order matters, not because the input symbols have to come before final states, but because you need to know which is which and not get that wrong. Without an order, you wouldn't know that.

But, if you wanted to represent a DFA as some sort of dictionary instead, like $\\{\`\`Q":\\{\ldots\\}, \`\`\Sigma":\\{\ldots\\},\ldots\\}$, that would be perfectly fine. Or a list of pairs, or really any way you like that makes it clear what's what.
> 3 votes

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


title: Check if K-Sum Variation is NP-Complete

text:
# Question
Title: Check if K-Sum Variation is NP-Complete
# Problem

Given a range of integers $\\{a,a+1,...,b-1,b\\}$, find a subset of size $k$ such that the sum is equal to $s$.

# Question

This problem came from evaluating some scheduling algorithms that I am interested in optimizing for some small home grown useless embedded system I am playing with. My problem is that I do not know if this problem is **NP-Complete** like the **K-Sum** problem. I am guessing it might be but it has been a while since I have dealt with proofs pertaining to **NP** problems. I remember something with **SAT**, but looking around did not jog any memories (at least any good ones).

How might I prove it is or is not **NP-Complete**?

# Answer
Nice question!

> Given a range of integers $\\{a,a+1,...,b−1,b\\}$, find a subset of size $k$ such that the sum is equal to $s$.

Well, this problem can be solved in $O(n)$ time, where $n$ is the number of given integers.

(**Continuity of $k$-sums**). Given integers $\\{a,a+1,...,a+n-1\\}$, an integer $k$, $1\le k\le n$ and an integer $s$, there are $k$ integers whose sum is $s$ if and only if $ka+\dfrac{(k-1)k}2\le s\le k(a+n-1)-\dfrac{(k-1)k}2$

Here is the algorithm.

---

Check if $ka+\dfrac{(k-1)k}2\le s\le k(a+n-1)-\dfrac{(k-1)k}2$. If not, return none.

Let $sum = s$. Let $S$ be an empty set. For $i$ from 0 to $n-1$ do the following.

* Let $temp = sum -(b - i)$.
* If $temp\le (k-i-1)(a+n-1)-\dfrac{(k-i-2)(k-i-1)}2$, let $sum = temp$ and insert $b-i$ into $S$. Otherwise, do nothing.
* If $sum = 0$, break the loop.

Return S.

---

Here are a few related exercises.

**Exercise 1.** Prove the proposition of continuity of $k$-sums.

**Exercise 2.** Show the algorithm is correct.

**Exercise 3.** Modify the algorithm so that it will try adding the smallest number first.

**Exercise 3.** Modify the algorithm so that it will run in $O(k)$ time.
> 2 votes

# Answer
I suspect a polynomial-time algorithm exists. WLOG, you can assume $a=0$ (subtract $a$ from all numbers in the range, and subtract $ak$ from $s$). Then the problem becomes: given a range $\\{0,\dots,b\\}$, find a subset of size $k$ that sums to $s$. If you allow a multiset, it is easy to come up with a polynomial-time algorithm; take $k-1$ copies of $\lfloor s/(k-1) \rfloor$ and one copy of $s - \lfloor s/(k-1) \rfloor$. I suspect similar ideas can probably be applied to find a set as well (i.e., to avoid repeats). I suggest you spend some time working out the details to see.
> 0 votes

---
Tags: complexity-theory, time-complexity, np-complete, subset-sum
---


title: Fixed point of hash

text:
# Question
Title: Fixed point of hash
Are hashing algorithms constructed to guarantee that no fixed point exists?

My assumption is not, because I don’t see what utility that would have. (Please correct me if I’m wrong.) As such, purely for curiosity’s sake, have any fixed points of common algorithms (e.g., MD5, SHA-256, etc.) been found?

# Answer
No, they are not constructed, to avoid having fixed point because it will not leverage extension attack, as of now, even making counter of lenght equal to some weak hash is infeasible and preimage attack is hard (otherwise we would call it compression, not hashing).

As of today, there are methods for collisions finding, and for SHA 256 for finding fixed points. Yes, it was found, take a look at crypto post.
> 1 votes

---
Tags: algorithms, hash, mathematical-analysis, fixed-point
---