title: Product of Lexical Specification

text:
# Question
Title: Product of Lexical Specification
I have a problem that asks me to consider the string abbbaacc. I'm supposed to figure out which of the following lexical specification produces the tokenization ab/bb/a/acc.

The options are:

```
A.
    a(b+c)*
    b+

B.
    ab
    b+
    ac*

C.
    c*
    b+
    ab
    ac*

D.
    b+
    ab*
    ac*

```

I just learned about REGEX, and I'm not sure about this, but to solve this problem would I just be trying see which options can make ab/bb/a/acc?

If that's correct, then would the answer be all four of them?

Since all four of them can match to ab/bb/a/acc:

```
A.
     a(b+c)* -> a, ab, acc
     b+ -> bb
B.
     ab -> ab
     b+ -> bb
     ac* -> a, acc
C.
     c* ->
     b+ -> bb
     ab -> ab
     ac* -> a, acc
D.
     b+ -> bb
     ab* -> a, ab
     ac* -> a, acc

```

I'm not sure if I'm doing this correctly.

# Answer
There's not enough information here to answer the question, but I can prove a pretty good guess based on how tokenizers are typically implemented. Generally the tokenizer will run through the list of patterns, trying each one I sequence. If one of them matches it takes the longest possible match as a token, then starts over at the top of the list. I surmise this is the implicit background for the question.

So, for instance, if you have `abbbaacc` and the rules `a(b|c)*` and `b+` in that order, then you'd tokenize that as `abbb/a/acc`.
> 0 votes

---
Tags: regular-expressions
---


title: Find path from A to B which length ≈ L

text:
# Question
Title: Find path from A to B which length ≈ L
I have an undirected weighted graph.

I want to find the path from A to B which length (sum of the weights) is as close as possible to a specific value "L".

To do that, I have been doing a DFS to check all the possible paths... When L is relatively small, it's ok. But when I ask for a bigger L, it takes too much time to complete. I added some criteria to stop searching useless paths but that cannot solve the problem.

So I was wondering how to do what I am searching for. Is DFS the only solution ? I thought about genetic algorithms but I don't know if it would work.

Thank you !

# Answer
> 1 votes
There are no known efficient algorithms for your problem. Consider the case where every edge has weight $1$ and there are $n$ vertices in the graph. A path from $A$ to $B$ with weight (approximately) $n-1$ is (approximately) a Hamiltonian path from $A$ to $B$ and finding Hamiltonian paths is **NP**-hard.

---
Tags: graphs
---


title: Is this counting language context free?

text:
# Question
Title: Is this counting language context free?
Let $\Sigma = \left\\{ 0,\\,1,\\,2\right\\}$. I want to look at the following language: $L=\left\\{ xyz \\, | \\, |x|\_0 + |z|\_0 = |x|\_2 +|z|\_2 \wedge y \in \left\\{ 1 \right\\} ^{\*} \right\\}$.

I would like to prove or disprove $L$ being context-free

I'm having a very hard time to construct a context-free grammer for $L$, so I attempted to build a non-deterministic PDA.

My attempt goes in the direction of: If i want to sum the zeroes from $x$ and $z$, and fron this sum to substract the sum of $2$s from both $x$ and $z$, I can do it differently:

I can count the number of $0$s from $x$ by inserting a #, then remove one # for every $2$ I count, if negative I'll push @ . Then I will do the same with $z$.

The points are:

1. I'm not sure if this idea will work?
2. If this language is CFL, I have no idea how to begin constructing a CFL grammer for it?

# Answer
> 3 votes
1. **Your idea is correct.** After all, $|x|\_0 + |z|\_0 = |x|\_2 + |z|\_2$ if and only if $|x|\_0 + |z|\_0 - (|x|\_2 + |z|\_2) = |xz|\_0 - |xz|\_2 = 0$. Note, however, you must (ab)use nondeterminism correctly so as to guess where $y$ is so as to know what belongs to $x$ and what to $z$.
2. Producing a CFG from a PDA is, unfortunately, not easy in general. There are cases in which, given a CFL, it is (much) easier to construct one than it is to construct the other. Having experience in these kind of exercises might give you a sudden flash of inspiration; failing that, you can always resort to the standard construction.

In this particular case, your "flash of inspiration" could have come from taking a closer look at the equation on the number of zeroes and two's. The idea is the equation holds for the empty word and we can produce symbols while conserving it; that is, for example, if you generate a zero for $x$ (i.e., $|x|\_0$ is increased by one), then you also want to generate a $2$ somewhere so the equation still holds. Hence, a CFG with the following set of productions suffices: $$\begin{align\*} S &\to X\_0 S X\_2 \mid X\_2 S X\_0 \mid X S X \mid Y \mid \varepsilon, \\ X\_0 &\to X 0 \mid 0 X, \\ X\_2 &\to X 2 \mid 2 X, \\ X &\to 0 X 2 \mid 2 X 0 \mid 1 X \mid X 1 \mid \varepsilon, \\ Y &\to 1 Y \mid \varepsilon \end{align\*}$$ A brief reasoning to make sure every word $w = x y z \in L$ is generated: The ones in $x$ and $z$ are generated by $X$, so we can exclude them. Further, any neighboring pair $02$ or $20$ may be generated by $X$ (and we include $X$ everywhere it is possible for such a pair to appear). Removing all such pairs, the only possible word left is of the form $x = 0^n$ and $z = 2^n$ or $x = 2^n$ and $z = 0^n$, and we can generate $w$ by using the appropriate rules for $S$ containing $X\_0$ and $X\_2$.

# Answer
> 2 votes
> I can count the number of 0s from $x$ by inserting a #, then remove one # for every 2 I count, if negative I'll push @ . Then I will do the same with $$.

This PDA is pretty good. You can certainly continue to convert this PDA to a context-free grammar according to some algorithm such as the one given in the proof of the language of a PDA is context-free, although that procedure is usually rather heavy and less enlightening.

> If this language is CFL, I have no idea how to begin constructing a CFL grammer for it?

I would agree that it might not be easy. I would recommend that you should read this answer to how to produce a context-free grammar by Hendrik Jan if you have not yet.

---

Here is the simplest context-free grammar for $L$. $$S \to 0S2S \mid 2S0S \mid 1S \mid \epsilon$$

Note that $L=\\{ xz \mid |x|\_0 + |z|\_0 = |x|\_2 +|z|\_2\\}=\\{ w \mid |w|\_0 = |w|\_2 \\}$. That is, $L$ is the language of words with equal number of 0s and 2s, as you have observed.

Here is a brief reasoning that shows the language of above grammar is $L$.

* It is immediate that all words generated by $S$ has equal number of $0$'s and $2$'s.
* Suppose $1^kw\in L$ for some $w$ that does not start with 1.

+ Suppose $w$ starts with 0. If we count the number of 0s and the number of 2s in $w$ starting from the starting 0, there will be a time that the number of 2s catches up with the number of 0s. So $w=0w\_12w\_2$ for some $w\_1, w\_2\in L$.
    + Suppose $w$ starts with 2. Similarly, $w=2w\_10w\_2$ for some $w\_1, w\_2\in L$.

Combining the above two cases with the base case $1^k$ for $k\ge0$, which can be generated, we see by mathematical induction that all words in $L$ can be generated.

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


# Question
Title: How does dynamic programming work in this example(generating the tables )
> For example, a sequence has the defined growth property: if it is a sequence of positive integers $a\_{1}, a\_{2}, a\_{3}....a\_{n}$ and such that:
>
> 1. $a\_{1}=1.$
> 2. $a\_{n+1} \leq$ Max$\_{1\leq i \leq n}$ ($a\_{i}+1$)
>
> We can quickly compute the number of such sequences of length n with the power of dynamic programing:
>
> Let sequence(l, m) be the number of possible sequences with length l and maximum number in the sequence m. The total number of such sequences for a length can be calculated by summing all the sequences with maximum value ranging from 1 to n for length l. The recurrence can be described as:
>
> sequence(l,m) = sequence(l-1, m-1 ) + m * sequence(l-1,m);
>
> (sequence (l,1)=1, sequence(l,m)=0 if l\< m)
>
> As we create a table of size l * m, where we fill the matrix column by column. The base case: the first column of the table sequence(l, 1) = 1 and for the subproblems where l \< m the number of sequences will be 0 since the maximum element in sequence can't be bigger than the length of sequence. We can now fill the table in the second column and apply the recurrence relation for every cell and obtain the value fro all combinations of l and m. Finally, We can sum up the last row to calculate the number of sequences.

Understand that the text already gives hint for creating the table. but I am still struggling to visualize it. First of all, What exactly is this sequence?

$a\_{2} = a\_{1+1} \leq max\_{1 \leq i \leq 1}(a\_{i}+1) $ which mean i can only be 1. Then $a\_{2} \leq max(2)$

and $a\_{3}\leq max(3)$ but what are some example of such sequence ? Any more guidance for completing the table?

What is exactly m in sequence(l, m)? Where should we place $a\_{4}$ in the table of l * m?

# Answer
> 1 votes
Here are all such sequences of length 1.

```
[1]

```

Here are all such sequences of length 2.

```
[1, 1]
[1, 2]

```

Here are all such sequences of length 3.

```
[1, 1, 1]
[1, 1, 2]

[1, 2, 1]
[1, 2, 2]
[1, 2, 3]

```

Here are all such sequences of length 4.

```
[1, 1, 1, 1]
[1, 1, 1, 2]

[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]

[1, 2, 1, 1]
[1, 2, 1, 2]
[1, 2, 1, 3]

[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]

[1, 2, 3, 1]
[1, 2, 3, 2]
[1, 2, 3, 3]
[1, 2, 3, 4]

```

Please observe how the sequences grow longer and longer with the condition $$a\_{n+1} \leq \max\_{1\le i \le n} (a\_{i}+1) = 1+\max\_{1\le i \le n} a\_{i}$$ as well as the recurrence relation $$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m).$$

---

> $a\_{2} = a\_{1+1} \leq \max\_{1 \leq i \leq 1}(a\_{i}+1) $ which mean i can only be 1. Then $a\_{2} \leq \max(2)$. and $a\_{3}\leq \max(3)$.

Yes, $a\_{2} \leq \max(2)=2$. However, $a\_{3}\leq \max(a\_1+1, a\_2+1)$. If $a\_2=1$, then $a\_3\le \max(1+1, 1+1)=2$. While $a\_3\le \max(3)=3$ is true, it might be relaxed too much.

---

Let us see how we are going to fill the two dimensional array sequence($m$,$l$).

For example, how to use the following relation? $$\text{sequence}(4,4) = \text{sequence}(3, 3 ) + 4 * \text{sequence}(3,4)\\,.$$ We know sequence$(3,3) = 1$ since there is only one sequence of length 3 and maximum number 3, $\[1,2,3\]$ or sequence$(3,3) = 1 + 3 * 0 = 1$. There is no sequence of length of length 3 and maximum number 4, since the maximum number in any sequence of length 3 is at most 3. So $$\text{sequence}(4,4) = 1 + 4 * 0 = 1\\,,$$ which corresponds to the unique sequence of length 4 and maximum number 4, $\[1,2,3,4\]$.

---

> What is exactly $m$ in $\text{sequence}(l, m)$? Where should we place $a\_4$ in the table of $l * m$?

It looks like you need to understand the recurrence relation.

$$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m),$$

where $\text{sequence}(l,m)$, $l\ge2$, $m\ge1$ is the number of sequences whose length is $l$ and whose maximum number is $m$. For example, a sequence $(a\_1, a\_2,a\_3,a\_4)$ is a sequence of length 4 and whose maximum number is $\max(a\_1, a\_2,a\_3,a\_4)$. If that maximum number is $k$, it contributes 1 to $\text{sequence}(4, k)$ if it satisfies the two conditions. For example, sequence $(1,2,3,2)$ contributes 1 to $\text{sequence}(4, 3)$ while sequence $(1,1,2,2)$ contributes 1 to $\text{sequence}(4, 2)$.

Let $a\_1, a\_2, \cdots, a\_l$ be such a sequence. Let us consider its first $l-1$ items, $a\_1, a\_2,\cdots, a\_{l-1}$.

* The maximum number of $a\_1, a\_2,\cdots, a\_{l-1}$ is smaller than $m-1$. Then $$a\_{l} = a\_{(l-1)+1}\leq \max\_{1\le i \le l-1} (a\_{i}+1) = 1+\max\_{1\le i \le l-1} a\_{i}\lt m$$, which contradicts that fact that the maximum number of all of them is $m.

So this situation cannot happen.
* The maximum number of $a\_1, a\_2,\cdots, a\_{l-1}$ is $m-1$. Then $a\_l$ must be $m$. Otherwise, the maximum number of the whole sequence will be $m-1$ instead of the required $m$.

So for each sequence counted in $\text{sequence}(l-1, m-1 )$, we have a sequence that should be counted in $\text{sequence}(l, m)$. We have a summand $\text{sequence}(l-1, m-1)$
* The maximum number of $a\_1, a\_2,\cdots, a\_{l-1}$ is $m$. Then $a\_l$ can be anyone of $1, 2, \cdots, m$ $m$. So for each sequence counted in $\text{sequence}(l-1, m)$, we have $m$ sequences that should be counted in $\text{sequence}(l, m)$. That is, we have a summand $ m * \text{sequence}(l-1, m)$.

Combining all three cases above, we obtain that recurrence relation.

---
Tags: dynamic-programming
---


# Question
Title: Density of regular language containing all squares
I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.

Suppose we have a regular language $L \subseteq \\{0,1\\}^\*$ and the language $ \mathbf{S} = \\{uu: u\in \\{0,1\\}^\*\\}$ is a subset of $L$. Clearly for even $n$ there are at least $2^{n/2}$ words of length $n$ in $L$. How would I show that there are at least $a2^n$ length $n$ binary words in $L$, for infinitely many $n$? Where $a$ is some constant that can depend on $L$.

Clearly $\mathbf{S}$ is non-regular, so there must be more length $n$ words accepted, but I am not sure how to get $\Theta(2^n)$ length $n$ words. Somehow one has to use the regularity of $L$, so maybe take its finite automaton, and relate the number of words to states/transitions? I don't see a way to proceed.

# Answer
Suppose that the Myhill–Nerode relation of $L$ has the equivalence classes $C\_1,\ldots,C\_m$. Let $N\_i(n) = |C\_i \cap \\{0,1\\}^n|$. If $x,y \in C\_i \cap \\{0,1\\}^n$ then $x^2,y^2 \in \mathbf{S} \subseteq L$, and so $xy,yx \in L$ since $C\_i$ is an equivalence class. Therefore $$ |L \cap \\{0,1\\}^{2n}| \geq \sum\_{i=1}^m N\_i(n)^2. $$ Since the function $x^2$ is convex, the right-hand side is minimized (under the constraint $\sum\_i N\_i(n) = 2^n$) when all $N\_i(n)$ are equal. Therefore $$ |L \cap \\{0,1\\}^{2n}| \geq m (2^n/m)^2 = \frac{2^{2n}}{m}. $$

---

The same argument works if we replace $\mathbf{S}$ with similar languages. Suppose for example that $L$ contains the language of all palindromes $\mathbf{P}$. If $x,y \in C\_i \cap \\{0,1\\}^n$ then $yy^R \in \mathbf{P} \subseteq L$, and so $xy^R \in L$. Just as before, this shows that $|L \cap \\{0,1\\}^{2n}| \geq 2^{2n}/m$.

Furthermore, for each letter $\sigma \in \\{0,1\\}$, we have $y\sigma y^R \in L$, and so $x\sigma y^R \in L$. Therefore $$ |L \cap \\{0,1\\}^{2n+1}| \geq \sum\_{i=1}^m 2N\_i(n)^2 \geq 2m(2^n/m)^2 = \frac{2^{2n+1}}{m}. $$ In total, we get, for all $n$, $$ |L \cap \\{0,1\\}^n| \geq \frac{2^n}{m}. $$

---

Consider now the language $L\_k$ of all words in which the first $k$ letters are the same as the last $k$ letters, reversed. This language has $m = \Theta(4^k)$ equivalence classes, contains all large enough palindromes, and has density $1/2^k = \Theta(1/\sqrt{m})$. This suggests the following vague question:

> What is the minimal density of a regular language having $m$ equivalence classes and containing all palindromes or all squares?
> 3 votes

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


title: Finding Conflict algorithm doubt

text:
# Question
Title: Finding Conflict algorithm doubt
Let $e\_1,e\_2,\cdots,e\_n$ are some events are given by their starting time and ending time.

I have to find an event that conflict with maximum number of other events.

Conflicts means interval overlaps

The idea is as follows: Sort events according to their starting times and then for each event check whether it conflict with other evenets or not. The first step seems to me doable in $\mathcal{O}(n \log n)$ time, but second step i.e. to find the number of events with which it conflicts is seems to $\mathcal{O}(n)$ Can we do it in $\mathcal{O}(\log n)$ time?

**Question :** Is it possible to do the second step as mentioned above in $\mathcal{O}(\log n)$ time?

# Answer
> 1 votes
Take all $2n$ starting *and* ending times and sort them, then walk through the list in sorted order, increasing a counter at each "starting" time, and decreasing the counter at each "ending" time. On every counter increase, check whether this is the highest the counter has gone so far, and if so update the best-so-far event.

---
Tags: algorithms, optimization
---


title: Dynamic Programming Problem on Tree

text:
# Question
Title: Dynamic Programming Problem on Tree
Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had more than $2$ children. Let $D$ be the number of $u$'s children. You can add $D-2$ node to replace the edge connecting $u$ and its children to form a new tree where $u$ is the root and the leaf nodes are its children. There are many possible ways to create $S$. Find the minimum depth of $S$ where depth is the maximum distance from root to some leaves.

My idea is to use Dynamic Programming approach. Let $dp\[u\]$ be the minimum depth we can make for subtree which $u$ is the root. Let $v$ be the child node of $u$. My approach is to sort $dp\[v\]$ in descending order and then use Dynamic Programming on the sorted list in $O(n^3)$. Similar to the solution of Matrix Chain Multiplication. But this approach is too slow. Is there any greedy solution so that I can calculate $dp\[u\]$ in $O(n)$ or $O(n log n)$?

# Answer
> 1 votes
So the difficulty is to determine $dp\[u\]$, depth of $u$, starting from the list of its sons depths $L\[dp\[v\]\]$.

Once $L\[dp\[v\]\]$ is sorted in a heap, you can recursively and greedily pop the 2 minimum values $i$, $j$ and push $1+max(i, j)$.

For instance, $L\[dp\[v\]\] = \[7,5,5,4,3,2,2\]$:

```
=> [7,5,5,4,3,3]
=> [7,5,5,4,4]
=> [7,5,5,5]
=> [7,6,5]
=> [7,7]

```

$dp\[u\] = 8$

This is actually $O(nlog(n))$ due to the heap sort.

---
Tags: data-structures, trees, dynamic-programming
---


title: Memory Mapping Segment

text:
# Question
Title: Memory Mapping Segment
I read that "Memory Mapping Segment"/"memory mapped file" is a segment of the virtual memory of a process, where a file or file-like Ressource is loaded into. It is for high performance file I/O.

I wonder..

(1) Is this normally done automatically by the OS?

(2) What are reasons to do this other than loading shared libraries? I can imagine that bigger files quickly blast the address space..

(3) if this isn't done, then where is the file read from. Does the process have to contact the hard drive to get the information from the library if it is not a "memory mapped file"

# Answer
> 1 votes
1) Yes, for OSes that support memory-mapped files. The OS simply allocates a region of the virtual address space for the file, and sets up its paging algorithms so that,

* when a page is accessed but is not in RAM, it is loaded in RAM
* when there's little RAM left, some memory-mapped pages can be saved to disk and freed (they can be reloaded later on, if needed, from disk)

This is very similar to what happens with swapping.

2) On 64 bit systems, I'd say that virtual address space is a non-issue. Even with files as ridiculously large as 1PB=1024TB each, you'd have to map 16000+ of them to exhaust the space. Even if some address space is reserved by the OS, this limitation is irrelevant until we can store petabytes very easily.

On 32-bit systems, yes, that can be an issue.

For a possible reason: read-only memory-mapped segments are cheap. The OS can unload their pages when memory becomes too tight, without accessing the disk. If the process used regular memory the access would be less efficient, unless the process implements some memory-management itself. The process is simpler to design since it can exploit the OS for making access efficient, and pretend a large file was fully loaded in RAM, roughly.

Read-write memory-mapped segments are less useful, in my opinion, but those are also simple to use by the process.

3) the file is read from (and written to, if the mapped segment isn't read-only) disk. But this is done by the OS, in its paging routines, not by the process.

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


# Question
Title: Decidability of language of TMs which accept only their Gödel number
I am trying to prove that $L = \\{\langle M \rangle \mid L(M) = \\{\langle M \rangle \\}\\}$ is undecidable, where $\langle M \rangle$ is the code of the TM $M$, and $L(M)$ the language recognized by $M$.

I think I can't use Rice's theorem, so I tried to find a reduction. The halting problem for example does not help me in this case. Do you have any idea how to prove it?

# Answer
The recursion theorem states that if $A(x,y)$ is a two-input Turing machine then there is a Turing machine $M$ such that $M(x) = A(x,\langle M \rangle)$. Moreover, $M$ can be constructed from $A$ effectively (i.e., using an algorithm). Using this, we can reduce the halting problem to your problem. Given a Turing machine $B$ and an input $z$, construct a new Turing machine $A(x,y)$ which acts as follows:

* If $x = y$ then simulate $B$ on $z$.
* Otherwise, enter an infinite loop.

Use the recursion theorem to construct a new machine $M$ that on input $x$ acts as follows:

* If $x = \langle M \rangle$ then simulate $B$ on $z$.
* Otherwise, enter an infinite loop.

Then $M \in L$ iff $B$ accepts $z$.
> 0 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: Allowing an empty (epsilon) transition in a PDA
I'm trying to allow an empty transition in a PDA for the following language:

* Alphabet: $Σ = \\{a, b, c\\}$
* Language: $L = \\{ a^ib^j \mid i \neq j \\} \cdot \\{ c \\}^\ast$

Examples of words in $L$:

* $\varepsilon$
* $aabccc$
* $abbccc$

Not in $L$:

* $abcc$
* $aabbc$

Here is what I came up with:

The diagram above uses JFLAP - where the symbol $Z$ reflects the empty stack. The symbol $λ$ is the empty symbol $ϵ$.

It accepts everything as it should, but I don't know how to let epsilon get through. `q7` to `q8` is when there is more `b` than `a`. So there should be a way to allow `q7` to `q9` where `a` is more than `b` but also epsilon can get through. Thoughts? I would like to simply set epsilon through but than `aabbc` can get through easily enough.

# Answer
> 2 votes
Some key points:

* The only case where you want to accept $\epsilon$ is when you haven't had any other input and your stack is empty. Therefore you need an accepting state right at the beginning.
* You need to take into consideration inputs such as: $bac, aac,...$ that will never result in an accepting state, or $abbb$ that results in an accepting state without containing any $c$'s
* If you get a $b$ and your stack is empty you have more $b$'s than $a$'s so you need an accepting state
* If you get a $c$ and and your stack is not empty you have more $a$'s than $b$'s so you need an accepting state
* You reject everything else.

---
Tags: formal-languages, pushdown-automata
---


# Question
Title: Approach to find minimum set in one table consisting of all items in second table
wondering if you can help me with the following problem.

I have one table consisting of items in each person's bag:

```
name  |  item1  |  item2  |  item3
____________________________________
jack  | pen     | pencil  | eraser
____________________________________
jane  | phone   | pen     | camera
____________________________________
leia  | pencil  | eraser  | glasses

```

I have another list with all items that can be in a bag:

* pen
* pencil
* eraser
* phone
* camera
* glasses

What is the best approach to find the minimum list of names who have all the items in the list? For example, in this toy example, the output would be {jane,leia}.

Your help is much appreciated. Please also let me know if I should formulate the problem differently.

# Answer
This is essentially the Set Cover problem, which is NP-hard, so you should not expect an algorithm that is always both exact **and** efficient (polynomial-time).

If you really need the minimum set, you have to resort to algorithms that sooner or later have to explore an exponentially large solution space. You might want to cast your problem as an Integer Linear Program (ILP) and use an ILP solver, or cast it as a Satisfiability (SAT) problem and use a SAT solver. If you want to implement the algorithm yourself from scratch, I suggest you have a look into branch and bound methods.

If you don't really need the minimum cardinality set, you can just greedily pick a name that covers as many as possible uncovered items, mark them covered, and repeat, until all items are covered. This won't do too bad, in a specific theoretical sense, although in practice it may be a relatively low quality solution.
> 2 votes

---
Tags: algorithms, graphs
---


title: Genetic algorithm problem

text:
# Question
Title: Genetic algorithm problem
This is a problem I found in an old exam in my school. I have to solve this Genetic Algorithm problem:
N students $x\_{1},..,x\_{N}$ have answered a quiz of 10 questions (True or False questions) and have obtained scors $s\_{1},..,s\_{N}$ (score can go from 0 to 10).
From these scores we would likw to deduce what are the correct answers to each question.
I don't know where to start. For my population it is obvious that it is the set of list of 10 booleans.
But for my fitness I don't what to choose since we don't have a rule to calculate score and we don't have the target (correct answers: we are trying to find)

Do you guys have any idea on how to solve this?

# Answer
There are only $2^{10} = 1024$ possibilities for the list of correct answers, so try all of them and see which one gives the correct scores.

If the number of questions is larger: Use integer linear programming; the problem can be straightforwardly expressed using integer linear constraints, and then can be solved with an ILP solver. I expect this will be more effective than using genetic algorithms.
> 0 votes

---
Tags: algorithms, genetic-algorithms
---


# Question
Title: Why we treat sentence letter $Q$ as conclusion in one form and premise in other?
Sorry for asking such a dumb question.

I am CS student and I am trying to understand the basic tenets of Logic. I am new to the subject and I am lost understanding Implication.

In formal logic, $(P\rightarrow Q)$, The sentence letter $P$ is premise and $Q$ is conclusion, right?

Now, we know that $(P\rightarrow Q)$ is equivalent to $-(P\wedge -Q)$ i.e. It is not the case that $P$ and not $Q$. Here, $Q$ acts as premise, right?

So, why we treat sentence letter $Q$ as conclusion in form and premise in other?

# Answer
> 3 votes
I completely agree with others that the terms "premise" and "conclusion" don't apply to things that aren't implications. By analogy, in $P\land Q$, $P$ and $Q$ are called "conjuncts", but it would make no sense to ask what the conjuncts of $P\to Q$ are.

However, there is terminology that could make sense of the connection that is more commonly used in type theory than logic but is just as applicable to logic. We can talk about "positive" and "negative" positions. In $P\to Q$, the premise, $P$, is in negative position and the conclusion is in positive position. These senses "multiply" in that in $(R\to S)\to Q$, $S$ is in negative position, but $R$ is in positive position (because it's in a negative position within a formula that is itself in negative position). Since $\neg P\equiv (P\to \bot)$, ($\bot$ is the always false formula) negation effectively swaps negative and positive. In $P\land Q$ and $P\lor Q$, both positions are positive. (The general intuition is that propositions in positive positions are possibly asserted, while propositions in negative position are possibly being assumed. They might not *actually* be asserted/assumed, e.g. in $P\lor Q$.)

This positive/negative notion can be a quick sanity check for equivalences and can help guide proof search. (Negative propositions will likely need to be assumed at some point and positive ones proven. Also, particularly for purely logical theorems, you are often trying to bring negative and positive occurrences together, e.g. as in $P\to P$.) For your equivalence $$P\to Q \equiv \neg (P\land\neg Q)$$ we can see on the right-hand side that $P$ occurs in a positive position within a formula in negative position and so is negative, while $Q$ occurs in negative position within a formula in negative position and so is positive. This matches the left hand side.

# Answer
> 0 votes
No, it's not correct to call $Q$ as the premise of $\neg(P \land \neg Q)$. You can only talk about the premise of a formula if it is of the form $\text{something} \to \text{something}$, i.e., if it is an implication. If it doesn't have that form, then it doesn't have a premise.

---
Tags: logic, propositional-logic
---


# Question
Title: How to formally prove that if triangle inequality is satisfied in a bunch of edges, then each edge has a positive value?
The exact questions states the following:

> Suppose that a complete undirected graph $G = (V,E)$ with at least 3 vertices has cost function $c$ that satisfies the triangle inequality. Prove that $c(u,v) \geq 0$ for all $u,v \in V$.

I can intuitively see that $c(u,v)$ is always positive but I don't understand how to present it in a formal proof. From how I see this, for triangle inequality to hold true, $a+b\geq c$, $b+c\geq a$ and $a+c\geq b$. From the above, we can obtain that $a+b\geq a-b$, $b+c\geq b-c$, etc. Since, sum is larger than the difference, it seems to be intuitive that all numbers positive.

I found out how to prove that each edge has positive weight. Now the issue is that there could be an edge that is not part of a triangle. Then how to prove that it is also positive? I guess we have to assume the graph to be complete. Otherwise I don't have any idea on how to solve it.

# Answer
> 4 votes
Let us first go into the proof. Let us then review any further considerations as you do (ie., whether the graph should be complete or not).

**Lemma** Given an undirected graph $G=(V,E), |V|\geq 3$, and a cost function $c$ defined over $E$, if the triangle inequality is satisfied, then $c(u,v)\geq 0, \forall \langle u,v\rangle \in E$.

Note that the lemma does not require the graph to be complete ---a graph is *complete* if there is an edge for every pair of vertices, i.e., $\langle u, v\rangle\in E, \forall u, v\in V$.

To prove the statement above take any three vertices $u, v, w\in V$ which are related to each other, i.e., that form a triangle. Let $\alpha=c(u,v), \beta=c(v,w), \gamma=c(u,w)$. Let us assume further without loss of generality that these edge costs are sorted in increasing order of cost: $\alpha\leq\beta\leq\gamma$ ---and this order necessarily exists as discrete optimization problems are usually defined over *total orders*.

Now, let us proof by contradiction the lemma. There are three different cases (all somehow related to each other, if you manage to understand the first, the others are rather equivalent but I wrote them down here for your convenience).

**Case 1** (*only one negative edge cost*)

Assume that $\alpha\<0$. Because triangle inequality is assumed by hypothesis then: $\alpha+\beta\geq\gamma$. To make signs apparent, take absolute values: $|\beta|-|\alpha|\geq |\gamma|$, where I considered $\beta, \gamma\geq 0$. Obviously, $|\gamma|\geq |\gamma| - |\alpha|$ and this is true for all plausible values of $\gamma$ (also negative ones). Thus:

$ |\beta|-|\alpha|\geq |\gamma|\geq |\gamma| - |\alpha| $

leading to $\beta\geq\gamma$ which contradicts our first assumption ($\beta\leq\gamma$).

However, devil's in the details so let us consider the frontier case where $\beta=\gamma$. In this case, take now the other relationship that results from triangle inequality: $\alpha+\gamma\geq\beta$. Since $\beta=\gamma$, the preceding relationship simplifies to $\alpha\geq 0$ which, again, contradicts our second assumption, $\alpha\<0$. Hence, $\alpha\geq 0$.

It is straightforward to prove that the same reasoning applies in case $\beta\<0$ or, equivalently, that $\gamma\<0$. Note, however, that from the order we assumed over these costs, $\beta\<0$ implies that there are two edge costs which are negative, and that $\gamma\<0$ implies that all of them are negative. These cases are examined next.

**Case 2** (*two negative edge costs*)

Still, there is a caveat in the preceding reasoning. When taking absolute values to make the signs apparent, I considered $\beta, \gamma\geq 0$. You might think that the lemma might not hold in case that two edge costs are negative. Let us assume that both $\alpha, \beta\<0$, then as triangle inequality is assumed $\alpha+\beta\geq\gamma$ and again, after taking absolute values the following results: $-|\alpha|-|\beta|\geq|\gamma|$, which is clearly impossible, as the left hand is a negative number and the right hand is a positive number.

And this completes the proof for the second case. If you are thinking of trying the same proof for $\beta, \gamma\<0$ or $\alpha,\gamma\<0$, note that all edge costs would be necessarily negative as they are sorted in increasing order of cost. This observation leads us to the third case.

**Case 3** (*all edge costs are negative*)

To conclude, what if all edge costs are negative, $\alpha, \beta, \gamma\<0$? Oh, well, then it just suffices to combine two expressions resulting from triangle inequality: $\alpha+\beta\geq\gamma$ and, since all of these are negative numbers, then $-|\alpha|-|\beta|\geq -|\gamma|$, but also $\alpha+\gamma\geq\beta$ and, again, because these are all negative numbers then $-|\alpha|-|\gamma|\geq-|\beta|$. Now, the observation is that the first inequality shall hold for values larger or equal than $-|\beta|$ and hence: $-|\alpha|-(-|\alpha|-|\gamma|)\geq -|\gamma|$ which leads to $|\gamma|\geq -|\gamma|$, which is only possible if $\gamma=0$ but this contradicts our assumption that $\gamma\<0$ and hence the third case is proven as well by contradiction.

*Note to the third case* \- in case you have difficulty to follow how the last inequality is hold, transform all $\geq$ to $\leq$ by multiplying all inequalities by $-1$. Now, only with positive numbers it might be easier to follow the reasoning.

**Observations**

Nowhere in the preceding proof I assumed the graph to be complete and, indeed, there might well be a pair of vertices $u,v\in V$ which are not directly related to each other through an edge. What we actually did is to prove that every three vertices connected to each other shall be non-negative given that triangle inequality is verified. This does not prevent some edge costs to be negative. It just suffices that the vertex connected to an edge with a negative cost is not connected to any other vertex. This is true because if the degree of a vertex equals 1 then triangle inequality can not be verified.

Equivalently, if the degree of each vertex is larger or equal than two, triangle inequality can be always verified and, in case it holds, then all edge costs are necessarily non-negative.

Hope this helps,

# Answer
> 1 votes
There is a much simpler proof.

Say $\\{a,b,c\\}$ are the weights of edges forming a triangle, with $a\<0$ and $b \leq c$. Then $a+b\<b \leq c$, so triangle inequality does not hold. Your question is the contrapositive of this.

---
Tags: graphs
---


# Question
Title: Polylogarithm growth rate proof using Polynomial growth equation
In the CLRS, there's this part, where it's shown that $$\lim\_{n\to\infty}\frac{(n^b)}{(a^n)} = 0$$ In the same chapter, it uses the aforementioned equation to prove that any polylogarithm function grows slower than any polynomial one, thus, $$\lim\_{n\to\infty}\frac{\log b^n}{ n^a}$$ It does that by substituting `lgn` for `n` and `2^a` for `a` in the first equation. How is it allowed to substitute the terms and prove the latter equation.

# Answer
Here is the starting point. For all real constants $a$ and $b$ such that $a \> 1$, $$\lim\_{n\to\infty}\frac{n^b}{a^n} = 0\\,.\tag{3.10}$$

Let $c=\log\_2 a$, i.e, $a=2^c$. Since $a\>1$, we have $c\>0$. Equation (3.10) becomes $$\lim\_{n\to\infty}\frac{n^b}{a^n} = \lim\_{n\to\infty}\frac{n^b}{2^{cn}}= 0\\,.\tag{cs.1}$$

Let $m=2^n$, i.e, $n=\log\_2 m$. Then equation (cs.1) becomes $$ \lim\_{n\to\infty}\frac{n^b}{2^{cn}} = \lim\_{m\to\infty}\frac{(\log\_2 m)^b}{2^{c\log\_2 m}} = \lim\_{m\to\infty}\frac{(\log\_2m)^b}{m^{c}}= 0\\,.\tag{cs.2}$$

Note that equation (cs.2) is, after $m$ is renamed to $n$ and $c$ is renamed to $a$, $$\lim\_{n\to\infty}\frac{(\log\_2 n)^b}{ n^a}=\lim\_{n\to\infty}\frac{{\lg}^b n}{ n^a}=0\tag{cs.3}$$ where $a\>0$.

What is done in CLRS is a shortened version of above transformations.

Be careful. $(\log\_2n)^b={\lg}^bn\not=\log\_2n^b=\log\_2(n^b)$, where each of two equalities is just a change of notation. $\log\_2 (b^n)$, which is equal to $n\log\_2 b$, is a linear function of variable $n$ while $(\log\_2 n)^b$ is a polylogarithm function of variable $n$.
> 3 votes

---
Tags: polynomials
---


title: Optimal partitioning of n-tuples

text:
# Question
Title: Optimal partitioning of n-tuples
**Motivation**

Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into solving the problem but I'm still unsatisfied with my solution.

**Problem formulation**

You are given a list of unique sets $X\_1,\dots,X\_n$, each containing four integers. You are also given an integer $k$. The goal is to partition the sets into $k$ groups, so that every group has between $0.8n/k$ and $1.2n/k$ sets, in a way that minimizes the number of different integers in each group. Formally, the goal is to find a function $f:\\{1,\dots,n\\} \to \\{1,\dots,k\\}$ that minimizes

$$\Phi(f) = \sum\_j \left|\bigcup\_{i \in f^{-1}(j)} X\_i\right|.$$

**Example**

If instead of sets of four integers we considered sets of two integers, we could give the following example: for the sets

```
{1, 2}, {2, 3}, {1, 3}, {3, 4}, {4, 5}, {3, 5}

```

the optimal partitioning for $k=2$ would be `{1, 2}, {2, 3}, {1, 3}` and `{3, 4}, {4, 5}, {3, 5}` with unique elements $|\\{1, 2, 3\\}|=3$, $|\\{3, 4, 5\\}|=3$ and $\Phi = 6$.

**My attempts so far**

So far I've attempted to solve this problem by modeling it as a graph partitioning problem and using KaHIP library to do the computation. I thought of two methods of how to model this problem as a graph.

1. Each set is a vertex, and we have an edge between two vertices if they share an integer. The number of shared integers determines the weight of the edge. The graph partitioning tool then directly yields some solution to our problem.
2. Each unique integer that occurs in any set is a vertex, and we put an edge between two integers if they are both contained in the same set. The number of such cases determines the weight of the edge. Having the integers partitioned like this we can assign each set a partition of some of its integers. Resulting partitions can be too large, but that can be resolved by applying the first approach to these now relatively small partitions.

The first model in my case turned out to be very space-consuming. I have approximately 2 millions of these sets and the first model produced over 74M edges. The second approach helps a great deal and yields results of similar quality.

The problem is that neither of these models is the exact model of my original problem. Notably, the number of cut edges will not correspond with the number of duplicated integers across partitions. Can you think of a better graph model or an altogether different approach to this problem that would yield better results?

# Answer
You might start from an initial solution computed using one of your two models, and then apply local search: consider any movement of one set from a group to another, and apply it if it does not violate the group constraints and it improves $\Phi$.

Local search is a common approach in graph partitioning, thus it is probably already a part of what KaHIP is doing, but even if it is, you would now do it with the correct measure, $\Phi$, not its surrogate, so the outcome is likely to be improved.
> 1 votes

---
Tags: graphs, optimization, heuristics, partitions
---


# Question
Title: The Church-Turing Thesis (Hello World tester) contradiction and randomized algorithms
The Church-Turing thesis proves that there is no algorithm (or program) $H$ that says whether a program $P$ written in a language, say $C$, on an input $I$ outputs the sentence `Hello World` or not. This is his proof, visit Hopcraft and etc. `introduction to automata theory languages and computation`, chapter 8.

The proof is by contradiction. Let there is such a program $H$ to do the task. He made several *simple* changes to $H$ and built a program $H\_2$, then showed $H\_2$ doesn't exist.

The program $H$ is as follows:

On input $P$ and $I$, it outputs `yes` or `no` which tells if the output is `Hello World` or not.

He then build program $H\_1$ as follows:

$H\_1$ takes $P$ and $I$ and runs $H$ on $P$ and $I$, if $H$ prints `yes`, it prints `yes` and if $H$ prints `no`, it prints `Hello World`. The $H\_1$ is as follows

He then built $H\_2$ as follows:

1. $H\_2$ reads the $P$ and store in an array $A$.
2. $H\_2$ simulates the $H\_1$, but whenever $H\_1$ would read an input, $H\_2$ reads from stored copy in $A$.

Hence $H\_2$ prints `yes` if $P$ prints `Hello World` when given itself as input and `Hello world` if doesn't print `Hello World`.

The contradiction occurs when when the $P$ is actually program $H\_2$, the source code of $H\_2$ is provided as input to itself. If the $H\_2$ prints `Yes`, then $H\_2$ in the box saying $H\_2$ on input $H\_2$ prints `Hello World`  and the `Hello World` is the output of `no` in $H$.

> The basis of contradiction is, $H\_2$ on input source code of $H\_2$ printed `no` while we assumed it is `yes` and **a program on the same input can't have different outputs.**

If $H$ were a program with randomized algorithm, then on the same input it would have different outputs. The basis of the contradiction is if $H\_2$ on input $H\_2$ prints something, it can't print something else on $H\_2$ again. But if $H$ contains some random process inside it, then on the same input it would print different things and it is not a contradiction at all.

Please explain where I am wring about this.

Thanks in advance.

# Answer
> The Church-Turing thesis proves that there is no algorithm (or program) that says whether a program written in a language, say , on an input outputs the sentence Hello World or not. This is his proof, visit Hopcraft and etc.

The Church-Turing thesis is introduced in the book as "the unprovable assumption that any general way to compute will allow us to compute only the partial-recursive functions (or equivalently, what Turing machines or modern-day computers can compute)". It has little to do with undecidability directly. I will treat "The Church-Turing thesis proves that" as a typo that should not exist.

---

> Please explain where I am wrong about this.

In fact, you are not necessarily wrong at all. It is just that your argument does not lead us anywhere.

What have been proved in the book is that there is no **non-randomized** algorithm that can decide whether a **non-randomized** program on an input outputs "Hello World" or not. No, there is no such adjective "non-randomized" in the original statement in the book. However, it does not matter much whether we add it or not. Why?

Because a randomized algorithm cannot decide anyway. It can only say something like the probability a given program on some given input outputs "Hello world" is less than 23 percent. I will not call that probabilistic prediction a decision. You have not found anything valuable or interesting by considering randomized algorithms. All you have observed is that the proof does not apply to randomized algorithms, which we do not have to consider in the first place anyway.

---

We might be thinking, wait, there is some information if we can be certain the probability a given program on some given input outputs "Hello world" is less than 23 percent. That could be mean that the undecidability only holds in some relative sense.

However, the conclusion is still something along the line that there is no algorithm, whether randomized or not, can always provide non-zero information regarding whether a deterministic program on a input outputs "Hello world" or not. You can read the question can a probabilistic Turing machine solve the halting problem? and its answers for more explanations.
> 1 votes

---
Tags: complexity-theory, church-turing-thesis
---


# Question
Title: Subset on boolean cube with largest sum of biases
On the boolean cube $\mathcal{B}=\\{0,1\\}^n$, we assign each vertex a value by $p:\mathcal{B}\rightarrow\[0,1\]$. Let $$\tilde{p}\_i=\sum\_{x\in\mathcal{B}}(-1)^{x\_i}p(x).$$ What is the value of $\max\_p\sum\_{i=1}^n|\tilde{p}\_i|$?

---

Since the objective $\sum\_{i=1}^n|\tilde{p}\_i|$ is convex on $p$, we can safely assume that $p(x)$ is either $0$ or $1$. So $p$ represents a subset of $\mathcal{B}$, and $|\tilde{p}\_i|$ indicates the 'bias' of this subset on the direction of $x\_i$. That's where the title comes from, but you can also think of it as bounding the L1 sum of some specific Fourier coefficients.

I tried to solve it combinatorially: let $f(n,k)$ denote the maximum value when $p$ represents a subset of size $k$. By considering the size of the intersection with $\\{x\in\mathcal{B}\mid x\_n=0\\}$, we have the following recursive relation: $$f(n,k)=\max\_{0\leq\ell\leq k} f(n-1,\ell)+f(n-1,k-\ell)+|k-2\ell|,$$ for all $0\leq k\leq 2^{n-1}$. And clearly $f(n,2^n-k)=f(n,k)$. I ran a program to compute the first several terms of $\max\_k f(n,k)$, which is always $f(n,2^{n-1})$: $$1,2,6,12,30,60,140,280,630,\cdots$$ It seems to be $n\cdot\binom{n-1}{\lfloor n/2\rfloor}$, and this value can indeed by achieved when the subset consists of those $x$ with Hamming weight at most $\lfloor n/2\rfloor$.

It would be great to have a formal proof of this observation. A direct proof via the properties of Fourier coefficients on the boolean cube would be even better. Thanks in advance.

# Answer
> 1 votes
It will be slightly cleaner to replace $\\{0,1\\}^n$ with $\\{-1,1\\}^n$, and to normalize your function $\tilde{p}\_i$ so that we get the $i$'th Fourier coefficient $$ \hat{p}(\\{i\\}) = \mathbb{E}\[x\_i p\]. $$ Let $\sigma\_1,\ldots,\sigma\_n \in \\{ \pm 1 \\}$. Then $$ \sum\_{i=1}^n \sigma\_i \hat{p}(\\{i\\}) = \mathbb{E}\left\[\left(\sum\_{i=1}^n \sigma\_i x\_i\right)p\right\]. $$ If we define a function $$ q(x\_1,\ldots,x\_n) = p(\sigma\_1 x\_1, \ldots, \sigma\_n x\_n) $$ then $q \in \[0,1\]$ and $$ \sum\_{i=1}^n \sigma\_i \hat{p}(\\{i\\}) = \mathbb{E}\left\[\left(\sum\_{i=1}^n x\_i\right) q\right\]. $$ Under the constraint $q \in \[0,1\]$, the right-hand side is clearly maximized when $$ q = \begin{cases} 1 & \text{if } \sum\_i x\_i \> 0, \\ 0 & \text{if } \sum\_i x\_i \< 0, \\ \ast & \text{if } \sum\_i x\_i = 0, \end{cases} $$ where $\ast$ means that the value doesn't matter. In other words, $q$ is the majority function, and so $$ \begin{align} \sum\_{i=1}^n \sigma\_i \hat{p}(\\{i\\}) &\leq 2^{-n} \sum\_{k \geq n/2} (k-(n-k)) \binom{n}{k} \\ &= 2^{-n} n \sum\_{k \geq n/2} \binom{n-1}{k-1} - 2^{-n} n \sum\_{k \geq n/2} \binom{n-1}{k} \\ &= 2^{-n} n \binom{n-1}{ \lceil n/2 \rceil - 1 } \\ &= 2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }. \end{align} $$ Therefore $$ \sum\_{i=1}^n |\hat{p}(\\{i\\})| \leq \max\_\sigma \sum\_{i=1}^n \sigma\_i \hat{p}(\\{i\\}) \leq 2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }. $$ Furthermore, this is achieved for the majority function.

---
Tags: combinatorics
---


# Question
Title: Difference between methods of converting from finite state machine to regular expression
I have a question about method that I saw on internet and method that my professor showed me. I have this finite state machine:

```
q1(a)=q1
q1(b)=q2
q2(a)=q2
q2(b)=q3
qf3(a)=qf3
qf3(b)=qf3

```

My professor using a method

```
r(p,q,k+1)=r(p,q,k)|r(p,k+1,k)r(k+1,k+1,k)*r(k+1,q,k)

```

and he start from (1,3,3). He get `r(1,3,3)=a*ba*b|(a|b)*`, I understand that method but if a finite state machine is more complicated then it takes to much time, so I saw on internet and I saw here a method where I start like this

```
q1=epsilon+q1a, q1=a*
q2=q1b+q2a, q2=a*ba*
q3=q2b+q3a+q3b, q3=a*ba*b(a+b)*,q3=a*ba*b(a|b)*

```

Both regular expression look similar but I do not know is that the same? Can you tell me where is difference if difference exist?

# Answer
There is a reference question on methods to convert a finite automaton into a regular expression. Personally I am very fond of the "State removal method" which is equivalent to the "Transitive closure method" you seem to be using. The reason is that the administration you do in the state removal seems to be less, and is more easily kept as labels to edges, rather than keeping track of many $R\[i,j,k\]$ sets.

Nevertheless, basically all methods use the same recursion, and one gets equivalent results. I say equivalent here, because there is no way to uniquely denote regular languages. Even when using the same method, when applying the reductions in a different order one gets a different result. But again, this is always the same language, only written in a different way.
> 1 votes

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


# Question
Title: operate infinite times over a regular language
Let $T:Σ^\*\to Σ^\*$ be an operation such that $T(L)$ is regular for all regular languages $L \in Σ^\*$.

Is it possible to prove $T^∞(L)$ is regular?

$T^∞(L)=\bigcup\_{i=1}^{\infty}{T^{i}\left(L\right)}$

# Answer
> 2 votes
Colleague Apass Jack already warned about the dangers of infinity, and he also indicated a very simple example that shows that a very simple iteration leads to a non-regular language. Case closed, but I like to add an observation: iterating simple local substitutions lead to Turing power, not just non-regularity.

The single steps of a Turing machine van be encoded, and performed with a regular operation. The instruction "on reading $a$ in state $q$, write $b$, move left and change to state $p$" is coded as rule $aq \mapsto pb$ and is extended to longer strings containing a single state as $\alpha aq \beta \mapsto \alpha pb\beta $. This operation can be extended to sets of instructions, and will map a regular language into a regular language. However,iterating them will actually generated Turing machine computations!

(I have an answer somewhere with this observation, but cannot find it.)

---
Tags: formal-languages, regular-languages, closure-properties
---


title: Unbiased random number generator

text:
# Question
Title: Unbiased random number generator
we have a six-sided dice numbered from 1 to 6, and each has the probability $p =\frac{1}{6}$. My task is to create a unbiased method to generate a random number from 1 to 10 using the given dice. I am aware that the method should maps the following set $$ \\{1,\dots 6\\}^k\mapsto \\{1,\dots, 10\\}$$, with $k$ is the number of time we throw the dice. For sure not the 36 elements will be mapped into the set containing 1 to 10. What i mean, the method will use a while loop and only stops if a certain tuple is found. My task then is the find those tuples and prove each thoese 10 tuples has the probaitly of $\frac{1}{10}.$ I think $k$ should be 2 in this case , but then i am not quite sure how to extract the 10 elements from 36 elements ($6^k$,with $k=2$) and have a probability of $p'=\frac{1}{10}$. can we maybe also generalize that for$ n$ elements ?

$$ \\{1,\dots 6\\}^k\mapsto \\{1,\dots, n\\} $$ I will appreciate any good ideas.

# Answer
Here is the algorithm for $n=10$.

1. Throw the dice twice to get $(x,y)$.
2. Compute $r=x + 6(y-1)$. If $r\le10$, return $r$ and stop.
3. If we have reached here, go back to step 1.

Here is the algorithm for general $n$.

1. Compute $n=\lceil \log\_6k\rceil$.
2. Throw the dice $n$ times to get $(x\_1, x\_2, \cdots, x\_n)$.
3. Compute $r=x\_1+6(x\_2-1)+6^2(x\_3-1)+\cdots+6^{n-1}(x\_n-1)$. If $r\le k$, return $r$ and stop.
4. If we have reached here, go back to step 2.

---

There are many variations, of course.

For example, in step 2 for $n=10$, we can return $r=10 - (x + 6(y-1))\\%10$ and stop when $x+6(y-1)\le30$ instead. This will reduce the chance to go to step 2. Here % is the remainder operator.

For example, here is gnasher729's algorithm for $n=10$. Throw a dice until we get a number $x\not=6$. Throw the dice once more to get another number $y$. Return ((x - 1) * 6 + (y - 1))%10+1$.

---

(**Exercise 1.**) (One minute or less) Devise an algorithm for $n=3$.

(**Exercise 2.**) Devise an algorithm for $n=7$. Try making its expected number of rolls as small as possible.

(**Exercise 3.**) Prove that the expected number of rolls in gnasher729's algorithm is the minimum among all algorithms.

(**Exercise 4.**) Given any $n\>1$, devise an algorithm with the least expected number of rolls.
> 4 votes

# Answer
Throw a dice until your number is not a six, giving a number x = one to five. Throw the dice once more, giving a number y = one to six. There are thirty combinations.

Calculate (x - 1) * 6 + (y - 1), take the last digit of the result, then add 1.
> 2 votes

# Answer
If you want unbiased result, then:

1. Throw first dice, this is uniform in {1-6}
2. Throw another one, check parity if it is odd add 6
    * Here it doesn't matter what split you choose, just aim at $\frac{1}{2}$ probability.
3. if result is 11 or 12 discard results and start from 1.

$k$ is 2 here, to get one result, but since this is rejection sampling, at average you need more than one pair. We cannot reuse failed sample, as this introduces bias.

By the way, it is tempting to multiply two results, discard anything that is greater than 27 and divide by 3 discarding reminder, but it is cutted $2\sigma$ Gaussian distribution, not uniform.

Solution for 1-10 is hand tailored, but with general procedure you could generalise to 1 to N uniform random distribution with M-sided dice or use bits of entropy extraction to produce bit sequences.
> 1 votes

# Answer
This is not an answer but a global analysis.

I see 3 answers here which are exactly the same. In any you may have to re-roll infinitly dices. The question is why ?

Just build the prime factorization of:

* you want 10 = 5 x 2
* you have 6 = 3 x 2

A dice cannot create a random (with homogeneous probability) choice which is not one of its prime component. Thus build the 2 is easy but the 5 is basically impossible. You have to cancel (re-roll) some values to change the nature of your dice. Here, one side of a dice is re-rolled to build a 5-sided dice.

You can apply this analysis to any values for this problem.
> 1 votes

# Answer
Here's a general solution: Assume you have an unbiased dice with D faces, numbered 0 to D-1 (for example D = 6). Assume you want to find one of N numbers, 0 to N-1.

Start with s = 0, S = 1. s is the current state, S is the number of possible states. We will always have 0 ≤ s \< S.

Throw the dice, throwing a number d, 0 ≤ d ≤ D-1. Replace s with s*D + d, and S with S*D. Calculate m = S % N. If s \< S - m then finish with the number s % N (the number of possible values s \< S - m is a multiple of N). Otherwise, replace s with s - (S - m), replace S with S - (S - m), and throw the dice again.
> 0 votes

---
Tags: random-number-generator
---


# Question
Title: Is it still transfer learning if you consider input as well as output? (neural networks)
I'm new to the CS stack exchange, so a fond hello to you all!

I joined since I have a question I've been curious about. I have recently been running some experiments in transfer learning - specifically I train a network to recognise a certain image, let's say a cat, and then I transfer the input and hidden layers of the network to another dataset and see if the trained weight distribution is a better starting point as opposed to a random distribution through XAVIER etc. etc.

I now wonder, what if the input is different, rather than the output? For example, if I have a dataset of Hotel reviews and build a sentiment analysis type predictor that would predict whether a review is negative or positive, one would have a binary classification problem. If you were then to apply those layers and weights as the starting point to Restaurant reviews, one has changed the input attributes (eg. word stems from a different domain) but the output may still be a binary classification problem for positive and negative classes.

All of the examples of transfer learning I see will change the input and output layers while retaining the hidden layers. If the input changes, but the output does not, is it still Transfer Learning?

Thank you!

# Answer
> 1 votes
This type of transfer learning only applies if you have the same features. If you don't, you'll either have to do something else, or find some way to first extract a common set of features from both, or choose a feature set that is the union of the two features. The latter choice would handle the example you gave of hotel reviews vs restaurant reviews.

That said, there is emerging evidence that for deep neural networks, it's not clear that transfer learning (pre-training on a different task) provides any advantage in aaccuracy over training from scratch on the second task. Recent research has shown that if you train long enough on the second task, you get accuracy as good as if you start with weights from a network that was pre-trained on the second task. So, it appears the main advantage of this kind of transfer learning might be to speed up training time, rather than to build better models.

---
Tags: machine-learning, neural-networks
---


# Question
Title: How to test for overflow when multiplying floats
I am trying to implement a 3-term recurrence relation: $$ p\_{n+1} = ap\_n + bp\_{n-1} $$ This can be implemented as

```
  p0 = P0 // starting value p_0
  p1 = P1 // starting value p_1
  loop n = 2,...,N
    pn = a*p1 + b*p0
    p0 = p1
    p1 = pn

```

Depending on $(a,b)$ and also the stopping point $N$, this can sometimes overflow, and I would like to detect such a failure. I believe it is bad form to simply let the loop run to completion and then use something like `isfinite` to check the final value.

A more elegant method would be to somehow test whether the term `a*p1 + b*p0` will exceed the floating point maximum (`DBL_MAX = 1.7976931348623157e+308`) prior to computing it. I could not find much information about this online, so does anyone have suggestions?

One idea I had, was suppose we are just dealing with the first term $a p\_n$. Then we could test: $$ \log{|a p\_n|} \> \log{\textrm{DBL\_MAX}} $$ or $$ \log{|a|} + \log{|p\_n}| \> \log{\text{DBL\_MAX}} $$ It seems that this test would work even if $a p\_n$ is not representable as a floating point number. I'm not sure how to extend this test to the general case $a p\_n + b p\_{n-1}$, or even if this test will account for all possible failure cases in double precision.

# Answer
> 1 votes
I want to further emphasize and underscore gnasher729's comment which is completely correct. `NaN` and `Infinity` were added exactly so you *wouldn't* need to do such checks all the time. That is, they were added to you wouldn't need to do exactly the thing you are suggesting doing. One of the consequences is that it often *is* the right thing to do to just blindly continue a calculation, checking whether it has overflowed or produced `NaN` only when you need to make a decision based on the result.

There are at least a few reasons it is this way. First, as you are starting to see, it can complicate your code quite a bit to attempt to preemptively detect potential errors. Second, such checking code tends to significantly slow down computation1. This is especially bad as the vast majority of the time you will not overflow, and so these checks are just wastes of time. Adding early abort code is then optimizing for a very rare case at the significant expense of the vastly more common case. Third, many aspects of IEEE754 have been carefully designed to behave sensibly even in "error" cases. Often this allows correct results *despite* overflows in intermediate calculations and allows even more error checking code to be eliminated as well as expanding the domain of operations. For example, dividing a finite number by `Infinity` doesn't cause an error but instead produces a (signed) `0`, which is likely the desired result.

So, to reiterate gnasher729's comment, the way you test for overflow when multiplying IEEE754 floating point numbers is by multiplying them and then checking whether they've overflowed. And you shouldn't even do that that often. You should only check for overflow when you need to make a code branch based on the decision2, and otherwise you should just let the error values propagate.

1 This especially true for SIMD architectures such as GPUs. GPUs are *much* happier doing the same thing to a bunch of data in parallel than doing different things in data dependent ways.

2 These code branches may be hidden, e.g. while calling a print routine may not require a branch in your code, there is one in the print routine to know whether to display "Infinity" or not. Therefore, you should check for overflow before printing assuming you want a behavior other than printing "Infinity", et cetera.

# Answer
> 0 votes
I found a solution, though I don't know if it is optimal. One could apply the following test:

```
if (fabs(p1) > DBL_MAX / fabs(a) || fabs(p0) > DBL_MAX / fabs(b)) { // overflow }

```

This would catch the error before it actually occurs. Though as gnasher says in his comments, one could do the operation, and then check afterward if the result is inf or nan. I don't know which method is considered better.

One consideration could be checking how long it takes to apply the above test vs calling `isfinite`. I don't know if one method is more optimal than the other.

---
Tags: floating-point, numerical-algorithms, numerical-analysis
---


# Question
Title: Find the Most Frequent Ordered Word Pair In a Document
This is a problem from Skiena's excellent book The Algorithm Design Manual:

> Give an algorithm for finding an ordered word pair(e.g."New York") occurring with the greatest frequency in a given webpage. Which data structure would you use? Optimize both time and space.

We need to look at all the words, so clearly we can't do better than `O(n)` time. One solution I can think of is inserting each ordered pair in a priority queue (`O(n)` time and space), and then returning the top item. However, the official site has a solution which suggests using a Trie. I understand that words may be repeated, or may be prefix/suffix of other words, so a Trie would save space, but can't figure out how to answer the question using it.

Ideas?

# Answer
In an $n-$word text you have exactly $n-1$ ordered word pairs (not distinct of course). If you use a Trie, you don't need to represent all $n-1$ pairs separately. Take for a example the following text:

> A new puppy in New York is happy with it's New York life.

You first start looking at the words in the text as pairs where the first pair is (a,new), the second is (new,puppy), (puppy,in), ... ,(York,life). The resulting trie will look something like this:

In order to find which pair appears the most times you need to count how many times you reach each leaf.
> 2 votes

---
Tags: algorithms, strings, information-retrieval
---


# Question
Title: Evolutionary optimisation algorithm and graph based search
Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms. Both of these methods entail doing a search on a graph of candidate solutions. Do all other evolutionary algorithms too entail - performing search on a graph?

# Answer
> 2 votes
> Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms

These are examples of **meta-heuristics**. Genetic algorithms are a class of Evolutionary algorithms which itself is one of many meta-heuristics.

> Both of these methods entail doing a search on a graph of candidate solutions.

Usually the "graph" is more *conceptual* than *physical*. Meaning that it's not actually represented by a graph data structure living in memory due to the huge search space. These techniques go (or not) from one solution (or a set of solutions) to its "neighbor" using heuristics. For example a solution that has a better fitness value.

> Do all other evolutionary algorithms too entail - performing search on a graph?

**Yes**. Evolutionary algorithms are **search** based, meaning that we go from a **set** of solutions to another based on *fitness* functions. We also include a *mutation* step (and may include crossover).

This search happens on the "conceptual" graph of possible solutions.

It is worth to mention that this class is **global search** based in contrast with **local search** like the Simulated Annealing algorithm.

For more info check out this Wikipedia article on Meta-heuristics.

---
Tags: optimization, evolutionary-computing
---


# Question
Title: What kind of operations can we do with bits?
I wonder if there are more things we can do with bits aside from NOT, AND, OR, XOR operations? I got this question from my teacher and I'm not really sure. How about bit shifting "\>\>"? Could we count this? Thanks for replying.

# Answer
If you think about it, there are $2^4 = 16$ possible ways of combining two bits to give a single-bit ouput (AND, OR, NOR, NAND, XOR, ...). Can you work out what they all are? This is because there are four possible input combinations ($00$, $01$, $10$, $11$) and any subset of those can be mapped to~$1$. But we could combine more than two bits to give a single bit output – can you work out how many operators there are that take $k$ bits as input and output one bit?

And we're not even restricted to one bit of output: in general, we can have any number of bits of input and any number of bits of output. You mentioned shifts, which map $k$ bits to $k$ bits, as an example of this.

Overall, there are infinitely many ways of combining bits.
> 3 votes

# Answer
Classifying the bit operations comes up when investigating special kinds of operations, like reversible bit operations or falsehood free (classical) logical operations.

> Formally, a reversible gate is just a permutation $G : \\{0, 1\\}^k \to \\{0, 1\\}^k$ of the set of $k$-bit strings, for some positive integer $k$. The most famous examples are:
>
> * the 2-bit CNOT (Controlled-NOT) gate, which flips the second bit if and only if the first bit is 1;
> * the 3-bit Toffoli gate, which flips the third bit if and only if the first two bits are both 1;
> * the 3-bit Fredkin gate, which swaps the second and third bits if and only if the first bit is 1

In similar terms, a falsehood free logical operation is just a Boolean function $f : \\{0, 1\\}^k \to \\{0, 1\\}$ with $f(1, \ldots, 1) = 1$. Before starting to omit logical operations, one can try to list as many logical operations as barely reasonable:

> If we limit ourself to constants, unary operations, and binary operations, then we get:
>
> * Constants for truth ($\top$) and falsehood ($\bot$)
> * An unary operation for negation ($\lnot$)
> * Binary operations for: or ($\lor$), and ($\land$), implication ($\to$), minus ($-$), nand ($|$), nor ($\overline{\lor}$), equivalence ($\equiv$), and xor ($\oplus$). The remaining binary operations add nothing new: reverse implication, reverse minus, first, second, not first, not second, true, and false
> 0 votes

---
Tags: bit-manipulation
---


# Question
Title: Greedy Solution for Selecting Prefix Sum
Given $n$ arrays. Each has size of $h$. Let $a\_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a\_{i, j}$, you have to pick $a\_{1, j}, a\_{2, j}, \dots, a\_{i-1, j}$ as well. Each element can only be picked once. Find maximum sum of elements.

My greedy solution is : Let $p\_{i, j}$ be $\sum\_{x=1}^{i} a\_{x, j}$. Sort a list of $\frac{p\_{i, j}}{i}$ for all $i$ and $j$ in descending order. Then iterate through the list and check each value whether we have included the prefix sum of this array into our final answer or not. If no and $h \geq j$, we include it in the final answer, subtract $i$ from $h$, and mark $j$ as included. If yes and $j \>$ the index of the previous one, we do the same thing just the part extended from the previous one.

Is this solution optimal or is there a better solution to this problem?

# Answer
Unfortunately, your greedy algorithm may return elements whose sum is not the maximum. For example, let $n=h=k=2$ and $$\begin{pmatrix} a\_{11} & a\_{12}\\ a\_{21} & a\_{22} \end{pmatrix} = \begin{pmatrix} 3 & 1\\ 2 & 1 \end{pmatrix}.$$ Your algorithm will pick 3 and 1. The optimal elements should be 3 and 2.

The natural approach to this problem is dynamic programming.

Here are the subproblems.

For nonnegative integers $t$ and $j$ such that $0\le j\le n$ and $0\le t \le \min(nh, t)$, find $dp(t,j)$, the maximal sum of $t$ elements from the first $j$ arrays where all elements selected from the same array must be a prefix of that array. The wanted maximum sum is the maximum number of all $dp(t,j)$.

In order to select $t$ elements from the first $j$ arrays, we can select $i$ elements from the $j$-th array and $t-i$ elements from the first $j-1$ arrays for some $i$, $0\le i\le \min(t,h)$. Hence we have the following recurrence relation.

$$ dp(t,j) = \max\_{0\le i\le \min(t,h)}\left(dp(t-i, j-1) + \sum\_{1\le k\le i}a\_{k,j}\right)$$

The base cases and the boundary cases can be figured out easily.
> 2 votes

---
Tags: algorithms, sorting, greedy-algorithms
---


# Question
Title: Using master theorem to solve recurrence with log
I'm not sure how to solve apply the master theorem in order to solve this recurrence:

> $$ T(n) = 4T(n/3) +O(n\log n),\text{ where } T(1) = 1.$$

The master theorem I have been shown is normally used to solve recurrences of the slightly different form $$ T(n) = aT(n/b) +O(n^d),\text{ where }T(1) = 1.$$

# Answer
Clearly $c := \log\_3 4 \> 1$. Choose $1 \< d \< c$ arbitrarily, say $d = \frac{1+c}{2}$. Then $O(n\log n) = O(n^d)$ and $d \< \log\_3 4$, and so we can apply the first case of the master theorem.
> 0 votes

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Prefix/suffix property of language containing only empty word
Does language $L ={\varepsilon}$, where $\varepsilon$ \- empty word has suffix/prefix property?

The definition says that language has prefix/suffix property requires that there is no code word in the system that is a prefix (initial segment) of any other code word in the system.

So if we have this finite language with $\varepsilon$ this mean that, there arent any prefix/suffix of empty word so our language has or not prefix/suffix property?

# Answer
> 1 votes
You probably mean $L=\\{\varepsilon\\}$, i.e. the language which contains only the empty word, as opposed to the empty language. Both the empty language and the language which contains only the empty word have the prefix/suffix property, since they satisfy the definion.

However, the prefix property is a property of a code, not a property of a language. A language can describe a code, but neither the empty language nor the language which contains only the empty word describe a code. So in the end it is irrelevant whether those languages have the prefix/suffix property.

**Edit** rici is right that Hopcroft&Ullman say that the LR(0) grammars define exactly the DCFL's having the prefix property. (They hasten to add that the prefix property is not a severe restriction.) So in this case it is good that the empty language and the language which contains only the empty word have the prefix property. Additionally, Berstel&Perrin allow the empty set as a code, so you can also dispute my other claim. But they agree that $\\{\varepsilon\\}$ has the prefix property, and is not a code:

> **Proposition 2.1.9** *Any prefix (suffix, bifix) set of words $X\neq \\{\varepsilon\\}$ is a code.*

Both Hopcroft&Ullman and Berstel&Perrin consider $\varepsilon$ to be a prefix/suffix of any word, but they require a proper prefix/suffix in the definition of the prefix/suffix property. (This is clearly the right thing to do, otherwise no set of words would have the prefix/suffix property.)

---
Tags: formal-languages, automata, regular-languages, formal-grammars
---


# Question
Title: Maximum Expected Fishing Day (Recurrence Relation)
> John joined a meetup where organize day long fishing trip once a month. The organizers are vary poor at planning, so will organize fishing on a random day of the month without any advance notice. Sadly, John needs to inform his boss in order to get time off from work at least a day in advance. With this situation, John is forced to schedule vacation days and hopping that the fishing will take place on them. At the same time, he can be strategic about it. For instance, he can wait until the end of the month at which point the fishing would have already happened or will guarantee to occur the next day. John can use a total of v day of vacation for the next m months. What is the greatest expected number of fishing meetup that he can arrange to attend? For simplification, we can assume that a month is only 30 days longs.
>
> It can be approached as: Defining the sub-problems as Maximum Expected Fishing Days MEFD: for every situation MEFD(m,d,v), where m is the number of months left including the current month, d is the numbers of days left in the current one, and v is the number of vacation days john left with the assumption that the fishing has not took place in the current month.
>
> Base case: for any (m,d,v) such that i, j or l equals to 0, MEFD(m,d,v) =0
>
> Recurrence Relation: MEFD(m,d,v) = max(MEFD$\_{1}$(m,d,v), MEFD$\_{2}$(m,d,v))
>
> MEFD$\_{1}$(m,d,v)=$\frac{1}{d}$(1+MEFD(m-1,30,v-1))+ $\frac{d-1}{d}$MEFD(m-1,d-1,v),
>
> MEFD$\_{2}$(m,d,v)=$\frac{1}{d}$(1+MEFD(m,30,v-1))+ $\frac{d-1}{d}$MEFD(m,d-1,v).

What does $\frac{1}{d}$ or $\frac{d-1}{d}$ means? Why do we need to multiply them ? Let's MEFD$\_{1}$ means that the Maximum Expected Fishing Day that John takes a vacation day off in the next day. then it would fall into two cases: 1, fishing meetup take place, 2, it didn't take place. As we can tell from MEFD$\_{1}$, 1 + ing means fishing meetup take place, then we - 1 from the months left and - 1 from vacations left.

What do we also need to -1 from months and vacations of the second part of the equation, + $\frac{d-1}{d}$MEFD(m-1,d-1,v)?

Or am i am reading this recurrence relation completely wrong? any points are really appreciated.

# Answer
Although the subproblems are defined correctly in the approach quoted in the question, there are some typos and glitches when it comes to the base cases and recurrence relations.

Please see the corrected base cases and recurrence relations below.

---

Base case: for any $(m,d,v)$ such that $m$, $d$ or $v$ equals to 0, $$\text{MEFD}(m,d,v) =0\tag{R0}$$

Recurrence Relations: $$\begin{align\*} \text{MEFD}(m,d,v) &= \max(\text{MEFD}\_{1}(m,d,v), \text{MEFD}\_{2}(m,d,v))\tag{R1}\\ \text{MEFD}\_{1}(m,d,v)&=\frac{1}{d}(1+\text{MEFD}(m-1,30,v-1))\\\&+\frac{d-1}{d}\text{MEFD}(m,d-1,v-1)\tag{R2}\\ \text{MEFD}\_{2}(m,d,v)&=\frac{1}{d}\text{MEFD}(m-1,30,v))\\\&+\frac{d-1}{d}\text{MEFD}(m,d-1,v)\tag{R3} \end{align\*}$$

Equation (R1) says that the maximum expected fishing days is the larger of the expected fishing days yielded by two strategies, John selects the next day and John does not select the next day. John will proceed with the best strategy in the remaining days.

Equation (R2) compute the maximum expected finishing days when John has selected the next day. The probability that the next day will be a fishing day is $\frac1d$, in which case John will proceed with the best strategy for the remaining $m-1$ months and $v-1$ vacations day. The probability that the next day will not be a fishing day is $\frac{d-1}d$, in which case John will proceed with the best strategy for the remaining $d-1$ day and $v-1$ vacation days.

Equation (R3) compute the maximum expected finishing days when John has decided to work for the next day. The probability that the next day will be a fishing day is $\frac1d$, in which case John will proceed with the best strategy for the remaining $m-1$ months and $v$ vacations day. The probability that the next day will not be a fishing day is $\frac{d-1}d$, in which case John will proceed with the best strategy for the remaining $d-1$ day and $v$ vacation days.

Note "John needs to inform his boss in order to get time off from work at least a day in advance" is interpreted as something like if John wants to take tomorrow off, he can just inform his boss tonight, at which time he must have known whether today is a fishing day. If it is, he will not, of course, select any remaining day in the current month as a vacation day. That is why whenever the next day will be a fishing day, we will only consider the remaining $m-1$ months in the above recurrence relations.
> 2 votes

---
Tags: recurrence-relation, recursion
---


# Question
Title: How does Tarjan's pseudocode work (explained to someone familiar with C or Java)?
# The Short Story

A famous computer scientist, Tarjan, wrote a book years ago. It contains absolutely bizarre pseudocode. Would someone please explain it?

# The Long Story

Tarjan is known for many accomplishments, including the fact that he was the coinventor of splay trees. He published a book, "*Data Structures and Network Algorithms*," during the 1980s.

All of the pseudo-code in Tarjan's book is written in a language of his own devising. The pseudo-code conventions are very regimented. It's almost a true language, and one could imagine writing a compiler for it. Tarjan writes that his language is based upon the following three:

I am hoping that someone familiar with one or two of the above languages, or the work of Tarjan, will be able to answer my question.

An example of a function written in Tarjan's language is shown below:

```
heap function mesh (heap nodes h1, h2);

    if key(h1) > key(h2) → h1 ⟷  h2 fi;

    right (h1) := if right(h1) = null → h2

                  |right(h1) ≠ null → mesh (right(h1), h2) fi;

    if rank (left (h1)) < rank (right (h1)) → left(h1) ⟷ right(h1) fi;

    rank (h1) := rank(right(h1)) + 1;

    return h1,

end mesh;

```

I have seen lots of pseudo-code, but I have never seen anything like Tarjan's. How does Tarjan's pseudocode work? How can examples of Tarjan's pseudocode be re-written as something which looks more like C or Java? It need not even be C or Java. The if-else construct in Tarjan's language is not only different from C-family languages, but also different from Python, MATLAB and many others.

# Answer
> 64 votes
# Table of Contents

I will divide my explanation of Tarjan's pseudocode into the following sections:

1. **Tarjan's If-else Blocks (the `->` & `|` operators)**
2. **Assignment and Equality Tests (`:=` and `=`)**
3. **There is `else if`, but no `else` construct**
4. **Tarjan's Conditional Assignment Operator `:= if`**
5. **Additional Examples of Tarjan's `if` and `:= if`**
5.5. **Tarjan Arrays (or Lists)**
6. **Summary of Operators**
7. **Tarjan's Double-pointed Arrow Operator ()**
8. **Tarjan's do-loops are like C/Java while-loops**
9. **Tarjan's Conditional-assignment operator with all false conditions**

---

# (1) Tarjan's If-else Blocks

# (the operators  and `|` )

The `if-else` construct is perhaps the most fundamental control structure in Tarjan's language.

In Tarjan's pseudo-code, every while-loop and assignment statement has an if-statement or if-else statement built into it.

Tarjan's arrow operator `->` (or →) is a delimiter between the condition of a if-statement and the execution block of an if-statement.

For example, in Tarjan's language we might have:

```
# Example One
 if a = 4 → x := 9 fi

```

If we begin translating the line of Tarjan code above into C or Java, we might obtain the following intermediate result:

```
if (a = 4)
    x := 9
fi

```

Instead of a right curly braces (as in C and Java) Tarjan ends an `if`-block with an ALGOL-like backwards spelling of the key-word: `fi`

If we continue translating our above example, we get:

```
    if (a = 4) {
        x := 9
    }

```

#(2) Assignment and Equality Tests (`:=` and `=`)

Tarjan takes these operators from ALGOL (later also seen in Pascal).

Tarjan uses `=` for equality tests, not assignments (so it works like `==` in the Java programming language).

For assignment, Tarjan uses `:=`, which works like Java `=`.

Thus, if we continue translating our example, we have:

```
if (a == 4) {
    x = 9;
}

```

The if-statement provided above is syntactically correct for C-family languages such as C itself, C++, and Java.

In somthing halfway between English and computer code, we have:

```
if
    the memory address labeled `a` contains the number `4`
then
    store the number `9` in the memory address labeled `x`

```

---

### Else Clauses

A vertical bar (or "pipe" or `|`) in Tarjan's language is equivalent to the `else if` keyword in C or Java.
For example, in Tarjan's language we might have:

```
# Example Two
if a = 4 → x := 9 | a > 4 → y := 11 fi

```

The Tarjan-code above translates to:

```
// This is C-style syntax

if (a == 4) {
    x = 9;
}
else if (a > 4) {
    y = 11;
}

```

---

# (3) `else if` only and no `else` construct

We have gone over the basics of Trajan's `if`-statements without describing the nuances.

We will now discuss a small detail.

The last clause in one of Tarjan's `if-else` blocks must always contain an arrow () operator.

There is no `else` keyword in Tarjan's language; there is only somthing analygous to `else if`.

The closest thing to an `else`-block in Tarjan's language is to make the rightmost test-condition `true`.

```
# Tarjan Syntax

if a = 4 → x := 9 |  a > 4  → y := 11 | true  → z := 99  fi

```

In C/Java, we would have:

```
// C-style or Java-style syntax.

if (a == 4) {
     x = 9;
}
else if (a > 4)  {
    y = 11;
}
else { // else if (true)
    z = 99;
}

```

Examples are easier to understand than general descriptions.

However, now that we have some examples under our belt, know that the general formal of a Tarjan's if-else construct is as follows:

```
    if condition
        → stuff to do
     | condition
        → stuff to do
     [...]
     | condition
        → stuff to do
    fi

```

The character `|` is like `if else`

The character  separates the test-condition from the stuff-to-do.

---

# (4) Tarjan's Conditional Assignment Operator `:= if`

Tarjan's `if` can be used two very different ways. So far, we have only described the C-style use of a Tarjan `if`.

Somewhat confusingly, Tarjan still uses the notation/syntax `if` for assignment statements.

Whether and `if` statement is an assignment-statment or not is dependent upon whether or not the `if` is preceded by an assignment operator.

For example, we might have the following Tarjan code:

```
# Example Three
x := if a = 4 → 9 fi

```

---

### Begin Digression

After working with Tarjan code for awhile, you get used to the order of operations. If we parenthesize test condition in the example above, we obtain:

```
x := (if (a = 4) → 9 fi)

```

`a = 4` is not an assignment operation. `a = 4` is like `a == 4` -- it returns true or false.

### End Digression

---

It can help to think of `:= if` as syntax for a single operator, distinct from `:=` and `if` In fact, we will refer to the `:= if` operator as the "conditional assignment" operator.

For `if` we list `(condition → action)`. For `:= if` we list `(condition → value)` where `value` is teh right-hand-side value we might assign to the left-hand-side `lhs`

```
# Example Four in Tarjan-Code
lhs := if (a = 4) → rhs fi

```

In C or Java, it might look like:

```
# Example Four
if (a == 4) {
    lhs = rhs;
}

```

For reader's whose first language is not English, note that `lhs` is a common abbreviation for `left-hand side` and `rhs` is `right-hand side`.

Consider the following example of "conditional assignment" in Tarjanian code:

```
# The Tarjanian Instantiation of Example Five

x := if a = 4 → 9 |  a > 4  → 11 | true  → 99  fi

```

In C/Java, we would have:

```
    // C/Java Instantiation of Example Five
    if (a == 4) {
        x = 9;
    }
    else if (a > 4)  {
        x = 11;
    }
    else if (true) { // else
        x = 99;
    }

```

---

# (5) Summary of Operators:

So far, we have:

* `:=` ...... Assignment operator (C/Java `=`)
* `=` ...... Equality test (C/Java `==`)
* ...... Delimiter between test-condition of an if-block and the body of an if-block
* `|` ..... C/Java else-if
* `if ... fi` ..... if-else block
* `:= if... fi` ..... Conditional assignment based on an if-else block

#(5.5) Tarjan Lists/Arrays:

Tarjan's Language has built-in array-like containers. The syntax for Tarjan arrays is much more intuitive than the notation for Tarjan `if else` statements.

```
list1  := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3  := ["a", "b", "c", "d"];
list4  := [ ]; # an empty array

```

Tarjan array elements are accessed with parentheses `()`, not square-brackets `[]`

Indexing begins at `1`. Thus,

```
list3  := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true

```

Below shows how to create a new array containing the 1st and 5th elements of `[1, 2, 3, 4, 5, 6, 7]`

```
nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]

```

The equality operator is defined for arrays. The following code prints `true`

```
x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)

```

Tarjan's way to test if an array is empty is to compare it to an empty array

```
arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment

```

One can create a view (not copy) of a sub-array, by providing multiple indices to operator `()` combined with `..`

```
list3  := ["a", "b", "c", "d"]

beg    := list3(.. 2)
# beg == ["a", "b"]
# beg(1) == "a"

end    := list3(3..)
# end == ["c", "d"]
# end(1) == "c"

mid    := list3(2..3)
# mid == ["b", "c"]
# mid(2) == "c"

# `list3(4)` is valid, but `mid(4)` is not

```

#(6) Additional Examples of Tarjan's `if` and `:= if`

The following is another examples of an Tarjan conditional assignment (`:= if`):

```
# Tarjan Example Six
a  := (false --> a | true --> b | false --> c1 + c2 |  (2 + 3 < 99) --> d)

```

`(true --> b)` is the leftmost `(cond --> action)` clause having a true condition. Thus, the original assignment Example Six has the same assignment-behavior as `a := b`

Below is our most complicated example of Tarjan code thus far:

```
# Tarjan Example -- merge two sorted lists

list function merge (list s, t);

return if s =[] --> t
        | t = [ ] --> s
        | s != [ ] and t != [] and s(l) <= t(1) -->
            [s(1)]& merge(s[2..], t)
        | s != [ ]and t != [ ] and s(1) > r(l) -->
            [t(1)] & merge (s,t(2..))
       fi
end merge;

```

The following is a translation of Tarjan's code for merging two sorted lists. The following is not exactly C or Java, but it is much closer to C/Java than the Tarjan version.

```
list merge (list s, list t) {

    if (s is empty) {
        return t;
    }
    else if (t is empty){
        return s;
    }
    else if  (s[1] <= t[1]) {
        return CONCATENATE([s[1]], merge(s[2...], t));
    else  { // else if (s[1] > t[1])
        return CONCATENATE ([t[1]], merge(s,t[2..]);
    }
}

```

Below is yet another example of Tarjan-code and a translation in something similar to C or Java:

```
heap function meld (heap h1, h2);

    return if h1 = null --> h2
            | h2 = null --> h1
            | h1 not null and h2 not null --> mesh (h1, h2)
           fi
end meld;

```

Below is the C/Java translation:

```
HeapNode meld (HeapNode h1, HeapNode h2) {

    if (h1 == null) {
       return h2;
    }
    else if (h2 == null) {
        return h1;
    } else {
        mesh(h1, h2)
    }
} // end function

```

#(7) Tarjan's Double-pointed Arrow Operator (`<-->`)

Below is an example of Tarjan code:

```
x <--> y

```

What Does a Double Arrow () Operator Do in Tarjan's Language?
Well, almost all variables in Tarjan's Language are pointers. `<-->` is a swap operation. The following prints `true`

```
x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true

```

After performing `x <--> y`, `x` points to the object which `y` used to point to and `y` points to the object which `x` used to point to.

Below is a Tarjan statement using the `<-->` operator:

```
x := [1, 2, 3]
y := [4, 5, 6]
x <--> y

```

Below is a translation from the Tarjan code above to alternative pseudocode:

```
Pointer X     = address of array [1, 2, 3];
Pointer Y     = address of array [4, 5, 6];
Pointer X_OLD = address of whatever X points to;
X = address of whatever Y points to;
Y = address of whatever X_OLD points to;

```

Alternatively, we could have:

```
void operator_double_arrow(Array** lhs, Array** rhs) {

    // swap lhs and rhs

    int** old_lhs = 0;
    old_lhs = lhs;
    *lhs = *rhs;
    *rhs = *old_lhs;
    return;
}

int main() {

    Array* lhs = new Array<int>(1, 2, 3);
    Array* rhs = new Array<int>(4, 5, 6);
    operator_double_arrow(&lhs, &rhs);
    delete lhs;
    delete rhs;
    return 0;
}

```

Below is an example of one of Tarjan's functions using the  operator:

```
heap function mesh (heap nodes h1, h2);
    if key(h1) > key(h2) → h1 ⟷  h2 fi;
    right (h1) := if right(h1) = null → h2
                   |right(h1) ≠ null → mesh (right(h1), h2)
                  fi;

    if rank (left (h1)) < rank (right (h1))
        → left(h1) ⟷ right(h1)
    fi;

    rank (h1) := rank(right(h1)) + 1;
    return h1;
end mesh;

```

Below is a translation of Tarjan's `mesh` function into pseudo-code which is not C, but looks more like C (relatively speaking). The purpose of this is to illustrate how Tarjan's  operator works.

```
node pointer function mesh(node pointers h1, h2) {

    if (h1.key) > h2.key) {

         // swap h1 and h2
            node pointer temp;
            temp = h1;
            h1 = h2;
            h2 = temp;
    }

    // Now, h2.key <= h1.key

    if (h1.right == null) {
        h1.right = h2;

    } else // h1.key != null {
        h1.right = mesh(h1.right, h2);
    }

    if (h1.left.rank < h1.right.rank ) {
        // swap h1.left and h1.right

        node pointer temp;
        temp = h1;
        h1 = h2;
        h2 = temp;
    }

    h1.rank = h1.right.rank + 1;
    return h1;
}

```

#(8) Tarjan's do-loops are like C/Java while-loops

Tarjan's language `if` and `for` constructs are familiar for C/Java programmers. However, the Tarjan keyword for a while-loop is `do`. All `do`-loops end with the keyword `od`, which is the backwards spelling of `do`. Below is an example:

```
sum := 0
do  sum < 50 → sum := sum + 1

```

In C-style pseudocode, we have:

```
sum = 0;
while(sum < 50) {
    sum = sum + 1;
}

```

The above is actually not quite right. A Tarjan do-loop is really a C/Java `while(true)` with an if-else block nested inside. A more literal translation of the Tarjan code is as follows:

```
sum = 0;
while(true) {
    if (sum < 50) {
         sum = sum + 1;
         continue;
         // This `continue` statement is questionable
    }
    break;
}

```

Below, we have a more complicated Tarjan `do`-loop:

```
sum := 0
do  sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5

```

C/Java-style pseudocode for the complicated Tarjan `do`-loop is as follows:

```
sum = 0;
while(true) {

    if (sum < 50) {
         sum = sum + 1;
         continue;
    }
    else if (sum < 99) {
         sum = sum + 5;
         continue;
    }
    break;
}

```

# (9) Tarjan's Conditional-assignment operator with all false conditions

Although the lengthy explanation above covers most things, a few matters are still left unresolved. I hope that someone else will someday write a new-improved answer based on mine which answers these quandries.

Notably, when the conditional assignment operator `:= if`  is used, and no condition is true, I am not what value is assigned to the variable.

```
x  := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi

```

I am not sure, but it is possible that no assignment is made to `x`:

```
x = 0;
if (false) {
     x = 1;
}
else if (false) {
     x = 2;
}
else if (99 < 2) {
     x = 3;
}
// At this point (x == 0)

```

You could require that the left-hand-side variable seen in an `:= if`  statement be previously declared. In that case, even if all conditions are false, the variable will still have a value.

Alternatively, perhaps all-false conditions represents a runtime error. Another alternative is to return a special `null` value, and store `null` in the left-hand argument of the assignment.

# Answer
> 8 votes
Never seen this before but I think I can infer what's meant from context.. Presumably the  must be a swap operation, and `if G1 -> S1 | G2 - >S2 | ... fi` is an if/then/else-type construct that also returns a value, like the ternary `?:` operator in C and Java.

With that in hand we could write the above function in a Java-like language like so:

```
HeapNode mesh(HeapNode h1, HeapNode h2)
{
  if(h1.key > h2.key)
  {
    // swap h1 and h2

    HeapNode t = h1;
    h1 = h2;
    h2 = t;
  }

  // One of the two cases has to hold in this case so we won't get to the
  // exception, but it'd be an exception if none of the cases were satisified
  // since this needs to return *something*.

  h1.right = (h1.right == null) ? h2
             : (h1.right != null) ? mesh(h1.right, h2)
             : throw new Exception();

  if(h1.left.rank < h1.right.rank)
  {
    // swap h1.left and h1.right

    HeapNode t = h1.left;
    h1.left = h1.right;
    h1.right = t;
  }

  h1.rank = h1.right.rank + 1;

  return h1;
}

```

---
Tags: programming-languages
---


# Question
Title: Can someone point out why these directed graphs aren't equivalence relations?
As far as I can tell, these two directed graphs are reflexive, symmetric and transitive.

# Answer
In the first one we have c ~ a and a ~ d but not c ~ d, so the relation is not transitive. A similar problem exists for the other graph. See if you can find the issue yourself.

Then ask yourself what the graph of an equivalence relation looks like in general.
> 0 votes

---
Tags: graphs, discrete-mathematics, transitivity
---


# Question
Title: Finding a suitable NP-complete problem for reduction
We are given a set of names and a set of papers with names written on each side of the paper (not necessarily different ones and either side of the paper can be empty). Can we place the sheets on a table such that every name shows up? Show that this problem is NP-complete.

I have difficulty in finding out an NP-complete problem from which it can be reduced to this problem.

I tried to reduce vertex cover and set cover problems but i was not successful. I am not sure if i am heading in the right direction.

# Answer
This is SAT in disguise. Every name corresponds to a clause. Every paper corresponds to a variable. Each side of the paper corresponds to a possible truth assignment to the variable.

If this is unclear, I suggest working out an example.
> 2 votes

---
Tags: np-complete, reductions, np-hard, np
---


# Question
Title: 3-SAT problem with number of clauses equal to number of variables
Consider the 3-SAT problem where the formula is in conjunctive normal form and we restrict the Boolean formulas such that the number of clauses in the formula is equal to the number of variables. Is this problem still NP-hard?

For example, this formula has $3$ variables and has $3$ clauses $(\lnot x\_1 \vee \lnot x\_2 \vee \lnot x\_3 ) \wedge (\lnot x\_1 \vee \lnot x\_3) \wedge (\lnot x\_2 \vee \lnot x\_3)$,

and the following formula has three variables but has only two clauses $(\lnot x\_1 \vee \lnot x\_2 \vee \lnot x\_3 ) \wedge (\lnot x\_2 \vee \lnot x\_3)$.

# Answer
> 7 votes
Let the variant of the 3-SAT problem you describe be called EQUAL-3-SAT, where (following your definition) each clause has at most 3 literals. We prove EQUAL-3-SAT is NP-complete by a reduction from 3-SAT as follows.

Let $\phi$ be an instance of 3-SAT with $n$ variables and $m$ clauses. If $\phi$ is balanced already in the beginning (the case $n=m$), we do nothing. If $n \> m$, we introduce a fresh variable $x$ that does not appear anywhere in $\phi$ and add to $\phi$ exactly $n-m+1$ clauses of the form $(x)$, so we have $n=m$, and we are done.

Then, if $n \< m$, we can do similar balancing: each addition of a 3-literal clause $(a \vee b \vee c)$, where $a$, $b$ and $c$ are fresh variables, increases $n$ by $3$, and $m$ by $1$. Keep adding this clause to $\phi$ until $n=m$, or the difference between $n$ and $m$ is exactly one or three (if the difference was two, repeating the process once more would balance $\phi$). If the difference is one, adding one more 3-literal clause causes $n=m+1$ thus we use the balancing process of the first step (case $n \> m$). If the difference is three, we simply add an 2-clause of the form $(a \vee b)$, increasing $n$ by two and $m$ by one, again giving us $n=m$.

Finally, we observe the new formula is satisfiable if and only if $\phi$ was.

# Answer
> -4 votes
If number of clauses is equal to number of variables this problem is in P.

---
Tags: complexity-theory, np-hard, satisfiability
---