# Question
Title: Counting primitive operations on recursive functions
I'm reading *Algorithm Design and Applications*, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given algorithm. Everything was clear to me until the moment they showed a recursive function (a simple recursive way to calculate the maximum value of an array) and its primitive operation count.

The function (in pseudo-code) is this:

```
Algorithm recursiveMax(A, n):
    Input: An array A storing n ≥ 1 integers.
    Output: The maximum element in A.

    if n = 1 then
        return A[0]
    return max{recursiveMax(A, n − 1), A[n − 1]}

```

where `A` is an array and `n` its length. The author states what follows concerning how we calculate the number of primitive operations this function has:

> As with this example, recursive algorithms are often quite elegant. Analyzing the running time of a recursive algorithm takes a bit of additional work, however. In particular, to analyze such a running time, we use a recurrence equation, which deﬁnes mathematical statements that the running time of a recursive algorithm must satisfy. We introduce a function T (n) that denotes the running time of the algorithm on an input of size n, and we write equations that T (n) must satisfy. For example, we can characterize the running time, T (n), of the recursiveMax algorithm as T(n) = 3 if n = 1 or T(n - 1) + 7 otherwise, assuming that we count each comparison, array reference, recursive call, max calculation, or return as a single primitive operation. Ideally, we would like to characterize a recurrence equation like that above in closed form, where no references to the function T appear on the righthand side. For the recursiveMax algorithm, it isn’t too hard to see that a closed form would be T (n) = 7(n − 1) + 3 = 7n − 4.

I can clearly understand that in the case of a single item array, our T(n) would be just 3 (only 3 primitive operations will occur, i.e. the comparision n = 1, the array index A\[0\] and the return operation), but I cannot understand why in the case where n is not 1 we have T(n-1) + 7. Why + 7? From where did we get this constant?

Also, I cannot comprehend this *closed form*: how did he get that T(n) = 7(n - 1) + 3?

I appreciate any help.

# Answer
> 0 votes
For $n\geq 2$, I believe that the $T(n) = T(n-1) + 7$ because of the comaparison operation $n = 1$, returning $\max$, computing $\max$, calling *recursiveMax*, computing *recursiveMax*, i.e., $T(n-1)$ term, computing $n-1$ twice, accesing $A\[n-1\]$.

However, the constant should not matter, since we are interested in asymptotic running time analysis, as nir shahar is saying.

Now, we have $T(n) = T(n-1) + 7$ for $n\geq 2$. You can expand this term, as follows:

\begin{align} T(n) &= T(n-2) + 2\cdot7 \\ &= T(n-3) + 3 \cdot 7 \\ &= T(n-4) + 4 \cdot 7 \\ &=... \\ &=T(1) + 7 \cdot (n-1) \\ &= 3 + 7 \cdot (n-1) \end{align}

This answers your second question.

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


title: Finding the perfect matching

text:
# Question
Title: Finding the perfect matching
This the following graph where I want to find the perfect matching and a maximum matching

I converted this to an bipartite graph, and found that the perfect matching exists and also found an maximum matching, but I am unable to justify that it is indeed maximum. How can you justify that a given matching is indeed maximum?

# Answer
To show that a certain matching $M$ is maximum in a graph $G$, it is necessary and sufficient to show that there is no augmenting path relative to $M$: a path in $G$ that starts and ends on free (unmatched) vertices, and alternates between edges in and not in $M$.
> 1 votes

# Answer
The graph admits no perfect matching. Look at the following figure and notice that any perfect matching must match vertex $x$. By symmetry suppose it does so with the blue edge $(x,y)$. Then, since $u$ and $v$ need to be matched, the matching must necessarily contain the two remaining blue edges. However, in this situation, vertex $w$ cannot be matched anymore. Therefore any matching has at least one unmatched vertex.

From the above discussion we know that the maximum size of a matching one can hope for is $\left\lfloor\frac{10-1}{2}\right\rfloor = 4$.

Here is a possible (maximum) matching of size $4$:
> 1 votes

---
Tags: graphs
---


# Question
Title: How many colors will be used in the following bipartite graph
I decided to create an algorithm to find the colors that is used to color a bipartite graph, the algorithm proceeds as follows:

* Rename the vertices in a some order $v\_1,v\_2,\ldots,v\_n$.
* Do a single pass through all vertices of the graph, starting from $v\_1$.
* To each $v\_i$ assign the smallest available color not used among its already colored neighbors.

Now I have consider the following graph, $K\_{4,4}$:

The question, I have is that, I have ordered the vertices in the graph. How many colors will be used here? The algorithm is giving me 7, I don't know why?

One very important question that I have is, will the change in orderings, would get the maximum and minimum colors? I think yes, but I am not getting it.

# Answer
Your algorithm is known as greedy coloring, and its properties are well-known.

When run on a complete bipartite graph, it always produces a 2-coloring (this is a nice exercise).
> 2 votes

---
Tags: graphs, colorings
---


# Question
Title: What is the formal mathematical model of a register machine?
I have been searching the web for a *mathematical model* of a register machine and have fallen short. The closest I have found is found here:

But I am looking for more detail than what is provided there, such as similar to the Turing Machine definition using tuples:

What resource describes the mathematical definition of either register machines or RAM machines at this level of formality? If none exist, how would you describe it (or please write the definition here otherwise for reference).

# Answer
> 2 votes
In my taste the register machine definition you found is good to go. The only difference is that it specifies its components using the phrase "is specified by", whereas the second definition lists those components explicitly as a 7-tuple.

The components of the register machine in tuple style are probably a sequence of registers, a set of labels, and a list of instructions, one for each label. What is perhaps lacking is the specification of an initial label, where the computation starts.

Your Turing machine might be formally specified, but it contains only the hardware (states and alphabet) and the program (transition function) but it lacks semantics: how do we build computations, what is the behaviour of the machine? The register machine does contains some semantics, although in words only, "add 1 to the contents of register $R$", but quite sufficient to see what is the meaning of the instructions.

Note there is no unique formalization of a register machine. There are variuos possibilities for the available instruction types. Wikipedia lists various historical variants.

---
Tags: computation-models, discrete-mathematics
---


# Question
Title: How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?
In Dijkstra's original paper, he talks about two problems related to graphs. The second one is the problem of finding the shortest path between two nodes, which is what is most commonly meant by Dijkstra's algorithm. However, he also poses another problem, namely that of constructing the tree of minimum total length between the $n$ nodes of the connected graph.

I am a bit unsure as to what this exactly means, so I tried performing the algorithm but in step 2 one needs to compare the branch (or edge) under consideration to the 'corresponding' branch in set II. It is however not clear to me what this corresponding branch is supposed to be. It also seems to me that at some point in the algorithm one needs to add branches to set II, but it is not clearly described when this happens.

So my question is how does this algorithm work exactly and what precisely does it output?

Below you can find the algorithm in image form:

# Answer
In modern terms, this problem is called Minimum Spanning Tree: Find the subtree of the input graph that minimizes the total weight of its edges. The algorithm here suggested by Dijkstra is today known as Prim's algorithm.

Regarding your question, the "corresponding branch" to a node $b$ in set $B$ is the shortest edge that runs from some node that was put into set $A$ at an earlier step, to $b$. There might well be no such edge; in that case you should clearly put your new edge into set II.
> 6 votes

# Answer
The tree of minimum total length is nothing but the minimum spanning tree. The algorithm that you are talking about is nothing but Prim's algorithm, also called Prim–Dijkstra algorithm.

**Answer to Your Question:** The corresponding branch is defined for every vertex $v \in B$. It is the minimum weighted edge among the edges that are incident on $v$ and set $A$. That is minimum weight edge among the edge set: $E\_{v} = \\{(u,v) \mid u \in A \\}$.
> 5 votes

---
Tags: graphs, spanning-trees, dijkstras-algorithm
---


# Question
Title: algorithm that determines if a given number n is composite or not on input <n>
Consider the following algorithm that determines if a given number n is composite or not

```
on input <n>
for i = 2..n
check if i divides n
if it does accept
reject

```

a) The loop runs n times so why this algorithm is not polynomial time in the size of input?.

b) How can a nondeterministic TM decide this problem(composite number) in polynomial time? Can we use that nondeterministic TM polynomial time algorithm to solve this problem in polynomial time on a computer. If not why?

# Answer
1. The size of the input is $\log(n)$ since it requires that much bits to represent $n$ in memory. Hence, the algorithm is exponential with respect to the size of the input.
2. Just ask for the composition. Multiplying can be done in polynomial time.
> 0 votes

# Answer
n is not polynomial in the size of n. In decimal: 1..9 have size 1. 10..99 have size 2. ... 1,000,000,000 to 9,999,999,999 have size 10. n grows exponential with the size of the input, not polynomial.

A non-deterministic TM can basically guess two factors a and b and then check if a\*b = n. That is easily done in polynomial time.

There are well-known and simple probabilistic algorithms that solve the problem in polynomial time in the size of n and there is a quite complicated non-probabilistic algorithm that runs in polynomial time.
> 0 votes

---
Tags: algorithms, turing-machines
---


# Question
Title: I'm studying a trie tree, where I want to delete a word, Please make me understand the algorithm
```
def delete(root: Node, key: str) -> bool:
    "Eagerly delete the key from the trie rooted at `root`.
    Return whether the trie rooted at `root` is now empty.
    """

    def _delete(node: Node, key: str, d: int) -> bool:
        """Clear the node corresponding to key[d], and delete the child key[d+1]
        if that subtrie is completely empty, and return whether `node` has been
        cleared.
        """
        if d == len(key):
            node.value = None
        else:
            c = key[d]
            if c in node.children and _delete(node.children[c], key, d+1):
                del node.children[c]
        # Return whether the subtrie rooted at `node` is now completely empty
        return node.value is None and len(node.children) == 0

    return _delete(root, key, 0)

```

I cannot able to understand what is the purpose of 'd' here anyone please explain me in detail?

# Answer
> 1 votes
`d` is the depth of the current node. In the Trie data structure, the first character is stored at the first level, and the second character is stored at the second level, etc. So, at depth `d`, we seek the node that matches the `d`-th character of the search string.

Exposed `delete(root, key)` method calls inner `delete(node, key, d)` method, with `d=0` and `node=root`. That is very meaningful since we are processing the first character of `key` and we are at depth `0`.

Assuming `key` is not empty, code will continue with the `else` branch. `c=key[0]`. That is the first character of `key`. `node.children` is a dictionary with keys of characters and values of `Node`s. `node.children[c]` is `node.children[key[0]]` at the first round: Take the node that holds first character of key.

Now, we should proceed with recursion: increase depth by one, which is the same as the index of the next character of the key. Use the currently retrieved node from `node.children[c]` as the current node.

The process continues until we exhaust the search string: `key`. That is mentioned on the basis of the recursion.

The return value, although not asked in the question, means: The processed node is now empty - it does not store any key by itself and it does not have any children. This is used in the upper level of recursion, to decide if we should delete the processed node or not.

---
Tags: time-complexity, data-structures, coding-theory, pseudocode
---


# Question
Title: Are functions with a finite domain and codomain always computable?
I apologise if my following reasoning is flawed, but I cannot find the "bug" in it.

Consider two *finite* subsets of $\mathbb{N}$, namely $A$ and $B$. The set of all functions $f:A\rightarrow B$ is clearly finite.

Are the functions in this set computable? I can imagine constructing a huge list of all possible functions $f:A\rightarrow B$. For all of these functions $f$ in this list, you can construct a table describing the inputs and outputs of $f$ (that is, all possible ways to pair the elements of $A$ to the elements of $B$). From this "view", all such functions $f$ seem to be computable, as you have an algorithm (the table) that explains how to compute each $f$.

However, consider a turing machine $M$ with encoding $m$ (with $m\in\mathbb{N}$). Per the Halting Theorem, surely an $M$ such that $h(m)$ is undecidable exists (where $h(\cdot)$ decides termination). Thus, consider the function $f^\star:A\rightarrow B$ such that, for every $a\in A$, $f(a)=h(m)$. This function is undecidable, right?

In my mind, it is as if all $f:A\rightarrow B$ are computable, but when what happens is that you cannot decide "which" of these $f^\star$ is, hence you cannot "in fact" compute it.

Question: **Are all functions with finite domain and codomain computable? If yes, why does my second argument fail?**

# Answer
Your table construction does prove that any function from $A$ to $B$ is computable. You can easily translate the table into many models of computation. For example, as a rewriting system, each input is an element of $A$ and there is one rule $a \to f(a)$ for each $a \in A$. Or, as a Turing machine, use the tape alphabet $A \uplus B \uplus \\{0\\}$ ($\uplus$ is a disjoint union¹), a starting set with a single symbol in $A$ followed by all blanks, a set state $\\{q\_0, q\_1\\}$ where $q\_0$ is the initial state and $\\{q\_1\\}$ is the set of final states, and a finite automaton with a transition $(q\_0, a) \to (q\_1, f(a), R)$ for each element $a \in A$. Or, as a program in pseudocode, the concatenation of `if x = a: return b` for each pair `(a, b)` such that $f(a) = b$. All of these constructions are possible because $A$ is finite.

Your second argument does not prove anything.

> Thus, consider the function $f^\*: A \to B$ such that, for every $a \in A$, $f^\*(a)=h(m)$. This function is undecidable, right?

No, there is no reason why this function would not be computable. $h$ is uncomputable, granted. But $f^\*$ is not $h$. It's some function that happens to coincide with $h$ on a finite subdomain. The restriction of an uncomputable function to a subdomain can be computable. For example, suppose $g\_0$ is a non-recursive function over the integers ($g\_0 : \mathbb{N} \to \mathbb{N}$) and define the function $g : \mathbb{N} \to \mathbb{N}$ by $g(2x) = g\_0(x)$ and $g(2x+1) = 0$ for every $x \in \mathbb{N}$. Well, $g$ restricted to the even numbers is non-recursive, since it's just $g$ with a trivial reencoding of the argument. But $g$ restricted to the odd numbers is recursive, since it's just a contant function.

In fact, by your first argument, the restriction of a function to a finite domain is always computable, regardless of the computability of the original function.

¹ <sub> A disjoint union is the union of the sets where each side is “annotated” to remember which side of the union it comes from. </sub>
> 6 votes

# Answer
Suppose that $A = \\{ a\_1,\ldots,a\_n \\}$. Here is a function that computes $f$ on input $x$:

* If $x = a\_1$, output $f(a\_1)$.
* If $x = a\_2$, output $f(a\_2)$.
* ...
* If $x = a\_n$, output $f(a\_n)$.

The values $f(a\_1),\ldots,f(a\_n)$ are hardcoded.
> 3 votes

---
Tags: computability
---


# Question
Title: Partition of a $k$-partite graph to minimal number of connected sets
Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices.

I'm trying to partition the graph to the minimal number of connected sets.

Sets $A\_0, A\_1, ..., A\_k$ are connected if you can reach from some vertex in $A\_0$ to some vertex in $A\_k$.

Assume the following $k$-partite graph (directed acyclic heading right):

In the above example, the minimal number of connected sets is $3$: $(0,1,2)$, $(3, 4, 5)$, $(6)$.

This problem can be solved using a reduction to the *Set-Cover* problem, however I think it's easier than that.

My idea is to greedily find the longest path from set $0$ to set $k$, then from set $k+1$ to set $j$, until reaching the last set.

Can anyone see in what cases it won't work? Any ideas on how to approach such proof of correctness?

Thanks

# Answer
> 2 votes
Your greedy approach works. Let's first find an abstraction of your problem that makes it easier to come up with a proof:

We have a family $F$ of sets of consecutive integers in $\\{1,\ldots,k\\}$ (we will call them *intervals*) that is closed under taking subintervals, i.e. for any $a\leq b\leq c\leq d$, if $\\{a,\ldots,d\\} \in F$, then $\\{b,\ldots,c\\} \in F$ also. Your problem is to find a minimum number of intervals in $F$ that covers $\\{1,\ldots,k\\}$. Converting from your graphic description to the set of intervals is not hard.

Another useful fact about $F$ is, as OP pointed out, that for every $i\in \\{1,\ldots,k\\}$, $\\{i\\}$ is in F.

My suggestion for a proof goes like this: Take any optimal solution $S^\*$. Show that you can switch out each interval in $S^\*$ with one in your greedy solution to obtain a set of equally few intervals. To this end, the fact that $F$ is closed under taking subintervals comes in handy.

Specifically, let $S$ be your greedy solution. We want to show for any $i$, the first (leftmost) $i$ intervals in $S$ cover at least as much as the first $i$ intervals in $S^\*$. We can show this by induction.

For the base case, it is vacuously true that the first zero intervals in $S$ cover at least as much of $\\{1,\ldots,k\\}$ as the first zero intervals of $S^\*$, which is nothing.

For the induction step, suppose that the hypothesis holds for the $i-1$ first intervals of $S$ and $S^\*$, and we show that it is the case also for the i'th interval. Say that the first $i-1$ intervals in $S$ cover $\\{1,\ldots,r\\}$ and the first $i-1$ intervals in $S^\*$ cover $\\{1,\ldots,r^\*\\}$. By our hypothesis, $r \geq r^\*$. $s^\*\_i$ then ends at some $t^\*$. If $t^\* \> r$, then, since $F$ is closed under taking subintervals, there is an interval going from $r+1$ to $t^\*$. And $s\_i$ is clearly not smaller than this interval. If $t^\* \leq r$, then we know that $\\{r+1\\}$ is an interval in $F$, and again, $s\_i$ is clearly not smaller than this interval. Therefore, if $s\_i$ ends at $t$, then $t \geq t^\*$. This concludes the proof.

I hope this rather thorough writeup can be of any help into how one can design a proof that a greedy algorithm is optimal. It often comes down to showing how, at each step, we have an optimal subsolution. If you took any optimal solution and switched out the first few items for the items you found, you would end up with just as good a solution. In our case, we can, for any $i$, take the interval set $(s\_1,\ldots,s\_{i\_1},s^\*\_i,\ldots,s^\*\_k)$. This is a solution (in fact, some elements may get covered twice or more, but this is not a problem).

---
Tags: algorithms, graphs, greedy-algorithms, partitions, dag
---


# Question
Title: Minimal cut of a directed graph such that disjoint elements are strongly connected
Given an arbitrary directed graph $G$ (which may not necessarily be connected) find a minimum set of edges $S\subseteq E$ such that every disjoint component of $G(V,E\cap S')$ is strongly connected.

A "minimum set" refers to the set with the minimum number of edges. The best algorithm I could come up with is exponential, ex. iterating over all sets of edges. Could this be done faster or probabilistically?

# Answer
There is a fast algorithm for this problem: (assuming you meant that $S$ is the set of edges being *removed* from $G$)

1. Compute the strongly connected components of $G$, with an algorithm of your choice. For example, this DFS-based algorithm can work in $O(|V|+|E|)$.
2. Define $S$ to be the set of edges between any two strongly connected components.

This algorithm is very efficient, running in linear time with respect to $|V|$ and $|E|$.

Additionally, it computes a correct set (which is easy to see why) and this set is the minimal set.

Indeed, if there is an edge $(v,u)$ that is between two strongly connected components, but it is not in $S$, then $(v,u)$ will be in the new graph. Notice there is no path $u\rightsquigarrow v$ (otherwise $v$ and $u$ would have been in the same strongly connected component) and hence, the new graph will contain a component that is not strongly connected.
> 1 votes

---
Tags: algorithms, graphs, connected-components, directed-graphs
---


# Question
Title: Formal semantics of a mutable/imperative stack
When introducing formal semantics for data structures, immutable stacks are a nice simple example :

* $\mathit{is\\\_empty}(\mathit{create()})=\mathrm{True}$
* $\mathit{is\\\_empty}(\mathit{push}(e, s))=\mathrm{False}$
* $\mathit{top}(\mathit{push}(e, s)) = e$
* $\mathit{pop}(\mathit{push}(e, s)) = s$

I am trying to do the same for a mutable stack structure, where the $\mathit{push}$ and $\mathit{pop}$ operations will modify a stack instead of returning one.

The way I am trying to do it is with Hoare triples. I can define the simplest ones (omitting that $s$ is a stack and $e$ an element) :

* $\[\]\ s\gets create() \ \[\mathit{is\\\_empty}(s) \text{ yields True}\]$
* $\[\]\ \mathit{push}(e, s) \ \[\mathit{is\\\_empty}(s) \text{ yields False}\]$

However I am not finding satisfactory axioms for $\mathit{pop}$. I could do $$\[\mathit{is\\\_empty}(s) \text{ yields some value } b\]\ \mathit{push}(e, s)\mathord{;} \mathit{pop}(s)\ \[\mathit{is\\\_empty}(s) \text{ yields the same value } b\]$$.

But this is formally only applicable when one would push and immediately pop, which is too restrictive.

With the immutable version, the same axiom (mutatis mutandis : sequence vs. composition) is acceptable because in any actual $\mathit{pop}(s)$ where $s$ is an expression that correctly denotes a non-empty stack, this expression $s$ can be reduced (in the sense of rewriting) to a normal form $\mathit{push}(\cdot, \cdot)$ and the axiom will then apply, allowing for further reduction.

This does not seem to work in the mutable/imperative case. **Or does it ?**

A solution would be to use properties that express the length of a stack~: pushing adds one, poping subtracts one, and expressing emptiness becomes easy. But this would not be sufficient for tracking the values of the elements ; applying the same idea would amount to having a whole immutable stack in the Hoare properties to track the mutable stack in the imperative program.

**Is there a neater approach to this ?**

# Answer
> 1 votes
After discussing it with specialists, a standard approach would be to denote the state of the mutable stack with an immutable stack in the Hoare triples.

E.g. :

* $\[\]\ s\gets create() \ \[s = \mathtt{\[\]}\]$
* $\[s = \mathtt{SomeStack}\]\ push(e, s) \ \[s = \mathtt{e\mathbin{::}SomeStack}\]$
* $\[s = \mathtt{\[\]}\]\ b\gets is\\\_empty(s)\ \[ b = \text{True} \]$
* $\[s = \mathtt{\\\_\mathbin{::}\\\_}\]\ b\gets is\\\_empty(s)\ \[ b = \text{False} \]$
* $\[s = \mathtt{h\mathbin{::}t}\]\ x\gets pop(s)\ \[ x = h, s = \mathtt{t} \]$

This is rather cumbersome, but it works. In a sense, it is not very different from what we do with variables in general, except that there are more than one way to change the value of a variable.

Things will get nasty if we begin to have alias problems, but this was to be expected ; separation logic is the key there.

---
Tags: semantics, stacks, hoare-logic, imperative-programming, persistent-data-structure
---


title: How can I make inference in CompuBERT?

text:
# Question
Title: How can I make inference in CompuBERT?
My question is about the paper Three is Better than One Ensembling Math Information Retrieval Systems (a system used for math information retrieval - both for finding answers and formula search)(code on github).

Before the questions, the following figures illustrates:

CompuBERT (taken from Three is Better than One Ensembling Math Information Retrieval Systems).

sentence-BERT (taken from Sentence-BERT Sentence Embeddings using Siamese BERT-Networks).

CompuBERT uses sentence-BERT but the paper Three is Better than One Ensembling Math Information Retrieval Systems does not explain the inferece (question answering) step. (the inference step in sentence-BERT is illustrated at the bottom left on the picture)

How can I make inferece with CompuBERT?

(please explain using the implementation on github)

# Answer
CompuBERT's objective is to create representations, i.e. embeddings $E$ such that a distance of a question to a relevant answer is minimal, while its distance to an irrelevant question is maximal.

On indexing (see in code), you infer these embeddings $Ea\_{1,..,n}$ for every potential answer in the collection.

On inference (see in code), you first infer an embedding $Eq$ of the asked question. Then, the embeddings of the relevant answers to this question will be the ones having the closest embeddings in your indexed collection. Hence, you search for the answers with minimal distance $\text{dist}(Eq, Ea\_i)$.

As shown in Fig. 7, CompuBERT is fine-tuned to optimize $\text{dist}(Eq, Ea\_i)=\cos(Eq, Ea\_i)$, so using a cosine distance might be a good choice of distance a function. Authors of Sentence-BERT report good performance for other distance metrics as well, depending on the use-case.

Note that by the time, we've extended our research further and found out that for this specific task, better objectives than *Cosine Similarity Loss* can be found, such as *Multiple Negatives Ranking Loss*. A paper with the results, together with a simplified implementation will be published soon in the following weeks.
> 3 votes

---
Tags: machine-learning
---


title: How can I convert a Grammar to NFA?

text:
# Question
Title: How can I convert a Grammar to NFA?
Hello I have a task where I´m stucking at.

I have to convert a Grammar to NFA. I have these information:

```
G=(V,T,P,S) V={S}, T{0} and

S -> 0S
S -> 0

```

I can´t do anything with this information for me it´s not clear. If someone can help it would be very nice.

# Answer
The language of the grammar is clearly $0^\*0$. Hence just build an NFA for this language (which is very easy to do).
> -1 votes

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


# Question
Title: How can I convert from DFA in to regular grammar?
I have following information.

```
        0    1
-> *q0  q0  q1
    q1  q1  q2
    q2  q2  q0

```

I have to convert this in to a regular grammar.

I wrote this:

```
q0 = q2,0 + ε
q1 = q0,0 + q1,0
q2 = q2,0 + q1,1 + q1,1

```

# Answer
> -2 votes
Treat the DFA like a PDA, and then use some algorithm that transforms PDAs to CFGs.

---
Tags: automata, finite-automata, formal-grammars, regular-expressions
---


# Question
Title: An integer (a string of digits) is $\text{/[0-9][0-9]$\ast$/}$. (Why isn't it just $\text{/[0-9]$\ast$/}$?)
I am currently studying the textbook *Speech and Language Processing*, 3rd edition (draft), by Jurafsky and Martin. Chapter **2.1.1 Basic Regular Expression Patterns** says the following:

> The regular expression $\text{/\[1234567890\]/}$ specifies any single digit. While such classes of characters as digits or letters are important building blocks in expressions, they can get awkward (e.g., it's inconvenient to specify
>
> $$\text{/\[ABCDEFGHIJKLMNOPQRSTUVWXYZ\]/}$$
>
> to mean "any capital letter"). In cases where there is a well-defined sequence associated with a set of characters, the brackets can be used with the dash (-) to specify any one character in a range. The pattern $\text{/\[2-5\]/}$ specifies any one of the characters 2, 3, 4, or 5. The pattern $\text{/\[b-g\]/}$ specifies one of the characters b, c, d, e, f, or g. Some other examples are shown in Fig. 2.3.

It then says the following:

> This language consists of strings with a *b*, followed by at least two *a*'s, followed by an exclamation point. The set of operators that allows us to say things like "some number of *a*s" are based on the asterisk or $\ast$, commonly called the **Kleene $\ast$** (generally pronounced "cleany star"). The Kleene star means "zero or more occurrences of the immediately previous character or regular expression". So $\text{/a$\ast$/}$ means "any string of zero or more *a*s". This will match *a* or *aaaaaa*, but it will also match *Off Minor* since the string *Off Minor* has zero *a*'s. So the regular expression for matching one or more *a* is $\text{/aa$\ast$/}$, meaning one *a* followed by zero or more *a*s. More complex patterns can also be repeated. So $\text{/\[ab\]$\ast$/}$ means "zero or more *a*'s or *b*'s" (not "zero or more right square braces"). This will match strings like *aaaa* or *ababab* or *bbbb*.
> For specifying multiple digits (useful for finding prices) we can extend $\text{/\[0-9\]/}$, the regular expression for a single digit. An integer (a string of digits) is thus $\text{/\[0-9\]\[0-9\]$\ast$/}$. (Why isn't it just $\text{/\[0-9\]$\ast$/}$?)

I don't understand why an integer (a string of digits) isn't $\text{/\[0-9\]$\ast$/}$. For $\text{/\[0-9\]\[0-9\]$\ast$/}$, it seems to me that, if we go by order of precedence, the first $\text{\[0-9\]}$ is a single digit, and then $\text{\[0-9\]$\ast$}$ is the next zero or more occurrences of digits, so this part makes sense. But it seems to me that $\text{/\[0-9\]$\ast$/}$ would just be the next zero or more occurrences of digits, so it seems that that would work as well, no? What am I misunderstanding here for $\text{/\[0-9\]\[0-9\]$\ast$/}$ and $\text{/\[0-9\]$\ast$/}$?

# Answer
The empty word $\epsilon$ isn't an integer. Integers are $0, 1, 2, 3, \dots, 10, 11, \dots$

Clearly none of them have $0$ letters when you write them, and hence they are not $\epsilon$.

Hence, you want an integer to be of the form $\text{/\[0-9\]\[0-9\]$^\ast$/}$.
> 5 votes

# Answer
$\[0-9\]\*$ includes all finite strings of the digits including the empty string $\epsilon$ (Some books denote the empty string by $\lambda$). An integer, by definition, has at least one digit. Hence, $\[0-9\]\[0-9\]\*$ is the correct definition. It is not possible to obtain an empty string from this definition.
> 2 votes

---
Tags: regular-expressions, natural-language-processing
---


# Question
Title: Nearest Neighbour search with Kirkpatrick's Hierarchy and Re-Triangulating Delaunay after vertex removal
Ok, so I'm having bit of an issue understanding nearest neighbour search with delaunay triangulation.

In particular, how do I re-triangulate my delaunay triangulations once I introduced holes?

But I should probabl provide a bit of context:

(source: university script, not sure I should/am allowed to link to it, so please just take my word for it that this is how it's explained therein. \[I'm skipping most of the proofs here because they aren't relevant to the question I'm having.\])

> **Theorem 10.17** Given a triangulation T for a set P ⊂ R2 of n points, one can build in O(n) time an O(n) size data structure that allows for any query point q ∈ conv(P) to find in O(log n) time a triangle from T containing q. The data structure we will employ is known as Kirkpatrick’s hierarchy.

> We will now the develop the data structure for point location in a triangulation, as described in Theorem 10.17.
>
> The main idea is to construct a hierarchy T0,. . . ,Th of triangulations, such that
>
> * T0 = T \[= Delaunay Triangulation\],
> * the vertices of Ti are a subset of the vertices of Ti−1, for i = 1, . . . , h, and
> * Th comprises a single triangle only.

> Search(x ∈ R2)
>
> 1. For i = h, h − 1, . . . , 0: Find a triangle ti from Ti that contains x.
> 2. return t0.
>
> This search is efficient under the following conditions.
>
> (C1) Every triangle from Ti intersects only few (\>= c) triangles from Ti−1. (These will then be connected via the data structure.)
>
> (C2) h is small (\>= d log n).

Ok, I get the *idea* behind it, I'm not certain about the actual implementation. Let's read on:

> Our working plan is to obtain Ti from Ti−1 by removing several independent (pairwise non-adjacent) vertices and re-triangulating. These vertices should
>
> a) have small degree (otherwise the degree within the hierarchy gets too large, that is, we need to test too many triangles on the next level) and
>
> b) be many (otherwise the height h of the hierarchy gets too large).

> **Lemma 10.22** In every triangulation of n points in R2 there exists an independent set of at least ⌈n/18⌉ vertices of maximum degree 8. Moreover, such a set can be found in O(n) time

> Let W ⊆ V denote the set of vertices of degree at most 8. Claim: |W| \> n/2

> Construct an independent set U in T as follows (greedily): As long as W != ∅, add an arbitrary vertex v ∈ W to U and remove v and all its neighbors from W.

> Obviously U is independent and all vertices in U have degree at most 8.

> Construct the hierarchy T0, . . . Th with T0 = T as follows.
>
> Obtain Ti from Ti−1 by removing an independent set U as in Lemma 10.22 and re-triangulating the resulting holes.

Alright, let's try this out. Let's say we have a voronoi diagram like so:

where green are our sites and red is our query point.

T0 is our delaunay triangulation

Let's construct our first set of independent vertices U0. As all vertices have degree \< 8, we can pick any we want, but we know from above that

> These vertices should
>
> a) have small degree (otherwise the degree within the hierarchy gets too large, that is, we need to test too many triangles on the next level) and
>
> b) be many (otherwise the height h of the hierarchy gets too large).

So let's start with the leftmost vertex, which has degree 3, and take it from there:

Remove these vertices and their edges:

And now re-triangulate to obtain T1 ... how?

I'm assuming T1 should end up looking like this ...

But that got me thinking ...

Ultimately, the search algorithm given is

> Search(x ∈ R2)
>
> 1. For i = h, h − 1, . . . , 0: Find a triangle ti from Ti that contains x.
> 2. return t0.

But if in the beginning, I would have set my red query point over here...

That would still be within the convex hull of T0 (our delaunay triangulation), *BUT* we'd have no way to find a triangle in T1 that contains it.

So that can't be T1.

I'd appreciate some help in understanding how Kirkpatrick's Hierarchy is constructed.

# Answer
To make our life easier, we always assume that the convex hull of the triangulation consists of three points. If it is not, just add three points far away and triangulate. Then, the important thing is that those points that we remove are always internal points, never on this outerface that is a triangle. The reason why we want them to be independent, is because we want the following property: after removing the points, we obtain a triangulation with holes, and each hole is star shaped (there exists a point that sees all the edges of the hole). So no point can be on the boundary, and no two points removed are allowed to be adjacent. You still need to argue why you can have that many points.

This is why the convex hull of the triangulations is always the same, and we don't have the issue you mention
> 1 votes

---
Tags: data-structures, computational-geometry, nearest-neighbour, voronoi-diagrams
---


title: Is "Query Equivalence" decidable?

text:
# Question
Title: Is "Query Equivalence" decidable?
I have studied in my Computability course that it is impossible to design an algorithm $A(x,y)$ which decides, for every couple of programs ($P\_1$, $P\_2$), whether they are equivalent (e.g. $\forall x \in Data:P\_1(x) = P\_2(x)$). This is easily shown with Rice's theorem.

I was wondering if a similar problem with SQL queries is solvable:

**Is it possible to design an algorithm $A\_D(x,y)$ which, given a fixed database schema $D$, decides if, for every possible instance of $D$, $Q\_1$ and $Q\_2$ return the same table $T$?**

---

**Appendix**

As suggested in the comments, I'll now specify the legal operations for $Q\_i$. I am talking about simple queries such as:

* Simple queries with SELECT \[DISTINCT\] ... FROM ... WHERE
* Queries with subqueries
* Queries with aggregated operators
* Queries with GROUP BY and HAVING
* CREATE VIEW

Furthermore, let's assume our SQL is not turing complete, so no CTE or RECURSIVE are allowed. Lastly, I mean only SELECT-like queries, no UPDATEs, INSERT INTOs, etc...

# Answer
> 5 votes
Suppose the abstract SQL you're considering has support for infinite-precision "big" integers that can store any integer values, and that these support `*`, `+`, and `=` in `WHERE` clauses.

Fix the schema as $k$ such integer values columns called `x_1`, ..., `x_k`.

---

Query equivalence in this schema is undecidable by a reduction to the satisfiability of Diophantine equations (Hilbert's 10th problem):

A system of Diophantine equations can be described as a multivariate-polynomial with integer coefficients $p(x\_1, \dots, x\_n) = 0$. Determining whether or not there is any tuple $(x\_1, \dots, x\_n) \in \mathbb{Z}^n$ that satisfies the equation is known to be an undecidable problem.

This condition can be directly represented as the `WHERE` clause in the SQL described above: `WHERE p(x_1, ..., x_k) = 0` (expanded using `*` and `+`).

Determining whether or not `SELECT * FROM t WHERE p(x_1, ..., x_k) = 0` is equivalent to `SELECT * FROM t WHERE false` is determining whether or not `p(x_1, ..., x_k)` has some assignment of integers $x\_1, \dots, x\_k$ such that $p(x\_1, \dots, p\_k) = 0$; thus if we were able to determing the equivalence of SQL queries, we would be able to determine the satisfiability of Diophantine equations.

Because the satisfiability of Diophantine equations is undecidable, so must this query equivalence problem.

---

The above doesn't rely on any particularly interesting features of SQL -- it certainly doesn't rely on any tricky "Turing complete" features of many SQL implementations -- it relies solely on the embedded ability to evaluate expressions involving integers. That means this is unfortunately rather unenlightening, but it also makes it hard to pare down SQL to something that won't immediately have undecidability creep in.

Like any theoretical result on decidability would, this does require arbitrary precision integers are supported. While I don't know of any popular SQL implementation that truly supports unbounded integers, PostreSQL for one documents arbitrary-precision integers that support at least 1000 digits of precision, which is likely "large enough" to say an abstract model of SQL supports unbounded integers.

It might be worth analyzing a SQL without any support for arithmetic operators like `+` and `*`, though I think it might be possible to emulate both `+` and `*` using `SUM` and `JOIN`s; even without `SUM` I think it may be possible.

# Answer
> 4 votes
The problem of query-equivalence, and the problem of query-containment (knowing if the result of some query Q1 is a subset of the result of some other query Q2, for any possible instance of the database) are undecidable in relational algebra \[1\].

Hence, the query-equivalence problem is undecidable in SQL (even without arithmetic operations, as already suggested).

\[1\] Abiteboul, Serge, Richard Hull, and Victor Vianu. Foundations of databases. Vol. 8. Reading: Addison-Wesley, 1995.

---
Tags: computability, database-theory
---


# Question
Title: What are some variants of the rod cutting problem?
I am looking at the possible implementations for solving the rod cutting problem (CLRS). Do you know of any variants of this problem and their use in industry?

# Answer
Rod Cutting Problem have many variations, One is with lenghts like 1,2,3,4,5,6,7,8

And another are with lenghts like 1, 5, 6, 8, 13, 15, 16, 19, 21, 22
> -3 votes

---
Tags: algorithms, dynamic-programming
---


title: Clustering Formulas for Networks

text:
# Question
Title: Clustering Formulas for Networks
Consider an undirected, unweighted graph =(,). I want to compute the clustering coefficient of each node. In the publicly available lecture from stanford, the following formula for computing the clustering coefficient $e\_v$ for a node $v$ is given as:

$$e\_v = \frac {\\#\text{edges among neighboring nodes}} {\\#\text {node pairs among } k\_v \text {neighboring nodes}} = \frac {\\#\text{edges among neighboring nodes}}{{k\_v \choose 2}} \in \[0,1\]$$

while in the documentation of the library networkX for python, defines the clustering coefficient as follows:

$$c\_u = \frac {2T(u)} {deg(u) (deg(u)-1)}$$

where $T(u)$ is the number of triangles through node $u$ and $()$ is the degree of $$.

I calculated a few examples (Erdös-Renyi Networks) and both gave the same result for every node in the example graphs. Can somebody give me the intuition behind that observation?

# Answer
1. $\\#\text{edges among neighboring nodes}$ is the same as $T(v)$ since a triangle through $v$ means that the side opposite to $v$ in the triangle is incident on two neighboring nodes.
2. $k\_{v} = deg(v)$. Therefore, ${k\_v \choose 2} = \frac{k\_{v}(k\_{v}-1)}{2} = \frac{deg(v)(deg(v)-1)}{2}$

Therefore, $$e\_v = \frac {\\#\text{edges among neighboring nodes}}{{k\_v \choose 2}} = \frac {2T(v)} {deg(v) (deg(v)-1)}$$
> 0 votes

---
Tags: graphs, clustering
---


title: Linear programing modeling

text:
# Question
Title: Linear programing modeling
I am trying to prepare for my Linear programing exam and i stumbled upon an exercice that i can't wrap my head around. It goes like this.

**Seven** days before the final match a tennis player is trying to optimize his training sessions. He has 4 different training options - **Serving**, **Volley**, **Right-hand hits**, **Back-hand hits**. He predicted the number of points he could obtain based on the repartition of the training sessions.

|  | Right-Hand | Back-Hand | Volley | Service |
| --- | --- | --- | --- | --- |
| 1 | 3 | 3 | 3 | 7 |
| 2 | 3 | 3 | 4 | 5 |
| 3 | 4 | 4 | 5 | 7 |
| 4 | 5 | 7 | 6 | 7 |

The columns represent the different types of training and the lines represent the number of days dedicated. The intersection is the estimated points he would obtain during the final match. For example if he chose to do 4 days of Right-Hand training he would obtain 5 points in the final match. The goal is to maximize the amount of points he would get.

**Note:** The player must dedicate at least 1 day for each training type.

**Solution:**

We can put x1 = days of Right-hand training, x2 = back-hand etc... In total he has 7 days so the first constraint would be:

x1 + x2 + x3 + x4 \<= 7

He has to dedicate 1 day to each training type so x1, x2, x3, x4 \>= 1 and x1, x2, x3, x4 are integer values. The problem i have is i don't know how to correlate these values to the numbers of points since the maximization requires to find the biggest number of points obtainable.

# Answer
> 0 votes
For $i \in \\{2,3,4\\}$ and $j \in \\{1,2,3,4\\}$,let $x\_{i,j}$ be an indicator variable that is $1$ if and only if at least $i$ days are spent doing the $j$-th type of training.

Let $c\_{i,j}$ be the number of points gained if exactly $i$ days are spent doing the $j$-th type of training.

What you want to optimize is described the following integer linear program, assuming that it is not necessary to train every day.

$$ \max \sum\_{j=1}^4 \sum\_{i=2}^4 x\_{i,j} \left( c\_i - c\_{i-1} \right) + \sum\_{j=1}^4 c\_{1,j} \quad \mbox{s.t.} \\ \sum\_{j=1}^4 \sum\_{i=2}^4 x\_{i,j} \le 3 \\ x\_{i+1,j} \le x\_{i,j} \quad \forall i \in \\{2,3\\}, \forall j \in \\{1,2,3,4\\} \\ x\_{i,j} \in \\{0,1\\} \quad \forall i \in \\{2,3,4\\}, \forall j \in \\{1,2,3,4\\} $$

If it is necessary to train every day, then the first constraint becomes $\sum\_{j=1}^4 \sum\_{i=2}^4 x\_{i,j} = 3$.

---
Tags: linear-programming
---


# Question
Title: If $p(n) := \sum_{i=0}^ka_in^i$ where $a_i\in\mathbb{N}, a_k \ne 0$ AND $k \ge 2$, is $L = \{0^n1^{p(n)} \mid n\in\mathbb{N}\}$ context-free?
I have the really strong feeling it is indeed NOT context-free, since the language $1^{n^k}$ for $k\ge 2$ is not context free (proven by the pumping lemma) and, in a sense, "the order of magnitude" of the number of 1s will always supercede the order of the number of 0s, but I really can't find an exhaustive proof for the global case where $p(n)$ is any polynomial of degree $k$. Any advice is welcome! Thanks in advance!

# Answer
> 2 votes
If $L$ is context-free then so is the language $L'$ obtained from $L$ by changing all $1$'s to $0$'s. Since $L'$ is unary, if it is context-free then it is actually regular. Moreover, in that case the set $N = \\{ n : 0^n \in L' \\}$ is eventually periodic. Consequently, $N$ is either finite or has positive lower density (there exists $\alpha \> 0$ such that for large $n$, $|N \cap \[n\]| \geq \alpha n$). In your case, $N$ is infinite but has upper density zero ($|N \cap \[n\]|/n \to 0$; in fact $|N \cap \[n\]| = O(n^{1/k})$), and so $L$ is not context-free.

# Answer
> 2 votes
Are you familiar with the pumping lemma for CFL? Let P be the pumping constant for the language. Prove that p(P + 1) - p(P) \>= P for all polynomials with degree greater than 1 and nonzero positive coefficients and try to use that fact to break the lemma. Good luck ^^

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


# Question
Title: Where are process pages stored - in the swap space or under file system? Can demand paging work without space space?
The Galvin OS text says that on older systems, there used to be a method, where the entire running process (when in idle state) was moved from the main memory (when main memory ran low) to the disk which acted as a backing store.

The text says that whatever processes we swap out are placed in the "swap space" of the disk.

Now as time passed the concept of swapping was used with paged processes as well:

Now I want to know when an executable is run where is the "process image" created and stored? In the picture below, the `a.out` is executable and I know that the executable is just a binary containing the machine instructions and data and relocation information for the target machine. But the virtual memory of this executable is yet to be formed, or rather the "process" is different from executable, where there is specific: code, static/global variable section, heap section, and stack section.

The diagram below shows that "new process" having 4 pages is in the disk, but wherein the disk is it kept? Under file system or the swap space?

In the demand paging section the text says:

Now the above picture is concerning demand paging. Where in the disk are the pages A, B, C, D, E, F, G, H are placed is it in the swap space or in the file system? Is it so that the system uses swap space only for those dirty pages which are flushed out of the main memory, (while keeping the actual pages of the process under file system) and read them later subsequently, but if that is the case we could as such just switch off the swap space and work with the file system version of the process on disk. I was having this doubt because the text in a section says :

> In Solaris 1 (SunOS), the designers changed standard UNIX methods to improve efficiency and reflect technological developments. *When a process executes, text-segment pages containing code are brought in **from the file system***, accessed in main memory, and thrown away if selected for page out. It is more efficient to reread a page from the file system than to write it to swap space and then reread it from there. ***Swap space is only used as a backing store for pages of anonymous memory (memory not backed by any file), which includes memory allocated for the stack, heap, and uninitialized data of a process.***

---

This is how the text defines virtual memory and demand paging:

> **Virtual memory** involves the separation of logical memory as perceived by developers from physical memory. This separation allows an extremely large virtual memory to be provided for programmers when only a smaller physical memory is available. Virtual memory makes the task of programming much easier, because the programmer no longer needs to worry about the amount of physical memory available; she can concentrate instead on programming the problem that is to be solved. The virtual address space of a process refers to the logical (or virtual) view of how a process is stored in memory. Typically, this view is that a process begins at a certain logical address—say, address 0 - and exists in contiguous memory. In fact, physical memory is organized in page frames, and that the physical page frames assigned to a process may not be contiguous. It is up to the memory-management unit (MMU) to map logical pages to physical page frames in memory.

> The **demand paging** and is commonly used in virtual memory systems. With demand-paged virtual memory, pages are loaded only when they are demanded during program execution. Pages that are never accessed are thus never loaded into physical memory. **A demand-paging system is similar to a paging system with swapping where processes reside in secondary memory (usually an HDD or NVM device)**.

# Answer
I guess, I have understood it: It goes something like this, if we have demand paging, the usual concept, \[from where textbook questions are made, we talk about a page being brought from memory and writing back a page to disk using one of the many page replacement algorithms\] all that works with SWAP SPACE on the disk \[the place where this pages of a process are stored\]. For demand paging to work in our usual intuition we need to have swap space \[file or partition\] on the disk. But suppose we do not have the swap space, then ALL the pages of the process are supposed to be in memory, and process pages can be only moved out when the process is still running, if the page which is to be removed is backed by some file \[opened for reading, possibly in shared memory mode\] or the code section of the process. \[Then if need be, we can later read them back from the file system\]. But if no such pages are available to be removed from the physical memory, we shall have an Out Of Memory (OOM) situation, and then the kernel works accordingly \[like it might decide to kill a process\].

Here is a nice answer.
> 0 votes

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


# Question
Title: Are there any solvers that can handle non-linearity?
I need a way to solve linear and non-linear inequalities over the natural numbers. So equations like this should be solveable:

$\forall n, p, q \in \mathbb{N}. q \cdot (1 + n^p) \leq q$

From what I gather SMT solver should are a good choice for this. I'm not an expert on the area of SMT solvers so I would like guidance on what solver would be best suited for this task. Wikipedia lists many but it's not clear to me which one I should pick.

Any pointers are appreciated! This will be part of a larger program so I can't use online services.

# Answer
> 2 votes
You can't. There is no solver that can handle all constraints over the natural numbers and always finds a solution if one exists. The problem is undecidable, even without allowing variables in the exponent. (See, e.g., https://en.wikipedia.org/wiki/Hilbert%27s\_tenth\_problem.)

So, there is no one-size-fits-all solver.

For this reason, and for other reasons, instead many solvers target a particular class of constraints that they are good at: maybe it's linear constraints, or quadratic, or polynomial, or convex, or something else. So, figuring out how to narrow down the set of constraints you need to support and then looking for a solver tailored for those is generally a more useful approach than trying to find one solver that can handle everything.

You can try a general-purpose solver like Z3, but it is more focused on (fixed-length or bounded-length) bitvectors than (unlimited-length) natural numbers and integers, and I'm not optimistic about its ability to handle hard cases over the natural numbers. While it does have some support for nonlinear constraints, I think that support might be more focused on real numbers than on natural numbers; and in any case Z3's support for arithmetic is primarily focused on linear constraints. I'm especially pessimistic if you have a combination of nested quantifiers together with nonlinear constraints over the naturals. On the other hand, if you have an upper bound on the size of all variables than you can convert to bitvector arithmetic and you will be in a domain where Z3 might have a better chance.

As you can see, the specifics of the constraints matter a lot on what solver is most appropriate and on your chances of success.

---
Tags: constraint-satisfaction, smt-solvers
---


# Question
Title: Are pages moved to the disk when the process is scheduled?
When process A has run long enough and the scheduler decides to run process B, will all the pages of process A be moved to the disk or they remain in the main memory?

# Answer
> 1 votes
A page is a part of RAM memory. It will never move to the disk, unless one of two happen:

1. The program specifically asked to store the memory in the disk (obviously, the memory will move to the disk)
2. There isn't enough RAM to store all of the memory of all processes combined. In this case, some processes' memory will be transferred to a designated area. When that process will need to run, it will be transferred back and once again memory of some other program will be placed there, if needed.

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


# Question
Title: What's the Context-Free grammar of this language : $L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$
I was trying to find the context-free grammar of
\`$L= \\{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \\}$ but I'm stuck. This is what I did so far:

$$ S \to X S Y | \lambda$$ $$X \to a|b$$ $$Y \to c|d $$ but I figured out that it doesn't respect the order.
My Question is different from this one because here $n, m, p or q$ can be equal to $0$ which is not the case in the other question where the answer use $a, d \>0$.

# Answer
> 1 votes
We can "force" the order using the following "trick":

* $S\rightarrow aSd \mid X \mid Y$
* $X\rightarrow bXd \mid Z$
* $Y \rightarrow aYc \mid Z$
* $Z \rightarrow bZc \mid \epsilon$

Basically, we allow $S$ to only derive $a$'s and $d$'s (the "outer" part of a fully derived word). Then, we allow $S$ to derive either $X$ or $Y$, each of them representing a change: we start to write $b$'s instead of $a$'s or start using $c$'s instead of $d$'s (this is the second-innermost part of a fully derived word), and finally $Z$ allows only $b$'s and $c$'s (which is the innermost part of a fully derived word)

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


# Question
Title: Difference Between k-center and k-mean/median
I know that k-mean/median is to find a set $F$ that minimize $$\sum\_{i\in C}\min\_{j \in F} d(i,j)$$ Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance).

The thing I am confused about is what is k-center about? Is it similar to k-mean/median?

# Answer
> 0 votes
I have been doing research on this subject for quite some time. I faced a lot of confusion in the beginning, but now it is clear. The following is an answer close to completion:

The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility such that $F \subseteq L$ and the total cost of assigning the clients to their closest facilities is minimized, i.e.,

$$\text{minimize} \quad \Phi\_C(F) \equiv \sum\_{i \in C} \\, \min\_{j \in F} \big\\{ d(j,i) \big\\}$$

If the distance $d(.,.)$ is replaced with $d(.,.)^{2}$, it is known as the $k$-means problem (referenced from here).

---

In the $k$-center problem, there are two changes:

1. $C = L$
2. The objective function is to find $F\subseteq L$ of size $k$ that minimize $\max\_{i \in C} \Big\\{ \min\_{j \in F} d(i,j) \Big\\}$. That is, we aim to minimize the maximum distance from a client to the closest facility.

Now, when $C$ is not necessarily the same as $L$, the $k$-center problem is known as the $k$-supplier problem.

---

However, for the $k$-median and $k$-means problem, when $C= L$, there is no different name given for the problem. However, in very few pieces of literature, they call the $k$-means problem with $L = C$ as the $k$-medoid problem.

---

**Summary:** You should differentiate the $k$-median/$k$-means/$k$-center problems on the basis of the *objective function* only. The remaining details like if $C = L$ or not, must be taken from where you are reading it from. Different authors make different assumptions. Furthermore, these assumptions can be of the following form:

Type of Space:

1. The space can be Euclidean, i.e., $d(.,.)$ is $\ell\_{2}$ norm or Euclidean norm
2. The space can be $\mathbb{R}^{d}$, with distance measure $d(.,.)$ as $\ell\_{1}$ norm, i.e., taxi-cab norm. **Be careful here:** In the solution to this problem, the optimal center of a cluster is the co-ordinate median of the points in the cluster. Therefore, some people like to call this problem, the $k$-median problem.
3. Likewise, space can be $\mathbb{R}^{d}$, but with distance functions: $\ell\_{0},\dotsc, \ell\_{\infty}$ (see this and related references for the studies done on this topic).
4. The space can be non-metric also, where distances do not follow the properties of metric space, like symmetry, triangle inequality, etc. (see this and related references for the studies done on this topic)

Continuous or Discontinuous Space:

1. In the $\mathbb{R}^{d}$ space, it possible that $L$ is given to you as a discrete/finte set of points in $\mathbb{R}^{d}$. More precisely, we call this problem as the discrete $k$-median/$k$-means/$k$-center problem.
2. On the other hand, it is possible that the entire space $\mathbb{R}^{d}$ is the feasible set of facility locations, i.e., $L = \mathbb{R}^{d}$. We call this the continuous space. It means that there are infinitely many facility locations and also $C \subseteq L$. Therefore, an algorithm for discrete $k$-median/$k$-means/$k$-center will not work here. (see this and related references for the studies done on this topic)

---

Please let me know in the comments if you want me to add something more, in case I missed something.

# Answer
> 0 votes
In the k-center problem, $F$ must be a subset of $C$; that is, you can only build facilities on top of clients.

In the k-mean/median problem, this is not required: you can build facilities anywhere in the metric space.

---
Tags: algorithms, search-algorithms, approximation, search-problem
---


# Question
Title: Deriving a lower bound on the conditional entropy, conditioned on an event
I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\\{0,1\\}^n$, and some arbitrary event $\mathcal{E}$: $$ H\[ Z \mid W \] \ge n - d\ \Longrightarrow\ H\[ Z \mid W, \mathcal{E}\] \ge n - \frac{d+1}{\Pr\[\mathcal{E}\]}. $$

The proof is very short, but I'm unable to follow one of the derivations, which seems to be using a general property of conditional entropy that I'm unfamiliar with.

**Proof of Lemma 19:** We know that the entropy of $Z$ can be at most $n$ no matter on what we condition. Let $H\_b$ denote the binary entropy. It follows that $$ \begin{align} n -d &\le H\[ Z \mid W\] \\ &= \Pr\[ \mathcal{E} \] H\[Z \mid W, \mathcal{E}\] + \Pr\[\neg \mathcal{E}\]\ H\[Z \mid W, \neg \mathcal{E}\] + H\_b(\Pr\[\mathcal{E}\]) \quad (2)\\ &\le \Pr\[ \mathcal{E}\]\ H\[Z \mid W, \mathcal{E}\] + \Pr\[\neg \mathcal{E}\]\cdot n + 1. \end{align} $$ **QED**

**My Questions:**

1. Why does (2) hold? Is this some general property of conditional entropy?
2. How exactly is $H\[ Z \mid W, \mathcal{E} \]$ defined? Is it equivalent to $\sum\_w \Pr\[W=w\mid \mathcal{E}\]\ H\[ Z \mid W=w,\mathcal{E}\]$ or $\sum\_w \Pr\[W=w\]\ H\[ Z \mid W=w,\mathcal{E}\]$?

# Answer
We treat $\mathcal{E}$ as an indicator random variable for the event $\mathcal{E}$ (so $\mathcal{E}$ stands for two different things). The derivation is $$ H(Z|W) \leq H(Z,\mathcal{E}|W) = H(Z|\mathcal{E},W) + H(\mathcal{E}|W) \leq H(Z|\mathcal{E},W) + H(\mathcal{E}). $$
> 0 votes

---
Tags: probability-theory, randomized-algorithms, information-theory, entropy, communication-complexity
---


# Question
Title: What is the actual formula for the efficiency in CSMA/CD?
Let there are $n$ devices in the setup. Let each device sends data with a probability $p$.

Successful transmission for a slot (hence of the setup in general) occurs when only one device communicates.

Hence using the binomial theorem, we have $P\_{success}= \binom{n}{1}\times p \times (1-p)^{n-1}$.

Differentiating $P{success}$ with respect to $p$ and equating it with $0$, we have $p=\frac{1}{n}$. So,

$P\_{success} |max = (1-\frac{1}{n})^{n-1}$

For infinitely large number of devices we have $P\_{success} |max = \frac{1}{e}$.

So the probability of success in the system is $\frac{1}{e}$ and let be $n$ trials.

So expected number of successes = $n \times p = \frac{n}{e}.$

Now for 1 success, we have $1 = \frac{n}{e} \implies n=e$.

Or in other words there is success in $1$ out $e$ trials. \[$P\_{success} |max =\frac{1}{e}$ \] So the number of trials to get one success is $e$.

Here we are finding the average situation. Before a success there are $e-1$ no. of failure in a slot with $e$ trials.$^\dagger$ So these slots with $e$ trials repeat. And hence if $c$ is the no. of failures,

$$\text{Efficiency} = \frac{T\_t} {2\*c\*T\_p+T\_t+T\_p}$$

$$= \frac{1}{2\times c\times a+1+a}= \frac{1}{1+(2c+1)a}= \frac{1}{1+(2(e-1)+1)a}$$

$$ =\frac{1}{1+4.4a}$$

\[Here is a material from MIT\] (see page 14)

But in many places, I find the formula as $\frac{1}{1+6.44a}$. (Simply because in the $\dagger$ they assume $c=e$ which is not correct. Just as in here.)

Again in the *Computer Networking : A Top-Down Approach* by *Kurose and Ross* states the formula to be:

$$\text{Efficiency}=\frac{1}{1+5. \frac{T\_p}{T\_t}}$$

Which is the correct one and which one to follow?

# Answer
> -1 votes
Differentiation of np(1-p)^(n-1) is = n(1-p)^(n-1) + n(n-1)p(1-p)^(n-2) = np^(n-2)(1-p + (n-1)p) = n(1-p)^(n-2)(1 + (n-2)p)= 0 has no solution except p = 1. So the first step of your deduction is wrong.

---
Tags: computer-networks
---


# Question
Title: How to rewrite a function such that integer division is applied before multiplication
Given the following function

$$ f(x,y) = (x \cdot y + 999)\\; \text{div} \\; 1000 $$

where $x \in \\{0, 1, 2, \dots, 2^{63}-1\\}$, $y \in \\{1, 2, 3, \dots, 500\\}$, and the div operator is defined to round down, i.e. $a\\;\text{div}\\;b \\;\colon= \lfloor a / b \rfloor$, is there a way to rewrite the expression such that the div operator is applied before the multiplication?

Let's say $y=20$. Then I expect the function to output the following values:

```
f(0, y) = 0
f(x, y) = 1  // for x in  1 to  50
f(x, y) = 2  // for x in 51 to 100
...

```

My problem is that I'm writing a program and the product $x\cdot y$ can become greater than $2^{63}-1$ and therefore overflow. However, the value of the whole expression is guaranteed to be less than this value, as it can approximately be

$$ (2^{63}-1)\cdot 500/1000 + 999/1000 \approx 2^{63} \cdot 0.5 + 1 \approx 2^{62} $$ at maximum. I tried to find some equivalence relation that involves products, divisions, and floor functions but couldn't find one that matches my problem.

# Answer
> 1 votes
The +999 will make the result go up by 1 *except* when xy is exactly 0 mod 1000.

It's easy to calculate xy mod 1000 without overflow, as (x mod 1000)\*(y mod 1000). So we have two cases:

* xy = 0 mod 1000: then your f(x,y) is the same as xy div 1000.
* xy != 0 mod 1000: then your f(x,y) is the same as (xy div 1000) + 1

So we can focus on just calculating xy div 1000.

The easiest thing is probably to long divide x by 1000. Let's say

$x = 1000a + r$

Of course $a,r$ are easy to calculate as $x\ \mathrm{div}\ 1000$ and $x\ \mathrm{mod}\ 1000$. Then

$xy = 1000ay + ry$

and therefore

$xy\ \mathrm{div}\ 1000 = ay + (ry\ \mathrm{div}\ 1000)$

No part of this expression will overflow if calculated straightforwardly.

---
Tags: integers, rounding
---


# Question
Title: Are Paging and page cache the same in Operating system?
I was looking at paging in OS.

It seems like there are two concepts with the same name but with different features, and I wanted to be clear about those, Paging and page cache.

Before I thought paging as

> (A page, memory page, or virtual page) a fixed-length contiguous block of virtual memory, described by a single entry in the page table

which is related to "fragmentation, frame, segmentation",

and page cache as

> a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory

which is related to "page fault, replacement algorithm, thrashing"

are the same.

But there is no document or any study that those two concepts come together and I was confused about it.

It's still not clear whether those are the same concept and both share relationship with other features like fragmentation, frame, segmentation, and page fault, replacement algorithm, thrashing or not.

# Answer
The page cache is, as the name suggests, a cache of pages.

*Demand paging* is the idea that a page (of virtual memory) does not need to be backed by a page frame (of physical memory) until it's requested for the first time. At that point, the data can be read from secondary memory into RAM, and the program can use it.

When you think about it, this is really a cache problem. The set of pages that are resident in RAM is a cache of pages in secondary storage. Hence, "page cache".

In practice, this is a little more complicated because not everything in RAM is a cached copy of something in secondary memory. The other main kind of page is *anonymous memory*, which essentially means memory that is allocated, such as heaps, stacks, and copy-on-write data. Although back in the day when RAM was expensive, some operating systems treated anonymous memory as a "cache" for secondary swap storage, which simplified the design enormously. We don't typically do this today.
> 1 votes

---
Tags: operating-systems, paging, caching
---


# Question
Title: Modify set to come as close as possible to target set using only specific exchanges
Note: I am searching for an algorithm that can do what I need or something similar to it, so that I can try to adapt it to my needs. My idea here was to ask for a reference (e.g. "This can be solved using an algorithm called xyz") but obviously I would also appreciate it if someone took the time to create one on-the-fly. The latter is not my expectation though. I am mostly looking for some keywords to continue my research on.

---

### Algorithm description

I am searching for an algorithm that can bring a given set of elements as close to a different set of the same length as possible. However the tricky part is that only specific elements may be exchanged.

The elements in the set can be assumed to have an intrinsic order. That is we can define a series `a < b < c < d < ...` for all elements across the sets.

The allowed changes are not known beforehand but are generally in the form of "replace the i-th element in the set with the j-th one" or "Replace the i-th and the j-th element and at the same time the k-th with l-th" or any extension of that. Thus: Pairwise exchanges of one or more pairs of elements where not the element itself but its position within the set is important.

As an example consider the set `{abcd}` and we want to check whether we can turn this into `{dabc}`. The allowed modifications are:

* Switch 0-th with 1-st
* Switch 2nd with 3rd

Using these rules it is impossible to convert the starting set into the target set and thus something that comes as close as possible to it, is enough.

The exact measure of "closeness" is not relevant for me, as long as the end-result is always the same, no matter from which permutation of the set I start (provided it is possible to arrive at the solution using only the given modifications). So in this example it should not matter whether I start from `{abcd}` or e.g. `{badc}`.

The other characteristic of the searched for algorithm is that if it is possible to reach the given target set with the allowed modifications, the algorithm should always transform my start set into the target set.

---

### The underlying application

The context to where I intend to use an algorithm as described above is to determine whether two Tensor specifications (for our intents and purposes a "Tensor" is a multidimensional array) are really referring to one and the same element, taking the Tensor's symmetry into account.

So for instance a Tensor could be $G^{ij}\_{ab}$ and its symmetries allow exchange index $i$ with $j$. Therefore $G^{ji}\_{ab}$ must have the exact same value because there exists a symmetry-relation that tells us that these two must be equal. $G^{ij}\_{ba}$ on the other hand would be a different element.

My idea was to establish something of a "canonical" order of indices such that Tensor elements that are really the same, end up being written in the exact same way and therefore can be compared for equality by a simple `==` check.

In order to do that I would map the indices into a set of indices (e.g. `{ijab}`) which I can sort, since my indices are comparable. Therefore I can create a target set of indices that is independent of the starting set and thus I can use that as a common reference point for all Tensors that contain the same indices (but maybe in different order).

---

### Clarification

The ultimate algorithmic goal is to solve the following problem:

Given a bunch of Tensors, say $G^{ij}\_{ab}$, $G^{ji}\_{ab}$ and $G^{ia}\_{jb}$, the task is to recognize which of these Tensors are actually equal.

Two Tensors are equal if they have the same index-structure or there exists a symmetry-transformation such that the index-structure becomes equal. A symmetry-transformation in this case is the exchange of indices.

Therefore my idea was to map the index-structure of each Tensor into a sequence of indices. In this case that'd end up being $ijab$, $jiab$ and $ iajb$.

The symmetry of the Tensors are read in as user-input and can therefore not be assumed to show any kind of specific properties. The only restriction is that they will always consist of pairwise index exchanges (possibly multiple exchanges can only be carried out together).

For instance such a symmetry operation may be to exchange index 0 with index 1.

Applying this rule, we can see that $jiab$ can be transformed into $ijab$ and thus $G^{ji}\_{ab}$ is the same as $G^{ij}\_{ab}$. $G{ia}\_{jb}$ on the other hand can not be transformed into this form and is therefore a different Tensor element.

In order to not have to perform this analysis every time I want to compare two Tensor elements, I thought about establishing some sort of "canonical" index structure. The idea here is that all equal Tensor elements will be transformed into the same index-structure (whatever that may be exactly) whereas different Tensor elements will result in a different index-structure.

# Answer
> 2 votes
It appears that your problem can be formalized as follows:

Input: group elements $g\_1,\dots,g\_m,y \in S\_n$
Question: can we write $y$ as a product of the generators? i.e., does there exist $i\_1,\dots,i\_k$ such that $y = g\_{i\_1} g\_{i\_2} \cdots g\_{i\_k}$?

(Here $S\_n$ represents the symmetric group on $n$ letters.) This amounts to testing membership in the group generated by $g\_1,\dots,g\_m$. In particular it is membership testing in a permutation group. This can apparently be solved in polynomial time, if I am understanding the following paper correctly:

Polynomial-time algorithms for permutation groups. Merrick Furst, John Hopcroft, Eugene Luks. FOCS 1980.

I'd suggest you check out Gap and Magma to see if they have algorithms for this problem.

# Answer
> 1 votes
Ignoring the algorithm here, the problem with your notion of closeness between two sets needs to be solved by defining what is this "closeness" in your eyes :

1. Does the distance between the element's position in the set VS his position in the target set matters ? If not, then the closeness score could simply be the number of elements correctly placed, and if the "distance" matters, then another problem arises.
2. Which one is better between a set of M correctly placed elements, but X elements placed far from their target position, and a set of M-1 elements with X+1 elements placed close to their target positions ? The way that you would compute your closeness score really matters here because you may need to balance between correctly placed elements, almost correct elements, and badly placed ones.

Without this notion clarified, it would be complicated to create an algorithm to get "as close as possible to a target set".

---

I thought about your problem during the night, and there's a way to solve your problem with a directed search for example. The metyric proposed below only works if there's no difference between an element "close" to his target position, and one "far" from its targets position, as explained above.

First, let's talk about the "closeness metric". Let's say that for any set $S$, which contains $N$ elements, $x\_i$ is a boolean which is equal to 1 if the element is well placed (identical to its place in target set), and 0 if not. The score of a set is $C\_S = \sum\_{i\in \[1,N\]} x\_i * (1 + 10^{-i})$. Each correctly placed element thus adds one to the score, and adds a little digit that can be used to compare two sets with the same number of well placed elements by saying "The one with the earliest misplaced element in the set is worse" (between two sets, the one with the highest value for this metric is considered "closer" to the target set). The only utility of this score is to ensure that between X solutions with the same number of well placed elements, the same one is always chosen.

Your operations on set can be seen as edges in a graph where each node represent a configuration of the set, and edges are links between twoconfigurations when an operation (defined in your rules) allows to transform the first one into the second one. Your relations seem reversible, but if they are not, then it's a directed graph.

To construct your graph, start by adding your initial configuration as the first node, and explore it by using any operation allowed. Each new configuration is added to the graph, linking it to its origin with the defined edge. Then, repeat the operation by choosing an un-explored node. If an exploration gives one or more node that are already explored, you can ignore them as they have "already" ben reached, and there's no need to reach them again.

The process continues until you either reach the solution (target set), or you have no more nodes to explore. Use the metric in a priority queue in order to explore nodes that are close to your target before nodes that are far from it. The best node according to your metric is always the result of the algorithm.

The search can be long if N is very big, and/or if you have many possible operations, but it guarantees that you will always find the same solution, and the target one if possible.

---
Tags: algorithms
---


title: Leaf nodes of B+ Tree

text:
# Question
Title: Leaf nodes of B+ Tree
I have a b+ tree and i want to find the record associated with a specific key Ki. So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists in the table and we can return the record associated with Ki.

Since the leaf nodes have the same structure of internal nodes, how can the algorithm know if a node is a leaf node ?

# Answer
There are two common ways that the implementation of any B-tree variant decides if you're at a leaf node or not.

1. Most B-tree implementations include a tiny header in each node (e.g. to store the number of elements/pointers in the node). It might only be a word in size, but even then, it's usually not hard to find one spare bit to mark leaf nodes vs internal nodes.
2. Unless you are in the middle of a difficult rebalance operation, all leaf nodes are at a fixed depth in any B-tree. So knowing this fixed depth means you can just keep track of how "deep" you are in the tree while searching and you will know when you reach a leaf.
> 0 votes

# Answer
This is code dependant issue, ie it depends on the way u wrote the code & defined the data structure in it.

If u r following the Wikipedia code ( took it from there). I didn't read the whole code but according to the fig they're attaching

-A leaf node has children links = Null (or nil depending on the programming language u r using) -Also, the internal nodes linked list link ( the red square in the Fig) should equal Null as opposed to leaf nodes. -Since this is only 1 pointer, ie easier to check, u could write something like

*While (node.linked\_list != Null)*

To stop the loop when u reach a leaf

(Note that a storage saving code would use one of the children links, say the 1st, as the linked list link, substituting the need to another pointer field by 1-bit Boolean flag identifying leaf nodes and consequently the meaning of this pointer)

Ps.

That's a 2 yrs old question, probably the student graduated & already became a developer by now!!!!
> 0 votes

---
Tags: trees, binary-trees, binary-search-trees
---


# Question
Title: What would happen if while making a connection between memory and CPU, the address lines get's interchanged
While making a circuit connection between Micro Processor and Memory Chips, the Address Lines A0 and A1 got interchanged. Means A0 of address bus got connected wrongly with A1 of Memory chip and A1 of address bus got wrongly connected with A0. Same error has been committed for both RAM and ROM chips. What would happen ?

# Answer
> 0 votes
With RAM it's not much of a problem. True, address 0 will be kept in cell 1 in the RAM, but who cares -- whenever the CPU access address 0 it will be directed to the same place, whatever its name is.

With ROM this might be a problem, since the ROM is pre-coded with content. When the CPU access address 0 of the ROMO it expects to see there the first byte of the ROM's content, however, it will retrieve the second, which might fail the program.

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


# Question
Title: Prove that the greedy algorithm for the minimum edge cover problem is 2-approximation
As said, I had to prove that the greedy algorithm:

> 1. Initialize $C = ∅$
> 2. Look for an un-covered vertex and add one of its edges to $C$
> 3. Repeat 2 while there's uncovered vertices

Is a 2-approximation algorithm.

My take was:

Let's say that $OPT$ (the optimal solution) takes $k$ edges, we should prove that $ALG$ takes at most $2k$ edges.

Let's assume by contradiction that $C=2k+1$. That means that $ALG$ covers at least $2k+1$ vertices, because each edge chosen by $ALG$ covers at least one vertex. We get that $OPT$ covers at most $2k$ vertices but $ALG$ covers at least $2k+1$ which is a contradiction $⇒ C ≤ 2k$

Now that we proved that if $OPT=k$ we get that $ALG ≤2k$ we can easily show that $\frac{ALG} {OPT}≤ 2$

Is my proof correct?

# Answer
No. Your proof would be "correct" for any constant, not only $2$ (which is a clear big red alert!).

The actual proof is as follows:

Let $OPT$ be the optimal solution, and $ALG$ the solution from this algorithm. Notice that each edge in $OPT$ connects two vertices, and thus each such edge must contribute to the covering with *at most* 2 vertices. Hence, the number of vertices in the graph is at most $2k$ where $k$ is the number of edges in $OPT$. Since your algorithm will take an edge for every node at the worst case, the number of edges in $ALG$ must be at most $2k$. Hence, $|ALG|\le 2\cdot |OPT|$, which means that the algorithm is indeed a 2-approximation of the problem.
> 1 votes

---
Tags: approximation, check-my-answer
---


# Question
Title: Proof of an interesting language being non-context free
Let $\Sigma = \\{a, b, c\\}$ and $L = \\{wa^{1 + k + 2n}b^nw^{rev}\mid n, k \in \mathbb{N}\_0, w \in \Sigma^\*\\}$. It is clear that $L$ is context free, but the question is the following:

Let $L'$ be the language of all words $z \in L$, where between the $i$-th and the $(i+1)$-th occurence of the substring $abc$, $z$ has at least $2i$ occurences of $b$. Then prove that $L'$ is not context-free.

My first intuitions were to go about it using the pumping lemma for CFL, but things started to get nasty quite quickly, because firstly I couldn't find the perfect word to contradict it and secondly, the considerable cases for the positioning of the pumpable substring are way too many provided even the bare minimal conditions for the quasi "perfect word". So I ended up giving up on that idea and instead searching for alternatives, but unfortunately my arsenal is not that broad - I tried exploiting closure properties of CFL (mostly closedness under intersection with regular languages), but couldn't figure it out either. So I'd be really interested if there are any slick alternatives that could provide a reasonable proof! Many thanks in advance!

# Answer
> 2 votes
Define $$ L\_0 = L' \cap (b^+abc)^\*(cba b^+)^\* = \\ \\{ ww^{\mathit{rev}} \mid w \in (b^+abc)^\*, ww^R \in L' \\}. $$ Now let $h$ be a homomorphism mapping $a,b,c$ to themselves and $d,e,f$ to $a,b,c$, and let $k$ be the homomorphism that maps $a,b,c$ to themselves and deletes $d,e,f$. Then $$ L\_1 = k(h^{-1}(L\_0) \cap (b^+abc)^\*(fede^+)^\*) = \\ \\{w \in (b^+abc)^\*, ww^R \in L'\\}. $$ Now let $r(a) = abc$ and $r(b) = bb$, and consider $$ L\_2 = r^{-1}(L\_1) = \\{ b^{n\_1} a b^{n\_2} a \dots b^{n\_m} a : n\_i \geq i \\}. $$ We now apply the pumping lemma on the word $bab^2ab^3a \ldots b^p a$ for large enough $p$. The pumping lemma decomposes this word as $uvwxy$, where $vy \neq \epsilon$ and $v,y$ can be pumped. suppose that $v \neq \epsilon$. If $v \in b^+$ then $uv^0wx^0y \notin L\_2$. If $v$ contains an $a$ then $uv^2wx^2y \notin L\_2$.

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


# Question
Title: Complexity of a Turing Machine when changing its alphabet to binary
I found in 'Computational Complexity: A Modern approach' Book the following statement that i dont quite understand its proof:

> For every f : {0, 1}∗ → {0, 1} and time-constructible T : N → N, if f is computable in time T(n) by a TM M using alphabet A, then it is computable in time 4log|A|T(n)by a TM M ̃ using the alphabet {0,1,Blank,◃}.

The proof is on the link :

First Part of proof

Second Part

So basically if we have a running time of T(n) on a certain alphabet A and we wanna switch to binary.. we gonna have to multiply it by log(|A|) (log of base 2, the number of bits to represent an element from A) because every step will be multiplied by the number of bits used to represent the element.

But in the proof, starting from the second paragraph, i dont really understand what they say and how they end up with the '4' in '4log|A|T(n)'.

# Answer
> 1 votes
The first part the proof reads "To simulate one step of $M$, the machine $M^{\sim}$ will: (1) ... (2)... (3)... (4) and (5) ....". Can you see the factor of 4?

You have a good understanding regarding the factor $\log|A|$. Let us take a close look at the steps in each stage of $M^{\sim}$ above. There are $\log|A|$ steps in stage (1) and in stage (5). However, there is only one step in stage (2) or stage (3) or stage (4). So there are less than $2\log|A|$ steps in stage (2), (3) and (4) combined, assuming $\log|A|\gt1$. If $\log|A|=1$, we can just let $M^\sim$ be $M$ and we are done. So there are less than $\log|A|+\log|A|+2\log|A|=4\log|A|$ steps of $M^\sim$ for one step of $M$.

The second part of the proof is justifying that the stage (2), (3) or (4) can be done in one step of machine $M^{\sim}$. It explains the power of larger registers. It points out that we can use more states in $M^\sim$ to identify the possibly much more situations ("states" could have been a better word had we not reserved that word for Turing machine) of the machine. Take your time. You will understand.

# Answer
> 0 votes
To simulate one step for M,M~

1. There are log|A| steps in stage (1) . (log|A| steps)
2. in stage (5),the heads want to write log|A| bits,the heads should use log|A| steps go back to the bagaining position,then use log|A| steps to write log|A| bits.(2log|A| steps)
3. the head should move to next symbol,just 1 stps needed(1\<=log|A|)

we find that M~ should use less than 4log|A| steps to simulate one step for M，so M~ less than 4log|A|T(n) steps.

---
Tags: turing-machines, time-complexity
---


# Question
Title: How to check if $x$ equals a certain value $y$ with while loops, addition and substraction
Consider, we are only allowed to use loops ($while$), addition ($+$), substraction ($-$) and checking if a value is $\> 0$. How can one find out, if a certain variable $x$ equals a value $y$? E.g. how can I find out if $x=4$ by only using the aforementioned methods? For $x=0$ I came up with the following:

```
y = 1
while x > 0:
    y = y - 1
    x = x - 1
while y > 0:
   do something

```

This way, $something$ gets only executed if $x=0$. But I have no clue about values above $0$.

# Answer
Start by calculating $x-y$. This is simple enough:

```
while y > 0:
    y -= 1
    x += 1

```

Now, compare what you got with $0$. That is, compare the value of $x$ *after* the loop to $0$, using the technique you thought of. This will guarantee that "$something$" is executed only if $x-y=0$, or equivalently if $x=y$.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Left recursive grammar to right recursive grammar
I am studying conversion from left recursive grammar to right recursive grammar. The given grammar is

$$E \to E + T \mid T $$

It's equivalent right recursive grammar will be $$\begin{align}E &\to TA\\ A &\to +TA \mid \epsilon\\ \end{align}$$

I understood this, that it is derived from changing the grammar $A \to Aa \mid b$ to its equivalent right recursive grammar and then comparing it accordingly. But why the right recursive grammar for this grammar is not

$$E \to T + E \mid E$$

As it also generates the same language and when there is only addition in an equation then associativity doesn't matter. Why can't this grammar be the equivalent right recursive grammar?

# Answer
The two grammars you provide are both right-recursive and they both recognise the same language. But they are only weakly equivalent to the original grammar (and to each other), because they do not generate the same parse tree. Strong equivalence would require that the same parse tree be derived.

```
            E→E+T         E→T+E              E→TA
              /  \          /  \              /  \
             /    \        /    \            /    \
          E→E+T    T       T   E→T+E        T    A→+TA
            / \    |       |     /  \       |       / \
           /   \   |       |    /    \      |      /   \
         E→T    T  c       a   T     E→T    a     T   A→+TA
           |    |              |       |          |      / \
           |    |              |       |          |     /   \
           T    b              b       T          b    T    A→ε
           |                           |               |
           |                           |               |
           a                           c               c

```

The only one of these grammars which correctly captures the desired parse of $a+b+c$ is the first one, because $+$ is syntactically left-associative. It's true that since $+$ is mathematically associative, meaning that $(a+b)+c = a+(b+c)$, the syntactic associativity doesn't really matter semantically. But syntax doesn't take semantics into account, and there is no guarantee that $+$ is associative. (Indeed, in computational floating-point arithmetic, it is not.) Had the operator had been $-$, for example, the semantics would clearly be altered by the different parses.

(It's not entirely clear how we are to interpret semantically the $A\to +TA\mid\epsilon$ grammar. But I think any natural interpretation would be right-associative.)
> 1 votes

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


title: Union of non-context free languages

text:
# Question
Title: Union of non-context free languages
For two languages over the same alphabet, if neither of them is context-free, can their union still be context-free?

If not, does one of the languages need to be context-free for this to happen? Do both need to be context-free?

# Answer
> 3 votes
Yes, and this works for regularity and decidability as well! (not that this is very helpful in any sense)

For example, take any problem $A$ such that $A$ and its complement $\overline{A}$ are not CFLs (the halting problem as an extreme example)

Their union is $\Sigma^\*$ which is obviously a CFL.

---

As a side note, and thanks for @D. Ben Knoble for pointing this out in the comments, that this is only an *example*. It does not necessarily hold for any two non-CFL languages, and on the contrary also a union of two CFL's *may* (not always!) end up not being a CFL.

# Answer
> 1 votes
Suppose $\Sigma=\\{0\\}$, and $\ell\_1=\\{0^n|n\text{ is prime}\\}$, and $\ell\_2=\\{0^n|n\text{ is not prime}\\}$ that neither of them are context-free languages. But the union of them:

$$L=\ell\_1\cup\ell\_2=\\{0^n|n\geq 0\\}.$$

Obviously $L$ is context-free.

---
Tags: context-free
---


# Question
Title: Runtime of sorting algorithms given a particular input
say that we have {2,3,5,4,6} as input that we want to sort in ascending order. Then, we know that we can use any of the sorting algorithms: bubble, insertion, selection, quick, merge, heap or counting. How can we determine the resultant running time for each of the above algorithms given {2,3,5,4,6} as an input?

# Answer
> 1 votes
**We analysis mentioned algorithms with assumption $n\to \infty$ that $n$ is input size**. So for a small input or constant number of input, measuring the running time of those algorithms are not correct. For example maybe for a given input with small size, after analysis running time you get an equal complexity but in general some of those algorithm have huge difference in time complexity, and we can see it as $n\to \infty$. In-addition, each algorithm that you mentioned have a constant factor, consequently using some symbol such as $O(.)$ to represent the complexity of that algorithm hide that constant.

# Answer
> 0 votes
The running time is measured independently of a particular input, and it is always written in asymptotic form (big-O notation).

You can't know the exact time an algorithm will run, since there are a lot of unpredictable factors that contribute to it.

# Answer
> 0 votes
You can use \<time.h\> in C to precisely figure out how long your sorting program has run.

```
#include <time.h>

int main(){

    clock_t start = clock();

    sort(); // Whatever sorting algorithm of your choice

    clock_t stop = clock();

    float running_time = (float)(stop - start) / CLOCKS_PER_SEC;

    return 0;

}

```

This might give you a rough estimate of how long your program has run, but with a 5 element array of 8-bit integers, you'll always get 0.00 in the *running-time* variable as it's not precise enough.

So, to find a more explicit answer, try to sort an array of 50,000 elements of 32-bit integers. This will give a clearer view of how each algorithm is performing.

---
Tags: runtime-analysis, sorting, quicksort, mergesort
---


# Question
Title: How LRU is used without special hardware?
I had been curious as to which page replacement algorithm is used in OSes like Windows and Linux. I could find that most information on the internet pointed at LRU(Least Recently Used) Algorithm.

But I was reading Modern Operating Systems by A. Tenenbaum and H. BOS, and it's stated that-

"LRU is an excellent algorithm, but it cannot be implemented without special hardware. If this hardware is not available, it cannot be used."

If this is the case then not all computers will have such special hardware. Then, how is LRU implemented in such systems running Windows or Linux?

# Answer
> 4 votes
The Linux kernel uses a (very rough) approximation of LRU, which is the reason why you find mention of LRU, even though it is not the true LRU algorithm. Here is a description taken from the source:

> Per node, two clock lists are maintained for file pages: the inactive and the active list. Freshly faulted pages start out at the head of the inactive list and page reclaim scans pages from the tail. Pages that are accessed multiple times on the inactive list are promoted to the active list, to protect them from reclaim, whereas active pages are demoted to the inactive list when the active list grows too big.

You can find the full details here: https://github.com/torvalds/linux/blob/master/mm/workingset.c

---
Tags: operating-systems, memory-management, memory-hardware, virtual-memory, page-replacement
---


# Question
Title: Asymptotic upper and lower bound of $\frac{1}{n^c}$?
Given a cost function like this $f(n)=\frac{1}{n^c}$ where $c \ge 1$, can we say that $f(n)=o(n)$ and $f(n)=O(n^2)$ are all correct upper bounds, but $f(n)=\Omega(n!)$ and $f(n)=\Omega(2^{n/1000})$ are not correct?

The problem with $f(n)=\frac{1}{n^c}$ is that it decreases as $n$ increases... so for large value of $n$, the function goes to zero.

# Answer
We can check the definitions.

You have that $\frac{f(n)}{n}=\frac{1}{n^{c+1}}\to0$ as $n\to\infty$. Therefore $f\in o(n)$. You also have that for $n\>1$ $|f(n)|\leq 1\leq n^2$. Therefore, $f\in O(n^2)$.

However, for all $C\>0$ we have some $n$ such that $Cn!\leq \frac{1}{n^c}=f(n)$ is not satisfied. It is enough to take $n$ such that $Cn!\>1$. Therefore, $f\not\in \Omega(n!)$. Similarly for all $C\>0$ we can find $n$ such that $C2^{n/1000}\leq \frac{1}{n^c}=f(n)$ is not satisfied. Note that these two negative claims happen for any $c$.
> 2 votes

# Answer
Let me elaborate more on $\Omega(n!)$ and $\Omega(2^{n/1000})$:

$f(n)=\Omega(n!) \implies f(n) \geq c \cdot n! \implies \frac{1}{n^c} \geq c \cdot n!$

Given some constant $c \geq 1$ and $n \geq n\_0$ where $n\_0 = 1$, we can clearly see that $\frac{1}{n^c} \leq c \cdot n!$ for all $c \geq 1$ and $n \geq 1$.

Hence, $\Omega(n!)$ cannot be a lower bound for $f(n)$.

We can use the same logic for $\Omega(2^{n/1000})$. Specifically:

Since $\Omega(2^{n/1000}) = \Omega(2^n)$ for large values of $n$: $\frac{1}{n^c}$ is always less than or equal to $2^n$ (provided that $c\geq 1$).

Hence, $\Omega(2^{n/1000})$ cannot be a lower bound for $f(n)$.

Is that explanation sound?
> -1 votes

---
Tags: asymptotics
---


# Question
Title: Multitape Turing Machine to shorten one's name
I am trying to formulate a multi-tape Turing Machine which converts one's name in the form of "(Firstname with the first letter in caps)(space)(Lastname with the first letter in caps)" to "(First letter of Lastname in caps). (space)(Firstname with the first letter in caps)".

For example, "Jayajit Banerjee" will be converted to "B. Jayajit".

I cannot understand how to approach and solve this problem. Any help is appreciated

# Answer
> 1 votes
You don't need a multi-tape TM for that.

When you see a "space", replace it with a ".". From this point on, the "state" of the TM will be the current letter it sees. Then, it will read the next letter and replace it with the current one. continue doing this until the end of the string.

---
Tags: turing-machines
---


# Question
Title: Can I say that, if f$(n) = 3n^2$, then f(n) = O(n^5)$?
If $f(n) = 3n^2$, then can I say that $f(n)$ has an asymptotic upper bound $f(n)=O(n^5)$?

While that bound is not tight, it is still true, right?

# Answer
Yes. $3n^2 = O(n^5)$.

An easy way to see this is to consider the limit of the ratio $\frac{3n^2}{n^5}$. You have:

$$ \lim\_{n \to \infty} \frac{3n^2}{n^5} = \lim\_{n \to \infty} \frac{3}{n^3} =0. $$
> 3 votes

# Answer
Yes. Following the definition of big-$O$, consider $c=3$, and we want to show that $f(n)\le c\cdot n^5$.

Clearly, $f(n)=3n^2\le 3n^5=c\cdot n^5$ (since $n$ is a positive integer)

Hence, $f(n)=O(n^5)$.

As you have said, this bound is indeed not tight. A tight bound will be: $f(n)=O(n^2)$.
> 1 votes

# Answer
Yes, that is absolutely correct. Why and when would you do this? You would do it if you are in a situation where O(n^2) or O(n^5) doesn't matter.

For example, you want to analyze f(n) + g(n) + h(n). And you found that f(n) = O(n^5). Now as long as you can show that g(n) and h(n) are O(n^5), it doesn't matter what they really are. So say you have g(n) = n^2 log n, you can say g(n) = O(n^5) and in this situation it doesn't matter - the sum of the three functions os still O(n^5).
> 1 votes

---
Tags: asymptotics
---