# Question
Title: Why is the base used to compute hashes in Rabin–Karp always primes?
The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is $$ h(x\_0\ldots x\_n) = \sum\_{i=0}^n b^i x\_i, $$ where $b$ is *prime* (all computations are module $2^w$, where $w$ is the width of a machine word). Why is it important for $b$ to be prime?

# Answer
A quick recap first. We are looking for a pattern $P\[1\ldots m\]$ in a string $S\[1\ldots n\]$. The Rabin-Karp algorithm does this by defining a hash function $h$. We compute $h(P)$ (that is, the hash of the pattern), and comparing it to $h(S\[1\ldots m\])$, $h(S\[2\ldots m+1\])$ and so on. If we find a matching hash, then it is a potential matching substring.

The efficiency of the algorithm depends on the ability to compute $h(S\[r+1\ldots s+1\])$ efficiently from $h(S\[r\ldots s\])$. This is called a "rolling hash". Note that *any* efficient rolling hash function will do, and it's still Rabin-Karp. The question that you're asking about is one particular choice of hash function, where you use:

$$h(S\[r\ldots s\]) = \sum\_{i=r}^s S\[i\]\\, p^{s-i} \bmod q$$

where $p$ is a prime number with roughly the same order of magnitude as the size of the character set, and $q$ is another prime number which defines the cardinality of the range of the hash function, typically of the same order of magnitude as a machine word divided by the character set size. If I'm reading it correctly, you're asking why $q$ has to be prime.

In fact, this is a more general question. In a lot of the old (and current) literature on hashing, the advice is that the hash function should be taken modulo a prime number (e.g. hash tables should have a prime size).

For a hash function to be as useful as possible, its range needs to be relatively uniform, even when its domain is not. Natural language text (say) doesn't have a uniform frequency distribution, but hash values should be.

If $q$ is a prime number, then a lot of other numbers are relatively prime to it, and in particular, the sum (especially if $p$ is also prime!). This makes the frequency distribution of the hash values more uniform, even though the hash function is relatively weak.

It's important to understand that we do this *because* the hash function is weak. If the hash function were stronger, taking the remainder when divided by a prime would not be necessary; you could, for example, take the remainder when divided by a power of two, which would be a much cheaper bit mask operation. However, it's hard to design strong rolling hash functions which are cheap enough to be done for every input character in the Rabin-Karp algorithm.

Something that's worth pointing out that this "remainder of a prime" technique used to be common in many hashing applications, but this advice is inadvisable on modern hardware. It advice made sense once upon a time, because while final integer division instruction was always expensive, so were the operations that you used to compute your hash function, such as integer multiplication. On modern CPUs, it is much more expensive to do an integer division even than an integer multiplication.

Modern carry-save adder multipliers are fully pipelined, so you can have several such instructions being executed at once. Modern dividers use the SPH or Goldschmidt algorithms, which are multi-cycle and impossible to pipeline. Goldschmidt dividers also tie up the multiplication unit, making the performance hit even greater.

I've had programs where this division instruction was the bottleneck, and the annoying part was that it was hidden inside the standard library.

On a modern CPU, it is worth using a more sophisticated hash function built out of fully pipelineable operations (e.g. multiplies or even table look-ups) and using hash tables which are powers of two, so the modulo operation is a bit mask. Do anything to avoid that division operation.

Just not for Rabin-Karp.
> 18 votes

# Answer
Pseudonym's answer is excellent, but there's some additional points worth mentioning. The generalized version of the hash algorithm used in the RabinKarp document is;

$$h(S\[0…s\])=\sum\_{i=0}^{s}p^iS\[i\] \mod q$$

This is typically implemented as;

```
h = 0 # Sometimes initialized to a seed value instead.
for i in range(s):
  h = (p * h + S[i]) % q

```

Note that this algorithm has a lot in common with simple LCG random number generators, hence its surprisingly good almost randomly distributed output. The `c` "increment" part of the LCG is just replaced with `S[i]` byte value. This suggests that good values for `p` and `q` should probably match the criteria for good `a` and `m` values for an LCG generator, but the most important thing is that they are relatively prime, as this prevents $(p^i\mod q)$ from cycling/repeating values prematurely for different `i` values. When they are relatively prime, $p^i\mod q$ is a different value for every value of i in 0..q-1.

This is probably the core part of the answer to the original question; when mutiplying/dividing numbers, primes are less likely hit cycles/alignments. A number that has many prime factors can be evenly divided by many other different numbers; every different combination of its prime factors is another divisor, with a modulus result of zero. These lead to more repetitions/cycles/matches when operating with these numbers.

Although people often talk about making `q` prime, this reduces the effective range of the hash values for the number of bits used, and can require an expensive division operation. If you are lucky the largest prime in N bits is very close to $2^N$ so it doesn't waste much of the available hash-space, and the mod operation can be implemented cheaply using a combination of shifts and adds as is done in zlib's adler32 implementation. However, even adler32's small sacrifice of 15 values past the prime has been shown to be not worth the extra benefits of using a prime modulus value.

Another common value for `q` is $(2^N -1)$, which only wastes one hash value in $2^N$ bits and mod can be efficiently computed by just adding the carry-over bits past N back into the hash. It's not always prime, but it's often got very few prime factors so it's easy to find a `p` that is relatively prime. Importantly it's relatively prime to $2^N$, so it avoids many nasty alignments when working with binary numbers. The one omitted hash value (all 1's, or sometimes remapped as all 0's) can be used as a special sentinel value for "empty hash bucket". It turns out this is equivalent to 1's complement arithmetic, which is often used in hash algorithms like Fletcher for this reason.

The original question's variant of this is one where `q` is effectively $2^N$ for N bits of hash, and it's not usually explicitly mentioned because you get it for free when using N-bit arithmetic. In this case it's important that `p` be odd so it's relatively prime to $2^N$. It's not strictly necessary that `p` be a prime, but to avoid nasty degenerate cases in your data it's better if it has very few prime factors. The LCG recommendations also suggest $(p-1)$ be divisible by 4. In my experience it helps if it has a good distribution of 1'S over the full $2^N$ hash size to spread the bits widely over the hash each iteration. Note that most recommended LCG multiplier values are NOT prime, but they do have few prime factors.

In my experience `0x8104225` is good, but `0x41c64e6d` is another widely used LCG multiplier that works well.

Note that Gear is also similar to this but defies the rule of "`p` should be odd for $q=2^N$" and actually uses $p=2$ implemented as a left-shift. It does this to intentionally take advantage of the property that this weakens the hash by "expiring the older bytes" out of the hash, since $2^iS\[i\]\mod 2^N=0$ for $i\geq N$, avoiding the need for keeping a sliding window to calculate the rolling sum of the last N bytes.
> 4 votes

---
Tags: search-algorithms, strings, rolling-hash
---


# Question
Title: Hardness of a problem which is the sum of two NP-Hard problems
Consider the problem of computing an exponential sum over a certain function $g(x)=f(x)+h(x)$, that is computing

$$\sum\_{x}g(x)=\sum\_{x}f(x)+\sum\_{x}h(x)$$

now if we know that $\sum\_{x}f(x)$ and $\sum\_{x}h(x)$ are two NP-Hard problems, what can we say about the hardness of $\sum\_{x}g(x)$?

# Answer
> 38 votes
Nothing.

**Lower bound:** Suppose $h(x) = -f(x)$. Then $\sum\_x g(x) = 0$, which is trivial to compute. If $\sum\_x f(x)$ is NP-hard to compute, then $\sum\_x h(x)$ will be too, but $\sum\_x g(x)$ will be easy to compute.

**Upper bound:** Suppose $h(x) = f(x)$. Then $\sum\_x g(x) = 2 \sum\_x f(x)$, which is as hard as computing $\sum\_x f(x)$, which is assumed to be NP-hard. Since NP-hard means (roughly speaking) NP-complete *or harder*, there is no upper bound on the complexity; it could be arbitrarily hard to compute $\sum\_x g(x)$.

---
Tags: complexity-theory, time-complexity, np-complete, np-hard
---


# Question
Title: Which of these two functions has a higher order of growth/complexity?
Consider the following functions:

$$f(n)=2^{\log^\*n} \text{ and } g(n)=\sqrt{2}^{\log{n}}$$

Using $\log{}$ properties I think that $g(n) \< f(n)$, since:

1. $f(n)\sim n$,
2. $g(n)\sim n^{\frac{1}{2}}$, and
3. $n^{\frac{1}{2}}\<n$.

However the book that I'm reading says otherwise.

What have I gotten wrong?

# Answer
You have gotten wrong the 1st property, that $2^{\log^\*(n)} \sim ~n$. This is not the case.

The notation $\log^\*(n)$ is the *iterated logarithm*, and the iterated logarithm grows much much slower than the logarithm, so $f$ grows much slower than linearly.
> 1 votes

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


# Question
Title: Why do register machines outperform stack machines?
Wikipedia says stack machine “designs have though been routinely outperformed by the traditional register machine systems, and have remained a niche player in the market.” Why is this?

# Answer
> 3 votes
I think the prime reason why **register** machines are better at performance because **registers** are within the **CPU** chip itself, however stack is generally the part of main memory, accessing register is on average **1-3** clock cycles, **level 1 cache** requires nearly **10-20 cycles** on average, and depending on the design it could have **level 2 shared cache** which takes about **40 cycles** on average, finally main memory takes **100s** of cycles in comparison per initial word access then once you access it, the further block containing the required word is only incrementally cycle consuming. Hence register based architecture should always out perform stack based.

> The data presented is definitely not according to today's state of the art processors take it from more of a conceptual stand point rather than practical one, and that I believe was the intent of the question.

Edit : I came across one more important reason why stack machines are not as efficient as register based microarchitectures, consider the following image

the expression evaluation algorithm is compared between both stack based and register based microarchitectures, observe how variables `a` and `c` are pushed twice. The context here being, the stack based microarchitecture is implemented using a register stack, a memory based would have been far worse in terms of cpu cycles, so even the register implementation of stack based machine still performs worse than plain register based machine, due to multiple push and pops of the same variable and this is an example of a bad architectural design, where the ISA only allows stack based operations.

# Answer
> 2 votes
Stack machines have a specialized hardware architecture, which is ideal for some problems. For the vast majority of algorithms, it's not optimal. For instance, take sorting. With random access, sorting is ideally done with a variation of the common quicksort algorithm. With a single stack, you have a problem even *sorting* the stack - the vast majority of input permutations can't even be sorted!

Now real-world stack machines are a bit more flexible, but as soon as you design an architecture that allows O(1) access to the top N values of the stack, it starts to morph into an N-register CPU. Sure, you get some fancy register shuffling as the stack is pushed and popped, but modern register-oriented CPU's can do far more flexible register renaming. on the fly.

---
Tags: automata, computer-architecture
---


title: Derivation from grammar

text:
# Question
Title: Derivation from grammar
Given the grammar $G=(\\{S, L\_x, R\_x, W\_x\\}, \\{a,b\\}, P, S)$ derive the words $abaaba$ and $aabbaabb$. $$ P=\left\\{ \begin{align}S\phantom{{}\_x R\_y} &\to \epsilon \mid L\_x R\_x,\\ L\_x \phantom{R\_y} &\to x \mid L\_x y W\_y,\\ W\_x y\phantom{{}\_y} &\to y W\_x,\\ W\_x R\_y &\to R\_y x,\\ R\_x \phantom{R\_y} &\to x \\ \end{align}\right\\}$$ with $x,y$ element of $\\{a,b\\}$. ($x$ and $y$ may or may not be equal)

Following the rules I always end up with words of the form $xx, xyxy, xyyxyy, \ldots$.
Am I allowed to replace each $y$ differently? Otherwise I don't see any way to get words like $abaaba$.

# Answer
The grammar as given in your assignment is an abbreviation for the following expanded grammar:

$$P=\left \\{ \begin{align} \begin{aligned} S &\to \epsilon, \\ S &\to L\_a R\_a, \\ S &\to L\_b R\_b, \\ \\ L\_a &\to a, \\ L\_a &\to L\_a a W\_a, \\ L\_a &\to L\_a b W\_b, \\ \\ L\_b &\to b, \\ L\_b &\to L\_b a W\_a, \\ L\_b &\to L\_b b W\_b, \\ \end{aligned}\qquad\begin{aligned} W\_a a &\to a W\_a, \\ W\_a b &\to b W\_a, \\ W\_b a &\to a W\_b, \\ W\_b b &\to b W\_b, \\\\[8pt\] W\_a R\_a &\to R\_a a, \\ W\_a R\_b &\to R\_b a, \\ W\_b R\_a &\to R\_a b, \\ W\_b R\_b &\to R\_b b, \\\\[8pt\] R\_a &\to a\\ R\_b &\to b\\ \end{aligned}\end{align}\right \\}$$

So, yes, $x$ and $y$ need to be replaced consistently when you expand the shorthand notation. (And it's probably clear why the shorthand was used.)

Intuitively, what's happening here is that $S$ creates a left marker ($L\_x$) and a right marker ($R\_x$) which will eventually resolve to the same character. The left marker then expands to a sequence of $xW\_x$ pairs, where $W\_x$ is a "walker". The $W\_x$s all walk to the right; when they finally hit the right marker, they deposit their payload *after* the right marker. This has the effect of creating two copies of the same string.

In an abbreviated form (combining derivation steps) you get something like this:

$$S\to L\_aR\_a\Rightarrow L\_a b W\_b a W\_a R\_a \Rightarrow L\_a b a R\_a b a \Rightarrow a b a a b a$$

Filling in the complete derivation would be a useful exercise. (Indeed, it's the exercise you've been asked to do.)
> 2 votes

---
Tags: formal-grammars
---


# Question
Title: is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?
My understanding is that a language cannot be decided if the language is actually infinite (not generated by any machine). However, actual infinites make me squirm. Is there any reason to believe in semi-decidable or undecidable languages other than a belief in actually infinite sets?

A positive answer to this question would confirm that there are, in fact, some Machines which present an insurmountable problem for decidability.

Edit: Still not resolved. Both answers use impredicative logic or prove something irrelevant.

# Answer
We can write a computer program that will enumerate all halting computer programs. It seems that you are happy to accept accumulating the output of program into a (potentially infinite) set. Thus, you accept "all halting computer programs" as a valid set. It is, however, not a decidable set.

The standard proof of the undecidability of the Halting problem is constructive. Since we are proving a negative statement, a constructive proof is going to start with the assumption that it were decidable and going to derive a contradiction. Note that a decider by definition will answer either "yes" or "no" on any input, we can thus do the case-distinction in the usual proof of the undecidability of the Halting problem without having to involke the law of excluded middle.

Alright, so let us have a look at how exactly to prove that the Halting problem is undecidable. Bob claims the Halting problem is decidable, and we prove him wrong. Since Bob claims decidability, we can make him tell us what program he thinks does the job. Bob has to give us a program D, and the assurance that on any input w, the computation D(w) will halt and answer either "true" or "false".

Now, consider the following program:

```
E(input s)
   While {D([s]('s')} {do nothing}
   halt

```

Here, with $\[s\](\`s')$ I mean "consider s as a program, and apply this program to the input given by s considered as a string". This may feel weird, but since we have received s, we can obviously copy it and so on.

Now, modulo knowing what D is (and that's Bob's responsibility, not mine), we have a concrete piece of code up there. Call that piece of code "e". We can again treat e both as a program (which takes an input) and as a string. In particular, it makes sense to consider $\[e\](\`e')$ again, which is the program e run on the string e as input.

Bob has claimed that running $D(\[e\](\`e')$ will answer either true or false, and that this answer is about whether the computation $\[e\](\`e')$ ever halts. Since Bob so kindly provided the case distinction for us, we can exploit it.

If $D(\[e\](\`e')$ answers "true", then in the computation that happens when we run E('e') we can never escape the while-loop, so it can't halt. Bob is wrong.

If $D(\[e\](\`e')$ answers "false", then E(\`e') never enters the loop, but halts straight away. Bob is wrong, again. We won.
> 4 votes

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


# Question
Title: why quicksort can have a best big o notation of (n log n)
Why does quicksort have a big $O$ notation of $(n \log n)$.

I would like some help understanding what exactly $(n \log n)$ is, and then how it applies to quicksort.

Also in $(n \log n)$, what is the base for the $\log$?

# Answer
> 4 votes
The "standard" version of quicksort does **not** have a worst case time complexity of $O(n \log n)$. In fact, it can even require $\Theta(n^2)$ time. However, quicksort does have an **average** time complexity of $O(n \log n)$. You can get quicksort to run in $O(n \log n)$ worst-case time if you use a suitable pivot-selection strategy. In particular you want a pivot-selection algorithm that requires at most linear time to find a pivot ensuring that the two recursive calls of quicksort are performed on at least a constant fraction of the input elements. See Median of medians.

The base of the $\log$ doesn't really matter as long as it is a constant greater than $1$. This is because the big-oh notation hides constant multiplicative factors and if you consider two possible bases $a$ and $b$, you have $\log\_a n = \frac{\log\_b n}{\log\_b a}$, where $\log\_b a = \Theta(1)$. That said, $\log$ usually refers to the binary logarithm in computer science.

---
Tags: big-o-notation
---


# Question
Title: Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time
I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c\_1})$ time and $O(n^{c\_2})$ space, for some constants $c\_1$ and $c\_2$. More precisely, the algorithm should find an upper and a lower bound on the chromatic number. The closer the bounds are to the chromatic number, the better.

If it isn't clear, the input to the algorithm is a graph. The exact representation of a graph isn't fixed (that is, I will switch data structures if it makes sense).

I already know about Brooks' theorem, which gives an upper bound in linear time and constant space, but I'm hoping for something stronger.

Related Mathoverflow question: https://mathoverflow.net/questions/33812/lower-bounds-for-chromatic-number-of-a-graph

# Answer
The result of Zuckermann tells you that the chromatic number of an $n$-vertex graph cannot be approximated in polynomial time to within $n^{1-\epsilon}$, for any $\epsilon \> 0$ unless P = NP. In other words, the problem is extremely hard to approximate, so you won't find good theoretical algorithms for the problem.

However, if you care about a practical solution as you claim, i.e., you just want a solution that is computed in a short amount of time and the result is good, there are many things you can try. First, quite a bit depends on the actual instances you want to compute the chromatic number for - what do you know about their structure? For instance, are they sparse or dense?

There a many approaches to try out here. For starters, I would take some sample - representative as possible - of your instances, and see how far their chromatic number is from their clique number (i.e., the size of a maximum clique). Especially if your graphs are sparse, there are very good heuristics and exact solvers available for computing the clique number that can work even on billion-scale graphs. So that will give you a lower bound. If you want a decent algorithm for testing whether that is optimal, you can try a SAT solver. It's simple to map the graph coloring problem to an instance of SAT, and the solvers are highly practical.

Of course, you can also consider a metaheuristic for the problem, say a genetic algorithm or ant colony optimization. For any of these, you can also exploit the lower bound information given via the clique number or upper bound information given by e.g., the maximum degree.
> 1 votes

---
Tags: graphs, reference-request, approximation, polynomial-time, colorings
---


# Question
Title: What do you get when you add $O(n)$ to itself $n$ times?
I was watching this video on Algorithms and counting number of inversions and he mentioned being cautions when $O(n) + O (n) = O(n)$, saying that is not true if you add $O(n)$ to itself $n$ times. Is the answer $O(n^2)$?

# Answer
> 2 votes
The notation $O(n)$ stands for a function which is bounded by $Cn$ for some constant $C\>0$ and large enough $n$.

If you have a two functions $f\_1,f\_2$ which are both $O(n)$, then so is their sum $f\_1+f\_2$: indeed, suppose that $f\_1(n) \leq C\_1n$ and $f\_2(n) \leq C\_2n$ for large enough $n$. Then $f\_1(n) + f\_2(n) \leq (C\_1 + C\_2)(n)$ for large enough $n$.

Similarly, if you have a single function $f(n)$ which is $O(n)$ and you add it to itself $n$ times then you get a function $nf(n)$ which is $O(n^2)$.

However, this fails when you add $n$ different functions which are $O(n)$. For example, consider the functions $f\_k(n) = kn$ and the function $g(n) = f\_1(n) + \cdots + f\_n(n)$. Then $f\_k(n) = O(n)$ for all $k$, but it is not true that $g(n) = O(n^2)$; rather, $g(n) = \Theta(n^3)$. (This means that $cn^3 \leq g(n) \leq Cn^3$ for some $c,C\>0$ and large enough $n$.)

If we know that the functions $f\_k$ are *uniformly* $O(n)$, that is, there is a single $C\>0$ and a single $N\>0$ such that $f\_k(n) \leq Cn$ whenever $n\>N$, then it does hold that $f\_k(1) + \cdots + f\_k(n) = O(n^2)$.

(It doesn't suffice to require just $C$ to be uniform. For example, if $f\_k(n) = n+k^2$ then $f\_k(n) \leq 2n$ for large enough $n$, but $f\_1(n) + \cdots + f\_n(n) = \Theta(n^3)$.)

# Answer
> 0 votes
What’s both important and confusing is that the two n’s in “adding up n O(n) functions” are not the same. And each of the O(n) functions has its own C, and it’s own n0.

Obviously adding n constants (the “C”s) is not necessarily O(n), for example if the n-th function has C = 2^n. And for the k-th function, the Limitation for n (n \>= n0) might only apply for n0 = 2^k. So when you add these n functions, the Big-O limitation doesn’t apply to most of them.

---
Tags: big-o-notation
---


title: Why is augmenting path calculation O(m)

text:
# Question
Title: Why is augmenting path calculation O(m)
I'm trying to learn augmenting paths and I got confused. I've found some other source that has the same setup that my slides have, therefore I will refer to that.

It is said that

> Each augmenting path computation can be easily done in O(m) time.

in these lecture notes within a graph of m edges. I could not understand how it is O(m). Isn't trying to find an augmenting path that has capacity from source to the target an exhaustive process? Maybe I misunderstand what they mean as augmenting path computation but even if that is the case, the clarification of that would be helpful

# Answer
As given in your lecture notes, and an *augmenting path* is an s-t path in the residual graph such that all edges on the path have a positive residual capacity.

There could be many augmenting paths in the graph. But you just need to find one such path. Therefore, you can apply **DFS** or **BFS** which takes $O(m)$ time to find one such path from $s$ to $t$.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Shortest path including all nodes in a subset
Given a directed graph $G=(V, E)$, two nodes $s, t \in V$ and a subset of nodes $U \subseteq V$.

Provide an algorithm that determines if there is a shortest path from $s$ to $t$ that passes via **all** nodes in $U$.

I came across a solution that starts with the following steps

* Run BFS on G, notate $d\_s(v) \quad \forall v \in V$
* Calculate $G^T$ (transposed graph)
* Run BFS on $G^T$, notate $d\_t(v) \quad \forall v \in V$
* Build $G^{'} = (V, E^{'})$ where $E^{'} = \\{(u,v)\in E | d\_s(u) + 1 + d\_t(v) = d\_s(t)\\}$

I don't quite understand the intuition for this specific build. It resembles the building of G scc with DFS which doesn't contribute much to my understanding.

Why would I want to build the graph this way and not use the shortest-path-tree I got from the first BFS execution?

EDIT: continued algorithm steps are:

* Run topological sort on $G^{'}$, notate the result with $a\_1, a\_2,...,a\_k$.
* Initialize field $c(v)=0 \quad \forall v \in V$
* Initialize starting node $v \leftarrow t$
* For all v in the reverse topological order do: (until arriving at s)
{
$\forall (x, v) \in E^{'}$
{
if $v \in U, c(x) \leftarrow max\\{c(x), c(v)+1\\}$
else $c(x) \leftarrow max \\{c(x), c(v)\\}$
}
}
* Return $c(s) == |U|$

# Answer
> 3 votes
$d\_{t}(s)$ denote the shortest path length from $s$ to $v$ in $G$.

$d\_{t}(v)$ denote the shortest path length from $v$ to $t$ in $G$.

Using this, the algorithm is constructing $G'$ which consists of exactly those edges of $G$ that appear in some shortest path from $s$ to $t$.

The construction of $G'$ uses the following property of shortest paths.

> **Property 1**: A path $p = (u\_{1},u\_2,\dotsc,u\_{\ell})$ is shortest path from $u\_{1}$ to $u\_{\ell}$ if and only if $(u\_{1},u\_{2},\dotsc, u\_{i})$ is a shortest path from $u\_{1}$ to $u\_{i}$ and $(u\_{i},\dotsc,u\_{\ell})$ is a shortest path from $u\_{i}$ to $u\_{\ell}$ for every $i \in \\{1,\dotsc,\ell\\}$.

Using *Property 1*, you can further prove the following properties of graph $G'$:

1. If $p$ is a shortest path from $s$ to $t$ in $G$, then it will also appear in $G'$.
2. For any vertex $v \in G'$, any path from $s$ to $v$ in $G'$ is a shortest path in $G$.
3. $G'$ is acyclic

Therefore, the algorithm simply checks in $G'$ if there is any path from $s$ to $t$ that contains all vertices in $U$. If it does contains such a path (i.e., $c(v) = |U|$), then that path is a shortest path by the definition of $G'$. And, if there is no such path, then there is no such path in $G$ as well.

# Answer
> 2 votes
The purpose of the BFS in the transposed graph is to eliminate edges that are part of shortest paths to *some* vertex, but not to $t$. These "useless" edges could otherwise lead to false positives in the traceback phase that builds $c(\cdot)$.

Consider the digraph with $E=\\{st,su\\}$ and $U=\\{u\\}$. The unique shortest path is the single edge $st$, so the answer is NO, but unless you know that the $su$ edge should be ignored (by making use of the transposed graph), the traceback phase will process it (on either its first or second iteration) and assign $c(s)=1$, resulting in YES being reported.

(Alternatively, you could augment the traceback phase by "marking" $t$ and any edge into a marked vertex, and considering only values of $c(\cdot)$ for marked vertices. This is fairly similar to just performing a backwards BFS from $t$, and probably a little more efficient in practice.)

---
Tags: algorithms, graphs
---


# Question
Title: Triangles covering all vertices of a tri-partite graph
This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers.

I'm designing fictional fruits. Each fruit has three attributes; color, taste and smell. Also, each of the values of the attributes have some compatibility with the values of the other attributes. So, we get a tri-partite graph. An example is shown below. Here, 1 and 2 are color attributes, 3,4 and 5 are taste attributes and 6 and 7 are smell attributes. Also, color-1 is compatible with taste-3 and smell-6 and so on.

I want to design a minimal number of fruits while still covering all attributes (all 2 colors, all 3 tastes and all 2 smells in this case). For example, the example graph above has the following solution (shown with pink lines, fruit-1 has color-1, taste-3 and smell-6; fruit-2 has color-1, taste-4 and smell-7 while fruit-3 has color-2, taste-5 and smell-6; hence covering all levels of all attributes with 3 fruits):

We know this is optimal since there are three tastes and we couldn't have used less than 3 fruits in this case.

The question is: how to design an algorithm to get the minimum number of fruits required and their configurations given a general graph like the one specified above.

Note that it might not have been possible to cover all attributes even if the graph has no isolated vertices and I asked a question on feasibility here: https://math.stackexchange.com/questions/3998648/possible-to-cover-all-vertices-of-a-tri-partite-graph-with-triangles

# Answer
First, let's invent a decision version of your problem, in which a number $t$ is given in addition to the graph, and the goal is to decide whether the vertices in the input graph can be covered with at most $t$ triangles.

*If* the NP-hard problem 3-dimensional matching (3DM) remains NP-hard under the restriction that $|V|$ is divisible by 3 and the target parameter $k=|V|/3$ (which I consider very likely but don't know for sure), then your problem is also NP-hard by reduction from it:

Given such an instance of 3DM, construct an instance of your problem on the same set of vertices by creating a triangle $abc$ for each 3-tuple $abc$ in the 3DM instance, and setting $t=|V|/3$. Clearly a solution to the 3DM instance corresponds to a solution to the constructed instance of your problem. Such a solution is optimal since all 3-tuples are disjoint. In the reverse direction, if all vertices can be covered using just $|V|/3$ triangles then the triangles must all be disjoint, meaning this corresponds to a valid solution to the original 3DM instance. Together, this means that the answer (YES or NO) is the same to both problem instances. Since the construction is polynomial time, and if the restricted variant of 3DM is NP-hard, so is your problem.

To extend this to a full proof of NP-hardness, one approach would be to try to prove NP-hardness of the restricted variant of 3DM -- e.g., by reducing the general variant to it.
> 2 votes

---
Tags: graphs, colorings, set-cover
---


# Question
Title: Recursively enumerable notation $RE$ vs. $RE\setminus R$
I know that it's a bit stupid question.. , but still, Is there any difference between $RE$ and $RE\setminus R$ notations?

I'm asking because I saw that in some places using both of the notations, for example for $$ L\_{HP}=\\{(\langle M\rangle,x)|M\ halts\ on\ x\\}$$

# Answer
> 2 votes
$RE$ stands for recursively enumerable (recognizable) and $R$ for recursive (decidable). $RE\ \backslash\ R$ simply stands for all the sets that are are recursively enumerable, but not recursive (recall that every recursive set and its complement are recursively enumerable, but not every recursively enumerable set is recursive e.g. Halting Problem).

$R \subset RE$ and $L\_{HP} \notin R$, therefore $L\_{HP}$ can be in both $RE$ and $RE\ \backslash\ R$.

# Answer
> -1 votes
If I understood it right:

$$L\_{HP}\in RE\setminus R$$

and because $$RE\setminus R\subset RE$$ So necessarily: $$L\_{HP}\in RE$$

---
Tags: complexity-theory, formal-languages, computability
---


# Question
Title: How does node expansion work in a graph for AI search?
I want to try and write an example that solves the problem of travelling from one location to another described in the book AI: A modern approach. The problem involves getting from a particular city in Romania called Arad to Bucharest and the problem can be expressed as a graph like in the following image:

If when constructing the graph a `Node` holds a reference to its parent, the action that was applied to get there and the current state at that node plus the path cost, how would node expansion work?

I am not sure how I can expand Arad to give the three nodes attached because Arad does not hold a reference to its children, instead the children hold a reference to Arad.

\** Edit I am now thinking (whilst I am still unsure how a node **is** expanded) that child nodes are not built until a node is expanded. Is this correct?

I could maintain a mapping between a node and its children as a hashtable or something like this but I don't think this would scale to a larger problem where there the journey were much larger.

Equally I could search all nodes at expansion time and then find which have Arad as their parent if I kept some sort of information about each node such as its number in the graph\tree, or the easiest would be for each node to hold a reference to all its child nodes but this does not match the description of a node and its properties specified in the book.

Can somebody explain how node expansion should work in a graph as I am guessing at how I might do it which might not be right.

# Answer
> 1 votes
It seems to me that you are confusing the graph itself with the search tree produced by some search procedure.

As you state, you can't go from one node to the next unless that node knows its neighbors (and not only its own parent). But the search tree is (perhaps implicitly) generated from a search procedure you perform on the actual graph. Perhaps this is what the authors mean with the description you quote.

The actual graph on which you do a search in you can represent via an adjacency list. There, given a node, you can locate its neighbors and the search progresses using that information.

---
Tags: graphs, search-algorithms, artificial-intelligence, graph-traversal
---


title: Randomly built binary search trees

text:
# Question
Title: Randomly built binary search trees
In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove:

> The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$.

We define "randomly built binary search tree on $n$ keys" as:

> a binary search tree that arises from inserting the keys in random order into an initially empty tree, where each of the $n!$ permutations of the input keys is equally likely.

In the proof, we defined some random variables:

Let $X\_n$ denotes the height of a randomly built binary search tree on $n$ keys and the exponential height $Y\_n = 2^{X\_n}$. Of the $n$ keys, we choose one key as the root of the tree, and we let $R\_n$ denotes the random variable that holds the position that this key would occupy if the set of keys were sorted (also know as 'rank' in the text). If we know that $R\_n=i$, it follows that $Y\_n=2\cdot max(Y\_{i-1},Y\_{n-1})$.

We also define indicator random variables $Z\_{n,1}, Z\_{n,2}, ..., Z\_{n,n}$, $Z\_{n,i} = I\\{R\_n=i\\}$.

> \begin{equation} \begin{split} E\[Y\_n\] & = E\Big\[\sum\_{i=1}^{n} Z\_{n,i} (2\cdot max(Y\_{i-1}, Y\_{n-i}))\Big\] \\ & = \sum\_{i=1}^{n} E\[Z\_{n,i} (2\cdot max(Y\_{i-1}, Y\_{n-i}))\] && \text{(by linearity of expectation)}\\ & = \sum\_{i=1}^{n} E\[Z\_{n,i}\] E\[(2\cdot max(Y\_{i-1}, Y\_{n-i}))\] && \text{(by independence)}\\ \end{split} \end{equation}

I would like to ask why is the last equality correct? In other words, why can we assume independence of $Z\_{n,i}$ and $max(Y\_{i-1},Y\_{n-i})$?

In the proof, there was a brief explanation:

> Having chosen $R\_n = i$, the left subtree (whose ranks are less than $i$. This subtree is just like any other randomly built binary search tree on $i-1$ keys. Other than the number of keys it contains, this subtree's structure is not affected at all by the choice of $R\_n=i$, and hence the random variables $Y\_{i-1}$ and $Z\_{n,i}$ are independent. Likewise, the right subtree, whose exponential height is $Y\_{n-i}$, is randomly built on the $n-i$ keys whose ranks are greater than $i$.

However, since $R\_n$ does affect the number of keys $Y\_{i-1}$ and $Y\_{n-i}$ contain (as acknowledged by the explanation above), wouldn't it mean that $Y\_{i-1}$ and $Y\_{n-i}$ are dependent on $Z\_{n,i}$?

*A note regarding similar questions posted on CS stackexchange*

I have read the answers for the following questions which are very similar to mine:

1. Proof that a randomly built binary search tree has logarithmic height
2. Average height of a BST with n Nodes.
3. Randomized BST height analysis : How $Z\_{n,i}$ and $Y\_{k-1}$ are independent?

For 1 & 2, the question was a more general one which asked for an explanation for the entire proof. Also, the answer for both questions did not attempt to justify the independence and simply used the result.

For 3, the question was based on a MIT lecture, https://www.youtube.com/watch?v=vgELyZ9LXX4 and it lacked some of the details which I have included above. Also, the answer was also not clear.

# Answer
> 1 votes
The idea is that the following two experiments produce the same random variable:

1. A random permutation $\pi$ of $\[n\]$ subject to $\pi\_i = n$.
2. Choose a random subset $S$ of $\[n-1\]$ of size $i$, a random permutation $\alpha$ of $S$, a random permutation $\beta$ of $\[n-1\] \setminus S$, and let $\pi = \alpha, n, \beta$.

The height of a BST based on the $\alpha$ part doesn't depend on $S$, which is why it is captured by $Y\_{i-1}$. It does depend on $|S|$, but that's fine, since we conditioned on the value of $i$. Similarly, the height of a BST based on the $\beta$ part doesn't depend on the identity of the particular elements in $\[n-1\] \setminus S$, only on $|\[n-1\] \setminus S| = n-i$, which is why it is captured by $Y\_{n-i}$.

You are worried that $R\_n$ affects the number of keys that $Y\_i$ and $Y\_{n-i}$ contain, but that's false – $Y\_i$ is the random height of a BST on $i$ elements, and this has absolutely nothing to do with $R\_n$. Instead, you should really think of these as $Y\_\<$ and $Y\_\>$, where $Y\_\<$ is the height of the BST formed by elements to the left of $R\_n$, and $Y\_\>$ is the height of the BST formed by elements to the right of $R\_n$. The random variables $R\_n,Y\_\<,Y\_\>$ are certainly dependent. But once we condition on the value of $R\_n$, we are breaking this dependence – $Y\_\<$ has the same distribution as $Y\_i$, and $Y\_\>$ has the same distribution as $Y\_{n-i}$. At the same time, $R\_n$ is no longer random, since we conditioned on its value.

As another example, let us consider the following random process: $A$ is a random bit, and $B$ is equal to $A$ with probability $2/3$, and otherwise it is opposite from $A$. Clearly $A$ and $B$ are dependent. If we know that $A = 0$, then $B$ is just a Bernoulli random variable, equal to $1$ with probability $1/3$.

# Answer
> 3 votes
Just to add on to the answer provided by @Yuval Filmus to further illustrate why the pair $Y\_{i-1},Y\_{n-i}$ should be independent on $Z\_{n,i}$.

Here is what I got wrong:

From $Y\_n = \sum\_{i=1}^{n} Z\_{n,i} (2\cdot max(Y\_{i-1}, Y\_{n-i}))$, I had mistakenly thought that $i$ is a random variable. When I put this back into the definitions: $Z\_{n,i}$ denotes the indicator random variable for the event that the rank of the root node is $i$. $Y\_{i-1}, Y\_{i-1}$ denotes the exponential height of a randomly built binary search tree with $i$ elements and $i-1$ elements respectively. In this case, since $Z\_{n,i}, Y\_{i-1}, Y\_{i-1}$ all dependent on this random variable $i$, I assumed that they must be dependent (through $i$).

Here is how I should have seen the equation above. By expanding out the summation: $$Y\_n = Z\_{n,1} (2\cdot max(Y\_{1-1}, Y\_{n-1})) + Z\_{n,2} (2\cdot max(Y\_{2-1}, Y\_{n-2})) + ... + Z\_{n,n} (2\cdot max(Y\_{n-1}, Y\_{n-n}))$$

Thus, $i$ is just a variable and should not affect the independence between the pair $Y\_{i-1},Y\_{n-i}$ and $Z\_{n,i}$. For instance in the first term $Z\_{n,1} (2\cdot max(Y\_{1-1}, Y\_{n-1}))$, $Z\_{n,1}$ denotes the indicator random variable for the event that the rank of the root node is 1. On the other hand, $Y\_{1-1}, Y\_{n-1}$ denotes the exponential height of a randomly built binary search tree with $0$ elements and $n-1$ elements respectively. Thus, from the definition alone, it should be clear that the pair $Y\_{i-1},Y\_{n-i}$ should not depend on $Z\_{n,i}$.

# Answer
> 0 votes
I was stuck thinking about this proof for a long time and why $Z\_{n,i}$ and $Y\_{i-1}$ should be independent. "Clearly" they depend on each other as they share the variable $i$. What made it click for me is that $Y\_{i-1}$ is not a single random variable whose values depend on $i$, rather it is any of the $Y\_0,Y\_1,\cdots, Y\_{n-1}$.

Think of a concrete example. Suppose $n=10$ and $i=4$. $Y\_3$ is the exponential height of a randomly built binary search tree having $3$ nodes. It takes the values $2^1,2^2$. Knowing the value of $Z\_{10,4}$ tells you nothing about the value that $Y\_3$ takes. Whether $Z\_{10,4}=1$ or $0$ ie. $R\_{10}=4$ or $R\_{10}\not=4$, $Y\_3$ still takes the values $2^1,2^2$ with the same probability distribution.

---
Tags: algorithm-analysis, data-structures, proof-techniques, binary-trees, probability-theory
---


# Question
Title: Linked allocation in operating systems: why not use a doubly linked list?
I'm reading here that linked allocation uses a linked list, where each block has a pointer to the *next block*. For sequential access, this would take moving through the blocks one by one. Would it not better to use a doubly linked list so that this time could be cut in half?

### Algorithmic analysis

I understand that sequential access remains ( O(n) ) worst case time for both singly linked list and doubly linked list. But non-asymptotically the time spent does become half.

# Answer
Singly and doubly linked lists have the identical (terrible) linear access time. Using doubly linked lists would not help performance. The only benefit you'd get is that reading file backwards is more efficient.

No modern file system uses linked allocation anymore. Most use ranges of consecutive blocks, so called extents. Extents are usually more space-efficient and support random access. Neither Singly or doubly linked lists support random access. In practice these days the metadata for a file is read in at once (with all its extents), this is fast. Reading all nodes of the linked lists would mean reading several blocks, one after the other. This is slow, obviously.
> 3 votes

# Answer
The solution that is usually used is not to use a linked list. Most common is that the OS tries to allocate as many sequential blocks as possible, and record ranges of consecutive blocks. Often only one range is used.
> 1 votes

---
Tags: filesystems
---


title: Solving largely monotone SAT formulas

text:
# Question
Title: Solving largely monotone SAT formulas
I just wonder if solving largely monotone SAT formulas (meaning most clauses do not contain negated literals, but some do) is in any way easier than general SAT formulas? In other words, are there heuristics specially designed for solving such formulas that are not applicable to more general SAT problems? I tried but didn't find any research in this particular direction.

Of course, what is considered "most" is up to interpretation, but let's say \>95% of the causes are monotone.

# Answer
The theory probably depends on the details. In practice, if you're only interested in solving an instance, here are a some thoughts:

* Most literals should be eliminated in presolve of today's solvers. They eliminate all positive-only (or negative-only) literals.
* Next, your setup implies that most literals should be set to $true$. Many solvers allow you to specify which assignment should be tried first ("initial phase"). By setting this to $true$, you should get fast solves.
* The potentially exponential blowup from resolution might be avoided, if there are very few negated literals. Thus, BVE and DP-based solvers could be quite effective on such formulas.
* Local search solvers (WalkSAT & Co) should also do very well.

Have you tried feeding your problem to Kissat or CaDiCaL?
> 4 votes

---
Tags: satisfiability, sat-solvers
---


# Question
Title: Find dominated or subsumed linear inequalities efficiently
# Problem statement

Given a set of $N$ linear inequalities of the form $a\_1x\_1 + a\_2x\_2 + ... + a\_Mx\_M \geq RHS$, where $a\_i$ and $RHS$ are integers. The inequality $A$ *dominates* or *subsumes* inequality $B$ if all its coefficients are less or equal and $RHS\_A \geq RHS\_B$. Most inequalities are sparse, i.e. most coefficients are zero. Usually, both $N \> 1000$ and $M \> 1000 $. I'm trying to identify *dominating* or *subsuming* inequalities efficiently.

**What are quick ways to find a) if an inequality is dominated by any other inequality, and b) which inequalities are dominated by a given inequality?**

(Monte-Carlo algorithms are fine, that only report correct results most of the time)

# Proposed solutions in the literature

Eén, N. and Biere, A., 2005, June. Effective preprocessing in SAT through variable and clause elimination. In International conference on theory and applications of satisfiability testing (pp. 61-75). Springer, Berlin, Heidelberg. (chapter 4.2) discuss a variant of this problem in the context where all coefficients are binary, i.e. $a\_i \in {0, 1}$. They propose occurrence lists, one per variable $x\_i$, containing all inequalities with non-zero coefficients $a\_i$. Additionally they use a hashing scheme, similar to Bloom filters, to quickly eliminate candidates. I don't see how to translate this to non-binary coefficients.

Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E. and Weninger, D., 2020. Presolve reductions in mixed integer programming. INFORMS Journal on Computing, 32(2), pp.473-506. (chapter 5.2) discuss a variant of the problem, but don't solve it. They first hash inequalities by indices of non-zero coefficients and the coefficient values. Additionally, they limit their search to a small subset of inequalities.

Schulz, S., 2013. Simple and efficient clause subsumption with feature vector indexing. In Automated Reasoning and Mathematics (pp. 45-67). Springer, Berlin, Heidelberg. describes Feature Vectors for clauses and a kd-tree-like data structure to query combinations of feature vectors.

# Things I've tried

* The trivial solution is to check all pairs of inequalities in $O(n^2)$. Unfortunately, that's too slow for my application where I have millions of inequalities.
* I tried performing a random projection of the coefficients for every inequality, resulting in a projection $p\_j$ for every inequality. An inequality $j$ can only dominate inequality $k$ if $p\_j \leq p\_k$. Thus we don't have to check all pairs. I repeat this process 10 times with multiple random projections, and use the random projection where I have to check the fewest pairs. In practice this is not effective, as most coefficients are zero - and it's unlikely that a random projection focusses exactly on the few non-zero elements. It doesn't help nearly enough.
* Similarly I implemented Feature Vectors, but couldn't replicate the performance reported by Schulz.
* AFAIK, multi-dimensional data structures break down in high-dimensional scenarios (curse of dimensionality). I'm not aware of indexing techniques that work for high-dimensional range queries.
* I thought about Bloom filters, unsuccessfully.
* I thought about randomized algorithms, unsuccessfully.

Do you have any other ideas?

# Answer
> 2 votes
Unfortunately there is a nearly-quadratic-time lower bound that may prove a barrier. In particular, you can't solve it in $O(N^{2-\varepsilon})$ time for any $\varepsilon\>0$ unless the Strong Exponential Time Hypothesis is false. In particular, the special case where all coefficients are 0 or 1 and the RHS is the same for all inequalities is equivalent to searching a bunch of sets for a pair that have a subset relationship, and that is hard: see https://cstheory.stackexchange.com/q/9896/5038.

The one saving grace is that this lower bound is for arbitrary sets, i.e., it does not take into account sparsity. It is possible that you might be able to use sparsity somehow to do better than the general case.

Here is an algorithm that takes advantage of sparsity to do a bit better. Suppose that every inequality has only $K$ nonzero coefficients. Form a balanced binary tree on the $N$ inequalities. Annotate each node with a map that maps $x\_i$ to the max of all coefficients of $x\_i$ in all inequalities under that node. Now given an inequality $A$, you can check whether it dominates any other inequality by traversing the tree in a top-down breadthfirst fashion. Any time you hit a node that maps $x\_i$ to something smaller than $x\_i$'s coefficient in $A$, there is no need to visit any of the children of that node, and traversal of that subtree can be skipped. Heuristically, I expect you'll probably need to visit $O(KN/M)$ nodes of the tree on average (well, plus $O(\lg N)$ to account for the fact that each inequality dominates itself, but I'll ignore that as it seems likely to be small in comparison to the other terms). Creating the tree takes $O(NK)$ time, and visiting each node takes $O(K)$ time, so I expect the overall running time per inequality will be something like $O(KN + K^2N/M)$, on average. Since you have $N$ inequalities, the total time should be something like $O(KN + K^2N^2/M)$. I don't know whether this is any better than what you already have in mind, though.

---
Tags: search-algorithms, probabilistic-algorithms, bloom-filters
---


# Question
Title: Can't wrap my head around on building a suffix table for Boyer Moore
My resources were the following video, as well as this video.

Basically, in one of the videos they state that the good suffix table for the pattern **"ABCBAB"** is the following:

| k | suffix | d2 |
| --- | --- | --- |
| 1 | B | 2 |
| 2 | AB | 4 |
| 3 | BAB | 4 |
| 4 | CBAB | 4 |
| 5 | BCBAB | 4 |

and for **"DRIDI"**:

| k | suffix | d2 |
| --- | --- | --- |
| 1 | I | 2 |
| 2 | DI | 5 |
| 3 | IDI | 5 |
| 4 | RIDI | 5 |

If all of the above is correct, I can't understand why in the first table, for k = 5, we have d2 = 4 (because we match the A with the suffix **"BCBAB"**?), where as in the second table for k = 4, we cannot do the same (match D with the D inside the suffix **"RIDI"**), hence why the value for d2 is the length of the pattern, i.e 5 and not 3.

What's going on here?

# Answer
The shift rules of Boyer–Moore algorithm come from the bad character rule and the good suffix rule.

While the bad character rule exploits a single character that is in the text but not in the pattern, the good suffix rule exploits **multiple** contiguous characters that appear in both the text and the pattern.

"In the first table, for k = 5, we have d2 = 4." This is because "AB" is both a prefix of "**AB**CBAB" and a suffix of "BCB**AB**". So if some text contains "**BCBAB**", it is possible that text extends to right to contain "**BCBAB**CBAB", thus containing the pattern "ABCBAB". It is not simply because 'we match the A with the suffix "BCBAB"'. That B after A should be matched as well.

In the second table for k = 4, although we can match the D at the beginning with the D inside "RIDI", a shift of 3 cannot possibly match the whole pattern, since it will lead to the mismatch between the I after D and the R after D. So there is no need to consider a shift of 3.

```
          T:    ***RIDI̲***
  current P:      DRIDI̲
P shifted 3:         DR̲IDI

```
> 1 votes

---
Tags: algorithms, strings, matching, string-matching, exact-string-matching
---


# Question
Title: Shared randomness does not increase capacity of a noisy channel - Why?
Why is it the case that when Alice and Bob use a noisy channel for communication, the capacity of the channel does not increase even if they are allowed to share pre-distributed randomness?

This is mentioned in some notes (see paragraph before Section 4 of https://cds.cern.ch/record/613098/files/0304102.pdf) but I have not seen a proof or an intuitive argument for it yet. Any reference to where this is covered would also be appreciated!

# Answer
> 2 votes
Each value of the shared randomness corresponds to a communication protocol. So overall, we have a mixture of communication protocols, whose expected quality is good. There must therefore be one of these communication protocols – a setting of the shared randomness – which is as good.

As an example, we know that a random code achieves capacity. This means that some *particular* code achieves capacity. It might be hard to find that code, but we know that it exists.

---
Tags: information-theory, randomness
---


# Question
Title: Is there a formal language of Combinatory Logic's expressions?
The Combinatory Logic uses expressions of the form (x y) called "applications" (here, we have an "application of x to y"). Thus, the language of CL is a set of "parenthetic expressions", each looking like a string of variables to which pairs of balanced parentheses are multiply applied in an exhaustive manner (that is, you cannot insert yet another pair of parentheses).

Is there a grammar which defines this language? (I am a novice in formal languages and I am not sure my question is correctly formulated)

# Answer
The set of valid expressions in combinatory logic forms a computable formal language, and so can be described by a grammar. It is likely that this language is context-free, and so can be described by a context-free grammar.

More generally, we know the power of grammars exactly: a formal language can be described by a grammar if and only if it is recursively enumerable. So if there is an algorithm which enumerates all valid expressions in combinatory logic, then the language of all valid expressions in combinatory logic can be described by a grammar.

Even more generally, by definition, a formal language over an alphabet $\Sigma$ is just a collection of words over $\Sigma$. This means that any encoding of combinatory logic expressions which uses some fixed alphabet is automatically a formal language.
> 1 votes

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


# Question
Title: Confusion in understanding a DFA question
I am new to DFA and I am trying to understand the following question.

The alphabet is Σ = {0, 1} Construct DFA for L = {0^n: n is either a multiple of 3 or a multiple of 5 }

**Question** The above language does not say anything about the 1s.

When we write strings in this Language, we get L = {є, 000, 00000, 000000, 000000000, ...} There are no ones in this language.

According to the language description, 0010 would not be a valid string. Right?

So, in the DFA that we construct do we need to show 1s? Can I just leave them out?

# Answer
> 0 votes
Either you can make a 1 transition from every state to a non-final sink state. Or make a note that any character that doesn't match an available transition goes to a non-final sink state.

Depends on what format is usual for the course.

I assume the reason that 1 is also in the alphabet is to trip up people who forget about this sink state.

---
Tags: finite-automata
---


# Question
Title: Every AVL tree can be colored to be a red-black tree
I want to prove any AVL tree can be turnt into a red-black tree by coloring nodes appropriately. Let $h$ be the height of a subtree of an AVL tree. It is given that such a coloring is constrained by these cases:

1. $h$ even $\implies$ black height $=$ $\frac{h}{2} + 1$, root node black
2. $h$ odd $\implies$ black height $=$ $\frac{h+1}{2}$, root node red

After that the root node is colored black.

---

I'm trying to prove this inductively. Let's start with the **base case** $h=1$. Then there is only one node (the root node) and it gets colored black (using case 2) which yields a valid red-black tree.

Now suppose the statement is true for some $h \geq 1$. Then for any node $u$ in the AVL tree, the height difference between their children is less than $1$. That is, for an AVL tree of height $h+1$ either both subtrees of the root node have height $h$ or one has height $h-1$.

By the induction hypothesis we know how to color the subtree of height $h$, depending on the parity of $h$. I'm unsure if I should use strong induction instead because it is *not* given in the hypothesis how to color a subtree of height $h-1$.

If we *would* know how to color both subtrees, then consider the following cases:

1. $h+1$ is even
    * one subtree has height $h$, the other height $h-1$
    * both subtrees have height $h$
2. $h+1$ is odd
    * one subtree has height $h$, the other height $h-1$
    * both subtrees have height $h$

For case 1.1 we would get $$ \begin{align\*} \quad & h+1 &\text{even} \\ \implies \quad & h &\text{odd} \\ \implies \quad & \text{black height} = \frac{h+1}{2} \\ \implies \quad & h-1 &\text{even} \\ \implies \quad & \text{black height} = \frac{(h-1)}{2} + 1 = \frac{h+1}{2} \end{align\*} $$

So their black heights differ by $1$. How would I take that into consideration?

# Answer
Here is a computer verification of your method.

The height discrepancies occur when we are making a red root, in which case the shorter child with the reduced black height would also have a red root. Since there can't be two consecutive red nodes, we need to turn the shorter child black, which increases its black height to match the taller child.
> 1 votes

---
Tags: induction, avl-trees, red-black-trees
---


# Question
Title: Simplify the definition of substitution in Lamdba calculus
Substitution in untyped Lambda calculus is complicated by variable capture.

Can this boring technical complication be entirely avoided by some restriction on the standard formation rules? Something that prevents the dangerous symbol duplication. If so, how? Otherwise why not?

Alternatively, can the complication be avoided by uniformly alpha-converting every Lambda abstraction of the final composite, to ensure that every binding/bound variable symbol only appears locally (and therefore never as a free variable in the argument of an application term). If so, it seems that the substitution rules could be simplified.

# Answer
> 3 votes
Yes, there are several techniques, such as de Bruijn indices and explicit substitutions. Actual implementations, at least those that actually have to work efficiently, use such techniques and never implement substitution by renaming variables.

---
Tags: lambda-calculus
---


# Question
Title: Computing FOLLOW sets of left recursive grammar
Left recursive ambiguous expression Grammar:

> $E \rightarrow E+E \mid E\*E \mid (E) \mid \mathbf i\mathbf d$

I tried computing FIRST and FOLLOW sets of both left recursive grammar and after eliminating left recursion. In both the cases, I was able to compute FIRST sets successfully, but not FOLLOW sets. I have shown the work I did to compute the two sets below.

*Note that to compute FIRST and FOLLOW sets, I followed the rules given in Compilers Principles, Techniques, & Tools Second Edition or The Dragon book*

---

I computed FIRST and FOLLOW sets of left recursive grammar following this post.

Computing FIRST sets:

> $First(E)$ = $First(E+E)$ $\cup$ $First(E\*E)$ $\cup$ $First\bigl((E)\big)$ $\cup$ $First(id)$
>
> Since $\epsilon\not\in\text{First}(E)$, ignore the rules $E$ $\rightarrow$ $E+E\mid E\*E$
>
> Therefore, $First(E) = \\{(, id\\}$

Computing the FOLLOW sets:

> $Follow(E) = First(+E) \cup First(\*E) \cup First\bigl()\bigr) \cup Follow(E) \cup$ {\\$}
>
> See that there is a recursive $Follow(E)$. I am not sure how to resolve this. I know that, a set does not include duplicates, so no matter how many times I union $Follow(E)$ with itself, the result does not change, though I am not sure if my argument even applies in this case. **How do I proceed from here?**

---

Since I was stuck, I tried computing FIRST and FOLLOW sets after eliminating left recursion.

Grammar after eliminating left recursion:

> $E \rightarrow (E)E' \mid \mathbf i\mathbf dE'$
>
> $E' \rightarrow +EE' \mid \*EE' \mid \epsilon$

Computing the FIRST sets:

> $First(E') = First(+EE') \cup First(\*EE') \cup \\{\epsilon\\}$
>
> Therefore, $Fisrt(E') = \\{\epsilon, +, \*\\}$
>
> $First(E) = First\bigl((E)E'\bigr) \cup First(\mathbf i\mathbf dE')$
>
> Therefore, $First(E) = \\{(, id\\}$

Computing FOLLOW sets:

> $Follow(E)$ = {\\$} $\cup First\bigl()E'\bigr) \cup Follow(E')$
>
> $Follow(E') = Follow(E) \cup Follow(E')$
>
> Again I am stuck with the recursion issue. **How do I proceed from here?**

---

**I suppose FIRST and FOLLOW sets do not change with elimination of left recursion, or do they? If yes, should one always calculate the sets after elimination of left recursion?**

# Answer
The cited algorithm for FIRST and FOLLOW is a least fixed-point algorithm; recursive inclusion of the same set is a no-op.

That's clearly stated in the Dragon Book's description of this algorithm, which involves repeatedly evaluating the equations until no additional elements are added to any set during an iteration.

The algorithm works without the necessity to remove left recursion (and recursive equations in the FOLLOW set are possible without left recursion in the grammar). Left recursion elimination is not isomorphic, by the way; it's not a reversible procedure and the original grammar can not be recovered.
> 1 votes

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


# Question
Title: Algorithm chalenge: find minimum range to cover all houses with light
N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R?

N is an array containing location of each house. K is an integer value.

I am unable to identify the algo for this. I tried solving by taking location of 1st and last house, then dividing by K, this will give me max range of each streetlight. However, assume N=\[3,4,5,10,13\] and K=3. With division this wont work.

# Answer
This is a known problem: https://binarysearch.com/problems/Minimum-Light-Radius

Key Idea: Binary search for the diameter, then use that to find the radius.
> 1 votes

---
Tags: algorithms, data-structures, search-algorithms, arrays, matrices
---


# Question
Title: Formal Binary String Regular Expression (each pair of 00 must have 11 before it)
I'm trying to construct a regular expression for the language of binary strings in which every 00 must have at least two 1s before it.

I realize this can be done with lookbehinds using the following regex: `^(?:(?<=11)00(?!0)|(?<=1)0|1+)+$` , however I am now trying to construct a regular expression in the sense of formal language theory.

I currently have `(0|)(11*0)*1*` (or `(0+ε)(11*0)*1*` ), which gives me the language of binary strings without consecutive 0s, but am not quite sure how to get the 'conditional' part in without actually using a conditional.

**Accepted:**
0
1
10
11100
1100

**Rejected:**
100
1000
11000

# Answer
Here is a way to describe a binary string in which every 00 must have at least two 1s before it.

It is a string that
$\quad$ starts with zero or one 0;
$\quad$ followed by zero or more blocks, where each block is
$\quad\quad$ either one or more 1s followed by a 0, such as 10, 110, 1110, etc,
$\quad\quad$ or two or more 1s followed by two 0s, such as 1100, 11100, 111100, etc;
$\quad$ followed by zero or more 1s.

Translated into regular expression, the description above becomes
$\quad$ `(0|ε)(11*0|111*00)*1*`

---

You might want to ask, how can we arrive that kind of description?

The observation here is that the number of consecutive 0s in the string is at most 2, a very small number. That indicates that we can break down the string by enumerate different possibilities of consecutive 0s. To paraphrase rici's comment, we could try using enumeration to simulate conditionals.

---

Of course, there is a mild stroke of luck involved in the approach above on that language. As a last resort, we can always use a heavier machinery such as constructing a DFA for the language (which can be done in one or several ways) and then converting the DFA to a regular expression.
> 1 votes

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


# Question
Title: Time complexity and upper and lower bounds
Consider the following algorithm:
(the `print` operation prints a single asterisk; the operation `x = 2x` doubles the value of the variable `x`).

```
for k = 1 to n:
   x = k
   while (x < n):
      print ’*’
      x = 2x

```

Let f (n) be the time complexity of this algorithm (or equivalently the number of times * is printed). Provide correct bounds for O(f (n)) and Ω(f (n)), ideally converging on Θ(f (n)).

This question is one of practices in *The Algorithm Design Manuel*.

I found the time complexity to be $\sum\limits\_{k=1}^{n}\lceil\lg(\frac n k)\rceil$

My question is, could this (or any function) be its own upper and lower bound?

Also is there a way to simplify this function (like writing the sums using some formula like $\frac{n(n+1)}2$)?

Thanks in advance.

# Answer
> 2 votes
Ever heard of Stirling's approximation? :) Well, it implies that $(\frac{n}{e})^{n} \leq n! \leq e^2 \cdot (\frac{n}{e})^{n+1}$. We will use it get a nice upper and lower bound on your function:

**Upper Bound:** $$\sum\_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil \leq n + \log \frac{n^n}{n!} \leq n + \log (e^n) = O(n)$$

**Lower Bound:**

$$\sum\_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil \geq \log \frac{n^n}{n!} \geq \log \Big(\frac{e^{n-1}}{n} \Big) = \log(e^{n-1}) - \log n= \Omega(n) $$

---

Thus, we get $\sum\_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil = \Theta(n) $

---
Tags: algorithms, time-complexity, asymptotics
---


# Question
Title: How are semaphores and test-and-set instructions connected?
Cheers, so my textbook explains these parts very poorly, so I would gladly take any advice! I am confused between the test-and-set instructions, which per my book *is a very common CPU instruction set*, and the use of semaphores for which my book says that: *a flag implemented using this way, is a semaphore*. Does that mean that semaphores are a part of these instructions or the opposite? Also, if a operating system does not support semaphores, can it support test-and-set instructions and if yes, can you reach mutual exclusion this way? Thanks!

# Answer
Semaphores are an abstract mechanism to control access to a shared resource. Other such mechanisms exist, for example locks and monitors. These are the counterparts of abstract data structures – they specify an API for a mechanism and its semantics, but not its implementation.

Implementing such mechanisms correctly requires hardware support. One way to implement semaphores is using test-and-set. Another popular instruction is compare-and-swap. Both of these are examples of *atomic instructions*, which are instructions performing several operations that cannot be interrupted in the middle. Such atomic instructions are necessary to correctly implement mechanisms such as semaphores.

Typically these control mechanisms are implemented by the operating system. For example, POSIX-compliant systems implement POSIX semaphores. Semaphores are just one more service provided by the operating system. Under the hood, semaphores are implemented using atomic instructions provided by the CPU.
> 2 votes

---
Tags: operating-systems, deadlocks, mutual-exclusion, semaphore
---


# Question
Title: EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?
So as I understand $EQ\_{TM}$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $A\_{TM}$ is reducible to its complement ${NEQ\_{TM}}$). But we can also reduce $A\_{TM}$ to $EQ\_{TM}$ itself, that means: $EQ\_{TM}$ and ${NEQ\_{TM}}$ are not disjoint since we can reduce $A\_{TM}$ to the two of them? And also, $EQ\_{TM}$ is not Turing recognizable but it contains some instance that is turing recognizable since we can reduce $A\_{TM}$ to it?

I have an intuition that these two questions have 'YES' as an answer and they are not problematic: it is OK to answer them with YES. But I have an unclear image about the fact of being a complement but having some shared elements with its complement, maybe the elements that are shared are just the strings but not the problems themselves?

Any clarifications would be welcome

# Answer
Note that $EQ\_{TM}$ is the language of machines that recognize the same language (they are not necessarily equivalent).

You said

> But we can also reduce $A\_{TM}$ to $EQ\_{TM}$ itself, that means: $EQ\_{TM}$ and $NEQ\_{TM}$ are not disjoint since we can reduce $A\_{TM}$ to the two of them?

This is far from being true, if there are reductions from a language $A$ to two languages $B$ and $C$, this does not say anything about $B\cap C$ as the reductions need not be related. To be concrete, it is shown here that every non-trivial language is $\text{R}$-hard, so clearly, you cannot claim that every two non-trivial languages intersect.

You also said

> And also, $EQ\_{TM}$ is not Turing recognizable but it contains some instance that is turing recognizable since we can reduce $A\_{TM}$ to it?

Clearly, $EQ\_{TM}$ contains some instances $\langle M\_1, M\_2 \rangle$, where it is easy to check whether $L(M\_1) = L(M\_2)$ (for example, all instances where $M\_2$ is identical to $M\_1$ with some new unreachable states). Also, you're right, this indeed can be thought of a consequence of the existence of a reduction from $A\_{TM}$ to $EQ\_{TM}$. Formally, we have the following claim (I leave it to you as a good non-trivial exercise), and thus the image of the reduction (which is a subset of $EQ\_{TM}$) is in $\text{RE}$.

**Claim:** Let $f: \Sigma^\* \to \Sigma^\*$ be a computable function and let $L\subseteq \Sigma^\*$ be a language in $\text{RE}$. It holds that $f(L) = \\{ f(x): x\in L \\}\in \text{RE}$.

BTW, complement languages, by definition, have empty intersection. So, regarding the question in the title, you can reduce $A\_{TM}$ to $EQ\_{TM}$ (here is a hint: there they asked about a reduction from the halting problem, but the hint is also good for your case), and being able to define such a reduction does not contradict anything.
> 1 votes

---
Tags: turing-machines, computation-models, turing-completeness
---


# Question
Title: (Finite Automata) Why the following is a NFA?
The first one seems like a DFA. Could someone explain why this is a NFA?

# Answer
> 2 votes
Here is a similar question:

> Which of the following are rational numbers: $$ 1, \frac{2}{3}, \sqrt{2}. $$

The correct answer is that both $1$ and $\frac{2}{3}$ are rationals, despite the fact that $1$ is also an integer.

One thing which is confusing here is that none of the given examples are DFAs or NFAs. Rather, they are pictorial representations of automata. Most of these pictorial representations can be interpreted as NFAs, and some can also be interpreted as DFAs. There would be no ambiguity if the automata were given as *tuples*, since the transition function of a DFA has signature $Q \times \Sigma \to Q$, whereas the transition function of an NFA has signature $Q \times \Sigma \to 2^Q$.

# Answer
> 1 votes
There are two explanations that work:

1. By definition every DFA is also a NFA (perhaps the question meant to ask which are NFAs but not DFAs and which are DFAs).
2. In a DFA, each state must have transitions (outgoing edges) defined for each element of the alphabet (commonly referred to as $\Sigma$).

If you look at the first one, states S1 and S2 don't have a transition for 1, and for state S3, there is no transition for 0. One of the comments mentions that it is common to ignore some transitions in a DFA and have them go to a dead state, but by definition, a DFA must be fully specified. Omitting transitions is just a convenience for some people, but isn't universal.

# Answer
> 0 votes
The first automaton is not a DFA because it has missing transitions. Indeed, the states $s\_1, s\_2$ have no outgoing transitions labeled with 1, also, the state $s\_3$ has not outgoing transition labeled with 0. As you've noted, intuitively, this automaton does not really look nondeterministic because you don't have a *guess* (the automaton has at most one run on a given input word) and you can easily direct all missing transitions to a rejecting sink to get a complete deterministic transition function ($\delta$ is defined for every state and letter). I agree, and some people consider such automata to be deterministic (this has been explained thoroughly here), but probably, the way you defined it in class does not allow missing transitions.

---
Tags: finite-automata, regular-expressions, compilers
---


# Question
Title: Haskell type classes as ontological categories
A paper uses Haskell type classes to represent ontological categories. A type class hierarchy is used to represent "concept hierarchies" where "functions are the units of inheritance". Here is a diagram of the Haskell type classes based on the paper:

With respect to the code below the following claim is made:

> The Haskell code given so far is complete and type checked, explaining the entire refined concept hierarchies. With instantiations for types of boathouses and houseboats, values can be declared and axioms stated and evaluated to demonstrate semantic properties and differences. For example, it can be shown that a passenger **on** a boat **in** a boathouse cannot be said to be an inhabitant, while a passenger **on** a houseboat can.

The spatial prepositions **in** and **on** form part of the semantics the `whatsIn` and `whatsOn` predicates in the code below.

I have a three questions:

(**Q1**) Is the claim true?

(**Q2**) How would go about validating such a claim.

As regards Q2, I have create 72 instances with appropriately kinded data types as advised by the GHCI compiler (not supplied in this post). Then I checked the types with the following type level queries

> Query 1 : A passenger **on** a boat **in** a boathouse cannot be said to be **in** the boathouse (i.e. an inhabitant)

```
:t whatsIn (BoatHouse (Boat People)) =t=> OK whatsIn (BoatHouse (Boat People)) :: [Boat People]
:t whatsOn (HouseBoat  People) =t=> ERROR  No instance for (Surfaces BoatHouse (Boat People))

```

> Query 2 : A person can be both **on** and **in** a houseboat (a passenger and an inhabitant).

```
whatsOn (HouseBoat  People) :: [People]
:t  whatsIn (HouseBoat  People)  =t=> whatsIn (HouseBoat  People) :: [People]
:t  whatsOn (HouseBoat  People) =t=> whatsOn (HouseBoat  People) :: [People]

```

(**Q3**) Both these queries seem to be apptropriately accepted and rejected by Haskell. Is there a better or easier way to validate this claim?

**Listing 1** shows the source code from paper.

```
class Containers a b where
 insert :: b -> a b -> a b
 remove :: b -> a b -> a b
 whatsIn :: a b -> [b]

class Surfaces a b where
 put ::  b -> a b -> a b
 takeOff :: b -> a b -> a b
 whatsOn :: a b -> [b]

class Paths a b c where
 move :: c -> a b c -> a b c
 origin, destination :: a b c -> b
 whereIs :: a b c -> c -> b

class PeopleClass p
class HeavyLoads l
class Surfaces w o => WaterBodies w o
class Containers h o => Houses h o
class (Surfaces v o, Paths a b (v o)) => Vehicles v o a b
class (Vehicles v o a b, WaterBodies w (v o)) => Vessels v o a b w
class (Vessels v p a b w, PeopleClass p) => Boats v p a b w
class (Boats v p a b w, HeavyLoads p) => Barges v p a b w
class (Houses h (v p), Boats v p a b w, Contacts w (h (v p))) => BoatHouses h v p a b w
class (Barges v p a b w, Houses v p, PeopleClass p) => HouseBoats v p a b w

```

# Answer
The code in **Listing 1** represents my attempt to test the claim. I have simplified the classes, while retaining that ability to test the original claim, which is repeated here:

*The Haskell code given so far is complete and type checked, explaining the entire refined concept hierarchies. With instantiations for types of boathouses and houseboats, values can be declared and axioms stated and evaluated to demonstrate semantic properties and differences. For example, it can be shown that a passenger on a boat in a boathouse cannot be said to be an inhabitant, while a passenger on a houseboat can.*

Here is the simplified class hierarchy:

If we interpret an **inhabitant** as being **directly in** the boathouse then the claim is somewhat reasonable. This is because in **Listing 1** `whatsIn` is not defined for type `BoatHouseD`, attempting to evaluate in GHCi:

```
whatsIn (BoatHouseDc (PeopleDc "joe"))

```

will cause error. In general, if a function is not defined for a data type that function will fail to type check. Note `whatsIn` is defined in an instance of `ContainersC` class for the type `BoatD` and also defined in an instance of `ContainersC` class for the type `BoatHouseD`. `whatsOn` is defined for an instance of SurfacesC. These functions cannot be defined in the sub-classes `HousesC`, `BoatHousesC`, and `HouseBoatsC` of `ContainersC` or `BoatsC`, `BoatHousesC`, and `HouseBoatC` of `SurfacesC`.

On the other hand the semantics of the Haskell code can be used to refute the claim. The `test` in **Listing 1** shows that if someone is on a boat and that boat is in a boathouse then they are indirectly in the boathouse.

**Conclusion**

Based on the Haskell code in **Listing 1** we can refute the claim. Reasoning **about** the Haskell code there is some credibility in the claim. The sub-classes seem to be redundant, because functions can only be defined in instances of the class where they were originally declared, not in any sub-class of that original class. So the functions `whatsIn` and `whatsOn` cannot be defined for the sub-classes.

Listing 1

```
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-#  OPTIONS_GHC  -Wno-missing-methods #-}
 -- The suffix D=data type,Dc=constructor
 -- The data types were chosen to match the type variables in the type classes
            data PeopleD = PeopleDc [Char] deriving (Show,Eq)
            data BoatD a  = BoatDc a deriving (Show,Eq)
            data HouseBoatD a  = HouseBoatDc a  deriving (Show,Eq)
            data BoatHouseD a  = BoatHouseDc a deriving (Show,Eq)

            class ContainersC a b where -- suffix C= class
             insert :: b -> a b -> a b
             remove :: b -> a b -> a b
             whatsIn :: (a b) -> [b]

            class SurfacesC a b where
             put ::  b -> a b -> a b
             takeOff :: b -> a b -> a b
             whatsOn :: (a b) -> [b]

            class PeopleC p
            class ContainersC h o => HousesC h o
            class (SurfacesC v o) => BoatsC v o
            class (HousesC h (v p), BoatsC v p) => BoatHousesC h v p
            class (BoatsC v p, HousesC v p, PeopleC p) => HouseBoatsC v p

            instance ContainersC BoatD PeopleD where
               whatsIn (BoatDc (PeopleDc x)) = [PeopleDc x]

            instance ContainersC BoatHouseD (BoatD PeopleD) where
                whatsIn (BoatHouseDc (BoatDc (PeopleDc x))) = [(BoatDc(PeopleDc x))]

            instance SurfacesC BoatD PeopleD where
               whatsOn (BoatDc (PeopleDc x)) = [PeopleDc x]

             test =  (head (whatsOn(head (whatsIn (BoatHouseDc (BoatDc (PeopleDc "joe"))))))) ==
                  (head (whatsOn(BoatDc (PeopleDc "joe"))))

```
> 1 votes

---
Tags: knowledge-representation, haskell
---


title: Complementary for $SAT$

text:
# Question
Title: Complementary for $SAT$
I have tried to find a definition of complementary language to $SAT$, I mean $\overline{SAT}$. But I still confused, in case of $L\in \overline{SAT}$ is it mean:
if $\varphi\in L$ then all interpretations are satisfy and if $\varphi\notin L$ then exists interpretation that unsatisfy
**OR** vice versa
if $\varphi\notin L$ then all interpretations are satisfy and if $\varphi\in L$ then exists interpretation that unsatisfy

please if you downvote write explanation of why

# Answer
Usually, when we talk about the complement of a set we have some reference set to compare to. In the setting of languages over some alphabet $\Sigma$, this means that the complement of some language $L$ would be $\overline L = \Sigma^\ast \setminus L$, i.e. the set of all strings over $\Sigma$ which are not in $L$.

In the particular case of $$\mathrm{Sat} = \\{\langle \psi \rangle \in \Sigma^\ast \mid \langle \psi \rangle \text{ encodes a satisfiable propositional formula } \psi \\}$$ we find that $$\overline{\mathrm{Sat}} = \\{w \in \Sigma^\ast \mid w \text{ does not encode a satisfiable propositional formula } \psi \\}$$ and hence, $\overline{\mathrm{Sat}}$ consists of all strings which represent unsatisfiable propositional formulas (i.e. ones that have no satisfying interpretations) and all strings which don't represent formulas at all.
> 4 votes

---
Tags: complexity-theory, formal-languages, computability, satisfiability
---


# Question
Title: Finding "entrance" points in a set of d-dimensional points. Can I do better than O(N^2)?
I am given a set of d-dimensional points, and need to find the set of **entrance points** in them.

Definitions:

* A point p1 **captures** p2 if 1) All dimensions of p1 is **smaller or equal to** p2; and 2) **At least** one dimension of p1 is **strictly less than** its corresponding dimension of p2. (e.g. `p1 = <1.0, 2.0, 3.0>`, `p2 = <1.0, 3.0, 3.0>`, since `1.0 == 1.0`, **`2.0 < 3.0`**, `3.0 == 3.0`, we say p1 **captures** p2.
* An **entrance point** is a point which it is not **captured** by any other points in the dataset.

For example, in the following dataset:

```
n = 4, d = 2
=============
p1 = <0.3, 1.5>
p2 = <0.2, 1.4>
p3 = <0.1, 1.7>
p4 = <0.8, 0.9>

```

The **entrance points** are `{p2, p3, p4}` because:

1. p1 is captured by p2 because all dimensions of p2 is less than p1.
2. p2, p3, p4 cannot capture each other.

---

Assuming d is a constant. Now I can only think of a naive O(N^2) solution, that is, take every possible pair of the points and compare the dimensions one by one. If a point is captured by the other, eliminate it from the final set.

I also thought of a divide-and-conquer solution. That is, recursively break the points down into two partitions, perform the previous O(N^2) algorithm to eliminate some candidates from the final set, then recursively merge each pair of the partitions, say part1 and part2, back by comparing each possible pair of points one from part1 and one from part2. However, even though the running time is a little faster with the aid of multi-threading, I found that it is still an O(N^2) algorithm because `T(N)=2T(N/2)+O(N^2)` ==\> `O(T(N)) = O(N^2)`.

I wonder if there exists an algorithm with lower time-complexity for this problem.

Also, is there any well-known name for this problem? Or are there any well-known problems similar to this one so I can look into?

# Answer
> 2 votes
Your problem is similar to finding Maxima of a point set in a $d$-dimensional space. In $2$-$D$ and $3$-$D$ there is a simple Divide and Conquer algorithm that has a $O(n \log n)$ running time. For higher dimension, there is $O(n (\log n)^{d-3}\log \log n)$ time algorithm as given in the Wikipedia page.

You can covert your problem to the *Maxima problem*, by simply negating the coordinate values of the input points. In other words, your problem is a *Minima problem*.

---
Tags: algorithms, time-complexity, computational-geometry
---


# Question
Title: Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$
I'm trying to find a grammar for $L = \\{w \text{ | }w \in \\{a,b\\}^\*, |w|\_a=|w|\_b-1\\}$, which is proving to be tricky.

I know that $L\_2 = \\{w \text{ | }w \in \\{a,b\\}^\*, |w|\_a=|w|\_b\\}$ has the following one, so I have been trying to modify it so that I "force" to have one more $b$, but I don't see how to do this. The obvious choice would be to replace $\epsilon$ with $b$, but that would potentially get two more $b$'s. Is there a trick for this one?

$$\begin{align} S &\to \epsilon \\ S &\to aSbS \\ S &\to bSaS \enspace. \end{align}$$

# Answer
> 3 votes
You asked for a trick. Yes, there is a construction to add a single letter to the strings in the language of a grammar given in advance.

For simplicity I will start with a grammar in Chomsky Normalform, i.e., every rule is of the form $A\to BC$ or $A\to \sigma$, with $A,B,C$ variables and $\sigma$ terminal.

Assume there is a context-free grammar $G$ for a language $L$ then we can construct a grammar for "strings in $L$ with an extra $b$" in a generic way. We use the variables to hand down the instruction "add a $b$" to one of their successors. For each variable $A$ we introduce a copy $A\_1$ that carries this task.

Thus, for every rule $A\to BC$ we add the new rules $A\_1\to B\_1C$ and $A\_1\to BC\_1$. Morever, we make it possible to add the extra $b$, with rules $A\_1 \to bA$. Now starting with $S\_1$ derivations are as before, except at some point in the derivation a single $b$ is introduced. Note that we need to generate a $b$ since variables $A\_1$ cannot be rewritten into terminals. One tiny detail: the $b$ can only be introduced *before* a variable, so in order to append a $b$ we need the additional rule $S\_1\to Sb$. (We need no other additional rules since a $b$ after a variable can be replaced by a $b$ before another variable, except at the end.)

# Answer
> 3 votes
You can simply consider the following grammar: $$ S\to S\_1 b S\_1$$ where $S\_1$ is the start variable of a grammar for the language of words $w$ with $|w|\_a = |w|\_b$. Correctness is self-explanatory.

So using the grammar you wrote, you get the following grammar: $$ S\to T b T$$

$$ T \to aTbT| bTaT | \epsilon$$

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