title: Cache Direct Map (Index, tag, hit/miss)

text:
# Question
Title: Cache Direct Map (Index, tag, hit/miss)
Alright, I thought I understood this concept but now I am confused. I looked up similar problems and their solutions to practice, and that's what threw me off. The question is a homework problem which says:

Below is a list of 32-bit memory address references, given as word addresses.

3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253

a) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with 16 one-word blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

b) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with two-word blocks and a total size of 8 blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

(How do I know how many bits the tag and index are supposed to have? Also, it is a miss unless both the tag and the index match, right? Or is it just if the index matches? I'm obviously extremely confused but I really do want to understand!)

My answer for a) :

```
Memory        Binary          tag          index         hit/miss
3             00000011       0000          0011          miss
180           10110100       0010          0000          miss
43            00101011       0010          0011          miss
2             00000010       0000          0010          miss
191           10111111       1011          1111          miss
88            01011000       0101          1000          miss
190           10111110       1011          1110          miss
14            00001110       0000          1110          miss
181           10101101       1010          1101          miss
44            00101100       0010          1100          miss
186           10111010       1011          1010          miss
253           11111101       1111          1101          miss

```

b)I'm not sure how to figure this out, but when I looked it up, people were saying the index should be left shifted one bit so that's what I got (I'd like to understand why)

```
3             00000011       0000          001          miss
180           10110100       0010          000          miss
43            00101011       0010          001          miss
2             00000010       0000          001          hit
191           10111111       1011          111          miss
88            01011000       0101          100          miss
190           10111110       1011          111          hit
14            00001110       0000          111          miss
181           10101101       1010          110          miss
44            00101100       0010          110          miss
186           10111010       1011          101          miss
253           11111101       1111          110          miss

```

As always, thank you so much for your help.

# Answer
> 8 votes
For a direct mapped cache the general rule is: first figure out the bits of the offset (the right-most bits of the address), then figure out the bits of the index (the next-to right-most address bits), and then the tag is everything left over (on the left side).

One way to think of a direct mapped cache is as a table with rows and columns. The *index* tells you what row to look at, then you compare the *tag* for that row, and if it matches, the *offset* tells you which column to use. (Note that the order you use the parts: index/tag/offset, is different than the order in which you figure out which bits are which: offset/index/tag.)

So in part (a) The block size is 1 word, so you need 0 offset bits (because $2^0=1$). You have 16 blocks, so you need 4 index bits to give 16 different indices (because $2^4=16$). That leaves you with the remaining 28 bits for the tag. You seem to have gotten this mostly right (except for the rows for "180" and "43" where you seem to have missed a few bits, and the row for "181" where you interchanged some bits when converting to binary, I think). You are correct that everything is a miss.

For part (b) The block size is 2 words, so you need 1 offset bit (because $2^1 = 2$). You have 8 blocks, so you need 3 index bits to give 8 different row indices (because $2^3=8$). That leaves you with the remaining 28 bits for the tag. Again you got it mostly right except for the rows for "180" and "43" and "181". (Which then will change some of the hits and misses.)

# Answer
> 4 votes
The accepted answer clear most of the doubt, and I wanna make a note here (for comp org student).

* The addresses are not byte addressable (as mentioned in the question, they are word addresses). The equation (with +2 offset) mentioned in the textbook should not be used directly in this question.
* remind that offset does not need to be matched for a **HIT** to be happened since cache will be filled by block (or 2 words in part b) each time a **MISS** happened. check this out

---
Tags: computer-architecture, cpu-cache
---


title: Maximum matching on a tree

text:
# Question
Title: Maximum matching on a tree
How should I compute efficiently a matching of maximum size in a tree?

My thoughts so far: since from a path we can get a matching, then just finding the longest path in the tree should be enough to answer the question.

Am I wrong? another approach?

# Answer
You can do much better. Consider for example the tree in which the root has $N$ children, and each one has one child. The maximum matching has size $N$, but the longest path is only four edges long.

Here is a better algorithm. Choose a root arbitrarily. For each subtree, calculate the maximum matching within the subtree, as well the maximum matching within the subtree that doesn't touch the root of the subtree. You can think of it as a form of dynamic programming.

Many problems on trees can be solved efficiently using this kind of dynamic programming.
> 4 votes

# Answer
Here's some pseudocode for @Yuval Filmus answer:

```
// v must be the root of the tree on the first call.
// if the graph has no root, pick any vertex as the root
max_matching(v)
    max_matching(c) for children of v
    // cost of not including edges (v, c)
    score[v][false] = sum for children(v) c of max(score[c][false]; score[c][true])
    // max cost of including edge (v, c), the c vertex
    // without edges, and the remaining children (max of with/without edges)
    score[v][true] = max for children(v) c of (1 + score[c][false] + max for children(v) d of max(score[d][false]; score[d][true]) where c != d)
    if score[v][true] > score[v][false]
        add edge (v, c) to maximum-matching set where c is the matching vertex from score[v][true]

```

The maximum-matching set contains the edges once the function returns. If just the number of edges is required, it can be calculated from `max(score[v][false]; score[v][true])` where v is the root of the tree.
> 2 votes

---
Tags: graphs
---


title: Context-free Grammar Exercise

text:
# Question
Title: Context-free Grammar Exercise
Could someone explain me how to form a context-free grammar with all rules R by this example language, please? \begin{equation} L:=\left\\{w c v c \overleftarrow{w} | w, v \in\\{a, b\\}^{+}\right\\} \end{equation} The arrow over w means, that the word w is written backwards.

I already know that \begin{equation} \Sigma=\\{a, b, c\\} \end{equation} and V (non terminal symbols) maybe have to be \begin{equation} V=\\{S, A, B, C\\} \end{equation}

Thank you for helping.

# Answer
I think you can solve this using this construct:

$$S \rightarrow ASA|BSB|ATA|BTB $$ $$T \rightarrow CAZC|CBZC$$ $$Z \rightarrow AZ|BZ|\epsilon$$ $$A \rightarrow a , B \rightarrow b, C \rightarrow c$$

First rule provides the $w$ and $w^R$ in the language, second rule makes sure $v \ge 1$ and has 1 c in both sides and third is just constructing the $v$ further. My assumption was your arrow on top of last $w$ was just meant it is reversed.
> 2 votes

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


# Question
Title: Clarification about conclusion of $Θ(nlogn)$?
1. Why the first part of formula is equal to $2 * 2^2 + ... + 2^{log(n)} = 2^2 + 2^3 +...+ 2^{log(n)} = 2^3 +...+ 2^{log(n)} =... +2^{log(n)}$
2. What is the logic behind ($2^{log n +1} - 2{log n}$) ?
3. I don't understand why $2n.log - (2^{log (n+1)} - 2)=Θ(nlogn)$ ? (Please explain what is math logic bihind it)

# Answer
In the first part where the summation $\sum\_{i=1}^{\log n}i2^i$, you see that whole summation can be written as that chain of summations (if you sum them all up you'll end up getting the first form on the top). Then you use the summation of power two's formula, i.e. $\sum\_{i=0}^{n}2^i= 2^{n+1}-1$.

In the first line $=2+2^2+...+2^{log n}$ the formula is missing a -1 so the result will be $2^{\log n +1}-2$, the second one is missing a 2 so it will be $2^{\log n+1}-2^2$ and so on.

You can write $2^{\log n +1}$ as $2\*2^{\log n}$ which is equal to $2\*n$. I think what confuses you is that you think they wrote $2^{\log (n+1)}$ where as it is $2^{\log n +1}$.

As for why the $2n\*\log n - (2^{\log n +1} -2) \in \Theta(nlogn)$, since $2n\log n \in \Theta(nlogn)$ and $2^{\log n + 1} = 2\*n$ thus it is $\Theta(n)$ and from the property of asyptotic notation we can conclude $\Theta(nlogn)-\Theta(n) \in \Theta(nlogn)$.
> 0 votes

---
Tags: algorithms, heaps
---


title: Are "logarithm types" a thing?

text:
# Question
Title: Are "logarithm types" a thing?
I'm attempting to formalize some thoughts I've had about paths into data structures. For example, a path into a list of `T`s might be a pair of an index with a path into a `T`; a path into a pair `(A, B)` would be the tagged union of a path into `A` or a path into `B`. Think of a path as a way to specify some small (atomic?) piece of a larger data structure—not unlike a lens, but here I'm emphasizing the structural decomposition of a data type as opposed to an arbitrary computation that satisfies the lens laws (maybe every path is usable as a lens, but not every lens corresponds to a path).

Strictly speaking, my first example about lists of `T`s is a little sloppy, since a path into such a list `l` should have its index bounded by the length of `l`. The pair `(Nat, path T)` is more properly a path into an *infinite* list of `T`s—or, equivalently, a path into a function `Nat -> T`.

So my first interesting observation is that I have an operator that turns exponentials into products and products into sums in a way that's awfully reminiscent of logarithms:

```
path (T^Nat) = Nat * (path T)
path (A * B) = path A + path B

```

That got me thinking about whether there's an `exp T` type as well. Leaving aside all restraint and sense of rigor, the terms of the usual series expansion for $e^x$ offer a hint:

$$e^x = \sum\_{n\ge0} \frac {x^n} {n!}$$

A type-theory interpretation of $\frac {x^n} {n!}$ might be a bag (as in multiset) of $x$s of size $n$ (it's an $n$-tuple $x^n$ but we don't care about the $n!$ ways the tuple can be ordered), so then a value of type $e^x$ would be a bag of $x$s of any size.

So if `bag` and `path` might be inverses, then that's saying something like, the type of all bags of paths into a type `T`, if it exists, is isomorphic to `T`. For example, there's an obvious isomorphism between `(bag A) * (bag B)` and `bag (A + B)` (an isomorphism that doesn't work if you replace `bag` with `list` or `set` or some other collection type, which reinforces my intuition that `bag` is the correct interpretation of $e^x$).

Of course, this is all appealing-sounding nonsense. I haven't even formally defined what a path *is*, never mind all the abuses involved in pretending the series expansion of $e^x$ is an algebraic data type. `path` may also be an idea of limited use, since it's not at all clear to me what to think about something like `path (A + B)` or `path Bool`. But has anyone made a more careful study of these ideas? Searching for "type theory" or "algebraic data types" along with "logarithms", "paths", "bags", "multisets", etc. hasn't yielded anything like what I'm attempting to describe here.

# Answer
Logarithm types are definitely a thing and have been noticed before by a number of people. In functional programming, a `Type -> Type` functor has a logarithm if it's representable, and then the logarithm is the representing object. See also this, this, and this. You are correct about the exponential functor being the bag functor, see e.g. this, where it's described as the fixed point of the derivative operation on endofunctors.
> 7 votes

# Answer
In addition to András' answer, there's one thing you might want to be aware of with all this. I think it's not well known, because although I noticed it many years ago, I haven't really talked about it with many people.

Basically, if you think about some finite arithmetic behind the arithmetic of types, and compare it to some of the power series formula type stuff, what you get won't actually make sense. For instance, you'll probably come across the booleans written as $\mathbf 2$, because it has two values. Now, if you write down the formula for unordered pairs, you'll say: $$\frac{2^2}{2!} = 2$$ and expect the unordered pairs of booleans to be isomorphic to the booleans. But this is actually wrong; there are three unordered pairs: $$\\{0,0\\}, \\{0,1\\}, \\{1,1\\}$$

The reason for this is that when we deal with actual types, we are either over-counting the relevant permutations, or under-counting some of the values relative to their representation in terms of combinatorial species. In terms of the permutations, there is a permutation between $(0,1)$ and $(1,0)$, but $(0,0)$ and $(1,1)$ cannot be permuted into distinct ordered pairs. In terms of values, there are actually *two* ways we could imagine representing $(0,0)$ in terms of distinct labellings:

$$((x, y), \\{x → 0, y → 0\\}) \\ ((y, x), \\{x → 0, y → 0\\})$$

And same for $(1,1)$. This comes from the study of species, where instead of constructions directly on types, one thinks primarily about combining different shapes of labelled trees, and then mapping the labels to the values that should occur at the labelled position. The discrepancy comes because with species, we usually consider structures where each position is *distinctly* labelled, like $(0,1)$, whereas with types you can have degenerate labellings that don't require a permutation to eliminate redundancies.

It is still true that in e.g. Conor McBride's answer linked in András' answer, the type of unordered pairs is something like $2^2/S\_2$ as some sort of type theoretic quotient by permutations. Just, some of the quotienting will be redundant, so you cannot do straight integer arithmetic to count the number of resulting values. Another example of this would be getting the answer: $$ℕ = e$$ by plugging in $\mathbf 1$ for $x$ in the power series. However, *all* the permutations are redundant in that case. (There is a different notion where this does work, though, here.)

It is possible to work out a formula that works for counting the values of unordered pairs of finite types. I think the easiest way to do it is to think in terms of total orders of the finite types, and ordered tuples that must also have ordered components. So $(0,0), (0,1), (1,1)$. You can represent $n$-tuples of finite types with size $k$ by having $n$ dots with $k-1$ marks interspersed, where the marks indicate when you should move to successive values. So the above pairs are: $$\cdot\cdot|\\ \cdot|\cdot\\ |\cdot\cdot$$ I forget the formula for this, but it's something like $n+k-1 \choose n$ or similar.
> 4 votes

---
Tags: type-theory
---


# Question
Title: Hamiltonian cycle, verifying and finding
If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle?

My attempt is to delete an edge of graph G and have G', after run the algorithm on G' to know if it has an hamiltonian cycle if not it means that the edge is in some hamiltonian cycle. Now I don't know how to go on.

# Answer
> 1 votes
Let $P$ be an arbitrary simple path in the graph. If $P$ appears in a Hamiltonian cycle of the graph, you can remove all the vertices of $p$ except the first and the last vertex, connect these two vertices with an edge and the resulting graph must be Hamiltonian.

Keeping this in mind, we can build the Hamiltonian cycle step by step starting with path of length one, since you already described how to build such a path. Then we can extend a path of length $i$ to a path of length $i+1$ using the trick above, where we try all neighbors of the last vertex in the path as a next vertex and we apply the trick above to check if a Hamiltonian cycle exists where the new path is a part of the cycle. Note that we call the black-box at most $m := |E|$ times. Once we reach a path of length $n-3$ it is easy to complete the path into a Hamiltonian cycle in linear time.

---
Tags: complexity-theory, reductions, hamiltonian-path
---


# Question
Title: Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable
I came across following facts:

> 1. Set of finite languages over a finite alphabet is countable.
> 2. Set of languages over finite alphabet is uncountable.
> I believe proof of this will be similar to below fact number 3.
> 3. Set of languages over {0,1} is uncountable.

I came across proof of fact 1 here and of fact 3 here.

**Summary of fact 1 proof:**

> Let your finite alphabet be $Σ={a\_1,…,a\_ℓ}$ and let $\\#$ be some character not in $Σ$. Let $L={w\_1,…,w\_n}$ be a finite language over $Σ$. Then the string $\\#w\_1\\#w\_2\\#…\\#w\_n$ maps different $L$ to different integer.

**Summary of fact 3 proof:**

> Let $L$ be set of all finite length strings over $\\{0,1\\}$. We can generate a one-to-one mapping from $L$ to $\mathbb{N}$ : just add a 1 in front of each string in W and interpret the resulting strings as binary numbers. So $L$ is countable. Now let $L\_{\\{0,1\\}}$ is countable, where $L\\{0,1\\}=\\{L\_1,L\_2,L\_3,…\\}$ with each $L\_i$ being a language over $\\{0,1\\}$. Given that each $L\_i$ is a set whose elements are strings from $L$, and since $L$ is countable, we can build a table whose row indices are language indices and whose column indices are string indices as follows: for each table cell with row index $i$ and column index $j$, write 1 if the language $L\_i$ contains the string $s\_j$ or 0 otherwise.
>
> We flip the value of every diagonal cell on the table above, then collect all strings $s\_j$ such that the diagonal cell on the column of $s\_j$ has a 1 after flipping:
> Lets call it $L\_{diag}={s\_2,s\_3,...}$.
> $L\_{diag}$ is a language with a special property: it is different from every language $L\_i∈L\_{\\{0,1\\}}$. This implies $L\_{diag}≠L\_i$ for all $L\_i∈L${{0,1}} and therefore $L\_{diag}∉L\_{\\{0,1\\}}$. However, since $L$ is a set of strings which are in $L$, $L\_{diag}$ is a language over {0,1} and therefore $L\_{diag}∈L\_{\\{0,1\\}}$, a contradiction. Hence $L\_{\\{0,1\\}}$ cannot be countable.

**Doubts**

I get both the proofs, but I dont get why approaches followed in each of them cannot be used to prove other fact incorrect. That is:

1. Why I cant use fact 1 proof approach to prove fact 3 is incorrect, that is "set of languages over {0,1} is countable". Cant I form similar string string $\\#w\_1\\#w\_2\\#…\\#w\_n$ for different languages to map them to different integers?
2. Why I cant use fact 3 proof approach to prove fact 1 is incorrect, that is "set of finite languages over a finite alphabet is uncountable"?

Cant I form similar table for finite languages and then form $L\_{diag}$ which wont belong to the set of finite languages?

# Answer
1. If the language is infinite, the word $\\# w\_1 \\# w\_2 \ldots$ would be infinite, and so doesn't map to an integer in any meaningful way.
2. Applying the diagonal argument on the set of all finite languages might (indeed, will) result in an infinite language.
> 1 votes

---
Tags: formal-languages, discrete-mathematics, sets, uncountability
---


title: How to simplify context free grammars?

text:
# Question
Title: How to simplify context free grammars?
How to simplify this context-free grammar? $$ S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b $$

Can the simplification result in this CFG?

$$ S \to AC \\ S \to A \\ A \to a \\ C \to E \\ E \to b $$

# Answer
Starting point: $$ S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b $$ Substitute values of $A,B,E$: $$ S \to aCD \\ C \to bD \mid \varepsilon \\ D \to C \mid b $$ Substitute values of $D$: $$ S \to aCC \mid aCb \\ C \to bC \mid bb \mid \varepsilon $$ You can generate $bb$ from $C$ even without the rule $C \to bb$: $$ S \to aCC \mid aCb \\ C \to bC \mid \varepsilon $$ You can generate $b$ from $C$: $$ S \to aCC \\ C \to bC \mid \varepsilon $$ The language of $C$ is $b^\*$, so $CC$ generates exactly the same words as $C$: $$ S \to aC \\ C \to bC \mid \varepsilon $$

---

The grammar generates the regular language $ab^\*$.
> 2 votes

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


# Question
Title: Sort array of duplicate integers in place
Given an array of integers within \[1, n\] where n = size of array, some elements may appear more than once.

Could we sort it with just 1 extra space and in O(n) time?

# Answer
> 1 votes
Use Radix sort. The time complexity is O(kn) and space complexity is O(k + n) . Here n is the number of elements and k is the number of bits required to represent largest element in the array.

---
Tags: sorting, arrays
---


# Question
Title: Paging - access less than a page of memory
I'm having a bit of trouble understanding how less than a page of memory can be used.

From what I understand, memory is given out in page size chunks - say pages are 4096 bytes, and 4 bytes are requested in a program via `malloc`, can less than a size of a page be allocated? Or is the rest of the memory in the page wasted?

# Answer
> 1 votes
You are confusing paging and memory allocation.

Paging is used to implement virtual memory: Your logical address space is divided into pages, and each page can be mapped to a physical address in RAM, or can be assigned to some location in your backing store. Because the computer has to keep track of how each page is used, we make the pages reasonably large to avoid having an unreasonably large number of pages.

malloc doesn't care about pages at all. It assumes that some portion of your logical address space is available for allocating memory. It doesn't care how this logical address space is mapped to RAM or backing storage. It just takes four bytes from your logical address space and keeps track that this memory is used. If - by coincidence - all but 100 bytes of a page had been used by malloc (which malloc doesn't know about and doesn't care about), and you called malloc to allocate another 200 bytes, you would likely get the last 100 bytes of that page and the next 100 bytes of the next page. malloc doesn't care.

Paging also doesn't care about malloc, it only cares about reading and writing data.

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


# Question
Title: What is the time complexity in solving a polynomial equation of degree N in one variable?
How easy/difficult(in terms of big-O) is it to solve polynomial equations of high degrees of N?

Do apps like Desmos actually solve equations to get roots or do they approximate roots by iterating through a range of values for x?

What mechanisms are at play in solving a univariate polynomial equation algorithmically?

# Answer
> 1 votes
The time complexity doesn't just depend on N. It's possible that due to the coefficients, you have to evaluate the polynomial with very high precision to determine whether some minimum of the polynomial near a point x has a value \>0, =0 or \<0, and you need to know this to know the number of roots near to x (0, 1, or 2).

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


# Question
Title: Heap down - What is math logic and intuition behind $\sum_{i=1}^{\log n}(\log n - i) \times 2^i $
In heap (bubble down) we have the formula : \begin{eqnarray\*} \sum\_{i=1}^{\log n}(\log n - i)\times 2^i & = & \log n\sum\_{i=1}^{\log n}2^i -\log n\sum\_{i=1}^{\log n}i\times2^i \\ & = & \log n\times2^{\log n+1}-(\log n\times2^{\log n+1}-(2^{\log n+1}−2)) \\ & = & 2n−2\in Θ(n) \end{eqnarray\*}

1. Why we have $\sum\_{i=1}^{log(n)}(\log n - i)\times2^i$ ?
2. How we get to $2−2\in Θ()$ ?

Please explain details!

# Answer
So I guess you are showing that a complete binary tree can be made a heap in linear time.

1. $(\log n - i)$ counts the maximum number of swaps that a node may require, starting at level $i$, and descending to its final level; at most it could become a leaf. For instance if it starts at level $0$, then it could possibly require $\log n$ swaps; this would happen if the node placed at the root position becomes a leaf, since $\log n$ is the full height of the binary tree. And since level $i$ has up to $2^i$ nodes, $(\log n - i)2^i$ counts the maximum number of swaps for all nodes from level $i$, and $\sum\limits\_i (\log n - i)2^i$ counts the maximum number of swaps for all nodes in the tree.
2. $2n-2$ is asymptotically $\leq 2n$ and $\geq n$; for instance $n\geq 2$ suffices. This is exactly the definition of $\Theta$.
> 1 votes

---
Tags: algorithms, heaps
---


# Question
Title: Can nfa consume more than one letter at a time
If I have a NFA/DFA and I expect inputs of 00, 01, 10, 11 can I read input in groups of 2 binary digits at a time.

like the example shown

# Answer
> 1 votes
Yes, as long as your alphabet is defined as a set of different couples of binary digits

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


# Question
Title: Is there a well-known algorithm for arranging inputs according to their category?
**Background:**

(I’m a complete beginner in computer science in general, so I do apologise if my question is not formulated in a sensible way. E.g. I have avoided technicalities in formulating my problem, but perhaps this causes issues. I'm willing to edit accordingly if so).

I’m trying to get to grips with the way that algorithms are/can be used in economics. I think I understand the (very) basics of how sorting algorithms and clustering algorithms could apply to some problems, but there is a (seemingly) elementary problem which I can’t find a well-known algorithm for.

**The problem:**

Suppose my entire input consists of a set of different quantities of two types of good. For example, apples and oranges:

*Input:* { 1 apple, 1 orange, 10 apples, 10 oranges }

Is there a well-known algorithm which can arrange these inputs by *type of good*, such that the output is the following two sets?:

*Set 1 (apples):* { 1 apple, 10 apples }

*Set 2 (oranges):* { 1 orange, 10 oranges }

**Clustering and sorting algorithms do not seem to be appropriate:**

From my (very, very basic) knowledge of clustering algorithms, they would not be appropriate here, as clusters are meant to represent closeness of data points in space. But, if I were to plot these goods as data points, I would have a representation of their values, whereas I'm trying to group them via their categories.

I also don’t think that a comparison based sorting algorithm would work, as these algorithms produce an ordering (total preorder) of the *values* input. Whereas, again, I'm trying to group them via their *categories*.

**Is my definition of algorithm the issue?**

Perhaps I'm misunderstanding the type of thing that can be input into an algorithm? Cormen *et al.* (*Introduction to Algorithms*, 2009, §1.1) informally define an algorithm as

> ...any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

So perhaps an algorithm can only take numerical values as an input and not numerical values attached to a category label (like 'apple', or 'orange')?

I’d be very grateful for any help :)

# Answer
> 1 votes
An algorithm can be seen as the steps needed to go from a well defined type of input to some well defined output. The input can therefore be everything that one can represent within a computer.

In the algorithm you are asking for it seems like the input has already been classified as specific good as in apples are already classified as apples, had it not been defined one could use clustering to find out what separates the types of goods from each other depending on the data of each entry of a good in the database. That means that clustering is a way of data mining.

One way of solving your problem could use sorting like this:

```
1: def separate_goods(List S):
2:    sort S on the type of good
3:    A := a list
4:    B := a list
5:    current_type := S[0].type
6:    B.add(S[0])
7:    i := 1
8:    while(i < length(S)){
9:       if(current_type == S[i].type):
10:          B.add(S[i])
11:          i := i + 1
12:      else:
13:          A.add(B)
14:          B := a new list
15:          B.add(S[i]
16:          current_type := S[i].type
17:          i := i + 1
18:   }
19:   A.add(B)
19:   return A

```

The idea behind this algorithm is to first sort the input list such that all the apples are next to each, the oranges are next to each other and so on. From there we can go through the list and put all apples in a list together (the list B), then add that list to A, which simply just stores a list for each type of good.

When we go through the list (in the while loop) and sees that we go from a good of type say apples to another of type orange, then know that we finished collecting apples (since they are all together due to the sorting) and we can therefore add the list B of all the apples to list A. Then we make B contain a new list for all goods of type oranges and continuous through the list adding goods of type oranges until we either have categorized all goods or finds a new type of good.

This is not the most effective algorithm one could make, however it illustrates that sorting can be used to solve this problem.

I'm not sure if this answers your question however feel free to reach out to me :)  This does not answer your question, here is another try:

Your problem is somewhat simple and can be solved in many ways, a particular fast way would be to use a hash table. Here you could hash each entry on the type of good, with this you can then access a list of all apples by using apple as key. I believe there is a chapter in Cormen et al about hashing that explains how this is done :)

---
Tags: algorithms, sorting, clustering
---


# Question
Title: Finishing degree requirements NP-complete: Choosing 1 element from each set avoiding conflicts
The question, which I have slightly paraphrased to get rid of the fat, is this: There are $k$ areas of study in which you need to take 1 course. For each area of study, there is a set of courses $C\_1,C\_2,\dots,C\_k$ that you have not yet taken. There are no conflicts between courses in the same area of study, but there can be conflicts between courses in different areas of study. You have a list of $(class1, class2)$ pairs in different areas of study that are in conflict. Can you choose 1 course from each area so that there are no conflicts? Is this an NP-complete problem?

Here is what I have so far:
`K-AREA-COURSE-REGISTRATION` ∈ NP: Given a random list of *k* courses, we can check that we have one course from each area in O(k) time. We can also check for conflicts in O(k^2) time (check each pair of courses for conflict).

`K-AREA-COURSE-REGISTRATION` is NP-complete: Reduce `3-SAT` to `K-AREA-COURSE-REGISTRATION`. Each 3-SAT literal becomes a course (same literal in different clause is a different course). Each clause becomes an area of study (clauses become the $C\_k$ sets). Create conflicts between two courses $a,b$ if, in the original 3-SAT problem, $a=x$ and $b=\bar{x}$. Choosing one course from each set will set at least 1 literal in each `3-SAT` clause true. The conflicts will stop us from setting a single literal both true and false

Question: Do I have/do you have any tips in accounting for the case of two courses $a,b$ which both map to the same literal $x$ in the original `3-SAT` but are in different clauses (therefore in different $Ck$ sets). I may be able to use conflicts to make sure both $a$ and $b$ are chosen, but I was thinking I could just ignore this since all that matters in 3-SAT is at least one literal.

# Answer
Assuming the sets $C\_i$ are pairwise disjoint, this problem is very related to the independent set problem and is called maximum colored independent set (also called rainbow colored independent set). The problem goes as follows. Given a graph and a colouring function over the vertices of the graph. Find a maximum independent set with each vertex in the set having a different colour. The problem is NP-hard as well (try to reduce Independent set).

Assuming the sets are not disjoint the problem does not get easier since the version with disjoint sets is only a special case of this problem.
> 1 votes

---
Tags: np-complete, 3-sat
---


# Question
Title: What happens with register usage in deeply nested functions calls (in theory)?
I am far from being able to construct a meaningful test for this using godbolt or some C compilation tool. But basically I am wondering what it would look like to have deeply nested function calls, where each function had let's say a dozen temporary variables throughout. What happens to register usage? It seems like everything would have to be stored in memory and the register usage would almost be negligible. What is it like in reality? Where am I going wrong?

# Answer
Ignore recursion for the moment, and pretend that a recursive call is just like any other call.

Then the solution is easy: all local variables are spilled to the stack across calls, including the recursive call. So yes, if there is deep recursion going on, most of the local variables will reside on the stack most of the time.

Every platform (operating system + CPU family) defines a protocol called the *application binary interface*, or ABI for short. This specifies how parameters are passed to a function, how values are returned, how the stack is to be managed, and so on. If you want to see what a real-world ABI looks like, see the SysV ABI for Intel x86-64/AMD64. Almost all operating systems follow this ABI on that family of CPUs, with Windows being the most notable exception.

The ABI will specify that some registers are not preserved across function calls (i.e. they are *caller-save*) and some are preserved (i.e. they are *callee-save*). A callee-save register must be preserved by a function if it wants to use that register, and a caller-save register must be explicitly spilled across a call if the caller needs the value.

It's also possible to optimise recursion, as long as the function ultimately presents itself to the rest of the system as if it obeys the ABI. This is where things get interesting.

Tail call optimisation is the most common scenario. If the last thing that a function does in some code path is to call another function, it's sometimes possible to transform the last call into a jump. And if it's a recursive call, then it can be transformed into a loop.

So this:

```
foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
}

```

can be transformed into this:

```
foo(args)
{
    while (the base case doesn't apply) {
        before_the_recursive_call();
        args = recursive_args;
    }
    return something();
}

```

But in that case, no local variables have to be saved across that final call. So nothing, in theory at least, needs to be spilled to the stack there.

As an aside, in C++, the semantics of RAII and exception handling often makes tail call optimisation impossible, so you won't often see this in compilers for the C family of languages.

There is a related optimisation called "middle recursion optimisation", which is used for the more familiar recursive scenario, where there is a single recursive call in the middle of a function:

```
foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
    return after_the_recursive_call();
}

```

This can be transformed into something like this:

```
foo(args)
{
    while (the base case does not apply) {
        before_the_recursive_call();
        push_anything_to_the_stack_that_the_last_part_needs();
        args = recursive_args;
    }

    return_value = something();  // base case

    while (pop_the_stack()) {
        return_value = after_the_recursive_call();
    }
    return return_value;
}

```

Again, this is rare in C-like languages. You would more typically find it in functional or logic languages which don't have loop constructs, and only have recursion. In a language like that, it's often worth going to a lot of trouble to optimise recursion into loops.
> 2 votes

---
Tags: optimization, computer-architecture, compilers, cpu
---


# Question
Title: Converting non-deterministic algorithm to deterministic
I was thinking about an non-deterministic algorithm to generate all the subsets of the $\\{1..n\\}$ set.

```
Subsets(n)
    S' = null
    for i = 1..n
        u = choice(1..n)
        if u in S'
           fail
        S' = S' + u
    for_each u in S'
         print u

```

How would I convert this algorithm into a deterministic form? I know that it is a lot more complicated to convert the `choice` statement in a deterministic manner but I want to get a general idea about maybe representing it in a deterministic manner.

# Answer
Any finitely terminating non-deterministic algorithm can be made deterministic by using depth-first search on the tree of possible executions.

Or, to explain it another way: each time you have a non-deterministic choice, fork the program into multiple copies, one per possible choice. Forking might be done by calling the operating system's `fork()` call (very expensive), or by capturing all the relevant state of the variables and storing it in a set of pending items to explore (potentially tedious to write the code), or by replacing the `choice()` with a recursive call that makes a copy of all of the relevant state (`i`, `S'`) and iteratively tries each of the possible choices (easiest to implement in this case).

Here is an example of how to implement the latter transformation. The state at the `choice` statement is the value of `S'` and `i`. So, we do the following:

```
search(S', i, u):
    if u in S'
        return
    S' = S' + u   # this needs to copy the set, not update it destructively
    i = i + 1
    if i>n:
        for_each u in S'
            print u
    else:
        for u in [1,2,..,n]
            search(S', i, u)

Subsets(n):
    for u in [1,2,..,n]:
        search(emptyset, 1, u)

```

Notice how `search` contains all of the code after the `choice` statement, until the next `choice` statement. We had to rip the for-loop over i apart to make this work, but the transformation was fairly mechanical.

This is a general method that can be used on *any* terminating non-deterministic algorithm -- not just this one.
> 2 votes

---
Tags: algorithms, nondeterminism
---


# Question
Title: What's the best algorithm to find the shortest path between 2 vertices in a graph?
Considering an *undirected* and *unweighted* graph, what's the best algorithm to find the shortest path between two vertices?

# Answer
> 1 votes
At least in theory, the most appropriate algorithm is breadth-first search (BFS), which you execute by starting from your source vertex $s$. Once the BFS traversal hits your target vertex $t$, you halt and trace back a chain of predecessors originating from $t$. This procedure runs in linear time, which is optimal.

However, from a practical standpoint, the answer might depend on the topology of your graph. For instance, some other linear time procedure like a bidirectional search can be much more efficient but this is more challenging to determine apriori.

# Answer
> 1 votes
As Juho already mentioned, Breadth First Search is a good choice but whether it is or not the *most appropriate* algorithm depends upon other factors. In the following I'm assuming that your graph $G(V, E)$ has been given explicitly, and that two vertices $s, t\in V$ are also known upfront.

First, note that Breadth First Search requires an amount of memory which is linear in the size of the graph and this restricts is applicability in most real-world cases. Since you are considering an unweighted/undirected graph then Bidirectional Breadth-First search is for sure much better than its unidirectional counterpart, as it lowers down the memory requirements from $O(bˆd)$ to $O(bˆ\frac{d}{2})$, with $d$ being the depth of the optimal solution (in your case, the number of steps required to get from one vertex to another) and $b$ the branching factor, or average number of descendants.

However, even so this algorithm might exhaust the available memory. If that is the case then you should consider depth-first search strategies. As you are interested in computing optimal solutions then you should consider either Iterative Deepening or Depth-First Branch-and-Bound. The latter is particularly well-suited for those cases where all solutions lie at the same depth (such as in permutation state spaces) which, most likely, is not your case; the former simply launches a number of depth-first searches incrementing the depth by one in each iteration and starting always from scratch until a solution is found. As the threshold was incremented by one in every iteration, the solution found has to be optimal.

However, depth-first strategies suffer severily from *transpositions*: if there are various paths to get from the start state to another node $n$, these algorithms re-expand $n$ as many times as necessary whereas breadth-first search strategies can avoid re-expansions.

In a nutshell:

* If you have memory enough then I recommend you bidirectional breadth-first search.
* If not, then consider iterative-deepening unless you have a large number of *transpositions*

In case you have not memory enough for running the first algorithm and you have many transpositions, then you should move to heuristic search algorithms.

Hope this helps,

# Answer
> 0 votes
You can search from both ends. Find the vertices one step away from X, one step from Y, 2 steps from X, two steps from Y, and so on, until you find a set with a common vertex.

---
Tags: graphs, shortest-path
---


# Question
Title: Divide and Conquer a problem into a sub-problem to solve it efficiently
Assume that problem A cannot be solved in O(n^2) time. However, we can transform problem A into a problem B in O(n^2 log n) time, and then solve B, and finally transform the solution of B into the solution of A in O(n) time.

Prove or Disprove: The above approach shows that problem B cannot be solved asymptotically less than O(n^2) time.

---

My Answer-\>

```
Let time complexity (TC) of B be h(n).
So overall complexity is maximum of(h(n), n²logn) which will be greater or equal
to n²logn greater than n² considering the highest polynomial term.

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0 }.

Here f(n) is O(n2logn+n) and g(n) is O(n2logn) which satisfy the above condition at c>=1 and n0 = 0

(n^2 log n) < 1*(n^2logn+n) for all n > 0

So lower bound of solution B is g(n) i.e. O(n^2logn)

So B cannot be solved asymptotically less than O(n^2 log n) time

Therefore B cannot be solved asymptotically less than O(n^2) time

```

# Answer
> 1 votes
The given information tells you absolutely nothing about the runtime of B.

As an example, let’s say the solution is a vector of N numbers which can be found in O(n^2 log n) but not in O(n^2), and let B be the problem “What was your input”. Solve the problem in O(n^2 log n), pass the solution to B, get it back in O(n), all consistent with the information you have.

---
Tags: algorithms, proof-techniques, divide-and-conquer, proof-of-work
---


# Question
Title: What is the difference between a microoperation, microinstruction and control word?
I've seen a few lectures interchangeably use the two words (microinstruction and microoperation). I've found a source that explains the difference between a microoperation and microinstruction, but I have not been able to associate the two to a control word. Books I have referred to have provided definitions of each, but no explanation about the relation amongst the three.
Edit: Could I also get a few examples to help differentiate the three ?

# Answer
> 2 votes
In traditional horizontal microcode,

* a micro-operation is the most basic operation achievable by a processor;
* a micro-instruction is a set of micro-operations which are executable simultaneously;
* control words are the bit patterns used to encode the micro-instructions.

---

*Micro-operation* is also used in current pipelined processors where an instruction is decomposed in a few (included zero) micro-operations or even a few instructions merged in one micro-operation which are then processed independently.

*Control word* is a far more general term and can refer to any bit patterns used to control any circuit. Its use for the encoding of micro-instructions come from the fact that horizontal micro-code is usually lightly encoded if at all, and thus fields in the encoding control directly parts of the processor. From there it went to be used for the encoding of any kind of micro-instructions. BTW, the area where the micro-program is stored is often called the *control store*.

---
Tags: computer-architecture
---


# Question
Title: Functional problem and verifying solutions
Is there a functional problem for which there is an algorithm that can decide if a solution is a solution or not in polynomial time but we can't find a solution in polynomial time?

Let FP be the class of functional problems.

**Update:** Every problem in FP, say $a$, has a correspondent decisione problem $a'$ (the associated decision problem $a'$ is the problem where we ask if a possible solution is a solution), I ask if there is a functional problem $a$ for which $a'$ is in P but $a$ is NOT in FP.

In this link: Hamiltonian cycle, verifying and finding

we have instead a functional problem HC (hamiltonian cycle) for which HC' is P and HC is in FP.

Intuitively I think that the kind of problems I search, should be 'more' the problem of kind of HC. But maybe the hard part, given $a$ (with $a'$ in P), is to prove that $a$ is NOT in FP.

# Answer
It appears that you are asking whether FP = FNP. That is an open problem. It is known that FP = FNP if and only if P = NP. I suspect that most theoreticians expect that it's likely that P != NP, which would imply FP != FNP. If FP != FNP, there exists a function problem whose solutions can be verified in polynomial time, but where you can't find a solution in polynomial time. In particularly, any FNP-complete problem -- such as FSAT, say -- will have that property, if FP != FNP. So, the FNP-complete problems are particularly good candidates for having the property you articulate. See https://en.wikipedia.org/wiki/Function\_problem for an overview.
> 2 votes

---
Tags: polynomial-time
---


title: Smallest $s$-component in mincut

text:
# Question
Title: Smallest $s$-component in mincut
Suppose there is a directed graph $G=(V,E)$, with source $s$ and sink $t$, and I compute the max flow on it. Then I know that I can find a min-cut $(A,B)$, by letting $A$ be the set of vertices that are reachable from the source $s$.

My question is is this set $A$ the smallest possible $s$-component? I think it is. To be precise, does there exist a subset of vertices $A^\*$, such that $(A^\*, V\setminus A^\*)$ is a min-cut, and for all other possible subsets of vertices $A$ such that $(A, V\setminus A)$ is a min-cut, we have $size(A^\*) \leq size(A)$.

Furthermore, for any other min-cut $(C,D)$, do we have $A \subset C$?. I also think this is the case. But I can't prove it.

Any intuition / hints are much appreciated!

**Edit**

**Definition of $s$-component:** The min-cut is the partition of the vertices of $G$ into two disjoint sets $(A,B)$, where $A$ contains the source $s$ and $B$ contains the sink $t$. The $s$-component w.r.t. a min-cut is then the set $A$.

By "smallest" $s$-component I mean $s$-component with smallest cardinality. I'm wondering if there can be several different **minimal** $s$-component w.r.t. set inclusion, i.e. $s$-components with same cardinality, but are not equal as sets. Equivalently, wondering if there is a **minimum** $s$-component; a set of vertices that is in ALL $s$-components.

# Answer
> 1 votes
I believe that the answer is yes: any min-cut constructed in this way from a max-flow will also have minimum possible cardinality, among all possible min-cuts.

There can be multiple min-cuts, all with the same cost. They form a lattice structure: the intersection of two min-cuts is another min-cut, and the union of two min-cuts is another min-cut. You can identify a "smallest" element in this lattice by taking the intersection of all min-cuts; this will be another min-cut, and it will have the smallest cardinality of all min-cuts.

As I understand it, it is possible to prove that the min-cut obtained from a max-flow is always this "smallest" min-cut. Or, to put it another way, if you think of the source $s$ on the left and the sink $t$ on the right, then any min-cut obtained from a $s,t$-max-flow will be always be a "leftmost" cut. Also, it will follow that any other min-cut will be a superset of this cut found by max-flow, exactly as you conjectured.

For references to these results, and other related material, see the following questions (note: you may need to double-check some of the claims yourself, as I have not personally verified them):

Does Ford-Fulkerson always produce the left-most min-cut

https://stackoverflow.com/a/8101250/781723

https://stackoverflow.com/q/26696312/781723

https://stackoverflow.com/q/9210755/781723

https://stackoverflow.com/q/41964288/781723

# Answer
> 0 votes
Answer yo your first question: Not necessarily. Any off-the-shelf max-flow or min-cut algorithm will produce an arbitrary min-cut partition, not a minimum cardinality one. But you can augment your graph, such that the max-flow output is what you want:

Let $A, V\setminus A$ and $B, V\setminus B$ be min-cut partitions: $$\delta(A,V\setminus A)=\delta(B,V\setminus B) = \min\_{X\subseteq V,s\in X} \delta(X,V\setminus X)$$ Now, add edges with weight $\varepsilon\>0$ from vertex $t$ to all other vertices. The new cuts corresponding to $A$ and $B$ have the updated weights: $$\delta(A, V\setminus A) + |A|\cdot \varepsilon, \\ \delta(B, V\setminus B) + |B|\cdot \varepsilon$$ respectively. Since both the first terms are equal, the second terms $\varepsilon |A|$ and $\varepsilon |B|$ will determine the order. So the min-cut in the new graph is the minimum cardinality, min-cut partition in the original graph. The only caveat is that $\varepsilon$ must be chosen small enough, to make sure it the min-cut in the new graph is a min-cut in the original graph. If weights are integers, any value less than $1/|V|$ would suffice.

($\star)$ : $\delta(X,V\setminus X)$ denotes the sum of weights of cross-edges between $X$ and $V\setminus X$.

---
Tags: network-flow, minimum-cuts
---


title: Run-Time environments

text:
# Question
Title: Run-Time environments
I was reading about Run-Time Environments.
In the Dragon book (2nd ed.) I came across the following presentation:

> \[To implement abstractions, the\] compiler `creates and manages a run-time environment in which it assumes its target programs are being executed.` This environment deals with a variety of issues such as the layout and `allocation of storage locations for the objects named in the source program`, the mechanisms used by the target program to access variables…

so I'm getting confused about points highlighted above:

* How does compiler execute the code, it is only supposed to generate the intermediate code right?
* And does it create runtime environment? I mean there's not a virtual machine that the program runs on, it just runs on your computer right? When does it create a runtime environment?
* Isn't memory managed by the operating system? Why is allocation of storage done by the compiler and at what point? Probably what variables are needed and how much may be known by the compiler but, how does it communicate this information to the OS?

# Answer
For most of these questions, the Runtime Environment as it seems to be described in your book is more easily understood by comparing a low-level language like C, to a VM (Runtime Environment) language like Java.

> How does compiler execute the code, it is only supposed to generate the intermediate code right?

Your quote doesn't say the compiler executes the code. It says that it can start up a RTE which takes over. For lower level languages that don't use a VM/RTE, it can signal the OS to begin execution of the program. In either case, this is a hand-off, not the execution itself.

> And does it create runtime environment? I mean there's not a virtual machine that the program runs on, it just runs on your computer right? When does it create a runtime environment?

Practically speaking, the interpretation of these terms is largely dependant on the language in question.

All programs run on the OS, which manages access to hardware for running programs.

In a low-level language like C, the Runtime Environment as a concept is arguably indistinguishable from the OS itself. Memory alloc/dealloc *requests* are made directly from the program to the OS.

In a high-level language like Java (the most commonly references "VM" language), the Runtime Environment as a concept is used loosely to refer to the program that sits between the executing program and the OS. The Java Runtime Environment consists of the Java Virtual Machine (which handles memory management requests to the OS, among other things), some libraries, and utilities.

> Isn't memory managed by the operating system? Why is allocation of storage done by the compiler and at what point? Probably what variables are needed and how much may be known by the compiler but, how does it communicate this information to the OS?

Hardware *memory address reservation* is managed by the OS.

Specifics of the complexity of memory management intervention provided by the RTE is going to be specific to the RTE implementation. Some provide more features than others.

The Java Virtual Machine makes the alloc/dealloc *requests* to the OS on the behalf of the executing programs. It also has a Garbage Collection cycle which looks for and frees memory reservations that are no longer being used by the program, rather than holding them all until execution halts.

In C, it is the explicit responsibility of the executing program to make these requests to the OS. Memory requested remains reserved until the program halts, or the memory is explicitly released by the program.
> 0 votes

# Answer
(Your question seems to be about concepts and terminology. The meaning of termini depends on context - the quote is from a compiler writers' book. Not only are the authors entitled to a "compiler centric" view of things: that perspective is to be expected.)

There are at least two "CS" interpretations to *runtime environment*.
One is the process/OS level - some lump of hardware turned into a MINIX machine, an OS/400, QNX, z/OS, Multics one, defined in an applicable application binary interface (ABI).
At this level, memory usually gets allocated in *segments* or *pages* (taking care no information *leaks*). (In a conventional OS,) Requirements like amount and initialisation are taken from an "executable file" in an appropriate format.
It is a matter of definition whether "the compiler" is responsible for the generation of such a file from source code or just some intermediate code which may be executed by an interpreter, or statically analysed&improved, turned into assembly language, assembled into an object file/module, linked with other modules.

To me, the *existence* of a *virtual machine* is a philosophical question (as opposed to the existence of the computing hardware heating up my environment) - I take the pragmatic stance of accepting help, from a mere concept when that is what it is. Proponents of something like the Java virtual machine (JVM) (a popular target for compilers, btw.) are entitled to making the case for VM existence.

Regarding exactly *when* the compiler *does* something, anything going on during execution of the compiler should be beyond doubt. A compiler-centric view may include anything from decisions made during the specification of the compiler (like row-major or column-major layout of two-dimensional arrays) up to and during the execution of the compiled program - anything not due explicitly to a specific part of the source code, but the language specification *implemented by the compiler*.

This is the programming language level - what gets your `main()` running (and possibly constructors&co. of statically allocated objects before that), that `Begin…End;`-block implicitly prefixed with `Simula` \- you name it. It takes care of memory(/address) allocation (and possibly initialisation) for a subroutine call stack (per coroutine/thread), "statically allocated" program data (those `objects named in the source program` \- on behalf of the program source code/the coder/the one who started the program), "automatically allocated" space (e.g., for "local" variables in potentially recursive subroutine calls), "dynamically allocated" space (e.g. objects for linked data structures. "dynamically": as need arises during program execution, a "program request" for (memory for) another object may lead to the language runtime environment requesting more memory from the OS - often, the RTE manages a memory pool for smallish requests and makes largish ones to the OS).
"The compiler" decides about memory layout for multi-dimensional arrays. It arranges access to machine code for the "runtime library" - with OS support more often than not.
In all, a Forth machine, a Java, Fortran, Beta one.

Note that

* the paragraph quoted does *not* say the `compiler [executes] the code`
* *`creates and manages`* needs interpretation/leaves room for it
* one resource managed by one authority doesn't preclude the same resource being managed by another one - expect conflicting responsibilities handled usefully.
> 0 votes

---
Tags: terminology, compilers
---


# Question
Title: What does the search problem imply about the decision problem?
Let $\Pi\_{dec}$ be an NP-complete decision problem and let $\Pi\_{opt}$ be its corresponding optimization problem. Assume $\Pi\_{opt}$ can be solved in polynomial time.

1. What does this imply for $\Pi\_{desc}$?
2. What does this imply for the class of NP-complete problems and the class NP, respectively.

I am not sure of my answers. For #1, I said that this does not imply anything. For #2, I don't really have any idea. Why would it say anything about NP problems?

# Answer
Let us take as an example MAX CUT.

The optimization problem is: given a graph $G$, find the value of the maximum cut.

The decision problem is: given a graph $G$ and an integer $k$, determine whether there is a cut of value at least $k$.

If we can solve the optimization problem, then we can solve the decision problem: just compare the value of the maximum cut to $k$.

Conversely, if we can solve the decision problem, we can solve the optimization problem, using binary search.
> 1 votes

---
Tags: complexity-theory, algorithm-analysis, decision-problem, search-problem
---


title: How to prove graph isomorphism is NP?

text:
# Question
Title: How to prove graph isomorphism is NP?
I know that Graph Isomorphism should be able to be verified in polynomial time but I don't really know how to approach the problem. Any help would be appreciated.

# Answer
You haven't explained what graph isomorphism means for you, so let me assume that you mean the language of all pairs of graphs $(G\_1,G\_2)$ which are isomorphic.

Two graphs $G\_1 = (V\_1,E\_1),G\_2 = (V\_2,E\_2)$ are isomorphic if there exists a bijection $f\colon V\_1 \to V\_2$ such that $(x,y) \in E\_1$ iff $(f(x),f(y)) \in E\_2$.

You take it from here.
> 7 votes

---
Tags: complexity-theory, np, graph-isomorphism
---


# Question
Title: How do I reduce subset sum to another problem in NP?
I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following.

Given $n$ integers $l\_1, \dots l\_n$, the lengths of the pens, r rows and a goal G. Is it possible to arrange the pens where each row has a maximum length G, where G is the minimum possible.

I have shown that this problem is in NP, but now I'm trying to reduce a subset sum problem to this problem with karp reduction.

I know how the subset sum problem looks like, but I'm having a trouble where to start with the reduction, any tips would be greatly appreciated.

# Answer
Let $S, k$ be a given instance of the subset sums problem. The goal is to build an equivalent instance of your problem (let us call it the pens arrangement problem). In the subsetsums problem, we are looking for a subset of the given set that sums up to $k$. So it is intuitive to set $G$ to $k$ and set the lengths of the pens to be the numbers in the given set.

However, In the subset sums problem, if you found a subset that sums to $k$ the rest will sum up to a number equal to $\sum\_{a \in S} a -k$ which might be not equal to k and hence might generate a problem. An easy solution is to add one number to set, namely $\sum\_{a \in S} a - 2k$. And change k onto$\sum\_{a \in S} a - k$. By this changes we turned the subset some problem into the two partitioning problem, where we are looking for a subset of the given set that sums up to half the sum of the elements in the setand hence, the rest of the elements have the same sum. After this step we canset the number of rows to two and the columns to the new value of $k$. Try to prove why this reduction works.
> 4 votes

---
Tags: algorithms, complexity-theory, reductions, np-hard
---


# Question
Title: Splitting a node in B+ tree with odd number of keys
This and several other resources suggest to *"Always a node that gets the middle key from bottom splits, should drop one item for a new middle key"*.

To illustrate with an example.

**For 5-way B+-tree,**

(24, 25, 44, 79) is one of the leaf nodes with its root being (..,24,80,...)

```
(..,24,80,...)
      \
       \
        \
       (24, 25, 44, 79)

```

After Inserting 40.

The node (**24, 25, 40, 44, 79)** gets overloaded and is forced to split(considering the siblings are full as well).

In such a case, is there any advantage of splitting it as

(**24, 25) (40, 44, 79)** over (**24, 25, 40) (44, 79)**

Is this split A

```
(..,24, 40, 80,...)
         | \
         |  \
         |   \
    (24, 25)  (40,44, 79)

```

better than this split B?

```
 (..,24, 44, 80,...)
          | \
          |  \
          |   \
 (24, 25, 40)  (44, 79)

```

If so, what makes A correct and B wrong, considering that both are satisfying the rules of the B+ tree.

I couldn't find any resource to back my argument that B is equally correct as A.

# Answer
There is no advantage to choosing one over the other.

"Real" B+-tree implementations will often rebalance if they can, rather than splitting. When a node becomes overfull, if there is a sibling (whether to the left or the right) which isn't yet full, it's often better to balance the entries evenly between this node and its sibling. This saves an allocation.
> 1 votes

---
Tags: data-structures, balanced-search-trees, b-tree
---


# Question
Title: Graph theory: BFS (Breadth First Search) - why is current processed first?
I am referencing some code I found on GeeksForGeeks.com: Why is the current node printed (and processed) first before its children are processed? Wouldn't "breadth first" mean "Process children first, then process parent"? or, is that only for Trees? I can't be the only one to not understand this, so instead of flaming me, somebody please simply post the answer?

```
void Graph::DFSUtil(int v, bool visited[])
{
    visited[v] = true; <-- why is this printed FIRST?
    cout << v << " ";

    // Recur for all the vertices adjacent
    // to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function
    // to print DFS traversal
    DFSUtil(v, visited);
}

```

# Answer
> 1 votes
1) In answer to the semantic question "Wouldn't 'breadth first' mean 'Process children first, then process parent'?"

This question is a duplicate of the following: What is the meaning of 'breadth' in breadth first search?

2) In answer to the technical question "Why is the current node printed (and processed) first before its children are processed?":

BFS processes nodes in the following order: the starting vertex, then all the vertices at distance 1, then all the vertices at distance 2, etc. As pointed out by @user111398, you need to mark a node as visited before processing it or you will go on an infinite loop if the graph is cyclic. If you mark the parent but don't process it before (marking and) processing its children then you are processing the nodes in the following order: all the nodes at max distance, then all the nodes at max depth minus one, etc. This is reverse-BFS, not BFS.

# Answer
> 0 votes
Trees are acyclic. If you have for instance the directed graph $(1,2),(2,1)$ and try running the algorithm with marking visited after the recursive call, you will get a stack overflow. Or for an undirected graph you can consider a triangle $(1,2),(2,3),(1,3)$ which will result in the same thing. For acyclic graphs this issue won't arise so mark visited in either place.

---
Tags: graph-traversal
---


# Question
Title: What category does questions like "Given n points on 2D plane find ..." belong to
Not after a specific answer, do following questions belong to same set of problem types?

Given n points in on 2D plane, find 4 or 5 , or m subset of points with less total distant to each other than all other points.

Or

Given n points in on 2D plane, count the number of triangles, squares etc. that they form.

Or

Given n points in on 2D plane, find a point that is closeses to most number of points as possible.

are these optimisation questions? or is there another name for above type of questions, or there can be no category for all the questions of type

Given n points in on 2D plane, find $\cdots$

This question did not seem to be fit for SO or Software engineering, so I am asking it here, if there is better SE to ask this question I'll delete this question and ask it there ( in reverse order ).

# Answer
Combinatorial geometry.

http://mathworld.wolfram.com/CombinatorialGeometry.html

Computational geometry.

https://en.m.wikipedia.org/wiki/Computational\_geometry
> 1 votes

---
Tags: terminology
---


# Question
Title: What's the correct algorithm to filter accumulating string concatenations?
I have a function that is receiving messages with the following pattern:

(In this picture, "string" and "message" are synonymous.)

I'm only interested in the largest messages, such as these:

over a particular window.

Is there an algorithm that can appropriately filter the messages in the desired manner over a specified window?

# Answer
Store them in a heap or priority queue, keyed on the size of the message. This way, if you want the $k$ largest messages, you can keep track of that as each message arrives. This will require $O(k)$ space to keep track of the $k$ largest messages at each step, and $O(\log k)$ time per message that arrives, so it should be pretty efficient.
> 1 votes

---
Tags: algorithms, optimization, filtering-problem
---


# Question
Title: Algorithm for computing $Pr[s \vDash C \bigcup^{\geq n} B]$ for probabilistic verification
I'm having some difficulty trying to come up with an algorithm for computing $Pr\[s \vDash C ~\bigcup^{\geq n} B\]$ given a finite Markov chain where $S$ is the set of states, $s \in S$, $B,C \subseteq S$, and $n \in \mathbb{N}$ where $n \geq 1$.

I have algorithms for computing $Pr\[s \vDash C~\bigcup~B\]$, $Pr\[s \vDash C~\bigcup^{\leq n}~B\]$, and $Pr\[s \vDash C~\bigcup^{=n}~B\]$. Instead of going down to the Markov chain itself I was thinking of using a combination of these algorithms to calculate $Pr\[s \vDash C ~\bigcup^{\geq n} B\]$, however, I'm worried about overcounting as it is not necessarily true that $B$ and $C$ are disjoint.

I am using the Principles of Model Checking book by Baier and Katoen.

# Answer
> 1 votes
To compute the probability for $\geq n$, you first compute the probability for an unbounded until and subtract from it the probability for $\leq n-1$. If you compare the sets of paths these formulas represent then you will that they are indeed the same. You start off with a set of all paths satisfying "reach B via C", let's call it $T$. From this set, you remove any paths where B is reached in $\leq n-1$, let's call it $U$. So the set of paths where B via C is reached in $\geq n$ steps is represented by $T \setminus U$. Using properties of probability measures, you can write $Pr(T\setminus U) = Pr(T) - Pr(U)$.

You can safely assume that $B$ and $C$ are disjoint without loss on generality. If they are not, then reaching a state from $B \cap C$ satisfies the "until", so you can just consider $(C\setminus B) \bigcup B$.

---
Tags: algorithms, software-verification, model-checking, markov-chains
---


# Question
Title: Grover's algorithm on probabilistic classical machines
As a starting point for this question, I came across this question, which AIUI is citing a construction showing how to simulate quantum circuits with a $PP$ algorithm, i.e. implying quantum computation in general is in $PP$.

However, it struck me as counterintuitive to say that the *only* way to implement a specific example of QC, like Grover's algorithm, would be to do so by emulating a quantum computer and running it in there. I then tried to imagine what implementing it more naturally might look like, e.g. operations in terms of list items directly rather than transforming them into a quantum state vector.

For background, I understand that non-$BPP$ algorithms in $PP$ are allowed to be arbitararily close to random, and so we potentially need to repeat them exponentially many times to arrive at any particular confidence in their answer. I'm specifically interested in what a *single* iteration (that then needs to be repeated exponentially many times) of a Grover-like algorithm looks like. I presume, from the fact that the translation in the linked thread is 1-1, that this single iteration would be expected to take $O(\sqrt n)$ time, but please let me know if this inference is incorrect.

(I'm also presuming that this Grover-like algorithm is **not** in $BPP$, because otherwise search theory would be very different. It being outside $BPP$ means we're talking about a search algorithm that in practice takes $O(2^\sqrt n)$ time, which isn't going to revolutionize anything.)

Also, since $PP$ is generally defined in terms of binary decision problems and Grover's algoritm is not one, I had to extrapolate slightly about what the success criteria looks like in a $PP$ rather than $BQP$ context. The criteria I tentatively came up with is that the algorithm should be create and pick from a probability distribution over the $N$ items of a list, with the property that the most likely item to be selected is the (a, if more than one) item marked by the oracle function, i.e. it has the pluarity, *but not necessarily majority*, of probability mass.

That has the obvious caveats that because the list in general contains more than two items, it is not more likely than not that that item gets selected, only that no single item is more likely. The difference in probability between the most and second-most likely items being chosen is also allowed to be arbitararily small. An algorithm that returns the marked item from a list of $N$ with probability $\frac{1}{N}+2^{-N}$ would be allowed so long as all other items were less likely.

Is there any existing work on algorithms that achieve the corresponding outcome as Grover's (or similar specific quantum algorithms), but in more direct/natural terms?

# Answer
> 2 votes
Let $F$ be a function that maps integers from $0 \dots N-1$ to $\\{0, 1\\}$. We want to find $x$ (which is promised to be unique) such that:

$$F(x) = 1$$

Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output:

1. $b$, if $F(a) = 0$
2. $a$, if $F(a) = 1$

For any fixed $x$ and $y$ we have:

$$P\_{a=x} = P\_{b=x} = P\_{a=y} = P\_{b=y} = \frac{1}{N}\\ P\_{a \ne x} = P\_{b \ne x} = P\_{a \ne y} = P\_{b \ne y} = \frac{N-1}{N}$$

Knowing that $a$ and $b$ are independent random variables, the probability that we output $x$ is

$$P\_{a = x \lor a \ne x \land b = x} = P\_{a = x} + P\_{a \ne x} P\_{b = x} = \frac{1}{N} + \frac{N - 1}{N^2}$$

and the probability that we output some other value $y \ne x$ is

$$P\_{a \ne x \land b = y} = P\_{a \ne x} P\_{b = y} = \frac{N - 1}{N^2} \< \frac{1}{N}$$

---
Tags: algorithms, complexity-classes, probabilistic-algorithms
---


# Question
Title: Need clarification regarding certificates of coNP problems
**NOTE**: this is **not** an attempt to prove $NP \neq coNP$

There is one thing I have never been able to completely digest about the certificates of problems in $coNP$ and I would very much appreciate a definitive clarification from this community.

Let's focus on the subset sum problem ($SUBSUM$), now we all know that this problem is in $NP$ since, to accept language membership, a Prover $P\_v$ can emit a certificate which a verifier $V\_r$ can check in polynomial time. Up to here no problem. The complement of this problem ($\overline{SUBSUM}$) is in $coNP$ which means that we do not know if there is a *succinct* (ie polynomial) certificate to decide the language. If such a certificate does not exist, then $NP \neq coNP$ and therefore $P \neq NP$. What I don't understand is this:

If I have (for example) a set $S$ of integers and the number $0$ as an input and I ask: Prove me that $\forall s \in S \space\space\lnot SUBSUM$, ie $\nexists$ a subset of $S$ such that the sum of its element give $0$ as a result (this is $\overline{SUBSUM}$, the complement of the subset problem). How can a certificate exist for this problem whose verification is in $P$? I mean, i need to prove it for all the subset so the search space must be the powerset of $S$. If $|S|=n$ then $\mathcal{|P(S)|}=2^n$. So if the prover, for example, produce a $2^{n/3}$ certificate, this means that I systematically leave out $2^{ \frac{2}{3}n}$ subsets. What I don't completely understand and for which I need clarification is why this argument is not accepted as evidence that $NP$ is not closed under complement.

# Answer
The proof does bot need to be a subset. It might be another indicator that the given set has a some stricture preventing it from being a positive instance of the subsetsums problem. A good example with a non-trivial certificate is linear programming. Linear programs admit both a positive and a negative certificate (For the question whether the optimal can be smaller/greater than a value k). The positive instance is of course an assignment of the variable. The negative however is given by Faraks lemma and the weak duality.

A good exercise for you is to look up linear programs, weak duality and Farkas lemma :)
> 2 votes

---
Tags: proof-techniques, co-np
---


# Question
Title: Assuming P != NP, what is the cardinality of the set of NP-Hard languages?
If P=NP, then every non-trivial language is NP-Hard, so clearly there are uncountably many NP-Hard languages. However it's less clear to me what the cardinality of this set is assuming P != NP.

# Answer
> 8 votes
Any upwards-closed non-empty class $\mathfrak{L}$ of languages has the cardinality of the continuum, with very few limitations on what kind of reasonable reducibility we are looking at. The reason is if $A \in \mathfrak{L}$ and $B$ is an arbitrary language, then the language $A + B = \\{0w \mid w \in A\\} \cup \\{1w \mid w \in B\\}$ satisfies that $A \leq A + B$, hence $A + B \in \mathfrak{L}$. Since $A + B = A + C$ iff $B = C$, we see that $B \mapsto A + B$ provides an injection from the all languages into $\mathfrak{L}$.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Traversing the edges of a labeled 2-regular graph based on a binary string
Let $G$ be a $2$-regular graph. Each edge of the graph is labeled with either 0 or 1. Given a such a graph and a staring vertex $u$ and $l$ length string of 0 and 1, we have to follow the edges of the graph $G$ based upon given string. We can assume that a solution always exists.

What is the best algorithm for such problem? I can solve this problem in $O(l)$ time. I am looking for an algorithm with better runtime answer.

# Answer
Note that a 2-regular graph is a disjoint union of cycles. Since you have a designated starting vertex $v$, you can disregard all cycles not containing $v$. Put differently, we can assume that the input graph is a single cycle (whose edges are labeled with zeros and ones).

Your current $\Theta(\ell)$ solution is optimal since even reading the input requires time linear in $\ell$, i.e., there exists no faster algorithm.

As a side note, the problem of finding an alternating 01-path is NP-hard for the general graph. Indeed, looking for such a path of length $m = |E|$ is equivalent to finding an alternating Hamiltonian path which is known to be NP-hard. This problem is easy for cycles of course.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Determine aproximation factor in a greedy algorithm
> Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences. We want to choose a menu such that we minimize the cost and such that at least one preference for each guest is satisfied.

I implemented an easy greedy algorithm that orders each element in respect of their $\frac{\text{# of people satisfied}}{\text{cost}}$ for example if element "a" satisfies 3 people if choose and has a cost of 10, its ratio would be $3/10$. I chose each element in a non-increasing order. Until i run out of people to satisfy.

How do i find the approximation factor for this algorithm? I think it should be around 2 since it's very similar to a greedy approach to knapsack problem, but i have no clue on how to demonstrate it.

# Answer
So if you are not updating the #satisfied/cost ratio after every selection, this algorithm won't perform well. Let $n$ be the number of people and $m$ the number of meals. We denote the cost of meal $i$ by $w\_i$. Let's say people $1...n-1$ are all satisfied by meals $1...m-1$ which all have the same cost, but person $n$ will only eat meal $m$. If the cost of meal $m$ is any more than $w\_1/(n-1)$, then your algorithm will select every meal.

If we instead modify the algorithm so that after every meal selection we recalculate the ratio excluding people that have already been satisfied, we can prove that the bound is $H\_d$, where $d$ is the maximum number of people that a single menu item can satisfy and $H\_d$ is the $d$th harmonic number.

Consider instead framing the problem as a weighted set cover problem. Each meal $i$ covers some subset of people $S\_i \subseteq \\{1,...,n\\}$ and has a weight $w\_i$. You want to select meals such that all people are covered and the cost of the meals is minimized. The slightly modified version of your algorithm below is an $H\_d$ approximation to the weighted set cover problem. The proof is rather involved and can be found in section 5.3 here. Note that $j\gets \arg\min\_k\frac{w\_k}{|S\_k\bigcap Uncovered|}$ in the algorithm is equivalent to selecting the max in your ratio i.e.

$$\arg\min\_k\frac{w\_k}{|S\_k\bigcap Uncovered|} = \arg\max\_k\frac{|S\_k\bigcap Uncovered|}{w\_k}$$ The algorithm is below:
> 2 votes

---
Tags: algorithms, linear-programming, greedy-algorithms, knapsack-problems
---


# Question
Title: Do any decision problems exist outside NP and NP-Hard?
This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP *nor* NP-hard.

In order to be in NP, problems have to have a verifier that runs in polynomial time on a deterministic Turing machine. Obviously, all problems in P meet that criteria, but what about the problems with sub-exponential complexity? They do not belong to P and it's not obvious to me that they all have efficient deciders. And they certainly don't qualify for NP-complete.

I'm willing to believe that all decision problems are either NP or NP-hard or both, but nobody has actually *said* that (that I can find). I'm also willing to believe that such problems do exist, even if they are very contrived. Maybe someone more knowledgeable can put this issue to rest for me. Thanks.

**Edit**

I abused the term 'subexponential' in my question. In my mind it meant some problem with a complexity between exponential and polynomial like L-notation in this table. See the links in Raphael's answer for more details.

# Answer
> 14 votes
If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case.

If, however, $P \neq NP$, then there are languages which are neither in NP nor NP-hard.

For example, we can consider the language $\\{1^n \mid \text{the } n\text{-th TM halts}\\}$. As this language is not computable, it is clearly outside of $NP$. As this language is sparse, $P \neq NP$ together with Mahaney's theorem implies that it is not NP-hard.

If we want a computable counterexample, we can take a language $L$ that is not in EXPSPACE. We number all finite words in increasing order as $(w\_n)\_{n \in \mathbb{N}}$, and now consider the language $L' = \\{1^n \mid w\_n \in L\\}$. Again, Mahaney's theorem ensures that $L'$ is not NP-hard. If $L'$ were in NP (or even PSPACE), then an EXPSPACE algorithm for $L$ would be available in "Given w\_n, compute 1^n and run the PSPACE-algorithm for $L'$ on it."

See here https://math.stackexchange.com/questions/235162/if-an-unary-language-exists-in-npc-then-p-np for a proof of Mahaney's theorem. Note that Yuval speaks about starting with an NP-complete unary language, that assumption is not used - the argument only needs an NP-hard unary language.

# Answer
> 3 votes
Assuming $P\not=NP$ there are lots of problems incomparable with $SAT$, hence neither $NP$ nor $NP$-hard.

Here's an overkill generalization of this fact:

> Suppose $X\not\in P$. Then there is some $Y$ such that $Y$ is incomparable with $X$ under polynomial-time-Turing reducibility *(hence a fortiori Karp reducibility)*.

(So in particular if $P\not=NP$ we get an affirmative answer to the OP.)

One way to prove this is with **forcing**. Fix an $X\not\in P$ and let $Y$ be sufficiently generic with respect to $X$ *($2$-generic with respect to $X$ is already overkill)*. Since only countably many things are reducible to $X$, a sufficient level of genericity will ensure that $Y$ is not reducible to $X$. So we only have to treat the possibility that $Y\ge\_pX$.

By genericity, if $Y\ge\_pX$ there is some condition $\sigma$ *(= "finite initial segment" of $Y$, thinking of languages as infinite binary strings)* such that for some number $e$ and polynomial $p$, $\sigma$ forces "$\Phi\_e$ is a $p$-bounded Turing reduction of $X$ to $Y$." But this lets us compute $X$ in polynomial time as follows: to tell whether $n\in Y$, we just check whether $$\Phi\_e^{\sigma^\smallfrown 1^{p(\vert n\vert)}}(n)\downarrow=1,$$ which can be done in polynomial time.

*EDIT: note that this argument produces **non-decidable** languages since "sufficiently generic" languages are not decidable. This is both good and bad: it shows that in a strong way that "hard to compute" and "computes a lot" aren't really the same, but it also means that the examples so produced aren't of general complexity-theoretic interest. Constructing decidable examples takes a finer-grained argument, and Arno's answer does precisely this. In general forcing arguments can often prove very broad results in quite snappy ways, but usually don't result in "nice" objects. The original example of this is probably the fact that forcing can build incomparable $\Delta^0\_2$ Turing degrees but we need priority arguments to build incomparable c.e. Turing degrees, but Baker-Gill-Solovay provides another good example since there is - to my knowledge - no known "nice" oracle relative to which we have $P=NP$, despite the existence of such being not too hard to prove via forcing.*

---

The proof above immediately yields a strengthening of the claim: for any $X$, the set of sufficiently generic $Y$s is always *comeager*, so in a precise sense "most" languages will be incomparable with $X$ as long as $X\not\in P$.

*(I strongly suspect the same is true for measure as well, but I don't have an argument at the moment.)*

---
Tags: complexity-theory, np-complete, np-hard, decision-problem, complexity-classes
---


# Question
Title: Proving that any CF language over a 1 letter alphabet is regular
I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far:

Let $L$ be a context free language. So, $L$ satisfies the pumping lemma. Let $p$ be $L$'s pumping constant. Let $L = L\_1 \cup L\_2$ where $L\_1$ consists of $w$ where $|w| \< p$ and and $L\_2$ consists of $w$ where $|w| \ge p$. We have a single letter alphabet and since $L\_1$ has a restriction on the length of its words, $L\_1$ is a finite language. Finite languages are regular so $L\_1$ is regular. If I can show that $L\_2$ is regular, I can use the fact that the union of regular languages is regular. But I am struggling on showing that $L\_2$ is regular. I know that since $w \in L\_2$ has to satisfy $|w| \ge p$, by the pumping lemma, $w$ can be written as $w = uvxyz$ where $|vxy| \le p$, $|vy| \> 0$ and $\forall t \ge 0$, $uv^txy^tz \in L$. Since we have a single letter alphabet (say the letter is $a$), $uv^txy^tz = uxz(vy)^t = uxz(a^{|vy|})^t \in L$. Now what?

# Answer
You have shown that for any given $w = uvxyz = a^{|uxz|+|vy|}$ there is a regular language $L\_w = a^{|uxz|+|vy|\cdot t} \subset L\_2$. Now you need to show that $\bigcup L\_w = L\_2$ and that this can be a finite union. Note that $|vy| \leq p$ and that $a^{(|uxz|+|vy|)+|vy|\cdot t} \subset a^{|uxz|+|vy|\cdot t}$ so not all values of $|uxz|$ matter.
> 2 votes

# Answer
Let $L$ be a unary context-free language. According to the pumping lemma, there is a constant $p$ such that if $a^n \in L$ then either $n \< p$ or there exists $q \in \\{1,\ldots,p\\}$ such that $a^{n+tq} \in L$ for all $t \geq 0$ (actually, the pumping lemma gives $t \geq -1$). Let $L\_0$ be the set of words in $L$ of length smaller than $p$, and for $q\_0 \in \\{1,\ldots,p\\}$, let $L\_{q\_0}$ be the set of words in $L$ of length at least $p$ for which the pumping lemma gives $q = q\_0$. I claim that $$ L = L\_0 \cup \bigcup\_{q=1}^p \\{ a^{n+tq} : a^n \in L\_q, t \geq 0\\}. $$

Proof of $ \subseteq $: If $x \in L$ then either $|x| \< p$, in which case $x \in L\_0$, or $|x| \geq p$, in which case $x \in L\_q$ for some $q$, and so $x$ belongs to the $q$'th summand on the right (choosing $t = 0$).

Proof of $ \supseteq $: This follows directly by definition of $L\_0$ and $L\_q$.

Since $L\_0$ is finite, it is regular. Hence it suffices to prove that for each $q \in \\{1,\ldots,p\\}$, the following language is regular: $$ R\_q := \\{ a^{n+tq} : a^n \in L\_q, t \geq 0\\}. $$ Let us write, for $0 \leq r \leq q-1$, $$ R\_{q,r} := \\{ a^{n+tq} : a^n \in L\_q, t \geq 0, n \equiv r \pmod q \\}, $$ so that $R\_q = \bigcup\_{r=0}^{q-1} R\_{q,r}$. Thus it suffices to prove that each $R\_{q,r}$ is regular.

If no $a^n \in L\_q$ satisfies $n \equiv r \pmod q$, then $R\_{q,r} = \emptyset$ is clearly regular. Otherwise, let $n\_{q,r}$ be the minimal $n \equiv r \pmod q$ such that $a^n \in L\_q$. I claim that $$ R\_{q,r} = \\{a^{n\_{q,r} + tq} : t \geq 0\\} = a^{n\_{q,r}} (a^q)^\*, $$ and so $R\_{q,r}$ is regular.

Indeed, clearly $R\_{q,r}$ contains the right-hand side. On the other hand, suppose that $a^m \in R\_{q,r}$. Then $m = n+tq$ for some $n \equiv r \pmod q$ and $t \geq 0$ such that $a^n \in L$. But then $m = n\_{q,r} + (t+(n-n\_{q,r})/q)q$ (our choice of $n\_{q,r}$ guarantees that $n \geq n\_{q,r}$ and that $n-n\_{q,r}$ is divisible by $q$), and so $a^m$ is an element of the right-hand side.
> 3 votes

# Answer
This is a special case of Parikh's theorem. You can find a proof in lecture notes of Lindqvist (linked in the Wikipedia article). In fact, Parikh's theorem is a bit more general: it states that the histograms of all words in a context free language are "regular" (for an exact statement, see the link).
> 2 votes

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


# Question
Title: Hausdorff distance between two binary images according to distance maps
I want to compute the Hausdorff distance between two (very large) binary images X and Y, which is:

$$H(X,Y) = \max\left\\{\\,h(X,Y), h(Y,X)\right\\}\\!$$

with

$$h(X,Y) = \sup\_{x \in X} \inf\_{y \in Y} d(x,y)$$

$d$ being the euclidean distance (or any kind of distance, as it doesn't matter).

The naive algorithm for $h$, comparing each pixel of $X$ to each pixel of $Y$, leading to a complexity of $O(X\*Y)$, is way too slow.

I have read many papers saying it is possible to compute the Hausdorff distance in $O(X+Y)$ by first calculating the distance map (distance transform) of $X$ and $Y$.

I can easily compute these distance maps, but I don't see how they can lead to the Hausdorff distance, and I did not manage to find the algorithm in any of these papers.

So the question is, does anyone know how to compute the Hausdorff distance of two images according to their distance map ?

# Answer
> 5 votes
So I finally managed to do it, here's the answer for future reference.

The idea is not to compute the distance map of the image, but of its complement.

Here's a example to better understand :

You have these binary images, where our objects are in black :

## Object $X$

## Object $Y$

To compute $h(Y, X)$, you need to compute the distance map $dX$ of the complement of $X$ (here using 4-adjacency, but work the same with any distance):

The distance is 0 on the object.

You now only need to find the $max(dX\[i,j\])$ such as $Y\[i, j\]$ is in the object.

Here's our example with $Y\[i, j\]$ in the object in orange, and the $max(dX\[i,j\])$ in red :

So $h(Y, X) = 3$.

$h(X, Y)$ is computed in a similar fashion, using $dY$ and $X$.

Now that you have $h(X,Y)$ and $h(Y,X)$, you can easily compute the Hausdorff distance $H(X,Y) = \max\left\\{\\,h(X,Y), h(Y,X)\right\\}\\!$.

If you already have your distance map, the complexity of the Hausdorf distance is obviously $O(X + Y)$ with this algorithm since you only need to iterate one time over each image.

Note that computing the distance matrix is also done in linear time, so its always better to go with this method instead of the naive one.

Here some sources:

---
Tags: algorithms, image-processing
---


# Question
Title: Prove that $\text{EF p}$ can't be written in LTL
Why can't we somehow represent it's negation in LTL and go from there? I think maybe because it has (effectively) two existential quantifiers, so negating it does not work. But how do I prove it?

# Answer
There is a delicate point here, about the semantics of LTL vs CTL.

Given a formula $\psi$ in LTL, we say that it holds in a structure $K$ if *every* path in $K$ satisfies $\psi$.

In CTL, however, the path quantifiers are built in to the formula.

To make this more precise, you can think of LTL as the fragment of CTL\* of the form $A\psi$, where $\psi$ doesn't contain any path quantifiers (i.e., it's in LTL).

Now, you suggest negating your formula, so you obtain $AG\neg p$. This formula is not an LTL formula, due to the quantifier $A$. But it does have an LTL equivalent, namely $G\neg p$.

However, if you try to negate back to CTL, the negation of the LTL formula is now $Fp$, but the semantic of LTL means that it is interpreted as $AFp$, whereas you wanted $EFp$.

To sum up, you just cannot express the path quantifier $E$ in LTL.

To prove that the formula $EFp$ does not have an LTL equivalent, consider (towards a contradiction) some equivalent LTL formula $\psi$, and take a structure that has two "branches" -- one with $p$ and one without (e.g., two states with self loops). Since this structure satisfies the $EFp$, then it also satisfies $\psi$, meaning that every computation in it satisfies $\psi$. But now, if you remove one of the branches (the one with $p$), then $\psi$ is still satisfied (since you only removed computations). However, $EFp$ is not satisfies, so $\psi$ is not its equivalent.
> 1 votes

---
Tags: linear-temporal-logic, temporal-logic
---