# Question
Title: Pushdown Automata - can you have multiple transition functions options between 2 states?
I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states?

For example,

```
 - if you have a 1 and the stack is empty, push it on the stack, and transition to q1
 - if you have a 0 and the stack is empty, push it on the stack, and transition to q1
 - if you have a 1 and there is a 1 on the stack, push it on the stack, and transition to q1
 - if you have a 1 and there is a 0 on the stack, pop the 0 off, and transition to q1
 - if you have a 0 and there is a 0 or 1 on the stack, push it on the stack and stay in q0

```

I was wondering if this is allowed, and it knows what to do given the scenario?

Sorry if this is obvious, I have been looking at some PDAs and haven't seen any that have multiple options to transition between states and was wondering if it was allowed.

# Answer
Simple answer: yes, that is allowed. In the example you give, it's simple--depending on the input symbol and the stack contents, there's one and only one choice for the action of the machine in state $q\_0$. It's even possible to have several actions as consequence to a single (input, stack top) pair, like this,

-- input 0 and stack top 1, push 0 and go to state $q\_2$

-- input 0 and stack top 1, push 1 and go to state $q\_3$

Seems wierd, I know but such machines are called *nondeterministic pushdown automata* and are quite useful; look them up.
> 2 votes

---
Tags: pushdown-automata
---


# Question
Title: How to perform orthogonal check on two circular binary strings?
Say we have two circular binary strings $a = a\_0a\_1...a\_{n-1}$ and $b = b\_0b\_1...b\_{n-1}$ with arbitary starting point, and define a and b are orthogonal if $\sum\_{i=0}^{n-1}a\_ib\_i = 0$. Is there a $O(nlogn)$ algorithm can tell a rotation of such circular binary string is orthogonal to another?

# Answer
> 7 votes
Say we have strings $a = a\_0a\_1...a\_{n-1}$ and $b=b\_0b\_1...b\_{n-1}$. First concatenate $a$ with itself and remove the last character. You should get a new string $a=a\_0a\_1...a\_{n-1}a\_0a\_1...a\_{n-2}$. Now we are interested in substrings of size $n$ in new string $a$ that are orthogonal to $b$ (this is a very classic trick to deal with cyclic strings/arrays).

Let's reinterpret them as polynomials in the following way.

For $a=a\_0a\_1...a\_{2n-2}$ use value at position $i$ as the coefficient associated with power $i$ in a polynomial such that $P\_a(x) = a\_0x^0 + a\_1x^1+...+a\_{2n-2}x^{2n-2}$.

Now reverse $b$ and get the new string $b=b\_{n-1}...b\_1b\_0$ and build a polynomial similarly as we did above. You get $P\_b(x)=b\_{n-1}x^0+...+b\_1x^{n-2}+b\_0x^{n-1}$.

Now let the magic happen. Multiply both polynomials into $P(x) = P\_a(x) \cdot P\_b(x)$ (Remember to do this fast). Wait, what ... where is the answer to the problem.

Let's see what is the $n-1$ coefficient of the new polynomial: $$P(x) = c\_0x^0+c\_1x^1+...+c\_{3n-3}x^{3n-3}$$

Coefficient at position $n-1$ is equal to $$c\_{n-1} = a\_0 \cdot b\_0 + a\_1 \cdot b\_1 + ... a\_{n-1}\cdot b\_{n-1}$$

Awesome, that is the dot product of original string $b$ with original string $a$ (without rotations). Keep looking at further terms of $P$. Coefficient at position $n$ is equal to $$c\_{n} = a\_1 \cdot b\_0 + a\_2 \cdot b\_1 + ... + a\_{n-1} \cdot b\_{n-2} + a\_{n} \cdot b\_{n - 1}$$

But keep in mind that $a\_n=a\_0$ since this is just $a$ concatenated with itself. So we have the dot product of $a$ rotated one step to the left with $b$. You can see that terms of $c\_{i}$ from $n - 1 \le i \le 2n - 1$ will give you the dot product of all rotations of $a$ with array $b$. Therefore, after computing $P$, you can find whether there is at least one dot product with value equals to $0$ easily.

In general polynomial multiplication is a useful representation to model convolutions of two arrays. It turns out that a lot problems can be modeled this way in areas such as: combinatoric, dynamic programming, string matching with least mismatches.

This is indeed relevant because there is a very efficient way to multiply polynomials which is via FFT in $O(n \log n)$ (or Karatsuba in $O(n^{\frac{3}{2}})$) instead of the naive $O(n^2)$ algorithm.

---
Tags: algorithms, string-matching
---


# Question
Title: DFA for language of all strings avoiding 'aa'
I'm trying to draw a dfa for this description

The set of strings over {a, b, c} that do not contain the substring aa,

current issue i'm facing is how many states to start with, any help how to approach this problem?

# Answer
For an alphabet of $\\{a, b, c\\}$ constructing a DFA that accepts all strings *not* containing the substring 'aa' tells you several things about the number of states you need. Firstly, and this is true for any DFA, you need at least one accepting state. Since your DFA is meant to filter out some strings, it requires a 'trap' or 'dead' state, a state that may never reach an accepting state once reached. Now clearly the strings 'a', 'b', 'c', and '' (empty string) do not contain the substring 'aa', therefore we know our initial state must also be an accepting state, which eliminates the next obvious choice for a new state.

So you know you need *at least* two states in your DFA, one trap state and one accepting state (which is also your initial state). Now you may also know that to construct a DFA that accepts the string 'aa' would require two states at least, so this gives a good guess that one additional state is required before transitioning to the trap state. So now there are three states to work with, if more are required they should come up as you construct your DFA from there.
> 1 votes

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


# Question
Title: All languages are regular, as unions of singleton languages
We know that singleton languages (languages containing exactly one word) are regular. We also know that a finite union of regular languages is also regular.

Suppose there is a non-regular language $L$. For every finite subset $\\{x\_1,x\_2,\ldots,x\_i\\}$ of elements of $L$, we can take the corresponding singleton languages and compute their union. This new language (which is a subset of $L$) should be regular. Now we do the same with rest of the language.

Finally, we must have $sL\_1, sL\_2,\dots, sL\_n,\dots$ which are all subsets of $L$ that are finite regular languages. If we take the union of $sL\_1, sL\_2,\dots, sL\_i$, where $i$ is finite, we again have a regular language. We do this for all languages obtained from $L$.

If we keep doing such "finite" unions of regular languages, we will eventually obtain $L$, which must be regular because we obtained it from a finite union of regular languages.

This obviously isn't right, but I don't understand why.

# Answer
The same "argument" would show that $\mathbb{N}$ is finite since it's the union of finite sets $$\mathbb{N}=\\{0\\}\cup\\{0,1\\}\cup\\{0,1,2\\}\cup ...$$ The point is that knowing that a given property is preserved under a given operation does not mean that it's preserved under "infinite iterations" of that operation.
> 7 votes

# Answer
You proved that any *finite* languages are regular. All the languages that you generated are finite.
> 2 votes

# Answer
You need to *keep doing* it an infinite number of times before you reach any infinite languages. So your proof will involve transfinite induction. As Wikipedia says:

> Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers.
>
> Let P(α) be a property defined for all ordinals α. Suppose that whenever P(β) is true for all β \< α, then P(α) is also true. Then transfinite induction tells us that P is true for all ordinals.
>
> Usually the proof is broken down into three cases:
>
> * *Zero case*: Prove that P(0) is true.
> * *Successor case*: Prove that for any successor ordinal α+1, P(α+1) follows from P(α) (and, if necessary, P(β) for all β \< α).
> * *Limit case*: Prove that for any limit ordinal λ, P(λ) follows from \[P(β) for all β \< λ\].

It is the *limit case* you won't be able to prove.
> 2 votes

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


title: nested boxes algorithm

text:
# Question
Title: nested boxes algorithm
I am given a set of 3D boxes {$B\_1$, $B\_2$...$B\_n$} and each box have length, width and height. But these values are interchangeable since I can rotate the box. I need to find out the maximum sequence of nested boxes.

I have tried this problem using sort. But I still get stuck. I used built in sort function to sort all boxes by length in ascending order. I read the reference about this question and learned that people used radix sort. I have know idea how radix sort is applied here because all sorts I am familiar is comparison sort.

# Answer
> 1 votes
One solution that comes to mind is to first build a directed graph where every vertex represents a vertex. An edge goes from Box A to Box B if B fits into A. One can easily verify that this graph contains no cycles. A maximum sequence of nested boxes is equivalent to the longest path in this directed acyclic graph. A longest path in a DAG can be found by using a topological sort on the graph.

This surely is a bit overkill and is probably also not the most efficient solution ($O(n^2)$ for building the graph).

---
Tags: algorithms, data-structures
---


# Question
Title: Return the subset with smallest cardinality of an array whose elements sum to at least a given value
Suppose we are given an array $A\[1\ldots n\]$ and a value $C$.

Is there an algorithm with linear expected runtime that can produce an array that is the subset with smallest cardinality of $A\[1\ldots n\]$ whose elements sum to at least $C$?

# Answer
> 1 votes
First, we randomly select an element that is not the smallest one as a pivot, and partition the elements into two subsets: the ones less than the pivot ($P$) and the ones no less than the pivot ($Q$). Let $S$ be the sum of elements in $Q$.

* If $S=C$, then $Q$ is exactly the optimal subset we want.
* If $S\<C$, then the optimal subset is the union of $Q$ and the subset with smallest cardinality of $P$ whose elements sum to at least $C-S$, which can be found by recursively applying this algorithm on $P$.
* If $S\>C$, then the optimal subset is the subset with smallest cardinality of $Q$ whose elements sum to at least $C$, which can be found by recursively applying this algorithm on $Q$.

Let $T(n)$ denote the expected running time of this algorithm on an input of $n$ elements, we have $$T(n)\le \frac{1}{n-1}\sum\_{i=1}^{n-1} T(\max\\{i,n-i\\})+cn,$$ where $c$ is a constant. By mathematical induction we can conclude that $T(n)\le 4cn$, thus the algorithm runs in expected linear time.

---

You can also use the idea of median-of-medians to get a **worst-case** linear time algorithm by selecting the pivot as the apporximate median produced by the median-of-medians algorithm.

---
Tags: algorithms, arrays, subset-sum
---


# Question
Title: Is {a^n: n is a product of exactly two primes} regular?
I am struggling to prove the following question.

> $L\_1 = \\{a^n: n \text{ is a product of exactly two primes}\\}$

I feel like the language is not regular but I am having trouble proving it. I tried using pumping lemma but got stuck at the end. Here's how I did it:

Assume that the language is regular and $m$ is a constant of Pumping Lemma. Now let $w = a^M$ where $M \> m$ and $M$ is a co-prime number. Clearly $w$ is in the language and $|w| \> m$.

Now let $y=a^j$ where $j$ is between $1$ and $m$, with $|xy| \leq m$ and $|y| \geq 1$.

**This is where I am getting stuck.** I feel like we should pump up but I don't know by "how much". Also, I feel like I have to know what is the next co-prime number after $M$, but can't figure it out.

# Answer
Just pump up $(M+1)$ $y$'s. Now you get $xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$. Since $M$ is a product of two primes, $M(j+1)$ is a product of at least 3 primes, so $a^{M(j+1)}\notin L\_1$, which proves $L\_1$ is not regular by the pumping lemma.
> 3 votes

# Answer
Here is yet another proof. It is known that the number of integers at most $n$ which are the product of two primes is $o(n)$, see for example this answer, which gives the asymptotic $\frac{n\log\log n}{\log n}$. This means that your language is infinite yet has vanishing asymptotic density. This is impossible for a regular unary language.
> 2 votes

# Answer
There is an alternative to the “pumping” lemma which I find easier: After each possible input, determine the set of continuations that would complete a string of the language. You can use each of those sets as a state in the finite state machine for the language, so if there is a finite number of those sets then the language is regular- if there are infinitely many different sets, the language is irregular.

In your case, after processing k symbols, a further pq-k symbols for primes p, q gives a string in the language. We’ll need some statement about primes. One statement is: The gaps between primes are arbitrarily long. Let p, q be consecutive primes with a larger gap q-p than any previous gap. After processing 2p symbols, the smallest even number of symbols to give a product of two primes is 2(q-p). Therefore, after processing 2p symbols you are in a different state than after processing 2p’ symbols for any prime p’ \< p.
> 1 votes

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


# Question
Title: Is L2 = {a^n| n is a product of one or more primes} regular?
I am having a hard time proving the following with pumping lemma: Is $L\_2 = \\{a^n \mid \text{$n$ is a product of one or more primes}\\}$ regular?

Here's what I have so far:

* Suppose $L$ is regular, and let $m$ be the constant pumping lemma.
* Let then $w = a^m$ where $m$ is a product of at least one prime number, therefore $w$ is in the language $L\_2$ and $|w| \geq m$.
* Then $w = xyz$, where $|xy| \leq m$ and $|y| \geq 1$.
* Then $y = a^j$ where $j \geq 1$.

This is where I'm not sure what to do: Pumping down we get $w\_2 = a^{m-j}$

I don't know where to keep going from here since I don't even know if pumping down is the right thing to do.

# Answer
According to the Fundamental Theorem of Arithmetic, any integer $\>1$ can be written as a product of one or more primes (in a unique way). So, it seems that your language can be simplified as $\\{a^n\mid n\geq 2\\}$.
> 1 votes

# Answer
As all words of length $\>1$ and only consisting of a's should be contained in L2, there is a simple finite automaton that recognizes it. So your attempt at using the pumping lemma is futile, as the pumping lemma only helps you prove that a language is irregular if it is, and doesn't tell you anything about languages that are regular.

Maybe I'm also understanding your description of L2 wrong, in that case please add a comment or edit your question.
> 1 votes

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


# Question
Title: What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?
After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages are delivered in order and no message is lost. In addition to that, the algorithm uses Lamport logical clock, so the requests will always be processed in order.

# Answer
I believe the purpose is to fulfill the first condition of entering the critical section (site $S\_i$ must receive a message from all other sites with timestamp greater than its own request) in case some other site never requests to enter the critical section.

If $S\_i$ sends a critical section request to $S\_j$, but $S\_j$ never requests the critical section and doesn't send a reply, $S\_i$ will never receive a message from $S\_j$ thus causing it to wait forever to enter the critical section. In this scenario, $S\_i$ cannot know for sure that $S\_j$ does not have a pending request with a timestamp lower than $S\_i$'s request.
> 1 votes

---
Tags: distributed-systems, mutual-exclusion
---


# Question
Title: Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$
> Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S)= \epsilon (\epsilon (S))$.

I would like to prove this by contradiction but I don't know if my idea is correct.

> Definition of $\epsilon -closure$: $\epsilon : 2^Q \rightarrow 2^Q $
>
> a) $S \subseteq \epsilon (S)$ Base case
>
> b) If $q \in \epsilon (S)$ then $\delta(q,\epsilon )\subseteq \epsilon (S)$ Recursive case
>
> c) and nothing else is in $\epsilon (S)$

Prove i) That $\epsilon (S) \subseteq \epsilon (\epsilon (S))$.

By contradiction, suppose $\exists x \in \epsilon (S)$ such that $x \notin \epsilon (\epsilon (S))$.

Using definitions of $\epsilon (S)$ , we know $S \in \epsilon (S)$. So $x \in S \in \epsilon (S)$, and $\delta(x,\epsilon ) \subseteq \epsilon (S)$.

Using definitions again, we know $S \in \epsilon (S)$, so $x \notin \epsilon (\epsilon (S))\notin \epsilon (S)$. Also $\delta (x, \epsilon) \nsubseteq \epsilon (\epsilon (S))$

We have a contradiction because $x \notin \epsilon (S)$ and we said $x \in \epsilon (S)$.

Therefore i) is true.

# Answer
> 1 votes
Your definition of $\epsilon$-closure is quite problematic. Here is a better formulation:

> $\epsilon(S)$ is the intersection of all sets $T \subseteq Q$ such that (i) $T \supseteq S$ and (ii) if $q \in T$ then $\delta(q,\epsilon) \subseteq T$.

Here is a series of claims which imply $\epsilon(S) = \epsilon(\epsilon(S))$.

**Claim 1.** $\epsilon(S) \supseteq S$.

**Proof.** $\epsilon(S)$ is the intersection of sets containing $S$, and so contains $S$.

**Claim 2.** If $q \in \epsilon(S)$ then $\delta(q,\epsilon) \subseteq \epsilon(S)$.

**Proof.** If $q \in \epsilon(S)$ then $q$ belongs to all sets $T$ in the definition. Property (ii) implies that all of these sets contain $\delta(q,\epsilon)$, and so $\epsilon(S)$ contains $\delta(q,\epsilon)$.

**Claim 3.** $\epsilon(\epsilon(S)) \supseteq \epsilon(S)$.

**Proof.** Follows directly from Claim 1.

**Claim 4.** $\epsilon(\epsilon(S)) \subseteq \epsilon(S)$.

**Proof.** $\epsilon(S)$ satisfies the $T$-conditions for $\epsilon(S)$: (i) is trivial, and (ii) follows from Claim 2.

**Claim 5.** $\epsilon(\epsilon(S)) = \epsilon(S)$.

**Proof.** Follows from Claim 3 and Claim 4.

---
Tags: automata, finite-automata, proof-assistants, check-my-answer
---


# Question
Title: Are SAT problems with at most one false clause NP-complete?
Is the problem of deciding whether a SAT instance, where at most one clause is false (that is, any given variable assignment will either lead to all clauses being true, or all but one), is satisfiable solvable in polynomial time?

# Answer
> 3 votes
Given a CNF with $n$ variables and $m$ clauses, we denote by $A\_i$ the set of truth assignments that do not satisfy clause $i$. Then the number of satisfiable assignments is $$2^n-\left|\bigcup\_{i=1}^m A\_i\right|.$$ Since each assignment makes at most one clause false, $A\_i$ and $A\_j$ are disjoint for $i\neq j$. Also note $|A\_i|=2^{n-n\_i}$ where $n\_i$ is the number of variables in clause $i$. Hence, the number of satisfiable assignments is exactly $2^n-\sum\_{i=1}^m 2^{n-n\_i}$ (this result is also given as lemma 2 in \[1\]).

So we can decide whether the CNF is satisfiable by checking whether $2^n-\sum\_{i=1}^m 2^{n-n\_i}\>0$, which can be done in polynomial time.

---

\[1\] Nishimura, N., Ragde, P., & Szeider, S. (2007). Solving #SAT using vertex covers. *Acta Informatica, 44*(7-8), 509-523.

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


# Question
Title: How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?
I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List Representation. What I did is as follows:

> • Do a simple BFS Traversal using a Queue while maintaining the parent node of nodes enqueued in the queue.
>
> • If I come across a node `u` that has a neighbor `v` such that `v` is already visited but `v` is not the parent of `u` then that means there is cycle in the graph.

**Pseudocode**:

```
#adjList is the adjacency list given as a dictionary
#myQueue is a double-sided queue containing node and its parent node ([Node, parNode])
#visited is a set containing visited nodes

while(myQueue):
    currNode, parNode = myQueue.pop() #dequeue operation
    visited.add(currNode) #Marking currNode as visited
    for childNode in adjList[currNode]: #Traversing through all children of currNode
        if currNode not in visited:
            myQueue.appendleft([childNode, currNode]) #Enqueue operation
        else:
            if childNode!=parNode: #Main logic for cycle detection
                print('CYCLE DETECTED')
                break

```

The above approach is working except in cases when I have more than 1 edge between 2 vertices for e.g. in following case we have 2 edges between vertices `0` and `1`:

Adjacency list of above graph is: `adjList = {0:[1, 1, 2], 1:[0, 0], 2:[0]}`. Here we can clearly see that the graph contains a cycle (In the adjacency list, it is represented by the fact that `1` appears twice in the adjacency list of `0` and `0` appears twice in the adjacency list of `1`) but above algorithm is not able to detect the same because when BFS will reach vertex `1`, vertex `0` is already visited but vertex `0` is also the parent of vertex `1` so this cycle will go undetected.

My question is how I can modify above algorithm to detect such cases?

**Edit**: I tried the same logic on directed graphs also, and I am facing similar problem i.e. case when I have a directed edge from vertex `0` to vertex `1` and another directed edge from vertex `1` to vertex `0`

# Answer
> 1 votes
If the case arrives where you see the case of a node being already visited but it is the parent of your current node, you just have to check whether there is a double edge between them. How to do that depends on your data structure, but if your adjacency list is sorted it would just amount to searching for the edge and checking how often it is in there.

Another problem I see is that your adjacency list doesn't actually contain any information that the edge is doubled.

For directed graphs, you can just completely get rid of the "parent check", as the only time that case arrives is when you have two edges going from $u$ to $v$ and vice versa.

Additionally, be careful if the graph is not connected, your BFS will not cover all of it, so you would need to start another BFS from an unvisited vertex again. This is especially important for directed graphs, as even if the graph might be connected, your BFS will probably not cover all of it.

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


# Question
Title: Applying subproblem technique to permutations with grouping
I am trying to apply overlapping subproblems and dynamic programming to permutations.

Say, we have a set of $n$ elements in a string. Each of these elements could be a $1$ or a $0$.

Given some string, I am trying to count the number of valid permutations- where a valid arrangement is defined as an ordering with no $1$ that stands alone from other 1s.

Example input string: $0101$

Example of valid arrangements: $1100, 0011, 0110$

Not valid: $0101, 1010, 1001$

EXPECTED OUTPUT: $3$

For example:

Say our input string contains four 1s and two 0s.

I suppose my difficulty is coming with defining the sub-problem. I initially thought I could set up a string with only the $0$ elements with slots/bins in between. $\[ \] 0 \[ \] 0 \[\] $, and then continue to use combinatorics to compute the number of additional arrangements possible with each 1 added in.

The first 1: 0 possibilities, because it will never have a 1 to accompany it.

Adding the 2nd 1: 3 possibilities, because the pair can go in either of the 3 slots.

Adding the 3rd 1: 0 new possibilities, because it must go with the other 2 ones, wherever they are.

Adding the 4th 1: We have enough to make 2 groups of $1$s now... here is where I start getting unsure. I'd think it would be an additional 3 possibilities. $\binom{3}{1} + \binom{3}{2} = 6$ total

Would anyone have an idea if I'm on the wrong track, or if not, how to proceed? This approach doesn't seem like it works for larger values. Thanks!

# Answer
> 0 votes
The subproblems can be broken down as follows.

```
f0 :- Number of available 0s.

f1 :- Number of available 1s.

ld :- The last digit of the string generated till now.

dp[f1][f0+f1][0] = dp[f1][f0+f1-1][0] + dp[f1-1][f0+f1-1][1]

dp[f1][f0+f1][1] = dp[f1-2][f0+f1-2][0] + dp[f1-1][f0+f1-1][1]

```

which basically boils down to,

Say at any step the string is `S0`

then `S011` and `S00` are valid as well.

Similarly,

if the string is `S1` then `S11` and `S10` are valid as well.

The following code solves the given problem recursively.

```
def rec(f0,f1,stn): # Frequency of 0,Frequency of 1, List to store generated output
  if f0==0 and f1==0:
    print(''.join(stn))
    return -1;
  if len(stn)==0 or stn[-1]=='0':
    if f0>0:
      rec(f0-1,f1,[x for x in stn]+['0'])
    if f1>1:
      rec(f0,f1-2,[x for x in stn]+['1','1'])
  else:
    if f1>0:
      rec(f0,f1-1,[x for x in stn]+['1'])
    if f0>0:
      rec(f0-1,f1,[x for x in stn]+['0'])

rec(4,4,[])

```

You can easily solve the overlapping subproblems issue by using a dp-table along with the propagation rules listed above.

Output of the code for a string with `4 1s` and `4 0s`:-

```
00001111
00011110
00011011
00111100
00110011
00110110
01111000
01100011
01100110
01101100
11110000
11000011
11000110
11001100
11011000

```

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


# Question
Title: Does the naive conversion of a Boolean Formula to CNF have a polynomial or exponential complexity?
I am reading the naive conversion to CNF, this procedure is explaining in this book book, but I have not found a conplexity analysis of this algorithm:

1. elimination of equivalence
2. Elimination of Implications
3. elimination of double negation
4. De Morgan Laws
5. distributive law

I found one implementation of this method in this Repo https://github.com/netom/satispy

Thanks

# Answer
> 1 votes
Any algorithm necessarily has exponential complexity, since the CNF of a formula can be exponentially longer than the DNF, and the input might be in DNF.

# Answer
> 0 votes
If you require a logically equivalent CNF formula, then that will give you a worst-case exponential size formula.

If, however, equisatisfiability is enough, then you can use Tseitin encoding, which will give you a polynomial size formula. The trick is in adding new atoms for logical operators.

---
Tags: satisfiability, boolean-algebra, propositional-logic
---


# Question
Title: Have computer scientists proven the world is fundamentally unpredictable?
In the book "This Will Make You Smarter: 150 New Scientific Concepts to Improve Your Thinking", Rudy Rucker, a computer scientist, state:

> A little-known truth: Every aspect of the world is fundamentally unpredictable. Computer scientists have long since proved this.
> How so? To predict an event is to know a shortcut for foreseeing the outcome. A simple counting argument shows that there aren't enough shortcuts to go around. Therefore most processes aren;t predictable. A deeper argument plays on the fact that if you could predict your actions, you could deliberately violate your predictions, which means the predictions were wrong after all.
> We often suppose that unpredictability is caused by random inputs from higher spirits or from low-down quantum foam. But chaos theory and computer science tell us that non-random systems produce surprises on their own. The unexpected tornado, the cartoon safe that lands on Uncle George, the winning pull on a slot machine odd things pop out of a computation. The world can simultaneously be deterministic and unpredictable.

(full entry available here)

My first question relates to references. Where can I read about computer scientists "proving" the world is "fundamentally unpredictable"?

Second, can someone elaborate on the argument? For instance, consider the phrase

> if you could predict your actions, you could deliberately violate your predictions, which means the predictions were wrong after all.

This is just bad modelling. If human agency (mine) affects the world, then my model should incorporate my action. And thus, I can predict what my action would cause to the world. So I don't see how this argument holds.

I also don't understand how the world can be deterministic and unpredictable. Rather, what happens is that the world is so complex that it is, **to us, given our current state of our knowledge**, unpredictable. But this is **epistemological unpredictability** and not necessarily **ontological unpredictability**, which is what you would assume is the meaning of "the world is unpredictable". The author seems to not know this difference.

Can some one please explain?

# Answer
> 3 votes
You are correct - there are many logical gaps and over-simplifications in the passage that you quote. To unpick just some of them:

* "*Every aspect of the world is fundamentally unpredictable. Computer scientists have long since proved this*": Computer scientists prove things about computing systems and models of computing systems. Whether this tells us anything about the "real world" is debatable.
* "*If you could predict your actions, you could deliberately violate your predictions*": There are two counters to this argument. The first is that it assumes we have free will, which is not certain - perhaps we only *think* we have free will. What if the very act of trying to violate a prediction is itself predictable and actually fulfills the prediction ? The second counter is that even if we do have free will, this logical argument only means that we cannot predict our own actions. It does not rule out some other (more advanced ?) being predicting our actions.
* "*Chaos theory and computer science tell us that non-random systems produce surprises on their own*" : What chaos theory actually tells us is that there are deterministic systems in which any uncertainty in initial conditions increases exponentially, leading to an uncertain future state that is, in effect, spread evenly across the whole configuration space. So deterministic systems can be unpredictable in the sense that any *finite* amount of information about the initial state does not let us conclude anything useful about a future state. But these "chaotic" systems are based on a continuous space of possible states. Whether they are accurate or useful models of the "real world" is, once again, debatable.

---
Tags: ontologies, epistemology
---


# Question
Title: Why do we have free variables in mu-calculus?
I'm reading the *Model Chekcing* book of E. M. Clarke and in the chapter about µ-calculus there is an example formula $$ f = \mu Z. ((q \mathrel{\mathrm{AND}} Y) \mathrel{\mathrm{OR}} \langle a \rangle Z) $$ As the author has mentioned, here $Y$ is a free variable, and we need an association list to pair $Y$ with the corresponding states. But why do we need it? Can it be replaced by an atomic proposition?

# Answer
> 1 votes
If you define the $\mu$-calculus to not allow free variables, you would have the problem that the components of a well-formed formula are not again well-formed formulas.

Consider a well-formed formula "$\mu Z . \varphi$", such that $Z$ occurs freely in $\varphi$ and $\varphi$ has no other free variables. If you were to exclude formulas with free variables from your definition, $\varphi$ would not be a well-formed formula.

This would make structural induction on formulas more complicated. For example the semantics of formulas (the set of states in which the formula holds) is usually defined inductively: You define the semantics of "$\mu Z . \varphi$" in terms of the semantics of $\varphi$. If your definition says $\varphi$ is not a well-formed formula, you would have to extended the induction to also cover these non-well-formed cases. If you have to consider these cases every time you do structural induction, you haven't really gained anything from excluding them in your definition.

---
Tags: model-checking, mu-calculus
---


# Question
Title: If R is a regular language, is $R^3= R \circ R \circ R$ also regular?
My understanding of a regular language is that for a language to be formal, it must be able to be represented by a DFA or NFA. To prove a language is not regular you can use the pumping lemma to get a contradiction.

I am trying to figure out whether $R^3$ or $R \circ R \circ R$ is regular if R is also regular.

My understanding of the definition of $R \circ R$ is that it is kind of a transitive mapping of R?

And I think if $R \circ R$ is regular then $R \circ R \circ R$ is also regular, so I need to prove $R \circ R$ is regular which really means that I am trying to prove that regular languages are transitive?

I am not sure how I would go about doing this as I am a little confused how regular languages and transitivity relate - as I have only worked with relations for transitivity.

# Answer
> 4 votes
'$R$' is not used in the literature to indicate languages ... generally we use $L$. Anyway, the "$\circ$" operator indicates the concatenation of two or more languages. Keep in mind that the concatenation of regular languages is also regular: you can proove this by 'linking' the *NFA*'s/*DFA*'s thath recognize them. In this case you are concatenating a regular language with itself, so the resulting language is also regular.

NB: The opposite is not always true: if the concatenation of two languages is regular, this does not mean that the languages themselves are necessarily regular.

---
Tags: regular-languages
---


title: {0,1}* ∈ P class?

text:
# Question
Title: {0,1}* ∈ P class?
I have the following question about complexity time classes. Given the language $L = \\{0,1\\}^\*$, is it inside the class P or not?

$$ L = \\{0,1\\}^∗ ∈ P? $$

# Answer
A useful exercise to answer the question could be to build a simple Turing machine $M$ (let's say one tape and one head) that recognizes your language. Such a *TM* could work directly on the input tape and be equipped with an extremely simple transition function:

1. Read input
2. If $($input $= 0$ $\lor$ input $= 1$$)$ $\implies$ Move ***R*** (right on the tape)

Note that this machine can be "read-only" it doesn't need to write anything. Suppose that the input tape is encoded like this:

$I = \[\varnothing, 0, 1,1,0,0,1,0,0,1,0,0,1,1,.........,\varnothing\]$ and that your *TM* start from the left blank symbol and ***HALT*** $\iff$ it reaches the final blank symbol, you can notice that this machine ***HALT*** $\iff$ it recognizes $L$.

I strongly suggest you do this exercise, writing down the formal definition of the machine, especially the transition function's table. Once this is done it will be much easier for you to answer these questions:

1. What is the time complexity of running $M$ on $w$ $\in$ $L$ if |$w$| $=n$ ?
2. Is $w$ $\in$ $L$ regular and why?
> 3 votes

---
Tags: complexity-classes
---


# Question
Title: Prove that there isn't a DFA characterized by (a*)+(b*) for which |Q| = 3
> Let $R=(a\*)+(b\*)$ be a regular expression. Prove that there cannot exist any DFA $M=(Q,\Sigma,\delta , q0, A)$ such that $|Q| = 3$ and $L(M)=L(R)$.

The problem is, I think IT IS possible to construct such a dfa that has 3 states in total.

Am I missing something?

# Answer
What you draw is an NFA, because you do not have both transition for $a$ and $b$ in two accept states. Indeed, you need 4 states at least. Because you have 4 different states:

1. Initial state
2. Detect $a^\*$ strings
3. Detect $b^\*$ string
4. None of them

You can't merge the first 3 steps because they are exclusive. Now, you can suppose that we can merge the 4th state with the others. Definitely you can't merge the 4th state with second and third state. Hence. the only possibility is merging the 4th state with the first state. But, we have some transitions from the initial state to other states, and if we merge the 4th and the first state, we will accept some strings that are not totally $a$ or $b$. And that is the contradiction to the definition of the language. Therefore, we need a state to go there if we found any $b$ in the middle of some $a$s or vice versa.
> 4 votes

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


# Question
Title: Bubble sort: how to calculate amount of comparisons and swaps
For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $\theta ()$ notation? I would know how to do it for any sequence, but not for a given one.

# Answer
Number of swaps: The number of swaps in Bubble sort is exactly the number of inverted pairs, i.e. the number of pairs $(i,j):i \< j\wedge s\[i\]\>s\[j\]$. This number of pairs should be $(n/2-1)+(n/2-2) + ... + 1$ which is of the order of $n^2$.

Number of comparisons: This is of the order of $n$ times the number of passes through the list, which is of the order of $n$, as the element N needs to get to the end.

Therefore you have $\Theta(n^2)$ comparisons and swaps.
> 0 votes

---
Tags: asymptotics, sorting
---


# Question
Title: Find the minimal tank capacity to be able to travel from any city to any other
There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w\_{u,v} \> 0$ fuel. At the same $w\_{u,v}$ can differ from $w\_{v, u}$. The task is to find the minimal tank capacity to be able to travel from any city to any other (possibly with refuels) in $O(n^2\log n)$.

# Answer
> 1 votes
A possible solution may be to compute the all pair shortest path matrix and then select the largest value in the matrix.

As long as `|E|<<|V|^2` or the graph is not dense, your complexity constraint should be satisifed.

Johnson's algorithm does it in `O(|V|^2 log |V|+|V||E|)`.

Refer to this for a better understanding of time complexity in case of Jhonson's Algorithm.

# Answer
> 1 votes
We first sort all edges according to their costs from small to large. Say the sorted edges are $e\_1,e\_2,\ldots,e\_{n(n-1)}$, and the corresponding costs are $w\_1\le w\_2\le\cdots\le w\_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e\_1,\ldots,e\_i$. Now $w\_i$ is the minimal tank capacity we want.

Sorting costs $O(n^2\log n)$ time. To find the minimal $i$, we can use the bisection method. We first test whether the graph is strongly connected with the edges $e\_1,\ldots,e\_{n(n-1)/2}$. If yes, we then test the connectivity with the edges $e\_1,\ldots,e\_{\lceil n(n-1)/4\rceil}$, otherwise we test the connectivity with the edges $e\_1,\ldots,e\_{\lceil3n(n-1)/4\rceil}$, and so on. The running time to find the minimal $i$ is also $O(n^2\log n)$. So the total running time of this algorithm is $O(n^2\log n)$.

---
Tags: algorithms, graphs, dynamic-programming, graph-traversal, weighted-graphs
---


# Question
Title: How does one simulate continuous gravity using a discrete timestep?
While gravity in real life is continuous, computers are limited to discrete calculations.

Therefore, a seemingly correct projectile simulation inevitably drifts off.

For example:

```
// Repeat once per frame
position += velocity * deltaTime;
velocity += gravity * deltaTime;

```

Graphed, compared to the actual projectile formula

# Answer
> 1 votes
This is an example of Euler's Method

Using differentiation, you can find a better formula. Since discrete calculations only "drift" if they are non-linear, you only need to alter the position/time calculation.

```
// Repeat once per frame
position += velocity * deltaTime + gravity * Math.pow(deltaTime, 2.0) / 2.0;
velocity += gravity * deltaTime;

```

Even large timesteps align perfectly with the continuous graph:

---
Tags: discrete-mathematics, physics
---


title: binomial tree number of nodes

text:
# Question
Title: binomial tree number of nodes
Does anybody knows that how we can assign number to nodes for binomial tree . I mean how we can represent the number of nodes by array? please give me hint I am really confused .

# Answer
In a binary tree, you can represent the tree from root to leaves as follows:

0 root 1 2 root's children 3 4 5 6 root's grandchildren etc.

To get the children of a node, you take its index x and compute 2x+1 and 2x+2.

This makes some certain assumptions: Each node has exactly two children, except the leaves, which are all on the same (or two neighboring) levels. If a level is not full, it is filled from left to right.
> 0 votes

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


# Question
Title: Rounding of $2-10^{20}$ in IEEE double precision
How do we get the rounding of $2-10^{20}$ in IEEE double precision? The textbook says it is $-10^{20}$, but I do not know why. I think my textbook only explains the rule for rounding mantissa.

# Answer
> 1 votes
Determine the binary exponent of $10^{20}$. From that determine the value of the lowest bit of the mantissa of $10^{20}$. Then ask yourself: How large does a number x have to be at least so that round (x-$10^{20}$) is not $-10^{20}$?

---
Tags: rounding
---


# Question
Title: Would proving P≠NP be harder than proving P=NP?
Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP.

Let Q be one of known NP-hard problems. To prove P=NP, we need to design a single polynomial time algorithm A for Q and prove that A correctly solves Q.

To prove P$\neq$NP, we need to show that *no* polynomial time algorithm solves Q. In other words, we have to rule out *all* polynomial time algorithms.

I have heard people say this makes the second more difficult task (assuming that it is really true).

> Is there a reason to think that proving P=NP (assuming that P=NP) would be easier than proving P$\neq$NP (assuming that P$\neq$NP)?

# Answer
> 28 votes
As Raphael explains, this question is ill-posed, since at most one of P=NP and P≠NP should be provable at all. However, a similar question arises in theoretical computer science in several guises, the most conspicuous of which is in the field of *approximation algorithms*.

Given an NP-hard optimization problem (say, maximization), we can ask how well we can approximate it. Proving an upper bound on the possible approximation is akin to P=NP, while proving a lower bound on the possible approximation is akin to P≠NP. The former is much easier than the latter. Indeed, to prove an upper bound all one has to do is to come up with an approximation algorithm and analyze it. In contrast, all known lower bounds are *conditional*: they are valid only if P≠NP (indeed, if P=NP then every NP-hard optimization problem would become solvable). To prove these lower bounds, we show that if we could approximate the problem too well, then we would obtain a polynomial time algorithm for some NP-hard problem. Usually this is done via the intricate technical machinery of the PCP theorem. This field, known as *hardness of approximation*, can be approached only be specialists, and is technical more challenging than most approximation algorithms. So in this case at least, P=NP is indeed easier than P≠NP.

# Answer
> 9 votes
We have not ruled out the possibility of a simple proof that P=NP. If someone tomorrow comes up with an algorithm that solves a NP-complete problem in P time, the world changes.

On the other hand, we *have* ruled out the possibility of a simple proof that P!=NP. Our typical proof techniques for showing that two different complexity classes have been formally proven insufficient. Three such techniques are known as "arithmetization", "natural proof"s, and the category of proofs called "relativizing" (ones that do not care what oracles are in use). It can be proven that any proof technique that falls into any 3 of those categories cannot prove P!=NP.

In effect, there is strong evidence that proving P!=NP requires new kinds of proof (new techniques with different properties), not just novel application of well-known proof techniques.

---

Now, it might turn out that P=NP, while there is no simple to verify algorithm in P that solves an NP-complete problem, and that novel proof techniques are required to prove P=NP. (If P=NP, we already know algorithms that are technically in P that solve NP-hard problems, amusingly. They are not practical to run, as their constant factor is large.)

Basically, we know a lot about what we cannot use to prove P!=NP, while we seemingly know little about what we cannot use to prove P=NP.

# Answer
> 8 votes
Well you basically have the idea. We generally think that P != NP but have no idea how we would even prove these things are not equal.

Conversely, if P = NP, you'd think we would have found an algorithm to solve one of the dozens of NP-complete problems by now.

These are very hand-wavey arguments but in a couple sentences they describe the culture among computer scientists.

Whether proving P != NP is "harder" of course depends on which is true though (barring meta-mathematical results?), and that, of course, we do not know.

# Answer
> 5 votes
There are some experts who believe that proving P$\neq$NP is a harder than proving P=NP in the sense of the time that they think it will take to settle the P vs. NP question. But that is mostly some intuition based on the feeling that it is easier to design algorithms for problems than proving that there are no (efficient) algorithms. Generally we have not been very successful in proving lower bounds for problems. We cannot even rule out a linear time algorithm for SAT. We cannot rule out that there isn't a log space algorithm for SAT. We cannot even show that there isn't polynomial size Boolean circuit of constant depth with $\land$, $\lor$, $\lnot$, and $\mod\_6$ gates that cannot solve SAT (in layman's terms it is possible that there is a constant time parallel algorithm with polynomial number of processors that solves SAT and each process computing only one of these gates). The best lower bounds we have for Turing machines solving SAT cannot even show that there isn't an algorithm whose running time multiplied by the space it uses is $n^{1.9}$. I can go on quite a bit about the quite embarrassing state of proving lower bounds (but keep in mind that we also have barrier results that explain why it is so difficult to prove lower bounds). Some experts think Ketan Mulmuley's GCT program is the most likely to resolve P vs. NP and Mulmuley himself has repeated said that he believes it will probably take over a hundred year to get there.

However there has been some recent work by Ryan Williams and others that show that there are intrinsic links between proving lower bounds and finding algorithms. E.g. he showed that an algorithm slightly better than brute force algorithm for a particular restricted SAT problem implies circuit lower bounds and then he designed such an algorithm. So I think people are a bit less pessimistic and also don't seem developing algorithm and proving lower bounds as separate as people used to think they are.

Now let's go back to the question and try to look at it a bit more religiously. To answer the question we need to formalize what we mean by difficulty of proving a statement. For this we can use proof theory and proof complexity which exactly looks at various ways of defining hardness of proving a statement. So let me give a short explanation of what is proof complexity is about. A proof system is essentially a verifier algorithm for proofs. We give a string $\pi$ and a string $\varphi$ and we ask if $\pi$ is a proof of $\varphi$ and the algorithm returns yes or no. You can think of any proof checker in this way. You can also think of proofs in a mathematical system like ZFC as such. The checking process itself can be done in polynomial time in the size of the proof because it is a syntactic task.

Now consider a formula $\varphi$. What does it mean for $\varphi$ to be hard to prove? One possibility is that the shortest proof of $\varphi$ is very large. If it is too large, say the number of bits required to represent it is larger than $2^{65536}$ then we cannot even state the proof. A second possibility is that the proof is not too large but it is hard to find. Let me explain this a bit: think about a proof search algorithm. Most rules are deterministic in a system like LK in the sense that you can determine the previous lines from the current line in the proof and the rule. An important exception to this is the cut rule. It is important because although we don't need the cut rule for proving statements it can reduce the size of the shortest proof considerably. However cut rule is not deterministic: there is a cut formula that we have to guess. You can think of cut rule as proving lemmas and using them. The cut formula is like a lemma. But what lemma should we prove that will help us? That is the difficult part. Often a result is proven in mathematics by finding a good lemma. Also when you use previously proven results you are essentially using the cut rule. Another important component in proving statements is definitions. Often we define a new concept, then prove statements about it, and finally apply it in our particular case. Using definitions reduces the size of the formulas (try expanding some mathematical formula to the pure set theoretic language by expanding definitions to get an idea of how important definitions are). Again what new definitions should we use? We don't know. This brings me to third meaning of a statement being difficult to prove. A statement can be difficult to prove because you need strong axioms. Take e.g. CH. It cannot be proven in ZFC nor can be refuted in ZFC. This is an extreme case but that happens more often that you think. E.g. do we need large cardinal axioms (to be able to work in Grothendieck universes) to prove FLT or can we prove it in a much weaker theory like PA? This is another concept regarding the difficulty of proving statements.

Now let's go back to P vs. NP. We don't have results that state that the problem cannot be settled one way or another in rather weak arithmetic theories. Alexander Razborov wrote a paper in 1995 titled "Unprovability of Lower Bounds on the Circuit Size in Certain Fragments of Bounded Arithmetic" that showed it is not possible to prove it in some weak theory but the theory is really really weak. To my knowledge there has not been much progress in extending that to considerable stronger theories like Sam Buss's bounded arithmetic theories and even if the result is extended to them they are still far away from something like PA or ZFC. So in short not only we cannot prove that SAT is not in very small complexity classes, we cannot even prove we cannot prove P$\neq$NP in very weak theories. The formal reason we have about why it is difficult to prove P$\neq$NP is barrier results that state that such and such techniques cannot prove by themselves that P$\neq$NP. They are nice results but they don't even rule out the possibility of combining those techniques to show P$\neq$NP.

# Answer
> 4 votes
I think that the question can be reduced to: is it easier to prove that something exists or to prove that something does not exist.

The argument in favour of proving that something exists is that it's easy to construct things that might satisfy the requirements and it's also easy to check if they indeed satisfy them.

In some cases this is true: if you want to find the root of a polynomial, it's easy to construct numbers and it's easy to check if they are roots.

The problem, of course, is that you have to be lucky. You might be able to reduce the search space, e.g. by proving that it must be a multiple of 5 or between 1 and 10; but, unless you limit it to a finite set of numbers (in which case you are not really using the "guess and validate" method), you don't have a method for solving the problem: you only have a method that, assuming you are extremely lucky, might generate a solution.

But if you want that, it's equally easy to prove that something does not exist! Generate texts that could be possible solutions and check if they actually are.

Therefore, having a method that might yield the solution by pure luck does not mean that proving that something exists is easier.

Now, is it generally easier to prove that something exists with some other method? It depends on the actual problem because otherwise proving that something does not exist would be reduced to proving that a proof that it doesn't exist exists. And I'm afraid that we cannot measure that as there never was something that was proven to both exist and not exist so we can (attempt to) measure the difficulty of the proof.

# Answer
> 0 votes
If you prove that P=NP then proving the opposite is not just harder, but impossible.

# Answer
> -2 votes
I believe it is impossible to prove P\<\>NP, because you would have to rule out all algorithms that could prove P=NP. There could be an infinite number of these possible. There is no way to disprove infinity, therefore it’s not possible. On the other hand all it would take is a single algorithm to prove P=NP, if it is so. Therefore, either P=NP which someone will prove, or we will never know.

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Is concept of virtual memory about memory isolation or about ability to swap? Or both?
Most reading I found about virtual memory, such as http://www.linux-tutorial.info/modules.php?name=MContent&pageid=89 or https://en.wikipedia.org/wiki/Virtual\_memory always state that virtual memory is a concept that allows operating system to make it "appear as though you have more memory than you really do".

But isn't that what overcommit is about? Isn't whole virtual memory concept primarily about the fact that each process has an isolated virtual memory pool, thus being unable to read or modify other process memory?

If not, what is this technology of memory isolation within own virtual memory pools called?

# Answer
> 4 votes
I would say virtual memory is not only about making memory appear bigger than it is, but also about providing many other memory related abstractions, like dealing with pages that are currently not in main memory, adding properties to memory (i.e. non-executability), and standardizing the memory layout of each process. It also allows easy relative addressing in large continuous blocks of data, which might not be able to be allocated contiguously if there was no memory virtualization.

Overcommit in my opinion is less about making it appear as if you had more memory, but more about not actually allocating physical memory if there is no need to do so, like when you allocate a huge chunk of memory "just for safety" which you have no intention of actually using.

Also, you might be confused about what sets apart overcommit and virtual memory, as they are not really two different things, but overcommit is just a part of how Linux and other operating systems implement their virtual memory.

About your last question, I would say that this is just an instantiation of process isolation (https://en.wikipedia.org/wiki/Process\_isolation), using the technology of virtual address space.

# Answer
> 0 votes
“Virtual memory” on its own is about virtualising memory, that is providing something that behaves as if it was memory, but isn’t.

The hardware that is typically used to support virtual memory can often be used for other purposes, like protecting different processes from each other, mapping files into memory, lazy loading of program code as required, or sharing library code between multiple processes while using memory for it only once.

---
Tags: memory-management
---


# Question
Title: How can a 32bit CPU have an addressable memory size of 16TB?
Frequently, on a 32-bit CPU, each page-table entry is 4 bytes long, but that size can vary as well.

A 32-bit entry can point to one of $2^{32}$ physical page frames.

If frame size is 4 KB (212), then a system with 4-byte entries can address $2^{44}$ bytes (or 16 TB) of physical memory.

The above statement is taken from the book "Operating System Principles" by Galvin.

If all 32 bits in a 32-bit CPU are used to refer to pages , then we can have $2^{32}$ pages. But then no more bits will be left to point to memory inside a page of size $2^{12}$ bits since all 32-bits have been used up.

How can we thus say that $2^{44}$ bytes are addressable?

# Answer
> 2 votes
The $32$ bit page frame address acts as a base address and will be typically stored in an index register.

An individual machine code instruction (e.g. a branch instruction) will then contain a $12$ ~~byte~~ bit offset. The offset is added to the base address to create the complete $44$ ~~byte~~ bit address.

---
Tags: operating-systems
---


# Question
Title: Is "represents" a symmetric relation in the provided answer to TAOCP exercise 1.1.9?
In exercise 1.1.9 of volume 1 of The Art of Computer Programming, the reader is asked to

> formulate a set-theoretic definition for the concept "$C\_2$ is a representation of $C\_1$"

where $C\_1$ and $C\_2$ are computational methods described in the previous few pages (reproduced here so the question can be answered without needing the book).

> Let us formally define a computational method to be a quadruple $(Q,I,\Omega,f)$, in which $Q$ is a set containing subsets $I$ and $Ω$, and $f$ is a function from $Q$ into itself. \[...\] The four quantities $Q$, $I$, $\Omega$, $f$ are intended to represent repectively the state of the computation, the input, the output, and the computational rule.

When I looked at the answer in the back, this definition was proposed:

> For example we can say $C\_2$ represents $C\_1$ if there is a function $g$ from $I\_1$ into $I\_2$, a function $h$ from $Q\_2$ into $Q\_1$, and a function $j$ from $Q\_2$ into the positive integers, satisfying the following conditions:
>
> * a) If $x$ is in $I\_1$ then $h(g(x)) = x$
> * b) If $q$ is in $Q\_2$ then $f\_1(h(q)) = h(f\_2^{\[j(q)\]}(q))$, where $f\_2^{\[j(q)\]}$ means that the function $f\_2$ is to be iterated $j(q)$ times.
> * c) If $q$ is in $Q\_2$ then $h(q)$ is in $\Omega\_1$ if and only if $q$ is in $\Omega\_2$

Later on, discussing this definition, Knuth writes (emphasis mine):

> The relation "$C\_2$ represents $C\_1$" generates an **equivalence relation** in which two computational methods apparently are equivalent if and only if they compute isomorphic functions of their inputs ...

To be an equivalence relation, a relation must be symmetric. That is, for a relation $R$, $(a, b) \in R$ implies $(b, a) \in R$. I don't believe this is true of the given definition.

Consider the computational methods $C\_1$ and $C\_2$, where

\begin{align\*} C\_2 &= \\{Q\_2, I\_2, \Omega\_2, f\_2\\}\\ C\_1 &= \\{Q\_1, I\_1, \Omega\_1, f\_1\\}\\\\ I\_2 &= \\{a\_1, a\_2\\}\\ \Omega\_2 &= \\{b\_1, b\_2\\}\\ Q\_2 &= I\_2 \cup \Omega\_2\\ f\_2 &= \\{(a\_1, b\_1), (a\_2, b\_2), (b\_1, b\_1), (b\_2, b\_2)\\}\\\\ I\_1 &= \\{c\\}\\ \Omega\_1 &= \\{d\\}\\ Q\_1 &= I\_1 \cup \Omega\_1\\ f\_1 &= \\{(c, d), (d, d)\\} \end{align\*}

It can be shown that $C\_2$ represents $C\_1$ by $g(q) = a\_1$, $h = \\{(a\_1, c), (a\_2, c), (b\_1, d), (b\_2, d)\\}$, and $j(q) = 1$.

However, $C\_1$ cannot represent $C\_2$, because for any proposed $g: I\_2 \rightarrow I\_1$ it must be the case that $g(a\_1) = g(a\_2) = c$. But $h(c)$ can only be either $a\_1$ or $a\_2$. If $h(c) = a\_1$, then $h(g(a\_2)) = a\_1 \neq a\_2$, but if $h(c) = a\_2$, then $h(g(a\_1)) = a\_2 \neq a\_1$. So in either case, the first requirement cannot be satisfied.

Has this been discussed elsewhere? So far my online searches haven't revealed any answers on the subject. To the best of my knowledge, this hasn't been errata'd (checked here).

Am I understanding the definition properly?

I'm uncertain about my result because of the specific wording "from $Q\_2$ *into* $Q\_1$", which seems to have varying meanings depending on where you ask (if it means "injection", it adds different inconsistencies). It also seems strange to me that this property would be overlooked, since Knuth also specifically mentions that "represents" is transitive, and a counterexample like this is quite easily constructed.

In summary: is it not symmetric? Has this been addressed somewhere? Am I owed 0x$1.00?

# Answer
> 3 votes
I slept on it and remembered there was another wording issue that was bugging me: "*generates* an equivalence relation". I wasn't familiar with it and assumed it just meant "is an equivalence relation". Turns out I was wrong. It has a very specific meaning that Wikipedia describes thusly:

> Given any binary relation $A \subset X \times X$ on $X$, the equivalence relation generated by $A$ is the intersection of the equivalence relations on $X$ that contain $A$.

In short, no, "represents" isn't a symmetric relation, nor did Knuth claim it is; he claimed that an equivalence relation could be constructed from it, which is true. Apparently my "knowledge of high school algebra", listed as the primary prerequisite to reading, is lacking.

---
Tags: computation-models
---


title: Visit all vertices of a graph

text:
# Question
Title: Visit all vertices of a graph
I need to find the fastest route passing in all vertices

* Each vertex is a class.
* I can choose the number of classes for semester.
* Some classes have prerequisites (A and B need to be done one semester before C), so I can't do A, B and C at the same time.
* Some classes (C in this case) have only in the second semester of the year (a year has only 2 semester).

So let's say that I study 2 classes each semester

**Worst case possible:**

First semester of year 1:

* Study A and D

Second semester of year 1:

* Study B (C can't be done because A and B is a prerequisite)

First semester of year 2:

* nothing (C can only be done in the second semester)

Second semester of year 2:

* Study C

**The optimal answer would be:**

First semester of year 1:

* Study A and B

Second semester of year 1:

* Study C and D

I know the basics of the most common graph algorithm like Kruskall, Prim, DFS... but I just don't know how I could apply them to my problem, the first think that I thought was use Dijkstra algorithm to pass in all vertices but how I would take in count that C can only be done at certain semesters? maybe I should use different algorithms at the same time?

This is not an exercise, it's a real problem that exists at my college, and I would like to solve using a smarter solution using an algorithm rather than a hard coded implementation. Anything that helps me to guide to the right direction will be well appreciated.

# Answer
> 2 votes
Ignoring the even semester constraints, you can model this as a scheduling problem where classes are jobs of processing time $1$ which have to satisfy precedence constraints and must be processed on a parallel machine that can process at most a fixed number $m$ of jobs at the same time. In standard notation, this problem would be called $Pm\mid\text{prec},p\_j=1|C\_\text{max}$ and is NP-complete (Ullman, *NP-complete scheduling problems*, J. Comp. Sys. Sci., 10, 1975).

That said, for the size of problems you may be interested in, an integer programming model can likely be solved to optimality. If you let the semesters be $S=\\{1,2,\ldots,s\\}$, where $s$ is some upper bound on the number of semesters, $m$ the maximum number of classes you can do every semester, and $\prec$ the predecence relation (i.e. $c\prec c'$ if class $c$ must precede class $c'$) a formulation would be \begin{align} \text{minimize } & C\_\text{max},\\ \text{subject to } & C\_\text{max} \geq s\\,x\_{cs}, & \forall c,s,\\ & \sum\_c x\_{cs} \leq m, & \forall s,\\ & \sum\_s x\_{cs} = 1, & \forall c,\\ & 1+\sum\_s s\\,x\_{cs} \leq \sum\_s s\\,x\_{c's}, & \forall c\prec c'\\ & x\_{cs}\in\\{0,1\\}, & \forall c,s, \end{align} where $x\_{cs}=1$ indicates that class $c$ is done in semester $s$. It would be also easy to add even semester restrictions to this model.

# Answer
> 0 votes
If there is no upper bound on the number of classes per semester and the dependencies are acyclic, this can be solved by a modified topological sort as follows:

Schedule every class for which all (zero or more) prerequisites are met in the earliest semester in which they are available. Repeat this for all remaining classes (i.e. those not yet scheduled), scheduling them in the earliest semester in which (a) they are available; and (b) all prerequisites have been scheduled in some earlier semester.

This schedules all classes. Call the schedule $S$, and let $C$ be some class. If there is another valid schedule $S'$ which schedules $C$ earlier, then some dependency of $C$ must also be scheduled earlier, or else $S'$ would schedule $C$ invalidly. Chase earlier scheduled dependencies until you reach a class $C\_0$ with no dependencies (one such class exists since the dependencies are acyclic). It too must have some dependency which is scheduled earlier in $S'$ than in $S$, but this is impossible since it has no dependencies. Thus no such $S'$ can exist, and $S$ schedules all classes optimally.

---
Tags: algorithms, graphs, search-algorithms
---


# Question
Title: Understanding addition overflows when performing full, signed multiplication of two 64-bit numbers
I am close to solving question 3.59 from Computer Systems: A Programmer's Perspective 3rd Editionby Randal E. Bryant and David R. O'Hallaron, however I am having difficulties with understanding the result.

Question 3.59 asks you to examine a sample of C and x86\_64 assembly code that performs a full, signed multiplication of two 64-bit numbers, producing a 128-bit result, and explain how the code is working. The C and assembly is below.

```
1  #include <stdint.h>
2  typedef __int128 int128_t;
3
4  void store_prod(int128_t *dest, int64_t x, int64_t y) {
5      *dest = x * (int128_t) y;
6  }

```

```
# x in %rsi, y in %rdx
1  store_prod:
2    movq    %rdx, %rax
3    cqto
4    movq    %rsi, %rcx
5    sarq    $63, %rcx
6    imulq   %rax, %rcx
7    imulq   %rsi, %rdx
8    addq    %rdx, %rcx
9    mulq    %rsi
10   addq    %rcx, %rdx
11   movq    %rax, (%rdi)
12   movq    %rdx, 8(%rdi)
13   ret

```

The book suggests thinking about the problem by recognizing that when $x$ and $y$ are extended to 128-bits, they can be written as $x = 2^{64}x\_{h} + x\_{l}$ and $y = 2^{64}y\_{h} + y\_{l}$, where $x\_{h}$, $x\_{l}$, $y\_{h}$, and $y\_{l}$ are 64-bit values.

I see that mathematically

$$ \begin{align\*} xy &= (2^{64}x\_{h} + x\_{l})(2^{64}y\_{h} + y\_{l}) \\ &= 2^{128}x\_{h}y\_{h} + 2^{64}(x\_{h}y\_{l} + x\_{l}y\_{h}) + x\_{l}y\_{l}. \end{align\*} $$

Since $x\_{h}$ and $y\_{h}$ are the sign extended parts of $x$ and $y$, we do not care about the $2^{128}x\_{h}y\_{h}$ term in the final value, so we really only care about $2^{64}(x\_{h}y\_{l} + x\_{l}y\_{h}) + x\_{l}y\_{l}$, which is how the value is calculated in the assembly code.

My misunderstanding comes about in lines 8 and 10 in the assembly code. Line 8 calculates $x\_{h}y\_{l} + x\_{l}y\_{h}$ and line 10 calculates $2^{64}(x\_{h}y\_{l} + x\_{l}y\_{h}) + x\_{l}y\_{l}$.

My question is why do we not have to worry about overflows when executing the addition instructions on these lines. Even if an overflow occurs, why are the bits of the result correct? Is it because any value resulting from an overflow would en dup going beyond 128-bits, which we then don't care about?

# Answer
Your explanations are a bit incorrect. What line 10 does is to add the high 64-bit word of $x\_l y\_l$ (`%rdx` after line 9) to $2^{64} (x\_h y\_l + x\_l y\_h)$. The low 64-bit word has been computed in line 9 and is in `%rax`.

Now, all the overflows that have been ignored will affect bit 128 only, i.e. the obtained result can differ from the correct result only by a multiple of $2^{128}$. But since one is interested in the result modulo $2^{128}$, such overflows do not matter.
> 1 votes

---
Tags: algorithms, multiplication, assembly
---


# Question
Title: How to construct a perfect BST from an unbalanced BST with n elements (assuming that n=(2^i)-1, i is natural)
How do I construct a perfect BST from an unbalanced BST with $n$ elements (assuming that $n=2^i-1$, $i$ is natural). \** At the worst case of $O(n)$\**.

# Answer
A simple way is as follows: do a symmetric visit of the BST (in time $O(n)$) and write down the elements in increasing order to an array $A$. Then reconstruct the BST from $A$.

If you're fine with a recursive algorithm, and the positions of $A$ are indexed form $0$ to $n-1$, then the root $r$ of the new BST will be exactly the element $A\[\frac{n-1}{2}\]$. The elements in $A\[0\], \dots, A\[\frac{n-1}{2}-1\]$ will be those of the subtree $L$ rooted in the left child of $r$, and the elements in $A\[\frac{n-1}{2}+1\], \dots, A\[n-1\]$ will be in the subtree $R$ rooted in the right child of $r$.

Notice that $|L| = 1 + \frac{n-1}{2}-1 = \frac{2^i - 2}{2} = 2^{i-1}-1$ and $|R| = 1 + (n - 1) - (\frac{n-1}{2} + 1 ) = (n - 1) - \frac{n-1}{2} = \frac{n-1}{2} = 2^{i-1}-1$, so you can apply this algorithm recursively.

The time required is $T(n) = T(2^i - 1) = 2 T(2^{i-1} - 1) + \Theta(1)$, with $T(1)=\Theta(1)$, which has solution $T(n)=\Theta(n)$.
> 1 votes

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


# Question
Title: How to detect number of specific object in an image and it's diameter(size)?
I have two images of `IRON RODS` (i.e only two images) and I want to detect how many rods are there in each image and get the diameter of each rod in a image?

I don't know where to start as there are lot of articles regarding object detection and it's hard to find one for my use-case.

If you can help me with a abstract view on how to model such requirement? Please point me a right direction.

Doubt:

1) How can I train with two images and then how to count numbers of rods are there in each image and retrieve it's diameter?

# Answer
> 3 votes
Well to answer your last question, you cannot train with the images that you want to test your algorithm with, that is a paradox...

You will need more than just two images if you want to build a robust model that can detect each rod AND predict their diameter. Those are two different problems, and you might want to split your model in two branches: one to detect each rod, the other to predict its diameter as a regression problem.

If you can obtain a larger dataset with ground truth, then you can proceed to train your model. I would tend to say that using an object detector CNN would be overkill, but if you need to predict the diameter of each rod in the image, it might be necessary. So maybe look into TinyYOLO for the detection part, and then you could use the predict bounding box of each rod in the image for a small perceptron to infer the diameter.

# Answer
> 1 votes
You might be able to solve your problem with classical image processing methods: binarize the image (to separate the black background from the rods), smooth with morphological operations, then use floodfill or connected components to identify each vertical black region. Each rod is a space between two vertical black regions, so you can then count the number of rods directly.

This assumes that all images look pretty similar to the example image you provided, and that there's not too much diversity in the images.

---
Tags: computer-vision
---


# Question
Title: Maximizing sum of numbers within a sequence
> Write an algorithm that, given sequence *seq* of *n* numbers where 3 \<= *n* \<= 1000 and each number *k* in *seq* 1 \<= *k* \<= 200, finds maximum sum by repeatedly removing one number from *seq*, except for first and last number in *seq*, and adding its value to sum of two adjacent numbers. Algorithm ends when there are only two numbers left.

For example:
\[2, 1, 5, 3, 4\], sum = 0
\[2, **1**, 5, 3, 4\], sum = 1 + 2 + 5 = 8, 1 removed
\[2, 5, **3**, 4\], sum = 8 + 3 + 5 + 4 = 20, 3 removed
\[2, **5**, 4\], sum = 20 + 5 + 2 + 4 = 31, 5 removed
\[2, 4\] only 2 numbers left so algorithm ends

So far I've written brute force algorithm checking all possible combinations but it's not well suited for large sequences.

My question is, is there more efficient algorithm solving this problem?

# Answer
I'll explain the Dynamic Programming approach to your problem using your sample sequence $\[2,1,5,3,4\]$. This approach is based on analysis of *sub-problems* \- in your case each sub-problem is simply a task to find the maximal *value* (in the sense you described in your question) for some sub-sequence. These sub-problems are *related* to each other - this *reducibility* relation means that one sub-problem can be reduced to another one in a single step. For example, the sub-problem $\[2,1,5,3,4\]$ can be reduced to sub-problems $\[2,5,3,4\]$, $\[2,1,3,4\]$ and $\[2,1,5,4\]$ by removing a single number from the sequence.

The graph of sub-problems with this reducibility relationship is below. It's easy to see that our problem is equivalent to a problem of finding a *path* from the vertex $\[2,1,5,3,4\]$ to the vertex $\[2,4\]$ (or vice versa), which will give us the maximal value for the vertex $\[2,1,5,3,4\]$ (see the path, marked by red color).

Not every problem can be solved by decomposition into sub-problems - such a problem must have Optimal Substructure for that. In our case it means that all the sub-problems along the optimal reducibility path must also have optimal solution. For example, the value of the vertex $\[2,5,3,4\]$ can be calculated along two paths, so we need to choose the maximal value (23) along the red path and forget about another path.

This **local optimization** is the reason why the Dynamic Programming method works so well for large problems. It often allows us to reduce exponential time complexity to polynomial one.

There are two ways to solve our problem using Dynamic Programming - "top-to-bottom" and "bottom-up". In our case they are equivalent to traversing our graph from the vertex $\[2,1,5,3,4\]$ to the vertex $\[2,4\]$ or vice versa.

* The **top-to-bottom** way involves developing a recursive function with two arguments - a sub-problem description (sub-sequence in our case), and mapping from the sub-problem description to the values space. This mapping will gather information about already solved sub-problems, so we will never solve the same problem again. The function will need to reduce (in one step!) the given sub-problem to all the possible sub-sub-problems and find the maximum of calculated values. Using such a mapping is often called Memoization.
* The **bottom-up** way starts from the simplest sub-problem ($\[2,4\]$ with value = 0) and assigns values to all the sub-problems going up layer by layer, again maximizing the value of each sub-problem, calculated over its sub-sub-problems. Here we don't need recursion, however multiple nested loops will be needed, and it's not easy to program that correctly right away.

Now - it's your job to choose a way you want and solve your problem in general case.

**ADDITION.** We can make our graph oriented (each arc is oriented from top to bottom) and weighted (each arc weight is equal to the portion of value, given by its beginning) - then the described above "bottom-up" approach becomes equivalent to the Longest Path in Acyclical Digraph Problem.
> 2 votes

# Answer
$$ \mathrm{OPT}\[i,j\] = \begin{cases} \max\_{h\in\\{i+1,\dots,j-1\\}} \left\\{\mathrm{seq}\[i\] + \mathrm{seq}\[h\] + \mathrm{seq}\[j\] + \mathrm{OPT}\[i,h\] + \mathrm{OPT}\[h,j\]\right\\} &\mbox{if } j-i \> 1 \\ 0 & \mbox{if } j-i = 1 \end{cases} $$ where $1\le i\<j\le n$.

Thank you all for your advices, especialy @Steven for providing link to another question.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Questions on shortest path and minimum spanning tree
T/F Questions

1. Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Solution - False

I think this should be True, as Dijkstra's Algorithm sums the paths from source to each vertex. If every edge weight is increased by a constant, then nothing should be changed if all edges are positive. If some edges are negatives, then I don't know if Dijkstra's Algorithm still applies here.

2. Adding a constant to every edge weight does not change the solution to the MST problem. (I don't have the solution for this)

I think this is True for the same reason above.

Can someone confirm on this?

# Answer
You are wrong on the first one and right on the second one (but for the wrong reason).

To see that (1) is false, just observe that there exists a constant $c$ such that adding $c$ to all weights turns the weighted minimum distance problem into the unweighted one.

On the other hand, (2) is true because every spanning tree contains has exactly $|V|-1$ edges, therefore adding $c$ to all weights adds $c(|V|-1)$ to the total cost of each spanning tree.
> 3 votes

# Answer
From @quicksort answer it should be clear that min spanning tree remains same. Just to understand why it is false for the shortest path problem, consider the following counter-example. Let a graph contain only the following 2 paths-: $S-W-T$ and $S-U\_1-U\_2-U\_3-T$. Let the weights of the edges be -: $S-W : 2\\ W-T : 2\\ S-U1 : 1\\ U1-U2 : 1\\ U2-T : 1$

Now the shortest S-T path is S-U1-U2-T. Now add a weight of 5 to all edges, and convince yourself the new shortest path will be S-W-T
> 1 votes

# Answer
This answer on stackoverflow has an example of why 1 is false.

https://stackoverflow.com/questions/10790909/adding-weights-to-all-edges-of-graph-change-in-spanning-tree-and-shortest-path

Quoting from the above:

> Consider a graph with 3 vertices (A,B,C), with the following edges:
>
> ```
> A-B = 1
> A-C = 0
> C-B = 0
>
> ```
>
> The shortest weighted path between A and B is A-C-B. If you add 2 to all the weights, your shortest path becomes A-B.
> 1 votes

# Answer
$\mathbf 1.$

Say there are two paths from node A to node B.

```
Path1 has 4 edges.

Path2 has 2 edges.

```

An overall increase in edge weight by x increases,

```
the cost of Path1 by 4x.

the cost of Path2 by 2x.

```

If Path 1 was the optimum path found by Dijkstra then in order for it to remain the optimum path even after the increase.

$Cost\_{Path1} + 4x \< Cost\_{Path2} + 2x$

or

$2x \< Cost\_{Path2}-Cost\_{Path1}$

For $x= \frac{Cost\_{Path2}-Cost\_{Path1}}{2} $ this is no longer valid.

Consider the given example:-

$\mathbf 2.$

Suppose there are two selections of edges for a MST.

$S\_1$ with cost $Cost\_{S1}$ and edges $E$

and

$S\_2$ with cost $Cost\_{S2}$ and edges $E$

Note that both have the same number of edges since MST is a tree and has $Edges = Vertices -1$

If $S\_1$ is the answer to the MST problem then,

$Cost\_{S1}\<Cost\_{S2}$

An increase in edge weight by $x$ would result in

$Cost\_{S1} + E\*x \<Cost\_{S2} +E\*x$

which is the same.

Thus no value of $x$ changes the answer to the MST problem.
> 0 votes

---
Tags: algorithms, graphs, shortest-path, minimum-spanning-tree
---


# Question
Title: How to evaluate all possible groups of adjacent tiles in 2D array?
I'm working on a tile based game idea in Javascript. It's a math puzzle game where players move around tiles with numbers on them, and the goal is to connect groups of tiles that have a sum of certain goal number, for example 5 or 7 or 9.  However, I'm stuck on the algorithm to detect these sum groups. I know how to do a flood fill algorithm using recursion to detect a group of adjacent tiles, like in the same game. But I don't know how to iterate through all the possible permutations of possible groups, and what is the best way to approach this?

Because the problem is that adjacent tiles form a group, but within that group of tiles there are many possibilities for sub groups. See tiles example below

```
Tile letters     Contains numbers    Represented as graph
+---+---+---+    +---+---+---+
| A | B | C |    | 1 | 5 | 2 |       1---5---2
+---+---+---+    +---+---+---+       |   |
| D | E | . |    | 2 | 1 | . |       2---1
+---+---+---+    +---+---+---+       |
| F | . | . |    | 4 | . | . |       4
+---+---+---+    +---+---+---+

```

So the group is all the tiles A though F, and a subgroup could be A, B and E (1+5+1) but also A, D and F (1+2+4). But A, C and F is not a possible group because those tiles are not adjacent. I suspect it could maybe be approached like it's a graph problem. But then I still don't know how to handle the many possible circular nodes.

So my question is; How to systematically go through and evaluate all possible permutations? Is there an algorithm for something like this? Or can someone explain how to approach this problem?

**EDIT**: I've put my code in the jsfiddle in the link below. It uses flood fill from a starting tile, in the example tile with nr 2. Then for each cell it counts to 15 and uses the bits of that counter to flood-fill to the 4 adjacent tiles (up,down,left,right). However it doesn't work properly because it doesn't consider branching paths. For example, in the jsfiddle example the combination 3-2-4 is never evaluated. https://jsfiddle.net/wu6p49r2/

I know how to do it by hand, see examples below. But what would the algorithm look like, to systematically gather these possible adjacent combinations starting at A?

```
Tiles ex.1    Tiles ex.2        Tiles ex.3
+---+---+     +---+---+---+     +---+---+---+
| A | B |     | A | B | C |     | A | B | C |
+---+---+     +---+---+---+     +---+---+---+
| D |         | D | E |         | D | E |
+---+         +---+---+         +---+---+
                                | F |
                                +---+
All possible adjacent combinations,
starting at A:

A             A                 A
A-B           A-B               A-B
A-D           A-B-C             A-B-C
A-B-D         A-B-E             A-B-E
              A-B-C-E           A-B-C-E
              A-B-E-D           A-B-E-D
              A-B-C-E-D         A-B-C-E-D
              A-D               A-B-E-D-F
              A-D-E             A-B-C-E-D-F
                                A-D
                                A-D-E
                                A-D-F
                                A-D-E-F

```

# Answer
Your groups of tiles can be considered as graphs, where vertices represent tiles and two vertices are connected by edge if and only if their corresponding tiles touch each other side by side. So, in terms of graph theory, the problem you are trying to solve is known as **CISE** (Connected Induced Subgraphs Enumerating). You can find a number of papers, describing algorithms to solve this problem - I'll excerpt here some results from this paper.

We consider undirected simple graphs $G = (V,E)$. Some notations:

* For any vertex $v \in V$, the *open neighborhood* of $v$ is defined as $N(v) = \\{u \space | \space {u, v} \in E\\}$ and the *closed neighborhood* of $v$ is defined as $N\[v\] = N(v) \cup \\{v\\}$.
* For any vertex set $W \subseteq V$ the *open neighborhood* of $W$ is defined as $N(W) = \bigcup\_{v∈W} N(v) \setminus W$ and the *closed neighborhood* of $W$ is defined as $N\[W\] = N(W) \cup W$.
* The graph $G\[W\]$, *induced* by a vertex set $W \subseteq V$, consists of **all** edges from $E$ with **both** ends in the $W$, so $G\[W\] = (W, \\{\\{u,v\\} \in E \space | \space u,v \in W\\})$.

The following recursive function will list all the connected induced subgraphs of the graph $G$, starting from some vertex. Both arguments $P$ and $X$ of this function are vertex sets. The function call `Enumerate({v}, N(v))` will list all the connected induced subgraphs, starting from some vertex $v \in V$. All these subgraphs will contain this vertex. Operations `+` and `-` denote set operations *union* and *minus* on vertex sets.

```
Enumerate(P, X)
  output P
  while vertex set X is not empty
    u = any vertex from X
    remove u from X
    X' = X + (N(u) - N[P])
    Enumerate(P + {u}, X')

```

In order to list all the subgraphs, **not** including this vertex $v \in V$, it should be removed from the graph $G$, and then the above recursive function should be called with another starting vertex.

I've implemented this algorithm and tested it on your example:

```
+---+---+---+
| A | B | C |
+---+---+---+
| D | E |
+---+---+

```

Graph representation of this configuration is below:

The `Enumerate('A', N('A'))` function call was able to find **more** subgraphs, than you mentioned in your question - new ones are marked by asterisk:

```
A
A B
A B C
A B C D    *
A B C D E
A B C E
A B D      *
A B D E
A B E
A D
A D E

```

As far as I understand your primary goal is to find subgraphs, satisfying some condition (sum of vertex weights = constant $M$). You can modify the function above to include checking this condition instead of simply printing $P$, for example:

```
if sum of vertex weights over P is equal to M
  output P
  return

```

Here you need to return from the function after the output because the vertex set $P$ expands with each recursive call, so the sum can only grow and become greater than this constant $M$ further on.

**ADDITION**. My C++ testing code is here.
> 1 votes

# Answer
I suggest you use a search algorithm on the following statespace: the state is a set of adjacent tiles whose numbers sum to 7 or less; it is possible to transition from state $s$ to $s'$ if $s'$ is obtained by adding to $s$ one tile that is adjacent to some tile in $s$. The initial state has the empty set $\emptyset$, and it can transition to any state containing a single tile.

Then, use a search algorithm, such a depth-first search or breadth-first search, to explore all states reachable from the initial state. You can store the reachable states in a hashtable. Whenever you discover a new reachable state, check if the numbers on its tiles sum to 7. If they do, you have found a valid solution.

As an optimization, you can use flood-fill to find all of the groups (connected components), then apply the above algorithm separately to each group.
> 3 votes

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


title: A problem on sets

text:
# Question
Title: A problem on sets
Given a collection C of sets, with union U, find a choice function which chooses a distinct element from each of the sets such that the union of the singleton distinct elements is U.

As an example, if we have the collection {1,2,3,4},{0,2,3,4},{0,1,3,4},{0,1,2,4} and {0,1,2,3} we can choose 1,0,3,4,2 from each of the sets respectively.

Can this be reduced to some another canonical problem? Has it been addressed in the existing literature?

# Answer
You can reduce your problem to maximum bipartite matching on the graph $G = ( U \cup C, E)$, where $E = \\{ (u,c) \in U \times C \\; : \\; u \in c\\}$.
> 2 votes

---
Tags: algorithms, sets
---


# Question
Title: Grokking pseudo-code for solution to gas station problem
I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in *To Fill or not to Fill: The Gas Station Problem*. The algorithm is reproduced below for ease of reference:

There are some obvious things to fix here in any implementation of the algorithm.

* The case $q = 1$ needs special consideration as noted by j\_random\_hacker in this CS SE answer.
* It may happen that no $v$ satisfies $g \leq d\_{uv}$ so that there is no vertex to pick in line 10 of the algorithm. In this case, the table entry should be declared infinite, $C\[u, q, g\] = \infty$.

Even with those two fixes, though, it seems to me that something is still off. As the description supporting the algorithm notes, cases where $c(v) \leq c(u)$ should only be considered when $g \leq d\_{uv}$, hence the special treatment in lines 9 and 10, but this additional constraint can be ignored when $c(v) \> c(u)$ (according to the formula for $A(u, q, g)$ preceding Theorem 2.2). In practice, this means that the generated program does *not* match the recurrence relation: Below is a rough Python implementation of lines 7--11 of Fill-Row (after `r` has been sorted):

```
i = 0
v = r[i]
for g in GV[u]:
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while g > d[v] - d[u]:
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

```

If this implementation is assumed to be a correct implementation of the pseudo-code, it is easy to generate examples where $C\[(u, q, g)\]$ does not match $A(u, q, g)$.

A first attempt at fixing this would be to ignore $g \leq d\_{uv}$ for $c(v) \> c(u)$:

```
i = 0
v = r[i]
for g in GV[u]:
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while True:
        if g <= d[v] - d[u] or c[v] > c[u]:
            break
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

```

This seems to work, in that I haven't been able to construct a counter-example. Yet it seems to me that it shouldn't: If $c(v) \> c(u)$ occurs for low values of $\mathrm{indep}\[v\]$, we risk skipping them for all but the smallest $g \in GV\[u\]$. As such, I would expect that we should rather reset the loop over `r` ($R$ in the paper) for each iteration, moving the first two lines inside the loop over `GV[u]`:

```
for g in GV[u]:
    i = 0
    v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while True:
        if g <= d[v] - d[u] or c[v] > c[u]:
            break
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

```

However, doing so takes us from $O(n \log n)$ to $O(n^2)$, which invalidates Theorem 2.2. You can probably do something more clever by keeping track of the cases $c(v) \> c(u)$ and $c(v) \leq c(u)$ separately, but that doesn't seem to be in the spirit of the pseudo-code (and in particular, I'm aware that an algorithm with lower complexity exists in *A fast algorithm for the gas station problem*, so that clearly we can do *something* to remedy this), so I'm simply wondering: Am I misreading the pseudo-code?

# Answer
> 2 votes
The second implementation is correct (so Theorem 2.2 survives): If the condition $c(v) \> c(u)$ causes the inner `while` to halt, that same value of $v$ will be give the optimal value for every following value of $g$, simply because the condition is independent of $g$.

---
Tags: algorithms, graphs, optimization, dynamic-programming, recurrence-relation
---


# Question
Title: Finding the shortest time to go from one stop to another stop in a train system with many train lines with connection stations
So I was thinking after discussing with my friend the other day, how would I use something like breadth-first or depth-first search to find the fastest time to go from one station to another station if there are a number of different train lines in a subway system. They may cross over each other, maybe multiple times even.

Train line in this case means a train that goes from a starting station to a ending station, with many station stops on the way, where certain station stops may give the option for the rider to swap to another "line" that also has its starting and stoping station. A simple example is a two-line subway system like so:

```
o : station   - : track

                     Line 2
                     START
                       |
                       o
                       |
Line 1 START o -- o -- o -- o -- o -- o END
                       |
                      END

```

I live in Taipei, Taiwan, so you may reference the MRT train map there for reference but it may look fairly complicated. I was looking for tips for a simpler start and ways to work out a solution to a smaller problem first, but the MRT system is my friend and I's target goal.

**What I have though of so far**

* Have an array that holds each stop name on along with the time it takes for previous stop to reach this stop represent a single train line, with each connection to another train line being a nested array at that item.
* Figure out how to tell the algorithm to look through each route to find the destination stop, adding the time taken along the way comparing to find the shortest time.

**Things to Consider**

* The time between each station is known to us. But for the purpose of this question just assume its 5 minutes between each station.
* A train line has a starting stop and a ending stop, but on the way it may stop on a stop that connects to any other train line.
* Any connection to another train line may connect to another line - but access to this third line may be reached by taking a further more complicated route by switching train lines. Meaning if I try out all possibilities it may take looping routes and test forever.
    + Its possible to take a transfer from one line to another, and go either left or right on the new line, i.e. the trains are not one-way.

**So how is it possible to**

Avoid our algorithm making loops, e.g.:

If line 1 connects to line 2 on its third stop, and that connects to a third line, and then back to line 1 later on down line 3. Then if we were to try find the shortest way to go from a stop in line 1 to another stop in line 1, the algorithm may test going from line 1 to line 2 taking the connection then to line 3 back to line 1 and back around.

And also, how do we make it decide where to make the turns, and what is a better way to represent this problem and find the shortest time?

# Answer
> 2 votes
Transform your input to a graph in which each vertex represents a stop on a line. If a stop is shared by multiple lines, then add one copy of the vertex per line and a new super-vertex connected to all such copies with edges of weight 2.5 (so there is a path of length 5 between any two of these stops). Add edges between consecutive stops of the same line with weights matching the travel times.

Use Dijkstra's algorithm to find the shortest path between the starting stop and the last stop.

The time required is $O(n\log n)$ where $n$ is the overall number of (not necessarily distinct) stops across the different lines. This is because is possible to assign edges to vertices so that: 1) each edge is assigned to a "stop" vertex, and 2) each "stop" vertex has at most $2$ edges assigned (i.e., the one towards the "next" stop w.r.t. an arbitrary direction of the line the vertex belongs to, if any, and possibly the one to a super-vertex), showing that the number of edges is at most $2n$.

EDIT:

Here is the graph obtained by applying the above transformation to the example in the question. The edges of the horizontal line are in red, those of the vertical line are in blue. All the vertices representing stops on a specific line are white, while the only super-vertex is in black. Black edges have a weight of $2.5$ each (not shown). The tree vertices in the gray circle together represent the stop at the intersection of the horizontal line and vertical line.

---
Tags: search-algorithms, search-trees
---


title: $L=\{a^ib^i|i\geq0\}$, cfg for $L^2$

text:
# Question
Title: $L=\{a^ib^i|i\geq0\}$, cfg for $L^2$
$L=\\{a^ib^i|i\geq0\\}$, cfg for $L^2$

can you write cfg for $L^2$ where $L=\\{a^ib^i|i\geq0\\}$?

the professor's answer sheet says it's $S\to AA\\ A\to aAb|\lambda$

but I think it is wrong because two $L$ have to be identical with each other.

can you help me figure out if there is cfg describing $L^2$?

# Answer
> 1 votes
The square language $L^2$ is defined as follows: $$ L^2 = LL = \\{ xy : x,y \in L \\}. $$ There is no requirement that $x = y$. Indeed, in your case $L^2 \supsetneq \\{ w^2 : w \in L \\}$.

---
Tags: automata, context-free
---


# Question
Title: Constructing a DFA of strings that are in A but not in B
I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c}

I am not really sure where to even start with this one, so any hints or suggestions would be much appreciated. I have never really encountered anything like this before. How do I represent "not in B". I have only dealt with more 'tangible' things, such as divisible by 5, a*b(cb)*, etc. This doesn't really have a rule...I don't even know what the set B is.

# Answer
> 1 votes
Take a DFA $D\_A$ for $A$ and a DFA $D\_B$ for $B$.

Define a DFA $D$ for $A \setminus B$ as follows:

* The set of states of $D$ is the cartesian product of the set of states of $D\_A$ with the set of states of $D\_B$.
* The initial state of $D$ is $(a\_0, b\_0)$ where $a\_0$ is the initial state of $D\_A$ and $b\_0$ is the initial state of $D\_B$.
* A state $(a,b)$ of $D$ is an accepting state iff $a$ is an accepting state of $D\_A$ and $b$ is *not* an accepting state of $D\_B$.
* A state $(a,b)$ has a transition to state $(a',b')$ when character $c \in \Sigma$ is read, which I will denote by $(a,b) \xrightarrow{c} (a', b')$, if and only if $a \xrightarrow{c} a'$ in $D\_A$ and $b \xrightarrow{c} b'$ in $D\_B$.

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